(57)【特許請求の範囲】
【請求項１】
情報ネットワークのトラフィックフローに対してアドミッション制御を行う方法であって、
上記ネットワークに進入しようとする到着トラフィックに関連する第１の有効包絡線を求める工程と、
上記ネットワーク内で現在進入を許可されている進入許可トラフィックに関連する第２の有効包絡線を求める工程と、
上記ネットワークから出ようとする退去トラフィックを測定してサービス曲線を求める工程と、
上記第１及び第２の有効包絡線の和が上記サービス曲線に等しいかそれよりも小さい場合に、上記到着トラフィックの進入を許可する工程とを備えているアドミッション制御方法。
【請求項２】
上記第１及び第２の有効包絡線は全域有効包絡線である請求項１記載のアドミッション制御方法。
【請求項３】
上記第２の有効包絡線は、集約トラフィックの測定値の平均及び分散の関数として求められた全域有効包絡線である請求項１記載のアドミッション制御方法。
【請求項４】
上記第１及び第２の有効包絡線は局所有効包絡線である請求項１記載のアドミッション制御方法。
【請求項５】
上記第２の有効包絡線は、集約トラフィックの測定値の平均及び分散の関数として求められた局所有効包絡線である請求項１記載のアドミッション制御方法。
【請求項６】
上記第１の有効包絡線は上記到着トラフィックの集約に基づいている請求項１記載のアドミッション制御方法。
【請求項７】
上記集約は、集約された到着フローを複数の時間間隔で測定し、その測定値の平均と分散を算出することによって求められる請求項６記載のアドミッション制御方法。
【請求項８】
上記第２の有効包絡線は再帰的に算出される請求項１記載のアドミッション制御方法。
【請求項９】
上記サービス曲線はパケット遅延の測定値に基づいて求められる請求項１記載のアドミッション制御方法。
【請求項１０】
上記サービス曲線は、１個の情報パケットを処理するのに必要な時間量と待ち行列中の情報パケットの数をそれぞれ表す複数の対からなるリストを展開し、該リストを利用して限界値を有するサービス包絡線を求めることによって得られる請求項１記載のアドミッション制御方法。
【請求項１１】
情報システムのトラフィックフローに対してアドミッション制御を行う方法であって、
上記情報システムに進入しようとする到着トラフィックに関連する第１の有効包絡線を求める工程と、
上記情報システム内で現在進入を許可されている進入許可トラフィックに関連する第２の有効包絡線を求める工程と、
上記情報システムから出ようとする退去トラフィックを測定してサービス曲線を求める工程と、
上記第１及び第２の有効包絡線の和が上記サービス曲線に等しいかそれよりも小さい場合に、上記到着トラフィックの進入を許可する工程とを備えているアドミッション制御方法。
【請求項１２】
上記情報システムはマルチポートスイッチである請求項１１記載のアドミッション制御方法。
【請求項１３】
上記情報システムは自律ネットワークである請求項１１記載のアドミッション制御方法。
【請求項１４】
上記情報システムはコンピュータネットワークドメインである請求項１１記載のアドミッション制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はネットワーク通信アーキテクチャに関し、特に、アドミッション制御によるパケット網上でのサービス品質の制御に関する。
【０００２】
【従来の技術】
現在、インターネットの大部分は“ベストエフォート型”サービスを提供するよう構成されている。インターネットプロトコル（ＩＰ）は、パケット配信を可能にする利用可能なあらゆる内部リンクを通じて最終目的地に対して情報パケットを配信するよう構成されている。そのようなパケットを配信するのにかかる実際の時間は、採用される経路と経路上で遭遇するトラフィックの輻輳に左右される。インターネットプロトコルの原初の設計では、配信を到達させることに焦点が置かれ、配信を達成するのにかかる実際の時間は副次的に考慮されるだけであった。
【０００３】
インターネットの利用が増大するにつれて、かつ、インターネットのトラフィックが等比級数的に拡大するにつれて、時間調整よりも配信を到達させることに重点を置くという原初の形が困難になりつつある。マルチキャストアプリケーションやストリーミング音声・画像アプリケーションの人気が高まるにつれて、パケット配信時間が中心的な課題となってきた。サービス品質（ＱｏＳ）は、通信網が実現する信頼性、可用性及び適時スループットの度合いを説明するためによく使用される用語である。サービス品質は、通信速度、パケット配信の適時性、ネットワークがパケットの流れに発生させるジッタの量、完全パケットロスの確率などの問題に対処する。ビジネスがインターネット上での存在形態にますます依存するようになるにつれて、一部には、より高いサービス品質に対してより多くのコストをかける意思を表示するようになっている。それは、サービス品質が高いほどより円滑でより気が利いているという顧客の感想に直結するからである。したがって、一部のインターネットサービスプロバイダは、様々な料金レートでそれぞれ異なるサービス品質レベルを提供することを確約する様々なサービスレベルアグリーメントを提供している。
【０００４】
インターネットなどのパケット交換網上でのサービス品質を向上させるために、多くの提案がなされている。例えば、サービス品質は、個々のルータをより高速かつよりインテリジェントにすることによって個々のルータレベルで向上させることが可能である。しかしながら、その場合、システムのコストも上昇する。それ以外の提案としては、ネットワークモデルのレベルでサービス品質問題に対処しているものがある。ネットワークモデルのレベルでは、個々のルータの性能についてはほぼ無視され、代わりに、ネットワーク上の全てのルータの集約された性能に重点が移っている。よく知られた手法の一つは、集約ネットワークをその外側境界すなわちエンドツーエンド性能に関してのみ考慮することである。そのような分析的な手法を使用すれば、ネットワーク全体の性能とネットワークが実現するサービス品質とを、ネット−ワークの終端に位置するルータ（すなわち、入口点と出口点のルータ）の振舞いによってほぼ制御することができる。
【０００５】
現在よく利用されているサービス品質（ＱｏＳ）制御用エンドツーエンドネットワークモデルはいくつか存在する。主なモデルとしては、統合サービス（Ｉｎｔｅｇｒａｔｅｄ  Ｓｅｒｖｉｃｅｓ  （ＩｎｔＳｅｒｖ））、マルチプロトコルラベルスイッチング（Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ（ＭＰＬＳ））、差別化サービス（Ｄｉｆｆｅｒｅｎｔｉａｔｅｄ  Ｓｅｒｖｉｃｅｓ  （ＤｉｆｆＳｅｒｖ））がある。ＩｎｔＳｅｒｖはフロー単位のサービス品質保証をサポートする。ＩｎｔＳｅｒｖは、経路を設定して資源を予約するシグナリングプロトコルによって資源が予約されるという相対的に複雑なアーキテクチャを採用している。ＭＰＬＳは、パケット転送処理に重点を置いたサービス品質保証方法を提供する。パケットには、ＭＰＬＳ対応ドメインの入口でラベルが付与される。そのパケットに対するその後の分類、転送処理及びサービスは、そのラベルに基づいて行われる。
【０００６】
ＩｎｔＳｅｒｖ、ＭＰＬＳ等のモデルは、コネクション単位でＱｏＳに対処するので、スケーラビリティ（拡張性）の問題を発生させる可能性がある。スケーラビリティを向上させるために、集約されたトラフィック単位でＱｏＳに対処するモデルが提案されている。ＤｉｆｆＳｅｒｖはそのようなモデルの一例である。ＤｉｆｆＳｅｒｖは、パケットをそれぞれマーキングして異なるサービス品質の取扱いの資格を与える様々なパケットクラスや集合を作成することにより、パケット集合に対してサービス品質を保証する。
【０００７】
大部分の場合、集約トラフィックを基盤とするネットワークモデルはいくつかの共通の概念を共有している。それらのモデルは、ネットワークがエッジルータとコアルータを有することを特徴とするという前提から始まっている。エッジルータは、顧客のトラフィック（すなわち、ネットワーク外の発信元からのパケット）を受け入れる。コアルータは、他のコアルータやエッジルータとの間で中継のパケット転送処理サービスを提供する。エッジルータは、外部トラフィックによるネットワーク進入要求を許可または拒否することによって、トラフィックの進入を制御し、重要なアドミッション制御機能を発揮する。エッジルータがアドミッション制御により最終的なトラフィックフローを制御するので、コアルータは、ネットワーク内部の一時的な輻輳に対処する必要がある程度にトラフィックを差別化するだけでよい。このネットワークモデルは、統計的多重化を採用してコアルータ資源を最大限利用することができる。
【０００８】
【発明が解決しようとする課題】
ネットワークを通過するトラフィックフローを集約レベルで予測し制御することは、非常に複雑な課題である。進入を過度に規制するアドミッション制御アルゴリズムは、内部コアルータ資源を浪費することになる。他方、緩すぎるアドミッション制御アルゴリズムは、ネットワークを過剰なトラフィックで溢れさせ、サービス品質を極度に低下させることになる。これまで多数のアドミッション制御アルゴリズムが提案されており、それらの一部は非常に工夫されているが、まだ改良の余地が多く残っている。
【０００９】
例えば、センチンカヤ（Ｃｅｎｔｉｎｋａｙａ）とナイトリー（Ｋｎｉｇｈｔｌｙ）は、ＩＥＥＥ  Ｉｎｆｏ  Ｃｏｍ  ２０００の「出口アドミッション制御（Ｅｇｒｅｓｓ  Ａｄｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ）」というタイトルの論文において、アドミッション制御の決定を出口ルータ（エグレスルータ）で入手される集約された測定値にのみ基づいて出口ルータにおいて行うというスケーラブルなサービス品質のプロビジョニングのための枠組みを説明している。彼らは、測定値に基づくサービス包絡線を、トラフィッククラスが受け取るエンドツーエンドサービスを適応的に記述する方法として紹介している。
【００１０】
【課題を解決するための手段】
本発明は、測定に基づくアドミッション制御アルゴリズムの基準を、到着集約トラフィックの全域有効包絡線とそれに対応する退去集約トラフィックのサービス曲線に置くという上記技術に対する改良に関する。本アドミッション制御アルゴリズムは、様々なネットワークモデルにうまく適応される。また、本発明は主としてマルチルータネットワークに関して説明されるが、本発明で採用した概念は、自律ネットワークシステムやスイッチング装置に対しても等しく適用可能である。例えば、スイッチング装置の場合、スイッチングハードウェアまたはソフトウェアは複数の入力ポートと複数の出力ポートを提供する。本発明を利用することにより、これら入力ポートと出力ポートの間のトラフィックフローを制御することができる。したがって、本発明は、単独の装置スイッチから大規模な多数の装置コンピュータ網ドメインまで様々な構造的細分性を有する“ネットワーク”に適用可能である。
【００１１】
【発明の実施の形態】
本発明とその目的及び利点をより深く理解するため、以下、本発明を好ましい実施形態と図面に基づいて詳しく説明する。
【００１２】
図１に示すように、ネットワーク１０は、複数のコアルータ１６に順次接続された複数のエッジルータ１２、１４を備えている。説明上、エッジルータ１２は入口ノード（イングレスノード）１８として働き、エッジルータ１４は出口ノード（エグレスノード）２０として働くものとする。図示のように、到着トラフィックが入口ノードから進入し、退去トラフィックが出口ノードから出る。
【００１３】
説明上、到着集約トラフィック２２はネットワーク２４からエッジルータ２６を介して入来するものとし、エッジルータ２６は到着集約トラフィックのフローを所定の境界内に限定するトラフィックコンディショナ機能２８を有しているものとする。
【００１４】
説明上、退去集約トラフィック３０はエッジルータ１４を出て、ネットワーク３２に進入するものとする。
【００１５】
ネットワーク１０は、到着集約トラフィック２２のパケットのネットワーク１０への進入を許可または阻止するアドミッション制御機能３４を実装している。アドミッション制御機能３４は、エッジルータ１２等の１台のルータ内に集中させてもよいし、ネットワーク１０中に分散させてネットワーク１０内の複数のルータで実行させるようにしてもよい。本発明によれば、アドミッション制御機能３４は、到着集約トラフィック２２の全域有効包絡線３６及び退去集約トラフィック３０のサービス曲線３８に基づくアドミッション制御アルゴリズムを実効する。
【００１６】
図２に、到着トラフィック、進入許可トラフィック及び退去トラフィックを有するネットワーク１０をさらに詳細に示す。図２は、現在好ましいアルゴリズムを理解するのに役立つ用語の一部を紹介している。到着トラフィック２２はトラフィックコンディショナまたはレギュレータ２８を介して供給されるものとし、トラフィックコンディショナ２８は、入口ノード１８に実装され、到着トラフィックを送信者が申告したトラフィックの仕様に従わせることができる。トラフィックコンディショナまたはレギュレータは、単純なメータリング機能を実現するリーキーバケットの形でモデル化することができる。あるいは、トラフィックコンディショナは、一部のパケット転送を遅延させることによってトラフィッククラスの時間的特性を選択的に変更する、より高度なトラフィックシェーピング機能を実行してもよい。
【００１７】
到着トラフィック２２には、決定的包絡線４２が関連付けられている。決定的包絡線は、３つの変数、すなわち、ピークトラフィックレート、平均トラフィックレート及びバーストサイズパラメータに関して特徴付けることができる。到着トラフィックは、関連するサービス品質要件４４を持つものと見なされる。通常、各サービスクラスは、それ自体のサービス品質要件を有することになる。図２に、複数のＱｏＳ要件４４を示す。ＱｏＳ要件は、以下の変数、すなわち、遅延違反確率と遅延限界によって特徴付けることができる。
【００１８】
進入許可トラフィック４６は、既にアドミッション制御地点を通過しており、従って、現在はネットワーク１０内を流れているという点で、到着トラフィックと区別することができる。進入許可トラフィック４６がネットワーク１０を退出すると、退去トラフィック３０となる。退去トラフィック３０は、各パケットの到着時刻と退去時刻を監視することにより測定されるサービス曲線またはサービス包絡線４８に関連付けされている。
【００１９】
本好ましい実施形態のアドミッション制御アルゴリズムは、到着トラフィックが所望のＱｏＳ要件を満たして進入を許可されるか拒否されるかを決定する際に、到着トラフィックの関連する決定的包絡線４２と退去トラフィックの関連するサービス包絡線４８を利用する。図３ａ及び図３ｂは、本好ましい実施形態のアルゴリズムをフロー図で示す。本好ましいアルゴリズムのより厳密な数学的導出については後述する。図３ａ及び図３ｂのフロー図は、適用可能であれば、詳細な数学的導出から特定の等式を引用している。先ず最初に、後述する詳細な数学的導出を導入する方法として、フロー図の説明を行う。すなわち、図３ａは全域有効包絡線に相当し、図３ｂは局所有効包絡線に相当する。これら２図の内容は類似しているため、図３ａを以下に詳細に説明し、図面を比較すれば明らかなように、数学的導出が異なっている場合以外は、図３ｂに適用可能であると見なす。
【００２０】
図３ａに示すように、本アルゴリズムは、ステップ６０において、ネットワークへの進入許可要求で始まる。到着トラフィックが、要求の一部として、特徴パラメータ６２で表現されるトラフィック特性を申告する。本実施形態で使用される具体的なパラメータは、決定的包絡線Ａｊ＊（τ）、サービス品質要件ＱｏＳ、遅延限界ｄ及び遅延違反確率εである。
【００２１】
次に、アルゴリズムは、ステップ６４で、申告されたパラメータ６２に基づいて到着トラフィックの全域有効包絡線を作成する。後述する数学的導出において、到着トラフィックの有効包絡線はＧｎｅｗの形で特徴付けられる。図３では、Ｇｎｅｗ包絡線を符号６６で示す。破線と大括弧で示すように、ステップ６４は、等式（３．８）から等式（３．１１）までを利用して実行される。
【００２２】
次に、アルゴリズムはステップ６８に進み、測定された統計値に基づいて進入許可トラフィックの全域有効包絡線を作成する。具体的には、符号７０で示す測定された統計値には、到着集約トラフィック量の平均と分散が含まれている。後述する詳細な数学的導出では、進入許可トラフィックの全域有効包絡線をＧｑＮｑの形で示す。図３では、このＧｑＮｑ包絡線を符号７２で示す。
【００２３】
ステップ７４では、両有効包絡線６６、７２と等式４．５を用いて算出されたサービス曲線４０の解析、及び、後述する表１に示すアルゴリズムに基づいて、アドミッション制御が最終的に決定される。すなわち、アドミッション制御の決定は、
Ｇｎｅｗ  ＋  ＧｑＮｑ  ≦  Ｓｑ
ならば、到着トラフィックの進入を許可することになる。
【００２４】
上記アドミッション制御条件のより精細な記述に関しては、以下の詳細な説明と特に、等式（３．１２）を参照されたい。
【００２５】
好ましいアドミッション制御アルゴリズムの詳細な説明
以下に、好ましいアルゴリズムについて詳細に説明する。説明のため、ＤｉｆｆＳｅｒｖアーキテクチャを想定する。本発明は、本発明のアドミッション制御アルゴリズムが様々なネットワークアーキテクチャで利用可能であるため、ＤｉｆｆＳｅｒｖアーキテクチャに限定されない。
【００２６】
サービス品質（ＱｏＳ）を提供するために、ＩｎｔＳｅｒｖ（ＩＳ）アーキテクチャはシグナリングプロトコルを利用して経路上の全てのルータの資源予約を設定する。この方法は、全てのルータが個別フロー状態を維持するとともにフロー単位で資源予約を処理する必要があるので、公知のスケーラビリティ問題を抱えている。ＤｉｆｆＳｅｒｖは、ＱｏＳを提供する別の方法であるが、スケーラビリティの制約はなく、ルータはスケジューリング機能とバッファリング機能を実装してそれらを到着パケットのヘッダにあるＤｉｆｆＳｅｒｖコードポイント（ＤＳＣＰ）に基づいて適用しさえすればよい。複数のドメインを横断するエンドツーエンドＱｏＳサービスは、個々のＤｉｆｆＳｅｒｖ（ＤＳ）ドメインのドメイン単位動作（ｐｅｒ  ｄｏｍａｉｎ  ｂｅｈａｖｉｏｒ（ＰＤＢ））を結合することによって構築される。これらＰＤＢは、ホップ単位転送動作（ｐｅｒ−ｈｏｐ  ｆｏｒｗａｒｄｉｎｇ  ｂｅｈａｖｉｏｒ（ＰＨＢ））を適切に展開することによって作成される。複数のＤＳドメインは１つの自律システム（ＡＳ）内に存在することができる。ＰＤＢの確定作業は現在活発に行われている研究領域であり、その最初の２，３の草案は入手可能である。したがって、ＤｉｆｆＳｅｒｖは、集約トラフィックのレベルでＱｏＳを保証することによってスケーラビリティ問題に対処する。
【００２７】
上述したように、ＤＳドメイン上のサービスプロビジョニングに対する主要な要件の１つは、有効なコネクションアドミッション制御（ＣＡＣ）が存在することである。そのようなアドミッション制御は、ＤｉｆｆＳｅｒｖネットワーク上のプレミアムサービス（ｐｒｅｍｉｕｍ  ｓｅｒｖｉｃｅｓ）に対してサービスレベルアグリーメント（ＳＬＡ）を動的に確立させながら利用することもできるし、静的なＳＬＡの再取決めを参考にしてもよい。ＤＳドメインの帯域幅ブローカ（Ｂａｎｄｗｉｄｔｈ  Ｂｒｏｋｅｒ  （ＢＢ））エンティティは、そのようなアドミッション制御用の典型的な場所である。有効なＣＡＣを設計する際に困難なことは、多数のソリューションが接続形態に依存した実装の方向に向かっているため、その範囲が限定されるとともに複雑さが増大する点である。
【００２８】
スケーラビリティ問題がなくＤｉｆｆＳｅｒｖのアドミッション制御を実現するため、数人の研究者が様々な端点（エンドポイント）ＣＡＣの形態を提案している。本実施形態の構成では、ＤＳドメインの端点（入口または出口ルータ）がアドミッション制御と資源管理を行う。これらルータは、ネットワーク上のトラフィックを測定して利用可能な資源のレベルを検出するとともに、検出した資源レベルが十分に高い場合にかつその場合にのみ、新しいコネクションを許可する。
【００２９】
本実施形態は、ＤＳドメイン内の集約トラフィックレベルに対して統計的にＱｏＳを保証する、測定に基づくＣＡＣアルゴリズムを提供する。ＤＳドメインの境界に到着する進入トラフィックは、上流側ドメインによって調整されているとみなされ、既定のＳＬＡ規則を固守するよう当該ドメインによってポリシー制御され、適切なＤＳＣＰをさらにマーキングされる。リーキーバケットに基づくポライサー、シェーパー、マーカーが様々に提案されている。ＤｉｆｆＳｅｒｖアーキテクチャは集約トラフィックごとに何らかのＰＤＢを付与するので、以下の説明では、この集約トラフィックをクラスと称する（ＤｉｆｆＳｅｒｖクラスとは異なる）。本発明は、遅延と遅延違反確率が与えられた時に、クラス分けされた集約トラフィックに対して遅延を保証するＰＤＢを目標としている。以上、決定的包絡線、すなわち、到着トラフィック包絡線と、サービス包絡線と、これらの包絡線から求められる性能特性限界について説明した。その後は、測定に基づくＣＡＣを導出して動的ＳＬＡを確立させ、全域有効包絡線及びサービス曲線と称する統計的トラフィック包絡線を利用して様々なサービスクラスに対して統計的な保証を提供する。これらの包絡線を得るため、測定手法を利用する。サービス曲線を測定することにより、ＤＳドメインの接続形態やドメイン内のクロストラフィックについて知らなくても、アドミッション制御状態が働くようになる。
【００３０】
或るネットワークドメインに到着するトラフィックについて考察する。トラフィックは、入口ノード１８でドメイン内に進入し、出口ノード２０に向かう（図１参照）。以下、連続時間流体低トラフィックモデルについて考える。異なるフローからの到着トラフィックは、そのＱｏＳ要件によって差別化される。ここでは、対象のＱｏＳ要件を、遅延違反確率と遅延限界とする。同じＱｏＳ要件、すなわち、同じ遅延限界要件及び遅延違反確率要件を持つ到着トラフィックは、１つのサービスクラスとして扱われる。したがって、ドメイン内への到着トラフィックはＱ個のクラスに分類される。ここで、１クラスｑ内のフロー数をＮｑで表す。
【００３１】
或る時間間隔（ｔ１，  ｔ２）におけるクラスｑのフローｊからの到着トラフィックを、Ａｑｊ（ｔ１，  ｔ２）で表す。各フローｊからのトラフィック到着は、トラフィックコンディショナで規制され、決定的劣加法的包絡線Ａｑｊ＊（τ）によって以下のように上限設定されるものとする。
【数１】
0003597505.tif 000002
【００３２】
到着トラフィックはパラメータ群を用いて決定的包絡線により特徴付けられる。最も一般的に利用されるトラフィックコンディショナは、ピークレート強調機構を有するリーキーバケットである。その場合、フローｊのトラフィックは、決定的包絡線が以下の数式
【数２】
0003597505.tif 000003
（但し、Ｐｑｊ  ≧ρｑｊはピークトラフィックレート、ρｑｊは平均トラフィックレート、σｑｊはバーストサイズパラメータ）によって与えられるとき、３個のパラメータ（Ｐｊ，  σｊ，  ρｊ）によって特徴付けられる。
【００３３】
ピークレートで強調されたリーキーバケットを生成する場合、フローｊのトラフィックは、決定的包絡線が以下の数式
【数３】
0003597505.tif 000004
（但し、Ｋｑｊはリーキーバケット対の数）によって与えられるとき、パラメータ群｛σｑｊｋ，  ρｑｊｋ｝ｋ＝１，  …，  Ｋｊによって特徴付けられる。
【００３４】
なお、同じサービスクラスからのフローは、異なる決定的包絡線によって特徴付けできるが、同じＱｏＳ要件を有することができる。
【００３５】
或る時間間隔（ｔ１，  ｔ２）においてドメインの出口ノードを離れるクラスｑのフローｊからのトラフィックを、Ａｑｏｕｔｊ（ｔ１，  ｔ２）で表す。クラスｑの集約トラフィックを以下のように定義する。すなわち、
到着トラフィックの集約
【数４】
0003597505.tif 000005
退去トラフィックの集約
【数５】
0003597505.tif 000006
【００３６】
長さβの時間間隔の場合、クラスｑからの到着フロー集合Ｎｑの経験的包絡線ＥＮｑ（τ；β）、すなわち、長さτ≦βのあらゆる時間間隔の到着フロー集合の上限を以下のように定義する。
【００３７】
【数６】
0003597505.tif 000007
【００３８】
以下、単一のサービスクラスの集約トラフィックに重点を置いて説明し、指数ｑを落とすものとする。ここで、サービス曲線の定義とその適用例を紹介する。今、時刻ｔ  ＝  ０においてドメイン内にトラフィックが存在しないと仮定する。したがって、集約トラフィックの場合、任意の時刻ｔにおけるドメイン内の待ち行列トラフィック量Ｂ（ｔ）は以下の数式によって求められる。
【数７】
0003597505.tif 000008
【００３９】
また、時刻ｔに集約トラフィックが経験する入口出口間遅延ｄ（ｔ）は、以下のように定義される。
【数８】
0003597505.tif 000009
【００４０】
（サービス曲線の定義）
Ｓ（・）を非減少関数とすると、Ｓ（０）  ＝  ０となる。任意の時刻ｔにおいて、Ｂ（ｓ）  ＝  ０かつＡｏｕｔＮ（ｓ，  ｔ）  ≧  Ｓ（ｔ−ｓ）となるようなｓ  ≦  ｔが存在する場合、ドメインは、集約トラフィックのサービス曲線Ｓ（・）を保証する。
【００４１】
このことから、ドメインが時刻ｓにおいて空の場合、Ｓ（ｔ−ｓ）により、或る時間間隔（ｓ，  ｔ）の間にドメインから供給されこのドメインを出るのに必要な集約トラフィック量の下限が規定されることがわかる。
【００４２】
上記サービス曲線の定義から、遅延上限は以下のようにして求めることができる。ビジー期間の長さがβの場合、ビジー期間の開始時刻をｓとすると、Ｂ（ｓ）  ＝  ０かつＡＮ（０，  ｓ）  ＝  ＡｏｕｔＮ（０，  ｓ）である。ｓ  ≦  ｔ＋ｄ  ≦βの場合に、ドメインがサービス曲線Ｓ（・）を保証する、すなわち、ＡｏｕｔＮ（ｓ，  ｔ）  ≧  Ｓ（ｔ−ｓ）が成立すると仮定すると、サービス曲線の定義から、ＡｏｕｔＮ（ｓ，  ｔ＋ｄ）  ＝  ＡｏｕｔＮ（０，  ｔ＋ｄ）  −  ＡＮ（０，  ｓ）  ≧  Ｓ（ｔ＋ｄ−ｓ）が成立する。したがって、等式（２．６）から、ＡＮ（０，  ｔ）  ≧  ＡｏｕｔＮ（０，  ｔ＋ｄ）  ≧  ＡＮ（０，  ｓ）＋  Ｓ（ｔ＋ｄ−ｓ）となる。したがって、等式（２．４）から
【数９】
0003597505.tif 000010
となる。τ＝  ｔ−ｓとすると、任意の時刻ｔ  ≧  ０について、等式（２．６）で定義される遅延が以下のようにして上限設定される。
【００４３】
【数１０】
0003597505.tif 000011
【００４４】
等式（２．８）から、遅延の上限は到着集約包絡線ＥＮ（τ；β）とサービス曲線Ｓ（τ）との間の最大水平距離であることがわかる（図４参照）。なお、βは、集約トラフィックの最大ビジー期間βｍａｘ、すなわち、
【数１１】
0003597505.tif 000012
によって上限設定される。したがって、以下の説明では、β＝βｍａｘを採用する。
【００４５】
本アドミッション制御アルゴリズムは、決定的包絡線とサービス曲線を利用することにより、全てのフローが同時に各自のピークレートでトラフィックを送信することを想定した最悪のシナリオに基づいて到着トラフィックが被る遅延の上限を求める。
【００４６】
以下に、上記の包絡線の概念に従って、トラフィックのほんの一部が遅延ＱｏＳ要件に違反する場合の統計的サービスを導出する。いわゆる全域有効包絡線を利用して各クラスの到着集約トラフィックを特徴付ける。これらの包絡線を利用することにより、決定論的サービスの場合と同じ方法をとって統計的サービスに対するＣＡＣを導出することができる。
【００４７】
有効包絡線とサービス曲線を用いた確率的保証
以下の節では、先の節で示した遅延の上限に基づいて遅延違反確率を導出する。その後、２０００年３月、イスラエル、テルアビブ、ＩＥＥＥ  ＩＮＦＯ  ＣＯＭＭ  ２０００議事録において、Ｒ．ボアスティン（Ｒ．  Ｂｏｏｒｓｔｙｎ）、Ａ．バーチャード（Ａ．  Ｂｕｒｃｈａｒｄ）、Ｊ．リーベハー（Ｊ．  Ｌｉｅｂｅｈｅｒｒ）及びＣ．オッタマコーン（Ｃ．  Ｏｔｔａｍａｋｏｒｎ）「有効包絡線：パケット網上の多重トラフィックの統計的限界（Ｅｆｆｅｃｔｉｖｅ  ｅｎｖｅｌｏｐｅｓ：  Ｓｔａｔｉｓｔｉｃａｌ  ｂｏｕｎｄｓ  ｏｎ  ｍｕｌｔｉｐｌｅｘｅｄ  ｔｒａｆｆｉｃ  ｉｎ  ｐａｃｋｅｔ  ｎｅｔｗｏｒｋｓ）」によって紹介された局所及び全域有効包絡線の定義を適用することにより、単一サービスクラスの場合のアドミッション制御状態を求める。そして、最後に、多重サービスクラスの場合のアドミッション制御状態について説明する。
【００４８】
局所有効包絡線とサービス曲線を用いた確率的保証
まず最初に、単一サービスクラスについて考察し、指数ｑを落とす。同じサービスクラスからの到着トラフィックの集約ＡＮ（ｔ１，  ｔ２）は、同じ遅延違反確率εと、同じ遅延限界要件ｄを有している。ＡＮ（ｔ１，  ｔ２）は、負ではないランダム処理群によって上限設定される。ＡＮ（ｔ１，  ｔ２）は、以下の特性を有している。すなわち、（１）統計的特性が経時的に変化しない定常性と、（２）全てのサービスクラス間で確率的に独立である独立性である。時刻τにドメインに到着するＮ個のフローからなる集約トラフィックの１ビットが被る入口出口間遅延をＤＮ（τ）とし、ＤＮ（τ）がランダム変数であると仮定する。遅延限界ｄが与えられると、ドメインは、あらゆる到着ビットの入口出口間遅延が遅延限界ｄを超えないことを保証する。すなわち、任意の時刻ｔ  ≧  ０，  ０  ≦τ≦  βｍａｘについて、等式（２．８）からＤＮ（τ）  ＝  ｍｉｎ｛ｚ  ：  ｚ  ≧  ０  ａｎｄ  ＡＮ（ｔ，  ｔ＋τ）  ≦  Ｓ（τ＋ｚ）｝≦  ｄが成立すること、あるいは、任意の時刻ｔ  ≧  ０，  ０  ≦τ≦  βｍａｘについて、ＡＮ（ｔ，  ｔ＋τ）  ≦  Ｓ（τ＋ｄ）が成立することを保証する。ＤＮ（τ）  ≧  ｄとなるようなＤＮ（τ）が存在する場合、あるいは、ＡＮ（ｔ，  ｔ＋τ）  ＞  Ｓ（τ＋ｄ）となるようなτが存在する場合に遅延違反が発生する。
【００４９】
等式（２．８）の場合、到着トラフィックが遅延違反を被る確率は、εによって限定される必要があり、任意の時刻ｔ  ≧  ０，  ０  ≦τ≦  βｍａｘについて、
【数１２】
0003597505.tif 000013
が成立する。
【００５０】
新規のフロー群はＤＳドメインから同じサービス保証を要求する。ＣＡＣは、アドミッション制御テストを利用して、要求されたサービス保証と全てのサービスクラスからの他のフローが確実に同時に満たされるようにする。等式（１）から、以下の局所有効包絡線の定義を利用して単一サービスクラスの場合のアドミッション制御状態を求めることができる。
【００５１】
（局所有効包絡線の定義）
集約トラフィックＡＮ（ｔ，  ｔ＋τ）の局所有効包絡線は、任意のτ  ≧  ０かつ任意のｔについて、
【数１３】
0003597505.tif 000014
を満たす関数ＬＮである。この式から、局所有効包絡線がいかなる特定時間間隔τにおいても集約トラフィックＡＮ（ｔ，  ｔ＋τ）に対して確率的限界を付与することがわかる。
【００５２】
（補助定理）
Ｍ個のクラスに分類されるフロー群が与えられ、各クラスが到着集約トラフィックＡＮｍにＮｍ個のフローを含んでいるものとする。クラスｍの局所有効包絡線をＬＮｍ（τ；ε）とし、ｘが与えられると、以下の不等式が成立する。
【数１４】
0003597505.tif 000015
【００５３】
同じサービスクラスからのフローを２つのカテゴリーに分類する。すなわち、Ｍ＝２とする。最初のグループはフロー群Ｎであり、既にドメインへの進入が許可されている。２番目のグループは新規のフロー群Ｋであり、ＤＳドメインからのＱｏＳサービスを要求している。最初のグループの局所有効包絡線をＬＮで表し、２番目のグループの局所有効包絡線をＬｎｅｗで表す。
【００５４】
（単一サービスクラスの場合のアドミッション制御状態）
上記局所有効包絡線の定義と補助定理及び等式（１）から、
【数１５】
0003597505.tif 000016
ならば、到着トラフィックの遅延違反確率はεより低い。但し、
１．同じサービスクラスに関して、新規のフロー群が同じ決定的包絡線Ａ＊ｊを有する場合にそれぞれ異なる決定的包絡線Ａ＊ｊによって調整される場合は、
【数１６】
0003597505.tif 000017
のとき、それぞれＬｊｎｅｗ（・；εｊ）を作成することが必要である。したがって、等式（２）は以下のようになる。
【数１７】
0003597505.tif 000018
【００５５】
２．等式（２）のＣＡＣは、ドメインの接続形態とドメイン内のスケジューリングアルゴリズムに依存しないが、ＤＳドメインの入口ノードと出口ノードで測定可能な  、測定に基づくトラフィック特徴付け包絡線には依存する。
【００５６】
（測定モーメントを用いた局所有効包絡線）
進入許可されたフロー群Ｎについて考察する。各フローの基本的な配分の知識を必要としない中心極限定理を用いて集約トラフィックの配分を特徴付けることとする。集約トラフィックの近似局所有効包絡線は、中心極限定理から次のようにして求めることができる。局所有効包絡線の定義から、Ｐｒ［ＡＮ（ｔ，  ｔ＋τ）≧ｘ］  ≒ε／２を設定し、以下の式を得る。
【数１８】
0003597505.tif 000019
但し、ｚはその近似値
【数１９】
0003597505.tif 000020
を有しており、
【数２０】
0003597505.tif 000021
とσ２（τ）はそれぞれ測定された集約トラフィック量の平均と分散である。これらの測定方法については後述する。
【００５７】
新規のフロー数はわずか数個の場合があるので、中心極限定理はそのような局所有効包絡線を作成するのに適切な選択肢ではないことがある。すなわち、求められた限界が十分に厳密ではないことがある。その代わりとして、集約トラフィックに対してより厳密な限界を提供するチャーノフ限界を利用する。新規のフロー群Ｋの局所有効包絡線は、チャーノフ限界を用いて求めることができ、次のようにして与えられる。
【００５８】
ランダム変数Ｙに関してチャーノフ限界を想起する。
【００５９】
【数２１】
0003597505.tif 000022
【００６０】
したがって、
【数２２】
0003597505.tif 000023
となる。但し、ＭＫ（ｓ，  τ）は、集約トラフィックの能率母関数である。
【００６１】
上記ボアスティン他による有効包絡線の定義では、ＭＫ（ｓ，  τ）は、フローの決定的包絡線の面から、すなわち、本実施形態ではリーキーバケット関数の面から導出及び付与される。ｓは、等式（６）が最小になるように選択される。ｓとＭＫ（ｓ，  τ）の両方の値があれば、
【数２３】
0003597505.tif 000024
となる。但し、ＡＫ＊（τ）は各新規フローの決定的包絡線である。
【００６２】
（多重サービスクラスの場合のアドミッション制御状態）
等式（２）のアドミッション制御状態は、新規フロー群がドメイン内への進入を許可された場合に、他のサービスクラスが同じ入口から出口までの経路を使用するというＱｏＳ要件を満たすことを保証しない。汎用性を損なうことなくそのことを保証できるようにするため、新規のフローが最高の優先順位を持つものと仮定し、全てのサービスクラスに関してアドミッション制御状態を検査する。このことは、次のような形で示すことができる。すなわち、各サービスクラスに関して、到着集約トラフィックの包絡線ＬｑＮｑ（τ；εｑ／２）とサービス曲線Ｓｑ（・）を求める。等式（２）から、到着包絡線Ｌｎｅｗ（τ；εｑ／２）を有する新規のフローは、全てのサービスクラスｑに関して次の条件を満たすとき、進入を許可される。
【００６３】
【数２４】
0003597505.tif 000025
【００６４】
本節では、測定に基づく包絡線（ＬＮ（・；ε）とＳ（・））に依存するＣＡＣを示した。これらの包絡線を求める方法については後節で示す。
【００６５】
全域有効包絡線とサービス曲線を用いた確率的保証
まず最初に、単一サービスクラスについて考察し、指数ｑを落とす。時間間隔（ｔ１，  ｔ２）における同じサービスクラスからの到着トラフィックの集約ＡＮ（ｔ１，  ｔ２）は、同じＱｏＳ要件、すなわち、同じ遅延違反確率εと同じ遅延限界要件ｄを有している。ＡＮ（ｔ１，  ｔ２）は、負ではないランダム処理群によって特徴付けされる。すなわち、ＡＮ（ｔ１，  ｔ２）は、（１）統計的特性が経時的に変化しない定常性と、（２）全てのサービスクラス間で確率的に独立である独立性を有している。ここで、最大ビジー周期の時間間隔βを考える。最大ビジー周期の間の時刻ｔにドメインに到着するＮ個のフローからなる集約トラフィックの１ビットが被る入口出口間遅延をＤＮ（ｔ）とし、ＤＮ（ｔ）がランダム変数であると仮定する。遅延限界ｄが与えられると、ドメインは、あらゆる到着ビットの入口出口間遅延が遅延限界ｄを超えないことを保証する。すなわち、任意のτで０  ≦τ≦  βについて、等式（２．８）から
【数２５】
0003597505.tif 000026
が成立すること、あるいは、任意のτで０  ≦τ≦  βについて、
【数２６】
0003597505.tif 000027
が成立することを保証する。
【００６６】
ＤＮ（ｔ）  ≧  ｄとなるようなＤＮ（ｔ）が存在する場合、あるいは、
【数２７】
0003597505.tif 000028
となるようなｔとτが存在する場合に遅延違反が生起する。
【００６７】
等式（３．２）の場合、到着トラフィックが遅延違反を被る確率は、εによって限定される必要があり、以下の数式
【数２８】
0003597505.tif 000029
が成立する。
【００６８】
新規のフロー群はＤＳドメインから同じサービス保証を要求する。ＣＡＣは、アドミッション制御テストを利用して、要求されたサービス保証と全てのサービスクラスからの他のフローが確実に同時に満たされるようにする。等式（３．４）から、以下の全域有効包絡線の定義を利用して単一サービスクラスの場合のアドミッション制御状態を求めることができる。
【００６９】
（全域有効包絡線の定義）
時間間隔βの全域有効包絡線は、以下の数式
【数２９】
0003597505.tif 000030
を満たす劣加法的関数ＧＮ（τ；β，ε）である。この式から、全域有効包絡線が時間間隔β内のいかなる特定時間間隔τにおいても集約トラフィックＡＮ（ｔ，  ｔ＋τ）に対して確率的限界を付与することがわかる。
【００７０】
（補助定理）
Ｍ個のクラスに分類されるフロー群が与えられ、各クラスが到着集約トラフィックＡＮｍにＮｍ個のフローを含んでいるものとする。クラスｍの全域有効包絡線をＧＮｍ（τ；β，ε）とし、ｘが与えられると、以下の不等式が成立する。
【００７１】
【数３０】
0003597505.tif 000031
【００７２】
同じサービスクラスからのフローを２つのカテゴリーに分類する。すなわち、Ｍ＝２とする。最初のグループはフロー群Ｎであり、既にドメインへの進入が許可されている。２番目のグループは新規のフロー群Ｋであり、ＤＳドメインからのＱｏＳサービスを要求している。最初のグループの全域有効包絡線をＧＮで表し、２番目のグループの全域有効包絡線をＧｎｅｗで表す。
【００７３】
（単一サービスクラスの場合のアドミッション制御状態）
上記全域有効包絡線の定義と補助定理及び等式（３．４）から、
【数３１】
0003597505.tif 000032
ならば、到着トラフィックの遅延違反確率はεより低い。但し、
１．同じサービスクラスに関して、新規のフロー群が同じ決定的包絡線Ａ＊ｊを有する場合にそれぞれ異なる決定的包絡線Ａ＊ｊによって調整される場合は、
【数３２】
0003597505.tif 000033
のとき、それぞれＧｊｎｅｗ（・；β，εｊ）を作成することが必要である。したがって、等式（３．５）は以下のようになる。
【００７４】
【数３３】
0003597505.tif 000034
【００７５】
２．等式（３．５）のＣＡＣは、ドメインの接続形態とドメイン内のスケジュ−リング  アルゴリズムに依存しないが、ＤＳドメインの入口ノードと出口ノードで測定可能  な、測定に基づくトラフィック特徴付け包絡線には依存する。
【００７６】
（全域有効包絡線の作成）
進入許可されたフロー群Ｎについて考察する。各フローの基本的な配分の知識を必要としない中心極限定理を用いて集約トラフィックの配分を特徴付けることとする。集約トラフィックの近似全域有効包絡線は、中心極限定理から次のようにして求めることができる。全域有効包絡線の定義から、
【数３４】
0003597505.tif 000035
を設定する。τ０とβが与えられると、任意の整数ｋに関して、以下の式を得る。
【００７７】
【数３５】
0003597505.tif 000036
但し、α＝１＋１／（ｋ＋１）で、ｚ´はε´＝τ０  （α−１）  ε／βｋの場合にその近似値
【数３６】
0003597505.tif 000037
を有しており、
【数３７】
0003597505.tif 000038
とσ２（τ）はそれぞれ測定された集約トラフィック量の平均と分散である。これらの測定方法については次の節で説明する。
【００７８】
等式（３．４）から、全域有効包絡線がいくつか存在し得ることがわかる。この方法は、τ０とβが与えられると、１  ≦  ｉ  ≦  ｎの場合、以下のｋｉ，  αｉ及びτｉを再帰的に算出する。但し、τｎはβよりも大きい第１の点である。したがって、全域有効包絡線のｎ個の点を次のようにして求めることができる。
【００７９】
【数３８】
0003597505.tif 000039
【００８０】
さらに、等式（３．７）から、
【数３９】
0003597505.tif 000040
但し、
【数４０】
0003597505.tif 000041
である。
【００８１】
新規のフロー群の場合も、同じ再帰的方法を用いて新規のフローＧｎｅｗの全域有効包絡線を求めることができる。しかしながら、等式（３．８）及び等式（３．１１）においては、上記測定に基づく集約トラフィック量の平均Ｘ（τ）と分散σ２（τ）の代わりに、それぞれＫρＫτとＫρＫτ（ＡＫ＊（τ）  −  ρＫτ）を使用する。但し、ρＫは長期間平均であり、ＡＫ＊（τ）は各新規フローの決定的包絡線である。
【００８２】
（多重サービスクラスの場合のアドミッション制御状態）
等式（３．２）のアドミッション制御状態は、新規フロー群がドメイン内への進入を許可された場合に、他のサービスクラスが同じ入口から出口までの経路を使用するというＱｏＳ要件を満たすことを保証しない。汎用性を損なうことなくそのことを保証できるようにするため、新規のフローが最高の優先順位を持つものと仮定し、全てのサービスクラスに関してアドミッション制御状態を検査する。このことは、次のような形で示すことができる。すなわち、各サービスクラスに関して、到着集約トラフィックの包絡線ＧｑＮｑ（τ；β，εｑ／２）とサービス曲線Ｓｑ（・）を求める。等式（３．５）から、到着包絡線Ｇｎｅｗ（τ；β，εｑ／２）を有する新規のフローは、全てのサービスクラスｑに関して次の条件を満たすとき、進入を許可される。
【００８３】
【数４１】
0003597505.tif 000042
【００８４】
本節では、測定に基づく包絡線（ＧＮ（・；β，ε）とＳ（・））に依存するＣＡＣを示した。これらの包絡線を求める方法については、次の節で示す。
【００８５】
透視包絡線の測定方法
本節では、単一サービスクラスの場合の到着集約トラフィックの全域有効包絡線と退去集約トラフィックのサービス包絡線を作成するために特徴パラメータを測定する方法を説明する。先ず最初に、等式（３．３）で使用される到着集約トラフィック量の平均と分散を測定する。その後、単一サービスクラスのトラフィックのサービス包絡線を測定する。本アドミッション制御アルゴリズムを使用した評価例については後述する。
【００８６】
（集約到着包絡線の測定）
入口ノードでの到着トラフィックの集約された特性を考察する。集約トラフィックを１つのガウス過程として特徴付けるためには、入口ノードでの到着トラフィック量の一次および二次モーメントを測定する必要がある。但し、到着トラフィックレートの平均と分散を測定するにあたり、ここでは、到着トラフィック量の平均と分散を測定する。時間間隔（ｔ１，  ｔ２）における集約フローからの到着トラフィックをＡＮ（ｔ１，  ｔ２）とする。時間を同じ長さτ単位で分割する。すなわち、ＭＰＥＧソースの場合には、τをフレーム時間と見なすことができる。また、時間を長さＴのＭ個の大きな間隔にも区分する（図５参照）。ｍ番目の時間間隔について、到着トラフィックの限界Ｘｍｋを時間間隔ｋτの関数として求める。現在時刻をｔとすると、現在時刻から長さＴのｍ番目の時間間隔を超える測定トラフィック量の限界は、ｍ  ＝  １，  …，  Ｍ及びｋ  ＝  １，  …，  Ｔ／τの場合、以下のようにして求めることができる。
【００８７】
【数４２】
0003597505.tif 000043
【００８８】
したがって、任意のＴ時間帯に関して、包絡線限界Ｘｍｋが求められる。これらの包絡線から、測定された包絡線の平均
【数４３】
0003597505.tif 000044
と分散
【数４４】
0003597505.tif 000045
を求めることができる。
【００８９】
但し、τ、Ｔ及びＭは測定の主要なパラメータである。τ、Ｔ及びＭの値の選択が不適切であれば、到着集約トラフィックを不精確に特徴付けてしまうこと、ひいては、コネクションが要求する帯域幅を過大評価してしまうことがある。本発明の方法では、これらのパラメータを変動させた。その結果、本発明の方法がパラメータの変化に特に敏感ではないことがわかった。パラメータの選択方法に関するより詳細な説明は、２０００年３月、イスラエル、テルアビブでのＩＥＥＥ  Ｉｎｆｏ  Ｃｏｍ  ２０００の議事録におけるＣ．センチンカヤ（Ｃ．  Ｃｅｎｔｉｎｋａｙａ）とＥ．ナイトリー（Ｅ．  Ｋｎｉｇｈｔｌｙ）の論文「出口アドミッション制御（Ｅｇｒｅｓｓ  Ａｄｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ）」及び１９９７年４月、神戸でのＩＥＥＥ  Ｉｎｆｏ  Ｃｏｍ  １９９７の議事録におけるＤ．ツェ（Ｄ．  Ｔｓｅ）及びＭ．グロスグロウサー（Ｍ．  Ｇｒｏｓｓｇｌａｕｓｅｒ）の論文「測定に基づくコールアドミッション制御：解析とシミュレーション（Ｍｅａｓｕｒｅｍｅｎｔ−ｂａｓｅｄ  Ｃａｌｌ  Ａｄｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  ：  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｓｉｍｕｌａｔｉｏｎ）」で知ることができる。
【００９０】
図６（ａ）及び図６（ｂ）のシミュレーション実験から到着包絡線の一例を示す。図６（ａ）では、時間間隔を横軸にとって到着集約トラフィック量を示し、図６（ｂ）では、時間間隔を横軸にとって到着集約トラフィックレートを示した。シミュレーションは、１２０回の多重化独立ＭＰＥＧ−２画像トレースから構成された。これらのトレースは、映画「スターシップ・トゥルーパーズ」（以下、「スターシップ」と称する）から得た。「スターシップ」は１８．６３３６  Ｍｂｐｓのピークレートと４．２６  Ｍｂｐｓの平均レートを有している。「スターシップ」のフレームレートは、１秒あたり３０フレームである。このトラフィックタイプは、非常に高いピーク対平均比を有しており、それは、バースト性が大きいことを示している。図６から、到着包絡線（Ａｒｒｉｖａｌ  Ｅｎｖ．）と到着レート（Ａｒｒｉｖａｌ  Ｒａｔｅ）はそれぞれピーク包絡線（Ｐｅａｋ  Ｅｎｖ．）とピークレート（Ｐｅａｋ  Ｒａｔｅ）よりも非常に小さいことがわかる。それは、集約トラフィックの統計的多重化によるものである。図に示すように、長い時間間隔が与えられると、到着トラフィック包絡線（到着トラフィック量）と到着レートはそれぞれ平均包絡線（Ａｖｅｒａｇｅ  Ｅｎｖ．）と平均レート（Ａｖｅｒａｇｅ  Ｒａｔｅ）に向かって減少する。
【００９１】
集約サービス包絡線の測定
ＤＳドメインの入口ノードに到着するトラフィックと出口ノードから退去するトラフィックについて考察する。サービス包絡線を測定するため、ドメイン内のクロックは同期化されているものと仮定する。パケットが、連続時間ではなく、離散時間で処理されるパケットシステムを考える。入口ノードに到着する各パケットは、時刻表示される。したがって、出口ノードでは、各パケットの入口出口間遅延を測定することができる。ｊ番目のパケットの到着時刻をａｊで示し、退去時刻をｄｊで示す。このトラフィックは、システム内に少なくとも１個のパケットが存在する場合には常に待ち行列に入るものとみなす。待ち行列の状態は、パケットの到着時刻と退去時刻を比較することによって検査することができる。トラフィックは、ｋ  ≧  １の場合に、
任意の０  ≦  ｍ  ≦  ｋ  −  ２について、ｄｊ＋ｍ  ＞  ａｊ＋ｍ＋１                      （４．４）
ならば、時間間隔［ａｊ，  ｄｊ＋ｋ−１］内のｋ個のパケットに関して連続的に待ち行列に入る。
【００９２】
次に、持ち行列パケット数ｋの状態でパケットｊを見たときに、ｘ個のビットを処理するのに必要な時間量Ｓｋｊ（ｘ）を表わす対（ｘ，  Ｓｋｊ（ｘ））を含んだリストをＳｅｒｖＥｎｖとする。総数ｎの到着パケットを含む時間間隔Ｔについて考える。パケットｊについて、このパケットの遅延とこのパケットの後に待ち行列に入ったパケットの遅延とを考察すると、以下のようにしてＳｋｊ（ｘ）を定義することができる。すなわち、任意のｋ  ≧  １について
Ｓｋｊ（ｘ）  ＝  ｄｊ＋ｋ−１  −  ａｊ                                                                          （４．５）
これにより、待ち行列条件が満たされる。
【００９３】
サービス包絡線の限界値は、次の表１に示すサービス包絡線限界アルゴリズムに従って求められる。
【００９４】
【表１】
0003597505.tif 000046
【００９５】
図７（ａ）は、シミュレーションから得られた退去集約トラフィックのサービス包絡線を示す。このシミュレーションは、６２２Ｍｂｐｓのリンク容量を有するノードと、図６（ａ）及び図６（ｂ）で使用されたものと同じ数のソース（「スターシップ」）とから構成されている。包絡線は増加関数である。さらに、図７（ｂ）はサービス包絡線の勾配を表す。包絡線の勾配は、到着集約フローのバースト性に関するサービスレートの変動を示す。
【００９６】
（局所有効包絡線を用いたアドミッション制御アルゴリズム）
１．ＤＳドメインからトラフィックのＱｏＳを要求するため、ユーザが、帯域幅ブローカに対して決定的包絡線Ａｊ＊（τ）、Ｑｏｓ要件、遅延限界ｄ及び遅延違反確率εを含むトラフィック特性を申告する。
【００９７】
２．ＣＡＣが、申告されたパラメータに基づき、等式（７）及び等式（８）を用いて局所有効包絡線Ｌｎｅｗを作成する。
【００９８】
３．さらに、ＣＡＣが、到着トラフィックの平均と分散の測定値を利用して、等式（４）から別の局所有効包絡線ＬｑＮｑを作成する。
【００９９】
４．最後に、ＣＡＣが、Ｌｎｅｗと、ＬｑＮｑと、Ｓｑとに基づいてアドミッション制御を決定する。この要求は、等式（９）の条件が真である場合に許可される。
【０１００】
（全域有効包絡線を用いたアドミッション制御アルゴリズム）
１．ＤＳドメインからトラフィックのＱｏＳを要求するため、ユーザが、帯域幅ブローカに対して決定的包絡線Ａｊ＊（τ）、Ｑｏｓ要件、遅延限界ｄ及び遅延違反確率εを含むトラフィック特性を申告する。
【０１０１】
２．ＣＡＣが、申告されたパラメータに基づき、等式（３．８）ないし等式（３．１１）を用いて全域有効包絡線Ｇｎｅｗを作成する。
【０１０２】
３．さらに、ＣＡＣが、（それぞれ等式（４．２）と等式（４．３）から得られた）到着トラフィックの平均と分散の測定値を利用して、等式（３．８）ないし等式（３．１１）から別の全域有効包絡線ＧｑＮｑを作成する。
【０１０３】
４．最後に、ＣＡＣが、Ｇｎｅｗと、ＧｑＮｑと、Ｓｑとに基づいてアドミッション制御を決定する。この要求は、等式（３．１２）の条件が真である場合に許可される。
【０１０４】
評価及びシミュレーション結果
本節では、ＣＡＣ状態の有効性を評価する。全てのフローが同質である、すなわち、全てのフローが同じ決定的包絡線を有し、ＤＳドメインからの同じ遅延ＱｏＳ保証を要求するものとした。「スターシップ」をトラフィックソースとして利用した。シミュレーションにおいては、遅延違反確率ε＝  １０−６を設定し、遅延限界要件ｄを変化させた。ＤＳドメインは６２２Ｍｂｐｓのリンク容量（全てのシミュレーションに関してＣ  ＝  ６２２  Ｍｂｐｓ）を有する出口ノードを備えているものとした。ドメイン内の全てのリンクは出口リンクと同じ容量を有しているものとした。各ノードはＦＩＦＯスケジューラを有しているものとした。ドメイン内のノード数とクロストラフィックが以下のように変わる３つのシナリオについて考察した。
【０１０５】
１．ＤＳドメインが、クロストラフィックのない１個のノードから構成される（図８（ａ）参照）。
【０１０６】
２．ＤＳドメインが、クロストラフィックのない２個のノードから構成される（図８（ｂ）参照）。
【０１０７】
３．ＤＳドメインが、クロストラフィックのない３個のノードから構成される（図８（ｂ）参照）。
【０１０８】
なお、３番目の構成においては、主トラフィックと同じＱｏＳ要件を有するクロストラフィックとして４０フローの「スターシップ」を使用した。
【０１０９】
上述のＣＡＣアルゴリズムを利用して本方法（図面では、Ａｐｐｒｏａｃｈで示す）を評価した。本方法のベンチマークとして、以下の２つの方法と一連のシミュレーション（図面では、Ｓｉｍｕｌａｔｉｏｎで示す）についても調査した。最初に、許可可能な最大フロー数が各フローの長期間の平均レートにより分割されたリンク容量によって決まる、したがって、平均リンク利用率が１である平均レート割当て（図面では、Ａｖｅｒａｇｅ  Ｒａｔｅで示す）について考察した。次に、許可可能な最大フロー数が各フローのピークレートによって分割されたリンク容量によって決まるピークレート割当て（図面では、Ｐｅａｋ  Ｒａｔｅで示す）について考察した。シミュレーションのため、各フローはＤＳドメイン内にランダムにトラフィックの送信を開始した。多数のシミュレーションが実行された。シミュレーションの結果の平均を示す。各方法によって得られた平均リンク利用率Ｕａｖｅを比較した。Ｕａｖｅは以下のように定義される。
【０１１０】
【数４５】
0003597505.tif 000047
但し、Ｎはドメインに進入許可されたコネクションの数、ρｊは各フローの長期間平均レート、Ｃは出口ノードのリンク容量である。
【０１１１】
図８（ａ）ないし図８（ｃ）は、調査した３つのシナリオと、遅延限界と平均リンク利用率との関係を示すそれぞれの結果を示す。これらの結果から、シミュレーション及び本発明の方法によって得られるリンク利用率がピークレート割当てによるものよりもかなり高いことがわかる。このことは、シミュレーションと本発明の方法が集約トラフィックから多重の利得を利用しており、高いリンク利用率を実現することを示している。例えば、図８（ａ）から、遅延限界ｄ  ＝  １０  ｍｓｅｃの場合に、シミュレーションと本方法は、８６％のリンク利用率を実現している。その一方で、ピークレート割当ての場合は、８２％しか得ていない。さらに、この結果は、本発明の方法が到着集約トラフィックと退去集約トラフィックを精確に特徴付けできることを示している。図８（ｂ）及び図８（ｃ）は、本発明の方法が基本的な接続構成やクロストラフィックについて知らなくてもドメインの精確な状態を入手でき、シミュレーション結果に近いリンク利用率を実現できることを示している。
【０１１２】
以上のことから分かるように、本発明によれば、全域有効包絡線とサービス包絡線を利用して到着集約トラフィックと退去集約トラフィックを精確に特徴付けする、測定に基づくアドミッション制御アルゴリズムを実現することができる。測定に基づき、ＣＡＣアルゴリズムはパラメータ群によって調整可能である。また、ＣＡＣアルゴリズムは、スケーラブルであり、様々なサービスクラスをサポートすることができる。
【０１１３】
以上、本ＣＡＣアルゴリズムによって得られるリンク利用率とシミュレーション結果とを比較することにより、ＣＡＣアルゴリズムの有効性を示した。本明細書では、本発明をその好ましい実施形態の形で説明したが、本発明の原理を多数のアプリケーションに適用することが可能であり、本アルゴリズムの実施の詳細を特許請求の範囲に記載した本発明の精神から逸脱することなく変更可能であることは言うまでもない。
【図面の簡単な説明】
【図１】本発明のアドミッション制御アルゴリズムを理解するのに役立つ、エンドツーエンドネットワークモデルの一例を示すネットワーク図。
【図２】ネットワーク内の到着トラフィックと進入許可トラフィックに関連するパラメータを示すブロック図。
【図３ａ】全域有効包絡線を説明する、好ましいアドミッション制御アルゴリズムのフロー図。
【図３ｂ】局所有効包絡線を説明する、好ましいアドミッション制御アルゴリズムのフロー図。
【図４】遅延限界の算出を説明するグラフ。
【図５】Ｔ  ＝  ３τかつＭ  ＝  ２のときに測定された時間間隔の一例を示すタイミング図。
【図６】（ａ）および（ｂ）は時間間隔ｋτが１００ｍｓまでの間で測定された到着トラフィックを示すグラフである。
【図７】（ａ）および（ｂ）は時間間隔が１００ｍｓまでの間で測定されたサービス包絡線を示すグラフである。
【図８】（ａ）、（ｂ）および（ｃ）は遅延限界ｄが１００ｍｓまでの間で３種類の異なるシナリオにおいてそれぞれ遅延限界を横軸にとって表した平均リンク利用率を示すグラフである。
【符号の説明】
１０、２４、３２    ネットワーク
１２、１４    エッジルータ
１６    コアルータ
２６    エッジルータ
６６    到着トラフィックの有効包絡線
７２    進入許可トラフィックの有効包絡線
【図１】
0003597505.tif 000048
【図２】
0003597505.tif 000049
【図３ａ】
0003597505.tif 000050
【図３ｂ】
0003597505.tif 000051
【図４】
0003597505.tif 000052
【図５】
0003597505.tif 000053
【図６】
0003597505.tif 000054
【図７】
0003597505.tif 000055
【図８】
0003597505.tif 000056