(57)【特許請求の範囲】
【請求項１】
二つの遅延分布に対して高速コンボルーション近似機能を遂行する遅延分布処理機において、
自己ノード内で発生する内部遅延分布を取得する段階と、
取得された前記内部遅延分布の最大遅延値に基づいて当該内部遅延分布に対する第１データ圧縮率を決定すると共に、当該第１データ圧縮率で前記内部遅延分布を圧縮する段階と、
隣接ノードから伝達された情報から外部遅延分布及び当該外部遅延分布に関する第２データ圧縮率を取得する段階と、
決定された前記第１データ圧縮率と取得された前記第２データ圧縮率とのうちの最小データ圧縮率値を選択する段階と、
共に圧縮された前記内部遅延分布と前記外部遅延分布とをコンボルーションして高速コンボルーション結果を得る段階と、
選択された前記最小データ圧縮率値を用いて、得られた前記高速コンボルーション結果から正規コンボルーション結果を復元する段階と、
復元された前記正規コンボルーション結果により表される累積遅延分布の最大遅延値に基づいて、当該累積遅延分布に対する第３データ圧縮率を決定すると共に、当該第３データ圧縮率で前記累積遅延分布を圧縮する段階と、を含む、
ことを特徴とする端−対−端遅延予測のための高速コンボルーション近似化方法。
【請求項２】
二つの遅延分布を伝達する機能を遂行する遅延分布処理機において、
自己ノード内で発生する内部遅延分布を取得する段階と、
取得された前記内部遅延分布の最大遅延値に基づいて当該内部遅延分布に対するデータ圧縮率を決定すると共に、当該データ圧縮率で前記内部遅延分布を圧縮する段階と、
隣接ノードから伝達された情報から外部遅延分布を取得する段階と、
圧縮された前記内部遅延分布と取得された前記外部遅延分布との他の隣接ノードに対する伝達順序を決定する段階と、
決定された前記伝達順序に従って、共に圧縮された前記内部遅延分布と前記外部遅延分布とを前記他の隣接ノードに伝達する段階と、を含む、
ことを特徴とする端−対−端遅延予測のための高速コンボルーション近似化方法。
【請求項３】
ＡＴＭ網におけるデータトラフィックを交換するスイッチと、このスイッチに接続され、隣接ノードとの間で遅延情報を交換する制御ブロックとを含む複数の単位ノードを具備したシステムにおいて、
前記制御ブロックは、
自己ノード内で発生する内部遅延分布を取得する第１確率分布貯蔵装置と、
この第１確率分布貯蔵装置で取得された前記内部遅延分布の最大遅延値に基づいて当該内部遅延分布に対する第１データ圧縮率を決定するデルタ１計算ブロックと、
このデルタ１計算ブロックで決定された前記第１データ圧縮率で前記内部遅延分布を圧縮する第１確率分布圧縮機と、
前記隣接ノードから伝達された情報から外部遅延分布及び当該外部遅延分布に関する第２データ圧縮率を取得する第２確率分布貯蔵装置と、
前記デルタ１計算ブロックで決定された前記第１データ圧縮率と前記第２確率分布貯蔵装置で取得された前記第２データ圧縮率とのうちの最小データ圧縮率値を選択する最小値計算ブロックと、
前記第１確率分布圧縮機で圧縮された前記内部遅延分布と前記第２確率分布貯蔵装置で圧縮された前記外部遅延分布とをコンボルーションして高速コンボルーション結果を得るコンボルーション計算機と、
前記最小値計算ブロック選択された前記最小データ圧縮率値を用いて、前記コンボルーション計算機で得られた前記高速コンボルーション結果から正規コンボルーション結果を復元する第３確率分布貯蔵装置と、
この第３確率分布貯蔵装置で復元された前記正規コンボルーション結果により表される累積遅延分布の最大遅延値に基づいて、当該累積遅延分布に対する第３データ圧縮率を決定すると共に、当該第３データ圧縮率で前記累積遅延分布を圧縮する第２確率分布圧縮機と、
をそれぞれ装備した複数の遅延分布処理機を有する、
ことを特徴とする端−対−端遅延予測のための高速コンボルーション近似化システム装置。
【請求項４】
ＡＴＭ網におけるデータトラフィックを交換するスイッチと、このスイッチに接続され、隣接ノードとの間で遅延情報を交換する制御ブロックとを含む複数の単位ノードを具備したシステムにおいて、
前記制御ブロックは、
自己ノード内で発生する内部遅延分布を取得する第１確率分布貯蔵装置と、
この第１確率分布貯蔵装置で取得された前記内部遅延分布の最大遅延値に基づいて当該内部遅延分布に対するデータ圧縮率を決定するデルタ計算ブロックと、
このデルタ計算ブロックで決定された前記データ圧縮率で前記内部遅延分布を圧縮する確率分布圧縮機と、
前記隣接ノードから伝達された情報から外部遅延分布を取得する第２確率分布貯蔵装置と、
前記確率分布圧縮機で圧縮された前記内部遅延分布と前記第２確率分布貯蔵装置で取得された前記外部遅延分布との他の隣接ノードに対する伝達順序を決定するスケジューラと、
をそれぞれ装備した複数の遅延分布処理機を有する、
ことを特徴とする端−対−端遅延予測のための高速コンボルーション近似化システム装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、端−対−端（END TO END）遅延予測のための高速コンボルーション近似化方法及びシステム装置に関するものであり、より詳細には、いろいろなノードに亙った遅延分布を高速でコンボルーションすることによって短い時間に端−対−端遅延の推定を可能にして、遅延分布を圧縮して伝達する高速コンボルーション近似化方法、及びその実施に直接使用する高速コンボルーション近似化システム装置に関するものである。
【０００２】
【従来の技術】
ＡＴＭ網で利用者が要求するＱｏＳ（サービス品質）には、大きくセル損失率とセル遅延とセル遅延変動などがある。
【０００３】
ＡＴＭ網は、リアルタイムトラフィックと非リアルタイムトラフィックを同時に受け入れなければならないが、リアルタイムトラフィックの場合、セル遅延（ＣＴＤ）とセル遅延変動（ＣＤＶ）とは、共に重要な品質要素である。また、網は、呼を設定する間に呼受付制御の過程で要求されるセル遅延変動が満足されるか否かを知得できなければならない。
【０００４】
従って、網は、各スイッチ又はノードでのセル遅延と遅延変動情報とを利用することにより、受容可能な端−対−端遅延変動を予測する必要がある。ここで、端−対−端ＱｏＳ予測は、信号及び呼受付制御だけでなく目的地までの最も良い経路を選択するためのＱｏＳルーティングにも使用され得る。
【０００５】
従来の端−対−端遅延を推定する方法としては、大きく次の５種類の方法が提案されている。
【０００６】
一番目の方法は、端−対−端ＣＤＶを、根源地から目的地までの各ノードでのＣＤＶの合計で推定するものである。
【０００７】
二番目の方法は、各ノードでのＣＤＶがＣＴＤの標準偏差の常数倍であり、常数があらゆるノードに対して同一であると仮定するものである。このような仮定の下、端−対−端ＣＤＶは、各ノードでのＣＤＶの自乗の和に平方根（SQUARE ROOT）を取った値と同じになるようになる。
【０００８】
三番目の方法は、各ノードでの遅延の平均と分散そしてＣＤＶまで用いる方法である。即ち、個別的な確率変数の分布がどうであっても確率変数の個数が多くなればその確率変数の和は正規分布に近づくという、中心極限定理を用いる方法である。
【０００９】
四番目の方法は、CHERNOFF BOUNDを用いる方法であるが、この方法では、各スイッチでのキューイング遅延がガンマ分布に従うと仮定している。
【００１０】
五番目の方法は、網が運用維持補修（ＯＡＭ）セルを使用する方法である。ＯＡＭセルを利用すれば、各ノードで遅延分布を求める必要がなく、直ちに端−対−端遅延分布を求めることができる。
【００１１】
【発明が解決しようとする課題】
しかし、上記のような従来の方法にあっては、以下に示すような問題点が引き起こされている。
【００１２】
前記一番目の方法により求められたＣＤＶは、実際、端−対−端ＣＤＶに対する上界（UPPER BOUND）ではない場合もある。
【００１３】
前記二番目の方法では、各ノードで標準偏差に乗じられる常数が同じでない場合もある。
【００１４】
前記三番目の方法の場合、各ノードでＣＤＶを計算しなければならない負担があって、αの値が非常に小さな場合にセル遅延時間分布の（１−α）分位数（QUANTILE）を計算するときは、非常に多くの数字のサンプルが必要になり、これは正に計算時間が長くなることを意味する。
【００１５】
前記四番目の方法は、圧縮されたビデオトラフィックの場合に広域依存特性を有することが知られており、広域依存トラフィックの場合、キュー長さ分布が双曲線（HYPERBOLIC TAIL）を有するために、ガンマ分布仮定が一般的に成立するとはいえない。
【００１６】
前記５番目の方法は、各ノードで遅延分布を求める必要がなく、直ちに端−対−端遅延分布を求めることができるが、ＯＡＭセルが発生する頻度に制限があるため、ＯＡＭセルを利用して遅延分布を得るまでに非常に長い時間がかかるようになって、ＯＡＭセルは連結毎に生成されるが、ＡＴＭ網で設定される連結の数字が非常に大きいため、ＯＡＭセルによって信号トラフィックが増え、網に負荷を加重させ得るという短所がある。
【００１７】
ここにおいて、本発明の目的は、上記のような問題点を解消するため、各ノードで分散的に遅延分布を求め、その情報を利用することにより端−対−端遅延を求めることの可能な、端−対−端遅延予測のための高速コンボルーション近似化方法及びシステム装置を提供せんとすることにある。
【００１８】
本発明の他の目的は、明細書、図面、特に特許請求の範囲の各請求項の記載から自ずと明らかとなろう。
【００１９】
【課題を解決するための手段】
当該課題の解決では、本発明が次に列挙する新規な特徴的構成手法及び手段を採用することにより、前記目的を達成するよう為される。
【００２０】
即ち、本発明方法の第１の特徴は、二つの遅延分布に対して高速コンボルーション近似機能を遂行する遅延分布処理機において、自己ノード内で発生する内部遅延分布を取得する段階と、取得された前記内部遅延分布の最大遅延値に基づいて当該内部遅延分布に対する第１データ圧縮率を決定すると共に、当該第１データ圧縮率で前記内部遅延分布を圧縮する段階と、隣接ノードから伝達された情報から外部遅延分布及び当該外部遅延分布に関する第２データ圧縮率を取得する段階と、決定された前記第１データ圧縮率と取得された前記第２データ圧縮率とのうちの最小データ圧縮率値を選択する段階と、共に圧縮された前記内部遅延分布と前記外部遅延分布とをコンボルーションして高速コンボルーション結果を得る段階と、選択された前記最小データ圧縮率値を用いて、得られた前記高速コンボルーション結果から正規コンボルーション結果を復元する段階と、復元された前記正規コンボルーション結果により表される累積遅延分布の最大遅延値に基づいて、当該累積遅延分布に対する第３データ圧縮率を決定すると共に、当該第３データ圧縮率で前記累積遅延分布を圧縮する段階とを含んでなる、端−対−端遅延予測のための高速コンボルーション近似化方法の構成採用にある。
【００２１】
本発明方法の第２の特徴は、二つの遅延分布を伝達する機能を遂行する遅延分布処理機において、自己ノード内で発生する内部遅延分布を取得する段階と、取得された前記内部遅延分布の最大遅延値に基づいて当該内部遅延分布に対するデータ圧縮率を決定すると共に、当該データ圧縮率で前記内部遅延分布を圧縮する段階と、隣接ノードから伝達された情報から外部遅延分布を取得する段階と、圧縮された前記内部遅延分布と取得された前記外部遅延分布との他の隣接ノードに対する伝達順序を決定する段階と、決定された前記伝達順序に従って、共に圧縮された前記内部遅延分布と前記外部遅延分布とを前記他の隣接ノードに伝達する段階とを含んでなる、端−対−端遅延予測のための高速コンボルーション近似化方法の構成採用にある。
【００２２】
一方、本発明装置の第１の特徴は、ＡＴＭ網におけるデータトラフィックを交換するスイッチと、このスイッチに接続され、隣接ノードとの間で遅延情報を交換する制御ブロックとを含む複数の単位ノードを具備したシステムにおいて、前記制御ブロックが、自己ノード内で発生する内部遅延分布を取得する第１確率分布貯蔵装置と、この第１確率分布貯蔵装置で取得された前記内部遅延分布の最大遅延値に基づいて当該内部遅延分布に対する第１データ圧縮率を決定するデルタ１計算ブロックと、このデルタ１計算ブロックで決定された前記第１データ圧縮率で前記内部遅延分布を圧縮する第１確率分布圧縮機と、前記隣接ノードから伝達された情報から外部遅延分布及び当該外部遅延分布に関する第２データ圧縮率を取得する第２確率分布貯蔵装置と、前記デルタ１計算ブロックで決定された前記第１データ圧縮率と前記第２確率分布貯蔵装置で取得された前記第２データ圧縮率とのうちの最小データ圧縮率値を選択する最小値計算ブロックと、前記第１確率分布圧縮機で圧縮された前記内部遅延分布と前記第２確率分布貯蔵装置で圧縮された前記外部遅延分布とをコンボルーションして高速コンボルーション結果を得るコンボルーション計算機と、前記最小値計算ブロック選択された前記最小データ圧縮率値を用いて、前記コンボルーション計算機で得られた前記高速コンボルーション結果から正規コンボルーション結果を復元する第３確率分布貯蔵装置と、この第３確率分布貯蔵装置で復元された前記正規コンボルーション結果により表される累積遅延分布の最大遅延値に基づいて、当該累積遅延分布に対する第３データ圧縮率を決定すると共に、当該第３データ圧縮率で前記累積遅延分布を圧縮する第２確率分布圧縮機とをそれぞれ装備した複数の遅延分布処理機を有してなる、端−対−端遅延予測のための高速コンボルーション近似化システム装置の構成採用にある。
【００２３】
本発明装置の第２の特徴は、ＡＴＭ網におけるデータトラフィックを交換するスイッチと、このスイッチに接続され、隣接ノードとの間で遅延情報を交換する制御ブロックとを含む複数の単位ノードを具備したシステムにおいて、前記制御ブロックが、自己ノード内で発生する内部遅延分布を取得する第１確率分布貯蔵装置と、この第１確率分布貯蔵装置で取得された前記内部遅延分布の最大遅延値に基づいて当該内部遅延分布に対するデータ圧縮率を決定するデルタ計算ブロックと、このデルタ計算ブロックで決定された前記データ圧縮率で前記内部遅延分布を圧縮する確率分布圧縮機と、前記隣接ノードから伝達された情報から外部遅延分布を取得する第２確率分布貯蔵装置と、前記確率分布圧縮機で圧縮された前記内部遅延分布と前記第２確率分布貯蔵装置で取得された前記外部遅延分布との他の隣接ノードに対する伝達順序を決定するスケジューラとをそれぞれ装備した複数の遅延分布処理機を有してなる、端−対−端遅延予測のための高速コンボルーション近似化システム装置の構成採用にある。
【００２４】
本発明の他の特徴及びこれに伴う長所などは、次に参照する本発明の好適な実施の形態に対する説明から明確になるであろう。
【００２５】
【発明の実施の形態】
以下、本発明の望ましい実施の形態を、添付図面を参照して詳細に説明する。
【００２６】
図１は、本発明のＡＴＭノードの概念を表した構成図である。図示のように、本構成においては、いろいろなスイッチノード（ノードＡ，Ｂ，Ｃ）が連結されており、一つのノードは、データトラフィックを交換するＮ×Ｎスイッチファブリック（スイッチ）１０１と、隣接するノード間に遅延に関する情報をやりとりして累積された遅延を計算するコントローラー（制御ブロック）１０２とから構成されている。
【００２７】
データが左側から右側に流れると仮定すれば、図１で左側にあるノードＡが上流（UPSTREAM）ノードになり、右側にある二つのノードＢ、Ｃが下流（DOWNSTREAM）ノードとなる。
【００２８】
隣接するノード間のデータトラフィックは、データリンク１０４を通じて伝達されるが、このリンクは概念的な連結を表し、物理的にデータリンクに含まれる場合や、データリンクと分離されて別個に存在する場合もある。物理的にデータリンクに含まれる場合には、データセルと制御用セルを区別し、制御用セルだけコントローラー１０２に下ろせば、論理的に制御メッセージリンク１０５を構成することができる。
【００２９】
端−対−端遅延分布を求めるための最初の段階として、まず、各ノードで遅延分布を求めなければならない。各ノードで遅延分布を求める方法は、大きく二つの方法がある。
【００３０】
一番目の方法は、テストセルを生成してスイッチを通過させながら総所要時間を測定する方法である。即ち、テストセルを生成してスイッチに入力する直前又は直後に、テストセルのタイムスタンプに入力時間を書き込み、スイッチを抜け出る瞬間の時刻からタイムスタンプに書かれた入力時間を引けば、一つのノードでの遅延がわかる。
【００３１】
二番目の方法は、出力バッファー型スイッチ又は出力ポート別にセルを分離して管理する共有バッファー型スイッチに適用が可能な方法で、バッファーを観察して遅延分布を得る方法である。各セルが到着する時点に観察したバッファー内のセルの数をＮ’、任意の時間に観察したバッファー内セルの数をＮとすれば、Ｎ’及びＮと、バッファーでセルがサービスを受ける直前まで留まる時間Ｗとの間には、次式（１）のような関係が成立する。
【００３２】
【数１】
0003856643.tif 000002
【００３３】
ここで、Ｋは、バッファーに存在できる最大セルの数である。
【００３４】
上記の式（１）を用いれば、各セルが到着する瞬間にバッファーを観察したり、各セルタイム毎にバッファーを観察したりすることにより、バッファーでセルがサービスを受ける前までの待ち時間の分布を分かることができ、サービス時間が一定な場合、即ち出力リンク率が一定であれば、Ｗをサービス時間ぐらい水平移動させることで、セルがスイッチングシステムに留まる時間の分布を得ることができる。
【００３５】
以上に説明した方法により、各ノードのスイッチ１０１で遅延の分布を求めることができる。端−対−端遅延分布を求めるためにノード別遅延情報を累積する方法としては、▲１▼各ノードが自身のノードで発生する遅延情報と隣接ノードから受ける遅延情報を単純に上流又は下流に送って、遅延情報を呼発生ノード又は目的地ノード等の１ケ所に集めて計算する方法がありえ、また他の方法として、▲２▼他のノードでの遅延情報をそのまま伝達のみをするだけでなく、自身のノードでの遅延情報まで含んだ結果を計算して伝達する方法がありえる。
【００３６】
▲１▼の場合は、中間ノードでのコントローラー１０２が直接連結されたＮ×Ｎスイッチファブリック１０１から遅延分布を受ければ（１０３）、遅延情報を圧縮して呼発生ノード又は目的地に送るようになって、上流ノード又は下流ノードから遅延情報を受ければ、単純に反対方向に伝達する役割をするようになる。なお、あらゆる遅延情報が集まる最後のノードでは、自身のノードで発生する遅延情報と受けた遅延情報とを利用して、最終的に端−対−端遅延を計算する機能が必要である。
【００３７】
▲２▼の場合は、各ノードのコントローラー１０２は直接連結されたスイッチで遅延情報を受け、上流ノード又は下流ノードの制御ブロックから、呼発生ノードから上流ノードまで、或いは目的地から下流ノードまで累積された遅延分布を受けて高速コンボルーションを遂行し、遅延情報を受けた反対方向に、自身まで累積された遅延分布を伝達するようになる。
【００３８】
▲１▼は、最終ノードを除外した他のノードで演算が減る長所がある反面、呼発生ノードから目的地ノードまでノードの個数がＺであるとすれば、ノード別遅延情報を伝達する回数がＺの自乗に比例するようになり、▲２▼の場合には、各ノードで高速コンボルーションを遂行するために必要な演算の量がさらに多いが、ノード別遅延情報を伝達する回数がＺに比例するようになる。
【００３９】
従って、端−対−端遅延予測値を得るまでにかかる時間は、▲２▼がさらに短いこともあり得るが、各ノードで高速コンボルーションを遂行した後、情報を継続して圧縮する▲２▼に比べ、あらゆる情報を集めて一度に処理する▲１▼の方が、もう少し正確な端−対−端遅延予測をすることもできる。
【００４０】
呼受付制御を行う場合には、呼発生ノードでトラフィックを網に送る以前に、網に進入する関門に該当するノードで網の状況を判断し、連結を設定するか否かを判断しなければならないので、呼発生ノード方向に近いながら呼受付制御機能を有するノードで、端−対−端遅延情報を必要とするようになる。
【００４１】
従って、この場合には、▲１▼各ノードが自身のノードで発生する遅延情報と下流ノードから受けた遅延情報を全て上流ノードに伝達するか、▲２▼下流ノードから累積された遅延情報を受けた後、自身までの遅延情報を追加して上流ノードに伝達することが望ましい。
【００４２】
図２は、遅延情報を隣接ノードと送受信するコンボルーションを計算するコントローラー２０２を表すものである。図示のように、ここでは、図１に示したコントローラー１０２の機能をもう少し具体的に表した。
【００４３】
網の周縁にあるノードの場合、呼受付制御（ＣＡＣ）ブロック２０４が呼受付制御機能をするようになる。ルーティング情報管理器２０３は、自身のノードを通る全ての連結に対するルーティング情報を管理する。
【００４４】
呼設定過程で呼受付制御ブロック２０４が呼連結を許諾した場合、新しい連結に対するルーティング情報がルーティング情報管理器２０３に追加される。遅延分布処理機（＃０〜＃Ｎ−１）２０５の機能は、各ノードでの遅延情報を累積する方法によって異なる。
【００４５】
前述した▲１▼の方法を用いる場合、遅延分布処理機２０５は、各出力ポート毎に一つずつ割り当てられて、該当出力ポートを通るセルの遅延分布を受けて貯蔵する。Ｎ×Ｎスイッチファブリック２０１から受けた出力ポート別遅延情報は、ルーティング情報管理器２０３を経て遅延分布処理機２０５に伝達される。
【００４６】
遅延情報を呼発生ノードで集める場合、遅延分布処理機２０５は、下流ノードから来る遅延情報も貯蔵し、直接連結されたスイッチで発生する遅延情報と下流ノードから受けた遅延情報とのうち、どのような遅延情報を先に上流に伝達するかを決定した後に、その順に、Ｎ×Ｎ遅延情報スイッチングブロック２０６を通じて上流に伝達するようになる。この場合、各遅延情報が出るポート番号は、ルーティング情報管理器２０３により決定される。
【００４７】
遅延情報を目的地ノードで集める場合には、上流から来る遅延情報が、Ｎ×Ｎ遅延情報スイッチングブロック２０６を通じ、該当する下流ノードの方向の遅延分布処理機２０５に伝達される。遅延分布処理機２０５は、直接連結されたスイッチから受けた遅延情報と上流ノードから受けた遅延情報とのうち、どのようなものを先に伝達するかを順序を定めて、直ちに遅延情報を下流ノードに伝達するようになる。
【００４８】
前述した▲２▼の遅延情報累積方法を用いる場合、遅延分布処理機２０５は、各出力ポート毎に一つずつ割り当てられて、該当出力ポートを通るセルの遅延分布を貯蔵し、他のノードの遅延を受けて高速コンボルーション近似計算を行う。
【００４９】
遅延分布処理機２０５が、下流ノードで累積された遅延分布を受けて高速コンボルーションをする場合には、計算結果を貯蔵しながら、ルーティング情報管理器２０３で該当する上流ノードを探してＮ×Ｎ遅延情報スイッチングブロック２０６に関連情報を送れば、計算結果は、Ｎ×Ｎ遅延情報スイッチングブロック２０６を経て上流ノードに伝達される。
【００５０】
遅延分布処理機２０５が、上流ノードで累積された遅延分布を受けて高速コンボルーションをする場合には、上流ノードから来る遅延分布が、Ｎ×Ｎ遅延情報スイッチングブロック２０６を通じて該当遅延分布処理機２０５に伝達され、遅延分布処理機２０５は、自身のノードでの遅延分布と上流ノードからの遅延分布とを全て受けたときに、直ちに高速コンボルーションを遂行し、その結果を下流ノードに送り出す。
【００５１】
図３は、高速コンボルーションの近似アルゴリズムの原理を表すものである。図示のように、Ｘが自己ノードでの遅延であり、Ｙが隣接ノードでの遅延であるとすれば、確率変数Ｘ２及びＹ２の確率質量関数（ｐｍｆ）３０３，３０４は、確率変数Ｘ及びＹの確率質量関数３０１，３０２から、それぞれ、次式（２）及び（３）により算出される。
【００５２】
【数２】
0003856643.tif 000003
【００５３】
なお、図３では、Δ及びΔ２の値が共に「２」の場合を扱っている。
【００５４】
図３で、Ｘ２及びＹ２のｐｍｆ３０３，３０４をコンボルーションすると、その結果、分布関数でも「０」がたくさん出現するということを容易に予測することができる。ここで、ΔとΔ２との値が同じであるとき、次式（４）及び（５）で見るように、「０」が出現する場合を掛け算から除外すると、掛け算の回数が減って速度を高めることができる。
【数３】
0003856643.tif 000004
【００５５】
なお、上式中のＰｘ2’(ｉ)及びＰｙ2’(ｉ)（共に略記）は、次式（６）のように定義される。
【００５６】
【数４】
0003856643.tif 000005
【００５７】
この結果は、Ｘ２のｐｍｆ及びＹ２のｐｍｆのコンボルーションが、Ｐｘ2’(ｉ)及びＰｙ2’(ｉ)をコンボルーションした後、スケールを変えることにより計算できることを意味する。ＸとＹの最大値をそれぞれＤＸ，ＤＹとすれば、ｐｍｆＰｘ2’(ｉ)を構成する確率値の個数は、Ｐｘ2(ｉ)に比べ１／Δ程度と小さい。
【００５８】
【外１】
0003856643.tif 000006
【００５９】
ところが、ΔとΔ２とが各々大きい値であっても、それらの最大公約数Δ’が小であれば、コンボルーション速度の面で利得が見られないので、データ圧縮率Δは、常に「２」の累乗形態に取られる。
【００６０】
いままで説明したように、データ圧縮率Δ及びΔ２を導入することにより、既存のコンボルーションを使用する場合に比べ、掛け算の回数を減らすことができる。この他に、データ圧縮率を使用すれば、端−対−端遅延を推定するために、隣接したノード間に伝達するデータの量を減らすことができる。
【００６１】
【外２】
0003856643.tif 000007
【００６２】
Δ２を一定の値に定めれば、隣接するノード間に伝達する確率値の個数は、最大遅延が増加すればするほど増えるようになる。これは、間もなく各ノードで発生する遅延程度によって端−対−端遅延計算が影響を受けることを意味するので望ましくない。
【００６３】
以上のような点を解消しようと、図４では、各ノードでの遅延に基づいてデータ圧縮率を決定するアルゴリズムを提案する。
【００６４】
図４は、高速コンボルーションの近似計算に必要なデータ圧縮率を計算するアルゴリズムを示した流れ図である。図示のように、ノード間に伝達する確率値の個数をｍとし、データ圧縮率がｍ又は２の累乗であると仮定する。
【００６５】
まず、アルゴリズムに使われる全ての変数と遅延分布を貯蔵する配列ａ［ｉ］とにメモリーを割り当てて初期化させる（４０１）。次に、遅延分布を配列ａ［ｉ］に貯蔵する（４０２）。ここで、ｉは、セルタイム単位の遅延を意味し、ａ［ｉ］は、遅延がｉセルタイムである確率を表す。
【００６６】
【外３】
0003856643.tif 000008
【００６７】
図５は、二つの遅延分布に対して高速コンボルーション近似機能を遂行する遅延分布処理機５０１をブロックで示したものである。図示のように、ここでは、前述した▲２▼の遅延累積方法を使用する場合において、高速コンボルーション近似計算を行う遅延分布処理機２０５の細部構成を表した。
【００６８】
確率分布貯蔵装置（＃１）５０２は、該当する出力ポートを通るセルの遅延分布５１２を貯蔵する。このとき、遅延はセルタイム単位で測定され、各遅延値に対して発生比率が貯蔵される。
【００６９】
確率分布貯蔵装置（＃２）５０３は、上流ノード又は下流ノードから遅延情報５１３を受ける。コントローラー（制御ブロック）２０２で高速コンボルーションされた結果は、確率分布圧縮機（＃２）５１１に貯蔵される。ここで、確率分布貯蔵装置（＃２）５０３が上流ノードから遅延情報５１３を受ければ、確率分布圧縮機（＃２）５１１は下流ノードに連結され、確率分布貯蔵装置（＃２）５０３が下流ノードから遅延情報５１３を受ければ、確率分布圧縮機（＃２）５１１は上流ノードに連結される。
【００７０】
確率分布貯蔵装置（＃２）５０３は、まず、隣接ノードから遅延分布データ圧縮率Δ２を受けてデルタ２ブロック５０５に伝達し、次いで、式（３）及び（６）により計算され圧縮された遅延分布Ｐｙ2’(ｉ)を受けて貯蔵する。
【００７１】
確率分布貯蔵装置（＃１）５０２は、自身のスイッチの該当出力ポートに出るセルが経る遅延分布５１２をそのまま受け入れる。デルタ１計算ブロック５０４は、確率分布貯蔵装置（＃１）５０２から入力された遅延分布５１２を利用して、図４のアルゴリズムによりデータ圧縮率Δを計算する。
【００７２】
Δが増加すれば速度が速くなる反面、正確度が落ちるという短所がある。正確度に比重をたくさん置く場合には、デルタ１計算ブロック５０４が、図４のアルゴリズムの代わりに、Δを常に「１」に固定して出力するようにすることもできる。
【００７３】
確率分布圧縮機（＃１）５０６は、デルタ１計算ブロック５０４で計算されたΔと共に、式（２）及び（６）を利用して圧縮された遅延分布Ｐｘ2’(ｉ)を生成して貯蔵する。
【００７４】
最小値計算ブロック５０７は、デルタ１計算ブロック５０４にて計算されたΔと、デルタ２ブロック５０５に貯蔵されたΔ２との最大公約数を計算する。ΔとΔ２とが共に２の累乗の場合には、二つの数字の最大公約数が、二つの数字中の小さな値と同じであるので、最小値計算ブロック５０７は、ΔとΔ２とのうちの最小値（Δ’）を選択する機能を行う。
【００７５】
コンボルーション計算機５０８は、圧縮された遅延分布Ｐｘ2’(ｉ)及びＰｙ2’(ｉ)を高速でコンボルーションする機能（即ち、双方の遅延分布に関して畳み込み積分を行う機能）を遂行する。確率分布貯蔵装置（＃３）５０９は、そのコンボルーション計算機５０８による高速コンボルーション結果とΔ’とを受けて、これを式（４）及び（５）により元来のスケールに復元し、この復元により得られる正規コンボルーション結果を貯蔵する。
【００７６】
端−対−端遅延計算のため、正規コンボルーション結果は、また他の隣接ノードにさらに伝えられなければならない。結果分布を伝達する前に、伝達するデータの量を減らすために、デルタ３計算ブロック５１０が、正規コンボルーション結果から得られた遅延分布に対してデータ圧縮率Δ３を計算するようになる。
【００７７】
確率分布圧縮機（＃２）５１１は、デルタ３計算ブロック５１０から受けたデータ圧縮率Δ３で、式（３）及び（６）のアルゴリズムにより遅延分布を圧縮した後、データ圧縮率と圧縮された累積遅延分布とを他の隣接ノードに伝達する（５１４）ために貯蔵する。
【００７８】
図６は、前述した▲１▼の遅延累積方法を使用する場合、遅延分布が全て集まる最終ノードを除外した各ノードで、自身のノードの遅延分布と隣接するノードの遅延分布とを伝達する機能を遂行する遅延分布処理機６０１をブロックで示したものである。
【００７９】
図５で説明した前述の▲２▼の遅延分布処理機５０１と同様に、直接連結されたスイッチの該当出力ポートで発生するセル遅延分布が確率分布貯蔵装置（＃１）６０２に貯蔵され、上流ノード又は下流ノードから受けた遅延情報が確率分布貯蔵装置（＃２）６０４に貯蔵される。
【００８０】
前述した▲２▼の遅延分布処理機５０１では、上流ノード又は下流ノードから受けた遅延情報中にデータ圧縮率を分離してデルタ２ブロック５０５に貯蔵したが、▲１▼の遅延分布処理機６０１の場合は、高速コンボルーションを行わないので、データ圧縮率を分離することなく、遅延分布の確率値等と共に確率分布貯蔵装置（＃２）６０４に貯蔵する。
【００８１】
確率分布貯蔵装置（＃１）６０２に貯蔵された遅延分布に対し、デルタ計算ブロック６０３は、図４のアルゴリズムによってデータ圧縮率Δを計算し、確率分布圧縮機（＃１）６０５は、確率分布貯蔵装置（＃１）６０２に貯蔵された遅延分布を式（２）及び（６）のアルゴリズムによってΔの割合で圧縮し、その圧縮された遅延分布とΔとを貯蔵する。
【００８２】
前述した▲２▼の方式の遅延分布処理機５０１は、二つの遅延分布を受けて高速コンボルーションをし、その結果を圧縮して伝達するので、計算結果を一回だけ転送すればよいが、▲１▼の方式の遅延分布処理機６０１は、二つの遅延分布を各々分離して伝達するために、二つの遅延分布のうち、どのような分布を先に伝達するかの順番を定める必要がある。このような役割を、スケジューラブロック６０６が遂行するようになる。
【００８３】
スケジューリングアルゴリズムとしては、早く到着した遅延分布を先に転送するFIFO（FIRST-IN FIRST-OUT）方式を用いることができる。二つの遅延分布が同時に到着する場合には、直接連結されたノードで発生する遅延情報に比べて、隣接するノードから伝達される情報の量が一般的に最も多いと見ることができるので、確率分布貯蔵装置（＃２）６０４に高い優先順位を与えて伝達する方法を使用すれば、確率分布貯蔵装置（＃２）６０４に必要なバッファーの量を最小化することができる。
【００８４】
その反面、全ての遅延情報が集まる最終ノードで各ノードの遅延分布が全て到着する以前に、高速コンボルーションの遂行を開始し、所要時間を減らそうとする場合には、直接連結されたスイッチで発生した遅延情報を貯蔵している確率分布圧縮機（＃１）６０５に高い優先順位を与えてコンボルーションを遂行するノードに近いノードから、遅延情報を先に伝達することが望ましい。
【００８５】
各中間ノードは、単純に、自身のノードで発生した遅延分布と隣接ノードから受けた遅延分布とを、呼発生ノード又は目的地ノードに単純に伝達する機能を行ったが、最終ノードの遅延分布処理機では、いろいろなノードで発生した遅延分布をコンボルーションしなければならないために、その構造が中間ノードに比べさらに複雑である。
【００８６】
図７は、前述した▲１▼の遅延累積方法を用いる場合、遅延分布が集まる最終ノードで全てのノードからの遅延分布を受けて高速コンボルーション近似機能を遂行する遅延分布処理機２０５をブロックで示したものである。
【００８７】
直接連結されたスイッチの該当出力ポートで発生する遅延分布は、遅延分布処理機７０１の確率分布貯蔵装置（＃１）７０２に貯蔵される。デルタ１計算ブロック７０３は、図４のアルゴリズムに従ってデータ圧縮率Δを決定し、確率分布圧縮機（＃１）７０５は、確率分布貯蔵装置（＃１）７０２に貯蔵された遅延分布をΔの割合で圧縮し、その圧縮された遅延分布と圧縮率Δとを選択器７０６に送り出すようになる。
【００８８】
高速コンボルーション計算が始まれば、選択器７０６は、初めに確率分布圧縮機（＃１）７０５の結果を選択するので、確率分布貯蔵装置（＃２）（本発明にいう「第２確率分布貯蔵装置」）７０７には、最終ノードで発生した遅延分布が貯蔵され、その遅延分布に対するデータ圧縮率がデルタ２ブロック７０８に貯蔵される。
【００８９】
確率分布貯蔵装置（＃３）（本発明にいう「第３確率分布貯蔵装置」）７０９は、初めに最終ノードに最も近いノードで発生した遅延分布を受けるようになって、その分布に対するデータ圧縮率をデルタ３ブロック７１０に貯蔵する。
【００９０】
その以後、最小値計算ブロック７１１が、高速コンボルーションされる二つの遅延分布に対する二つのデータ圧縮率中から最小値を選択して、コンボルーション計算機ブロック７１２は、圧縮された二つの遅延分布に対してコンボルーション演算を遂行し、その結果を確率分布貯蔵装置（＃４）（本発明にいう「第４確率分布貯蔵装置」）７１３に送り出す。従って、確率分布貯蔵装置（＃４）７１３は、一旦、最終ノードからの遅延分布と最も近いノードからの遅延分布を高速コンボルーションした結果と、データ圧縮率の最小値とを貯蔵するようになる。
【００９１】
この結果を、選択器７０６にフィードバック（FEED BACK）させれば、選択器７０６は、二番目からコンボルーションが全て終わるときまで、確率分布貯蔵装置（＃４）７１３を選択するようになる。従って、累積されたコンボルーション結果は、確率分布貯蔵装置（＃２）７０７に貯蔵され、次に近いノードに対する遅延分布は、確率分布キュー（QUEUE）７０４から確率分布貯蔵装置（＃３）７０９に伝達されて貯蔵される。
【００９２】
このように、確率分布貯蔵装置（＃２）７０７に貯蔵された累積遅延分布と、確率分布貯蔵装置（＃３）７０９に貯蔵された次に近いノードの遅延分布とに対し、高速コンボルーションを遂行する過程を反復することにより、結果的に端−対−端遅延が近似的に計算される。この結果は、最終的に確率分布貯蔵装置（＃４）７１３に貯蔵される。
【００９３】
以上、本発明の望ましい実施の形態を説明したが、本発明は、上述の例に限定されることはなく、本発明が属する技術分野において通常の知識を有する者であれば、本発明の思想と精神を離れることなく、本発明を修正し又は変更すること可能であろう。
【００９４】
【発明の効果】
以上、詳細に説明したように、本発明によれば、いろいろなノードに亙った遅延分布を高速にコンボルーションすることによって、短時間で端−対−端遅延の推定を可能にするという効果がある。
【００９５】
また、本発明によれば、遅延分布を全て伝達することなく圧縮して伝達することにより、制御情報による負荷を減らすことができ、端−対−端遅延推定時間を短縮させることができる。
【００９６】
さらに、本発明によれば、端−対−端遅延の推定情報を利用して現在の網の状況を的確に把握することにより、呼受付制御を向上させることができると共に、ＱｏＳルーティングをする場合にも有用な情報を提供できる。
【図面の簡単な説明】
【図１】本発明のＡＴＭノードの概念を表した構成図である。
【図２】遅延情報を隣接ノードと送受信するコンボルーションを計算する制御ブロックを示す図である。
【図３】高速コンボルーションの近似アルゴリズムの原理の説明図である。
【図４】高速コンボルーションの近似計算に必要なデータ圧縮率を計算するアルゴリズムを表した順序図である。
【図５】二つの遅延分布に対して高速コンボルーション近似機能を遂行する遅延分布処理機のブロック図である。
【図６】自身のノードの遅延分布と隣接ノードの遅延分布を伝達する機能を遂行する遅延分布処理機のブロック図である。
【図７】あらゆるノードからの遅延分布を受けて高速コンボルーション近似機能を遂行する遅延分布処理機のブロック図である。
【符号の説明】
１０１，２０１…Ｎ×Ｎスイッチファブリック（スイッチ）
１０２，２０２…コントローラー（制御ブロック）
１０４…データリンク
１０５…制御メッセージリンク
２０３…ルーティング情報管理器
２０４…呼受付制御（ＣＡＣ）ブロック
２０５，５０１，６０１，７０１…遅延分布処理機（＃０〜＃Ｎ−１）
２０６…Ｎ×Ｎ遅延情報スイッチングブロック
３０１，３０２，３０３，３０４…確率質量量関数（ｐｍｆ）
５０２，６０２，７０２…確率分布貯蔵装置（＃１）
５０３，６０４，７０７…確率分布貯蔵装置（＃２）
５０４，７０３…デルタ１計算ブロック
５０５，７０８…デルタ２ブロック
５０６，６０５，７０５…確率分布圧縮機（＃１）
５０７…最小値計算ブロック
５０８，７１２…コンボルーション計算機
５０９，７０９…確率分布貯蔵装置（＃３）
５１０…デルタ３計算ブロック
５１１…確率分布圧縮機（＃２）
５１２…遅延分布
５１３…遅延情報
６０３…デルタ計算ブロック
６０６…スケジューラブロック
７０４…確率分布キュー
７０６…選択器
７１０…デルタ３ブロック
７１１…最小値計算ブロック
７１３…確率分布貯蔵装置（＃４）
【図１】
0003856643.tif 000009
【図２】
0003856643.tif 000010
【図３】
0003856643.tif 000011
【図４】
0003856643.tif 000012
【図５】
0003856643.tif 000013
【図６】
0003856643.tif 000014
【図７】
0003856643.tif 000015