Channel Partitioning MAC protocols:FDMA FDMA:frequency division multiple access channel spectrum divided into frequency bands each station assigned fixed frequency band unused transmission time in frequency bands go idle example:6-station LAN,1,3,4 have pkt,frequency bands 2,5,6 idle time 5:DataLink Layer 5-21
5: DataLink Layer 5-21 Channel Partitioning MAC protocols: FDMA FDMA: frequency division multiple access channel spectrum divided into frequency bands each station assigned fixed frequency band unused transmission time in frequency bands go idle example: 6-station LAN, 1,3,4 have pkt, frequency bands 2,5,6 idle frequency bands
Random Access Protocols When node has packet to send o transmit at full channel data rate R. o no a priori coordination among nodes two or more transmitting nodes "collision", random access MAC protocol specifies: o how to detect collisions o how to recover from collisions (e.g.,via delayed retransmissions) Examples of random access MAC protocols: o slotted ALOHA o ALOHA o CSMA,CSMA/CD,CSMA/CA 5:DataLink Layer 5-22
5: DataLink Layer 5-22 Random Access Protocols When node has packet to send transmit at full channel data rate R. no a priori coordination among nodes two or more transmitting nodes ➜ “collision”, random access MAC protocol specifies: how to detect collisions how to recover from collisions (e.g., via delayed retransmissions) Examples of random access MAC protocols: slotted ALOHA ALOHA CSMA, CSMA/CD, CSMA/CA
Slotted ALOHA Assumptions Operation all frames same size when node obtains fresh time is divided into frame,it transmits in next equal size slots,time to slot transmit 1 frame no collision,node can send nodes start to transmit new frame in next slot frames only at if collision,node beginning of slots retransmits frame in each nodes are synchronized subsequent slot with prob. ▣if2 or more nodes p until success transmit in slot,all nodes detect collision 5:DataLink Layer 5-23
5: DataLink Layer 5-23 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 node node 2 node 3 Pros Cons single active node can collisions,wasting slots continuously transmit idle slots at full rate of channel ▣nodes may be able to highly decentralized: detect collision in less only slots in nodes than time to transmit need to be in sync packet clock synchronization simple 5:DataLink Layer 5-24
5: DataLink Layer 5-24 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 clock synchronization
Slotted Aloha efficiency Efficiency is the long-run ▣For max efficiency fraction of successful slots with N nodes,find p* when there are many nodes, that maximizes each with many frames to send Np(1-p)N-1 ▣For many nodes,take ▣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 ▣prob that node1has At best:channel success in a slot used for useful =p(1-p)N-1 transmissions 37% 口prob that any node has of time! a success Np(1-p)N-1 5:DataLink Layer 5-25
5: DataLink Layer 5-25 Slotted Aloha efficiency Suppose N nodes with many frames to send, each transmits in slot with probability p prob that node 1 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 are many nodes, each with many frames to send At best: channel used for useful transmissions 37% of time!