The Medium Access Control Sublayer
We already know that, networks can be divided into two categories: those using point-to-point
connections and those using broadcast channels. This chapter deals with broadcast networks and
their protocols.
In any broadcast network, the key issue is how to determine who gets to use the channel when
there is competition for it. To make this point clearer, consider a conference call in which six
people, on six different telephones, are all connected so that each one can hear and talk to all the
others. It is very likely that when one of them stops speaking, two or more will start talking at
once, leading to chaos. In a face-to-face meeting, chaos is avoided by external means, for
example, at a meeting, people raise their hands to request permission to speak. When only a
single channel is available, determining who should go next is much harder. Many protocols for
solving the problem are known and form the contents of this chapter. In the literature, broadcast
channels are sometimes referred to as multiaccess channels or random access channels.
The protocols used to determine who goes next on a multiaccess channel belong to a sublayer of
the data link layer called the MAC (Medium Access Control) sublayer. The MAC sublayer is
especially important in LANs, many of which use a multiaccess channel as the basis for
communication. WANs, in contrast, use point-to-point links, except for satellite networks.
Because multiaccess channels and LANs are so closely related, in this chapter we will discuss
LANs in general, including a few issues that are not strictly part of the MAC sublayer. The MAC
sublayer is the bottom part of the data link layer.
The traditional way of allocating a single channel, such as a telephone trunk, among multiple
competing users is Frequency Division Multiplexing (FDM). If there are N users, the bandwidth
is divided into N equal-sized portions, each user being assigned one portion. Since each user has
a private frequency band, there is no interference between users. When there is only a small and
constant number of users, each of which has a heavy (buffered) load of traffic (e.g., carriers'
switching offices), FDM is a simple and efficient allocation mechanism.
However, when the number of senders is large and continuously varying or the traffic is bursty,
FDM presents some problems. If the spectrum is cut up into N regions and fewer than N users
are currently interested in communicating, a large piece of valuable spectrum will be wasted. If
more than N users want to communicate, some of them will be denied permission for lack of
bandwidth, even if some of the users who have been assigned a frequency band hardly ever
transmit or receive anything.
However, even assuming that the number of users could somehow be held constant at N,
dividing the single available channel into static subchannels is inherently inefficient. The basic
problem is that when some users are quiescent, their bandwidth is simply lost. They are not using
it, and no one else is allowed to use it either. Furthermore, in most computer systems, data traffic
is extremely bursty (peak traffic to mean traffic ratios of 1000:1 are common). Consequently,
most of the channels will be idle most of the time.
, The poor performance of static FDM can easily be seen from a simple queueing theory
calculation. Let us start with the mean time delay, T, for a channel of capacity C bps, with an
arrival rate of frames/sec, each frame having a length drawn from an exponential probability
density function with mean 1/µ bits/frame. With these parameters the arrival rate is frames/sec
and the service rate is µC frames/sec. From queueing theory it can be shown that for Poisson
arrival and service times,
T= 1(µC-λ)
For example, if C is 100 Mbps, the mean frame length, 1/µ, is 10,000 bits, and the frame arrival
rate, , is 5000 frames/sec, then T = 200 µsec. Note that if we ignored the queueing delay and
just asked how long it takes to send a 10,000 bit frame on a 100-Mbps network, we would get the
(incorrect) answer of 100 µsec. That result only holds when there is no contention for the
channel.
Now let us divide the single channel into N independent subchannels, each with capacity C/N
bps. The mean input rate on each of the subchannels will now be /N. Recomputing T we get
Equation 4
TFDM= 1/ [µ(C/N)-(λ/N)]
The mean delay using FDM is N times worse than if all the frames were somehow magically
arranged orderly in a big central queue.
Precisely the same arguments that apply to FDM also apply to time division multiplexing
(TDM). Each user is statically allocated every Nth time slot. If a user does not use the allocated
slot, it just lies fallow. The same holds if we split up the networks physically. Using our previous
example again, if we were to replace the 100-Mbps network with 10 networks of 10 Mbps each
and statically allocate each user to one of them, the mean delay would jump from 200 µsec to 2
msec.
Since none of the traditional static channel allocation methods work well with bursty traffic, we
will now explore dynamic methods.
Dynamic Channel Allocation in LANs and MANs
Before we get into the first of the many channel allocation methods to be discussed in this
chapter, it is worthwhile carefully formulating the allocation problem. Underlying all the work
done in this area are five key assumptions, described below.
Station Model. The model consists of N independent stations (e.g., computers, telephones, or
personal communicators), each with a program or user that generates frames for transmission.
Stations are sometimes called terminals. The probability of a frame being generated in an
interval of length t is t, where is a constant (the arrival rate of new frames). Once a frame
We already know that, networks can be divided into two categories: those using point-to-point
connections and those using broadcast channels. This chapter deals with broadcast networks and
their protocols.
In any broadcast network, the key issue is how to determine who gets to use the channel when
there is competition for it. To make this point clearer, consider a conference call in which six
people, on six different telephones, are all connected so that each one can hear and talk to all the
others. It is very likely that when one of them stops speaking, two or more will start talking at
once, leading to chaos. In a face-to-face meeting, chaos is avoided by external means, for
example, at a meeting, people raise their hands to request permission to speak. When only a
single channel is available, determining who should go next is much harder. Many protocols for
solving the problem are known and form the contents of this chapter. In the literature, broadcast
channels are sometimes referred to as multiaccess channels or random access channels.
The protocols used to determine who goes next on a multiaccess channel belong to a sublayer of
the data link layer called the MAC (Medium Access Control) sublayer. The MAC sublayer is
especially important in LANs, many of which use a multiaccess channel as the basis for
communication. WANs, in contrast, use point-to-point links, except for satellite networks.
Because multiaccess channels and LANs are so closely related, in this chapter we will discuss
LANs in general, including a few issues that are not strictly part of the MAC sublayer. The MAC
sublayer is the bottom part of the data link layer.
The traditional way of allocating a single channel, such as a telephone trunk, among multiple
competing users is Frequency Division Multiplexing (FDM). If there are N users, the bandwidth
is divided into N equal-sized portions, each user being assigned one portion. Since each user has
a private frequency band, there is no interference between users. When there is only a small and
constant number of users, each of which has a heavy (buffered) load of traffic (e.g., carriers'
switching offices), FDM is a simple and efficient allocation mechanism.
However, when the number of senders is large and continuously varying or the traffic is bursty,
FDM presents some problems. If the spectrum is cut up into N regions and fewer than N users
are currently interested in communicating, a large piece of valuable spectrum will be wasted. If
more than N users want to communicate, some of them will be denied permission for lack of
bandwidth, even if some of the users who have been assigned a frequency band hardly ever
transmit or receive anything.
However, even assuming that the number of users could somehow be held constant at N,
dividing the single available channel into static subchannels is inherently inefficient. The basic
problem is that when some users are quiescent, their bandwidth is simply lost. They are not using
it, and no one else is allowed to use it either. Furthermore, in most computer systems, data traffic
is extremely bursty (peak traffic to mean traffic ratios of 1000:1 are common). Consequently,
most of the channels will be idle most of the time.
, The poor performance of static FDM can easily be seen from a simple queueing theory
calculation. Let us start with the mean time delay, T, for a channel of capacity C bps, with an
arrival rate of frames/sec, each frame having a length drawn from an exponential probability
density function with mean 1/µ bits/frame. With these parameters the arrival rate is frames/sec
and the service rate is µC frames/sec. From queueing theory it can be shown that for Poisson
arrival and service times,
T= 1(µC-λ)
For example, if C is 100 Mbps, the mean frame length, 1/µ, is 10,000 bits, and the frame arrival
rate, , is 5000 frames/sec, then T = 200 µsec. Note that if we ignored the queueing delay and
just asked how long it takes to send a 10,000 bit frame on a 100-Mbps network, we would get the
(incorrect) answer of 100 µsec. That result only holds when there is no contention for the
channel.
Now let us divide the single channel into N independent subchannels, each with capacity C/N
bps. The mean input rate on each of the subchannels will now be /N. Recomputing T we get
Equation 4
TFDM= 1/ [µ(C/N)-(λ/N)]
The mean delay using FDM is N times worse than if all the frames were somehow magically
arranged orderly in a big central queue.
Precisely the same arguments that apply to FDM also apply to time division multiplexing
(TDM). Each user is statically allocated every Nth time slot. If a user does not use the allocated
slot, it just lies fallow. The same holds if we split up the networks physically. Using our previous
example again, if we were to replace the 100-Mbps network with 10 networks of 10 Mbps each
and statically allocate each user to one of them, the mean delay would jump from 200 µsec to 2
msec.
Since none of the traditional static channel allocation methods work well with bursty traffic, we
will now explore dynamic methods.
Dynamic Channel Allocation in LANs and MANs
Before we get into the first of the many channel allocation methods to be discussed in this
chapter, it is worthwhile carefully formulating the allocation problem. Underlying all the work
done in this area are five key assumptions, described below.
Station Model. The model consists of N independent stations (e.g., computers, telephones, or
personal communicators), each with a program or user that generates frames for transmission.
Stations are sometimes called terminals. The probability of a frame being generated in an
interval of length t is t, where is a constant (the arrival rate of new frames). Once a frame
