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τ 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
Analysis of CSMA/CD, continued P(success)=NP(1-p)=(1 N s= limit(N>oo)P(success) et X Average number of slots per succesful transmission P(X=)=(1P)1 EⅨX e Once a mini-slot has been successfully captured, transmission continues without interruption New transmission attempts will begin at the next mini-slot after the end of the current packet transmission Eytan Modiano
Analysis of CSMA/CD, continued 1 P(success) =NP(1 - p)N-1 = (1− N) N −1 1 Ps = limit (N → ∞) P(success) = e Let X = Average number of slots per succesful transmission − P(X = i) = (1 - Ps )i 1 Ps 1 ⇒ E[X] = = e Ps • Once a mini-slot has been successfully captured, transmission continues without interruption • New transmission attempts will begin at the next mini-slot after the end of the current packet transmission Eytan Modiano Slide 6
Analysis of CSMA/CD, continued Let s average amount of time between successful packet transmissions s=(e-1)2τ+D+t t Ave time until start of next Mini-slot dle/collision Mini-slots Packet transmission time Efficiency =D /S= Dn / D +t+ 2i(e-1) °Let阝=tDn=> Efficiency=1(1+445)=≤11t24) Eytan Modiano
τ τ τ τ β τ ≈ β λ β Analysis of CSMA/CD, continued • Let S = Average amount of time between successful packet transmissions S = (e-1)2τ + DTp + τ Ave time until start of next Mini-slot Idle/collision Mini-slots Packet transmission time • Efficiency = DTp/S = DTp / (DTp + τ + 2τ(e-1)) • Let β = τ/ DTp => Efficiency ≈ 1/(1+4.4β) = λ < 1/(1+4.4β) Eytan Modiano Slide 7
Notes on CSMA/CD Can be viewed as a reservation system where the mini-slots are used for making reservations for data slots In this case, Aloha is used for making reservations during the mini-slots Once a users captures a mini-slot it continues to transmit without interruptions In practice, of course, there are no mini-slots Minimal impact on performance but analysis is more complex Eytan Modiano
Notes on CSMA/CD • Can be viewed as a reservation system where the mini-slots are used for making reservations for data slots • In this case, Aloha is used for making reservations during the mini-slots • Once a users captures a mini-slot it continues to transmit without interruptions • In practice, of course, there are no mini-slots – Minimal impact on performance but analysis is more complex Eytan Modiano Slide 8
CSMA/CD examples Example( Ethernet) Transmission rate 10 Mbps Packet length= 1000 bits, D o=10-4sec Cable distance =1 mile, t= 5x10- sec B=5x102andE=80% Example(GEO Satellite)-propagation delay 1/4 second B=2,500andE~0% CSMA/CD only suitable for short propagation scenarios! How is Ethernet extended to 100 Mbps? How is Ethernet extended to 1 Gbps?
τ β β CSMA/CD examples • Example (Ethernet) – Transmission rate = 10 Mbps – Packet length = 1000 bits, DTp = 10-4 sec – Cable distance = 1 mile, τ = 5x10-6 sec – β = 5x10-2 and E = 80% • Example (GEO Satellite) - propagation delay 1/4 second – β = 2,500 and E ~ 0% • CSMA/CD only suitable for short propagation scenarios! • How is Ethernet extended to 100 Mbps? • How is Ethernet extended to 1 Gbps? Eytan Modiano Slide 9
Token rings Token rings were developed by IBM in early 1980s Token: a bit sequence Token circulates around the ring Busy token: 01111111 Free token :01111110 Token Ring When a node wants to transmit Wait for free token Remove token from ring(replace with busy token) Transmit message When done transmitting, replace free token on ring Nodes must buffer 1 bit of data so that a free token can be changed to a busy token Token ring is basically a polling system Token does the polling Slide 10
Token rings • Token rings were developed by IBM in early 1980’s • Token: a bit sequence – Token circulates around the ring Busy token: 01111111 Free token: 01111110 • When a node wants to transmit – Wait for free token – Remove token from ring (replace with busy token) – Transmit message – When done transmitting, replace free token on ring – Nodes must buffer 1 bit of data so that a free token can be changed to a busy token • Token ring is basically a polling system Token does the polling Token Ring Eytan Modiano Slide 10