(57)【要約】パケット損失の可能性を算出した結果に対応してエラー訂正（EC）パラメーターの組を順応させるという最適化方法によって、通信システムにおけるパケットの損失を最少化することができる。導出されたアルゴリズムを通信パラメーターの組に適用することによって、算出された前記の可能性を得ることができる。アルゴリズムは、通信システムのベルヌーイ分布トラフィック・モデルと固定ビット・レート（CBR）モデルから導かれる。崩壊状態モデルを用いれば、パケット損失の可能性の近似値を算出するきわめて効率のよいアルゴリズムを得ることができる。前記アルゴリズムのそのほかの実施態様も同様に開示する。
2008545356.tif 000002
【特許請求の範囲】
【請求項１】
通信システムにおいてパケットの供給をコントロールする方法であり、
パケットの組の形にアレンジされた情報を運ぶ源信号を供給する第１のデータ源と、
前記源信号を受信し、バッファー・サイズの大きさを持つバッファーに前記パケットのうちから少なくともいくつかのパケットに対応する情報を格納し、少なくともいくつかが前記バッファーに格納されていた情報のパケットを含む出力信号を送信する、パケット処理装置であって、ここで、前記パケットの組の中の前記パケットの少なくともいくつかに対応する情報が、前記バッファーが一杯であるために損失したために前記出力信号から削除されている、パケット処理装置と、
前記出力信号のパケットのうち少なくともいくつかを受信するレシーバーと
を含み、
前記方法は、
（ａ）前記バッファー・サイズと、
前記時間間隔の間に、前記パケット処理装置によって任意の競合データ源からの競合パケットが受信される干渉確率と、
前記バッファーが空でない時に一定時間間隔の間に前記パケット処理装置がパケットの送信を成功する送信確率と
を表すパラメーターを運ぶ１または複数の信号を受信するステップと、
（ｂ）前記パラメーターから損失確率の１または複数の量を導くステップであって、各量はデータ・パケット中の情報が損失する可能性を表し、ここで、損失確率の各量は前記バッファーが一杯になることを原因とする損失を計算に入れる処理から導かれ、さらにここで、
（１）前記プロセスは前記バッファー・サイズとは独立の計算複雑性をもち、０から１の間の値をとる全ての前記送信確率と前記干渉確率と前記到着確率に対して、前記損失確率は０から１の間の値をとるか、または、
（２）前記プロセスは、前記源信号中のパケットが決定的過程に従って前記パケット処理装置に到着するモデルの解決法を表すか
のいずれかである、ステップと、
（ｃ）前記第１のデータ源の動作を順応させて、前記パケット処理装置の前記バッファーが一杯であるためにデータ・パケット中の情報が損失する可能性を引き下げる方法であって、ここで、
前記パケットの組が、第１数のデータ・パケットと第２数のエラー訂正パケットを含み、
前記レシーバーが前記受信したパケットにエラー訂正処理を適用して、破損した、あるいは損失した情報をリカバリーし、
前記パラメーターは、前記第１および前記第２数、および、前記第１のデータ源からのパケットが一定時間間隔内に前記パケット処理装置によって受信される到着確率をも表し、
データ・パケット中の情報が失われエラー訂正処理によってリカバリーされない損失確率の量が、前記パラメーターから導かれ、
前記損失確率の量に対応して前記第１数または前記第２数が変更されるように前記第１のデータ源の動作が順応させられるか、
または、
複数の到着確率のそれぞれに対応する損失確率の量は前記パラメーターから導かれ、ここで、各到着確率は、前記第１のデータ源からのパケットが時間間隔内に前記パケット処理装置によって受信される確率を表し、
複数の損失確率中で最小の損失確率を導く前記到着確率を選択し、前記パケット処理装置が選択された到着確率をより厳密に反映するような態様でパケットを受信するよう前記第１のデータ源の動作を変更することによって、前記第１のデータ源の動作が順応させられるか、
のいずれかであるステップを含む方法。
【請求項２】
前記処理が、前記源信号中のパケットが決定的過程に従って前記処理装置に到着し、一定頻度でパケットが到着するモデルの解決方法を表し、前記到着確率が前記一定頻度に比例する、請求項１に記載の方法。
【請求項３】
前記到着確率が、決定過程に従って前記処理装置に到着する前記源信号中のパケットの第１の確率分布に合致し、
前記干渉確率が、確率的過程に従って前記処理装置に到着する競合パケットの第２の確率分布に一致する、
請求項１に記載の方法。
【請求項４】
前記到着確率が、ベルヌーイ過程に従って前記処理装置に到着する前記源信号中のパケットの第１の確率分布に合致し、
前記プロセスは、近似することなく損失確率の量を導き、第２数と第３数の積に比例する計算複雑性をもち、ここで、第３数は第１数と第２数の和に等しい、
請求項１に記載の方法。
【請求項５】
前記プロセスが、定常状態確率が閾値より小さいバッファー使用量の状態を除外することによって、前記損失確率の量を、近似を用いて導く、請求項１ないし４のいずれか１項に記載の方法。
【請求項６】
前記プロセスが、第４数の三乗と第１数と第５数の積に比例する計算複雑性をもち、ここで、前記第４数は前記閾値を越える定常状態確率を持つ状態のバッファー使用量の数を表し、前記第５数は前記到着確率に反比例する、請求項５に記載の方法。
【請求項７】
第２の処理を、前記バッファー・サイズと、前記第１及び第２の数と、前記到着確率と、前記転送確率と、初期損失確率とを表す情報とに適用することによって、前記干渉確率を導く、請求項１ないし６のいずれか１項に記載の方法。
【請求項８】
定常状態確率が閾値より小さいバッファー使用量の状態を除外することによって、近似によって、前記干渉確率の量を前記第２の処理が導く、請求項７に記載の方法。
【請求項９】
パケットの組の形にアレンジされた情報を運ぶ源信号を供給する第１のデータ源と、
前記源信号を受信し、バッファー・サイズの大きさを持つバッファーに前記パケットの組の中の前記パケットの少なくともいくつかに対応する情報を格納し、前記バッファーに少なくともいくつかが格納されていた情報のパケットを含む出力信号を送信し、ここで、前記パケットの組の中の前記パケットの少なくともいくつかに対応する情報が、前記バッファーが一杯であるために損失して前記出力信号から削除されている、パケット処理装置と、
前記出力信号の前記パケットのうち少なくともいくつかを受信するレシーバーと
を含み、ここで、１又は複数の前記第１のデータ源と、前記パケット処理装置と、前記レシーバーとが、請求項１ないし８のいずれか１項に記載の方法を実行するように適合された回路をもつ、通信システム。
【請求項１０】
前記パケットの組が第１数のデータ・パケットと第２数のエラー訂正パケットを含み、
前記レシーバーがエラー訂正プロセスを前記受信したパケットに適用して、破損したあるいは失われた情報をリカバリーする、
請求項９に記載の通信システム。
【請求項１１】
通信システムにおいてパケットの提供をコントロールするための請求項１ないし８のいずれか１項に記載の方法を装置が実行できるように設けた命令のプログラムを運ぶ媒体であって、ここで、前記通信システムは、
パケットの組の形でアレンジされた情報を運ぶ源信号を提供する第１のデータ源と、
前記源信号を受信し、バッファー・サイズの大きさを持つバッファーに前記パケットの組の中の少なくともいくつかの前記パケットに対応する情報を格納し、前記バッファーに少なくともいくつかが格納されていた情報のパケットを含む出力信号を送信するパケット処理装置であって、ここで前記パケットの組の中の前記パケットの少なくともいくつかに対応する情報が前記バッファーが一杯であるために損失して前記出力信号から削除される、パケット処理装置と、
前記出力信号のパケットのうち少なくともいくつかを受信するレシーバーと
を含む、媒体。
【請求項１２】
前記パケットの組は第１数のデータ・パケットと、第２数のエラー訂正パケットを含み、
前記レシーバーは前記受信したパケットにエラー訂正処理を適用して破損したあるいは失われた情報をリカバリーする、
請求項１１に記載の媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット単位に分割された情報のストリームを処理してレシーバーに送信する装置の動作を最適化することに関連し、特に、前記装置の運転を順応させて、レシーバーにおけるパケット損失を最小化することに向けられている。本発明が有利に使用されるのは、マルチメディア情報を運ぶパケットのストリームを、ワイヤレス・ネットワークを通じて送信するシステムの場合である。
【背景技術】
【０００２】
ワイヤレス・ネットワーク上のリアルタイム・マルチメディア・トラフィックの配信は、第三世代携帯電話、WIFI、およびWIMAXワイヤレス・ネットワークでの重要なアプリケーションになると期待されている。これらのアプリケーションでは、画像や音声を表すデジタル・データのようなマルチメディア情報を、パケット単位に配置する。マルチメディア発信源はこれらのパケットのストリームをワイヤレス・アクセス・ポイントのような処理装置に送り、この処理装置は前記パケットをワイヤレス通信チャンネルを通じてエンド・ユーザーのレシーバーに送信する。処理装置は、パケットを即時に送信できない場合、送信可能になるまで一時的にそのパケットをキュー又はバッファーに格納する。例えば、無線通信チャンネルが他の処理装置によって使用されている場合には、処理装置はパケットを送信できないことがありうる。
【０００３】
エンド・ユーザーが受信したマルチメディア情報の知覚品質は、パケット損失、パケット遅延、および遅延ジッターを含む多くの要因によってマイナスの影響を受けることがある。パケット損失は、エンド・ユーザー・レシーバーによって受信されなかった消失パケット、および、受信されたもののパケットが運ぶ情報が破損していた破損パケットを含む。これらのパケット損失が生じる原因として、(1)雑音のある通信チャンネル、(2)複数のトランスミッターによる同時送信、またはパケットの「コリジョン」、(3)送信前のパケットを一時的に格納する処理装置が使用するバッファーのオーバーフローを挙げることができる。バッファー・オーバーフローは、処理装置がパケットを一時的にそのバッファーに格納する必要があるにもかかわらず、バッファーがすでに一杯であった場合に生じうる。雑音のあるチャンネル及びコリジョンによるパケット損失をここではI型損失と呼び、バッファー・オーバーフローによるパケット損失をここではII型損失と呼ぶ。
【０００４】
I型及びII型パケット損失による知覚効果を減少させる技術が、数多く提唱されてきた。前方エラー訂正(FEC)と呼ばれる技術は、損失の頻度がそれほど高くなく長く続かない環境において、消失又は破損パケットによって運ばれる情報をリカバリーする機能をレシーバーに付与する。FECが対処可能なエラーの発生する条件の長さと頻度は２のパラメーターnとkによってコントロールされる。ここで、(n-k)の「FECパケット」は、kのマルチメディア・パケットと結合して、nの「マルチメディア+FECパケット」のパケットの組を構成する。仮にレシーバーがnのパケット中の少なくともkのパケットを破損することなく受信できれば、消失または破損パケットによるあらゆる損失をリカバリーすることができる。
【０００５】
残念ながら、FECには代償がある。(n-k)のFECパケットを付加することによって、コリジョンによって生じる遅延の危険を上昇させ、各パケットの組を送信するために必要な時間帯域幅またはチャンネル帯域幅を上昇させる。FECパラメーター(n,k)の値は、競合する要求の得失評価を最適化するように選ばれる。比率ψ=n/kを高くすれば、エラー訂正ができるレベルを向上させるが、同時に、ψのファクターによって、遅延を増やし、必要なチャンネル帯域幅を増加させることになる。
【０００６】
FECパラメーター(n,k)は、特定のパケット損失の割合に対する、保護、遅延、および、帯域幅の要求に合致するように決定される。残念ながら、全ての要求を同時に満たすことは不可能であるだろうし、複数の要求の間での妥協が不可欠であるだろう。さらに、チャンネル帯域幅の使用可能量によって比率ψに現実上の制限が加えられる。比率をきわめて高くした場合、高い帯域幅が必要になって、他のデータ源からのパケットを受信できなくなるか、あるいは、通信チャンネルの使用可能な帯域幅をこえることになる。FECパラメーターを最適に選択するためには、チャンネルの使用可能な帯域幅を考慮に入れると同時に、他のデータ源からのパケットのために必要な帯域幅も考慮にいれる必要がある。
【０００７】
しかしながら、実際には、通信システムの状態は急激に変化しうる。帯域幅の上昇を最小限に抑えつつ、希望の保護レベルを与えるFECパラメーターを最適に選択するためには、FECパラメーターの値(n,k)を順応的に設定する必要がある。要求されていることは、低い計算複雑性を有する処理によって実装できる、FECパラメーターを順応させる方法である。このことによって、安価であって通常のネットワーク機器に組み込むことができる処理能力の少ない装置を用いて、リアル・タイムにFECシステムを順応させることができる。
【０００８】
状態を定期的に計測でき、これらの測定結果を、FECパラメーターを順応させるシステムの一部に提供する機能があれば、本発明の順応型FECシステムはより効率的に実装することができる。このような計測機能の存在は、本開示においてはすべて本質的なものではない。原理的には、本発明において、特定の計測機能は不可欠ではない。説明の便宜のため、以下の説明では、以下に説明する通信システム・モデルの入力パラメーターとして必要な全てのトラフィック頻度と損失を計測する機能を使用できると想定する。本発明の実施態様では、FECパラメーター(n,k)を順応させてII型パケット損失の効果を最小化する他のパラメーターと同時に、これらの計測結果を使用することができる。
【発明の開示】
【発明を解決するための手段】
【０００９】
本発明の目的の１は、計算複雑性の小さい処理を用いて、パケット通信システムにおけるエラー訂正パラメーターを順応させ、パケット損失による影響を最小化する方法を提供することである。
【発明を実施するための最良の形態】
【００１０】
本発明のある実施態様では、通信システムにおけるパケットの提供をコントロールする。前記通信システムは、
第一数のデータ・パケットと第二数のエラー訂正パケットを含むパケットの組にアレンジされた情報を運ぶ源信号を提供する第一のデータ源と、
源信号を受信し、バッファー・サイズの大きさを持つバッファーにパケットの組の中の少なくとも一部のパケットの情報を格納し、少なくとも一部分がバッファーに格納されていた情報のパケットを含む出力信号を送信し、ここで、パケットの組の少なくともいくつかのパケットの情報はバッファーが一杯だったことによる損失のために出力信号から除かれている、パケット処理装置と、
出力信号の中の少なくともいくつかのパケットを受信し、受信したパケットにエラー訂正処理を適用して破損した、あるいは消失した情報をリカバリーするレシーバーと
を含む。前記コントロールの方法は、
(a)バッファー・サイズと、第一数および第二数と、ある時間間隔において第一のデータ源からのパケットがパケット処理装置に受信される到着確率と、バッファーが空でない場合に前記時間間隔おいてパケット処理装置がパケットを正常に送信する送信確率と、前記時間間隔において他の競合するデータ源からの競合するパケットがパケット処理装置によって受信される干渉確率とを表すパラメーターを運ぶ、１または複数の信号を受信するステップと、
(b)データ・パケット中の情報が失われエラー訂正処理によって修正されない損失確率の値を前記パラメーターから得るステップであって、前記損失確率の値はバッファーが一杯であることによる損失を考慮に入れる処理から得ることができ、ここで、(1)前記処理はバッファー・サイズとは独立の計算複雑性を持ち、０から１の間の値をとる到着確率、送信確率、干渉確率のいずれに対しても、損失確率は０から１の間の値をとるか、(2)前記処理は、源信号中のパケットが決定的過程に従ってパケット処理装置に到着するようなモデルの解決法であるかのいずれかのステップと、
(c)損失確率の計測値に応じて第１数又は第２数を順応させるステップと
によって達成される。
【００１１】
本発明の他のもう一つの実施態様では、通信システムにおけるパケットの提供をコントロールする。前記通信システムは、
パケットの組にアレンジされた情報を運ぶ源信号を提供する第一のデータ源と、
源信号を受信し、バッファー・サイズの大きさを持つバッファーにパケットの組の中の少なくとも一部のパケットの情報を格納し、少なくとも一部分がバッファーに格納されていた情報のパケットを含む出力信号を送信し、ここでパケットの組の少なくともいくつかのパケットの情報はバッファーが一杯であったことによる損失のために出力信号から除かれている、パケット処理装置と、
出力信号の中の少なくともいくつかのパケットを受信するレシーバーと
を含む。前記コントロールの方法は、
(a)バッファー・サイズと、同じ時間間隔にパケット処理装置が任意の競合データ源からの競合パケットを受信する干渉確率と、バッファーが空でない場合に前記時間間隔おいてパケット処理装置がパケットを正常に送信する送信確率とを表すパラメーターを運ぶ１または複数の信号を受信するステップと、
(b)前記パラメーターから、複数の到着確率のそれぞれに対応する個々の損失確率を得るステップであって、個々の損失確率はデータ・パケット中の情報が失われる確率であって、バッファーが一杯であるために生じる損失を考慮に入れる処理から導かれる確率を表し、ここで、それぞれの到着確率は、第１のデータ源からのパケットが前記パケット処理装置にある時間間隔の間に受信される確率を表し、そして、ここで、(1)プロセスの計算複雑性はバッファー・サイズとは独立であり、損失確率は到着確率のいかなる値に対しても0から1の間の値をとり、送信確率と干渉確率は0から1の間の値をとるか、あるいは、(2)前記プロセスが、決定的過程に従って前記源信号中のパケットがパケット処理装置に到着するモデルの解決方法である場合のいずれかである、ステップと、
(c)複数の損失確率の中で最小の損失確率を導く到着確率を導く到着確率を選択するステップと、
前記複数の損失確率のなかの最小の損失確率が導く到着確率を選択するステップと、
(d)第１のデータ源の動作を、パケット処理装置が前記の選択された到着確率をより厳密に反映する方法でパケットを受信するように順応させるステップと
によって達成される。
【００１２】
本発明の様々な特徴と好ましい実施態様は、以下の議論と付属の図面を参照することによってよりよく理解できる。以下の議論と図面の内容は、単に例として説明されているのみであって、本発明の範囲に関する制限を意味するものではない。
【発明の詳細な説明】
【００１３】
本発明の実現方法
A.  はじめに
1.  通信システム
図１は、通信システムの概略図であって、１または複数のデータ源２、４は、パケットの形式にアレンジされた情報を運ぶ源信号を提供する。少なくとも複数のパケットによって運ばれる情報は、例えばマルチメディア情報であってもよい。データ源２によって提供された源信号は、パケットの組の形式にアレンジされた情報を運び、これを「主パケット」と呼ぶ。なぜなら、これらのパケットを利用可能にすることが本発明の主題であるからである。主パケットの組には主データ・パケットと主エラー訂正(EC)パケットが含まれる。ある組には、主パケットの総数nに対して、kの主データ・パケット、(n-k)の主ECパケットが含まれる。データ源４のような他のデータ源も、「競合パケット」と呼ばれる、パケットの形式にアレンジされた情報を運ぶ源信号を提供する。「競合パケット」と呼ばれるのは、競合パケットは主パケットを提供するのに必要な資源を争う関係にあるからである。しかしながら、他のデータ源から発信される源信号は、前記の情報と同じタイプの情報を運ぶものである必要はなく、競合パケットはデータ源２について記述されたものと同じアレンジ形式である必要もない。
【００１４】
各データ源２、４から発信された源信号は、それぞれ通信経路３、５を経由してパケット処理装置１０に渡される。これらの通信経路３、５は様々な種類の、例えば、金属線や光ファイバーを含む媒体によって実装されてもよい。パケット処理装置１０は各データ源２、４からのパケットを受信し、少なくともいくつかのパケットに対する情報をキュー又はバッファーに保存する。パケット処理装置１０は、情報のパケットを通信経路１１を経由してレシーバー２０に送信する。この図に示した例では、レシーバー２０は、データ源２、４からの情報のパケットを処理する。レシーバー２０は、データ源２から受信した情報の主パケットに対して必要に応じてEC処理を適用し、結果として得られた情報を通信経路２１を通して送信する。レシーバー２０は、データ源４からの競合パケットを通信経路２２を通して送信する。通信システムは、必要に応じて、他にレシーバー、トランスミッター、データ源を含んでもよい。
【００１５】
この通信システムには、クオリティ・オブ・サービス処理や付加的なEC処理のような、他の技術を組み込むこともできる。クオリティ・オブ・サービス処理を用いることによって、パケットの全ての損失を防止しあるいは減少させることができる。このことは、データ源２またはパケット処理装置１０のいずれかが、レシーバー２０が受信確認を行わなかった主パケットを再送信することによって、実現することができる。すでに述べたEC処理、および以下に述べるEC処理に加えて、１または複数のEC処理を使用することもできる。これらの付加的なEC処理は、パケット処理装置１０およびレシーバー２０の中に実装することもでき、I型損失を減少させることができる。これらの付加的な処理を組み込むことによって、通信経路１１を通じて送信することができるオリジナルのパケットの頻度は減少する。なぜなら、経路の帯域幅の一部は、パケットの再送信、および、第２のECプロセスの付加的なECパケットのために必要となるからでる。その結果として、I型の損失の確率は上昇する。クオリティ・オブ・サービス処理、および付加的なEC処理を使用することは、以下に記載する通信モデルには含まれないが、必要があれば組み込むことができる。
【００１６】
図１に示す概略図には、現実の通信システムの実装においては好ましい複数の構成要素は含まれていないが、これらは本発明を説明するにあたって必要ではない。例えば、この図には、通信経路１１が空いているか否か、即ち、他のパケット処理装置が現に通信経路１１を使用しているか否か、またはレシーバー２０による受信を妨害しかねない種類の障害が存在するか否か、という点を明らかにするために必要な構成要素は図示されていない。同様に、パケット損失に関する、あるいはパケットの再送信の必要性に関する情報をレシーバー２０から得るために必要な構成要素も示されていない。
【００１７】
2.  通信システム・モデル
本発明の様々な実施態様の実施は、通信システム・モデルから得られたアルゴリズムを用いてII型損失の確率を計算し、その結果に基づいて行われる。前記モデルから、以下に記載する複数のパラメーターの関数として、II型主パケット損失の確率を得ることができる。これらの各パラメーターはバッファー使用量に影響を与え、言い換えればII型損失の確率に影響を与える。
【００１８】
通信システム・モデルは、ECパラメーター(n,k)の変化が主データ・パケットの頻度に与える影響を考慮にいれることができ、これによって、II型主パケット損失を最小化するよう順応型ECシステムを設計することができる。以下に記載する導出方法では、パケット処理装置１０における全パケットの到着パターンと、パケット処理装置１０のバッファーの大きさと、通信経路１１の利用可能性とを考慮に入れる。このモデルでは、II型主パケット損失の可能性を算出するためのアルゴリズムを導き出し、EC処理によるエラー訂正後の主データ・パケットの損失を極小化するようにECパラメーター(n,k)を順応させる。
【００１９】
以下に記載する通信モデルでは、すでに記載した順応型EC処理以外の処理は、II型損失を減少させるためには使用されていないことを想定している。このモデルに含まれない処理の例としては、クオリティ・オブ・サービス保護処理を挙げられる。そこでは、データ源２は、レシーバー２０が受信確認をしない主パケットを再送信する。レシーバー２０は、受信したパケットに対応するアクノレッジメントをデータ源２に対して送信する。データ源２は、一定の時間内にアクノレッジメントを受信しない場合、損失したと推定される１又は複数の主パケットを再度送信する。この処理はI型損失およびII型損失の両者をともに軽減する。このような処理をこのモデルに導入することはできるが、主パケットを２回以上送信することによって、パケット処理装置１０に到着する主パケットの頻度が増大し、そのためにバッファー使用量とII型損失の頻度を上昇させることになる。すなわち、パケットが再送信される頻度は、損失する確率に依存する。
【００２０】
a)基本的なアプローチ
以下に記載するように、マルコフを基礎とした２の定常状態モデルを構築し解決する。このモデルはバッファー使用量を次に示すものの関数として記述する。即ち、
(1)パケット処理装置１０にデータ源２から到着する主パケットの頻度
(2)パケット処理装置１０に他のデータ源から到着する競合パケットの頻度
(3)パケット処理装置１０が主パケットを送信し、レシーバー２０がそれを破損することなく受信する確率
(4)パケット処理装置１０のバッファー又はキューの大きさ
(5)ECパラメーター(n,k)
である。これらのモデルのうち一方は、ベルヌーイ過程の確率分布をもつ確率的過程に従って主パケットがパケット処理装置１０に到着するシステムを記述する。これらのモデルのうちもう一方は、固定ビット・レート(CBR)処理の決定論的過程に従って主パケットがパケット処理装置１０に到着するシステムを記述する。EC処理が行われない場合、これらのいずれのモデルでも、データ源２から提供された主パケットの組のなかの任意の１のパケットのII型損失の確率はバッファー使用量の関数として計算される。EC処理が行われる場合、ECリカバリー後の主データ・パケット損失の確率は、ECパラメーター(n,k)の関数として計算される。
【００２１】
この２のモデルの数理解析は著しく異なる。CBRトラフィックに対しては、定常状態マルコフ・モデルを解くためには特異値解析が用いられる（Press他著、“Numerical  Recipes  in  C++:  The  Art  of  Scientific  Computing”  第２版、ケンブリッジ大学出版局、１９９２年出版を参照のこと）。ベルヌーイ分布トラフィックに対しては、線形回帰方程式の定理を用いてマルコフ・モデルに対する閉形式解を得ることができる。加えて、ECリカバリー後のパケット損失確率の計算方法も、この２種類のトラフィックでは異なっている。ベルヌーイ分布トラフィックでは、データ・パケットとECパケットの到着は統計的に独立であることが想定され、このことによって単純な引数の組み合わせを用いてパケット損失確率を導くことができる。CBRトラフィックに対しては、データ及びECパケットの正確な到着パターンを反映する反復的数学的方法を構築する。いずれのモデルであっても、競合パケットのトラフィックはベルヌーイ分布であることが想定されている。このことは、データ源２とレシーバー２０は競合パケットの現実の処理について知らないことを示しているのであるから、伝統的な想定である。しかしながら、データ源２から送信された主パケットの到着処理は既知であってコントロールすることができるのであるから、このトラフィックに対する処理を変更した場合の効果について調査することができる。
【００２２】
本発明は、パケット処理装置１０が通信経路１１として無線周波数(RF)またはその他の無線技術を用いて複数のマルチメディアのパケットを送信する場合に、有利に使用することができるが、しかしながら、本発明は特定の種類のデータ・パケットあるいは特定の通信技術に限定されない。主データ・パケットの送信または受信の失敗の許容可能な確率のみが、以下のモデルに影響を与える唯一の通信経路の特性である。この確率を０あるいは任意の小さい値にまで減少させる代わりに、有線による通信あるいは光技術による通信を用いてモデル化することもできる。
【００２３】
b)導出の概要
以下に記述するのは、一般的な通信モデル、個々のパケットの損失確率を計算するための一般的なアルゴリズムの導出法、ベルヌーイ分布トラフィックにおける分析的通信モデルの導出法、CBRトラフィックにおける通信モデルの導出法、各モデルにおけるECリカバリー後の損失確率の計算法である。CBRトラフィックにおける損失確率の計算に用いられるアルゴリズムは計算複雑性が高いので、損失確率の近似値を算出する遙かに複雑性の低いアルゴリズムを導く。
【００２４】
B.  通信システム・モデル
1.  概要
以下に記述する２の通信モデルによって、図１に図示したシステムのような通信システムの動作を示す。このモデルにはレシーバー２０に加えて1または複数のレシーバーがあってもよい。これらのモデルによれば、パケット処理装置１０はデータ源からのパケットを受信し、バッファーに保存する。パケットは順次バッファーから取り出されて、通信経路１１を経由して送信される。これらのモデルでは、パケットは先入れ先出し方式(FIFO)の順でバッファーに格納され、取り出されることが想定されている。パケットが到着した際にバッファーが一杯であった場合、そのパケットは廃棄される。以下に記述する技術は、他のキュー方式によるモデルを導くこともできるが、数理的解析はより複雑になる。
【００２５】
以下の記述するモデルは離散時間モデルであって、パケット処理装置１０はタイム・スロットと呼ばれる一定の時間ごとにパケットを受信し送信する。モデルを単純化するために、全てのパケットは同じ固定長をもつものとする。
【００２６】
このモデルにおける想定では、与えられた任意のタイム・スロットにおいてパケット処理装置１０は１の主データ及び１の競合データを受信することができ、１のパケットを送信することができる。この想定によって計算を単純化することができるが、より一般化されたモデルを導きたいときは、この想定を緩和することができる。「ベルヌーイ・トラフィック・モデル」とは、パケット処理装置１０に到着する主パケットがベルヌーイ確率分布による確率過程の形式によって記述されうる通信システムを意味する。これらのパケットのうちの１が与えられたタイム・スロットの間にパケット処理装置１０に到着する確率をpAと表す。ここで0≦pA≦1である。「CBRトラフィック・モデル」とは、主データ・パケットが、mタイム・スロットごとに一回という一定の頻度でパケット処理装置１０に到着するような、決定的過程として記述されうる方式をとる通信システムをいう。説明の便宜のため、1/mを到着確率と呼び、シンボルpAで表す。パケットは固定長の情報または固定数のビットを運ぶものと想定しているのであるから、一定のパケット到着確率は固定ビット・レート(CBR)と等しい。従って、第２のモデルをCBRトラフィック・モデルと呼ぶ。
【００２７】
両方のモデルにおいて、データ源２以外から供給される全ての競合パケットは、ベルヌーイ確率分布を持つ確率過程によって記述される形式で、パケット処理装置１０に到着すると想定されている。任意の与えられたタイム・スロットの間に競合パケットがパケット処理装置１０に到着する確率をpCと表す。ここで0≦pC≦1である。この想定は多くのアプリケーションにおいて合理的である。なぜなら、競合パケットを送る他のデータ源が使用する処理方法は通常わからないからである。競合パケットの到着を計測しあるいは見積もるための任意の技術を、競合パケットの到着の分布を導くために使用することができ、以下に述べる技術を、到着過程を反映するモデルを構築するのに使用することができる。しかしながら、到着過程が不明の場合、ベルヌーイ分布は伝統的な想定である。以下に述べるモデルでは、全ての競合パケットの累積的到着確率としてpCのみを用いるのであるから、これらのモデルでは競合トラフィックのデータ源は１だけが想定されている。発信源が１であることは、複数のデータ源の累積的結果を表す可能性もある。
【００２８】
両者のモデルでの想定は、少なくとも１のパケットがバッファーに格納されている各タイム・スロットで、シンボルpDで表される確率でパケット処理装置１０はバッファーからパケットを取り出し、通信経路１１を経由して前記のパケットを送信するのに成功する。ここでpDは0≦pD≦1である。パケットが運ぶ情報が破損されることなくレシーバー２０が受信した場合、そのパケットの送信は成功したものとみなされる。他の装置によって同じ通信経路に他のパケットが送信されることによって、または、雑音や他の干渉によって、パケット中の情報が破損する可能性がある。好ましい実装では、パケット処理装置１０に通信経路１１が空いているかどうかをパケット送信前に判断させて、破損の危険を避ける。
【００２９】
パケットが運ぶ情報の実施態様によっては、破損したパケットが使用可能な場合もあるし、使用できない場合もある。例えば、ビデオ・フレーム中の破損したビデオ情報が一部のみが破損している場合には、破損していないビデオ情報に基づく予測によって置き換えることができることもある（Wah他著  “A  Survey  of  Error-Concealment  Schemes  for  Real-Time  Multimedia  and  Video  Transmissions  over  the  Internet”、  米国電気電子学会(IEEE)  マルチメディア・ソフトウェア工学に関する国際シンポジウム2000、台北、台湾）。この例とは対照的に、高度に圧縮された音声情報を運ぶパケットが破損している場合には、情報をリカバリーし、あるいは置き換えることはできない。以下の述べるモデルでは、部分的に破損したパケットは有用な情報を含まないと想定して、破損することなくレシーバー２０にパケットが送信される確率pDを使用する。必要であれば、一部分破損したパケットをレシーバー２０が受信する可能性を別に定義して、破損したパケットの少なくとも一部分が復元できる可能性をこのモデルに付加することもできる。通信経路１１のギルバート・モデルを用いれば、適切な確率pDを、この付加された確率から導くことができる (Bolot他著  “Adaptive  FEC-based  error  control  for  Internet  telephony”  IEEE  Infocom  2003、サンフランシスコを参照のこと)。
【００３０】
複数の競合するデータ源があるシステムでは、平均してあるタイム・スロットにおいて１を越える競合パケットが到着する可能性があり、これはpC>1という関係として表現することができる。計算を単純化するために、以下のモデルでは0≦pC,pA,pD≦1と想定する。pC,pA,pD<1となるように、各タイム・スロットの長さを減らすことによって、この想定を満たすことができる。
【００３１】
前記のモデルと以下に記載するそれに基づく結果は、パケット損失について検討しているが、遅延および遅延ジッターについては検討していない。さらに、このモデルでは、データ源からレシーバーに向けてパケットが流れる場合のみについて検討されていて、信号がレシーバーからデータ源に向けて流れる場合については検討されていない。
【００３２】
2.バッファー動作の分析
以下のモデルでは、パケット処理装置１０は長さLのキュー又はバッファーを持ち、各タイム・スロットにおいて、データ源２から受信した全ての主パケットと他のデータ源からの全ての競合パケットを、バッファーに格納することを試みる。これらのモデルによれば、この装置がパケットをバッファーに格納する動作は以下のように記述することができる。
【００３３】
１．任意のタイム・スロットにおいて、前記装置はデータ源２からpAの確率で主パケットを受け取り、他のデータ源からpCの確率で競合パケットを受け取る。主パケットと競合パケットを同じタイム・スロットで受信した場合、一方のパケットが他方のパケットより前に到着する可能性は等しいと想定する。言葉をかえれば、競合パケットが主パケットに先立って到着する可能性は0.5であると想定する。
【００３４】
２．与えられたタイム・スロットにおいて、到着しうる主パケットと競合パケットの総数jは、集合{0,1,2}のうちの任意の数である。到着するパケットは、以下に示すルールに従ってバッファーに格納され、あるいは廃棄される。
【００３５】
a)  これらのパケットが到着する直前のバッファーの使用量がL-j以下であれば、到着する全てのパケットはバッファーに格納される。
【００３６】
b)  j=2であり、かつバッファー使用量がL-1である場合は、到着する２のパケットのうち先に到着するものがバッファーに格納され、後に到着するパケットは廃棄される。
【００３７】
c)  それ以外の場合は、到着するパケットは全て廃棄される。
【００３８】
３．任意の与えられたタイム・スロットにおいて、確率pDでパケット処理装置１０はバッファーからパケットを取り出し、通信経路１１を経由してそのパケットを送信し、そのパケットが運ぶ情報は破損されることなく受信される。パケットはFIFO順でバッファーに格納され取り出される。バッファーが空である場合、取り出され送信されるパケットはない。１のパケットが取り出されて送信されれば、バッファー使用量が１減少する。
【００３９】
以下の記載するモデルでは、バッファーの統計的な使用量を記述する定常状態ベクトルを含む。このベクトルは次のように表される。
【数１】
2008545356.tif 000003
【００４０】
ここで、PN=あるタイム・スロットの終了段階においてバッファーにNのパケットが格納されている確率、L=バッファーの長さ又は大きさである。この定常状態ベクトルはパラメーターpAと、pCと、pDと、Lとの関数として表現することができる。この関数を以下導く。
【００４１】
C.  パケット損失確率
1.  イントロダクション
主パケットがパケット処理装置１０に到着したタイム・スロットにおいて、以下の２の条件のいずれかを満たす場合、パケット処理装置１０はデータ源２からの主パケットを破棄する。すなわち、(1)バッファー使用量がLである場合、または、(2)バッファー使用量がL-1であり、かつ、競合パケットが主パケットに先立って到着した場合、である。到着した主パケットが与えられたタイム・スロットにおいて破棄される可能性Plossは次のように表される。
【数２】
2008545356.tif 000004
【００４２】
係数２分の１は、主パケットと競合パケットが同じタイム・スロットに到着した場合、競合パケットが主パケットに先立って到着する確率が0.5に等しいという想定を反映したものである。
【００４３】
定常状態ベクトルPは、Pの異なる状態の間の遷移の確率を表す成分をもつ遷移行列から算出することができる。この遷移行列の一般的なパラメーター表現をはじめに導く。この一般化された表現は、パラメーターを適切に選択して、ベルヌーイ・トラフィックおよびCBRトラフィックに対して適合されうる。
【００４４】
2.  遷移行列
シンボルTはこの遷移行列を表し、表記法Ta,bは、連続したタイム・スロットの間でバッファー使用量がaからbに変化する確率を表す。ここで、0≦a,b≦Lである。バッファー使用量は、送信されたパケットがバッファーから取り除かれた後の、各タイム・スロットの終了時において計測される。表記法(Ta,b)uはuのタイム・スロット経過後にバッファー使用量がaからbに変化する確率を表す。ここでu≧1である。従って、Ta,b=(Ta,b)1である。
【００４５】
遷移行列の成分は次のように表される。
【数３】
2008545356.tif 000005
【００４６】
ここで、
qA=あるタイム・スロットにおいて主パケットが到着しない確率、またはqA=1-pA、
qC=あるタイム・スロットにおいて競合パケットが到着しない確率、またはqC=1-pC、
qD=あるタイム・スロットにおいてデータ・パケットの送信に成功しない確率、またはqD=1-pD
である。
【００４７】
これらのタイム・スロットにおいてデータ・パケットの送信に成功しない場合とは、送信の試みに失敗した場合、送信が行われなかった場合、クオリティ・オブ・サービス保護処置の一部としてパケットが送信された場合である。
【００４８】
例えば、要素T0,0は、バッファーがあるタイム・スロットの終了時において空であり、次のタイム・スロットの終了時においても空である確率を意味する。この状態は、３の起こりうる状態の結果として生じ、これらの起こりうる状態の確率は式３に示されるT0,0の３の項によってそれぞれ表される。第１の項qAqCは、次のタイム・スロットにおいて主パケットおよび競合パケットのいずれもが到着しない確率を表す。第２の項qApCpDは、主パケットが到着せず、競合パケットが到着してバッファーに格納され、バッファーからパケットが取り出されて送信された確率を表す。第３の項pAqCpDは、主パケットが到着してバッファーに格納され、競合パケットが到着せず、パケットがバッファーから取り出されて送信された確率を表す。
【００４９】
D.ベルヌーイ・モデルにおけるII型パケット損失の確率
はじめに、EC保護のないベルヌーイ分布トラフィックのII型パケット損失の確率を計算するモデルを導く。続いて、このモデルを修正して、EC保護のあるベルヌーイ分布トラフィックにおけるパケット損失の可能性を計算できるようにする。
【００５０】
１．  EC保護のないベルヌーイ分布トラフィックの定常状態モデル
ベルヌーイ・トラフィック・モデルを導くためのはじめのステップは、EC保護のないベルヌーイ分布トラフィックの定常状態ベクトルPの計算方法を得ることである。多くのマルコフ・モデルの適用事例では、定常状態ベクトルPに対する陽公式を得ることができないが、この行列は行列分解の特異値分解の結果として表現することができる。残念ながら、このアプローチは魅力的ではない。なぜなら、この方法による解は閉形式ではなく、計算複雑性が極めて高いからである。これに換えて、線形回帰方程式の理論を用いて、Pに対する閉形式の表現を確立する。はじめに、定理１で、比較的複雑で計算上高くつくPに対する式を導き、続いて定理２で単純化する。
【００５１】
定理１は以下のとおりである。
【００５２】
定理１
【数４】
2008545356.tif 000006
【００５３】
ここで
【数５】
2008545356.tif 000007
【００５４】
定理１は数学的帰納法によって証明される。式３で与えられた遷移行列の定義から、次の関係を導くことができる。
【数６】
2008545356.tif 000008
【００５５】
式７から１１に与えた定義を用いて、式１２から１５に与えられた関係は次のように表される。
【数７】
2008545356.tif 000009
【００５６】
方程式１７、１８、１９の関係は、j=1,2,3の場合の方程式５の関係を表す。式１９の関係は、式５がj,j+1,j+2で成り立つとき、式５が4≦j+3≦L-1でも成り立つことを示すために使うことができる。式５に与えられた定義を用いて、式１９の関係を書き換えると、次のことを証明することによって、定理１を証明することができる。
【数８】
2008545356.tif 000010
【００５７】
これは次の式と等価である。
【数９】
2008545356.tif 000011
【００５８】
さらに次のように変形できる。
【数１０】
2008545356.tif 000012
【００５９】
次のことがわかっている。
【数１１】
2008545356.tif 000013
【００６０】
ここで
【数１２】
2008545356.tif 000014
【００６１】
は、iの選択肢の中から順序なくjを取り出す方法の数を表す２項係数である。
【００６２】
式７を用いて、式２３の左辺は次のように書き直すことができる。
【数１３】
2008545356.tif 000015
【００６３】
式２４と２５の関係を適用し、各項を結合して単純化すれば、次のように式２３の左辺が０に等しくなるように表すことができる。
【数１４】
2008545356.tif 000016
【００６４】
式２３の右辺の各項は次のように表すことができる。
【数１５】
2008545356.tif 000017
【００６５】
式２４と２５の関係を適用し、各項を結合して単純化すれば、次のように式２３の右辺が０に等しくなるように表すことができる。
【数１６】
2008545356.tif 000018
【００６６】
式２３、２９、および３３より、j+3に対して式５が正しいことがわかる。j=Lに対して、式５及び式２０から式６が得られる。式４は、式５及び式６、
【数１７】
2008545356.tif 000019
【００６７】
という事実から得られる。
【００６８】
定理１でBjに対して得られた式は、式７で示したBjの定義をB0=1として拡張することによって単純化することができる。これは、次のことを示すことによって行われる。
【００６９】
補助定理１
【数１８】
2008545356.tif 000020
【００７０】
式３４の関係は次のものと等価である。
【数１９】
2008545356.tif 000021
【００７１】
式２５から、式３５の左辺の第１項と、右辺の第１項は、ともに１に等しいことがわかる。式２４から、式３６に示すように、式３５の左辺の第２項は、右辺の第２項と第３項の和に等しいことがわかる。
【数２０】
2008545356.tif 000022
【００７２】
検討を加えると、式３５の左辺の第３項と右辺の第４項は、総和の項の総和の範囲がl=1から1/2・jでなければともに0に等しく、その範囲内にあれば1に等しいことがわかる。これによって補助定理１が得られ、この補助定理はBjの項は、一般化されたフィボナッチ数として表すことができることを示している。
【００７３】
補助定理２
まず、次の数列を定義する。
【数２１】
2008545356.tif 000023
【００７４】
ここで、KAとKBは、正の実数である。
【００７５】
α及びβが、式x2=KAx+Kbの根として定義され、あるいは
【数２２】
2008545356.tif 000024
【００７６】
と定義され、相互に等しくない場合、線形回帰式の定理から以下のことがわかる。
【数２３】
2008545356.tif 000025
【００７７】
式３７と式３８を検討することによって、式３８はi=0,1に対して正しいことがわかり、数学的帰納法によって式３８はi≧2に対して正しいことがわかる。式３７の関係を、式３４のBjに対する式に適用することによって、KAとKBは次の値をとることがわかる。
【数２４】
2008545356.tif 000026
【００７８】
従って
【数２５】
2008545356.tif 000027
【００７９】
ここで
【数２６】
2008545356.tif 000028
【００８０】
である。
【００８１】
これはβ=1-αであることを示している。この関係を式３８のβに代入すると、式７のBjの式は次のように表すことができる。
【数２７】
2008545356.tif 000029
【００８２】
これは、式７の表現に比べて、計算複雑性が減少している。
【００８３】
式３９および４０の関係を、BjおよびKcに代入すると、式４の項は次のように表現できる。
【数２８】
2008545356.tif 000030
【００８４】
定常状態ベクトルPを算出するアルゴリズムであって、定理１から導かれたアルゴリズムに比べて計算複雑性が減少しているアルゴリズムは、式４、５、６を次のように書き換えることで得られる。
【数２９】
2008545356.tif 000031
【００８５】
ここで
【数３０】
2008545356.tif 000032
【００８６】
である。
【００８７】
２．  ベルヌーイ・トラフィック・モデルでのパケット損失確率
EC保護を使用しない場合、主パケットのいずれかかが損失する可能性は式２及び式４２ないし４４を用いることによって計算できる。ベルヌーイ分布トラフィックに対してEC保護を使用した場合、データ・パケットが損失する可能性はECパケットが損失する可能性とは独立であると想定できる。付加したECパケットによって、主パケットの到着頻度は係数ψだけ増加する。その結果、到着する確率は同じ係数だけ増加し、次のように表すことができる。
【数３１】
2008545356.tif 000033
【００８８】
EC保護が使用される場合、i>0かつs>0として、iのデータ・パケットが損失し、少なくともs=(n-k-i+1)のECパケットが損失する場合、主データ・パケットは損失し、リカバリーされない。ECリカバリーがない場合のデータ・パケットが損失する可能性は、式４６で示すとおり、iの主データ・パケットを受信する可能性と少なくともsの主ECパケットを受信する確率の積で計算できる。
【数３２】
2008545356.tif 000034
【００８９】
ここで、pi(k,n)は、iのデータ・パケットと少なくともsのECパケットを損失する確率であり、
【数３３】
2008545356.tif 000035
【００９０】
である
式４６で示した確率Plossは、式４５で示したpAの修正された値を用いて、式２で示したように計算できる。Plossは、主データ・パケットまたは主ECパケットが廃棄される可能性を表す。
【００９１】
ECリカバリーが使用されることなく、主データ・パケットが損失する確率Elossは以下の式に等しく、
【数３４】
2008545356.tif 000036
【００９２】
ECリカバリー後に主データ・パケットをリカバリーする可能性Erecは次の式で表される。
【数３５】
2008545356.tif 000037
【００９３】
E.  CBRトラフィック・モデルにおけるII型パケット損失の確率
１．  ECを行うCBRトラフィック・モデルにおける送信スキーム
すでに示した定常状態ベクトルPの算出アルゴリズムは、ベルヌーイ・トラフィック・モデルの通信システムに対して導かれた。次の節では、CBRトラフィック・モデルの通信システムにおける定常状態ベクトルPの算出アルゴリズムを導く。このモデルではタイム・スロットは１から無限大まで番号が振られ、主データ・パケットはパケット処理装置にm>1としてt=m,2m,…のタイム・スロットに到着する。主データ・パケットは、m-1の中間のタイム・スロットの間は到着しない。一連のkの主データ・パケットは、一連の(n-k)の主ECパケットと組み合わされて、nの主パケットの組を形作る。m=4、k=3、n=5の場合のパケットの組の例を図２に示す。D1というラベルによって示された第１の組のkの主データ・パケットは、k・mのタイム・スロットの間隔の間、mタイム・スロットごとに１回、パケット処理装置１０に到着する。D2というラベルで示される、次の組の主データ・パケットは、次のk・mタイム・スロットの間隔の間に同様な態様で到着する。EC1のラベルで示される第１の組の(n-k)のECパケットは、次の主パケットの組のデータ・パケットの間の空のタイム・スロットに到着する。このスキームの実現可能性を保証するために、ECパケットの数(n-k)は、次のkのデータ・パケットに対する空のタイム・スロットの数を超えないという制限を受ける。これは、
【数３６】
2008545356.tif 000038
【００９４】
と表すことができる。
【００９５】
この到着スキームは、正式には次のように表すことができる。
【数３７】
2008545356.tif 000039
【００９６】
ここで、
2≦i≦nに対してei=ti-ti-1でありかつ、
ti=主パケットの組のi番目のパケットがパケット処理装置１０に到着するタイム・スロット
である。
【００９７】
式５０のはじめの行は、第１の主データ・パケット以外の、主パケットの組の全てのデータ・パケットに関するものである。第２の行は、最後のデータ・パケットの直後に続く、その組の第１のECパケットに関するものである。第３の行は、次のパケットの組中のデータ・パケットの直後に続かない主ECパケットに関するものである。最後の行は、次のパケットの組のデータ・パケットの直後に続く主ECパケットに関するものである。
【００９８】
以下で導くCBRトラフィック・モデルでは、パケット処理装置１０は、主パケットの組の中のはじめのパケット（これは常に主データ・パケットである）を破棄することを仮定する。このパケットが破棄されるとすれば、その確率は、その前の任意のパケットが破棄される確率とは独立である。主パケットの組の中の全てのパケットに対して、主パケットが破棄される可能性は、直前の主パケットの損失確率と直前の主パケットがパケット処理装置１０に到着したときのバッファーの使用量を反復的に使用することで計算することができる。この反復的アプローチは式２に示した表現と整合性があり、主パケットが破棄されたときは常に少なくともL-1のバッファー使用量があることを示している。先行する主パケットが到着するとき使用量が少なくともL-1ある状態は、前記の先行するパケットが破棄されず、かつバッファー使用量が0からL-1というより少ないレベルにある場合の状態に比べて、次の主パケットが到着するときに使用量が少なくともL-1ある確率を上昇させる。その結果、パケット処理装置１０が先行する主パケットを破棄するか否かという点は、バッファー使用量に関する何らかの情報を与え、これは言い換えると、次の主パケットが破棄される可能性に関する何らかの情報を与える。
【００９９】
２．  CBRトラフィック・モデルにおける遷移行列
ベルヌーイ・トラフィック・モデルのすでに述べた遷移行列を、CBRトラフィック・モデルに適合させる。ベルヌーイ分布トラフィックでは、到着過程は到着確率pAにのみ依存するのであるから、全てのタイム・スロットに対して到着過程は統計的に等しい。その結果、すでに述べた遷移T行列は、任意の２の連続するタイム・スロットの確率の間の遷移を適切に記述することができる。CBRトラフィックでは、平均あるいは合成到着確率はpA=1/mで表されるが、CBRトラフィックの到着プロセスは決定的であり、各タイム・スロットは２のクラスの１に分類することができる。タイム・スロットi=1(mod m)では、主パケットが到着し、これらのタイム・スロットに対する遷移行列Fは、式３にpAに1を、qAに0を代入することによって得られる。タイム・スロットi≠1(mod m)では、主パケットが到着せず、これらのタイム・スロットに対する遷移行列Gは、式３にpAに0を、qAに1を代入することによって得られる。遷移行列FとGの積は、連続するタイム・スロットでパケットが到着することを表す。パケットが到着するタイム・スロットは行列Fで表され、パケットが到着しないタイム・スロットは行列Gで表される。
【０１００】
３．  EC保護のないCBRトラフィック・モデルでのパケット損失確率
EC保護のないCBRトラフィック・モデルの、バッファー使用量に対する定常状態ベクトルπは次のように表される。
【数３８】
2008545356.tif 000040
【０１０１】
ここで、Tは行列の積の転置を意味する。
【０１０２】
式５１は行列(FGm-1)T-Iの特異値分解によって解くことができる。ここで、Iは全ての対角成分が１である対角行列であって、一次元の解空間をもち、式
【数３９】
2008545356.tif 000041
【０１０３】
をもちいてπの最終値を決定する。主データ・パケットの損失確率は、式５３に示す定常状態ベクトルPを用いるのではなく、定常状態ベクトルπを用いて、式２と同様な式から計算できる。
【数４０】
2008545356.tif 000042
【０１０４】
４．  EC保護のあるCBRトラフィック・モデルにおけるパケット損失確率
EC保護のないCBRトラフィック・モデルにおけるパケット損失確率を計算する式を導くアプローチを拡張して、EC保護のあるCBRトラフィック・モデルにおける式を導くことができる。これはkのデータ・パケットからなる組の、任意の主データ・パケットがリカバーされない確率を計算することによって、行うことができる。
【０１０５】
a)  主パケットに対する送信スキームの定義
あるパケットの組の中のnの主パケットのうちのはじめのものが損失する確率は、第１の主データ・パケットが到着するタイム・スロットの直前のタイム・スロットのバッファー使用量の定常状態ベクトルSから決定することができる。この定常状態ベクトルは、ある主パケットの組のkのデータ・パケットが到着する、m・kのタイム・スロットの組に対して導くことができる。主パケットに先行する組の(n-k)のECパケットは、はじめのwのタイム・スロットの間に到着する。ここで、
【数４１】
2008545356.tif 000043
【０１０６】
である。
【０１０７】
m≦wの場合、主パケットの最新の組のデータ・パケットのいくつかもまた、第一のwのタイム・スロットの間に到着する。式４９から、w≦m・kであることがわかる。
【０１０８】
さらに次の値を定義する。
【数４２】
2008545356.tif 000044
【０１０９】
値z-1は、想定したk・mのタイム・スロットのw番目のタイム・スロットと、次の主データ・パケットとの間のタイム・スロットの数に等しい。値yは、データ・パケットがECパケットによって干渉さてれない場合の、mのタイム・スロットの周期または期間の数に等しい。定常状態ベクトルSはこれらの値によって表現できる。式６２は、図３に示すようなm-1>wの状態を表しており、ここでは、m=4、k=4、n=6、w=2、u=2、z=2、f=1、y=3である。式６３は、図４に示すようなm-1<wの状態を表しており、ここでは、m=4、k=4、n=8、w=5、u=1、z=3、f=1、y=2である。w=m-1に対しては、wは全てのm≧2に対してm-1(mod  m)と合同ではないので、式は必要ではない。これは、m=2の場合を検討することでわかる。m=2とすれば、wは偶数であり、m-1(mod  m)と合同となることはない。m>2に対しては、反対のことを想定すれば矛盾が生じるので合同ではないことが証明できる。すなわち、次に示す(n-k)の値が存在すると仮定する。
【数４３】
2008545356.tif 000045
【０１１０】
定義より
【数４４】
2008545356.tif 000046
【０１１１】
ここで、0≦d≦m-2であって、この式と式５９から、
【数４５】
2008545356.tif 000047
【０１１２】
であることがわかる。式６１は、左辺は整数であるが、右辺は整数ではないので真とはなり得ない。このことは式５９の仮定とは矛盾し、wはm-1(mod  m)とは合同とはなり得ないことを示している。
【０１１３】
上に示した到着過程の定義より、定常状態ベクトルSは次のように表すことができる。
【数４６】
2008545356.tif 000048
【０１１４】
πではなくSに対する式５２を使用して、式５１からから、ベクトルπと同じ方法で、定常状態ベクトルSを決定することができる。
【０１１５】
b)  ECリカバリー確率
CBRトラフィック・モデルで、ECプロセスによって破棄されたデータ・パケットがリカバリーされる確率は、次に示す５段階のステップによって計算できる。
【０１１６】
ステップ１：このステップでは、タイム・スロットjの終了時におけるバッファー使用量がgであるという条件を前提として、タイム・スロットj+m-1の終了時におけるバッファー使用量がhである、条件つき確率を決定する。この確率U(m-1,g,h)は次のように表される。
【数４７】
2008545356.tif 000049
【０１１７】
ここで、xjは正の整数であり、
【数４８】
2008545356.tif 000050
【０１１８】
である。
【０１１９】
この条件つき確率の定義が表していることは、m-1の中間のタイム・スロットの間に主パケットが到着するタイム・スロット（行列Fで表される）と、主データ・パケットが到着しないタイム・スロット（行列Gで表される）があるということである。特に、(j-1)番目のデータ・パケットが到着したタイム・スロットの終了時のバッファー使用量がgであることを前提として、j番目の主パケットが到着する前のタイム・スロットの終了時におけるバッファー使用量がhである条件つき確率R(ej-1,g,h)を、2≦j≦nに対して、計算する。
【数４９】
2008545356.tif 000051
【０１２０】
ここで、
(Fx)g,h=行列Fのx乗のg行h列の要素
(Gy)g,h=行列Gのy乗のg行h列の要素
(FxGy)g,h=行列の積FxGxのg行h列の要素
【数５０】
2008545356.tif 000052
【０１２１】
である。項R(ej-1,g,h)は2≦j≦nに対してのみ定義されているのであるから、jがこの範囲に収まらないw、m、q、uのパラメーターの組は、発生することがなく無視されるべき条件を表す。
【０１２２】
ステップ２：このステップでは、主パケットが到着するタイム・スロットの直前のタイム・スロットの終了時におけるバッファー使用量がhであるときの、到着する主パケットが破棄されるか場合と、破棄されない場合の条件つき確率を決定する。パケットが破棄されない条件は次の通りである。
【０１２３】
・ h≦L-2である場合、または、h=L-1かつk=L-2である場合は、到着するパケットは破棄されない。
【０１２４】
・ rを主パケットが到着するタイム・スロットの終了時におけるバッファー使用量として、h=r=L-1である場合、次の条件のいずれか一方が満たされれば、到着するパケットは破棄されない。１）競合パケットが到着せず、パケットがバッファーから確率qCpDで送信される。２）競合パケットが到着したが、それは主パケットの後に到着し、パケットがバッファーから確率
【数５１】
2008545356.tif 000053
【０１２５】
で送信される。
【０１２６】
・ rを主パケットが到着するタイム・スロットの終了時におけるバッファー使用量として、h=L-1かつr=Lである場合、次の条件のいずれか一方が満たされれば、到着するパケットは破棄されない。１）競合パケットが到着せず、確率qCqDでパケットがバッファーから送信されない。２）競合パケットが到着したが、それは主パケットの後に到着し、確率
【数５２】
2008545356.tif 000054
【０１２７】
でパケットがバッファーから送信されない。
【０１２８】
・ h=Lの場合、到着する主パケットは破棄される。
【０１２９】
最新のタイム・スロットにおいて主パケットが到着し、前のタイム・スロットの終了時のバッファー使用量がhであると仮定して、最新のタイム・スロットの終了時のバッファー使用量がrであり、かつ到着する主パケットが破棄されない条件つき確率は次のように表すことができる。
【数５３】
2008545356.tif 000055
【０１３０】
同様に、最新のタイム・スロットにおいて主パケットが到着し、前のタイム・スロットの終了時のバッファー使用量がhであると仮定して、最新のタイム・スロットの終了時のバッファー使用量がrであり、到着する主パケットが破棄される条件つき確率は次の様に表すことができる。
【数５４】
2008545356.tif 000056
【０１３１】
ステップ３：このステップでは、ある組の中の(j-1)番目の主パケットが到着するタイム・スロットの終了時のバッファー使用量がgであるとして、その組の主パケットのj番目のパケットが到着するタイム・スロットの終了時のバッファー使用量がrであり、かつ、j番目のパケットが破棄されない場合の、条件つき確率を決定する。この条件つき確率は次のように表すことができる。
【数５５】
2008545356.tif 000057
【０１３２】
同様に、ある組の中の(j-1)番目の主パケットが到着するタイム・スロットの終了時のバッファー使用量がgであるとして、その組の主パケットのj番目のパケットが到着するタイム・スロットの終了時のバッファー使用量がrであり、かつ、j番目のパケットが破棄される場合の条件つき確率は、次のように表すことができる。
【数５６】
2008545356.tif 000058
【０１３３】
ステップ４：このステップでは、1≦a≦nかつ0≦b≦aとして、主パケットの組のはじめのaのパケットのうち、bのパケットが破棄される条件つき確率M(a,b,d)と、そのa番目のパケットが到着するタイム・スロットの終了時のバッファー使用量がdに等しい条件つき確率を決定する。a=1に対しては、確率M(a,b,d)は、すでに述べた式６２および６３に定義されたベクトルSの関数として表現することができる。a>1に対しては、確率M(a,b,d)は、次の式に示すように、A(k,g,j)とB(k,g,j)を用いて再帰的に定義することができる。
【数５７】
2008545356.tif 000059
【０１３４】
ステップ５：このステップでは、kの主パケットのうちνが破棄され、はじめのaのECパケットのうちbが破棄され、a番目のECパケットが到着するタイム・スロットの終了時にバッファー使用量がdに等しい確率D(a,b,d,ν)を求める。ここで、1≦a≦n-k、0≦b≦a、0≦ν≦kである。a=1に対して、確率D(a,b,d,ν)はM(k,ν,j)、A(j,d,k)、B(j,d,k)の関数として表すことができる。a>1に対しては、確率D(a,b,d,ν)はD(a-1,b,d,ν)、A(j,d,k)、B(j,d,k)を用いて、次の式に示すように、再帰的に定義することができる。
【数５８】
2008545356.tif 000060
【０１３５】
kの主データ・パケットのうちνが破棄され、(n-k)のECパケットのうちbが破棄される確率H(ν,b)は次のように表すことができる。
【数５９】
2008545356.tif 000061
【０１３６】
ECプロセスによってリカバリーされるデータ・パケットの数の平均値または期待値Erecは次のように表すことができる。
【数６０】
2008545356.tif 000062
【０１３７】
ここで、
【数６１】
2008545356.tif 000063
【０１３８】
である。
【０１３９】
F.  CBRトラフィク・モデルにおける近似アルゴリズム
Erecの近似値のみを計算をするアルゴリズムは、ベルヌーイ・トラフィック・モデルにおいては通常不要である。なぜなら、式４８に示すようにErecを厳密に算出するには、計算複雑性がO(1)である、式４２、k=L-1に対する式４３、および式４４を計算し、計算複雑性がO(nk)である式４６が必要であるからである。Erecを計算するこのアルゴリズムの全体にわたる計算複雑性は、O(nk)である。この複雑性を表す数は、全ての必要な二項係数が予め計算され、引き続いて使用することができるように格納されていることを想定している。Erecを計算するのに必要な時間は、L=400の場合、Cプログラミング言語を用いて実装し、カリフォルニア州サンタ・クララのIntel社から供給されている3.4GHzのペンティアム(R)マイクロプロセッサーを用いれば、1msec未満である。これは、多くの実施例でのリアル・タイム性の要求に十分合致する速度である。
【０１４０】
残念ながら、CBRトラフィック・モデルでは、Erecの近似値を求めるアルゴリズムが必要である。なぜなら、厳密アルゴリズムの計算複雑性が極めて高いからである。
【０１４１】
１．  厳密アルゴリズムの複雑性
前記の５ステップのアルゴリズムから導かれた式７１は、近似を用いることなく期待値Erec計算するのであるから、ここでは厳密アルゴリズムと呼ぶ。第１ステップでは行列m・kの積を行った上で、行列(L+1)x(L+1)の特異値分解を計算する。これらの演算の計算複雑性はO(mkL3)である。第２ステップと第３ステップを実行するために必要な演算の計算複雑性は、無視することができる。確率M(a,b,d)を計算する第４ステップの演算の計算複雑性はO(k2L)である。確率D(a,b,dν)を計算する第５ステップの演算の計算複雑性はO((n-k)2kL2)である。５段階のアルゴリズムの全体としての計算複雑性は、およそ((mkL3+k2L+((n-k)2kL2)である。しかしながら、現実的な実装では、バッファーの大きさLは、n,kの値よりも１桁または２桁大きいと思われるのであるから、このアルゴリズムの全体としての複雑性はおよそO(mkL3)である。
【０１４２】
表１の要素は、５ステップのアルゴリズムをCプログラミング言語で書いた実装の例を、3.4GHzペンティアム・プロセッサー上で実行した場合の、Erecを計算するために必要な総時間を示している。第１ステップの特異値分解には、ケンブリッジ大学出版局１９９２年、Press他著「Numerical  Recipes  in  C++;  The  Art  of  Scientific  Computing（第２版）」に記載の、「svdcmp」ルーチンを用いた。
【表１】
2008545356.tif 000064
【０１４３】
典型的なマルチメディア無線ネットワークでは、パケット処理装置１０は市場に流通しているIEEE802.11に基づいたワイヤレス・アクセス・ポイント(AP)として実装され、典型的には３００またはそれ以上のパケットにあたるバッファーの格納容量がある。表１の要素がによれば、このようなAPでは、前記の典型的な実装を用いて期待値Erecを計算するのに必要な時間は、少なくとも623msecであるということである。残念ながら、多くのマルチメディア・アプリケーションに対して、ECパラメーター(n,k)をリアル・タイムに適用するためには、少なくとも１桁少ない時間の間にこの計算を行わなければならない。つぎに、かなり少ない時間でErecの概算値を計算する、より複雑性の少ないアルゴリズムを次に導く。
【０１４４】
２．崩壊状態モデル
前記の５ステップのアルゴリズムの目的は、ECリカバリー後の情報の損失を最小化するECパラメーター(n,k)を決定することである。このアルゴリズムを用いて計算をする必要があるのは、バッファー・オーバーフローのためにパケット処理装置１０が１または複数のパケットを破棄してパケット損失が発生した場合のみである。バッファー・オーバーフローが発生するのは、バッファー使用量がLであるか、またはそれに近い値であり、パケット処理装置１０における競合パケットと主パケット両者の累積的な到着頻度が、その装置がパケットをバッファーから送信する頻度に比べて高い場合である。言葉を換えれば、kがLにきわめて近い例外的な場合を除いて、全てのkに対して、定常状態ベクトルSの成分Skは０か、または０に近いということである。
【０１４５】
数値実験によって、これらの予想を確認する。図５ないし７に、異なる競合トラフィック頻度pCに対する定常状態確率Skの分布を示す。この３の例において、m=4、n=6、k=5、pD=0.8である。到着頻度の合計pA+pCがpDに等しいとき、このモデルは平衡状態になり、これはpC=0.5の時に生じる。図５に示す例では、pC=0.52であり、これは、平衡頻度に比べてわずかに大きい。この図に示すように、kが増大するに従って、定常状態確率Skは急速に増大するが、定常状態確率が0.01より大きくなるのは、k>95の場合だけである。pCが増大して、到着頻度の合計pA+pCが転送頻度pDより大きい場合、例えば、図６及び７にそれぞれ示すようにpC=0.6およびpC=0.66のような場合であっても、kがLにきわめて近い場合でない限り、定常状態確率Skは、0であるか0に近い。
【０１４６】
この挙動は、よい近似アルゴリズムの開発に使用できる。定常状態確率Skが0あるいは0に近いトラフィック・モデルのいかなる状態も、システムに対して顕著な影響を与えない。なぜなら、システムは原則としてこの状態にならないからである。図５ないし７に示す例では、Sk≒0である全ての状況のうち大部分は、定常状態モデルの動的変化に影響をほとんど与えないか、全く与えない。結果として、これらの状態を定常状態ベクトルSの計算を行うときに無視したとしても、計算結果に大きな変化を与えないし、Erecの計算値に大きな変化を与えない。
【０１４７】
この観察結果に基づけば、Sk>εであって、εを小さい閾値としたときの、定常状態kのみに対するErecを計算する近似アルゴリズムを導くことができる。この近似アルゴリズムは、Sk>εである全ての状態kが個々のベクトル成分Ck=Sk+L0によって表され、Sk≧εである他の全ての状態kは単一状態C0に崩壊する、崩壊した状態ベクトルCを使用する。L0をバッファー使用量の閾値として、k≦L0でSk≦εが前提とされている。結果として、崩壊した状態ベクトルCは、0≦k≦L-L0に対して、L-L0+1の成分Ckを持つにすぎない。
【０１４８】
式３の遷移行列を、Lにかえて値L-L0を用いて再定義することによって、L+1の成分を持つ定常状態ベクトルSは、L-L0+1のみの成分を持つ崩壊した状態ベクトルCによって、近似的に表すことができる。0≦a,b≦L-L0に対する、状態CaとCbの間の遷移確率を、Ta+L0,b+L0と定義する。この遷移行列は、a,b>0であれば、バッファー使用量の変化を正確に表しているが、a=0であるかまたはb=0である場合には、バッファー使用量の動的変化を近似的に表すにすぎない。この近似は、閾値εに十分に小さな値を選べば、1≦k≦L-L0のときCkの計算の正確性に顕著な影響を与えない。なぜなら、崩壊した状態C0は、確率がεL0という、きわめてまれな頻度でしか発生しないからである。正確にいえば、差の絶対値|Ck-Ck+L0|は1≦k≦L-L0において極めて小さいことが期待できるのである。
【０１４９】
崩壊した状態ベクトルCは、式６２または６３のいずれかに特異値分解を適用し、すでに述べたようにベクトルπに換えてベクトルＣを使った式５２を用いて前記結果を正規化することによって、計算することができる。ベクトルCを計算した後、Erecの近似値は、ベクトルSではなくベクトルCを用いて式７１から計算できる。図５ないし７の例から、値L0は値Lに近いことが予想できるので、計算複雑性をO(mkL3)からO(mk(L-L0)3)に減少させることができるということが予想できる。表１でバッファーの大きさLに換えて値L-L0を使用して、L0が充分にLに近い場合、この典型的な実装の実行時間を１桁またはそれ以上減少させることがわかる。L0の値は、多くのマルチメディア・アプリケーションのリアル・タイム性の要求を満たすような、近似アルゴリズムの実装ができる値が選ばれる。
【０１５０】
近似アルゴリズムを使用する前に、L0を決定しなければならない。数値シミュレーションによれば、μ=0.1として、pA+pC>pD+μである場合は常に、近似アルゴリズムの正確性を顕著に下げることなく、L0=10を選ぶことができる。式７１から計算されたErecの正確な値とともに、近似アルゴリズムに使用するために、μの異なる値に対して適切であるL0の値の組を予め計算しておくことができる。これは、L0のどの値を使用すれば近似アルゴリズムがErecを見積もる上で正確性を維持できるのかを決定するためである。
【０１５１】
この崩壊した定常状態近似技術は、原則としていかなるトラフィック・モデルに対しても、計算複雑性を減少したアルゴズムを得るために使用することができる。
【実施例】
【０１５２】
G  実施例
前記の技術を使用して、パケット通信システムにおける様々な種類の実施例を実装するアルゴリズムを導くことができる。
【０１５３】
ある実施例では、前記のアルゴリズムを使用して、パラメーターpA、pC、pD、LおよびECパラメーター(n,k)が与えられたときの、ECリカバリー後の主パケットの損失確率を計算する。
【０１５４】
ある実施例では、ECパラメーター(n,k)を順応させて、ECリカバリー後の主データ・パケットの損失を最小化する。これを実現する一つの方法は、検討中の通信システムに対して、全ての適切なパラメーター値の組(n,k)を、はじめに決定しておくことである。通信経路帯域幅および最大許容遅延などのこのシステムに関する制約は、ECパラメーターの選択に関しても制約となる。帯域幅に関する制限は比率φに関する制限となり、遅延に関する制限は、パラメーターnに関する制限となる。最大限許容可能な遅延の総量と帯域幅を規定した上で、これらの要求を満たすECパラメーターの組(n,k)を全て特定することによって、適切なパラメーターの値の組(n,k)を決定することができる。上に導いたアルゴリズムを、パラメーターpA、pC、pD、Lおよび、適切なECパラメーターの値の全部又は一部に適用することによって、関連する損失確率を計算することができる。損失確率を最も下げるECパラメータの値(n,k)が、パラメーターの最適な組として選択される。
【０１５５】
他の実施例は、データ源２が主パケットを送信する最適な頻度を決定するために使用される。この実施例では、ECパラメーター(n,k)の値を選択し、異なるパケット到着頻度pAに対して前記のアルゴリズムを適用して、関連する損失確率を計算する。多くの場合、実施上の配慮から、考え得る頻度に関して制限がある。損失確率を最小化する頻度は、データ源の最適送信頻度として設定される。
【０１５６】
別の方法として、導かれたアルゴリズムを、ECパラメーター(n,k)とパケット到着頻度の両者の一連の値に適用して、損失確率を最小化する設定を決定する。
【０１５７】
さらに別の実施例では、パラメーターpA、pD、L、ECパラメーター(n,k)、および、ECリカバリー後の主パケットを損失する割合を与えて、競合パケットが到着する確率を表すpCを計算する。前記のアプリケーションは、パラメーターpA、pC、pD、Lの値は既知のものであることを想定している。pCの値が未知である場合、EC保護がないときはpCの値はパラメーターpA、pD、Ploss、およびLから得ることができ、EC保護があるときは、pA、n、k、pD、Eloss、およびLから得ることができる。例えば、データ源２において、pCを計算する反復処理が実装されてもよい。この処理は、データ源２からpA、n、およびkの値を得ることができ、レシーバー２０からpD、および、PlossまたはElossの値を得ることができる。Lの値は通常はア・プリオリにわかっているのであるが、仮にわかっていなかった場合にはパケット処理装置１０から得ることができる。反復を行う方法は、次のパラグラフで述べる。このプロセスで計算されるpcの値は、すでに述べたアルゴリズムの入力パラメーターとして使うなど、他の実施例において使用することもできる。
【０１５８】
EC保護がない場合、ベルヌーイ・トラフィック・システムのpcの値は、式２および式４２ないし４４に定められた関係から決定することができる。CBRトラフィック・モデルでは、この値は、式２に定められた関係と、式５３に関連して述べた前記の技術から決定することができる。いずれのタイプのシステムであっても、これらの式によって定められた関係から、pCとPlossの間の関係は単調な一対一写像となる。この写像の特徴を使用して、pcの値に収束する反復的二分探索法によってpcを決定することができる。
【０１５９】
EC保護がある場合、ベルヌーイ・トラフィック・システムのpcの値は、式２および４８に定められた関係から決定することができる。CBRトラフィック・モデルでは、その値は、式２および７１に定められた関係から決定することができる。いずれのタイプのシステムであっても、これらの式によって定められた関係から、pCとErecの間の関係は単調な一対一写像となる。この写像の特徴を使用して、pcの値に収束する反復的二分探索法によってpcを決定することができる。
【０１６０】
多くの実装では、nとkの適切な選択は、帯域幅と遅延の要求によって制限を受ける。前のパラグラフで記載したアルゴリズムを使用して、全ての適切なnとkの組の中から、ECリカバリー後の損失確率を最小化するECパラメーター(n,k)を発見することができる。pcの値は前記の方法で決定され、nとkの全ての適切な値に対する探索が行われて、最適値を見つける。
【０１６１】
H実装
図１によれば、通信経路３、５、１１、２１、および２２は、金属線を経由する電気信号、光ファイバーを経由する光信号、空間を経由する無線周波数(RF)放射のような、原則として任意の技術とメディアによって実装することができる。本発明は、図１に示すような、通信経路１１が無線RF経路であり、他の通信経路が電気又は光経路である通信システムの場合に、有利に使用することができる。
【０１６２】
本発明の様々な実施態様を実施するのに必要な機能は、個別の論理要素、集積回路、１または複数のASIC、ないしプログラム制御プロセッサーを含む様々な方法によって実装することができる。これらの要素が実装される態様は、本発明にとって重要ではない。
【０１６３】
本発明をソフトウェアとして実装した場合、超音波領域から紫外線領域を含む周波数帯域のベースバンドあるいは変調された通信経路、または、磁気テープ、磁気カード、磁気ディスク、光カード、光ディスク、紙を含む媒体上の可読性のあるマークを含む、原則として任意の記録技術を用いた情報を運ぶ記憶媒体のような、様々な種類の機械可読媒体に搭載することができる。
【図面の簡単な説明】
【０１６４】
【図１】通信システムの概略図である。
【図２】CBRトラフィック・モデルの、タイム・スロットごとにアレンジされたパケットの組の概略図である。
【図３】CBRトラフィック・モデルの、タイム・スロットごとにアレンジされた主パケットの組の概略図である。
【図４】CBRトラフィック・モデルの、タイム・スロットごとにアレンジされた主パケットの組の概略図である。
【図５】バッファー使用状態の関数としての定常状態確率を表す図である。
【図６】バッファー使用状態の関数としての定常状態確率を表す図である。
【図７】バッファー使用状態の関数としての定常状態確率を表す図である。
【図１】
2008545356.tif 000065
【図２】
2008545356.tif 000066
【図３】
2008545356.tif 000067
【図４】
2008545356.tif 000068
【図５】
2008545356.tif 000069
【図６】
2008545356.tif 000070
【図７】
2008545356.tif 000071
【手続補正書】
【提出日】平成20年4月17日(2008.4.17)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０１４１
【補正方法】変更
【補正の内容】
【０１４１】
１．  厳密アルゴリズムの複雑性
前記の５ステップのアルゴリズムから導かれた式７１は、近似を用いることなく期待値Erec計算するのであるから、ここでは厳密アルゴリズムと呼ぶ。第１ステップでは行列m・kの積を行った上で、行列(L+1)x(L+1)の特異値分解を計算する。これらの演算の計算複雑性はO(mkL3)である。第２ステップと第３ステップを実行するために必要な演算の計算複雑性は、無視することができる。確率M(a,b,d)を計算する第４ステップの演算の計算複雑性はO(k2L)である。確率D(a,b,dν)を計算する第５ステップの演算の計算複雑性はO((n-k)2kL2)である。５段階のアルゴリズムの全体としての計算複雑性は、およそO(mkL3+k2L+((n-k)2kL2))である。しかしながら、現実的な実装では、バッファーの大きさLは、n,kの値よりも１桁または２桁大きいと思われるのであるから、このアルゴリズムの全体としての複雑性はおよそO(mkL3)である。
【国際調査報告】
2008545356.tif 000072
2008545356.tif 000073