4
1 Introduction
When we investigated the performance of gigabit networks and end-hosts in the DataTAG
testbed, we soon realized that some losses occurred in end-hosts, and that it was not clear where
these losses occurred. To get a better understanding of packet losses and buffer overflows, we
gradually built a picture of how the networking code of the Linux kernel works, and instrumented
parts of the code where we suspected that losses could happen unnoticed.
This report documents our understanding of how the networking code works in Linux kernel
2.4.20 [1]. We selected release 2.4.20 because, at the time we began writing this report, it was the
latest stable release of the Linux kernel (2.6 had not been released yet), and because it was the
first sub-release of the 2.4 tree to support NAPI (New Application Programming Interface [4]),
which supports network interrupt mitigation and thereby introduces a major change in the way
packets are handled in the kernel. Until 2.4.20 was released, NAPI was one of the main novelties
in the development branch 2.5 and was only expected to appear in 2.6; it was not supported by the
2.4 branch up to 2.4.19 included. For more introductory material on NAPI and the new
networking features expected to appear in Linux kernel 2.6, see Cooperstein’s online tutorial [5].
In this document, we describe the paths through the kernel followed by IP (Internet Protocol)
packets when they are received or transmitted from a host. Other protocols such as X.25 are not
considered here. In the lower layers, often known as the sub-IP layers, we concentrate on the
Ethernet protocol and ignore other protocols such as ATM (Asynchronous Transfer Mode).
Finally, in the IP code, we describe only the IPv4 code and let IPv6 for future work. Note that the
IPv6 code is not vastly different from the IPv4 code as far as networking is concerned (larger
address space, no packet fragmentation, etc).
The reader of this report is expected to be familiar with IP networking. For a primer on the
internals of the Internet Protocol (IP) and Transmission Control Protocol (TCP), see Stevens [6]
and Wright and Stevens [7]. Linux kernel 2.4.20 implements a variant of TCP known as
NewReno, with the congestion control algorithm specified in RFC 2581 [2], and the selective
acknowledgment (SACK) option, which is specified in RFCs 2018 [8] and 2883 [9]. The classic
introductory books to the Linux kernel are Bovet and Cesati [10] and Crowcroft and Phillips [3].
For Linux device drivers, see Rubini et al. [11].
In the rest of this report, we follow a bottom-up approach to investigate the Linux kernel. In
Section 2, we give the big picture of the way the networking code is structured in Linux. A brief
introduction to the most relevant data structures is given in Section 3. In Section 4, the sub-IP
layer is described. In Section 5, we investigate the network layer (IP unicast, IP multicast, ARP,
ICMP). TCP is studied in Section 6 and UDP in Section 7. The socket Application Programming
Interface (API) is described in Section 8. Finally, we present some concluding remarks in
Section 9.
