基於Multipath TCP在軟體定義網路下之多路徑路由演算法

An Efficient Multipath Routing Algorithm for Multipath TCP in Software-Defined Networks

劉力瑋(Liu, Lee Wei)

指導教授 ： 許健平

國立清華大學/電機資訊學院/通訊工程研究所/碩士(2015年)

摘要

隨著軟體定義網路的快速發展，我們比過去更容易操縱網路流量。多路徑繞徑協定一直都是一個重要的研究主題，在本文中，我們著重在設計多路徑演算法結合Multipath TCP(MPTCP)。MPTCP 是 TCP 的延伸，此協定透過多條路徑來傳送，而不是用一條路徑來傳送，此協定明顯提高了點對點傳輸的吞吐量。換言之，一個MPTCP的流量可以分成多個子流量來進行點對點的傳輸。我們將此繞逕問題制定成k條不相交路徑之最大化最小頻寬的路徑。k條不相交路徑之最大化最小頻寬的路徑是要找k條不相交的路徑，且在這k條不相交的路徑中頻寬最小的路徑要被最大化。由於此問題屬於NP-complete的問題，所以我們提出了一個啟發式演算法能在多項式時間內解決此問題。我們將來自同一組點對點傳輸的多個MPTCP子流量分散到不同的路徑上來避免子流量互相競爭網路資源，且縮小了每條路徑的頻寬差距。我們的模擬結果顯示我們提出的演算法之於其他演算法能針對一個MPTCP流量提供較好得吞吐量，較小的路徑頻寬差距以及較短的平均路徑長度。

關鍵字

k條最大化最小之不相交路徑 ； 多路徑路由演算法 ； 多路徑傳輸控制協定 ； 軟體定義網路

並列摘要

Due to the rapid growth of Software-Defined Networks, we can manipulate network traffic easier than before. One of the major issues on SDN is the multipath routing protocols. In this paper, we focus multipath routing algorithm on Multipath TCP (MPTCP). MPTCP is an extension of TCP that increases the throughput of TCP communication significantly by utilizing multiple paths transmission rather than single path. In other words, an MPTCP flow generates multiple sub-flows for end-to-end communications. We consider the multipath routing problem as a k Max-Min bandwidth disjoint paths one. The problem is to find k disjoint paths with relative higher throughput and the smallest bottleneck bandwidth of the k paths is the maximum. Since this problem is NP-complete, we propose a heuristic algorithm to solve this problem in polynomial time. The simulation results show that our proposed algorithm perform better than previous works in terms of average throughput and average hop count.

並列關鍵字

k Max-min disjoint paths ； multipath routing algorithm ； multipath TCP ； software-defined networks

參考文獻

[4] M. Koerner, and O. Kao, "Evaluating SDN based Rack-to-Rack Multi-Path Switching for Data-Center Networks," Procedia Computer Science, Vol. 34, pp. 118-125, 2014

[5] R. van der Pol, M. Bredel, and A. Barczyk, “Experiences with MPTCP in an Intercontinental Multipathed OpenFlow Network,” Proceedings of the 29th Trans European Research and Education Networking Conference, Maastricht, Netherland, June 2013.

[8] I. F. Akyildiz, A. Lee, P. Wang, M. Luo, and W. Chou, "A Roadmap for Traffic Engineering in SDN-OpenFlow Networks," Computer Networks, Vol. 71, No. 4, pp. 1-30, October 2014.

[11] R.M. Karp, “On the Computational Complexity of Combinatorial Problems,” Networks, Vol. 5, No. 1, pp. 45-68, USA, January 1975.

[12] B. Ulrik, G. Neyer, and D. Wagner, "Edge-Disjoint Paths in Planar Graphs with Short Total Length," 1996.