Internet DRAFT - draft-thubert-rtgwg-arc-bicast
draft-thubert-rtgwg-arc-bicast
RTGWG P. Thubert, Ed.
Internet-Draft cisco
Intended status: Standards Track IJ. Wijnands
Expires: April 19, 2014 Cisco Systems
October 18, 2013
Applying Available Routing Constructs to bicasting
draft-thubert-rtgwg-arc-bicast-01
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 19, 2014.
Copyright Notice
Copyright (c) 2013 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.
Thubert & Wijnands Expires April 19, 2014 [Page 1]
Internet-Draft ARC bicasting October 2013
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Downward Bicasting Operation . . . . . . . . . . . . . . . . . 4
4. Upward Bicasting Operations . . . . . . . . . . . . . . . . . 5
4.1. Resolving crossing ARCs . . . . . . . . . . . . . . . . . 5
4.2. Single Point of Failure . . . . . . . . . . . . . . . . . 6
5. Applicability . . . . . . . . . . . . . . . . . . . . . . . . 7
5.1. In conjunction with Protocol Independent Multicast . . . . 7
6. Manageability . . . . . . . . . . . . . . . . . . . . . . . . 7
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7
8. Security Considerations . . . . . . . . . . . . . . . . . . . 7
9. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 7
10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8
10.1. Normative References . . . . . . . . . . . . . . . . . . 8
10.2. Informative References . . . . . . . . . . . . . . . . . 8
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 8
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:
Thubert & Wijnands Expires April 19, 2014 [Page 2]
Internet-Draft ARC bicasting October 2013
+========I========+
| |
| +====J====+
| | |
+====H====+ | +=====K=====+
| | | | |
+====D====+ +====E====+ +====F====+ +====G====+
| | | | | | | |
+=========B=========+ | | +==========C==========+
| | | | | |
| +======A=======+ |
| | | |
------------------------------------------------------------------Omega
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.
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
One way of doing this is
o The basic rule is that an ARC MUST have at least one Left and one
Right Edge.
Thubert & Wijnands Expires April 19, 2014 [Page 3]
Internet-Draft ARC bicasting October 2013
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.
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
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 19, 2014 [Page 4]
Internet-Draft ARC bicasting October 2013
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
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
Then comes the left reservation which collisions:
Thubert & Wijnands Expires April 19, 2014 [Page 5]
Internet-Draft ARC bicasting October 2013
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
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
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.
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
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.
Thubert & Wijnands Expires April 19, 2014 [Page 6]
Internet-Draft ARC bicasting October 2013
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
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
This is in fact what happens also in the case of a monoconnected
zone, or if a breakage cause the downward packet to bounce.
5. Applicability
5.1. In conjunction with Protocol Independent Multicast
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
Thubert & Wijnands Expires April 19, 2014 [Page 7]
Internet-Draft ARC bicasting October 2013
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", Internet-Draft draft-thubert-rtgwg-arc-00,
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 19, 2014 [Page 8]
