Topic: Routing in wireless and overlay networks
jinyang@cs.nyu.edu

Goal of routing:
- node discovery (find a path)
- find a GOOD path to destination node
- low message overhead and deal with changes promptly -> less per-node routing state?

Most common wireless deployment: wired APs connect wireless nodes to the Internet 
  --> No routing over wireless links needed!

Why routing over wireless? 
We don't want to wire every AP! More flexible, cheaper, quicker deployment
* Increase a single AP's coverage without putting down more wires for another AP.
* Urban mesh of wireless routers that connect nodes to a few wired Internet gateways.
* A network of wireless sensor nodes that collect data and monitor the environment.

Why traditional Distance-Vector and Link-State not sufficient? or What's
different in wireless that requires us to design new routing protocols?)
* Much more frequent link/node changes. 
   - Link qualities change
   - Links emerge or disappear due to interference or node movements 
* Links are crappy 
   - lossy 
   - asymmetric
* Links are plentiful w/ lots of local redundancy w/ geographical hints

Paper I: ETX

What is a good path?
- good end-to-end performance
  * low latency 
  * high throughput 
  * low loss (?)
- minimal consumption of (global) resources 
- policy conforming

Throughput of a wireless path is affected by:
- various levels of loss (in contrast, wired links either work or don't)
  but MAC retransmits at least 7 times, so loss shows up as throughput reduction
  1 hop path with 60% loss has lower throughput than 2 hop path with 1% link loss rate.
- links are asymmetric (forward and reverse loss rates are different)
  (Both directions are important, because ACKs travel in the reverse direction)
- successive hops interfere (2 hop routes achieves 50% throughput of one hop route)
  (Explain why that is the case)

Why doesn't shortest path work well?

Strawman alternatives, why don't they work?
- only use links with very low loss by setting a threshold
  Problem: threshold too high, network becomes disconnected
           1 hop with 40% loss is better than 2 hop with 10% loss.
- Minimize end to end loss rate
  Problem: successive hops interfere.
- end to end delay? (high loss ==> high delay per hop)
  Problem: but queuing ==> high delay too! So end to end delay is 
  sensitive to network load. Routes will oscillate with load.
 
The ETX metric
- What it is:
  1/d_f*d_r
- Why does it take care of the 3 factors?
- Is ETX load sensitive?
  To a first approximation, no.
  In contrast, delay is a load sensitive metric

Obtaining a link's ETX metric:
- explicit periodic probing.
  why not passively measure?
- preferentially send ETX probe than data

Incorporating ETX in routing protocols:
DSDV:
at each node:
handle_update(Route r, Node nbr)
{
  update_metric //spf: r.metric++
                //etx: r.metric += etx[nbr]
  if (r.seq == curr[r.dest].seq && r.metric < curr[r.dest].metric) {
      //heard a route with same freshness but better metric
      schedule_trigger_update
      //record when the better metric was heard
      curr[r.dest].best_time = now;
  }else if (r.seq >  curr[r.dest].seq) {
     //update the weighted settling time with the settling time of the old route with seq curr[r.dest].seq
     ...

     curr[r.dest] = r; 

     curr[r.dest].first_time = curr[r.dest].best_time = now;
     schedule_trigger_update
  }
}

lookup_route(dest)
{
  //dsdv
  return curr[dest]

  if (curr[dest].first_time+2*wst > now)
    return curr[dest]
  else
    return old[dest]  
}

DSR:
original: Flood with TTL
now: flood with ETX metric
Changes: original: nodes forward each flooded mesg at most once.
nodes forward flooded msg again if it has a better ETX.

Graphs:

ETX Assumptions on the radio:
* one channel
* transmit power is fixed


Discussions:
* Does ETX always use lower loss links than shortest path? Example.
* Why don't the authors explicitly try to minimize end-to-end loss? e.g. minimize sum_l( log(loss_l))
In other words, does ETX always prefer links with low loss? Example?
* If you are to design a network in which each node is equipped with multiple radios that operate on 
  multiple orthogonal (non-interfering) channels, do you still want to use ETX? why and why not?


Paper II: Geographic routing

Goal: find a (reasonably short) path to the destination node w/ low message overhead
Assumptions: Each node knows its geographic location.  Route packets to a destination location.

Strawman: forward packets to the neighbor geographically closest to the destination
Highly efficient because:
- only local state is needed 
(i.e. a node only needs to learn about its neighbors to make forwarding decision)
- geographic location efficiently aggregates routing information
(allows a node to efficiently distinguish neighbors that make forwarding progress to the 
 destination from those that don't. 
 In contrast, traditional routing tables contain only one single next hop choice per destination.)

Greedy routing cannot get out of "void" (local maxima)
An example of void.

How to traverse along the perimeter of the "void"?
- right hand rule
- why crossing edges are bad.
  An example.
- Solution: planarization

Discussion of assumptions of GPSR
- Are wireless networks truly unit graphs?
  * 
- What about link qualities?