Solutions to Chapter 5
1. Explain the difference between connectionless unacknowledged service and connectionless acknowledged service. How do the protocols that provide these services differ? Solution: In an acknowledged connectionless network, reliable delivery can be achieved through the use of ACK and NAK transmissions. Such protocols are suited for communication over networks in which higher layers are sensitive to loss and the underlying network is inherently unreliable with a significant probability of loss or error. Unacknowledged networks provide simpler and faster communication for networks that are inherently reliable or provide service to higher layers that can tolerate information loss. 2. Explain the difference between connection-oriented acknowledged service and connectionless acknowledged service. How do the protocols that provide these services differ? Solution: The use of acknowledgments can provide reliable transfer over networks that are prone to error and loss. In connection oriented networks, every packet in a data flow travels on the same path through the network and the proper ordering of packets is guaranteed. In such networks, if a packet arrives out of order, the receiver immediately knows that a packet has been lost. In a connectionless network, the service needs a mechanism for dealing with unordered delivery of information. This is especially important for real-time or delay-sensitive traffic, which may require immediate retransmission and may not be able to use buffering to correct unordered packet arrivals. 3. Suppose that the two end-systems α and β in Figure 5.3 communicate over a connection-oriented packet network. Suppose that station α sends a 10-kilobyte message to station β and that all packets are restricted to be 1000 bytes (neglect headers); assume that each packet can be accommodated in a data link frame. For each of the links, let p be the probability that a frame incurs errors during transmission. Solutions follow questions: 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 β. Let p be the probability that a frame incurs errors during transmission. We know the following: Message length = 10,000 bytes Maximum packet size = 1000 bytes Number of packets for transmission = 10 The probability of a packet arriving error free at end system Ppacket = (1 - p)3. The probability that all packets arrive error free at end system β is Perror = [(1 - p)3]10= (1 - p)30 ≈ e-30p. a. 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?
30p

The average number of required transmissions = 1/ Perror = e b.

.

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?

The average number of transmissions per packet = 1/ Ppacket = e3p. The total number of packet transmissions is then 10/ Ppacket = 10e3p. As an example suppose p = .01, then the message retransmission approach requires 1.35 message transmissions. The packet transmission approach requires 1.03 message transmissions. Clearly packet-by-packet retransmission is better. 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. Solutions follow questions: a. Develop an approach that allows the peer processes to exchange messages of arbitrary size.

To exchange messages of arbitrary size, large messages must be segmented into parts of M-H bytes each in length to be transmitted in multiple PDUs. Small messages must be placed in a single PDU. b. What essential control information needs to be exchanged between the peer processes?

The peer processes need to communicate information that allows for the reassembly of messages at the receiver. For example, the first PDU may contain the message length. The last PDU may contain and end-of-message marker. Sequence numbers may also be useful to detect loss in connection oriented networks and to help in reconstruction of the messages in connectionless networks. Lastly, since variable size PDUs are permitted, the size of the PDU must be transmitted in the PDU header. 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?

In this case, in addition to all of the header information mentioned in b), each PDU must be labeled with a stream ID, so that the receiver can treat each stream independently when reassembling messages. 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. Solutions follow questions: 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?

The streams should be segmented into M − H size blocks and transmitted in the PDUs. Since there is no inherent message length known a priori, an end-of-stream code must be transmitted in the last PDU. If the stream bytes arrive at a sufficient rate, the PDU size will be constant and need not be transmitted in the header. The packets may still be numbered for reordering in a connectionless network (as in problem 4). The number of PDUs in the stream can be theoretically infinite and only a finite number of bits can be used to represent sequence numbers. Thus, the size of the sequence number field in the header should be chosen small enough to incur as little overhead as possible and large enough so that two simultaneously arriving (but different) PDUs with the same sequence number is unlikely. 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?

The bytes at the transmitter should be buffered until M − H are available for transfer. Depending on how sporadic the arrivals are and the delay sensitivity of the application, this buffer delay may need to be limited by sending partially full PDUs. Thus, each PDU header must include a field to hold the size of the PDU c. Suppose that the bytes arrive at a constant rate and that no byte is to be delayed by more that T seconds. Does this have an impact on the efficiency?

Yes. Because the header length is constant, larger PDUs provide more efficient data transfer. If T is very small, partially filled packets must always be sent. If T is large, larger PDUs can be transmitted so more efficient transmission can be achieved. Because the bytes arrive at a constant rate, the PDUs will all be the same length. Thus, there is no need for a PDU length field in the header. 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?

A timer is required that counts down from T seconds. When the first byte arrives the timer starts. When a PDU is full or when the timer expires (whichever occurs first), the PDU is transmitted and the timer is restarted upon the arrival of the next byte. 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: Solutions follow questions: a. The bytes from each user pair arrive at the same constant rate.

All incoming bytes from the n streams should be buffered separately into n queues. Each queue should be serviced in round-robin fashion. b. The bytes from the user pairs arrive sporadically and at different rates.

All incoming bytes from the n streams should be buffered separately into n queues. Assuming that the arrival rate of each stream is constant, each queue should be serviced at rate proportional to their arrival rate in sequential order. One implementation of this is weighted round-robin service, where the weights would be proportional to the arrival rates. If the arrival rates are variable, the weight can be dynamically proportional to the inverse of the queue lengths. In both cases, if a queue is empty, it loses its “turn” in the round-robin service. 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. Solutions follow questions: 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.

Message size is important because in real-time signals of voice it is necessary to transfer fixed packet size of that holds no more than 20 ms of speech signal. The handling of arbitrary message size is not as important as long as the desired packet size for voice can be handled.

Sequencing is important because each packet needs to arrive in the same sequence that it was generated. Reliability is moderately important since voice transmission can tolerate a certain level of loss and error. Pacing and flow control are not as important because the synchronous nature of the voice signal implies that the end systems will be matched in speed. Timing, for real-time voice transfer is important because this adaptation function helps to control the jitter in the delivered signal. Addressing is only during the connection setup phase if we assume some for of virtual circuit packet switching method. Privacy, integrity, and authentication have traditionally not been as important as the other issues discussed above. b. Compare a hop-by-hop approach to an end-to-end approach to meeting the requirements of the voice signal.

If the underlying network is reliable then the end-to-end approach is better because the probability of error is very low so processing at the edge suffices to provide acceptable performance. If the underlying network is unreliable then the hop-by-hop approach may be required. For example if the probability of error is very high, as in a wireless channel, then error recovery at each hop may be necessary to make effective communication possible. 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. Solutions follow questions: 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.

The following table summarizes parts (a) and (b):
Adaptation function Handling of arbitrary message size Reliability and sequencing Pacing and flow control Timing Addressing Privacy, integrity and authentication Relevant in Upstream Direction (part a) No Yes No Yes Yes Yes Relevant in Downstream Direction (part b) No Yes No Yes Yes No

Because traffic in a cellular network consists of constant rate streams of information, the message size need not be arbitrary, and the timing and sequence of packets is essential for service. Addressing is necessary to identify the two end callers, and authentication may only be necessary in the upstream direction, although if it is done at the base station, it need not be repeated. Pacing and flow control are not necessary because cellular networks service constant bit rate traffic and only admit calls that can be accommodated at that constant bit rate. b. Are the requirements the same in the opposite direction from the telephone office to the base station?

See answer to part (a).

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?

If the signals include email and other short messages in addition to voice, further adaptation functions are required. The handling of arbitrary message sizes is needed, since email messages are variable in length. Although timing is still necessary for voice traffic, the message traffic has no strict timing requirements. Pacing and flow control may now be needed depending on the nature of the messages. Text email is low in bandwidth and likely would not require flow control, but very large messages, particularly those transmitted in the downstream direction to the cellular user would require flow control. 9. Suppose that streaming video information is transferred from a server to a user over a packet network. Solutions follow questions: 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.

The following table summarizes the results of part (a).
Adaptation function Handling of arbitrary message size Reliability and sequencing Pacing and flow control Timing Addressing Privacy, integrity and authentication Required No Yes Maybe Yes Maybe Maybe Discussion Stream has no inherent required message size This may be relaxed in connection-oriented network See note below Video has strict timing requirements Required for point-to-point or point-to multipoint transfer, but not in broadcast system Required for point-to-point or point-to multipoint transfer, but may not be required in broadcast system

Whether explicit pacing and flow control is necessary depends on the nature of the receiver. If the receiver is dedicated for receiving video, it should able to handle the incoming signal. If other applications may be received at the same time, flow control might be needed. If the signal is constant-rate, uncompressed video, flow control is not possible. For a compressed signal, flow control may be implemented by using MPEG, which transmits video in layers that can be selectively discarded to reduce the bandwidth to the receiver. 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?

The following table summarizes the results of part (b).
Adaptation function Handling of arbitrary message size Reliability and sequencing Pacing and flow control Timing Addressing Privacy, integrity and authentication Required No Yes No Yes Yes Yes Discussion Can define messages to be fixed length Necessary to allow user to perform many operations in a short time period Control messages would not likely produce high bandwidth Interactive control has timing requirements The control traffic must be addressed to the video server Authentication is important that only the users have control over the content they receive. Privacy for control information may be provided, but would likely not be a strict requirement.

10. Discuss the merits of the end-to-end vs. hop-by-hop approaches to providing a constant transfer delay for information transferred from a sending end system to a receiving end system. Solution: Jitter in networks has two primary sources – variation in queuing delay and variation in propagation delay. The former is caused because traffic intensity at nodes varies with time, so the buffering that is required at each node is equally variable. The latter exists primarily in connectionless networks and results because each packet in a flow can traverse a different path through the network to its destination. Hop-by-hop approaches can be used to deal with queuing delay variation, and end-to-end approaches are required to deal with path-length variation. By setting up a path prior to transmission, a constant propagation delay can be ensured. To deal with queuing delay variation, the scheduler at a node can give delay sensitive traffic priority, ensuring that it’s delay is kept below some maximum amount. This can be based on header information in the packet. If the path for a flow has been previously specified, the number of nodes in the path is known, so an overall queuing delay maximum is, thus, insured. 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. Solutions follow questions: a. Show that the protocol still operates correctly.

The protocol will operate correctly because there is only one variation from the protocol in the chapter, namely, the sender will retransmit before the time-out. b. Does the state transition diagram need to be modified to describe the new operation?

The state transition diagram remains the same. c. What is the main effect of introducing the immediate-retransmission feature?

The main effect is that the expected time for transmission is reduced because when the error is detected a NAK is send and the sender can stop the transmission and initiate the retransmission of the frame. If the error is in the ACK then the sender will not have to wait for the time out. Always when there is an error in the ACK or NAK the last frame sent has to be retransmitted because the sender does not know if the frame was received with or without errors. 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? Solution: The sender cannot send the next frame until it has received the ACK for the last frame so, if the receiver gets a frame with the wrong sequence it has to be a retransmission of the previous frame received. This means that the ACK was lost so the receiver has to ACK again to indicate the sender that it has received the frame. 13. Discuss the factors that should be considered in deciding whether an ARQ protocol should act on a frame in which errors are detected. Solution:

If a frame is in error, then all of the information contained in it is unreliable. Hence any action taken as a result of receiving an erroneous frame should not use the information inside the frame. A viable option when an erroneous frame is received is to do nothing, and instead to rely on a timeout mechanism to initiate retransmission. However error recovery will be faster if we use a NACK message to prompt the sender to retransmit. The inherent tradeoff is between the bandwidth consumed by the NACK message and the faster recovery. 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 setup 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 setup and is ready to transfer information. This situation provides an example of how unnumbered acknowledgments can arise for confirmed services. Solutions follow questions: 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.

Fundamentally, the problem involves getting the receiver state to change from an idle state to a connected state. This is the same as getting the state to go from state (0,0) to state (1,1) in Figure 5.11. Therefore transmissions of the SETUP message must be accompanied by the start of an associated timer to trigger retransmissions. Also, the receiver must acknowledge every SETUP frame that it receives. The sender should ignore redundant SETUP acknowledgments and the receiver should ignore redundant SETUP frames. In order to allow multiple connections, each flow’s SETUP and acknowledgment frames should be indexed. 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.

This problem is very similar to problem a. except that in the SETUP problem the actual transfer of frames cannot begin until a SETUP acknowledgment is received. In the disconnect case, the sender can stop transmitting after a certain number of retransmissions of the DISC message. 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?

If the DISC acknowledgment is lost, the original DISC message will remain unacknowledged. By conventional protocol rules, the initiating station will retransmit the DISC message. The receiver will receive this message last (likely after acknowledging the last SETUP message and the connection will be terminated. To solve this, the initiating station should not send out SETUP messages with DISC messages outstanding. Alternatively, the ARQ could be altered to let the initiating station ignore outstanding DISC messages if another SETUP has been sent. 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. Solutions follow questions: The file length n = 8 x 106 bits, the transmission rate R = 1 Mbps, and 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.

P[no error in the entire file] = (1 – p)n ≈ e–np , for n >> 1, p << 1 = e-8 = 3.35 x 10-4 We conclude that it is extremely unlikely that the file will arrive error free. b. The file is broken up into N equal-sized blocks that are transmitted separately. What is the probability that all the blocks arrive correctly without error? Does dividing the file into blocks help?

A subblock of length n/N is received without error with probability: P[no error in subblock] = (1 – p)n/N A block has no errors if all subblocks have no errors, so P[no error in block] = P[no errors in subblock]N =((1 – p)n/N)N = (1 – p)n So simply dividing the blocks does not help. 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?

Refer to the following figure for the discussion. tf tACK

ACK/NAK

We assume the following: • • • • • • t0 = basic time to send a frame and receive the ACK/NAK ttotal = total transmission time until success nf = number of bits/frame na = number of bits per ACK nt = number of transmissions Pf = probability of frame transmission error t0 = tf + tACK = nf /R + na /R (tprop ≈ 0).

P[nt = i ] = P[one success after i – 1 failure] = (1 – Pf) Pf i – 1 ttotal | i transmissions = i.t0 E[ttotal i −1 2 ] = ∑ it 0 P[nt = i ] = t0 ( − Pf )∑ iPf 1 = t 0 (1 − Pf ) / (1 − Pf ) =t 0 / (1 − Pf ) ∞ ∞ i =1 i =1

Here, nf = n >> na thus t0 ≈ tf = n/R ; and Pf = 1 – P[ no error] = 1 – e–np E[total] = n/R (1 – Pf) = n/[Re–np] = 8 / (3.35 x 10–4) = 23,847 seconds = 6.62 hours! The file gets through, but only after many retransmissions. 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.

For 1 block Pf = 1 – Pb = 1 – (1 – p) n/N and nf = n/N if tprop ≈ 0 and na << n/N : t0b = nf/R = n/NR Tb = E[ttotalb] = t0b / (1 – Pf) = n(1 – p)–n/N /NR average time to transmit one block T = E[ttotal] = N Tb = n(1 – p)–n/N /R = 8 (1 – p) –n/N = 8 enp/N if n/N >> 1, p << 1 • • • N = 80 ⇒ T ≈ 8 e0.1 = 8.84 sec N = 800 ⇒ T ≈ 8 e0.01 = 8.08 sec N = 8000 ⇒ T ≈ 8 e0.001 = 8.008 sec

Each subblock has a higher probability of arriving without errors, and so requires fewer retransmissions to deliver error free. The overall delay is reduced dramatically. e. Explain qualitatively what happens to the answer in part (d) when the overhead is taken into account.

As N increases, the effect of overhead becomes more significant because the headers constitute a bigger fraction of each subblock. 16. Consider the state transition diagram for Stop-and-Wait ARQ in Figure 5.11. Let Pf be the probability of frame error in going from station A to station B and let Pa be 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? Solution: We know that Pf is the probability of frame error and Pa is the probability of ACK error. We assume that: • • • X is the random variable that represents the number of trials before a successful transmission of a frame. Y is the random variable that represents the number of trials before a successful transmission of an ACK. X and Y follow a geometric random-variable distribution. T1 = Average time to go from (0,0) to (0,1) = 2 [E(X) + 1]

2  Pf   Pf + 1 − Pf  T1 = 2  + 1 = 2   = 1 − Pf 1 − Pf   1 − Pf 
T2 = Average time to go from (0,1) to (1,1) = 1 [E(Y) + 1]

1  Pa   Pa + 1 − Pa  + 1 =  T2 =   = 1 − Pa 1 − P a   1 − P a 
Throughput = Frame Time / Expected Total Transmission Time = 2 / (T1 + T2)

Pf 0.2 0.02 0.002 0

Pa 0.1 0.01 0.001 0

T1 2.5000 2.0408 2.0040 2.0000

T2 1.1111 1.0101 1.0010 1.0000

Throughput 0.5538 0.6555 0.6656 0.6667

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. Solution: In the table below, each possible event, the current state of the transmitter and its corresponding action are described. Event Packet error Data arrives Data arrives Data arrives ACK arrives ACK arrives NA NA NA N N Buffer Empty N Y Y Y N State Correct Sequence Number NA NA NA Y Y Action ACK outstanding DC N Y Add the data to the buffer Start timeout Send the data, set the timeout timer Buffer the data Reset the timeout timer Send the next frame Set the timeout timer Do nothing Do nothing

ACK arrives N DC N ACK arrives Y DC NA Note: DC – don’t care, NA – not applicable

In the table below, each possible event, the current state of the receiver and its corresponding action are described. Event Data Rnext is correct arrives Y Y Y Y Y N N NA Note: NA – not applicable Action Error in packet Y N N NA Do nothing Send next ACK Send Previous ACK Do Nothing (idle state)

18. A 64-kilobyte message is to be transmitted from the source to the destination. 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.
1000 km

1000 km

Source

Switch

Destination

1.5 Mbps

1.5 Mbps

Solution: Message Size 65536 bytes Max Packet Size 2048 bytes Packet Header 32 bytes Available for info 2016 bytes # of packets needed 32.51 packets Total 33 packets bit error rate 1E-06 bits/packet 16384 Probability of error in packet 0.016251 Propagation speed 2E+05 Km/s Distance 1000 Km Bandwidth 1.5 Mb/s

1 – (1– bit_error_rate) ^ (bits/packet)

We assume that the ACK time and processing time are negligible. Tprop = Tf = T0 = Pf = distance / propagation speed = 0.0050 s packet size / bandwidth = 0.0109 s Tprop + Tf = 0.0159 s probability of error in packet = 0.016251 T0/ (1 - Pf) = 0.0162

E[Ttotal]=

Since we have to send every packet over two links and we have 33 packets, then the average time is E[Ttotal] * 2 * 33 = 1.068255711. 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. Solution:

Fr 0

Fr 0 Fr 1

Fr 1 Fr 2

Fr 2 Fr 3

Fr 3 Fr 4

Fr 4

ACK 0

ACK ACK 0 1

ACKACK 1 2

ACK ACK 2 3

ACK ACK 3 4

ACK 4

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 the transmissions are error free and that each packet has 60 bytes of header attached. Solution: The propagation delay in an Ethernet LAN is negligible compared to the total transmission time of a packet from start to finish. Ignoring processing time and using the terminology in the chapter, we have:

to = tf + tack =

8(512 + 60) 64 + = 4.64 × 10 − 4 6 6 10 × 10 10 × 10 to R 8 × 512 −4 = 4.64 × 106 = 0.8828 = 88.3% 10 × 10

n f − no ηo = R
0 eff

R

=

One more source of overhead occurs because the last packet is not full. However, this additional overhead accounts for a very small fraction of the total overhead and does not affect the above result. 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. Solution: Stop-and-Wait:

timeout Fr 0 Fr 1 Fr 1 Fr 2

timeout Fr 2

ACK 1 Go-Back-N:

ACK 2

ACK 3

ACK 3

timeout ACK 1 Fr 1 ACK 2 Fr 2 ACK 3 Fr 3

Fr 0

Fr 2

ACK 1 Fr 0

ACK 2 Fr 1

ACK 3 Fr 2

ACK 3 Fr 2

ACK 4 Fr 3

The performance of both protocols is identical in terms of recovery time. Each one takes on full timeout, which is equal to one full propagation delay. 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 roundtrip times of 10 msec, 1 msec, and 100 msec. Solutions follow questions: a. Find the delay-bandwidth product for each of the 12 combinations of speed and distance. Delay-bandwidth (Mb) Bit Rate Mbps 1 10 100 1000 b. Round Trip Time (msec) 10 1 0.1 0.01 0.001 1.0 0.10 0.010 10.0 1.00 0.100 100.0 10.00 1.000

100

Suppose 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? Block 1000 bytes Sequence 32 bits 4294967296

assuming no errors Time for the sequence number to wrap around (sec) Prop Delay + Frame Time * 232 Bit Rate Round Trip Time (msec) Mbps 100 10 1 1 34359738.47 34359738.38 34359738.37 10 3435973.94 3435973.85 3435973.84 100 343597.48 343597.39 343597.38 1000 34359.84 34359.75 34359.74 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?

Same analysis as (b) changing the block from 1000 bytes to 1 byte Bit Rate Mbps 1 10 100 1000 Round Trip Time (msec) 100 10 1 34359.84 34359.75 34359.74 3436.07 3435.98 3435.97 343.70 343.61 343.60 34.46 34.37 34.36

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: Solutions follow questions: Go-Back-N with N = 7, ttimeout = 2, tprop = 0.5, tACK = 1, tf = 1. Each tick represents one half of a unit of time. a. Station A sends six frames in a row, starting at t = 0. All frames are received correctly. ttime-out Fr 0 Fr 1 Fr 0 Fr 2 Fr 3 Fr 4 Fr 5 Fr 5

ACK 2 tack

ACK 3

ACK 5

ACK 6

ACK 6

b.

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

ttime-out Fr 0 Fr 1 Fr 0 Fr 2 Fr 3 Fr 4 Fr 3 Fr 4 Fr 5 Fr 4

ACK 2 tack

ACK 3

ACK 5

ACK 6

ACK 6

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. ttime-out Fr 0 Fr 1 ACK 2 Fr 2 ACK 2 Fr 3 ACK 2 Fr 2 ACK 3 Fr 3 ACK 4 Fr 4 ACK 4 Fr 5 ACK 4 Fr 4 ACK 5 Fr 5 ACK 6

Fr 0

Fr 1

ACK 1

ACK 1 Fr 0 ttime-out

ACK 2 Fr 1

ACK 2 Fr 2

ACK 2 ACK 3 Fr 3 Fr 2

ACK 4 Fr 3

ACK 4 Fr 4

ACK 5 Fr 5 tack

ACK 6 FR 5 ACK 6

ttime-out

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 that they use a time-out value of 2, and that frames in the opposite directions are 2.5 units long and that they use a time-out value of 4. Assume 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 pattern of transmissions and associated state transitions that result if there are no transmission errors. Solution: The following figure shows a bidirectional link using Go-Back-N ARQ, where N = 3, and the ACKs are piggybacked. In addition, nA = 1, nB = 2.5, tout A = 2, tout B = 4, and tprop = 0.

0,0 A

1,0

2,0

0,1

1,1

2,2

3,2

4,2

5,3

3,3

4,4

5,4

6,4

B 0,0 1,2 2,3 3,4 4,7 5,2

The state for each node is composed of the ordered pair (Slast, Rnext). The global state of the system is composed by [A(Slast, Rnext), B(Slast, Rnext)] Node A retransmits because the ACK of node B arrives late. Tail of arrow: Initiates transmission at sender Head of arrow: arrival of last bit to the receiver
0 1 2

A

tout A

3, ACK1

4

5, ACK2

6, ACK3

7

B
0 1, ACK1 2, ACK2 3, ACK4 4, ACK5

25. Consider the Go-Back-N ARQ protocol. Solutions follow questions: a. What can go wrong if the ACK timer is not used?

When no traffic arrives at a receiver during bidirectional Go-Back-N ARQ, and the receiver has to send an ACK, it usually sends the ACK after the ACK timer expires. If the ACK timer is not used, there are only two options remaining: 1) The ACK must be sent immediately (that is, never use piggybacking) Although this will function correctly, it is an inefficient use of bandwidth in the general case. 2) The ACK must only be sent if it can be piggybacked This is problematic if traffic arrives sporadically. The sender will wait a long time until a piggyback opportunity arises. 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.

Assume that the timer counts down from ttimeout. In order to have a separate timer for each frame, we need not implement N timers. Only the oldest frame can timeout. The system can save, for each frame, an arrival offset time that is related to the frame that preceded it and place these offsets in an ordered list based on the frame sequence numbers. If an ACK for the oldest frame arrives, the system simply increments the timer by the offset of the following frame in the list. If an ACK for any other frame arrives, the timer is incremented by the sum of all of the offsets in the list that are up to this newly acknowledged 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)?

If each frame needs to be acknowledged individually, then the number of ACK messages will increase and the rate at which the transmission window can be increased will be reduced. 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 it belongs to. Acknowledgments for all ARQ processes are piggybacked onto every frame. Solutions follow questions: a. Qualitatively, compare the relative performance of this protocol with Go-Back-N ARQ and with Stop-andWait ARQ.

For simplicity assume that the time between consecutive frame transmissions in Stop-and-Wait corresponds to N consecutive transmissions without stopping. The parallel Stop-and-Wait procedure described above is an effective way to fill the transmission pipe without the additional complexity of Go-Back-N ARQ. Vs. Go-Back N. Go-Back-N delivers frames in order. The parallel Stop-and-Wait protocol does not deliver frames in order, so additional processing is required if frames must be delivered in sequence. Because all the processes are independent, this protocol retransmits erroneous frames individually. In contrast, the Go-Back-N protocol retransmits a group of N frames. In this sense, the parallel protocol seems to perform similar to a Selective Repeat process. Vs. Stop-And-Wait. If Stop-and-Wait is used, the effective bandwidth, without errors, will be N times less than the protocol described here. In fact, the larger N, the more efficient the protocol described is. At its worst case, where N = 1, it reduces to Stop-And-Wait. b. How does the service offered by this protocol differ from that of Go-Back-N ARQ?

Assuming N connections are serviced in both cases, in Go-Back-N N outstanding frames are permitted no matter how many of the connections are actually sending traffic. In this protocol, when only i connections have traffic, the effective total send window is reduced to i frames. 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. Solutions follow questions: a. Identify what variables need to be maintained.

Rnext : frame expected by receiver Slast : oldest outstanding frame (back of window) Srecent : most recently transmitted frame 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.

Transmitter The following state diagram describes the transmitter’s behavior. The table after it describes the events and their corresponding actions.

N

Start State

Send frame Srecent = Srecent +1

Srecent = Slast + Ws – 1 ?

Y Action (see table) Idle State Event (see table) Event Receives an ACK with Rnext Timeout expires Action update Slast to Rnext, update the timeout timer Srecent is updated to Slast

Receiver The receiver is very simple. It remains idle until it receives a frame with Rnext. At that point it increments Rnext and sends the new Rnext in an ACK frame. 28. Modify the program in problem 27 to implement Selective Repeat ARQ. Solution: Receiver Event Receives a frame with Rnext Action Rnext incremented as many frames as possible such that all frames with sequence number < Rnext have already been successfully received. ACK sent with new Rnext Add this sequence number to the list of received frames Send ACK with Rnext

Receives a frame with a sequence number not equal to Rnext

Transmitter The flow chart is identical to that of Problem 5.27. The only differences lie in the response to different events, as summarized in the following table: Event Receives an ACK with Rnext Timeout expires on frame i Receives an NAK with Rnext Action Update Slast to Rnext , Update each timer that belongs to a frame with a sequence number < Rnext Resend frame i only Resend frame Rnext

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? Solutions follow questions: 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.

Since each keystroke is echoed, there will always be a piggyback opportunity. Thus, the piggyback method should be used. 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.

The upstream traffic to a server is generally much less than the downstream traffic. Thus, the piggybacking method is non-ideal in this case. If the channel has a low probability of error, the alternating ACK method is better, as it saves bandwidth. However, if the connection causes frequent errors, every frame should be acknowledged. Additional overhead traffic is caused by the ACK frames, but will compensated by the bandwidth savings that will arise when the errors are discovered more quickly. 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 station 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: Solutions follow questions: a. Station A sends six frames in a row, starting at t = 0. All frames are received correctly.

Frame 0 1 A

2

3

4

5

B ACK 1 2 3 4 5 6 Tail of arrow: Initiates transmission at sender Head of arrow: arrival of last bit at the receiver Propagation delay = 0.5; Frame Length = 1; ACK Length = 1 b. Station A sends six frame in a row, starting at t = 0. All frames are received correctly, except frame 3 is lost.

Frame 0 1 A B A C K 1

2

3

4

5

3

4

5

A C K 2

A C K 3

Err

N A K 3

N A K 3

A C K 6

A C K 6

A C K 6

Tail of arrow: Initiates transmission at sender Head of arrow: arrival of last bit at the receiver Propagation delay = 0.5; Frame Length = 1; ACK Length = 1

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. Solution: Assume Ws + W R = 2m and assume that the current send window is 0 to WS – 1. Suppose also that the receive window is 0 to WR –1. Now suppose that frame 0 is received correctly but that the acknowledgment for frame 0 is lost. The transmitter can transmit new frames only up to frame WS – 1. Depending on which transmission arrive without error, Rnext will be in the range between 1 and Ws while Rnext + W R –1 will be in the range of 1 to WR + W S – 1. The maximum value of Rnext occurs when frames 0 through WS – 1 are received correctly, in which case the value of Rnext is WS and the value of R Rnext + W R –1 increases to WR + W S – 1. Crucially, the receiver will not receive frame WR + W S until the acknowledgment for frame 0 has been received at the transmitter. Any receipt of frame 0 prior to frame WR + W S indicates a duplicate transmission of frame 0. Therefore, the sum of the maximum window sizes is 2m. 32. Suppose that Selective Repeat ARQ is modified so that ACK messages contain a list of the next m frames that it expects to receive. Solutions follow questions: a. How does the protocol need to be modified to accommodate this change?

First, the frame header needs to be modified to accommodate the list of frames to receive. It can be a fixed or a variable number of slots. NAK won’t be necessary because the receiver explicitly indicates which frames need to be transmitted. b. What is the effect of the change on protocol performance?

The performance will increase in cases of multiple errors or in cases where the delay is high. A single frame can ask for the retransmission of several frames. The drawback is the overhead in the header and the increased protocol complexity relative to pure Selective-Repeat ARQ.

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. Solutions follow questions: First we assume the following: Pf = 1 – (1 – 10–4)nf nf = 256 × 8 = 2048 or nf = 512 × 8 = 4096 tprop = 100 ms no = 0 na = 64 bits tproc = 0 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.

Using the results in Table 5.2,

1− η = (1 − Pf ) 1+

no nf

n a 2(t prop + t proc ) R + nf nf

= 0.125 (nf = 2048) = 0.177 (nf = 4096) 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.

Given that WS = 23 = 8, we can calculate that the window size is:

n f ×W S R

= 290ms

Since this is greater than the round trip propagation delay, we can calculate the efficiency by using the results in Table 5.2.

1− η = (1 − Pf )

no nf

1 + (W S − 1) Pf

= 0.355 (nf = 2048) = 0.198 (nf = 4096)

34. A communications link provides 1 Mbps for communications between the earth and the moon. The link is used to send 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.

Solutions follow questions: a. How many images per second can be transmitted over the link?

The number of images that can be transmitted per second is:

1 × 10 6
b.

bits bits (10000 2 × 16 × 3 ) = 2.1 × 10 − 4 bits / image sec image

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.

The total time to get an acknowledgment from earth, assuming that tACK << tf is:

(10000 2 × 16 × 3 t O = t f + 2t prop =

bits ) image 375000 × 10 3 m +2 bits m 1× 10 6 3 × 10 8 sec sec

= 4800 + 1.25 = 4800 sec/ image
Note that if each image is transmitted in a single block, tprop becomes insignificant compared to tf. 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.

We know that in order to optimize efficiency, WS should be chosen such that, without error, packets can be continuously transmitted. For Go-Back-N, ignoring tproc, we have: WS =

2t prop + t ack + t f + 2t proc tf 2(1.25) +

=

2t prop + t ack tf

+1

=

64 6 1× 10 6 + 1 = 3 × 10 +1 nf nf
−5

1×10 6
Pf = 1 − (1 − 10

)

nf

We have assumed that nACK = 64 bits. To calculate the transmission efficiency, we can now use the result from Table 5.2.

1− η = (1 − 10 −5 ) nf no nf

1+ (

3 × 10 6 n )[1 − (1 − 10 −5 ) f ] nf n f − no

η = (1 − 10 −5 )

nf

n f + (3x10 6 )[1 − (1 − 10 −5 ) f ] n This optimum value of nf can be found by taking the derivative with respect to nf and equating the result to zero. (See problem 5.36). In this case, assuming that n0 = 20 bytes we get that ηmax = 3.04 (when nf = 5619bits)

For the case of Selective Repeat, assuming an ideal window size, we have:

η = (1 − 10 − 5 ) f (1 − n n0 ) nf

In this case, assuming again that n0 = 20 bytes we get that ηmax = 92.24% (when nf = 4080 bits) 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. Solution: Using Selective Repeat ARQ for efficiency’s sake and assuming that the overhead no = 64 bits, we need to select nf and R to ensure delivery in 250 ms or less. Total delay = 2t prop +

8 × 10 6 8 × 10 6 = 200 × 10 −3 + < 250 × 10 −3 o ηR Reff

ηR > 6.25 × 10 −9
Using the results of Table 5.2, we see that

(1 − 10 −8 ) f (1 − n 64 ) R > 53.33 × 10 6 nf

The allowable region is shown below as the area under the graph.

Possible R – nf combinations to keep delay under 250ms
1.00E+10

1.00E+09 R

1.00E+08

1.00E+07 10 100 nf 1000 10000

36. Find the optimum frame length that maximizes transmission efficiency by taking the derivative and setting it to zero for the following protocols: Solutions follow questions: a. Stop-and-Wait ARQ.

η = (1 − Pb )

nf

n f − no n f + n a + 2(t proc + t prop ) R

Let a = (1 – Pb) Let b = 2 (tproc + tprop) R + na

a f [ln a(n f − n o ) + 1](n f + b) − a f (n f − n o ) d n f n f − no [a ]= =0 dn f nf +b ( n f + b) 2 n n

a f {ln a[n 2 + (b − n o )n f − n o b] + n f + b − n f + no = 0 f n n 2 + (b − n o ) n f − n o b ] + n f + f

b − n f + no b ln a

=0

nf =
b.

(n o − b) ± (b − n o ) 2 − 4 2

(b − n o − n o b) ln a

Go-Back-N ARQ.

Borrowing the result from problem 34(c)

η = (1 − Pb )

nf

n f − no n f + n f [1 − (1 − Pb ) f ][ n 2 R(t proc + t prop ) nf

]

Let a = (1 – Pb) Let b = 2R (tproc + tprop) and use the approximation 1-(1-p)n≈np, then

η=

a f (n f − n o ) n n f + n f Pb b

=

a f (n f − n o ) n n f [1 + Pb b]

Taking the derivative and equating the numerator to zero, we find that: f dη a (n f − no ) (a = = 0= dn f nf

n

nf

ln a (n f − n0 ) + a f )n f − a f (n f − n0 ) n n

nf

2

which leads to the quadratic equation

n 2 − no n f + no / ln a = 0 f which gives the solution:

nf =
c.

no ± no − 4
2

no ln a

2

Selective Repeat ARQ.

Borrowing the result from problem 34c:

η = (1 − Pb ) f (1 − n n0 ) nf

Except for a scale factor, this equation is the same as the approximation for η found in part (b). The solution for the optimum frame size has the same form. 37. Suppose station A sends information to station B on a data link that operates at a speed of 10 Mbps, and that 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. b. c. One-way propagation delay is 1 microsecond. One-way propagation delay is 1 ms. One-way propagation delay is 100 ms.

Solution: ttimeout = 2tprop + 10tf

Fr 0

ACK 0

Fr 0

time 0 tf + tprop tprop + 10tf 3tprop + 11tf

tf depends on the size of the packets. However, assuming that the packets are 1 Mbit in order to maximize efficiency, tf = 100 ms. For parts (a), (b) and (c), the sequence of events will look the same as above. 38. Redo problem 37 using Xon/Xoff flow control. Solution: If tprop is less than 50ms (parts (a) and (b)), the following picture holds. tprop 0.1 + tprop

ON

OFF

ON

time
0 2tprop 0.1 2tprop + 0.1 1 - 2t + tprop 2tprop

If tprop is greater than 50ms, the following picture is more indicative of the sequence of events: tprop 0.1 + tprop

ON OFF

ON

time 0 0.1 2tprop 2tprop + 0.1 1 - 2t+tprop 2tprop

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. b. One-way propagation delay in data link 1 and in data link 2 are 1 ms. One-way propagation delay in data link 1 and in data link 2 are 100 ms.

Solution:

A

10Mbps

100kbps

Buffer

1Mbps

B

Assume that a frame is nf bits long, then the frame transmission time in link 1 is t1 = nf/107 seconds, and t2 = nf/105 seconds on the second link. Therefore the time to transmit a frame over the second link is 100 times greater than the time to transmit over the first link. For example if nf = 10000 bits, then t1 = 1 ms and t2 =100 ms. Consequently, the node between link 1 and link 2 must be capable of buffering the bits that arrive in link 1 but which must wait for transmission over link 2. If we assume that the frame is buffered before node until it has completely arrived, then it will take t3 = nf/106 seconds to read out. In the above example, we have t3 = 10 ms. The ACK message for Stop-andWait can then be sent. Let tf=t1+t2+t3. The sequence of events is then as follows: a frame that begins transmission at time 0 will be received in its entirety at node B at time tf + tprop; an ACK message is send thereafter, and the message arrives at the transmitter at approximately time tf+2tprop. 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, 51 ms. Solutions follow questions: a. Sketch the sequence of packet transmission times and packet arrival times.

0 b.

50

100

150

Find the delay that is inserted at the receiver to produce a fixed end-to-end delay of 75 ms. 0 0 45 45 75 30 1 10 50 60 85 25 2 20 53 73 95 22 3 30 46 76 105 29 4 40 30 70 115 45 5 50 40 90 125 35 6 60 46 106 135 29 7 70 49 119 145 26 8 80 55 135 155 20 9 90 51 141 165 24

Packet # Transmission Time Delay Arrival Time Desired playout time Delay Inserted

c.

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

Buffer Depth vs. Time
5 4 Buffer Depth 3 2 1 0 40 60 80 100 Time 120 140 160 180

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. Solutions follow questions: a. What is the relationship between the maximum acceptable delay and the playout buffer?

The length of the playout buffer determines the maximum playout delay that will occur (i.e. when the buffer is full). This maximum buffer length is therefore determined by the maximum acceptable playout delay. b. What is the impact of the bit rate of the application information stream on the buffer requirements?

The maximum delay incurred by the buffering is explicitly equal to Max buffer delay = buffer size (in bits) / playout rate Since the playout rate is equal to the bit rate of the application information stream, we see that for a given acceptable maximum playout delay, the buffer size is directly determined by the playout rate. c. What is the effect of jitter on the buffer size design?

In general, to reduce playback delay, the buffer length should be kept as small as possible. However, the buffer must be able to accommodate the jitter of the incoming traffic stream. Jitter has the effect of making the incoming data rate variable. If the stream has high jitter (i.e. high delay variations), then the buffer must be made large to accommodate times when the incoming data rate may be higher than the playback rate. From another perspective, if the jitter is large, there is a large chance that many packets will arrive after a propagation delay that is significantly smaller than that of the other packets in the stream. These packets must be buffered until it is their turn to be played out. 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 time stamp is obtained by sampling a clock that advances every ∆ seconds. Is there a minimum value that is required for ∆? If so what is it? Solution: The clock is sampled every 10 ms to produce a timestamp. Clearly, we require that ∆ < 10 ms in order to ensure a unique timestamp for each packet. However, if the timestamps are to be used for error detection, a ∆ of just under 10 ms is not sufficient. To illustrate, suppose that the clock advances every ∆ = 9 ms. Then the times at which the clock advances will be as follows: Clock tick: 0 Count: 0 9 1 18 2 27 3 36 4 45 5 54 6 63 7 72 8 81 9 90 10

The time stamps that result from sampling every 10 ms will be: Sample: Stamp: 0 0 10 1 20 2 30 3 40 4 50 5 60 6 70 7 80 8 90 10 100 11

We see that the sample at time 90 will have a time stamp of 10, which is 2 units larger than the time stamp at time 80. If a packet is lost, a gap in the timestamps will be detected by the receiver. However for the example, the receiver may not be able to decide whether a packet was lost or whether the phenomenon above occurred. While it is true that this problem can be overcome because of the periodic nature of the above phenomenon, a more reliable solution is to place the constraint that ∆ < 5ms. With this constraint in place each timestamp will be offset by 2∆ or possibly 3∆ (in the case of an extra skipped clock pulse). If a packet is lost, a timestamp offset of 4∆ or possibly 5∆ will be detected at the receiver, which is completely unambiguous. 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? Solution: Yes. Two variations are possible. The first is to transmit groups of consecutive packets with a common sequence number and different time stamps. The second is to transmit groups of consecutive packets with a common time stamp and different sequence numbers. The former is preferable for the reasons described in Problem 42. Since time stamps periodically skip over one clock increment, by having the timestamps occupy the least significant bit locations, the loss to the sequence number space is minimized. 44. Consider the timestamp method for timing recovery discussed in the chapter. Solutions follow questions: a. Find an expression that related the difference frequency ∆f to the number of cycles M and N. ∆f = fn – fs = fn(1 – b.

M ) N

Explain why only M needs to be sent.

fn is globally known and N is agreed on beforehand (as a standard or else during connection setup). Thus, only M needs to be sent. c. Explain how the receiver uses this value of M to control the playout procedure.

The procedure plays out frames at a rate: fr = fn – ∆f = fn (1 –

M M )= fn N N

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. Solution: The round trip propagation delay is:

(375 × 10 6 m) 2tprop = 2 = 2.50 sec 3 × 10 8 m / s
To allow for continuous transmission, we must use Go-Back-N or Selective Repeat. Go-Back-N: If N = 7 à

7n f 1.5Mbps 127n f

= 2.5s à nf = 535 715 bits

If N = 127 à

1.5Mbps

= 2.5s à nf = 29 528 bits

Selective Repeat: If N = 4 à

4n f 1.5Mbps 64n f

= 2.5s à nf = 973 500 bits

If N = 64 à

1.5Mbps

= 2.5s à nf = 58 594 bits

46. Perform the bit stuffing procedure for the following binary sequence: 1101111111011111110101. Solution: The inserted stuff bits are underlined. 1101111111011111110101 à 110111110110111110110101 47. Perform bit destuffing for the following sequence: 11101111101111101111110. Solution:

The removed stuff bits are indicated by a ‘-‘. 11101111101111101111110 à 111011111-11111-1111110 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? Solution: R = 1.5 Mbps, and nf =250 bytes or 2000 bits (250 x 8). The distance that the information must travel is the earth-to-satellite distance, or d ≈ 36,000 km. The speed of light c is 3 x 108. We can calculate the propagation delay and processing rate as follows: tprop = d/c = 36 x 106 / 3 x 108 = 120 ms tf = nf/R = 2000/1.5 x 106 = 1.33 ms We can use either Go-Back-N or Selective Repeat ARQ. The default window size is N = 7 (with a 3bit sequence number). 0 1 2 3 4 5 6 7 …

ACK0

tprop

tf

tcycle

The maximum information rate is achieved with no error, and hence, no retransmission. tcycle = minimum time to transmit a group of N packets = tf + 2 tprop = 1.33 + 2x2120 = 241.33 ms n = no. of bits transmitted in a cycle = N.nf = 7x2000 = 14,000 bits Rmax = no. of bits sent in a cycle / minimum cycle time = n/tcycle = 58 kbps If the extended sequence numbering option (7-bit) is used, the maximum send window size would be N = 27 – 1 = 127, and hence, the maximum information rate is: Rmax = N.nf / tcycle = 127x2000/(241.33x10-3) = 1.052 Mbps 49. In HDLC how does a station know if a received frame with the fifth bit set to 1 is a P or an F bit? Solution: If the station is a secondary station, the bit is a ‘P’ (and the station is being Polled for more frames). If it is a primary station, the bit is a ‘F’ bit (indicating the Final frame of the current transmission).

50. Which of the following statements are incorrect? Solutions follow questions: For this question, one must just keep in mind that all frames always contain the address of the secondary station. a. A transmitting station puts its own address in command frames.

Incorrect. Command frames are destined for secondary stations, so this transmitter would put the address of the secondary station in the frame. b. A receiving station sees its own address in a response frame.

Incorrect. Responses come from secondary stations to primary stations. Thus the address in the frame is that of the sender in this case. c. A response frame contains the address of the sending station.

TRUE. Response frame originate in secondary stations, so they will have contain the address of the sender. 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 to deal with the case where the frame is lost during transmission? Solution: The poll bit is like a token that is passed to a secondary so it can transmit. At the end of transmission the secondary must return it in the form of final bit. If the poll frame is lost then the token no longer exists and no station can transmit. The server must create a new token (poll frame) only after it is sure that the previous poll frame is lost and not just delayed. Consequently it must wait for certain period of time. 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. Solution: Suppose two outstanding SREJ frames exist. Let frame A have N(R) = m and frame B have N(R) = n. Without loss of generality, suppose n > m. Since each SREJ frame with value N(R) implicitly acknowledges all previous frames up to N(R) – 1, frame A indicates that frame m has not yet been received and frame B indicates that frame m has been received. Thus, if two SREJ are allowed to be outstanding at the same time, contradictory information will be sent to the receiver. 53. The following corresponds to an HDLC ABM frame exchange with no errors.

Station A

1

2

3

4

5

6

7

8

9

Station B 1. BI00 6. xIxx a. b. 2. AI00 7. xIxx 3. xIxx 8. xRRxx 4. xIxx 9. xRRxx 5. xRRxx

Complete the diagram by completing the labeling of the frame exchanges. Write the sequence of state variables at the two stations as each event takes place.

Solution:
NA(R) = 0 NA(R) = 1 NA(R) = 2 N A(R) = 3

AI00 AI11 BI00 BI12

BRR2

BI22

AI22

BRR3 ARR3

NB(R) = 0 N B(R) = 1

NB(R) = 2

NB(R) = 3

54. Assume station B is awaiting frame 2 from station A. Timeout expires Station A

1

2

3

4

5

Station B 1. BI23 a. b. 2. xRRxP 3. xRRxy 4. xIxx 5. xRRx

Complete the diagram in HDLC ABM by completing the labeling of the frame exchanges. Write the sequence of state variables at the two stations as each event takes place.

Solution: This sequence of events appears to be Stop-And-Wait.

Timeout expires
NA(R) = 3

BI23

BRR3P

BRR2F

BI23P

BRR3F

Suppose NB(R) = 2

NB(R) = 3

55. The following corresponds to an HDLC ABM frame exchange. Station A

1

2

3

4

5

6

7

8

Station B 1. BI00 5. xREJx a. b. 2. AI00 6. xIyx 3. xIxx 7. xyxx 4. xIxx 8. xyxx

Complete the diagram by completing the labeling of the frame exchanges. Write the sequence of state variables at the two stations as each event takes place.

Solution:
NA(R) = 0 NA(R) = 1 Out-of-sequence

AI00 BI00 AI10 AI20

AREJ1 AI11P AI21 AI31

NB(R) = 1

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 it 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

Solution: 0x7D 0x5E 0xFE 0x24 0x7D 0x5D 0x7D 0x5D 0x62 0x7D 0x5E → 0x7E 0xFE 0x24 0x7D 0x7D 0x62 0x7E 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? Solution: Assuming the overhead in one packet is equal to 8 bytes for the PPP header plus 20 bytes for the IPv4 header and 20 bytes for the TCP header. Thus, the total overhead in bits is 8 x (8 + 20 + 20) = 384 bits. Thus, Time to send 8×1016 bits = (time for 1 packet)(# of packets needed) = (

nf R

)(

8 × 10 6 ) n f − no

8 × 500bits 10 6 bytes )[ ] = ( 56 × 10 3 bps (500 − 70)bytes
= 0.7143

sec × 2326 packets packet

= 166.14 seconds 58. Suppose that packets arrive from various sources to a statistical multiplexer that transmits the packets over a 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. Solution: This is an M/M/1/K system in which: Service rate µ = 6400 bps / 8000 bits = 0.125 packets/sec Packet length E[L] = 8000 bits Buffer size K = 100 packets Thus: E[T] =

E[ N ] λ (1 − PL ) (1 −

λ λ K )( ) λ ( K + 1)λK +1 µ µ where PL = and E[N] = − K +1 λ µ − λ µ − λK +1 1 − ( ) K +1 µ

Average Packet Delay vs. Arrival Rate
45 40 35 Average Delay 30 25 20 15 10 5 0 0 0.02 0.04 0.06 Arrival Rate 0.08 0.1 0.12

59. Suppose that the traffic that is directed to a statistical multiplexer is controlled so that ρ 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. Solution: (1 – ρ) ρk Ploss = ------------1 – ρk+1 with k = 24 Ploss= 0.000948 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 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. Solution: Assuming that the overhead in each packet is 48 bytes (as described in Problem 57), we have: R = 106 bps L = constant (250, 500, and 1000 bytes) Kà∞ no = 48 bytes µ = R/L packets/sec Because of the constant length packets, this is an M/D/1 system. Average delay, E[TD] = 1 +

λ 1 2( µ − λ ) µ

Let γ be the rate in packets per second at which user information transferred. γ =ρ Thus, λ = γL / (L-48)

R ( L − no ) λ R ( L − 48) ( L − 48) = =λ L L µ L L L

γL γL2 γL3 L L − 48 E[TD] = 1 + = 1+ = 1+ R γL L − 48 2 R[ R( L − 48) − γL2 ] 2( − )R 2 R[ R( ) − γL ] L L − 48 L
Packet Delay vs. Throughput
Throughput = 1000 1.0045 1.004 1.0035 1.003 1.0025 1.002 1.0015 1.001 1.0005 1 0 500 1000 1500 2000 2500 3000 3500 Throughput = 500 Throughput = 250

Throughput

61. Suppose that a multiplexer receives constant-length packet 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 on the first line and the average number of packets that are transmitted in the second line. Solution: The probability that there are k packet arrivals in a T-second period is given by the binomial distribution with parameters N = 60 and p = 0.1. The average number of arrivals is Np = 6. The average number of arrivals that get transferred to the first line is given by:

 60  k  (0.1) k (0.9) 60− k = 4.59 ∑   k =0  k 
8

The remainder of the packet arrivals are sent to the second line, so the average number sent to line 2 is 6 – 4.59 = 1.41 packets per T-second period. 62. Discuss the importance of queueing delays in multiplexers that operate at bit rates of 1 Gbps or higher. Solution: By aggregating traffic, better delay performance is achieved, as illustrated in section 5.5. In multiplexers that operate at bit rates of 1 Gbps or higher, the queuing delay experienced by packets is much shorter than it would be if many lower bit rate systems were used.