Clever Geek Handbook

Algorithm for efficient management of connection resources

it is difficult to view this if it was asked before, since I do not know its name. So here it is:

I am making this server that connects to messaging gateways to send messages. A session with this gateway requires a username and password combination. This way the gateway knows who has to pay.

Now I can have thousands of messages in the queue to send, for example for 5 different username and password combinations. However, the gateway is limited that I am only saying that two connections open at the same time.

So effectively this is a supply and demand issue with constraints:

I have a gateway that can only handle N concurrent connections (username / pw combo) I have X messages pushed onto the stack belonging to Y different of these connections.

how I, in a nice and clean way, manage these connections effectively so that they sometimes give breathing space for other connections, maybe even prioritize, maybe even allow multiple connections with the same username / password for extra speed (if it does not interfere with other queued connections)

Does anyone know what algorithms exist for this? So I can do it for google. Or maybe someone can already give me some pointers.

I've given a few hits to myself, but I feel like I'm not creating an elegant solution yet, but somehow end up in long nested statements

thank

+2


source to share


3 answers


As another poster, you will need a priority queue, although I suggest you hybridize a priority queue with a queue queue.

  • For each connection (username / password) create a simple LIFO queue. The module that receives the messages must queue them for the appropriate user.
  • The dispatcher module must support priority queue sorting. This means that you have a function priority(queue)

    that calculates the priority for a given queue based on the number of messages, the priority of the account, the time since the last submission, etc. The implementation is priority(queue)

    left as an exercise for the reader.
  • The inner dispatcher loop takes N priority queues from the queue queue, makes a gateway connection for each username / password, and sends all messages on those queues. New empty queues are returned to the queue queue. Recalculate priority for all queues, rinse and repeat.


Ideally, the sending part of the message in step # 3 could be multithreaded.

An alternative implementation of step 3 would be to send messages from each queue until that queue priority drops below the priority of the next waiting queue. However, this means that you recalculate priority(queue)

after each dispatch, which may be more expensive than worth.

+1


source


Conceptually, you want to implement a Priority Queue .

Since you have specific ideas about which message is more prioritized than others, you need an implementation that allows you to calculate a priority score for each entry in the queue. Since you want to group messages occasionally, you will also need to check the queue when prioritizing a new entry in the queue (for example, you might decide to set the priority of a new item to the priority of the newest existing item with the same username if at most N items already have this priority.



Given that you have a fixed number of outbound gateways, you probably need one priority queue for each gateway. A routing component that accepts a new message and determines which queue to place it can check the items in each existing queue to determine which one is best placed (for example, put it on the same queue as other items with the same id user) if anything optimizes the bandwidth.

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

+1


source


Look at OS task scheduling and network scheduling algorithms. They are trying to solve many similar problems by assigning time series of a limited resource to more consumers. There's a lot of research out there. In particular, a weighted fair queue sounds like it might be helpful to you.

Any particular choice is highly dependent on what kind of behavior you want your algorithm to have. For example, if you want to minimize latency across all queues, you need to prioritize the queues with the oldest messages and possibly increase trays to longer queues.

On the other hand, you might want to pre-empt someone doing large batch dispatches as their messages will have a long latency anyway and allow easy queuing before the packet is sent.

0


source






More articles:


All Articles