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]