Network coding in wireless

* Wireless medium is broadcast
* Intermediate relays mixed packets 
* Multiple next hops can decode the same mixed packet into multiple packets

1. An example:






Benefits:
* better throughput
  no coding: 4 separate transmissions
  coding: 3 separate txs

Requirements & Caveats:
* A and B must store all transmitted packets
* R must indicate which packets are coded together: A+B
* A and B must send similar amount of traffic

2. Does it work if only A sends?

3. How about if two flows in similar directions traversing the same router R?







4. How about two flows in similar directions traversing different routers R?








5. How about more flows? 3 flows, opposite directions?








6. How about many flows, but all nodes can hear each other?





MAC gain. 
802.11 MAC allocates b/w to each node propoortionally to the number of its competing senders 
Example A-R-B










What if links are lossy?

1. Does it work with one flow, two hops?







2. How about one flow traversing different intermediate Rs?






3. Many flows, all can hear each other?



Why coding inside the network is beneficial?
1. Utilize overhead or transmitted packets to 
  allow multiple nodes decode different native packets from same coded packets
2. When MAC tries to be fair, congested region limit e2e throughput, coding
  allows congested routers/regions to push out more information 
3. less coordination needed for reliability in the face of loss

Challenges & COPE solutions:

* Which packets to code?
  1. Must know what packets each of the next hop nodes already have.
  Solution:
  - Each node piggybacks reception reports in each packet header 
    (if no packets to send, broadcast reception report in separate pkt)
  - It takes a while to get reception report from receivers, senders also guess
    If node B receive packet X from node A, 
	 guess the set of nodes that also heard X based on link state loss information.
  - Code as many packets as possible such that all next hops can decode pkts with high prob.
  2. Code similar sized packets together. i.e. reduce waste due to padding 
  3. Code if possible, otherwise, just send native packets
  4. Never code packets headed to the same next hop (why not??)

* How to ensure hop-by-hop reliability?
  1. all next hops must ack the successful decoding of a packet
     but only one can ack synchronously with unicast (others snoop unicast packets).
	  others ack asynchronously in packet header
	  asynchronous ack causes packets to be re-ordered
  2. Do not reorder TCP packets
     the end node correctly orders received tcp packets before passing it to TCP layer

Performance:
Did COPE achieve throughput gains in the toy examples?
Roughly. UDP shows better gain because of MAC effects

Under scenarios of many random multi-hop flows?
No gain for TCP flows. 
Authors attribute to high loss rates due to hidden terminal.
Does toy example 1 also have hidden terminal problem?

Scenarios of all nodes accessing a single gateway?
No gain for TCP.

Discussions:
* this paper achieves benefits 1 & 2 of networking
  Increases aggregate throughputs in the presence of multiple flows?

  How about benefit 3?  Can we increase the throughput of a single (multi-hop) flow?
  EXOR does so without coding.
  See paper in reading list for a solution from the same set of authors using random network coding

* Can one mix signals instead of bits?
  Example 1:
  A <---> R <---> B 

  Example 2:
  A ---> R ---> B