[發(fā)明專利]在笛卡爾拓?fù)涞木W(wǎng)絡(luò)中構(gòu)建無死鎖路由的方法和裝置

有效

• 申請?zhí)枺?/td>: 201711192650.0
• 申請日: 2017-11-24
• 公開（公告）號: CN108111410B
• 公開（公告）日: 2021-08-10
• 發(fā)明（設(shè)計）人: 弗拉基米爾·茲多爾諾夫;埃坦·扎哈維
• 申請（專利權(quán)）人: 特拉維夫邁絡(luò)思科技有限公司
• 主分類號: H04L12/703
• 分類號: H04L12/703;H04L12/721;H04L12/733;H04L12/861;H04L12/947
• 代理公司: 北京德崇智捷知識產(chǎn)權(quán)代理有限公司 11467
• 代理人: 申雪梅

1.一種用于在具有笛卡爾拓?fù)涞木W(wǎng)絡(luò)中構(gòu)建無死鎖路由的裝置，包括：

網(wǎng)絡(luò)接口，配置為與一個網(wǎng)絡(luò)進(jìn)行通信，所述網(wǎng)絡(luò)包括在多維度的笛卡爾拓?fù)渲邢嗷ミB接的多個交換機(jī)；以及

處理器，其配置為：

預(yù)定義笛卡爾拓?fù)涞木S度中的順序；

通過基于至少沿著候選路由的相應(yīng)數(shù)量的交換機(jī)來評估候選路由，以搜索經(jīng)由網(wǎng)絡(luò)從源交換機(jī)到目標(biāo)交換機(jī)的路由，所述路由到下一跳交換機(jī)的遍歷與預(yù)定義順序相反地從一個維度變化到另一維度，從而選擇從源到目標(biāo)的多個路由，其具有與預(yù)定順序相反的最大數(shù)量的下一跳交換機(jī)變化；

對應(yīng)于與預(yù)定順序相反的最大數(shù)量的下一跳交換機(jī)變化，為路由器配置多個虛擬通道（VL），以及

配置網(wǎng)絡(luò)中的交換機(jī)，以沿著選擇的多路由的優(yōu)選路由將來自源交換機(jī)的數(shù)據(jù)包路由到目標(biāo)交換機(jī)。

2.根據(jù)權(quán)利要求1所述的裝置，其中，處理器配置成對交換機(jī)進(jìn)行配置，以為每個交換機(jī)分配多個虛擬緩沖，虛擬緩沖的數(shù)量為遍歷改變與預(yù)定義順序相反的交換機(jī)的最大數(shù)量的整數(shù)倍。

3.根據(jù)權(quán)利要求1所述的裝置，其中，處理器配置成對交換機(jī)進(jìn)行配置，使得所述交換機(jī)重新關(guān)聯(lián)數(shù)據(jù)包，所述數(shù)據(jù)包與給定虛擬通道（VL）相關(guān)聯(lián)地被接收并且所述數(shù)據(jù)包在下一跳中與預(yù)定順序相反地開始遍歷一個不同維度，具有與給定VL不同的VL。

4.根據(jù)權(quán)利要求1所述的裝置，其中，處理器配置成通過為源交換機(jī)的給定入口接口定義至少兩個出口接口來為交換機(jī)定義自適應(yīng)路由規(guī)則，用于將數(shù)據(jù)包從源交換機(jī)路由到目標(biāo)交換機(jī)而不超過源交換機(jī)的VL預(yù)算，并且配置成對交換機(jī)進(jìn)行配置，以使用至少兩個出口接口來應(yīng)用從源交換機(jī)到目標(biāo)交換機(jī)的自適應(yīng)路由。

5.根據(jù)權(quán)利要求4所述的裝置，其中，通過考慮入口數(shù)據(jù)包的VL值和入口接口以及通過經(jīng)由兩個或多個出口接口中的每一個的路由和通過源交換機(jī)而導(dǎo)致的多次反向轉(zhuǎn)向，處理器配置為定義至少兩個出口接口。

6.根據(jù)權(quán)利要求1所述的裝置，其中，處理器配置成對交換機(jī)進(jìn)行配置，以利用自適應(yīng)路由沿著選擇的多路由而路由數(shù)據(jù)包。

7.根據(jù)權(quán)利要求1所述的裝置，其中，處理器配置成對交換機(jī)進(jìn)行配置，以沿著優(yōu)選路由將數(shù)據(jù)包從源交換機(jī)路由到目標(biāo)交換機(jī)，并且，當(dāng)沿著優(yōu)選路由的交換機(jī)或鏈路故障時，使用選擇的多路由的其它路由。

8.根據(jù)權(quán)利要求1所述的裝置，其中，處理器配置成搜索需要最小數(shù)量的反向轉(zhuǎn)換的路由。

9.根據(jù)權(quán)利要求1所述的裝置，其中，處理器配置成，通過以廣度優(yōu)先搜索順序從目標(biāo)交換機(jī)開始遍歷網(wǎng)絡(luò)的交換機(jī)，來搜索路由。

10.根據(jù)權(quán)利要求9所述的裝置，其中，處理器配置為遍歷交換機(jī)，以選擇下一跳交換機(jī)，通過選擇的下一跳交換機(jī)，優(yōu)選路由具有相鄰的交換機(jī)之間的最短路徑。

11.根據(jù)權(quán)利要求9所述的裝置，其中，處理器配置為遍歷交換機(jī)，以選擇下一跳交換機(jī)，對于所述下一跳交換機(jī)，從源交換機(jī)遍歷的維度在相鄰的交換機(jī)之間按照順序是最高的。

12.根據(jù)權(quán)利要求9所述的裝置，其中，處理器配置為遍歷交換機(jī)，以為每個當(dāng)前的交換機(jī)確定沿著從當(dāng)前的交換機(jī)到目標(biāo)交換機(jī)的路由的多個反向轉(zhuǎn)換。

13.根據(jù)權(quán)利要求12所述的裝置，其中，處理器配置為遍歷交換機(jī)，以為每個交換器確定從當(dāng)前交換機(jī)到目標(biāo)交換機(jī)的距離。

14.根據(jù)權(quán)利要求9所述的裝置，其中，處理器配置為遍歷交換機(jī)，以為每個當(dāng)前的交換機(jī)確定朝向目標(biāo)交換機(jī)在當(dāng)前的交換機(jī)和朝下一跳交換機(jī)之間遍歷的維度。