router-router NHRP (moderately long)

[Yakov Rekhter <[e-mail]>]

Folks,

Appended is a next iteration (still a rough draft) on the router-router
NHRP. I would greatly appreciate review and comments (especially on the 
things marked as "Discussion"). 

Yakov.

P.S. I also plan to send a separate note that outlines how the
mechanism described in this note could be used to establish
shortcuts that cross multiple routing domains.
------------------------------------cut here-----------------------------------

Router-to-router (R2R) NHRP


Abstract

This document describes a mechanism (called R2R NHRP) that allows to
acquire the information needed to construct a shortcut between a pair
of routers that are within a single routing domain.  If a path spans
multiple routing domains (all on a common NBMA network), then using the
mechanism described in this document the shortcuts could be established
within each such domain;  at the domain's boundary forwarding will be
provided via IP routers, so that the path across the NBMA network will
have more than one IP hop.

NHRP Target Information

The mechanism described in this document allows to establish a shortcut
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, and can not be modified by the routers
that forward the messages.

[Discussion: this is one of the differences with the existing NHRP.
Should the existing NHRP generalize its format to support NHRP target
?]

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 router can originate and/or 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 router 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 router can originate and/or 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.


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


Processing R2R 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.

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

[Discussion: perhaps an originator of a Request could specify whether
it is interested in discovered shortcuts that cross originator's domain
boundaries. If the originator is only interested in getting the
shortcut information within its local routing domain, then a border
router in the domain always sends back a Reply and terminates the
query.]

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.

Domain-specific rules

The following sections describes rules specific to particular routing
domains (e.g., RIP domain, OSPF domain).

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.

[Discussion: it is not clear what is the value of updating NLRI in the
NHRP route information.]

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

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

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.


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


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. 

[Discussion: To speed up convergence Purges should be made reliable 
for the router-router case.]

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.

[Discussion: keepalives could be send directly to the other end of a
shortcut (using IP routing). This is somewhat different with the
general idea of NHRP that NHRP packets are handled on a hop-by-hop
basis. Of course, keepalives could be sent on a hop-by-hop basis as
well, but this would not offer any advantages. An alternative is to use
NHRP Request as a keepalive mechanism. This would put more load on the
routers along the shortcut, but would allow faster convergence.]

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