[發明專利]一種隊列調度方法及裝置

有效

• 申請號: 201410411353.0
• 申請日: 2014-08-20
• 公開（公告）號: CN104144134A
• 公開（公告）日: 2014-11-12
• 發明（設計）人: 董君
• 申請（專利權）人: 杭州華三通信技術有限公司
• 主分類號: H04L12/863
• 分類號: H04L12/863
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 梁少微;王麗琴

技術領域

本發明涉及網絡通信技術領域，特別涉及一種隊列調度方法及裝置。?

背景技術

加權輪詢調度(WRR，Weighted?Round?Robin)隊列是數通設備支持的一種隊列形式。其有如下幾個特征：1、每組有若干個隊列，如1.2…N；2、每個隊列可以指定份額，通常以字節(Byte)為單位，也可以指定權重；3、一組隊列可以應用到接口上。?

現有WRR隊列調度采用份額輪詢的方式調度，當前隊列的份額消耗完后，增加對應的份額，轉而進行下一隊列的調度，以到達按配置份額調度的目的。當多個隊列配置較大份額時，每次輪詢份額需要消耗完再進行下一輪隊列調度，隊列可能獨自占用較大的時間片，同一隊列再次發送的間隔也較大。從較短的時間片來評估隊列，公平性較差。?

發明內容

為實現上述發明目的，本發明提供了一種隊列調度方法，所述隊列為加權輪詢調度WRR隊列，該方法包括：?

建立以隊列勢能為關鍵值的完全二叉樹，所述完全二叉樹的節點與擁塞隊列一一對應；?

在報文入隊或者出隊時，基于隊列勢能值對所述隊列對應的節點在所述完全二叉樹中的位置進行調整，使得完全二叉樹上所有父節點的勢能值均小于等于子節點的勢能值。?

為實現上述發明目的，本發明還提供了一種隊列調度裝置，所述隊列為加權輪詢調度WRR隊列，該裝置包括：?

樹建立模塊，用于建立以隊列勢能為關鍵值的完全二叉樹，所述完全二叉樹的節點與擁塞隊列一一對應；?

隊列調度模塊，用于在報文入隊或者出隊時，基于隊列勢能值對所述隊列對應的節點在所述完全二叉樹中的位置進行調整，使得完全二叉樹上所有父節點的勢能值均小于等于子節點的勢能值。?

綜上所述，本發明實施例中，采用完全二叉樹加權重的方式實現WRR隊列調度。通過本發明的隊列調度方式，使得隊列獨自占用的時間片很短，同一隊列再次發送的間隔也很短，從較短的時間片來評估隊列，隊列調度更加公平。?

附圖說明

圖1為本發明提出一種隊列調度方法的流程示意圖。?

圖2為本發明提出一種入隊調度方法的流程示意圖。?

圖3為本發明提出一種出隊調度方法的流程示意圖。?

圖4為本發明實施例隊列調度裝置的結構示意圖。?

具體實施方式

以下參照附圖，對本發明實施例作進一步地詳細說明。?

為更好地說明本發明，下面簡單介紹一下有關WRR隊列的概念。?

WRR有多個隊列Q，各個隊列定義為Q[1],Q[2],Q[3],…,Q[N]；?

每個隊列有一個輪詢值V，V[1],V[2],V[3],…,V[N]；?

每個隊列有一個權重值W，W[1],W[2],W[3],…W[N]，WRR隊列公用一個常數C。W由計算所得，W[1]＝C/V[1],W[2]＝C/V[2],W[3]＝C/V[3],…,W[N]＝C/V[N]。(說明：C的取值決定了C/W的精度，建議C的取值是各隊列W最大值的100倍或以上)。?

每個隊列有一個勢能P，P[1],P[2],P[3],…,P[N]，P是W和L之積的累加值。L表示一個報文的長度。因此，本發明中隊列的勢能P由W和L?決定，用于作為完全二叉樹的關鍵值，在報文入隊和出隊時，根據勢能值進行完全二叉樹的重構。?

現有技術中，WRR隊列調度采用份額輪詢的方式調度，比如，每個報文長度為1000個字節，兩隊列分別配置份額100000及200000，則，隊列1＝份額100000/1000字節＝100個報文；隊列2＝200000/1000字節＝200個報文。也就是說，需要隊列1發完100個報文之后，隊列2再發200個報文，必須等待隊列2發完200個報文后，才能重新進行隊列1的調度。這樣，在長時間來看，兩個隊列發報文的比例雖然是1：2，但是在較短的時間內來看，總是在發同一個隊列的報文，因此隊列的短期公平性難以體現。?

本發明為體現短期公平性，采用完全二叉樹加權重的方式實現WRR隊列調度。WRR一組擁塞隊列以P為關鍵(Key)值建立一棵完全二叉樹，也可將此完全二叉樹稱之為堆。本發明中將報文緩沖到一個空隊列，該隊列就成為擁塞隊列，每個擁塞隊列作為堆的一個節點，隊列的示意如下；?