Problem .
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.
Problem .
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.
Problem .
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.
Problem .
Consider a shared medium with N backlogged nodes running the slotted Aloha MAC protocol without any backoffs. An idle slot is one in which no node sends data. We will refer to the fraction of time during which no node uses the medium as the "idletime" of the protocol.
Problem .
True or false?
Assume that the shared medium has N nodes and they are always backlogged.
Problem .
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.
2) Random loads setup: core 1 load = 20%, core 2 load = 30%, core 3 load = 10%, core 4 = 5%, core 5 = 1%, core 6 = 3%, core 7 = 1%, core 8 load = 30%
Help Ben out by evaluating the effectiveness (bus utilization) of TDM under these two traffic scenarios.
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 .
Randomized exponential backoff is a mechanism used to stabilize contention MAC protocols. Which of the following statements is correct?
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 1 Megabit/s. There are two possible strategies for accessing the shared link:
In each of the following two cases, which strategy would you pick and why?
0.64+0.05+0.08+0.05+0.08+0.05=0.95s.
Problem .
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?
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.
1–7.5/8 = 1/16 = 6.25%.
Problem .
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.
P[4 nodes transmit] = p^{4}
P[3 nodes transmit] = 4p^{3}(1-p)
P[2 nodes transmit] = 6p^{2}(1-p)^{2}
P[1 node transmits] = 4p(1-p)^{3}
p[0 nodes transmit] = (1-p)^{4}
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.
Thus, the expected number of packets through is
(1/9)*4p^{3}(1-p) + (4/9)*6p^{2}(1-p)^{2} + (1)*4p(1-p)^{3} = 4/9*p^{3}(1-p) + (4/3)p^{2}(1-p)^{2} + 4p(1-p)^{3}
The utilization is half of that.
Problem .
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
p_1 = 2(p_2) and p_2 = p_3
If p = p3
U = 2p(1-p)^{2} + 2(1 - 2p)p(1 - p) = 4p - 10p^{2} + 6p^{3}
dU/dp = 4 - 20p + 18p^{2} = 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 .
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.
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.
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 . 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.
Why does Alyssa's rule improve the TDD protocol?
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.
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).