Intra-domain Traffic Engineering Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Outline ● ● ● Introduction to Internet Traffic Engineering IP-based Traffic Engineering MPLS-based Traffic Engineering Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Do IP networks manage themselves? ● In some sense, yes: – – ● But, does the network run efficiently? – – ● Congested link when idle paths exist? High-delay path when a low-delay path exists? How should routing adapt to the traffic? – – ● TCP senders send less traffic during congestion Routing protocols adapt to topology changes Avoiding congested links in the network Satisfying application requirements (e.g., delay) … essential questions of Traffic Engineering Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Traffic Engineering ● What is Traffic Engineering? – Control and optimization of routing, to steer traffic through the network in the most effective way “Internet traffic engineering is defined as that aspect of Internet network engineering dealing with the issue of performance evaluation and performance optimization of operational IP networks. Traffic Engineering encompasses the application of technology and scientific principles to the measurement, characterization, modeling, and control of Internet traffic” RFC 3272 – Overview and Principles of Internet TE Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Traffic Engineering ● Two fundamental approaches: – IP-based Traffic Engineering – MPLS-based Traffic Engineering Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group IP-based Traffic Engineering ● Using traditional routing protocols: – – – – Routers flood information to learn topology Routers determine “next hop” to reach other routers Path selection based on link weights (shortest path) Link weights configured by network operator 2 3 2 1 1 1 3 5 4 3 Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Approaches for setting the link weights ● Conventional static heuristic – Proportional to physical distance • Cross-country links have higher weights • Minimizes end-to-end propagation delay – Inversely proportional to link capacity • Smaller weights for higher-bandwidth links • Attracts more traffic to links with more capacity ● Can we do better? Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Approaches for setting the link weights ● A traffic engineered approach – Collect measurements of traffic and topology – Tune the weights based on the offered traffic – Network management system sets the link weights – Acting on network-wide view of traffic and topology – Directly minimizes metrics like max link utilization Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group TE approach: Measure, Model and Control Network-wide “what if” model Offered Topology/ traffic Configuration measure Changes to the network control Operational network Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group IP-based Traffic Engineering ● Topology – ● Traffic matrix – ● Configurable parameters for routing protocol Performance objective – ● Offered load between points in the network Link weights – ● Connectivity and capacity of routers and links Balanced load, low latency, … Question: Given the topology and the traffic matrix, which link weights should be used? Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group IP-based Traffic Engineering ● Instrumentation – – ● Network-wide models – – ● Topology: monitoring of the routing protocols Traffic matrix: fine-grained traffic measurement Representations of topology and traffic “What-if” models of shortest-path routing Network optimization – – Efficient algorithms to find good configurations Operational experience to identify key constraints Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Topology/Routing ● Router configuration files – – – – ● Daily snapshot of network assets & configuration Software to parse the router config commands Network-wide view of topology & routing policies Also useful for detecting configuration mistakes Routing monitors – – – – – Online monitoring of routing protocol messages Real-time view of routes via neighboring ASes Real-time view of paths within the AS Software for aggregating and querying the data Also useful for detecting and diagnosing anomalies Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Formalizing the Optimization Problem ● Input: graph G(R,L) – – – ● Input: traffic matrix – ● R is the set of routers L is the set of unidirectional links cl is the capacity of link l Mi,j is traffic load from router i to j Output: setting of the link weights – – wl is weight on unidirectional link l Pi,j,l is fraction of traffic from i to j traversing link l Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Formalizing the Optimization Problem ● A solution to the optimization problem cannot freely allocate the traffic load between two routers – – ● The traffic between two routers can only flow along a shortest weighted path (routing protocols work this way) This constraint implies that we achieve a sub-optimal solution to the general routing problem In case multiple shortest weighted paths exist, traffic can be split among them – In practice, this is allowed by OSPF by means of the ECMP (Equal Cost Multi-Path) function Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Formalizing the Optimization Problem ● To enforce the optimal solution, it is necessary to split traffic along multiple shortest paths Values of Pi,j,l 0.25 0.25 0.5 1.0 0.25 0.5 1.0 0.25 0.5 0.5 Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Complexity of the Optimization Problem ● NP-complete optimization problem – – ● No efficient algorithm to find the link weights Even for simple objective functions What are the implications? – Have to resort to searching through weight settings Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Optimization based on local search ● Start with an initial setting of the link weights – – – ● Compute the objective function – – – ● E.g., same integer weight on every link E.g., weights inversely proportional to capacity E.g., existing weights in the operational network Compute the all-pairs shortest paths to get Pi,j,l Apply the traffic matrix Mi,j to get link loads ul Evaluate the objective function from the ul/cl Generate a new setting of the link weights repeat Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Making the search efficient ● Avoid repeating the same weight setting – – – ● Avoid computing shortest paths from scratch – – ● Explore settings that changes just one weight Apply fast incremental shortest-path algorithms Limit number of unique values of link weights – ● Keep track of past values of the weight setting … or keep a small signature of past values Do not evaluate setting if signatures match Do not explore 216 possible values for each weight Stop early, before exploring all settings Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Application to AT&T's backbone network ● Performance of the optimized weights – – – Search finds a good solution within a few minutes Much better than link capacity or physical distance Competitive with multi-commodity flow solution ● ● Optimal routing possible with more flexible routing protocols (e.g. MPLS) How AT&T changes the link weights – – – – Maintenance every night from midnight to 6am Predict effects of removing link(s) from network Reoptimize the link weights to avoid congestion Configure new weights before disabling equipment Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group To learn more... ● Overview papers – ● Traffic measurement – – ● R. Caceres, N. Duffield, A. Feldmann, et al., “Measurement and analysis of IP network usage and behavior”, IEEE Communications Magazine, May 2000 A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, F. True, “Deriving traffic demands for operational IP networks: Methodology and experience”, IEEE/ACM Transactions on Networking, June 2001 Topology and configuration – ● B. Fortz, J. Rexford, M. Thorup, “Traffic engineering with traditional IP routing protocols”, IEEE Communication Magazine, October 2002 A. Feldmann, J. Rexford, “IP network configuration for intradomain traffic engineering”, IEEE Network Magazine, September/October 2001 Intradomain route optimization – B. Fortz, M. Thorup, “Internet traffic engineering by optimizing OSPF weights”, Proc. Of IEEE INFOCOM 2000 Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Traffic Engineering ● Two fundamental approaches: – IP-based Traffic Engineering – MPLS-based Traffic Engineering Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Multi-Protocol Label Switching ● Multi-Protocol – Encapsulate a data packet ● – Put an MPLS header in front of the packet ● ● Could be IP, or some other protocol (e.g., IPX) Actually, can even build a stack of labels… Label Switching – – MPLS header includes a label Label switching between MPLS-capable routers IP packet MPLS header Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Forwarding Equivalence Class (FEC) ● Rule for grouping packets – – ● Packets that should be treated the same way Identified just once, at the edge of the network Example FECs – Destination prefix ● ● – Src/dest address, src/dest port, and protocol ● ● – Longest-prefix match in forwarding table at entry point Useful for conventional destination-based forwarding Five-tuple match at entry point Useful for fine-grain control over the traffic Sent by a particular customer site ● ● Incoming interface at entry point Useful for virtual private networks Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group LSP (Label Switched Path) Setup ● Protocols used to automatically establish LSPs: – – LDP (Label Distribution Protocol – RFC 3036) RSVP (with the objects needed to request/map labels) ● – – Exploit IP routing tables information to establish paths and bind FECs to LSPs CR-LDP (Constraint-based Routing LDP – RFC 3212) RSVP-TE (TE extension to RSVP – RFC 3209) ● Support establishment of explicit paths Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Explicit routing ● ● ● LSPs can be established along paths other than the shortest path More flexibility than destination-based IP routing In an MPLS network, it is (in theory) possible to implement the optimal solution to the general routing problem (multi-commodity flow problem) Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group TE with constraint-based routing ● Explicit routing + fine-grained FEC definition – ● ● Allows to select a suitable path for each flow We can select a path that meets the QoS requirements of the flow Knowledge of network resource usage is required – Extend OSPF to disseminate the extra information (OSPF-TE – RFC 3630) ● ● Maximum bandwidth, maximum reservable bandwidth, unreserved bandwidth, TE metric, etc. The MPLS ingress LSR (Label Switching Router) computes the constraint-based path and establishes the corresponding explicit LSP Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group TE with constraint-based routing ● Given the network topology and the flow requirements, how to select a path? – – ● A feasible path is such that R(l)>B on all the links – ● We assume that flow requirements are expressed in terms of requested bandwidth B between a source s and a destination d The residual bandwidth on each link is R(l) If we prune all the links such that R(l)<B, all the paths between s and d in the pruned topology are feasible What feasible path can we choose? – The goal is to optimize resource usage Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Widest Shortest Path (WSP) ● ● WSP selects the path with the minimum hop count among all feasible paths In case several such path exist, the one the maximal residual bandwidth is selected – ● The residual bandwidth of a path is the minimum among the residual bandwidths of its links R. Guerin, D. Williams, and A. Orda, “QoS routing mechanisms and OSPF extensions,” in Proc. IEEE Globecom, 1997 Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Other TE algorithms ● Most of TE algorithms – – – ● ● prune links with insufficient bandwidth assign a cost to each link in the pruned topology select the least cost path Different techniques to assign costs The cost may be an increasing function of link load – – Slightly loaded links are preferred Heavily loaded links are discouraged Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Minimum Interference Routing (MIRA) ● Given the knowledge of ingress-egress pairs, MIRA selects the path which minimizes the interference – ● ● The minimum interference path between a particular ingress-egress pair is the path which maximizes the minimum maxflow between all other ingress-egress pairs This problem is NP-hard – ● Interference on an ingress-egress pair (s,d) due to routing a flow between some other ingress-egress pair is defined as the decrease in the maximum network flow between s and d Set link weights proportional to maxflow reduction K. Kar, M. Kodialam, and T. Lakshman, “Minimum Interference Routing of Bandwidth Guaranteed Tunnels with MPLS Traffic Engineering Applications,” IEEE Journal on Selected Areas in Communications, vol. 18, no. 12, pp. 25662579, December 2000. Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group Simple Minimum Interference Routing (SMIRA) ● The interference on an ingress-egress pair is evaluated by means of a k-shortest-path-like computation instead of a maxflow computation – – – – ● ● The set of k paths is determined by first computing the widestshortest path between s and d Then, all the links along this path with a residual bandwidth equal to the bottleneck bandwidth of the path are pruned The second path is the widest-shortest path in the pruned topology This procedure is repeated until either k paths are found or no more paths are available The cost of links belonging to the set of k paths is increased proportionally to the weight of the path and the ratio of bottleneck bandwidth to residual bandwidth. I. Iliadis and D. Bauer, “A New Class of Online Minimum-Interference Routing Algorithms,” Networking 2002, LNCS 2345, pp. 959-971, 2002. Computer Science Department (Dipartimento di Informatica e Sistemistica - DIS), University of Napoli Federico II – Comics Group