Tags: view all tags

Computer Network Performance

Prof. Novella Bartolini

Grades and registrations

First midterm results available here: MidtermGrades1

Second midterm results available here: SecondMidtermGrades

Results of the written exam of June 18, 2018: FirstAnnGrades

Results of the written exam of June 28, 2018: SecondAnnGrades

Results of the written exam of September 18, 2018: SeptemberGrades

Exams and office hours

Students who did not register for a project/paper presentation yet, are encouraged to do so for the exam session that will be held in September.

Extraordinary exam appeal will be held on November 7, 2018.

Registration is mandatory, please use this registration page.

Thesis opportunities

If you are interested in doing your thesis in any field related to computer network performance, algorithms and protocols,

here you can find a (non exhaustive) list of opportunities: thesis opportunities.

These thesis will potentially open the path to future research collaborations, research contracts and PhD studies, while giving you a perspective on new challenging topics in future technologies.

Lessons

Day	Topics covered
February 27, 2018	All lessons cancelled due to adverse weather conditions
March 1, 2018	Introduction to the study of performance of computer systems. Motivating examples. Single server network (interarrival time, service time, service rate). Performance metrics: Response time, Waiting time, Population. Stability condition. From textbook: pages 3-16 + ex 2.1.
March 6, 2018	Open and closed queueing networks. Performance metrics: throughput and utilization, slowdown. The utilization law. Interactive and batch closed systems. From textbook: pages 16-25 + ex 2.2.
March 8, 2018	Probability review: Sample space, events and related probability. Conditional probability. Independent events. Law of total probability, Bayes law. Discrete and continuous random variables. Probability mass and cumulative distribution function of discrete random variables. Common discrete distributions: Bernoulli, Binomial, Geometric and Poisson. Probability density and cumulative distribution function of continuous random variables. Common continuous distributions: uniform and exponential. Expectation and variance. From textbook: pages 31-46 + ex 3.1, 3.2. Assignment: ex 3.5.
March 13, 2018	Probability review cont.d: Joint probabilities and independence. Probabilities and expectation via conditioning. Linearity of expectation (end of review). Time average and ensemble average (skimmed). Ergodic system properties. Little's Law for open and closed systems. Proof of Little's law for open systems. From textbook: pages 47-50, 53-55, 84-90, 95-99 + ex 3.5, 6.1.
March 15, 2018	Application of Little's Law to a whole system or to parts of it. Little's law for time in queues. Utilization law. Little's law for multiple classes of arrivals. Little's law for queues with limited buffer size. Forced flow law. Service demand and bottleneck law. From textbook: pages 100-110 + ex 6.5. Assignment: ex 6.2, 6.3, 6.4, 6.6, 6.7.
March 20, 2018	Review of operational laws. Introduction to project topics. Slides available. From textbook: ex 6.2, 6.3, 6.4.
March 22, 2018	Introduction to project topics. Boolean Network Tomography. k-identifiability and bounds. Slides available (same file of previous lesson).
March 27, 2018	Review of operational laws. Asymptotic bounds for closed systems. Modification analysis for closed systems. From textbook: pages 114-122. Assignment: ex 7.2, 7.3, 7.4, 7.5.
April 2, 2018	Easter vacation
April 5, 2018	Review of modification analysis. Stochastic processes: examples. Definition of Markov chain. From textbook: pages 122, 129-131 + ex 7.2, 7.3.
April 10, 2018	Stochastic processes and properties of Markov chains. Discrete Time Markov Chains (DTMC). Examples: repair facility problem, umbrella problem, program analysis problem, admission control based on threshold, admission control based on histeresis cycle. n-step transition probability and Chapman-Kolmogoroff equations. Limiting distribution and stationary distribution for a finite state DTMC. From textbook: pages 129 - 136.
April 12, 2018	Equivalence of limiting and stationary distribution. Infinite state DTMCs. How to solve stationary equations in infinite-state DTMCs. Stationary equations and flow balance equations. From textbook: pages 136-145, 168-170 (par 9.6) + ex 8.1, 8.2, 8.3. Assignment: ex 8.6.
April 17, 2018	Analysis of a DTMC representing a queue with a threshold based service discipline. Conditions for existence of the limiting distributions in finite-state DTMC. Definition of period in a DTMC. Aperiodicity. Irreducibility. Relationship between time recurrence and irreducibility in finite-state DTMCs. From textbook: pages 148 - 155 + ex 8.6.
April 19, 2018	Infinite-state DTMCs. Ergodicity and conditions of existence of the limiting distribution. Recurrent and transient states. Irreducibility and time recurrency in infinite-state DTMCs. Limiting probabilities interpreted as rates, equivalence of flow balance and stationary equations. The Google PageRank algorithm: how to rank web pages by means of a DTMC. Continuous Time Markov Chains. Poisson distribution of events, exponential interarrival times. Review of exponential distribution: memoryless property. Study of the M/M/1/inf queue: flow balance equations, utilization, population, throughput, response time, queue population. From textbook: pages 155 -160, 164 - 166, 168 - 170, 190 - 195, 206 - 207 + 213 - 216, 225 - 226, 229 - 234, 236 - 239 + ex 9.10.
April 24, 2018	Review of uniformization and discretization techniques for CTMCs. Embedded DTMC. State probability distribution in CTMCs. Examples and exercizes on CTMCs and computation of basic performance parameters (throghput, utilization, average population in the system, average population in the queue, response time, waiting time, loss rate, capacity planning): single server with finite queue, single server with infinite queue, cluster of m servers each with its own queue, single server with no queue. From textbook: review of chapters 12 and 13.
April 26, 2018	Exercizes on: M/M/1/inf queue, M/M/1/M_h queue, closed systems. From textbook: ex 13.1, 13.2, 13.4 + several exercizes taken from other books. Assignment: ex 13.5.
May 3, 2018	Midterm
May 8, 2018	Discussion and solutions of the midterm exercizes.
May 10, 2018	Canceled due to health reasons
May 15, 2018	Introduction to optimization problems in a network of UAVs (Unmanned Aerial Vehicles).
May 17, 2018	Server farms: k-server loss systems, M/M/k queueing systems with finite and infinite queue, comparisons of multiple server organizations. Performance analysis of overload control policies: admission control, dynamic server provisioning based on a threshold or on a histeresis cycle defined on the system population. From textbook: pages 253-264 + several exercizes taken from other books. Assignment: ex 14.3, 14.5, 14.6.
May 22, 2018	Practice with finite state chains: exact and asymptotic analysis. Closed networks with routing cycles in the subsystem, tandem servers with finite buffer size, closed networks with multiple devices. Benefits (or absence of) of load balancing in open and in closed systems From textbook: pages 282-285 + ex 14.6, 16.1, 16.2. Assignment: ex 14.6 (partly solved in class, to be finished, find counterexample to disprove benefit of load balancing in open systems, prove benefit of load balancing in closed systems).
May 24, 2018	Network of queues and Jackson Product Form Jackson Network Definition Solving the Jackson Network Local balance approach From textbook: pages 297-306 + ex 17.1.
May 29, 2018	Practice with Jackson networks, server farms and mixed workload centers. From textbook: ex 17.2, 17.3, 17.4, review and discussion of 14.6 and an exercize on mixed workload not in the book.
May 31, 2018	Second midterm