Please use this identifier to cite or link to this item: http://hdl.handle.net/11455/90797
標題: Scalable and Efficient Algorithms for Packet Classification
可擴充性及有效率的封包分類演算法
作者: Jyun-Kai Wang
王俊凱
關鍵字: packet classification
independent sets
封包分類
獨立集
引用: [1] X. Sun, S.K. shahni, and Y. Q. Zhao, 'Packet Classification consuming small amount of memory,' IEEE/ACM Transactions on Networking, vol. 13, no. 5, pp. 1135-1145, 2005. [2] M. Faezipour and M. Nourani, 'Wire-Speed TCAM-Based Architectures for Multimatch Packet Classification,' IEEE Transactions on Computers, vol. 58, no. 1, pp. 5-17 [3] C. Yeim-Kuan, I. L. Chun, and S. Cheng-Chien, 'Multi-field Range Encoding for Packet Classification in TCAM,' in Proceedings of the IEEE INFOCOM., PP. 196-200, 2011 [4] W. Jiang, and Viktor K., 'Scalable Packet Classification on FPGA,' in IEEE transactions on very large scale integration (VLSI) systems, vol. 20, no. 9, pp. 1668-1680, 2012. [5] P. Gupta and N. McKeown, 'Packet classification using hierarchical intelligent cuttings,' in Proceedings of Hot Interconncets VII, August 1999. [6] G. V. Sumeet Singh, Florin Baboescu and J. Wang, 'Packet classification using multidimensional cutting,' in Proceedings of ACM SIGCOMM '03, August 2003, pp. 213-214. [7] H. Liu, 'Efficient mapping of range classifier into ternary-cam,' in Hot Interconncets X, August 2003, pp. 95-100. [8] H. Lim, M. Y. Kang and C. Yim, 'Tow-dimensional packet algorithm using a quad-tree,' in Computer Communications 2007, vol. 30, 2007, pp. 1396-1405. [9] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, 'Fast and scalable layer four switching,' in Proceedings of ACM SIGCOMM '98, September 1998, pp. 191-120. [10] Florin Baboescu, Sumeet Singh, George Varghese, 'Packet Classification for Core Routers: Is there an alternative to CAMs?' in Proceedings of IEEE INFOCOM '03, March 2003, pp. 53-63. June 22, 2010 MANUSCRIPT 34. [11] T. Lakshman and D. Stidialis, 'High-speed policy-based packet forwarding using efficient multi-dimensional range matching,' in Proceedings of ACM SIGCOMM '98, September 1998, pp. 203-214. [12] F. Baboescu and G. Varghese, 'Scalable packet classification,' in Proceedings of ACM SIGCOMM '01, August 2001, pp. 199-210. [13] P. Gupta and N. McKeown, 'Packet classification on multiple field,' in Proceedings of ACM SIGCOMM '99, September 1999, pp. 147-160. [14] V. Srinivasan, G. Varghese, and S. Suri, 'Packet classification using tuple space search,' in Proceedings of ACM SIGCOMM '99, September 1999, pp. 135-146. [15] M. M. Buddhikot, S. Suri, and M. Waldvogel, 'Space decomposition techniques for fast layer-4 switching,' in Proceedings of IFIP Sixth International Workshop on High Speed Networks, 1999, pp. 25-42. [16] T. Woo, 'A modular approach to packet classification: algorithms and results,' in Proceedings of IEEE INFOCOM '00, March 2000, pp. 1213-1222. [17] E. Spitznagel, D. E. Taylor, and J. S. Turner, 'Packet classification using extended tcams,' in Proceedings of IEEE International Conference on Network Protocols(ICNP '03,), November 2003, pp. 120-131. [18] J. van Lunterner and T. Engbersen, 'Fast and scalable packet classification,' IEEE Journal on Selected Areas in Communications, vol. 21, no. 4, pp. 560-571, May 2003. [19] H. Che, Z. Wang, K. Zheng, and B. Liu, 'Dres: Dynamic range encoding scheme for tcam coprocessors,' Computers, IEEE Transactions on, vol. 57, no. 7, pp. 902-915, July 2008. [20] A. Feldmann and S. Muthukrishnan, 'Tradeoffs for packet classification,' in Proceedings of IEEE INFOCOM '00, March 2000, pp. 1103-1202. [21] A. Bremler-Barr, D. Hay, D. Hendler, and B. Farber, 'Layered interval codes for tcam-based classification,' in Proceedings of ACM SIGMETRICS '08, 2008, pp. 445-446. [22] A. Bremler-Barr, and D. Hendler, ' Space-efficient tcam-based classification using gray coding,' IEEE INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, pp. 1388-1396, May 2007. [23] K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary, 'Algorithms for advanced packet classification with ternary cams,' in Proceedings of ACM SIGCOMM '05, 2005, pp. 193-204 [24] P. Gupta and N. McKeown, 'Algorithms for packet classification,' IEEE Network Magazine, vol. 15, no. 2, pp. 24-32, 2001. [25] Chazelle, B., and Guibas, J.,L., 'Fractional Cscading,' Digital Systems Research Center Technical Report, Palo Alto, June 1986. [26] P.-C. Wang, C.-L. Lee, C.-T. Chan, and H.-Y. Chang, 'Performance improvement of two-dimensional packet classification by filter rephrasing,' IEEE/ACM Transactions on Networking, vol. 15, no. 4, pp. 906-917, 2007. [27] Y.-K Chang, 'Efficient Multidimensional Packet Classification with Fast Updates,' IEEE Transactions on Computers, vol. 58, issue 4, pp. 463-479, 2009. [28] A. Kesselman, K. Kogan, S. Nemzer, and M. Segal, 'Space and Speed Tradeoffs in TCAM Hierarchical Packet Classification,' in Proceedings of the IEEE Sarnoff Symposium 2008, pp. 1-6, 2008. [29] T. Mishra and S. Sahni, 'PETCAM-A Power Efficient TCAM Architecture for Forwarding Tables,' IEEE Transactions on Computers, vol. 61, no. 1, pp. 3-17, 2012 [30] B. Lampson, V. Srinivasan, and G. Varghese, 'IP lookups using multiway and multicolumn search,' IEEE/ACM Transactions On Networking, vol. 7, no.4 pp.323-334, June 1999. June 22, 2010 MANUSCRIPT 35. [31] S. Dharmapurikar, H. Song, J. Turner, and J. Lockwood, 'Fast packet classification using bloom filters,' in ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems. New York, NY, USA: ACM, 2006, pp. 61-70 [32] Meiners, C.R., Patel, J., Norige, E., Liu, A.X. and Torng, E., 'Fast Regular Expression Matching Using Small TCAM,' IEEE/ACM Transactions on Networking, vol 22, issue 1, pp.94-109, 2014 [33] E. Taylor and J. S. Turner, 'Classbench: a packet classification benchmark,' in Proceedings of IEEE INFOCOM '05, March 2005, pp.2608-2079. [34] Y. Heeyol and R. Mahapatra, 'A Memory-Efficient Hashing by Multi-Predicate Bloom Filters for Packet Classification,' in Proceedings of the 27th Conference on Computer Communications (IEEE INFOCOM 2008), pp.1795-1803, 2008.
摘要: Abstract Packet classification is important to facilitate various network services in routers. Because Internet traffic increases rapidly, improvement to the performance of packet classification is thus crucial. In this paper, we present several approaches to improving a notable packet-classification algorithm based on independent sets. The independent-set algorithm has superior storage and update performance. However, its performance is tied to the number of independent sets because of too many overlapping field specifications. Our approaches either increase the number of rules in each independent set or eliminate the small independent sets by storing the rules in the form of bit vectors. The experimental results show that the number of independent sets can be drastically reduced. Both search and storage performance can be improved simultaneously.
摘要 封包分類對於增進路由器所提供的各種服務來說非常重要。隨著網路流量的增加,改進封包分類的效能也變得很重要。在本篇論文中,我們提出一些方法去改進一個值得注意的演算法,獨立集演算法(independent-set algorithm)。獨立集演算法有卓越的儲存及更新能力,然而,因為有很多欄位的規範重疊,它的效能跟獨立集的個數息息相關。我們的方法不是增加每個獨立集中的規則數,就是移除較小的讀立集,並將裡面的規則存在bit vector中,使獨立集的個數降低。實驗的結果證明獨立集的數量大大的減少,搜尋及儲存的效能也同時獲得改善。
URI: http://hdl.handle.net/11455/90797
其他識別: U0005-2008201515482900
文章公開時間: 2015-08-25
Appears in Collections:資訊科學與工程學系所

文件中的檔案:

取得全文請前往華藝線上圖書館



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.