Tags:
create new tag
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: 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: 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
October 2, 2019 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.
October 4, 2019 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 9, 2019 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 11, 2019 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 16, 2019 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 18, 2019 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 23, 2019 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 25, 2019 Review of performance bounds, their interpretation for open networks.

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

From textbook: ex 7.2 (b), 7.4, 7.5
November 6, 2019 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.
November 8, 2019 Review of stochastic processes, DTMCs, transition probability matrix in one and multiple steps, limiting probabilities.
Stationary equations. Infinite state DTMCs.
November 13, 2019 Midterm exercizes
November 15, 2019 Midterm exercizes
November 20, 2019 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 22, 2019 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 27, 2019 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 29, 2019 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
December 4, 2019 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.
December 6, 2019 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.
December 11, 2019 Boolean Network Tomography: identifiability and k-identifiability, projects

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


Slides on centralized task assignment for a network of aerial drones:
Link 1
December 18, 2019 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 20, 2019 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.
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.
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).
Lesson moved to the afternoon
Midterm



Textbook

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

Attachments Attachments
Topic attachments
I Attachment History Action Size Date Who Comment
PDFpdf CNP_written_exam_instructions.pdf r1 manage 705.1 K 2020-06-09 - 12:47 NovellaBartolini Online exam instructions
PDFpdf cnp_instructions_june6_2020.pdf r1 manage 707.1 K 2020-07-04 - 21:56 NovellaBartolini  
Edit | Attach | Watch | Print version | History: r12 < r11 < r10 < r9 < r8 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r12 - 2020-12-31 - 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-2025 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback