Algorithmic approaches for IP address lookup and packet classification

Abstract

The basic function of an Internet router is to forward packets towards their destinations. As the applications in the Internet are evolving towards multimedia-oriented and QoS-aware, more complex analysis of the incoming packet is performed by the routers in addition to the IP address lookup. Routers are required to classify packets based on multiple header fields into equivalence classes called flows. The challenges for the IP address lookup and packet classification are driven by the following factors: (i) the rapid growth of communication bandwidth, (ii) the expected growth of the routing table and filter database, (iii) the deployment of IPv6, and (iv) fast incremental update. This thesis presents algorithmic approaches to solve these problems. The first contribution of this work is the design of an efficient hardware solution for IP address lookup. The problem is modeled as a searching problem on a binary-trie. The binary-trie is partitioned into fixed size non-overlapping sub-trees. Each sub-tree is represented using a bit-vector and can be searched in parallel for the best matching prefix. The address lookup is implemented using hardware pipeline with a throughput of one lookup per memory access. A distinguishing feature of our design is that routing table entries are not replicated in the data structure. Hence, table update can be done in constant time with only a few memory accesses. Our design can be extended to IPv6. The second contribution of this work is the design of a two-stage approach for packet classification. The first stage determines the best matching source and destination prefix pair and the second stage determines the highest priority matching filter by comparing the remaining fields against a short list of candidate rules in parallel. The first stage 2- dimenional search problem is reduced to a l-dimenional search problem by a process called filter decomposition. The decomposed filters are organized as a height-balanced search tree. The search operation is speeded up by parallel processing techniques to achieve a throughput of one packet per memory cycle. Our design is scalable to larger rule databases and IPv6. It also allows the incremental updates the data structures.

Date of Award	3 Oct 2005
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chi Wai Derek PAO (Supervisor)