軟體定義網路架構下使用線性規劃獲得最佳多路徑遶送

Using Linear Programming To Obtain Optimal Multipath Routing In SDN Architecture

李家元(Chia-Yuan Lee)

指導教授 ： 張明峰

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2016年)

摘要

軟體定義網路(SDN)是未來網路架構的趨勢，在其架構下能夠有效率的把控制層(Control Plane)與資料層(Data Plane)分離，控制器(Controller)具有網路管理權限。它採用集中控管的方式，統一下達指令給其管理的網路設備。流量工程(Traffic Engineering)亦是網路研究中重要的一環，能夠解決擁塞、提升產能、頻寬、容錯率、網路安全性等等的議題。線性規劃是解決最優化問題的一種方法，當目標函數和約束條件皆為線性，即可使用線性規劃找出最佳解。本研究取得流量矩陣與網路拓樸兩參數，使用線性規劃方法得出最佳多路徑遶送。為了避免大型線性規劃的計算所產生的誤差，我們採用分數來當作運算元，確保結果的正確性。得出最佳多路徑遶送後，利用線性規劃尋找多重最佳解的方式得出最佳多解，並且與目前網路狀態做比較，找出最少被重新遶送流量的解，成為目前網路狀態的最佳解，利用控制器將其套用在軟體定義網路上。研究結果顯示，我們的演算法確能夠有效的減少流量被重新遶送的量，另外若能夠成功預測未來網路的走勢，代表更能夠在長時間經過後，更有效的減少整體網路被重新遶送的量。

關鍵字

軟體定義網路 ； 線性規劃 ； 多路徑遶送

並列摘要

Software Define Network is the future trend of network architecture. SDN architecture separates the control plane and data plane. SDN controllers have network administrative rights to give instructions to SDN switches. With SDN centralized control, Traffic Engineering can be performed in a efficient manner. Traffic engineering can be used to avoid congestion, improve throughput, bandwidth, fault tolerance and security. Linear programming can be used to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Our research uses traffic matrix and network topology as inputs, and uses linear programming to find optimal multipath solutions. In addition, we also try to utilize multiple optimal solutions and find the best solution sequence that re-routes the least portion of traffic. We need accurate future traffic matrix to support our research, but it is very hard to measure. Our experiment results indicate that choosing from multiple solutions with future knowledge can reduce re-routing traffic. We will try to predict future traffic matrix and reduce measure error in future work.

並列關鍵字

SDN ； Linear Programming ； Multipath routing

參考文獻

[2] Ashwin Sridharan, Student Member, IEEE, Roch Guérin, Fellow, IEEE, and Christophe Diot, “Achieving Near-Optimal Traffic Engineering Solutions for Current OSPF/IS-IS Networks”, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 13, NO. 2, APRIL 2005

[3] George B. Dantzig and Philip Wolfe, “The Decomposition Algorithm for Linear Programs”, Econometrica, Vol. 29, No. 4, October 1961

[1] Sangman Cho, Theodore Elhourani, and Srinivasan [1] Ramasubramanian, “Independent Directed Acyclic Graphs for Resilient Multipath Routing”, IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 20, NO. 1, February 2012