Skip to content
Textbook Guides

Solution Manual For Data Networks, 2nd Edition

Solution Manual For Data Networks, 2nd Edition provides expert solutions to textbook questions, making complex problems easier to solve.

Preview 16 of 164 pages

See the first 16 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    SOLUTIONS MANUAL | Second Edition DIMITRI BERTSEKAS Massachuserts Institute of Technology ROBERT GALLAGER Massachusetts Institute of Technology PRENTICE HALL, Upper Saddle River, New Jersey 07458

  2. Page 2
    Read page 2 as text

    Downloaded from StudyXY.com ® + StudyXY Sd Ye. o> \ | iF ’ pr E \ 3 S Stu dy Anything This ContentHas been Posted On StudyXY.com as supplementary learning material. StudyXY does not endrose any university, college or publisher. Allmaterials posted are under the liability of the contributors. wv 8) www.studyxy.com

  3. Page 3
    Read page 3 as text

    Solutions Manual -- Data Networks, 2/E by Dimitri Bertsekas and Robert Gallager TABLE OF CONTENTS CHAPTER 3 toouueereereereseessses sees sess ssssssssssssassssse sess sess sssssssssssassnsssssssossessesesssmsensnsessossessssseenses 23 CHAPTER 4 cooovoneereenenee sees esssssssssasasassnssssssssssesssessessssssssssasnnsns asses sosessessassnsessesssssseneess | CHAPTER © coveveaeerneesseeecemmaaensssssessesssesssesesasmssmsenesssessssssssssssssssessansssessassssesesssesmsnesssssssessseees 148 + StudyXY

  4. Page 4
    Read page 4 as text

    CHAPTER 1 SOLUTIONS 1.1 There are 250,000 pixels per square inch, and multiplying by the number of square inches and the number of bits per pixel gives 5.61 x 108 bits. 1.2 a) There are 16 x 109 bits going into the network per hour. Thus there are 48 x 109 bits per hour traveling through the network, or 13.33 million bits per second. This requires 209 links of 64 kbit/sec. each. b) Since a telephone conversation requires two people, and 10% of the people are busy on the average, we have 50,000 simultaneous calls on the average, which requires 150,000 links on the average. Both the answer in a) and b) must be multiplied by some factor to provide enough links to avoid congestion (and to provide local access loops to each telephone), but the point of the problem is to illustrate how little data, both in absolute and comparative terms, is required for ordinary data transactions by people. 1.3 There are two possible interpretations of the problem. In the first, packets can be arbitrarily delayed or lost and can also get out of order in the network. In this interpretation, if a packet from A to B is sent at time T and not received by some later time t, there is no way to tell whether that packet will ever arrive later. Thus if any data packet or protocol packet from A to B is lost, node B can never terminate with the assurance that it will never receive another packet. In the second interpretation, packets can be arbitrarily delayed or lost, but cannot get out of order. Assume that each node is initially in a communication state, exchanging data packets. Then each node, perhaps at different times, goes into a state or set of states in which it sends protocol packets in an attempt to terminate. Assume that a node can enter the final termination state only on the receipt of one of these protocol packets (since timing information cannot help, since there is no side information, and since any data packet could be followed by another data packet). As in the three army problem, assume any particular ordering in which the two nodes receive protocol packets. The first node to receive a protocol packet cannot go to the final termination state since it has no assurance that any protocol packet will ever be received by the other node, and thus no assurance that the other node will ever terminate. The next protocol packet to be received then finds neither node in the final termination state. Thus again the receiving node cannot terminate without the possibility that the other node will receive no more protocol packets and thus never terminate. The same situation occurs on each received protocol packet, and thus it is impossible to guarantee that both nodes can eventually terminate. This is essentially the same argument as used for the three army problem. — StudyXY

  5. Page 5
    Read page 5 as text

    CHAPTER 2 SOLUTIONS 2.1 Let x(t) be the output for the single pulse shown in Fig. 2.3(a) and let y(t) be the output for the sequence of pulses in Fig. 2.3(b). The input for 2.3(b) is the sum of six input pulses of the type in 2.3(a); the first such pulse is identical to that of 2.3(a), the second is delayed by T time units, the third is inverted and delayed by 2T time units, etc. From the time invariance property, the response to the second pulse above is x(t-T) (i.e. x(t) delayed by T); from the time invariance and linearity, the response to the third pulse is -x(t-2T). Using linearity to add the responses to the six pulses, the overall output is y(©) = x(®) + x(t-T) - x(t-2T) + x(t-3T) -x(t-4T) - x(t-5T) To put the result in more explicit form, note that 0 H t<0 XO = J1_g ; 0<t<T Ene t>T Thus the response from the ith pulse (1 <i < 6) is zero up to time (i-1)T. For t <0, then, y© =0;from0<t<T yO=x@®=1-¢2T ;0<t<T From T <1t< 2T, y(©) = x(t) + x(t-T) =(e2-1)eT 4 [1 - £20 DM =1- eT Similarly, for 2T £t < 3T, y(®) = x(t) + x(t-T) - x(t-2T) = (€2-1)e VT + (2-1)e 2 T/T _[] _ e202DIT) =-1+Qet1)e?T ; 2T<t<3T A similar analysis for each subsequent interval leads to y(t) = 1-(2e6-2e4 + 1)e2/T ; 3T<t<4T =-1+(2e8-2e6+2e4- eT; 4T<t<6T =-(e12-2e8 + 2e6-2et+ eT | 126T + StudyXY

  6. Page 6
    Read page 6 as text

    The solution is continuous over t with slope discontinuities at 0, 2T, 3T, 4T, and 6T; the value of y(t) at these points is y(0) = 0; y2T) = .982; y(3T) = -.732; y(4T) = .766; y(6T) = -968. Another approach to the problem that gets the solution with less work is to use x(t) to first fin the response to a unit step and then view y(t) as the response to a sum of displaced unit steps. 2.2 From the convolution equation, Eq. (2.1), the output (t) is - T rt) = I s(Dh(t-t)dt = I h(t-t)dt ~ =0 Note that h(t-T) = oe *t-0 for t-1 > 0, (i.e. for t<t), and h(t-t) =0 for t>t. Thus fort< 0, h(t-) = 0 throughout the integration interval above. For 0 <t<T, we then have t T w= ears | 0dr =1-¢™ ;0<t<T =0 = Fort 2 T, h(t-T) = 0e"*(t-® over the entire integration interval and T 0) =] ae Vgr = Dg > T =0 Thus the response increases towards 1 for 0 <t <T with the exponential decay factor a, and then, for t > T, decays toward 0. 2.3 From Eg. (2.1), = | 7 hyde Using T' = t-T as the variable of integration for any given t, = | ST p(t dr _ om I (pyar = 2g where H(f) is as given in Eq. (2.3). 2.4 +oo h(t) = [ H(fel2nfdf + StudyXY

  7. Page 7
    Read page 7 as text

    Since H(f) is 1 from fg to fo and 0 elsewhere, we can integrate exp(j2rft) from -fj to fo, obtaining bn 1 of rf] = sin(2nfor) (1) = Zrlexpl nfl) — exp(—i2nfyt)] = — Note that this impulse response is unrealizable in the sense that the response starts before the impulse (and, even worse, starts an infinite time before the impulse). None the less, such ideal filters are useful abstractions in practice. 2.5 The function s1(t) is compressed by a factor of B on the time axis as shown below -A A -AR AR S,(f) = i 5; (e2dr = I (Bye 2d = i dt 1 (f =| seo 5s(%) [so BBB S(f) Thus S(f) is attenuated by a factor of B in amplitude and expanded by a factor of § on the frequency scale; compressing a function in time expands it in frequency and vice versa. 2.6 a) We use the fact that cos(x) = [exp(jx) + exp(-jx)]/2. Thus the Fourier transform of s(t)cos(2nfor) is = exp(j2rfyt) + exp(—j2nfyt I sp TREE 7 PCR) exp(—j2nft) dt = Ru exp[—2n(f-fo)] dt + 0 expl[—j2n(f+fo) dt S(f-fy) S(f+fy) ST tz + StudyXY

  8. Page 8
    Read page 8 as text

    b) Here we use the identity cos2(x) = [1+cos(2x)}/2. Thus the Fourier transform of s(t)cos2(2pfot) is the Fourier transform of s(t)/2 plus the Fourier transform of s(t)cos[2p(2fp)t]/2. Using the result in part a, this is S()/2 + S(f-2fo)/4 +S(f+2fp)/4. 2.7 a) E{frame time on 9600 bps link} = 1000 bits / 9600 bps = 0.104 sec. E {frame time on 50,000bps link} = 0.02 sec. b) E{time for 106 frames on 9600 bps link} = 1.04-105 sec. E{time for 106 frames on 50,000 bps link} = 2-104 sec. Since the frame lengths are statistically independent, the variance of the total number of bits in 106 frames is 106 times the variance for one frame. Thus the standard deviation of the total number of bits in 106 frames is 103 times the standard deviation of the bits in one frame or 5:10 bits. The standard deviation of the transmission time is then S.D. {time for 106 frames on 9600 bps link} = 5-105 / 9600 = 52 sec. S.D. {time for 106 frames on 50,000 bps link} = 5:105/ 50,000 = 10 sec. ¢) The point of all the above calculations is to see that, for a large number of frames, the expected time to transmit the frames is very much larger than the standard deviation of the transmission time; that is, the time per frame, averaged over a very long sequence of frames, is close to the expected frame time with high probability. One's intuition would then suggest that the number of frames per unit lime, averaged over a very long time period, is close to the reciprocal of the expected frame time with high probability. This intuition is correct and follows either from renewal theory or from direct analysis. Thus the reciprocal of the expected frame time is the rate of frame transmissions in the usual sense of the word "rate". 2.8 Let xij be the bit in row i, column j. Then the ith horizontal parity check is hi = Zj xj where the summation is summation modulo 2. Summing both sides of this equation (modulo 2) over the rows i, we have Zihi = Zij xij This shows that the modulo 2 sum of all the horizontal parity checks is the same as the modulo 2 sum of all the data bits. The corresponding argument on columns shows that the modulo 2 sum of the vertical parity checks is the same. + StudyXY

  9. Page 9
    Read page 9 as text

    2.9 a) Any pattern of the form --110-- —--011-- —-101-- will fail to be detected by horizontal and vertical parity checks. More formally, for any three rows iy, i2, and i3, and any three columns jj, j2, and 3, a pattern of six errors in positions (i130), (31 72)» (2 J2)» (i2 j3)» (3 j1), and (i3 j3) will fail to be detected. b) The four errors must be confined to two rows, two errors in each, and to two columns, two errors in each; that is, geometrically, they must occur at the vertices of a rectangle within the array. Assuming that the data part of the array is J by K, then the array including the parity check bits is J+1 by K+1. There are (J+1)J/2 different possible pairs of rows (counting the row of vertical parity checks), and (K+1)K/2 possible pairs of columns (counting the column of horizontal checks). Thus there are (J+1)(K+1)JK/4 undetectable patterns of four errors. 2.10 Let x = (x1, X2, -- XN) and x’ = (x'}, X'2, --- X'N) be any two distinct code words in a parity check code. Here N = K+L is the length of the code words (K data bits plus L check bits). Let y = (y1, - YN) be any given binary string of length N. Let D(x,y) be the distance between x and y (i.e. the number of positions i for which x; # y;). Similarly let D(x',y) and D(x,x’) be the distances between x' and y and between x and x'. We now show that D(x.x") < D(x,y) + D(x"y) To see this, visualize changing D(x,y) bits in x to obtain y, and then changing D(x',y) bits in y to obtain x". If no bit has been changed twice in going from x to y and then to x', then it was necessary to change D(x,y) + D(x,y) bits to change x to x’ and the above inequality is satisfied with equality. If some bits have been changed twice (i.e. x; = Xj # yj for some i) then strict inequality holds above. By definition of the minimum distance d of a code, D(x,x) 2 d. Thus, using the above inequality, if D(x,y) < d/2, then D(x"y) >d/2. Now suppose that code word x is sent and fewer than d/2 errors occur. Then the received string y satisfies D(x,y) < d/2 and for every other code word x', D(x',y) > d/2. Thus a decoder that maps y into the closest code word must select x, showing that no decoding error can be made if fewer than d/2 channel errors occur. Note that this argument applies to any binary code rather than just parity check codes. 2.11 The first code word given, 1001011 has only the first data bit equal to 1 and has the first, third, and fourth parity checks equal to 1. Thus those parity checks must check on the first data bit. Similarly, from the second code word, we see that the first, second, and fourth parity checks must check on the second bit. From the third code word, the first, second, and third parity check each check on the third data bit. Thus + StudyXY

  10. Page 10
    Read page 10 as text

    C1 =S81+82+583 cp =572 +83 c3=5] +83 C4=81 +82 The set of all code words is given by 0000000 0011110 1001011 1010101 0101101 0110011 1100110 1111000 The minimum distance of the code is 4, as can be seen by comparing all pairs of code words. An easier way to find the minimum distance of a parity check code is to observe that if x and x' are each code words, then x + x' (using modulo 2 componentwise addition) is also a code word. On the other hand, x + x' has a 1 in a position if and only if x and x’ differ in that position. Thus the distance between x and x' is the number of ones in x +x". It follows that the minimum distance of a parity check code is the minimum, over all non- zero code words, of the number of ones in each code word. 2.12 D p*+p%D+1) D'+D+D? p’+Dp%p*+D’ p? = Remainder 2.13 Let z(D)=Di+ zj. Di"! +..+ Di and assume i<j. Multiplying G(D) times Z(D) then yields g(D)z(D) = DL + (zj.1 + gL. )DLA + (72 + g17j-1 + gL) 2 + +(g1 + zi)DI*1 + Di Clearly the coefficient of DL+j and the coefficient of Di are each 1, yielding the desired two non-zero terms. The above case i<j arises whenever z(D) has more than one non-zero term. For the case in which z(D) has only one non-zero term, i.e. z(D) = Dj for some j, we have g(D)z(D) = DL#j + gi | DL#i-1 + + Di which again has at least two non-zero terms. 2.14 Suppose g(D) contains (1+D) as a factor; thus g(D) = (1+D)h(D) for some polynomial h(D). Substituting 1 for D and evaluating with modulo 2 arithmetic, we get g(1) = 0 because of the term (1+D) = (1+1) = 0. Let e(D) be the polynomial for some arbitrary undetectable error sequence. Then e(D) = g(D)z(D) for some z(D), and hence e(1) = g(1)z(1) = 0. Now e(D) = Z; eiD}, so e(1) = Zi ej. Thus e(1) = 0 implies that an even number of elements ej + StudyXY

  11. Page 11
    Read page 11 as text

    are 1; i.e. that e(D) corresponds to an even number of errors. Thus all undetectable error sequences contain an even number of errors; any error sequence with an odd number of errors is detected. 2.15 a) Let Di*L, divided by g(D), have the quotient z®(D) and remainder c®(D) so that Di+L = gD)z()(D) + ci}(D) Muitiplying by s; and summing over i, s(D)DL = 5; 5iz®(D) + Z; sic(D) Since Z; sic®(D) has degree less than L, this must be the remainder (and Z; siz@(D) the quotient) on dividing s(D)DL by g(D). Thus ¢(D) = %; sic)(D). b) Two polynomials are equal if and only if their coefficients are equal, so the above polynomial equality implies cj = Zi sici® 2.16 a) Consider the two scenarios below and note that these scenarios are indistinguishable to the receiver. of x] ol x | K \ fA packet 1 9 accepted + StudyXY

  12. Page 12
    Read page 12 as text

    or packet 1 9 accepted If the receiver releases the packet as x3 in the questioned reception, then an error occurs on scenario 2. If the receiver returns an ack but doesn't release a packet (i.e. the appropriate action for scenario 2), then under scenario 1, the transmitter erroneously goes on to packet 3. Finally, if the receiver returns a nak, the problem is only postponed since the transmitter would then transmit (2,x7) in scenario 1 and (2,x1) in scenario 2. As explained on page 66, packets x and x; might be identical bit strings, so the receiver can not resolve its ambiguity by the bit values of the packets. b) The scenarios below demonstrate incorrect operation for the modified conditions. ol x |] [of x» | [1] x packet 1 9 accepted ) [ox] packet 1 9? accepted + StudyXxy

  13. Page 13
    Read page 13 as text

    2.17 a) T=Ti+Ts+2T4 b) q = (1-po(1-pp) A packet is transmitted once with probability q, twice with probability (1-q)q, three times with probability (1-q)2g, etc. Thus the expected number of transmissions of a given packet is x 1 E{transmissions per packet} = y iq1—q)"™ = 3 i=l To verify the above summation, note that forany x,0 <x <1, Ce Vd dN TER 1 2x “2% =m x Tax\Tx) Tq? i=1 i=l iol (1-x) Using x for (1-q) above gives the desired result. ©) E({tme per packet} = (T; + Tr + 2T@)/q =(1.3)/0.998 = 1.303 Note that p; and pg have very little effect on E[time per packet] in stop and wait systems unless they are unusually large. 2.18 0 Packets 1 2 3 4 6 delivered 4 IC NC A NE Node A \A/ \/ \# t —p A sn| © 1 2 3 4 | s|e Window [0,3] [1,4] 2,51 |[3.61|(4.71 + StudyXxy

  14. Page 14
    Read page 14 as text

    Assume that the transmitter always sends the next packet in order until reaching the end of the window, and then goes back to the beginning of the window. 0 Packets 1 2 delivered RN oTol of v Ju [1 | Node A \A \f \f \/ \/ \/ t— Window [0.3] [1,4] [2,5] 2.19 The simplest such deadlock occurs if there is sufficient propagation delay in the system that each side can send n-1 frames (containing packets numbered 0 to n-2) before finishing receipt of the first frame from the other side. In this case, the nth frame from each side will carry the packet numbered n-1 without acking any packets from the other side. Thus each side will go back to packet 0, but in the absence of errors, each side will be looking for packet n by time the repeat of packet 0 occurs. Each side will then cycle from 0 to n-1, and neither side will ever receive any acks. The diagram below illustrates this for n=3. The first number in each frame position is SN and the second is RN. 0 1 2 (0,0) 2,0) (0,0) (1,0) NN PO PaPaVaVaN 0,0) (1,0) (2,0) 0,0) (1,0) 0 1 2 2.20 The simplest example is for node A to send packets 0 through n-1 in the first n frames. In case of delayed acknowledgements (i.e. no return packets in the interim), node A goes back and retransmits packet 0. If the other node has received all the packets, it is waiting for packet n, and if the modulus m equals n, this repeat of packet 0 is interpreted as packet n. + StudyXxy

  15. Page 15
    Read page 15 as text

    The right hand side of Eq. (2.24) is satisfied with equality if SN = SNpn(t;)+n-1. This occurs if node A sends packets 0 through n-1 in the first n frames with no return packets from node B. The last such frame has SN = n-1, whereas SNp;, at that time (say t;) is 0. Continuing this scenario, we find an example where the right hand side of Eq. (2.25) is satisfied with equality. If all the frames above are correctly received, then after the last frame, RN becomes equal to n. If another frame is sent from A (now call this time t;) and if SN is still O, then when it is received at B (say at tp), we have RN(t2) = SNppn(t1)+n. 2.21 Let RN(t) be the value of RN at node B at an arbitrary time T; SNp;n is the smallest packet number not yet acknowledged at A at time t (which is regarded as fixed) and SNmax -1 is the largest packet number sent from A at time t. Since RN(1) is non decreasing in 7, it is sufficient to show that RN(t+Tp+Tg) € SNpax and to show that RN(t-Try-Tq) 2 SNpjn. For the first inequality, note that the packet numbered SNyax (by definition of SNpax) has not entered the DLC unit at node A by time t, and thus can not have started transmission by time t. Since there is a delay of at least Tm+T4 from the time a packet transmission starts until the completion of its reception, packet SNpax can not have been received by time t+Tp+T4. Because of the correcmess of the protocol, RN(t+Ty+Tg) can be no greater than the number of a packet not yet received, i.e. SNmax. For the second inequality, note that for the transmitter to have a given value of SNpp at time t, that value must have been transmitted earlier as the request number in a frame coming back from node B. The latest time that such a frame could have been formed is t- Tm-T4, so by this time RN must have been at least SNmin. 2.22 a) If the transmitter never has to go back or wait in the absence of errors, then it can send a continuous stream of new packets in the absence of errors. In order for such a continuous stream to be sent, each packet must be acknowledged (i.e. SNp;n must advance beyond the packet's number) before the next n-1 frames complete transmission. Thus these n-1 frame transmission times are in a race with the time, first, for the given packet to propagate over the channel and, second, for the acknowledgement to wait for the feedback frame in progress, then wait to be transmitted in the next feedback frame and propagated back to the original transmitter. In order for the feedback to always win the race, the minimum time for the n-1 frames to be transmitted must be greater than the maximum time for the feedback, i.e., (0-1) Tin > 2Td + 2Tmax Tmax < [(0-1)/2] Tin - Tq b) If an isolated error occurs in the feedback direction, the feedback could be held up for one additonal frame, leading to (0-1) Tmin > 2Td + 3Tmax Tmax < [(0-1)/3]Tmin - (2/3)Tq + StudyXY

  16. Page 16
    Read page 16 as text

    2.23 After a given packet is transmitted from node A, the second subsequent frame transmission termination from B carries the acknowledgement (recall that the frame transmission in progress from B when A finishes its transmission cannot carry the ack for that transmission; recall also that propagation and processing delays are negligible. Thus q is the probability of n-1 frame terminations from A before the second frame termination from B. This can be rephrased as the probability that out of the next n frame terminations from either node, either n-1 or n come from node A. Since successive frame terminations are equally likely and independently from A or B, this probability is n _ nl on _ -n a= p Tan 2 - @*2 i=n-1 2.24 If an isolated error in the feedback direction occurs, then the ack for a given packet is held up by one frame in the feedback direction (i.e., the number RN in the feedback frame following the feedback frame in error reacknowledges the old packet as well as any new packet that might have been received in the interim). Thus q is now the probability of n-1 frame terminations from A before 3 frame terminations from B (one for the frame in progress, one for the frame in error, and one for the frame actually carrying the ack; see the solution to problem 2.23). This is the probability that n-1 or more of the next n+1 frame terminations come from A; since each termination is from A or B independently and with equal probability, [a+] _ n : -n-1 -n-1 CED) ; a 2 [n+2+(n+ 1)n/2]2 i=n-1 2.25 As in the solution to problem 2.23, q is the probability of n-1 frame terminations coming from node A before two frame terminations come from node B. Frame terminations from A (and similarly from B) can be regarded as alternate points in a Poisson point process from A (or from B). There are two cases to consider. In the first, the inital frame is received from A after an even numbered point in the Poisson process at B, and in the second, the initial frame is received after an odd numbered point. In the first case, q is the probability that 2n-2 Poisson events from A occur before 4 Poisson events occur from B. This is the probability, in a combined Poisson point process of Poisson events from A and B, that 2n-2 or more Poisson events come from A out of the next 2n+1 events in the combined process. In the second case, q is the probability that 2n-2 Poisson events from A occur before 3 events occur from B. Since these cases are equally likely, 2n+1 @n+1)! 2n Qn)! 1 n+)! \oon1 |g nm)! | ,-2n a=13 5 Lo) =p ; SE: 2.40 i1(2n+1-1)! 2.4, il(2n-i)! 2.26 We view the system from the receiver and ask for the expected number of frames, 7, arriving at the receiver starting immediately after a frame containing a packet that is accepted + StudyXY

148 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Information Technology study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.