Protocol Header Design 101

This post does not reflect the views of current, past, or future employers. The opinions in this article are my own.

Sally and Bob have entered the “Design the Next Greatest Networking Protocol” contest. By happenstance, both of them submit protocols that do the exact same thing and carry the same information in their protocol headers. The only difference is how the header fields are formatted — while the content is the same, the structure is different. Is there an objective way for the judges to determine which protocol is better? Let’s see if we can give the judges something to work with!

Building blocks

The basic unit of a protocol header is a byte consisting of eight bits (more formally known as an octet). We can construct larger units as multiples of bytes like half words (two bytes), words (four bytes), and double words (eight bytes). We’ll refer to these units based on bytes as ordinal types. A protocol header is composed of some number of fields. Fields may be ordinal types like bytes or halfwords, or they may be non-ordinal types as bit-fields that are sequences of bits of some length.

The IPv4 header. This is the canonical example of a protocol header. Most fields are ordinal types of 32-bit words (e.g. the source IP address), 16-bit half words (e.g. the checksum), or 8-bit bytes (e.g. time to live). There are four bit-fields (.e.g version and flags) with a size that is not a multiple of eight bits.

To implement a protocol we need to define a protocol data structure in the programming language being used for the implementation. Below is an example that shows the data structure for the IPv4 header in P4, on the left, and in C, on the right.

header ipv4_t {                     struct iphdr {
    bit<4>    version;                  #if defined(__LITTLE_ENDIAN_BITFIELD)
    bit<4>    ihl;                          __u8    ihl:4,
    bit<8>    diffserv;                             version:4;
    bit<16>   totalLen;                 #elif defined (__BIG_ENDIAN_BITFIELD)
    bit<16>   identification;               __u8    version:4,
    bit<3>    flags;                                ihl:4;
    bit<13>   fragOffset;               #endif
    bit<8>    ttl;                          __u8    tos;
    bit<8>    protocol;                     __u16   id;
    bit<16>   hdrChecksum;                  __u16   tot_len;
    ip4Addr_t srcAddr;                      __u16   frag_off;
    ip4Addr_t dstAddr;                      __u8    ttl;
}                                           __u8    protocol;
                                            __u16   check;
                                            __u32   saddr;
                                            __u32   daddr;
                                    }

It’s interesting that everything’s a bit-field in P4, but in C we use ordinal types where possible. For instance, the total length field is defined with type “bit<16>” in P4, but as type “__u16” in C. It’s the same effect, but personally I wish P4 used ordinal types since they’re based on bytes which is the fundamental data unit of all of networking protocols and computers.

Protocol Field Types

To derive some meaningful guidance, let’s start by categorizing protocol field structure. We can base this on three dimensions: whether a field is an ordinal type (i.e. a byte, half word, word, etc.), the bit size of the field, and alignment of the field. Considering these dimensions, we can classify protocol header fields with a Protocol Field Type that gives a hint as to how much effort is needed to process a field.

Type I: Ordinal types

The simplest protocol fields are those that are bytes, half words, words, double words. In a CPU, accessing these ordinal types requires no special operations, simple memory loads and stores suffice.

Type II: Odd multiple of bytes

A field may be composed of multiple bytes where the number of bytes is not a power of two (i.e. not an ordinal type). Perhaps the most common case of this in protocols is a 24-bit field within a 32-word. One could conceive of others like 48-bits in a 64-bit word. These are straightforward to deal with. For a 24-bit field we can load the whole word and then either shift or mask out the extra eight bits depending on alignment.

Type III: Bit-fields in a byte

It’s quite common in protocols to pack bit-fields into a single byte. These are fairly easy to deal with. If the bit-field we’re interested in is aligned to the left of the byte (high order bits) then we can extract the value by a shift right, if the bit-field is aligned to the right then we would mask out the high order bits to extract the value. If the bit-field is in the middle of other bit-fields then we need both a shift and a mask:

bitfield_val = byte_val >> (8 -bit_field_num_bits) / Aligned left /

bitfield_val = byte_val & ~((1 << bit_field_num_bits) -1) / Aligned right /

bitfield_val = (byte_val >> (8 -bit_field_num_bits)) & ~((1 << bit_field_num_bits) -1) / Not aligned /

Type IV: Bit-fields spanning a byte boundary

Now this is where things get interesting. A Type IV field is a bit-field that spans a byte boundary. As we previously discussed, this has performance ramifications if the bit-field endianness of the architecture doesn’t match the data endianness (e.g. we’re accessing a bit-field of a big endian protocol from a little endian CPU). When there’s an endianness mismatch the field is split into two parts: high order bits and low order bits. Accessing the field then requires loading the two parts, left shifting the high order bits by the number of low order bits and then or’ing everything together.

If you looked closely at the data structures for the IPv4 header above, you may have noticed that the C structure does not have a flags field whereas the P4 one does. This could have been represented in the C structure by:

#if defined(__LITTLE_ENDIAN_BITFIELD)
    __u16 frag_offset1: 5;
    __u16 flags: 3;
    __u16 frag_offset2: 8;
#elif defined (__BIG_ENDIAN_BITFIELD)
    __u16 flags: 3;
    __u16 frag_offset: 13;
#endif

The reason they didn’t do that is probably because fragment offset is a Type IV field and it’s just as easy to hide the complexity to process the field in the fragmentation code — we only care about splitting frag_offset into sub-fields when a packet is fragmented, which is reasonably rare. There’s a more interesting example of this in the IPv6 structure:

struct ipv6hdr {
        ...
        __u8                    version:4,
                                priority:4;
        __u8                    flow_lbl[3];
        ...
}

The priority field is actually eight bits and the flow_lbl is twenty bits in the protocol, so the structure definition is incorrect! The comment before the structure plainly says that:

BEWARE, it is incorrect. The first 4 bits of flow_lbl are glued to priority now, forming “class”.

Hmm, the most deployed kernel on the planet admits to being incorrect about what may soon be the most used Layer 3 protocol. Interesting— just say’in :-). Obviously the code works, but yeah, Type IV protocol fields are a major pain in the !#?@&.

Type V: Bit-fields spanning two byte boundaries

If you’re thinking that if a bit-field spanning one byte boundaries is bad then spanning two byte boundaries is worse then you’re right! When there’s an endianness mismatch between the protocol and the CPU the field is split into three parts: high order bits, middle order bits, and low order bits. Accessing the field requires loading the three parts, left shifting the high order bits by the number of low order bits plus the number of middle order bits, left shifting the middle order bits by the number of low order bits, and then or’ing everything together. We show this misery below in code.

Protocol field types in the wild

Let’s take a look at some examples of the different Protocol Field Types and how implementations would process fields for each of our types. We’ll work with some example fields that are illustrated below:

Examples of fields for different Protocol Field Types. The fields of interest are in yellow. The Type I field is the Option Length field in a TCP header, the Type II field is the Virtual Network Identifier (VNI) in VXLAN, the Type III field is the header length from the IPv4 header, the Type IIIa field is the “request close” field from a UET PDS RUD/ROD ACK header, the Type IV field is the next_hdr field in a UET PDS request packet, and the Type V field is rue_info from Falcon Base Acknowledgement header.

The data structures for our examples are defined in the code below. We assume this code will be compiled on a little endian CPU so we only list the bit-field format for little endian.

#include <linux/types.h>

union my_struct {
        struct {
                __u8 type;
                __u8 len; /* <<< Length */
        } type_i; /* Two byte TCP options header */
        struct {
                __u32 vni: 24; /* <<< Virtual Network Identifier */
                __u32 rsvd: 8;
        } type_ii; /* First four bytes of VXLAN header */
        struct {
                __u8 len: 4; /* <<< IPv4 header length */
                __u8 ver: 4;
        } type_iii; /* First byte of IPv4 header */
        struct {
                __u16 next_hdr1: 3;
                __u16 type: 5;

                __u16 rsvd2: 1;
                __u16 request: 2; /* <<< Request close */
                __u16 probe: 1;
                __u16 retrans: 1;
                __u16 ecn_marked: 1;
                __u16 rsvd1: 1;
                __u16 next_hdr2: 1;
                } type_iii_a; /* From UET PDS RUD/ROD ACK */
        struct {
                __u16 next_hdr_ctrl1: 3; /* <<< Next header */
                __u16 type: 5;
                __u16 flags: 7;
                __u16 next_hdr_ctrl2: 1; /* <<< Part 2 */
        } type_iv; /* From UET PDS prologue header */
        struct {
                __u32 rue_info1: 7; /* <<< RUE info */
                __u32 rsvd8: 1;
                __u32 rue_info2: 8; /* <<< Part 2 */
                __u32 oo_wind_notify: 2;
                __u32 rue_info3: 6; /* <<< Part 3 */
        } type_v; /* From Falcon Base ACK header */
};

/* FUnctions to add one to a field */

__u64 func_type_i(union my_struct *s) { return s->type_i.len + 1; }

__u64 func_type_ii(union my_struct *s) { return s->type_ii.vni + 1; }

__u64 func_type_iii(union my_struct *s) { return s->type_iii.len + 1; }

__u64 func_type_iii_a(union my_struct *s) { return s->type_iii_a.request + 1; }

__u64 func_type_iv(union my_struct *s)
{
        return ((s->type_iv.next_hdr_ctrl1 << 1) +
                                        s->type_iv.next_hdr_ctrl2) + 1;
}

__u64 func_type_v(union my_struct *s)
{
        return ((s->type_v.rue_info1 << 14) | (s->type_v.rue_info2 << 6) |
                s->type_v.rue_info3) << 4;
}

For today’s exercise we’re not going to run the program, we just want to compile to a .o and then disassemble it to see what the compiler did. I’m compiling for a RISC-V target.

$ /opt/riscv/bin/riscv64-unknown-linux-gnu-gcc -O3 -c -o test_fields.o test_fields.c

And to generate the disassembly:

$ /opt/riscv64/bin/riscv64-unknown-linux-gnu-objdump -S -d test_fields.o

test_fields.o:     file format elf64-littleriscv

Disassembly of section .text:

0000000000000000 <func_type_i>:
   0: 00154503           lbu a0,1(a0)
   4: 2505               addiw a0,a0,1
   6: 8082               ret

0000000000000008 <func_type_ii>:
   8: 4108               lw a0,0(a0)
   a: 0085551b           srliw a0,a0,0x8
   e: 2505               addiw a0,a0,1
  10: 8082               ret

0000000000000012 <func_type_iii>:
  12: 4108               lw a0,0(a0)
  14: 893d               andi a0,a0,15
  16: 2505               addiw a0,a0,1
  18: 8082               ret

000000000000001a <func_type_iii_a>:
  1a: 4108               lw a0,0(a0)
  1c: 0095551b           srliw a0,a0,0x9
  20: 890d               andi a0,a0,3
  22: 2505               addiw a0,a0,1
  24: 8082               ret

0000000000000026 <func_type_iv>:
  26: 411c               lw a5,0(a0)
  28: 0077f513           andi a0,a5,7
  2c: 00f7d79b           srliw a5,a5,0xf
  30: 8b85               andi a5,a5,1
  32: 0015151b           slliw a0,a0,0x1
  36: 9d3d               addw a0,a0,a5
  38: 2505               addiw a0,a0,1
  3a: 8082               ret

000000000000003c <func_type_v>:
  3c: 411c               lw a5,0(a0)
  3e: 00154703           lbu a4,1(a0)
  42: 07f7f513           andi a0,a5,127
  46: 0067171b           slliw a4,a4,0x6
  4a: 00e5151b           slliw a0,a0,0xe
  4e: 0127d79b           srliw a5,a5,0x12
  52: 8d59               or a0,a0,a4
  54: 03f7f793           andi a5,a5,63
  58: 8d5d               or a0,a0,a5
  5a: 0045151b           slliw a0,a0,0x4
  5e: 8082               ret

Now let’s count the number of instructions to process the field of each type:

Count of instructions to process protocol fields for different Protocol Field Types.

Categorizing existing protocol headers

So now we can characterize protocol fields with a measure of their processing complexity, next we’ll survey various protocols and count the number of fields they have for each Protocol Field Type. This can be thought of as one measure of a protocol’s complexity (although certainly not the only one!).

Counts of fields of the various Protocol Fields Types for different protocols. The left column gives the protocol header and the right columns give the number of fields in the protocol header definition for the Protocol Field Types. means that a Type I field is included that contains single bit flags; single bit flags are easily extracted or set in a word so we don’t need to consider them as their own type. ^ indicates the protocol header has reserved fields that are not counted under the field types.*

Protocol header design principles

The data from our little experiment is clear and I believe is good input into deriving some guidelines for protocol header design. So for our judges of the protocol design contest they might want to consider:

• The fundamental data unit of a protocol header is the byte. Specifically, an octet of eight bits. Ordinal types of a byte, two bytes, four bytes, and eight bytes make for good field sizes.
• Protocol header length should generally be a multiple of four bytes (thirty-two bits). There are exceptions like when a header is effectively a sub-header as in the case of a two byte TCP option header. Typically the start of a protocol header is at a four or eight byte offset from the start of the packet (it’s common to insert two byte padding in front of the Ethernet header to properly align the following network header).
• Protocol fields with a lower Protocol Field Type classification are generally better than higher numbered ones. For instance, a bit-field constrained to one byte (Type III) is almost certainly better than the bit-field spanning a byte boundary (Type IV). Or, if you’re using a Type V bit-field spanning two byte boundaries you might want to consider rearranging it so that it spans one byte boundary as a Type IV field.
• Minimize use of reserved fields. Like about 99% of the time, reserved fields are never unreserved for real fields. It’s almost always better to only use reserved fields solely for padding.
• Pack bit flags into one word (most protocols already do that anyway).
• Mind cache locality. If your protocol spans multiple cache lines, think about grouping fields together to promote cache locality. Also, think about cache locality with respect to the whole packet.
• If your protocol has a version field put it at the very beginning of the header in the first byte like in the IP header. That way we only need to decode the first byte to determine the format of all the following bytes. Side note: I’ve gone back and forth about whether protocols should have a version field. These days I’m inclined to believe they’re mostly a waste of precious protocol header space. For new protocols encapsulated in UDP, I think it’s just as easy to forego the version number and get a UDP port number for each version.
• Fixed length headers or variable length headers?… Well that’s the existential question and a story for another day! :-)

Anyway, that’s it. Good luck to Sally and Bob and all would-be protocol designers!