Distributed, scalable routing based on link-state vectors

Reviewer: Jeffrey David Oldham

The authors introduce link vector algorithms for routing in large networks. Each router executing a link-vector algorithm maintains information about preferred paths to all other network routers rather than maintaining information about all links in the network. Thus, router storage and communication requirements are less than for distance-vector and link-state algorithms. To construct its set of preferred paths, a source router requests the preferred paths of all neighboring routers and then uses a path-selection algorithm such as shortest-path routing. When a link's performance parameters (for example, congestion level or availability) change enough to affect routing, the adjacent nodes notify their neighbors of all changes to their sets of preferred paths. Each router that changes its set of preferred paths continues propagating the information. The authors compare their algorithms with existing algorithms for routing in a distributed network and present a pseudocode implementation. After proving that every router receives recent link-state information and that the routing tables do not contain loops, they show that the communication, time, and router storage complexity are bounded by the complexity of current router algorithms. The paper ends with limited results from a simulation. This well-written paper omits discussion of whether the algorithm prevents oscillations in path preference. The authors need to conduct more extensive simulations to validate the effectiveness of the routing algorithms . A succinct discussion of existing router algorithms motivates the link vector algorithms while assisting readers less familiar with routing. The algorithmic analysis uses a minimum of mathematical notation.