Re: Mesh linking - technical (Was: Re: [Unreal-users] Planned features for 3.3?)

[Bram M. (Syzop) <sy...@vu...>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

christian sullivan wrote:
> Just to cast my .02 into the ring..here are my thoughts.
> 
> There is just really no way that you can (sanely) do full mesh All:All
> linking on larger networks.
> That said, here are some of my thoughts on the idea.
> 
> In order to handle desynch issues, a simple syn/ack type system could
> be implemented.
> 
> User on Server A sets mode +i
> Server A sends mode change to Servers B and C
> Server B acks, Server C does not
> Server A tries n more times to update Server C
> (now let's just get silly...)

If it's TCP then it doesn't make much sense to try multiple times,
unless you actually reconnect of course :).
(But.. it doesn't have to be TCP per se, especially if you put in
sequencing numbers and all that stuff, it makes more sense to go the UDP
way)

But.. I'm not sure if what you said is related to the problem I stated,
since acknowledgments as-is don't solve that particular problem :(

> When a server joins the "mesh" it sends a ping type request, and based
> on the latency/response time of the ping-replys it assigns each server
> in the mesh it's own internal metric

That makes sense (especially for non-full-meshing), but also doesn't
solve the problem from above, since lag will vary from time to time.

On a side note, as others mentioned, you probably also want the option
to humanly control this.

Of course, there are many docs on this subject because routers have been
doing this for a long time.

tabris wrote:
> 	This issue came up on #freenode a year or so ago, and although nothing 
> was really resolved, among the ideas that came up was multi-path 
> routing combined with unique IDs. So you'd have something like a UUID 
> (which usually contains a timestamp too).

This too, doesn't seem to solve the problem. As you can see in my
timestamp idea it's not a good solution because you would have to
artificially introduce a sticky lag of X seconds, and if the lag would
be >X you would have a (non fatal or not) split.
Since, if you process messages realtime you cannot say later on "oh
oops, actually message Y should be before the message X I just sent
out". Too bad IRC servers do not yet have timemachine capabilities ;).

Saturn, the bringer of old age wrote:
> There are a couple ways to deal with this, one off the top of my head
> is: each server has its own sequence number that gets incremented every
> time it sends a line. Then when something that depends on previous state
> happens it refers to this number. So you get something like:
> 
> Server A user connects then joins the channel on line number 500
> Server B sends the mode command with its own line number but also refers
>   back to line number 500 from server A
> Server C stores the mode command until it receives line number 500
>   from server A, then processes it.

This one is particularly interesting, it seems to (try to) handle one of
the source problems which is dependencies.
At first, it seems to theoretically at least solve the JOIN+MODE and
JOIN+KICK problems. In practice it seems a bit more complex of course,
like we would have to store seq# of all joins (easy), and at least
MODE's can have multiple dependencies (:a JOIN, :b JOIN, :x MODE +vvv a
b c) [also easy, I guess].

Of course, there will still be odd issues, such as:
<Bot> -Blah-: <some nice infoline here>
*** Blah joins #blah
*** Bot sets mode: +o Blah
But ah well.

*think a bit further out loud* :)
how about a JOIN, MODE, PART (or JOIN+MODE+QUIT, even).
I suppose in that case we could just use message sequencing without any
dependency stuff (for PART/QUIT).
Let's have some sequencing fun (a different problem, I know).

Let's take this network setup:
  B----C
 /|    |\
A |    | F
 \|    |/
  D----E

{actually B<->E and D<->C might also be connected}

A and F are "leafs", B/C/D/E are routing servers ("hubs"). Naturally in
a real network setup there would be many more leafs, but ah well.

Now, whenever for example a broadcast message from A->ALL travels the
net, and the shortest path to C would be A->B->C (it is at least in # of
hops)... Now suppose B dies... C still needs to get the message.
So who is gonna save that message until it gets "acknowledged"? The
directly connected servers is not a good idea (B, in our case), since
they might (will) die... So I suppose we would have to revert to the
source server, in this case A, to keep a copy. Of course this is
sub-optimal, since "client servers" should theoretically deal as few as
possible with all this routing stuff etc, but it's the only way to - for
example - guarantee delivery of non-broadcast messages such as private
messages.
Then, server A will have to resend the message to C (this time via
A->D->E->C.
Ok, that all makes sense to me...

I'm wondering what would happen if we had for example, from the bot
points of view (which, will be on server D):
:master JOIN #chan {message #100}
:MODE #chan +omi master {message #101}
Now what happens if the JOIN gets delivered from A->D, but then the
server dies when it wants to send it A->B.
The bot will see the join, and do the MODE.
The MODE will be broadcasted from D->B, D->E, etc.
So B will see the mode but it will have a dependency on {message #100}.
Unfortunately, at this moment the server A just died, so server B will
never receive this message, nor can it request A to resend.
Now, we have the situation where we have this MODE in the queue... but
what are we going to do with it?
We cannot simply throw it away because the MODE also did an +mi. We
could of course, still process it, but then the '+o master' should not
be done.
Now, we could have a nice problem with 'master' being joined from
another server, but NICK(U)ID can solve that problem (which is on TODO
btw, but not because of meshing).
Not sure if I missed anything in the above story that could still lead
to any problems?

Oh yes, I did: what if server A's network gets extremely lagged (and
will ultimately have all their links timed out)... Would the MODE +omi
master (or more specific, the +mi part) be delayed up to <server link
timeout> seconds? Obviously that would be no good.
For a tad more realistic scenario one could imagine it being a +ol 20 (a
+o for the known user, combined with the +l 20 by the classical "set
limit to <numusers>+<somevalue> script"), but actually the +omi isn't
all that uncommon either, for smart eggdrops that is :).
For some reason, I doubt it would be acceptable to have a +mi (or any
other non-directly-user-affecting mode, including +be) mode delayed for
like 30/60/90/120 seconds.
Of course, you could set this time limit to a low value like 15s, but
wouldn't we then end up with (much) more splits than without meshing?
And still, delaying a +i for 15 seconds will be quite desasterous in
most cases.

Another, more likely scenario, is a multi-user-KICK. At the moment we
don't have that at Unreal, but it might be implemented some day.
In that particular case, the KICK for all those persons would have to be
delayed until all persons joins have been received.
Unless you go "split down" such kicks in individual ones.. Perhaps you
could even do the same with modes... although that must be quite an
insane idea/funny view.
In that case ':Bot MODE #chan +omi master' will be translated to a '+mi'
and a '+o master', giving 2 mode lines... That must be real fun with
like 6 arguments.. all those +o's on a different line. Actually, I've
seen that plenty of times on M$ Exchange IRC servers, it's just.. ugly.

Thanks to everyone that contributed so far, it's nice to see some real
technical discussion on this subject[1] :).

	Syzop.

[1] The reason I originally did not post it on searchirc is because
    I expected a lot of idiots replying with their "I thought about
    this problem for 10 seconds and I know the solution!" replies.

- --
Bram Matthys
Software developer/IT consultant        sy...@vu...
PGP key:                       www.vulnscan.org/pubkey.asc
PGP fp: 8DD4 437E 9BA8 09AA 0A8D  1811 E1C3 D65F E6ED 2AA2

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (MingW32)

iD8DBQFCttXz4cPWX+btKqIRApSlAJ4z/jeFmWv/004AFY8tHxjiPAwWSgCg1NXa
+CayVFK5bPyhnV3XsLhGIYM=
=DLLv
-----END PGP SIGNATURE-----