Reading for Lecture Oct 9

XORs in The Air: Practical Wireless Network Coding

The paper shows that intelligently mixing packets increases network throughput. The COPE architecture’s principles exploit the broadcast nature of the wireless channel and the theory of network coding. It inserts a coding shim between the IP and MAC layers, which identifies coding opportunities and benefits from them by forwarding multiple packets in a single transmission.

The basic idea of COPE is that a COPE router XORs two packets from two nodes sending to each other and broadcast the XORed packet to both of the nodes so that the two can again XOR with their packets to get their expected packets, thus this process needs only three transmissions instead of 4. COPE architecture incorporates three main techniques: 1) Opportunistic listening; 2) Opportunistic Coding; and 3) Learning neighbor state.

Opportunistic listening happens since wireless is a broadcast medium so that nodes have many opportunities to overhear packets when they equipped with omni-directional antennae. Cope nodes in promiscuous mode snoop on all communications over the wireless medium and store overheard packets for a limited period of time. In addition, each node broadcasts reception reports to its neighbors about the overheard packets.

The opportunistic coding aims at maximizing the number of native packets delivered in a single transmission, while ensuring that each intended next hop has enough information to decode its native packets.

Since report packets can be lost during congestions, thus a node has to guess to learn about packets that its neighbors have using ETX metric broadcast to all nodes then estimates the probability that a particular neighbor has a packet as the delivery probability of the link between the packet’s previous hop and the neighbor.

The COPE actually has beneficial side effect on MAC because it reduces the mismatch between edge nodes and the routers resulting in fewer packets dropped and thus better gain.
The paper does not address the issue of packet reordering as they prefer to code packets of the same size. When finding the maximum number of packets encoded, they do not account for the error in wireless environment and implicitly assume that the links are error free. This probably not true since when n too large the probability that one packet is corrupted become considerably large, and if a node can not receive one packet out of n, it can not decode its expected packet thus a retransmission is likely to happen for each node.

ExOR: Opportunistic Multi-Hop Routing for Wireless Network

The ExOR chooses each hop of a packet’s route after the transmission for that hop so that the choice can reflect which intermediate nodes actually received the transmission. This deferred choice allows each transmission multiple opportunities to make progress by choosing the best possible current routes.

The basic idea of this routing is that when a source wants to send a packet, it broadcasts the packets and some sub-set of nodes will receive the packet. All the nodes run a protocol to discover and agree on which nodes are in that sub-set. The nodes in the subset closest to the destination broadcast the packet. Again the nodes receiving the second transmission agree on the closest receiver, which then broadcast the packet. This process continues until the destination has received the packet.

The agreement protocol must have low enough overhead that it does not overwhelm the potential throughput gain and must be robust in the face of packet loss that disagreement and thus duplicate forwarding are rare. ExOR must have a metric reflecting the cost of moving a packet forward from any node to the destination thus it helps choosing the closest node.

The ExOR must choose the most useful nodes as participants and avoid simultaneous transmissions by different nodes to minimize collisions. The ExOR operates in batches of packets and includes a list of prioritized candidate forwarders in each packet. The receiving nodes buffer successfully received packets and wait to the end of the batch. The forwarders then broadcast the packets in their buffer in prioritized order. The batch map included in each packet indicates the highest-priority node known to have received a copy of that packet.
Since ExOR operates in batches of packets, packets likely suffer from large delay.