ネットワーク計算

ネットワーク計算とは、「並行プログラム、デジタル回路、通信ネットワークなどの人工システムに関する洞察を与える数学的結果の集合」です。^{[1]ネットワーク計算は、}コンピュータネットワークのパフォーマンス保証を分析するための理論的枠組みを提供します。トラフィックがネットワークを流れる際、システムコンポーネントによって課される制約の対象となります。たとえば、

• データリンク容量
• トラフィック シェーパー (リーキー バケツ)
• 混雑制御
• バックグラウンドトラフィック

これらの制約は、ネットワーク計算法で表現および分析できます。制約曲線は、最小プラス代数による畳み込みを使用して組み合わせることができます。ネットワーク計算は、交通到着関数と交通出発関数、およびサービス曲線を表現するためにも使用できます。

この計算では「代替代数を使用して、複雑な非線形ネットワークシステムを解析的に扱いやすい線形システムに変換します。」^[2]

現在、ネットワーク計算には2つの分野があります。1つは決定論的境界を扱う分野、もう1つは確率的境界を扱う分野です。^[3]

ネットワーク計算では、フローは累積関数Aとしてモデル化されます。ここで、A(t)は、フローによって間隔[0,t)で送信されたデータ量 (たとえばビット数) を表します。このような関数は非負で非減少です。時間領域は、多くの場合、非負の実数の集合です。

${\displaystyle A:\mathbb {R} ^{+}\rightarrow \mathbb {R} ^{+}}$

${\displaystyle \forall u,t\in \mathbb {R} ^{+}:u<t\implies A(u)\leq A(t)}$

サーバーは、リンク、スケジューラ、トラフィック シェーパ、またはネットワーク全体になることができます。これは、到着累積曲線Aと出発累積曲線Dの関係として単純にモデル化されます。一部のデータの出発は到着前には発生しないという事実をモデル化するには、 A ≥ Dである必要があります。

到着曲線Aと出発曲線Dが与えられた場合、任意の瞬間tにおけるバックログb(A,D,t)は、 AとDの差として定義できます。 tにおける遅延d(A,D,t)は 、出発関数が到着関数に到達するまでの最小時間として定義されます。フロー全体を考慮する場合、これらの値の最大値が使用されます。

${\displaystyle b(A,D,t):=A(t)-D(t)}$

${\displaystyle d(A,D,t):=\inf \left\{d\in \mathbb {R} ^{+}~st~D(t+d)\geq A(t)\right\}}$

${\displaystyle b(A,D):=\sup _{t\geq 0}\left\{A(t)-D(t)\right\}}$

${\displaystyle d(A,D):=\sup _{t\geq 0}\left\{\inf \left\{d\in \mathbb {R} ^{+}~s.t.~D(t+d)\geq A(t)\right\}\right\}}$

一般に、フローは正確にはわかっておらず、フローとサーバーに関する制約 (一定期間に送信されるパケットの最大数、パケットの最大サイズ、最小リンク帯域幅など) のみがわかっています。ネットワーク計算の目的は、これらの制約に基づいて、遅延とバックログの上限を計算することです。そのために、ネットワーク計算では min-plus 代数を使用します。

ネットワーク計算では、最小プラス半環(最小プラス代数と呼ばれることもある) を集中的に使用します。

フィルタ理論と線形システム理論では、2つの関数の畳み込みは次のように定義されます。 ${\displaystyle f}$${\displaystyle g}$

${\displaystyle (f\ast g)(t):=\int _{0}^{t}f(\tau )\cdot g(t-\tau )d\tau }$

最小プラス半環では、和はそれぞれ最小下限演算子に置き換えられ、積は和に置き換えられます 。したがって、2つの関数とに対する最小プラス畳み込みは、${\displaystyle f}$${\displaystyle g}$

${\displaystyle (f\otimes g)(t):=\inf _{0\leq \tau \leq t}\left\{f(\tau )+g(t-\tau )\right\}}$

たとえば、サービス曲線の定義を参照してください。畳み込みと最小プラス畳み込みは多くの代数的特性を共有しています。特に、両方とも可換かつ結合的です。

いわゆるmin-plus逆畳み込み演算は次のように定義される。

${\displaystyle (f\oslash g)(t):=\sup _{\tau \geq 0}\left\{f(t+\tau )-g(\tau )\right\}}$

たとえば、トラフィック エンベロープの定義で使用される場合など。

垂直方向と水平方向の偏差は、最小プラス演算子で表現できます。

${\displaystyle b(f,g)=(f\oslash g)(0)}$

${\displaystyle d(f,g)=\inf\{w:(f\oslash g)(-w)\leq 0\}}$

累積曲線は実際の動作であり、設計時には不明です。わかっているのは、何らかの制約です。ネットワーク計算では、トラフィック エンベロープ (到着曲線とも呼ばれる) の概念を使用します。

累積関数Aは、すべてのtに対して次の式が成り立つ とき、包絡線E（到達曲線とも呼ばれ、αで表記される）に従うと言われる。

${\displaystyle E(t)\geq \sup _{\tau \geq 0}\{A(t+\tau )-A(\tau )\}=(A\oslash A)(t).}$

2つの同等の定義が与えられる。

したがって、EはフローAに上限制約を課す。このような関数Eは、任意のtから始まる長さdの任意の間隔で見られるフローのビット数の上限を指定するエンベロープとして見ることができる（式（1）を参照）。

トラフィックフローにパフォーマンス保証を提供するには、サーバーの最小パフォーマンスを指定する必要があります（ネットワークの予約やスケジュールポリシーなどによって異なります）。サービス曲線は、リソースの可用性を表現する手段を提供します。弱く厳密なサービス曲線、可変容量ノードなど、いくつかの種類のサービス曲線が存在します。 概要については、 ^{[4] [5]を参照してください。}

Aをサーバーの入口に到着する到着フロー、Dを出口から出発するフローとします。システムがペア(A,B)に単純な最小サービス曲線 Sを提供するとするには、すべてのtに対して次の式が成り立ちます。 ${\displaystyle D(t)\geq (A\otimes S)(t).}$

A はサーバーの入口に到着する到着フロー、D は出口から出発するフローとします。バックログ期間とは、 任意のt ∈ Iにおいて A(t)>D(t)となる間隔 Iです。

システムが(A,B) のペアに厳密な最小サービス曲線 S を提供するとは、がバックログ期間である場合にとなる場合に限られます。 ${\displaystyle \forall s,t\in \mathbb {R} ^{+}}$${\displaystyle s\leq t}$${\displaystyle (s,t]}$${\displaystyle D(t)-D(s)\geq S(t-s)}$

サーバーが曲線Sの厳密な最小サービスを提供する場合、曲線Sの単純な最小サービスも提供します。

著者や論文の目的に応じて、同じ概念に対して異なる表記法や名前が使用されることがあります。

交通エンベロープとサービス曲線から、遅延とバックログの境界、および出発フローのエンベロープを計算できます。

A をサーバーの入口に到着する到着フロー、D を出口から出発するフローとします。フローがトラフィック エンベロープEであり、サーバーが曲線Sの最小サービスを提供する場合、バックログと遅延は制限できます。

${\displaystyle b(A,D)\leq b(E,S)}$

${\displaystyle d(A,D)\leq d(E,S)}$

さらに、出発曲線にはエンベロープがあります。 ${\displaystyle E'=E\oslash S}$

さらに、これらの境界は厳密です。つまり、あるEとSが与えられれば、 b(A,D) = b(E,S)かつv(A,D) = v(E,S)となるような 到着と出発を構築できます。

最初のサーバーの出力が 2 番目のサーバーの入力である、2 つのサーバーのシーケンスを考えてみましょう。このシーケンスは、他の 2 つのサーバーの連結として構築された新しいサーバーとして考えることができます。

そして、最初の（または 2 番目の）サーバーがそれぞれ単純な最小限のサービス（または）を提供する場合、両方のサーバーを連結すると単純な最小限のサービスが提供されます。 ${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle S_{e2e}=S_{1}\otimes S_{2}}$

証明では、サービス曲線の定義と、畳み込み、等張性（）、結合性（）のいくつかの特性を反復的に適用します。 ${\displaystyle X\geq A\otimes S_{1}}$${\displaystyle D\geq X\otimes S_{2}}$${\displaystyle D\geq (X\otimes S_{2})\otimes S_{1}}$${\displaystyle D\geq X\otimes (S_{2}\otimes S_{1})}$

この結果の興味深い点は、エンドツーエンドの遅延の上限がローカル遅延の合計よりも大きくないことです 。 ${\displaystyle d(E,S_{2}\otimes S_{1})\leq d(E,S_{1})+d(E\oslash S_{1},S_{2})}$

この結果は、Pay burst only once (PBOO) として知られています。

^{ネットワーク計算に基づいたツールはいくつかあります。比較については[6]}をご覧ください。

最小プラス代数専用のツールとライブラリがいくつかあります。

• ネットワーク計算インタープリターはオンライン (min,+) インタープリターです。
• Nancyは、最小プラスと最大プラスの演算を実装したC#ライブラリです。^[7]
• MIN-plus ExpRession VErification（Minerve）は、min-plus演算の有効性をチェックするために使用されるCoqライブラリです。^[8]

^{これらのツールとライブラリはすべて、[9]}で紹介されているアルゴリズムに基づいています。

• DiscoDNCはネットワーク計算フレームワークの学術的なJava実装です。^[10]
• RTCツールボックスは、ネットワーク計算とほぼ同等の理論であるリアルタイム計算フレームワークの学術的なJava / MATLAB実装です。 ^{[4] [11]}
• CyNC ^{[12]ツールは、RTCツールボックスをベースにした学術的な}MATLAB /Symulinkツールボックスです。このツールは2004年から2008年にかけて開発され、現在はオールボー大学で教育に使用されています。
• RTaW-PEGASEは、ネットワーク計算に基づいたスイッチドイーサネットネットワーク（AFDX、産業用および車載用イーサネット）のタイミング解析ツールに特化した産業用ツールです。^[13]
• WOPANetsはネットワーク計算に基づく分析と最適化分析を組み合わせた学術ツールです。^[14]
• DelayLyzerはProfinetネットワークの境界を計算するために設計された産業用ツールです。^[15]
• DEBORAHはFIFOネットワークに特化した学術ツールです。^[16]
• NetCalBoundsはブラインドネットワークとFIFOタンデムネットワークに特化した学術ツールです。^{[17] [18]}
• NCBoundsはPythonで書かれたネットワーク計算ツールで、BSD 3条項ライセンスの下で公開されています。レートレイテンシサーバとトークンバケット到着曲線を考慮します。循環トポロジを含むあらゆるトポロジを処理できます。^[19]
• シーメンスネットワークプランナー（SINETPLAN）は、ネットワーク計算（他の方法の中でも）を使用してPROFINETネットワークの設計を支援します。^[20]
• 実験的モジュラーTFA（xTFA）はPythonコードであり、ルドヴィク・トーマスの博士論文^{[21]をサポートするものである。}
• Panco は、線形計画法を使用してネットワーク計算の境界を計算する Python コードです。
• Saihu は、xTFA、DiscoDNC、Panco という 3 つの最悪ケース ネットワーク分析ツールを統合した Python インターフェイスです。
• CCACは、ネットワーク計算のようなモデルを使用して輻輳制御アルゴリズム（CCA）のパフォーマンス特性を検証するためのSMTソルバーベースのツールです。

WoNeCa ワークショップは、ネットワーク計算に関するワークショップです。ネットワーク計算の理論に関心のある研究者と、既存の結果を新しいアプリケーションに適用したい研究者を集めるために 2 年ごとに開催されます。また、このワークショップは、応用待ち行列モデルに関心のある研究者にネットワーク計算理論を広める役割も果たします。

• EPFLが主催する WoNeCa6 は、2022 年 9 月 8 日と 9 日にスイスのローザンヌで開催される予定です。プレゼンテーションの募集はこちらから。
• WoNeCa5は、 COVID-19パンデミックのため、2020年10月9日にバーチャルで開催されました。
• WoNeCa4 は、2018 年 2 月 28 日にドイツのエアランゲンで開催された第 19 回国際 GI/ITG コンピューティング システムの測定、モデリング、評価会議 (MMB2018) に合わせて開催されました。
• WoNeCa3 は、2016 年 4 月 6 日にドイツのミュスターで MMB & DFT 2016 カンファレンスの一環として開催されました。
• WoNeCa2 は、2014 年 3 月 19 日にドイツのバンベルクで開催された MMB & DFT 2014 カンファレンスの一環として開催されました。
• WoNeCa1 はカイザースラウテルン大学が主催し、2012 年 3 月 21 日にドイツのカイザースラウテルンで MMB2012 の一環として開催されました。

2018 年、第 30 回国際電気通信会議 (ITC 30) の一環として、ネットワーク計算およびアプリケーションに関する国際ワークショップ (NetCal 2018) がオーストリアのウィーンで開催されました。

2024年4月1日から4月4日まで、ドイツのダグストゥールでネットワーク計算ダグストゥールセミナー（24141）が開催されました。

ネットワーク計算に関する書籍、調査、チュートリアル

• C.-S. Chang:通信ネットワークにおけるパフォーマンス保証、Springer、2000 年。
• J.-Y. Le Boudec および P. Thiran: Network Calculus: A Theory of Deterministic Queuing Systems for the Internet、Springer、LNCS、2001 (オンラインで入手可能)。
• A. Bouillard、M. Boyer、E. Le Corronc:決定論的ネットワーク計算: 理論から実践的実装まで、Wiley-ISTE、2018
• Y. Jiang と Y. Liu:確率的ネットワーク計算、Springer、2008 年。
• A. Kumar、D. Manjunath、J. Kuri:コミュニケーション ネットワーキング: 分析的アプローチ、Elsevier、2004 年。
• S. Mao および S. Panwar:エンベローププロセスとサービス品質プロビジョニングにおけるそのアプリケーションの調査、IEEE Communications Surveys and Tutorials、8(3):2-20、2006 年 7 月。
• M. Fidler:ネットワーク計算における決定論的および確率論的サービス曲線モデルの調査、IEEE Communications Surveys and Tutorials、12(1):59-86、2010年1月。
• C. Lin、Y. Deng、Y. Jiang:確率ネットワーク計算の応用について、Frontiers Computer Science、7(6): 924-942、2013
• M. FidlerとA. Rizk：確率ネットワーク計算ガイド、IEEE Communications Surveys and Tutorials、17(1):92-105、2015年3月。
• L. Maile、K. Hielscher、R. German：「TSNのネットワーク計算結果：入門」、IEEE情報通信技術会議(1):131-140、2020年5月。

最大プラス代数または凸最小化に関する関連書籍

• RT Rockafellar：凸解析、プリンストン大学出版、1972年。
• F. Baccelli、G. Cohen、GJ Olsder、J.-P. Quadrat:同期と線形性: 離散イベント システムのための代数、Wiley、1992 年。
• VN Kolokol'tsov、Victor P. Maslov :冪等分析とその応用、Springer、1997。ISBN 0792345096 。

決定論的ネットワーク計算

• RL Cruz: ネットワーク遅延の計算。パート I: 分離されたネットワーク要素とパート II: ネットワーク分析、IEEE Transactions on Information Theory、37(1):114-141、1991 年 1 月。
• AK Parekh および RG Gallager:フロー制御に対する一般化されたプロセッサ共有アプローチ: 複数ノードの場合、IEEE Transactions on Networking、2 (2):137-150、1994 年 4 月。
• C.-S. Chang:決定論的および確率的キューイングネットワークの安定性、キューの長さ、遅延、IEEE Transactions on Automatic Control、39(5):913-931、1994年5月。
• DE Wrege、EW Knightly、H. Zhang、J. Liebeherr：「パケット交換ネットワークにおけるVBRビデオの決定論的遅延境界：基本的な制限と実際的なトレードオフ」、IEEE/ACM Transactions on Networking、4(3):352-362、1996年6月。
• RL Cruz: SCED+: サービス品質保証の効率的な管理、IEEE INFOCOM、pp. 625–634、1998 年 3 月。
• J.-Y. Le Boudec:ネットワーク計算の保証付きサービスネットワークへの応用、IEEE Transactions on Information Theory、44(3):1087-1096、1998年5月。
• C.-S. Chang:決定論的トラフィ​​ック規制とサービス保証について: フィルタリングによる体系的なアプローチ、IEEE Transactions on Information Theory、44(3):1097-1110、1998年5月。
• R. Agrawal、RL Cruz、C. Okino、およびR. Rajan：フロー制御プロトコルのパフォーマンス境界、IEEE / ACM Transactions on Networking、7（3）：310-323、1999年6月。
• J.-Y. Le Boudec:可変長パケットシェーパーのいくつかの特性、IEEE/ACM Transactions on Networking、10(3):329-337、2002年6月。
• C.-S. Chang、RL Cruz、J.-Y. Le Boudec、およびP. Thiran：「制約付きトラフィック規制と動的サービス保証のための最小+システム理論」、IEEE/ACM Transactions on Networking、10(6):805-817、2002年12月。
• Y. Jiang:保証レートサーバとレイテンシレートサーバの関係、コンピュータネットワーク43(3): 307-315、2003。
• M. FidlerとS. Recker:共役ネットワーク計算:Legendre変換を適用する二重アプローチ、Computer Networks、50(8):1026-1039、2006年6月。
• Eitan Altman、Kostya Avrachenkov、Chadi Barakat: TCP ネットワーク計算: 大きな帯域幅と遅延の積の場合、IEEE INFOCOM の議事録、ニューヨーク、2002 年 6 月。
• J. Liebeherr: Max-Plus および Min-Plus ネットワーク計算の双対性、Foundations and Trends in Networking 11(3-4): 139-282、2017 年。

ネットワークトポロジー、フィードフォワードネットワーク

• A. Charny および J.-Y. Le Boudec:集約スケジューリングによるネットワークの遅延境界、QoFIS、pp. 1–13、2000 年 9 月。
• D. Starobinski、M. Karpovsky、L. Zakrevski:ターン禁止を使用した一般的なトポロジへのネットワーク計算の適用、IEEE/ACM Transactions on Networking、11(3):411-421、2003年6月。
• M. Fidler:差別化サービスネットワークのためのパラメータベースのアドミッション制御、コンピュータネットワーク、44(4):463-479、2004年3月。
• L. Lenzini、L. Martorini、E. Mingozzi、および G. Stea: FIFO 多重化シンクツリー ネットワークにおけるエンドツーエンドのフローごとの厳密な遅延境界、パフォーマンス評価、63(9-10):956-987、2006 年 10 月。
• J. Schmitt、F. Zdarsky、および M. Fidler:任意の多重化における遅延境界: ネットワーク計算で困った状況に陥ったとき...、IEEE Infocom 教授、2008 年 4 月。
• A. Bouillard、L. Jouhet、E. Thierry:フィードフォワードネットワークの最悪ケース解析における厳密なパフォーマンス境界、Proc. IEEE Infocom、2010 年 4 月。

測定に基づくシステム識別

• C. Cetinkaya、V. Kanodia、EW Knightly：「出力アドミッション制御によるスケーラブルなサービス」、IEEE Transactions on Multimedia、3(1):69-81、2001年3月。
• S. Valaee、B. Li:アドホックネットワーク向け分散コールアドミッション制御、IEEE VTC論文集、pp. 1244–1248、2002年。
• A. Undheim、Y. Jiang、および PJ Emstad。外部測定によるルーター モデリングへのネットワーク計算アプローチ、IEEE 第 2 回中国における通信およびネットワークに関する国際会議 (Chinacom) の議事録、2007 年 8 月。
• J. Liebeherr、M. Fidler、S. Valaee：「帯域幅推定へのシステム理論的アプローチ」、IEEE Transactions on Networking、18(4):1040-1053、2010年8月。
• M. Bredel、Z. Bozakov、Y. Jiang:外部測定によるネットワーク計算を使用したルーターのパフォーマンス分析、Proc. IEEE IWQoS、2010 年 6 月。
• R. Lubben、M. Fidler、J. Liebeherr:ランダム サービスを備えたネットワークにおける確率的帯域幅推定、IEEE Transactions on Networking、22(2):484-497、2014 年 4 月。

確率ネットワーク計算

• O. Yaron および M. Sidi:ロバスト指数境界による通信ネットワークのパフォーマンスと安定性、IEEE/ACM Transactions on Networking、1(3):372-385、1993 年 6 月。
• D. StarobinskiとM. Sidi：通信ネットワークの確率的に制限されたバースト性、IEEE Transactions on Information Theory、46(1):206-212、2000年1月。
• C.-S. Chang:決定論的および確率的キューイングネットワークの安定性、キューの長さ、遅延、IEEE Transactions on Automatic Control、39(5):913-931、1994年5月。
• R.-R. Boorstyn、A. Burchard、J. Liebeherr、C. Oottamakorn:トラフィックスケジューリングアルゴリズムの統計的サービス保証、IEEE Journal on Selected Areas in Communications、18(12):2651-2664、2000年12月。
• Q. Yin、Y. Jiang、S. Jiang、および PY Kong:通信ネットワークの一般化確率的制限バーストトラフィックの分析、IEEE LCN、pp. 141–149、2002 年 11 月。
• C. Li、A. Burchard、J. Liebeherr:有効帯域幅を備えたネットワーク計算、バージニア大学、技術レポート CS-2003-20、2003 年 11 月。
• Y. Jiang:基本的な確率ネットワーク計算、ACM SIGCOMM 2006。
• A. Burchard、J. Liebeherr、SD Patek：「エンドツーエンドの統計的サービス保証のための最小プラス計算」、IEEE Transactions on Information Theory、52(9):4105–4114、2006年9月。
• F. Ciucu、A. Burchard、J. Liebeherr：「ネットワークの確率的解析のためのネットワークサービス曲線アプローチ」、IEEE/ACM Transactions on Networking、52(6):2300–2312、2006年6月。
• M. Fidler:モーメント生成関数を使用したエンドツーエンドの確率ネットワーク計算、IEEE IWQoS、2006 年 6 月。
• Y. Liu、C.-K. Tham、Y. Jiang：確率的QoS分析のための計算、パフォーマンス評価、64（6）：547-572、2007年。
• Y. Jiang と Y. Liu:確率的ネットワーク計算、Springer、2008 年。

無線ネットワーク計算

• M. Fidler:フェージング チャネルの確率的サービス品質分析に対するネットワーク計算アプローチ、Proc. IEEE Globecom、2006 年 11 月。
• K. Mahmood、A. Rizk、Y. Jiang:空間多重化 MIMO 無線チャネルのフローレベル遅延について、Proc. IEEE ICC、2011 年 6 月。
• K. Mahmood、M. Vehkaperä、Y. Jiang:相関 MIMO 無線チャネルの遅​​延制約スループット分析、Proc. IEEE ICCCN、2011。
• K. Mahmood、M. Vehkaperä、Y. Jiang:確率的ネットワーク計算を使用した CDMA の遅延制約スループット分析、Proc. IEEE ICON、2011。
• K. Mahmood、M. Vehkaperä、Y. Jiang:バーストトラフィックと遅延制約のあるマルチユーザー CDMA 受信機のパフォーマンス、Proc. ICNC、2012。
• Y. Zhang および Y. Jiang:分散のあるガウスチャネル上のデータ伝送のパフォーマンス、Proc. ISWCS、2012。
• H. Al-Zubaidy、J. Liebeherr、A. Burchard：「マルチホップフェーディングチャネルのための（最小、×）ネットワーク計算」、Proc. IEEE Infocom、pp. 1833–1841、2013年4月。
• K. Zheng、F. Liu、L. Lei、C. Lin、およびY. Jiang：ワイヤレス有限状態マルコフチャネルの確率的パフォーマンス分析、IEEE Trans. Wireless Communications 12（2）：782-793、2013。
• J.-w. Cho および Y. Jiang: 802.11 におけるバックオフプロセスの基礎: 集約の二分法、IEEE Trans. Information Theory 61(4): 1687-1701、2015 年。
• M. Fidler、R. Lubben、N. Becker：「容量・遅延・誤差境界：ソースとシステムの構成可能モデル」、Transactions on Wireless Communications、14(3):1280-1294、2015年3月。
• F. Sun および Y. Jiang:無線チャネル容量の統計的特性: 理論と応用、Proc. IFIP Performance、2017。