CNP1718 < PDSDR

---+ Computer Network Performance
---++ Prof. Novella Bartolini
<hr width="100%"></hr>
---++ Grades and registrations

%RED% *First midterm results available here: MidtermGrades1* %ENDCOLOR%

%RED% *Second midterm results available here:* SecondMidtermGrades %ENDCOLOR%

%RED% *Results of the written exam of June 18, 2018:* FirstAnnGrades %ENDCOLOR%

%RED% *Results of the written exam of June 28, 2018:* SecondAnnGrades %ENDCOLOR%

*%RED%Results of the written exam of September 18, 2018:%ENDCOLOR%* SeptemberGrades

---
---+ Exams and office hours

<span style="background-color: transparent;">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.</span>
---

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

<span class="WYSIWYG_COLOR" data-mce-mark="1" style="background-color: transparent; color: green;"> Registration is mandatory, please use this [[Prenotazioni.2018_11_07_MidtermOfComputerNetworkPerformance#2018_11_07_MidtermOfComputerNetworkPerformanceedittable1][ registration page]].</span>
---

<pre data-fulltext="" data-placeholder="Traduzione" dir="ltr" id="tw-target-text"> </pre>

---+ 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">February 27, 2018</font></td> <td align="left" valign="top"> _All lessons cancelled due to adverse weather conditions_ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">March 1, 2018</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 + ex 2.1.</i></td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">March 6, 2018</font></td> <td align="left" valign="top">Open and closed queueing networks. <br /> Performance metrics: throughput and utilization, slowdown. <br /> The utilization law. <br /> Interactive and batch closed systems. <br /> <br /><i>From textbook: pages 16-25 + ex 2.2.</i></td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">March 8, 2018</font></td> <td align="left" valign="top "> _Probability review:_ <br /> Sample space, events and related probability. <br /> Conditional probability. <br /> Independent events. <br /> Law of total probability, Bayes law. <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 /> Expectation and variance. <br /> <br /><i>From textbook: pages 31-46 + ex 3.1, 3.2.<br /> Assignment: ex 3.5.</i></td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">March 13, 2018</font></td> <td align="left" valign="top "> _Probability review cont.d:_ <br /> Joint probabilities and independence.<br /> Probabilities and expectation via conditioning.<br /> Linearity of expectation <i> (end of review). </i><br /> <br /> Time average and ensemble average (skimmed).<br />Ergodic system properties. <br /> Little's Law for open and closed systems. <br /> Proof of Little's law for open systems. <br /><br /><i>From textbook: pages 47-50, 53-55, 84-90, 95-99 + ex 3.5, 6.1.</i></td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">March 15, 2018</font></td> <td align="left" valign="top ">Application of Little's Law to a whole system or to parts of it.<br /> Little's law for time in queues.<br /> Utilization law.<br /> Little's law for multiple classes of arrivals.<br /> Little's law for queues with limited buffer size.<br />Forced flow law.<br /> Service demand and bottleneck law. <br /><br /><i>From textbook: pages 100-110 + ex 6.5.<br /> Assignment: ex 6.2, 6.3, 6.4, 6.6, 6.7.</i></td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">March 20, 2018</font></td> <td align="left" valign="top ">Review of operational laws.<br /> Introduction to project topics.<br /><br /><i> [[%ATTACHURL%/TesiProgettiPerfCompNet.pdf][Slides available]].</i><br /><i> From textbook: ex 6.2, 6.3, 6.4.</i></td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">March 22, 2018</font></td> <td align="left" valign="top ">Introduction to project topics. <br /> Boolean Network Tomography.<br /> k-identifiability and bounds.<br /> <br /><i> Slides available (same file of previous lesson).</i></td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">March 27, 2018</font></td> <td align="left" valign="top ">Review of operational laws.<br /> Asymptotic bounds for closed systems.<br /> Modification analysis for closed systems.<br /> <br /><i>From textbook: pages 114-122.<br /> Assignment: ex 7.2, 7.3, 7.4, 7.5.</i></td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">April 2, 2018</font></td> <td align="left" valign="top "> _Easter vacation_ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">April 5, 2018</font></td> <td align="left" valign="top ">Review of modification analysis. <br /> Stochastic processes: examples. <br /> Definition of Markov chain. <br /> <br /> _From textbook: pages 122, 129-131 + ex 7.2, 7.3._ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">April 10, 2018</font></td> <td align="left" valign="top ">Stochastic processes and properties of Markov chains.<br />Discrete Time Markov Chains (DTMC). <br /> Examples: repair facility problem, umbrella problem, program analysis problem, admission control based on threshold, admission control based on histeresis cycle. <br /> <i>n</i>-step transition probability and Chapman-Kolmogoroff equations. <br />Limiting distribution and stationary distribution for a finite state DTMC.<br /><br /> _From textbook: pages 129 - 136._ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">April 12, 2018</font></td> <td align="left" valign="top ">Equivalence of limiting and stationary distribution.<br /> Infinite state DTMCs.<br />How to solve stationary equations in infinite-state DTMCs.<br />Stationary equations and flow balance equations. <br /><br /> _From textbook: pages 136-145, 168-170 (par 9.6) + ex 8.1, 8.2, 8.3.<br /> Assignment: ex 8.6._ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">April 17, 2018</font></td> <td align="left" valign="top ">Analysis of a DTMC representing a queue with a threshold based service discipline.<br /> Conditions for existence of the limiting distributions in finite-state DTMC. <br /> Definition of period in a DTMC. Aperiodicity. <br /> Irreducibility. Relationship between time recurrence and irreducibility in finite-state DTMCs. <br /> <br /> _From textbook: pages 148 - 155 + ex 8.6._ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">April 19, 2018</font></td> <td align="left" valign="top ">Infinite-state DTMCs. Ergodicity and conditions of existence of the limiting distribution. <br /> Recurrent and transient states. Irreducibility and time recurrency in infinite-state DTMCs. <br /> Limiting probabilities interpreted as rates, equivalence of flow balance and stationary equations. <br /> The Google PageRank algorithm: how to rank web pages by means of a DTMC. <br /> Continuous Time Markov Chains. Poisson distribution of events, exponential interarrival times. <br /> Review of exponential distribution: memoryless property. <br /> Study of the M/M/1/inf queue: flow balance equations, utilization, population, throughput, response time, queue population. <br /> <br /><br /> _From textbook: pages 155 -160, 164 - 166, 168 - 170, 190 - 195, 206 - 207 + 213 - 216, 225 - 226, 229 - 234, 236 - 239 + ex 9.10._ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">April 24, 2018</font></td> <td align="left" valign="top ">Review of uniformization and discretization techniques for CTMCs. Embedded DTMC. <br /> State probability distribution in CTMCs. <br /> 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): <br /> single server with finite queue, <br /> single server with infinite queue, <br /> cluster of m servers each with its own queue, <br /> single server with no queue. <br /> <br /> <br /> _From textbook: review of chapters 12 and 13._ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">April 26, 2018</font></td> <td align="left" valign="top ">Exercizes on: M/M/1/inf queue, M/M/1/M_h queue, closed systems. <br /><br /> _From textbook: ex 13.1, 13.2, 13.4 + several exercizes taken from other books. <br /> Assignment: ex 13.5._ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">May 3, 2018</font></td> <td align="left" valign="top "> _Midterm_ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">May 8, 2018</font></td> <td align="left" valign="top "> _Discussion and solutions of the midterm exercizes._ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">May 10, 2018</font></td> <td align="left" valign="top "> _Canceled due to health reasons_ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">May 15, 2018</font></td> <td align="left" valign="top ">Introduction to optimization problems in a network of UAVs (Unmanned Aerial Vehicles).</td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">May 17, 2018</font></td> <td align="left" valign="top ">Server farms: k-server loss systems, M/M/k queueing systems with finite and infinite queue, comparisons of multiple server organizations.<br /> 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. <br /> <br /> <br /> _From textbook: pages 253-264 + several exercizes taken from other books. <br /> Assignment: ex 14.3, 14.5, 14.6._ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">May 22, 2018</font></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 /> Benefits (or absence of) of load balancing in open and in closed systems<br /> <br /> <br /> _From textbook: pages 282-285 + ex 14.6, 16.1, 16.2.<br /> 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)._ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">May 24, 2018</font></td> <td align="left" valign="top ">Network of queues and Jackson Product Form <br /> Jackson Network Definition <br />Solving the Jackson Network <br />Local balance approach <br /> <br /> <br /> _From textbook: pages 297-306 + ex 17.1._ </td> </tr> <tr style="background-color: #daf2fc;"> <td align="left" valign="top"><font size="2">May 29, 2018</font></td> <td align="left" valign="top ">Practice with Jackson networks, server farms and mixed workload centers. <br /> <br /> <br /> _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._ </td> </tr> <tr style="background-color: #e4e6e6;"> <td align="left" valign="top"><font size="2">May 31, 2018</font></td> <td align="left" valign="top "> _Second 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.

<hr width="100%/"></hr>
This topic: PDSDR > WebHome > CNP1718
Topic revision: r35 - 2018-10-27 - NovellaBartolini