Algoritmo para aplanar el uso máximo en el tiempo?

Question

Tengo un entorno que sirve a muchos dispositivos distribuidos en 3 zonas horarias al recibir y enviar datos durante las primeras horas de la noche. La distribución de estos dispositivos se determinó pseudoaleatoriamente en función de un número de identificación y un cálculo simple utilizando una operación de módulo. El resultado de tal cálculo crea un pico artificial innecesario que consume más recursos de los que me gustaría durante ciertas horas de la noche.

Como parte de nuestro protocolo puedo indicar a los dispositivos cuándo conectarse a nuestro sistema en las noches siguientes.

Estoy buscando un algoritmo que generalmente pueda distribuir el pico en una línea más nivelada (aunque generalmente más alta en la mayoría de los casos) o al menos un empujón en la dirección correcta, es decir qué tipo de terminología debo emplear para leer . Tengo a mi disposición números de identificación para dispositivos, la hora actual y la zona horaria del dispositivo como entradas para realizar el cálculo. También puedo realizar algunos cálculos analíticos iniciales para crear grupos de los que extraer tragamonedas, aunque creo que este enfoque puede ser menos elegante de lo que estoy esperando (aunque un algoritmo de aprendizaje puede no ser malo ...).

(En última instancia y algo menos relevante que pondrá en práctica este algoritmo usando C#.)

Answer 1

Si desea evitar los picos asociados con el uso de tiempos aleatorios, observe las diversas funciones de hash usadas para hashtables. Su lectura puede comenzar en los artículos de Wikipedia sobre el tema:

http://en.wikipedia.org/wiki/Hash_function

Básicamente, dividir lo que quiere que su ventana de actualización sea en el número apropiado de cubos. Una opción podría ser 3 horas * 60 minutos * 60 segundos = 10800 cubos. Luego utilícelo como su tamaño de tabla hash, para la función de hashing elegida. Su entrada única puede ser la identificación del dispositivo. No te olvides de usar GMT por el tiempo elegido. Su lenguaje de programación de elección probablemente tenga varias funciones hash incorporadas, pero el artículo debería proporcionar algunos enlaces para que pueda comenzar si desea implementar uno desde cero.

Este enfoque es superior a la respuesta anterior de los tiempos de acceso aleatorio, ya que tiene mucho mejores propiedades de regularidad, y asegura que sus patrones de acceso serán de aproximadamente plana, en comparación con la función aleatoria que es probable que a veces los picos de exposición .

He aquí alguna información más específica sobre cómo poner en práctica varias funciones:

http://www.partow.net/programming/hashfunctions/index.html

Answer 2

Usted dice que usted puede decir dispositivos que hora de conectar, así que no veo por qué necesita nada al azar o modulused. Cuando se conecte cada dispositivo, elija una hora de mañana que actualmente no tenga muchos dispositivos asignados y asigne el dispositivo a esa hora. Si todos los dispositivos consumen la misma cantidad de recursos que el servicio, entonces un algoritmo codicioso trivial producirá una distribución completamente uniforme: asigne cada dispositivo a la hora que esté menos congestionada. Si el servidor maneja otro trabajo aparte de estos dispositivos, entonces querrá comenzar con su perfil de carga típico y luego agregar la carga del dispositivo a eso. Realmente no llamaría a esto "cálculos analíticos", simplemente almacenando un histograma de la carga esperada contra el tiempo durante las próximas 24 horas.

¿O tiene el problema de que el dispositivo podría no obedecer las instrucciones (por ejemplo, podría estar desconectado en el momento asignado y luego conectarse cada vez que lo haga)? Obviamente, si sus usuarios en un huso horario en particular todos comienzan a trabajar a la misma hora en la mañana, entonces esa sería una estrategia problemática.

Answer 3

Simplemente tome la cantidad de dispositivos y divida su intervalo de tiempo en n segmentos iguales y asigne cada segmento a un dispositivo, informándoles de cuándo conectarse la próxima vez que se conecte.

Esto le dará una distribución óptimamente uniforme en todos los casos.

Normalice todas las veces a GMT, ¿qué le importa las zonas horarias o el horario de verano o lo que sea? Ahora no importa en qué zona horaria se encuentre.

Agregar una distribución aleatoria puede generar aglomeraciones (una distribución aleatoria uniforme solo es uniforme en el límite, pero no necesariamente para una muestra en particular), y realmente debería ser usado si no hay un mecanismo de retroalimentación. Dado que puedes controlar hasta cierto punto cuando conectan un componente aleatorio no es en absoluto necesario y ni siquiera es remotamente óptimo.

Si le preocupa la deriva del reloj en todos los dispositivos, considere que aunque agregara aleatoriedad, esto no disminuiría la aleatoriedad de la deriva de su reloj de ninguna manera, y solo contribuiría a una asignación aún menos óptima.

Si desea garantizar una distribución estable de dispositivos por región, calcule la proporción de dispositivos por región y distribuya las asignaciones de ranura de forma adecuada.Por ejemplo, si tiene 50/25/25 por zona horaria, respectivamente, asigne ranuras a la primera zona horaria, luego las dos ranuras siguientes a las zonas horarias restantes, luego repita.