基于優(yōu)先公平調(diào)度的網(wǎng)絡(luò)鏈路狀態(tài)測量方法

張敏++邱恭安++張士兵

摘要：在不增加網(wǎng)絡(luò)開銷前提下為實現(xiàn)網(wǎng)絡(luò)實時狀態(tài)的測量，利用優(yōu)先公平調(diào)度原理中隱性的網(wǎng)絡(luò)狀態(tài)統(tǒng)計功能，提出使用周期性測量的優(yōu)先隊列隊長和鏈路公平速率指標(biāo)估計下游鏈路承載狀態(tài)，實現(xiàn)無開銷的鏈路狀態(tài)測量。仿真顯示優(yōu)先隊列隊長和鏈路公平速率變化曲線能夠反映出下游鏈路的不同負(fù)載率變化。

關(guān)鍵詞：網(wǎng)絡(luò)測量 優(yōu)先公平調(diào)度 公平速率

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2016）12-0052-02

1 引言

網(wǎng)絡(luò)鏈路狀態(tài)是指定信源和信宿間路徑承載的數(shù)據(jù)分組狀態(tài)，反映了鏈路和網(wǎng)絡(luò)負(fù)載的流量信息，常作為狀態(tài)參數(shù)用于網(wǎng)絡(luò)流量控制和擁塞控制。當(dāng)前，多業(yè)務(wù)綜合承載是網(wǎng)絡(luò)IP化的應(yīng)用趨勢，不同業(yè)務(wù)具有不同的特征，需要差異化的服務(wù)性能保障[1]，因此，實時獲得網(wǎng)絡(luò)鏈路狀態(tài)是差異化保障不同業(yè)務(wù)服務(wù)質(zhì)量和有效提高網(wǎng)絡(luò)效率的基礎(chǔ)。

目前，網(wǎng)絡(luò)鏈路狀態(tài)測量主要是顯式的測量方法，包括主動測量和被動測量兩類。主動測量方法針對網(wǎng)絡(luò)性能參數(shù)發(fā)送探測分組，通過收到的應(yīng)答分組分析計算網(wǎng)絡(luò)狀態(tài)，但增加了網(wǎng)絡(luò)額外開銷，且具有較大的網(wǎng)絡(luò)狀態(tài)測量時延。被動測量通過在網(wǎng)絡(luò)中設(shè)置流量監(jiān)測點，捕捉網(wǎng)絡(luò)的流量參數(shù)，獲取網(wǎng)絡(luò)承載業(yè)務(wù)的統(tǒng)計信息，其無需發(fā)送測量數(shù)據(jù)分組，但需要網(wǎng)絡(luò)節(jié)點設(shè)備被動地收集數(shù)據(jù)包，操作相對復(fù)雜，網(wǎng)絡(luò)狀態(tài)信息存在一定的陳舊性。隨著，網(wǎng)絡(luò)信息安全的提高以及多業(yè)務(wù)綜合承載的擴(kuò)展，既有網(wǎng)絡(luò)鏈路狀態(tài)測量方法的測量精度和時延受到很大影響[2]，針對該問題，本文利用優(yōu)先公平調(diào)度機(jī)制中隊長參數(shù)和鏈路公平速率實現(xiàn)隱式的網(wǎng)絡(luò)聯(lián)網(wǎng)狀態(tài)測量，能夠為兩類不同業(yè)務(wù)分別提供業(yè)務(wù)匹配的鏈路狀態(tài)。

2 優(yōu)先公平調(diào)度機(jī)制原理

分組調(diào)度指按照一定的規(guī)則決定從等待隊列中選擇分組進(jìn)行發(fā)送，使得所有輸入業(yè)務(wù)流能夠按照預(yù)定的方式共享輸出鏈路帶寬[3]。優(yōu)先公平調(diào)度包含絕對優(yōu)先公平調(diào)度和相對優(yōu)先公平調(diào)度，其中，絕對優(yōu)先公平調(diào)度以連續(xù)方式為目標(biāo)隊列賦予優(yōu)先級，當(dāng)調(diào)度分組時，如果高優(yōu)先級隊列非空，則其分組優(yōu)先被選擇服務(wù)。只有高優(yōu)先級隊列為空時，才會服務(wù)次高優(yōu)先隊列。為提高調(diào)度機(jī)制對鏈路狀態(tài)的適應(yīng)性和業(yè)務(wù)服務(wù)公平性，提出了相對優(yōu)先公平調(diào)度，其為高優(yōu)先隊列預(yù)留一定的緩存空間，使得低優(yōu)先隊列能相對公平地得到調(diào)度服務(wù)，僅當(dāng)優(yōu)先隊列隊長超過一定門限時，才為優(yōu)先隊列提供絕對的優(yōu)先轉(zhuǎn)發(fā)。

當(dāng)網(wǎng)絡(luò)業(yè)務(wù)分為時延敏感和可靠性敏感兩類業(yè)務(wù)時，優(yōu)先公平隊列調(diào)度算法在邏輯上維護(hù)兩個隊列，優(yōu)先隊列和普通隊列。當(dāng)有新業(yè)務(wù)到達(dá)時，首先根據(jù)業(yè)務(wù)屬性判斷出業(yè)務(wù)類型，若該業(yè)務(wù)類型屬于優(yōu)先業(yè)務(wù)，則將該業(yè)務(wù)分組置于優(yōu)先隊列隊尾，若檢測到優(yōu)先隊列為空，則將該業(yè)務(wù)分組插入優(yōu)先隊列隊首；若屬于普通業(yè)務(wù)，則將該業(yè)務(wù)分組置于普通隊列隊尾，若檢測到普通隊列為空，則將該分組插入普通隊列隊首。當(dāng)業(yè)務(wù)被調(diào)度轉(zhuǎn)發(fā)時，若優(yōu)先隊列不為空，則轉(zhuǎn)發(fā)優(yōu)先隊列中的業(yè)務(wù)分組，若優(yōu)先隊列為空，則轉(zhuǎn)發(fā)普通隊列中的業(yè)務(wù)分組，若在普通隊列分組轉(zhuǎn)發(fā)期間，有優(yōu)先業(yè)務(wù)分組到達(dá)，則待當(dāng)前普通業(yè)務(wù)分組發(fā)送完成后，再轉(zhuǎn)發(fā)優(yōu)先隊列分組，優(yōu)先隊列和普通隊列內(nèi)部采用先到先服務(wù)模式。

3 隱式網(wǎng)絡(luò)鏈路狀態(tài)測量方法

在綜合業(yè)務(wù)承載的IP網(wǎng)絡(luò)中，時延敏感業(yè)務(wù)一般具有較低且穩(wěn)定的傳輸速率，但需要相對持久的傳輸時間，要求較小的端到端時延，能夠容忍一定程度的分組丟失，如VoIP業(yè)務(wù)?？煽啃悦舾袠I(yè)務(wù)一般是傳統(tǒng)彈性網(wǎng)絡(luò)流，其接入峰值速率為接入線速率，對分組丟失率敏感，但可接受較大的端到端傳輸時延。因此，若根據(jù)業(yè)務(wù)請求接入峰值速率特征，將網(wǎng)絡(luò)業(yè)務(wù)分為兩類，則優(yōu)先調(diào)度機(jī)制可建模為兩隊列優(yōu)先排隊模型[4]。其中，優(yōu)先隊列分組具有絕對的優(yōu)先轉(zhuǎn)發(fā)權(quán)，優(yōu)先使用網(wǎng)絡(luò)資源來滿足其請求的服務(wù)質(zhì)量，普通隊列分組僅使用優(yōu)先隊列分組剩下的有效資源。當(dāng)網(wǎng)絡(luò)節(jié)點下游鏈路資源不足以實時轉(zhuǎn)發(fā)優(yōu)先分組時，優(yōu)先分組進(jìn)入緩存進(jìn)行排隊，因此，優(yōu)先隊列的排隊等待時間和優(yōu)先隊列分組隊長間接反映出下游鏈路承載狀態(tài)，隱式地反映出鏈路中時延敏感業(yè)務(wù)的負(fù)載狀態(tài)。由于可靠性敏感業(yè)務(wù)所在的普通隊列分組僅使用優(yōu)先隊列分組剩下有效鏈路資源，當(dāng)下游鏈路中資源不足時，普通隊列中的分組會得不到及時的服務(wù)，網(wǎng)絡(luò)節(jié)點進(jìn)程中該類業(yè)務(wù)數(shù)量隨之增加，因此，鏈路公平速率間接反映了下游鏈路普通業(yè)務(wù)的負(fù)載狀態(tài)。因此，利用優(yōu)先公平調(diào)度機(jī)制中優(yōu)先隊列隊長和鏈路公平速率參數(shù)能夠?qū)崿F(xiàn)對鏈路狀態(tài)的隱式測量。

設(shè)網(wǎng)絡(luò)節(jié)點通過在優(yōu)先隊列的入口處設(shè)置計數(shù)器對優(yōu)先隊列緩存中比特數(shù)進(jìn)行統(tǒng)計，利用該計數(shù)器的時間相對變化值估計出優(yōu)先隊列分組排隊的總比特數(shù)。假設(shè)在時刻t1，計數(shù)器的數(shù)值pb（t1），在時刻t2，計數(shù)器的數(shù)值為pb（t2），C是鏈路有效帶寬，則優(yōu)先隊列隊長priority_load計算公式為。

公平調(diào)度機(jī)制通常使用最大-最小公平份額算法計算鏈路的公平速率。設(shè)網(wǎng)絡(luò)節(jié)點進(jìn)程中共同承載M類業(yè)務(wù)，且各自有獨立的峰值速率，記為Rp={R1， R2，…， RM}，且R1

公平速率是一個隨進(jìn)程中業(yè)務(wù)規(guī)模波動而動態(tài)變化的值，能夠動態(tài)反應(yīng)鏈路負(fù)載狀態(tài)。

4 測量方法實驗與分析

4.1 仿真實驗設(shè)置

網(wǎng)絡(luò)仿真拓?fù)淙鐖D1所示，其中，s0 s1 s2 s3 s4 s5為六個源節(jié)點（信源），節(jié)點s0和s1設(shè)置為TCP Agent，應(yīng)用層協(xié)議為FTP；節(jié)點s2 s3 s4和s5設(shè)UDP Agent，應(yīng)用層協(xié)議為CBR。r1和r2為網(wǎng)絡(luò)節(jié)點，仿真對其間鏈路狀態(tài)進(jìn)行測量，網(wǎng)絡(luò)節(jié)點使用優(yōu)先公平調(diào)度機(jī)制，其它節(jié)點均應(yīng)用尾丟棄策略（DropTail），接納控制機(jī)制配置在鏈路入口節(jié)點處，鏈路總緩存為Bmax=64 個分組。為實現(xiàn)下游鏈路處于輕載、重載和過載不同狀態(tài)，四個發(fā)送CBR業(yè)務(wù)源節(jié)點的發(fā)送速率設(shè)為3Mbps，與網(wǎng)絡(luò)節(jié)點間的接入鏈路帶寬設(shè)置為3Mbps，兩個發(fā)送FTP業(yè)務(wù)源節(jié)點與網(wǎng)絡(luò)節(jié)點間的接入鏈路帶寬設(shè)為4 Mbps。網(wǎng)絡(luò)節(jié)點間的鏈路帶寬設(shè)為12 Mbps，所有鏈路時延均為1 ms。設(shè)時延敏感業(yè)務(wù)為語音UDP分組，可靠性敏感業(yè)務(wù)由TCP業(yè)務(wù)組成，優(yōu)先隊長和公平速率的測量間隔均為100 ms，仿真統(tǒng)計了目標(biāo)鏈路上兩類業(yè)務(wù)參數(shù)曲線分別如圖2，3所示。

4.2 實驗結(jié)果與分析

由圖2可知，四個CBR信源分別在0.0 s，2.5 s，5.0 s，7.5 s時刻開始發(fā)送數(shù)據(jù)，在10.0 s 11.0 s 12.0 s 12.5 s時刻停止發(fā)送。在0.0 s到2.5 s時間范圍內(nèi)，一個CBR信源發(fā)送數(shù)據(jù)，峰值速率為3 Mbps，而網(wǎng)絡(luò)鏈路帶寬為12 Mbps，此時優(yōu)先隊列隊長均值為零，下游鏈路能夠及時轉(zhuǎn)發(fā)所有的CBR分組，不需等待調(diào)度，優(yōu)先隊列處于輕載狀態(tài)。在2.5 s到5.0 s時間內(nèi)，兩個CBR信源發(fā)送數(shù)據(jù)，峰值速率為6 Mbps，下游網(wǎng)絡(luò)鏈路出現(xiàn)來不及轉(zhuǎn)發(fā)已到達(dá)優(yōu)先分組，優(yōu)先分組需要排隊等待調(diào)度轉(zhuǎn)發(fā)服務(wù)，此時優(yōu)先隊長在15個分組到25個分組之間浮動，反映出優(yōu)先業(yè)務(wù)負(fù)載狀態(tài)由輕載進(jìn)入重載情況。在5.0s到7.5s時間內(nèi)，CBR信源發(fā)送速率從6 Mbps增至9 Mbps，理論上下游鏈路出現(xiàn)重載情況，由于下游鏈路轉(zhuǎn)發(fā)速率低于優(yōu)先分組到達(dá)速率，因此，優(yōu)先隊列中緩存了大量等待轉(zhuǎn)發(fā)的優(yōu)先分組，優(yōu)先隊列隊長在25個分組到50個分組之間變化，達(dá)到了鏈路總緩存的50%以上，屬于重載情況。在7.5 s到10 s時間內(nèi)，CBR信源的總發(fā)送速率達(dá)到峰值，4個CBR信源同時發(fā)送，峰值速率達(dá)到12 Mbps，鏈路處于過載狀態(tài)，此時，優(yōu)先隊列中緩存的分組個數(shù)已高達(dá)64個，達(dá)到了設(shè)置的隊列長度的最大值，反映網(wǎng)絡(luò)鏈路處于過載狀態(tài)。

由圖3可知，兩個FTP信源分別在0.0 s和0.5 s處開始發(fā)送數(shù)據(jù)，在12.0 s和12.5 s處結(jié)束發(fā)送數(shù)據(jù)。在仿真開始時，一個FTP信源開始發(fā)送數(shù)據(jù)，鏈路公平速率在短時間內(nèi)升到8Mbps，反映出下游網(wǎng)絡(luò)鏈路分配了充足的有效帶寬用于普通業(yè)務(wù)傳輸。在2.5s處，5.0s處和7.5秒處公平速率分別出現(xiàn)了明顯下降并逐漸穩(wěn)定的過程，在7.5s之后降到接近0，下游網(wǎng)絡(luò)鏈路普通業(yè)務(wù)的吞吐量降為0，此時，普通業(yè)務(wù)處于餓死狀態(tài)，網(wǎng)絡(luò)處于嚴(yán)重?fù)砣麪顟B(tài)。

綜上所述，當(dāng)網(wǎng)絡(luò)鏈路處于輕載狀態(tài)時，優(yōu)先業(yè)務(wù)分組被直接轉(zhuǎn)發(fā)，優(yōu)先隊列的平均長度為零，普通業(yè)務(wù)分組使用優(yōu)先分組剩余有效帶寬，以較高的公平速率進(jìn)行傳輸。當(dāng)鏈路處于輕微的重載狀態(tài)時，優(yōu)先業(yè)務(wù)分組通過排隊使用下游網(wǎng)絡(luò)鏈路資源，并使用非搶占型調(diào)度，優(yōu)先分組等待正在發(fā)送普通分組完成后才插入隊首被調(diào)度，因此，優(yōu)先隊列隊長隨時間增加到一定數(shù)值，且鏈路公平速率開始降低。當(dāng)鏈路處于重載狀態(tài)時，下游網(wǎng)絡(luò)鏈路由于來不及轉(zhuǎn)發(fā)收到的優(yōu)先分組，優(yōu)先分組排隊隊長增加到總緩存的50%以上，網(wǎng)絡(luò)鏈路剩下的有效帶寬進(jìn)一步減小，普通業(yè)務(wù)的鏈路公平速率與優(yōu)先業(yè)務(wù)負(fù)載率成反比例變化，但仍維持著最基本的普通業(yè)務(wù)吞吐量。當(dāng)鏈路處于過載狀態(tài)時，優(yōu)先業(yè)務(wù)使用全部網(wǎng)絡(luò)鏈路帶寬以滿足其請求的服務(wù)質(zhì)量參數(shù)，擠占了普通業(yè)務(wù)需求的網(wǎng)絡(luò)資源，普通業(yè)務(wù)的傳輸被迫中斷，鏈路公平速率降到零?？梢姡趦?yōu)先公平調(diào)度處理時統(tǒng)計優(yōu)先隊列長度，由最大-最小公平份額算法計算鏈路公平速率，能夠從不同角度估計下游鏈路的準(zhǔn)實時負(fù)載狀態(tài)，實現(xiàn)對網(wǎng)絡(luò)鏈路狀態(tài)的隱式測量。

5 結(jié)語

所提隱式網(wǎng)絡(luò)鏈路狀態(tài)測量方法能夠準(zhǔn)實時的反應(yīng)網(wǎng)絡(luò)鏈路中不同業(yè)務(wù)的負(fù)載狀態(tài)，相較于主動測量方法，不需要發(fā)送探測分組，減少了測量過程對鏈路本身狀態(tài)的影響。相較于傳統(tǒng)被動測量方法，不需要設(shè)置網(wǎng)絡(luò)流量監(jiān)測點，不涉及網(wǎng)絡(luò)業(yè)務(wù)的隱私安全。所提網(wǎng)絡(luò)鏈路狀態(tài)測量方法通過周期性測量獲得鏈路狀態(tài)信息，存在一定的時滯性，能夠為一般網(wǎng)絡(luò)監(jiān)測提供應(yīng)用參考。

參考文獻(xiàn)

[1]尹浩，李峰.互聯(lián)網(wǎng)性能測量技術(shù)發(fā)展研究[J].計算機(jī)研究與發(fā)展，2016，53（1）：3-14.

[2]馮韜，于建江.復(fù)雜環(huán)境下的網(wǎng)絡(luò)時延測量方法研究[J].科技信息，2012，（22）：27，29.

[3]林闖，單志廣，任豐原.計算機(jī)網(wǎng)絡(luò)的服務(wù)質(zhì)量（QoS）[M].北京：清華大學(xué)出版社，2004：170-174.

[4]邱恭安，張順頤，胡雋.基于模糊流感知的動態(tài)優(yōu)先公平調(diào)度算法[J].電子與信息學(xué)報，2009，31（2）： 467-471.