Lectures 13&14 Packet Multiple Access: The Aloha protocol Eytan Modiano Massachusetts Institute of Technolog
Lectures 13 & 14 Packet Multiple Access: The Aloha protocol Eytan Modiano Massachusetts Institute of Technology Eytan Modiano Slide 1
Multiple Access Shared Transmission Medium a receiver can hear multiple transmitters a transmitter can be heard by multiple receivers the major problem with multi-access is allocating the channel between the users the nodes do not know when the other nodes have data to send Need to coordinate transmissions
Multiple Access • Shared Transmission Medium – a receiver can hear multiple transmitters – a transmitter can be heard by multiple receivers • the major problem with multi-access is allocating the channel between the users; the nodes do not know when the other nodes have data to send – Need to coordinate transmissions Eytan Modiano Slide 2
Examples of multiple Access channels Local area networks(LANs) Traditional Ethernet Recent trend to non -multi-access lANs satellite channels Multi-drop telephone Wireless radio Medium Access Control (MAC) MAC NET Regulates access to channel DLC LLC Logical Link Control (LLC) All other dlc functions PHY
Examples of Multiple Access Channels • Local area networks (LANs) – Traditional Ethernet – Recent trend to non-multi-access LANs • satellite channels • Multi-drop telephone • Wireless radio • Medium Access Control ( MAC) – Regulates access to channel • Logical Link Control (LLC) – All othe r DLC f unctions NET DLC PHY MAC LLC Eytan Modiano Slide 3
Approaches to Multiple Access Fixed Assignment (TDMA, FDMA, CDMA each node is allocated a fixed fraction of bandwidth Equivalent to circuit switching very inefficient for low duty factor traffic Contention systems Polling Reservations and Scheduling Random access
Approaches to Multiple Access • Fixed Assignment (TDMA, FDMA, CDMA) – each node is allocated a fixed f raction of bandwidth – Equivalent to circuit switching – very inefficient for low duty factor traffic • Contention systems – Polling – Res ervations and Scheduling – Random Access Eytan Modiano Slide 4
Aloha Single receiver, many transmitters Receiver Transmitters E. g, Satellite system wireless
Aloha Single receiver, many transmitters Receiver ... . Transmitters E.g., Satellite system, wireless Eytan Modiano Slide 5
Slotted Aloha Time is divided into"slots" of one packet duration E.g., fixed size packets When a node has a packet to send, it waits until the start of the next slot to send it Requires synchronization If no other nodes attempt transmission during that slot, the transmission is successful Otherwise“ collision” Collided packet are retransmitted after a random delay uccess Collision Success
Slotted Aloha • Time is divided into “slots” of one packet duration – E.g., fixed size packets • When a node has a packet to send, it waits until the start of the next slot to send it – Requires synchronization • If no other nodes attempt transmission during that slot, the transmission is successful – Otherwise “collision” – Collided packet are retransmitted after a random delay 1 2 3 4 5 Success Idle Collision Idle Success Eytan Modiano Slide 6
Slotted Aloha assumptions Poisson external arrivals No capture Packets involved in a collision are lost Capture models are also possible Immediate feedback Idle(o), Success(1), Collision(e) If a new packet arrives during a slot, transmit in next slot If a transmission has a collision, node becomes backlogged while backlogged, transmit in each slot with probability qr until successful Infinite nodes where each arriving packet arrives at a new node Equivalent to no buffering at a node(queue size 1) Pessimistic assumption gives a lower bound on Aloha performance
Slotted Aloha Assumptions • Poisson external arrivals • No capture – Packets involved in a collision are lost – Capture models are also possible • Immediate feedback – Idle (0) , Success (1), Collision (e) • If a new packet arrives during a slot, transmit in next slot • If a transmission has a collision, node becomes backlogged – while backlogged, transmit in each slot with probability qr until successful • Infinite nodes where each arriving packet arrives at a new node – Equivalent to no buffering at a node (queue size = 1) – Pessimistic assumption gives a lower bound on Aloha performance Eytan Modiano Slide 7
Markov chain for slotted aloha 03 P3 4 2 0 灯 state(n) of system is number of backlogged nodes pi, i-1= prob. of one backlogged attempt and no new arrival pi, i =prob. of one new arrival and no backlogged attempts or no new arrival and no success pi, i +1= prob of one new arrival and one or more backlogged attempts pi, i+j= Prob. Of J new arrivals and one or more backlogged attempts or J+1 new arrivals and no backlogged attempts Steady state probabilities do not exists Backlog tends to infinity = system unstable More later
Markov chain for slotted aloha P03 0 1 P P P34 10 13 2 3 • state (n) of system is number of backlogged nodes. pi,i-1 = prob. of one backlogged attempt and no new arrival pi,i =prob. of one new arrival and no backlogged attempts or no new arrival and no success pi,i+1= prob of one new arrival and one or more backlogged attempts pi,i+j = Prob. Of J new arrivals and one or more backlogged attempts or J+1 new arrivals and no backlogged attempts • Steady state probabilities do not exists – Bac klog tends to infinity => system unstable Eytan Modiano – More later Slide 8
slotted aloha let g(n) be the attempt rate(the expected number of packets transmitted in a slot) in state n gn)=λ+nqr The number of attempted packets per slot in state n is approximately a poisson random variable of mean g(n) P(m attempts)=g(nme-9g(n)/m P(idle)= probability of no attempts in a slot =e g(n) p(success)= probability of one attempt in a slot g(n)e-g(n) P(collision = P(two or more attempts)=1-P(idle) -P(success)
slotted aloha • let g(n) be the attempt rate (the expected number of packets transmitted in a slot) in state n g(n) = λ + nqr • The number of attempted packets per slot in state n is approximately a Poisson random variable of mean g(n) – P (m attempts) = g(n)me-g(n)/m! – P (idle) = probability of no attempts in a slot = e-g(n) – p (success) = probability of one attempt in a slot = g(n)e-g(n) – P (collision) = P (two or more attempts) = 1 - P(idle) - P(success) Eytan Modiano Slide 9
Throughput of Slotted Aloha The throughput is the fraction of slots that contain a successful transmission= P(success)= g(n)e-g(n) When system is stable throughput must also equal the external arrival rate(a) Departure rate g(n)e-g(n) g(n) What value of g(n) gn)e g(m)=e gtn)-g(n)e-tn) maximizes throughput? lg(n) g(m)=1 g(n)too many idle slots g(n)>1=> too many collisions P(success)=(n )e g(m)=1/ex0.36 If g(n)can be kept close to 1, an external arrival rate of 1/e packets per slot can be sustained
Throughput of Slotted Aloha • The throughput is the fraction of slots that contain a successful transmission = P(success) = g(n)e-g(n) – When system is stable throughput must also equal t he external arrival rate ( λ) -1 e Departure rate g(n)e-g(n) 1 g(n) – What value o f g(n) maximizes throughput? – g(n) too many idle slots – g(n) > 1 => too many collisions – If g(n) can be kept close to 1, an external arrival rate of 1/e packets per slot can be sustained d dg ( n ) g ( n ) e − g(n) = e − g(n) − g ( n ) e − g(n) = 0 ⇒ g ( n ) = 1 ⇒ P (success ) = g ( n ) e − g(n) = 1/ e ≈ 0.36 Eytan Modiano Slide 10