[發明專利]一種可擴展的全流優先級調度方法

有效

• 申請號: 200910236816.3
• 申請日: 2009-10-30
• 公開（公告）號: CN101714947A
• 公開（公告）日: 2010-05-26
• 發明（設計）人: 李國棟;陳震;薛一波;李軍
• 申請（專利權）人: 清華大學
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 胡小永

1.一種可擴展的全流優先級調度方法，其特征在于，將相同優 先級的流分為一組，組間按優先級調度，組內按差額輪詢方式調度， 包括以下步驟：

S1：接收網絡數據包，解析所述網絡數據包流標簽；

S2：根據流標簽計算網絡數據包組內出隊列順序，并將網絡數據 包插入到所屬流隊列，具體包括步驟：

根據流標簽檢查網絡數據包所屬流是否存在于活躍流表中；

計算網絡數據包組內出隊列順序，若所屬流存在于活躍流表中， 將所屬流的網絡數據包數加1，否則，獲取流的優先級，申請一個該 流的空隊列，并初始化該流的調度信息；

將所述網絡數據包插入所屬的流隊列；

流隊列所在優先級組的網絡數據包數加1；

判斷所述優先級組的網絡數據包數是否為1，若是，則將比特向 量中所述優先級組對應的比特向量位設為1；

S3：網絡數據包組間按優先級、組內按出隊列順序出隊列；

S4：將網絡數據包發送出去。

2.如權利要求1所述的可擴展的全流優先級調度方法，其特征 在于，所述步驟S2還包括步驟：

當所屬流不存在于活躍流表時，將該所屬流插入到活躍流表尾 部，并建立流和流隊列動態映射關系。

3.如權利要求1所述的可擴展的全流優先級調度方法，其特征 在于，所述步驟S3包括步驟：

找到一個具有最高優先級的非空優先級組；

取得所述優先級組上的一輪鏈表頭的網絡數據包，并更新網絡數 據包所在流的剩余配額；

判斷所屬流的剩余配額是否大于所述網絡數據包的長度，若是， 所述網絡數據包出隊列，并更新所屬流的剩余配額、所屬流的網絡數 據包數以及所述優先級組的網絡數據包數，否則更新所述優先級組出 隊輪；

判斷所屬流的網絡數據包數是否為0，若是，在活躍流表中刪除 所屬流并更新所述優先級組出隊輪，否則，直接更新所述優先級組出 隊輪；

所述優先級組的網絡數據包數減1；

判斷所述優先級組中網絡數據包數是否為0，若是，將比特向量 中所述優先級組對應的比特向量位設為0，否則結束。

4.如權利要求1所述的可擴展的全流優先級調度方法，其特征 在于，所述初始化流的調度信息包括初始化流中的網絡數據包數、流 的配額和流的當前剩余配額。

5.一種可擴展的全流優先級調度系統，其特征在于，包括：

網絡數據包接收模塊，用于接收網絡數據包，并解析所述網絡數 據包流標簽；

網絡數據包入隊列模塊，用于根據流標簽計算網絡數據包組內出 隊列順序，并將網絡數據包插入到所屬流隊列，具體包括：

活躍流表中流查詢模塊，用于根據流標簽查詢網絡數據包所 屬流是否存在于活躍流表中；

流隊列準備模塊，用于計算網絡數據包組內出隊列順序，若 所屬流存在于活躍流表中，將所屬流的網絡數據包數加1，否則， 獲取流的優先級，申請一個該流的空隊列，并初始化該流的調度 信息；

流隊列插入模塊，用于將網絡數據包插入所屬的流隊列；

優先級組更新模塊，用于將流隊列所在優先級組的網絡數據 包數加1；

比特向量設置模塊，用于判斷所述優先級組的網絡數據包數 是否為1，若是，則將比特向量中所述優先級組對應的比特向量 位設為1；

網絡數據包出隊列模塊，用于網絡數據包組間按優先級、組內按 出隊列順序出隊列；

網絡數據包發送模塊，用于將網絡數據包發送出去。

6.如權利要求5所述的可擴展的全流優先級調度系統，其特征 在于，所述網絡數據包出隊列模塊包括：

最高非空優先級組查找模塊，用于找到一個具有最高優先級的非 空優先級組；

調度輪鏈表頭的網絡數據包獲取模塊，用于取得所述優先級組上 的一輪鏈表頭的網絡數據包，并更新網絡數據包所在流的剩余配額；

出隊列判斷模塊，用于判斷所屬流的剩余配額是否大于所述網絡 數據包的長度，若是，所述網絡數據包出隊列，并更新所屬流的剩余 配額、所屬流的網絡數據包數以及所述優先級組的網絡數據包數，否 則更新所述優先級組出隊輪；

流的網絡數據包數判斷模塊，用于判斷所屬流的網絡數據包數是 否為0，若是，則在活躍流表中刪除所屬流并更新所述優先級組出隊 輪，否則，直接更新所述優先級組出隊輪；

優先級組更新模塊，用于將所述優先級組的網絡數據包數減1；

比特向量設置模塊，用于判斷所述優先級組中網絡數據包數是否 為0，若是，將比特向量中所述優先級組對應的比特向量位設為0， 否則結束。