$Id$
Messages
  Link State Updates (HSLS)
  ETX Beacons (ETX)
  Hello (HSLS)

We should be able to use LSU's as our Hello's and ETX beacons. We gain
efficiency by piggybacking this all together. There should be a
"subscription service" by which many different kinds of information
piggy back on the LSUs that HSLS sends out to take advantage of the
way HSLS messages propogate to the whole network in a scalable
manner. Other things that might piggy back on HSLS LSU messages
include name service and gateway advertisement.

ETX beacons only ever go one hop, so they won't piggy back on the
multi-hop HSLS LSUs.

We can't see any difference between an LSU and a Hello in the HSLS
protocol.
[ Note: I believe the Hello's referred to in the BBN reference
implementation where already there in the link layer, not
strictly part of their HSLS implmentation -bdc ]

Broadcast is less reliable than unicast in 802.11. How do we deal with
this in our design? Do we use broadcast or unicast for beacons? Do we
supplement ETX beacons with promscuous packet capture and other kernel
information to get additional information about adjacent nodes? 

  While these remain open questions, later conversation suggested that
  because Unicast is the way that "normal" data will be transmitted,
  it is the way that ETX data should be transmitted because that will
  give us the most relevent metric. For nodes that are clearly well
  linked to us though, for which broadcast and unicast would work
  equaly well, it seems pretty wasteful to use unicast. So perhaps we
  only unicast the beacon to those nodes for which we used to be
  adjacent but which we've started missing. 

  Similarly, it may be the wrong thing to do to include promiscuous
  mode data sniffing in our adjacency calculation because if we can't
  get actual ETX beacons through to them or receive them from them
  then even though we can see that they are there by other means,
  maybe they shouldn't get a good metric.

ETX might subscribe to multiple beacon services such as HSLS, 802.11b
beacons, or private ETX-only beacons (if we want to beacon more often
than te HSLS one hop LSUs).

The ETX module will implement both an HSLS beacon tranceiver 
and a direct IP beacon tranceiver.

State machine for ETX in a given node A, transitions happen on ticks
(though in reality we won't busy wait, we'll wait for data to be
available to us and then check the clock to see how many ticks have
passed):

    +---------+                +-------+
--->|         |                |       |--recv(N)--+ tick++,
    | Unknown |---recv(N)----->| Known |           | n.rx++
 +->|         |     tick++,    |       |<----------+
 |  +---------+     n.rx++     +-------+
 |          |                   |     ^
 +-!recv(N)-+      tick++       |     |       tick++,             
                 activate  !recv(N)  recv(N)  n.rx++,
              supplements       |     |       deactivate supplements
                                v     |
                               +---------+   
                               |         |
                               | Missing |
                               |         |
                               +---------+

 For each other node N we have a separate state machine. 

 N's state starts out as "unknown" (the node isn't known to A).

 if we've received a ETX beacon from N then increase rx and go to the
 known state.

 if a tick passes and we've not received a beacon then go to the
 missing state (unless in the unknown state).

 the missing state may activate the promiscuous and kernel supplements
 if we use those.

 every M ticks recompute link weight

The beacon message contains a sequence number and a list of nodes that
N has received beacons from since the last beacon sent by N. For every
node there is a m-bitfield with the first element representing a
beacon sent to N this interval, the second element represents a beacon
sent to N last interval, etc.

tx = [0,1] running average of beacons N received from us.

                                      1
link weight  =               --------------------
                                1           1
                               ---    +    ---
                               rx          tx


rx_new = .5 * rx_old  + .5 * rx_this-interval

(This one needs some serious thinking and work)
tx_new = .5 * tx_old + sum[1..(seq_new-seq_old)](.5^i * bitmap[i])

if we miss then tx doesn't change.

ETX Message Format

  IP (v4 or v6) Protocol encapsulated. 

An ETX Message contains an ETX header followed by any number of
ETX peer blocks.  The ETX header format is:
  version - 8 bis
  flags - 8 bits (bit 0 = ETX_F_INIT)
  seq no - 12 bits
  beacon interval - 4 bits 
  time expected to return, present only if ETX_F_BYE flag is set - 32 bits
The format of an ETX peer block is:
    IPv6 addr - 128 bits
    bitfield - 16 bits
    signal - 8 bits
    noise - 8 bits
    extensions used bitmask - 16 bits
    length of extensions block
    ETX extensions block

  If we are using ETX with v4 we just embed the v4 address into the
  appropriate v6 space rather than having different implementations
  for 4 and 6.

  the INIT flag is used to detect wraparounds vs. reboots. If seqno is
  less than the width of the bit field and INIT is on then we assume
  that we just started counting because the node rebooted, if seqno is
  low but INIT is off then we assume we just wrapped around from the
  max value of seqno.

What happens if intervals are different? 

Side Note:
  
 Packet Error Rate = k_1 * ( Bit Error Rate) ^ (k_2 * length)

 If we send beacons of two sizes and get error rates we can solve for
 the two constants above.

Security Note: Can people use the init bit to falsify their data?
Dropping duplicate seqnos and dropping over-frequent init beacons will help. 
What about nodes that lie about their link quality?
We could occasionally not send to them and flag them as liars if they
say they received somehting that we didn't send.

Note: What do we do about late beacons? How late? 

$Id$