Algorithm for effective connection resource management

Question

Hi,

difficult to look this up if it has been asked previously since I don't know the name for it. So here goes:

I'm making this server which connects to messaging gateways in order to send msgs. A session with this gateway requires a username/password combo. This way the gateway knows who to bill.

Now I could have thousands of messages queued up to send, belonging for instance to 5 different username/password combos. However, the gateway is restricted that I only have say 2 connections open at the same time.

So effectively it is a question of supply and demand with constraints:

I have a gateway which can only handle N concurrent connections (username/pw combo) I have X messages stacked up belonging to Y different of these connections

how do I, in a nice and clean way, efficiently manage these connections so that they sometimes give breathing space for other connections, perhaps even take into account priority, perhaps even allow multiple connections with the same username/password for extra speed (if it doesn't sit in the way of other queued connections)

Does anyone have a clue what kind of algorithms exist for this? So I can google for it. Or perhaps someone already can give me some pointers.

I've given a few stabs at it myself, but I feel I'm still not yet creating an elegant solution, but somehow endup in long nested if statements

thanks

Answer 1

Conceptually you want to implement a Priority Queue.

Since you have specific ideas about what message to prioritize over others, you would want an implementation that allows you to calculate a priority score for each queue entry. Since you want to group messages sometimes, you would also need to be able to examine the queue when assigning priority to a new queue entry (for example, you might decide to set the priority of a new element equal to the priority of the newest existing element with the same username as long as no more than N elements already have that priority.

Given that you have a fixed number of outbound gateways, you would probably want one priority queue per gateway. A routing component that takes a new message and determines which queue to place it on could examine elements in each existing queue to determine which one to best place it on (i.e. place it in the same queue as other elements with the same user ID) if that will optimize throughput.

If your gateway is even a little slower than the routing algorithm, you will have a net increase in speed by making the routing algorithm as clever as possible.

Answer 2

As another poster mentioned, you need a Priority Queue, though I suggest that you hybridize the priority queue with a queue-of-queues.

1. For each connection (username/password), create a simple LIFO queue. The module that receives messages should enqueue them for the appropriate user.
2. The dispatcher module should maintain a priority-sorted queue-of-queues. This implies that you have a function priority(queue) which calculates the priority for a given queue based on the number of messages, account priority, time since last send, etc. Implementing priority(queue) is left as an exercise to the reader.
3. The dispatcher's inner loop takes the N highest-priority queues off of the queue-of-queues, makes a connection to the gateway for each username/password, and sends all messages in those queues. The newly emptied queues go back into the queue-of-queues. Recalculate priority for all queues, rinse and repeat.

Ideally, the message-sending portion of step #3 could be multi-threaded.

An alternate implementation of step #3 would be to send messages from each queue until that queue's priority drops below the priority of the next waiting queue. However, this implies that you recalculate priority(queue) after every send, which may be more expensive than it's worth.

Answer 3

Take a look at OS task scheduling and network scheduling algorithms. They try to solve a lot of similar problems of assigning timeslices of a limited resource to a larger number of consumers. There's a huge amount of research out there. In particular weighted fair queueing sounds like it might be useful for you.

Any particular choices depend heavily on what behavior you want your algorithm to have. For instance if you want to minimize latency for all queues you'll want to prioritize queues with the oldest messages and maybe give larger slices to longer queues.

On the other hand you might want to preempt someone doing large batch sends as their messages will have a long latency anyway and let queues with light usage through before the batch send.