Table of Contents
Section 3: The Data Link Layer
The Data Link Layer
Problems with the Physical Layer
Functions of the Data Link Layer
Framing
One way to overcome this problem is to break the bit stream into discrete frames
On receipt of the frame the recipient recalculates the checksum and compares it to the one received
Framing methods
Character counting
An obvious problem with this method is that if, during transmission, the character count field gets corrupted the receiver will lose track of the correct frame boundaries at which point it becomes difficult to resynchronise
Delimiting characters
Character stuffing
This technique is known as character stuffing and is demonstrated below
Delimiting flags
Bit stuffing
Invalid code delimiters
Therefore,
Error Detection and Correction
There are two approaches to solving this problem
Parity Bits
Improving parity bits
Example
Note that using this technique we can detect a burst error of up to n-bits
The cyclic redundancy check
To start we note that any bit string containing k bits can be used to represent a polynomial of degree k-1 with coefficients of 0 and 1
Secondly we remember that polynomial arithmetic is done modulo 2
Detecting errors
The following algorithm may be used for computing the checksum:
In the words of Tanenbaum, in any division problem, if you diminish the dividend(i.e. xrM(x)) by the remainder(i.e. r), what is left over(i.e. T(x)) is divisible by the divisor(i.e. G(x))
Example
To complete step 2 we must divide xrM(x) by G(x) in order to calculate the remainder
Thirdly, we subtract this remainder from xrM(x) using subtraction modulo-2 as follows
Generator Polynomials
For example, the two 16 bit checksums catch all single and double errors, all errors with an odd number of bits, all burst errors or length 16 or less, 99.997% of 17-bit error bursts, and 99.998% of 18-bit and longer bursts
Flow Control
Packet Structure
The trailer stores the checksum which is computed over the entire frame
Protocol 1:Utopia
Protocol 2:Stop-and-Wait
Hence each time B sends a frame to A it must stop-and-wait for an acknowledgement before sending another frame
Protocol 3: PAR
Problem 1
Adding a sequence number
Problem 2
The problem arises if this next frame is lost.
The solution to this problem is to allow B to place the sequence number it is acknowledging in the acknowledgement frame
Protocol 4
Piggybacking
But what happens if the assumption that hosts always have data to send, is dropped
Pipelining
PPT Slide
It can be seen from the above that sender is active for 20 of the total 520 msecs of communication time i.e. it is idle for 96% of time
Sliding Window Protocols
Prior to dispatching a new frame the upper edge of the sender’s window is advanced by one and the frame is given the new highest sequence number
When a frame corresponding to the lower edge arrives, both edges are advanced by one. Frames outside the window are discarded. Frames inside the window but higher than the lower edge are buffered until all lower frames arrives
PPT Slide
Handling Errors
Go Back N
Go Back N
PPT Slide
Selective Repeat Protocols
PPT Slide
Maximum window size
Solution
Buffers and timers
NAK Frames
High Level Data Link Protocol (HDLC)
X.25 Networks
Origins of HDLC
Bit oriented protocols
Frame structure
Frame Types
Information frames
Since HDLC is used a lot in master-slave scenarios the P/F, or Poll/Final, bit is used to co-ordinate communication
Supervisory frames
Receive ready frames are acknowledgement frames where the next field holds the next frame expected
Unnumbered frames
Modes of Operation
Conclusion
|
Author: John B. Mc Donald.
Email: johnmcd@cs.may.ie
Home Page: http://www.cs.may.ie/~johnmcd
|