[Ndn-interest] Network inconsistency and NLSR sequence numbers
David R. Oran
daveoran at orandom.net
Tue Aug 27 10:12:12 PDT 2019
On 27 Aug 2019, at 0:52, Viktor S. Wold Eide wrote:
> On Mon, Aug 26, 2019 at 5:52 PM WENTAO SHANG <wentaoshang at ucla.edu>
>> 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
>>> dynamic environments. Are there any implementations for Ndn which
>>> 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
Any reasonable link state protocol has no problem with nodes coming and
going, or new nodes being introduced (modulo having the right keying
material to sign their updates, and being included in the network’s
While modeling link state routing as a distributed database with
eventual consistency (or as an append-only log-based CRDT) might have
had some intellectual appeal, there seems to be accumulating evidence
that this approach has neither the responsiveness nor the robustness one
would like from a routing protocol.
There is one area where NDN/CCNx needs semantics a bit different from
the Link State protocols currently used for IP. Since IP uses asymmetric
routing/forwarding, it’s perfectly ok for links to work in one
direction but not in the reverse direction. NDN, on the other hand,
requires symmetric routing, and hence either individual links, or
parallel links between node pairs used as a link bundle need to operate
in both directions. Sone link state protocols (e.g. OSPF) did not bother
to check this since the asymmetry would not break IP. ISIS did in fact
have symmetry checking where it did not enter a link into the topology
unless both/all routers on the link reported it in LSPs. Most people
running the protocol turned this off, but the capability is still there
in the design.
Another thing in some link state protocols is the ability to ensure that
links asserted to be broadcast media in fact have transitive closure of
connectivity. This is crucial if one wants to use multicast/broadcast
for control protocols like flooding or consensus. In the early days of
Ethernet that had physical bus topologies, transitive connectivity
failures were not at all uncommon. These became fairly rare when people
moved to switched topologies and ran the ethernet link protocol only
point-to-point. However, this concern is back again with WiFi or mesh
since hidden nodes often break transitive closure. This is one of the
reasons a link state protocol (at least one without this feature) may
not be a good match for such environments.
I bring this last point up because I frankly disagree with the assertion
that link state can’t deal with dynamic environments. Especially when
you consider the more recent fast reroute extensions, they can respond
and converge after topology changes in 100ms or less. Where this
doesn’t help is with mesh wireless where you don’t have enough
bandwidth to sustain the high flooding rate such responsiveness demands.
>>> 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
>>> 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
> I do not quite get the reasoning here.
Nor I, frankly.
> 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
Well, it’s kind of nice for forensics, but not for anything else I can
> 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 obviously agree with this.
>> 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.
Yes, and I’ll once again point out that we are now in a state where
civilization would pretty much collapse without them, since so many
things already depend on clocks provided by GPS and other sources.
Having NDN depend on loose clock synchronization seems pretty minor by
> Best regards
> Viktor S. Wold Eide
More information about the Ndn-interest