| Home Page |

| Course Page |

Data Link Layer

Lecture Notes

Rochester Institute of Technology—Department of Computer Science

**Bit error**- The transmitter sent a certain bit, but the receiver received the opposite bit

**Bit error rate (BER)**- The probability of a bit error

- Independent bit errors
- Bit error rate =
*p* - Probability of
*k*bit errors in an*n*-bit packet - pr(
*n,k,p*) = choose(*n,k*)*p*^{k}(1 −*p*)^{n−k} - A binomial distribution

- Bit error rate =
**Burst error**- In a group of
*k*consecutive bits, some or all bits were received as the opposite of what was sent

- In a group of
**Erasure**- A group of sent bits vanished and were never received at all
- Usually pertains to entire packets, not individual bits

- Error detection and retransmission
- Erasure coding
- Forward error correction (FEC)

- Also known as Automatic Repeat reQuest (ARQ)
- Operation
- Receiver detects whether an error exists in a received packet
- If so, receiver requests transmitter to re-send the bad packet

- Error detection techniques
- Parity
- Cyclic redundancy check (CRC)
- Checksum

**Even parity**- Transmitter: Add one check bit = modulo-2 sum of the data bits
- Receiver: Verify that modulo-2 sum of the data and check bits = 0
- Can detect a single-bit error

**Odd parity**- Transmitter: Add one check bit = modulo-2 sum of the data bits, plus 1
- Receiver: Verify that modulo-2 sum of the data and check bits = 1
- Can detect a single-bit error

**Cyclic redundancy check**- With a generating polynomial of degree
*n*:- There are
*n*check bits - Can detect an error burst of up to
*n*bits with probability 1 - Otherwise, probability of undetected error is approximately 2
^{−n}

- There are
- Some generating polynomials:
- CRC-16-ANSI =
*x*^{16}+*x*^{15}+*x*^{2}+ 1 - CRC-16-CCITT =
*x*^{16}+*x*^{12}+*x*^{5}+ 1 - CRC-32-IEEE 802.3 =
*x*^{32}+*x*^{26}+*x*^{23}+*x*^{22}+*x*^{16}+*x*^{12}+*x*^{11}+*x*^{10}+*x*^{8}+*x*^{7}+*x*^{5}+*x*^{4}+*x*^{2}+*x*+ 1

- CRC-16-ANSI =
- Transmitter:
- Append
*n*0 bits to data bits - Treat the result as coefficients of a polynomial (mod 2)
- Divide this polynomial by the CRC generator polynomial (mod 2)
- Remainder polynomial = check bits
- Send data bits plus check bits

- Append
- Receiver:
- Treat the data bits plus check bits as coefficients of a polynomial (mod 2)
- Divide this polynomial by the CRC generator polynomial (mod 2)
- Verify that remainder = 0

- Can be done very easily in hardware with a shift register, no division circuits needed (see below)

- With a generating polynomial of degree
- CRC example
- Generator polynomial = CRC-4-ITU =
*x*^{4}+*x*+ 1; represented as 10011 - Transmitter:
- Data = 10010110; represents
*x*^{7}+*x*^{4}+*x*^{2}+*x* - Data plus four 0 bits = 100101100000; represents
*x*^{11}+*x*^{8}+*x*^{6}+*x*^{5} - Divide data-plus-check polynomial by generator polynomial (only the mod 2 coefficients are shown):
10001111 +------------- 10011 | 100101100000 -10011 ----- 00011 -00000 ----- 00111 -00000 ----- 01110 -00000 ----- 11100 -10011 ----- 11110 -10011 ----- 11010 -10011 ----- 10010 -10011 ----- 0001

- Remainder = check bits = 0001
- Send data bits plus check bits = 100101100001

- Data = 10010110; represents
- Receiver:
- Divide data-plus-check polynomial by generator polynomial:
10001111 +------------- 10011 | 100101100001 -10011 ----- 00011 -00000 ----- 00111 -00000 ----- 01110 -00000 ----- 11100 -10011 ----- 11110 -10011 ----- 11010 -10011 ----- 10011 -10011 ----- 0000

- Remainder = 0, so no error detected

- Divide data-plus-check polynomial by generator polynomial:
- Receiver, with errors:
- An error burst garbles the first four bits, 111101100001 received
- Divide data-plus-check polynomial by generator polynomial:
11100100 +------------- 10011 | 111101100001 -10011 ----- 11011 -10011 ----- 10001 -10011 ----- 00100 -00000 ----- 01000 -00000 ----- 10000 -10011 ----- 00110 -00000 ----- 01101 -00000 ----- 1101

- Remainder ≠ 0, so error detected

- Generator polynomial = CRC-4-ITU =
- Hardware shift register circuit for calculating a CRC
- Number of shift register bits = number of check bits
- Shift register bit positions numbered 0 to
*n*−1, right to left - If the CRC generator polynomial includes the term
*x*^{i}, then there is an XOR gate at the input of shift register bit*i*, otherwise not - The output of shift register bit
*n*−1 feeds back to all the XOR gates

- Hardware shift register circuit for calculating CRC-4-ITU
- The CRC-4-ITU generator polynomial is
*x*^{4}+*x*+ 1; so the circuit is: - Example CRC calculation: Data = 10010110
- Initialize shift register to zero
- Feed data plus four 0 bits = 100101100000 through shift register
Register Data bits 0 0 0 0 <-- 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 <-- 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 <-- 0 1 0 1 1 0 0 0 0 0 0 1 0 0 <-- 1 0 1 1 0 0 0 0 0 1 0 0 1 <-- 0 1 1 0 0 0 0 0 0 0 0 1 <-- 1 1 0 0 0 0 0 0 0 1 1 <-- 1 0 0 0 0 0 0 1 1 1 <-- 0 0 0 0 0 1 1 1 0 <-- 0 0 0 0 1 1 1 1 <-- 0 0 0 1 1 0 1 <-- 0 0 1 0 0 1 <-- 0 0 0 0 1 <--

- Check bits = register = 0001

- The CRC-4-ITU generator polynomial is
**Checksum**- Internet Checksum: RFC 1071, RFC 1141, RFC 1624
- Transmitter:
- Group pairs of bytes into words, first byte = most significant, second byte = least significant
- Checksum = −(sum of the words (mod 65535))
- That is, checksum = 65535 − (sum of the words (mod 65535))
- However, if checksum = 0, set checksum to 65535
- Convert checksum back to two bytes
- Append checksum bytes to packet

- Receiver:
- Group pairs of bytes into words, first byte = most significant, second byte = least significant
- Verify sum of the words (mod 65535) = 0

- Probability of undetected error is approximately 2
^{−16}

- Internet Checksum example
- Transmitter:
- Packet bytes (decimal) = (58, 110, 67, 83, 69, 234)
- Words (decimal) = (58⋅256+110, 67⋅256+83, 69⋅256+234) = (14958, 17235, 17898)
- Checksum = −(14958 + 17235 + 17898) (mod 65535) = 15444 = 60⋅256+84
- Send (58, 110, 67, 83, 69, 234, 60, 84)

- Receiver:
- Packet bytes = (58, 110, 67, 83, 69, 234, 60, 84)
- Words = (14958, 17235, 17898, 15444)
- (14958 + 17235 + 17898 + 15444) (mod 65535) = 0; no error detected

- Receiver, with errors:
- The second byte gets garbled
- Packet bytes = (58, 254, 67, 83, 69, 234, 60, 84)
- Words = (15102, 17235, 17898, 15444)
- (15102 + 17235 + 17898 + 15444) (mod 65535) = 144 ≠ 0; error detected

- Transmitter:

- Scenario
- For each packet the transmitter sends . . .
- Either the receiver receives the packet with no errors . . .
- Or the receiver does not receive the packet at all; the packet is "dropped" or "erased"
- Also, the receiver knows
*which*packets are missing

- Reasons for erasure
- Router congestion
- Error detected in received packet

- Erasure coding
- The transmitter generates additional, redundant packets . . .
- That let the receiver
*calculate*what was in the missing packets . . . - Without having to request retransmissions

- Erasure coding techniques
- Longitudinal parity
- Longitudinal parity with interleaving
- Two-dimensional parity
- Reed-Solomon codes

**Longitudinal parity**- Transmitter:
- For every
*n*data packets, generate one redundant packet - Each byte of redundant packet = XOR of corresponding bytes of data packets

- For every
- Receiver:
- If one of the
*n*+1 packets is erased . . . - Each byte of erased packet = XOR of corresponding bytes of remaining packets

- If one of the
- Can tolerate erasure of one packet out of
*n*

- Transmitter:
- Longitudinal parity example
- 16 data packets,
*n*= 16, each packet = 4 bytes (hexadecimal)

- 16 data packets,
**Longitudinal parity with interleaving**- Transmitter:
- For every
*n*×*k*data packets, generate*k*redundant packets - Arrange data packets into an
*n*×*k*matrix *k*redundant packets = longitudinal parity of the columns- Transmit packets by rows

- For every
- Receiver:
- If one of the
*n*+1 packets in a column is erased . . . - Each byte of erased packet = XOR of corresponding bytes of remaining packets

- If one of the
- Can tolerate erasure of one packet in each column
- Can tolerate erasure of
*k**consecutive*packets

- Transmitter:
- Longitudinal parity with interleaving example
- 16 data packets,
*n*= 8,*k*= 2, each packet = 4 bytes (hexadecimal)

- 16 data packets,
**Two-dimensional parity**- Transmitter:
- For every
*n*×*n*data packets, generate 2*n*+1 redundant packets - Arrange data packets into an
*n*×n matrix *n*redundant packets = longitudinal parity of the rows*n*+1 redundant packets = longitudinal parity of the columns- Transmit packets by rows

- For every
- Receiver:
- If one of the
*n*+1 packets in a row or column is erased . . . - Each byte of erased packet = XOR of corresponding bytes of remaining packets in the same row or column

- If one of the
- Can tolerate erasure of one packet in each row and one packet in each column
- Can tolerate erasure of
*k**consecutive*packets

- Transmitter:
- Two-dimensional parity example
- 16 data packets,
*n*= 4, each packet = 4 bytes (hexadecimal)

- 16 data packets,
**Reed-Solomon coding**- For every
*n*packets, generate*k*redundant packets - Details: See "A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems"
- Can tolerate erasure of
*any k*packets

- For every
- Probability of erasures
*p*= probability of erasing a packet- Assume erasures are independent
- pr(
*n,k*) = probability of erasing exactly*k*packets in a group of*n*packets = choose(*n,k*)*p*^{k}(1 −*p*)^{n−k} - choose(
*n,k*) =*n*! /*k*! / (*n − k*)! - Probability of erasing anywhere from 0 to
*k*packets in a group of*n*packets = Sum from*i*= 0 to*k*of pr(*n,i*)

- Scenario
- Done at the bit level rather than the packet level
- Transmitter appends check bits to each data word
- Receiver uses check bits to detect
*and correct*errors

- Notation: "(
*n, k, d*) code"- Each codeword is
*n*bits - Each codeword contains
*k*data bits and*n − k*check bits - The minimum Hamming distance between any two codewords is
*d*

- Each codeword is
- To correct
*m*errors, we need*d*≥ 2*m*+ 1 **Hamming code**- A (2
^{i}−1, 2^{i}−1−*i*, 3) code for some*i* - Can correct a one-bit error
- Details: See "The Hamming Code"

- A (2
**Golay code**- A (24, 12, 8) code
- Can correct up to three bit errors
- Used by the Voyager I and Voyager II spacecraft (1979−1981) to send pictures of Jupiter and Saturn
- Generator matrix:
[ 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0 ] [ 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 ] [ 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 ] [ 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 1 0 0 ] [ 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 1 1 0 ] [ 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 ] [ 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 ] [ 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 1 1 0 1 ] [ 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 ] [ 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 ] [ 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1 ] [ 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 ]

**Reed-Solomon code**- Can also be used to correct errors, not just recover from erasures
- Used on compact discs to deal with scratches on the disc's surface
- Used on recent space missions like Mars Pathfinder

**Trellis coded modulation (TCM)**- Published by Gottfried Ungerböck in 1982
- Survey articles:
- G. Ungerböck. Trellis-coded modulation with redundant signal sets, Part I: Introduction.
*IEEE Communications Magazine,*25(2):5-11, February 1987. - G. Ungerböck. Trellis-coded modulation with redundant signal sets, Part II: State of the art.
*IEEE Communications Magazine,*25(2):12-21, February 1987.

- G. Ungerböck. Trellis-coded modulation with redundant signal sets, Part I: Introduction.
- A combination of a
**trellis code**for forward error correction and**multilevel DPSK**for modulation - Each group of
*k*bits is encoded by a codeword with*k*+1 bits - Each codeword then causes a phase shift in the DPSK modulated waveform
- Demodulation is followed by soft bit detection with Viterbi decoding for error correction

- Example of a TCM trellis (from Ungerböck's article)
- Each edge encodes two data bits as one of eight signals
- Edge marked "0 4": encode data bits 00 with signal 0; encode data bits 01 with signal 4
- Edge marked "2 6": encode data bits 10 with signal 2; encode data bits 11 with signal 6
- Edge marked "1 5": encode data bits 00 with signal 1; encode data bits 01 with signal 5
- Edge marked "3 7": encode data bits 10 with signal 3; encode data bits 11 with signal 7

- ARQ: Used universally in TCP
- Requires feedback from receiver to transmitter (ACKs)
- Good when bandwidth is large and latency is small

- Erasure coding: ACK-less error control
- Good when packet loss probability is small
- Proactive erasure coding
- Reactive erasure coding; NACK-based protocols
- Reliable multicast protocols

- FEC: Eliminates errors altogether (with high probability)
- Good when bit error rate is not too high, but erroneous packet rate is high
- Good for data links with large latency, where feedback from receiver to transmitter is undoable

- MAC = Medium Access Control
- Standardized by the IEEE
- Used to designate a
*station*(or a group of stations) on the local network - Format (48 bits):
`xxxxxxLM xxxxxxxx xxxxxxxx yyyyyyyy yyyyyyyy yyyyyyyy``M`= 0: unicast address,`M`= 1: multicast address`L`= 0: global address,`L`= 1: local address`xxx...xxx`= Organizationally Unique Identifier; designates equipment vendor`yyy...yyy`= Network interface controller (NIC) number

- Transmission order
- Bytes of the MAC address are sent in big-endian order (network order)
- Bits of each byte are sent in
*little-endian order* - Therefore, the first bit sent is the unicast/multicast bit
- The second bit sent is the global/local bit

- Unicast address
- Designates one particular station to receive a transmission

- Multicast address
- Designates every station in a particular
*multicast group*to receive a transmission

- Designates every station in a particular
- Broadcast address
- = 11111111 11111111 11111111 11111111 11111111 11111111
- Designates
*every*station (on the local network) to receive a transmission

- Local network technology with wired (cable) communication medium
- Ethernet frame format
- Header (14 bytes)
- Destination MAC address (6 bytes)
- Source MAC address (6 bytes)
- EtherType field (2 bytes) — designates what the payload is

- Payload (46–1500 bytes)
- CRC (4 bytes) — for error detection

- Header (14 bytes)
- Wikipedia article on the EtherType field: http://en.wikipedia.org/wiki/EtherType
- Early versions of Ethernet used a
**bus**topology with a shared communication medium- Thick wire Ethernet (10BASE5) — http://en.wikipedia.org/wiki/10BASE5
- Thin wire Ethernet (10BASE2) — http://en.wikipedia.org/wiki/10BASE2
- Each station taps into the shared cable
- Medium access: Carrier Sense Multiple Access with Collision Detection (CSMA/CD)

- More recent versions of Ethernet used a
**star**topology with a shared communication medium- Category 5 (CAT5) twisted pair cables
- Each station connects to a central
**hub**with a separate cable - The hub is dumb; it relays every incoming signal onto every outgoing cable
- Medium access: CSMA/CD

- Modern versions of Ethernet use a
**star**topology with a non-shared communication medium- Category 5 (CAT5) twisted pair cables
- Each station connects to a central
**switch**with a separate cable - The switch is smart; it queues incoming frames and sends them out only on the appropriate port(s)
- The switch discovers which stations are attached to which ports by examining the source MAC addresses in the frames
- Medium access: Not needed

- Local network technology with wireless (radio) communication medium
- Like early Ethernet, Wi-Fi uses a shared communication medium
- Medium access protocol required

- Unlike early Ethernet, some stations may not be able to receive other stations' transmissions
- Hidden Station Problem

- Infrastructure mode
- The wireless local network includes a
**Wireless Access Point (AP)** - AP routes frames between wireless and wired networks
- AP also participates in medium access control

- The wireless local network includes a
- Ad hoc mode
- No AP
- Stations communicate wirelessly only among each other

- Three kinds of medium access
- Carrier sense
- Distributed Coordination Function
- Point Coordination Function

- Carrier sense
- Typically used for short data frames
- Wait until the medium is idle for the Distributed Inter-Frame Space (DIFS) (50 μsec)
- Transmit the data frame to the destination
- Wait to receive an Acknowledgment (ACK) frame from the destination
- If ACK fails to arrive, backoff and try again
- Collisions can happen
- E.g., if multiple stations all sense an idle medium and transmit at the same time

- Distributed Coordination Function (DCF)
- A.k.a. Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA)
- Typically used for long data frames
- Wait until the medium is idle for the DIFS
- Transmit a Request To Send (RTS) frame to the destination
- Wait to receive a Clear To Send (CTS) frame from the destination
- The RTS/CTS handshake indicates how long the sending station needs to use the channel
- Other stations hear the RTS and the CTS
- Other stations will not transmit during the time interval reserved by the RTS/CTS — collision avoidance

- Transmit the data frame to the destination
- Wait to receive an Acknowledgment (ACK) frame from the destination
- If ACK fails to arrive, backoff and try again
- Collisions are mostly avoided but still can happen
- E.g., if a distant station does not hear the RTS/CTS handshake

- Point Coordination Function (PCF)
- Typically used when real-time frame delivery guarantees are required (video, audio)
- The AP polls the stations in a round-robin fashion
- Each station waits to receive a poll, then transmits a data frame
- Collisions cannot happen
- Not supported by most APs

| Course Page |

| Home Page |