Technical Report PHD-2007-17

Title: Traffic Engineering in IP and MPLS Networks
Authors: Gabi Nakibly
Supervisors: Reuven Cohen
Abstract: Traffic engineering is a set of actions whose goal is to evaluate and optimize the performance of operational networks. The performance of an operational network is enhanced by addressing traffic-oriented performance measures, such as delay, delay variation, packet loss, and throughput, while utilizing network resources economically and reliably. One of the most important traffic engineering actions is the control of the routing function in the network so that traffic can be steered through it as effectively as possible. This thesis contains three parts. The first two parts address traffic engineering in IP networks and the third addresses traffic engineering in MPLS networks. In the first part we study the computational complexity and effectiveness of a concept we term ``N-hub Shortest-Path Routing'' in IP networks. N-hub Shortest-Path Routing allows the ingress node of a routing domain to determine up to N intermediate nodes (``hubs'') through which a packet will pass before reaching its final destination. This facilitates better utilization of the network resources, while allowing the network routers to continue to employ the simple and well-known shortest-path routing paradigm. Although this concept has been proposed in the past, this thesis is the first to investigate it in depth. We apply N-hub Shortest-Path Routing to the problem of minimizing the maximum load in the network. We show that the resulting routing problem is NP-complete and hard to approximate. However, we propose efficient algorithms for solving it both in the online and the offline contexts. Our results show that N-hub Shortest-Path Routing can increase network utilization significantly even for $N=1$. Hence, this routing paradigm should be considered as a powerful mechanism for future datagram routing in the Internet. In the second part, we consider the application of ``N-hub Shortest-Path Routing'' to network services traffic. Network services are provided by means of dedicated service gateways, through which traffic flows are directed. Existing work on service gateway placement has been primarily focused on minimizing the length of the routes through these gateways. Only limited attention has been paid to the effect these routes have on overall network performance. We propose a novel approach for the service placement problem, which takes into account traffic engineering considerations. Rather than trying to minimize the length of the traffic flow detours, we take advantage of them in order to enhance the overall network performance. We divide the problem into two sub-problems: finding the best location for each service gateway, and selecting the best service gateway for each flow. We propose efficient algorithms for both problems and study their performance. Our main contribution is showing that placement and selection of network services can be used as effective tools for traffic engineering. In the third part, we consider the MPLS recovery mechanisms. These mechanisms are increasing in popularity because they can guarantee fast restoration and high QoS assurance. Their main advantage is that their backup paths are established in advance, before a failure event takes place. Most research on the establishment of primary and backup paths has focused on minimizing the added capacity required by the backup paths in the network. However, this so-called Spare Capacity Allocation (SCA) metric is less practical for network operators who have a fixed capacitated network and want to maximize their revenues. In this thesis we present a comprehensive study on restorable throughput maximization in MPLS networks. We present the first polynomial-time algorithms for the splittable version of the problem. For the unsplittable version, we provide a lower bound for the approximation ratio and propose an approximation algorithm with an almost identical bound. We present efficient heuristics which are shown to have excellent performance. One of our most important conclusions is that when one seeks to maximize revenue, local recovery should be the recovery scheme of choice.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2007
To the main CS technical reports page

Computer science department, Technion