Transcript the data link layer

THE DATA LINK LAYER
Out of order with the book
Dr. John P. Abraham
University of Texas, Panam
The data link layer


Provides data transport across a
physical link
Handles physical addressing, network
topology, line discipline,Frame
synchronization, error notification,
orderly delivery of frames and flow
control.
Services provided by data link
layer



Unacknowledged connectionless
service
Acknowledged connectionless service
Acknowledged connection-oriented
service
Unacknowledged connectionless service




No connection established.
Send frames. No acknowledgment by
receiving machine.
If lost, no attempt to recover by this
layer. Recovery is left up to the higher
layers
Good for reliable lines such as fiber, use
for speech, video, etc. where late is
worse than lost frames.
Acknowledged connectionless service




No connection established
Frames are sent and each is individually
acknowledged
Frames are resent if acknowledgement
received within timeout period.
Useful for unreliable channels such as
wireless.
Acknowledged connection-oriented
service




Reliable service
Source and destination establish
connection
All frames are received in the right order
After transmission the connection is
releasedaming
Framing

In order to provide service to the
network layer, the data link layer must
use the service provided to it by the
Physical layer. The physical layer only
accept a raw bit stream. For a long bit
stream, if error occurred during
transmission, the entire stream has to
be sent again. Therefore, it is broken to
smaller frames.
Each frame will have to be distinguished
somehow. Three methods are used



Character count
Starting and ending characters, with
character stuffing
Starting and ending flags, with bit stuffing
Character count



The first byte indicates how many characters are in
the frame including the first byte.
Trouble with this scheme is that if the first byte of any
frame gets corrupted, the destination will get out of
sequence, having no way to find where the beginning
of the next frame is.
This method is rarely used any more.
Start and end with control chars with
character stuffing


Resynchronize at the beginning of each frame
Start with ASCII chars DLE & STX
– Data Link Escape, Start of Text


End with the same sequence
If these ASCII char is part of the text then double it
– like Jim’’s book - in pascal

Problem - must use 8 bit ASCII which is not suitable for all communications
Start and end with flags with stuffing




Each frame begins with bit pattern 01111110
If senders data has five consecutive ones then stuff it with a zero which is
deleted at the receiving end
This bit pattern called flag byte is added at the end of each frame as well
With this method boundary between two frames are easily recognized
Error control



How to make sure that all data arrived at the
destination correctly and in the proper order.
The receiver sends special control characters
indicating positive or negative acknowledgement
about incoming frames.
What to do if the acknowledgment gets lost? -the
computer will hang.
– Introduce timers for each frame.
– The time has to be set long enough to send/receive in both
directions
– The time will vary depending upon distance, conditions, etc.
– We will examine this in more detail later.
Elementary data link protocols





Receives packets from network layer
The packet is treated as pure data, even though it may contain data and
control information.
It is the data link’s job to transmit it to the receiver’s data link layer, which in
turn gives it to the network layer.
Data link encapsulates it in a frame by adding data link header and trailer to it.
Appropriate checksums are computed and included in the frame.
Receiving data link layer





computes the checksum
if checksum does not match send error message
If checksum is ok notify sending data link layer
Check all header trailer information
If all OK strip off the header and trailer and pass the packet to the data link
layer
Pseudocode for data link layer routine







Wait for an event to happen
Fetch packet from the network layer for transmission on the channel
Deliver information from inbound frame to network layer
Go get an inbound frame from the physical layer
Pass the frame to physical layer for transmission
Start clocks and stop clocks as necessary
etc, etc
Sliding Window Protocols







For full duplex two transmission lines are required
One to send data and the other to receive data
and/or ACKs
Sending ACKs in a packet of its own is waste of
resources
May use piggybacking
The acknowledgement is attached to an outgoing
data frame(ack field in the frame header)
Data link layer must wait until it has some thing to
send before it can ack.
This may cause time out and the frame may be resent.

The essence of sliding window protocols is that at
any instant of time, the sender maintains a set of
sequence numbers corresponding to frames it is
permitted to send. These frames are said to fall
within the sending window. Similarly, the receiver
also maintains a receiving window corresponding to
the set of frames it is permitted to accept. It is NOT
necessary for the sender and receiver to have same
number limits.

Sequence numbers of frames sent but not
acknowledged are kept in the senders window.
Th receivers window corresponds to the frames it
may accept.

One bit sliding window protocol


uses stop and wait scheme, since the sender
transmits a frame and waits for its acknowledgement
before sending the next one.
The acknowledgement field of the frame contains the
number of the last frame received without error. If
this number agrees with the sequence number of the
frame the sender is trying to send, the sender knows
that it is done and can proceed with the next frame.
A protocol using Go-Back-N



Takes into account of round trip transmission time.
Enough frames should be send to stuff the band with
to avoid channel idling
Consider a 50-kbps satellite channel with 500 m-sec
round-trip propagation delay
– Let us send 1000 bit frames
– At t=0 starts sending the first frame, at t=20 msec the frames has
been send
– Receiver fully receives only at t=270msc, and ack will be received
at t=520 msec.
– Sender would be blocked 96% of time- only 4% of available band
width was used.
Go-Back-N continued.






Instead of sending 4 frames, the sender should have sent
26 frames. This will take t=520 msec.
at t=520 the acknowledgement for the first frame will be
received. The senders maximum window size is 26.
This technique is called pipelining.
If a frame in the middle of a stream gets damaged, what
should the receiver do? Should all frames starting at that
point be re-sent?
Go-Back-N simply discards all frames including the
damaged one, not sending acks. The time out at the sender
will resend all subsequent frames.
Can waste a lot of bandwidth in an unreliable channel.
Selective Repeat



Receiver stores all good frames after the damaged frame.
Notifies the sender of the bad frame, and sender re-sends that one.
This technique requires the data link layer to have large amount of memory
for the cache.
Examples of Data Link Protocols

HDLC - HIGH LEVEL DATA LINK CONTROL
– DERIVED FROM IBM’S SNA - LAYER CALLED SDLC
(SYNCHRONOUS DATA LINK PROTOCOL).
– ANSI MODIFIED IT TWICE FINALLY IT IS NOW HDLC
– CCITT MODIFIED HDLC AS A PART OF X.25 CALLED
LAPB (LINK ACCESS PROCEDURE B)

ALL ARE BIT ORIENTED PROTOCOLS
– FRAME EXAMPLE
– 01111110/ADDRESS/CONTROL/DATA/CHECKSUM/01111110
– CONTROL FIELD IS FOR FRAME SEQUENCE NOS
DATA LINK LAYER IN THE
INTERNET



HOME USER DIALS UP THE INTERNET PROVIDER
THE PC AT HOME FUNCTIONS AS A CHARACTER
ORIENTED TERMINAL LOGGED INTO THE
INTERNET SERVICE PROVIDER’S TIME SHARING
SYSTEM. -This is called a SHELL ACCOUNT. CAN’T
USE WWW.
THE HOME PC CAN CALL THE INTERNET
PROVIDER’S ROUTER AND THEN ACT LIKE A
FULL-BLOWN INTERNET HOST. CAN USE WWW.
TO DO THIS SOME POINT-TO-POINT DATA LINK
PROTOCOL IS REQUIRED.
POINT-TO-POINT DATA LINK
PROTOCOL


FRAMING, ERROR CONTROL AND OTHER DATA
LINK LAYER FUNCTIONS
TWO POINT-TO-POINT PROTOCOLS
– SLIP - SERIAL LINE IP
– PPP - POINT-TO-POINT PROTOCOL
SLIP (SERIAL LINE IP)






DEVISED IN 1984 TO CONNECT SUNS TO
INTERNET USING MODEMS
SLIP DOES NOT DO ERROR CORRECTION
ONLY SUPPORTS IP -NOT IPX
EACH SIDE MUST KNOW EACH OTHER’S IP
ADDRESS IN ADVANCE
SLIP DOES NOT PROVIDE USER AUTHENTICATION
SLIP IS NOT AN INTERNET APPROVED STANDARD
THEREFORE MANY VERSIONS EXIST
PPP - POINT TO POINT PROTOCOL






APPROVED INTERENT STANDARD
HANDLES ERROR CORRECTION
SUPPORTS MULTIPLE PROTOCOLS
IP ADDRESS CAN BE NEGOTIATED AT CONNECT
TIME
PERMITS AUTHENTICATION
A LINK PROTOCOL CALLED LCP (LINK CONTROL
PROTOCOL) CONNECTS, NEGOTIATES, AND
TERMINATES CONNECTIONS
EXAMPLE OF PC CONNECTION


PC CALLS PROVIDER’S ROUTER VIA MODEM,
ROUTER ESTABLISHES A PHYSICAL
CONNECTION, THE PC THEN SENDS THE ROUTER
A SERIES OF LCP (LINK CONTROL PROTOCOLS)
TO NEGOTIATE PPP PERAMETERS TO BE USED.
THEN A SERIES OF NCP(NETWORK CONTROL
PROTOCOLS) ARE SENT TO CONFIGURE THE
NETWORK LAYER. A NETWORK ADDRESS IS
ISSUED - THE PROVIDER HAS A LIMITED
NUMBER.
– IF TOTAL CUSTOMER CONNECTION EXCEEDS THE
AVAILABLE NO OF IP ADDRESSES CAN’T CONTINUE.