Research On High Performance IP Route Lookup And Packet Classification

IP route lookup and packet classification are two of the key critical data path functions for Internet applications. The rapid progress of Internet development is continuously posing great demands and challenges on their performance. The main contributions of this thesis are two folds: first, it thoroughly studies and analyzes the two problems as well as the associated real-life data distributions, and then provides the directions on how to combine the two research topics and develop efficient processing schemes; second, it proposes a series of novel and high performance algorithms as well as the corresponding mechanisms and thorough performance analysises for both high-end applications and several newly emerging application environments, e.g. embedded system, IPv6 specific occasions and the modern multi-core network processor applications, etc, as the following.The proposed TCAM (Ternary Content Addressable Memory) based route lookup algorithm, T-DPRLA, explores chip-level-parallelism by leveraging a novel distributed parallel architecture, based on a set of heuristic rules to evenly partition the route table and balance the lookup tasks among the TCAM chips. By integrating with an efficient dynamic load-balancing mechanism with only minor overhead, T-DPRLA achieves a deterministic, high and scalable throughput performance. According to the thorough theoretical analysis, the proposed prototype of T-DPRLA can support up to 160Gbps wire speed packet processing with high storage and power efficiency, and is scalable targeting even higher requirements.The proposed TCAM-based packet classification scheme DPPC-RE inherits the idea of exploring chip-level-parallelism from T-DPRLA, and applies it to the problem of packet classification, based on the key observation that the two research topics studied in this thesis are actually with similar underlying mathematic models. Meanwhile, DPPC-RE integrates a range-encoding scheme using the same TCAM chips used for rule-matching. This approach not only solves the range matching problem arised in conventional TCAM-based scheme, but also realizes an efficientdynamic load-balancing mechanism, and therefore achieves a stable high performance in terms of throughput.By leveraging a set of heuristic rules derived from the studies on abundant of real-life route databases and combining the strengths of both CAM-based mechanisms and Trie-based algorithms, this thesis also proposed 1) a high performance route lookup scheme with very low memory requirement especially suitable for embedded applications; 2) a novel dynamic variable stride bitmap compression Trie route lookup algorithm which is especially suitable for IPv6 environment.According to the in deep studies on the packet classification problem and leveraging the features of the popular-gaining multi-core Network Processor (NP) architecture, we develop a parallel packet classification scheme via rule set pre-partitioning (PPCvRP), which not only boosts the performance of conventional software-based algorithms distinctly, but also is with explicit performance and memory cost estimation.