Не случайное взвешенное распределение

Question

В настоящее время у меня есть система, в которой сервер сообщает всем клиентским приложениям, когда к следующему подключению к серверу между настроенным временем сервера (например, время отклика от 12 до 6 часов).

В текущем алгоритме используется код 10-значного идентификационного номера клиента (довольно распределенный) на количество секунд в окне времени и дает довольно равномерно распределенное, прогнозируемое время для каждого клиента для подключения к серверу. Проблема в том, что клиенты находятся в разных часовых поясах несоразмерно, а определенные временные зоны перекрываются для данного окна, поэтому сетевой эффект заключается в том, что загрузка не распределяется равномерно на сервере. Я хотел бы разработать алгоритм, который я мог бы сконфигурировать с процентом клиентов, которые мы сейчас имеем для каждого часового пояса, и распространить его следующее время соединения между окном, которое приводит к равномерной нагрузке на сервер способом что является предсказуемым (неслучайным).

здесь простое графическое представление:

      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

Разделите проблему на две части: (1) определите, какое распределение вы хотите иметь у каждого набора клиентов; и (2) детерминистически назначать время повторного соединения, соответствующее этому распределению.

Для проблемы (1) рассмотрим двумерный массив чисел, подобно диаграмме, которую вы нарисовали: каждая строка представляет собой часовой пояс, и каждый столбец представляет равный период времени (час, возможно) во время день. Задача, которую вы должны решить, состоит в том, чтобы заполнить сетку такими цифрами, что

• общая сумма каждой строки - количество клиентов в этом часовом поясе;
• для каждой строки, все номера за пределами окна повторного подключения этого часового пояса равны нулю;
• суммы столбцов не превышают заданного максимума (и максимально равномерно сбалансированы).

У этой проблемы есть много решений. Вы можете найти его в симуляции без какой-либо жесткой математики. Напишите программу, которая заполняет сетку так, чтобы клиенты каждого часового пояса распределялись равномерно (то есть, как вы распространяете их сейчас), а затем неоднократно перемещаете клиентов по горизонтали из переполненного времени суток в менее переполненные.

Для задачи (2) требуется функция, которая принимает десятизначный идентификатор и требуемое распределение (то есть одну строку матрицы из задачи 1 выше) и детерминистически создает время повторного соединения. Это легко сделать с помощью линейной интерполяции. Предположим, что требуемое распределение:

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

Сначала найти сумму всей строки, и масштабировать число до диапазона идентификаторов. То есть разделить на сумму и умножить на 10 .

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

Теперь пусть x = десятизначный идентификатор и прочитайте строку слева направо. В каждом поле вычитают значение в этом поле из x. Продолжайте движение до тех пор, пока число в поле больше, чем осталось в x. Возвращают время

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

Обратите внимание, что, как только вы вычислить решение задачи (1), время будет Подсоедините детерминированным до следующий раз, когда вы пересчитывать матрицу. Тогда время повторного соединения каждого будет немного изменяться - но не так много, если матрица не изменится резко.

Answer 2

Как об этом что-то простое:

• Если нагрузка на сервер в порядке, отправить клиенту такое же количество секунд отправлено в прошлый раз.

• Если загрузка на сервере слишком высока, вместо этого отправьте клиенту другое случайное число в окне времени.

В течение нескольких дней все должно разбираться.

(Это предполагает, что вы есть способ измерения количества вы пытаетесь оптимизировать, которая, кажется, не слишком неразумно.)

Answer 3

Почему бы не сгенерировать раз переподключение-окна в GMT на сервере и преобразовать по местному времени клиента, прежде чем отправлять время клиенту?

Answer 4

Вы можете принять во внимание часовой пояс пользователя в дополнение к его идентификатору.

Одним из примеров решения, которое использует это было бы следующее:

Есть 24 часовых поясов. Вычислите, какая относительная нагрузка существует для каждого из часовых поясов. Вы можете сделать это, суммируя общее количество клиентов из каждого часового пояса из ваших статических данных. Теперь у вас есть «взвешенные часовые пояса». Каждый часовой пояс получит долю времени пропорционально его весу.

Например, если у вас есть следующие данные (для простоты, предположим, что есть только три часовых пояса):

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

Тогда вы бы разделить интервал времени размер на 60, и дать каждому из часовой пояс его доля времени: первый часовой пояс будет получать (20/60 * # время), второй получит следующее (30/60 * # время) и т. д.

Как только у вас есть меньшие временные рамки , вы можете сообщить каждому клиенту о своем времени согласно вашей предыдущей функции (например, по модулю), используя меньший интервал в соответствии с тем, что вы рассчитали для своего конкретного часового пояса.

Примечания:

1. Очевидно, что вам потребуется некоторое минимальное значение клиентов NUM для часовых поясов, которые очень мало трафика, но это просто - вы просто изменить исходную таблицу.
2. Это один из примеров «временного разделения», вы можете изменить этот пример по своему усмотрению, например, у вас могут быть взаимные временные рамки для нескольких часовых поясов.

EDIT:

Учитывая пример, который вы добавили к вашему вопросу, вы могли бы применить этот метод следующим образом:

Если я вас правильно понимаю, у вас есть 10 часов, в которых сервер активен , и вы хотите, чтобы нагрузка была более или менее одинаковой для каждого из этих часов. Значение: в каждый из этих часов вы хотели бы, чтобы 10% клиентов получили доступ к серверу. Используя изложенную выше идею, можно разделить пользователей неравномерно, так что для каждого часового пояса есть часы с «большей вероятностью» и часы с «меньшей вероятностью». В вашем примере в группе GMT-4 10%/40% клиентов получат доступ к серверу в первый час: 12 AM-01AM GMT. Можно вычислить нагрузку для каждого из часовых поясов, так что общая нагрузка для сервера в каждый час составляет 10%. Есть много способов сделать это - жадный будет. После этого вы знаете весы для каждого из часовых поясов, и должно быть яснее, как использовать метод разделения времени, описанный выше.

Answer 5

Я бы определить вспомогательный класс для каждого из Часовых поясов вы смотрите на:

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); 
    } 
} 

Вы теперь использовать метод GetStartTime, чтобы получить начальное время для клиента от этой временной зоны. Идея здесь в том, что у нас есть эта таблица hourlyWeights с распределением, которое вы хотите получить за данный часовой пояс, например. [40, 20, 0, 0, 0, 0] означают, что эти клиенты будут обслуживаться только в течение первых 2 часов, и мы хотим, чтобы в течение первого часа было вдвое больше клиентов. Примечание. Я предполагаю, что идентификаторы равномерно распределены между клиентами из заданного часового пояса.

Сложный бит - создать эти классы. Если у вас достаточно стабильная структура клиентов, вы можете вручную разобрать дистрибутивы и поместить их в файл конфигурации. Если он меняет часто, дайте мне знать, и я отправлю код, чтобы понять его динамически.