通過保護路由實現網絡擁塞的負載平衡研究

A Study of Load Balancing for Network Congestion through Protection Routings

陳冠宇(Guan-Yu Chen)

指導教授 ： 張肇明

國立臺北商業大學/管理學院/資訊與決策科學研究所/碩士(2021年)

摘要

網路擁塞的負載平衡能夠使資料中心網路的流量平均分配在所有的傳輸路徑之間，使得網路可以以較低的平均端到端傳輸延遲來傳輸更多的數據。保護路由是一種容錯路由，當單個傳輸路徑或節點發生故障時，它可以調用無環的備用路徑進行數據轉發。在本論文中，我們提出了一種新的想法即當網路擁塞達到一定門檻值時，將採用保護路由的備用路徑來疏散網路流量。 為了計算流量傳輸完成時間，我們在不同情況下進行了許多模擬，包括網路大小、傳輸對數、數據流長度以及調用備用路由的門檻值。在我們的模擬中，我們會對佇列設置門檻值，如果佇列中的封包數量達到門檻值，我們將此狀態視為擁塞。當主要傳輸路徑發生擁塞時，節點將調用備用路徑來轉發封包。最後，我們總結出關於透過保護路由來解決環面網路和高斯網路上的網路擁塞的負載平衡分析觀點。

關鍵字

完全獨立生成樹 ； 負載平衡 ； 網路壅塞 ； 環面網路 ； 緊密高斯網路 ； 保護路由

並列摘要

The load balancing for network congestion is to evenly distribute traffic among all links in a data center network so that the network can transmit more data flows with lower average end-to-end transmission delay. A protection routing is a fault-tolerant routing that can invoke a loop-free alternate path for packet forwarding when a single link or node fails. In this thesis, we develop a new idea that the alternate route of the protection routing will be taken to dredge the network traffic when the network congestion of the primary route reaches a certain threshold. Then, to calculate the flow completion time, we conduct a lot of simulations under different situations, including network sizes, the number of transmission pairs, flow lengths, and the thresholds for invoking alternate routes. In our simulation, there is a threshold associated with the queue so that if the number of packets in the queue reaches the threshold, we regard the status as the congestion. When congestion occurs in the primary link, the node will invoke the alternate path by sending packets to the second next-hop. Finally, we summarize some crucial analysis viewpoints about the load balancing for network congestion through protection routing on the torus network and the dense Gaussian network.

並列關鍵字

completely independent spanning trees ； load balancing ； network congestion ； torus networks ； dense Gaussian networks ； protection routing

參考文獻

[1] Al-Fares, M., Radhakrishnan, S., Raghavan, B., Huang, N., & Vahdat, A. (2010). Hedera: Dynamic flow scheduling for data center networks. Proceedings of the 7th USENIX conference on Networked systems design and implementation, 19.

[2] Alizadeh, M., Edsall, T., Dharmapurikar, S., Vaidyanathan, R., Chu, K., Fingerhut, A., Lam, V. T., Matus, F., Pan, R., Yadav, N., & Varghese, G. (2015). CONGA: Distributed congestion-aware load balancing for datacenters. ACM SIGCOMM Computer Communication Review, 44(4), 503–514.

[3] Benson, T., Anand, A., Akella, A., & Zhang, M. (2011). MicroTE: Fine grained traffic engineering for data centers. Proceedings of the Seventh COnference on Emerging Networking EXperiments and Technologies on - CoNEXT '11, 1–12.

[4] Chen, G., Cheng, B., & Wang, D. (2021). Constructing Completely Independent Spanning Trees in Data Center Network Based on Augmented Cube. IEEE Transactions on Parallel and Distributed Systems, 32(3), 665–673.

[5] Chen, G.-Y., Pai, K.-J., Wu, R.-Y., & Chang, J.-M. (2021). A Website for Constructing Dual-CISTs and Configuring Protection Routings in Tours Networks. https://torus-cist.herokuapp.com/routing