King’s College London
This paper is part of an examination of the College counting towards the award of a degree. Examinations are governed by the College Regulations under the authority of the Academic Board.
Degree Programmes
Module Code Module Title Examination Period
MSci, MSc, MEng
7CCSMNTH
Network Theory May 2019 (Period 2)
Time Allowed 3 hours
Rubric ANSWER FOUR OF FIVE QUESTIONS.
All questions carry equal marks. If more than four questions are answered, the answers to the first four questions in exam paper will count.
ANSWER EACH QUESTION ON A NEW PAGE OF YOU ANSWER BOOK AND WRITE ITS NUMBER IN THE SPACE PROVIDED
Calculators Calculators may be used. The following models are permitted: Casio fx83 / Casio fx85
Notes Books, notes or other written material may not be brought into this examination
PLEASE DO NOT REMOVE THIS PAPER FROM THE EXAMINATION ROOM
TURN OVER WHEN INSTRUCTED
King’s College London ©2019
Question One
a) Figure 1 shows the internet topology of different Internet Service Providers (ISPs) connecting to Google’s data centre (node g in the graph). The labels on the edges indicate the capacities of the links (in Mbps).
i. What is the maximum data rate that can be achieved from ISP ‘s’ to google?
[3 marks] ii. How should data be routed from ISP ‘s’ to achieve this data rate?
Explain your calculation in details.
[9 marks]
b) Explain with examples from the topology of Figure 1 why routing based on
shortest paths may be sub-optimal.
[3 marks]
c) Using Dijkstra’s algorithm, calculate the shortest paths from the ISP ‘s’ to all
7CCSMNTH Network Theory
other ISPs in this topology.
Figure 1. Network topology for Question 1
[10 marks]
2
[Total 25 marks]
SEE NEXT PAGE
Question Two
a) ConsideranM/G/1systeminwhichtimeisdividedintointervalsoflengthqsec each. Assume that arrivals are Bernoulli, that is
P[1 arrival in any interval] = λq P[0 arrival in any interval] = 1-λq P[ > 1 arrivals in any interval] = 0
Assume that a customer’s service time is some multiple of q sec such that: P[service time = nq sec] = gn n = 0, 1, 2, …
b)
In a computer network a link has a transmission rate of C bit/s. Messages arrive at this link in a Poisson fashion with rate λ messages per second. Assume that the messages have exponentially distributed length with a mean of 1/μ bits, and that the messages are queued in a First Come First Served (FCFS) fashion if the link is busy.
i) Write down the detailed balance equations.
ii) What is the probability that there is no queue?
iii) What is the probability that the queue has k packets?
[4 marks] [4 marks] [1 marks]
iv) If we want the average time spent by a packet to be less than some value T0, what is the minimum possible value for transmission rate C?
[10 marks]
[Total 25 Marks]
SEE NEXT PAGE
3
7CCSMNTH Network Theory
i) Find expected number of arrivals in an interval.
ii) Find the average arrival rate.
iii) Find ymn = P[m customers arrive in nq sec]
[2 marks] [2 marks]
[2 marks]
Question Three
a) Draw simple, connected graphs with degree sequences of
(i) (1; 2; 3),
(ii) (1; 2; 3; 4)
(iii) (1; 2; 3; 4; 6)
[1 mark]
[2 marks]
If there will be a cascade, write down a suitable set of initial nodes that will lead to the cascade. If there will not be a cascade, explain why not.
Fig. 2. Infinite tree topology for Question 3.d
4
7CCSMNTH Network Theory
[2 marks]
b) Prove that there can be no graph of degree sequence (1;2; 3; 4; 5).
[5 marks]
c) In the Erdos-Renyi random graph of G(n,p),
i. Explain how the clustering coefficient C is calculated.
[6 marks]
ii. What property of network is captured by the clustering coefficient?
[4 marks]
d) In the infinite tree in Fig 2, will there be an infinite cascade if the adoption threshold is
i. q = 1/3.
ii. q = 1/2
[2 marks]
[3 marks]
[Total 25 marks]
SEE NEXT PAGE
Question Four
Consider problem (P1) below, (P1): Minimise
Subjectto
(x1 − 12)2 +(x2 +6)2
x12 +3×1 +x22 −4.5×2 ≤6.5
(x1 −9)2 +x2 ≤64
a) Use the logarithmic barrier method to approximate (P1) with an unconstrained problem.
[5 marks]
b) Determine whether or not the point x = (x1, x2) = (2, 1) is a candidate to be an optimal solution to problem P1.
c) Consider optimisation problem (P2) to be, (P2): Minimise f(x)
Subject to gi(x) ≤ 0 for i = 1, …, m hi(x) = 0 for i = 1, …, n
Let x* be a feasible solution that solves P2 locally. Show the Karush–Kuhn– Tucker optimality conditions for (P2).
[5 marks] d) Describe the steps used to solve an optimization problem using Newton’s
algorithm.
5
7CCSMNTH Network Theory
[10 marks]
[5 marks]
[Total 25 marks]
SEE NEXT PAGE
Question Five
iterated removal of dominated strategy
6
7CCSMNTH Network Theory
a) Assume you are a selfish rational agent. Suppose you and two of your friends go to a coffee house. You have the option of getting a cappuccino, tea, or bottled water costing £3, £1.5 or £1 respectively.
i) Which item would you choose if you were paying for the item yourself?
[4 marks]
ii) Which item would you choose if you were splitting the bill equally with
your friends
[6 marks]
b) In the 802.11 (WiFi) protocol, each station with data to send contends for airtime. If a station does not send data in a slot, airtime is wasted. If only one station sends data, it succeeds. If both send, there is a collision of signals, both fail, and both must try again. The possible actions for each station is ‘Send’ (S) and ‘Don’t send’ (D). Each station prefers success to a wasted time slot, and prefers a wasted time slot to a collision, because on a collision, not only is no progress achieved, but energy is also wasted. We can express these preferences by assigning a utility of -1 to a collision, 0 to a wasted time slot,
and 1 to success.
i) Write down the payoff matrix for each station as a normal form game
[4 marks]
ii) Suppose one station is much more powerful and always succeeds in
capturing the time slot if it tries. Assuming this station is the column player, write down the new payoff matrix
[4 marks]
iii) Identify the Nash equilibrium of the “capture effect WiFi game” by
[7 marks] [Total 25 marks]
FINAL PAGE