軟體定義網路負載平衡演算法效能比較

Performance Comparisons of Load Balancing Algorithms for Software Defined Networking

韋地亞(Widhi Yahya)

指導教授 ： 江振瑞 ； -

國立中央大學/資訊電機學院/資訊工程學系/碩士(2014年)

摘要

軟體定義網路(Software Defined Networking, SDN) 的概念是將網路設備中的控制層(control plane)與資料層(data plane)分開。在SDN中，有一個集中管理的控制器(controller)可以設置交換器上的封包轉送表(forwarding table)(也稱為流表(flow table))，負責各種通訊間的封包轉發。SDN的使用者可以在控制器上撰寫應用程式來監控和維護整個網路。負載平衡(load balancing)就是其中一個應用的例子，可以用SDN的概念來達到廣域網路中，分散各處伺服器(server)間負載量的平衡。本論文提出一個負載平衡演算法，利用延伸Dijkstra最短路徑演算法(extended Dijkstra’s shortest path algorithm)， 考慮節點權重與邊權重的好處，來找到離客戶端(client)最近的伺服器。我們使用Pyretic 語言來實作演算法，並使用Mininet 模擬工具在Abilene 拓樸下來評估演算法的效能。我們也比較了循環演算法(round-robin algorithm)和隨機演算法(randomized algoithm)的模擬結果。實驗結果顯示本論文提出的演算法比起其他演算法，在控制器上多花費一點點的計算負擔和記憶體使用量，即可達到更短的端到端的延遲(end-to-end latency)，更大的網路吞吐量(throughput)以及更短的反應時間(response time)。

關鍵字: 軟體定義網路(SDN), 負載平衡, 循環演算法, 隨機演算法, Dijkstra最短路徑演算法

關鍵字

軟體定義網路(SDN) ； 負載平衡 ； 循環演算法 ； 隨機演算法 ； Dijkstra最短路徑演算法

並列摘要

Software Defined Networking (SDN) is a concept that is used to decouple the control plane and data plane of network devices. In SDN, a logically centralized controller configures the forwarding tables (also called flow tables) of switches that are responsible for forwarding the packets of communication flows. SDN users can composite application programs run on top of the controller to monitor and manage the whole network. Load balancing is an example of applications that can be achieved by using the SDN concept for balancing the loads of servers that are located and spread in wide area networks. In this thesis, we propose a load balancing algorithm that takes advantage of the extended Dijkstra’s shortest path algorithm considering both the edge weights and node weights to find the nearest server for a requesting client. We implement the proposed algorithm in Pyretic and simulate it under the Abilene topology with Mininet tools. We also compare the simulation results with those of the naive load balancing schemes, namely the round-robin algorithm and the randomized algorithm. As shown by the comparisons, the proposed algorithm outperforms the others in term of the network end-to-end latency, throughput and response time at the expense of a little heavier computation load and more memory usage of the SDN controller.

Keywords: Software Defined Networking (SDN), Load Balancing, Round Robin Algorithm, Randomized Algorithm, Dijkstra’s Shortest Path Algorithm

並列關鍵字

Software Defined Networking (SDN) ； Load Balancing ； Round Robin Algorithm ； Randomized Algorithm ； Dijkstra’s Shortest Path Algorithm

參考文獻

[AKL13] S. Agarwal, M. Kodialam, and T. V. Lakshman, “Traffic Engineering in Software Defined Networks”, Proceedings IEEE INFOCOM, 2013.

[CFSV+89] Cieslak, A. Fawaz, S. Sack, P. Varaiya, J. Walrand,and A. Li, “The Programmable Network Prototyping System,” INFOCOM '89. Proceedings of the Eighth Annual Joint Conference of the IEEE Computer and Communications Societies. Technology: Emerging or Converging, 1989.

[DTS13] S. Das, D. Talayco, and R. Sherwood, “Software-Defined Networking and OpenFlow,” 13-Handbook of Fiber Optic Data Communication a Practical Guide to Optical Networking, 4th edition, 2013.

[FYFA12] S. Fang, Y. Yu, C. H. Foh, and K. M. Aung, “A Loss-free Multipathing Solution for Data Center Network: using Software-defined Networking Approach”, APMRC, 2012.

[JHLC14] J.R. Jiang, H.W. Huang, J.H. Liao, and S.Y. Chen, "Extending Dijkstra’s Shortest Path Algorithm for Software Defined Networking," Technical Report, National Central University, 2014.