基于改進令牌桶算法的分級協(xié)同流控模型設(shè)計*

黎 明，茍 江，梁衛(wèi)星

（中電科航空電子有限公司,四川 成都 611731）

0 引言

近幾十年來，民用飛機空地傳輸技術(shù)高速發(fā)展，空地傳輸設(shè)備從高頻（High Frequency，HF）、甚高頻（Very High Frequency，VHF）到L 頻段海事衛(wèi)星通信，再到3G、4G、5G，空地網(wǎng)絡(luò)（Air-To-Ground，ATG）及Ku/Ka 頻段寬帶衛(wèi)星通信，各鏈路實時性、可靠性、帶寬及傳輸成本各不相同，不同種類業(yè)務(wù)對安全性、可靠性需求亦不相同，這對空地傳輸提出了新的傳輸服務(wù)質(zhì)量需求。國外民用飛機如A320、A330 等采用柯林斯的設(shè)備對機載無線鏈路集中管理，提供空地分級傳輸服務(wù)，實現(xiàn)鏈路管理集中化、多源數(shù)據(jù)歸一化、空地傳輸標(biāo)準(zhǔn)化，同時對傳輸過程實施流量控制。國內(nèi)民機尚不具備空地分級傳輸技術(shù)及相關(guān)設(shè)備?？盏胤旨墏鬏斝柰黄频钠渲幸粋€關(guān)鍵技術(shù)就是空地傳輸?shù)牧髁靠刂颇Ｐ汀?/p>

目前，傳輸控制協(xié)議/互聯(lián)網(wǎng)協(xié)議（Transmission Control Protocol/Internet Protocol，TCP/IP）分層協(xié)議模型是網(wǎng)絡(luò)流量控制算法的基礎(chǔ)。TCP/IP 協(xié)議層之間互相獨立，各層網(wǎng)絡(luò)流量控制算法性能指標(biāo)互有差異，很多流控算法研究都集中在了網(wǎng)絡(luò)層和鏈路層[1,2]：在網(wǎng)絡(luò)層，為了提高傳輸服務(wù)質(zhì)量，路由協(xié)議設(shè)計了新的路徑選取指標(biāo)[3,4]；在鏈路層，調(diào)度策略使用等待延遲或預(yù)估延遲作為隊列調(diào)度優(yōu)先級的依據(jù)[5,6]。

由于TCP/IP 協(xié)議模型各層相互獨立，層間信息彼此不透明，流量控制優(yōu)化僅使用層內(nèi)數(shù)據(jù)將無法高效應(yīng)對網(wǎng)絡(luò)環(huán)境和層間出現(xiàn)的變化，進而總體流控優(yōu)化目標(biāo)得不到滿足。此外，各協(xié)議層控制命令交互需要頻繁進行協(xié)議頭封裝和解封裝，占用了大量的通信和系統(tǒng)資源。

為解決上述問題，很多流控算法通過綜合利用各層的特征數(shù)據(jù)，加強了網(wǎng)絡(luò)間協(xié)議的協(xié)同性，進而提高網(wǎng)絡(luò)流控的綜合性能指標(biāo)。例如，在網(wǎng)絡(luò)層，路由算法中計算路徑使用了數(shù)據(jù)在鏈路上的預(yù)估傳輸時間和鏈路的干擾比例信息[7]；在數(shù)據(jù)鏈路層，同時利用各隊列數(shù)據(jù)的優(yōu)先級和節(jié)點在當(dāng)前時隙中的傳輸速率共同決定屬于該節(jié)點隊列的調(diào)度權(quán)值[8]。但上述方法僅實現(xiàn)信息共享，仍然保留了各協(xié)議層行為的相互獨立，各層的控制策略并未協(xié)同融合。

本文擬將機載空地交互數(shù)據(jù)細(xì)分為獨立的業(yè)務(wù)流，實施精細(xì)化管控，并采用多層級流控綜合控制模式，結(jié)合網(wǎng)絡(luò)層、傳輸層流控技術(shù)在分層模型中各自的流控特點，打破各層次之間獨立運作形式，設(shè)計包括網(wǎng)絡(luò)層和傳輸層在內(nèi)的多層級協(xié)同流控機制，更加精確地控制不同優(yōu)先級、不同安全等級業(yè)務(wù)流的傳輸服務(wù)質(zhì)量[9,10]。

1 協(xié)同流控模型

本文將打破網(wǎng)絡(luò)層、傳輸層獨立工作的協(xié)議限制，將網(wǎng)絡(luò)層和傳輸層統(tǒng)一建模，對網(wǎng)絡(luò)通信的傳輸服務(wù)質(zhì)量進行綜合表述。在此基礎(chǔ)上，對各層的參數(shù)進行優(yōu)化選擇，最終實現(xiàn)網(wǎng)絡(luò)性能的跨層優(yōu)化和協(xié)同控制，協(xié)同流控模型如圖1 所示。

1.1 網(wǎng)絡(luò)層流量控制

在網(wǎng)絡(luò)層，通過建立多優(yōu)先級隊列的方式，實現(xiàn)不同安全等級業(yè)務(wù)流的流量控制。采用區(qū)分隊列服務(wù)算法[11]，使數(shù)據(jù)的調(diào)度優(yōu)先級根據(jù)業(yè)務(wù)的服務(wù)質(zhì)量（Quality of Service，QoS）需求和網(wǎng)絡(luò)環(huán)境進行更新。

在傳輸系統(tǒng)中各節(jié)點，網(wǎng)絡(luò)層均維護一個數(shù)據(jù)隊列，尚未轉(zhuǎn)發(fā)的數(shù)據(jù)包緩存在隊列中。以節(jié)點中一個數(shù)據(jù)包為例，若T表示數(shù)據(jù)包的剩余生存時間，D表示數(shù)據(jù)包的允許最大端到端時延，d表示數(shù)據(jù)包在已完成傳輸中消耗的時間，T、D、d滿足：

各節(jié)點根據(jù)T值將數(shù)據(jù)包從小到大排序，并按順序發(fā)送各個數(shù)據(jù)包；若各節(jié)點收到的數(shù)據(jù)包的T值小于零，則該數(shù)據(jù)包將被節(jié)點丟棄，否則依據(jù)上述排序規(guī)則將數(shù)據(jù)包插到本節(jié)點維護數(shù)據(jù)隊列的相應(yīng)位置。

在t時刻，Qn(t)表示節(jié)點n的數(shù)據(jù)隊列長度。Qn(t)在每個時刻進行更新，更新算法為：

式中：μni(t)為t時刻，由節(jié)點n向節(jié)點i傳輸?shù)臄?shù)據(jù)量，滿足μni(t)∈[0,μmax]；l{n=sm}為指示函數(shù)，若節(jié)點n作為會話m源節(jié)點，則該指示函數(shù)值為1；O(n)為發(fā)送節(jié)點n的所有接收鄰近節(jié)點的集合；I(n)為接收節(jié)點n的所有發(fā)送鄰近節(jié)點的集合；μjn(t)為t時刻，由節(jié)點j向節(jié)點n傳輸?shù)臄?shù)據(jù)量；r(t)是當(dāng)前節(jié)點內(nèi)各數(shù)據(jù)剩余生存時間的期望值。

1.2 傳輸層流量控制

典型的傳輸層流控策略數(shù)學(xué)優(yōu)化模型為[12]：

式中：m為源節(jié)點與目的節(jié)點之間建立的會話；xm為表示會話m的數(shù)據(jù)流速率；x為各xm組成的向量；為通信鏈路l中屬于會話m的數(shù)據(jù)流速率；cl為通信鏈路l可支持的最大數(shù)據(jù)傳輸速率；L(m)為會話m的數(shù)據(jù)流經(jīng)所有通信鏈路l的集合；Λ 為網(wǎng)絡(luò)可支持會話數(shù)據(jù)速率區(qū)域；Um(xm)=log(1+xm)。

式（4）表示某個通信鏈路上所有會話數(shù)據(jù)速率和應(yīng)小于該通信鏈路支持的最大傳輸速率；式（5）表示向量x中各會話速率xm都應(yīng)大于等于零；式（6）表示各會話的數(shù)據(jù)速率屬于可支持會話數(shù)據(jù)速率區(qū)域。

1.3 網(wǎng)絡(luò)層與傳輸層協(xié)同流量控制技術(shù)

傳輸層和網(wǎng)絡(luò)協(xié)同流控數(shù)學(xué)優(yōu)化模型為[13]：

式中：Pe為鏈路目標(biāo)誤碼率；ym(Pe)為會話m丟包率；Um為會話m的網(wǎng)絡(luò)效益函數(shù)；l為網(wǎng)絡(luò)節(jié)點或網(wǎng)絡(luò)鏈路；Hl為網(wǎng)絡(luò)節(jié)點或網(wǎng)絡(luò)鏈路l的資源損耗函數(shù)；wl為網(wǎng)絡(luò)節(jié)點或網(wǎng)絡(luò)鏈路l獲得的功率、信道等資源；w為wl構(gòu)成的向量；W為物理層獲得的功率、信道等資源分配結(jié)果集；r為所有會話的路由路徑矩陣，值為|l|×|m|；R為所有路由矩陣集合；f為表示鏈路層可同時傳輸?shù)逆溌肪仃?，f的值為1×L，L表示網(wǎng)絡(luò)中鏈路的數(shù)量；F為同時成功傳輸且互不干擾的鏈路矩陣集合；C(w,Pe)為由wl和Pe共同確定的最大鏈路容量，C(…,…)表示鏈路容量算法。

上述優(yōu)化模型的優(yōu)化目標(biāo)是使全網(wǎng)獲得的網(wǎng)絡(luò)效益與資源損耗和的最大化。模型中：式（8）表示經(jīng)過任意通信鏈路的會話數(shù)據(jù)速率和應(yīng)小于該通信鏈路最大帶寬；式（9）表示會話速率會受到鏈路層運行機制的約束；式（10）、式（11）和式（12）表示優(yōu)化模型中用的路由矩陣、鏈路矩陣及物理層資源屬于F、R和W的集合。

2 改進的令牌桶流控算法

在傳輸層的流量控制機制中，為實現(xiàn)精準(zhǔn)的流量控制功能，使用了令牌桶算法。令牌分配策略由傳輸層流控模塊計算和分配，傳輸層流控模塊的令牌桶算法的基本原理如圖2 所示。

圖2 令牌桶算法

令牌桶算法中，在無需限速時，算法讓入棧數(shù)據(jù)全速出棧；當(dāng)需要限速時，算法會周期性（系統(tǒng)中為1 s）地提供令牌，令牌數(shù)量根據(jù)傳輸層流控模塊計算下發(fā)，數(shù)據(jù)元（cell）獲得令牌則可轉(zhuǎn)發(fā)，否則將緩存在隊列中。令牌分配的數(shù)量直接決定了數(shù)據(jù)的出棧速率。

如圖1 所示，在傳輸層，機載應(yīng)用的業(yè)務(wù)流通過統(tǒng)一接口發(fā)送給傳輸層流控代理模塊，將其封裝后放入相應(yīng)的應(yīng)用隊列中；調(diào)度器的設(shè)計借鑒操作系統(tǒng)任務(wù)調(diào)度機制[14]，依據(jù)傳輸層流控模塊分配給各個應(yīng)用隊列的令牌值，輪詢出隊各應(yīng)用隊列中的數(shù)據(jù)包并將其發(fā)送到網(wǎng)絡(luò)層，進行下一層級的傳輸。傳輸層流控模塊通過各傳輸層流控代理模塊上報的隊列狀態(tài)統(tǒng)計信息和當(dāng)前網(wǎng)絡(luò)層隊列擁塞狀態(tài)，實時計算各應(yīng)用隊列的令牌值，并發(fā)送給各調(diào)度器使用。若傳輸層流控模塊發(fā)現(xiàn)網(wǎng)絡(luò)層出現(xiàn)擁塞，則通過令牌桶算法重新計算各應(yīng)用隊列所分配的令牌值，限制其傳輸速率。傳輸層流控模塊的令牌分配策略如圖3 所示。

圖3 令牌分配策略

3 仿真分析

在仿真中，主要進行功能仿真和性能仿真兩個方面的測試。

3.1 功能仿真

功能仿真主要用于驗證系統(tǒng)的流量控制相關(guān)功能，實驗步驟如下：

（1）在0～4 s，入棧速率從0 逐漸增加到1 500 kbit/s，之后維持該入棧速率；

（2）第2 s 時，限制隊列出棧速率至500 kbit/s；

（3）第7 s 時，限制隊列出棧速率至1 000 kbit/s；

（4）第13 s時，限制隊列出棧速率至1 500 kbit/s。

根據(jù)本科醫(yī)學(xué)教育教學(xué)改革的要求，不斷完善考核制度是提高醫(yī)學(xué)本科學(xué)生教學(xué)質(zhì)量的重要環(huán)節(jié)[1]。在本校教育教學(xué)改革的過程中，將醫(yī)學(xué)免疫學(xué)與微生物學(xué)課程考核分為平時考核和期末考核。其中，考勤、課堂表現(xiàn)、作業(yè)是學(xué)生平時考核的主要內(nèi)容。因為作業(yè)是學(xué)生復(fù)習(xí)并鞏固所學(xué)醫(yī)學(xué)免疫學(xué)與微生物學(xué)知識，獨立運用所學(xué)知識解決臨床相關(guān)問題，提高學(xué)生綜合素質(zhì)能力的重要手段；并且在教學(xué)過程中，教師也可以通過作業(yè)了解學(xué)生對所學(xué)內(nèi)容的掌握情況及應(yīng)用能力，以便更好地改進教學(xué)策略和方法，提高教學(xué)效果[2]。因此，作業(yè)在醫(yī)學(xué)免疫學(xué)與微生物學(xué)課程平時考核中占有很大比例。

數(shù)據(jù)記錄了隊列的入棧、出棧速率（圖4），以及隊列內(nèi)緩存數(shù)據(jù)元（cell）的丟棄率（圖5），為了便于觀察數(shù)據(jù)元的丟棄現(xiàn)象，避免出現(xiàn)較大的延遲，此隊列的長度設(shè)置較短。

如圖4 所示，虛線為入棧速率，實線為出棧速率。0～2 s 時由于沒有限速，隊列全速轉(zhuǎn)發(fā)，出棧速率與入棧速率相等。當(dāng)?shù)? s 時，限速至500 kbit/s，出棧速率穩(wěn)定維持在500 kbit/s 左右，此處的波動主要由程序的異步采樣引入。此時，圖5 中統(tǒng)計出數(shù)據(jù)元的丟棄率在66.6%，與理論計算值相符。

圖4 隊列出棧、入棧速率統(tǒng)計

圖5 數(shù)據(jù)元丟棄率統(tǒng)計

到第7 s 時限速提高至1 000 kbit/s，出棧速率立刻提升到規(guī)定速率，統(tǒng)計數(shù)據(jù)元丟棄率下降到33.3%附近。

仿真進行到13 s 時，出棧速率限制提高到1 500 kbit/s，則圖4 中記錄的出棧速率迅速提高至1 500 kbit/s，圖5 中隊列的丟包率也下降至0 附近。由于此時仍然存在限速，出入棧速率雖然都設(shè)置為1 500 kbit/s，但存在系統(tǒng)異步采樣的統(tǒng)計問題，所以數(shù)據(jù)元的丟棄率不完全為0。通過以上仿真，驗證了本算法能夠通過調(diào)度令牌桶數(shù)量，實現(xiàn)對隊列的精確控制。

3.2 性能仿真

性能仿真用于驗證本算法在單機設(shè)備上的出棧隊列速率上限。

仿真結(jié)果如圖6 所示，橫坐標(biāo)為各隊列的入棧速率，縱坐標(biāo)為隊列的出棧速率總和，業(yè)務(wù)流的數(shù)量使用不同樣式線條，速率的計量單位是數(shù)據(jù)元（cell）個數(shù)，根據(jù)系統(tǒng)設(shè)計，每一個cell 對應(yīng)的數(shù)據(jù)大小是1 KB。

圖6 隊列性能仿真

從圖6 可以看出，當(dāng)使用單個隊列注入數(shù)據(jù)時，出棧速率最高接近500 000 個cell 每秒，換算為速率約為4 000 Mbit/s。單個隊列速率上限受到主流軟件的性能約束。隨著使用隊列的增加，總的出棧速率逐漸逼近性能上限，當(dāng)超過15個隊列全速注流時，系統(tǒng)出棧速率接近800 000 個cell 每秒，換算為速率約為6 400 Mbit/s。

3.3 結(jié)果分析

傳統(tǒng)的令牌桶算法主要包括向令牌桶中填充令牌的速率參數(shù)-CIR、令牌桶容量參數(shù)-CBS、超額突發(fā)尺寸-EBS 3 個參數(shù)。該算法一般采用雙桶結(jié)構(gòu)：C 桶（CBS 桶）和E 桶（EBS 桶），兩個令牌桶總?cè)萘糠謩e為承諾突發(fā)尺寸（Committed Burst Size，CBS）和超額突發(fā)尺寸（Excess Burst Size，EBS）。兩桶的初始值都是滿值：CBS 和EBS。當(dāng)令牌按照承諾訪問速率（Committed Access Rate，CAR）生成時，先往C 桶中填充直至填滿，C 桶填滿后，再往E 桶中填充，當(dāng)兩桶都被填滿時，令牌桶將丟棄新產(chǎn)生的令牌。該算法的不足：若某一時刻的隊列入隊速率達到CBS ＋EBS，則只能使上一時間段的隊列入隊速率低于CAR，這樣系統(tǒng)就限制了應(yīng)用的傳輸，帶寬利用率低，并且容易出現(xiàn)丟包。本系統(tǒng)改進令牌桶算法原理與傳統(tǒng)算法相同，但單位時間結(jié)束后，并不清零E 桶，剩余的令牌留給下一時間段復(fù)用。使用這種改進方式，可以更大概率地減少擁塞時的數(shù)據(jù)丟包。

4 結(jié)語

本研究通過分析傳輸層、網(wǎng)絡(luò)層各協(xié)議層獨立流控算法的特性，在綜合考慮空地傳輸網(wǎng)絡(luò)環(huán)境及不同業(yè)務(wù)流傳輸服務(wù)質(zhì)量需求的基礎(chǔ)上，以理論模型為指導(dǎo)，設(shè)計了基于改進令牌桶算法的分級協(xié)同流量控制模型，提出了多協(xié)議層級優(yōu)先級隊列的協(xié)同流控調(diào)度機制，以實現(xiàn)機載數(shù)據(jù)空地分級可靠傳輸。通過功能仿真和性能仿真實驗可知，本文提出的模型和算法是高效可行的。