Data Link Layer

Major functions:

Message interpretation(Framing)

Error Handling

Flow control

Link management

3 possible services provided to upper layer

1. Unacknowledged Connectionless Service

-Called as Datagram service(DG)

-Frames can get lost

-No flow control

-Like regular mail

-Most LAN protocols uses this mode

2. Acknowledged Connectionless Service

-No connection is established prior to data transmission

-A message will be answered by a message(=Acknowledged)

- Return receipt

3. Connection-oriented Service

-Error recovery

-Flow control

-Ensures correct delivery of frames

OSI Service Primitives

Connection-oriented Service mode

DL-CONNECT.request(......)

DL-DISCONNECT.request(......)

DL-DATA.request(.......)

Connectionless Service mode

DL-UNITDATA.request(....)

Framing

-Pre-defined format for frames

-Synchronization for frames---How to start & end(Delimit) a frame

Synchronization methods

1. Asynchronous mode

-Start-Stop--uses START bit and STOP bit to delimit a character

-Called “Character synchronization”

-Inefficient--overhead

-Simple

-Terminals / PC serial ports use this mode

2. Synchronous mode

-Each Frame is synchronized using a kind of delimiters

-Several methods of synchronization

Frame Synchronization Methods

1. Character Stuffing

-IBM Bisynch(BSC-Binary Synchronous Control) Protocol

-Uses few SYN characters to start a frame

-Problem--DATA characters can include the control characters such as ETX

-To avoid the above problem(to achieve data transparency--to be able to send any

characters including control characters, the protocol uses DLE(Data Link Escape)

characters

-Transmitter prefixes DLE in front of any control characters(SYN, STX, ETX, …)

--called Character stuffing

-Receiver removes DLE and accept the next character as a control character

-Example:

-How about a DLE inside data? A DLE DLE will be sent--receiver will delete

a DLE and accept next DLE as a data character

-Inefficient for non-text communication--overhead of DLE characters

2. Character Count

-DEC DDCMP

-Uses Count field instead of DLE's--Count field says how many bytes the frame carries

SYN SYN Count(2 bytes) data characters …….. error detect codes

3. Bit Stuffing

-Uses Flag byte(01111110) to start a frame and to end a frame

-To achieve Data Transparency, stuff 0 after every 5 consecutive 1's

-Receiver will Destuff--throw away any 0 following 5 consecutive 1’s

Example: ISO’s 2^nd layer protocol HDLC

- IBM SDLC (SNA)

- CCITT X.25

-Another example: PPP(Point-to-Point protocol) used in Modem connections

-Address & Control field are not used

-Protocol field carries information about the upper layer protocol--IP, ICMP, ….

4. Physical Code Violations

-Token Ring uses D-Manchester Code Violation to start and end a frame

Both starting delimiter and ending delimiter are identified by means of differential manchester code violations ('JK' code symbols).

Error Control

Main Approaches

1. Echoplex

2. Automatic detection & retransmission

3. Forward Error Correction--use an error-correction code

1. Echoplex

Used in Telnet--When a character is entered in a Telnet session, the character is sent to

the computer and the computer will echo the character--a crude way of check error

2. Automatic detection & retransmission

Use an error detection code to detect error

Error Detection Codes

(a)Parity Code(VRC--Vertical Redundancy Check)

-A Parity bit is used

-Odd or Even parity

-Detects all odd number of error(1 bit error, 3 bit error, …)

-Even number of errors can not be detected

(b) LRC(Longitudinal Redundancy Check)

-Sometimes called “Block Check Code” or “Checksum”

-A block of characters are parity checked

-Often used along with VRC

-It is 2-demensional code

-Divide a block(block size is determined by LAN requirements--Ethernetà

1500Bytes, Token Ringà 8000Bytes, ….) by a predetermined Divisor and

calculate the Remainder and attach the Remainder at the end of data bits

-Receiver will also divide the data bits with the same Divisor and calculates

Remainder and compares the received Remainder with the calculated one

-If they matchà No error detected, If no match à Error detected and the

frame is deleted

The above calculations can easily be done using hardware Shift Registers

--Binary division = a series of Shift followed by adds

Example shift register:

-A carefully designed(chosen) divisor is used

-A divisor is usually represented using a polynomial notation

-There are several standard Divisors that are adopted International standards

-CRC-32 is used in LAN protocols---Ethernet, Token Ring, ….

3. Forward Error Correction--use an error-correction code

-Many FEC’s have been developed

Hamming Code

Convolution Code=Reed-Solomon Code used in CD-ROM

Trellis Code used in V.32 Modems

Example: Hamming code

Single Error Correction Double Error Detection

Hamming designed to have several parity bits in the following position:

2**0, 2**1, 2**2, 2**3 positions will have parity bits

Other bit positions are for data bits

The parity bit at 2**0 position checks positions 1, 3, 5, 7, 9, 11

The parity bit at 2**1 position checks positions 2, 3, 6, 7, 10, 11

The parity bit at 2**0 position checks positions 4, 5, 6, 7

The parity bit at 2**0 position checks positions 8, 9, 10, 11

Let’s use Even Parity for this example:

Let’s say a single-bit error occurs in bit position 7:

The receiver checks parity bits to find the error:

Major Design Aspects

1. Services

2. Framing

3. Synchronization

4. Error Control

5. Flow Control

Flow Control

Sender should not swamp receiver

Typically controlled by the receiver by some kind of permission(Acknowledgement)

Link Management

Properties of link

- Topology

- Duplicity

- Link Control Method

Topology(of connections between computers)

-Star

-Ring

-Bus

-Tree

-Mesh

Duplicity(the mode of interaction between computers)

ANSI US Telecomm. ITU-T

Industry

--------------------------------------------------------

One-way Simplex

--------------------------------------------------------

Two-way HDX Simplex

--------------------------------------------------------

Two-way FDX Duplex

Simul-

taneous

--------------------------------------------------------

Link Control Methods(for Connection-Oriented Services)--A link(the name for OSI second

Layer(DLC--Data Link Control) originates from this) for the connection must be managed

Need to

-initialize

-maintain

-terminate

in an orderly manner

Example:

For connection-oriented

--------Initialize---------------

Connect.request---->

<----Connect.response

--------Maintain---------------

Data.request-------->

<-----Data.response

.........

…….

--------Terminate-------------

Disconnect.request-->

<--Disconnect.response

Example:

For connection-less

--------No Initialization, No Maintainence, No Termination------

Data.request----->

<----Data.request

Data Link Protocol

Let’s design a DLC protocol

--In error-prone line a frame belongs to

-Correct frame--no error detected, deliver it to the upper layer

-Damaged frame--error detected, discard it

-Lost frame--Receiver did not get the frame--synchronization lost

-Undetected error--no error detected but it contains error--deliver it to the upper layer

--For damaged frame & completely lost frame, the connection-oriented protocol must handle

so that we can achieve an “Orderly, error-free communication between peer-to-peer entities”

--Positive Acknowledgement--Receiver returns an Acknowledgement for a frame successfully

received

--Some protocols also employ Negative Acknowledgement

--The protocols(that are designed to achieve all of the above) are collectively called as

ARQ(Automatic Repeat Request)

--3 ARQ versions

-Stop-and-Wait ARQ

-Go-Back-N ARQ

-Selective Repeat ARQ

Stop-and-Wait ARQ

Timeout:length of timeout is a Configuration parameter

If Timeout is

too long, then .….?

too short, then .…?

Utilization of Stop-And-Wait

Time for Info.

U= -------------------

Total time

t_frame

_{= -----------------}

₂_t_prop + t_frame

= -----------------

1 + 2 a

where

Distance / Velocity

a= -------------------

Length / Rate

= (D * R) / (V * L)

Above analysis suggests Long Frames

Problem with long frames ?

----->Leads to "Windowing"

Sliding Window Protocols

Sender's window

=List of Frame Sequence #'s sent and waiting for Ack.(Those frames are buffered)

Receiver's window

=List of Frame Sequence #'s that are ready / permitted to be received(means that the receiver has at least that many buffered readied(committed) for those frames)

- Windowing used in every layer of protocols(when a layer provides Connection-Oriented service, For connectionless services, windowing does not have any meaning)

- Send Seq. #, Rcv Seq. #

( uses n bits )

(3 bits or 7 bits are commonly used number)

-Ack's are piggybacked ( n bits )

Piggybacked Ack.=Sending Ack. on data frame on FDX link

Frame format of HDLC

2 Alternatives in Windowing

1. Go-Back-N ARQ

- Receiver sends Ack for the correctly received frame

- An Acknowledgement field has a meaning of “next expected sequence number”

(Example: Ack 2 means “next expected packet sequence number is 2

and all packets up to 2( 0, 1) are received)

- Sender keeps on sending frames (limited to the Window size) and receiver keeps on

acknowledging.

- When a frame is damaged, receiver sends a Reject control packet(Nak)

- Sender goes back to the Rejected frame and sends all the frames starting with the

rejected one even if those frames are already sent to the receiver

- Sender’s buffer size = Window size

- Receiver’s buffer size = 1

2. Selective-Repeat ARQ

- Same as the Go-Back-N ARQ except when the receiver receives a frame which is

out of sequence, it sends a SREJ(Selective Reject)

- Sender retransmits only the rejected packet and continues with other packets

- More efficient than Go-Back-N

- Sender’s buffer size = Receiver’s buffer size=Window size

- TCP uses a version of Selective-Repeat ARQ--No SREJ used, retransmission occurs

when the timer expires or 2 consecutive Acks for the previous segment are returned

from the receiver

Go-Back-N

- IBM SDLC

- X.25 LAPB

- 802.2(LLC)

- ISO HDLC(an option)

Selective-Repeat

- ISO HDLC(an option)

- ANSI ADCCP

Data Link Control Frame formats: