[Ndn-interest] Network inconsistency and NLSR sequence numbers

[David R. Oran]

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> 
> 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.
>
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 
trust schema.

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.

(TL;DR warning)
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 
>>> 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.
>
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
> desirable.
>
Well, it’s kind of nice for forensics, but not for anything else I can 
think of.

> 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 
comparison.

>
> Best regards
> Viktor S. Wold Eide

DaveO