Proposed empirical methodology

In the previous section, we showed that the simple models proposed in the literature do not accurately predict the interference in our testbed. We now present a simple empirical methodology to estimate $LIR$.

Recall that in Section 2, we listed several reasons why two links may impact each other's throughput. If we ignore the ACKs (given their relatively small size), we can then use the following simple methodology to estimate the impact of carrier sensing and collision of data packets as follows.

First, have one node, say $A$, broadcast packets as fast as it can. Only one node is active at a time. Denote the send rate by $S_{A}$. Keep track of the delivery rate of packets at all other nodes in the network. For example, the delivery rate at node $B$ will be denoted by $R_{AB}$. Have each node broadcast in turn. Then, select a pair of nodes, say $A$ and $C$, have them broadcast packets together. Denote their send rates by $S^{AC}_A$ and $S^{AC}_C$. At all remaining nodes measure the delivery rate of packets they receive from each of the two broadcasting nodes. For example, at node $B$, the delivery rate of packets from $A$ is denoted by $R_{AB}^{AC}$. Similarly, at node $D$, the delivery rate of packets from $C$ is denoted by $R_{CD}^{AC}$. Have each pair broadcast in turn. Thus, we have carried out a total of $O(n^2)$ experiments.

Consider links $L_{AB}$ and $L_{CD}$. Using the data gathered from the above methodology, we can define the ``broadcast interference ratio'' (BIR) as follows.

$$\small BIR = ({R_{AB}^{AC} + R_{CD}^{AC}}) / ({R_{AB} + R_{CD}})$$ (2)

Figure 3: Median LIR and BIR of 75 pairs.

Our hypothesis is that the $BIR$ is a good approximation of $LIR$. If the hypothesis is true, we can estimate interference for every pair of links using only $O(n^2)$ experiments, while testing each link pair will require far more (potentially $O(n^4)$) experiments. This is a substantial improvement: if we use 30 second transfers, and repeat each experiment 5 times, calculating $BIR$ for every pair of links requires just over 28 hours. The key idea is that we can estimate unicast interference using broadcast packets, if we ignore impact of ACKs.

There are several reasons to believe that our hypothesis is correct. It is easy to see that $BIR$ captures impact of carrier sensing on the two senders. It also captures the impact of data packet collisions at the receivers. The ACK packets are quite small (only 14 bytes) and the chance of them colliding with each other is also small. There are also some reasons to believe that the hypothesis is not correct. First, if a broadcast packet is lost (say due to collision), it is not retransmitted. On the other hand, a lost unicast packet is retransmitted multiple times, and the mean wait time (802.1 backoff) before sending the next retransmission is doubled. Thus, a lost unicast packet has a higher impact on throughput measured at the user level. Second, while ACK packets may not collide with one another, data and ACK packets can still collide. We now test our hypothesis experimentally.