Transcript notes

EEC-484/584
Computer Networks
Lecture 13
Wenbing Zhao
[email protected]
Outline



CRC
Medium Access Control (MAC)
Ethernet



Manchester Encoding
The Ethernet MAC Sublayer Protocol
The Binary Exponential Backoff Algorithm
4/10/2016
EEC-484/584: Computer Networks
Wenbing Zhao
Checksumming: Cyclic Redundancy Check




view data bits, D, as a binary number
choose r+1 bit pattern (generator), G
goal: choose r CRC bits, R, such that
 <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 (Ethernet, 802.11 WiFi)
4/10/2016
EEC484/584: Computer Networks
3
CRC Example
Want:
D.2r XOR R = nG
equivalently:
D.2r = nG XOR R
equivalently:
if we divide D.2r by
G, want remainder
R
R = remainder[
4/10/2016
D.2r
G
]
EEC484/584: Computer Networks
4
Medium Access Control
Two types of “links”:

point-to-point



PPP for dial-up access
point-to-point link between Ethernet switch and host
broadcast (shared wire or medium)


old-fashioned Ethernet
802.11 wireless LAN
shared wire (e.g.,
cabled Ethernet)
4/10/2016
shared RF
(e.g., 802.11 WiFi)
shared RF
(satellite)
EEC484/584: Computer Networks
humans at a
cocktail party
(shared air, acoustical)
5
MAC Protocols

Assumption



Single shared broadcast channel
Two or more simultaneous transmissions by nodes:
interference
Collision if node receives two or more signals at the same
time
MAC protocols


Distributed algorithm that determines how nodes share
channel, i.e., determine when node can transmit
Communication about channel sharing must use channel itself!

4/10/2016
No out-of-band channel for coordination
EEC484/584: Computer Networks
6
Ideal MAC 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
4/10/2016
EEC484/584: Computer Networks
7
MAC Protocols: a taxonomy
Three broad classes:
 Channel Partitioning



Random Access



divide channel into smaller “pieces” (time slots,
frequency, code)
allocate piece to node for exclusive use
channel not divided, allow collisions
“recover” from collisions
“Taking turns”

4/10/2016
nodes take turns, but nodes with more to send can take
longer turns
EEC484/584: Computer Networks
8
Channel Partitioning MAC protocols: 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
6-slot
frame
1
4/10/2016
3
4
1
3
EEC484/584: Computer Networks
4
9
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 pkt, frequency
bands 2,5,6 idle
FDM cable
4/10/2016
frequency bands

EEC484/584: Computer Networks
10
Random Access Protocols

When node has packet to send




two or more transmitting nodes ➜ “collision”,
random access MAC protocol specifies:



transmit at full channel data rate R.
no a priori coordination among nodes
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
4/10/2016
EEC484/584: Computer Networks
11
Pure ALOHA


pure Aloha: simple, no synchronization
when frame first arrives
transmit immediately


collision probability increases:

frame sent at t0 collides with other frames sent in [t0-1,t0+1]
4/10/2016
EEC484/584: Computer Networks
12
Pure Aloha efficiency
P(success by given node) = P(node transmits) .
P(no other node transmits in [p0-1,p0] .
P(no other node transmits in [p0,p0+1]
= p . (1-p)N-1 . (1-p)N-1
= p . (1-p)2(N-1)
… choosing optimum p and then letting n -> infty ...
= 1/(2e) = .18
4/10/2016
EEC484/584: Computer Networks
13
Slotted ALOHA
Assumptions:
 all frames same size
 time divided into equal
size slots (time to
transmit 1 frame)
 nodes start to transmit
only slot beginning
 nodes are
synchronized
 if 2 or more nodes
transmit in slot, all
nodes detect collision
4/10/2016
Operation:
 when node obtains fresh
frame, transmits in next
slot
 if no collision: node can
send new frame in next
slot
 if collision: node
retransmits frame in
each subsequent slot
with prob. p until
success
EEC484/584: Computer Networks
14
Slotted ALOHA
Pros
 single active node can
continuously transmit at
full rate of channel
 highly decentralized: only
slots in nodes need to be
in sync
 simple
4/10/2016
Cons
 collisions, wasting slots
 idle slots
 clock synchronization
EEC484/584: Computer Networks
15
Slotted Aloha efficiency
Efficiency : long-run
fraction of successful slots
(many nodes, all with many
frames to send)



suppose: N nodes with
many frames to send, each
transmits in slot with
probability p
prob that given node has
success in a slot = p(1-p)N-1
prob that any node has a
success = Np(1-p)N-1
4/10/2016


max efficiency: find p* that
maximizes
Np(1-p)N-1
for many nodes, take limit
of Np*(1-p*)N-1 as N goes
to infinity, gives:
Max efficiency = 1/e = .37
At best: channel
used for useful
transmissions 37%
of time!
EEC484/584: Computer Networks
!
16
CSMA (Carrier Sense Multiple Access)
CSMA: listen before transmit:
If channel sensed idle: transmit entire frame
 If channel sensed busy, defer transmission

human analogy: don’t interrupt others!
4/10/2016
EEC484/584: Computer Networks
17
CSMA collisions
spatial layout of nodes
collisions can still occur:
propagation delay means
two nodes may not hear
each other’s transmission
collision:
entire packet transmission
time wasted
note:
role of distance & propagation
delay in determining collision
probability
4/10/2016
EEC484/584: Computer Networks
18
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:


4/10/2016
easy in wired LANs: measure signal strengths,
compare transmitted, received signals
difficult in wireless LANs: received signal strength
overwhelmed by local transmission strength
EEC484/584: Computer Networks
19
CSMA/CD collision detection
4/10/2016
EEC484/584: Computer Networks
20
Ethernet
“dominant” wired LAN technology:
 cheap $20 for NIC
 first widely used LAN technology
 simpler, cheaper than other schemes
 kept up with speed race: 10 Mbps – 10 Gbps
Metcalfe’s Ethernet
sketch
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
application
transport
network
link
physical
MAC protocol
and frame format
100BASE-TX
100BASE-T2
100BASE-FX
100BASE-T4
100BASE-SX
100BASE-BX
copper (twister
pair) physical layer
fiber physical layer
Manchester Encoding


Binary encoding
 Hard to distinguish 0 bit (0-volt) from idle (0-volt)
 Requires clocks of all stations synchronized
Manchester encoding
 used in 10BaseT
 each bit has a transition
 allows clocks in sending and receiving nodes to
synchronize to each other

4/10/2016
no need for a centralized, global clock among nodes!
EEC-484/584: Computer Networks
Wenbing Zhao
Ethernet Frame Structure

Preamble: for clock synchronization



First 7 bytes with pattern 10101010, last byte with pattern
10101011
The two consecutive 1’s indicate the start of a frame
How can the receiver tell the end of the frame?

No current on the wire (interesting discussion at
http://www.tomshardware.com/forum/19951-42-detecting-length-ethernet-frame)
Not considered
as part of the
header!
4/10/2016
>= 64 bytes
EEC-484/584: Computer Networks
Wenbing Zhao
Ethernet Frame Structure

Destination address: 6 bytes (48 bits)
Highest order bit: 0 individual, 1 multicast;
all 1’s broadcast
 Frames received with non-matching destination address is
discarded
Type/Length: type of network layer protocol (or length of payload)
Pad – used to produce valid frame >= 64 bytes
Checksum – 32-bit cyclic redundancy check




4/10/2016
EEC-484/584: Computer Networks
Wenbing Zhao
CSMA with Collision Detection


If two stations start transmitting simultaneously, both
detect collision and stop transmitting
Monitor collision while sending


Minimum time to detect collision => minimum frame length
Time divided into slots


4/10/2016
Length of slot = 2t = worst-case round-trip propagation time
To accommodate longest path, slot time = 512 bit times = 51.2
msec (10Mbps Ethernet)
=> min frame length: 51.2 msec X 10 Mbps = 512 b = 64 byte
EEC-484/584: Computer Networks
Wenbing Zhao
Minimum Time to Detect Collision
(in worst-case scenario)

To ensure the sender can detect collision

All frames must take more than 2t to send so that transmission
is still taking place when the noise burst gets back to the sender
4/10/2016
EEC-484/584: Computer Networks
Wenbing Zhao
Ethernet MAC Sublayer Protocol

Connectionless: No handshaking between sending and
receiving NICs
 Ethernet resides in the Network Interface Card (NIC)

Unreliable: receiving NIC doesn’t send acks or nacks to

sending NIC
 stream of datagrams passed to network layer can have gaps
(missing datagrams)
 gaps will be filled if app is using TCP
 otherwise, app will see gaps
Ethernet’s MAC protocol: CSMA/CD
4/10/2016
EEC-484/584: Computer Networks
5-28
Ethernet CSMA/CD algorithm
1. NIC receives datagram from
4. If NIC detects another
network layer, creates frame
transmission while
transmitting, aborts and sends
2. If NIC senses channel idle,
jam signal
starts frame transmission If
NIC senses channel busy,
5. After aborting, NIC enters
waits until channel idle, then
exponential backoff: after
transmits
mth collision, NIC chooses K at
random from
3. If NIC transmits entire frame
{0,1,2,…,2m-1}. NIC waits K·512
without detecting another
bit times, returns to Step 2
transmission, NIC is done with
frame !
4/10/2016
EEC-484/584: Computer Networks
5-29
Randomization and
Binary Exponential Backoff






After 1st collision, station picks 0 or 1 at random, waits that
number of slots and tries again
After 2nd collision, station picks 0,1,2,3 at random, waits that
number of slots and tries again
….
After i-th collision, station picks 0,1,…,2i-1 at random, …
If 10 <= i < 16, station picks 0,1,…,210-1 at random
If i=16, controller reports failure to computer
Why randomization is needed?
4/10/2016
EEC-484/584: Computer Networks
Wenbing Zhao
Exercise

An IP packet to be transmitted by Ethernet is
60 bytes long. Is padding needed in the
Ethernet frame, and if so, how many bytes?
4/10/2016
EEC-484/584: Computer Networks
Wenbing Zhao
Exercise

Consider building a CSMA/CD network
running at 1 Gbps over a 1-km cable. The
signal speed in the cable is 200,000 km/sec.
What is the minimum frame size?
4/10/2016
EEC-484/584: Computer Networks
Wenbing Zhao