[發明專利]一種定長包加權公平排隊調度方法及裝置

有效

• 申請號: 201210246793.6
• 申請日: 2012-07-17
• 公開（公告）號: CN103546390B
• 公開（公告）日: 2018-05-18
• 發明（設計）人: 黃煒;孫明施
• 申請（專利權）人: 中興通訊股份有限公司;深圳市中興微電子技術有限公司
• 主分類號: H04L12/861
• 分類號: H04L12/861
• 代理公司: 北京派特恩知識產權代理有限公司 11270
• 代理人: 張穎玲;蔣雅潔

本發明公開了一種定長包加權公平排隊調度方法及裝置，本方法中，在計數器的當前計數時刻下完成調度鏈表的任務調度后，分別計算各非空調度鏈表中大于所述當前計數時刻方向上距離當前計數值最近的待調度計數值，將計算出的待調度計數值中距離所述當前計數值最近的一個作為下一計數值。本方案采用了一種最小差距算法替代原專利中的計數器累加算法，克服計數器累加算法迭代次數過多的問題，使計數器累加算法適應高速的調度要求。

技術領域

本發明涉及數據通信類芯片的隊列調度技術，尤其涉及一種定長包加權公平排隊加權公平排隊（Weighted Fair Queuing，簡稱WFQ）調度方法及裝置。

背景技術

數據通信類芯片不可避免要涉及到流量管理，流量管理的核心是隊列調度技術。WFQ調度技術是RR，WRR，DWRR等各種調度算法中是性能最好的一種，也是一種較理想的調度算法，但實現復雜度高，要達到較高的性能比較困難。

在數據通信類芯片的帶寬逐漸提高的同時，調度方式逐漸向基于代表固定字節數的授權調度方向發展，授權的調度方式基本和定長包的調度方式類似。這里提到的也主要是基于定長包或授權的WFQ調度算法。

在國際公開號為WO03084283A2的專利中提到一種WFQ調度算法，如下為該專利的實現方式：

因為定長包或授權的調度的帶寬分配實際上就是調度機會的分配，因此需要用計數器來計算和控制調度機會的分配。如果帶寬的分配精度最小可以達到1/16，則相應地需要一個計數范圍為0-15的計數器控制調度機會的分配。為了保證調度機會能夠均勻地進行分配，可以對各個權重等級對應的調度機會進行規定，使相應權重的flow能夠以均勻地間隔獲調度機會，規定如下：

對于1:4K的WFQ調度器，可以設置的最小權重為1/4096，需要的比特數為12比特，每一位分別對應1/2，1/4，1/8…1/4096，為每個權重比特設置1個調度鏈表，調度鏈表由待發放調度機會的flow組成，共12個調度鏈表；設置一個12位計數器，12個調度鏈表和計數器的對應關系如表1所示：

表1