Tom Herbert, SiPanda CTO, August 12, 2024.
Way back in the early 90’s when I was a grad student at Purdue, one of my fellow students was lamenting about protocols with Variable Length Headers (or VLH). I suppose this was probably in reference to variable length IPv4 headers that can have options. My thought at the time was “what’s the big deal?”-- RFC791 was clear on the requirements and it isn't exactly hard to code up VLH in software. Fast forward to today, many people, in particular hardware vendors trying to build high speed data paths, are still lamenting VLH! They are especially leary of Type Length Values (TLVs), which are not only variable length but combinatorial in the number of possible TLV types in a packet. Nertheless, I’m still inclined to say “what’s the big deal?” ;-), but this time around I’ll show why these protocols with variable length headers and TLVs aren’t as hellish as they’re made out to be!
Network protocol parsing– a few basics
Network protocol parsing is essential in network processing, and is perhaps the most common operation in a networking stack. Basically, every packet ever received by any device needs to be parsed to some extent, so we want parsing to be fast as possible . Parsing can be defined as the operation of inspecting network packets to identify and process their constituent protocol layers, and so a protocol parser is then an entity that parses a set of protocols. A parse graph shows the various protocols that may be parsed and their relationships. The diagram above is an example parse graph and “parse walk” for parsing an example packet.
Example parse graph and parsing a packet. This diagram shows a parse graph with common networking protocols and parsing of a TCP/IPv4 packet in GRE in IPv6 with Hop-by-Hop Options. The linearized parse walk is shown at the bottom.
The annoying thing about parsing is that it is inherently a serialized operation. As a parser parses a packet, it needs to parse each encapsulated protocol header in order– there’s really no way around this. Some vendors have skirted this requirement by limiting support to a small set of protocols. For instance, some routers only forward plain TCP or UDP over IPv4 or IPv6 packets in the fast path; packets with IP options, extension headers, or other transport protocols are either relegated to the slow path or just outright dropped. By artificially limiting the “allowed” set of protocols, it’s possible to employ TCAMs or other hardware techniques, but that’s at the cost of limiting the user and deployability of protocols. Sadly, this technique has been used many times over, and the net effect is that we have an ossified Internet that forces the Least Common Denominator as the status quo. We need to do better than that! Fortunately there is a way: make the parsing function efficient so that it’s not a problem even in hardware!
Bare minimum parser processing
We first ask what the minimal processing is needed to parse a protocol header. In a nutshell we need to identify the protocol of each protocol header in a packet, verify and optionally process the header, and then proceed to the next header. The input to the process is a packet, and as it turns out there’s just two things the parser needs to deduce from each protocol header for this processing:
The length of the protocol header and hence the offset of the next header
The type of the next header protocol for non-leaf protocols.
With this understanding, we can formulate the procedures for parsing a protocol header. We assume that the parser has a concept of a “current header” that is indicated by a pointer to the first byte of the header being processed. The parsing procedures are then:
Check the minimum length of the protocol header. All protocol headers, even VLH ones, have some minimum length requirement. For instance, the minimum length of an IPv4 header is twenty bytes. Make sure that the minimum length of the current header fits within the extent of the packet. If the length check fails, stop parsing and report the error.
Determine the length of the current protocol header. This can be a fixed length which is typically the minimum length also (the IPv6 header is forty bytes for instance), or derived from the packet for a variable length header (for instance, the length of the IPv4 header equals the IP header length field value multiplied by four).
Check that the length of the whole header is valid, that is the derived length fits within the extent of the packet. If the check fails, stop parsing and report an error.
Determine the type of next header for a non-leaf protocol. This is usually decuded by reading a “next protocol” field in the current header.
For a non-leaf protocol, perform a table lookup on the next protocol type. This returns the next node in the parse graph to process. If a next node is found then set the current protocol pointer to of the offset of the next header (current offset plus length of the header), and jump to processing for the next node (loop to step 1).
The diagram below illustrates basic parsing procedures.
Goin’ beyond the basics
The parsing procedures we described are simple, but foundational. Next time we’ll elaborate a bit on them to show how TLVs and flag-fields are parsed using similar procedures. We’ll also add some ancillary processing into the mix including metadata extraction (that is saving certain fields in a header for later processing) as well as backend processing of the protocol (more than just parsing, but actually processing of the protocol). With these few additions we’ll show how protocol parsing or any Internet protocol can be very efficiently implemented in hardware or software without any artificial restrictions.
SiPanda
SiPanda was created to rethink the network datapath and bring both flexibility and wire-speed performance at scale to networking infrastructure. The SiPanda architecture enables data center infrastructure operators and application architects to build solutions for cloud service providers to edge compute (5G) that don’t require the compromises inherent in today’s network solutions. For more information, please visit www.sipanda.io. If you want to find out more about PANDA, you can email us at panda@sipanda.io. IP described here is covered by patent USPTO 12,026,546 and other patents pending.
Comments