Distributed Coordinated Deflection Routing Algorithms for High Speed Networks

Article type: Research Article

Authors: Bona, Raffaele | Davoli, Franco | Di Febbraro, Angela

Affiliations: Department of Communications, Computer and Systems Science (DIST), University of Genova, Via Opera Pia, 13 – 16145 Genova, Italy

Abstract: The deflection routing problem for a high speed network is dealt with, where every packet must be associated with one output port at the instant of its arrival at a switching node. Conflicts occur whenever two or more should be sent through the same output port. The algorithm proposed to solve such situations coordinates locally optimal strategies, based on instantaneous information, via a mechanism to exchange information among the nodes. Such a coordination is performed by making each node pass some aggregate information, regarding the traffic ‘congestion’ in the downstream portion of the network, to its predecessors. The algorithm is first stated in its optimal version, which may require a significant computational overhead. For this reason, a suboptimal, but computationally efficient version of the algorithm is also introduced. Some simulation results are presented to compare the performance of both versions of the algorithm with those of other routing policies previously proposed in the literature.

Keywords: Deflection Networks, Dynamic Routing, Distributed Algorithms

DOI: 10.3233/JHS-1995-4305

Journal: Journal of High Speed Networks, vol. 4, no. 3, pp. 287-297, 1995