Digital Logic

Digital Logic

The CRC process can be represented by, and indeed implemented as, a dividing circuit

consisting of exclusive-or gates and a shift register. The shift register is a string

of 1-bit storage devices. Each device has an output line, that indicates the value currently

stored, and an input line. At discrete time instants, known as clock times, the

value in the storage device is replaced by the value indicated by its input line.

The entire register is clocked simultaneously, causing a 1-bit shift along the entire

register.

The circuit is implemented as follows:

1. The register contains n bits, equal to the length of the FCS.

2. There are up to n exclusive-or gates.

3. The presence or absence of a gate corresponds to the presence or absence of

a term in the divisor polynomial, P(X).

The architecture of this circuit is best explained by first considering an example,

which is illustrated in Figure 6.6. In this example, we use

which were used earlier in the discussion.

Part (a) of the figure shows the shift register implementation. The process

begins with the shift register cleared (all zeros). The message, or dividend, is then

entered, one bit at a time, starting with the most significant bit. Part (b) is a table

that shows the step-by-step operation as the input is applied one bit at a time. Each

row of the table shows the values currently stored in the five shift-register elements.

In addition, the row shows the values that appear at the outputs of the three exclusive-

or circuits. Finally, the row shows the value of the next input bit, which is available

for the operation of the next step.

Because no feedback occurs until a 1-dividend bit arrives at the most significant

end of the register, the first five operations are simple shifts. Whenever a 1 bit

arrives at the left end of the register ( 4 , a 1 is subtracted (exclusive-or) from the

second (c,), fourth (el), and sixth (input) bits on the next shift. This is identical to

the binary long-division process illustrated earlier. The process continues through

all the bits of the message, plus five zero bits. These latter bits account for shifting

M to the left five position to accommodate the FCS. After the last bit is processed,

the shift register contains the remainder (FCS), which can then be transmitted.

At the receiver, the same logic is used. As each bit of M arrives, it is inserted

into the shift register. If there have been no errors, the shift register should contain

the bit pattern for R at the conclusion of M. The transmitted bits of R now begin to

arrive, and the effect is to zero-out the register so that, at the conclusion of reception,

the register contains all 0s.

 

ERROR CONTROL

Error control refers to mechanisms to detect and correct errors that occur in the

transmission of frames. The model that we will use, which covers the typical case, is

illustrated in Figure 6.lb. As before, data are sent as a sequence of frames; frames

arrive in the same order in which they are sent; and each transmitted frame suffers

an arbitrary and variable amount of delay before reception. In addition, we admit

the possibility of two types of errors:

Lost frame. A frame fails to arrive at the other side. For example, a noise

burst may damage a frame to the extent that the receiver is not aware that a

frame has been transmitted.

Damaged frame. A recognizable frame does arrive, but some of the bits are in

error (have been altered during transmission).

The most common techniques for error control are based on some or all of the

following ingredients:

Error detection. As discussed in the preceding section.

Positive acknowledgment. The destination returns a positive acknowledgment

to successfully received, error-free frames.

Retransmission after timeout. The source retransmits a frame that has not

been acknowledged after a predetermined amount of time.

Negative acknowledgment and retransmission. The destination returns a negative

acknowledgment to frames in which an error is detected. The source

retransmits such frames.

Collectively, these mechanisms are all referred to as automatic repeat request

(ARQ); the effect of ARQ is to turn an unreliable data link into a reliable one.

Three versions of ARQ have been standardized:

Stop-and-wait ARQ

Go-back-N ARQ

Selective-reject ARQ

All of these forms are based on the use of the flow control technique discussed

in Section 6.1. We examine each in turn.

Stop-and-Wait ARQ

Stop-and-wait ARQ is based on the stop-and-wait flow-control technique outlined

previously and is depicted in Figure 6.8. The source station transmits a single frame

and then must await an acknowledgment (ACK). No other data frames can be sent

until the destination station's reply arrives at the source station.

Two sorts of errors could occur. First, the frame that arrives at the destination

could be damaged; the receiver detects this by using the error detection technique

referred to earlier and simply discards the frame. To account for this possibility, the

source station is equipped with a timer. After a frame is transmitted, the source station

waits for an acknowledgment. If no acknowledgment is received by the time

the timer expires, thenthe same frame is sent again. Note that this method requires

that the transmitter maintain a copy of a transmitted frame until an acknowledgment

is received for that frame.

The second sort of error is a damaged acknowledgment. Consider the following

situation. Station A sends a frame. The frame is received correctly by station B,

which responds with an acknowledgment (ACK). The ACK is damaged in transit

and is not recognizable by A, which will therefore time-out and resend the same

frame. This duplicate frame arrives and is accepted by B, which has therefore

accepted two copies of the same frame as if they were separate. To avoid this problem,

frames are alternately labeled with 0 or 1, and positive acknowledgments are

of the form ACKO and ACK1. In keeping with the sliding-window convention, an

ACKO acknowledges receipt of a frame numbered 1 and indicates that the receiver

is ready for a frame numbered 0.

The principal advantage of stop-and-wait ARQ is its simplicity. Its principal

disadvantage, as discussed in Section 6.1, is that stop-and-wait is an inefficient

mechanism. The sliding-window flow control technique can be adapted to provide

more efficient line use; in this context, it is sometimes referred to as continuous

ARQ.

Go-back-N ARQ

The form of error control based on sliding-window flow control that is most commonly

used is called go-back-N ARQ.

In go-back-N ARQ, a station may send a series of frames sequentially numbered

modulo some maximum value. The number of unacknowledged frames outstanding

is determined by window size, using the sliding-window flow control

technique. While no errors occur, the destination will acknowledge (RR = receiveready)

incoming frames as usual. If the destination station detects an error in a

frame, it sends a negative acknowledgment (REJ = reject) for that frame. The destination

station will discard that frame and all future incoming frames until the

frame in error is correctly received. Thus, the source station, when it receives an

REJ, must retransmit the frame in error plus all succeeding frames that were transmitted

in the interim.

Consider that station A is sending frames to station B. After each transmission,

A sets an acknowledgment timer for the frame just transmitted. The go-back-

N technique takes into account the following contingencies:

I. Damaged frame. There are three subcases:

a) A transmits frame i. B detects an error and has previously successfully

received frame (i - 1). B sends REJ i, indicated that frame i is rejected.

When A receives the REJ, it must retransmit frame i and all subsequent

frames that it has transmitted since the original transmission of frame i.

b) Frame i is lost in transit. A subsequently sends frame (i + 1). B receives

frame (i + 1) out of order and sends an REJ i. A must retransmit frame i

and all subsequent frames.

c) Frame i is lost in transit, and A does not soon send additional frames. B

receives nothing and returns neither an RR nor an REJ. When A's timer

expires, it transmits an RR frame that includes a bit known as the P bit,

which is set to 1. B interprets the RR frame with a P bit of 1 as a command

that must be acknowledged by sending an RR indicating the next frame

that it expects. When A receives the RR, it retransmits frame i.

2. Damaged RR. There are two subcases:

a) B receives frame i and sends RR (i + I), which is lost in transit. Because

acknowledgments are cumulative (e.g., RR 6 means that all frames

through 5 are acknowledged), it may be that A will receive a subsequent

RR to a subsequent frame and that it will arrive before the timer associated

with frame i expires.

b) If A's timer expires, it transmits an RR command as in Case lc. It sets

another timer, called the P-bit timer. If B fails to respond to the RR command,

or if its response is damaged, then A's P-bit timer will expire. At this

point, A will try again by issuing a new RR command and restarting the

P-bit timer. This procedure is tried for a number of iterations. If A fails to

obtain an acknowledgment after some maximum number of attempts, it

initiates a reset procedure.

3. Damaged REJ. If an REJ is lost, this is equivalent to Case lc.

Figure 6.9 is an example of the frame flow for go-back-N ARQ. Because of the

propagation delay on the line, by the time that an acknowledgment (positive or negative)

arrives back at the sending station, it has already sent two additional frames

beyond the one being acknowledged. Thus, when an REJ is received to frame 5, not

only frame 5, but frames 6 and 7, must be retransmitted. Thus, the transmitter must

keep a copy of all unacknowledged frames.

In Section 6.1, we mentioned that for a k-bit sequence number field, which

provides a sequence number range of 2k, the maximum window size is limited to

2^k - 1. This has to do with the interaction between error control and acknowledgment.

Consider that if data are being exchanged in both directions, station B must

send piggybacked acknowledgments to station A's frames in the data frames being

transmitted by B, even if the acknowledgment has already been sent; as we have

mentioned, this is because B must put some number in the acknowledgment field of

its data frame. As an example, assume a 3-bit sequence number (sequence-number

space = 8). Suppose a station sends frame 0 and gets back an RR 1, and then sends

frames 1, 2, 3, 4, 5, 6, 7, 0 and gets another RR 1. This could mean that all eight

frames were received correctly and the RR 1 is a cumulative acknowledgment. It

could also mean that all eight frames were damaged or lost in transit, and the receiving

station is repeating its previous RR 1. The problem is avoided if the maximum

window size is limited to 7 (2^3 - 1).

Selective-reject ARQ

With selective-reject ARQ, the only frames retransmitted are those that receive a

negative acknowledgment, in this case called SREJ, or that time-out. This would

appear to be more efficient than go-back-N, because it minimizes the amount of

retransmission. On the other hand, the receiver must maintain a buffer large

enough to save post-SREJ frames until the frame in error is retransmitted, and it

must contain logic for reinserting that frame in the proper sequence. The transmitter,

too, requires more complex logic to be able to send a frame out of sequence.

Because of such complications, select-reject ARQ is much less used than go-back-

N ARQ.

The window-size limitation is more restrictive for selective-reject than for goback-

N. Consider the case of a 3-bit sequence-number size for selective-reject.

Allow a window size of seven, and consider the following scenario [TANE88]:

1. Station A sends frames 0 through 6 to station B.

2. Station B receives all seven frames and cumulatively acknowledges with

RR 7.

3. Because of a noise burst, the RR 7 is lost.

4. A times out and retransmits frame 0.

5. B has already advanced its receive window to accept frames 7,0,1,2,3,4, and

5. Thus, it assumes that frame 7 has been lost and that this is a new frame 0,

which it accepts.

The problem with the foregoing scenario is that there is an overlap between

the sending and receiving windows. To overcome the problem, the maximum window

size should be no more than half the range of sequence numbers. In the scenario

above, if only four unacknowledged frames may be outstanding, no confusion

can result. In general, for a k-bit sequence number field, which provides a sequence

number range of 2^k, the maximum window size is limited to 2^(k-1).