Slotted aLOHA Assumptions Operation 口 all frames same size o when node obtains fresh o time is divided into frame, it transmits in next equal size slots, time to slot transmit 1 frame g no collision node can send g nodes start to transmit new frame in next slot frames only at 口 F collision,node beginning of slots retransmits frame in each O nodes are synchronized subsequent slot with prob 计f2 or more nodes p until success transmit in slot all nodes detect collision 5: DataLink Layer 5a-26
5: DataLink Layer 5a-26 Slotted ALOHA Assumptions all frames same size time is divided into equal size slots, time to transmit 1 frame nodes start to transmit frames only at beginning of slots nodes are synchronized if 2 or more nodes transmit in slot, all nodes detect collision Operation when node obtains fresh frame, it transmits in next slot no collision, node can send new frame in next slot if collision, node retransmits frame in each subsequent slot with prob. p until success
Slotted ALOHA node11 node 2 2 node 3 C E C S E C E SS Pros Cons o single active node can o collisions, wasting slots continuously transmit o idle slots at full rate of channel 口 nodes may be able to o highly decentralized detect collision in less only slots in nodes than time to transmit need to be in sync packet D simple 5: DataLink Layer 5a-27
5: DataLink Layer 5a-27 Slotted ALOHA Pros single active node can continuously transmit at full rate of channel highly decentralized: only slots in nodes need to be in sync simple Cons collisions, wasting slots idle slots nodes may be able to detect collision in less than time to transmit packet
Slotted Aloha efficiency Efficiency is the long-run o For max efficiency fraction of successful slots with N nodes, find p when there' s many nodes, each that maximizes with many frames to send Np(1-p)N-1 口 For many nodes,take D Suppose n nodes with limit of np大(1-p*)N-1 many frames to send, as n goes to infinity each transmits in slot gIves 1/e 37 with probability p D prob that 1st node has At best: channel success in a slot used for useful p(1-P)N- transmissions 37% o prob that any node has of time! a success= Np(1-P)N 5: Datalink layer 5a-28
5: DataLink Layer 5a-28 Slotted Aloha efficiency Suppose N nodes with many frames to send, each transmits in slot with probability p prob that 1st node has success in a slot = p(1-p)N-1 prob that any node has a success = Np(1-p)N-1 For max efficiency with N nodes, 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 1/e = .37 Efficiency is the long-run fraction of successful slots when there’s many nodes, each with many frames to send At best: channel used for useful transmissions 37% of time!
Pure unslotted) ALOHA D unslotted Aloha: simpler no synchronization D when frame first arrives o transmit immediately o collision probability increases o frame sent at to collides with other frames sent in [to-1, to+1 will overlap ill overlap with start of with end of i' s frame→←- is frame node i frame 0 t+1 5: Datalink layer 5a-29
5: DataLink Layer 5a-29 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, po P(no other node transmits in [po-1, po p·(1→p 1 =p.(1-p)2N-1) choosing optimum p and then letting n-> infty Even worse/=1/(2e)=18 5: Datalink layer 5a-30
5: DataLink Layer 5a-30 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 !