一种基于速率和队列长度的无线路由器主动队列管理方法

摘要

本发明公开了一种基于速率和队列长度的无线路由器主动队列管理方法。本发明共包括四个模块：入队模块，出队模块，更新模块和丢弃模块，根据缓存器入队速率和出队速率估计值，以及缓存器队列实时长度来控制调整数据分组丢弃概率，并同时利用缓存区入队速率和出队速率估计值来调整数据分组丢弃概率更新时间。本发明具有高适应性和高鲁棒性，在动态复杂的有线-无线异构网络环境下，具备在保证较高的链路利用率的条件下减小端到端时延的特点。

说明书

技术领域

本发明属于路由器队列管理和拥塞控制领域，涉及一种基于速率和队列长 度的无线路由器主动队列管理方法。

背景技术

网络拥塞控制是近十几年来一个热门的研究话题。经过实践证明，在传统 网络环境下，TCP端到端拥塞控制机制能够有效的防止拥塞崩溃现象的发生。 然而传统的端到端拥塞控制机制在公平性、端到端延时、链路利用率以及发生 拥塞后恢复正常工况的响应性等指标等方面效率低下，网络服务质量也得不到 很好的保证。所以主动队列管理（Active Queue Management,AQM）被推荐部 署在网络中间节点（如路由器）上来增强端到端拥塞控制机制性能。

主动队列管理方法的主要技术要求包括：（1）提供高的网络吞吐量，提 高网络带宽利用率；（2）降低网络端到端时延；（3）保证较高的鲁棒性和响 应性；（4）方法简单高效，便于推广和扩展，能部署到实际网络中并可以适 应不同的网络环境。

现有的主动队列管理方法中，由S.Floyd最早提出的随机早期检测 （RED）方法应用最广泛，在征求意见文件Request for Comment(RFC)2309中 被推荐为AQM唯一候选算法。但是随着实验研究的深入，人们逐渐发现RED算 法本身存在着很多不完善的地方，如稳定性不理想，对参数选取敏感等。所以 针对RED算法有着很多改进的版本，比如self-configuring RED（自配置 RED）、ARED(自适应RED)、loss ratio based RED(基于丢包速率的RED)。这 些改进的RED算法在一定程度上提升了RED算法在不同网络情形下的性能。 C.V.Hollot等人在TCP流量控制动态非线性模型基础上提出了包含PI（比例 积分）控制器的AQM。虽然PI控制器能够克服RED的部分局限，但是PI控制 器鲁棒性较差，不适应复杂多变的网络环境。

目前AQM方法有两个主要的问题尚未得到完满解决：（1）大多数现有AQM 方法是针对有线网络环境设计的，在无线网络环境下会导致网络服务质量下 降；（2）大多数现有AQM方法没有自适应性，尤其算法中的参数多为静态参 数，需要经过在经验基础上的选择才能够满足特定的网络环境。

发明内容

本发明的目的是克服现有技术的不足，提供一种能够保证高链路利用率和 低传输时延的基于速率和队列长度的无线路由器主动队列管理方法，能够适应 高误码率和网络容量变化的动态复杂有线-无线异构网络环境。

基于速率和队列长度的无线路由器主动队列管理方法，共分为入队模块， 更新模块，丢弃模块和出队模块四个模块，方法的步骤如下:

步骤（1）：初始化，等待新的数据分组到达；

步骤（2）：当新的数据分组到达后，如果现有缓存区队列长度Q(t)小于缓 存区最大队列长度Q_Max，转到步骤（3）；如果现有缓存区队列长度Q(t)等于缓 存区最大队列长度Q_Max，转到步骤（11）；

步骤（3）：数据分组入队，更新当前路由器缓存区队列长度Q(t)；

步骤（4）：根据下面公式：

r_in(t)＝(1-e^-ΔT/K)1/ΔT+e^-ΔT/Kr_in(t_pre)

估计缓存区入队速率，其中e是自然常数，r_in(t)为入队速率估计值，ΔT是更 新时间，K为调节常数，t_pre为前一次估计算法执行时刻；

步骤（5）：判断当前系统时间和前一次丢弃概率更新时间的差值是否大 于ΔT，是则转到下一步，否则转到步骤（8）；

步骤（6）：根据下面公式计算当前更新时间

$\mathrm{\Delta T}={\mathrm{Te}}^{-\delta |r_{\mathrm{in}}\left(t\right)-r_{\mathrm{out}}\left(t\right)|}$

其中e是自然常数，T为平均的往返时间Round-Trip Time，δ为更新时间调整 常数，r_in(t)和r_out(t)为入队速率和出队速率估计值；

步骤（7）：根据下列公式：

P(t)＝1-θ^-p(t)

p(t)＝p(t_pre)+γ[|r_in(t)-r_out(t)|+Q_max/Q(t)-1]

计算分组丢弃概率，其中P(t)为t时刻缓存区分组丢弃概率，θ和γ为调节丢 弃概率变化的常数；

步骤（8）：随机产生一个服从（0,1）上均匀分布的随机变量P，如果 转到步骤（9）；否则转到步骤（11）；

步骤（9）：数据分组出队，根据下列公式：

r_out(t)＝(1-e^-ΔT/K)1/ΔT+e^-ΔT/Kr_out(t_pre)

估计此时刻缓存区出队速率，转到步骤（12），其中e是自然常数，r_out(t)为 出队速率估计值，ΔT是当前更新时间，K为调节常数，t_pre为前一次估计算法执 行时刻；

步骤（10）：更新当前路由器缓存区队列长度Q(t)；

步骤（11）：丢弃该数据分组；

步骤（12）：转到步骤（2），重复步骤（2）到步骤（11），直至结 束。

本发明具有高适应性和高鲁棒性，在动态复杂的有线-无线异构网络环境 下，具备在保证较高的链路利用率的条件下减小端到端时延的特点。

附图说明

图1为本发明的模块示意图；

图2为本发明的软件流程图；

图3为本发明的仿真实验拓扑图；

图4为本发明中二态马尔科夫错误模型示意图；

图5为本发明中链路利用率随时间的变化图；

图6为本发明中端到端时延随时间的变化图。

具体实施方式

本发明为一种无线路由器主动队列管理方法，可称之为基于速率和队列长 度的主动队列管理方法（NRAQM）。目的是得到一种能够有效适应有线-无线异 构网络环境的主动队列管理方法。仿真实验结果表明，这种主动队列管理方法 能够有效适应有线-无线网络的时变特性，有良好的综合性能。

基于速率和队列长度的无线路由器主动队列管理方法，共分为入队模块， 更新模块，丢弃模块和出队模块四个模块，模块示意图如图1所示。本发明的 软件流程如图2所示，其中具体步骤如下:

步骤（1）：初始化，等待新的数据分组到达；

步骤（2）：当新的数据分组到达后，如果现有缓存区队列长度Q(t)小于缓 存区最大队列长度Q_Max，转到步骤（3）；如果现有缓存区队列长度Q(t)等于缓 存区最大队列长度Q_Max，转到步骤（11）；

步骤（3）：数据分组入队，更新当前路由器缓存区队列长度Q(t)；

步骤（4）：根据下面公式：

r_in(t)＝(1-e^-ΔT/K)1/ΔT+e^-ΔT/Kr_in(t_pre)，

估计缓存区入队速率，其中e是自然常数，r_in(t)为入队速率估计值，ΔT是更 新时间，K为调节常数，t_pre为前一次估计算法执行时刻；

步骤（5）：判断当前系统时间和前一次丢弃概率更新时间的差值是否大 于ΔT，是则转到下一步，否则转到步骤（8）；

步骤（6）：根据下面公式计算当前更新时间

其中e是自然常数，T为平均的往返时间Round-Trip Time，δ为更新时间调整 常数，r_in(t)和r_out(t)为入队速率和出队速率估计值；

步骤（7）：根据下列公式：

P(t)＝1-θ^-p(t)

p(t)＝p(t_pre)+γ[|r_in(t)-r_out(t)|+Q_max/Q(t)-1]

计算分组丢弃概率，其中P(t)为t时刻缓存区分组丢弃概率，θ和γ为调节丢 弃概率变化的常数；

步骤（8）：随机产生一个服从（0,1）上均匀分布的随机变量P，如果 转到步骤（9）；否则转到步骤（11）；

步骤（9）：数据分组出队，根据下列公式：

r_out(t)＝(1-e^-ΔT/K)1/ΔT+e^-ΔT/Kr_out(t_pre)

估计此时刻缓存区出队速率，转到步骤（12），其中e是自然常数，r_out(t)为 出队速率估计值，ΔT是当前更新时间，K为调节常数，t_pre为前一次估计算法执 行时刻；

步骤（10）：更新当前路由器缓存区队列长度Q(t)；

步骤（11）：丢弃该数据分组；

步骤（12）：转到步骤（2），重复步骤（2）到步骤（11），直至结 束。

本主动队列管理方法的核心是通过利用估计的缓存器入队速率和出队速 率、以及缓存器队列实时长度来控制调整数据分组丢弃概率，并同时利用估计 的缓存区入队速率和出队速率来调整数据分组丢弃概率更新的时间，来有效地 提升网络的性能。

本主动队列管理方法主要分为四个模块：入队模块、更新模块、丢弃模块 和出队模块。其中具体各个模块功能如下所述：入队模块主要功能是更新当前 路由器缓存区队列长度和估计缓存区入队速率，主要包含上述步骤（2），步 骤（3），步骤（4）；更新模块是本发明的核心模块，主要包含上述步骤 （5），步骤（6），步骤（7）；丢弃模块主要功能是以P(t)的概率对缓存区内 的数据分组做丢弃操作，主要包含上述步骤（8），步骤（11）；出队模块主 要功能是当数据分组出队后更新队列长度和估计缓存区出队速率，主要包含上 述步骤（9），步骤（10）。

实施例

本实施例在NS2(Network Simulator,Version2)网络仿真软件上实现了一 种基于速率和队列长度的主动队列管理方法(NRAQM)，并对它的性能进行了详 细测试。NS2网络仿真软件由UC Berkeley大学开发而成，是针对网络技术应 用测试的开源免费软件模拟平台。同时NS2是目前学术界广泛使用的一种网络 模拟软件，通过该平台所得出的研究结果也是被学术界所普遍认可的。

采用典型的杠铃型拓扑结构，如图3所示。其中n条数据流共用一条瓶颈 链路。W（1）,…,W(n)为发送节点，M（1）,…,M(n)为接收节点，R和BS为 路由器。数据发送端W(1),W(2),…,W(n)到R之间均为有线链路。数据接 收端M(1),M(2),…,M(n)和基站BS之间均为无线链路。

在实施例中以TCP-Reno为缺省传输层协议。瓶颈链路缓存区队列长度为20 个数据包。所有有线链路的带宽设置为10Mbps。所有链路传输时延设置为 10ms。

为了验证本发明在复杂网络情形下的鲁棒性。将仿真的环境设置为一个包 含流量变化、误码率变化和带宽变化的复杂情形。整个仿真实验持续60秒。 开始10秒钟内，基于TCP的FTP业务流数目从0增加到100，同时每个FTP流 持续时间为50秒，所有基于TCP的FTP业务流在实验开始60秒钟后都停止。 无线链路带宽会在2Mbps和11Mbps之间随机变化。同时为了更准确的表现无 线链路的误码率变化特点，采用了二态马尔科夫错误模型，如图3所示。其中 平均误码率P可由下列公式计算：

$P_{\mathrm{average}}=P_G\frac{P_{\mathrm{BG}}}{P_{\mathrm{BG}}+P_{\mathrm{GB}}}+P_B\frac{P_{\mathrm{GB}}}{P_{\mathrm{BG}}+P_{\mathrm{GB}}},$

其中G(Good)为误码率较低时的状态，误码率为P_G；B(Bad)为误码率较高时的 状态，误码率为P_B；而G和B之间转变的概率分别为P_GB和_PBG。

在实施例中将NRAQM与已有的RED、Drop Tail和PI等AQM控制器进行比 较。图4和图5分别是链路利用率和端到端时延随时间的变化图。从图4可以 看出，NRAQM比RED、Drop Tail和PI等AQM控制器有着更高的链路利用率。 这是因为NRAQM同时利用出队和入队速率作为参考变量，在带宽和误码率不断 变化的无线链路中有更好的性能。从图5可以看出，NRAQM和RED相对于Drop Tail和PI有着更小的端到端时延。同时还可以看到NRAQM的端到端时延比 RED、Drop Tail和PI的端到端时延震荡幅度更小。这是因为NRAQM采用的更 新计时模块可以使端到端时延更加平稳。