(57)【特許請求の範囲】
【請求項１】
ネットワーク・ノードの出力リンクにおけるサービスからなるタイプのパケットの順番を確定するための方法において、前記パケットは相当数の入力パケットフローから誘導され、最小数量riは各入力フローのために保存され、各入力フローにおいて数量xi(t)が時間tごとに割り当てられる方法であって、
活性であるすべてのフローについて、最小保存数量riを越える前記割り当てxi(t)の部分Δxi(t)と、最小保存数量riを越える瞬間的数量λi(t)の部分ei(t)との間の比率が、常に同じ値K(t)になるように前記パケットの順番を確定することを特徴とする方法。
【請求項２】
前記瞬間的数量の値が推定方法Ｐによって評価され、フローFkへの時刻ｔにおいて割り当てられる前記数量の値
【数１】
0004031862.tif 000035
が下記の方程式によって与えられる請求項１記載の順番確定方法。
【数２】
0004031862.tif 000036
上記の式において、rk，rjは、夫々、フローFkとFjのために保存された最小数量であり、epk(t)とepj(t)は推定過剰なトラヒック値であり、その値は下記の方程式によって与えられる。
【数３】
0004031862.tif 000037
Ｃは前記ノードの出力リンクの最大数量であり、β（ｔ）は瞬間ｔにおける活性フロー全体｛F1〜FN｝である。
【請求項３】
前記ネットワークのノードの中におけるパケットのフローFkのシーケンスの第一のパケットPik の到着aik の時点において、前記パケットPik にマーカFik が割り当てられ、前記マーカFik の値は、前記ネットワークの出力リンクにおける前記パケットPik のサービス順番を保証するために使用される請求項１または２記載の順番確定方法。
【請求項４】
前記入力のフローに対応する相当数の待機キュー101〜10Nを備えたノードに実現され、前記マーカFikを計算するために考慮されるパケットPikの到着aikの時刻が対応キュー10kの先頭における前記パケットPik の到着の時刻である請求項３記載の順番確定方法。
【請求項５】
前記入力フローのパケットが中に記憶される単一の待機キュー10を備えたノードのために実現され、前記マーカFik の計算のために考慮されるパケットPikの到着aikの時刻が前記キュー10における前記パケットPikの到着の時刻である請求項３記載の順番確定方法。
【請求項６】
前記マーカFikの値が前記ノードの出力線の理論的離脱時刻に対応する請求項３記載の順番確定方法。
【請求項７】
前記マーカFikの値が下記の方程式によって与えられる請求項３記載の順番確定方法。
【数４】
0004031862.tif 000038
上記の式において、LikはフローFkの第一のパケットPikの長さであり、
【数５】
0004031862.tif 000039
は、ノードへの到着の瞬間aikにおいて前記パケットPikに割り当てられる数量であり、Fik-1は、以前においてはフローFkの(i-1)番目のパケットPik-1に割り当てられていたマーカである。
【請求項８】
前記マーカFikの値が、バーチャル時間関数によって定義されるバーチャル時間単位で表現されるマーカFikの理論的離脱時刻に対応する請求項３記載の順番確定方法。
【請求項９】
前記マーカFikの値が下記の方程式によって与えられる請求項３記載の順番確定方法。
【数６】
0004031862.tif 000040
上記の式において、LikはフローFkの第一のパケットPikの長さであり、
【数７】
0004031862.tif 000041
は、前記ネットワークのノードへの到着の瞬間aikにおいて前記パケットPikに割り当てられる数量であり、v(aik)は前記ネットワークのノードへの前記パケットPikの到着の瞬間aikにおいてバーチャル時間の関数によって採択される値であり、Fik-1は、以前においてはフローFkの(i-1)番目のパケットPik-1に割り当てられていたマーカであり、max(x,y)は、２つの値xとyを有する関数であり、前記２つの値のうち大きい方に対応する。
【請求項１０】
前記推定の方法が、パラメータkの加重指数法であり、ｎ乗目の推定の場合、下記の方程式でenを与えることができる請求項２〜７のいずれか記載の順番確定方法。
en=ken-1+(1-k)E
上記の式において、Ｅは各新しい推定において積分される値である。
【請求項１１】
前記請求項１〜１０のいずれか記載の方法を実現するシステムにおいて、夫々がパケットのフローを受け入れる備えをした相当数の入力と、各入力において出力がネットワーク・ノードの出力リンクに接続される待機キューからなるタイプであり、更に前記入力におけるパケットの各新しい到着時に、推定の方法を手段として瞬間数量の値を計算するために備えられたユニット、マーカ計算ユニット、および、各ノードにおけるマーカ管理ユニットと、前記ノードの出力リンクのキューからのパケットの送信を命令するためのユニットからなるシステム。
【請求項１２】
問題のパケットがキューの先頭に到着した時、前記マーカの計算を実現するためのマーカ計算ユニットが備わっている請求項９記載のシステム。
【請求項１３】
夫々がパケットのフローを受け入れる備えをした相当数の入力と、様々な入力から誘導されるパケットのフローを受け入れるために備えられ、出力はネットワーク・ノードの出力線に接続されるキューからなるタイプであり、更になかでも、前記入力におけるパケットの各新しい到着時に、推定の方法を手段として瞬間数量の値を計算するために備えられたユニット、マーカ計算ユニット、および、各ノードにおけるマーカ管理ユニットと、前記ノードの出力リンクのキューからのパケットの送信を命令するためのユニットからなる請求項１〜９のいずれか記載のシステム。
【請求項１４】
問題のパケットが前記キューの中に記憶される時、前記マーカの計算を実現するためのマーカ計算ユニットが備わっている請求項１１記載のシステム。
【請求項１５】
増分順番でマーカのソーティングを実現するためのマーカ管理ユニットが備わっている請求項１１または１２記載のシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットの公平損失配列（arrangement of equitable-loss）のための方法（process）に関する。前記方法は、特に、ＡＴＭ (Asynchronous Transfer Mode;非同期転送モード）技術を使用する高容量集積サービス・ネットワーク（high-volume integrated services network）に応用することができる。パケット交換タイプであるそのようなネットワークにおいては、パケットは、通常は交換要素が置かれている各ノードにおいて、他の接続部から来るパケットとの相互作用で生じる。
【０００２】
前記ネットワークは、径路指示時間、ジッタ（サービス時間の変動）、パケット損失、最小容量などの点から常に要求が厳しくなっている、前記ネットワークから性能値を求めるアプリケーション間の通信が可能になるように設計されている。
【０００３】
【従来の技術】
従来のパケット交換ネットワークは最善努力の方法として知られているタイプである。即ち、このネットワークは、サービスの保証を提供しない。このタイプのネットワークの背後にある理念は、インテリジェンスはアプリケーションの中に集中しており、ネットワーク自体は可能な限り単純とするというものである。その結果、そのネットワークが過負荷になると性能値が大幅に劣化し、相当数のパケットの損失に至ることがある。このことに加えて、様々な品質のサービスを必要とするアプリケーションが結合して存在すると、混雑に関して各アプリケーションが同質のタイプの行動をとることが求められる。換言すると、各アプリケーションは、「攻撃的な」アプリケーションはそれに応じて有利にされて帯域幅の大きな部分を占め、控え目なアプリケーション（行動規則を順守する傾向が高いアプリケーション）は被害を受ける状況をもたらす危険を冒して、容量減少の規則に従うことを要求される。この現象がますます大きくなり、アプリケーションの帯域幅要求がより貪欲になるリスクがある。従って、いくつかのオーディオ・アプリケーションとビデオ・アプリケーションが調和して共存する可能性はないと思われる。
【０００４】
これらの問題を解決するため、異なった接続部から誘導されるパケットがサービスを受ける順番を決定するためにコマンドを実現することができるようにする多数の配列手順が適用されてきた。これらの手順は、「公平である（equitable）」と呼ばれている。順応(conformity)と許可(admission) のチェックに結合された時、これらの手順は、あるノードの帯域幅のある与えられた小部分が、明快に、特定の接続部に捧げることを保証できるようにするからである。そのような容量の保証がある与えられたチャンネルのすべてのノードに拡大されると、サービス時間、ジッタまたは損失に関して更に洗練されたサービス保証を提供するための本質的基盤を形成する。同様に、そのような容量の保証が緩和されると、統計的なコミットメントを提供することによって、適用されるサービスの品質に関してネットワークの使用を改善するための機会が提供される。
【０００５】
従って、コールの確立段階の間に、予想されるトラヒックと性能値の特徴に関する要求が発出される。ネットワーク中の各ノードにおいて接続のための許可チェック条件の試験される。そして、利用することができるネットワーク資源が、現存する接続を混乱させることなく接続を求める要求を満足させるために十分である場合、新しい接続はネットワークによって受け入れられる。従って、ネットワークは、加入者がこのトラヒックの特徴を尊重することを条件として、要求された性能値が尊重されることを保証する。
【０００６】
順番を確定するための方法は、ネットワーク中の各ノードにおいて実現される。この方法は、各パケットの性能要求のトラヒックの特徴に基づいて各パケット間を区別することによって、どのパケットに送信のためのサービスを提供すべきかを決定する段階からなる。
【０００７】
第一の順番確定（establishing of order）方法は「先入れ先出し法(FIFO)」というサービス名で呼ばれており、ネットワーク・ノードの各出力リンクのためのキュー（queue;待ち行列）を利用する。
【０００８】
従来の方法において使用されているFIFOの方法の文脈において、Demers他 およびParekhとGallagerは、共同で、汎用プロセッサ共用規則(Generalized Processor Sharing Discipline) 即ちGPS 規則と呼ばれる別の方法を提案した。一方では、この方法は、"the Journal of Internet Working Research and Experiment", 1990年10月、の3-26ページに「公正キューイング・アルゴリズムの解析とシミュレーション」という標題で掲載された論文の中で与えられており、他方では、"the journal Proceedings of IEEE of Infocom" 914 - 924ページ、1992年に「集積サービス・ネットワークにおける輻輳制御への汎用プロセッサ共用アプローチ − 単一ノードのケース」という標題で掲載された論文の中で与えられている。この方法の基本原理を以下にまとめる。
【０００９】
フロー（flows）1,....Nに関する重み付けの集合r1....rNが与えられたと仮定する。ノードはGPS 規則を実現し、２つの瞬間sとtが与えられたとすると、瞬間sとtの間で活性である２つのフローiとjにサービスするデータWi(s,t)とWj(s,t)の量は、下記に示される。
【数８】
0004031862.tif 000002
ここでフローの少なくとも１個のパケットがキューの中に存在するか、または瞬間sとtとの間においてサービスの過程にある場合をいう。
【００１０】
重み付けr1からrNまでは、夫々、接続部1からNまでに割り当てられた数量に正比例する。そのような順番確定方法は、また、重み付けに精密に比例した出力容量の分割を可能にし、従って、異なったフローに割り当てられる数量の分割を可能にするという意味において公平であると考えられる。
【００１１】
同様に、上記に表示した関係は流体モデルを定義すると考えられる。事実、流体フローであると仮定すると、要求されるだけ小さくトラヒックユニットにサービスを提供することができ、または、同様に、すべてのフローに平行してサービスを提供することができる。その結果、いつでもフローの重み付けに精密に応じたサービスに分割することができる。しかしながら、流体モデルにより提起される問題は、パケットからなるフローの文脈において流体モデルを実現するという問題である。
方程式(1)を下記の形態に書き直すことができる。
【数９】
0004031862.tif 000003
【００１２】
数量q(s,t)は、正規化サービス数量と呼ばれる。フローkの場合、この数量は一般に
【数１０】
0004031862.tif 000004
と表示される。この式は下記のように書くことができる。
q(s,t)=v(t)-v(s)                                        (3)
関数v(t)は関数q(s,t)の時間上の展開を示し、システムのバーチャル時間関数として知られている。この方法によって定められたバーチャル時間は、システム中のサービスの増加につれて段階的に増大する。v(t)は、フラグメントの形状において直線状である増分ストリング関数であり、任意瞬間tにおけるその勾配は、その時点において活性であるフローの重み付けの合計に反比例することを示すことができる。
【００１３】
現行のネットワークにおいては、ある瞬間においては一つのフローがサービスを受け、このサービスは、先取りすることができない可変サイズのデータ・パケットの送信に対応する。このことの結果として、流体モデルの「理想的」公平性に可能な限り近いアプローチをする一方、上記において説明した流体モデルを、パケットのような最終実体(entities)を操作するメカニズムによって近似することが必要である。公正キューイングと呼ばれ、また、差別なしにＰＧＰＳ（パケット型汎用プロセッサ共用）またはＷＦＱ（重み付け公正キューイング）として知られる既知の形態の実現の一般原則は、サーバのバーチャル時間関数の助けで入ってくるパケットのマーク、および、増分マークの方式で選択されるキューの中への挿入に基づいている。送信のために選択されたパケットは、その時点においてキューの中にある最初のパケットである。
【００１４】
【発明が解決しようとする課題】
本発明の目的は、上記で説明した流体モデルの目的とは異なっている。事実、適応アプリケーションのユーザに提供されなければならない３つのタイプの保証を区別することができる。第一の保証は容量に関する。事実、すでに示された適応しきい値の理由のため、考慮しているフローのために用意される最小容量限度を供給することが肝要である。この最小容量は、例えばベースバンドが階層的なフローによるサービスを受けることができるようにし、または、余分なフローの場合において保証された最大損失割合となる。
【００１５】
第二の保証は、サービス時間に関する。われわれは、下記において、パケットのサービス時間を考慮する。パケットのサービス時間はキュー中の待ち期間とリンクの送信時間とに分割され、伝搬時間とジッタは考慮されない。事実、アプリケーションが対話制約に従うか否かにかかわらず、受信装置は、技術的には「プレイアウト・バッファ」と呼ばれている受信キューを備えていなければならず、「プレイアウト・バッファ」の長さはその受信装置が達成できる最大サービス時間によって決定される。この最大保証サービス時間は、受信される最小数量にではなくすべてのフローパケットに関係することが注目される。
【００１６】
第三の保証は性質が異なる保証である。即ち、他のユーザからのフローが同様に劣化され、その割合が同じである場合に限って、ユーザは、実際に、自己のフローが劣化の対象にすべきであると合法的に要求することができる。従って、このことは、すでに述べた通り、最善の努力ネットワーク上における均質行動の当然の帰結である、ネットワークの中における資源の配分の公平性に関連する保証を構成する。このケースにおいては、アプリケーションの行動にかかわらず、公平なサービスを供給することを引き受けるのはネットワークである。そのアプリケーションは結果として協力することを拘束されない。
【００１７】
本発明の目的は、上記の３種類の保証を提供できる方法を提供することである。従って、課題は、適応フローのニーズを満たすことになる帯域幅の配分の公平性と、パケットを操作するメカニズムによって近似させることができる流体モデルとを同時に明らかにすることである。
【００１８】
【課題を解決するための手段】
この目的を達成するため、本発明に従ったパケットの順序を制定するための方法は、ネットワーク・ノードの出力リンクにおけるサービス、多数の入力パケットフローから誘導されるパケット、各入力フローのために用意された最小数量ri、および、各入力フローのために各時間tに割り当てられた数量xi(t)からなるタイプの方法である。この方法の特徴は、パケットが、常に、割り当てられた数量xi(t)の部分Δxi(t)が瞬間的数量λi(t)の部分ei(t)上の最小保存数量riを越えており、最小保存数量ri活性であるすべてのフローのためのこの時点における同じ値K(t)に適応するようにサービスされることである。
【００１９】
本発明は、同様に、本発明に従って順番を制定するための方法を実現するために提供されるシステムに関する。
【００２０】
上記において示された本発明の特徴とその他の特徴は、添付図面に関連して提供される説明を読めば明らかになるであろう。
【００２１】
【発明の実施の形態】
説明を続けるため、図１に示されたシステムを先ず考慮する。
このシステムは、夫々の入力E1〜ENにおいて活性フローF1〜FNを受信するＮ個の入力キュー101〜10Nからなる。入力キュー101〜10Nはネットワーク・ノードＮに接続されており、ネットワーク・ノードＮの出力は容量Ｃの出力リンクＳに与えられる。
【００２２】
r1〜rNは、夫々フローF1〜FNに対する通信の確定の瞬間における最小保存数量であるとし、λ1(t)〜λN(t)は、フローF1〜FNによって時間tに有効に付託された瞬間的な数量であるとする。一方では、入力キュー101〜10Nは、夫々、サイズB1〜BNを有し、他方、瞬間ｔにおける入力キュー101〜10Nの内容は、夫々、b1(t)〜bN(t)に等しいものと考える。従って、各通信の確定の瞬間においてなされる保存はパラメータri，Biの「漏れバケツ」に対応する。
【００２３】
過剰トラヒック量ei(t)は、対応するキュー10iが一杯である時、換言すると、bi(t)=Biである時、最小保存数量riを超過するトラヒック量であると定義されている。bi(t)がBiに等しいとはフローFiが輻輳している時をいう。定義により、この過剰トラヒック量は下記に等しい。
bi(t) = Biの時、  ei(t) = λi(t) - ri      (4)
【００２４】
同様に、瞬間tにおける割り当てられた数量xi(t)の部分Δxi(t)は保存数量riを越えるものと定義されている。
ΔXi(t)=xi(t)-ri                                           (5)
【００２５】
本発明に従い、キュー101〜10N中のパケットは、出力リンクＳにおいて次のような方法でサービスを受ける、その方法は、最小保存数量riを越える実数量λi(t)の部分ei(t)における最小保存数量riを越える割り当てられた数量xi(t)の部分Δxi(t)の時間tの関係が、すべての活性フローFiについて、この時間tにおいて同じ値に等しくなる方法でサービスを受ける。この値はK(t)として示される。
【００２６】
この特徴は、下記の方程式によって表示することができる。
【数１１】
0004031862.tif 000005
この方程式において考慮されるのは、瞬間t において活性であるフローF1〜FN、換言すると、対応するキューの中に少なくとも１個のパケットが存在するフローのみである。
【００２７】
様々な活性フローについての方程式 (6)を合計することにより、下記の方程式によって、時刻t における値K(t)が与えられることを示すことができる。
【数１２】
0004031862.tif 000006
式(7) において、β(t)は、瞬間t における活性フローの結合｛F1〜FN｝である。時刻t において活性フローFiに割り当てられる瞬間数量は下記の式によって与えられることを、この式から推論することができる。
【数１３】
0004031862.tif 000007
【００２８】
すべてのフローFi，Fjについて、過剰数量ei(t)とej(t)は正である場合、即ち、キュー10iと10jの入力に夫々従属する実数量λi(t)とλj(t)が、夫々、最小保存数量riとrjより大きい場合、下記が得られることを示すことができる。
【数１４】
0004031862.tif 000008
これらの数量は、夫々、フローFiとFjの夫々について過剰であるトラヒック量の損失の割合を示す。従って、フローFiとFjの夫々について過剰であるトラヒック量の損失の割合は同じであることが示される。従って、損失は公平となる。
【００２９】
更に、すべての最小保存数量riの合計が出力リンクＳの最大容量Ｃより低い時、即ち、
【数１５】
0004031862.tif 000009
である時に限り新しい通信の許可のための手順が実現される場合、すべてのフローFiについて最小保存数量riは数量に対する最小限度を構成し、この結果、riに対するBiは最大サービス時間限度を構成する。
【００３０】
最小保存数量がゼロである特定のケースにおいて、方程式(5) は下記になり、
Δxi(t)=xi(t)                                           (11)
方程式(6) は下記になる。
【数１６】
0004031862.tif 000010
方程式(12)は、下記の通り書き直すことができる。
【数１７】
0004031862.tif 000011
換言すると、任意の時刻tにおける公平割り当ては、すべての活性フローF1〜 FNの損失の割合を均衡させる。
【００３１】
従って、本発明に従った方法は、最小保存数量riに対応する保証された数量を得ることができるようにすることが示され、また、同様に、Bi/ri によって与えられる保証されたサービス時間を得ることができるようにすることが示されている。更に、本発明に従った方法は、損失の平衡を保証することになる。
【００３２】
上記において開示した方法を実現するための方法を以下に説明する。一時に一個づつしかサービスを受けることができず、また、各ケースにおいて完全なサービスを受けなければならないパケットまたは有限長さのセルに上記において開示した方法を適用しなければならないという事実を考慮するためである。
【００３３】
図１に示されたシステムは、各入力Ekについて、各瞬間tにおいて入力フロー Fk(K=1〜N）の瞬間値を計算するために用意されたユニット11kからなっている。以下においてはλPkとしてこの瞬間値を表示する。この計算は、Pと呼ばれる推定モデルにより実現される。新しいパケットPikが例えばフローFkのシーケンスの最初のパケットであるとして、このシステムに与えられた場合、その新しいパケットPikは、その容量の限度において、対応するキュー10kの末尾に記憶される。
【００３４】
図１に点線で示されている通り、ユニット11kは、単独ユニット11を手段として実現される。
【００３５】
キュー10kの末端においてではなく、パケットが読み出されサービスを受ける準備を終えるキュー10kの先頭においてパケットが到着する瞬間であって以下においてはaikとして示される瞬間において、Fikとして示される値を有するマーカがこのパケットPikに取り付けられる。この値Fikはシステムのユニット12kによって計算される。マーカFikは、フローFkに割り当てられた数量が本発明にしたがった方法と一致する瞬間、特に、上記方程式 (8)に一致する瞬間において、システムが、出力リンクＳの前記パケットPikの送信を命じることができるようにする。この送信コマンドは、すべてのキュー101〜10kに共通であるコマンド・ユニット13によって行われる。
【００３６】
図１において点線で示されている通り、ユニット12k は、単一のユニット12を手段として実現される。
【００３７】
従って、出力リンクＳのパケットpを送信するための方法は下記の通りである。与えられた時点tにおいて、各キュー10k（k=1〜N）の先頭において、パケットpkが記憶され、そのパケットに対してマーカFkが割り当てられる。ユニット14は、サービスを受けるべきフローF1〜FNのリストを収容している。このマーカが増加する順番にソートされている。出力リンクＳにおいて新しいパケットｐがサービスを受けようとしている時、コマンド・ユニット13はユニット14のリストの先頭を調べる。このリストは、その後、サービスを受けるべき次のパケット、即ち、マーカが最小であるパケット示す。
【００３８】
到着の時刻aikにおいてフローFkのシーケンスの最初のパケットPikに割り当てられるマーカFikの計算を説明する。フローFkの瞬間値は方法Pによって推定されること、および、その値はλPk(t)として示されることが想起されるであろう。
【００３９】
フローFkを越える数量の値は瞬間数量λPk(t)の推定値から推論され、従って、bi(t)=Biの時に下記に等しい。
【数１８】
0004031862.tif 000012
【００４０】
今や、方程式 (3)は下記のように書き直される。
【数１９】
0004031862.tif 000013
方程式(15)はすべての活性フローFkに、即ち、考慮の対象である時間tにおいて下記の方程式を確認するすべてのフローFkに適用される。
【数２０】
0004031862.tif 000014
【００４１】
フローFkによって時刻tに割り当てられた瞬間数量
【数２１】
0004031862.tif 000015
の値は、方程式(8) に基づいて計算され、従って、下記に等しい。
【数２２】
0004031862.tif 000016
【００４２】
L’kは前記パケットPikの全長であり、aikは入力キュー10kへの到着iの瞬間であり、d’kは前記キュー10kもしくはサービス時間からの完全抽出の瞬間または前記キュー10kもしくはサービス時間からの離別の瞬間である。同様に、d’kはパケットP’kの送信またはサービス時間の開始の時刻である。
【００４３】
パケットP’kのすべてのビットの送信の間、即ち、瞬間b’kとd’kとの間において瞬間値は一定であると考えられている。到着時、即ち時刻aikにおいて記されている通り、送信の時刻b’kと停止の時刻d’kとの間に構成される瞬間tにおける瞬間値は、瞬間a’tにおける瞬間値に等しいと考えられる。従って、
【数２３】
0004031862.tif 000017
【００４４】
フローFkのための最小保存数量rkは通信の全期間の間一定なのであるから、rkは、方程式(14)と(18)から下記に従う。
【数２４】
0004031862.tif 000018
【００４５】
パケットP’kが到着した時、即ち、時刻aikにおいて、フローFk以外の各活性フローFj（j=｛1〜N｝）の瞬間数量の推定値λpjは、事実、フローFjの最新のパケットPljの到着の時刻aljにおいて推定されたこのフローFjの瞬間数量の推定値λpj(alj)である。従って、
【数２５】
0004031862.tif 000019
方程式(14)と(20)から、
【数２６】
0004031862.tif 000020
【００４６】
従って、方程式(18)，(19)と(21)から誘導された値を方程式(17)に代入することによって、式(22)を容易に実証することができる。
【数２７】
0004031862.tif 000021
換言すると、時間間隔[bik，dik]の間に属する時刻においてフローFkに割り当てられる数量は、時刻aikにおいてフローFkに割り当てられた数量と同じ値を有する。
【００４７】
パケットPikの送信のために要する合計時間は、パケットPikのビット
【数２８】
0004031862.tif 000022
の送信数量に対するパケットPikの長さLikの比率であるが、前記合計時間は、また、送信の停止時刻dikと開始時刻bikとの間の差、即ち、dik-bikでもある。従って、
【数２９】
0004031862.tif 000023
【００４８】
本発明の第一実施例に従い、パケットPikにはマーカが適用され、前記マーカの値Fikは、キュー10kからの理論的送出し時間に対応し、Fik=dikである。
【００４９】
パケットPikがサービスを受けるのは、同じフローの先行パケットPik-1の末においてである。換言すると、パケットPikのサービスbikの開始のための時刻は、先行パケットPik-1のサービスの末の時刻、即ちdik-1に等しい。この値は、本実施例の仮説により、パケットPik-1に割り当てられたマーカFik-1に等しい。従って、マーカFikの値は下記の回帰公式によって計算することができる。
【数３０】
0004031862.tif 000024
【００５０】
本発明の第二実施例に従い、パケットPikには、キュー10kからのパケットPik の完全抽出時刻に対応することになるマーカFikが割り当てられる。前記完全抽出時刻は、v(t)として示され時刻t においてはバーチャル時刻v(t)に対応するバーチャル時刻の関数によって定義されるバーチャル時刻ユニットとして表示される。従って、Fik=v(dik)が得られる。
【００５１】
このことに加えて、バーチャル時刻v(t)の増分ストリング関数が選択され、上記の方程式(23)は下記の通り書き直される。
【数３１】
0004031862.tif 000025
【００５２】
パケットPikはaikに到着する前およびフローFkの先行パケットPik-1が完全にサービスされる前にサービスを受けることができないのであるから、この結果、下記の式が誘導される。
【数３２】
0004031862.tif 000026
式(26)において、max(x,y)は、x とy の二つの値が２つの値の大きな方に対応する関数である。
【００５３】
この値はバーチャル時刻中に保存される。従って、下記の通り書くことができる。
【数３３】
0004031862.tif 000027
従って、
【数３４】
0004031862.tif 000028
従って、第２実施例中のマーカFikは下記に等しくなる。
【数３５】
0004031862.tif 000029
【００５４】
最小保存数量rkがゼロである場合、割り当てられた数量
【数３６】
0004031862.tif 000030
の値は瞬間数量λPkの値に等しいことが認められるであろう。この場合、最後の方程式は下記になる。
【数３７】
0004031862.tif 000031
【００５５】
このケースにおいては、バーチャル時間関数v(t)は明示されていないが、特に、Hui Zhang が、1995年10月の"Proceedings of IEEE" Vol. 83, No.10 "Service Disciplines for Guaranteed Performance Service in Packet-Switching Network"［パケット交換ネットワークにおける保証された性能サービスのためのサービス秩序」という標題の論文で説明したWFQ（加重型公正キューイング）およびSCFQ（自己クロック型公正キューイング）という名称で知られている順序確定手順において使用された関数と同じであるかもしれない。
【００５６】
フローFkによって受信される正規化推定サービスは、下記の方程式により、２つの時刻t1とt2との間に構成される時間間隔の間に下記の方程式によって定義されることだけは想起しなければならない。
【数３８】
0004031862.tif 000032
【００５７】
従って、バーチャル時間v(t)の関数が考慮され、２つの時刻t1とt2との間の増加はこの期間の間の活性フローFkの推定正規化サービスに等しくて下記の通りである。
【数３９】
0004031862.tif 000033
【００５８】
フローFkのサービスの場合、バーチャル時間の原点 v(t)=0 は時刻 t=0に置かれる。従って。
v(0)=0                                              (33)
このように定義された関数v(t)は増分ストリング関数であることを示すことができる。
【００５９】
以前の手順において使用された推定の方法に関しては、パケットの連続到着の観察に基づくものであれば、どのような数量の推定方法でも使用することができる。例えば、パラメータ k（例えば、k=0.9)の指数加重平均値を使用することができる（一般にＥＷＭＡ"Exponential Weighted Moving Average" ［指数加重移動平均］として知られている）。nth推定の場合、enは下記の方程式で与えられることがある。
en=ken-1+(1-k)E                                      (34)
【００６０】
式(34)において、Ｅは推定において積分された新しい値である。例えば、パケットLikのサイズ、および、現在のパケットの到着時刻と先行パケットの到着時刻との間の時間に基づいて定義された値を値Ｅに割り当てることができるはずである。
【数４０】
0004031862.tif 000034
【００６１】
本発明の方法を実現するため、ここまで、図１に示されたシステムを考慮してきた。ただし、図２の目的であるシステムを使用することも同様に可能である。以下、図２に示されたシステムを説明する。
【００６２】
このシステムは、１個のキュー20からなっており、キュー20の出力は出力リンクＳに与えられる。このキュー20、夫々フローF1〜FNによって供給されるE1〜ENの20個の入力からなっている。このキュー20は、同様に、各入力E1〜ENにおおけるユニット21k(k=1〜N)からなっており、ユニット21kは、システム中のフローFkから新しいパケットPikが到着した時、推定法Ｐにより、フローFkの瞬間数量  λPik(t)を再計算する。各入力E1〜ENにおいても、同様に、ユニット22k(k=1〜N)が備わっており、ユニット22kは、キュー20の中においてパケットPikが到着した時aik、上記において記載した方程式に従って、マーカFikの値の計算を実現する。
【００６３】
図２において点線で示されている通り、ユニット21kは単一のユニット21を手段として実現することができることが認められるであろう。このことはユニット22kにも当てはまる。即ち、ユニット22kは、図２において点線で示されている通り、単一のユニット22を手段として実現することができる。
【００６４】
フローFkからのパケットPikの到着の期日aikは、そのパケットがキュー20内に0 入された実時間中の瞬間であると定義される。
【００６５】
ユニット23が備わっているのは、増分マーカによってキュー20のソートを実現するためである。従って、キュー20の先頭に置かれるパケットは、最小のマーカが割り当てられるパケットである。
【００６６】
ユニット24が備わっているのは、先行パケットがキュー20から完全に抽出された時、キュー20の先頭にあるパケットの送信の開始を制御するためである。
【００６７】
最後に、オーバーフロー制御スイッチ25kが備わっているのは、このフローFkのためのパケットの数が、上記の表現を利用するとBkに等しい所定値よりも大きい時、パケットがフローFk入るのを拒絶するためである。キュー10は、その後、各容量B1〜BNのＮ個のバーチャル・キューとして機能する。ここでＮは活性フローの数である。
【図面の簡単な説明】
【図１】  本発明の方法の実現のための、第一実施例の順番確定システムである。
【図２】  本発明の方法の実現のための、第二実施例の順番確定システムである。
【図１】
0004031862.tif 000042
【図２】
0004031862.tif 000043