Small World and Power Law Phenomena in Networks (original) (raw)
CMPSCI 691S: Scaling, Power Laws, and the Small World Phenomena in Networks
Instructor: Prof. Don Towsley
Time: Tuesdays, 5:10 - 7:10
Location: ELab 325
Amherst, Mass. 01003-4610
(413) 545-0207 (office)
(413) 545-1249 (fax)
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
Power Laws in Control
Power Laws in Networks
The Small World Phenomena
Non-linear Dynamical Systems and Networks
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
- M.E. Crovella, A. Bestavros. "Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes," IEEE/ACM Transactions on Networking, 5(6):835--846, December 1997. (presenter B. Liu)
- A. Erramilli, O. Narayan, W. Willinger. "Experimental Queuing Analysis with Long-Range Dependent Packet Traffic," IEEE/ACM Transactions on Networking, 4(2):209-223, April 1996. (Presenter J. Padhye) 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
- B.K. Ryu, A. Elwalid. "The Importance of Long-range Dependence of VBR Video Traffic in ATM Traffic Engineering: Myths and realities," _ACM Computer Communication Review,_26:3-14, Oct. 1996. (presenter Z. Koren)
- M. Grossglauser, J. Bolot. "On the Relevance of Long Range Dependence in Network Traffic," IEEE/ACM Transactions on Networking, 1998. (Presenter D. Figueiredo.)
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
- A. Feldmann, A. C. Gilbert, W. Willinger. "Dynamics of IP Traffic: A Study of the Role of Variability and the Impact of Control,"ACM Computer Communication Review, Sept. 1999. (Presenter J. Shapiro)
- T. Tuan, K. Park. "Multiple timescale congestion control for selfsimilar network traffic," Perfoormance Evalaution, 1999. (presenter B. Liu.)
Week 6
- M. Krunz, A. Makowski. "Modeling video traffic using M/G/infinity input processes: A compromise between Markovian and LRD models," IEEE JSAC 16(5):733-748, June 1888. (presenter P. Ji)
- Z. Liu, P. Nain, D. Towsley, Z.-L. Zhang. "Asymptotic behavior of a multiplexer fed by a long-range dependent process," (Presenter D. Towsley.)
Power Laws in Control
Week 7
- J.M. Carlson, J. Doyle. "Highly optimized tolerance: A mechanism for power laws in designed systems,"Phys. Rev. E 60, 1412, (1999) (Presenter W. Gong.)
- J.M. Carlson, J. Doyle. "Highly optimized tolerance and generalized source coding", to appear in Phys. Rev. Letters. (presenter M. Adler)
- J.M. Carlson, J. Doyle. "Highly optimized tolerance: Robustness and design" submitted to Phys. Rev. Letters.
Power Laws in Networks
Week 8
- J. Chuang, M. Sirbu. "Pricing multicast communications: A cost-based approach," ( .ps.gz,.pdf)Proc. INET'98, 1998. (Presenter J. Shapiro)
- G. Phillips, S. Shenker, H. Tangmunarunkit. Scaling of multicast trees: comments on the Chuang-Sirbu scaling law," Proc. SIGCOMM'99, Sept. 1999.
Week 9
- M. Faloutsos, P. Faloutsos, C. Faloutsos. "On power law relationships of the Internet topology," Proc. SIGCOMM'99, Sept. 1999. (presenter D. Figueiredo.)
- E. Zegura, K. Calvert, M.J. Donahoo. "A quantitative comparison of graph-based models for Internet topology,"IEEE/ACM Trans. on Networking, 5(6), Dec. 1997. (presenter B. Wang.)
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
- D. Gibson, J. Kleinberg. "Inferring Web Communities from link topology," Proc. 9th ACM Conf. on Hypertext and Hypermedia, 1998. (Presenter X. Zhang) 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
- The IBM Clever project. http://www.almaden.ibm.com/cs/k53/clever.html
- The Xerox Parc Internet Ecologies Area. http://www.parc.xerox.com/istl/groups/iea/
Nonlinear Dynamical Systems
Week 12
- A. Veres, M. Boda. "The Chaotic nature of TCP congestion control," IEEE INFOCOM'00, March 2000. (Presenter C. Hollot)