Routing Bandwidth-Guaranteed Paths in MPLS Traffic Engineering: A Multiple Race Track Learning Approach

摘要

This paper presents an efficient adaptive online routing algorithm for the computation of bandwidth-guaranteed paths in Multiprotocol Label Switching (MPLS)-based networks by using a learning scheme that computes an optimal ordering of routes. The contribution of this work is twofold. The first is that we propose a new class of solutions other than those available in the literature, incorporating the family of stochastic Random Races (RR) algorithms. The most popular previously proposed MPLS-based Traffic Engineering (TE) solutions attempt to find a superior path to route an incoming setup request. Our algorithm, on the other hand, tries to learn an optimal ordering of the paths through which requests can be routed according to the rank of the paths in the order learned by the algorithm. The second contribution of our work is that we have proposed a routing algorithm that has a performance superior to the important algorithms in the literature. Our conclusions are based on three important performance criteria: 1) the rejection ratio, 2) the percentage of accepted bandwidth, and 3) the average route computation time per request. Although some of the previously proposed algorithms were designed to achieve low rejection and high throughput of route requests, they are unreasonably slow. Our algorithm, on the other hand, in general attempts to reject the least number of requests, achieves the highest throughput, and computes routes in the fastest possible time when compared to the algorithms that we used as benchmarks for comparison.