一種新穎的資料中心拓樸

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：91

、訪客IP：18.221.139.146

姓名

戴曉琪(Hsiao-Chi Tai) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

一種新穎的資料中心拓樸
(A Novel Data Center Network Topology)

相關論文

★ 基於OP-TEE的可信應用程式軟體生態系統	★ 在低軌道衛星無線通訊中的CSI預測方法
★ 為多流量低軌道衛星系統提出的動態換手策略	★ 基於Trustzone的智慧型設備語音隱私保護系統
★ 一種減輕LEO衛星網路干擾的方案	★ TruzGPS:基於TrustZone的位置隱私權保護系統
★ 衛星地面整合網路之隨機接入前導訊號設計與偵測	★ SatPolicy: 基於Trustzone的衛星政策執行系統
★ TruzMalloc: 基於TrustZone 的隱私資料保護系統	★ 衛星地面網路中基於物理層安全的CSI保護方法
★ 低軌道衛星地面整合網路之安全非正交多重存取傳輸	★ 低軌道衛星地面網路中的DRX機制設計
★ 衛星地面整合網路之基於集合系統的前導訊號設計	★ 基於省電的低軌衛星網路路由演算法
★ 衛星上可重組化計算之安全FPGA動態部分可重組架構	★ 衛星網路之基於空間多樣性的前導訊號設計

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

大規模資料中心實現了雲計算的新時代，並提供核心基礎架構，以
滿足企業信息技術需求和基於雲的服務的計算和存儲需求。為了支持
不斷增長的雲計算需求，當今資料中心的服務器數量呈指數級增長，
這導致設計高效且經濟高效的資料中心網絡面臨巨大挑戰。網絡結構
是支配整個資料中心性能的關鍵因素。互連拓撲很大程度上決定了資
料傳輸的關鍵性能因素，例如: 資料中心的流完成時間。其中網絡延
遲，可擴展性和可靠性是資料中心性能的三個關鍵指標。影響延遲的
主要原因是傳輸延遲，較低的延遲可以減少傳輸時間，這是通過減少
傳輸路徑來實現的。可擴展性允許大規模快速構建並使用更少的連接
來降低總體成本。可靠性是當錯誤發生時，整個拓撲必須有備份路徑
來完成傳輸，也就是容錯能力。我們的目標是設計拓撲以實現上述三
個標準並提高拓撲的吞吐量。
在本文中，我們設計了一個混合拓撲，稱為 DBS，它結合了 De Bruijn 圖和 Sunlet 圖。DBS 可以構建低直徑的資料中心，並在不同的工作負載下提供低延遲。在路由中，我們結合了兩種經典路由方法 ECMP 和 VLB 來提高吞吐量。

摘要(英)

Large-scale data centers enable the new era of cloud computing and provide the core infrastructure to meet the computing and storage requirements for both enterprise information technology needs and cloud-based services. To support the ever-growing cloud computing needs, the number of servers in today′s data centers are increasing exponentially, which in turn leads to enormous challenges in designing an efficient and cost-effective data center network. The topological properties of a networking structure are critical factors that dominate the performance of the entire data center. Network latency, scalability and reliability are three key metrics of data center performance. Lower latency can reduce the time of transmission, which is by reducing transmossion path (diameter). The scalability allow to build rapidly at scale and use less ports (degree) to reduce overall costs. The reliability is when the error occurs, the entire topology must have a backup path to complete the transmission. We aim to design a topology to achieve the above three criteria and to improve the throughput of our topology.

In this paper, we design a hybrid topology, called DBS, which combine De Bruijn graph and Sunlet graph. DBS enables constructing low diameter and highly resilient datacenter and offer low latency under different workload. In routing, we combine two classic routing method, ECMP and VLB to improve our throughput.

關鍵字(中)

★ 資料中心
★ 拓樸
★ De Bruijn 圖

關鍵字(英)

★ Data center
★ Topology
★ De Bruijn graph

論文目次

Contents
中文摘要 i
Abstract ii
致謝 iii
Contents iv
List of Figures vi
List of Tables viii
1 Introduction 1
2 Related work and Preliminary 5
2.1 Related work . . . . . . . . . . . . . . 5
2.1.1 Types of high-radix topologies . . . . . . . . . . . . . . . . . . . 6
2.2 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3 Network topology 17
3.1 Global Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Local Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3 Node Labelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4 Performance Analysis 22
4.1 Path Latency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
iv
4.2 Fault Tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3 Expandability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5 Simulation 26
5.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.2 Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2.1 ECMP is Enough? . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.2.2 VLB is Enough? . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2.3 Hybrid Routing - ECMP-VLB . . . . . . . . . . . . . . . . . . . 30
5.3 Communication Pairs of Distribution. . . . . . . . . . . . . . . . . . . . 32
5.4 All-to-All Traffic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
5.5 ProjecToR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6 Conclusion and Future work 38
Bibliography 39

參考文獻

Bibliography
[1] M. Al-Fares, A. Loukissas, and A. Vahdat, “A scalable,commodity data center network architecture,” ACM SIGCOMM, vol. 38, 2008.
[2] L. Tripathy, D. Tripathy, and C. Tripathy, “Fault tolerance in interconnection
network-a survey,” Applied Sciences, Engineering and Technology, 2015.
[3] J. Kim, W. J. Dally, B. Towles1, and A. K. Gupta, “Microarchitecture of a high-radix
router.” In Proc. of the International Symposium on Computer Architecture (ISCA),
2005.
[4] W. J. Dally, “Performance analysis of k-ary n-cube interconnection networks,” IEEE
Transactions on Computers, vol. 39, 1990.
[5] D. Abts, A. Bataine, S. Scott, G. Faanes, J. Schwarzmeier, E. Lundberg, T. Johnson,
M. Bye, and G. Schwoerer, “The cray blackwidow: A highly scalable vector multiprocessor,” In Proceedings of the International Conference for High Performance
Computing, Networking, Storage, and Analysis., 2007.
[6] S. Scott, D. Abts, J. Kim, and W. J. Dally, “The blackwidow high-radix clos network,” In Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis, 2006.
[7] M. Besta and T. Hoefler, “Slim fly: A cost effective low-diameter network topology,”
ACM SIGCOMM, pp. 345–359, 2014.
[8] R. Barriuso and A. Knies, “108-port infiniband fdr switchx switch platform hardware
user manual,” 2014.
[9] J. H. Ahn, N. Binkert, A. Davis, M. McLaren, and R. S. Schreiber, “Hyperx: Topology, routing, and packaging of efficient large-scale networks,” Proceedings of the
Conference on High Performance Computing Networking, Storage and Analysis,
2009.
[10] A. Singla, C. Y. Hong, L. Popa, and P. B. Godfrey, “Jellyfish: Networking data
centers randomly,” In Proc. of the 9th USENIX conference on Networked Systems
Design and Implementation, pp. 597–598, 2012.
[11] S. A. Jyothi, A. Singla, P. B. Godfrey, and A. Kolla, “Measuring throughput of data
center network topologies,” Special Interest Group for the computer systems performance evaluation community, pp. 597–598, 2014.
[12] A. Valadarsky, G. Shahaf, M. Dinitz, and M. Schapira, “Xpander: Towards optimalperformance datacenters,” International Conference on emerging Networking Experiments and Technologies., 2016.
[13] N. G. D. Bruijn, “A combinatorial problem,” Technical Report, 1946.
[14] W. J. Dally, “Performance analysis of k-ary n-cube interconnection networks,” IEEE
Transactions on Computers, pp. 775–785, 1990.
[15] A. Agarwal, “Limits on interconnection network performance,” IEEE Trans. Parallel Distribution System, pp. 398–412, 1991.
[16] S. A. Ghozati and H. C. Wasserman, “The k-ary n-cube network: modeling, topological properties and routing strategies,” IEEE Computers & Electrical Engineering,
vol. 25, pp. 155–168, 1999.
[17] J. Kim, W. J. Dally, and D. Abts, “Flattened butterfly : A cost-efficient topology for
high-radix networks,” International Symposium on Computer Architecture, 2007.
[18] J. Kim, W. J. Dally, S. Scott, and D. Abts, “Technology-driven, highly-scalable dragonfly topology,” International Symposium on Computer Architecture, 2008.
[19] C. Clos, “A study of non-blocking switching networks,” The Bell System technical
Journal, 1953.
[20] L. N. Bhuyan and D. P. Agrawal, “Generalized hypercube and hyperbus structures
for a computer network,” IEEE Transactioin Computer, 1984.
[21] B. D. McKay, M. Miller, and J. Siran, “A note on large graphs of diameter two and
given maximum degree,” Journal of Combinatorial Theory Series B, 1998.
[22] M. Miller and J. Siran., “Moore graphs and beyond: A survey of the degree/diameter
problem,” Electronic Journal of Combinatorics, 2005.
[23] P. R. Hafner, “Geometric realisation of the graphs of mckay miller siran,” Journal of
Combinatorial Theory, 2004.
[24] Y. BILU and N. Linial, “Lifts, discrepancy and nearly optimal spectral gap,” Combinatorica, 2006.
[25] “Facebook data center,” 2014, https://code.fb.com/production-engineering/
introducing-data-center-fabric-the-next-generation-facebook-data-centernetwork/.
[26] W.D.Wallis, Magic Graphs. Birkhauser Basel, 2000.
[27] “Netbench,” 2017, http://merlin.fit.vutbr.cz/ant/netbench/index.html.
[28] R. Zhang-Shen, “Valiant load-balancing: Building networks that can support all traffic matrices,” Algorithms for Next Generation Networks, 2010.
[29] M. Al-Fares, A. Loukissas, and A. Vahdat, “A scalable, commodity data center network architecture.” ACM SIGCOMM, 2008.
[30] M. Alizadeh, S. Yang, M. Sharif, S. Katti, N. McKeown, and B. Prabhakar, “pfabric:
Minimal near-optimal datacenter transport,” ACM SIGCOMM, 2013.
[31] M. Alizadeh, A. Kabbani, T. Edsall, B. Prabhakar, A. Vahdat, and M. Yasuda, “Less
is more: Trading a little bandwidth for ultra-low latency in the data center,” USENIX
NSDI, 2012.
[32] D. Wischik, C. Raiciu, A. Greenhalgh, and M. Handley, “Design, implementation
and evaluation of congestion control for multipath tcp.” USENIX NSDI, 2011.
[33] J. Yen, “Finding the k shortest loopless paths in a network,” Management Science,
no. 45, 1971.
[34] S. Kandula, D. Katabi, S. Sinha, and A. Berger, “Flare: Responsive load balancing
without packet reordering.” Computer Communication Review, 2007.
[35] A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. A. Maltz,
P. Patel, and S. Sengupta, “Vl2: A scalable and flexible data center network,” Communications of the ACM, 2009.
[36] T. Benson, A. Akella, and D. A. Maltz, “Network traffic characteristics of data centers in the wild,” ACM SIGCOMM, 2010.
[37] A. Roy, J. B. Hongyi Zeng, G. Porter, and A. C. Snoeren, “Inside the social network’s
(datacenter) network,” ACM SIGCOMM, 2015.
[38] M. Ghodbadi, R. Mahajan, A. Phanishayee, H. Rastegarfar, P.-A. Blanche, M. Glick,
D. Kilper, J. Kulkarni, G. Ranade, and N. Devanur, “Projector : Agile reconfigurable
datacenter interconnect,” ACM SIGCOMM, 2016.

指導教授

張貴雲(Guey-Yun Chang)

審核日期

2019-7-26

推文