Subject: [Anima] ASA coordination and consensus

From: Brian E Carpenter <[email-masked]>
Date: Mon, 13 Jun 2016 10:44:00 +1200

Hi,

I was looking at draft-ciavaglia-anima-coordination, and noticed that although
it mentions several possible algorithms for coordination, they are mainly aimed
at avoiding simultaneous actions by competing ASAs.

Is there also scope for applying explicit consensus-forming algorithms as well?
There is quite a large literature on consensus algorithms, mainly starting with
Paxos. I'm not saying that any of that is directly applicable to Anima, but it
seems like a closely related problem space.

What I did notice is that all consensus algorithms seem to assume that at any
one moment, there is a designated "master" that is in effect the arbitrator.
It would be nice to avoid that, if possible. It isn't clear to me whether
draft-ciavaglia-anima-coordination assumes that the actual coordination
function runs in a specific master.

Regards
   Brian

---

From: Brian E Carpenter <[email-masked]>
Date: Wed, 15 Jun 2016 08:21:09 +1200

Hello Pierre,

On 15/06/2016 07:19, Peloso, Pierre (Nokia - FR) wrote:
> Hi Brian and Anima Folks,
> 
> Thanks for these interesting questions around coordination topic.
> 
>  Before responding directly to Brian questions, I would suggest we keep in mind a preliminary question:
> Do we intend inside Anima to design coordination solutions that achieve coordination in between
>       1 - a pre known set of (function, algorithm) pairs, 
>       2 - any sets of (function, algorithm) pairs, that could be installed on the network.
> I use here the wording (function, algorithm) pair as I consider the autonomic function along with its implemented ASA piece of code form such a pair. Exemple of what I mean: e.g. function: load balancing inside an OSPF area ; algorithm: re-inforcement learning based on links load ratios and modifying the metric of links.
> Dealing with the pros and cons of these approaches:
>      - Coordination type 1 solutions offer a specific (though tailored) solution to a given problem (coordinating a given set of ASAs a priori known)
>      - Coordination type 2 solutions offer a generic (though not tailored) solution to a wide range of problems (coordinating ASAs which are present in the Autonomous network not precluding which ASAs they are).
> Of course the specific solution is likely to converge faster on the problem it is designed for but will not adapt to additional Autonomic functions.
> [Extra comment: For coordination type 1 solution, I would even favor to embed the coordination code directly inside the concerned ASA as those are a priori known, this is a joint design, both the ASA and their coordination. Put simply the feed-back loops being known, coordinating them is easy.*]

Yes, that is an important choice. Type 1 is obviously possible, and will sometimes
happen as a natural consequence of developing a set of ASAs touching related
parameters. Type 2 might be much harder, because I am not sure what kind of
abstraction we could use to represent coordination independently of the use case.
(That is actually a bigger version of the problem presented by the signaling
protocol - how to represent negotiation independently of the use case - which
I hope we have solved to some extent in GRASP.)

> 
>  Moving to consensus-forming algorithm, it would be absolutely nice to have them abroad, and the scope of the draft is quite open to those. This is more or less simple to achieve depending whether we consider Coordination of type 1 or Coordination of type 2. I am not versed that much in such algorithms, but the case in which I have encountered those were addressing a specific problem, so I cannot imagine whether making them generic is feasible and which are the meta info they require on the functions to coordinate in order to drive them towards a consensus. It would be interesting to know more...

My understanding is that there are general solutions, for some meaning of
'general'. I'm in the middle of a conversation with Heidi Howard in Cambridge,
she has some overview slides at http://hh360.user.srcf.net/slides/qcon_london16.pdf

This is getting a bit researchy for an IETF WG, we can discuss off-list if you
prefer.

> 
>  The question of having a master is something that does not sound pretty autonomic, once again I think this also looks quite differently depending of the context of in which this master is emerging: coordination can either be delegated to ASAs or achieved by a dedicated coordination function. Coordination is required when we have a set (a herd) of ASAs instances which are polling the network and enforcing actions onto the network, each pursuing its own optimization goal.

The master could be elected automatically, which I think would be OK in
an autonomic system, but Heidi's point is that the master becomes a bottleneck.

>  - If coordination is delegated to ASAs and a "selected" instance will have the power to lead the herd, we will have to convince the network operators that this leader will not overlook the others ASAs optimization goals.
>  - If we provide a "kind of third-party" Coordination function which we ask the network operator to entrust with the ability to coordinate this herd of ASAs, this one having the only objective of getting the best of the others, is easier to trust.
> 
> In draft-ciavaglia-anima-coordination we favor a coordination that is generic and then external to ASAs**, in which case, the coordination itself may or may not be based on a master, but it's in any case clearly a third-party coordination. Then in a dedicated entity but not an ASA as a piece of an autonomic loop polling the network and enforcing actions onto the network, it is more a function enforcing settings onto the ASA instances. 
> 
> Finally, I would clarify a point raised by Brian concerning draft-ciavaglia-anima-coordination, though we could believe the coord algorithms aim at avoiding simultaneous actions (and then avoiding collision) by competing ASAs, they really aim at avoiding that the control loops either annihilate each other or continuously diverge or continuously move back and forth.

Yes, competing control loops is the most obvious problem area, but I wrote "actions"
because maybe there are other cases where coordination is needed.

Regards
     Brian

> Regards,
> 
> Pierre
> 
> 
> * That is also the reason why I consider that there is no need to have external coordination between instances of a given ASA, I would expect the ASA designers to have made their job properly and provide the appropriate mechanism to coordinate the a priori known interacting instances. (There the feed-back loops are known a priori)
> ** To be totally honest, there are some expected APIs in the ASA to support the coordination (e.g. allowing the coordination function to control the pace of the execution of an ASA control-loop)
> 
>> -----Message d'origine-----
>> De : Anima [mailto:[email-masked]] De la part de Brian E Carpenter
>> Envoyé : lundi 13 juin 2016 00:44
>> À : Anima WG
>> Objet : [Anima] ASA coordination and consensus
>>
>> Hi,
>>
>> I was looking at draft-ciavaglia-anima-coordination, and noticed that
>> although it mentions several possible algorithms for coordination, they are
>> mainly aimed at avoiding simultaneous actions by competing ASAs.
>>
>> There is quite a large literature on consensus algorithms, mainly starting
>> with Paxos. I'm not saying that any of that is directly applicable to Anima,
>> but it seems like a closely related problem space.
>>
>> _______________________________________________
>> Anima mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/anima
>

---

From: "Peloso, Pierre (Nokia - FR)" <[email-masked]>
Date: Tue, 14 Jun 2016 19:19:40 +0000

Regards,

Pierre