mmnvxnvmRMO,1,WmHmVNWMAmD]m
`
`

`
`
`
`
`
`.._<-.,..-_........
`
`To Joanna and Marie
`
`Editorial/production supervision by Margaret Rizzi
`Cover design by Wanda Lubelska
`Manufacturing buyer: Rhett Conklin
`
`© 1987 by Prentice—Hall, Inc.
`A Division of Simon 8: Schuster
`
`Englewood Cliffs, New jersey 07632
`
`All rights reserved. No part of this book may be
`reproduced, in any form or by any means,
`without permission in writing from the publisher.
`
`Printed in the United States of America
`
`1098765432
`
`ISBN El-1.3-l‘IEEIE5-'-i
`
`DES
`
`PRENTIcE—HALL INTERNATIONAL (UK) LIMITED, London
`PRENTIcE—HAI.I_ or AUSTRALIA PTY. LIMITED, Sydney
`PRENTIcE—I-{ALL CANADA INc., Toronto
`PRENTICE-HALL HISPANOAMERICANA, S.A., Mexico
`PRENTICE-HALL OF INDIA PRIVATE LIMITED, New Delhi
`
`PRENTICE-HALL OF JAPAN, INc., Tokyo
`PRENTICE-HALL or SOUTHEAST ASIA PTE. LTD., Singapore
`EDITORA PRENTICE-HALL DO BRASIL, LTD., Rio de janeiro
`
`
`
`llhl-‘i-a_-r.n£.-:._..-
`
`

`
`58
`
`Data Link Control and Communication Channels
`
`Chap. 2
`
`the above properties). Their generator polynomials are
`
`g(D) = D16 + D15 + D2 + 1,
`
`g(D) = D16 + D” + D5 + 1,
`
`for CRC—16
`
`for CRC—CCITT
`
`2.4 ARQ—RETRANSMISSION STRATEGIES
`
`The general concept of automatic repeat request (ARQ) is to detect frames with er-
`rors at the receiving DLC module and then to request the transmitting DLC module
`to repeat the information in those erroneous frames. Error detection was discussed
`in the last section, and the problem of requesting retransmissions is treated in this
`section. There are two quite different aspects of retransmission algorithms or proto-
`cols. The first is that of correctness; z'.e., does the protocol succeed in releasing each
`packet, once and only once, without errors, from the receiving DLC? The second is
`that of efficiency; i.e., how much of the bit transmitting capability of the bit pipe is
`wasted by unnecessary waiting and by sending unnecessary retransmissions? First,
`several classes of protocols are developed and shown to be correct (in a sense to be
`defined more precisely later). Later, the effect that the various parameters in these
`classes have on efiiciency is considered.
`Recall from Fig. 2.2 that packets enter the DLC layer from the network layer;
`a header and trailer are appended to each packet in the DLC module to form a
`frame and the frames are transmitted on the virtual bit pipe (z'.e., are sent to
`the physical layer for transmission). When errors are detected in a frame, a new
`frame containing the old packet is transmitted. Thus, the first transmitted frame
`might contain the first packet, the next frame the second packet, the third frame a
`repetition of the first packet, and so forth. When a packet is repeated, the header
`and trailer might or might not be the same as in the earlier version.
`Since framing will not be discussed until the next section, we continue to
`assume that the receiving DLC knows when frames start and end; thus a CRC (or
`any other technique) may be used for detecting errors. We also assume, somewhat
`unrealistically, that all frames with errors are detected. The reason for this is that
`we want to prove that ARQ works correctly except when errors are undetected.
`This is the best that can be hoped for, since error detection cannot work with
`perfect reliability and bounded delay; in particular, any code word can be changed
`into another code word by some string of transmission errors. This can cause
`erroneous data to leave the DLC or, perhaps worse, can cause some control bits to
`be changed.
`Next, a number of assumptions are made about the bit pipes over which these
`frames are traveling. These assumptions are somewhat more general than before.
`The major reason for this generality will appear when framing is studied; in effect,
`these general conditions will allow us to relax the assumption that the receiving
`DLC has framing information.
`
`H3-1.1‘.-u-—-—-_-
`
`

`
`Sec. 2.4
`
`ARQ—Retransmission Strategies
`
`59
`
`Transmitter departure times at A —-> I
`
`
`
`Receiver arrival times at B
`
`Model of frame transmissions: frame 2 is lost and never
`Figure 2.17
`arrives; frame 4 contains errors; the frames have variable transmission delay.
`but those that arrive do so in the order transmitted.
`
`Assume first that each transmitted frame is delayed by an arbitrary and vari-
`able time before arriving at the receiver, and assume that some frames might be
`“lost” and never arrive. Those frames that arrive, however, are assumed to arrive
`in the same order as transmitted, with or without errors. Figure 2.17 illustrates
`this behavior.
`
`2.4.1 Stop-and—Wa1't ARQ
`
`The simplest type of retransmission protocol is called st0p—and-wait. The basic
`idea is to ensure that each packet has been correctly received before initiating
`transmission of the next packet. Thus, in transmitting packets from point A to B,
`the first packet is transmitted in the first frame, and then the sending DLC waits.
`If the frame is correctly received at B, B sends an acknowledgment (called an ack)
`back to A; if the frame is received with errors, B sends a negative acknowledgment
`(called a nak) back to A. Since errors can occur from B to A as well as from A to
`B, the ack or nak is protected with a CRC.
`If a frame is received without errors at B, and the corresponding ack is received
`without errors at A, then A can start to send the next packet in a new frame.
`Alternatively, detected errors can occur either in the transmission of the frame or
`the return ack or nak, and in this case A resends the old packet in a new frame.
`Finally, if either the frame or the return ack or nak is lost, A must eventually time
`out and resend the old packet. Since frames can be arbitrarily delayed, it is possible
`for A to time out, to resend an old packet, and subsequently to get an ack or nak
`for the earlier transmission (see Fig. 2.18).
`Note that because of the time outs, and also because of the potential errors
`in the B to A channel, it is possible that B receives the first packet correctly
`in the first frame and then receives it again in the second frame (see Fig. 2.18).
`By assumption, packets are arbitrary bit strings, and the first and second packet
`could be identical. Thus, if B receives the same packet twice, it cannot tell whether
`
` ‘
`
`

`
`60
`
`Data Link Control and Communication Channels
`
`Chap. 2
`
`Transmitter departure times at A fir t
`
`
`
`JV
`Packei 0
`
`Packet 0 or 1?
`
`Receiver arrival times at B
`
`The trouble with unnumbered packets. If the transmitter at
`Figure 2.18
`A times out and sends packet 0 twice, then the receiver at B cannot tell whether
`the second frame is a retransmission of packet O or the first transmission of
`packet 1.
`
`Transmitter departure times at A —> t
`
`
`
`Receiver arrival times at B
`
`The trouble with unnumbered acks. If the transmitter at
`Figure 2.19
`A times out and sends packet 0 twice, and then sends packet 1 after the first
`ack, node A cannot tell whether the second ack is for packet 0 or 1.
`
`the second frame is repeating the first packet or sending the second packet (which
`happens to be the same bit string as the first packet).
`The simplest solution to this problem is for the sending DLC module (at A)
`to add a sequence number to identify successive packets. Although this strategy
`seems simple and straightforward, it will not work as just described. The problem
`is that acks can get lost on the return channel, and thus when B gets the same
`packet correctly twice in a row, it has to send a new ack for the second reception
`(see Fig. 2.19). Node A, after transmitting the packet twice but receiving only one
`ack, could transmit the next packet in sequence, and then on receiving the second
`ack, could interpret that as an ack for the new packet, leading to a potential failure
`of the system.
`To avoid this type of problem, the receiving DLC (at B), instead of returning
`ack or nak on the reverse link, returns the number of the next packet awaited. This
`
`

`
`Sec. 2.4
`
`ARQv—Retransmission Strategies
`
`i 61
`
`provides all the information of the ack/nak, but avoids ambiguities about which
`frame is being acked. An equivalent convention would be to return the number
`of the packet just accepted, but this is not customary. Node B can request this
`next awaited packet on the receipt of each packet, at periodic intervals, or at an
`arbitrary selection of times. In many applications, there is another stream of data
`from B to A, and in this case, the requests for the next packet in one direction are
`usually “piggybacked” into the header of the frames in the opposite direction.
`It should be evident that this stop—and—wait strategy, including the sender’s
`sequence number (SN) on each transmitted packet and the receiver’s request num-
`ber (RN) in the feedback direction, works correctly (assuming no CRC failures).
`Node A never sends a new packet until B requests it, thus signifying acceptance of
`the previous packet. and B always knows which packet it is receiving if the CRC
`checks. The only trouble is that the numbers SN and RN can become arbitrar-
`ily large as transmission continues. The final modification to the stop—and-wait
`strategy, then, is to transmit SN and RN with some modulus; it turns out that a
`modulus of 2 is suflicient.
`We now show why sending SN and RN modulo 2 works correctly for the given
`assumptions. Assume that the system st.arts initially with no frames in transit on
`the bit pipe, with A starting to send packet 0, and B looking for packet 0. Consider
`A as having two possible states, 0 and 1, corresponding to the number (modulo 2)
`of the packet currently being sent (or awaited from the higher layer if no packet
`currently exists). Thus, A starts in state 0; a transition to state 1 occurs upon
`receipt of an error—free request for packet 1 modulo 2. Note that A has to keep
`track of more information than just this state, such as the contents of the current
`packet and the time until time out, but the above binary state is all that is of
`concern here.
`Node B similarly is regarded as having two possible states, 0 and 1, corre-
`sponding to the number modulo 2 of the packet currently awaited. When a packet
`of the desired number modulo 2 is received, the DLC at B releases that packet
`to the higher layer and changes state, awaiting the next packet. The combined
`state of A and B is then initially (0,0); when the first packet is received error free,
`the state of B changes to 1, yielding a combined state (0, 1). When A receives
`the new RN value (z'.e., 1), the state of A changes to 1 and the combined state
`becomes (1,1). Note that there is a fixed sequence for these combined states, (0,0),
`(0,1), (1,1), (1.0), (0,0), etc., and that A and B alternate in changing states. It is
`interesting that at the instant of the transition from (0,0) to (0,1), B knows the
`combined state, but subsequently, up until the transition later from (1,1) to (1,0),
`it does not know the combined state (’f.6., B never knows that A has received the
`ack information until the next packet is received). Similarly, A knows the com-
`bined state at the instant of the transition from (0.1) to (1,1) and of the transition
`from (1,0) to (0,0). The combined state is always unknown to either A or B, and
`is frequently unknown to both. The situation here is very similar to that in the
`three-army problem discussed in section 1.4. Here, however, information is trans-
`mitted even though the combined state information is never jointly known, whereas
`
`

`
`52
`
`Data Link Control and Communication Channels
`
`Chap. 2
`
`in the three—army problem, it is impossible to coordinate an attack because of the
`impossibility of obtaining this joint knowledge.
`The stop-and—wait strategy is not very useful for modern data networks be-
`cause of its highly ineflicient use of communication links. The problem is that it
`should be possible to do something else while waiting for an ack. There are three
`common strategies for extending the basic idea of stop-and-wait so as to achieve
`higher efficiency:
`the ARPANET ARQ, go back 72 ARQ, and, finally, selective
`repeat ARQ.
`
`2.4.2 ARPANET ARQ
`
`The ARPANET achieves efficiency by using eight stop-and-wait strategies in par-
`allel, multiplexing the bit pipe between the eight. That is, each incoming packet is
`assigned to one of eight virtual channels, assuming that one of the eight is idle; if
`all the virtual channels are busy, the incoming packet waits outside the DLC (see
`Fig. 2.20). The busy virtual channels are multiplexed on the bit pipe in the sense
`that frames for the different virtual channels are sent one after the other on the
`link. The particular order in which frames are sent is not very important, but a
`simple approach is to send them in round robin order. If a virtual channel’s turn
`for transmission comes up before an ack has been received for that virtual channel,
`then the packet is sent again, so that the multiplexing removes the need for any time
`outs.
`(The actual ARPANET protocol, however, does use time outs.) When an
`ack is received for a frame on a given virtual channel, that virtual channel becomes
`idle and can accept a new packet from the higher layer.
`Somewhat more overhead is required here than in the basic stop-and—wait pro-
`tocol. In particular, each frame carries both the virtual channel number (requiring
`three bits), and the sequence number modulo 2 (z'.e., one bit) of the packet on that
`virtual channel. The acknowledgment information is piggybacked onto the frames
`going in the opposite direction. Each such frame in fact carries information for all
`eight virtual channels. In particular, an eight bit field in the header of each return
`frame gives the number modulo 2 of the awaited packet for each virtual channel.
`One of the desirable features of this strategy is that the ack information is
`repeated so often (i.e., for all virtual channels in each return frame), that relatively
`few retransmissions are required because of transmission errors in the reverse di-
`rection. Typically, only one retransmission is required for each frame in error in
`the forward direction. We shall see that the go back 71, protocol to be discussed
`next requires more retransmissions and thus has a somewhat lower link efficiency.
`The undesirable feature of the ARPANET protocol is that packets are released
`to the higher layer at the receiving DLC in a different order than that of arrival
`at the sending DLC. The DLC layer could, in principle, reorder the packets, but
`since a packet on one virtual channel could be arbitrarily delayed, an arbitrarily
`large number of later packets might have to be stored. The ARPANET makes no
`effort to reorder packets on individual links, so this protocol is not a problem for
`ARPANET. We shall see later that the lack of ordering on links generates a number
`
`

`
`Sec. 2.4
`
`ARQ—Retransmission Strategies
`
`63
`
`Stop and wait virtual channel A
`
`
`
`lncoming packets
`
`Stop and wait virtual channel H
`
`la)
`
`Virtual channel
`SN I-1
`1-
`
`E -1
`
`One bit RN for each virtual channel
`
`p..|
`
`(b)
`
`N OA packet 1
`
`08 packet 2
`
`1A packet 3
`
`
`OB packet 2
`0A packet 4
`
`
`
`
`
`RN
`
`Packetl
`
`Packet3
`
`Packet2
`
`(c)
`
`ARPANET ARQ. (a) Eight multiplexed, stop-and—wait
`Figure 2.20
`(b) Bits in the header for ARQ control.
`(c) Operation of
`virtual channels.
`multiplexed stop and wait for two virtual channels. Top to bottom frames
`show SN and the channel number, and bottom to top frames show RN for
`both channels. The third frame from bottom to top acks packet 1 on the A
`channel.
`
`of problems at higher layers. Most modern networks maintain packet ordering for
`this reason, and consequently do not use this protocol despite its high efiiciency and
`low overhead. For very poor communication links, where efficiency and overhead
`are very important, it is a reasonable choice.
`
`2.4.3 Go back 71 ARQ
`
`it appears in
`Go back 11 ARQ is the most widely used type of ARQ protocol;
`the various standard DLC protocols, such as HDLC, SDLC, ADCCP, and LAPB.
`It is not elucidating to know the meaning of these acronyms, but, in fact, these
`standards are almost the same. They are discussed in section 2.6, and some of
`their differences are mentioned there.
`
`

`
`64
`
`Data Link Control and Communication Channels
`
`Chap. 2
`
`
`
`Go back 4 protocol. Send numbers SN are shown for
`Figure 2.21
`frames going from A to B, and receive numbers RN are shown in frames from
`B to A. Note that an error in the second frame forces node A to retransmit
`packet 1 after packet 4. An error in the return frame carrying RN = 2 causes
`no problem.
`
`The basic idea of go back n is very simple. Incoming packets to a transmitting
`DLC module for a link from A to B are numbered sequentially, and this sequence
`number SN is sent. in the header of the frame containing the packet.
`In contrast
`to st0p—and—wait, successive packets are sent without waiting for the next packet
`to be requested. The receiving DLC at B sends request numbers RN back t.o A
`requesting packet RN and acknowledging all packets prior to RN.
`The go back number n in a go back 71 protocol is a parameter that determines
`how many successive packets can be sent in the absence of a request for a new
`packet. Specifically, node A is not allowed to send packet z" + 71 before 2' has been
`acknowledged (2'.e., before i + 1 has been requested). For any given time, let ymm
`denote the number of the last request number RN that A has received from B.
`Then, in a go back 71 system, A can send packets with numbers in the ‘‘window‘’
`from ymm to 3/mm + n — 1, but cannot send higher numbered packets. As succes—
`sively higher numbered packets are requested, ymm increases and this window slides
`upward; thus, go back n protocols are often called sliding window ARQ protocols.
`The operation of the receiving DLC (node B) in a go back n protocol is es-
`sentially the same as stop-and—wait. Packets are accepted in order, and the number
`of the next desired packet, RN, is sent in the header of each packet in the reverse
`direction. For the present, assume that RN and SN are integers that can be arbi«
`trarily large: later it will be shown that they can be sent modulo m for a modulus
`m > n. Thus, when B receives a packet containing errors, it cannot accept any
`of the higher numbered packets until A goes back and retransmits the packet that
`was received in error.
`Figure 2.21 illustrates this operation for the case of go back 4. We focus on
`the flow of packets from A to B. Thus, the sequence numbers SN are shown for
`the frames going from A to B, and the receive numbers RN, providing acks for the
`A to B traffic, are shown in the feedback frames from B to A. Assume that RN
`
`

`
`Sec. 2.4
`
`ARQ—Retransmission Strategies
`
`65
`
`‘/min
`SN6
`Node/A
`
`5
`
`7
`
`7
`8
`9
`10
`I
`sis 6|7l8 9|'1o11129l
`
`-Q—
`
`\l-I-—
`
`OO-ul-—--
`
`l
`
`12
`10
`ill10 11 12
`
`
`
`
`
`Continuation of Fig. 2 21 for go back 4 ARQ. Note that an
`Figure 2.22
`error in the reverse frame carrying RN = 6 causes node A to go back to packet
`5. Note also that long reverse frames cause node A to go back and retransmit
`packet 9.
`
`is placed in the frame header, so that when a packet is correctly received at B, the
`new RN is sent back in the following reverse frame; this RN cannot be used at A
`until the CRC at the end of that reverse frame is checked. Note in particular the
`ack for packet number 0; the packet is received at B while B is sending its own
`second frame, and thus it is acked (by RN = 1) in B’s third frame. Node A cannot
`“believe” the information until the end of the frame when the CRC is checked, and
`at this time ymin is changed as shown.
`Note that when an error occurs in the second frame from A, A continues with
`new packets as far as possible, and then repeats packet 1 after packet 4 (strangely,
`this is regarded as going back 4 from packet 5. which would normally follow 4, to
`1). Node A thus repeats four packets for the one error.
`this
`Next, consider the error in the first reverse frame carrying RN = 2:
`causes no problem for the forward traffic since the next reverse frame arrives before
`
`A is required to go back. Figure 2.22 (which is a continuation of Fig. 2.21) shows
`another example of an error, in the first frame from B carrying RN : 6, in which
`A is required to go back.
`While A is retransmitting packet 5 in this example. RN = 7 arrives from B.
`Some implementations of go back 72 (such as the one illustrated) will foolishly follow
`packet 5 by packet 6 in this type of situation, and others will jump ahead and send
`packet 7 next. as requested. Finally, at the end of the diagram, it is seen that node
`A goes back because some long frames from B delayed the ack information. All the
`retransmissions in Fig. 2.22 could have been avoided by a larger choice of n. These
`efficiency aspects of go back 71 are explored later. but first we define the protocol
`more carefully and show that it works correctly.
`There are many variations of go back 7; protocols. One of these appeared
`in Fig. 2.22. Another more important variation is the use of time outs or extra
`feedback information to determine when to go back and retransmit. Thus. we
`want to demonstrate the correctness of an entire class of protocols. We continue to
`assume that frames may be lost or arbitrarily delayed, and that all frames detected
`
`L_j____,
`
`

`
`66
`
`Data Link Control and Communication Channels
`
`Chap. 2
`
`ymin
`
`Vmax
`
`Not yet sen’!
`Range of yrec
`
`
`Range of n packets
`
`
`Ymin*
`
`n—1
`
`
`
`ymin'l
`Acknowledged packets I
`Vmax'
`
`
`
`Range of n-1 packets
`
`Allowable range for transmitted packets
`
`Allowable range for packets in a go back n ARQ system.
`Figure 2.23
`ymm is the smallest packet number not yet acknowledged and ymax — 1 is
`the largest packet number yet sent.
`The awaited packet at the receiving
`DLC lies between ymm and ymax. The top dashed line indicates the range
`from the smallest allowable transmitted packet number to the largest possi-
`ble awaited number. The bottom dashed line is the range from the smallest
`awaited number to the largest transmitted number.
`
`as error free are in fact error free and arrive in the order sent. We also assume
`
`that SN and RN are arbitrary integers: the practical case in which SN and RN
`are sent within some modulus is considered later. The rules followed at a sending
`DLC, as a function of the go back number n, are now given and then followed by
`explanatory comments.
`
`Rules Followed by the Sending DLC
`
`The Variable ymm initially has the value 0. Whenever an error—free frame is received
`on the reverse link by the sending DLC module, ymin is updated to equal the receive
`number RN in that frame. There is a variable ymax with initial value 0: after packet
`transmissions start, 3/max is maintained to be 1 greater than the number of the
`largest numbered packet yet sent. When a new frame is prepared for transmission,
`the packet placed in the frame is constrained to have a number 2 Z 0 in the range
`(see Fig. 2.23)
`
`ymax ‘ 71 S 3 S ,7/min ‘l’ 71 —1
`
`(224)
`
`A sequence number SN = 2 is sent in the header of the frame. New packets
`arrive, on request and as available, from the next higher layer and are sequentially
`numbered starting from 0. These packets. while in the range of Eq. (2.24), are
`buffered, conceptually within the DLC module. Finally, there is some T > 0 such
`that, if the packet numbered ymin is available, it will be transmitted at least once
`each T seconds until ymin changes (z'.e., ymm is acked).
`The significance of the notation ymax above is as follows: assume the sending
`DLC is sending from A to B; since packet ymax has never been sent, it is an upper
`bound on the packet awaited by B. Similarly, as noted before, ymin is a lower bound
`on the packet awaited by B. It will be seen shortly that ymm can never decrease,
`and therefore Eq.
`( 2.24) asserts that the highest numbered packet yet transmitted
`
`

`
`Sec. 2.4
`
`ARQ —Retransmission Strategies
`
`can never exceed ymin + n — 1. Thus, ymax must satisfy
`
`3/max S 3/min ‘l‘ 71
`
`67
`
`(2-25)
`
`This means that the lower limit on 2 in Eq. (2.24) is always less than or equal to
`ymin, thus always allowing packet ymm to be sent.‘ Note that in the example of
`Fig. 2.22, when A went back,
`it went back to 2/max ~ n; thus, the lower limit in
`Eq. (2.24) allows A to keep sending packets in order after going back, even when
`ym-1,, jumps to a larger value.
`These rules permit A to send and resend packets in any order so long as
`they lie in the range of Eq. (2.24) (see Fig. 2.23). This provides the flexibility to
`use available timing information or subsidiary feedback information to increase the
`efficiency of the algorithm without worrying about correctness (after the class of
`protocols is shown to be correct).
`The timing constraint that ymm is sent at least once each T seconds is some-
`what artificial; its purpose is to exclude protocols that never go back and transmit
`the desired packet. Note, however, that the higher layer might have no new pack-
`ets to send for an arbitrarily long time. Thus, if the last packet from the higher
`layer is ym-m, then the timing rule (as well as common sense) forbids waiting until
`ymin + n — 1 comes from the higher layer.
`In other words, a “pure” go back 72
`strategy, which only goes back to ymm after sending ymin + n — 1, will not function
`properly if the higher layer can run out of packets; such a strategy is ruled out by
`the timing assumption above. Some sort of time out feature is required in go back
`n protocols.
`Finally, note that RN is compared with ymm for each error—free return frame.
`Problem 2.19 shows that the protocol can deadlock (z'.e., reach a point from which
`no further packets can be received) if RN is compared only for frames containing
`the awaited packet in the reverse direction.
`
`Rules Followed by Receiving DLC
`
`The receiving DLC has a variable yrec initially set to 0. When an error—free frame
`arrives, the sequence number SN in the frame is compared to ym. If SN = ymc.
`then the packet in the frame is accepted, it is passed to the higher layer, and the
`variable yrec is incremented. The latest value of yrec is used as the receive number
`RN in each frame on the reverse link. Finally, there is some T > 0 such that at least
`one such reverse frame is sent each T seconds. This implies that if a DLC module
`has no packets to send, it still must send receive numbers (at least each T seconds)
`to acknowledge the opposite trafiic; this requires some type of “supervisory” frame
`carrying no packet data. The fact that yrec is nondecreasing in time, coupled with
`the fact that the reverse frames carrying RN stay in order. insures that gum,
`is
`nondecreasing in time.
`It will now be shown that this class of protocols is correct in the sense that
`if the receiving DLC is waiting for the packet numbered ym, and if that packet is
`
`

`
`68
`
`Data Link Control and Communication Channels
`
`Chap. 2
`
`available at the sending side, then that packet will eventually be delivered correctly
`to the higher layer at the receiving side. Assume that the probability of error in
`any frame transmitted in either direction is at most some constant p strictly less
`than 1.
`
`While the receiving side is waiting for a frame with SN = yrec, the frames
`in the reverse direction contain RN = yrec and are sent at least each T seconds.
`With probability 1, one of these frames is eventually received error free (given that
`yrec doesn’t change first). At this point, ymm at the sending side becomes equal
`to 3/we and this equality is maintained until ymc changes (zIe., until the packet is
`correctly received). The sending side must then send packet yrec at least once each
`T seconds, so it will be correctly received eventually with probability 1. Thus, with
`the given assumptions, this class of protocols is correct.
`
`Go back 72 with Modulus m > n
`
`It will now be shown that if the sequence number SN and the receive number RN
`are sent modulo m, for some m > n, then the protocol continues to work correctly.
`An intuitive argument for this is illustrated by Fig. 2.23. One dashed line in the
`figure goes from the smallest possible packet number 2 to the largest possible yrec,
`and the other dashed line from the smallest yrec to the largest 2. The magnitude
`I2 — 3/rec] is at most n, which is less than m. Thus, if SN (which is 2 modulo m)
`equals yrec, it must be that 2 = yrec. To make this argument precise, one must be
`more careful about timing, ’f.€.,
`the fact that packet 2 might be arbitrarily delayed
`on the link.
`
`First assume that only SN is sent modulo m, whereas RN is an unrestricted
`integer as before. Consider a link from node A to B and let ymm, yremymax, and
`the packet number 2 be unrestricted integers as before. The rules at the sending
`DLC (node A) are the same as before, except that SN = 2 modulo m. The rules
`at the receiving DLC (node B) are also the same as before, except that SN = yrec
`modulo m is the new criterion for accepting a packet, passing it to the next higher
`layer, and incrementing yrec. We shall show that packets are accepted at B for
`the system in which SN = 2 modulo m if and only if (iff) they would have been
`accepted for the system with no modulus (i.e., iii" 2 = yrec).
`Let t be the time at which an error—free frame arrives at B and let t’ < t be
`
`the time at which that frame was prepared for transmission at A. Let ygml and
`yfmax be the values of ymiu and ymax at time 15’. An important relation between
`these quantities for the system without the modulus is
`
`yfnin S 3/rec —<— yfnax
`
`(226)
`
`The first inequality above is true because yfimn is the last Value of RN received at
`A before t’ ; that value of RN is a yet earlier value of yrec at node B, which is less
`than or equal to yrec at time t. The second inequality is true because yfnax has not
`been sent by A before If’ ; by the ordering of frames on the A —-> B link, y,’mx cannot
`have reached B before 2 (2Ie., before time t).
`
`

`
`69
`
`Sec. 2 .4
`
`ARQ~Retransmission Strategies
`dulo m, induction will be used on the
`SN=2m0
`B. We use Eq. (2.26) as the
`To prove correctness when
`free frames arrive at
`successive times at which error-
`modulo m = SN iff y,eC = 2.
`inductive hypothesis, and use this to show that yrec
`ms the same update at time
`This will show that the system with a modulus perfor
`until the next error~free
`t as the modulus-free system: this will establish Eq. (2.26)
`-free arrival at B,
`B. Note that Eq. (2.26) holds before the first error
`arrival at
`r the induction.
`smission at time 15’, Eq. (2.24) asserts
`providing a basis fo
`When the packet 2 is prepared for tran
`
`that
`
`yi'nax_nSZ—<—yinin+n~1
`Combining the first half of Eq. (2.27) with the last half of Eq. (2.26),
`2 _>_ yinax ~ n 2 yrec ~ n
`
`(2.27)
`
`(2.28)
`
`Combining Eqs. (2.26) and (2.27) in the opposite way,
`2§y(n«m+n—1§yrec+n~1
`The two dashed lines in Fig. 2.23 illustrate these relations; what has been
`discussion is a precise interpretation of appropriate
`added to the previous intuitive
`timing of events at sending and receiving DLCS. Combining these two relations,
`
`(2.29)
`
`(2.30)
`
`This implies that 2 — y,eC modulo m 2 0 iff 2 2 ym, Thus, the class of protocols
`for n < m is correct with SN 2 2 modulo m.
`Finally,
`bers RN are also sent modulo m. Thus,
`assume that the receive num
`the receiving DLC sets RN in each reverse frame to be yrec modulo m, using the
`current value of y,eC. The rule for updating ymm at the sending DLC is changed as
`follows: whenever an error—free frame arrives in the reverse direction, the value of
`RN in the frame modifies ymin by the rule
`until ymm modulo m = RN
`
`(231)
`
`To show that correctness is st
`which error-free reverse frames arriv
`time at which a given reverse
`,
`time that the frame was prepared at B. Let 1/,“ denote ymc at B at that earlier
`time. The appropriate relation satisfied by the system without any modulus (and
`
`' duction on the times at
`(node A). Let t be the
`
`"s sent with a modulus) is
`
`(2.32)
`
`

`
`70
`
`Data Link Control and Communication Channels
`
`Chap. 2
`
`
`
`Go back 7 ARQ with long frames in the reverse direction.
`Figure 2.24
`Note that the ack for packet 1 has not arrived at the sending side by the time
`packet 6 finishes transmission, thereby causing a retransmission of packet O.
`
`The first part of Eq. (2.32) follows from the ordering of frames on the B -+ A link;
`no frame sent by B after t’ can arrive before t. The second part follows since ymax
`has not been sent from A before If, and certainly cannot have arrived at B before
`t’. The third part follows from Eq. (2.25).
`We use Eq.
`(2.32) as an inductive hypothesis as before. The rule (2.31)
`updates ymm to a value y satisfying y modulo m = RN = yfec modulo m and also
`satisfying ymin S y 3 ymin + m ~ 1. Since n < m, it is seen from Eq. (2.32) that
`y = y,’,eC, completing the proof of correctness.
`At this point, we can see that it is unnecessary for ymin, y,ec, and ymax to be
`saved as unrestricted integers; all values can be stored modulo m.
`
`Efficiency of Go back 71, Implementations
`
`Retransmissions, or delays waiting for time outs, oc