臺灣博碩士論文加值系統

本論文探討多種基於速寫演算法的流量計數方式，以實際的核心網路流量來模擬測試並比較其效能。將兩種演算法CM-Sketch(Count Min Sketch)與MPC(Multiple Probabilistic Counting)，以硬體描述語言(Verilog HDL)實現在NetFPGA-10G開發平台，並且完成具有網路資料分流(Network Traffic Tap)功能之高速網路流量量測系統。此系統，在觀測時間之內，可以量測流經觀測點所有不同種類封包流的個數(Distinct Flow Count)，以及每一個流量中的封包出現次數。

Network traffic flow measurement and analysis are the essential part of the network intrusion detection system design. In this dissertation, we study selected sketch-based algorithms which are capable of estimating the cardinality and multiplicities of traffic flow in high-speed core networks. We explore these algorithms with real-world network traffic traces and implement two of them in NetFGPA 10G platform. The traffic measurement prototype is capable of acting as a network tap to identify the number of distinct IP flows and the number of times a packet belongs to a particular IP flow. We also provide register interfaces for the host to retrieve these measurement results for high level application design.

中文摘要 I
Abstract II
誌謝 III
目錄 IV
圖目錄 VII
算法列表 X
1 緒論 1
1.1 背景 1
1.2 動機與目的 3
1.3 論文架構 4
2 相關研究與探討 5
2.1 速寫(Sketch)演算法 5
2.1.1 統計總數演算法 6
2.1.2 統計個數演算法 11
2.1.3 速寫演算法比較 17
2.2 異常來源查詢 20
3 NetFPGA-10G 25
3.1 簡介 25
3.2 硬體架構 26
3.3 硬體開發 28
3.4 NetFPGA-10G自我測試 30
4 系統架構與實現方式 32
4.1 系統架構 32
4.2 速寫演算法模組實現 34
4.2.1 速寫演算法模組 34
4.2.2 速寫演算法觀測模組 36
4.2.3 查詢模組 37
4.3 控制模組實現 38
4.4 MPC模組實現 39
4.5 暫存器(Register)架構 40
4.6 系統驗證與模擬 41
5 實驗與討論 48
5.1 基本功能測試 49
5.2 流量測試 53
6 結論與未來展望 57
6.1 結論 57
6.2 未來展望 58
參考文獻 59
圖目錄
1.1 網路頻寬成長[1] 2

2.1 LC演算法累計方式 6
2.2 LC演算法統計方式 7
2.3 FM-Sketch累計方式 8
2.4 FM-Sketch累計結果 9
2.5 CM-Sketch[2] 12
2.6 PCSA需陣列對應[3] 14
2.7 儲存空間4M位元計算結果 19
2.8 儲存空間8M位元計算結果 19
2.9 CGT累計[4] 21
2.10 Fast Sketch累計[5] 23

3.1 NetFPGA-10G硬體架構[6] 26
3.2 各模組連接示意圖[6] 29
3.3 NetFPGA-10G測試[7] 30
3.4 NetFPGA-10G測試結果 31

4.1 系統架構圖 33
4.2 速寫演算法模組流程 35
4.3 速寫演算法觀測模組 37
4.4 查詢模組 38
4.5 控制模組實現 39
4.6 MPC模組實現 40
4.7 暫存器架構 41
4.8 封包輸入 42
4.9 計數結果1 43
4.10 計數結果2 43
4.11 寫入速寫表差值 44
4.12 寫入門檻值 44
4.13 讀出來源端位址 45
4.14 總數計算結果 46

5.1 量測架構 49
5.2 讀出量測的數值 50
5.3 寫入速寫表差值與門檻值 51
5.4 超過門檻值的來源端位址 52
5.5 無超過門檻值的來源端位址 53
5.6 讀出CM-Sketch陣列中量測的數值(Tcpreplay) 54
5.7 寫入速寫表差值與門檻值(Tcpreplay) 55
5.8 過濾出的來源端位址(Tcpreplay) 56
算法列表
2.1 PCSA演算法[8] 9
2.2 MPC演算法[9] 11
2.3 PMCCOUNT(f)[3] 13
2.4 GETZSUM(f)[3] 14
2.5 GSTKSUM(f)[3] 15
2.6 PMCESTIMATE(f)[3] 15
2.7 CGT查詢[4] 21
2.8 Fast Sketch查詢[5] 23
2.9 不同區間查詢異常來源 24

[1] Higher speed ethernet study Group(HSSG). http://www.ieee802.org/802_tutorials/07-November/HSSG_Tutorial_1107.zip.
[2] G. Cormode and S. Muthukrishnan. An improved data stream summary: the
count-min sketch and its applications. Journal of Algorithms, 55(1):58-75, 2005.
[3] P. Lieven and B. Scheuermann. High-speed per- ow tra c measurement with proba-bilistic multiplicity counting. In INFOCOM, 2010 Proceedings IEEE, page 1-9, 2010.
[4] G. Cormode and S. Muthukrishnan. What's hot and what's not: tracking
most frequent items dynamically. In Proceedings of the twenty-second ACM
SIGMOD-SIGACT-SIGART symposium on Principles of database systems, page 296-306, 2003.
[5] Y. Liu, W. Chen, and Y. Guan. A fast sketch for aggregate queries over high-speed network traffc. In INFOCOM, 2012 Proceedings IEEE, page 2741-2745, 2012.
[6] M. Blott, J. Ellithorpe, N. McKeown, K. Vissers, and H. Zeng. FPGA research design platform fuels network advances.
[7] netfpga10g / production test manual. http://netfpga10g.pbworks.com/w/page/45026818/Production%20Test%20Manual.
[8] M. Hadjieleftheriou, J. W Byers, and G. Kollios. Robust sketching and aggregation of distributed data streams. Technical report, Citeseer, 2005.
[9] S. Ganguly, M. Garofalakis, and R. Rastogi. Processing set expressions over con-tinuous update streams. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data, page 265-276, 2003.
[10] D. Barman, P. Satapathy, and G. Ciardo. Detecting attacks in routers using sketches.In High Performance Switching and Routing, 2007. HPSR'07. Workshop on, page 1-6,2007.
[11] B. Krishnamurthy, S. Sen, Y. Zhang, and Y. Chen. Sketch-based change detection:methods, evaluation, and applications. In Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement, page 234-247, 2003.
[12] K. Y Whang, B. T Vander-Zanden, and H. M Taylor. A linear-time probabilistic counting algorithm for database applications. ACM Transactions on Database Sys-tems, 15(2):208-229, 1990.
[13] P. Flajolet and G. Nigel Martin. Probabilistic counting algorithms for data base applications. Journal of Computer and System Sciences, 31(2):182-209, 1985.
[14] S. H Shin and M. Yoon. Virtual vectors and network tra c analysis. Network, IEEE,26(1):22-26, 2012.
[15] A. Metwally, D. Agrawal, and A. E Abbadi. Why go logarithmic if we can go linear?:Towards effective distinct counting of search traffic. In Proceedings of the 11th interna-tional conference on Extending database technology: Advances in database technology,page 618-629, 2008.
[16] S. Ganguly, M. Garofalakis, R. Rastogi, and K. Sabnani. Streaming algorithms for robust, real-time detection of ddos attacks. In Distributed Computing Systems, 2007.ICDCS'07. 27th International Conference on, page 4-4, 2007.
[17] The spread of the witty worm. http://www.caida.org/research/security/witty/.
[18] Passive monitor: equinix-sanjose. http://www.caida.org/data/monitors/passive-equinix-sanjose.xml.
[19] SFP+. http://www.cisco.com/en/US/prod/collateral/switches/ps9441/ps9402/ps9512/AAG_SFP+.pdf.
[20] OpenCPI - open component portability infrastructure. http://opencpi.org/.
[21] XAUI. http://www.xilinx.com/products/intellectual-property/XAUI.htm.
[22] 10 gigabit ethernet media access controller (10GEMAC).
http://www.xilinx.com/products/intellectual-property/DO-DI-10GEMAC.htm.
[23] xapp852(2.3v). http://www.xilinx.com/support/documentation/application_notes/xapp852.pdf.
[24] Memory interface generator (MIG). http://www.xilinx.com/products/intellectual-property/MIG.htm.
[25] Tri-mode ethernet MAC. http://www.xilinx.com/support/documentation/ip_documentation/hard_temac.pdf.
[26] AXI reference guide UG761 (v13.1). http://www.xilinx.com/support/documentation/ip_documentation/ug761_axi_reference_guide.pdf,March 2011.
[27] NetFPGA-10G reference NIC. http://netfpga10g.pbworks.com/w/page/32283870/NetFPGA-10G+Reference+NIC.
[28] Easics crctool. http://www.easics.be/webtools/crctool.
[29] How do i create a custom AXI IP core? http://www.xilinx.com/support/answers/37425.htm.
[30] 10g-pcie2-8b2-2s. https://www.myricom.com/products/network-adapters/10g-pcie2-8b2-2s.html.