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]