## Description

1. (4 marks) Consider the network link described in problem 4 of assignment #2, with

Poisson packet arrivals, an arrival rate of 8000 packets/second, and a mean packet

service (transmission) time of 0.1 milliseconds. Assume now that 10% of the packets

are “small” packets with transmission time of (exactly) 0.01 milliseconds and 90%

are “big” packets with transmission time of (exactly) 0.11 milliseconds. (Note that

the overall mean is still 0.1 milliseconds.) Give the mean residence time of the

“small” packets, and of the “big” packets, supposing that non-preemptive priority is

given to the “small” packets.

2. (6 marks) Consider the request routing problem described in problem 2 of

assignment #2, with Sslow = 3, Sfast = 1.5, and FCFS scheduling at each server.

Suppose that the requests are generated by a fixed number N of clients with average

think time 30, that service times are exponentially distributed, and that routing can be

modeled as probabilistic. Using the single class exact MVA algorithm, determine the

value of f (to two decimal places) that maximizes throughput for each value of N

between 1 and 30 inclusive.

3. Suppose that at a “Rock Paper Scissors” (http://www.rpschamps.com) competition, a

particular player had a probability of 0.3 of throwing “Rock” after throwing “Rock”,

and 0.4 of throwing “Rock” after throwing either “Paper” or “Scissors”. This player

had a probability of 0.5 of throwing “Paper” after throwing “Rock”, and 0.3 of

throwing “Paper” after throwing “Paper” or “Scissors”. Finally, the player had a

probability of 0.2 of throwing “Scissors” after throwing “Rock”, and 0.3 of throwing

“Scissors” after throwing “Paper” or “Scissors”.

(a) (3 marks) Construct a discrete time state-transition model for this player. You

should have three states, corresponding to the three possible outcomes of the most

recent throw of this particular player.

(b) (3 marks) Give a set of three independent equations that could be solved to obtain

the proportion of the player’s throws that are of each type. (You do not need to

carry out the solution.)

4. Consider a system with two processors P1 and P2, each with its own cache, and a

particular memory block b. The mean time between read accesses to block b by each

processor is R, the mean time between write accesses to block b by each processor is

W, and these interaccess times are independent and exponentially distributed. A read

or write access to block b causes it to be loaded into the respective processor’s cache,

if not already present; furthermore, a write access causes the block to be removed

from the cache of the other processor, if present there. Assume further that whenever

block b is present in a particular cache, eviction from that cache by the cache

replacement policy, so as to make room for some other block, occurs at a rate λ.

(a) (4 marks) Construct a continuous time state-transition model for this system.

Your model should have four states (block b in neither cache, block in P1 cache

but not in P2 cache, block in P2 cache but not in P1 cache, block in both caches).

(b) (4 marks) Give a set of equations that could be used to find the equilibrium state

probabilities, given values for the parameters R, W, and λ.

5. Consider a system that utilizes two servers to process an incoming request stream.

Request arrivals are Poisson at rate . Request service times are independent and

exponentially distributed with mean S.

(a) (4 marks) Give a state-transition model for this system, assuming that an

incoming request is assigned to each server with probability ½ independently of

the states of the servers and of the routing of prior requests. Make sure you

clearly describe your choice of system states.

(b) (4 marks) Repeat part (a), but now assuming that an incoming request is assigned

to the server that currently has the smallest number of requests. If both servers

have the same number of requests, the request is assigned to each server with

probability ½.

(c) (4 marks) Repeat part (a), but now assuming that requests are assigned in a

round-robin manner.

(d) (2 marks) How do you think the system performance with these three routing

options would compare, and why?