Medium Access Control: Static Allocation

Static allocation Algorithms

Deterministic or pessimistic MAC algorithms assume that collisions are a very severe problem and that they must be completely avoided. These algorithms ensure that at any time, at most one device is allowed to send a frame on the LAN. This is usually achieved by using either a distributed protocol which elects one device that is allowed to transmit at each time, or a central protocol such that there is a central entity that assigns transmit time to hosts. A deterministic MAC algorithm ensures that no collision will happen, but there is some overhead in regulating the transmission of all the devices attached to the LAN.

A first solution is to define, a priori, the distribution of the transmission resources among the different devices that want to share the resources. These methods are referred to as Channel Partitioning Protocols. If $N$ devices need to share the transmission capacities of a LAN operating at $b$ Mbps, each device could be allocated a bandwidth of $\frac{b}{N}$ Mbps (although, note that the practically achievable throughput is less than this limit).

Frequency Division Multiplexing

Frequency Division Multiplexing (FDM) is a static allocation scheme in which a frequency is allocated to each device attached to the shared medium. As each device uses a different transmission frequency, collisions cannot occur.

FDM applied to optical fiber is typically referred to as Wavelength Division Multiplexing (WDM). In optical networks, WDM can be used which uses the same principles as FDM but is applied to light. An optical fiber can transport light at different wavelengths without interference. With WDM, a different wavelength is allocated to each of the devices that share the same optical fiber.

TDM

Time Division Multiplexing (TDM) is a static bandwidth allocation method that was initially defined for the telephone network. In the fixed telephone network, a voice conversation is usually transmitted as a $64$ kbps signal. Thus, a telephone conservation generates $8$ kbps, or $1$ byte every $125$ microseconds. Telephone conversations often need to be multiplexed together on a single line. For example, in Europe, thirty 64 Kbps voice signals are multiplexed over a single 2 Mbps line. This is done by using Time Division Multiplexing (TDM).

TDM divides the transmission opportunities into slots. In the telephone network, a slot corresponds to 125 microseconds. A position inside each slot is reserved for each voice signal. The figure below illustrates TDM on a link that is used to carry four voice conversations. The vertical lines represent the slot boundaries and the letters the different voice conversations. One byte from each voice conversation is sent during each 125 microsecond slot. The byte corresponding to a given conversation is always sent at the same position in each slot.

Dynamic TDM

TDM, as shown above, can be completely static, i.e., the same conversations always share the link. However, if the time slot allocation is static and some users are not currently transmitting, the resources are being wasted.

Dynamic TDM can be used in that scenario, which simply allows for the time slot allocations to be dynamically adjusted to make more efficient use of the transmission resources. In order to do so, the two parties part of a session must exchange messages specifying which conversation uses which byte inside each slot. Thanks to these signaling messages, it is possible to dynamically add and remove voice conversations from a given link.

Disadvantages

TDM and FDM are widely used in telephone networks to support fixed bandwidth conversations. Using them in Local Area Networks that support computers would probably be inefficient though, because computers usually don’t send information at a fixed rate. Instead, they often have an on-off behavior. During the on-period, the computer tries to send at the highest possible rate, e.g., to transfer a file. During the off-period, which is often much longer than the on-period, the computer does not transmit any packet. Using a static allocation scheme for computers attached to a LAN would lead to huge inefficiencies, as they would only be able to transmit at $\frac{1}{N}$ of the total bandwidth during their on-period. This is despite the fact that the other computers are in their off-period and therefore don’t need to transmit any information.

Quick Quiz!

The dynamic MAC algorithms discussed in the remainder of this chapter aim to solve this problem. In the next lesson, we’ll look at some optimistic allocation protocols!