バックプレッシャールーティング

数学的確率論の一分野である待ち行列理論において、バックプレッシャールーティングアルゴリズムは、最大のネットワークスループットを実現する待ち行列ネットワークの周囲にトラフィックを誘導する方法であり、^[1]リャプノフドリフトの概念を使用して確立されています。バックプレッシャールーティングは、各ジョブがネットワーク内の複数のサービスノードを訪問できる状況を考慮しています。これは、各ジョブが単一のサービスノードのみを訪問する最大重みスケジューリングの拡張です。

バックプレッシャールーティングは、輻輳勾配を利用してマルチホップネットワーク上でトラフィックを動的にルーティングするアルゴリズムです。このアルゴリズムは、センサーネットワーク、モバイルアドホックネットワーク（MANETS）、無線と有線のコンポーネントを含む異種ネットワークなどの無線通信ネットワークに適用できます。^{[2] [3]}

バックプレッシャーの原理は、製品組み立てシステムや処理ネットワークの研究など、他の分野にも適用できます。^[4] この記事では、複数のデータ ストリームからのパケットが到着し、適切な宛先に配信する必要がある通信ネットワークに焦点を当てています。バックプレッシャー アルゴリズムはスロット時間で動作します。タイム スロットごとに、隣接するノード間の差分バックログを最大化する方向にデータをルーティングしようとします。これは、水が圧力勾配を介してパイプ ネットワークを流れるのと似ています。ただし、バックプレッシャー アルゴリズムは、マルチコモディティ ネットワーク (異なるパケットが異なる宛先を持つ可能性がある) や、一連の (おそらく時間によって変化する) オプションから送信速度を選択できるネットワークに適用できます。バックプレッシャー アルゴリズムの魅力的な機能は次のとおりです。(i) ネットワーク スループットが最大化される、(ii) 時間によって変化するネットワーク条件に対して堅牢であることが証明されている、(iii) トラフィック到着率やチャネル状態確率を知らなくても実装できる。ただし、このアルゴリズムは大きな遅延を引き起こす可能性があり、干渉のあるネットワークでは正確に実装するのが難しい場合があります。遅延を減らし、実装を簡素化するバックプレッシャーの変更については、以下の「遅延の改善」と「分散バックプレッシャー」で説明します。

バックプレッシャー ルーティングは主に理論的な文脈で研究されてきました。実際には、アドホック無線ネットワークでは、最短経路計算やネットワーク フラッディングに基づく代替ルーティング メソッドが実装されるのが一般的です 。たとえば、アドホック オンデマンド距離ベクトル ルーティング(AODV)、 地理ルーティング、極度に好都合なルーティング(ExOR) などです。しかし、バックプレッシャーの数学的最適性の特性により、南カリフォルニア大学とノースカロライナ州立大学の無線テストベッドでバックプレッシャーの使用が最近実験的に実証されました。^{[5] [6] [7]}

オリジナルのバックプレッシャー アルゴリズムは、Tassiulas と Ephremides によって開発されました。^[2]彼らは、ランダムなパケット到着と固定のリンク選択オプション セットを備えたマルチホップパケット無線ネットワークを考慮しました。彼らのアルゴリズムは、最大重みリンク選択ステージと差分バックログ ルーティングステージで構成されていました。マルチコモディティ ネットワーク フローを計算するために設計されたバックプレッシャーに関連するアルゴリズムは、Awerbuch と Leighton によって開発されました。^[8] バックプレッシャー アルゴリズムは、後に Neely、Modiano、および Rohrs によって拡張され、モバイル ネットワークのスケジューリングを処理します。^{[9]バックプレッシャーは、} Lyapunov ドリフト の理論を介して数学的に分析され、フロー制御メカニズムと組み合わせて使用​​​​してネットワーク ユーティリティの最大化を提供できます。^{[10] [11] [3] [12] [13]} （ユーティリティ最適化とペナルティ最小化を伴うバックプレッシャーも参照）。

バックプレッシャー ルーティングは、ネットワーク内の 1 つのタイムスロットから次のタイムスロットまでのキュー バックログの二乗の合計を (おおよそ) 最小化する決定を行うように設計されています。この手法の正確な数学的展開については、後のセクションで説明します。このセクションでは、一般的なネットワーク モデルと、このモデルに関するバックプレッシャー ルーティングの動作について説明します。

N個のノードを持つマルチホップ ネットワークを考えてみましょう( N = 6の例については、図 1 を参照 )。ネットワークは、スロット時間 で動作します。各スロットで、新しいデータがネットワークに到着し、すべてのデータを適切な宛先に届けるために、ルーティングと送信スケジュールの決定が行われます。ノード宛てのデータを商品 c データと呼ぶことにします。各ノードのデータは、その商品に従って格納されます。および について、をノードnの商品cデータの現在の量 (キュー バックログとも呼ばれる) とします。ノード内のキュー バックログのクローズアップを図 2 に示します。 の単位は、問題のコンテキストによって異なります。たとえば、バックログは整数単位のパケット を取ることができ、これは、データが固定長パケットに分割されている場合に便利です。あるいは、実数値単位のビットを取ることもできます。すべてのタイムスロットtおよびすべてのタイムスロットについて、であると想定されます。これは、どのノードも自分宛てのデータを保存しないためです。あるノードから別のノードに送信されるデータは、最初のノードのキューから削除され、2 番目のノードのキューに追加されます。宛先に送信されたデータは、ネットワークから削除されます。データはネットワークに外部から到着することもあり、スロットtでノードnに到着し、最終的にノードcに配信される必要がある新しいデータの量として定義されます。 ${\displaystyle t\in \{0,1,2,\ldots \}}$${\displaystyle c\in \{1,\dots ,N\}}$${\displaystyle n\in \{1,\ldots ,N\}}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle Q_{n}^{(c)}(t)}$${\displaystyle Q_{n}^{(c)}(t)}$${\displaystyle Q_{c}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle A_{n}^{(c)}(t)}$

をスロットtのリンク ( a , b )上でネットワークが使用する伝送速度とし、これは現在のスロットでノードaからノードbに転送できるデータ量を表します。を伝送速度マトリックスとします。これらの伝送速度は、時間によって変化する可能性のあるオプションのセットから選択する必要があります。具体的には、ネットワークには時間によって変化するチャネルとノードの移動性があり、これがスロットごとに伝送機能に影響を与える可能性があります。これをモデル化するために、S ( t ) がネットワークのトポロジ状態を表すものとし、これは伝送に影響を与えるスロットtのネットワークの特性を捉えます。 をトポロジ状態S ( t )で使用できる伝送速度マトリックス オプションのセットを表すものとします。スロットtごとに、ネットワーク コントローラはS ( t ) を観察し、セット 内の伝送速度を選択します。各スロットtでどのマトリックスを選択するかについては、次のサブセクションで説明します。 ${\displaystyle \mu_{ab}(t)}$${\displaystyle (\mu_{ab}(t))}$${\displaystyle \Gamma_{S(t)}}$${\displaystyle (\mu_{ab}(t))}$${\displaystyle \Gamma_{S(t)}}$${\displaystyle (\mu_{ab}(t))}$

この時間変動ネットワークモデルは、スロットtごとの伝送速度がチャネル状態行列と電力割り当て行列の一般関数によって決定されるケースのために最初に開発されました。^[9] このモデルは、サーバー割り当て、サブバンド選択、コーディングタイプなどの他の制御決定によって速度が決定される場合にも使用できます。サポート可能な伝送速度が既知であり、伝送エラーがないことを前提としています。バックプレッシャールーティングの拡張された定式化は、マルチレシーバーダイバーシティを介してワイヤレスブロードキャストの利点を活用するネットワークなど、確率的なチャネルエラーのあるネットワークに使用できます。 [ ^1]

バックプレッシャーコントローラはスロットtごとにS ( t )を観察し、次の3つのステップを実行します。

• まず、各リンク（a、b）ごとに、使用する最適な商品を選択します。 ${\displaystyle c_{ab}^{opt}(t)}$
• 次に、どのマトリックスを使用するかを決定します。${\displaystyle (\mu_{ab}(t))}$${\displaystyle \Gamma_{S(t)}}$
• 最後に、リンク ( a、b )を介して送信する商品の量を決定します(最大 ですが、場合によってはそれより少なくなる可能性もあります)。${\displaystyle c_{ab}^{opt}(t)}$${\displaystyle \mu_{ab}(t)}$

各ノードa は、自身のキューのバックログと現在の隣接ノードのバックログを監視します。ノードaの現在の隣接ノードは、現在のスロットで非ゼロの送信速度を選択できるノードbです。したがって、隣接ノードはセット によって決定されます。極端な場合、ノードはN  − 1 個の他のすべてのノードを隣接ノードとして持つことができます。ただし、特定の地理的距離を超えて離れているノード間の送信、または伝播信号強度が特定のしきい値を下回るノード間の送信を排除するセットを使用するのが一般的です。したがって、隣接ノードの数はN  − 1 よりはるかに少なくなるのが一般的です。図 1 の例では、リンク接続による隣接ノードを示しており、ノード 5 には隣接ノード 4 と 6 があります。この例は、隣接ノード間の対称関係 (つまり、5 が 4 の隣接ノードである場合、4 は 5 の隣接ノードである) を示していますが、一般にそうである必要はありません。 ${\displaystyle \mu_{ab}(t)}$${\displaystyle \Gamma_{S(t)}}$${\displaystyle \Gamma_{S(t)}}$

特定のノードの隣接ノードのセットによって、現在のスロットでの送信に使用できる送信リンクのセットが決まります。各送信リンク ( a、b ) について、最適な商品は、 次の差分バックログ量を最大化する商品として定義されます。 ${\displaystyle c_{ab}^{opt}(t)}$${\displaystyle c\in \{1,\ldots ,N\}}$

${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)}$

最適な商品を選択する際に同点になった場合は、恣意的に破棄されます。

図 2 に例を示します。この例では、各キューには現在、赤、緑、 青の 3 つの商品のみがあり 、これらはパケットの整数単位で測定されていると想定しています。有向リンク (1,2) に注目すると、差分バックログは次のようになります。

${\displaystyle Q_{1}^{({\text{red}})}(t)-Q_{2}^{({\text{red}})}(t)=1}$

${\displaystyle Q_{1}^{({\text{green}})}(t)-Q_{2}^{({\text{green}})}(t)=2}$

${\displaystyle Q_{1}^{({\text{blue}})}(t)-Q_{2}^{({\text{blue}})}(t)=-1}$

したがって、スロットtのリンク(1,2)を介して送信する最適な商品は緑の商品です。一方、スロットtの逆リンク(2,1)を介して送信する最適な商品は青の商品です。

各リンク（ a、b ）の最適な商品が決定されると、ネットワークコントローラは次の重みを計算します。 ${\displaystyle W_{ab}(t)}$

${\displaystyle W_{ab}(t)=\max \left[Q_{a}^{(c_{ab}^{\mathrm {opt} }(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t),0\right]}$

重みは、リンク ( a、b )の最適な商品に関連付けられた差分バックログの値であり、最大値は 0 です。次に、コントローラーは、次の最大重み問題の解決策として伝送速度を選択します (同点の場合は任意に決定)。 ${\displaystyle W_{ab}(t)}$

${\displaystyle {\text{(式 1)}}\qquad {\text{最大化: }}\sum _{a=1}^{N}\sum _{b=1}^{N}\mu _{ab}(t)W_{ab}(t)}$

${\displaystyle {\text{(式 2)}}\qquad {\text{ただし: }}(\mu _{ab}(t))\in \Gamma _{S(t)}}$

最大重み決定の例として、現在のスロットtで、6 ノード ネットワークの各リンクの差分バックログによって、次のリンク重みが決まるものとします。 ${\displaystyle W_{ab}(t)}$

${\displaystyle (W_{ab}(t))=\left[{\begin{array}{cccccc}0&2&1&1&6&0\\1&0&1&2&5&6\\0&7&0&0&0&0\\1&0&1&0&0&0\\1&0&7&5&0&0\\0&0&0&0&5&0\end{array}}\right]}$

セットには、数え切れないほど無限の数の伝送速度マトリックスが含まれる可能性がありますが、簡単にするために、現在のトポロジ状態には 4 つの選択肢のみがあると仮定します。 ${\displaystyle \Gamma_{S(t)}}$

${\displaystyle \Gamma _{S(t)}=\{{\boldsymbol {\mu }}_{a},{\boldsymbol {\mu }}_{b},{\boldsymbol {\mu }}_{c},{\boldsymbol {\mu }}_{d}\}}$

現在のトポロジ状態S ( t )における4つの可能な伝送速度の選択肢の図。オプション(a)は、伝送速度で単一のリンク(1,5)をアクティブにします。他のすべてのオプションは2つのリンクを使用し、アクティブ化された各リンクの伝送速度は1です。 ${\displaystyle \mu_{15}=2}$

これら 4 つの可能性は、次のマトリックス形式で表されます。

${\displaystyle {\boldsymbol {\mu }}_{a}=\left[{\begin{array}{cccccc}0&0&0&0&2&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right],\quad {\boldsymbol {\mu }}_{b}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\0&0&1&0&0&0\\0&0&0&0&0&0\\0&0&0&0&1&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right]}$

${\displaystyle {\boldsymbol {\mu }}_{c}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\1&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&1&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right],\quad {\boldsymbol {\mu }}_{d}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\0&0&0&0&0&0\\0&1&0&0&0&0\\0&0&0&0&0&0\\0&0&0&1&0&0\\0&0&0&0&0&0\end{array}}\right]}$

いずれの場合も、ノード 6 は送信も受信もできないことに注意してください。これは、ノード 6 が現在通信範囲外にあるために発生する可能性があります。4 つの可能性のそれぞれに対するレートの加重合計は次のとおりです。

• 選択肢（a）：.${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=12}$
• 選択肢（b）：.${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=1}$
• 選択肢（c）：.${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=1}$
• 選択肢（d）：.${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=12}$

最大重みが 12 で同点の場合、ネットワーク コントローラは、オプションまたは オプションのいずれかを選択して、同点を任意に解決できます。 ${\displaystyle {\boldsymbol {\mu }}_{a}}$${\displaystyle {\boldsymbol {\mu }}_{d}}$

ここで、各リンクの最適な商品 が決定され、伝送速度も決定されているものとします。特定のリンク ( a、b ) 上の最適な商品の差分バックログが負の場合、現在のスロットではこのリンクを介してデータは転送されません。それ以外の場合、ネットワークはこのリンクを介して商品データの単位を送信することを提案します。これは、各リンク ( a、b ) および各商品cのルーティング変数を 定義することによって行われます。ここで、 ${\displaystyle c_{ab}^{opt}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle \mu _{ab}(t)}$${\displaystyle c_{ab}^{\mathrm {opt} }(t)}$ ${\displaystyle \mu _{ab}^{(c)}(t)}$

${\displaystyle \mu _{ab}^{(c)}(t)={\begin{cases}\mu _{ab}(t)&{\text{ if }}c=c_{ab}^{opt}(t){\text{ and }}Q_{a}^{(c_{ab}^{opt}(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t)\geq 0\\0&{\text{ otherwise}}\end{cases}}}$

の値は、スロットtのリンク ( a、b ) を介して商品c のデータに提供される伝送速度を表します。ただし、ノードには、すべての送信リンクで提供される速度での伝送をサポートするのに十分な特定の商品がない場合があります。これは、次の場合に、ノードnと商品cのスロットtで発生します。 ${\displaystyle \mu _{ab}^{(c)}(t)}$

${\displaystyle Q_{n}^{(c)}(t)<\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)}$

この場合、すべてのデータが送信され、提供されたレートの未使用部分を埋めるためにヌル データが使用され、実際のデータとヌル データが対応する送信リンクに任意に割り当てられます (提供されたレートに従って)。これは、キュー アンダーフロー状況と呼ばれます。このようなアンダーフローは、ネットワークのスループットや安定性の特性には影響しません。直感的に言えば、これは、送信ノードのバックログの量が少ない場合にのみアンダーフローが発生するためであり、つまり、ノードが不安定になる危険はありません。 ${\displaystyle Q_{n}^{(c)}(t)}$

バックプレッシャー アルゴリズムは、事前に指定されたパスを使用しません。パスは動的に学習され、パケットごとに異なる場合があります。特にシステムの負荷が軽く、データを宛先にプッシュする圧力が十分でない場合は、遅延が非常に大きくなる可能性があります。たとえば、1 つのパケットがネットワークに入り、他のパケットは入らないとします。このパケットはネットワークをループ状に歩き、圧力勾配が形成されないため宛先に到達しない可能性があります。これは、バックプレッシャーのスループットの最適性または安定性の特性と矛盾しません。ネットワークには一度に最大 1 つのパケットしかなく、したがって自明に安定しているからです (到着率と同じ 0 の配信率を達成)。

事前に指定されたパスのセットにバックプレッシャーを実装することも可能です。これにより、容量領域が制限される可能性がありますが、順序どおりの配信と遅延が改善される可能性があります。容量領域に影響を与えずに遅延を改善する別の方法は、 リンクの重みを望ましい方向に偏らせる拡張バージョンを使用することです。 ^[9] このような偏りのシミュレーションでは、遅延が大幅に改善されました。^{[1] [3]} バックプレッシャーは、キューで先入れ先出し ( FIFO ) サービスを必要としないことに注意してください。後入れ先出し ( LIFO ) サービスは、スループットに影響を与えることなく、大部分のパケットの遅延を大幅に改善できることが観察されています。 ^{[7] [14]}

伝送速度が選択されると、ルーティング決定変数は 単純な分散方式で計算でき、各ノードは自身と近隣ノード間のキューバックログの差のみを知る必要があることに注意してください 。ただし、伝送速度の選択には、式 (1) ～ (2) の最大重み問題の解決が必要です。チャネルが直交している特殊なケースでは、アルゴリズムは自然な分散実装を持ち、各ノードでの個別の決定に簡略化されます。ただし、最大重み問題は、チャネル間干渉のあるネットワークの集中制御問題です。集中方式でも解決が非常に難しい場合もあります。 ${\displaystyle (\mu _{ab}(t))}$${\displaystyle \mu _{ab}^{(c)}(t)}$

信号対雑音プラス干渉比 (SINR) によって決定されるリンク レートを持つ干渉ネットワークの分散アプローチは、ランダム化を使用して実行できます。^[9] 各ノードは、すべてのスロットt を送信することをランダムに決定します(現在送信するパケットがない場合は、「ヌル」パケットを送信します)。実際の送信レートとそれに対応する実際の送信パケットは、2 段階のハンドシェイクによって決定されます。最初のステップでは、ランダムに選択された送信ノードが、実際の送信の強度に比例した信号強度でパイロット信号を送信します。2 番目のステップでは、すべての潜在的な受信ノードが結果として生じる干渉を測定し、その情報を送信機に送り返します。すべての発信リンク ( n、b ) の SINR レベルはすべてのノードnに通知され、各ノードn はこの情報に基づいて変数と変数を決定できます。結果として得られるスループットは必ずしも最適ではありません。ただし、ランダム送信プロセスは、チャネル状態プロセスの一部と見なすことができます (アンダーフローの場合はヌル パケットが送信され、チャネル状態プロセスが過去の決定に依存しないことを条件とします)。したがって、この分散実装の結果のスループットは、このようなランダム送信を使用するすべてのルーティングおよびスケジューリング アルゴリズムのクラスで最適です。 ${\displaystyle \mu _{nb}(t)}$${\displaystyle (\mu _{nb}^{(c)}(t))}$

代替の分散実装は、大まかに 2 つのクラスに分類できます。最初のクラスのアルゴリズムは、最大重み問題に対する定数乗法係数近似を考慮し、定数係数スループット結果を生成します。2 番目のクラスのアルゴリズムは、最大重み問題のソリューションを時間の経過とともに更新することに基づいて、最大重み問題に対する加法近似を考慮します。この 2 番目のクラスのアルゴリズムは、適切な仮定の下で最大スループットを達成できることが証明されていますが、静的なチャネル条件とより長い (多くの場合、非多項式) 収束時間を必要とするようです。^{[15] [4] [13]}加法近似は、古いキュー バックログ情報を使用して実装された場合、バックプレッシャーの最適性を証明するのに役立つことがよくあります (Neely テキストの演習 4.10 を参照)。^[13]

このセクションでは、あるスロットから次のスロットまでのキューバックログの二乗和の変化の境界を貪欲に最小化する結果としてバックプレッシャーアルゴリズムがどのように発生するかを示します。^{[9] [3]}

上のセクションで説明したように、N個のノードを持つマルチホップ ネットワークを考えてみましょう。スロットtごとに、ネットワーク コントローラはトポロジ状態S ( t ) を観察し、次の制約に従って伝送速度とルーティング変数 を選択します。 ${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 3)}}\qquad (\mu _{ab}(t))\in \Gamma _{S(t)}}$

${\displaystyle {\text{(Eq. 4)}}\qquad 0\leq \mu _{ab}^{(c)}(t)\qquad \forall a,b,c,\forall t}$

${\displaystyle {\text{(Eq. 5)}}\qquad \sum _{c=1}^{N}\mu _{ab}^{(c)}(t)\leq \mu _{ab}(t)\qquad \forall (a,b),\forall t}$

これらのルーティング変数が決定されると、送信が行われ（必要に応じてアイドル フィルを使用）、結果として得られるキュー バックログは次の条件を満たします。

${\displaystyle {\text{(Eq. 6)}}\qquad Q_{n}^{(c)}(t+1)\leq \max \left[Q_{n}^{(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{(c)}(t),0\right]+\sum _{a=1}^{N}\mu _{an}^{(c)}(t)+A_{n}^{(c)}(t)}$

ここで、 は、スロットtでノードnに外生的に到着する新しい商品c データのランダムな量であり、 は、スロットtのリンク ( n、b ) 上の商品cトラフィックに割り当てられた送信速度です。は、スロットtのリンク ( a、b ) で実際に送信される商品cデータの量よりも大きい場合があることに注意してください。 これは、ノードnに十分なバックログがない可能性があるためです。 同じ理由で、式 (6) は、等式ではなく不等式です。 は、 スロットtでノードnに実際に内生的に到着する商品cよりも大きい場合があるためです。 式 (6) の重要な特徴は、決定変数がキューのバックログとは無関係に選択された場合でも、この式が成り立つことです。 ${\displaystyle A_{n}^{(c)}(t)}$${\displaystyle \mu _{nb}^{(c)}(t)}$${\displaystyle \mu _{nb}^{(c)}(t)}$${\displaystyle \sum _{a=1}^{N}\mu _{an}^{(c)}(t)}$${\displaystyle \mu _{ab}^{(c)}(t)}$

すべてのスロットtおよびすべての について、キューには自分自身宛てのデータは保存されないため、であると想定されます。 ${\displaystyle Q_{c}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$

を現在のキューバックログの行列として定義します。次の非負関数を定義します。これはLyapunov 関数と呼ばれます。 ${\displaystyle {\boldsymbol {Q}}(t)=(Q_{n}^{(c)}(t))}$

${\displaystyle L(t)={\frac {1}{2}}\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)^{2}}$

これは、キューのバックログの二乗の合計です (後の分析の便宜上、 1/2 を掛けています)。上記の合計は、すべてのn、 cについて合計することと同じです。これは、すべてのおよびすべてのスロット${\displaystyle n\neq c}$${\displaystyle Q_{c}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$tについてとなるためです。

条件付きリアプノフドリフトは 次のように定義されます。 ${\displaystyle \Delta (t)}$

${\displaystyle \Delta (t)=E\left[L(t+1)-L(t)\mid {\boldsymbol {Q}}(t)\right]}$

次の不等式がすべての、、に対して成り立つことに注意してください。 ${\displaystyle q\geq 0}$${\displaystyle a\geq 0}$${\displaystyle b\geq 0}$

${\displaystyle (\max[q-b,0]+a)^{2}\leq q^{2}+b^{2}+a^{2}+2q(a-b)}$

キュー更新方程式（式（6））を2乗し、上記の不等式を使用することで、すべてのスロットt とに対して、送信およびルーティング変数を選択するための任意のアルゴリズムの下で、およびであることを示すことは難しくありません。^[3]${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 7)}}\qquad \Delta (t)\leq B+\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)E\left[\lambda _{n}^{(c)}(t)+\sum _{a=1}^{N}\mu _{an}^{(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)|{\boldsymbol {Q}}(t)\right]}$

ここで、B は、到着の 2 番目のモーメントと伝送速度の最大可能な 2 番目のモーメントに依存する有限定数です。

バックプレッシャーアルゴリズムは、すべてのスロットtでおよび S ( t )を観察し、ドリフト境界式(7)の右辺を最小化するように選択するように設計されています。Bは定数であり、は定数であるため、これ は次のものを最大化することになります。 ${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$${\displaystyle \lambda _{n}^{(c)}}$

${\displaystyle E\left[\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)\left[\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)-\sum _{a=1}^{N}\mu _{an}^{(c)}(t)\right]|{\boldsymbol {Q}}(t)\right]}$

ここで、最大化決定を明らかにするために、有限和が期待値に押し込まれている。期待値を機会主義的に最大化する原理により、上記の期待値は、その内部の関数を最大化することによって最大化される（観測された、が与えられた場合）。したがって、式 （3）-（5）の制約に従って、および を選択して、以下を最大化します。${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle S(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle \sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)\left[\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)-\sum _{a=1}^{N}\mu _{an}^{(c)}(t)\right]}$

どのような決定が上記を最大化するかはすぐには分かりません。これは合計を入れ替えることで明らかにすることができます。実際、上記の式は以下の式と同じです。

${\displaystyle \sum _{a=1}^{N}\sum _{b=1}^{N}\sum _{c=1}^{N}\mu _{ab}^{(c)}(t)[Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)]}$

重みは、ノードaとb間の商品cの現在の差分バックログと呼ばれます。考え方は、重みが差分バックログである上記の加重合計を最大化するように決定変数を選択することです。直感的には、これは差分バックログが大きい方向に大きなレートを割り当てることを意味します。 ${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

明らかに、 の場合はいつでもを選択する必要があります。さらに、特定のリンク が与えられている場合、式 (3) ～ (5) に従って、最適な選択が次のように決定されることを示すことは 難しくありません。まず、リンク ( a、b )の差分バックログを最大化する 商品を見つけます。リンク ( a、b )の最大化する差分バックログが負の場合、 リンク ( a、b ) のすべての商品に を割り当てます。それ以外の場合は、商品 に完全なリンク レートを割り当て、このリンク上の他のすべての商品にゼロ レートを割り当てます。この選択により、次のようになります。 ${\displaystyle \mu _{ab}^{(c)}(t)=0}$${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)<0}$${\displaystyle \mu _{ab}(t)}$${\displaystyle (a,b)}$${\displaystyle \mu _{ab}^{(c)}(t)}$${\displaystyle c_{ab}^{opt}(t)\in \{1,\ldots ,N\}}$${\displaystyle \mu _{ab}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle \mu _{ab}(t)}$${\displaystyle c_{ab}^{opt}(t)}$

${\displaystyle \sum _{c=1}^{N}\mu _{ab}^{(c)}(t)[Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)]=\mu _{ab}(t)W_{ab}(t)}$

ここで、スロットtのリンク( a、b )の最適商品の差分バックログ(最大値は0)です。 ${\displaystyle W_{ab}(t)}$

${\displaystyle W_{ab}(t)=\max[Q_{a}^{(c_{ab}^{opt}(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t),0]}$

残っているのは を選択することだけです。これは、次の問題を解くことによって行われます。 ${\displaystyle (\mu _{ab}(t))\in \Gamma _{S(t)}}$

${\displaystyle \mathrm {Maximize:} \sum _{a=1}^{N}\sum _{b=1}^{N}\mu _{ab}(t)W_{ab}(t)}$

${\displaystyle \mathrm {Subjectto:} (\mu _{ab}(t))\in \Gamma _{S(t)}}$

上記の問題は、式(1)-(2)の最大重み問題と同一である。バックプレッシャーアルゴリズムは、の最大重み決定を使用し、上記のように最大差分バックログを介してルーティング変数を選択する。 ${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

バックプレッシャーアルゴリズムの注目すべき特性は、観測されたトポロジ状態S ( t )とそのスロットのキューバックログのみに基づいて、スロットtごとに貪欲に動作することである。したがって、到着率やトポロジ状態確率の知識を必要としない。 ${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \pi _{S}=Pr[S(t)=S]}$

このセクションでは、バックプレッシャーアルゴリズムのスループット最適性を証明します。^{[3] [13]} 簡単にするために、イベントがスロット上で独立かつ同一に分散されている（iid）シナリオが検討されていますが、同じアルゴリズムが非iidシナリオでも動作することが示されています（以下の非iid操作とユニバーサルスケジューリングを参照）。

をスロットtへの外生到着行列とします。この行列は、有限の2次モーメントと平均を持つスロット上で独立かつ同一分布（iid）していると仮定します。 ${\displaystyle (A_{n}^{(c)}(t))}$

${\displaystyle \lambda _{n}^{(c)}=E\left[A_{n}^{(c)}(t)\right]}$

すべての に対して、それ自体宛てのデータは到着しないので、 であると仮定します。したがって、到着率の行列は、対角線上にゼロを持つ非負の実数の行列 です。${\displaystyle \lambda _{c}^{(c)}=0}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle N\times N}$

トポロジー状態S ( t ) が確率を持つスロットにわたって iid であると仮定します ( S ( t ) が実数値エントリを持つベクトルの非可算無限集合内の値を取る場合、 は確率分布であり、確率質量関数ではありません)。 ネットワークの一般的なアルゴリズムは、スロットtごとにS ( t ) を観察し、式 (3) ～ (5) の制約に従って伝送速度とルーティング変数を選択します。ネットワーク容量領域は、ネットワークを安定化するアルゴリズムが存在するすべての到着率行列の集合の閉包です。 すべてのキューの安定性は、ネットワークへのトラフィックの合計入力速度が、その宛先に配信されるデータの合計速度と同じであることを意味します。容量領域内の任意の到着率行列に対して、 S ( t )のみに基づいて(したがってキューのバックログとは無関係に)決定変数と すべてのスロットtを選択する定常かつランダムなアルゴリズムがあり、すべての に対して次の式が得られることが示されます。^{[9] [13]}${\displaystyle \pi _{S}=Pr[S(t)=S]}$${\displaystyle \pi _{S}}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$ ${\displaystyle \Lambda }$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle (\mu _{ab}^{*}(t))}$${\displaystyle (\mu _{ab}^{*(c)}(t))}$${\displaystyle n\neq c}$

${\displaystyle {\text{(Eq. 8)}}\qquad E\left[\lambda _{n}^{(c)}+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)\right]\leq 0}$

S ( t )のみに基づいて決定するこのような定常かつランダムなアルゴリズムは、S のみのアルゴリズムと呼ばれます。 が の内部にあると仮定すると、 が存在するようになり、 の場合は 1 、それ以外の場合は 0 になります。その場合、すべての に対して次を生成するSのみのアルゴリズムが存在します。 ${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle \epsilon >0}$${\displaystyle (\lambda _{n}^{(c)}+\epsilon 1_{n}^{(c)})\in \Lambda }$${\displaystyle 1_{n}^{(c)}}$${\displaystyle n\neq c}$${\displaystyle n\neq c}$

${\displaystyle {\text{(Eq. 9)}}\qquad E\left[\lambda _{n}^{(c)}+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)\right]\leq -\epsilon }$

技術的な要件として、伝送速度を選択するためのあらゆるアルゴリズムにおいて、伝送速度の 2 番目のモーメントは有限であると想定されます。有限の最大速度がある場合、これは当然当てはまります。 ${\displaystyle \mu _{ab}(t)}$${\displaystyle \mu _{max}}$

バックプレッシャーアルゴリズムは、すべてのスロットtを観察し、決定を選択し、ドリフト境界式(7)の右側を最小化するため、次の式が得られます 。${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 10)}}\qquad \Delta (t)\leq B+\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)E\left[\lambda _{n}^{(c)}(t)+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)|{\boldsymbol {Q}}(t)\right]}$

ここで、およびは、 ランダム化された決定を含む、式(3)-(5)を満たす任意の代替決定である。 ${\displaystyle (\mu _{ab}^{*}(t))}$${\displaystyle (\mu _{ab}^{*(c)}(t))}$

ここで と仮定します。すると、式 (8) を満たすSのみのアルゴリズムが存在します。これを式 (10) の右辺に代入し、このSのみのアルゴリズムで与えられた条件付き期待値が無条件期待値と同じであることに注目すると ( S ( t ) はスロットに対して iid であり、Sのみのアルゴリズムは現在のキューのバックログに依存しないため)、次の式が得られます。 ${\displaystyle (\lambda _{n}^{(c)})\in \Lambda }$${\displaystyle {\boldsymbol {Q}}(t)}$

${\displaystyle \Delta (t)\leq B\,}$

したがって、二次リヤプノフ関数のドリフトは、すべてのスロットtに対して定数B以下である。この事実は、キュー到着が制限された秒モーメントを持つという仮定と合わせて、すべてのネットワークキューに対して次のことを意味する：^[16]

${\displaystyle \lim _{t\rightarrow \infty }{\frac {Q_{n}^{(c)}(t)}{t}}=0{\text{ with probability 1}}}$

平均キューサイズをより深く理解するために、到着率がの内部にあると仮定することができます。そのため、式(9) が他の Sのみのアルゴリズムに対して成立するような が存在します。式 (9) を式 (10) の右辺に代入すると、次の式が得られます。 ${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle \epsilon >0}$

${\displaystyle \Delta (t)\leq B-\epsilon \sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)}$

そこからすぐに次の式が得られます（^{[3] [13]}を参照）。

${\displaystyle \limsup _{t\rightarrow \infty }{\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{n=1}^{N}\sum _{c=1}^{N}E\left[Q_{n}^{(c)}(\tau )\right]\leq {\frac {B}{\epsilon }}}$

この平均キュー サイズの境界は、容量領域の境界までの距離が 0 に近づくにつれて増加します。これは、到着率およびサービス率を持つ単一の M/M/1 キューと同じ定性的なパフォーマンスです 。ここで、平均キュー サイズは に比例します。 ${\displaystyle \epsilon }$${\displaystyle \Lambda }$${\displaystyle \lambda }$${\displaystyle \mu }$${\displaystyle 1/\epsilon }$${\displaystyle \epsilon =\mu -\lambda }$

上記の分析では、簡単にするために iid 特性を仮定しています。しかし、同じバックプレッシャーアルゴリズムは、非 iid 状況でも堅牢に動作することが示されています。到着プロセスとトポロジー状態がエルゴードであるが必ずしも iid ではない場合、バックプレッシャーはシステムを安定化させます。^[9] より一般的には、ユニバーサルスケジューリングアプローチを使用すると、任意の（おそらく非エルゴード）サンプルパスに対して安定性と最適性特性を提供することが示されています。^[17]${\displaystyle (\lambda _{n}^{(c)})\in \Lambda }$

バックプレッシャーは、ドリフトプラスペナルティ技術を介してフロー制御と連携して機能することが示されている。 ^{[10] [11] [3]} この技術は、ドリフトの合計と重み付けされたペナルティ式を貪欲に最大化する。ペナルティは、パフォーマンスのトレードオフを決定するパラメータVによって重み付けされる。この技術は、平均遅延がO ( V )である一方で、スループットユーティリティが最適性のO (1/ V )以内であることを保証する。したがって、平均遅延の対応するトレードオフで、ユーティリティを最適性に任意に近づけることができる。同様の特性は、平均電力最小化^[18]や、より一般的なネットワーク属性の最適化でも示されている 。^[13]

ネットワーク効用を最大化しながらキューを安定化するための代替アルゴリズムは、流体モデル解析^[12]、共同流体解析とラグランジュ乗数解析^[19] 、凸最適化^[20]、および確率的勾配^{[21]を使用して開発されてきた。これらのアプローチでは、} O (1/ V )、O ( V )の効用遅延結果 は得られない。

• オーストラリア
• ダイバーシティバックプレッシャールーティング（DIVBAR）^[1]
• ドリフトプラスペナルティ
• 排他的論理和
• 地理的ルーティング
• アドホックルーティングプロトコルのリスト
• リアプノフ最適化

• L. Tassiulas および A. Ephremides、「マルチホップ無線ネットワークで最大スループットを実現するための制約付きキューイング システムとスケジューリング ポリシーの安定性特性」、IEEE Transactions on Automatic Control、vol. 37、no. 12、pp. 1936–1948、1992 年 12 月。
• L. Georgiadis、MJ Neely、および L. Tassiulas、「ワイヤレス ネットワークにおけるリソース割り当てとクロス レイヤー制御」、Foundations and Trends in Networking、第 1 巻、第 1 号、pp. 1–149、2006 年。
• MJ Neely.確率的ネットワーク最適化と通信および待ち行列システムへの応用、Morgan & Claypool、2010 年。