Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

My big idea: Ancient Brain


CA114      CA170

CA668      CA669      Projects

  Packets and frames

Types of service

Error detection and correction



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

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

  3. 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?

  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.


Imagine average 10 frames per packet.
  1. 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.

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


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

Error detection and correction

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.


Broadcast networks

ancientbrain.com      w2mind.org      humphrysfamilytree.com

On the Internet since 1987.

Wikipedia: Sometimes I link to Wikipedia. I have written something In defence of Wikipedia. It is often a useful starting point but you cannot trust it. Linking to it is like linking to a Google search. A starting point, not a destination. I automatically highlight in red all links to Wikipedia and Google search and other possibly-unreliable user-generated content.