在規則表有限的軟體定義網路中最大化服務品質

Maximizing Quality of Service with Rule Table Constraints in Software Defined Network

吳孟桓(Wu, Meng Huan)

指導教授 ： 蔡明哲

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

摘要

軟體定義網路(Software Defined Network)在近幾年已經成為骨幹網路及資料庫網路中新穎的網路解決方案，因為在軟體定義網路中會有一個中央控制中心可以改變每個資料流所流動的路徑進而達到自訂的網路目標。要改變每個資料流的路徑必須經由增加優先權較高的路由規則到路由器中，路由表一般來說是儲存在TCAM中，然而因為TCAM是非常昂貴的，因此在軟體定義網路中便因為這樣可以改變路徑的機制而有了新的網路資源限制:路由表大小。在這篇論文中我們同時考慮了每個使用者的服務品質，因此論文的目標則著重於在軟體定義網路的環境下最大化每個使用者的服務品質。綜觀上述講到的各點在這篇論文中我們提出了一個優化的問題，並且證明這是一個NP-hard的問題，隨後提出一個直覺的Heuristic以及做了一連串的實驗來證實我們演算法的效能。

關鍵字

軟體定義網路 ； 路由表大小限制 ； 服務品質

並列摘要

Software Defined Networks (SDNs) are becoming the leading technology behind many traffic engineering solutions, both for backbone and data-center networks, since it allows a central controller to manage the path of the flows according to specific objective. The central controller manage the path of the flows via additional assignment of rules in the rule table of the networking devices. Typically the rule table is stored in the ternary content addressable memory (TCAM). However, TCAM is expensive such that it is limited in the networking devices and would be the bottleneck of the network. In this thesis, we concentrate on solving the global network problem in the environments which the rule table size in forwarding devices is limited. Meanwhile, we consider the problem associated with the quality of service. We formulate this problem as an NP-hard optimization problem and propose a heuristic for it.

參考文獻

[4] R. Narayanan, S. Kotha, G. Lin, A. Khan, S. Rizvi, W. Javed, H. Khan, and S. A. Khayam, "Macroflows and microflows: Enabling rapid network innovation

[6] R. Cohen, L. Lewin-Eytan, J. S. Naor et al., "On the effect of forwarding table size on SDN network utilization," in INFOCOM, 2014 Proceedings IEEE. IEEE, 2014, pp. 1734-1742.

[8] Y. Kanizo, D. Hay, and I. Keslassy, "Palette: Distributing tables in software-defined networks," in INFOCOM, 2013 Proceedings IEEE. IEEE, 2013, pp. 545-549.

[10] R. Karp, "Reducibility among combinatorial problems," in Complexity of Computer Computations. Plenum Press, 1972, pp. 85-103

[11] R. Albert and A.L. Barabasi. "Statistical mechanics of complex networks." Reviews of Modern Physics, Vol. 74, pp. 47-97, 2002.