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?