Dave Cridland wrote:
On Mon Apr 6 17:54:16 2009, Philipp Hancke wrote:
Actually, the current model enables a single client to bring down
a server by making the server broadcast large presence stanzas at
a high rate. Simplistic bandwidth control mechanisms such as "karma"
account traffic per socket, and do not throttle the client when it
generates excessive amounts of s2s traffic.
How does the client force the subscription?
It does not need to force them. It uses the usual subscription process
with online remote clients. Once the subscription is established, the
remote clients can go offline (or use a weird privacy list to block all
incoming presence). The bis optimizations make that more costly for the
attacker btw.
Yes. But not at the cost of making the protocol worse. By the way, the
It is not "worse", just different.
No, it is worse, the failure case of the missing unsubscribed is a
privacy leak.
If unsubscribed is missed - in a detectable way - why would you not
resend that once the connectivity for the responsible domain is
reestablished? (there are some (implementations) bugs related to
detecting that, but I will post that to another thread)
version 0.1 of stanza repeaters (does anyone still have a digital copy
btw) was using hashes to workaround this.
Let's review what happens currently, assuming an initiating contact
with n availableremote contacts across d domains, each of which has y
resources connected - y being different in each instance obviously:
"available remote contacts" is those bis optimizations?
Actually, were those discussed before they were introduced?
What is their impact on presence reliability?
Yes, and they're not mandated.
1) Client sends home server a broadcast presence. Cost E1, O(1).
Why not shift the responsibility for distribution to the client?
This would make E1=O(n) and E2=O(1) (simple message routing).
Afaics, your argument applies for that as well.
Ah, but the server has responsibility anyway, so it's a reasonable
optimization there.
I would argue that the remote server has a similar responsibility :-)
2) Home server, which (almost certainly) has client's roster
in-memory, iterates through and emits one presence stanza per remote
subscribed contact known to be available. Cost E2, O(n). (Iterating
through a list of known available contacts).
Actually, why don't you send the presence stanza to each connected
resource of each available contact here - iterating through a list of
known avaible contact resources)?
It's not that server's responsibility to maintain that definitive list,
though.
Sure. It means that a part of the distribution load is already done on
the remote server. The privacy considerations are less tricky of course.
3) Home server encodes and transmits N stanzas, remote server decodes
and transmits N stanzas. Cost E3, O(n). (One stanza per contact -
arguably this is O(d) to open the stream, and O(y) to send the
stanzas - you pick).
O(y) should be O(n) here?
No, it's d*O(y), but that's equivalent to O(y). I don't think it makes a
huge difference whether it's O(y) + O(d) or O(n), though.
Ah. I probably mis-read your y as 'each remote contact has y resources
(clients) connected' - which is how you are using it in E4.
What you mean here is not y, but the number of remote contacts in
each domain - n/d?
4) Remote server receives one or more fully-addressed stanzas, and
broadcasts them to all resources. Cost E4, O(y). (Iterating through a
list of resources of the recipient).
This is done n times. And you are neglecting costs for privacy list
checks (I will call that O(p), different for each instance and
quite costly imo).
Hence E4 = O(n) + n*(O(p) + O(y))
Well, the moment you start considering privacy lists, the entire thing
breaks, because evaluation of those needs handling at both ends, so a
reverse roster lookup fails. Instead, what's needed is list building,
Well... I don't think a "reverse roster lookup" is really the way to
go. The SIMPLE people seem to use a rather explicit list, but I do not
see how they solve a potential desync.
which means evaluating the privacy list locally n times, in order to
collate a per-domain list of contacts. I've not considered this, because
of the risks of such lists being lost, or out of sync themselves, and
I am arguing that you do not need to do this per stanza in the mcast
case, but once per session.
the problems that having arbitrary servers able to command resources on
your server.
They command those resources because users on your server want them to
do so. Allowing arbitrary servers to command your resources is not
a good idea (-:
This gives E, as O(n) + O(y), a linear complexity algorithm.
O(n) + n*(O(p) + O(y)).
That's O(n + np + ny), I think.
ay.
You want to replace 2-4 with:
2') Home server collates roster by remote domain and emits one
presence stanza per remote domain which has a subscribed contacts
known to be available. This is, I'll accept, likely to be close to
the energy cost of 2, although due to the fluctuating nature of the
final clause that collation has to be done each time, so it'll be a
little above. Cost E2' is, therefore > E2. O(n) + O(d) - I have a
feeling this can be reduced to O(n).
3') encode/transmit/decode 1 stanza per remote domain. This is
certainly an energy/cpu/cost saving compared to the 3 above, no
argument from me here. Cost E3' is < E3. O(d) (One stanza per domain.
Still linear, of course).
Linear with d. Assuming that people 'cluster', d << n is reasonable.
Sure, but I'm astonishingly unconvinced that the O(y) term in E3 is
significant - I suspect the maintainence of the domain XMLstreams is by
far the bigger cost, here - in fact, I personally think it's entirely
reasonable to suggest that for all practical purposes, E3 == E3' ==
O(d), although in practise E3' will be slightly smaller, and in the case
where y is particularly big, that difference will of course become
significant.
But for the vast majority of cases, y == 1 - in my roster, it's a
maximum of 12 (for jabber.org), the next highest is 6 or so (for
gmail.com), and the remaining levels or 2 or 1, across quite a few
see above for y.
domains. I don't think under these cases that - unless the constant
involved is massive - O(y) is going to be a substantial factor.
This O(whatever) is multiplied by number P of presence changes per hour.
3 is a reasonal assumption for normal usage, but I've seen 15-20 from
some contacts.
4') Lookup sender against all rosters in the system, and detirmine
which of the resulting potential recipients is online and available
to the sender. It seems reasonable that it would be possible to limit
the lookup to only contacts who are online and available - assuming
we ignore privacy lists - but you're still adding a lookup and the
This depends on how you do the lookup imo.
Yes, Waqas argues that it might be replacement rather than addition.
associating lookup mechanics (like a hash table or something) which
must be maintained in-memory. I strongly suspect that this much, much
more costly to use, build, and maintain than 4 above, hence E4' >> E4. I
If you are neglecting privacy lists above certainly.
I think you can reduce this to E4' = n*O(y).
n cannot possibly occur in this - n is a figure local to the initiating
server. It might happen d times, though, on different servers.
On each server it is approximately (n/d)*O(y), which sums up to n*O(y).
believe this to be possible to implement as O(log(y)), but I also
suspect it's overwhemlingly more likely that it's O(y) (as derived
from a reverse roster lookup O(log(y)) combined with a
resource-broadcast lookup O(y)).
This give E' as O(n) + O(d) + O(y), a linear compexity algorithm.
Poof goes your argument above about linear complexity versus constant
amortized time.
I can't see (E3' - E3) < ((E4' - E4) + (E2' - E2)) as being at all
likely, so I continue to maintain that this is a false optimization.
I disagree. But at least your argument is technically founded and better
than what I have heard from the council in 2006 (and I had to gather
that from the chatroom).
Waqas points out some potential flaws - I'm still not convinced that it
represents a cost-saving for either end, but the difference might well
Above you mention "the problems that having arbitrary servers able to
command resources on your server".
This is exactly what a remote entity makes your server do for every
stanza it sends to you. Your server has to consult the privacy list
for inbound stanzas to make a routing decision.
For your 12 contacts on jabber.org, this means that jabber.org
has to load 12 privacy lists and check those. Some of those
contacts might be offline and - if your server does not keep all user
data in memory all the time - the lookup might become even more
expensive.
I think waqas already describes the per-source hashtable necessary for
mcast. When distributing to users in that table, it is not necessary to
check individual privacy lists again, because they would not be
contained in the list if they were not interested in stanzas from that
particular source. Making sure that this table never contains users
which the source would not want to be there is the hard part.
be smaller than I thought. In particular, he suggests that E4 might be
implemented as a single multivalued hashtable, thus reducing that lookup
to O(1).
He argues for E4', not E4? We need better symbols obviously.
We had a very interesting conversation about the relative costs of
string internalization and all sorts.
mh... we could extend that to discussing that optimization on
highly parallel vector computers (-:
I care about effective flood control mechanisms. This is about moving
cost where they are affordable.
(I also continue to maintain that this is an arse-clenchingly more
complex solution to the problem of getting presence from one contact
to another, but I hope nobody's arguing against me, there).
It is a different solution. One that has been used for years on IRC.
IRC has a different structure, and uniform view throughout the network -
indeed, one server is specifically designed to be indistinguishable from
any other. That's not the case in XMPP, and means different approaches
Which is a design flaw in IRC that WiZ himself exploited in killer.c
and considerations. IRC behaves like a single XMPP cluster, in that
respect, where all these optimizations are entirely possible.
IRC uses those optimizations on a highly trusted network. XMPP does not
have this advantage. I still wonder why there are no flood bots in XMPP.
philipp
