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.

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…

1-Persistent CSMA : In the 1-persistent CSMA, when a station has data to transmit, it first listens to the channel to see if any other station is transmitting at that instant. If the channel is busy, the station waits until it becomes idle. When a station senses an idle channel, it transmits straightaway. If a collision occurs, the station waits a random amount of time and starts all over again. The stations involved in the collision wait for a random amount of time because if they transmit immediately after the collision, then a collision will occur once again and this process will go on in lockstep. The protocol is referred to as 1-persistent because the station transmits with a probability of ‘1’ whenever it finds the channel idle.

Nonpersistent CSMA : The Nonpersistent CSMA protocol is less greedy than the 1-persistent CSMA in the sense that if the channel is already in use, the station does not continually sense it for the purpose of seizing it immediately upon detecting the end of the previous transmission. Instead of sensing the channel immediately, it waits a random period of time and then repeats the algorithm. Thus, this algorithm leads to better channel utilisation and longer delays than 1-persistent CSMA.

p-Persistent CSMA : A compromise that attempts to reduce collisions, like the non-persistent CSMA, and reduce idle time, like 1-persistent, is the p-persistent CSMA which is basically a hybrid CSMA combining both better channel utilisation and shorter delays. It chiefly applies to slotted channels and works as follows. When a station is ready to send, it senses the channel as is the case with all CSMA protocols. If it is idle, it transmits with a probability ‘p’. With a probability q=1-p it defers transmission until the next slot. If that slot is also idle, it either transmits or defers again, with probabilities ‘p’ and ‘q’. This process is repeated until either the frame has been transmitted or another station has begun transmitting. In the latter case, it acts as if there had been a collision (i.e., it waits a random time and starts again). If the channel is initially sensed to be busy, the station waits until the next slot and applies the above algorithm.

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…

If the medium is idle, transmit; else, go to next step.

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

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

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

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 ‘t₀’. 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

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 T_p . At ‘t₀’ , one station begins transmitting. At (T_p – 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 (2T_p – s). In other words, in the worst case a station cannot be sure that it has seized the channel until it has transmitted for 2T_p 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 2T_p.

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.

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.

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 (2T_p). 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 2³ – 1. In general, after ‘i’ collisions, a random number between 0 to 2ⁱ – 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.

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…

• 10Base5 cabling : This type of cabling is popularly referred to as thick Ethernet. It was one of the earliest types of cables used for LAN’s. The 10Base5 cable resembles a yellow garden hose, with markings every 2.5 meters to show where the taps go. Connections to this cable are made using vampire taps, in which a pin is carefully forced halfway into the coaxial cable’s core. The notation 10Base5 suggests that the LAN operates at 10 Mbps, uses baseband signaling and can support segments of up to 500 meters.

• 10Base2 cabling : 10Base2 or thin Ethernet, which in contrast to the garden-hose-like thick Ethernet, bends easily. Connections to this cable are made using industry standard BNC connectors to form T-junctions, rather than using vampire taps. 10Base2 cables are easier to install, are relatively inexpensive and are much more reliable. The only drawback of using the 10Base2 cable is that it can run for only 200 meters and can handle only 30 stations per cable segment. The transceiver electronics are present on the controller board, since the connection to the cable, which is a BNC T-junction is passive. Also, each station always has its own transceiver.

• 10Base-T cabling : With 10Base-T, there is no single, main cable because each station has a cable running to a central hub (a box full of electronics). Adding or removing stations is simpler in this configuration and cable breaks can be detected easily. The disadvantage of 10Base-T is that the maximum cable run from the hub is only 100 meters, sometimes 150 meters (if high quality twisted pairs are used). Also, a large hub is very expensive. Still, 10Base-T is steadily gaining popularity due to the ease of maintenance that it offers.

• 10Base-F cabling : 10Base-F is yet another cabling option and it employs fiber optics. The advantage of 10Base-F is that the maximum cable run is 2000 meters, which is excellent by any standards and it can accommodate up to 1024 stations per cable segment. It also has excellent noise immunity and is the method of choice when running between buildings or widely separated hubs. The only disadvantage with 10Base-F cabling is that it is very expensive due to the cost of the connectors and terminators.

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.

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.

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.

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.

• CsmaCd : This is the main class which creates most of the objects required and also initialises the applet at run-time. It contains the following methods :

• init : This is the method which initialises the applet.

• run : This is a method which contains the code for any executing thread of the CsmaCd class. In this case the thread that this method represents runs in the background throughout the life cycle of the applet and constantly checks for collisions.

• stop : Required for stopping any executing thread. In this case it is called when the applet is exited so that the collision-checking thread is destroyed.

• actionPerformed : This is an event-handling method which is invoked whenever any of the buttons is clicked. Depending on the button clicked, it calls the appropriate method.

• addNode : This method is called from the actionPerformed method whenever the "Add Node" button is clicked. It switches the applet into the "adding" mode in which the user can add nodes to the network. Since this button appears as the "Done" button in "adding" mode, the method has another function – that of switching out of "adding mode" when the button is clicked a second time.

• removeNode : This method is called from the actionPerformed method whenever the "Remove Node" button is clicked. It switches the applet into the "removing" mode in which the user can remove nodes from the network. Since this button appears as the "Done" button in "removing" mode, the method has another function – that of switching out of "removing mode" when the button is clicked a second time.

• startOrStop : Invoked from the actionPerformed method when the "Start" button is clicked. It starts the simulation by initialising all the variables and launching threads for all the nodes that wish to transmit data. Once the simulation begins, the "Start" button displays the caption "Stop". When the button is now clicked, this method is invoked, but this time it stops the simulation by destroying all the threads and resetting the variables. It also refreshes the applet display by invoking the "paint" method of the "Canvas1" class.

• Canvas1 : This class is derived from the Java "Canvas" class. It is used to manage a major part of the display. Except for the buttons, all the components are drawn on the canvas using this class. It contains a number of methods which control most of the working of the applet. These are described below :

• Canvas1 : This is the constructor for this class. It creates an instance of the class, which is used for controlling the simulation. It also initialises the variables.

• paint : This method is the most important, since it is invoked whenever the display is to be refreshed. It draws the static elements on the canvas when executed.

• onLine : A mouse click or movement of the mouse anywhere on the canvas invokes this method. It checks whether the mouse was on the Ethernet cable. It returns a boolean value indicating the result.

• onNode : This method is invoked whenever the mouse is clicked or moved anywhere on the canvas. It checks if the mouse was on any of the nodes. It returns a value indicating the number of the node which was clicked. If none of the nodes was clicked, it returns some other value.

• mouseClicked : This is an event-handling method which is invoked whenever the mouse is clicked. It traps the location of the click, which is used by the applet. The onLine and onNode methods are invoked to detect on which component the click occurred. If the click was on the cable, depending on the mode (adding or removing), a node is added to or removed from the network. If the click was on a node, a window is displayed which prompts the user to input the node parameters like data rate and destination node. A click at any other location is ignored.

• mouseMoved : This is an event-handling method which is invoked whenever the mouse is moved. It traps the location of the click, which is used by the applet. The onLine and onNode methods are invoked to detect on which component the mouse currently is. If the mouse is on the cable (in adding or removing mode) or on a node (not in either adding or removing mode), the mouse pointer is changed to display a hand so that the user knows that he can click at that spot and carry out whatever operation he wants to. Whenever this method detects that neither of the stated conditions is satisfied, the mouse pointer is changed back to the default.

• run : As mentioned before, this method contains the code for any executing thread of a class, in this case the Canvas1 class. The construction of this method is complex since it handles two sets of threads, one of these sets consisting of an array of threads. The first thread set waits for the user to input the parameters in the options window. Once done, this method extracts the parameters and stores them for the simulation. The second thread set has a separate thread for each node in the network. The entire simulation is controlled from this method. An instance of this method is created for each node when the simulation is started.

• displayPacketStatus : This method displays the packet status (number of packets successfully transmitted against number of packets waiting to be transmitted) for each node in the network. It is invoked from the "run" method.
• displayBackoffStatus : This method displays the status of each node when it is backing off after a collision. It is invoked from the "run" method.

• Node : This class defines a node in the network. It contains all the attributes of a node like position, status and rate of packet generation. An instance of this class is created for each node added to the network. The following methods are available :

• Node : This is the constructor for this class. It creates an instance of the class for each node in the network. The node is created at the position specified during the instantiation of the class.

• run : Each node in the network generates data packets at a constant rate specified by the user. The packet generation is done in the background through a thread of the "Node" class. This method contains the code for this thread.

• drawNode : This method draws a node at the desired position on the network and displays the correct node status. It also displays on screen the path a packet from this node will take when transmitted. It is invoked when a node is added to the network, when the node status changes and when the display is to be refreshed (from the paint method of the "Canvas1" class).

• eraseNode : This method erases a node and its associated packet path from the display when called. It is invoked when a node is removed from the network.

• Packet : This class defines a packet of a node in the network. An instance of this class is created for each node in the network once the user has specified the node parameters. It describes the main attributes of a packet like its dimensions, the node which created it and its position at any given instant. Though a packet is defined, this class actually handles an entire stream of packets that arise from a given node. This is possible because all packets from a particular node will have the same attributes. The following methods are members of this class :

• Packet : This is the constructor for the class. It creates an instance of the class for each node in the network that has its parameters set. The packet is created by specifying its position (same as that of the node associated with it) and the node from which it will be generated.

• sendPacket : This is the method which handles the movement of the packets through the network. It charts the entire course of the packet, performing other functions as well like informing the nodes along the way that the line is busy and taking action when a collision occurs (detected by the thread running in the "CsmaCd" class). This action includes sending the jamming signal to the other nodes and collecting data about the collision which will be used during the backoff.

• Window : This class is derived from the Java "Frame" class. It defines a window which prompts the user to specify the node parameters when he clicks on a node. Only two parameters are asked for – the destination node and the rate of data transmission in Mbps. It consists of the following methods :

• Window : This is the constructor for the class. It sets up the window, when created, by adding all the components and giving it a title.

• processWindowEvent : This method is an event-handler that processes window events. In this case, it detects whether the "close window" button on the status bar has been clicked. If it has been clicked, the window is closed and the parameters are not modified.

• actionPerformed : This is an event-handler which is invoked when either of the buttons in the window are clicked. It closes the window in both cases, the only difference being that when "Ok" is clicked, the changes made to the parameters are saved.

• textValueChanged : This method is invoked when the text in either of the text boxes changes. It is used to keep track of the values entered by the user and also to check whether they are valid.

• Error : Derived from the Java "Frame" class, it defines a window which is displayed whenever an error occurs while a node is being added to the network. The errors are of two types – either the user has exceeded the upper limit on the number of nodes that can be added to the network or the node that he is trying to add overlaps an existing node. In either case the error message is displayed in the window, which is an instance of this class. The following methods are part of this class :

• Error : This is the constructor for the class. It creates an instance of the class with the appropriate error message depending on the error that has occurred.

• actionPerformed : Closes the error window when the user clicks on the "Ok" button.

• Help : Online help on using the applet is provided through this class. It is derived from the Java "Frame" class. Whenever the user clicks on the "Help" button, a window, which is an instance of this class, is displayed. It consists of the following methods :

• Help : This is the constructor for the class. The help text is added to the window in this method.

• processWindowEvent : This method is an event-handler that processes window events. In this case, it detects whether the "close window" button on the status bar has been clicked. If it has been clicked, the window is closed.

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.