[發明專利]一種基于動態權重計算的隊列調度方法

有效

• 申請號: 201410216080.4
• 申請日: 2014-05-21
• 公開（公告）號: CN104009936B
• 公開（公告）日: 2017-12-01
• 發明（設計）人: 楊國英;閆魯生;于永學
• 申請（專利權）人: 邦彥技術股份有限公司;中國人民解放軍91655部隊
• 主分類號: H04L12/865
• 分類號: H04L12/865
• 代理公司: 廣州嘉權專利商標事務所有限公司44205
• 代理人: 唐致明

技術領域

本發明涉及通信技術領域，尤其涉及一種基于動態權重計算的隊列調度方法。

背景技術

目前，隨著網絡通信技術的飛速發展，人們對網絡的服務質量、性能等提出了更高的要求。隊列調度方法作為保證網絡有效性和實用性的重要技術，對網絡服務質量起著非常重要的作用。現有的隊列調度方法主要有SP、FIFO、RR等，FIFO根據數據包到達的先后時間進行調度，即先到先服務，但是這種方法沒有考慮實際的業務應用需要。嚴格優先級調度方法根據隊列優先級進行調度，優先級高的隊列調度完后再調度低優先級隊列，可能導致低優先級隊列長時間得不到服務。RR調度方法按照比例對多個隊列進行調度，該方法具有較好的公平性，但是無法保證隊列的優先級。

現有的加權輪詢調度算法，即加權輪詢算法，其基本思想是給不同的隊列賦予不同的權值，加權輪詢調度器工作于循環模式，按順序服務數據隊列。當每次輪詢時，每一隊列根據其權重值決定被發送出去數據包的數量。如果某一隊列的數據包數量小于權重值，則加權輪詢調度器就調度下一隊列中的數據包。加權輪詢算法具有一定的公平特性，但是該算法的權重值是固定分配的，不能根據網絡的負載狀況實現動態的帶寬資源分配。

發明內容

為了解決上述技術問題，本發明的目的是提供一種能動態調整權重值，提高靈活性的一種基于動態權重計算的隊列調度方法。

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

一種基于動態權重計算的隊列調度方法，包括以下步驟：

A、接收數據包，并對其進行分類進而將其存放于對應的業務隊列中；

B、讀取測量每個業務隊列中數據包的信息；

C、根據讀取的各業務隊列中數據包的信息和收益最大判斷準則，計算各個業務隊列的最優權重值；

D、根據計算得到各業務隊列的最優權重值，加權輪詢調度器對業務隊列中的數據包進行調度輸出。

作為所述的一種基于動態權重計算的隊列調度方法的進一步改進，所述步驟A包括：

A1、接收數據包并讀取其帶寬需求和時延需求；

A2、根據數據包的帶寬需求和時延需求，將其分為A類業務數據包、B類業務數據包和C類業務數據包；

A3、將分類后的數據包存放于對應的業務隊列中。

作為所述的一種基于動態權重計算的隊列調度方法的進一步改進，所述步驟C中A類業務隊列的最優權重值計算公式為：

其約束條件為：

w_k≥1，w_k∈N，

其中，w_k表示除低時延隊列外的其他A類業務的權重值，w_l表示低延時隊列的權重值，w_i表示第i個隊列的權重值，C_i和C_l分別表示隊列i和隊列l中一個數據包的價格，L_i和L_l分別表示第i個隊列和第l個隊列的平均數據包大小，m表示隊列的數量，表示第k個業務類別中每個業務流所應得到的帶寬，B表示總帶寬值，N_l和N_k分別表示低時延隊列和其他業務隊列中包含的激活的數據流的數量，ρ表示令牌桶的平均速率，σ表示令牌桶深度，表示L_l中的最小值，表示L_k中的最大值，D_l表示數據包的時延，r表示收益。

作為所述的一種基于動態權重計算的隊列調度方法的進一步改進，所述步驟C中B類業務隊列的最優權重值計算公式為：

其約束條件為：

w_k≥1，w_k∈N，

其中，w_k表示B類業務的權重值，w_i表示第i個隊列的權重值，C_i表示隊列i中一個數據包的價格，L_i表示第i個隊列的平均數據包大小，m表示隊列的數量，表示第k個業務類別中每個業務流所應得到的帶寬，B表示總帶寬值，N_k表示當前對應隊列中包含的激活的數據流的數量，r表示收益。

作為所述的一種基于動態權重計算的隊列調度方法的進一步改進，所述步驟C中C類業務隊列的最優權重值計算公式為：

其約束條件為：

w_k≥1，w_k∈N，