Analysis of routing algorithms for large networks
Raj Nair · 1993
The dissertation studies routing algorithms for large networks. The dissertation is divided into four chapters. Chapter one describes the background. Chapter two presents a distributed algorithm for finding multiple disjoint paths in a network. Multiple paths may be used in large networks to reduce congestion, increase reliability of packet delivery and improve communications security. We compare our algorithm with an alternate approach that does not always retain the shortest path as one of its disjoint paths. The alternate approach finds a pair of disjoint paths of minimum total cost. Simulation shows that our algorithm requires 3 to 4 times fewer messages to discover paths of comparable quality. Chapter three presents a formal specification and analysis of the Election and Flooding Algorithms of Open Shortest Path First (OSPF), a dynamic hierarchical routing protocol draft standard for the Internet. A refined state machine specification of the Election Algorithm is presented. State space analysis is performed on a subset of the Election Protocol in a three-router multiaccess network with zero-length channels using a Prolog-based analyzer. The analysis shows that the protocol has no deadlock states or non-executable transitions. The protocol is not dependent on a particular transition to make progress after the $Wait\sb{-}Timer\sb{-}Expiration$ event. Deleting this event simplifies the protocol without affecting the functionality, but with a possible performance degradation. The number of transitions needed to reach a consensus in the election grows in greater proportion than the number of participants of the election. Therefore, it is recommended that only a few routers be made eligible for participating in elections. A simulation of the Flooding Protocol on 20, 50 and 80 node, point-to-point networks yields three results: (1) For the 50 node network, link speeds over 4000 kbps result in input-buffer overflow causing retransmissions. The bootup-convergence-time increases by two to three times the RxmtInterval for link speeds in the ranges from 4000 to 6000 kbps and above 50 Mbps respectively. The increase is because of several unacknowledged flooding packets received within an RxmtInterval. (2) For 20 and 50 node networks, the input buffer size has little impact on the bootup-convergence-time. For the 80 node network, a small change in the input-buffer size drastically changes the bootup-convergence-time. (3) For the 50 node network, reducing the RxmtInterval lowers the bootup-convergence-time for high link speeds. Chapter five is the conclusion.