M. Heusse, ENST de Bretagne, Brest, France
Martin.HEUSSE@enst-bretagne.fr
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.