| RTGWG | P. Thubert, Ed. |
| Internet-Draft | cisco |
| Intended status: Standards Track | IJ. Wijnands |
| Expires: April 12, 2013 | Cisco Systems |
| October 11, 2012 |
Applying Available Routing Constructs to bicasting
draft-thubert-rtgwg-arc-bicast-00
This draft introduces methods that leverage the concept of ARC to enable bicasting operations.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119].
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http:/⁠/⁠datatracker.ietf.org/⁠drafts/⁠current/⁠.
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."
This Internet-Draft will expire on April 12, 2013.
Copyright (c) 2012 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 Simplified BSD License.
Traditional routing and forwarding uses the concept of path as the basic routing paradigm to get a packet from a source to a destination by following an ordered sequence of arrows between intermediate nodes. In this serial design, a path is broken as soon as a single arrow is, and getting around a breakage can require path recomputation, network reconvergence, and incur delays to till service is restored.
Available Routing Constructs [I-D.thubert-rtgwg-arc] (ARC) introduces the concept of ARC as a routing construct made of a sequence of nodes and links with 2 outgoing edges, that is this resilient to one breakage so that an ARC topology is resilient to one breakage per ARC.
+========I========+
| |
| +====J====+
| | |
+====H====+ | +=====K=====+
| | | | |
+====D====+ +====E====+ +====F====+ +====G====+
| | | | | | | |
+=========B=========+ | | +==========C==========+
| | | | | |
| +======A=======+ |
| | | |
------------------------------------------------------------------Omega
Figure 1: ARC Representation
The routing graph to reach a certain destination is expressed as a cascade of ARCs, which terminates in an abstract destination Omega, each ARC providing its own independent domain of fault isolation and recovery:
This cascade of ARCs appears ideally suited to the operation of bicasting (a.k.a. duocasting), which consists in sending two copies of a single packet, if possible over divergent - that is fully or partially non-congruent - paths, in order to augment the chances that at least one of the copies reaches the destination timely.
The draft uses the terminology defined in [I-D.thubert-rtgwg-arc].
R========I========L
| |
| L====J====R
| | |
L====H====R | R=====K=====L
| | | | |
R====D====L L====E====R L====F====R R===G====L
| | | | | | | |
R=========B=========L | | R==========C==========L
| | | | | |
| L======A=======R |
| | | |
------------------------------------------------------------------Omega
Figure 2: Orienting ARCs
This specificatin also introduces Sided ARCs, that is ARCs with at least an Edge that is known as Left and an Edge that is known as Right. The sense of Left and Right adds up to the existing sense of height that is already defined in [I-D.thubert-rtgwg-arc].
Two copies of a same packet from a given node are forwarded downwards along opposite side of the cascading ARCs, each packet bearing an indication (such as a tag or a label) of its intended side, Left or Right.
packet |
rrrrrrrrrrrrrrVllll
r l
r llll=J====R
r l |
L====H=rrrr l R=====K=====L
| r l | |
R====D====L L==rrrrrrrr lll==F====R R===G====L
| | | r l | | |
R=========B=========L r l R==========C==========L
| | r l | |
| lllllllllrrlrrrr |
| l r |
------------------------------------------------------------------Omega
Figure 3: Bicasting Down an ARC ascade
packet |
l Left packet path rrrrrrrrrrrrrrVllll
R Right packet path r l
r llll=J====R
r l |
L====H=rrrr l R=====K=====L
| r l | |
R====D====L L==rrrrrrrr lll==F====R R===G====L
| | | r l | | |
R=========B=========L r l R==========C==========L
| | r l | |
| rrrrrrrrr\/lllll |
| r /\ l |
------------------------------------------------------------------Omega
Figure 4: Breakage at a Congruent Link
The packets exit the ARCs along their paths through an Edge that matches the indication in the packet.
It is also possible with a downward bicasting to place states in the intermediate routers in order to provision an upward bicast path from Omega to a source D. In that case, if the graph is biconnected, it is possible to resolve the pathological cases so as to ensure a real separation of the left and Right paths.
r |
R====D====L L==rrrrrrrr L====F====R R===G====L
| | | r | | | |
R=========B=========L r | R==========C==========L
| | r | | |
| L======Arrrrrrrr |
| | r |
------------------------------------------------------------------Omega
Figure 5: crossing: Right packet
r l
R====D====L L==rrrrrrrr lll==F====R R===G====L
| | | r l | | |
R=========B=========L r l R==========C==========L
| | r l | |
| L======Arrr?rrrr |
| | r |
------------------------------------------------------------------Omega
Figure 6: crossing: left packet approaching
r l
R====D====L L==rrrrrrrr lll==F====R R===G====L
| | | r l | | |
R=========B=========L r l R==========C==========L
| | r l | |
| lllllllll==rrrrr |
| l r |
------------------------------------------------------------------Omega
Figure 7: crossing: Resolved state
The first pathological case occurs when both Left and Right packet cross over the same ARC, as illustrated below. Say that the Right reservation comes first and sets up the right path:
r |
R====D====L L==rrrrrrrr L====F====R R===G====L
| | | r | | | |
R=========B=========L r / R==========C==========L
| | r/ | |
| L======A==rrrrrr |
| | r |
------------------------------------------------------------------Omega
Figure 8: SPoF: Right packet
r l
R====D====L L==rrrrrrrr lllllllllll R===G====L
| | | r lll l | |
R=========B=========L r ll R=====lllllllllllllllll
| | rll | l
| L======Arrrrrrrr l
| | r l
------------------------------------------------------------------Omega
Figure 9: SPoF: Left Packet
r l
R====D====L L==rrrrrrrr L=lllllllll R===G====L
| | | r | l | |
R=========B=========L r | R=====lllllllllllllllll
| | r | | l
| L======Arrrrrrrr l
| | r l
------------------------------------------------------------------Omega
Figure 10: SPoF: Resolved state
The second pathological case occurs when both Left and Right packet reach a same ARC at the same node, which is this a Single Point Of Failure (SPoF) for both paths.
(To be refined in 01) Upwards bicasting can be used for Protocol Independent Multicast PIM [RFC4601] and Point-to-Multipoint and Multipoint-to-Multipoint Label Switched Paths mLDP [RFC6388]. A bicasted downards Join message would establish two non congruent return paths, each path joining the receiver and Omega that is the set of existing receivers.
This specification describes a generic model. Protocols and management will come later
This specification does not require IANA action.
This specification is not found to introduce new security threat.
The authors wishes to thank Dirk Anteunis, Stewart Bryant, Patrice Bellagamba, George Swallow, Eric Osborne, Clarence Filsfils and Eric Levy-Abegnoli for their participation and continuous support to the work presented here.
| [RFC2119] | Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. |
| [RFC4601] | Fenner, B., Handley, M., Holbrook, H. and I. Kouvelas, "Protocol Independent Multicast - Sparse Mode (PIM-SM): Protocol Specification (Revised)", RFC 4601, August 2006. |
| [RFC6388] | Wijnands, IJ., Minei, I., Kompella, K. and B. Thomas, "Label Distribution Protocol Extensions for Point-to-Multipoint and Multipoint-to-Multipoint Label Switched Paths", RFC 6388, November 2011. |
| [I-D.thubert-rtgwg-arc] | Thubert, P and P Bellagamba, "Available Routing Constructs", Internet-Draft draft-thubert-rtgwg-arc-00, October 2012. |