To put this discussion of ARP in the proper perspective, let's talk a little bit about where we've been and where we're headed. If you're a regular reader of this column, you know that my long-term goal is to produce a small, portable UDP/IP stack appropriate for use in all sorts of embedded systems. The complete stack should be finished, documented, and available for downloading from www.embedded.com in just a few short months.

We've already discussed that TCP support is not always required in embedded uses of Internet technologies (" TCP/IP or Not TCP/IP?" April 2000, p. 49). I don't have to convince you that there's no reason to go to the trouble and expense of including software in ROM that your application doesn't actually require. Hence, my decision to include only UDP in this stack. A UDP/IP stack was sufficient for my own use of the Internet protocols to keep a satellite gateway's firmware up to date and send logging messages to a control and monitoring station. That was several years ago, but the technique is just as useful today.

We've also seen how a network stack (UDP/IP or TCP/IP) fits into the broader embedded software framework. Once implemented, the stack of protocols is simply another API to be called from your application program. The stack is internally dependent upon the API of the underlying operating system and network device driver, but otherwise separate from those pieces of software. It is, in effect, middleware. The ARP protocol is just one component of a TCP/IP or UDP/IP stack.

Lookup, look down
Last month we talked about the unique hardware addresses associated with each device connected to a physical network like Ethernet. I told you that these addresses must be globally unique; no two Ethernet-connected systems may have the same 6-byte hardware address. It turns out that every system on an IP network also has a second address. This logical address is called, as you might expect, the "IP address."

The best analogy I can draw to this two-address phenomenon is that of a toll-free phone number, like the 800- and 888-prefixed numbers in the U.S. Although each toll-free number is unique and can be used to contact a person at a particular physical location, the number itself does not convey any direct information about what the actual phone number is. For a while I had a toll-free number of my own; calls to that number were automatically redirected to the phone in my office. My office phone had an area code, exchange, and four more digits just like any other; my 888-number had nothing in common with it. You can't tell from a toll-free number if it will reach the phone on your desk or one on the other side of the country.

In much the same way, each node on the Internet (or an intranet) has two addresses: one physical and one logical. Neither of these addresses contains any information about the other. And yet, unlike the phone number example, you need both addresses to communicate with a given system. Usually, your application knows just one address-the IP address-of the remote system. But no network packets can be sent to the remote system without the hardware address as well.

ARP is the Internet's lookup service. Given an IP address (toll-free number), ARP can obtain the hardware address (actual area code and phone number) to which network packets should be sent on the physical network. Similarly, a related reverse-lookup service called RARP can obtain the IP address of a machine given only its hardware address. ARP is used by every machine on the Internet; the use of RARP is more limited.

ARP, ARP, and away
Before we go on, I need to let you know that I'm restricting the remainder of this month's discussion to simple networks where all of the connected systems are on the same physical network. In other words, I'm not going to tell you how the hardware addresses obtained with the help of ARP are sometimes white lies, used in conjunction with nodes on the network called bridges, switches, and routers to direct your packets across physical network boundaries. Those details really aren't important to you anyway-unless the embedded system you are building is itself a bridge, switch, or router-since these white lies don't affect your ARP implementation. (Now just pretend like I didn't open up a whole can of worms of routing issues you hadn't thought about before and let's carry on.)

As specified in RFC 826 (way back in the early days of the Reagan administration), ARP is a general-purpose protocol that can be used to map any type of hardware address to any type of protocol address. However, for most practical purposes, all anyone really cares about using ARP for, these days, is converting the IP address of a remote machine into an Ethernet address. It's the device driver for the Ethernet controller that needs this information. Every time the IP layer passes the network driver a packet to send over the Ethernet, it needs to figure out what Ethernet address, specifically, to send the packet to. So ARP will be at the very bottom of our UDP/IP stack, residing below the IP layer but above the network driver.

Figure 1: How ARP Works

Figure 1 shows how ARP works. In short, the system that needs a hardware address sends an ARP request message out onto the network. Since the sender doesn't know the hardware address of the system it's looking for, this message is broadcast to all systems on the physical network. (On Ethernet, address FF:FF:FF:FF:FF:FF is reserved for broadcast messages.) Included within the ARP request is the IP address (also known as, protocol address) of the target system and both of the sender's addresses. Each system that receives the broadcast ARP request checks to see if its local IP address matches the target protocol address in the ARP request. The one system with that IP address sends an ARP reply directly to the requester. Normal UDP/IP communication can begin only after the requester receives the ARP reply.

Preliminaries
Before I can show my ARP implementation code, we need to discuss a few preliminaries. The first of these is that I'm following the source code conventions of the ýC/OS-II real-time operating system (see Jean Labrosse's MicroC/OS-II, R&D Books, 1998). One thing you'll notice as a direct result of this is that my code uses the set of portable, compiler-independent data types shown in Table 1. These types will be used instead of char, short, int, long, and their unsigned counterparts, whenever the size of a field is dictated by a network protocol. So, for example, the definition of an ARP packet looks like this in my implementation:

typedef struct
{
INT16U hw_type;
INT16U prot_type;
INT8U hw_len;
INT8U prot_len;
INT16U operation;


} NetArpHdr;


typedef struct
{
NetArpHdr arpHdr;
INT8U
sender_hw_addr
[HW_ADDR_LEN];
INT32U sender_ip_addr;
INT8U target_hw_addr
[HW_ADDR_LEN]; 
INT32U target_ip_addr;


} NetArpPkt;

The advantage of this should be clear enough. Each field will have the correct size (in bytes and sign) on any platform, provided the fellow doing the port of the protocol stack remembers to redefine the six basic types in Table 1 to match the compiler and underlying hardware. So, for example, a port to an 80186 processor would include the definitions:

typedef unsigned char INT8U;
typedef unsigned short INT16U;
typedef unsigned long INT32U

My choice of ýC/OS-II as RTOS also affects my naming convention. Except for well-known names I want to mimic, all of my function and data structure names will begin with the prefix Net. That prefix will be followed by the module name-for example, Arp-and then a name descriptive of the function itself.

The second thing we need to talk about is the format of IP addresses. You might, for example, refer to your personal workstation by a dotted-decimal number such as 207.221.32.136. This is your workstation's IP address, but in a human-readable string format. For reasons you can easily understand, the protocol stack doesn't much like to deal with strings. Rather, it prefers to deal with numbers. Therefore, the protocol stack treats your IP address as a big-endian 4-byte unsigned integer. (The preceding string IP address would be treated as 0x8820DDCF.)

Just as string addresses are hard for the protocol stack to manipulate, big-endian 32-bit integers are hard for people (even programmers) to interpret. So one of the first things I did on this project was to write a pair of functions for converting string IP addresses to 32-bit integers and vice versa. Following a naming convention with which I was familiar I called these inet_addr() and inet_ntoa(), respectively. Their prototypes are as follows:

INT32U inet_addr(char const * str);


void inet_ntoa(INT32U ip_addr, 
char * buf);

The only thing to be aware of when using these is that the second function requires the caller to reserve 16-bytes of space for buf in advance of the call. That is the maximum length of a dotted-decimal IP address, including the null terminator for the string.

'Nuff said
With those preliminaries out of the way, we can now begin to look at the code within the ARP module. It should be obvious from Figure 1 that there will be at least two functions: one for the sending of ARP requests and replies and another for receiving these packets and processing them. I've called these functions NetArpSnd() and NetArpRcv(), respectively.

Listing 1: A function to send ARP request and reply packets

The implementation of NetArpSnd() is shown in Listing 1. This function would typically be called by the IP module above or the network driver below, after it had been determined that the hardware address of the target system was not known. In that case, the call might look something like this:

NetArpSnd(ARP_REQUEST, broadcast,
inet_addr("207.221.32.136"));

In addition, NetArpSnd() may also be called by the NetArpRcv() function, which we'll see next, in order to send an ARP reply to a remote system that requested the hardware address of the local system. In that case, the first parameter will be ARP_REPLY and the second and third parameters will be the local_hw_addr() and the local_ip_addr(), respectively.

Listing 2: A function to handle incoming ARP packets

The implementation of NetArpRcv() is shown in Listing 2. This implementation conforms to the recommendation, in RFC 826, that any valid ARP packet directed to a local system, whether it be an ARP request or reply, be examined for useful hardware addresses. If the packet is an ARP request, this function is responsible for invoking NetArpSnd() to send the reply.

Cacheing in
If you looked closely at the code in Listing 2, you probably noted a call to a mysterious function named NetArpAddEntry(). Obviously, we don't want to broadcast an ARP request onto the network and wait for a reply before sending each and every IP packet. This could seriously offset the performance of communications across the entire network. So we need a way to keep track of the hardware addresses we've already learned about. To do this, the ARP module typically includes a cache of the most recently used hardware addresses. An ARP cache can be implemented in a variety of ways and there are no strict rules about doing it. In fact, nothing in the standard specifically precludes a system from asking for the hardware address of a system each time a packet is to be sent to it; so an ARP cache is not strictly necessary. Because I want my stack to be small and simple and because I only aim to support IP-Ethernet address pairs, I've employed a pretty basic strategy for hardware address tracking. The first element of this strategy is the ARP cache itself, which is defined as follows:

typedef struct
{
INT32U ip_addr;
INT8U hw_addr[HW_ADDR_LEN];


} NetArpTblEntry;


NetArpTblEntry gArpCache[NET_ARP_CACHE_SIZE];

where the size of the cache, NET_ARP_CACHE_SIZE, is a configuration option. Each entry in the cache takes up 10 bytes of RAM, so you want to limit this as much as possible. The correct number of entries depends heavily on your application. If you'll only be communicating with one other system, a cache containing just one entry would be sufficient.

Listing 3: A function to flush the ARP cache

Before using the ARP cache, it should be flushed or initialized with meaningless records. This can be done with the help of the function shown in Listing 3, NetArpFlush(). The idea here is simply to ensure that none of the data in the cache be interpreted as a valid address pair.

One important thing to note about flushing the cache is that address pairings can become "stale" over time. For example, imagine that a system you're communicating with has a hardware failure. A new system is substituted for it and given the same IP address as the old one. But this new system will have a different hardware address. The result? Your IP packets will be sent to a non-existent hardware address and will be received by no one. You won't be able to communicate with the replacement system unless and until it happens to send you an ARP request. (NetArpRcv() automatically updates the ARP cache when either an ARP request or an ARP reply is received.) One way to prevent such problems from occuring is to periodically flush the cache. The network device driver might, for example, flush the cache every 20 minutes. The next IP packet sent from the local application code to each IP address will trigger an ARP request and a fresh ARP reply. Since embedded systems tend to run for long periods of time without a reset, you should plan for the worst case and flush the cache from time to time.

Listing 4: A function to search the ARP cache for a hardware address

A cache of hardware addresses isn't very useful without a way to do lookups. That's the purpose of the NetArpLookup() function in Listing 4. The guts of this routine should make perfect sense. The ARP cache is searched, linearly, until an IP address matching the one provided as a parameter is found. If a match is found, a pointer to the associated hardware address is returned. Otherwise, a pointer to the broadcast address is returned. The caller must check this return value to see if a call to NetArpSnd() is necessary.

Listing 5: A function to add an entry to the ARP cache

Listing 5 shows the implemenation of the final function in the ARP module. NetArpAddEntry() simply adds a new IP-Ethernet address pair to the ARP cache. If the IP address is already in the cache, that record is updated. If it is not already in the cache, the first available slot is filled in. If, for some reason, the entire ARP cache is filled, the cache is flushed and the new address pair is inserted in the very first location. The position of the entry in the cache is returned, though the caller should have no particular use for it.

Still searching...
I still haven't made up my mind about the embedded platform I'm ultimately going to test this UDP/IP stack on. The problem is that I want to balance two different sets of needs-mine and yours. As the developer of the stack, I need a toolset that is easy to work in and debug with. Likewise, I'd prefer a hardware platform that is easy to understand and explain. As a user of the stack, however, you may only want to evaluate its performance on the reference platform, then port it to something of your own design. So I'm trying to find an inexpensive (under $200) single-board computer that is widely available and will continue to be. It'd also be nice if all the tools you'd need to make minor configuration changes and recompile the stack were available for free or as demo versions.

While I consider my hardware and tool options, I'm developing the UDP/IP stack on a PC. Only the network driver will be hardware specific, so it's relatively easy to do the bulk of the development as though it were a PC application. I've got the whole stack up and running on my development PC already, with separate client and server threads passing messages back and forth over UDP/PI. The stack itself is reentrant, so both threads can share those modules. Underneath the stack, I've implemented a dummy network device driver that assigns each thread unique Ethernet and IP addresses and its own private ARP cache. It then routes packets from one thread to the other as though there were an actual network between them.

By this time next month, I should have some client and server apps, the UDP/IP stack, and my dummy network driver running on ýC/OS-II. Since the book describing that RTOS includes a DOS port on floppy disk, it should be easy enough to accomplish the port of my existing Win32 stack-or so I hope. At that point, I'll probably have a complete set of source code worth sharing with you. Then you can quite literally play along at home if you choose, for the small price of a PC and about $120 ($70 for the ýC/OS-II book and $50 for the Borland C compiler). Who knows, maybe that's the only platform you'll ever want for playing with this stuff. But I'll still ultimately need to test my code on a network-connected embedded system.

Next month I'll tell you everything you ever wanted to know about the IP layer and share my implementation of it with you. In the meantime, enjoy this month's feature articles on Bluetooth and flash memory, and try to stay connected..