Packets and frames

Types of service

Limits of error-checking:
All error-detection and correction methods
only work below a certain error rate

HDLC

PPP

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?

  1. Error checking - all circuits have errors occasionally.

  2. 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

  1. Packet is generic term for piece of data that higher layer wants to send.

  2. 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:
  1. Unacknowledged connectionless service ("light" data link layer, packet-by-packet error-checking)

  2. Acknowledged connectionless service ("heavyweight" data link layer, frame-by-frame error-checking)

  3. Acknowledged connection-oriented service

Do error checking in what layer?

  1. Low error rate (e.g. fiber): Do error-checking in higher layer, on larger pieces of data (multi-frame objects).

  2. High error rate (e.g. wireless): Do error-checking in data link layer, on every single frame.

Example

Imagine average 10 frames per packet.
  1. high error rate: Imagine average 20 percent of frames are lost.

  2. low error rate:

Framing

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).
  1. 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.

  2. 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:

  1. Phone lines - moderate
  2. Coaxial cable - low
  3. Fiber optic - very low
  4. Wireless - very high

Burst errors

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:

  1. 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.

  2. Disadvantage - Much harder to correct than isolated errors.

Error-detection (and re-transmit) v. Error-correction

  1. 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.

  2. 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.

All error-detection and correction methods only work below a certain error rate

If we allow any number of errors in data bits and in check bits, then no error-detection (or correction) method can guarantee to work, since any valid pattern can be transformed into any other valid pattern.

All methods of error-detection and correction only work if we assume the number of bits changed by error is below some threshold. If all bits can be changed, no error detection method can work even in theory. All methods only work below a certain error rate. Above that rate, the line is simply not usable.
General strategy: Coding scheme so that a small no. of errors in this block won't change one legal pattern into another legal pattern: If errors still getting through: Reduce block size, so will get less errors per block.

3.2.1 Error-correcting codes

Frame or codeword length n = m (data) + r (redundant or check bits).
All 2m patterns are legal.
Not all 2n patterns are legal.

Basic idea: If illegal pattern, find the legal pattern closest to it. That might be the original data (before errors corrupted it).

Given two bitstrings, XOR gives you the number of bits that are different. This is the Hamming distance.
If two codewords are Hamming distance d apart, it will take d one-bit errors to convert one into the other.

  1. To detect (but not correct) up to d errors per length n, you need a coding scheme where codewords are at least (d+1) apart in Hamming distance. Then d errors can't change into another legal code, so we know there's been an error.

  2. To correct d errors, need codewords (2d+1) apart. Then even with d errors, bitstring will be d away from original and (d+1) away from nearest legal code. Still closest to original. Original can be reconstructed.

Error-detection example: Parity bit

Recall modems.
Appended to data so that no. of 1 bits is even (or odd).
Codeword distance 2.
Can detect (but not correct) 1 error.
Can't detect 2 errors.

Error-correction example: Sparse codewords

Let's say only 4 valid codewords, 10 bits: 
0000000000
0000011111
1111100000
1111111111
Minimum distance 5.
Can detect and correct 1,2 errors.
Can detect but not correct 3,4 errors.
Can't detect 5 errors.

Note: Can detect some (even most) 5 bit errors.
Just can't guarantee to detect all 5 bit errors.

e.g. Encode every 2 bits this way.
Need 5 times the bandwidth to send same amount of data.
But can communicate even if almost every other bit is an error (4 out of 10).

Theoretical limit of 1-bit error-correction

Detect and correct all 1 errors.
Need distance 3.

We need to have 2m legal messages.
If change 1 bit, must get illegal (and an illegal which is 1 bit away from this message, but not 1 bit away from any other legal message).
So each of the 2m must have n illegal codewords at distance 1 from it (systematically change each bit). These are my illegals, can't overlap with the illegals that are 1 bit away from other patterns.
Each message needs (n+1) patterns reserved for it.
(n+1) 2m <= 2n
(n+1) <= 2n-m
(m+r+1) <= 2r

For large r, this is always true.
i.e. This is putting a limit on how small r can be.
e.g. Let m=64. Then we need:
r+65 <= 2r
Remember powers of 2.
i.e. r >= 7

What block size?

It scales well. Let m=1000. then r=10.
Question is, will 1000 bits only have 1 error?

e.g. Could send 1 M bits, need only 20 check bits to error-correct 1 bit error! But if there are 2 errors the system fails.

If errors getting through: Reduce m until almost never get more than 1 error per block.

Hamming code

Error-detection (and re-transmit) v. Error-correction

Example

Errors isolated. 1 in 106.
Block size 1000 bits.
i.e. Error on average 1 bit every 1000 blocks.
  1. To do error-correction on 1000 bit block, need 10 check bits (210=1024).
    1 M of data needs overhead of 10,000 check bits.

  2. To just error-detect a block with a 1 bit error, need 1 parity bit.
    1 M of data needs 1,000 check bits.
    Once every 1000 blocks (1 M), 1 block needs to be re-transmitted (extra 1001).
    1 M of data needs overhead 2,001 bits.

Q. For what error rate are they equal?

3.2.2 Error-detecting codes

Parity bit for 1 bit error detection

Parity bit can detect 1 error. Won't detect 2. Will detect 3, won't detect 4, etc.
If large block has 1 parity bit and is badly damaged, the odds of detecting this are only 0.5.

Parity bit for n bit burst error detection

Each block is considered as matrix, width n, height k.
Parity bit calculated for each column.
Last row of parity bits appended: (parity bit for col 1, col 2, ..., col n)
Transmit n(k+1) block row by row.

  1. Any burst of length up to n in the data bits will leave at most 1 error in each col.
    Can be detected.

  2. If burst is in the parity bits row, they will be wrong and we will detect there has been an error.
    Note: Don't know where error was (this is detection not correction). Will ask for re-transmit (don't know that data bits were actually ok).

Q. What about burst of length up to n partly in last row of data and partly in the parity bits row?

For longer bursts, damaging the whole block:

Prob. of any given damaged column having correct parity by chance = 1/2
Prob. of all columns having correct parity by chance = (1/2)n
Reasonable chance we'll detect it.
(If every parity bit in last line ok, it is prob. because there was no error, rather than by chance.)

Isolated errors

Isolated errors more difficult:
Any 2-bit error, where errors come at time t and t+n, will not be detected.

Polynomial codes

Simple Data Link protocol sample code

Sliding Window protocols

3.6 Example Data Link protocols

3.6.1 HDLC

3.6.2 PPP (point-to-point Data Link protocol in Internet)

Recall 1.2.

  1. Local networks - LANs - look at Data Link layer for these later.
  2. Wide-area network - built mainly on point-to-point leased lines. Look at Data Link layer for these here.
Point-to-point situations:
  1. LAN of organisation attaches to Internet.
    All comms of organisation goes through router, which has point-to-point leased line connection with outside router.

  2. Home user. Point-to-point connection with ISP.
    Like having temporary leased line (dial-up) or permanent (broadband, on 24/7).

  3. Point-to-point between backbone routers on Internet.

PPP

Broadcast networks