CSC407 Winter 2007

Exercise 3

General

This exercise is out of 40, and is worth 20% of your course grade. All work must be submitted via Subversion, and must be readable on CDF. See the home page for the course late policy.

This assignment is due at 5:00 pm EST on Monday, April 9. Please ask questions early.

Performance (20 marks)

These questions relate to performance modeling and analysis. Submit your answers on paper to the course instructor.

1. Throughput (5 marks)

An MP3 music server receives 4 requests per minute; half of them take 1 millisecond to process ("file not found"), and the other half take 10 seconds to process ("file available for download"). What is the utilization of the server? What is its average response time? If the rate at which requests arrive stays constant, how quickly would the server have to handle each request in order to cut the response time to one-tenth its current value? Show your work.

Solution:

2. Markov Chains (5 marks)

Winter days in Toronto are either clear, rainy, or snowy. If a day is clear, the next day is equally likely to be clear, rainy, or snowy. If a day is rainy or snowy, then half the time we get the same weather the next day; one quarter of the time, the next day is clear, and the remaining one quarter of the time, the next day is, well, whatever's left over. What percentage of winter days are clear, rainy, and snowy? Show your work.

Solution: Let Pc, Pr, Ps, be the probabilities of Clear, Rainy, Snowy day respectively. The equations can be set up as follows:

(1)Pc=1/3 Pc + 1/4 Pr + 1/4 Ps
(2)Pr=1/3 Pc + 1/2 Pr + 1/4 Ps
(3)Ps=1/3 Pc + 1/4 Pr + 1/2 Ps
(4)Ps+Pc + Pr = 1

There are a number of ways to solve this. You can subtract (3) from (2) only to realize that Pr=Ps which was somewhat expected.

From there replace Pr and Ps with, say, Z and solve (3) and (4). The result should be Pr = Ps = 4/11, and Pc = 3/11, which is intuitive as we expect clear days to be a bit less probable.

3. Throughput Again (5 marks)

Back in the Dark Ages, students had to register for courses by filling in a printed form, taking it to their registrar, and getting it checked and signed. You know there are three people working in the registrar's office, and you can see that eleven students are entering the office every minute. How long on average is each registrar spending with each student?

Solution: There are two ways to go about this. One is to assume a multi-server queue (M/M/c formally, but doesn't matter) which has as many times greater service rate as the servers. Thus if each server has a rate μ our 3 server setting has a rate &mut = 3μ.

Now we assume that since there is no infinite line waiting at the registrars office it must be that λ <= &mut, λ <= 3μ. So:

A second way is by direct application of Little's law (see slide 17 of Performance Analysis I): (11 requests per minute) × (X minutes response time) = 3 servers. Then 11X=3, which implies X=3/11 (mins) and intuitively this is a maximum time.

4. Virus Propagation (5 marks)

Dr. Nefarious has just invented a super-virus that can infect any computer at all. Assume that:

  1. there are one billion computers on the Internet;
  2. the virus tries to infect machines at random;
  3. it takes the virus one second to either infect an uninfected machine, or realize that a machine is already infected; and
  4. there is no cure (mwah hah hah).

How long until 99% of the machines on the Internet are infected? Explain your reasoning.

Solution: I would tackle this using a recurrence relation. Let N be the total number of machines, It be the number of machines infected at time t, and Ut be the number of uninfected machines at time t (which is just N-It). When t=0, It=1 and Utt=N-1. Since target are chosen randomly, the probability that a particular infected machine will attack an uninfected machine is Pt=Ut/N. The probability that an uninfected machine will stay uninfected must be Qt=(1-Pt)It, i.e., the probability that none of the infected machines will attack it. The number of uninfected machines that stay uninfected is therefore QtUt. So, at time t:

Ut=Qt-1Ut-1
It=N-Ut
Pt=Ut/N
Qt=(1-Pt)It

and around we go again. At this point, you can either recast this as a differential equation:

ΔU/Δt=Ut+1 - Ut
=U(1-U/N)N-U - U

or write a small program in your favorite language and run it until Ut is 0.01N (i.e., 99% of the machines are infected). If you do the latter, however, you have to be careful about your floating point numbers: when N is 109 and U is 109-1, even 64-bit arithmetic has problems...

Term Paper (20 marks)

The final part of the term paper has two parts, each worth 10 marks. First, write a short critique (at least two 8.5x11 pages, but no more than four) of the architectures of the applications you have been studying. Where and how could their code be simplified? Made more efficient? Made more flexible, or easier to extend? Be very specific: "padding" will cost you marks. Submit your answer in a PDF file called critique.pdf in your e03 directory (with the usual redirect file in your partner's directory).

Second, think of a feature that you might want to add to the applications you are studying, and describe how you would implement it for each one. For example, if your applications are a pair of games, your feature might be, "Allow users to customize the colors and shapes of their pieces." Again, be very specific in your descriptions: explain how the conceptual, implementation, and execution architectures would change (if at all), how old configuration files and other application data would be upgraded, and so on. Submit your answer in a PDF file called extension.pdf in your e03 directory (with the usual redirect file in your partner's directory).

Valid XHTML 1.0! Valid CSS! $Id: ex03.html,v 1.9 2007/04/20 01:41:50 gvwilson Exp $