Routing in hierarchical networks
Shukri Abdallah · 1993
The dissertation studies routing in two types of hierarchical networks: area and landmark hierarchies. The dissertation is divided into five chapters. Chapter one is an introduction to routing. Chapter two presents a distance vector algorithm for alternate path routing that can be used in an area or in a landmark hierarchy. The communication and computational complexities of this algorithm are 2E messages per destination and O(d * D) steps at a node respectively, where D is the network diameter, d is the average node degree and E is the number of links in the network. Chapter three presents a congestion control scheme based on alternate path routing. In the scheme, if a node encounters congestion or loses its preferred neighbor on its primary path to a destination, it sends data packets to that destination over pre-computed alternate paths. The scheme ensures that data packets do not travel in loops and limits the spread of congestion to neighboring nodes. Simulations of the scheme show that alternate path routing reduces the number of dropped packets, achieves a more uniform link utilization than shortest path routing and alleviates congestion in networks under light to moderate loading. Chapter four presents a formal specification and a discrete-event simulation of the Election Protocol of the Open Shortest Path First (OSPF) routing algorithm. OSPF is a dynamic, area-hierarchy routing protocol to support the TCP/IP protocol suite. The simulation shows three results: (a) The Designated Router (DR) can be elected in a constant time. (b) If a router has a limited amount of input buffer space, a competition for buffer space between the Election and the Flooding Protocols increases the election time and causes an oscillatory behavior. (c) In the worst case, when the DR and the BDR fail at the same time, the DR-agreement-time is bounded above by twice the HelloInterval. Chapter five is the conclusion.