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]