CSMA/CD Protocol

In the previous chapter, having studied about the Sliding Window Protocols, we now focus our attention on the features, design and implementation details of the Carrier Sense Multiple Access/Collision Detection (CSMA/CD) protocol.

CSMA/CD and it precursors such as Pure ALOHA, Slotted ALOHA etc., have been termed as 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. Transmissions are ordered randomly. They have also been termed as contention techniques as the stations contend for time on the medium. As has been seen from the previous chapters, both pure & slotted ALOHA exhibit poor utilisation. With slotted ALOHA the best channel utilisation that can be achieved is 1/e (0.368). This was expected, since with stations transmitting at will, without paying attention to what the other stations are doing, there are bound to be many collisions. In local area networks, however it is possible for stations to detect what other stations are doing and to adapt their behavior accordingly. Thus, these networks can achieve a much better utilisation than 1/e.

CSMA protocols

The foregoing observations led to the development of Carrier Sense Multiple Access (CSMA) protocols in which the stations listen for a carrier (i.e., a transmission) and act accordingly. With CSMA, a station wishing to transmit first listens to the medium to determine if another transmission is in progress (carrier sense). If the transmission medium is in use, the station waits. If the medium is idle, the station may transmit. A number of CSMA protocols have been proposed as follows…

CSMA with Collision Detection

As is evident from the discussion above and in the previous chapters, both persistent and non-persistent CSMA protocols are an obvious improvement over ALOHA, because they ensure that no station begins to transmit when it senses the channel busy. Another major improvement which can be realised, is for the stations to abort their transmission as soon as they detect a collision. In other words, if two stations sense the channel to be idle and begin transmitting simultaneously, there is bound to be a collision and both will detect it almost immediately. Rather than continue transmission of the damaged frames, the stations should abruptly stop transmission as soon as a collision is detected, failing which the medium remains unusable for the duration of transmission of the damaged frames. This waste can be reduced if a station continues to listen to the medium while transmitting and can thereby save both time and bandwidth by quickly terminating damaged frames. Thus, this protocol has been rightly referred to as CSMA/CD (Carrier Sense Multiple Access with Collision Detection). The following rules can therefore be chalked out for working of CSMA/CD…

Fig. 4-1 CSMA/CD states - Contention, Transmission or Idle

Keeping in mind the above rules for CSMA/CD operation, it is quite evident that the model for CSMA/CD operation will consist of alternating contention and transmission periods, with idle periods occurring when all the stations are quiet, as shown in the figure above. In order to observe the details of the contention algorithm, let us suppose that two stations begin transmitting at exactly time ‘t0’. It has to be determined how long it will take for both the stations to realize that there has been a collision, because this is vital in determining the length of the contention period, and hence what the delay and throughput will be. The minimum time to detect the collision is then just the time it takes for the signal to propagate from one station to the other. On the basis of this reasoning, one might think that a station not hearing a collision for a time equal to the full cable propagation time after starting its transmission could be sure that it has seized (i.e., by ‘seize’ it is meant that all other stations knew it was transmitting and would not interfere) the cable. But this surmise can be proved wrong by considering the following worst-case scenario as shown in the figure below

Fig. 4-2 CSMA/CD Operation

Referring to the figure above, let the time for a signal to propagate between the two farthest stations be (in the above case A and C) be Tp . At ‘t0’ , one station begins transmitting. At (Tp – s), an instant before the signal arrives at the most distant station C, that station also begins transmitting. The station C detects the collision almost instantly and stops, but the little noise burst caused by the collision does not get back to the original station until time (2Tp – s). In other words, in the worst case a station cannot be sure that it has seized the channel until it has transmitted for 2Tp without hearing a collision. As can be seen from the figure, a jamming signal is sent on the channel as soon as the collision is detected. Hence, the contention interval is modeled as a Slotted ALOHA system with slot-width 2Tp.

It should be noted that the process of collision detection is an analog process. The station’s hardware must listen to the cable while it is transmitting. If what it reads back is different from what it is putting out, it knows a collision is occurring.

IEEE Standard 802.3 (Ethernet)

The IEEE 802.3 standard is for a 1- persistent CSMA/CD LAN. Thus, all stations connected to such a LAN and wanting to transmit, first listen to the cable. If the cable is busy, the station waits until it goes idle; otherwise it transmits immediately. If two or more stations simultaneously begin transmitting on an idle cable, they will collide. All colliding stations terminate their transmission, wait a random time, and repeat the whole process all over again.

The Binary Exponential Backoff Algorithm

When a collision occurs, randomization is done according to the ‘Binary Exponential Backoff Algorithm’. The algorithm is as follows :

After a collision, time is divided up into discrete slots whose length is equal to the worst case round-trip propagation time on the ether (2Tp). Following the first collision, each station waits either 0 or 1 slot times before trying again. If two stations collide and each one picks up the same random number, they will collide again. After the second collision, each one picks either 0, 1, 2 or 3 at random and waits that number of slot times. If a third collision occurs ( the probability of this happening is 0.25), then the next time the number of slots to wait is chosen at random from the interval 0 to 23 – 1. In general, after ‘i’ collisions, a random number between 0 to 2i – 1 is chosen, and the station waits for that number of slots before retransmitting. However, after ten collisions have been reached, the randomization interval is frozen at a maximum of 1023 slots. After 16 collisions, the controller breaks down and reports failure back to the computer. It should be noted that when a collision occurs, the colliding stations backoff and get prepared for retransmission, while other stations are informed of the collision with the help of the jamming signal. If some of the other stations decide to initiate a transmission while retransmission of the colliding stations has still not been completed, then such stations also behave as if they are directly involved in the collision and contend for channel use in accordance with the Binary Exponential Backoff Algorithm. So, the stations actually involved in the collision are not given any special priority for channel seizure and have to contend with the remaining stations on an equal-priority basis.

Thus, as can be seen in the above algorithm, the randomization interval grows exponentially as more and more consecutive collisions occur. So, the algorithm ensures a low delay when only a few stations collide, but also ensures that the collision is resolved in a reasonable interval when many stations collide. In the applet designed to depict the features & working of the CSMA/CD protocol, the above algorithm has been implemented to resolve collisions.

802.3 Cabling

Fig. 4-3 Types of Cabling

As is evident from the figure above, for the IEEE 802.3 LAN (Ethernet) or for that matter for any CSMA/CD LAN, typically five types of cabling are commonly used, which have been discussed below…

In 10Base5, a transceiver is clamped securely around the cable so that its tap is in direct contact with the cable’s inner core. The transceiver contains all the circuitry and the electronics to handle carrier and collision detection. When the collision is detected, it is the job of the transceiver to transmit the jamming signal via the cable to all other transceivers, informing them of the collision. A transceiver cable is present, which connects the transceiver to an interface board in the computer. The transceiver cable is usually 50 meters long and is composed of five individually shielded twisted pairs. Two of the pairs are for data in and data out, respectively. Two more are for control in and out. The fifth pair, which is normally not used, allows the computer to power the transceiver electronics. The interface board present inside the computer contains a controller chip that transmits frames to, and receives frames from, the transceiver. The controller is responsible for assembling the data into the specified frame format, as well ascomputing checksums on outgoing frames and verifying them on incoming frames. Transceivers with special enhancements are also available, which allow up to eight nearby computers to be attached to them, thereby assisting in reducing the number of transceivers needed.

Detecting cable breaks, bad taps, or loose connectors can be a major problem with 10Base5 and 10Base2 cabling. To overcome this problem, techniques have been developed to track them down. In a technique called Time Domain Reflectometry, a pulse of known shape is injected into the cable. If the pulse hits an obstacle or the end of the cable, an echo will be generated and sent back. By carefully timing the interval between sending the pulse and receiving the echo, it is possible to precisely point out/localize the origin of the echo. In this way, the breaks, bad taps etc. can be found out and rectified.

Cable Topologies

As can be seen from Fig. 4-4 below, there are different cable topologies or in other words there are different ways of wiring up a building. In part (a) of Fig. 4-4, a single cable is snaked from room to room, with each station tapping onto it at the nearest point. In part (b), a vertical spine runs from the basement to the roof, with horizontally running cables on each floor connected to it by special amplifiers (repeaters). In some buildings the horizontal cables are thin, and the backbone is thick. The most general topology is the tree, as shown in part (c) of the figure below, because a network with two paths between some pairs of stations would suffer from interference between two signals.

Fig. 4-4 Cable Topologies

Since each of the four cabling options have a maximum cable length per segment, to allow larger networks, multiple cables can be connected by repeaters as shown in part (d) of the figure above. A repeater, which is a physical layer device, receives, amplifies and retransmits signals in both directions. For the concerned software, a series of cable segments connected by repeaters is no different than a single cable (except for the delay introduced by the repeaters). It should be noted that, a system may contain multiple cable segments and multiple repeaters, but no two transceivers may be more than 2.5 km apart and no path between any two transceivers may traverse more than four repeaters.

This section having dealt with the features and working of the CSMA/CD protocol and the IEEE 802.3 standard (Ethernet), the following sections throw some light on the working and the class hierarchy of the Java applet, designed as a teaching tool, to study the behavior of the CSMA/CD protocol and its adaptability in a changing networking environment.

Applet Design

Since the simulator has been developed in Java, which is an Object-Oriented Language, the design entails the discussion of the classes (which represent the objects that an Ethernet implementing the CSMA/CD protocol would contain) and their methods. These components have been listed below.

Review of Design

From the foregoing discussion of the class structure it is evident that the applet design is efficient and represents quite accurately the needs of the application. The important objects in a network (nodes and data packets) have been identified and classes have been constructed for them.

The "Node" class defines a network node in terms of its main attributes and it also contains the methods that handle a node well with respect to the simulation. This encapsulation of a node into a single class with its properties and associated methods also allows for code reusability since the same class can be used for further simulations. The same goes for the "Packet" class which represents a data packet precisely. The sendPacket method of this class concentrates on the movement of the packet for CSMA/CD and is a complete module in itself. It can be easily overloaded to simulate some other protocol while using the same class to represent the packet.

That the "Canvas1" class contains most of the functionality of the applet is quite understandable since this is a simulation and the emphasis is on conveying to the user the working of a protocol through the dynamic visual medium. All the graphics associated with this applet are drawn on the canvas thus making it very convenient to program and understand if most of the work is carried out in methods of this class. The main class (CsmaCd) handles only the components that are directly associated with it like the buttons. This again is logical since the buttons are used only for a fraction of the time that the applet is running and the code for these is easily handled at this level, reducing the complexity of the canvas class in the process.

A separate class for the error messages again helps in code reusability. Any number of error messages can be displayed through the use of a single class. When an error is trapped, the error code generated is all that is required to access this class and display the message. This abstraction makes it easier to develop the rest of the application as well as other applications requiring this functionality. The "Help" class too helps in a similar manner.

In conclusion, the design appears robust and allows for code reusability and eases the work of modifying the code. The clear-cut identification of objects and the accurate encapsulation of members within the classes make it easy to understand the working of the applet. However, some improvements can be made. Since there are a number of threads in use, separate classes for the threads will make the design simpler.

All the functionality for the thread can be in this class which is derived from the Java "Thread" class. This will also reduce the complexity of the main classes like the "Canvas1" class.

In the next chapter we study the implementation of the Sliding Window and CSMA/CD protocols.

Home | Contents | Previous chapter | Return to top of document.