非隨機加權分配

Question

我目前有一個系統，服務器告訴所有的客戶端應用程序什麼時候在服務器配置的時間窗口（例如12到6客戶端時間）之間連接到服務器。

當前算法通過時間窗口中的秒數對客戶端的10位ID號（公平分佈）進行修改，併爲每個客戶端連接到服務器提供相當平均分佈的可預測時間。現在的問題是，客戶端在不同的時區內是不成比例的，並且給定窗口的某些時區重疊，所以最終的結果是負載未在服務器上均勻分佈。我想要的是設計一種算法，我可以用我們當前擁有的每個時區的一定比例的客戶端進行配置，並讓它在窗口之間分配客戶端的下一個連接時間，從而導致服務器負載均勻這是可預測的（非隨機）。

這裏是一個簡單的圖形表示：

      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），您需要一個採用十位ID和所需分佈（即上述問題1中的一行矩陣）並確定性地生成重新連接時間的函數。這很容易通過線性插值完成。假設所需的分佈是：

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

首先找到整行的總和，並將數字縮放到ID的範圍。也就是說，除以和然後乘以10 。

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

現在讓x =十位數的ID，並從左到右讀取該行。在每個框中，從x中減去該框中的值。繼續前進，直到框中的數字大於x中剩下的數字。返回時間

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

注意，一旦你計算問題的解決方案（1），重新連接時間將是確定性的直到下次重新計算矩陣時間。然後每個人的重新連接時間會稍稍變化 - 但不會太大，除非矩陣變化很大。

Answer 2

這個怎麼樣簡單的東西：

• 如果服務器上的負載是確定的，向客戶端發送相同的秒數你上次發送。

• 如果服務器上的負載過高，請在時間窗口中向客戶端發送一些其他隨機數。

幾天後，事情應該自行解決。

（這裏假設你有測量你試圖優化，這似乎不太合理數量的某種方式。）

Answer 3

爲什麼不能在服務器上生成在格林尼治標準時間的重新連接，窗口時間和轉換在您將時間發送到客戶端之前將客戶端當地時間發送給客戶

Answer 4

除了ID以外，還可以考慮用戶的時區。

有24個時區：使用這將是以下

一個例子的解決方案。計算每個時區的相對負載。您可以通過從靜態數據中總結每個時區的客戶端總數來完成此操作。現在你有「加權時區」。每個時區將獲得與其權重成比例的時間份額。

例如，如果您有以下數據（爲簡單起見，讓我們假設只有三個時區）：

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

那麼你會分配時間間隔大小的60，並給每個其時間份額：第一個時區將得到（20/60 *＃時間），第二個將得到以下（30/60 *＃時間）等。

一旦你有較小的時間段，您可以根據您之前的功能（例如，mod）告訴每個客戶其時間，根據您計算的特定時區的更小間隔。

注：

1. 很顯然，你需要的時區是在交通非常低一些的最低客戶NUM值，但是這很簡單 - 你只需編輯原始表。
2. 這是「時間分割」的一個例子，您可以根據需要修改此示例，例如，您可以爲多個時區分配相互時間範圍。

編輯：

給你添加到你的問題的例子，你可以應用此方法通過以下方式：

如果我理解正確的話，你有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]意味着這些客戶只能在頭兩個小時內提供服務，而且我們希望在第一個小時內客戶數量增加一倍。注意：我假設ID從給定時區的客戶端均勻分佈。

棘手的一點是要創建這些類。如果客戶的結構相當穩定，則可以手動計算分佈並將其放入配置文件中。如果它經常變化，讓我知道，我會張貼一些代碼動態地弄清楚。