NT技术中延迟分布估计算法的研究

摘要：网络断层扫描(NT)是一种新的网络外部测量方法，它是网络测量技术与统计学理论相结合的产物。在简要介绍网络断层扫描的基础上，该文提出了一种基于重要性抽样(IS)和期望最大化算法(EM Algorithm)网络断层扫描的时延估计方法，最后基于NS2仿真试验验证了该方法的有效性和准确性。

关键词：网络断层扫描，端到端测量，期望最大化算法，重要性抽样，NS2

中图分类号：TP301文献标识码：A文章编号：1009-3044(2011)09-1997-02

Study on Estimation Algorithm of Network Link Delay Distributions in NT Technology

WU Li-peng, WU Chen-wen, SONG Jin

(Scholl of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

Abstract: Network topology is a new network external measuring method, a product of the combination of network measurement technology and statistical theory. With a brief introduction to network tomography, based on importance sampling (IS) and expectation maximization algorithm (EM Algorithm), the author puts forward a method of Network Link Delay Distributions in NT Technology, and its validity and accuracy is testified by simulation based on NS2.

Key words: network tomography; end-to-end measurements; EM algorithm; importance sampling; NS2

1 概述

网络测量（Network Measurement，NM）是获取网络的拓扑结构和性能参数的方法，也是有效的设计、实现和管理网络的必要工具。但是，当今网络的大规模、分布化、不协作、异质等特点，使得传统的基于网络内部设备的网络测量方法的缺陷越来越明显：

1) 测量依赖于自治系统内部节点的协作，基于网络安全和商业利益等原因，有些自治系统并不对外开放，难以实现内部节点的协作和信息交流，无法保证测量的准确性。

2) 网络测量依赖于特定的网络协议[1]（如TCP/IP协议、SNMP协议），无法实现与网络结构和协议无关的测量；

3) 测量信息的传输可能影响到网络的运行，在网络高负载是无法进行测量。

为此，近年来国际上多家研究机构提出了一种新的网络测量技术称为网络断层扫描（Network Tomography，NT）。它是根据网络外部(即网络边界)的测量信息来分析和推断网络的内部性能，是一种在没有网络节点协作条件下，通过主动发包探测或被动收集网络内部有用信息的新技术，结合统计学方法能够很好地推理出网络所有链路上的QoS参数，如延迟分布、丢包率、网络拓扑结构和OD(origin―destination)流量等。

而EM算法作为一种统计学上的参数估计算法，常被用于推测网络所有链路上的QoS参数，但是EM算法并非万能，其最大的缺点是收敛速度较慢，因此本文把蒙特卡洛方法重要性抽样(Importance Sampling ,简称IS) 与EM算法相结合,提出一种基于重要性抽样的期望最大化算法(IS-EM)。和期望最大化算法相比,新方法不仅十分显著地减少了计算量,而且保持了EM方法的优越性能。

2 链路时延估计EM算法

图1的二叉树模型描述了网路的逻辑结构，节点n0表示发送探针包的根节点，n4～n7为探针包的端接收节点，n1～n3为中间节点。设X=(x1,x2,…,xi)'是反映链路延迟分布性能参数的 维随机向量，Y=(y1,y2,…,yi)'是端接收节点的j维测量向量。而我们的目的就是通过观测向量Y来估计向量X。

其数学模型为：

Y=AX(1)

其中A为路由矩阵又网络拓扑中的路由器决定。

一般情况下，由于i>>j，所以 是不满秩矩阵，所以对于多播延迟推断，极大似然估计方法通常是行不通的，而目前比较通用的方法就是利用EM算法。

EM算法是一种求解极大似然估计的迭代最优化算法，可以从理论上证明，它的每一次迭代都能保证似然函数的非递减性。其迭代可分为两步：一是根据参数初始值或前一次迭代值来计算似然函数的期望（E-Step），第二步将似然函数最大化以获得新的参数值（M-Step），重复这两步，直到认为结果符合收敛条件时结束。

在链路时延估计的线性模型Y=AX下，EM算法的两个迭代计算步骤定义为：

E-Step：计算Q(θ, θ(i-1))。这里

M-Step：在θ中找这样的θ(i)

E-Step和M-Step交替的重复，直到平稳。

3 时延推理算法的改进

3.1 重要性抽样

重要性抽样是经典Monte Carlo 方法里最常用的抽样方法，基本原理如下：

其中p(x)，g(x)是概率密度函数，则积分I估计为

这里，xh是根据g(x) 分布抽取的第h个样本。由先前文献得到，估计值^I是无偏的，其方差取决于g(x)的选择。g(x)称为重要函数(Importance Function，简称IF)。重要性抽样的关键是重要函数的选取。为了减小估计的误差，重要函数应该近似于原概率分布，而且为了实现方便，应该易于从其中抽取样本。把IS方法应用于期望最大化方法，可以把从难以抽取样本的概率密度转换为从重要函数进行抽样。

3.2 基于重要性抽样的最大似然方位估计方法

把重要性抽样和EM算法相结合，需要重点研究该方法中重要函数的选取。首先，在这儿采用的重要抽样函数g(x)与原密度函数f(x)是类型相同的函数，是把f(x)向“感兴趣的区域”移动，以增加在“感兴趣区域”的抽样次数。采用的方法：

1) 寻找对Pf贡献大的点：

① 用JC法求出的设计点作为x*

② 用下列方程求出x*

极限状态方程。

2) 确定重要抽样函数g(x)的均值，把与原概率密度函数相同的函数作为g(x)，并取其均值μg=x*。

3) 确定标准差σg

取一实数b>x*，将区间?Wx*，b 划分为m等分，可得到m个值，v1

式中：

根据上述方法，定义重要抽样函数g(x)为：

g(x)=esx-μ(s)f(x)，其中函数μ(s)=logM(s)可通过f(x)的矩量母函数M(s)=E{exp(sX)}得到。

4 仿真实验

重要抽样的参与能显著的降低EM算法的计算复杂度。为了验证EM算法与重要性抽样结合的方法的有效性，利用图2所示的二叉树网络拓扑在NS2上进行仿真实验。假设网络的时延分布已知，如果时延估计算法所得的结果近似于原始分布，则该法有效。

图2中，n0节点是根节点，负责发送探针包。n8～n15是端接收节点，其它节点是网络拓扑内部节点，途中链路上的数字表示链路上延迟分布的平均延迟。下面将链路直接用其下层节点的编号标识。

在试验中，通过根节点n0到端节点n8～n15各路径上的累计链路时延计算观测值Y，因为有8个端节点，所以有8维。从仿真结果看比较接近与原始时延分布。图3给出了链路n12的原始时延分布与估计时延分布的比较，说明新方法是一种有效的时延分布推测算法。

5 结束语

针对EM算法由于多维搜索而导致的计算量大，难以工程应用的问题，利用蒙特卡罗方法，把重要性抽样与EM估计方法相结合，提出了基于重要性抽样的EM估计新方法。给出了理论推导过程，重点研究了重要函数的选取，并进行了仿真性能研究。结果表明，新方法不但保持了EM方法的优良性能，逼近于真实时延分布，而且把EM算法的计算复杂度显著减少，大大减少了计算量，为EM算法的工程实现提供了一种新途径。

参考文献：

[1] Aiyou Chen，Jin Cao，Tian Bu:Network Tomography:Identifiability and Fourier Domain Estimation.INFOCOM 2007:1875-1883.

[2] Rahman MM，Saha S，Chengan U，Alfa AS.IP traffic matrix estimation methods:Comparisons and improvements.In:Proc.of the IEEE Int'1 Conf on Communications(ICC).Istanbul:IEEE Communications Society，2006，90-96.

[3] 李东，张乃牛孙怡. 网络透视中延迟推理算法的研究和改进[J]. 哈尔滨工业大学学报，2009(1):89-92.

[4] 赵荣芳，耿玉水，韩涛. 网络时延测量技术研究[J]. 山东轻工业学院学报(自然科学版)，2009(2):75-77，82.

[5] 李勇军，蔡皖东，王伟. 网络断层扫描技术综述[J]. 计算机工程，2006，32（13）：91-93.

[6] 王伟，蔡皖东，李勇军. 网络断层扫描中推断分析理论与方法的研究[J]. 计算机应用研究，2007.

[7] 刘瑞芳，徐惠民. 性能测量和推测系统的设计[J]. 计算机与信息技术，2006(9).