Nowadays, IP networks are rapidly evolving toward a QoS-enabled infrastructure. The need for packet classification is increasing in accordance with emerging differentiated services. While the new differentiated services could significantly increase the number of rules, it has been demonstrated that performing packet classification on a potentially large number of rules is difficult and has poor worst-case performance. In this work, we present an enhanced tuple pruning search algorithm called "tuple pruning plus" (TPP) for packet classification, which outperforms the existing schemes on the scalability. Our main idea is to simplify the lookup procedure and to avoid unnecessary tuple probing by maintaining the least-cost property of rule through precomputation and the proposed information marker. With extra rules added for information marker, only one tuple access is required in each packet classification. In our experiments, 70 MB DRAM is used to achieve 50 million packets per second (MPPS) for a 1 M-rule set, showing a performance improvement by a factor of 50. We also present a heuristic to further reduce the required storage to about 20 MB. These results demonstrate the effectiveness of the TPP scheme to achieve high speed packet classification

Ternary content addressable memory (TCAM) is favorable for high-speed search due to its parallel architecture and ability for searching arbitrary-length keys. However, the usage of TCAM is limited because of its high cost and power consumption. This paper introduces a TCAM-based Huffman decoding algorithm for single-side growing Huffman tree (SGH-tree), which has been proposed to reduce the sparsity of traditional Huffman tree. Our scheme is based on the property, which leaves in the SGH-tree are highly concentrated. By extracting and searching the common prefixes of the codewords, the power consumption and the required storage of TCAM can be significantly reduced as well as its cost. In our experiments based on twelve real images, the power consumption is reduced to twentieth as compared to the original implementation.

To reduce the memory size and fasten the process of searching for a symbol in a Huffman tree, we exploit the property of the encoded symbols and propose a memory-efficient data structure to represent the Huffman tree, which uses memory nd bits, where n is the number of source symbols and d is the depth of the Huffman tree. Based on the proposed data structure, we present an O(log n)-time Huffman decoding algorithm. An adaptive version for single-side growing Huffman tree is also addressed. This version could improve the average performance from log n to /spl Sigma//sub i//sup n//spl lceil/i/(h - 1)/spl rceil/ /spl times/ w/sub i/log h//spl Sigma/w/sub i/, where w/sub i/ is the frequency for i/sub th/ symbol and h is a pre-defined value.

To provide differentiated quality of service, packet classification is important for determining which flow an incoming packet belongs to so as to decide what service quality it should receive. Packet classification is essentially a problem of multidimensional range matching. Tuple space search is a well-known solution based on multiple hash accesses for various filter length combinations. Tuple pruning algorithm is a tuple-based algorithm which is able to achieve good performance in a practical environment; however, its worst-case speed is not guaranteed. We explore the relative property of filters and reorganize the filters through filter conversion. As compared with the tuple pruning algorithm, the proposed scheme can significantly improve the worst-case performance. Experimental results on both real-world and synthetic filter databases show that the worst-case lookup speed of the proposed scheme is 9 to 31 times faster than that of the tuple pruning algorithm.

In next-generation networks, packet classification is important in fulfilling the requirements of multimedia services, including VoIP and VoD. Using pre-defined filters, the incoming packets can be categorized that determines to which forwarding class a packet belongs. Packet classification is essentially a problem of multidimensional range matching. The tuple space search is a well-known solution based on multiple hash accesses for various filter length combinations. The tuple-based algorithm, a rectangle search, is highly scalable with respect to the number of filters; however, it suffers from the memory-explosion problem. Besides, the lookup performance of the rectangle search is not sufficiently fast to accomplish high-speed packet classification. This work proposes an improved scheme to reduce the required storage and realize OC-192 wire-speed forwarding. The scheme consists of two parts. The "Tuple Reduction Algorithm" drastically reduces the number of tuples by duplicating filters. Dynamic programming is used to optimize the tuple reduction and two heuristic approaches are introduced to simplify the optimization process. Furthermore, the "Look-ahead Caching" scheme is presented to improve the lookup performance. The basic idea is to prevent unnecessary tuple probing by filtering out the "un-matched" situation of the incoming packet. The experimental results show that combining the tuple reduction algorithm with look-ahead caching increases the lookup speed by a factor of six while requiring only around one third of the storage. Additionally, an extension of multiple fields to more general filters is addressed.