[發(fā)明專利]交換設(shè)備內(nèi)實(shí)現(xiàn)分組調(diào)度的方法及交換設(shè)備

有效

• 申請?zhí)枺?/td>: 200910000610.0
• 申請日: 2009-01-08
• 公開（公告）號: CN101478483A
• 公開（公告）日: 2009-07-08
• 發(fā)明（設(shè)計(jì)）人: 汪斌強(qiáng);于婧;鄭德任;周粳迪
• 申請（專利權(quán)）人: 中國人民解放軍信息工程大學(xué)
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京集佳知識產(chǎn)權(quán)代理有限公司
• 代理人: 逯長明

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

本發(fā)明涉及計(jì)算機(jī)通信技術(shù)領(lǐng)域，特別涉及交換設(shè)備內(nèi)實(shí)現(xiàn)分組調(diào)度的方法及交換設(shè)備。

背景技術(shù)

交換設(shè)備作為互聯(lián)網(wǎng)的主要節(jié)點(diǎn)設(shè)備，是網(wǎng)絡(luò)中進(jìn)行網(wǎng)間連接的關(guān)鍵，包括交換機(jī)和路由器等，目前的高性能交換設(shè)備多采用分布式體系結(jié)構(gòu)。由于交叉(crossbar)是目前高性能交換設(shè)備中最簡單常用的構(gòu)件，因此大多數(shù)商用路由器采用crossbar來構(gòu)建交換結(jié)構(gòu)。常用的基于crossbar的交換結(jié)構(gòu)依據(jù)排隊(duì)機(jī)制可分為：OQ(Output?Queued，輸出排隊(duì))，IQ(Intput?Queued，輸入排隊(duì))、CIOQ(Combined?Input-Output-Queued，聯(lián)合輸入輸出排隊(duì))和CIOQ(Combined?Input-Crosspoint-Queued，聯(lián)合輸入交叉點(diǎn)排隊(duì))。

上述任意一種交換結(jié)構(gòu)都是基于單一輸出端口，其影響和制約了交換設(shè)備的網(wǎng)絡(luò)性能，主要表現(xiàn)在：單一端口導(dǎo)致進(jìn)入交換設(shè)備的分組僅有唯一輸出端口，相同輸出端口的爭用極易引發(fā)交換擁塞，直接導(dǎo)致路由交換設(shè)備時延性能惡化，不利于支持實(shí)時業(yè)務(wù)；單一端口引發(fā)的交換擁塞不僅迫使交換設(shè)備采用內(nèi)部加速機(jī)制或復(fù)雜的調(diào)度機(jī)制，而且需要配合以高速大容量緩存機(jī)制，這些機(jī)制已成為高速路由交換設(shè)備的實(shí)現(xiàn)瓶頸；單一端口的路由機(jī)制使得當(dāng)前網(wǎng)絡(luò)的抗毀性能較差，單個網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)生故障會對網(wǎng)絡(luò)業(yè)務(wù)性能產(chǎn)生較大影響。

以一個4乘4交換結(jié)構(gòu)為例，如圖1所示，傳統(tǒng)路由交換機(jī)制由于報(bào)文僅有唯一的輸出端口，一旦四個輸入端口到達(dá)業(yè)務(wù)均具有相同的輸出端口時，僅有其中一個輸入端口的報(bào)文可以獲得調(diào)度輸出，其余輸入端口的報(bào)文被阻塞。由此可見，基于單一輸出端口的交換機(jī)制在存在端口爭用時的實(shí)時吞吐量很低，對于發(fā)生輸出端口爭用的重負(fù)載業(yè)務(wù)其擁塞程度還會不斷加劇。由于擁塞直接導(dǎo)致了交換設(shè)備的時延、時延抖動以及丟包率等方面的性能惡化，不利于對實(shí)時多媒體業(yè)務(wù)提供良好的性能支持，而且擁塞導(dǎo)致路由交換設(shè)備需要設(shè)置大量的緩存資源，增加了設(shè)備的硬件成本和實(shí)現(xiàn)難度。

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

本發(fā)明的目的在于提供交換設(shè)備內(nèi)實(shí)現(xiàn)分組調(diào)度的方法及交換設(shè)備，以解決現(xiàn)有技術(shù)中交換設(shè)備轉(zhuǎn)發(fā)報(bào)文的調(diào)度方式采用單一路徑，容易導(dǎo)致?lián)砣膯栴}。

為解決上述技術(shù)問題，本發(fā)明提供如下技術(shù)方案：

一種交換設(shè)備內(nèi)實(shí)現(xiàn)分組調(diào)度的方法，包括：

至少一個輸入調(diào)度器接收分組報(bào)文后，將所述分組報(bào)文輸入分組緩存器內(nèi)的分組隊(duì)列；

按照所述分組隊(duì)列的緊迫度從高到低的順序，將所述分組隊(duì)列輸出至對應(yīng)的輸出緩存器；

所述輸出緩存器根據(jù)接收到的分組隊(duì)列內(nèi)的分組報(bào)文的優(yōu)先級對所述分組報(bào)文進(jìn)行調(diào)度。

所述方法應(yīng)用于包含N個輸入調(diào)度器、N個分組緩存器、N個輸出緩存器的交換結(jié)構(gòu)，所述N為大于1的自然數(shù)；

每個所述分組緩存器包括N個虛擬輸出隊(duì)列、一個多播隊(duì)列和N乘N個帶緩存的交叉節(jié)點(diǎn)。

所述分組緩存器包括M個虛擬輸出隊(duì)列和一個多播隊(duì)列，所述M為大于1的自然數(shù)，所述將分組報(bào)文輸入分組緩存器內(nèi)的分組隊(duì)列包括：

判斷所述分組報(bào)文的類型；

當(dāng)所述分組報(bào)文為單播報(bào)文時，將所述分組報(bào)文輸入所述M個虛擬輸出隊(duì)列中最短的虛擬輸出隊(duì)列，當(dāng)所述分組報(bào)文為組播報(bào)文時，將所述分組報(bào)文輸出至所述多播隊(duì)列。

所述將分組報(bào)文輸入所述M個虛擬輸出隊(duì)列中最短的虛擬輸出隊(duì)列包括：

獲取所述分組報(bào)文的輸出端口標(biāo)簽；

按照最短優(yōu)先原則從所述輸出端口中對應(yīng)選擇進(jìn)入最短的虛擬輸出隊(duì)列的輸出端口；

將所述分組報(bào)文輸入所述選擇的輸出端口。

還包括M乘M個帶緩存的交叉節(jié)點(diǎn)，

所述按照分組隊(duì)列的緊迫度從高到低的順序，將所述分組隊(duì)列輸出至對應(yīng)的輸出緩存器包括：

分別定義所述分組隊(duì)列的緊迫度和根據(jù)所述分組隊(duì)列映射的邏輯隊(duì)列的緊迫度；

判斷所述分組報(bào)文所在分組隊(duì)列的緊迫度及所在邏輯隊(duì)列的緊迫度；

將所述分組隊(duì)列的緊迫度和邏輯隊(duì)列的緊迫度最高的分組報(bào)文輸入到對應(yīng)的交叉節(jié)點(diǎn)進(jìn)行緩存；

將緩存緊迫度最高的交叉節(jié)點(diǎn)所緩存的分組報(bào)文傳輸?shù)綄?yīng)的輸出緩存器。

所述輸出緩存器根據(jù)接收到的分組隊(duì)列內(nèi)的分組報(bào)文的優(yōu)先級對所述分組報(bào)文進(jìn)行調(diào)度包括：

調(diào)用預(yù)先設(shè)置的差額輪詢算法；

當(dāng)輪詢到當(dāng)前優(yōu)先級時，判斷預(yù)先為所述優(yōu)先級分配的計(jì)數(shù)器的值是否大于所述分組隊(duì)列的包長；

當(dāng)所述計(jì)數(shù)器的值大于所述分組隊(duì)列的包長時，輸出所述分組隊(duì)列內(nèi)的分組報(bào)文。