1. Slides 13 and 14 in Chapter 5 notes illustrate through an example how message segmentation can reduce end-to-end delay. In this problem, you are being asked to derive generalized results, including the effect of propagation delay, which was ignored when you solved this problem in Midterm-2. Drawing diagrams would help you answer this problem correctly.

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 segment al ion) 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 (with segmentation).
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 + H, where we have assumed that M (number of data bits in each packet) is an integer. The total number of bits transmitted is therefore N + = M + NH.

(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 that the propagation delay over each hop is tprop. Your answer should be in terms of tprop, M, H, R and L. In the context of slide 13, tprop = 0, M = 3 x 106 bits, H = 0 bits, R= 106 bps, L = 3 hops and the end-to-end delay is 9 seconds.

(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 that the propagation delay over each hop is tpro,p. Your answer should be in terms of tprop, M, N, H, R and L. In the context of slide 14, tproi, = 0, M = 3 x 106 bits, N = 3 packets, H = 0 bits, R = 106 bps, L = 3 hops and the end-to-end delay is 5 seconds.

(c) We can now define an end-to-end throughput measure, 7 (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, n, as follows:

Write down an expression for 77 when packet switching is used.

(d) Using your result in part (c), superimpose the plots of n (in %) vs. N for tprop = 0.1, 0.2, 0.5, 1.0 sec. 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, (iv) H = 100 bits and (iv) L = 5. Be sure to label the axes and provide an appropriate legend. What do you think is the best choice of N from an efficiency standpoint? Does your answer change depending on the value of tprop?

(e) Using your result in part (b), plot the end-to-end delay vs. N for H = 100 bits. vs. N for tprop = 0.1, 0.2, 0.5, 1.0 sec. 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, (iv) H = 100 bits and (iv) L = 5. Be sure to label the axes and provide an appropriate legend. What do you think is the best choice of N from an efficiency standpoint? Does your answer change depending on the value of tprop? Using engineering judgement, what value of N would you choose considering both efficiency and end-to-end delay?

2. Consider the 6-node network in Fig. 1 where link costs reflect capacities in Mbps. The bottleneck capacity of a path is defined as the minimum of the capacities of the edges constituting the path. For example, the bottleneck capacity of the path (A44.13i4Dt4F) is the minimum of the capacities of (A 44 B), (B D) and (D F) = min(50,10,100) = 10. Quite obviously, we would like to find paths which maximize the bottleneck capacities. Some simple modifications to Dijkstra's algorithm will allow us to solve this problem.

When we are trying to I minimize I the cost of a path, and cost of a path = I sum I of the costs of hops constituting a path, a key step in Dijkstra's algorithm is as follows:

Let p(x, y) denote the best cost of going from node x to y and Cxy denote the (x, y)th element of the link cost matrix. When node j has been 'reached' (label set) at any iteration from node i (the source), the source compares p(i, k), where k is a node 'not yet reached' (label not yet set), to p(i, j) + C3k. If p(i,j) 0 Cik121 (1) the source knows that a *better* route has been found to k, via j, and it updates p(i, k) as follows:

p(i, k) <- p(i, i) II Cjk (2)

Note that the boxed term 'minimize' maps to the `<' sign in eqn. (1) while the boxed term 'sum' maps to the `+' signs on the l.h.s of eqn. (1) and the r.h.s of eqn. (2). Read the previous sentence very, very carefully.

When solving a bottleneck capacity problem, we are seeking to maximize' the cost of a path, and cost of a path = I minimum of the costs of hops constituting a path. How should you modify eqns. (1) and (2) so that you can solve bottleneck capacity type problems?

Two other modifications are necessary for solving bottleneck capacity type problems. Usually, if nodes i and j are not directly connected, we set Cii = oo. Is the oo value still going to work? And finally, at any iteration, we usually set the label of the node which corresponds to the minimum of the distance vector. Is this still going to work?

After you have figured out the necessary modifications, find the set of optimal paths from node B to all other nodes in Fig. 1 such that the bottleneck capacities of the paths are maximized.

You will need to include the following with your test:

(a) How should eqns. (1) and (2) be modified for solving bottleneck capacity type problems? How should Ca, be set if nodes i and j are not directly connected? At any iteration, how should you pick the node whose label is to be set?

(b) The link cost matrix of the network which you used for computing the optimal paths.

(c) Fill in Table 1, which is similar in format to the one shown in slide 38 of Chapter 5 notes.

(d) Fill in Table 2, which shows the optimal paths from the source (node B) to all other nodes, along with the bottleneck capacities of the paths.