Which Carrier Sense technology is used on wireless networks to reduce collision?

P-Persistent CSMA

The p-persistent CSMA algorithm takes a moderate approach between nonpersistent and 1-persistent CSMA. It specifies a value; the probability of transmission after detecting the medium is idle. The station first checks if the medium is idle, transmits a frame with the probability P if it is idle, and delays one time unit of maximum propagation delay with 1-P. If the medium is busy, the station continues to listen until the channel is idle and repeats the same procedure when the medium is idle. In general, at the heavier load, decreasing P would reduce the number of collisions. At the lighter load, increasing P would avoid the delay and improve the utilization. The value of P can be dynamically adjusted based on the traffic load of the network.

CSMA/CD is the result of the evolution of these earlier protocols and the additions of two capabilities to CSMA protocols. The first capability is the listening during the transmission; the second one is the transmission of the minimum frame size to ensure that the transmission time is longer than the propagation delay so that the state of the transmission can be determined. CSMA/CD detects a collision and avoids the unusable transmission of damaged frames. The following describes the procedures of CSMA/CD:

If the medium is idle, the frame is transmitted.

The medium is listened to during the transmission; if collision is detected, a special jamming signal is sent to inform all of stations of the collisions.

After a random amount of time (back-off), there is an attempt to transmit with 1-persistent CSMA.

The back-off algorithm uses the delay of 0 to 2 time units for the first 11 attempts and 0 to 1023 time units for 12 to 16 attempts. The transmitting station gives up when it reaches the 16th attempt. This is the last-in first-out unfair algorithm and requires imposing the minimum frame size for the purpose of collision detection. In principle, the minimum frame size is based on the signal propagation delay on the network and is different between baseband and broadband networks. The baseband network uses digital signaling, and there is only one channel used for the transmission, while the broadband network uses analog signaling, and it can have more than one channel. One channel is used for transmitting, and another channel can be used for receiving. The baseband network has two times the propagation delay between the farthest stations in the network, and the broadband network has four times the propagation delay from the station to the headend, with two stations close to each other and as far as possible from the “headend.” The delay is the minimum transmission time and can be converted into the minimum frame size.

The comparison of baseband and broadband in CSMA/CD schemes is as follows:

Different carrier sense (CS): Baseband detects the presence of transition between binary 1 and binary 0 on the channels, but broadband performs the actual carrier sense, just like the technique used in the telephone network.

Different collision detection (CD) techniques: Baseband compares the received signal with a collision detection (CD) threshold. If the received signal exceeds the threshold, it claims that the collision is detected. It may fail to detect a collision due to signal attenuation. Broadband performs a bit-by-bit comparison or lets the headend perform collision detection by checking whether higher signal strength is received at the headend. If the headend detects a collision, it sends a jamming signal to the outbound channel.

6.12 Idle Signal Casting Multiple Access

In the CSMA scheme, each terminal must be able to detect the transmissions of all other terminals. However, not all packets transmitted from different terminals can be sensed, or terminals may be hidden from each other by buildings or some other obstacles. This is known as the hidden terminal problem, which severely degrades the throughput of the CSMA. The idle signal casting multiple access (ISMA) system transmits an idle/busy signal from the base station to indicate the presence or absence of another terminal's transmission. The ISMA and CSMA are basically the same. In the CSMA, each terminal must listen to all other terminals, whereas in the ISMA, each terminal is informed from the base station of the other terminals' transmission. Similar to CSMAs, there are nonpersistent ISMAs and 1-persistent ISMAs.

Carrier Sense Multiple Access (CSMA)

In the CSMA technique, an attempt is made to avoid collisions by listening to the carrier due to transmission from another user before transmitting, and inhibiting transmission if the channel is sensed busy. This is advantageous when the propagation delay between any source-destination pair is small compared to the packet transmission time. Many CSMA protocols exist; they differ according to the action that a terminal takes to transmit a packet after sensing the channel. In all cases, however, when a terminal learns that its transmission has incurred a collision, it reschedules the transmission of the packet according to a randomly distributed delay. At this new point in time, the transmitter senses the channel again and repeats the algorithm dictated by the protocol. In nonpersistent CSMA, a ready terminal senses the channel and operates as follows. If the channel is sensed idle, the terminal transmits the packet. If the channel is sensed busy, then the terminal schedules the retransmission of the packet to some later time according to the retransmission delay distribution. At this new point in time, it senses the channel and repeats the algorithm described.

In the 1-persistent CSMA protocol, a ready terminal senses the channel and operates as follows. If the channel is sensed idle, it transmits the packet with probability one. If the channel is sensed busy, it waits until the channel goes idle and then immediately transmits the packet with probability one. In 1-persistent CSMA, whenever two or more terminals become ready during a packet transmission period, they wait for the channel to become idle (at the end of that transmission), and then they all transmit with probability one. A conflict will also occur with probability one. Randomizing the starting time of transmission of packets accumulating at the end of a transmission period reduces interference and improves performance. The p-persistent scheme involves including an additional parameter p, the probability that a ready packet persists (1 − p being the probability of delaying transmission by τ seconds, where τ is the maximum propagation delay among all pairs). Parameter p is chosen to reduce the level of interference while keeping the idle periods between any two consecutive nonoverlapped transmissions as small as possible.

The CSMA technique has been applied to ground radio (e.g., PRNET), and to local area communications (e.g., ETHERNET). In ETHERNET, CSMA is used on a tapped coaxial cable to which all the communicating devices are connected. On the coaxial cable, in addition to sensing carrier, it is possible for the transceivers to detect collisions. This is achieved by having each transmitting device compare the bit stream it is transmitting to the bit stream it sees on the channel. When transmitting users detect interference among several transmissions (including their own), they abort the transmission of colliding packets. This variation of CSMA is referred to as carrier sense multiple access with collision detection (CSMA-CD).

The performance of CSMA is heavily dependent on the ratio, a, of propagation delay to packet transmission time. The maximum throughput of a CSMA protocol degrades significantly as a gets larger. For a ratio a = 0.01, nonpersistent CSMA achieves a channel utilization equal to 0.815, a significant improvement over the ALOHA schemes.

While until recently most of the concepts described in this section had been realized in experimental systems (namely, the ALOHA System, PRNET, and Xerox's experimental ETHERNET), it is important to note that today many contention systems of the ETHERNET type are available on the market. Examples are the Hyperchannel and the Hyperbus of Network Systems Corporation, Z-Net of Zilog, Omninet of Corvus, and ETHERNET itself. The latter has been announced as a product made available jointly by Xerox Corporation, Digital Equipment Corporation, and INTEL. Complete specifications of the data link and physical link protocols have been issued and constituted the basis of a standard for the IEEE Computer Society Project 802 on the standardization of local networks. A key feature that distinguishes this product from other already available systems is the LSI implementation of many of the data link and physical link protocols. The LSI implementation of network protocols clearly marks a trend in the evolution of computer networking, a trend that is indicative of the existence of a wide market and the need to provide reasonably priced components.

26.5.1 Media access control (MAC)

The CSMA/CD function is implemented in the MAC layer. The functions of the MAC layers are:

When sending frames – receive frames from LLC; control whether the data fills the LLC data field, if not add redundant bits; make the number of bytes an integer, and calculate the FCS; add the preamble, SFD and address fields to the frame; send the frame to the PLS in a serial bit stream.

When receiving frames – receive one frame at a time from the PLS in a serial bit stream; check whether the destination address is the same as the local node; ensure the frame contains an integer number of bytes and the FCS is correct; remove the preamble, SFD, address fields, FCS and remove redundant bits from the LLC data field; send the data to the LLC.

Avoid collisions when transmitting frames and keep the right distance between frames by not sending when another node is sending; when the medium is free, wait a specified period before starting to transmit.

Handle any collision that appears by sending a jam signal; generate a random number and back off from sending during that random time.

21.5.4 IEEE 802.11 Medium Access Control

Wireless local area networks operate using a shared, high bit rate transmission medium to which all devices are attached and information frames relating to all calls are transmitted. MAC sublayer defines how a user obtains a channel when he or she needs one.

MAC schemes include random access, order access, deterministic access, and mixed access. The random access MAC protocols are: ALOHA (asynchronous, slotted), carrier-sense multiple-access (CSMA) (CSMA/collision-detection (CD), CSMA/collision-avoidance (CA), non-persistent, and p-persistent). The maximum throughput of slotted ALOHA protocol is about 36% of the data rate of the channel (see Chapter 5). It is simple, but not very efficient. Most WLANs implement a random access protocol, CSMA/CA with some modification, to deal with the hidden node problem. The CSMA peaks at about 60%. When the traffic becomes heavy, it degrades badly. The way of dealing with that situation is to use p-persistent. Most mobile data networks also use random access protocol, usually one that is simpler than CSMA, namely slotted ALOHA. Table 21.10 provides a comparison of MAC schemes for wireless networks.

Table 21.10. Comparison of MAC access schemes in wireless networks.

Deterministic MAC schemes improve throughput and response time when traffic is heavy. They offer the guaranteed bandwidth for isochronous traffic. In mixed cases such as CSMA/TDMA, the frame is divided into a random access part and a reserved part. When the traffic is light, it is left to be mostly random. When the traffic is heavy and throughput is in danger of declining or if a node requires isochronous bandwidth, the control point allocates bandwidth deterministically. CSMA/TDMA approaches CSMA performance under light traffic, so it has fast access time. It approaches TDMA performance when the traffic becomes heavy, so its throughput can rise close to 100% of the data rate.

IEEE 802.11 uses a modified protocol known as carrier sense multiple access with collision avoidance (CSMA/CA) or distributed coordination function (DCF). CSMA/CA attempts to avoid collisions by using explicit packet acknowledgment (ACK), which means an ACK packet is sent by the receiving station to confirm that the data packet arrived intact.

The CSMA/CA protocol is very effective when the medium is not heavily loaded since it allows stations to transmit with minimum delay. But there is always a chance of stations simultaneously sensing the medium as being free and transmitting at the same time, causing a collision. These collisions must be identified so that the MAC layer can retransmit the packet by itself and not by the upper layers, which would cause significant delay. In the Ethernet with CSMA/CD the collision is recognized by the transmitting station, which goes into a retransmission phase based on an exponential random backoff algorithm. While these collision detection mechanisms are a good idea on a wired LAN, they cannot be used on a WLAN environment for two main reasons:

Implementing a collision detection mechanism would require the implementation of a full duplex radio capable of transmitting and receiving at the same time, an approach that would increase the cost significantly.

In a wireless environment we cannot assume that all stations hear each other (which is the basic assumption of the collision detection scheme), and the fact that a station wants to transmit and senses the medium as free does not necessarily mean that the medium is free around the receiver area.

To overcome these problems, the 802.11 uses a CA mechanism together with a positive ACK. The MAC layer of a station wishing to transmit senses the medium. If the medium is free for a specified time, called distributed inter-frame space (DIFS), then the station is able to transmit the packet; if the medium is busy (or becomes busy during the DIFS interval) the station defers using the exponential backoff algorithm.

This scheme implies that, except in cases of very high network congestion, no packets will be lost because retransmission occurs each time a packet is not acknowledged. This entails that all packets sent will reach their destination in sequence.

The 802.11 MAC layer provides for two other robustness features: cycle redundancy check (CRC) checksum and packet fragmentation. Each packet has a CRC checksum calculated and attached to ensure that the data was not corrupted in transmit. This is different from the Ethernet, where higher-level protocols such as TCP handle error checking.

Packet fragmentation allows large packets to be segmented into smaller units when sent over the medium. This is useful in very congested environments or when interference is a factor, since large packets have a better chance of being corrupted. This technique reduces the need for retransmission in many cases and improves overall wireless network performance. The MAC layer is responsible for reassembling fragments received, rendering the process transparent to higher-level protocols. The following are some of the reasons it is preferable to use smaller packets in a WLAN environment:

Due to higher BER of a radio link, the probability of a packet getting corrupted increases with packet size.

In case of corrupted packets (either due to collision or interference), smaller packets cause less overhead.

On an FHSS system the medium is interrupted periodically for hopping. With smaller packets the chance that the transmission will be postponed after dwell time is reduced.

A simple send-and-wait algorithm is used at the MAC sublayer. In this mechanism the transmitting station is not allowed to transmit a new packet until one of the following happens:

Receives an ACK for the packet, or

Decides that packet was retransmitted too many times and drops the whole frame.

4.4.1 Review of media access control mechanisms

4.4.1.3 CSMA-CA Contention Collision (CC)

The unslotted CSMA-CA channel access mechanism in IEEE 802.15.4 usually works well when the node density is sparse and nodes are more uniformly distributed in the network. Once beyond a certain boundary, the overall network performance can be degraded dramatically as more nodes are contending for the same medium. This results in transmission failures, leading to large backoff periods, and finally connection terminations. Each node in LR-WPAN specifies three variables for each transmission attempt:

NB: the number of times that CSMA-CA is required to backoff; it is denoted by macMaxCSMABackoffs: 0–5 (default = 4).

BE: a backoff exponent that is used to calculate the backoff period (i.e., 0 ~ (2BE − 1)) a node shall wait before attempting to access a channel; it is denoted by macMaxBE: 3–8 (default = 5); macMinBE: 0 ~ macMaxBE (default = 3).

CW: the contention window length that represents the number of backoff periods in ensuring that a channel is free; it is denoted by CW: 0–2, (default = 2). This variable is only used in the beacon-enabled operational mode (to be discussed in Section 4.2). Two successful clear channel assessments (CCAs) in a row are required before transmission. Otherwise, CW is always reset to 2.

Notably, the CW parameter in LR-WPAN is used differently than that in IEEE 802.11 WLAN. The difference is that CW in IEEE 802.11 can be doubled when network congestion occurs, and may be frozen if a packet loss is detected.

13.6.2.4 CSMA/CD

In the previous CSMA systems once transmission commences it is completed even if a collision occurs on the first bit. This is clearly wasteful of bandwidth. In a modification, known as Carrier Sense Multiple Access with Collision Detection (CSMA/CD), a user monitors the line even when it commences transmission and stops once a collision is detected (Metcalfe and Boggs, 1976). After that the user waits a random time before sensing the line again. This multiple access method has been standardised by the IEEE as 802.3 (IEEE, 1985).

It is also not always possible for a sender to effectively sense the line during its transmission since the strength of the transmitted signal may be so strong as to swamp any signal returned back. Often CSMA/CD algorithms require that each user which detects a collision transmit a short jamming signal to immediately inform all other users that a collision has occurred on the line.

1.2.5.2 Token Passing (IEEE 802.4 and IEEE 802.5)

When compared with CSMA/CD, the token passing system is deterministic and has the advantages like higher throughput and priority setting. There are two different topologies used: token passing bus (IEEE802.4) and token passing ring (IEEE802.5). The basic scheme of operation in token passing systems is listed below:

Only one device/node can talk at a time.

Node/device waits for a free token to communicate over the channel.

Token circulates among the node until one wants to communicate.

If a station does not have any data to transmit it passes the token to the neighbor.

Token is held for a specified time.

When the node/device grabs the token it takes the following actions:

Sending device/node sets the token busy and adds information and a trailer packet.

The entire message is sent over the channel for communication.

Every node examines the header packet or frame to check if it belongs to it or to ignore in case it is not meant for it.

Intended node/device copies the message set bit in the trailer field to acknowledge and send back. The sender then checks the message received back to check if it’s properly received. Then it frees the token in case it is not required.

The most popular is Fieldbus, like Foundation Fieldbus, and Profibus, which utilize token passing media access.

Its advantages include:

High throughput at higher network load (number of nodes) when compared with CSMA/CD but saturates after a certain number of nodes in network.

Deterministic

Priority setting (up to six)

Its disadvantages include:

Complicated protocol and software

Higher bandwidth expensive cable and hardware

2 THE HIGH PRIORITY BINARY EXPONENTIAL BACKOFF ALGORITHM

The CSMA/CD (Carrier Sense Multiple Access with Collision Detection) protocol is the protocol implemented at the MAC layer of both ANSI/IEEE 802.3 and Ethernet local area networks. For a 10/100 Mbps Ethernet implementation, the following set of parameters is used:

Basically, the CSMA/CD protocol works as follows (Figure 1a): when a station wants to transmit, it listens to the transmission medium. If the transmission medium is busy, the station waits until it goes idle; otherwise, it transmits immediately. If two or more stations simultaneously begin to transmit, the transmitted frames will collide. Upon the collision detection, all the transmitting stations will terminate their own transmission and send a jamming sequence2. When the transmission is aborted due to a collision, it will be repeatedly retried after a randomly evaluated delay (backoff time), until it is either successfully transmitted, or definitely aborted (after a maximum number of 16 attempts).

The backoff delay is evaluated by locally executing the Binary Exponential Backoff (BEB) algorithm, which operates as follows: after the end of the jamming sequence, the time is divided into discrete slots, whose length is equal to the slot time. The backoff time is given by tbackoff = r × T, where r is a random integer in the range 0 ≤ r ≤ 2k – 1, k is the smaller of n or 10 (n is the number of retransmission attempts) and T is the slot time in seconds. This means that the station will wait between 0 and 2k–1 slot times. After 10 attempts, the waiting interval is fixed at 1023 slot times, and finally after 16 attempts the transmission is discarded.

On the other hand, a station implementing the h-BEB algorithm operates as follows (Figure 1b): whenever there is a collision, the station immediately starts to transmit (backoff interval equal to 0). This behavior guarantees the highest transmitting probability to the h-BEB Station, as it will always try to transmit its frame in the first slot, while all the other stations will wait between 0 and 2k-l slot times.

The h-BEB collision resolution algorithm can be used to support real-time traffic separation, as the traffic generated by the h-BEB Station will be always transferred prior to the traffic generated by the other stations. This behavior is highly adequate to, for instance, real-time video/voice transferring applications in legacy shared Ethernet networks. By simply plugging a notebook computer with the modified hardware to the network, it becomes possible to transfer traffic at a higher priority than the traffic generated by all the other stations.