Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4568 + 2419 = 6987
Home Page
 Data Communications and Networks • CSCI 351-01 • Spring Semester 2016
Course Page

## CSCI 351—Data Communications and Networks Data Link Layer Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

### Transmission Errors

• 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) pk (1 − p)nk
• A binomial distribution

• Burst error
• In a group of k consecutive bits, some or all bits were received as the opposite of what was sent

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

### Error Control: Three Approaches

• Error detection and retransmission

• Erasure coding

• Forward error correction (FEC)

### Error Detection and Retransmission

• 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 2n
• Some generating polynomials:
• CRC-16-ANSI = x16 + x15 + x2 + 1
• CRC-16-CCITT = x16 + x12 + x5 + 1
• CRC-32-IEEE 802.3 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
• 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
• 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)

• CRC example
• Generator polynomial = CRC-4-ITU = x4 + x + 1; represented as 10011
• Transmitter:
• Data = 10010110; represents x7 + x4 + x2 + x
• Data plus four 0 bits = 100101100000; represents x11 + x8 + x6 + x5
• 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

• 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

• 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

• 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 xi, 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 x4 + 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

• 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

### Erasure Coding

• 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
• Receiver:
• If one of the n+1 packets is erased . . .
• Each byte of erased packet = XOR of corresponding bytes of remaining packets
• Can tolerate erasure of one packet out of n

• Longitudinal parity example
• 16 data packets, n = 16, each packet = 4 bytes (hexadecimal)

• 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
• 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
• Can tolerate erasure of one packet in each column
• Can tolerate erasure of k consecutive packets

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

• Two-dimensional parity
• Transmitter:
• For every n×n data packets, generate 2n+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
• 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
• Can tolerate erasure of one packet in each row and one packet in each column
• Can tolerate erasure of k consecutive packets

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

• Reed-Solomon coding

• 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) pk (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)

### Forward Error Correction

• 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

• To correct m errors, we need d ≥ 2m + 1

• Hamming code
• A (2i−1, 2i−1−i, 3) code for some i
• Can correct a one-bit error
• Details: See "The Hamming Code"

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

### Error Control Usage

• 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 Addresses

• 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

• Broadcast address
• = 11111111 11111111 11111111 11111111 11111111 11111111
• Designates every station (on the local network) to receive a transmission

### Ethernet — IEEE 802.3

• 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

• 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

• 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

### Wi-Fi — IEEE 802.11

• 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

• 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

 Data Communications and Networks • CSCI 351-01 • Spring Semester 2016
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4568 + 2419 = 6987
Home Page
Copyright © 2016 Alan Kaminsky. All rights reserved. Last updated 12-Jan-2016. Please send comments to ark­@­cs.rit.edu.