多重路徑策略性路由的設計與分析

近幾年許多研究試著將第三層網路的優點引進至第二層網路中，利用等價多重路徑 (Equal Cost Multipath, ECMP) 的方法來提升鏈路的使用率以及擁有分散負載的能力，但是ECMP卻被以最短路徑的計算規則限制了可用的多重路徑數，在某些拓樸中還可以發現很多的送收組合只有單一路徑可以使用的情況。因此，本篇論文使用的方法不再是採用最短路徑的ECMP，而是利用策略性路由的概念，提出一個基於代數 (Algebra) 運算的策略性路由並且結合壅塞控制機制的方法，藉由代數模型制定策略規則來產生多重路徑，這樣可以將非常不同的路徑視為等價，使得路徑的產生更多元。此外，在實現策略性路由的過程中發現，不同的拓樸設計以及代數規則的制定對於策略性路由所產生的路徑數量有著相當大的影響，這也使得路由能夠依據不同的網路目標來做彈性調整。然而，這種允許使用非最短路徑的路由方式，導致網路中的鏈路平均使用比例變大，進而影響其他路徑在做繞送的機會，所以在本篇論文的網路設計中，除了加入一個能根據當下網路使用狀況分散資料流的壅塞控制機制外，本篇論文還提供了多個選擇路徑的轉發方法讓多重路徑的使用能更加有效率，進而提升了整個網路的吞吐量。

關鍵字

新興網路架構；等價多重路徑；策略性路由；代數路由；壅塞控制

並列摘要

In recent years, many efforts have been tried to bring the advantages of L3 routing to L2 networks by using equal cost multipath (ECMP) to increase link utilization and improve load-balancing. However, ECMP routing only allows the use of paths with the same cost and this cost is usually expressed by a metric value (e.g., hops). In many network topologies, ECMP does not necessarily provide enough path diversity. Non-ECMP can open up a new horizon where bisection bandwidth can be increased with a smaller cost and alternative topology designs can be explored for different applications or traffic patterns. Thus we propose a policy based multipath routing by using an algebraic routing model. Paths are selected based on a policy value that grades their preference. Paths with equal preference values might be different in the number of hops, bandwidth, etc. Although the policy based multipath routing has a great potential in finding multipath, the policy based multipath seems also affected by the network topology and the algebraic policy. For this reason, we also present a congestion control mechanism to spread loading dynamically by taking a global view of link utilization. In addition, we also provide several forwarding methods about how multiple paths are allocated to different flows.

並列關鍵字

Emerging Network Architecture ； ECMP ； Policy Based Routing ； Algebraic Routing ； Congestion Control

參考文獻

[2] D. Allan and P. Ashwood-Smith, “Shortest Path Bridging: efficient control of larger Ethernet networks,” Communications Magazine, IEEE, no. October, pp. 128–135, 2010.

[4] C. Cheng, R. Riley, S. P. R. Kumar, and J. J. Garcia-Luna-Aceves, “A loop-free extended Bellman-Ford routing protocol without bouncing effect,” volume 19. ACM, New York, NY, USA, September 1989.

[9] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, 1:269–271, 1959.

[12] M. Caesar and J. Rexford, BBGP routing policies in ISP networks, IEEE Network, vol. 19, no. 6, pp. 5–11, Nov.–Dec. 2005.

[16] D. Allan, J. Farkas, and S. Mansfield, “Intelligent load balancing for shortest path bridging,” Communications Magazine, IEEE, vol. 50, no. 7, pp. 163–167, 2012.

國際替代計量

多重路徑策略性路由的設計與分析

未授權

主題瀏覽