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

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

 

图2 仿真结果:估测值与实际值的比较

      本文提出了利用多播依赖树模型和上向——下向算法推测链路时延的方法。和传统的方法比较，这种方法可以在数据不完整的情况下，推测各条链路上的条件概率，这也恰恰适合端到端测量的特点。仿真结果也显示了这种方法的正确性和有效性，估测数据和真实数据比较一致，能够反映链路延迟的基本状况。相信我们提出的这种方法可以运用到以后的网络测量中。

 

1. M.Coates, A.O.Hero, R.Nowak and B.Yu. “Internet Tomography,” IEEE Signal Processing Magazine, May 2002, pp. 47-65.

2. M. Coates and R. Nowak, “Network tomography for internal delay estimation,” in Proc. IEEE Int. Conf. Acoust., Speech, and Signal Proc., May2001, pp. 3409-3412.

3. M. Coates and R. Nowak, “Sequential Monte Carlo Inference of Internal delays in nonstationary data networks,” IEEE Transactions on Signal Processing, Vol. 50, No. 2, Feb. 2002, pp. 366-376

4. Y. Tsang, M. Coates, and R. Nowak, “Nonparametric Internet tomography,” in Proc. IEEE Int. Conf. Acoust., Speech, and Signal Processing, May 2002

5. Y. Tsang, M. Coates, and R. Nowak, “Network delay tomography,” IEEE Transactions on Signal Processing, Vol. 51, No. 8, Aug. 2003, pp. 2125-2136.

6. F. Lo Presti, N.G. Duffield, J. Horowitz, and D. Towsley, “Multicast-based inference of network-internal delay distributions,” Univ. Massachusetts, Amherst, MA, Tech. Rep. 99-55, 1999.

7. M.F. Shih and A.O. Hero, “Unicast inference of network link delay distributions from edge measurements,” in Proc. IEEE Int. Conf. Acoust., Speech, and Signal Processing., Salt Lake City, UT, May 2001, pp. 3421-3424.

8. M.F. Shih and A.O. Hero, “Unicast inference of network link delay distributions using mixed finite mixture models,” in IEEE Int.Conf. Acoust., Speech, Signal Process., Orlando, FL, May 2002.

9. O.Ronen, J.R.Rohlicek, and M.Ostendorf, “Parameter Estimation of Dependence Tree Models Using the EM Algorithm,” IEEE Signal Processing Letters, Vol.2, No.8, pp.157-159, Aug. 1995.