NHRP for the router-to-router case (fairly long message)

[Yakov Rekhter <[e-mail]>]

Folks,

Appended is a draft from myself and Bruce Cole that looks at several design 
alternatives for the NHRP in the router-to-router case.
Please comment.

Thanks.

Yakov&Bruce.
--------------------------------------------------------------------


Alternatives for Router-to-Router NHRP
--------------------------------------


Abstract

This document presents  and examines several design alternatives for
the Next Hop Resolution Protocol (NHRP), where the protocol is applied
to the environment where both the NHRP Requestor and Responder are
routers (both source and destination are off an NBMA network). The list
of alternative is by no means exhaustive - it is quite plausible that
other alternatives (or some variations on the alternatives described
here) should be possible.


Problem Statement

When a path from a source to a destination traverses an NBMA network,
the segment of the path through the NBMA network may include more than
two (ingress and egress) routers. The primary design objective of NHRP
is to minimize the number of routers within the segment (preferably to
just two -- ingress and egress). A feasible solution, by definition,
must provide a steady-state loop free forwarding. We refer to a path
that forms a feasible solution as a "valid path".

Due to changes in network topology a valid path may become invalid
later on.  When an ingress router discovers (via NHRP) an egress router
(for a particular destination), the minimized path (directly from the
ingress to the egress router) is guaranteed to be valid only at the
time when the path was discovered. Subsequently, the path may become
invalid - the path may result in a forwarding loop. Therefore, it is
essential to have some mechanism(s) to detect invalid path in a
timely fashion, so that a new (valid) path could be established.

It could be shown that relying only on the routing information present
at both the ingress and the egress routers (NHRP Requestor and NHRP
Responder) may not be sufficient to detect when a (previously) valid
path becomes invalid.

Upon some introspection one could realize that a collection of routing
information from all the routers between the Requestor and the
Responder through which an NHRP Request was traversed is sufficient to
detect when a (previously) valid path becomes invalid.  However, from a
practical point of view, requiring every router along the NHRP Request
path to maintain a state for each such Request and signal back to the
Requestor when the routing changes occur may present (among other things) a
serious scaling problem, and thus is not practical.

To address the scaling concern, while at the same time allow to detect
invalid paths in a timely fashion, we relax the requirement to monitor
the routing information on all the routers between the Requestor and the
Responder through which an NHRP Request was traversed by reducing this
set of routers. The reduced set consists of only the routers where the
routing information that was used to forward the Request was either (a)
translated from one routing protocol to another, or (b) was created as
a result of routing information aggregation procedures.  [It is not
clear whether we can relax this by removing (b).] For the rest of this
document we'll refer to these routers as "border routers". [A better term is
needed.]


Alternative 1: short-cut between border routers

The first design alternative is to eliminate extra hops between border
routers, but not across border routers. Therefore, if a path through an NBMA
network spans multiple border routers, then the path will have more than
one IP hop across the NBMA network -- 1 IP hop per border router.

For example, if a path segment through an NBMA network is R1, R2, R3,
R4, R5, R6, and R7 (where R1 is an ingress router, R7 is an egress
router), and R3 and R5 are border routers, then the optimized path would be
R1, R3, R5, R7 (extra hops through R2, R4, and R6 will be eliminated).

The scheme works as follows. An ingress router generates an NHRP
Request for a particular destination.  The request is forwarded along
the path to that destination until it hits a router (on the same NBMA
network) that is a border router.  At this point the router sends back an
NHRP Response. In addition, the router may originate its own NHRP
Request for the same destination as was carried in the received
request. The new request will be forwarded until it reaches next border
router. The process will continue in a similar fashion until a request
reaches an egress router.

Each border router monitors changes in the routes that were used to
originate NHRP Requests or Responses. If such a router detects changes
in a route associated with a request, the router initiates another NHRP
Request.  If the router detects changes in a route associated with a
response, the router sends a Purge message to the recipient of the
response.

Using the example above, R1 would generate an NHRP Request. The request
will be forwarded to R2, and R2 will forward it to R3. When the request
reaches R3, R3 sends back an NHRP Response (since R3 is a border router),
thus establishing a short-cut R1-R3 (bypassing R2). R3 also originates
its own NHRP Request. This request is forwarded to R4, and R4 forwards
it to R5. Since R5 is a border router, R5 sends back (to R3) an NHRP
Response, thus establishing a short-cut R3-R5 (bypassing R4). R5 also
originates its own NHRP Request. This request is forwarded to R6, and
R6 will forward it to R7. Since R7 is an egress router, it sends back
(to R5) an NHRP Response, thus forming a short-cut R5-R7 (bypassing
R6).

Any changes in the route maintained by R5 (that was used to generate
the response to R3) would result in (a) R5 originating another NHRP
Request, and (b) R5 sending a Purge message to R3. As a result of this
message R3 would originate another NHRP Request.  Note that if the
route that was used by R3 to generate an NHRP Response to R1 doesn't
change, then R3 doesn't send any messages to R1. Likewise, any changes
in the route maintained by R3 (that was used to generate the response
to R1) would result in (a) R3 originating another NHRP Request, and (b)
R3 sending a Purge message to R1.

To provide the desired path optimization, this alternative requires
that all the border routers within an NBMA network be NHRP-capable. While
failure to meet this requirement impacts path optimality, a much more
serious issue associated with violating this requirement is the
ability to maintain a valid path. If some of the border routers are not
NHRP-capable, and other (NHRP-capable) routers along a path of a given
NHRP Request can't detect that some of the border routers along the path do
not support NHRP, such a situation may lead to a long-live invalid
path.

Using the example above, if R3 is a border router, but does not support
NHRP, and if R2 and R4 wouldn't be able to detect that the path between
them traverses through a border router that does not support NHRP (R3),
routing changes in R3 may cause the path to become invalid. But since
R3 is not NHRP-capable, R3 wouldn't be able to indicate the change to
other NHRP-capable routers along the path.  As a result, there is a
potential for a long-lived invalid path.

Since presence of border routers that do not support NHRP could lead to a
potentially serious failure mode, it may be desirable to have
mechanisms to avoid such failures.  Because border routers are most likely
to be the routers that interconnect different routing domains, one
could suggest that a way to detect a situation where an NHRP Request
path traverses through an NHRP-incapable border router is to carry
sufficient information in the request to identify when the request
crosses routing domain boundaries.  For certain scenarios this
detection seems to be quite straightforward (e.g. detecting routing
domain boundaries between domains that run different routing
protocols).  However, for other scenarios that involve multiple
instances of the same routing protocol, where each group of routers
runs just one instance of a particular routing protocol, but there are
more than one such group (with a common protocol) on the same NBMA
network, detecting routing domain boundary may be more problematic. For
example, it is not clear how to distinguish between two instances of
RIP, or OSPF, or Dual IS-IS.

In principle every router (regardless of what protocols the router
runs) could be configured with additional information that would allow
them to detect a situation where a pair of routers (on a common NBMA) run
the same or different instances of a particular routing protocol.  In
practice this requires additional configuration on every NHRP-capable
router connected to an NBMA network. This configuration is likely to
depend on manual procedures, and therefore may be error prone and
difficult to administer.

Another possible way to avoid failures associated with the presence of border
routers that do not support NHRP is to require configuration of multiple
logical NBMA networks over the single physical network in such a way
that boundaries of each logical NBMA network will be congruent to the
boundaries formed by border routers. Since NHRP Requests can not cross
logical NBMA boundaries, it follows that NHRP Requests will never cross
a border router (regardless of whether such a router supports NHRP or
not).  That would certainly eliminate the problem due to NHRP
non-capable border routers. The drawback of this approach is that it
requires administrative efforts to partition an NBMA network into
multiple logical NBMA networks.  On the other hand, once the partition
is done (provided that the partition is correct), the scheme is quite
robust with respect to its ability to detect invalid paths.

Alternative 2: short-cut across border routers

The second design alternative is to eliminate extra hops across the
whole NBMA network, regardless of the number of border routers along the
path segment within the NBMA network.  Therefore, even if a path
through an NBMA network spawns multiple border routers, then the path will
have just one IP hop across the NBMA network.

For example, if a path segment through an NBMA network is R1, R2, R3,
R4, R5, R6, and R7 (where R1 is an ingress router, R7 is an egress
router), and R3 and R5 are border routers, then the optimized path would be
R1, R7 (extra hops through R2, R3, R4, R5, and R6 will be eliminated).

The scheme works as follows. An ingress router generates an NHRP
Request for a particular destination.  The request is forwarded along
the path to that destination until it reaches a router (on the same
NBMA network) that is a border router.  At this point the router
instantiates a state associated with the request. This state contains
(among other things) the identity of the requestor and the route that
is used to forward the request. Once the state is instantiated, the
router forwards the request. The process continues until the request
reaches an egress router.

Each border router monitors changes in routes that were used to originate
NHRP Requests or Responses, or to forward NHRP Requests.  If such a
router detects changes in a route associated with originating a
request, the router initiates another NHRP Request.  If the router
detects changes in a route associated with a response, the router sends
a Purge message to the recipient of the response.  If a router detects
changes in a route associated with forwarding a request, the router
sends a Purge message to the originator of the Request (the information
about the originator is maintain by the router).

Using the example above, R1 would generate an NHRP Request. The request
will be forwarded to R2, and R2 will forward it to R3. When the request
reaches R3, R3 instantiates a state associated with the request. The
state contains the route that R3 use to further forward the request,
and the address of the request's originator (R1). R3 then forwards the
request.  The request will be forwarded to R4, and R4 will forward it
to R5. Since R5 is a border router, R5 (just like R3) instantiates a state
associated with the request. The state contains the route R5 uses to
further forward the request, and the address of the request originator
(R1).  The request will be forwarded to R6, and R6 will forward it to
R7. Since R7 is an egress router, it sends back an NHRP Response, thus
forming a short-cut R1-R7.  R7 also instantiates a state associated
with the request.  Any changes in the state maintained by R3, R5, or R7
would result in a Purge message being sent to R1. As a result of
receiving the message, R1 would issue a new NHRP Request, which would
result in obtaining a valid path.

To deal with a loss of state due to router crash this alternative
requires periodic re-validation of paths. The time interval between two
consecutive re-validations (two consecutive NHRP Requests from the same
router for the same target address) imposes an upper bound on the
life-time of an invalid path.

While this alternative provides a better path optimization than the
previous alternative, its scaling properties are inferior to the
previous alternative.  This alternative requires every border router to
maintain the amount of state proportional to the number of NHRP Request
paths that either terminate or traverse through that router, where an
NHRP path could originate from any router connected to the NBMA
network.

Just like the previous alternative, this alternative has a weak point
with respect to the requirement it imposes on the deployment of NHRP on
border routers, and on the ability to detect when an NHRP Request path
traverses through a border router that doesn't support NHRP.


Alternative 3:

If we can not assume that all border routers within an NBMA network are
NHRP-capable, and if we don't have a mechanism to detect all the
occurences where an NHRP Request path traverses through a border router
that is NHRP-incapable, then we can not rely on changes to routing
information as being the trigger to re-validate the validity of a
short-cut path acquired via NHRP. As a result we need to come up with
some other mechanism(s) to trigger the re-validation.

This alternative suggests that the frequency with which a particular
short-cut route (acquired via NHRP) be re-validated be coupled with the
rate of data traffic being forwarded via this route. In a most simple
case, the higher the data traffic rate associated with a particular
route, the greater is the frequency with which the route gets
re-validated (via issuing NHRP Requests) - the less is the time between
two consecutive NHRP Requests.

By coupling the frequency of route re-validating with the data traffic
rate for the route, this scheme constrains the amount of traffic that
could be affected by a forwarding loop. Moreover, since a forwarding
loop usually results in the increase of traffic through the routers in
the loop, and since the router that originated the NHRP Request is just
one of the routers in the loop, formation of the loop would result in
the increased data traffic rate through that router, which in turn
would decrease the time between two consecutive NHRP Requests.

A more sophisticated strategy would be to couple the time between two
consecutive NHRP Requests to some combination of the data rate and its
first derivative over time. The latter (the first derivative) would
allow a faster adaptation where significant changes in the data rate
occur.  Since formation of forwarding loops results in such significant
changes, coupling the time between the two consecutive NHRP requests
with the first derivate of data rate would help to shorten the duration
of such loops.

While traffic volume may be a good metric to determine how quickly an
invalid path needs to be detected (and subsequently replaced with a
valid path), it is equally important to avoid long-lived invalid paths
even in presence of only low volume traffic.  Therefore, in addition to
the data rate (and perhaps its derivative) driven frequency of NHRP
Requests, this alternative would also have some fixed timer that
imposes a lower bound on the frequency with which NHRP Requests should
be issued. This, in turn, imposes an upper bound on the life time of an
invalid path.

An important potential drawback of this alternative is the overhead
associated with processing NHRP traffic. 

For this scheme to work, a router that originates or forwards an NHRP
Request should not send this request over an NHRP-discovered route. The
request has to be sent over a route acquired via conventional routing
protocol(s).