一种基于时间粒度的互联网服务质量保证方法

摘要

本发明公开了一种基于时间粒度的互联网服务质量保证方法，其通过在实时业务数据包的包头中增加一个用于记录数据包状态信息的延迟控制扩展头，边缘路由器根据当前令牌数量设置实时业务数据包中的相对时限标识，核心路由器根据收到数据包的相对时限值，把数据包分配到不同粒度的延迟队列中，依次发送这些队列中的数据包；边缘路由器通过发送实时业务测试数据包的方法，测量网络的拥塞程度，从而作出是否接受新呼叫的决定。本发明既能较好地保障数据包的端到端延迟，又在核心路由器具有很低的计算复杂度，在提高服务质量的同时具有很强的扩展性。

说明书

技术领域

本发明涉及一种分组交换网络的服务质量保证方法，具体涉及一种基于时间粒度的互联网服务质量保证方法，属于数据通信领域。

背景技术

目前互联网开始提供视频电话、视频会议和IPTV等实时多媒体业务，这些业务要求较低的网络延迟，但互联网目前还缺乏一种行之有效的服务质量保证方案。互联网最早试图采用集成服务的方法为实时业务提供服务质量保证，它以资源预留协议(ResourceReSerVation Protocol，RSVP，参考：R.Braden，Resource ReSerVation Protocol(RSVP)，RFC 2205，September 1997)为作为呼叫信令，以加权公平队列(Weighted Fair Queuing，WFQ，参考：Abhay K.Patekh，“A Generalized Processor Sharing ApproachFlow Control in Integrated Services Networks：The Single-Node Case”，IEEE/ACM Trans.on Network，Vol 1，No.3，June 1993.)等队列调度算法作为数据平面的控制手段，为每个会话流提供不低于预约水平的服务质量。由于RSVP采用软状态的呼叫系统，需要定时更新和维护状态信息，使得其能保持的呼叫数量受到较大的限制。WFQ队列调度算法的计算复杂度为0(N)，其中N是当前呼叫数量。虽然平滑轮循(Smoothed Round Robin，SRR，参考：Chuanxiong Guo，SRR：An 0(1)Time ComplexityPacket Scheduler for Flows in Multi-Service Packet Networks，IEEE/ACMTransactions on Networking，Volume：12，Issue：6 On page(s)：1144-1155，Dec.2004)的计算复杂度为0(1)，但该方法仍需要对每个会话流过滤，并保存每个会话流的状态。为了克服集成服务的扩展性问题，目前大量采用区分服务的方法。区分服务的思路是建立一个区分服务的实施域，在该实施域的边界把数据流分为有限的几种类型，在区分服务的核心路由器上只需要根据数据包的类型为之提供相应的服务即可。这种方法不需要在区分服务的核心路由器上维护每个会话流的状态，因此处理效率较高，计算复杂度较低。区分服务虽然有一些基于带宽代理(Bandwidth Broker，BB，参考：K.Nichols，A Two-bitDifferentiated Services Architecture for the Internet，RFC2638，July 1999)的呼叫控制方法，但尚无标准化的呼叫控制协议。在数据平面上，区分服务虽然计算复杂度低，提供比尽力服务较好的服务质量，但仍无法为实时业务提供服务质量保证。全局最早时限优先(Global Earliest Deadline First，GEDF，参考：Matthew Andrews，LisaZhang，Minimizing End-to-End Delay in High-Speed Networks with a SimpleCoordinated Schedule，IEEE INFOCOM 1999)和核心抖动虚拟时钟(Core-Jitter VirtualClock，CJVC，参考：Ion Stoica，Hui Zhang，PProviding，Guaranteed Services WithoutPer Flow Management，ACM SIGCOMM 1999)等调度算法把每个数据包的延迟特性编码到数据包的包头中，核心路由器不再保留每个会话的状态信息，而是根据每个数据包的延迟特性，顺序发送，这类算法的计算复杂度为0(logN)，其中N是队列中的数据包数量。

发明内容

有鉴于此，本发明致力于提供一种基于时间粒度的互联网服务质量保证方法。

本方法采用区分服务的基本思路，把本域内的路由器分为边缘路由器和核心路由器，在边缘路由器为每个实时业务数据包贴上相对延迟标记，核心路由器根据收到实时业务数据包的相对延迟标记，控制该数据包的排队延迟，从而保障实时业务的端到端时延。

边缘路由器保存每个实时业务的会话信息，采用令牌控制器控制实时业务的流量，并根据当前剩余令牌数量设置实时业务数据包中的相对时限标识，两者的关系是当前剩余令牌数量越多，相对时限的值就越小。路由器收到数据包的相对时限值为正，表示该数据包提前到达该路由器，反之，则表示该数据包延迟到达了。数据包的相对时限值越大，在其后的转发过程中，可以忍受的排队延迟也越大。数据包经过一个路由器后，其相对时限会发生改变。数据包从核心路由器输出时，相对时限需要减去其排队时延，再加上转发延迟常量。

核心路由器以比转发延迟常量更小的时长作为基本延迟单位，以基本延迟单位或其整数倍作为等待队列的时限跨度，根据进入核心路由器的数据包的相对时限，可以计算得到该数据包的路由时限；核心路由器根据数据包的路由时限分派数据包，将其插入到相应队列的队尾。发送时，路由时限低的队列优先发送，在每个队列内部，按照数据包到达路由器的先后顺序发送。在核心路由器建立的等待队列分为两种不同的时间粒度，N个细粒度的队列以基本延迟单位作为其时限跨度，M个粗粒度的队列以N倍基本延迟单位作为其时限跨度。N个细粒度的队列接收相对时限从0到N个基本延迟单位的数据包，其中队列R(n)用于接收路由时限属于[(n-1)×u，n×u)的数据包；M个时间粗粒度的数据包等待队列T(m)，用于接收路由时限大于U的普通实时业务数据包，其中队列T(m)用于接收路由时限属于[m×U，(m+1)×U)的数据包。当核心路由器进入拥塞状态，就丢弃后继的测试数据包，直到拥塞状态解除。每经过n倍基本延迟单位的时长，就把第一个粗粒度队列中的数据包分配到细粒度队列中，其余的粗粒度队列依次向前晋升。

在呼叫控制方面，在每个路由器的输出接口，分配一定的带宽预留给实时业务，并为该部分业务提供较高的调度优先级。在发送实时业务数据前，发送端的边缘路由器向接收端的边缘路由器发送实时业务测试数据包；接收端的边缘路由器检查收到实时业务数据包时，若发现了实时业务测试失败数据包，就拒绝该呼叫；否则，建立该实时业务。

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

一种基于时间粒度的互联网服务质量保证方法，包括：

1)在实时业务数据包的包头中增加一个用于记录数据包状态信息的延迟控制扩展头；

2)边缘路由器转发收到的普通实时业务数据包，并设置该数据包的相对时限；

3)核心路由器根据普通实时业务数据包的相对时限，计算得到该数据包的路由时限；

4)核心路由器根据每个普通实时业务数据包的路由时限建立数据包等待队列；

5)核心路由器发送普通实时业务数据包并更新该数据包的相对时限。

所述延迟控制扩展头的数据结构为：下一个包头的类型、扩展头的长度、扩展头的版本、测试标志、业务等级、相对时限。

所述的方法中边缘路由器转发收到的普通实时业务数据包并设置每个数据包的相对时限的方法为：

1)边缘路由器为每个实时业务分配一个令牌控制器，配置其最大令牌深度Δ和令牌到达速度α，所述最大令牌深度大于最大数据包的长度；

2)长度为L的普通实时业务数据包到达边缘路由器时，如果当前剩余令牌数量δ大于L时，则发送该数据包，设置其相对时限为β＝(Δ-δ)/α，并且将当前剩余令牌数量减少L；否则等待当前剩余令牌数量δ大于L后，再发送该数据包。

所述的方法中核心路由器根据每个普通实时业务数据包的路由时限r建立数据包等待队列的方法为：

1)在核心路由器中设置两种时间粒度，细粒度为基本延迟单位u，粗粒度U的长度为N个细粒度，即U＝N×u；

2)将忙期分为K个更新时段，每段的时间长度为U，记录每个时段的起点时刻B(k)；

3)计算在第k个更新时段内到达的普通实时业务数据包的路由时限r，r＝t-B(k)+β+σ，其中t为当前时刻，β为该数据包进入该核心路由器时的相对时限，σ为转发延迟常量；

4)在核心路由器中建立N个时间细粒度的数据包等待队列R(n)，用于接收路由时限属于[0，N×u)的普通实时业务数据包，其中队列R(n)用于接收路由时限属于[(n-1)×u，n×u)的数据包；所述时间细粒度的数据包等待队列的路由时限跨度为基本延迟单位u；

5)在核心路由器中建立M个时间粗粒度的数据包等待队列T(m)，用于接收路由时限属于[U，(M+1)×U)的普通实时业务数据包，其中队列T(m)用于接收路由时限属于[m×U，(m+1)×U)的数据包，所述时间粗粒度的数据包等待队列的相对时限跨度为U；

6)建立首队列F和尾队列Z，首队列F用于接收路由时限小于零的数据包，尾队列Z用于接收路由时限大于(M+1)×U的数据包；

7)发送队列的建立顺序依次为队列F、N个时间细粒度的数据包等待队列R(n)、M个时间粗粒度的数据包等待队列T(m)、尾队列Z。

所述基本延迟单位u小于所述转发延迟常量σ。

所述的方法中核心路由器发送普通实时业务数据包的方法为：

1)依次发送队列F、N个时间细粒度的数据包等待队列R(n)、M个时间粗粒度的数据包等待队列T(m)、尾队列Z中的数据包；发送完毕后恢复状态变量初始值；

2)更新时刻B(k)到达时，对于时间细粒度队列R(n)中未发送的数据包依照发送顺序依次加入到队列F的尾部；

3)更新时刻B(k)到达时，还需将第一个粗粒度队列T(1)中的数据包分配到细粒度队列中，其余的粗粒度队列依次向前晋升，并把队列Z中符合条件的数据包加入到队列T(M)。

所述的方法中核心路由器更新普通实时业务数据包相对时限的方法为：

1)核心路由器记录数据包到达时间t_arv，和数据包的发送时间t_snd；

2)核心路由器发送该数据包时更新其相对时限为β+σ-(t_snd-t_arv)，其中β为该数据包进入该核心路由器时的相对时限。

所述实时业务数据包包括普通实时业务数据包、实时业务测试数据包和实时业务测试失败数据包；在非拥塞状态，实时业务测试数据包与普通实时业务数据包在核心路由器中的处理过程是相同的，但在拥塞状态下，核心路由器把实时业务测试数据包变更为实时业务测试失败数据包，并放置到尽力服务队列的尾部；核心路由器通过尽力服务队列来转发实时业务测试失败数据包。

所述实时业务的建立方法为：

1)在每个路由器的输出接口，分配一定的带宽预留给实时业务，并为该部分业务设定发送优先级；

2)在发送实时业务数据前，发送端的边缘路由器向接收端的边缘路由器发送实时业务测试数据包；

3)接收端的边缘路由器检查收到的实时业务数据包时，若发现了实时业务测试失败数据包，就拒绝该呼叫；否则，建立该实时业务。

所述实时业务的路由建立方法为：在路由器的路由表中添加一个新建标志字段，当路由器的路由项发生变化时，路由器设置该路由项的新建标志有效，等待新建标志有效时长τ后，路由器就更新该路由项的新建标志为无效；路由器输出普通实时业务数据包时，若对应的路由项的新建标志为有效，则路由器设置该数据包为实时业务测试数据包。

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

1、在本发明提出的队列调度算法在核心路由器的计算复杂度低。在核心路由器中，根据数据包的相对时限值进行分组为若干个有限的队列，在这些队列间，顺序发送，计算复杂度仅为0(1)。

2、在本发明提出的队列调度算法在边缘路由器的计算复杂度也较低，只需根据令牌控制器中的令牌深度设置标记相对时限即可。该方法较核心抖动虚拟时钟方法简单，不需要边缘路由器计算每条路径的松弛变量。

3、本发明提出的队列调度算法可以控制每个数据包在路由器的排队延迟，从而保证端到端的传输延迟。

4、本发明提出的队列调度算法比简单的FIFO队列调度算法带宽利用效率更高，可以在同样的网络环境下为实时业务提供更大的保证带宽。

5、本发明提出的基于测量的接入控制技术，可以保证粗粒度的队列调度的端到端时延。

6、本发明提出的基于测量的接入控制技术，不需要在核心路由器上维护每个会话的状态信息，具有较强的可扩展性。

7、本发明在网络路由发生变化时，可以较好地保护实时业务的服务质量；当网络资源充足时，可以为传输路径变化的实时业务提供很好的服务质量；当网络资源不足时，可以自动中止传输路径变化的实时业务，从而保证其它实时业务的服务质量。

附图说明

图1为本发明中数据包的延迟控制扩展头的内部结构图；

图2为本发明的网络设备连接关系图；

图3为本发明的边缘设备内部结构图；

图4为本发明的核心设备内部队列调度结构图；

图5为本发明的呼叫控制过程图；

图6为本发明的方法流程图。

具体实施方式

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

本发明的方法流程图如图6所示，本实施例是在以IPv6网络环境为基础，来实现本服务质量保证系统。

协议扩展

为了满足服务质量保证的要求，需要扩展现有IPv6标准，在IP包头中增加一个延迟控制扩展头，其值暂定为102，对应的关键字为DLCT。边缘路由器收到用户的实时业务数据包后，在数据包头中增加延迟控制扩展头；当实时业务数据包到达通信对端的边缘路由器后，边缘路由器删除延迟控制扩展头，再转发给通信对端的用户。如图1所示，该扩展头的格式如下：

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

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

第三个八比特组为扩展头的版本(Message Version)，其值为1，表明当前版本为1，其它值保留；

第四个八比特组的前四个比特是测试标志，0B1000为实时业务测试数据包，0B1100为实时业务测试失败数据包，0B0000为普通实时业务数据包；后四个比特是业务等级(Service Level)，其值为正整数，表明实时业务的等级；

第五、六、七和八个八比特组为相对时限(Relative Deadline)，取值范围为整数，单位为100微秒。

图2为IPv6网络环境的结构，服务质量保证系统分布在边缘路由器和核心路由器上。本系统限定每个核心路由器的基本延迟单位u为800微秒，转发延迟常量σ为3毫秒，限定端到端的转发跳数小于16，这样端到端的排队延迟就保证在48毫秒内。

队列调度

本专利提出的服务质量保证方法采用区分服务的思路，把区域内的路由器分为边缘路由器和核心路由器，边缘路由器保存每个数据流的状态信息，并把相对时限信息编码到数据包的延迟控制扩展头中，核心路由器无需维护每个会话的状态信息，只需要根据数据包头中的相对时限信息处理数据包即可。

该方法不考虑线路传输延迟和数据传输路径的跳数，这些问题都由网络规划和终端系统负责。本方法通过限定实时业务数据包在核心路由器中的排队延迟，使之小于转发延迟常量σ，来保证数据包的端到端传输延迟。

由于网络负载的变化，数据包可能提前或延后到达下一跳路由器，本文把这个时间差值β称为相对时限。相对时限为正，表示提前到达；相对时限为负，表示延迟到达。对于提前到达的数据包，其在队列中等待的时间可以大于转发延迟常量，但应当小于转发延迟常量与相对时限之和。核心路由器通过让提前到达的数据包在队列中等待更长的时间，让其它相对时限更小的数据包先发送，从而提高网络系统的整体延迟性能。

在边缘路由器为每个实时业务分配一个令牌控制器，如图3所示，配置其最大令牌深度Δ，令牌到达速度α，其中最大令牌深度Δ必须大于最大数据包的长度。

当长度为L的普通实时业务数据包到达边缘路由器时，若令牌控制器的当前剩余令牌数量δ大于当前数据包的长度L就发送该数据包，标识该数据包的相对时限β为(Δ-δ)/α，并把当前剩余令牌数量减少L。否则，等待令牌控制器的当前剩余令牌数量大于数据包长度后，再发送该数据包，标识该数据包的相对时限β为(Δ-δ)/α，并把当前剩余令牌数量减少L。

当数据包到达核心路由器时，核心路由器记录该数据包的达到时间t_arv，和数据包的发送时间t_snd，并在发送时更新该数据包的相对时限为β+σ-(t_snd-t_arv)，其中β为该数据包进入该核心路由器时的相对时限；

如图4所示，在核心路由器的输出接口，建立34个队列，分别为F、R(1)、R(2)、...、R(16)、T(1)、T(2)、...、T(16)、Z。指针PR取值为1、2、...、16时，指示的当前发送队列分别为R(1)、R(2)、...、R(16)，取值为0，表示该指针无效，指针PR的初始值为0。指针PT取值为1、2、...、16时，指示的当前发送队列分别为T(1)、T(2)、...、T(16)，取值为0，表示该指针无效，指针PT的初始值为0。

初始化时，核心路由器输出接口上的34个队列全部为空，其忙期开始的时间为0，忙期结束的时间为E，将该忙期分为长度为U(12.8毫秒)的K个更新时段，K个时段的起点时刻为0、B(1)、B(2)、...、B(K-1)。

当普通实时业务数据包p在路由器的第k个更新时段内到达，该数据包的路由器时限r为当前时刻t减去第k个更新时段的开始时刻B(k)，加上该数据包进入核心路由器时的相对时限，再加上转发延迟常量σ。

若该路由器时限r小于零，则该数据包放入队列F中，

若该路由器时限r小于n×800微秒，大于等于(n-1)×800微秒，则该数据包放入队列R(n)中；若当前指针PR为零，则更新指针PR为n；若当前指针PR取值不为零，并且n小于指针PR，则PR的值更改为n；

若该路由器时限r小于(m+1)×12800微秒，大于等于m×12800微秒，则该数据包放入队列T(m)中；若当前指针PT为零，则更新指针PT为m；若当前指针PT取值不为零，并且m小于指针PT，则PT的值更改为m；

否则，则该数据包放入队列Z中；

在发送时，接口从这34个队列中选择数据包来发送，其选择方法是这样的。

若队列F不空，则发送队列F的队头数据包；

若队列F为空且指针PR不等于零，就检查队列R(PR)是否为空。若队列R(PR)不空，则发送队列R(PR)的队头数据包；否则，指针PR加一，再次测试R(PR)是否为空；若直到R(16)都为空，则置指针PR为零；

当队列F为空，指针PR为零且指针PT不等于零时，就检查队列T(PT)。若队列T(PT)不空时，就发送队列T(PT)的数据包；若队列T(PT)为空时，指针PT加一，再检查队列T(PT)是否为空。若直到T(16)都为空，则置指针PT为零；

当队列F为空，指针PR为零且指针PT也为零时，就检查队列Z是否为空。若队列Z不为空则发送队列Z的队头数据包；否则，路由器就结束了这个忙期，PT和PR都变为初始值零。

在更新时刻B(k)到达时，若队列R(1)、R(2)、...、R(16)中仍有数据包未能发送，就把这些数据包依照发送顺序依次加入到队列F的尾部。然后把队列T(1)中的数据包按照其路由器时限，分配到16个时间细粒度队列R(1)、R(2)、...、R(16)中。并将队列T(2)、T(3)、...、T(16)更新为队列T(1)、T(2)、...、T(15)，最后把队列Z中的属于T(16)的部分数据包移动到队列T(16)中，并把PT和PR都变为初始值零。

在发送过程，队列R(1)、R(2)、...、R(16)的限定时刻D(1)、D(2)、...、D(16)分别为800、1600、...、12800微秒，若D(i)时刻到达了，但R(1)、R(2)、...、R(i)这i个队列中还有未发送完的数据包，则核心路由器进入拥塞状态。核心路由器进入拥塞状态后，当D(j)时刻到达了，队列R(1)、R(2)、...、R(j)这j个队列均无等待发送的数据包，则核心路由器进入非拥塞状态。在拥塞状态下，核心路由器把实时业务测试数据包包头中的测试标志更改为0B1100，从而把该数据包变更为实时业务测试失败数据包，并放置到尽力服务队列的尾部；核心路由器通过尽力服务队列来转发实时业务测试失败数据包。在非拥塞状态，核心路由器采用与普通实时业务数据包相同的处理方法，处理实时业务测试数据包。核心路由器采用与尽力服务的方法处理实时业务测试失败数据包。

呼叫控制

在每个路由器的输出接口，分配一定的带宽预留给实时业务，并为该部分业务提供较高的调度优先级。本方法采用RSVP协议作为终端和边缘路由器之间的呼叫信令。如图5所示，在发送实时业务数据前，发送方先发送Path消息到边缘路由器，并在边缘路由器建立相关的状态信息。发送端的边缘路由器再转发Path消息到接收端的边缘路由器，并在其后1秒种时间内，根据Path要求的资源特性向接收端的边缘路由器发送顺序编号的实时业务测试数据包。

接收端的边缘路由器检查收到的实时业务数据包，若发现了实时业务测试失败数据包就拒绝这个呼叫，否则，转发Path消息到接收端。接收端的边缘路由器收到终端返回的Resv消息，再转发给发送端的边缘路由器，并转发给发送端。发送端最后发出确认消息ResvConf给接收端，这样呼叫就建立了。

待会话结束后，终端发送PathTear或ResvTear，释放在边缘路由器预留的资源。

路由变更

在路由器的路由项中增加新建标志字段，当增加或更改路由项时，设置该路由项的新建标志为有效，并启动新建标志有效定时器，新建标志有效定时器的长度为1秒种，新建标志有效定时器超时后，设置新建标志为无效。路由器输出普通实时业务数据包时，若对应的路由项的新建标志为有效，则路由器设置该数据包为实时业务测试数据包。在实时业务的正常运行过程中，若收到实时业务测试失败数据包，就中止本次实时通信业务。