Subject: [Anima] Comments on draft-liu-anima-grasp-distribution-05

From: Brian E Carpenter <[email-masked]>
Date: Thu, 15 Mar 2018 15:33:07 +1300

Hi,

Since there were a lot of updates in this version, I read it again
from the beginning. Here are my comments.

In general I think this is useful work that the WG should consider
adopting. There is definitely a requirement for something in the
space between peer-to-peer synchronization and flooding to all
autonomic nodes. The fixed size of GRASP messages also limits
information distribution at present.

> 3.2 One-to-Many Communications
> 
>    Some information exchange involve an information source and multiple
>    receivers. This scenario can be divided into two situations:
> 
>       1) When some information are relevant to all or most of the nodes
>       in the domain, the node that firstly handle the information should
>       use a mechanism to propagate it to all the other nodes.
...
>       2) A more general case is that some information is only relevant
>       to a specific group of nodes belonging to the same sub-domain or
>       sharing the same interests.

It's probably worth mentioning that there is a tradeoff here. If some
information is relevant to 50% of nodes, it is probably cheapest to
simply flood it to all nodes. If it is relevant to only 5% of nodes,
it is probably cheapest to use a pub/sub model.

> 3.3 Requirements
...
>       3) Distributed Coordination....
...
>       Obviously, purely relying
>       on instant communication model is inefficient, while a scalable,
>       common, yet distributed data layer, on which AFs can store and
>       share information in an asynchronous way, should be a better
>       choice.

This is the most interesting case (I think of it as a whiteboard, where
any ASA can read, write or erase). Doesn't it also relate to distributed
consensus mechanisms? 

Can we consider the previous case (pub/sub) to be a subset of this case,
with only one node having write/erase capability?

> 5.1 GRASP for instant communications
...
>       o  Matching condition: "Device role=IPRAN_RSG"
> 
>       o  Matching objective: "Neighbors"
> 
>       o  Action: "Forward"
> 
>    This example means: only distributing the information to the
>    neighbors who are IPRAN_RSG. 

How does the node performing the distribution know which of
its neighbours have the role IPRAN_RSG? Is there a registration
process? Is it really any different than the subscribe process
in pub/sub? ("I subscribe to IPRAN_RSG information".)

>  5.2 GRASP for asynchronous communications

Once we have the previous point solved, we can model the
asynch distribution as a selective flood to the "whiteboard"
in each node.

Having said that, I want to look back in the draft at the Event Queue
described in section 4.2.1. I'm not sure that we need it as a separate
engine from the queues implied by GRASP's existing asynchronous
operations. If you model a producer or consumer as a process using
GRASP, it will naturally need to support simultaneous asynch operations
and an event queue.

I am wondering to what extent I can model this directly over GRASP as it
exists today. My main question is mentioned above: how does a node
know which of its neighbours have a given role?

(One possible answer is that *every* node sends out a local GRASP
flood at very low frequency, stating which roles it supports.
Then every node builds a cache of its neighbours' roles. I can
make that work with GRASP today.)

Regards
    Brian

---

From: Xun Xiao <[email-masked]>
Date: Thu, 22 Mar 2018 10:51:23 +0000

Dear Brian,

Thanks for your detailed review. To your comments, after discussing among all co-authors, we put inline reply below.

BR.

-Xun Xiao on behave of Artur, Zoran ang Bing

-----Original Message-----
From: Anima [mailto:[email-masked]] On Behalf Of Brian E Carpenter
Sent: Thursday, March 15, 2018 3:33 AM
To: Anima WG <[email-masked]>
Subject: [Anima] Comments on draft-liu-anima-grasp-distribution-05

Hi,

Since there were a lot of updates in this version, I read it again from the beginning. Here are my comments.

In general I think this is useful work that the WG should consider adopting. There is definitely a requirement for something in the space between peer-to-peer synchronization and flooding to all autonomic nodes. The fixed size of GRASP messages also limits information distribution at present.

[Xun, Artur, Zoran and Bing] We would appreciate, if this work could be adopted as a WG document. We also appreciate that we share the same view on the problem space.

[Xun, Artur, Zoran and Bing] Our main concern in this document is not just the (re-)statement of the requirement to reach (sub-)sets of nodes in an Autonomic Domain, but rather a suggestion of a model and a simple mechanism, allowing to do it efficiently at different scales and in networks of different topologies. In other words, while it would be an easy game to implement such a mechanism in a very small network (any viral propagation) or in a sparse network ("expanding circle", as an example), it is much harder to find a cheap and scalable solution for any network. We believe that "any" network matters, because ANIMA protocols can be seen as a "first" set of procedures to be executed. It means it must work, when one simply does not know yet, how the network looks like.

...
>       sharing the same interests.

It's probably worth mentioning that there is a tradeoff here. If some information is relevant to 50% of nodes, it is probably cheapest to simply flood it to all nodes. If it is relevant to only 5% of nodes, it is probably cheapest to use a pub/sub model.

[Xun, Artur, Zoran and Bing] We were motivated by the tradeoff when doing this work. A more rigorous way is to define a nice metric on this. It should reflect:
 - The size of the network or the volume of messages to be sent (or of data?)
 - The absolute number of nodes that want to receive it
 - Ultimately, it should also somehow reflect the speed of information propagation.
 - Cost of sending that many messages from any individual node?
NOTE that simply putting a percentage is not enough, as it might be still disastrous to epidemically flood messages in a very dense big network even to only 5% of nodes. Flooding is in general not the top option to disseminate information, even if you need to send info to all nodes (and not 'only' 50% of them), let alone when it is only a small fraction of the network. The thing is that flooding will send many duplicate messages and as such uses nodes' communication capabilities in a pretty inefficient way. Simply, flooding will send data along each link. It is always better to setup a structure that we can use for dissemination. With this structure, that our pub/sub in fact represents, we send in total one message per node, which is much better. So our pub/sub should be seen as a systematic way to disseminate info, rather than an efficient realization of our wish to disseminate date to any x% of the nodes in the network. Probably, this is something to discuss over and over again in the group until we get full consensus in the group.

...
...
>       share information in an asynchronous way, should be a better

This is the most interesting case (I think of it as a whiteboard, where any ASA can read, write or erase). Doesn't it also relate to distributed consensus mechanisms? 

[Xun, Artur, Zoran and Bing] Very good, yes, why not. We would only add "...the data that it's authorized to" or something like this, but in principle, yes.

Can we consider the previous case (pub/sub) to be a subset of this case, with only one node having write/erase capability?

[Xun, Artur, Zoran and Bing] We think autonomic networking will definitely require a distributed / shared data layer that facilitates information distribution. PubSub is just a model, it's not a mechanism. You can implement it with different mechanisms. Whiteboard is a very particular PubSub instance (everybody is subscribed to everything, everybody is publishing at the exact same location). Similarly, Blockchain would realize the PubSub model where no one can arbitrarily modify the published information, i.e. realizing as a permanent whiteboard (=ledger, secure log, etc).

[Xun, Artur, Zoran and Bing] Simply put, your parallel with a whiteboard scenario is valid. Though, our pub/sub is a more general option, as there can me many such whiteboards, and nodes that disseminate information would require some knowledge which one they should select, etc. And yes, as soon as we start talking about multiple nodes writing in a shared storage of any kind, we need to consider consensus/concurrency etc. issues.

...
>    neighbors who are IPRAN_RSG. 

How does the node performing the distribution know which of its neighbours have the role IPRAN_RSG? Is there a registration process? Is it really any different than the subscribe process in pub/sub? ("I subscribe to IPRAN_RSG information".)

[Xun, Artur, Zoran and Bing] First of all, in this example, it assumes that the role of the device (i.e. IPRAN_RSG) is pre-defined, thus everyone in the network may know what the role of a node is already. However, we notice that this will not be always the case because for different ASAs running on the same node, their roles could be different. Then, how a node (or an ASA) can identify itself and roles of the other nodes (ASAs) will be a challenge. But in principle, yes, the nodes interested in that have to 'subscribe'.

>  5.2 GRASP for asynchronous communications

Once we have the previous point solved, we can model the asynch distribution as a selective flood to the "whiteboard"
in each node.

[Xun, Artur, Zoran and Bing] Again yes and no. It really depends on the extent the shared data layer (i.e. the whiteboard in your term) can support the asynch distribution. A simple solution is that the information is simply forwarded through the shared data layer. A more intelligent solution is that the shared data layer delegates the information delivery in the sense that information storage and notification are autonomously done.

Having said that, I want to look back in the draft at the Event Queue described in section 4.2.1. I'm not sure that we need it as a separate engine from the queues implied by GRASP's existing asynchronous operations. If you model a producer or consumer as a process using GRASP, it will naturally need to support simultaneous asynch operations and an event queue.

I am wondering to what extent I can model this directly over GRASP as it exists today. My main question is mentioned above: how does a node know which of its neighbours have a given role?

[Xun, Artur, Zoran and Bing] Probably only modifying GRASP is not enough. It may involve introducing some new modules and capability assumptions (e.g. local storage) to ANI. If an efficient and intelligent "whiteboard" can be nicely realized, role identification should be easy.

(One possible answer is that *every* node sends out a local GRASP flood at very low frequency, stating which roles it supports.
Then every node builds a cache of its neighbours' roles. I can make that work with GRASP today.)

[Xun, Artur, Zoran and Bing] The problem is not how a node would send such a message or to whom locally. The problem is that it would have to be propagated, which, in a big network, would be an overkill with flooding. Actually, if you are interested in concrete numbers, there is a lot of work and empiric conclusions on that from GNUTELLA, which uses such a protocol with limits to cut off flood storms (e.g. max. TTL and max. number of nodes that you locally send it out to). Gnutella worked (with many tricks to limit the inefficient search), but it could not reliably find an available piece of information. Not sure, this is a suitable for ANIMA.

Regards
    Brian

_______________________________________________
Anima mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/anima