Data Link Layer
Data link layer algorithms
may be embedded in the network hardware
(rather than running as software process on a machine).
In general,
computer algorithms don't have
to be run as software on general-purpose machines.
You can design dedicated hardware to run them.
Often done to increase speed
for fundamental algorithms run constantly.
Or some combination of dedicated hardware
plus limited-programmable.
What does data link layer have to do?
Assume a single link from A to B.
Assume service provided by physical layer
is that it will
deliver bits to B in the order in which they are sent.
So what does data link layer have to do?
- Error checking - all circuits have errors occasionally.
- Flow regulation
- Line has finite data rate, and machines have finite rate at which
they can process incoming.
Regulate flow so that slow receivers are not swamped by fast senders.
3.1 Packets and frames
-
Packet
is generic term
for piece of data
that higher layer wants to send.
-
Data link layer sends
frames
- small fixed (or max) length pieces of data.
Frame length specific to hardware.
Frame is packet encoded for transmission on this link.
As a packet travels across the Internet from A to B,
it may go along multiple types of links (phone, fiber, wireless),
each with different frame sizes and formats.
Packet may be encoded in a different way for each link
it travels on.
Small packet: Goes in 1 frame.
Larger packet (quite normal):
Multiple frames per packet.
Packet has to be broken up, sent as multiple frames, re-assembled.
Packet
may travel through many Data Link Layers:
A router on the Internet.
Frame -to- packet -to- [routing decision] -to- packet -to- frame.
It goes through Layer 2 - Data Link layer [actual transmission] on many routers
and
Layer 3 - Network layer [routing decision] on many routers.
Transport layer is the first end-to-end layer.
3.1.1 Types of service
Types of service
offered by data link layer to higher layer:
- Unacknowledged connectionless service
("light" data link layer, packet-by-packet error-checking)
-
A sends frames to B.
No acks.
No logical connection established or released.
-
If frame lost, no attempt to detect loss or recover from it
(at least, not in data link layer).
- Works if error rate low (e.g. fiber).
Error recovery
can be done in higher layers
on larger pieces of data.
- e.g. Most LANs
(fiber or high-quality copper,
all local,
short distances,
very low error rate)
use this service in data link layer.
- Also for comms where small errors not necessarily
a problem, e.g. streaming
audio, video, voice.
- Acknowledged connectionless service
("heavyweight" data link layer, frame-by-frame error-checking)
-
Still no logical connection.
-
But if frame not ack'd after timeout, it is re-sent.
- Lost ack means a frame
might be received multiple times.
- Used when error rate high (e.g. wireless).
- Acknowledged connection-oriented service
- A and B set up connection before transferring data.
- Frames numbered.
Each frame sent is received exactly once, in right order.
Do error checking in what layer?
- Low error rate (e.g. fiber): Do error-checking in higher layer,
on larger pieces of data (multi-frame objects).
- High error rate (e.g. wireless): Do error-checking in data link layer,
on every single frame.
Example
Imagine average 10 frames per packet.
- high error rate:
Imagine average 20 percent of frames are lost.
- Error-check in higher layer:
Packet-by-packet checking.
Send packet. If didn't get through, higher layer
sends entire packet again.
Average packet will lose 2 frames.
Will take a while on average to get clear run of 10 frames in a row
without error.
prob. of frame getting through = 0.8.
If send frame 100 times, 80 will get through, 20 will fail.
prob. of 10 in a row ok = (0.8)10 = 0.1 approx.
If send packet 100 times, only 10 will get through, 90 will fail.
- Error-check in data link layer is best:
Frame-by-frame checking.
Packets will get through much faster.
- low error rate:
- Error-check in higher layer is best:
Packets will get through quicker if there
is no frame checking, and complete re-send of the (very rare)
bad packet.
- Error-check in data link layer:
Frame-by-frame checking is obviously more costly.
So don't use it unless the error rate is high enough
to make it worthwhile.
- e.g.
Imagine average 0.1 percent of frames are lost.
1 in 1000 frames lost.
prob. of frame getting through = 0.999
prob. of 10 in a row ok = (0.999)10 = 0.99 approx.
If do packet-level error checking,
approx
1 in 100 packets lost and has to be re-sent
3.1.3 Error Control
Recall
types of service.
Special control frames - contain positive ack (received ok)
or negative ack (received but corrupted).
Noise burst error may wipe frame completely.
No ack sent back at all.
Also ack could be sent but lost!
Sender must have timer for each frame.
If no ack within timeout, re-send.
Timer must be specific to this link and to hardware on this link
(how long frame transmit and ack return will take).
Timer goes off.
Re-send frame.
Receiver may receive frame multiple times (e.g. if ack was lost).
Must make sure doesn't pass it twice to higher layers.
Solution: Assign sequence numbers to frames.
3.1.4 Flow control
Fast sender. Slow receiver can't process incoming frames fast enough.
Can happen even if receiver is fast machine (as traffic increases).
- Feedback-based flow control
- Receiver sends back info to sender about how it is doing,
e.g. "You can send up to 100 k now,
then wait until I say".
- Used in Data Link.
- Rate-based flow control
- Protocol has built-in data rate limit.
- Used in higher layers.
3.2 Error detection / correction
Error:
0 changes to 1
or 1 changes to 0
Error rates:
- Phone lines - moderate
- Coaxial cable - low
- Fiber optic - very low
- Wireless - very high
Errors may come in isolated single bits
or in
bursts (lots of bits in a row lost).
Radio has a lot of burst errors.
Technically, a burst error
doesn't mean every single bit in the burst is precisely flipped.
Burst errors look more like this
(dash "-" means data got through ok, B means bit was flipped):
-----------------------------------------------------------------------
-----------------------------------------------------------------------
------------------BBBB-BBB--BBB-B--BBBB-BBB----------------------------
-----------------------------------------------------------------------
-----------------------------------------------------------------------
-----------------------------------------------------------------------
Inside burst, signal may be distorted but (by chance) the bit
comes out reading the same.
Technically, a burst error
means first and last bits flipped,
not necessarily
all ones in between.
Burst errors:
- Advantage - Might get few bad blocks.
e.g. Block size 1000 bits. Error rate 1 in 1000.
If errors random, average block will have error.
If errors in bursts of 100, will get a burst of 100 in a row for every 100,000 bits (100 blocks).
This burst will cover only 1 or 2 blocks.
So on average, only 1 or 2 blocks per 100 has error.
- Disadvantage - Much harder to correct than isolated errors.
- Error-detecting codes
- just include enough redundant info with the block
for the receiver to be able to deduce that there was an error
(then asks for re-transmit).
Used when error rate low (e.g. fiber).
Recall discussion in 3.1.1.
- Error-correcting codes
- include more info - include enough redundant info with the block
for the receiver to be able to deduce what bits are wrong
and reconstruct original.
Used when error rate high (e.g. wireless).
Detect plus re-transmit no good because re-transmit will have errors too.
Simple Data Link protocol
sample code
3.6 Example Data Link protocols
- HDLC
- SDLC
used in IBM's
SNA
mainframe network protocol.
- Features:
3.6.2 PPP (point-to-point Data Link protocol in Internet)
Recall
1.2.
- Local networks - LANs
- look at Data Link layer for these later.
- Wide-area network - built mainly on
point-to-point leased lines.
Look at Data Link layer for these here.
Point-to-point situations:
- LAN of organisation attaches to Internet.
All comms of organisation goes through router,
which has point-to-point leased line connection with outside router.
- Home user. Point-to-point connection with ISP.
Like having temporary leased line (dial-up)
or permanent
(broadband, on 24/7).
- Point-to-point between backbone routers on Internet.
PPP
- Internet protocol stack:
- TCP - Transport Layer
- IP - Network Layer
- PPP - Data Link layer for point-to-point lines
- SLIP (replaced by PPP)
- Features of PPP:
- character-oriented, using byte stuffing
- start and end flag bytes
01111110
( = tilde
if stream were to be interpreted as text)
- escape byte
01111101
( = right chain bracket
if stream were to be interpreted as text)
- payload is variable length up to some max
(default max is 1500 bytes = 12 k bits)
-
CRC checksum.
- polynomial: the 16-bit HDLC polynomial
CRC-CCITT
by default
-
32-bit Ethernet polynomial
is an option.
- default is
unacknowledged service
in Data Link layer,
no acks, no frame numbers
- ack-ed (reliable) service can be set up as an option
- generally, though, if you need reliable service,
this is done in higher layer
(TCP)
Ancient Brain