Performance Analysis of Computer
Networks
(Winter 2011-12)
Textbooks
We will use the following textbook for this course:
- Probability, Statistics, and Random Processes For Electrical Engineering by Alberto Leon-Garcia, 3rd edition, Prentice Hall, 2008. ISBN: 0-13-601641-3.
We will also use important papers published in the research literature in computer networks to supplement the material from the textbook.
Syllabus
The course covers three broad techniques for the performance analysis of computer networks: queueing theory, simulation, and measurements. In the discussion of each mathematical technique and the underlying theories in the syllabus below, this course will also introduce students to a variety of principles, protocols and systems in computer networks through case studies and examples of applying these tools in engineering contexts.
- Review of probability theory with examples of applications in computer networks; review of random variables: the exponential random variable, the binomial random variable, the Zipf random variable and the Poisson random variable; joint probabilities of random variables; examples of applications in computer networks.
- Computer simulation methods; correct use of pseudo-random number generation; generating multiple pseudo-random streams; approaches to Monte Carlo methods; statistical analysis of simulated data; mean and variance estimation; the normal distribution; review of the Central Limit Theorem; estimating confidence intervals; the t distribution; computer methods for generating random variables; examples of applications in computer networks.
- Random processes; the exponential and the Poisson random processes; memoryless property; sum of Poisson processes; the independent increments property; Little's theorem; examples of applications in networking.
- Markov chains and Markov processes; transition probabilities and transition matrices; stationarity; simulation of Markov chains; numerical solution of Markov chains; examples from computer networks; theory versus simulation versus prototype experimentation: strengths and pitfalls of each.
- Introduction to queueing theory; M/M/1 queueing systems; distribution of delay and the number in the system; finite capacity systems; multi-server systems; examples of applications in computer networks.
- Introduction to network measurement techniques; review of classic tools based on ICMP, SNMP and traceroute; capacity estimation; available bandwidth estimation using packet dispersion techniques; direct and iterative probing using packet trains; topology inference and network tomography.
- Estimation of delay between arbitrary hosts; off-label use of DNS for delay estimation; Geo-location strategies based on multi-lateration and distance-delay correlation; available tools and their accuracy; techniques and challenges in network measurement.
- M/G/1 systems; the concept of residual service time; mean delay; non-preemptive priority queueing systems; other Markov queueing systems; multi-dimensional Markov chains; M/G/1 systems; a brief introduction to networks of queues and their analysis techniques and their limits in reliable performance analysis; Burke's theorem; examples from networking.
- An introduction to long-range dependent properties of network traffic; self-similarity and definitions; understanding heavy tails; Implications of long-range dependence in computer network design and traffic engineering; general remarks on fundamental principles of design and implementation; introduction to G/G/1 systems.
- Fundamental principles of design and implementation with case studies from router architecture design, traffic management strategies, and resource allocation policies; adherence to design principles versus after-the-fact performance analysis.
Grading Policy
The grading in the course is based on homework submissions, the mid-term examination and the final examination. The cumulative grade is based on the following:
- Homework problem assignments: 10%
- Homework projects: 15%
- Mid-term examination: 35%
- Final examination: 40%
Both your class rank in the exam scores and your class rank in the overall scores will be considered for the final grade.
Policy on homework assignments
Homeworks are always due at the beginning of the next class (6pm on Thursdays) after they are assigned. Homework solutions will be made available on the course web site soon after the time they are due, and therefore, homeworks submitted after the due date will not be accepted, and will be graded at 0 points. Homeworks should be delivered as a hardcopy to either the instructor or the teaching assistant. Typically, homeworks are collected during the class hours; if a student is unable to attend class, he/she should make alternate arrangements to deliver the homework to the instructor before the time it is due (e.g., by faxing the homework to the instructor, or sending the homework as an e-mail attachment to the teaching assistant).
Policy on exams
All exams in the course will be open-textbook. Use of other books or any other material, however, is not permissible. Use of calculators, cell phones, laptops or any other devices capable of computing are prohibited. The exams will cover material discussed in the lectures, homeworks or sections of the textbook given as reading assignments. For example, the exams may include questions on material covered in class lectures or homeworks but not specifically covered in the textbook. Similarly, the exams may include any material covered in a section of the textbook given as a reading assignment but not specifically covered in the lectures or homeworks.
Policy on Absences
Absence from examinations will be excused only under extraordinary circumstances such as medical or family emergencies. A missed examination without prior approval and without legitimate reasons will be graded at zero points. An absence will be excused only if the student is able to provide legitimate documentation (such as a physician's note). An absence from an examination with prior approval will require the student to take an alternate exam at a later time. Special examinations will not be held earlier or on later dates to accommodate, for example, flight schedules for overseas vacations.
Policy on Academic Honesty
Each student is expected to complete weekly assignments independently; it is not acceptable to copy another student's work or to copy solutions from any other source. Barring action on flagrant violations, an honor system will be assumed.
The following is a partial list of activities that will be considered to constitute academic dishonesty:
- Presenting the work of another person (fellow student or not) as your own.
- Cheating in an examination such as through conversations with other students, sharing textbooks, calculators or other materials with another student, using unauthorized books not approved by the instructor in an open book examination, or by inappropriate or unauthorized use of technology such as laptops and cell-phones during an examination.
- Using or attempting to use the work of another student or providing answers to other students.
- Failing to take reasonable measures to protect your work from use by other students in assignments, projects or examinations.
Penalties for academic dishonesty will be strictly enforced and will include a lowering of the grade or a failing grade in the course.