臺灣博碩士論文加值系統

許多的網路服務需要有封包分類的功能，像防火牆、提供不同品質的服務、網路計價……等，都需要路由器決定進來的封包屬於那一個服務等級、並且決定如何去處理它。傳統的封包分類器有下列的缺點如無法支援彈性的規則，規則優先權的設定，很差的新增、刪除效率新增、刪除、難以擴充到多個欄位等問題。
在這篇論文之中，我們提出了一個新的封包分類器的架構，除了改善過去已提出的封包分類器架構，解決了擴充至多個欄位的問題，並讓允許使用者可以設定彈性的規則－包括各個欄位區間的設定、規則之間的優先權、not運算子的使用。我們會實作我們的架構於PC-based router上，並且測試其效能，查看是否我們的架構符合真實網路的需求。
另外我們針對規則管理提出一些解決方式，包括偵測規則衝突、如何解決規則衝突，規則更新時的lock機制。一個好的規則管理方式有助於網路管理者訂定出符合期望的網路政策。

Many advanced network services need packet classification, such as like firewalls, QoS, Internet pricing. It is necessary to determine which class of service an arriving packet belongs to as to know how to deal with it. Traditional packet classifier has some drawbacks such as poor support for flexible field, lack of setting precedence order of rule, bad efficiency of updating rules and no easy extension to multi-field.
In this paper, we propose new packet classification architecture. It can easily solve the problem of extension to multi-field and allow network manager to set flexible rule including range type field, precedence order of rule and not operator support. We will implement our architecture on PC-based router, and test it’s performance to evaluation if it fit the need of real network.
Besides, we also propose some method to detect and solve rule conflict and lock mechanism of updating rule. A good rule management will help network administrator to set expected network policy .

謝詞..........................................................五
論文摘要......................................................六
THESIS ABSTRACT...............................................七
目錄..........................................................八
表次..........................................................十
圖次........................................................十一
第一章 緒論...................................................1
第二章 文獻探討...............................................3
第一節 封包分類器問題......................................3
第二節 文獻探討............................................4
2.2.1區間比對..........................................4
2.2.2封包分類演算法....................................5
第三章 索引搜尋法(index search)...............................12
第一節 封包分類器的要求....................................12
第二節 索引搜尋法的概念....................................14
第三節 Group threaded binary search tree..................18
3.3.1 Group Threaded Binary Search Tree概念...........18
3.3.2 區間之間的關係..................................20
3.3.3 Group threaded binary search tree..............21
3.3.4 加入區間........................................23
3.3.5 刪除區間........................................24
3.3.6 搜尋區間........................................25
第四節 加入規則............................................28
第五節 刪除規則............................................30
第六節 搜尋規則............................................31
第七節 索引搜尋法的效率.....................................32
3.6.1Group threaded binary search tree的效率...........32
3.6.2索引搜尋法的time complexity.......................33
3.6.3 Index search vs. Linear Search...................33
3.6.4 Index search vs. Hierarchical Tries..............34
第八節 not邏輯運算子的支援..................................36
第四章 系統實作和效能評估......................................37
第一節 系統架構...........................................37
第二節 更新規則的機制......................................39
第三節 規則管理...........................................41
4.3.1規則衝突(Rule Conflict)..........................41
4.3.2規則衝突的解決方式................................41
第四節 效能評估...........................................43
4.4.1 Interval Tree和Group Threaded Binary Search Tree的比較..........................................................43
4.4.2 Index Search和linear Search的比較...............49
4.4.3 規模化測試(Scalability Test)....................51
第五章 結論...................................................53
參考文獻......................................................54

[1]H. Adiseshu, S. Suri, and G. Parulkar, “Detecting and resolving packet filter conflicts,” In Proc. INFOCOM, volume 3, pages 1203--1212. IEEE, March 2000.
[2]M. M. Buddhikot , S. Suri , and M. Waldvogel, "Space Decomposition Techniques for Fast Layer-4 Switching,” Proc. Conf. Protocols for Hight Speed Networks, Aug. 1999, pp. 25-41.
[3]W. Cheswich and S. Bellovin, “Firewalls and Internet Security,” Addison-Wesley, 1995
[4]D. Decasper, Z. Dittia, G. Parulkar, B. Plattner, “Router Plugins: A Software Architecture for Next Generation Routers,” In Sigcomm, 1998.
[5]Mikael Degermark, Andrej Brodnik, Svante Carlsson, and Stephen Pink, “Small forwarding tables for fast routing lookups,” In Proc. ACM SIGCOMM Conference (SIGCOMM '97), pages 3-14, October 1997.
[6]A. Feldmann and S. Muthukrishnan, “Tradeoffs for packet classification,” In Proc. INFOCOM, volume 3, pages 1193- 1202. IEEE, March 2000.
[7]P. Gupta and N. McKeown, Algorithms for Packet Classification, IEEE Network , March/April 2001, vol. 15, no. 2, pp 24-32.
[8]P. Gupta and N. McKeown, "Packet classification on multiple fields," in Proceedings of ACM SIGCOMM'99, ACM, August 1999.
[9]Sundar Iyer, Ramana Rao Kompella and Ajit Shelat “ClassiPI: An Architecture for Fast and Flexible Packet Classification,” IEEE Network , March/April 2001, vol. 15 , no. 2 , p33-41.
[10]T.V. Lakshman and D. Stiliadis, “High Speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching,” Proc. ACM SIGCOMM '98, 1998.
[11]L B. Lampson, V. Srinivasan and G. Varghese, “IP Lookups using Multiway and Multicolumn Search,” In Infocomm, 1998.
[12]Peter Newman, Greg Minshall, and Larry Huston, “IP Switching and gigabit routers,” IEEE Communications Magazine, January 1997.
[13]M. H. Overmars and A.F. van der Stappen. “Range Searching and Point Location Among Fat Objects,” Journal of Algorithms, vol 21, no. 3, Nov. 1996, pp.629-56.
[14]V. Srinivasan, S.Suri, and G.Varghese, "Packet Classification using Tuple Space Search," in Proceedings of ACM SIGCOMM, Sept 1999.
[15]V. Srinivasan, G. Varghese, S. Suri, and M. Waldgovel, “Fast and scalable layer four switching,” In Proceedings of SIGCOMM, October 1998.
[16]V. Srinivasan and G.Varghese, "Fast IP Lookups using Controlled Prefix Expansion", in Proc. ACM Sigmetrics, June 1998.