Examinable material
When I say | I mean | Learn it by |
---|---|---|
Understand | "Understand the term ergodic" means that, if I use the word "ergodic" in a question, you need to comprehend what I'm describing. | Read the relevant section of the notes. If there's anything that confuses you, look it up or ask someone for help. |
Know | You need to be able to reproduce this section of notes from memory, without thinking | Copy it out. Copy it out again, but in your own words. Copy it out again from memory. Keep doing this until you get it right. |
Be able to | You need to (1) state what you're doing, (2) explain any special terms in what you've stated, (3) do it. For example, "Be able to fit distributions" means you should answer a question by writing "I will fit the XXX distribution to this data by writing out the likelihood function and maximizing it with respect to parameters YYY and ZZZ", then state the density of XXX is and the likelihood function, then go ahead and maximize it. | Solve problems. Whenever you quote a result in your answer, make sure you know exactly what assumptions underly that result, e.g. what model it comes from. |
-
§1. Fundamentals
- Know how to distinguish a 'random sample' from a 'random variable'. Know the definitions of empirical distribution function, and of distribution function, and understand the relationship between the two.
- Know the definitions of density, mean/expectation, median, standard deviation, variance, covariance, confidence interval. Understand the difference between discrete and continuous random variables. Know the density of the Uniform, Exponential, Pareto, Normal, Geometric, Binomial, Poisson distributions. Know the distribution function of the Uniform, Exponential, Pareto, Geometric distributions. Know the mean and standard deviation of the Uniform, Exponential, Poisson, and Normal distributions. Know the mean of the Binomial and Geometric distributions.
- Be able to plot an empirical distribution function. Be able to fit distributions (you need to know enough calculus to be able to reproduce the examples of fitting distributions that we have studied). Be able to generate random variables using the inversion method.
- Be able to work with random variables, both directly via their density or distribution function (e.g. §1.8a), and indirectly via formulae for expectation and variance (§1.7). Understand which of these formulae require independence.
-
§2. Simulation
- Know the three types of simulation (discrete time, event driven, fluid).
- Understand the different vantage points from which averages can be measured, and be able to reason about which is appropriate for a given purpose.
- Know what is meant by stable/unstable/bistable, transient behaviour, equilibrium, periodic, stationary, limiting, ergodic. Be able to diagnose which of these applies to a given simulator, by understanding how each shows up in simulation data. Understand how to present data from a single run, and how to present data from multiple runs including error bars.
- Understand the challenge of working with heavy-tailed random variables (§2.5 and §1.8c).
- Know what is meant by a Poisson process, know the properties of the Poisson process, and be able to reason about inter-event times, event rates, superposition and thinning. Know what is meant by a processor-sharing queue and know the stability condition and queue size distribution. Know what is meant by an Erlang link and understand what is measured by the blocking probability. Understand what is meant by a FIFO queue. Understand what is meant by an open/closed workload model.
-
§3. Analysing random processes
- Know what is meant by "drift". Be able to derive drift equations by calculating expectations, and draw drift diagrams (both the one-variable sort and the two-variable sort). Be able to simulate a drift model on computer (i.e. fluid simulation). Know the two drift models for the processor sharing link. Know the term "fixed point of a drift model", and be able to distinguish stable and unstable fixed points. Know what is meant by bistability.
- Be able to write down fixed-point equations for a system and solve them on a computer using the iterative method. Know the Dynamic Alternative Routing model, and be able to solve the Erlang fixed point approximation numerically.
- Know Little's Law. Know how to apply it to busy times in a processor sharing link, and utilization and average queueing delay in a FIFO queue. Be able to use the flow conservation law.
-
§4. TCP
- Understand the idea of windowed flow control, and the relationship between window size and transmission rate. Know TCP's mechanism for adapting its window size.
- Be able to derive (and extend) the drift model for TCP. Be able to sketch a drift diagram for TCP.
- Be able to derive the TCP throughput equation. Be able to use the fixed point method to analyse networks.
-
§5. Resource allocation
- Know what is meant by a feasible region, understand the examples given, and be able to identify it in new problems.
- Understand that there is a choice of operating point, know the definition of the weighted α-fair operating point, and understand its relationship to TCP and to maximizing throughput.
- Understand how to solve constrained multivariate optimization by steepest ascent. Understand that TCP can be seen as such a solver.