極端資料流在雲端資料中心之路由方法研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：91

、訪客IP：3.144.90.108

姓名

林佳叡(Chia-Ray Lin) 查詢紙本館藏

畢業系所

通訊工程學系

論文名稱

極端資料流在雲端資料中心之路由方法研究
(Study of Routing Algorithm for Extreme Types of Flows in Cloud Data Center)

相關論文

★ 應用MSPP至DWDM都會光纖網路的設計	★ 光網路與WiMAX整合架構研究及其簡化雛型實驗
★ 以Linux系統為基礎之NAT效能優化研究及其實作	★ 光波長劃分多工網路之路徑保護機制研究
★ 標籤交換網路下具有服務品質路由安排之研究	★ 以訊務相關性為基礎的整合性服務可調整QoS排程器之研究
★ 以群體播送支援IPv6環境下移動式網路連結更新之研究	★ 無線區域網路資源動態分配之效能研究
★ 在微觀移動環境下有效資源保留之路徑管理研究	★ 無線網路交握程序之預先認證方法分析與比較
★ 無線區域網路虛擬允入控制之研究	★ IPv6環境下移動網路之連結更新程序及其效能之研究
★ 具有限數量波長轉換節點的分波多工網路之群播波長分配與容量計算研究	★ 階層化行動式IPv6移動錨點選擇機制研究
★ 具高能量移動節點之叢集式感測網路效能研究	★ 預先註冊之快速換手階層化行動式IPv6研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

架設雲端資料中心的目的就是要提供多項的服務，而這些服務未來會使用越來越多
的網路資源。因此要如何有效的分配在雲端資料中心的網路資源，變成一項重要的問題。
以往最常被使用的 Dijkstra’s 演算法，是使用在普遍的網路拓樸，但是雲端資料中心的
拓樸以及資料流的特性與普遍的網路有別，因此需要為了雲端資料中心設計一個路徑演
算法來解決頻寬的分配。
我們設計出了 pairing 演算法，將以往大部分是從一個節點開始尋找路徑，變成從
兩個節點出發一起尋找。由於雲端資料中心為了能夠讓大量的伺服器之間快速且可靠的
傳輸訊息，因此雲端資料中心的網路拓樸都有很多條路徑而且是被經過設計的。根據這
些設計的規律，從兩個節點一起尋找路徑不但不用擔心在尋找的過程中，這兩個節點可
能永遠不會連結起來而成為一條真正的路徑，而且還可以同時根據兩個節點所看到的網
路狀況，尋找真正適合的路徑。除了路徑演算法的部分，我們還提出了兩種分流的方式，
讓資料流有更多的機會使用更多的頻寬，減少資料流被擋住的可能性。
由模擬結果可知，本論文提出之方法，可以有效的減少資料流被完全阻擋的比例，
而且滿足率超過 80% 但不包括完全滿足的資料流比例也比較多。這是因為我們有效的
分配瓶頸的鏈結。同時也可以看到，當網路越壅塞時，改善的幅度是越來越明顯。因此，
我們有效的利用網路資源，讓比較多的資料流能夠建立連線，也讓比較多的資料流能夠
有更高的滿足率。

摘要(英)

The purpose of deploying cloud data center is to provide different kinds of services.
However, these services would require more and more network resources in the future.
Therefore, the efficiency of allocating network resources in cloud data center has become an
important issue. Dijkstra’s algorithm is one of the most used routing algorithm for general
networks. But the topology and traffic pattern in cloud data center are different from the
general networks, so it’s essential to design a routing algorithm for cloud data center to
provide a solution for allocating the network resources.
We designed the pairing algorithm, which searches a path from two nodes instead of
one. In order to transfer data among massive servers with guaranteed speed and reliability, the
network topology is especially designed with multiple path. It’s able to search a path
according to the pattern of the topology from two nodes and don’t need to concern that these
two nodes will not be able to meet to provide the path. This makes pairing algorithm allowed
to discover a path from two aspects simultaneously as well. Besides routing algorithm, we
also proposed two method of splitting flows, which allows the flows to use more network
resources and reduces the chance of a flow to be blocked.
According to the simulation result, the pairing algorithm and split with allocation
constraint is able to reduce the ratio of complete blocking effectively. Also, the ratio of flows
satisfied over 80% without fully satisfied is higher. Therefore, we allocate the network
resource more efficiently, not only more flows can be established, but also more flows
achieve over 80% of satisfaction rate.

關鍵字(中)

★ 雲端資料中心
★ 路徑演算法

關鍵字(英)

論文目次

中文摘要 ................................................................................................................................. i
Abstract ................................................................................................................................ v
致謝 ............................................................................................................................... vi
Table of Content ....................................................................................................................... vii
List of Figures ........................................................................................................................... ix
List of Tables ............................................................................................................................. xi
Chapter 1 Introduction ............................................................................................................ 1
1.1 Background ............................................................................................................................. 1
1.2 Motivation ............................................................................................................................... 1
1.3 Chapter Outline ....................................................................................................................... 3
Chapter 2 Research Backgrounds ........................................................................................... 4
2.1 Cloud Data Center Networks .................................................................................................. 4
2.2 SDN......................................................................................................................................... 6
2.3 Related Works ......................................................................................................................... 9
Chapter 3 Proposed Method ................................................................................................. 15
3.1 System Architecture .............................................................................................................. 15
3.2 Classification ......................................................................................................................... 16
3.3 Pairing Algorithm ................................................................................................................. 18
3.4 Splitting Methods .................................................................................................................. 23
Chapter 4 Simulation and Results ........................................................................................ 27
4.1 Simulation Environment ....................................................................................................... 27
4.2 Mix Mice and Elephant Flows .............................................................................................. 28
4.3 Elephant Flow Simulation Environment ............................................................................... 30
4.3.1 Case 1: Normal Scenario ................................................................................................... 30
4.3.1 Case 2: Hot-pod Scenario ................................................................................................. 38

Chapter 5 Conclusions and Future Works ............................................................................ 44
References .............................................................................................................................. 46

參考文獻

[1] S. Sen, D. Shue, S. Ihm, and M. J. Freedman, “Scalable, optimal flow routing in
datacenters via local link balancing”, in Proc. ACM CoNEXT, Santa Barbara, CA, USA,
pp. 151–162, 2013.
[2] M. Al-Fares, A. Loukissas, and A. Vahdat, “A Scalable, Commodity Data Center Network
Architecture”, in Proc. ACM Sigcomm, pp. 63–74, 2008.
[3] W. Xia, P. Zhao, Y. Wen, and H. Xie, “A survey on data center networking (DCN):
Infrastructure and operations”, IEEE Commun. Surveys Tuts., vol. 19, no. 1, pp. 640–656,
1st Quart., 2017.
[4] A. Greenberg, J. Hamilton, and N.Jain, "VL2: A scalable and flexible data center network",
in Proc. ACM SIGCOMM Conf. Data Commun. (SIGCOMM), pp. 51-62, 2009.
[5] A. Singla, C.-Y. Hong, L. Popa, and P. B. Godfrey, "Jellyfish: Networking data centers
randomly”, in Proc. 9th USENIX Conf. Netw. Syst. Design Implement. (NSDI), pp. 225-
238, 2012.
[6] C. Guo, H.Wu, K.Tan, L.Shi, Y.Zhang, and S.Lu, "DCell: A scalable and fault-tolerant
network structure for data centers", in Proc. ACM SIGCOMM Conf. Data Commun.
(SIGCOMM), pp. 75-86, 2008.
[7] C. Guo, G.Lu, D.Li, H.Wu, X.Zhang, and Y.Shi, "BCube: A high performance server-
centric network architecture for modular data centers", in Proc. ACM SIGCOMM Conf.
Data Commun. (SIGCOMM), pp. 63-74, 2009.
[8] T. Benson, A. Akella, and D. A. Maltz, “Network traffic characteristics of data centers in
the wild”, Internet Measurement Conf. (IMC), pp. 267–280, 2010.
[9] (Oct. 2018). ONF SDN. [Online]. Available: https://www.opennetworking.org/sdn-
definition/
[10] OpenFlow Switch Specification v1.5.1
47
[11] S. Y. Wang, H. W. Chiu, C. L. Chou, "Comparisons of SDN OpenFlow Controllers over
EstiNet: Ryu vs. NOX", The International Symposium on Advances in Software Defined
Networks, pp. 1-6, 2015.
[12] Hopps, C. Analysis of an Equal-Cost Multi-Path Algorithm. RFC 2992, IETF, 2000.
[13] M. Al-Fares, S. Radhakrishnan, B. Raghavan, N. Huang, and A. Vahdat,”Hedera:
Dynamic flow scheduling for data center networks”, in Proc. USENIX NSDI, San Jose,
CA, USA, pp. 19, 2010.
[14] W. Wang et al., “Freeway: Adaptively isolating the elephant and mice flows on different
transmission paths”, in Proc. IEEE ICNP, Raleigh, NC, USA, pp. 362–367, 2014.
[15] H. Xu and B. Li, “RepFlow: Minimizing flow completion times with replicated flows in
data centers”, in Proc. IEEE INFOCOM, Toronto, ON, Canada, pp. 1581–1589, 2014.
[16] D. Zats, T. Das, P. Mohan, D. Borthakur, and R. Katz, “DeTail: Reducing the flow
completion time tail in datacenter networks”, in Proc. ACM SIGCOMM, Helsinki, Finland,
pp. 139–150, 2012.

指導教授

陳彥文

審核日期

2019-1-17

推文