[net2-wg] Distilling

[Rodrigo Fonseca]

Hi,

the alpha testing we're doing has raised a number of issues, many of
which we have discussed. Here's a discussion on the most prominent
ones, followed by what we should do now and in the near future.

A. Loops:

if the topology allows loops and they are not handled, they are
obviously bad: packets will essentially loop forever.
We talked about this issue, and the solution is two-fold:
    1. Make sure the topology does not have loops: this is done by
using DSDV-like sequence numbers from the roots.
    2. Handling them properly at forwarding time:
        2.1 using unique ids for messages (origin node + sequence
number imposed at send-time) and detecting repeated messages. Have to
differentiate between retransmissions from the previous node --- which
should be dropped --- and packets that loop. The way to do this is to
add a ttl, and record for each message forwarded the unique id and
ttl.
       2.2 just use a ttl for the message, and drop it if it is
extinguished. This last one bounds the damage, but does not help in
delivering the packet.
      Obs: for 2.1 to be useful, there needs to be a mechanism to
forcibly select another route

B. Alternate Routes:
   We talked about this in the 5/18 meeting. The forwarding engine
should be able to request another route from the routing engine. Two
ways to do this:
    1. getNextHops interface. The routing engine gives an ordered list
of possible next hops, and the forwarding engine can make use of this
for retransmission and for loop handling.
    2. getNextHop(i): the forwarding engine asks for the i-th best
next hop for this. Note that this is slightly different from saying
this is the 5th time I forward this. It says: give me the 5th
candidate. This way the policy stays within the forwarding engine, and
the mechanism within the routing engine.
    I think 2 is probably more flexible and less cumbersome.

C. Link Estimator and Forwarding:
     Then there is the question of the Forwarding Engine telling the
link estimator about the number of retransmissions required to send to
a destination. This is a direct measurement of the ETX! It would be
great to integrate this into the Link Estimator computations, and this
would in turn improve the route selection. This mechanism is
orthogonal to B. B is an immediate repair action for THIS packet, C is
longer term (probably for future packets)

D. Dropping Packets and Reliability
   Of course dropping packets is not what we want. it's bad, it wastes
all that energy invested in the packet so far, etc. The question is
where we want to stand in the best-effort <-> all-effort line. We need
a backpressure mechanism working to prevent queues overflowing. We
need the alternate routes mechanism working to try other nodes.
But it is also good to bound the amount of effort that will be
invested in any one packet.

  Some measures are required end-to-end to achieve 100% reliability,
like end-to-end acks, network level rate control, and possibly FEC.
These are normally transport issues.

-----------------------------------------------------
So, the question remains of what to do for the beta release, should we
fix all these? Should we deliver some version and keep working on
these? Some of them require a bit of design and testing, so I think we
should decide on a set of things to be in the beta release, release it
with caveats, and keep doing the others.

The main features needed so far are the following. I marked with one *
what should be done now, and with 2 starts ** what I think could go
onto beta 2.

TreeRouting:
   * replacement policy for links
   * getNextHop(i) call
   ** DSDV-like sequence numbers to prevent loops
ForwardingEngine:
   * retransmission timing: ?
   ** mechanism for uniquely identifying messages
   * ttl (or hopcount so far)
   * mechanism for dealing with loops
      * ttl-based only for B1
      ** unique_id + alternate route for B2
   * asking for alternate routes
      * for retransmissions
      ** for loops detected
   ** reporting to the LE about number of retransmissions per packet
   ** backpressure mechanism (ECN bit?)
LinkEstimator:
   ** integrating retransmissions per packet information in estimates

What do people think? Feel free to shift stars around, to add or drop
items to or from the list.

Rodrigo