Internet DRAFT - draft-bashandy-bgp-frr-vector-label

draft-bashandy-bgp-frr-vector-label



Network Working Group                                       A. Bashandy
Internet Draft                                                 N. Kumar
Intended status: Standards Track                     M. Konstantynowicz
Expires: January 2013                                     Cisco Systems
                                                           July 7, 2012

    BGP FRR Protection against Edge Node Failure Using Vector Labels
               draft-bashandy-bgp-frr-vector-label-00.txt


Abstract

Consider a BGP free core scenario. Suppose the edge BGP speakers PE1,
PE2,..., PEn know about a prefix P/m via the external routers CE1,
CE2,..., CEm.  If the edge router PEi crashes or becomes totally
disconnected from the core, it is desirable for a core router "P"
carrying traffic to the failed edge router PEi to immediately restore
traffic by re-tunneling packets originally tunneled to PEi and
destined to the prefix P/m to one of the other edge routers that
advertised P/m, say PEj, until BGP re-converges. In doing so, it is
highly desirable to keep the core BGP-free while not imposing
restrictions on external connectivity or complicating provisioning
effort. Thus (1) a core router should not be required to learn any
BGP prefix, (2) the size of the forwarding and routing tables in the
core routers should be independent of the number of BGP prefixes, (3)
re-routing traffic without waiting for re-convergence must not cause
loops, (4) provisioning effort should be kept at minimum, and (5)
there should be no restrictions on what edge routers advertise what
prefixes. For labeled prefixes, (6) the label stack on the packet
must allow the repair PEj to correctly forward the packet and (7)
there must not be any need to perform more than one label lookup on
any edge or core router during steady state

Status of this Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   This document may contain material from IETF Documents or IETF
   Contributions published or made publicly available before November
   10, 2008. The person(s) controlling the copyright in some of this
   material may not have granted the IETF Trust the right to allow
   modifications of such material outside the IETF Standards Process.
   Without obtaining an adequate license from the person(s)
   controlling the copyright in such materials, this document may not
   be modified outside the IETF Standards Process, and derivative
   works of it may not be created outside the IETF Standards Process,
   except to format it for publication as an RFC or to translate it
   into languages other than English.




Bashandy                Expires January ` 2013                 [Page 1]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   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

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html

   This Internet-Draft will expire on January 7, 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
   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
      1.1. Conventions used in this document.........................5
      1.2. Terminology...............................................5
      1.3. Problem definition........................................7
   2. Overview of BGP FRR in an MPLS Core............................8
      2.1. Control Plane operation...................................8
      2.2. Forwarding behavior at Steady State (while pPE is reachable)
      ..............................................................12
      2.3. Forwarding behavior when pPE Fails.......................13
   3. Overview of the BGP FRR using Vector Labels in an IP Core.....14
      3.1. Pure IP Core.............................................15

Bashandy               Expires January 7, 2013                 [Page 2]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

         3.1.1. Control Plane.......................................15
         3.1.2. Forwarding plane during Steady State (when pPE is
         reachable).................................................15
         3.1.3. Forwarding plane at Failure (when pPE is unreachable)15
      3.2. Hybrid IP core...........................................16
         3.2.1. Control Plane.......................................16
         3.2.2. Forwarding Plane during Steady State (when pPE is
         reachable).................................................17
         3.2.3. Forwarding plane at Failure (when pPE is unreachable)17
   4. Rules for Choosing and Managing the Repair path...............17
      4.1. General Rules for Managing the Repair Path...............18
      4.2. Rules for Choosing the Repair Path for Labeled Prefixes..19
   5. Inter-operability with Existing IP FRR Mechanisms.............19
   6. Example.......................................................20
      6.1. Control Plane............................................21
      6.2. Forwarding Plane at Steady State (When PE0 is reachable).22
      6.3. Forwarding Plane at Failure (When PE0 is not reachable)..24
   7. Security Considerations.......................................25
   8. IANA Considerations...........................................25
   9. Conclusions...................................................25
   10. References...................................................26
      10.1. Normative References....................................26
      10.2. Informative References..................................27
   11. Acknowledgments..............................................27
   Appendix A. Other Algorithms to Allocate and Disseminate Vector
   labels...........................................................28
      A.1. iPE chooses the repair path..............................28
         A.1.1. Allocating Vector Labels using a Hash Function......28
               A.1.1.1.1. Calculating and distributing the mapping rNH-
               >vL to different routers.............................28
               A.1.1.1.2. Risk  of Mis-configuration leading to Mismatch
               in rNH-->vL Mapping..................................29
               A.1.1.1.3. Risk of forwarding to Incorrect VRF during
               convergence only.....................................29
         A.1.2. pPE Allocates and advertises vL with protected prefixes
         ...........................................................29
               A.1.2.1.1. Risk of forward to Incorrect VRF during
               Convergence Only.....................................30
      A.2. pPE chooses rPE and distributes the mapping of vL-->rNH..30
      A.3. Combination of iPE and  pPE Choosing rPE.................31

1. Introduction

   In a BGP free core, where traffic is tunneled between edge routers,
   BGP speakers advertise reachability information about prefixes to
   other edge routers but not to core routers. For labeled address
   families, namely AFI/SAFI 1/4, 2/4, 1/128, and 2/128, an edge
   router assigns local labels to prefixes and associates the local
   label with each advertised prefix such as L3VPN [10], 6PE [11], and

Bashandy               Expires January 7, 2013                 [Page 3]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   Softwire [9]. Suppose that a given edge router is chosen as the
   best next-hop for a prefix P/m. An ingress router that receives a
   packet from an external router and destined to the prefix P/m
   "tunnels" the packet across the core to that egress router. If the
   prefix P/m is a labeled prefix, the ingress router pushes the label
   advertised by the egress router before tunneling the packet to the
   egress router. Upon receiving the packet from the core, the egress
   router takes the appropriate forwarding decision based on the
   content of the packet or the label pushed on the packet.

   In modern networks, it is not uncommon to have a prefix reachable
   via multiple edge routers. One example is the best external path
   [8]. Another more common and widely deployed scenario is L3VPN [10]
   with multi-homed VPN sites. As an example, consider the L3VPN
   topology depicted in Figure 1.


                                PE1 .............+
                                                |
                                       +--------+---------------+
                                       |                        |
                                       |   VPN 1 Network        |
                                       |                        |
                                       |            VPN prefix  |
                                       |           (10.0.0.0/8) |
                                       |                        |
                                       +---+--------------------+
                                           |
                                   /------CE1
                                  /
                                 /
    BGP-free core      P--------PE0
                                 \
                                  \
                                   \------CE2
                                           |
                                       +---+--------------------+
                                       |                        |
                                       |   VPN 2 Network        |
                                       |                        |
                                       |            VPN prefix  |
                                       |           (20.0.0.0/8) |
                                       |                        |
                                       +--------+---------------+
                                                |
                               PE2 .............+

             Figure 1 VPN prefix reachable via multiple PEs


Bashandy               Expires January 7, 2013                 [Page 4]

Internet-Draft       BGP FRR Using Vector Labels              July 2012



   As illustrated in Figure 1, the edge router PE0 is the primary NH
   for both 10.0.0.0/8 and 20.0.0.0/8. At the same time, both
   10.0.0.0/8 and 20.0.0.0/8 are reachable through the other edge
   routers PE1 and PE2, respectively.

   1.1. Conventions used in this document

   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].

   In this document, these words will appear with that interpretation
   only when in ALL CAPS. Lower case uses of these words are not to be
   interpreted as carrying RFC-2119 significance.

   1.2. Terminology

   This section defines the terms used in this document. For ease of
   use, we will use terms similar to those used by L3VPN [10]

   o  BGP-Free core: A network where BGP prefixes are only known to
      the edge routers and traffic is tunneled between edge routers

   o  External prefix: It is a prefix P/m (of any AFI/SAFI) that a BGP
      speaker has an external path. The BGP speaker may learn about
      the prefix from an external peer through BGP, some other
      protocol, or manual configuration. The protected prefix is
      advertised to some or all of the internal peers.

   o  Protectable prefix: It is an external prefix P/m of any
      AFI/SAFI) that a BGP speaker has an external path to and is
      eligible to have a repair path.

   o  Protected prefix: It is an external prefix P/m (of any AFI/SAFI)
      that a BGP speaker has an external path to and also has a repair
      path to.

   o  Primary Egress PE, "ePE": It is an IBGP peer that can reach the
      prefix P/m through an external path and advertised the prefix to
      the other IBGP peers. The primary egress PE was chosen as the
      best path by one or more internal peers. In other words, the
      primary egress PE is an egress PE that will normally be used by
      some ingress PEs when there is no failure. Referring to Figure
      1, PE0 is an egress PE.




Bashandy               Expires January 7, 2013                 [Page 5]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   o  Protected egress PE, "pPE" (Protected PE for simplicity): It is
      an egress PE for which there exists a repair path for some or
      all of the prefixes to which it has an external path. Referring
      to Figure 1, PE0 is a protected egress PE.

   o  Protected edge router: Any protected egress PE.

   o  Protected next-hop (pNH): It is an IPv4 or IPv6 host address
      belonging to the protected egress PE. Traffic tunneled to this
      IP address will be protected via the mechanism proposed in this
      document. Note that, in most cases, the protected next-hop will
      be different from the next-hop attribute in the BGP update
      message [2][3].

   o  CE: It is an external router through which an egress PE can
      reach a prefix P/m. The routers "CE1" and "CE2" in Figure 1 are
      examples of such CEs.

   o  Ingress PE, "iPE": It is a BGP speaker that learns about a
      prefix through another IBGP peer and chooses that IBGP peer as
      the next-hop for the prefix.

   o  Repairing P router "rP" (Also "Repairing core router" and
      "repairing router"): A core router that attempts to restore
      traffic when the primary egress PE is no longer reachable
      without waiting for IGP or BGP to re-converge. The repairing P
      router restores the traffic by rerouting the traffic (through a
      tunnel) towards the pre-calculated repair PE when it detects
      that the primary egress PE is no longer reachable. Referring to
      Figure 1, the router "P" is the repairing P router.

   o  Repair egress PE "rPE" (Repair PE for simplicity): It is an
      egress PE other than the primary egress PE that can reach the
      protected prefix P/m through an external neighbor. The repair PE
      is pre-calculated via other PEs prior to any failure. Referring
      to Figure 1, PE1 is the repair PE for 10.0.0.0/8 while PE2 is
      the repair PE for 20.0.0.0/8.

   o  Underlying Repair label (rL): The underlying repair label is the
      label that is advertised by rPE and is used by rPE to forward
      repaired traffic, which is traffic re-tunneled by the rP after
      detecting that the pPE is no longer reachable. A repair label is
      defined for labeled protected prefixes only.

   o  Repair next-hop (rNH): It is an IPv4 or IPv6 host address
      belonging to the repair egress PE. If the protected prefix is
      advertised via BGP, then the repair next-hop MAY be the next-hop
      attribute in the BGP update message [2][3].


Bashandy               Expires January 7, 2013                 [Page 6]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   o  BGP nexthop (bgpNH): This is the usual next-hop attribute for
      route advertisements as specified in [2]in [3]. In most case,
      bgpNH is different from pNH

   o  Vector Label (vL): It is a label that identifies the repair PE
      within a certain label context. Every distinct rPE must have a
      distinct vector label the aforementioned label context. Vector
      labels in different label contexts may overlap

   o  Repair path (Also Repair Egress Path): It is the repair next-
      hop. If an underlying repair label exists, the repair path is
      the repair next-hop together with the underlying repair label.

   o  Primary tunnel: It is the tunnel from the ingress PE to the
      primary egress PE

   o  Repair tunnel: It is the tunnel from the repairing P router to
      the repair egress PE

   1.3. Problem definition

   The problem that we are trying to solve is as follows

   o  Even though multiple prefixes may share the same egress router,
      they have different repair edge router. In Figure 1 above, both
      10.0.0.0/8 and 20.0.0.0/8 share the same primary next hop PE0,
      the routing protocol(s) must identify that the node protecting
      repair node for 10.0.0.0/8 is PE1 while the node protecting
      repair node for 11.0.0.0/8 is PE2

   o  On loosing connection to the edge router, the core router "P"
      MUST reroute traffic towards the *correct* repair edge router
      that can reach prefixes that were reachable via the failed edge
      router without waiting for IGP or BGP to re-converge and update
      the routing tables. On the failure of PE0 illustrated in Figure
      1, the core router P needs to  reroute traffic for 10.0.0.0/8
      towards PE1 and traffic for 11.0.0.0/8 towards PE2

   o  The repairing core router P MUST NOT be forced to learn about
      the BGP prefixes on any of the edge router. The same applies for
      all core routers.

   o  There SHOULD NOT be a need for a special router or group of
      routers to handle rerouting traffic on edge node failure.

   o  The size of the routing table on any core router MUST be
      independent of the number of BGP prefixes in the network.



Bashandy               Expires January 7, 2013                 [Page 7]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   o  Rerouting traffic without waiting for IGP and BGP to re-converge
      after a failure MUST NOT cause loops.

   o  For labeled prefixes, when a packet gets re-routed to the repair
      PE, the label stack on the packet MUST ensure correct
      forwarding.

   o  Provisioning and maintenance overhead must be kept at minimum

   o  At steady state, when pPE is reachable, paths taken by traffic
      must not be impacted by deploying the solution proposed in this
      document unless desired by the operator.

   o  The solution must be incrementally deployable

2. Overview of BGP FRR in an MPLS Core

   The solution proposed in this document relies on the collaboration of
   egress PE, ingress PE, penultimate hop routers, and repairing core
   router. This section gives an overview of how to the solution works
   for both labeled (AFI/SAFI 1/4, 2/4, 1/128, and 2/128) and unlabeled
   (AFI/SAFI 1/1, 2/1, 1/2, and 2/2) protected prefixes in an MPLS core.
   Specifications of the solution in IP core are provided in Section 3.

   2.1. Control Plane operation

   1. Each egress router that is capable of handling repaired traffic
      assigns each protectable labeled prefix a repair label: "rL". "rL"
      is advertised as optional path attribute. "rL" MUST be Per-CE or
      per-VRF for good BGP attribute packing and forwarding simplicity.
      For unlabeled prefix, no repair label is needed. A router that is
      capable of handling repaired traffic is called a repair PE "rPE".

       a. The semantics of the repair label "rL" is:

           i. If "rL" is per-CE, then pop *two* labels and send the
               packet to the appropriate CE

          ii. If "rL" is per-VRF, then pop *two* labels and forward the
               packet based on the contents under the two popped labels

   2. Each protectable egress PE (pPE) is assigned a unique protectable
      IP address "pNH". Traffic tunneled to pNH is protected by the BGP
      FRR proposed in this document

       a. Only a single pNH is needed per pPE




Bashandy               Expires January 7, 2013                 [Page 8]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

       b. If all iPE's support the BGP FRR scheme proposed in this
          document, then pNH may be the usual BGP next-hop attribute.
          Otherwise, pNH MUST NOT be identical to the BGP next-hop
          attribute

       c. pPE advertises pNH as a prefix into IGP

       d. pPE advertises an explicit label for pNH (instead of the usual
          implicit NULL). This way if the penultimate hop does not
          understand the BGP FRR scheme proposed in this document, pPE
          can handle the special popping behavior for protected traffic
          tunneled to pNH

       e. "pPE" advertises the protected next-hop "pNH" to the
          penultimate hops to indicate that traffic flowing through the
          tunnel to the tail end "pNH" is protected against the failure
          of the node "pPE" and requires special processing by the
          penultimate hop as will be described in the next few steps

       f. For every BGP next-hop (bgpNH) that pPE advertises with its
          routes, pPE separately advertises the mapping (bgpNH,pNH) to
          all ingress PE. A method analogous to how tunnel information
          is advertised [4] can be used to advertise this mapping to
          ingress PE's. The mapping "(bgpNH,pNH)" means: if the ingress
          PE wants to protect traffic normally tunneled to "bgpNH"
          against the failure of "pPE", the iPE MUST tunnel the traffic
          to "pNH" instead of bgpNH.

   3. If a pPE knows that a P/m to which it has an external path is also
      reachable via another PE,

       a. pPE chooses one of the other PEs as a repair PE "rPE". The pPE
          chooses, as a repair next-hop, an IP address "rNH" local to or
          advertised by rPE. Rules governing rNH are

           i. "rNH" SHOULD be the next-hop attribute advertised by rPE
               when it announces reachability to the protected prefix
               P/m to minimize the number of prefixes advertised into
               IGP and BGP.

          ii. if rPE also advertised a protected next-hop (pNH) for any
               BGP prefix that rPE can protect, then rNH MUST NOT be any
               protected next-hop (pNH) advertised by rP

       b. pPE assigns a vector label "vL" for "rNH". A distinct "vL" is
          needed for every distinct "rNH" within the context of a pPE




Bashandy               Expires January 7, 2013                 [Page 9]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

       c. pPE advertises the mapping (pNH,rNH,vL) to all ingress PE's.
          The mapping (pNH,rNH,vL) means: "Within the context of the
          protected next-hop pNH, the repair next-hop rNH is assigned
          the vector label vL"

       d. "pPE" advertises the triplet (pNH,rNH,vL) to candidate
          repairing core routers. For example, an LDP optional TLV can
          be used for this purpose

   4. An ingress PE "iPE" receives route updates from pPE with "bgpNH"
      as the next-hop attribute. Suppose an ingress PE "iPE" chooses
      "bgpNH" as the best path for one or more protectable PE. If iPE
      wants to protect traffic tunneled to "bgpNH" against pPE failure,
      "iPE"  performs the following steps

       a. iPE receives the mapping (bgpNH,pNH) from pPE to indicate that
          the protected next-hop for traffic tunneled to bgpNH is pNH

       b. iPE receives the mapping (pNH,rNH,vL) from "pPE" to indicate
          that the vector label pointing to the repair next-hop "rNH"
          for traffic tunneled to pNH is "vL"

       c. iPE receives an advertisement for the protectable route from
          rPE with "rNH" as the next-hop

       d. If the above 3 conditions are satisfied, then iPE chooses rPE
          as the repair PE with rNH as the repair next-hop and the
          vector label "vL"



   As a result of the above steps, the following nodes store the
   following information

   o  Ingress PE (iPE)

       o Receives from pPE NLRI advertisement for the protected labeled
          prefix P/m containing the usual BGP next-hop attribute "bgpNH"

       o Receives from pPE the mapping (bgpNH,pNH). This means that if
          iPE wants to protect traffic normally tunneled to "bgpNH"
          against pPE failure, the iPE MUST tunnel the traffic to "pNH"
          instead of "bgpNH"







Bashandy               Expires January 7, 2013                [Page 10]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

       o Receives the triplet (pNH,rNH,vL). The triplet (pNH,rNH,vL)
          means that if iPE chooses rNH as the repair next-hop for the
          traffic tunneled to the protected next-hop pNH, then iPE has
          to use the vector label "vL" while tunneling traffic. The
          method of using the vector label "vL" is described in the
          forwarding behavior in Section 2.2 and 2.3.

   o  Penultimate Hop

       o Receives the "pNH" from pPE

       o As such, it knows the pNH needs certain special treatment as
          described in the forwarding behavior in Section 2.2 and 2.3.

       o Penultimate hop advertises "pNH" as its own prefix into IGP.
          The penultimate hop advertises pNH so that when pPE is lost,
          nodes continue to forward the traffic towards the original pPE
          and hence get protected by the rP. This behavior is required
          until BGP on the iPE's recalculate and start forwarding
          traffic towards an alternative PE.

       o Penultimate hop advertises "pNH" as its own prefix into IGP
          but with one of the following conditions

            . For link-state IGPs, "pNH" MAY be advertised with
               *maximum metric* so as not to affect the path taken by
               the traffic flowing from iPE's to pPE's

            . For distance vector IGPs, the penultimate hop advertises
               metric of "pNH" as follows

               PHP-metric(pNH) =

                     pPE-metric(pNH) + metric-From-PHP-to-pPE

               That is, the metric advertised by the penultimate hop for
               pNH equals the metric advertised by pPE for pNH plus the
               metric from the penultimate hop to pPE

            . This way the advertisement of pNH by the penultimate hop
               into IGP does not impact the path taken by the traffic
               from iPE's to pPE's








Bashandy               Expires January 7, 2013                [Page 11]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

            . When does the penultimate hop stop advertising pNH as its
               own prefix? The penultimate hop should continue to
               advertise pNH long enough for iPE's to re-converge.
               Advertising pNH longer than necessary is harmless because
               iPE's would have already re-converged to a new BGP next-
               hop and hence no traffic will be attracted to the non-
               existing pNH. The specific period length can be subject
               to configuration but the default value may be in the
               order of 2-3 minutes

   o  Repairing core router "rP" (which may also be the penultimate hop)

       o Receives the triplet (pNH,rNH,vL) from pPE

       o Creates a distinct label context for "pNH"

            . In LDP core, the context is identified by the IGP label
               of pNH

            . In an IP core, the context is identified by the "pNH"
               address itself.

       o Inserts the label vL in the label context identified by pNH.

            . The forwarding entry for vL in the label context of pNH
               is

                 . Swap vL with the IGP label of rNH

                 . Forward the packet towards rNH

       o Installs the following forwarding entry for pNH

            . If pNH is not reachable, pop the label for pNH and lookup
               the label underneath the label of pNH in the label
               context of pNH

            . Otherwise, forward the packet to pNH as usual

   What is left it to outline the forwarding behavior before and after
   the failure of "pNH".

   2.2. Forwarding behavior at Steady State (while pPE is reachable)

   This section outlines the packet forwarding procedure when pPE is
   still reachable.

   1. Ingress PE (iPE) receives a packet matching P/m from an external
      neighbor and reachable via pPE

Bashandy               Expires January 7, 2013                [Page 12]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   2. Ingress PE: Pushes *four* labels

       o Bottom label: VPN label advertised by pPE

       o Second label: rL

       o Third label: vL corresponding to chosen rNH

       o Top label: IGP label towards pNH (not the bgpNH attribute)

       o In pushing the labels "vL" following by "rL", iPE practically
          encodes the chosen repair path into the packet.

   3. Penultimate Hop

       a. Receives a packet with top label bound to pNH

       b. Pops *three* labels *all the time*.

       c. Sends packet to pNH

   4. Protected Egress PE (pPE)

       a. Receives a packet with top label as VPN label

       b. Forwards the packet as usual

   Thus the packet can be delivered correctly to its destination.

   2.3. Forwarding behavior when pPE Fails

   The repairing router "rP" directly connected to a failure detects
   that pNH is no longer reachable. The following steps are applied.

   1. Repairing router "rP"

       a. Receives packet with top label bound to pNH

       b. pNH is not reachable

       c. Pop the label of pNH. The vector label "vL" is right under the
          label of pNH

       d. Lookup "vL" in the label context identified by the label of
          "pNH". The lookup yields a rewrite label corresponding to the
          chosen rNH

       e. Swap the top label with the label of rNH


Bashandy               Expires January 7, 2013                [Page 13]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

       f. Send packet towards rNH

       g. In effect, the repairing router uses the vector label to find
          the repair PE chosen by the ingress PE

   2. Penultimate hop of rPE

       a. rNH is not a protected NH for rPE

       b. Thus the penultimate hop employs the usual penultimate (single
          label) hop popping and then forwards the packet to rPE

   3. Repair PE (rPE)

       a. Receives packet with top label rL (which rPE advertised) and
          the bottom label is the regular VPN label advertised by the
          primary PE "pPE"

       b. Make a lookup on "rL"

       c. rL per CE

           i. Pop *two* labels.

          ii. Send to correct CE

       d. rL per VRF

           i. Pop *two* labels.

          ii. Make IP lookup in appropriate VRF

         iii. Send to the CE

   To protect unlabeled traffic there is no need for dual label popping
   or "rL". Instead, all the repairing router needs to do when it
   detects that "pNH" is no longer reachable is to re-tunnel the packet
   towards "rNH" in a regular LSP

   The next section presents the solution in an IP core.



3. Overview of the BGP FRR using Vector Labels in an IP Core

   This section describes the BGP FRR using vector labels solution in an
   IP core for both labeled (AFI/SAFI 1/4, 2/4, 1/128, and 2/128) and
   unlabeled (AFI/SAFI 1/1, 2/1, 1/2, and 2/2) protected prefixes.


Bashandy               Expires January 7, 2013                [Page 14]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   The primary difference between a MPLS core and an IP core is that the
   tunnels between edge routers are IP based such as [5][6][7]. In this
   section, we propose two alternatives: A completely pure IP core and a
   hybrid IP/MPLS core

   3.1. Pure IP Core

   In this section, we propose a scheme by which core routers are
   incapable of handling any kind of MPLS labels.

3.1.1. Control Plane

   The pPE still needs to advertise the mapping (bgpNH,pNH) as in
   Section 2 but it does not allocate or advertise a vector label.

   The rPE advertises rL with protected prefixes to all its iBGP peer as
   in MPLS core solution in Section 2.

   Assume iPE decides that rPE is the repair PE for a protected prefix.

   o  iPE pushes the usual VPN label for labeled prefixes

   o  iPE pushes the repair label "rL" advertised by the chosen rPE

   o  iPE pushes *two* IP tunnel headers on the packet

       o Repair tunnel header. This will be the inner tunnel header with
          destination address rNH towards the rPE

       o Protected tunnel header: This will be the outer tunnel header
          with destination address pNH towards the pPE

3.1.2. Forwarding plane during Steady State (when pPE is reachable)

   1. iPE pushes the VPN label and the repair label followed by the two
      tunnel headers described in the previous section

   2. rP: No special behavior necessary

   3. pPE

       a. Decapsulates *two* tunnel headers and the repair label "rL"

       b. Uses the contents of the packet underneath

3.1.3. Forwarding plane at Failure (when pPE is unreachable)

   1. iPE is not yet aware of the failure so its behavior remains the
      unchanged.

Bashandy               Expires January 7, 2013                [Page 15]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   2. rP

       a. Decapsulates the outer tunnel header towards pNH

       b. Uses the repair tunnel header to forward the packet towards
          rPE

   3. rPE

       a. Decapsulates the tunnel header

       b. Uses the repair label "rL" to forward the packet to the
          correct CE

           i. Pop rL and the VPN label under it

          ii. Use the forward the packet to the correct CE

   3.2. Hybrid IP core

   In this section, we assume that rP is capable of handling MPLS labels

3.2.1. Control Plane

   The pPE needs to advertise the mapping (bgpNH,pNH). iPE also needs to
   allocate a vector label for each known rPE and advertise the mapping
   (pNH,rNH,vL) to all its iBGP peers and to candidate repair core
   routers. This behavior is identical to iPE behavior in MPLS core in
   Section 2.

   The rPE advertises rL with protected prefixes to all its iBGP peer as
   in the case of MPLS core described in Section 2.

   Assume iPE decides that rPE is the repair PE for a given prefix:

   o  iPE pushes the usual VPN label for labeled prefix

   o  iPE pushes the repair label "rL" advertised by the chosen rPE

   o  Pushes the vector label of the chosen rPE

   o  iPE pushes two the protected tunnel header: This will be the outer
      IP tunnel header with destination address pNH towards the pPE

   rP behavior is identical to its behavior in an MPLS core in Section
   2.




Bashandy               Expires January 7, 2013                [Page 16]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

3.2.2. Forwarding Plane during Steady State (when pPE is reachable)

   4. iPE pushes the two tunnel headers described in the previous
      section

   5. rP: No special behavior necessary

   6. pPE

       a. Decapsulates the outer tunnel headers plus *two* labels (vL
          and rL

       b. Uses the contents of the packet after decapsulation to forward
          the packet

3.2.3. Forwarding plane at Failure (when pPE is unreachable)

   7. iPE is not yet aware of the failure so its behavior remains the
      same

   8. rP

       a. Decapsulates the tunnel header towards pNH

       b. Pops the vector label "vL"

       c. Looks up the vector label "vL" in the label context identified
          by pNH. The lookup should yield the rNH

       d. Encapsulates the packet into a tunnel header with destination
          address rNH and forwards the packet towards rPE

   9. rPE

       a. Decapsulates the tunnel header

       b. Uses the repair label "rL" to forward the packet to the
          correct CE

           i. Pop *two* labels for labeled traffic

          ii. Forward the packet to the correct CE

4. Rules for Choosing and Managing the Repair path

   This section specifies rules governing how a protectable edge
   router pPE chooses and advertises the repair path. Other than the
   rules in this section, the method of choosing the repair path is
   beyond the scope of this document.

Bashandy               Expires January 7, 2013                [Page 17]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   4.1. General Rules for Managing the Repair Path

   This section specifies general rules for choosing the repair path
   for both labeled and unlabeled prefixes.

   1. A repair PE MUST be another edge router that advertises the same
      prefix to the protected edge router pPE via IBGP peering.

   2. If a repairing P router "rP" determines that the path taken by
      the repair tunnel to a repair edge router rPE passes through the
      protected edge router pPE, then the repairing router "P" MUST
      NOT install this repair path in its forwarding plane. Instead,
      the repairing "p" router MAY use other paths that do not pass
      through pPE or use existing core FRR mechanisms such as [12],
      [13], and [14].

   3. Let the protected next-hop pNH match the IGP route pR. If the
      "rP" determines that the repair tunnel to a repair edge router
      passes through a next-hop of the IGP route pR, then the
      repairing router SHOULD NOT install this repair path in its
      forwarding plane.

   4. A protected next-hop uniquely identifies an protected PE within
      a BGP-free core. Thus a protected next-hop NH MUST NOT be
      advertised by two different pPEs.

   5. At any point in time, for the same primary and repair next-hops
      pNH and rNH, only one advertisement is valid. Thus for the same
      value of pNH and rNH, an advertisement of the pair (pNH,rNH)
      MUST override or be preceded by the withdrawal of any previously
      advertised pair (pNH,rNH).

   6. If the repair PE "rPE" advertises one or more protected next-
      hops, then the repair next-hop "rNH" MUST be different from any
      protected next-hop "pNH" advertised by rPE

   If rules (1), (2), and(3), then the tunnel to the repair edge router
   rPE does not provide protection against the failure of the edge node
   ePE. Instead it provides core protection against the failure of the
   path through the core leading to the protected edge node pPE. Thus
   existing core FRR protection mechanisms such as those specified in
   [12], [13], and [14] can be used instead.

   Rules (4), (5), and (5) ensures that there is no ambiguity about the
   primary and repair next-hops





Bashandy               Expires January 7, 2013                [Page 18]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   4.2. Rules for Choosing the Repair Path for Labeled Prefixes

   This section specifies rules in additions to those mentioned in
   Section 4.1 by which an edge router iPE chooses and advertises the
   repair path for a protected labeled prefix P/m.

      A edge router iPE MUST only choose the edge router rPE and the
      underlying repair label rL as a repair path for the prefix P/m
      if the "rL" allocated on per-VPN or per-CE/per-next-hop basis.

   The reason for this rule is that "rL" is advertised as path
   attributes in MP/BGP updates. If "rL" is allocated on per-prefix
   basis, then attribute packing will be severely impacted



5. Inter-operability with Existing IP FRR Mechanisms

   Current existing IP FRR mechanisms can be divided into two
   categories: core protection and edge protection. Core protection
   techniques, such as [12], [13], and [14], provide protection against
   internal node and/or link failure. Thus the technique proposed in
   this document is not related to existing IP FRR mechanisms. If the
   failure of an internal node or link results in completely
   disconnecting a protectable edge node, then an administrator MAY
   configure the repairing router to prefer the technique proposed in
   this document over existing IP FRR mechanisms.

   Edge protection techniques, such as [16] provide protection against
   the failure of the link between PE and CE routers. Thus existing PE-
   CE link protection can co-exist with the techniques proposed in this
   document because the two techniques are independent of each other.


















Bashandy               Expires January 7, 2013                [Page 19]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

6. Example

   We will use and LDP core as an example. Consider the diagram
   depicted in Figure 2 below. We assume that the PEs advertise repair
   labels as specified in [15]

     +-----------------------------------+
     |                                   |
     |   LDP Core                        |
     |                                   |
     |                                  PE1  Lo = 9.9.9.1
     |                                   |\
     |                                   | \
     |                                   |  \
     |                                   |   \
     |                                   |  CE1.......VRF "Blue"
     |                                   |   /       (10.0.0.0/8)
     |                                   |  /        (11.0.0.0/8)
     |                                   | /
     |                                   |/
   PE11                        P--------PE0    Lo1 = 1.1.1.1/32
     |                                   |\    Lo2 = 1.1.1.2/32
     |                                   | \
     |                                   |  \
     |                                   |   \
     |                                   |  CE2.......VRF "Red"
     |                                   |   /       (20.0.0.0/8)
     |                                   |  /        (21.0.0.0/8)
     |                                   | /
     |                                   |/
     |                                  PE2  Lo = 9.9.9.2
     |                                   |
     |                                   |
     +-----------------------------------+
                Figure 2 : Edge node BGP FRR in LDP core


   o  In Figure 2, PE0 is the pPE for VRFs "Blue" and "Red". PE1 and PE2
      are the rPEs for VRFs "Blue" and "Red", respectively. VRF Blue has
      10.0.0.0/8 and 11.0.0.0/8 and VRF Red has 20.0.0.0/8 and
      21.0.0.0/8

   o  Assuming PE0 uses per prefix label allocation, PE0 assigns the VPN
      labels 4100, 4200, 4300, and 4400 to 10.0.0.0/8, 11.0.0.0/8,
      20.0.0.0/8, and 21.0.0.0/8 respectively. PE0 advertises the
      prefixes 10.0.0.0/8, 11.0.0.0/8, 20.0.0.0/8, and 21.0.0.0/8 using
      MP/BGP as usual



Bashandy               Expires January 7, 2013                [Page 20]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   6.1. Control Plane

   1. rPEs Allocate and advertise Repair labels

       a. Acting as a rPE, PE1 allocates (on per-CE basis) and
          advertises a repair label rL1=3100 with the prefixes
          10.0.0.0/8 and 11.0.0.0/8 to all iBGP peers

       b. Similarly, PE2 allocates and advertises the repair label
          rL2=3200 with the prefixes 20.0.0.0/8 and 21.0.0.0/8

   2. pPE calculates and advertises the pNH

       a. Assume that PE0 uses "Loopback0" as the BGP next-hop, PE0
          automatically picks Loopback2 as the pNH. As such PE0
          advertises (bgpNH,pNH)=(1.1.1.1,1.1.1.2) to all iBGP peers
          including the iPE PE11.

       b. When the iPE "PE11" receives (bgpNH,pNH)=(1.1.1.1,1.1.1.2),
          PE11 understands that if it wants to protect traffic whose
          bgpNH=1.1.1.1 against the failure of the node 1.1.1.1, PE11
          has to tunnel the traffic to 1.1.1.2 instead of 1.1.1.1

   3. pPE allocates and advertizes vector labels

       a. On receiving the repair labels 3100 and 3200 from PE1 and
          PE2, respectively, PE0 detects that there are two rPEs: PE1
          and PE2. AS such PE0 assigns two vector labels vL1 = 1100
          and vL2 = 1200 to PE1 and PE2, respectively

       b. PE0 advertises (1.1.1.2, 9.9.9.1, 1100)  and (1.1.1.2,
          9.9.9.2, 1200) to all iBGP peers, including the ingress PE
          PE11

       c. On receiving (1.1.1.2, 9.9.9.1, 1100) and (1.1.1.2, 9.9.9.2,
          1200), the ingress PE PE11 understand that if it were to
          pick 9.9.9.1 as the rPE for packet tunneled to 1.1.1.2, then
          it has to push the vector lagbel 1100. Similarly, to protect
          a packet tunneled to 1.1.1.2 using the rPE 9.9.9.2, then it
          has to push the vector label 1200.

       d. PE0 also advertises (1.1.1.2, 9.9.9.1, 1100) and (1.1.1.2,
          9.9.9.2, 1200) to all candidate repairing core routes,
          including the core router "P".

   4. The repairing core router creates the repair state




Bashandy               Expires January 7, 2013                [Page 21]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

       a. Acting as a rP, the core router "P" receives the
          advertisements (1.1.1.2, 9.9.9.1, 1100)and (1.1.1.2,
          9.9.9.2, 1200) from PE0.

       b. rP understands that it has to pop *3* labels when it
          receives a packet whose top label is the LDP label for
          1.1.1.2

       c. rP creates a label context identified by the LDP label of
          1.1.1.2/32

       d. rP inserts the following two label entries in the created
          label context

           i. 1100-->9.9.9.1

          ii. 1200-->9.9.9.2

   5. The ingress PE calculates the rPEs

       a. PE11 receives an advertisement for 10.0.0.0/8, 11.0.0.0/8,
          20.0.0.0/8, and 21.0.0.0/8 from PE0 with the BGP next-
          hop=1.1.1.1. Because PE11 received
          (bgpNH,pNH)=(1.1.1.1,1.1.1.2) from PE0, then PE11 knows that
          to protect traffic tunneled to PE0, it has to tunnel the
          traffic to 1.1.1.2 instead of 1.1.1.1

       b. PE11 receives an advertisement from PE1 for 10.0.0.0/8 and
          11.0.0.0/8 with the repair label 3100

       c. Hence PE11 picks PE1 as the rPE for the prefixes 10.0.0.0/8
          and 11.0.0.0/8 with rNH=9.9.9.1 and rL=3100. Remember that
          the vector label for 9.9.9.1 is 1100.

       d. Similarly, PE11 receives an advertisement from PE2 for
          20.0.0.0/8 and 21.0.0.0/8 with the repair label 3200

       e. Hence PE11 picks PE2 as the rPE for the prefixes 10.0.0.0/8
          and 11.0.0.0/8 with rNH=9.9.9.2 and rL=1200. Remember that
          the vector label for 9.9.9.1 is 1100.

   6.2. Forwarding Plane at Steady State (When PE0 is reachable)

   1. Ingress PE PE11

       a. Traffic for VRF "Blue"

           i. PE11 receives a packet for VRF Blue with destination
               address 10.1.1.1 from an external router.

Bashandy               Expires January 7, 2013                [Page 22]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

          ii. PE11 pushes the following labels

                 1. The VPN label 4100

                 2. The Repair label 3100

                 3. The vector label 1100

                 4. The LDP label for 1.1.1.2

       b. Traffic for VRF "Red"

           i. PE11 receives a packet for VRF Red with destination
               address 20.1.1.1 from an external router

          ii. PE11 pushes the following labels

                 1. The VPN label 4300

                 2. The Repair label 3200

                 3. The vector label 1200

                 4. The LDP label for 1.1.1.2

   2. Penultimate Hop of PE0 (Which is also the rP "P")

       a. Receives a packet with top label for the protected next-hop
          1.1.1.2

       b. Pops *3* labels

       c. Forwards the packet to 1.1.1.2

   3. Protected PE PE0

       a. Traffic for VRF "Blue"

           i. PE0 receives traffic with the top label 4100.

          ii. 4100 is the VPN label for VRF "Blue"

         iii. PE0 pops the label 4100 and forwards the packet to CE1

       b. Traffic for VRF "Red"

           i. PE0 receives traffic with the top label 4300.

          ii. 4300 is the VPN label for VRF "Red"

Bashandy               Expires January 7, 2013                [Page 23]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

         iii. PE0 pops the label 4300 and forwards the packet to CE2

   6.3. Forwarding Plane at Failure (When PE0 is not reachable)

   1. The ingress PE PE11

          Does not know about the failure yet and hence it does not
          change its behavior.

   2. Repair PE rP

       a. Traffic for VRF "Blue"

           i. Receives a packet with the top label being the LDP label
               for 1.1.1.2

          ii. 1.1.1.2 is not reachable

         iii. Pop the LDP label of 1.1.1.2. The vector label 1100 is
               under it

          iv. Lookup the vector 1100 in the label context of 1.1.1.2.
               The lookup yields the LDP label of the rNH 9.9.9.1

           v. Swap the vector label 1100 with the LDP label of the of
               9.9.9.1 and forward the packet towards PE1

       b.  Traffic for VRF "Red"

           i. Receives a packet with the top label being the LDP label
               for 1.1.1.2

          ii. 1.1.1.2 is not reachable

         iii. Pop the LDP label of 1.1.1.2. The vector label 1200 is
               under it

          iv. Lookup the vector 1200 in the label context of 1.1.1.2.
               The lookup yields the LDP label of the rNH 9.9.9.2

           v. Swap the vector label 1200 with the LDP label of the of
               9.9.9.2 and forward the packet towards PE2

   3. The repair Router "PE1"

       a. The penultimate hop of PE1 performs the usual penultimate hop
          popping



Bashandy               Expires January 7, 2013                [Page 24]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

       b. PE1 receives a packet with the top label equals the repair
          label 3100, which was allocated on per-CE basis and points to
          CE1

       c. PE1 pops *2* labels and forwards the packet to CE1

   4. The repair Router "PE2"

       a. The penultimate hop of PE2 performs the usual penultimate hop
          popping

       b. PE1 receives a packet with the top label equals the repair
          label 3200, which was allocated on per-CE basis and points to
          CE2

       c. PE2 pops *2* labels and forwards the packet to CE2

7. Security Considerations

   No additional security risk is introduced by using the mechanisms
   proposed in this document

8. IANA Considerations

   No requirements for IANA

9. Conclusions

   This document proposes a method that allows fast re-route
   protection against edge node failure or complete disconnected from
   the core in a BGP-free core. The method proposed has the following
   advantages

   o  Very scalable:

       o No router has to copy the routing table of another router

       o Minimum additional prefixes injected in the core. In fact, at
          most one additional prefix per pPE is injected and only if
          there is no spare IP address on the pPE

   o  Minimal provisioning overhead:

       o If there is a spare IP address on the pPE, then the
          provisioning effort is just enablement. If not, then the
          provisioning effort is just to configure a distinct IP address
          on each pPE to act as the pNH.



Bashandy               Expires January 7, 2013                [Page 25]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

       o Absolutely no restriction on which PE is connected to which
          VRF.

       o On a PE where BGP FRR is already configured, moving,
          connecting, or disconnecting a CE to/from the PE requires zero
          operator intervention to protect prefixes.

   o  Immunity to misconfigation: the only configuration that may be
      required is a distinct pNH on each pPE. The mapping (bgpnh,pPE)
      and (pNH,rNH,vL) is advertised to all BGP peers. If the operator
      configures the same pNH on two different pPE, then the
      misconfiguration will be detected almost immediately

   o  No Need for IP or TE FRR: Because the exit point of the repair
      tunnel from rP to rPE is different from the primary tunnel exit
      point

   o  Works in both MPLS core and IP core

   o  Works with per-CE, per-VRF and per-prefix label allocation

   o  Can be incrementally deployed. There is no flag day. Different
      routers can be upgraded at different times

   o  Zero impact on the paths taken by traffic: Enabling/deploying the
      feature described in this document has no effect on the paths
      taken by traffic at steady state



10. References

   10.1. Normative References

   [1]   Bradner, S., "Key words for use in RFCs to Indicate Requirement
         Levels", BCP 14, RFC 2119, March 1997.

   [2]   Rekhter, Y., Li, T., and S. Hares, "A Border Gateway Protocol 4
         (BGP-4), RFC 4271, January 2006

   [3]   Bates, T., Chandra, R., Katz, D., and Rekhter Y.,
         "Multiprotocol Extensions for BGP", RFC 4760, January 2007

   [4]   Malhotra, P. and Rosen, E., " The BGP Encapsulation Subsequent
         Address Family Identifier (SAFI) and the BGP Tunnel
         Encapsulation Attribute", RFC 5512, April 2009

   [5]   Lau, J., Ed., Townsley, M., Ed., and I. Goyret, Ed., "Layer Two
         Tunneling Protocol - Version 3 (L2TPv3)", RFC 3931, March 2005.

Bashandy               Expires January 7, 2013                [Page 26]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   [6]   Farinacci, D., Li, T., Hanks, S., Meyer, D., and P. Traina,
         "Generic Routing Encapsulation (GRE)", RFC 2784, March 2000.

   [7]   Perkins, C., "IP Encapsulation within IP", RFC 2003, October
         1996.

   10.2. Informative References

   [8]   Marques,P., Fernando, R., Chen, E, Mohapatra, P., Gredler, H.,
         "Advertisement of the best external route in BGP", draft-ietf-
         idr-best-external-04.txt, April 2011.

   [9]   Wu, J., Cui, Y., Metz, C., and E. Rosen, "Softwire Mesh
         Framework", RFC 5565, June 2009.

   [10]  Rosen, E. and Y. Rekhter, "BGP/MPLS IP Virtual Private Networks
         (VPNs)", RFC 4364, February 2006.

   [11]  De Clercq, J. , Ooms, D., Prevost, S., Le Faucheur, F.,
         "Connecting IPv6 Islands over IPv4 MPLS Using IPv6 Provider
         Edge Routers (6PE)", RFC 4798, February 2007

   [12]  Atlas, A. and A. Zinin, "Basic Specification for IP Fast
         Reroute: Loop-Free Alternates", RFC 5286, September 2008.

   [13]  Shand, S., and Bryant, S., "IP Fast Reroute", RFC5714, January
         2010

   [14]  Shand, M. and S. Bryant, "A Framework for Loop-Free
         Convergence", RFC 5715, January 2010.

   [15]  Bashandy, A., Pithawala, P., and Heitz, J., "Scalable, Loop-
         Free BGP FRR using Repair Label", draft-bashandy-idr-bgp-
         repair-label-02.txt", July 2011

   [16]  O. Bonaventure, C. Filsfils, and P. Francois. "Achieving sub-50
         milliseconds recovery upon bgp peering link failures," IEEE/ACM
         Transactions on Networking, 15(5):1123-1135, 2007

11. Acknowledgments

   Special thanks to Clarence Filsfils, Eric Rosen, Stewart Bryant,
   and Pradosh Malhotra for the valuable comments

   This document was prepared using 2-Word-v2.0.template.dot.





Bashandy               Expires January 7, 2013                [Page 27]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

Appendix A.                 Other Algorithms to Allocate and Disseminate Vector labels

   This section outlines two alternate algorithms for Allocating and
   distributing vector label "vL" to "rPE" mapping. The alternate
   algorithms can be divided into two categories, iPE chooses the repair
   path and pPE chooses the repair path

A.1. iPE chooses the repair path

A.1.1. Allocating Vector Labels using a Hash Function

   In the method of allocating and advertising vector labels outlined in
   Sections 2 and 3 each pPE allocates and binds a vector label to
   each known rPE. As a result, the same rPE may be bound to multiple
   vector labels by multiple pPEs and thus requiring additional storage
   on the rP. In this section, we propose a method by which a vector
   label is computed using a hash function based on the numerical value
   of rNH

A.1.1.1.1. Calculating and distributing the mapping rNH->vL to
different routers

   1. We assume that all routers in a BGP free core, including edge
      router, agree on the set of candidate repair next-hops. This can
      be achieved via default behavior (e.g. all host routes) or some
      sort of configuration, such as ISIS administrative tags

   2. No need for pPE to advertise the (pNH,rNH,vL) to iPE or rP

   3. Each candidate rP and iPE calculates the vL for each candidate
      repair next-hop rNH

   4. The rP inserts the calculated mapping vL-->rNH in a "repair label
      context" that is common for all protected PEs instead of having
      separate label context for each pPE.

   5. If iPE chooses rNH as the repair next-hop for traffic tunneled to
      pNH, iPE calculates the vL corresponding to the chosen rNH and
      pushes vL as described in Sections 2.1.

   6. On pPE failure, the lookup for vL occurs in the common "repair
      label context"

   IN the next subsections, we outline two risks of using the hash
   function for rNH-->vL mapping.





Bashandy               Expires January 7, 2013                [Page 28]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

A.1.1.1.2. Risk  of Mis-configuration leading to Mismatch in rNH-->vL
Mapping

   1. Due to misconfiguration, some routers may not have the identical
      sets of candidate repair next-hops "rNH's" or use the same hash
      function to calculate vL. For example, an upgraded router may have
      a new hash function enabled or the ISIS administrative tags may
      not be associated with all candidate rNHs

   2. To alleviate this risk, we propose that each rPE associates the
      calculated value of vL for each rNH in an optional TLV in IGP

   3. If a router finds that its calculated value for rNH-->vL is
      different from the value received from the corresponding rPE, then
      the router can raise an alarm,

A.1.1.1.3. Risk of forwarding to Incorrect VRF during convergence only

   Identical mapping of rNH-->vL is only guaranteed if the set of
   candidate rNH is the same on all routers. Because each router
   calculates rNH-->vL independently, there is a minor risk of
   forwarding to incorrect VRF. Consider the following example

   1. The risk exists even if every rPE advertises the vL of its own rNH

   2. Two rNH's, say rNH1 and rNH2, map to the same vL, even if rNH1,
      and rNH2 protect different prefixes

   3. rPE1 and rPE2 have not yet heard each other mappings

   4. iPE learns about vL-->rNH1 before vL-->rNH2

   5. rP/PLR learns about vL-->rNH2 before vL-->rNH1

   6. If pPE fails during the short period before iPE and rP can detect
      the vL collision, rP re-routes traffic to rNH2 but the repair
      label pushed by iPE is for rNH1.

A.1.2. pPE Allocates and advertises vL with protected prefixes

   1. pPE allocates a single vL for all prefixes reachable via the same
      CE. If two prefixes bound to the same vL are protected by
      different rPE's, then pPE MUST re-advertise the second protectable
      prefix with a different vL to all ingress PEs

   2. pPE always advertises (pNH, vL) with protected prefixes as
      optional attributes all the time even if there is no rPE



Bashandy               Expires January 7, 2013                [Page 29]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   3. iPEs and the pPE agree on the way to pick the rPE. E.g. if there
      are multiple rPEs, choose the one with lowest router ID

   4. When rPE advertises rL for a protected prefix

       a. Both pPE and iPE will get the update

       b. Both pPE and iPE will choose the same rPE for the protected
          prefix

   5. iPE associate the correct triplet (pNH, vL, rL) with protected
      prefixes without getting a re-advertisement for the prefix from
      pPE

   6. pPE Informs  about (pNH, rNH, vL)

   7. Hence rP/PLR knows that the vector label vL maps to rNH in the
      label context of pNH.

   8. rP/PLR inserts vL-->rNH  in the context of pNH

A.1.2.1.1. Risk of forward to Incorrect VRF during Convergence Only

   The conditions for the risk to exist

   o  More than one rNH, say rNH1 and rNH2, protect the same prefix

   o  iPE learns about rNH1 and has not yet learnt about rNH2

   o  pPE learns about rNH2 and has not yet learnt about rNH1

   o  pPE fails during this time period

   How incorrect forwarding can occur

   o  pPE maps vL to rPE2 on rP/PLR while iPE maps vL to rPE1

   o  pPE fails during this short period,

   o  rP/PLR re-routes the packet to rPE2 but the repair label pushed by
      iPE belongs to rPE1 (say rL1)



A.2. pPE chooses rPE and distributes the mapping of vL-->rNH

   In Sections 2, 3, and A.1 the ingress PE chooses the rPE for every
   protectable prefix. While it causes less churn because there is never
   a need to re-advertise protected prefixes, it is difficult to

Bashandy               Expires January 7, 2013                [Page 30]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

   configure a policy to control the choice of the rPE if the policy has
   to be applied to all iPEs. In this Section, we propose an algorithm
   to select rPE and advertise vL-->rNH via pPE instead of iPE

   1. pPE allocates a single vL for all prefixes reachable via the same
      CE

       a. We assume that prefixes reachable via the same CE or belong to
          the same VRF  are protectable by the same rPE

       b. If two prefixes bound to the same vL are protected by
          different rPE's, then pPE MUST re-advertise the second
          protectable prefix with a different vL to all ingress PEs

   2. pPE always advertises (pNH, vL) with protected prefixes as
      optional attributes all the time even if there is no rPE. Remember
      that pNH,vL) means the vector label for protected traffic tunneled
      to pNH is vL

   3. Based on rPE advertisement, pPE decides that the repair next-hop
      for a given protected prefix P/m is rNH. pPE sends the mapping
      (vL,rNH) similar to [4] as a separate advertisement to iPEs

   4. Suppose two prefixes prefixes P1/m1 and P2/m2 are associated with
      the same vector label vL1 but are protected by two different
      repair PEs: rNH1 and rNH2

       a. Re-advertise P2/m2 with a new vector label vL2

       b. pPE sends the mapping( vL1,rNH1) and (vL2,rNH) in a separate
          advertisement to iPEs

       c. The re-advertisement of the prefix p2/m2 with the new vector
          label vL2 must be done BEFORE sending the vector label mapping
          to guarantee correct forwarding

   Unlike the schemes in Sections A.1.1 and A.1.2 there is no risk of
   forwarding to incorrect VRF because pPE is the only source of mapping
   vL-->rNH

A.3. Combination of iPE and  pPE Choosing rPE

   o  pPE can choose the rPE by specifying the mapping of vL to rNH, re-
      advertising/advertising the protected prefix with rNH, or a
      combination of both

   o  pPE decides the prefixes for which it chooses the rPE based on
      various factors. For example


Bashandy               Expires January 7, 2013                [Page 31]

Internet-Draft       BGP FRR Using Vector Labels              July 2012

       o Option 1: The operator can configure the prefixes for which the
          pPE can choose the rPE.

       o Option 2: If there is more than one rPE, then pPE chooses the
          rPE. Otherwise, it is left to iPE

   o  There are probably other options

   o  As long as the pPE does not specify the rPE for a prefix, then the
      iPE is free to choose the rPE, otherwise, the iPE has to abide by
      pPE choice

   A combination of iPE and pPE choosing the rPE reduces the
   provisioning overhead when configuring a policy to choose the rPE at
   the expense of increasing the churn.





Authors' Addresses

   Ahmed Bashandy
   Cisco Systems
   170 West Tasman Dr, San Jose, CA 95134
   Email: bashandy@cisco.com

   Nagendra Kumar
   Cisco Systems
   170 West Tasman Dr, San Jose, CA 95134
   Email: naikumar@cisco.com

   Maciek Konstantynowicz
   Cisco Systems
   170 West Tasman Dr, San Jose, CA 95134
   Email: mkonstan@cisco.com














Bashandy               Expires January 7, 2013                [Page 32]