[發(fā)明專利]一種CICQ結構交叉緩存隊列均衡的分組調度算法

在審

• 申請?zhí)枺?/td>: 201510733429.6
• 申請日: 2015-11-02
• 公開（公告）號: CN105429898A
• 公開（公告）日: 2016-03-23
• 發(fā)明（設計）人: 熊慶旭;張元昊
• 申請（專利權）人: 北京航空航天大學
• 主分類號: H04L12/863
• 分類號: H04L12/863
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發(fā)明屬于高性能分組交換機控制技術領域。

背景技術

到目前為止，人們對高性能的聯合輸入交叉點排隊(CombinedInputandCrossbarQueued，CICQ)結構的調度算法進行了大量研究，經典的主流算法分為基于輪詢RR(Round-Robin)和最大權重匹配算法兩大類型?；赗R的算法主要有RR-RR、DRR(DifferentialRound-Robin)、TFQA(TrackingFairQuotaAllocation)、RR-LQD(LongestQueueDetecting)等。基于權重的最大匹配法主要包括以隊長、交叉緩存占用率、阻塞時間為權重的最大權重匹配法，包括LQF-RR(LongestQueueFirstandRR)、MCBF(MostCriticalBufferFirst)、SCBF(ShortestCrosspointBufferFirst)、SBF-GWF(theShortestbufferFirstandtheGreatestWeighbufferFirst)、HOPS(HybridOptimizationPacketScheduling)、MCQF(MostCriticalQueueFirst)等。RR及其改進算法實現簡單，復雜度一般為O(1)，且大多數算法對可接入的均勻業(yè)務的通過率接近100％，但分組平均時延較大。最大權重匹配法以復雜度增大為代價來獲取分組時延的下降。例如代表性的MCBF算法以特定輸出和輸入端口對應的crossbar中緩存的分組數目為權重，充分利用crossbar資源，但沒有考慮VOQ的隊列長度。而近來提出的SBF-GWF算法，在MCBF的基礎上，進一步地，輸出調度采用VOQ隊長為權重，相比MCBF及其他算法，時延性能有顯著的提高。

在已有的CICQ調度算法的研究中，即使是性能突出的SBF-GWF算法，相比采用最簡單的FIFO(FirstInFirstOut)算法的輸出排隊(OQ)結構，時延性能依然有較大差距。根本原因在于OQ結構交換機能夠工作于work-conserving狀態(tài)，確保達到100％的通過率，從而使得時延下降。但是OQ結構較高的加速比使得其可擴展性受限，在大規(guī)模高速交換中不具有實用價值。

基于上述分析，不同于已有的算法，本發(fā)明以最大程度逼近交換機工作于work-conserving狀態(tài)為核心，提出了CICQ結構中的一種新的分組輸入調度算法，即交叉緩存隊列均衡(CrossbufferQueueBalance,CQB)算法。本發(fā)明提供的CQB算法以輸出端口為匹配基準，選擇交叉緩存(crossbuffer)隊列長度最小的輸出端口優(yōu)先匹配，盡量均衡所有輸出端口的crossbuffer分組占用，以盡可能地使得交換機逼近工作于work-conserving狀態(tài)，在提高交換機通過率的同時，降低分組的平均時延。

發(fā)明內容

本發(fā)明的目的是提供針對crossbuffer緩存容量為一個分組的CICQ結構交換機最大程度工作于work-conserving狀態(tài)，且具有良好的通過率和平均分組時延性能的分組輸入調度算法。為實現上述目的，本發(fā)明采用的技術路線為：

第一步初始化端口集合；

每個時隙開始時，令輸出端口集合OP包含所有輸出端口，輸入端口集合IP包含所有輸入端口；

第二步判斷調度是否結束；

如果OP為空，則該時隙輸入調度結束；否則，進入第三步；

第三步選擇待匹配的輸出端口；

從指針po指向的輸出端口開始，在OP中選擇第一個crossbar隊列長度B_j最小的輸出端口j，并將po指向其下一個輸出端口的位置；

其中B_j表示輸出端口j的crossbar隊列長度，po為輸出端口的優(yōu)先級指針，其在整個調度初始時指向輸出端口1；

第四步檢驗選擇的輸出端口是否有合適的輸入端口與之匹配；

如果EIP_j與IP的交集WEIP_j為空，從OP中剔除輸出端口j，回到第二步；

其中CB_ij表示輸入端口i和輸出端口j對應的交叉緩存(crossbuffer)，EIP_j表示滿足VOQ_ij不為空且CB_ij為空的所有輸入端口i的集合；

第五步為等待匹配的輸出端口選擇合適的輸入端口與之匹配；