Network Working Group Yakov Rekhter
Internet Draft Cisco Systems
Expiration Date: August 1997 February 1997
NHRP for Destinations off the NBMA Subnetwork
draft-ietf-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) [NHRP] 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 [NHRP] allows to
determine the NBMA subnetwork address of an egress router from the
NBMA subnetwork that is ``nearest'' to the destination station.
However, the ability of determining the egress router is constrained
to the destinations that are directly connected to the egress router.
This document describes extensions to the NBMA Next Hop Resolution
Protocol (NHRP) [NHRP] 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.
Yakov Rekhter [Page 1]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
3. 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). This document requires that the NHRP target shall not be
modified by the routers that forward the messages.
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.
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.
Yakov Rekhter [Page 2]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
4. NHRP Route Information
To allow routers along a path to unambiguously determine routing
domain boundaries, and to provide correct next hop information, the
NHRP Request carries the NHRP route information. The NHRP route
information is generated by the router that originates an NHRP
Request, but could be modified by the routers that forward the
Request.
The NHRP route information consists of two components, protocol
independent and protocol specific. The protocol independent
component consists of NLRI and the protocol type of the NHRP
forwarding route associated with the NHRP target. For RIP, OSPF, and
Dual IS-IS the protocol specific component is empty. For RIP-2 the
protocol specific component contains the Route Tag of the route.
Definition of the protocol specific component for other routing
protocols is outside the scope of this document.
[Discussion: it is not clear how much value is in carrying (and
updating) the NLRI information (as part of the NHRP route
information) for such protocols as RIP, OSPF, and Dual IS-IS.]
5. Processing NHRP Request
Processing of an NHRP Request is covered by two sets of rules: the
first set is independent of a particular routing domain, the second
set is specific to a particular routing domains.
5.1. Domain-independent rules
When a router receives a Request, the router uses the NHRP target
and the NHRP route 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.
If the first NHRP target constraint is violated, the router reports
an error to the originator of the Request and terminates the query.
If the second NHRP target constraint is violated, then the router
sends back an NHRP Reply and terminates the query. The Reply should
indicate that the second NHRP target constraint was violated. The
Reply contains IP and NBMA addresses of the router.
If the NHRP forwarding route indicates next hop that is not on the
Yakov Rekhter [Page 3]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
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 that is not annotated with the border
router information, then the router is either within the routing
domain that the originator of the Request is in, or is a border
router for that domain. In this case the router uses domain-specific
rules (see below) to determine whether it is a border router for the
routing domain that the originator of the request is in, or whether
it is just an internal router within the domain.
If the router is a border router for the routing domain that the
originator of the Request is in, then the router can either (a)
annotate the request with the IP and NBMA addresses associated with
the NHRP forwarding route for the NHRP target carried by the Request
and forward the Request (outside the domain), or (b) send back an
NHRP Reply (and thus terminate the query). The Reply contains the IP
and NBMA addresses associated with the NHRP forwarding route for the
NHRP target carried by the Request. The choice between (a) and (b)
is a local to the router matter.
If a router receives a Request that is annotated with the border
router information, then the originator of the Request and the router
are in different routing domains. In this case the router uses only
the NHRP target information to handle the Request.
5.2. Domain-specific rules
The following sections describes rules specific to particular routing
domains (e.g., RIP domain, OSPF domain).
5.2.1. RIP Domain
When a router receives a Request, such that (a) the NHRP route
information indicates RIP, (b) the router determines (using the
domain-independent rules) that it is in the same domain as the
originator of the Request, and (c) the domain-independent rules do
not require the router to terminate the query, the router checks if
the NHRP forwarding route is a RIP-learned route.
If it is a RIP-learned route, then the router replaces NLRI in the
NHRP route information of the Request with the NLRI of the NHRP
forwarding route, and forwards the Request to the next hop specified
by the route. Otherwise, the router and the originator of the
Request are in the same routing domain, and the router is a border
router for that domain.
Yakov Rekhter [Page 4]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
[Discussion: it is not clear what is the value of updating NLRI in
the NHRP route information.]
5.2.2. RIP-2 Domain
When a router receives a Request, such that (a) the NHRP route
information indicates RIP-2, (b) the router determines (using the
domain-independent rules) that it is in the same domain as the
originator of the Request, and (c) the domain-independent rules do
not require the router to terminate the query, the router checks if
the NHRP forwarding route is a RIP-2-learned route.
If it is a RIP-2-learned route, and the Route Tag of the route is the
same as the one carried in the NHRP route information of the Request,
then the router replaces the NLRI information in the NHRP route
information of the Request with NLRI of the NHRP forwarding route,
and forwards the Request to the next hop specified by the route.
Otherwise, the router and the originator of the Request are in the
same routing domain, and the router is a border router for that
domain.
[Discussion: it is not clear what is the value of updating NLRI in
the NHRP route information.]
5.2.3. OSPF Domain
When a router receives a Request, such that (a) the NHRP route
information indicates OSPF, (b) the router determines (using the
domain-independent rules) that it is in the same domain as the
originator of the Request, and (c) the domain-independent rules do
not require the router to terminate the query, the router checks if
the NHRP forwarding route is an OSPF-learned route.
If the route is an OSPF-learned route, but the router is neither an
Area Border Router (ABR), nor AS Boundary Router (ASBR), the router
forwards the Request to the next hop specified by the NHRP forwarding
route.
If the route is an OSPF-learned route, and the router is an ABR, then
the router replaces NLRI in the NHRP route information of the Request
with NLRI of the NHRP forwarding route, and forwards the Request to
the next hop specified by the route.
[Discussion: it is not clear what is the value of updating NLRI in
the NHRP route information.]
Yakov Rekhter [Page 5]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
If the route is not an OSPF-learned route, and the router is an ASBR,
then the router and the originator of the Request are in the same
routing domain, and the router is a border router for that domain.
If the route is not an OSPF-learned route, and the router is not an
ASBR, then the router indicates an error.
5.2.4. Dual IS-IS Domain
When a router receives a Request, such that (a) the NHRP route
information indicates Dual IS-IS, (b) the router determines (using
the domain-independent rules) that it is in the same domain as the
originator of the Request, and (c) the domain-independent rules do
not require the router to terminate the query, the router checks if
the NHRP forwarding route is a Dual IS-IS-learned route.
If the route is a Dual IS-IS-learned route, and the router is not a
L2 router, the router forwards the Request to the next hop specified
by the route.
If the route is not a Dual IS-IS-learned route, and the router is a
L2 router, then the router and the originator of the Request are in
the same routing domain, and the router is a border router for that
domain.
If the route is a Dual IS-IS-learned route, and the router is a L2
router, then the router replaces the NLRI information in the NHRP
route information of the Request with the NLRI of the NHRP forwarding
route, and forwards the Request to the next hop specified by the
route.
[Discussion: it is not clear what is the value of updating NLRI in
the NHRP route information.]
Yakov Rekhter [Page 6]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
6. Maintaining 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.
Once a shortcut is established, the Requester needs to have some
mechanism(s) to ensure that the other end of the shortcut is alive.
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" ?]
Yakov Rekhter [Page 7]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
7. Extensions to multi-domains shortcuts
While the NHRP mechanism described above is mostly constrained to the
routers within a single routing domain, in certain situations the
information provided by this mechanism could be sufficient to
establish shortcuts that would span multiple domains.
Consider an example where an NHRP Request was originated within a
particular routing domain A, and the NHRP target of the Request is in
some other routing domain B. Further assume that the border routers
in both A and B participate in a single common instance of BGP. Since
BGP preserves the next hop information across an NBMA network, the
routing information available at the border routers in A would
contain the next hop IP information that may be in some other routing
domain along the path to B, perhaps even in B itself. Therefore, when
a border router in A receives the Request, the router would annotate
the Request with the next hop information that is associated with a
router in some other routing domain, thus providing the information
needed to establish a shortcut that spans multiple routing domains.
[Discussion: BGP preserves the next hop IP information, but does not
carry NBMA address information. The NBMA address information could be
either added to BGP (as another attribute), or NHRP could be used to
resolve IP address to NBMA address mapping.]
[The following could be viewed as controversial. More discussion is
needed.]
While the ability of BGP to preserve the next hop information could
reduce the number of IP hops along a path, the information, by
itself, may not be sufficient to form a single IP hop across an NBMA
network. However, we could observe that once a router (e.g., a
border router) acquires a shortcut information, then as long as the
router has sufficient assurances that the information is correct, the
router could pass this information to other routers in response to
NHRP Requests. Since a border router (by definition) belongs to
multiple routing domains, passing the information through the border
router from one domain to another would be sufficient for
establishing shortcuts that span multiple routing domains.
For example, assume that a border router X within a given domain A
acquired the information needed to form a shortcut within A for a
given NHRP target (the target may be either within A or outside of
A). Further assume that X is also in some other routing domain B,
and there is a router Y in B that would like to acquire the shortcut
information for exactly the same NHRP target. If the NHRP Request
originated by Y would reach X, then when X receives the Request
rather than indicating itself as the next hop, X would use the
Yakov Rekhter [Page 8]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
shortcut information it already has to specify the next hop in the
Reply. Thus Y would have the information to construct a shortcut that
crosses domain's boundary.
If X would detect any changes in the information associated with the
shortcut (either due to local changes, or as a result of receiving a
Purge message), then X would reissue the NHRP Request, and also would
send a Purge message to Y. When Y would receive the Purge message
from X, Y would reissue the NHRP Request as well.
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.
To simplify the presentation we decompose the problem into the
following three subproblems:
(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).
Yakov Rekhter [Page 9]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
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 route information
contains NLRI and the protocol (BGP) of the NHRP forwarding route.
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 local change in the NHRP forwarding route (even if the there was no
changes in the route).
7.2. Handling NHRP Request within the BGP domain
When a BGP router (e.g., a border router at the source domain)
originates an NHRP Request, this Request would be sent to a router
that is either
(a) an egress router from an NBMA network (since in the absence
of aggregation BGP preserves the next hop information),
or
(b) a border router within the domain that contains all the
destinations carried by the NHRP target, or
(c) a router that aggregates NLRI carried by the NHRP route
information of the Request.
With case (a) when the router receives the Request the router sends
back an NHRP Reply and terminates the query. Case (b) is handled as
described in the next section.
With case (c) when the router receives the Request, the router
determines the NHRP forwarding route for the NHRP target carried by
the Request and originates its own NHRP Request. The Request
contains exactly the same NHRP target, as was carried by the original
Yakov Rekhter [Page 10]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
request; the NHRP route information contains NLRI and the protocol
(BGP) of the NHRP forwarding route. The newly originated Request is
sent to the next hop of the NHRP forwarding route. Once the router
receives a Reply to its own Request, the router uses the next hop
information from the Reply to construct its own Reply to the source
of the original NHRP 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).
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 route information contains NLRI and the protocol of the NHRP
forwarding route. 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).
[Discussion: it is not clear what are the merits of carrying and
updating NLRI in the NHRP route information.]
Yakov Rekhter [Page 11]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
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
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. Open issues
During routing transients it is quite possible that neither the
router that originates an NHRP Request for a particular NHRP target,
nor the router that terminates this Request (and sends back an NHRP
Reply) would experience any changes in the NHRP forwarding route
associated with the NHRP target. However, this may not be true for
the routers along the path that the NHRP Request would traverse. It
is not clear whether this could lead to a formation of a persistent
forwarding loop, even in the presence of the mechanisms described
above. Further study of this issue is needed before advancing the use
of NHRP for establishing shortcuts among routers.
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
Yakov Rekhter [Page 12]
Internet Draft draft-ietf-ion-r2r-nhrp-00.txt February 1997
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.
10. Security Considerations
To be supplied
11. References
To be supplied.
12. Acknowledgements
To be supplied.
13. Author Information
Yakov Rekhter
cisco Systems, Inc.
170 Tasman Dr.
San Jose, CA 95134
Phone: (914) 528-0090
email: yakov@cisco.com
Yakov Rekhter [Page 13]
