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

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

摘要：在不增加網(wǎng)絡(luò)開銷前提下為實(shí)現(xiàn)網(wǎng)絡(luò)實(shí)時(shí)狀態(tài)的測量，利用優(yōu)先公平調(diào)度原理中隱性的網(wǎng)絡(luò)狀態(tài)統(tǒng)計(jì)功能，提出使用周期性測量的優(yōu)先隊(duì)列隊(duì)長和鏈路公平速率指標(biāo)估計(jì)下游鏈路承載狀態(tài)，實(shí)現(xiàn)無開銷的鏈路狀態(tài)測量。仿真顯示優(yōu)先隊(duì)列隊(duì)長和鏈路公平速率變化曲線能夠反映出下游鏈路的不同負(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]，因此，實(shí)時(shí)獲得網(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)答分組分析計(jì)算網(wǎng)絡(luò)狀態(tài)，但增加了網(wǎng)絡(luò)額外開銷，且具有較大的網(wǎng)絡(luò)狀態(tài)測量時(shí)延。被動測量通過在網(wǎng)絡(luò)中設(shè)置流量監(jiān)測點(diǎn)，捕捉網(wǎng)絡(luò)的流量參數(shù)，獲取網(wǎng)絡(luò)承載業(yè)務(wù)的統(tǒng)計(jì)信息，其無需發(fā)送測量數(shù)據(jù)分組，但需要網(wǎng)絡(luò)節(jié)點(diǎn)設(shè)備被動地收集數(shù)據(jù)包，操作相對復(fù)雜，網(wǎng)絡(luò)狀態(tài)信息存在一定的陳舊性。隨著，網(wǎng)絡(luò)信息安全的提高以及多業(yè)務(wù)綜合承載的擴(kuò)展，既有網(wǎng)絡(luò)鏈路狀態(tài)測量方法的測量精度和時(shí)延受到很大影響[2]，針對該問題，本文利用優(yōu)先公平調(diào)度機(jī)制中隊(duì)長參數(shù)和鏈路公平速率實(shí)現(xiàn)隱式的網(wǎng)絡(luò)聯(lián)網(wǎng)狀態(tài)測量，能夠?yàn)閮深惒煌瑯I(yè)務(wù)分別提供業(yè)務(wù)匹配的鏈路狀態(tài)。

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

分組調(diào)度指按照一定的規(guī)則決定從等待隊(duì)列中選擇分組進(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)隊(duì)列賦予優(yōu)先級，當(dāng)調(diào)度分組時(shí)，如果高優(yōu)先級隊(duì)列非空，則其分組優(yōu)先被選擇服務(wù)。只有高優(yōu)先級隊(duì)列為空時(shí)，才會服務(wù)次高優(yōu)先隊(duì)列。為提高調(diào)度機(jī)制對鏈路狀態(tài)的適應(yīng)性和業(yè)務(wù)服務(wù)公平性，提出了相對優(yōu)先公平調(diào)度，其為高優(yōu)先隊(duì)列預(yù)留一定的緩存空間，使得低優(yōu)先隊(duì)列能相對公平地得到調(diào)度服務(wù)，僅當(dāng)優(yōu)先隊(duì)列隊(duì)長超過一定門限時(shí)，才為優(yōu)先隊(duì)列提供絕對的優(yōu)先轉(zhuǎn)發(fā)。

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

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

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

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

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

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

4 測量方法實(shí)驗(yàn)與分析

4.1 仿真實(shí)驗(yàn)設(shè)置

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

4.2 實(shí)驗(yàn)結(jié)果與分析

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

由圖3可知，兩個(gè)FTP信源分別在0.0 s和0.5 s處開始發(fā)送數(shù)據(jù)，在12.0 s和12.5 s處結(jié)束發(fā)送數(shù)據(jù)。在仿真開始時(shí)，一個(gè)FTP信源開始發(fā)送數(shù)據(jù)，鏈路公平速率在短時(shí)間內(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，此時(shí)，普通業(yè)務(wù)處于餓死狀態(tài)，網(wǎng)絡(luò)處于嚴(yán)重?fù)砣麪顟B(tài)。

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

5 結(jié)語

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

參考文獻(xiàn)

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

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

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

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