Proposed federation changes for M4

[Ted Ross <tr...@redhat.com>]

There are a number of changes desired for federation for the M4 release:

1) Intelligent forwarding of messages based on actual bindings at the 
destination.

    In the current code, message forwarding is done based on
    statically configured bindings to the inter-broker queues.  To get
    messages to consumers who have recently added bindings to their
    local exchanges requires that either:

    a) The federation bindings be general enough to handle any
       possible new binding.  This means that messages are forwarded
       regardless of whether there is an eligible consumer to receive
       it, wasting bandwidth.

    b) The federation bindings somehow be manually changed to
       accomodate the new destination bindings.

    It is desired that federated brokers forward only those messages
    for which there are bindings at the destination.

2) Automatic configuration of the anti-looping (tag/exclude) mechanism.

    The anti-looping mechanism is hard to configure correctly and is
    arguably a detail of the brokers' implementation.  It would be
    better if anti-looping was applied correctly without any input
    from the broker administrator.

=========

I'll cover (2) first as it is a building block for (1).

The anti-looping mechanism prevents messages from being received more
than once on any given broker.  This is important because most useful
federation topologies, especially topics and fanouts, involve loops.
Without anti-looping, a single message can cycle around the topology
indefinitely, being delivered to the same consumers repeatedly.

Anti-looping is implemented with a "tag and exclude" feature of
queues.  The inter-broker queue is configured with two strings:  the
tag and the exclusion tag.  The queue marks all queued messages with
the tag (i.e. appends the tag to a list of tags) and drops all
messages that contain the exclusion tag.

A working convention for tags is as follows:

  - Each broker is assigned a unique tag.
  - Each federation queue uses the local (source) broker's tag and
    excludes the tag for the subscribing (dest) broker.

Here's the proposal for M4:

1) Make the local tag a configuration item for the broker (vhost
   actually).  This can be supplied in the command line or may be set
   by a remote management console.  The tag is stored persistently and
   need be set only once.

2) Add the tag to the server-properties and client-properties fields
   in the connection.start-ok and connection.start messages
   respectively.  Name this property "qpid.federation_tag".

3) When federation routes are set up and their queues configured, if
   tag and exclude values are not supplied in the setup method
   (bridge), use the locally configured tag and the tag advertised by
   the federation peer when setting up the queue.

=========

Here's the proposal for (1).  I'm calling this "dynamic routing"
because it involves dynamically creating and deleting bindings on the
federation queues.

When a federation route is configured, a subscription is created on
the source broker with the "dest" field set to the name of the
destination exchange.  In a "pull" route, this subscription is
initiated by the destination broker.  The federation code that manages
this subscription can track the local bindings on the dest exchange
and propagate the union of the binding keys to the source exchange.

I propose that dynamic routing not be supported for "push" routes.

It is theoretically possible for the derivative bindings to be
"coalesced" or summarized into a smaller number of bindings for a
topic exchange.  I have no plans to attempt this at this time.

It doesn't take much thought to realize that there is a looping issue
for dynamic bindings much like there is with messages.  The solution,
of course, is also similar in that bind commands have an argument
field that can carry a tag list.  Here are the rules:

1) If a local binding is untagged (i.e. it was created by a local
   consumer), tag the bind request with only the local broker tag
   before propagating it to any source brokers.

2) If a binding is declared and it is tagged with the local broker
   tag, do not apply the binding (silently drop it).

3) If the set of tags changes on an existing binding, re-propagate it
   to all sources.

When a new route is established (because it was just added or because
the remote broker just became reachable), the existing bindings of the
dest exchange must be iterated over for propagation.

There is a problem for which I don't currently have a solution.  The
exchange.unbind command does not have an arguments field so
propagation of unbinds is problematic.  One possibility (admittedly
ugly) is to use a field in the exchange.bind arguments to indicate
that a bind command is to be interpreted as an unbind for the purposes
of propagation.

-Ted

Re: Proposed federation changes for M4

[Ted Ross <tr...@redhat.com>]

Martin,

This isn't a modification to the broker.  It's a python model of the 
broker that simulates arbitrary federation topologies and traces all of 
the binding changes and message flows.  I used it to experiment with 
variations on the protocol for dynamic binding.

I'm planning to put it in trunk/qpid/python/models unless anybody 
objects.  It's not part of the qpid distribution and I don't think any 
qpid user would have any interest in it.

-Ted

Martin Ritchie wrote:
> This sort of experimentation sounds ideal for a branch. It sounds like
> there will be modification to the broker so having that on a branch
> will give you isolation to allow for testing.
>
> Or have I got the wrong end of the stick?
>
> Regards
> Martin
>
> 2008/10/20 Ted Ross <tr...@redhat.com>:
>   
>> Gordon Sim wrote:
>>     
>>> I've used your example to try and clarify my own thoughts on how this a
>>> little. It may be that I'm just repeating your suggestion, I've added a bit
>>> more detail so that if thats the case its hopefully clearer and if I'm still
>>> missing something that too will be easier to point out.
>>>
>>>
>>>       
>> I've come to the conclusion that merely thinking about the protocol and
>> algorithms for dynamic binding is insufficient to solve the problem.  So, to
>> make progress, I've modeled the broker in a test/simulation environment to
>> experiment with and validate candidate solutions in various federation
>> topologies.  The things I'm most interested in are:
>>
>> 1) Protocol self-stabilization,
>> 2) zero failures to deliver messages to appropriately bound consumers,
>> 3) minimized delivery of messages to exchanges which have no real consumers
>> bound, and
>> 4) maximized tolerance of variations in topology.
>>
>> Having gone through a number of iterations over the weekend, I think I have
>> arrived at an acceptable solution.
>>
>> Question: is there an appropriate location in the SVN tree to put model code
>> like this simulator?  It's not a customer deliverable, but it is a design
>> tool that may have value for the community.
>>
>> I'll provide details of the newest proposal under separate cover.
>>
>> -Ted
>>
>>
>>     
>
>
>
>   

Re: Proposed federation changes for M4

[Martin Ritchie <ri...@apache.org>]

This sort of experimentation sounds ideal for a branch. It sounds like
there will be modification to the broker so having that on a branch
will give you isolation to allow for testing.

Or have I got the wrong end of the stick?

Regards
Martin

2008/10/20 Ted Ross <tr...@redhat.com>:
> Gordon Sim wrote:
>>
>> I've used your example to try and clarify my own thoughts on how this a
>> little. It may be that I'm just repeating your suggestion, I've added a bit
>> more detail so that if thats the case its hopefully clearer and if I'm still
>> missing something that too will be easier to point out.
>>
>>
> I've come to the conclusion that merely thinking about the protocol and
> algorithms for dynamic binding is insufficient to solve the problem.  So, to
> make progress, I've modeled the broker in a test/simulation environment to
> experiment with and validate candidate solutions in various federation
> topologies.  The things I'm most interested in are:
>
> 1) Protocol self-stabilization,
> 2) zero failures to deliver messages to appropriately bound consumers,
> 3) minimized delivery of messages to exchanges which have no real consumers
> bound, and
> 4) maximized tolerance of variations in topology.
>
> Having gone through a number of iterations over the weekend, I think I have
> arrived at an acceptable solution.
>
> Question: is there an appropriate location in the SVN tree to put model code
> like this simulator?  It's not a customer deliverable, but it is a design
> tool that may have value for the community.
>
> I'll provide details of the newest proposal under separate cover.
>
> -Ted
>
>



-- 
Martin Ritchie

Re: Proposed federation changes for M4

[Ted Ross <tr...@redhat.com>]

Gordon Sim wrote:
> I've used your example to try and clarify my own thoughts on how this 
> a little. It may be that I'm just repeating your suggestion, I've 
> added a bit more detail so that if thats the case its hopefully 
> clearer and if I'm still missing something that too will be easier to 
> point out.
>
>
I've come to the conclusion that merely thinking about the protocol and 
algorithms for dynamic binding is insufficient to solve the problem.  
So, to make progress, I've modeled the broker in a test/simulation 
environment to experiment with and validate candidate solutions in 
various federation topologies.  The things I'm most interested in are:

1) Protocol self-stabilization,
2) zero failures to deliver messages to appropriately bound consumers,
3) minimized delivery of messages to exchanges which have no real 
consumers bound, and
4) maximized tolerance of variations in topology.

Having gone through a number of iterations over the weekend, I think I 
have arrived at an acceptable solution.

Question: is there an appropriate location in the SVN tree to put model 
code like this simulator?  It's not a customer deliverable, but it is a 
design tool that may have value for the community.

I'll provide details of the newest proposal under separate cover.

-Ted

Re: Proposed federation changes for M4

[Gordon Sim <gs...@redhat.com>]

I've used your example to try and clarify my own thoughts on how this a 
little. It may be that I'm just repeating your suggestion, I've added a 
bit more detail so that if thats the case its hopefully clearer and if 
I'm still missing something that too will be easier to point out.

Re: Proposed federation changes for M4

[Ted Ross <tr...@redhat.com>]

Gordon Sim wrote:
> Ted Ross wrote:
>> Here's the proposal for (1).  I'm calling this "dynamic routing"
>> because it involves dynamically creating and deleting bindings on the
>> federation queues.
>>
>> When a federation route is configured, a subscription is created on
>> the source broker with the "dest" field set to the name of the
>> destination exchange.  In a "pull" route, this subscription is
>> initiated by the destination broker.  The federation code that manages
>> this subscription can track the local bindings on the dest exchange
>> and propagate the union of the binding keys to the source exchange.
>
> When you say 'propagate' you mean it will bind a queue it has created 
> on the remote broker (and to which it has subscribed) to the remote 
> exchange so as to have a binding to that queue for each unique binding 
> key defined in the local exchange?
Yes, that is exactly right.
>
>> It doesn't take much thought to realize that there is a looping issue
>> for dynamic bindings much like there is with messages.  The solution,
>> of course, is also similar in that bind commands have an argument
>> field that can carry a tag list.  Here are the rules:
>>
>> 1) If a local binding is untagged (i.e. it was created by a local
>>   consumer), tag the bind request with only the local broker tag
>>   before propagating it to any source brokers.
>>
>> 2) If a binding is declared and it is tagged with the local broker
>>   tag, do not apply the binding (silently drop it).
>>
>> 3) If the set of tags changes on an existing binding, re-propagate it
>>   to all sources.
>
> I _think_ there is a simpler scheme that would work (but perhaps I've 
> misunderstood your description or haven't considered all the cases).
>
> If the bridge that issues the bind requests for a particular route 
> identifies itself and the names of the brokers it has links to (active 
> or not) when it makes that request. Bridges on the broker receiving 
> that request can then ignore that binding if their 'peer' brokers is 
> in that list.
I'm not sure I'm parsing your text correctly but I think it overlooks 
the multi-hop scenario where a federation binding needs to be propagated 
to more than one broker.
>
>> When a new route is established (because it was just added or because
>> the remote broker just became reachable), the existing bindings of the
>> dest exchange must be iterated over for propagation.
>>
>> There is a problem for which I don't currently have a solution.  The
>> exchange.unbind command does not have an arguments field so
>> propagation of unbinds is problematic.  One possibility (admittedly
>> ugly) is to use a field in the exchange.bind arguments to indicate
>> that a bind command is to be interpreted as an unbind for the purposes
>> of propagation.
>
> Can't bridges just track the bindings they have established and then 
> react to unbind on their local broker by unbinding their subscription 
> queue from the remote exchange if necessary? Why would extra tagging 
> be needed? (Apologies if my understanding is overly simplistic here).
Let me answer with an example to illustrate.  Consider a 
"transit-broker" scenario where there are three brokers connected in a 
star (or "line" ;) configuration:

Assume that the federation is configured as a distributed direct exchange.

    +----+            +----+            +----+
    |    | ---------> |    | ---------> |    |
    | B1 |            | B2 |            | B3 |
    |    | <--------- |    | <--------- |    |
    +----+            +----+            +----+

In this example, clients on B1 and B3 can only communicate with each 
other through the transit-broker B2.

A client on broker B1 binds key "A" to the exchange:

      A
      |
    +----+            +----+            +----+
    |    | ---------> |    | ---------> |    |
    | B1 |            | B2 |            | B3 |
    |    | <--------- |    | <--------- |    |
    +----+            +----+            +----+

In order for "A" messages to reach the client from anywhere in the 
network, the binding to A must be propagated to the other brokers in the 
topology.  The federation bindings (those not created directly by a 
client) are tagged according to the rules.

      A
      |
    +----+            +----+            +----+
    |    | ---------> |    | ---------> |    |
    | B1 |            | B2 |            | B3 |
    |    | <--------- |    | <--------- |    |
    +----+      A(1)  +----+     A(1,2) +----+

Note that when B3 attempts to propagate the binding back to B2, the 
binding is dropped and propagation stops.

Now a second client, on B2, also binds to "A".  The binding propagates 
outward from B2 and the new configuration of tags is as follows:

      A                 A
      |                 |
    +----+   A(2)     +----+            +----+
    |    | ---------> |    | ---------> |    |
    | B1 |            | B2 |            | B3 |
    |    | <--------- |    | <--------- |    |
    +----+      A(1)  +----+      A(2)  +----+

Note that the binding from B3 to B2 no longer has the "1" tag.

If the client on B2 were to unbind "A", simply propagating the the 
unbind outbound will correctly remove the binding on B1 but will 
incorrectly remove the binding on B3.  There has to be more intelligent 
discrimination as to which bindings to modify in a bind/unbind scenario.

Having gone through this exercise, I think I'm seeing a solution to my 
no-arguments-in-unbind problem.  More on this later...

-Ted

Re: Proposed federation changes for M4

[Gordon Sim <gs...@redhat.com>]

Ted Ross wrote:
> Here's the proposal for (1).  I'm calling this "dynamic routing"
> because it involves dynamically creating and deleting bindings on the
> federation queues.
> 
> When a federation route is configured, a subscription is created on
> the source broker with the "dest" field set to the name of the
> destination exchange.  In a "pull" route, this subscription is
> initiated by the destination broker.  The federation code that manages
> this subscription can track the local bindings on the dest exchange
> and propagate the union of the binding keys to the source exchange.

When you say 'propagate' you mean it will bind a queue it has created on 
the remote broker (and to which it has subscribed) to the remote 
exchange so as to have a binding to that queue for each unique binding 
key defined in the local exchange?

> I propose that dynamic routing not be supported for "push" routes.
> 
> It is theoretically possible for the derivative bindings to be
> "coalesced" or summarized into a smaller number of bindings for a
> topic exchange.  I have no plans to attempt this at this time.
> 
> It doesn't take much thought to realize that there is a looping issue
> for dynamic bindings much like there is with messages.  The solution,
> of course, is also similar in that bind commands have an argument
> field that can carry a tag list.  Here are the rules:
> 
> 1) If a local binding is untagged (i.e. it was created by a local
>   consumer), tag the bind request with only the local broker tag
>   before propagating it to any source brokers.
> 
> 2) If a binding is declared and it is tagged with the local broker
>   tag, do not apply the binding (silently drop it).
> 
> 3) If the set of tags changes on an existing binding, re-propagate it
>   to all sources.

I _think_ there is a simpler scheme that would work (but perhaps I've 
misunderstood your description or haven't considered all the cases).

If the bridge that issues the bind requests for a particular route 
identifies itself and the names of the brokers it has links to (active 
or not) when it makes that request. Bridges on the broker receiving that 
request can then ignore that binding if their 'peer' brokers is in that 
list.

> When a new route is established (because it was just added or because
> the remote broker just became reachable), the existing bindings of the
> dest exchange must be iterated over for propagation.
> 
> There is a problem for which I don't currently have a solution.  The
> exchange.unbind command does not have an arguments field so
> propagation of unbinds is problematic.  One possibility (admittedly
> ugly) is to use a field in the exchange.bind arguments to indicate
> that a bind command is to be interpreted as an unbind for the purposes
> of propagation.

Can't bridges just track the bindings they have established and then 
react to unbind on their local broker by unbinding their subscription 
queue from the remote exchange if necessary? Why would extra tagging be 
needed? (Apologies if my understanding is overly simplistic here).

Re: Proposed federation changes for M4

[Ted Ross <tr...@redhat.com>]

Ted Ross wrote:
> 1) Make the local tag a configuration item for the broker (vhost
>   actually).  This can be supplied in the command line or may be set
>   by a remote management console.  The tag is stored persistently and
>   need be set only once.
Upon some thought (and off-list discussion with Carl), it seems that 
requiring the admin to configure unique tags in all the brokers is not a 
good idea.  It might well be that there are multiple admins for multiple 
subsets of federated brokers.

Given this, it seems easier to use UUIDs for broker tags.  This removes 
any need for administrative involvement but it also increases the size 
of the tag somewhat.

Here's my main question.  If we move from a string-based tag (right now 
tags are represented as strings and lists of tags are comma-separated) 
to a binary tag, we will more likely use arrays of vbin8s as opposed to 
comma-separated strings.  Should this be implemented in a 
backward-compatible fashion?  In other words, should I add a new 
parameter for binary tracing and leave the string-based one intact and 
handle both cases?  This would allow federation interop between M3 and 
M4 brokers.

An alternative is to use a string representation of the binary data 
(i.e. hex or base64) but this further increases the size of the tag on 
the wire.

-Ted

Re: Proposed federation changes for M4

[Carl Trieloff <cc...@redhat.com>]

>
> There is a problem for which I don't currently have a solution.  The
> exchange.unbind command does not have an arguments field so
> propagation of unbinds is problematic.  One possibility (admittedly
> ugly) is to use a field in the exchange.bind arguments to indicate
> that a bind command is to be interpreted as an unbind for the purposes
> of propagation.

I think you have found a bug in the spec... all commands where meant to have
a field table. There are probably 3 options
- we errata another method with the FT (not great)
- do something like you suggest . (ugly)
- map bind/unbind with the FT into qmf, and use QMF to negotiate the 
dynamic routes.

Personally, I would use qmf.
Carl.