MPLS WG L. Qiu Internet-Draft University of Texas at Austin Intended status: Standards Track Y. Yang Expires: January 13, 2011 Yale University Y. Zhang University of Texas at Austin July 12, 2010 MPLS-ff for Supporting Fractional Forwarding draft-yang-mpls-ff-01.txt Abstract A fractional-forwarding scheme is a highly compact, flexible scheme for specify routing for both traffic engineering (TE) and fast rerouting. The ability of fractional forwarding can be a key benefit of MPLS over OSPF/IS-IS. Many highly effective TE algorithms are proposed and evaluated based on fractional forwarding. In this document, we propose MPLS-ff, an extension to MPLS to allow efficient implementation of fractional forwarding. 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 13, 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 13, 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 13, 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 . . . . . . . . . . . . . 7 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8 6. Security Considerations . . . . . . . . . . . . . . . . . . . . 8 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 7.1. Normative References . . . . . . . . . . . . . . . . . . . 8 7.2. Informative References . . . . . . . . . . . . . . . . . . 8 Appendix A. Acknowledgments . . . . . . . . . . . . . . . . . . . 9 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9 Qiu, et al. Expires January 13, 2011 [Page 3] Internet-Draft MPLS-ff Extension July 2010 1. Introduction A fractional-forwarding 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, fractional forwarding specifies the fraction of traffic to be routed along each (logical) outgoing link. A major advantage of fractional-forwarding 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. This type of approaches can already be quite beneficial to traffic engineering by conducting load balancing among the selected paths. Thus, it can also benefit from our proposed fractional forwarding. An issue 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 fractional-forwarding representation is used to make computation tractable. In the second phase, a path generation technique can be used to convert a fractional-forwarding specification into a 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 fractional-forwarding, 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 fractional forwarding based MPLS. The rest of the document is organized as follows. In Section 2, we give details on fractional forwarding and list the required changes to the MPLS data plane. 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 13, 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 interface 1 with a splitting ratio of 0.3, while the other going out to interface 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 on 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 may 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 13, 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 this approach is fast deployment. An issue of this approach, however, is that the configuration command can be vendor specific, and thus lacking standard. Hence, 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. Note that the label distribution process and the fraction assignment are two orthogonal processes. One can have scenarios where a router locally adjusts the forwarding fractions. This is useful, for example, for TeXCP [5], where each router tries to balance the load among multiple LSPs. As another note, the fraction ratios at each switching node can be either local or global. By local, we mean that the ratios specifies the local fraction among the outgoing interfaces. By global, a ratio indicates the global fraction of the total traffic for the given OD pair. 4. Use Case Qiu, et al. Expires January 13, 2011 [Page 6] Internet-Draft MPLS-ff Extension July 2010 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 [4]. 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;" 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. Qiu, et al. Expires January 13, 2011 [Page 7] Internet-Draft MPLS-ff Extension July 2010 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 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. Qiu, et al. Expires January 13, 2011 [Page 8] Internet-Draft MPLS-ff Extension July 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 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 13, 2011 [Page 9]