トップノードアルゴリズムは、リソース予約カレンダーを管理するためのアルゴリズムです。このアルゴリズムは2003年に初めて公開され[1]、2009年に改良されました[2]。このアルゴリズムは、リソースが多くのユーザー間で共有される場合に使用されます（例えば、通信リンクの帯域幅や大規模データセンターのディスク容量など）。
このアルゴリズムにより、ユーザーは次のことが可能になります。
- 特定の期間に利用可能なリソースの量を確認する
- 特定の期間に一定量のリソースを予約する
- 以前の予約を削除する、
- カレンダーを前へ進めます (カレンダーは定義された期間をカバーしており、時間の経過とともに前へ進めなければなりません)。
原理
カレンダーは二分木として保存され、葉は基本期間を表します。他のノードは、その子孫ノードすべてによってカバーされる期間を表します。
7時間制カレンダーの例（基本周期は1時間）
予約期間の期間は、「トップノード」の集合によって表されます。この集合は、予約期間を正確にカバーする最小のノード集合です。
バイナリツリーのノードが特定の予約の「トップノード」となるのは、
- その子孫はすべて予約期間内にあり、
- ルート ノードであるか、親ノードの少なくとも 1 つの子孫が予約期間外です。
1:00から5:59までの予約のトップノード
各ノードには次の値が格納されます。
q(ノード) = max(q(左の子), q(右の子))
+ このノードを「トップノード」とするすべての予約の予約済みリソースの合計量
(コードの最適化のため、この合計の 2 つの部分は通常別々に保存されます。)
パフォーマンス
このアルゴリズムの利点は、新しいリソース予約を登録する時間がカレンダーのサイズのみによって決まり、予約の総数には左右されないことです。
暦の基本周期の数を nとします。
特定の予約における「トップノード」の最大数は 2.log n です。
- 特定の期間に利用可能なリソースの量を確認する：O（log n）
- 特定の期間に一定量のリソースを予約する：O（log n）
- 以前の予約を削除するには：O（log n）
- カレンダーを進めるには：O（log n + M.log n）
ここで、Mは追加されたカレンダー期間中にアクティブな予約の数です。
（カレンダー終了後に予約が許可されない場合は 、 M = 0 になります。）
参考文献
- ^ 関連する米国特許（アルゴリズムは2008年からパブリックドメインです）
- ^ 改良されたトップノードアルゴリズム
外部リンク
- （フランス語） Cソースコード
