Link Layer
All material copyright 1996-2012
J.F Kurose and K.W. Ross, All Rights Reserved
George Parisis
School of Engineering and Informatics
University of Sussex
Link Layer 5-2
Outline
v introduction, services
v error detection, correction
v multiple access protocols
v LANs
§ addressing, ARP
§ Ethernet
§ switches
Link Layer 5-3
MAC addresses and ARP
v 32-bit IP address:
§ network-layer address for interface
§ used for layer 3 (network layer) forwarding
v MAC (or LAN or physical or Ethernet) address:
§ function: used ‘locally” to get frame from one interface
to another physically-connected interface (same
network, in IP-addressing sense)
§ 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)
Link Layer 5-4
LAN addresses and ARP
each adapter on LAN has unique LAN address
adapter
1A-2F-BB-76-09-AD
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
71-65-F7-2B-08-53
LAN
(wired or
wireless)
Link Layer 5-5
LAN addresses (more)
v MAC address allocation administered by
IEEE
v manufacturer buys portion of MAC address
space (to assure uniqueness)
v MAC flat address ➜ portability
§ can move LAN card from one LAN to another
v IP hierarchical address not portable
§ address depends on IP subnet to which node is
attached
Link Layer 5-6
ARP: address resolution protocol
ARP table: each IP node
(host, router) on LAN has
table
§ IP/MAC address
mappings for some
LAN nodes:
< IP address; MAC address;
TTL>
§ TTL (Time To Live):
time after which
address mapping will
be forgotten (typically
20 min)
Question: how to determine
interface’s MAC address,
knowing its IP address?
1A-2F-BB-76-09-AD
58-23-D7-FA-20-B0
0C-C4-11-6F-E3-98
71-65-F7-2B-08-53
LAN
137.196.7.23
137.196.7.78
137.196.7.14
137.196.7.88
Link Layer 5-7
ARP protocol: same LAN
v A wants to send datagram to B
§ B’s MAC address not in A’s ARP table.
v A broadcasts ARP query packet, containing B’s IP address
§ dest MAC address = FF-FF-FF-FF-FF-FF
§ all nodes on LAN receive ARP query
v B receives ARP packet, replies to A with its (B’s) MAC
address
§ frame sent to A’s MAC address (unicast)
v A caches (saves) IP-to-MAC address pair in its ARP table
until information becomes old (times out)
§ soft state: information that times out (goes away) unless refreshed
v ARP is “plug-and-play”:
§ nodes create their ARP tables without intervention from net
administrator
Link Layer 5-8
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 (how?)
§ assume A knows R’s MAC address (how?)
Addressing: routing to another
LAN
R
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55
A
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
B
R
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55
A
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
B
Link Layer 5-9
Addressing: routing to another
LAN
IP
Eth
Phy
IP src: 111.111.111.111
IP dest: 222.222.222.222
v A creates IP datagram with IP source A, destination B
v 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
R
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55
A
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
B
Link Layer 5-10
Addressing: routing to another
LAN
IP
Eth
Phy
v frame sent from A to R
IP
Eth
Phy
v frame received at R, datagram removed, passed up to IP
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 src: 111.111.111.111
IP dest: 222.222.222.222
R
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55
A
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
B
Link Layer 5-11
Addressing: routing to another
LAN
IP src: 111.111.111.111
IP dest: 222.222.222.222
v R forwards datagram with IP source A, destination B
v 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
Eth
Phy
IP
Eth
Phy
R
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55
A
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
B
Link Layer 5-12
Addressing: routing to another
LAN
v R forwards datagram with IP source A, destination B
v R creates link-layer frame with B’s MAC address as dest, frame
contains A-to-B IP datagram
IP src: 111.111.111.111
IP dest: 222.222.222.222
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP
Eth
Phy
IP
Eth
Phy
R
1A-23-F9-CD-06-9B
222.222.222.220
111.111.111.110
E6-E9-00-17-BB-4B CC-49-DE-D0-AB-7D
111.111.111.112
111.111.111.111
74-29-9C-E8-FF-55
A
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
B
Link Layer 5-13
Addressing: routing to another
LAN
v R forwards datagram with IP source A, destination B
v R creates link-layer frame with B’s MAC address as dest, frame
contains A-to-B IP datagram
IP src: 111.111.111.111
IP dest: 222.222.222.222
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP
Eth
Phy
Link Layer 5-14
Outline
v introduction, services
v error detection, correction
v multiple access protocols
v LANs
§ addressing, ARP
§ Ethernet
§ switches
Link Layer 5-15
Ethernet
“dominant” wired LAN technology:
v cheap $20 for NIC
v first widely used LAN technology
v simpler, cheaper than token LANs and ATM
v kept up with speed race: 10 Mbps – 10 Gbps
Metcalfe’s Ethernet sketch
Link Layer 5-16
Ethernet: physical topology
v bus: popular through mid 90s
§ all nodes in same collision domain (can collide with
each other)
v star: prevails today
§ active switch in center
§ each link runs a (separate) Ethernet protocol (nodes
do not collide with each other)
switch
bus: coaxial cable
star
Data Link Layer 5-17
Ethernet: physical topology
Link Layer 5-18
Ethernet frame structure
sending adapter encapsulates IP datagram (or
other network layer protocol packet) in
Ethernet frame
preamble:
v 7 bytes with pattern 10101010 followed by
one byte with pattern 10101011
v used to synchronize receiver, sender clock
rates
dest.
address
source
address
data
(payload) CRC preamble
type
Link Layer 5-19
Ethernet frame structure (more)
v 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
v type: indicates higher layer protocol (mostly IP
but others possible, e.g., Novell IPX, AppleTalk)
v CRC: cyclic redundancy check at receiver
§ error detected: frame is dropped
dest.
address
source
address
data
(payload) CRC preamble
type
Link Layer 5-20
Ethernet: unreliable, connectionless
v connectionless: no handshaking between
sending and receiving NICs
v unreliable: receiving NIC doesnt send acks or
nacks to sending NIC
§ data in dropped frames recovered only if initial
sender uses higher layer rdt (e.g., TCP),
otherwise dropped data lost
v Ethernet’s MAC protocol: unslotted CSMA/CD
with binary backoff
Link Layer 5-21
802.3 Ethernet standards: link & physical
layers
v 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
application
transport
network
link
physical
MAC protocol
and frame format
100BASE-TX
100BASE-T4
100BASE-FX 100BASE-T2
100BASE-SX 100BASE-BX
fiber physical layer copper (twister
pair) physical layer
Link Layer 5-22
Outline
v introduction, services
v error detection, correction
v multiple access protocols
v LANs
§ addressing, ARP
§ Ethernet
§ switches
Link Layer 5-23
Ethernet switch
v link-layer device: takes an active role
§ store, forward Ethernet frames
§ examine incoming frame’s MAC address,
selectively forward frame to one-or-more
outgoing links when frame is to be forwarded
on segment, uses CSMA/CD to access
segment
v transparent
§ hosts are unaware of presence of switches
v plug-and-play, self-learning
§ switches do not need to be configured
Link Layer 5-24
Switch: multiple simultaneous
transmissions
v hosts have dedicated, direct
connection to switch
v switches buffer packets
v Ethernet protocol used on
each incoming link, but no
collisions; full duplex
§ each link is its own
collision domain
v switching: A-to-A’ and B-to-
B’ can transmit
simultaneously, without
collisions
switch with six interfaces
(1,2,3,4,5,6)
A
A’
B
B’ C
C’
1 2
3 4 5
6
Link Layer 5-25
Switch forwarding table
Q: how does switch know A’
reachable via interface 4, B’
reachable via interface 5?
switch with six interfaces
(1,2,3,4,5,6)
A
A’
B
B’ C
C’
1 2
3 4 5
6 v A: each switch has a switch
table, each entry:
§ (MAC address of host, interface
to reach host, time stamp)
§ looks like a routing table!
Q: how are entries created,
maintained in switch table?
§ something like a routing
protocol?
A
A’
B
B’ C
C’
1 2
3 4 5
6
Link Layer 5-26
Switch: self-learning
v switch learns which
hosts can be reached
through which interfaces
§ when frame received,
switch “learns”
location of sender:
incoming LAN
segment
§ records sender/
location pair in switch
table
A A’
Source: A
Dest: A’
MAC addr interface TTL
Switch table
(initially empty)
A 1 60
Link Layer 5-27
Switch: frame filtering/forwarding
when frame received at switch:
1. record incoming link, MAC address of sending host
2. index switch table using MAC destination address
3. if entry found for destination
then {
if destination on segment from which frame arrived
then drop frame
else forward frame on interface indicated by
entry
}
else flood /* forward on all interfaces except
arriving
interface */
A
A’
B
B’ C
C’
1 2
3 4 5
6
Link Layer 5-28
Self-learning, forwarding: example
A A’
Source: A
Dest: A’
MAC addr interface TTL
switch table
(initially empty)
A 1 60
A A’ A A’ A A’ A A’ A A’
v frame destination, A’,
locaton unknown: flood
A’ A
v destination A location
known:
A’ 4 60
selectively
send
on just one link
Link Layer 5-29
Interconnecting switches
v switches can be connected together
Q: sending from A to G – how does S1 know to
forward frame destined to F via S4 and S3?
v A: self learning! (works exactly the same as in
single-switch case!)
A
B
S1
C D
E
F
S2
S4
S3
H
I
G
Link Layer 5-30
Institutional network
to external
network
router
IP subnet
mail server
web server
Link Layer 5-31
Switches vs. routers
both are store-and-forward:
§ routers: network-layer
devices (examine network-
layer headers)
§ switches: link-layer
devices (examine link-layer
headers)
both have forwarding
tables:
§ routers: compute tables
using routing algorithms, IP
addresses
§ switches: learn forwarding
table using flooding,
learning, MAC addresses
application
transport
network
link
physical
network
link
physical
link
physical
switch
datagram
application
transport
network
link
physical
frame
frame
frame
datagram
Link Layer 5-32
Summary
v principles behind data link layer services:
§ error detection, correction
§ sharing a broadcast channel: multiple access
§ link layer addressing
v instantiation and implementation of various link
layer technologies
§ Ethernet
§ switched LANs