CMPSCI 691S: Scaling, Power Laws, and the Small World Phenomena in Networks
-
Time: Tuesdays, 5:10 - 7:10
-
Location: ELab 325
-
Computer Science Department
-
University
of Massachusetts
-
Amherst, Mass. 01003-4610
-
(413) 545-0207 (office)
-
(413) 545-1249 (fax)
towsley@cs.umass.edu
Seminar Description
Scaling phenomena permeate modern communication networks. For example,
there is considerable data to support the hypothesis that network traffic
exhibits multi-scalar behavior, with correlations at multiple timescales.
There is even evidence that traffic may be self-similar and fractal in
nature. This can be explained by assuming that network workloads are described
by power laws. For example, there is considerable evidence that file sizes
and web object sizes are described by distributions which decay according
to a power law. In other words, if X is the size of the object in bytes,
then P[X>x] = c x^{-a}. This may not seem unusual until one realizes that
all network models and simulations prior to the early 90s were based on
the assumption that P[X>x] = c e^-{ax}.
In this seminar, we will explore different manifestations of scaling
phenomena and power laws. Not only do they arise in the context of network
traffic characterization, but also in the description of network topologies.
This will lead naturally to the "small world" phenomena that has so recently
been in the press. During the first third or so of the semester we will
focus on scaling in traffic models. We will then look at a very interesting
set of papers on control mechanisms that produce power laws. One consequence
of the theory in these papers is an explanation of the multiscalr traffic
behavior.
The remainder of the course will cover power laws in network topologies,
culminating in the small world phenomena. we will explore what it is how
it is poorly explained by traditional graph models, and examine preliminary
models explaining the phenomena.
In the final weeks of the course, if time permits, we will shift to
an entirely diferent topic, namely how to model networks as nonlinear dynamical
systems.
Course Prerequisites
A course on networking, a course on probability theory, and reasonable
mathematical maturity. Useful references include:
-
S.M. Ross. Stochastic Processes, Wiley, 1983. This is
an accessible reference to probability theory and stochastic processes.
-
C. Chatfield. The Analysis of Time Series: an Introduction, 4th
edition, Chapman & Hall, 1989. An accessible reference on time series
analysis. It explains what ARMA and ARIMA processes are.
-
J. Beran. Statistics for Long-Memory Processes. Chapman Hall 1994.
Describes what long range dependence and self-similarity are. Presents
many of the tests for testing for LRD that we will encounter during the
course.
Course Requirements
This course can be taken for one credit or three credits. For one credit,
students are expected to attend the course and present one paper. For three
credits, students are expected to either turn in detailed critical summaries
of all of the papers or to propose and complete a course project.
Reading List and Schedule
Scaling Phenomena in Network Traffic
Week 1
-
W. Leland, M. Taqqu, W. Willinger, D. Wilson. "On
the Self-Similar Nature of Ethernet Traffic (Extended Version)," IEEE/ACM
Transactions on Networking, 2(1):1-15, February 1994. (Presenter D.
Towsley.)
-
V. Paxson, S. Floyd. "Wide-Area
Traffic: The Failure of Poisson Modeling," IEEE/ACM Transactions
on Networking, 3(3):226-244, June 1995. (Presenter T. Bu)
Week 2
Some other papers that might be of interest related to the Crovella, Bestavros
paper include.
-
P. Barford, A. Bestavros, A. Bradley, and M. E. Crovella, "Changes
in Web Client Access Patterns: Characteristics and Caching Implications,"
in World Wide Web, Special Issue on Characterization and Performance Evaluation,
Vol. 2, pp. 15-28, 1999. This paper updates the study by examining web
traffic characteristics in 1998. Briefly, distributions of object sizes
remain heavy-tailed but with different parameter values.
-
K. Park, G. Kim, M. E. Crovella, "On
the Effect of Traffic Self-similarity on Network Performance," Proceedings
of the SPIE International Conference on Performance and Control of Network
Systems, November, 1997. This paper examines the effects that different
transport protocols can have on traffic characteristics when fetching WWW
objects whose lengths are characterized by a heavy tail distribution. In
the case of TCP, the congestion control algorithm has the effect of reducing
the long range dependence. Nevertheless, simulations show the resulting
network traffic to still be LRD.
Week 3
Week 4
-
P. Abry, D. Veitch. "Wavelet
Analysis of Long-Range Dependence Traffic," IEEE Transactions on
Information Theory, 44(1):2-15, January, 1998. (Presenter V. Misra.)
-
V. Misra, W. Gong. "A
Hierarchical Model for Teletraffic", Proceedings of 37th IEEE Conference
of Decision and Control, December 1998, Tempa, Fl. (Presenter V. Misra)
Week 5
Week 6
Power Laws in Control
Week 7
Power Laws in Networks
Week 8
Week 9
Small World Phenomena
Week 10
-
D. Watts, S. Strogatz. "Collective dynamics of small-world networks," Nature,
393:440-442, 1998. (Presenter R. Datta)
-
J. Kleinberg , R. Kumar, P. Raghavan, S. Rajagopalan, A.S. Tomkins. "The
WEB as a graph: measurements, models, and methods," Intntl. Conf.
on Combinatorics and Computing, 1999. (presenter B. Wang.)
Week 11
Some web sites that may be of interest in the context of small worlds,
power laws in graphs, and graph models of the web include
Nonlinear Dynamical Systems
Week 12
-
A. Veres, M. Boda. "The Chaotic nature of TCP congestion control,"
IEEE INFOCOM'00, March 2000. (Presenter C. Hollot)