Building-Block Protocols

by
Edoardo S. Biagioni
last updated June 17, 1999

This is a summary describing the ideas and motivation behind building block protocols.

The basic idea is to decompose existing networking protocols into simpler components. It should be possible to easily assemble these components into functional networking protocol stacks. Use of different components or the same components in different orders would lead to different protocols.

One crucial observation is that protocols generally add headers as the packet moves down the stack (to be sent), and correspondingly remove headers as the packet moves up the stack. This is related to another observation, that protocols generally have two types of functions: format and control.

The distinction between format and control is important because most format functions can very naturally be separated so different header fields are checked independently by separate protocol building blocks. This leads to very small building blocks. Control functions often involve multiple header fields, and might be harder to partition.

Many protocols have mostly "format" functions, with the only control being whether to accept or discard a packet. Some examples of these include the ethernet protocol and the host-side IP protocol.

Some examples of building blocks

The above are all very general protocol building blocks. Some of the standard protocols are sufficiently interesting that more specific building blocks might be needed, including: A specific example of a protocol stack that I have built can be used to ping a fixed address. I will first describe the individual protocols in the IP portion of the stack, then specify why I think this model is still insufficient and why and how I am trying to improve it.
  1. a counter protocol to generate the IP packet ID, and ignore it on incoming packets (this stack does not implement IP fragmentation).
  2. a constant protocol to generate the IP fragmentation fields.
  3. an IP-specific protocol to select which interface to use to send the packet.
  4. a de/multiplexer protocol to handle the IP addresses.
  5. a de/multiplexer protocol to handle the IP protocol type field and de/multiplex to/from TCP, UDP, ICMP.
  6. a constant protocol to generate the IP time-to-live field, and a void protocol to ignore the field on receipt.
  7. a swap protocol to put the IP address information in its proper place (on sending) or bring it to the front of the header (on receipt). This swapping is needed because the IP header fields are not in the order in which we would like them for processing using the building blocks.
  8. a length protocol to generate and check the packet length. This protocol adds a constant to the length of the packet seen by this protocol, to take into account the IP header fields not yet generated or already stripped in processing.
  9. two constant protocols to generate the type of service and the header length and IP version number (the type of service is ignored on receipt).
  10. a checksum protocol to generate the IP header checksum.
  11. a swap protocol to put the IP header checksum into its place (sending) or move it to the front of the packet (receiving).
For reference, here is the format of the constant part of the IP header, from RFC 791:
    0                   1                   2                   3   
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |Version|  IHL  |Type of Service|          Total Length         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Identification        |Flags|      Fragment Offset    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Time to Live |    Protocol   |         Header Checksum       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                       Source Address                          |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                    Destination Address                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Some of the things I am unhappy about with the building-block implementation described above, in no particular order:

Related Ideas

Work so far

I have a simple plan for how to partition the standard TCP/IP protocol stacks into building blocks.

You may also look at my (unedited) source code for the SML building blocks. This is work done while I was at Carnegie Mellon University.

Blanca Lopez designed a simple ethernet protocol, and has begun (but does not expect to complete) an implementation in C.