時間の経過と共にピーク使用量を平坦化するアルゴリズム？

Question

私は、夜間にデータを送受信することで、3つのタイムゾーンにまたがる多くのデバイスに対応する環境を持っています。これらの装置の分布は、識別番号とモジュロ演算を用いた簡単な計算に基づいて擬似ランダムに決定された。このような計算の結果、夜間の特定の時間帯に必要なリソースよりも多くのリソースを消費する不要な人工的なピークが生成されます。

私たちのプロトコルの一部として、後日にシステムに接続するときにデバイスに指示することができます。

私は一般にピークをよりレベルの高いラインに（一般的にはより高い頻度ではあるが）、または少なくとも正しい方向に押し込むことができるアルゴリズムを探している。 。私は、デバイスの識別番号、現在の時刻、およびデバイスのタイムゾーンを計算を実行するための入力として利用できます。私は、このアプローチが私が望んでいるよりもあまり優雅ではないかもしれないと感じていますが（学習アルゴリズムは悪いことではないかもしれませんが...）、スロットを描画するためのプールを作成するためにいくつかの前向き分析計算を実行することもできます。

（私はC＃を使用して、このアルゴリズムを実装します最終的には、やや少ない関連する。）

Answer 1

ランダム時間の使用に関連するスパイクを避けたい場合は、ハッシュテーブルに使用されるさまざまなハッシュ関数を見てください。 、基本的に

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

あなたのアップデートウィンドウがバケツの適切な数になりたいものは何でも分割：あなたの読書は、件名にWikipediaの記事で開始される可能性があります。 1つのオプションは、3時間* 60分* 60秒= 10800バケットの場合があります。次に、選択したハッシュ関数に対してハッシュテーブルサイズとして使用します。固有の入力はデバイスIDです。選択した時間にGMTを使用することを忘れないでください。お使いのプログラミング言語には、ハッシュ関数が組み込まれているのが一般的ですが、最初から実装したい場合は、記事にいくつかのリンクが必要です。

このアプローチは、より良い均一性プロパティがあるため、ランダムアクセス時間の以前の回答よりも優れています。また、は、アクセスパターンが時々スパイクを呈する可能性があるランダム関数。

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

Answer 2

あなたが接続するために何時間デバイスを伝えることができるので、あなたがランダムまたはmodulused何かを必要とする理由私は見ていないと言います。各デバイスが接続すると、現在割り当てられているデバイスが多くない明日の時間を選択し、その時間にデバイスを割り当てます。デバイスがすべて同じ量のリソースを使用してサービスする場合、些細なグリーディ・アルゴリズムでは完全にスムーズな配信が行われ、現在最も混雑していない時間帯に各デバイスを割り当てます。サーバーがこれらのデバイスだけでなく他の作業を処理している場合は、典型的な負荷プロファイルから始め、そのデバイス負荷をそのデバイスに追加したいと考えています。私は実際にこの「分析的計算」と呼ばず、次の24時間の時間に対する期待負荷のヒストグラムを保存するだけです。

または、デバイスが指示に従わない可能性があります（たとえば、割り当てられた時間にオフラインになり、次にオンになるたびに接続するなど）。明らかに、特定のタイムゾーンのユーザーがすべて朝から同じ時間に作業を開始すると、それは問題のある戦略になります。

Answer 3

デバイスの数をとって、時間間隔をn個の等しいセグメントに分割し、各セグメントをデバイスに割り当て、次に接続するときに接続するタイミングを通知するだけです。

これにより、すべてのケースで最適な均一分布が得られます。

GMTに常時正規化します。タイムゾーンや昼間の節約などについて気になりますか？今すぐあなたがいる時間帯に関係なく今です。

ランダムな分布を追加すると、一様分布が均一になります（ただし、一様分布は一様であり、必ずしも特定のサンプルではありません）。フィードバックメカニズムがない場合に使用されます。あなたがランダムなコンポーネントに接続するときにあなたはある程度まで制御することができるので、すべてが必要ではなく、遠隔的に最適でもありません。

デバイス間のクロックドリフトが懸念される場合は、ランダム性を追加しても、クロックドリフトのランダム性が低下することはなく、さらに最適化されない割り当てにのみ寄与します。

地域ごとにデバイスを安定して配信する場合は、地域ごとのデバイスの比率を計算し、スロットの割り当てを適切に分散します。たとえば、タイムゾーンごとに50/25/25がある場合は、スロットを最初のタイムゾーンに割り当て、次に2つのスロットを残りのタイムゾーンに割り当ててから、繰り返します。