基於軟體定義網路之資料中心多路徑路由機制

Multipath Routing in SDN-based Data Center Networks

雷逸志(Yi-Chih Lei)

指導教授 ： 王國禎

國立交通大學/資訊學院/網路工程研究所/碩士(2014年)

https://doi.org/10.6842/NCTU.2014.00949

摘要

軟體定義網路Software-Defined Networking(SDN)架構，分離了交換器資料層與控制層，使網路管理者能掌握可用網路資源的全局狀況，並透過中央控制器管理網路資源。越來越多的資料中心網路Data Center Networks(DCNs)使用能夠提供每一對用戶端多路徑路由能力的多樹根網路拓樸。傳統的單一路徑路由無法充分利用資料中心網路所提供的網路資源，現有的多路徑路由演算法也無法以全局的角度來挑選多條路由路徑，更無法根據當下的網路資源來決定適當的路徑數量，這對路徑品質、建立多條路徑的成本以及分配資料流到多條路徑的複雜度皆會產生影響。我們在基於軟體定義網路的資料中心網路中提出了一個具資料流適應性的多路徑路由演算法adaptive worst-fit multipath routing (AWMR)。AWMR能夠根據當下可用的網路資源以及當下新產生的資料流所需頻寬挑選出多條路徑，並決定各資料流所需的路徑數量，而非對每一個資料流皆提供統一的路徑數量。AWMR主要有兩個階段：第一個階段負責找出來源用戶端與目的地用戶端之間的可能路徑集合，並且算出此集合之剩餘可用頻寬；第二個階段則是基於widest disjoint path策略，根據當下新產生的資料流所需頻寬來挑選出具有最大剩餘頻寬的多條路徑。
因為AWMR能夠有效地最小化多路徑路由之路徑數量，所以上述所提之建立多條路徑的成本以及分配多條路徑之間資料流的複雜度皆能有效減少。除此之外，相較於另外一篇在挑選路徑上僅採用本地視角的相關文獻：使用深度優先搜尋與挑選最大剩餘頻寬連結演算法(DFS+worst fit link)， AWMR除了使用全局角度來挑選多條路徑，還同時避免了路徑之間共用瓶頸連結的問題，使得AWMR能夠得到較低的平均延遲時間。實驗結果證明，相對於DFS+worst fit link演算法，我們所提出具適應性的最大剩餘頻寬多路徑路由演算法AWMR，能夠降低52.67%的平均延遲時間，並且提升17.57%的吞吐量與5.95%的封包抵達率。因此，AWMR更能有效利用使用多樹根拓樸之基於軟體定義網路的資料中心所提供之多路徑路由能力。

關鍵字

資料中心網路 ； 多路徑路由 ； 軟體定義網路

並列摘要

Software-Defined Networking (SDN), which decouples data and control planes, allows network administrators to have a global view of available network resources and to directly manage the network resources with a central controller. More and more data center networks (DCNs) use multi-rooted network topologies which offer multipath capability for each host pair. Traditional single path routing cannot fully utilize the network resources that DCNs provide. Existing multipath routing algorithms cannot select multiple paths in a global view and cannot determine a proper number of paths according to available network resources, which have impacts on path quality, cost of constructing multiple paths. We propose an SDN-based adaptive worst-fit multipath routing (AWMR) algorithm for DCNs which can select multiple routing paths and determine the number of paths for a new-coming flow according to the available network resources and the demanded bandwidth of the new-coming flow, instead of using a fixed number of routing paths for each flow. The proposed AWMR is composed of two stages. The first stage of the proposed AWMR finds an initial routing path set that includes paths whose lengths are the shortest between source and destination hosts, and computes available bandwidth of such a path set. The second stage of the proposed AWMR, which utilize an improved widest disjoint path (iwdp) scheme, then selects the worst-fit paths according to the demanded bandwidth of the new-coming flow. Since the proposed AWMR minimizes the number of routing paths used efficiently, the cost of constructing multiple paths can be decreased. Since the proposed AWMR selects multiple paths in a global view rather than in a local view of DFS+worst fit link, which is a representative related work, the proposed AWMR can get smaller average end-to-end delay due to avoiding the shared bottleneck link problem among multiple paths. Simulation results have shown that the average end-to-end delay of the proposed AWMR is 52.67% better than that of DFS+worst-fit link. The average throughput per flow of the proposed AWMR is 17.57% better than that of DFS+worst-fit link. The average packet delivery ratio of the proposed AWMR is 5.95% better than that of DFS+worst-fit link. Therefore, the proposed AWMR can better fully utilize the multipath capability of multi-rooted topologies in SDN-based DCNs.

並列關鍵字

data center networks ； multipath routing ； software-defined networking

參考文獻

[3] S. Fang, Y. Yu, C. H. Foh, and K. M. M. Aung, "A loss-free multipathing solution for data center network using software-defined networking approach," in Proc. IEEE Asia-Pacific Magnetic Recording Conference, Oct. 2012, pp. 1-8.

[5] M. Dasgupta, and G. P. Biswas, "Design of multipath data routing algorithm based on network reliability," in Proc. Computers & Electrical Engineering, Nov. 2012, pp. 1433-1443.

[6] T. Cheocherngngarn, H. Jin, J. Andrian, D. Pan, and J. Liu, "Depth-first worst-fit search based multipath routing for data center networks," in Proc. IEEE Global Telecommunications Conf., Dec. 2012, pp. 2821-2826.

[10] C. Cheng, R. Riley, and S. P. R. Kumar, "A loop-free extended Bellman-Ford routing protocol without bouncing effect," in Proc. ACM SIGCOMM Computer Communication Review, Vol. 19, No. 4, Sep. 1989, pp. 224-236.

[1] R. N. Mysore, A. Pamboris, N. Farrington, N. Huang, P. Miri, S. Rad-hakrishnan, V. Subramanya, and A. Vahdat, "Portland: a scalable fault-tolerant layer 2 data center network fabric," in Proc. ACM SIGCOMM, Aug. 2009, pp. 39-50.