Tag Archives: mesh

XORs in the Air: Practical Wireless Network Coding

S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, “XORs in the Air: Practical Wireless Network Coding,” ACM SIGCOMM Conference, (September 2006). [PDF]

Summary

This paper present COPE, a new forwarding architecture for wireless mesh networks that significantly improves the overall throughput by exploiting the shared nature of wireless medium using network coding. All the nodes communicate using broadcast in COPE. Each node stores overheard packets from its neighbors in a buffer pool for a short amount of time and also tells its neighbors what packets it has in its own pool using a bitmap. When a node transmits any packet, it uses the knowledge about its neighbor (if it knows) or intelligently guesses to XOR multiple packets together and transmits them as a single packet. Receiving node in the next hop, decodes the packet by re-XORing it with the packets in its pool. Packets are encoded only if they can be extracted in the next hop.

The authors explain through examples and prove theorems to show Coding gain and Coding+MAC gain (gain due to resource allocation less skewed toward hub-type nodes) of using COPE over traditional options. They have three results:

  1. In the absence of opportunistic listening, COPE’s maximum coding gain is 2, and it is achievable;
  2. In the absence of opportunistic listening, COPE’s maximum Coding+MAC gain is 2, and it is achievable; and
  3. In the presence of opportunistic listening, COPE’s maximum coding gain is unbounded.

There are several implementation related gotchas:

  • Packets are never delayed to avoid unnecessary queue development.
  • COPE prefers XORing packets of same length and keeps multiple virtual queues per neighbor based one for each packet size!
  • It also tries to avoid TCP packet reordering and use hop-by-hop ACKs and retransmissions.
  • While guessing whether or not to XOR one more packet to the mix, COPE calculates the probability based on some metric (ETX/ETT), and if the probability goes below a threshold (0.8 in the paper), it does not XOR that packet.
  • Moreover, COPE implements a pseudo-broadcast consisting of multiple unicasts to work-around default broadcasts poor reliability and lack of backoff.

COPE was evaluated on a 20 node 802.11a wireless testbed with a bit rate of 6 Mbps. Main results are:

  • For toy topologies, TCP flows get lower (no MAC gain) boost than UDP flows.
  • For a congested wireless medium, UDP flows gets 3-4x boost in overall throughput and approaches Coding+MAC gain. But with increasing load, UDP decreases and seems to have been stabilizing around 2x range.
  • But TCP suffers from hidden-terminal induced collision related backoff and cannot gain much using COPE. Without any hidden terminal, the maximum goodput shows 38% improvement.
  • Almost half the coded packets are XOR of only 2 packets and trailing off at a maximum of 5 packets.
  • Finally, if COPE based access network is connected to the Internet through a gateway, throughput gain varies from 5% to 70% based on uplink to downlink ratio.

Comments

This is an overall excellent paper that combines theory with practice and backs up the claims with wide range of experimental evaluation. The paper is also very well written and easy to follow. However, there are several issues that could use more explanation. COPE requires as many virtual queues as there are packet sizes (which they say essentially to be 2 for the Internet) for each neighbor within its hearing distance, and will have to look through all of them to find optimal XOR strategy. The paper does not provide any evaluation of how big they grow or how long its takes to optimally pick an XORing strategy.

The authors say that the pseudo-broadcast mechanism will make sure that every node gets more than once chance to overhear. However, they avoid to mention and evaluate that this might also result in a higher number of collisions and link layer retransmits.

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

J. Bicket, D. Aguayo, S. Biswas, R. Morris, “Architecture and Evaluation of an Unplanned 802.11b Mesh Network,” ACM Mobicom Conference, (September 2005). [PDF]

Summary

Planning and deployment of a large wireless mesh network in a urban area is complex, time-consuming, and expensive . This paper argues that an unplanned wireless mesh network with commodity hardware can do quite as well. The authors presents their experience with such an unplanned architecture, Roofnet, and evaluate multiple characteristics of Roofnet architecture.

Primary design decisions for Roofnet are as follows:

  1. Unconstrained node placement: No topology or planned coverage. 37 Nodes are pseudo-randomly spread over 4 square kilometer urban area.
  2. Omni-directional antenna: No directional high-fidelity connection. Nodes should be able to connect to anyone within their reach (based on some clever formula)
  3. Multi-hop routing: No base-station- or access-point-centric single hop connection. Nodes should be able to find their way to the Internet through multiple hops over the network.
  4. Routing optimization for throughput: No routing optimization for route route repair as in a mobile network. Routes are optimized for throughput in a slowly changing network.

Architecture

Roofnet is deployed in a densely populated urban area where line-of-sight propagation between nodes is often obstructed. Most Roofnet nodes are on top of three-four storeyed building with a few on higher ones. Each Roofnet node consists of a PC (running Linux, routing s/w on Click, DHCP server, and a web server), an 802.11b card (with RTS/CTS disabled), and a roof-mounted omni-directional antenna.

In order that Roofnet nodes be self-configuring several challenges must be addressed: address allocation, finding gateway to the Internet, finding best route to the gateway. Roofnet uses internal addressing mechanism which are translated using NATs for local network under each Roofnet node. Gateways are speacial Roofnet nodes that have wired connection to the Internet and provide NAT service for TCP flows originating inside Roofnet.

Roofnet routing protocol, Srcr, tries to find the highest throughput route between any pair of Roofnet nodes. Each Srcr node maintains a partial database of link metrics between other pairs of nodes and uses Dijkstra’s algorithms on that database. Nodes learn fresh link metrics by pushing, pulling (through flooding), or overhearing. Srcr chooses route with in estimated transmission time (ETT) metric that predicts the total amount of time it would take to send a data packet along a route (taking into account each link’s highest-throughout transmission bit-rate and its delivery probability at that bit-rate). Roofnet has its own bit-rate measuring and selection algorithm SampleRate to choose among the 802.11b transmit bit-rates.

Evaluation Results

  • Over all pairs, Roofnet throughput and latency averages are 627 kbps and 39 ms, respectively. The authors also found that Roofnet nodes are most possibly working at 5.5 Mbps.
  • Srcr uses mostly shorter links, almost all of the which that are faster than 2 Mbps, and it ignores most of the links slower than that.
  • Through simulation, the authors found that the network approaches all-pairs connectivity after total of number of node crosses 20, and average throughput increases with higher density. They postulate that higher density gives more shorter links with higher transmission rate to increase throughput.
  • In terms of robustness, the authors found that there are a few links (around a dozen) that contribute to half the throughput. They also found that there are two nodes that carries 43% of the total throughput.
  • A comparison against single-hop alternative shows that multi-hop architecture can operate with fewer number of gateways since it can take multiple hops to reach gateways (duh!). For single-hop scenario, minimum number of gateways for full Internet connectivity is found to be 5.
  • Distribution of throughout is dictated by hop-count with throughput decreasing significantly faster with increasing hop-count.The authors postulate that this is because of packet loss from inter-hop interference. However, they also found that RTS/CTS scheme, that is supposed to avoid such collisions, does not even performance.

Critique

This paper performs an elaborate measurement study to propound unplanned mesh network deployment as a considerable alternative to engineered network deployment in an urban area. However elaborate, there are several things that require further explanation. First of all, Roofnet ‘layer’ and Roofnet addressing scheme could use better explanation. It is not clear why they needed a different layer and how they used it.

Secondly, a significant number of evaluations have been done using a mathematical formula of end-to-end throughput, which – the authors admit – has estimation error. However, there was no evaluation regarding the level of estimation mismatch it is causing. If the introduced error is quite high, then all the results will be affected. Since the total number of nodes is very low, even smaller changes in required number of nodes for ‘X’ is significant.

In addition, there is no evaluation regarding how SampleRate works, what it selected in practice, and what was used for simulation. One might assume that the authors were using 5.5 Mbps in simulation based on their findings from basic performance analysis. A little clarification could help.

Finally, based on their results (e.g., 2 nodes carrying 43% throughput, 12 links carrying 50%, very few links were highly used) it seems plausible that a spanning tree was formed. It would have been nice to know the properties of such formation (even though on pseudo-random graphs).