High-speed packet classification for differentiated services in next-generation networks

Pi Chung Wang*, Chia Tai Chan, Shuo Cheng Hu, Chun Liang Lee, Wei Chun Tseng


研究成果: Article同行評審

23 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)925-934
期刊IEEE Transactions on Multimedia
出版狀態Published - 12月 2004


深入研究「High-speed packet classification for differentiated services in next-generation networks」主題。共同形成了獨特的指紋。