Question
In this problem, you will derive the efficiency of a CSMA/CD-like multiple access protocol. In this protocol, time is slotted and all adapters are synchronized to the slots. Unlike slotted ALOHA, however, the length of a slot (in seconds) is much less than a frame time (the time to transmit a frame). Let S be the length of a slot. Suppose all frames are of constant length L = Krs, where R is the transmission rate of the channel and k is a large integer. Suppose there are N nodes, each with an infinite number of frames to send. We also assume that d prop < S, so that all nodes can detect a collision before the end of a slot time. The protocol is as follows:
• If, for a given slot, no node has possession of the channel, all nodes contend for the channel; in particular, each node transmits in the slot with probability p. If exactly one node transmits in the slot, that node takes possession of the channel for the subsequent k – 1 slots and transmits its entire frame.
• If some node has possession of the channel, all other nodes refrain from transmitting until the node that possesses the channel has finished trans- mitting its frame. Once this node has transmitted its frame, all nodes contend for the channel. Note that the channel alternates between two states: the productive state, which lasts exactly k slots, and the nonproductive state, which lasts for a random number of slots. Clearly, the channel efficiency is the ratio of k/(k + x), where x is the expected number of consecutive unproductive slots.
a. For fixed N and p, determine the efficiency of this protocol.
b. For fixed N, determine the p that maximizes the efficiency.
c. Using the p (which is a function of N) found in (b), determine the effi-
ciency as N approaches infinity.
d. Show that this efficiency approaches 1 as the frame length becomes
large.
Answer
a.
To determine the efficiency of the protocol for fixed N and p, we need to calculate the expected number of consecutive unproductive slots, denoted by x.
In each slot, the probability of no node transmitting (unproductive slot) is (1 - p).
Therefore, the probability of x consecutive unproductive slots is .
The channel alternates between the productive state (k slots) and the nonproductive state (x consecutive unproductive slots).
So, the expected number of consecutive unproductive slots, x, is given by:
To calculate the efficiency, we use the formula: Efficiency = k / (k + x)
b.
To find the p that maximizes the efficiency for fixed N, we can differentiate the efficiency equation with respect to p and set it to zero.
Differentiating Efficiency = k / (k + x) with respect to
Setting
Substituting dx/dp = x / k into the equation for
Now we solve for p that maximizes the efficiency by substituting dx/dp = x / k into the equation for x.
c.
Using the p found in part (b), as N approaches infinity, we assume that p also approaches a certain value, denoted as p∞. We substitute this value of p into the equation for x and calculate the corresponding efficiency.
d.
To show that the efficiency approaches 1 as the frame length becomes large, we need to analyze the efficiency equation in the limit as the frame length (L) approaches infinity.
This analysis involves taking the limit of the efficiency equation as L approaches infinity and demonstrating that it tends to 1.