Fast compression state lookup of Internet packet headers

The focus of this paper is on the engineering of a work efficient IPv6 header compressor. We introduce a new adaptive data structure, the move-to-root Patricia tree, with favorable properties for this particular application. Considerable effort has been devoted to an efficient implementation in the C programming language, and the incorporation of the data structure with an existing IPv6 header compression implementation for the NetBSD operating system. Experiments performed on a 200 MHz Pentium Pro machine running NetBSD 1.2 show that the data structure gives extremely fast compression state lookup. Our results indicate that we can perform lookup on approximately 100,000 headers per second. Assuming an average packet size of 125 bytes, this translates into a link capacity of 100 Mbits per second. 1. Introduction In today's Internet, a widely used method for increasing the bandwidth utilization is header compression. The header compression algorithm groups packets into flows where the ...<p>Godkänd; 1997; Bibliografisk uppgift: Presented at Workshop on Algorithm Engineering, Venice, 11-13 September 1997; 20080506 (ysko)