AA1920Bartolini < PDSDR

Tags: view all tags
---+ Computer Network Performance
---++ Prof. Novella Bartolini
---
---+ Office hours

Office hours: Tuesdays, only by appointment.

The results of the second midterm are available: [[ListHereFirstMidtermGrades][Midterm results here!]]

Result of the January written exam: PrimoAppelloPCN2020

Results of the February written exam: SecondoAppelloPCN2020

---
---+ *DATE AND ROOM CHANGED FOR THE SECOND APPEAL:*
---+ The written test of the second appeal has been postponed to
---+ *February 19th, 10:30 Aula 1L - Castro Laurenziano 7a*

---

OPIS TOKENS:

6P8ERYWL

799BC5QA
---

---+ 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: [[https://sites.google.com/view/novellabartolini/thesis][ 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.

<br /><br />
---

---+ Lessons

<table align="left" border="1" cellpadding="1" cellspacing="1" style="width: 90%;"> <tbody> <tr style="background-color: #1a1d5f;"> <td align="left"> *Day* </td> <td align="left"> *Topics covered* </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">October 2, 2019</font></td> <td align="left" valign="top">Introduction to the study of performance of computer systems. <br /> Motivating examples. <br /> Single server network (interarrival time, service time, service rate). <br /> Performance metrics: Response time, Waiting time, Population. <br /> Stability condition. <br /> <br /><i>From textbook: pages 3-16 + assignment ex 2.1.</i></td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top">October 4, 2019</td> <td align="left" valign="top">Discussion on ex 2.1. <br /> Performance metrics: throughput and utilization, discussion on user/provider's perspective. <br /> <br /> _Probability review:_ <br /> Sample space, events and related probability. <br /> Conditional probability. <br /> Independent events. <br /> Law of total probability, Bayes law. <br /> Examples and excercizes in class. <br /><br /> _From textbook: pages 31-37 + ex 2.1._ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top">October 9, 2019</td> <td align="left" valign="top"> _Probability review:_ <br /> Discrete and continuous random variables. <br /> Probability mass and cumulative distribution function of discrete random variables. <br /> Common discrete distributions: Bernoulli, Binomial, Geometric and Poisson. <br /> Probability density and cumulative distribution function of continuous random variables. <br /> Common continuous distributions: uniform and exponential. <br /> <br /> Examples of probability distributions in computer networks: Poissonian arrivals, exponential interarrival and service times. Examples of geometric distribution in probabilistic routing. <br /> Expectation and conditional expectation. <br /> Utilization law: general case and single server, infinite queue case. Use of the total probability law to derive the utilization law. <br /> <br /><i>From textbook: pages 16-20, 37-47 + ex 3.1, 3.2.</i></td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top">October 11, 2019</td> <td align="left" valign="top"> _Probability review:_ <br /> Joint probability mass(discrete)/density(continuous) function <br /> Expectation of the sum and of the product of two random variables <br /> Which exponential happens first? <br /> <br /> Performance metrics: slowdown of a job <br /> Characterization of a closed network and related performance parameters: a discussion on the throughput of a batch system <br /> <br /> _From textbook: pages 47-57 + ex 2.2, 3.14, 3.5._ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top">October 16, 2019</td> <td align="left" valign="top">Review of ex. 2.2. <br /> Ergodic systems (irreducible, positive recurrent, aperiodic systems). <br /> Little's law for open and closed systems (proof). <br /> Corollaries of Little's law: utilization law. <br /> Simple exercizes of Little's law application. <br /> Examples of systems with multiple devices and probabilistic routing, <br /> use of Little's law in a finite queue system with loss. <br /> <br /><i>From textbook: pages 95-106 + ex 6.1, 6.2</i></td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top">October 18, 2019</td> <td align="left" valign="top">Operational laws: forced flow law, demand definition and demand law, bottleneck law, and related proofs. <br /> Examples of application of the operational laws to closed systems <br /> <br /> _From textbook: pages 106-111 + ex 6.5_ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top">October 23, 2019</td> <td align="left" valign="top">Review of operational laws. <br /> What-if analysis of closed systems: performance bound theorem. <br /> Plot of performance bounds for throughput and response time. Population knee point.<br /> Examples of use of bounds to address what-if questions on capacity planning.<br /><br /> _From textbook: pages 114-122_ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top">October 25, 2019</td> <td align="left" valign="top">Review of performance bounds, their interpretation for open networks.<br /> <br /> _From textbook: ex 7.2 (a-c-d), 7.3, 6.3, 6.4_ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top">October 30, 2019</td> <td align="left" valign="top">Performance bounds and timeline analysis with example. <br /><br /> _From textbook: ex 7.2 (b), 7.4, 7.5_ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">November 6, 2019</font></td> <td align="left" valign="top">Stochastic processes, discrete and continuous. <br /> Discrete Time Markov Chains (DTMC): Markovian property, time homogeneity.<br /> 1-step transition probability matrix. <br /> Chapman-Kolmogoroff equations. n-step transition probability matrix.<br /> Limiting probability and limiting distribution of a DTMC.<br /><br /> _From textbook: pages 127-135._ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top">November 8, 2019</td> <td align="left" valign="top">Review of stochastic processes, DTMCs, transition probability matrix in one and multiple steps, limiting probabilities. <br />Stationary equations. Infinite state DTMCs.</td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top">November 13, 2019</td> <td align="left" valign="top">Midterm exercizes</td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top">November 15, 2019</td> <td align="left" valign="top">Midterm exercizes</td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top">November 20, 2019</td> <td align="left" valign="top">Infinite state DTMCs and related stationary equations. <br /> Examples of DTMC analysis: one server with infinite queue. <br /> <br /> <i>From textbook: pages 142-145</i><br /> _From textbook: ex 8.1, 8.2, 8.3, 8.6_ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top">November 22, 2019</td> <td align="left" valign="top">Ergodicity theory. <br /> Ergodicity in finite-state DTMC (existence of the limiting distribution). Conditions for existence of the limiting distributions in finite-state DTMC. <br /> Definition of period in a finite-state DTMC. Aperiodicity. Irreducibility.<br /> Relationship between time recurrence and irreducibility in finite-state DTMCs. Stationary equations and flow balance equations. Ergodicity in infinite state DTMCs. Examples of positive recurrent, transient and null-recurrent DTMCs.<br /> Limiting probabilities interpreted as rates, flow balance and stationary equations. <br /> <br /> <br /> _From textbook: pages 148-160, 164-166, 168-171 + ex 9.10_ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top">November 27, 2019</td> <td align="left" valign="top">A discussion on limiting and stationary distributions.<br /> Real-world examples: Google PageRank algorithm. <br /> Poissonian processes and exponential distribution - an in-depth discussion on definitions and properties.<br /> Additivity of Poissonian processes. <br /> A preliminary study of a single server system with Poissonian arrivals and Exponential service times.<br /><br /> _From textbook: pages 190-195, 206 - 207 + 213 - 216_ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top">November 29, 2019</td> <td align="left" valign="top">Continuous Time Markov Chains (CTMC). <br /> Uniform time observation of non-uniform processes. Uniformization and discretization. Embedded Discrete Time Markov Chain of a non-uniform continuous time process.<br /> Study of the M/M/1/inf queue: flow balance equations, utilization, population, throughput, response time, queue population, average waiting time. <br /> Process with a server without queue: throughput, loss rate, utilisation, average population, average response time.<br /> Finite queue servers.<br /> <br /> <br /> _From textbook: pages 225 - 226, 229 - 234, 236 - 239 + ex 13.1, 13.2, 13.4 + assignment 13.5_ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top">December 4, 2019</td> <td align="left" valign="top">Continuous time Markov processes representing systems with multiple classes and admission control. <br /> Threshold-based and hysteresis policies. <br /> Capacity planning for performance requirements. <br /> <br /> _Exercise from previous year exams._ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top">December 6, 2019</td> <td align="left" valign="top">Capacity planning in single server (Bertsekas -Gallager result, and buffer sizing). <br /> Capacity planning of a cluster of m servers each with its own queue, how to determine the number of servers in a cluster to meet performance constraints (response time, waiting time, queue length, theoretical limitations).<br /> Server farms: k-server loss systems, M/M/k queueing systems with finite and infinite queue<br /> Utilization in a multiple server system. <br /> <br /> _From textbook: pages 253-264 + several exercizes taken from other books. Assignment: ex 14.3, 14.5, 14.6._ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top">December 11, 2019</td> <td align="left" valign="top">Boolean Network Tomography: identifiability and k-identifiability, projects<br /> <br /> _Slides on tomography available here: <br /> [[%ATTACHURL%/TesiProgettiPerfCompNet_Part1.pdf][Link 1 ]]<br /> [[%ATTACHURL%/TesiProgettiPerfCompNet_Part2.pdf][Link 2 ]]_ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top">December 13, 2019</td> <td align="left" valign="top">Drone trajectory planning, projects. <br /><br /><br /> <i>Slides on centralized task assignment for a network of aerial drones: <br /> [[%PUBURL%/PDSDR/AA1819Bartolini/CNP_projects.pdf][Link 1 ]]<br /> </i></td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"> [[%PUBURL%/PDSDR/AA1819Bartolini/CNP_projects.pdf][December 18, 2019]]</td> <td align="left" valign="top">Practice with finite state chains: exact and asymptotic analysis.<br /> Closed networks with routing cycles in the subsystem, <br /> tandem servers with finite buffer size, <br /> closed networks with multiple devices.<br /> Comparison of a system with a unique fast server and one with m servers m times slower (statistical and frequency division multiplexing).<br /> <br /> <br /> <i>From textbook: pages 239-242, 282-285 + 16.1, 16.2. <br /> </i></td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top">December 20, 2019</td> <td align="left" valign="top">Jackson networks, Jackson theorem (with proof), product form solution for the limiting probabilities, average number of jobs in a Jackson network.<br /> <br /> <i>From textbook: pages 297-306 + 17.1. <br /> </i></td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"> </td> <td align="left" valign="top">Discussion on Jackson theorem and related assumptions on arrivals, alternative ways to solve networks with feedback loops. <br /> <br /> <i>From textbook: 17.1 (discussion), 17.2, 17.3, 17.4. <br /> </i></td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"> </td> <td align="left" valign="top">Networks of multiple devices, which do not have product form solution and why, examples.<br /> Exercizes from previous exams. <br /> <br /> <i>From textbook: 18.6, 18.1, 18.2 (suggested to read chapter 18). <br /> </i></td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"> </td> <td align="left" valign="top"><i>Lesson moved to the afternoon </i><br /> Midterm</td> </tr> </tbody> </table> <hr width="100%/"></hr>

 <br /><br />
---+ Textbook

 Mor Harcol-Balter,<i> Performance Modeling and Design of Computer Systems</i>, Cambridge University Press, 2013.
   * [[%ATTACHURL%/CNP_written_exam_instructions.pdf][CNP_written_exam_instructions.pdf]]: Online exam instructions <p> </p>
   * [[%ATTACHURL%/cnp_instructions_june6_2020.pdf][cnp_instructions_june6_2020.pdf]]: cnp_instructions_june6_2020.pdf
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
pdf	CNP_written_exam_instructions.pdf	r1	manage	705.1 K	2020-06-09 - 12:47	NovellaBartolini	Online exam instructions
pdf	cnp_instructions_june6_2020.pdf	r1	manage	707.1 K	2020-07-04 - 21:56	NovellaBartolini