As telecommunication networks grow larger and more complex, it is important to monitor internal link characteris tics for operation, monitoring, and diagnosis pwposes. Since router link monitoring is not practical due to high commu nication overhead, there has been considerable interest in monitoring from edge (end-to-end) observations. This pa per fo cuses on the estimation of internal link delay distri butions from edge measurements. Discrete and continuous delay models are introduced and we propose a new mixed finite mixture model for link delay probability density func tions(p.d.f.). When collecting end-to-end unicast packet de lays from edge nodes, we are able to estimate internal link delay distributions using the EM algorithm. Simulation re sults are given to illustrate our method. Network tomography is a new area concerned with inference of internal statistics of a network based on end-to-end mea surements at edge nodes. Tomography provides a vital tool for characterizing network behaviors without cooperating in ternal nodes. This is especially useful when either internal parameters are inaccessible or direct measurement of data traffic statistics are not supported by internal switches and routers [I, 2, 3, 51. Link-level packet delays are important particulars for op timizing network performance and evaluating quality of ser vice(QoS). While transmission and propagation delays are usually conSidered as constant factors, the queueing delays contribute random packet delays. The inference of link delay distributions from end-to-end measurements was first pro posed by Presti et al [4] . They applied a discrete (binned) delay model and derived a sample-average based algorithm using multicast probes. Coates and Nowak [5] suggested an alternative '.unicast probing scheme using packet pairs and developed a :maximum likelihood(ML) inference technique based on the EM algorithm. A unicast approach for estimat ing cumulant generating functions of internal link delays was introduced in [6] . In this paper, our fo cus is on a mixed discrete and con tinuous model for unicast end-to-end packet delays for in- ference of internal link delay distributions. First we review identifiability conditions for discrete and continuous delay models. Under a mixed finite mixture model for packet link delay p.d.f.'s, we show that it is possible to reconstruct con sistent estimates of the link delay p.d.f.'s using single packet unicast. An EM-based algorithm is used to approximate ML estimates of a Gaussian mixture with a Dirac delta at zero delay. Computer simulations are reported which demonstrate the promise of our approach. As in [5], we consider the network topology as a logical tree , where V is the set of nodes and E is the set of links. Assume the root node has only one child node. As sume a total of L links and number them from 1, . . . ,L. As sociate the only link connecting the root node as link 1. Each node in the tree has two or more child nodes, except the root and leaf nodes. Time stamped unicast packets are sent from the root node to one of the leaf nodes. The leaf nodes, considered as packet receivers, collect end-to-end delays for those packets. The pwpose is to identify the packet delay distribution for each individual internal link from the edge observations at the packet receivers. Assume there are R receivers and R possi ble routes from root to leaf nodes in the network. Note that all the packet routes include link 1. Let X" I = 1, . . . ,L be the packet delay at link I, and l'i, i = 1,... ,R be the end-to-end delay of a packet along the path destinated to receiver i. We make the following in-1.0-7803-7402-9/021$17.00 «:12002 IEEE
REF also used finite mixture models for link delay distributions and implemented an EM algorithm for parameter estimation, but the method was based on unicast measurements and again it suffered from high computational complexity similar to other likelihood based methods.
Unicast-based inference of network link delay distributions using mixed finite mixture models
2002 IEEE International Conference on Acoustics, Speech, and Signal Processing
2002 IEEE International Conference on Acoustics, Speech, and Signal Processing
Computer Science