Which of these statements are true for correctly implemented
versions of stabilized unslotted Aloha, stabilized slotted Aloha, and
Time Division Multiple Access (TDMA)? Assume that the slotted and
unslotted versions of Aloha use the same stabilization method and
parameters.
When the number of nodes is large, unslotted Aloha has a lower
maximum throughput than slotted Aloha.
True. By a factor of 2: 1/2e instead of 1/e.
When the number of nodes is large and nodes transmit data according
to a Poisson process, there exists some offered load for which
the throughput of unslotted Aloha is higher than the throughput of
slotted Aloha.
False.
TDMA has no packet collisions.
True. TDMA eliminates collisions by explicitly allotting time slots.
There exists some offered load pattern for which TDMA has lower
throughput than slotted Aloha.
True. For example, a skewed workload in which some nodes have much
more traffic to send than others.
Problem 2.
Binary exponential backoff is a mechanism used in some MAC protocols.
Which of the following statements is correct?
A. It ensures that two nodes that experience a collision in a
time slot will never collide with each other when they each
retry that packet.
B. It ensures that two or more nodes that experience a collision in a
time slot will experience a lower probability of colliding with each
ther when they each retry that packet.
C. It can be used with slotted Aloha but not with carrier sense
multiple access.
D. Over short time scales, it improves the fairness of the
throughput achieved by different nodes compared to not using the
mechanism.
B is true. The others are false.
Problem 3.
In the Aloha stabilization protocols we studied, when a node
experiences a collision, it decreases its transmission probability,
but sets a lower bound, p_min. When it transmits successfully, it
increases its transmission probability, but sets an upper bound, p_max.
Why would we set a lower bound on p_min that is not too close to 0?
To avoid starvation where some nodes are denied access to the medium for long periods of time.
Why would we set p_max to be significantly smaller than 1?
To avoid the capture effect, in which a successful node hogs the
medium for multiple time slots even when other nodes are backlogged.
Let N be the average number of backlogged nodes. What happens if we
set p_min >> 1/N?
The rate of collisions will be high and the utilization close to 0.
Problem 4.
Consider a shared medium with N nodes running the slotted Aloha MAC
protocol without any backoffs. A "wasted slot" is one in which no
node sends data. The fraction of time during which no node uses the
medium is the "waste" of the protocol.
If the sending probability is p, what is the waste? What are
the smallest and largest possible values of the waste?
(1-p)N. 0 and 1.
If the Aloha sending probability, p, for each node is picked so
as to maximize the utilization, what is the corresponding waste?
1/e --> same as the utlization!
Problem 5.
True or false?
Assume that the shared medium has N nodes and they are always
backlogged.
In a slotted Aloha MAC protocol using binary exponential backoff,
the probability of transmission will always eventually converge to some
value p, and all nodes will eventually transmit with probability p.
False - In a binary exponential backoff, the probability of
transmission constantly changes. If the a transmission succeeds, then
the probability goes up. If the transmission fails, the probability
goes down.
Using carrier sense multiple access (CSMA), suppose that a node
"hears" that the channel is busy at time slot t. To maximize utilization,
the node should not transmit in slot t and instead transmit the packet
in the next time slot with probability 1.
False - The node should not transmit at time t+1 with 100%
probability. Other nodes may have also "heard" that the channel is
busy and would want to send a packet at time t+1. So the node should
send with a probability less than 100% to reduce the possibility of a
collision.
There is some workload for which an unslotted Aloha with
perfect CSMA will not achieve 100% utilization.
True - Multiple nodes may think that the channel is idle and send a
packet at the same time, resulting in a collision. Thus, the
utilization can never reach 100%.
Problem 6.
Eight Cell Processor cores are connected together with a shared
bus. To simplify bus arbitration, Ben Bittdidle, young IBM
engineer, suggested time-domain multiplexing (TDM) as an arbitration
mechanism. Using TDM each of the processors is allocated a
equal-sized time slots on the common bus in a round-robin fashion.
He's been asked to evaluate the proposed scheme on two types of
applications: 1) core-to-core streaming, 2) random loads.
1) Core-to-core streaming setup: Assume each core has the same stream bandwidth requirement.
Help Ben out by evaluating the effectiveness (bus utilization) of
TDM under these two traffic scenarios.
1) All cores have same bandwidth requirements during streaming, so,
bus utilization is 100%
2) Each core is given 12.5% of bus bandwidth, but not all cores can
use it, and some need more than that. So bus utilization is: 12.5% +
12.5% + 10% + 5% + 1% + 3% + 1% + 12.5% = 57.5%
Problem 7.
Randomized exponential backoff is a mechanism used to stabilize
contention MAC protocols. Which of the following statements is
correct?
It ensures that two nodes that experience a collision in a
time-slot will never collide with each other when they each
retry that packet.
False. They might get unlucky and back-off the same amount.
It ensures that two or more nodes that experience a collision
n a time-slot will experience a lower probability of colliding with
ach other when they each retry that packet.
True. The probability of a repeat collision is a smaller in each
subsequent backoff.
It can be used with slotted Aloha but not with CSMA.
False. It can be used in any contention protocol.
Problem 8.
Three users X, Y and Z use a shared link to connect to the
Internet. Only one of X, Y or Z can use the link at a given time. The
link has a capacity of 1Mbps. There are two possible strategies for
accessing the shared link:
TDMA: equal slots of 0.1 seconds.
"Taking turns": adds a latency of 0.05 seconds before taking the
turn. The user can then use the link for as long as it has data to
send. A user requests the link only when it has data to send.
In each of the following two cases, which strategy would you pick and why?
X, Y and Z send a 40KBytes file every 1sec.
TDMA. Why: Each of the users generate a load of 40KB/s = 0.32Mbps,
which can be fully transmitted given the share of 0.33Mbps available
per user when partitioning the channel with TDMA. Taking turns on the
other hand does not offer enough capacity for all the files to be
transmitted: 3*0.32 + 3*0.05 = 1.11s > 1s, and would incur extra
overhead.
X sends 80KBytes files every 1sec, while Y and Z send 10KBytes
files every 1sec.
Taking Turns Why: First, by using TDMA, X does not have enough
capacity to transmit, 80KB/s = 0.640Mbps > 0.33Mbps. Second, with
TDMA, Y and Z waste 3 out of 4 slots. On the other hand, when taking
turns, there is enough capacity to transmit all the data:
0.64+0.05+0.08+0.05+0.08+0.05=0.95s.
Problem 9.
Alyssa P. Hacker is setting up an 8-node broadcast network in her
apartment building in which all nodes can hear each other. Nodes send
packets of the same size. If packet collisions occur, both packets are
corrupted and lost; no other packet losses occur. All nodes generate
equal load on average.
Alyssa observes a utilization of 0.5. Which of the following are
consistent with the observed utilization?
True/False: Four nodes are backlogged on average, and the network
is using Slotted Aloha with stabilization, and the fairness is close
to 1.
False. With four backlogged nodes and fairness close to 1, the
probability of of transmission is 1/4. That would put the utilization
at 4*(1/4)*(1–1/4)3 = 0.42 < 0.5.
True/False: Four nodes are backlogged on average, and the
network is using TDMA, and the fairness is close to 1.
True. TDMA gives each node an equal share of the network, but 4 nodes
have nothing to send, giving a utilization of 0.5.
Now suppose Alyssa's 8-node network runs the Carrier Sense Multiple
Access (CSMA) MAC protocol. The maximum data rate of the network is 10
Megabits/s. Including retries, each node sends traffic according to
some unknown random process at an average rate of 1 Megabit/s per
node. Alyssa measures the network's utilization and finds that it is
0.75. No packets get dropped in the network except due to collisions.
What fraction of packets sent by the nodes (including retries)
experience a collision?
The offered load presented to the network is 8 Megabits/s in
aggregate. The throughput of the protocol is 0.75*10 = 7.5
Megabits/s. The packet collision rate is therefore equal to
1–7.5/8 = 1/16 = 6.25%.
Problem 10.
Note: this problem is useful to review how to set up and solve problems
related to Aloha-like access protocols, but the calculations shown in the
answer are more complex than we would ask on a quiz.
Consider a network with four nodes, where each node has a dedicated
channel to each other node. The probability that any node transmits is
p. Each node can only send OR receive one packet at a time. What is
the utilization of the network? Assume each packet takes 1 time
slot. Assume each node has 3 queues -- one for each other node -- and
that each is backlogged.
Utilization is the expected number of packets that get through in each
slot divided by the maximum (2, i.e. when A always transmits to B and
C always transmits to D).
For each case, we compute the expected number of packets that get
through, then remove conditioning using the total probability theorem.
Expected packets through if 4 nodes transmit = 0
No one is free to receive a packet.
Expected packets through if 3 nodes transmit = 1*(3/27) = 1/9
Without loss of generality, assume that A,B and C transmit. There are
27 combinations of destinations that they can transmit to (each can
choose one of 3). Of these, only 3 result in the successful
transmission of one packet (e.g. A->D,B->C,C->B) or
(B->D,A<->C) or (C->D,A<->B)
Expected packets through if 2 nodes transmit = 2*(2/9) = 4/9
Similar to above, assume that A and B transmit. There are 9
combinations of destinations. Of these, only 2 result in the
successful transmission of 2 packets (A->D,B->C) or (A->C,B->D).
Expected packets through if 1 node transmits = 1
No matter who the node transmits to, it will get through.
Expected packets through if 0 nodes transmit = 0
No packets sent.
Suppose that there are three nodes seeking access to a shared
medium using slotted Aloha, where each packet takes one slot to
transmit. Assume that the nodes are always backlogged, and that each
has probability p_i of sending a packet in each slot, where i = 1, 2
and 3 indexes the node. Suppose that we assign more the sending
probabilities so that
What are the probabilities that maximize the utilization and
the corresponding utilization?
Differentiating U and sett the result equal to zero we obtain
dU/dp = 4 - 20p + 18p2 = 0
has two roots at p=0.2616 and 0.8495. However, only the root at 0.2616 is
feasible since the other leads to a value of p_1 that is greater than 1. Thus,
p_1 = 0.5232, p_2 = 0.2616 and p_3 = 0.2616.
The corresponding utilization is 0.4695.
Problem 12.
Suppose that two nodes are seeking access to a shared medium using
slotted Aloha with binary exponential backoff subject to maximum and
minimum limits of the probability pmax = 0.8 and pmin = 0.1. Suppose
that both nodes are backlogged, and at slot n, the probabilities the
two nodes transmit packets are p_1 = 0.5 and p_2 = 0.3.
What are the possible values of p_1 at slot n+1? What
are the probabilities assocated with each possible value?
p_1 increases to 0.8 if node 1 transmits a packet and node 2 does not
transmit a packet. Probability of this event:
(p_1)(1 - p_2) = 0.5*0.7 = 0.35
p_1 decreases to 0.25 if node 1 transmits a packeet and node 2 also
transmits a packet. Probability of this event:
(p_1)(p_2) = 0.15
Otherwise p_1 stays the same with probability 1 - 0.35 - 0.15 = 0.5.
What are the possible values of p_2 at slot n+1? What are
the probabilities associated with each possible value?
p_2 increases to 0.6 if node 2 transmits a packet and node 1 does not
transmit a packet. Probability of this event:
(p_2)(1 - p_1) = 0.3*0.5 = 0.15
p_2 decreases to 0.15 if node 2 transmits a packeet and node 1 also
transmits a packet. Probability of this event:
(p_1)(p_2) = 0.15
Otherwise p_2 stays the same with probability 1 - 0.15 - 0.15 = 0.7.
Problem 13.
Bluetooth is a wireless technology found on many mobile devices,
including laptops, mobile phones, GPS navigation devices, headsets,
and so on. It uses a MAC protocol called Time Division Duplex
(TDD). In TDD, the shared medium network has 1 master and N
slaves. You may assume that the network has already been configured
with one device as the master and the others as slaves. Each slave has
a unique identifier (ID) that serves as its address, an integer
between 1 and N . Assume that no devices ever turn off during the
operation of the protocol. Unless otherwise mentioned, assume that no
packets are lost.
The MAC protocol works as follows. Time is slotted and each packet is
one time slot long.
In every odd time slot (1, 3, 5, …, 2t–1,
…), the master sends a packet addressed to some slave for which
it has packets backlogged, in round-robin order (i.e., cycling through
the slaves in numeric order).
In every even time slot (2, 4, 6, …, 2t,
…), the slave that received a packet from the master in the
immediately preceding time slot gets to send a packet to the master,
if it has a packet to send. If it has no packet to send, then that
time slot is left unused, and the slot is wasted.
Alyssa P. Hacker finds a problem with the TDD protocol
described above, and implements the following rule in addition:
From time to time, in an odd time slot, the master sends a "dummy"
packet addressed to a slave even if it has no other data packets to
send to the slave (and even if it has packets for other slaves).
Why does Alyssa's rule improve the TDD protocol?
Because it will prevent a slave from being starved; without it, a
slave that has packets to send will never send data packets if the
master never has packets to send to it.
Henceforth, the term "TDD" will refer to the protocol described
above, augmented with Alyssa's rule. Moreover, whenever a "dummy"
packet is sent, that time slot will be considered a wasted slot.
Alyssa's goal is to emulate a round-robin TDMA scheme amongst
the N slaves. Propose a way to achieve this goal by specifying the ID
of the slave that the master should send a data or dummy packet to, in
time slot 2t–1 (note that 1 ≤ t ≤ ∞).
Send to the slave whose ID is (t mod N)+1. This is almost exactly the
same problem as in PSet #6, Task 1 (TDMA). The only difference is that
the nodes begin with ID 1 here, not 0.
Henceforth, assume that the TDD scheme implements round-robin TDMA
amongst the slaves. Suppose the master always has data packets to send
only to an arbitrary (but fixed) subset of the N slaves. In addition,
a (possibly different) subset of the slaves always has packets to send
to the master. Each subset is of size r, a fixed value. Answer the
questions below (you may find it helpful to think about different
subsets of slaves).
What is the maximum possible utilization of such a
configuration?
The protocol is TDMA, so the master sends useful data packets in r of
the 2N slots in an epoch, and receives useful packets in the r of the
2N slots. So the utilization is r/N. If one N seeks to maximize that
over r, it's clear that the maximum happens when r = N, giving us a
maximum of 1.
What is the minimum possible utilization (for a given value of
r) of such a configuration? Assume that r > N/2. Note that if the
master does not have a data packet to send to a slave in a round, it
sends a "dummy" packet to that slave instead. A dummy packet does not
count toward the utilization of the medium.
r/N. When minimizing over all r, the smallest value becomes 1/2 + 1/N when N is even
and 1/2 + 1/2N when N is odd.
Problem 14.
Recall the MAC protocol with contention windows. Here, each node
maintains a contention window, W, and sends a packet t idle time
slots after the current slot, where t is an integer picked uniformly
in [1, W]. Assume that each packet is 1 slot long.
Suppose there are two backlogged nodes in the network with
contention windows W1 and W2, respectively. Assume that both nodes
pick randomly from [1, W1] and [1, W2] at the current time and
that W1 ≥ W2. What is the probability that the two nodes will
collide the next time they each transmit?
The two nodes collide if they pick identical random numbers. The
probability that the node with the smaller contention window picks a
given number x in the interval [1, W2] is 1/W2. The probability that the other node
also picks the same x is 1/W1. So the probability that both nodes pick
the same given number x is 1/(W1*W2). Now, there are W2 ways in which we can
choose x in [1, W2]. So the desired probability is W2/(W1*W2) = 1/W1.
More generally, the desired probability is equal to min(W1,W2)/(W1*W2)
= 1/max(W1,W2).
Another approach to the answer, based on the fact that for
uniform distributions all choices are equally likely. There are W1*W2
ways of picking pairs of contention window sizes at the two
nodes. Of these pairs, W2 of them can be both the same (or, in
general, min(W1,W2) of them), i.e., of the form (x, x). So the
desired probability is W2/(W1*W2) = 1/W1.
Problem 15.
Eager B. Eaver gets a new computer with two radios. There are N other
devices on the shared medium network to which he connects, but each of
the other devices has only one radio. The MAC protocol is slotted
Aloha with a packet size equal to 1 time slot. Each device uses a
fixed transmission probability, and only one packet can be sent
successfully in any time slot. All devices are backlogged.
Eager persuades you that because he has paid for two radios, his
computer has a moral right to get twice the throughput of any other
device in the network. You begrudgingly agree. Eager develops two
protocols:
Protocol A: Each radio on Eager's computer runs its MAC protocol
independently. That is, each radio sends a packet with fixed
probability p. Each other device on the network sends a packet with
probability p as well.
Protocol B: Eager's computer runs a single MAC protocol across its
two radios, sending packets with probability 2p, and alternating
transmissions between the two radios. Each other device on the network
sends a packet with probability p.
With which protocol, A or B, will Eager achieve higher throughput?
Protocol B. Eager's throughput with Protocol A is
2p(1–p)N+1. With Protocol B, his throughput is
2p(1–p)N, which is bigger than the expression for the
throughput of Protocol A because 0<1–p<1. The reason is
that with Protocol A, his two radios "interact" with each other and
sometimes can both collide, which does not occur with Protocol B.
Which of the two protocols would you allow Eager to use on the
network so that his expected throughput is double any other device's?
Protocol A, not B! The reason is that each of Eager's radios operates
under the same rules as all the other ones, and he has two
radios. More specifically, the throughput of any other device on the
network in Protocol A is equal to p(1–p)N+1, which is
one-half of Eager's throughput in Protocol A. In Protocol B, however,
any other devices get a throughput equal to p(1–p)N–1(1‐2p), which
is smaller than one-half of Eager's throughput.
