Transcript ECE544 - WINLAB

ECE544: Communication Networks-II
Spring 2013
D. Raychaudhuri
Lecture II
Includes teaching materials from L. Peterson, J. Kurose
Today’s Lecture
• Recap of network architecture & topdown design
– architecture paper discussion
• Shared media (MAC) protocols
– Ethernet
– Token ring
– IEEE 802.11
Link Layer: Introduction
• Some terminology:
– hub/repeater (layer 1), bridge/LAN switch (layer 2), router
(layer 3), host (layers 1-3 + app)
– Links are communication channels that connect adjacent nodes
along communication path (point-to-point, shared, wired,
wireless)
– Layer-2 frame: encapsulates payload/datagram/IP
packet/service unit
LAN 1
LAN 2
Link
Lin
k
Host
Switch
Switch
Link
Router
Host
Link Layer Services
• Data-link layer: transfer datagram from one
node to adjacent node over a link
– Framing: encapsulate datagram into frame, adding
header, trailer.
• Identify what set of bits constitute a frame, that is,
determining the beginning and the end of a frame
– channel access if shared medium
• MAC addresses used in frame headers to identify source,
destination
• different from IP address!
– Reliable delivery between adjacent nodes
• Error detection
• Error recovery: forward error correction code, retransmission
(ARQ)
Link Layer Communication
•
•
•
Link layer implemented in adaptor (NIC) and driver (Ethernet card,
WLAN card)
Sending side: encapsulates higher layer payload in a frame, adds error
checking bits, flow control, etc.
Receiving side: error detection, flow control, extracts payload, passes
to the receiving node
Link layer protocol
Sending Datagram
node
Datagram
Frame
Frame
Adaptor
Adaptor
Host
CPU
Control status
register
Cache
Memory
I/O
bus
Bus
interface
NIC
Link Network
interface
Recv
node
Layer 2 vs. Layer 3
• Layer 2 switching
– Based on MAC address
– Self configuring and
plug & play
– Transparent to
protocols above the
MAC layer
– Fast and inexpensive
– Does not limit the
scope of broadcasts
– Does not scale to
extremely large
networks
• Layer 3 routing
– Based on IP address
– Must get IP address
(DHCP or manual assign)
– Easily connect LANs that
uses different link
protocols
– Scalable to large network
by subnet routing
– Broadcast limited only in
a subnet
• Link Layer Techniques
– Encoding (more Physical Layer stuff)
– Framing & PPP Protocol
– Error Detection & Correction
– ARQ
• Self study topics (see Ch2 & slides)
Binary Encoding
• Binary Encoding: turn the binary data (bits) into
signals to transmit on cable or optical fiber link
(physical layer stuff, but better to know)
• Baseband, not modulate to high frequency
• Nonreturn To Zero (NRZ): 1=high signal, 0=low
signal
– May stay on high or low signal too long for a long strings of
consecutive 1s or 0s => baseline wander, clock recovery
problems.
• Nonreturn to Zero Inverted (NRZI): 1 = signal
transition (low to high, or high to low), 0=no change.
– Solve the problem of consecutive 1s, but not consecutive 0s
Manchester Encoding
•
Manchester Encoding: NRZ_encode data XOR clock
– Clock cycle (a low/high pair) = 2 x signal interval
– Baud rate (the signal change rate) = 2 x bitrate
– 0 =high-to-low transition, 1 = low-to-high transition
– Clock recovery
•
Variation: Differential Manchester
– 1 = the first half of the signal equal to the last half of the previous bit’s
signal
– 0 = the first half of the signal opposite to the last half of the previous bit’s
signal
Bits
NRZ
Clock
Manchester
NRZI
0
0
1
0
1
1
1
1
0
1
0
0
Point-to-Point Data Link Protocol
• Two types of links
– point-to-point link (easier than broadcast link)
• one sender, one receiver on the link, NO Media Access
Control
• no need for explicit MAC addressing
• e.g., dialup link, ISDN line
– Broadcast (shared wire or medium)
• popular point-to-point DLC protocols:
– PPP (point-to-point protocol): byte-oriented
• PPP for dial-up access
• PPP over Ethernet (DSL)
– HDLC (High level data link control): bit-oriented
Modem
PPP
PPP Functions
• Framing: encapsulation of network-layer datagram in data link
frame
– Identify what set of bits constitute a frame, that is,
determining the beginning and the end of a frame
• carry data of any network layer protocol (not just IP) at same
time
– ability to demultiplex upwards
• bit transparency: must carry any bit pattern in the data field
• error detection (no correction)
• connection liveness: detect, signal link failure to network
layer
• network layer address negotiation: endpoint can
learn/configure each other’s network address
• PPP
–
–
–
–
no error correction/recovery
no flow control
out of order delivery OK
no need to support multipoint links (e.g., polling)
PPP Data Frame
•
•
•
•
•
•
Flag: delimiter (framing)
Address:
Control:
Protocol: upper layer protocol to which frame carried (e.g. IP)
Info: upper layer data
Check: CRC
Octet: 1
1
1
1 or 2
protocol
01111110
11111111
00000011
flag
address
control
variable
info
2 or 4
CRC
1
01111110
Byte Stuff
• “data transparency”requirement: data field
must be allowed to include flag pattern
<01111110>
– Q: is received <01111110> data or flag?
• Sender: adds (“stuffs”) extra < 01111110>
byte after each < 01111110> data byte
• Receiver:
– two 01111110 bytes in a row: discard first byte,
continue data reception
– single 01111110: flag byte
PPP Link Control Protocol (LCP)
• Before exchanging network-layer data,
data link peers must
– configure PPP link (max. frame length,
authentication)
• learn/configure network
– layer information
– for IP: carry IP Control Protocol (IPCP)
msgs (protocol field: 8021) to
configure/learn IP address
High-Level Data Link Control (HDLC)
• Bit oriented protocol: view the frame as a collection of bits,
does not care byte boundaries.
• Sentinel characters 01111110 transmitted as the link is idle for
synchronization
• Bit stuffing: to distinguish the data pattern 01111110 in the
body from the special “beginning/end” sequence
– after transmitting any 5 consecutive 1s in body, insert a 0
– 011111xxxx => 0111110xxx
Bits: 8
01111110
Beginning
sequence
16
Header
variable
body
16
CRC
8
01111110
ending
sequence
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
Parity Checking
• Single Bit Parity:
– Detect single bit
errors
• Two Dimensional Bit Parity:
– Detect and correct single
bit error
Internet Checksum
• Goal: detect “errors” (e.g., flipped bits) in
transmitted segment (note: used at transport layer)
Sender:
• treat segment contents
as sequence of 16-bit
integers
• checksum: addition (1’s
complement sum) of
segment contents, and
take the ones
complement of the
result
• sender puts checksum
value into UDP
checksum field
Receiver:
• compute checksum of
received segment
• check if computed
checksum equals
checksum field value:
– NO -error detected
– YES -no error detected.
But maybe errors
(internet checksum not
very strong for error
detection, but simple)
Cyclic Redundancy Check (CRC)
• A (n+1)-bit message M can be represented as a polynomial of
degree n. For example,
– X = 10011010;
– M(X) = X7 + X4 + X3 + X
• Choose k+1 bit pattern (divisor), C(X), a polyn of degree k
• goal: get k CRC bits, Y, such that
– P=<M,Y> exactly divisible by C (modulo 2)
– receiver knows C, divides <M,Y> by C. If non-zero
remainder: error detected!
– can detect all burst errors less than k+1 bits
n bits
M: data bits to be sent
M x 2k XOR R
k bits
Y: CRC
CRC Example
• Goal: design P(X) such that it is
exactly divisible by C(X)
•
T(X) = M(X) Xk (add k zero’s to
the end of the message)
R  rem ainder[
•
T(X )
]
C( X )
Subtract the remainder from T(X) to get P(X).
– P(X) is now exactly divisible by C(X).
• Corresponding to the complete
transmitted message
(Remember – all addition/subtract use modulo-2
arithmetic)
Automatic Repeat reQuest(ARQ)
•
Stop-and-wait ARQ
•
Go-back-N ARQ
•
Selective-repeat
– Transmit a frame and wait for acknowledge
– If positive acknowledge (ACK) from receiver, send next frame
– If ACK does not arrive after a certain period of time (Timeout), retransmits the
frame
– Simple, low efficiency
–
–
–
–
Transmit frames continuously, no waiting
The receiver only acks the highest-numbered frames received in sequence
ACK comes back after a round-trip delay
If timeout, the sender retransmits the frames that are not acked and N-1
succeeding frames that were transmitted during the round-trip delay (N frames
transmitted during a round-trip delay)
– Need buffer at transmitter, does not have to buffer the frames at the receiver,
– moderate efficiency and complexity. Less efficient when the round-trip delay is
large and data transmission rate is high
–
–
–
–
Transmit continuously, no waiting
The receiver acks all successfully received frames
The sender only retransmits (repeats) the unacked frames when their timers expire
Most efficient, but most complex, buffer needed at both transmitter and receiver,
need per frame timer
Sliding Window
• Reliable delivery: retransmission
• Ordered delivery: preserve the order in which
the frames are transmitted
– Receiver does not pass along (buffer) out-of-order
frames
• Flow control: feedback mechanism by which
the receiver is able to throttle the sender
– Inform the sender of how much frames the
receiver has room to receive
Sliding Window (Cont)
• Send window size (SWS): the upper bound on the
number of unacked frames that the sender can
transmit,
– set according to the round-trip delay to keep the pipe full
(recall: bandwidth x delay product represents the amount of
data that could be in transit)
• LAR: the sequence # of the last ack received
• LFS: the sequence # of the last frame sent
• Receiver window size (RWS): the upper bound on the
number of out-of-order frames that the receiver is
willing to accept
• LAF: the sequence # of the largest acceptable frame
• LFR: the sequence # of the last frame received
• SeqNumToAck: the largest sequence # not yet acked,
such that all frames with seq # <= SeqnumToAck
have been received
Sliding Window
LAR
1
Sender
LFS
SWS
2
3
4
5
Ack 1
1
Receiver
LFR
2
6
7
Error
4
9
3
Ack 2
Ack 2
3
8
5
RWS
6
4
5
8
9
7
8
9
10 11 12
Ack 4 Ack 5
Ack 2 Ack 3
Ack 6
Ack 2
7
6
3
4
5
6
7
8
9
10 11 12
LAF
SeqNumToAck
• LFS-LAR<=SWS, LAF-LFR<=RWS
• Finite Seq. # wraps around:
– SWS < (MaxSeqNum+1)/2 when RWS=SWS to distinguish
between different incarnations of the same seq. #
Shared Media Networks
• MAC (medium access control)
–
–
–
–
–
ALOHA, Slotted ALOHA
CSMA/CD, CSMA/CA
Token Ring
TDMA, Dynamic TDMA
FDMA, CDMA
• LAN Technologies
– IEEE 802.3 Ethernet
– IEEE 802.5 Token Ring
– IEEE 802.11 Wireless LAN
Medium Access Sublayer
End host
Application
Presentation
Applications
Session
Transport
TCP/UDP
Network
IP
Data link
Physical
LLC
MAC
Subnet
Physical
• Medium access control (MAC)
sublayer is not relevant on
point-to-point links
• The MAC sublayer is only used
in broadcast or shared
medium/channel networks
• All communication entities
“share” a common channel
– Wired networks: Ethernet LAN
– Wireless & Mobile Networks:
Satellite, Cellular, Wireless LAN,
Media Access Protocol
• Shared broadcast channel
– two or more simultaneous transmissions by nodes:
interference
• Collision if node receives two or more signals at the same time
• MAC protocol
– Determines how nodes share channel, i.e., determine when
node can transmit
• Ideally, if broadcast channel of rate R bps
– When one node wants to transmit, it can send at rate R.
– When M nodes want to transmit, each can send at average
rate R/M (fairness)
MAC Classification
• Channel Partitioning
– divide channel into smaller “pieces” (time slots, frequency, code)
– allocate piece to node for exclusive use
• TDMA, CDMA, FDMA
• Random Access
– channel not divided
• When node has frame to send, transmit with the total channel bandwidth
– No coordination between nodes, control is completely distributed
– two or more nodes transmit simultaneously ➜“collision”
– random access MAC protocol should specify:
• how to detect collisions
• how to recover from collisions (e.g., via delayed retransmissions)
• Examples: ALOHA, Slotted ALOHA, CSMA/CD, CSMA/CA
• “Taking turns”
– Nodes take turns
• Token ring
• Hybrid
– Combine two or more techniques together
Pure (Unslotted) ALOHA
•
Early packet radio network created at
the U. of Hawaii in 1970
•
Uplink channel (clients->hub) and
downlink channel (hub->clients) uses
different frequencies
•
Client nodes send data frames to the
central hub using the shared uplink
channel.
•
The hub immediately re-send the
received frames, allowing clients to
determine whether or not their data
had been received properly.
• Simplest form of random access,
provides basis for more advance
contention MAC
Hub
Client
•
•
Aloha Algorithm
Aloha Algorithm:
– Nodes transmit immediately whenever they have a frame to send
– No synchronization among nodes
• If collision, retransmit after random delay
– random delay prevents the same frames from colliding
over and over again
collision window or “vulnerable period”:
– frame sent at t0 collides with other frames sent in [t0-1,t0+1]
Pure Aloha efficiency
•
Assume that the aggregate frame arrival is Poisson Process
e GG k
k!
•
P [k arrivals in a time-interval] =
•
G: the mean number of aggregate arrivals (all nodes in network) in the
time interval
•
time-interval = one frame transmission time
•
Conditional successful probability for one frame transmission attempt is
–
•
P0 = P [0 other attempts in 2 time-intervals] =e-2G
The probability of successful transmission
– S = GP0 = Ge-2G
•
S is optimum at G=1/2
•
S=1/2e = 0.184
Slotted Aloha
•
Assumptions
– all frames same size
– time is divided into equal size slots,
time to transmit 1 frame
– nodes start to transmit frames only
at beginning of slots
– nodes are synchronized
– if 2 or more nodes transmit in slot,
detect collision
– Feedback channel about whether
packet is received or not (halfduplex)
•
Operation
–
–
–
when node obtains fresh frame,
it transmits at the beginning of
next slot
no collision, node can send new
frame in next slot
if collision, wait a random
number of slots and try to send
again
Efficiency of Slotted ALOHA
•
Aggregate frame arrival is Poisson Process
e GG k
k!
•
P [k arrivals in a time-interval] =
•
G: the mean number of aggregate arrivals (for all nodes in network) in this
interval
•
time-interval = slot (one frame transmission time)
•
Successful probability for each slot is :
S= P [1 attempt in a slot] =Ge-G
• S is optimum at G=1
• S=1/e = 0.368
(slotted aloha reduce the potential collision period from 2t to t by node
synchronization)
Performance of ALOHA
• Throughput versus offered traffic for ALOHA systems
• The main reason for poor channel utilization of ALOHA (pure or
slotted) is that all stations can transmit at will, without paying
attention to what the other stations are doing.
Carrier Sense Multiple Access (CSMA)
• CSMA: listen before transmit:
– If channel sensed idle: transmit
– If channel sensed busy, defer transmission
• Human analogy: don’t interrupt others!
• Can collisions occur in this scheme?
– Two nodes might attempt to transmit a frame at the same time
– Propagation delay means two nodes may not hear each other’s
transmission immediately
• Several variants of CSMA protocols:
– Non-Persistent CSMA
– 1-Persistent CSMA
– P-Persistent CSMA
Non-persistent CSMA
•
•
•
To send data, a node first listens to the channel to
see if anyone else is transmitting.
If so, the node waits a random period of time
(instead of keeping sensing until the end of the
transmission) and repeats the algorithm. Otherwise,
it transmits a frame.
If a collision occurs, the node waits a random
amount of time and starts all over again.
1-persistent CSMA
Algorithm:
1. To send data, a node first listens to the channel to see if anyone else is
transmitting.
2. If so, the node waits (keeps sensing it) until the channel becomes idle.
Otherwise, it transmits a frame.
3. If a collision occurs, the node waits a random amount of time and starts
all over again.

It is called 1-persistent because the station transmits with a
probability of 1 whenever it starts sensing the channel and finds
the channel idle. (Greedy)
P-persistent CSMA
•
•
Assume channels are slotted
One slot = contention period (i.e., one round trip propagation
delay)
Algorithm:
1.
Sense the channel
–
–
–
2.
If channel is idle, transmit a packet with probability p
•
if a packet was transmitted, go to step 2
•
if a packet was not transmitted, wait one slot and go to step 1
If channel is busy, wait one slot and go to step 1.
In other words, wait until idle and then transmit with probability p
Detect collisions
–
If a collision occurs, wait a random amount of time and go to step 1
Propagation Delay
A
B
C
D
• D only sense A’s transmission after a propagation
delay τ
• If τ is larger than packet transmission time, too
much time wasted.
• CSMA in satellite communication? No.
• Distance & propagation delay determine collision
probability
The size (length) of the network must be limited!
CSMA Performance Analysis
• Assumptions
– Constant length packets
– No errors, except those caused by collisions
– Collision: entire packet transmission time
wasted
– Each host can sense the transmissions of all
other hosts
– The propagation delay is small compared to the
transmission time
Analysis of Non-persistent CSMA
Unsuccessful
transmission
period
Successful
transmission
period
Normalized Time
a
Y
a
1
Idle period
1
Busy period
a
Busy period
• Poisson arrival, P(k arrivals in time duration t) =
•
•
•
•
Prob. of success transmission S= U x I/(B+I)
Mean B = Y + 1 + a , mean I = 1/G
U = Ge-Ga
FY(y)=P{no packet occur in an duration of a-y }
= e-G(a-y) (CDF)
E (Y )  a 
1
(1  e  aG )
G
a: the ratio of
propagation
delay to packet
transmission
time
eGt G kt
k!
Ge aG
S
G(1  2a)  e aG
Comparison of the channel utilization versus load for
various random access protocols
CSMA with Collision Detection
CSMA/CD (Carrier Sense Multiple Access with Collision
Detection) protocol further improves ALOHA by aborting
transmissions as soon as a collision is detected.
Operation:
•
To send data, a node first listens to the channel to see if
anyone else is transmitting.
•
If not, it transmits a frame
•
If channel busy, deferral as in CSMA
–
•
the node wait a random period of time and repeats the algorithm
(non-persistent), or waits until the end of the transmission (1persistent)
The node will detect the collision, if collision detected, abort its
transmission (reducing channel wastage), waits a random
amount of time, and starts all over again.
How to Detect Collision
• Prerequisite: A node can listen while talking
• Easy in wired LANs: measure signal
strength, compare Tx and Rx signals
• Difficult in wireless LANs: receiver shut off
while transmitting
Tx
Rx
CSMA/CA
• Wireless LANs
• How can a node detect collision if it cannot listen while talking?
• Collision Avoidance
– Random Backoff (instead of 1-persistent)
– Request-to-send (RTS)/clear-to-send (CTS)
• CS no longer works well
– Rules:
• carrier
==> do not transmit
• no carrier ==> OK to transmit
– But the above rules do not always apply to wireless.
Problems with carrier sensing
Hidden terminal problem
Z
Y
W
W finds that medium is free
and it transmits a packet to Z
no carrier ===>
/ OK to transmit
Problems with carrier sensing
Exposed terminal problem
W
Z is transmitting
to W
Z
X
Y
Y will not transmit to X
even though it cannot interfere
Presence of carrier ===>
/ hold off transmission
Solving Hidden Node problem with RTS/CTS
- listen RTS
- wait long enough
for the requested
station to respond
with CTS
- if (timeout) then
ready to transmit
CTS
RTS
Z
X
Y
W
- listen CTS
- wait long enough
for the transmitter
to send its data
listen RTS ==> transmitter is close
listen CTS ==> receiver is close
Note: RTS/CTS does not solve exposed terminal problem. In the example above,
X can send RTS, but CTS from the responder will collide with Y’s data.
RTS/CTS exchange example
SIFS
DIFS
Frame
RTS
Transmitter
Receiver
352
304
µs 10 µs
µs
Other
ACK
CTS
8192 s
10
µs
304
10 µs
µs
NAV (RTS)
NAV (CTS)
•
•
RTS + CTS + Frame + ACK exchange invoked when frame size is
large
NAV (Network Allocation Vector)
– NAV maintains prediction of future traffic on the medium based
on duration information that is announced in RTS/CTS frames
prior to actual exchange of data
“Taking Turns” MAC protocols
Token passing:
Polling:
• control token passed from one
• master node
node to next sequentially.
“invites” slave
nodes to transmit • token message
in turn
• concerns:
• concerns:
– token overhead
– polling overhead
– complexity
– single point of
– single point of failure (token)
failure (master)
TDMA
• Time Division Multiple Access (TDMA)
Fixed TDMA
• access to channel in "rounds"
• each station gets fixed length slot (length = packet
transmission time) in each round
• unused slots go idle – Not efficient
• example: 6-station LAN, 1,3,4 have pkt, slots 2,5,6
idle
Dynamic TDMA
• In dynamic TDMA, a scheduling algorithm dynamically
reserves a variable number of timeslots in each frame to
variable user data streams, based on the traffic demand of each
user data stream.
• Negotiations (beforehand) to determine how to allocate slots
dynamically.
TDD-TDMA Frame
TDM Downlink
D-TDMA Uplink
Modem
preamble
S-ALOHA
control
Burst from Access Point -> Mobiles
Burst from User A
To Access Point
Frame header and schedule
User B
User C
FDMA
Frequency bands
• FDMA: frequency division multiple access
– channel spectrum divided into frequency bands
– each station assigned a frequency band
• unused transmission time in frequency bands go idle if
assignment fixed
– Inefficient => make it dynamically assigned to different
stations based on traffic demand
– OFDMA
Spread Spectrum and CDMA
•
What if we don’y not divide up the channel by time (as in TDMA), or
frequency (as in FDMA)? Is collision inevitable?
•
Not if collision is no longer damaging!
– Is there any way to decode bits garbled by other overlapping
frames?
Code Division Multiple Access (CDMA) based on Spread Spectrum
•
Another perspective to solve multiple access problems
•
Spread Spectrum is a PHY innovation, not a MAC technique.
•
CDMA encodes data with a special code associated with each user and
uses the constructive interference properties of the special codes to
perform the multiplexing.
Spread Spectrum
• Idea
– spread signal over wider frequency band than
required
– originally deigned to thwart jamming
• Frequency Hopping
– transmit over random sequence of frequencies
– sender and receiver share…
• pseudorandom number generator
• seed
Spread Spectrum (cont)
• Direct Sequence
– for each bit, send XOR of that bit and n
random bits
– random sequence known to both sender and
receiver
– called n-bit chipping code
1
0
Data stream: 1010
1
0
Random sequence: 0100101101011001
1
0
XOR of the two: 1011101110101001
Code Division Multiple Access (CDMA)
• Multiplexing Technique used with spread spectrum
• Start with data signal rate D
– Called bit data rate
• Break each bit into k chips according to fixed pattern
specific to each user
– User’s code
• New channel has chip data rate kD chips per second
• E.g. k=6, three users (A,B,C) communicating with
base station R
• Code for A = <1,-1,-1,1,-1,1>
• Code for B = <1,1,-1,-1,1,1>
• Code for C = <1,1,-1,1,1,-1>
LAN technologies
Ethernet
Token Ring
Wireless LAN
Ethernet Overview
•
•
•
•
History
– developed by Xerox PARC in mid-1970s
– roots in Aloha packet-radio network
– standardized by Xerox, DEC, and Intel in 1978
– similar to IEEE 802.3 standard
CSMA/CD
Evolution: Bus topology (90’s)  Star topology (now)
Most successful access network technology
Hub or switch
Advance
Ethernet Frame
•
•
Preamble: 8 bytes
– 7 bytes with pattern 10101010 followed by one byte with pattern
10101011
– used to synchronize receiver, sender clock rates
Addresses:6 bytes
– if adapter receives frame with matching destination address, or
with broadcast address, it passes data in frame to net-layer
protocol, otherwise, adapter discards frame
Type: 2 bytes
•
CRC: 4 bytes
•
Body: 46-1500 bytes
•
– indicates the higher layer protocol (mostly IP but others also supported)
– checked at receiver, if error is detected, the frame is simply dropped
– Sending adapter encapsulates IP datagram (or other network layer protocol
packet) in Ethernet frame
Octets
8
6
6
2
Preamble
Dest
addr
Src
addr
Type
64-1518
72-1526
46-1500
Body
4
CRC
MAC Address
• MAC Addresses
– unique, 48-bit unicast address assigned to each adapter
• example: 38:10:2b:e4:b1:02
– broadcast: all 1s, ff:ff:ff:ff:ff:ff
– multicast: multicast flag (the lowest bit of the 1st octet)= 1
• 01-00-5E-00-00-00 to 01-00-5E-7F-FF-FF for IP multicast
– IP multicast group address mapped to the lower order 23
bits of MAC address (not one-to-one mapping)
– Unique MAC address allocation administered by IEEE
• manufacturer buys portion of MAC address space
• the first three octets as vendor-specific
MAC Address vs. IP Address
• 48-bit MAC address
– Layer 2
– Used to get packet from
one interface to another
within the same
LAN/subnet (Ethernet,
token ring…)
– Flat
– Unique
– No change when moving
• 32-bit IP address
– Network layer
– Used to get packet to
destination IP subnet
– Hierarchical
– Change when moving
• Depending on IP subnet to
which node is attached
• IP to MAC address translation: ARP (more later)
Different Flavors of Ethernet Format
•
Ethernet version II
Octets
8
6
2
Src
Dest
Type
MAC
MAC
Data link header
Preamble
•
8
Preamble
6
6
Dest
MAC
Src
MAC
Datalink Header
•
•
•
•
Body
2
1
1
Length DSAP SSAP
4
FCS
Data & CRC (FCS)
IEEE 802.3
Octets
•
46-1500
6
1
Control
Logical Link Control
43-1497
Body
4
FCS
Data & CRC (FCS)
Length: the length of the data in the frame (excluding preamble, CRC, DLC
addresses, and the Length field itself)
Destination Service Access Point (DSAP): a pointer to a memory buffer in the
receiving station. It tells the receiving NIC in which buffer to put this information.
useful in situations where users are running multiple protocol stacks, etc...
Source Service Access Point (SSAP)
Control: the type of LLC frame
Distinguish Ethertypes and Control field
– Ethertypes value > 0x05DC (1500), Length <= 1500
Unreliable, connectionless service
• Connectionless: No handshaking
between sending and receiving adapter.
• Unreliable: receiving adapter doesn’t
send acks or nacks to sending adapter
– stream of datagrams passed to network
layer can have gaps
– gaps will be filled if app is using TCP
– otherwise, app will see the gaps
Ethernet CSMA/CD
1. If sender senses channel idle, it starts to transmit
frame. If it senses channel busy, waits until channel
idle and then transmits (1-persistent CSMA)
•
Inter-frame gap: time to send 96 bits (9.6 s for 10Mbps)
2. If adapter transmits entire frame without detecting
another transmission, the adapter is done with
frame !
3. If adapter detects another transmission while
transmitting, aborts and sends 32-bit jam signal
(collision detection)
4. After aborting, sender enters exponential backoff
– after the mth collision, adapter chooses a K at random from
{0,1,2,…,2m-1}. Then waits K·512 bit times (k x 51.2 us in
10 Mbps Ethernet) and returns to Step 1
– give up after several tries (usually 16)
Ethernet CSMA/CD (Cont)
Exponential Backoff:
Jam Signal:
• Goal: adapt retransmission
• make sure all other
attempts to the estimated
transmitters are aware of
current # of active stations or
collision;
load
• 32 bits
– heavy load: random wait will be
• Frame: 64 (preamble) + 32
longer
(jamming sequence) = 96 bits • first collision: choose K from
– Runt Frame
{0,1}; delay is K·512 bit (51.2 s
in 10 Mbps) transmission times
• after second collision: choose K
from {0,1,2,3}…
• after ten collisions, choose K
from {0,1,2,3,4,…,1023}
Collisions
A
B
A
B
A
B
A
B
The longer the propagation delay,
the higher probability of collision.
Worst case:
• A sends at t, A’s frame arrives B
at t+d
• B begins transmitting at t+d
and collides with A’s frame
• B sends runt frame, the runt
frame arrives A at t+2d
• To detect collision, A must
continue transmit until t+2d. A
must transmit for 2d.
• Round-trip delay about 51.2 us
for 2500m long Ethernet with 4
repeater
– Corresponds to 512 bits for 10
Mbps Ethernet
– So min frame size 512 bits
10BaseT and 100BaseT
•
•
•
•
10/100 Mbps rate; latter called “fast ethernet”
T stands for Twisted Pair
Star toplogy, max 100m between node and hub
Hubs: physical-layer repeaters
– bits coming from one link go out all other links at the same
rate
– no frame buffering
– no CSMA/CD at hub: adapters detect collisions
– provides net management functionality
Hub
Legacy Ethernet
•
10Base5
•
10Base2
–
–
–
–
–
Bus topology with coaxial cable
10 Mbps, Up to 500m each segment
No more than 4 repeaters between any pair of stations
Max 2500 m
Max 1024 hosts
– Daisy chain
– Up to 200m
Repeater
Terminator
Terminator
Transceiver
Adaptor
10 Base5 Ethernet
Gbit Ethernet
• uses standard Ethernet frame format
• allows for point-to-point links and shared
broadcast channels
• in shared mode, CSMA/CD is used; short
distances between nodes required for
efficiency
• uses hubs
• Full-Duplex at 1 Gbps for point-to-point links
• 10 Gbps now
Ethernet Performance
• Max throughput <1 as a function of span
– As propagation delay increases, efficiency decreases
– instability can occur unless load is reduced under congestion
conditions
– retransmission backoff policy for stability
~0.8
Thru
stable policy
(retx backoff)
Capacity Limit
Traffic
margin
Overload
region
unstable policy
(no backoff)
load lines
Normal operating
point
stable policy
(backoff too high)
Offered Traffic
Wireless LANs
• 802.11 a/b/g different Phy technologies
– 802.11 b/g: 20 MHz channel in 2.4 GHz, up to 11
Mbps (802.11b), 54 Mbps (802.11g) phy data rate
– 802.11a: 20 MHz channel in 5GHz, up to 54 Mbps
phy data rate
• 802.11n:
– 130 Mbps phy data rate on 20 MHz channel (2 x
2 MIMO)
– 300 Mbps phy data rate on 40 MHz channel
(channel bonding with 2 x 2 MIMO)
See supplementary WLAN tutorial slides
Today’s Homework
• Peterson & Davie, Chap 2, 4th ed
2.6
2.18
2.23
2.33
2.44
2.42
Download and review Ethernet and 802.11 MAC specs,
and study IEEE 802.11 Wireless LAN Overview slides
Due 2/8
74