Carrier Sense Multiple Access with Collision Detection (CSMA/CD)

---

The most commonly used medium access control technique for bus, tree and star topologies is CSMA/CD. The original base band version of this technique was developed and patented by Xerox as part of its Ethernet LAN. The original broadband version was developed and patented by MITRE as part of its MITREnet LAN. All of this work formed the basis for the IEEE 802.3 standard for CSMA/CD.

Before examining this technique, we look at some earlier schemes from which CSMA/CD evolved.

Precursors

CSMA/CD and its precursors can be termed random access, or contention techniques. They are random access in the sense that there is no predictable or scheduled time for any station to transmit; station transmissions are ordered randomly. They are contention in the sense that stations contend for time on the medium.

The earliest of these techniques, known as ALOHA, was developed for packet radio networks. However, it is applicable to any shared transmission medium. ALOHA, or pure ALOHA, as it is sometimes called, is a true free-for-all. Whenever a station has a frame to send, it does so. The station then listens for an amount of time equal to the maximum possible round-trip propagation delay on the network (twice the time it takes to send a frame between the two most widely separated stations) plus a small fixed time increment. If the station hears an acknowledgment during that time, fine; otherwise, it resends the frame. If the station fails to receive an acknowledgment after repeated transmissions, it gives up.

A receiving station determines the correctness of an incoming frame by examining a frame-check-sequence field, as in HDLC. If the frame is valid and if the destination address in the frame header matches the receiver's address, the station immediately sends an acknowledgment. The frame may be invalid due to noise on the channel or because another station transmitted a frame at about the same time. In the latter case, the two frames may interfere with each other at the receiver so that neither gets through; this is known as a collision. If a receiving station determines that a frame is invalid, it simply ignores the frame.

ALOHA is a very simple technique and hence pays a penalty for it. Because the number of collisions rises rapidly with increased load, the maximum utilization of the channel is only about 18%.

To improve efficiency, a modification of ALOHA, known as slotted ALOHA, was developed. In this scheme, time on the channel is organized into uniform slots whose size equals the frame transmission time. Some central clock or other technique is needed to synchronize all stations. Transmission is permitted to begin only at a slot boundary. Thus, frames that do overlap will do so totally. This increases the maximum utilization of the system to about 37%.

Both ALOHA and slotted ALOHA exhibit poor utilization. Both fail to take advantage of one of the key properties of both packet radio and LANs, which is that propagation delay between stations is usually very small compared to frame transmission time.

Consider the following observations. If the station-to-station propagation time is large compared to the frame transmission time, then, after a station launches a frame, it will be a long time before other stations know about it. During that time, one of the other stations may transmit a frame; the two frames may interfere with each other and neither gets through. Indeed, if the distances are great enough, many stations may begin transmitting, one after the other, and none of their frames get through unscathed. Suppose, however, that the propagation time is small compared to the frame transmission time. In that case, when a station launches a frame, all the other stations know it almost immediately. So, if they had any sense, they would not try transmitting until the first station was done. Collisions would be rare since they would occur only when two stations began to transmit almost simultaneously.

The foregoing observations led to the development of carrier sense multiple access (CSMA). With CSMA, a station wishing to transmit first listens to the medium to determine if another transmission is in progress (carrier sense). If the medium is in use, the station must wait. If the medium is idle, the station may transmit. It may happen that two or more stations attempt to transmit at about the same time. If this happens, there will be a collision; the data from both transmissions will be garbled and not received successfully. To account for this, a station waits a reasonable amount of time after transmitting, for an acknowledgment, taking into account the maximum round-trip propagation delay and the fact that the acknowledging station must also contend for the channel in order to respond. If there is no acknowledgment, the station assumes that a collision has occurred and re-transmits.

One can see how this strategy would be effective for networks in which the average frame transmission time is much longer than the propagation time. Collisions can occur only when more than one user begins transmitting within a short time (the period of the propagation delay). If a station begins to transmit a frame and there are no collisions during the time it takes for the leading edge of the packet to propagate to the farthest station, then there will be no collision for this frame since all other stations are now aware of the transmission.

The maximum utilization achievable using CSMA can far exceed that of ALOHA or slotted ALOHA. The maximum utilization depends on the length of the frame and on the propagation time; the longer the frames or the shorter the propagation time, the higher the utilization.

With CSMA, an algorithm is needed to specify what a station should do if the medium is found busy. Three approaches are followed.

1. Non-persistent CSMA – Here, a station wishing to transmit listens to the medium and obeys the following rules:

   A. If the medium is idle, transmit; otherwise, go to step B.

   B. If the medium is busy, wait an amount of time drawn from a probability distribution (the retransmission delay) and repeat step A.

   The use of random delays reduces the probability of collisions. To see this, consider that two stations become ready to transmit at about the same time while another transmission is in progress; if both stations delay the same amount of time before trying again, they will both attempt to transmit at about the same time. A problem with this approach is that capacity is wasted because the medium will generally remain idle following the end of a transmission even if there are one or more stations waiting to transmit.

   
   

2. 1-persistent CSMA - To avoid idle channel time, the 1-persistent protocol can be used. A station wishing to transmit listens to the medium and obeys the following rules:

   A. If the medium is idle, transmit; otherwise, go to step B.

   B. If the medium is busy, continue to listen until the channel is sensed idle; then transmit immediately.

   Whereas non-persistent stations are deferential, 1-persistent stations are selfish. If two or more stations are waiting to transmit, a collision is guaranteed. Things get sorted out only after the collision.

   
   

3. p-persistent CSMA - A compromise that attempts to reduce collisions, like non-persistent, and reduce idle time, like 1-persistent, is p-persistent. The rules are -

   A. If the medium is idle, transmit with probability p

   B. If the medium is busy, continue to listen until the channel is idle and repeat step A.

CSMA/CD

CSMA, although more efficient than ALOHA or slotted ALOHA, still has one glaring inefficiency. When two frames collide, the medium remains unusable for the duration of transmission of both damaged frames. For long frames, compared to propagation time, the amount of wasted capacity can be considerable. This waste can be reduced if a station continues to listen to the medium while transmitting. This leads to the following rules for CSMA/CD:

1. If the medium is idle, transmit; otherwise, go to step 2.

2. If the medium is busy, continue to listen until the channel is idle, then transmit immediately.

3. If a collision is detected during transmission, transmit a brief jamming signal to assure that all stations know that, there has been a collision and then cease transmission.

4. After transmitting the jamming signal, wait a random amount of time, then attempt to transmit again (repeat from step 1).

The figure below illustrates the technique for a base band bus. At time t₀, station A begins transmitting a packet addressed to D. At t₁, both B and C are ready to transmit. B senses a transmission and so defers. C, however, is still unaware of A's transmission and begins its own transmission. When A's transmission reaches C, at t₂, C detects the collision and ceases transmission. The effect of the collision propagates back to A, where it is detected some time later, t₃, at which time A ceases transmission.

With CSMA/CD, the amount of wasted capacity is reduced to the time it takes to detect a collision.

The amount of time that it takes to detect a collision is no greater than twice the end-to-end propagation delay for a base band bus.

For a broadband bus, the delay is longer. The figure below shows a broadband dual-cable system. This time, the worst case occurs for two stations as close together as possible and as far as possible from the head end. In this case, the maximum time to detect a collision is four times the propagation delay from an end of the cable to the head end.

An important rule followed in most CSMA/CD systems, including the IEEE standard, is that frames should be long enough to allow collision detection prior to the end of transmission. If shorter frames are used, then collision detection does not occur, and CSMA/CD exhibits the same performance as the less efficient CSMA protocol.

As with CSMA, CSMA/CD employs one of the three persistence algorithms. The most common choice is 1-persistent. It is used by both Ethernet and MITREnet, and is in the IEEE 802 standard.

Although the implementation of CSMA/CD is substantially the same for base band and broadband, there are differences. One is the means for performing carrier sense. For base band systems, this is done by detecting a voltage pulse train. For broadband, the RF carrier is detected.

Collision detection also differs for the two systems. For base band, a collision should produce substantially higher voltage swings than those produced by a single transmitter. Accordingly, the IEEE standard dictates that the transmitter will detect a collision if the signal on the cable at the transmitter tap point exceeds the maximum that could be produced by the transmitter alone. Because a transmitted signal attenuates as it propagates, there is a potential problem: If two stations far apart are transmitting, each station will receive a greatly attenuated signal from the other. The signal strength could be so small that when it is added to the transmitted signal at the transmitter tap point, the combined signal does not exceed the CD threshold. For this reason, among others, the IEEE standard restricts the maximum length of coaxial cable to 500m for 10BASE5 and 200m for 10BASE2.

A much simpler collision detection scheme is possible with the twisted-pair star-topology approach. In this case, collision detection is based on logic rather than sensing voltage magnitudes. For any hub, if there is activity (signal) on more than one input, a collision is assumed. A special sign called the collision presence signal is generated. This signal is generated and sent out as long as activity is sensed on any of the input lines. This signal is interpreted by every node as an occurrence of collision.

Implementations of the CSMA/CD scheme

1. Ethernet
2. Cheapernet
3. 10 BASE-T LAN
4. 10 BASE-F LAN

The Ethernet (10 BASE-5)

Ethernet is a solution to the need for a mass market local network standard. It was originally developed at the Xerox Research Centre in 1972 and later updated in a cooperative effort involving DEC, Intel and Xerox in 1980. It is presently a defacto standard for LAN.

The Ethernet implements the lower two layers and satisfies the IEEE 802.3 standard. In general terms, Ethernet is a multi-access, packet-switched communication system for carrying digital data among locally distributed computing systems. The medium for Ethernet is a low-noise, shielded, 50 ohms co-axial cable. The maximum loss from one end to the other is 8.5 dB at 10 MHz. Data transfer rate is 10 million bits per second (10 Mbps). Each segment of cable can be up to 500 m in length and can be connected into longer network lengths using repeaters to strengthen the signal. At each end of the cable segment a terminator is attached. This passive device provides the proper electrical termination to eliminate reflections.

The transceiver transmits and receives signals on the coaxial cable. Further, it also isolates the node from the channel so that a failure within the node will not affect the rest of the network. the transceiver is also responsible for detecting collisions.

The Ethernet transceiver is connected to the network coaxial cable using a single tap (known as a vampire tap). Towards the station side, the transceiver is connected via the transceiver cable which can be up to 50 m in length.

The interface to which the transceiver cable is connected is known as AUI or 10 BASE-5 interface (Also known as Thick Ethernet). Here 10 refers to 10 Mbps data rate and 5 refers to 500 m (the maximum length of a cable segment).

The maximum number of nodes per segment is 100 and minimum node spacing is 2.5 m.

To get 500 m in length per segment, the Ethernet cable must be highly immune to noise and this is responsible for the high cost of the cable.

To overcome this drawback, cheapernet was developed.

The Cheapernet (10 BASE-2)

Cheapernet è Cheaper implementation of the Ethernet.

The IEEE 802.3 type 10 BASE-2 (i.e. Cheapernet) has the same functional electrical specification as type 10 BASE-5, with only two exceptions in physical characteristics. These two physical differences attribute to the cost reduction, thus making it a cheapernet.

These 2 differences are:-

1. The cable used in cheapernet is a lower cost 50 ohm coaxial cable than the one used for Ethernet (cost ratio 1:5). The less expensive RG-58 CATV cable is commonly used as the medium.

2. The transceiver is integrated into the Data transmitting equipment. So the coaxial cable physically comes to the Data transmitting equipment (normally a computer), and connects to the transceiver within the DTE, and goes to the next DTE.

The kind of connector used at the DTE is a low cost BNC-T connector.

Thus more flexible thin coaxial cable and easy to use and cheap BNC-T connectors have made the cheapernet an easy to install Ethernet compatible network.

Because of the lower quality cables and connectors used in the cheapernet, there are some drawbacks. The maximum distance for one cheapernet cable segment is 185 m. The maximum number of nodes allowed for one cheapernet cable segment is 30 and maximum spacing between two nodes is 0.5 m. The BNC interface is known as 10 BASE-2. Here 2 refers to maximum length of the segment, which is rounded off to 200 m.

Since, Ethernet and Cheapernet share the same functional and electrical characteristics, both may be mixed in a network. Ethernet, for example may serve as a backbone for Cheapernet, in a hybrid Ethernet/ Cheapernet network.

The 10 BASE-T

Also known as type 1-BASE-5 star LAN. This network was proposed by HP in 1987 and it became a part of the IEEE 802.3 standard in 1990.

At the center of the star network, there is a network concentrator or hub. Each node is connected to the hub by CAT-3 UTP (unshielded twisted pair) cable, having a maximum length of 100 m. The hub is usually located in a wiring closet. All the basic features and access policy of bus topology have been retained in 10 BASE-T.

Moreover, it gives a higher level of fault tolerance, because link faults at individual nodes are isolated by the hub and the entire network is not affected.

The 10 BASE-F

A fourth cabling option for 802.3.

It uses fiber optics. Connector and terminators are expensive, but it has excellent noise immunity. It is chosen when running between buildings or widely separated hubs.

---