Section 5.5. Contention-Access MAC

5.5. Contention -Access MAC

Contention-access MAC is stochastic, more suitable for bursty traffic, whereby the waste of shared-medium bandwidth cannot be tolerated. Unlike the round- robin and reservation schemes, no control is involved in the contention scheme. Rather, each user needing to transmit frames must contend to access the medium. This scheme is simple to implement and is an effective solution for light or moderate traffic.

When a user logs on to a LAN, a channel for the transmission of a frame can be demanded at any random instance, potentially resulting in frame collision. This serious issue can be resolved in a number of ways, as follows :

• Permanent assignment of one channel to each user . This method can clearly waste the system bandwidth.

• Checking users regularly . The system can poll each user on a regular basis to see whether it has anything to transmit. This method could result in a long delay for larger networks.

• Random access of a channel . The system can provide a mechanism whereby a user can access at any time. This method is efficient but faces the collision issue if two or more frames are transmitted at the same time.

Several random-access methods are provided for computer networks. Two commonly used ones are Aloha method (see Section 4.4.2) and Carrier Sense Multiple Access (CSMA). The CSMA scheme is explained in the next section.

5.5.1. Carrier Sense Multiple Access (CSMA)

Carrier Sense Multiple Access (CSMA) is a protocol that lets only one user at a time transmit, on a first come, first served basis. A user needing to transmit data first listens to the medium and senses for a carrier on the medium to determine whether other users are transmitting: the carrier-sense phase. If the medium is busy, the user has to wait until the medium is idle. The amount of time a user must wait depends on the particular type of the protocol. If no other users transmit data, the user proceeds to transmit its data onto the medium. However, when the medium is busy, a user can follow one of the following three approaches:

1. Nonpersistent CSMA . The user waits for a random amount of time after a collision before sensing the channel again. The random delay is used to reduce the collision. However, this scheme uses the transmission channel inefficiently: Even though the transmission is completed, the user rechecks the medium only after expiration of the random delay. The random wait time is normally 512 g bit times, where g is a number drawn randomly .

2. 1-persistent CSMA . This scheme overcomes the disadvantage of the nonpersistent CSMA by continuing to sense the channel while it is busy. As soon as the medium is idle, the user transmits immediately. In this scheme, a collision occurs if more than one user is waiting to transmit.

3. p-persistent CSMA . This scheme is a compromise between the nonpersistent and the 1-persistent methods. When the medium is idle, the user can transmit with a probability p . If the medium is busy, the user can transmit for a time equal to the maximum propagation delay. Deciding on an appropriate value of p is crucial for efficient operation of the scheme.

If two or more users simultaneously try to transmit, a collision of frames occurs, and all data is corrupted. In such a case, all corresponding users stop transmitting. Thus, after a collision, all the users involved will start contention, each after a randomly chosen amount of time. After finishing the transmission of data, a user waits for an acknowledgment from the destination user. If the acknowledgment does not arrive , the user retransmits the data.

The main disadvantage of CSMA when a collision occurs is that other users cannot use the medium until all corrupted frames finish transmission. This problem increases in the case of long frames. However, this issue can be resolved with the use of CSMA/CD, whereby a user listens to the channel while transmitting data. In case of a collision, the transmission is halted, and a jamming signal is transmitted to inform the other users that a collision has occurred. The user enters into back-off mode and transmits after the back-off duration if the medium is idle. In Figure 5.5, a frame that leaves user 4 destined for user 2, collides with another frame that leaves user 1 destined for user 3. Immediately after the collision, user 2 finds the medium idle and transmits its frame destined to user 1.

Figure 5.5. The movement and collision of frames in a contention-access MAC network

Consider n users to be connected onto a common cable so that when one user transmits a frame while others are silent, all other users sense that frame. When a user starts the transmission, no others start before the user has propagated a signal throughout the cable. This way, the user can finish its frame without collision. The CSMA/CD method can be set up to detect collisions ahead of time. It is quite possible for a user to listen to the cable while transmitting; obviously, if two or more users start to transmit simultaneously, they find a collision in process and cease transmission. That is why this process is called CSMA collision detection (CSMA/CD).

CSMA/CD requires the frame length to be long enough to permit collision detection before the completion of transmission. The maximum time to detect a collision is not greater than twice the end-to-end propagation delay. The process of CSMA/CD is viewed in terms of slots and minislots. Setting minislots is required for a signal to propagate from one end of the cable to the other. Minislots are used in a contention mode. If all users are synchronized in minislots and one user transmits during an empty slot, all the other users pick up the transmitted frame until the frame is transmitted completely. However, if more than one user transmits during that slot, each transmitting user senses the situation and ceases transmitting.

Analysis of Frame Delay

Consider once again the bus LAN shown in Figure 5.5. Let be the average distance between any two users. The maximum is the distance between user 1 and user 4, and the minimum is the distance between user 1 and user 2. Let c be the speed of propagation. The average propagation delay of a frame between any two users can be determined by

Equation 5.1

Now, let f be the average frame size in bits and r be the data rate on the channel over the medium. The frame transmission time, t _r , can be calculated by

Equation 5.2

Here, the utilization of the LAN bus can be obtained by

Equation 5.3

Analysis of Contention

If a total of n users are attached to the medium and n _a of them are active, the probability of a user restraining itself to resend its frame during a time slot is

Equation 5.4

In general, an empty time slot remains empty, is taken by a user, or undergoes a collision. Apparently, the probability that a user attempts to transmit frames in an empty time slot is

Equation 5.5

By combining the two Equations (5.4) and (5.5), we obtain

Equation 5.6

This probability value merges to when n _a approaches a very large number. A different situation is that a frame tries i times in i empty slots to transmit its frame and is unsuccessful owing to collision, but it successfully sends its frame on time i + 1. The probability that this situation happens is obviously modeled by a geometric random variable, explained in Appendix C, and is obtained by

Equation 5.7

Interestingly, the average number of contentions can be computed by knowing this behavioral model using the expected value explained in Appendix C:

Equation 5.8

Analysis of Throughput

Consider Figure 5.6, and assume that the frame arrivals on the network have a Poisson distribution (see Appendix C for the details of the Poisson model) with an average arrival rate » and a frame duration of T seconds. Based on this model, the probability that there are k frames in a given period [0, t ] is obtained from

Figure 5.6. A timing illustration of CSMA/CD

Equation 5.9

We start with frame 2 and let t _p be the total propagation delay between any pair of users. Thus, the probability that a frame is transmitted successfully, P _t , is the probability that no additional frame is transmitted during t _p and is expressed by Equation (5.9) when k = 0 as

Equation 5.10

The delay time caused by the last colliding frame is modeled by a random variable, Y . The probability that this last frame is transmitted at or before time y is the probability that no other frames are transmitted in the interval ( y , t _p ] and is obtained from

Equation 5.11

The preceding probability is clearly calculated only for 0 <y <t _p and is known as the cumulative distribution function (CDF) of the random variable y . If this distribution is known, the probability density function (PDF), or f _Y (y) , can be determined (see Appendix C); thus, the average of time y can be estimated by the expected value of y :

Equation 5.12

As seen in Figure 5.6, the average busy time of a channel, t _B , has three components : frame duration ( T ), propagation delay ( t _p ), and the relative delay of the last colliding frame ( E [ Y ]):

Equation 5.13

From the property of the Poisson random variable, we calculate the average idle time as

Equation 5.14

The overall throughput of a CSMA/CD channel is defined as the number of frames per time slot and is obtained from

Equation 5.15

Throughput R can be normalized to throughput per frame time, or R _n . Practically, R _n is easier to use for the estimation of the system throughput.

5.5.2. Ethernet LAN: IEEE 802.3 Standard

The IEEE 802.3 standards committee developed a widely used LAN standard called Ethernet , which covers both the MAC layer and the physical layer. The IEEE 802.3 standard uses CSMA for controlling media access and the 1-persistent algorithm explained earlier, although the lost time owing to collisions is very small. Also, IEEE 802.3 uses a back-off scheme known as binary exponential backoff . The use of random backoff minimizes subsequent collisions. This back-off scheme requires a random delay to be doubled after each retransmission. The user drops the frame after 16 retries. The combination of the 1-persistent scheme and binary exponential backoff results in an efficient scheme. A brief description of the frame fields follows and is shown in Figure 5.7.

• Preamble is 7 bytes and consists of a pattern of alternating 0s and 1s. This field is used to provide bit synchronization.

• Start of frame consists of a 10101011 pattern and indicates the start of the frame to the receiver.

• Destination address specifies the destination MAC address.

• Source address specifies the source MAC address.

• Length/Type specifies the frame size, in bytes. The maximum Ethernet frame size is 1,518 bytes.

• LLC data is data from the LLC layer.

• Pad is used to increase the frame length to the value required for collision detection to work.

• Frame check sequence is 32-bit CRC for error checking (see Section 4.5.2).

Figure 5.7. Details of Ethernet IEEE 802.3 LAN frame

The Ethernet versions have different data rates. Version 1000BaseSX, carrying 1 Gb/s, and 10GBase-T, carrying 10 Gb/s, hold the most promise for the future of high-speed LAN development.