Slotted aloha Efficiency max efficiency: find p Efficiency long-run that maximizes fraction of successful slots Np(1-p)N-1 (many nodes, all with many for many nodes, take frames to send) limit of Np*(1-P*)N-ias n goes to infinity, gives ·supp0se; N nodes with many frames to send Max efficiency 1/e=.37 each transmits in slot with probability p prob that given node has At best: channel success in a slot =p(1- used for useful p)M-1 transmissions 37% prob that any node has a of time success= Np(1-p)N-l
Slotted Aloha Efficiency • suppose: N nodes with many frames to send, each transmits in slot with probability p • prob that given node has success in a slot = p(1- p)N-1 • prob that any node has a success = Np(1-p)N-1 • max efficiency: find p* that maximizes Np(1-p)N-1 • for many nodes, take limit of Np*(1-p*)N-1 as N goes to infinity, gives: Max efficiency = 1/e = .37 Efficiency : long-run fraction of successful slots (many nodes, all with many frames to send) At best: channel used for useful transmissions 37% of time! !
Pure(unslotted)aLOHA unslotted Aloha: simpler, no synchronization When frame first arrives transmit immediately collision probability increases frame sent at to collides with other frames sent in [to- 1,to+1] will overlap will overlap with start of with end of ← i's frame is frame node i frame 0
Pure (unslotted) ALOHA • unslotted Aloha: simpler, no synchronization • when frame first arrives – transmit immediately • collision probability increases: – frame sent at t0 collides with other frames sent in [t0- 1,t0+1]
Pure Aloha Efficiency P(success by given node)=p(node transmits P(no other node transmits in [po-1, poI P(no other node transmits in [po-1, po p·(1-p)-1·(1-p) =p·(1-p)2(N-1 choosing optimum p and then letting n ->infty =1/(2e)=18 even worse than slotted aloha
Pure Aloha Efficiency P(success by given node) = P(node transmits) . P(no other node transmits in [p0-1,p0] . P(no other node transmits in [p0-1,p0] = p . (1-p)N-1 . (1-p)N-1 = p . (1-p)2(N-1) … choosing optimum p and then letting n -> infty ... = 1/(2e) = .18 even worse than slotted Aloha!
CSMA ( Carrier Sense Multiple access) CSMA: listen before transmit If channel sensed idle: transmit entire frame If channel sensed busy, defer transmission human analogy dont interrupt others
CSMA (Carrier Sense Multiple Access) CSMA: listen before transmit: If channel sensed idle: transmit entire frame • If channel sensed busy, defer transmission • human analogy: don’t interrupt others!
CSMA Collisions collisions can still occur: Space propagation delay means two nodes may not hear each other s transmission collision entire packet transmission time wasted note: role of distance& propagation delay in determining collision probabili spatial layout of nodes
CSMA Collisions collisions can still occur: propagation delay means two nodes may not hear each other’s transmission collision: entire packet transmission time wasted spatial layout of nodes note: role of distance & propagation delay in determining collision probability