Research On High Speed IP Routing Lookup And Packet Classification Algorithms

Since 1997, the traffic, bandwidth and link speed of the Internet have doubled every six months, which has lead to tremendous increase of packet arrival rate. However, routers are not able to keep up with this pace now because they must execute expensive per-packet processing operations. Besides, IP routing lookup algorithms must be able to lookup large route tables as the Internet scales rapidly. And due to the popularization of IPv6 in the future, IP routing lookup algorithms should have even better performance on searching the huge IPv6 route tables and processing the 128-bit IPv6 addresses.On the other hand, the Internet needs to provide various differentiated services to different users based on their different requirements and expectations of quality. These services include firewall, virtual private network, policy-based routing, QOS control, network intrusion detection, network address translation, congestion control, traffic billing, resource reservation, load balancing, and content-based forwarding, etc. And most of the services are based on packet classification. However, performing classification quickly on multiple fields is known to be difficult, and the fast increase of packet arrival rate also put great pressure on the packet classification algorithms.As the IP routing lookup and packet classification algorithms are at the key position of the networks, they not only provide the basic supports for the Internet, but also have strong influences on its performance and functionalities. Hence high speed IP routing lookup and packet classification algorithms are needed to meet the tendency of the Internet. Therefore, this thesis goes deep into the research of IP routing lookup and packet classification algorithms, and proposes four high speed algorithms for different applications and requirements.Firstly, after the survey and taxonomy of the current typical algorithms, this thesis brings forward an IP routing lookup and classification model, MDCM, based on their spatial geometry essence. And then some important conclusions, methods and principles are brought out to guide the algorithm's design. Particularly, based on the maximal/minimal entropy theory and the experiments for the similarity of prefixes' hash distribution, the maximal entropy criterion method is put forward to choose the hash functions for IP routing lookup algorithms.This thesis also proposes a high speed hardware IPv4 routing lookup algorithm CAT. This algorithm breaks through the generic design pattern, which gets better search performance at the cost of storage and update performance. The CAT algorithm searches faster and needs less memory by utilizing Amdahl's law, the information constrains of the MDCM model, and the features of the group associated CAM and TCAM. Using 10ns CAM and TCAM, it can satisfy the need of the line speed forwarding for the 40Gbps link. Also CAT is a highly parallelized hardware algorithm, and is easy to be pipelined. The CAT algorithm supports fast incremental...