Telecom Networks Test 2

There are 3 questions. Marks allocated to each part are indicated in square brackets.

This exam is open book. You are permitted to consult any resources | textbook, web, notes. But do not discuss the questions and solutions with your classmates. Do not ask anyone else to help you solve the problems.






P30    P4






P12

 P13

P23




P19 


Figure 1: Distributed hash table for question 1. Solid circles represent peers, labelled by their location. The table uses a 5-bit key space, so peers have addresses from 0 to 31.

The gure above illustrates the peers involved in a P2P network that is using the Chord dis-tributed hash table for routing and key searches. The table uses a 5-bit key space. As a result all distances are computed modulo 32 (we focused on 128 in lectures, but here there are at most 32 peers, numbered from 0 to 31).

Assume that there is no key copying currently implemented. This means that in its current deployment keys are stored at only one peer, i.e., the peer responsible for each key is computed using Chord’s mechanism for assigning keys to peers.

1

The labels next to the peers indicate their addresses in the key space, i.e. P4 has address 4.

Peer P12 departs from the network.

    a) Which keys are irrevocably lost when peer P12 departs? [2 marks]

    b) Write down all  nger tables for all nodes prior to the departure of P12. [4 marks]

    c) After the departure of P12, all peers remove the routing table ( nger table) entries referencing peer 12. Assume that no new routing table entries are added. A search fails if it does not reach the correct peer corresponding to the searched key. Give an example of a search that starts at peer 19 and fails. List all visited peers in order. [4 marks]

    d) We say that an overlay network is routable if we can successfully search for all key addresses from all peers in the network. Is the overlay network routable after the departure of P12? Expain why or why not. [2 marks]

    e) If it is not routable, what is the smallest number of changes that you need to make to the routing tables at the peers to make the overlay network to make it routable? Specify the change(s). [2 marks]

    f) Suppose that peer P19 discovers that its successor link is no longer consistent, because peer P23 has updated its predecessor link. What must have happened in order for this to occur? [1 marks]

    g) Before peer P12 has departed, what is the expected number of hops required for a query to be resolved, if the query starts uniformly at random from one of the six peers and targets a key that is selected uniformly at random from the range [0,31]? [5 marks]






























2

Question 2 [20 marks]




E



1.5

Flow 1

C


2.5
Flow 5
A
3
B








4.5


Flow 2
D







1



Flow 4

F



Figure 2: Network for question 2. Each link is labelled with its capacity in Mb/s.


    a) For the network and ows in Figure 2 calculate the max-min fair ow allocations. Show all steps in the procedure you use to calculate them. [5 marks]

    b) For this network, is it possible to identify any allocation that has higher aggregate rate than the max-min fair allocation. (The aggregate rate is the sum of all rates allocated to all ows). Explain why or why not. [3 marks]

    c) What is a proportionally fair  ow allocation? [2 marks]

    d) Is the allocation (1; 2; 1:75; 0:75; 1:5) proportionally fair? Show why or why not. [4 marks]

    e) The fairness conditions and algorithms we have studied have assumed that each user ( ow) has in nite demand. Suppose that there is a nite demand vector d such that user r requests a rate of dr. This means that the user should not be allocated a rate higher than dr. The de nition of max-min fairness is now similar, but it focuses only on users whose demand has not been satis ed. A ow allocation x is max-min fair for a demand d if it is feasible and for any other feasible ow allocation y, if there exists yr > xr for xr < dr then there exists ys such that ys < xs xr.

Specify an algorithm that will identify a max-min fair allocation when there is a demand vector d. [4 marks]

    f) If the demand vector d is [1; 3; 3; 0:9; 2], identify the max-min fair ow rate allocation for the network and ows in Figure 2. [2 marks]




3

Question 3 [20 marks]
For a weight vector w = (wr; r 2 R), where R is the set of user ows, with A the link-route incidence matrix and c the corresponding vector of link capacities, the NETWORK(A; c; w) problem is de ned as:

X
maximize
wr log xr

r2R
subject to
Ax  c
over
x  0
In the lectures, we proposed the following dynamic algorithm for setting rates

0
d

dtxr(t) =  r @wr


0
X
j (t) = pj @


xr(t)
j (t)
1
;
r 2 R;
(1)
X

A



j2J (r)





xs(t)1;
j
2 J
:
(2)
A




s:j2J (s)

Here J is the set of links in the network and J (r) are the links traversed by route r. The function pj ( ) is positive, continuous and increasing and r is a scalar constant.

    a) Why is the solution to the NETWORK problem unique? [2 marks]

    b) Explain how the proposed dynamic algorithm works in performing congestion control and rate allocation. [5 marks]

    c) Explain how I can choose price functions so that the dynamic algorithm always converges (to within an arbitrarily close approximation) to the solution of the NETWORK(A; c; w) problem. [4 marks]

    d) Explain why this choice is not a practical solution when we consider networks with time delay. Provide a detailed explanation. [4 marks]

    e) You have implemented a version of the dynamic algorithm above, but modi ed it so that it takes into account the time delays in the network. You are now faced with the choice of the gain r for each route r. What aspects will a ect your decision for this value? What is the trade-o between choosing a large value and choosing a small value? [5 marks]
















4