請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/28972
標題: | 使用位元向量編碼的快速封包分類法 Fast Packet Classification Using Bit Vector Encoding |
作者: | Ching-Fu Kung 龔景富 |
指導教授: | 王勝德(Sheng-De Wang) |
關鍵字: | 封包分類,位元向量, packet classification,bit vector, |
出版年 : | 2007 |
學位: | 碩士 |
摘要: | 封包分類在許多的網路應用中都扮演著非常重要的角色,像是防火牆、頻寬保證服務(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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/28972 |
全文授權: | 有償授權 |
顯示於系所單位: | 電機工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-96-1.pdf 目前未授權公開取用 | 585.45 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。