router-route NHRP - multi-domain shortcuts (moderately long)

[Yakov Rekhter <[e-mail]>]

Folks,

Here (as I promised) is a rough outline of how the router-router mechanism
(the one I posted today) could be extended to provide information for
the shortcut that could cross routing domain boundaries.

Your review and comments would be greatly appreciated.

Yakov.
---------------------------------cut here------------------------------------
Extensions to multi-domains shortcuts

While the R2R NHRP mechanism 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 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.

[Getting into more controversy...]

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

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

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


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

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