指数バックオフ

指数バックオフは、フィードバックを使用してプロセスのレートを乗法的に下げ、徐々に許容可能なレートを見つけるアルゴリズムです。これらのアルゴリズムは、無線ネットワークやコンピュータネットワークなど、さまざまなシステムやプロセスで使用されています。

指数バックオフアルゴリズム

指数バックオフアルゴリズムは、閉ループ制御システムの一種で、悪影響イベントに応じて制御対象プロセスの速度を低下させます。たとえば、スマートフォンアプリがサーバーに接続できない場合、1 秒後に再試行し、再度失敗した場合は 2 秒後、4 秒後などと試行します。一時停止するたびに、一定量 (この場合は 2) が掛けられます。この場合、悪影響イベントはサーバーに接続できないことです。悪影響イベントの他の例としては、ネットワークトラフィックの衝突、サービスからのエラー応答、速度を下げるための明示的な要求 (バックオフなど) などがあります。

レートの低下は指数関数としてモデル化できます。

t=b^{c}

または

f={\frac {1}{b^{c}}}

ここで、 $t$ はアクション間に適用される時間遅延、 $b$ は乗法係数または基数、 $c$ は観察される有害事象の数、 $fはプロセスの頻度 (または速度) (つまり、単位時間あたりのアクションの数) です$ $。c$ の値は有害事象 $が$ 観察されるたびに増加し、遅延が指数関数的に増加し、したがって速度は反比例します。b $= 2の指数バックオフアルゴリズムは、$ バイナリ指数バックオフアルゴリズムと呼ばれます。

有害事象に応じてレートが削減された場合、通常はその削減レベルが永久に維持されることはありません。回復時間または冷却期間と呼ばれる期間に有害事象が見られない場合、レートは再び増加される可能性があります。レートを再び増加しようとするまでの経過時間自体は、指数バックオフアルゴリズムによって決定されます。通常、レートの回復はバックオフによるレートの低下よりもゆっくりと起こり、レートの振動を回避するために注意深い調整が必要になることがよくあります。 ^[1]正確な回復動作は実装固有であり、さまざまな環境要因によって通知される場合があります。

システムで実際にレート削減を実現するメカニズムは、単純な時間遅延よりも複雑である場合があります。場合によっては、値 $t は$ 特定の時間遅延値ではなく、時間遅延の上限を指すことがあります。指数バックオフという名前は、有害イベント数と遅延時間の間の正確な数値関係ではなく、バックオフの指数関数的増加特性を指します。

レート制限

指数バックオフは、Web サービスなどのコンピュータシステムのレート制限メカニズムの一部として一般的に利用され、リソースへのアクセスの公平な分配を強制し、ネットワークの輻輳を防ぐのに役立ちます。サービスがクライアントにリクエストの送信頻度が高すぎることを通知するたびに、クライアントは、クライアントのリクエストレートが許容可能な均衡に達するまで、事前に決められた係数でレートを減らします。サービスは、クライアントがリクエストを頻繁に送信している場合にリクエストに応答することを拒否することでレート制限を強制し、不正なクライアントが割り当てられたリソースを超えないようにすることができます。

固定レート制限よりも指数バックオフアルゴリズムを使用する利点は、クライアントに事前情報を提供せずにレート制限を動的に達成できることです。たとえば、高負荷やサービス中断などによりリソースが予期せず制限された場合、サービスからのバックオフ要求とエラー応答により、クライアントからの要求レートが自動的に低下します。これにより、サービスに過負荷をかけずに、ある程度の可用性を維持できます。さらに、たとえば、高負荷期間中に電話ネットワーク上の緊急通話のバックオフを減らすなど、個々の重要度に基づいて特定のクライアントにサービス品質を優先させることができます。

アルゴリズムの単純なバージョンでは、メッセージは事前に決められた（ランダムではない）時間だけ遅延されます。たとえば、信頼性の低いトランスポート（ UDPなど）上のSIPプロトコルでは、クライアントはT1秒（通常は500ミリ秒（往復時間の推定値）で、再送のたびに2倍になり、T2秒（デフォルトは4秒）。これにより、再送信間隔は500 ミリ秒、1秒、2秒、4秒、4秒、4 sなど^[2]

衝突回避

指数バックオフアルゴリズムを使用すると、ネットワークの衝突を回避できます。ポイントツーマルチポイントまたは多重化ネットワークでは、複数の送信者が 1 つの共有チャネルを介して通信します。2 人の送信者が同時にメッセージを送信しようとしたり、互いに通信したりする場合、衝突が発生し、メッセージが破損または失われます。各送信者は、同じメッセージを再送信する前にバックオフできます。

決定論的指数バックオフアルゴリズムはこのユースケースには適していません。各送信者が同じ期間バックオフするため、同時に再送が行われ、別の衝突が発生するからです。代わりに、衝突を回避するために、再送間の時間がランダム化され、指数バックオフアルゴリズムによって、可能な遅延値の範囲が設定されます。時間遅延は通常、ネットワーク上の固定長の期間 (またはスライス) であるスロットで測定されます。バイナリ指数バックオフアルゴリズム (つまり、 $b$ $= 2$ ) では、 $c 回の衝突の後、各再送は$ $0$ から $2$ $c$ $- 1$ の間のランダムな数のスロット時間だけ遅延されます。最初の衝突の後、各送信者は 0 または 1 スロット時間待機します。2 回目の衝突の後、送信者は 0 から 3 スロット時間 (両端を含む) の間待機します。3 回目の衝突の後、送信者は 0 から 7 スロット時間 (両端を含む ) の間待機します。再送信の試行回数が増えると、遅延の可能性の数は指数関数的に増加します。これにより衝突の確率は減少しますが、平均遅延は増加します。

指数バックオフは、キャリア検知多重アクセス/衝突回避(CSMA/CA) およびキャリア検知多重アクセス/衝突検出(CSMA/CD) ネットワークでのフレームの再送信時に利用されます。このアルゴリズムは、これらのネットワークでデータを送信するために使用されるチャネルアクセスメソッドの一部です。イーサネットネットワークでは、このアルゴリズムは衝突後の再送信をスケジュールするためによく使用されます。再送信は、スロット時間 (たとえば、512 ビットを送信するのにかかる時間、つまり 512 ビット時間) と再送信の試行回数から算出された時間だけ遅延されます。

例

この例はイーサネットプロトコル^[3]からのもので、送信ホストはフレームを送信しているときに衝突が発生したこと（つまり、別のホストが送信しようとしたこと）を知ることができます。衝突が発生した直後に両方のホストが再送信を試みると、さらに別の衝突が発生し、パターンが永遠に続きます。ホストは、この状況が発生しないように、許容範囲内でランダムな値を選択する必要があります。そのため、指数バックオフアルゴリズムが使用されます。ここで例として使用されている値は51.2μsです。これは、10 Mbit/sイーサネット回線。ただし、実際には、 51.2 μs は任意の正の値に置き換えることができます。

衝突が最初に発生したら、妨害信号を送信して、それ以上のデータが送信されないようにします。
0秒後にフレームを再送信するか、51.2 μs、ランダムに選択。
失敗した場合は、次のいずれかの後にフレームを再送信します。0 秒、51.2μs、102.4 μs、または153.6μs .
それでも失敗する場合は、 $k$ 後にフレームを再送信します。51.2 μs、ここで $kは0から$ $23 - 1$ までのランダムな整数です。
さらなる失敗については、c回目の失敗の後に、 $k 回$ 後にフレームを再送信します。51.2 μs、ここで $kは0から$ $2 c - 1$ までのランダムな整数です。

歴史と理論

AFIPS 1970 で発表された独創的な論文^[4]で、ノーマン・エイブラムソンは、異なる島にいる複数の「ユーザー」が単一の無線チャネル (つまり、単一の周波数) を共有し、時間同期なしでハワイ大学のメインコンピュータにアクセスするというアイデアを発表しました。メインコンピュータの受信機でのパケット衝突は、タイムアウト後に送信者によって検出されたエラーとして処理されます。メインコンピュータから肯定応答を受信しなかった各送信者は、「失われた」パケットを再送信します。エイブラムソンは、共有チャネルに送信されるパケットのシーケンスは、レート $G$ のポアソン過程であると想定しました。レート Gは、送信者への新しいパケット到着レート $S$ とチャネルに再送信されたパケットのレートの合計です。定常状態を想定すると、彼はチャネルのスループットレートが理論上は最大値 1/(2 $e$ ) = 0.184 であることを示しました。 $S=Ge^{-2G}$

ラリー・ロバーツは、各タイムスロットがパケット伝送時間に十分な長さであるタイムスロットALOHAチャネルを検討しました。( TDMAプロトコルを使用する衛星チャネルはタイムスロット化されています。) ラリー・ロバーツは、アブラムソンと同じポアソン過程と定常状態の仮定を使用して、理論上、最大スループット率は1/ $e$ = 0.368であることを示しました。^{[5]ロバーツは}ARPANET研究プロジェクトのプログラムマネージャでした。スロットALOHAのアイデアに触発され、ロバーツはARPANETに衛星リンクを含める新しいARPANET衛星システム(ASS)プロジェクトを開始しました。

アブラムソンと彼の同僚、その他によるシミュレーション結果から、ALOHA チャネルは、スロットの有無にかかわらず不安定で、輻輳崩壊に陥ることがあるということが判明しました。輻輳崩壊までの時間は、新しいパケットの到着率やその他の未知の要因に依存していました。1971 年、ラリーロバーツは、 UCLAのレナードクラインロック教授と彼の博士課程の学生であるサイモンラムに、 ARPANETの衛星システムプロジェクトに参加するよう依頼しました。サイモンラムは、博士論文研究で、スロット付き ALOHA の安定性、パフォーマンス評価、および適応制御に取り組むことになりました。クラインロックと共同執筆した最初の論文は、1972 年 8 月に ASS グループに配布されたARPANET衛星システム (ASS) Note 12 でした。 ^{[6]この論文では、} $K$ スロットの間隔でランダムに選択されたスロットが再送信に使用されました。モデルから得られた新しい結果は、 $Kが増加するとチャネルスループットが増加し、$ $K が$ 無限大に増加するにつれて1/ $e$ に収束するというものです。このモデルはポアソン分布の到着と定常状態の仮定を保持しており、統計的動作と混雑の崩壊を理解することを目的としたものではありません。

安定性と適応型バックオフ

安定性を理解するために、ラムは博士論文の第 5 章でスロット ALOHA の統計的動作を分析するための離散時間マルコフ連鎖モデルを作成しました。 ^{[7]このモデルには、}N、s、pの3 つのパラメータがあります。N はユーザーの総数です。いつでも、各ユーザーはアイドル状態またはブロック状態になることがあります。各ユーザーは、次のタイムスロットで送信するパケットを最大で 1 つ持っています。アイドル状態のユーザーは、確率sで新しいパケットを生成し、次のタイムスロットで直ちに送信します。ブロックされたユーザーは、平均再送間隔を同じに保つために、バックログパケットを確率 p で送信します。2つの再送方法のスループット遅延の結果は、広範なシミュレーションによって比較され、基本的に同じであることがわかりました。^[8]

ラムのモデルは、スロット付きALOHAの安定性の問題に対する数学的に厳密な答えと、任意の安定したシステムのスループット遅延性能を計算するための効率的なアルゴリズムを提供します。ラムのマルコフ連鎖モデルから、以下に示す3つの重要な結果が彼の博士論文の第5章に記載されています（これは、Len Kleinrock教授と共同でIEEE Transactions on Communicationsに掲載されました。^[9]）

ポアソン到着 (つまり、無限のN )を伴うスロット ALOHA は、定常確率分布が存在しないため、本質的に不安定です。 (定常状態に到達することは、Abramson と Roberts のモデルで使用された重要な仮定でした。)
有限のNと有限のKを持つスロット ALOHA の場合、マルコフ連鎖モデルを使用して、特定の入力レート ( N × s ) に対してシステムが安定しているか不安定であるかを判断し、安定している場合は平均パケット遅延とチャネルスループットレートを計算できます。
Kを増やすと、安定したスロットALOHAチャネルで収容できるユーザーの最大数が増加します。^[10]

帰結

有限の（N × s ）に対して、現在のK値に対する不安定なチャネルは、Kを十分に大きな値に増やすことによって安定させることができ、その値をK（N、s ）と呼ぶ。^[11]

適応型バックオフのためのヒューリスティックRCP

ラムはマルコフ決定理論を用いてスロット付きALOHAの最適制御ポリシーを開発したが、これらのポリシーでは、ブロックされたすべてのユーザーがマルコフ連鎖の現在の状態（ブロックされたユーザーの数）を知る必要がある。1973年、ラムは、ユーザーがシステム状態を推定するための複雑なプロトコルを使用する代わりに、各ユーザーが自分のローカル情報、つまりバックログパケットが遭遇した衝突の数を使用する単純なアルゴリズムを作成することを決定した。^[13]上記の系を適用して、ラムは次のクラスの適応型バックオフアルゴリズム（ヒューリスティックRCPと呼ばれる）を発明した。

ヒューリスティックRCPアルゴリズムは、次のステップから構成されます。(1) mは、制御ループのフィードバック情報として、ユーザーでパケットが以前に発生した衝突の数を表します。新しいパケットの場合、K (0)は1に初期化されます。(2)パケットの再送間隔K ( m )は、mが増加するにつれて増加します(上記の系が示唆するようにチャネルが安定するまで)。実装では、K (0)=1の場合、mが増加すると、K ( m )は乗算(または加算)によって増加できます。

観察

数年後にイーサネットで使用されるバイナリ指数バックオフ (BEB) は、ヒューリスティック RCP の特殊なケースです。 $K(m)=2^{m}$

BEB の実装は非常に簡単です。ただし、BEB は 2 を唯一の乗数として使用するため、最適化の柔軟性がなく、多くのアプリケーションには最適ではありません。特に、多数のユーザーを持つシステムの場合、BEB はK ( m ) の増加が遅すぎます。一方、ユーザー数が少ないシステムの場合、システムを安定させるにはK をかなり小さくすれば十分であり、バックオフは必要ありません。

複数の乗数を使用する乗法 RCP の例を示すには、Lam の博士論文の第 6 章の 214 ページの表 6.3 の一番下の行、または Lam-Kleinrock の論文の 902 ページの表 III の一番下の行を参照してください。この例では、

新しいパケットは直ちに送信され、m =0、K (0)=1
前回の衝突が 1 回あるパケットの場合、K (1) = K (0) × 10 = 10 (乗数はK ^* = 10 に直接ジャンプします。これは、この特定のシステム (衛星チャネルのスロット ALOHA) の定常状態での最適なK値であることがわかりました)。
以前に 2 回衝突したパケットの場合、K (2) = K (1) × 10 = 100 (衝突が 1 回増えると、K は10 回増加します)。
K (3) = K (2) × 2 = 200
K ( m )= K ( m −1) （m ≥ 4の場合）

この例では、Nが約 400 の安定したスロット付き ALOHA システムにはK =200 で十分であり、これは上記の系 3 の結果から導き出されます。Kをこれ以上増やす必要はありません。

切り捨て指数バックオフ

アルゴリズムの「切り捨て」バリアントは、 $c$ に制限を導入します。これは、特定の回数増加した後、指数関数が停止することを意味します。 $c$ に制限がない場合、送信者がネットワークサービスの低下などによる悪影響を繰り返し観測すると、送信間の遅延が望ましくないほど長くなる可能性があります。ランダム化されたシステムでは、これが偶然発生する可能性があり、予測できない遅延につながります。 $c$ の無制限の増加による遅延の延長は、指数関数的に可能性が低くなりますが、本当に大きな数の法則により、混雑したネットワークでは事実上避けられません。 $c を$ 制限すると、予想外に長い送信遅延の可能性が減り、一時的な停止後の回復時間が改善されます。

例えば、切り捨てバイナリ指数バックオフアルゴリズムで上限が $i = 10に設定されている場合（$ IEEE 802.3 CSMA/CD標準^[14]の場合）、最大遅延は1023スロット時間、つまり $210 - 1に$ なります。

システムに適切なバックオフ制限を選択するには、衝突確率と遅延のバランスを取る必要があります。上限を上げると、各送信試行での衝突確率が指数関数的に減少します。同時に、制限を増やすと、送信の可能な遅延時間の範囲も指数関数的に増加し、パフォーマンスの決定性が低下し、平均遅延が増加します。システムに最適な制限値は、実装と環境の両方に固有です。^[15]

予想されるバックオフ

バックオフ時間が均一に分布している場合、期待されるバックオフ時間は可能性の平均です。バイナリ指数バックオフアルゴリズムでは、 c回の衝突の後、遅延は $[0, 1, ..., N]$ スロットからランダムに選択されます。ここで、 $N = 2 c - 1$ であり、期待されるバックオフ時間（スロット単位）は

\operatorname {E} (c)={\frac {1}{N+1}}\sum _{i=0}^{N}i={\frac {1}{N+1}}{\frac {N(N+1)}{2}}={\frac {N}{2}}.

たとえば、3 回目 ( $c = 3$ ) の衝突の予想されるバックオフ時間を計算するには、まず最大バックオフ時間Nを計算します。

N=2^{c}-1

N=2^{3}-1=8-1

N=7,

次に、バックオフ時間の可能性の平均を計算します。

\operatorname {E} (c)={\frac {1}{N+1}}\sum _{i=0}^{N}i={\frac {1}{N+1}}{\frac {N(N+1)}{2}}={\frac {N}{2}}={\frac {2^{c}-1}{2}}

。

つまり、この例では $E (3) = 3.5$ スロットとなります。

参照

参考文献

^ タネンバウムとウェザオール、2010、p. 395
^ Rosenberg 他「RFC3261 – SIP: セッション開始プロトコル」インターネット協会。2002 年。
^ ピーターソン、ラリー L.、デイビー、ブルース S. (2022)。「第 2 章: 直接リンク」。コンピュータネットワーク: システムアプローチ (第 6 版)。Morgan Kaufmann Publishers。p. 120。ISBN 978-0-12-818200-0。
^ Abramson, Norman (1970)。ALOHA システム - コンピュータ通信のもう 1 つの代替手段(PDF)。1970 年秋季合同コンピュータ会議議事録。AFIPS プレス。
^ Roberts, Lawrence G. (1975 年 4 月)。「スロットとキャプチャの 有無による ALOHA パケットシステム」。コンピュータ通信レビュー。5 (2): 28–42。doi : 10.1145 /1024916.1024920。
^ Kleinrock, Leonard; Simon S. Lam (1972 年 8 月)。再送信遅延分布の影響を含む ARPANET 衛星システムモデルの解析結果(PDF) (技術レポート)。ARPA ネットワーク情報センター、スタンフォード研究所、カリフォルニア州メンロパーク。ASS ノート 12 (NIC 11294)。
^ Lam, Simon S. (1974 年 3 月)。「コンピュータネットワークにおける衛星通信への応用を伴うマルチアクセスブロードキャストチャネルでのパケット交換」、博士論文、306 ページ (論文)。UCLA-ENG-7429 (ARPA)、UCLA 工学応用科学学部。
^ ラム博士論文第5章100ページの図5-1
^ Kleinrock, Leonard; Lam S., Simon (1975 年 4 月). 「マルチアクセスブロードキャストチャネルでのパケット交換: パフォーマンス評価」(PDF) . IEEE Transactions on Communications . COM-23 (4): 410–423. doi :10.1109/TCOM.1975.1092814 . 2023 年2 月 16 日閲覧。
^ ラム博士の博士論文第5章114ページの図5-9、または1975年のクラインロック-ラム論文418ページの図10。
^ ラム博士の博士論文第5章116ページの図5-10、または1975年のクラインロック-ラム論文418ページの図11。
^ Lam, Simon S.; Kleinrock, Leonard (1975 年 9 月). 「マルチアクセスブロードキャストチャネルでのパケット交換: 動的制御手順」(PDF) . IEEE Transactions on Communications . COM-23 (9): 891–904. doi :10.1109/TCOM.1975.1092917 . 2023 年7 月 16 日に閲覧。
^ Lam-Kleinrock論文^[12]の901-902ページのアルゴリズム4 、またはLamの博士論文の第6章の209-210ページのサブセクション6.7.2を参照。
^ 「IEEE 規格 802.3-2015」。IEEE 。 2022年3月20日閲覧。（購入）
^ タネンバウムとウェザオール、2010、p. 285

文献

Tanenbaum, Andrew; Wetherall, David (2010)。コンピュータネットワーク(第 5 版)。ピアソン。ISBN 978-0132126953。

この記事には、連邦規格 1037Cのパブリックドメインマテリアルが組み込まれています。一般調達局。2022 年 1 月 22 日時点のオリジナルよりアーカイブ。

[1] タネンバウムとウェザオール、2010、p. 395

[sip-2] Rosenberg 他「RFC3261 – SIP: セッション開始プロトコル」インターネット協会。2002 年。

[3] ピーターソン、ラリー L.、デイビー、ブルース S. (2022)。「第 2 章: 直接リンク」。コンピュータネットワーク: システムアプローチ (第 6 版)。Morgan Kaufmann Publishers。p. 120。ISBN 978-0-12-818200-0。

[abramson1-4] Abramson, Norman (1970)。ALOHA システム - コンピュータ通信のもう 1 つの代替手段(PDF)。1970 年秋季合同コンピュータ会議議事録。AFIPS プレス。

[roberts1-5] ^ Roberts, Lawrence G. (1975 年 4 月)。「スロットとキャプチャの 有無による ALOHA パケットシステム」。コンピュータ通信レビュー。5 (2): 28–42。doi : 10.1145 /1024916.1024920。

[6] Kleinrock, Leonard; Simon S. Lam (1972 年 8 月)。再送信遅延分布の影響を含む ARPANET 衛星システムモデルの解析結果(PDF) (技術レポート)。ARPA ネットワーク情報センター、スタンフォード研究所、カリフォルニア州メンロパーク。ASS ノート 12 (NIC 11294)。

[Lam74-7] Lam, Simon S. (1974 年 3 月)。「コンピュータネットワークにおける衛星通信への応用を伴うマルチアクセスブロードキャストチャネルでのパケット交換」、博士論文、306 ページ (論文)。UCLA-ENG-7429 (ARPA)、UCLA 工学応用科学学部。

[8] ラム博士論文第5章100ページの図5-1

[KL75-9] Kleinrock, Leonard; Lam S., Simon (1975 年 4 月). 「マルチアクセスブロードキャストチャネルでのパケット交換: パフォーマンス評価」(PDF) . IEEE Transactions on Communications . COM-23 (4): 410–423. doi :10.1109/TCOM.1975.1092814 . 2023 年2 月 16 日閲覧。

[10] ラム博士の博士論文第5章114ページの図5-9、または1975年のクラインロック-ラム論文418ページの図10。