Need algorithm help... I'm not good with "numbers".

dwhitney67 · 08-28-2012, 07:22 PM

Hi Everyone,

I've been assigned a (difficult) task of maintaining/augmenting existing spaghetti code which, amongst many other new features that need to be added, requires me to develop an algorithm to deduce the maximum throughput demand (ie rate) at which I can send network packets from one system to another using various middlewares (e.g. ActiveMQ, Websphere, native sockets).

Basically, I need to test sending messages using a start rate, then escalate that rate periodically until I find the max rate that the middleware cannot support. Once I find that maximum rate, I then need to scale down the rate to find that "magic" sweet spot, or asymptote, where data flows without a hitch.

I've come up with a simple algorithm, where I increase the demand by factors of 2, until I reach throughput demand where the packet receiver(s) can no longer receive packets at the desired rate. Once this demand is reached, I would throttle it back (using a quasi binary search pattern) to find the optimal rate that the receiver(s) can support.

Below is a simple C++ program that I used to test this algorithm (please don't laugh!). Can someone suggest an alternative or more optimal approach for this algorithm?

Code:

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

bool performDemand(int demand)
{
    // perform task...

    // Pretend we get results that validates/invalidates current demand.
    return (demand < 4000) || (rand() % 2 == 1);
}

int main(int argc, char** argv)
{
    srand(time(0));

    int curDemand = 1000;
    int prvDemand = 0;
    int badDemand = 0;

    while ((curDemand - prvDemand) > 1)
    {
        std::cout << "curDemand: " << curDemand << "\tprvDemand: " << prvDemand << std::endl;

        bool success = performDemand(curDemand);

        if (success)
        {
            prvDemand = curDemand;

            if (badDemand == 0)
            {
                curDemand *= 2;
            }
            else
            {
                curDemand = curDemand + (badDemand - curDemand) / 2;
            }
        }
        else
        {
            badDemand = curDemand;
            curDemand = curDemand - (curDemand - prvDemand) / 2;
        }
    }
    std::cout << "\nAll done!" << std::endl;
}

Snark1994 · 08-29-2012, 04:34 AM

What information do you have? Do you just get a boolean value as to whether or not the demand is good, or do you get a measure of how much it failed by?

If you don't have any other information, then I think your binary search idea is probably optimal-ish - the only thing that's really going to affect it is how good your guess is for the initial value to try (though this is going on a slightly stale memory of the algorithmics I've done). I would code the binary search slightly differently, but that's probably more down to personal taste. The only problem I can see is the fact that (as your 'rand()' call demonstrates) that there's some error in the result of 'performDemand'. I'm not sure the model you've got for it is very accurate (i.e. it fails 1/2 the time if we're above the bad demand threshold) - I would expect a more bell-shaped curve. In any case, you can't use a strict binary search, because there's no way for it to 'backtrack' if it gets a bad result. For example:

Code:

bad at 10000
0 - 10000 range: good at 5000 (by chance and sod's law)
5000 - 10000 range: etc.

As you see, your code will never be able to backtrack and you will end up with a very wrong answer (definitely not 4000 - I believe the average value you would get is 7500 by symmetry, but don't quote me on that). I think the best solution would be to run the test many times (I don't know how many is suitable) and then take an average over that dataset for a more reliable answer as to whether or not that demand is good or bad.

On the other hand, if you do, I think you could get a much more efficient algorithm. I don't have the details (I could do some research on it if you do have this information) but essentially, by looking at how much it fails by, you can then make an educated guess as to how far away from the ideal value you are: if it completely chokes up, then you want to take it down a whole load, but if you're only losing a couple of packets then you're quite close and you only want to change it a little bit.

As you may well have guessed by now, I know very little about networks - so apologies if what I said makes no sense in the context you're working with

Hope this helps,

dwhitney67 · 08-29-2012, 05:36 AM

@ Snark1994 -- Thanks for your reply.

Quote: