[發明專利]一種用于輸入隊列交換機的混合隊列架構的混合調度方法

有效

• 申請號: 201910200066.8
• 申請日: 2019-03-15
• 公開（公告）號: CN110011934B
• 公開（公告）日: 2020-09-15
• 發明（設計）人: 黃煬;胡冰
• 申請（專利權）人: 浙江大學
• 主分類號: H04L12/861
• 分類號: H04L12/861;H04L12/863;H04L12/911;H04L12/931;H04L12/935
• 代理公司: 杭州求是專利事務所有限公司 33200
• 代理人: 林超

本發明公開了一種用于輸入隊列交換機的混合隊列架構與混合調度方法。輸入輸出端口之間經交換結構進行數據分組的傳輸，中心調度器執行調度算法并完成交換結構的配置，輸入端口中建立兩類虛擬輸出隊列，增設流虛擬輸出隊列；新到達輸入端口的數據分組經過濾器被分配至兩類虛擬輸出隊列中，由中心調度器采用整合幀預留和基于時隙的混合調度方法對輸入到輸入端口的數據分組進行調度并對交換機的交換結構進行配置。本發明能夠在兼容現有Internet輸入隊列交換機的虛擬輸出隊列技術的同時為確定性業務提供流粒度的QoS服務，減少分組進入隊列和離開隊列的時間，且能夠將未使用的預留資源共享給所有的非確定性業務，實現資源利用率最大化。

技術領域

本發明涉及輸入隊列交換機領域的一種調度方法，尤其涉及一種用于輸入隊列交換機的混合隊列架構與混合調度方法。

背景技術

隨著通信需求的快速增長，大量的具有嚴格的服務質量(QoS，QualityofService)的新應用(如工業自動化)，要求網絡可以提供有保證的QoS。但目前大多數商用交換機/路由器旨在實現更高的吞吐量和更低的互聯網盡力而為流量平均延遲，而無法提供有保證的QoS。充分利用交換機的同時，仍然給某些特定的流量提供確定性服務的問題一直尚未解決。

作為交換網絡中的核心設備，交換機/路由器是確定性網絡的重要組成部分。傳統的輸出隊列交換機可以通過在每個輸出端口采用一些帶寬預留算法(例如WFQ算法)來提供有保證的QoS。然而，輸出隊列交換機面臨著糟糕的N-Speedup問題，這使得它們難以應用于實際的高速交換網絡當中。輸入隊列交換機，無需進行N倍加速，更適合大規模交換網絡。為了消除線頭阻塞問題，輸入隊列交換機可以使用虛擬輸出隊列(VOQ)技術。

輸入隊列交換機的調度方式主要分為兩個方向：基于時隙和基于幀。

基于時隙的迭代調度算法采用迭代調度的策略，它根據每個VOQ的實時隊列狀態確定每個時隙輸入和輸出之間的匹配規則。迭代調度算法(例如，優先級iSLIP)通常分為三個步驟，包括：請求，授權和接受。

基于時隙的迭代調度算法著重于如何提高輸入和輸出之間的匹配效率，并且由于此類算法是基于實時隊列狀態而進行端口匹配，通常具有高資源利用率的特點。但這些算法的主要問題是它們無法實現資源預留或提供有保證的QoS。

基于幀的保證QoS調度算法假設可以通過一些預留協議(例如RSVP和SDN)預先知道每個端口對之間的業務需求。使用一個N×N的矩陣T描述在一個調度幀中，每個輸入和輸出端口對之間的確定性業務的預留時隙之和。

基于幀的調度算法需要將T分解為F置換子矩陣M_k。其中M_k表示該調度幀中第k個時隙的輸入輸出端口對的匹配規則。由于基于幀的調度是靜態的，因此如果預留的VOQ為空，則基于幀的調度方法面臨資源浪費的問題。

目前仍然缺乏一種高效的調度解決方案，不僅可實現與基于時隙的調度解決方案類似的高資源利用率，而且還能夠提供像基于幀的調度算法那樣的有保證的QoS服務。

發明內容

為了解決背景技術中存在的問題，本發明所提供一種用于輸入隊列交換機的混合隊列架構與混合調度方法，用以在實現在為確定性業務提供有保證的QoS的同時，能夠實現高資源利用率。

本發明采用的技術方案是：