[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
Internetworking Over NBMA                                  Yakov Rekhter
INTERNET-DRAFT                                             Cisco Systems
<draft-halpern-ion-r2r-nhrp-00.txt>                         Joel Halpern
Expiration Date: December 1998                  Newbridge Networks, Inc.
                                                               June 1998


             NHRP for Destinations off the NBMA Subnetwork

                   draft-halpern-ion-r2r-nhrp-00.txt


1. Status of this Memo

   This document is an Internet-Draft.  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.''

   To learn the current status of any Internet-Draft, please check the
   ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow
   Directories on ftp.is.co.za (Africa), nic.nordu.net (Europe),
   munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or
   ftp.isi.edu (US West Coast).


2. Abstract

   The NBMA Next Hop Resolution Protocol (NHRP) [1] specifies a
   mechanism that allows a source station (e.g., a host or a router) on
   an NBMA subnetwork to find the NBMA subnetwork address address of a
   destination station when the destination station is connected to the
   NBMA subnetwork. For the case where the destination station is off
   the NBMA subnetwork the mechanism described in [1] allows to
   determine the NBMA subnetwork address of an egress router from the
   NBMA subnetwork that is ``nearest'' to the destination station.  If
   used to locate an egress router wherein the destination station is
   directly behind the egress router, the currently document NHRP
   behaviors are sufficient.  However, as documented elsewhere [2],
   there are cases where if used between routers for generalized
   transit, NHRP can produce loops.

   This document describes extensions to the NBMA Next Hop Resolution



Joel Halpern                                                    [Page 1]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


   Protocol (NHRP) [1] that allow to acquire and maintain the
   information about the egress router without constraining the
   destination(s) to be directly connected to the egress router.


3. CONVENTIONS

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


4. NHRP Target Information

   The mechanism described in this document allows to find an egress
   router for either a single destination, or a set of destinations
   (where the set is expressed as a single address prefix). Since a
   single destination is just a special case of a set of destinations,
   for the rest of the document we will always talk about a set of
   destinations, and will refer to this set as an ``NHRP target''.

   The NHRP target is carried in the NHRP Request,  Reply, and Purge
   messages as an address prefix (using the Destination Prefix Length
   extension). In order to ensure correctness, a target may be replaced
   by an identical target with a longer prefix length.  Other than this
   increase of prefix length, no NHS shall modify the NHRP target
   information in an NHRP message.

   In general a router may maintain in its Forwarding Information Bas
   (FIB) routes whose Network Layer Reachability Information (NLRI) that
   exhibits a subset relation. Such routes are called overlapping
   routes.  To provide correct forwarding in the presence of overlapping
   routes this document constrains an NHRP target by requiring that all
   the destinations covered by the target must form a subset of the NLRI
   of at least one route in the Forwarding Information Base (FIB) of the
   router that either originates, or propagates an NHRP Request. For the
   rest of the document we'll refer to this as the ``first NHRP target
   constraint''.  A station can originate an NHRP Request, and a router
   can propagate an NHRP Request only if the NHRP target of the Request
   does not violate the first NHRP target constraint.

   If a received NHRP request does not meet this ``first NHRP target
   constrant'' when received, the receiving router has two choices.  It
   may answer the request, defining itself as the egress.  This is
   compatible with the base NHRP specification, and preserves the
   ``first NHRP target constraint''.  Alternatively, the router may
   lengthen the received prefix until the first constraint is met.




Joel Halpern                                                    [Page 2]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


   A route (from a local FIB) whose NLRI forms a minimal superset of all
   the destinations covered by the NHRP target is called an ``NHRP
   forwarding route''. Observe, that by definition the set of
   destinations covered by an NHRP target always exhibits a subset
   relation to the set of destinations covered by the NHRP forwarding
   route associated with the target.

   This document further constrains origination/propagation of NHRP
   Requests by prohibiting the NHRP target (carried by a Request) to
   form a superset of the destinations covered by any of the routes in
   the local FIB.  The constraint applies both to the station that
   originates an NHRP Request and to the routers that propagate the
   Request. For the rest of the document we'll refer to this constraint
   as the ``second NHRP target constraint''. A station can originate an
   NHRP Request, and a router can propagate an NHRP Request only if the
   NHRP target of the Request does not violate the second NHRP target
   constraint. The second NHRP target constraint guarantees that
   forwarding to all the destinations covered by the NHRP target would
   be accomplished via a single (common) route, and this route would be
   nothing, but the NHRP forwarding route for the target.

   Again, if a received NHRP request does not meet the ``second NHRP
   target constraint'', the router may either respond to the request,
   providing its own NBMA address, or it may lengthen the prefix in the
   request so as to meet the second constraint.


5. NHRP Requester and Terminator Processing

   The issue being addressed with the behaviors being mandated in this
   document is to ensure that sufficient information is present and
   processed to avoid NHRP shortcuts causing packet forwarding loops.

   In order to do this, the requester and responder of the request must
   undertake certain work, and any "border routers" in the forwarding
   path must also perform certain work.

   The work performed by the requester and responder consists of two
   kinds of work.  One set is requester only work, and is required in
   order to determine where the protocol boundaries are.  The other set
   is the route monitoring work.










Joel Halpern                                                    [Page 3]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


5.1. NHRP IGP information

   The primary cause of NHRP forwarding loops is the loss of information
   at a routing protocol boundary.  Normally, such boundaries are
   detected by the router at the boundary.  However, it is possible for
   IGP boundaries to overlap.  Therefore, NHRP requesting Routers MUST
   include the NHRP IGP Identifier extension.  This extension indicates
   what IGP the originator of the request uses.  This extension must
   always be included by a requesting router, since it is not possible
   to tell a priori whether the eventual resolution of the request will
   be a host or a router.

   Because the entire BGP domain is consider one routing domain, the
   extension also contains an indication as to whether the originator
   was a BGP speaker.


5.2. NHRP Requestor and Responder monitoring

   NHRP requestors and responders are required monitor routing to
   mainting correct shortcut information.

   Once a router that originates an NHRP Request acquires the shortcut
   next hop information, it is essential for the router to be able to
   detect any changes that would affect the correctness of this
   information. The following measures are intended to provide the
   correctness.

   Both ends of a shortcut have to monitor the status of the route that
   was associated with the shortcut (the NHRP forwarding route). If the
   status changes at the router that generate the NHRP Reply, this
   router should send a Purge message, so that the NHRP Requester would
   issue another NHRP. If the status changes at the Requester, the
   Requester must issue another NHRP. This allows to ensure that when
   both end of a shortcut are up, any changes in routing that impact
   forwarding to any of the destination in the NHRP target would result
   in a revalidation (via NHRP) of the shortcut.  Note that in addition
   to sending purges/reverifies in response to routing changes which
   directly effect the NHRP target, there is one other case.

   A router MUST perform the appropriate purge/reverification process if
   it receives routing updates which case an issued NHRP request to
   violate either of the the target constraints defined earlier.  This
   is possible at an NHRP originator, and is more likely at border
   devices.

   Once a shortcut is established, the Requester needs to have some
   mechanism(s) to ensure that the other end of the shortcut is alive.



Joel Halpern                                                    [Page 4]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


   Among the possible mechanisms are: (a) indications from the Data Link
   layer, (b) presence of traffic in the reverse direction that comes
   with the Link Layer address of the other end, (c) keepalives sent by
   the other end. This is intended to suppress black holes, when the
   next hop router in the shortcut (the router that generated Reply)
   goes down.

   A requester should establish a shortcut only after the requester
   determines that the information provided by NHRP is fairly stable.
   This is necessary in order to avoid initiating shortcuts that are
   based on transients routing information, and thus would need to be
   revalidated almost immediately anyway.

   [Discussion: Should a router forward an NHRP Request based on a route
   that is in a transient (e.g., holddown) state, or should the Request
   be discarded ?]

   [Discussion: what are the criteria to determine whether the
   information provided by NHRP is "fairly stable" ?]



6. Border Processing of NHRP Request

   Processing of an NHRP Request is covered by two sets of rules: the
   first set for IGP related processing, and the second set for BGP
   related processing.  The rules for IGP processing relate to
   determining where the IGP borders are (in particular in the case of
   overlapping IGPs), and then for what must happen at said borders.


6.1. Border Determination

   When a router receives a request, and determines  that it is not the
   NBMA exit router, it must perform a seris of checks before forwarding
   the request.

   When a router receives such a Request, the router uses the NHRP
   target and the NHRP IGP information  to check whether  (a) the first
   and the second NHRP target constraints are satisfied, (b) the router
   it is in the same routing domain as the originator of the Request,
   and if yes, then whether (c) it is a border router for that domain.

   When the NHRP target is checked against the forwarding database, a
   determination must be made as to whether either of the target
   constraints have been violated.  If they are violated, then the
   router MAY either




Joel Halpern                                                    [Page 5]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


         o Extend the prefix so as to meet the constraints.

         o replay to the request indicating that it is the destination

         o return an error indicating which constraint was violated.

   If the NHRP forwarding route indicates next hop that is not on the
   same NBMA as the interface on which the Request was received, the
   router sends back an NHRP Reply and terminates the query.

   If a router receives a request without IGP information, then it was
   originated within this domain by a host.  If the router is an AS
   Border Router (ie running BGP), and if the forwarding path exits the
   AS, then it must behave as a border router for this request.
   Otherwise, for requests without IGP information, the router is not a
   border router.

   For requests with IGP information, the router compares the forwarding
   information against the IGP in the request.  If the forwarding entry
   indicates that the next hop is to exit the AS (an AS Border Router),
   then check the BGP behaviors below.

   When the IGP the next hop was learned from is the same IGP as
   indicated in the request, then the NHS simply forwards the request.
   [Of course, as per NHRP, it is free to respond indicating it is the
   termination of the shortcut, for example when the Router/NHS is a
   firewall.]

   When the IGP the next hop was learned fromis different from that
   listed in the NHRP request, then this NHS is a border router for this
   request.


6.2. Border Behavior

   In all cases, a border router has two choices.  It MAY terminate and
   respond to the request, responding with its IP and NBMA address.

   Alternatively, it MAY perform border propagation.


6.2.1. Reorigination

   Open receiving an NHRP request for which the NHS is a border router,
   if it chooses to propogate the request, it MUST originate a new NHRP
   request.  This request will have a locally generated request
   identifier, and the same NHRP target information as in the received
   request.  The NHRP IGP Information will be the correct indication for



Joel Halpern                                                    [Page 6]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


   the outgoing interface, with BGP indication if the received request
   had the BGP indication, or if this transition crosses the AS border.
   All other extensions are copied from the incoming request to the new
   request.


6.2.2. Response Propagation

   When an NHRP response is received for a propagated request, the
   information is copies from the received request, and passed on in a
   new NHRP response, responding to the originally received request.
   The prefix length in the received response is copied to the new
   response.  All extensions except the NHRP IGP Information are copied
   to the new response.

   In addition, the border router saves state about this information
   exchange.  The saved state includes the NHRP target from the
   response, with the NHRP prefix length that resulted from the
   exchange.  It also includes the both the original requester, and the
   identity of the responder.  These are used to generate appropriate
   reverification and purges whenever routing changes in a way that
   could effect the resolution.


6.3. Border Information

   Somtimes the routing protocol will have provided the border router
   with enough information to generate a response to an incoming NHRP
   request.  In particular, the border router may have information about
   IP prefix to NBMA address bindings.  If such information is present,
   it may be used by a border router to produce an NHRP response without
   actually propagating the request.  In such a case, that information
   must be monitorred for stability to maintain the correctness of the
   shortcut.


7. BGP Operation

   While the NHRP mechanism described above is mostly constrained to the
   routers within a single routing domain, the same mechanisms can be
   used for shortcuts taht span multiple domains.  In doing so, one
   wants to produce as little additional overhead in the BGP space as
   possible.

   Therefore, we will treat the space over which BGP runs as a single
   routing domain.  Care must be taken to propagate information across
   the individual AS without error, and to indicate that one has
   properly entered the BGP space.



Joel Halpern                                                    [Page 7]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


   Additional complexity in handling multi-domains shortcuts arise if
   routing information gets aggregated at the border routers (which
   certainly happens in practice). Since BGP is the major protocol that
   is used to exchange routing information across multiple routing
   domains, we'll restrict our proposal to the case where the routing
   information exchange across domains' boundaries is controlled by BGP.

   If both the source and the destination domains are on a common NBMA
   network, and the path between these two domains is also fully within
   the same NBMA network, then we have only three routing domains to
   deal with: source routing domain, BGP routing domain, and destination
   routing domain. If the destination domain is not on the same NBMA as
   the source domain, then we need to deal only with two domains - the
   source and the BGP. Note that we treat all routers that participate
   in a single (common) instance of BGP as a single BGP routing domain,
   even if these routers participate in different intra-domain routing
   protocols, or in different instances of the same intra-domain routing
   protocol.


         (a) how a border router in the domain that the originator of
               the Request is in handles the Request (crossing IGP/BGP
               boundary),

         (b) how the Request is handled across the BGP domain, and
               finally

         (c) how a border router in the domain where the NHRP target is
               in handles the Request (crossing BGP/IGP boundary).



7.1. Handling NHRP Request at the source domain border router

   When a border router receives an NHRP Request originated from within
   its own (IGP) routing domain, the border router determines the NHRP
   forwarding route for the NHRP target carried by the Request. If the
   router already has the shortcut information for the forwarding route,
   then the router uses this information to construct a Reply to the
   source of the NHRP Request.  Otherwise, the router originates its own
   NHRP Request.  The Request contains exactly the same NHRP target, as
   was carried by the original Request;  The NHRP IGP Information will
   indicate that the request was generated by BGP, and will indicate the
   IGP of the BGP AS being entered.  While it is assumed that a BGP
   transit AS will generally use only one IGP, the IGP information (and
   border processing) is included to allow all cases. The newly
   originated Request is sent to the next hop of the NHRP forwarding
   route. Once the border router receives a Reply to its own Request,



Joel Halpern                                                    [Page 8]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


   the border router uses the next hop information from the Reply to
   construct its own Reply to the source of the original NHRP Request.

   If the border router later on receives a Purge message for the NHRP
   forwarding route, the border router treats this event as if there was
   a local change in the NHRP forwarding route (even if the there was no
   changes in the route).

   This is exactly the same behavior as all other border cases, and is
   described here for completeness.


7.2. Handling NHRP Request within the BGP domain

   Routers within an AS will check the IGP, and perform appropriate
   processing based on the IGP match.  In general, this will result in
   normal forwarding of the NHRP request.

   Therefore, the significant cases occur at the BGP speaking routers.
   There are two conditions to check for, early exit of the NBMA, and
   reachability aggregation.  Both of these conditions appply to
   Automnomous systems which do not contain the NHRP target.


7.2.1. NBMA exit

   The BGP router in deciding where to send the NHRP request will
   determine what the correct exit from the autonomous system is.  It
   will determine if that exit is within the NBMA.  If it is not within
   the NBMA, then the router MUST respond to the NHRP request,
   indicating its own IP and NBMA addresses as the correct termination
   of the shortcut.  This is because the actual NBMA border device is
   not in a position to monitor the topology properly.

   [Discussion:  Should we also have an error from the border router
   inside the AS, in case the BGP router can not make this
   determination?]


7.2.2. Reachability Aggregation

   BGP routers aggregate reachability.  If the router aggregates
   reachability that includes the NHRP target, only this router has the
   visibility to some of the topology changes that can affect the
   correctness of the route.  Therefore, this router is a border router
   for this NHRP request.

   It must originate a new request, place the correct information in the



Joel Halpern                                                    [Page 9]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


   request, reeceive the response, and generate the correct response
   towards the requester.  This aggregating router must also monitor
   routing in case of changes which affect the request.

   If the router later on receives a Purge message for the NHRP
   forwarding route, the router treats this event as if there was a
   change in the NHRP forwarding route (even if the there was no changes
   in the route).

   It should be noted that this conditions applies if the router COULD
   aggregate relevant routing information, even if it currently does
   not.



7.3. Handling NHRP Request at the destination domain border router

   When a border router receives an NHRP Request from a BGP speaker, and
   the border router determines that all the destinations covered by the
   NHRP target of the Request are within the (IGP) domain of that border
   router, the border router determines the NHRP forwarding route for
   the NHRP target carried by the Request. The newly formed Request
   contains exactly the same NHRP target as the received Request; the
   NHRP IGP Information indicates the IGP this router is using to select
   the route to the destination.  The newly originated Request is sent
   to the next hop of the NHRP forwarding route. Once the border router
   receives a Reply to its own Request, the border router uses the next
   hop information from the Reply to construct its own Reply to the
   source of the original NHRP Request.

   If the border router later on receives a Purge message for the NHRP
   forwarding route, the border router treats this event as if there was
   a change in the NHRP forwarding route (even if the there was no
   changes in the route).


8. More state, less messages

   It should be possible to reduce the number of Purge messages and
   subsequent NHRP messages (caused by the Purge messages) by
   maintaining more state on the border routers at the source and
   destination domains, and the BGP routers that perform aggregation
   along the path from the source to the destination.

   Specifically, on these routers it would be necessary to keep the
   information about all the NHRP targets for which the routers maintain
   the shortcut information.  This way when such a router determines
   that the NHRP forwarding route (for which the router maintains the



Joel Halpern                                                   [Page 10]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


   shortcut information) changes due to some local routing changes, the
   router could check whether these local changes impact forwarding to
   the destinations covered by the NHRP targets.  Only for the targets
   that are impacted by the changes the router would send Purge
   messages.

   Note that this mechanism (maintaining NHRP targets) precludes the use
   of Address Prefix Extension - the shortcut will be determined only
   for the destinations covered by the NHRP target (so, if the target is
   a single IP address, then the shortcut would be determined only for
   this address).


9. NHRP IGP Information Extension Format

         0                   1                   2                   3
         0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   0-3  |C|u|        Type = 9           |        Length = 4             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   4-7  |  flags      |b| Reserved      |        IGP ID                 |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


         C "Compulsory." If clear, and the NHS does not recognize the
               type code, the extension mayb safely be ignored.  For the
               IGP Information extension, this bit is clear.

               [Discussion.  There is a deployment tradeoff against
               robustness in the setting of the C bit.]

         u Unused and must be set to zero

         Type The extension type code.  For the IGP Information
               extension, this is 9.

         Length the length in octets of the value.  For this extension,
               this is 4.

         flags Other than the "b" flag, these are reserved, SHALL be set
               to 0 on transmission, and SHALL be ignored on reception.

         b This flag indicates whether the request (or a predecessor
               thereof) was originated by a BGP speaker.  Set (to 1) to
               indicate that the BGP speaker has operated on this.
               Clear (to 0) if not.

         IGP ID This field indicates the IGP used by the request



Joel Halpern                                                   [Page 11]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


               originator.  The currently defined values are:

                                    1 = RIP
                                    2 = RIPv2
                                    3 = OSPF
                                    4 = Dual IS-IS



10. Open issues

   The mechanisms described in this document assume that certain routers
   along a path taken by an NHRP Request would be required to maintain
   state associated with the NHRP forwarding route associated with the
   NHRP target carried by the Request. However, it is quite clear that
   the router(s) may also lose this state. Further study of the impact
   of losing the state is needed before advancing the use of NHRP for
   establishing shortcuts among routers.

   The mechanisms described in this document may result in a situation
   where a router would be required to maintain NHRP peering with
   potentially a fairly large number of other routers. Further study is
   needed to understand the implications of this on the scalability of
   the approach where NHRP is used to establish shortcuts among routers.

   This document doesn't have a proof that the mechanisms described here
   result in loop-free steady state forwarding when NHRP is used to
   establish shortcuts among routers.


11. Security Considerations

   Security is provided in the base NHRP protocol, using hop-by-hop
   authentication.  There is no change to the fundemental security
   capabilities provided therein when these extensions are used.  It
   should be noted that the assumption of transitive trust which is the
   basis of such security may well be significantly weaker in an inter-
   domain environment, and administrators of border routers should take
   this into consideration.












Joel Halpern                                                   [Page 12]


Internet Draft     draft-halpern-ion-r2r-nhtp-00.txt           June 1998


12. References

   [1]  J. Luciani, D. Katz, D. Piscitello, B. Cole, N. Doraswamy.,
   "NBMA Next Hop Resolution Protocol", RFC-2332, USC/Information
   Sciences Institute, April 1998.

   [2] D. Cansever., "NHRP Protocol Applicability Statement", RFC-2333,
   USC/Information Sciences Institute, April 1998

   [3] S. Bradner., "Key words for use in RFCs to Indicate Requirement
   Levels", RFC-2119, USC/Information Sciences Institute, March 1997.


13. Acknowledgements

   To be supplied.


14. Author Information

   Joel M. Halpern
   Newbridge Networks Inc.
   593 Herndon Parkway
   Herndon, VA 20170
   Phone: (703) 736-5954
   email: jhalpern@newbridge.com

   Yakov Rekhter
   cisco Systems, Inc.
   170 Tasman Dr.
   San Jose, CA 95134
   Phone: (914) 528-0090
   email: yakov@cisco.com


















Joel Halpern                                                   [Page 13]