August 5, 2018
1. [this problem worth 80 points total] Consider the example network shown in Figure 1. It is easy to see that the shortest paths from A to all other nodes are: (i) A ↔ B for reaching B, (ii) A ↔ B ↔ C for reaching C (tie broken arbitrarily), (iii) A ↔ D for reaching D, and (iv) A ↔ D ↔ E for reaching E. If you ‘join’ (think set union) all these edges, you get the shortest path tree (SPT), also shown in Figure 1, with a total cost of 6. Referring to the SPT, node A is known as the root of the tree (we also say that the tree is rooted in A). Of course, this is not the only possible shortest path tree. For example, you can replace the edge B ↔ C with D ↔ C without increasing the cost of the SPT. Coincidentally, the SPT for this network is also a minimum spanning tree (MST). You can verify using Prim’s algorithm that the cost of the MST is also 6.
Now consider the network shown in Figure 2.
(a) Using Dijkstra’s algorithm, find the shortest paths from node A to all other nodes. Include a table showing the minimum distance vector and the predecessor vector at each iteration, as shown in slide 14 of Part 2 of Chapter 5 notes. [25 points]
(b) Using the results in (a), sketch the SPT rooted in A. What is the total cost of the SPT? [5 points].
(c) Using Prim’s algorithm, find and sketch the MST rooted in A. What is the total cost of the MST? If you have finished Problem 1 of this test, you can use your code to find the MST. If not, you need to show all the iterative steps which lead to the MST. [25 points]
(d) Would the MST change if you were to root it in D (this tree structure would be needed if node D were to broadcast to everybody else)? Irrespective of whether the MST changes or not, sketch the MST rooted in D. [10 points]
(e) Based on (b) and (c), what can you infer regarding the SPT vis-a-vis the MST? Which tree would node A prefer to use if it wants to broadcast a message to all other nodes in the network? [5 points]
(f) Suppose node A is the source (or root) and it has the MST pre-computed and stored. Explain how it can quickly construct a multicast tree from the MST if it wants
Figure 1: (a) Left: example network for Problem 1. (b) Right: shortest path tree, rooted in A.
Figure 2: Network for Problem 1. This is the network you should use for answering the questions.
(a) Provide suitable IP addresses for the rest of the interfaces. Assume that a class C addressing scheme is used. [20 points]
(b) Given the addressing scheme in part (a), group all the interfaces into suitable ‘IP networks’ from an addressing perspective. Then, indicate the IP addresses of each of those networks. [10 points]
(c) Given the addressing scheme in part (a), determine the routing table of the de- vice/interface with an IP address of 126.96.36.199. You might want to take a look at slide 15 of Part 3 of Chapter 5 notes. [20 points]
Figure 3: Local Area Network (LAN) for Problem 2.
One flip side of message segmentation which was ignored in slides 13 and 14 is the effect of overhead bits. In practice, when a message is segmented into several packets, each packet incurs an overhead because some header and trailer bits need to be appended. Let us define the following parameters:
• M = the size of a message (before segmentation) in bits, • N = the number of packets the message is segmented into, and • H = the number of overhead bits per message (no segmentation) or per packet
The actual number of bits transmitted when the message is not segmented is therefore M +H. Conversely, when the message is segmented, the number of bits in each packet is M
N + H, where we have assumed that M
N (number of data bits in each packet) is an
integer. The total number of bits transmitted is therefore N ( M N
= M + NH. (this problem is worth 70 points total)
(a) Calculate the end-to-end delay when the message is sent without segmentation over L hops, the data rate of each hop being R bps. Assume negligible propagation delay over each hop. Your answer should be in terms of M , H, R and L. In the context of slide 13, M = 3 × 106 bits, H = 0 bits R = 106 bps, L = 3 hops and the end-to-end delay is 9 seconds. [10 points]
(b) Calculate the end-to-end delay when the message is segmented into N packets and each packet is transmitted over L hops, the data rate of each hop being R bps. Assume negligible propagation delay over each hop. Your answer should be in terms of M , N , H, R and L. In the context of slide 14, M = 3× 106 bits, N = 3 packets, H = 0 bits, R = 106 bps L = 3 hops and the end-to-end delay is 5 seconds. [20 points]
(c) We can now define an end-to-end throughput measure, γ (in bps), as follows:
γ = number of data bits delivered
end-to-end delay ,
where the numerator is M irrespective of message switching or packet switching. Next, define an end-to-end efficiency measure, η, as follows:
η = γ
Write down an expression for η when packet switching is used. [5 points]
(d) Using your result in part (c), superimpose the plots of η (in %) vs. N for H = 0 and H = 100 bits in one figure (use different line types). Other parameters are as follows: (i) M = 2 Kb, (ii) N = 2 : 2 : 100 in MATLAB notation, (iii) R = 1 Kbps
(e) Using your result in part (b), plot the end-to-end delay vs. N for H = 100 bits. Other parameters are as follows: (i) M = 2 Kb, (ii) N = 2 : 2 : 100 in MATLAB notation, (iii) R = 1 Kbps and (iv) L = 10. Be sure to label the axes. What do you think is the best choice of N from an end-to-end delay standpoint? Using engineering judgement, what value of N would you choose considering both efficiency and end-to- end delay? [15 points]