[發(fā)明專利]最短路徑確定中的打破平局

在審

• 申請?zhí)枺?/td>: 201410174422.0
• 申請日: 2008-12-11
• 公開（公告）號: CN103973566A
• 公開（公告）日: 2014-08-06
• 發(fā)明（設計）人: J.恰鮑特;D.艾倫;N.布拉格;P.阿什伍德史密斯
• 申請（專利權）人: 北方電訊網(wǎng)絡有限公司
• 主分類號: H04L12/721
• 分類號: H04L12/721
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 張懿;劉春元

本申請是申請日為2008年12月11日、申請?zhí)枮?00880127674.0、發(fā)明名稱為“最短路徑確定中的打破平局”的專利申請的分案申請。

技術領域

本發(fā)明涉及在諸如以太網(wǎng)的分組轉發(fā)通信網(wǎng)絡中在多種可能性中一致地選擇路徑，諸如等開銷最短路徑。

背景技術

在分組轉發(fā)通信網(wǎng)絡中，節(jié)點可以得知有關網(wǎng)絡的拓撲結構的情況，并且可以基于它獲取的關于該拓撲結構的信息決定它將如何向其它網(wǎng)絡節(jié)點中的每一個傳遞業(yè)務(traffic)。選擇路徑的主要根據(jù)是路徑開銷，其可以按照節(jié)點之間的跳躍(hop)的數(shù)量或者通過諸如連接節(jié)點的鏈路的帶寬等某個其它度量來規(guī)定，或者通過這兩者來規(guī)定。開放式最短路徑優(yōu)先(OSPF)和中間系統(tǒng)到中間系統(tǒng)(IS-IS)是被廣泛使用的鏈路狀態(tài)協(xié)議，它們基于每個節(jié)點的對路徑開銷的通告來建立最短路徑。這些協(xié)議通常不嘗試在多個等開銷的路徑之間打破平局(tie-break)。相反，它們通常跨若干等開銷的路徑傳播業(yè)務。傳播算法沒有被規(guī)定并且可以從路由器到路由器不同。可替換地，它們可以對單個路徑進行局部選擇而不考慮與由其它路由器進行的選擇的一致性。因此，無論發(fā)生何種情況，不能保證流的反方向(reverse direction)使用正方向(forward direction)所使用的路徑。

諸如組播開放式最短路徑優(yōu)先協(xié)議(MOSPF)的組播(multicast)路由協(xié)議依賴于網(wǎng)絡中的每個路由器構造相同的最短路徑樹。由于這個原因，MOSPF實現(xiàn)基于鏈路類型、LAN相比點對點(LAN vs.point-to-point)以及路由器標識符的打破平局方案以確保產生一樣的樹。但是，把打破平局決定建立在具有最大的標識符的父代(parent)之上意味著一般而言反向的流所使用的路徑將不會與正向的流所使用的路徑相同。

生成樹協(xié)議(生成樹協(xié)議(STP)、快速生成樹協(xié)議(RSTP)、多生成樹協(xié)議(MSTP))是在任意的拓撲結構中創(chuàng)建無回路的生成樹的方法。生成樹協(xié)議由網(wǎng)絡中的每個節(jié)點執(zhí)行。所有生成樹協(xié)議都使用基于(橋標識符，端口標識符)的局部打破平局決定在等開銷的路徑之間進行選擇。在生成樹中，首選選擇根節(jié)點，然后相對于那個根通過所有節(jié)點來構造樹。因此，盡管所有路徑對于離開和返回業(yè)務是對稱的(根據(jù)定義，簡單樹(simple tree)使得這成為僅有可能的構造)，但是選擇過程是慢的并且簡單樹的結構不能使用任何多余的容量。類似地，Radia Perlman的Rbridges提議使用父節(jié)點的標識符作為決勝局(tie-breaker)。

Mick Seaman在他給IEEE802.1工作組的“最短路徑橋接”提議(http://www.ieee802.org/1/files/public/docs2005/new-seaman-shortest-pat h-0305-02.pdf)中描述了對快速生成樹協(xié)議的簡單的協(xié)議增強，其通過增加“截斷矢量(cut vector)”來強制執(zhí)行一致的打破平局決定。該提議使用每一節(jié)點的VID來標識每一節(jié)點的生成樹。為了把需要由橋傳送的所有信息放進單個合法的以太網(wǎng)幀，這種技術目前將以太網(wǎng)的大小限制為32個橋。

圖1示出，即使對于普通的網(wǎng)絡的例子，基于父節(jié)點標識符的打破平局方法如何無法產生對稱路徑。在這個例子中，鏈路被認為具有等開銷并且因此路徑開銷的確定僅考慮跳躍的數(shù)量。首先考慮計算從A到B的路徑。當計算到達節(jié)點2時，將會發(fā)現(xiàn)等開銷的路徑的存在。有第一路徑(A-1-3-6)和第二路徑(A-1-4-5)。如果打破平局算法基于具有最小的標識符的父節(jié)點來選擇路徑，則它將選擇第二路徑(A-1-4-5)，因為節(jié)點標識符5小于節(jié)點標識符6。但是，現(xiàn)在考慮計算從B到A的路徑。當計算到達節(jié)點1時，將會發(fā)現(xiàn)等開銷的路徑的存在。有第一路徑(B-2-6-3)和第二路徑(B-2-5-4)。使用相同的打破平局標準，該打破平局算法選擇第一路徑(B-2-6-3)，因為節(jié)點標識符3小于節(jié)點標識符4。因此，可以看到的是由節(jié)點A和B進行的最短路徑計算提供不一致的結果。

在諸如給IEEE802.1aq的提議“供應商鏈路狀態(tài)橋接(PLSB)”的一些新興的協(xié)議中有為單播和未知/組播業(yè)務兩者保持跨網(wǎng)絡轉發(fā)的一致性以及在流的正方向和反方向兩者上都使用共同的路徑的要求。因此，重要的是當在等開銷的路徑之間打破平局時節(jié)點可以一致地得出相同的決定。此外，理想的是節(jié)點可以用最少量的處理努力來執(zhí)行打破平局。

發(fā)明內容