成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	李春億 Li, Chun-I
論文名稱：	用於封包分類上的TCAM多維編碼技術 Multi-Dimensional Range Encoding for Packet Classification in TCAM
指導教授：	張燕光 Chang, Yeim-Kuan
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2010
畢業學年度：	98
語文別：	英文
論文頁數：	78
中文關鍵詞：	三態內容尋址記憶體、封包分類、多維範圍編碼
外文關鍵詞：	TCAM, Packet classification, multi-dimensional range encoding
相關次數：	點閱：77 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

封包分類一般是指對進入網路裝置的封包實行分類，判斷其屬於何種”flow”的程序。所有的在相同flow的封包皆必須服從相同的預先定義規則，並採取類似的方式進行處理。目前封包分類已被廣泛的應用在不同的網路服務上，例如利用防火牆防止未經授權的訪問，或是使路由器得以支援QoS服務。為了能夠讓每一個傳入路由器的封包得以正確的尋找到相稱的規則並執行適當的動作，每一個路由器都必須利用內部的規則表來維護所有預先定義的規則。然而，隨著網路發展的速度不斷的提升，規則表也必須隨之成長。因此，在必須儲存龐大規則表的情況下，如何減少路由器的記憶體使用量成了一個非常重要的課題。
在這篇論文中，我們基於三態內容尋址記憶體（TCAM）的硬體，著重在如何以區間編碼的方式降低TCAM的需求量的課題上。觀察目前現有的各種編碼方式，大多數都是單一維度的編碼演算法，執行不同維度的編碼時，必須各自獨立進行。在這篇論文中，我們提出了一個有效率的二維區間編碼演算法。藉由將原本的二維規則表，分割成一組基本區域的集合，並將此基本區域集合映射到多維立方體。而被相同二維範圍所覆蓋的基本區域也可以映射到多維立方體中的一個子立方體，這也表示每一個二維範圍都能夠以一個三元字串來表示。藉由我們提出的編碼演算法，我們可以減少所需的超立方體維度。在透過現實生活中的規則表進行實驗模擬下，比起基於單維的演算法，我們提出的二維編碼演算法確實能夠使用更少的TCAM記憶體使用量。以規則數量為10k的規則表來說，比起效能最好的單維編碼演算法，我們提出的多維編碼演算法能減少18% ~ 25%的TCAM記憶體使用量，而以5k大小的規則表來比較，也能減少20% ~ 25%的TCAM記憶體使用量。

Packet classification is generally referred to the process of categorizing packets into flows in networking devices. All packets belonging to the same flow obey a pre-defined rule and are processed in a similar manner. Packet classification has wide applications such as unauthorized access prevention in firewalls and Quality of Service supported in Internet routers. The Classifier containing all the pre-defined rules are processed by the router for each incoming packet in order to find the best matching rule and take appropriate actions. However, the sizes of classifiers increase as quickly as the Internet traffic grows. Thus, how to reduce the memory usage for storing classifiers in routers is a very important problem. In this thesis, we focus on the range encoding problem in reducing the ternary content-addressable memory (TCAM) requirement. Existing range encoding schemes are usually 1-dimensional schemes that perform range encoding processes in the range fields independently. We propose an efficient 2-dimensional range encoding algorithm. The original 2-dimensional classifier is first divided into a set of elementary regions that will be mapped onto the vertices of a multi-dimensional hypercube. The elementary regions covered by each 2-D range can be also be mapped to a sub-cube in order to represent the 2-D range by only one ternary string. By using the proposed encoding algorithms, we can minimize the size of the hypercube. Our performance experiments on real-life classifiers show that the proposed 2-dimensional range encoding schemes uses less TCAM memory than the previously proposed 1-dimension-based schemes. Compared with the classifiers of 10k rules, our proposed schemes can reduce 18% ~ 25% TCAM memory usage than 1-Dimansional encoding scheme which has the best performance, and in classifiers of 5k rules, our proposed schemes can also reduce 20% ~ 25% TCAM memory usage.

Chapter 1  Introduction...............1
1  Motivation...............1
2  Definition of packet classification problem...............2
3  Metrics for classification algorithms...............3
4  Organization of the thesis...............4
Chapter 2  Previous Works on Packet Classification...............6
1  Organization of the chapter...............6
2  TCAM technology...............7
3  Espresso-II...............9
4  Overview of Range Encoding Schemes...............10
5  Database-independent Encoding Schemes...............11
5.1    Direct range-to-ternary string conversion using BRGC...............11
5.2  Database Independent Range PreEncoding (DIRPE)...............13
5.3  Short Range Gray code Encoding (SRGE)...............15
6  Database-dependent Encoding Schemes...............16
6.1  H. Liu encoding scheme...............17
6.2    Elementary interval based encoding...............19
6.3  Bitmap intersection...............20
6.4  Parallel Packet Classification (PPC)...............21
7  Hybrid Encoding Scheme...............24
7.1  Dynamic Range Encoding Scheme (DRES)...............24
Chapter 3  Proposed Scheme...............25
1  Preliminaries...............25
2  2-Dimensional Range Encoding Algorithm...............26
3  Scheme 1 – Best effort approach...............35
3.1    Problems of Scheme 1...............40
4  Scheme 2 – Systematic approach...............43
5  Scheme 3 – Layer approach...............47
6  Scheme 4 – Optimized layer approach for reducing the number of layers...............51
7  Hardware architecture for proposed scheme...............54
Chapter 4  Performance Simulation...............56
1  Benchmark and performance metrics...............56
2  Simulation environment...............56
3  Test data and comparing schemes...............56
4  Performance Evaluation...............57
Chapter 5  Conclusion...............76
Reference  77
                                    

[1] R. Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, 1984.
[2] A. Bremler-Barr and D. Hendler, “Space-Efficient TCAM-based Classification Using Gray Coding,” Proc. IEEE INFOCOM, 2007.
[3] A. Bremler-Barr, D. Hayy, and D. Hendler, “Layered Interval Codes for TCAM-based Classification,” Proc. IEEE INFOCOM, 2009.
[4] F. Gray, "Pulse Code Communication", U. S. Patent 2 632 058, March 17, 1953.
[5] A. L. Buchsbaum, G. S. Fowler, B. Krishnamurthy, K.-P. Vo, and J. Wang, "Fast Prefix Matching of Bounded Strings", ACM Journal of Experimental Algorithmics, Jan. 2003.
[6] Y.-K. Chang and Y.-C. Lin, "Dynamic Segment Trees for Ranges and Prefixes," IEEE Trans. Computers, Vol. 56, Issue 6, pp. 769 - 784, June 2007.
[7] Y.-K. Chang and C.C. Su, "Efficient TCAM Encoding Schemes for Packet Classification using Gray Code," Proc. IEEE Globecom 2007, pp. 1834-1839, Nov. 2007.
[8] H. J. Chao, “Next Generation Routers,” Proc. of the IEEE, vol. 90, Issue 9, pp.1518-1558, Sep. 2002.
[9] H. Che, Z. Wang, K. Zheng, and B. Liu, “DRES: Dynamic Range Encoding Scheme for TCAM Coprocessors,” IEEE Trans. Computers, Vol. 57, Issue 7, pp.902-915, June 2008.
[10] Q. Dong , S. Banerjee , J. Wang , D. Agrawal , and A. Shukla, “Packet Classifiers in Ternary CAMs Can Be Smaller,” Proc. ACM SIGMETRICS, 2006.
[11] P. Gupta and N. McKeown, “Algorithms for Packet Classification,” in IEEE Network 2001, vol. 15, pp. 24–32, 2001.
[12] P. Gupta and N. McKeown, “Packet Classification on Multiple Fields,” Computer Communication Review, vol. 29, pp. 147–160, Oct. 1999.
[13] T. Lakshman and D. Stiliadis, “High-Speed Policy-Based Packet Forwarding Using Efficient Multi-Dimensional Range Matching,” Computer Communication Review, vol. 28, no. 4, pp. 203–214, Oct. 1998.
[14] K. Lakshminarayanan, S. Venkatachary, and A. Rangarajan,“Algorithms for Advanced Packet Classification With Ternary CAMs,” Proc. ACM SIGCOMM, 2005.
[15] H. Liu, “Efficient Mapping of Range Classifier into Ternary-CAM,” Proc. IEEE Symp. High Performance Interconnects (HOTI’02), 2002.
[16] H. Liu, “Routing Table Compaction in Ternary CAM”, IEEE Micro, Vol. 22, Issue 1, pp. 58-64, Jan-Feb 2002.
[17] J. Lunteren and T. Engbersen, "Fast and Scalable Packet Classification," IEEE Journal on Selected Areas in Communications, Vol. 21, No. 4, May 2003.
[18] C.R. Meiners, A.X. Liu, and E. Torng, “TCAM Razor: A Systematic Approach Towards Minimizing Packet Classifiers in TCAMs,” Proc. IEEE ICNP, 2007.
[19] N. Mohan and M. Sachdev, "Low Power Dual Matchline Ternary Content Addressable Memory," Proc. IEEE ISCAS, pp. 633-636, May 23-26, 2004
[20] B. Schieber, D. Geist, and A. Zaks, “Computing the Minimum DNF Representation of Boolean Functions Defined by Intervals,” Discrete Applied Mathematics, no. 1-3, pp. 154–173, 2005.
[21] D. Taylor, “Survey and taxonomy of packet classification techniques,” ACM Computer Surveys, vol. 37, pp. 238-275, Sep. 2005.
[22] D. Taylor and J. Turner, “ClassBench: A Packet Classification Benchmark,” Proc. IEEE INFOCOM, 2005.
[23] F. Yu and R. H. Katz, “Efficient Multi-Match Packet Classification with TCAM,” Proc. IEEE Symp. High Performance Interconnects (HOTI’04), 2004.
[24] K. Zheng, H. Che, Z. Wang and B. Liu, “TCAM-based Distributed Parallel Packet Classification Algorithm with Range Matching Solution,” Proc. IEEE INFOCOM, Miami, March 2005.
[25] http://www.arl.wustl.edu/~hs1/PClassEval.html, ClassBench: A Packet Classification Benchmark.

校內：2012-08-27公開
校外：2013-08-27公開

簡易檢索 / 詳目顯示

相關論文