Packet Multiple access ll Local Area Networks(LANs) Eytan Modiano Massachusetts Institute of Technology Department of Aeronautics and Astronautics Eytan Modiano
Packet Multiple Access II: Local Area Networks (LANs) Eytan Modiano Massachusetts Institute of Technology Department of Aeronautics and Astronautics Eytan Modiano Slide 1
CSMA/CD and Ethernet Two way cable wsws Ws W CSMA with Collision Detection(CD)capability Nodes able to detect collisions Upon detection of a collision nodes stop transmission Reduce the amount of time wasted on collisions Protocol All nodes listen to transmissions on the channel When a node has a packet to send Channel idle => Transmit Channel busy = wait a random delay (binary exponential backoff) If a transmitting node detects a collision it stops transmission Eytan Modiano Waits a random delay and tries again
CSMA/CD and Ethernet Two way cable WS WS WS WS WS WS • CSMA with Collision Detection (CD) capability – Nodes able to detect collisions – Upon detection of a collision nodes stop transmission Reduce the amount of time wasted on collisions • Protocol: – All nodes listen to transmissions on the channel – When a node has a packet to send: Channel idle => Transmit Channel busy => wait a random delay (binary exponential backoff) – If a transmitting node detects a collision it stops transmission Slide 2 Eytan Modiano Waits a random delay and tries again
Time to detect collisions T= prop WS /s delay a collision can occur while the signal propagates between the two nodes It would take an additional propagation delay for both users to detect the collision and stop transmitting If t is the maximum propagation delay on the cable then if a collision occurs, it can take up to 2t seconds for all nodes involved in the collision to detect and stop transmission Eytan Modiano
τ τ τ = Time to detect collisions WS τ WS τ = prop delay • A collision can occur while the signal propagates between the two nodes • It would take an additional propagation delay for both users to detect the collision and stop transmitting • If τ is the maximum propagation delay on the cable then if a collision occurs, it can take up to 2τ seconds for all nodes involved in the collision to detect and stop transmission Eytan Modiano Slide 3
A pproximate model for cSMA/CD Simplified approximation for added insight ● Consider a s| otted system with“mini- slots” of duration2τ packet minislots If a node starts transmission at the beginning of a mini-slot, by the end of the mini-slot either No collision occurred and the rest of the transmission will be uninterrupted A collision occurred, but by the end of the mini-slot the channel would be idle again Hence a collision at most affects one mini-slot Eytan Modiano
τ Approximate model for CSMA/CD • Simplified approximation for added insight • Consider a slotted system with “mini-slots” of duration 2τ −> 2τ<− <----------- 1 ----------------> packet minislots • If a node starts transmission at the beginning of a mini-slot, by the end of the mini-slot either – No collision occurred and the rest of the transmission will be uninterrupted – A collision occurred, but by the end of the mini-slot the channel would be idle again • Hence a collision at most affects one mini-slot Eytan Modiano Slide 4
Analysis of CSMA/CD Assume n users and that each attempts transmission during a free"mini-slot with probability p P includes new arrivals and retransmissions P(i users attempt)=.P(1-P) Plexactly 1 attempt=P(success)=NP(1-P) To maximize P(success), NP(1-P)1]=N(1P)-N(N-1)P(1-P 3 Average attempt rate of one per slot Notice the similarity to slotted Aloha Eytan Modiano
Analysis of CSMA/CD • Assume N users and that each attempts transmission during a free “mini-slot” with probability p – P includes new arrivals and retransmissions N i N −i P(i users attempt) = i P ( 1− P) P(exactly 1 attempt) = P(success) = NP(1 - P)N-1 To maximize P(success), d dp [NP(1 - P)N-1] = N(1 - P) N-1 − N(N − 1)P(1− P) N− 2 = 0 1 ⇒ P = opt N ⇒ Average attempt rate of one per slot ⇒ Notice the similarity to slotted Aloha Eytan Modiano Slide 5