Efficient QoS routing in MPLS networks

Abstract

To enhance the QoS capability of IP networks, Multi-Protocol Label Switching (MPLS) has been developed to provide QoS guaranteed services. Recently many different QoS routing protocols for establishing traffic engineering paths in MPLS networks (IP networks with MPLS) have been proposed and they can be grouped into two categories: the distributed and centralized approach. In the distributed approach, a source determines the routing path from itself to its destination and all routing information is updated by flooding; while in the centralized approach, the routing decision is made by the central manager. To search for the optimal routing path, most of the existing routing protocols use the Widest Shortest Path (WSP), which is the shortest path searching with the consideration of hop count and route bandwidth. However, the WSP has high path searching complexity and requires a large dynamic routing table. To address these drawbacks, we develop a new path selection algorithm called the Largest Widest Shortest Path with Limited Choices (LWSP-LC) for QoS routing protocols in MPLS networks. The LWSP-LC comes from the WSP but with two important modifications. First, the number of possible choices to select the optimal path is significantly reduced. Second, an additional parameter, which is the available bandwidth, is considered in the path selection. The LWSP-LC can be implemented in both distributed and centralized approach, and we call the routing protocols as Efficient Distributed QoS Routing (EDQR) and Efficient Centralized QoS Routing (ECQR) respectively. To compare the performance of EDQR and ECQR with other existing QoS routing protocols, we develop a simulation model with three different networks including a real network and two traffic scenarios. Our simulation results show that, under different situations, our algorithms always have a lower path searching complexity and smaller communication overhead but without significant performance degradation. We find that the difference of the path searching complexity and the communication overhead can be up to 251 and 46 times respectively. Moreover, our algorithms do not require any additional hardware or processing power but the contribution is still significant. We also investigate the effect of the number of possible choices on the performance of our routing protocol and simulation results shows that a very limited number of choices is good enough to maintain a reasonable routing performance in terms of the connection blocking probability. We also develop a general rule to compute the upper bound of the minimum number of possible choices for our algorithm based on the network size. In this way, we can easily set the number of choices for our algorithm as the upper bound of the minimum number of possible choices by using the general rule.

Date of Award	2 Oct 2003
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chi Chung CHEUNG (Supervisor)