Transcript Link Layer

17:
Link Layer, Multiple Access
Protocols, ARP
Last Modified:
4/10/2016 1:15:29 AM
5: DataLink Layer
5a-1
Data Link Layer
Goals:
Overview:
 understand principles
 link layer services
behind data link layer
services:



sharing a broadcast
channel: multiple access
link layer addressing
error detection,
correction
 instantiation and
implementation of various
link layer technologies
 error detection, correction
 multiple access protocols and
LANs
 link layer addressing, ARP
 specific link layer technologies:



Ethernet: hubs, bridges,
switches
IEEE 802.11 Wireless LANs
Others: PPP< ATM, X.25,etc.
data-link layer has responsibility of
transferring datagram from one node
to physically adjacent node over a link
5: DataLink Layer
5a-2
Link Layer: setting the context
 two physically connected devices or nodes:
 host-router, router-router, host-host
 unit of data: frame
M
Ht M
Hn Ht M
Hl Hn Ht M
application
transport
network
link
physical
data link
protocol
phys. link
adapter card
network
link
physical
Hl Hn Ht M
frame
5: DataLink Layer
5a-3
Link Layer: Implementation
 Typically, implemented in “adapter” or or
network interface card (NIC)



e.g., PCMCIA card, Ethernet card
Hardware, software, firmware
typically includes: RAM, DSP chips, host system
bus interface, and link interface
M
Ht M
Hn Ht M
Hl Hn Ht M
application
transport
network
link
physical
data link
protocol
phys. link
adapter card
network
link
physical
Hl Hn Ht M
frame
5: DataLink Layer
5a-4
Adaptors Communicating
datagram
datagram
controller
controller
receiving host
sending host
datagram
frame
 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 at receiving
side
Data Link Layer
5-5
Link Layer Services
 Framing, link access:
 encapsulate datagram into frame, adding header, trailer
 implement channel access if shared medium,
 ‘physical addresses’ used in frame headers to identify
source, dest
• different from IP address!
 Reliable delivery between two physically connected
devices:



we learned how to do reliable delivery over an unreliable
link
seldom used on low bit error link (fiber, some twisted
pair)
wireless links: high error rates
• Q: why both link-level and end-end reliability?
5: DataLink Layer
5a-6
Link Layer Services (more)
 Flow Control:

pacing between sender and receivers
 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,
5: DataLink Layer
but not at same time
5a-7
Link Layer
 Node-to-node connectivity
 Point-to-point or multiple access
 Multiple access requires addressing
 Both require rules for sharing the links
 Examples:
Point-to-point (single wire, e.g. PPP, SLIP)
 Broadcast (shared wire or medium; e.g,
Ethernet or wireless)
 Switched (e.g., switched Ethernet, ATM etc)

5: DataLink Layer
5a-8
Communication Technologies
 Wired LANs, Wireless LANs (RF or light),
Cellular Telephones, Satellites, Packet
Radio, Wired Telephone, Voice
5: DataLink Layer
5a-9
Basics of Link Layer
 Multiple Access Protocols
 Error Detection/Correction
5: DataLink Layer 5a-10
Multiple Access
 Multiple Access - fundamental to
communication
 Two or more communicators use a shared
medium to share information
 Multiple Access Protocol - Rule for sharing
medium to facilitate communication?

Can simultaneous transmissions cause
interference?
 Claim: humans use multiple access protocols
all the time
5: DataLink Layer 5a-11
Multiple Access protocols
 Algorithm that determines how stations share channel,
i.e., determine when station can transmit
 Note: communication about channel sharing must use
channel itself! (or be agreed upon ahead of time)
 what to look for in multiple access protocols:
 synchronous or asynchronous
 information needed about other stations
 robustness (e.g., to channel errors)
 performance
5: DataLink Layer 5a-12
Ideal Multiple Access Protocol
Broadcast channel 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
Data Link Layer
5-13
Realistic MAC Protocols: a taxonomy
Three broad classes:
 Channel Partitioning


divide channel into smaller “pieces” (time slots,
frequency)
allocate piece to node for exclusive use
 Random Access
 allow
collisions
 “recover” from collisions
 Polling Style

tightly coordinate shared access to avoid collisions
Goal: efficient, fair, simple, decentralized
5: DataLink Layer 5a-14
Channel Partitioning : TDMA
TDMA: time division multiple access
 access to channel in "rounds"
 each station gets fixed length slot (length = pkt
trans time) in each round
 unused slots go idle
 example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6
idle
5: DataLink Layer 5a-15
Channel Partitioning : 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 pkt, frequency
frequency bands
bands 2,5,6 idle
5: DataLink Layer 5a-16
Channel Partitioning: CDMA
CDMA (Code Division Multiple Access)
 unique “code” assigned to each user; ie, code set partitioning
 used mostly in wireless broadcast channels (cellular,
satellite,etc)
 all users share same frequency, but each user has own
“chipping” sequence (ie, code) to encode data
 encoded signal = (original data) X (chipping sequence)


For each code there is a spreading factor G
For d bits of user data, G*d bits are trannsmitted
 decoding: inner-product of encoded signal and chipping
sequence
 allows multiple users to “coexist” and transmit
simultaneously with minimal interference (if codes are
“orthogonal”)
5: DataLink Layer 5a-17
Can’t Cheat Nature
 TDMA – all channel part of time
 FDMA – part of channel all the time
 CDMA – use all the channel all the time
BUT transmit more bits (spread-out) in a
specified pattern that avoids interference
with others
5: DataLink Layer 5a-18
TDMA vs FDMA vs CDMA
 In TDMA, each station gets the whole channel
spectrum some of the time
 In FDMA, each station gets part of the channel
spectrum all of the time
 In CDMA, each station is assigned a code that
determines what portions of the channel spectrum
they use and for how long to avoid collision with
others
 All require lots of coordination about who “speaks”
when and in what way!

What if didn’t want to coordinate things so tightly?
5: DataLink Layer 5a-19
Random Access protocols
 Random access protocols are alternative to
tight coordination
When want to transmit, transmit and hope for
the best
 If bad things happen, protocol says how to
recover

5: DataLink Layer 5a-20
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 MAC protocol specifies:
 how to detect collisions
 how to recover from collisions (e.g., via delayed
retransmissions)
 Examples of random access MAC protocols:
 slotted ALOHA
 ALOHA
 CSMA and CSMA/CD (Ethernet)
 Remember Ethernet grew out of technology for
broadcast in Hawaiian Islands?
5: DataLink Layer 5a-21
Random Access: Slotted Aloha
 time is divided into equal size slots (= pkt trans. time)
 node with new arriving pkt: transmit at beginning of
next slot
 if collision: retransmit pkt in future slots with
probability p, until successful.
Success (S), Collision (C), Empty (E) slots
5: DataLink Layer 5a-22
Slotted Aloha efficiency
Q: what is max fraction slots successful?
A: Suppose N stations have packets to send
 each transmits in slot with probability p
 prob. successful transmission S is:
by single node:
S= (prob it sends) * (prob all others do not)
= p (1-p)(N-1)
by any of N nodes
S = Prob (only one transmits)
= N p (1-p)(N-1)
… choosing optimum p as n -> infty ...
= 1/e = .37 as N -> infty
At best: channel
use for useful
transmissions 37%
of time!
5: DataLink Layer 5a-23
Random Access: Pure
(unslotted) ALOHA
 unslotted Aloha: simpler, no synchronization
 pkt needs transmission:
 send without awaiting for beginning of slot
 collision probability increases:
 pkt sent at t0 collide with other pkts sent in [t0-1, t0+1]
5: DataLink Layer 5a-24
Pure Aloha (cont.)
P(success by given node) = P(node transmits) .
P(no other node transmits in [p0-1,p0] .
P(no other node transmits in [p0-1,p0]
= p . (1-p) . (1-p)
P(success by any of N nodes) = N p . (1-p) . (1-p)
… choosing optimum p as n -> infty ...
= 1/(2e) = .18
0.4
0.3
Slotted Aloha
0.2
0.1
protocol constrains
effective channel
throughput!
Pure Aloha
0.5
1.0
1.5
2.0
G = offered load = Np
5: DataLink Layer 5a-25
CSMA: Carrier Sense Multiple Access
CSMA: listen before transmit:
 If channel sensed idle: transmit entire pkt
 If channel sensed busy, defer transmission
 Persistent CSMA: retry immediately with
probability p when channel becomes idle (may cause
instability)
 Non-persistent CSMA: retry after random interval
 human analogy: don’t interrupt others!
5: DataLink Layer 5a-26
CSMA collisions
spatial layout of nodes along ethernet
collisions can occur:
propagation delay means
two nodes may not year
hear each other’s
transmission
collision:
entire packet transmission
time wasted
note:
role of distance and
propagation delay in
determining collision prob.
5: DataLink Layer 5a-27
CSMA/CD (Collision Detection)
CSMA/CD: carrier sensing, deferral as in CSMA



collisions detected within short time
colliding transmissions aborted, reducing channel wastage
persistent or non-persistent retransmission
 collision detection:
 easy in wired LANs: measure signal strengths, compare
transmitted, received signals
 difficult in wireless LANs: receiver shut off while
transmitting
 human analogy: if start talking at same time some one
else does don’t just continue talking
5: DataLink Layer 5a-28
CSMA/CD collision detection
5: DataLink Layer 5a-29
Compromise? Polling Style MAC
protocols
channel partitioning MAC protocols:
 share channel efficiently 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
Polling style protocols (“taking turns”)
look for best of both worlds!
5: DataLink Layer 5a-30
Polling style MAC protocols
Polling:
 master node
“invites” slave nodes
to transmit in turn
 Request to Send,
Clear to Send msgs
 concerns:



polling overhead
latency
single point of
failure (master)
Token passing:
 control token passed from
one node to next
sequentially.
 token message
 concerns:



token overhead
latency
single point of failure (token)
5: DataLink Layer 5a-31
Reservation-based protocols
Distributed Polling:
 time divided into slots
 begins with N short reservation slots
reservation slot time equal to channel end-end propagation
delay
 station with message to send posts reservation
 reservation seen by all stations
 after reservation slots, message transmissions ordered by

known priority
5: DataLink Layer 5a-32
Basics of Link Layer
 Multiple Access Protocols
 Error Detection/Correction
5: DataLink Layer 5a-33
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
5: DataLink Layer 5a-34
Smart Redundancy
 In general, more bits of redundancy the
stronger the error detection/correction
abilities but smart redundancy
 What if transmitted another copy of the
same thing?

How many bits till not detected? Ability to
correct?
 Can we do better than that with less
space?
5: DataLink Layer 5a-35
Recall: Internet checksum
We saw this a bunch of times in upper layers – is this
a good choice for the link layer?
Sender:
 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
Receiver:
 compute checksum of received segment
 check if computed checksum equals checksum field value
5: DataLink Layer 5a-36
Intelligent choice for link
layer?
 Tailored to type and frequency of errors
expected in the specific technology being
used
Some technologies (like fiber) have very low
error rates
 Some technologies (like wireless) have high
error rates

 How to we tailor the number of bits to use
and *how* we use them to get the desired
effect??
5: DataLink Layer 5a-37
Example: Parity
Single Bit vs Two Dimensional Two Dimensional Bit Parity:
Detect and correct single bit errors
Bit Parity: Example of using
Want even number of 1’s in each dimension
redundant bits intelligently
for increased
error detection/correction
capability!
Single Bit Parity:
Detect single bit errors
0
0
5: DataLink Layer 5a-38
Beyond parity?
 How can we generalize this example of
single vs double bit parity?
 Is there a theory of using redundant bits
efficiently based on the types of errors we
expect to find?
 Cyclic Redundancy Checks (CRC) views both
the data and the redundant bits as binary
polynomials and ensures that they satisfy a
certain mathematical relationship
5: DataLink Layer 5a-39
Checksumming: Cyclic Redundancy Check
 view data bits, D, as a binary number or binary polynomial

101011= X^5+X^3+X^1+X^0 = X^5+X^3+X+1.
 choose r+1 bit pattern/polynomial (generator), G
 goal: choose r CRC bits, R, such that




<D, R> = D* 2r XOR R (shift D over place R in the end)
<D,R> exactly divisible by G (modulo 2)
receiver knows G, divides <D,R> by G. If non-zero remainder:
error detected!
can detect all burst errors less than r+1 bits
 widely used in practice (ATM, HDCL)
5: DataLink Layer 5a-40
CRC Example
Want:
D.2r XOR R = nG
equivalently:
if we divide D.2r
by G, want
reminder R
R = remainder[
D.2r
G
]
5: DataLink Layer 5a-41
 CRCs are simple to implement in binary
hardware
 Produce fixed sized output (or Frame
check sequence, FCS)
 Can be analyzed mathematically in a
consistent way
 Can be tailored to catch burst errors of
particular lengths etc
5: DataLink Layer 5a-42
Common CRC Polynomials (G)
 CRC-1: x+1 will do common parity
 2 bit generator gives 1 bit output
 CRC-12 used for transmission of streams of 6-bit
characters and generates 12-bit FCS

CRC-12: X^12+X^11+X^3+X^2+X+1
 Both CRC-16 and CCRC-CCITT are used for 8 bit
transmission streams and both result in 16 bit
FCS. Considered to give adequate protection for
most applications.


CRC-16: X^16+X^15+X^2+1 (USA)
CRC-CCITT: X^16+X^12+X^5+1 (Europe)
 CRC-32 gives extra generates 32 bit FCS. Used by
the local network standards committee (IEEE-802
– e.g. Ethernet) and in some DOD applications.

CRC-32:
X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X
5: DataLink Layer
^7+X^5+X^4+X^2+X+1
5a-43
LAN Addresses
Each adapter on LAN has unique LAN address
5: DataLink Layer 5a-44
LAN Addresses vs IP
Addresses
32-bit IP address (128 bit IPv6):
 network-layer address
 used to get datagram to destination network
(recall IP network definition)
LAN (or MAC or physical) address:
 used to get datagram from one interface to
another physically-connected interface (same
network)
 48 bit MAC address (for most LANs)
burned in the adapter ROM
5: DataLink Layer 5a-45
LAN Address vs IP Addresses
(more)
 MAC address allocation administered by IEEE
 manufacturer buys portion of MAC address space
(to assure uniqueness)
 Analogy:
(a) MAC address: like Social Security Number
(b) IP address: like postal address
 MAC flat address => portability

can move LAN card from one LAN to another
 IP hierarchical address NOT portable
 depends on network to which one attaches
5: DataLink Layer 5a-46
Recall earlier routing discussion
Starting at A, given IP
datagram addressed to B:
A
223.1.1.1
223.1.2.1
 look up net. address of B, find B
on same net. as A
 link layer send datagram to B
inside link-layer frame
frame source,
dest address
B’s MAC A’s MAC
addr
addr
223.1.1.2
223.1.1.4 223.1.2.9
B
223.1.1.3
datagram source,
dest address
A’s IP
addr
B’s IP
addr
223.1.3.27
223.1.3.1
223.1.2.2
E
223.1.3.2
IP payload
datagram
frame
5: DataLink Layer 5a-47
Question:
How can we determine the
MAC address of B
given B’s IP address?
5: DataLink Layer 5a-48
ARP: Address Resolution Protocol
 Each IP node (Host,
Router) on LAN has
ARP module, table
 ARP 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)
5: DataLink Layer 5a-49
ARP protocol
 A knows B's IP address, wants to learn physical




address of B
A broadcasts ARP query pkt, containing B's IP
address
 Special broadcast address FF:FF:FF:FF:FF:FF
 all machines on LAN receive ARP query
B receives ARP packet, replies to A with its (B's)
physical layer address
A caches (saves) IP-to-physical address pairs until
information becomes old (times out)
 soft state: information that times out (goes
away) unless refreshed
Plug-and-play much like switch table
5: DataLink Layer 5a-50
Hands-on: arp
 arp ipaddress

Return the MAC address associated with the
given IP address
 arp –a
 List
the contents of the local ARP cache
 arp –s hostname macAddress
 Used by the system administrator to add a
specific entry to the local ARP cache
5: DataLink Layer 5a-51
Routing to another LAN
walkthrough: routing from A to B via R
A
R
B
 In routing table at source Host, find router
111.111.111.110
 In ARP table at source, find MAC address E6-E900-17-BB-4B, etc
5: DataLink Layer
5a-52
 A creates IP packet with source A, destination B
 A uses ARP to get R’s physical layer address for 111.111.111.110
 A creates Ethernet frame with R's physical address as dest,





Ethernet frame contains A-to-B IP datagram
A’s data link layer sends Ethernet frame
R’s data link layer receives Ethernet frame
R removes IP datagram from Ethernet frame, sees its
destined to B
R uses ARP to get B’s physical layer address
R creates frame containing A-to-B IP datagram sends to B
A
R
B
5: DataLink Layer 5a-53
LAN technologies
Data link layer so far:

services, error detection/correction, multiple
access
Next: LAN technologies
Ethernet
 hubs, bridges, switches
 802.11
 PPP
 ATM

5: DataLink Layer 5a-54
Outtakes
5: DataLink Layer 5a-55
Reed Solomon codes
 Non-binary CRCs
 Used in CDs/DVDs/Blueray, some data
transmission standards, storage arrays like
RAID
 Cyclic BCH codes
5: DataLink Layer 5a-56
 Add t check symbols to detect any
combination of up to t erroneous symbols,
and correct up to t/2 symbols.
 Erasure code - can correct up to t known
erasures, or it can detect and correct
combinations of errors and erasures.
 Multiple-burst bit-error correcting codes,

a sequence of b + 1 consecutive bit errors can
affect at most two symbols of size b
 Designer of code selects t or b according
to expected errors in application domain
5: DataLink Layer
5a-57
Summary of MAC protocols
 What do you do with a shared media?

Channel Partitioning, by time, frequency or code
• Time Division,Code Division, Frequency Division

Random access
• ALOHA, S-ALOHA, CSMA, CSMA/CD
• carrier sensing: easy in some technologies (wire), hard
in others (wireless)
• CSMA/CD used in Ethernet

Polling Style
• polling from a central cite, token passing
5: DataLink Layer 5a-58