(57)【特許請求の範囲】
【請求項１】
パケット化通信ネットワークのサーバのためのコネクション受付制御方法において、
前記サーバは、受付パケットのＥＤＦスケジューリングを行い、パケットの全処理レートを有し、
前記方法は、
（ａ）複数のクラスｃのそれぞれについて、現在申告されているクラスｃのセッションを含む、現在サービスされているクラスｃのセッションの数Ｎcを表す動作点を定義するステップと、
（ｂ）定義された動作点が、可能な動作点の空間の受付可能領域内にあるかどうかを判断するステップとを有し、
各クラスｃはピークトラフィックレートｒ（ｃ）を有し、
前記受付可能領域は、すべてのセッションがそれぞれの最大到着レートでパケットのバーストを同時に送信開始した場合に少なくともいくつかのパケットが受付を拒否されるような少なくとも１つの点を含み、
各パケットは、指定された遅延限界より長く遅延する確率（以下「違反確率」という）を有し、前記受付可能領域は、指定された限界より大きい違反確率を有するパケットがサーバにより処理されないことを保証するように選択され、
前記違反確率は、前記サーバが受付パケットのＥＤＦスケジューリングのために構成されていることを考慮に入れて計算されることを特徴とするコネクション受付制御方法。
【請求項２】
前記受付可能領域は、各セッションに対して、パケット到着のパターンをサーバの処理容量と比較することによって違反確率が部分的に計算されるという性質を有することを特徴とする請求項１に記載の方法。
【請求項３】
前記パケット到着のパターンは、最後の時点が、有効パケット到着時刻ａであるか、または、それより１遅延限界以下の増分だけ後の時刻である離散時点系列に関して定義され、
前記違反確率は、前記最後の時点を除く前記系列の任意の時点ｙに対して、ｙとａの間に到着するパケットの累積量が、
（ｉ）前記系列に属し、時間的にｙの次に来る時点と、
（ｉｉ）時点ａ＋Ｔと
の間に前記サーバが処理可能な全パケット量を超える確率として推定されることを特徴とする請求項２に記載の方法。
【請求項４】
前記サーバは、少なくとも１つの別のサーバを含む申告されたセッションの経路に沿った最初のサーバであり、
前記経路に含まれるすべてのサーバにわたって生じる、前記セッションのパケットの全遅延に対する限界が指定され、
前記方法は、
前記経路に含まれる各サーバごとに個別の遅延限界を指定するステップをさらに有することを特徴とする請求項１に記載の方法。
【請求項５】
個別のサーバに対する遅延限界は、個々の遅延限界の和が全遅延限界になるように全遅延限界を分割することにより指定されることを特徴とする請求項４に記載の方法。
【請求項６】
前記全遅延限界は、第１部分と第２部分に分割され、
前記第２部分は、個々のサーバのそれぞれの全パケット処理レートに比例して、個々のサーバの遅延限界に割り当てられ、
最初のサーバに割り当てられる遅延限界は、
（ｉ）前記全遅延限界の第１部分と、
（ｉｉ）前記全遅延限界の第２部分のうち前記最初のサーバに割り当てられる部分と
の和であり、
別のサーバのそれぞれに割り当てられる遅延限界は、前記第２部分のうち該別のサーバに割り当てられる部分であることを特徴とする請求項５に記載の方法。
【請求項７】
各サーバの受付可能領域は、各セッションに対して、パケット到着のパターンをサーバの処理容量と比較することによって違反確率が部分的に計算されるという性質を有し、
前記パケット到着のパターンは、最後の時点が、有効パケット到着時刻ａであるか、または、それより１遅延限界以下の増分だけ後の時刻である離散時点系列に関して定義され、
前記違反確率は、前記最後の時点を除く前記系列の任意の時点ｙに対して、ｙとａの間に到着するパケットの累積量が、
（ｉ）前記系列に属し、時間的にｙの次に来る時点と、
（ｉｉ）時点ａ＋Ｔと
の間に前記サーバが処理可能な全パケット量を超える確率として推定され、
違反確率を推定する目的では、前記最初のサーバへのパケットの有効到着時刻は実際の到着時刻であり、
前記目的では、前記別のサーバのそれぞれへのパケットの有効到着時刻は擬似到着時刻であり、
それぞれの擬似到着時刻は、
（ｉ）前のサーバへの有効パケット到着時刻と、
（ｉｉ）前のサーバに対して指定された遅延限界と
の和に等しいことを特徴とする請求項５に記載の方法。
【請求項８】
前記判断するステップは、可能な動作点の空間の記憶された表現において前記定義された動作点を探索するステップを有することを特徴とする請求項１に記載の方法。
【請求項９】
前記判断するステップは、現在申告されているセッションのパケットが、指定された限界より高い違反確率を有するかどうかを判断するための計算を実行するステップを有することを特徴とする請求項１に記載の方法。
【請求項１０】
前記受付可能領域は、各セッションに対して、パケット到着のパターンをサーバの処理容量と比較することによって前記計算が部分的に実行されるという性質を有することを特徴とする請求項９に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケット化通信ネットワークにおけるコネクション受付制御（ＣＡＣ：Connection Admission Control）の方法に関し、特に、最先期限優先（ＥＤＦ：Earliest-Deadline-First）スケジューリング規律を適用したネットワークにおけるＣＡＣに関する。
【０００２】
【従来の技術】
図１は、ユーザ１０．１〜１０．３、１２．１〜１２．４、および１５．１〜１５．３が、相互接続されたサーバあるいは交換機２０．１〜２０．５を通じて相互に通信することが可能な、単純化されたパケットネットワークの概略図である。このネットワークは例示のために単純化されている。現実のネットワークは一般に、図示したよりも多くのユーザおよびサーバを有する。例えば、ユーザ１０．１がネットワークを通じてユーザ１５．１につなぎたい場合、ユーザ１０．１は、セッションを設定する要求を、関連するサーバ２０．１へ発する。セッションとは、ソースからデスティネーションまでの固定されたパスを有する関連するパケットの集まりであって、パケット注入レート、バーストサイズ、および最大パケット長のような指定された性質の記述を有するものである。この固定パスは通常、ユーザが設定要求を行うときに決定されるが、最初のサーバ２０．１によって決定されることもある。設定要求は、このパスに沿ったすべてのサーバに渡される。各サーバは、要求されたセッションを受け付けるかどうかを決定するコネクション受付制御（ＣＡＣ）という機能に関わる。セッションが、パスに沿ったすべてのサーバによって受け付けられた場合、設定要求は受け入れられ、パケットを送ることができる。
【０００３】
各サーバｅは、有限の処理レートＣeを有する。すなわち、各サーバｅは、単位時間あたりＣeビット以下のレートで、待ち合わせているパケットを次のサーバに（あるいは、最後のサーバからデスティネーションユーザに）中継することができる。この処理レートが有限であるため、一般に、一部のビットは、パスに沿ったサーバの一部または全部で遅延を生じることになる。
【０００４】
過大なパケット遅延は、さまざまな種類のネットワークトラフィックの顧客にとって許容できないことがある（例えば、音声トラフィックは、遅延に敏感であることで知られている）。とりわけ、サービス品質（ＱｏＳ）要求の標題のもとでネットワークに要求される遅延パフォーマンスを指定することに関心が高まっている。この点に関して、通常のＱｏＳ要求は、指定されたサービスクラスにおけるパケット遅延は、指定されたしきい値より常に小さくなければならない、あるいは（確率的な要求である場合）パケット遅延がしきい値を超えるのは指定された確率以下でなければならない、というものである。
【０００５】
ＱｏＳ要求に従うネットワークでは、ＣＡＣ機能は、遅延に対して指定された制限を満たすことが可能かどうかを考慮することになる。指定された制限を満たすことができないと判断される場合、申告されたセッションは拒否されるセッションとなる。このような制限が満たされるかどうかは、部分的には、サーバのリソースがどのようにセッションどうしの間で割り当てられるかに依存する。（なお、ここで用いる「セッション」という用語は、ここでの文脈に当てはまる意味において、「コネクション」という用語と同義語である。）このような割当ては、いわゆるスケジューリング規律によって支配される。２つの著名なスケジューリング規律として、一般化プロセッサ共有（ＧＰＳ：Generalized Processor Sharing）と最先期限優先（ＥＤＦ）がある。ＧＰＳの下では、サーバは、そのリソースを、指定された重みに従ってコネクションどうしの間で分割する。ＥＤＦの下では、サーバは、各入力パケットｐに、到着時に期限（デッドライン）ｄpを割り当て、常に、最先の期限のパケットにサービスする。与えられたネットワーク状態に対して、それぞれのスケジューリング規律は、新たに申告されたセッションの受付可能性に関して異なる判定を導くことがある。
【０００６】
遅延に基づく受付判定へのほとんどのアプローチは、最悪の場合の仮定（例えば、すべてのセッションがピークとお茶クレーとでパケットのバーストを同時に送信する）に基づいている。このような仮定に基づくアプローチは、過大な数の呼への受付を拒否するため、不利である。伝送されるトラフィックの量についての多少の改善が、少なくとも研究段階としては、統計的多重化というアプローチを通じて達成されている。これは、確率的遅延限界を守りながら、より多くの申告されたセッションを受け入れるために、申告されたトラフィックの統計的性質を利用する。ＧＰＳスケジューリングに適用した統計的多重化については、例えば、A. Elwalid et al., "Design of generalized processor sharing schedulers which statistically multiplex heterogeneous QoS classes", Proc. IEEE INFOCOM '99 (March 1999) 1220-1230、および、K. Kumaran et al., "Novel techniques for the design and control of Generalized Processor Sharing schedulers for multiple QoS classes", submitted for publication in Proc. IEEE INFOCOM '00 (March 2000)、に記載されている。
【０００７】
【発明が解決しようとする課題】
しかし、今までのところ、ＥＤＦスケジューリング規律の下で、遅延に基づく受付判定に統計的多重化を適用したものはない。
【０００８】
【課題を解決するための手段】
本発明では、ＥＤＦスケジューリング規律の下で、パケット遅延限界に違反する確率を推定する新しい方法を開発した。本発明の方法は、申告されたネットワークトラフィックの統計的性質を考慮に入れることにより、統計的多重化の範囲に入る。本発明の方法によれば、ＥＤＦを使用するサーバが、申告されたトラフィックに関する最悪の仮定に基づく旧式のＣＡＣ法を用いて可能となるより多くの申告されたセッションを受け付けながら、確率的なＱｏＳ要求を満たすことが可能となる。
【０００９】
すなわち、本発明の１つの特徴によれば、パケット化通信ネットワークにおいてサーバへの指定されたクラスのトラフィックの申告されたセッションの受付可能性を決定する方法が実現される。各クラスｃは、ピークトラフィックレートｒ（ｃ）を有する。サーバは、全処理レートＣを有する。受け付けられるパケットは、ＥＤＦスケジューリング規律に従ってスケジューリングされる。本発明による受付可能性を決定する方法は、サーバの動作点を定義するステップを含む。動作点は、現在申告されている、または、現在サービスされている、各クラスのセッション数Ｎcを表す。本発明の方法はさらに、定義した動作点が、受付可能領域を定義する動作点セット内に入るかどうかを判断するステップを含む。受付可能領域は、いずれかのパケットに対して遅延限界に違反する確率があるしきい値を下回る動作点からなる。従来技術の方法とは異なり、受付可能領域は、すべてのセッションがピーク到着レートでパケットのバーストを同時に送信し始めたとしてもパケット遅延限界の違反となる、少なくとも１つの点を含む。
【００１０】
【発明の実施の形態】
図２に、サーバ２５のいくつかの機能を模式的に示す。ブロック３０は、セッション設定要求を受け取り、ＣＡＣを実行し、設定要求が受け入れられるかどうかの確認を返す。要求が受け入れられる場合、設定要求は下流の次のサーバに渡される。設定要求が、ソースからデスティネーションまでの要求されたパスに沿ったすべてのサーバで受け入れられる場合、設定動作が実行される。ブロック３５は、入力パケットを受け取り、それを処理するためのスケジューリングを行い、処理が進むにつれて、出力パケットを下流の次のサーバに送る。ブロック３５は、最後のサーバにある場合、処理したパケットをそのデスティネーションに送る。
【００１１】
新たなセッションを求めるそれぞれの設定要求は、そのセッションを特徴づける記述的情報を含む。ｉ番目のセッションに対するそのような情報は通常、平均トラフィック到着レートρi（単位は例えば毎秒ビット）、ピークトラフィック到着レートｒi、バーストサイズσi、最大パケットサイズＬi、遅延限界Ｔi、および最大許容違反確率δiを含む。遅延に対するＱｏＳ要求は、申告されたセッションのいずれかのパケットがＴiより遅れる確率はδi以下、すなわち、Ｐｒ［パケットｐの遅延＞Ｔi］≦δi、というものである。
【００１２】
重要な点であるが、上記のような情報は、トラフィックの複数のクラスごとに記憶されることが可能である。このような記憶情報が利用可能な場合、到来する要求は、関連するクラスを識別するインデックスの値を提供すれば十分である。また、以下で説明する方法の応用では、申告されたセッションにおけるパケット到着時刻およびパケットサイズの統計分布の形についてのいくつかの仮定も要求する。ポアソン到着のような、１つの一般的に適用可能な分布を、トラフィックのすべてのクラスについて仮定することができる。あるいは、さらに有利な点であるが、各クラスに特定の分布を対応させることも可能である。その分布の識別（または記述）は、関連するクラスを記述する記憶情報に含めることが可能である。
【００１３】
図３に、本発明の一実施例による例示的な受付制御手続きを示す。ブロック４０で、セッションｉに対する設定要求を受け取る。ブロック４５で、パケット到着統計、ならびに遅延限界および最大許容違反確率の記述を読み出す。ブロック５０で、パケット到着過程についての与えられた情報および（与えられた、または、仮定された）統計モデルに関して、パケット期限違反確率（ＰＤＶＰ：packet-deadline violation probability）を推定するための計算を実行する。この計算の例については後述する。ブロック５５で、ＰＤＶＰを、最大許容違反確率δiと比較する。ＰＤＶＰがδiを超えない場合、ブロック６０に示すように、申告されたセッションは受付可能であるとみなされる。そうでない場合、ブロック６５に示すように、申告されたセッションは拒否される。
【００１４】
上記のように、設定要求は、記述的情報の明示的なセットを含むことは必ずしも要求されない。その代わりに、設定情報は、申告されたセッションが属するクラスを識別するインデックスの値を提供することも可能である。その場合、記述的情報は、記憶されたデータベースから得られる。
【００１５】
さまざまなクラスのトラフィックの統計的性質が事前に既知である場合、オフライン計算により、与えられた申告されたセッションが受付可能であるかどうかを判断する有用なツールとして作用する状態図を構成することが可能である。このような状態図は、トラフィックのクラスの個数だけのデカルト座標軸を有する数学的空間を占有する。サーバの各「状態」は、順序付きのｎ項組として表現可能であり、その各成分は、現在進行中の対応するクラスのセッション数を表す。
【００１６】
例えば、図４は、クラスＩ（横軸）およびクラスＩＩ（縦軸）という２つのクラスのみのトラフィックをサポートする例示的なサーバの状態図である。各状態は、図４では、離散的な点として表現され、その水平位置はクラスＩセッションの個数（「クラスＩ要素数」）を示し、垂直位置はクラスＩＩセッションの個数（「クラスＩＩ要素数」）を示す。図の境界７０は、受付可能領域を画する。受付可能領域は、境界７０と座標軸によって定められる。表現点が境界の座標原点に近い側にある状態は受付可能であり、表現点が境界の座標原点から遠い側にある状態は受付可能でない。
【００１７】
図４の２次元状態図に示したような直線上の境界は、３次元における平面上の境界や、４以上の次元における超平面に境界に容易に一般化される。このような境界は、例えば、各クラスｃのすべてのパケット到着がピークレートｒ（ｃ）のみで起こると仮定するＣＡＣへの従来のアプローチで遭遇するものである。このような仮定の下では、各クラスのパケット到着の全レートは、関連するクラス要素数Ｎcと、関連するピークレートとの積となる。従って、全到着レートは、これらの積の、すべてのクラスにわたる和となる。単純化された解析によれば、受付可能領域は、この和がサーバの全処理レートＣ以下であるようなすべての状態点からなる。すなわち、この単純化された解析の下では、受付可能条件は
【数１】
0003779860.tif 000002
となる。このような領域の境界は、上記のような直線、平面、または超平面である。
【００１８】
さらに詳細な、最悪の場合の解析は、例えば、J. Liebeherr et al., "Exact admission control for networks with a bounded delay service", IEEE Transactions on Networking 4 (December 1996)、に記載されている。この詳細な解析の結果は、長さｘの期間に到着可能なセッションｉのトラフィックの最大量を表す関数Ａi*（ｘ）で都合よく記述される。言い換えると、Ａi*（ｘ）は、バーストが時刻０に始まった場合に時刻ｘまでに到着するセッションｉトラフィックの量である。それぞれのセッションに対する遅延限界ＴiがＴ1≦Ｔ2≦...となるように順序づけられている場合、Liebeherr et al.の最悪の場合の解析の下では、Ｔi以降のすべての時刻ｔに対して、次の不等式
【数２】
0003779860.tif 000003
が満たされる場合に限り、セッションのセットは受付可能である。ただし、和はすべてのセッションｊにわたる。この解析による受付可能領域は一般に、面
【数３】
0003779860.tif 000004
で定められる領域よりもやや大きくなる。
【００１９】
重要な点であるが、本発明のように、統計的多重化の原理を適用すると、結果として得られる受付可能領域は、（いずれの解析による）最悪の場合の受付可能領域よりも大きくなり、実際にはそれをサブセットとして含む。従って、最悪の場合の状態図により受付可能な任意の点は、本発明に従って構成される状態図によっても受付可能である。さらに、本発明により構成される状態図は、最悪の場合の受付可能領域の外側にある追加の受付可能点を含むことになる。
【００２０】
実際には、状態図は、コンピュータなどのデータ処理装置のメモリ内のデータ構造として実現される。図４のような、状態図の図形的表現は教示的な工夫としては有用であるが、状態図に実現される原理は、図形的表現なしに容易に使用されることに注意すべきである。
【００２１】
図５に、本発明の代替実施例による例示的な受付制御手続きを示す。ブロック７５で、セッションｉに対する設定要求を受け取る。ブロック８０で、サーバは、要求されたセッションが属するクラスを識別するインデックスを読み出す。ブロック８５で、各クラスの現在の要素数をクラス要素数レジスタから読み出す。ブロック９０で、サーバは、その状態図にアクセスする。サーバに対して提案される動作点は、現在の要求に対応するクラスの要素数に単位増分を追加することによって、現在の状態から導出される状態である。ブロック９５で、提案された動作点が受付可能領域内にあるかどうかを判断する。受付可能領域内にない場合、ブロック１００に示すように、セッションは拒否される。しかし、提案された動作点が受付可能領域内にある場合、セッションは受付可能であるとみなされる。さらに、セッションは、そのパスに沿ったすべてのサーバによって受け入れられた場合、ネットワークに受け付けられ、ブロック１１０に示すように、関連するクラス要素数レジスタが１単位だけインクリメントされる。
【００２２】
次に、違反確率を推定する例示的な手続きについて、図６を参照して説明する。図示のようにタイムラインが構成される。なお、図６の図形的表現は教示目的には有用であるが、これから説明する手続きの実際の実現は、図形的表現を必要とせずに、計算上行われる。
【００２３】
図示したタイムラインにおいて、時間は左から右に進む。点列ｙ0，ｙ1，...が、インデックス添字が増大するにつれて先行する時刻へ延びるように定義される。始点ｙ0は、パケットｐの到着時刻ａpからパケットｐの期限ｄpまでの閉区間上の任意の点に置くことが可能である。パケットの期限は、その到着時刻に、対応するセッションｉの遅延限界Ｔiを加えたものである。ｙ0は、図中では、到着時刻と期限の中間にあるように示されているが、ｙ0は、例えばちょうどパケット到着時刻ａpに位置することも可能である。後続の点ｙnは、収束列を形成しない限り、任意の区間に位置することが可能である。例えば、図示のように、ｙ1は、ａpよりＴi／２だけ先行する時点に位置し、後のそれぞれのｙnは、前の点よりＴi／２だけ先行する時点に位置する。点列ｙnは原理的には無限であるが、一般には、それほど不正確さを導入せずに、５０個以下の点で打ち切ることが可能である。上記の点列をＹ（ａp，ｄp）で表す。
【００２４】
発明者が数学的に証明したところによれば、ＥＤＦサーバに広く適用可能ないくつかの仮定の下で、セッションｉの与えられたパケットｐが期限に違反する確率は、決して超えることができない上界を有する。この上界は、ＰＤＶＰの有用な推定値を提供する。ＰＤＶＰを推定するために、この上界を厳密に計算するか、そうでなければ、適当な近似手続きを用いてこの上界自体を推定することが可能である。関連する仮定は次の通りである。
（ｉ）各セッションへのパケット到着は統計的に独立である。
（ｉｉ）各セッションは、各サーバにおける負荷の小部分（例えば１％未満）のみを構成する。
【００２５】
到着時刻ａp、期限ｄpのパケットｐが与えられ、点列Ｙ（ａp，ｄp）が与えられた場合、パケット違反確率の上界は、
点列Ｙ（ａp，ｄp）の任意の時点ｙn（ｎ＞０）に対して、ｙnとａpの間に到着するパケットの累積量が、時間的に次の時点ｙn-1とパケット期限ｄpの間にサーバが処理可能な全パケット量を超える確率
である。数学的には、この確率は次のように書ける。
【数４】
0003779860.tif 000005
この式において、Ａi（ｙn，ｄp−Ｔi）は、ｙnとａpの間（すなわち、ｙnとｄp−Ｔiの間）に到着するパケットの累積量（例えば、ビット数）を表す。外側の和は、点列Ｙ（ａp，ｄp）のインデックスｎにわたり実行される。内側の和は、現在サービスされているすべてのセッションと、新たに申告されたセッションのインデックスｉにわたり実行される。
【００２６】
上の式で書かれる確率は、パケット到着過程の適当な統計モデルが与えられれば、標準的な方法によって計算することができる。特に、計算を簡単にするためにチェルノフ限界として知られる種類の上界近似が容易に適用される。
【００２７】
チェルノフ限界近似によれば、
【数５】
0003779860.tif 000006
である。ただし、ｓは、任意の非負の値をとりうる自由に動くパラメータであり、Ｅ［・］は期待値を表し、標準的な統計計算の方法を用いて評価される。最良の限界を生じるパラメータｓの値は、例えば１次元最適化から容易に決定される。不等式（２）の右辺から、式（１）の外側の和におけるそれぞれの確率と置き換えることが可能な表式が直ちに導出される。
【００２８】
ここまでは、全体の遅延限界Ｔiが、注目するサーバから発する１つのホップのみに適用されるときの受付決定について説明してきた。しかし、さらに一般的には、Ｔiは、セッションに対して指定されたパスのすべてのホップにわたる累積遅延バジェットを表す。発明者が見出したところによれば、少なくとも、（ｉ）ネットワークが、期限に違反したあらゆるパケットを捨てるいわゆる「廃棄(drop)ネットワーク」であり、（ｉｉ）パケットｐの到着時刻ａpに対する解釈を修正（後述）した場合には、パスに沿った各サーバにおいて上記と同じ方法を適用することができる。さらに、この点に関して有用な、累積遅延Ｔiを分割する特定の方法について以下で説明する。
【００２９】
以下、図７を参照して、好ましい分割について説明する。ａpより後であるがａp＋Ｔiより前の時点τpを選択する。図中、ブロック１１５で表される最初のτp−ａp単位の遅延を、パケットｐのパスの最初のホップに割り当てる。残りの遅延を、サーバ速度に比例して、最初のホップを含む複数のホップの間で分ける。サーバをｅ0，ｅ1，...，ｅK-1で表し、パケットｐに対するｊ番目のサーバ（すなわち、ｊ番目のホップが出るサーバ）の期限を
【数６】
0003779860.tif 000007
で表し、ｊ番目のサーバの処理レートを
【数７】
0003779860.tif 000008
で表す。すると、分割は次のように記述される。
【数８】
0003779860.tif 000009
【００３０】
従って、図中、参照符号１２０で表される遅延のそれぞれの割当ては、図中、射影１２５で示されるように、それぞれのサーバ処理レートに比例する。
【００３１】
ｋ番目のサーバへのパケット到着時刻
【数９】
0003779860.tif 000010
の修正（前に言及）は、前のサーバのパケットの期限
【数１０】
0003779860.tif 000011
に等しく設定される擬似到着時刻
【数１１】
0003779860.tif 000012
でパケット到着時刻を置き換えることにより達成される。最初のサーバｅ0へのパケットの擬似到着時刻はτpに等しく設定される。
【００３２】
重要な点であるが、パラメータτpは、フローレギュレータの挙動をエミュレートする有用な手段を提供し、それにより、最初のサーバに到着するトラフィックがバースト性であるときに、申告されたセッションの受容レートを改善する。すなわち、最初のホップにおける追加遅延τp−ａpにより与えられる余裕は、最初のホップにおけるセッションｉトラフィックをなめらかにすることができる。これにより、後続のホップにおける違反確率を低減することができる。このために、あるパラメータＢ、ｆの（Ｂ，ｆ）レートコントローラをセッションｉが通ったと仮定した場合にパケットｐがその最初のサーバに到着するであろう時刻に、τpを設定することが有用である。（Ｂ，ｆ）レートコントローラとは、期間［ｓ，ｔ］の間に出て行く全トラフィックが高々Ｂ＋ｆ（ｔ−ｓ）であるようにトラフィックを制御する装置である。
【００３３】
しかし、注意すべき点であるが、現実のレートコントローラは使用しない。その代わりに、パケットｐは、その到着時刻ａpにサービスを受ける資格があることになる。レートコントローラのエミュレーションは単に、好適な方法でパケット期限を定義するために用いられる道具である。
【００３４】
全遅延バジェットが複数のホップにわたって割り当てられると、ｊ番目のサーバは、単一ホップの場合と同じ解析を実行する。ただし、（ｉ）ｊ番目のサーバは、パケットｐがその擬似到着時刻
【数１２】
0003779860.tif 000013
に到着すると仮定し、（ｉｉ）ｊ番目のサーバは、パケットｐに、
【数１３】
0003779860.tif 000014
に等しい遅延限界を割り当てる。
【００３５】
なお、ネットワーク挙動のわれわれの解析では、サーバにおけるサービスはプリエンプティブであると仮定している。すなわち、サーバは複数のパケットに同時にサービスすることが可能であり、かつ、あるパケットへのサービスが完了する前に別のパケットにサービスを移行することができることを仮定している。プリエンプティブ性は、解析を簡単にするため、有用な仮定である。実際上は、この仮定は重要ではない。ここで考えているプリエンプティブ方式は、非プリエンプティブ方式に容易に変換されるからである。その場合、各パケットは、各ホップで高々Ｌmax／Ｃeの追加遅延を受ける。ただし、Ｌmaxは、すべてのセッションにわたる最大パケットサイズである。高速ネットワークの場合、この追加遅延は無視できる。この点に関して有用な文献は、L. Georgiadis et al., "Optimal multiplexing on a single link: Delay and buffer requirements", IEEE Transactions on Information Theory 43 (1997)、である。
【００３６】
例
本発明によるＣＡＣを実現するＥＤＦサーバのパフォーマンスを、各セッションごとに有効帯域幅を課することにより統計的多重化法を実現したＧＰＳサーバのパフォーマンスと比較するために、一連の数値シミュレーションを実行した。
【００３７】
まず、１つだけのクラスのトラフィックを考える。各セッションへのパケット到着を、周期１０ｓでオン期間１ｓの周期的オン・オフ過程によりモデル化した。オン期間中、サイズ１０ｋｂのパケットを、サイズ１００ｍｓの区間ごとに１回注入する。従って、ピークレートは１００ｋｂｐｓであり、平均レートは１０ｋｂｐｓである。各サーバの処理レートは１００Ｍｂｐｓである。従って、サーバが安定であるセッションの最大数は１０，０００である。すべてのセッションは同じ遅延限界Ｔを有する。
【００３８】
時間離散化系列を、ｙ0＝ｄp−Ｔ、ｙn＝ｙn-1−Ｔ／２で定義する。
【００３９】
図８は、固定値の違反確率の場合に、サポート可能なコネクションの最大数を、遅延限界Ｔに対して示すグラフである。違反確率はｅ-16に固定されている。１つのホップのみを考慮している。図から明らかなように、遅延のそれぞれの値に対して、ＧＰＳを用いてサポート可能なよりもＥＤＦ規律を用いてサポート可能なコネクション数のほうが多い。
【００４０】
図９は、５ホップセッションの場合に、サポート可能なコネクションの最大数を、遅延に対して示すグラフである。図８の場合と同じ仮定をしている。遅延限界はエンドツーエンドである。遅延は、前述のように、複数のホップに割り当てられる。このような割当て方式をここでは調整ＥＤＦ（ＣＥＤＦ：Coordinated EDF）という。２つの曲線がＣＥＤＦ規律に対して示されている。両方の曲線で、ネットワークは、期限を満たさないパケットを廃棄(drop)すると仮定している。従って、これらの曲線は両方とも「ＤＲＯＰ−ＣＥＤＦ」とラベルされている。しかし、これらの２つの曲線は、最初の時点τpの割当てにおいて相違している。単に「ＤＲＯＰ−ＣＥＤＦ」とラベルされている曲線では、τpはパケット到着時刻である。「遅延−ＤＲＯＰ−ＣＥＤＦ」とラベルされている曲線では、τpは、パケットが（１０ｋｂ，５０ｋｂｐｓ）レートコントローラを出る時刻である。
【００４１】
図１０は、単一のサーバおよび２クラスのセッションに対する受付可能領域のグラフである。上記と同じ仮定をしている。ただし、クラス１は遅延限界が２００ｍｓであり、クラス２は遅延限界が５０ｍｓである。各クラスに要求される違反確率はｅ-16である。ＥＤＦ曲線では、すべてのパケットに対する時間離散化系列は、ｙ0＝ｄp−Ｔ2、ｙn＝ｙn-1−Ｔ2／２で定義される。図には、ＥＤＦおよびＧＰＳの場合の違反確率の推定値によって与えられる受付可能領域の境界をプロットしている。受付可能領域は、Ｎ1個のクラス１セッションとＮ2個のクラス２セッションがすべて、要求された違反確率でそれらの遅延限界を満たすことができるような対（Ｎ1，Ｎ2）からなる。
【００４２】
【発明の効果】
以上述べたごとく、本発明によれば、ＥＤＦスケジューリング規律の下で、遅延に基づく受付判定に統計的多重化を適用することが可能となる。
【図面の簡単な説明】
【図１】相互接続されたサーバあるいは交換機を通じてユーザが相互に通信する例示的なパケットネットワークの概略図である。
【図２】サーバのいくつかの機能を例示する概略図である。
【図３】本発明の一実施例による受付制御手続きの流れ図である。
【図４】２つのクラスのトラフィックをサポートする例示的なサーバの状態図である。
【図５】本発明の代替実施例による受付制御手続きの流れ図である。
【図６】本発明に従って違反確率を推定する手続きを理解する際の教示的な補助として有用なタイムライン図である。
【図７】本発明のいくつかの実施例で複数のホップに遅延を割り当てる手続きを理解する際の教示的な補助として有用な幾何学的構成図である。
【図８】本発明の方法を含むＥＤＦをＧＰＳと比較した数値シミュレーションによるパフォーマンス曲線の図である。図中には、固定値の違反確率に対して、サポート可能なコネクションの最大数を、遅延限界Ｔに対してプロットしている。１ホップのみを考慮している。
【図９】本発明の方法を含むＥＤＦをＧＰＳと比較した数値シミュレーションによるパフォーマンス曲線の図である。図中には、５ホップのセッションについて、サポート可能なコネクションの最大数を、遅延に対してプロットしている。
【図１０】本発明の方法を含むＥＤＦをＧＰＳと比較した数値シミュレーションによるパフォーマンス曲線の図である。１サーバ、２クラスのセッションの場合の受付可能領域を図示している。
【符号の説明】
１０  ユーザ
１２  ユーザ
１５  ユーザ
２０  サーバ
【図１】
0003779860.tif 000015
【図２】
0003779860.tif 000016
【図３】
0003779860.tif 000017
【図４】
0003779860.tif 000018
【図５】
0003779860.tif 000019
【図６】
0003779860.tif 000020
【図７】
0003779860.tif 000021
【図８】
0003779860.tif 000022
【図９】
0003779860.tif 000023
【図１０】
0003779860.tif 000024