Fast routing lookup and packet classification for next-generation routers

The key to the success of the next generation IP networks to provide good services relies on the deployment of high performance routers to do fast IP routing lookups. In an IP routing lookup, the destination address of an incoming packet is used to search for the next hop by querying a routing table. The routing table consists of a set of IP routes. Searching for the next hop is done in the longest matching manner. That is, the set of routes that match the destination address of the packet is determined. Among them, the longest matching prefix is selected and its corresponding next hop is used for forwarding the packet.; The first part of this dissertation focuses on IP routing lookup problem. A so-called two-trie structure is proposed. The two-trie structure shares nodes representing the front and the rear trie of the route prefixes so that the resulting number of nodes can be reduced. Our simulation results indicate that the memory can be significantly saved while it still provides fast lookups when compared with the standard trie.; The ability to provide differentiated service to users with widely varying requirements is becoming increasingly important. To support service differentiation, the next generation IP routers should be able to identify a flow that an incoming packet belong to based on some criteria on the contents of the packet header other than its IP destination address. This is known as the packet classification.; The second part of this dissertation focuses on two-dimensional packet classification problem, which is of increasing importance due to two major applications: lookups for multicast forwarding and policy-based routing. The dissertation proposes a two-dimensional packet classification scheme based on the assumption that memory cost is cheaper so using larger amounts of memory inefficiently is advantageous if it leads to a simple and fast solution for packet classification problem. Within the current technology, the scheme can be applied to practical sizes of filter databases with fast classification and inexpensive cost.