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 <− <----------- 1 ----------------> • 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