Advanced Computer
Networks
Week 3 & 4
Link layer and LANs: our goals
understand principles instantiation, implementation
behind link layer services: of various link layer
• error detection, correction technologies
• sharing a broadcast channel:
multiple access
• link layer addressing
• local area networks:
Ethernet, VLANs
datacenter networks
Link layer, LANs: roadmap
introduction
Error detection, correction
multiple access protocols
LANs
• addressing, ARP
• Ethernet
• switches
• VLANs
a day in the life of a web
link virtualization: MPLS request
data center networking
Link layer: introduction
terminology: mobile network
hosts, routers: nodes national or global ISP
communication channels that
connect adjacent nodes along
communication path: links
• wired , wireless
• LANs
layer-2 packet: frame,
encapsulates datagram datacenter
network
link layer has responsibility of
transferring datagram from one node enterprise
to physically adjacent node over a link network
Link layer: context
datagram transferred by
different link protocols over
different links:
• e.g., WiFi on first link,
Ethernet on next link
each link protocol provides
different services
• e.g., may or may not provide
reliable data transfer over link
Link layer: services
framing, link access: …
• encapsulate datagram into frame, adding …
header, trailer Cable access
• channel access if shared medium
• “MAC” addresses in frame headers identify
source, destination (different from IP
address!)
reliable delivery between adjacent nodes
cellular
• we already know how to do this!
• seldom used on low bit-error links Ethernet LANs
• wireless links: high error rates
• Q: why both link-level and end-end
WiFi
reliability?
Link layer: services (more)
…
flow control:
• pacing between adjacent sending and …
receiving nodes Cable access
error detection:
• errors caused by signal attenuation, noise.
• receiver detects errors, signals
retransmission, or drops frame
error correction: cellular
• receiver identifies and corrects bit error(s)
without retransmission Ethernet LANs
half-duplex and full-duplex:
• with half duplex, nodes at both ends of link WiFi
can transmit, but not at same time
Host link-layer implementation
in each-and-every host
link layer implemented on-chip or
in network interface card (NIC) application
transport
• implements link, physical layer network
link
cpu memory
attaches into host’s system buses host bus
(e.g., PCI)
controller
combination of hardware, link
physical
software, firmware
physical
network interface
Interfaces communicating
application application
transport transport
cpu memory memory CPU
datagram network network
link link
linkh datagram controller controller
link
datagram
link
physical physical
physical physical
sending side: receiving side:
encapsulates datagram in frame looks for errors, reliable data
adds error checking bits, reliable data transfer, flow control, etc.
transfer, flow control, etc. extracts datagram, passes to
upper layer at receiving side
Error Detection
EDC: error detection and correction bits (e.g., redundancy)
D: data protected by error checking, may include header fields
datagram datagram Error detection not 100%
otherwise reliable!
all protocol may miss
bits in D’ N
OK
?
detected
error
some errors, but rarely
d data bits larger EDC field yields
D EDC D’ EDC’ better detection and
correction
bit-error prone link
Error Detection
Parity checking
Example
Let us look at some transmission scenarios. Assume the
sender sends the dataword 1011. The codeword created
from this dataword is 10111, which is sent to the receiver.
We examine following cases:
1. No error occurs; the received codeword is 10111. The
syndrome is 0. The dataword 1011 is created.
2. One single-bit error changes a1 . The received
codeword is 10011. The syndrome is 1. No dataword
is created.
3. One single-bit error changes r0 . The received codeword
is 10110. The syndrome is 1. No dataword is created.
Hamming code C(7, 4)
The structure of the encoder and decoder for a Hamming code
Logical decision made by the correction logic analyzer
A CRC code with C(7, 4)
CRC encoder and decoder
Division in CRC encoder
Division in the CRC decoder for two cases
polynomial to represent a binary word
CRC division using polynomials
Standard polynomials
Multiple access links, protocols
two types of “links”:
point-to-point
• point-to-point link between Ethernet switch, host
• PPP for dial-up access
broadcast (shared wire or medium)
• old-school Ethernet
• upstream HFC in cable-based access network
• 802.11 wireless LAN, 4G/4G. satellite
shared wire (e.g., shared radio: 4G/5G shared radio: WiFi shared radio: satellite humans at a cocktail party
cabled Ethernet) (shared air, acoustical)
Multiple access protocols
single shared broadcast channel
two or more simultaneous transmissions by nodes: interference
• collision if node receives two or more signals at the same time
multiple access protocol
distributed algorithm that determines how nodes share channel,
i.e., determine when node can transmit
communication about channel sharing must use channel itself!
• no out-of-band channel for coordination
An ideal multiple access protocol
given: multiple access channel (MAC) of rate R bps
1. when one node wants to transmit, it can send at rate R.
2. when M nodes want to transmit, each can send at average
rate R/M
3. fully decentralized:
• no special node to coordinate transmissions
• no synchronization of clocks, slots
4. simple
MAC protocols: taxonomy
three broad classes:
channel partitioning
• divide channel into smaller “pieces”
(time slots, frequency, code)
• allocate piece to node for exclusive
use
random access
• channel not divided, allow collisions
• “recover” from collisions
“taking turns”
• nodes take turns, but nodes with
more to send can take longer turns
Channel partitioning MAC protocols: TDMA
TDMA: time division multiple access
access to channel in “rounds”
each station gets fixed length slot (length = packet transmission
time) in each round
unused slots go idle
example: 6-station LAN, 1,3,4 have packets to send, slots 2,5,6 idle
6-slot 6-slot
frame frame
1 3 4 1 3 4
Channel partitioning MAC protocols: FDMA
FDMA: frequency division multiple access
channel spectrum divided into frequency bands
each station assigned fixed frequency band
unused transmission time in frequency bands go idle
example: 6-station LAN, 1,3,4 have packet to send, frequency bands 2,5,6 idle
frequency bands
FDM cable
Random access protocols
when node has packet to send
• transmit at full channel data rate R
• no a priori coordination among nodes
two or more transmitting nodes:
“collision”
random access protocol specifies:
• how to detect collisions
• how to recover from collisions (e.g., via delayed retransmissions)
examples of random access MAC protocols:
• ALOHA, slotted ALOHA
• CSMA, CSMA/CD, CSMA/CA
Pure ALOHA
unslotted Aloha: simpler, no synchronization
• when frame first arrives: transmit immediately
collision probability increases with no synchronization:
• frame sent at t0 collides with other frames sent in [t0-1,t0+1]
will overlap will overlap
with start of with end of
i’s frame i’s frame
t0 - 1 t0 t0 + 1
pure Aloha efficiency: 18% !
Slotted ALOHA
operation:
t0 t0+1
when node obtains fresh
assumptions: frame, transmits in next slot
all frames same size • if no collision: node can send
time divided into equal size new frame in next slot
slots (time to transmit 1 frame) • if collision: node retransmits
nodes start to transmit only frame in each subsequent
slot beginning slot with probability p until
nodes are synchronized success
if 2 or more nodes transmit in
slot, all nodes detect collision
Slotted ALOHA
node 1 1 1 1 1
node 2 2 2 2
C: collision
S: success
3 3 3
node 3 E: empty
C E C S E C E S S
Pros: Cons:
single active node can collisions, wasting slots
continuously transmit at full rate idle slots
of channel
nodes may be able to detect collision in
highly decentralized: only slots in less than time to transmit packet
nodes need to be in sync
simple clock synchronization
CSMA (carrier sense multiple access)
simple CSMA: listen before transmit:
• if channel sensed idle: transmit entire frame
• if channel sensed busy: defer transmission
human analogy: don’t interrupt others!
CSMA/CD: CSMA with collision detection
• collisions detected within short time
• colliding transmissions aborted, reducing channel wastage
• collision detection easy in wired, difficult with wireless
human analogy: the polite conversationalist
“Taking turns” MAC protocols
channel partitioning MAC protocols:
share channel efficiently and fairly at high load
inefficient at low load: delay in channel access, 1/N
bandwidth allocated even if only 1 active node!
random access MAC protocols
efficient at low load: single node can fully utilize channel
high load: collision overhead
“taking turns” protocols
look for best of both worlds!
“Taking turns” MAC protocols
polling:
centralized controller “invites”
other nodes to transmit in turn data
poll
typically used with “dumb”
devices centralized
controller
concerns: data
• polling overhead
• latency
client devices
• single point of failure (master)
• Bluetooth uses polling
“Taking turns” MAC protocols
T
token passing:
control token message
explicitly passed from one node
(nothing
to next, sequentially to send)
transmit while holding token T
concerns:
• token overhead
• latency
• single point of failure
(token) data
Summary of MAC protocols
channel partitioning, by time, frequency or code
• Time Division, Frequency Division
random access (dynamic),
• ALOHA, S-ALOHA, CSMA, CSMA/CD
• carrier sensing: easy in some technologies (wire), hard in others
(wireless)
• CSMA/CD used in Ethernet
• CSMA/CA used in 802.11
taking turns
• polling from central site, token passing
• Bluetooth, FDDI, token ring
Link layer, LANs: roadmap
introduction
error detection, correction
multiple access protocols
LANs
• addressing, ARP
• Ethernet
• switches
• VLANs
a day in the life of a web
link virtualization: MPLS
request
data center networking
MAC addresses
32-bit IP address:
• network-layer address for interface
• used for layer 3 (network layer) forwarding
• e.g.: [Link]
MAC (or LAN or physical or Ethernet) address:
• function: used “locally” to get frame from one interface to another
physically-connected interface (same subnet, 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 “numeral” represents 4 bits)
MAC addresses
each interface on LAN
has unique 48-bit MAC address
has a locally unique 32-bit IP address (as we’ve seen)
[Link]
1A-2F-BB-76-09-AD
LAN
(wired or wireless)
137.196.7/24
71-65-F7-2B-08-53 58-23-D7-FA-20-B0
[Link] [Link]
0C-C4-11-6F-E3-98
[Link]
ARP: address resolution protocol
Question: how to determine interface’s MAC address, knowing its IP
address?
ARP table: each IP node (host,
ARP
router) on LAN has table
[Link]
ARP
1A-2F-BB-76-09-AD • IP/MAC address mappings for
ARP some LAN nodes:
LAN < IP address; MAC address; TTL>
71-65-F7-2B-08-53
[Link]
58-23-D7-FA-20-B0
[Link] • TTL (Time To Live): time after
ARP 0C-C4-11-6F-E3-98 which address mapping will be
[Link]
forgotten (typically 20 min)
ARP protocol in action
example: A wants to send datagram to B
• B’s MAC address not in A’s ARP table, so A uses ARP to find B’s MAC address
A broadcasts ARP query, containing B's IP addr
Ethernet frame (sent to FF-FF-FF-FF-FF-FF)
1 • destination MAC address = FF-FF-FF-FF-FF-FF
• all nodes on LAN receive ARP query C Source MAC: 71-65-F7-2B-08-53
Source IP: [Link]
ARP table in A Target IP address: [Link]
…
IP addr MAC addr TTL
TTL
A B
1
71-65-F7-2B-08-53 58-23-D7-FA-20-B0
[Link] [Link]
D
ARP protocol in action
example: A wants to send datagram to B
• B’s MAC address not in A’s ARP table, so A uses ARP to find B’s MAC address
ARP message into Ethernet frame
(sent to 71-65-F7-2B-08-53)
C Target IP address: [Link]
Target MAC address:
ARP table in A 58-23-D7-FA-20-B0
…
IP addr MAC addr TTL
TTL
A B
2
71-65-F7-2B-08-53 58-23-D7-FA-20-B0
[Link] [Link]
2 B replies to A with ARP response,
giving its MAC address
D
ARP protocol in action
example: A wants to send datagram to B
• B’s MAC address not in A’s ARP table, so A uses ARP to find B’s MAC address
C
ARP table in A
IP addr MAC addr TTL
TTL
137.196. 58-23-D7-FA-20-B0 500
A B
7.14
71-65-F7-2B-08-53 58-23-D7-FA-20-B0
[Link] [Link]
3 A receives B’s reply, adds B entry
into its local ARP table
D
Routing to another subnet: addressing
walkthrough: sending a datagram from A to B via R
focus on addressing – at IP (datagram) and MAC layer (frame) levels
assume that:
• A knows B’s IP address
• A knows IP address of first hop router, R (how?)
• A knows R’s MAC address (how?)
A B
R
[Link]
74-29-9C-E8-FF-55 [Link]
49-BD-D2-C7-56-2A
[Link]
1A-23-F9-CD-06-9B
[Link] [Link]
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B [Link]
88-B2-2F-54-1A-0F
Routing to another subnet: addressing
A creates IP datagram with IP source A, destination B
A creates link-layer frame containing A-to-B IP datagram
• R's MAC address is frame’s destination
MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B
IP src: [Link]
IP dest: [Link]
IP
Eth
Phy
A B
R
[Link]
74-29-9C-E8-FF-55 [Link]
49-BD-D2-C7-56-2A
[Link]
1A-23-F9-CD-06-9B
[Link] [Link]
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B [Link]
88-B2-2F-54-1A-0F
Routing to another subnet: addressing
frame sent from A to R
frame received at R, datagram removed, passed up to IP
MAC src: 74-29-9C-E8-FF-55
IP src: [Link]
MAC dest: E6-E9-00-17-BB-4B
IP dest: [Link]
IP src: [Link]
IP dest: [Link]
IP IP
Eth Eth
Phy Phy
A B
R
[Link]
74-29-9C-E8-FF-55 [Link]
49-BD-D2-C7-56-2A
[Link]
1A-23-F9-CD-06-9B
[Link] [Link]
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B [Link]
88-B2-2F-54-1A-0F
Routing to another subnet: addressing
R determines outgoing interface, passes datagram with IP source A, destination B
to link layer
R creates link-layer frame containing A-to-B IP datagram. Frame destination
address: B's MAC address
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
IP src: [Link]
IP dest: [Link]
IP
Eth
Phy
A B
R
[Link]
74-29-9C-E8-FF-55 [Link]
49-BD-D2-C7-56-2A
[Link]
1A-23-F9-CD-06-9B
[Link] [Link]
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B [Link]
88-B2-2F-54-1A-0F
Routing to another subnet: addressing
R determines outgoing interface, passes datagram with IP source A, destination B
to link layer
R creates link-layer frame containing A-to-B IP datagram. Frame destination
address: B's MAC address
MAC src: 1A-23-F9-CD-06-9B
transmits link-layer frame MAC dest: 49-BD-D2-C7-56-2A
IP src: [Link]
IP dest: [Link]
IP
IP Eth
Eth Phy
Phy
A B
R
[Link]
74-29-9C-E8-FF-55 [Link]
49-BD-D2-C7-56-2A
[Link]
1A-23-F9-CD-06-9B
[Link] [Link]
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B [Link]
88-B2-2F-54-1A-0F
Routing to another subnet: addressing
B receives frame, extracts IP datagram destination B
B passes datagram up protocol stack to IP
IP src: [Link]
IP dest: [Link]
IP
IP Eth
Eth Phy
Phy
A B
R
[Link]
74-29-9C-E8-FF-55 [Link]
49-BD-D2-C7-56-2A
[Link]
1A-23-F9-CD-06-9B
[Link] [Link]
CC-49-DE-D0-AB-7D E6-E9-00-17-BB-4B [Link]
88-B2-2F-54-1A-0F