[Ndn-interest] Network inconsistency and NLSR sequence numbers

WENTAO SHANG wentaoshang at ucla.edu
Thu Aug 22 08:58:37 PDT 2019

I sort of remember that when we were building ChronoChat on top of
ChronoSync we always append random strings to the user names to avoid
confusing the sync layer. This could also be applied to NLSR.

Essentially we need something to differentiate the old router instance from
the new. Under NDN design principle the "thing" that differentiates them
must be reflected in the name. It could be either random number or a
timestamp (assuming you can recover old timestamp when you reinstall the
router instance).


On Thu, Aug 22, 2019, 8:44 AM Ashlesh Gawande (agawande) <
agawande at memphis.edu> wrote:

> 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
> _______________________________________________
> 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/08a7d987/attachment.html>

More information about the Ndn-interest mailing list