Resource Optimisation for Robust IP Network Provisioning

Centre for Communication Systems Research (CCSR), University of Surrey, Guildford, UK.

The current Internet consists of a large collection of Autonomous Systems (ASes) or domains, each being a network or group of networks managed by a single authority such as an Internet Service Provider (ISP), enterprise or university. These ASes employ their own network policies and routing protocols. Due to the remarkable increase in Internet traffic because of peer-to-peer content downloading, multimedia streaming, voice over IP, online gaming, video conferencing, etc., network providers seek to optimise the network resource usage in an efficient manner utilising Traffic Engineering (TE) techniques. These techniques control traffic routing so as to optimise operational IP network performance. TE techniques can be classified into intra-AS and inter-AS. Network providers use intra-AS TE techniques to control routing the traffic within their network to achieve objectives such as load balancing and/or minimising resource consumption. On the other hand, they use inter-AS TE techniques to control inbound and outbound traffic to achieve load balancing over inter-AS resources and/or minimising peering costs.

Unfortunately, due to a variety of reasons such as malicious attacks, misconfiguration and accidental damage, various failures, and in particular link failures, occur as part of daily network operations. Recent research revealed that both single intra- and inter-AS link failure are common events and transient in nature. The potential impact of a link failure can be delay, packet discard, service disruption and severe congestion due to the shifting of an excessive amount of traffic to alternative paths that are already highly utilised. Given the short-lived nature of transient failures, network operators may not have sufficient time to re-configure their networks before the failure is restored, resulting to a detrimental failure impact. In order to manage this situation, in this thesis we propose proactive network provisioning approaches that predict the impact of transient link failures and implement remedy solutions to alleviate the detrimental failure impact. In fact, the contributions of our thesis are as follows:

Improving intra-AS primary path robustness. Routing traffic flows through high availability network segments results in minimising their path failure probability and also in reducing the amount of backup resources required to protect these primary paths. We therefore propose a heuristic algorithm with four link cost functions that take link availability into account to improve primary path availability while optimising network resources.
Making inter-AS outbound TE robust to inter-AS link failure for long and short term network provisioning. Transient inter-AS link failures are as common as intra-AS link failures and can have similar detrimental consequences. We therefore propose an IP tunneling approach that can provide fast rerouting and also a tabu search heuristic that provides primary and secondary egress points to achieve load balancing under both no failure and also single inter-AS link failure states. On the other hand, network conditions such as traffic variations and destination prefix reachability change as well. These events may make the long term outbound TE solutions inaccurate. We therefore propose a short term network provisioning framework that provides inter-AS outbound robust TE solutions considering the network dynamics.
Making both intra- and outbound inter-AS TE robust to intra- or inter-AS link failure. Due to common and transient nature of both intra- and inter-AS link failures, there are significant interactions between them. As a result, the overall network performance may not be truly robust to intra- and inter-AS link failures if they are considered separately. We therefore propose a joint robust TE approach that balances the intra- and inter-AS load balancing under intra- or inter-AS link failure taking into account their interactions.

Key words: Survivability, Robust Traffic Engineering, Intra- and Inter-AS Link Failure, Fast Recovery.

PhD Thesis, May 2008.

The full thesis in Acrobat pdf (1.43M) can be made available by contacting the author (mina.amin (at) live.co.uk).