臺灣博碩士論文加值系統

在現今的網路環境中，辨識"Heavy Hitter"的流量是很重要的，對於很多網路功能或管理都需要偵測Heavy Hitter功能。當總流量過大時，對服務伺服器有著很大的負擔，然而網路資料通常都是很大量的，無法將之全部都記錄下來，所以如何在有限的空間能辨識"Heavy Hitter"的流量便成了一項挑戰，不論在傳統網路或是SDN中，都是值得研究的議題。

在本篇論文中，主要為兩個重點，第一，我們從各個方面分析了HashPipe algorithm，如要運用幾張table、各張table該如何分配比例會有最佳的準確度及最少的碰撞次數、以及說明碰撞次數與時間長短的關係等。第二，我們結合了HashPipe algorithm與Count_Min Sketch的方法，探討整體演算法的效率及準確度，以及探討單一台設備與分散式的網路架構下該如何辨識"Heavy Hitter"的流量，並以數學證明我們的論點。

在實驗結果部分，主要應用在SDN的網路環境，並將演算法實作在Heavy Hitter Agent中，我們將會實驗error rate、總collision次數以及其他不同的角度，且利用SDN的彈性與技術，能不影響整體網路的運作下偵測"Heavy Hitter"。

In today's network environment, it is important to recognize the traffic of "Heavy Hitter". For many network functions or management, it is necessary to detect the Heavy Hitter. Network data is usually very large, and it is impossible to record all of them. How to identify the "Heavy Hitter" traffic in a limited space becomes a challenge, whether in traditional networks or SDN. It is a topic worth studying.

In this paper, there are two main points. First, we analyze the HashPipe algorithm from various aspects. For example, how to use several tables and how to allocate the table will have the best accuracy and the minimum number of collisions. And we explain the relationship between the number of collisions and the length of time. Second, we propose a method for HashPipe algorithm and Count_Min Sketch to improve the efficiency and accuracy of the overall algorithm, and to explore how to identify the "Heavy Hitter" traffic under a single device and a distributed network architecture. We prove our arguments with rigorous analysis.

In the experimental results section, mainly with the SDN network environment, the algorithm is implemented in the Heavy Hitter Agent. By utilizing the flexibility and technology of SDN, our method can detect "Heavy Hitter" without affecting the operation of the overall network.

1 Introduction 1
2 Background 4
2.1 Definition 4
2.2 Heavy Hitter Solutions 5
2.2.1 Sketch-base Solutions 5
2.2.2 Counter-base Solutions 6
2.2.3 Sampling Solutions 10
3 Analysis and Implementation 12
3.1 Analysis 14
3.2 Multiple HashPipes 24
3.3 Distributed Situation 26
4 Experiments and Evaluation 29
4.1 Dataset Collection 30
4.2 SDN overview 30
4.3 Single Agent Environment and Experiment 33
4.4 Distributed Environment and Experiment 44
5 Related work 46
6 Conclusion 49

[1] “Github DDoS attack.” https://githubengineering.com/ddos-incident-report/.
[2] “Netflow.” http://www.cisco.com/c/en/us/tech/quality-of-service-qos/netflow/index.html.
[3] “Software-Defined Networking (SDN) Definition.” https://www.opennetworking.org/
sdn-resources/sdn-definition. [Online].
[4] D. Kreutz, F. M. Ramos, P. E. Verissimo, C. E. Rothenberg, S. Azodolmolky, and
S. Uhlig, “Software-defined networking: A comprehensive survey,” Proceedings of the
IEEE, vol. 103, no. 1, pp. 14–76, 2015.
[5] L. Jose, M. Yu, and J. Rexford, “Online measurement of large traffic aggregates on
commodity switches.,” in Hot-ICE, 2011.
[6] M. A. da Cruz, L. C. e Silva, S. Correa, and K. V. Cardoso, “Accurate online detection
of bidimensional hierarchical heavy hitters in software-defined networks,” in
Communications (LATINCOM), 2013 IEEE Latin-America Conference on, pp. 1–6,
IEEE, 2013.
[7] Y. Afek, A. Bremler-Barr, S. L. Feibish, and L. Schiff, “Detecting heavy flows in the
sdn match and action model,” Computer Networks, vol. 136, pp. 1–12, 2018.
[8] R. Harrison, Q. Cai, A. Gupta, and J. Rexford, “Network-wide heavy hitter detection
with commodity switches,” in Proceedings of the Symposium on SDN Research, p. 8,
ACM, 2018.
[9] V. Sivaraman, S. Narayana, O. Rottenstreich, S. Muthukrishnan, and J. Rexford,
“Heavy-hitter detection entirely in the data plane,” in Proceedings of the Symposium
on SDN Research, pp. 164–176, ACM, 2017.
[10] A. Metwally, D. Agrawal, and A. El Abbadi, “Efficient computation of frequent and
top-k elements in data streams,” in International Conference on Database Theory,
pp. 398–412, Springer, 2005.
[11] G. Cormode and S. Muthukrishnan, “An improved data stream summary: the countmin
sketch and its applications,” Journal of Algorithms, vol. 55, no. 1, pp. 58–75,
2005.
[12] C. Estan and G. Varghese, New directions in traffic measurement and accounting,
vol. 32. ACM, 2002.
[13] G. S. Manku and R. Motwani, “Approximate frequency counts over data streams,” in
VLDB’02: Proceedings of the 28th International Conference on Very Large Databases,
pp. 346–357, Elsevier, 2002.
[14] J. S. Vitter, “Random sampling with a reservoir,” ACM Transactions on Mathematical
Software (TOMS), vol. 11, no. 1, pp. 37–57, 1985.
[15] K. Yi and Q. Zhang, “Optimal tracking of distributed heavy hitters and quantiles,”
Algorithmica, vol. 65, no. 1, pp. 206–223, 2013.
[16] “The CAIDA UCSD Anonymized Internet Traces 2015.” http://www.caida.org/data/
passive/passive_2015_dataset.xml.
[17] “editcap tool.” https://www.wireshark.org/docs/man-pages/editcap.html.
[18] “scapy.” https://scapy.net/.
[19] “tcpreplay tool.” https://tcpreplay.appneta.com/.
[20] “OpenFlow.” https://www.opennetworking.org/sdn-resources/openflow. [Online].
[21] “RabbitMQ .” https://www.rabbitmq.com/.
[22] M. Mitzenmacher, T. Steinke, and J. Thaler, “Hierarchical heavy hitters with the
space saving algorithm,” in 2012 Proceedings of the Fourteenth Workshop on Algorithm
Engineering and Experiments (ALENEX), pp. 160–174, SIAM, 2012.
[23] G. Cormode, S. Muthukrishnan, K. Yi, and Q. Zhang, “Optimal sampling from
distributed streams,” in Proceedings of the twenty-ninth ACM SIGMOD-SIGACTSIGART
symposium on Principles of database systems, pp. 77–86, ACM, 2010.
[24] B. Kveton, S. Muthukrishnan, H. T. Vu, and Y. Xian, “Finding subcube heavy hitters
in analytics data streams,” in Proceedings of the 2018 World Wide Web Conference
on World Wide Web, pp. 1705–1714, International World Wide Web Conferences
Steering Committee, 2018.