Bit Stuffing

  • Use reserved bit patterns to indicate the start and end of a frame

Example

  • If the frame delimiter is 0111 At the beginning and end of each frame we use this sequence
  • 0111##########0111###############0111########0111
  • If the delimiter appears in the data then we have to mask it by stuffing bits into the data
  • Within the frame, replace every occurrence of two consecutive l's with 110 i.e. stuff (insert) a zero bit after each pair of l's in the data. This prevents 3 consecutive l's from ever appearing in the frame.
  • Likewise, the receiver converts two consecutive l's followed by a 0 into two l's, but recognises the 0111 sequence as the end of the frame.
  • The frame "1011101" would be transmitted over the physical layer as
  • "0111 10110101 0111".
  • Note: When using bit stuffing, locating the start/end of a frame is easy, even when frames are damaged . The receiver simply scans arriving data for the reserved patterns. Moreover, the receiver will re-synchronise quickly with the sender as to where frames begin and end, even when bits in the frame get garbled.
  • The main disadvantage with bit stuffing is the insertion of additional bits into the data stream, wasting bandwidth. How much expansion? The precise amount depends on the frequency in which the reserved patterns appear as user data.

Ex 2.

use the 8-bit sequence of 01111110 to delimit consecutive frames

Character stuffing: Same idea as bit-stuffing, but operates on bytes instead of bits.

Encoding Violations

Send a signal that doesn't conform to any legal bit representation.

In Manchester encoding, for instance, 1-bits are represented by a high-low sequence, and 0-bits by low-high sequences. The start/end of a frame could be represented by the signal low-low or high-high. The advantage of encoding violations is that no extra bandwidth is required as in bit-stuffing.

So here for example you are using ME any prolonged high or low out of sequence with the interval must be noise

Error Correcting Codes

A bit stream has enough redundant information in it to allow for errors to be detected and corrected

Requires the use of code words which are used in the place of the original data

Hamming distance

The amount of bits that need to be changed before the code is unrecognisable

ex

10001001

EOR10110001

00111000this has 3 bits in the result

Therefore the Hamming distance of these codes is 3

we can therefore correct an error for example if a code comes in as 11001001 it can only be the first code

Error Detecting Codes

Most simple scheme used here is the parity bit scheme

commonly used on ASCII character streams

For EVEN parity an extra bit is added to the 7 bit character

eg E = 1000101 (decimal 69) we would add 1 making it

10001011

for ODD parity 10001010

Here the Hamming distance is only 2 therefore there is not enough information to correct it as only a change to one bit could not be recovered therefore we use Parity bits for error detection

However, should there be two bits in error then the parity bit scheme falls down

Check Sums

Polynomial Code or cyclic redundancy code (CRC)

Data Link protocols

The Stop-and-Wait protocol (protocol 2 Tanenbaum)

This protocol suffers from poor performance under long delays e.g. a satellite link running at 64 kbps with a frame size of 10000 bits takes approx 10000/64000 = .15 seconds to transmit a frame

if round trip takes .5 second then we can only send 10000 bits every (0.15 + .5) seconds

therefore we are only using < 1/3 of the available bandwidth

solutions

use larger frames, problem error rates likely to increase with larger frames

use pipelining and piggy backs

PiggybackingAcknowledgments

Previously we have looked at simplex protocols - stop-and-wait

Assumption:

  • That links carry traffic in both directions simultaneously (Duplex)
  • If we add an acknowledgment field to the frame header we can reduce the number of ACK frames coming back
  • This is know as piggybacking

Advantages:

1.No need for a separate ACK frames. We attach the ACK information to regular data frames, saving bandwidth.

2.Receiver processes only one half as many frames as before, reducing the interrupt load on the machine.

However:

  • What happens if there are no data frames to send? That is, there are no data frames to piggyback ACK information.
  • Solution: set a timer, and if the timer expires before a data frame is sent, send the ACK in its own frame.
  • The sender's retransmit timer must take into consideration the possibility of delayed ACKS.

Pipelining

Stop-and-wait protocols have the advantage of simplicity

BUT They make inefficient use of bandwidth.

Why: The line is not busy whilst waiting for ACKs

Alternative : Pipelining

Basically allow the sender to transmit multiple frames before requiring an acknowledgment

This reduces the channel idle time across long delay paths

If you have a transmission return time T and it takes S time to transmit a stream of n frames then if the ACK for frame-0 arrives just before S expires then the sender can continue to transmit frames - receiving the ACKS as they come in

if T = 100 msec and it takes 10 msec to transmit a frame then if 10 frames were sent then the return ACK for frame-0 would arrive at approx 110 msec after the beginning of transmission and then after ACK 1-2-3…. Would arrive at 10 msec intervals

Sliding Windows Protocol

  1. Each frame is given its own sequence number
  1. Re-transmissions will use the sequence number that was originally assigned to the frame.

The sender maintains two variables:

SL = the sequence number of the oldest frame sent, but not ACK'ed (e.g., "left" window edge).

SR = the sequence number of the next new frame to send that has never been sent (e.g., the "right" edge of the window).

"New" frames are those that have never been sent yet, whereas "old" frames are those that have already been transmitted one or more times.

SR - SL= size of the send window.

The receiver maintains two variables:

RL = the lowest numbered frame the receiver is willing to accept (e.g., "left" window edge)

RR = one more than the highest numbered frame the receiver is willing to accept (e.g., the "right" edge of the window).

RR - RL = size of the receive window.

The receiver rejects all incoming frames whose sequence numbers are outside of the receive window.

In general, the size of the receive window is the same as the maximum window size.

However, by varying the size of the receive window, the receiver can provide flow control.

Algorithm (Sender):

1. Transmit all frames in the senders window. That is, transmit those frames having sequence numbers in the range SL seq < SR-,).

  • Once all the frames in the window have been transmitted, no more frames can be sent, and we wait for an acknowledgment. The sender needs a way to block the layer above it from continuing to generate more new packets.

2.Set a timer for each data frame sent. Strictly speaking, a timer for each frame is not needed.

  • However, at least one timer is needed at any time the sender has unacknowledged data in its send window. Timing every frame insures that we retransmit a frame as early as possible after it is lost.

3.Wait for an ACK or a timer event:

ACK:If a new ACK, advance the window, cancelling timers for every packet that was ACKed by the cumulative ACK. Old (duplicate) ACKs can be ignored. As window advances, new frames can be transmitted. Allow layer above to generate new traffic (if previously disabled).

Timeout: Retransmit the lost packet. Which frame? ln general, the frame corresponding to the left edge will be the one needed to be retransmitted. (It was the one transmitted the longest time ago).

a)Cancel all timers. That is, if we need to retransmit one packet, we know that all packets to the right of it will need to be retransmitted also. That is, it will one

round trip time before we can get an ACK for the packet we are retransmitting, and since we are using cumulative ACKS, we won't get ACKs for the packets to the right of the retransmitted one either. Thus, the timers are guaranteed to go off as well. Thus, a better strategy is to simply cancel the other timers, send a single packet, and then wait for its ACK, which will hopefully ACK all the packets to the right of the retransmitted one.

b) Retransmit the packet at the left edge (only), and start a retransmit timer for it.

(c)Wait for ACK, or timeout event.

(d)When an ACK for the retransmitted packet is received, update window, and retransmit all packets have been sent, but for which no ACK has been received. Be sure to start timers for each of these!

Algorithm (Receiver):

1.If received frame is DATA frame lies outside of receive window, discard it, but send ACK for packet immediately to the left of the left window edge. That is, the packet is a duplicate, but the sender does not know that we have it. Thus, we must send back and ACK notifying the sender of which packets we have already received.

2.If DATA frame lies within window:

(a) Examine queue to see whether packet is new or a duplicate.

(b) If new, insert in queue, mark as having been received.

(c) Advance the window if appropriate.

There are three cases.

First, the received packet may be the left window edge, that is, the packet we expected. In this case, the window advances by a single packet, the one just received.

Second, the packet may be the left window edge, but if it is a retransmission, then we may already have received packets to the right of the new packet as wen. In this case, the window advances beyond the new packet, including those to the right of it that were received earlier. In the

third case, the received packet may not be the left window edge, in which case we save the packet, but the window doesn't advance. As the window advances, pass received data to the upper layer.Note that you will need another variable, to keep track of which packets have already been passed up to the application.

(b)Generate an ACK for the frame. By already having advanced the window in the previous step, the ACK we send is simply one less than the current left window edge, RL.

Ideally, sequence numbers increase forever and are never reused. In practice, sequence numbers wrap around back to zero.

When is it safe to reuse sequence numbers?

What is the relationship between the sequence number space and the size of the sender and receiver windows? Assume the use of n-bit sequence numbers: 0 - (2' - 1).

1.SL SR, RL < RR. When SL = SR, sender has no unacknowledged frames.

2. What sequence numbers are potentially active? The sender may send any frames in its send window at any time. Thus, SR - SL sequence numbers are reserved for the sender.

3. Likewise, the receiver may generate ACKs for any frames in its receive window. Thus, RR - RL sequence numbers are reserved for the receiver. In order to uniquely identify all (possible) active frames, (SR - SL) + (RR - RL) 2-.

Go Back N

if the sender's window is N

while the receiver's window is one

the receiver rejects all frames except for the one it expects

frames arrive in order

as the Nth frame is being sent, an ACK arrives, the window advances, and the right edge of the send window becomes N+1

the channel stays busy 100% of the time.

Kermit

Kermit file transfer protocol is basically a "stop & wait" ARQ data link protocol.

Key characteristics:

  • Designed to transfer files of data between dissimilar computers.
  • Operates over the simplest possible physical link: asynchronous and allowing only "printable" ASCII characters, even though the transferred file may contain unprintable data.
  • Connection-oriented with a flexible initial connection protocol which allows new (and improved) versions to interoperate with older, simpler implementations.

Kermit Frame Format

A Kermit packet consists of

several characters:

  • MARK - ASCII <SOH> character, indicates start of packet, and is the only non printable character in a packet, thus allowing unambiguous start of packet indication.
  • LEN - Gives length of packet, expressed in excess-32 notation to force printable characters
  • SEQ - sequence number. Valid sequence numbers extend from 0 to 63, excess-32
  • TYPE - Indicates what sort of packet this is. There are many (> 30) different types, including
  • 'Y'(ACK)
  • 'N'(NAK)
  • 'S'(Send Initiate)
  • 'E' (Fatal Error).
  • DATA - between zero and 91 characters of data. If the data is unprintable, It is encoded as a two character printable sequence.
  • CHECK - A 6 bit, excess-32 simple checksum

Kermit Operation

In Kermit one host is set into the Originator Mode

the other the into the Answer Mode

The user then enters the Connect command

then Receive or Send as required

Ethernet Frame Format

Ethernet is connectionless, so frames are relatively simple:

  • Preamble - 7 bytes of 0101010101... allows the R clock to synchronise with the S clock
  • Start Of Frame - 1 byte, thus: 10101011
  • Source and Destination Address - each 6 bytes (48 bits!)
  • Type field - Indicates which higher-level protocol created this frame. In 802.3 this field gives the length (in bytes) of the data field.
  • Data field - from 46 (preserves CSMA/CD minimum frame size requirement) to 1500 bytes.

High-Level Data Link Control Protocol

HDLC is the all full duplex, synchronous, sliding window protocols

HDLC originated in IBM, from work on SDLC (Synchronous)

  • HDLC has led to
  • ADCCP
  • LAP-B
  • LAP-D
  • LAP-M etc...

Tanenbaum:- “The nice thing about standards is that you have so many to chose from. Furthermore, if you do not like any of them you can just wait for next year’s model”

All of these are bit-oriented and use bit-stuffing for data transparency

HDLC can operate in one of 3 modes:

  • Normal Response Mode (NRM), used in polled multi-drop Installations
  • Asynchronous Response Mode (ARM), also used for polling
  • Asynchronous Balanced Mode (ABM)

HDLCFrames

All HDLC frames contain the following fields:

  • FLAG - discussed earlier, this is the unique bit pattern 01111110. Bit stuffing is used to guarantee uniqueness.
  • Address - This Is used In the "response" modes (NRM, ARM) and always contains the address of the secondary station. Normally 8 bits but can be extended.
  • Control - Indicates types of frame, together with appropriate control information such as sequence numbers. See next slide.
  • Data - (or I, for Information, field) may contain any number (from zero upwards) and sequence of bits: bit stuffing guarantees transparency. Normally a multiple of 8 bits, not including any extra, inserted, 0 bits. This field only contains data in I frames - It is empty for S and U frames.
  • FCS - or Frame Check Sequence is a modified CCITT-16 CRC.

HDLC Control Field

Information Frame:

Seq - The sequence number of this frame, 3 bits

Next - This is a piggybacked acknowledgment. However, instead of ACKing the last frame correctly received, it indicates the frame number of the next frame expected. 3 bits

P/F - Poll/Final bit, used In multi-drop installations

Supervisory Frame:

  • Type - Indicates type of frame

HDLC Frame Types

The four possible Seq-frames are:

  • Type 0: An ACK frame, officially called ReceiverReady.
  • Type 1: A NAK frame, officially called Reject, this frame requests a go-back-N retransmission; the sender is required to re-transmit all frames starting with frame Next
  • Type 2: An ACK, but requests the sender to stop sending. Officially Receive Not Ready. Used for flow control and other purposes.
  • Type 3: Officially Selective Reject, requests retransmission of a specified frame.

Unnumbered Control Frame:

Some typical U-frames Include:

SNRM - Set Normal Response Mode - these set the current mode. Normal was used for master slave comms. Dumb terminals

DISC - DISConnect, to announce that a system is (for example) going down

FRMR - Frame Reject, indicates receipt of a valid, but impossible, frame.

NRM and the P/F bit

In NRM, one station is the primary and one or more others (in a multi-drop configuration) are secondaries.

A primary sets the P (for Poll) bit when it wants (or allows) a secondary station to send. The secondary may then transmit frames until it, in turn sets the F (for Final) bit. The interpretation of whether the bit is P or F depends on whether a primary or a secondary station sets it.

Note that the address field in the frame always contains the address of the secondary station involved in the transfer.

LAP-B

A variation of HDLC, LAP-B (Link Access Protocol B) is used as the data link access protocol for X.25 Public Data Networks such as Australian Telecom's "Austpac"

LAP-B uses HDLC's ABM (Asynchronous Balance) mode, with all frames treated as commands(ie, the P bit is set).

It uses RR and REJ frames for error control and RNR for flow control. SREJ is not used.

LAP-B also supports the U-frame for connection initialisation using extended (7 bit) sequence numbers for long delay or high bit rate links.

LAP-B is also used to carry dataon ISDN B-channels.

LAP-D

This is the HDLC subset specified for the D-channel (used for signalling - call setup and the like) of an ISDN service.

It makes use of the extended address and control fields allowed in HDLC The control field allows 7 bit sequence numbers to be used, as well as a subset of the HDLC supervisory (RR, RNR and REJ only) and several unnumbered frame types. It also defines a new, connectionless, I-frame type