MPLS WG L. Qiu Internet-Draft University of Texas at Austin Intended status: Standards Track Y. Yang Expires: January 6, 2011 Yale University Y. Zhang University of Texas at Austin July 5, 2010 MPLS-ff for Supporting Flow-Based Routing draft-yang-mpls-ff-00.txt Abstract A flow-based routing scheme is a highly compact, flexible scheme for specify routing for both traffic engineering (TE) and fast rerouting. Many highly effective TE algorithms are proposed and evaluated based on flow-based routing. In this document, we propose MPLS-ff, an extension to MPLS to allow efficient implementation of flow-based routing. We present the required extensions in the MPLS data forwarding plane. We also list the requirements in signaling for MPLS-ff. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [1]. Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. 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/ietf/1id-abstracts.txt. Qiu, et al. Expires January 6, 2011 [Page 1] Internet-Draft MPLS-ff Extension July 2010 The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on January 6, 2011. Copyright Notice Copyright (c) 2010 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the BSD License. Qiu, et al. Expires January 6, 2011 [Page 2] Internet-Draft MPLS-ff Extension July 2010 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Data Plane Extension Requirements . . . . . . . . . . . . . . . 5 3. Control Plane Extension Requirements . . . . . . . . . . . . . 6 4. Use Case . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4.1. Resilient Routing Reconfiguration . . . . . . . . . . . . . 6 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7 6. Security Considerations . . . . . . . . . . . . . . . . . . . . 7 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 7.1. Normative References . . . . . . . . . . . . . . . . . . . 8 7.2. Informative References . . . . . . . . . . . . . . . . . . 8 Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . . 8 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 8 Qiu, et al. Expires January 6, 2011 [Page 3] Internet-Draft MPLS-ff Extension July 2010 1. Introduction A flow-based routing scheme is a highly compact, flexible scheme for specify routing for both traffic engineering (TE) and fast rerouting (FRR). In this scheme, for a given origin-destination (OD) pair, a set of links are used to carry traffic for this pair; at each router, flow routing specifies the fraction of traffic to be routed along each (logical) outgoing link. A major advantage of flow-based routing is that it allows efficient computation of optimal traffic engineering and fast rerouting. Many highly effective TE algorithms are proposed and evaluated using realistic traffic patterns. They can consider many factors including traffic variations and network failures [2], [3], [4]. In contrast, traffic engineering using path-based routing (i.e., routing specified by how traffic is split among LSPs) can be intractable, since there can be exponential number of candidate LSPs between each OD pair. There are several ways to address the intractability problem of computation using path-based routing. One type of approaches is to preselect a small number of paths (e.g., K-shortest paths [5]) and then focus traffic engineering to only these preselected paths. A limitation of this type of approaches is that the preselected paths need to have high quality. Another type of approaches is to use a two-phase process. In the first phase, a flow-based routing representation is used to make computation tractable. In the second phase, a path generation technique can be used to convert a flow-based routing into path-based routing. A problem of this type of approaches is that a small variation in the result of the first-phase can lead to a different set of paths to be selected. For example, in a recent proposed scheme named R3, the protection routing needs to be revised (i.e., traffic splitting ratios re-scaled) after each failure. With flow-based routing, the re-scaling can be implemented efficiently. The objective of this document is to propose a simple extension to MPLS to allow efficient implementation of flow-based routing. The rest of the document is organized as follows. In Section 2, we give details on flow-based routing and list the required changes to MPLS data plane to support flow-based routing. We name the extension MPLS-ff, standing for MPLS with flow and flexible forwarding. In Section 3, we discuss requirements on extensions in the control plane to signal MPLS-ff configurations. In Section 4, we give one use case. Qiu, et al. Expires January 6, 2011 [Page 4] Internet-Draft MPLS-ff Extension July 2010 2. Data Plane Extension Requirements The new functionality required by MPLS-ff does not require any change to MPLS header. MPLS-ff needs an ability to associate multiple outgoing subentries with an incoming entry in a switching table, so that we can achieve more flexible traffic forwarding. For each outgoing subentry, MPLS-ff specifies a next-hop splitting ratio, indicating the desired fraction of traffic to be sent to that entry. As an example, with MPLS-ff, the switching table of a transit router may specify that the incoming label 10,000 is associated with two outgoing subentries: one going out to port 1 with a splitting ratio of 0.3, while the other going out to port 3 with a splitting ratio of 0.7. This means that traffic with incoming label 10,000 is split to the two outgoing entries, with the first one taking 30% traffic, while the second one taking 70%. MPLS-ff does not specify the exact details of how to implement the splitting ratios. However, it is desired that the implementation of the splitting ratios SHOULD satisfy additional requirements. Consistent Forwarding: One straightforward approach of implementing the splitting ratios is random splitting. However, this may cause packets of the same TCP flow to follow different routes, which will generate out-of-order packets and degrade TCP performance. To avoid unnecessary packet reordering, packets belonging to the same TCP flow should be routed consistently. One way to achieve consistent splitting is to use hashing. The hashing implementation should satisfy two requirements: 1. At each given switching router, the hash of the packets belonging to the same (TCP) flow should be the same so that all these packets are forwarded along the same path. 2. The hash of a flow at different routers should be independent of each other. One way to achieve this is that the input to the hash should include router ID in addition to (TCP) flow identification fields. If the hash value is only determined by the TCP flow, the probability distribution of the hash values might be "skewed" on some routers. For example, for a TCP flow ab, if router i only forwards the packets with hash values between 40 and 64 to router j, then router j may never see packets in TCP flow ab with hash values less than 40. Qiu, et al. Expires January 6, 2011 [Page 5] Internet-Draft MPLS-ff Extension July 2010 3. Control Plane Extension Requirements We envision that a first approach to setup MPLS-ff is to use static configurations. An advantage of fast deployment. An issue of this approach, however, is that the configuration command can be vendor specific, thus lacking standard. Thus, it can be desirable to extend an existing MPLS signaling protocol to allow setting up MPLS-ff states at the switching routers for a given flow. We identify the following requirements: o The signaling protocol is extensible to carry the next-hop splitting ratios. An MPLS signaling protocol allowing TLV (e.g., RSVP based) can be extended to carry a new type of splitting ratio. o The signaling protocol can set up MPLS-ff states at a set of routers that do not form a single path, but a directed acyclic graph (DAG). An additional requirement that is related with both data forwarding and signaling is MPLS label space management. For scalability and ease of signaling, different switching routers may assign different outgoing label values for the same OD pair. However, traffic of the same OD pair from multiple incoming labels may converge to the same router again. As an example, in Figure 2 of [4], traffic of the same OD pair comes to router R2 from both R4 and R5. Ideally, the two incoming streams of data should belong to the same forwarding equivalence class (FEC) again. Supporting such convergence can reduce storage overhead and improve load balancing. 4. Use Case 4.1. Resilient Routing Reconfiguration Supporting of MPLS-ff can allow efficient implementation of new traffic engineering and fast rerouting capabilities. One use case is the implementation of a new capability named R3: Resilient Routing Reconfiguration. Specifically, R3 is a technique to address major practical challenges when using MPLS-based FRR in large business core networks [6]: o Complexity: "the existing FRR bandwidth and preemption design quickly becomes too complicated when multiple FRR paths are set up to account for multiple failures;" Qiu, et al. Expires January 6, 2011 [Page 6] Internet-Draft MPLS-ff Extension July 2010 o Congestion: "multiple network element failure can cause domino effect on FRR reroute due to preemption which magnifies the problem and causes network instability;" o No performance predictability: "service provider loses performance predictability due to the massive amount of combinations and permutations of the reroute scenarios." R3 is a routing protection protection scheme that is (i) provably congestion-free under a large number of failure scenarios; (ii) efficient by having low router processing overhead and memory requirements; (iii) flexible in accommodating different performance requirements (e.g., handling realistic failure scenarios, prioritized traffic, and the trade-off between performance and resilience); and (iv) robust to both topology failures and traffic variations. Note that by "congestion-free" in R3, it means that all traffic demands, except those that have lost reachability due to network partition, are routed without creating any link overload, when certain weak conditions are verified. This is a much stronger guarantee than providing reachability alone (as is commonly done in existing FRR schemes). Please see Section 4.3 of [4] for an example of how to use MPLS-ff to efficiently implement R3. Evaluations based on real Internet topologies and traffic traces show that R3 achieves near-optimal performance. Its performance is at least 50% better than existing protection schemes including OSPF reconvergence, OSPF with CSPF fast rerouting, and among others. 5. IANA Considerations This document makes no request of IANA. Note to RFC Editor: this section may be removed on publication as an RFC. 6. Security Considerations MPLS-ff introduces more routing states into each switching router. In addition, depending on the signaling protocol, additional security risks maybe introduced in attacking switching routers. 7. References Qiu, et al. Expires January 6, 2011 [Page 7] Internet-Draft MPLS-ff Extension July 2010 7.1. Normative References [1] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. 7.2. Informative References [2] Hao Wang, Haiyong Xie, Lili Qiu, Yang Richard Yang, Yin Zhang, and Albert Greenberg., "COPE: Traffic Engineering in Dynamic Networks", In SIGCOMM 2006. [3] Hao Wang, Yang R. Yang, Paul H. Liu, Jia Wang, Alex Gerber, and Albert Greenberg., "Reliability as an Interdomain Service", In SIGCOMM 2007. [4] Y. Wang, H. Wang, A. Mahimkar, R. Alimi, Y. Zhang, L. Qiu, Y.R. Yang., "R3: Resilient Routing Reconfiguration", In SIGCOMM 2010; available at http://cs-www.cs.yale.edu/homes/yry/projects/ reinforce/r3-sigcomm10.pdf. [5] S. Kandula, D. Katabi, B. Davie, and A. Charny., "Walking the Tightrope: Responsive yet Stable Traffic Engineering", In SIGCOMM 2005. [6] N. So and H. Huang., "Building a highly adaptive, resilient, and scalable MPLS backbone", In MPLS World Congress 2007. [7] Cetin, R., Nadeau, T., and K. Koushik, "Multiprotocol Label Switching (MPLS) Traffic Engineering Management Information Base for Fast Reroute", draft-ietf-mpls-fastreroute-mib-14 (work in progress), April 2010. Appendix A. Acknowledgments The proposed design is based on [4]. We thank Dave Wang from WANDL for valuable discussions. We thank Richard Alimi for creating an XML skeleton for this draft. Authors' Addresses Lili Qiu University of Texas at Austin Email: lili@cs.utexas.edu Qiu, et al. Expires January 6, 2011 [Page 8] Internet-Draft MPLS-ff Extension July 2010 Y. Richard Yang Yale University Email: yry@cs.yale.edu Yin Zhang University of Texas at Austin Email: yzhang@cs.utexas.edu Qiu, et al. Expires January 6, 2011 [Page 9]