臺灣博碩士論文加值系統

軟體定義網路是一個新興的架構，它能讓網路可程式化、網路設計有彈性、有效率地控管網路。軟體定義網路主要的架構切成了三層，包刮應用層、控制層、資料層。在這個架構下，控制器就像是整體網路的大腦，它管理資料層的交換器。主要會影響整體網路的效能有控制器的位置、控制器跟交換機的延遲時間、控制器之間的延遲時間、控制器的容量。決定控制器擺放的位置與計算出網路所需的控制器數量，同時還要滿足各個網路所需的條件，不是輕易地就可以決定出來。已經有集中式的解法來解決這個問題。但是，當網路環境會動態地變動，集中式的解法可能會增加成本或是不滿足限制條件。在這篇論文中，我們提出了一個潛在賽局，這個賽局是一個分散式的系統，用來解決軟體定義網路控制器佈署的問題。同時，我們的分散式系統的機制有自我穩定的特性，當網路環境動態地改變時，它可以自主適應地來更改結果。再者，我們提出我們的賽局有確定的潛在方程式、賽局最後都會停在納許均衡點。模擬結果展現出了我們的方法有自主適應的特性。

Software defined network (SDN) has emerged as a new paradigm that provides network programmability, flexibility and efficient network management. The main idea of SDN is splitting the network into application layer, control layer and data layer. In this splitting concept, controller is the brain of SDN network, which manages SDN switch. SDN network performance will be affected by controller location and some metrics such as controller-switch latency, inter-controller latency and controller capacity. It is not easy to determine the location for controllers and number of controllers requirement while meeting the constraint. There existing centralized solution that increases cost and not satisfies constraint when the network dynamics. In this paper, we proposed a potential game which is a distributed mechanism to solve controller placement problem (CPP). Meanwhile, our distributed mechanism have self-stabilizing property that it can adaptively change solution when the network dynamics such as controller failure, link failure and adding nodes. Also, we present our game have exact potential function and end up to Nash equilibrium (NE) eventually. Simulation result shows our approach have adaptability property

摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Related Works and Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.1 Overview of CPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Adaptive Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Non-Cooperative Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.4 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Distributed Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.1 Design of Basic Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Stability Proof of Basic Game . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3 Design of Priority Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.4 Design of Fast Priority Game . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1 Experiment Environment Setup . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.2 Static Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3 Large Scale Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.4 Link Failure Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.5 Controller Failure Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.6 Adding node Scenario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.7 Dynamic Switch Traffic Load . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

[1] B. Heller, R. Sherwood, and N. McKeown, “The controller placement problem,” in Proceedings of the First Workshop on Hot Topics in Software Defined Networks, ser. HotSDN ’12. New York, NY, USA: ACM, 2012, pp. 7–12.
[2] G. Yao, J. Bi, Y. Li, and L. Guo, “On the capacitated controller placement problem in software defined networks,” IEEE Communications Letters, vol. 18, no. 8, pp. 1339–1342, Aug 2014.
[3] F. J. Ros and P. M. Ruiz, “On reliable controller placements in software-defined networks,” Computer Communications, vol. 77, pp. 41 – 51, 2016.
[4] D. Hock, M. Hartmann, S. Gebert, M. Jarschel, T. Zinner, and P. Tran-Gia, “Pareto-optimal resilient controller placement in sdn-based core networks,” in Proceedings of the 2013 25th International Teletraffic Congress (ITC), Sep. 2013, pp. 1–9.
[5] A. Sallahi and M. St-Hilaire, “Expansion model for the controller placement problem in software defined networks,” IEEE Communications Letters, vol. 21, no. 2, pp. 274–277, Feb 2017.
[6] A. Sallahi and M. St-Hilaire, “Optimal model for the controller placement problem in software defined networks,” IEEE Communications Letters, vol. 19, no. 1, pp. 30–33, Jan 2015.
[7] M. T. I. ul Huque, G. Jourjon, and V. Gramoli “Revisiting the controller placement problem,” in 2015 IEEE 40th Conference on Local Computer Networks (LCN), Oct 2015, pp. 450–453.
[8] L. Yao, P. Hong, W. Zhang, J. Li, and D. Ni, “Controller placement and flow based dynamic management problem towards sdn,” in 2015 IEEE International Conference on Communication Workshop (ICCW), June 2015, pp. 363–368. 36
[9] B. P. R. Killi and S. V. Rao, “Optimal model for failure foresight capacitated controller placement in software-defined networks,” IEEE Communications Letters, vol. 20, no. 6, pp. 1108–1111, June 2016.
[10] S. Lange, S. Gebert, T. Zinner, P. Tran-Gia, D. Hock, M. Jarschel, and M. Hoffmann, “Heuristic approaches to the controller placement problem in large scale sdn networks,” IEEE Transactions on Network and Service Management, vol. 12, no. 1, pp. 4–17, March 2015.
[11] A. Jalili, V. Ahmadi, M. Keshtgari, and M. Kazemi, “Controller placement in software defined wan using multi-objective genetic algorithm,” in 2015 2nd International Conference on Knowledge-Based Engineering and Innovation (KBEI), Nov 2015, pp. 656–662.
[12] J. Liao, H. Sun, J. Wang, Q. Qi, K. Li, and T. Li, “Density cluster based approach for controller placement problem in large-scale software defined networkings,” Computer Networks, vol. 112, pp. 24 – 35, 2017.
[13] M. T. I. ul Huque, W. Si, G. Jourjon, and V. Gramoli, “Large-scale dynamic controller placement,” IEEE Transactions on Network and Service Management, vol. 14, no. 1, pp. 63–76, March 2017.
[14] M. Tanha, D. Sajjadi, R. Ruby, and J. Pan, “Capacity-aware and delay-guaranteed resilient controller placement for software-defined wans,” IEEE Transactions on Network and Service Management, vol. 15, no. 3, pp. 991–1005, Sep. 2018.
[15] M. F. Bari, A. R. Roy, S. R. Chowdhury, Q. Zhang, M. F. Zhani, R. Ahmed, and R. Boutaba, “Dynamic controller provisioning in software defined networks,” in Proceedings of the 9th International Conference on Network and Service Management (CNSM 2013), Oct 2013, pp. 18–25.
[16] H. K. Rath, V. Revoori, S. M. Nadaf, and A. Simha, “Optimal controller placement in software defined networks (sdn) using a non-zero-sum game,” in Proceeding of IEEE In-37 ternational Symposium on a World of Wireless, Mobile and Multimedia Networks 2014, June 2014, pp. 1–6.
[17] L. Yen and B. Ye, “Link-preserving channel assignment game for wireless mesh networks,” in 2016 International Computer Symposium (ICS), Dec 2016, pp. 446–451.
[18] L. Yen and Z. Chen, “Game-theoretic approach to self-stabilizing distributed formation of minimal multi-dominating sets,” IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 12, pp. 3201–3210, Dec 2014.
[19] L.-H. Yen, C.-M. Lin, and V. C. M. Leung, “Distributed lifetime-maximized target coverage game,” ACM Trans. Sen. Netw., vol. 9, no. 4, pp. 46:1–46:23, Jul. 2013.
[20] B. P. R. Killi, E. A. Reddy, and S. V. Rao, “Cooperative game theory based network partitioning for controller placement in sdn,” in 2018 10th International Conference on Communication Systems Networks (COMSNETS), Jan 2018, pp. 105–112.
[21] D. Monderer and L. S. Shapley, “Potential games,” Games and Economic Behavior, vol. 14, no. 1, pp. 124 – 143, 1996.
[22] S. Knight, H. X. Nguyen, N. Falkner, R. Bowden, and M. Roughan, “The internet topology zoo,” IEEE Journal on Selected Areas in Communications, vol. 29, no. 9, pp. 1765–1775, October 2011