Transcript ch4

Computer Networks
Chapter 4
Medium Access Control Sublayer
Medium Access Control Sublayer
Chapter 4
• Channel Allocation Problem
• Multiple Access Protocols
• Ethernet
• Wireless LANs
• Broadband Wireless
• Bluetooth
• RFID
• Data Link Layer Switching
Revised: August 2011
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
TheProblem
• Network Links
• Point to point
• Broadcast
• Broadcast channels are called
• Multiaccess channels
• Random access Channels
• In a broadcast network, the key issue is how to determine who
gets to use the channel when there is competition for it.
• Protocols to determine who gets access belong to the MAC
sublayer
The MAC Sublayer
Responsible for deciding who sends next on a
multi-access link
• An important part of the link layer, especially
for LANs
MAC is in here!
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Application
Transport
Network
Link
Physical
Channel Allocation Problem (1)
How to allocate a single broadcast channel among competing users.
Static allocation: divide capacity among users
For fixed channel and traffic from N users ( each gets 1/N)
• Divide up bandwidth using FDM, TDM, CSMA, etc.
• This is a static allocation, e.g., FM radio
Works for small number of users with steady demand
This static allocation performs poorly for bursty traffic
• Allocation to a user will sometimes go unused
• Some denied access even if bandwidth is available, but assigned to others
Most channels are idle most of the time
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Channel Allocation Problem (2)
Dynamic allocation gives the channel to a user when they need it.
Potentially N times as efficient for N users.
Schemes vary with assumptions:
Assumption
Implication
Independent traffic
N independent stations ( computer, phone)
Often not a good model, but permits analysis
Single channel
All stations transmit on same channel
No external way to coordinate senders ( can assign priorities)
Observable
collisions
If two frames transmit, collision occurs- back off try again
Needed for reliability; mechanisms vary (eg. CDMA)
Continuous or
slotted time
Slotting may improve performance- contains 0 or more frames
(idle, successful or collision)
Carrier sense
Can improve performance if available
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Channel Allocation Problem
• Some assumptions were made:
• Frame arrivals are independent and at a constant rate
• In reality, not good model of network traffic (based on quequeing theory and
Poisson Distributions)
• Single challenge – no way to communicate
• Collision assumption- stations need a way to detect collisions
• Wired channels – hardware can detect collisions
• Wireless more difficult to detect
• Slotted time assumes a master clock- not always available
• Networks may or may not have carrier sense- wireless can’t always use
it- out of range
Poisson Distribution
• Simple queueing theory example: ( See p.259)
• Average time delay (T) to send a frame onto a channel of capacity
C bps.
• Assume a random average arrival rate of λ frames/sec and that
frames vary in length with an average length of 1/μ bits.
• The service rate of the channel is μC frames/sec
• According to queueing theory the delay is
T = 1/( μC – λ)
http://en.wikipedia.org/wiki/Poisson_distribution
Poisson Distribution
• When λ is small, the range of likely
possibilities is near 0.
• As λ gets larger, the probability of
zero occurrences becomes unlikely
• The “hump” is the likelihood of
the occurrence of a certain value
• http://www.umass.edu/wsp/resources/poisson/
Number of occurrences
Multiple Access Protocols
• ALOHA »
• CSMA (Carrier Sense Multiple Access) »
• Collision-free protocols »
• Limited-contention protocols »
• Wireless LAN protocols »
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
ALOHA
• 1970’s in University of Hawaii – connect users on remote islands
• String cables in Pacific Ocean not feasible
• Used short-range radios
• Users shared upstream frequency to send frames to central computer
• Two versions
• Pure – time continuous
• Slotted divided into discrete slots into which all frames must fit
• Basic idea – let users transmit whenever they have data to be sent. If
there are collisions handle them – called a contention system
ALOHA -Random Access Protocols
ALOHAnet
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
12
ALOHA Random Access Protocols
• The ALOHA protocol is straightforward:
• when a station has a packet to send
• it transmits the packet on the inbound frequency
• the central transmitter repeats the transmission on the outbound frequency (which all
stations can receive)
• To insure that transmission is successful
• a sending station listens to the outbound channel
• if a copy of its packet arrives, the sending station moves to the next packet
• if no copy arrives, the sending station waits a short time and tries again
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
13
Pure ALOHA
In pure ALOHA, users transmit frames whenever they have data;
users retry after a random time for collisions
• Efficient and low-delay under low load
`
User
A
B
C
D
E
Collision
Time
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Collision
ALOHA
• Why might a packet fail to arrive? Interference
• if two stations simultaneously transmit
• the signals will interfere and the two transmissions will be garbled
• called a collision, and say that the two transmitted packets collide
• The protocol handles a collision
• by requiring a sender to retransmit each lost packet
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
15
ALOHA
• When two frames try to occupy the same channel there is a collision
• In a collision frames are damaged and destroyed
• Senders need a way to detect other transmissions
• If frame is destroyed, sender waits a random time and rebroadcasts
• Referred to as exponential backoff -doubling the wait time after each
failure
• Frames do not collide if no other frames are sent within one frame
time of its start
• When will a frame arrive undamaged? P0 =probability of 0 collisions
• For G frames and S throughput S = GP0 ( about 18% efficient)
Pure ALOHA
Collisions happen when other users transmit during a vulnerable
period that is twice the frame time
• Synchronizing senders to slots can reduce collisions
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Slotted ALOHA
Slotted ALOHA is twice as efficient as pure ALOHA
• Low load wastes slots, high loads causes collisions
• Efficiency up to 1/e (37%) for random traffic models
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
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
Cons
• collisions, wasting slots
• idle slots
• nodes may be able to detect collision
in less than time to transmit packet
• clock synchronization
Data Link Layer
5-19
Slotted ALOHA
• The probability that there is no other traffic during a time slot is e-G,
where G is the number of packet attempts per unit time.
• Slotted ALOHA peaks at G= 1, with a throughput of S= 1/e or about
37%, which is twice that of pure ALOHA.
• Optimal is 37% empty slots, 37% successful transmissions and 26%
collisions.
• Operating at higher values of G reduces the number of empties, but
increases the number of collisions exponentially.
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, IBM Token Ring
Data Link Layer
5-21
CSMA - Ethernet
• Researchers at Xerox PARC created a random access protocol (1973)
• In 1978, a standard (also called the DIX standard) was created
• by Digital Equipment Corporation, Intel, and Xerox
• It is widely known as Ethernet
• It uses cable as a shared medium
• instead of broadcasting radio frequency transmissions through the
atmosphere
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
22
Classic Ethernet
• Bob Metcalfe and David Boggs developed
the Ethernet protocol
Classic Ethernet
“dominant” wired LAN technology:
• cheap $20 for NIC
• first widely used LAN technology
• simpler, cheaper than token LANs and ATM
• kept up with speed race: 10 Mbps – 10 Gbps
Metcalfe’s Ethernet
sketch
Data Link Layer
5-24
Ethernet -Star topology
• bus topology popular through mid 90s
• all nodes in same collision domain (can collide with each other)
• today: star topology prevails
• active switch in center
• each “spoke” runs a (separate) Ethernet protocol (nodes do not collide with each other)
switch
bus: coaxial cable
star
Data Link Layer
5-25
Ethernet Frame Structure
Sending adapter encapsulates IP datagram (or other network layer protocol packet)
in Ethernet frame
Preamble:
• 7 bytes with pattern 10101010 followed by one byte with pattern 10101011
• used to synchronize receiver, sender clock rates
Data Link Layer
5-26
Ethernet Frame Structure (more)
• Addresses: 6 bytes
• 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., Novell
IPX, AppleTalk)
• CRC: checked at receiver, if error is detected, frame is dropped
Data Link Layer
5-27
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
Data Link Layer
fiber physical layer
5-28
CSMA - Ethernet
• Ethernet uses three (3) mechanisms to handle
collisions:
• Carrier sense
• Collision detection
• Binary exponential backoff
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
29
CSMA - Ethernet
• Ethernet requires each station to monitor the cable to
detect whether another transmission is already in progress
• this process is known as carrier sense
• it prevents the most obvious collision problems
• and substantially improves network utilization
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
30
CSMA - Collisions
• A collision can occur if two stations wait for a transmission to stop,
find the cable idle, and both start transmitting
• A small part of the problem is that even at the speed of light,
some time is required for a signal to travel down the cable
• Thus, a station at one end of the cable cannot know instantly
when a station at the other end begins to transmit
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
31
CSMA – Collision Detection
• To handle collisions
• each station monitors the cable during transmission
• If the signal on the cable differs from the signal that the station is
sending
• it means that a collision has occurred
• the technique is known as collision detection
• when a collision is detected, the sending station aborts
transmission
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
32
CSMA - Collisions
• Many details complicate Ethernet transmission
• For example, following a collision, transmission does not abort
until enough bits have been sent to guarantee that the collided
signals reach all stations
• Furthermore, following a transmission, stations must wait for
an interpacket gap (9.6 sec for a 10 Mbps Ethernet) to insure
that all stations sense an idle network and have a chance to
transmit
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
33
Binary Exponential Backoff
• After a collision occurs
• a computer must wait for the cable to become idle again
before transmitting a frame
• Randomization is used to avoid having multiple stations transmit
simultaneously as soon as the cable is idle
• The standard specifies a maximum delay, d, and requires each
station to choose a random delay less than d after a collision
occurs
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
34
Binary Exponential Backoff
• When two stations each choose a random value
• the station that chooses the smallest delay will proceed to send
a packet and the network will return to normal operation
• In the case where two or more computers happen to choose nearly
the same amount of delay
• they will both begin to transmit at nearly the same time
• producing a second collision
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
35
Binary Exponential Backoff
• To avoid a sequence of collisions
• Ethernet requires each computer to double the range from which a delay is chosen
after each collision
• a computer chooses a random delay between 0 - d after one collision
• a random delay between 0 - 2d after a second collision
• a random delay between 0 - 4d after a third, and so on
• After a few collisions, the range from which a random value is chosen becomes large
• Thus, some computer will choose a random delay shorter than the others, and will
transmit without a collision
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
36
Binary Exponential Backoff
• Doubling the range of the random delay after each collision
is known as binary exponential backoff
• By using exponential backoff
• an Ethernet can recover quickly after a collision
• because each computer agrees to wait longer times between
attempts when the cable becomes busy
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
37
Binary Exponential Backoff
• Even in the unlikely event that two or more computers
choose delays that are approximately equal
• exponential backoff guarantees that contention for the
cable will be reduced after a few collisions
• The combination of techniques described above is known by
the name Carrier Sense Multi-Access with Collision
Detection (CSMA/CD)
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
38
CSMA/CD Algorithm
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
39
CSMA
Carrier Sense Multiple Access (CSMA)
CSMA improves on ALOHA by sensing the channel!
• User doesn’t send if it senses someone else
Variations on what to do if the channel is busy:
• 1-persistent (greedy) sends as soon as idle
• Nonpersistent waits a random time then tries again
• p-persistent sends with probability p when idle
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
CSMA 1-Persistent
• Carrier Sense Multiple Access
• 1-Persistent is the simplest scheme but is greedy :
• When station has data to send, it listens to channel to see if anyone else is
transmitting
• If channel is idle, it sends its data, otherwise it waits.
• When channel becomes idle it transmits.
• If a collision occurs, it waits a random amount of time and starts again.
• Called 1-persistent because the station transmits with a probability of 1
when the channel is idle.
• Collisions occur and propagation delay and bandwidth-delay product
increases chance. Still better than ALOHA
CSMA Non-Persistent
• Conscious attempt is made to be non-greedy:
• Station listens for an idle signal and if no one else is transmitting it
sends its data.
• If channel is in use it does not keep sensing; instead it waits a random
amount of time before it tries sensing again.
• This leads to a better channel utilization but longer delays than
1- Persistent CSMA
CSMA p-Persistent
• This protocol is used with slotted channels
•
•
•
•
When a station is ready to send, it senses the channel
If the channel is idle, it sends with a probability p.
With a probability q = 1-p, it defers until the next slot.
If that slot is idle, it either transmits or defers again with probabilities p
and q.
• This continues until the frame is transmitted or until another station
begins transmitting. In this case, it acts as though there was a collision
and randomly backs off.
• WI-Fi ( 802.11) uses a refinement of this protocol
CSMA – Persistence
CSMA outperforms ALOHA, and being less persistent is better under high
load
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
CSMA/CD
• CSMA protocols are an improvement over ALOHA because they
ensure that no station transmits while the channel is busy.
• If two stations sense the channel to be idle and both start
transmitting simultaneously, collisions will still
• An improvement is for the station to quickly detect the busy
channel and to stop transmitting since the frame will be
garbeled and lost anyway.
• This is known as CSMA/CD ( Carrier Sense Multiple Access with
Collision Detection) and it saves time and bandwidth.
CSMA/CD
• CSMA/CD ( Carrier Sense Multiple Access with Collision Detection)
• This is important because it is the basis of the Ethernet LAN protocol.
• Suppose a station has just finished transmitting a frame and not any
other station with a frame to send can do so.
• If two or more begin to send there will be a collision.
• If a station detects the collision, it aborts the transmission, waits a
random time and tries again sending when the channel becomes idle.
• Thus there are contention and transmitting times as well as idle times
CSMA – Collision Detection
CSMA/CD improvement is to detect/abort collisions
• Reduced contention times improve performance
Collision time is much
shorter than frame time
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
CSMA/CD
• The contention algorithm:
• Suppose two stations begin to transmit at the same time (t0).
• How long will it take them to detect a collision?
• The minimum time is the same as the time it takes for the signal to
propagate from one station to another.
• Suppose a station begins transmitting and just before the frame
arrives that station begins transmitting.
• When it detects the collision, it stops transmitting, but in the
meantime almost 2 time units have passed (2τ –ε).
• We can think of this as a slotted ALOHA system with a slot of 2 τ
Collision Free Protocols
• Since collisions are not acceptable for real time traffic, such as VoIP,
we must examine collision free protocols:
• 1. Basic Bit-map method – station sets a bit in a slot to indicate it
has something to send. Works as long as everyone agrees. (Like
making a reservation)
• 2. Token passing- token is passed from one station to another –
permission to send.
• 3. Binary countdown-station wanting to send broadcasts its address
as a binary bit string, which is ORed with others trying to send.
• An arbitration rule is applied ot choose one( usually highest).
Limited Contention Protocols
• Two basic strategies for channel acquisition in broadcast network:
• Contention (as in CSMA) for heavy loads there is increasing
overhead
• Collision free - larger delays for light loads, but as loads increase
there is greater efficiency
• Combine best features of both – limited contention protocols
• Divide stations into groups
• Adaptive tree walk protocol
Collision-Free – Bitmap
Collision-free protocols avoid collisions entirely
• Senders must know when it is their turn to send
The basic bit-map protocol:
• Sender set a bit in contention slot if they have data
• Senders send in turn; everyone knows who has data
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Collision-Free – Token Ring
Token sent round ring defines the sending order
• Station with token may send a frame before passing
• Idea can be used without ring too, e.g., token bus
Token
Station
Direction of
transmission
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Collision-Free – Countdown
Binary countdown improves on the bitmap protocol
• Stations send their address in contention
slot (log N bits instead of N bits)
• Medium ORs bits; stations give up when
they send a “0” but see a “1”
• Station that sees its full address is next
to send
CN5E by Tanenbaum & Wetherall, ©
Pearson Education-Prentice Hall and D.
Wetherall, 2011
Limited-Contention Protocols
Idea is to divide stations into groups within which only a very small
number are likely to want to send
• Avoids wastage due to idle periods and collisions
Already too many contenders for a good chance of
one winner
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Limited Contention–Adaptive Tree Walk
Tree divides stations into groups (nodes) to poll
• Depth first search under nodes with poll collisions
• Start search at lower levels if >1 station expected
Level 0
Level 1
Level 2
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
CSMA/CA
• CSMA/CD does not work as well in wireless LANs
• because a transmitter used in a wireless LAN has a limited
range
• A receiver that is more δ than away from the transmitter
• will not receive a signal, and will not be able to detect a
carrier
• Consider three computers with wireless LAN hardware
positioned as the next slide illustrates
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
56
CSMA/CA
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
57
CSMA/CA
• In Figure 14.6, computer1 can communicate with
computer2, but cannot receive the signal from computer3
• Thus, if computer3 is transmitting a packet to computer2,
computer1's carrier sense mechanism will not detect the
transmission
• Similarly, if computer1 and computer3 simultaneously
transmit, only computer2 will detect a collision
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
58
CSMA/CA
• The problem is sometimes called the hidden station problem
• because some stations are not visible to others
• Wireless LANs use a modified access protocol
• known as CSMA with Collision Avoidance (CSMA/CA)
• The CSMA/CA triggers a brief transmission from the intended
receiver before transmitting a packet
• The idea is that if both the sender and receiver transmit a message
• all computers within range of either will know a packet transmission is
beginning
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
59
CSMA/CA
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
60
CSMA/CA
• On the previous slide
• computer3 sends a short message to announce that it is ready to transmit a
packet to computer2
• and computer2 responds by sending a short message announcing that it is
ready to receive the packet
• all computers in range of computer3 receive the initial announcement
• and all computers in the range of computer2 receive the response
• even though it cannot receive the signal or sense a carrier, computer 1 knows
that a packet transmission is taking place
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
61
CSMA/CA
• Collisions of control messages can occur when using CSMA/CA,
but they can be handled easily
• For example, if computer1 and computer3 each attempt to
transmit a packet to computer2 at exactly the same time
• their control messages will collide
• When a collision occurs, the sending stations apply random
backoff before resending the control messages.
• Because control messages are much shorter than a packet, the
probability of a second collision is low
© 2009 Pearson Education Inc., Upper Saddle River, NJ. All rights reserved.
62
Wireless LAN Protocols
Wireless has complications compared to wired.
Nodes may have different coverage regions
• Leads to hidden and exposed terminals
Nodes can’t detect collisions, i.e., sense while sending
• Makes collisions expensive and to be avoided
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Wireless LANs– Hidden terminals
Hidden terminals are senders that cannot sense each other but
nonetheless collide at intended receiver
• Want to prevent; loss of efficiency
• A and C are hidden terminals when sending to B
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Wireless LANs– Exposed terminals
Exposed terminals are senders who can sense each other but still
transmit safely (to different receivers)
• Desirably concurrency; improves performance
• B  A and C  D are exposed terminals
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Wireless LANs – MACA
MACA protocol grants access for A to send to B:
• A sends RTS to B [left]; B replies with CTS [right]
• A can send with exposed but no hidden terminals
A sends RTS to B; C and E hear and defer
for CTS
B replies with CTS; D and E hear and
defer for data
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Elements of a wireless network
wireless hosts
 laptop, PDA, IP phone
 run applications
 may be stationary (non-mobile)
or mobile
network
infrastructure
Wireless, Mobile Networks
 wireless does not always mean
mobility
6-67
Elements of a wireless network
network
infrastructure
Wireless, Mobile Networks
base station
 typically connected to wired
network
 relay - responsible for sending
packets between wired
network and wireless host(s)
in its “area”
 e.g., cell towers, 802.11
access points
6-68
Elements of a wireless network
network
infrastructure
Wireless, Mobile Networks
wireless link
 typically used to connect
mobile(s) to base station
 also used as backbone link
 multiple access protocol
coordinates link access
 various data rates,
transmission distance
6-69
Characteristics of selected wireless link standards
200
Data rate (Mbps)
54
5-11
802.11n
802.11a,g
802.11b
4
1
802.11a,g point-to-point
data
802.16 (WiMAX)
3G cellular
enhanced
UMTS/WCDMA-HSPDA, CDMA2000-1xEVDO
802.15
.384
UMTS/WCDMA, CDMA2000
3G
.056
IS-95, CDMA, GSM
2G
Indoor
Outdoor
10-30m
50-200m
Mid-range
outdoor
Long-range
outdoor
200m – 4 Km
5Km – 20 Km
Wireless, Mobile Networks
6-70
Wireless Link Characteristics
Differences from wired link ….
• decreased signal strength: radio signal attenuates as it propagates through
matter (path loss)
• interference from other sources: standardized wireless network frequencies
(e.g., 2.4 GHz) shared by other devices (e.g., phone); devices (motors)
interfere as well
• multipath propagation: radio signal reflects off objects ground, arriving ad
destination at slightly different times
…. make communication across (even a point to point) wireless link much more
“difficult”
Wireless, Mobile Networks
6-71
Wireless network characteristics
Multiple wireless senders and receivers create additional problems (beyond
multiple access):
B
A
C
C
A
Hidden terminal problem
B
space
B, A hear each other
 B, C hear each other
 A, C can not hear each other
means A, C unaware of their interference at
B

C’s signal
strength
A’s signal
strength
Signal attenuation:



Wireless, Mobile Networks
B, A hear each other
B, C hear each other
A, C can not hear each other interfering
at B
6-72
IEEE 802.11 Wireless LAN
• 802.11a
• 802.11b
• 5-6 GHz range
• 2.4-5 GHz unlicensed spectrum
• up to 54 Mbps
• up to 11 Mbps
• direct sequence spread spectrum (DSSS) in physical • 802.11g
layer
• 2.4-5 GHz range
• all hosts use same chipping code
• up to 54 Mbps
• 802.11n: multiple antennae
• 2.4-5 GHz range
• up to 200 Mbps


all use CSMA/CA for multiple access
all have base-station and ad-hoc network versions
Wireless, Mobile Networks
6-73
802.11 LAN Architecture

Internet

AP
hub, switch
or router
wireless host communicates with base
station
 base station = access point (AP)
Basic Service Set (BSS) (aka “cell”) in
infrastructure mode contains:
 wireless hosts
 access point (AP): base station
 ad hoc mode: hosts only
BSS 1
AP
BSS 2
Wireless, Mobile Networks
6-74
802.16: WiMAX
point-to-point
• like 802.11 & cellular: base station
model
• transmissions to/from base station by hosts
with omnidirectional antenna
• base station-to-base station backhaul with
point-to-point antenna
• unlike 802.11:
point-to-multipoint
• range ~ 6 miles (“city rather than coffee
shop”)
• ~14 Mbps
Wireless, Mobile Networks
6-75
Ethernet
• Classic Ethernet »
• Switched/Fast Ethernet »
• Gigabit/10 Gigabit Ethernet »
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Classic Ethernet – Physical Layer
One shared coaxial cable to which all hosts attached
• Up to 10 Mbps, with Manchester encoding
• Hosts ran the classic Ethernet protocol for access
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Classic Ethernet – MAC
MAC protocol is 1-persistent CSMA/CD (earlier)
• Random delay (backoff) after collision is computed with BEB (Binary
Exponential Backoff)
• Frame format is still used with modern Ethernet.
Ethernet
(DIX)
IEEE
802.3
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Classic Ethernet – MAC
Collisions can occur and take as long as 2 to detect
•  is the time it takes to propagate over the Ethernet
• Leads to minimum packet size for reliable detection
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Classic Ethernet - Performance
Efficient for large frames, even with many senders
• Degrades for small frames (and long LANs)
10 Mbps Ethernet,
64 byte min. frame
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Switched/Fast Ethernet
• Hubs wire all lines into a single CSMA/CD domain
• Switches isolate each port to a separate domain
• Much greater throughput for multiple ports
• No need for CSMA/CD with full-duplex lines
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Switched/Fast Ethernet
Switches can be wired to computers, hubs and switches
• Hubs concentrate traffic from computers
• More on how to switch frames the in 4.8
Switch
Hub
Switch ports
Twisted pair
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Switched/Fast Ethernet
Fast Ethernet extended Ethernet from 10 to 100 Mbps
• Twisted pair (with Cat 5) dominated the market
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Gigabit / 10 Gigabit Ethernet
Switched Gigabit Ethernet is now the garden variety
• With full-duplex lines between computers/switches
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Gigabit / 10 Gigabit Ethernet
• Gigabit Ethernet is commonly run over twisted pair
• 10 Gigabit Ethernet is being deployed where needed
• 40/100 Gigabit Ethernet is under development
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Wireless LANs
• 802.11 architecture/protocol stack »
• 802.11 physical layer »
• 802.11 MAC »
• 802.11 frames »
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.11 Architecture/Protocol Stack
Wireless clients associate to a wired AP (Access Point)
• Called infrastructure mode; there is also ad-hoc mode with no AP, but
that is rare.
To Network
Access
Point
Client
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.11 Architecture/Protocol Stack
MAC is used across different physical layers
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.11 physical layer
• NICs are compatible with multiple physical layers
• E.g., 802.11 a/b/g
Name
Technique
Max. Bit Rate
802.11b
Spread spectrum, 2.4 GHz
11 Mbps
802.11g
OFDM, 2.4 GHz
54 Mbps
802.11a
OFDM, 5 GHz
54 Mbps
802.11n
OFDM with MIMO, 2.4/5 GHz
600 Mbps
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.11 MAC
• CSMA/CA inserts backoff slots to avoid collisions
• MAC uses ACKs/retransmissions for wireless errors
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.11 MAC
Virtual channel sensing with the NAV and optional RTS/CTS (often not
used) avoids hidden terminals
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.11 MAC
• Different backoff slot times add quality of service
• Short intervals give preferred access, e.g., control, VoIP
• MAC has other mechanisms too, e.g., power save
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.11 Frames
• Frames vary depending on their type (Frame control)
• Data frames have 3 addresses to pass via APs
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Broadband Wireless
• 802.16 Architecture / Protocol Stack »
• 802.16 Physical Layer »
• 802.16 MAC »
• 802.16 Frames »
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.16 Architecture/Protocol Stack
Wireless clients connect to a wired basestation (like 3G)
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.16 Architecture/Protocol Stack
MAC is connection-oriented; IP is connectionless
• Convergence sublayer maps between the two
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.16 Physical Layer
Based on OFDM; base station gives mobiles bursts (subcarrier/time
frame slots) for uplink and downlink
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.16 (Wi-MAX) MAC
Connection-oriented with base station in control
• Clients request the bandwidth they need
Different kinds of service can be requested:
• Constant bit rate, e.g., uncompressed voice
• Real-time variable bit rate, e.g., video, Web
• Non-real-time variable bit rate, e.g., file download
• Best-effort for everything else
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
802.16 Frames
• Frames vary depending on their type
• Connection ID instead of source/dest addresses
(a)
(b)
(a) A generic frame. (b) A bandwidth request frame
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Bluetooth
• Bluetooth Architecture »
• Bluetooth Applications / Protocol »
• Bluetooth Radio / Link Layers »
• Bluetooth Frames »
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Bluetooth Architecture
Piconet master is connected to slave wireless devices
• Slaves may be asleep (parked) to save power
• Two piconets can be bridged into a scatternet
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Bluetooth Applications / Protocol Stack
Profiles give the set of protocols for a given application
• 25 profiles, including headset, intercom, streaming audio, remote control,
personal area network, …
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Bluetooth Radio / Link Layers
Radio layer
• Uses adaptive frequency hopping in 2.4 GHz band
Link layer
•
•
•
•
TDM with timeslots for master and slaves
Synchronous CO for periodic slots in each direction
Asynchronous CL for packet-switched data
Links undergo pairing (user confirms passkey/PIN) to authorize them before
use
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Bluetooth Frames
Time is slotted; enhanced data rates send faster but for the same
time; addresses are only 3 bits for 8 devices
(a)
(b)
(a)
(b)
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
RFID
• Gen 2 Architecture »
• Gen 2 Physical Layer »
• Gen 2 Tag Identification Layer »
• Gen 2 Frames »
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Gen 2 Architecture
Reader signal powers tags; tags reply with backscatter
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Gen 2 Physical Layer
• Reader uses duration of on period to send 0/1
• Tag backscatters reader signal in pulses to send 0/1
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Gen 2 Tag Identification Layer
Reader sends query and sets slot
structure
Tags reply (RN16) in a random
slot; may collide
Reader asks one tag for its
identifier (ACK)
Process continues until no tags
are left
CN5E by Tanenbaum & Wetherall, ©
Pearson Education-Prentice Hall and D.
Wetherall, 2011
Gen 2 Frames
• Reader frames vary depending on type (Command)
• Query shown below, has parameters and error detection
• Tag responses are simply data
• Reader sets timing and knows the expected format
Query message
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Data Link Layer Switching
• Uses of Bridges »
• Learning Bridges »
• Spanning Tree »
• Repeaters, hubs, bridges, .., routers, gateways »
• Virtual LANs »
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Uses of Bridges
• Common setup is a building with centralized wiring
• Bridges (switches) are placed in or near wiring closets
CN5E by Tanenbaum & Wetherall, ©
Pearson Education-Prentice Hall and D.
Wetherall, 2011
Learning Bridges
A bridge operates as a switched LAN (not a hub)
• Computers, bridges, and hubs connect to its ports
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Learning Bridges
Backward learning algorithm picks the output port:
• Associates source address on frame with input port
• Frame with destination address sent to learned port
• Unlearned destinations are sent to all other ports
Needs no configuration
• Forget unused addresses to allow changes
• Bandwidth efficient for two-way traffic
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Learning Bridges
Bridges extend the Link layer:
• Use but don’t remove Ethernet header/addresses
• Do not inspect Network header
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Spanning Tree – Problem
Bridge topologies with loops and only backward learning will cause
frames to circulate for ever
• Need spanning tree support to solve problem
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Spanning Tree – Algorithm
• Subset of forwarding ports for data is
use to avoid loops
• Selected with the spanning tree
distributed algorithm by Perlman
I think that I shall never see
A graph more lovely than a tree.
A tree whose crucial property
Is loop-free connectivity.
A tree which must be sure to span.
So packets can reach every LAN.
First the Root must be selected
By ID it is elected.
Least cost paths from Root are traced
In the tree these paths are placed.
A mesh is made by folks like me
Then bridges find a spanning tree.
– Radia Perlman, 1985.
CN5E by Tanenbaum & Wetherall, ©
Pearson Education-Prentice Hall and D.
Wetherall, 2011
Spanning Tree – Example
After the algorithm runs:
• B1 is the root, two dashed links are turned off
• B4 uses link to B2 (lower than B3 also at distance 1)
• B5 uses B3 (distance 1 versus B4 at distance 2)
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Repeaters, Hubs, Bridges, Switches,
Routers, & Gateways
Devices are named according to the layer they process
• A bridge or LAN switch operates in the Link layer
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Virtual LANs
VLANs (Virtual LANs) splits one physical LAN into multiple logical LANs
to ease management tasks
• Ports are “colored” according to their VLAN
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Virtual LANs – IEEE 802.1Q
Bridges need to be aware of VLANs to support them
• In 802.1Q, frames are tagged with their “color”
• Legacy switches with no tags are supported
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
Virtual LANs – IEEE 802.1Q
802.1Q frames carry a color tag (VLAN identifier)
• Length/Type value is 0x8100 for VLAN protocol
CN5E by Tanenbaum & Wetherall, © Pearson Education-Prentice
Hall and D. Wetherall, 2011
References and Resources
• Queueing theory and Poisson Distributions
• http://www.youtube.com/watch?v=Fk02TW6reiA
• http://stattrek.com/probability-distributions/poisson.aspx
• http://www.math.csusb.edu/faculty/stanton/probstat/poisson.html
• http://mathworld.wolfram.com/PoissonDistribution.html
• http://hyperphysics.phy-astr.gsu.edu/hbase/math/poifcn.html
End
Chapter 4
CN5E by Tanenbaum & Wetherall, ©
Pearson Education-Prentice Hall and
D. Wetherall, 2011