[發明專利]一種分組調度方法和設備

有效

• 申請號: 200710179905.X
• 申請日: 2007-12-19
• 公開（公告）號: CN101465794A
• 公開（公告）日: 2009-06-24
• 發明（設計）人: 涂曉東;李劍;謝軍;楊洋;蔣章震
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L29/06
• 代理公司: 北京三高永信知識產權代理有限責任公司
• 代理人: 何文彬

技術領域

本發明涉及通信領域，特別涉及一種分組調度方法和分組調度設備。

背景技術

目前，數據轉發設備在出口調度業務時都會用到隊列調度機制(QSM，Queueing?SchedulingMechanism)，所謂隊列調度機制是指按照一定的服務規則對數據轉發設備中因發生沖突而需排隊等待的不同業務分組進行調度和服務，使所有的輸入業務分組能按預定的方式共享數據轉發設備的輸出鏈路帶寬并提供服務質量(QoS，Quality?of?Service)的保證。參見圖1，為數據轉發設備的調度服務示意圖，當業務分組到達數據轉發設備時，將業務分組進行流分類，分別暫存到相應的隊列1、2......n中，數據轉發設備中的調度器根據采用的隊列調度機制從n個隊列中選擇出下一個需要進行發送的業務分組。

根據隊列調度機制的服務規則、調度目標及其發展趨勢，目前已出現的隊列調度算法包括：基于輪循的調度算法、基于通用處理機共享(GPS，Generalized?Processor?Sharing)的調度算法、基于時延的調度算法、基于服務曲線(Service?Curve)的調度算法等。

在GPS調度算法的基礎上，現有技術提供了一種整形虛擬時鐘(ShVC，Shaped?VirtualClock)算法，該算法具體包括：

1)采用實際時鐘(Real-time?Clock)作為系統虛擬時間函數(Virtual?Time?Function)V_s(t)，V_s(t)＝t，t＞0；

2)每個分組到達時為其分配一個虛擬開始時標(Virtual?Starting?Time)和虛擬結束時標(Virtual?Finishing?Time)計算規則如下：

Sik=max[Vs(aik),Fik-1]=max[aik,Fik-1]]]>

Fik=Sik+Likri]]>

和分別表示隊列i的第k個分組的到達時間和分組長度，r_i表示隊列i的預約帶寬(Allocated?Rate)，表示隊列i中第k-1個分組的虛擬結束時間。虛擬開始時標為隊列i的第k個業務分組到達的時間和上一個分組的虛擬結束時間中的最大值；虛擬結束時標為隊列i的第k個業務分組發送的結束時間，具體為虛擬開始時標加上該業務分組的分組長度除以預約帶寬。其中，預約帶寬是通信雙方向網絡申請的帶寬，為一個隊列中所有業務分組的預約帶寬的總合。

3)分組選擇策略為最小合法虛擬結束時間優先(SEFF，Smallest?Eligible?virtual?Finishedtime?First)，即在合法的分組中，優先地選擇具有最小虛擬結束時間的分組進行發送。在此，所謂合法的分組，一般情況下指的是分組的虛擬開始時標小于或等于系統時鐘。