一种基于令牌的互联网流量控制方法

摘要

本发明公开了一种基于令牌的互联网流量控制方法，涉及分组交换网络的流量控制技术。该方法包括：用户终端设备根据网络拥塞情况设置待发送数据包的令牌级；网络接入路由器控制终端用户流入网络的令牌速度；网络中间路由器在输出接口上拥有一个物理拥塞控制器，物理拥塞控制器根据带宽资源拥塞程度自适应地调整物理拥塞指数，并按计算所得的公平丢包概率，随机丢弃令牌级小于物理拥塞指数的数据包；域间互连路由器的输出接口不但拥有物理拥塞控制器，还拥有一个虚拟拥塞控制器，虚拟拥塞控制器根据令牌资源的拥塞程度自适应地调整虚拟拥塞指数，降低所有输出数据包的令牌级。本发明能公平分配带宽资源，有效减少网络内部的丢包数量。

说明书

技术领域

本发明涉及了分组交换网络的流量控制技术，具体涉及一种基于令牌的互联网流量控制方法。

背景技术

目前互联网中路由器的流量控制功能较弱，仅通过丢包信号向用户终端设备提供网络拥塞信息，进入网络的流量主要由用户终端设备通过传输层或应用层来自主控制，网络缺乏相应的监控能力。随着断点续传、多线程下载等网络技术的出现，互联网的公平性和稳定性受到了挑战。核心无状态公平队列CSFQ(Core-Stateless Fair Queueing)就是一种增强网络流量控制能力的方法，它由网络接入路由器测量并标记会话流的发送速率，通常把源地址和目的地址均相同的数据包归为一个会话流；在网络中间路由器，根据输出接口的拥塞程度自适应地调整公平带宽参数，根据公平带宽与数据包所标识的发送速率的比值得到该数据包的接收概率；该方法在网络接入路由器，还可以把接入链路带宽等参数作为权重，用加权后的发送速度标记数据包，提供有区别的服务。这种算法有三个缺陷：无法应对Bit-Torrent下载引发的公平性问题、在穿越不同管理域时需要重新标记会话速率、权重信息无法跨越管理域。由于BT下载流的多目的地址性，CSFQ会话流单源单目的地址的分类方法，无法控制BT业务的汇总传输量，从而BT业务会降低其它传统业务的服务质量，威胁互联网公平性和稳定性。由于不同管理域间无法建立完全的信任关系，需要对其数据流重新标记，这是该方法实施的主要性能瓶颈。由于权重信息无法可信地传递给其它管理域，在域间重新测量和标记会话速率时，权重信息必然丢失，这样权重功能仅在一个管理域内部有效，限制了该方法的灵活性。

发明内容

有鉴于此，本发明致力于提供一种基于令牌的互联网流量控制方法。

本发明的上述目的是通过如下的技术方案予以实现的：

一种基于令牌的互联网流量控制方法，包括：

a1)在数据包中增加令牌级标识，用户终端设备根据网络拥塞情况设置待发送数据包的令牌级，数据包消耗的令牌数量与数据包的令牌级成正比；

b1)网络接入路由器控制终端用户流入网络的令牌速度，当数据包到达接入路由器时，接入路由器判断其流量控制器中的令牌数量是否满足该数据包的需要，若令牌数量小于该数据包需要消耗的令牌数量，丢弃该数据包，否则，接收该数据包，并减少其流量控制器中的令牌数量；

c1)网络中间路由器在其输出接口上有一个物理拥塞控制器，物理拥塞控制器根据输出链路的带宽资源拥塞程度自适应地调整物理拥塞指数，当数据包到达网络中间路由器时，若数据包的令牌级大于该物理拥塞指数，接收该数据包，否则，根据当前物理拥塞指数和数据包的令牌级，计算得到该数据包的公平丢包概率，按照公平丢包概率随机丢弃该数据包，物理拥塞控制器在输出数据包时，若数据包的令牌级小于物理拥塞指数，设置数据包的令牌级标识为当前物理拥塞指数。

所述步骤c1之后进一步包括：

a2)域间互连路由器在其输出接口上有一个物理拥塞控制器，物理拥塞控制器实时测量输出链路的带宽资源拥塞程度，自适应地调整其物理拥塞指数，当数据包到达域间互连路由器时，若数据包的令牌级大于物理拥塞指数，接收该数据包，否则，根据当前物理拥塞指数和数据包的令牌级，计算得到该数据包的公平丢包概率，按照公平丢包概率随机丢弃该数据包，物理拥塞控制器在输出数据包时，若数据包的令牌级小于物理拥塞指数，设置数据包的令牌级标识为当前物理拥塞指数；

b2)域间互连路由器在其输出接口上还有一个虚拟拥塞控制器，虚拟拥塞控制器根据令牌资源的拥塞程度自适应地调整虚拟拥塞指数，并对所有经过虚拟拥塞控制器的数据包降低其令牌级，降低的级数等于虚拟拥塞指数；

c2)域间互连路由器在其输入接口上控制其它管理域流入的令牌速度，当数据包到达域间互连路由器的输入接口时，域间互连路由器判断其流量控制器中的令牌数量是否满足该数据包的需要，若令牌数量小于该数据包需要消耗的令牌数量，丢弃该数据包，否则，接收该数据包，并减少流量控制器中的令牌数量。

数据包消耗的令牌数量等于数据包的令牌级与数据包长度的乘积。

物理拥塞控制器实时测量其输出速度，由输出速度除以链路传输带宽就得到物理拥塞更新因子；物理拥塞指数采用乘性迭代的逼近方式，新的物理拥塞指数等于当前物理拥塞指数乘以物理拥塞更新因子。

虚拟拥塞控制器实时测量其令牌输出速度和数据包输出速度，由令牌输出速度减去令牌允许输出速度，再除以数据包输出速度就得到虚拟拥塞更新增量；虚拟拥塞指数采用加性迭代的逼近方式，新的虚拟拥塞指数等于当前虚拟拥塞指数加上虚拟拥塞更新增量。

物理拥塞控制器的公平丢包概率等于其当前物理拥塞指数减去数据包的令牌级，乘以1.1，除以当前物理拥塞指数。

在数据包中，除增加令牌级标识外，还增加了路径令牌级标识、已确认降低级标识、令牌降低级标识、反向令牌级标识、反向降低级标识和前期令牌级标识，其中路径令牌级标识用于收集传输路径的最高物理拥塞指数，已确认降低级标识用于存储虚拟拥塞控制器对令牌级的降低级数中已确认的部分，令牌降低级标识用于存储虚拟拥塞控制器对令牌级的降低级数中待确认的部分，反向令牌级标识用于向通信对端反馈其前向传输路径的最高物理拥塞指数，反向降低级标识用于向通信对端反馈其前向传输路径上的所有虚拟拥塞控制器对令牌级的降低级数中已确认的部分，前期令牌级标识用于存储发送方已知的前向传输路径的最高物理拥塞指数。

用户终端从通信对端返回数据包中提取反向令牌级和反向降低级，用反向令牌级和反向降低级之和，标识待发送数据包的令牌级。用户终端根据收到数据包中的路径令牌级、已确认降低级和反向令牌级的值，分别设置发送数据包的反向令牌级、反向降低级和前期令牌级；设置待发送数据包的路径令牌级为其取值范围内的最小值；设置待发送数据包的令牌降低级和已确认降低级为零。

物理拥塞控制器在输出数据包时，不但更新令牌级标识，还要更新路径令牌级、令牌降低级和已确认降低级标识，以便向终端设备传递网络拥塞信息；路径令牌级的更新方法是若物理拥塞指数大于路径令牌级，就更新路径令牌级为当前物理拥塞指数；令牌降低级的更新方法是将令牌降低级减少max(0，令牌降低级-max(0，前期令牌级-当前物理拥塞指数))；已确认降低级的更新方法是将已确认降低级增加max(0，令牌降低级-max(0，前期令牌级-当前物理拥塞指数))；虚拟拥塞控制器在输出数据包时，不但更新令牌级标识，还要增加令牌降低级标识，增加的数量等于虚拟拥塞指数。

本发明具有如下技术效果：

1、在本系统中，链路越拥塞，要求通过该链路的数据包令牌级也越高，消耗的令牌资源也越大，这样，对于接入令牌资源受限的情况，能够通过的流量就越小，这样就实现了网络流量的接入控制功能，能有效减少网络内部的丢包数量，降低了网络流量振荡。

2、在本系统中，对于一个接入令牌资源固定的会话流，其数据包的令牌级存在一个唯一的最优点，以该令牌级传输数据包能获得最高的网络传输速度，前面算法计算得到的令牌级就正好等于这个最优点。以UDP业务为例，在发送数据包时设置低于最优点的令牌级，虽然可以增大其数据包进入网络的速度，但其丢包率的增幅更大，反而会降低其吞吐量。这样的约束机制，有助于避免无效的数据传输。

3、在本系统中，在网络接入路由器和域间互连路由器，只需要在输入接口配置一个简单的令牌桶控制器就可以有效控制用户滥用网络资源的行为，而不需要监视每个会话流的行为特性，计算复杂度取得了很大降低。

4、在本系统中，在网络中间路由器和域间互连路由器，只需要控制输出接口的物理拥塞指数和虚拟拥塞指数，就可以实现流量控制和资源公平分配的功能，而不需要监视每个会话流的行为特性。

5、本系统具有BT业务公平性，在本系统中BT业务的使用者可以高效地利用网络的空闲带宽资源，但不会影响其他用户的服务质量。

6、在本系统中，固定的字节流量通过拥塞程度高的链路，会消耗更多的令牌资源。以令牌资源作为计费的依据，就可以实现基于网络拥塞程度的、灵活先进的计费模式。

附图说明

图1为本发明中令牌级扩展头的内部结构图；

图2为本发明在IPv6网络环境的设备连接图；

图3为本发明在IPv6网络环境的用户终端设备内部结构图；

图4为本发明在IPv6网络环境的用户出口路由器内部结构图；

图5为本发明在IPv6网络环境的网络接入路由器内部结构图；

图6为本发明在IPv6网络环境的网络中间路由器内部结构图；

图7为本发明在IPv6网络环境的域间互连路由器内部结构图；

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。

本发明在以IPv6网络环境为基础，来实现本流量控制系统。

协议扩展

为了满足流量控制的要求，需要扩展现有IPv6标准，在IP包头中增加一个令牌级扩展头，其值暂定为101，对应的关键字为TKLV。如图1所示，该扩展头的格式如下：

第一个八比特组为下一个包头的类型；

第二个八比特组为扩展头长度，指明令牌级扩展头的长度，以八比特组的数量来表示，并且不包括最开始的8个八比特组；其值为1；

第三个八比特组为令牌类型tktype，其值为1，表明当前版本为1，其它值保留；

第四个八比特组为数据长度tklen，其值为7，表明当前版本的有效信息字节的长度为7；

第五个八比特组为令牌级tklevel，取值范围暂定为[10，100]的整数，其它值保留，其值在经过网络中间路由器和域间互连路由器时，可被路由器升高或降低；

第六个八比特组为路径令牌级tkpath，取值范围为[10，100]的整数，其它值保留，其发送时的初始值为10，该值用于存储数据包传输路径中的最高物理拥塞指数；

第七个八比特组为令牌降低级tkdown，取值范围为[0，90]的整数，其它值保留，它是用于汇总数据包传输路径中虚拟拥塞控制器对令牌级还未确认的降低量；

第八个八比特组为已确认降低级tkdowned，取值范围为[0，90]的整数，其它值保留，它是用于汇总数据包传输路径中虚拟拥塞控制器对令牌级已确认的降低量；

第九个八比特组为前期令牌级tkprev，取值范围为[10，100]的整数，其它值保留，其值为上一次收集到的传输路径中最高物理拥塞指数，该值在传输过程中不变；

第十个八比特组为反向令牌级tkback，取值范围为[10，100]的整数，其它值保留，它存储的是从对端收到数据包中的路径令牌级字段，该值在传输过程中不变；

第十一个八比特组为反向降低级tkbackdown，取值范围为[0，90]的整数，其它值保留，它存储的是从对端收到数据包中的已确认降低级字段，该值在传输过程中不变。

第十二、十三、十四、十五和十六个八比特组为填充字节。

图2为IPv6网络环境的结构，流量控制实体分布在用户终端设备、用户出口路由器、网络接入路由器、网络中间路由器和域间互连路由器上。

用户终端设备

如图3所示，在用户终端的IP层增加了网络拥塞特性资料库，每个拥塞特性由四元组构成(host_tkpath，host_tkdowned，host_tkback，host_tkbackdown)，每个源地址和目的地址对存在一个唯一的拥塞特性与之对应。网络拥塞特性资料库具有从收到的数据包提取拥塞信息，对发送的数据包设置令牌级标识和拥塞信息的功能。当收到对端的数据包时，拥塞特性四元组的更新算法是host_tkpath元素设置为数据包中的路径令牌级，host_tkdowned元素设置为数据包中的已确认降低级，host_tkback元素设置为数据包中的反向令牌级，host_tkbackdown元素设置为数据包中的反向降低级，更新算法用等式表示如下：

host_tkpath＝tkpath；

host_tkdowned＝tkdowned；

host_tkback＝tkback；

host_tkbackdown＝tkbackdown；

当向通信对端发送数据包时，设置数据包中令牌级扩展头的算法是：令牌级设置为元素host_tkback与host_tkbackdown的和，前期令牌级设置为元素host_tkback，反向令牌级设置为元素host_tkpath，反向降低级设置为元素host_tkdowned，路径令牌级、令牌降低级和已确认降低级分别设置为10、0和0，该算法的等式表示如下：

tklevel＝host_tkback+host_tkbackdown；

tkpath＝10；

tkdown＝0；

tkdowned＝0；

tkprev＝host_tkback；

tkback＝host_tkpath；

tkbackdown＝host_tkdowned；

用户出口路由器

如图4所示，用户出口路由器的输出接口由基于启动势的延迟抖动受限公平队列SPJBQ(Start Potential-based Jitter Bounded Queueing)和令牌桶整形器构成。SPJBQ把从每个用户终端收到的数据包归为一个会话，公平分配用户出口的令牌资源。令牌桶整形器的工作过程是当整形器中的令牌资源足够发送下一个数据包时，它就从SPJBQ的输出队列中取出一个数据包，发送到传输链路上。该令牌桶整形器和网络接入路由器的令牌桶控制器配置相同的令牌桶深度和令牌到达速度，保证输出数据流消耗令牌的速度遵循与接入服务提供商签订的合约规范。

网络接入路由器

如图5所示，在网络接入路由器，基于令牌的令牌桶控制器根据用户合约规定来配置令牌桶深度D和令牌生成速率S。该令牌桶控制器的控制过程是这样的，当有数据包到达时，若令牌桶控制器中的令牌数量不足以满足该数据包的要求时，丢弃该数据包；否则，减少令牌桶控制器中的令牌数量，接收该数据包，放置到输出接口中。

网络中间路由器

网络中间路由器只与域内信任的路由器相连。如图6所示，在网络中间路由器，基于令牌的流量控制器由位于输出接口的物理拥塞控制器和后继的尾丢弃队列构成。物理拥塞控制器有一个重要的工作参数-物理拥塞指数α，其取值范围为[10，100]的整数。物理拥塞控制器有三个功能，自适应地调整物理拥塞指数α、按照公平丢包概率随机丢弃数据包、更新数据包的令牌级和其它拥塞标识。在网络中间路由器，设备输出端口的链路速率为C，采用指数平滑方法测量得到物理拥塞控制器的输出速度为ν，ν＞C的情况称为物理拥塞，ν＜C的情况称为物理空闲。输出速度ν与链路速率C的比值，反映了输出接口的带宽资源拥塞程度，该比值越大，输出接口的带宽资源拥塞程度越高。物理拥塞指数α的自适应算法是每经历一段持续时间的物理拥塞，物理拥塞指数α就增加，每经历一段持续时间的物理空闲，物理拥塞指数α就减少。物理拥塞指数α的更新值为物理拥塞指数α的当前值乘以输出速度ν，再除以链路速率C。在物理拥塞控制器，根据数据包的令牌级γ和当前出口的物理拥塞指数α按照公平丢包概率随机丢弃数据包，其算法是这样的。若令牌级γ大于或等于物理拥塞指数α，就接收该数据包；若令牌级γ小于物理拥塞指数α，则该数据包的公平丢包概率ρ为1.1*(α-γ)/α，物理拥塞控制器以公平丢包概率ρ随机丢弃该数据包，以概率1-ρ接收该数据包。物理拥塞控制器在输出数据包时，令牌级扩展头的更新算法是：若数据包的令牌级标识小于物理拥塞指数，则设置其令牌级标识为物理拥塞指数。若数据包的路径令牌级标识小于物理拥塞指数，则设置其路径令牌级标识为物理拥塞指数。数据包的令牌降低级标识减少max(0，tkdown-max(0，tkprev-α))，数据包的已确认降低级标识增加max(0，tkdown-max(0，tkprev-α))，用等式表示如下：

若tklevel＜α，则tklevel＝α；

若tkpath＜α，则tkpath＝α；

tkdowned+＝max(0，tkdown-max(0，tkprev-α))；

tkdown-＝max(0，tkdown-max(0，tkprev-α))；

域间互连路由器

域间互连路由器成对出现，如图7所示，每个域间接口由输出接口和输入接口两个功能实体构成的。在输入接口，令牌桶控制器根据相邻运营商达成的协议来配置令牌桶深度D和令牌生成速率S。该令牌桶控制器的控制过程是这样的，当有数据包到达时，若令牌桶控制器中的令牌数量不足以满足该数据包的要求时，丢弃该数据包；否则，减少令牌桶控制器中的令牌数量，接收该数据包。

在输出接口，基于令牌的流量控制器由物理拥塞控制器、虚拟拥塞控制器和令牌桶整形器顺序连接而成。其中物理拥塞控制器的工作过程与网络中间路由器相同。

虚拟拥塞控制器有一个重要的工作参数-虚拟拥塞指数κ，其取值范围为[0，90]的整数。虚拟拥塞控制器有两个功能，自适应地调整虚拟拥塞指数κ和降低输出数据包的令牌级。

域间互连互通合约所规定的域间令牌允许输出速度为K，虚拟拥塞控制器采用指数平滑方法测量得到其令牌输出速度μ和数据包的输出速度ν。μ＞K的情况称为虚拟拥塞，μ＜K的情况称为虚拟空闲。令牌输出速度μ与域间令牌允许输出速度K的比值，反映了域间输出接口的令牌资源拥塞程度，该比值越大，输出接口的令牌资源拥塞程度也越高。虚拟拥塞指数的自适应算法是每经历一段持续时间的虚拟拥塞，虚拟拥塞指数就增加，每经历一段持续时间的虚拟空闲，虚拟拥塞指数就减少。虚拟拥塞指数的更新算法是这样的：由令牌输出速度μ减去域间令牌允许输出速度K，除以数据包的输出速度ν，就得到虚拟拥塞更新增量δ。虚拟拥塞指数κ的更新值等于虚拟拥塞指数κ的当前值加上虚拟拥塞更新增量δ。

数据包经过虚拟拥塞控制器的更新算法是：对数据包的令牌级标识减少κ，令牌降低级标识增加κ。该算法的等式表述如下：

tklevel-＝κ；

tkdown+＝κ；

这样对于虚拟拥塞控制器，一个长度为L，令牌级标识为γ的输入数据包经过其后的令牌桶整形器时消耗的令牌数量为L*(γ-κ)。

令牌桶整形器的工作过程是当整形器中的令牌资源足够发送下一个数据包时，它就从虚拟拥塞控制器的输出队列中取出一个数据包，发送到传输链路上。

综上所述，本发明公开了一种基于令牌的互联网流量控制方法。上面描述的应用场景和实施例，并非用于限定本发明，任何本领域技术人员，在不脱离本发明的精神和范围内，可做各种的更动和润饰，因此本发明的保护范围视权利要求范围所界定。