Technical Summary
ABSTRACT:
This study addressed performance
analysis tools and effective protocols for congestion control and resource management in
computer networks. In the initial phase of the work, fundamental properties of distributed
algorithms for congestion control were our primary focus. We had some success with a
two-dimensional Brownian motion model for a system with adaptive control. With the
experience gained from this study, the project branched into (i) network traffic
models, and (ii) algorithms for congestion-control and resource-management. The
latter were developed and evaluated using the former. We have also archived and
distributed a number of network traffic traces.
A. Workload Studies
Time series models for Internet traffic.
In (Basu, Mukherjee and Klivansky 1995), we develop a library of parametric traffic models for data traffic sequences from two campus FDDI rings, an Ethernet, two entry/exit points of the NSFNET, and sub-sequences belonging to popular TCP port numbers. Appropriately differenced sequences of these traces admit Auto-Regressive-Moving-Average (ARMA) models with non-Gaussian errors. Parameter estimation, forecasting tail percentiles, and synthetic generation of traffic sequences are addressed. The models are intended to be used as part of simulation studies of network protocols. The forecasting algorithm has potential application in dynamic bandwidth/buffer management.
On long-range dependence in NSFNET traffic.
In (Klivansky, Mukherjee and Song 1994), we show the presence of long-range dependence in multiplexed traffic over NSFNET core switches, and statistically infer the factors contributing to it. Over the NSFNET, the number of active conversations are typically an order of magnitude larger than campus level networks; yet traffic appears to have the burstiness properties of long-memory processes. The traffic data was collected from seven NSFNET core switches (CNSS's) distributed across the US. Investigation of the underlying processes for a subset of traffic created by TCP applications indicates that the (heavy-tailed) joint distribution of TCP conversation sizes and conversation transmission rates are the key factors contributing to long-range dependence. Since these distributions are primarily application-level characteristics and to a certain extent network independent, long-range dependence is likely to be present in highly-multiplexed data networks that are running current TCP applications.
Properties of Internet round-trip delays.
In (Mukherjee 1994), we study the properties of round-trip delay and packet loss over several long and short paths for an extended period of time (one and a half years). The distribution of delay appears to consistently fit the Gamma distribution. The correlation between round-trip delay and packet loss is, however, low over the Internet, especially for low delays.
Survey of traffic models.
In (Adas 96b), A. Adas (then Ph.D. student, currently at Rockwell Int'l) surveys a broad range of network traffic models from the literature.
B. Algorithms for congestion-control/resource-management
Intrinsic properties of distributed, adaptive, feedback control algorithms.
Queues with feedback control are typically difficult to analyze. In (Mukherjee and Strikwerda 1994), we use a Fokker-Planck approximation to characterize stability and fairness issues in distributed feedback control vis-a-vis the system parameters (e.g., feedback delay and feedback algorithm used). Several conservation laws governing this system are given in the journal version of the paper. They indicate fundamental limits of feedback control in a noisy environment.
An architecture for providing guarantees on quality of service requirements for variable bit-rate video.
Network support for variable bit-rate video needs to consider (i) properties of workload induced (e.g., significant auto-correlations into far lags and heterogeneous marginal distributions), and (ii) application specific bounds on delay-jitter and statistical cell-loss probabilities. In (Adas and Mukherjee 1996), we present a quality-of-service solution for such traffic at each multiplexing point in a network. Heterogeneity in both offered workload and quality-of-service requirements are addressed.
A per-virtual-circuit framing structure and a pseudo earliest-due-date cell dispatcher are introduced to provide guaranteed delay-jitter bounds. Heterogeneous jitter-bounds are supported through software controlled frame-sizes which may be independently set for each virtual-circuit. The framing structure is a generalization of per-link framing introduced by Golestani. The proposed framing structure (i) eliminates correcting for phase mismatches between incoming frames and outgoing frames necessary in per-link framing, (ii) results in significant reduction in end-to-end delay bound and multiplexor buffer requirements, and (iii) allows for flexible specification and implementation of delay-jitter bounds.
Strong auto-correlations typically seen in video traffic make equivalent bandwidth computations for heterogeneous cell-loss bounds intractable. To address this, the framing strategy is combined with an active cell-discard mechanism with prioritized cell-dropping, the latter utilizing the history of dropped cells and target cell-loss bounds for each virtual circuit. Upper bounds on the equivalent bandwidth needed to support a given workload with a target quality of service are also given. .These are validated through numerical and simulation results from variable bit-rate MPEG-I video traces. The effect of slowly decaying auto-correlation functions on queue length statistics is studied in (Adas and Mukherjee 1995)
Optimal congestion control at a network multiplexor.
In (Mukherjee and Sengupta 1997), we give an algorithm for optimally controlling upstream data traffic at a network multiplexor. The algorithm requires (i) a protocol between adjacent routers to communicate rate assignments periodically, (ii) optimal rate-assignment computations that are autonomously carried out at each individual router for each of its output links, and (iii) time-series based transfer-function models that predict future departures from each upstream point from a history of previous assigned rates to it, and the corresponding departures that were observed. A number of such transfer-function models are necessary, and their precise formulation is dictated by the desired optimization formulation. The modeling method admits feedback delay. However, the prediction accuracy can be expected to decay with the magnitude of the delay.
Dynamic bandwidth reservation for variable bit-rate video.
In (Adas 1996a), A. Adas proposes a dynamic bandwidth allocation strategy to support variable bit rate (VBR) video traffic, and evaluates it assuming a Renegotiation Constant-Bit-Rate (RCBR) network service model. The algorithm uses adaptive least mean square (LMS) linear prediction because the latter does not require prior knowledge of traffic statistics, nor does it assume stationarity in data. By reserving bandwidth equal to the predicted value, only the prediction errors need to be buffered. Because the errors are almost white noise, small buffer size, high utilization, and small delay are achieved. Results for one-frame ahead prediction and one-group-of-pictures ahead prediction show that for the same expected cell loss, buffer size is reduced by a factor 15-160 and network utilization is increased by 190%-300% as compared to a fixed service rate. Results also indicate that even when renegotiations are slowed down to the order of tens of seconds, the queue size is reduced by a factor of 16-30.
A two-level traffic shaping and scheduling algorithm for flow control in high speed networks.
We propose a two-level flow control architecture for flow control in high speed networks. At the lower level is a generalized Virtual Clock scheduler (at each switch) that schedules bursty traffic with a parameterized dynamic priority algorithm (Mukherjee, Landweber and Faber 1992). At the higher level is an adaptive feedback control algorithm which shapes traffic as a function of network load by dynamically adjusting the time interval over which a transmitter maintains a pre-specified average rate (Faber, Landweber and Mukherjee 1992).
On designing a wide-area optical network.
Design principles for next generation optical wide-area networks is explored in (B. Mukherjee, Ramaswamy, Banerjee and A. Mukherjee 1996).These employ wavelength-division multiplexing (WDM), and are targeted to nationwide coverage. Algorithms are developed so that the WDM-based network architecture will (i) provide a high aggregate system capacity due to spatial reuse of wavelengths, and (ii) support a large and scalable number of users, given a limited number of wavelengths. The objective is to investigate the overall design, analysis, upgradability, and optimization of a nationwide WDM network consistent with device capabilities, e.g., aimed at upgrading the current NSFNET or its anticipated follow-ons. We illustrate our approaches by employing experimental traffic statistics collected from NSFNET.
C. Interaction of Error Recovery Protocols and Congestion Control Protocols
A proof of quasi-independence of sliding window flow control and go-back-n error recovery under independent packet errors
A quasi-independence result holds for the go-back-n automatic repeat request (ARQ) protocol and the sliding window flow control protocol if packet errors are independent. The result is independent of the magnitude of the packet error probability or the cost of an error. A parallel result for the selective repeat ARQ protocol, however, does not appear to hold. See (Mukherjee 1996).
The results from (Adas
and Mukherjee 1995) and (Klivansky, Mukherjee and Song 1995) were
presented in a hot topics panel discussion in SIGMETRICS 1995.
Publications
- Adas, A. "Supporting real time
VBR video using dynamic reservation based on linear prediction,'' Proc. IEEE Infocom,
San Francisco, 1476-1483, March 1996. (Extended
version -- pdf -- 261KB.)
- Adas, A. "Traffic models in
broadband networks,'' IEEE Communications Magazine, July 1997. (postscript -- 289KB. )
- Adas, A. and A. Mukherjee,
"Providing guaranteed quality of service for variable bit-rate video at a
multiplexor,'' Performance Evaluation, (38), 1, pp 45-65,
September 1999 . (Extended version -- pdf -- 332KB.
)
- Adas, A. and A. Mukherjee, "On resource management and
QoS guarantees for long range dependent traffic,'' Proc. IEEE Infocom, 779-787,
Boston, April 1995. (Extended
version .ps.Z.)
- Basu, S., A. Mukherjee and S. M.
Klivansky, ``Time-series models of Internet traffic,'' Proc. IEEE Infocom, San
Francisco, 603-610, March 1996. (Extended
version -- pdf -- 324KB.)
- Erramilli, A., D. P. Heyman, T. V.
Lakhsman, A. Mukherjee, O. Narayan, S. Q. Li and W. Willinger, "Performance impacts
of self-similarity in network traffic,'' Hot Topics Panel, SIGMETRICS 1995, Ottawa,
May 1995.
- Faber, T., L.H. Landweber and A.
Mukherjee, "Dynamic time windows: packet admission control with feedback,'' Proc.
ACM Sigcomm, pp 124-135, Baltimore, August 1992. (pdf -- 1341KB)
- Klivansky S., A. Mukherjee and C. Song,
"On long-range dependence in NSFNET traffic,'' 7th IEEE LAN/MAN Workshop, Marathon
FL, March 1995. (Extended version -- pdf--
480KB.)
- Klivansky S., and A. Mukherjee,
"Disclosure on traffic models for performance analysis of a class of wide-area
network problems," preprint, February 1995. (pdf --314KB.)
- Mukherjee, A., "On the dynamics and
significance low frequency components of Internet load,'' Journal of Internetworking:
Practice and Experience, 5, (4), 1994, 163-205.
- Mukherjee, A., ``A proof of
quasi-independence of sliding window flow control and Go-Back-N error recovery under
independent packet errors,'' Computer Networks and ISDN Systems, April 1996. (pdf -- 253KB.)
- Mukherjee, A., L.H. Landweber and T.
Faber, "Dynamic time windows and generalized virtual clock: combined
closed-loop/open-loop congestion control,'' Proc. IEEE Infocom, Florence, pp
322-332, May 1992.
- Mukherjee, B, S. Ramaswamy, D. Banerjee
and A. Mukherjee, "Some principles for designing a wide-area optical network,'' ACM/IEEE
Trans. Networking, 4, (5), 1996, 684-696. Preliminary version: Proc. IEEE
Infocom, Toronto, 1994.
- Mukherjee, A. and B. Sengupta,
"Optimal congestion control at a network multiplexor," in preparation.
- Mukherjee, A. and J.C. Strikwerda,
"Analysis of dynamic congestion control protocols --- a Fokker-Planck
approximation,'' Journal of High Speed Networks, 3, (1), 1994, 31-56.
Preliminary version: Proc. ACM Sigcomm, Zurich, pp. 159-169, September 1991.(pdf -Sigcomm-version -- 160KB)
Other Related Reports
- Mukherjee, A., "Traffic signatures for network
engineering," preprint, March 1996.
Article (pdf) -- 294KB; Transparencies (pdf) -- 210KB.
- Kilvansky, S., and A. Mukherjee, "The NSFNET simulation platform," preprint, August 1995. (pdf -- 561KB.)
A Wide Area Simulation Platform
With the help of traffic traces, we developed an environment that reproduced temporal and spatial correlations in packet traffic at each Core Nodal Sub-Subsystem (C-NSS) of the NSFNET. The workload for this environment was derived from
- signatures of different applications on the NSFNET backbone (Klivansky and Mukherjee 1995), and
- spatial information on [Origin, Destination] traffic matrix.
The former was extracted from our traffic measurements on seven C-NSS's. The latter was derived from summary statistics generated by Merit Corporation's nnstat program every 15 minutes. (The NSF/Merit partnership provided us with four months worth of data during the period January 1992-April 1992.) While the 15-minute granularity was a little coarse, the platform showed one way of providing a realistic environment for studying resource management algorithms. The spatial data was used in the wide-area optical network design above.
Graduate Students Who Worked On This Project
- A. Adas, Ph.D. student. Graduated in May 1997. First job: Rockwell Int'l.
- S. M. Klivansky, MS student. First job: Sun Microsystems.
Questions and Comments: am_knoltex@yahoo.com
© A. Mukherjee, 1997-1999