Centre for Communication Systems Research (CCSR), University of Surrey, Guildford, UK.
The Internet is a collection of more than 20,000 Autonomous Systems (ASes), each being an administrative region that employs its own network policies and protocols. Much of Internet traffic traverses multiple ASes before reaching its destination. With the emergence of multimedia applications, Internet Service Providers (ISPs) are carrying increasing amount of outbound traffic that flows through and out of their networks. In order to prevent network overloading and maintain satisfactory performance for their customer traffic, ISPs are seeking for effective network management approaches to optimize their network resource utilization. A common approach currently employed by ISPs is to strategically control the routing of traffic in their networks.
Traffic Engineering (TE) is the set of techniques to predict and engineer the traffic routing behavior so as to optimize IP network performances. It can be classified into intra- and inter-AS. In intra-AS TE, the operator of an AS controls traffic routing only within the network with general objectives of improving load balancing and/or minimizing bandwidth consumption in intra-AS links. Inter-AS TE aims to control traffic entering and exiting the AS. Unlike intra-AS TE, the typical objectives of inter-AS TE is to improve load balancing over inter-AS links and/or to minimize peering costs with adjacent ASes. In this thesis, we investigate how to effectively apply both intra- and inter-AS TE to network dimensioning, which is responsible for assigning physical network resources to the forecasted traffic and provides network provisioning directives in order to accommodate it. The objective of this thesis is to achieve the following network dimensioning goals through TE:
Maximizing the network ability to accommodate more future traffic demands: many novel optimization problem formulations and algorithms have been proposed in the literature for intra- and inter-AS TE separately. However, there exists an interaction effect between them which, if taken into consideration, allows the overall network performance to be further optimized. To achieve this, we propose a joint optimization approach to combine intra- and inter-AS TE with an efficient algorithm. The joint optimization approach significantly outperforms, in terms of bandwidth utilization and consumption, the approaches that consider intra- and inter-AS TE separately. This allows ISPs to accommodate significantly more future traffic demands in their networks.
Enhancing the robustness of network dimensioning solutions against traffic demand uncertainty: network dimensioning should not only focus on performance but also on robustness. The traffic matrix, which specifies the traffic demand between each pair of nodes in the network, is an essential input to TE. In theory, predictable TE performance can only be achieved if this traffic matrix is accurate. However, due to dynamic network conditions and lack of perfect traffic measurement infrastructure, traffic demands are likely derived with uncertainty. As a result, any deviation from the traffic matrix stipulated values could lead to unpredictable TE performance. To obtain robust solutions, we perform TE optimization across multiple possible traffic matrices as a means to model traffic demand uncertainty. We propose a scenario-based robust optimization approach for TE to achieve good performance under any of these traffic matrices. This enhances the robustness of network dimensioning solutions against traffic demand uncertainty.
Achieving low-cost and resource-efficient end-to-end bandwidth guarantees provisioning: the current best-effort Internet does not provide Quality of Service (QoS) guarantees for the emerging multimedia applications. End-to-end bandwidth guarantee across ASes is vital in order to achieve the required QoS. In order for ISPs to provision this guarantee efficiently, two issues have to be considered. The first one is an economic issue that determines the minimum bandwidth to be purchased from downstream ASes towards destinations with as low cost as possible. Having access to both the purchased bandwidth from the downstream ASes and the AS-owned bandwidth in the network, the second issue is to assign end-to-end routes to customer traffic with bandwidth guarantees while optimizing network resource utilization. We propose a network dimensioning system that consists of novel problem formulations and efficient algorithms for the above two issues and achieve their objectives.
Key words: Traffic Engineering, Quality of Service, Robustness
PhD Thesis, December 2006.
The full thesis in Acrobat pdf (1.2M) can be made available by contacting the author (royhokh (at) googlemail.com).