3rd Edition: Chapter 4
Computer Networking: A Top Down Approach
Copyright By PowCoder代写 加微信 powcoder
7th edition
April 2016
The Link Layer and LANs
The Powerpoint slides are from Kurose and Ross’s book’s website.
Chapter 6: Link layer and LANs
our goals:
understand principles behind link layer services:
error detection, correction
sharing a broadcast channel: multiple access
link layer addressing
local area networks: Ethernet
instantiation, implementation of various link layer technologies
Link Layer
Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request
Link Layer
Link layer: introduction
terminology:
hosts and routers: nodes
communication channels that connect adjacent nodes along communication path: links
wired links
wireless links
layer-2 packet: frame, encapsulates datagram
link layer has responsibility of
transferring datagram from one node
to physically adjacent node over a link
Link Layer
Link layer: context
datagram transferred by different link protocols over different links:
e.g., Ethernet on first link, frame relay on intermediate links, 802.11 on last link
each link protocol provides different services
e.g., may or may not provide rdt over link
Link Layer
Link layer services
framing, link access:
encapsulate datagram into frame, adding header, trailer
channel access if shared medium
“MAC” addresses used in frame headers to identify source, destination
different from IP address!
reliable delivery between adjacent nodes
seldom used on low bit-error link (fiber, some twisted pair)
may be needed for high error rate link (wireless)
Link Layer
flow control:
control transmission rate between adjacent sending and receiving nodes
error detection:
errors caused by signal attenuation, noise
receiver detects presence of errors:
signals sender for retransmission or drops frame
error correction:
receiver identifies and corrects bit error(s) without resorting to retransmission
half-duplex and full-duplex
with half duplex, nodes at both ends of link can transmit, but not at same time
Link layer services (more)
Link Layer
Where is the link layer implemented?
in every host, link layer is implemented in “adaptor” (aka network interface card NIC) or on a chip
Ethernet card, 802.11 card; Ethernet chipset
implement link, physical layer
attach to host’s system buses
combination of hardware, software, firmware
controller
(e.g., PCI)
network adapter card
application
transmission
Link Layer
Adaptors communicating
sending side:
encapsulates datagram in frame
adds error checking bits, rdt, flow control, etc.
receiving side
looks for errors, rdt, flow control, etc.
extracts datagram, passes to upper layer
controller
controller
sending host
receiving host
Link Layer
Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request
Link Layer
Error detection
EDC= Error Detection and Correction bits (redundancy)
D = Data protected by error checking, may include header fields
Error detection not 100% reliable!
protocol may miss some errors, but rarely
larger EDC field yields better detection and correction
Link Layer
Parity checking
single bit parity:
detect single bit errors
two-dimensional bit parity:
detect and correct single bit errors
parity error
Link Layer
Internet checksum (review)
treat segment contents as sequence of 16-bit integers
checksum: addition (1’s complement sum) of segment contents
sender puts checksum value into UDP checksum field
compute checksum of received segment
check if computed checksum equals checksum field value:
NO – error detected
YES – no error detected. But maybe errors nonetheless?
goal: detect “errors” (e.g., flipped bits) in transmitted packet (note: used at transport layer only)
Link Layer
Cyclic redundancy check
more powerful error-detection coding, widely used in practice (Ethernet, 802.11 WiFi)
view data bits, D, as a binary number
choose r+1 bits (generator), G
goal: choose r CRC bits, R, such that
receiver knows G, divides
can detect all burst errors less than r+1 bits
Link Layer
CRC example
D.2r XOR R = nG
equivalently:
D.2r = nG XOR R
equivalently:
if we divide D.2r by G, we want remainder R to satisfy:
R = remainder[ ]
Link Layer
Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request
Link Layer
Multiple access links
two types of “links”:
point-to-point
dial-up access
point-to-point link between Ethernet switch and host
broadcast (shared wire or wireless medium)
old-fashioned Ethernet
802.11 wireless LAN
shared wire (e.g.,
cabled Ethernet)
(e.g., 802.11 WiFi)
(satellite)
Link Layer
Multiple access protocols
multiple users share single broadcast channel
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
inbound channel for coordination (no out-of-band channel)
use channel itself for communication about how channel is shared!
Link Layer
MAC protocols
three broad classes:
channel partitioning
divide channel into smaller “pieces” (time slots, frequency, code)
allocate one piece to one node for exclusive use
random access
channel not divided, allow collisions
“recover” from collisions
“taking turns”
nodes take turns, and nodes with more to send can take longer turns
Link Layer
Channel partitioning MAC protocols: TDMA
TDMA: time division multiple access
channel time divided into fixed length slots
each station gets a slot (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
Link Layer
FDMA: frequency division multiple access
channel spectrum divided into frequency bands
each station assigned a 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
Channel partitioning MAC protocols: FDMA
Link Layer
Random access protocols
when node has packet to send
transmit at full channel data rate
no a priori coordination among nodes
two or more nodes transmitting ➜ collision
random access MAC 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
Link Layer
Pure (unslotted) ALOHA
stations access channel at will and may cause collisions when two or more stations access the channel at some overlapped time instant
simpler, no synchronization
Link Layer
Slotted ALOHA
channel time is divided into slots
stations access channel at beginning of each slot
frame transmission occupies the entire slot
if one or more other stations access the same slot, collision occurs; frame is wiped out by collision
Link Layer
CSMA (carrier sense multiple access)
CSMA: listen before transmit:
if channel sensed idle, transmit entire frame
if channel sensed busy, defer transmission
collisions can still occur:
propagation delay will cause two nodes not to hear each other’s transmission at the same time
when collision occurs, entire packet transmission time wasted
spatial layout of nodes
Link Layer
CSMA/CD (collision detection)
CSMA/CD: carrier sensing, deferral as in CSMA
collisions detected within short time
colliding transmissions aborted, reducing channel wastage
collision detection:
easy in wired LANs: measure signal strengths, compare transmitted, received signals
difficult in wireless LANs: received signal strength overwhelmed by local transmission strength
better performance than ALOHA, and simple, cheap, decentralized!
Link Layer
CSMA/CD (collision detection)
spatial layout of nodes
Link Layer
“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!
Link Layer
master node “invites” slave nodes to transmit in turn
typically used with “dumb” slave devices
polling overhead
single point of failure (master)
“Taking turns” MAC protocols
Link Layer
token ring:
control token passed from one node to next sequentially.
token overhead
single point of failure (token)
“Taking turns” MAC protocols
Link Layer
Summary of MAC protocols
channel partitioning, by time, frequency or combination
Time Division, Frequency Division
random access (dynamic)
ALOHA, Slotted-ALOHA, CSMA, CSMA/CD
carrier sensing: easy in some technologies (wire), hard in others (wireless)
CSMA/CD used in Ethernet
taking turns
polling from central site
token ring
Link Layer
Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request
Link Layer
MAC addresses
32-bit IP address:
network-layer address for interface
used for layer 3 (network layer) forwarding
MAC (or LAN or physical or Ethernet) address:
function: used ‘locally” to send frame from one interface to another physically-connected interface (same network)
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)
Link Layer
LAN addresses
each adapter on LAN has unique LAN 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
Network Layer: Data Plane
LAN addresses (more)
MAC address allocation administered by IEEE
manufacturer obtains portion of MAC address space (to assure uniqueness)
MAC flat address is portable
can move LAN card from one LAN to another
IP hierarchical address not portable
address depends on IP subnet to which node is attached
Network Layer: Data Plane
Translation of Addresses
Network Layer: Data Plane
Translation between IP addresses and MAC addresses
Address Resolution Protocol (ARP) for mapping an IP address to a MAC address
Reversed ARP (RARP) for mapping a MAC address to an IP address
IP address
MAC address
IP address
MAC address
ARP: address resolution protocol
ARP table: each 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
137.196.7.23
137.196.7.78
137.196.7.14
137.196.7.88
Network Layer: Data Plane
ARP protocol: same LAN
A wants to send datagram to B
B’s MAC address not in A’s ARP table.
A broadcasts ARP query packet, containing B’s IP address
destination MAC address =
FF-FF-FF-FF-FF-FF
all nodes on LAN receive ARP query
B receives ARP packet, replies to A with its (B’s) MAC address
frame sent to A’s MAC address (unicast)
A caches (saves) IP-to-MAC address pair in its ARP table until information becomes stale (times out)
soft state: information that times out unless refreshed
ARP is “plug-and-play”:
nodes create their ARP tables without intervention from net administrator
Network Layer: Data Plane
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 (via DCHP)
assume A knows R’s MAC address (via ARP)
Addressing: routing to another LAN
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
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
Network Layer: Data Plane
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
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
Addressing: routing to another LAN
IP src: 111.111.111.111
IP dest: 222.222.222.222
A creates IP datagram with IP source A, destination B
A creates link-layer frame with R’s MAC address as destination address, frame contains A-to-B IP datagram
MAC src: 74-29-9C-E8-FF-55
MAC dest: E6-E9-00-17-BB-4B
Network Layer: Data Plane
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
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
Addressing: routing to another LAN
frame sent from A to R
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
Network Layer: Data Plane
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
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
Addressing: routing to another LAN
IP src: 111.111.111.111
IP dest: 222.222.222.222
R forwards datagram with IP source A, destination B
R creates link-layer frame with B’s MAC address as destination address, frame contains A-to-B IP datagram
MAC src: 1A-23-F9-CD-06-9B
MAC dest: 49-BD-D2-C7-56-2A
Network Layer: Data Plane
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
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
Addressing: routing to another LAN
R forwards datagram with IP source A, destination B
R creates link-layer frame with B’s MAC address as destination address, 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
Network Layer: Data Plane
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
222.222.222.222
49-BD-D2-C7-56-2A
222.222.222.221
88-B2-2F-54-1A-0F
Addressing: routing to another LAN
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 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
Network Layer: Data Plane
Reverse Address Resolution Protocol (RARP)
RARP can find a machine’s logical address by using its physical address
an RARP request messages is created and broadcast on the local network
broadcasting is done at data link layer
broadcast request does not pass the boundaries of a network
the machine on the local network that knows the logical address will respond with an RARP reply
Network Layer: Data Plane
RARP: request and reply
Network Layer: Data Plane
Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request
Link Layer
“dominant” wired LAN technology:
single chip, multiple speeds (e.g., Broadcom BCM5761)
first widely used LAN technology
simpler, cheap
kept up with speed race: 10 Mbps – 10 ’s Ethernet sketch
Link Layer
Ethernet: physical 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 link runs a (separate) Ethernet protocol (nodes do not collide with each other)
bus: coaxial cable
Link Layer
Ethernet frame structure
sending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet frame
7 bytes with pattern 10101010 followed by one byte with pattern 10101011
used to synchronize receiver, sender clock rates
Link Layer
Ethernet frame structure (more)
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., PX, AppleTalk)
CRC: cyclic redundancy check at receiver
error detected: frame is dropped
Link Layer
Ethernet: unreliable, connectionless
connectionless: no handshaking between sending and receiving NICs
unreliable: receiving NIC doesn’t 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
Ethernet’s MAC protocol: unslotted CSMA/CD with binary backoff
Link Layer
Ethernet CSMA/CD algorithm
1. NIC receives datagram from network layer, creates frame
2. If NIC senses channel idle, starts frame transmission. If NIC senses channel busy, waits until channel idle, then transmits.
3. If NIC transmits entire frame without detecting another transmission, NIC is done with frame !
4. If NIC detects another transmission while transmitting, aborts
5. After aborting, NIC enters binary (exponential) backoff:
after mth collision, NIC chooses K at random from {0,1,2, …, 2m-1}. NIC waits K·512 bit times, returns to Step 2
longer backoff interval with more collisions
Link Layer
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, 10 Gbps, 40 Gbps
different physical layer media: fiber, cable
application
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
Link layer, LANs: outline
6.1 introduction, services
6.2 error detection, correction
6.3 multiple access protocols
addressing, ARP and RARP
6.5 a day in the life of a web request
Link Layer
Ethernet switch
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 those links, uses CSMA/CD to access links
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com