Carrier-sense multiple access: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 09:51, 17 May 2024

Carrier-sense multiple access (CSMA) is a medium access control (MAC) protocol in which a node verifies the absence of other traffic before transmitting on a shared transmission medium, such as an electrical bus or a band of the electromagnetic spectrum.

Under CSMA, a transmitter uses a carrier-sense mechanism to determine whether another transmission is in progress before initiating a transmission. That is, it tries to detect the presence of a carrier signal from another node before attempting to transmit. If a carrier is sensed, the node waits for the transmission in progress to end before initiating its own transmission. Using CSMA, multiple nodes may, in turn, send and receive on the same medium. Transmissions by one node are generally received by all other nodes connected to the medium.

Variations on basic CSMA include addition of collision-avoidance (CSMA/CA), collision-detection (CSMA/CD) and collision-resolution techniques.

Access modes

Variations of CSMA use different algorithms to determine when to initiate transmission onto the shared medium. A key distinguishing feature of these algorithms is how aggressive or persistent they are in initiating transmission. A more aggressive algorithm may begin transmission more quickly and utilize a greater percentage of the available bandwidth of the medium. This is typically at the expense of an increased likelihood of collision with other transmitters.

1-persistent: 1-persistent CSMA is an aggressive transmission algorithm. When the transmitting node is ready to transmit, it senses the transmission medium for idle or busy. If idle, then it transmits immediately. If busy, then it senses the transmission medium continuously until it becomes idle, then transmits the message (a frame) unconditionally (i.e. with probability=1). In case of a collision, the sender waits for a random period of time and attempts the same procedure again. 1-persistent CSMA is used in CSMA/CD systems including Ethernet.

Non-persistent: Non persistent CSMA is a non-aggressive transmission algorithm. When the transmitting node is ready to transmit data, it senses the transmission medium for idle or busy. If idle, then it transmits immediately. If busy, it jumps to the final random waiting step of 1-persistent CSMA directly before repeating the whole logic cycle again: it does not persist in checking the busy channel trying to get its transmission through, hence the name. This approach reduces the chance of collision and results in overall higher medium throughput but with a penalty of longer initial delay compared to 1–persistent.

P-persistent: This approach lies between the 1-persistent and non-persistent CSMA access modes.^[1] When the transmitting node is ready to transmit data, it senses the transmission medium for idle or busy. If idle, then it transmits immediately. If busy, then it senses the transmission medium continuously until it becomes idle, then transmits with probability p. If the node does not transmit (the probability of this event is 1-p), it waits for a random period of time before re-attempting the same procedure, using the same probability p.^[2] If the transmission medium is not busy, it transmits again with the same probability p. This probabilistic hold-off repeats until the frame is finally transmitted or when the medium is found to become busy again (i.e. some other node has already started transmitting). In the latter case the node repeats the whole logic cycle (which started with sensing the transmission medium for idle or busy) again. p-persistent CSMA is used in CSMA/CA systems including Wi-Fi and other packet radio systems. Note that p = 0-persistent CSMA is different from non-persistent CSMA. Both can only transmit at the start of the procedure (if the channel is idle), but their behaviour on a busy channel differs: non-persistent CSMA doesn't attempt to sense the channel and restarts its logical cycle, whilst p = 0 necessarily gets stuck in an infinite loop of waiting (since it has zero probability of transmission even if the channel goes back to being idle).

O-persistent: Each node is assigned a transmission order by a supervisory node. When the transmission medium goes idle, nodes wait for their time slot in accordance with their assigned transmission order. The node assigned to transmit first transmits immediately. The node assigned to transmit second waits one time slot (but by that time the first node has already started transmitting). Nodes monitor the medium for transmissions from other nodes and update their assigned order with each detected transmission (i.e. they move one position closer to the front of the queue).^[3] O-persistent CSMA is used by CobraNet, LonWorks and the controller area network.

Protocol modifications

When broadcasting over vehicular ad hoc networks, the original 1-persistence and p-persistence strategies often cause the broadcast storm problem.^{[citation needed]} To improve performance, engineers developed three modified techniques: weighted p-persistence, slotted 1-persistence, and slotted p-persistence.^[4]^[5]

Carrier-sense multiple access with collision detection: CSMA/CD is used to improve CSMA performance by terminating transmission as soon as a collision is detected, thus shortening the time required before a retry can be attempted. CSMA/CD is used by Ethernet.

Carrier-sense multiple access with collision avoidance: In CSMA/CA collision avoidance is used to improve the performance of CSMA. If the transmission medium is sensed busy before transmission, then the transmission is deferred for a random interval. This random interval reduces the likelihood that two or more nodes waiting to transmit will simultaneously begin transmission upon termination of the detected transmission, thus reducing the incidence of collision. CSMA/CA is used by Wi-Fi.

CSMA with Collision Resolution: CSMA/CR uses priorities in the frame header to avoid collisions. It is used in the Controller Area Network.

Virtual time CSMA: VTCSMA is designed to avoid collision generated by nodes transmitting signals simultaneously, used mostly in hard real-time systems. It uses two clocks to prioritize messages based on their deadline.^[6]

References

^ F. Calí, M. Conti, and E. Gregori, "Dynamic IEEE 802.11: design, modeling and performance evaluation," IEEE J. Selected Areas Commun., vol. 18, pp. 1774–1786, Sept. 2000
^ Kleinrock, L.; Tobagi, F. (December 1975). "Packet Switching in Radio Channels: Part I--Carrier Sense Multiple-Access Modes and Their Throughput-Delay Characteristics". IEEE Transactions on Communications. 23 (12): 1400–1416. doi:10.1109/TCOM.1975.1092768. ISSN 0096-2244. S2CID 5879608.
^ US 5761431, Gross, Kevin Paul; Anderson, Charles William & Lieb, Derek Wearin, "Order persistent timer for controlling events at multiple processing stations", published 1998-06-02, assigned to Peak Audio Inc.
^ Najafzadeh; Ithnin; Karimi. "An Analytical Model for Sparse and Dense Vehicular Ad hoc Networks". "Advances in Computer Science and Information Technology": First International Conference on Computer Science and Information Technology, CCSIT 2011. p. 211.
^ Choi et al.: "Robust broadcast scheme regardless of vehicle distribution in vehicular ad hoc networks". EURASIP Journal on Wireless Communications and Networking 2014 2014:133. doi:10.1186/1687-1499-2014-133 [accessed Sep 2, 2017].
^ Krishna, C. M.; Shin, K. G. (1997). Real-Time Systems. McGraw-Hill Higher Education. p. 240. ISBN 978-0-07-070115-1.

General

Andrew S. Tanenbaum, Computer Networks. Prentice Hall, Upper Saddle River, NJ (2003). 892 pp. ISBN 0-13-066102-3

[1] F. Calí, M. Conti, and E. Gregori, "Dynamic IEEE 802.11: design, modeling and performance evaluation," IEEE J. Selected Areas Commun., vol. 18, pp. 1774–1786, Sept. 2000

[2] Kleinrock, L.; Tobagi, F. (December 1975). "Packet Switching in Radio Channels: Part I--Carrier Sense Multiple-Access Modes and Their Throughput-Delay Characteristics". IEEE Transactions on Communications. 23 (12): 1400–1416. doi:10.1109/TCOM.1975.1092768. ISSN 0096-2244. S2CID 5879608.

[3] US 5761431, Gross, Kevin Paul; Anderson, Charles William & Lieb, Derek Wearin, "Order persistent timer for controlling events at multiple processing stations", published 1998-06-02, assigned to Peak Audio Inc.

[4] Najafzadeh; Ithnin; Karimi. "An Analytical Model for Sparse and Dense Vehicular Ad hoc Networks". "Advances in Computer Science and Information Technology": First International Conference on Computer Science and Information Technology, CCSIT 2011. p. 211.

[5] Choi et al.: "Robust broadcast scheme regardless of vehicle distribution in vehicular ad hoc networks". EURASIP Journal on Wireless Communications and Networking 2014 2014:133. doi:10.1186/1687-1499-2014-133 [accessed Sep 2, 2017].

[6] Krishna, C. M.; Shin, K. G. (1997). Real-Time Systems. McGraw-Hill Higher Education. p. 240. ISBN 978-0-07-070115-1.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 1: / Line 1: @@
-{{short description|system allowing transmitters to take turns on a shared media}}
+{{short description|System allowing transmitters to take turns on a shared media}}
-'''Carrier-sense multiple access''' ('''CSMA''') is a [[media access control]] (MAC) protocol in which a node verifies the absence of other [[Network traffic|traffic]] before [[Transmission (telecommunications)|transmitting]] on a shared [[transmission medium]], such as an [[Bus (computing)|electrical bus]] or a band of the [[electromagnetic spectrum]].
+'''Carrier-sense multiple access''' ('''CSMA''') is a [[medium access control]] (MAC) protocol in which a node verifies the absence of other [[Network traffic|traffic]] before [[Transmission (telecommunications)|transmitting]] on a shared [[transmission medium]], such as an [[Bus (computing)|electrical bus]] or a band of the [[electromagnetic spectrum]].
-A [[transmitter]] attempts to determine whether another transmission is in progress before initiating a transmission using a carrier-sense mechanism. That is, it tries to detect the presence of a [[carrier signal]] from another node before attempting to transmit. If a carrier is sensed, the node waits for the transmission in progress to end before initiating its own transmission. Using CSMA, multiple nodes may, in turn, send and receive on the same medium. Transmissions by one node are generally received by all other nodes connected to the medium.
+Under CSMA, a [[transmitter]] uses a carrier-sense mechanism to determine whether another transmission is in progress before initiating a transmission. That is, it tries to detect the presence of a [[carrier signal]] from another node before attempting to transmit. If a carrier is sensed, the node waits for the transmission in progress to end before initiating its own transmission. Using CSMA, multiple nodes may, in turn, send and receive on the same medium. Transmissions by one node are generally received by all other nodes connected to the medium.
-Variations on basic CSMA include addition of [[Collision (telecommunications)|collision]]-avoidance, collision-detection and collision-resolution techniques.
+Variations on basic CSMA include addition of [[Collision (telecommunications)|collision]]-avoidance ([[CSMA/CA]]), collision-detection ([[CSMA/CD]]) and collision-resolution techniques.
 ==Access modes==
-Variations of CSMA use different algorithms to determine when to initiate transmission onto the shared medium. A key distinguishing feature of these algorithms is how aggressive or persistent they are in initiating transmission. A more aggressive algorithm may begin transmission more quickly and utilize a greater percentage of available bandwidth of the medium. This is typically at the expense of increased likelihood of collision with other transmitters.
+Variations of CSMA use different algorithms to determine when to initiate transmission onto the shared medium. A key distinguishing feature of these algorithms is how aggressive or persistent they are in initiating transmission. A more aggressive algorithm may begin transmission more quickly and utilize a greater percentage of the available bandwidth of the medium. This is typically at the expense of an increased likelihood of collision with other transmitters.
 ; 1-persistent : 1-persistent CSMA is an aggressive transmission algorithm. When the transmitting node is ready to transmit, it senses the transmission medium for idle or busy. If idle, then it transmits immediately. If busy, then it senses the transmission medium continuously until it becomes idle, then transmits the message (a [[Frame (telecommunications)|frame]]) unconditionally (i.e. with probability=1). In case of a [[Collision (telecommunications)|collision]], the sender waits for a [[Randomness|random]] period of time and attempts the same procedure again. 1-persistent CSMA is used in CSMA/CD systems including [[Ethernet]].
-; Non-persistent : Non persistent CSMA is a non-aggressive transmission algorithm. When the transmitting node is ready to transmit data, it senses the transmission medium for idle or busy. If idle, then it transmits immediately. If busy, then, instead of persisting in checking the channel, it jumps to the final step of 1-persistent CSMA directly (i.e.: it starts waiting for a random period of time during which it does not sense the transmission medium) before repeating the whole logic cycle again. This approach reduces collision, results in overall higher medium throughput but with a penalty of longer initial delay compared to 1–persistent. Note: non-persistent shouldn't be seen as "p=0-persistent", because although the latter can also only transmit if the channel is idle at the start of the procedure, it would get stuck in an infinite loop of waiting, whilst non-persistent never enters that loop.
+; Non-persistent : Non persistent CSMA is a non-aggressive transmission algorithm. When the transmitting node is ready to transmit data, it senses the transmission medium for idle or busy. If idle, then it transmits immediately. If busy, it jumps to the final random waiting step of 1-persistent CSMA directly before repeating the whole logic cycle again: it does not persist in checking the busy channel trying to get its transmission through, hence the name. This approach reduces the chance of collision and results in overall higher medium throughput but with a penalty of longer initial delay compared to 1–persistent.
-; P-persistent : This is an approach between 1-persistent and non-persistent CSMA access modes.<ref>F. Calí, M. Conti, and E. Gregori, "Dynamic IEEE 802.11: design, modeling
+; P-persistent : This approach lies between the 1-persistent and non-persistent CSMA access modes.<ref>F. Calí, M. Conti, and E. Gregori, "Dynamic IEEE 802.11: design, modeling
-and performance evaluation," IEEE J. Selected Areas Commun., vol. 18, pp. 1774–1786, Sept. 2000</ref> When the transmitting node is ready to transmit data, it senses the transmission medium for idle or busy. If idle, then it transmits immediately. If busy, then it senses the transmission medium continuously until it becomes idle, then transmits with probability ''p''. If the node does not transmit (the probability of this event is ''1-p''), it waits until the next available [[Time-division multiple access|time slot]]. If the transmission medium is not busy, it transmits again with the same probability ''p''. This probabilistic hold-off repeats until the frame is finally transmitted or when the medium is found to become busy again (i.e. some other node has already started transmitting). In the latter case the node repeats the whole logic cycle (which started with sensing the transmission medium for idle or busy) again. p-persistent CSMA is used in CSMA/CA systems including [[Wi-Fi]] and other [[packet radio]] systems.
+and performance evaluation," IEEE J. Selected Areas Commun., vol. 18, pp. 1774–1786, Sept. 2000</ref> When the transmitting node is ready to transmit data, it senses the transmission medium for idle or busy. If idle, then it transmits immediately. If busy, then it senses the transmission medium continuously until it becomes idle, then transmits with probability ''p''. If the node does not transmit (the probability of this event is ''1-p''), it waits for a [[Randomness|random]] period of time before re-attempting the same procedure, using the same probability ''p''.<ref>{{Cite journal |last1=Kleinrock |first1=L. |last2=Tobagi |first2=F. |date=December 1975 |title=Packet Switching in Radio Channels: Part I--Carrier Sense Multiple-Access Modes and Their Throughput-Delay Characteristics |url=https://ieeexplore.ieee.org/document/1092768 |journal=IEEE Transactions on Communications |language=en |volume=23 |issue=12 |pages=1400–1416 |doi=10.1109/TCOM.1975.1092768 |s2cid=5879608 |issn=0096-2244}}</ref> If the transmission medium is not busy, it transmits again with the same probability ''p''. This probabilistic hold-off repeats until the frame is finally transmitted or when the medium is found to become busy again (i.e. some other node has already started transmitting). In the latter case the node repeats the whole logic cycle (which started with sensing the transmission medium for idle or busy) again. p-persistent CSMA is used in CSMA/CA systems including [[Wi-Fi]] and other [[packet radio]] systems. Note that ''p = 0''-persistent CSMA is different from non-persistent CSMA. Both can only transmit at the start of the procedure (if the channel is idle), but their behaviour on a busy channel differs: non-persistent CSMA doesn't attempt to sense the channel and restarts its logical cycle, whilst ''p = 0'' necessarily gets stuck in an infinite loop of waiting (since it has zero probability of transmission even if the channel goes back to being idle).
-; O-persistent : Each node is assigned a transmission order by a supervisory node. When the transmission medium goes idle, nodes wait for their time slot in accordance with their assigned transmission order. The node assigned to transmit first transmits immediately. The node assigned to transmit second waits one time slot (but by that time the first node has already started transmitting). Nodes monitor the medium for transmissions from other nodes and update their assigned order with each detected transmission (i.e. they move one position closer to the front of the queue).<ref>{{Cite patent|US|5761431}}</ref> O-persistent CSMA is used by [[CobraNet]], [[LonWorks]] and the [[controller area network]].
+; O-persistent : Each node is assigned a transmission order by a supervisory node. When the transmission medium goes idle, nodes wait for their time slot in accordance with their assigned transmission order. The node assigned to transmit first transmits immediately. The node assigned to transmit second waits one time slot (but by that time the first node has already started transmitting). Nodes monitor the medium for transmissions from other nodes and update their assigned order with each detected transmission (i.e. they move one position closer to the front of the queue).<ref>{{Cite patent|country=US|number=5761431|pubdate=1998-06-02|title=Order persistent timer for controlling events at multiple processing stations|assign1=Peak Audio Inc.|inventor1-last=Gross|inventor1-first=Kevin Paul|inventor2-last=Anderson|inventor2-first=Charles William|inventor3-last=Lieb|inventor3-first=Derek Wearin}}</ref> O-persistent CSMA is used by [[CobraNet]], [[LonWorks]] and the [[controller area network]].
 ==Protocol modifications==
-When broadcasting over vehicular ad hoc networks, the original 1-persistence and p-persistence strategies often cause the [[broadcast storm]] problem.{{cn|date=November 2018}} To improve performance, engineers developed three modified techniques: weighted p-persistence, slotted 1-persistence, and slotted p-persistence.<ref>
+When broadcasting over vehicular ad hoc networks, the original 1-persistence and p-persistence strategies often cause the [[broadcast storm]] problem.{{citation needed|date=November 2018}} To improve performance, engineers developed three modified techniques: weighted p-persistence, slotted 1-persistence, and slotted p-persistence.<ref>
 Najafzadeh; Ithnin; Karimi.
 "An Analytical Model for Sparse and Dense Vehicular Ad hoc Networks".
@@ Line 43: / Line 44: @@
 ;Virtual time CSMA
-:VTCSMA is designed to avoid collision generated by nodes transmitting signals simultaneously, used mostly in hard [[Real-time computing|real-time systems]]. It uses two clocks to prioritize messages based on their deadline.<ref>{{cite book |last1=Krishna |first1=C. M. |last2=Shin |first2=K. G. |date=1997 |title=Real-Time Systems |url=https://www.amazon.com/Real-Time-Systems-Mcgraw-Hill-Computer-Science/dp/0070570434/ |publisher=McGraw-Hill Higher Education |page=240 |isbn=978-0-07-070115-1 }}</ref>
+:VTCSMA is designed to avoid collision generated by nodes transmitting signals simultaneously, used mostly in hard [[Real-time computing|real-time systems]]. It uses two clocks to prioritize messages based on their deadline.<ref>{{cite book |last1=Krishna |first1=C. M. |last2=Shin |first2=K. G. |date=1997 |title=Real-Time Systems |publisher=McGraw-Hill Higher Education |page=240 |isbn=978-0-07-070115-1 }}</ref>
 ==See also==