[發明專利]一種用于差分隊列服務系統的數據包快速入隊方法

有效

• 申請號: 201110387461.5
• 申請日: 2011-11-30
• 公開（公告）號: CN102404225A
• 公開（公告）日: 2012-04-04
• 發明（設計）人: 姜勝明;郭棉;官權升;毛華超
• 申請（專利權）人: 華南理工大學
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 何淑珍

技術領域

????本發明屬于隊列管理和分組調度技術領域，具體涉及一種用于差分隊列服務系統的數據包快速入隊方法。

背景技術

????在現有的互聯網技術中，有兩種經典的服務質量方案，即綜合服務（Integrated?Services）和區分服務(Differentiated?Services)。它們提供服務質量的做法是，將緩存分成多個優先級隊列，時延敏感的業務流進入高優先級的隊列，其他業務流進入低優先級的隊列。分組調度器采用優先級隊列調度、加權公平隊列調度或其他調度算法在多個隊列中選擇數據包進行調度。但是，一般路由器中可能有幾十條至幾百條甚至更多的服務質量保障隊列，在極短的時間內要求調度器在這些隊列中選擇一個數據包進行轉發的做法對處理器和存儲器訪問操作提出了嚴格的要求。實際上，由于硬件實現上的難度，在一個數據包轉發期間在所有隊列中選擇下一數據包的行為限制了隊列的數量，從而也限制了綜合服務和區分服務對服務質量保障的粒度與公平性。

????針對綜合服務和區分服務中存在的問題，一種差分隊列服務（Differentiated?Queueing?Services）方案被提出（參考文獻[1]?Jiang?S.，“Granular?differentiated?queueing?services?for?QoS:?structure?and?cost?model.”ACM?SIGCOMM?Computer?Communication?Review2005;?35(2):13–22.?和?[2]?Jiang?S.，“Differentiated?Queueing?Service?(DQS)?for?End-to-End?QoS?Provisioning:?An?Evaluation?from?Per-Flow,?Per-Class?to?Per-Packet.”??Recent?Advances?in?Providing?QoS?and?Reliability?in?the?Future?Internet?Backbone,?Nova?Science:?New?York,?2011）。該方案的主要思想是：每個數據包攜帶其時延要求，路由器根據數據包的時延要求決定其在緩存隊列里的位置，從而保障數據包的服務質量。差分隊列服務方案的主要優點是，由于服務質量要求是由數據包攜帶，因而具有可擴展性；另外，由于該方案將新到的數據包按時延要求放入隊列的合適位置，因而具有數據包粒度的服務質量保障；最后，該方案的隊列由差分隊列服務隊列和一個或幾個其他隊列組成，因而調度非常簡單。

????實現差分隊列服務的一個關鍵技術問題是如何快速地將新到的數據包按服務質量要求放入隊列合適的位置。這是因為，數據包入隊這種操作所消耗的時間會影響端到端服務質量的保障和網絡資源的利用率。具體表現在，如果新數據包沒有在有效時間內被放到合適的位置，就有可能得不到及時的服務，從而影響服務質量。另外，如果上述操作消耗過多的時間，將會影響系統的性能，從而降低網絡資源利用率，尤其是在高速網絡中這種問題更加突出。

在現有技術中，綜合服務和區分服務一般采用多個優先級隊列提供服務質量，差分隊列服務主要采用差分隊列服務隊列提供服務質量，這些隊列的特點是采用單一的數據包入隊規則。綜合服務和區分服務的多優先級隊列機制要求每個數據包到達時都要在所有隊列中查找該數據包所屬的隊列。采用單一數據包入隊規則的差分隊列服務隊列要求每次數據包到達時均要發起查找插入過程。以上數據包入隊規則一般要求在一個數據包服務時間內完成新數據包的查找插入過程，因而對處理器和存儲器訪問操作提出了嚴格的要求，然而硬件實現上的難度限制了以上服務方案的數據包入隊的速率和效率，使其成為高速網絡的瓶頸。

發明內容

本發明的目的是解決如何快速地將新到的數據包按服務質量要求放入隊列合適的位置這個關鍵問題，因此提供一種用于差分隊列服務系統的數據包快速入隊方法，減少數據包入隊操作所消耗的時間，加快數據包入隊速度，使其適用于高速網絡。

為了達到上述目的，本發明公開的差分隊列服務系統的隊列由差分隊列服務隊列和其他隊列構成，差分隊列服務隊列包括先進先出區間和差分隊列服務區間；所述先進先出區間位于隊列前部，差分隊列服務區間緊隨其后；設先進先出區間長度為L，差分隊列服務區間閾值為H，根據隊列長度以及各區間的入隊規則將新數據包快速插入隊列。

本發明通過如下技術方案實現：

一種用于差分隊列服務系統的數據包快速入隊方法，包括如下步驟：