Subject: neighbor sensing in TBRPF

From: Matthew Impett <[email-masked]>
Date: Tue, 8 Aug 2000 17:18:38 -0400 (EDT)

I have a general concern with the neighbor sensing mechanism as decribed
in the TBRPF draft. The neighbor setup process guarantees only
bidirectional links be setup, but seemingly does not guarantee that
bidirectional links which become unidirectional during their lifetime will
always be detected as so. Consider the following network setup:

  "Cloud of Nodes" <---> A <---> B <---> "Cloud of Nodes"

Where "Cloud of Nodes" is a portion of the network containing any number
of nodes.  In the picture above, some number of nodes in the left cloud
have bidirectional links to node A, node A has a bidirectional link to
node B, and node B has bidirectional links to some number of nodes in the
cloud on the right.

Now, if the link between node A and node B where to become unidirectional,
as follows:

  "Cloud of Nodes" <---> A ---> B <---> "Cloud of Nodes"

I believe that node B may never determine that the link has become
so. Node B will continue to hear HELLO packets from node A and will
therefore never declare the link down.  When node A determines that the
link has failed for node B (by setting his metric to infinity), that node
may broadcast updates which could inform B that A believes the metric for
that link is infinite (assuming A doesn't unicast those
updates).  However, if this packet is lost, B will have no
way of getting a NACK back to node A, and A will therefore never
retransmit the packet. In this situation, node B will continue to forward
data traffic toward node A for A and all the nodes in the left cloud.

Therefore, while the neighbor discovery process of TBRPF saves
considerable bandwidth compared to that of other protocols, such as OLSR 
and IMEP, the lack of continuously sending a neighbor list seems to lead
to instabilities.

Matthew Impett
<[email-masked]>
Institute for Systems Research
University of Maryland, College Park

---

From: Richard <[email-masked]>
Date: Wed, 09 Aug 2000 16:42:18 -0700

Dear Matthew Impett,

Thank you for your feedback on TBRPF. Someone at the MANET WG meeting 
last Thursday mentioned the same problem (Vincent Park I think).  
This problem does not occur if data packets are always acked at 
the link layer, since the absence of acks would indicate to 
node B that the link to A is down.  However, if data packets are not 
acked, then I believe your analysis is correct.

We have a fix for this problem, but I need to discuss it with
my co-workers before disclosing it.

However, I want to point out that, even if TBRPF used the standard neighbor 
discovery protocol that includes a list of known neighbors in each 
Hello message, it still has the following efficiency advantages:

  1. TBRPF does not require periodic broadcast of link states.

  2. TBRPF uses full spanning trees for broadcasting updates,
     to eliminate redundant messages (i.e., to avoid having 
     an update reach the same node via multiple paths).

With our fix for the neighbor discovery protocol, we still expect
to have the third advantage that Hello messages are smaller.

Richard Ogier
Sr. Research Engineer
SRI International
333 Ravenswood Ave.
Menlo Park, CA 94025
Tel: 650-859-4216
Fax: 650-859-4812
Email: [email-masked]