Network Working Group Yakov Rekhter Internet Draft Cisco Systems Expiration Date: July 1996 January 1996 NHRP for Destinations off the NBMA Subnetwork draft-ietf-rolc-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 station (e.g., a host or a router) on an NBMA subnetwork to find the NBMA subnetwork 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, [NHRP] constrains the ability of determining the egress router to the destinations that are directly connected to the egress router. This document describes extensions to the NHRP that allow a station 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-rolc-r2r-nhrp-00.txt January 1996 3. Definitions 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 Base (FIB) routes whose Network Layer Reachability Information (NLRI) exhibits a subset relation. Such routes are called overlapping routes. 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. We will refer to the information acquired via NHRP as a ``shortcut''. We will refer to the entity that originates an NHRP Request and the entity that replies to that Request as the ``ends of the shortcut''. To provide correct forwarding in the presence of overlapping routes this document constrains an NHRP target 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. 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 NHRP target constraint. For the rest of the document we'll refer to this constraint as the ``NHRP target constraint''. The NHRP target constraint guarantees that within a given station 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-rolc-r2r-nhrp-00.txt January 1996 4. NHRP Route Information To allow routers along a path to unambiguously determine routing domain boundary the NHRP Request carries the NHRP route information. The NHRP route information is generated by the station that originates an NHRP Request. The NHRP route information is carried as an NHRP Route Information Extension. 4.1. NHRP Route Information Extension Encoding Compulsory = 1 Type = TBD Length = variable This extension is used to determine when an NHRP Request reaches routing domain boundary. The NHRP Route Information extension consists of two components, protocol independent and protocol specific. The protocol independent component consists of the protocol type of the NHRP forwarding route associated with the NHRP target. For RIP, OSPF, Dual IS-IS, and BGP the protocol specific component is empty. For RIP-2 the protocol specific component is two octets long and contains the Route Tag of the NHRP forwarding route. Definition of the protocol specific component for other routing protocols is outside the scope of this document. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | unused | Protocol Type | Protocol Specific Information | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ This document defines the following values for the Protocol Type field: RIP 1 RIP-2 2 OSPF 3 Dual IS-IS 4 BGP 5 Yakov Rekhter [Page 3] Internet Draft draft-ietf-rolc-r2r-nhrp-00.txt January 1996 5. Processing NHRP Request Processing of an NHRP Request by routers 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 an NHRP Request, the router uses the NHRP target and the NHRP route information carried in the Request to check whether (a) the NHRP target constraint is 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 NHRP target constraint is violated, the router reports an error to the originator of the Request (by sending to the originator the NHRP Error Indication message) and terminates the query. The message should indicate that the NHRP target constraint was violated. If the constraint is not violated, the router determines the NHRP forwarding route associated with the NHRP target carried by the Request. This route is used by the domain-specific rules (see Section 5.2) to determine whether the router is in the same routing domain as the originator of the Request, and whether the router is a border router for the routing domain that the originator of the Request is in. If the router is in a different routing domain than the originator of the Request, then the router reports an error to the originator of the Request (by sending to the originator the NHRP Error Indication message) and terminates the query. If the router is within the same routing domain as the originator of the Request, and the router determines that it is a border router for that domain (using the domain-specific rules), then the router terminates the query and sends back an NHRP Reply. The information carried in the Reply may be either (a) IP and NBMA addresses of the router itself, or (b) IP and NBMA addresses of some other router that the router acquires via either NHRP or some other procedures (see Section 7). The former allows to establish shortcuts within a single routing domain. The latter allows to establish shortcuts that cross domain's boundary. The choice between (a) and (b) is a local to the router matter. If the router is within the same routing domain as the originator of the Request, and the router performs routing information aggregation, then it could be possible for the NHRP forwarding route associated with the NHRP target to be a local aggregate (constructed by the Yakov Rekhter [Page 4] Internet Draft draft-ietf-rolc-r2r-nhrp-00.txt January 1996 router as a result of routing information aggregation). In this case the router must terminate the query and send back an NHRP Reply with its own IP and NBMA addresses as the next hop. 5.2. Domain-specific rules The following describes NHRP handling rules specific to particular routing domains (e.g., RIP domain, OSPF domain). 5.2.1. RIP, OSPF, Dual IS-IS Domains If the routing protocol by which the NHRP forwarding route was acquired is the same as the protocol indicated by the Protocol Type field in the NHRP Route Information Extension carried by the Request, then the router handles the Request following the procedures described in [NHRP]. Otherwise, the router is a border router. 5.2.2. RIP-2 Domain If the routing protocol by which the NHRP forwarding route was acquired is the same as the protocol indicated by the Protocol Type field in the NHRP Route Information Extension carried by the Request, and the Route Tag of the route is the same as carried in the NHRP Route Information Extension, then the router handles the Request following the procedures described in [NHRP]. Otherwise, the router is a border router. 6. Maintaining correct shortcut information Once a station that originates an NHRP Request acquires an address of an egress router along a path to a destination, it is essential for the station 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 should monitor the status of the route that was associated with the shortcut (the NHRP forwarding route). If the status changes at the router that generated the NHRP Reply (the egress router), 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 Request. This allows to ensure that when both ends of a shortcut are up, any changes in routing that impact forwarding to any of the destination covered by Yakov Rekhter [Page 5] Internet Draft draft-ietf-rolc-r2r-nhrp-00.txt January 1996 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. This is needed to suppress black holes if the next hop router in the shortcut (the router that generated Reply) goes down. 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) information gleaned from routing protocol(s), (d) NHRP itself. A Requester should establish a shortcut only after the Requester has a reasonable assurance 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. A router should not propagate an NHRP Request if the propagation is based on the routing information that the router views as transient. Likewise, a router should not construct an NHRP Reply based on such information. 7. Multi-domains shortcuts While the NHRP mechanism described above is constrained to the routers within a single routing domain, the information provided by this mechanism could be sufficient to establish shortcuts that would span multiple domains. 7.1. Using the ``third-party'' next hop information Certain routing protocols (e.g., BGP) allow a router to advertise a route with some other (than the router) entity as the next hop. This feature could be used to acquire the shortcut information that crosses domain's boundary. 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 identify a router 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 could use this information (rather than its own IP and Yakov Rekhter [Page 6] Internet Draft draft-ietf-rolc-r2r-nhrp-00.txt January 1996 NBMA addresses) to construct an NHRP Reply. This way the Reply would carry the next hop information that is associated with a router in some other routing domain, thus providing to the Requester the information needed to establish a shortcut that spans multiple routing domains. Since BGP does not carry the NBMA address information for the next hop, a router that uses the next hop information from a BGP-learned route should use NHRP to acquire the NBMA address of the entity identified by the next hop. 7.2. Chaining/Leaking NHRP information across domain's boundary 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 by using this information to construct NHRP Replies. In effect the router would ``leak'' the NHRP-learned information. Since a border router (by definition) belongs to multiple routing domains, passing the NHRP 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. This way Y would get the information needed 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. Yakov Rekhter [Page 7] Internet Draft draft-ietf-rolc-r2r-nhrp-00.txt January 1996 7.3. Chaining/Leaking NHRP information with BGP Additional complexity in handling multi-domains shortcuts arises if the 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, the following assumes that the routing information exchange across domains' boundary is controlled by BGP. If both the source and the destination domains are on a common NBMA network, and a path between these two domains is also fully within the same NBMA network, then we have only three routing domains to deal with: the source routing domain, the BGP routing domain, and the 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, (c) how a border router in the domain where the NHRP target is in handles the Request (crossing BGP/IGP boundary). 7.3.1. Handling NHRP Request at the border router in the source domain 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 (received) Request; the NHRP Route Information extension contains the Protocol Type (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 Yakov Rekhter [Page 8] Internet Draft draft-ietf-rolc-r2r-nhrp-00.txt January 1996 information from the Reply to construct its own Reply to the source of the original NHRP Request. If later on the border router receives a Purge message for the NHRP forwarding route, the border router treats this event as if there was a local change to the NHRP forwarding route (even if the there was no changes to the route). 7.3.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 a router that receives a Request determines that it performs routing information aggregation for the NHRP target, the router could either (i) initiate another NHRP Request, and use the information received in response to this Request to construct an NHRP Reply for the original Request, or (ii) find the NHRP forwarding route associated with the NHRP target and forward the Request to the next hop of the NHRP forwarding route. The choice between options (i) and (ii) is a local to the router matter. If the router selects option (i), then 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 the Protocol Type (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 Yakov Rekhter [Page 9] Internet Draft draft-ietf-rolc-r2r-nhrp-00.txt January 1996 later on receives a Purge message for the NHRP forwarding route, the router treats this event as if there was a change to the NHRP forwarding route (even if the there was no changes to the route). 7.3.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 the Protocol Type 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 to the NHRP forwarding route (even if the there was no changes to the route). 7.4. Tradeoffs between state, messages, and path optimality 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 routing information aggregation along the path from the source to the destination. Specifically, on each such router it would be necessary to keep the information about all the NHRP targets for which the router maintains the shortcut information. This way when the 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. The router would send Purge messages only for the targets that are impacted by the changes. Upon some introspection one could realize that the shortcut information across a BGP domain could be used for as long as the NHRP forwarding route at both ends of the shortcut stays the same (even in Yakov Rekhter [Page 10] Internet Draft draft-ietf-rolc-r2r-nhrp-00.txt January 1996 the presence of aggregation along the shortcut). Such information would provide loop-free forwarding, but may result in a potentially suboptimal path (if a router that performs aggregation along the path selects another (better) route for forming the aggregate). This way there is no need to maintain an additional state on the BGP routers that perform routing information aggregation, and there will be no additional NHRP traffic when these routers change the way they construct their aggregates, provided that the aggregated routes would stay the same. 8. Security Considerations Security issues are not discussed in this document. 9. References [NHRP] Katz, D., Piscitello, D., Cole, B., Luciani, J., ``NBMA Next Hop Resolution Protocol (NHRP)'', Internet Draft, December 1995 10. Acknowledgements To be supplied. 11. 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 11]