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]