Lecture Today slotted vs unslotted ALOHA Carrier sensing multiple access Ethernet DataLink Layer 1 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 DataLink Layer 2 1 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 DataLink Layer 3 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 DataLink Layer 4 2 Slotted Aloha efficiency Efficiency is the long run fraction of successful slots when there are many nodes each with many frames to send N nodes with many frames to send each transmits in slot with probability q new arrival or re Tx prob that node 1 has success in a slot For max efficiency with N nodes find q that maximizes Nq 1 q N 1 For many nodes take limit of Nq 1 q N 1 as N goes to infinity gives 1 e 37 q 1 q N 1 At best channel used for useful transmissions 37 of time Total expected utilization Nq 1 q N 1 DataLink Layer 5 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 DataLink Layer 6 3 Pure Aloha efficiency P success by given node P node transmits at to P no other node transmits in t0 1 t0 P no other node transmits in t0 t0 1 q 1 q N 1 1 q N 1 q 1 q 2 N 1 choosing optimum q and then letting N infty Even worse 1 2e 18 DataLink Layer 7 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 Do we then get effective channel partitioning with no collisions possible DataLink Layer 8 4 CSMA collisions spatial layout of nodes collisions can still occur propagation delay means two nodes may not hear each other s transmission collision entire packet transmission time wasted note role of propagation delay in determining collision probability DataLink Layer 9 CSMA Efficiency Key parameters Propagation delay in seconds tprop packet transmission time ttrans Efficiency depends only on tprop ttran and decreases with this parameter DataLink Layer 10 5 CSMA Efficiency Decreases with tprop ttrans Decreases with increasing distance between nodes t trans R L where R is the link speed in bits s and L is the frame length in bits So efficiency decreases with increasing link speed R DataLink Layer 11 CSMA CD Collision Detection CSMA CD carrier sensing deferral as in CSMA collisions detected within short time colliding transmissions aborted reducing channel wastage collision detection easy in wired LANs measure signal strengths compare transmitted received signals difficult in wireless LANs receiver shut off while transmitting human analogy the polite conversationalist DataLink Layer 12 6 CSMA CD collision detection DataLink Layer 13 Ethernet dominant wired LAN technology cheap 20 for 100Mbs first widely used LAN technology Simpler cheaper than token LANs and ATM Kept up with speed race 10 Mbps 10 Gbps Metcalfe s Ethernet sketch DataLink Layer 14 7 Star topology Bus topology popular through mid 90s Now star topology prevails hub DataLink Layer 15 Unreliable connectionless service Connectionless No handshaking between sending and receiving adapter Unreliable receiving adapter doesn t send acks or nacks to sending adapter stream of datagrams passed to network layer can have gaps gaps will be filled if app is using TCP otherwise app will see the gaps DataLink Layer 16 8 Ethernet uses CSMA CD No slots adapter doesn t transmit if it senses that some other adapter is transmitting that is carrier sense transmitting adapter aborts when it senses that another adapter is transmitting that is collision detection Before attempting a retransmission adapter waits a random time that is random access DataLink Layer 17 Ethernet CSMA CD algorithm 1 Adaptor receives 4 If adapter detects datagram from net layer another transmission while creates frame transmitting aborts and sends jam signal 2 If adapter senses channel idle it starts to transmit 5 After aborting adapter frame If it senses enters exponential channel busy waits until backoff after the mth channel idle and then collision adapter chooses transmits a K at random from 0 1 2 2m 1 Adapter 3 If adapter transmits waits K 512 bit times and entire frame without returns to Step 2 detecting another transmission the adapter is done with frame DataLink Layer 18 9
View Full Document
Unlocking...