Layered cutting scheme for packet classification

Yeim-Kuan Chang, Han Chen Chen

研究成果: Conference contribution

6 引文 斯高帕斯(Scopus)

摘要

Packet classification is an important topic for highspeed routers nowadays. There are many packet classification algorithms based on decision tree like Hicuts, Hypercuts and Hypersplit. Because Hicuts and Hypercuts divides the rule sets by cutting the address space into equal-sized subspaces, their cutting efficiency is not good. Although Hypersplit proposed a good end-point-based cutting scheme, the resulting tree depth is still very high. In this paper, we propose a multi-dimensional cutting algorithm to significantly reduce the decision tree depth and a multi-layered scheme to dramatically reduce the usage of memory. Our experimental results show that the proposed layered scheme needs much less memory than Hypersplit for Firewall and IPC rule tables with a factor of 2 to 106 improvement while the proposed layered scheme needs a little more memory than Hypersplit for some of ACL tables. In addition, in terms of number of memory accesses, the proposed layered scheme and Hypercuts are better than Hicuts and Hypersplit for all tables while the proposed layered scheme is better than Hypercuts for ACL and Firewall tables. In terms of number of memory accesses, our layered cutting scheme and Hypercuts perform equally well for small rule tables. But, in larger rule tables, the proposed layered cutting scheme has better performance.

原文English
主出版物標題Proceedings - 25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011
頁面675-681
頁數7
DOIs
出版狀態Published - 2011 6月 3
事件25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011 - Biopolis, Singapore
持續時間: 2011 3月 222011 3月 25

出版系列

名字Proceedings - International Conference on Advanced Information Networking and Applications, AINA
ISSN(列印)1550-445X

Other

Other25th IEEE International Conference on Advanced Information Networking and Applications, AINA 2011
國家/地區Singapore
城市Biopolis
期間11-03-2211-03-25

All Science Journal Classification (ASJC) codes

  • 一般工程

指紋

深入研究「Layered cutting scheme for packet classification」主題。共同形成了獨特的指紋。

引用此