Recall routing protocols from previous class

How to choose routes?
  greedy forwarding rule: "choose nbr closest to dst"
  neighbor means any node we've recently heard a HELLO message
  a node in a big net has many neighbors with varying S/Ns
  [[picture, shows shortest path choose worst links]]





Actual link loss rate?
  neighbors have varying quality? Yes. [[graph]]
  Delivery rate is not bi-modal, many intermediate quality links.







What is a good path? How does link quality impact path "goodness"?
- good end-to-end performance
  * high throughput 
    Using links with low delivery ratio causes more link re-transmission, 
	 hence reducing path throughput
  * low loss (?)
	 802.11 re-transmits lost packets up to 7 times, so a link 
	 with 50% broadcast packet loss does not cause 50% loss in unicast packets
  * low latency 
    loss causes re-transmission, thus increasing the latency to successfully 
	 transmit a unicast packets
- minimal consumption of (global) resources 

Let's choose routes to optimize for path throughput
  * lost packets are retransmitted, reducing throughput
  * asymmetric links lose acks, causing retransmission
  * throughput decreases w/ hop count

Let's predict throughput along a route
A-B-C-D (three 100% hops)
A-E-D via two 50% hops
throughput of 1st route? 1/3
throughput of 2nd route? 1/4 or 1/8 if ACKs are lost with 50%
Prefers the 2nd (and longer) path

A-D (40%), throughput 2/5

Three Strawman alternatives:
1. only use links with high delivery ratio by setting a threshold
  Problem: threshold too high, network becomes disconnected
           1 hop with 40% loss is better than 2 hop with 10% loss.
2. Minimize end to end loss rate
  Problem: successive hops interfere.
3. 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.
  Second order effects? hidden terminal collision, 
  In contrast, delay is a load sensitive metric

Obtaining a link's ETX metric:
- explicit periodic probing using broadcast packets.
  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.

ETX open questions:
* hops stop interfering when far apart, hard to predict
* loss rate differs for different pkt sizes, ACK vs DATA
* 802.11 backoff means bad links are slower than ETX imagines
* real radios have many possible tx bit rates / modulations
  maybe look at S/N and choose appropriate modulation?
 
  How do you design a metric to accomodate multiple different rates?


Paper II: EXOR

Traditional routing:
  graph abstraction
  measure all link qualities
  pick the best single path
  forward data along JUST that path

  Wireless is different:
  1. each transmission is heard by many receivers
  2. near ones hear most pkts, far ones hear some
     but far receivers are most valuable
	  [[example horizontal chain]]





  3. reception at different receivers not very correlated
     [[example vertical chain]]




  if you fix a route, it has to use relatively near nodes thus wasting far receptions
  similarly, may be able to re-send from better node than sender
  EXOR: why not have best actual receiver of each pkt forward it?

ExOR: 
* each pkt transmission is a broadcast
  any receiver is a potential forwarder
* decide who forwards AFTER reception
  However, receivers need to agree on who received the packet
     don't want more than one to forward!
  and on who is the best receiver to forward the packet
     i.e. "closest" to destination
  This agreement's overhead is big, so needs to batch over many packets

  sender includes a list of candidate forwarders
     [show data packet format]
  a fixed transmission schedule across all forwarders
     best candidate first
  after slots have gone by, all receivers know who got it
     cascaded ACKs to help ACKs from distant nodes
  Big improvements, mostly due to significant lucky long hops

Discussions:
* Fixed tx schedule
  one forwarder at a time (no spatial reuse)
  why not let multiple forwarders proceed? (collision? potential duplicate transmission?)
* ExOR does not interact well w/ TCP and real time traffic due to batching