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

[tabris <ta...@ta...>]

On Sunday 19 June 2005 11:02 am, Bram Matthys (Syzop) wrote:
> {note to anyone who is planning to reply: please read the whole text
> first}
>
> tabris wrote:
> > 	What is the planned feature list for 3.3? The FAQ doesn't list it,
> > and there's nothing in google either.
> >
> > 	One thing that comes to mind is mesh routing. So far one
> > experimental IRCd has it, maybe it should be possible to stick into
> > Unreal. With 18 months to do the development, anything is possible,
> > right?
>
> This is a (searchirc) forum post I prepared a few months ago but
> never send out:
>
> Mesh linking (without desynchs) impossible?
>
> Just like many other ircd coders I have been thinking of alternative
> linking methods for a long time, several years ago I've also written
> a simple ircd once that implemented mesh linking (eg: in all-to-all
> principle). But I've always been wondering if mesh linking is really
> possible without desynch issues.
>
> Basically the problem is sequencing and difference in lag.
> Example:
> - a mesh network ABC where all nodes are connected to each other.
> - A<->B has 0.1s of lag
> - A<->C has 0.5s of lag.
> - B<->C has 0.1s of lag (irrelevant in this example)
>
> [SERVER A] User a connects to this server and joins #chan
> [SERVER B] Got this message from server A, a user on this server
> sends a 'MODE #chan +v a' (say, an autovoice bot).
> [SERVER C] Server C still hasn't received the message from A yet, but
> does get the 'MODE #chan +v a', however 'a' does not exist, hence
> this mode is ignored.=20
> [SERVER C] Server C gets the connect+join message from server A.
>
> The desynch is clear, user 'a' is voiced on server A and B, but
> voiceless on server C.
>
> {note that the above example occurs due to JOIN+MODE, it is not
> required nor relevant that the user just connected. Naturally there
> are several other occurrences of this problem, such as JOIN+KICK,
> etc, but this particular JOIN+MODE one is the hardest to solve, so
> let's concentrate on that one}
>
> With normal IRC linking this situation is not possible.
>
> So while I agree it's not hard to simply code something that connects
> all-to-all (or even with servers connected to 1 node), it's much
> harder - if not "impossible" - to prevent any desynchs.
>
> Alternate methods (I think they also appeared in IRC3), including
> "resend" systems with acknowledgments etc, can AFAICT also not deal
> with this problem.
>
> One possible crazy way I can think of to deal with this problem is to
> have absolute time, basically delay all actions several seconds (or
> whatever <max acceptable lag> is), order them by absolute time and
> then execute them (for example MODE=3Dt110, CONNECT=3Dt000, JOIN=3Dt020).
> Something I highly doubt anyone would want (besides you never know
> how much you should actually delay, so it's completely infeasible
> anyway).

	This issue came up on #freenode a year or so ago, and although nothing=20
was really resolved, among the ideas that came up was multi-path=20
routing combined with unique IDs. So you'd have something like a UUID=20
(which usually contains a timestamp too). I agree on the 'taking more=20
bandwidth'. And after looking at some of the docs on InspIRCd, I've=20
felt like asking if they have _any_ clue on real network-theory.

	If nothing else, full meshing is pointless b/c some servers may not be=20
reachable even under optimum conditions (certain kinds of hubs, or IPv6=20
vs IPv4). Further, full meshing is inefficient. It would be better to=20
have leaves have multiple hubs, and hubs to be doubly or triply linked.=20
But not to have N:N linking (exponential/factorial complexity,=20
anyone?).

	Of course, there is also the fact that full-meshing ignores the fact=20
that there are certain routes that are more efficient than others, and=20
that it should be the humans job (or at least option) of choosing those=20
routes.
>
> There is also another "possibility" as well, which is if all servers
> forward all (broadcast related) stuff they receive one time... so
> even though a broadcast message will go A->B and A->C, you could also
> let it forward by B too, so A->B->C AND A->C. In that case this
> sequencing problem disappears. Downside is that you are using XX(X?)
> times more bandwidth than needed on an average network (if I'm not
> mistaken the formula is SERVERS*(SERVERS-1) ?), which I doubt is
> acceptable.
>
> I wonder if the coders of the few ircds that implemented mesh links
> actually thought of things like this (brain?), because I have a
> feeling they simple implemented it (like I did several years ago, and
> yes, it was fun) instead of actually thinking trough all these
> possible (theoretical) desynch situations and how to deal with them.
>
> Any (well-thought-through) comments are welcome. I would love it if
> someone could prove me wrong and resolve these issues by some things
> I haven't thought of yet. That would mean mesh linking is more viable
> than I thought, but - for now - I'm afraid I'm correct.
>
> 	Syzop.

=2D-=20
Keep ancient lands, your storied pomp! cries she
With silent lips.  Give me your tired, your poor,
Your huddled masses yearning to breathe free,
The wretched refuse of your teeming shore.
Send these, the homeless, tempest-tossed to me...
		-- Emma Lazarus, "The New Colossus"