基于排队论的VoIP低延时排队算法分析

杨俊叶 王训伟

（1.石家庄理工职业学院 互联网应用学院，河北 石家庄 050091;2.石家庄智库科技有限公司，河北 石家庄 050091）

引言

排队论是研究计算机网络通信的重要工具，它能有效地对通信系统进行描述和建模，特别是针对其中的通信队列。在VoIP网络中，目前主流排队算法包括FIFO(First In FIRST Out Queueing algorithm,先入先出排队算法)、PQ (Priority Queueing algorithm,优先级排队算法)、CQ(Custom Queueing algorithm,定制排队算法)、WFQ(Weighted Fair Queueing algorithm,加权公平排队算法)、CBWFQ(Class-Based WFQ Queueing algorithm,基于类的加权公平排队算法)、LLQ(Low Latency Queueing algorithm,低延时排队算法)等[1]。其中，LLQ在CBWFQ基础上增加了优先级队列，从而可以提供绝对的优先权，同时还能保证实时业务的低延时要求。VoIP是一种实时性业务，对通信延时的要求比较高。因此可以将LLQ算法应用于VoIP网络，通过LLQ优化排队算法，来保证其数据传输的服务质量。本文详细分析了在VoIP中的低延时排队算法。

一、排队论理论简介

排队论又叫做随机服务系统理论，主要解决与随机到来、排队服务现象有关的应用问题，在计算机网络等领域有着广泛的应用。排队论主要研究三个方面的内容：(1)形态问题, 即研究各种排队系统的规律性,这包括队长分布、等待时间分布、忙闲期分布等, 同时又分稳态和瞬态两种情形。(2)最优化问题, 又分静态最优和稳态最优; 前者指最优设计, 后者指现在排队系统的最优运用。(3)排队系统的统计推断, 即判断一个给定的排队系统符合哪种类型,以便根据排队理论进行分析研究[2]。

一般的排队系统都具有三个要素，这就是输入过程、排队规则和服务机构。常见的排队模型包括M/M/S、M/M/S/K、M/G/1等。计算机网络通信过程与排队系统具有相互对应的关系，网络中的信道数相当于排队论中的窗口数、单位时间内的平均呼叫数相当于顾客的到达率λ、每次呼叫占用线路的平均时间相当于平均服务时间[3]，通信过程也可以利用排队过程来表示。这样就可以利用排队论理论对不同的网络通信进行建模和分析。

二、VoIP网络模型的建立与分析

（一）VoIP网络

VoIP（Voice-over-IP）是一种可以在IP网络上互传音讯或视讯的一种通信技术。简单地说，就是通过语音压缩算法对语音信号进行压缩编码处理，然后把这些语音数据按TCP/IP标准进行打包，经过网络把数据包发送到接收端；接收端把这些语音数据包串起来，经过解码，解压缩处理将其恢复成原来的语音信号，从而达到由Internet传送语音的目的[4]。IP电话系统的基本组成如图1所示。

图1 VoIP电话系统基本组成

IP电话系统有4个基本组件：终端设备，网关、多点控制单元和网守。

1.终端设备是一个IP客户终端，可以直接连接在IP网上进行实时的语音或多媒体通信。

2.网关是通过IP网络提供语音通信的关键设备，完成实时语音压缩，完成寻址和呼叫控制。

3.网守负责用户注册和管理。

4.MCU(多点控制单元)的功能在于利用IP网络实现多点通信，使得IP电话能够支持诸如网络会议的多点通信[4]。

VoIP网络通信的发送、接收、处理过程具有如图2所示的模式。发送方将IP语音数据进行编码，并按照相关协议打包封装，由发送单元将数据包送入IP分组网络通道中。相应地，接收单元将接收到的数据包放在缓冲区中，经过解码和转换后进入处理单元进行处理，最后到达接收方。

图2 VoIP网络通信一般模式

（二） VoIP网络模型

在网络传输的过程中，假定没有数据包丢失，只考虑网络传输延时TN,发送方以一个输出速率为λo的队列加以抽象，那么接收方就是一个典型的M/M/1的排队系统[5]。两个M分别代表发送方的输出过程和接收方的处理过程为马尔可夫过程，服从泊松分布，1代表一条信道。图2所示的VoIP通信过程可抽象为图3所示的模型：λO 为发送方的数据包输出速率，λI 为数据包到达接收模块的速率，LQ 为缓冲区的数据包个数，γ为接收模块的数据丢失率,TJ为解码时间，TD为调度时间,TC为处理时间,TS为数据包在队列中的服务时间，且TS=TJ+TD+TC 。

图3 VoIP通信系统抽象模型

（三）抽象模型分析

VoIP通信系统模型中，主要参数的含义为：① LQ，它确定在保证丢失率可接受的数值范围内，应为系统分配的缓冲区大小；②λI，在确定保持多大的输入速率下，有确定缓冲区大小的系统能够在一定的时间范围内，处理完数据，不产生丢失；③TS，系统处理时间越短越好。设处理模块（服务台）的使用率为ρ，图2中所示的各个变量均为随机变量，发送方和接收方的输出队列和输入队列均可假定为泊松分布。用L表示在系统平衡状态下的队长，根据概率论和排队论可以得出如下关系式[6]：

需要指出的是L在此的含义是进入处理模块和存储在缓冲区中的所有数据包的平均数量，因此还可以得出如下关系式：

如果把VoIP通信过程处理模块看做是一个闭合区域，根据Little定律[3]，得到

由图2可知：

通过整理可以得到以下式子：

由此可以看出，⑷式是一个关于λo 、TS 、LQ的三元方程，只要在服务时间、发送速率和缓冲区大小三者中有两项

为已知条件的情况下，都可以求得第三者的值。这样就得出了在VoIP通信网络中，服务时间、发送速率、接收缓冲区的大小之间的数学关系。

三、低延时排队算法分析

（一） VoIP的队列调度

IP电话是对实时性要求很高的数据传送。延时会影响VoIP通话中的语音质量，因此提供高品质的语音应该从减少延时这方面入手。在VoIP电话系统中，通过相应地QOS策略对IP数据包进行合理的排队，对其中特定的数据包赋以较高的优先级，从而加速传输的进程，并实现实时交互[1]。

排队机制作为IP网络QoS 的实现机制之一，无论是在综合业务体系（IntServ）还是在区分业务体系（DiffServ）里，都有着重要的作用。路由器中排队算法所要完成的功能就是如何从多个（或一个）队列中选择下一个待转发的分组，其结构如图4所示。

图 4 路由器中的队列管理

VoIP网络中所要调度的分组数据包大体上可以分为两类：一是具有优先级，二是不具有优先级[7]。

VoIP网络中路由器中的队列调度分为以下几种方式：

1.当拥有绝对优先级队列中有IP数据包分组时，调度器会优先发送此队列，直到此队列中没有任务了，才对其他队列进行调度。若该优先级队列本来为空，但在调度其他队列时，不具备绝对优先级的分组却进入了此优先级队列，那么就应该在当前调度的分组出队时立刻转去调度进入优先队列里的分组。

2.如果在网络设备接口没有发生拥塞，属于优先队列的分组获得空闲的带宽，此队列中的分组就都可以被发送。

3.如果在其接口发生拥塞，优先级队列中的分组就会被限制传输速度，超出规定流量的那部分分组也将被丢弃，这样就保证了属于优先队列的分组不会占用超出规定的带宽，同时也保护了其他分组的应得带宽。只要优先队列中有分组，调度器就会发送此优先队列中的分组。

（二）LLQ算法分析

LLQ是一种集合了PQ、CQ、WFQ算法优点、能有效地应对延时要求颇高的实时性业务的算法。此算法最重要的一点就是增加了一个优先级队列，在IP数据包传送的过程中拥有绝对的优先权。

根据VoIP通信系统模型和路由器中的队列调度，我们可以知道VoIP网络中低延时排队的通信队列是一个M/M/1排队模型，所以低延时排队的通信队列模型也应该满足第2节中列出的几个式子。

在⑶式中，λI是一个定值时，TS随着ρ值的变化而发生相应地变化。当TS取得最大值时，即系统处理数据的时间取最大值，也就是说队列等待的时间取最大值，相应地服务台的使用率取最大值(传输的数据包平均数取最大值)。在⑵式中，LQ随着ρ值的变化而发生相应地变化。当ρ取得最大值时，相应地缓冲区的长度取得最大值，即是通信队列的队长取得最大值。

当本来为空的优先级队列中有数据分组进入时，调度器会在当前调度的分组出队时立刻转去调度进入优先级队列里的数据分组，也就是说优先级队列队头分组接受调度的最大延时为一个最大分组的发送时间。那么当数据分组个数是一个定值时，数据分组长度越大，优先级队列队头等待调度的延时会越长。

当⑵式中的LQ 取最大值时，⑶式中的ρ随之取得相应地最大值，这就使得系统处理数据的时间TS取得最大值，因此就得到了优先级队列队头等待调度的最大延时。

如果在数据平均到达率一定的情况下，减小了数据分组的长度，也就是说上式中LQ的值减小，就会降低优先级队列队头等待调度的延时。

对于VoIP通信网络来说，对延时的要求比较高，低延时排队算法在实时业务上能比较理想地实现低延时处理效果，所以在VoIP通信队列选择低延时排队算法。但低延时排队算法并不能够完全代替FIFO，PQ 或者CQ，我们应该根据网络中不同的QoS要求，进行合理的选择，因为任何一种排队算法都不是尽善尽美的。

四、总结

将排队论理论用于分析VoIP网络系统的通信处理过程，具有很大的优越性。这一方面可以将研究对象(发送、接收和处理过程)抽象化，便于利用精确的数学语言来描述，另一方面也可以抛弃次要因素，一定程度上简化了研究对象，使得建模和分析成为可能。如今的网络，需要我们积极探索开发新的、具有实质性飞跃的排队算法。新算法可以从严格的、多层的分类或组合，以及算法复杂度低等方面入手，尽可能让数据分组里的附加信息减少，从而降低网络总体负荷。而排队论则是对这些算法分析的重要手段和方法。相信通过这一系列的改进能够使网络上的各种应用，尤其是实时业务的应用得到长足的发展。