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

有效

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

技術領域

本發明涉及網絡管理和網絡監控技術領域，特別涉及一種可擴展的全流優先級調度方法及系統。?

背景技術

急速增長的用戶數量和流量，嚴重影響關鍵業務正常使用。如何保障關鍵業務，進行流量管理是關鍵。增長帶寬，可能暫時解決網絡速度變慢的現象，關鍵業務的網絡質量有所改善。然而增長的帶寬很快被無休止的增長的非關鍵業務流量所占據。因此合理分配網絡資源，保障關鍵業務的關鍵在于：(1)如何能夠將帶寬合理的分配到每個流；(2)如何實施監控和直接控制各種應用流量，根據不同應用程序設置不同的優先級別，以保證對關鍵業務應用提供快捷、準確的網絡服務。為每個流分配一個專有的隊列，加上適當的調度出隊算法，能夠提供帶寬分配和服務保障。然而其面臨著多個難題：高速網絡設備中同時存在的流的數目在百萬量級，隨著網絡帶寬的進一步增長，流的數目也隨之增長。而在高速網絡中相鄰兩個包的時間間隔只有幾十納秒。如果將百萬量級的流存儲在慢速的DRAM中，不能達到線速處理；而如果將百萬的流存儲在快速存儲器，如SRAM中，成本將很高。?

流一般定義為網絡數據包頭具有特定相同域的網絡數據包集合(如TCP/IP協議的五元組)。同一個流的網絡數據包要求相同的服務等級。當前學術界和工業界廣泛采用的方法是以秒或者分鐘做為處理時間粒度(即認為在秒或分鐘內的存在的流)，在此粒度下，系統內流的數目在百萬量級。集成服務(IntServ)做為調度結構的先驅，它為每個同時存在的流保留資源，由于其處理的流數目在百萬量級。所以其處理復雜度高，限制了其廣泛應用。另外的一種思路是采用ASIC硬件加速隊列組織和調度，然而該種方法開發周期長，成本高，在通用硬件中應用并不廣泛。另外一種在Linux系統中廣泛使用的調度算法CBQ(Class-Based?Queueing)【Main?page?of?CBQ.www.icir.org/floyd/cbq.html】采用樹的組織結構，根節點表示真個帶寬資源，其下每個子節點代表一種資源分配單位，不同的分支根據策略可以采用不同的調度算法。然而該算法僅適合處理高度聚類的流，如果要處理細粒度的流，如一個具有相同五元組(源IP，源端口，目的IP，目的端口，協議)的流，該樹結構的高度將變得很大，從而處理復雜度高。?

發明內容

(一)發明目的?

本發明的目的是提供一種可擴展的全流優先級調度方法，該方法實現了全流的服務區分和帶寬保證。?

(二)發明內容?

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

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

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

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

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

其中，所述步驟S2包括步驟：?

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

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

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

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

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

其中，所述步驟S2還包括步驟：?

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

其中，所述步驟S3包括步驟：?

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

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

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

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

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