成功大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	王之洵 Wang, Chih-Hsun
論文名稱：	對於多層Prefix之二分搜尋封包分類方法 Multi-layered Binary Prefix Search for Packet Classification
指導教授：	張燕光 Chang, Yeim-Kuan
學位類別：	碩士 Master
系所名稱：	電機資訊學院 - 資訊工程學系 Department of Computer Science and Information Engineering
論文出版年：	2016
畢業學年度：	104
語文別：	英文
論文頁數：	67
中文關鍵詞：	封包分類、二分搜尋法、決策樹
外文關鍵詞：	Packet Classification, Binary search, Decision tree
相關次數：	點閱：124 下載：5
分享至:	分享至facebook 分享至twitter

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

封包分類是路由器中的一個主要功能，它有許多應用例如:服務質量(QoS)、安全、監測、分析與網路入侵偵測等。在現今廣為人知的基於決策樹的封包分類方法中，如：HiCuts、HyperCuts、EffiCuts，都會面臨分類規則重複導致記憶體使用量爆炸的問題，並且記憶體存取次數和它們所建決策樹高度的關係密不可分。
在這篇論文中我們提出了一個叫 binary search on buckets(BSOB)的方法來解決多維的封包分類問題。BSOB 利用在決策樹中對已排序好的樹節點之 ID (prefix)做二分搜尋，並事先計算好每一個樹節點與其相關連的祖先節點，給予一條 pointer (fast link)指向其祖先節點，在搜尋到特定樹節點之節點時，fast link 可以用來
直接存取與其相關的節點，減少已知決策樹方法要從根結點遍歷至部分葉節點所需的記憶體存取次數。
為了解決基於決策樹的封包分類方法造成的記憶體爆炸問題，我們將原始的規則表分成多個組別分別建立 BSOB 結構，並利用rule retain的方式，將會造成重複的規則保留在內部節點，因此規則重複的問題可以被減少。
在由 ClassBench 產生的 12 種大小 100K 的分類表，我們在 PC 軟體環境下的實驗結果顯示 BSOB 使用了 2.5-2.8 MB memory，在平均情況下需要 8-15 記憶體存取次數，在最差的情況下需要 21-51 記憶體存取次數，比起已知基於決策樹的方法好上許多。實驗也列出BSOB 的更新數據結果，Insert 動作所需的記憶體存取次數約比搜尋次數高 1-3 倍，刪除動作則是和搜尋相當接近。因為 BSOB 所需記憶體空間小以及分類速度的優點，BSOB 可以處理 SDN 環境下更多維度及更多規則的封包分類問題。

Packet classification is a key functionality of the Internet routers for many network applications, such as Quality of Service (QoS), security, monitoring, analysis, and network intrusion detection (NIDS). The existing well-known decision-tree-based schemes, like HiCuts, HyperCuts and EffiCuts, suffer from a memory explosion problem caused by rule duplication and the number of memory accesses are inseparable with the height of decision tree they built.
In this thesis, we propose a scheme called binary search on buckets (BSOB) for multi-dimensional packet classification problem. BSOB performs binary searches on the ID (prefix) of ordered leaf nodes in the decision tree. We give a pointer to tree node pointing to its
corresponding ancestor node based on their prefix. When searching to a certain node, the fast link can be utilized to directly access to its ancestor node that is related to the certain node. Hence, BSOB can improves the existing well-known decision-tree-based schemes that
need to traverse the decision tree from the root node to some leaf nodes.
In order to solve the memory explosion problem caused by decision-tree-based scheme, we divide the original rule table into multiple groups and construct the BSOB structure to each group. Moreover, we use node retain technique which retains the rule that causes duplication in internal node. Hence, the rule duplication problem can be reduced.
For 12 types classifiers with 100,000 rules generated by ClassBench, our experimental results implemented on a PC software environment show that BSOB uses 2.5-2.8 MB
memory and needs 8-15 memory accesses in average case and 21-51 memory accesses in worst case that is much better than the existing well-known decision-tree based schemes. We also show the update results of BSOB. Insert operation is about 1-3 times higher than search and the delete operation is close to the search speed. Because of the advantage of less memory usage and high classification speed, BSOB is able to address the packet classification problems in SDN environment that has more header fields and large rule sizes.

摘要 .................................................. i 
Abstract ............................................. ii 
誌謝 ................................................. iv 
TABLE OF CONTENTS ..................................... v 
LIST OF TABLES ...................................... vii 
LIST OF FIGURES .................................... viii 
Chapter 1  Introduction ............................... 1 
Chapter 2  Background ................................. 4 
Chapter 3  Related Work ............................... 6 
3.1  Introduction ..................................... 6 
3.2  Bit Vector ....................................... 9 
3.3  RFC ............................................. 11 
3.4  HiCuts .......................................... 14 
3.5  HyperCuts ....................................... 17 
3.6  EffiCuts ........................................ 19 
Chapter 4  Proposed Scheme ........................... 21 
4.1  Rule table analysis ............................. 21 
4.2  Simple Grouping ................................. 24 
4.3  Partition Phase ................................. 26 
4.4  BSOB Construction ............................... 31 
4.5  Classification Phase ............................ 34 
4.6  Why Binary Decision Tree ........................ 39 
Chapter 5  Optimization of BSOB ...................... 40 
5.1  Introduction .................................... 40 
5.2  Reducing Memory Access .......................... 40 
5.2.1  Fast Link ..................................... 40 
5.2.2  Index Range Array ............................. 41 
5.2.3  Record the Priority Value ..................... 43 
5.3  Self-defined Priority ........................... 44 
5.3.1  Why Self-defined Priority? .................... 44 
5.3.2  Rule Space based Scheme ....................... 46 
5.3.3  Rule ID based Scheme .......................... 46 
5.4  Filtering ....................................... 48 
5.5  Using RFC for Group 3 ........................... 49 
Chapter 6  Performance Evaluation .................... 51 
6.1  Introduction .................................... 51 
6.2  Experimental Environment ........................ 51 
6.3  Experiment Results .............................. 52 
6.4  BOSB for Software-defined Networking ............ 62 
Chapter 7  Conclusion ................................ 64 
Reference  ............................................65 
                                    

[1] “OpenFlow Switch Specification V1.1.0,” https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-spec-v1.1.0.pdf
[2] 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.
[3] B. Vamanan, G.Voskuilen, T. Vijaykumar, “EffiCuts: Optimizing Packet Classification for Memory and Throughput,” in ACM SIGCOMM, 2010.
[4] D. E. Taylor, “Survey and Taxonomy of Packet Classification Techniques,” in ACM Computing Surveys, vol. 37, no. 3, pp. 238-275, Sep. 2005.
[5] D. E. Taylor, J. S. Turner, “ClassBench: A Packet Classification Benchmark,” in IEEE/ACM Transaction on Networking, vol. 15, pp. 499-511, 2007.
[6] F. Baboescu, G. Varghese, “Scalable Packet Classification,” IEEE-ACM Transactions on Networking, vol. 13, no. 1, pp. 2-14, Feb. 2005.
[7] 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.
[8] H. J. Chao, “Next Generation Routers,” in Proceedings of the IEEE, vol. 90, no. 9, pp. 1518-1558, Sep. 2002.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] P. Gupta and N. McKeown, “Algorithms for Packet Classification,” in IEEE Network, vol. 15, no. 2, pp. 24-32, Mar.-Apr. 2001.
[14] P. Gupta and N. McKeown, “Packet Classiﬁcation Using Hierarchical Intelligent Cuttings,” in Proceedings. IEEE High-Performance Interconnects, pp. 34-41, 1999.
[15] 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.
[16] 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.
[17] 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.
[18] 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.
[19] T.Y. Woo, “A Modular Approach to Packet Classification: Algorithms and Results,” in Proceedings of Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, pp. 1213-1222 vol.3, 2000.
[20] 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.
[21] 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.
[22] 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.
[23] 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.
[24] 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.
[25] 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.
[26] Y. K. Chang, “Efficient Multidimensional Packet Classification with Fast Updates,“ IEEE Transactions on Computers, vol. 58, no. 4, pp. 463-479, Apr. 2009.
[27] Y. K. Chang, “Fast Binary and Multiway Prefix Searches for Packet Forwarding,” Computer Networks, vol. 51, no. 3, pp. 588-605, Feb. 21 2007.
[28] 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
[29] 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.
[30] 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.

校內：2020-01-01公開
校外：不公開電子論文尚未授權公開，紙本請查館藏目錄

簡易檢索 / 詳目顯示

相關論文