[Ndn-interest] Network inconsistency and NLSR sequence numbers

[Ashlesh Gawande (agawande)]

Just one sequencing file is used to store three separate numbers now (including 0.5.0 release that is under test here).

This is a known design issue from "A Secure Link State Routing Protocol for NDN<https://named-data.net/wp-content/uploads/2018/05/secure_link_state_routing_protocol_ndn.pdf>" paper:

"Another problem is that the sequence number file where NLSR records its LSA version numbers can become corrupted during operation or during reboot, which can cause a router to inject LSAs with older version numbers than the ones already distributed. In this case, the new LSAs will be discarded by other routers, so this router cannot become part of the topology. It is our ongoing work to address this problem."

ChronoSync/PSync (NLSR can switch b/w either as of 0.5.0) does not remove old data from sync but that is a separate problem (some discussion here about adding timestamp to LSAs: https://redmine.named-data.net/issues/3593). Because even if sync did remove obsolete data by some mechanism, NLSR still holds onto the sequence number information (but maybe then NLSR could also let go of old data after notification of removal from sync).

Ashlesh
________________________________
From: Ndn-interest <ndn-interest-bounces at lists.cs.ucla.edu> on behalf of David R. Oran <daveoran at orandom.net>
Sent: Thursday, August 22, 2019 10:18 AM
To: Viktor S. Wold Eide <viktor.s.wold.eide at gmail.com>
Cc: ndn-interest <ndn-interest at lists.cs.ucla.edu>
Subject: Re: [Ndn-interest] Network inconsistency and NLSR sequence numbers

This sounds like a CLASSIC link state algorithm design bug. I’m
frankly pretty surprised the NLSR team didn’t learn from correct link
state protocols like ISIS.

Maybe it’s because of inappropriate reliance on Chronosync rather than
doing a bespoke flooding protocol?

In addition to sequence numbers, you need an AGE field to time out old
LSPs and something like CSNPs to recover state faster than the age
timeout.

I’d be interested in whether this is just some code bug and things are
actually properly designed.

(BTW: modulo sequence spaces are neither necessary nor desirable for
link stat protocols - again look at ISIS which uses a simple linear
space, avoiding classic bugs like the old Arpanet “Christmas”
problem.)

On 22 Aug 2019, at 7:24, Viktor S. Wold Eide via Ndn-interest wrote:

> Hi Junxiao,
>
> Thanks a lot for the quick reply.
>
> Having to backup sequence numbers sounds like a flaw in the protocol
> design, but I guess there are some reasons for the choices?
>
> Regarding your suggestion using a random UUID, let's hope some of the
> NLSR developers can share their viewpoint?
>
> Regarding your suggestion that a node might query the network / other
> nodes about it's own sequence number. I understand that it might fix
> the problem for some cases, but I expect that this will lead to other
> and more severe problems and errors. What if other nodes do not agree
> and answer with different numbers? It seems the problem quickly gets
> worse.
>
> Could this be fixed using a sliding window approach for sequence
> numbers? That is, if and when a node experiences segment numbers
> outside some valid window (to far behind or to far ahead for node X)
> this is interpreted as a need to re-synchronize / accept a new
> sequence number window for node X? Or will this approach not work? If
> not, what are the issues?
>
>> From looking very quickly at the nlsr source code, it appears that
> sequence numbers are uint32_t, at least in some places (lsa.hpp),
> while uint64_t in other places (lsdb.cpp). If 32-bit, or if starting
> at a random number, some wrap-around handling appears necessary
> anyway?
>
> As written initially, I would expect that nodes must forget / delete /
> reset knowledge of other nodes in some cases, and at least after some
> time. Is this the case, or will a node be remembered forever,
> potentially?
>
> Best regards
> Viktor S. Wold Eide
> _______________________________________________
> Ndn-interest mailing list
> Ndn-interest at lists.cs.ucla.edu
> http://www.lists.cs.ucla.edu/mailman/listinfo/ndn-interest

DaveO
_______________________________________________
Ndn-interest mailing list
Ndn-interest at lists.cs.ucla.edu
http://www.lists.cs.ucla.edu/mailman/listinfo/ndn-interest
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndn-interest/attachments/20190822/78ae027f/attachment-0001.html>