Open Collections

The online and offline properties of routing algorithms in MPLS

University of British Columbia

This thesis focuses on the route allocation problem. In particular, we consider how to optimally place a LSP on a network such that the bandwidth demand is guaranteed. The objection function is throughput. Specifically, two metrics are used: the number of rejected requests and the amount of rejected bandwidth. We evaluate the performance of five routing algorithms: the shortest path algorithm, the widest-shortest path algorithm, the shortest-widest path algorithm, the minimum interference routing algorithm, and the profile-based routing algorithm. In addition, we investigate the sensitivity of history of the two more sophisticated routing algorithms: the minimum interference routing algorithm, and the profile-based routing algorithm. We explore the sensitivity of history through the use of the batch process scheme. The batch process scheme allocates tunnels for a batch of requests at a time, and can be viewed as a continuum with its ends being the online and offline scheme. We compare the performance of routing algorithms with varying batch sizes indicating the changes of the history information. The routing decisions that routing algorithms make significantly influence the performance of the network. Thus, it is beneficial to evaluate the performance of routing algorithms. Furthermore, with the batch process scheme, algorithms can make use of the history information in order to make better routing decisions which would greatly enhance the utilization of the network resources.

Thesis/Dissertation

application/pdf

2009-09-22

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/13049

Computer Science

University of British Columbia

UBCV

DSpace