I2MIX: Integration of Intra-?ow and Inter-?ow Wireless Network Coding Chuan Qin, Yi Xian, Chase Gray, Naveen Santhapuri, Srihari Nelakuditi University of South Carolina, Columbia {qinc, xian, graycm, santhapu, srihari}@cse.sc.edu Abstract—Wireless network coding has been shown to reduce the number of transmissions by exploiting the broadcast nature of the wireless medium. Multiple packets may be encoded into a single packet when their respective next hops have enough information to decode them. Previous research has shown that packets belonging to different ?ows may be encoded (inter?ow coding) when they are passing through a common router. Similarly, it has also been shown that coding packets of the same ?ow (intra-?ow coding) may provide better reliability by not relying on the reception of any single packet. In this work, we ?rst present IMIX, an intra-?ow wireless network coding scheme which has the potential to save transmissions and therefore improve network throughput. We then propose I2 MIX, the ?rst design to the best of our knowledge, that can bene?t from integrating inter and intra ?ow wireless network coding. Finally, we show through trace based evaluations that I2 MIX can reduce the total number of transmissions by 21-30%. information. By doing this, they remove the possibility of useless duplicated transmissions and remove the need for intercandidate coordination. However, it seems dif?cult to deploy COPE and MORE simultaneously because COPE assumes a network using bestpath routing and MORE uses opportunistic routing. In this paper, we address the integration of inter-?ow and intra-?ow coding in order to bene?t from both of them. The main contributions of this paper are as follows: • I. INTRODUCTION In wireless networks, transmissions are broadcast, and all neighbors of a transmitting node will receive the packet. This fundamental difference between wired and wireless networks has spawned many schemes unique to wireless communication. At the network layer, opportunistic routing schemes such as ExOR [1] enable all potential next-hops to aid in forwarding. However, there may be signi?cant overhead due to duplicated packets and the negotiation between forwarding nodes. Wireless network coding is another method of exploiting broadcast transmissions. In contrast, [2] uses the broadcast nature at MAC layer, by including packet id in a special RTS and next-hops can tell the sender whether they already heard the packets through CTS. In wireless network coding, routers encode (mix) the content of multiple packets and broadcast the resulting coded packets on the wireless medium. One speci?c coding scheme, termed COPE [3], encodes multiple packets destined to different next hops and broadcasts them together. This is possible as long as the sender knows all of the participating next hops have enough knowledge to decode their packet(s). This can occur when a sender has multiple ?ows intersecting at it, thus it is termed inter-?ow coding [4]. To ?nd coding opportunities, every node in COPE needs to timely inform its neighbors of which packets it has overheard. This control information required in COPE introduces additional overhead that reduces the maximum gain achievable. Conversely, it is also possible to perform intra-?ow coding [4]. One such intra-?ow scheme, termed MORE [5], uses random linear combinations while transmitting to give each transmitted packet unique • • • We describe IMIX, an intra-?ow coding scheme that uses linear coding with best path forwarding. In 802.11 a down stream node may overhear packets meant for upstream nodes (we use the term ”long jumps” for this). IMIX makes use of this overhearing to reduce number of transmissions. Since IMIX uses linear coding, packets obtained by overhearing will not be duplicated by actual transmissions. By using linear coding, IMIX can achieve the same performance as a perfect acknowledgment scheme [4], with much lower complexity. We introduce OSPR (Opportunistic Single-Path Routing), which selects routes with least ETX value, taking overhearing opportunities into consideration. OSPR aids in improving the performance of IMIX. OSPR is light weight and can be easily embedded into both proactive and reactive routing protocols. We propose I2 MIX, which is the ?rst scheme, to the best of our knowledge, that can bene?t from both inter?ow and intra-?ow coding. I2 MIX is an extended version of IMIX that also includes inter-?ow coding. I2 MIX has additional improvements resulting from moving the decoding process from endpoints in IMIX to each hop. By doing this we trade additional computing resources for more network performance improvement, which is considered more valuable. We show by trace based evaluation the performance improvements that can be obtained by IMIX and I2 MIX. The rest of this paper is organized as follows, Section II presents and discusses the design of IMIX. In section III, an IMIX aware routing scheme is introduced. Section IV presents the design of I2 MIX. In section V, we evaluate the performance of IMIX and I2 MIX. Section VI discusses related work, and section VII concludes and discusses future work. 1 1.0 0.5 no. of transmissions with IMIX 1000 300 no. of transmissions with IMIX 0 200 400 600 800 1000 3 1.0 800 250 200 600 150 400 100 200 2 0 no. of transmissions with ETX-based forwarding 50 0 0 50 100 150 200 250 300 no. of transmissions with ETX-based forwarding Fig. 1. An example for single hop IMIX (a) IMIX vs. Normal forwarding (b) IMIX vs. Normal forwarding with perfect acknowledgments Fig. 2. Due to intra-?ow wireless coding, IMIX has much better performance than normal forwarding. Though, if we assume perfect acknowledgments, IMIX does not signi?cantly outperform normal forwarding. II. IMIX:INTRA-FLOW MIXING In [5], the authors proposed that intra-?ow coding can be used to dramatically improve the performance of opportunistic routing. Later, [4] extended the usage of intra-?ow coding to best-path routing. However, their primary goal was to increase reliability for single hop transmissions, while we attempt to use coding for any packets heard on the medium. In previous research, the potential of intra-?ow coding to exploit overheard transmissions in best-path routing has never been explored. Consider the simple scenario showed in Fig. 1, suppose there is a path from node 1 to node 3 via node 2 with 100% delivery ratio. Node 1 can also reach node 3 with a 50% delivery ratio. Assuming links are symmetric, the ETX value of path 1?2?3 will be 2, and of path 1?3 will be 4. The former one will be chosen by current routing algorithms. Using this path, the lower bound of the total transmissions for n packets is 2n+2 (2n packets and 2 acknowledgments). By using wireless network coding, this number can be decreased further. Suppose that node 1 sends the random linear combinations of n packets. Node 2, after receiving n coded packets, should be able to decode them (since the coef?cients are randomly generated, we can suppose these combinations are linearly independent). At node 3, approximately n/2 coded packets should have been received simultaneously from node 1. Thus, only n/2 more packets are needed for node 3 to decode the original n packets. Node 2 will send new random linear combinations of all the packets it received, and node 3 will send an acknowledgment to node 2 after receiving n/2 packets. The total number of transmissions can thus be reduced to 1.5n + 2. We describe this network coding scheme, called IMIX (Intra-?ow MIXing), as follows: De?nition (IMIX) At each hop within a single ?ow, 1) The sender codes n packets with random linear coding, and keeps sending randomly coded packets until it receives an acknowledgment from the next hop. 2) The next hop sends an acknowledgment immediately after receiving n linearly independent coded packets. If the next hop is the destination, it will recover the original data using the coded packets and the coef?cients in the header, otherwise it will forward the packets by following rule 1. IMIX is not dependent on the routing protocol. It can operate below any single path routing protocol. The coding gain of IMIX is the result of possible overheard transmissions from all previous hops in the path. If there are no overhearing opportunities, the necessary transmissions will be the same as that with linear coding mentioned in [4]. This property guarantees that this scheme will not increase the number of transmissions, even in the worst case. Notice that more overhearing opportunities doesn’t always imply more coding bene?ts. The reason is, with high packet overhearing from up stream nodes, a node needs fewer packets from its previous hop to decode the packets, which will decrease the opportunities for subsequent hops to overhear transmissions. Now the question is, how many overhearing opportunities can we take advantage of in a wireless network? In Fig. 2(a) we compare IMIX with normal ETX based best-path forwarding. We use the trace data from Roofnet [6], and the settings of the evaluation are introduced in section V. Fig. 2(a) shows that IMIX can reduce the transmissions by half or more. Unfortunately, most of the gains in Fig. 2(a) are not from overhearing, but from the poor performance of the acknowledgment scheme used by normal forwarding. Traditionally, acknowledgments will be sent for every single data packet, but with intra-?ow coding, only one acknowledgment is needed for every n packets [4]. We achieve the same performance as an optimal acknowledgment scheme, without the cost of increased protocol complexity and larger sized ACKs from the receiver. In order to correctly obtain the gain by overhearing, we must assume perfect acknowledgments so that our results are not skewed towards IMIX due to its robust acknowledgment scheme. We use this assumption for normal forwarding in the remainder of this paper. With this assumption, retransmissions will occur only when data packets are lost, but not acknowledgments. Fig. 2(b) shows the gain achieved by IMIX over normal routing under this assumption. We can see that the gain from overheard transmissions is not signi?cant. This can be best explained as a side effect of the ETX based route decision process. During the ETX route selection process between a node pair, an intermediate node which is physically closer to the destination is more likely to be selected as the next hop. This will result in longer links and less total hops. Both of which will decrease the probability of overhearing transmissions from previous hops. In fact, during our evaluation we found that even though there are overhearing opportunities on certain links, the transmission quality of most of these links are poor and would not contribute signi?cantly to coding gain. Roofnet nodes ETX path OSPR path c TABLE I NOTATION Si rm,v spt u v O(v) u Pspt rest(m) disv u Dv parent(v) no. of necessary transmissions for each packet by the ith hop delivery ratio on link m ? v the SPT tree being built the last joined node a neighbor of the last joined node the probability of each packet overheard by v set of nodes along the shortest path from the root of spt to u the probability that node m still need to transmit a packet the minimal distance from root to v through u the minimal distance from root to v the parent node of v in spt b a Fig. 3. A Roofnet scenario Since ETX-based routing does not work well with IMIX, in order to ?nd out how many overhearing opportunities exist in wireless networks, an overhearing aware routing algorithm is needed to maximize the coding gains of IMIX. We will discuss this algorithm in the next section. III. OSPR:OPPORTUNISTIC SINGLE-PATH ROUTING An overhearing aware routing algorithm must take into account the overhearing probabilities from each of the upstream nodes at a given node. We ?rst describe the metric for calculating the number of necessary transmissions with overhearing and then give the algorithm for ?nding the routes with the metric. If we de?ne Si as the number of necessary transmissions for each packet from the ith hop of a path (0 for the source) to the its next hop, we can capture the possibility of a transmission being overhearing by another node in this path with Si × ri,j Here ri,j is the delivery ratio on the link between the ith and jth node on a path. Using IMIX, a node uses the overheard packets from all hops preceding it. Because there is no duplication in information due to the use of linear coding, the possibility of one packet being overheard by the i+1 node in a path can be expressed as: i?1 more hops, and therefore can provide more overhearing opportunities. Fig. 3 shows the difference between the OSPR path and the ETX based best-path, which are calculated for the same node pair in the Roofnet [6] topology. Although the OSPR path has two more hops, it can actually achieve better throughput under IMIX by providing more overhearing opportunities. Alg 1 1: 2: 3: 4: 5: 6: 7: 8: 9: : SPT Updating procedure for OSPR: Update(v, spt, u) O(v) ? 0 u for all p ? Pspt do if rm,v > 0 then O(v) += rm,v ? rest(m) rest(m) ? (1 ? min(1, O(v)))/rm,v disv ? rest(u) + D u u if disv < Dv then u Dv ? disv u parent(v) ? u (Sj × rj,i+1 ) j=0 Note that the maximum probability of overhearing a transmission is one, therfore any value greater than one should be treated at one. The resulting equation for the number of necessary transmissions for each packet from the ith node to its next hop in a path is: Si = 1 ? min(1, i?1 j=0 (Sj × rj,i+1 )) ri,i+1 By using the value Si , it is possible to select routes that maximize intra-?ow coding gain. Our routing algorithm that uses this coding opportunity metric is called OSPR (Opportunistic Single-Path Routing). Compared with normal best path routing, OSPR routes have a higher probability of including OSPR can be implemented by simply replacing the distance updating procedure in Dijkstra algorithm by Alg 1. The notation used here is listed in Table I. The time complexity of the modi?ed Dijkstra algorithm is O(n3 ), larger than the O(n2 ) complexity of original Dijkstra but still acceptable. OSPR can be applied not only in proactive routing protocols, but also in most reactive protocols. For example, in DSR, Si can be calculated and carried in route requests at each hop, so the destination can ?nd the best route by comparing the route requests from different neighbors. Now we can answer the question proposed in last section, how many overhearing opportunities can we take advantage of in a wireless network? Evaluation results in section V shows that the performance of IMIX is affected by the routing algorithm. With IMIX using ETX based best paths, IMIX can save no more than 2% of transmissions in comparison with normal best-path forwarding. In contrast, with OSPR the overhearing savings increase but are partially offset by the longer hops taken by OSPR. We further analyze and show more evaluation results about running IMIX with OSPR In section V. It is interesting to compare OSPR with opportunistic routing. Their gains are both based on the broadcasting nature of wireless transmissions. Both take advantage of possible long jumps towards the destination which are not reliable enough for traditional best-path routing. But opportunistic routing can 1 1.0 3 2 1.0 4 0.5 0.5 5 (a) A typical scenario in which can bene?t from both intra-?ow and inter-?ow coding 2 I2 MIX 1 3 1 3 4 2 6 3 1 2 4 5 4 5 5 (b) Linear coding gain (c) ”Early-Forwarder” gain (d) ”Gossip” gain Fig. 4. Scenarios in which I2 MIX can have gain. Dashed lines represent overheard transmissions, with the delivery ratio noted beside the line. Solid lines show links actually used for transmissions, which we assume has a delivery ratio of one. also use multiple forwarding candidates which may exist in some scenarios to reduce transmissions, while IMIX can only bene?t from just a portion of them. However, according to [7], The majority of the the node pairs in Roofnet have only one good candidate, and about 90% have no more than two. Since, this work is on coding we intend to explore this in future work. IV. I2 MIX:INTRA-FLOW&INTER-FLOW MIXING The major distinctions between IMIX and MORE are: First, IMIX uses an acknowledgment at each hop, but MORE uses it from end-to-end; Second, and most importantly, IMIX relies on best-path routing instead of opportunistic routing, which is used in MORE. The latter one can not work well with inter-?ow coding (because inter-?ow coding – like COPE needs the information of the next hops, which is unknown in opportunistic routing). Conversely, IMIX still has a chance to bene?t from inter-?ow coding. In this section we present an improved version of IMIX – I2 MIX (Intra-?ow&Inter?ow MIXing). To the best of our knowledge, I2 MIX is the ?rst scheme that can combines both intra-?ow and inter-?ow coding. The description is as follows: De?nition (I2 MIX) At each node with packets in its sending queue: 1) The sender codes a set of packets in its queue using random linear coding, and continues sending randomly coded packets until receiving an acknowledgment from all the respective next hops of each coded packet 2) If a receiver is the next hop of the coded packets, it sends an acknowledgment as soon as it is able to recover the original data from the coded packets. It then examines those packets sent to it, and puts them in its sending queue unless the node is the destination. Fig 4(a) shows how I2 MIX can bene?t from both intra-?ow and inter-?ow coding. Assume node 1 is sending n packets to node 5 via node 3, and node 2 is sending n packets to node 4 via 3. With normal forwarding, node 3 needs to send at least 2 ? n packets. Using IMIX or COPE, the number of packets will be decreased to n. By using I2 MIX, the number of transmissions at node 3 can be further decreased. Since both node 4 and 5 have heard 1.5?n packets coded from the original 2 ? n packets, when node 3 broadcasts the coded combinations of the packets to 4 and 5, only 0.5 ? n more coded packets are needed for both of them to be able to decode. In other word, the number of transmissions at node 3 is reduced to 0.5 ? n. The key differences between I2 MIX and IMIX are: First, in I2 MIX, packets from all ?ows are coded together at a node, while in IMIX, packets are only coded with other packets from the same ?ow. Second, in I2 MIX, before the sender stops transmitting the current combination and move to the next one, it needs an acknowledgment from the next hop of each ?ow. Third, the packets need to be decoded at each hop in I2 MIX. This means there is a trade off between reducing transmissions and increasing computing complexity. Since communication resources are considered more valuable and increase at a slower rate than computing resources, it seems to be an obvious choice to prefer more computing usage to save communication resources. The distinctions between I2 MIX’s and COPE’s inter-?ow coding methods are: First, I2 MIX performs linear coding for packets from different ?ows, instead of a simple XOR as COPE does. Second, unlike COPE, I2 MIX needs no reception reports, which will cause constant overhead even when there are few coding opportunities. By using linear coding, I2 MIX will catch every existing coding opportunity, and no extra transmissions will be introduced. Besides gains already seen in IMIX and COPE, I2 MIX also has other bene?ts: Linear coding gain: Inter-?ow coding gain in I2 MIX is similar to COPE, but can be improved upon. The reason is because we use linear coding, thus overheard packets will not be duplicates. As we show in Fig. 4(b), When node 5 is able to hear from more than one previous hop in another ?ow, the packets it hears from different senders will each contain new information, which will provide more inter-?ow coding opportunities for node 3. ”Early-Forwarder” gain: As Fig. 4(c) shows, when link 2?4 has better delivery ratio than link 2?3, node 4 may recover the original packets earlier than node 3 and start to forward the received packets immediately. If node 3 is close to node 4, the packets it heard from 4 will help it to decode the coded packets it received from node 2. ”Gossip” gain: There are a number of other scenarios in which one node can overhear useful packets. We term all these additional scenarios ”Gossip” gain. Fig. 4(d) shows one of these scenarios. The packets node 3 overhears through link 4?3 while node 4 transmits to node 5 can help it decode the packets it has overheard through link 1?3 while node 1 was transmitting to nodes 2 and 4. In I2 MIX, packets from all ?ows will be coded together at each node. Although it provides us the integration of inter- ?ow and intra-?ow coding, this blindness in coding may cause a problem which has already been shown in Fig. 4(d). In this scenario, when node 1 is sending, it will code packets from ?ow 1?2?3 and ?ow 1?4?5 together, which may increase the dif?culty for node 3 to decode its overheard packets through link 1?3 since the coded packets now contain the packets from ?ow 1?4?5, which are currently useless to it. In fact, this problem exists in all inter-?ow coding schemes. In COPE, overheard packets may be coded packets, for which a node can do nothing but drop. To the best of our knowledge, this problem has not been solved yet. The coding gain from both intra-?ow and inter-?ow coding in I2 MIX will be reduced by the problem mentioned above. Fortunately, this reduction is not very signi?cant for the following reasons: First, it only affects overheard packets, because the transmission to the speci?ed next hop will be guaranteed by the receipt of an acknowledgment. Second, each node that overhears transmission will be able to successfully decode their packet as long as at least one of the actual next hops from the sender has a delivery ratio less than the delivery ratio from the sender to the overhearing node. Third, even if the overheard packets can not be decoded directly, they may be able to be decoded together with some cached packets or future packets. V. EVALUATION In this section we evaluate the performance of our proposed schemes using the link-level measurement trace of MIT Roofnet [6], a 38-node multi-hop wireless network. The measurement trace recorded packet delivery over each link of the network for a total of 90 seconds with transmission rates: 1, 2, 5.5 and 11 Mbps. We compute the average delivery ratio over 90 seconds for each link, and use this average value as its link-level delivery probability. We assume that perfect acknowledgments are used throughout the evaluation as explained in Section II. To minimize the randomness in traf?c generation, we generate a one-packet ?ow between every node pair. The number of transmissions with ETX based best-paths is de?ned by the sum of the ETX cost on the paths between all of these node pairs. Similarly, the number of transmissions with IMIX can be de?ned by the sum of Si (de?ned in section III) on all paths. For inter-?ow coding, we calculate the gain differently. We capture the gain from inter-?ow coding by rules similar to that of COPE. If a node is at the intersection of two ?ows, and its next hop on each ?ow (suppose they are node a and b) can overhear from some previous hops on the other ?ow, we assume there is a coding opportunity, and the gain can be found by the overhearing possibility on either a or b depending on whose value is less. Also, since ?nding an optimal mixing algorithm is NP-hard [8], for simplicity we only XOR code two packets together. A. IMIX We discussed in Section II that, with the assumption of perfect acknowledgement, linear coding has no gain when comparing with a regular ETX based scheme. Fig. 5(a) shows the gain with IMIX over a regular ETX based scheme with and without OSPR. It can be seen that the gain is negligible whelm IMIX is deployed on an ETX based path. Even with OSPR, the gains are not much (about 2-5%) and this can be explained with the results in Fig. 5(b). The longer hops chosen by IMIX increase the base ETX value and thus offset some of the gains. This is the penalty for preferring short hops with more overhearing opportunities for long hops. OSPR based paths show gains inspite of this additional overhead. Fig. 5(b) shows the cumulative distribution of fraction of ?ows vs. transmission savings for 2Mbps data rate. It can be seen that only about 20% of the nodes have any gain at all for an ETX based path. For OSPR based path, this increases to 65% (indicating the overhearing opportunities created by OSPR) but only about 30% of the nodes have a gain above 5% and the low average gain re?ects this. These results are consistent with those reported in [2]. With the perfect acknowledgment assumption relaxed, the gains will be much higher with IMIX as shown before. We feel that the Roofnet topology is also a signi?cant factor affecting the gain. A denser topology might yield better gains due to the increase in overhearing opportunities along the OSPR path. B. I2 MIX The evaluation result of I2 MIX is shown in Fig. 5(c). I2 MIX performs slightly worse than inter-?ow coding on an ETX based path and performs signi?cantly better on an OSPR path. This is because, when using an ETX based path, some coding opportunities are lost due to the useless overheard (coded) packets. This loss can easily be outweighed by choosing an OSPR path which increases overhearing opportunities. Routing on an OSPR path creates more coding opportunities because more nodes overhear packets and will be able decode coded packets. We obtained a gain of 21-30% in our evaluation of I2 MIX with OSPR. While these gains are signi?cant, they may not accurately re?ect the complete potential for gain because of the evaluation methodology and the topology. As mentioned in [3], the majority of gains in inter-?ow coding are obtained by reducing the traf?c at intersecting nodes, which are also likely to be congested nodes. This kind of improvement can not be shown in our of?ine evaluation and can enhance the real world performance of I2 MIX. The ”Firsthelp-others” gain and ”Gossip” gain can also be not shown in this of?ine evaluation. It is reasonable for us to believe that I2 MIX can have more gain in our future simulations. At lower data rates, the transmission range and thus the overhearing probability increases in the network which leads to an increased gain. For both IMIX and I2 MIX the gains are higher at lower data rates which can be observed in Fig. 5. VI. RELATED WORK Network coding was ?rst proposed for improving multicast capacity in wired networks [9]. There have been several coding schemes proposed for wireless networks, which can be divided into two categories, inter-?ow wireless network coding and 0.07 0.06 Fraction of saved transmissions IMIX/ETX IMIX/OSPR Fraction of saved transmissions 0.3 IMIX/ETX IMIX/OSPR Fraction of saved transmissions 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 Inter/ETX I2MIX/ETX I2MIX/OSPR 0.25 0.05 0.04 0.03 0.02 0.01 0 M 11 s bp 5M 5. 2M s bp 1M s bp 0.2 0.15 0.1 0.05 0 M 11 5M 5. 2M 1M 0 0 0.1 0.2 0.3 0.4 Fraction of flows 0.5 0.6 0.7 s bp s bp s bp Data rates (a) Transmissions saved by IMIX Fig. 5. intra-?ow wireless network coding [4]. An example of inter?ow coding is COPE [3], in which the intersecting nodes of multiple ?ows keep track of coding opportunities, and perform XOR coding whenever there is an opportunity found. MORE [5] uses intra-?ow coding to improve the performance of ExOR [1], which is an opportunistic routing scheme that can take advantage of the broadcasting nature of wireless. By using linear coding to reduce reliance on the reception of any single packet, MORE can increase the unicast throughput of ExOR by 22-45%. Linear coding has been extensively used for various applications. Speci?cally, [10] [11] and [12] show that linear coding can achieve the best capacity for multicast traf?c, and the required polynomial time complexity is bounded at O(n2 ) for encoding algorithms, O(n2 ) for testing innovation and O(n3 ) for decoding [13]. Our work differs from other inter-?ow coding schemes as we propose to use linear coding for inter-?ow coding. IMIX differs from other intra-?ow coding schemes because it takes advantage of the overhearing opportunities. Recently, a link layer mechanism RTS-id [2] was proposed, which is similar to IMIX in that it reduces duplicated packets by taking advantage of overheard packets. Though both schemes depend on link layer caching, their strategies are completely different. In RTS-id, a special RTS which contains the ID of the next data packet is used. If the receiver already has this packet in its cache, it will reply with a special CTS to save the duplicated transmission of the data packet. IMIX uses linear coding to take advantage of caching. We believe the savings in RTS-id is a subset of the saving in IMIX. This is because the duplication of packets has already been eliminated in IMIX, and in RTS-id duplication may still occur because overheard packets are not exploited. Also, as we discussed in this paper, without a proper routing strategy, there are not enough bene?ts from overhearing transmissions. We believe RTS-id can have more gain if it works with the IMIX aware routing algorithm, OSPR, proposed in this paper. VII. CONCLUSIONS Previous intra-?ow coding schemes such as MORE work only with opportunistic routing, but inter-?ow coding requires best-path routing, which means they cannot be applied together. To achieve the goal of integrating intra-?ow and s bp Data rates s bp (b) Transmissions saved on fraction of ?ows (c) Transmissions saved by I2 MIX Evaluation results for IMIX, OSPR and I2 MIX, with Roofnet topology inter-?ow wireless network coding, we proposed IMIX, an intra-?ow wireless network coding scheme based on best-path routing that can bene?t from broadcast transmissions. Since IMIX is not able to gain much from traditional ETX-based best-paths, we presented a routing algorithm called OSPR, which can ?nd the paths that expand the coding gain of IMIX. Finally, intra-?ow coding and inter-?ow coding are integrated within I2 MIX, an updated version of IMIX which can save between 21-30% of the transmissions in our evaluations based on the Roofnet topology, with the tradeoff resulting from applying hop-by-hop decoding instead of end-to-end decoding. Our next step is to investigate the performance of the above schemes with simulations in the QualNet simulator [14]. The results presented in this paper assume a ?xed rate for the whole network and we intend to investigate the effects of dynamic rate selection on IMIX and I2 MIX. REFERENCES [1] S. Biswas and R. Morris, “Exor: Opportunistic multi-hop routing for wireless networks,” in Proc. ACM Sigcomm, 2005. [2] M. Afanasyev, D. Andersen, and A. Snoeren, “Ef?ciency through eavesdropping: Link-layer packet caching,” in NSDI, 2008. [3] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, “Xors in the air: Practical wireless network coding,” in Proc. ACM Sigcomm, 2006. [4] C. Fragouli, D. Katabi, A. Markopoulou, M. Medard, and H. Rahul, “Wireless network coding: Opportunities and challenges,” in MILCOM, 2007. [5] S. Chachulski, M. jennings, S. Katti, and D. Katabi, “Trading structure for randomness in wireless opportunistic routing,” in Proc. ACM Sigcomm, 2007. [6] MIT Roofnet, “http://www.pdos.lcs.mit.edu/roofnet/,” . [7] Zifei Zhong and Srihari Nelakuditi, “On the ef?cacy of opportunistic routing,” in Proc. IEEE SECON, 2007. [8] R. Alimi, L. Li, R. Ramjee, H. Viswanathan, and Y. Yang, “ipack: innetwork packet mixing for high throughput wireless mesh networks,” in Proc. IEEE Infocom, 2008. [9] R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung, “Network information ?ow,” IEEE/ACM Trans. Information Theory, July 2000. [10] S. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE/ACM Trans. Information Theory, 2003. [11] R. Koetter and M. Medard, “An algebraic approach to network coding,” IEEE/ACM Trans. Networking, 2003. [12] S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen, “Polynomial time algorithms for multicast network code construction,” IEEE/ACM Trans. Information Theory, 2003. [13] Christos Gkantsidis and Pablo Rodriguez, “Network coding for large scale content distribution,” in Proc. IEEE Infocom, 2005. [14] “Qualnet Network Simulator,” http://www.scalable-networks.com/.

Pair-wise Resistance to Traf?c Analysis in MANETs Chase Gray, Jason Byrnes, Srihari Nelakuditi {graycm, byrnesj, srihari}@cse.sc.edu Department of Computer Science and Engineering University of South Carolina I. Introduction and Motivation Some of the same features that make MANETs attractive, such as mobility and self-organization, also lead to increased vulnerability to traf?c analysis. Data on who is communicating with whom, how often, how much, and when is easily available to any eavesdropper within range of the wireless network. Even if the payload is encrypted, standard MANET protocols transmit enough header and routing information in the clear making traf?c analysis relatively easy for attackers. But users of MANETs may want to resist traf?c analysis for a variety of reasons, ranging from secrecy for government and industry to simple personal privacy for individuals. Traf?c analysis is a threat to secure communication, either by identifying targets for attacks such as denial-of-service or encryption cracking, or by revealing communication relationships. Network-wide Anonymity Perhaps the most enduring idea for resisting traf?c analysis is the “mix” [1], in which messages are routed through an unpredictable series of proxies that alter it at each hop via encryption, stalling, padding, and other means designed to prevent recognition. Onion routing [2] is a derivative of the mix in which messages are encrypted in layers that must be decrypted independently by routers at each hop toward the destination. Another classic approach, Crowds [3], has cooperating nodes forward messages for each other in an unpredictable manor amongst themselves before sending the message toward its destination. While the above approaches are applicable to both wired and wireless, other efforts have produced protocols that are specifically designed for multi-hop wireless networks [4]. All these protocols require all or a large number of the nodes in the network to implement the protocol. Pair-wise Anonymity For governments and corporations that control their own networks, networkwide anonymity protocols may be suf?cient. However, there are other scenarios where a pair of users (government, industrial, or private) must communicate in a public network, but still wish to keep their relationship hidden. A public network will be unlikely (a) before (b) after Figure 1: Perceived throughput for each pair of nodes in a MANET before and after source node 48 takes measures to resist traf?c analysis. to have any sort of anonymity protocol since it increases complexity and cost, and is simply not needed by most users. Therefore, we need to devise a new protocol for enabling private anonymous communication between a pair of nodes without a network-wide anonymity protocol, which is the focus of this paper. To demonstrate users’ vulnerability to traf?c analysis, we simulated in ns2 50 randomly deployed nodes with 30 TCP and UDP ?ows of random duration. We selected a node pair to be the ”communicators of interest” and set a 10-second UDP ?ow between them. Figure 1(a) shows the information an omniscient attacker would be able to obtain from silently observing the network. The communication from nodes 48?30 shows up as one of the higher-throughput ?ows, so an attacker can assume a relationship between the two. Though not shown in the ?gure, this throughput could then be shown over time to show the duration, frequency, and volume at different times. We can resist traf?c analysis by altering the apparent destinations of packets which changes an adversary’s view from Figure 1(a) to that of Figure 1(b). Node 48 still appears to be sending the same volume of traf?c, but the apparent destinations are more numerous and thus each ?ow is less signi?cant. Now, an adversary would be more likely to focus attention on other more signi?cant ?ows. Our goal is to enable 48 and 30 to accomplish this effect without the assistance or knowledge of other nodes in the network. II. Our Approach A pair of nodes can resist traf?c analysis as illustrated in the previous section by having the source node address packets to another node in the network such that the path passes through or near the intended destination. The intended destination listens to all transmissions in its neighborhood and extracts those packets that are meant for it. We refer to this approach as Covert Neighborhood Transmissions (CoNTra). Our approach takes advantage of the broadcast transmissions and multi-hop paths intrinsic to MANETs. Suppose node S in Figure 2 wishes to reduce or eliminate the perceived volume of traf?c it is sending to D. S constructs and sends a packet that has data encrypted for D but a destination address for some other node, such as 6. If the packet’s route is S?1?4?6, when 4 transmits to 6, D can overhear the transmission and receive the packet. Therefore, D must listen to every transmission it can hear and check if the packet is really a CoNTra packet intended for itself. Analyzer Model Before describing how we decide where to send covert packets we need to de?ne a model of the attacker. We assume an omniscient observer that can hear all packet transmissions but may or may not be aware of CoNTra. The best traf?c analysis strategy for the CoNTra-aware observer would be to count transmissions at all nodes that can somehow receive a packet from S (directly, as a forwarder, or by overhearing) and suspect all of these nodes as CoNTra recipients of S. It could then narrow down these suspects by observing how the set of suspects changes as nodes move, join, and leave the network. As an example, suppose S is sending CoNTra packets to D on the path S?1?4?6. A na¨ve analyzer ? would count all the traf?c from S as messages for 6. A CoNTra-aware analyzer, however, would equally suspect 1, 2, 3, 4, D, and 6; that is, all the nodes that can hear a transmission anywhere on the path from S to 6. Node 6 is included as a suspect because the CoNTraaware analyzer can’t be sure if CoNTra is being used or if this is just a normal transmission. Now, instead of knowing precisely who the receiver is, there are 6 possible nodes to choose from. Now, suppose node 1 leaves the network and the CoNTra path switches to S?2?4?6. The analyzer will observe the same volume on this new path, so can therefore eliminate 1 from its list of suspects. Also note that although 5 is now in overhearing range of the path, the clever analyzer would not add it to the suspect set because it was not a potential receiver before 1 left. Therefore the number of suspects is narrowed from 6 to 5. Figure 2: A sample network: S is the CoNTra sender, D is the destination, and G is a ”ghost node”. Solid lines indicate direct transmissions and dashed lines indicate overheard transmissions. Note that realistic traf?c analysis will not be as easy as the above example due to network dynamism and uncertainty about packet receptions. Also, in realistic situations attackers would only have limited view of the overall network so would have to perform their analysis with incomplete data. Finally, S will likely have non-CoNTra ?ows to other destinations. Since it is dif?cult to impossible for an observer to distinguish CoNTra from non-CoNTra traf?c it would have to suspect nodes along these other paths as well. Path Selection The ?rst step in CoNTra path selection is to ?nd paths that either pass through D or through a neighbor that D can overhear. S ?rst identi?es D’s neighbors, then compiles a list of paths that include but do not terminate at the neighbor or D itself. The neighbor and path information can be gathered in a variety of ways, depending on the routing protocol. In DSR, for example, a node maintains a path cache for not only paths that it is using but for all overheard paths. D may assist S by sending it neighbors and potentially useful destinations derived from its cache. D can further improve the probability of successful transmission by using signal-to-noise ratio to identify neighbors that it can hear consistantly and sending only the best candidates to S. The next step is to choose the best path from the list of paths compiled in the ?rst step. To select this path S again uses any information it has about the network to calculate which path involves the largest number of nodes, through either overhearing or inclusion on the path itself. Under the global attacker model, the best strategy is to select one path for CoNTra that routes through as many nodes as possible and use this path as long as the topology is consistent. It may be tempting to use multiple paths to widen the set of potential suspects. But the ?aw in this approach is that no matter which path is added, D will always overhear the highest volume of traf?c (be- cause all CoNTra transmissions intersect around D’s neighborhood), and any additional nodes picked up as potential receivers will have signi?cantly less traf?c. For example, if the path S?3?5?7?8 is used, the suspects are nodes 1, 2, 3, 5, 7, 8, and D1 . It may be tempting to add S?2?4?6 and split the traf?c evenly between the two paths, but this only serves to make the possible traf?c at nodes 2 and D (the intersection of the overhearing area of the two paths) double that at the other nodes. Keeping the same path for a given topology ensures that all nodes get the same amount of traf?c (and therefore the same amount of suspicion) even if the list of nodes is smaller. Reliability Packet delivery may be less reliable with CoNTra because any guaranteed delivery or reliability mechanism present in lower layers of the network will only apply for delivering the packet to the addressee, not our intended destination. For example, the 802.11 RTS/CTS will not help avoid collisions at D because it is not part of the exchange. Retransmission triggered by acknowledgments would improve delivery probability but would create a data-ACK pattern revealing S and D’s relationship. To address this while providing guaranteed delivery we use batched negative acknowledgments. This removes both temporal correlation and 1:1 ratio of data and ACKs. Internal Observers A shortcoming of the basic CoNTra technique is some nodes in the network receive extra packets that are useless to them. If an attacker is participating in the network and not just listening passively (an “internal observer”) it could receive such unintelligible data, which it may assume is from a CoNTra sender. This would not directly expose the receiver but it would reveal the path being used for CoNTra, narrowing down the set of possible receivers. In the case that S knows of nodes that are not attackers S can avoid this problem by addressing CoNTra data to them whenever possible. If there is no real node in the network that S can safely address packets to it can work with D to create one: S requests a route to some non-existant “ghost node” G, and D responds with a Route Reply suggesting it has a direct link to G. S can now address a CoNTra packet to G; D will get the packet and forwards it to G but no real node will receive unexpected messages. The limitation of this method is it can be suspicious for D to be the only node that ever hears G. Also, it is impossible to create a node in the network anywhere else but adjacent to D, which may result in a shorter path and therefore fewer suspect nodes. Node 8 was chosen as the endpoint because although 7 works as well, using 8 adds an additional node to the set of suspects. 1 Route failures can also provide opportunities for avoiding internal observers. DSR and other protocols use Route Error messages to notify other nodes in the network of failed links. If S hears one of these messages concerning a path from which D can overhear, S can send on this path with a very low likelihood of the addressee actually receiving the packet. D will still receive the packet as it is on the near side of the break. Since this technique would be suspicious if S receives a Route Error message in response to an attempt to send on a route, S should only do this if it ?nds out about the error by overhearing a Route Error message destined for another node. III. Conclusions and Future Work We have outlined a new approach to countering traf?c analysis by a pair of nodes, a scenario that is largely unaddressed by previous research on anonymity. Our proposed approach distributes the perceived amount of traf?c from a source to a destination among nodes other than the intended destination. We have discussed the bene?ts and challenges of this approach, though a formal protocol speci?cation remains as our future work. Additionally, we plan to evaluate the ef?cacy of CoNTra w.r.t. the number of nodes, number of observers, mobility patterns, and traf?c volumes. We also intend to implement CoNTra in Click on our testbed of laptops and Meraki wireless routers. References [1] CHAUM, D. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM 4, 2 (February 1981). [2] GOLDSCHLAG, D. M., REED, M. G., AND SYVERSON, P. F. Hiding routing information. In Proceedings of the First International Workshop on Information Hiding (London, UK, 1996), Springer-Verlag, pp. 137–150. [3] REITER, M., AND RUBIN, A. Crowds: Anonymity for web transactions. ACM Transactions on Information and System Security 1, 1 (June 1998). [4] ZHANG, Y., LIU, W., LOU, W., AND FANG, Y. Mask: Anonymous on-demand routing in mobile ad hoc networks. In Transactions on Wireless Communications (September 2006), vol. 21, IEEE, pp. 2376–2385.

On Bit-Rate Selection for Opportunistic Routing Chase Gray Naveen Santhapuri Srihari Nelakuditi Department of Computer Science and Engineering University of South Carolina, Columbia, SC 29201 Email: {graycm,santhapu,srihari}@cse.sc.edu Abstract—Opportunistic routing (OR) schemes, such as ExOR, have been shown to provide signi?cant throughput gains over traditional best-path routing schemes for wireless networks. Though the performance of OR schemes depend on the bitrate, they currently use a ?xed rate for transmitting packets. While several schemes have been proposed for selecting bit-rate for unicast transmission to a single receiver, none of them are suitable for broadcast transmission to multiple receivers under OR. This paper attempts to maximize the bene?ts of OR with dynamic bit-rate selection. We ?rst de?ne a new metric, Expected Anypath Communication Time (ExACT), that captures the time to deliver a packet to destination with a given rate at each hop under OR. We then propose Bit-rate Selection for Opportunistic Routing (BitSOR) algorithm that minimizes ExACT for each pair of nodes in the network. We evaluate the performance of BitSOR using MIT Roofnet trace and demonstrate signi?cant potential improvement with dynamic rate over OR with the best ?xed rate. I. INTRODUCTION Multi-hop wireless mesh networks are becoming increasingly popular for last mile connectivity due to their ease of deployment and low cost. Emerging commercial applications of multi-hop mesh networks such as community wireless networks [1] and city-wide broadband Internet access [2], [3] might be coming to more metropolitan areas in the near future [4]. For most of these applications, the majority of the nodes are stationary and plugged in (not running on battery power). Therefore the focus of most routing algorithms for these networks is to maximize network throughput. Opportunistic routing (OR) schemes that take advantage of the broadcast nature of wireless transmissions have been actively researched over the past few years [5]–[8]. OR works under the assumption that each transmission is most likely overheard by multiple receivers. The number of nodes overhearing a transmission is partly a function of the bitrate at which the data is transmitted by the sender. If the sender transmits at a low bit-rate, then its packet might be heard by some far away nodes due to low SINR (signal to interference and noise ratio) requirements at lower rates. But it would tie up the wireless channel for many of its neighbors for a longer period of time due to the slower transmission rate. Conversely, if the sender transmits at a higher bit-rate, the packet loss probability would be high and the number of potential receivers might be few [9], but the channel would be occupied for less time. Thus, the bit-rate used for transmitting affects the throughput of an OR scheme signi?cantly. Nevertheless, previously proposed OR schemes use ?xed bit-rate, and dynamic bit-rate selection for OR is considered an open problem [8]. There are many schemes proposed for selecting bit-rate at the MAC layer [10]–[13]. But all of these schemes are interested only in determining the best rate for a single receiver. They are suitable for traditional routing protocols that forward the packet to a single next-hop along the chosen path. However, they are quite inadequate for OR where packets are broadcast to multiple potential receivers. While the problem of identifying the best rate for delivering a packet to multiple receivers is hard, it is even more so with OR. The ideal transmission rate under OR has to deliver the packet to at least one of the potential next-hop nodes (candidates), preferably to the highest priority candidate (which is “closer” to the destination than all other candidates). Probably due to the challenges involved in addressing this problem, previously proposed OR schemes use ?xed rate [5], [8] transmissions. In this paper, we take a step towards designing a practical dynamic rate selection protocol for OR by developing an of?ine algorithm for selecting the best rate at each node under OR for each destination. We make the following contributions in this paper towards maximizing the performance of OR for wireless networks with bit-rate selection: 1) We propose a new routing metric Expected Any-path Communication Time (ExACT) that captures the total transmission time needed to deliver a packet from a given node to its destination sending at the speci?ed rate at each hop under OR. 2) We present the Bit-rate Selection for Opportunistic Routing (BitSOR) algorithm. The algorithm selects the ideal bit-rate, the candidates at that bit-rate, and the priority for each candidate for each possible destination so as to minimize the corresponding ExACT. 3) We evaluate the performance of BitSOR using the MIT Roofnet trace [?] and demonstrate signi?cant potential improvement with dynamic rate selection over OR with the best ?xed rate, particularly for distant node pairs. The remainder of this paper is organized as follows. Section II provides an overview of opportunistic routing and existing bit-rate selection algorithms. Our new path metric for determining the best bit-rate for OR is presented in Section III. We illustrate the need for bit-rate selection for OR in mesh networks and describe BitSOR in Section IV. The MIT Roofnet trace based evaluation results are presented in Section V. We discuss the challenges in designing a practical scheme in Section VI. Finally, Section VII concludes and outlines areas for further work. II. RELATED WORK A. Routing Metrics The minimum hop count metric used for routing has been shown to not necessarily maximize the throughput of a ?ow in a wireless network [14]. Expected number of transmissions(ETX) [14] estimates the number of transmissions needed to deliver a unicast packet by measuring the loss rate of broadcast packets between pairs of neighboring nodes. ETX does not accurately re?ect the cost of a link when multiple bit-rates are available. A low rate link with a smaller ETX may actually be slower than a high rate link with a larger ETX. Expected Transmission Time (ETT) [15] addresses this limitation of ETX by accounting for bit-rate. Both ETX and ETT assume that a packet will travel along a single path from source to destination. This is not true for opportunistic routing, as a packet may travel along any one of the many potential paths through candidates. [6] presents a new metric, Expected Anypath Transmissions (EAX), that re?ects the number of transmissions needed to deliver a packet from a node to its destination under OR. In this work, we extend EAX to take the bit-rate into account to de?ne a new metric, ExACT. B. Opportunistic Routing Multi-hop wireless networks typically use routing techniques similar to those in wired networks [16], [17]. Recently there have been many schemes proposed that take advantage of broadcast transmissions to send information opportunistically. Extremely opportunistic routing (ExOR) is one such routing scheme [5] where, for each destination, a set of next-hop candidates are selected and each of them is assigned a priority according to its closeness to the destination. The highest priority node is chosen as the next-hop for forwarding, after the packet’s transmission, among the candidates that received it. Therefore, the utility of OR hinges on inter-candidate communication and candidate selection. ExOR does not take into account the availability of different bit-rates and hence may not select the best possible candidates. MORE [8] extends ExOR by increasing the usefulness of forwarding duplication due to unsuccessful inter-candidate communication. It achieves this by linearly coding packet combinations at each hop, thus attempting to ensure that each packet has new information. Due to this, they are able to mitigate the need for a robust acknowledgement scheme. In [8], the authors state that they were forced to evaluate OR at a ?xed rate due to the unavailability of an appropriate auto-rate mechanism for OR. This paper explores the scope for solving this problem by developing an of?ine algorithm for bit-rate selection for OR schemes. C. Rate Selection The original bit-rate selection algorithm was created for the WaveLAN-II 802.11 cards [10] called Auto Rate Fallback (ARF). Adaptive Auto Rate Fallback (AARF) [11] is an extension of ARF where step-up parameter is doubled every time the algorithm tries to increase the bit-rate and the subsequent packet fails. This is helpful when packet failures take up a large amount of transmissions time. The MadWi? device driver for Atheros cards [18] uses the Onoe algorithm which is much less sensitive to individual packet failure than the ARF algorithm, and basically tries to ?nd the highest bit-rate that has less than 50% loss rate. This algorithm is relatively conservative; once it decides a bit-rate will not work, it will not attempt to step up again until at least 10 seconds have gone by. Receiver Based Auto-Rate (RBAR) [12] chooses the bit-rate based on S/N measurements at the receiver. In CHARM [19] the authors uses a rate selection algorithm based on a moving average of estimated path-loss at the receiver. In both the above schemes, the basic intuition is that channel quality seen by the receiver is what determines whether a packet can be received. Opportunistic Auto-Rate (OAR) [20] takes advantage of higher bit-rates by opportunistically sending multiple back-to-back data packets whenever the channel quality is good but is not appropriate for networks using OR. SampleRate [13] chooses the bit-rate that it predicts will provide the most throughput based on estimates of the expected per-packet transmission time for each bit-rate. We intend to use the general concepts of SampleRate while designing a practical bit-rate selection scheme for OR. III. EXPECTED ANY-PATH COMMUNICATION TIME (EXACT) Current bit-rate selection algorithms try to ?nd the most ef?cient rate for sending with the assumption of a single receiver and are not applicable to OR. Therefore, OR protocols currently use a ?xed sending rate. This brings us to the question: How should auto-rate choose the best sending rate in order to maximize the bene?ts of OR? In this section we present our path metric for routing which will be used by the bit-rate selection algorithm to select the best rate. To develop our auto-rate algorithm for opportunistic routing, we need a new path metric that does not assume a single path. This is similar to EAX [6], which provides a metric for capturing the cost from source to destination assuming a packet could traverse any possible path. This new metric is termed Expected Any-Path Communication Time(ExACT). We extend on the formula in [6] to account for all possible sending rates. Because nodes could be sending at different rates we must normalize each value to total communication time instead of total number of transmissions, similar to [15]. Due to the 802.11 physical layer preamble being transmitted at the lowest possible rate, we must take this into account when determining the “effective” bit-rate. In this paper we are focusing our work with 802.11b, which has a preamble time of 192µs. Due to this, the “effective” bit-rate is closer to optimal as the packet sizes increase because the preamble time becomes a smaller portion of total communication time. The values calculated for 802.11b can be seen in Table I. To simplify computation, we assume that acknowledgement reception ratio is 100%. This is a reasonable assumption if an opportunistic routing scheme such as MORE [8] is used that does not require strict coordination among candidate nodes for forwarding. We calculate the total communication time to transmit a packet from a source s to a destination d, given 95% 97% 31 24 23 31 24 23 95% 23 19% 97% 31 97% 24 63% 97.5% 35 1 35 5 25% 37 52% 26 100% 52% 5 1 48% 35 98% 79% 89% 25% 37 1 63% 0 48% 37 73% 0 5 52% 0 52% 8 12 8 98% 12 26 8 12 26 98% (a) 5.5 Mbps (b) 11 Mbps (c) Dynamic Rate Fig. 1. Sample topologies, extracted from Roofnet trace, at 5.5 mbps, 11 mbps and optimal opportunistic rate for source node 5 and destination node 0. White nodes indicate node using 11mbps, gray nodes indicates node using 5.5mbps for broadcast, black nodes indicate unused nodes for that network instance. Invalid or unused links are represented with gray dotted arrows and valid links are represented with solid black arrows. TABLE I EFFECTIVE SENDING RATES FOR 802.11B Bit-rate 1 2 5.5 11 200 bits 0.5102 0.68493 0.8758 0.95156 1000 bits 0.83893 1.44509 2.6751 3.5347 4000 bits 0.9542 1.82482 4.35127 7.19895 12000 bits 0.98425 1.93798 5.05515 9.35374 A. Illustration Fig. 1 lists a set of topologies relevant for opportunistic routing between source node 5 and destination node 0. These were extracted from the Roofnet trace for two different bitrates, 5.5 Mbps in Fig. 1a and 11 Mbps in Fig. 1b. Fig. 1c is the resulting network when each node determines the best sending rate using the ExACT metric. The ExACT values can be seen in Table II, ??, and IV. We include all nodes used at any of the rates chosen. This is to help illustrate the changing opportunities at each node when selecting the best sending rate. Unused nodes in a certain network instance are shaded black, and their unused links are dashed and shaded gray. The solid black links show connections to each candidate that makes forward progress based on the ExACT metric for destination node 0. For illustration, let’s look at node 24 in Fig. 1. In Fig. 1a it is not involved in the forwarding at all. The ExACT values for nodes 23 and 8 do not indicate forward progress with a ?xed network rate of 5.5 Mbps, so we do not have a path traveling through node 24. In Fig. 1b, node 24 is involved in forwarding and it has chosen a rate of 11 Mbps. Node 24 is actually the only node with a connection to destination node 0. Finally, in Fig. 1c with dynamic rate selection, node 24 has been chosen to be one among the three nodes to send at 5.5 Mbps. It is also no longer the bottleneck node along the path to destination node 0. Source node 5 has gained many more chances for opportunistic routing and its resulting ExACT value re?ects this. By using rate selection for our opportunistic routing, we have gained more routes and have also been able to avoid a possible bottleneck link from node 24 to node 0. These types of gains occur frequently in the Roofnet trace data. We explore the results in more detail in Section V. B. Routing Protocol Our opportunistic routing protocol is based on the proposed ExACT metric. It involves the updating of ExACT values, selecting candidates, and prioritizing them. After the ExACT values are calculated for each node and each rate, the candidate set is constructed. All neighboring nodes that have a lower ExACT value to the destination than the current the candidate set C s,d . Suppose candidate ci is the candidate with priority i (with 1 being the highest). Suppose that packet s,d delivery probability from s to Ci is fi . Each node has a set of available rates. Let r denotes a speci?c effective sending ? rate (in Mbps) at node s, and ri denote the ideal transmission rate for packets from ci to d. Then we have, ExACT(s, d, r) = 1 r + i ? ExACT(ci , d, ri )fi i?1 j=1 (1 ? fj ) 1? i (1 ? fi ) The above equation is composed of three core parts. 1/r is the amount of time it takes to transmit a single packet at biti?1 ? rate r. ExACT(ci , d, ri )fi j=1 (1 ? fj ) is time from ci to d taking into account the probability that s delivers successfully to ci and fails to deliver to higher priority candidates. Finally we divide by 1 ? i (1 ? fi ), which is the probability of successfully delivering the packet to one of the candidates. The candidate selection process is explained in much more depth in [?]. IV. BIT-RATE SELECTION FOR OPPORTUNISTIC ROUTING (BITSOR) The bit-rate that yields the minimum ExACT value is the ideal rate at which source node s should broadcast a packet to its candidates corresponding to destination d. Since the ExACT expression is recursive, the computation starts at the destination and works backwards, calculating the minimum ExACT value at each candidate next-hop until the minimum ExACT value and the corresponding rate r? at the source is known. This resulting value is the total time to transmit a single packet at rate r? from s to d with the candidate set C s,d . We call our rate selection algorithm BitSOR (Bit-rate Selection for Opportunistic Routing). node (in other words that make forward progress to the destination) are included in the set. The candidates are then prioritized based on the ExACT values (least value candidate has highest priority). Gathering the delivery probabilities for ExACT values can be done by periodic probes [13] or by estimating reception probability at the receiver like in [19]. If there is bidirectional traf?c or ACKs, this information can be continually updated if the receiver embeds the delivery probability in the reverse traf?c. The interval between ExACT value updates can be selected based on the frequency of delivery probability changes. In [13] it was shown that any updates within 10 seconds are not helpful but this can vary from one topology to another. We are currently working on a practical opportunistic routing protocol taking these aspects into consideration. TABLE II VALUES FOR FIG. 1A Node 5 37 26 ExACT 13348 3854 2373 Cands 37 26,0 0 TABLE III VALUES FOR FIG. 1B Node 5 23 8 31 12 35 24 ExACT 11650 9290 11000 7940 9690 7930 6620 Cands. 23,8 31 12 24 35 24 0 0.03 ExACT (in seconds) with BitSOR 0.03 0.025 0.02 0.015 0.01 0.005 0 0.02 0.015 0.01 0.005 0 0 0.02 0.01 0.005 0.015 0.025 ExACT (in seconds) with fixed rate 11 Mbps 0.03 ExACT (in seconds) with BitSOR 0.025 0 0.005 0.01 0.02 0.015 0.025 ExACT (in seconds) fixed rate 5.5 Mbps 0.03 (a) 11 Mbps (b) 5.5 Mbps Fig. 2. The ExACT value (in seconds) with opportunistic routing with dynamic rate vs. opportunistic routing with various ?xed rates. The packet size is 12000 bits. V. EVALUATION In this section we present of?ine simulation results to assess the gains that can be obtained by using an optimal bit-rate selection algorithm for OR. We used the publicly available Roofnet trace data, obtained from 90 second transmissions by each node in the network. The ?rst set of results are based on the average delivery ratios over the entire time for each link. For the second set of results, we extracted the delivery ratios for each link during 85 one-second snapshots of the network. A. Topology based on delivery ratios over entire trace Our ?rst evaluation is the comparison of total time for dynamic rate vs. ?xed rate opportunistic schemes for each (src,dest) pair. Fig. 2 shows scatter plots of all node pairs for 11 Mbps and 5.5 Mbps respectively. In the 11 Mbps case, most of the node pairs perform only slightly better with dynamic rate but for some node pairs ?xed rate can be four times worse. In contrast, 5.5 Mbps performs consistently worse than 11 Mbps but the most variation seen is less than half. This would imply that always sending at 11 Mbps would result in more TABLE IV VALUES FOR FIG. 1C Node 5 37 23 1 31 26 24 ExACT(in µs) 8080 3510 6240 4910 5100 1310 3780 Rate (mbps) 5.5 5.5 11 11 11 11 5.5 Improvement 30.6% N/A 32.8% N/A 35.7% N/A 42.9% Cands 37,23 0,26 1,31 37,24 24 0 0 frequent path cost changes that might have to be updated at neighboring nodes. Conversely, 5.5 Mbps is much less prone to have constantly varying ExACT values. The box plot in Fig. 3 shows the mean, median and standard deviation for the ExACT values of dynamic rate and all ?xed rates. The error bars show the ?rst and fourth quartile to the minimum and maximum ExACT values respectively. We can again see that the variation of ExACT values at 11 Mbps is greater than the average dynamic rate ExACT value for the entire fourth quartile. Fig. 4 shows the gain over ?xed-rate schemes for a different number of hops. The gains are higher for four and ?ve hops and these results also corroborate the results in Fig. 2 and 3 showing a number of pairs performing very well with optimal dynamic rate while many perform about equal. The number of (src,dest) pairs selecting a data rate varies with the size of the packet and is shown in Fig. 5. At lower packet sizes there are more 5.5 Mbps links but as the packet size increases, the 11 Mbps links dominate the network. This is because of the physical preamble overhead (192µs) whose signi?cance decreases with an increase in packet size. This results in a higher increase in effective rate of 11 Mbps at higher packet size when compared with 5.5 Mbps and thereby reduces the ExACT value for 11mbps links. B. Snapshot topologies based on one second averages Signal conditions vary frequently and the resulting changes to delivery ratios and the topology may effect the optimal bit-rate. To see this affect we created topology snapshots by extracting delivery ratios of all links for each second. By measuring the improvement variations and optimal-rate variations we show how often the optimal rates change and how many (src,dest) pairs operate at a given optimal rate. Fig. 6 and Fig. 7 show the aggregate ExACT improvement over ?xed rates for each snapshot for 12000-bit packets and 4000bit packets respectively. It can be observed that at lower packet sizes there are more links using 5.5Mbps (resulting in a lower speedup value) and hence the resulting gain from ?xed rate 5.5Mbps reduces while the gain over 11Mbps increases. We can also see again the stability of 5.5 Mbps even over 85 one second intervals. In Fig. 8, the number of times the selected rate changes over the entire trace time at one second intervals is shown for each (src,dest) pair. We can see that there is a signi?cant amount of change occurring for each node pair. 1200 Number of (node,dest) pairs 1000 1 2 5.5 11 800 600 400 200 Fig. 3. Comparisons between ExACT values for opportunistic routing with dynamic rate (OR-DR) vs. opportunistic routing with ?xed rate (OR-FR). The packet size is 12000 bits. 0 Ratio of ExACT with dynamic rate vs. fixed rate 5 Ratio of ExACT with dynamic vs. fixed rate 4 Fig. 5. Actual bit rates selected for each source destination pair at each packet size 20 0 Packet Size in Bits 10 00 40 00 12 00 0 4 3 40 Total communication time improvement (%) 3 35 5.5 mbps 11 mbps 2 2 30 1 0 1 2 3 4 5 Number of ETX hops 6 7 1 0 1 2 3 Number of ETX hops 4 5 25 (a) 11 mbps (b) 5.5 mbps Fig. 4. The gain obtained as number of hops increase. OR-DR vs. OR-FR with a packet size of 12000 bits. 20 15 Total communication time improvement (%) Overall we have found signi?cant improvements can be found by selecting appropriate rates in opportunistic routing. Some of the potential is not re?ected in the Roofnet topologies because of the fewer (4) 802.11b rates and fewer nodes in the network. It is also due to the delivery ratios measured without any internal interference which enables a disproportionately large number of 11 Mbps links as shown in Fig. 9. With a mesh network using 802.11a radios, there are a total of 8 data rates available and the need for selecting optimal rate might be even more signi?cant. We plan to test this hypothesis on a testbed soon. VI. CHALLENGES AND DISCUSSION Bit-rate selection for OR can be approached in many ways. Simple local heuristics can be used to reduce state propagation overhead but might not give a global improvement. Two intuitive ideas can be picking the rate which is best for most of the candidates and picking the best-rate of the next-hop candidate with the best ETT. It is not immediately clear if these approaches will result in a near-optimum value. BitSOR selects rates that minimize the ExACT values. Thus far we have presented an of?ine bit-rate selection protocol which requires each node to have the delivery ratio information from every other node in the network. This is 10 0 20 40 60 80 Topology snapshot time (seconds) Fig. 6. Percentage improvement in total communication time for 85 one second topology snapshots. 12000 bit packets 30 5.5 mbps 11 mbps 25 20 15 10 0 20 40 60 80 Topology snapshot time (seconds) Fig. 7. Percentage improvement in total communication time for 85 one second topology snapshots. 4000 bit packets 40 Count of bit-rate changes 30 consistency is much higher and distance vector updates would be much less frequent. If the node wished to choose 11 Mbps, it may choose to not update when its ExACT value varies but, on average converges to its reported ExACT value. VII. CONCLUSION AND FUTURE WORK 20 10 0 0 500 1000 Node Destination Pair # Fig. 8. 2000 Number of nodes changing rates. The rates are shown by interval. Number of node-destination pairs using bit-rate 1500 5.5 Mbps, 12000 bit packet 11 Mbps, 12000 bit packet 5.5 Mbps, 4000 bit packet 11 Mbps, 4000 bit packet Bit-rate selection for opportunistic routing is an interesting open problem. In this work we address this problem by proposing a new metric, ExACT, and a new bit-rate selection algorithm, BitSOR, to select the ideal rate for OR. Our evaluation based on the Roofnet trace data has shown that dynamic rate selection performs signi?cantly better than OR with the best ?xed rate, particularly for distant node pairs. It also indicates the scope for further improvement in other topologies with 802.11b and networks using 802.11a radios. We are currently running the MORE [8] implementation on our testbed of Atheros chipset based routers, which we are extending to use BitSOR to determine the appropriate sending rate. REFERENCES [1] B. A. Chambers, “The Grid Roofnet: A Rooftop ad hoc wireless network,” MS Thesis, MIT, 2002. [2] “Seattle wireless,” http://www.seattlewireless.net. [3] “Bay area wireless users group,” http://www.bawug.org. [4] “Austin wireless,” http://www.austinwirelesscity.org. [5] S. Biswas and R. Morris, “Opportunistic routing in multi-hop wireless networks,” in ACM SIGCOMM, Aug. 2005. [6] Z. Zhong and S. Nelakuditi, “On the ef?cacy of opportunistic routing,” in Proceedings of SECON’07. IEEE, 2007. [7] R. C. Shah, S. Wietholter, A. Wolisz, and J. M. Rabaey, “When does opportunistic routing make sense?” in PERCOMW ’05: Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications Workshops. Washington, DC, USA: IEEE Computer Society, 2005, pp. 350–356. [8] S. Chachulski, M. Jennings, S. Katti, and D. Katabi, “Trading structure for randomness in wireless opportunistic routing,” in ACM SIGCOMM. New York, NY, USA: ACM, 2007, pp. 169–180. [9] D. Aguayo, J.Bicket, S.Biswas, G.Judd, and R. Morris, “Link-level measurements from an 802.11b mesh network,” in ACM SIGCOMM 2004, Aug. 2004. [10] A. Kamerman and L. Monteban, “Wavelan(c)-ii: a high-performance wireless lan for the unlicensed band,” Bell Labs Technical Journal, vol. 2, no. 3, pp. 118–133, 1997, http://dx.doi.org/10.1002/bltj.2069. [11] M. Lacage, M. H. Manshaei, and T. Turletti, “Ieee 802.11 rate adaptation: A practical approach,” citeseer.ist.psu.edu/719742.html. [12] G. Holland, N. H. Vaidya, and P. Bahl, “A rate-adaptive MAC protocol for multi-hop wireless networks,” in Mobile Computing and Networking, 2001, pp. 236–251, citeseer.ist.psu.edu/holland01rateadaptive.html. [13] J. C. Bicket, “Bit-rate selection in wireless networks,” 2005, http://dspace.mit.edu/handle/1721.1/34116. [14] D. D. Couto, D. Aguayo, J. Bicket, and R. Morris, “A high-throughput path metric for multi-hop wireless routing,” in Proc. ACM Mobicom, 2003. [15] R. Draves, J. Padhye, and B. Zill, “Routing in multi-radio, multi-hop wireless mesh networks,” in Proc. ACM Mobicom, 2004. [16] C. Perkins, “Ad-hoc on-demand distance vector routing,” 1997, citeseer.ist.psu.edu/article/perkins97adhoc.html. [17] C. Perkins and P. Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers,” in ACM SIGCOMM, 1994, pp. 234–244, citeseer.ist.psu.edu/perkins94highly.html. [18] “Madwi?,” http://sourceforge.net/projects/madwi?. [19] G.Judd, X. Wang, and P. Steenkiste, “Extended abstract: Lowoverhead channelaware rate adaptation,” in Proc. ACM Mobicom, 2007. [20] B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly, “OAR: an opportunistic auto-rate media access protocol for ad hoc networks,” Wirel. Netw., vol. 11, no. 1-2, pp. 39–53, 2005. 1000 500 0 0 20 40 60 80 Topology snapshot time (seconds) Fig. 9. Total node-destination pairs using a certain rate for each one second topology snapshot. not practical for a real-time rate selection algorithm. We are working on a hybrid distance vector and link state routing protocol. Using this approach, nodes periodically ?ood their best estimate ExACT values to each destination. This information is used to maintain relative consistency among nodes. Between link state updates, nodes piggyback updated ExACT information on opportunistic packets. Because nodes interested in using this forwarder should most likely overhear when the forwarder transmits the packet, updated ExACT information would trickle in the reverse path direction beginning at neighbors of the destination. Nodes that cannot overhear these piggybacked updates would not be at a loss because the forwarder is probably out of range or has a low delivery ratio. To reduce the effect of frequently changing ExACT values in the network, nodes do not recalculate them unless the updated ExACT value is signi?cantly differing from the current value within a threshold. Furthermore, nodes may prefer to maintain consistent ExACT values as opposed to minimizing them. From our results, a node could maintain a more consistent ExACT value by using 5.5 Mbps. By using this lower rate, ExACT time is not signi?cantly lower, but

MANETs’ openness and adaptability increase their vulnerability to traffic analysis Observers can easily gather traffic flow source, destination, volume, duration, frequency, and timing from routing information Data encryption does not prevent this Of concern for law enforcement, military, personal privacy, and commercial interests Observers are passive analyzers classified as follows: External: “Hears” everything but does not participate in routing Internal: Participates as a node in the network S can reach D via 3 5 7 8, 3 5 7, 2 D G, 1 4 6, etc When 5 sends to 7, D overhears Increased likelihood of collisions at D due to listening to nodes without being part of the RTS/CTS exchange D’s participation reveals that D is attempting to listen to a packet that was not destined for itself Acknowledging each packet gives D away by creating a pattern For guaranteed delivery D sends batched negative acknowledgements Removes timing correlation between data and ACK Reduces the volume of traffic from D to S Simple traffic analysis (left) shows throughput for each source-destination pair Assume 48 30 (shown in green) wishes to conceal its high traffic volume By dispersing 48 30’s traffic to other nodes in 30’s neighborhood, 48 30’s relationship is less apparent (right). We have written a DSR ns2 simulation that measures anonymity by counting total packets per flow and have found that CoNTra can send as little as one packet directly to D and still maintain acceptable delivery ratios In addition to counting packets, we must consider more advanced attacks: Count traffic at each node on and in listening distance of all paths from S Weigh nodes with some metric in addition to traffic intensity The following graph shows the number of unique nodes S addresses packets to in order to get information to D “Ghost node” created by D; S can send to this node to avoid internal observers Existing protocols for resisting traffic analysis require all nodes in network to implement a common protocol, which is not always practical CoNTra is a pair-wise protocol Only the pair that’s communicating implements – or even knows about – the protocol Works in existing MANETs without modification to any network protocol Sender S sends data meant for destination D to nodes other than D on paths that pass through D’s listening range When D hears a node forward a CoNTra packet, it quietly accepts it Primary issues Path Selection: Select paths that D can overhear reliably Avoiding Detection: Make it difficult for observers to detect the use of CoNTra 7 and 8 may get CoNTra data addressed to them but not actually for them The simulation was conducted with 5 m/s random motion and mixed TCP and UDP flows for 30% of the nodes The “Isolated” results show the number of nodes used when S communicates only with D. “Active” indicates S is active in the network with nodes in addition to D In general it is better for a CoNTra node to be active with other (non-CoNTra) destinations because this provides more path information Generally, CoNTra’s ability to disperse traffic increases with the number of nodes 1. Collect pool of usable paths Find all nodes that D can hear directly Collect all paths from S that terminate beyond these nodes Paths can be from own cache or sent to S by D in a scheduled update packet 2. Choose a path for each transmission, preferring: Longer paths after D to increase set of possible receivers Lack of a predictable pattern Uniform selection of nodes in D’s neighborhood and beyond D Goal: increase the cost or difficulty for an attacker to correctly deduce a sender/receiver relationship Assuming observers know exactly how CoNTra operates, try to look as much as possible like a normal network node Must maintain a façade of normal network participation while using CoNTra techniques Addressing data for D to other nodes in the network is vulnerable to internal observers To counter internal observers, packets should never reach addressee Use “ghost nodes” D fabricates route requests and other information to spoof the existence of a node in its neighborhood S sends to this node; no real node gets the packet Use bad paths Listen for evidence of bad paths, such as route errors If the bad path can still get the packet to D, use it quickly for a small number of transmissions Apply CoNTra to AODV, OLSR, and other protocols Consider more than 2 cooperating CoNTra nodes Possible application for emergency vehicles in VANETS Characterize traffic analysis attacks specific to CoNTra Create effectiveness/anonymity metric for CoNTra Continue simulation Wider variety of scenarios Measure performance based on effectiveness metric Implementation on Meraki routers and laptop testbed using MIT Click