[jdev] Routing

[Jonathan Dickinson]

Hey All,

You will need a monospace font for this one :).

Can anyone give me some advice on this problem? From what I can tell, currently routers are a congestion point for all components. E.g.

+--------+
| ROUTER +-S2S
+---+----+
|
C2S

As you can see the performance of the whole server depends on the router, and the router can't be scaled horizontally by clustering it (as far as I can tell). Like as follows:

+--------+ +--------+
| ROUTER +---+ ROUTER +-C2S
+--------+ +--------+
| | | |
C2S C2S C2S S2S

Can anyone correct me on this?

I came up with the following solution to the problem:

C2S S2S
| |
+--------+
| ROUTER |
+----+---+
/ | \
C2S-+--------+ +----+---+ +--------+-C2S
| ROUTER +-+ FAILURE+-+ ROUTER |
C2S-+--------+ +----+---+ +--------+-C2S
\ | /
+----+---+
| ROUTER |
+--------+
| |
S2S S2S

The router network works like a token ring network, only that there is no token. Each router can send the packet along to the next as it wishes (in one direction only). The following flow would apply:

<!-- Router1 -->
<route from="c2s1.50" to="joe (AT) joe (DOT) com">
...
</route>

<!-- Router2 -->
<route from="r1" to="joe (AT) joe (DOT) com">
<visit name="r1"/>
...
</route>

<!-- Router3 -->
<route from="r2" to="joe (AT) joe (DOT) com">
<visit name="r1"/>
<visit name="r2"/>
...
</route>

If at any point one of the routers handles the packet successfully it simply stops passing the route node around. If the route node visits the same router twice it:

a. If the node is from 'this' domain send it to the failure node.
b. If the node is not from 'this' domain:
1. If I have a S2S component attached send it to that.
2. If I don't have a S2S component attached send it on.

Components would send failures if no connected client is found: thus making the router continue routing the packet.

The sexy thing about this is that you should be able to remove and connect routers to the network without bringing the whole thing down.

Great so far, this would work well with single-sign-in capable systems (i.e. no resources/priorities like MSN). Now, I can't for the life of me figure out a way to handle resources and priorities. One way would be to (but it's ugly):

Component gets route packet:

<route from="r4" to="joe (AT) joe (DOT) com">
<visit name="r3"/>
<visit name="r4"/>
<priority name="c2s4.1" resource="home" value="0"/>
<priority name="c2s3.50" resource="mobile" value="50"/>
...
</route>

Thus each stanza would make a complete trip round the network (2 at worst) before it could be sent. Does anyone have any clever ideas how to get around this?

Thanks!

Jonathan
_______________________________________________
JDev mailing list
FAQ: http://www.jabber.org/discussion-lists/jdev-faq
Forum: http://www.jabberforum.org/forumdisplay.php?f=20
Info: http://mail.jabber.org/mailman/listinfo/jdev
Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
_______________________________________________

[Artur Hefczyc]

Hi Jonathan,

First - you didn't tell us what you are writing about...
Are you working on kind of clustering implementation for some server
or what?

Anyway.
I think the basic idea is good. I mean with the token-ring like
implementation.

This is how clustering in Tigase server is implemented.
It is more like on your second diagram:

Router-1 <-----> Router-2 <-------> Router-n

There are SM, c2s, s2s and possible other components (MUC, PubSub)
attached to each router. Routers deliver packets to components by
the packet address. Whole clustering is implemented on the component
level. The component decides whether the packet can be processed
locally or it should be forwarded to a different cluster node.

This is because each component has different needs about clustering
so the logic must be inside the component otherwise the router
implementation would be too complex and couldn't be generic.

Artur

On 23 Jun 2008, at 12:42, Jonathan Dickinson wrote:

> Hey All,
>
> You will need a monospace font for this one :).
>
> Can anyone give me some advice on this problem? From what I can
> tell, currently routers are a congestion point for all components.
> E.g.
>
> +--------+
> | ROUTER +-S2S
> +---+----+
> |
> C2S
>
> As you can see the performance of the whole server depends on the
> router, and the router can't be scaled horizontally by clustering it
> (as far as I can tell). Like as follows:
>
> +--------+ +--------+
> | ROUTER +---+ ROUTER +-C2S
> +--------+ +--------+
> | | | |
> C2S C2S C2S S2S
>
> Can anyone correct me on this?
>
> I came up with the following solution to the problem:
>
> C2S S2S
> | |
> +--------+
> | ROUTER |
> +----+---+
> / | \
> C2S-+--------+ +----+---+ +--------+-C2S
> | ROUTER +-+ FAILURE+-+ ROUTER |
> C2S-+--------+ +----+---+ +--------+-C2S
> \ | /
> +----+---+
> | ROUTER |
> +--------+
> | |
> S2S S2S
>
> The router network works like a token ring network, only that there
> is no token. Each router can send the packet along to the next as it
> wishes (in one direction only). The following flow would apply:
>
> <!-- Router1 -->
> <route from="c2s1.50" to="joe (AT) joe (DOT) com">
> ...
> </route>
>
> <!-- Router2 -->
> <route from="r1" to="joe (AT) joe (DOT) com">
> <visit name="r1"/>
> ...
> </route>
>
> <!-- Router3 -->
> <route from="r2" to="joe (AT) joe (DOT) com">
> <visit name="r1"/>
> <visit name="r2"/>
> ...
> </route>
>
> If at any point one of the routers handles the packet successfully
> it simply stops passing the route node around. If the route node
> visits the same router twice it:
>
> a. If the node is from 'this' domain send it to the failure node.
> b. If the node is not from 'this' domain:
> 1. If I have a S2S component attached send it to that.
> 2. If I don't have a S2S component attached send it on.
>
> Components would send failures if no connected client is found: thus
> making the router continue routing the packet.
>
> The sexy thing about this is that you should be able to remove and
> connect routers to the network without bringing the whole thing down.
>
> Great so far, this would work well with single-sign-in capable
> systems (i.e. no resources/priorities like MSN). Now, I can't for
> the life of me figure out a way to handle resources and priorities.
> One way would be to (but it's ugly):
>
> Component gets route packet:
>
> <route from="r4" to="joe (AT) joe (DOT) com">
> <visit name="r3"/>
> <visit name="r4"/>
> <priority name="c2s4.1" resource="home" value="0"/>
> <priority name="c2s3.50" resource="mobile" value="50"/>
> ...
> </route>
>
> Thus each stanza would make a complete trip round the network (2 at
> worst) before it could be sent. Does anyone have any clever ideas
> how to get around this?
>
> Thanks!
>
> Jonathan
> _______________________________________________
> JDev mailing list
> FAQ: http://www.jabber.org/discussion-lists/jdev-faq
> Forum: http://www.jabberforum.org/forumdisplay.php?f=20
> Info: http://mail.jabber.org/mailman/listinfo/jdev
> Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
> _______________________________________________

Artur
--
Artur Hefczyc
http://www.tigase.org/
http://artur.hefczyc.net/

_______________________________________________
JDev mailing list
FAQ: http://www.jabber.org/discussion-lists/jdev-faq
Forum: http://www.jabberforum.org/forumdisplay.php?f=20
Info: http://mail.jabber.org/mailman/listinfo/jdev
Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
_______________________________________________

[Tomasz Sterna]

Dnia 2008-06-23, pon o godzinie 13:42 +0200, Jonathan Dickinson pisze:
> Thus each stanza would make a complete trip round the network (2 at
> worst) before it could be sent. Does anyone have any clever ideas how
> to get around this?

In http://svn.xiaoka.com/jabberd2/branches/clustering you will find
jabberd2 which routes packets based on full-JIDs.


--
/\_./o__ Tomasz Sterna
(/^/(_^^' http://www.xiaoka.com/
._.(_.)_ im:smoku (AT) xiaoka (DOT) com

_______________________________________________
JDev mailing list
FAQ: http://www.jabber.org/discussion-lists/jdev-faq
Forum: http://www.jabberforum.org/forumdisplay.php?f=20
Info: http://mail.jabber.org/mailman/listinfo/jdev
Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
_______________________________________________

[Jonathan Dickinson]

Okay, so from what I can tell Tigase works as follows:

+--------+ +--------+
| ROUTER +--+ ROUTER |
+--------+ +--------+
| | | |
C2S --- C2S C2S --- C2S

(Components are aware of each other, packet switched/p2p)

And jabberd2 works as follows (my diagram is a gross simplification):

+------------+ +------------+
| ROUTER /---+-+---\ ROUTER |
| / /-+-+-\ \ |
+------/--/--+-+--\--\------+
| | | |
C2S C2S C2S C2S

(Router knows the routes to each connected entity, circuit switched)

One thing I am worried about is storing routes in each router or component. You could get, in the worst case scenario, a router with every single possible route target stored (and then you might as well no longer cluster them). I was hoping to do something more along the terms of classical routing where the router has zero-knowledge: it gets a packet - sees if it should/can be routed to a connected component otherwise it sends it on.

Both are proven concepts, P2P scales really well and PSTN has been around for ages and just works. I will probably try both and see how they pan out.

> -----Original Message-----
> From: jdev-bounces (AT) jabber (DOT) org [mailto:jdev-bounces (AT) jabber (DOT) org] On
> Behalf Of Tomasz Sterna
> Sent: 23 June 2008 02:27 PM
> To: Jabber/XMPP software development list
> Subject: Re: [jdev] Routing
>
> Dnia 2008-06-23, pon o godzinie 13:42 +0200, Jonathan Dickinson pisze:
> > Thus each stanza would make a complete trip round the network (2 at
> > worst) before it could be sent. Does anyone have any clever ideas how
> > to get around this?
>
> In http://svn.xiaoka.com/jabberd2/branches/clustering you will find
> jabberd2 which routes packets based on full-JIDs.
>
>
> --
> /\_./o__ Tomasz Sterna
> (/^/(_^^' http://www.xiaoka.com/
> ._.(_.)_ im:smoku (AT) xiaoka (DOT) com
>
> _______________________________________________
> JDev mailing list
> FAQ: http://www.jabber.org/discussion-lists/jdev-faq
> Forum: http://www.jabberforum.org/forumdisplay.php?f=20
> Info: http://mail.jabber.org/mailman/listinfo/jdev
> Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
> _______________________________________________
_______________________________________________
JDev mailing list
FAQ: http://www.jabber.org/discussion-lists/jdev-faq
Forum: http://www.jabberforum.org/forumdisplay.php?f=20
Info: http://mail.jabber.org/mailman/listinfo/jdev
Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
_______________________________________________

[Pedro Melo]

Hi,

On Jun 23, 2008, at 12:42 PM, Jonathan Dickinson wrote:

> Can anyone give me some advice on this problem? From what I can
> tell, currently routers are a congestion point for all components.
> E.g.
>
> +--------+
> | ROUTER +-S2S
> +---+----+
> |
> C2S
>
> As you can see the performance of the whole server depends on the
> router, and the router can't be scaled horizontally by clustering
> it (as far as I can tell). Like as follows:
>
> +--------+ +--------+
> | ROUTER +---+ ROUTER +-C2S
> +--------+ +--------+
> | | | |
> C2S C2S C2S S2S
>
> Can anyone correct me on this?

I might be missing something obvious, but this is exactly what
ejabberd does, it scales horizontally the router core.

The JSM is another matter altogether, though...

Keeping the "who's online and where" table is the tricky part. On a
first approach you would have to keep it up-to-date on each node.

A way to bypass that limitation is a clever use of the resource part
of each jid: just add a contanst-length "tag" to the resource,
marking the server where that resource is located. This seems to be
what Google is doing.


> I came up with the following solution to the problem:
>
> C2S S2S
> | |
> +--------+
> | ROUTER |
> +----+---+
> / | \
> C2S-+--------+ +----+---+ +--------+-C2S
> | ROUTER +-+ FAILURE+-+ ROUTER |
> C2S-+--------+ +----+---+ +--------+-C2S
> \ | /
> +----+---+
> | ROUTER |
> +--------+
> | |
> S2S S2S
>
> The router network works like a token ring network, only that there
> is no token. Each router can send the packet along to the next as
> it wishes (in one direction only). The following flow would apply:
>
> <!-- Router1 -->
> <route from="c2s1.50" to="joe (AT) joe (DOT) com">
> ...
> </route>
>
> <!-- Router2 -->
> <route from="r1" to="joe (AT) joe (DOT) com">
> <visit name="r1"/>
> ...
> </route>
>
> <!-- Router3 -->
> <route from="r2" to="joe (AT) joe (DOT) com">
> <visit name="r1"/>
> <visit name="r2"/>
> ...
> </route>
>
> If at any point one of the routers handles the packet successfully
> it simply stops passing the route node around. If the route node
> visits the same router twice it:
>
> a. If the node is from 'this' domain send it to the failure node.
> b. If the node is not from 'this' domain:
> 1. If I have a S2S component attached send it to that.
> 2. If I don't have a S2S component attached send it on.

First, let me state that I don't totally understand what you are
trying to achieve with this design, so I'm probably missing something.

But with this design, all stanzas need to cross (on average) N/2
routers where N is the number of routers. More: with the rules above,
it seems to me that outbound stanzas need a run-around the circle
once before we decide the stanza is not ours. This of course is the
only way to do it if each node does not have a notion of local
domains, but again, if the problem is router congestion, I believe
your design is even worse than the current ones.


> Components would send failures if no connected client is found:
> thus making the router continue routing the packet.
>
> The sexy thing about this is that you should be able to remove and
> connect routers to the network without bringing the whole thing down.

As you can today, with ejabberd for example. In fact one of the funny
aspects of ejabberd is that you can add or remove nodes in runtime,
but you cannot add or remove virtual domains in runtime. :)


> Great so far, this would work well with single-sign-in capable
> systems (i.e. no resources/priorities like MSN). Now, I can't for
> the life of me figure out a way to handle resources and priorities.
> One way would be to (but it's ugly):
>
> Component gets route packet:
>
> <route from="r4" to="joe (AT) joe (DOT) com">
> <visit name="r3"/>
> <visit name="r4"/>
> <priority name="c2s4.1" resource="home" value="0"/>
> <priority name="c2s3.50" resource="mobile" value="50"/>
> ...
> </route>
>
> Thus each stanza would make a complete trip round the network (2 at
> worst) before it could be sent. Does anyone have any clever ideas
> how to get around this?

Get an Google Account. Log into Google Talk. Look at the resource you
get back from the server. It ends with 8 char hex string. Its the
server that is handling this connection. So each router can find the
correct server just by looking at the last 8 chars of the destination
jid.

Best regards,
--
HIId: Pedro Melo
SMTP: melo (AT) co (DOT) sapo.pt
XMPP: pedro.melo (AT) sapo (DOT) pt


_______________________________________________
JDev mailing list
FAQ: http://www.jabber.org/discussion-lists/jdev-faq
Forum: http://www.jabberforum.org/forumdisplay.php?f=20
Info: http://mail.jabber.org/mailman/listinfo/jdev
Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
_______________________________________________

[Norman Rasmussen]

On Mon, Jun 23, 2008 at 3:19 PM, Pedro Melo <melo (AT) co (DOT) sapo.pt> wrote:

> Get an Google Account. Log into Google Talk. Look at the resource you
> get back from the server. It ends with 8 char hex string. Its the
> server that is handling this connection. So each router can find the
> correct server just by looking at the last 8 chars of the destination
> jid.
>

As you sure that the suffix is used to route the stanza's? If you use
non-sasl login, you can force the server's to not use the suffix. Also the
suffix is random. As far as I knew if was so that you can never cause a
resource conflict.

--
- Norman Rasmussen
- Email: norman (AT) rasmussen (DOT) co.za
- Home page: http://norman.rasmussen.co.za/

_______________________________________________
JDev mailing list
FAQ: http://www.jabber.org/discussion-lists/jdev-faq
Forum: http://www.jabberforum.org/forumdisplay.php?f=20
Info: http://mail.jabber.org/mailman/listinfo/jdev
Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
_______________________________________________

[Jonathan Dickinson]

> -----Original Message-----
> From: jdev-bounces (AT) jabber (DOT) org [mailto:jdev-bounces (AT) jabber (DOT) org] On
> Behalf Of Pedro Melo
> Sent: 23 June 2008 03:20 PM
> To: Jabber/XMPP software development list
> Subject: Re: [jdev] Routing
>
> ...
>
> Get an Google Account. Log into Google Talk. Look at the resource you
> get back from the server. It ends with 8 char hex string. Its the
> server that is handling this connection. So each router can find the
> correct server just by looking at the last 8 chars of the destination
> jid.

Thanks a million Pedro. That seems like a *great* idea to me!!! I think the resource would then be transformed internally so that you could do the classical resource login. Thanks a million!!! I am going to go for this one.

>
> Best regards,
> --
> HIId: Pedro Melo
> SMTP: melo (AT) co (DOT) sapo.pt
> XMPP: pedro.melo (AT) sapo (DOT) pt
>
>
> _______________________________________________
> JDev mailing list
> FAQ: http://www.jabber.org/discussion-lists/jdev-faq
> Forum: http://www.jabberforum.org/forumdisplay.php?f=20
> Info: http://mail.jabber.org/mailman/listinfo/jdev
> Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
> _______________________________________________
_______________________________________________
JDev mailing list
FAQ: http://www.jabber.org/discussion-lists/jdev-faq
Forum: http://www.jabberforum.org/forumdisplay.php?f=20
Info: http://mail.jabber.org/mailman/listinfo/jdev
Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
_______________________________________________

[Pedro Melo]

Hi,

On Jun 23, 2008, at 2:40 PM, Norman Rasmussen wrote:

> On Mon, Jun 23, 2008 at 3:19 PM, Pedro Melo <melo (AT) co (DOT) sapo.pt> wrote:
> Get an Google Account. Log into Google Talk. Look at the resource you
> get back from the server. It ends with 8 char hex string. Its the
> server that is handling this connection. So each router can find the
> correct server just by looking at the last 8 chars of the destination
> jid.
>
> As you sure that the suffix is used to route the stanza's? If you
> use non-sasl login, you can force the server's to not use the
> suffix. Also the suffix is random. As far as I knew if was so
> that you can never cause a resource conflict.

No, I'm not sure. I've seen it referenced somewhere and I'll try to
find the source of the reference. It makes sense to me though, and I
would use it if I needed to scale to that number of connected resources.

I don't understand, using a non-sasl login part. I always get the
extra bytes myself. As for being "random", how can you tell? How can
you tell if you are not being sent to a different server?

Best regards,
--
HIId: Pedro Melo
SMTP: melo (AT) co (DOT) sapo.pt
XMPP: pedro.melo (AT) sapo (DOT) pt


_______________________________________________
JDev mailing list
FAQ: http://www.jabber.org/discussion-lists/jdev-faq
Forum: http://www.jabberforum.org/forumdisplay.php?f=20
Info: http://mail.jabber.org/mailman/listinfo/jdev
Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
_______________________________________________

[Pedro Melo]

Hi,

On Jun 23, 2008, at 2:36 PM, Jonathan Dickinson wrote:

>> -----Original Message-----
>> From: jdev-bounces (AT) jabber (DOT) org [mailto:jdev-bounces (AT) jabber (DOT) org] On
>> Behalf Of Pedro Melo
>> Sent: 23 June 2008 03:20 PM
>> To: Jabber/XMPP software development list
>> Subject: Re: [jdev] Routing
>>
>> ...
>>
>> Get an Google Account. Log into Google Talk. Look at the resource you
>> get back from the server. It ends with 8 char hex string. Its the
>> server that is handling this connection. So each router can find the
>> correct server just by looking at the last 8 chars of the destination
>> jid.
>
> Thanks a million Pedro. That seems like a *great* idea to me!!! I
> think the resource would then be transformed internally so that you
> could do the classical resource login. Thanks a million!!! I am
> going to go for this one.

I like it too. But be advised of something. A lot of protocols allow
the use of a full jid (including the resource) as a persistent ID.

For example, the spec still allows (this is being dropped in the bis
spec I believe) subscribing entries in the roster with a full JID.
Also, some people would like to subscribe pubsub notes using the full
jid, thus allowing them to subscribe some nodes only when they are
connected from the desktop client (and not from the phone).

Basically there are two different views about JIDs: some see it as
routing helpers, other as part of the user identity. For example,
some expect that if they connect as me@domain/res, I will always kick
the other connections me@domain/res... Using the resource as a
routing helper could prevent this kind of stuff.

Just an heads up about the duality of resources.

Best regards,
--
HIId: Pedro Melo
SMTP: melo (AT) co (DOT) sapo.pt
XMPP: pedro.melo (AT) sapo (DOT) pt


_______________________________________________
JDev mailing list
FAQ: http://www.jabber.org/discussion-lists/jdev-faq
Forum: http://www.jabberforum.org/forumdisplay.php?f=20
Info: http://mail.jabber.org/mailman/listinfo/jdev
Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
_______________________________________________

[Artur Hefczyc]

Hi,

>> s2s component needs to obtain dialback keys which can be stored on a
>> different
>> node.
>
> I am going to do S2S at a much later stage :).

Yes, but it is always good to plan ahead...

>> SM must handle properly situation where 2 users talk to each other
>> and
>> they are connected to a different nodes. Or it needs to handle
>> properly the
>> case when user opens 2 or more connection and each connection end-
>> up on a
>> different node therefore SM behaves in a similar way to what you
>> described below.
>> If local SM can not process the packet it forwards it to the SM on
>> the
>> next node.
>> If all nodes couldn't process the packet is it sent back to the first
>> node which handles it somehow.
>
> Okay, what about when the SM is on the 3rd router or such? How does
> it handle this case? Similar to the round-trip fashion of mine?

This is the case indeed. The packet travels through all nodes until it
finds
a component which can handle it properly. Some packets can simply die
if there is no handler and some must be returned to the original sender.
It all depends on particular case.

>> I am now preparing presentation about Tigase cluster implementation.
>> I will let you know when it is ready.
>
> Please that would be fantastic! Tigase is a good benchmark so any
> tips I can get from you guys would be great!

I will run benchmarking for Tigase cluster too. But it won't probably
happen
until August.

>> Are you going to implement clustering in the server or you are
>> seeking
>> the
>> information out of curiosity?
>
> Yup clustered XMPP server in C#. Going to have a whole bunch of
> goodness included (ASP.Net-like webservices, but over XMPP - etc.).

Good luck then :-)
Artur
--
Artur Hefczyc
http://www.tigase.org/
http://artur.hefczyc.net/

_______________________________________________
JDev mailing list
FAQ: http://www.jabber.org/discussion-lists/jdev-faq
Forum: http://www.jabberforum.org/forumdisplay.php?f=20
Info: http://mail.jabber.org/mailman/listinfo/jdev
Unsubscribe: JDev-unsubscribe (AT) jabber (DOT) org
_______________________________________________