Redes ip

A Hybrid Genetic Algorithm for Routing Optimization in IP Networks Utilizing Bandwidth and Delay Metrics
Anton Riedl
Institute of Communication Networks, Munich University of Technology Munich, Germany E-mail: Anton.Riedl@ei.tum.de
Abstract – In this paper we study routing optimization in the context of IP traffic engineering, which relies on conventional, destination-based routing protocols.We introduce the different concepts of routing optimization and discuss their implications for traffic engineering. The specific focus is on routing technologies that utilize multiple metric types – in our case delay and bandwidth metrics – in order to derive the shortest paths towards every destination in the network. A novel hybrid genetic algorithm is presented, which allows the computation ofan optimized set of link metrics, considering single as well as dualmetric protocols. Finally, the benefits of two metric types for traffic engineering are demonstrated. Keywords – IP Traffic engineering, genetic algorithm, bandwidth-delay sensitive routing, destination-based routing, OSPF, EIGRP

a consequence, it is possible to optimize routing by setting the metric values appropriately. Wespecifically focus on routing protocols, which take into account two types of link metrics – one for delay and one for bandwidth. However, in the context of routing optimization the two metrics do not really have any physically relevant meaning. Instead, they are used purely as generic means for the sake of traffic engineering. The remainder of the paper is organized as follows: In section IIexisting routing concepts are presented and their implications for routing optimization are discussed. We show how shortest paths are determined when delay and bandwidth metrics are considered and illustrate the advantage of dualmetric protocols over their single-metric counterparts. In section III a hybrid genetic algorithm for the computation of optimized routing schemes is introduced. Computationresults and performance issues are presented in section IV. Section V concludes the paper. II. ROUTING OPTIMIZATION CONCEPTS IN IP NETWORKS A. Destination-Based vs. Source/Flow-Based Routing Two fundamentally different routing concepts exist, which strongly influence the optimization procedure and the achievable results: destination-based routing and source- or flow-based routing. Conventionalrouting protocols such as OSPF [1], EIGRP [2], or IS-IS [3], follow the next-hop destination-based routing paradigm. Within each router the forwarding decision for an IP packet is based solely on the destination address specified in the packet header. No information about the origin or any other context of the packet is taken into account. As a consequence, this routing procedure is simple and quiteefficient. However, it imposes limitations on routing optimization, as illustrated in Figure 1.
Flow 1

I. INTRODUCTION Routing optimization is an important method of Internet traffic engineering, which is applied on a medium-term time basis (at least some hours) and to a rather coarse level of flow granularity (e.g., aggregation of all traffic flows between specific ingress/egress nodes). Incases where increasing traffic loads or temporary traffic variations cause localized link congestions, routing optimization can be carried out to resolve – or at least alleviate – potential network performance problems. The idea is to adjust routing to current load situations and, thus, better utilize available network resources, leading to improved Quality of Service (QoS). The routing optimizationproblem can be formulated as follows: Given a dimensioned network and a traffic demand matrix, we would like to find a routing solution, which optimizes a certain network QoS measure. As QoS measure several expressions are conceivable. Most definitions found in the literature are based on link utilization values, as these correlate with packet delay and packet loss within routers. A common...