Subject: TBRPF clarifications

From: Richard <[email-masked]>
Date: Tue, 21 Aug 2001 11:18:30 -0700

I would like to clarify some things about TBRPF, since some statements 
made at the IETF meeting in London might give some people an incorrect 
view of TBRPF-PT. (This is partly because the proposed draft update was 
not posted until a few days before the meeting.)  The presentation
slides can be found at http://tbrpf.erg.sri.com

First, there was a comment that TBRPF-PT is looking more like OLSR.
One reason is that the proposed update states that MPRs are used.
(Recall that at the March IETF meeting, Thomas Clausen presented
a slide that stated the possibility of adding MPRs to TBRPF, and 
of adding some feature of TBRPF to OLSR, so this modification 
is in line with the goals of the proactive team.)
However, TBRPF-PT does not use MPRs the same way as OLSR, and thus 
we probably shouldn't call them MPRs.  TBRPF always used "parents", 
which are similar to MPRs, and we can continue to call these "parents" 
and not "MPRs".  More specifically, MPRs (as defined in OLSR) have 
the following two properties:

  1. MPRs are selected by the MPR source (called MPR selector in OLSR). 
     In TBRPF they are NOT selected by the MPR source. (We allowed this 
     as an option, but will remove it until we conduct simulations to 
     determine whether it improves performance.)

  2. MPRs forward update messages received from the MPR source.
     In TBRPF-PT, NO update packets are forwarded by any node.
     (TREE UPDATEs are broadcast only to neighbors.)

Another new feature of TBRPF-PT is that it uses periodic updates in 
addition to differential updates.  However, periodic updates are 
certainly not unique to OLSR, and OLSR does NOT use differential 
updates.  Since DSDV uses both differential and periodic updates, 
TBRPF's method for reporting updates is actually closer to DSDV than 
to OLSR.  Periodic updates were added to simplify TBRPF-PT, e.g., 
to avoid the need for NACKs and retransmissions. 

There are several major differences between TBRPF and OLSR, and there 
are reasons for these differences, i.e., our intention is that these 
differences will improve performance, although simulations are needed 
to verify this.  Here is a list of some of the differences:

  1. As discussed above, TBRPF-PT does not use MPRs as defined in OLSR.
     Instead, TBRPF uses NEW PARENT messages to select "parents".  
     (We hope that this will provide faster response to failures.)

  2. TBRPF-PT uses differential updates and OLSR does not. (These allow
     important updates to propagate quickly in small messages to all 
     nodes affected by the update.)

  3. OLSR uses update sequence numbers and TBRPF-PT does not. (This is
     mainly because TBRPF-PT uses TREE UPDATEs, which are broadcast
     only to neighbors.)

  4. In TBRPF-PT each node reports only links in the reportable part of 
     its source tree, which is a subset of the links reported in OLSR.

  5. In OLSR, MPRs forward TC messages, while TBRPF does not forward any 
     control messages.

  6. TBRPF neighbor discovery (TND) uses differential HELLOs while OLSR 
     uses full HELLOs.  (This results in smaller HELLOs.)

Another issue that came up at the meeting is whether TBRPF can be 
"merged" with OLSR, despite the above differences.  That issue was 
not resolved at the meeting, but is being looked at now. I will give 
my own thoughts on this.  

One way to "merge" them is to simply replace item 1 above with 
"TBRPF uses MPRs", which we already know how to do.  Another way is to 
incorporate TND (item 6) into OLSR; I know this is possible and am 
working on an interface to do this.  Other possible ways involve the 
incorporation of one or more of the items 2-5 into OLSR. Simulations are 
needed to determine whether any such merging will improve performance, 
and to compare the performance of the two protocols.  We therefore plan
to conduct ns-2 simulations very soon.

Regards,
Richard Ogier

P.S. Since Joe brought up the issue of hysteresis and HELLO sequence 
numbers for OLSR, I will comment on the use of hysteresis in TBRPF 
neighbor discovery (TND). We had never discussed hysteresis with INRIA, 
so apparently both teams came to the same conclusion from experiments 
that hysteresis is needed.  (Of course this is not a new idea; it was 
considered in the 1980s in the SURAN program.)  

In TND, the HELLO sequence number is used to determine whether two of 
the last NBR_HOLD_COUNT (default = 3) consecutive HELLOs were received
from a given neighbor, necessary for declaring the neighbor 1-WAY or
2-WAY; and to determine whether NBR_HOLD_COUNT consecutive HELLOs were 
missed, which results in declaring the neighbor LOST.  (A neighbor is 
also declared LOST if no HELLO is heard within NBR_HOLD_TIME seconds.)

Thus, TBRPF also uses hysteresis for neighbor sensing, although it uses 
a simpler method than OLSR.  We also considered using an exponentially 
decayed count of received HELLOs (similar to OLSR), but we found rules 
such as "2 of the last 3 HELLOs must be received" to be adequate.
Our experiments showed that more than one HELLO should be received
before accepting a new neighbor, and we decided that waiting for more 
than 2 HELLOs would incur too much delay.

Our TBRPF implementation team (including Fred Templin, Bhargav Bellur,
Mark Lewis, and others) has also used signal strength measurements
to provide hysteresis, although we have not yet included this
in the TBRPF draft.  The following paragraph is from Fred:

  For some time, we have been using IEEE 802.11 RSSI (Rx Signal 
  Strength Indicator) measurements for neighbor discovery messages under 
  our field implementation of TBRPF-FT to provide hysteresis for link 
  stability.  This method allows us to detect and expire marginal links with 
  existing neighbors whose RSSI measurements fall below a low watermark 
  threshold as well as avoid forming links with new neighbors until their 
  RSSI measurements rise above a high watermark. We also avoid unnecessary 
  overhead by measuring RSSI only for neighbor discovery messages; not 
  for other protocol and/or data messages. In recent experiments, we have 
  included link state metrics based on the RSSI measurements in TBRPF-FT 
  protocol messages for QoS routing.

---

From: Joe Macker <[email-masked]>
Date: Tue, 21 Aug 2001 18:58:38 -0400

Richard:

Just a few comments. Thanks for providing your thoughts.

>considered in the 1980s in the SURAN program.)

Right, hysteresis is nothing new, basically a fundamental control theory 
technique that has been applied for decades (centuries?) in sensing and 
machine control problems.  It may also not be known that other manet 
participants not mentioned have experimented with it at some level (e.g., 
AODV ns2 code also has some options for it).  There are many ways to 
implement hysteresis so its still worth a little discussion.

>such as "2 of the last 3 HELLOs must be received" to be adequate.

To be fair to other OLSR implementors (there may have been some confusion 
caused in discussions of hysteresis work and application), while I and Ron 
Lee added an EWMA-based Hello hysteresis and packet jitter functions to 
Anis's OLSR Linux code (still not in the INRIA released version), I have 
heard that other OLSR implementations have taken a simpler counting 
approach for hysteresis as you mention (Clausen has mentioned taken the 
simpler approach in his experiments to me in the past).  IMHO, EWMA is also 
simple, but the other approach is potentially fine and may indeed have 
lower delay as mentioned. It was just our opinion that EWMA smoothes out 
the case of bursty losses better.  Perhaps not that important, but perhaps 
so.  I don't believe the newer OLSR spec dictates an approach and people 
have done at least 3 ways with OLSR  that I know of (IP layer Hello EWMA, 
IP layer Hello  windowed threshold, Lower layer single strength 
feedback).  At this point, we all know its important to do something and we 
have simulation models and real life code to begin gaining more experience 
with.

>   protocol messages for QoS routing.

I think we would all like to optional use RSSI techniques if an open source 
interface approach were available for all card drivers.  Such lower layer 
interface issues were discussed frequently at early manet meeting (I don't 
remember if you were as involved at that point), but people also felt there 
was no well-adopted interface means of getting that feedback on all cards 
and systems at the present time.  The consensus seemed to be we should 
develop IP layer approaches that can stand alone (reasonable device 
independence), but that can also take advantage of lower layer enhancements 
when better understood and available.

In addition, addressing the RSSI proposed use on periodic messaging there 
are likely still issues to consider such as urban environment fading 
channels,etc giving periodic poor indicators when relying on only 
"infrequent" signal strength sampling events as proposed..  Many of my ns2 
experiments have been done with ricean/rayleigh models applied and you 
definitely get some different robustness results so I think its good to be 
looking at that case as well.  I think its a good idea to be looking at 
this, but more experience will tell the whole story here on how to 
effectively apply it.  Thanks for your thought provoking post.

---

From: Richard <[email-masked]>
Date: Tue, 21 Aug 2001 21:08:10 -0700

Joe,

I agree that both methods (EWMA and Hello windowed threshold) are very 
simple, so I probably should not have said that one method is simpler 
than the other.  (One is just easier for a non-technical person to 
understand.)  I also agree that it is not clear that either method 
is significantly better than the other.

One of the issues in using hysteresis for neighbor discovery is 
the cost of declaring a link "up" when that link will soon be 
declared "down".  The cost of doing this depends on the routing 
protocol. For example, in TBRPF-PT, the cost is small because such 
a link is not likely to be used for forwarding data packets, and is 
not likely to be reported to nodes more than one hop away (assuming 
the network is dense so that the new link is not likely to provide 
a shorter path between any two nodes other than the endpoints of the 
new link).  This is because of the use of NON_TREE_PENALTY, which 
penalizes the addition of links to the source tree that are not already 
in the source tree.  Perhaps this property could be introduced into 
OLSR by penalizing, in the selection of MPRs, neighbors that are not 
already MPRs, or neighbors that have only recently become neighbors 
and are therefore not yet considered stable.  We are currently 
investigating the use of stability and link-quality metrics in TBRPF.

Richard

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 22 Aug 2001 11:27:27 +0200

Dear Richard,

A link subject to hysteris is likely to be at range limit and to impact
shortest path detection (reactively or proactively). EWMA proposed by Joe
team is interesting because it allows to fine tuning of link control and it
naturally adapts to faster hello transmission. However our experiments show
that link control via S/N level is more reliable but it requires an access
to this information via a non-standard way.

Philippe

---

From: "Philippe Jacquet" <[email-masked]>
Date: Wed, 22 Aug 2001 12:15:19 +0200

Dear Richard,

I am now fairly lost. In a previous mail I asked you whether your MPRs were
the same as in OLSR, i.e. they cover the whole two hop neighbor set. Your
answer was yes. Did you modify that property meanwhile? I understand that
TBRPF-PT MPRs do not need to relay multihop control message since TBRPF, as
far I have understood it, don't have multihop control message. However
multihop message may be useful for gateway announcement, DHCP, etc.

Philippe

---

From: Richard <[email-masked]>
Date: Wed, 22 Aug 2001 08:14:44 -0700

Philippe,

Parents also cover the whole two-hop neighborhood,
i.e., the parents p(u) of all 2-hop neighbors of node u.
Since TBRPF always used parents, I am focusing on
properties of MPRs (as defined in OLSR) that are not
shared by parents. I agree that certain control messages
should be broadcast via parents or MPRs, but this is just
reverse-path forwarding which has always been done using
parents (e.g., DVMRP).  An important difference between parents
and MPRs is that parents are selected by the children while MPRs
are selected by the MPR source (called "MPR selector" in OLSR).

In my previous email with you, we were discussing the proposed
update to TBRPF-PT using MPRs (in which MPRs are selected by the
MPR source as in OLSR).  That is not the method we are now using
for TBRPF-PT.  (We have reasons for not using that method, but
I won't go into that now.)

Richard

---

From: Richard <[email-masked]>
Date: Wed, 22 Aug 2001 09:55:15 -0700

Philippe,

I agree that a marginal link is likely to be at range limit and 
is therefore likely to result in a shorter path (while a longer 
path with good quality links would be preferred).  On the other
hand, the marginal link might provide the *only* path to some
node, which is better than no path.  Therefore, it might be
better to establish the marginal link, but give it a large
cost/penalty (e.g., based on EWMA) so that it is used only if 
necessary to reach some node.  (As I said, we are currently
investigating the use of such link metrics in TBRPF.)

Regarding my earlier email to you, I would like to clarify that we 
are not ruling out the possibility of using MPRs (where MPRs are 
selected by the MPR source as in OLSR) in a future version of TBRPF,
or in a "merged" protocol.  But simulations are first needed to
determine whether such an approach would improve performance.

Richard

---

From: Richard <[email-masked]>
Date: Thu, 23 Aug 2001 08:35:07 -0700

Philippe,

I would like to add one more thought.
Your statement "A link subject to hysteresis is likely to be
at range limit and to impact shortest path detection"
assumes that all radios have about the same transmission power
and that the terrain is flat with no obstacles.
For example, a link at range limit to a low-power radio is less 
likely to affect shortest path detection (i.e., to provide a shorter 
path to other nodes).  This is also the case for a link that is at 
range limit due to some obstacle (e.g., building) between the nodes.

It would be good to include such obstacles in simulations.
The ns-2 simulations I have seen seem to assume a flat
terrain with no obstacles, which I think is too optimistic.

Richard

---

From: "Philippe Jacquet" <[email-masked]>
Date: Thu, 23 Aug 2001 18:34:26 +0200

Or at least an ns2 model with random and variable fading should suffice to
model random obstacles. Does anybody have information about such radio model
in ns2? We already made some simulations with random fading but it was not
in ns2.

Philippe

---

From: Joe Macker <[email-masked]>
Date: Thu, 23 Aug 2001 18:08:22 -0400

>in ns2? We already made some simulations with random fading but it was not

Yes, there are ricean/rayleigh fading models developed for ns2 that one can 
install. I have used them and they seem to work.  Also, the original cmu 
work had an ability (or at least planned ability) to model obstacles but I 
don't remember how far this was taken.  I think ad-hockey had a graphical 
obstacle tool in it?

-Joe