CS402: Computer Communications and Networks

Point-to-point datalink layers must select one of the framing techniques described above and optionally add retransmission algorithms such as those explained for the transport layer to provide a reliable service. Datalink layers for Local Area Networks face two additional problems. A LAN is composed of several hosts that are attached to the same shared physical medium. From a physical layer perspective, a LAN can be organized in four different ways:

• a bus-shaped network where all hosts are attached to the same physical cable
• a ring-shaped where all hosts are attached to an upstream and a downstream node so that the entire network forms a ring
• a star-shaped network where all hosts are attached to the same device
• a wireless network where all hosts can send and receive frames using radio signals

These four basic physical organizations of Local Area Networks are shown graphically in the figure below. We will first focus on one physical organization at a time.

Figure 6.3: Bus, ring and star-shaped Local Area Network

The common problem among all of these network organizations is how to efficiently share access to the Local Area Network. If two devices send a frame at the same time, the two electrical, optical, or radio signals that correspond to these frames will appear at the same time on the transmission medium, and a receiver will not be able to decode either frame. Such simultaneous transmissions are called collisions. A collision may involve frames transmitted by two or more devices attached to the Local Area Network. Collisions are the main cause of errors in wired Local Area Networks.

All Local Area Network technologies rely on a Medium Access Control algorithm to regulate the transmissions to either minimize or avoid collisions. There are two broad families of Medium Access Control algorithms:

1. Deterministic or pessimistic MAC algorithms. These 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 a distributed protocol which elects one device allowed to transmit at each time. 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.
2. Stochastic or optimistic MAC algorithms. These algorithms assume that collisions are part of the normal operation of a Local Area Network. They aim to minimize the number of collisions, but they do not try to avoid all collisions. Stochastic algorithms are usually easier to implement than deterministic ones.

We first discuss a simple deterministic MAC algorithm, and then we describe several important optimistic algorithms before coming back to a distributed and deterministic MAC algorithm.

Source: Olivier Bonaventure, https://s3.amazonaws.com/saylordotorg-resources/wwwresources/site/wp-content/uploads/2012/02/Computer-Networking-Principles-Bonaventure-1-30-31-OTC1.pdf
This work is licensed under a Creative Commons Attribution 3.0 License.