You probably use TCP/IP every day, but do you really understand how it works? This two-part article presents sufficient information for you to integrate a stack into your next design.

Embedded engineers are facing a new requirement to put Internet connectivity in a wide variety of systems they design and build. Connectivity is required either to exchange billing information or business data, or to facilitate remote process and/or machine control. For almost everyone, the TCP/IP protocol suite is the core technology for this connectivity. For many, TCP/IP is now the technology of choice for all data transfers, including both video and voice. Web browsing and remote device configuration now are also possible with TCP/IP.

TCP/IP stands for Transaction Control Protocol and Internet Protocol. Actually, though, TCP/IP is a complete protocol suite which includes these protocols, as well as others. Many embedded engineers are familiar with TCP/IP only as a mechanism to access the Internet from their PCs or laptops. They know it as one of the vague things that go wrong when their PCs can no longer access the file server that holds the source files they're supposed to be working on. Now, many of these same engineers are responsible for designing and delivering an embedded system that implements the TCP/IP protocols. Many engineers may not be familiar with the memory or CPU requirements, or with the real-time constraints imposed on their system by the protocols. After reading this two-part article, any engineer familiar with embedded software or system or hardware design can grasp the essentials necessary to obtain a TCP/IP stack and integrate it into his or her design. I'll also describe some of the choices in implementing TCP/IP, such as where to get the protocols, what's available for the target hardware, and whether it is necessary to have a commercial real-time operating system (RTOS) to run the protocols.

In this month's installment, I'll introduce TCP/IP and its components and layers. Next month, I'll get into some issues that are of interest primarily to embedded systems designers. Many written materials are available for TCP/IP network administrators and implementors. In this article, I will address specific issues related to TCP/IP stack selection, porting, and implementation in embedded systems. I tend to take a low-level view of the protocols; therefore, I emphasize what happens when a packet is received and transmitted at the lower layers of the protocol. After developing an understanding of the foundation below the networking applications, you may continue to explore the upper layer protocols and services that give the Internet enormous value.

History of TCP/IP

The TCP/IP protocols were first adopted by the Defense Advanced Research Projects Agency (DARPA) as part of a project to connect primary government-funded research institutions in a computer network. Around the same time, at the University of California at Berkeley, the Berkeley Systems Distribution (BSD) version of Unix was widely distributed to university computer science departments. DARPA contracted to have the TCP/IP protocols merged into the Berkeley BSD Unix operating system. DARPA wanted to force everyone to use a standard set of protocols so it required anyone hooking up to the Internet to run the TCP/IP protocols.

Because of DARPA, the TCP/IP protocol source code was widely distributed as part of BSD. All TCP/IP source code leveraged from the BSD sources had to contain the UC Berkeley copyright. From this leveraged source code, vendors ported the TCP/IP protocols to most mainframe and mini-computers. Then, as the embedded industry grew, RTOS vendors and separate protocol stack vendors ported the TCP/IP sources from BSD to many embedded environments. That's why most of the products using TCP/IP today contain much of the unaltered code from BSD and much of the source still carries the UC Berkeley copyright.

The OSI layered model

The Open System Interconnect (OSI) model was introduced in the '70s by the International Standards Organization (ISO) to promote inter-operability between diverse vendors' systems. They released the final OSI standard in 1984.

TCP/IP was already established while the ISO networking standards were evolving. Nowadays, explaining all networking in terms of the OSI model is common because it provides a common terminology to discuss issues related to computer networking.

The principle behind layering is that each layer hides its implementation details from the layers below and the layers above. Each layer on the transmitting machine has a logical peer-to-peer connection with the corresponding layer in the receiving machine. This is accomplished through the use of encapsulation.

Figure 1: TCP/IP Stack

Physical. The physical layer encompasses the actual physical data transmission. Examples are Ethernet (CSMA/CD) or Token Ring for LAN applications, or various high-speed serial interfaces for WANs. Physical layer implementation is specific to the type of transmission. In this article, I generally use Ethernet as an example of a physical layer protocol. Each machine on the physical network has an address called the media access control (MAC) address. Most MACs provide several addressing modes. They have an individual address that uniquely identifies each actual interface card. They also have a concept of multicast and broadcast addresses, where a transmitted frame can be shotgunned out to the wire with the target specified as all machines (in the case of broadcast) or a subset of machines (in the case of multicast). In Ethernet, the multicast and broadcast addresses are implemented by setting magic bits in the MAC address.

Data link. The data link layer isolates the layers above from the physical and electrical transmission details. Technically, the data link layer is responsible for presenting an interface for an error-free transmission, otherwise known as a connection-oriented service to the layer above. Of course, the legacy of TCP/IP is to not assume that the lower layers have any sort of error recovery. Therefore, most implementations of the data link layer for TCP/IP don't implement any mechanism for reliability.

Traditionally, the hardware for connectivity was referred to as network interface cards (NIC). The data link layer can be thought of as having two internal layers. The upper part handles the framing details and the interface with the upper layers. The lower part is essentially the device driver for the NIC, including device management, interrupt handling, and DMA control. In this article, I use the 802.2 LLC type of framing at the link layer in my examples. The IEEE 802.2 standard calls for three types of service: connectionless mode, connection mode, and acknowledged connection mode. I'll only address connectionless service at this layer, because in TCP/IP, connection-oriented service is handled at the transport layer.

It is up to the link layer to do some filtering of packets or frames. The most elemental filtering actually occurs at the physical layer. The link sets up the physical layer to receive only packets with its own MAC address in the destination field, as well as all multicast and broadcast packets. (For a discussion of the promiscuous mode, see next month's detailed discussion about link layer interfaces.)

Network. The network layer encompasses the Internet domain knowledge. It contains the routing protocols, and it understands the Internet addressing scheme. The IP addressing mechanism must be converted into physical (MAC) addresses before the data can be transmitted by the link and physical layers.

IP. The Internet Protocol (IP) is the part of the stack known as the network layer. The network layer handles routing of packets across network interfaces. Domain naming and address management are considered to be part of this layer as well. IP also includes a mechanism for fragmentation and reassembly of packets that exceed the link layer's maximum transmission unit (MTU).

IP addressing. IP addresses are used to ensure that packets are routed to the correct destination (see Table 1). Also, IP addresses can be coded as broadcast and multicast addresses. It is the convention to use the dotted decimal notation to describe IP addresses. However, expressing network address masks as hex numbers is generally more convenient. The class of the address determines the number of machines on a subnet and hence the type of subnetting. The subnet doesn't need to be divided on a byte boundary. Class A and B addresses aren't used much any more because they allow too many hosts on a subnet. Generally, Class C or subdivided class B addressing is used. The subnet mask defines the type of addressing. For example, the subnet address for a subdivided class B address allowing 512 network IDs and 128 host IDs would be 0xffffff80.

Table 1: Addressing
Class	Lower bound of address range	Upper bound of address range
A	0 . 0 . 0 . 0	127 . 255 . 255 . 255
B	128 . 0 . 0 . 0	191 . 255 . 255 . 255
C	192 . 0 . 0 . 0	223 . 255 . 255 . 255
Multicast	224 . 0 . 0 . 0	239 . 255 . 255 . 255

ARP. Address Resolution Protocol (ARP) can be thought of as either in the network or the link layer. Here, I will consider it to be a part of the network layer. The purpose of ARP is to map IP addresses used at the network layer into MAC addresses used at the link layer. I'll discuss how ARP is called from the link layer later. Incoming packets that have the ARP type in the type field are sent to ARP by the link layer.

Transport. The transport layer implements reliable sequenced packet delivery known as connection-oriented transfer. This layer incorporates retrying and sequencing necessary to correct for lost information at the lower layers. The transport for TCP/IP actually provides two protocols: TCP for reliable or connection-oriented transmission, and UDP for unreliable, or connectionless transmission.

Why do we need a reliable delivery mechanism at the transport layer? IP makes no assumptions about the reliability in the underlying data link and physical layers. If a mechanism for reliable transfer exists, it must be implemented above the network layer. The telephony world and the IP world have a long-standing debate about how much error checking and reliability need to be designed into the lower layers. Many of the WAN-type protocols, such as X.25, have a great deal of error checking in the lower layers. TCP/IP is intended to work with LAN protocols, such as CSMA/CD, that drop packets at the physical layer when collisions occur. However, with sufficient raw bandwidth, TCP can repair transmission errors at layer four before noticeable data loss occurs. In the context of TCP/IP, the transport layer refers to the application-level API for the transport layer. Two common APIs exist: transport layer interface (TLI) and sockets. Therefore, we usually refer to the application API as the transport layer. The transport layer provides an interface for both connectionless transport and connection-oriented transport. If the socket API is used, connectionless sockets are called datagram sockets and the connection-oriented sockets are called stream sockets.

UDP-Unreliable or connectionless transport . UDP allows the application to send and receive only individual packets of data. Each packet is sent as a separate transmission. UDP only provides a simple interface to the IP layer. It has no mechanism to retry or retransmit lost packets. If the application has a large amount of data to send, it has to worry about breaking up the data into individual, small-enough pieces. In the network layer, IP does allow for fragmentation and reassembly, but generally UDP applications pay attention to the maximum transmission unit. Also, the networking infrastructure in between the sending and receiving machines can change routing decisions at any time; therefore the application can make no assumption that the packets were received in the order that they were sent.

TCP connection-oriented or streaming sockets. This streaming type transport (not to be confused with STREAMS) is implemented by the TCP protocol. TCP breaks up the data into packets. It sequences the packets so they can be marshalled at the other end in the order that they were sent. It also retransmits packets that were lost by the lower layers.

The TCP or stream type sockets are buffered, and they are full duplex. The application in the transmitting machine can write an undifferentiated stream of data in the socket as if it were a pipe and the application on the receiving machine will receive the same data in the same order.

Session. The session layer was originally conceived to support virtual terminal applications between remote login terminals and a central terminal server. In the early days of networking, when most users used computers through a terminal interface, the session layer was intended to keep track of a logged-in user talking to a central time-sharing system. Telnet is an example of a protocol that contains session management. Because TCP/IP only incorporates protocols through the transport layer, all the software above the transport layer is generally lumped together as networking applications, so the session layer isn't differentiated from the application layer.

Presentation. The presentation layer maps the user's view of the data as a structured entity to the lower layer protocol's view as a stream of bytes. This is accomplished through Abstract Syntax Notation (ASN.1), which is a high-level language that describes a user level representation of the data. The presentation layer has no specific role in TCP/IP because TCP/IP is only implemented from the physical through the transport layers. Therefore, any presentation level functionality is viewed as part of the application layer.

Application. The application layer encompasses virtually all applications of TCP/IP networking, including network file systems, web server or browser, or client server transaction protocols. Network management is really in the application layer, although there are hooks down in the protocols to gather statistics and events and pass them up to the management application. Also, object exchange methods such as Distributed Common Object Model (DCOM) and Common Object Request Broker Architecture (CORBA) are considered part of the application layer.

Implementation

In this section, I'll discuss how the protocols are actually implemented in an embedded system.

Encapsulation. Encapsulation is used to isolate each of the layers in the protocol stack. Each layer frames the data, prepending the data with its own header information. In the sending machine, the layer places its own header information in front of the data it gets from the layer above before passing it to the layer below. In the receiving machine, each layer first interprets and then strips the header information from frames received from the layer below before passing them up to the layer above. In reality, it is not quite so simple. In many cases, the headers are saved for use by the layers above.

Buffer management. TCP/IP breaks the data down into a series of packets or frames. Buffers are created to hold the frames and the data contained in them. Because of the inherent asynchronous nature of a network, the buffers must be deployed and de-deployed dynamically. They can be deployed from a pre-allocated series of buffer pools or they can be allocated from the global memory pool when needed. They have variable lifetimes depending on any number of factors, such as network throughput, whether the included frame is part of a stream transmission, or whether the packet is a datagram. An understanding of buffer management is fundamental to an understanding of the protocol implementation.

Table 2: Fields in mbuf structure
m_next	Next mbuf in chain of mbufs. A chain of one or more mbufs is used to contain a single packet.
m_nextpkt	Next mbuf in a queue of packets.
m_len	Contains total length of data in the mbuf, including cluster if one is attached.
m_data	Address of the beginning of the data. This may point to a location in the data area in the top of the mbuf or it may point to a location within a cluster. M-data doesn’t necessarily point to beginning of data area but can be incremented to where usable data starts
m_type
m_flags	Described in Table 3.
m_pkthdr.len	This location will be the beginning of data if flags field is 0.
m_pkthdr.rcvif

The basic buffering mechanism used in Berkeley-based TCP/IP is called mbufs, or memory buffers. Mbufs can be expanded to allow for variable length frames used often in IP-based communications. The mbuf data structure is shown in Table 2. Small amounts of data can be placed directly in the data area of the mbuf. Larger amounts of data require the mbufs to be extended with clusters. A cluster is a data structure that holds heterogeneous data for extending the data-carrying capability of an individual mbuf. Mbufs can be chained to allow for easy implementation of packet queues, as shown in Figure 2. The basic mbuf contains some header information with a data area which can be extended with a cluster if the frame can't fit into the data area. Mbufs are also convenient places to put control information or other temporary data used within the protocols.

Figure 2: Linking of mbufs

There are four types of mbufs, as shown in Table 3. The mbuf type is differentiated by the m_flags field in the mbuf structure.

The data's journey down the stack

The best way to understand any protocol is to follow the data as it travels from the application layer, down the stack of the sending machine, out the wire, and up the stack of the receiving machine.

Typically, an application scribbles the data in a socket. A socket can be thought of as a mated pair of logical endpoints. One endpoint is on the sending machine and one is on the receiving machine. Here is how a piece of information actually travels down the TCP/IP stack. The first thing that the application or user layer does is create a socket with the socket() system call.

Sending data via UDP or connectionless transmission. Let's assume that the user wishes to send a single message to another system via the UDP or datagram protocol. To use UDP, the application specifies the SOCK_DGRAM protocol in the socket() system call. For example, the user invokes the sendmsg() system call, passing a message pointer as an argument.

Figure 3: UDP Encapsulation

Sending streaming data via TCP or SOCK_STREAM protocol. If users wish to transmit a reliable stream of data, they use TCP by specifying the SOCK_STREAM protocol in the socket() system call. On the machine that wishes to use a remote service or the client end, the connect() call establishes a connection between the local socket and the remote endpoint. The connect() call waits until the connection is established. The TCP protocol maintains a state machine to keep track of the connection. Once the connect() call returns, the socket is ready to accept data.

The application can then write data in the socket with sendmsg() or another write call. The user data is accumulated in the send buffer of TCP. If your implementation supports zero copy sockets, the data isn't copied. It is tied up in mbuf and cluster structures by using pointer manipulation only.

When a streaming socket receives the data, it breaks the data into frames and allocates buffers to hold the data. The TCP headers are then placed in front of the data and the frame is passed down to the IP layer. The data is split up into individual frames to ensure that the data length is less than the MTU.

Figure 4: TCP Encapsulation

Figure 4 shows the TCP encapsulation. Some of the fields shown are used to keep track of the state of the connection. For example, TCP uses the sequence number field and acknowledgement number field to maintain the order of the individual datagrams. The state bits (Finish, Synch, Reset, Push, Acknowledge, and Urgent) are used by the protocols on both ends to keep track of the state of the connection and manage the establishment and break down of the connection. It's important to note that the actual data transmission is buffered and asynchronous. The embedded system must have some kind of timer management to implement the retransmits necessary to compensate for lost packets. It also must have a dynamic buffer mechanism to hold packets until they can be retransmitted or discarded.

Figure 5: IP Encapsulation

IP layer encapsulation and fragmentation. IP layer encapsulation is shown in Figure 5. The IP layer puts its headers on the front of the data it receives from the transport protocols. It also establishes the route for the packet according to its routing tables and inserts the appropriate address in the IP header. It calculates the checksum and sets the time-to-live (TTL) field to zero for packets originated above.

The transport protocols don't necessarily know the MTU for a particular link layer. As I mentioned, the MTU is the maximum packet size that can be transmitted across a physical layer. In particular, streaming sockets used for connection-oriented transmission are completely independent of the implementation of the lower layers. IP's job is to fragment the data into small enough packets to fit within the MTU. Routers or networking equipment between the sending and receiving machines may break the data into even smaller frames if the data must pass through link layers that have a smaller MTU than the one at the transmitter's interface. IP keeps track of the packet fragmentation and assures that the packet is reassembled in the receiving machine in the same way it was fragmented.

IP implements packet routing. The IP layer can be set for IP forwarding to send packets received in one interface out another. This is a fundamental routing capability that can be used when the IP layer is multiplexed to two or more link layer interfaces. IP maintains routing tables to determine which gateway to send a packet to reach a particular final destination machine. I won't cover routing here because that's a substantial topic on its own.

Link layer encapsulation. In this section, I concentrate on 802.2 LLC encapsulation. Since legacy TCP/IP ports such as BSD 4.3 were hard coded to handle Ethernet type II encapsulation, I show it in Figure 6. 802.3 type encapsulation is necessary to support link layers other than Ethernet. Problems can occur because of confusion between the two types of encapsulation if the TCP/IP stack was originally written to assume Ethernet type II encapsulation and the stack is later used over other link layers.

Figure 6: Ethernet type II Encapsulation

If link layer multiplexing is used, the IP layer above can receive packets from one of several instances of link layers, where each link layer passes up packets from a specific physical layer. For each interface that is attached to IP, the link layer's output function is called by IP to transmit the frame. The packet is passed along with a pointer to the destination address in a sockaddr{} structure. For Ethernet drivers, the output function calls etherOutput(), which calls addrResolve() to convert the IP address in the sockaddr{} structure to a MAC address.

This conversion from IP to MAC addresses is actually done by the Address Resolution Protocol (ARP). When ARP is called by the link layer, it is passed a pointer to a frame and a pointer to the sockaddr{} structure. It then looks in its tables to see if the address has already been resolved. If it finds the address, it queues the packet to the interface for transmission with the correct MAC address. If the address is not already resolved, ARP sends a broadcast packet containing the IP address to see if an ARP server somewhere on the network knows the MAC address that corresponds with the enclosed IP address.

At this point, any intelligence from the IP layer about fragmentation, routing, or IP addressing is perceived as mere data by the link layer to be blindly buried in the LLC frame. The link layer puts the destination address in the frame, which is passed to it from IP. Of course, as previously discussed, IP determines which IP address to use from its routing tables. Then the source address is put in the frame and the length is calculated. For TCP/IP, most of the stuff in the LLC and SNAP headers is hard coded, as shown in Figure 7. The type field is set to the protocol type depending on whether it's an IP, ARP, or RARP packet.

Figure 7: Data link LLC Encapsulation

The link layer is generally thought of as having an upper and lower part. The upper part handles the encapsulation and the multiplexing with the layers above. The lower layer handles the device interface, including DMA and interrupt handling. After prepending the LLC headers in front of the data, the lower half of the link layer picks up the data. The lower half sets up the DMA and hardware for frame transmission.

Physical layer. The management of the physical layer is really part of the lower half of the link layer networking interface driver. The frame is now ready for transmission and it typically is placed in a circular buffer ready for transmission by the DMA hardware.

The data's journey up the stack

In this section the path of data will be traced as it is received by the PHY and passed up the stack through the protocols to the socket layer.

Received by the link layer. The data is received at the link layer via DMA into a circular buffer by the interface hardware. A driver in a zero copy implementation will place the circular buffer in memory in such a way that packets can be massaged into clusters which can later have mbuf wrappers placed around them without unnecessary copying by the CPU.

The link layer determines the type of framing. If the incoming packet is coming from an Ethernet interface, it may have either Ethernet type II framing or 802.3 type framing. The length field in the 802.3 type framing is at the same displacement as the type field in the Ethernet type II frame. The allowable types are in Table 4. If any of these types were to be interpreted as a length, they would represent a packet length greater than the MTU of Ethernet of 1,500 bytes. Therefore, the two types of framing can be distinguished.

The interface's input function compares the MAC address of the incoming packet with the broadcast address. If the incoming packet is a broadcast packet, it is given to each protocol that is attached to this interface. If the multicast bits are set for this interface, the packet is passed to any protocol that has requested multicast packets.

If the incoming packet is a unicast, the type field determines which protocol receives the frame. If there is a protocol, bound to the driver that wants to receive data promiscuously, it would receive all the frames that are received at the link layer. If the incoming frame is typed as an ARP packet, it is queued to the ARP protocol's input function. If typed for IP, it is queued to IP's input function.

Received by IP. Most of the complexity in the IP layer has to do with routing or IP forwarding. For the purposes of this section on IP, I assume that your embedded application is not expected to do routing. Layer 3 routing is a much larger topic and should be treated in a separate venue. (Next month, I discuss criteria for selecting a stack vendor to ensure that the implementation can be extended for routing.) The IP layer compares the IP destination address of the incoming packet to its own IP address and subnet mask to see if the packet is destined for itself. If IP forwarding is not turned on and the packet is not destined for itself, it is discarded.

IP must now determine whether the packet is fragmented and requires reassembly, or whether it is a complete IP datagram. The packet is reassembled if required, and once it is determined to be a complete IP datagram, it is time for transport demultiplexing. IP has to be able to tell which transport is to receive the packet. It could be a UDP datagram or it could be destined for TCP. IP determines this information when it checks the protocol ID in the IP header The data is then sent to the appropriate transport by way of the protocol switch table.

Received by UDP. If the data is sent to UDP by a lower layer protocol, it is received by the UDP_input() function. First the IP header is stripped and saved for later use. The UDP length is verified and the checksum is checked, which requires some of the fields from the previously saved IP header.

The incoming packet is then checked to see if it was sent to a multicast or a broadcast address. If it was sent by the original sending machine to a broadcast or multicast address, the packet is given to each of the matching socket's input queues. If the data was sent to the correct unicast address but the port number is wrong, an ICMP packet is sent out indicating the port is unreachable. Otherwise if everything is okay, it is placed on the socket's input queue.

Received by TCP. TCP input is complicated and I won't be able to do it complete justice in this article. You may refer to "Stevens" in the references below for more information about TCP. The first thing it does is to verify the TCP checksum. The timestamp in the packet is then examined to verify the state of the connection. TCP must now decide if more data needs to be sent to the other end or if a timeout has occurred. If the incoming packet is data and not an acknowledgement, the IP and TCP headers are dropped and the data is placed into the listening socket's input buffer.

Upcoming

In part two of this series on TCP/IP, I'll look at the details involved in putting TCP/IP into a resource-constrained embedded system.

Thomas Herbert is a field consulting engineer with Wind River Systems. Before that, he worked in embedded systems in various applications for many years for such companies as Xerox Corp., Eastman Kodak, and as an independent consultant. Tom has contributed several articles to Embedded Systems Programming over the past few years and holds a patent in pattern recognition. He can be reached at tom.herbert@windriver.com

Resources

Many excellent books have been written on TCP/IP internals, application programming using TCP/IP, and maintenance and configuration of IP networks. You'll find a few references below which I have found valuable for explaining the internals of TCP/IP and may be useful to the embedded engineers who want to bone up on networking. The first and most important references for TCP/IP are the first two volumes. If you really need to see how the protocols work and how they are implemented, these books are the definitive guides.

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

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

For an authoritative work on BSD 4.4, I suggest:

McKusick, Marshall Kirk, Keith Bostic, Michael J. Karels, and John S. Quaterman. The Design and Implementation of the 4.4BSD Operating System. Reading, MA: Addison-Wesley, 1996.

For general information on STREAMS, see: Herbert, Thomas F., " Implementing Network Protocols and Drivers with STREAMS," Embedded Systems Programming, April 1997, p. 28.

Or you may want to read the definitive reference on SVR4 STREAMS. Even if you're not specifically interested in STREAMS, Chapter 11 on DLPI data link provider interface (DLPI) is a good look at what functionality needs to be in a good multiplexing data link interface. Unfortunately, at the time of the writing of this article, this book is out of print:

Unix Press. STREAMS Modules and Drivers. Englewood Cliffs, NJ: Prentice-Hall, 1993.