隊列調度方法

2023-06-26 22:52:06

專利名稱：：隊列調度方法
技術領域：
：本發明涉及隊列調度技術，尤其涉及一種基於赤字加權輪詢(DWRR,DeficitWeightedRoundRobin)、嚴才各優先級(SP,StrictPriority)的混合隊列調度方法。
背景技術：
：現有的IP網絡提供Internet,Intranet和Extranet連接，隨著網絡技術的發展，IP網絡所提供的業務種類也在不斷增加，這些業務包括聚集業務、傳輸業務和話音業務，其中，聚集業務通過接入伺服器如窄帶接入伺服器、寬帶接入伺服器等聚集非持久連接用戶的業務流，送至Internet接入提供商或Internet內容提供商。傳輸業務在IP網絡的持久連接用戶之間傳輸業務或將他們的業務傳給與Internet直接相連的站點。話音業務有如呼叫等待、業務群IP和網絡電話(VoIP，VoiceoverInternetProtocol)等。目前的IP網絡技術是第四版本的IP協議(IPv4)技術，其提供的業務是盡力而為的數據業務，沒有對業務進行分類，所有業務沒有區別地公平共享網絡資源，只是通過提供充足的網絡資源保證一定的服務質量(QoS，QualityofService)。而實際的IP網絡中，各業務對於延遲、丟包率、抖動的要求並不相同，使得現有IP網絡"盡力而為，，的工作特性已經無法滿足這些應用業務的需要。為了解決這一矛盾，IPQoS技術應運而生。IPQoS旨在通過給予控制網絡資源的使用方法，來保證區分式的網絡服務。IPQoS通過資源分配、路由、交換、分組調度以及分組丟棄等方法，從而實現數據報文的區分服務。其中，分組調度是IPQoS中的重要一環。它基於隊列和優先級的思想，將不同報文(數據包)進行優先級區分。不同優先級的報文進入不同級別的隊列中。然後，在這些隊列中運行一定的調度算法，從而決定哪個或哪些隊列中的報文優先處理、哪個或哪些隊列中的報文被滯後處理或丟棄。目前，業界提出的分組調度算法很多，如SP算法，其是先將報文按優先級入隊，然後先發送最高優先級隊列的報文，等最高優先級隊列中的報文發送完畢後，再發送次優先級隊列中的報文。而DWRR算法是加權循環算法的一種改進，是一種帶有加權性質的算法，根據隊列的優先級確定隊列的權重，並按權重為待隊列分配相應的資源進行數據調度。現有具備QoS隊列調度方法，往往根據用戶需要和實際工作場景提供多種隊列調度算法，如SP調度和加權循環調度的混合調度等。多類型調度隊列存在時，目前系統是根據隊列類型維護多套算法，以——實現各類型調度的需要，這不僅增加了運作維護成本，而且，多套算法共存下的調度融合性並不好，從而造成調度紊亂。
發明內容有鑑於此，本發明的主要目的在於提供一種隊列調度方法，能融合多種調度算法，維護成本低。為達到上述目的，本發明的技術方案是這樣實現的一種隊列調度方法，包括A、為數據包隊列配置參數，從而確定出所述隊列的調度^^莫式；B、提取數據包的特徵，根據所述特徵確定所述數據包所屬隊列的屬性，將所述數據包歸入與所述隊列屬性對應的隊列，衝艮據優先級將所述隊列置入活動隊列鍊表中；按所分配資源進行隊列調度。優選地，所述隊列的配置參數包括隊列總數目、隊列屬性標識、隊列存儲數據包的上限、各隊列優先級、隊列權重、隊列使能狀態以及隊列所對應數據包特徵。優選地，所述隊列屬性標識具體為赤字加4又4侖詢DWRR隊列標識、嚴才各優先級SP隊列標識。優選地，所述數據包的特徵包括數據包的MAC地址、虛擬區域網ID、虛擬區域網優先級、源/目的IP位址、源/目的埠信息以及協議類型。優選地，步驟B具體為Bl、根據所述數據包協議類型確定所述l史據包所屬隊列的屬性標識，並根據所述數據包的參數特徵確定所述數據包的優先級，從而確定所述數據包應歸入的隊列；B2、判斷所述應歸入的隊列是否被禁止，若是則丟棄所述數據包，若否則判斷所述隊列是否達到存儲上限，若達到存儲上限，則丟棄所述數據包，若未達到存儲上限，將所述悽t據包歸入所述隊列中。優選地，步驟B2還包括判斷所述隊列是否為首次接收到數據包，若是則根據優先級將所述隊列置入活動隊列鍊表中，並對所述活動隊列鍊表中的隊列按優先級重新排序。優選地，步驟B2還包括若所述應歸入的隊列為赤字加權輪詢隊列，歸入所述隊列之前還包括判斷所述隊列的權重是否為0,若為0則丟棄所述數據包。優選地，步驟C具體為Cl、獲取所述活動隊列鍊表中優先級最高的節點隊列，判斷所述優先級最高的隊列是否為嚴格優先級隊列，若是則將當前可分配的帶寬資源全部分配給所述嚴格優先級隊列，否則將當前帶寬資源按權重比例分配給赤字加權輪詢隊列；C2、根據所述隊列所分配的帶寬資源，獲耳又隊列中的第一個數據包，根據所述第一個數據包的大小為其分配相應的帶寬資源，有剩餘帶寬資源時繼續分配給本隊列中的下一個數據包；C3、隊列中一個數據包發送完畢後，判斷所述隊列是否還有剩餘數據包，若有則將分配給所述發送完畢數據包的帶寬資源分配給下一個數據包，若隊列中無數據包則即返回步驟Cl，將所述帶寬資源進行重新分配。本發明根據應用場景的不同，為隊列配置相應的參數，根據配置參數確定隊列的調度模式，再根據各數據包的參數特徵確定數據包的優先級，從而確定數據包應歸入的隊列；將各隊列置入到活動隊列鍊表中，再根據活動隊列鍊表中的隊列狀況為這些隊列分配帶寬資源，按所分配資源對隊列中數據包進行調度。本發明在融合了多調度算法的基礎上實現了較優的數據包調度，並且，本發明充分考慮了各種應用場景，因此能較好地融合多種調度算法，在實現時省卻了各調度算法中相同的程序代碼，開發及維護較方便。圖1為本發明隊列調度方法的流程圖；圖2為本發明數據包歸入隊列的流程圖；圖3為本發明數據包隊列調度的流程圖。具體實施方式本發明的核心思想是目前的IP網絡各節點中，往往需要多種調度算法才能實現業務的QoS,而對於調度算法的支持，基本上是單獨支持的狀況，調度實現的整體性不佳，往往存在紊亂的狀況。本發明針對上述問題，為隊列配置相應的參數，根據配置參數確定隊列的調度模式，再根據各數據包的參數特徵確定數據包的優先級，從而確定數據包應歸入的隊列；將各隊列置入到活動隊列鍊表中，再根據活動隊列鍊表中的隊列屬性為這些隊列分配帶寬資源，按所分配資源對隊列中數據包進行調度。本發明在融合了多調度算法的基礎上實現了較優的數據包調度，並且，本發明充分考慮了各種應用場景，因此能較好地融合多種調度算法，在實現時省卻了各調度算法中相同的程序代碼，開發及維護較方便。以下結合附圖對本發明進行詳細描述。圖1為本發明隊列調度方法的流程圖，如圖l所示，本發明隊列調度方法包括以下步驟步驟101:為數據包隊列配置參數，確定出所述隊列的調度模式。根據系統的具體應用場景，配置隊列參數，根據隊列配置參數確定當前調度模式。配置參數至少包括隊列總數目、隊列屬性標識、隊列存儲數據包的上限、各隊列優先級、隊列權重、隊列使能狀態以及隊列所對應數據包特徵，關於各參數的詳細信息，參見表一:tableseeoriginaldocumentpage8表表一中的各參數可通過資料庫的形式提前保存在系統中，需要對隊列進行配置時，根據需要從資料庫中選用相應的參數，完成各隊列的配置。其中，數據包的特徵包括數據包的硬體地址信息、虛擬區域網(VLAN,VirtualLocalAreaNetwork)信息如VLANID及VLAN優先級等、源/目的IP位址，協議類型，源/目的埠等，還包括各協議的特有信息如動態主才幾分配協議(DHCP,DynamicHostConfigurationProtocol)的Option字賴:信息以及悽丈據包的訪問接口等。數據包上可以攜帶並可作為信息識別的所有參數都可以作為數據包特徵。步驟102:提取數據包的特徵，根據所述特徵確定所述數據包所屬隊列的屬性，將所述數據包歸入與所述隊列屬性對應的隊列，根據優先級將所述隊列置入活動隊列鍊表中。對於各數據包，需要將其歸入相應的隊列中，才能完成對其的調度。本發明根據數據包的特徵信息，確定這些數據包的優先級等，以與其相應的QoS要求相適應，從而保證其QoS。例如，對於，語音業務數據包，由於實時性要求較高，需要優先調度，可將這類數據包歸入SP隊列中。而對於實時性要求不高的普通數據包，則可歸入到DWRR隊列中，在優先級較高的數據包調度完畢後，再調度這類數據包。以下對數據包歸入隊列的機制進行詳細描述。圖2為本發明邀:據包歸入隊列的流程圖，如圖2所示，數據包歸入隊列包括步驟201:解析數據包，提取數據包特徵，根據數據包特徵，得出其對應的隊列優先級。數據包特徵與隊列優先級的對應關係依據實際應用場景而定，參照該對應關係，根據數據包特徵確定該數據包對應的隊列。對於若沒有對應隊列的數據包，則歸入到一個默認優先級隊列中，該默認優先級隊列一般為最低優先級隊列。步驟202:查找到數據包對應的隊列，判斷該隊列是否使能，若不使能時丟棄該數據包，結束本次處理。步驟203:判斷隊列權重是否為0,權重為0時丟棄數據包，結束本次處理。步驟204:判斷隊列可接收的數據包總數是否已達上限，達到數據包上限時，結束本次處理。這裡，數據包總數達到上限，可以是數據包欲歸入的隊列已達上限，也可以是當前所有隊列的整體數據包達到上限，任何的隊列都不再允許新的數據包歸入。步驟205:將數據包歸入隊列。數據包歸入隊列時，根據數據包的特徵進行入隊順序處理。如對於某些特殊數據包或關鍵:數據包，如對等網鏈路控制協議(PPPLCP，Point-to-PointProtocolLinkControlProtocol)數據包、地址解析協議(ARP，AddressResolutionProtocol)數據包、網際網路組管理協議(IGMP,InternetGroupManagementProtocol)數據包、DHCP請求數據包等，插入到隊列頭部，以便於出隊時優先處理。步驟206:判斷歸入數據包的隊列是否為首次接收到數據包，是時將該隊列按照其優先級加入到活動隊列鍊表(ActiveList)中。ActiveList按照隊列優先級由高到低進行排序，最高優先級隊列放在鍊表頭部。其中，SP隊列優先級高於DWRR隊列優先級；SP隊列之間按優先級進行排列；DWRR隊列之間同樣按優先級進行排列。不同的隊列，優先級不同。本領域技術人員應當理解，步驟202至步驟204的判斷順序可以互換。步驟103:為所述活動隊列鍊表中各隊列分配資源，按所分配資源進行隊列調度。以下對本發明的隊列調度進行詳細描述。圖3為本發明數據包隊列調度的流程圖，如圖3所示，本發明數據包隊列調度包括步驟301:計算活動隊列鍊表中各個隊列可使用的帶寬份額。從鍊表的頭節點隊列開始進行計算。判斷該隊列是否屬於SP隊列，若是則將當前可分配帶寬資源分配給該頭節點隊列，其他隊列已分配的帶寬資源不變，即對於已分配的帶寬資源，繼續被原隊列使用發送數據包；否則，說明當前活動隊列鍊表中的隊列全部為DWRR隊列，按照各個隊列的權重值按比例進行帶寬資源分配。需要說明的是，對於鍊表的頭節點隊列，也即是當前優先級最高的隊列。步驟302:對於每個分配了帶寬資源的隊列，獲取該隊列中的第一個數據包，根據數據包的長度，為所述數據包分配相應的帶寬資源。步驟303:為第一個數據包分配分帶寬資源後，判斷所述隊列中是否還有剩餘帶寬資源，若有則判斷該隊列中是否還有凝:據包，若有則將剩餘帶寬資源分配給該隊列中的下一個數據包，依此類推；若沒有剩餘的數據包，則返回步驟301，對將當前的剩餘資源重新進行分配。以上所述僅為本發明的較佳實施例而已，並非用於限定本發明的保護範圍。權利要求1、一種隊列調度方法，其特徵在於，該方法包括A、為數據包隊列配置參數，從而確定出所述隊列的調度模式；B、提取數據包的特徵，根據所述特徵確定所述數據包所屬隊列的屬性，將所述數據包歸入與所述隊列屬性對應的隊列，根據優先級將所述隊列置入活動隊列鍊表中；C、根據隊列屬性及隊列優先級為所述活動隊列鍊表中各隊列分配資源，按所分配資源進行隊列調度。2、根據權利要求1所述的隊列調度方法，其特徵在於，所述隊列的配置參數包括隊列總數目、隊列屬性標識、隊列存儲數據包的上限、各隊列優先級、隊列權重、隊列使能狀態以及隊列所對應數據包特徵。3、根據權利要求2所述的隊列調度方法，其特徵在於，所述隊列屬性標識具體為赤字加權4侖詢DWRR隊列標識、嚴才各優先級SP隊列標識。4、根據權利要求l、2或3所述的隊列調度方法，其特徵在於，所述數據包的特徵包括數據包的MAC地址、虛擬區域網ID、虛擬區域網優先級、源/目的IP位址、源/目的埠信息以及協議類型。5、根據權利要求4所述的隊列調度方法，其特徵在於，步驟B具體為Bl、根據所述數據包協議類型確定所述數據包所屬隊列的屬性標識，並根據所述數據包的參數特徵確定所述數據包的優先級，從而確定所述數據包應歸入的隊列；B2、判斷所述應歸入的隊列是否被禁止，若是則丟棄所述數據包，若否則判斷所述隊列是否達到存儲上限，若達到存儲上限，則丟棄所述數據包，若未達到存儲上限，將所述it據包歸入所述隊列中。6、根據權利要求5所述的隊列調度方法，其特徵在於，步驟B2還包括判斷所述隊列是否為首次接收到數據包，若是則4艮據優先級將所述隊列置入活動隊列鍊表中，並對所述活動隊列鍊表中的隊列按優先級重新排序。7、根據權利要求5所述的隊列調度方法，其特徵在於，步驟B2還包括若所述應歸入的隊列為赤字加權輪詢隊列，歸入所述隊列之前還包括判斷所述隊列的權重是否為O,若為0則丟棄所述數據包。8、根據權利要求4所述的隊列調度方法，其特徵在於，步驟C具體為Cl、獲取所述活動隊列鍊表中優先級最高的節點隊列，判斷所述優先級最高的隊列是否為嚴格優先級隊列，若是則將當前可分配的帶寬資源全部分配給所述嚴格優先級隊列，否則將當前帶寬資源按權重比例分配給赤字加權輪詢隊列；C2、根據所述隊列所分配的帶寬資源，獲取隊列中的第一個數據包，根據所述第一個數據包的大小為其分配相應的帶寬資源，有剩餘帶寬資源時繼續分配給本隊列中的下一個邀:據包；C3、隊列中一個數據包發送完畢後，判斷所述隊列是否還有剩餘數據包，若有則將分配給所述發送完畢數據包的帶寬資源分配給下一個數據包，若隊列中無數據包則即返回步驟C1,將所述帶寬資源進行重新分配。全文摘要本發明公開了一種隊列調度方法，涉及隊列調度技術，為解決目前多隊列融合時隊列調度不合理而提出，所採用的技術方案為A.為數據包隊列配置參數，從而確定出所述隊列的調度模式；B.提取數據包的特徵，根據所述特徵確定所述數據包所屬隊列的屬性，將所述數據包歸入與所述隊列屬性對應的隊列，根據優先級將所述隊列置入活動隊列鍊表中；C.根據隊列屬性及隊列優先級為所述活動隊列鍊表中各隊列分配資源，按所分配資源進行隊列調度。本發明充分考慮了各種應用場景，因此能較好地融合多種調度算法，在實現時省卻了各調度算法中相同的程序代碼，開發及維護較方便。文檔編號H04L12/56GK101217499SQ20081005652公開日2008年7月9日申請日期2008年1月21日優先權日2008年1月21日發明者偉蔣申請人:中興通訊股份有限公司