基于改进令牌桶算法的分级协同流控模型设计*

黎 明，苟 江，梁卫星

（中电科航空电子有限公司,四川 成都 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 结语

本研究通过分析传输层、网络层各协议层独立流控算法的特性，在综合考虑空地传输网络环境及不同业务流传输服务质量需求的基础上，以理论模型为指导，设计了基于改进令牌桶算法的分级协同流量控制模型，提出了多协议层级优先级队列的协同流控调度机制，以实现机载数据空地分级可靠传输。通过功能仿真和性能仿真实验可知，本文提出的模型和算法是高效可行的。