One document matched: draft-thubert-rtgwg-arc-bicast-00.txt
RTGWG P. Thubert, Ed.
Internet-Draft cisco
Intended status: Standards Track IJ. Wijnands
Expires: April 14, 2013 Cisco Systems
October 11, 2012
Applying Available Routing Constructs to bicasting
draft-thubert-rtgwg-arc-bicast-00
Abstract
This draft introduces methods that leverage the concept of ARC to
enable bicasting operations.
Requirements Language
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].
Status of this Memo
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 14, 2013.
Copyright Notice
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
Thubert & Wijnands Expires April 14, 2013 [Page 1]
Internet-Draft ARC bicasting October 2012
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.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Downward Bicasting Operation . . . . . . . . . . . . . . . . . 5
4. Upward Bicasting Operations . . . . . . . . . . . . . . . . . 6
4.1. Resolving crossing ARCs . . . . . . . . . . . . . . . . . 6
4.2. Single Point of Failure . . . . . . . . . . . . . . . . . 7
5. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 9
5.1. In conjunction with Protocol Independent Multicast . . . . 9
6. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 9
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
8. Security Considerations . . . . . . . . . . . . . . . . . . . 9
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 9
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9
10.1. Normative References . . . . . . . . . . . . . . . . . . . 9
10.2. Informative References . . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10
Thubert & Wijnands Expires April 14, 2013 [Page 2]
Internet-Draft ARC bicasting October 2012
1. Introduction
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.
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:
+========I========+
| |
| +====J====+
| | |
+====H====+ | +=====K=====+
| | | | |
+====D====+ +====E====+ +====F====+ +====G====+
| | | | | | | |
+=========B=========+ | | +==========C==========+
| | | | | |
| +======A=======+ |
| | | |
------------------------------------------------------------------Omega
Figure 1: ARC Representation
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.
Thubert & Wijnands Expires April 14, 2013 [Page 3]
Internet-Draft ARC bicasting October 2012
2. Terminology
The draft uses the terminology defined in [I-D.thubert-rtgwg-arc].
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].
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
One way of doing this is
o The basic rule is that an ARC MUST have at least one Left and one
Right Edge.
o The leg of an ARC between the cursor and the Edge inherits the
side of the Edge. In a Comb, the whole buttressing ARC inherits
the side of the Edge.
o An Edge ending in Omega can arbitrarily become Left or Right as
long as the basic rule is satisfied.
o An Edge that does not end in Omega inherits the side of an ARC it
terminates into, again as long as the basic rule is satisfied.
o A collision occurs if all the Edges end up on the same side. The
shortest path is used to resolve the collision and restore the
basic rule: the Edge closer to Omega and all butressing ARCs on
the same side of the cursor keep the side, and the other Edges are
toggled. In case of equal cost, an other tie breaker must be
used.
Thubert & Wijnands Expires April 14, 2013 [Page 4]
Internet-Draft ARC bicasting October 2012
o For instance, this situation occurs in the representation above
for ARC F, which has both ends ending in a Right side of ARCs, and
since the Edge closer to Omega is the one that ends in ARC C, that
Edge becomes Right and the other becomes Left.
3. Downward Bicasting Operation
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.
The packets exit the ARCs along their paths through an Edge that
matches the indication in the packet.
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
As it goes, the method does not guarantee a full non congruence of
the paths, as illustrated above. In case of a breakage, this can be
compensated by the capability to return a packet along an ARC upon a
failure, that is already used to protect unicast traffic.
Thubert & Wijnands Expires April 14, 2013 [Page 5]
Internet-Draft ARC bicasting October 2012
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
4. Upward Bicasting Operations
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.
4.1. Resolving crossing ARCs
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======Arrrrrrrr |
| | r |
------------------------------------------------------------------Omega
Figure 5: crossing: Right packet
Then comes the left reservation which collisions:
Thubert & Wijnands Expires April 14, 2013 [Page 6]
Internet-Draft ARC bicasting October 2012
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
The segment between the two incoming point of the common ARC is
common to both path and expose the bicasted traffic. The resolution
is to leave the second packet through but prune the unwanted states
along the collision segment of the ARC afterwards.
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
States along the ARC between the two incoming points are cleaned, up
and the paths that were generated by the Left and Right packets are
now crossed. This results in two non-congruent upward paths.
4.2. Single Point of Failure
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.
Thubert & Wijnands Expires April 14, 2013 [Page 7]
Internet-Draft ARC bicasting October 2012
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
The resoution is to reject the second packet and send it back along
the incoming ARC to exit on the other side. The rejected packet
clans up the states that it has created on its way back and then
creates states on the other side of the ARC.
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
At this point the downward packet will exit the incoming ARC in the
wrong side for its own indication.
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
This is in fact what happens also in the case of a monoconnected
zone, or if a breakage cause the downward packet to bounce.
Thubert & Wijnands Expires April 14, 2013 [Page 8]
Internet-Draft ARC bicasting October 2012
5. Applicability
5.1. In conjunction with Protocol Independent Multicast
(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.
6. Manageability
This specification describes a generic model. Protocols and
management will come later
7. IANA Considerations
This specification does not require IANA action.
8. Security Considerations
This specification is not found to introduce new security threat.
9. Acknowledgements
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.
10. References
10.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
10.2. Informative References
[I-D.thubert-rtgwg-arc]
Thubert, P. and P. Bellagamba, "Available Routing
Constructs", draft-thubert-rtgwg-arc-00 (work in
Thubert & Wijnands Expires April 14, 2013 [Page 9]
Internet-Draft ARC bicasting October 2012
progress), October 2012.
[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.
Authors' Addresses
Pascal Thubert (editor)
Cisco Systems, Inc
Village d'Entreprises Green Side
400, Avenue de Roumanille
Batiment T3
Biot - Sophia Antipolis 06410
FRANCE
Phone: +33 497 23 26 34
Email: pthubert@cisco.com
IJsbrand Wijnands
Cisco Systems
De kleetlaan 6a
Diegem 1831
Belgium
Email: ice@cisco.com
Thubert & Wijnands Expires April 14, 2013 [Page 10]
| PAFTECH AB 2003-2026 | 2026-04-21 19:30:02 |