SEC. 3.3
`
`ELEMENTARY DATA LINK PROTOCOLS
`
`197
`
`be possible for the sender to simply insert a delay into protocol 1 to slow it down
`sufficiently to keep from swamping the receiver. However, more usually, each
`data link layer will have several lines to attend to, and the time interval between a
`frame arriving and its being processed may vary considerably. If the network
`designers can calculate the worst-case behavior of the receiver, they can program
`the sender to transmit so slowly that even if every frame suffers the maximum
`delay, there will be no overruns. The trouble with this approach is that it is too
`conservative. It leads to a bandwidth utilization that is far below the optimum,
`unless the best and worst cases are almost the same (i.e., the variation in the data
`link layer's reaction time is small).
`A more general solution to this dilemma is to have the receiver provide feed(cid:173)
`back to the sender. After having passed a packet to its network layer, the receiver
`sends a little dummy frame back to the sender which, in effect, gives the sender
`permission to transmit the next frame. After having sent a frame, the sender is
`required by the protocol to bide its time until the little dummy (i.e., acknowledge(cid:173)
`ment) frame arrives.
`Protocols in which the sender sends one frame and then waits for an acknowl(cid:173)
`edgement before proceeding are called stop-and-wait. Figure 3-10 gives an
`example of a simplex stop-and-wait protocol.
`As in protocol 1, the sender starts out by fetching a packet from the network
`layer, using it to construct a frame and sending it on its way. Only now, unlike in
`protocol 1, the sender must wait until an acknowledgement frame arrives before
`looping back and fetching the next packet from the network layer. The sending
`data link layer need not even inspect the incoming frame: there is only one possi(cid:173)
`bility.
`The only difference between receiver 1 and receiver2 is that after delivering a
`packet to the network layer, receiver2 sends an acknowledgement frame back to
`the sender before entering the wait loop again. Because only the arrival of the
`frame back at the sender is important, not its contents, the receiver need not put
`any particular information in it.
`Although data traffic in this example is simplex, going only from the sender to
`the receiver, frames do travel in both directions. Consequently, the communica(cid:173)
`tion channel between the two data link layers needs to be capable of bidirectional
`information transfer. However, this protocol entails a strict alternation of flow:
`first the sender sends a frame, then the receiver sends a frame, then the sender
`sends another frame, then the receiver sends another one, and so on. A half(cid:173)
`duplex physical channel would suffice here.
`
`3.3.3. A Simplex Protocol for a Noisy Channel
`
`Now let us consider the normal situation of a communication channel that
`makes errors. Frames may be either damaged or lost completely. However, we
`assume that if a frame is damaged in transit, the receiver hardware will detect this
`
`Ex.1006.215
`
`DELL
`
`

`

`198
`
`THE DATA LINK LAYER
`
`CHAP. 3
`
`/* Protocol 2 (stop-and-wait) also provides for a one-directional flow of data from
`sender to receiver. The communication channel is once again assumed to be error
`free, as in protocol 1. However, this time, the receiver has only a finite buffer
`capacity and a finite processing speed, so the protocol must explicitly prevent
`the sender from flooding the receiver with data faster than it can be handled. */
`
`typedef enum {frame_arrival} evenUype;
`#include "protocol.h"
`
`void sender2(void)
`{
`frames;
`packet buffer;
`evenUype event;
`
`/* buffer for an outbound frame */
`/* buffer for an outbound packet */
`/* frame_arrival is the only possibility */
`
`while (true) {
`from_network_layer( &buffer);
`s.info = buffer;
`to_physicaUayer( &s);
`waiUor _event( &event);
`
`/* go get something to send */
`/* copy it into s for transmission */
`/* bye bye little frame */
`/* do not proceed until given the go ahead */
`
`}
`}
`
`void receiver2(void)
`{
`framer, s;
`evenUype event;
`while (true) {
`waiUor _event( &event);
`from_physicaUayer( &r);
`to_network_layer( &r. info);
`to_physicaUayer( &s );
`
`}
`}
`
`/* buffers for frames */
`/* frame_arrival is the only possibility */
`
`/* only possibility is frame_arrival */
`/* go get the inbound frame */
`/* pass the data to the network layer */
`/* send a dummy frame to awaken sender */
`
`Fig. 3-10. A simplex stop-and-wait protocol.
`
`when it computes the checksum. If the frame is damaged in such a way that the
`checksum is nevertheless correct, an exceedingly unlikely occurrence, this proto(cid:173)
`col (and all other protocols) can fail (i.e., deliver an incorrect packet to the net(cid:173)
`work layer).
`At first glance it might seem that a variation of protocol 2 would work: adding
`a timer. The sender could send a frame, but the receiver would only send an
`acknowledgement frame if the data were correctly received. If a damaged frame
`arrived at the receiver, it would be discarded. After a while the sender would time
`
`Ex.1006.216
`
`DELL
`
`

`

`SEC. 3.3
`
`ELEMENTARY DATA LINK PROTOCOLS
`
`199
`
`out and send the frame again. This process would be repeated until the frame
`finally arrived intact.
`The above scheme has a fatal flaw in it. Think about the problem and try to
`discover what might go wrong before reading further.
`To see what might go wrong, remember that it is the task of the data link layer
`processes to provide error free, transparent communication between network
`layers processes. The network layer on machine A gives a series of packets to its
`data link layer, which must ensure that an identical series of packets are delivered
`to the network layer on machine B by its data link layer. In particular, the net(cid:173)
`work layer on B has no way of knowing that a packet has been lost or duplicated,
`so the data link layer must guarantee that no combination of transmission errors,
`no matter how unlikely, can cause a duplicate packet to be delivered to a network
`layer.
`Consider the following scenario:
`
`1. The network layer on A gives packet 1 to its data link layer. The
`packet is correctly received at B and passed to the network layer on
`B. B sends an acknowlledgement frame back to A.
`
`It just never
`2. The acknowledgement frame gets lost completely.
`arrives at all. Life would be a great deal simpler if the channel only
`mangled and lost data frames and not control frames, but sad to say,
`the channel is not very discriminating.
`
`3. The data link layer on A eventually times out. Not having received
`an acknowledgement, it (incorrectly) assumes that its data frame was
`lost or damaged and sends the frame containing packet 1 again.
`
`4. The duplicate frame also arrives at data link layer on B perfectly and
`is unwittingly passed to the network layer there. If A is sending a file
`to B, part of the file will be duplicated (i.e., the copy of the file made
`by B will be incorrect and the error will not have been detected). In
`other words, the protocol will fail.
`
`Clearly, what is needed is some way for the receiver to be able to distinguish
`a frame that it is seeing for the first time from a retransmission. The obvious way
`to achieve this is to have the sender put a sequence number in the header of each
`frame it sends. Then the receiver can check the sequence number of each arriving
`frame to see if it is a new frame or a duplicate to be discarded.
`Since a small frame header is desirable, the question arises: What is the
`minimum number of bits needed for the sequence number? The only ambiguity in
`this protocol is between a frame, m, and its direct successor, m + 1. If frame mis
`lost or damaged, the receiver will not acknowledge it, so the sender will keep try(cid:173)
`ing to send it. Once it has been correctly received, the receiver will send an
`
`Ex.1006.217
`
`DELL
`
`

`

`200
`
`THE DAT A LINK LA YER
`
`CHAP. 3
`
`acknowledgement back to the sender. It is here that the potential trouble crops up.
`Depending upon whether the acknowledgement frame gets back to the sender
`correctly or not, the sender may try to send m or m + 1.
`The event that triggers the sender to start sending m + 2 is the arrival of an
`acknowledgement for m + l. But this implies that m has been correctly received,
`and furthermore that its acknowledgement has also been correctly received by the
`sender (otherwise, the sender would not have begun with m + 1, let alone m + 2).
`As a consequence, the only ambiguity is between a frame and its immediate
`predecessor or successor, not between the predecessor and successor themselves.
`A I-bit sequence number (0 or I) is therefore sufficient. At each instant of
`time, the receiver expects a particular sequence number next. Any arriving frame
`containing the wrong sequence number is rejected as a duplicate. When a frame
`containing the correct sequence number arrives, it is accepted, passed to the net(cid:173)
`work layer, and the expected sequence number is incremented modulo 2 (i.e., 0
`becomes 1 and 1 becomes 0).
`An example of this kind of protocol is shown in Fig. 3-11. Protocols in which
`the sender waits for a positive acknowledgement before advancing to the next
`data item are often called PAR (Positive Acknowledgement with Retransmis(cid:173)
`sion) or ARQ (Automatic Repeat reQuest). Like protocol 2, this one also
`transmits data only in one direction. Although it can handle lost frames (by tim(cid:173)
`ing out), it requires the timeout interval to be long enough to prevent premature
`timeouts. If the sender times out too early, while the acknowledgement is still on
`the way, it will send a duplicate.
`When the previous acknowledgement finally does arrive, the sender will mis(cid:173)
`takenly think that the just-sent frame is the one being acknowledged and will not
`realize that there is potentially another acknowledgement frame somewhere "in
`the pipe." If the next frame sent is lost completely but the extra acknowledgement
`arrives correctly, the sender will not attempt to retransmit the lost frame, and the
`In later protocols the acknowledgement frames will contain
`protocol will fail.
`information to prevent just this sort of trouble. For the time being, the acknowl(cid:173)
`edgement frames will just be dummies, and we will assume a strict alternation of
`sender and receiver.
`Protocol 3 differs from its predecessors in that both sender and receiver have a
`variable whose value is remembered while the data link layer is in wait state. The
`sender remembers
`the sequence number of the next frame
`to send
`in
`next_frame_to_send; the receiver remembers the sequence number of the next
`frame expected inframe_expected. Each protocol has a short initialization phase
`before entering the infinite loop.
`After transmitting a frame, the sender starts the timer running. If it was
`already running, it will be reset to allow another full timer interval. The time
`interval must be chosen to allow enough time for the frame to get to the receiver,
`for the receiver to process it in the worst case, and for the acknowledgement
`frame to propagate back to the sender. Only when that time interval has elapsed
`
`Ex.1006.218
`
`DELL
`
`

`

`SEC. 3.3
`
`ELEMENTARY DATA LINK PROTOCOLS
`
`201
`
`f* Protocol 3 (par) allows unidirectional data flow over an unreliable channel. */
`
`/* must be 1 for protocol 3 *f
`#define MA)(_SEQ 1
`typedef enum {frame_arrival, cksum_err, timeout} evenLtype;
`#include "protocol.h"
`
`void sender3(void)
`{
`seq_nr nexLframe_to_send;
`frames;
`packet buffer;
`evenLtype event;
`
`nexLframe_to_send = O;
`from_network_layer( &buffer);
`while (true) {
`s.info = buffer;
`s.seq = nexLframe_to_send;
`to_physicaLlayer( &s);
`starLtimer(s.seq);
`waiLfor _event( &event);
`if (event== frame_arrival) {
`from_physicaLlayer( &s);
`if (s.ack == nexLframe_to_send) {
`from_network_layer( &buffer);
`inc(nexLframe_to_send);
`
`f* seq number of next outgoing frame *f
`f* scratch variable */
`f* buffer for an outbound packet */
`
`/* initialize outbound sequence numbers */
`/* fetch first packet */
`
`/* construct a frame for transmission *f
`/* insert sequence number in frame */
`/* send it on its way */
`/* if answer takes too long, time out */
`/* frame_arrival, cksum_err, timeout*/
`
`/* get the acknowledgement */
`
`/* get the next one to send */
`/* invert nexUrame_to_send */
`
`}
`}
`
`void receiver3(void)
`{
`seq_nr frame_expected;
`framer, s;
`evenLtype event;
`
`frame_expected = O;
`while (true) {
`waiLfor _event( &event);
`if (event== frame_arrival) {
`from_physicaLlayer( &r);
`if (r.seq == frame_expected) {
`to_network_layer( &r. info);
`inc(frame_expected);
`
`}
`s.ack = 1 - frame_expected;
`to_physicaLlayer( &s);
`
`}
`}
`
`/* possibilities: trame_arrival, cksum_err */
`f* a valid frame has arrived. */
`/* go get the newly arrived frame */
`/* this is what we have been waiting for. */
`/* pass the data to the network layer */
`/* next time expect the other sequence nr */
`
`/* tell which frame is being acked */
`/* none of the fields are used */
`
`Fig. 3-11. A positive acknowledgement with retransmission protocol.
`
`Ex.1006.219
`
`DELL
`
`

`

`202
`
`THE DAT A LINK LA YER
`
`CHAP. 3
`
`is it safe to assume that either the transmitted frame or its acknowledgement has
`been lost, and to send a duplicate.
`After transmitting a frame and starting the timer, the sender waits for some(cid:173)
`thing exciting to happen. There are three possibilities: an acknowledgement
`frame arrives undamaged, a damaged acknowledgement frame staggers in, or the
`timer goes off. If a valid acknowledgement comes in, the sender fetches the next
`packet from its network layer and puts it in the buffer, overwriting the previous
`packet. It also advances the sequence number. If a damaged frame arrives or no
`frame at all arrives, neither the buffer nor the sequence number are changed, so
`that a duplicate can be sent.
`When a valid frame arrives at the receiver, its sequence number is checked to
`see if it is a duplicate. If not, it is accepted, passed to the network layer, and an
`acknowledgement generated. Duplicates and damaged frames are not passed to
`the network layer.
`
`3.4. SLIDING WINDOW PROTOCOLS
`
`In the previous protocols, data frames were transmitted in one direction only.
`In most practical situations, there is a need for transmitting data in both directions.
`One way of achieving full-duplex data transmission is to have two separate com(cid:173)
`munication channels and use each one for simplex data traffic (in different direc(cid:173)
`tions). If this is done, we have two separate physical circuits, each with a "for(cid:173)
`ward" channel (for data) and a "reverse" channel (for acknowledgements). In
`both cases the bandwidth of the reverse channel is almost entirely wasted. In
`effect, the user is paying for two circuits but using only the capacity of one.
`A better idea is to use the same circuit for data in both directions. After all, in
`protocols 2 and 3 it was already being used to transmit frames both ways, and the
`reverse channel has the same capacity as the forward channel. In this model the
`data frames from A to B are intermixed with the acknowledgement frames from A
`to B. By looking at the kind field in the header of an incoming frame, the receiver
`can tell whether the frame is data or acknowledgement.
`Although interleaving data and control frames on the same circuit is an
`improvement over having two separate physical circuits, yet another improvement
`is possible. When a data frame arrives, instead of immediately sending a separate
`control frame, the receiver restrains itself and waits until the network layer passes
`it the next packet. The acknowledgement is attached to the outgoing data frame
`(using the ack field in the frame header). In effect, the acknowledgement gets a
`free ride on the next outgoing data frame. The technique of temporarily delaying
`outgoing acknowledgements so that they can be hooked onto the next outgoing
`data frame is known as piggybacking.
`The principal advantage of using piggybacking over having distinct acknowl(cid:173)
`edgement frames is a better use of the available channel bandwidth. The ack field
`
`Ex.1006.220
`
`DELL
`
`

`

`SEC. 3.4
`
`SLIDING WINDOW PROTOCOLS
`
`203
`
`in the frame header costs only a few bits, whereas a separate frame would need a
`header, the acknowledgement, and a checksum. In addition, fewer frames sent
`means fewer "frame arrived" interrupts, and perhaps fewer buffers in the
`receiver, depending on how the receiver's software is organized. In the next pro(cid:173)
`tocol to be examined, the piggyback field costs only 1 bit in the frame header. It
`rarely costs more than a few bits.
`However, piggybacking introduces a complication not present with separate
`acknowledgements. How long should the data link layer wait for a packet onto
`which to piggyback the acknowledgement? If the data link layer waits longer
`than the sender's timeout period, the frame will be retransmitted, defeating the
`whole purpose of having acknowledgements. If the data link layer were an oracle
`and could foretell the future, it would know when the next network layer packet
`was going to come in, and could decide either to wait for it or send a separate
`acknowledgement immediately, depending on how long the projected wait was
`going to be. Of course, the data link layer cannot foretell the future, so it must
`resort to some ad hoc scheme, such as waiting a fixed number of milliseconds. If
`a new packet arrives quickly, the acknowledgement is piggybacked onto it; other(cid:173)
`wise, if no new packet has arrived by the end of this time period, the data link
`layer just sends a separate acknowledgement frame.
`In addition to its being only simplex, protocol 3 can fail under some peculiar
`conditions involving early timeout. It would be nicer to have a protocol that
`remained synchronized in the face of any combination of garbled frames, lost
`frames, and premature timeouts. The next three protocols are more robust and
`continue to function even under pathological conditions. All three belong to a
`class of protocols called sliding window protocols. The three differ among them(cid:173)
`selves in terms of efficiency, complexity, and buffer requirements, as discussed
`later.
`In all sliding window protocols, each outbound frame contains a sequence
`number, ranging from 0 up to some maximum. The maximum is usually 2n - 1 so
`the sequence number fits nicely in an n-bit field. The stop-and-wait sliding win(cid:173)
`dow protocol uses n = 1, restricting the sequence numbers to 0 and 1, but more
`sophisticated versions can use arbitrary n.
`The essence of all sliding window protocols is that at any instant of time, the
`sender maintains a set of sequence numbers corresponding to frames it is permit(cid:173)
`ted to send. These frames are said to fall within the sending window. Similarly,
`the receiver also maintains a receiving window corresponding to the set of frames
`it is permitted to accept. The sender's window and the receiver's window need
`not have the same lower and upper limits, or even have the same size. In some
`protocols they are fixed in size, but in others they can grow or shrink as frames
`are sent and received.
`Although these protocols give the data link layer more freedom about the
`order in which it may send and receive frames, we have most emphatically not
`dropped the requirement that the protocol must deliver packets to the destination
`
`Ex.1006.221
`
`DELL
`
`

`

`204
`
`THE DA TA LINK LA YER
`
`CHAP. 3
`
`network layer in the same order that they were passed to the data link layer on the
`sending machine. Nor have we changed the requirement that the physical com(cid:173)
`munication channel is "wire-like," that is, it must deliver all frames in the order
`sent.
`The sequence numbers within the sender's window represent frames sent but
`as yet not acknowledged. Whenever a new packet arrives from the network layer,
`it is given the next highest sequence number, and the upper edge of the window is
`advanced by one. When an acknowledgement comes in, the lower edge is
`advanced by one. In this way the window continuously maintains a list of unack(cid:173)
`nowledged frames.
`
`4
`
`3
`
`4
`
`3
`
`4
`
`3
`
`4
`
`3
`
`Sender :\!): :~: :C): :0:
`
`Receiver 7 0 ·.c;7 .... 0
`6\3:..:·1
`
`6
`
`1
`
`6
`
`:
`.
`
`1
`
`7
`
`0
`
`"w~;:~;:1;'f4,
`
`6~1
`5y2
`
`5
`
`2
`
`5
`
`2
`
`5
`
`2
`
`4
`
`3
`
`(a)
`
`4
`
`3
`
`(b)
`
`4
`
`3
`
`(c)
`
`4
`
`3
`
`(d)
`
`Fig. 3-12. A sliding window of size 1, with a 3-bit sequence number.
`(a) Initially. (b) After the first frame has been sent. (c) After the first frame has
`been received. (d) After the first acknowledgement has been received.
`
`Since frames currently within the sender's window may ultimately be lost or
`damaged in transit, the sender must keep all these frames in its memory for possi(cid:173)
`ble retransmission. Thus if the maximum window size is n, the sender needs n
`buffers to hold the unacknowledged frames. If the window ever grows to its max(cid:173)
`imum size, the sending data link layer must forcibly shut off the network layer
`until another buff er becomes free.
`The receiving data link layer's window corresponds to the frames it may
`accept. Any frame falling outside the window is discarded without comment.
`When a frame whose sequence number is equal to the lower edge of the window
`is received, it is passed to the network layer, an acknowledgement is generated,
`and the window is rotated by one. Unlike the sender's window, the receiver's
`
`Ex.1006.222
`
`DELL
`
`

`

`SEC. 3.4
`
`SLIDING WINDOW PROTOCOLS
`
`205
`
`/* 0 or 1 only */
`/* 0 or 1 only */
`/* scratch variables */
`/* current packet being sent */
`
`/* Protocol 4 (sliding window) is bidirectional and is more robust than protocol 3. */
`#define MAX_SEQ 1
`/* must be 1 for protocol 4 */
`typedef enum {frame_arrival, cksum_err, timeout} evenUype;
`#include "protocol.h"
`void protocol4 (void)
`{
`seq_nr nexUrame_to_send;
`seq_nr frame_expected;
`framer, s;
`packet buffer;
`evenUype event;
`nexUrame_to_send = O;
`frame_expected = O;
`from_network_laye r( &buffer);
`s.info = buffer;
`s.seq = nexUrame_to_send;
`s.ack = 1 - frame_expected;
`to_physicaUayer( &s);
`starUimer(s.seq);
`while (true) {
`/* frame_arrival, cksum_err, or timeout*/
`waiUor_event(&event);
`if (event== frame_arrival) { /* a frame has arrived undamaged. */
`from_physicaUayer(8,r);
`/* go get it */
`
`/* next frame on the outbound stream */
`/* number of frame arriving frame expected */
`/* fetch a packet from the network layer */
`/* prepare to send the initial frame */
`/* insert sequence number into frame */
`/* piggybacked ack */
`/* transmit the frame */
`/* start the timer running */
`
`if (r.seq == frame_expected) {
`/* Handle inbound frame stream. */
`to_network_layer(&r.info); /* pass packet to network layer*/
`inc(frame_expected);
`/* invert sequence number expected next*/
`
`if (r.ack == nexUrame_to_send) { /* handle outbound frame stream. */
`from_network_layer(&buffer);
`/*fetch new pkt from network layer*/
`inc(nexUrame_to_send); /* invert sender's sequence number */
`
`}
`s.info = buffer;
`s.seq = nexUrame_to_send;
`s.ack = 1 - frame_expected;
`to_physicaUayer( &s);
`start_timer(s.seq);
`
`/*construct outbound frame */
`/* insert sequence number into it */
`/* seq number of last received frame */
`/* transmit a frame */
`/* start the timer running */
`
`}
`}
`
`Fig. 3-13. A 1-bit sliding window protocol.
`
`Ex.1006.223
`
`DELL
`
`

`

`206
`
`THE DAT A LINK LA YER
`
`CHAP. 3
`
`window always remains at its initial size. Note that a window size of 1 means
`that the data link layer only accepts frames in order, but for larger windows this is
`not so. The network layer, in contrast, is always fed data in the proper order,
`regardless of the data link layer's window size.
`Figure 3-12 shows an example with a maximum window size of 1. Initially,
`no frames are outstanding, so the lower and upper edges of the sender's window
`are equal, but as time goes on, the situation progresses as shown.
`
`3.4.1. A One Bit Sliding Window Protocol
`
`Before tackling the general case, let us first examine a sliding window proto(cid:173)
`col with a maximum window size of 1. Such a protocol uses stop-and-wait, since
`the sender transmits a frame and waits for its acknowledgement before sending
`the next one.
`Figure 3-13 depicts such a protocol. Like the others, it starts out by defining
`some variables. Next_frame_to__send tells which frame the sender is trying to
`send. Similarly, frame_expected tells which frame the receiver is expecting. In
`both cases, 0 and 1 are the only possibilities.
`Normally, one of the two data link layers goes first. In other words, only one
`of the data link layer programs should contain the to_physicaLlayer and
`start_timer procedure calls outside the main loop. In the event both data link
`layers start off simultaneously, a peculiar situation arises, which is discussed later.
`The starting machine fetches the first packet from its network layer, builds a
`frame from it, and sends it. When this (or any) frame arrives, the receiving data
`link layer checks to see if it is a duplicate, just as in protocol 3. If the frame is the
`one expected, it is passed to the network layer and the receiver's window is slid
`up.
`
`The acknowledgement field contains the number of the last frame received
`without error. If this number agrees with the sequence number of the frame the
`sender is trying to send, the sender knows it is done with the frame stored in
`buffer and can fetch the next packet from its network layer. If the sequence
`number disagrees, it must continue trying to send the same frame. Whenever a
`frame is received, a frame is also sent back.
`Now let us examine protocol 4 to see how resilient it is to pathological
`scenarios. Assume that A is trying to send its frame 0 to B and that B is trying to
`send its frame 0 to A. Suppose that A sends a frame to B, but A's timeout interval
`is a little too short. Consequently, A may time out repeatedly, sending a series of
`identical frames, all with seq = 0 and ack = 1.
`the first valid frame arrives at B,
`it will be accepted, and
`When
`frame_expected will be set to 1. All the subsequent frames will be rejected,
`because B is now expecting frames with sequence number 1, not 0. Furthermore,
`since all the duplicates have ack = 1 and B is still waiting for an acknowledge(cid:173)
`ment of 0, B will not fetch a new packet from its network layer.
`
`Ex.1006.224
`
`DELL
`
`

`

`

`

`208
`
`THE DATA LINK LAYER
`
`CHAP. 3
`
`consider a 50-kbps satellite channel with a 500-msec round-trip propagation
`delay. Let us imagine trying to use protocol 4 to send 1000-bit frames via the
`satellite. At t = 0 the sender starts sending the first frame. At t = 20 msec the
`frame has been completely sent. Not until t = 270 msec has the frame fully
`arrived at the receiver, and not until t = 520 msec has the acknowledgement
`arrived back at the sender, under the best of circumstances (no waiting in the
`receiver and a short acknowledgement frame). This means that the sender was
`blocked during 500/520 or 96 percent of the time (i.e., only 4 percent of the avail(cid:173)
`able bandwidth was used). Clearly, the combination of a long transit time, high
`bandwidth, and short frame length is disastrous in terms of efficiency.
`
`Time---
`
`(a)
`
`(b)
`
`Fig. 3-15. (a) Effect of an error when the receiver window size is l. (b) Effect
`of an error when the receiver window size is large.
`
`The problem described above can be viewed as a consequence of the rule
`requiring a sender to wait for an acknowledgement before sending another frame.
`If we relax that restriction, much better efficiency can be achieved. Basically the
`solution lies in allowing the sender to transmit up to w frames before blocking,
`instead of just 1. With an appropriate choice of w the sender will be able to
`
`Ex.1006.226
`
`DELL
`
`

`

`SEC. 3.4
`
`SLIDING WINDOW PROTOCOLS
`
`209
`
`continuously transmit frames for a time equal to the round-trip transit time
`without filling up the window. In the example above, w should be at least 26.
`The sender begins sending frame 0 as before. By the time it has finished sending
`26 frames, at t = 520, the acknowledgement for frame 0 will have just arrived.
`Thereafter, acknowledgements will arrive every 20 msec, so the sender always
`gets permission to continue just when it needs it. At all times, 25 or 26 unack(cid:173)
`nowledged frames are outstanding. Put in other terms, the sender's maximum
`window size is 26.
`This technique is known as pipelining. If the channel capacity is b bits/sec,
`the frame size l bits, and the round-trip propagation time R sec, the time required
`to transmit a single frame is lib sec. After the last bit of a data frame has been
`sent, there is a delay of R/2 before that bit arrives at the receiver, and another
`delay of at least R/2 for the acknowledgement to come back, for a total delay of
`R. In stop-and-wait the line is busy for lib and idle for R, giving a line utilization
`of ll(l + bR). If l < bR the efficiency will be less than 50 percent. Since there is
`always a nonzero delay for the acknowledgement to propagate back, in principle
`pipelining can be used to keep the line busy during this interval, but if the interval
`is small, the additional complexity is not worth the trouble.
`Pipelining frames over an unreliable communication channel raises some seri(cid:173)
`ous issues. First, what happens if a frame in the middle of a long stream is dam(cid:173)
`aged or lost? Large numbers of succeeding frames will arrive at the receiver
`before the sender even finds out that anything is wrong. When a damaged frame
`arrives at the receiver, it obviously should be discarded, but what should the
`receiver do with all the correct frames following it? Remember that the receiving
`data link layer is obligated to hand packets to the network layer in sequence.
`There are two basic approaches to dealing with errors in the presence of pipe(cid:173)
`lining. One way, called go back n, is for the receiver simply to discard all subse(cid:173)
`quent frames, sending no acknowledgements for the discarded frames. This strat(cid:173)
`egy corresponds to a receive window of size 1. In other words, the data link layer
`refuses to accept any frame except the next one it must give to the network layer.
`If the sender's window fills up before the timer runs out, the pipeline will begin to
`empty. Eventually, the sender will time out and retransmit all unacknowledged
`frames in order, starting with the damaged or lost one. This approach, shown in
`Fig. 3-15(a) can waste a lot of bandwidth if the error rate is high.
`The other general strategy for handling errors when frames are pipelined,
`called selective repeat, is to have the receiving data link layer store all the correct
`frames following the bad one. When the sender finally notices that something is
`wrong, it just retransmits the one bad frame, not all its successors, as shown in
`Fig. 3-15(b ). If the second try succeeds, the receiving data link layer will now
`have many correct frames in sequence, so they can all be handed off to the net(cid:173)
`work layer quickly and the highest number acknowledged.
`This strategy corresponds to a receiver window larger than 1. Any frame
`within the window may be accepted and buffered until all the preceding ones have
`
`Ex.1006.227
`
`DELL
`
`

`

`210
`
`THE DATA LINK LAYER
`
`CHAP. 3
`
`/* Protocol 5 (pipelining) allows multiple outstanding frames. The sender may transmit up
`to MAX_SEQ frames without waiting for an ack. In addition, unlike the previous protocols,
`the network layer is not assumed to have a new packet all the time. Instead, the
`network layer causes a network_layer_ready event when there is a packet to send. */
`
`/* should be 2"n - 1 */
`#define MAK_SEQ 7
`typedef enum {frame_arrival, cksum_err, timeout, network_layer_ready} evenUype;
`#include "protocol.h"
`
`static boolean between(seq_nr a, seq_nr b, seq_nr c)
`{
`/* Return true if (a <=b < c circularly; false otherwise. */
`if (((a<= b) && (b < c)) II ((c <a) && (a<= b)) II ((b < c) && (c <a)))
`return(true);
`else
`return(false);
`
`static void send_data(seq_nr frame_nr, seq_nr frame_expected, packet buffer[])
`{
`/* Construct and send a data frame. */
`frame s;
`/* scratch variable */
`
`/* insert packet into frame */
`s.info = buffer[frame_nr);
`/* insert sequence number into frame */
`s.seq = frame_nr;
`s.ack = (frame __ expected + MAX_SEQ) % (MAX_SEQ + 1 );/* piggyback ack */
`to_physicaUayer(&s);
`/*transmit the frame */
`start_timer(frame_nr);
`/* start the t