Lectures 15&16 Local area networks Eytan Modiano
Lectures 15 & 16 Local Area Networks Eytan Modiano Eytan Modiano Slide 1
Carrier Sense Multiple Access(CSMA) In certain situations nodes can hear each other by listening to the channel “ Carrier Sensing CSMA: Polite version of aloha Nodes listen to the channel before they start transmission Channel idle = Transmit Channel busy = Wait goin backlog) When do backlogged nodes transmit? When channel becomes idle backlogged nodes attempt transmission with probability q=1 Persistent protocol, =1 Non-persistent protocol, g 1
Carrier Sense Multiple Access (CSMA) • In certain situations nodes can hear each other by listening to the channel - “Carrier Sensing” • CSMA: Polite version of Aloha – Nodes listen to the channel before they start transmission Channel idle => Transmit Channel b usy => Wait (join backlog) – W h e n do backlogged nodes t r a nsmit? When channel becomes idle bac klogged nodes att empt tran s mission with probability qr= 1 Persistent protocol, qr= 1 Non-persistent protocol, qr< 1 Eytan Modiano Slide 2
CSMA Let t s the maximum propagation delay on the channel When a node starts/stops transmitting, it will take this long for all nodes to detect channel busy/idle For initial understanding, view the system as slotted with mini- slots"of duration equal to the maximum propagation delay Normalize the mini-slot duration to p=t/Dtp and packet duration= 1 <---11 packet minislots Actual systems are not slotted, but this hypothetical system simplifies the analysis and understanding of CSMA
CSMA • Let τ = the maximum propagation delay on the channel – When a node starts/stops transmitting, it will take this long for all nodes to detect channel busy/idle • For initial understanding, view the system as slotted with "minislots" of duration equal to the maximum propagation delay – Normalize the mini-slot duration to β = τ/Dtp and packet duration = 1 −> β packet minislots • Actual systems are not slotted, but this hypothetical system simplifies the analysis and understanding of CSMA Eytan Modiano Slide 3
Rules for slotted csma When a new packet arrives If current mini-slot is idle, start transmitting in the next mini-slot If current mini-slot is busy, node joins backlog If a collision occurs, nodes involved in collision become backlogged Backlogged nodes attempt transmission after an idle mini-slot with probability qr <1(non-persistent Transmission attempts only follow an idle mini-slot Each busy-period"(success or collision )is followed by an idle slot before a new transmission can begin Time can be divided into epochs A successful packet followed by an idle mini-slot (duration=B+1) A collision followed by an idle mini-slot (duration=B+1) An idle minislot (duration=B)
Rules for slotted CSMA • When a new packet arrives – If current mini-slot is idle, start transmitting in the next mini-slot – If current minislot is busy, node joins backlog – If a collision occurs, nodes involved in collision become backlogged • Backlogged nodes attempt transmission after an idle mini-slot with probability qr < 1 (non-persistent) – Transmission attempts only follow an idle mini-slot – Each”busy-period” (success or collision) is f ollowed by an idle slot before a new transmission can begin • Time can be divided into epochs: – A successful packet followed by an idle mini-slot (duration = β+1) – A collision followed by an idle mini-slot (duration = β+1) – An idle minislot (duration = β) Eytan Modiano Slide 4
DAnalysis of CSMA Let the state of the system be the number of backlogged nodes Let the state transition times be the end of idle slots Let t(n)= average amount of time between state transitions when the system is in state n T(n)=β+(1-e(1-q When gr is small (1-a)n-e-qn=>T(n)=B+(1-e-p-ngr) At the beginning of each epoch, each backlogged node transmits with probabilit lity gr New arrivals during the previous idle slot are also transmitted With backlog n, the number of packets that attempt transmission at the beginning of an epoch is approximately Poisson with rate gn)=β+nq
�Analysis of CSMA • Let the state of the system be the number of backlogged nodes • Let the state transition times be the end of idle slots – Let T(n) = average amount of time between state transitions when the system is in state n T(n) = β + (1 - e-λβ (1-qr)n) When qr is small (1-qr)n ~ e-qrn => T(n) = β + (1 - e-λβ−nqr ) • At the beginning of each epoch, each backlogged node transmits with probability qr • New arrivals during the previous idle slot are also transmitted • With backlog n, the number of packets that attempt transmission at the beginning of an epoch is approximately Poisson with rate g(n) = λβ + nqr Eytan Modiano Slide 5
Analysis of CSMA The probability of success (per epoch)is Ps=g(n)e-g(n) The expected duration of an epoch is approximately T(n)~β+(1-e9) Thus the success rate per unit time is n <departure rate 8(m)le-8(m) B+1 e&(n)
Analysis of CSMA • The probability of success (per epoch) is Ps = g(n) e-g(n) • The expected duration of an epoch is approximately T(n) ~ β + (1 - e-g(n) ) • Thus the success rate per unit time is g(n)e− g(n) λ < departure rate= β +1− e− g(n) Eytan Modiano Slide 6
Maximum Throughput for CSMa The optimal value of g(n can again be obtained: g(n)≈√2月 < l+√2B Tradeoff between idle slots and time wasted on collisions High throughput when B is small Stability issues similar to aloha (less critical) Departure rate Arrival rate 入β+
Maximum Throughput for CSMA • The optimal value of g(n) can again be obtained: 1 g ( n ) ≈ 2 β λ < 1 + 2 β • Tradeoff between idle slots and time wasted on collisions • High throughput when β is small • Stability issues similar to Aloha (less critical) 1-¦2 β Arrival rate Departure rate g(n) = λβ r + nq Eytan Modiano ¦2 β Slide 7
Unslotted CSMA Slotted csMA is not practical Difficult to maintain synchronization Mini-slots are useful for understanding but not critical to the performance of CSMA Unslotted CSMA will have slightly lower throughput due to increased probability of collision Unslotted CSMa has a smaller effective value of B than slotted CSMA Essentially B becomes average instead of maximum propagation delay
Unslotted CSMA • Slotted CSMA is not practical – Difficult to maintain synchronization – Mini-slots are useful for understanding but not critical to the performance of CSMA • Unslotted CSMA will have slightly lower throughput due to increased probability of collision • Unslotted CSMA has a smaller effective value of β than slotted CSMA – Essentially β becomes average instead of maximum propagation delay Eytan Modiano Slide 8
CSMA/CD and Ethernet Two way cable wswswswswS 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 Waits a random delay and tries again
CSMA/CD and Ethernet Two way cable WS WS WS WS WS WS • CSMA with C ollision Detection (CD) capability – Nodes able to detect collisions – Upon detection of a collision nodes stop transmission Reduce the amount of ti m e wasted on collisions • Protocol: – All nodes listen to transmissions on the channel – When a node has a packet to send: Chann el idle = > T ransmit Channel busy => wait a random dela y (binary exponential backoff) – If a transmitting node detects a collision it stops transmission Eytan Modiano Waits a random dela y and tries again Slide 9
Time to detect collisions C= prop t wS 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
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 10