3 - Minimum-hop Route Maintenance

Summary

A basic problem that must be addressed in any design of a distributed network is the routing of messages. That is, if a node in the network wants to send a message to some other node in the network or receives a message destined for some other node, a method is needed to enable the node to decide over which outgoing link it has to send this message. Algorithms for this problem are called routing algorithms. In the sequel we will only consider distributed routing algorithms which are determined by the cooperative behavior of the local routing protocols of the nodes in order to guarantee effective message handling and delivery.

Desirable properties of routing algorithms are for example correctness, optimality, and robustness. Correctness seems easy to achieve in a static network, but the problem is far less trivial in case links and nodes are allowed to go down and come up as they can do in practice. Optimality is concerned with finding the “quickest” routes. Ideally, a route should be chosen for a message on which it will encounter the least delay but, as this depends on the amount of traffic on the way, such routes are hard to predict and hence the goal is actually difficult to achieve. A frequent compromise is to minimize the number of hops, i.e., the number of links over which the message travels from origin to destination. We will restrict ourselves to minimum-hop routing. Robustness is concerned with the ease with which the routing scheme is adapted in case of topological changes.