臺灣博碩士論文加值系統

快速封包分類已經是網際網路支援加值服務的關鍵技術，這些服務的共通性就是必須要能辨識使用者資料流。封包分類可看成在一個規則集合裡面尋找一個最好的匹配規則的過程，但由於網際網路協定階層化，封包分類通常是指對選自封包表頭欄位的處理程序，例如來源及目的位址、來源及目的埠、協定識別號及服務種類。一般而言，封包分類的複雜度與欄位數目、欄位寬度、匹配標準及規則數目有很大相依性。
在本論文中，我們提出Entry-pruning Line Search Algorithm 及 Adaptive Line Search Algorithm 兩種快速封包分類演算法，只要增加少量儲存空間，就可以大幅改善Line Search Algorithm的平均及最差情況搜尋效能。

Fast packet classification has become a key component to enable additional services in Internet applications. What these services have in common is their requirement for recognizing flows. Basically packet classification can be considered as a process looking for the best matching filter in a filter set. Because of the Internet protocol layers, packet classification is often performed for multiple fields selected from packet headers such as source and destination IP addresses, source and destination port numbers, protocol ID, and even type of service. In general, the search time and storage complexity of a packet classification depend heavily on the number of fields, lengths of fields, match criterion and the number of filters.
In this thesis, we propose two fast packet classification algorithms: Entry-pruning Line Search algorithm and Adaptive Line Search algorithm, with increasing a little storage, the average and worst case search performance can be improved obviously.

Chinese Abstract i
English Abstract ii
Acknowledgements iiiii
Contents iiv
List of Table vi
List of Figures vi
Chpater 1 Introduction 1
1.1 Problem Statements 3
1.2 Organization of the Thesis 4
Chapter 2 Related Work 5
2.1 One-dimensional Tuple Space Search Algorithms 5
2.1.1 Linear Search on One-dimensional Tuple Space 6
2.1.2 Binary Search on One-dimensional Tuple Space 7
2.1.3 Improvements 9
2.2 Two-dimensional Tuple Space Search Algorithms 10
2.2.1 Linear Search on Two-dimensional Tuple Space 11
2.2.2 Line Search Algorithm 11
Chapter 3 Proposed Algorithms 15
3.1 Entry Pruning Line Search Algorithm 15
3.1.1 Pruning Criteria 15
3.1.2 Entry-Pruning Line Search Process 17
3.2 Adaptive Line Search Algorithm 18
3.2.1 Adaptive Line Search Process 18
Chapter 4 Simulation Design 21
4.1 Simulation Model 21
4.2 Simulation Rule Set 22
4.3 Test Packet Generation 23
Chapter 5 Simulation Results 27
5.1 Entry-pruning Line Search Algorithm 27
5.1.1 Storage Requirement 27
5.1.2 Search Performance 29
5.2 Adaptive Line Search Algorithm 30
5.2.1 Storage Requirement 30
5.2.2 Search Performance 32
Chapter 6 Summary and Future Work 34
6.1 Summary 34
6.2 Future Work 35
Bibliography 36

[1]. M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable High Speed IP Routing Table Lookups,” in Proceedings of ACM SIGCOMM’97, Sept. 1997, pp. 25-36.
[2]. M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small Forwarding Tables for Fast Routing Lookups,” in Proceedings of ACM SIGCOMM’97, 1997.
[3]. V. Srinivasan and G. Varghese, “Fast IP Lookups Using Controlled Prefix Expansion,” in ACM TOCS, vol. 17, pp. 1-40, Feb. 1999.
[4]. B. Lampson, V. Srinivasan, and G. Varghese, “IP Lookups Using Multiway and Multicolumn Search,” in IEEE/ACM Transactions on Networking, Vol. 7, No. 3, pp. 324-334, June 1999.
[5]. P. Gupta, S. Lin, and N. Mckeown, “Routing Lookups in hardward at Memory Access Speeds,” in Proceedings of INFOCOM’98.
[6]. S. Sikka and G. Varghese, “Memory-Efficient State Lookups with Fast Updates,” in Proceedings of SIGCOMM’00, 2000.
[7]. S. Nilsson and G. Karlsson, “IP-Address Lookup Using LC-Tries,” in IEEE Journal on Selected Areas in Communications, Vol. 17, pp. 1083-1092, June 1999.
[8]. T. Chiueh and P. Pradhan, “High Performance IP Routing Table Lookup Using CPU Caching,” in Proceedings of IEEE INFOCOM, April 1999.
[9]. G. Cheung and S. McCanne, “Optimal Routing Table Design for IP Address Lookups under Memory Constraints,” in Proceedings of IEEE INFOCOM, 1999, pp.1437-1444.
[10]. M. A. Ruiz-Sanchez, E. W. Biersack, and W. Dabbous, “Survey and Taxonomy of IP Address Lookup Algorithms,” in IEEE Network Magazine, March/April 2001, pp. 8-23.
[11]. T.V. Lakshman and D. Stiliadis, “High-Speed Policy-based Packet Forwarding Using Efficient Multi-Dimensional Range Matching,” in Proceedings of ACM SIGCOMM’98, 1998.
[12]. P. Gupta and N. McKeown, “Packet Classification on Multiple Fields,” in Proceedings of ACM SIGCOMM’99, pp. 147-160, 1999.
[13]. A. Hari, S. Suri, and G.. Parulkar, “Detecting and Resolving Packet Filter Conflicts,” in Proceedings of IEEE INFOCOM’00, 2000.
[14]. T-Y.C. Woo, “A Modular Approach to Packet Classification: Algorithms and Results,” in Proceedings of IEEE INFOCOM, 2000, pp. 1213-1222.
[15]. V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “Fast and Scalable Layer Switching,” in Proceedings of ACM SIGCOMM’98, Sept. 1998, pp. 191-202.
[16]. V. Srinivasan, S. Suri, and G. Varghese, “Packet Classification Using Tuple Space Search,” in ACM Computer Communication Review, 1999.
[17]. M. Waldvogel, “Multi-Dimensional Prefix Matching using Line Search,” in Proceedings of IEEE LCN’00, Nov. 2000, pp. 200-207.
[18]. P. Warkhede, S. Suri, and G. Varghese, “Fast Packet Classification for Two-Dimensional Conflict-Free Filters,” in Proceedings of IEEE INFOCOM’01, 2001.
[19]. V. Srinivasan, “A Packet Classification and Filter Management System,” in Proceedings of IEEE INFOCOM’01, 2001.
[20]. F. Baboesuc and G. Varghese, “Scalable Packet Classification,” in Prodeedings of ACM SIGCOMM’01, Aug. 2001, pp. 199-210.
[21]. P. Gupta and N. McKeown, “Algorithms for Packet Classification,” in IEEE Network Magazine, March/April 2001, pp. 24-32.
[22]. P. Gupta, “Algorithms for Routing Lookups and Packet Classification,” Ph.D. Dissertation, University of Stanford, 2000.
[23]. D. Shah and P. Gupa, “Fast Incremental Updates on Ternary-CAMs for Routing Lookups and Packet Classification,” in Proceedings of Hot Interconnects, 2000.
[24]. Merit Networks Inc., “Internet Performance Measurement and Analysis (IPMA) Statistics and Daily Reports,” IMPA Project, http://www.merit.edu/ipma/routing_table/
[25]. http://www.mcvax.org/~jhma/routing/