Data Structures and Algorithms for Packet Forwarding and Classification

Summary form only given. Efficient packet forwarding is central to moving traffic smoothly through the Internet. For example, at a line rate of 10Gbps and a minimum packet size of 40 bytes, an Internet router must process more than 30 million packets per second. At 80Gbps, more than 240 million packets must be processed per second. At its simplest, packet processing involves extracting the packet´s destination address, doing a look up in a router table of size up to about 1 million, and sending the packet to its next hop as determined by the table lookup. Besides providing a very high look up rate, an Internet router must be able to update its lookup table at rates that are of the order of 50,000 updates per second (peak). The extreme performance demand on an Internet router may be somewhat reduced by maintaining an additional flow table, filtering out packets that correspond to a packet in the flow table, and doing a router table lookup only for those packets that do not correspond to an existing flow. Power consumption is another very important consideration in the design of an Internet router. For example, Sekiguchi projects that with a 40% annual growth in Internet traffic, the energy consumed by routers in Japan in 2022 will exceed the 2005 gross power generation of Japan. Extensive research has been conducted to develop good data structures to meet the lookup and update requirements of a router as well as to reduce power consumption. This talk reviews some of this research as well as current trends in router design. Sample data structures include multibit one- and two-dimensional tries and hybrid shape shifting tries. Hardware assisted solutions such as Ternary Content Addressable Memories also are reviewed. For more details, see the listed references.