ネットワーク計算
Theoretical framework for analysing performance guarantees in computer networks

ネットワーク計算とは、「並行プログラム、デジタル回路、通信ネットワークといった人工システムへの洞察を与える数学的成果の集合」である[1]。ネットワーク計算は、コンピュータネットワークにおける性能保証を分析するための理論的枠組みを提供する。トラフィックがネットワークを流れる際には、システム構成要素によって課される制約を受ける。例えば、以下のような制約である。

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

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

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

システムモデリング

フローとサーバーのモデリング

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

サーバーの入口と出口における到着曲線と出発曲線。

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

∀ u , t ∈ R + : u < t ⟹ A ( u ) ≤ A ( t ) {\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)は、 出発関数が到着関数に到達するのに必要な最小の時間として定義されます。フロー全体を考慮する場合、これらの値の最大値が使用されます。

到着累積曲線と出発累積曲線間の水平および垂直偏差

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

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

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

d ( A , D ) := sup t ≥ 0 { inf { d ∈ R +   s . t .   D ( t + d ) ≥ A ( t ) } } {\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\}}

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

最小プラス半リング

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

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

( f ∗ g ) ( t ) := ∫ 0 t f ( τ ) ⋅ g ( t − τ ) d τ {\displaystyle (f\ast g)(t):=\int _{0}^{t}f(\tau )\cdot g(t-\tau )d\tau }

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

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

例えば、サービス曲線の定義を参照してください。畳み込みと最小プラス畳み込みは多くの代数的性質を共有しています。特に、どちらも可換性と結合性を備えています。

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

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

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

垂直方向と水平方向の偏差は、最小値と最大値の演算子を使用して表現できます。

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

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

交通封筒

累積曲線は設計時には未知の現実の挙動です。既知のものは何らかの制約です。ネットワーク計算では、トラフィックエンベロープ（到着曲線とも呼ばれる）の概念が使用されます。

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

E ( t ) ≥ sup τ ≥ 0 { A ( t + τ ) − A ( τ ) } = ( A ⊘ A ) ( t ) . {\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 に対して次の式が成り立つことを 意味する。 D ( t ) ≥ ( A ⊗ S ) ( t ) . {\displaystyle D(t)\geq (A\otimes S)(t).}

厳格な最小限のサービス

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

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

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

表記

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

ネットワーク計算の主な表記
概念名 表記 コメント
累積曲線 R , A , F {\displaystyle R,A,F} 最初の論文では が使用されていましたが、[1] F lowには が、A rrivalにはが使用されています。 R {\displaystyle R} F {\displaystyle F} A {\displaystyle A}
入力/出力曲線のペア ( R i n , R o u t ) {\displaystyle (R_{in},R_{out})} ( R , R ∗ ) {\displaystyle (R,R^{*})} 、、​ ( A , D ) {\displaystyle (A,D)} ( F i n , F o u t ) {\displaystyle (F^{in},F^{out})} 入力/出力曲線のペアは当初 と表記されていました。これは到着と出発を表します。その後、入力フローと出力フローに名前を付けました。 ( R , R ∗ ) {\displaystyle (R,R^{*})} ( A , D ) {\displaystyle (A,D)} ( F i n , F o u t ) {\displaystyle (F^{in},F^{out})}
エンベロープ、到着曲線 E , α {\displaystyle E,\alpha } 「エンベロープ」という用語を使用する著者は、 も使用しており、逆に「到着曲線」や も使用しています。 E {\displaystyle E} α {\displaystyle \alpha }
サービス曲線 S , β {\displaystyle S,\beta } 著者は一般的に両方または両方を使用する E , S {\displaystyle E,S} α , β {\displaystyle \alpha ,\beta }
遅延、水平偏差 d ( A , D ) , h ( A , D ) , h D e v ( A , D ) {\displaystyle d(A,D),h(A,D),hDev(A,D)} 「水平偏差」という用語は数学的な定義を強調していますが、「遅延」は意味論を強調しています。
バックログ、垂直偏差 b ( A , D ) , v ( A , D ) , v D e v ( A , D ) {\displaystyle b(A,D),v(A,D),vDev(A,D)} 「垂直偏差」という用語は数学的な定義に重点を置いていますが、「バックログ」は意味に重点を置いています。
畳み込み ∗ , ⊗ {\displaystyle *,\otimes }
デコンボリューション ⊘ {\displaystyle \oslash }

基本的な結果: パフォーマンスの境界とエンベロープの伝播

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

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

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

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

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

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

連結 / PBOO

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

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

2つのサーバーのシーケンス

証明は、サービス曲線の定義と、畳み込み、等張性( )、結合性( )のいくつかの特性を繰り返し適用して行います。 X ≥ A ⊗ S 1 {\displaystyle X\geq A\otimes S_{1}} D ≥ X ⊗ S 2 {\displaystyle D\geq X\otimes S_{2}} D ≥ ( X ⊗ S 2 ) ⊗ S 1 {\displaystyle D\geq (X\otimes S_{2})\otimes S_{1}} D ≥ X ⊗ ( S 2 ⊗ S 1 ) {\displaystyle D\geq X\otimes (S_{2}\otimes S_{1})}

この結果の興味深い点は、エンドツーエンドの遅延の限界がローカル遅延の合計よりも大きくないこと です。 d ( E , S 2 ⊗ S 1 ) ≤ d ( E , S 1 ) + d ( E ⊘ S 1 , S 2 ) {\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]
  • DYRECTsnは、タイムセンシティブネットワーク（TSN）における動的フローのためのPythonベースの学術ツールです。ネットワークのオフライン最適化と、リアルタイムフローのオンラインアドミッション制御機能を備えています。 [14]
  • WOPANetsはネットワーク計算に基づく分析と最適化分析を組み合わせた学術的なツールです。[15]
  • DelayLyzerはProfinetネットワークの境界を計算するために設計された産業用ツールです。[16]
  • DEBORAHはFIFOネットワークに特化した学術的なツールです。[17]
  • NetCalBoundsはブラインドネットワークとFIFOタンデムネットワークに特化した学術的なツールです。[18] [19]
  • NCBoundsはPythonで書かれたネットワーク計算ツールで、BSD 3条項ライセンスの下で公開されています。レート・レイテンシ・サーバーとトークン・バケット到着曲線を考慮しており、循環型を含むあらゆるトポロジーに対応しています。[20]
  • シーメンスネットワークプランナー（SINETPLAN）は、ネットワーク計算（他の手法の中でも）を使用してPROFINETネットワークの設計を支援します。[21]
  • 実験的モジュラーTFA（xTFA）はPythonコードであり、ルドヴィク・トーマスの博士論文[22]をサポートするものである。
  • Panco は、線形計画法を使用してネットワーク計算の境界を計算する Python コードです。
  • Saihu は、xTFA、DiscoDNC、Panco という 3 つの最悪ケース ネットワーク分析ツールを統合した Python インターフェイスです。
  • CCACは、ネットワーク計算のようなモデルを使用して輻輳制御アルゴリズム（CCA）のパフォーマンス特性を検証するためのSMTソルバーベースのツールです。
  • AFDXパフォーマンス分析ツールは、FIFO、SPQ、DRR、WRRスケジューリングを備えたAFDXネットワークの分析と最適化のために開発されたツール群であり、Aakash SONI [23]の博士論文をサポートするためにC++で書かれています。

イベント

WoNeCaワークショップは、ネットワーク計算に関するワークショップです。ネットワーク計算理論に関心を持つ研究者と、既存の成果を新しい応用に応用したい研究者が一堂に会することを目的として、2年に1回開催されます。また、応用待ち行列モデルに関心を持つ研究者にネットワーク計算理論を普及させることも目的としています。

  • WoNeCa7 は、第 36 回国際電気通信会議 (ITC 36) の一環として、ノルウェーのトロンハイムで開催されました。
  • WoNeCa6は、 EPFL（スイス連邦工科大学ローザンヌ校）主催で、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：分離されたネットワーク要素（doi：10.1109/18.61109）」およびパートII：ネットワーク分析（doi：10.1109/18.61110）、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：「共役ネットワーク計算：ルジャンドル変換を適用する二重アプローチ」、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：「マルチホップフェーディングチャネルの(min, ×)ネットワーク計算」、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：「容量・遅延・誤差境界：ソースとシステムの構成可能モデル」、無線通信取引、14(3):1280-1294、2015年3月。
  • F. Sun および Y. Jiang:無線チャネル容量の統計的特性: 理論と応用、Proc. IFIP Performance、2017。

引用

  1. ^ ab ル・ブーデック、ジャン=イヴ;ティラン、パトリック (2001)。グース、ゲルハルト。ハートマニス、ジュリス。ヴァン・レーウェン、ジャン（編）。ネットワーク微積分学: インターネットの決定論的キューイング システムの理論。コンピューターサイエンスの講義ノート。 Vol. 2050.土井：10.1007/3-540-45318-0。ISBN 978-3-540-42184-9. S2CID  20610609。
  2. ^ ジャン、ユーミン;劉永 (2009)。確率的ネットワーク計算。Bibcode :2009snc..book....L. CiteSeerX 10.1.1.725.5561。土井：10.1007/978-1-84800-127-5。ISBN  978-1-84800-126-8。
  3. ^ Fidler, M. (2010). 「ネットワーク計算における決定論的および確率論的サービス曲線モデルのサーベイ」. IEEE Communications Surveys & Tutorials . 12 : 59–86 . doi :10.1109/SURV.2010.020110.00019. S2CID  10745931.
  4. ^ アン・ ブイヤール;ジュエ、ローラン。ティエリー、エリック (2009)。 Network Calculus のサービス曲線: すべきこととしてはいけないこと (技術レポート)。インリア。 RR-7094。
  5. ^ Bouillard, Anne; Jouhet, Laurent; Thierry, Éric. ネットワーク計算における異なるサービスクラスの曲線の比較(PDF) . 第10回国際離散事象システムワークショップ (WODES 2010). ベルリン工科大学.
  6. ^ Zhou, Boyang; Howenstine, Isaac; Limprapaipong, Siraphob; Cheng, Liang (2020年12月14日). 「リアルタイムシステムにおけるネットワークインフラストラクチャのためのネットワーク計算ツールに関する調査」. IEEE Access . 8. IEEE: 223588– 223605. Bibcode :2020IEEEA...8v3588Z. doi : 10.1109/ACCESS.2020.3043600 .
  7. ^ Zippo, Raffaele; Stea, Giovanni (2022年6月). 「Nancy: 効率的な並列ネットワーク計算ライブラリ」. SoftwareX . 19 101178. Elsevier. arXiv : 2205.11449 . Bibcode :2022SoftX..1901178Z. doi : 10.1016/j.softx.2022.101178 .
  8. ^ Rakotomalala, Lucien; Boyer, Marc; Roux, Pierre (2021). coq を用いたmin-plus計算の検証. 第13回NASA形式手法シンポジウム (NFM 2021). doi :10.1007/978-3-030-76384-8.
  9. ^ ブイヤール、アンヌ；ティエリー、エリック (2008). 「ネットワーク計算のためのアルゴリズムツールボックス」 .離散事象動的システム：理論と応用. 18 : 3–49 . doi :10.1007/s10626-007-0028-x. S2CID  14643542.
  10. ^ Bondorf, Steffen; Schmitt, Jens B. (2014). The DiscoDNC v2 – A Comprehensive Tool for Deterministic Network Calculus (PDF) . 8th International Conference on Performance Evaluation Methodologies and Tools (VALUETOOLS 2014).
  11. ^ Thiele, Lothar; Chakraborty, Samarjit; Naedele, Martin (2000). 「ハードリアルタイムシステムのスケジューリングのためのリアルタイム計算」. 2000 IEEE 国際回路・システムシンポジウム. 21世紀の新興技術. Proceedings (IEEE Cat No.00CH36353) . 第4巻. pp.  101– 104. doi :10.1109/ISCAS.2000.858698. ISBN 0-7803-5482-6。
  12. ^ Schioler, Henrik; Schwefel, Hans P.; Hansen, Martin B. (2007). CyNC: ネットワーク計算のためのMATLAB/SimuLinkツールボックス. 第2回パフォーマンス評価方法論およびツールに関する国際会議 (ValueTools '07).
  13. ^ Boyer, Marc; Migge, Jörn; Fumey, Marc (2011). PEGASE：最悪のケースにおけるネットワーク通過時間に対応する堅牢かつ効率的なツール(PDF) . SAE 2011 AeroTech Congress & Exhibition.
  14. ^ Maile, Lisa; Hielscher, Kai-Steffen; German, Reinhard (2024). 「時間依存型ネットワークにおける静的トラフィ​​ックと動的トラフィ​​ックの遅延保証の統合」. Kalyvianaki, Eleni; Paolieri, Martina (編).パフォーマンス評価の方法論とツール. コンピュータ科学、社会情報学、電気通信工学研究所講義ノート. 第539巻. Springer, Cham. pp.  117– 132. doi :10.1007/978-3-031-48885-6_8. ISBN 978-3-031-48884-9。
  15. ^ Mifdaoui, Ahlem; Ayed, H. (2010). 「WOPANets: 組み込みネットワークの最悪ケース性能分析ツール」. 2010 第15回 IEEE 国際ワークショップ 通信リンクとネットワークのコンピュータ支援モデリング、分析、設計 (CAMAD) . pp.  91– 95. doi :10.1109/CAMAD.2010.5686958. ISBN  978-1-4244-7634-3。
  16. ^ Schmidt, Mark; Veith, Sebastian; Menth, Michael; Kehrer, Stephan (2014). DelayLyzer: 産業用イーサネットネットワークにおける遅延境界解析ツール. 第17回国際GI/ITG会議「コンピューティングシステムの測定、モデリング、評価、および信頼性とフォールトトレランス (MMB & DFT 2014)」. doi :10.1007/978-3-319-05359-2_19.
  17. ^ Bisti, Luca; Lenzini, Luciano; Mingozzi, Enzo; Stea, Giovanni (2012). DEBORAH: FIFOタンデムの最悪ケース解析ツール. 形式手法、検証、妥当性確認の活用に関する国際シンポジウム. doi :10.1007/978-3-642-16558-0_15.
  18. ^ Bouillard, Anne; Stea, Giovanni (2015年10月). 「FIFO多重化フィードフォワードネットワークにおける正確な最悪ケース遅延」. IEEE/ACM Transactions on Networking . 23 (5): 1387– 1400. Bibcode :2015ITNet..23.1387B. doi :10.1109/TNET.2014.2332071. hdl : 11568/501671 . S2CID  14216975.
  19. ^ ブイヤール、アンヌ；エリック、ティエリー（2016年9月）「フィードフォワードネットワークの最悪ケース解析における厳密な性能限界」（PDF） .離散事象動的システム. 26 (3): 383– 411. doi :10.1007/s10626-015-0213-2. S2CID  40699209.
  20. ^ Bouillard, Anne (2019).ネットワーク計算を用いた巡回ネットワークの安定性と性能限界．第17回時間付きシステムの形式的モデリングと分析に関する国際会議．
  21. ^ Kerschbaum, Sven; Hielscher, Kai-Steffen; German, Reinhard (2016). 「PROFINETネットワークにおける非タイムクリティカルなデータのシェーピングの必要性」. 2016 IEEE 第14回国際産業情報学会議 (INDIN) . pp.  160– 165. doi :10.1109/INDIN.2016.7819151. ISBN 978-1-5090-2870-2。
  22. ^ Thomas, Ludovic (2022年9月).時間依存ネットワークにおけるスケジューリング、冗長性、同期メカニズムの組み合わせがレイテンシ境界に及ぼす副作用の分析(博士論文). トゥールーズ大学.
  23. ^ Soni, Aakash (2020-05-06). QoSベースの産業用組み込みネットワークのリアルタイムパフォーマンス分析（論文）（フランス語）. トゥールーズ、INPT.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Network_calculus&oldid=1318429444"