[發(fā)明專(zhuān)利]一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201110387461.5
• 申請(qǐng)日: 2011-11-30
• 公開(kāi)（公告）號(hào): CN102404225A
• 公開(kāi)（公告）日: 2012-04-04
• 發(fā)明（設(shè)計(jì)）人: 姜?jiǎng)倜?/a>;郭棉;官權(quán)升;毛華超
• 申請(qǐng)（專(zhuān)利權(quán)）人: 華南理工大學(xué)
• 主分類(lèi)號(hào): H04L12/56
• 分類(lèi)號(hào): H04L12/56
• 代理公司: 廣州粵高專(zhuān)利商標(biāo)代理有限公司 44102
• 代理人: 何淑珍

1.一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，差分隊(duì)列服務(wù)系統(tǒng)的隊(duì)列由差分隊(duì)列服務(wù)隊(duì)列和其他隊(duì)列構(gòu)成，差分隊(duì)列服務(wù)隊(duì)列包括先進(jìn)先出區(qū)間和差分隊(duì)列服務(wù)區(qū)間；所述先進(jìn)先出區(qū)間位于隊(duì)列前部，差分隊(duì)列服務(wù)區(qū)間緊隨其后；設(shè)先進(jìn)先出區(qū)間長(zhǎng)度為L(zhǎng)，差分隊(duì)列服務(wù)區(qū)間閾值為H，其特征在于所述方法具體包括如下步驟：

1）新數(shù)據(jù)包到達(dá)系統(tǒng)，從該數(shù)據(jù)包的包頭讀取端到端時(shí)延；

2）判斷端到端時(shí)延是否大于0：是，則跳往步驟3）；否，則放入其他隊(duì)列，本數(shù)據(jù)包入隊(duì)過(guò)程結(jié)束；

3）判斷當(dāng)前差分隊(duì)列服務(wù)隊(duì)列的長(zhǎng)度是否小于L：是，則執(zhí)行步驟4）；否，則跳往步驟5）；

4）判斷當(dāng)前差分隊(duì)列服務(wù)隊(duì)列的服務(wù)時(shí)間與該數(shù)據(jù)包的服務(wù)時(shí)間之和是否不大于該數(shù)據(jù)包所容忍的最大時(shí)延：是，則放入先進(jìn)先出區(qū)間的尾部，本數(shù)據(jù)包入隊(duì)過(guò)程結(jié)束；否，則放入其他隊(duì)列，本數(shù)據(jù)包入隊(duì)過(guò)程結(jié)束；

5)?確定新數(shù)據(jù)包在差分隊(duì)列服務(wù)區(qū)間的插入位置；

6）判斷新數(shù)據(jù)包在差分隊(duì)列服務(wù)區(qū)間的插入位置是否同時(shí)滿足如下條件，a)該數(shù)據(jù)包插入位置前面所有數(shù)據(jù)包的服務(wù)時(shí)間與該數(shù)據(jù)包的服務(wù)時(shí)間之和不大于該數(shù)據(jù)包所容忍的最大時(shí)延，b）該數(shù)據(jù)包插入位置后面的數(shù)據(jù)包的時(shí)延保障不受影響：是，則將數(shù)據(jù)包插入步驟5）所確定的位置，本數(shù)據(jù)包入隊(duì)過(guò)程結(jié)束；否，則將該數(shù)據(jù)包放入其他隊(duì)列，本數(shù)據(jù)包入隊(duì)過(guò)程結(jié)束。

2.根據(jù)權(quán)利要求1所述的一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，其特征在于，所述差分隊(duì)列服務(wù)隊(duì)列為一個(gè)，其他隊(duì)列為一個(gè)或一個(gè)以上。

3.根據(jù)權(quán)利要求1或2所述的一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，其特征在于，所述差分隊(duì)列服務(wù)隊(duì)列調(diào)度優(yōu)先級(jí)高于其他隊(duì)列。

4.根據(jù)權(quán)利要求1所述的一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，其特征在于所述步驟5）確定新數(shù)據(jù)包在差分隊(duì)列服務(wù)區(qū)間的插入位置包括：

判斷當(dāng)前差分隊(duì)列服務(wù)隊(duì)列的長(zhǎng)度是否小于L與H之和：是，則用順序查找法確定；否，則用二分查找法確定。

5.根據(jù)權(quán)利要求4所述的一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，其特征在于插入位置滿足：新數(shù)據(jù)包與當(dāng)前差分隊(duì)列服務(wù)區(qū)間的數(shù)據(jù)包按數(shù)據(jù)包的最遲離開(kāi)時(shí)刻升序排列。

6.根據(jù)權(quán)利要求4所述的一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，其特征在于所述順序查找法從當(dāng)前差分隊(duì)列服務(wù)區(qū)間尾部開(kāi)始查找。

7.根據(jù)權(quán)利要求4所述的一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，其特征在于所述二分查找法從當(dāng)前差分隊(duì)列服務(wù)區(qū)間的實(shí)際長(zhǎng)度的中間位置開(kāi)始查找。

8.根據(jù)權(quán)利要求4所述的一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，其特征在于所述方法查找的范圍均為當(dāng)前差分隊(duì)列服務(wù)區(qū)間的實(shí)際長(zhǎng)度。

9.根據(jù)權(quán)利要求1所述的一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，其特征在于所述先進(jìn)先出區(qū)間長(zhǎng)度L由如下條件確定：服務(wù)完先進(jìn)先出區(qū)間的數(shù)據(jù)包所需時(shí)間，不得大于時(shí)間t1與時(shí)間t2之和；所述時(shí)間t1為先進(jìn)先出區(qū)間查找特定位置時(shí)間，該位置使新數(shù)據(jù)包與該區(qū)間的數(shù)據(jù)包按數(shù)據(jù)包的可容忍的最遲離開(kāi)隊(duì)列時(shí)刻升序排列；所述時(shí)間t2為將新數(shù)據(jù)包插入查找到的位置的時(shí)間。

10.根據(jù)權(quán)利要求1所述的一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，其特征在于所述差分隊(duì)列服務(wù)區(qū)間閾值H由如下條件確定：用順序查找法的平均查找時(shí)間不得大于用二分查找法的平均查找時(shí)間。