Multicast topology inference from measured end-to-end loss

The use of multicast inference on end-to-end measurement has been proposed as a means to infer network internal characteristics such as packet link loss rate and delay. We propose three types of algorithm that use loss measurements to infer the underlying multicast topology: (i) a grouping estimator that exploits the monotonicity of loss rates with increasing path length; (ii) a maximum-likelihood estimator (MLE); and (iii) a Bayesian estimator. We establish their consistency, compare their complexity and accuracy, and analyze the modes of failure and their asymptotic probabilities     

Network loss tomography using striped unicast probes

In this paper, we explore the use of end-to-end unicast traffic as measurement probes to infer link-level loss rates. We leverage off of earlier work that produced efficient estimates for link-level loss rates based on end-to-end multicast traffic measurements. We design experiments based on the notion of transmitting stripes of packets (with no delay between transmission of successive packets within a stripe) to two or more receivers. The purpose of these stripes is to ensure that the correlation in receiver observations matches as closely as possible what would have been observed if a multicast probe followed the same path to the receivers. Measurements provide good evidence that a packet pair to distinct receivers introduces considerable correlation which can be further increased by simply considering longer stripes. Using an M/M/1/K model for a link, we theoretically confirm this benefit for stripes. We also use simulation to explore how well these stripes translate into accurate link-level loss estimates. We observe good accuracy with packet pairs, with a typical error of about 1%, which significantly decreases as stripe length is increased.     

Bayesian inference of network loss and delay characteristics with applications to TCP performance prediction

In large-scale dynamic communication networks, end systems cannot rely on the network itself to cooperate in characterizing its own behavior. This has prompted research activities on methods for inferring internal network behavior based on the external end-to-end network measurements. In particular, knowledge of the link losses and link delays inside the network is important for network management. However, it is impractical to directly measure packet losses or delays at every router. On the other hand, measuring end-to-end (from sources to destinations) losses or delays is relatively easy. We formulate the problems of link and delay estimation in a network based on end-to-end measurements as Bayesian inference problems and develop several Markov chain Monte Carlo (MCMC) algorithms to solve them. We show how these link loss and delay estimates can be used to predict point-to-point transfer control protocol (TCP) throughput in the network. We apply the proposed link loss and delay estimation algorithms, as well as the TCP throughput estimation algorithms, to data generated by the network simulator (ns-2) software and obtain good agreements between the theoretical results and the actual measurements.     

Network Tomography of Binary Network Performance Characteristics

In network performance tomography, characteristics of the network interior, such as link loss and packet latency, are inferred from correlated end-to-end measurements. Most work to date is based on exploiting packet level correlations, e.g., of multicast packets or unicast emulations of them. However, these methods are often limited in scope-multicast is not widely deployed-or require deployment of additional hardware or software infrastructure. Some recent work has been successful in reaching a less detailed goal: identifying the lossiest network links using only uncorrelated end-to-end measurements. In this paper, we abstract the properties of network performance that allow this to be done and exploit them with a quick and simple inference algorithm that, with high likelihood, identifies the worst performing links. We give several examples of real network performance measures that exhibit the required properties. Moreover, the algorithm is sufficiently simple that we can analyze its performance explicitly     

NCTU‐VT: a freeware for wireless VoIP performance measurement

Voice over IP (VoIP) is a promising low‐cost voice communication over the wireless IP network. To provide satisfactory VoIP services, the Quality of Service (QoS) of the wireless network should be guaranteed. This paper proposes a VoIP performance measurement freeware called NCTU VoIP Testing Tool (NCTU‐VT). We compare NCTU‐VT with two commercial tools SmartVoIPQoS and IxChariot in terms of packet loss, latency, and Mean Opinion Score (MOS) of the VoIP sessions in Wi‐Fi network. Our study indicates that these three tools can accurately measure VoIP performance in Wi‐Fi environment. Copyright © 2010 John Wiley & Sons, Ltd.     

New delay measurement method based on accurate timestamp in OpenFlow

At present,delay measurement methods in OpenFlow network have the disadvantage of excessive network resources and poor measurement accuracy.DeMon,an active mechanism to measure the delay of multiple paths between any two switch based on the controllable feature of individual traffic flow provided in OpenFlow was proposed.DeMon required only one probe packet to be send from controller,which was excepted to reduce the operational cost.Moreover,DeMon used OpenFlow switch instead of controller to get the timestamp of probe packet,making the measurement accuracy and stability have been greatly improved compared with other monitoring techniques in the OpenFlow network.     

Time‐varying network link loss rate tracking from unicast end‐to‐end measurements

Time‐varying network link loss rate is a useful information for network managers to discover and locate the network link failures. This paper proposes a method to track time‐varying network link loss rates from unicast end‐to‐end measurements. The method first trains a state transition matrix to capture the spatio‐temporal characters of packet link transmission probabilities by sending end‐to‐end probe packets and then estimates the time‐varying link loss rates using the state transition matrix and the end‐to‐end measurements obtained from background traffic (the existed packets in network). We also introduce a validation step to check and retrain the state transition matrix in order to ensure the accuracy of the state transition matrix. Our method is capable of tracking the variation of link loss rates without incessantly sending probe packets, which is very feasible for many practical applications. The ns‐2 simulation results show the good performance of our method.     

Accurate estimation of capacities and cross-traffic of all links in a path using ICMP timestamps

The estimation of the link capacity and its available bandwidth in an end-to-end path is crucial for network management, admission control and flow control for adaptive applications. This paper introduces an estimation mechanism able to accurately estimate the available bandwidth of all links in an end-to-end path, through its capacity and cross-traffic estimation. The estimation procedures resort to the dispersions of packet pairs and trains using the concepts of ICMP Timestamp and Traceroute that, efficiently used together, enable the measurement of the dispersions in all links in the path. These mechanisms were evaluated through simulation experiments, where we analyzed the influence of the several network parameters on each estimation mechanism. The results show that these estimation methods are able to accurately estimate both the capacity and the cross-traffic of all links in a path with moderate length and with low overhead.     

Bandwidth estimation: metrics, measurement techniques, and tools

In a packet network, the terms bandwidth and throughput often characterize the amount of data that the network can transfer per unit of time. Bandwidth estimation is of interest to users wishing to optimize end-to-end transport performance, overlay network routing, and peer-to-peer file distribution. Techniques for accurate bandwidth estimation are also important for traffic engineering and capacity planning support. Existing bandwidth estimation tools measure one or more of three related metrics: capacity, available bandwidth, and bulk transfer capacity. Currently available bandwidth estimation tools employ a variety of strategies to measure these metrics. In this survey we review the recent bandwidth estimation literature focusing on underlying techniques and methodologies as well as open source bandwidth measurement tools.     

The use of end-to-end multicast measurements for characterizinginternal network behavior

We present a novel methodology for identifying internal network performance characteristics based on end-to-end multicast measurements. The methodology, solidly grounded on statistical estimation theory, can be used to characterize the internal loss and delay behavior of a network. Measurements on the MBone have been used to validate the approach in the case of losses. Extensive simulation experiments provide further validation of the approach, not only for losses, but also for delays. We also describe our strategy for deploying the methodology on the Internet. This includes the continued development of the National Internet Measurement Infrastructure to support RTP-based end-to-end multicast measurements and the development of software tools to analyze the traces. Once complete, this combined software/hardware infrastructure will provide a service for understanding and forecasting the performance of the Internet     

Evaluation and characterization of available bandwidth probing techniques

The packet pair mechanism has been shown to be a reliable method to measure the bottleneck link capacity on a network path, but its use for measuring available bandwidth is more challenging. In this paper, we use modeling, measurements, and simulations to better characterize the interaction between probing packets and the competing network traffic. We first construct a simple model to understand how competing traffic changes the probing packet gap for a single-hop network. The gap model shows that the initial probing gap is a critical parameter when using packet pairs to estimate available bandwidth. Based on this insight, we present two available bandwidth measurement techniques, the initial gap increasing (IGI) method and the packet transmission rate (PTR) method. We use extensive Internet measurements to show that these techniques estimate available bandwidth faster than existing techniques such as Pathload, with comparable accuracy. Finally, using both Internet measurements and ns simulations, we explore how the measurement accuracy of active probing is affected by factors such as the probing packet size, the length of probing packet train, and the competing traffic on links other than the tight link.     

Toward scalable admission control for VoIP networks

We present an overview of scalable admission control in IP networks. We introduce various approaches and discuss the mechanism and characteristics of each method. In particular, we argue that end-to-end measurement based admission control (EMBAC), which employs end-to-end on-demand probing, should be used for call admission control. Second, we consider use of EMBAC in VoIP networks. We present a new probability-based EMBAC scheme and show that its performance is close to the ideal method using virtual-trunk-based admission control. We also present a QoS allocation approach for selecting an admission threshold and dimensioning link capacities. A simple network design and evaluation results suggest that this QoS allocation approach is effective to adequately dimension a network, while satisfying end-to-end targets in terms of blocking probability and packet loss rate.     

An Investigation of Link Quality Assessment for Mobile Multi-hop and Multi-rate Wireless Networks

Wireless ad hoc networks will be an important component in future communication systems. The performance of wireless ad hoc networks can be improved by link quality-aware applications. Wireless link quality is dynamic in nature, especially in mobile scenarios. Therefore, accurate and fast packet delivery ratio estimation is a prerequisite to good performance in mobile, multi-hop and multi-rate wireless ad hoc networks. In this paper, we propose a novel packet delivery ratio estimation method that improves the accuracy and responsiveness of the packet delivery ratio estimation. The proposed link quality estimation components are implemented in a IEEE 802.11b/g test-bed. The experiment results show that the accuracy of the packet delivery ratio estimation can improve up to 50% in mobile scenarios without introducing overhead. We also show the end-to-end performance impact of this improved estimation on route selection using different routing metrics and configurations. The measurement results show that our packet delivery ratio method leads to better route selection in the form of increased end-to-end throughput compared to traditional methods, which respond slowly to the link dynamics.     

基于最小覆盖集的高精度链路丢包率测量方法

为降低链路丢包率测量过程中网络资源消耗,提高测量的精度,该文提出一种基于最小覆盖集的高精度链路丢包率测量方法。通过最小覆盖集测量方法有效降低路由矩阵的秩,从而减少测量路径数量;采用线性方程组求解和Gibbs采样相结合的方法,有效提高测量的准确度。仿真实验结果表明,该文提出的算法需要较少的端到端测量路径,同时具备更高的精度。     

Network tomography from measured end-to-end delay covariance

End-to-end measurement is a common tool for network performance diagnosis, primarily because it can reflect user experience and typically requires minimal support from intervening network elements. However, pinpointing the site of performance degradation from end-to-end measurements is a challenging problem. We show how end-to-end delay measurements of multicast traffic can be used to infer the under-lying logical multicast tree and the packet delay variance on each of its links. The method does not depend on cooperation from intervening network elements; multicast probing is bandwidth efficient. We establish desirable statistical properties of the estimator, namely consistency and asymptotic normality. We evaluate the approach through simulations, and analyze its failure modes and their probabilities.     

Rate control for streaming video over wireless

Rate control is an important issue in video streaming applications for both wired and wireless networks. A widely accepted rate control method in wired networks is TCP-friendly rate control (TFRC) (Floyd, 2000). It is equation-based rate control in which the TCP-friendly rate is determined as a function of packet loss rate, round-trip time, and packet size. TFRC assumes that packet loss in wired networks is primarily due to congestion, and as such is not applicable to wireless networks in which the main cause of packet loss is at the physical layer. In this article we review existing approaches to solve this problem. Then we propose multiple TFRC connections as an end-to-end rate control solution for wireless video streaming. We show that this approach not only avoids modifications to the network infrastructure or network protocol, but also results in full utilization of the wireless channel. NS-2 simulations, actual experiments over a 1/spl times/RTT CDMA wireless data network, and video streaming simulations using traces from the actual experiments are carried out to characterize the performance and show the efficiency of our proposed approach.     

QUORUM—Quality of Service in Wireless Mesh Networks

Wireless mesh networks (WMNs) can provide seamless broadband connectivity to network users with low setup and maintenance costs. To support next-generation applications with real-time requirements, however, these networks must provide improved quality of service guarantees. Current mesh protocols use techniques that fail to accurately predict the performance of end-to-end paths, and do not optimize performance based on knowledge of mesh network structures. In this paper, we propose QUORUM, a routing protocol optimized for WMNs that provides accurate QoS properties by correctly predicting delay and loss characteristics of data traffic. QUORUM integrates a novel end-to-end packet delay estimation mechanism with stability-aware routing policies, allowing it to more accurately follow QoS requirements while minimizing misbehavior of selfish nodes.     

Sequential Monte Carlo inference of internal delays innonstationary data networks

On-line, spatially localized information about internal network performance can greatly assist dynamic routing algorithms and traffic transmission protocols. However, it is impractical to measure network traffic at all points in the network. A promising alternative is to measure only at the edge of the network and infer internal behavior from these measurements. We concentrate on the estimation and localization of internal delays based on end-to-end delay measurements from a source to receivers. We propose a sequential Monte Carlo (SMC) procedure capable of tracking nonstationary network behavior and estimating time-varying, internal delay characteristics. Simulation experiments demonstrate the performance of the SMC approach     

基于线性规划的Internet端到端时延的估计

测量Internet端到端时延特征是研究Internet端到端分组行为的重要内容之一,它能够应用于QoS(Quality of Service),SLA(Service Level Agreement)的管理、拥塞控制算法研究等许多方面.常用的端到端时延测量方法大多依赖于GPS接收机或采用NTP协议来实现收发端时钟的同步,但由于GPS接收机价格较高不可能每台主机都能配备, NTP协议的精度不能满足要求。该文基于线性规划的方法估计收发时钟的频差、相对时钟偏差等参数,以获得端到端时延的估计。作者在几条不同的链路上进行了测试,结果表明该方法能有效消除收发时钟不同步的影响。     

System Level Design for Clustered Wireless Sensor Networks

We present a system level design methodology for clustered wireless sensor networks based on a semi-random communication protocol called SERAN, a mathematical model that allows to optimize the protocol parameters, and a network initialization and maintenance procedure. SERAN is a two-layer (routing and MAC) protocol. At both layers, SERAN combines a randomized and a deterministic approach. While the randomized component provides robustness over unreliable channels, the deterministic component avoids an explosion of packet collisions and allows our protocol to scale with network size. The combined result is a high reliability and major energy savings when dense clusters are used. Our solution is based on a mathematical model that characterizes performance accurately without resorting to extensive simulations. Thanks to this model, the user needs only to specify the application requirements in terms of end-to-end packet delay and packet loss probability, select the intended hardware platform, and the protocol parameters are set automatically to satisfy latency requirements and optimize for energy consumption.