技術(shù)領(lǐng)域

????本發(fā)明屬于隊(duì)列管理和分組調(diào)度技術(shù)領(lǐng)域，具體涉及一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法。

背景技術(shù)

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

????針對(duì)綜合服務(wù)和區(qū)分服務(wù)中存在的問題，一種差分隊(duì)列服務(wù)（Differentiated?Queueing?Services）方案被提出（參考文獻(xiàn)[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）。該方案的主要思想是：每個(gè)數(shù)據(jù)包攜帶其時(shí)延要求，路由器根據(jù)數(shù)據(jù)包的時(shí)延要求決定其在緩存隊(duì)列里的位置，從而保障數(shù)據(jù)包的服務(wù)質(zhì)量。差分隊(duì)列服務(wù)方案的主要優(yōu)點(diǎn)是，由于服務(wù)質(zhì)量要求是由數(shù)據(jù)包攜帶，因而具有可擴(kuò)展性；另外，由于該方案將新到的數(shù)據(jù)包按時(shí)延要求放入隊(duì)列的合適位置，因而具有數(shù)據(jù)包粒度的服務(wù)質(zhì)量保障；最后，該方案的隊(duì)列由差分隊(duì)列服務(wù)隊(duì)列和一個(gè)或幾個(gè)其他隊(duì)列組成，因而調(diào)度非常簡(jiǎn)單。

????實(shí)現(xiàn)差分隊(duì)列服務(wù)的一個(gè)關(guān)鍵技術(shù)問題是如何快速地將新到的數(shù)據(jù)包按服務(wù)質(zhì)量要求放入隊(duì)列合適的位置。這是因?yàn)椋瑪?shù)據(jù)包入隊(duì)這種操作所消耗的時(shí)間會(huì)影響端到端服務(wù)質(zhì)量的保障和網(wǎng)絡(luò)資源的利用率。具體表現(xiàn)在，如果新數(shù)據(jù)包沒有在有效時(shí)間內(nèi)被放到合適的位置，就有可能得不到及時(shí)的服務(wù)，從而影響服務(wù)質(zhì)量。另外，如果上述操作消耗過多的時(shí)間，將會(huì)影響系統(tǒng)的性能，從而降低網(wǎng)絡(luò)資源利用率，尤其是在高速網(wǎng)絡(luò)中這種問題更加突出。

在現(xiàn)有技術(shù)中，綜合服務(wù)和區(qū)分服務(wù)一般采用多個(gè)優(yōu)先級(jí)隊(duì)列提供服務(wù)質(zhì)量，差分隊(duì)列服務(wù)主要采用差分隊(duì)列服務(wù)隊(duì)列提供服務(wù)質(zhì)量，這些隊(duì)列的特點(diǎn)是采用單一的數(shù)據(jù)包入隊(duì)規(guī)則。綜合服務(wù)和區(qū)分服務(wù)的多優(yōu)先級(jí)隊(duì)列機(jī)制要求每個(gè)數(shù)據(jù)包到達(dá)時(shí)都要在所有隊(duì)列中查找該數(shù)據(jù)包所屬的隊(duì)列。采用單一數(shù)據(jù)包入隊(duì)規(guī)則的差分隊(duì)列服務(wù)隊(duì)列要求每次數(shù)據(jù)包到達(dá)時(shí)均要發(fā)起查找插入過程。以上數(shù)據(jù)包入隊(duì)規(guī)則一般要求在一個(gè)數(shù)據(jù)包服務(wù)時(shí)間內(nèi)完成新數(shù)據(jù)包的查找插入過程，因而對(duì)處理器和存儲(chǔ)器訪問操作提出了嚴(yán)格的要求，然而硬件實(shí)現(xiàn)上的難度限制了以上服務(wù)方案的數(shù)據(jù)包入隊(duì)的速率和效率，使其成為高速網(wǎng)絡(luò)的瓶頸。

發(fā)明內(nèi)容

本發(fā)明的目的是解決如何快速地將新到的數(shù)據(jù)包按服務(wù)質(zhì)量要求放入隊(duì)列合適的位置這個(gè)關(guān)鍵問題，因此提供一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，減少數(shù)據(jù)包入隊(duì)操作所消耗的時(shí)間，加快數(shù)據(jù)包入隊(duì)速度，使其適用于高速網(wǎng)絡(luò)。

為了達(dá)到上述目的，本發(fā)明公開的差分隊(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，根據(jù)隊(duì)列長(zhǎng)度以及各區(qū)間的入隊(duì)規(guī)則將新數(shù)據(jù)包快速插入隊(duì)列。

本發(fā)明通過如下技術(shù)方案實(shí)現(xiàn)：

一種用于差分隊(duì)列服務(wù)系統(tǒng)的數(shù)據(jù)包快速入隊(duì)方法，包括如下步驟：