Local Fairness in General Topology Networks with Convergence Routing

Convergence Routing is a unique varienat of deflection routing which ensures that packets (or cells) will converge to their destinations along a global sense of direction. In this work we show how a global sense of direction can be used in an arbitrary network for the design of a control algorithm which (a) ensures fair access in switch-based local area networks, (b) is efficient with respect to performance measures we have developed, and (c) is easily interfaced to the convergence routing mechanism. We present performance measures which assess the new access- and flow-control algorithm: (i) Locality - only the sub-network containing conflicting traffic streams gets involved in the fairness regulation. (ii) scalability - the data-structure sizes used in the algorithm are a function of the switching node degree, and uses constant space control signals of only 2-bit (the ATM standard, for example, dedicates four bits in the header of each cell to generic flow-control). (iii) Linear access-time measured by the maximal clique in the conflict-graph to which a node belongs, and a frequency which is inverse linear in this parameter (when the traffic pattern stabilizes).

By: Alain Mayer (Columbia Univ.), Yoram Ofek and Moti Yung

Published in: IEEE INFOCOM 95: The Conference on Computer Communication: 14th Annual Joint Conference of the IEEE Computer and Communication Societies; Bringing Information to the People, Vol. 2. Los Alamitos, CA, IEEE Computer Society Press, 1995. p. 891-9, IEEE in 1994

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .