Selective Repeat (SR)

Selective Repeat (SR)

The GBN protocol allows the sender to potentially "fill the pipeline" in "Pipelined Reliable Data Transfer Protocols" Figure 2 with packets, therefore avoiding the channel utilization problems we noted with stop-and-wait protocols. There are, on the other hand, scenarios in which GBN itself suffers from problems. Particularly, when the window size and bandwidth-delay product are both large, many packets can be in the pipeline. A single packet error can thus cause GBN to retransmit a large number of packets, many unnecessarily. As the probability of channel errors increases, the pipeline can become filled with

Go-Back-N in operation

these unnecessary retransmissions. Imagine, in our message-dictation scenario, that if every time a word was garbled, the surrounding 1,000 words (for instance, a window size of 1,000 words) had to be repeated. The dictation would be slowed by all of the reiterated words.

As the name suggests, selective-repeat protocols avoid unnecessary retransmissions by having the sender retransmit only those packets that it suspects were received in error (that is, were lost or corrupted) at the receiver. This individual, as-needed, retransmission will require that the receiver individually acknowledge correctly received packets. A window size of N will again be used to limit the number

Selective-repeat (SR) sender and receiver views of sequence-number space

of outstanding, unacknowledged packets in the pipeline. However, unlike GBN, the sender will have already received ACKs for some of the packets in the window. Figure 2 shows the SR sender's view of the sequence number space. Figure 3 details the various actions taken by the SR sender.

The SR receiver will acknowledge a correctly received packet whether or not it is in order. Out-of-order packets are buffered until any missing packets (that is, packets with lower sequence numbers) are received, at which point a batch of packets can be delivered in-order to the upper layer. Figure 4 itemizes the various actions taken by the SR receiver. Figure 5 shows an example of SR operation in the presence of lost packets. Note that in Figure 5, the receiver initially buffers packets 3, 4 and 5 and delivers them together with packet 2 to the upper layer when packet 2 is finally received.

It is important to note that in Step 2 in Figure 4, the receiver reacknowledges (rather than ignores) already received packets with certain sequence numbers below the current window base. You should convince yourself that this reacknowledgment is indeed needed. Given the sender and receiver sequence number spaces in Figure 2, for instance, if there is no ACK for packet send_base propagating from the receiver to the sender, the sender will ultimately retransmit packet send_base, even though it is clear (to us, not the sender!) that the receiver has already received

SR sender events and actions


SR receiver events and actions

that packet. If the receiver were not to acknowledge this packet, the sender's window would never move forward. This example illustrates an important aspect of SR protocols (and many other protocols as well). The sender and receiver will not always have an identical view of what has been received correctly and what has not. For SR protocols, this means that the sender and receiver windows will not always coincide.

SR operation

The lack of synchronization between sender and receiver windows has important consequences when we are faced with the reality of a finite range of sequence numbers. Consider what could happen, for example, with a finite range of four packet sequence numbers, 0,1,2,3 and a window size of three. Suppose packets 0 through 2 are transmitted and correctly received and acknowledged at the receiver. At this point, the receiver's window is over the fourth, fifth and sixth packets, which have sequence numbers 3,0 and 1, respectively. Now consider two scenarios. In the first scenario, shown in Figure 6(a), the ACKs for the first three packets are lost and

SR receiver dilemma with too-large windows

the sender retransmits these packets. The receiver thus next receives a packet with sequence number 0 - a copy of the first packet sent.

In the second scenario, shown in Figure 6(b), the ACKs for the first three packets are all delivered correctly. The sender thus moves its window forward and sends the fourth, fifth, and sixth packets, with sequence numbers 3,0 and 1, respectively. The packet with sequence number 3 is lost, but the packet with sequence number 0 arrives - a packet containing new data.

Now consider the receiver's viewpoint in Figure 6, which has a figurative curtain between the sender and the receiver, since the receiver cannot "see" the actions taken by the sender. All the receiver observes is the sequence of messages it receives from the channel and sends into the channel. As far as it is concerned, the two scenarios in Figure 6 are identical. There is no way of distinguishing the retransmission of the first packet from an original transmission of the fifth packet. Clearly, a window size that is 1 less than the size of the sequence number space won't work. The window size must be less than or equal to half the size of the sequence number space for SR protocols.

This completes our discussion of reliable data transfer protocols. We've covered a lot of ground and introduced various mechanisms that together provide for reliable data transfer. Table 1 summarizes these mechanisms. Now that we have seen all of these mechanisms in operation and can see the "big picture", we encourage you to review this section again to see how these mechanisms were incrementally added to cover increasingly complex (and realistic) models of the channel connecting the sender and receiver, or to improve the performance of the protocols.

Let's end our discussion of reliable data transfer protocols by considering one remaining assumption in our underlying charnel model. Recall that we have assumed that packets cannot be reordered within the channel between the sender and receiver. This is usually a reasonable assumption when the sender and receiver are connected by a single physical wire. On the other hand, when the "channel" connecting the two is a network, packet reordering can occur. One manifestation of packet reordering is that old copies of a packet with a sequence or acknowledgment number of x can appear, even though neither the sender's nor the receiver's window contains x. With packet reordering, the channel can be thought of as essentially buffering packets and spontaneously emitting these packets at any point in the future. Because sequence numbers may be reused, some care must be taken to guard against such duplicate packets. The approach taken in practice is to ensure that a sequence number is not reused until the sender is "sure" that any previously sent packets with sequence number x are no longer in the network. This is done by assuming that a packet cannot "live" in the network for longer than some fixed maximum amount of time. A maximum packet lifetime of approximately three minutes is assumed in the TCP extensions

Summary of reliable data transfer mechanisms and their use

for high-speed networks. Sunshine 1978 describes a method for using sequence numbers such that reordering problems can be completely avoided.


Tags

packets, gbn protocol, pipeline, retransmission, sr receiver, sequence numbers

Copy Right

The contents available on this website are copyrighted by TechPlus unless otherwise indicated. All rights are reserved by TechPlus, and content may not be reproduced, published, or transferred in any form or by any means, except with the prior written permission of TechPlus.