1

I'm working on an algorithm which routes tasks through a chain of distributed resources based on a hash (or random number).

For example, say you have 10 gateways into a service which distribute tasks to 1000 handlers through 100 queues. 10,000 connected clients are expected to be connected to gateways at any given time (numbers are very general to keep it simple).

Thats

  • 10,000 clients
  • 10 gateways (producers)
  • 100 queues
  • 1000 workers/handlers (consumers)

The flow of each task is client->gateway->queue->worker

Each client will have it's own hash/number which is used to route each task from the client to the same worker each time, with each task going through the same gateway and queue each time. Yet the algorithm handles distribution evenly, meaning each gateway, queue, and worker will have an even workload.

My question is what exactly would this be called? Does such a thing already exist? This started off as a DHT, but I realized that DHTs can't do exactly what I need, so I started from scratch.

  • Are you looking for Queue Theory? – Deer Hunter Feb 5 '14 at 11:09
  • did you look into consistent hashing? – miraculixx Jun 10 '14 at 2:16
1

Each client will have it's own hash/number which is used to route each task from the client to the same worker each time, with each task going through the same gateway and queue each time. Yet the algorithm handles distribution evenly, meaning each gateway, queue, and worker will have an even workload.

These two characteristics are not compatible.

Consider the case where your system is new and process each client one time. Now sort all your clients according to the worker that processed them and send the clients in this order to your system: you will attain the highest possible congestion while respecting the first condition.

If you do not want to drop completely the second requirement, you will probably need to specialise the problem and make an assumption on the distribution of client arrivals.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.