UBC Theses and Dissertations
Load-sensitive adaptive routing (LSAR) for computer networks Wang, Hao
Shortest Path First (SPF) routing protocols such as OSPF and IS-IS are the dominant intradomain Internet routing protocols nowadays, and are widely used in the Internet Service Provider (ISP) backbone networks. The weights, or the lengths, of the links in an OSPF/IS-IS network are set by the network operator and usually are not changed during the network operation. The packets are routed along the shortest paths from the sources to the destinations. The paths between the origin and destination pairs are fixed regardless of the traffic load changes, since the weights of the links are predetermined. The objective of this thesis is to investigate a way of adapting the weights in SPF routing, such as OSPF and IS-IS, in real-time dynamically according to the traffic loads of the links and to evaluate its performance over non-adaptive routing. The feedback effect and the stability issue of adaptive routing are studied from a control point of view, and the analysis shows why Minimal-Delay Adaptive Routing in the early ARPANET is not stable and what can be done to make adaptive routing stable. The thesis presents a routing algorithm, Load-Sensitive Adaptive Routing (LSAR), which keeps the traffic balancing ability of adaptive routing and avoids the undesirable unstable behavior at the same time. Finally, the performance of LSAR is tested in simulations. The simulation software used is Network Simulator 2 (ns2). The result shows that, compared with non-adaptive OSPF/IS-IS routing, LSAR improves the network throughput and reduces the packet drop rate significantly, and does not show unstable behavior under either light or heavy traffic load.
Item Citations and Data