Mob 3 media access 20010

  • 41 trang
  • file .pdf
Mobile Communications
 Media Access
 Motivation
 SDMA, FDMA, TDMA
 Aloha
 Reservation schemes
 Collision avoidance, MACA
 Polling
 CDMA
 SAMA
 Comparison
Internet & Mobile Communications -
2010
Motivation
 Can we apply media access methods from
fixed networks?
 Example CSMA/CD
– Carrier Sense Multiple Access with Collision
Detection
– send as soon as the medium is free, listen into the
medium if a collision occurs (original method in
IEEE 802.3)
2
Internet & Mobile Communications - 2010
Background on LANs
 Shared Access Networks are different
– they assume multiple nodes on the same physical link
– Bus, ring and wireless structures
– Transmission sent by one node is received by all
others
– No intermediate switches
 Need methods for moderating access (MAC
protocols)
– Fairness
– Performance
– How can this be done?
3
Internet & Mobile Communications - 2010
Background on LANs
 Multiple Access Methods
– Fixed assignment
 Partition channel so each node gets a slice of the
bandwidth
 Essentially circuit switching – thus inefficient
 Examples: TDMA, FDMA, CDMA (all used in wireless/
cellular environments)
– Contention-based
 Nodes contends equally for bandwidth and recover from
collisions
 Examples: Aloha, Ethernet
– Token-based or reservation-based
 Take turns using the channel
 Examples: Token ring
4
Internet & Mobile Communications - 2010
Background on LANs
 Our Focus is Ethernet
– History
 Developed by Bob Metcalfe and others at Xerox PARC in
mid-1970s
 Roots in Aloha packet-radio network
 Standardized by Xerox, DEC, and Intel in 1978
 LAN standards define MAC and physical layer connectivity
– IEEE 802.3 (CSMA/CD - Ethernet) standard – originally 2Mbps
– IEEE 802.3u standard for 100Mbps Ethernet
– IEEE 802.3z standard for 1,000Mbps Ethernet
– CSMA/CD: Ethernet’s Media Access Control (MAC) policy
 CS = carrier sense
– Send only if medium is idle
 MA = multiple access
 CD = collision detection
– Stop sending immediately if collision is detected
5
Internet & Mobile Communications - 2010
Background : Ethernet Overview
 Most popular packet-switched LAN technology
 Bandwidths: 10Mbps, 100Mbps, 1Gbps
 Max bus length: 2500m
– 500m segments with 4 repeaters
 Bus and Star topologies are used to connect hosts
– Hosts attach to network via Ethernet transceiver or hub or
switch
 Detects line state and sends/receives signals
– Hubs are used to facilitate shared connections
– All hosts on an Ethernet are competing for access to the
medium
 Switches break this model
 Problem: Distributed algorithm that provides fair
6 access
Internet & Mobile Communications - 2010
Background: Ethernet Overview (contd.)
 Ethernet by definition is a broadcast protocol
– Any signal can be received by all hosts
– Switching enables individual hosts to communicate
 Network layer packets are transmitted over an
Ethernet by encapsulating
 Frame Format
64 48 48 16 32
Preamble Dest Src Type Body CRC
addr addr
7
Internet & Mobile Communications - 2010
Background: Ethernet Frames
 Preamble is a sequence of 7 bytes, each set to “10101010”
– Used to synchronize receiver before actual data is sent
 Addresses
– unique, 48-bit unicast address assigned to each adapter
 example: 8:0:e4:b1:2
 Each manufacturer gets their own address range
– broadcast: all 1s
– multicast: first bit is 1
 Type field is a demultiplexing key used to determine which higher
level protocol the frame should be delivered to
 Body can contain up to 1500 bytes of data
8
Internet & Mobile Communications - 2010
Background: Ethernet’s MAC Algorithm
 In Aloha, decisions to transmit are made without paying attention
to what other nodes might be doing
 Ethernet uses CSMA/CD – listens to line before/during sending
 If line is idle (no carrier sensed)
– send packet immediately
– upper bound message size of 1500 bytes
– must wait 9.6us between back-to-back frames
 If line is busy (carrier sensed)
– wait until idle and transmit packet immediately
 called 1-persistent sending
 If collision detected
– Stop sending and jam signal
– Try again later
9
Internet & Mobile Communications - 2010
Background: State Diagram for CSMA/CD
Packet?
No
Sense Send Detect
Carrier Collision
Yes
Discard
Packet Jam channel
attempts < 16 b=CalcBackoff();
wait(b);
attempts++;
attempts == 16
10
Internet & Mobile Communications - 2010
Background: Collisions
 Collisions are caused when two adaptors transmit at
the same
 time (adaptors sense collision based on voltage
differences)
– Both found line to be idle
– Both had been waiting to for a busy line to become idle
A starts at A B
time 0
Message almost
A B
there at time T when
B starts – collision!
How can we be sure A knows about the collision?
11
Internet & Mobile Communications - 2010
Background: Collision Detection
 How can A know that a collision has taken place?
There must be a mechanism to insure retransmission on collision

– A’s message reaches B at time Tp
– B’s message reaches A at time 2 Tp
– So, A must still be transmitting at 2 Tp
 IEEE 802.3 specifies max value of 2 Tp to be 51.2us
– This relates to maximum distance of 2500m between hosts
– At 10Mbps it takes 0.1us to transmit one bit so 512 bits (64B) take
51.2us to send
– So, Ethernet frames must be at least 64B long
 14B header, 46B data, 4B CRC
 Padding is used if data is less than 46B
 Send jamming signal after collision is detected to insure all hosts
see collision
– 48 bit signal
12
Internet & Mobile Communications - 2010
Background: Collision Detection contd.
A B
time = 0
A B
time = Tp
A B
time = 2Tp
13
Internet & Mobile Communications - 2010
Background: Exponential Backoff
 If a collision is detected, delay and try again
 Delay time is selected using binary exponential backoff
– 1st time: choose K from [0,1] then delay = K * 51.2µs
– 2nd time: choose K from [0,1,2,3] then delay = K * 51.2µs
– nth time: delay = K x 51.2µs, for K=0..2n – 1
 Note max value for k = 1023
– give up after several tries (usually 16)
 Report transmit error to host
 If delay were not random, then there is a chance that
sources would retransmit in lock step
 Why not just choose from small set for K
– This works fine for a small number of hosts
– Large number of nodes would result in more collisions
14
Internet & Mobile Communications - 2010
Background: MAC Algorithm from the Receiver Side
 Senders handle all access control
 Receivers simply read frames with acceptable
address
– Address to host
– Address to broadcast
– Address to multicast to which host belongs
– All frames if host is in promiscuous mode
15
Internet & Mobile Communications - 2010
Background: Experiences with Ethernet
 Ethernets work best under light loads
– Utilization over 30% is considered heavy
 Network capacity is wasted by collisions
 Most networks are limited to about 200 hosts
– Specification allows for up to 1024
 Most networks are much shorter
– 5 to 10 microsecond RTT
 Transport level flow control helps reduce load
 Ethernet is inexpensive, fast and easy to administer!
16
Internet & Mobile Communications - 2010
Motivation
 Problems in wireless networks
– signal strength decreases proportional to the square
of the distance
– the sender would apply CS and CD, but the
collisions happen at the receiver
– it might be the case that a sender cannot “hear” the
collision, i.e., CD does not work
– furthermore, CS might not work if, e.g., a terminal is
“hidden”
17
Internet & Mobile Communications - 2010
Motivation: hidden and exposed terminals
 Hidden terminals
– A sends to B, C cannot receive A
– C wants to send to B, C senses a “free” medium (CS fails)
– collision at B, A cannot receive the collision (CD fails)
– A is “hidden” for C
 Exposed terminals A B C
– B sends to A, C wants to send to another terminal (not A or B)
– C has to wait, CS signals a medium in use
– but A is outside the radio range of C, therefore waiting is not
necessary
18 – C is “exposed” to B
Internet & Mobile Communications - 2010
Motivation - near and far terminals
 Terminals A and B send, C receives
– signal strength decreases proportional to the square of the
distance
– the signal of terminal B therefore drowns out A’s signal
– C cannot receive A
A B C
 If C for example was an arbiter for sending rights,
terminal B would drown out terminal A already on the
physical layer
 Also severe problem for CDMA-networks - precise
19
power control needed!
Internet & Mobile Communications - 2010
Access methods SDMA/FDMA/TDMA
 SDMA (Space Division Multiple Access)
– segment space into sectors, use directed antennas
– cell structure
 FDMA (Frequency Division Multiple Access)
– assign a certain frequency to a transmission channel between
a sender and a receiver
– permanent (e.g., radio broadcast), slow hopping (e.g., GSM),
fast hopping (FHSS, Frequency Hopping Spread Spectrum)
 TDMA (Time Division Multiple Access)
– assign the fixed sending frequency to a transmission channel
between a sender and a receiver for a certain amount of time
 The multiplexing schemes presented in chapter 2 are
20 now used to control medium access!
Internet & Mobile Communications - 2010