Networks, Security, and Privacy 158.235
Dr Hooman Alavizadeh Massey University
1
Data Link
Layer
Reading: Chapter 4 / Chapter 7 in the prescribed textbook
2
Introduction
• Layer 2 in the Internet model
• Responsible for moving messages from one device (node) to another physically adjacent node over a link
• Major functions of a data link layer protocol
– Data Transfer (over a Link) – Error Control
Internet Model
Application Transport Network Data Link Physical
3
Where is the link layer implemented?
• in each and every host
• link layer implemented in
“adaptor” (aka network interface card NIC) or on a chip
– Ethernet card, 802.11 card; Ethernet chipset
– implements link, physical layer
• attaches into host’s system buses
• combination of hardware, software, firmware
host
bus
(e.g., PCI)
cpu
controller
physical
transmission
memory
application
transport
network
link
link
physical
network adapter card
4
Data Link Layer
• Data Transfer
• Error Control
• Ethernets –Wired vs Wireless
5
MAC addresses
• MAC address:
– 48 bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable
– e.g.: 1A-2F-BB-76-09-AD hexadecimal (base 16) notation
(each “number” represents 4 bits)
– function: used ‘locally” to get frame
from one interface to another physically-connected interface (same network, in IP-addressing sense)
6
MAC addresses
• MAC address allocation administered by IEEE
• manufacturer buys portion of MAC address space (to assure uniqueness)
• analogy:
– MAC address: like Social Security Number – IP address: like postal address
7
Data Transfer: Same Network
Question: how to determine a MAC address knowing its
IP address?
137.196.7.23 A
LAN 71-65-F7-2B-08-53
• A broadcasts ARP query packet, containing B’s IP address
137.196.7.14
B
58-23-D7-FA-20-B0
– dest MAC address = FF-FF- FF-FF-FF-FF
– all nodes on LAN receive ARP query (broadcast)
ARP query
ARP reply
Src IP address
137.196.7.23
137.196.7.14
Dest IP address
137.196.7.14
137.196.7.23
Src MAC address
71-65-F7-2B-08- 53
58-23-D7-FA-20- B0
Dest MAC address
FF-FF-FF-FF- FF-FF
71-65-F7-2B-08- 53
• B receives ARP packet, replies to A with its (B’s) MAC address
– frame sent to A’s MAC address (unicast)
8
Data Transfer: Different Networks
walkthrough: send datagram from A to B via R
– focus on addressing – at IP (datagram) and MAC layer
(frame)
– assume A knows B’s IP address
– assume A knows IP address of first hop router, R – assume A knows R’s MAC address
A
111.111.111.111 74-29-9C-E8-FF-55
111.111.111.112 CC-49-DE-D0-AB-7D
R
222.222.222.220 1A-23-F9-CD-06-9B
111.111.111.110 E6-E9-00-17-BB-4B
B
222.222.222.222 49-BD-D2-C7-56-2A
222.222.222.221 88-B2-2F-54-1A-0F
9
Data Transfer: Different Networks
❖ A creates IP datagram with IP source A, destination B
❖ A creates link-layer frame with R’s MAC address as dest, frame
contains A-to-B IP datagram
MAC src: 74-29-9C-E8-FF-55 MAC dest: E6-E9-00-17-BB-4B
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
A
111.111.111.111 74-29-9C-E8-FF-55
111.111.111.112 CC-49-DE-D0-AB-7D
R
222.222.222.220 1A-23-F9-CD-06-9B
111.111.111.110 E6-E9-00-17-BB-4B
B
222.222.222.222 49-BD-D2-C7-56-2A
222.222.222.221 88-B2-2F-54-1A-0F
10
Data Transfer: Different Networks
❖ framesentfromAtoR
❖ frame received at R, datagram removed, passed up to IP
MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-EI9P-0s0rc-:1171-B1.B1-141B.111.111
IP dest: 222.222.222.222 IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
IP
Eth
Phy
A
111.111.111.111 74-29-9C-E8-FF-55
111.111.111.112 CC-49-DE-D0-AB-7D
R
222.222.222.220 1A-23-F9-CD-06-9B
111.111.111.110 E6-E9-00-17-BB-4B
B
222.222.222.222 49-BD-D2-C7-56-2A
222.222.222.221 88-B2-2F-54-1A-0F
11
Data Transfer: Different Networks
❖ R forwards datagram with IP source A, destination B
❖ R creates link-layer frame with B’s MAC address as dest, frame
contains A-to-B IP datagram
IP
Eth
Phy
A
111.111.111.111 74-29-9C-E8-FF-55
111.111.111.112 CC-49-DE-D0-AB-7D
MAC src: 1A-23-F9-CD-06-9B MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP Eth Phy
R
222.222.222.220 1A-23-F9-CD-06-9B
111.111.111.110 E6-E9-00-17-BB-4B
B
222.222.222.222 49-BD-D2-C7-56-2A
222.222.222.221 88-B2-2F-54-1A-0F
12
Data Transfer: Different Networks
❖ R forwards datagram with IP source A, destination B
❖ R creates link-layer frame with B’s MAC address as dest, frame
contains A-to-B IP datagram
IP
Eth
Phy
A
111.111.111.111 74-29-9C-E8-FF-55
111.111.111.112 CC-49-DE-D0-AB-7D
MAC src: 1A-23-F9-CD-06-9B MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP Eth Phy
R
222.222.222.220 1A-23-F9-CD-06-9B
111.111.111.110 E6-E9-00-17-BB-4B
B
222.222.222.222 49-BD-D2-C7-56-2A
222.222.222.221 88-B2-2F-54-1A-0F
13
Data Transfer: Different Networks
❖ R forwards datagram with IP source A, destination B
❖ R creates link-layer frame with B’s MAC address as dest, frame
contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B MAC dest: 49-BD-D2-C7-56-2A
IP src: 111.111.111.111
IP dest: 222.222.222.222
IP
Eth
Phy
A
111.111.111.111 74-29-9C-E8-FF-55
111.111.111.112 CC-49-DE-D0-AB-7D
R
222.222.222.220 1A-23-F9-CD-06-9B
111.111.111.110 E6-E9-00-17-BB-4B
B
222.222.222.222 49-BD-D2-C7-56-2A
222.222.222.221 88-B2-2F-54-1A-0F
14
Data Link Layer
• Data Transfer
• Error Control
• Ethernets –Wired vs Wireless
15
Error Control
• Network errors
– Types
• Corrupted data • Lost data
– Caused by problems in transmission (not humans)
• Networks should be designed with:
– Error prevention – Error detection – Error correction
4 – 16
Sources of Network Errors
• Line noise and distortion
– Major reason for errors and caused by several sources
– More likely on electrical media and lower-end cables (e.g. twisted pair)
– Undesirable electrical signal
– Degrades performance of a circuit
– Manifestation
• Extra bits
• Flipped bits • Missing bits
17
Sources of Errors and Prevention
Source of Error
White Noise
Cross-talk
Attenuation
What Causes It
Movement of electrons
Multiplexer guardbands too small or wires too close together
Gradual decrease in signal over distance
How to Prevent or Fix
Increase signal strength
Increase the guardbands or move or shield the wires
Use repeaters
Impulse Noise Sudden increases in electricity (e.g., lightning)
Shield or move the wires
Echo Poor (misaligned) connections Fix the connections or tune equipment
Intermodulation noise Signals from several circuits combine
Move or shield the wires
18
Error Detection
• Receivers need to know when the data transmitted is not correct
• Add “check value” (error detection value) to message
• Check value produced by mathematical formula
Message
Check Value
19
Sender calculates an
Error Detection Value (EDV) and transmits it along with data
Receiver recalculates EDV and checks it against the received EDV
Error Detection
Mathematical calculations
Mathematical calculations
? =
Data to be EDV transmitted
–If the same→No errors in transmission
– If different → Error(s) in transmission
20
Error Detection Techniques
• Parity checks
• Checksum
• Cyclic Redundancy Check (CRC)
21
Parity Checking
• One of the oldest and simplest
• A single bit added to each character – Even parity: number of 1’s remains even – Odd parity: number of 1’s remains odd
• Receiving end recalculates parity bit
– If one bit has been transmitted in error the received
parity bit will differ from the recalculated one
• Simple, but doesn’t catch all errors
– If two (or an even number of) bits have been transmitted in error at the same time, the parity check appears to be correct
– Detects about 50% of errors
22
Examples of Using Parity
To be sent: Letter V in 7-bit ASCII: 0110101
EVEN parity sender
Add a bit so that the number of all transmitted 1’s is EVEN
ODD parity sender
Add a bit so that the number of all transmitted 1’s is ODD
01101010 parity
receiver
01101011 parity
receiver
23
Checksum
• A checksum (usually 1 byte) is added to the end of the message
• It is 95% effective • Method:
• Add decimal values of each character in the message
• Divide the sum by 255
• The remainder is the checksum value
24
CRC
• Cyclic redundancy check (CRC)
– Treats message as a single binary number (D)
– Choose r+1 bit pattern (generator), G – Uses remainder as the check value
• goal: choose r CRC bits, R, such that
▪
▪ receiver knows G, divides
• Modes:
– CRC-16 (~99.998% error detection rate)
– CRC-32 (>99.99999% error detection rate)
25
Error Correction
• Once detected, the error must be corrected
• Error correction techniques
– Retransmission (or, backward error correction)
• Simple and most common
• Automatic Repeat reQuest (ARQ)
• This can also provide flow control by limiting the number of messages sent
– Forward Error Correction
• Receiving device can correct incoming messages without retransmission
26
• •
Automatic Repeat reQuest (ARQ)
Process of requesting a data transmission be resent
Main ARQ protocols
– Stop and Wait ARQ (A half duplex technique)
• Sender sends a message and waits for acknowledgment, then sends the next message
• Receiver receives the message and sends an acknowledgement, then waits for the next message
– Continuous ARQ (A full duplex technique)
• Sender continues sending packets without waiting
for the receiver to acknowledge
• Receiver continues receiving messages without acknowledging them right away
27
Stop and Wait ARQ
Sender
Sends Packet A, then waits to hear from receiver.
Sends the next packet (B)
Receiver
Sends acknowledgement
Sends negative acknowledgement
Sends acknowledgement
Resends the packet again
28
Continuous ARQ
Sender sends packets continuously without waiting for receiver to acknowledge
Notice that acknowledgments now identify the packet being acknowledged.
Receiver sends back a NAK for a specific packet to be resent.
29
Flow Control with ARQ
• Ensuring that sender is not transmitting too quickly for the receiver
– Stop-and-wait ARQ
• Receiver sends an ACK or NAK when it is
ready to receive more packets – Continuous ARQ:
• Both sides agree on the size of the “sliding window”
– Number of messages that can be handled by the receiver without causing significant delays
30
Flow Control Example
window size =4
01 23 4 56 78 9
(slide window)
01 23 456 78 9
(slide window) 01 23 4 56 78 9
(slide window) 01 23 4 56 78 9
(timeout)
01 23 4 56 78 9
sender
0 12 3
ACK 0 4
ACK 4 5 67 8
ACK 7 9
98
receiver
set window size to 2
31
Forward Error Correction
• Receiving device can correct incoming messages itself (without retransmission)
• Requires extra corrective information
– Sent along with the data
– Allows data to be checked and corrected by the receiver
– Amount of extra information: usually 50-100% of the
data
• Used in the following situations:
– One way transmissions (retransmission not possible)
– Transmission times are very long (satellite)
– In this situation, relatively insignificant cost of FEC
32
Hamming Code – An FEC Example
• A scheme by adding parity bit intelligently such that one erroneous bit can be detected and corrected
• Bit position is split into ‘parity bit’ position and ‘data bit’ position:
– parity bit occupies position 1, 2, 4, 8, 16, 32, …
– data bit occupies the remaining positions (3, 5, 6, 7, 9,…) – parity bit value calculation:
• position 1 → check 1 bit, skip 1 bit, and so forth (1, 3, 5, …)
• position 2 → check 2 bits, skip 2 bits (2, 3, 6, 7, 10, 11,…)
• position 4 → check 4 bits, skip 4 bits ( 4-7, 12-15, …)
33
Hamming Code – Example
Data: 11011010 Even Parity
Position Data
P1: data at position 3, 5, 7, 9, 11 → 11111 (odd 1s) → Parity bit: 1 P2: data at position 3, 6, 7, 10, 11 → 10101 (odd 1s) → Parity bit: 1 P4: data at position 5, 6, 7, 12 →1010 (even 1s) → Parity bit: 0
P8: data at position 9, 10, 11, 12 → 1010 (even 1s) → Parity bit: 0
Data sent: 111010101010
12
3
4
567
8
9 10 11 12
11
1
0
101
0
1010
P1 P2 P4 P8
34
Hamming Code – Example
Data Received: 111010101110
Position Data
Check P1: data at position 3, 5, 7, 9, 11 → 11111 (odd 1s) → Parity bit: 1 – OK
Check P2: data at position 3, 6, 7, 10, 11 → 10111 (even 1s) → Parity bit: 0 – Not OK
Check P4: data at position 5, 6, 7, 12 →1010 (even 1s) → Parity bit: 0 – OK
Check P8: data at position 9, 10, 11, 12 → 1110 (odd 1s) → Parity bit: 1 – Not OK
Parity bit at position 2 and 8 are incorrect.
The erroneous bit is placed at bit position 2+8 = 10
12
3
4
567
8
9 10 11 12
11
1
0
101
0
1110
P1 P2 P4 P8
35
Data Link Layer
• Data Transfer
• Error Control
• Ethernets –Wired vs Wireless
36
WIRED ETHERNET
37
Ethernet
“dominant” wired LAN technology:
• cheap $20 for NIC
• first widely used LAN technology
• kept up with speed race: 10 Mbps – 10 Gbps
Metcalfe’s Ethernet sketch
38
(Wired) Ethernet
sending adapter encapsulates IP datagram (or other network layer protocol packet) in
Ethernet frame
preamble:
type
preamble
dest. address
source address
data (payload)
CRC
• 7 bytes with pattern 10101010 followed by one byte with pattern 10101011
• used to synchronize receiver, sender clock rates
39
Ethernet frame structure
❖addresses: 6 byte source, destination MAC
addresses
▪ if adapter receives frame with matching destination
address, or with broadcast address (e.g. ARP packet),
it passes data in frame to network layer protocol ▪ otherwise, adapter discards frame
❖type: indicates higher layer protocol (mostly IP but others possible, e.g., Novell IPX, AppleTalk)
❖CRC: cyclic redundancy check at receiver
▪ error detected: frame is dropped type
preamble
dest. address
source address
data (payload)
CRC
40
802.3 Ethernet standards: link & physical layers
• many different Ethernet standards
– common MAC protocol and frame format
– different speeds: 2 Mbps, 10 Mbps, 100 Mbps, 1Gbps, 10G bps
– different physical layer media: fiber, cable
100BASE-TX
100BASE-T4
MAC protocol and frame format
100BASE-T2
100BASE-SX
100BASE-FX
100BASE-BX
application
transport
network
link
physical
copper (twister pair) physical layer
fiber physical layer
41
Ethernet topology
• bus: popular through mid 90s
– all nodes in same collision domain (can collide with
each other)
• star: prevails today
– active switch in center
– each “spoke” runs a (separate) Ethernet protocol
(nodes do not collide with each other)
bus: coaxial cable
switch
star
42
Switch Operation
▪ Switches learn which MAC address is associated with an interface (physical port) by reading the source address on a frame
▪ When a new frame is received, the switch reads the destination MAC address
▪ Looks up destination address in the forwarding table
– If found, forwards frame to the corresponding interface
– If not found, broadcasts frame to all devices (like a hub)
43
Forwarding table
❖Switch-based Ethernet A
Switch Forwarding Table
MAC Port
00-22-69-13-EA-3E
1
00-22-69-13-EA-3A
2
00-22-69-13-EA-01
3
00-22-69-13-EA-6C
4
00-22-69-13-EA-3E
43
D
00-22-69-13-EA-6C
B
00-22-69-13-EA-3A
1
2
C
00-22-69-13-EA-01
44
Media Access Control (MAC)
• Carrier Sense (CS):
– A computer listens to the bus to determine if another computer is transmitting before sending anything
– Transmit when no other computer is transmitting
• Multiple Access (MA):
– All computers have access to the network medium CSMA: listen before transmit:
▪ if channel sensed idle: transmit entire frame ▪ if channel sensed busy, defer transmission
❖human analogy: don’t interrupt others!
45
CSMA/CD
CSMA/CD: carrier sensing, deferral as in CSMA
▪ collisions detected within short time
▪ colliding transmissions aborted, reducing channel
wastage
❖Collision Detection (CD):
▪ easy in wired LANs: measure signal strengths, compare transmitted, received signals
▪ difficult in wireless LANs: received signal strength overwhelmed by local transmission strength
❖human analogy: the polite conversationalist 46
WIRELESS ETHERNET
47
Wireless Ethernet
• Commonly called Wi-Fi
• A family of standards developed by IEEE
formally called 802.11
• Uses radio frequencies to transmit signals
through the air (instead of cables) • Wi-Fihasmanybenefits
– Provides network connections where cabling is impossible or undesirable
– Allows device and user mobility
– Potentially more economical than wired networks
48
802.11 Frame
• Includes four address fields
Two addresses have the same meaning as in wired Ethernet, the others are used communicating with APs and other devices
Address 1: AP Address 3: dest. MAC Address 4: used only in to receive this frame address ad hoc mode
Address 2: source MAC address
Frame Duration Address Address Address Sequence Address 2: source MAC address
Control / ID 1 2 3 Control (2 bytes) (2 bytes) (6 bytes) (6 bytes) (6 bytes) (2 bytes)
Address 4
(6 bytes)
Data (46-2312 bytes)
FCS (6 bytes)
49
Wireless Ethernet
• Components
– Access points (APs)
• Antenna type – Omnidirectional – Directional
• Association with AP
– Active vs. passive scanning
– Wireless NICs
• Topology Physical star Logical bus
50
Association with AP
BBS 1
BBS 2
BBS 1
BBS 2
AP 2 4
AP1
1112 AP2 AP1 2
passive scanning:
(1) beacon frames sent from APs (2) association Request frame sent:
H1 to selected AP
(3) association Response frame sent
from selected AP to H1
active scanning:
(1) Probe Request frame
H1
233 H1
broadcast from H1
(2) Probe Response frames sent
from APs
(3) Association Request frame
sent: H1 to selected AP
(4) Association Response frame
sent from selected AP to H1
51
WLAN Media Access Control
• Uses CSMA/CA
– CA→collisionavoidance(beforecollisionhappens)
– A station waits until another station is finished transmitting plus an additional random period (i.e. back- off timer) before sending anything
• collisions harder to detect on wireless Ethernet (‘over the air’), so more effort is put into avoidance
52
END
53