依赖树模型和上向——下向算法在网络时延估测中的应用

摘要：因特网发展得越来越庞大，越来越复杂，各条链路的运行参数对于评估网络性能十分重要，但有时无法直接测量。网络断层成像（network tomography）技术研究基于端-端测得的数据推算链路的性能参数。本文提出了利用依赖树模型和上向——下向算法，推测链路的时延分布。仿真实验证明了这种方法的正确性，能够根据端-端测量结果精确地推算出链路的时延特性。 关键字：网络断层成像；依赖树模型；上向——下向算法。   Abstract: Internet is increasing larger and more complex. It is essential to have link-level performance data for management, but sometimes it cannot be measured directly. Network tomography is based on end-to-end measurement to reason the network internal performance. Instead of using classical statistics method, we use the dependence tree model and upward-downward algorithm to infer link delay. The simulation results show the method works efficiently and produces reasonable accurate results. Keywords: network tomography；Dependence Tree Model；Upward-Downward Algorithm

1 引言

      为了更好地设计、控制和管理网络，必须要更好的了解网络特性。Internet是个庞大的分布式网络并且还在不断的扩大，仅仅通过网络设备收集的数据，反映网络状况，只能管理较小的网络。如果希望得到更大范围、更普遍意义的网络运行参数，只能借助于端到端的测量。利用端到端测量的结果，建立数学模型，计算出网络内部各条链路的统计特征，例如时延和丢包率，可以帮助我们优化网络。这种利用端到端测量推测网络内部运行特征的方法称为网络断层成像（network tomography）[1]。       目前关于链路时延性能推测的研究文献主要有[2]-[8]。本文采用依赖树模型（Dependence Tree Model）和上向——下向算法（Upward-Downward Algorithms）[9]，对各条链路时延进行离散化处理，通过在源节点加载多播探测流量，根据在多个不同的接受节点采集到的探测包的时延情况，推测途径的各条链路的时延分布。这种方法利用了多播探测流量在公共链路上的相关性，结合我们使用的模型和算法进行推测。在网络中进行多播形成的树状结构与依赖树非常相似，使得这一问题比较适合使用依赖树进行解决，算法简单。       依赖树是为解决n维随机变量联合概率分布问题而提出的一种模型。令X=(X1,X2,…Xn)表示n维离散随机变量，P(X)表示X的联合概率密度函数，那么依赖树就可以定义为一个三元组{X,S,P}，其中，S表示树结构，即X中各个分量之间的依赖关系。如果树状拓扑结构已知，那么对联合概率的估计就可使用上向－下向算法得到。

2 多播依赖树模型和上向——下向算法

      把多播探测情况抽象为一棵逻辑多播树，由源节点发送多播探测包，在各个叶子节点接收。假设对于不同链路和不同探测包来说延迟是相互独立的。可以把逻辑多播树看作是一种特殊的依赖树，它比依赖树增加了一个源节点，另外拓扑结构已知并且只能在叶子节点进行观测。图1就是这样一个多播依赖树，节点0作为源节点发送探测包给叶子节点。           图1: 8个节点的多播依赖树模型         由于端到端测量的特点，我们只能在源节点和叶子节点上观测数据，而对于根节点和中间节点中的实际情况不清楚，于是可以把节点分为三类：

3 仿真结果

      为了证明依赖树模型和上向——下向算法在时延估计中的正确性，我们使用C++编写软件进行了仿真计算。按照图1所示的树状拓扑结构，假设各条链路上延迟最大为3个单位，最小为0，即M=4，可以任意设置不同链路上不同延迟出现的概率。   图2 仿真结果:估测值与实际值的比较