Arq Selective Repeat Diagram

a. Suppose that the data link control just transfers frames and does not implement error control. Find the probability that the message arrives without errors at station p.

b. Suppose that error recovery is carried out end to end and that if there are any errors, the entire message is retransmitted. How many times does the message have to be retransmitted on average?

c. Suppose that the error recovery is carried out end to end on a packet by packet basis. What is the total number of packet transmissions required to transfer the entire message?

4. Suppose that two peer-to-peer processes provide a service that involves the transfer of discrete messages. Suppose that the peer processes are allowed to exchange PDUs that have a maximum size of M bytes, including H bytes of header. Suppose that a PDU is not allowed to carry information from more than one message.

a. Develop an approach that allows the peer processes to exchange messages of arbitrary size.

b. What essential control information needs to be exchanged between the peer processes?

c. Now suppose that the message transfer service provided by the peer processes is shared by several message source-destination pairs. Is additional control information required, and if so, where should it be placed?

5. Suppose that two peer-to-peer processes provide a service that involves the transfer of a stream of bytes. Suppose that the peer processes are allowed to exchange PDUs that have a maximum size of M bytes, including H bytes of header.

a. Develop an approach that allows the peer processes to transfer the stream of bytes in a manner that uses the transmission line efficiently. What control information is required in each PDU?

b. Suppose that the bytes in the stream arrive sporadically. What is a reasonable way to balance efficiency and delay at the transmitter? What control information is required in each PDU?

c. Suppose that the bytes arrive at a constant rate and that no byte is to be delayed by more than T seconds. Does this requirement have an impact on the efficiency?

d. Suppose that the bytes arrive at a variable rate and that no byte is to be delayed by more than T seconds. Is there a way to meet this requirement?

6. Suppose that two peer-to-peer processes provide a service that involves the transfer of a stream of bytes. Develop an approach that allows the stream transfer service to be shared by several pairs of users in the following cases:

a. The bytes from each user pair arrive at the same constant rate.

b. The bytes from the user pairs arrive sporadically and at different rates.

7. Consider the transfer of a single real-time telephone voice signal across a packet network. Suppose that each voice sample should not be delayed by more than 20 ms.

a. Discuss which of the following adaptation functions are relevant to meeting the requirements of this transfer: handling of arbitrary message size; reliability and sequencing; pacing and flow control; timing; addressing; and privacy, integrity, and authentication.

b. Compare a hop-by-hop approach to an end-to-end approach to meeting the requirements of the voice signal.

8. Suppose that a packet network is used to transfer all the voice signals that arrive at the base station of a cellular telephone network to a telephone office. Suppose that each voice sample should not be delayed by more than 20 ms.

a. Discuss which of the following adaptation functions are relevant to meeting the requirements of this transfer: handling of arbitrary message size; reliability and sequencing; pacing and flow control; timing; addressing; and privacy, integrity, and authentication.

b. Are the requirements the same in the opposite direction from the telephone office to the base station?

c. Do the answers to parts (a) and (b) change if the signals arriving at the base station include e-mail and other short messages?

9. Suppose that streaming video information is transferred from a server to a user over a packet network.

a. Discuss which of the following adaptation functions are relevant to meeting the requirements of ths transfer: handling of arbitrary message size; reliability and sequencing; pacing and flow control; timing; addressing; and privacy, integrity, and authentication.

b. Suppose that the user has basic VCR features through control messages that are transferred from the user to the server. What are the adaptation requirements for the control messages?

10. Discuss the merits of the end-to-end versus hop-by-hop approaches to providing a constant transfer delay for information transferred from a sending end system to a receiving end system.

11. Consider the Stop-and-Wait protocol as described in the chapter. Suppose that the protocol is modified so that each time a frame is found in error at either the sender or receiver, the last transmitted frame is immediately resent.

a. Show that the protocol still operates correctly.

b. Does the state transition diagram need to be modified to describe the new operation?

c. What is the main effect of introducing the immediate-retransmission feature?

12. In Stop-and-Wait ARQ why should the receiver always send an acknowledgment message each time it receives a frame with the wrong sequence number?

13. Discuss the factors that should be considered in deciding whether an ARQ protocol should act on a frame in which errors are detected.

14. Suppose that a network layer entity requests its data link layer to set up a connection to another network layer entity. In order to set up a connection in a data link, the initiating data link entity sends a SETUP frame, such as SABM in Figure 5.37. Upon receiving such a frame, the receiving data link entity sends an acknowledgment frame confirming receipt of the SETUP frame. Upon receiving this acknowledgment, the initiating entity can inform its network layer that the connection has been set up and is ready to transfer information. This situation provides an example of how unnumbered acknowledgments can arise for confirmed services.

a. Reexamine Figure 5.9 and Figure 5.10 with respect to error events that can take place and explain how these events are handled so that connection setup can take place reliably.

b. To terminate the connection, either data link layer can send a DISC frame that is then acknowledged by an unnumbered acknowledgment. Discuss the effect of the above error events and how they can be dealt with.

c. Suppose that an initiating station sends a SETUP frame twice but that the corresponding ACK times are delayed a long time. Just as the ACK frames from the original transmissions are about to arrive, the initiating station gives up and sends a DISC frame followed by another SETUP frame. What goes wrong if the SETUP frame is lost?

15. A 1 Mbyte file is to be transmitted over a 1 Mbps communication line that has a bit error rate of p = 10-6.

a. What is the probability that the entire file is transmitted without errors? Note for n large and p very small, (1 — p)n ^ e-np.

b. The file is broken up into N equal-sized blocks that are transmitted separately. What is the probability that all the blocks arrive without error? Is dividing the file into blocks useful?

c. Suppose the propagation delay is negligible, explain how Stop-and-Wait ARQ can help deliver the file in error-free form. On the average how long does it take to deliver the file if the ARQ transmits the entire file each time?

d. Now consider breaking up the file into N blocks. (Neglect the overhead for the header and CRC bits.) On the average how long does it take to deliver the file if the ARQ transmits the blocks one at a time? Evaluate your answer for N = 80, 800, and 8000.

e. Explain qualitatively what happens to the answer in part (d) when the overhead is taken into account.

16. Consider the state transition diagram for Stop-and-Wait ARQ in Figure 5.11. Let p be the probability of frame error in going from station A to station B and let Pa be the probability of ACK error in going from B to A. Suppose that information frames are two units long, ACK frames are one unit long, and propagation and processing delays are negligible. What is the average time that it takes to go from state (0,0) to state (0,1)? What is the average time that it then takes to go from state (0,1) to state (1,1)? What is the throughput of the system in information frames/second?

17. Write a program for the transmitter and the receiver implementing Stop-and-Wait ARQ over a data link that can introduce errors in transmission. Assume station A has an unlimited supply of frames to send to station B. Only ACK frames are sent from station B to station A. Hint: Identify each event that can take place at the transmitter and receiver and specify the required action.

18. A 64-kilobyte message is to be transmitted from the source to the destination, as shown on the next page. The network limits packets to a maximum size of two kilobytes, and each packet has a 32-byte header. The transmission lines in the network have a bit error rate of 10-6, and Stop-and-Wait ARQ is used in each transmission line. How long does it take on the average to get the message from the source to the destination? Assume that the signal propagates at a speed of 2 x 105 km/second.

19. Suppose that a Stop-and-Wait ARQ system has a time-out value that is less than the time required to receive an acknowledgment. Sketch the sequence of frame exchanges that transpire between two stations when station A sends five frames to station B and no errors occur during transmission.

20. The Trivial File Transfer Protocol (RFC 1350) is an application layer protocol that uses the Stop-and-Wait protocol. To transfer a file from a server to a client, the server breaks the file into blocks of 512 bytes and sends these blocks to the client using Stop-and-Wait ARQ. Find the efficiency in transmitting a 1 MB file over a 10 Mbps Ethernet LAN that has a diameter of 300 meters. Assume that the transmissions are error free and that each packet has 60 bytes of header attached.

21. Compare the operation of Stop-and-Wait ARQ with bidirectional Go-Back-N ARQ with a window size of 1. Sketch out a sequence of frame exchanges using each of these protocols and observe how the protocols react to the loss of an information frame and to the loss of an acknowledgment frame.

22. Consider the various combinations of communication channels with bit rates of 1 Mbps, 10 Mbps, 100 Mbps, and 1 Gbps over links that have round-trip times of 10 msec, 1 msec, and 100 msec.

a. Find the delay-bandwidth product for each of the 12 combinations of speed and distance.

b. Suppose that 32-bit sequence numbers are used to transmit blocks of 1000 bytes over the above channels. How long does it take for the sequence numbers to wrap around, that is, to go from 0 up to 2m?

c. Now suppose the 32-bit sequence numbers are used to count individual transmitted bytes. How long does it take for the sequence numbers to wrap around?

23. Consider a bidirectional link that uses Go-Back-N with N = 7. Suppose that all frames are one unit long and that they use a time-out value of 2. Assume the propagation is 0.5 unit and the processing time is negligible. Assume the ACK timer is one unit long. Assuming stations A and B begin with their sequence numbers set to zero, show the pattern of transmissions and associated state transitions for the following sequences of events:

a. Station A sends six frames in a row, starting at t = 0. All frames are received correctly.

b. Station A sends six frame in a row, starting at t = 0. All frames are received correctly, but frame 3 is lost.

c. Station A sends six frames in a row, starting at t = 0. Station B sends six frames in a row starting at t = 0.25. All frames are received correctly.

24. Consider a bidirectional link that uses Go-Back-N with N = 3. Suppose that frames from station A to station B are one unit long and use a time-out value of 2. Frames in the opposite directions are 2.5 units long and use a time-out value of 4. Assume that propagation and processing times are negligible, that the stations have an unlimited number of frames ready for transmission, and that all ACKs are piggybacked onto information frames. Assuming stations A and B begin with their sequence numbers set to zero, show the transmissions and associated state transitions that result when there are no transmission errors.

25. Consider the Go-Back-N ARQ protocol.

a. What can go wrong if the ACK timer is not used?

b. Show how the frame timers can be maintained as an ordered list where the time-out instant of each frame is stated relative to the time-out value of the previous frame.

c. What changes if each frame is acknowledged individually instead of by using a cumulative acknowledgment (Rnext acknowledges all frames up to Rnext —1)?

26. Suppose that instead of Go-Back-N ARQ, N simultaneous Stop-and-Wait ARQ processes are run in parallel over the same transmission channel. Each SDU is assigned to one of the N processes that is currently idle. The processes that have frames to send take turns transmitting in round-robin fashion. The frames carry the binary send sequence number as well as an ID identifying which ARQ process the frame belongs to. Acknowledgments for all ARQ processes are piggybacked onto every frame.

a. Qualitatively, compare the relative performance of this protocol with Go-Back-N ARQ and with Stop-and-Wait ARQ.

b. How does the service offered by this protocol differ from that of Go-Back-N ARQ?

27. Write a program for the transmitter and the receiver implementing Go-Back-N ARQ over a data link that can introduce errors in transmission.

a. Identify which variables need to be maintained.

b. The program loops continuously waiting for an event to occur that requires some action to take place. Identify the main events that can occur in the transmitter. Identify the main events that can occur in the receiver.

28. Modify the program in problem 27 to implement Selective Repeat ARQ.

29. Three possible strategies for sending ACK frames in a Go-Back-N setting are as follows: send an ACK frame immediately after each frame is received, send an ACK frame after every other frame is received, and send an ACK frame when the next piggyback opportunity arises. Which of these strategies are appropriate for the following situations?

a. An interactive application produces a packet to send each keystroke from the client; the server echoes each keystroke that it receives from the client.

b. A bulk data transfer application where a server sends a large file that is segmented in a number of full-size packets that are to be transferred to the client.

30. Consider a bidirectional link that uses Selective Repeat ARQ with a window size of N = 4. Suppose that all frames are one unit long and use a time-out value of 2. Assume that the one-way propagation delay is 0.5 time unit, the processing times are negligible, and the ACK timer is one unit long. Assuming stations A and B begin with their sequence numbers set to zero, show the pattern of transmissions and associated state transitions for the following sequences of events:

a. Station A sends six frames in a row, starting at t = 0. All frames are received correctly.

b. Station A sends six frames in a row, starting at t = 0. All frames are received correctly, but frame 3 is lost.

c. Station A sends six frames in a row, starting at t = 0. Station B sends six frames in a row, starting at t = 0.25. All frames are received correctly.

31. In the chapter we showed that if the transmit and receive maximum window sizes are both equal to the available sequence number space, then Selective Repeat ARQ will work correctly. Rework the arguments presented in the chapter to show that if the sum of the transmit and receive maximum window sizes equals the available sequence number space, then Selective Repeat ARQ will work correctly.

32. Suppose that Selective Repeat ARQ is modified so that ACK messages contain a list of the next m frames that the transmitter expects to receive.

a. How does the protocol need to be modified to accommodate this change?

b. What is the effect of the change on protocol performance?

33. A telephone modem is used to connect a personal computer to a host computer. The speed of the modem is 56 kbps and the one-way propagation delay is 100 ms.

a. Find the efficiency for Stop-and-Wait ARQ if the frame size is 256 bytes; 512 bytes. Assume a bit error rate of 10~4.

b. Find the efficiency of Go-Back-N if three-bit sequence numbering is used with frame sizes of 256 bytes; 512 bytes. Assume a bit error rate of 10~4.

34. A communication link provides 1 Mbps for communications between the earth and the moon. The link sends color images from the moon. Each image consists of 10,000 x 10,000 pixels, and 16 bits are used for each of the three color components of each pixel.

a. How many images/second can be transmitted over the link?

b. If each image is transmitted as a single block, how long does it take to get an acknowledgment back from earth? The distance between earth and the moon is approximately 375,000 km.

c. Suppose that the bit error rate is 10~5, compare Go-Back-N and Selective Repeat ARQ in terms of their ability to provide reliable transfer of these images from the moon to earth. Optimize your frame size for each ARQ protocol.

35. Two computers are connected by an intercontinental link with a one-way propagation delay of 100 ms. The computers exchange 1-Megabyte files that they need delivered in 250 ms or less. The transmission lines have a speed of R Mbps, and the bit error rate is 10~8. Design a transmission system by selecting the bit rate R, the ARQ protocol, and the frame size.

36. Find the optimum frame length that maximizes transmission efficiency by taking the derivative and setting it to zero for the following protocols:

a. Stop-and-Wait ARQ.

c. Selective Repeat ARQ.

37. Suppose station A sends information to station B on a data link that operates at a speed of 10 Mbps and that station B has a 1-Megabit buffer to receive information from A. Suppose that the application at station B reads information from the receive buffer at a rate of 1 Mbps. Assuming that station A has an unlimited amount of information to send, sketch the sequence of transfers on the data link if Stop-and-Wait ARQ is used to prevent buffer overflow at station B. Consider the following cases:

a. One-way propagation delay is 1 microsecond.

b. One-way propagation delay is 1 ms.

c. One-way propagation delay is 100 ms.

38. Redo problem 37 using Xon/Xoff flow control.

39. Suppose station A sends information to station B over a two-hop path. The data link in the first hop operates at a speed of 10 Mbps, and the data link in the second hop operates at a speed of 100 kbps. Station B has a 1-Megabit buffer to receive information from A, and the application at station B reads information from the receive buffer at a rate of 1 Mbps. Assuming that station A has an unlimited amount of information to send, sketch the sequence of transfers on the data link if Stop-and-Wait ARQ is used on an end-to-end basis to prevent buffer overflow at station B.

a. One-way propagation delay in data link 1 and in data link 2 is 1 ms.

b. One-way propagation delay in data link 1 and in data link 2 is 100 ms.

40. A sequence of fixed-length packets carrying digital audio signal is transmitted over a packet network. A packet is produced every 10 ms. The transfer delays incurred by the first 10 packets are 45 ms, 50 ms, 53 ms, 46 ms, 30 ms, 40 ms, 46 ms, 49 ms, 55 ms and 51 ms.

a. Sketch the sequence of packet transmission times and packet arrival times.

b. Find the delay that is inserted at the receiver to produce a fixed end-to-end delay of 75 ms.

c. Sketch the contents of the buffer at the receiver as a function of time.

41. Consider an application in which information that is generated at a constant rate is transferred over a packet network so timing recovery is required at the receiver.

a. What is the relationship between the maximum acceptable delay and the playout buffer?

b. What is the impact of the bit rate of the application information stream on the buffer requirements?

c. What is the effect of jitter on the buffer size design?

42. A speech signal is sampled at a rate of 8000 samples/second. Packets of speech are formed by packing 10 ms worth of samples into each payload. Timestamps are attached to the packets prior to transmission and used to perform error recovery at the receiver. Suppose that the timestamp is obtained by sampling a clock that advances every A seconds. Is there a minimum value that is required for A? If so, what is it?

43. Suppose that PDUs contain both timestamps and sequence numbers. Can the timestamps and sequence numbers be combined to provide a larger sequence number space? If so, should the timestamps or the sequence numbers occupy the most significant bit locations?

44. Consider the timestamp method for timing recovery discussed in the chapter.

a. Find an expression that relates the difference frequency A/ to the number of cycles M and N.

b. Explain why only M needs to be sent.

c. Explain how the receiver uses this value of M to control the playout procedure.

45. A 1.5 Mbps communications link is to use HDLC to transmit information to the moon. What is the smallest possible frame size that allows continuous transmission? The distance between earth and the moon is approximately 375,000 km, and the speed of light is 3 x 108 meters/second.

46. Perform the bit stuffing procedure for the following binary sequence: 1101111111011111110101.

47. Perform bit destuffing for the following sequence: 11101111101111101111110.

48. Suppose HDLC is used over a 1.5 Mbps geostationary satellite link. Suppose that 250-byte frames are used in the data link control. What is the maximum rate at which information can be transmitted over the link?

49. In HDLC how does a station know whether a received frame with the fifth bit set to 1 is a P or an F bit?

50. Which of the following statements are incorrect?

a. A transmitting station puts its own address in command frames.

b. A receiving station sees its own address in a response frame.

c. A response frame contains the address of the sending station.

51. In HDLC suppose that a frame with P =1 has been sent. Explain why the sender should not send another frame with P = 1. What should be done if the frame is lost during transmission.

52. HDLC specifies that the N(R) in a SREJ frame requests the retransmission of frame N(R) and also acknowledges all frames up to N(R)-1. Explain why only one SREJ frame can be outstanding at a given time.

53. The following corresponds to an HDLC ABM frame exchange with no errors.

a. Complete the diagram by completing the labeling of the frame exchanges.

b. Write the sequence of state variables at the two stations as each event takes place.

Station A

Station A Station B

54. Assume station B is awaiting frame 2 from station A.

a. Complete the diagram in HDLC ABM by completing the labeling of the frame exchanges.

b. Write the sequence of state variables at the two stations as each event takes place. 55. The following corresponds to an HDLC ABM frame exchange.

a. Complete the diagram by completing the labeling of the frame exchanges.

b. Write the sequence of state variables at the two stations as each event takes place.

Station A

Station A 1. BI00 2. AI00 3. xlxx 4. xlxx 5. xREJx 6. xlyx 7. xyxx 8. xyxx

56. The PPP byte stuffing method uses an escape character defined by 0x7D (01111101). When the flag is observed inside the frame, the escape character is placed in front of the flag and the flag is exclusive-ORed with 0x20. That is, 0x7E is encoded as 0x7D 0x5E. An escape character itself (0x7D) is encoded as 0x7D 0x5D. What are the contents of the following received sequence of bytes after byte destuffing:

0x7D 0x5E 0xFE 0x24 0x7D 0x5D 0x7D 0x5D 0x62 0x7D 0x5E

57. Suppose that a 1-Megabyte message is sent over a serial link using TCP over IP over PPP. If the speed of the line is 56 kbps and the maximum PPP payload is 500 bytes, how long does it take to send the message?

58. Suppose that packets arrive from various sources to a statistical multiplexer that transmits the packets over 64 kbps PPP link. Suppose that the PPP frames have lengths that follow an exponential distribution with mean 1000 bytes and that the multiplexer can hold up to 100 packets at a time. Plot the average packet delay as a function of the packet arrival rate.

59. Suppose that the traffic is directed to a statistical multiplexer is controlled so that p is always less than 80%. Suppose that packet arrivals are modeled by a Poisson process and that packet lengths are modeled by an exponential distribution. Find the minimum number of packet buffers required to attain a packet loss probability of 10~3 or less.

60. Suppose that packets arrive from various sources to a statistical multiplexer that transmits the packets over a 1 Mbps PPP link. Suppose that the PPP frames have a constant length of L bytes and that the multiplexer can hold a very large number of packets at a time. Assume that each PPP frame contains a PPP, IP, and TCP header in addition to the user data. Plot the average packet delay as a function of the rate at which user information is transmitted for L = 250 bytes, 500 bytes, and 1000 bytes.

61. Suppose that a multiplexer receives constant-length packets from N = 60 data sources. Each data source has a probability p = 0.1 of having a packet in a given T-second period. Suppose that the multiplexer has one line in which it can transmit eight packets every T seconds. It also has a second line where it directs any packets that cannot be transmitted in the first line in a T-second period. Find the average number of packets that are transmitted in the first line and the average number of packets that are transmitted in the second line.

62. Discuss the importance of queueing delays in multiplexers that operate at bit rates of 1 Gbps or higher.