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.
- format makes sure the packet is formatted correctly when it is
sent and makes sure incoming packets are acceptable. This correctness
is both syntactic, relating the different components of data in the
packet, and semantic, relating the contents of the packet to the state
of the sender or receiver.
- control insures that appropriate actions occur as a result of
sending or receiving packets, and can only be invoked if the packet is
syntactically and semantically correct. Actions might include putting
the packet in a queue, segmentation or reassembly, starting a timer,
and so on.
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 constant protocol simply adds a fixed-size constant
header to all outgoing packets. For receiving packets, the constant
protocol discards packets that don't match its constant header. This
can be useful for example in building a custom protocol to send
ethernet packets from a fixed source to a fixed destination.
- The length protocol adds a header containing the packet
length. On receipt, the packet is discarded if it is too short,
accepted otherwise. If the length is too long, the packet is trimmed
before it is accepted. A good use of this protocol would be in
generating and accepting the IP packet length field.
- A multiplexer protocol adds a header containing a value
that reflects which of several higher-level protocol stacks this
packet was sent from. A corresponding demultiplexer protocol
checks the header of incoming packets and dispatches the packet to one
of several higher-level protocol stacks. This has many applications,
including generating and processing addresses, protocol type fields
(ethernet and IP), port numbers (UDP and TCP), and so on.
- A counter protocol adds a header containing a value that
is incremented, as an integer, every time a packet is sent. On the
receive side, the value can be ignored (by a void protocol
which simply strips the header), checked (by a counter
receive protocol) for correct sequencing, for sequencing with no gaps,
uniqueness, and so on. This can be useful in generating the packet ID
field in the IP header, for ICMP-based applications including ping and
traceroute, and for TCP-like sliding window sequence numbers.
- A CRC protocol can add a standard CRC header or trailer.
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:
- The inetsum protocol computes the Internet checksum.
Parameters specify how many bytes to check, possibly including a
pseudoheader.
- The tcpseq protocol is like counter, but
incrementing by packet size rather than incrementing by one for
each packet.
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.
- a counter protocol to generate the IP packet ID, and
ignore it on incoming packets (this stack does not implement IP
fragmentation).
- a constant protocol to generate the IP fragmentation fields.
- an IP-specific protocol to select which interface to use to send
the packet.
- a de/multiplexer protocol to handle the IP addresses.
- a de/multiplexer protocol to handle the IP protocol type
field and de/multiplex to/from TCP, UDP, ICMP.
- a constant protocol to generate the IP time-to-live field,
and a void protocol to ignore the field on receipt.
- 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.
- 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.
- 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).
- a checksum protocol to generate the IP header checksum.
- 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:
- the sender and receiver are currently tightly coupled. That is,
if I have a constant block on the sender side, I must have a
corresponding constant block on the receiver side. If we
assume that the packet format determines the protocol stack, then this
make sense. However, sometimes flexibility is preferred -- for
example, we'd like to use a counter to generate the packet
ID, then a void to ignore it on receipt (as long as we don't
implement fragmentation. Similarly, coupling the multiplexer and
demultiplexer makes for a more complex building block than would be
needed otherwise. For example, a pair of addresses (as in IP, source
and destination address) are in opposite order for packets being sent
and received (if I am A and sending to B, packets I send have A,B, and
packets I receive have B,A -- this makes it necessary to build a
special-purpose address-handling de/multiplexer).
- the current code is in SML. I'd be interested in using C to see
- how hard this would be to do neatly in C
- whether performance is an issue for building-block protocols
- I have never built a stateful protocol such as TCP, and would
like to do so. I would especially like to do so while using as
few and as small special-purpose building blocks as possible.
- It would be nice to have a user interface to help build protocol
stacks, which right now is still somewhat messy.
Related Ideas
- Building blocks could be seen as the elements in a language for
designing protocols. This is a little weak since the syntax would be
very loose (we'd like to be able to compose most protocols with most
other protocols) and the semantics very complicated (each building
block could be arbitrarily complex) and extensible (people could
write new buliding blocks from scratch)
- Unix (Sys V) Streams tried to do something similar. One of the
differences is they never tried to split each of the TCP/IP protocols
into tiny little bits to be implemented by a different stream
protocol, and so failed (in my opinion) to validate their ideas by
using them to implement standard protocols.
- The x-kernel talks a lot about small building blocks, but again
haven't taken apart TCP or IP. A lot of their building blocks seem
rather complex to me.
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.