臺灣博碩士論文加值系統

隨著網路上的資料量越來越龐大，資料中心越來越普及。在資料中
心中兩個核心問題: 負載平衡與快速線路異常偵測也備受重視。負載平
衡是一個很重要的技術，用來處理動態、不可預測的交通需求量。一
般而言，負載平衡的目標是分配相等的交通量到多重路徑上。然而，
大多數的方法都受制於封包亂序或者無法及時回應。近年來，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.

中文摘要i
Abstract ii
致謝iii
Contents iv
List of Figures vi
List of Tables ix
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 9
4.1 Artificial Flowlet-based Splitting 9
4.2 Enqueue Scheme 11
4.3 Dequeue Scheme 12
4.4 Create New Artificial Flowlet 13
5 Congestion Detection 15
5.1 Leaf-To-Leaf Feedback 15
6 Practical Issue 17
6.1 Downlink Balancing 17
6.2 Uplink Balancing 18
7 Link Failure Detection 19
7.1 Symbol Definition 19
7.2 Leaf-To-Leaf Information 20
7.2.1 Packet Format 21
7.2.2 Congestion Table 21
7.2.3 Link Fault Detection 22
7.3 Threshold of Suspected Circumstances 27
8 Simulation 28
8.1 Simulation Environment 28
8.2 Parameter Choice 29
8.3 Comparison Result 30
8.3.1 Artificial Flowlet vsSpontaneous Flowlet 30
8.3.2 Flow Completion Time (FCT) 33
8.3.3 Oversubscription 33
8.4 Average Packet Traveling Time Between Leaf Switches 34
8.5 Error Detection Time Resolution 35
8.6 Improved our scheme 37
9 Conclusion 42
Bibliography 43

[1] Mohammad Al-Fares, Sivasankar Radhakrishnan, Barath Raghavan, Nelson Huang,
and Amin Vahdat. Hedera: Dynamic flow scheduling for data center networks. Proceedings
of the 7th USENIX Conference on Networked Systems Design and Implementation,
10:19–19, 2010.
[2] K Papagiannakit, Nina Taft, and Christophe Diot. Impact of flow dynamics on traffic
engineering design principles. INFOCOM 2004. Twenty-third AnnualJoint Conference
of the IEEE Computer and Communications Societies, 4:2295–2306, 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. Proceedings of the 2nd ACM SIGCOMM
Workshop on Internet measurment, pages 91–92, 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.
ACM SIGCOMM Computer Communication Review, 44(4):503–514, 2014.
[6] Costin Raiciu, Sebastien Barre, Christopher Pluntke, Adam Greenhalgh, Damon
Wischik, and Mark Handley. Improving datacenter performance and robustness with
43
multipath tcp. ACM SIGCOMM Computer Communication Review, 41(4):266–277,
2011.
[7] Hong Xu and Baochun Li. Repflow: Minimizing flow completion times with replicated
flows in data centers. IEEE INFOCOM 2014-IEEE Conference on Computer
Communications, pages 1581–1589, 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. Proceedings of
the Ninth ACM Conference on Emerging Networking Experiments and Technologies,
pages 49–60, 2013.
[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. volume 43, pages 435–446, 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.
44