成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	賴弈豪 Lai, Yi-Hao
論文名稱：	用於全區域網路以位址區間編碼及雜湊表為基礎的封包分類方法 Range Encoding and Hash table based Packet Classification for Global View Networking
指導教授：	張燕光 Chang, Yeim-Kuan
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2017
畢業學年度：	105
語文別：	英文
論文頁數：	61
中文關鍵詞：	封包分類、IP查詢、編碼、雜湊表
外文關鍵詞：	Packet Classification, IP lookup, Encoding, Hash table
相關次數：	點閱：87 下載：2
分享至:	分享至facebook 分享至twitter

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

封包分類是路由器中的一個重要功能，它有許多應用，像是連線品質管理(QoS)、防火牆、流量控制和分析等等。而隨著網路的發展與軟體定義網路(SDN)的出現、全區域網路架構中的封包分類不再僅僅是用來解決單一路由器上查詢的問題。全區域網路需要得到的是封包的網路表現(network-wide behavior)，也就是路由器上輸出結果的集合。由於查詢變得更為複雜，傳統上一般的封包分類方法已不足以使用在現今的網路架構。
在這篇論文中我們提出一個名為 Range Encoding Hash Table (REHT)的兩層封包分類架構，能夠有效的解決全區域網路架構中，多個規則表與路由表混和的封包分類問題。第一層對各個維度的輸入值做區段編碼的處理，第二層對編碼後的結果做hash 來達快速的封包分類查詢。在多維度的規則表中，有些維度可能是 wildcard 或是包含很大一區段的值，這樣的規則會導致建立 hash 表時發生記憶體使用量過大的問題。針對這樣的問題，我們定義規則集中各維度 wildcard 的標準，並以此來做 hash table 的分組，減少記憶體的使用量。
透過用 hash 的方法來存取規則，我們可以解決 cross-product 所可能產生的記憶體過大的問題，又同時能夠快速的查詢，根據我們使用真實網路數據得到的實驗結果顯示，相較於現有的 BDDs 以及 MDD 來查詢封包的網路表現，我們的方法在記憶體使用量與查詢速度都有較好的效能。

Packet classification is an important functionality of the Internet router for many network applications, such as Quality of Service (QoS), firewall, traffic control or analysis. With the development of Internet and the mergence of software-defined networking (SDN), packet classification for global view networking is no longer just used to search for the action taken at a single router. The global view of networks requires to identify the network-wide behaviors of packets, which is defined as the combination of output actions. As the search becomes more complex, traditional packet classification methods are not efficient to be employed in today’s network architecture.
In this thesis, we propose a 2-layer packet classification scheme named Range Encoding Hash Table (REHT). REHT can search for the network-wide behaviors of packets efficiently. In layer 1, we encode the field values of the input header separately. In layer 2, hash tables are used for the encoded values to achieve high classification speed. Some header fields may be wildcard or a large range value in the multidimensional rule table. These rules lead to a memory explosion problem in the hash table. In response to this problem, we define the wildcard standards for each header fields, and reduce the memory usage by the proposed grouping optimizations.
Since we use hashing method to store and search rules, we can solve the problem that cross-product may encounter and also reach very fast classification speed. Experiments with real network datasets show that compared with another two methods for network-wide behaviors, our proposed schemes have better performance in both memory consumption and classification speed.

摘要 i 
Abstract ii 
誌謝 iii 
TABLE OF CONTENTS ................................... iv 
LIST OF TABLES ...................................... vi 
LIST OF FIGURES .................................... vii 
Chapter 1 Introduction ............................... 1 
1.1 Introduction ..................................... 1 
1.2 Organization of the Thesis ....................... 4 
Chapter 2 Background ................................. 5 
2.1 Background ....................................... 5 
2.2 Difficulty in Network-wide Behaviors ............. 7 
Chapter 3 Related Work .............................. 10 
3.1 Overview ........................................ 10 
3.2 HiCuts .......................................... 11 
3.3 HyperCuts ....................................... 14 
3.4 BDDs ............................................ 16 
3.5 MDD ............................................. 18 
3.6 RFC ............................................. 19 
3.7 Cuckoo Hashing .................................. 23 
Chapter 4 Proposed Scheme ........................... 25 
4.1 Overview ........................................ 25 
4.2 Range Encoder ................................... 31 
4.2.1 Direct Entry Mapping .......................... 32 
4.2.2 Multiway Range Tree ........................... 32 
4.2.3 Conditional Judgment .......................... 34 
4.3 Hash Table ...................................... 35 
4.3.1 Inserting Rules ............................... 35 
4.3.2 Possibility Bitmap ............................ 37 
4.3.3 Searching Process ............................. 38 
4.4 Optimized Scheme for ACL Rule ................... 40 
4.4.1 Permit Bitmap ................................. 44 
4.4.2 Grouping Optimized ............................ 48 
Chapter 5 Performance Evaluation .................... 50 
5.1 Introduction .................................... 50 
5.2 Experimental Analysis ........................... 51 
5.3 Experimental Results ............................ 54 
5.4 Conclusions ..................................... 57 
Reference 59 

                                    

[1] A. Feldman and S. Muthukrishnan, “Tradeoffs for Packet Classification,” in Proceedings of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 1193-1202 vol.3, 2000.
[2] B. Vamanan, G.Voskuilen, T. Vijaykumar, “EffiCuts: Optimizing Packet Classification for Memory and Throughput,” in ACM SIGCOMM, 2010.
[3] D. E. Taylor, “Survey and Taxonomy of Packet Classification Techniques,” in ACM Computing Surveys, vol. 37, no. 3, pp. 238-275, Sep. 2005.
[4] D. E. Taylor, J. S. Turner, “ClassBench: A Packet Classification Benchmark,” in IEEE/ACM Transaction on Networking, vol. 15, pp. 499-511, 2007.
[5] F. Baboescu, G. Varghese, “Scalable Packet Classification,” IEEE-ACM Transactions on Networking, vol. 13, no. 1, pp. 2-14, Feb. 2005.
[6] F. Geraci, M. Pellegrini, and P. Pisata, “Packet Classification via Improved Space Decomposition Techniques,” in Proceedings of 24th Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 304-312 vol. 1, 2005.
[7] H. J. Chao, “Next Generation Routers,” in Proceedings of the IEEE, vol. 90, no. 9, pp. 1518-1558, Sep. 2002.
[8] H. Lu, S. Sahni, “O(log W) Multidimensional Packet Classification,” in IEEE/ACM Transactions on Networking, vol. 15, no. 2, pp. 462-472, Apr. 2007.
[9] K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary. “Algorithms for Advanced Packet Classification with Ternary CAMs,” in Proceedings of the ACM SIGCOMM ’05 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM ’05), pp. 193 – 204, 2005.
[10] R. Cohen and D. Raz, “Simple Efficient TCAM based Range Classification,” in Proc. IEEE Conf. Commun. (INFOCOM’11), pp. 196-200, Apr. 10-15, 2011.
[11] H. Song and J. W. Lockwood, “Efficient Packet Classification for Network Intrusion Detection Using FPGA,” Proc. Thirteenth ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA), 2005.
[12] W. Jiang and V. K. Prasanna, “Scalable Packet Classiﬁcation on FPGA,” IEEE Transactions on vary large scale integration (VLSI) systems, vol. 20, no. 9, pp. 1668– 1680, 2012.
[13] J. M. Wagner, W. Jiang and V. K. Prasanna, “A Scalable Pipeline Architecture for Line Rate Packet Classification on FPGAs,” Proc. The 21st IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS), 2009.
[14] P. Gupta and N. McKeown, “Algorithms for Packet Classification,” in IEEE Network, vol. 15, no. 2, pp. 24-32, Mar.-Apr. 2001.
[15] P. Gupta and N. McKeown, “Packet Classiﬁcation Using Hierarchical Intelligent Cuttings,” in Proceedings. IEEE High-Performance Interconnects, pp. 34-41, 1999.
[16] T. V. Lakshman and D. Stiliadis, “High-Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching,” in Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, pp. 203-214, 1998.
[17] P. Gupta, and N. McKeown, “Packet Classification on Multiple Fields,” in Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, pp. 147-160, 1999.
[18] S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet Classification Using Multidimensional Cutting,” in Proceedings. ACM Special Interest Group on Data Communication, pp. 213-224, 2003.
[19] R.E. Bryant, “Graph-based algorithms for boolean function manipulation,” in IEEE Transactions on Computers, C-35(8):677–691, 1986.
[20] A. Srinivasan, T. Ham, S. Malik, and R.K. Brayton, “Algorithms for discrete function manipulation,” in IEEE ICCAD, pages 92–95, 1990.
[21] H. K. Yang and Simon S. Lam, “Real-time Veriﬁcation of Network Properties using Atomic Predicates,” in 2013 21st IEEE International Conference on Network Protocols (ICNP).
[22] T. Inoue, T. Mano, K. Mizutani, S. Minato, and O. Akashi, “Rethinking Packet Classification for Global Network View of Software-Defined Networking,” in 2014 IEEE 22nd International Conference on Network Protocols (ICNP), pp. 296-307.
[23] Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher, “Cuckoo
Filter: Practically Better Than Bloom,” in 10th ACM International on Conference on
emerging Networking Experiments and Technologies, 2014, pp.75-88.
[24] Y. C. Cheng and P. C. Wang, “Packet Classification Using Dynamically Generated Decision Trees,” in IEEE Transactions on Computers, vol. 64, pp. 582-586, 2015.
[25] Y. K. Chang and C. Y. Chien, “Layer Partitioned Search Tree for Packet Classification,” in IEEE 26th International Conference on Advanced Information Networking and Applications, pp. 276-282, 2012.
[26] Y. K. Chang and H. C. Chen, “Layered Cutting Scheme for Packet Classification,” The IEEE 25th International Conference on Advanced Information Networking and Applications (AINA-2011), 2011.
[27] Y. K. Chang and K. Y. Liu, “An Efficient TCAM Update Scheme for Packet Classification,” in IEEE 27th International Conference on Advanced Information Networking and Applications, pp. 1017-1024, 2013.
[28] Y. K. Chang and Y. H. Wang, “Cubecuts: A Novel Cutting Scheme for Packet Classification,” in Proc. IEEE Workshops Int. Conf. Adv. Inf. Netw. Appl, 274–279, 2012.
[29] Y. K. Chang, “Efficient Multidimensional Packet Classification with Fast Updates,“ IEEE Transactions on Computers, vol. 58, no. 4, pp. 463-479, Apr. 2009.
[30] Y. K. Chang, “Fast Binary and Multiway Prefix Searches for Packet Forwarding,” Computer Networks, vol. 51, no. 3, pp. 588-605, Feb. 21 2007.
[31] Y. K. Chang, C. C. Su, Y. C. Lin, and S. Y. Hsieh, “Efficient Gray Code Based Range Encoding Schemes for Packet Classification in TCAM”, IEEE/ACM Transactions on Networking, pp. 1201-1214, 2013
[32] Y. K. Chang, Y. S. Lin, and C. C. Su, “A High-Speed and Memory Efficient Pipeline Architecture for Packet Classification,” Proc. the International IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM), pp.215 - 218, 2010.
[33] Y. K. Chang and Y. C. Lin, “Dynamic Segment Trees for Ranges and Prefixes”, IEEE Transactions on Computers, pp. 769-784, 2007.
[34] Y. Qi, L. Xu, B. Yang, Y. Xue, and J. Li, "Packet Classification Algorithms: From Theory to Practice," in Proceedings of INFOCOM 2009, pp. 648-656, 2009.
[35] T. Ganegedara, W. Jiang and V. K. Prasanna, “FRuG: A Benchmark for Packet Forwarding in Future Networks”, in Performance Computing and Communications Conference (IPCCC), 2010 IEEE 29th International, pp. 231-238, 2010.

校內：2020-01-01公開
校外：2020-01-01公開

簡易檢索 / 詳目顯示

相關論文