[Ndn-interest] Network inconsistency and NLSR sequence numbers

WENTAO SHANG wentaoshang at ucla.edu
Wed Aug 28 20:03:14 PDT 2019

On Tue, Aug 27, 2019, 12:53 AM Viktor S. Wold Eide <
viktor.s.wold.eide at gmail.com> wrote:

> On Mon, Aug 26, 2019 at 5:52 PM WENTAO SHANG <wentaoshang at ucla.edu> wrote:
> >
> > On Mon, Aug 26, 2019, 2:19 AM Viktor S. Wold Eide <
> viktor.s.wold.eide at gmail.com> wrote:
> >>
> >> I certainly would like to also have routing that is more geared towards
> >> dynamic environments. Are there any implementations for Ndn which you
> >> would recommend that I try out?
> >
> >
> > We did some work before on running sync as a smart forwarding protocol
> in sensor networks but it's based on simulation. I don't know if we have
> any implementation that can be readily deployed on real devices...
> Then there seems to be no other options for routing in Ndn as of
> now. Hence, it seems even more important to have a routing
> implementation that works.
> I do not see any reasons why nlsr should not be able to handle well an
> environment where nodes are added and removed dynamically, as long as
> the frequency is low or modest. How well it would handle more high-
> frequent changes is of course interesting, but not the issue discussed
> here.
> >> Do you know of another way to get rid of information in nlsr/sync,
> >> that is, information from other nodes that are no longer connected to
> >> the Ndn network.
> >
> >
> > My understanding is that removing old data from sync is a separate
> problem and is optional for the routing protocol on top of sync.
> >
> > One way to look at sync is that it is essentially an append only log.
> Supporting append only log efficiently on persistent storage is a classic
> problem that has been well studied by database and file system researchers.
> There are many good ideas that we can borrow from there to improve our
> implementation of sync (e.g., Log-Structured Merge).
> >
> I do not quite get the reasoning here.
> The ability to forget / get rid of nodes not seen for a while seems
> like one of the most basic characteristics of a routing protocol, in
> order to correctly reflect the state of the network.
> A network which never forgets any node seen - I do not see how that is
> desirable.
> When choosing data structures for implementing nlsr, then there are
> some operations that must be supported. If sync does not support what
> a routing protocol needs, then sync is not the right choice or sync
> needs to be extended. Exposing the lack of required functionality from
> sync into the routing, here the inability to delete / remove nodes,
> can hardly be the right choice.

I agree that this is a problem in the current implementation. But at the
protocol design level, removing a router from a sync group does not
necessarily require stopping the world and garbage-collecting the sync data
repo on every single router. E.g., one can do something like publishing a
tombstone object to mark that some stale sync user is gone and will never
generate new sequence number. (I remember we experimented with some similar
ideas on either ChronoChat or NLSR.) In theory one can have a sync protocol
that never removes any data from its distributed data collection but still
allows applications running on top of it to remove logical entities. I
think these two are separate problems that can be (and should be) decoupled
from each other.


> > Folks who know more about implementation detail should chime in on this.
> But I think this is probably an optimization in the current implementation
> (with additional dependency on synchronized clock) for speeding up
> convergence.
> >
> Let's see if anyone with more knowledge chimes in. In my opinion a
> design which depends on synchronized clocks is a to strict and far
> reaching requirement, but that was/is a separate discussion.
> Best regards
> Viktor S. Wold Eide
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.lists.cs.ucla.edu/pipermail/ndn-interest/attachments/20190828/28d4cc6a/attachment.html>

More information about the Ndn-interest mailing list