A New Distributed and Adaptive Approach to Routing and Load Balancing in Dynamic Communication Networks

M. Heusse, ENST de Bretagne, Brest, France

S. Guérin, ENST de Bretagne, Brest, France

D. Snyers, ENST de Bretagne, Brest, France
Email: Dominique.Snyers@enst-bretagne.fr

P. Kuntz, ENST de Bretagne, Brest, France
Email: Pascale.Kuntz@enst-bretagne.fr

This work presents a unified overview of a new family of distributed algorithms for routing and load balancing in dynamic communication networks. These new algorithms are described as an extension to the classical routing algorithms: they combine the ideas of online asynchronous distance vector routing with adaptive link state routing. Estimates of the current load and link costs are measured by sending routing agents in the network that mix with the regular information packets and keep track of the delays encountered during their journey. The routing tables are then regularly updated based on that information without any central control nor complete knowledge of the network topology. Two new algorithms are proposed here. The first one is based on round trip routing agents that update the routing tables by backtracking their way after having reached the destination. The second one relies on forward agents that update the routing tables directly as they move toward their destination. An efficient co-operative scheme is proposed to deal with asymmetric connections. All these methods are compared on a simulated network with various traffic loads; the robustness of these algorithms to network changes is also studied.