Subject: Re: Re: neighbor sensing in TBRPF

From: [email-masked]
Date: Thu, 10 Aug 2000 05:33:51 -0400

Richard <[email-masked]> wrote:
> 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.

Richard,

I think this is true only to the extent that you trust your internal DB entries to accurately reflect your neighbors' entries.  In practice, this is sometimes not true (transmission/memories errors...etc) and additional mechanism/overhead would likely be required within TBRPF (or similar approach) to safeguard against these problems in practice.

Have you addressed this issue in simulation or implementation as yet?

-scott

  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]

> 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
> 
> Institute for Systems Research
> University of Maryland, College Park
>

---

From: Richard <[email-masked]>
Date: Thu, 10 Aug 2000 21:17:11 -0700

> I think this is true only to the extent that you trust your internal DB entri
es to accurately reflect your neighbors' entries.  In practice, this is sometim
es not true (transmission/memories errors...etc) and additional mechanism/overh
ead would likely be required within TBRPF (or similar approach) to safeguard ag
ainst these problems in practice.
> Have you addressed this issue in simulation or implementation as yet?

Scott,

We plan to add a checksum to link-state updates to detect data 
corruption due to transmission/memory errors, as is done in OSPF.  
This will be incorported into our simulation and implementation soon.  
For example, a node receiving a link-state update whose checksum is 
incorrect will respond with a NACK (if the update was locally broadcast).

With the checksum, undetected errors will be very rare.  TBRPF allows 
the infrequent periodic broadcast of link states (e.g., once every 30 minutes) 
to correct these rare errors, as is done in OSPF.

The additional overhead of the checksum and NACKs or ACKs
should be much smaller than the overhead saved by not requiring
frequent periodic broadcast of link states (e.g., every 5 seconds).

Richard