臺灣博碩士論文加值系統

隨着近些年5G的發展，5G的新使用場景給產業界帶來了新的發展方向。隨着物聯網的發展，隨之而來的是網路中物聯網裝置的爆增。根據McKinsey Global Institute發表於2015的報告，截至到2025年，將會有1兆的物聯網裝置接入網路。面對大量且多樣的物聯網裝置，使用軟體定義網路是勢在必行的。但由於交換機的流表空間是有限的，並不能容納所有的流表條目。因此，我們需要一種有效的流表條目管理方式來減少封包處理延遲和信令開銷。在一般的網路中，延遲插入可以減少流表條目的數量，但會增加封包處理的延遲，導致網路效能下降。PFIM和EPFIM專爲物聯網裝置設計，他們通過偵測流量的週期性並進行流表條目的預先插入來降低封包處理延遲。但是他們無法偵測同一流量中的多個週期性，且在週期判斷的準確性和偵測時的信號開銷仍有改進的空間。

本文提出了一種基於週期性子流的主動流表條目插入機制。我們設計了一種新的數據收集方法，以提高流表條目預先插入的準確性。加入了全新的資料結構，實現了對同一流量中多種週期性流量的偵測。提出了新的演算法，實現了精準的週期計算。我們的方法相比與以往的方法，在流表命中率上有高達80%的提升，在平均每一流表命中率所需插入次數上，有高達99%的提升。

With the developing of 5G mobile network, 5G provides a new scenario and new direction of development for the industry, making the Internet of Things (IoT) into the golden age of development. With the developing of IoT, the number of IoT devices in the network keep increasing. According to the report of McKinsey Global Institute, which released in 2015, there will be 1 trillion IoT devices connect to the internet. SDN is necessary since ISPs require to provide various services for various IoT devices. However, the size of the flow table is limited, and it can not accommodate all flow entries for all traffic passing through. Thus, an efficient flow entry management scheme is required to reduce the processing delay and signal overhead. In general network, delayed installation is proposed, and it may reduce the number of flow entries. However, it will increase the processing delay, downgrading the network performance. PFIM and EPFIM are designed for IoT. They reduce the processing delay by detecting the periodicity of traffic and pre-installing flow entries. However, they are not able to detect multiple periodicities. Besides, there is still room for improving the accuracy of periodic detection and reducing signal overhead.

In this thesis, we propose a periodic subflow-based proactive flow installation mechanism. We design a new method of data collection to improve the accuracy of pre-installation. A new data structure is designed to enable the detection of multiple periodicities in a single flow. A new algorithm is proposed to achieve accurate periodic calculation. Compared with the previous mechanism, our mechanism improves the hit ratio of flow table hit by up to 80%, and improves the required installation per table hit up to 99%.

中文摘要 .............i
Abstract ..............ii
Acknowledgements ............iv
Contents ..............v
List of Tables .............vii
List of Figures ............viii
1 Introduction ............1
2 Related Works .............6
2.1 Delay Installation and Expedite Eviction .......7
2.1.1 Defect on Expedited Eviction .......9
2.1.2 Defect on Delayed Installation .......9
2.1.3 Defect on Data Collection Mechanism .....9
2.2 PFIM ............11
2.2.1 Defect of Data Collection Mechanism .....11
2.2.2 Slow Reaction While periodicity Changes .....12
2.3 EPFIM ............13
2.3.1 Defect on Debug Function .......13
3 Proposed Scheme ...........15
3.1 Why Focus on Proactive-Installation .......15
3.2 Periodic Subflow-Based Proactive Flow entry Installation Mechanism
(PSPFIM) ............18
3.2.1 Improvement on Data Collection .......18
3.2.2 Byte-Count Division ........19
3.2.3 Calculating GCD of Flow Intervals ......20
3.2.4 Algorithm for Finding Periodicity in PSPFIM ....24
3.2.5 Condition for Pre-install Termination .....25
4 Simulation Setup ...........26
4.1 Table Hit Ratio(Rhit) ..........26
4.2 Required Installation per Table Hit(Rrith) ......27
4.3 Simulation Environment ..........27
4.4 Assumption ...........28
5 Performance Evaluation ...........29
5.1 Experiment 1: Improvement on Data Collection Mechanism ..29
5.1.1 Table Hit Ratio .........29
5.1.2 Required Installation per Table Hit ......33
5.2 Experiment 2: Different Period on Performance .....34
5.2.1 Table Hit Ratio .........34
5.2.2 Required Installation per Table Hit ......37
5.3 Experiment 3: Difference in Performance Between GCD Existence .38
5.3.1 Table Hit Ratio .........40
5.3.2 Required Installation per Table Hit ......40
5.4 Experiment 4: Improvement on number of OpenFlow Message ...41
6 Conclusions ............43
References .............44

[1] Angel Leonardo Valdivieso Caraguay, Alberto Benito Peral, Lorena Isabel ´
Barona Lopez, and Luis Javier Garcia Villalba. Sdn: Evolution and opportu
nities in the development iot applications. International Journal of Distributed
Sensor Networks, 10(5):735142, 2014.
[2] Ali Sydney. The evaluation of software defined networking for communication and
control of cyber physical systems. PhD thesis, Kansas State University, 2013.
[3] James Manyika, Michael Chui, Peter Bisson, Jonathan Woetzel, Richard Dobbs,
Jacques Bughin, and Dan Aharon. Unlocking the potential of the internet of
things. McKinsey Global Institute, 2015.
[4] Partha Pratim Ray. A survey of iot cloud platforms. Future Computing and
Informatics Journal, 1(1-2):35–46, 2016.
[5] Philipp Schulz, Maximilian Matthe, Henrik Klessig, Meryem Simsek, Gerhard
Fettweis, Junaid Ansari, Shehzad Ali Ashraf, Bjoern Almeroth, Jens Voigt, Ines
Riedel, et al. Latency critical iot applications in 5g: Perspective on the design
of radio interface and network architecture. IEEE Communications Magazine,
55(2):70–78, 2017.
[6] Meigen Huang and Bin Yu. Sdn-based secure localization in heterogeneous wsn.
In International Conference on Information and Communications Security, pages
276–287. Springer, 2017.
[7] Diego Kreutz, Fernando Ramos, Paulo Verissimo, Christian Esteve Rothenberg,
Siamak Azodolmolky, and Steve Uhlig. Software-defined networking: A compre
hensive survey. arXiv preprint arXiv:1406.0440, 2014.
[8] Anders Nygren, B Pfaff, B Lantz, B Heller, C Barker, C Beckmann, D Cohn,
D Malek, D Talayco, D Erickson, et al. Openflow switch specification version 1.5.
1. Open Networking Foundation, Tech. Rep., 2015.
[9] Brent Stephens, Alan Cox, Wes Felter, Colin Dixon, and John Carter. Past: Scal
able ethernet for data centers. In Proceedings of the 8th international conference
on Emerging networking experiments and technologies, pages 49–60. ACM, 2012.
[10] Junho Suh, Ted Taekyoung Kwon, Colin Dixon, Wes Felter, and John Carter.
Opensample: A low-latency, sampling-based measurement platform for commod
ity sdn. In 2014 IEEE 34th International Conference on Distributed Computing
Systems, pages 228–237. IEEE, 2014.
[11] Chuanji Zhang, Hemin Yang, and George F Riley. Admission control in software
defined datacenter network in view of flow table capacity. In IEEE INFOCOM
2018-IEEE Conference on Computer Communications Workshops (INFOCOM
WKSHPS), pages 871–876. IEEE, 2018.
[12] Zehua Guo, Ruoyan Liu, Yang Xu, Andrey Gushchin, Anwar Walid, and
H Jonathan Chao. Star: Preventing flow-table overflow in software-defined net
works. Computer Networks, 125:15–25, 2017.
[13] Theophilus Benson, Aditya Akella, and David A Maltz. Network traffic charac
teristics of data centers in the wild. In Proceedings of the 10th ACM SIGCOMM
conference on Internet measurement, pages 267–280. ACM, 2010.
[14] Aakash S Iyer, Vijay Mann, and Naga Rohit Samineni. Switchreduce: Reduc
ing switch state and controller involvement in openflow networks. In 2013 IFIP
Networking Conference, pages 1–9. IEEE, 2013.
[15] Masoud Moshref, Minlan Yu, Abhishek Sharma, and Ramesh Govindan. vcrib:
Virtualized rule management in the cloud. In Presented as part of the, 2012.
[16] Kanak Agarwal, Colin Dixon, Eric Rozner, and John Carter. Shadow macs: Scal
able label-switching for commodity ethernet. In Proceedings of the third workshop
on Hot topics in software defined networking, pages 157–162. ACM, 2014.
[17] Adam Zarek, Y Ganjali, and D Lie. Openflow timeouts demystified. Univ. of
Toronto, Toronto, Ontario, Canada, 2012.
[18] Eun-Do Kim, Seung-Ik Lee, Yunchul Choi, Myung-Ki Shin, and Hyoung-Jun Kim.
A flow entry management scheme for reducing controller overhead. In 16th In
ternational Conference on Advanced Communication Technology, pages 754–757.
IEEE, 2014.
[19] Sajad Shirali-Shahreza and Yashar Ganjali. Delayed installation and expedited
eviction: An alternative approach to reduce flow table occupancy in sdn switches.
IEEE/ACM Transactions on Networking, 26(4):1547–1561, 2018.
[20] Peter Bull, Ron Austin, and Mak Sharma. Pre-emptive flow installation for inter
net of things devices within software defined networks. In 2015 3rd International
Conference on Future Internet of Things and Cloud, pages 124–130. IEEE, 2015.
[21] Luis Sanabria-Russo, Jesus Alonso-Zarate, and Christos Verikoukis. Sdn-based
pro-active flow installation mechanism for delay reduction in iot. In 2018 IEEE
Global Communications Conference (GLOBECOM), pages 1–6. IEEE, 2018.
[22] Arunan Sivanathan, Hassan Habibi Gharakheili, Franco Loi, Adam Radford,
Chamith Wijenayake, Arun Vishwanath, and Vijay Sivaraman. Classifying iot
devices in smart environments using network traffic characteristics. IEEE Trans
actions on Mobile Computing, 2018.
[23] Hasan Ali Khattak, Michele Ruta, and Eugenio Eugenio Di Sciascio. Coap-based
healthcare sensor networks: A survey. In Proceedings of 2014 11th International
Bhurban Conference on Applied Sciences ＆ Technology (IBCAST) Islamabad,
Pakistan, 14th-18th January, 2014, pages 499–503. IEEE, 2014.
[24] Yuvraj Upadhyay, Amol Borole, and D Dileepan. Mqtt based secured home au
tomation system. In 2016 Symposium on Colossal Data Analysis and Networking
(CDAN), pages 1–4. IEEE, 2016.
[25] Eun-Do Kim, Yunchul Choi, Seung-Ik Lee, and Hyoung Jun Kim. Enhanced flow
table management scheme with an lru-based caching algorithm for sdn. IEEE
Access, 5:25555–25564, 2017.
[26] Jmmurillo. How to find the approximate basic period or gcd of a list of numbers?
Mathematics Stack Exchange. URL:https://math.stackexchange.com/q/914288
(version: 2017-11-23).