(3.227.235.183) 您好!臺灣時間:2021/04/20 07:54
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:吳寶欽
研究生(外文):Pao-chin Wu
論文名稱:適合在網路處理器上使用之多模式比對演算法
論文名稱(外文):A Fast Multi-pattern Matching Algorithm for Network Processors
指導教授:楊竹星楊竹星引用關係
指導教授(外文):Chu-sing Yang
學位類別:碩士
校院名稱:國立中山大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
畢業學年度:94
語文別:中文
論文頁數:42
中文關鍵詞:模式比對網路處理器
外文關鍵詞:pattern matchingnetwork processor
相關次數:
  • 被引用被引用:1
  • 點閱點閱:149
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
近年來,網路的應用越來越廣,各種網路服務如雨後春筍般出現如,網路拍賣、隨選視訊、網路電話、網路日誌(Blog)等等。因此我們需要好的網路品質以便提供順暢的服務,而目前的網路上有許多的流量是來自於P2P 的應用, 透過這樣的技術可以將頻寬需求分散,因此伺服器不需要有很大的頻寬也能夠提供像檔案傳輸這類需要大量頻寬的服務。但也由於這樣的特點容易將網路的頻寬佔光,導致其它的服務品質下降甚至無法使用。因此我們需要一個服務控制器(Service Controller)來對P2P 服務的流量進行控管,降低其所使用的頻寬。

傳統單純以軟體實作的網路系統無法負荷高速的網路所產生的流量,而開發特殊的ASIC 又需要較長的開發週期且難以重複使用,因此網路處理器(Network Processor)採取中庸之道,使用軟體搭配針對網路處理功能特製化的處理器來建置網路系統以獲得軟體的彈性且能應付高速網路所產生的流量。

在服務控制器要能夠控管P2P 服務的流量,首先必須有一個優質的服務分類器(Service Classifier)來辨識出P2P 服務的流量。服務分類器若使用特徵值比對的方式來實作,則模式比對(Pattern Matching)的演算法對整體的效能就會有很大的影響,本論文提出了一個多模式比對演算法改進了既有的WM 演算法,經過在網路處理器
IXP2400 上實作並比較數種模式比對演算法之後,發現確實獲得較好的效能。
There are more and more Internet services such as video on demand, voice over IP,Blog, and so on. The network quality is important for providing good services. P2P technology can decentralize the usage of bandwidth, so a server can provide services with lower bandwidth. The bandwidth is filled by P2P traffic if we don’t limit the usage of P2P applications, so we need a service controller that can limit the P2P traffic to provide better quality for other applications.

The traditional network systems use software solutions or hardware solutions. The software solutions offer flexibility but have low performance; The hardware solutions offer highest speed but are inflexible and expensive to modify or upgrade. there is another solution known as network processors. A network processor can be programmed and has been optimizede for packet procecssing.

We need a good service classifier to classify P2P traffic, then we can limit it. The performance of a signature based service classifier is dominated by the speed of its pattern
matching algorithm. In this paper, we proposed a fast ulti-pattern matching algorithm by improving WM algorithm. Serveral algorithms are implemented on IXP2400 network
processor for performance evaluation, and our proposed algorithm outperforms other algorithms if its parameters are properly set.
第一章前言
第二章相關研究
2.1 P2P 流量判別
2.2 模式比對
2.2.1 Boyer-Moore
2.2.2 Boyer-Moore-Horspool
2.3 多模式比對
2.3.1 分類
2.3.2 SBMH
2.3.3 WM
2.3.4 FNP
第三章網路處理器開發平台
3.1 IXP2400
3.1.1 簡介
3.1.2 XScale
3.1.3 Microengine
3.1.4 DRAM and SRAM Controller
3.1.5 SHaC Unit
3.1.6 Media and Switch Fabric Interface
3.2 ENP2611
3.2.1 基本規格
3.2.2 PM3386/PM3387 及SPI-3 Bridge
3.3 作業系統
3.3.1 開機流程
3.3.2 IXA SDK Drivers
3.3.3 ENP2611 Drivers
第四章設計與實作
4.1 WMT
4.1.1 使用Trie 來代替HASH
4.1.2 改進SHIFT 計算方式
4.2 Trie Data Structure
4.3 實作
4.3.1 SBMH
4.3.2 WM
4.3.3 FNP
4.3.4 WMT
第五章效能量測與分析
5.1 驗證及效能量測環境
5.1.1 測試模式
5.1.2 資料結構
5.1.3 演算法驗證
5.2 效能量測
5.2.1 實驗一
5.2.2 實驗二
5.2.3 實驗三
5.2.4 實驗四
5.2.5 實驗五
5.2.6 綜合結果
5.3 在Gigabit 乙太網路下的處理情形
第六章結論與未來工作
6.1 結論
6.2 未來工作
[1] Clam antivirus. http://www.clamav.net/.
[2] Intel internet exchange architecture software development kit. http://www.intel.com/design/network/products/npfamily/sdk.htm.
[3] Intel IXP2400 network processor. http://www.intel.com/design/network/products/npfamily/ixp2400.htm.
[4] RadiSys ENP2611. http://www.radisys.com/products/product_detail.cfm?id=1317.
[5] RedBoot: A complete bootstrap environment for embedded systems. http://sourceware.org/redboot/.
[6] Snort. http://www.snort.org/.
[7] Aho, A. V., and Corasick, M. J. Efficient string matching: an aid to bibliographic search. Commun. ACM 18, 6 (1975), 333–340.
[8] Baeza-Yates, R., and Gonnet, G. H. A new approach to text searching.Commun. ACM 35, 10 (1992), 74–82.
[9] Boyer, R. S., and Moore, J. S. A fast string searching algorithm. Commun.ACM 20, 10 (1977), 762–772.
[10] Fisk, M., and Varghese, G. Fast content-based packet handling for intrusion detection. Tech. Rep. CS2001-0670, University of California at San Diego, La Jolla, CA, USA, 2001.
[11] Horspool, R. N. Practical fast searching in strings. Software - Practice and Experience 10 (1980), 501–506.
[12] Kim, S., and Kim, Y. A fast multiple string pattern matching algorithm. In Proceeding of 17th AoM/IAoM Conference on Computer Science (1999).
[13] Liu, R.-T., Huang, N.-F., Chen, C.-H., and Kao, C.-N. A fast stringmatching algorithm for network processor-based intrusion detection system. Trans. on Embedded Computing Sys. 3, 3 (2004), 614–633.
[14] Maly, K. Compressed tries. Commun. ACM 19, 7 (1976), 409–415.
[15] Sen, S., Spatscheck, O., and Wang, D. Accurate, scalable in-network identification of P2P traffic using application signatures. In WWW ’04: Proceedings of
the 13th international conference on World Wide Web (New York, NY, USA, 2004), ACM Press, pp. 512–521.
[16] Wu, S., and Manber, U. A fast algorithm for multi-pattern searching. Tech. Rep. TR-94-17, University of Arizona, 1994.
[17] 陳建華. 基於Linux Netfilter 的通訊協定分類器之設計與實作. 國立中山大學資訊工程學系碩士論文.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 王夢鷗:〈唐人小說概述〉《中國古典小說研究專集3》,靜宜大學中國古典小說研究中心主編(台北:聯經,1981年),頁37-47。
2. 王夢鷗:〈枕中記及其作者〉,《幼獅學誌》,第5卷2期,1966年12月,台北,頁。
3. 王夢鷗:〈枕中記及其作者〉,《幼獅學誌》,第5卷2期,1966年12月,台北,頁。
4. 王拓:〈枕中記與杜子春──唐代神異小說所表現的兩種人生態度〉,《幼獅月刊》,卷40卷第2期,1974年8月。頁15-20。
5. 王拓:〈枕中記與杜子春──唐代神異小說所表現的兩種人生態度〉,《幼獅月刊》,卷40卷第2期,1974年8月。頁15-20。
6. 王小琳:〈論唐代傳奇創作活動的特徵及其對傳奇敘事的影響〉,《中山人文學報》第九期,1999年8月,頁79-95。
7. 王小琳:〈論唐代傳奇創作活動的特徵及其對傳奇敘事的影響〉,《中山人文學報》第九期,1999年8月,頁79-95。
8. 19.楊青青,能力雜誌,統一企業以e化因應全球化佈局,2001年12月。
9. 19.楊青青,能力雜誌,統一企業以e化因應全球化佈局,2001年12月。
10. 7.蔡宏明(民90),傳統產業的現況與面臨的挑戰,實用稅務,2001年,316期,頁12-17。
11. 7.蔡宏明(民90),傳統產業的現況與面臨的挑戰,實用稅務,2001年,316期,頁12-17。
12. 4.潘維忠,我國網路金流發展之現況與願景, 財金資訊 卷期╱年月 31 ,2003年12月,頁42-47。
13. 4.潘維忠,我國網路金流發展之現況與願景, 財金資訊 卷期╱年月 31 ,2003年12月,頁42-47。
14. 王夢鷗:〈唐人小說概述〉《中國古典小說研究專集3》,靜宜大學中國古典小說研究中心主編(台北:聯經,1981年),頁37-47。
15. 吳碧貞:〈唐代文人的小說觀──以唐代小說序言為考察範圍〉,《中文研究學報》1期,1997年6月,頁45。
 
系統版面圖檔 系統版面圖檔