Archives

January 2001 Issue

Slicing Through the MAC Sublayer
Understanding Dynamic Allocation Protocols
By

In the first installment of our series on the media access control (MAC) sublayer, Thomson Multimedia’s Louis Litwin described how the algorithms used at that level help control access to the transmission medium in a broadcast network. In part two, he explains how to increase traffic efficiency with dynamic allocation protocols.

The shared nature of the hybrid fiber/ coax (HFC) network necessitates that a mechanism be available to control who can send traffic on the network and when. Without such a mechanism, devices might transmit simultaneously, causing the traffic to collide and become garbled.

Last month, we noted that static allocation protocols may alleviate this problem. While they are easy to implement, they don’t make efficient use of system bandwidth for typical network situations where users are not transmitting constantly. Dynamic allocation protocols that assign bandwidth on an as-needed basis are much more efficient. True, they are more complex to implement than static allocation protocols, but for most systems, this complexity is a small price to pay for bandwidth efficiency.

Aloha protocol

Aloha is an interesting dynamic allocation protocol in which all users are free to transmit whenever they have data available. If a user does not have any frames to send, he sits idle to free up the channel bandwidth for use by others. When a user needs to transmit a frame, he does so. Because multiple users might transmit at the same time, the free-for-all nature of Aloha means that collisions will occur frequently. However, users that are transmitting may listen to the channel to determine if a collision occurred. When this happens, Aloha employs a technique known as random back-off. When a user detects that his transmitted frame collided with another frame, the user waits a random amount of time and then retransmits the frame. The back-off time must be random in order to prevent the same users from colliding time after time.

Two different types of Aloha exist: pure and slotted. Users in a pure Aloha system may transmit instantly at any time, as shown in Figure 1. Aloha systems have the best performance when all devices use a constant frame size. A pure Aloha system with a constant frame size has a maximum bandwidth utilization of about 18 percent. A system that has a maximum possible throughput of B bits per second (bps) may achieve a maximum throughput of 0.18B bps when using pure Aloha.

In a slotted Aloha system, time is divided into slots the size of a single frame. If a user wants to transmit, he must wait until the start of the next time slot. An example of a slotted Aloha system is shown in Figure 2. By limiting the frame transmission to discrete time instances, a slotted Aloha system may achieve twice the bandwidth utilization of pure Aloha system, or about 37 percent. The bandwidth utilization achievable by either Aloha system is a small fraction of the total system bandwidth. The reason for such low utilization is because users in Aloha are not very "polite." That is, they transmit whenever they want to without regard for the transmissions of others.

A polite protocol: carrier sense multiple access

Carrier sense multiple access (CSMA), a more polite family of protocols, uses the carrier-sense technique to increase bandwidth utilization. If users in a CSMA system want to transmit, they first listen to the transmission medium to see if another user is sending data. If someone else already is transmitting, they wait to transmit until a later time.

Some variations of CSMA react differently when they find an idle channel. In 1-persistent CSMA, a user with data to transmit will send it whenever he senses an idle channel. If the channel is in use, the user will continually sense it until the channel becomes free. The protocol gets its name because the user transmits with a probability of 1 whenever the channel is idle.

Another variation is called nonpersistent CSMA. When users detect a busy channel in this protocol, they do not monitor the channel continuously to find out when it becomes idle. Instead, users wait a random amount of time and then sense the channel. If the channel is idle at that point, they transmit, otherwise the process repeats.

Because users in nonpersistent CSMA do not constantly monitor a busy channel, this protocol may result in longer delays compared to 1-persistent CSMA. However, it is able to achieve a higher bandwidth utilization because it handles problems related to propagation delay better than 1-persistent CSMA. Suppose users in 1-persistent CSMA need to transmit. They sense an idle channel and begin transmission. Shortly thereafter, another user needs to transmit as well. If the first user’s signal has not yet propagated to the second user, he will sense an idle channel and begin transmission as well, resulting in a collision of the two users’ frames. Nonpersistent CSMA handles this situation better because it does not constantly monitor the channel when it is in use. Thus the probability that several users will begin transmitting immediately after the previous user’s transmission ends is much lower than it is for 1-persistent CSMA.

Another type of CSMA protocol used on slotted channels is p-persistent CSMA. In this protocol, a user with data to send will sense the channel. If the channel is idle, the user will transmit a frame with probability p. A user with data to send will not transmit during an idle slot with probability 1-p. If the user senses the channel is in use, he waits until the next slot and repeats the procedure.

Decreasing the value of p results in a longer transmission delay (because users wanting to transmit will skip over idle frames more often), but greater bandwidth utilization. A 1-persistent CSMA can achieve a maximum bandwidth utilization of about 55 percent, and nonpersistent CSMA can achieve a utilization of about 90 percent. A utilization of nearly 100 percent is possible with p-persistent CSMA when p is set to a small value such as 0.01; however, users will experience very long transmission delays.

A further improvement is CSMA with collision detection (CSMA/CD). In this protocol, users abort their transmission as soon as they detect a collision. Because a frame is lost, whether one bit or all of the bits are garbled, there is no point in continuing the transmission. In addition, aborting the transmission frees up the channel for other users.

Reservation protocols

The ultimate in politeness is reservation protocols. Collisions do not occur in these protocols because all users with data to transmit make a reservation prior to sending data.

An example is the basic bit-map protocol. The system starts out with N contention slots, one for each user in the system. During a user’s corresponding slot, he sends a 1 if he has data to send and a 0 if he does not have data to send. After all users have placed their reservations, those users with data to send transmit their frames in numerical order based on their address. An example of this protocol is shown in Figure 3. (Note: There are three blue contention slots in Figure 3, one for users 1, 2 and 3.)

A 1 during the contention slots for users 1 and 3 indicates they have data to send. After the contention slots, users begin transmitting data. User 2 has nothing to send, so he remains idle. User 3 knows that user 1 has data to send, so he waits until user 1 transmits before sending his own frame.

Reservation protocols are good for avoiding collisions. However, they can be inefficient when there are not many users that need to transmit. This inefficiency is a result of the overhead for the contention slots. The channel is busy for the duration of all N contention slots, even if only one user has data to send.

Wireless network protocols

The MAC sublayer in wireless networks faces an interesting problem. The transmission medium is shared, but because of the limited range of the transmitters, it is possible that not all stations can hear each other. In this case, the previously mentioned CSMA protocols will fail. An example of this problem is illustrated in Figure 4 (at right), where the radius of the circles represent the range of the transmitter. The three receivers—A, B and C—are located so user B can hear both A and C, but users A and C cannot hear each other.

As a result, problems may arise. Suppose user C is transmitting to user B. During that transmission, user A needs to transmit to user B as well. User A senses the channel, but because he cannot hear user C, he proceeds to transmit to user B and the frames from users A and C collide at user B’s receiver. This situation is commonly referred to as the hidden station problem.

Multiple access with collision avoidance

Multiple access with collision avoidance (MACA) is one protocol developed to solve the hidden station problem. It solves the problem by having the transmitting user briefly contact the receiving user to indicate his intention to send data. The receiving station then broadcasts approval of the transmission so that all other nearby users can hear it, and then the transmitting station sends the frame.

An example using the arrangement in Figure 4 helps illustrate how the protocol works. Suppose user C wants to transmit to user B. Instead of sending the data immediately, user C sends B a brief frame called a request to send (RTS) frame.

This frame indicates user C’s intention to send and also informs user B of the length of the frame to be transmitted. At this point, user A is unaware of user C’s intentions. However, user B then replies to user C with a clear to send (CTS) frame, which serves two purposes. First, it informs user C that he may proceed with the transmission. Second, it solves the hidden station problem by informing all users within range of user B that B is about to receive a transmission of a given length from some user in the system.

Although user A did not hear the RTS frame from user C, he does hear the CTS frame from user B, and knows that another user is about to send a frame. If user A has data to send, he will wait until user C completes the transmission before contacting user B with his own RTS frame. User A knows how long to wait because the CTS frame from user B indicated the length of the frame to be transmitted.

Examples of MAC protocols

IEEE 802.3 standard, which uses CSMA/CD, and IEEE 802.4, which uses the protocol token bus, are two standardized real-world MAC protocols. Both fall under the IEEE 802.x family of standards for local area networks (LANs).

IEEE 802.3: 1-persistent CSMA/CD

The IEEE 802.3 standard describes a 1-persistent CSMA/CD protocol for LANs. The different types of cable used with this standard are referred to as 10BaseX where "10" refers to a throughput of 10 Mbps and "Base" refers to baseband modulation. The X can be a number or a letter. If it is a number, it refers to the length of the maximum segment of coaxial cable in hundreds of meters. For example, 10Base-5 supports a maximum segment length of 500 meters. When X is a letter, it denotes a cable type other than coax. For example, 10BaseT is for a cable of twisted pair copper telephone wires.

In case of a collision, this version of CSMA/CD uses a binary exponential backoff (BEB) algorithm. After a collision, the transmitter will pick a random number W within a given randomization interval R, waiting for W time slots before attempting to transmit again. The randomization interval is set to 0�R�1 after the first collision. After each subsequent collision, the size of the interval doubles (after the second collision, the interval is 0�R�3). The interval continues to double until it reaches its maximum size of 0 �R�1023. If a collision still occurs at that point, the transmitter informs the higher protocol layers that communications failed.

IEEE 802.4: token bus

The IEEE 802.4 standard uses the interesting concept of a token to create a collision-free environment. Each user on the network has a unique address and the users are organized into a logical ring structure.

This ring structure is for addressing purposes only, and positions on the logical ring are not necessarily related to the users’ physical positions. A given user will be aware of the stations that are logically located before and after him on the ring. Initially, the highest numbered user transmits his frame.

After his transmission is complete, he passes control of the transmission medium to his logical neighbor by sending him a control frame. This frame commonly is called a token, and collisions are prevented by only allowing the user with the token to transmit. Because a system only has a single token, this structure guarantees that only one user will be transmitting at any given time.

MAC sublayer protocols perform an important function in your network. Understanding how static and dynamic allocation protocols work will allow you to build a network that reduces traffic collisions and makes efficient use of bandwidth.

Louis Litwin is with Thomson Multimedia Corporate Research’s technical staff. He may be reached at .

 Back to January 2001 Issue

Access Intelligence's CABLE GROUP
Communications Technology | CableFAX Daily | CableFAX's CableWORLD | CT's Pipeline
CableFAX Magazine | CableFAX databriefs | Broadband Leaders Retreat | CableFAX Leaders Retreat