臺灣博碩士論文加值系統

隨著各種應用的發展，資料中心的效能越來越被重視，在資料中心的多路徑負載平衡方法正面臨著更高效能與更高效率的挑戰。目前使用最廣泛的負載平衡方法是等價多路徑路由，但此方法主要的問題是不會考慮壅塞的狀況，所以頻寬使用的效率往往非常差。為了解決這個問題，相繼有了CONGA與HULA等論文的提出。然而，CONGA有幾項問題，第一點是記憶體用量耗費太大，第二點是路徑壅塞的資訊不夠及時，第三點是實作在客製化晶片上費時又缺乏彈性；接著，HULA的提出解決了CONGA部分的問題，其實驗結果也顯示在平均流量完成時間上HULA比CONGA有更好的表現。不過儘管有進步的結果，HULA的做法同時也衍生出了幾個問題，第一點是HULA的每個交換機只選擇且僅記錄最佳路徑，這樣的決策方式容易讓最佳的路徑很快速地陷入壅塞，第二點是HULA透過送額外的探針來偵測壅塞，除了會浪費頻寬外，資訊的及時性也直接取決於送探針的頻率。若鏈結頻寬是有限的情況下，探針的頻率與資訊更新的超時設定會嚴重地影響HULA的效能，而導致結果很不穩定。本篇論文提出一個有權重的等價多路徑方法W-ECMP，旨在解決容易壅塞最佳路徑的問題，透過計算權重機率性地選擇路徑來避免快速阻塞一條路徑，再藉由P4 Inband Network Telemetry (INT)的概念將路徑壅塞資訊夾帶在正常流量上來取代送探針，除了讓頻寬使用較有效率外，資訊更新的及時性也會隨著網路的負載而提升，不必仰賴送探針的頻率。在這篇論文的實驗結果中，除了顯示了HULA的問題外，W-ECMP也在平均流量完成時間上相較於HULA有較好的效率表現。

As many kinds of applications developing, the performance of data center is getting more and more attention. Data centers everywhere face ongoing challenges for higher performance and greater efficiency. The most commonly load-balancing scheme used on data centers is equal-cost multi-path (ECMP). The major problem of ECMP is that it balances the traffic without considering the congestion. To overcome this problem, CONGA and HULA are proposed successively. Nevertheless, CONGA has the following problems. First, the cost of the memory usage is too large. Second, the congestion information is not real-time enough. Third, implementing in customized ASICs is time-consuming and lacking flexibility. Then, HULA is proposed to solve some problems of CONGA, and the result shows that HULA performs better than CONGA in average flow completion time (FCT). However, although HULA has improvement, there are some derivative problems from HULA. Each switch only selects and records the best path, which is easy to congest the best path, and HULA uses probes that wastes bandwidth and intensely influences the performance of HULA if the link bandwidth is limited. This thesis proposes a weighted ECMP (W-ECMP) scheme for solving the problem of HULA that is easy to congest the best path. W-ECMP chooses a path with a weighted probability to avoid congesting a path quickly, and encapsulates the path congestion information into the normal traffic according to the concept of Inband Network Telemetry (INT), which increases updating speed as the network loading increases. From experimental result, except showing the problems of HULA, W-ECMP gets the better performance than HULA does in average FCT.

中文摘要 i
Abstract ii
誌謝 iii
Contents iv
List of Figures vi
List of Tables vii
List of Symbols viii
Acronyms and Abbreviations viii
Notation viii
Chapter 1 Introduction 1
Chapter 2 Related Work 4
2.1 P4 4
2.1.1 Abstract Forwarding Model 6
2.1.2 Behavioral-Model 7
2.1.3 Inband Network Telemetry (INT) 8
2.2 Flowlet 8
2.3 CONGA and HULA 9
Chapter 3 System Architecture 11
3.1 Characteristics of W-ECMP 11
3.2 W-ECMP Header Format 13
3.3 Reverse Collection for Congestion 14
3.4 Flowlet Probabilistic Decision with Weight 16
3.5 W-ECMP Algorithm in P4 18
Chapter 4 Performance Evaluation 22
4.1 Testbed Setup 22
4.1.1 Software Tools and Hardware Configuration 22
4.1.2 Experiment Setting 24
4.2 Extreme Case 25
4.3 General Case 26
4.3.1 Observation 26
4.3.2 Analysis and Discussion 27
Chapter 5 Conclusions 31
References 32

[1] M. Al-Fares, A. Loukissas, and A. Vahdat, "A scalable, commodity data center network architecture." pp. 63-74.
[2] 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." pp. 51-62.
[3] M. Al-Fares, S. Radhakrishnan, B. Raghavan, N. Huang, and A. Vahdat, "Hedera: Dynamic Flow Scheduling for Data Center Networks." pp. 19-19.
[4] S. Jain, A. Kumar, S. Mandal, J. Ong, L. Poutievski, A. Singh, S. Venkata, J. Wanderer, J. Zhou, and M. Zhu, “B4: Experience with a globally-deployed software defined WAN,” ACM SIGCOMM Computer Communication Review, vol. 43, no. 4, pp. 3-14, 2013.
[5] M. Alizadeh, T. Edsall, S. Dharmapurikar, R. Vaidyanathan, K. Chu, A. Fingerhut, F. Matus, R. Pan, N. Yadav, and G. Varghese, "CONGA: Distributed congestion-aware load balancing for datacenters." pp. 503-514.
[6] N. Katta, M. Hira, C. Kim, A. Sivaraman, and J. Rexford, "Hula: Scalable load balancing using programmable data planes." p. 10.
[7] P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C. Schlesinger, D. Talayco, A. Vahdat, and G. Varghese, “P4: Programming protocol-independent packet processors,” ACM SIGCOMM Computer Communication Review, vol. 44, no. 3, pp. 87-95, 2014.
[8] N. Dukkipati, and N. McKeown, “Why flow-completion time is the right metric for congestion control,” ACM SIGCOMM Computer Communication Review, vol. 36, no. 1, pp. 59-62, 2006.
[9] "The P4 Language Specification, Version 1.0.4," https://p4lang.github.io/p4-spec/p4-14/v1.0.4/tex/p4.pdf, 2017.
[10] S. Kandula, D. Katabi, S. Sinha, and A. Berger, “Dynamic load balancing without packet reordering,” ACM SIGCOMM Computer Communication Review, vol. 37, no. 2, pp. 51-62, 2007.
[11] C. Kim, A. Sivaraman, N. Katta, A. Bas, A. Dixit, and L. J. Wobker, "In-band network telemetry via programmable dataplanes."
[12] J. Zhang, K. Xi, L. Zhang, and H. J. Chao, "Optimizing network performance using weighted multipath routing." pp. 1-7.
[13] J. Zhou, M. Tewari, M. Zhu, A. Kabbani, L. Poutievski, A. Singh, and A. Vahdat, "WCMP: Weighted cost multipathing for improved fairness in data centers." p. 5.
[14] "Mininet - An Instant Virtual Network on your Laptop (or other PC)," http://mininet.org, 2014.
[15] J. E. Jon Dugan, Jim Ferbuson, Andrew Gallatin, Mark Gates, Kevin Gibbs, Stephen Hemminger, Nathan Jones, Feng Qin, Gerrit Renker, Ajay Tirumala, Alex Warshavsky., "iPerf - The ultimate speed test tool for TCP, UDP and SCTP," https://iperf.fr/, 2016.
[16] A. Bas, "Behavioral-model - P4 software switch," https://github.com/p4lang/behavioral-model, 2017.
[17] "Open vSwitch," http://openvswitch.org/.
[18] "INT demo," https://github.com/p4lang/p4factory/tree/master/apps/int.
[19] "In‐band Network Telemetry (INT) spec," http://p4.org/wp-content/uploads/fixed/INT/INT-current-spec.pdf, 2016.
[20] M. Mahalingam, D. Dutt, K. Duda, P. Agarwal, L. Kreeger, T. Sridhar, M. Bursell, and C. Wright, Virtual extensible local area network (VXLAN): A framework for overlaying virtualized layer 2 networks over layer 3 networks, 2070-1721, 2014.
[21] Y. Iozzelli, L. Rizzo, and G. Lettieri, “Performance improvements on the P4 software switch,” 2016.
[22] H. T. Dang, H. Wang, T. Jepsen, G. Brebner, C. Kim, J. Rexford, R. Soulé, and H. Weatherspoon, "Whippersnapper: A P4 Language Benchmark Suite." pp. 95-101.