This article throws light upon the top four issues caused by media access protocols. The issues are: 1. ALOHA 2. Slotted ALOHA 3. Carrier Sense Multiple Access 4. CSMA with Collision Detection.
Issue # 1. ALOHA:
ALOHA is the product of the thought process of Norman Abramson who, in the 1970s, along with his colleagues in the University of Hawaii, came up with this effective and yet elegant method of allocating channels between contending parties.
Although the original application for which it was thought of was for radio broadcasting, it was very soon taken up for use in satellite transmission. There are two streams in ALOHA—pure ALOHA and slotted ALOHA. We shall first discuss pure ALOHA.
The basic idea of ALOHA is simple—and that is the reason it is elegant—and that is, to let the user transmit whenever he/they have data transmit any data. Naturally, there will be collisions and hence destruction of frames, but how to handle such situations efficiently, is what makes ALOHA so successful.
ADVERTISEMENTS:
In case of ALOHA the feedback property of broadcasting that comes in handy is the fact that the sending channel can listen to the despatch and hence find out if there has been a collision.
In a LAN, this feedback will be immediate; in case of satellite transmission—because the satellite is invariably in a geostationary orbit—this feedback will take about 270 msec. If the frame was destroyed, the sender retransmits the frame after an arbitrary amount of time.
The frames are all kept of the same size, since this increases the throughput. An important point for consideration is the efficiency of an ALOHA channel, that is, what fraction of the transmitted frames escape collisions? In order to answer this, consider an infinite collection of interactive users each on his own computer station. Now a user will always be in either of two states—transmitting or waiting for a response.
The station transmits a frame and checks the channel if it was successful in sending it correctly. On seeing the successful reply, the user goes back to typing else the user continues to wait and the frame continues to be sent again and again until success is finally achieved. Let frame time indicate the time taken by a standard fixed-length frame to be transmitted (this will thus be the frame length divided by the bit rate).
ADVERTISEMENTS:
Now assume that this infinite population of users generates new frames according to a Poisson Distribution with a mean of 5 frames per frame time. If S > 1 then the users are generating frames faster than the rate at which the channel can handle frames and nearly every frame will suffer a collision.
In order to get a reasonable throughput, we must aim to make 0 < S < 1. In addition to new frames, the station must also retransmit frames that have been damaged. If the probability of transmission is k transmission attempts per frame time (retransmitted frames and new frames combined) is also Poisson, with a mean of G per frame time then G > S.
If the load is low then there will be few retransmissions since there will be few collisions, therefore, G = S. At high transmission rates G > S and there will be many more collisions. Under all conditions the throughput is S = GPO, where P0 is the probability that a frame will not suffer a collision. The probability that k frames are generated during a given frame time is
Therefore, the probability of zero frames is e-G. In the interval of two frame times, the mean number of frames generated is 2G. The probability that no other traffic is generated in this period is PO = e-2G and since S = POG,
Issue # 2. Slotted ALOHA:
This was an attempt to improve upon some the capacity that ALOHA could handle. In 1970, Roberts proposed in a paper that the time interval be divided into discrete intervals, each interval corresponding to one frame. This approach required that users agree to slot boundaries and to synchronize their functions. One way to achieve synchronization is to have a special station emit a pip at the start of each interval.
The method proposed by Roberts, in contrast to the method in pure ALOHA, a station is not allowed to send whenever a carriage return is typed and must wait for the start of the next slot. Thus, this becomes a discrete ALOHA, in contrast to the continuous pure ALOHA. Since the vulnerable period is now reduced, the probability of no other traffic during the same slot is e-G. This results in
Slotted ALOHA will peak at G = 1, with S — 1/e, where S is the throughput. This throughput is equal to about 0.368. This is twice that of pure ALOHA. If the system is operating at G = 1, the probability of an empty slot is 0.368.
ADVERTISEMENTS:
We can normally expect, in case we are using slotted ALOHA, that at best 37% of the slots are empty, 37% succeed and the balance 26% end up in collisions. If the system operates at higher values of G, the number of empty slots decreases, but the number of collisions increases exponentially.
To achieve this deduction consider the transmission of a test frame. The probability that it will avoid a collision is e-G, that is, the probability that all other users in this slot are silent. Then the probability of a collision is 1 — e-G. The probability of transmission requiring exactly k attempts is
The expected number of transmissions per carriage return is then
It must be obvious from the above equation that the expectation is directly and heavily dependent on G and a slight increase in the channel load will drastically reduce its performance.
Issue # 3. Carrier Sense Multiple Access:
Carrier Sense Multiple Access or simply CSMA, as it is usually referred to, has been developed to improve channel utilization. The best channel utilization that can be achieved with slotted ALOHA is 1/e. While this does appear to be somewhat low, it is not surprising considering the fact that all stations continue to transmit at will, without looking at what other stations are doing.
This is bound to cause many collisions. In Local Area Networks it is possible to detect what other stations are doing and accordingly to adapt ones requirements. In that case, the utilization can be improved drastically.
Accordingly, certain protocols have been developed to improve the utilization to better than 1/e that can be achieved by slotted ALOHA. Protocols in which various channels listen for a carrier and act depending upon what they see are called carrier sense protocols. There are several such protocols and we shall discuss some of them here.
i. 1-Persistent CSMA:
When a station has data to send, it first listens to the channel to see whether anyone else is transmitting on that channel at that moment. If the channel is busy, the station waits until the channel becomes idle and then transmits a frame.
In case a collision occurs, the station waits for an arbitrary time period and then tries to repeat the procedure again. This protocol is called 1-persistent because the transmission has a probability of success of 1, whenever it finds the channel idle.
Propagation delays affect the performance of this protocol. There is a small likelihood that just as a station begins sending data frames, another station will become ready to send and sense the channel. If the first stations channel has not yet reached the second one, the second channel will sense an idle state and will begin transmitting a frame, thereby resulting in a collision.
The longer is the propagation delay, the more acute this problem becomes and the poorer the performance of this protocol. In fact, even if the propagation delay is nil, there will still be collisions.
For example, consider while a station is transmitting two other stations become ready to transmit and will wait for the transmission by that station to stop. As soon as this transmission stops, both these stations will start to transmit simultaneously and a collision will definitely occur. In spite of this, it has a higher throughput than pure ALOHA and more or less the same as slotted ALOHA.
ii. Non-persistent CSMA Protocol:
This is a second example of a carrier sense protocol that we shall discuss is Non-persistent CSMA protocol. This protocol is less greedy than the 1 -persistent protocol discussed above. In this, the station desirable to send a frame first senses whether any other station is broadcasting on the channel. If no other station is using the channel, it itself begins to transmit.
If the channel is being used, the station desirous of sending a message does not continue to monitor the channel and immediately start sending, on the previous transmission being ended.
Instead it waits for a random amount of time and then repeats the sensing procedure and continues. This invariably leads to better channel utilisation (certainly better than 1-persistent protocol). Unfortunately, it also gets higher delays as a byproduct.
iii. p-Persistent CSMA:
This is the last CSMA without collision protocol that we shall discuss. This possible only in slotted channels. In this, when a station is ready to transmit, it senses the channel. If it is idle, it transmits with the probability of p (and hence it defers transmission with the probability of 1 – p).
It keeps on doing this, slot after slot until the frame to be dispatched or another station has begun transmitting. In case the channel is not idle, it waits for a random amount of time and repeats the whole process again.
A graphical comparison of the channel utilisation of all the protocols discussed above is shown in Fig. 9.1:
Issue # 4. CSMA with Collision Detection:
The protocols just discussed, namely, the persistent and non-persistent CSMA protocols are a definite improvement on the ALOHA and slotted ALOHA protocols because they do not permit any station to transmit when the channel is busy and also the sending stations abort their transmission when they see that a collision has occurred.
If in case two stations find that the channel is idle then both may try to send a frame, in which case a collision is bound to occur.
As soon as each station finds out that a collision has occurred each station stops its transmission immediately, thereby saving on time and bandwidth. This protocol, widely used today is known as Carrier Sense Multiple Access with Collision Detection (CSMA/CD). This protocol is widely used in LANs.
In this protocol, when a station has finished sending its frame(s), another station may try to send its frame(s). If more than one station tries to transmit a frame, a collision will occur. Collisions can be detected by looking at the pulse width of the received signal and comparing it with that of the transmitted signal.
As soon as the transmitting station detects a collision, it immediately suspends its transmission and after waiting for a random period of time, it tries to transmit again, assuming that no other station has started transmitting in the meantime.
Therefore, this protocol consists of alternating periods of transmission and contention with periods of idleness thrown in between, which will occur when there is no work. Suppose two stations begin transmitting at exactly the same time. There will be a collision; the question now is—how long will the period of contention last? The answer to this question will determine the delay and the throughput.
The minimum time for detecting this collision will be the time it takes the signal to travel from one station to another. It would appear from this that a station that does not hear the collision for the time equal to the full cable propagation time after starting its transmission could begin to believe that it has complete control of the channel.
This is not so. Consider the case where the time for a signal to propagate between the two farthest stations is r. One station begins to transmit and at T— Ԑ, that is an instant before the signal arrives at the farthest station, that station also begins transmitting. Of course, the collision is detected immediately, but the noise caused by the collision does not get back to the original station till 2T — Ԑ.
This implies that a station can be absolutely certain that the channel is idle until it has transmitted for 2T without hearing a collision. Therefore, contention interval slot could be made 2T. On a 1-km long coaxial cable, T = 5 µsec. Once, a station has control of the channel, it is free to transmit at the rate that suits it. Collision detection is an analog process and the station must listen to the cable while it is transmitting.
If what it reads back is different from what it has transmitted, it knows that a collision has occurred. The hardware must be sufficiently well designed to be able to notice a collision between two very low powered signals and it is for this reason that special encoding is normally used. CSMA/CD is an important protocol and Ethernet—which is identified as an international standard IEEE 802.3—is one version of it.