[發(fā)明專(zhuān)利]一種CLOS交換網(wǎng)中選擇路由的方法及路由選擇裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 200710030152.6
• 申請(qǐng)日: 2007-09-10
• 公開(kāi)（公告）號(hào): CN101119503A
• 公開(kāi)（公告）日: 2008-02-06
• 發(fā)明（設(shè)計(jì)）人: 徐福紅
• 申請(qǐng)（專(zhuān)利權(quán)）人: 華為技術(shù)有限公司
• 主分類(lèi)號(hào): H04Q3/52
• 分類(lèi)號(hào): H04Q3/52;H04Q11/00
• 代理公司: 廣州三環(huán)專(zhuān)利代理有限公司
• 代理人: 郝傳鑫

技術(shù)領(lǐng)域

本發(fā)明涉及通信領(lǐng)域，尤其涉及一種CLOS交換網(wǎng)中選擇路由的方法及路由選擇裝置。

背景技術(shù)

最初的CLOS交換網(wǎng)是一種理論上的嚴(yán)格無(wú)阻塞的多級(jí)互連網(wǎng)絡(luò)，是由Charles?Clos于1953年提出的。CLOS交換網(wǎng)由于在通信網(wǎng)與多處理器計(jì)算機(jī)系統(tǒng)中被廣泛運(yùn)用，因而受到廣泛重視。CLOS交換網(wǎng)是由多個(gè)交換單元(又稱(chēng)集成單元)組成，每個(gè)交換單元包含n個(gè)輸入端口，m個(gè)輸出端口(m＞1，n＞1，如果m＝n，即為對(duì)稱(chēng)CLOS交換網(wǎng))。任意的前級(jí)到任意中央級(jí)有且只有一個(gè)連接供使用，同樣，任意的中央級(jí)到后級(jí)有且只有一個(gè)連接供使用。如圖1所示的CLOS交換網(wǎng)示意圖，從第一級(jí)的任意一個(gè)交換單元到第二級(jí)的任意一個(gè)交換單元，有且只有一條連線(一條路徑)，同理，對(duì)于第二級(jí)的任意一個(gè)交換單元到第三級(jí)的任意一個(gè)交換單元也是如此。但是，從第一級(jí)的任意一個(gè)交換單元到第三級(jí)的任意一個(gè)交換單元的可用路由數(shù)為m。其中，典型的CLOS交換網(wǎng)是三級(jí)全互連對(duì)稱(chēng)網(wǎng)絡(luò)，如圖2所示，包括第一級(jí)、第二級(jí)、第三級(jí)，對(duì)稱(chēng)的入線數(shù)目等于出線數(shù)目，三級(jí)對(duì)稱(chēng)CLOS交換網(wǎng)C(m，m，r)的輸入級(jí)有r個(gè)n×m交叉開(kāi)關(guān)，中間級(jí)有m個(gè)r×r交叉開(kāi)關(guān)，輸出級(jí)有r個(gè)m×n交叉開(kāi)關(guān)，網(wǎng)絡(luò)共有N＝n×r個(gè)輸入與輸出端口，每個(gè)中間級(jí)開(kāi)關(guān)與每個(gè)輸入、輸出開(kāi)關(guān)有且僅有1條鏈路連接。

通常，設(shè)計(jì)CLOS交換網(wǎng)結(jié)構(gòu)，其交換性能主要包括伸縮性、交換時(shí)延、數(shù)據(jù)傳輸?shù)淖月酚尚耘c有序性，以及如何處理網(wǎng)絡(luò)交換的碰撞沖突，即擁塞。在考慮降低擁塞的同時(shí)，我們也要考慮增加容量，大量上調(diào)m和n的數(shù)量，這樣會(huì)使實(shí)現(xiàn)交換單元的數(shù)量和交換網(wǎng)絡(luò)技術(shù)成本大大增加。為了使CLOS交換網(wǎng)的設(shè)計(jì)代價(jià)與交換性能折中，現(xiàn)有技術(shù)提供了一種路由算法，該算法提供了如圖3所示的CLOS交換網(wǎng)路由算法思想，主要包括：

假設(shè)CLOS交換網(wǎng)是由規(guī)格為n×m的交換單元組成(n代表交換單元輸入端口數(shù)目，m代表輸出端口數(shù)目)。給定輸入端口X(由于整個(gè)網(wǎng)絡(luò)對(duì)外是一個(gè)整體，所以這里的X與網(wǎng)絡(luò)中某個(gè)具體交換單元的端口編號(hào)是有區(qū)別的，如果該網(wǎng)絡(luò)輸入/輸出級(jí)有8個(gè)交換單元，那么X可以取1～n×8之間的任何值，表示業(yè)務(wù)從X端口進(jìn)入)；給定輸出端口Y(表示業(yè)務(wù)要從X端口到達(dá)與Y端口相連的設(shè)備)，假設(shè)完成后，即進(jìn)行下述流程；

s101，對(duì)于給定的輸入端口X，由X/n向上取整得到i，將輸入級(jí)第i個(gè)交換單元的輸出端口中沒(méi)有被占用的端口放在一個(gè)集合{I}里(已經(jīng)被占用的端口視為無(wú)效端口)，此時(shí){I}集合中的端口編號(hào)表示可以與中間級(jí)建立連接的輸入級(jí)交換單元；

s102，同樣，對(duì)于給定的輸出端口Y，由Y/n向上取整得到p，再將輸出級(jí)第p個(gè)交換單元的輸入端口中沒(méi)有被占用的端口放在集合{P}里，此時(shí)集合{P}中的端口編號(hào)表示可以與中間級(jí)建立連接的輸出級(jí)交換單元。

如果端口Z同時(shí)出現(xiàn)在集合{I}與集合{P}里，則表示包含輸入端口X的輸入級(jí)交換單元、包含輸出端口Y的輸出級(jí)交換單元均能與第Z個(gè)中間級(jí)交換單元建立連接。此時(shí)，建立連接的端口如圖3所示依次為：X→Z→i→p→W→Y，其中Z＝W。

但是，在選取中間級(jí)交換單元時(shí)，滿足上述通路要求的交換單元可能為多個(gè)，若在滿足通路要求的多個(gè)交換單元中以隨機(jī)方式選擇，就會(huì)雜亂無(wú)章；若按照編號(hào)從小到大順序選擇，則會(huì)造成小編號(hào)交換單元任務(wù)繁重、大編號(hào)交換單元閑置，不利于設(shè)備的使用。

發(fā)明人在實(shí)施本發(fā)明過(guò)程中發(fā)現(xiàn)：由于存在至少兩個(gè)滿足通路要求的中間級(jí)交換單元，隨機(jī)選擇或按照編號(hào)大小進(jìn)行選擇會(huì)造成中間級(jí)交換單元的選擇不平衡，不利于后續(xù)業(yè)務(wù)的路由選擇，從而造成系統(tǒng)各部分業(yè)務(wù)不平衡，降低系統(tǒng)工作效率。

發(fā)明內(nèi)容

本發(fā)明實(shí)施例所要解決的技術(shù)問(wèn)題在于，提供了一種CLOS交換網(wǎng)中選擇路由的方法，以及一種路由選擇裝置，可優(yōu)化中間級(jí)的路由選擇，使系統(tǒng)中各部分業(yè)務(wù)趨于平衡，提高系統(tǒng)工作效率。

為了解決上述技術(shù)問(wèn)題，本發(fā)明實(shí)施例提出了一種CLOS交換網(wǎng)中選擇路由的方法，包括：

獲得由中間級(jí)提供的、可在輸入級(jí)交換單元與輸出級(jí)交換單元之間承載當(dāng)前業(yè)務(wù)的路由集合；

計(jì)算所述路由集合中各路由對(duì)應(yīng)的、所述中間級(jí)對(duì)所述輸入級(jí)交換單元與輸出級(jí)交換單元后續(xù)業(yè)務(wù)的路由能力；

根據(jù)所述路由能力，從所述路由集合中確定一條用于在所述輸入級(jí)交換單元與輸出級(jí)交換單元之間承載當(dāng)前業(yè)務(wù)的路由。

相應(yīng)地，本發(fā)明實(shí)施例還提供了一種路由選擇裝置，包括：