指数バックオフ

指数バックオフは、フィードバックを利用して処理速度を段階的に減少させ、許容可能な速度を徐々に見つけるアルゴリズムです。これらのアルゴリズムは、無線ネットワークやコンピュータネットワークをはじめとする幅広いシステムやプロセスで利用されています。

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

指数バックオフアルゴリズムは、悪影響事象に応じて制御対象プロセスの実行速度を低下させる閉ループ制御システムの一種です。例えば、モバイルアプリがサーバーへの接続に失敗した場合、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 ms (これは往復時間の推定値です) であり、T2 秒 (デフォルト値は4 秒）。これにより、再送信間隔は500 ミリ秒、1 秒、2 秒、4 秒、4 秒後4 秒。^{[ 2 ]}

衝突回避

指数バックオフアルゴリズムは、ネットワーク衝突を回避するために使用できます。ポイントツーマルチポイントネットワークまたは統計的時分割多重ネットワークでは、複数の送信者が単一の共有チャネルを介して通信します。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 から $2$ $3$ $-$ $1$ までのランダムな整数です。
さらに失敗した場合は、c番目の試行の失敗後、 $k$ 回目の試行後にフレームを再送信します。51.2 μs、ここで $k$ $は0から2c$ $- 1 まで$ のランダムな整数です。

歴史と理論

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

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

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

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

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

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

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

系

有限の ( N × s ) の場合、現在のK値に対する不安定なチャネルは、 K を十分に大きな値に増加させることで安定させることができ、これをK ( N , s )と呼ぶ。^{[ 11 ]}

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

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

ヒューリスティック 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の例を示すには、ラムの博士論文第6章214ページの表6.3の最下段、またはラム＝クラインロック論文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
m ≥ 4 の場合、 K ( m ) = K ( m − 1)

この例では、K = 200 で、 Nが約 400 の安定したスロット付き ALOHA システムを構築できます。これは、上記の系 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$ スロットとなります。

参考文献

↑ Tanenbaum & Wetherall 2010 、p. 395
↑ Rosenberg et al. RFC3261 – SIP: セッション開始プロトコル。インターネット協会。2002年。
↑ Peterson, Larry L.; Davie, Bruce S. (2022). 「第2章：直接リンク」 .コンピュータネットワーク：システムアプローチ（第6 版）. Morgan Kaufmann Publishers. p. 120. ISBN 978-0-12-818200-0。
↑アブラムソン、ノーマン (1970)。ALOHAシステム - コンピュータ通信のもう一つの代替案(PDF)。1970年秋季合同コンピュータ会議議事録。AFIPS Press。
↑ロバーツ、ローレンス G. (1975 年 4 月) 「スロットとキャプチャの有無による ALOHA パケットシステム」。ACM SIGCOMM Computer Communication Review。5 ( 2): 28–42。doi : 10.1145 / 1024916.1024920。
↑クラインロック、レナード、サイモン S. ラム (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. Bibcode : 1975ITCom..23..410K . doi : 10.1109/TCOM.1975.1092814 . 2023 年2 月 16 日取得.
↑ラムの博士論文第5章114ページの図5-9、または1975年のクラインロック＝ラム論文418ページの図10。
↑ラムの博士論文第5章116ページの図5-10、または1975年のクラインロック＝ラム論文418ページの図11。
1 2 Lam, Simon S.; Kleinrock, Leonard (1975 年 9 月)。「マルチアクセスブロードキャストチャネルにおけるパケットスイッチング: 動的制御手順」 ( PDF)。IEEE Transactions on Communications。COM-23 (9): 891–904。Bibcode : 1975ITCom..23..891L。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日取得。（購入）
↑ Tanenbaum & Wetherall 2010 、p. 285 .

参考文献

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

この記事は、連邦規格1037C（一般調達局）からのパブリックドメイン資料を組み込んでいます。 2022年1月22日にオリジナルからアーカイブされました。

[1] Tanenbaum & Wetherall 2010 、p. 395

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

[3] Peterson, Larry L.; Davie, Bruce S. (2022). 「第2章：直接リンク」 .コンピュータネットワーク：システムアプローチ（第6 版）. Morgan Kaufmann Publishers. p. 120. ISBN 978-0-12-818200-0。

[abramson1-4] アブラムソン、ノーマン (1970)。ALOHAシステム - コンピュータ通信のもう一つの代替案(PDF)。1970年秋季合同コンピュータ会議議事録。AFIPS Press。

[roberts1-5] ロバーツ、ローレンス G. (1975 年 4 月) 「スロットとキャプチャの有無による ALOHA パケットシステム」。ACM SIGCOMM Computer Communication Review。5 ( 2): 28–42。doi : 10.1145 / 1024916.1024920。

[6] クラインロック、レナード、サイモン S. ラム (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. Bibcode : 1975ITCom..23..410K . doi : 10.1109/TCOM.1975.1092814 . 2023 年2 月 16 日取得.

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

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

[LK75-12] 1 2 Lam, Simon S.; Kleinrock, Leonard (1975 年 9 月)。「マルチアクセスブロードキャストチャネルにおけるパケットスイッチング: 動的制御手順」 ( PDF)。IEEE Transactions on Communications。COM-23 (9): 891–904。Bibcode : 1975ITCom..23..891L。doi : 10.1109 / TCOM.1975.1092917。2023年7月16 日取得。

[13] Lam-Kleinrock 論文^{[ 12 ]}の 901-902 ページにあるアルゴリズム 4または Lam の博士論文の第 6 章の 209-210 ページにあるサブセクション 6.7.2 を参照してください。

[IEEE_802_3-14] 「IEEE規格802.3-2015」。IEEE 。 2022年3月20日取得。（購入）

[15] Tanenbaum & Wetherall 2010 、p. 285 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

[ 7 ]

[

[ 9 ]

[ 10 ]

[ 11 ]

[ 13 ]

[ 12 ]

[ 14 ]

[ 15 ]

指数バックオフ