[發(fā)明專利]用于組合輸入交叉點(diǎn)緩存交換結(jié)構(gòu)的旋轉(zhuǎn)輪訓(xùn)調(diào)度方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201410558886.1
• 申請(qǐng)日: 2014-10-20
• 公開（公告）號(hào): CN104333516A
• 公開（公告）日: 2015-02-04
• 發(fā)明（設(shè)計(jì)）人: 李冰;程慧敏;劉勇;趙霞;董乾;王剛;陳德斌;陸清茹;許立峰
• 申請(qǐng)（專利權(quán)）人: 東南大學(xué)成賢學(xué)院
• 主分類號(hào): H04L12/865
• 分類號(hào): H04L12/865
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 熊玉瑋

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

本發(fā)明公開了用于組合輸入交叉點(diǎn)緩存交換結(jié)構(gòu)的旋轉(zhuǎn)輪訓(xùn)調(diào)度方法，屬于互聯(lián)網(wǎng)信息傳輸?shù)募夹g(shù)領(lǐng)域。

背景技術(shù)

計(jì)算機(jī)網(wǎng)絡(luò)規(guī)模的日益擴(kuò)大，主要體現(xiàn)在兩個(gè)方面，一個(gè)是互聯(lián)網(wǎng)用戶的迅猛增長(zhǎng)，使得交換網(wǎng)絡(luò)端口的密度增大，另一個(gè)是多媒體業(yè)務(wù)的增多，使得交換結(jié)構(gòu)輸入輸出端口的線速（line?Speed）不斷提高。另外，片上多處理器CMP(Chip?Multi-processor）逐漸成為主流，使得各個(gè)處理器核以及處理器與其它模塊(如cache）之間的互連(即片上網(wǎng)絡(luò)）及其通信速率成為了影響處理器性能的重要因素。以上問(wèn)題的解決都聚焦于交換系統(tǒng)的容量不斷擴(kuò)大，交換延時(shí)的不斷改善。

交叉開關(guān)(Crossbar）交換結(jié)構(gòu)由于其內(nèi)部無(wú)阻塞特性，即在同一時(shí)刻，允許多個(gè)無(wú)沖突的輸入輸出口之間并行傳輸數(shù)據(jù)，使其逐漸成為了現(xiàn)代交換機(jī)核心的首選結(jié)構(gòu)。尤其是近年來(lái)隨著硬件工藝水平的不斷發(fā)展，使得在交換結(jié)構(gòu)的各個(gè)交叉點(diǎn)處設(shè)置少量緩存成為了可能。為了進(jìn)一步提高系統(tǒng)的傳輸性能，組合輸入交叉點(diǎn)緩存交換結(jié)構(gòu)得到了普遍的應(yīng)用。它允許數(shù)據(jù)包在傳輸過(guò)程中先暫存在交叉點(diǎn)的緩存隊(duì)列中，再經(jīng)過(guò)輸出調(diào)度發(fā)送到輸出端。這種在輸入端和輸出端分別調(diào)度的結(jié)構(gòu)大大降低了所采用的調(diào)度算法的復(fù)雜度。但若要達(dá)到較高的時(shí)延性能，還需要輸入調(diào)度和輸出調(diào)度的完美配合。現(xiàn)有的組合輸入輸出調(diào)度算法由于存在指針同步（pointer?synchronization,?PS）現(xiàn)象，使得輸出端口無(wú)法做到盡職服務(wù)（working-conserving），從而增加了數(shù)據(jù)包的傳輸延時(shí)。

對(duì)該問(wèn)題的詳細(xì)介紹如下：

（1）?組合輸入交叉點(diǎn)緩存交換結(jié)構(gòu)（VOQ_CQ）

組合輸入交叉點(diǎn)緩存（Combined?Virtual?output?queue?and?Crosspoint?queue,?簡(jiǎn)稱VOQ_CQ）是在交叉開關(guān)(Crossbar）交換結(jié)構(gòu)的輸入端和交叉點(diǎn)處分別設(shè)置緩存，如圖1所示。輸入端的緩存采用虛擬輸出隊(duì)列（Virtual?Output?Queue，簡(jiǎn)稱VOQ），隊(duì)列的個(gè)數(shù)等于輸出端口的數(shù)目。交叉點(diǎn)緩存CQ有2個(gè)信元空間。?

輸入端口有數(shù)據(jù)包輸入時(shí)，根據(jù)其所要到達(dá)的目的端口的地址信息，將數(shù)據(jù)包緩存在對(duì)應(yīng)的虛擬輸出隊(duì)列中，輸入調(diào)度根據(jù)已定的調(diào)度順序?qū)?shù)據(jù)包發(fā)送到交叉點(diǎn)緩存，輸出調(diào)度結(jié)合當(dāng)前交叉點(diǎn)緩存的狀態(tài)及已定的調(diào)度法則將數(shù)據(jù)包發(fā)送到輸出端口。這種分布式的調(diào)度可以不用集中考慮輸入輸出端口的當(dāng)前狀態(tài)，大大降低了調(diào)度算法的復(fù)雜性。此外，任意交叉點(diǎn)處CQ（i,?j）緩存容量設(shè)置為兩個(gè)信元空間的策略也保證了傳輸過(guò)程的流水線操作。

（2）?現(xiàn)有算法的同步現(xiàn)象

目前，基于Crossbar交換結(jié)構(gòu)的調(diào)度算法已經(jīng)取得了很多的研究成果。它們大體上可以分為無(wú)隊(duì)列狀態(tài)信息的調(diào)度算法：如Random，RR（Round-Robin）等，和基于隊(duì)列狀態(tài)信息的調(diào)度算法：如LQF（longest?queue?first）,?OCF（oldest?cell?first）等。

適用于VOQ_CQ結(jié)構(gòu)的算法可以是上述調(diào)度算法的任意組合，如RR_RR,OCF_RR,LQF_OCF等。在考慮組合調(diào)度算法對(duì)系統(tǒng)性能的影響時(shí)，由于輸入調(diào)度起到關(guān)鍵的作用，所以我們重點(diǎn)分析一下輸入調(diào)度。

RR算法相對(duì)公平且易于實(shí)現(xiàn)，但基于Round-Robin規(guī)則的下一個(gè)隊(duì)列所對(duì)應(yīng)的CQ可能處于滿狀態(tài)，而且若對(duì)應(yīng)的輸出端口比較繁忙，最壞情況下，RR算法需要等待N個(gè)時(shí)槽（N為輸入端口的數(shù)目）數(shù)據(jù)包才能被從VOQ發(fā)送往CQ，進(jìn)而等待被轉(zhuǎn)發(fā)。即使其它的CQ處于空狀態(tài)也無(wú)法完成數(shù)據(jù)的轉(zhuǎn)發(fā)，從而造成其它的輸出端口不能做到盡職服務(wù)。

LQF算法與RR算法相比，雖然性能有所提升，但依然具有上述算法的缺點(diǎn)，另外其實(shí)現(xiàn)復(fù)雜度較高，最壞情況下也需要等待N個(gè)時(shí)槽，即LQF計(jì)算復(fù)雜度為0（N）。

同樣，OCF算法也有與上述兩個(gè)算法同樣的缺點(diǎn)。

目前已有的Crossbar調(diào)度算法方面的資料，給出了一種基于反饋機(jī)制的調(diào)度算法，但其是適用于兩級(jí)交換結(jié)構(gòu)的調(diào)度算法，而且沒有考慮到多個(gè)輸入端口時(shí)的去同步機(jī)制。

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

本發(fā)明所要解決的技術(shù)問(wèn)題是針對(duì)上述背景技術(shù)的不足，提供了用于組合輸入交叉點(diǎn)緩存交換結(jié)構(gòu)的旋轉(zhuǎn)輪訓(xùn)調(diào)度方法。

本發(fā)明為實(shí)現(xiàn)上述發(fā)明目的采用如下技術(shù)方案：

用于組合輸入交叉點(diǎn)緩存交換結(jié)構(gòu)的旋轉(zhuǎn)輪訓(xùn)調(diào)度方法，?包括如下步驟：

輸入端口設(shè)置有輪詢調(diào)度虛擬輸出組中各虛擬輸出隊(duì)列的優(yōu)先級(jí)指針，