Figure 1: The big picture

Turtles all the way down
Before we go on, I want to make sure you have a solid picture in your head. That picture is the one in Figure 1, which shows how the TCP/UDP/IP stack fits in between your application code and the network interface. What I want you to understand from this figure is the black box nature of the stack. From the application programmer's point of view, a TCP/UDP/IP stack is nothing but an API to be called. In other words, data is sent and received over the network via a set of well-defined function calls. Typically, the so-called "sockets" API is used.

Figure 1 also shows the black box nature of the network interface. In an ideal world, the device driver interface would remove the stack developer from any knowledge of the actual interface type. In such a case, the same stack could communicate unchanged over an Ethernet or Token Ring network or via a serial or modem link, through the same set of device driver calls. In practice, however, this is difficult to achieve. You'll see as we go along that the implementation of the lowest layers of the TCP/UDP/IP stack is inextricably linked with the device driver and particulars of the hardware below. This is one of those practical realities rarely dealt with in books.

The convenient end
Another practicality that must be dealt with in a TCP/UDP/IP stack implementation is the issue of endianness. By definition, any computer system must be either:

• big endian -it stores the most significant byte of any multi-byte data field at the lowest memory address, which is also the address of the entire field
• little endian -it stores the least significant byte of any multi-byte data field at the lowest memory address, which is also the address of the entire field

char c1 = 1;
char c2 = 2;
short s = 255; //0x00FF
long l = 0x44332211;

Offset: Memory Dump
0x0000: 01 02 FF 00
0x0004: 11 22 33 44

The 68k and PowerPC are big endian processors, while the x86 and Alpha are little endian. The endianness difference can cause problems if a computer is, unknowingly, trying to read binary data written in the opposite format from a shared memory location or a file. To see what I mean, take a look at an x86 memory dump with a 16- or 32-bit integer stored inside. (If you don't have such a memory dump handy, take a look at Figure 2.) An x86 processor stores data in memory with its least significant byte first. However, your mind tends to expect the data to read from the most significant byte to the least. ¹

Unfortunately, it's not just processors that have this property. Communication protocols, file formats, and all sorts of other computer-related specifications require an endianness of their own. As it turns out, all of the protocol layers in the TCP/IP suite are defined to be big endian. In other words, any 16- or 32-bit value within the various layer headers (for example, an IP address, a packet length, or a checksum) must be sent and received with its most significant byte first. ²

#if defined(BIG_ENDIAN)
#define htons(A) (A)
#define htonl(A) (A)
#define ntohs(A) (A)
#define ntohl(A)
(A)
#elif defined(LITTLE_ENDIAN)
#define htons(A) ((((A) & 0xff00) >> 8) | \
((A) & 0x00ff) 
<
<
8))
#define htonl(A) ((((A) & 0xff000000) >> 24) | \
(((A) & 0x00ff0000) >> 8) | \
(((A) & 0x0000ff00) 
<
<
8) | \
(((A) & 0x000000ff) 
<
<
24))
#define ntohs htons
#define ntohl htohl
#else
#error "One of BIG_ENDIAN or 
LITTLE_ENDIAN must be #define'd."
#endif

This, of course, leads to an annoying little implementation detail. If your TCP/UDP/IP stack will run on a little endian processor, you'll have to reorder-at run time-the bytes of every multi-byte data field within the various layer's headers. If your stack will run on a big endian processor, then you have nothing to worry about. But what if you want your stack to be portable so it will run on processors of both types? Well, then, you'll have to decide whether to do this reordering or not, either on the fly or at compile time. The typical solution to the endianness problem is to define a set of four preprocessor macros: htons(), htonl(), ntohs(), and ntohl() , as shown in Listing 1. These macros make the following conversions:

• htons() -reorder the bytes of a 16-bit value from processor order to network order. The macro name can be read "host to network short"
• htonl() -reorder the bytes of a 32-bit value from processor order to network order. The macro name can be read "host to network long"
• ntohs() -reorder the bytes of a 16-bit value from network order to processor order. The macro name can be read "network to host short"
• ntohl() -reorder the bytes of a 32-bit value from network order to processor order. The macro name can be read "network to host long"

If the processor on which the TCP/UDP/IP stack is to be run is itself big endian, each of the four macros will be defined to do nothing and there will be no run-time performance impact. If, however, the processor is little endian, the macros will reorder the bytes appropriately. As we get into the details of the IP and UDP layer implementations, you'll see that these macros are routinely called when building and parsing network packets. Only when we see how frequently they are called will we be able to assess the true cost of implementing a big endian protocol stack on a little endian processor.

Hidden assumptions
If you read Christopher Leidigh's recent article ( "Configuring TCP/IP Hosts," April 2000), you're probably aware that simply adding a protocol stack and network interface to your software doesn't make your system TCP/IP-ready. Among other things, each system requires an IP address to communicate over the network. Leidigh's article did a great job of showing us how to bootstrap a system, determining the IP address in the process. But did you notice the way he assumed (like everyone else) that your system already had a unique hardware address?

"Upon receipt [of the broadcast packet], a RARP server will look up the client's hardware address in its tables [and return the IP address allocated to the client]" (p. 75).

Where does the "client's hardware address" (also called the MAC address ³ ) come from? Unlike the IP address, this is not something you can request from a local server. In fact, the RARP server referred to in the above quote can only respond to your system by using the hardware address it sent within the IP address request. The hardware address must be built into your system at manufacturing time.

This leads, of course, to two questions. One is: what value should you use for the hardware address? The other is: how do you have that value "built into your system"? I'll answer the second, and easier, question first.

Every system on a physical network like Ethernet or Token Ring includes a peripheral called a network controller . This chip is the processor's interface to the physical communications medium. As part of its initialization, the network controller must be fed a unique hardware address. In the case of Ethernet, the hardware address is a 48-bit value. In all but the rarest of circumstances, the hardware address will reside in an on-board non-volatile memory device.

Since the hardware address is unique for each board that rolls off the assembly line, it's typically not placed in the same ROM as the firmware. That way, identical copies of the firmware can be mass produced at a lower average cost per chip, while the unique hardware address can be placed in a very small EEPROM (along with other board-specific parameters, if any) when the board is assembled. The contents of this EEPROM might be determined by the board's serial number and created as part of the manufacturing process. ⁴

Now onto the remaining question.

OUI, oui!
Okay, so you know what the hardware address is and what to do with it once you've got it. But where does this globally unique 48-bit identifier come from? Clearly 248 is an incredibly large number of unique addresses, but no set of numbers is itself large enough to guarantee global uniqueness on its own. In the case of Ethernet, the upper three bytes of the 48-bit MAC address are carefully controlled by the IEEE. The scheme for guaranteeing uniqueness of the lower three bytes is individually up to the companies that make Ethernet-capable devices. All of us must work together with the IEEE to guarantee global uniqueness of our MAC addresses.

Every company that wants to produce Ethernet-capable products must first register with the IEEE (standards.ieee.org/regauth/oui/). You start by filling out some paperwork and sending them a check for $1,250. In return, your organization becomes the proud owner of a 24-bit Organizationally Unique Identifier (OUI) and the 16,777,216 unique hardware addresses it is capable of identifying. ⁵

What I've found usually works best for internal management of the lower 24 bits of the address is to break those bits into two fields. For example, you might break up your approximately 16.8 million unique addresses into 256 blocks of 65,536 addresses. That way, you could allocate the blocks one at a time to particular manufacturing groups, on an as-needed basis. The lowest 16 bits of the MAC address could then match up with the lowest 16 bits of the device's serial number for ease of manufacturing. Following this scheme, the 255th board manufactured within block two would be given the MAC address "OUI:02:00:FF," where OUI is the three-byte hexadecimal value assigned to your company by the IEEE.

What else?
This month in the Internet Appliance Design section, we've got a very timely set of articles for you. The first, by Greg Wickham, tells us about one company's early experiences with the Java programming language. In this case, the company is Alcatel and the Java code is compiled to native code as part of the development process. In other words, they're using Java without a Java Virtual Machine. Stay tuned folks, I believe ahead-of-time compilation like this has the potential to revolutionize high-end embedded systems development within just a few years.

On the subject of wireless communications, we've got an article about IrDA, by Charles Knutson. This article drills right down into the IrDA protocol stack, showing what you need to implement to support infrared communications with PCs, printers, and other systems. The author focuses on the use of IrDA in resource-constrained embedded systems by showing us what can be left out.

Next month I'll tell you everything you ever wanted to know about the mappings between IP addresses and Ethernet addresses and the corresponding Address Resolution Protocol (ARP). In the meantime, stay connectedı

Michael Barr is the technical editor of Embedded Systems Programming. He holds BS and MS degrees in electrical engineering from the University of Maryland. Prior to joining the magazine, Michael spent half a decade developing embedded software and device drivers. He is also the author of the book Programming Embedded Systems in C and C++ (O'Reilly & Associates). Michael can be reached via e-mail at mbarr @ netrino.com.

References
1. Frankly, I can never remember which is which: big endian or little endian. So I tend to use the terms "human readable" and "not human readable" on a day-to-day basis, especially when I'm troublesh6ooting problems alongside other engineers who may be even less versed in the formal terminology.

Back

2. Of course, a convention must also be agreed upon for the application-level data payload being transmitted over the network. However, in this case it is up to the designer(s) of the application to choose the endianness. They'll usually tend to make the choice that minimizes byte reordering.

Back

3. MAC is short for media access control.

Back

4. It should be clear that there is nothing to preclude your storing the hardware address in any nonvolatile memory device, including the ROM or Flash that contains the firmware. This is a decision, however, that should be made with manufacturing concerns, and costs, in mind.

Back

5. I was shocked to learn recently that Cisco owns 60 such sets, for a grand total of over 1 billion addresses!

Back

Resources
If you're working with TCP/IP, there are two series of books that you should know about. The first is a series of four books by Douglas Comer. In theory, you only need to buy three of these, since there are two versions of Volume 3, but some cross-platform developers may want to get all four. The first volume of the book gives you the big picture of TCP/IP network architecture and the relationships among and between the various protocols. Volume 2 is an implementer's guide, with the most recent edition geared toward ANSI C. The third volume focuses on application-level programming, where you're using the TCP/IP protocols through either the UNIX or Windows sockets API.

Comer, Douglas E. Internetworking with TCP/IP-Volume 1: Principles, Protocols, and Architecture, 4th ed. Englewood Cliffs, NJ: Prentice Hall, 2000.

Comer, Douglas E. and David L. Stevens. Internetworking with TCP/IP-Volume 2, ANSI C Version: Design, Implementation, and Internals, 3rd ed. Englewood Cliffs, NJ: Prentice Hall, 1998.

Comer, Douglas E. and David L. Stevens. I nternetworking with TCP/IP-Volume 3, Windows Socket Version: Client-Server Programming and Applications, 1st ed. Englewood Cliffs, NJ: Prentice Hall, 1997.

Comer, Douglas E. and David L. Stevens. Internetworking with TCP/IP-Volume 3, BSD Socket Version: Client-Server Programming and Applications, 2nd ed. Englewood Cliffs, NJ: Prentice Hall, 1996.

The second series of books is by W. Richard Stevens (no relation to David L.). The first two volumes of these are my personal favorites, despite the fact that I originally cut my teeth on TCP/IP at a time when only Comer's first edition books were available. This three-volume set follows a similar flow to the Comer books. However, I haven't found as much use for Stevens' Volume 3 as I have for Comer's.

Stevens, W. Richard. TCP/IP Illustrated-Volume 1: The Protocols. Reading, MA: Addison-Wesley, 1994.

Wright, Gary R. and W. Richard Stevens. TCP/IP Illustrated-Volume 2: The Implementation. Reading, MA: Addison-Wesley, 1995.

Stevens, W. Richard. TCP/IP Illustrated-Volume 3: TCP for Transactions, HTTP, NNTP, and the Unix Domain Protocols. Reading, MA: Addison-Wesley, 1996.