Required reading: Implementing network protocols at user level
Why talk about networking in an operating system class? Networking
modules are sophisticated users of operating system functions, and do
require some special support:
- Access to the network interface card to send/receive packets
- Scheduling the destination process of a packet
- Asynchronous processing of packets (e.g., interrupt handler),
because destination process may not exist anymore (e.g., TCP WAIT
- Timer support for retransmitting packets and estimating round-trip
- Memory allocation and deallocation for buffering packets (for
retransmission, out-of-order packets, etc.)
- Support for copying packet data between address space (packet
arrives in kernel, but its data may be for some user program).
- Support for multiple protocols (IP, UDP, TCP, etc.) and routing
A major issue in implementing protocols is managing concurrency.
The network, user programs, and protocols all generate packets, and
potentially concurrently while sharing state.
- Every packet has its own thread
- Every "connection" has its own thread---today's paper.
- Every protocol is implemented by its own thread
- The network module has one thread
- The network modules is implemented in interrupt handler---active messages.
The other major issue is protection. The network device is shared
and the network module needs to be involved in demultiplexing the
packets to the right destinatin process. Possible organizations to
solve this problem:
- Network module is located in kernel---UNIX.
- Network module is trusted server---Mach/L4
- Demultiplexing module in kernel and everything else in user
space---This paper and exokernel
- Protocol independent interface.
- Different types of socket: reliable, unreliable, etc.
- Interface: bind, listen, connect, read, write, close, select
- Driver network interrupt in interrupt queue
- Software interrupt (bottom half) does all incoming packet
processing, copying data into kernel buffers, and inserting the buffer
in the appropriate socket structure
- Applications poll for packets and its top kernel half copies the
packet from kernel buffers into user space.
- Applications send packets by copying data into kernel and buffers
and then running the send state machine of the protocol.
- Timer wheels
- Strategy: implement protocols in library, except for the code that
requires a trusted server.
- Server sets up connections, creates channels between application
and driver, hands channel off to library linked with user application.
Channel mapped shared between kernel and user space. What is in a
channel? (Answer: packets and synchronization state.)
- Library contains the common path of sending and receiving packets
- Listen: contact network server to receive connection
- Connect: contact network server to setup connection
- Packet delivery: packet filter to demultiplexing to process and
connection; set semaphore. No protocol code is run! When run
destination process? (Try to batch packets, does first process more
packets from network card, if there are any.)
- Packet processing: one thread per connection waiting on semaphore
- Write: copy packet in channel, call system call to get into
driver, check header, make an entry in send queue of driver. Send
interrupt completes sets bit in packet in channel to signal that the
packet has been sent. (Extend for fragmentation, send window,
congestion window, etc.)
- The application calls into the library using the write socket
- The library formats a packet in the shared buffer, and copies the
data into buffer shared with the network module (if we change API, we
can avoid this copy).
- The library makes a system into the network module, with arguments
the packet pointer and a send capability (obtained previously from the
- The network modules verifies the packet against a template.
- The network module passes the packet to the deiver, which
transmits it (hopefully with DMA).
- Read: sleep on semaphore. Copy packet out of channel. How do you
deal with IP fragments? (Answer: the implementation described in the
- Close: hand channel back to network server so that it can
terminate the connection correctly (TCP WAIT state).
- Sharing of sockets; why is it difficult to get this right in a
- What are the implications of trusting the application to get its
TCP implementation correct? Is that different for a (in-kernel or
out-kernel) server implementation?
- How is memory waste avoided because each application has its own
implementation of TCP? (Answer: shared libraries)
- Performance tables:
- Table 1: What does "user packet size" mean?
- Table 1: Why does Ultrix over Ethernet peak at 7.6?
- Table 1: Why is the "Our Mach" not doing better?
- Table 2: Why does Our mach better than Mach/UX?
- Table 3: What applications are hurt by slow connection setup?
- How important is batching?
- How would the numbers change on faster machines?
- What applications demonstrate the extensibility of user-level networking?