Distribución ponderada no aleatoria

Question

Actualmente tengo un sistema en el que el servidor indica a todas las aplicaciones cliente cuándo conectarse próximamente al servidor entre una ventana de tiempo configurada por el servidor (por ejemplo, 12 a 6 am, hora del cliente).

El algoritmo actual hace un mod del número de identificación de 10 dígitos del cliente (bastante distribuido) por el número de segundos en la ventana de tiempo y proporciona un tiempo bastante uniformemente distribuido y predecible para que cada cliente se conecte al servidor. El problema ahora es que los clientes se encuentran en diferentes zonas horarias desproporcionadamente, y ciertas zonas horarias se superponen para la ventana dada, por lo que el efecto neto es que la carga no se distribuye uniformemente en el servidor. Lo que me gustaría es diseñar un algoritmo que pueda configurar con un porcentaje de clientes que tenemos actualmente para cada zona horaria, y hacer que distribuya el siguiente tiempo de conexión del cliente entre la ventana que da como resultado una carga uniforme en el servidor de una manera eso es predecible (no aleatorio).

aquí es una sencilla representación gráfica:

      12AM 1AM 2AM 3AM 4AM 5AM 6AM GMT 
GMT -4 40% of the clients ||||||||||||||||||||||||||||||    
GMT -5 10% of the clients  ||||||||||||||||||||||||||||||   
GMT -6 20% of the clients   ||||||||||||||||||||||||||||||  
GMT -7 30% of the clients    |||||||||||||||||||||||||||||| 

Answer 1

Divida el problema en dos partes: (1) determinando qué distribución quiere que tenga cada conjunto de clientes; y (2) asignar de manera determinista tiempos de reconexión que se ajusten a esa distribución.

Para el problema (1), considere una matriz bidimensional de números, muy similar al diagrama que dibujó: cada fila representa una zona horaria y cada columna representa un período de tiempo igual (una hora, quizás) durante El dia. El problema que tiene que resolver es completar la cuadrícula con números tales como

• el total de cada fila es el número de clientes en esa zona horaria;
• para cada fila, todos los números fuera de la ventana de reconexión de la zona horaria son cero;
• las sumas de las columnas no exceden un máximo predeterminado (y están lo más equilibradas posible).

Este tipo de problema tiene muchas soluciones. Puede encontrar uno por simulación sin hacer ninguna matemática difícil. Escriba un programa que llene la cuadrícula para que los clientes de cada zona horaria estén distribuidos uniformemente (es decir, la forma en que los está distribuyendo ahora) y luego mueva a los clientes horizontalmente de horas abarrotadas a menos concurridas.

Para el problema (2), desea una función que tome una identificación de diez dígitos y una distribución deseada (es decir, una fila de la matriz del problema 1 anterior) y deterministicamente produce un tiempo de reconexión. Esto se hace fácilmente por interpolación lineal. Supongamos que la distribución deseada es:

12:00 1:00 2:00 3:00 4:00 5:00 6:00 ... 
    +------+------+------+------+------+------+---- 
    | 0 | 0 | 100 | 70 | 30 | 0 | ... 
    +------+------+------+------+------+------+---- 

En primer lugar encontrar la suma de toda la fila, y la escala de los números hasta el rango de IDs. Es decir, divida por la suma y multiplique por 10 .

12:00 1:00 2:00  3:00  4:00  5:00 6:00 ... 
    +------+------+-----------+-----------+-----------+------+---- 
    | 0 | 0 | 500000000 | 350000000 | 150000000 | 0 | ... 
    +------+------+-----------+-----------+-----------+------+---- 

Ahora deje x = la identificación de diez dígitos, y lea la fila de izquierda a derecha. En cada casilla, reste el valor en esa casilla de x. Continúe hasta que el número en la casilla sea mayor que lo que queda en x. Devolver el tiempo

(start time for this box) + (duration of this box) * x/(number in box) 

Tenga en cuenta que una vez que se calcula la solución al problema (1), los tiempos de reconexión serán determinista hasta la próxima vez que vuelva a calcular la matriz. Entonces, el tiempo de reconexión de todos cambiará un poco, pero no mucho, a menos que la matriz cambie drásticamente.

Answer 2

¿Qué tal esto para algo simple:

• Si la carga en el servidor está bien, enviar al cliente el mismo número de segundos enviado la última vez.

• Si la carga en el servidor es demasiado alta, envíe al cliente otro número aleatorio en la ventana de tiempo.

En unos días las cosas deberían solucionarse por sí solas.

(Esto supone que tiene alguna manera de medir la cantidad que usted está tratando de optimizar, lo que no parece demasiado razonable.)

Answer 3

Por qué no generar sus tiempos de reconexión-ventana en GMT en el servidor y convertir al tiempo local del cliente antes de enviar el tiempo al cliente?

Answer 4

Puede tener en cuenta la zona horaria del usuario además de su ID.

Una solución ejemplo que utiliza este sería el siguiente:

hay 24 zonas de tiempo. Calcule qué carga relativa hay para cada zona horaria. Puede hacer esto sumando la cantidad total de clientes de cada zona horaria desde sus datos estáticos. Ahora tiene "zonas horarias ponderadas". Cada zona horaria obtendrá un tiempo compartido proporcional a su peso.

Por ejemplo, si usted tiene los siguientes datos (por simplicidad, supongamos que sólo hay tres zonas horarias):

Time Zone | Clients num 
------------------------ 
    0  |  20 
    1  |  30 
    2  |  10 

A continuación, hay que dividir su tiempo de intervalo de tamaño de 60, y dar a cada uno de las zonas horarias su parte del tiempo: la primera zona horaria se obtendrá (20/60 * #tiempo), la segunda obtendrá lo siguiente (30/60 * #tiempo) etc.

Una vez que tenga los marcos de tiempo más pequeños , puede decirle a cada cliente de su tiempo de acuerdo con su función anterior (es decir, mod, por ejemplo), usando el intervalo más pequeño de acuerdo con lo que calculó para su zona horaria específica.

Notas:

1. Obviamente, se necesita algún valor mínimo num clientes para las zonas horarias que son muy bajos en el tráfico, pero esto es simple - sólo editar la tabla original.
2. Este es un ejemplo de "división de tiempo", puede modificar este ejemplo a su necesidad, por ejemplo, podría tener marcos de tiempo mutuos para varias zonas horarias.

EDIT:

Teniendo en cuenta el ejemplo que ha añadido a su pregunta, usted podría aplicar este método de la siguiente manera:

Si he entendido bien, usted tiene 10 horas en las que el servidor está activo , y le gustaría que la carga sea más o menos igual para cada una de estas horas. Significado: en cada una de estas horas, le gustaría que el 10% de los clientes accedieran al servidor. Usando la idea explicada anteriormente, es posible dividir a los usuarios de manera no uniforme, de modo que para cada zona horaria, haya horas con "más probabilidad" y horas con "menos probabilidad". En su ejemplo, en el grupo GMT-4, 10%/40% de los clientes tendrán acceso al servidor en la primera hora: 12 AM a 01 GMT GMT. Es posible calcular la carga para cada zona horaria, de modo que la carga total del servidor en cada hora sea del 10%. Hay muchos métodos para hacer esto: uno codicioso lo hará. Una vez que tenga esto, conocerá los pesos para cada una de las zonas horarias, y debería ser más claro cómo usar el método de tiempo compartido descrito anteriormente.

Answer 5

Yo definiría una clase de ayuda para cada una de las zonas horarias que está mirando:

class Timezone 
{ 
    DateTime start; 
    int hourlyWeights[6]; //assuming you have 6 hour long timeslot for every timezone 

    DateTime GetStartTime(long clientId) 
    { 
    long allTicks = 3600*sum(hourlyWeights); 
    long clientTicks = clientId%allTicks; 
    int i = 0; 
    while(clientTicks>hourlyWeights[i]) 
    { 
     clientTicks -= hourlyWeights[i]*3600; 
     i++; 
    } 
    long seconds = clientTicks/hourlyWeights[i]; 
    return start.AddHours(i).AddSeconds(seconds); 
    } 
} 

Ahora utiliza el método GetStartTime para obtener la hora de inicio para un cliente de esta zona horaria. La idea aquí es que tenemos esta tabla de ponderaciones por hora con la distribución que desea obtener para la zona horaria dada, p. [40, 20, 0, 0, 0, 0] significa que estos clientes se atenderán solo durante las primeras 2 horas, y queremos el doble de clientes durante la primera hora. Nota: Supongo que los identificadores se distribuyen de manera uniforme entre los clientes de una zona horaria determinada.

El truco es crear estas clases. Si tiene una estructura de clientes bastante estable, entonces puede averiguar las distribuciones manualmente y ponerlas en el archivo de configuración. Si cambia a menudo, avíseme y publicaré un código para resolverlo dinámicamente.