跳到主要內容

臺灣博碩士論文加值系統

(3.233.217.106) 您好!臺灣時間:2022/08/17 12:31
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:施松伯
研究生(外文):Song-Bor Shih
論文名稱:一個兩階段的封包分類法
論文名稱(外文):A Two-Stage Packet Classification
指導教授:陳文村陳文村引用關係
指導教授(外文):Wen-Tsuen Chen
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:33
中文關鍵詞:封包分類字首範圍
外文關鍵詞:packet classificationprefixrange
相關次數:
  • 被引用被引用:0
  • 點閱點閱:139
  • 評分評分:
  • 下載下載:17
  • 收藏至我的研究室書目清單書目收藏:0
隨著網際網路的蓬勃發展,即時性 (real time) 和多媒體方面的應用需要服務品質 (Quality of Service) 保證。為了提供服務品質保證,下一世代路由器裡的封包分辨器 (packet classifier) 是一項必須的元件。根據預先定義的規則 (pre-defined rule) ,此分辨器負責將進入的封包分辨成不同的資料流 (flow) 或是服務等級(service-classes) 。一個類別規則包含有多個欄位,包括來源與目的地位、來源與目的地阜 (port) 、協定類型 (protocol type) 等等。一般來說,位址欄位是由字首定義 (prefix-defined) 而阜欄位是由範圍定義 (range-defined) 。為了簡化這個複雜的封包分辨問題,很多出版的論文沒有處理範圍並且假設所有的欄位都是由字首定義。範圍與字首之間的轉換是可能的,不過這麼做卻會導致記憶體爆炸與大量的儲存空間的浪費。
在本篇文章,我們發展一個有效的兩階段的封包分類演算法。在第一階段,先使用字首欄位來分辨封包。在這個階段,對於每一個規則,利用這些字首定義的欄位來遞迴地建立搜尋路徑。接下來在第二階段才由範圍欄位來分辨封包。在這個階段,先將規則所規定的範圍,投影到座標軸上產生互不重疊的基本區間 (elementary intervals) ,再依這些基本區間產生搜尋路徑。自從這些範圍沒有被轉換成字首,我們的演算法能明顯的節省儲存空間。實驗的結果指出與傳統的階層式tries來比,我們能夠降低高達95%的儲存空間。並且對於大量的規則來說,我們的方法明顯地展現了比傳統的方法較快的查詢時間。

Emerging real-time and multimedia applications require quality of service (QoS) guarantees. The packet classifier in next-generation routers is an essential component in QoS provisioning. It is responsible for classifying incoming packets into distinct flows or differential service-classes according to pre-defined rules. A classification rule contains multiple fields, including source and destination addresses, source and destination ports, and protocol type, etc. Generally speaking, address fields are prefix-defined and port fields are range-defined. In order to simplify the complex packet classification (PC) problem, many published papers [8-11] do not deal with ranges and assume all fields are prefixes. The transformation between range and prefix is possible. However, this will result in the memory explosion.
In this article, we develop an efficient two-stage packet classification algorithm. The first stage classifies packets by using prefix fields and the second one distinguishes them by using range fields. Our algorithm can save memory significantly since the range is not converted into prefixes. Experimental results indicate that we reduce 95% of the storage space in comparison with the conventional Hierarchical Tries (H-Tries). Furthermore, our solution demonstrates significant faster lookup time than the conventional one for numerous rules.

CHAPTER 1 INTRODUCTION……………………………………1
CHAPTER 2 BACKGROUND AND RELATED WORKS….…....6
2.1 Background………………………………………………………….6
2.2 Previous Works……………………………………………………...7
2.2.1 Metrics of Performance Evaluation……………………………...7
2.2.2 Assumptions of Published Papers………………………………..8
2.2.3 Taxonomy of Previous Works……………………………………9
2.2.3.1 Tries-based methods………………………………………...9
2.2.3.2 Tuple Space Search and extension…………………………12
2.2.3.3 Arbitrary range-enabled methods………………………….13
CHAPTER 3 PROBLEM DEFINITION…………….....…….……15
CHAPTER 4 TWO-STAGE CLASSIFICATION…………………17
CHAPTER 5 EXPERIMENTAL RESULTS……………..………...23
CHAPTER 6 CONCLUSIONS……………………………………..28
REFERENCES……………………………………………………...…30

[1] D. Decasper et al., “Router Plugins: A Software Architecture for Next-Generation Routers,” IEEE/ACM Transactions on Networking, vol. 8, no. 1, Feb. 2000.
[2] R. Bhagwan and Bill Lin, “Fast and Scalable Priority Queue Architecture for High-Speed Network Switches,” Proc. INFOCOM’2000, vol. 2, Mar. 2000, pp. 538 —47.
[3] A. Feldman and S. Muthukrishnan, “Tradeoffs for Packet Classification,” Proc. INFOCOM’2000, vol. 3, Israel, Mar. 2000, pp. 1193-1202.
[4] N. F. Huang et al., “A Fast IP Routing Lookup Scheme for Gigabit Switching Routers,” Proc. INFOCOM’99, vol. (March). 1999.
[5] M. A. Ruiz-Sanchex et al., “Survey and Taxonomy of IP Address Lookup Algorithms,” IEEE Network, vol. 15, issue 2, Mar.-Apr. 2001, pp. 8-23.
[6] S. Iyer et al., “ClassiPI: An Architecture for Fast and Flexible Packet Classification,” IEEE Network, vol. 15, issue 2, Mar.-Apr. 2001, pp. 34-41.
[7] T. V. Lakshman and D. Stiliadis, “High Speed Policy Based Packet Forwarding Using Efficient Multi-dimensional Range Matching,” Proc. ACM SIGCOMM’98, Vancouver, Canada, Sept. 1998.
[8] V. Srinivasan, “A Packet Classification and Filter Management System,” Proc. INFOCOM’2001, vol. 3, Mar. 2001. pp. 1464-73.
[9] T. Woo, “A Modular Approach to Packet Classification: Algorithms and Results,” Proc. INFOCOM’2000, Israel, Mar. 2000.
[10] V. Srinivasan et al., “Packet Classification Using Tuple Space Search,” Proc. ACM SIGCOMM’99, Sept. 1999.
[11] V. Srinivasan, S. Suri, G. Varghese, and M. Waldvogel, “Fast and Scalable Layer 4 Switching,” Proc. ACM SIGCOMM’98, Sept. 1998, pp. 203-14.
[12] P. Gupta and N. McKeown, “Classifying Packets Using Hierarchical Intelligent Cuttings,” IEEE Micro, vol. 20, no. 1, Jan.-Feb. 2000, pp. 34-41.
[13] Prefix database MaeEast, The Internet Performance Measurement and Analysis (IPMA) project, data available at http://www.merit.edu/ipma/routing_table/, Aug. 1999.
[14] H. Adiseshu. G. Parulkar, and R. Yavatkar, “SSP: A state management protocol for IntServ, DiffServ, and label switching,” Proc. ICNP’98, 1998.
[15] S. Blake et al., “An Architecture for Differentiated Services,” RFC 2475, Dec. 1998.
[16] S. Shenker, P. Partridge, and R. Guerin, “Specification of Guaranteed Quality of Service,” RFC 2212, Sep. 1997.
[17] B. Braden, L. Zhang, S. Berson, S. Herxog, and S. Jamin, “Resource ReSerVation Protocol,” RFC 2205, 1997.
[18] D. Awduche et al., “Requirements for Traffic Engineering Over MPLS,” RFC 2702, Sep. 1999.
[19] I. Andrikopoulos and G. Pavlou, “Supporting Differentiated Services in MPLS Networks,” Proc. IWQoS’99, pp. 207-15.
[20] R. Rabbat et al., “Traffic Engineering Algorithms Using MPLS for Service Differentiation,” Proc. ICC’2000, vol. 2, 2000, pp. 791 —5.
[21] B. N. Levine et al., “Consideration of Receiver Interest for IP Multicast Delivery,” Proc. INFOCOM’2000, vol. 2, Mar. 2000, pp. 470-9.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top