Tags:
create new tag
view all tags

Computer Network Performance

Prof. Novella Bartolini


Office hours

Office hours: Wednesday 1.30 - 3.00 only by appointment.

Exam - summer session

The next written text is on June 4, 2019, at 10.30, room P2.

Second midterm - results - please READ

(The results of the first and second midterm are available at the MidtermResults page.)

Results of the written exam held on January 10: RisultatiPrimoAppelloPCN19

Results of the February exam: RisultatiFebbraioPCN19

Results of July 2019: RisultatiSecondoAppello

Results of September 2019: RisultatiAppelloSettembre

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: 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
September 26, 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 + assignment ex 2.1.
September 28, 2018 Discussion on ex 2.1.
Performance metrics: throughput and utilization, discussion on user/provider's perspective.

Probability review:
Sample space, events and related probability.
Conditional probability.
Independent events.
Law of total probability, Bayes law.
Examples and excercizes in class.

From textbook: pages 31-37 + ex 2.1.
October 3, 2018 Probability review:
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.

Examples of probability distributions in computer networks: Poissonian arrivals, exponential interarrival and service times. Examples of geometric distribution in probabilistic routing.
Expectation and conditional expectation.
Utilization law: general case and single server, infinite queue case. Use of the total probability law to derive the utilization law.

From textbook: pages 16-20, 37-47 + ex 3.1, 3.2.
October 5, 2018 Probability review:
Joint probability mass(discrete)/density(continuous) function
Expectation of the sum and of the product of two random variables
Which exponential happens first?

Performance metrics: slowdown of a job
Characterization of a closed network and related performance parameters: a discussion on the throughput of a batch system

From textbook: pages 47-57 + ex 2.2, 3.14, 3.5.
October 10, 2018 Review of ex. 2.2.
Ergodic systems (irreducible, positive recurrent, aperiodic systems).
Little's law for open and closed systems (proof).
Corollaries of Little's law: utilization law.
Simple exercizes of Little's law application.
Examples of systems with multiple devices and probabilistic routing,
use of Little's law in a finite queue system with loss.

From textbook: pages 95-106 + ex 6.1, 6.2
October 12, 2018 Operational laws: forced flow law, demand definition and demand law, bottleneck law, and related proofs.
Examples of application of the operational laws to closed systems

From textbook: pages 106-111 + ex 6.5
October 17, 2018 Review of operational laws.
What-if analysis of closed systems: performance bound theorem.
Plot of performance bounds for throughput and response time. Population knee point.
Examples of use of bounds to address what-if questions on capacity planning.

From textbook: pages 114-122
October 19, 2018 Review of performance bounds, their interpretation for open networks.

From textbook: ex 7.2 (a-c-d), 7.3, 6.3, 6.4
October 24, 2018 Performance bounds and timeline analysis with example.

From textbook: ex 7.2 (b), 7.4, 7.5
October 26, 2018 Stochastic processes, discrete and continuous.
Discrete Time Markov Chains (DTMC): Markovian property, time homogeneity.
1-step transition probability matrix.
Chapman-Kolmogoroff equations. n-step transition probability matrix.
Limiting probability and limiting distribution of a DTMC.

From textbook: pages 127-135.
October 31, 2018 Review of stochastic processes, DTMCs, transition probability matrix in one and multiple steps, limiting probabilities.
Stationary equations. Infinite state DTMCs.
November 2, 2018 Lesson cancelled
November 7, 2018 Midterm
November 9, 2018 Infinite state DTMCs and related stationary equations.
Examples of DTMC analysis: one server with infinite queue.

From textbook: pages 142-145
From textbook: ex 8.1, 8.2, 8.3, 8.6
November 14, 2018 Ergodicity theory.
Ergodicity in finite-state DTMC (existence of the limiting distribution). Conditions for existence of the limiting distributions in finite-state DTMC.
Definition of period in a finite-state DTMC. Aperiodicity. Irreducibility.
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.
Limiting probabilities interpreted as rates, flow balance and stationary equations.


From textbook: pages 148-160, 164-166, 168-171 + ex 9.10
November 16, 2018 A discussion on limiting and stationary distributions.
Real-world examples: Google PageRank algorithm.
Poissonian processes and exponential distribution - an in-depth discussion on definitions and properties.
Additivity of Poissonian processes.
A preliminary study of a single server system with Poissonian arrivals and Exponential service times.

From textbook: pages 190-195, 206 - 207 + 213 - 216
November 21, 2018 Continuous Time Markov Chains (CTMC).
Uniform time observation of non-uniform processes. Uniformization and discretization. Embedded Discrete Time Markov Chain of a non-uniform continuous time process.
Study of the M/M/1/inf queue: flow balance equations, utilization, population, throughput, response time, queue population, average waiting time.
Process with a server without queue: throughput, loss rate, utilisation, average population, average response time.
Finite queue servers.


From textbook: pages 225 - 226, 229 - 234, 236 - 239 + ex 13.1, 13.2, 13.4 + assignment 13.5
November 23, 2018 Continuous time Markov processes representing systems with multiple classes and admission control.
Threshold-based and hysteresis policies.
Capacity planning for performance requirements.

Exercise from previous year exams.
November 28, 2018 Capacity planning in single server (Bertsekas -Gallager result, and buffer sizing).
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).
Server farms: k-server loss systems, M/M/k queueing systems with finite and infinite queue
Utilization in a multiple server system.

From textbook: pages 253-264 + several exercizes taken from other books. Assignment: ex 14.3, 14.5, 14.6.
November 30, 2018 Boolean Network Tomography: identifiability and k-identifiability, projects

Slides on tomography available here:
Link 1
Link 2
December 5, 2018 Drone trajectory planning, projects.


Slides on centralized task assignment for a network of aerial drones:
Link 1
December 7, 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.
Comparison of a system with a unique fast server and one with m servers m times slower (statistical and frequency division multiplexing).


From textbook: pages 239-242, 282-285 + 16.1, 16.2.
December 12, 2018 Jackson networks, Jackson theorem (with proof), product form solution for the limiting probabilities, average number of jobs in a Jackson network.

From textbook: pages 297-306 + 17.1.
December 14, 2018 Discussion on Jackson theorem and related assumptions on arrivals, alternative ways to solve networks with feedback loops.

From textbook: 17.1 (discussion), 17.2, 17.3, 17.4.
December 19, 2018 Networks of multiple devices, which do not have product form solution and why, examples.
Exercizes from previous exams.

From textbook: 18.6, 18.1, 18.2 (suggested to read chapter 18).
December 21, 2018 Lesson moved to the afternoon
Midterm



Textbook

Mor Harcol-Balter, Performance Modeling and Design of Computer Systems, Cambridge University Press, 2013.

Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf CNP_projects.pdf r1 manage 302.7 K 2019-01-02 - 18:06 NovellaBartolini  
PDFpdf TesiProgettiPerfCompNet_Part1.pdf r1 manage 8516.4 K 2019-01-02 - 13:00 NovellaBartolini  
PDFpdf TesiProgettiPerfCompNet_Part2.pdf r1 manage 8516.6 K 2019-01-02 - 13:00 NovellaBartolini  
Edit | Attach | Watch | Print version | History: r20 < r19 < r18 < r17 < r16 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r20 - 2019-10-17 - NovellaBartolini





 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback