# Note 6: Medium Access Control Protocols

Note 6: Medium Access Control Protocols Random Access 1 Quiz #3 Describe in your own words bit stuffing and byte stuffing. 2 ALOHA Wireless link to provide data transfer between main campus & remote campuses of University of Hawaii Simplest solution: just do it A station transmits whenever it has data to transmit If more than one frames are transmitted, they interfere with each other (collide) and are lost If ACK not received within timeout, then a station picks random backoff time (to avoid repeated collision) Station retransmits frame after backoff time First transmission t0-X t0

Backoff period B Retransmission t t0+X Vulnerable period t0+X+2tprop t0+X+2tprop + B Time-out 3 ALOHA Model Definitions and assumptions X: frame transmission time (assumed to be constant) S: throughput (average # of successful frame transmissions per X seconds) G: load (average # of transmission attempts per X sec.) Psuccess : probability a frame transmission is successful S GPsuccess

X Prior interval Any transmission that begins during vulnerable period leads to collision Success if no arrivals during 2X seconds X frame transmission 4 Abramsons Assumption What is probability of no arrivals in vulnerable period? Abramson assumption: The backoff algorithm spreads the retransmissions so that frame transmissions, new and repeated, are equally likely to occur at any instant This implies that the number of frames transmitted in a time interval has a Poisson distribution ( t ) k t P[k arrivals in t seconds] k! e

Psuccess P[0 arrivals in 2X seconds] (2X ) 0! 0 2 X e 2G e 5 Throughput of ALOHA S GPsuccess Ge 2G S e-2 = 0.184 0.2

0.18 0.16 0.14 0.12 0.1 0.08 0.06 0.04 0.02 0 Collisions are means for coordinating access Max throughput is max=1/2e (18.4%) Bimodal behavior: Small G, SG Large G, S0 Collisions can snowball and drop throughput to zero G

6 Slotted ALOHA Time is slotted in X seconds slots Stations synchronized to frame times Stations transmit frames in first slot after frame arrival Backoff intervals in multiples of slots Backoff period kX (k+1)X Vulnerabl eperiod t0 +X+2tprop B t t0 +X+2tprop+ B Time-out

Only frames that arrive during prior X seconds collide 7 Throughput of Slotted ALOHA ( t ) k P[k arrivals in t seconds] k! e ( X ) 0 X G P[0 arrivals in X seconds] e 0! e G S GPsuccess G e 0.4 0.368 0.35 0.3 Ge-G

0.25 0.184 0.2 0.15 0.1 Ge-2G 0.05 G 8 4 1 0.5 0.25 0.125 0.0625 0.03125

0 0.01563 S 2 Psuccess t 8 Application of Slotted Aloha cycle ... ... Reservation mini-slots X-second slot Reservation protocol allows a large number of stations with infrequent traffic to reserve slots to transmit their frames in future cycles

Each cycle has mini-slots allocated for making reservations Stations use slotted Aloha during mini-slots to request slots 9 Carrier Sensing Multiple Access (CSMA) A station senses the channel before it starts transmission If busy, either wait or schedule backoff (different options) If idle, start transmission Vulnerable period is reduced to tprop (due to channel capture effect) Collisions in ALOHA or Slotted ALOHA involve 2 or 1 frame transmission times X If tprop >X (or if a>1), no gain compared to ALOHA or slotted ALOHA Station A begins transmission at t=0 Station A captures channel at t = tprop A

A 10 CSMA Options Transmitter behavior when busy channel is sensed 1-persistent CSMA (most greedy) Start transmission as soon as the channel becomes idle Low delay and high collision rates Non-persistent CSMA (least greedy) Wait a backoff period, then sense carrier again High delay and low collision rates p-persistent CSMA (adjustable greedy) Wait till channel becomes idle, transmit with prob. p; or wait another tprop & re-sense with probability 1-p

Delay and collisions rates can be balanced Sensing 11 1-Persistent CSMA Throughput 0.6 0.53 0.5 0.4 a 0.01 0.45 0.3 0.2 0.16 Better than Aloha & slotted Aloha for small a Worse than Aloha for a > 1 a =0.1

0.1 64 32 16 8 4 2 1 0.5 0.25 0.13 0.06 0.03 0

0.02 S G a=1 12 Non-Persistent CSMA Throughput a = 0.01 0.81 0.9 0.8 0.7 0.6 0.51 0.5 0.4 a = 0.1 0.3 0.2 0.14

Higher maximum throughput than 1persistent for small a Worse than Aloha for a > 1 0.1 64 32 16 8 4 2 1 0.5 0.25 0.13

0.06 0.03 0 0.02 S G a=1 13 CSMA with Collision Detection (CSMA/CD) Monitor for collisions & abort transmission Stations with frames to send, first do carrier sensing After beginning transmissions, stations continue listening to the medium to detect collisions If collisions detected, all stations involved stop transmission, reschedule random backoff times, and try again at scheduled times In CSMA collisions result in wastage of X seconds spent transmitting an entire frame CSMA-CD reduces wastage to time to detect collision and abort transmission

14 CSMA/CD reaction time A begins to transmit at A t=0 B A B A detects collision at A t= 2 tprop- B B begins to transmit at t = tprop- ; B detects collision at t = tprop It takes 2 tprop to find out if channel has been captured 15

CSMA-CD Model Assumptions Collisions can be detected and resolved in 2tprop Time slotted in 2tprop slots during contention periods Assume n busy stations, and each may transmit with probability p in each contention time slot Once the contention period is over (a station successfully occupies the channel), it takes X seconds for a frame to be transmitted It takes tprop before the next contention period starts. (a) Busy Contention Busy Idle Contention Busy Time 16

Contention Resolution How long does it take to resolve contention? Contention is resolved (success) if exactly 1 station transmits in a slot: Psuccess np(1 p) By taking derivative of Psuccess we find max occurs at p=1/n max success P n 1 1 1 n 1 1 n 1 1 n (1 ) (1 ) n n n e

On average, 1/Pmax = e = 2.718 time slots to resolve contention Average Contention Period 2t prop e seconds 17 CSMA/CD Throughput Busy Contention Busy Contention Busy Contention Busy Time At maximum throughput, systems alternates between contention periods and frame transmission times max X

1 1 X t prop 2et prop 1 2e 1 a 1 2e 1 Rd / L Rd/(vL) where: R bits/sec, L bits/frame, X=L/R seconds/frame a = tprop/X meters/sec. speed of light in medium d meters is diameter of system 2e+1 = 6.44 18 CSMA-CD Application: Ethernet First Ethernet LAN standard used CSMA-CD 1-persistent Carrier Sensing R = 10 Mbps tprop = 51.2 microseconds 512 bits = 64 byte slot accommodates 2.5 km + 4 repeaters

Truncated Binary Exponential Backoff After the nth collision, select backoff from {0, 1,, 2k 1}, where k=min(n, 10) 19 Throughput for Random Access MACs 1 CSMA/CD 1-P CSMA 0.8 Non-P CSMA max 0.6 Slotted ALOHA 0.4 ALOHA 0.2 a

0 0.01 0.1 1 For small a: CSMA-CD has best throughput For larger a: Aloha & slotted Aloha better throughput 20 Carrier Sensing and Priority Transmission Certain applications require faster response than others, e.g. ACK messages Impose different interframe times High priority traffic sense channel for time Low priority traffic sense channel for time High priority traffic, if present, seizes channel first This priority mechanism is used in IEEE 802.11 wireless LAN 21 Note 6: Medium Access Control Protocols Scheduling

22 Scheduling for Medium Access Control Schedule frame transmissions to avoid collision in shared medium More efficient channel utilization Less variability in delays Can provide fairness to stations Increased computational or procedural complexity Two main approaches Reservation Polling 23 Reservation Systems Reservation interval r d Frame transmissions d

d r d Cycle n r = 1 2 d d Time Cycle (n + 1) 3 M Transmissions organized into cycles Cycle: reservation interval + frame transmissions

The reservation intervals has a minislot for each station to request reservations for frame transmissions 24 Reservation System Options Centralized or distributed system Centralized systems: A central controller listens to reservation information, decides order of transmission, issues grants Distributed systems: Each station determines its slot for transmission from the reservation information Single or Multiple Frames Single frame reservation: Only one frame transmission can be reserved within a reservation cycle Multiple frame reservation: More than one frame transmission can be reserved within a frame Channelized or Random Access Reservations Channelized (typically TDMA) reservation: Reservation messages from different stations are multiplexed without any risk of collision Random access reservation: Each station transmits its reservation message randomly until the message goes through 25 Example Initially stations 3 & 5 have reservations to transmit frames (a) r

3 5 r 3 5 r 3 5 8 r 3 5 8 r 3 r 3 t Station 8 becomes active and makes reservation Cycle now also includes frame transmissions from station 8

(b) 8 r 3 5 r 3 5 r 3 5 8 r 3 5 8 t 26 Efficiency of Reservation Systems Assume minislot duration = vX TDM single frame reservation scheme If propagation delay is negligible, a single frame transmission requires

(1+v)X seconds Link is fully loaded when all stations transmit, maximum efficiency is: max MX 1 M vX MX 1 v TDM k frame reservation scheme If k frame transmissions can be reserved with a reservation message and if there are M stations, as many as Mk frames can be transmitted in XM(k+v) seconds Maximum efficiency is: max MkX 1 M vX MkX 1 v k 27 Random Access Reservation Systems

Large number of light traffic stations Dedicating a minislot to each station is inefficient Slotted ALOHA reservation scheme Stations use slotted Aloha on reservation minislots On average, each reservation takes at least e minislot attempts Effective time required for the reservation is 2.71vX max X 1 X (1 ev) 1 2.71v 28 Example: GPRS General Packet Radio Service Packet data service in GSM cellular radio GPRS devices, e.g. cellphones or laptops, send packet data over radio and then to Internet Slotted Aloha MAC used for reservations Single & multi-slot reservations supported 29

Polling Systems Centralized polling systems: A central controller transmits polling messages to stations according to a certain order Distributed polling systems: A permit for frame transmission is passed from station to station according to a certain order A signaling procedure exists for setting up order Central Controller 30 Polling System Options Service Limits: How much is a station allowed to transmit per poll? Exhaustive: until stations data buffer is empty (including new frame arrivals) Gated: all data in buffer when poll arrives Frame-Limited: one frame per poll Time-Limited: up to some maximum time Priority mechanisms More bandwidth & lower delay for stations that appear multiple times in the polling list Issue polls for stations with message of priority k or higher 31 Average Cycle Time

t t t t t 1 2 3 4 5 t M 1 t Tc

Assume walk times all equal to t Exhaustive Service: stations empty their buffers Cycle time = Mt + time to empty M station buffers /M be frame arrival rate at a station NC average number of frames transmitted from a station Time to empty one station buffer: Tc Tstation Nc X ( Tc )X M M X Average Cycle Time: Tc Mt MTstation Mt Mt Tc Tc 1

33 Efficiency of Polling Systems Exhaustive Service Cycle time increases as traffic increases, so delays become very large Walk time per cycle becomes negligible compared to cycle time: Tc Mt Efficiency Tc Can approach 100% Limited Service Many applications cannot tolerate extremely long delays Time or transmissions per station are limited This limits the cycle time and hence delay Efficiency of 100% is not possible MX 1

Efficiency MX Mt 1 t / X Single frame per poll 34 Application: Token-Passing Rings token Free Token = Poll Frame Delimiter is Token Free = 01111110 Busy = 01111111 Listen mode Input from ring Delay Transmit mode Output to ring

Ready station looks for free token Flips bit to change free token to busy Delay From device To device Ready station inserts its frames Reinserts free token when done 35 Methods of Token Reinsertion Multi-token operation Free token transmitted immediately after last bit of data frame Single-token operation Free token inserted after last bit of the busy token is received back Transmission time at least ring latency If frame transmission time is longer than ring latency, equivalent to multi-token operation

Busy token Free token Frame Idle Fill Single-Frame operation Free token inserted after transmitting station has received last bit of its frame Equivalent to attaching trailer equal to ring latency 36 Token Ring Throughput Definition : ring latency (time required for bit to circulate ring) X: maximum frame transmission time allowed per station Multi-token operation Assume network is fully loaded, and all M stations transmit for X seconds upon the reception of a free token This is a polling system with limited service time: max MX 1 1

MX 1 / MX 1 a / M a is the normalized ring latency X 37 Token Ring Throughput Single-token operation Effective frame transmission time is maximum of X and , therefore max = MX = + M max{(X,} 1 max{1, a} + a/M Single-frame operation Effective frame transmission time is X+ ,therefore

max = MX + M(X+ ) = 1 1+a(1 + 1/M) 38 Token Reinsertion Efficiency Comparison 1.2 M = 50 Maximum throughput 1 0.8 Multiple token operation M = 10 M = 50 0.6

M = 10 0.4 0.2 Single frame operation Single token operation 0 0 0.4 0.8 1.2 1.6 2 2.4 2.8 3.2 3.6 4 4.4 4.8 a a <<1, any token reinsertion strategy acceptable a 1, single token reinsertion strategy acceptable a >1, multitoken reinsertion strategy necessary 39 Application Examples Single-frame reinsertion IEEE 802.5 Token Ring LAN @ 4 Mbps

Single token reinsertion IBM Token Ring @ 4 Mbps Multitoken reinsertion IEEE 802.5 and IBM Ring LANs @ 16 Mbps FDDI Ring @ 50 Mbps All of these LANs incorporate token priority mechanisms 40 Comparison of MAC approaches Aloha & Slotted Aloha Simple & quick transfer at very low load Accommodates a large number of low-traffic bursty users Highly variable delay at moderate loads Efficiency does not depend on a CSMA-CD Quick transfer and high efficiency for low delay-bandwidth product Can accommodate a large number of bursty users Variable and unpredictable delay

41 Comparison of MAC approaches Reservation On-demand transmission of bursty or steady streams Accommodates large number of low-traffic users with slotted Aloha reservations Can incorporate QoS Handles large delay-bandwidth product via delayed grants Polling Generalization of time-division multiplexing Provides fairness through regular access opportunities Can provide bounds on access delay Performance deteriorates with large delay-bandwidth product 42 Note 6: Medium Access Control Protocols Channelization 43

Why Channelization? Channelization Semi-static bandwidth allocation of portion of shared medium to a given user Highly efficient for constant-bit rate traffic Preferred approach in Cellular telephone networks Terrestrial & satellite broadcast radio & TV 44 Why not Channelization? Inflexible in allocation of bandwidth to users with different requirements Inefficient for bursty traffic Does not scale well to large numbers of users Average transfer delay increases with number of users M Dynamic MAC much better at handling bursty traffic 45 Channelization Approaches Frequency Division Multiple Access (FDMA) Frequency band allocated to users Broadcast radio & TV, analog cellular phone

Time Division Multiple Access (TDMA) Periodic time slots allocated to users Telephone backbone, GSM digital cellular phone Code Division Multiple Access (CDMA) Code allocated to users Cellular phones, 3G cellular 46 Channelization: FDMA Divide channel into M frequency bands Each station transmits and listens on assigned bands Frequency 1 2 W Guard bands M1 M

Time Each station transmits at most R/M bps Good for stream traffic; Used in connection-oriented systems Inefficient for bursty traffic 47 Channelization: TDMA Dedicate 1 slot per station in transmission cycles Stations transmit data burst at full channel bandwidth Guard time Frequency W 1 2 3 ... M

1 Time One cycle Each station transmits at R bps 1/M of the time Excellent for stream traffic; Used in connection-oriented systems Inefficient for bursty traffic due to unused dedicated slots 48 Guardbands FDMA Frequency bands must be non-overlapping to prevent interference Guardbands ensure separation; form of overhead TDMA Stations must be synchronized to common clock Time gaps between transmission bursts from different stations to prevent collisions; form of overhead Must take into account propagation delays 49 Channelization: CDMA

Code Division Multiple Access Channels determined by a code used in modulation and demodulation Stations transmit over entire frequency band all of the time! Frequency 1 2 W 3 Time 50 CDMA Spread Spectrum Signal Transmitter from one user Binary information R1 bps W1 Hz R >> R1bps W >> W1 Hz

Unique user binary random sequence Radio antenna Digital modulation User information mapped into: +1 or -1 for T sec. Multiply user information by pseudo- random binary pattern of G chips of +1s and -1s Resulting spread spectrum signal occupies G times more bandwidth: W = GW1 Modulate the spread signal by sinusoid at appropriate f c 51 CDMA Demodulation Signals from all transmitters

Signal and residual interference Digital demodulation Correlate to user binary random sequence Binary information Recover spread spectrum signal Synchronize to and multiply spread signal by same pseudo-random binary pattern used at the transmitter In absence of other transmitters & noise, we should recover the original +1 or -1 of user information Other transmitters using different codes appear as residual noise 52 Pseudorandom pattern generator

g2 g0 R0 R1 g3 R2 output g(x) = x3 + x2 + 1 The coefficients of a primitive generator polynomial determine the feedback taps Time R0 R1 R2 0 1 0 0 1 0 1 0 2 1 0 1 3 1 1 0 4 1 1 1

5 0 1 1 6 0 0 1 7 1 0 0 Sequence repeats from here onwards 53 Channelization in Code Space Each channel uses a different pseudorandom code Codes should have low cross-correlation If they differ in approximately half the bits the correlation between codes is close to zero and the effect at the output of each others receiver is small As number of users increases, effect of other users on a given receiver increases as additive noise CDMA has gradual increase in BER due to noise as number of users is increased Interference between channels can be eliminated if codes are selected so they are orthogonal and if receivers and transmitters are synchronized Shown in next example 54 Example: CDMA with 3 users

Assume three users share same medium Users are synchronized & use different 4-bit orthogonal codes: {-1,-1,-1,-1}, {-1, +1,-1,+1}, {-1,-1,+1,+1} -1 -1 +1 User 1 x Receiver +1 -1 +1 User 2 x +1 User 3 +

+1 -1 x Shared Medium 55 Sum signal is input to receiver Channel 1: 110 -> +1+1-1 -> (-1,-1,-1,-1),(-1,-1,-1,-1),(+1,+1,+1,+1) Channel 2: 010 -> -1+1-1 -> (+1,-1,+1,-1),(-1,+1,-1,+1),(+1,-1,+1,-1) Channel 3: 001 -> -1-1+1 -> (+1,+1,-1,-1),(+1,+1,-1,-1),(-1,-1,+1,+1) Sum Signal: (+1,-1,-1,-3),(-1,+1,-3,-1),(+1,-1,+3,+1) Channel 1 Channel 2 Channel 3 Sum Signal 56 Example: Receiver for Station 2 Each receiver takes sum signal and integrates by code

sequence of desired transmitter Integrate over T seconds to smooth out noise Decoding signal from station 2 + x Integrate over T sec Shared Medium 57 Decoding at Receiver 2 Sum Signal: Channel 2 Sequence: Correlator Output: Integrated Output: Binary Output: (+1,-1,-1,-3),(-1,+1,-3,-1),(+1,-1,+3,+1) (-1,+1,-1,+1),(-1,+1,-1,+1),(-1,+1,-1,+1) (-1,-1,+1,-3),(+1,+1,+3,-1),(-1,-1,-3,+1) -4, +4, -4 0,

1, 0 Sum Signal X = Channel 2 Sequence Correlator Output +4 Integrator Output -4 -4 58 Walsh Functions Walsh functions provide orthogonal code sequences by mapping 0 to -1 and 1 to +1

Walsh matrices constructed recursively as follows: W2n= W1= W 4= 0 W2= 0 0 0 0 0 1 0 1 0 0 1 1 0 1

1 0 Wn W n Wn Wnc 0 0 0 1 W8= 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0

0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 0 0 0 1 0

1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 1 0

0 1 59 Channelization in Cellular Telephone Networks Cellular networks use frequency reuse Band of frequencies reused in other cells that are sufficiently far that interference is not a problem Cellular networks provide voice connections that are steady streams FDMA used in AMPS TDMA used in IS-54 and GSM CDMA used in IS-95 60 Further Reading Textbook: 6.1, 6.2, 6.3, 6.4 61

## Recently Viewed Presentations

• These are the tiniest microorganisms. bacteria. viruses. smallest living thing. unicellular prokaryote (NO nucleus) reproduces . FAST. through . binary fission
• AUTONOMIC DRUGS (Cholinergic and Anticholinergic Drugs) Presented by Sasan Zaeri (PharmD, PhD) Neurotransmitters ACh ACh Sweat glands Striated muscle ACh SOMATIC NERVOUS SYSTEM Heart Sm. mus. Glands ACh ACh Parasympathetic ACh E, NE Ad. M. Heart Sm. mus. Glands ACh...
• cougar take to reduce human conflict, improve ungulate populations, or reduce livestock conflicts, and confirm cougar population resiliency. Management Scales and Objectives. Attention to fine-scale situations. Target Area Management. Stakeholder Attention. Frequency of Use. Design and Considerations. Zone Updates
• Vendor Template Excel worksheet - track changes. NYSED should plan changes ahead of time and have fewer changes. Provide materials sooner for review prior to the meetings. Split meetings (HR & Student). More timely delivery of SIRS Manual with complete...
• 750 Computer hours, 10GB of storage, one 10GB SQL Azure . 52% off of our normal consumption rates. From April 1st until June 30th, if you buy two Windows Azure and SQL Azure Extended subscriptions (\$109.95 per Base Unit per...
• The U.S. Mobile Market. 87 percent of Americans have a mobile phone. Of those, only about 12 percent currently use them to make mobile payments. Some believe that mobile payments will achieve "widespread mainstream consumer adoption" by 2015
• Genral mamager, Garden Silk, Surat Shri.Deepak S. Tandlekar 5 Secretary Principal I.T.I.,Majuragate,Surat Shri.H.V.Patel 4 Member Sr. Vice Precidant H.R. Reliance Ind,Surat Shri Himanshu Bhatt 3 Member Head Personal EHS&TQM, L&T, Hazira Shri Atik M. Desai 2 Chairman Chairman, Apparel Mfg.Asso.,Surat...
• WLS Anticipate Fed raising rates Result: dampen housing market Housing market tends to lag economy showing signs of slowing Did not want to focus on industry directly impacted by Fed interest rate moves TOPP Strong financial position Not in a...