[發明專利]用于容錯和負載平衡路由的方法、系統和計算機存儲介質

有效

• 申請號: 201380077450.4
• 申請日: 2013-06-14
• 公開（公告）號: CN105379196B
• 公開（公告）日: 2019-03-22
• 發明（設計）人: 鄔海濤;郭傳雄;張永光;袁利華
• 申請（專利權）人: 微軟技術許可有限責任公司
• 主分類號: H04L12/70
• 分類號: H04L12/70
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 顧嘉運

描述了用于在存在鏈路故障的情況下平衡以多根樹拓撲配置的網絡的通信負載的技術。為子圖計算最大流量(通過最小分割)，所述子圖將源和目的地節點之間的鏈路上的有效鏈路容量合并。確定計及鏈路故障以及多個節點對當前可用的鏈路容量的共享的有效鏈路容量。通信被平衡同時充分利用了可用的鏈路容量，甚至是在部分故障的鏈路(例如部分故障的鏈路聚合組LAG)上的可用鏈路容量。

背景

多根樹結構通常被部署在生產數據中心網絡(DCN)中以提供高對分帶 寬。諸如等價多路徑路由之類的負載平衡策略常用于平衡在DCN中的節點(例如商 用網絡交換機、路由器)之間的多條并行路徑上的數據通信負載。然而，當鏈路故 障發生時，高度對稱的DCN變得不對稱。所述不對稱性對于現有的通信無察覺路由 (oblivious routing)協議的負載平衡來說是種挑戰，因為現有的路由協議被設 計成通過最低成本路徑解決目的地的可到達性。這樣，現有的負載平衡策略不能同 時地平衡通信并充分利用鏈路容量。因此，出現了網絡擁塞，減少了DCN中的數據 吞吐量。

DCN一般使用在節點之間的邏輯鏈路。邏輯鏈路一般被稱為鏈路聚合 組(LAG)，其通常由多個物理鏈路組成。LAG的使用使得負載平衡問題更加復雜， 因為LAG中的物理鏈路故障導致在邏輯鏈路中的部分容量損失。現有的路由協議 (例如開放最短路徑優先(OSPF))通常不會注意到對邏輯鏈路的容量的這種改變， 并且因此，繼續將相同量的負載路由到降級的LAG，這引起了網絡擁塞。

為了通過現有路由協議處理這個問題，整個LAG(包括部分故障的LAG 的健康的物理鏈路)經常被無效。例如，為了幫助路由協議找到不同的路徑以暫時 減輕由不平衡的負載所引起的擁塞，可以禁用附加的鏈路。然而，犧牲的鏈路容量 經常會導致更大規模的擁塞，特別是當網絡中的總體鏈路容量被高度利用時。例如， OSPF不恰當地平衡面臨不對稱且非鏈路分離路徑上的鏈路故障的負載，即使LAG 中的物理鏈路故障的信息是可用的。

附圖簡述

參考附圖來描述具體實施方式。在附圖中，附圖標記最左邊的數字標識 該附圖標記首次出現的附圖。在各附圖中，使用相同的標號來指示相同的特征和組 件。

圖1(A)和1(B)示出網絡的示例網絡拓撲。

圖2(A)和2(B)示出示例網絡中的部分鏈路故障。

圖3(A)-3(C)示出示例網絡的子圖和經轉換的子圖。

圖4(A)-4(C)示出示例網絡中的有效的鏈路容量。

圖5(A)示出示例網絡中的節點之間的鏈路的當前鏈路容量。圖5(B) 示出示例網絡中的節點之間的鏈路的有效鏈路容量。

圖6示出用于確定在節點處的有效鏈路容量的偽代碼的示例。

圖7(A)和7(B)示出存在鏈路故障時節點之間的路徑上的最大流量。

圖8(A)-8(D)示出子圖的共同部分減少。

圖9是示出示例負載平衡系統的組件的框圖。

圖10是示出示例負載平衡過程的流程圖。

圖11是示出一旦檢測到故障條件的示例負載平衡過程的流程圖。

詳細描述

概覽

在數據中心網絡(DCN)中，在其中節點(例如商用交換機、路由器) 和鏈路一般被配置為多根樹拓撲，具有等價多路徑路由(ECMP)的傳統的路由協議 (諸如開放最短路徑優先(OSPF))必須使用許多到目的地的路徑以確定實現通信負 載平衡的許多條ECMP條目。這樣，當鏈路故障發生時，傳統的路由協議和負載平 衡策略經常不恰當地對到目的地的通信進行平衡。在DCN拓撲中的各種層級處的節 點間的非鏈路分離路徑的誤算以及鏈路競爭的忽視是傳統的通信無察覺負載平衡 路由的基礎問題的示例。