美国麻省理工大学：《Communication Systems Engineering（通讯系统工程）》Eytan Modiano Massachusetts Institute of Technology

Packet multiple access and the Aloha protocol Eytan Modiano Massachusetts Institute of Technology Department of Aeronautics and Astronautics Eytan Modiano

Packet multiple access and the Aloha protocol Eytan Modiano Massachusetts Institute of Technology Department of Aeronautics and Astronautics Eytan Modiano Slide 1

Packet Multiple Access SHARED UPLIN TERMINAL APPL TERMINALL TRANS NET LLC DLC MAC PHYS TERM|NA凵 TERMINAl Medium Access Control(MAC) Regulates access to channel TERMINA Logical Link Control (LLC) Eytan Modiano All other dlc functions

Packet Multiple Access TERMINAL TERMINAL TERMINAL TERMINAL TERMINAL PMA SHARED UPLINK PHYS DLC NET TRANS APPL LLC MAC • Medium Access Control (MAC) – Regulates access to channel • Logical Link Control (LLC) Eytan Modiano Slide 2 – All other DLC functions

Examples of multiple Access channels Local area networks lANs) · Satellite channels Wireless radio Characteristics of Multiple Access channel Shared transmission medium A receiver can hear multiple transmitters a transmitter can be heard by multiple receivers The major problem with multiple access is allocating the channel between the users Nodes do not know when other nodes have data to send Need to coordinate transmissions Eytan Modiano

Examples of Multiple Access Channels • Local area networks (LANs) • Satellite channels • Wireless radio • Characteristics of Multiple Access Channel – Shared Transmission Medium A receiver can hear multiple transmitters A transmitter can be heard by multiple receivers – The major problem with multiple access is allocating the channel between the users Nodes do not know when other nodes have data to send Need to coordinate transmissions 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 Packet multiple access Polling Reservations and Scheduling Random Access Eytan Modiano

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 • Packet multiple access – Polling – Reservations and Scheduling – Random Access Eytan Modiano Slide 4

Aloha Single receiver, many transmitters Receiver Transmitters E.g., Satellite system wireless Eytan Modiano

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 successft Otherwise“ collision” Collided packet are retransmitted after a random delay Success Collision Success Eytan Modiano

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, it becomes backlogged and retransmitted after a random delay Let n be the number of backlogged nodes Eytan Modiano

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, it becomes backlogged and retransmitted after a random delay – Let n be the number of backlogged nodes Eytan Modiano Slide 7

slotted aloha Let g be the attempt rate(the expected number of packets transmitted in a slot) The number of attempted packets per slot is approximately a poisson random variable of mean g=n+n*qr q e probability that a backlogged packet is retransmitted in a slot n= number of backlogged packets P(m attempts)=gme 9/m P(idle)= probability of no attempts in a slot=e 9 p(success)=probability of one attempt in a slot= ge9 P(collision)=P (two or more attempts)=1-P(idle)-P(success Eytan Modiano

λ slotted aloha • Let g be the attempt rate (the expected number of packets transmitted in a slot) – The number of attempted packets per slot is approximately a Poisson random variable of mean g = λ + n*qr qr = probability that a backlogged packet is retransmitted in a slot n = number of backlogged packets – P (m attempts) = gme-g/m! – P (idle) = probability of no attempts in a slot = e-g – p (success) = probability of one attempt in a slot = ge-g – P (collision) = P (two or more attempts) = 1 - P(idle) - P(success) Eytan Modiano Slide 8

Throughput of Slotted Aloha The throughput is the fraction of slots that contain a successful transmission P(success)=ge9 When system is stable throughput must also equal the external arrival rate (2) Departure rate ge s=e 8-ge 8=0 What value of g dg(n maximizes throughput? →g= g too many idle slots g>1=> too many collisions →P( success)=ge=1/e≈0.36 If g 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) = ge-g – When system is stable throughput must also equal the external arrival rate (λ) -1 e Departure rate ge-g 1 g d – What value of g dg n ge − g = e− g − ge− g = 0 ( ) maximizes throughput? ⇒= g 1 – g too many idle slots – g > 1 => too many collisions ⇒ P(success) = ge− g = 1/ e≈ 0.36 – If g can be kept close to 1, an external arrival rate of 1/e packets per Eytan Modiano Slide 9 slot can be sustained

Instability of slotted aloha if backlog increases beyond unstable point (bad luck then it tends to increase without limit and the departure rate drops to o Aloha is inherently unstable and needs algorithm to keep it stable Drift in state n, D(n)is the expected change in backlog over one time slot Dn)=λ-P( success=λ-g(n)e9 negative drift Departure rate negative drift Arrival rate Stable Unstable G=0|G=1 G=λ+n Slide 10

λ λ Instability of slotted aloha • if backlog increases beyond unstable point (bad luck) then it tends to increase without limit and the departure rate drops to 0 – Aloha is inherently unstable and needs algorithm to keep it stable • Drift in state n, D(n) is the expected change in backlog over one time slot – D(n) = λ - P(success) = λ - g(n)e-g(n) negative drift positive drift G=0 e G=1 Ge-G -1 λ Arrival rate Departure rate Stable Unstable negative drift positive drift Eytan Modiano G = λ + nqr Slide 10