Open Collections

Load-sensitive adaptive routing (LSAR) for computer networks

University of British Columbia

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.

Thesis/Dissertation

application/pdf

2009-10-28

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/14233

Electrical and Computer Engineering

University of British Columbia

UBCV

DSpace