Fast IP table lookup and packet classification

With the advances of optical transmission technologies such as Wavelength Division Multiplexing, the data rates of the links have increased rapidly in recent years. The packet by packet processing property of router requires faster IP table lookup algorithms to keep pace with the rocking transmission speed. Each router is required to make forwarding decision-the output port number-to each packet based on the destination IP address in the packet header. The development of the Internet and the increase of the number of users make the size of the forwarding table larger and larger. This also challenges the design of the forwarding engine. In the first part of this thesis, the IP table lookup problem is analyzed. We present one fast IP table lookup algorithm which is designed for backbone routers. Besides the development of the Internet itself, the applications that run on the Internet have become more varied. These applications, such as real-time video and voice, require different service quality levels and are expected to be processed separately. Due to the traditional best-effort design of the Internet, which treats all the packets destined to the same IP address identically, it can not provide this kind of service quality level. New functions and mechanisms should be considered. Motivated by this goal, the idea of a flow-aware router emerges. The flow-aware routers are designed to provide differentiated services to different users based on their requirements and expectations of the service quality from the Internet. This requires the router to have the ability to classify the packet into pre-defined flows and treat them differently. The process is called packet classification. The high and increasing link speed of the Internet requires the decision speed of packet classification fast enough. Because the service requirements and expectations of the applications are different, the decision is made on, not only the destination IP address, but the source IP address and even the protocol, port number, link level addresses. All these make the packet classification problem a more challenge one. In the second part of this thesis, we develop a fast packet classification algorithm which is to do two-dimensional packet classification. It also can be extended to a multiple-dimension packet classification. The first algorithm we developed is for packet-by-packet IP routing. In this algorithm, we achieved about 20-30% memory reduction compared with similar routing lookup algorithms. The second algorithm is developed for two-dimensional packet classification and it can be extended to multi-dimensional packet classification. By pipeling, this algorithm can be used for OC-192 link rate. With the development of the Internet, better routing lookup and packet classification algorithms are desired. The research in this area keeps on going