idnits 2.17.1 draft-ietf-rolc-nhrp-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Cannot find the required boilerplate sections (Copyright, IPR, etc.) in this document. Expected boilerplate is as follows today (2024-04-16) according to https://trustee.ietf.org/license-info : IETF Trust Legal Provisions of 28-dec-2009, Section 6.a: This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 2: Copyright (c) 2024 IETF Trust and the persons identified as the document authors. All rights reserved. IETF Trust Legal Provisions of 28-dec-2009, Section 6.b(i), paragraph 3: This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing document type: Expected "INTERNET-DRAFT" in the upper left hand corner of the first page ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about Internet-Drafts being working documents. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity. ** The document seems to lack a 1id_guidelines paragraph about the list of current Internet-Drafts. ** The document seems to lack a 1id_guidelines paragraph about the list of Shadow Directories. ** Expected the document's filename to be given on the first page, but didn't find any ** The document is more than 15 pages and seems to lack a Table of Contents. == No 'Intended status' indicated for this document; assuming Proposed Standard == It seems as if not all pages are separated by form feeds - found 0 form feeds but 26 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. ** There are 42 instances of too long lines in the document, the longest one being 4 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == Couldn't figure out when the document was first submitted -- there may comments or warnings related to the use of a disclaimer for pre-RFC5378 work that could not be issued because of this. Please check the Legal Provisions document at https://trustee.ietf.org/license-info to determine if you need the pre-RFC5378 disclaimer. -- The document date (October 15, 1993) is 11141 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: '1' is defined on line 1174, but no explicit reference was found in the text == Unused Reference: '2' is defined on line 1176, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. '2' Summary: 13 errors (**), 0 flaws (~~), 5 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Routing over Large Clouds Working Group Juha Heinanen 3 Request for Comments: DRAFT (Telecom Finland) 4 Expires Apr 15, 1994 Ramesh Govindan 5 (Bellcore) 6 October 15, 1993 8 NBMA Next Hop Resolution Protocol (NHRP) 10 Status of this Memo 12 This document is an Internet Draft. Internet Drafts are working 13 documents of the Internet Engineering Task Force (IETF), its Areas, 14 and its Working Groups. Note that other groups may also distribute 15 working documents as Internet Drafts. 17 Internet Drafts are draft documents valid for a maximum of six 18 months. Internet Drafts may be updated, replaced, or obsoleted by 19 other documents at any time. It is not appropriate to use Internet 20 Drafts as reference material or to cite them other than as a 21 ``working draft'' or ``work in progress.'' Please check the 1id- 22 abstracts.txt listing contained in the internet-drafts Shadow 23 Directories on nic.ddn.mil, nnsc.nsf.net, nic.nordu.net, 24 ftp.nisc.sri.com, or munnari.oz.au to learn the current status of any 25 Internet Draft. 27 Abstract 29 This document describes the NBMA Next Hop Resolution Protocol (NHRP). 30 NHRP can be used by a source terminal (host or router) connected to a 31 Non-Broadcast, Multi-Access link layer (NBMA) network to find out the 32 IP and NBMA addresses of the "NBMA next hop" towards a destination 33 terminal. The NBMA next hop is the destination terminal itself, if 34 the destination is connected to the NBMA network. Otherwise, it is 35 the egress router from the NBMA network that is "nearest" to the 36 destination terminal. Although this document focuses on NHRP in the 37 context of IP, the technique is applicable to other network layer 38 protocols as well. 40 1. Introduction 42 The NBMA Next Hop Resolution Protocol (NHRP) allows a source terminal 43 (a host or router), wishing to communicate over a Non-Broadcast, 44 Multi-Access link layer (NBMA) network, to find out the IP and NBMA 45 addresses of the "NBMA next hop" towards a destination terminal. The 46 NBMA next hop is the destination terminal itself, if the destination 47 is connected to the NBMA network. Otherwise, it is the egress router 49 RFC DRAFT NBMA NHRP October 15, 1993 51 (out of the NBMA network) nearest to the destination terminal. 53 Conventional hop-by-hop IP routing may not be sufficient to resolve 54 the "NBMA next hop" towards the destination terminal. An NBMA 55 network may, in general, consist of multiple logically independent IP 56 subnets (LISs, [3]); IP routing would only resolve the next hop LIS 57 towards the destination terminal. 59 Once the NBMA next hop has been resolved, the source may either start 60 sending IP packets to the destination (in a connectionless NBMA 61 network such as SMDS) or may first establish a connection to the 62 destination with the desired bandwidth and QOS characteristics (in a 63 connection oriented NBMA network such as ATM). 65 An NBMA network can be non-broadcast either because it technically 66 doesn't support broadcasting (e.g. an X.25 network) or because 67 broadcasting is not feasible for one reason or another (e.g. an SMDS 68 broadcast group or an extended Ethernet would be too large). 70 2. Protocol Overview 72 In this section, we briefly describe how a source S uses NHRP to 73 determine the "NBMA next hop" to destination D. S first determines 74 the next hop to D through normal routing processes. If this next hop 75 is reachable through its NBMA interface, S formulates an NHRP request 76 containing the source and destination IP addresses and QOS 77 information. S then forwards the request to an entity called the 78 "Next Hop Server" (NHS). 80 For administrative and policy reasons, a physical NBMA network may be 81 partitioned into several disjoint logical NBMA networks (discussed 82 later in this section); NHSs cooperatively resolve the NBMA next hop 83 within their logical NBMA network. Unless otherwise specified, we use 84 NBMA network to mean logical NBMA network. 86 Each NHS "serves" a pre-configured set of terminals and peers with a 87 pre-configured set of NHSs, which all belong to the same NBMA 88 network. An NHS exchanges routing information with its peers (and 89 possibly with the terminals it serves) using regular routing 90 protocols. (However, an NHS, unless it is also an egress/ingress 91 router, need not necessarily be able to switch regular IP packets). 92 This exchange is used to construct a forwarding table per QOS in 93 every NHS. The forwarding table determines the next hop NHS towards 94 the NHRP request's destination. This next hop NHS may depend on the 95 request's QOS information. 97 After receiving an NHRP request, the NHS checks if it "serves" D. If 98 so, the NHS resolves D's NBMA address, using mechanisms beyond the 100 RFC DRAFT NBMA NHRP October 15, 1993 102 scope of this document (examples of such mechanisms include ARP [1, 103 2] and pre-configured tables). The NHS then either forwards the NHRP 104 request to D or generates a positive NHRP reply on its behalf. The 105 reply contains D's (D is S's NBMA next hop) IP and NBMA address and 106 is sent back to S. NHRP replies usually traverse the same sequence 107 of NHSs as the NHRP request (in reverse order, of course). 109 If the NHS does not serve D, it extracts from its forwarding table 110 the next hop towards D. If no such next hop entry is found, the NHS 111 generates a negative NHRP reply. 113 If the next hop is behind the NHS's NBMA interface, the NHS forwards 114 the NHRP request to the next hop. If the next hop is behind some 115 other interface, the NHS may be willing to act as an egress router 116 for traffic bound to D. In that case, the NHS generates a positive 117 NHRP reply containing its own IP and NBMA address (i.e., the NHS is 118 the NBMA next hop from S to D). 120 An NHS receiving an NHRP reply may cache the NBMA next hop 121 information contained therein. To a subsequent NHRP request, this 122 NHS might respond with the cached, non-authoritative, NBMA next hop 123 or with cached negative information. If a communication attempt based 124 on non-authoritative information fails, a source terminal can choose 125 to send an authoritative NHRP request. NHSs never respond to 126 authoritative NHRP requests with cached information. 128 NHRP requests and replies never cross the borders of a logical NBMA 129 network. Thus, IP traffic out of and into a logical NBMA network 130 always traverses an IP router at its border. Network layer filtering 131 can then be implemented at these border routers. 133 NHRP provides a mechanism to aggregate NBMA next hop information in 134 NHS caches. Suppose that NHS X is the NBMA next hop from S to D. 135 Suppose further that X is an egress router for all terminals sharing 136 an IP address prefix with D. When X generates an NHRP reply in 137 response to a request, it may replace the IP address of D with this 138 prefix. The prefix to egress router mapping in the reply is cached 139 in all NHSs on the path of the reply. A subsequent (non- 140 authoritative) NHRP request for some destination that shares an IP 141 address prefix with D can be satisfied with this cached information. 143 To dynamically detect link-layer filtering in NBMA networks, NHRP 144 incorporates a "Route record" in replies. This Route record contains 145 the network and link layer addresses of intermediate NHSs willing to 146 route packets from the source to the destination prefix. When a 147 source terminal is unable to open a connection to the responder, it 148 attempts to do so successively with one of the NHSs in the Route 149 record until it succeeds. This approach finds the optimal best hop in 151 RFC DRAFT NBMA NHRP October 15, 1993 153 the presence of link-layer filtering. 155 3. Configuration 157 Terminals 159 To participate in NHRP, a terminal connected to an NBMA network 160 should to be configured with the IP address(es) of its NHS(s). 161 These NHS(s) may be physically located on the terminal's default or 162 peer routers, so their addresses may be obtained from the 163 terminal's IP forwarding table. If the terminal is attached to 164 several link layer networks (including logical NBMA networks), it 165 should also be configured to receive routing information from its 166 NHS(s) and peer routers so that the terminal can determine which IP 167 networks are reachable through which link layer networks. 169 Next Hop Servers 171 An NHS is configured with a set of IP address prefixes that 172 correspond to the IP addresses of the terminals it is serving. 173 Moreover, the NHS must be configured to exchange routing 174 information with its peer NHSs (if any). If a served terminal is 175 attached to several link layer networks, the NHS may also need to 176 be configured to advertize routing information to such terminals. 178 If an NHS is acting as an egress router for terminals connected to 179 other link layer networks than the NBMA network, the NHS must, in 180 addition to the above, be configured to exchange routing 181 information between the NBMA network and these other link layer 182 networks. 184 In all cases, routing information is exchanged using regular 185 intra-domain and/or inter-domain routing protocols. 187 4. Packet Formats 189 NHRP requests and replies are carried as ICMP messages. This section 190 describes the packet formats of NHRP requests and replies: 192 NHRP Request 194 RFC DRAFT NBMA NHRP October 15, 1993 196 0 1 2 3 197 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 198 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 199 | Type | Code | Checksum | 200 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 201 | Hop Count | Unused | 202 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 203 | Destination IP address | 204 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 205 | Source IP address | 206 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 208 Type 209 19 211 Code 212 A response to an NHRP request may contain cached information. If an 213 authoritative answer is desired, then code 2 (NHRP request for 214 authoritative information) should be used. Otherwise, a code value of 1 215 (NHRP request) should be used. 217 Hop Count 218 The Hop count indicates the maximum number of NHSs that a request 219 or reply is allowed to traverse before being discarded. 221 Source and Destination IP Addresses 222 Respectively, these are the IP addresses of the NHRP request 223 initiator and the terminal for which the NBMA next hop is desired. 225 NHRP Reply 227 0 1 2 3 228 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 229 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 230 | Type | Code | Checksum | 231 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 232 | Hop Count | Unused | Route record length | 233 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 234 | Source IP address | 235 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 236 | Destination IP address | 237 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 238 | Destination mask | 239 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 240 | | 241 | NHRP route record (variable) | 242 | | 243 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 245 RFC DRAFT NBMA NHRP October 15, 1993 247 Type 248 20 250 Code 251 NHRP replies may be positive or negative. An NHRP positive, 252 non-authoritative reply carries a code of 1, while a positive, 253 authoritative reply carries a code of 2. An NHRP negative, 254 non-authoritative reply carries a code of 3 and a negative, 255 authoritative reply carries a code of 4. An NHS is not allowed to 256 reply to an NHRP request for authoritative information with cached 257 information, but may do so for an NHRP Request. 259 Route Record Length 260 The length in words of the NHRP route record (see below). 262 Source IP Address 263 The address of the initiator of the corresponding NHRP request. 265 Destination IP Address and Mask 266 If the NHRP Request's destination is on the NBMA, the reply contains 267 that destination address and a mask of all 1s. Otherwise, the 268 responder may choose to act as the egress router for all terminals in 269 the destination's subnet. If so, the reply contains a prefix of the 270 requested destination IP address and the corresponding mask. 272 NHRP Route Record 273 The NHRP route record is a list of NHRP "Route elements" for NHSs on 274 the path of a positive NHRP reply. Only NHSs that are willing to act 275 as egress routers for packets from the source to the destination insert 276 a Route element in the NHRP reply. Negative replies do not carry 277 Route elements. 279 The first Route element is always that of the destination terminal or, 280 if the destination is not directly attached to the NBMA, that of the 281 responding egress router. Each Route element is formatted as follows: 283 0 1 2 3 284 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 285 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 286 | IP address | 287 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 288 | LL length | Link Layer (LL) address | 289 +-+-+-+-+-+-+-+-+-+ | 290 | (variable length) | 291 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 293 The LL length field is the length of the link layer address in 294 bits. The LL address itself is zero-filled to the nearest 32-bit 296 RFC DRAFT NBMA NHRP October 15, 1993 298 boundary. 300 On the reply path, an NHS willing to route packets from source to 301 the destination prefix should append its Route element to the 302 current Route Record, adjust the Route record length appropriately, 303 and recompute the ICMP checksum. The Route record is used to 304 discover link layer filters, as described in Section 2. 306 If the first Route element's IP address and the destination's IP 307 address differ, the source terminal may assume that the reply was 308 generated by an egress router. 310 An NHS may cache replies containing a Route record. Subsequently, 311 when it responds to an NHRP request with the cached reply, 312 intermediate NHSs on the path to the initiator may attach Route 313 elements to the reply. 315 5. Protocol Operation 317 The external behavior of an NHS may be described in terms of two 318 procedures (processRequest and processReply) operating on two tables 319 (forwardingTable and cacheTable). In an actual implementation, the 320 code and data structures may be realized differently. 322 Each NHS has for each supported QOS an NHRP forwardingTable 323 consisting of entries with the fields: 325 327 In case the NHS is also a host or serving as a router, the NHRP 328 forwarding table may be integrated with the normal IP forwarding 329 table of the NHS. 331 The networkLayerAddrPrefix field identifies a set of network layer 332 addresses known to the NHS. It consists of two subfields . 335 The type field indicates the type of the networkLayerAddrPrefix. The 336 possible values are: 338 - locallyServed: The NHS is itself serving the 339 networkLayerAddrPrefix. The outIf field denotes the NBMA interface 340 via which the served terminals can be reached and the outIfAddr 341 field has no meaning. Such a forwardingTable entry has been 342 created by manual configuration. 344 - nhsLearned: The NHS has learned about the networkLayerAddrPrefix 345 from another NHS. The outIf and outIfAddr fields, respectively, 347 RFC DRAFT NBMA NHRP October 15, 1993 349 denote the NBMA interface and IP address of this next hop NHS. 350 Such a forwardingTable entry is a result of network layer address 351 prefix information exchange with one of the NHS's peers. 353 - externallyLearned: The NHS has learned about the 354 networkLayerAddrPrefix via normal IP routing from outside of the 355 NBMA network. In this case, the NHS may act as an egress router 356 for the terminals sharing the networkLayerAddrPrefix. The outIf and 357 outIfAddr fields, respectively, denote the interface and IP address 358 of the next hop router. If the outIfAddr field is empty, the 359 networkLayerAddrPrefix is assumed to be directly connected to the 360 outIf of the NHS. 362 The protocol used to exchange networkLayerAddrPrefix information 363 among the NHSs or between NHSs and their peer routers can be any 364 regular IP intra-domain or inter-domain routing protocol. 366 In addition to the forwardingTable, each NHS has for each supported 367 QOS an NHRP cacheTable consisting of entries with the fields: 369 371 The entries in the cacheTable are learned from NHRP replies 372 traversing the NHS. The networkLayerAddrPrefix field identifies a set 373 of IP addresses sharing a common Route record. The 374 networkLayerAddrPrefix field consists of two subfields . The routeElementList field is either empty (in case of a 376 negative cache entry) or consists of a list of subfields of the form 377 . 379 The cacheTable entries could also include a timeStamp field to be 380 used to age cacheTable entries after a certain hold period. 382 The following pseudocode defines how NBMA NHRP requests and replies 383 are processed by an NHS. 385 RFC DRAFT NBMA NHRP October 15, 1993 387 procedure processRequest(request); 388 let bestMatch == matchForwardingTable(request.dIPa) do 389 if bestMatch then 390 if bestMatch.type == locallyServed then 391 let nbmaAddr == arp(request.dIPa) do 392 if nbmaAddr then 393 genPosAuthReply(request.sIPa, 394 request.dIPa, 0xFFFFFFFF, 395 request.dIPa, nbmaAddr) 396 else 397 genNegAuthReply(request.sIPa, request.dIPa) 398 end 399 end 400 elseif bestMatch.type == nhsLearned then 401 if not requestForAuthInfo?(request) then 402 let cacheMatch == matchCacheTable(request.dIPa) do 403 if cacheMatch then 404 if cacheMatch.routeElementList == EMPTY then 405 genNegNonAuthReply(request.sIPa, request.dIPa) 406 else 407 genPosNonAuthReply(request.sIPa, 408 cacheMatch.networkLayerAddrPrefix.ipAddr, 409 cacheMatch.networkLayerAddrPrefix.mask, 410 cacheMatch.routeElementList); 411 end 412 else /* no cache match */ 413 forwardRequest(request, bestMatch.OutIf, 414 bestMatch.OutIfAddr) 415 end 416 end 417 else /* request for authoritative information */ 418 forwardRequest(request, bestMatch.OutIf, 419 bestMatch.OutIfAddr) 420 end 421 else /* bestMatch.type == externallyLearned */ 422 genPosAuthReply(request.sIPa, 423 bestMatch.networkLayerAddrPrefix.ipAddr, 424 bestMatch.networkLayerAddrPrefix.mask, 425 selfIpAddr, selfNbmaAddr) 426 end 427 else /* no match in forwardingTable */ 428 genNegAuthReply(request.sIPa, request.dIPa) 429 end 430 end 431 end 433 RFC DRAFT NBMA NHRP October 15, 1993 435 procedure processReply(reply); 436 addCacheTableEntry(reply.dIPa, reply.dm, reply.routeRecord); 437 if reply.sIPa == selfIpAddr then 438 /* reply is to the NHS itself */ 439 else 440 let bestMatch == matchForwardingTable(reply.sIPa) do 441 if bestMatch then 442 if bestMatch.type != externallyLearned then 443 forwardReply(reply, bestMatch.outIf, bestMatch.outIfAddr) 444 else /* bestMatch.type == externallyLearned */ 445 /* request should never originate outside of the NBMA */ 446 end 447 end 448 end 449 end 450 end 452 The semantics of the procedures and constants used in the pseudocode 453 are explained below. 455 matchForwardingTable(ipAddress) returns the forwardingTable entry 456 whose networkLayerAddrPrefix field is the longest match for ipAddress 457 or FALSE if no match is found. 459 arp(ipAddress) resolves the NBMA address corresponding to ipAddress. 460 It returns FALSE if the resolution fails. 462 genPosAuthReply(sourceIpAddr, destinationIpAddr, destinationMask, 463 originatorIpAddr, originatorNbmaAddr) generates a positive, 464 authoritative reply with sourceIpAddr, destinationIpAddr, and 465 destinationMask in Source IP address, Destination IP address and 466 Destination mask fields, respectively. The Route record field of the 467 reply consists of one Route element that contains originatorIpAddr 468 and originatorNbmaAddr as its IP and Link layer addresses. 470 genNegAuthReply(sourceIpAddr, destinationIpAddr) and 471 genNegNonAuthReply(sourceIpAddr, destinationIpAddr) respectively 472 generate a negative, authoritative and non-authoritative reply with 473 sourceIpAddr and destinationIpAddr in Source IP address and 474 Destination IP address fields. The Destination mask field has always 475 value 0xFFFFFFFF and the route Record field is empty. 477 selfIpAddr and selfNbmaAddr denote the egress router's own IP and 478 NBMA addresses in the NBMA via which its peer NHSs can be reached. 480 requestForAuthInfo?(request) tests if request is a Request for 481 authoritative information. 483 RFC DRAFT NBMA NHRP October 15, 1993 485 matchCacheTable(ipAddr) returns a cacheTable entry whose 486 networkLayerAddr field is the best match for ipAddr or FALSE if no 487 match is found. 489 genPosNonAuthReply(sourceIpAddr, destinationIpAddr, destinationMask, 490 routeElementList) generates a positive, non-authoritative reply with 491 sourceIpAddr, destinationIpAddr, and destinationMask in Source IP 492 address, Destination IP address and Destination mask fields, 493 respectively. The Route record field of the reply is constructed 494 from routeElementList. 496 forwardRequest(request, interface, ipAddr) decrements the Hop count 497 field of request, recomputes the ICMP Checksum field, and forwards 498 request to ipAddr of interface provided that the value of the Hop 499 count field remains positive. 501 addCacheTableEntry(ipAddr, mask, routeRecord) adds a new entry to the 502 cacheTable or overwrites an existing entry whose 503 networkLayerAddrPrefix field is equal to . A new entry 504 is not added if matchCacheTable(ipAddr) returns an entry whose 505 routeElementList is equivalent to routeRecord. The 506 networkLayerAddrPrefix field of the new entry is . The 507 routeElementList field is constructed from routeRecord. In addition, 508 if the NHS processing the reply would be willing to serve as an 509 egress router for , it should add a new Route element 510 to the end of the routeElementList field. 512 forwardReply(reply, interface, ipAddr) decrements the Hop count field 513 of request, recomputes the ICMP Checksum field, and forwards request 514 to ipAddr of interface provided that the value of the Hop count field 515 remains positive. If the NHS processing the reply would be willing 516 to serve as an egress router for , it should, 517 before recomputing the Checksum field, add a new Route element 518 to the end of reply.routeRecord. 520 An NBMA terminal has, for each supported QOS, a forwardingTable and 521 one or more cacheTables. The former can be the terminal's IP 522 forwarding table and is either manually configured or filled via 523 routing information exchange with the terminal's NHSs or peer 524 routers. There is one cacheTable per connected NBMA network. If the 525 terminal's forwardingTable shows that a particular destination is 526 behind an NBMA network, the terminal first consults the corresponding 527 cacheTable. If no match is found, it generates an NHRP request to 528 the NHS pointed to by the forwardingTable entry. When the reply 529 arrives, the terminal updates the appropriate cacheTable in the same 530 way as an NHS does. 532 RFC DRAFT NBMA NHRP October 15, 1993 534 6. Discussion 536 The result of an NHRP request depends on how routing is configured 537 among the NHSs of an NBMA network. If the destination terminal is 538 directly connected to the NBMA network and the NHSs always prefer 539 NBMA routes over routes via other link layer networks, the NHRP 540 replies always return the NBMA address of the destination terminal 541 itself rather than the NBMA address of some egress router. For 542 destinations outside the NBMA network, egress routers and routers in 543 the other link layer networks should exchange routing information so 544 that the optimal egress router is always found. 546 When the NBMA next hop towards a destination is not the destination 547 terminal itself, the optimal NBMA next hop may change dynamically. 548 This can happen, for instance, when an egress router nearer to the 549 destination becomes available. To detect this change, a source 550 terminal can periodically reissue the NHRP request. Alternatively, 551 the source can be configured to receive routing information from its 552 NHSs. When it detects an improvement in the route to the 553 destination, the source can reissue the NHRP request to obtain the 554 current optimal NBMA next hop. 556 In addition to NHSs, an NBMA terminal could also be associated with 557 one or more regular routers that could act as "connectionless 558 servers" for the terminal. Then the terminal could choose to resolve 559 the NBMA next hop or just send the IP packets to one of the 560 terminal's connectionless servers. The latter option may be 561 desirable if communication with the destination is short-lived and/or 562 doesn't require much network resources. The connectionless servers 563 could, of course, be physically integrated in the NHSs by augmenting 564 them with IP switching functionality. 566 NHRP supports portability of NBMA terminals. A terminal can be moved 567 anywhere within the NBMA network and still keep its original IP 568 address as long as its NHS(s) remain the same. Requests for 569 authoritative information will always return the correct link layer 570 address. 572 References 574 [1] Address Resolution Protocol, David C. Plummer, RFC 826. 576 [2] Classical IP and ARP over ATM, Mark Laubach, Internet Draft. 578 [3] Transmission of IP datagrams over the SMDS service, J. Lawrence 579 and 580 D. Piscitello, RFC 1209. 582 RFC DRAFT NBMA NHRP October 15, 1993 584 Acknowledgements 586 We would like to thank John Burnett of Adaptive, Dennis Ferguson of 587 ANS, Joel Halpern of Network Systems, and Paul Francis of Bellcore 588 for their valuable insight and comments to earlier versions of this 589 draft. 591 Authors' Addresses 593 Juha Heinanen Ramesh Govindan 594 Telecom Finland, Bell Communications Research 595 PO Box 228, MRE 2P-341, 445 South Street 596 SF-33101 Tampere, Morristown, NJ 07960 597 Finland 599 Phone: +358 49 500 958 Phone: +1 201 829 4406 600 Email: Juha.Heinanen@datanet.tele.fi Email: rxg@thumper.bellcore.com 602 Routing over Large Clouds Working Group Juha Heinanen 603 Request for Comments: DRAFT (Telecom Finland) 604 Expires Apr 15, 1994 Ramesh Govindan 605 (Bellcore) 606 October 15, 1993 608 NBMA Next Hop Resolution Protocol (NHRP) 610 Status of this Memo 612 This document is an Internet Draft. Internet Drafts are working 613 documents of the Internet Engineering Task Force (IETF), its Areas, 614 and its Working Groups. Note that other groups may also distribute 615 working documents as Internet Drafts. 617 Internet Drafts are draft documents valid for a maximum of six 618 months. Internet Drafts may be updated, replaced, or obsoleted by 619 other documents at any time. It is not appropriate to use Internet 620 Drafts as reference material or to cite them other than as a 621 ``working draft'' or ``work in progress.'' Please check the 1id- 622 abstracts.txt listing contained in the internet-drafts Shadow 623 Directories on nic.ddn.mil, nnsc.nsf.net, nic.nordu.net, 624 ftp.nisc.sri.com, or munnari.oz.au to learn the current status of any 625 Internet Draft. 627 Abstract 629 This document describes the NBMA Next Hop Resolution Protocol (NHRP). 630 NHRP can be used by a source terminal (host or router) connected to a 631 Non-Broadcast, Multi-Access link layer (NBMA) network to find out the 632 IP and NBMA addresses of the "NBMA next hop" towards a destination 633 terminal. The NBMA next hop is the destination terminal itself, if 634 the destination is connected to the NBMA network. Otherwise, it is 635 the egress router from the NBMA network that is "nearest" to the 636 destination terminal. Although this document focuses on NHRP in the 637 context of IP, the technique is applicable to other network layer 638 protocols as well. 640 1. Introduction 642 The NBMA Next Hop Resolution Protocol (NHRP) allows a source terminal 643 (a host or router), wishing to communicate over a Non-Broadcast, 644 Multi-Access link layer (NBMA) network, to find out the IP and NBMA 645 addresses of the "NBMA next hop" towards a destination terminal. The 646 NBMA next hop is the destination terminal itself, if the destination 647 is connected to the NBMA network. Otherwise, it is the egress router 649 RFC DRAFT NBMA NHRP October 15, 1993 651 (out of the NBMA network) nearest to the destination terminal. 653 Conventional hop-by-hop IP routing may not be sufficient to resolve 654 the "NBMA next hop" towards the destination terminal. An NBMA 655 network may, in general, consist of multiple logically independent IP 656 subnets (LISs, [3]); IP routing would only resolve the next hop LIS 657 towards the destination terminal. 659 Once the NBMA next hop has been resolved, the source may either start 660 sending IP packets to the destination (in a connectionless NBMA 661 network such as SMDS) or may first establish a connection to the 662 destination with the desired bandwidth and QOS characteristics (in a 663 connection oriented NBMA network such as ATM). 665 An NBMA network can be non-broadcast either because it technically 666 doesn't support broadcasting (e.g. an X.25 network) or because 667 broadcasting is not feasible for one reason or another (e.g. an SMDS 668 broadcast group or an extended Ethernet would be too large). 670 2. Protocol Overview 672 In this section, we briefly describe how a source S uses NHRP to 673 determine the "NBMA next hop" to destination D. S first determines 674 the next hop to D through normal routing processes. If this next hop 675 is reachable through its NBMA interface, S formulates an NHRP request 676 containing the source and destination IP addresses and QOS 677 information. S then forwards the request to an entity called the 678 "Next Hop Server" (NHS). 680 For administrative and policy reasons, a physical NBMA network may be 681 partitioned into several disjoint logical NBMA networks (discussed 682 later in this section); NHSs cooperatively resolve the NBMA next hop 683 within their logical NBMA network. Unless otherwise specified, we use 684 NBMA network to mean logical NBMA network. 686 Each NHS "serves" a pre-configured set of terminals and peers with a 687 pre-configured set of NHSs, which all belong to the same NBMA 688 network. An NHS exchanges routing information with its peers (and 689 possibly with the terminals it serves) using regular routing 690 protocols. (However, an NHS, unless it is also an egress/ingress 691 router, need not necessarily be able to switch regular IP packets). 692 This exchange is used to construct a forwarding table per QOS in 693 every NHS. The forwarding table determines the next hop NHS towards 694 the NHRP request's destination. This next hop NHS may depend on the 695 request's QOS information. 697 After receiving an NHRP request, the NHS checks if it "serves" D. If 698 so, the NHS resolves D's NBMA address, using mechanisms beyond the 700 RFC DRAFT NBMA NHRP October 15, 1993 702 scope of this document (examples of such mechanisms include ARP [1, 703 2] and pre-configured tables). The NHS then either forwards the NHRP 704 request to D or generates a positive NHRP reply on its behalf. The 705 reply contains D's (D is S's NBMA next hop) IP and NBMA address and 706 is sent back to S. NHRP replies usually traverse the same sequence 707 of NHSs as the NHRP request (in reverse order, of course). 709 If the NHS does not serve D, it extracts from its forwarding table 710 the next hop towards D. If no such next hop entry is found, the NHS 711 generates a negative NHRP reply. 713 If the next hop is behind the NHS's NBMA interface, the NHS forwards 714 the NHRP request to the next hop. If the next hop is behind some 715 other interface, the NHS may be willing to act as an egress router 716 for traffic bound to D. In that case, the NHS generates a positive 717 NHRP reply containing its own IP and NBMA address (i.e., the NHS is 718 the NBMA next hop from S to D). 720 An NHS receiving an NHRP reply may cache the NBMA next hop 721 information contained therein. To a subsequent NHRP request, this 722 NHS might respond with the cached, non-authoritative, NBMA next hop 723 or with cached negative information. If a communication attempt based 724 on non-authoritative information fails, a source terminal can choose 725 to send an authoritative NHRP request. NHSs never respond to 726 authoritative NHRP requests with cached information. 728 NHRP requests and replies never cross the borders of a logical NBMA 729 network. Thus, IP traffic out of and into a logical NBMA network 730 always traverses an IP router at its border. Network layer filtering 731 can then be implemented at these border routers. 733 NHRP provides a mechanism to aggregate NBMA next hop information in 734 NHS caches. Suppose that NHS X is the NBMA next hop from S to D. 735 Suppose further that X is an egress router for all terminals sharing 736 an IP address prefix with D. When X generates an NHRP reply in 737 response to a request, it may replace the IP address of D with this 738 prefix. The prefix to egress router mapping in the reply is cached 739 in all NHSs on the path of the reply. A subsequent (non- 740 authoritative) NHRP request for some destination that shares an IP 741 address prefix with D can be satisfied with this cached information. 743 To dynamically detect link-layer filtering in NBMA networks, NHRP 744 incorporates a "Route record" in replies. This Route record contains 745 the network and link layer addresses of intermediate NHSs willing to 746 route packets from the source to the destination prefix. When a 747 source terminal is unable to open a connection to the responder, it 748 attempts to do so successively with one of the NHSs in the Route 749 record until it succeeds. This approach finds the optimal best hop in 751 RFC DRAFT NBMA NHRP October 15, 1993 753 the presence of link-layer filtering. 755 3. Configuration 757 Terminals 759 To participate in NHRP, a terminal connected to an NBMA network 760 should to be configured with the IP address(es) of its NHS(s). 761 These NHS(s) may be physically located on the terminal's default or 762 peer routers, so their addresses may be obtained from the 763 terminal's IP forwarding table. If the terminal is attached to 764 several link layer networks (including logical NBMA networks), it 765 should also be configured to receive routing information from its 766 NHS(s) and peer routers so that the terminal can determine which IP 767 networks are reachable through which link layer networks. 769 Next Hop Servers 771 An NHS is configured with a set of IP address prefixes that 772 correspond to the IP addresses of the terminals it is serving. 773 Moreover, the NHS must be configured to exchange routing 774 information with its peer NHSs (if any). If a served terminal is 775 attached to several link layer networks, the NHS may also need to 776 be configured to advertize routing information to such terminals. 778 If an NHS is acting as an egress router for terminals connected to 779 other link layer networks than the NBMA network, the NHS must, in 780 addition to the above, be configured to exchange routing 781 information between the NBMA network and these other link layer 782 networks. 784 In all cases, routing information is exchanged using regular 785 intra-domain and/or inter-domain routing protocols. 787 4. Packet Formats 789 NHRP requests and replies are carried as ICMP messages. This section 790 describes the packet formats of NHRP requests and replies: 792 NHRP Request 794 RFC DRAFT NBMA NHRP October 15, 1993 796 0 1 2 3 797 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 798 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 799 | Type | Code | Checksum | 800 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 801 | Hop Count | Unused | 802 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 803 | Destination IP address | 804 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 805 | Source IP address | 806 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 808 Type 809 19 811 Code 812 A response to an NHRP request may contain cached information. If an 813 authoritative answer is desired, then code 2 (NHRP request for 814 authoritative information) should be used. Otherwise, a code value of 1 815 (NHRP request) should be used. 817 Hop Count 818 The Hop count indicates the maximum number of NHSs that a request 819 or reply is allowed to traverse before being discarded. 821 Source and Destination IP Addresses 822 Respectively, these are the IP addresses of the NHRP request 823 initiator and the terminal for which the NBMA next hop is desired. 825 NHRP Reply 827 0 1 2 3 828 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 829 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 830 | Type | Code | Checksum | 831 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 832 | Hop Count | Unused | Route record length | 833 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 834 | Source IP address | 835 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 836 | Destination IP address | 837 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 838 | Destination mask | 839 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 840 | | 841 | NHRP route record (variable) | 842 | | 843 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 845 RFC DRAFT NBMA NHRP October 15, 1993 847 Type 848 20 850 Code 851 NHRP replies may be positive or negative. An NHRP positive, 852 non-authoritative reply carries a code of 1, while a positive, 853 authoritative reply carries a code of 2. An NHRP negative, 854 non-authoritative reply carries a code of 3 and a negative, 855 authoritative reply carries a code of 4. An NHS is not allowed to 856 reply to an NHRP request for authoritative information with cached 857 information, but may do so for an NHRP Request. 859 Route Record Length 860 The length in words of the NHRP route record (see below). 862 Source IP Address 863 The address of the initiator of the corresponding NHRP request. 865 Destination IP Address and Mask 866 If the NHRP Request's destination is on the NBMA, the reply contains 867 that destination address and a mask of all 1s. Otherwise, the 868 responder may choose to act as the egress router for all terminals in 869 the destination's subnet. If so, the reply contains a prefix of the 870 requested destination IP address and the corresponding mask. 872 NHRP Route Record 873 The NHRP route record is a list of NHRP "Route elements" for NHSs on 874 the path of a positive NHRP reply. Only NHSs that are willing to act 875 as egress routers for packets from the source to the destination insert 876 a Route element in the NHRP reply. Negative replies do not carry 877 Route elements. 879 The first Route element is always that of the destination terminal or, 880 if the destination is not directly attached to the NBMA, that of the 881 responding egress router. Each Route element is formatted as follows: 883 0 1 2 3 884 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 885 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 886 | IP address | 887 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 888 | LL length | Link Layer (LL) address | 889 +-+-+-+-+-+-+-+-+-+ | 890 | (variable length) | 891 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 893 The LL length field is the length of the link layer address in 894 bits. The LL address itself is zero-filled to the nearest 32-bit 896 RFC DRAFT NBMA NHRP October 15, 1993 898 boundary. 900 On the reply path, an NHS willing to route packets from source to 901 the destination prefix should append its Route element to the 902 current Route Record, adjust the Route record length appropriately, 903 and recompute the ICMP checksum. The Route record is used to 904 discover link layer filters, as described in Section 2. 906 If the first Route element's IP address and the destination's IP 907 address differ, the source terminal may assume that the reply was 908 generated by an egress router. 910 An NHS may cache replies containing a Route record. Subsequently, 911 when it responds to an NHRP request with the cached reply, 912 intermediate NHSs on the path to the initiator may attach Route 913 elements to the reply. 915 5. Protocol Operation 917 The external behavior of an NHS may be described in terms of two 918 procedures (processRequest and processReply) operating on two tables 919 (forwardingTable and cacheTable). In an actual implementation, the 920 code and data structures may be realized differently. 922 Each NHS has for each supported QOS an NHRP forwardingTable 923 consisting of entries with the fields: 925 927 In case the NHS is also a host or serving as a router, the NHRP 928 forwarding table may be integrated with the normal IP forwarding 929 table of the NHS. 931 The networkLayerAddrPrefix field identifies a set of network layer 932 addresses known to the NHS. It consists of two subfields . 935 The type field indicates the type of the networkLayerAddrPrefix. The 936 possible values are: 938 - locallyServed: The NHS is itself serving the 939 networkLayerAddrPrefix. The outIf field denotes the NBMA interface 940 via which the served terminals can be reached and the outIfAddr 941 field has no meaning. Such a forwardingTable entry has been 942 created by manual configuration. 944 - nhsLearned: The NHS has learned about the networkLayerAddrPrefix 945 from another NHS. The outIf and outIfAddr fields, respectively, 947 RFC DRAFT NBMA NHRP October 15, 1993 949 denote the NBMA interface and IP address of this next hop NHS. 950 Such a forwardingTable entry is a result of network layer address 951 prefix information exchange with one of the NHS's peers. 953 - externallyLearned: The NHS has learned about the 954 networkLayerAddrPrefix via normal IP routing from outside of the 955 NBMA network. In this case, the NHS may act as an egress router 956 for the terminals sharing the networkLayerAddrPrefix. The outIf and 957 outIfAddr fields, respectively, denote the interface and IP address 958 of the next hop router. If the outIfAddr field is empty, the 959 networkLayerAddrPrefix is assumed to be directly connected to the 960 outIf of the NHS. 962 The protocol used to exchange networkLayerAddrPrefix information 963 among the NHSs or between NHSs and their peer routers can be any 964 regular IP intra-domain or inter-domain routing protocol. 966 In addition to the forwardingTable, each NHS has for each supported 967 QOS an NHRP cacheTable consisting of entries with the fields: 969 971 The entries in the cacheTable are learned from NHRP replies 972 traversing the NHS. The networkLayerAddrPrefix field identifies a set 973 of IP addresses sharing a common Route record. The 974 networkLayerAddrPrefix field consists of two subfields . The routeElementList field is either empty (in case of a 976 negative cache entry) or consists of a list of subfields of the form 977 . 979 The cacheTable entries could also include a timeStamp field to be 980 used to age cacheTable entries after a certain hold period. 982 The following pseudocode defines how NBMA NHRP requests and replies 983 are processed by an NHS. 985 RFC DRAFT NBMA NHRP October 15, 1993 987 procedure processRequest(request); 988 let bestMatch == matchForwardingTable(request.dIPa) do 989 if bestMatch then 990 if bestMatch.type == locallyServed then 991 let nbmaAddr == arp(request.dIPa) do 992 if nbmaAddr then 993 genPosAuthReply(request.sIPa, 994 request.dIPa, 0xFFFFFFFF, 995 request.dIPa, nbmaAddr) 996 else 997 genNegAuthReply(request.sIPa, request.dIPa) 998 end 999 end 1000 elseif bestMatch.type == nhsLearned then 1001 if not requestForAuthInfo?(request) then 1002 let cacheMatch == matchCacheTable(request.dIPa) do 1003 if cacheMatch then 1004 if cacheMatch.routeElementList == EMPTY then 1005 genNegNonAuthReply(request.sIPa, request.dIPa) 1006 else 1007 genPosNonAuthReply(request.sIPa, 1008 cacheMatch.networkLayerAddrPrefix.ipAddr, 1009 cacheMatch.networkLayerAddrPrefix.mask, 1010 cacheMatch.routeElementList); 1011 end 1012 else /* no cache match */ 1013 forwardRequest(request, bestMatch.OutIf, 1014 bestMatch.OutIfAddr) 1015 end 1016 end 1017 else /* request for authoritative information */ 1018 forwardRequest(request, bestMatch.OutIf, 1019 bestMatch.OutIfAddr) 1020 end 1021 else /* bestMatch.type == externallyLearned */ 1022 genPosAuthReply(request.sIPa, 1023 bestMatch.networkLayerAddrPrefix.ipAddr, 1024 bestMatch.networkLayerAddrPrefix.mask, 1025 selfIpAddr, selfNbmaAddr) 1026 end 1027 else /* no match in forwardingTable */ 1028 genNegAuthReply(request.sIPa, request.dIPa) 1029 end 1030 end 1031 end 1033 RFC DRAFT NBMA NHRP October 15, 1993 1035 procedure processReply(reply); 1036 addCacheTableEntry(reply.dIPa, reply.dm, reply.routeRecord); 1037 if reply.sIPa == selfIpAddr then 1038 /* reply is to the NHS itself */ 1039 else 1040 let bestMatch == matchForwardingTable(reply.sIPa) do 1041 if bestMatch then 1042 if bestMatch.type != externallyLearned then 1043 forwardReply(reply, bestMatch.outIf, bestMatch.outIfAddr) 1044 else /* bestMatch.type == externallyLearned */ 1045 /* request should never originate outside of the NBMA */ 1046 end 1047 end 1048 end 1049 end 1050 end 1052 The semantics of the procedures and constants used in the pseudocode 1053 are explained below. 1055 matchForwardingTable(ipAddress) returns the forwardingTable entry 1056 whose networkLayerAddrPrefix field is the longest match for ipAddress 1057 or FALSE if no match is found. 1059 arp(ipAddress) resolves the NBMA address corresponding to ipAddress. 1060 It returns FALSE if the resolution fails. 1062 genPosAuthReply(sourceIpAddr, destinationIpAddr, destinationMask, 1063 originatorIpAddr, originatorNbmaAddr) generates a positive, 1064 authoritative reply with sourceIpAddr, destinationIpAddr, and 1065 destinationMask in Source IP address, Destination IP address and 1066 Destination mask fields, respectively. The Route record field of the 1067 reply consists of one Route element that contains originatorIpAddr 1068 and originatorNbmaAddr as its IP and Link layer addresses. 1070 genNegAuthReply(sourceIpAddr, destinationIpAddr) and 1071 genNegNonAuthReply(sourceIpAddr, destinationIpAddr) respectively 1072 generate a negative, authoritative and non-authoritative reply with 1073 sourceIpAddr and destinationIpAddr in Source IP address and 1074 Destination IP address fields. The Destination mask field has always 1075 value 0xFFFFFFFF and the route Record field is empty. 1077 selfIpAddr and selfNbmaAddr denote the egress router's own IP and 1078 NBMA addresses in the NBMA via which its peer NHSs can be reached. 1080 requestForAuthInfo?(request) tests if request is a Request for 1081 authoritative information. 1083 RFC DRAFT NBMA NHRP October 15, 1993 1085 matchCacheTable(ipAddr) returns a cacheTable entry whose 1086 networkLayerAddr field is the best match for ipAddr or FALSE if no 1087 match is found. 1089 genPosNonAuthReply(sourceIpAddr, destinationIpAddr, destinationMask, 1090 routeElementList) generates a positive, non-authoritative reply with 1091 sourceIpAddr, destinationIpAddr, and destinationMask in Source IP 1092 address, Destination IP address and Destination mask fields, 1093 respectively. The Route record field of the reply is constructed 1094 from routeElementList. 1096 forwardRequest(request, interface, ipAddr) decrements the Hop count 1097 field of request, recomputes the ICMP Checksum field, and forwards 1098 request to ipAddr of interface provided that the value of the Hop 1099 count field remains positive. 1101 addCacheTableEntry(ipAddr, mask, routeRecord) adds a new entry to the 1102 cacheTable or overwrites an existing entry whose 1103 networkLayerAddrPrefix field is equal to . A new entry 1104 is not added if matchCacheTable(ipAddr) returns an entry whose 1105 routeElementList is equivalent to routeRecord. The 1106 networkLayerAddrPrefix field of the new entry is . The 1107 routeElementList field is constructed from routeRecord. In addition, 1108 if the NHS processing the reply would be willing to serve as an 1109 egress router for , it should add a new Route element 1110 to the end of the routeElementList field. 1112 forwardReply(reply, interface, ipAddr) decrements the Hop count field 1113 of request, recomputes the ICMP Checksum field, and forwards request 1114 to ipAddr of interface provided that the value of the Hop count field 1115 remains positive. If the NHS processing the reply would be willing 1116 to serve as an egress router for , it should, 1117 before recomputing the Checksum field, add a new Route element 1118 to the end of reply.routeRecord. 1120 An NBMA terminal has, for each supported QOS, a forwardingTable and 1121 one or more cacheTables. The former can be the terminal's IP 1122 forwarding table and is either manually configured or filled via 1123 routing information exchange with the terminal's NHSs or peer 1124 routers. There is one cacheTable per connected NBMA network. If the 1125 terminal's forwardingTable shows that a particular destination is 1126 behind an NBMA network, the terminal first consults the corresponding 1127 cacheTable. If no match is found, it generates an NHRP request to 1128 the NHS pointed to by the forwardingTable entry. When the reply 1129 arrives, the terminal updates the appropriate cacheTable in the same 1130 way as an NHS does. 1132 RFC DRAFT NBMA NHRP October 15, 1993 1134 6. Discussion 1136 The result of an NHRP request depends on how routing is configured 1137 among the NHSs of an NBMA network. If the destination terminal is 1138 directly connected to the NBMA network and the NHSs always prefer 1139 NBMA routes over routes via other link layer networks, the NHRP 1140 replies always return the NBMA address of the destination terminal 1141 itself rather than the NBMA address of some egress router. For 1142 destinations outside the NBMA network, egress routers and routers in 1143 the other link layer networks should exchange routing information so 1144 that the optimal egress router is always found. 1146 When the NBMA next hop towards a destination is not the destination 1147 terminal itself, the optimal NBMA next hop may change dynamically. 1148 This can happen, for instance, when an egress router nearer to the 1149 destination becomes available. To detect this change, a source 1150 terminal can periodically reissue the NHRP request. Alternatively, 1151 the source can be configured to receive routing information from its 1152 NHSs. When it detects an improvement in the route to the 1153 destination, the source can reissue the NHRP request to obtain the 1154 current optimal NBMA next hop. 1156 In addition to NHSs, an NBMA terminal could also be associated with 1157 one or more regular routers that could act as "connectionless 1158 servers" for the terminal. Then the terminal could choose to resolve 1159 the NBMA next hop or just send the IP packets to one of the 1160 terminal's connectionless servers. The latter option may be 1161 desirable if communication with the destination is short-lived and/or 1162 doesn't require much network resources. The connectionless servers 1163 could, of course, be physically integrated in the NHSs by augmenting 1164 them with IP switching functionality. 1166 NHRP supports portability of NBMA terminals. A terminal can be moved 1167 anywhere within the NBMA network and still keep its original IP 1168 address as long as its NHS(s) remain the same. Requests for 1169 authoritative information will always return the correct link layer 1170 address. 1172 References 1174 [1] Address Resolution Protocol, David C. Plummer, RFC 826. 1176 [2] Classical IP and ARP over ATM, Mark Laubach, Internet Draft. 1178 [3] Transmission of IP datagrams over the SMDS service, J. Lawrence 1179 and 1180 D. Piscitello, RFC 1209. 1182 RFC DRAFT NBMA NHRP October 15, 1993 1184 Acknowledgements 1186 We would like to thank John Burnett of Adaptive, Dennis Ferguson of 1187 ANS, Joel Halpern of Network Systems, and Paul Francis of Bellcore 1188 for their valuable insight and comments to earlier versions of this 1189 draft. 1191 Authors' Addresses 1193 Juha Heinanen Ramesh Govindan 1194 Telecom Finland, Bell Communications Research 1195 PO Box 228, MRE 2P-341, 445 South Street 1196 SF-33101 Tampere, Morristown, NJ 07960 1197 Finland 1199 Phone: +358 49 500 958 Phone: +1 201 829 4406 1200 Email: Juha.Heinanen@datanet.tele.fi Email: rxg@thumper.bellcore.com