Trading packet headers for packet processing

Abstract

In high speed networks, packet processing is rel- atively expensive while bandwidth k cheap. Thus, it pays to add information to packet headers to make packet processing easier. While this is an old idea, we describe severat specific new mechanisms based on this principle. We describe a new technique, source hashing, which can provide ()( 1) lookup costs at the data link, routing, and transport layers. Source hashing is especially powerful when combined with tbe old idea of a flow identifier fjkw ID); the fknv ID allows packet processing information to be cached and source hashing allows efficient cache lookups. Unlike virtual circuit identifiers (VCI'S), source hashing does not require a round-trip delay for set up. (n an experiment with the BSD packet filter implementation, we found that adding a jo., ID and a source bash improved packet processing costs by a factor of seven. We also found a 45 ~0 improvement when we conducted a simitar experiment with 1P packet forwarding. We also describe two other new techniques: threaded indices, which allows fast VCI-like Iookups for datagram protocols like 1P and a Data Manipulation Layer (DML), which compiles out all the information needed for integrated layer processing (ILP) and scheduling into an easily accessible portion of each packet.