Detecting shared congestion of flows via end-to-end measurement

Current Internet congestion control protocols operate independently on a per-flow basis. Recent work has demonstrated that cooperative congestion control strategies between flows can improve performance for a variety of applications, ranging from aggregated TCP transmissions to multiple-sender multicast applications. However, in order for this cooperation to be effective, one must first identify the flows that are congested at the same set of resources. We present techniques based on loss or delay observations at end hosts to infer whether or not two flows experiencing congestion are congested at the same network resources. Our novel result is that such detection can be achieved for unicast flows, but the techniques can also be applied to multicast flows. We validate these techniques via queueing analysis, simulation and experimentation within the Internet. In addition, we demonstrate preliminary simulation results that show that the delay-based technique can determine whether two TCP flows are congested at the same set of resources. We also propose metrics that can be used as a measure of the amount of congestion sharing between two flows     

Distributed routing with on-line marginal delay estimation

A procedure is presented for estimating online marginal packet delays through links with respect to link flows without making the standard assumptions (exponentially distributed packet lengths, Poisson arrival processes). This procedure is based on a technique known as perturbation analysis. No knowledge of network parameters (arrival rates, link capacities) is required. This is used in the context of a minimum delay distributed routing algorithm for real-time implementation. Experimental results are included to investigate the effect of the algorithm step-size and observation period parameters, demonstrate the adaptivity of the approach, and compare it to well-known analytical approximation     

Measurement and Classification of Out-of-Sequence Packets in a Tier-1 IP Backbone

We present a classification methodology and a measurement study for out-of-sequence packets in TCP connections going over the Sprint IP backbone. Out-of-sequence packets can result from many events including loss, looping, reordering, or duplication in the network. It is important to quantify and understand the causes of such out-of-sequence packets since it is an indicator of the performance of a TCP connection, and the quality of its end-end path. Our study is based on passively observed packets from a point inside a large backbone network-as opposed to actively sending and measuring end-end probe traffic at the sender or receiver. A new methodology is thus required to infer the causes of a connection's out-of-sequence packets using only measurements taken in the "middle" of the connection's end-end path. We describe techniques that classify observed out-of-sequence behavior based only on the previously and subsequently-observed packets within a connection and knowledge of how TCP behaves. We analyze numerous several-hour packet-level traces from a set of OC-12 and OC-48 links for tens of millions connections generated in nearly 7600 unique ASes. We show that using our techniques, it is possible to classify almost all out-of-sequence packets in our traces and that we can quantify the uncertainty in our classification. Our measurements show a relatively consistent rate of out-of-sequence packets of approximately 4%. We observe that a majority of out-of-sequence packets are retransmissions, with a smaller percentage resulting from in-network reordering     

Supporting stored video: reducing rate variability and end-to-endresource requirements through optimal smoothing

Variable-bit-rate (VBR) compressed video can exhibit significant multiple-time-scale bit-rate variability. In this paper we consider the transmission of stored video from a server to a client across a network, and explore how the client buffer space can be used most effectively toward reducing the variability of the transmitted bit rate. Two basic results are presented. First, we show how to achieve the greatest possible reduction in rate variability when sending stored video to a client with given buffer size. We formally establish the optimality of our approach and illustrate its performance over a set of long MPEG-1 encoded video traces. Second, we evaluate the impact of optimal smoothing on the network resources needed for video transport, under two network service models: deterministic guaranteed service (Chang 1994; Wrege et al. 1996) and renegotiated constant-bit-rate (RCBR) service (Grossglauser et al. 1997). Under both models, the impact of optimal smoothing is dramatic     

Announced Arrival Random Access Protocols

In this paper we propose and evaluate several protocols for a random access channel. The channel is divided into a control subchannel which is used to inform all users of the approximate times of arrival of new packets and a data subchannel which is used to transmit the data. Packets arriving at different users at approximately the same time may cause a collision on the control subchannel. Such collisions are resolved on the data subchannel by a collision resolution algorithm. Eight protocols that differ in the feedback available on both channels and the time that the feedback is available are described and evaluated. The expected delay of each protocol is determined by modeling the system as a slotted concentrator. Comparisons are made among the protocols described and analyzed in this paper and between these protocols and other protocols that have been studied previously.     

The Analysis of a Statistical Multiplexer with Nonindependent Arrivals and Errors

Most stochastic models for discrete time statistical multiplexers make the assumption that 1) arrivals are governed by a Bernoulli process and that 2) transmission errors or multiplexer failures are described by an independent error process. We study a multiplexer operating in a two state Markovian environment in which each state is characterized by its own Bernoulli arrival process and independent error process. We derive the probability generating function for the queue length distribution for such a system. We also consider two special cases of this model. One referred to as the saturated arrival model corresponds to a system in which during one of the two states, the saturated state, at least one arrival occurs during each discrete time unit. The other model, the breakdown model, corresponds to a system in which during one of the two states, the breakdown state, the multiplexer is inoperative. For both models, we generalize the analysis to cases in which the durations of the saturated state and breakdown state may take on values described by arbitrary distributions. Finally, we study the effects of different arrival processes and error processes on queue length behavior.     

Proxy-assisted techniques for delivering continuous multimedia streams

We present a proxy-assisted video delivery architecture that can simultaneously reduce the resources requirements at the central server and the service latency experienced by clients (i.e., end users). Under the proposed video delivery architecture, we develop and analyze two novel proxy-assisted video streaming techniques for on-demand delivery of video objects to a large number of clients. By taking advantage of the resources available at the proxy servers, these techniques not only significantly reduce the central server and network resource requirements, but are also capable of providing near-instantaneous service to a large number of clients. We optimize the performance of our video streaming architecture by carefully selecting video delivery techniques for videos of various popularity and intelligently allocating resources between proxy servers and the central server. Through empirical studies, we demonstrate the efficacy of the proposed proxy-assisted video streaming techniques.     

Parity-based loss recovery for reliable multicast transmission

We investigate how forward error correction (FEC) can be combined with automatic repeat request (ARQ) to achieve scalable reliable multicast transmission. We consider the two scenarios where FEC is introduced as a transparent layer underneath a reliable multicast layer that uses ARQ, and where FEC and ARQ are both integrated into a single layer that uses the retransmission of parity data to recover from the loss of original data packets. To evaluate the performance improvements due to FEC, we consider different loss rates and different types of loss behavior (spatially or temporally correlated loss, homogeneous or heterogeneous loss) for up to 10⁶ receivers. Our results show that introducing FEC as a transparent layer below ARQ can improve multicast transmission efficiency and scalability. However, there are substantial additional improvements when FEC and ARQ are integrated     

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     

Burst reduction properties of rate-control throttles: departure process

In this paper we study the departure processes of two rate-control throttles: the token bank and the leaky bucket. Using sample path methods and the notion of majorization, we analyze the effect that parameters such as the token buffer capacity and token generation rate have on the vector of interdeparture times. In the transient case, we establish the monotonicity of the burst reduction in the sense of the majorization. In the case that the departure process converges in coupling to a stationary and ergodic process, the transient comparison results allow us to establish the monotonicity of the stationary interdeparture times in the sense of the convex ordering. Comparisons between the two flow control schemes are also established when appropriate.The work of this author was supported in part by the CEC DG XIII under the ESPRIT BRA grant QMIPS.The work of this author was supported in part by the National Science Foundation under grants ASC 88-8802764 and NCR-9116183.