多发送端拓扑结构中网络链路延迟推断方法

许鑫¹，何泾沙²，石恒华¹

 (1. 北京工业大学 计算机学院，北京，100124；

2. 北京工业大学 软件学院，北京，100124)

摘  要：为检测多发送端拓扑结构中网络内部延迟情况，在充分利用路径延迟数据的基础上，提出一种简单易行的网络链路延迟分布推断方法。在满足网络平稳性、网络链路延迟的时间独立性和空间独立性的假设下，将复杂的多发送端拓扑结构的网络分解成多个简单的单发送端拓扑结构的分解单元，采用最大似然估计法并按照分解单元所含链路个数的升序推断各分解单元中的网络链路延迟分布，使得分解单元中的数据流共享链路延迟分布的真实值和估计值之间的差异逐渐减小。研究结果表明：采用该方法能有效推断出复杂的多发送端拓扑结构中网络链路延迟分布情况，与最小方差权值平均方法相比，具有较高的精度。

关键词：延迟；推断；拓扑；最大似然估计；多发送端

中图分类号：TP393.06          文献标志码：A         文章编号：1672-7207(2010)03-1058-07

Network link delay inference in multiple-source topology

XU Xin¹, HE Jing-sha², SHI Heng-hua¹

 (1. College of Computer Science, Beijing University of Technology, Beijing 100124, China;

2. School of Software Engineering, Beijing University of Technology, Beijing 100124, China)

Abstract: Considering making good use of path delay data, an easily-accomplished method for inferring network link delay distributions was proposed to monitor network internal delay in multiple-source topology. Under the assumptions that the network was stationary, network link delays were temporally and spatially independent, the complex multiple-source network was decomposed into simple multiple single-source decomposition units. The ascending order of the number of links in every decomposition unit was regarded as the inference order for all decomposition units. Maximum likelihood estimation was adopted to infer network link delay distributions for each decomposition unit. The difference between the true and estimated value of network shared data-flow link delay distributions gradually decreased in these inference procedures. Simulation results demonstrate that this method can effectively infer network link delay distributions in complex multiple-source topology, and obtain higher accuracy than the method of minimum variance weighted average.

Key words: delay; inference; topology; maximum likelihood estimation; multiple source

网络透视(Network tomography)^[1]作为新兴的网络测量方法已受到很多研究机构^[2-7]的关注。其基本思想是利用统计学方法，分析端到端的网络路径级属性信息并推断网络链路级属性信息，以更好地检测网络行为及诊断网络的性能变化。Chen等^[8]认为这种方法将成为复杂网络性能诊断和评估中最受关注的方法之一。在对基于网络透视的链路延迟分布推断研究   中，Lo等^[9]提出使用端到端多播测量法建立基于逻辑多播树的离散延迟推断模型。Shih等^[10]提出使用端到端单播测量法建立有限的混合模型，采用最大似然估计(Maximum likelihood estimation, MLE)和期望最大化(Expectation maximization, EM)算法来推断网络链路延迟情况。Xia等^[11]对固定和随机这2种网络链路延迟情况分别进行了研究，并对随机情况采用混合指数模型进行建模。虽然这些方法可以较精确地推断出网络链路延迟情况，但是，这些都是针对单一发送端的情况进行研究的，对于复杂拓扑结构的网络链路性能研究还较少。Bu等^[12]提出采用最小方差权值平均(Minimum variance weighted average, MVWA)方法对多发送端拓扑结构的网络链路丢包率和延迟分布进行研究。通过对每一个逻辑多播树进行单独推断，根据所获得的探测包数量进行加权得到融合结果。然而，这种方法没有充分利用来自各逻辑多播树的路径数据，忽略了其中的关联关系，造成最终推断结果不精确。Rabbat等^[13]通过研究网络拓扑结构变化，探测包到达序列及时间同步等来对复杂拓扑结构的网络链路丢包率进行推断，该方法的分析过程较复杂且实现较困难。由于多播测量能有效节省带宽且易于统计推  断^[9]，本文作者采用端到端多播测量法进行推断研究。在尽可能充分利用路径数据的基础上，提出一种简单易行的针对多发送端拓扑结构的网络链路延迟推断方法。在满足网络平稳性、网络链路延迟的时间独立性和空间独立性的假设下，将复杂的多发送端拓扑结构的网络分解成多个分解单元，并根据各分解单元所含链路数量的升序依次推断各分解单元中的网络链路延迟分布。

1  多发送端拓扑结构分解

在满足网络平稳性、网络链路延迟的时间独立性和空间独立性的假设下，本文作者提出分解排序法，即提出将多发送端拓扑结构的网络分解为多个单发送端拓扑结构的分解单元，并按照各分解单元所含链路数量的升序进行排序。

1.1  假设条件

基于如下假设^{[2, 9-10]}对网络延迟分布进行推断研究：

(1) 网络平稳性。每次测量时网络保持平稳。

(2) 时间独立性。不同数据包在同一链路上的延迟统计独立，并且同分布。

(3) 空间独立性。同一数据包在不同链路上的延迟统计独立。

网络流量突发或长时间发生延迟会造成不同数据包之间发生关联，此时，时间独立性不成立；经过同一路径的不同数据流会发生相互影响，此时，空间独立性不成立。然而，Lo等^{[9, 14]}证明了当上述假设条件不能满足时，对网络性能推断的影响程度很小。同时，这些假设又有助于分析网络属性和结构信息，因此，本文作者基于上面的假设条件进行推断研究。

1.2  分解单元

选择逻辑多播树^[9]作为研究多发送端拓扑结构中的基本分解单元。定义逻辑多播树为T = (V, L)(其中：V为节点集；L为链路集)。发送端节点作为逻辑多播树的唯一根节点。节点对(k, j)表示从节点k到节点j的链路j。这里，链路j对应的节点就是节点j，节点k是节点j的父节点。

分解单元如图1所示，其中：节点0是发送端节点，节点1是分支节点，并且是节点2和节点3的父节点；节点2和节点3是互为兄弟的叶节点。发送端链路1与链路2和链路3分别组成路径1和路径2。因此，基于网络透视的延迟分布推断模型Y=AX ^[2]，根据可测的路径i上的延迟Y _i (i=1, 2)和已知的拓扑结构A，来推断链路j上的延迟X_j (j=1, 2, 3)。

图1  分解单元

Fig.1  Decomposition unit

1.3  分解排序法

设多发送端拓扑结构网络中的发送端节点个数为M，接收端节点个数为R，节点集为V，链路集为L。该网络将分解出M个分解单元，每个分解单元都包括唯一发送端链路和多个数据流共享链路。多发送端拓扑结构分解过程如图2所示，具有4个发送端拓扑结构的网络将会被分解为4个分解单元，其中：节点对(S₁, 1)，(S₂, 1)，(S₃, 1)和(S₄, 3)分别为发送端链路S₁，S₂，S₃和S₄。由于发送端节点S₁，S₂和S₃均向接收端节点2，4，5，7和8发送数据流，发送端节点S₄向接收端节点4，5，7和8发送数据流，因此，链路j(j=2, …, 8)为数据流共享链路。节点1和节点3为网络的数据流汇聚节点。

设S_m(m=1, …, M)表示发送端节点，R_m表示发送端节点S_m发送的数据包所到达的接收端节点个数，且R_m≤R，T_m表示以S_m为发送端节点的分解单元，V_m表示分解单元T_m的节点集，L_m表示分解单元T_m的链路集，并且V_m?V，L_m?L，C_m表示L_m中链路个数。分解排序法描述如下：

步骤1  标记发送端节点并确定分解单元个数M。

步骤2  划分出M个分解单元。对于每个发送端节点S_m进行如下操作：从S_m出发，寻找由S_m发送的数据包达到对应的所有R_m个接收端节点所经过的节点集V_m 和链路集L_m，即得到分解单元T_m = (V_m, L_m)。

步骤3  依照每个分解单元T_m所包含的链路个数C_m的升序方式排列各分解单元，完成分解排序过程。

由于C₄＜C₁=C₂=C₃，按照上面的分解排序法，图2中的分解单元排序为T₄ T₁ T₂ T₃。每个数据包都标记其发送端节点，同时，保证其接收端节点能确认该数据包的发送端地址；因此，在多发送端拓扑结构的网络中，每个分解单元T_m都可以采集到对应R_m条路径延迟数据。通过分析这些路径延迟数据来计算出分解单元T_m的网络链路延迟分布。除对第1个分解单元计算外，其余分解单元的计算都是基于前面计算结果依次进行的。在使用相同测量次数的延迟数据时，分解单元T_m含有链路个数C_m越少，计算结果越精确；因此，采用链路个数较少的分解单元作为最先推断对象，使得后续计算能在较好的计算基础上进行修正。

2  分解单元的链路延迟分布计算方法

采用离散延迟模型^[10]对网络中的各分解单元进行链路延迟分布的计算。在对分解单元中的所有链路进行拓扑简化后，使用最大似然估计法^[15-16]对该分解单元中的网络链路延迟分布参数进行估计。

2.1  离散延迟模型

设q为离散延迟模型中的量化单元，主要用来量化所有链路j上的延迟X_j (j=1, …, J)。当延迟X_j在 内时，则该延迟被量化为dq。其中：量化索引d=0, …, D；D为1个正整数。当d=0时，量化区间为。

令表示量化后的链路j上的延迟分布；

，为待估计参数，并且满足。

2.2  分解单元的计算方法

2.2.1  拓扑简化

为便于对分解单元中的各条链路延迟分布进行参数估计，提出1种拓扑简化法来分析和处理各链路在所属分解单元中的拓扑结构。即对于某条链路，在其所属分解单元中寻找通过该链路的所有路径，通过进行拓扑简化使得每条链路只属于该分解单元中的某一条路径。若仅有1条路径通过，则不需要进行拓扑简化处理。

图2  多发送端拓扑结构分解

Fig.2  Decomposition of multiple-source topology

对于某条链路j的拓扑简化描述如下。

步骤1  寻找子孙节点。寻找并标记链路j对应节点的所有子孙节点。

步骤2  自底向上，逐步合并。在这些子孙节点中，从深度最大(距离链路j所对应节点的跳数最多)的叶节点开始，先对同父的兄弟节点进行合并，然后，与其父节点合并。依此类推，直至下一个将合并的节点为链路j对应的节点为止，此时得到1条路径。

以图2分解单元T₁中的链路3为例，拓扑简化过程如图3所示。在步骤1中寻找链路3的子孙节    点，链路3对应节点3，节点3的所有子孙节点为节点4、5，6，7和8。在步骤2中，先合并兄弟叶节点7和8为节点(7, 8)，然后，与其父节点6合并为节点(6, (7, 8))，再与节点6的兄弟节点4，5合并为节点   (4, 5, (6, (7, 8)))，此时，它们的父节点为节点3，是所求链路3的对应节点。可见，中止拓扑简化，得到路径S₁-1-3-(4, 5, (6, (7, 8)))。

图3中节点(4, 5, (6, (7, 8)))对应链路的延迟概率可以表达为：

其中：d_j为链路j上延迟的量化索引；y₁，y₂，y₃和y₄分别为到叶节点4，5，7和8的路径延迟值，函数index(x)表示延迟值为x时所对应的量化索引。

2.2.2  参数估计

采用最大似然估计法^[15-16]对该分解单元中的网络链路延迟分布进行参数估计。

令Y为可测的端到端路径延迟数据。第j条链路上延迟X_j的概率为：

因此，在给定完整延迟数据X₁, …, X_T的情况下，X的对数似然函数表示为：

其中：()；为链路j上经历延迟为dq的数据包个数；I为示性函数；X_tj为第t组数据中链路j的延迟。

通过EM算法求解网络链路延迟分布的最大似然估计值。

令表示第k次估计，最大化第k+1次目标方程为：

计算出第k+1次估计值，循环计算，直至得到满足一定精度的网络链路延迟分布的估计值为止。

3  多发送端拓扑结构中网络链路延迟推断方法

对于整体的多发送端拓扑结构，提出的推断过程描述如下。

步骤1  按照分解排序法分解多发送端拓扑结构的网络，得到分解单元的排序；

步骤2  依次选择分解单元T_m，按照分解单元计算方法对T_m中所有链路进行拓扑简化，使用其对应的R_m条路径延迟数据进行最大似然估计，计算发送端链路和数据流共享链路的延迟分布，此时，将数据流共享链路的延迟分布作为计算下一个分解单元延迟分布的初始值，即下一次计算过程是修正前面的计算结果。

图3  拓扑简化

Fig.3  Topology simplification

步骤3  重复步骤2，直到完成对所有分解单元的计算为止，从而得到多发送端拓扑结构中所有链路的延迟分布情况。

其中，发送端链路只包含于1个分解单元中，因此，只使用所在分解单元的路径延迟数据进行1次计算，而数据流共享链路可以使用包含它的所有分解单元的路径延迟数据进行多次计算。

4  仿真实验

4.1  实验平台

使用OPNET仿真软件进行多发送端拓扑结构的网络延迟实验。网络拓扑如图4所示。节点对(S₁, 1)，(S₂, 1)，(S₃, 1)和(S₄, 3)分别为发送端链路S₁，S₂，S₃和S₄，其余链路均为数据流共享链路。

4.2  实验设置

图4中各链路的数据传送速率如表1所示，各发送端节点发送的数据包属性如表2所示。实验仿真时间为1 000 s，选择量化单元q=0.1，共有40个量化区间。在每条链路上采集1 000个点作为该链路延迟的真实值，并采用同一量化单元q=0.1进行量化，统计得到各链路延迟的真实分布情况，用于与本文作者提出的方法的推断结果进行对比。

根据分解排序法，得到分解单元的推断顺序为T₄ T₁ T₂ T₃，即：首先计算分解单元T₄得到链路S₄及数据流共享链路4，5，6，7和8上的延迟分布估计值；将这些数据流共享链路上的延迟分布估计值作为计算分解单元T₁中对应链路上的延迟分布初始值，以得到链路S₁及数据流共享链路2，3，4，5，6，7和8上的延迟分布估计值；将这些数据流共享链路上的延迟分布估计值作为下一个分解单元T₂中对应链路上的延迟分布初始值。依此类推，计算得出所有链路上的延迟分布估计值。

图4  多发送端的网络拓扑

Fig.4  Multiple-source network topology

4.3  实验结果

4.3.1  有效性验证

选择非数据流共享链路S₁以及数据流共享链路2，4和8作为代表链路进行分析。图5所示为这4条链路上的延迟分布真实值和估计值的对比结果。

如图5(a)所示，对于非数据流共享链路S₁，只使用分解单元T₁进行网络链路延迟分布估计，虽然没有多次估计修正过程，但是网络链路延迟分布估计值已经能较好模拟真实网络的变化情况。

设P_d和Q_d分别表示当量化索引为d时数据流共享链路j上的延迟分布真实值和估计值，根据计算链路j的P_d和Q_d之间的差异，其中，数据流共享链路4和8共进行了4次估计，结果如表3所示。

表1  各链路上数据传送速率

Table 1  Data rate of each link

表2  各发送端节点发送的数据包属性

Table 2  Packet properties of each source

(a) 链路S₁；(b) 链路2；(c) 链路4；(d) 链路8

图5  链路延迟分布真实值和估计值的对比

Fig.5  Comparisons between true and estimated values of links delay distribution

对于数据流共享链路，对真实值与多次修正的估计值进行对比，结果如图5(b)~(d)所示。可见：每次修正结果总体上都更趋近于真实的延迟分布情况。链路4和链路8上的延迟真实值和估计值之间的差异如表3所示，可见：链路4和8的每次估计都使得真实值和估计值的差异减小。图5也显示出每次修正后的变化趋势。

表3  链路4和链路8上的延迟真实值和估计值之间的差异

Table 3  Difference between true and estimated values of delay for Link 4 and Link 8

在对多发送端拓扑结构的网络链路延迟分布进行推断研究时，要充分考虑所有分解单元中的数据流对网络性能的影响。从图4可见：该网络中的4个发送

端节点所产生的数据流共同影响其数据流共享链路，因此，只使用其中某个分解单元的路径数据进行分析，则推断结果只是受该分解单元中数据流影响的粗略估计值。但是，若在满足网络平稳性、网络链路延迟时间独立性和空间独立性的假设条件下，使用其余分解单元的路径延迟数据对该分解单元的粗略估计值进行多次迭代修正，则会使推断结果更符合网络内部的真实情况。

4.3.2  与MVWA方法的比较

采用本文作者提出的方法与MVWA方法^[12]所得的链路延迟分布比较结果如图6所示。链路延迟分布概率越大，精度越高。从图6可见：作者提出的方法优于MVWA方法。由于MVWA方法只是通过对每个逻辑多播树进行单独计算，虽然考虑了所有数据流的影响，但是，这种较简单的通过加权得到估计值的方法却降低了精度。而作者提出的方法在没有增加计算复杂度的情况下，充分利用了路径数据，通过多次估计修正达到较高的精度。

1—真实值；2—本文方法估计值；3—MVWA估计值

(a) 链路2；(b) 链路4

图6  本文方法与MVWA方法链路延迟分布概率的比较

Fig.6  Comparisons of probability of links delay distribution between method in this paper and MVWA method

5  结论

(1) 提出一种网络链路延迟分布推断方法来解决复杂的多发送端拓扑结构中网络内部延迟推断问题。该方法将复杂的多发送端拓扑结构的网络分解成多个简单的分解单元，并按照各分解单元所含链路个数的升序计算各分解单元网络链路延迟分布。

(2) 每个分解单元的计算是在完成拓扑简化处理后，使用最大似然估计法进行网络链路延迟分布的估计。由于对每个分解单元的数据流共享链路延迟分布的计算，都是基于前面估计结果进行修正，因此，数据流共享链路延迟分布的真实值和估计值之间的差异逐渐减小，即推断结果逐渐趋近于网络内部的真实情况。

(3) 与MVWA方法相比，本文作者所提出的方法能更精确地推断出多发送端拓扑结构中网络内部链路延迟情况，具有较强的实用性。

参考文献：

[1] Vardi Y. Network tomography: estimating source-destination traffic intensities from link data[J]. American Statistical Association, 1996, 91: 365-377.

[2] Castro R, Coates M J, Liang Gang, et al. Network tomography: recent developments[J]. Statistical Science, 2004, 52(3): 499-517.

[3] Duffield N G. Network tomography of binary network performance characteristics[J]. IEEE Transactions on Information Theory, 2006, 52(12): 5373-5388.

[4] Shih M, Hero A O. Hierarchical inference of unicast network topologies based on end-to-end measurements[J]. IEEE Transactions on Signal Processing, 2007, 55(5): 1708-1718.

[5] Jin Xing, Tu Wang-qing, Gary Chan S H. Scalable and efficient end-to-end network topology inference[J]. IEEE Transaction on Parallel and Distributed System, 2008, 19(6): 837-850.

[6] Duffield N G, Lo Presti F, Paxson V, et al. Network loss tomography using striped unicast probes[J]. IEEE/ACM Transaction on Networking, 2006, 14(4): 691-710.

[7] Sharma G, Jaggi S, Dey B K. Network tomography via network coding[C]//Masimo F. IEEE Information Theory and Applications Workshop. Piscataway: IEEE, 2008: 151-157.

[8] Chen Ai-you, Cao Jin, Bu Tian. Network tomography: identifiability and Fourier domain estimation[C]//IEEE INFOCOM. Anchorage: IEEE, 2007: 1875-1883.

[9] Lo P F, Duffield N G, Horowitz J, et al. Multicast-based inference of network-internal delay distributions[J]. IEEE/ACM Transactions on Networking, 2002, 10(6): 761-775.

[10] Shih M, Hero A O. Unicast-based inference of network link delay distributions with finite mixture models[J]. IEEE Transactions on Signal Processing, 2003, 51(8): 2219-2228.

[11] Xia Y, Tse D. Inference of link delay in communication networks[J]. IEEE Journal on Selected Areas in Communications, 2006, 24(12): 2235-2248.

[12] Bu T, Duffield N G, Lo Presti F, et al. Network tomography on general topologies[C]//Richard M. Proceeding of the ACM Sigmetrics. Marina Del Rey: ACM Press, 2002: 21-30.

[13] Rabbat M G, Coates M J, Nowak R D. Multiple-source Internet tomography[J]. IEEE Journal on Selected Areas in Communications, 2006, 24(12): 2221-2234.

[14] Caceres R, Duffield N G, Horowitz J, et al. Multicast-based inference of network-internal loss characteristics[J]. IEEE Transactions on Information Theory, 1999, 45(7): 2462-2480.

[15] Liang Gang, Yu Bin. Maximum pseudo likelihood estimation in network tomography[J]. IEEE Transactions on Signal Processing, 2003, 51(8): 2043-2053.

[16] Tsang Y,Nowak R. Network tomography in theory and practice[D].Houston: Rice University. Department of Electrical and Computer Engineering, 2005.

收稿日期：2009-04-10；修回日期：2009-07-10

基金项目：北京市自然科学基金资助项目(KZ200610005003)；北京市教委科技发展面上项目(KM200510005008)

通信作者：许鑫(1981^­-)，女，北京人，博士研究生，从事网络性能和拓扑测量的研究；电话：13910411711；E-mail: cindy_xu@emails.bjut.edu.cn

(编辑 刘华森)