臺灣博碩士論文加值系統

軟體定義網路（SDN）將資料層與控制層分離，故可快速部署新技術和降低網路管理成本，在SDN中，交換器依照記錄於資料流條目中由控制器決定的規則來轉送封包，然而當一個封包進入交換器且未匹配任何資料流條目時，交換器會發出Packet-In訊息請求控制器處理。由於控制器負責眾多交換器，故一般會成為效能瓶頸，目前已有許多降低控制器負荷的研究。然而，仍有很多無謂的Packet-In訊息送至控制器。
本論文提出Packet-In Buffering and Prioritization (PIBP)的方法，利用暫存Packet-In訊息及優先化這些訊息來減少Packet-In訊息數量及加快其處理速度。PIBP的概念是交換器只針對未匹配資料流表之每個新資料流的第一個封包發送Packet-In給控制器，其他屬於同資料流的封包則暫存在交換器中，同時讓這些封包具較高優先權，亦即當控制器的回傳封包經交換器送出後，暫存在交換器且屬於同資料流的封包也會一併送出。我們也以排隊理論來分析PIBP效能。模擬結果顯示與優先權隊列方法相比，PIBP最多可減少23.08% 送至控制器的Packet-In訊息數量、最多可減少新資料流第一個封包的延遲時間為15.31%、最多可減少Packet-In訊息的延遲時間為21.34%、且最多可減少整體封包延遲時間為19.50%。

Software-Defined Networks (SDN), which decouples the control plane from the data plane, can fast deploy new network technologies and reduce the network management cost. In SDN, the switch forwards incoming packets according to well-defined rules, which are determined by the controller and recorded in the flow entries. When a switch receives a packet that is unmatched with any flow entries, the switch sends this packet as Packet-In message to the controller for its processing. Since the controller is responsible for many switches, it is usually a performance bottleneck. There are many studies on reducing controller’s load, but still many unnecessary Packet-In messages are sent to the controller.
This thesis proposes a novel method, Packet-In Buffering and Prioritization (PIBP). PIBP buffers Packet-In messages and prioritizes these messages to reduce the number of Packet-In messages sent to the controller and accelerate their processing, respectively. The concept of PIBP is that only the first packet of each flow which does not match any flow entry is sent to the controller. The other packets belonging to the same flow are temporarily stored in the switch. Moreover, these messages have higher priority. That is, after the packet from the controller has been forwarded from switches, the buffered packets belonging to the same flow are also forwarded. We formally analyze the performance of PIBP with queuing theory. The simulation results show that PIBP can decrease the number of Packet-In messages sent to the controller by 23.08% at most, the delay of first packet of each flow by 15.31% at most, the delay of Packet-In messages by 21.34% at most, and the overall delay by 19.50% at most, compared to a typical method, Priority-Queue.

摘要 I
Abstract II
Contents III
List of Figures IV
List of Tables V
Chapter 1 Introduction 1
Chapter 2 Background 4
2.1. SDN and OpenFlow 4
2.2. Related Work 5
Chapter 3 Packet-In Buffering and Prioritization 8
3.1. Concept of PIBP 8
3.2. Working Mechanism 8
3.3. Example 10
Chapter 4 Analysis 13
4.1. Used Notations 13
4.2. Analytical Model 14
4.3. Analysis 15
Chapter 5 Performance Evaluation 20
5.1. Simulation Setup 20
5.2. Impact of packet arrival rate in each flow (λP) 21
5.3. Impact of flow arrival rate (λF) 23
Chapter 6 Conclusion 25
References 27

[1] N. McKeown, Software-defined networking, INFOCOM keynote talk, Rio de Janeiro, Brazil, April 2009.
[2] “Software-Defined Networking: The New Norm for Networks”, Open Networking Foundation, April 2012.
[3] Y. Jarraya, T. Madi, and M. Debbabi, “A Survey and a Layered Taxonomy of Software-Defined Networking,” IEEE Communication Surveys & Tutorials, vol. 16, no. 4, pp. 1955-1980, 2014.
[4] N. McKeown, T. Anderson, H. Balakrishnan, G. Parulkar, L. Peterson, J. Rexford, S. Shenker, and J. Turner, “OpenFlow: Enabling Innovation in Campus Networks,” ACM SIGCOMM Computer Communication Review, vol. 38, no. 2, pp. 69-74, April 2008.
[5] A. Lara, A. Kolasani, and B. Ramamurthy, “Network Innovation using OpenFlow: A Survey,” IEEE Communication Surveys & Tutorials, vol. 16, no. 1, pp. 493-512, Aug. 2013.
[6] W. Miao, G. Min, Y. Wu, and H. Wang , “Performance Modelling of Preemption-based Packet Scheduling for Data Plane in Software Defined Networks,” in Proceedings of the IEEE International Conference on Smart City, Chengdu, China, pp. 60–65, Dec. 2015.
[7] Y. Goto, H. Masuyama, B. Ng, W. K. Seah, and Y. Takahashi, “Queueing Analysis of Software Defined Network with Realistic OpenFlow-based Switch Model,” IEEE International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS), London, UK, Sept. 2016.
[8] T. Koponen, M. Casado, N. Gude, J. Stribling, L. Poutievski, M. Zhu, R. Ramanathan, Y. Iwata, H. Inoue, T. Hama, and S. Shenker, “Onix: a distributed control platform for largescale production networks,” in Proceedings of the 9th USENIX conference on Operating systems design and implementation, Vancouver, CA, pp. 351-364, 2010.
[9] A. Tootoonchian and Y. Ganjali, “HyperFlow: a distributed control plane for OpenFlow,” in Proceedings of the 2010 internet network management conference on Research on enterprise networking, San Jose, CA, pp. 3, 2010.
[10] G. Wang, J. Li, and X. Chang, “Modeling and Performance Analysis of the Multiple Controllers’ Approach in Software Defined Networking,” 2015 IEEE 23rd International Symposium on Quality of Service (IWQoS), Portland, USA, June 2015.
[11] M. Yu, J. Rexford, M. J. Freedman, and J. Wang, “Scalable flow-based networking with DIFANE,” ACM SIGCOMM Computer Communication Review, vol. 40, no. 4, pp. 351-362, Oct. 2010..
[12] A. R. Curtis, J. C. Mogul, J. Tourrilhes, P. Yalagandula, P. Sharma, and S. Banerjee, “DevoFlow: scaling flow management for high-performance networks,” ACM SIGCOMM Computer Communication Review, vol. 41, no. 4, pp. 254-265, Aug. 2011.
[13] D. Kotani and Y. Okabe, “Packet-In Message Control for Reducing CPU Load and Control Traffic in OpenFlow Switches,” 2012 European Workshop on Software Defined Networking (EWSDN), Oct. 2012.
[14] ONF, Open Networking Foundation, [Online] Available at
https://www.opennetworking.org/, accessed June 2017.
[15] Open Networking Foundation, “OpenFlow Switch Specification 1.4.0,” Oct. 2013. [Online]. Available at
https://www.opennetworking.org/images/stories/downloads/sdn-resources/onf-specifications/openflow/openflow-spec-v1.4.0.pdf.
[16] Head-of-line blocking from Wikipedia. [Online]. Available at
https://en.wikipedia.org/wiki/Head-of-line_blocking, accessed June 2017.
[17] D. Pan and Y. Yang, “FIFO-based multicast scheduling algorithm for virtual output queued packet switches,” IEEE Transactions on Computers, vol. 54, no. 10, pp. 1283-1297, Oct. 2005.
[18] A. Martı´nez, P. J. Garcı´a, F. J. Alfaro, Jose´ L. Sa´nchez, Jose´ Flich, F. J. Quiles, and J. Duato, “A Switch Architecture Guaranteeing QoS Provision and HOL Blocking Elimination,” IEEE Transactions on Parallel and Distributed Systems, vol. 20, is. 1, pp. 13-24, Jan. 2009.
[19] V. Skorpil and P. Zednicek, “Virtual Output Queuing,” International Journal of Communications, vol. 5, is. 1, pp. 10-17, 2011.
[20] R. Pe˜naranda, C. G´omez, M. E. G´omez, P. L´opez, and J. Duato, “HoL-Blocking Avoidance Routing Algorithms in Direct Topologies,” 2014 IEEE International Conference on High Performance Computing and Communications, 2014 IEEE 6th International Symposium on Cyberspace Safety and Security, and 2014 IEEE 11th International Conference on Embedded Software and System (HPCC, CSS, ICESS), Paris, France, Aug. 2014.
[21] P. Y´ebenes, G. Maglione-Mathey, J. Escudero-Sahuquillo, P. J. Garc´ıa, and F. J. Quiles, “Modeling a switch architecture with virtual output queues and virtual channels in HPC-systems simulators,” 2016 International Conference on High Performance Computing & Simulation (HPCS), Innsbruck, Austria, July 2016.
[22] Wolfgang Fischer, “The Markov-modulated Poisson process (MMPP) cookbook ,” Performance Evaluation, vol. 18, is. 2, pp. 149-171, Sept. 1993.
[23] Hans-Peter Schwefel, “Correlated/Bursty Traffic Models, MMPPs”. [Online]. Available at
http://kom.aau.dk/~hps/TrafficII_Fall04/MM2_MMPP.pdf, accessed May 2017.
[24] Daniel Myers, “CS 547 Lectures 26 and 27: Priority Queueing”. [Online]. Available at
http://pages.cs.wisc.edu/~dsmyers/cs547/lecture_26_27_priority_queueing.pdf, accessed May 2017.
[25] Daniel Myers, “CS 547 Lecture 25: Bulk Arrivals”. [Online]. Available at
http://pages.cs.wisc.edu/~dsmyers/cs547/lecture_25_bulk_arrivals.pdf, accessed May 2017.
[26] S. Ghimire, R. P. Ghimire, and G. B. Thapa, “Mathematical Models of Mb/M/1 Bulk Arrival Queueing System,” Journal of the Institute of Engineering, vol. 10, no. 1, pp. 184-191, 2014.