一種計算轉發最短路徑的方法

2023-05-05 23:23:36

專利名稱：一種計算轉發最短路徑的方法
技術領域：
本發明涉及計算轉發最短路徑的技術，尤其涉及一種交換機堆疊系統計算 轉發最短路徑的方法。
背景技術：
當交換機堆疊系統中的交換機比較多時，報文轉發路徑的選擇會影響到整 個交換機堆疊系統的負載和轉發能力。舉例來說，由六臺交換機組成的堆疊系
統，從交換機1到交換機6依次採用菊花鏈式，即交換機之間採用環形拓樸結 構連接。當報文從交換機1的埠進來，需要轉發到交換機6的埠時，如果 是從交換機1開始途經六臺交換機逐個轉發，會很佔用帶寬，並且使得鏈路上 的帶寬使用不合理。對於這種情況最快的轉發方式就是將報文從交換機1的端 口直接轉發到交換機6與交換機1相連的埠 ，也就是說選擇一條轉發的最短 路徑，將報文從交換機1直接轉發到交換機6。
目前，由於採用現有技術進行報文轉發時，通常是按照預先設置的交換機 堆疊系統中各交換機之間的轉發路徑直接進行報文轉發，而不是按照計算並判 斷出的轉發最短路徑進行報文轉發的，因此，採用現有技術存在的缺點是報 文的轉發效率低；帶寬佔用率高，且鏈路上的帶寬使用不合理。

發明內容
有鑑於此，本發明的主要目的在於提供一種計算轉發最短路徑的方法，能 在交換機堆疊系統實現報文的最短路徑轉發，使報文的轉發效率得到提升；降 低帶寬佔用率，且使鏈路上的帶寬使用更合理。
為達到上述目的，本發明的技術方案是這樣實現的
一種計算轉發最短路徑的方法，該方法包括以下步驟八、創建權重數組；根據預先設置的埠屬性初始化所述創建的權重數組，
以獲取交換機到其鄰居交換機的權重數組；
B、 遞歸遍歷並計算當前交換機到其他交換機的權重數組；比較並獲取所 述當前交換機到其他交換機的權重數組中的最小值，來獲取到交換機堆疊系統 中當前交換機到其他交換機的最短路徑。
其中，步驟A中還包括根據所述預先設置的埠屬性初始化發送矩陣； 步驟B中還包括計算所述發送矩陣，以完成所述當前交換機到其他交換機的報 文發送。
其中，步驟B之後還包括
C、 繼續執行步驟B，直至循環遍歷完所有交換機，來獲取到所述交換機堆 疊系統中每個交換機到其他交換機的最短路徑；獲取到所述每個交換機到其他 交換機的發送矩陣；
D、 根據每個交換機到其他交換機的最短路徑、每個交換機到其他交換機 的發送矩陣，完成最短路徑的報文轉發。
其中，所述計算當前交換機到其他交換機的權重數組具體為在所述當前 交換機到目的交換機的轉發路徑未知條件下；或者當前交換機到目的交換機的 轉發路徑已知，且當前交換機到目的交換機的權重數組> 當前交換機到參照交換 機的權重數組+所述參照交換機到目的交換機的權重數組條件下，計算當前交換 機到其他交換機的權重數組的公式為
weight[src] [dst]=weight[src] [mid]+weight[mid] [dst];
其中，src為所述當前交換機的編號，mid為所述參照交換機的編號，dst 為所述目的交換機的編號；weight[src][dst]為當前交換機到其他交換機的權重數 組，weight[src][mid]為當前交換機到參照交換機的權重數組，weight[mid][dst] 為參照交換機到目的交換機的權重數組。
其中，所述計算發送矩陣的計算公式為發送矩陣[src][dsth發送矩陣 [src] [mid]。
本發明遞歸遍歷並計算當前交換機到其他交換機的權重數組；比較並獲取當前交換機到其他交換機的權重數組中的最小值，來獲取到交換機堆疊系統中 當前交換機到其他交換機的最短路徑。
採用本發明，能在交換機堆疊系統實現報文的最短路徑轉發，提升報文在 交換機堆疊系統的轉發性能，即不僅使報文的轉發效率得到提升，而且降低帶 寬佔用率，且使鏈路上的帶寬使用更合理。


圖1為本發明方法的實現流程示意圖2為一交換機堆疊系統的組成結構示意圖。
具體實施例方式
本發明的核心思想是遞歸遍歷並計算當前交換機到其他交換機的權重數 組；比較並獲取當前交換機到其他交換機的權重數組中的最小值，來獲取到交 換機堆疊系統中當前交換機到其他交換機的最短路徑。
下面結合附圖對技術方案的實施作進一步的詳細描述。
如圖l所示， 一種計算轉發最短路徑的方法，該方法包括以下步驟
步驟101、創建權重數組；根據預先設置的埠屬性初始化所述創建的權 重數組，以獲取交換機到其鄰居交換機的權重數組。
這裡需要指出的是，權重數組，用於標識交換機堆疊系統中各交換機之間 報文轉發路徑的距離。針對鄰居交換機而言，相鄰的兩個交換機互為鄰居交換 機。埠屬性，用於記錄交換機堆疊系統中各交換機之間的埠連接關係。
這裡，針對創建權重數組而言，設置交換機堆疊系統中交換機的數目為n,
按照從小到大順序為每個交換機編號0、 1......( n - 1 )，則創建二維數組weight[n]為權重數組，該權重數組用來記錄任意兩個交換機之間的路徑權重。通常， 在互為鄰居交換機的兩個交換機之間的路徑權重，即交換機到其鄰居交換機的 權重數組為1，可以理解為交換機到其鄰居交換機的路徑為一跳。
這裡，步驟101中還包括根據預先設置的埠屬性初始化發送矩陣，即報文的發送路徑，以便後續通過對發送矩陣的計算完成當前交換機到其他交換 機的報文發送。當前交換機指源交換機，其他交換機指通過源交換機需將報文 發送到的目的交換機。發送矩陣的表示方式為發送矩陣[源][目的]。發送矩陣 [源][目的],用於標識源交換機上的堆疊埠 ，源交換機發往目的交換機任何端 口的報文均通過該堆疊埠發送。
其中，步驟101中進一步還包括根據預先設置的埠屬性初始化接收矩
陣，即報文的接收路徑，以便後續通過對接收矩陣的計算完成其他交換機從當 前交換機的報文接收。當前交換機指源交換機，其他交換機指通過源交換機需 將報文發送到的目的交換機。接收矩陣的表示方式為接收矩陣[目的][源]。接收 矩陣[源][目的],用於標識目的交換機上的堆疊埠 ，若源交換機需要發送報文 給目的交換機，則發送至該堆疊埠，也就是說，目的交換機從源交換機任何 埠 4妄收的4艮文均通過該堆疊埠"t妄收。
以下，針對根據預先設置的埠屬性初始化所述創建的權重數組，以及發 送矩陣和接收矩陣而言，進行舉例闡述。
當埠 i為編號為src的交換才幾的堆疊埠時，該埠 i的埠屬性為 tx_cpu—key和tx_stk—idx，並且tx—cpu—key對應的交4奐才幾編號為dst。 乂人而將交 換機src作為源交換機，將交換機dst作為目的交換機。那麼交換機src通過該 埠 i可以發送報文給交換機dst，則初始化並設置權重數組為 weight[src][dst]=l;初始化並設置發送矩陣為發送矩陣[src][dst]^;初始化並 設置接收矩陣為[dst][src]= tx_stk_idx。按照此方法，遍歷交換機堆疊系統中 所有交換機的所有堆疊埠 ，根據交換機堆疊系統中的所有堆疊埠的埠屬 性來完成對權重數組、發送矩陣和接收矩陣的初始化。另外，當該堆疊埠為 全雙工時，即該堆疊埠不僅可以用作發送才艮文的埠 ，而且還可以用作接收 報文的埠。那麼，同樣可以初始化並設置權重數組為weight[dst][ src]=l; 初始化並設置發送矩陣為發送矩陣[dst][ src]=i;初始化並設置接收矩陣為 接收矩陣[src][dst;h tx—stk—idx。按照此方法，遍歷交換機堆疊系統中所有交換 機的所有堆疊埠 ，同樣根據交換機堆疊系統中的所有堆疊埠的埠屬性來完成對權重數組、發送矩陣和接收矩陣的初始化。
步驟102、遞歸遍歷並計算當前交換才幾到其他交換機的權重數組；比較並 獲取當前交換機到其他交換機的權重數組中的最小值，來獲取到交換機堆疊系 統中當前交換機到其他交換機的最短路徑。
其中，步驟102中還包括計算發送矩陣以完成當前交換機到其他交換機 的報文發送。步驟102中還進一步包括計算接收矩陣以完成其他交換機從當 前交換機的報文接收。
這裡，計算當前交換機到其他交換機的權重數組具體為在當前交換機到 目的交換機的轉發路徑未知條件下；或者當前交換機到目的交換機的轉發路徑 已知，且當前交換機到目的交換機的權重數組>當前交換機到參照交換機的權重 數組+參照交換機到目的交換機的權重數組條件下，計算當前交換機到其他交換 機的權重數組的公式為如下所示的公式(1 ):
weight[src][dst]二weight[src][mid]+weight[mid][dst] ( 1 )
其中，src為當前交換機的編號，mid為參照交換機的編號，dst為目的交 換機的編號；weight[src] [dst]為當前交換機到其他交換機的權重數組， weight[src][mid]為當前交換機到參照交換機的權重數組，weight[mid][dst]為參照 交換機到目的交換機的權重數組。並且，當前交換機src和參照交換機mid，參 照交換機mid和目的交換機dst之間均相通。
這裡，計算發送矩陣的計算公式為如下所示的公式(2): 發送矩陣[src][dsfh發送矩陣[src][mid] ( 2 )
這裡，計算接收矩陣的計算公式為如下所示的公式(3): 接收矩陣[dst][src]—妄收矩陣[dst][mid] ( 3 )
這裡需要指出是，由於在通過計算和比較權重數組來獲取最短路徑時，要 遍歷交換機堆疊系統中的所有交換機，但是交換機不能相同。比如交換機堆疊 系統中有三個交換機，編號分別為src、 mid和dst，三者不能相同的意思指 交換機src、交換機mid和交換機dst不能指代同一臺交換機，即交換機src、交 換機mid和交換機dst指代交換機堆疊系統中的三個不同的交換機。步驟103、繼續執行步驟102,直至循環遍歷完交換機堆疊系統中的所有交 換機，來獲取到交換機堆疊系統中每個交換機到其他交換機的最短路徑；獲取 到每個交換機到其他交換機的發送矩陣。
其中，步驟102中，進一步還包括步驟獲取到每個交換機到其他交換機 的接收矩陣。
步驟104、將每個交換機到其他交換機的最短路徑、每個交換機到其他交 換機的發送矩陣設置到報文路徑轉發表中並下發至晶片，根據晶片中的設置值 完成最短路徑的報文轉發。
其中，步驟104中，進一步還包括步驟將每個交換機到其他交換機的接 收矩陣也設置到報文路徑轉發表中並下發至晶片，那麼，根據晶片中的設置值 完成最短路徑的報文轉發即為根據每個交換機到其他交換機的最短路徑、每 個交換機到其他交換機的發送矩陣以及每個交換機到其他交換機的接收矩陣， 完成最短路徑的報文轉發。
以下以 一 實例闡述以遍歷方式計算轉發最短路徑的具體實現過程。
以圖2中的四臺交換機堆疊為例，從上至下編號分別為A、 B、 C和D,即 如圖2所示，本實例中交換機堆疊系統包括交換4幾A、交換機B、交換機C 和交換機D。其中，交換機A與交換機B和交換機D相連；交換機B與交換 機A交換機和C相連；交換機C與交換機B和交換機D相連；交換機D與交 換機C和交換機A相連。每臺交換機的堆疊埠都是x 口和y 口，圖中未顯示。
以針對交換機A進行遞歸遍歷並計算當前交換機到其他交換機的權重數組 為例。具體來說，首先初始化各交換機的權重數組和發送矩陣。weight[A][B]=l， 發送矩陣[A][B^x, weight[A][D]=l,發送路徑[A][D]，。那麼在計算最短路徑 時，要遍歷該交換機堆疊系統的所有交換機，也就是說，上述公式(l)和公式 (2 )中所涉及到的計算參數源交換機src、參照計算機mid和目的交換機dst 都要遍歷到所有交換機，且源交換機src、參照交換機mid和目的交換機dst不 能相同。則首先從A開始進行遞歸遍歷並計算當前交換機到其他交換機的權重 數組的過程為a、 以交換機A為源交換機src，因為源交換機src、參照交換機mid和目的 交換機dst不能相同，則參照交換機mid從交換機B開始，即此時取參照交換 機mid為交換機B ，此時目的交換機dst從交換機C開始。
這裡，weight[A][C]未知，則weight[A〗[C]=weight[A][B]+weight[B][C]=2, 發送矩陣[A][Cp發送矩陣[A][B^x。接下來，目的交換機dst要選為交換機D, 但是，weight[B][D]未知，目的交換機dst繼續往下遍歷。由於交換機D是最後 一個，停止對目的交換才幾dst的遍歷。
b、 接下來，參照交換機mid要往下遍歷，此時取交換機mid為交換機C， 重新開始從A遍歷，則此時目的交換機dst可以取為交換機B和交換機D。
這裡，weight[A][B]已知且weight[A][B]〈weight[A][C]+weight[C][B],所以 weight[A][B]保持不變，同理，發送矩陣[A][B]也保持不變。
接下來，目的交換機dst要選為交換才幾D , weight[A][D]已知，且 weight[AJ[D]〈weight[A][C]+weight[C][D]，所以weight[A][D]保持不變，同理， 發送矩陣[A][D]也保持不變，目的交換機dst為交換機D時已是最後一個。由 於交換機D是最後一個，停止對目的交換機dst的遍歷。
c、 接下來，參照交換機mid繼續往下遍歷，此時取參照交換機mid為交換 機D,目的交換機dst可以取為交換機B和交換機C,分別按照上述方法進行 計算，這樣交換機A到其他各交換機的最短路徑就都確定了 。
執行為以交換機A為源交換機src的遞歸遍歷後，接下來源交換機src往下 遍歷，依照上述從A開始進行遞歸遍歷並計算當前交換機到其他交換機的權重 數組的a c過程的原理進行權重數組和發送矩陣的計算，直至循環遍歷完交換 機堆疊系統中的所有交換機，從而最終獲取到交換機堆疊系統中每個交換機到 其他交換機的最短路徑和獲取到每個交換機到其他交換機的發送矩陣。
以上所述，僅為本發明的較佳實施例而已，並非用於限定本發明的保護範圍。
權利要求
1、一種計算轉發最短路徑的方法，其特徵在於，該方法包括以下步驟A、創建權重數組；根據預先設置的埠屬性初始化所述創建的權重數組，以獲取交換機到其鄰居交換機的權重數組；B、遞歸遍歷並計算當前交換機到其他交換機的權重數組；比較並獲取所述當前交換機到其他交換機的權重數組中的最小值，來獲取到交換機堆疊系統中當前交換機到其他交換機的最短路徑。
2、 根據權利要求1所述的方法，其特徵在於，步驟A中還包括根據所 述預先設置的埠屬性初始化發送矩陣；步驟B中還包括計算所述發送矩陣， 以完成所述當前交換機到其他交換機的報文發送。
3、 根據權利要求2所述的方法，其特徵在於，步驟B之後還包括C、 繼續執行步驟B，直至循環遍歷完所有交換機，來獲取到所述交換機堆 疊系統中每個交換機到其他交換機的最短路徑；獲取到所述每個交換機到其他 交換機的發送矩陣；D、 根據每個交換機到其他交換機的最短路徑、每個交換機到其他交換機 的發送矩陣，完成最短路徑的報文轉發。
4、 根據權利要求2或3所述的方法，其特徵在於，所述計算當前交換機到 其他交換機的權重數組具體為在所述當前交換機到目的交換機的轉發路徑未 知條件下；或者當前交換機到目的交換機的轉發路徑已知，且當前交換機到目 的交換機的權重數組〉當前交換機到參照交換機的權重數組+所述參照交換機 到目的交換機的權重數組條件下，計算當前交換機到其他交換機的權重數組的 公式為weight[src] [dst]=weight[src] [mid]+weight[mid] [dst];其中，src為所述當前交換機的編號，mid為所述參照交換機的編號，dst 為所述目的交換機的編號；weight[src][dst]為當前交換機到其他交換機的權重數 組，weight[src][mid]為當前交換機到參照交換機的權重數組，weight[mid][dst] 為參照交換機到目的交換機的權重數組。
5、根據權利要求4的方法，其特徵在於，所述計算發送矩陣的計算公式為發送矩陣[src] [dst]=發送矩陣[src] [mid]。
全文摘要
本發明公開了一種計算轉發最短路徑的方法，該方法包括以下步驟創建權重數組；根據預先設置的埠屬性初始化所述創建的權重數組，以獲取交換機到其鄰居交換機的權重數組；遞歸遍歷並計算當前交換機到其他交換機的權重數組；比較並獲取所述當前交換機到其他交換機的權重數組中的最小值，來獲取到交換機堆疊系統中當前交換機到其他交換機的最短路徑。採用本發明，能在交換機堆疊系統實現報文的最短路徑轉發，使報文的轉發效率得到提升；降低帶寬佔用率，且使鏈路上的帶寬使用更合理。
文檔編號H04L12/56GK101299726SQ200810129129
公開日2008年11月5日 申請日期2008年6月30日 優先權日2008年6月30日
發明者陳建光 申請人:中興通訊股份有限公司