[發(fā)明專利]路由數(shù)據(jù)分組以及確定路由的方法和裝置、胖樹網(wǎng)絡(luò)

有效

• 申請(qǐng)?zhí)枺?/td>: 201310627428.4
• 申請(qǐng)日: 2013-11-29
• 公開（公告）號(hào): CN103873367B
• 公開（公告）日: 2017-05-03
• 發(fā)明（設(shè)計(jì)）人: C·J·明肯伯格;G·羅德里格赫雷拉;M·格撒特
• 申請(qǐng)（專利權(quán)）人: 國際商業(yè)機(jī)器公司
• 主分類號(hào): H04L12/733
• 分類號(hào): H04L12/733;H04L12/703
• 代理公司: 中國國際貿(mào)易促進(jìn)委員會(huì)專利商標(biāo)事務(wù)所11038
• 代理人: 邊海梅

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

本發(fā)明一般涉及胖樹網(wǎng)絡(luò)中的無死鎖路由。

背景技術(shù)

胖樹網(wǎng)絡(luò)是包括以多根樹形拓?fù)溥B接的多個(gè)交換機(jī)的分層遞歸結(jié)構(gòu)網(wǎng)絡(luò)。這些網(wǎng)絡(luò)得到廣泛的普及并被用在許多現(xiàn)代的高性能計(jì)算系統(tǒng)和商業(yè)數(shù)據(jù)中心基礎(chǔ)設(shè)施中。胖樹拓?fù)浣Y(jié)構(gòu)存在大量變型，但從附圖的圖1中可以理解這些網(wǎng)絡(luò)的基本原理。其顯示了被稱為“k元n樹”的具體的非常規(guī)則的胖樹網(wǎng)絡(luò)的例子。在這種指定中，k為樹的數(shù)基(即在每一級(jí)中子和/或父的數(shù)量)，n是級(jí)數(shù)。k元n樹有n級(jí)交換機(jī)，每個(gè)交換機(jī)具有數(shù)基2k，其中一半端口向下連接，而另一半向上連接。(頂級(jí)中的交換機(jī)(即樹的根)在原理上只需要數(shù)基k，因?yàn)樗鼈儧]有父，但實(shí)際上這些端口可能存在并且是未連接的以允許未來網(wǎng)絡(luò)擴(kuò)展)。圖1的網(wǎng)絡(luò)是二進(jìn)制4樹，由此k＝2且n＝4，其中正方形表示交換機(jī)并且它們之間的線表示交換機(jī)間鏈路。交換機(jī)形成間接網(wǎng)絡(luò)拓?fù)涞幕ミB網(wǎng)絡(luò)，即末端節(jié)點(diǎn)(計(jì)算節(jié)點(diǎn)、服務(wù)器等)連接在網(wǎng)絡(luò)的邊緣處，從而在計(jì)算和聯(lián)網(wǎng)之間提供明確的區(qū)分。圖1中的末端節(jié)點(diǎn)由圓圈表示，并連接到交換機(jī)的底層，即樹拓?fù)涞娜~子。

經(jīng)由包括兩個(gè)路由階段的簡單路由過程，可在胖樹網(wǎng)絡(luò)中的任何一對(duì)末端節(jié)點(diǎn)之間傳輸分組。第一路由階段是“向上階段”，其中路由跟隨拓?fù)涞南蛏戏较?即朝向根)中的一個(gè)或多個(gè)交換機(jī)到交換機(jī)跳躍。這接著是“向下階段”，在“向下階段”中，路由跟隨拓?fù)涞南蛳路较蛑械囊粋€(gè)或多個(gè)交換機(jī)到交換機(jī)跳躍。利用這種路由策略，最短路徑路由是直接的，因?yàn)槁酚芍话ㄏ蛏?向下轉(zhuǎn)彎，而不包括向下/向上轉(zhuǎn)彎，從而避免了死鎖。(如果在通道依賴關(guān)系圖中的資源之間有循環(huán)依賴， 則死鎖可能發(fā)生，因?yàn)檫@可能導(dǎo)致網(wǎng)絡(luò)的操作中資源請(qǐng)求之間不可調(diào)和的沖突）。在任何源和目的地（未連接到相同的葉交換機(jī)）之間還有多條等長的路徑，從而使能網(wǎng)絡(luò)操作中的多條路徑和負(fù)載平衡。胖樹網(wǎng)絡(luò)還提供高平分帶寬，并且層次結(jié)構(gòu)易于擴(kuò)展到非常大的網(wǎng)絡(luò)。

由于胖樹網(wǎng)絡(luò)的間接特性，用于這些網(wǎng)絡(luò)的路由算法只處理從一個(gè)末端節(jié)點(diǎn)到另一個(gè)末端節(jié)點(diǎn)的流量，而不提供從網(wǎng)絡(luò)中的任何交換機(jī)到任何其它交換機(jī)的連接。完全的交換機(jī)到交換機(jī)連接將需要使用具有向上/向下轉(zhuǎn)彎的路由，而這些轉(zhuǎn)彎可以在網(wǎng)絡(luò)中引入死鎖，必須不惜一切代價(jià)避免死鎖。然而，直接的交換機(jī)到交換機(jī)連接對(duì)若干網(wǎng)絡(luò)管理功能來說可以是非常有益的，例如通信拓?fù)渥兓ü?jié)點(diǎn)和/或交換機(jī)的添加或去除）、本地故障事件（例如鏈路斷開）的分布以及診斷（測量任意交換機(jī)對(duì)之間的延遲或吞吐量）。此外，目前的InfiniBand交換機(jī)經(jīng)常具有需要與網(wǎng)絡(luò)中所有交換機(jī)連接的嵌入的子網(wǎng)管理器。（InfiniBand是InfiniBand貿(mào)易協(xié)會(huì)的商標(biāo)）。

在Bogdanski等人在ACM Trans.Architecture and Code Optimization、第8卷第4期、2012年1月的“sFtree：A fully connected and deadlock-free switch-to-switch routing algorithm for fat-trees”中描述了胖樹網(wǎng)絡(luò)中完全連接的提議。此提議指定在整個(gè)間接網(wǎng)絡(luò)拓?fù)鋬?nèi)的特定反轉(zhuǎn)的子樹，其中在路由期間向下/向上轉(zhuǎn)彎可能發(fā)生。如果傳統(tǒng)兩階段的向上-向下路由不提供源交換機(jī)和目的地交換機(jī)之間的連接，則使用四階段的向上-向下-向上-向下路由，其中，在指定的子樹中發(fā)生向下/向上轉(zhuǎn)彎。通過路由限制來避免硬件修改，例如使用作者認(rèn)為對(duì)于這些網(wǎng)絡(luò)不可取的虛擬通道，這提供了無死鎖的路由。提出的路由方法既不是最短路徑，也不能充分利用路徑多樣性。此外，因?yàn)樗谝粋€(gè)反轉(zhuǎn)的子樹中集中交換機(jī)到交換機(jī)流量，該網(wǎng)絡(luò)容易由于網(wǎng)絡(luò)故障而發(fā)生擁塞效應(yīng)和連接損失。