基于改進令牌桶算法的分級協同流控模型設計*

黎 明，茍 江，梁衛星

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

0 引言

近幾十年來，民用飛機空地傳輸技術高速發展，空地傳輸設備從高頻（High Frequency，HF）、甚高頻（Very High Frequency，VHF）到L 頻段海事衛星通信，再到3G、4G、5G，空地網絡（Air-To-Ground，ATG）及Ku/Ka 頻段寬帶衛星通信，各鏈路實時性、可靠性、帶寬及傳輸成本各不相同，不同種類業務對安全性、可靠性需求亦不相同，這對空地傳輸提出了新的傳輸服務質量需求。國外民用飛機如A320、A330 等采用柯林斯的設備對機載無線鏈路集中管理，提供空地分級傳輸服務，實現鏈路管理集中化、多源數據歸一化、空地傳輸標準化，同時對傳輸過程實施流量控制。國內民機尚不具備空地分級傳輸技術及相關設備。空地分級傳輸需突破的其中一個關鍵技術就是空地傳輸的流量控制模型。

目前，傳輸控制協議/互聯網協議（Transmission Control Protocol/Internet Protocol，TCP/IP）分層協議模型是網絡流量控制算法的基礎。TCP/IP 協議層之間互相獨立，各層網絡流量控制算法性能指標互有差異，很多流控算法研究都集中在了網絡層和鏈路層[1,2]：在網絡層，為了提高傳輸服務質量，路由協議設計了新的路徑選取指標[3,4]；在鏈路層，調度策略使用等待延遲或預估延遲作為隊列調度優先級的依據[5,6]。

由于TCP/IP 協議模型各層相互獨立，層間信息彼此不透明，流量控制優化僅使用層內數據將無法高效應對網絡環境和層間出現的變化，進而總體流控優化目標得不到滿足。此外，各協議層控制命令交互需要頻繁進行協議頭封裝和解封裝，占用了大量的通信和系統資源。

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

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

1 協同流控模型

本文將打破網絡層、傳輸層獨立工作的協議限制，將網絡層和傳輸層統一建模，對網絡通信的傳輸服務質量進行綜合表述。在此基礎上，對各層的參數進行優化選擇，最終實現網絡性能的跨層優化和協同控制，協同流控模型如圖1 所示。

1.1 網絡層流量控制

在網絡層，通過建立多優先級隊列的方式，實現不同安全等級業務流的流量控制。采用區分隊列服務算法[11]，使數據的調度優先級根據業務的服務質量（Quality of Service，QoS）需求和網絡環境進行更新。

在傳輸系統中各節點，網絡層均維護一個數據隊列，尚未轉發的數據包緩存在隊列中。以節點中一個數據包為例，若T表示數據包的剩余生存時間，D表示數據包的允許最大端到端時延，d表示數據包在已完成傳輸中消耗的時間，T、D、d滿足：

各節點根據T值將數據包從小到大排序，并按順序發送各個數據包；若各節點收到的數據包的T值小于零，則該數據包將被節點丟棄，否則依據上述排序規則將數據包插到本節點維護數據隊列的相應位置。

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

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

1.2 傳輸層流量控制

典型的傳輸層流控策略數學優化模型為[12]：

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

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

1.3 網絡層與傳輸層協同流量控制技術

傳輸層和網絡協同流控數學優化模型為[13]：

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

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

2 改進的令牌桶流控算法

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

圖2 令牌桶算法

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

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

圖3 令牌分配策略

3 仿真分析

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

3.1 功能仿真

功能仿真主要用于驗證系統的流量控制相關功能，實驗步驟如下：

（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。

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

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

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

圖4 隊列出棧、入棧速率統計

圖5 數據元丟棄率統計

到第7 s 時限速提高至1 000 kbit/s，出棧速率立刻提升到規定速率，統計數據元丟棄率下降到33.3%附近。

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

3.2 性能仿真

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

仿真結果如圖6 所示，橫坐標為各隊列的入棧速率，縱坐標為隊列的出棧速率總和，業務流的數量使用不同樣式線條，速率的計量單位是數據元（cell）個數，根據系統設計，每一個cell 對應的數據大小是1 KB。

圖6 隊列性能仿真

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

3.3 結果分析

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

4 結語

本研究通過分析傳輸層、網絡層各協議層獨立流控算法的特性，在綜合考慮空地傳輸網絡環境及不同業務流傳輸服務質量需求的基礎上，以理論模型為指導，設計了基于改進令牌桶算法的分級協同流量控制模型，提出了多協議層級優先級隊列的協同流控調度機制，以實現機載數據空地分級可靠傳輸。通過功能仿真和性能仿真實驗可知，本文提出的模型和算法是高效可行的。