Re: [PATCH net-next] net: ipvs: random start for RR scheduler

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



	Hello,

On Tue, 10 May 2022, Menglong Dong wrote:

> On Tue, May 10, 2022 at 2:17 AM Julian Anastasov <ja@xxxxxx> wrote:
> >
> >         or just use
> >
> >         start = prandom_u32_max(svc->num_dests);
> >
> >         Also, this line can be before the spin_lock_bh.
> >
> > > +     cur = &svc->destinations;
> >
> >         cur = svc->sched_data;
> >
> >         ... and to start from current svc->sched_data because
> > we are called for every added dest. Better to jump 0..127 steps
> > ahead, to avoid delay with long lists?
> >
> 
> I'm a little afraid that the 'steps' may make the starting dest not
> absolutely random, in terms of probability. For example, we have
> 256 services, and will the services in the middle have more chances
> to be chosen as the start? It's just a feeling, I'm not good at
> Probability :/

	Me too, so I created a test for the eyes :) I hope
it correctly implements the algorithm.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DESTS		1024
#define NTESTS		(500000)
#define MAX_STEP	32

/* MAX_STEP:
 * 4: last has 3 times more chance than first
 * 5: last has 2 times more chance than first
 * 6: last has 60% more chance than first
 * 7: last has 50% more chance than first
 * 10: last has 20% more chance than first
 * 16: last has 10% more chance than first
 * 32: last has 3% more chance than first
 */

int
main (int argc, char *argv[])
{
	int arr[DESTS];		/* Hits per dest */
	int i, n;
	int64_t perc = 0, perc2;

	memset(arr, 0, sizeof(arr));
	srand(257);
	/* Do more test for better stats */
	for (i = 0; i < NTESTS; i++)
	{
		int pos = 0;	/* sched_data */

		/* Show progress */
		perc2 = ((int64_t) i * 100) / NTESTS;
		if (perc != perc2)
		{
			fprintf(stderr, "\r%d%%", (int) perc2);
			fflush(stderr);
			perc = perc2;
		}
		/* Add all dests */
		for (n = 2; n < DESTS; n++)
		{
			int m, step;

			/* New dest -> new step */
			m = n;
			if (m > MAX_STEP)
				m = MAX_STEP;
			step = rand() % m;

			pos = (pos + step) % n;
		}
		/* Start pos determined */
		arr[pos] ++;
	}
	fprintf(stderr, "\n");
	for (n = 0; n < DESTS; n++)
	{
		printf("%d\t%d\n", n, arr[n]);
	}
	return 0;
}

$ gcc -Wall -O -o test test.c

	Output can be saved to file and shown with gnuplot:

$ ./test > file.out
$ gnuplot
gnuplot> plot 'file.out'

	What I see is that the value 128 is good but using
32 (MAX_STEP in the test) gives good enough results (3% diff).
The test shows that:

- last dests have more chance to be selected as starting point
- low value for MAX_STEP causes higher difference in probability
between first and last dests

	Our goal is to select lower value for MAX_STEP that
provides probability difference that is low enough.

Regards

--
Julian Anastasov <ja@xxxxxx>




[Index of Archives]     [Netfitler Users]     [Berkeley Packet Filter]     [LARTC]     [Bugtraq]     [Yosemite Forum]

  Powered by Linux