Search

Inference of network internal characteristics has become an increasingly important issue for communication network operation. Since it is impractical to directly monitor the network internal nodes, people use the end-to-end information collected by probe packets to estimate the statistics of interest. This new area of networking research is called network tomography . When specialized to the Internet it is called Internet tomography. Our work focuses on unicast probing methods, which are supported by much of today's Internet. We first deal with the estimation of internal link delay distributions from end-to-end delay measurements. Unlike the discrete delay models used in previous work, we focus on continuous distributions of non-zero queueing delays. We send individual unicast packets throughout the network and develop an estimator for link delay cumulant generating functions (CGF) based on an over-determined system of equations. We propose a bias corrected estimator for the CGF which eliminates the nonlinearity effect of the log function. When the network is modelled by a logical tree we use packet pair probes to collect end-to-end delay information. We propose a novel hybrid continuous/discrete finite mixture model for the link delay distributions. A penalized maximum-likelihood expectation-maximization (PML-EM) algorithm is developed to select the model and estimate its parameters. Since the complexity of the algorithm grows exponentially with the size of the network, we propose an accelerated algorithm to obtain a linear reduction in run-time. The second problem we address is network topology discovery using end-to-end measurements. Topology estimation can be formulated as a hierarchical clustering problem of the leaf nodes based on pair-wise correlations as similarity metrics. Unlike previous work which first assumes the network topology being a binary tree and then tries to generalize to a non-binary tree, we provide a framework which directly deals with general logical tree topologies. Based on our proposed finite mixture model for the set of similarity measurements we develop a penalized hierarchical topology likelihood that leads to a natural hierarchical clustering algorithm for the leaf nodes. The performance of our algorithms are evaluated by matlab and ns-2 simulations.