RFC 1735

NBMA Address Resolution Protocol (NARP)

📅 published December 1994, from ietf

NBMA Address Resolution Protocol (NARP) 🦋

okay bestie, this is RFC 1735 and it's giving early-days experimental energy ✨ It was written by J. Heinanen (Telecom Finland) and R. Govindan (ISI) in December 1994 for the Network Working Group. The category is Experimental. The title block doesn't list anything it obsoletes or updates, so it's standing on its own 💅

Status of this Memo ✨

so the memo says it defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. They're asking for discussion and suggestions for improvement, and distribution of the memo is unlimited 🌸

IESG Note 🙈

the IESG wants everyone to know that this work isn't an Internet standard. It's an early stage in the ongoing effort to sort out direct communication over NBMA subnets. It's a suitable experimental protocol for early deployment, and it's expected to be superseded by other work being developed within the IETF 🧚

Abstract 💜

this document describes the NBMA Address Resolution Protocol (NARP). NARP lets a source terminal (a host or router) that's connected to a Non-Broadcast, Multi-Access link layer (NBMA) network find the NBMA addresses of a destination terminal, as long as that destination is connected to the same NBMA network. The doc focuses on NARP in the context of IP, but the technique also works for other network layer protocols. This RFC is a product of the Routing over Large Clouds Working Group of the IETF ✨

1. Introduction ✨

okay so NARP is for a source terminal (a host or router) that wants to talk over a Non-Broadcast, Multi-Access link layer (NBMA) network. It helps the source find out the NBMA addresses of a destination terminal, but only if that destination is on the same NBMA network as the source 🦋

a regular address resolution protocol like ARP [1, 2] for IP might not be enough to resolve the destination's NBMA address. That's because ARP only works for terminals on the same IP subnetwork. An NBMA network can be made up of multiple logically independent IP subnets (LISs, [3]), so it's a whole different vibe 😭

once the destination's NBMA address is resolved, the source has two options. It can start sending IP packets right away (on a connectionless NBMA network like SMDS). Or it can set up a connection to the destination first, with the bandwidth and QOS characteristics it wants (on a connection oriented NBMA network like ATM) 💅

an NBMA network can be non-broadcast for two reasons. Either it technically can't do broadcasting (like an X.25 network), or broadcasting isn't feasible for some reason (like an SMDS broadcast group or an extended Ethernet that would be way too large) 🙈

2. Protocol Overview 🔥

in this section we give a quick rundown of how a source S uses NARP to figure out the NBMA address of a destination D, or to find out that no such address exists. S first checks whether D is on the same IP subnetwork as S itself. If it is, S resolves D's NBMA address the usual way, with something like ARP [1, 2] or preconfigured tables. If D is on a different subnetwork, S builds a NARP request that contains the source and destination IP addresses. Then S forwards that request to an entity called the "NBMA ARP Server" (NAS) 🎀

for administrative and policy reasons, a physical NBMA network might be split into several disjoint logical NBMA networks. The NASs work together to resolve the NBMA next hop within their logical NBMA network. From here on, when we say "NBMA network," we always mean a logical NBMA network 🌈 If S is connected to several NBMA networks, it should have at least one NAS in each of them. To know which NAS(s) to ask for which destination addresses, a multi-homed S should also be configured to receive reachability information from its NASs 🧚

each NAS "serves" a preconfigured set of terminals, and it peers with a preconfigured set of NASs, all of which belong to the same NBMA network. A NAS can also peer with routers outside the NBMA it serves. A NAS swaps reachability information with its peers (and maybe with the terminals it serves) using regular routing protocols. That exchange is used to build a forwarding table in every NAS. The forwarding table tells the NAS which next hop NAS to send a NARP request toward the request's destination, or which next hop router outside the NBMA to use 💖

when a NAS gets a NARP request, it checks whether it "serves" D. If it does, the NAS resolves D's NBMA address using mechanisms that are outside the scope of this document. Examples include ARP [1, 2] and preconfigured tables. Then the NAS either forwards the NARP request on to D, or it generates a positive NARP reply on D's behalf. The reply contains D's IP and NBMA addresses and gets sent back to S. NARP replies usually go through the same sequence of NASs as the request did, just in reverse order, of course 🦋

if the NAS doesn't serve D, it pulls the next hop toward D out of its forwarding table. If that next hop is a peer NAS, the NAS forwards the NARP request to it. If the next hop is a peer router outside the served NBMA, or if there's no next hop entry at all, the NAS generates a negative NARP reply 💀

a NAS that receives a NARP reply can cache the NBMA address information in it. If a later NARP request for the same target address doesn't ask for an authoritative reply, the caching NAS can answer with the cached non-authoritative NBMA address, or with cached negative information. A well behaving terminal should always accept a non-authoritative reply first. Only if a communication attempt based on that non-authoritative information fails can the terminal choose to send another request, this time asking for an authoritative reply ✨

NARP requests and replies never cross the borders of an NBMA network. So IP traffic going out of and coming into an NBMA network always passes through an IP router at its border. Network layer filtering can then be implemented at those border routers 🔥

3. Configuration 🎀

Terminals

to take part in NARP, a terminal connected to an NBMA network should be configured with the IP address(es) of its NAS(s). If the terminal is attached to several NBMA networks, it should also be configured to receive reachability information from its NAS(s). That way it can tell which IP destinations are reachable through which NBMA networks 🫶

NBMA ARP Servers

a NAS is configured with a set of IP address prefixes that match the IP addresses of the terminals it serves. The NAS also has to be configured to exchange reachability information with its peer NASs, if it has any. It may additionally be configured to exchange reachability information with routers outside the NBMA it serves. And finally, if a served terminal is attached to several NBMA networks, the NAS may need to be configured to send reachability information to that terminal 👑

4. Packet Formats ✨

okay so NARP requests and replies ride around inside IP packets with protocol type 54 🎀 this section walks through what each packet looks like, bestie 💅

NARP Request

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |    Version    |   Hop Count   |          Checksum             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Type      |    Code       |           Unused              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    Destination IP address                     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Source IP address                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | NBMA length   |                NBMA address                   |
      +-+-+-+-+-+-+-+-+                                               |
      |                  (variable length)                            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Version

The NARP version number. Currently this value is 1 🦋

Hop Count

The Hop count is the max number of NASs that a request or reply is allowed to traverse before it gets tossed 🗑️ so it's like a little countdown, iykyk 💀

Checksum

It's the standard IP checksum over the entire NARP packet, starting with the fixed header 🔢

Type

The NARP packet type. The NARP Request has a Type code of 1 🌸

Code

A response to an NARP request may contain cached information. If you want an authoritative answer, then code 2 (NARP Request for Authoritative Information) should be used. Otherwise, a code value of 1 (NARP Request) should be used ✨

Source and Destination IP Addresses

Respectively, these are the IP addresses of the NARP requestor and the target terminal that you want the NBMA address for. Main character energy 👑

NBMA Length and NBMA Address

The NBMA length field is the length of the NBMA address of the source terminal, measured in bits. The NBMA address itself is zero-filled out to the nearest 32-bit boundary 🧚

NARP Reply

       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
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |    Version    |   Hop Count   |          Checksum             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |     Type      |      Code     |           Unused              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                    Destination IP address                     |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                      Source IP address                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      | NBMA length   |                NBMA address                   |
      +-+-+-+-+-+-+-+-+                                               |
      |                  (variable length)                            |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Version

Same deal as before: the NARP version number, currently 1 💖

Hop Count

The Hop count is the max number of NASs that a request or reply is allowed to traverse before it gets discarded. Same vibes as the request, bestie 🫶

Checksum

The standard IP checksum over the entire NARP packet, starting with the fixed header ✨

Type

The NARP packet type. The NARP Reply has a Type code of 2 🎀

Code

NARP replies can be positive or negative, and they can also be authoritative or not, so there are four flavours 🍓

  • A Positive, Non-authoritative Reply carries a code of 1.
  • A Positive, Authoritative Reply carries a code of 2.
  • A Negative, Non-authoritative Reply carries a code of 3.
  • A Negative, Authoritative reply carries a code of 4.

The general rule is that a NAS should not reply to an NARP request for authoritative information with cached information, but it may do so for a plain NARP request. A NAS implementation is allowed to relax this rule and return non-authoritative information even when authoritative was desired, but only if the NAS becomes heavily loaded and the cached information was updated very recently 🌈

This is the one spot where the rule bends. Cached info can sneak into an authoritative answer, but only when the NAS is drowning and the cache is fresh. Otherwise, stick to the rule 🙈

Source and Destination IP Address

Respectively, these are the IP addresses of the NARP requestor and the target terminal that the NBMA address is wanted for 🦋

NBMA Length and NBMA Address

The NBMA length field is the length of the NBMA address of the destination terminal, measured in bits. The NBMA address itself is zero-filled to the nearest 32-bit boundary. Negative replies do not carry the NBMA length or the NBMA address field 💀

A NAS may cache NBMA replies. 🧚

5. Protocol Operation ✨

Okay bestie, so the outside behavior of a NAS can be described with two procedures, processRequest and processReply, which work on two tables, forwardingTable and cacheTable. 🧚 A real implementation can build its code and data structures differently, so don't panic if yours looks different. 💅

Each NAS has a forwardingTable with entries shaped like this:

<networkLayerAddrPrefix, type, outIf, outIfAddr>

The networkLayerAddrPrefix field is the set of IP addresses the NAS knows about. It has two subfields, <ipAddr, mask>. 🎀

The type field tells you what kind of prefix you're looking at. The possible values are:

  • locallyServed: The NAS is serving this prefix itself. The outIf field is the NBMA interface where the served terminals can be reached, and the outIfAddr field has no meaning here. These entries get created by manual configuration. 🏠
  • nasLearned: The NAS learned about the prefix from another NAS. outIf and outIfAddr are the NBMA interface and IP address of this next hop NAS. These entries come from prefix information exchange with one of the NAS's peer NASs. 🤝
  • externallyLearned: The NAS learned about the prefix from a peer router outside the served NBMA. outIf and outIfAddr are the NBMA interface and IP address of this next hop NAS. These entries come from prefix information exchange with one of the NAS's peer routers. 🌍

The protocol used to swap networkLayerAddrPrefix info between the NASs can be any regular IP intra-domain or inter-domain routing protocol. Pick your favourite, it's giving flexibility. ✨

Each NAS also has a NARP cacheTable, with entries shaped like this:

<networkLayerAddr, nbmaAddr, timeStamp>

The cacheTable entries are learned from NARP replies that travel through the NAS. A negative cache entry has an empty nbmaAddr. The timeStamp field records when the entry was created or last updated. That's how the NAS figures out if an entry is super fresh, and how it ages out the old ones after a certain hold period. ⏳

Here's how a NAS processes NBMA NARP requests and replies. Bookmark this one, it's the main event. 👑

  procedure processRequest(request);
    let bestMatch == matchForwardingTable(request.dIPa) do
       if bestMatch then
          if bestMatch.type == locallyServed then
             let nbmaAddr == arp(request.dIPa) do
                if nbmaAddr then
                   genPosAuthReply(request.sIPa, request.dIPa, nbmaAddr)
                else
                   genNegAuthReply(request.sIPa, request.dIPa)
                end
             end
          elseif bestMatch.type == nasLearned then
             if not requestForAuthInfo?(request) or
                   realBusyRightNow?() then
                let cacheMatch == matchCacheTable(request.dIPa) do
                   if cacheMatch and
                         (not requestForAuthInfo?(request) or
                            realRecentCacheEntry?(cacheMatch)) then
                      if cacheMatch.nbmaAddr == EMPTY then
                         genNegNonAuthReply(request.sIPa, request.dIPa)
                      else
                         genPosNonAuthReply(request.sIPa, request.dIPa,

                            cacheMatch.nbmaAddr)
                      end
                   else /* no cache match */
                      forwardRequest(request, bestMatch.OutIf,
                         bestMatch.OutIfAddr)
                   end
                end
             else /* request for authoritative information */
                forwardRequest(request, bestMatch.OutIf,
                   bestMatch.OutIfAddr)
             end
          else /* bestMatch.type == externallyLearned */
             genNegAuthReply(request.sIPa, request.dIPa)
          end
       else /* no match in forwardingTable */
          genNegAuthReply(request.sIPa, request.dIPa)
       end
    end
  end

  procedure processReply(reply);
    addCacheTableEntry(reply.dIPa, reply.nbmaAddr, currentTime);
    if reply.sIPa == selfIpAddr then
       /* reply is to the NAS itself */
    else
       let bestMatch == matchForwardingTable(reply.sIPa) do
          if bestMatch then
             forwardReply(reply, bestMatch.outIf, bestMatch.outIfAddr)
          end
       end
    end
  end

Now for the semantics of the functions in that pseudocode. Don't worry, it's less scary than it looks! 🙈

  • matchForwardingTable(ipAddress): returns the forwardingTable entry whose networkLayerAddrPrefix is the longest match for ipAddress, or FALSE if nothing matches. 🔍
  • arp(ipAddress): resolves the NBMA address for ipAddress. It returns FALSE if the resolution fails.
  • genPosAuthReply(sourceIpAddr, destIpAddr, destNbmaAddr) and genPosNonAuthReply(sourceIpAddr, destIpAddr, destNbmaAddr): generate a positive, authoritative and a non-authoritative reply, with sourceIpAddr, destIpAddr and destNbmaAddr going into the Source IP address, Destination IP address and NBMA Address fields.
  • genNegAuthReply(sourceIpAddr, destIpAddr) and genNegNonAuthReply(sourceIpAddr, destIpAddr): generate a negative, authoritative and a non-authoritative reply, with sourceIpAddr and destIpAddr going into the Source IP address and Destination IP address fields.
  • requestForAuthInfo?(request): tests whether the request is a Request for authoritative information.
  • realBusyRightNow?(): returns TRUE if the NAS is heavily loaded and FALSE otherwise.
  • realRecentCacheEntry?(cacheTableEntry): returns TRUE if the cacheTableEntry was updated very recently and FALSE otherwise.
  • matchCacheTable(ipAddr): returns a cacheTable entry whose networkLayerAddr field equals ipAddr, or FALSE if no match is found.
  • forwardRequest(request, interface, ipAddr): decrements the Hop count field of request, recomputes the NARP Checksum field, and forwards request to ipAddr of interface, as long as the Hop count field stays positive. 🚀
  • addCacheTableEntry(ipAddr, nbmaAddr, time): adds a new entry to the cacheTable, or overwrites an existing entry whose networkLayerAddr field equals ipAddr.
  • forwardReply(reply, interface, ipAddr): decrements the Hop count field of request, recomputes the NARP Checksum field, and forwards reply to ipAddr of interface, as long as the Hop count field stays positive.

Terminals get the glow-up too! 🦋 Like NASs, each NBMA terminal has a forwardingTable and a cacheTable. The forwardingTable is either manually configured, or filled in through reachability information exchange with the terminal's NASs or peer routers.

When a terminal wants the NBMA address of a particular destination terminal, it first checks for a matching entry in its forwardingTable. If there isn't one, the destination is unreachable and the terminal gives up. 😭 If a forwardingTable entry is found, and the next hop belongs to one of the terminal's NASs, the terminal then checks its cacheTable for the NBMA address. If there's no cache match, the terminal sends a NARP request to the next hop NAS. If the reply is positive, the terminal learns the NBMA address and updates its cacheTable with the new info. ✨

6. Discussion 💬

The NARP semantics are super similar to the ATMARP semantics described in [2]. Honestly, it's giving sibling energy. There are only two actual differences:

  • NARP requests and replies include a hop count, which stops them from looping forever if the NAS routing is misconfigured. 🔁
  • NARP requests and replies tell authoritative and non-authoritative information apart. 🧐

Here's the wishlist moment. To keep the NBMA terminals as simple as possible, it would be desirable to extend the ATMARP protocol a little further so it could also be used as the terminal-NAS protocol. This could be easily done just by adding three new operation codes to ATMARP to cover the different kinds of queries and responses. NARP would then become the NAS-NAS protocol. And if the NASs are co-located with the "classical" ATM ARP servers, the terminals wouldn't need to make any distinction between local and foreign IP subnetworks. Simple, clean, iconic. 👑

The NASs can also act as "connectionless servers" for the terminal, by advertising to it all destinations, whether they're inside or outside the served NBMA. Then the terminal can choose either to try resolving the NBMA address of the destination, or just send the IP packets to the NAS. The second option might be the move if the communication is short-lived and/or doesn't need much network resources. 🌸

NARP also supports portability of NBMA terminals. A terminal can be moved anywhere within the NBMA network and still keep its original IP address, as long as its NAS(s) stay the same. Requests for authoritative information will always return the correct NBMA address. 🎀💖

References 📚

[1] Plummer, D., "An Ethernet Address Resolution Protocol - or - Converting Network Protocol Addresses to 48.bit Ethernet Address for Transmission on Ethernet Hardware", STD 37, RFC 826, MIT, November 1982.

[2] Laubach, M., "Classical IP and ARP over ATM", RFC 1577, Hewlett-Packard Laboratories, January 1994.

[3] Piscitello, D., and J. Lawrence, "Transmission of IP Datagrams over the SMDS Service, RFC 1209, Bell Communications Research, March 1991.

Acknowledgements 🫶

Huge thanks to John Burnett of Adaptive, Dennis Ferguson of ANS, Joel Halpern of Network Systems, and Paul Francis of Bellcore for their super valuable insight and comments on earlier versions of this draft. You're all iconic. 🌈

Security Considerations 💀

Security issues are not discussed in this memo. 💀 Full stop, we're leaving that topic off the table here.

Authors' Addresses 🦋

Juha Heinanen, Telecom Finland, PO Box 228, SF-33101 Tampere, Finland

Phone: +358 49 500 958 EMail: Juha.Heinanen@datanet.tele.fi

Ramesh Govindan, USC/Information Sciences Institute, 4676 Admiralty Way, Marina del Rey, CA 90292

Phone: +1 310-822-1511 EMail: govindan@isi.edu

📦 where this page comes from