Chapter Seven

Data Link Layer


This chapter is about various protocols being used in data link layer which is the second lowest layer in ISO/OSI reference model. The protocols are generally classified into byte oriented and bit oriented protocols. The former protocol is the oldest technology and has been widely proved to be a reliable protocol for low speed low volume data transfer while the latter protocol is more efficient in data processing. Error detection and correction is done in this layer by re-transmitting the error frame. Upon completion of this chapter, you should:

Understand the functions of data link layer

Identify the structure of Bisync frame or block

Understand high level Data Link Control Procedures


Data Link Layer

This is the second layer principally responsible for sending and receiving the data in an error-free environment. In addition, it also maintains the data flow gracefully and is able to correct the sequence of transmission in case a distorted frame is detected. The functions provided are summarized as follows:

Frame Flow control, To prevent the sender from sending too fast. For example, RNR in SDLC will be sent by the receiver if the receiver hasn’t finished processing the previously received frames. It is required due to speed mismatch between two communicating parties as shown in Figure .


One party may be temporarily incapable of handling the current traffic load. For instance, due to temporary hardware problem, buffer space depletion, sudden processor load demanded by other functions.

Error Control and Detection, To maintain the frames being transmitted/received are in sequence and to make sure the frames haven’t been distorted due to transmission error.
Link awareness, To monitor the link conditions and ensure the other end is still alive. For IBM machines operating as a secondary station, a 32 second time-out event will be forwarded to upper levels in case there is no activity in the link either due to the line or equipment failure. As a primary station, it will repetitively poll the secondary stations for a certain configured time-out period.

The data link peer parties may reside in a host-node configuration, or a node-node configuration as shown in Figure . The host-node refers to the interface between the Data Terminating Equipment and the network boundary(DCE in this diagram). The frame size between host-node and node-to-node may be varied, as a result, the frames may be fragmented (break into a few smaller frames) and reassembled (combine a few smaller frames into a larger frame) while traversing along a pre-determined transmission path.

Explain why data link layer is concerned about frames between two adjacent nodes.


It is error-free data transmission between two machines.

The block diagram indicating the relationship between network layer and physical layer is shown in Figure .



Additional frame header embedding the physical address of recipient, one control byte, and frame delimiter are added to the Level two frame. The transmission is carried out by the physical layer using synchronous/asynchronous data transmission. A transmission flag is added to the frame by physical layer as well.

Hundreds of different link protocols are used by data communications in industry. A few examples are given below:

High Level data Link Control (HDLC: ISO). It is also the superset of SDLC, LAP and LAPB. That is to say, HDLC covers SDLC (used by IBM), LAP and LAPB (used by X.25) Fax transmission uses the modified HDLC which is more complex.
Synchronous Data Link Control (SDLC: IBM) It is the proprietary product of IBM System Network Architecture (SNA)
Advanced Data Communication Control Procedure (ADCCP: ANSI)
Link Access Protocol (LAP: CCITT)
Hewlett Packard Data Link Control (HPDLC: HP)


X.25 uses LAP or LAPB as the data link layer.

Layer 2 frame

Protocol Data Unit (PDU) for data link layer is often called a frame with frame structure as given below:

Header

Data Field..............

Trailer

The data field is used to carry layer 3 PDU, while the header (also called) PCI in OSI model) contains control information. E.g. Sequence No.,frame type, acknowledgment, etc.). Layer 2 passes the entire frame to layer 1 for transmission.



The internal structure of the frame should be mechanical to the peer layer-2’s only.

Layer 1 accepts a layer 2 frame as a block of data to be embedded in layer 1 frame for transmission. Moreover, its internal structure is of no concern.

Can you Figure out how many bytes are required for the header and trailer? Also find out the improvement in utilization if they are not added.


Three bytes including transmission flag, physical address of recipient and control byte for header.


Error Detection and Control

The function of data link layer is to provide an error free transmission environment. The cause of noise and remedial methods are firstly discussed. The noisy signals which causes the data lost or corruption are classified into three types:

Sources of error

This section discusses where the error comes from. Error is mainly caused by random signal that is unpredictable. Here, random signal refers to the noise.

White Noise

It is present in all electronic devices and cannot be eliminated by any circuits. It increases with temperature, but is independent of frequency. That means the white noise covers the whole frequency spectrum and will be picked up by both low or high frequency devices.

Interference

It is caused by picking up the unwanted electromagnetic signals nearby such as crosstalk due to adjacent cables transmitting electronic signals or lightning causing power surge.

Crosstalk can be reduced by twisting the telephone wires. This will cancel the effect of interference.

Human error

Noise sometimes is caused by human being such as plugging or unplugging the signal cables, or power on/off the related communications equipment.

Other Errors

Other errors that are less relevant are:

intermodulation noise (spceial type of cross talk),
echoes (when signals are reflected)
attenuation (loss of signal power), attenuation distortion refers to high frequencies losing power faser than low frequencies
delay distortion caused by signal travelling at different speeds thru the media.jitter caused by frequent gain and phase cahnges of analog carrier signals(eg.volume fluctuation in a phone line).
Harmonic distortions(out of phase) and line outages.

It will produce random electromagnetic wave which will be picked up by computer. Proper earthing is therefore vital to the reliability of computer systems.

Figure shows the effect of corrupting the data by the presence of noise. The binary data being transmitted will be incorrectly altered by the noise. That is why the protocols available in data link layer must be capable to detect the correctness of received data. The factors to measure how effective the protocols to detect the transmission error include the percentage of detecting an error (single bit, double bit or triple bit errors), and undetected error. BER (bit error rate = Incorrect Data/Total transmitted Data ) is a measurement of how well the medium transmission quality. The typical values are 10-4 for telephone line and 10-10 for optical fiber.  

The prevention methods are: Shielding, Moving cables, Changing multiplexing techniques, Improving connection quality with better equipment, Amplifies and repeaters, Equalization takes of attenuation and delay distortion, Condition by using expensive error free circuits.

Error Detection

A few codes or bits in association with the data are appended to the frame so that the receiver can detect the presence of error by using a simple algorithm.

Vertical Redundancy Check

A single bit either ‘1’ or ‘0’ is appended to the end of each character to produce an odd or even number of ‘1’ bits. This method is commonly used in start/stop transmission (Asynchronous) as shown in Figure .

Type

Description

Even Parity

The total number of binary ‘1’ bits for a particular character is even. For example

Odd Parity

The total number of binary ‘1’ bits for a particular character is odd. For example

An ASC character transmitting at asynchronous mode will have:


 1 start bit + 7 data bits + 1 parity bit + 1 or 2 stop bits = 10 bits, not just 8 bits

The advantages and disadvantages are:

Advantages

Disadvantages

Can you explain why overhead is 10%?


Parity Bit/Total Bits


Longitudinal Redundancy Check

This method is better than a simple Vertical Redundancy Check. The data is grouped into blocks of characters, say for example 12 bytes from the Hong Kong Stock Exchange, each of the character has a parity bit added. A block check character (BCC) is then appended to the end of each transmission block. The size of BCC can be 8, 12 or 16 bits depending on the algorithm.

The parity bits at the end of each character are known as Vertical Redundancy Check (VRC) while the BCC is called the Block Check Character (BCC).

The advantage and disadvantage is:

Advantage

Disadvantage

Improved error detection capability

More overhead is required in coding/decoding and transmission of LRC

Both parity and two-coordinate parity checking are commonly used in low speed communication.

Bits in characters

1

2

3

...

n

LRC


Cyclic Redundancy Check

This is a faster method and is commonly used in protocol operating at synchronous mode such as SDLC. In this method, the data to be sent is divided by a set of binary constant called the generator polynomial. The remainder after division called Frame Check Sequence (FCS) will be appended to the original data stream. The original data plus the frame check sequence will be transmitted over the transmission media. At the receiving end, the received data will be verified by using the same generator polynomial to determine whether the message received is error-free. CRC can be implemented by means of hardware such as Synchronous Communication Chip (SCC) chip which provides the necessary circuit in physical layer to detect the transmission error.

The generator polynomial defined by CCITT for use on the switched telephone is:


X16 + X12 + X5 + X0



The equivalent binary expression is 10001000000100001

Another commonly used code is the CRC-16:


X16 + X12 + X2 + X0

Write down the binary expression.

These 16 bit codes can detect the following errors:

All single bit errors
All two bit errors
All errors with an odd number of error bits
All burst error of length 16 bits or less
99.97% of 17 bit errors

Error is measured in terms of Bit Error Rate. Typical value for switched line is 10-5.

What is the FCS if the frame transmitted in decimal is 728 and the generator polynomial is 13? Assume two digits are used for error checking.


Byte and Bit protocols

The data link layer protocols based on the frame structure (whether frames are constructed out of bits or characters) can be classified into:

Byte oriented such as IBM BSC
Bit oriented such as HDLC (High level Data Link Procedure) or SDLC

The control information in a frame does not need to be continuous. Typically, the delimiter field and the error checking field are separated from other control fields.

Can you list the dummy character used by SNA/SDLC, when there is no data being transmitted?


It will send out a string of flags

The frame format for Byte oriented frame is:

SYN

SYN

DLE

STX

Data

DLE

ETX

BCC

BCC

And the Bit oriented frame:

Flag

Address

Control

Data........

FCS

FCS

Flag

What is the advantage of bit oriented frame compared to byte oriented frame in terms of data position identification?


The protocol can detect the exact location of control and data filed without processing the individual characters.


Byte-oriented Protocols

This type of protocols was developed a long time ago. A well known example is the IBM BISYNC protocol used in Remote Job Entry (RJE). The computer has to stripe down the character by character within the frame in order to determine the meaning and action of received data.

The Byte oriented protocols such as BISYNC have the following characteristics:

Half duplex in Data Link Level ( can have FDX or HDX in physical level.)
Data link Level (not in physical level)
An industry standard
Used in Synchronous modem (Some users may use Sync/Async protocol converter to fit into his own system such as Reuters.)
Uses either ASCII or EBCDIC as the code sets
Ideal for Low speed and High volume transaction
Uses VRC, CRC or LRC to determine transmission error

BISYNC is widely used in:

Remote Batch
Interactive terminals
CPU to CPU communications such as Prime to IBM. (Getting unpopular)


A typical BSC format delineated by a pair of PADs is:

PAD

SYNC

SYNC

SYNC

SYNC

SOH

HEADER  

STX

TEXT

ETB

BCC

BCC

PAD


Type

Description

PAD

Used to indicate the block start

SYNC

Used to synchronize the receiver

STX

Used to indicate the Start of Text

ETX

Used to indicate the end of text

SOH

Used to indicate the start of header

BCC

Block Check Character for error checking

ETB

Used to indicate the end of message block

ACK

Positive acknowledgment

NAK

Negative acknowledgment

WACK

Wait for acknowledgment

ENQ

Enquiry message

TTD

Temporary Text delay

Byte stuffing

Since BISYNC uses a lot of binary characters (STX, SYNC) for control purpose, a pair of special characters DLE is used to quote the binary data so that the receiver will transparently treat the bracket data. Use of DLE to quote data is called byte stuffing as given below:

STX

TEXT

EXT

TEXT

ETB

TEXT

ETX

BCC

BCC

DLE

STX

TEXT

ETX

TEXT

DLE

ITB


BSC Line States

There are FOUR line states that BSC will be used to transfer data. Initially, BSC will be in disconnected state until it receives an event, it will then change to other state and take appropriate action.

Type

Description

Disconnected

No virtual connection has been established

Connected

A virtual connection has been established. The line can then move to Text or Control state.

Control

Can exchange control information such as ENQ or ACK0 etc.

Text

Data frame is exchanged.

Data Flow

The principal means of flow control is to lay down rules to control if a sender can transmit a frame. For simplicity, both send and receive party can be considered to consist of a sender and a receiver as shown in Figure

BSC uses simple stop-and-wait protocol. The sender, after sending a frame, will stop and wait for an acknowledgment frame (from the receiver of the peer party) before sending another frame. The data link layer frames of such a protocol may consist of an information and acknowledge frame as shown in Figure .


The general frame flow diagram is given in Figure

Normal BSC Data Flow (BSC Contention)

Figure shows the normal data flow with acknowledgment frame. The transmitter initially transmits an ENQ and waits for an ACK0 prior to sending the test frame.



The receiver uses ACK0 and ACK1 alternatively to inform the transmitter that the messages are received correctly. Can you explain the reason behind?


Line Bid Time outs (BSC Contention)

After polling the remote for eight times, the sender may assume that the remote machine is dead (usually power off) and will stop polling. These retried time-outs can be configured by the user. Figure uses the two seconds as the time-out value.


Error Control - NAK (BSC Contention)

As shown in Figure , a NAK (negative acknowledgment) will be sent back to the transmitter, if the received data has detected a transmission error by checking the received frame against the Block Check Character (BCC).


Error Control - Lost Acknowledgment (BSC Contention)

If the transmitter cannot receive the acknowledgment from the receiver, it will send an ENQ instead of data frame and waits for the positive acknowledgment from the receiver as shown in Figure . Note that there is a 3-second delay for replying an ENQ.

Error Control - Lost Message (BSC Contention)

Similar to Figure , the transmitter will send an ENQ instead. However, the receiver will send an ACK0 instead of ACK1 after receiving the second ENQ.

Can you draw a distinction between Figure and ?


WAIT FOR ACK - WACK (BSC Contention)

If the receiver is busy, it will respond an WACK to temporarily stop the sender until the busy condition is removed. Once the condition is over, it will send an ACK0 to inform the sender to re-send data frame.

Temporary Text Delay - TTD (BSC Contention)

In this case, the sender is busy, it delays for 2 seconds and sends an TTD to inform the receiver to suspend the transmission as shown in Figure . The use of TTD is to maintain the communication link between the sender and receiver.


Duplicated frames

 Duplicated frames occur for various reasons such as lost of acknowledgment. Figure shows the duplication of data frame due to lost frame and Figure shows the condition when the receiver is too late to acknowledge the frame.

Duplicated frames can be handled by the use of sequence numbe, can you explain why it can fix this number?



The user can check the correct sequence and remove duplicated frames by just looking at the sequence number.


Bit-oriented Protocols

These protocols interpret the message as a stream of unstructured bits and uses the relative bit position to determine the control information. This mechanism is more efficient compared to byte-oriented protocols and is extremely suitable for simultaneous communications protocols such as HDLC and SDLC. The entire message is delineated by a Flag whereas the BSC has to use numerous control fields such as SYNC, STX etc.

A typical bit oriented frame (HDLC) is given below:

Type

Description

Flag

This is the delimiter used to identify the start and end of variable-length frame. An example is 7EH in HDLC.

Address

This is the destination address associated with the communications device in the network. This address is also called physical address.

Control

 Contains the type of information about the message itself. Control byte can be used to classify Supervisory, Unnumbered and Information frames.

Data

Data portion of message. Data field is only available for information frame and is regarded as packet without frame header and trailer.

FCS

Frame check sequence using CRC-CCITT or CRC-16 to ensure transmission error free.

Control field format

There are three different formats for this fields, with a few bits assigned to identify which format is being sent. Figure shows various control formats.

The three formats are:

Type

Description

Information format (I)

 including a send sequence, a receive sequence and an information field.

Supervisory format

including a receive sequence and two bits to indicate different supervisory format such as RR, RNR and REJ etc.

Non sequence format

Having no sequence count and is used for setting operating mode. For example, the UA (unnumbered frame acknowledgment)

 


Bit stuffing

Bit-oriented protocols use a unique sequence of bits such as 7EH for the start and end of frame. To avoid an occurrence of this flag bit pattern (01111110) anywhere, the sending station will automatically insert an extra zero into the five contiguous ‘1’ bit stream. The receiving station will monitor the bit stream and delete the extra zero.

0111 1110

address

Control

Data 0111 1110

FCS

FCS

0111 1110

Try to insert a zero bit for Five consecutive 1, as shown below:

0111 1110

address

control

data 011111010

FCS

FCS

0111 1110


Primary & Secondary Stations

There are two types of stations defined in these protocols:

Primary Stations
It is responsible for controlling data link by issuing commands such as Receive Ready.
Secondary
It receives commands from the primary and return responses.


In IBM SNA/SDLC, if the receiver does not receive any message for longer than 32 seconds, it will assume that the primary is not functioning and subsequently disable the line.

Figure shows the three operation modes. Here, Normal response mode support one primary and a few secondary stations, whereas asynchronous response mode and asynchronous balanced mode support only one primary and one secondary.


HDLC

The High-level data link control protocol (HDLC) is a full-duplex bit-oriented protocol. This protocol has a few configurations as given in Figure .

Type

Description

Normal Response mode

Used in multipoint environment with Master/Slave relationship. The master is responsible for polling the slaves by periodically sending a special poll frame. In IBM SNA/SDLC, the polled frame is SNRM (Set Normal Response Mode).

Asynchronous Balance Mode

Used in point to point link where the stations behave as peers. This mode is used by X.25 to establish connection.


HDLC CONTROL FRAME FORMATS

Below shows the comparison amongst all data link layers.

Name

LAP

LAP-B  

HDLC

SDLC

Information

I

I

I

I

Receive Not Ready

RNR

RNR

RNR

RNR

Receive Ready

RR

RR

RR

RR

Reject

REJ

REJ

REJ

REJ

Selective Reject

   

SREJ

 

Set Normal Response Mode

   

SNRM

SNRM

Set Asynchronous Response Mode

SARM

 

SARM

 

Set Asynchronous Balanced Mode

 

SABM

SABM

 

Sey Initialization Mode

   

SIN

SIN

Disconnect

DISC

DISC

DISC

DISC

Unnumbered Information

   

UI

UI

Unnumbered Poll

   

UP

UP

Reset

   

RESET

 

Exchange Identification

   

XID

XID

Unnumbered Acknowledgment

UA

UA

UA

UA

Disconnect Mode

 

DM

DM

DM

Request Initialization Mode

   

RIM

RIM

Frame Reject

 

FRMR

FRMR

FRMR

Request Disconnect

   

RD

RD

Command Reject

CMDR

     

Test

     

Test

Beacon

     

BCN

Configure

     

CFGR



Based on above table, HDLC is a full specification comprising LAP, LAPB and SDLC.


Flow Control

There are two methods namely rate control and sliding window to regulate the flow of frames. Sliding window uses the size of sending window to restrict the number of frames being sent out.

Link Initialization & Disconnection
Sliding Window (The normal value is 7 for 3-bit control field). It consists of
Sending Window
Receiving Window
Error Handling (about the receipt of corrupted message(s))
Go Back N, ask the sender to repeat the whole sequence starting from the first rejected message. (Some frames had been receivd by the receiver. As a result, it is less efficient.)
Selective repeat, just to ask the sender to send the message(S) that was/were rejected by use of SREJ message. (It is more efficient. However, it needs buffer to store the previously received frames.)

Explain why selective reject is more efficient in full duplex data link and is the same in half duplex data link. The physical layer for both cases are full duplex in nature. That is to say, no need to check the voltage status of CTS.

UA is sent by the receiver to acknowledge the numbered frame during link initialization and termination.

Write down the full name of UA.


Link Initialization

Figure shows the methods of establishing a call under three response modes. UA frame is used to respond to all three cases.

Link Disconnection

Figure shows the methods of terminating a call under three response modes.

Explain why computer B will respond a DISC to machine A instead of UA for Asynchronous Response Mode.


Sliding Window Example

Figure shows two examples of using sliding send windows to control the number of frames to be delivered. In case 1, the transmitter can send out a series of frame numbered from 0 to 6 and in case, it sends out from 0 to 4.

Explain why it cannot send out the frames from 0 to 7.

No acknowledge will be used by the receiver to identify the number of frames received.

Data Flow

Figure shows the data flow by use of Information or Supervisory (Receive Ready) frames to acknowledge the sender. The use of information frames can speed up the response.


Error Handling

In case there is a transmission error, the receiver simply responds a Reject frame against the corrupted frame or a Receive Ready starting from the corrupted frame to the sender to re-send the whole frames.

In case various errors as listed below are not caused by transmission, the receiver will send a FRMR to the transmitter to reset the communication link. Software error could be one of the following:

Bad Address field
Fewer than 32 bits between flags
Information field is not a multiple of 8 bits

Receiver does nothing upon receipt of an invalid frame. It simply reports this event to higher layer and waits for a link re-initialization.

Explain why transmission error is not regarded as a serious error.

Go Back N, Error Handling

An REJ signal is sent to A for an invalid frame of sequence 5. Note that A has to re-send the data frame starting from sequence 5.


Selective Repeat, Error Handling

An SREJ frame is sent from B to A for an invalid frame of sequence 4 as shown in Figure
$[F#,dc5-22]. Here, the transmitter can immediately send out the error frame without waiting for the last frame. This saves a lot of time to perform retransmission. Note that A only re-sends the corrupted frame of sequence 4. The performance is far better than the case in Figure .


Self-examined Questions

HDLC

List the FOUR types of supervisory frames.

 
 
List the THREE modes defined by HDLC.

 
 
What is the function of the P-bit?

 
 
When is a FRMR sent instead of a REJ?

 
 
What is a problem of having a large window size?

 
 
What is the function of a sending window?

 
 

BSC

How are frames delineated in BSC? (What character, PAD, STX, ETX...)

 
 
How to fix the problem of duplicated frames?

 
 
What is the function of the EOT character?

 
 

True or False

UA is sent in response to SNRM.

RNR is used to respond to RR.

Information frame must be responded by Information frame .

REJ is sent against all the invalid frames for physical layer operating at half duplex mode.