ロングテールトラフィック

ロングテール分布またはヘビーテール分布は、平均値または中央値から離れた領域に比較的高い確率を割り当てる分布です。より正式な数学的定義は以下で示されます。テレトラフィック エンジニアリングのコンテキストでは、多くの重要な数量がロングテール分布を持つことが示されています。たとえば、Web サーバーから転送されるファイルのサイズを考えると、かなりの精度で分布はヘビーテールです。つまり、転送される小さなファイルは多数ありますが、重要なのは、転送される非常に大きなファイルの数がダウンロード量の主要な構成要素であるということです。

多くのプロセスは、技術的には長距離依存ですが、自己相似ではありません。これら 2 つの現象の違いは微妙です。ヘビー テールは確率分布を指し、長距離依存は時系列の特性を指すため、これらは注意して使用し、区別する必要があります。ヘビー テール分布のサンプルを重ね合わせると、長距離依存の時系列が形成されますが、これらの用語は異なります。

さらに、自己相似だが長距離に依存しない ブラウン運動もあります。

堅牢で信頼性の高いネットワークとネットワーク サービスの設計は、今日のインターネットの世界ではますます困難な課題となっています。この目標を達成するには、インターネット トラフィックの特性を理解することがますます重要な役割を果たします。測定されたトラフィック トレースの実証的研究により、ネットワーク トラフィックの自己相似性が広く認識されるようになりました。^[1]

自己相似性を持つイーサネットトラフィックは、長い時間スケールにわたって依存性を示します。これは、到着と出発のプロセスがポアソン分布である電話トラフィックとは対照的です。 ^[2]

多くの時系列では、その系列を平均化すると、データはより滑らかに見え始めます。しかし、自己相似データでは、大規模であっても、スパイク状でバースト的なトレースに直面します。このような動作は、データの強い依存性によって引き起こされます。大きな値はクラスター状になり、クラスターのクラスター状になる傾向があります。これは、ネットワークのパフォーマンスに広範囲にわたる影響を及ぼす可能性があります。^[3]

ヘビーテール分布は、物理現象と社会現象の両方を含む多くの自然現象で観察されています。マンデルブロは、ヘビーテール分布を使用して、株式市場、地震、天気などの現実世界のフラクタル現象をモデル化することを確立しました。 ^[2] イーサネット、WWW、SS7、TCP、FTP、TELNET、VBRビデオ（ ATMネットワークを介して送信されるタイプのデジタルビデオ）トラフィックは自己相似性があります。^[4]

パケット化されたデータネットワークにおける自己相似性は、ファイルサイズの分布、人間の相互作用、および/またはイーサネットのダイナミクスによって引き起こされる可能性があります。^[5]コンピュータネットワークにおける自己相似性と長距離依存の特性は、ネットワークの分析や設計を行う人々にとって根本的に異なる一連の問題を提示し、システムが構築されてきた以前の仮定の多くは、自己相似性が存在するともはや有効ではありません。^[6]

長距離および短期の依存プロセスは、自己共分散関数によって特徴付けられます。

短距離依存プロセスでは、時間差が大きくなるにつれて、異なる時間における値間の結合は急速に減少します。

• すべての遅れにわたる自己相関関数の合計は有限です。
• 遅延が増加すると、短期依存プロセスの自己相関関数は急速に減少します。

長距離プロセスでは、より長い時間スケールでの相関関係がより重要になります。

• すべての遅れにわたって合計された自己相関関数の下の面積は無限大である。^[7]
• 自己相関関数の減衰は、特定の関数形式を持つと仮定されることが多い。

${\displaystyle \rho (k)\sim k^{-\alpha }}$

ここで、ρ( k )は遅れkにおける自己相関関数、αは区間(0,1)のパラメータであり、~はkが無限大に近づくにつれて漸近的に比例することを意味します。

このような自己相関関数のべき乗法則スケーリングは、ビン拡張法によってシーケンスから評価された場合、分散と平均の間のべき乗法則関係に双条件で関連していることを示すことができます。この分散対平均のべき乗法則は、Tweedie 指数分散モデルと呼ばれる統計分布の族の固有の特徴です。中心極限定理が特定の種類のランダム データが正規分布の形に収束する方法を説明するのと同じように、関連する定理であるTweedie 収束定理が存在し、これは他の種類のランダム データがこれらの Tweedie 分布の形に収束し、その結果として自己相関関数で分散対平均のべき乗法則とべき乗法則の減衰の両方を表現する方法を説明します。

ヘビーテール分布を数学的に紹介する前に、従来の電話ネットワークをモデル化するために使用されるメモリなしポアソン分布について簡単に説明します。詳細については、ポアソン分布に関する記事を参照してください。

純粋な偶然の到着と純粋な偶然の終了を仮定すると、次のようになります。

• 特定の時間における通話着信数はポアソン分布に従います。

${\displaystyle P(a)=\left({\frac {\mu ^{a}}{a!}}\right)e^{-\mu },}$

ここで、aはコールの到着数、 は時間Tにおけるコールの平均到着数です。このため、純粋偶然トラフィックはポアソン トラフィックとも呼ばれます。 ${\displaystyle \mu}$

• 特定の時間におけるコール出発数もポアソン分布に従います。

${\displaystyle P(d)=\left({\frac {\lambda ^{d}}{d!}}\right)e^{-\lambda },}$

ここで、dはコール出発回数、 は時間Tにおけるコール出発回数の平均です。 ${\displaystyle \lambda}$

• 通話の到着と出発の間の間隔Tは、独立した同一分布のランダム イベント間の間隔です。これらの間隔は負の指数分布を持つことがわかります。つまり、

${\displaystyle P[T\geq \ t]=e^{\frac {-t}{h}},}$

ここでhは平均保持時間（MHT）である。^[4]

統計学と確率論の基礎に関する情報は、外部リンクのセクションにあります。

ヘビーテール分布は、指数分布などの一般的に使用される（メモリのない）分布とは質的に異なる特性を持っています。

ハーストパラメータ Hは、ヘビーテール分布を適用できる長距離依存性を示す時系列の自己相似性のレベルを測る指標です。Hは0.5から1までの値を取ります。0.5の値は、データが無相関であるか、短距離相関のみであることを示します。Hが1に近いほど、持続性または長距離依存性の度合いが高くなります。^[4]

ハーストパラメータHの典型的な値:

• 純粋なランダムプロセスはH = 0.5である。
• H > 0.5の現象は、通常、複雑なプロセス構造を持ちます。

分布がヘビーテールであるとは、次のような場合です。

${\displaystyle P[X>x]\sim x^{-\alpha },\ {\text{as}}\ x\to \infty ,0<\alpha <2}$

これは、ランダム変数の値が小さい場合の分布に関係なく、分布の漸近形状が双曲線である場合、分布は裾が重いことを意味します。最も単純な裾が重い分布は、その範囲全体にわたって双曲線であるパレート分布です。指数分布とパレート分布の補完分布関数を以下に示します。左側に示されているのは、大きな領域にまたがる線形軸上に示された分布のグラフです。^[8]右側は、より小さな領域で対数範囲を持つ補完分布関数のグラフです。^[5]

指数分布の範囲の対数を取ると、結果として得られるプロットは直線になります。対照的に、ヘビーテール分布のプロットは依然として曲線です。これらの特徴は、右上のグラフで明確に確認できます。ロングテール分布の特徴は、範囲とドメインの両方の対数を取ると、ロングテール分布のテールが数桁にわたってほぼ直線になることです。^[9]左上のグラフでは、前述のヘビーテール分布の存在条件は、「ガンマ指数テール」というラベルの付いた曲線では満たされていません。

重裾分布の 確率質量関数は次のように表されます。

${\displaystyle p(x)=\alpha k^{\alpha }x^{-\alpha -1},\ \alpha ,k>0,\ x\geq k}$

累積分布関数は次のように表されます。

${\displaystyle F(x)=P[X\leq \ x]=1-\left({\frac {k}{x}}\right)^{\alpha }}$

ここで、k はランダム変数が取り得る最小値を表します。

この主題のより厳密な数学的処理に興味のある読者は、外部リンクのセクションを参照してください。

一般に、ロングテールトラフィックの原因については主に 3 つの理論があります (3 つの原因すべてのレビューを参照^[10] )。1 つ目は、アプリケーション層に基づく原因で、ユーザー セッションの継続時間はファイル サイズの分布によりロングテール分布で変化するという理論です。ファイル サイズの分布がヘビーテールの場合、クライアント/サーバーネットワーク環境での多数のファイル転送の重ね合わせは長距離依存になります。さらに、この因果メカニズムは、ネットワーク リソース (帯域幅とバッファー容量) とネットワーク トポロジの変更に対して堅牢です。^[11]これは現在、エンジニアリング文献で最も人気のある説明であり、観測されたファイル サイズ分布を通じて最も実証的な証拠がある説明です。

2 番目は、トランスポート層の原因であり、中程度から高いパケット損失状況での TCP の輻輳回避アルゴリズムによる複数の TCP ストリーム間のフィードバックが自己相似トラフィックを引き起こすか、少なくともそれが伝播することを可能にしていると理論化されています。ただし、これは比較的短い時間スケールでのみ重要な要因であり、自己相似トラフィックの長期的な原因ではないと考えられています。

最後に、シミュレートされたトポロジー上のパケット交換ネットワークの物理シミュレーションに基づいて予測される、理論化されたリンク層の原因です。臨界パケット生成率では、ネットワーク内のフローが混雑し、1/f ノイズとロングテールトラフィック特性を示します。ただし、これらの種類のモデルは、ネットワークトラフィックが混雑していない領域でもロングテールになり、すべてのレベルのトラフィックでロングテールになるという点で非現実的であるという批判があります^[12]。

シミュレーションでは、トラフィックソースが長距離依存性を持たない場合でも、通信ネットワーク内の特定のノード（トラフィックを転送するエンティティ）のキューの長さのダイナミクスに長距離依存性が発生する可能性があることが示されました。このメカニズムは、シミュレーションにおけるルーティング効果からのフィードバックに関連していると考えられています。^[13]

ロングテール トラフィックのモデリングは、ネットワークが伝送するトラフィックの正確な想定に基づいてネットワークをプロビジョニングするために必要です。ロングテール トラフィックを伝送するネットワークの規模設定とプロビジョニングについては、次のセクションで説明します。

パケット化されたトラフィックは（従来の電話トラフィックとは異なり）自己相似性またはフラクタル特性を示すため、従来のトラフィックモデルはロングテールトラフィックを運ぶネットワークには適用できません。^[4]インターネット研究で行われた以前の分析作業では、指数分布のパケット到着間隔などの仮定が採用されており、そのような仮定に基づいて得られた結論は、ヘビーテール分布が存在する場合には誤解を招いたり不正確になったりする可能性があります。^[2]

実世界のさまざまな現象を効率的かつ正確にモデル化するには、異なるスケールで行われた観察がそれぞれ重要な情報を含んでいるという事実を組み込む必要があることは、長い間認識されてきました。最も単純な言葉で言えば、大規模なデータをその平均値で表すことは、多くの場合有用ですが（平均収入や1日あたりの平均顧客数など）、不適切である場合もあります（バッファリングや待機キューのコンテキストなど）。^[3]

音声とデータの融合により、将来のマルチサービスネットワークはパケット化されたトラフィックに基づくものとなり、将来のマルチサービスネットワークの開発、設計、規模決定にはロングテールトラフィックの性質を正確に反映したモデルが必要となる。^{[4]私たちは、回線交換ネットワーク用の}アーランモデルに相当するものを求めている。^[5]

豊富なデータフィッティング技術を備えたヘビーテールモデルはそれほど多くありません。^[14]フラクタルトラフィックの明確なモデルはまだ登場しておらず、明確なモデルに向けた明確な方向性もありません。^[4]ロングテールトラフィックを正確に表す数学モデルを導き出すことは、研究の豊かな分野です。

ガウスモデルは、長距離依存のガウスモデルであっても、現在のインターネットトラフィックを正確にモデル化することができません。^{[15]ポアソン過程や有限}マルコフ過程などの時系列の古典的なモデルは、独立性、または少なくとも弱い依存性の仮定に大きく依存しています。 ^[3]ただし、ポアソン過程とマルコフ過程は、ある程度の成功を収めて使用されています。非線形手法は、短距離と長距離の両方の依存ストリームを再現できるパケットトラフィックモデルの作成に使用されます。^[13]

ロングテール トラフィックをモデル化するタスクには、次のようなモデルがいくつか提案されています。

• 分数ARIMA
• 非整数ブラウン運動
• 反復カオスマップ
• 無限マルコフ変調プロセス
• ポアソン・パレート・バースト過程 (PPBP)
• マルコフ変調ポアソン過程（MMPP）^[16]
• マルチフラクタルモデル^[3]
• マトリックスモデル^[4]
• ウェーブレットモデリング
• トゥイーディー分布

競合するモデルのどれが適切であるかについては意見が一致していないが^[4]、M/G/プロセスであるポアソン・パレート・バースト・プロセス（PPBP）は、おそらくこれまでで最も成功したモデルである。このモデルは、ロングテール・トラフィックのシンプルだが正確なモデルの基本要件を満たすことが実証されている^{[15] 。}${\displaystyle {\mathcal {1}}}$

最後に、ブロードバンドネットワークのトラフィックをモデル化するために安定確率過程を使用したシミュレーション^[4]の結果を示します。シミュレーションは、さまざまな経験的データ（イーサネット、WWW、VBRビデオ）と比較されます。 ${\displaystyle \alpha}$

場合によっては、ハーストパラメータの増加がネットワークパフォーマンスの低下につながる可能性があります。ヘビーテールがネットワークパフォーマンスを低下させる程度は、輻輳制御が情報を節約しながらソーストラフィックを平均的に一定の出力ストリームに整形できるかどうかによって決まります。^[17]ヘビーテールトラフィックの輻輳制御については、次のセクションで説明します。

トラフィックの自己相似性は、キューのサイズやパケット損失率などの主要なパフォーマンス指標に悪影響を及ぼします。ロングテール トラフィックのキューの長さの分布は、ポアソン ソースの場合よりもゆっくりと減衰します。ただし、長距離依存性は、小さなバッファーでのパフォーマンスに影響を与える短期的な相関関係については何も意味しません。^[16] ヘビーテール トラフィックの場合、ライトテール トラフィックの場合よりも非常に大きなバーストが頻繁に発生します。^[18]さらに、ロングテール トラフィックのストリームを集約すると、自己相似性 (「バースト性」) が平滑化されるのではなく、通常、問題が複雑になります。^[1]

^[4]から引用した右上のグラフは、自己相似性の度合いが異なるトラフィック ストリーム間のキューイング パフォーマンスの比較を示しています。任意のチャネル使用率で、データの自己相似性が増加するとキュー サイズが増加し、ネットワーク パフォーマンスが低下することに注意してください。

マルチメディアやその他のQoSに敏感なトラフィックストリームがネットワークトラフィックのますます大きな割合を占める現代のネットワーク環境では、遅延変動やパケット損失変動などの「ジッター」の形での2次パフォーマンス指標が、ユーザー指定のQoSをプロビジョニングする上で重要になっています。自己相似性バースト性は、2次パフォーマンス指標に悪影響を及ぼすことが予想されます。^[19]

インターネット（およびIPを採用した他のネットワーク）などのパケット交換ベースのサービスはベストエフォート型サービスであるため、パフォーマンスの低下は望ましくないが許容できる。ただし、接続が契約されているため、ATMネットワークは遅延とジッタを交渉された制限内に抑える必要がある。^[20]

自己相似トラフィックはクラスタリングの持続性を示し、ネットワーク パフォーマンスに悪影響を及ぼします。

• ポアソン トラフィック (従来の電話ネットワークで発生) では、短期的にはクラスタリングが発生しますが、長期的には平滑化されます。
• ロングテールトラフィックでは、バースト的な動作自体がバースト的になる可能性があり、クラスタリング現象を悪化させ、ネットワークパフォーマンスを低下させます。^[4]

ネットワークのサービス品質の多くの側面は、ネットワーク障害を引き起こす可能性のあるトラフィックのピークへの対処に依存しています。

• セル/パケット損失とキューオーバーフロー
• 遅延制限の違反（例：ビデオ内）
• 統計的多重化における最悪のケース

ポアソン過程は状態を持たないため、良好な振る舞いをします。ピーク負荷は持続しないため、キューがいっぱいになることはありません。長距離秩序では、ピークはより長く続き、より大きな影響を及ぼします。つまり、平衡はしばらくの間シフトします。^[7]

ロングテール トラフィックによるネットワーク リソースへの要求が増大しているため、サービス品質とサービス レベル契約が満たされるようにネットワークを慎重にプロビジョニングする必要があります。次のサブセクションでは、標準的なネットワーク リソースのプロビジョニングについて説明し、その次のサブセクションでは、大量のロングテール トラフィックを伝送する Web サーバーのプロビジョニングについて説明します。

長距離依存入力を持つネットワークキューの場合、使用率がかなり低いレベルでキューイング遅延が急激に増加し、キュー長がゆっくりと減少することは、損失パフォーマンスの段階的な改善にはバッファサイズの大幅な増加が必要であることを意味している。^[21]

自己相似性が増すにつれてスループットは徐々に低下しますが、キューイング遅延はより劇的に増加します。トラフィックが自己相似性を持つ場合、キューイング遅延はシステムに存在するバッファ容量に比例して増加することがわかります。これら 2 つの観察結果を合わせると、ネットワークの QoS 提供に潜在的に深刻な影響を及ぼします。自己相似性が増加するにつれてスループットまたはパケット損失のレベルを一定に保つには、非常に大きなバッファ容量が必要です。しかし、バッファリングが増加するとキューイング遅延が大きくなり、したがって自己相似性によってスループット/パケット損失と遅延のトレードオフ曲線が大幅に急峻になります。^[17]

ATMは、通信ネットワークにおいて、二次的なパフォーマンス測定の問題を克服するために採用することができます。ATMで使用される短い固定長セルは、音声やビデオなどの遅延に敏感なサービスの遅延と、最も重要なジッタを削減します。^[22]

ワークロードパターンの複雑さ（たとえば、バースト的な到着パターン）は、平均応答時間の増加と応答時間の変動の増加という点で、リソース需要、スループット、およびユーザー要求によって発生する待ち時間に大きな影響を与える可能性があります。リソースの適応型で最適な管理と制御がなければ、応答時間に基づくSLAは不可能です。サイトの容量要件は増加する一方で、許容可能なレベルのパフォーマンスと可用性を提供する能力は低下します。^[18]ロングテールトラフィックを制御および管理する手法については、次のセクションで説明します。

要求パターンを正確に予測する能力は、キャパシティプランニングの重要な要件です。バースト性と重なり合った相関性のある到着の実際的な結果として、キャパシティプランニングが困難になります。^[18]

SLA に関しては、独立したライトテールのリクエスト トラフィックの場合と比較して、ヘビーテールのディストリビューションで同じレベルのサービスを提供するには、より強力なサーバー セットが必要です。優れたパフォーマンスを保証するには、ピーク トラフィック期間に重点を置く必要があります。パフォーマンスを最も低下させるのは、大量のリクエストのバーストであるためです。そのため、一部のビジー サイトでは、ボリュームを処理するためにより多くのヘッドルーム (予備容量) が必要です。たとえば、大量のオンライン取引サイトでは、3 対 1 の比率で予備容量が確保されています。^[18]

長距離依存性がネットワーク パフォーマンスに与える影響に関する追加情報については、外部リンク セクションを参照してください。

多様なネットワークコンテキストでスケール不変のバースト性が普遍的に見られることを考えると、自己相似トラフィックを検出して管理できる効果的なトラフィック制御アルゴリズムを見つけることが重要な問題となっている。自己相似ネットワークトラフィックを制御する問題はまだ初期段階にある。^[23]

自己相似性トラフィックのトラフィック制御は、2つの方面から研究されてきました。1つ目は、リソースプロビジョニングのコンテキストにおけるパフォーマンス分析の拡張として、2つ目は、ネットワークパフォーマンスを向上させるために大きな時間スケールでの相関構造を積極的に活用する、複数の時間スケールのトラフィック制御の観点からです。^[24]

リソースプロビジョニングアプローチは、帯域幅とバッファ容量という2つの主要なネットワークリソースタイプの相対的な有用性を、自己相似性に対する抑制効果の観点から特定することを目指しており、小さなバッファ/大きな帯域幅のリソースディメンショニングポリシーを提唱しています。リソースプロビジョニングは本質的にオープンループですが、複数の時間スケールのトラフィック制御は、自己相似トラフィックに存在する長距離相関構造を利用します。^[24]輻輳制御は複数の時間スケールで同時に実行でき、異なる時間スケールで抽出された情報を協調的に活用することで、大幅なパフォーマンス向上を実現します。^[23]

ロングテールトラフィックを制御するために採用されている別のアプローチは、トラフィック制御がワークロード特性を認識するようにする。たとえば、 Webクライアント/サーバー相互作用のコンテキストでHTTPでTCPが呼び出されると、転送されるファイルのサイズ（サーバー側で既知）が伝達されるか、トランスポート層のプロトコルにアクセスできるようになり、代替プロトコルの選択も含まれるため、より効率的なデータ転送が可能になる。Webサーバーのヘビーテールファイルサイズ分布における接続要求の大部分を占める短いファイルの場合、楽観的制御の精神に基づいて、精巧なフィードバック制御をバイパスして軽量メカニズムを採用し、帯域幅の利用率を向上させることができる。^[19]

パケットトラフィックを制御する最も簡単な方法は、キューの長さを制限することであることが判明しました。ネットワーク内の長いキューは、ホスト（パケットを送受信できるエンティティ）で必ず発生します。したがって、長いキューを持つホストでのパケット生成率を下げることで、輻輳制御を実現できます。^[13]

長距離依存性とその交通制御への活用は、存続期間または接続期間が長いフローや接続に最適です。^[19]

• エレファントフロー
• トラフィック生成モデル
• トゥイーディー分布