Fast Routing Algo

Hi there,

I need to build a routing tool/service but do not know which is the fastest algorithm to use. I do believe that a star topolgy for this network is the best one, though I may be very wrong.

In this network there are subrcirbers that send messages and subsribers that recieve messages. the tool is connected to each of these subscribers. We can count on there being more than 1 in each group.

Messages will be pumped by the senders to the service, and the service has to route the message to the correct database of the reciever it was meant for.

Messages come in sporadically. i.e. We can have a message every few seconds or in massive bursts of messages (e.g. 1000+ messages per second)

There are two possible setups:
1. We know which database to send the message to, based on who the reciever is. We know who the reciever is from the message.
2. We know which database to send the message to, based on who the sender is. We know who the sender is from the connection. i.e. we have a unique connection with a sender for each reciever account. (I dont think this case is considered routing, but am not sure. I read something about pipeline routing, but am not sure whether this is pipeline routing).

So my questions are:
1. What is the best topology for each case?

2. What do you guys suggest as the best algorithm and data structure to implement in this case?

Thank you very much for assistance
Ron

Hi,

I don't have experience to comment on your first question so others hopefully will do that. As for the fast routing algo. A month or so ago I needed to choose one myself and I've decided to go with Contraction Hierachies (CH for short). There are a few reasons for that:
1. It has a good balance between fast queries and preprocessing time.
2. It is easier to implement than most of the other alternatives, but it is still by far as simple as a plain old Djkstra.
3. There are a few tools that use this algorithm, so you can look at other implementations (Graphhopper, Project OSRM and graphserver all use this algorithm; OpenTripPlanner says they also use it, but I could not find code that actually constructs the CH in its sources)
The actual algorithm was developed quite a few years back by a guy from KIT (project homepage). For a static graph - i. e. weights of edges do not change over time, don't have shedules, etc. - it is a very elegant and fast algorithm. For time dependent scenario things are much more complicated (but the same goes for any other algorithm in the wild). Needless to say, that is exactly what I've been strugling with for the past 2 weeks I guess (worst thing is that I was not able to find any example implementation for this scenario).
If you want some more choices, there is a very good paper by Daniel Delling et. al. "Engineering Route Planning Algorithms". Those guys have done a gread job comparing quite a few different algorithms. I recommend reading it before making your desidion.

Hope that helps :)

Thanks Mikism, I'll defnitely read that paper, and look into CH.

Cheers :)