ExOR

Sanjit Biswas, Robert Morris, "ExOr: Opportunistic Multi-Hop Routing for Wireless Networks"

Departure from traditional wireless routing

• do not model wireless network as point-to-point links
• use the broadcasting nature of wireless
• Idea: to route packet from A to B, broadcast packet, see how far it went, i.e. which node N received it and is closest to B, repeat process from N

Example

• Take sequence Src-A-B-C-D-E-Dst
• It would be great if Src sends it, then the furthest station (which received the packet correctly) forwards it and so on
• this works better because at most the probabilities are known which stations are likely to receive the packet, the routing decision is deferred until the packet is send and it is known which links worked and which didn't
• each forwarding step is an independent random event
• if there are parallel structures, there are independent chances which link will succed, hence the total chance of any of links succeding will be higher
  

Challenge

• algorithm must find a node N or a set of nodes N which will forward the packets, all other nodes who received the packet will drop it
• if this algorithm gives no such node N, the packet is lost, is the algorithm is likely to give more than one such node N, there will be a chain reaction flooding the network wasting capacity: robust algorithm giving 1 in almost all situations
  
• algorithm is distributed and has to arrive at consensus
• has to have little overhead

Proposed solution

• collect packets together into a batch
  
• each node maintains a routing table which has path length (metrix e.g. ETX) from neighbors to destination
• a node uses the table to determine and prioritize (by closeness to destination) a list of forwarders (small to keep cost to arrive at agreement low)
  
• the highest-priority forwarder will broadcast all packets in the batch it received correctly, it will include the list of these packets as "batch map"
• the next forwarders will send packets which were not acknowledged through the "batch map" of higher priority nodes
• traditional routing as fall back mechanism for remaining 10% of packets
  
• scheduler so that only one node sends a time
• link state protcol to give input on forwarder list algorithm
• implemented in Click toolkit
  

Results

• end-to-end throughput boosted by around 2 (even higher for multi-hop routes)
  
• but bad TCP performance (fixed by split connection)

Criticism

• algorithmic overhead
• promicious mode: extra energy?
• there is no use on allowing only one station to send if the stations are so far apart that no middle man can hear both stations, scheduler should take this into accoung