臺灣博碩士論文加值系統

本論文主要是提出一種能夠在分散式高速網路流量下偵測巨大流量的架構，所提出的架構主要分在可程式化Tofino2交換器中透過dSketch演算法實現區域監測系統，以及透過控制器收集每台交換器經壓縮感知後的流量資訊，並且使用偏差正交匹配追蹤演算法還原壓縮過的流量資訊從而得到全域的網路流量資訊偵測分散式巨大流量，本論文所提出的架構能夠有效偵測分散式巨大流量，還有能夠減少交換器上傳網路流量資訊給控制器的通信資料量。

In this paper, we propose a system that can detect heavy hitter under distributed high-speed network traffic. The system architecture is to implement a regional monitoring system on programmable Tofino2 switches through the dSketch algorithm. Additionally, the controller is used to collect flow information from each switch after compression sensing, and to restore the compressed traffic information by using the biased orthogonal matching pursuit algorithm to obtain the global network traffic information for detecting distributed heavy hitter. It also reduces communication overhead when the switch uploads network traffic information to the controller.

目錄
摘要 I
Abstract II
致謝 III
目錄 IV
圖目錄 VII
表目錄 IX
第一章 緒論 1
1.1 研究動機 . .............................. 1
1.2 研究目的 . .............................. 2
1.3 論文架構 . .............................. 2
第二章 研究背景 3
2.1 可程式化資料平面 . ......................... 3
2.1.1 PSA.............................. 5
2.1.2 V1Model........................... 5
2.1.3 TNA/T2NA.......................... 6
2.2 速寫演算法 . ............................. 7
第三章 相關研究 8
3.1 dSketch................................ 8
3.2 壓縮感知 . .............................. 10
3.3 偏差正交匹配追蹤演算法 . ..................... 11
3.3.1 正交匹配追蹤演算法 . ................... 11
3.3.2 偏差正交匹配追蹤演算法 . ................ 13
第四章 系統設計與實現 15
4.1 在可程式化交換器實現區域監測巨大流量 . ........... 15
4.1.1 入口解析器 . ........................ 15
4.1.2 主要模組 . .......................... 16
4.1.3 入口封裝器 . ........................ 20
4.2 分散式巨大流量偵測 . ....................... 21
4.2.1 BarefootRuntime....................... 21
4.2.2 分散式巨大流量測量 . ................... 22
第五章 系統驗證與效能評估 25
5.1 軟體模擬測試 . ........................... 25
5.1.1 偏差正交匹配追蹤演算法對於巨大流量的測試 . .... 25
5.1.2 軟體模擬模分散式巨大流量偵測 . ............ 28
5.1.3 測試流量 . .......................... 29
5.1.4 功能驗證 . .......................... 31
5.2 實機實測 . .............................. 32
5.2.1 測試環境 . .......................... 33
5.2.2 功能驗證 . .......................... 35
5.3 資源使用量 . ............................. 36
第六章 綜合討論與結論 40
6.1 綜合討論 . .............................. 40
參考資料 42
附錄 A 45

圖目錄
圖 2.1 軟體定義網路架構 [4] ...................... 4
圖 2.2 PISA 架構 [4] ........................... 4
圖 2.3 PSA 架構 [4] ........................... 5
圖 2.4 V1Model 架構 [4] ......................... 6
圖 2.5 TNA/T2NA 架構 [4] ....................... 6
圖 2.6 速寫演算法 . ........................... 7
圖 3.1 壓縮感知演算法示意圖 . .................... 10
圖 4.1 解析鏡像標頭 . .......................... 16
圖 4.2 以來源 IP 地址為鍵計算雜湊值 . ................ 17
圖 4.3 以入口端口作為鍵，對 Sketch 結構的暫存器執行不同的更
新動作的表格 . ........................... 17
圖 4.4 sketch_count 動作為統計封包個數，sketch_decay 動作為更
新封包個數 . ............................. 18
圖 4.5 以入口端口作為鍵，對儲存時戳的暫存器執行不同的更新
動作的表格 . ............................. 18
圖 4.6 window_update 動作為儲存目前封包的時戳並回傳時戳差為
0，window_diff 動作為回傳時戳差 . ................ 19
圖 4.7 以時戳差作為鍵，zero0 動作為記錄目前流量的封包個數，
shift0 動作為把目前流量的封包個數右移一位，並且都設定鏡像 19
圖 4.8 偵測區域巨大流量表格 . .................... 20
圖 4.9 入口封裝器為把目前流量對應的封包個數封裝到鏡像標頭 . 21
圖 4.10 簡易的 Barefoot Runtime 架構 [2] ............... 22
圖 4.11 分散式巨大流量偵測架構 . ................... 23
圖 4.12 本系統架構 . .......................... 23
圖 4.13 儲存來源 IPv4 地址的暫存器 . ................. 24
圖 5.1 模擬 2 個區域監測端的交換器和 1 台的控制器其拓樸示意圖 29
圖 5.2 202105291400.pcap 前 10 個封包數最多的來源 IP 地址其每
10 秒封包數 . ............................ 30
圖 5.3 圖上為 202105291400_0 不同來源 IP 地址的每 10 秒封包數,
圖下為 202105291400_1 不同來源 IP 地址的每 10 秒封包數，
共 900 秒時間 . ........................... 32
圖 5.4 軟體模擬分散式巨大流量偵測，圖上和圖下分別為區域監
測端交換器 0、1 把在流量中的巨大流量過濾後的流量每 10
秒封包數。 . ............................. 32
圖 5.5 實機測試環境 . .......................... 34
圖 5.6 實機測試拓樸示意圖 . ...................... 35
圖 5.7 「port 0」和「port 1」為從流量播放器在端口 0 和端口 1 所
測量到的每秒封包個數 . ...................... 36
圖 5.8 switch_tofino2_yo.p4 的資源使用量 . .............. 38
圖 5.9 區域監測巨大流量系統 +switch_tofino2_y0.p4 的資源使用量 39

表目錄
表 5.1 N=65,536 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原的前 10 個最大值之平均相對誤差 . ......... 27
表 5.2 N=65,536 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之召回率 . .............. 27
表 5.3 N=65,536 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之準確率 . .............. 27
表 5.4 N=65,536 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之 F1-score .............. 28
表 5.5 202105291400.pcap 前 10 個封包數最多的來源 IP 地址 . ... 30
表 5.6 202105291400_0 不同來源 IP 地址對應的封包數 . ...... 30
表 5.7 202105291400_1 不同來源 IP 地址對應的封包數 . ...... 31
表 5.8 實機測試所使用的流量 202105291400 ............. 33
表 5.9 資源使用量的比較 . ....................... 37
表 A.1 N=32,768 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原的前 10 個最大值之平均相對誤差 . ......... 45
表 A.2 N=16,384 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原的前 10 個最大值之平均相對誤差 . ......... 45
表 A.3 N=8,192 時，在不同的壓縮比和 Zipf 參數下，壓縮前和壓
縮後還原的前 10 個最大值之平均相對誤差 . ........... 46
表 A.4 N=4,096 時，在不同的壓縮比和 Zipf 參數下，壓縮前和壓
縮後還原的前 10 個最大值之平均相對誤差 . ........... 46
表 A.5 N=32,768 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之召回率 . .............. 46
表 A.6 N=16,384 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之召回率 . .............. 47
表 A.7 N=8,192 時，在不同的壓縮比和 Zipf 參數下，壓縮前和壓
縮後還原其偵測巨大流量之召回率 . ............... 47
表 A.9 N=4,096 時，在不同的壓縮比和 Zipf 參數下，壓縮前和壓
縮後還原其偵測巨大流量之召回率 . ............... 47
表 A.10 N=32,768 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之準確率 . .............. 48
表 A.11N=16,384 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之準確率 . .............. 48
表 A.12 N=8,192 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之準確率 . .............. 48
表 A.13 N=4,096 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之準確率 . .............. 49
表 A.14 N=32,768 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之 F1-score .............. 49
表 A.15 N=16,384 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之 F1-score .............. 49
表 A.16 N=8,192 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之 F1-score .............. 50
表 A.17 N=4,096 時，在不同的壓縮比和 Zipf 參數下，壓縮前和
壓縮後還原其偵測巨大流量之 F1-score .............. 50

[1] Aaron Turner, Tcpreplay - Pcap editing and replaying utilities, ULR: https://
tcpreplay.appneta.com/(visited on 07/10/2023 ).
[2] Andy Fingerhut, Vladimir Gurevich, P416 Programming for Intel® Tofino™
using Intel P4 Studio™, May 21, 2021, URL:https://opennetworking.org/wpcontent/
uploads/ 2021/05/2021-P4-WS-Vladimir-Gurevich-Slides.pdf(visited
on 07/10/2023 ).
[3] K. Cho, MAWI Working Group Traffic Archive, [online] Available: https://
mawi.wide.ad.jp/mawi/ (visited on 07/19/2023 ).
[4] Larry Peterson, Carmelo Cascone, Brian O＇Connor, Thomas Vachuska, and
Bruce Davie, Software-Defined Networks: A Systems Approach —Software-
Defined Networks: A Systems Approach Version 2.1-dev documentation.
URL: https://sdn.systemsapproach.org, License: CC BY-NC-ND 4.0 (visited
on 07/06/2023 ).
[5] MassDAL Code Bank – Sketches, [online] Available: http://
www.dimacs.rutgers.edu/~graham/code/ (visited on 08/04/2023 ).
[6] The P4.org Architexture Working Group, P4~16~ Portable Switch Architecture
(PSA), ULR: https:// p4.org/ p4-spec/ docs/PSA.html (visited on
07/10/2023 ).
[7] Barefoot Networks,PUBLIC_tofino-Native-Arch.pdf,URL: https://
github.com/ barefootnetworks/Open-Tofino/ blob/ master/PUBLIC_tofino-
Native-Arch.pdf (visited on 07/08/2023 ), July 2023. original-date:
2020-10-14T22:45:36Z.
[8] Lada Adamic and Bernardo Huberman. Zipf’s Law and the Internet. Glottometrics,
3, November 2001.
[9] Pat Bosshart, Dan Daly, Glen Gibb, Martin Izzard, Nick McKeown, Jennifer
Rexford, Cole Schlesinger, Dan Talayco, Amin Vahdat, George Varghese, and
David Walker. P4: programming protocol-independent packet processors.
ACM SIGCOMM Computer Communication Review, 44(3):87–95, July 2014.
[10] D.L. Donoho. Compressed sensing. IEEE Transactions on Information Theory,
52(4):1289–1306, 2006.
[11] Xin Zhe Khooi. Khooi, Xin Zhe and Csikor, Levente and Li, Jialin and Kang,
Min Suk and Divakaran, Dinil Mon, dSketch, [online] Available: https://
bit.ly/3sTFWS9. (visited on 09/08/2023 ), August 2023.
[12] Xin Zhe Khooi, Levente Csikor, Jialin Li, Min Suk Kang, and Dinil Mon Divakaran.
Revisiting Heavy-Hitter Detection on Commodity Programmable
Switches. In 2021 IEEE 7th International Conference on Network Softwarization
(NetSoft), pages 79–87, 2021.
[13] S. Muthukrishnan. Data Streams: Algorithms and Applications. Foundations
and Trends® in Theoretical Computer Science, 1(2):117–236, 2005.
[14] Robin Sommer and Anja Feldmann. NetFlow: information loss or win? In
Proceedings of the second ACM SIGCOMM Workshop on Internet measurment
- IMW ’02, page 173, Marseille, France, 2002. ACM Press.
[15] Joel A. Tropp and Anna C. Gilbert. Signal Recovery From Random Measurements
Via Orthogonal Matching Pursuit. IEEE Transactions on Information
Theory, 53(12):4655–4666, 2007.
[16] Ying Yan, Jiaxing Zhang, Bojun Huang, Xuzhan Sun, Jiaqi Mu, Zheng Zhang,
and Thomas Moscibroda. Distributed Outlier Detection Using Compressive
Sensing. In Proceedings of the 2015 ACM SIGMOD International Conference
on Management of Data, SIGMOD ’15, pages 3–16, New York, NY, USA,
2015. Association for Computing Machinery. event-place: Melbourne, Victoria,
Australia.