Consider the scenario shown below, in which there are four wireless nodes, A, B,
ID: 3761823 • Letter: C
Question
Consider the scenario shown below, in which there are four wireless nodes, A, B, C, and D. The radio coverage of the four nodes is shown via the shaded ovals; all nodes share the same frequency. When A transmits, it can only be heard/received by B; when B transmits, both A and C can hear/receive from B; when C transmits both B and D (but not A) can hear/receive from C; when D transmits, only C can hear/receive from D. Now suppose that node A has an infinite supply of messages that it wants to send to D; there are no other messages in the network. A message from A must first be sent to B, which then sends the message to C, which then sends the message to D. Time is slotted, with a message transmission time taking exactly one time slot, for example, as in slotted Aloha. During a slot, a node can do one of the following:
send a message (if it has a message to be forward toward D);
receive a message (if exactly one is being sent to it);
iii. remain silent.
As always, if a node hears two or more simultaneous transmissions, a collision occurs and none of the transmitted messages are received successfully. You can assume that there are no bit level errors, and thus, if exactly one message is sent, it will be received correctly by those within the transmission radius of the sender.
Now suppose that an omniscient controller (that is, a controller that knows the state of every node in the network) can command each node to do whatever it (the omniscient controller) wishes, that is, to send a message, to receive a message, or to remain silent.
a) Given this omniscient controller, what is the maximum rate at which messages can be transferred from A to D?
b) Now suppose that for every data message going from A to D, D will send an ACK message that must be forwarded back to A. What is the maximum rate at which data messages can be transferred from A to D?
Explanation / Answer
a. 1 message/ 2 slots
b. 2 messages/slot
c. 1 message/slot
a) Given this omniscient controller, what is the maximum rate at which messages can be transferred from A to D?
i) 1 message/slot
ii) 2 messages/slot
iii) 2 messages/slot
b) Now suppose that for every data message going from A to D, D will send an ACK message that must be forwarded back to A. What is the maximum rate at which data messages can be transferred from A to D?
i) 1 message/4 slots
ii) slot 1: Message A B, message D C
slot 2: Ack B A
slot 3: Ack C D
= 2 messages/ 3 slots
iii)
slot 1: Message C D
slot 2: Ack DC, message A B
Repeat
slot 3: Ack B A
= 2 messages/3 slots