Network Working Group Yufei Wang (Photuris) Internet Draft Leah Zhang (Photuris) Expiration Date: December 2001 June 2001 A Scalable and Hybrid IP Network Traffic Engineering Approach draft-wang-te-hybrid-approach-00.txt Status of this memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract Currently a common approach to IP network traffic engineering is the overlay approach where explicit end to end MPLS LSPs between all possible edge nodes are established to form a full mesh virtual network on top of the physical topology. By carefully choosing the routes for these LSPs, one can completely control how traffic flows across the network and therefore achieve any given traffic engineering objective. However scalability is a serious concern with this approach because it requires N square number of LSPs where N is the number of nodes. WAng, Y. & Zhang, L. [Page 1] Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001 A recent research [1] proposes a scalable traffic engineering method by optimizing the IGP link weights and shows that theoretically the native shortest path routing (OSPF or IS-IS) under appropriate link weight setting matches the performance of the overlay approach exactly. But this theoretical result faces two major practical problems. One is that it only applies to static traffic engineering as link weights cannot be changed too often due to IGP slow convergence. The other is that it may need to split traffic across multiple equal cost shortest paths if any, in unequal proportions and currently OSPF only supports equal splitting. We are proposing a new approach called the hybrid approach which relies on both IGP link weight setting and MPLS LSPs. The hybrid approach retains the scalability of the link weight method and at the same time eliminates the two practical problems of it. The basic idea of this new approach is to rely on IP native routing (OSPF, IS-IS) for most part of the network and to use MPLS LSPs for load balancing at some locations only when necessary. The new approach achieves the exact performance of the overlay approach without the associated complexity. Introduction Traffic engineering is concerned with the problem of how to optimally map traffic flows onto the network topology so that network resources are best utilized and network congestions are minimized or completely eliminated [2]. If the traffic matrix (end to end bandwidth requirement, each individual requirement is called a demand) and network bandwidth are given, the traffic engineering problem can be modeled as a mathematical problem called multi-commodity network flows [3] which can then be solved easily by some very efficient algorithms such as the simplex method [4]. The solution of this mathematical model provides the optimal set of end to end routes, one for each demand. Therefore how to determine the optimal routes is not a problem at all. But how to implement these routes in real world IP networks is the concern. This draft addresses precisely this concern. WAng, Y. & Zhang, L. [Page 2] Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001 One straightforward implementation is to set up an explicit LSP for each of these routes so that each demand will follow its respective optimal routing exactly. This is the overlay approach. The concern with this approach is that it does not scale because it requires N square number of LSPs where N is the number of nodes. And even worse, N square may not be enough because sometimes a demand needs to be split between multiple routes. In other words, it is possible that the optimal routing provides multiple optimal paths between a pair of end nodes and the traffic between them needs to be split across these paths according to the optimal proportions (which are also determined by the solution of the mathematical model). In such cases multiple LSPs should be set up between these two nodes for load splitting. It should be pointed out that although from network topology point of view there may be many alternative paths connecting two end nodes, not all of them need to necessarily be chosen as optimal paths for traffic engineering purpose. Normally the possibilities of traffic splitting between multiple optimal paths may be far less than those suggested by topological connectivity. The overlay approach seems to be the only viable approach even with its scalability concern until very recently when a research paper [1] observes that the optimal routes are always the shortest paths with respect to an appropriate set of positive link weights and proposes a new approach which relies on the IP native shortest path routing (OSPF, IS-IS). The new approach controls how traffic moves cross the network by making the desirable routes the shortest paths through optimal link weight setting. The paper also observes that the optimal link weights are actually provided by the optimal solution of the mathematical model as a by-product. This theoretical result may provide us some valuable insight into the traffic engineering capabilities of shortest path routing. However the proposed IGP link weight setting method does have its practical limitations. One major issue is that it only applies to static traffic engineering as link weights cannot be changed too often to respond to traffic pattern changes in real time due to IGP slow convergence. Another issue is that it may need to split traffic WAng, Y. & Zhang, L. [Page 3] Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001 across multiple equal cost shortest paths if any, in unequal proportions, while current IGP protocols only support equal splitting. Regarding the first issue, one may argue that the link weight method can be used for long-term statistical traffic engineering where traffic volumes are measured as statistical averages and that this method is not designed for handling traffic fluctuations in real time. But the second issue indeed limits the possibility that this method can be implemented in real networks today because IGP protocols do not support arbitrary load splitting. It is possible that we implement the link weight method by only doing equal load splitting even though the optimal routing requires unequal distributions. But another research [5] shows that the performance of equal splitting only traffic engineering can deviate from that of the optimal solution significantly, at least for some worst cases. It is interesting to notice that traffic splitting across multiple optimal paths between two nodes for the overlay approach and traffic splitting across multiple equal cost shortest paths between the same node pair for the link weight approach are identical. The multiple optimal paths in the overlay approach are precisely turned into multiple equal cost shortest paths by properly setting the link weights in the link weight approach. So no matter which implementation approach we take, we all implement the optimal traffic engineering routing and we all face the unequal traffic splitting problem. In todayÆs technology, unequal splitting among multiple MPLS LSPs is readily supported [6,7]. When setting up each LSP, one can specify its (virtual) bandwidth, and traffic can be split across multiple LSPs in proportion to their bandwidth ratios. This capability of LSPs motivates us to propose a new approach called the hybrid approach which relies on both IGP link weights and MPLS LSPs. The hybrid approach retains the advantages of IGP link weights method while eliminates its shortcomings. To avoid ambiguity, throughout this paper, all traffic (demands), links, and LSPs are assumed unidirectional, even though we do not explicit mentioning directionality. In the illustrated examples, the direction is always assumed to go from left to right. We use the term optimal routing to refer to the optimal solution of WAng, Y. & Zhang, L. [Page 4] Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001 the mathematical traffic enginerring model. But the term optimal routing can also refer to any desirable set of routes designed by a carrier which may not be necessarily mathematical optimal but are prefered to be implemented for some practical reasons. This draft is about a new approach to the implementation of such routing scheme. Whether the routing is realy optimal or not does not make any difference to our approach because research [1] shows that even a non-optimal set of routes can also be reproduced as shortest paths as long as they are not loopy. The Hybrid Approach In this approach we rely on optimal IGP shortest path routing to route most of traffic and only use LSPs to do the necessary traffic splitting. We would like to make the following observations. First, not every demand needs to be split for optimal routing. Second, even a demand indeed needs to be split, the section of the split routing (which is called load balance section from now on) does not necessarily span the entire path from the source node to the destination node. Third, many different demands may share the same load balance section. As an example, the third observation of common load balance section is illustrated in figure 1, where many demands (A to I, A to J, B to I, C to H, etc.) share the common load balance section that goes between D and G. A E I \ /,,\ / \ /, ,\ / \ /, LSP1 ,\ / C ---- D : : G ----- H / \` LSP2 ` / \ / \` ` / \ / \` / \ B F J Figure 1 WAng, Y. & Zhang, L. [Page 5] Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001 In order to reduce number of LSPs required, we donÆt set up an LSP for every demand that requires splitting. We aggregate splitting. That is, different demands which share the same load balance section are aggregated and LSPs are set up only between the two end points of the load balance section where traffic flows actually start to diverge to difference paths and where they converge back to one path, not between the source node and the destination node of each individual demand. As illustrated in figure 1, only two LSPs need to be setup for the common load balance section between D and G, LSP1 and LSP2. LSP1 goes from D via E to G and LSP2 goes from D via F to G. All demands which share this load balance section D-G (e.g. demands A to I, A to J, B to I, C to H, etc.) are aggregated between D and G and are load balanced uniformly by these two LSPs. So the basic idea of the hybrid approach is to set up LSPs for all load balance sections for traffic splitting. These LSPs are viewed as virtual links (express paths) between the head end and the tail end of a load balance section. They are advertised into IGP as forwarding adjacencies (FA) [8] between the head end and the tail end. The LSPs are assigned weights that are the sum of the weights of the links on their paths. So the LSPs are also on the shortest path routing and carry the same total weight as their respective original paths. The routers can be configured [8] such that the LSPs (FAs) are preferred over the original links. In addition, these LSPs are assigned bandwidths that represent the proportions of the optimal traffic splitting and traffic is split across LSPs according to their bandwidths [6,7]. Therefore traffic will be split at the load balance section across multiple LSPs in proportion to the bandwidth ratios of these LSPs which will be then identical to the optimal traffic split ratios. The number of LSPs required by this approach normally should be far less than the overlay approach because of the following reasons. First, the percentage of demands that need splitting for optimal routing is usually very small. As discussed previously, even though the topological WAng, Y. & Zhang, L. [Page 6] Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001 connectivity may offer many alternative paths between a source node and a destination node, only one or very few of them may be selected as optimal paths. Second, the ôsplitting aggregationö further reduces the LSP needs to per load balance segment from per individual demands. We use the example in figure 1 to demonstrate how scalable this hybrid approach is. In figure 1, all the demands that go from node set {A,B,C,D} to node set {G,H,I,J} need to traverse the load balance section D-G. There are a total of 16 such demands (A-G, A-H, A-I, A-J, B-G, B-H, B-I, B-J, etc.). If all of them need to be split between D and G, the overlay approach will need to set up a total of 32 end to end LSPs, two for each demand. Even if some of the demands only take one of the two paths between D-G without load balancing, we still need a minimum of 16 LSPs. But in the hybrid approach we only need 2 LSPs. And the performances of the two approaches are identical. Both follow the optimal routing exactly. To summarize, the procedure of the hybrid approach is as follows. 1. Solve the mathematical model (just as the link weight setting method) to find the optimal solution, if the solution is not given. 2. Derive the following information from the optimal solution: a) The optimal set of link weights, b) All the load balance sections, and c) The aggregated traffic split proportions for each load balance sections. 3. Set the links to the optimal link weights 4. Set up traffic split LSPs for each load balance section. Set the weights of the LSPs as the sum of the link weights of their respective paths. Set their bandwidths to the optimal aggregated traffic split proportions. Advertise these LSPs as forwarding adjacencies into IGP [8] and make LSPs the preferred paths over the native IGP paths [6] [7]. 5. IGP will compute the optimal shortest path routing. Traffic will follow the IGP shortest path routing and only at the load balance sections will diverge to appropriate LSPs to achieve the optimal load balancing. WAng, Y. & Zhang, L. [Page 7] Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001 Load Balance Sections and their Scope Since in the hybrid approach we only establish LSPs for load balance sections, the concept of load balance section is a key concept and we would like to offer a thorough description of it. We first give a precise definition of load balances section and then provide an investigation of load balance scopes for nested load balance sections. A load balance section with respect to a given optimal routing consists of two nodes, one is called the head end and one is called the tail end, and two or more paths called LB (Load Balance) paths between the head end and the tail end such that: ¸ All of the LB paths are optimal shortest paths, ¸ LB paths diverge at the head end and converge at the tail end, and ¸ LB paths never come back together at any point in between. Again using the example in figure 1, D-G is a load balance section but C-H is not. Although C-H also has multiple optimal paths, the paths do not diverge at C nor converge at H. A load balance section is a property of an optimal routing as a whole, but not a property of the routing of an individual demand. It is shared by all the demands whose optimal paths traverse the section. D / \ / \ C/ \G / \ / \ / \ / \ A-----B/ \ / \H--------I \ E / \ / \ / \ / \ / \ / F Figure 2 WAng, Y. & Zhang, L. [Page 8] Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001 Load balance sections can be nested one inside another. The example in figure 2 has two load balance sections, B-H and C-G, where C-G is inside B-H. Obviously any optimal paths between C-G are also on the optimal paths between B-H. There are three optimal paths between B-H. Therefore we need to set up three LSPs for B-H, LSP1, LSP2, and LSP3 (not shown). The first two LSPs, LSP1 (B-C-D-G-H) and LSP2 (B-C-E-G-H) also traverse load balance section C-G. The third LSP, LSP3, takes the bottom route (B-F-H). The bandwidths for these three LSPs are set according to the optimal routing specifications on how the aggregated traffic between B-H should be split. Since for load balance section C-G, there are only two optimal paths, we need only set up two LSPs, LSP4 (C-D-G) and LSP5 (C-E-G), between C-G (not shown). Similarly the bandwidths for LSP4 and LSP5 are set according to the optimal routing specifications on how the aggregated traffic between C-G should be split. Please note that here the aggregated traffic for C-G does not include the portion of the aggregated traffic for B-H which flows through LSP1 and LSP2. It can been seen that the LSPs for C-G are only responsible for load balancing "local" traffic, or more specifically, demands between nodes B-G, C-G, and C-H. The balancing of "through" traffic is taken care of by two of the LSPs for the outer load balance section B-H, LSP1 and LSP2. The advantage of this separation is that the impact of any changes to a nested load balance section may only be limited to local traffic and may not affect its outer load balance sections. The downside is of course that it may be desirable sometimes that a load balance section should be able to balance all the traffic flowing through it, not just local traffic. Unfortunately the current technology does not support the latter option, even though the optimal routing solution provides traffic split ratios for either way. Dynamic Load Balancing In addition to its scalability, another benefit of this approach is that it not only can handle static traffic patterns, but also can address traffic changes dynamically. The key for this capability is the rapid reconfigurability of LSPs' bandwidth. WAng, Y. & Zhang, L. [Page 9] Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001 The original LSP bandwidth is set according to the optimal split proportions of the optimal routing. The optimal routing is the solution of the mathematical traffic engineering model which is formed based on static traffic or statistical average traffic. The actual traffic flowing across the network may deviate from this ôassumedö traffic pattern from time to time. Therefore it would be desirable if the approach can modify its way of directing traffic flows in response to traffic fluctuations rapidly or in real time. Fortunately this hybrid approach can handle traffic changes in a quick and easy way. When load level disparity among the constituent links of LSPs of a load balance section is detected, the bandwidths of these LSPs can be adjusted to make the load levels more even. In RSVP-TE [9], we can use the shared reservation style to setup a new LSP with the adjusted bandwidth to replace the old LSP with the old bandwidth gracefully. The time this process takes is usually very short. Two clarifications should be made with this dynamic load balance feature. First, the changes in the aggregated traffic to be split across a load balance section are not the reason for the modification of LSP bandwidth ratios because all the LSPs at the load balance section are designed to share the load of the same traffic. The traffic volume scale up or scale down should not affect the percentages of their shares. What triggers the modification is the uneven load changes of individual links of the load balance sections caused by traffic in other directions. In the example of figure 1, what may cause bandwidth adjustments to LSP1 and LSP2 are the possible changes of traffic between nodes D and E, or E and G, or D and F, or F and G, or E and F, but not the aggregated traffic between D and G. Second, this reconfiguration still stays within the optimal routing pattern. If the traffic changes so drastically that load balance ratio adjustments can no longer handle, we have to re-compute a new set of optimal routes based on a new assumed traffic pattern. But hopefully this global re-optimization does not need to be done too often for at least two reasons. First, carriers desire route stability and even though routing needs to be changed to reflect new traffic, changes should be made gradually in a controlled fashion, not drastically in every minute. Second, technically the IGP protocols take time to converge and do not allow real time link weight changes either. WAng, Y. & Zhang, L. [Page 10] Internet Draft draft-wang-te-hybrid-approach-00.txt June 2001 Security Considerations This document raises no new security concerns for IP network traffic engineering. References [1] Yufei Wang, Zheng Wang, Leah Zhang, "Internet traffic engineering without full mesh overlaying," Proceedings of INFOCOM'2001, April 2001. [2] D. Awduche, J. Malcolm, J. Agogbua, M. O'Dell, J. McManus, "Requirements for traffic engineering over MPLS," RFC2702, September 1999. [3] Yufei Wang and Zheng Wang, "Explicit routing algorithms for internet traffic engineering," Proceedings of ICCCN'99, September 1999. [4] R. Ahuja, T. Magnanti, J. Orlin, "Network Flows", Prentice Hall, 1993. [5] B. Fortz and M. Thorup, "Internet traffic engineering by optimizing ospf weights," Proceedings of INFOCOM'2000, March 2000. [6] Cisco IOS. http://www.cisco.com/univercd/cc/td/doc/product/software/ ios120/120newft/120t/120t7/te120_7t.htm [7] Juniper JUNOS. http://www.juniper.net/ [8] K. Kompella and Y. Rehkter, "LSP hierarchy with MPLS TE," Internet Draft, draft-ietf-mpls-lsp-hierarchy-02.txt, February 2001. [9] D. Awduche, et.al, "RSVP-TE: Extensions to RSVP for LSP tunnels," Internet Draft, draft-ietf-mpls-rsvp-lsp-tunnel-08.txt, February 2001. Author Information Yufei Wang 20 Corporate Place South Piscateway, NJ 08854 Phone: +1 732-465-1000, x1258 Email: ywang@photuris.com Leah Zhang 20 Corporate Place South Piscateway, NJ 08854 Phone: +1 732-465-1000, x1252 Email: lzhang@photuris.com