應用於資料中心之負載平衡演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：11

、訪客IP：3.145.125.13

姓名

郭哲岳(Che-Yueh Kuo) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

應用於資料中心之負載平衡演算法
(Intra Data Center Path Load Balancing)

相關論文

★ 基於OP-TEE的可信應用程式軟體生態系統	★ SeFence: 基於安全感測的可信任周邊存取控制
★ 高解析度二維地理影像的三維建模：旋轉變換投影與傳統方法的比較研究	★ 在低軌道衛星無線通訊中的CSI預測方法
★ 為多流量低軌道衛星系統提出的動態換手策略	★ 基於Trustzone的智慧型設備語音隱私保護系統
★ 一種減輕LEO衛星網路干擾的方案	★ TruzGPS:基於TrustZone的位置隱私權保護系統
★ 衛星地面整合網路之隨機接入前導訊號設計與偵測	★ SatPolicy: 基於Trustzone的衛星政策執行系統
★ TruzMalloc: 基於TrustZone 的隱私資料保護系統	★ 衛星地面網路中基於物理層安全的CSI保護方法
★ 低軌道衛星地面整合網路之安全非正交多重存取傳輸	★ 低軌道衛星地面網路中的DRX機制設計
★ 衛星地面整合網路之基於集合系統的前導訊號設計	★ 基於省電的低軌衛星網路路由演算法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

在數據中心中，負載平衡是一個很重要的技術，用來處理動態與不
可預測的交通需求量。一般而言，負載平衡的目標是分配相等的交通
量到多重路徑上。然而，大多數的方法都受制於封包亂序或者快速回
應。近年來，Flare 引進基於flowlet 的分流方法，它達到快速回應且不
造成封包亂序。但是，資料中心內的高頻寬環境造成產生flowlet 的間
隔減少。除此之外，分流的細膩度會隨著交通量變大而變粗，在此篇
論文中，我們提出一個人工flowlet 為基底的負載平衡演算法，其能保
持好的分流細膩度且避免封包亂序，在實驗中顯示，我們的方法在流
的完成時間好20%。

摘要(英)

Load balancing is an important technique to cope with dynamic and unpredictable
traffic demands in data center networks. In general, load balancing
schemes aim to split traffics evenly among multiple paths. However, most
existing approaches either suffers from packet reordering (which may confuse
TCP congestion control) or fail to quick response (i.e., coarse slicing
granularity). Recently, FLARE introduced a burst (called flowlet) based traffic
splitting, which attains responsiveness without causing packet reordering.
However, the very high bandwidth of internal datacenter flows suggests that
the gaps needed for flowlets may be rare. Besides, in Flare, splitting granularity
increases (i.e., coarse granularity) when flow size increases. In this
paper, we propose an artificial flowlet-based load balancing algorithm which
can maintain fine-granularity (even in large flows) and can also avoid packet
reordering. Our scheme has at least 20% improvement in flow completion
time under the same incidence of packet reordering.

關鍵字(中)

★ 資料中心架構
★ 負載平衡
★ 分散式

關鍵字(英)

★ Datacenter fabric
★ Load balancing
★ Distributed

論文目次

中文摘要i
Abstract ii
致謝iii
Contents iv
List of Figures vi
List of Tables viii
1 Introduction 1
2 Related work and Preliminary 4
2.1 Flow-based Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Packet-based Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Sub-Flow-based Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Problem Statement 7
3.1 Traffic Splitting Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Environment Description . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4 Design 10
4.1 Artificial Flowlet-based Splitting . . . . . . . . . . . . . . . . . . . . . . 10
4.2 Slot-based Dequeue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
iv
4.3 Enqueue Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5 Practical Issue 16
5.1 Dequeue Ratio and Queue Occupancy . . . . . . . . . . . . . . . . . . . 16
5.2 Slot Boundary and Packet Size . . . . . . . . . . . . . . . . . . . . . . . 17
6 Simulation 19
6.1 Simulation Environment . . . . . . . . . . . . . . . . . . . . . . . . . . 19
6.2 Parameter Choice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
6.3 Comparison Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
6.3.1 Artificial Flowlet vs. Spontaneous Flowlet . . . . . . . . . . . . 21
6.3.2 Load Balancing Efficiency . . . . . . . . . . . . . . . . . . . . . 22
6.3.3 Reordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6.3.4 Flow Completion Time (FCT) . . . . . . . . . . . . . . . . . . . 24
6.3.5 Ovsersubscription . . . . . . . . . . . . . . . . . . . . . . . . . 24
7 Conclusion 27
Bibliography 28

參考文獻

[1] Mohammad Al-Fares, Sivasankar Radhakrishnan, Barath Raghavan, Nelson Huang,
and Amin Vahdat. Hedera: Dynamic flow scheduling for data center networks. In
Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation,
NSDI’10, pages 19–19, Berkeley, CA, USA, 2010. USENIX Association.
[2] K Papagiannakit, Nina Taft, and Christophe Diot. Impact of flow dynamics on traffic
engineering design principles. In INFOCOM 2004. Twenty-third AnnualJoint
Conference of the IEEE Computer and Communications Societies, volume 4, pages
2295–2306. IEEE, 2004.
[3] Matthew Roughan, Albert Greenberg, Charles Kalmanek, Michael Rumsewicz, Jennifer
Yates, and Yin Zhang. Experience in measuring backbone traffic variability:
Models, metrics, measurements and meaning. In Proceedings of the 2nd ACM SIGCOMM
Workshop on Internet measurment, pages 91–92. ACM, 2002.
[4] Srikanth Kandula, Dina Katabi, Shantanu Sinha, and Arthur Berger. Dynamic load
balancing without packet reordering. ACM SIGCOMM Computer Communication
Review, 37(2):51–62, 2007.
[5] Mohammad Alizadeh, Tom Edsall, Sarang Dharmapurikar, Ramanan Vaidyanathan,
Kevin Chu, Andy Fingerhut, Francis Matus, Rong Pan, Navindra Yadav, George
Varghese, et al. Conga: Distributed congestion-aware load balancing for datacenters.
In ACM SIGCOMM Computer Communication Review, volume 44, pages 503–514.
ACM, 2014.

[6] Costin Raiciu, Sebastien Barre, Christopher Pluntke, Adam Greenhalgh, Damon
Wischik, and Mark Handley. Improving datacenter performance and robustness with
multipath tcp. In ACM SIGCOMM Computer Communication Review, volume 41,
pages 266–277. ACM, 2011.
[7] Hong Xu and Baochun Li. Repflow: Minimizing flow completion times with replicated
flows in data centers. In IEEE INFOCOM 2014-IEEE Conference on Computer
Communications, pages 1581–1589. IEEE, 2014.
[8] David Zats, Tathagata Das, Prashanth Mohan, Dhruba Borthakur, and Randy Katz.
Detail: reducing the flow completion time tail in datacenter networks. ACM SIGCOMM
Computer Communication Review, 42(4):139–150, 2012.
[9] Jiaxin Cao, Rui Xia, Pengkun Yang, Chuanxiong Guo, Guohan Lu, Lihua Yuan,
Yixin Zheng, Haitao Wu, Yongqiang Xiong, and Dave Maltz. Per-packet loadbalanced,
low-latency routing for clos-based data center networks. In Proceedings of
the Ninth ACM Conference on Emerging Networking Experiments and Technologies,
CoNEXT ’13, pages 49–60, New York, NY, USA, 2013. ACM.
[10] Stanislav Rost and Hari Balakrishnan. Rate-aware splitting of aggregate traffic.
Technical report, Technical report, MIT, 2003.
[11] Mohammad Alizadeh, Shuang Yang, Milad Sharif, Sachin Katti, Nick McKeown,
Balaji Prabhakar, and Scott Shenker. pfabric: Minimal near-optimal datacenter
transport. In ACM SIGCOMM Computer Communication Review, volume 43, pages
435–446. ACM, 2013.
[12] Chi-Yao Hong, Matthew Caesar, and P Godfrey. Finishing flows quickly with preemptive
scheduling. ACM SIGCOMM Computer Communication Review, 42(4):
127–138, 2012.

指導教授

張貴雲(Guey-Yun Chang)

審核日期

2016-8-2

推文