Slotted ALOHA:efficiency efficiency:long-run fraction of successful slots (many nodes,all with many frames to send) 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 at best:channel used for useful transmissions 37%of time! Link Layer:6-26
efficiency: long-run fraction of successful slots (many nodes, all with many frames to send) ▪ 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 ▪ at best: channel used for useful transmissions 37% of time! Slotted ALOHA: efficiency Link Layer: 6-26
Pure ALOHA unslotted Aloha:simpler,no synchronization when frame first arrives:transmit immediately collision probability increases with no synchronization: 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 i's frame to-1 to to+1 pure Aloha efficiency:18%! Link Layer:6-27
Pure ALOHA Link Layer: 6-27 ▪ unslotted Aloha: simpler, no synchronization • when frame first arrives: transmit immediately ▪ collision probability increases with no synchronization: • frame sent at t0 collides with other frames sent in [t0 -1,t0+1] t t0 - 1 t0 0 + 1 will overlap with end of i’s frame will overlap with start of i’s frame ▪ pure Aloha efficiency: 18% !
CSMA(carrier sense multiple access) simple CSMA:listen before transmit: if channel sensed idle:transmit entire frame if channel sensed busy:defer transmission human analogy:don't interrupt others! CSMA/CD:CSMA with collision detection collisions detected within short time colliding transmissions aborted,reducing channel wastage collision detection easy in wired,difficult with wireless human analogy:the polite conversationalist Link Layer:6-28
CSMA (carrier sense multiple access) Link Layer: 6-28 simple CSMA: listen before transmit: • if channel sensed idle: transmit entire frame • if channel sensed busy: defer transmission ▪ human analogy: don’t interrupt others! CSMA/CD: CSMA with collision detection • collisions detected within short time • colliding transmissions aborted, reducing channel wastage • collision detection easy in wired, difficult with wireless ▪ human analogy: the polite conversationalist
CSMA:collisions spatial layout of nodes collisions can still occur with carrier sensing: propagation delay means two nodes to may not hear each other's just- t started transmission collision:entire packet transmission time wasted distance propagation delay play role inin determining collision probability Link Layer:6-29
CSMA: collisions Link Layer: 6-29 ▪ collisions can still occur with carrier sensing: • propagation delay means two nodes may not hear each other’s juststarted transmission ▪ collision: entire packet transmission time wasted • distance & propagation delay play role in in determining collision probability spatial layout of nodes
CSMA/CD: spatial layout of nodes CSMA/CS reduces the amount of time wasted in collisions transmission aborted on collision detection collision detect/abort time Link Layer:6-30
CSMA/CD: Link Layer: 6-30 ▪ CSMA/CS reduces the amount of time wasted in collisions • transmission aborted on collision detection spatial layout of nodes