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

有效

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

1.一種隊列調度方法，所述隊列為加權輪詢調度WRR隊列，其特征在于，該方法包括：

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

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

2.如權利要求1所述的方法，其特征在于，在報文入隊時，進行入隊調度，該方法包括：

將報文緩沖到一個空隊列，以使該空隊列成為首次擁塞的隊列；

將該首次擁塞的隊列作為完全二叉樹的一個節點，加入到以隊列勢能為關鍵值的完全二叉樹的最后一個節點的后面；

基于隊列勢能值對該首次擁塞的隊列對應的節點在所述完全二叉樹中的位置進行調整，使得完全二叉樹上所有父節點的勢能值均小于等于子節點的勢能值。

3.如權利要求1所述的方法，其特征在于，在報文出隊時，進行出隊調度，該方法包括：

將根節點隊列緩沖的首報文出隊，以使該根節點隊列成為首報文出隊隊列；

根據報文長度和首報文出隊隊列的權重值，更新首報文出隊隊列的勢能值；

判斷首報文出隊后，該首報文出隊隊列是否為空，當不為空時，

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

4.如權利要求3所述的方法，其特征在于，該方法進一步包括：

當首報文出隊后，該首報文出隊隊列為空，且在將該空的首報文出隊隊列移出時所述完全二叉樹不為空時：

將該首報文出隊隊列對應的節點移出，將完全二叉樹上最后一個節點移到根節點的位置；

基于隊列勢能值對該被移到根節點位置節點在所述完全二叉樹中的位置進行調整，使得完全二叉樹上所有父節點的勢能值均小于等于子節點的勢能值。

5.如權利要求3所述的方法，其特征在于，該方法進一步包括：

當首報文出隊后，該首報文出隊隊列為空，且在將該空的首報文出隊隊列移出時所述完全二叉樹也為空時：

將該首報文出隊隊列對應的節點移出，將該首報文出隊隊列移除之前對應的更新勢能值作為完全二叉樹的初始勢能。

6.如權利要求3或5所述的方法，其特征在于，所述根據報文長度和首報文出隊隊列的權重值，更新首報文出隊隊列的勢能值的方法包括：

根據P_更新＝P+W*L，其中，W表示首報文出隊隊列的權重值，L表示報文的長度，P_更新表示以該首報文出隊隊列更新前的勢能值進行W和L之積的累加，以P_更新對首報文出隊隊列的勢能值進行更新。

7.一種隊列調度裝置，所述隊列為加權輪詢調度WRR隊列，其特征在于，該裝置包括：

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

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

8.如權利要求7所述的裝置，其特征在于，在報文入隊時，進行入隊調度，所述隊列調度模塊進一步包括：

緩沖單元，用于將報文緩沖到一個空隊列，以使該空隊列成為首次擁塞的隊列；

入堆調度單元，用于將該首次擁塞的隊列作為完全二叉樹的一個節點，加入到以隊列勢能為關鍵值的完全二叉樹的最后一個節點的后面；基于隊列勢能值對該首次擁塞的隊列對應的節點在所述完全二叉樹中的位置進行調整，使得完全二叉樹上所有父節點的勢能值均小于等于子節點的勢能值。