跳到主要內容

臺灣博碩士論文加值系統

(3.235.185.78) 您好!臺灣時間:2021/07/27 18:13
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:龔景富
研究生(外文):Ching-Fu Kung
論文名稱:使用位元向量編碼的快速封包分類法
論文名稱(外文):Fast Packet Classification Using Bit Vector Encoding
指導教授:王勝德王勝德引用關係
指導教授(外文):Sheng-De Wang
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:46
中文關鍵詞:封包分類位元向量
外文關鍵詞:packet classificationbit vector
相關次數:
  • 被引用被引用:0
  • 點閱點閱:193
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
封包分類在許多的網路應用中都扮演著非常重要的角色,像是防火牆、頻寬保證服務(Quality of Service, QoS),虛擬私人網路(Virtual Private Networks, VPN)等等。
本篇論文將會提出一套針對位元向量(Bit Vector)做編碼的方法,稱為EBV演算法,藉此來降低BV演算法中的位元向量長度,這個做法的好處不僅能降低記憶體的用量,也能節省讀取位元向量時所需的記憶體存取次數。我們使用規則庫產生工具ClassBench來產生九種不同的規則庫。測試的結果可以發現EBV演算法的確能大幅降低Lucent BV演算法的記憶體用量,並且藉由硬體的平行處理,在做規則搜尋時大約只需要原本Lucent BV演算法所需要的記憶體讀取次數的1/2。
使用Xilinx Vertex4 FX-20 FPGA實作EBV演算法,在1K的規則庫,使用64bytes封包大小做為最小封包來計算,在三階管線架構下可以達到500Mbps以上的封包過濾速度;使用五階管線架構,則可達到1Gbps以上的封包過濾速度。
Packet classification plays an important role in many network applications, like firewall, quality of service, virtual private networks, etc.
This paper proposes a method to encode bit vector, called EBV scheme, in order to reduce the length of bit vectors which are basic data structure of Lucent BV scheme. The advantages of compressing bit vectors include lowering the memory space requirement and reducing the memory access times when reading bit vector information from memory. When evaluating the performance, we use the ClassBench, rule set generation tool, to generate nine different rule sets. Testing result shows that the proposed EBV scheme needs a smaller memory storage than the Lucent BV scheme and by using parallel processing in hardware, searching rules with the EBV scheme needs about half of memory access times that are required with the Lucent BV scheme.
We use a Xilinx Vertex4 FX-20 FPGA platform to implement the EBV scheme. With 64-byte packets and rule sets with about 1K rules, the EBV scheme can filter packets up to 500Mbps using a three-stage pipeline architecture and 1Gbps using a five-stage pipeline architecture.
致謝 i
中文摘要 ii
英文摘要 iii
第一章 序論 1
1.1 問題描述 1
1.2 研究目的 2
1.3 論文架構 3
第二章 相關研究 4
第三章 EBV演算法 8
3.1 基礎演算法介紹 9
3.1.1. BV演算法 9
3.1.2. BARTS演算法 11
3.2 EBV演算法介紹 16
3.2.1. 位元向量之編碼 16
3.2.2. WCBV 19
3.2.3. 搜尋 20
第四章 效能評估 22
4.1 CBV演算法簡介 23
4.2 記憶體用量 25
4.2.1. 索引表 25
4.2.2. WCBV 28
4.2.3. 已編碼位元向量 29
4.2.4. 解碼表 30
4.2.5. 演算法記憶體用量比較 31
4.3 封包過濾速度 34
4.3.1. 單一欄位搜尋 35
4.3.2. 位元向量解壓縮及解碼 36
4.3.3. 讀取WCBV 37
4.3.4. 演算法記憶讀取次數比較 37
第五章 硬體實作及結果 40
5.1 實作環境介紹 40
5.2 實驗數據分析 41
第六章 結論 44
參考文獻 45
[1]T. V. Lakshman and D. Stidiais, “High speed policy-based packet fowarding using efficient multidimensional range matching,” in Proc. ACM SIGCOMM, Sep. 1998, pp. 191-202.

[2]F. Baboescu and G. Varghese “Scalable Packet Classification,” IEEE/ACM Trans. Networking, vol. 13, Issue 1, pp. 2–14, Feb. 2005.

[3]T. Srinivasan, N. Dhanasekar, M. Nivedita, R. Dhivyakrishnan, and A. A. Azeezunnisa, “Scalable and Parallel Aggregated Bit Vector Packet Classification using Prefix Computation Model,” in Proc. PARELEC, 2006, pp. 139-144.

[4]J. Li, H. Liu, and K. Sollins, Scalable packet classification using bit vector aggregating and folding, MIT, Dept., Comput. Sci., Apr. 2003, Tech. Rep. MIT-LCS-TM-637.

[5]P. C. Wang, H. Y. Chang, C. T. Chan, and S. C. Hu, “Scalable Packet Classification Using Condensate Bit Vector,” IEICE Trans. Communications, Vol. E88-B, No.4, pp. 1440-1447, 2005.

[6]C. R. Hsu, C. Chen, and C. Y. Lin, “Fast Packet Classification Using Bit Compression,” in Proc. IEEE GLOBECOM Conf., 2005, vol. 2, pp. .

[7]J. van Lunteren, “Searching very large routing tables in fast sram,” in Proc. IEEE ICCCN Conf., Oct. 2001, pp. 4-11.

[8]J. van Lunteren, “Searching very large routing tables in wide embedded memory,” in Proc. IEEE GLOBECOM Conf., Nov. 2001, vol. 3, pp.1615-1619.

[9]J. van Lunteren and T. Engbersen, “Fast and scalable packet classification,” IEEE Journal on Selected Areas in Communications, vol. 21, pp. 560-570, May. 2003.

[10]P. Gupta and N. McKeown, “Packet classification using hierarchical intelligent cuttings,” IEEE Micro, vol. 20, no. 1, pp. 34-41, Feb. 2000.

[11] P. Gupta and N. McKeown, “Packet classification on multiple fields,” in Proc. ACM SIGCOMM, Aug 1999, vol. 9, no. 4, pp. 147-160.
[12]D. E. Taylor and J. S. Turner, “ClassBench: A Packet Classification Benchmark,” in Proc. INFOCOMM, Mar. 2005, vol. 3, pp. 2068-2079.

[13]D. E. Taylor, “Survey and taxonomy of packet classification techniques,” ACM computing Surveys, vol. 37, no. 3, pp. 238-275, Sep. 2005.

[14]S. Singh, F. Baboescu, G. Varghese, and J. Wang, “Packet classification using multidimensional cutting,” in Proc. of ACM SIGCOMM, Aug. 2003, pp. 213-224.

[15]V. Srinivasan, G.. Varghese, S. Suri, and M. Waldvogel, “Fast and scalable layer four switching,” in Proc. of ACM SIGCOMM, Sep. 1998, pp. 191-202.

[16]F. Baboescu, S. Singh, and G. Varghese, “Packet classification for core routers: Is there alternative to CAMs?” in Proc. IEEE INFCOMM, Mar. 2003, pp. 53-63.

[17]Xilinx, ML405 Evaluation Platform User Guide, UG201 v1.2, Mar. 2007.

[18]E. Spitznagel, D. Taylor, and J. Turner, “Packet classification using extended TCAMs,” in Proc. IEEE ICNP, Nov. 2003, pp. 120-131.

[19]T. Woo, “A Modular Approach to Packet Classification: Algorithms and results,” In Proc. IEEE INFOCOM, Tel-Aviv, Israel, pp. 1213-1222, Mar. 2000.

[20]A. Feldman and S. Muthukrishnan, "Tradeoffs for packet classification," in Proc. IEEE INFOCOM, vol. 3, Mar. 2000, pp. 1193-2002.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top