基于网络演算的网络性能分析研究

王 帅，陈彦德，朱 磊

(解放军理工大学 通信工程学院，江苏 南京 210007)

引言

被称为第三次工业革命的信息技术产业发展至今，网络已在人们日常生活中变得不可或缺。各式各样的新兴业务使网络从数据型通信网络向能够传送语音、图像、视频、动画的多媒体综合网络发展。新兴的多媒体业务和实时业务的业务流复杂度与突发性与以前相比有了很大变化，对网络服务质量(即QoS，Quality of Service)也有了更高的要求。QoS是一种可控的系统行为，是服务性能综合效果的体现［1］，可以由服务可行性、适应性、活性等多种描述来表示，具体到网络性能定量分析上，主要指带宽(吞吐量)、时延、时延抖动、数据积压等。对QoS有需求的业务往往对一项或多项指标要求较高，如音频和视频业务等会话类业务要求时延和时延抖动尽量小以防止失真，而流媒体点播业务则更看重控制丢包率的大小［2］。

对网络性能进行定量分析以求得各项QoS指标是网络选择、接纳控制、资源预留、垂直切换等网络研究的基础，这一课题涉及网络服务模型、网络业务流模型、节点服务策略以及网络性能分析方法等。传统网络性能分析主要基于排队论、统计学、随机过程和图论，结合尽力服务(best effort)模型求解网络稳定状态下的性能指标，在刻画和分析复杂业务流的实时网络性能上比较欠缺。伴随着IntServ［3］(Integrate Service)、DiffServ(Differentiated Service)等QoS服务模型和自相似业务流模型的提出，网络演算［4］因为能够直观、准确、实时地描述业务流端到端性能而获得了广泛地关注。

本文就基于网络演算的网络性能分析研究这一课题，对如何应用网络演算分析网络端到端性能进行论述。介绍了网络演算的理论知识和网络性能分析中到达曲线和服务曲线的求解，如何求解各项网络性能指标并进行了总结和展望。

1 网络演算介绍

1.1 网络演算概述

网络演算是近十年来新兴的对网络排队系统性能定量分析的数学工具。它是一套基于最小加代数的数学演算理论。网络演算以广义增函数为运算对象，以节点为研究目标，通过分析流经节点的端到端业务流，推算整个网络的服务性能。网络演算最早由 R.L.Cruz［5］提出，他所定义的(σ，ρ)流量模型发展形成了到达曲线。服务曲线则由Cruz和Sariowan［6］在GPS模型的基础上提出，服务曲线能够看作是对服务策略和调度策略的一种抽象描述。另外C.S.Chang［7］、J.Y.Le Boundec、Gallager等人也做出了大量基础研究工作，提出并总结出基于到达曲线和服务曲线的网络分析方法，最终形成了网络演算理论体系。网络演算又分为确定网络演算(Deterministic Netwrok Calculus)和随机网络演算(Statistical Network Calculus)。确定网络演算研究已比较成熟，用于分析端到端业务流最坏情况下的网络性能。随机网络演算在最近几年内发展迅速，主要是将概率论的相关知识引入最小加代数体系，将网络演算的适用范围从确定性问题扩展到随机性问题上。

1.2 网络演算理论基础

定义一广义增函数集合

若f(x)连续且一阶可导，则定义广义增函数集合为:

最小加卷积满足结合律和交换律，且当f(0)=g(0)且均为凹函数时，f⊗g≤min{f，g}。

定义三最小加反卷积(Min-plus Deconvolution)

φ与最小加卷积类似，∀f，g∈F，f与g的最小加反卷积为:

定义四到达曲线(Arrival Curve)

假设一端到端业务流流经网络节点，到达曲线可以看作是对流入节点业务流的限制，即流量包络［8］。给定广义递增函数α(t)，定义域t≥0，假设数据流流经某节点且其到达累积函数为I(t)，则对∀s≤t，当满足:

称α(t)为I(t)的到达曲线，或称I(t)受限于到达曲线α(t)。

定义五服务曲线(Service Curve)

服务曲线描述了节点的服务能力，确切地说是节点为满足业务QoS需求所需要提供的服务下限。给定广义递增函数β(t)，定义域t≥0。假设流入流出节点的业务流的累积函数分别为I(t)和O(t)，对∀t≥0，∃t≥0 ≤ t，t0≥0，满足:

则称β(t)为节点提供的服务曲线，或称节点提供给业务流的服务能力受限于服务曲线β(t)。

定义六网络服务曲线(Service Curve)

节点以串联方式依次流过N个网络节点，假设每个节点提供的服务曲线为βn(n=1，2，…N)。则这N个节点串联形成的端到端网络服务曲线为:

网络演算是基于单个节点的网络性能分析理论，通过网络服务曲线可以把N个节点的串联系统等效成一个大型节点进行分析，克服了传统网络性能分析方法对网络拓扑依赖性强、无法很好地对如战场通信网络这样拓扑结构变化起伏较大的网络进行分析的缺点。

定义七有效到达曲线

则称αε为到达流量I(t)的有效到达曲线［8］，当ε=0时有效到达曲线退化成定义四中的到达曲线α(t)。

定义八有效服务曲线

则称βε为到达流量I(t)的有效服务曲线［8］，可以理解为节点以(1－ε)的概率为业务流提供服务曲线βε，当ε=0时有效服务曲线退化成定义五中的服务曲线β(t)。

2 到达曲线与服务曲线的求解

2.1 业务流建模与到达曲线的求解

提取业务流的流量特征，构建业务流模型，进而获得到达曲线是进行网络演算的前提。在传统的网络性能分析中，通常用排队论和随机过程刻画业务流模型，如泊松模型、开关模型和Markov模型［9］。而在新兴业务中，业务流的复杂性和突发性大大增加。随着业务流建模研究的不断发展，在不同类型网络和QoS保障体系中，对业务流模型的分类也不尽相同。在实际应用网络演算解决具体问题时，需根据应用场景的特征对相应业务流建模获得到达曲线。如从宏观角度可根据业务流的自相似和多分形特征将业务流模型分为短程相关模型、长程相关模型和自相似模型［10］。而在无线蜂窝网络中业务流可分为受约束流、无记忆开关流、分形布朗运动流三类。本节以确定网络演算和随机网络演算中应用最为广泛几种流量模型为例［11-12］，对到达曲线进行综述。

2.1.1 漏桶模型

漏桶算法(Leaky Bucker Algorithm)是一种典型的QoS业务流规整算法，主要用于描述数据型流量。

根据到达曲线可以看出，数据源能够一次发送数据量为b(bit)的数据，但在较长时间内速率不会超过γ(bit/s)。

2.1.2 通用信元速率模型

通用信元速率算法(Generic Cell Rate Algorithm)主要应用于描述ATM网络当中的业务流。

它的到达曲线由一个阶梯函数刻画:

通用信元速率模型描述的是发送分组大小恒为k个数据单元的业务流，分组间时间间隔为T'个时间单元，修正参数 表示实际时间间隔与理想时间间隔T'之间的差值。

2.1.3 恒定比特流模型和可变比特流模型

漏桶模型和通用信元速率模型刻画了大多数的QoS数据业务，恒定比特流模型和可变比特流模型作为这两种模型的扩展在特定场景下也有广泛的应用。恒定比特流是最简单的业务比特流，可以看作是桶深无限大的漏桶模型的一个特例，到达曲线为:

可变比特流的代表是RSVP(ReSerVation Protocol)协议中的path报文。它描述了确保服务中定义的T-SPEC流量特征信息，到达曲线为:

其中参数M为最大报文长度，p为峰值速率，b为桶深，r为平均速率。在进行业务QoS协商和资源预留时，会话发起方首先发向目的节点送path报文，中间节点会读取业务流信息并根据自身服务能力判断能否达到业务流的QoS需求，达到需求才继续更新和传递path报文，最后得到能够提供可靠服务的业务流端到端传输路径。

2.1.4 无记忆开关流模型

无记忆开关流多用于语音电话、彩铃、视频电话业务。对于无记忆开关流，在ON状态下业务以恒定速率R产生数据流，而OFF状态下则不产生数据流。无记忆开关流的流量特性具有统计性，用确定网络演算无法描述，它的有效到达曲线为:

2.1.5 分形布朗运动流模型

分形布朗运动流是一种典型的自相似流，它主要用于描述手机电视、手机游戏、WAP等多媒体业务。分形布朗运动的到达累积函数I(t)=ρt+βZt。Zt为自相似参数为H的分形布朗运动，ρ代表流量均值，β2代表流量方差。分形布朗运动流的有效到达曲线为:

2.2 通用服务曲线的求解

网络演算最早是针对IntServ服务体系提出的。在IntServ中各类业务流根据流量特征被分类建模，并通过资源预留与QoS协商达到确保服务。资源预留的过程是一个分组调度过程，而服务曲线正是对分组调度过程的抽象。Parekh和Gallagher通过研究GPS(Generalized Processing Sharing)调度算法定义了严格服务曲线，描述了节点向业务流提供最低服务的能力。包括GPS在内，虚拟时钟调度(Virtual Clock Scheduling)、自时钟公平排队(Self-clock Fair Scheduling)等调度算法都满足保证速率GR(Guranteed Rate)框架，并符合速率延迟时间(Rate-lantency)模型。因此，IETF定义了通用服务曲线，为各应用场景下服务曲线的推算提供了模版。

通用服务曲线定义为:

其中R为节点提供的服务速率，T是与R有关的时延参数。R与节点自身服务能力以及调度算法有关，在不能直接求得R时，可以将R等效为该节点到下一节点间的链路吞吐量求解。

T主要用于表示一定的时延，具体定义为:

3 网络性能指标的计算

本节主要介绍网络演算如何通过到达曲线和服务曲线求解网络节点的主要性能指标。假设一条流经N个节点的数据流，记广义增函数Ih(t)、Oh(t)分别为为节点h的输入输出流量累积函数。节点的到达曲线和服务曲线如图1所示:

图1 节点网络性能分析示意图

3.1 时延

对业务流量来说，节点对数据的处理过程可以看作一个排队问题，假设节点对数据的处理是无时延的，那么一个数据比特进入和流出节点的时间应该相同。则任意时刻t0下，时延D0(t)为服务曲线与到达曲线之间的水平偏差值，即O(t0+D(t0))=I(t0)。最大水平偏差值D即为时延上界:

时延上界表示业务流经过节点经历的最大可能时延，即只有D不超过业务流的时延限制，节点才能为该业务流提供可靠的服务保障［25］。

3.2 时延抖动

时延抖动一般有两种定义方法，一是定义为数据传输中时延的最大差值，即:

二是定义为时延函数的方差，即:

时延抖动能够体现业务对时延稳定程度的需求。

3.3 数据积压

假设业务流流经节点没有数据损失，则任意时刻t0下，数据积压B0(t)为到达曲线与服务曲线之间的垂直偏差值，即O(t0)+B(t0)=I(t0)。最大垂直偏差B(t)为数据积压上界:

数据积压上界为业务流经过节点进行排队处理时的最大队列长度，即只有节点缓冲区大小不小于B(t)，节点才能为该业务流提供可靠地服务保障。

3.4 可用带宽、有效带宽和等效容量

假设一条到达曲线为α(t)，且要求时延不超过DQoS的业务流能够以确保服务通过预留缓冲区长度为BQoS的节点。当α(t)为凹函数时，可用带宽、有效带宽和等效容量如图2所示。

图2 可用带宽示意图

可用带宽E为节点实际能够为业务流提供的传输速率，表现为服务曲线的斜率。有效带宽ED为能够满足时延 DQoS要求的最小传输速率，表现为t=－D处与到达曲线之间的斜率，即:

等效容量为给定到达曲线α(t)和节点缓冲区长度为BQoS时的传输速率，表现为纵坐标数据量为B处与到达曲线的斜率，即:

4 总结与展望

网络演算能够直观、准确、实时地分析节点网络性能，进而计算整个网络的性能边界，在解决复杂业务流的QoS保障问题上得到了广泛应用。在近十年的发展中，确定网络演算的理论已相对成熟，并应用于解决各种网络性能分析问题［13-15］。随机网络演算将网络演算的应用从求解最坏情况下的性能边界扩展到求解一般情况下的具体性能，使网络演算能对使用统计复用的多媒体业务流进行更加准确的分析。但由于将概率论完全引入最小加代数系统还存在一定难度，随机性网络演算的研究还有很大的发展空间。总之，基于网络演算的网络性能分析方法能够填补传统网络性能分析方法的不足，为解决各类网络分析问题提供了新的方法和思路，具有良好的应用前景，值得进一步关注和研究。

［1］ 陈艳平.基于网络演算的QoS分析方法与保障技术［T］.哈尔滨工业大学博士研究生学位论文，2012:3.

［2］ C.Partridge S.Shenker，R.Guerin.Specification of guaranteed quality of service［C］.RFC 2212，Internet Engineering Task Force.September 1997:889-893.

［3］ S.Berson S.Herzog R.Braden(Ed.)，L.Zhang，S.Jamin.Resource reSer Vation Protocol(RSVP)version 1，functional specification［C］.RFC 2205，Internet Engineering Task Force.September 1997:953-962.

［4］ Jean-Yves Le Boudec，Patrick Thiran.Network Calulus:A Theory of Determinstic Queuing System for the Internet［C］.Herdelberg:Springer-Verlag.2004:140-151.

［5］ R.L.Cruz.A calculus for network delay，part I:Network elements in isolation［J］.IEEE Trans Inform Theory.Jan 1991，37:114-131.

［6］ H.Aariowan.A service curve approach to performance guarantees in integrated service networks［C］.PhD dessertation，Univ Calif San Diego.1996:46.

［7］ C.S.Chang.Performance Guarantees in Communication Networks［C］.Springer-Verlag.New York.2000:930-939.

［8］ 倪锐，周武旸，卫国.基于网络演算的无线蜂窝网建模及其业务匹配研究.通信学报［J］.2010，31(7):33-39.

［9］ C.Florin，B.Almut，L.Jorg.Sealing properties of Statistieal End-to-End Bounds in the Network Caleulus［J］.IEEE Transaetionson Information Theory，2006，52 (6):2300-2312.

［10］ G.AndrasB Jozsef Astochastie Extension of Network Caleulus for Workload Loss Examinations［J］.IEEE Conununications Letters，2006，10(5):399-401.

［11］ M Flider，S Recker.Conjugate network calculats:a dual approach to applying the legendre transform［J］.Computer Networks，2006 50(8):1026-1039.

［12］ A.Burchard C.Li，J.Liebeherr.A network calculus with effective bandwidth［C］.Technical Report CS － 2003-20，U-niversity ofVirginia，Computer Science Department.Nov 2003.

［13］ 李庆华.基于网络演算的无线自组网QoS确定性能确定上界研究［J］.通信学报，2008，29(9):32-39.

［14］ 喻莉，姜烈，罗晶晶，张婕.基于跨层网络演算模型的无线网络移动性能分析［J］.电子与信息学报，2012，34(1):57-62.

［15］ 李庆华.基于网络演算的无线自组网TCP性能分析与改进［T］.中南大学，研究生博士学位论文，2010:42-56.