两次随机丢包的被动队列管理的方法

摘要

本发明公开了一种两次随机丢包的被动队列管理的方法。在网络发生拥塞，瓶颈节点队列满时，在瓶颈节点队列中两次丢弃数据包，每次随机丢弃1个。本发明方法简单，不会增加瓶颈节点的计算量，避免全局同步和死锁，改善了网络传输的公平性，提高网络资源的利用率。

权利要求

1.一种两次随机丢包的被动队列管理的方法，在网络发生拥塞，瓶颈节点队列满时，在瓶颈节点队列中两次丢弃数据包，每次随机丢弃1个，其特征是，对于瓶颈节点具体操作步骤如下：Q表示瓶颈节点队列的最大长度，q表示当前瓶颈节点队列长度；

(1)判断是否有新的数据包要进入瓶颈节点队列：如果否，则还是在第(1)步；如果是，则到第(2)步；

(2)判断是否q≥Q-1：如果是，则到第(3)步；如果否，则到第(7)步；

(3)调用随机函数计算得到[1，q-1]之间的随机数；

(4)丢弃位于步骤(3)计算得到的随机数位置的数据包；

(5)再调用随机函数计算得到[1，q-2]之间的随机数；

(6)丢弃位于步骤(5)计算得到的随机数位置的数据包；

(7)新数据包进入瓶颈节点队列，然后再到第(1)步。

说明书

两次随机丢包的被动队列管理的方法

技术领域

[0001] 本发明涉及数据通信领域，尤其涉及两次随机丢包的被动队列管理的方法。

背景技术

[0002] TCP通过“慢启动”、“拥塞避免”、“快速重传”、“快速恢复”4个算法设置不同的参数来实现不同TCP拥塞控制，就是和式增加积式减少（AIMD，additive increase multiplicative decrease），TCP根据拥塞窗口来调整发送速度。瓶颈节点中最常用的队列管理策略是“弃尾”（Drop Tail），即随着缓冲区的溢出而丢包，是一种被动队列管理机制。“弃尾”的缺陷包括数据流的全局同步，死锁及持续队满造成的突发数据流被扼杀等。主动队列管理虽然可以有效地解决“全局同步”问题，但存在参数设置敏感，响应相对滞后于实际网络状况的缺陷，其算法比较复杂。在实际使用中，复杂的算法给网络设备带来很大的开销，中间节点的性能下降，反而加重了网络拥塞，所以目前各种主动队列管理算法并没有在网络上大量使用。

发明内容

[0003] 本发明的目的就是采用两次随机丢包的被动队列管理的方法，避免全局同步和死锁，提高网络资源的利用率。在网络发生拥塞，瓶颈节点队列满时，在瓶颈节点队列中两次丢弃数据包，每次随机丢弃1个。该方法简单，不会增加瓶颈节点的计算量。由于是在瓶颈节点队列满时才丢弃数据包，所以是一种被动式队列管理的方法。

[0004] 为了实现上述目的，本发明采用的技术方案是：

[0005] 当瓶颈节点队列满时，计算一个1到队列长度减1的随机数，丢弃位于该随机数的数据包；再次计算一个1到当前队列长度减1（为丢包前队列长度减2）的随机数，再丢弃位于该随机数的数据包。采用两次随机丢包主要是因为：（1）瓶颈节点队列满时，说明拥塞比较严重，因此只丢弃1个数据包是不够的；（2）如果一个TCP链接在队列中的数据包个数为n个，队列最大长度为Q个数据包，则该TCP链接第一次被丢包的概率为n/Q，第二次被丢包的概率为(n-1)/(Q-1)或为n/(Q-1)，因此对占据队列较多的TCP链接有更好的惩罚作用，改善公平性。瓶颈节点具体操作步骤如下：

[0006] Q表示瓶颈节点队列的最大长度，q表示当前瓶颈节点队列长度。

[0007] （1）判断是否有新的数据包要进入瓶颈节点队列，如果否，则还是在第（1）步，如果是，则到第（2）步；

[0008] （2）判断是否q≥Q-1，如果是，则到第（3）步，如果否，则到第（7）步；

[0009] （3）调用随机函数计算得到[1,q-1]之间的随机数；

[0010] （4）丢弃位于步骤（3）计算得到的随机数位置的数据包；

[0011] （5）调用随机函数计算得到[1,q-2]之间的随机数；

[0012] （6）丢弃位于步骤（5）计算得到的随机数位置的数据包；

[0013] （7）新数据包进入瓶颈节点队列，然后再到第（1）步。

[0014] 本发明方法能避免全局同步和死锁，改善网络传输的公平性，提高网络资源的利用率。该方法简单，适合在现有的Internet上使用。

附图说明

[0015] 图1 是本发明方法的流程图；

[0016] 图2 是本发明方法进行测试的网络拓扑。

具体实施方式

[0017] 下面结合附图对本发明作进一步详细说明。

[0018] 本发明中Q表示队列的最大长度，q表示当前瓶颈节点队列长度。瓶颈节点对新数据包的处理方法如图1所示，

[0019] （1）判断是否有新的数据包要进入瓶颈节点队列，如果否，则还是在第（1）步，如果是，则到第（2）步；

[0020] （2）判断是否q≥Q-1，如果是，则到第（3）步，如果否，则到第（7）步；

[0021] （3）调用随机函数计算得到[1,q-1]之间的随机数；

[0022] （4）丢弃位于步骤（3）计算得到的随机数位置的数据包；

[0023] （5）调用随机函数计算得到[1,q-2]之间的随机数；

[0024] （6）丢弃位于步骤（5）计算得到的随机数位置的数据包；

[0025] （7）新数据包进入瓶颈节点队列，然后再到第（1）步。

[0026] 图2是本发明方法的测试网络环境，R0为瓶颈节点，瓶颈链路位于节点R0和节点R1之间，链路容量12Mbps，延时15ms，分别采用不同的队列管理，缓存大小为30 packets；节点Si均为持久性FTP业务源，他们与节点R0之间的链路容量均为20Mbps，延时15ms，向目标节点Di发送数据；节点Di与节点R1之间的链路容量均为20Mbps，延时15ms；数据包均为1040Byte(包括40Byte包头)。接收端Di的窗口设置足够大，使得TCP发送仅受拥塞窗口Cwnd控制。

[0027] 表1是本发明方法图1实施例与弃尾被动队列管理、RED主动队列管理、1次随机丢包被动队列管理方法在图2网络环境下进行比对，设置发送节点S的个数分别为2、4、6、8、10，接收节点D的个数与发送节点相同，统计80s内瓶颈链路R0到R1传输的有效包个数。
本发明方法的效率要高于弃尾被动队列管理、RED主动队列管理和1次随机丢包被动队列管理。特别是在2个发送节点时，本发明的方法传输有效数据包比弃尾被动队列管理、RED主动队列管理、1次随机丢包被动队列管理分别高出8.8%、16.3%、7.2%。本发明方法能有效提高网络的传输效率。

[0028] 表1

[0029]发送端个数 2 4 6 8 10
弃尾被动队列管理 98867 100649 101943 102470 103249
RED主动队列管理 92517 95109 96768 97922 98784
1次随机丢包被动队列管理 100428 103438 105884 108468 109732
本发明方法 107614 108163 108383 109401 109957

[0030] 本实施例并非构成对本发明的限制，本领域技术人员在通过阅读本实施例后做出的等同变换，也属于本发明的保护范围。