Measurement and analysis of end-to-end delay and loss in the internet

Measurement and analysis of the network behavior are crucial to understanding the Internet performance and designing appropriate control mechanisms for better performance. End hosts and their applications, however, have a limited capability in accessing and acquiring information about the network behavior. To them, end-to-end measurement of the network behavior is usually the only available information. This thesis focuses on two fundamental measures of network performance: end-to-end packet delay and loss. First, we address the issue of accuracy in end-to-end delay. Raw delay measurements in the Internet contain impairments due to unsynchronized clocks between two measuring hosts. We propose a linear programming (LP) based algorithm to estimate and remove clock skew in delay measurements. We compare the LP-based algorithm with three other algorithms, and show that the LP-based algorithm is robust, and performs well over actual delay measurements and in simulation. Next, we consider the problem of adaptively adjusting the playout delay at the receiver of packet audio applications. We first present efficient algorithms that compute a bound on the achievable performance of any playout delay adjustment algorithm, and a new adaptive playout delay adjustment algorithm that tracks the network delay of recently received packets and efficiently maintains delay percentile information. We also look at the correlation between end-to-end delay and loss. We quantify the correlation as sample mean delay conditioned on loss and loss conditioned on delay, and analyze the measurements based on them. The results indicate that it is likely that the packet delay would increase in the near future if a packet loss is detected. Recent developments from the MINC (Multicast-based Inference of Network-internal Characteristics) project have shown that we can attain asymptotically converging estimates of link loss using Maximum Likelihood Estimators (MLE) from end-to-end multicast measurements. We validate the effectiveness of the MLE algorithm by showing that the inferred link loss estimates are close to the actual link loss inside the network. Also we study the performance of MLE estimates given a limited number of packets and under a wide range of loss rates and tree topologies. We conclude this dissertation with a discussion for future research.