Bit-Oriented Protocols

• In character-oriented protocols, bits are grouped into predefined patterns forming characters
• By comparison, bit-oriented protocols can pack more information into shorter frames

A lot of bit-oriented protocols have been developed over the years:

• One of these HDLC is the design of the ISO and has become the basis for all bitoriented protocols in use today
  • In 1975, IBM gave Synchronous Data Link Control (SDLC)
  • In 1979, ISO answered with High Level Data Link Control (HDLC)
• Since 1981, ITU-T has developed a series of protocols called Link Access Protocols
• LAPs: LAPB, LAPD, LAPM, LAPZ etc. all based on HDLC

HDLC is basis for all protocols, so we will study it in detail:

High Level Data Link Control (HDLC)

• Bit-oriented data link protocol designed for:
  • Full Duplex and Half Duplex
  • Point-to-point And Multipoint Links

Characterization of HDLC

HDLC can be characterized by:

• Station Types
• Configurations
• Response Modes

STATION TYPES(1)

HDLC differentiates b/w 3 types of stations:

• Primary Station
• Secondary Station
• Combined Station

STATION TYPES (2)

Primary Station

• Primary station works in the same way as primary devices in the discussion of flow control
• The primary is a device in point-to-point or multipoint line configuration that has complete control of the link

STATION TYPES (3)

Secondary Station

• The primary sends commands to the secondary stations
• A primary issues commands and a secondary issues responses

STATION TYPES (4)

Combined Station

• A combined station can both command and respond
• A combined station is one of a set of connected peer devices programmed to behave either as a prim
  ary or as a secondary depending on the nature and the direction of the transmission

Configuration (1)

• Configuration refers to the relationship of the hardware devices on a link
• Primary , secondary and combined stations can be configured in three ways:
  • Unbalanced Configuration
  • Symmetrical Configuration
  • Balanced Configuration

Configuration (2)

Unbalanced Configuration

• Also called Master/Slave Configuration
• One device is a primary and others are secondary
• Unbalanced configuration can be point to point if only two devices are involved
• Most of the times it is multipoint with one primary controlling several secondaries

Configuration (3)

Symmetrical Configuration

• Each physical station on a link consists of two logical stations, one a primary and the other a secondary
• Separate lines link the primary aspect of one physical station to the secondary aspect of another physical station

Configuration (4)

Balanced Configuration

• Both stations in a point-to-point topology are of combined type
• HDLC does not support balanced multipoint

Station Types & Configurations

Modes

• A mode in HDLC is the relationship b/w two devices involved in an exchange
• The mode describes who controls the link
• HDLC supports 3 modes of communication b/w stations:
  • Normal Response Mode (NRM)
  • Asynchronous Response Mode (ARM)
  • Asynchronous Balanced Mode (ABM)

Normal Response Mode (NRM)

• Refers to the standard primary-secondary relationship
• Secondary device must have permission from primary device before transmitting
• Once permission has been granted, the secondary may initiate a response transmission of one or more frames containing data

Asynchronous Response Mode (ARM)

• A secondary may initiate a TX w/o permission from the primary whenever the channel is idle
• ARM does not alter the primary secondary relationship in any other way
• All transmissions from the primary still go to the secondary and are then relayed to the other devices

Asynchronous Balanced Mode (ABM)

• All stations are equal and therefore only combined stations connected in point-topoint are used
• Either combined station may initiate TX with the other combined station w/o permission

HDLC Frames

HDLC defines 3 types of Frames:

• Information Frames (I-Frames)
• Supervisory Frames (S-Frames)
• Unnumbered Frames(U-Frames)

I-Frames are used to transport user data and control information relating to user data
S-Frames are used only to transport control information
U-Frame are reserved for System Management
Each frame in HDLC may contain up to six fields

• A beginning Flag Field
• An address field
• A control field
• An information Field
• A frame check sequence (FCS)
• An ending Flag Field

Flag Field

• •The flag field of an HDLC frame is an 8-bit sequence with a bit patter 01111110 that identifies both the beginning and the ending of the of a frame
• It serves as a Synchronization pattern for the receiver
• Fig. shows placement of 2 flag fields in an I-Frame

HDLC Address Field

• The second field of HDLC frame contains the address of the secondary station that is either the originator or the destination of the frame
• If a primary station creates Frame it includes a ‘To’ address and if a secondary creates the frame, it contains a ‘From’ address
• Can be of one byte or several bytes depending upon the network
• If the address field is only 1 byte, the last bit is always a 1
• If the address is of several bytes, all bytes but the last one will end with 0 , and the last will end with a 1
• Ending each intermediate byte with 0 indicates to the receiver that there are more address bytes to come

HDLC Control Field

• The control field is a one o two byte segment of the frame used for flow management
• The two byte case is called the Extended Mode

Control fields differ depending on the frame type:

• If the control field is a 0, the frame is an I-Frame
• If the first bit is 1 and the second bit is a 0 , it is S-Frame
• If both first and second bits are 1’s, it is U-Frame

• P/F bit is a single bit with dual purpose
• It has meaning only when it is ‘1’ and it can mean Poll or Final
• When the frame is sent by a primary to secondary, it means POLL
• When the frame is sent by a secondary to a primary, it is FINAL

HDLC Control Field –EXTENDED

• Control field in the I-Frame and S-Frame is two bytes long to allow seven bits of sending and receiving sequence
• However the control field in the U-Frame is still one byte

• Information field contains the user’s data in an I-Frame and Network Management information in a U-Frame
• An S-Frame has no information field
• Its length can vary from one network to another but remains fixed within each network
• It is possible to send Control information in the information field of the I-Frame along with data.
• This process is called Piggybacking

• The FCS is HDLC’s error detection field
• It can contain a two- or four byte CRC

Link Access Procedures

• LAPB
  • Link access procedure, balanced
• LAPD
  • Link access procedure for D- channel
• LAPM
  • Link access procedure for modems

Summary

• Synchronous Protocols
  • Bit-Oriented Protocols
• HDLC
  • Link Access Protocols (LAPs)

Reading Sections

Section11.4, 11.5
“Data Communications and Networking” 4th Edition by Behrouz A. Forouzan

YMODEM

YMODEM is similar to X-MODEM with only the following major differences:

• 1024-Byte data unit
• Two CANsto abort Transmission
• ITU-T CRC-16 for Error Checking
• Multiple files can be sent simultaneously

ZMODEM

• Newer Protocol
• Combines features of

XMODEM
and
YMODEM

BLAST

• Blocked Asynchronous Transmission
• More powerful than XMODEM
• Full Duplex
• Sliding Window Flow Control
• Allows transfer of Data and Binary Files

KERMIT

• Designed at Columbia University
• Most Widely used Asynchronous Protocol
• File Transfer protocol is similar in operation to XMODEM, with sender waiting for an NAK before it starts TX
• Kermit allows the transmission of control characters as Text

Synchronous Protocols

Speed of synchronous TX makes it a better choice over Asynchronous T for LAN, MAN and WAN technology

Classes of Synchronous Protocols

Synchronous Protocols can be divided into two main classes:

• Character – Oriented Protocols
• Bit – Oriented Protocols

Character – Oriented Protocols

• Also called Byte- Oriented Protocol
• These protocols interpret a transmission frame or packet as a succession of characters, each usually composed of one byte
• All control information is in the form of an existing character encoding system

Bit – Oriented Protocols

These protocols interpret a transmission frame or packet as a succession of individual bits, made meaningful by their placement in the frame
Control information can be one or multiple bits depending on the information embodied in the pattern

• Character –Oriented Protocols are not as efficient as bit – oriented protocols and are seldom used
• They are easy to comprehend and employ the same logic as bit-oriented protocols
• Their study will provide the basis for studying the other data link layer protocols
• In all data link protocols, control information is inserted in the data frame as separate control frames or as addition to existing data frames
• In character oriented protocols, this info is in the form of code words taken from oexisting character sets such as ASCII
• IBN’s BSC is the best known character oriented protocol

Binary Synchronous Communication (BSC)

• Developed by IBM in 1964
• Usable in both point-to-point and multiple communications
• It supports half-duplex TX using stop-and-wait ARQ flow control
• Does not support full duplex TX or sliding window protocol

BSC FRAMES
BSC protocol divides a transmission into frames

CONTROL FRAMES

• If a frame is used strictly for control purposes, it is called a Control frame
• Control frames are used to exchange information b/w communicating devices for example, to establish the connection, to control the flow, to request error correction etc

DATA FRAMES

• If a frame contains part or all of the message itself, it is called a Data Frame
• Data frames are used to transmit information, but may also contain control information applicable to that information

• Figure shows the format of a simple data frame
• Arrow shows the direct of TX
• The frame begins with two or more synch. (SYN) characters
• These characters alert the receiver to the arrival of a new frame and provide a bit pattern used by the receiving device to synch itself with that of the sending device
• After the two synch characters, comes a start of text (STX) character
• This character signals to the receiver that the control information is ending and the next byte will be data
• Data or text can consist of varying number of characters
• An end of text (ETX) indicates the end of text
• Finally, the Block Check Count (BCC) are included for error correction
• A BCC field can be a one-character LRC or a two –character CRC

Data Frame with Header

• A frame as simple as above is seldom used
• Usually we need to include the address of the receiving device, the address of the sending device and the identity number of the frame (0 or 1) for stop-and-wait ARQ

• All the above information is included in a special field called Header
• Header begins with start of the header (SOH) character
• The header comes after the SYNs and before the STX character
• Everything received after the SOH field but before STX character is the Header information

Mltiblock Frame

• The probability of an error in the block of text increases with the length of the frame
• The more bits in a frame, the more are the chances of an error
• For this reason, text in a message is often divided b/w several blocks
• Each block starts with STX and ends with ITB, intermediate text block except the last one
• Last block ends with ETX character
• After the ETX has been reached, and the last BCC checked, the receiver sends a single ACK for the entire frame
• The figure includes only 2 blocks but actual frames can have more than two
• Some messages may be too long to fit in a frame
• Several frames can carry continuation of a single message
• To let the Rx know that the end of frame is not the end of transmission, the ETX character in all the frames but the last one is replaced by an End of Transmission block (ETB)
• The receiver must acknowledge each frame separately

Control Frames

• A control frame is used by one device to send commands to or to get information from another device
• A control frame contains control characters but no data
• It carries information specific to the functioning of the data link layer itself

Control frames serve 3 purposes:

• Establishing Connections
• Maintaining Flow and Error Control during Data Transmission
• Terminating Connection

Summary

• Data Link Protocols
• Asynchronous Protocols
• Synchronous Protocols

Reading Sections

Section11.1, 11.2
“Data Communications and Networking” 4th Edition by Behrouz A. Forouzan

SLIDING WINDOW ARQ

Among several popular mechanisms for error control two protocols are important:

• Go-back-n ARQ
• Selective Reject ARQ

Three features are added to sliding window flow control to allow for the retransmission of the lost or the damaged frames:

• The sending device keeps copies of the transmitted frames until all of them have been acknowledged
• In addition to ACK frames, receiver also has the option of NAK frames, if data has been received damaged
• Because sliding window is a continuous TX mechanism, both ACK and NAK frames must be numbered for identification
  • ACK frames carry the number of the next frame expected
    • ACK 5 tells sender that all frames up to frame 5 are received
  • NAK frames carry the number of the damaged frame itself
    • If data frames 4 and 5 are damaged, NAK 4 and NAK 5 must be sent
• Like sender in stop-and wait ARQ, the sliding window ARQ is also equipped with a timer in the sender to deal with lost ACKs

Go Back n ARQ

In Go Back n ARQ, if one frame is lost or damaged, all frames sent since last frame acknowledged are retransmitted

Go Back n- Lost Data Frame

• Sliding window requires that data frames be transmitted sequentially
• If one or more frames are so noise corrupted that they become lost in transit, the next frame to arrive at the receiver will be out of sequence

Go Back n- Lost ACK

• When the window capacity is reached and all frames allowed have been sent , the sender starts a Timer
• If an ACK is not received before that Timer expires, sender retransmits all therames since the last ACK

Selective Reject ARQ

• In selective-reject ARQ, only the specific damaged or los frame is retransmitted
• If a frame is corrupted in transit, a NAK is returned and the frame is resent out of sequence
• The Rx device must be able to sort frames and insert the retransmitted frame into the proper place

The selective reject ARQ differs from Go Back n in the following ways:

• The Rx device must contain sorting logic to enable it to reorder frames received out of sequence
• Sending device must contain a searching mechanism that allows it to find and select only the requested frame for retransmission
• Selective Reject ARQ
• A buffer in the receiver must keep all previously received frames on hold until all retransmissions have been stored
• To avoid selectivity, ACK number, like NAK numbers must refer to frame received instead of next expected frame
• A smaller window size is required because of this added complexity

• Selective Reject ARQ-Lost Frame

Lost ACK/NAK are treated exactly in the same way as by Go Back n

Selective Reject ARQ vs Go Back n

• Although retransmitting only specific damaged or lost frames may seems more efficient than resending all the frames
• Because of the complexity of sorting and storage required by the receiver and exa logic needed by sender to select specific frames for retransmission, selective reject ARQ is EXPENSIVE and not often used
• Selective reject gives better performance but in practice it is usually it is discarded in favor ofgo-back-n for simplicity of implementation

Protocols

Protocol: Set of rules or conventions for executing a particular task
Protocol in DataComm.:Set of rules or specifications used to implement one or more layers of the OSI Model
Example: EIA 232-D interface is a protocol used at the physical layer in the OSI Model Protocols
Data Link Protocols: Set of specifications used to implement the data link layer Data link protocols contain rules for:

• Line Discipline
• Flow Control
• Error Control

Categories of Data Link Protocols

Data link protocols can be divided into two sub-groups:

Asynchronous Protocols: Treat each character in a Bit stream independently
Synchronous Protocols: Take the whole bit stream and chop it into characters of equal Size

Asynchronous Protocols

Employed mainly in Modems
Inherent Slowness is a disadvantage: Requires addition of start and stop bits and extended spaces b/w frames, so these are mainly replaced with High-speed synchronous mechanisms

Not Complex and Inexpensive to Implement

Transmission does not require timing coordination; Timing is done by using extra bits

Different Asynchronous Protocols

A variety of Asynchronous protocols have been developed
We will discuss some of the important ones
XMODEM
In 1979 Ward Christiansen designed a File transfer protocol for Telephone-line communication b/w PCs called XMODEM
Half Duplex and Stop-and-Wait ARQ protocol

XMODEM

• The first field is a One Byte start of header (SOH) field
• The second field is a two-byte Header.
  • The first header byte , the Sequence number carries the Frame number
  • The second header byte is used to check the validity of the sequence number
• The fixed data field holds 128 bytes of data
• The last field CRC checks for errors in the data field only

Transmission in XMODEM

• TX begins with sending of a NAK frame from the receiver to the sender
• Each time, the sender sends a frame, it must wait for an ACK before sending next frame
• If NAK is received instead of ACK, the last frame is sent again
• A frame is also resent if no response arrives from a receiver after a fixed time period
• A sender can also receive cancel (CAN) to abort TX

Control Frames in XMODEM

Control frames from the receiver

• ACK: Acknowledgement
• NAK: Error or start of transmission
• CAN: Aborts the transmission

Summary

• Error Control
  • Stop-and-Wait ARQ
  • Sliding Window ARQ
    • Go-back-n
    • Selective Reject
• Data Link Protocols

Reading Sections

Section 10.3,11.1,
“Data Communications and Networking” 4th Edition by Behrouz A. Forouzan

Flow Control- Explanation

• Any receiving device has a limited speed at which it can process incoming data and a limited amount of memory in which to store incoming data
• The receiving device must be able to inform the sending device before those limits are reached and to request that the TX device send fewer frames or stop temporarily

Flow Control-Buffer

• Incoming data must be processed and checked before it can be used
• The rate of such processing is often slower than the rate of TX
• So, each receiving device has a block of memory called BUFFER, reserved for storing incoming data until it is processed
• If the buffer begins to fill up, the receiver must be able to tell the sender to halt the TX until it is once again able to receive

Methods for Flow Control

• Two methods have been developed to control the flow of data across communication links :
  • Stop and Wait
  • Sliding Window

Stop and Wait

In this method, the sender waits for an ACK after every frame it sends

• Only when an ACK has been received, is the next frame sent
• This process of alternately sending and waiting repeats until the sender transmits anEOT frame

Example: Officer giving dictation to the Typist, He says a word, typist says OK, he says the next word, typist says OK and so on

• Advantages of Stop and Wait
  • SIMPLICITY
    • Each frame is checked and acknowledged before the next frame is sent
• Disadvantages of Stop and Wait
  • INEFFICIENT ( Slow)
    • Each frame must travel all the way to the receiver and an ACK must travel all the way back before the next frame can be sent
    • If the distance b/w devices is long, the time spent waiting for ACKs between each frame can be significantly long

Sliding Window

• In this method, sender can transmit several frames before needing an ACK
• Frames can be sent one right after another meaning link can carry several frames at once and its capacity can be used efficiently
• The receiver uses a single ACK to confirm the receipt of multiple data frames
• Sliding Window refers to imaginary boxes at both the sender and the receiver
• This window can hold frames at either end and provides the upper limit on the number of frames that can be sent before requiring an ACK
• Frames may be ACK at any point w/o waiting for the window to fill up and may be TX as long as the window is not yet Full
• To keep track of which frames have been transmitted and which received, sliding window introduces an identification scheme based on the size of the window
• The frames are numbered modulo-n means from 0 to n-1
• If n=8, frames are numbered 0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,0,….
• When the receiver sends the ACK, it includes the number of the next frame it expects to receive

• For example, to ACK the receipt of a string of frames ending in frame 4, the receiver sends an ACK with number 5
• The window can hold n-1 frames at either end, therefore a max of n-1 frames may be sent before an ACK is required

• At the beginning of a TX, sender’s window contains n-1 frames
• As frames are sent out, the left boundary of window moves inward, shrinking the size of the window
• When an ACK is received, the window expands to allow in a number of new frames equal to the number of frames acknowledged by that ACK

• The receiver window therefore does not show the frames that are received but the frames that may still be received before an ACK is sent

ERROR CONTROL

Refers primarily to error detection and correction

AUTOMATIC REPEAT REQUEST (ARQ)

Error control in data link layer is implemented simply:

• Anytime an error is detected in an exchange, a negative acknowledgement (NAK) is returned and the specified frames are retransmitted

Categories of Error Control

Stop and Wait ARQ

• It is a form of stop-and-wait flow control extended to include retransmission of data in case of Lost or Damaged frames
• For retransmission to work, 4 features are added to the basic flow control mechanism
• Sending device keeps a copy of the last frame transmitted until it receives the ACK for that frame
• Both data and ACK frames are numbered 0 and 1 alternately
• A data 0 frame is acknowledged by a ACK 1 frame indicating that the receiver has received data 0 and is now expecting data 1
• Sending device keeps a copy of the last frame transmitted until it receives the ACK for that frame
• Both data and ACK frames are numbered 0 and 1 alternately
  • A data 0 frame is acknowledged by a ACK 1 frame indicating that the receiver has received data 0 and is now expecting data 1
    • If an error is discovered in a data frame an NAK frame is returned NAK frames which are not sent tell the sender to retransmit the last frame
    • The sending device is equipped with Timer. If an expected ACK is not received within an allotted time period, the sender assumes that the last frame sent is lost and resends the frame

Damaged Frame

Lost Frame

Any of the 3 frame types can be lost in transit:

• Lost Data Frame
• Lost ACK Frame
• Lost NAK Frame

Lost ACK, NAK Frame

Summary

• Flow Control
  • Stop-and-Wait-
  • Sliding Window
• Error Control

Reading Sections

Section 10.2, 10.3 “Data Communications and Networking” 4th Edition by Behrouz A. Forouzan

Line Discipline

Enquiry / Acknowledgement (ENQ/ACK)

• Used primarily in systems where there is no question of wrong receiver getting the transmission
• In other words when there is a Dedicated Link b/w the two devices so that the only device that can receive data is the intended one
• Enquiry / Acknowledgement (ENQ/ACK)
• ENQ/ACK coordinates who may start a transmission and whether or not the intended recipi nt is ready and enabled

• Using ENQ/ACK, a session can be initiated by either station on a link as long as both are of equal rank- a printer for example cannot initiate communication with a CPU
• Enquiry / Acknowledgement (ENQ/ACK)
• In both half duplex and full duplex TX, the initiating device establishes the session
• In half-duplex, the initiator then sends its data while the responder waits
• The respondent may take over the link when the initiator is finished or has requested a response
• In full duplex, both the devices can TX simultaneously once the link has be established

How It Works?

• The receiver must answer either with an acknowledgement (ACK) frame if it is ready to receive or with a negative acknowledgement ( NAK), if it is not
• By requiring a response, even if the answer is negative, the initiator knows that his enquiry was in fact received even if the receiver is currently unable to receive
• If neither an ACK or a NAK is received within a specified time limit, the initiator assumes that an ENQ frame was lost in transit, it disconnects and sends a replacement
• An initiating system ordinarily makes 3 such attempts before giving up
• If the response to the ENQ is negative for 3 attempts, the initiator disconnects and begins the process again at another time

If the response is positive the initiator is free to send its data

• The initiator first transmits a frame called an enquiry (ENQ) asking if the receiver is available to receive data
• Once all of its data have been transmitted, the sending system finishes with an End of Transmission (EOT) frame

Poll / Select

Primary-Secondary communication

• This method works with topologies where one device is designed as a Primary station and the other devices are Secondary stations
• Multipoint systems must coordinate several nodes, not just two
• The questions are not only Are you Ready? But also Which of the device has the right to use the channel
• Whenever a multipoint link consists of a primary device and multiple secondarydevices using a single TX line , all exchanges must be made through the primary device even when the ultimate destination is a secondary device
• The primary device controls the link and the secondary device follow sits instruction
• It is up to the primary to determine which device is allowed to use the channel ata given time
• The primary therefore is always the initiator of the a session

• If the primary wants to receive data, it asks the second-arise if they have anything to send, This is called POLLING
• If the primary wants to send data, it tells the target secondary to get ready to receive, This function is called SELECTING

ADDRESSING

• For point-to-point configuration, there is no need for addressing
• Any TX put onto the link by one device can be intended only for the other
• For the primary device in a a multipoint topology to be able to identify and communicate with a specific secondary device, there must be some addressing convention
• For this reason, every device on the link has an address that can be used for identification
• Inny transmission, this address will appear in a specified portion of each frame, called the Address Field or Header depending upon the protocol
• If the TX comes from a secondary device, the address indicates the originator of the data

SELECT

• The select mode is used whenever the primarydevice has something to send
• Primary control the link and if primary is not sending or receiving data, it knows that the link is available
• If it has something to send, it sends it
• As a frame makes its way to the intended device, each of the other devices check the address field
• Only when the device recognizes its own address, does it open the frame and read the data
• In case of a SEL frame, the enclosed data consists of an alert that data is forthcoming
• What it does not know, however is if the target device it ready to receive (ON)
• So the primary must alert the secondary to the upcoming TX and wait for an acknowledgement of the secondary ready status
• Primary send a SEL frame, one field of which includes the address of the intended RX
• If the secondary is awake and running, it returns an ACK frame to the primary
• The primary then sends one or more data frames , each addressed to the intended secondary

POLL

• Used by the primary device to receive transmissions from the secondary devices
• The secondaries are not allowed to TX data until asked
• By keeping control with the primary, the multipoint system guarantees that only one TX can occur at a time
• When the primary is ready to receive, data , it must ask (POLL) each device in turn if it has anything to send
• When the first secondary is approached, it responds either with a NAK frame if it has nothing to send or with data if it does
• If the response is negative, primary then polls the next secondary
• When the primary has received data, it acknowledges by sending an ACK

Two possibilities for termination:

• A secondary sends all its data and finishes with EOT frame
• Primary says “ Time is Up

Flow Control -Definition

• 2nd aspect of data link control is Flow Control
• In most protocols, flow control is a set of procedures that tells the sender how much data it can transmit before it must wait for an ACK from the receiver
• The flow of data must not be allowed to overwhelm the receiver

Summary

• Line Discipline
  • ENQ/ACK
  • POLL/SELECT
• Flow Control
  • Stop-and-Wait
  • Sliding Window

Reading Sections

• Section 10.1,10.2 “Data Communication and Networking” 4th Edition by Behrouz A. orouzan

Error Correction And Detection Method

CHECKSUM

• Error detection method used by the Higher Layers
• Like VRC, LRC, CRC, Checksum is also based on the concept of redundancy

One’s Complement

Finding one’s complement

• Invert every 1 to 0 and 0 to 1
• A and –A are one’s complement of each other
• +A = 1010 → -A = 0101
• +0 = 0000 → -0 = 1111

• Error detection method used by the Higher Layers
• Like VRC, LRC, CRC, Checksum is also based on the concept of redundancy

CHECKSUM Generator

• The sender subdivides data units into equal segments of ‘n’ bits(16 bits)
• These segments are added together using one’s complement
• The total (sum) is then complemented and appended to the end of the original data unit as redundancy bits called CHECKSUM
• The extended data unit is transmitted across the network
• The receiver subdivides data unit as above and adds all segments together and complement the result
• If the intended data unit is intact, total value found by adding the data segments and the checksum field should be zero
• If the result is not zero, the packet contains an error & the receiver rejects it

Checksum Figure

Performanceof Checksum

• Detects all errors involving an odd number of bits
• Detects most errors involving an even number of bits
• One pattern remains elusive

Examples

Example 9.7

checksum

Example 9.8

• Examples of no error and a burst error

• Error is invisible if a bit inversion is balanced by an opposite bit inversion in the corresponding digit of another segment

Segment1 10111101
Segment2 00101001
Checksum 00011001
Sum 11111111

• The error is undetected

ERROR CORRECTION

• Mechanisms that we have studied all detect errors but do not correct them
• Error correction can be done in two ways:
  • Receiver can ask Sender for Re- TX
  • Receiver can use an error-detecting code, which automatically correct certain errors
• Error correcting code are more sophisticated than error detecting codes
• They require more redundancy bits
• The number of bits required to correct multiple –bit or burst error is so high that in most cases it is inefficient
• Error correction is limited to 1, 2 or 3 bit

Single-bit Error Correction

Simplest case of error correction

• Error correction requires more redundancy bits than error detection
• One additional bit can detect single-bit errors
  • Parity bit in VRC
  • One bit for two states: error or no error
• To correct the error, more bits are required
  • Error correction locates the invalid bit or bits
  • 8 states for 7-bit data : no error, error in bit 1, and so on
  • Looks like three bits of redundancy is adequate
  • What if an error occurs in the redundancy bits?

Hamming Code

Redundancy Bits (r)

• r must be able to indicate at least m+r+1 states
• m+r+1 states mus boverable by r bits
• Therefore, 2r ≥ m+r+1
• If m=7, r=4 as 24 ≥ 7+4+1

Hamming Code

• Each r bit is the VRC bit for one combination of data bits
• rit is calculated using all bit positions whose binary representation includesa 1 in the first(second) position, and so on

Summary

• Checksum
• Single-Bit Error Correction
• Haming Code

Reading Sections

• Section 9.6, 9.7, “Data Communications and Networking” 4th Edition by Behrouz A. Forouzan