of 93
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

IGP Traffic Engineering: A comparison of Computational Optimization Algorithms

Category:

Creative Writing

Publish on:

Views: 3 | Pages: 93

Extension: PDF | Download: 0

Share
Description
IGP Traffic Engineering: A comparison of Computational Optimization Algorithms Hong Feng Wang Thesis presented in partial fulfilment of the requirements for the degree of Master of Science at the University
Transcript
IGP Traffic Engineering: A comparison of Computational Optimization Algorithms Hong Feng Wang Thesis presented in partial fulfilment of the requirements for the degree of Master of Science at the University of Stellenbosch Supervisor: Dr. Antoine B. Bagula Co-supervisor: Prof. A. E. Krzesinski March 2008 Declaration I, the undersigned, hereby declare that the work contained in this thesis is my own original work and that I have not previously in its entirety or in part submitted it at any university for a degree. Signature:... Date:... i Abstract Traffic Engineering (TE) is intended to be used in next generation IP networks to optimize the usage of network resources by effecting QoS agreements between the traffic offered to the network and the available network resources. TE is currently performed by the IP community using three methods including (1) IGP TE using connectionless routing optimization (2) MPLS TE using connection-oriented routing optimization and (3) Hybrid TE combining IGP TE with MPLS TE. MPLS has won the battle of the core of the Internet and is making its way into metro, access and even some private networks. However, emerging provider practices are revealing the relevance of using IGP TE in hybrid TE models where IGP TE is combined with MPLS TE to optimize IP routing. This is done by either optimizing IGP routing while setting a few number of MPLS tunnels in the network or optimizing the management of MPLS tunnels to allow growth for the IGP traffic or optimizing both IGP and MPLS routing in a hybrid IGP+MPLS setting. The focus of this thesis is on IGP TE using heuristic algorithms borrowed from the computational intelligence research field. We present four classes of algorithms for Maximum Link Utilization (MLU) minimization. These include Genetic Algorithm (GA), Gene Expression Programming (GEP), Ant Colony Optimization (ACO), and Simulated Annealing (SA). We use these algorithms to compute a set of optimal link weights to achieve IGP TE in different settings where a set of test networks representing Europe, USA, Africa and China are used. Using NS simulation, we compare the performance of these algorithms on the test networks with various traffic profiles. ii Opsomming Verkeersingenieurswese (VI) is aangedui vir gebruik in volgende generasie IP netwerke vir die gebruiksoptimering van netwerkbronne deur die daarstelling van kwaliteit van diens ooreenkomste tussen die verkeersaanbod vir die netwerk en die beskikbare netwerkbronne. VI word huidiglik algemeen bewerkstellig deur drie metodes, insluitend (1) IGP VI gebruikmakend van verbindingslose roete-optimering, (2) MPLS VI gebruikmakend van verbindingsvaste roete-optimering en (3) hibriede VI wat IGP VI en MPLS VI kombineer. MPLS is die mees algemene, en word ook aangewend in metro, toegang en selfs sommige privaatnetwerke. Nuwe verskaffer-praktyke toon egter die relevansie van die gebruik van IGP VI in hibriede VI modelle, waar IGP VI gekombineer word met MPLS VI om IP roetering te optimeer. Dit word gedoen deur òf optimering van IGP roetering terwyl n paar MPLS tonnels in die netwerk gestel word, òf optimering van die bestuur van MPLS tonnels om toe te laat vir groei in die IGP verkeer òf die optimering van beide IGP en MPLS roetering in n hibriede IGP en MPLS situasie. Die fokus van hierdie tesis is op IGP VI gebruikmakend van heuristieke algoritmes wat ontleen word vanuit die berekeningsintelligensie navorsingsveld. Ons beskou vier klasse van algoritmes vir Maksimum Verbindingsgebruik (MVG) minimering. Dit sluit in genetiese algoritmes, geen-uitdrukkingsprogrammering, mierkoloniemaksimering and gesimuleerde temperoptimering. Ons gebruik hierdie algoritmes om n versameling optimale verbindingsgewigte te bereken om IGP VI te bereik in verskillende situasies, waar n versameling toetsnetwerke gebruik is wat Europa, VSA, Afrika en China verteenwoordig. Gebruikmakende van NS simulasie, vergelyk ons die werkverrigting van hierdie algoritmes op die toetsnetwerke, met verskillende verkeersprofiele. iii List of Publications A.B.Bagula and H.Wang, On the use of Genetic Algorithms to Fine-tune OSPF Routing, Southern African Telecommunication Networks Applications Conference (SATNAC), A.B.Bagula and H.Wang, On the Relevance of Using Gene Expression Programming in Destination-based Traffic Engineering, Lecture Notes in Computer Sciences, Volume 3801, Pages , December iv Contents 1 Introduction The TE problem The IGP TE Problem A hybrid routing architecture Related work Thesis Contribution and Outline Genetic Algorithms Introduction to GA Application to IGP TE Problem Chromosome Representation Initialization of Population Fitness Function Genetic Operators The local search HybridGA Algorithm v Contents vi 2.4 An illustration Comparison on the USA test network The impact of genetic operations Conclusion Gene Expression Programming Introduction to GEP Genetic operators The GEP Algorithm Application to IGP TE Problem Forming chromosome Fitness Function and Population HybridGEP Algorithm An application Comparison on the USA network The impact of genetic operations Conclusion Ant Colony Optimization Introduction to ACO Application to IGP TE Problem Mapping between real and virtual networks The link weight assignment model Contents vii Calculation of the pheromone Pheromone accumulation and evaporation Daemon action Stopping condition The link weight assignment algorithms An application Comparison using the USA network The impact of ACO operations Conclusion Simulated Annealing Algorithms Introduction to Simulated Annealing Application to IGP TE Problem The link weight assignment Algorithms An application Comparison on USA network The impact of annealing operations Conclusion Algorithm Comparison Introduction to the experiments Defining confidence intervals for the experiments Comparing the different algorithms Contents viii 6.4 The impact of parameter setting on performance Conclusion Conclusion Summary Future work Bibliography 91 List of Figures 1.1 Example of TE problem Architecture of the hybrid TE model Evolutionary loop of GA A five-link network with assigned link weights Flowchart of HybridGA Topology of the USA test network Throughput comparison among OSPF, GA, and HybridGA Evolution of the Fitness Evolution of the Maximum Link Utilization Evolution circuit in GEP Flowchart of a GEP algorithm Gene expression of link weight Gene expression of link weight Chromosome of link weights Flowchart of HybridGEP ix Contents x 3.7 Throughput comparison among OSPF, GEP, and HybridGEP Fitness evolution Link Utilization evolution Path selection The virtual network model The link weight assignment process Flowchart of ACO Flowchart of HybridACO Throughput comparison among OSPF, ACO, and HybridACO Pheromone updating MLU Comparison using 150 ants Cooling down to freeze the atoms Flowchart of SA Flowchart of HybridSA Throughput comparison among OSPF,SA,and HybridSA Comparison of Maximum Link Utilization between SA and HybridSA Comparison of the Temperature Curve between SA and HybridSA Modification to link utilization Modification to link weights Topology of the USA test network List of figures xi 6.2 Topology of the Europe test network Topology of the China test network Confidence interval of HybridGA on Europe network Confidence interval of HybridGEP on Europe network Confidence interval of HybridACO on Europe network Confidence interval of HybridSA on Europe network Comparison of cumulative means on Europe network Comparison of Maximum Link Utilization Comparison of Average Link Utilization List of Tables 2.1 Performance comparison between GA and HybridGA Performance comparison between GEP and HybridGEP Performance comparison between ACO and HybridACO Performance comparison Algorithm comparison under heavy traffic profile Impact of parameter setting xii Chapter 1 Introduction The rapid growth in Internet users and applications has increased the demand for the usage of the Internet resources such as routers, bandwidth, Web servers, etc. This has raised the need for new network management techniques allowing the network resources to match the application requirements in order to deliver the Quality of Service (QoS) demanded by modern IP applications. At the network level, the Internet is divided into routing domains also referred to as Autonomous Systems (ASes) interacting with each others to control and deliver the traffic offered by IP applications. Each of these domains fall under a single institution administration such as a company, a university or an Internet Service Provider. While inter-domain communication is achieved using the Border Gateway Protocol (BGP) [1] to exchange routing information between IP domains, intra-domain communication uses Interior Gateway Protocols (IGPs) such as Open Shortest Path First (OSPF) [2] or Intermediate Systems-Intermediate System (IS-IS) [3] to select the paths used by the traffic within an IP domain. Modern IP network operation practices for intradomain routing include the assignment of link weights in IGP protocols to route the traffic offered to a network within an IP domain and the calculation and dissemination of link state updates to the edge of an IP domain. Using the complete knowledge of the domain s topology each edge router computes the least cost paths to each destination and creates forwarding tables used to direct each IP packet to the next router on the path to its final destination. The weight values (costs) assigned to the links in OSPF are selected in the range [1, 65535] where = It is currently recognized that when using traditional destination-based routing, IGP proto- 1 Chapter 1. Introduction 2 S1 S2 S (a) non-optimal routing D1 D2 D3 S1 S2 S (b) optimal routing D1 D2 D3 Figure 1.1: Example of TE problem cols lead to unbalanced network configurations where some resources are over utilized while others remain idle. Such unwanted situations can be avoided by using traffic engineering (TE) or network engineering (NE). The objective of TE is to move traffic to where the resources are available in the network to improve routing performance (e.g. minimize link utilization, minimize propagation delay, etc.). In contrast, NE moves the network resources to where the traffic is offered to the network to achieve the same routing objective. Both of these network management techniques involve different optimization algorithms based on exact methods or heuristic methods. The focus of this thesis lies on computational algorithms used to achieve TE. 1.1 The TE problem Figure 1.1 illustrates two network configurations where three traffic flows are routed on three origin-destination pairs (i.e. S1-D1; S2-D2; S3-D3). Traditional destination-based routing will lead to the non-optimal network configuration which uses the paths on the S1-D1 pair, on the S2-D2 pair and on the S3-D3 pair as illustrated by Figure 1.1 (a). As a result the link 7 8 used by three flows may become a bottleneck for traffic engineering leading to congestion or higher loss upon failure though the network still has enough resources (bandwidth) to route the three traffic flows without overloading any link of the network. An optimized network configuration can be obtained by separating the three flows to allow each of the flows to be routed on its own path. This can be done by adjusting the weight (cost) on the links 1 7; 8 5; 10 7; and 8 14 from one to two as depicted by Figure 1.1 (b) while leaving the other link costs to 1. This reflects a situation where TE is used to improve the network performance by manipulating the link weights. Chapter 1. Introduction 3 TE is currently performed by the IP community using three methods: (1) Interior Gateway Protocol (IGP) TE using connectionless routing optimization, (2) Multiprotocol Label Switching (MPLS) TE using connection-oriented routing optimization, and (3) Hybrid TE combining IGP TE with MPLS TE. At its outset, MPLS TE raised controversies concerning how the future Internet will be engineered. On one hand, the IP engineers believing that the Internet could be engineered without the need of sophisticated network management such as provided by MPLS, proposed a single and scalable Internet where the routing of the traffic in the Internet could be optimized by optimizing only the IGP link weights. On the other hand, telecommunication operators adopted a connection oriented routing model borrowed from the ATM virtual circuit model referred to as MPLS. While MPLS has won the battle of the core of the Internet and is making its way into metro, access and even some private networks, emerging Internet service provider operation practices are revealing the relevance of using IGP TE in hybrid TE models where IGP TE is combined with MPLS TE to optimize IP networks. This is done by either optimizing IGP routing using the link weight optimization paradigm while setting a few number of MPLS tunnels in the network as proposed by [4] or by optimizing the management of MPLS tunnels to allow growth for the IGP traffic as proposed in [5]. A third option consists of optimizing both IGP and MPLS routing in a hybrid IGP+MPLS setting. The focus of our work lies on IGP TE using heuristic algorithms borrowed from the computational optimization research field. 1.2 The IGP TE Problem Given a directed acyclic graph G(N, L) where N is the set of nodes representing the routers of the network while L is the set of arcs representing the capacitated network links between the routers. Let D = (r i,e ) denote a demand matrix where r i,e = (i, e, d i,e ) is a triple expressing a request to route d i,e units of data traffic between the source i and the destination e. Problem 1: Routing optimization problem The routing problem consists of finding a set of paths to route the demand D in order to minimize a measure of congestion defined by the objective function Ω given by: Ω = max l L (µ l) (1.1) Chapter 1. Introduction 4 where µ l = f l C l is the utilization of link l, f l is the total traffic carried by link l and C l is the capacity of link l. Note that as defined above The routing problem above is an optimization problem consisting of minimizing the maximum link utilization. The demand matrix D can be estimated using future demands based for example on concrete measures of flow between source-destination pairs as proposed in [6, 7] for the AT&T Worldnet backbone or predicted from a concrete set of consumer subscriptions to virtual leased lines as suggested by [8]. Problem 2: Link weights setting problem Given the network model defined above and a demand matrix D expressing as above the demand in traffic flow between origin-destination pairs, the routing optimization problem Problem 1 can be redefined as a link weight setting problem consisting of determining a set of weights W={w l }, where each weight w l [1, Maxwt] such that the objective function Ω is minimized A hybrid routing architecture Offline Routing Link Weights Weight Estimation Network States Online Routing Path Dijkstra Selection IP forwarding Packet Forwarding Congestion Control Failure Detection Network Monitoring Figure 1.2: Architecture of the hybrid TE model The IGP TE problem above has been solved using methods borrowed from computational and non-computational intelligence and its solution can be implemented using a hybrid Chapter 1. Introduction 5 offline/online routing architecture using offline link weight calculation and online routing by performing path selection and packet forwarding to achieve optimized IGP routing. The architecture depicted by Figure 1.2 reveals a two-layer model where the offline weight calculation is separated from the online packet forwarding. The upper layer of the architecture implements two functions: (1) collecting current network state (e.g, network topology, traffic demands, propagation delays; etc.) and (2) calculating the link weights based on the network state. The lower layer implements three functions: (1) path selection using Dijkstra s algorithm with link costs set to the link weight values (2) populating forwarding tables to use the selected paths and (3) network monitoring through congestion control and failure detection. Note that these functions are defined by the closed loop of our proposed routing architecture where (1) the path selection in the bottom layer is performed based on the weights computed by the weight selection in the upper level (2) the packet forwarding in the lower layer is defined by the paths selected during path selection and (3) the weight estimation in the upper layer is triggered by the network monitoring engine in the lower layer when new link weights need to be calculated. As proposed in [2], the guideline on how to best design OSPF networks is to use at most 200 routers in a single area/domain. As suggested by CISCO in [9], no more than six router hops from source to destination and 30 to 100 routers should be used per area/domain, but less than 40 routers is recommended to achieve OSPF routing scalability. 1.3 Related work It was proved in [10] that finding not only the optimal OSPF weight setting but even an approximate solution to the problem was NP-hard. A piece-wise linear and convex function Ω is defined and used in [10] as a congestion measure for the weight setting problem in OSPF routing. This problem is solved using a local search heuristic. Using a single descent and working with small networks of at most 16 nodes and 18 links, a local search procedure similar to [10] is presented in [11] while the work presented in [12] use local search with a single descent in a model which deals simultaneously with the network design problem on small networks with at most 13 links. A completely different approach Chapter 1. Introduction 6 using Lagrangian relaxation is presented in [13] to solve the weight setting problem on networks of up to 26 nodes. The work presented in [14] deals with search heuristics for load balancing in IP networks. This work studies three different heuristics proposed in [10] and [11] and evaluate their performance using topologies with power-law properties. The evaluation results revealed that the heuristic proposed by [10] performs better than the other and achieves results which are reasonable close to the optimum but at the price of high processing time. A solution to the OSPF weight setting problem is proposed in [15]. The paper formulates a relevant OSPF routing optimization problem, proves its NP-completeness, and discusses possible heuristic approaches and related optimization methods for solving it. These heuristics include simulated annealing and genetic algorithms. Two basic approaches to the OSPF weight setting problem are considered in the paper and the resulting optimization algorithms presented: a direct and a two-phase approach. Heuristic solutions using analogies with natural and social systems have been proposed to optimize IGP routing [8, 16, 17, 18, 19]. Building upon the congestion measure in [10], [8, 18, 19] solve the weight setting problem in the OSPF routing using a genetic algorithm in [8] and a hybrid genetic algorithm [18, 19]. In [18, 19], a hybrid genetic algorithm is proposed with a local improvement procedure for the OSPF weight-setting problem. The local improvement procedure makes use of an efficient dynamic shortest path algorithm to recompute shortest paths after the modification of link weights. Using a set of real and synthetic test problems, the model showed near-optimal solutions. In [16], the OSPF weight setting problem is solved by using a local search to complement the global search implemented by classical genetic algorithms to improve the genetic individuals fitness through hill-climbing and speeding up the genetic search. The local search is used to map the link weights to the offered load by diverting traffic from the link with the highest utilization. A newly developed evolutionary computation method was proposed in [20] under th
Similar documents
View more...
Search Related
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks