ELEN E9701 Scaling in Networks

Seminar Benefits

Professor Lazar

Applicable Degree Programs

Most courses 4000-level and above can be credited to all degree programs. All courses are subject to advisor approval.
Lecturer/Manager Professor Aurel A. Lazar
Class location: 253 S.W. Mudd
Office hours: Mondays, 4:00-6:00 AM EST
Office phone: +1 212 854 1747
Email address: aurel "at" ee.columbia.edu
Class Web Site: Offered by the COMET Group
Mailing list:
Teaching assistant: ---
TA office phone: ---
TA Email address: ---
TA office hours: ---
Day and time: Mondays, 2:00 - 4:00 AM
Credits for course: 3
Prerequisites: A graduate level course in computer communication networks (e.g., ELEN E6761) or a course in stochastic processes (e.g., ELEN E6711), or the instructor's approval.
Description: This research seminar will explore evolutionary models of the Internet with a focus on scalability. We will consider random graph models of the Internet and the Web and analyze their growth and evolution. In large part we will read and critique research papers that were published outside the EE/CS literature. This will give breadth but also depth to empirical observations that not only apply to the Internet and the Web, but also to a wide range of networks arising in social sciences, biology and economics. Strong student participation in class is encouraged.

The topological structure of networks arising in communications, biology, social sciences and economics. Structural characteristics of evolving networks. Topological invariants obtained through empirical investigations: power laws, clustering and the small world phenomena. Classical random networks and elements of random graph theory. Percolation theory. Small world networks and their properties. Scale-free networks and their characteristics. Models of evolving networks. Error and attack tolerance, and the robustness of the Internet.

Required text(s): The seminar will be based on research papers that will be posted on the web.
Reference text(s): Balachander Krishnamurthy and Jennifer Rexford, Web Protocols and Practice, Addison-Wesley, New York, 2001.
Bela Bollobas, Random Graphs, Second Edition, Cambridge University Press, 2001.

Homework(s): ---
Paper(s): Students are expected to submit a review paper on one of the following scalability topics on communication networks: scalability of switching systems, network protocols, routing and qos architectures, wireless networks, content delivery networks, signaling architectures, management architectures, peer-to-peer and other service architectures. Each student is also expected to present one of the research papers to be discussed in class. Early sign up and choice of a research paper(s) is highly recommended.

Students are expected to complete during the course of the semester either a programming project that focuses on graph invariants arising in modeling the architecture of the Internet or a theoretical analysis on the implications of graph invariants on the architecture of the Internet.

Midterm exam: See "Paper(s)". Submission date: Monday, October 29, 2001, 2:00 PM.
Final exam: See "Project(s)". Submission date: Monday, December 10, 2001, 2:00 PM.
Grading: Class presentation and participation 1/3, midterm 1/3, final 1/3.
Hardware requirements: Access to a PC or workstation. Linux, Windows and Apple Power PC OS are strongly preferred.
Software requirements: Access to the WWW and a Java platform.
Homework submission: ---