Re: OT: load distribution algorithm

On Tue, 25 Sep 2007 18:19:48 -0000, Aric Bills <aric.bills@xxxxxxxxx>
wrote:

I like the list structure Uwe proposes. Some random thoughts:

* If you have to search the list very often, you might consider
creating a hash table to serve as an index, rather than calling
[lsearch] each time.

Thanks for the ideas, all are welcome.

In the meantime I wondered, could it be possible to devise a state
machine which avoids the need for sorting and searching?

I don't know how to formally describe it, I can only tell it like a
story. If anyone spots defects in my thinking, please speak up. Here
we go ...

Imagine one dispatcher sending "jobs" (or in this case, sockets) to a
pool of worker queues. We call each worker queue "you" (they are like
borg, they don't need names).

At initial state, all queues are equal. The dispatcher will simply
round robin jobs, until some queue completes a job. How can we know
all queues are equal?

There is a global flag, the shortest queue flag (sqf). At initial
state, its value is -1, which means nobody has the flag, and thus, all
queues are equal.

When the dispatcher accepts a new socket, he will detach the socket
from his thread, select a worker queue (you!), and send you an event
message using thread::send.

The message contains the socket id and a command calling your main
proc. Your main proc is merely a short stub which attaches the socket
to your thread, and sets a fileevent handler which will start the real
work, after stubby returns.

But before all that, stubby will first increment your queue length
counter, because now you have one more socket to work, and the counter
tells you how many.

When you finish a job (user quit, whatever) you will close the socket.
Then, you will decrement your queue length counter and try to grab the
shortest queue flag. If nobody has the flag (sqf < 0), you get it by
default.

Once you get the flag, you immediately set it to the freshly updated
value of your queue length. The value (sqf >= 0) means somebody has
the flag, and the rules say, no one else can grab it from you, unless
their value is less than yours.

Maybe you have the shortest queue, maybe not, who knows? In any case,
you were the first to finish a job, and until now, the dispatcher used
simple round robin. If the dispatcher chooses you next, his choice
may not be optimal, but it would never be worse than round robin by
more than a value of 1. We can tolerate that, it's insignificant for
our purposes.

What's important is now, somebody has the flag!

You will also mark the flag with your id (an index value which locates
your thread id) so the dispatcher can look and see who has the flag.

Now when the next socket arrives, the dispatcher will look and see if
somebody has the flag. Of course, he was already doing this, even in
the initial state, that's how he knew to use simple round robin in the
first place.

But now that somebody has the flag, it gets more interesting.

The dispatcher is very lazy, and he does not want to be bothered with
hard work. He wants you to do the hard work, and when he gets another
socket to dispatch, he does not want to query every one of you, to see
who has the shortest queue. He only likes simple, easy decisions.

So, what does the dispatcher think?

Well let's see, somebody has the flag now, and its value tells me what
their queue length is. I also know who was next in the round robin
rotation, so let me look and compare their queue length to the worker
who has the flag. Yes, I have a global list of all queue counters,
the workers keep it updated for me when they adjust their own internal
counters. I'm much too lazy to look through the whole list, but I can
tolerate checking one, the one up next in the round robin.

So what to do? Naturally, I'll send it to the shortest of the two,
unless they are equal, in which case, next up in the round robin wins
the tie.

Now if the decision went to next up in the round robin, it's just like
actually doing round robin, so I'll advance the round robin pointer to
next in the rotation.

But if the decision went to the queue holding the flag, I don't need
to do anything more, I'll just leave the round robin pointer where it
was, and I'm done until the next socket arrives.

"Ah, I like this job!"

Earlier, we said "no one else can grab it [the flag] from you, unless
their value is less than yours."

The workers have to settle that among themselves, but the dispatcher
never worries, he knows the worker borg always follow the rule.


--
Internet service
http://www.isp2dial.com/
.

Relevant Pages

  • Re: OT: load distribution algorithm
    ... and hence its queue length becomes ... I realized I could eliminate the -1 flag value ... I also arbitrarily start the roundrobin with the worker holding the ... new socket arrives, the dispatcher always makes a simple choice. ...
    (comp.lang.tcl)
  • Re: wave api callback mechanism
    ... > structure to "not in queue" ... I am trying to develop a waveform audio driver using UAM model. ... the callback function passed by wave audio manager using WAVEOPENDESC ... structure and just before that I also set the flag of the WAVEHDR ...
    (microsoft.public.windowsce.platbuilder)
  • Re: wave api callback mechanism
    ... Anwar wrote: ... > structure to "not in queue" ... the callback function passed by wave audio manager using WAVEOPENDESC ... structure and just before that I also set the flag of the WAVEHDR ...
    (microsoft.public.windowsce.platbuilder)
  • Re: IF_HANDOFF vs. IFQ_HANDOFF
    ... Is IF_HANDOFF supposed to be used only when the target queue is not the ... The network adapter's transmit descriptor ring ... whether coalescing that locking with existing driver locking makes ... The whole point of the IFF_OACTIVE flag is to suppress the call to the ...
    (freebsd-net)
  • EventBroker in Composite Application Block - Generic way to Raise / Fire Events at Run Time?
    ... foreach (message in queue) ... public void ActionSomeTopic(object sender, ... the dispatcher, i.e. ...
    (microsoft.public.dotnet.framework.windowsforms)