在三級clos交叉網絡中配置多層粒度業務路由的方法

2023-06-10 08:03:31 3

專利名稱：在三級clos交叉網絡中配置多層粒度業務路由的方法
技術領域：
本發明涉及通信領域中大容量交叉連接裝置實現中業務路由的配置，特別 是涉及一種在三級CLOS交叉網絡中實現多層粒度交叉連接的方法。
背景技術：
IP (InternetProtocol,網際網路協議)路由器和光交叉連接設備中，經常要 使用多級CLOS交換(網絡)。多級CLOS交換把交換單元分成多級輸入級、 輸出級以及以奇數方式增加的中間級。只有兩個相鄰級之間存在連接；中間級 只有一級的CLOS交換稱為三級CLOS交換。
大容量光交叉連接設備中， 一般用多層粒度進行交叉連接，例如，各級交 換單元的輸入、輸出埠可以是物理通道組，每個物理通道組包括多條物理通 道，每條物理通道包括多個時隙組，每個時隙組又可以包括多個時隙，在實現 時，可以上述任何一種粒度進行交叉連接。
由於CLOS交換是一個多通路的交換結構，從一個輸入埠到一個輸出端 口之間可能會有多條路徑，因此可以大大減少交叉節點數，提高利用率。但是 與單級網絡相比，任意一個三級CLOS交換都可能存在由於線路爭用而產生的 內部阻塞。因此，實現CLOS矩陣正常、高效工作的重點是要設計一種支持多 層粒度交叉連接、重構簡單有效的方法。在實際應用中，交叉裝置根據業務需 求，由設備控制晶片計算埠連接關係，並通過指令下達到交叉電路，完成交 叉動作。為了滿足時間要求(例如保護倒換實現的時間小於50ms，建立連接 的時間小於2s等要求)，該方法需要提高計算效率、減少交叉連接配置的反 應時間。
目前存在的三級CLOS交叉連接方法存在以下一些問題
1)，各方法分別依託於一種固定的三級CLOS矩陣結構，如三級CLOS
矩陣的各級交換單元都是空分交換單元；輸入級、輸出級的交換單元是空分交 換單元，中間級交換單元是時空分(Time Space, TS)交換單元等。這樣就從
根本上限制了方法的適用性；
2) ，各方法在實現上都只是考慮了單粒度的交叉連接，沒有考慮多層粒 度交叉連接的問題，這同樣從根本上限制了方法的適用性；
3) ，內部阻塞時的重構方法不能很好地解決優化分配連接資源(降低阻 塞率)和快速實現重構的矛盾。

發明內容
本發明所要解決的技術問題在於提供一種在三級CLOS交叉網絡中實現 多層粒度交叉連接的方法，用於解決現有方法適用性差以及不能更好地平衡重 構阻塞率與重構速度的矛盾。
為了實現上述目的，本發明提供了一種在三級CLOS交叉網絡中實現交叉 連接的方法，其特徵在於，包括
步驟一，讀取業務源、業務宿及業務粒度信息並確定當前連接為單播連接；
步驟二，判斷所述業務源、所述業務宿所在的交換晶片是否有空閒連接資 源，若沒有，返回一失敗信息後結束，否則，根據所述業務粒度信息中業務粒 度的不同採用不同的搜索方式搜索一直接可用的中間級交叉單元並判斷是否 搜索到所述直接可用的中間級交叉單元，若搜索到，則建立當前業務源與當前
業務宿之間的連接，返回一成功信息後結束，否則，進入步驟三；
步驟三，調整已有連接並判斷是否有當前業務源或業務宿所需的空閒埠 釋放，若有，則建立當前業務源與當前業務宿之間的連接，返回一成功信息後 結束，否則，返回一失敗信息後結束。
所述的在三級CLOS交叉網絡中實現交叉連接的方法，其中，所述步驟二
中，所述業務粒度分為最大業務粒度、次大業務粒度及更小業務粒度。
所述的在三級CLOS交叉網絡中實現交叉連接的方法，其中，所述步驟二
中，當所述業務粒度為最大業務粒度時，還包括以洪泛搜索方式搜索所述可用
的中間級交叉單元的步驟，具體為
步驟31，對當前業務源所屬輸入級交叉單元空閒出埠對應的最大粒度
連接，選擇順序數最小的最大粒度連接對應的中間級交叉單元為當前交叉單
元；及
步驟32，在當前業務宿所屬輸出級交叉單元中，判斷與當前中間級交叉
單元對應的入埠是否有空閒的最大粒度連接，若有，則建立當前業務源和當
前業務宿之間的最大粒度連接，返回成功信息後結束；否則，判斷是否己經遍 歷所有當前業務源所屬輸入級空閒出埠對應的最大粒度連接，若是，則進入 所述步驟三；否則，選擇順序數次小的最大粒度連接對應的中間級交叉單元為 當前交叉單元，回到所述步驟32繼續執行。
所述的在三級CLOS交叉網絡中實現交叉連接的方法，其中，所述步驟二 中，當所述業務粒度為次大業務粒度時，還包括以絕對最小搜索方式搜索所述 可用的中間級交叉單元的步驟，具體為
步驟41，對當前業務源所屬輸入級交叉單元出埠對應的所有最大粒度
連接，選擇次大粒度已被佔用最少的最大粒度連接對應的中間級交叉單元為當
前中間級交叉單元；若同時存在符合條件的多個中間級交叉單元，則選擇順序 數最小的最大粒度連接對應的中間級交叉單元為當前中間級交叉單元；及
步驟42，在當前業務宿所屬輸出級交叉單元中，判斷與當前中間級交叉 單元對應的入埠是否有空閒的次大粒度連接，若有，則建立當前業務源和當 前業務宿之間的次大粒度連接，返回成功信息後結束；否則，判斷是否已經遍 歷所有當前業務源所屬輸入級出埠對應的最大粒度連接，若是，則進入所述 步驟三；否則，順序選擇次大粒度連接利用次少的最大粒度連接對應的中間級 交叉單元為當前中間級交叉單元，回到所述步驟42繼續執行。
所述的在三級CLOS交叉網絡中實現交叉連接的方法，其中，所述步驟二 中，當所述業務粒度為更小業務粒度時，還包括以絕對最大搜索方式搜索選擇 所述可用的中間級交叉單元的步驟，具體為.-
步驟51，對當前業務源所屬輸入級交叉單元出埠對應的待建業務粒度 的上一級粒度連接，選擇業務粒度已被佔用最多的上一級粒度連接對應的中間 級交叉單元為當前中間級交叉單元；若同時存在符合條件的多個中間級交叉單 元，則選擇順序數最小的上一級粒度連接對應的中間級交叉單元為當前交叉單 元；若需要佔用一新的上一級粒度連接，則從佔用粒度最少的更上一級粒度連 接中選擇，若同時存在符合條件的多個更上一級粒度連接，則選擇順序數最小 的更上一級粒度連接對應的中間級交叉單元為當前中間級交叉單元；及
步驟52，在當前業務宿所屬輸出級交叉單元中，判斷與當前中間級交叉 單元對應的入埠是否有空閒的相應粒度的連接，若有，則建立當前業務源和
當前業務宿之間的更小粒度連接，返回成功信息後結束；否則，判斷是否已經 遍歷所有當前業務源所屬輸入級出埠對應的上一級粒度連接，若是，則進入 所述步驟三；否則，順序選擇粒度佔用次多的上一級粒度連接對應的中間級交 叉單元為當前中間級交叉單元，回到所述步驟52繼續執行。
所述的在三級CLOS交叉網絡中實現交叉連接的方法，其中，所述步驟三 中，所述調整已有連接的步驟具體為
步驟61，遍歷當前業務宿所佔晶片空閒入埠對應的業務源所屬晶片出 埠的己有連接並判斷是否有合適的空閒資源為該已有連接直接建立另一條 通路；並當存在直接重建連接的空閒資源時，為該已有連接重新建立新的連接 通路；
步驟62，令當前業務源佔用該已有連接釋放出的空閒交叉粒度資源，建 立連接並返回成功信息後結束；否則，記錄所述步驟61中所有遍歷的已有連 接；
步驟63,遍歷當前業務源所佔晶片空閒出埠對應的當前業務宿所屬交 叉單元入埠的已有連接並判斷是否有合適的空閒資源為該已有連接直接建 立另一條通路；並當存在直接重建連接的空閒資源時，為該已有連接重新建立 新的連接通路；及
步驟64，令當前業務宿佔用該已有連接釋放出的空閒交叉粒度資源，建 立連接並在返回成功信息後結束；否則，記錄所述步驟63中所有遍歷的已有 連接，進入下一層重構。
所述的在三級CLOS交叉網絡中實現交叉連接的方法，其中，所述步驟 64中，所述進入下一層重構的步驟具體為
步驟71，選擇所述步驟61中所有遍歷的已有連接的第l條，分別確定該 己有連接的業務源所屬晶片的空閒出埠和業務宿所屬晶片的空閒入埠；
步驟72，遍歷業務宿所屬晶片空閒入埠對應的業務源所屬晶片出埠 的己有連接並判斷是否有合適的空閒資源為該已有連接直接建立另一條通路， 並當存在直接重建連接的空閒資源時，為該已有連接重新建立新的連接通路， 同時拆除所述步驟71中的已有連接，其業務源和業務宿佔用該已有連接釋放 出的空閒交叉粒度資源，建立新的連接並返回到所述步驟62;否則，記錄所 有遍歷的已有連接-，
步驟73，遍歷業務源所屬晶片空閒出埠對應的業務宿所屬晶片入埠 的己有連接並判斷是否有合適的空閒資源為該己有連接直接建立另一條通路； 並當存在直接重建連接的空閒資源時，則為所述步驟72中的已有連接重新建 立新的連接通路，同時拆除所述步驟71中的已有連接，其業務源和業務宿佔 用該已有連接釋放出的空閒交叉粒度資源，建立新的連接並返回到所述步驟 64;否則，記錄所有遍歷的已有連接；及
步驟74，依次選擇所述步驟61中所有遍歷的已有連接的第2條到最後一 條，重新進入所述步驟71，若重構成功，返回成功信息後結束，若重構仍然 失敗，重新進入所述步驟71，並所述步驟61中所有遍歷的已有連接更換為所 述步驟63中所有遍歷的已有連接，並在重構失敗時，返回到所述步驟71。
所述的在三級CLOS交叉網絡中實現交叉連接的方法，其中，所述步驟 74中，所述重構的重構深度為大於1的整數，該重構深度根據重構的時間、 計算資源而確定。
為了實現上述目的，本發明還提供了一種在三級CLOS交叉網絡中實現交 叉連接的方法，其特徵在於，包括
步驟91，讀取業務源、業務宿以及業務粒度信息並對當前連接進行判斷， 若當前連接為單播連接，則轉入步驟92，若當前連接為多播連接，則轉入步 驟93;
步驟92，判斷所述業務源、所述業務宿所在的交換晶片是否有空閒連接 資源，若沒有，返回一失敗信息後結束，否則，根據所述業務粒度信息中業務 粒度的不同採用不同的搜索方式搜索一直接可用的中間級交叉單元並判斷是 否搜索到所述直接可用的中間級交叉單元，若搜索到，則建立當前業務源與當 前業務宿之間的連接，返回一成功信息後結束，否則，進入步驟94;
步驟93,判斷所述多播連接能否在輸出級廣播，若能，則在所述輸出級 建立連接，返回一成功信息後結束，否則，進一步判斷所述多播連接能否在中 間級廣播，若能，則在所述中間級建立連接，返回一成功信息後結束，否則， 進入步驟94;及
歩驟94，調整已有連接並判斷是否有當前業務宿所需的空閒埠釋放， 若有，則建立當前業務源與業務宿之間的連接，返回一成功信息後結束，否則， 返回一失敗信息後結束。
所述的在三級CLOS交叉網絡中實現交叉連接的方法，其中，所述步驟 94中，還包括
步驟101，遍歷當前業務宿所屬交叉單元入埠部分的已有單播連接並判
斷是否能為該己有單播連接直接建立另一條通路，若存在直接重建連接的通 路，則重新建立該已有單播連接，並令所述業務源佔用該連接釋放出的空閒交
叉粒度資源，建立連接並返回成功信息後結束；否則，記錄遍歷的所有已有單 播連接；
步驟102，遍歷當前業務宿所屬交叉單元入埠部分的已有多播連接並判 斷是否能為所述已有多播連接直接建立另一條通路，若存在直接重建連接的通 路，則重新建立所述已有多播連接並令所述業務源佔用該已有多播連接釋放出 的空閒交叉粒度資源，建立連接並返回成功信息後結束；否則轉入步驟103， 及；
步驟103，對所述步驟101中所有已有單播連接按照單播連接時的重構步 驟進行下一層次的重構，並在重構中按照所述步驟102進行多播連接的重構， 其中，所述重構的重構深度為大於1的整數，所述重構深度根據重構的時間、 計算資源而確定。
所述的在三級CLOS交叉網絡中實現交叉連接的方法，其中，所述步驟 93、步驟94中，還包括在業務路由建立和重構的步驟中根據業務粒度信息中 業務粒度的不同採用不同的搜索方式搜索空閒資源的步驟，具體為
當所述業務粒度為最大業務粒度時，以洪泛搜索方式進行搜索；或 當所述業務粒度為次大業務粒度時，以絕對最小搜索方式進行搜索；或 當所述業務粒度為更小業務粒度時，以絕對最大搜索方式進行搜索。 採用本發明方法，與現有技術相比，由於採用了通用的、具備多層粒度交 叉能力的交叉矩陣單元，因而從根本上拓寬了三級CLOS交換網絡實現交叉連 接方法的適用性，也更符合實際情況；另外，本發明方法在業務建立和重構的 過程中，針對不同的業務粒度採用不同的資源搜索方式，兼顧了小粒度資源的 集中優化使用和大粒度資源的均衡使用，在業務建立時能儘量減少重構發生的 可能性，在需要重構時能儘量減少重構深度，降低重構阻塞率。
以下結合附圖和具體實施例對本發明進行詳細描述，但不作為對本發明的 限定。


圖1為現有三級CLOS交換結構；
圖2為現有對稱三級CLOS交換結構；
圖3為本發明單播算法流程示意圖4為本發明單播算法-物理鏈路組連接示例；
圖5為本發明單播算法-物理鏈組連接示例；
圖6為本發明單播算法-時隙連接示例；
圖7為本發明一實施例的單播算法流程示意圖8為本發明多播算法流程示意圖9為本發明多播算法-時隙連接示例；
圖io為本發明一實施例的多播算法流程示意圖。
具體實施例方式
本發明所述三級CLOS交叉網絡實現多層粒度交叉連接的方法包括單播 和多播兩種情況。下面結合附圖及具體實施例，詳細描述本發明方法的實現過程。
如圖1所示，為現有三級CLOS交換結構，圖2為現有對稱三級CLOS 交換結構。其中，^為輸入級(第一級)各交換單元的輸入埠數，"2為輸出 級(第三級)各交換單元的輸出埠數；m為中間級(第二級)交換單元的個 數；n和^分別為中間級交換單元的輸入和輸出埠數。
當",="2， ^=^時，稱三級CLOS交換結構是"對稱的"。如圖2所示， A = "2 = 4 ， ^ = r2 = 4 , m = 4 。
為了具體描述本發明方法的實現過程，設圖2中每個交換單元都是完全無 阻的時空分(TS)交換單元(可以是一個具體的晶片)。輸入級、輸出級和 中間級之間的埠為最大粒度的連接，稱為物理鏈路組(個數為4);每個物
理鏈路組中包含次大粒度的連接，稱為物理鏈路(個數為2);每條物理鏈路
又包含交叉粒度的連接，稱為時隙(個數為2)。輸入級和中間級之間以及中
間級和輸出級之間的物理鏈路組、物理鏈路、時隙都分別按順序進行編號。輸 入級、中間級以及輸出級的交換晶片同樣按順序進行編號。
如圖3所示，為本發明單播算法流程示意圖。該流程包括-
步驟31，讀取業務源、業務宿以及業務粒度信息，判斷業務源和業務宿
所在交換晶片是否有空閒連接資源，如果沒有，則返回失敗信息後結束。如果
有，則進入步驟32;
步驟32，根據業務粒度的不同，採用不同的搜索方式，選擇一個直接可 用的中間級交叉單元，如果有，則建立當前業務源和業務宿之間的連接，返回
成功信息後結束，否則，進入步驟33;
步驟33，調整已有連接，判斷是否有當前業務源或業務宿所需的空閒端 口釋放，如果有，則建立當前業務源和業務宿之間的連接，返回成功信息後結 束，否則，返回失敗信息後結束。
上述步驟32進一步包括
對於最大業務粒度，採用如下"洪泛"搜索方式選擇可用的中間級交叉單
元，該方式具體又包括
al)，對當前業務源所屬輸入級交叉單元空閒出埠對應的最大粒度連接， 選擇順序數最小的那個最大粒度連接對應的中間級交叉單元為當前交叉單元；
bl)，在當前業務宿所屬輸出級交叉單元中，判斷與當前中間級交叉單元 對應的入埠是否有空閒的最大粒度連接，如果有，則建立當前業務源和當前 業務宿之間的最大粒度連接，返回成功信息後結束；否則，判斷是否已經遍歷 所有當前業務源所屬輸入級空閒出埠對應的最大粒度連接，如果是，則進入 步驟33;如果尚未遍歷完，選擇順序數次小的那個最大粒度連接對應的中間
級交叉單元為當前交叉單元，回到步驟bl繼續執行；
對於次大業務粒度，採用如下"絕對最小"搜索方式選擇可用的中間級交
叉單元，該方式具體又包括
a2)，對當前業務源所屬輸入級交叉單元出埠對應的所有最大粒度連接， 選擇次大業務粒度已被佔用最少的一個最大粒度連接對應的中間級交叉單元 為當前中間級交叉單元；如果同時存在符合條件的多個中間級交叉單元，則選 擇順序數最小的那一個最大粒度連接對應的中間級交叉單元為當前中間級交 叉單元；
b2)，在當前業務宿所屬輸出級交叉單元中，判斷與當前中間級交叉單元 對應的入埠是否有空閒的次大粒度連接，如果有，則建立當前業務源和當前業務宿之間的次大粒度連接，返回成功信息後結束；否則，判斷是否已經遍歷 所有當前業務源所屬輸入級出埠對應的最大粒度連接，如果是，則進入步驟 33;如果不是，則順序選擇次大粒度連接利用次少的那個最大粒度連接對應的 中間級交叉單元為當前中間級交叉單元，回到步驟b2繼續執行；
對於其他更小的業務粒度，採用如下"絕對最大"搜索方式選擇可用的中 間級交叉單元，該方式具體又包括
a3)，對當前業務源所屬輸入級交叉單元出埠對應的待建業務粒度上一 級粒度的連接，選擇業務粒度已被佔用最多的那個上一級粒度連接對應的中間 級交叉單元為當前中間級交叉單元；如果同時存在符合條件的多個中間級交叉 單元，則選擇順序數最小的那個連接對應的中間級交叉單元為當前交叉單元； 如果需要佔用一個新的上一級粒度連接，則從佔用粒度最少的更上一級粒度連 接中選擇，如果同時存在符合條件的多個更上一級粒度連接，則選擇順序數最 小的那個連接，它對應的中間級交叉單元為當前中間級交叉單元；
b3)，在當前業務宿所屬輸出級交叉單元中，判斷與當前中間級交叉單元 對應的入埠是否有空閒的相應粒度的連接，如果有，則建立當前業務源和當 前業務宿之間的更小粒度連接，返回成功信息後結束；否則，判斷是否已經遍 歷所有當前業務源所屬輸入級出埠對應的上一級粒度連接，如果是，則進入 步驟33;如果不是，則順序選擇粒度佔用次多的那個上一級粒度連接對應的 中間級交叉單元為當前中間級交叉單元，回到步驟b3繼續執行；
上述步驟33中的調整已有連接的步驟進一步包括-
步驟331，遍歷當前業務宿所佔晶片空閒入埠對應的業務源所屬晶片出 埠的已有連接，按照步驟32，判斷是否有合適的空閒資源為該已有連接直 接建立另一條通路；
步驟332，如果存在直接重建連接的空閒資源，則為步驟331中的己有連 接重新建立新的連接通路；
步驟333，令當前業務源佔用該連接釋放出的空閒交叉粒度資源，建立連 接，返回成功信息後結束；否則，記錄步驟331中所有遍歷的已有連接，進入 步驟334;
步驟334，遍歷當前業務源所佔晶片空閒出埠對應的當前業務宿所屬交 叉單元入埠的已有連接，按照步驟32，判斷是否有合適的空閒資源為該已
有連接直接建立另 一條通路；
步驟335，如果存在直接重建連接的空閒資源，則為步驟334中的已有連 接重新建立新的連接通路；
步驟336，令當前業務宿佔用該連接釋放出的空閒交叉粒度資源，建立連 接，返回成功信息後結束；否則，記錄步驟334中所有遍歷的已有連接，進入 步驟337;以及
步驟337，進入下一層次重構；該步驟又包括
cl)，選擇步驟331中所有遍歷的已有連接的第1條，分別確定該連接的 業務源所屬晶片的空閒出埠和業務宿所屬晶片的空閒入埠；
c2)，遍歷業務宿所屬晶片空閒入埠對應的業務源所屬晶片出埠的已 有連接，按照步驟32，判斷是否有合適的空閒資源為該已有連接直接建立另 一條通路；
c3)，如果存在直接重建連接的空閒資源，則為步驟c2中的已有連接重 新建立新的連接通路；同時拆除步驟cl中的已有連接，其業務源和業務宿佔 用步驟c2中已有連接釋放出的空閒交叉粒度資源，建立新的連接，返回到步 驟333;否則，記錄步驟c2中所有遍歷的已有連接，進入步驟c4;
c4)，遍歷業務源所屬晶片空閒出埠對應的業務宿所屬晶片入埠的已 有連接，按照步驟32，判斷是否有合適的空閒資源為該已有連接直接建立另 一條通路；
c5)，如果存在直接重建連接的空閒資源，則為步驟c4中的已有連接重 新建立新的連接通路；同時拆除步驟cl中的已有連接，其業務源和業務宿佔 用步驟c4中已有連接釋放出的空閒交叉粒度資源，建立新的連接，返回步驟 336;否則，記錄步驟c4中所有遍歷的已有連接，進入步驟c6;
c6)，依次選擇步驟331中所有遍歷的已有連接的第2條到最後一條，重 新進入步驟cl;如果重構成功，則返回成功信息後結束；如果重構仍然失敗， 進入步驟C7;
c7)，重新進入步驟cl，只不過把"步驟331中所有遍歷的已有連接" 更換為"步驟334中所有遍歷的已有連接"；以及
c8)，如果重構仍然失敗，則進入更下一層次的重構，重新進入步驟337， 此時，"己有連接"是最近一次記錄的、更新層次的，因重構而需要調整的已
有連接數量將增加一條；
該步驟中，重構深度(層次數)M是大於1的整數，根據時間、計算資 源等因素確定，如果超過規定的重構深度M而仍然無法建立相應的業務源到 業務宿的連接，則返回失敗信息後結束。
結合圖3，在以下實施例將詳細描述3種不同業務粒度建立業務路由的過 程，更具體地描述本發明的技術方案。
如圖4所示，需要建立從輸入級交換晶片1的第一個物理鏈路組到輸出級 交換晶片1的第一個物理鏈路組的單播連接；具體實現該連接可按照圖7所示 的步驟進行處理。
對於該物理鏈路組連接，採用如下"洪泛"搜索方式，包括
4a)，對輸入級晶片1出埠的所有空閒物理鏈路組，選擇順序數最小的 那個空閒物理鏈路組對應的中間級晶片為當前中間級交叉單元。例如，如果中 間級晶片A和B與輸入級晶片1的出埠都存在空閒物理鏈路組相連，則選 擇序號小的A;
4b),判斷與當前中間級晶片A對應的輸出級晶片1入埠是否有空閒 物理鏈路組，如果有，則建立輸入級晶片1和輸出級晶片1之間的物理鏈路組 連接，返回成功信息後結束；否則，判斷是否已經遍歷所有輸入級晶片l空閒 出埠對應的物理鏈路組，如果是，則進入步驟33;如果尚未遍歷完，選擇 順序數次小的那個物理鏈路組對應的中間級晶片為當前交叉單元，如晶片B， 回到步驟4b繼續執行。
如圖5所示，為需要建立從輸入級交換晶片1的第一個物理鏈路組中的第 一個物理鏈路到輸出級交換晶片1的第一個物理鏈路組中的第一個物理鏈路 的單播連接；具體實現該連接可按照圖7所示的步驟進行處理。
對於該物理鏈路連接，採用如下"絕對最小"搜索方式，包括
5a)，對輸入級晶片1出埠對應的所有物理鏈路組，選擇物理鏈路已被 佔用最少的那個物理鏈路組對應的中間級晶片為當前中間級交叉單元；如果中 間級晶片A和B同時符合條件，則選擇順序數最小的那一個，即中間級晶片 A;
5b)，判斷與中間級晶片A對應的輸出級晶片1入埠是否有空閒的物 理鏈路，如果有，則分別選擇相應物理鏈路組中順序數最小的空閒物理鏈路建
立輸入級晶片1和輸出級晶片1之間的物理鏈路連接，例如，選擇輸入級和中
間級之間物理鏈路組1的物理鏈路1以及中間級和輸出級之間物理鏈路組1
的物理鏈路l;返回成功信息後結束；否則，判斷是否已經遍歷所有輸入級芯
片1出埠對應的物理鏈路組，如果是，則進入步驟33;如果不是，則順序
選擇物理鏈路利用次少的那個物理鏈路組對應的中間級晶片為當前中間級交
叉單元，如晶片C，回到步驟5b繼續執行。
如圖6所示，為需要建立從輸入級交換晶片1的第一個物理鏈路組中的第
一個物理鏈路內的第一個時隙到輸出級交換晶片1的第一個物理鏈路組中的 第一個物理鏈路內的第一個時隙的單播連接；具體實現該連接可按照圖7所示
的步驟進行處理。
對於該時隙連接，採用如下"絕對最大"搜索方式，包括
6a)，對輸入級晶片1出埠對應的物理鏈路，選擇時隙資源已被佔用最 多的那個物理鏈路對應的中間級晶片為當前中間級交叉單元；如果同時存在符 合條件的多個中間級晶片，則選擇順序數最小的那個物理鏈路對應的中間級芯 片為當前交叉單元，例如，如果中間級晶片A和B都滿足該需求，則選擇序 號小的A;如果需要佔用一個新的空閒物理鏈路，則從空閒物理鏈路資源最多 的物理鏈路組中選擇，如果同時存在符合條件的多個物理鏈路組，則選擇順序 數最小的那個，它對應的中間級晶片為當前中間級交叉單元；
6b)，判斷與中間級晶片A對應的輸出級晶片1的入埠是否有空閒的 時隙資源，如果有，則建立從輸入級交換晶片1的第一個物理鏈路組中的第一 個物理鏈路內的第一個時隙，到輸出級交換晶片1的第一個物理鏈路組中的第 一個物理鏈路內的第一個時隙的單播連接，返回成功信息後結束；否則，判斷 是否已經遍歷輸入級晶片1的所有出埠對應的物理鏈路資源，如果是，則進 入步驟33;如果不是，則順序選擇時隙資源佔用次多的那個物理鏈路對應的 中間級晶片為當前中間級交叉單元，如晶片D，回到步驟6b繼續執行。
結合圖3、 4，對於物理鏈路組連接，例如，輸入級晶片1到中間級晶片A、 D的物理鏈路組被佔用，同時中間級晶片B、 C到輸出級晶片1的物理鏈路組 也被佔用，則調整已有連接的步驟包括
all)，遍歷輸出級晶片1空閒入埠對應的輸入級晶片1出埠的已有 物理鏈路組連接(如從輸出級晶片1入埠 1開始，檢査其對應的輸入級晶片 1到中間級晶片A之間的已有物理鏈路組連接——可能是從輸入級晶片1到輸
出級晶片2、 3或者4的一個連接)，按照步驟32，判斷是否有合適的空閒物 理鏈路組為該已有連接直接建立另一條通路；
a12)，如果存在直接重建連接的空閒物理鏈路組資源(如選擇中間級芯 片B、 C或者D作為其中間級晶片)，則為步驟all中的已有連接重新建立新 的連接通路；
a13)，令當前業務源佔用該連接釋放出的空閒物理鏈路組資源，建立輸 入級晶片1和輸出級晶片1之間的物理鏈路組連接，返回成功信息後結束；否 則，記錄步驟all中所有遍歷的已有物理鏈路組連接，進入步驟al4;
a14)，遍歷輸入級晶片1空閒出埠對應的輸出級晶片1入埠的已有 物理鏈路組連接(如從輸入級晶片1出埠 1開始，檢査其對應的輸出級晶片 1到中間級晶片A之間的已有物理鏈路組連接——可能是從輸入級晶片2、 3 或者4到輸出級晶片1的一個連接)，按照步驟32，判斷是否有合適的空閒 物理鏈路組資源為該已有連接直接建立另一條通路；
a15)，如果存在直接重建連接的空閒資源(如選擇中間級晶片B、 C或 者D作為其中間級晶片)，則為步驟a14中的已有連接重新建立新的連接通 路；
a16)，令當前業務宿佔用該連接釋放出的空閒物理鏈路組資源，建立輸 入級晶片1和輸出級晶片1之間的物理鏈路組連接，返回成功信息後結束；否 則，記錄步驟al4中所有遍歷的已有物理鏈路組連接，進入步驟al7;
a17)，進入下一層次重構；該步驟又包括
a171)，選擇步驟all中所有遍歷的已有連接的第l條，分別確定該連接 的業務源所屬晶片的空閒出埠和業務宿所屬晶片的空閒入埠；
a172)，遍歷業務宿所屬晶片空閒入埠對應的業務源所屬晶片出埠的 已有連接，按照步驟32，判斷是否有合適的空閒資源為該已有連接直接建立 另一條通路；
a173)，如果存在直接重建連接的空閒資源，則為步驟al72中的已有連 接重新建立新的連接通路；同時拆除步驟a171中的已有連接，其業務源和業 務宿佔用步驟a172中已有連接釋放出的空閒交叉粒度資源，建立新的連接， 返回到步驟a13。否則，記錄步驟a172中所有遍歷的己有連接，進入步驟al74;a174)，遍歷業務源所屬晶片空閒出埠對應的業務宿所屬晶片入埠的 已有連接，按照步驟32，判斷是否有合適的空閒資源為該已有連接直接建立 另一條通路；
a175)，如果存在直接重建連接的空閒資源，則為步驟a174中的已有連 接重新建立新的連接通路；同時拆除步驟a171中的己有連接，其業務源和業 務宿佔用步驟a174中已有連接釋放出的空閒交叉粒度資源，建立新的連接， 返回步驟al6。否則，記錄步驟al74中所有遍歷的已有連接，進入步驟al76;
a176)，依次選擇步驟all中所有遍歷的已有連接的第2條到最後一條， 重新進入步驟al71;如果重構成功，則返回成功信息後結束；如果重構仍然 失敗，進入步驟al77;
a177)，重新進入步驟a171，只不過把"步驟all中所有遍歷的已有連接" 更換為"步驟al4中所有遍歷的己有連接"；以及
a178)，如果重構仍然失敗，則進入更下一層次的重構，重新進入步驟 a17，注意此時的"已有連接"是最近一次記錄的、更新層次的，因重構而需 要調整的已有連接數量將增加一條；
該步驟中，重構深度(層次數)M是大於l的整數，比如取4，則如果重 構深度M超過4而仍然無法建立相應的業務源到業務宿的連接，則返回失敗 信息後結束。
結合圖3、 5，對於物理鏈路連接，例如，輸入級晶片1到中間級晶片A、 D的所有物理鏈路被佔用，同時中間級晶片B、 C到輸出級晶片1的所有物理 鏈路也被佔用，則調整該已有連接的步驟包括
a21)，遍歷輸出級晶片1空閒入埠對應的輸入級晶片1出埠的已有 物理鏈路連接(如從輸出級晶片1入埠 1開始，檢査其對應的輸入級晶片1 到中間級晶片A之間的已有物理鏈路連接——可能是從輸入級晶片1到輸出 級晶片2、 3或者4的一個連接)，按照步驟32，判斷是否有合適的空閒物理 鏈路為該已有連接直接建立另一條通路；
a22)，如果存在直接重建連接的空閒物理鏈路資源(如選擇中間級晶片 B、 C或者D作為其中間級晶片)，則為步驟a21中的已有連接重新建立新的 連接通路；
a23)，令當前業務源佔用該連接釋放出的空閒物理鏈路資源，建立輸入 級晶片l和輸出級晶片l之間的物理鏈路連接，返回成功信息後結束；否則，
記錄步驟a21中所有遍歷的已有物理鏈路連接，進入步驟a24;
a24)，遍歷輸入級晶片1空閒出埠對應的輸出級晶片1入埠的已有 物理鏈路連接(如從輸入級晶片1出埠 1幵始，檢査其對應的輸出級晶片1 到中間級晶片A之間的已有物理鏈路連接——可能是從輸入級晶片2、 3或者 4到輸出級晶片1的一個連接)，按照步驟32，判斷是否有合適的空閒物理鏈 路資源為該已有連接直接建立另 一條通路；
a25)，如果存在直接重建連接的空閒資源(如選擇中間級晶片B、 C或 者D作為其中間級晶片)，則為步驟a24中的已有連接重新建立新的連接通 路；
a26)，令當前業務宿佔用該連接釋放出的空閒物理鏈路資源，建立輸入 級晶片l和輸出級晶片l之間的物理鏈路連接，返回成功信息後結束；否則， 記錄步驟a24中所有遍歷的已有物理鏈路連接，進入步驟a27;
a27)，進入下一層次重構；該步驟又包括
a271)，選擇步驟a21中所有遍歷的已有連接的第1條，分別確定該連接 的業務源所屬晶片的空閒出埠和業務宿所屬晶片的空閒入埠；
a272)，遍歷業務宿所屬晶片空閒入埠對應的業務源所屬晶片出埠的 已有連接，按照步驟32，判斷是否有合適的空閒資源為該已有連接直接建立 另一條通路；
a273)，如果存在直接重建連接的空閒資源，則為步驟a272中的已有連 接重新建立新的連接通路；同時拆除步驟a271中的已有連接，其業務源和業 務宿佔用步驟a272中已有連接釋放出的空閒交叉粒度資源，建立新的連接， 返回到步驟a23。否則，記錄步驟a272中所有遍歷的已有連接，進入步驟a274;
a274)，遍歷業務源所屬晶片空閒出埠對應的業務宿所屬晶片入埠的 已有連接，按照步驟32，判斷是否有合適的空閒資源為該已有連接直接建立 另一條通路；
a275)，如果存在直接重建連接的空閒資源，則為步驟a274中的已有連 接重新建立新的連接通路；同時拆除步驟a271中的已有連接，其業務源和業 務宿佔用步驟a274中已有連接釋放出的空閒交叉粒度資源，建立新的連接， 返回步驟a26。否則，記錄步驟a274中所有遍歷的已有連接，進入步驟a276;
a276)，依次選擇步驟a21中所有遍歷的已有連接的第2條到最後一條， 重新進入步驟a271;如果重構成功，則返回成功信息後結束；如果重構仍然 失敗，進入步驟a277;
a277)，重新進入步驟a271，只不過把"步驟a21中所有遍歷的已有連接" 更換為"步驟a24中所有遍歷的已有連接"；以及
a278)，如果重構仍然失敗，則進入更下一層次的重構，重新進入步驟 a27，注意此時的"已有連接"是最近一次記錄的、更新層次的，因重構而需 要調整的已有連接數量將增加一條；
該步驟中，重構深度(層次數)M是大於l的整數，比如取4，則如果重 構深度M超過4而仍然無法建立相應的業務源到業務宿的連接，則返回失敗 信息後結束。
結合圖3、 6，對於時隙連接，例如，輸入級晶片1到中間級晶片A、 D 的所有時隙被佔用，同時中間級晶片B、 C到輸出級晶片1的所有時隙也被佔 用，則調整該已有連接的步驟包括
a31)，遍歷輸出級晶片1空閒入埠對應的輸入級晶片1出埠的已有 時隙連接(如從輸出級晶片1入埠 1開始，檢査其對應的輸入級晶片1到中 間級晶片A之間的已有時隙連接——可能是從輸入級晶片1到輸出級晶片2、 3或者4的一個連接)，按照步驟32，判斷是否有合適的空閒時隙為該已有連 接直接建立另一條通路；
a32)，如果存在直接重建連接的空閒時隙資源(如選擇中間級晶片B、 C 或者D作為其中間級晶片)，則為步驟a31中的已有連接重新建立新的連接 通路；
a33)，令當前業務源佔用該連接釋放出的空閒時隙資源，建立輸入級芯 片1和輸出級晶片1之間的時隙連接，返回成功信息後結束；否則，記錄步驟 a31中所有遍歷的已有時隙連接，進入步驟a34;
a34)，遍歷輸入級晶片1空閒出埠對應的輸出級晶片1入埠的已有 時隙連接(如從輸入級晶片1出埠 1開始，檢查其對應的輸出級晶片1到中 間級晶片A之間的已有時隙連接——可能是從輸入級晶片2、 3或者4到輸出 級晶片1的一個連接)，按照步驟32，判斷是否有合適的空閒時隙資源為該 已有連接直接建立另一條通路；
a35)，如果存在直接重建連接的空閒資源(如選擇中間級晶片B、 C或 者D作為其中間級晶片)，則為步驟a34中的已有連接重新建立新的連接通 路；
a36),令當前業務宿佔用該連接釋放出的空閒時隙資源，建立輸入級芯 片l和輸出級晶片l之間的時隙連接，返回成功信息後結束；否則，記錄步驟 a34中所有遍歷的已有時隙連接，進入步驟a37;
a37)，進入下一層次重構；該步驟又包括
a371)，選擇步驟a31中所有遍歷的已有連接的第1條，分別確定該連接 的業務源所屬晶片的空閒出埠和業務宿所屬晶片的空閒入埠；
a372)，遍歷業務宿所屬晶片空閒入埠對應的業務源所屬晶片出埠的 已有連接，按照步驟32，判斷是否有合適的空閒資源為該己有連接直接建立 另一條通路；
a373)，如果存在直接重建連接的空閒資源，則為步驟a372中的己有連 接重新建立新的連接通路；同時拆除步驟a371中的已有連接，其業務源和業 務宿佔用步驟a372中已有連接釋放出的空閒交叉粒度資源，建立新的連接， 返回到步驟a33。否則，記錄步驟a372中所有遍歷的已有連接，進入步驟a374;
a374)，遍歷業務源所屬晶片空閒出埠對應的業務宿所屬晶片入埠的 己有連接，按照步驟32，判斷是否有合適的空閒資源為該已有連接直接建立 另一條通路；
a375)，如果存在直接重建連接的空閒資源，則為步驟a374中的已有連 接重新建立新的連接通路；同時拆除步驟a371中的已有連接，其業務源和業 務宿佔用步驟a374中已有連接釋放出的空閒交叉粒度資源，建立新的連接， 返回步驟a36。否則，記錄步驟a374中所有遍歷的已有連接，進入步驟a376;
a376)，依次選擇步驟a31中所有遍歷的已有連接的第2條到最後一條， 重新進入步驟a371;如果重構成功，則返回成功信息後結束；如果重構仍然 失敗，進入步驟a377;
a377)，重新進入步驟a371，只不過把"步驟a31中所有遍歷的已有連接" 更換為"步驟a34中所有遍歷的已有連接"；以及
a378)，如果重構仍然失敗，則進入更下一層次的重構，重新進入步驟 a37，注意此時的"已有連接"是最近一次記錄的、更新層次的，因重構而需
要調整的已有連接數量將增加一條；
該步驟中，重構深度(層次數)M是大於l的整數，比如取4，則如果重
構深度M超過4而仍然無法建立相應的業務源到業務宿的連接，則返回失敗 信息後結束。
如圖7所示，為本發明一實施例的單播算法流程示意圖，該流程包括如下 步驟
步驟71，讀取業務源、業務宿以及業務粒度信息；
步驟72,判斷業務源和業務宿所在交換晶片是否有空閒連接資源，若有， 則進入步驟73，否則，返回失敗信息後結束；
步驟73，根據業務粒度大小的不同，採用不同的搜索方式，選擇一個直 接可用的中間級交叉單元；具體為
對於物理鏈路組連接，採用"洪泛"搜索方式；
對於物理鏈路連接，採用"絕對最小"搜索方式；
對於時隙連接，採用"絕對最大"搜索方式。
步驟74，判斷是否能夠搜索到一個直接可用的中間級交叉單元，若能夠， 則進入步驟75，否則，將重構深度M設為1，並進入步驟76;
步驟75，建立當前業務源和業務宿之間的連接，返回成功信息後結束；
步驟76，分別在業務源、業務宿所在晶片調整已有連接，根據被調整連 接業務顆粒的不同，在重構中分別採用"洪泛"、"絕對最小"、"絕對最大" 的搜索方式尋找空閒連接資源；以及
步驟77，判斷是否當前業務源或業務宿所需的空閒埠釋放，若釋放， 則進入步驟75,否則，將重構深度M執行加1操作，並進一步判斷此時的重 構深度M是否大於4，若大於4，則返回失敗信息後結束，否則，進入步驟 76。
如圖8所示，為本發明多播算法流程示意圖；該流程包括 步驟81，首先讀取業務源、業務宿以及業務粒度信息；
步驟82，確定當前連接是為單播連接還是為多播連接，如果當前連接為 單播，則轉入步驟86執行；如果當前連接為多播，則按照下述步驟83 85 進行，在業務路由建立和重構中針對不同業務粒度使用的搜索方式與單播情況 相同；
步驟83，如果可以在輸出級廣播，則在輸出級建立連接，返回成功信息 後結束；
步驟84，如果不能在輸出級廣播，看是否可以在中間級廣播，如果可以 在中間級建立連接，則在中間級建立連接，返回成功後結束；
步驟85，如果不能在中間級廣播，則調整己有連接，判斷是否有當前業 務宿所需的空閒埠釋放，如果有，則建立當前業務源和業務宿之間的連接， 返回成功信息後結束，否則，返回失敗信息後結束；以及
步驟86，如果為單播，按照單播算法流程進行。唯一不同的，在對單播 連接進行重構的過程中，先是對現存的單播連接進行査找並記錄，在經過單播 算法流程中步驟33的步驟333之後，對現存的多播連接進行査找，但不記錄；
上述步驟85，進一步包括以下步驟
步驟851，遍歷當前業務宿所屬交叉單元入埠部分的已有單播連接； 步驟852，按照步驟81，判斷是否能為步驟851中的已有單播連接直接建
立另一條通路。如果存在直接重建連接的通路，則重新建立步驟851中的連接，
並令步驟85中的業務源佔用該連接釋放出的空閒交叉粒度資源，建立連接，
返回成功信息後結束；否則，進入步驟853;
步驟853，如果不存在直接重建連接的通路，則記錄步驟851遍歷的所有
連接；
步驟854，遍歷當前業務宿所屬交叉單元入埠部分的己有多播連接； 步驟855，按照步驟82到步驟84，判斷是否能為步驟854中的已有多播 連接直接建立另一條通路。如果存在直接重建連接的通路，則重新建立步驟 854中的連接，並令步驟85中的業務源佔用該連接釋放出的空閒交叉粒度資 源，建立連接，返回成功信息後結束；否則，進入步驟856;
步驟856，對步驟853中記錄的連接，按照單播情況下的步驟33的步驟 337，進行下一層次的重構，並在重構中按照以上步驟854和855考慮多播連 接的重構，然後判斷是否能為步驟853中記錄的連接建立另一條通路；如果重 構成功，則為其建立新的連接，並令步驟85中的業務佔用該重構連接釋放出 的空閒交叉連接資源，建立連接，返回成功信息後結束；否則，進行再下一層 次的重構，重構深度(層次數)是大於1的整數，根據時間、計算資源等因素 確定，如果超過規定的重構深度而仍然無法建立相應的業務源到業務宿的連
接，則返回失敗信息後結束。
如圖9所示，以時隙連接為例，設需要建立從輸入級交換晶片1的第一個
物理鏈路組中的第一個物理鏈路內的第一個時隙到輸出級交換晶片1的第一 個物理鏈路組中的第一個物理鏈路內的第一個時隙的連接，以及到輸出級交換
晶片2的第二個物理鏈路組的第二個物理鏈路內的第二個時隙的多播連接。 對多播情況，按照圖IO所示的步驟進行處理，在業務路由建立和重構中
針對不同業務粒度使用的搜索方式與單播情況相同。
結合圖3、 7、 9，如圖10所示，為本發明一實施例的多播算法流程示意
圖，該流程包括
步驟1001，首先讀取業務源、業務宿以及業務粒度信息，確定當前連接 為單播還是多播；若為單播，則按照單播算法流程進行。該單播流程與圖7 所示的單播流程存在唯一不同之處，即在對單播連接進行重構的過程中，先是 對現存的單播連接進行査找並記錄，在經過單播算法流程步驟33的子步驟333 之後，才對現存的多播連接進行査找，但不記錄；若為多播，則執行多播算法 流程，進入步驟1002;
步驟1002，判斷多播是否可以在輸出級廣播，若可以，則進入步驟1007; 否則，進入步驟1003;
該步驟中，若多播可以在輸出級廣播，則在輸出級建立連接，是因為上述 多播連接需求的輸出級交換晶片有兩個，因此不能在輸出級建立連接；
步驟1003，若多播不能在輸出級廣播，則進一步判斷多播是否可以在中 間級廣播即搜索中間級晶片A D，看是否存在一個中間級晶片，保證實現 上述連接。例如，中間級晶片A滿足該需求，則通過中間級晶片A建立連接； 若可以，則進入步驟1007，否則，將重構深度N設為1，並進入步驟1004;
步驟1004，若多播不能在中間級廣播，則調整業務宿所在晶片的已有單 播和多播連接，根據被調整連接業務顆粒的不同，在重構中分別採用"洪泛"、 "絕對最小"、"絕對最大"的搜索方式尋找空閒連接資源-,
步驟1005，判斷是否有當前業務宿所需的空閒時隙釋放，若有，則進入 步驟1007;否則，進一步對重構深度N執行加1操作，並進入步驟1006;
步驟1006，判斷此時的重構深度N是否大於4，若是，則返回失敗信息 後結束，否則，進入步驟1004; 步驟1007，建立當前業務源和業務宿之間的連接，返回成功信息後結束。 上述步驟1004中，已有連接的調整進一步包括以下步驟
dl)，對當前業務宿所屬輸出級晶片1和/或晶片2的入埠部分的已有 單播連接進行檢査。例如，從輸入級交換晶片1的第一個物理鏈路組中的第一 個物理鏈路內的第一個時隙到輸出級交換晶片1的第一個物理鏈路組中的第 一個物理鏈路內的第一個時隙的連接可以通過中間級晶片B建立，這時，設 存在一個單播連接從輸入級晶片2經中間級晶片B到輸出級晶片2;
d2)，遍歷步驟dl中的已有單播連接，按照步驟1001，判斷是否能為其 直接建立另一條通路。如果存在直接重建連接的通路，則重新建立步驟dl中 的連接，並令步驟1004中從輸入級交換晶片1的第一個物理鏈路組中的第一 個物理鏈路內的第一個時隙到輸出級交換晶片2的第二個物理鏈路組的第二 個物理鏈路內的第二個時隙的連接佔用該連接釋放出的空閒時隙資源，建立連 接，返回成功信息後結束；否則，進入步驟d3;
d3)，如果不存在直接重建連接的通路，則記錄步驟d2遍歷的所有已有 單播連接；
d4)，遍歷當前業務宿所屬晶片入埠部分的已有多播連接，按照步驟 1002 1003，判斷是否能為已有多播連接直接建立另一條通路。如果存在直接 重建連接的通路，則重新建立該多播連接，並令步驟1004中從輸入級交換芯 片1的第一個物理鏈路組中的第一個物理鏈路內的第一個時隙到輸出級交換 晶片2的第二個物理鏈路組的第二個物理鏈路內的第二個時隙的連接佔用該 連接釋放出的空閒時隙資源，建立連接，返回成功信息後結束；否則，進入步 驟d5;
d5)，對步驟d3中記錄的連接，按照發明內容單播情況下的步驟33的子 步驟333，進行下一層次的重構，並在重構中按照以上步驟d4考慮多播連接 的重構，然後判斷是否能為步驟d3中記錄的連接建立另一條通路；如果重構 成功，則為其建立新的連接，並令步驟1004中從輸入級交換晶片1的第一個 物理鏈路組中的第一個物理鏈路內的第一個時隙到輸出級交換晶片2的第二 個物理鏈路組的第二個物理鏈路內的第二個時隙的連接佔用步驟d2或者步驟 d5中連接釋放出的空閒時隙資源，建立連接，返回成功信息後結束；否則， 進行再下一層次的重構，重構深度(層次數)M是大於l的整數，比如取4，
則如果重構深度M超過4而仍然無法建立相應的業務源到業務宿的連接，則 返回失敗信息後結束。
本發明提出一種三級CLOS交叉網絡實現多層粒度交叉連接的方法，給出 了單播、多播兩種情況下的算法流程，更好地解決方法適用性以及更好地平衡 重構阻塞率與重構速度的矛盾。
當然，本發明還可有其他多種實施例，在不背離本發明精神及其實質的情 況下，熟悉本領域的技術人員當可根據本發明作出各種相應的改變和變形，但 這些相應的改變和變形都應屬於本發明所附的權利要求的保護範圍。
權利要求
1、一種在三級CLOS交叉網絡中實現交叉連接的方法，其特徵在於，包括步驟一，讀取業務源、業務宿及業務粒度信息並確定當前連接為單播連接；步驟二，判斷所述業務源、所述業務宿所在的交換晶片是否有空閒連接資源，若沒有，返回一失敗信息後結束，否則，根據所述業務粒度信息中業務粒度的不同採用不同的搜索方式搜索一直接可用的中間級交叉單元並判斷是否搜索到所述直接可用的中間級交叉單元，若搜索到，則建立當前業務源與當前業務宿之間的連接，返回一成功信息後結束，否則，進入步驟三；步驟三，調整已有連接並判斷是否有當前業務源或業務宿所需的空閒埠釋放，若有，則建立當前業務源與當前業務宿之間的連接，返回一成功信息後結束，否則，返回一失敗信息後結束。
2、 根據權利要求1所述的在三級CLOS交叉網絡中實現交叉連接的方法， 其特徵在於，所述步驟二中，所述業務粒度分為最大業務粒度、次大業務粒 度及更小業務粒度。
3、 根據權利要求2所述的在三級CLOS交叉網絡中實現交叉連接的方法， 其特徵在於，所述步驟二中，當所述業務粒度為最大業務粒度時，還包括以洪 泛搜索方式搜索所述可用的中間級交叉單元的步驟，具體為步驟31，對當前業務源所屬輸入級交叉單元空閒出埠對應的最大粒度 連接，選擇順序數最小的最大粒度連接對應的中間級交叉單元為當前交叉單 元；及步驟32，在當前業務宿所屬輸出級交叉單元中，判斷與當前中間級交叉 單元對應的入埠是否有空閒的最大粒度連接，若有，則建立當前業務源和當 前業務宿之間的最大粒度連接，返回成功信息後結束；否則，判斷是否已經遍 歷所有當前業務源所屬輸入級空閒出埠對應的最大粒度連接，若是，則進入 所述步驟三；否則，選擇順序數次小的最大粒度連接對應的中間級交叉單元為 當前交叉單元，回到所述步驟32繼續執行。
4、 根據權利要求2所述的在三級CLOS交叉網絡中實現交叉連接的方法， 其特徵在於，所述步驟二中，當所述業務粒度為次大業務粒度時，還包括以絕對最小搜索方式搜索所述可用的中間級交叉單元的歩驟，具體為-步驟41，對當前業務源所屬輸入級交叉單元出埠對應的所有最大粒度 連接，選擇次大粒度已被佔用最少的最大粒度連接對應的中間級交叉單元為當 前中間級交叉單元；若同時存在符合條件的多個中間級交叉單元，則選擇順序 數最小的最大粒度連接對應的中間級交叉單元為當前中間級交叉單元；及步驟42，在當前業務宿所屬輸出級交叉單元中，判斷與當前中間級交叉 單元對應的入埠是否有空閒的次大粒度連接，若有，則建立當前業務源和當 前業務宿之間的次大粒度連接，返回成功信息後結束；否則，判斷是否已經遍 歷所有當前業務源所屬輸入級出埠對應的最大粒度連接，若是，則進入所述 步驟三；否則，順序選擇次大粒度連接利用次少的最大粒度連接對應的中間級 交叉單元為當前中間級交叉單元，回到所述步驟42繼續執行。
5、 根據權利要求2所述的在三級CLOS交叉網絡中實現交叉連接的方法， 其特徵在於，所述步驟二中，當所述業務粒度為更小業務粒度時，還包括以絕 對最大搜索方式搜索選擇所述可用的中間級交叉單元的步驟，具體為步驟51，對當前業務源所屬輸入級交叉單元出埠對應的待建業務粒度 的上一級粒度連接，選擇業務粒度已被佔用最多的上一級粒度連接對應的中間 級交叉單元為當前中間級交叉單元；若同時存在符合條件的多個中間級交叉單 元，則選擇順序數最小的上一級粒度連接對應的中間級交叉單元為當前交叉單 元；若需要佔用一新的上一級粒度連接，則從佔用粒度最少的更上一級粒度連 接中選擇，若同時存在符合條件的多個更上一級粒度連接，則選擇順序數最小 的更上一級粒度連接對應的中間級交叉單元為當前中間級交叉單元；及步驟52，在當前業務宿所屬輸出級交叉單元中，判斷與當前中間級交叉 單元對應的入埠是否有空閒的相應粒度的連接，若有，則建立當前業務源和 當前業務宿之間的更小粒度連接，返回成功信息後結束；否則，判斷是否已經 遍歷所有當前業務源所屬輸入級出埠對應的上一級粒度連接，若是，則進入 所述步驟三；否則，順序選擇粒度佔用次多的上一級粒度連接對應的中間級交 叉單元為當前中間級交叉單元，回到所述步驟52繼續執行。
6、 根據權利要求1-5任一所述的在三級CLOS交叉網絡中實現交叉連接 的方法，其特徵在於，所述步驟三中，所述調整已有連接的步驟具體為步驟61，遍歷當前業務宿所佔晶片空閒入埠對應的業務源所屬晶片出埠的已有連接並判斷是否有合適的空閒資源為該已有連接直接建立另一條通路；並當存在直接重建連接的空閒資源時，為該己有連接重新建立新的連接 通路；步驟62，令當前業務源佔用該已有連接釋放出的空閒交叉粒度資源，建 立連接並返回成功信息後結束；否則，記錄所述步驟61中所有遍歷的已有連 接；步驟63，遍歷當前業務源所佔晶片空閒出埠對應的當前業務宿所屬交 叉單元入埠的已有連接並判斷是否有合適的空閒資源為該已有連接直接建 立另一條通路；並當存在直接重建連接的空閒資源時，為該已有連接重新建立 新的連接通路；及步驟64，令當前業務宿佔用該已有連接釋放出的空閒交叉粒度資源，建 立連接並在返回成功信息後結束；否則，記錄所述步驟63中所有遍歷的已有 連接，進入下一層重構。
7、根據權利要求6所述的在三級CLOS交叉網絡中實現交叉連接的方法， 其特徵在於，所述步驟64中，所述進入下一層重構的步驟具體為步驟71，選擇所述步驟61中所有遍歷的已有連接的第l條，分別確定該 已有連接的業務源所屬晶片的空閒出埠和業務宿所屬晶片的空閒入埠；步驟72,遍歷業務宿所屬晶片空閒入埠對應的業務源所屬晶片出埠 的已有連接並判斷是否有合適的空閒資源為該己有連接直接建立另一條通路， 並當存在直接重建連接的空閒資源時，為該已有連接重新建立新的連接通路， 同時拆除所述步驟71中的已有連接，其業務源和業務宿佔用該已有連接釋放 出的空閒交叉粒度資源，建立新的連接並返回到所述步驟62;否則，記錄所 有遍歷的已有連接；步驟73，遍歷業務源所屬晶片空閒出埠對應的業務宿所屬晶片入埠 的已有連接並判斷是否有合適的空閒資源為該已有連接直接建立另一條通路； 並當存在直接重建連接的空閒資源時，則為所述步驟72中的已有連接重新建 立新的連接通路，同時拆除所述步驟71中的已有連接，其業務源和業務宿佔 用該已有連接釋放出的空閒交叉粒度資源，建立新的連接並返回到所述步驟 64;否則，記錄所有遍歷的已有連接；及歩驟74，依次選擇所述步驟61中所有遍歷的已有連接的第2條到最後一條，重新進入所述步驟71，若重構成功，返回成功信息後結束，若重構仍然 失敗，重新進入所述步驟71，並所述步驟61中所有遍歷的已有連接更換為所 述步驟63中所有遍歷的已有連接，並在重構失敗時，返回到所述步驟71。
8、 根據權利要求7所述的在三級CLOS交叉網絡中實現交叉連接的方法， 其特徵在於，所述步驟74中，所述重構的重構深度為大於1的整數，該重構 深度根據重構的時間、計算資源而確定。
9、 一種在三級CLOS交叉網絡中實現交叉連接的方法，其特徵在於，包括步驟91，讀取業務源、業務宿以及業務粒度信息並對當前連接進行判斷， 若當前連接為單播連接，則轉入步驟92，若當前連接為多播連接，則轉入步 驟93;步驟92，判斷所述業務源、所述業務宿所在的交換晶片是否有空閒連接 資源，若沒有，返回一失敗信息後結束，否則，根據所述業務粒度信息中業務 粒度的不同採用不同的搜索方式搜索一直接可用的中間級交叉單元並判斷是 否搜索到所述直接可用的中間級交叉單元，若搜索到，則建立當前業務源與當 前業務宿之間的連接，返回一成功信息後結束，否則，進入步驟94;步驟93，判斷所述多播連接能否在輸出級廣播，若能，則在所述輸出級 建立連接，返回一成功信息後結束，否則，進一步判斷所述多播連接能否在中 間級廣播，若能，則在所述中間級建立連接，返回一成功信息後結束，否則， 進入步驟94;及步驟94,調整已有連接並判斷是否有當前業務宿所需的空閒埠釋放， 若有，則建立當前業務源與業務宿之間的連接，返回一成功信息後結束，否則， 返回一失敗信息後結束。
10、根據權利要求9所述的在三級CLOS交叉網絡中實現交叉連接的方法， 其特徵在於，所述步驟94中，還包括步驟101，遍歷當前業務宿所屬交叉單元入埠部分的已有單播連接並判 斷是否能為該已有單播連接直接建立另一條通路，若存在直接重建連接的通 路，則重新建立該已有單播連接，並令所述業務源佔用該連接釋放出的空閒交 叉粒度資源，建立連接並返回成功信息後結束；否則，記錄遍歷的所有已有單 播連接；步驟102，遍歷當前業務宿所屬交叉單元入埠部分的已有多播連接並判 斷是否能為所述已有多播連接直接建立另一條通路，若存在直接重建連接的通 路，則重新建立所述已有多播連接並令所述業務源佔用該已有多播連接釋放出 的空閒交叉粒度資源，建立連接並返回成功信息後結束；否則轉入步驟103， 及；步驟103，對所述步驟101中所有已有單播連接按照單播連接時的重構步 驟進行下一層次的重構，並在重構中按照所述步驟102進行多播連接的重構， 其中，所述重構的重構深度為大於1的整數，所述重構深度根據重構的時間、 計算資源而確定。
11、根據權利要求9或IO所述的在三級CLOS交叉網絡中實現交叉連接 的方法，其特徵在於，所述步驟93、步驟94中，還包括在業務路由建立和重 構的步驟中根據業務粒度信息中業務粒度的不同採用不同的搜索方式搜索空 閒資源的步驟，具體為當所述業務粒度為最大業務粒度時，以洪泛搜索方式進行搜索；或 當所述業務粒度為次大業務粒度時，以絕對最小搜索方式進行搜索；或 當所述業務粒度為更小業務粒度時，以絕對最大搜索方式進行搜索。
全文摘要
本發明公開了一種在三級CLOS交叉網絡中實現交叉連接的方法，包括步驟一，讀取業務源、業務宿及業務粒度信息並確定當前連接為單播連接；步驟二，判斷業務源、業務宿所在的交換晶片是否有空閒連接資源，若沒有，返回一失敗信息後結束，否則，根據業務粒度信息中業務粒度的不同採用不同的搜索方式搜索一直接可用的中間級交叉單元，若搜索到，則建立當前業務源與當前業務宿之間的連接，否則，進入步驟三；步驟三，調整已有連接並判斷是否有當前業務源或業務宿所需的空閒埠釋放，若有，則建立當前業務源與當前業務宿之間的連接，否則，返回一失敗信息後結束。本發明解決現有方法適用性差以及更好地平衡重構阻塞率與重構速度的矛盾。
文檔編號H04L12/56GK101170485SQ20061011411
公開日2008年4月30日 申請日期2006年10月27日 優先權日2006年10月27日
發明者淵 古, 瀅 陶 申請人:中興通訊股份有限公司