(57)【要約】【課題】送信のために１つのデータストリームに複数のデータストリームを多重化すること。【解決手段】複数のデータストリームを１つのデータストリームに比例して多重化可能にする方法およびシステムが開示される。移動局１２は別個のデータストリームを形成するアプリケーションを有する。例示アプリケーションは音声３２、シグナリング３４、Ｅ−メール３６およびウエブアプリケーション３８を含む。データストリームはマルチプレクサによりトランスポートストリーム５０と呼ばれる１つのデータストリームに結合される。トランスポートストリーム５０は逆方向リンクを介してＢＴＳ１４に送られる。マルチプレクサモジュール４８は相対比率および優先度に従ってデータストリームをトランスポートストリームに結合する。【選択図】図２
2004503176.tif 000002
【特許請求の範囲】
【請求項１】
下記工程を具備する、１つのデータストリームに複数のデータストリームを多重化する方法：
キューのリストを作成する、各キューはデータストリームを表し、前記データストリームの比率値に反比例する長さを有し、各データストリームは少なくとも１つのパケットから構成される；
各フレームに対して前記比率値の反比例により各キューをインクリメントする；
充填されたキューに対応する前記データストリームからパケットをスケジュールする；および
前記充填されたキューを空にする。
【請求項２】
下記工程を具備する、１つのデータストリームに複数のデータストリームを多重化するための方法：
キューのリストを作成する、各キューはデータストリームを表し、前記データストリームの比率値に反比例する長さを有し、各データストリームは少なくとも１つのフレームから構成される；
各フレームに対して前記比率値の反比例により各キューをインクリメントする；
充填されたキューに対応する前記データストリームからフレームをスケジュールする；および
前記充填されたキューを空にする。
【請求項３】
下記工程を具備する、１つのデータストリームに複数のデータストリームを多重化するための方法：
キューのリストを作成する、各キューはデータストリームを表し、前記データストリームの比率値に反比例する長さを有し、各データストリームは少なくとも１つのフレームから構成される；
各フレームに対して前記比率値の反比例により各キューをインクリメントする；
第１にデータストリームを表すキューが満杯かどうかに基づいてかつ第２にデータストリームの優先値に基づいて、単一のデータストリームに複数のデータストリームからのフレームを分配する；および
前記キューが満杯のときキューを空にする。
【請求項４】
下記工程を具備する、１つのデータストリームに複数のデータストリームを多重化するための方法：
キューのリストを作成する、各キューはデータストリームを表し、前記データストリームの比率値に反比例する長さを有し、各データストリームはフレームから構成され、優先度を有する；
各フレームに対して前記比率値の反比例により各キューをインクリメントする；
すべてのキュー長の和に等しい長さのアレイを作成する；
前記アレイが満杯になるまで、充填されたキューに対応するデータストリームの識別子を前記アレイに挿入する；および
前記充填されたキューを空にする。
【請求項５】
前記アレイを介して継続的にループし、前記アレイの先頭の識別子に対応するデータストリームからフレームを送信することをさらに具備する、請求項４の方法。
【請求項６】
フレームが送信されることになっているとき前記アレイを介してループし、前記アレイの先頭の識別子に対応する前記データストリームから前記フレームを送信することをさらに具備する、請求項４の方法。
【請求項７】
下記工程を具備する、１つのデータストリームに複数のデータストリームを多重化するための方法：
複数のアプリケーションにより複数のデータストリームを作成する、各データストリームは少なくとも１つのフレームから構成される；および
前記複数のデータストリームを単一のデータストリームに均一に分配する。
【請求項８】
前記複数のデータストリームを単一のデータストリームに均一に分配する工程は、各データストリームの比率値に基づく、請求項７の方法。
【請求項９】
前記複数のデータストリームを単一のデータストリームに均一に分配する工程は、第１にデータストリームの比率値に基づき、第２にデータストリームの優先度に基づく、請求項７の方法。
【請求項１０】
下記工程を具備する、１つのデータストリームに複数のデータストリームを多重化するための方法：
加入者装置の複数のアプリケーションにより複数のデータストリームを形成する、各データストリームは少なくとも１つのフレームから構成される；
マルチプレクサにより前記複数のデータストリームを受信する；
前記マルチプレクサにより複数のデータストリームを単一のデータストリームにより均一に分配する；および
基地局により前記単一データストリームを受信する。
【請求項１１】
下記を具備する加入者装置：
メモリ；
前記メモリに存在する複数のアプリケーション、各アプリケーションはデータストリームを形成し、各データストリームは少なくとも１つのフレームから構成される；および
各データストリームを受信し、前記複数のデータストリームからフレームを単一データストリームに均一に分配するように構成されたマルチプレクサ。
【請求項１２】
前記マルチプレクサは各データストリームを受信し、前記比率値に基づいて前記複数のデータストリームからフレームを単一のデータストリームに均一に分配するように構成される、請求項１１の加入者装置。
【請求項１３】
前記マルチプレクサは各データストリームを受信し、第１にデータストリームの比率値に基づいて、第２にデータストリームの優先度に基づいて前記複数のデータストリームからフレームを単一のデータストリームに均一に分配するように構成される、請求項１１の加入者装置。
【請求項１４】
下記を具備する無線通信システム：
メモリに存在する複数のアプリケーションとマルチプレクサを有する加入者装置、各アプリケーションは前記マルチプレクサへの入力としてデータストリームを形成し、各データストリームは少なくとも１つのフレームから構成され、前記マルチプレクサはデータストリームの比率値に基づいて前記データストリームからフレームを単一ストリームに均一に分配する；
前記加入者装置に接続され、前記単一ストリームを受信するように構成される基地局；および
基地局に接続される基地局コントローラ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は一般に通信の分野に関し、特に１つのデータストリームに複数のデータストリームを比例して多重化するための新規で改良されたシステムおよび方法に関する。
【０００２】
【関連出願の記載】
符号分割多元接続（ＣＤＭＡ）変調技術の使用は、多数のシステムユーザが存在する通信を容易にするためのいくつかの技術の１つである。時分割多元接続（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）および振幅圧伸シングルサイドバンド（ＡＣＳＳＢ）のようなＡＭ変調方式のような他の技術が知られているが、ＣＤＭＡは他の技術に対して著しい利点を有する。多元接続通信システムにおけるＣＤＭＡ技術の使用は、この発明の譲受人に譲渡され、参照することにより、ここに組み込まれる米国特許第４，９０１，３０７号（発明の名称：「衛星または地上中継器を用いたスペクトル拡散多元接続通信システム」）および米国特許第５，１０３，４５９号（発明の名称：「ＣＤＭＡセルラ電話システムの波形を発生するためのシステムおよび方法」）に開示されている。
【０００３】
複数のデータストリームからのフレームを１つのデータストリームに割当てるための割当て方式を選択することは困難である。多くの割当て方式は性能に関する要求事項に不十分である。例えば、最も短い仕事を最初にやる（ＳＪＦ）方式はより長い仕事を渇望させる。加入者装置／移動電話に関して存在するアプリケーションはタイムリーな方法で処理しなければならない多くのフレームからなるデータストリームを生じる場合がある。さらにＳＪＦ方式において、多くのフレームを有するデータストリームの処理は、処理するフレームが少ない他のデータストリームのために渇望するかもしれない。同様に、後入れ先だし（ＬＩＦＯ）方式はＬＩＦＯキューにおいて最初であったデータストリームからのフレームを渇望することになる。一方先入れ先だし方式は、データストリームの相対的重要度に適応しない。ＦＩＦＯにおいては、すべてのデータストリームはその順番を待たなければならない。従って、極めて重要なデータストリームが多数の重要度の低い処理すべきデータのために待たなければならないかもしれない。データストリームを渇望しない割当て方式が望まれる。データストリームからのフレームがいつ処理されるかについて制限を持つことが望ましい。
【０００４】
いくつかの割当て方式はデータストリーム内のフレーム数を考慮しない。例えば、ＦＩＦＯおよびＬＩＦＯはデータストリームからのフレームがいつ処理キューに入るかに関心があるのみである。これらはデータストリームのサイズを考慮しない。データストリームのサイズを考慮すると同時にデータストリームを渇望させない割当て方式が望まれる。
【０００５】
【課題を解決するための手段】
この発明は、送信のために１つのデータストリームに複数のデータストリームを多重化するためのシステムおよび方法に向けられている。この方法はキューのリストを作る。各キューはデータストリームを表し、データストリームの比例値に反比例する長さを有する。各データストリームは少なくとも１つのパケットまたはフレームから構成される。この発明の一実施形態において、各データストリームは少なくとも１つのパケットから構成される。この発明の他の実施形態において、各データストリームは少なくとも１つのフレームから構成される。各キューは各輸送フレームの比例値の反比例によってインクリメントされる。この発明の一実施形態において、パケットは充填されたキューに対応するデータストリームからスケジュール（ｓｃｈｅｄｕｌｅ）される。この発明の他の実施形態において、フレームは、データストリームを表すキューが一杯かどうか、かつデータストリームの優先度値の両方に基づいて複数のデータストリームから単一のデータストリームに分配される。さらに、この発明の他の実施形態において、第１にデータストリームを表すキューが一杯かどうかに基づいて、第２にキューの優先度に基づいてフレームが分配される。
【０００６】
この発明の一実施形態において、複数のアプリケーションはマルチプレクサにより多重化される複数のデータストリームを供給する。この発明の他の実施形態において、加入者装置は複数のデータストリームを基地局内のマルチプレクサにより多重化する。この発明のさらに他の実施形態において、複数の基地局は基地局コントローラのマルチプレクサにより複数のデータストリームを多重化する。
【０００７】
この発明の一実施形態において、加入者装置はメモリ、メモリに存在する複数のアプリケーションおよびマルチプレクサから構成される。各アプリケーションはデータストリームを生成し、各データストリームは少なくとも１つのフレームから構成される。マルチプレクサは各データストリームを受信し、複数のデータストリームから単一のデータストリームにフレームを均一に分配するように構成される。この発明の一実施形態において、マルチプレクサは各データストリームを受信し、比例値に基づいて複数のデータストリームから単一のデータストリームに均一にフレームを分配するように構成される。
【０００８】
この発明の他の実施形態において、マルチプレクサは各データストリームを受信するように構成され、第１にデータストリームの比例値に基づいて、第２にデータストリームの優先度に基づいて複数のデータストリームからのフレームを単一のデータストリームに均一に分配する。
【０００９】
さらに、この発明の他の実施形態において、無線通信システムは加入者装置と、加入者装置に接続された基地局と、基地局に接続された基地局コントローラから構成される。加入者装置は複数のアプリケーションとマルチプレクサを有し、各アプリケーションはマルチプレクサへの入力としてデータストリームを生じ、各データストリームは少なくとも１つのフレームから構成される。マルチプレクサはデータストリームの比例値に基づいてデータストリームからのフレームを単一のストリームに均一に分配する。
【００１０】
【発明の実施の形態】
この発明の特徴、目的および利点は、同一部に同符号を付した図面とともに以下に述べる詳細な説明からより明らかになるであろう。
【００１１】
この発明が具現化される例示セルラ移動電話システムを図１に示す。例示目的のために、このシステムはここでは、Ｗ−ＣＤＭＡセルラ通信システムの脈絡の中で記載される。しかしながら、この発明はパーソナル通信システム（ＰＣＳ）、無線ローカルループ、構内交換機（ＰＢＸ）あるいは他の知られたシステムのような他の種類の通信システムに適用可能であることが理解されなければならない。ＴＤＭＡおよびＦＤＭＡのような他の良く知られた送信変調方式を利用したシステム並びに他のスペクトル拡散システムはこの発明を採用することができる。
【００１２】
図１に示すように、無線通信ネットワーク１０は一般に複数の移動局（加入者装置またはユーザ機器とも呼ばれる）１２ａー１２ｄ、複数の基地局（基地局トランシーバ（ＢＴＳｓ）またはノードＢとも呼ばれる）１４ａ−１４ｃ、基地局コントローラ（ＢＳＣ）（無線ネットワークコントローラまたはパケット制御機能１６とも呼ばれる）、移動局コントローラ（ＭＳＣ）または交換台１８、パケットデータサービングノード（ＰＤＳＮ）またはインターネットワーク機能（ＩＷＦ）２０、公衆電話交換網（ＰＳＴＮ）２２（一般的には電話会社）、およびインターネットプロトコル（ＩＰ）ネットワーク２４（一般にはインターネット）を含む。簡単の目的のために、４つの移動局１２ａ−１２ｄ、３つの基地局１４ａ−１４ｃ、１つのＢＳＣ１６、１つのＭＳＣ１８および１つのＰＳＤＮ２０が示される。いかなる数の移動局１２、基地局１４、ＢＳＣ１６、ＭＳＣ１８およびＰＤＳＮ２０も有り得ることは当業者に理解されるであろう。
【００１３】
一実施形態において、無線通信ネットワーク１０はパケットデータサービスネットワークである。移動局１２ａ−１２ｄは、携帯電話、ＩＰベースウエブブラウザアプリケーションを実行するラップトップコンピュータに接続されるセルラ電話、相関するハンズフリーカーキットを有するセルラ電話、ＩＰベースウエブブラウザアプリケーションを実行するパーソナルデジタルアシスタンス（ＰＤＡ）、ポータブルコンピュータに組み込まれた無線通信モジュール、または無線ローカルループまたはメーター読取りシステムに見つけられるような固定ロケーション通信モジュールのような多数の異なる種類の無線通信装置のいずれかであり得る。最も一般的な実施形態において、移動局はいかなる種類の通信装置であり得る。
【００１４】
移動局１２ａ−１２ｄは、例えばＥＩＡ／ＴＩＡ／ＩＳ−７０７規格に記載されるような１つ以上の無線パケットデータプロトコルを実行するように有利に構成することができる。特定の実施形態において、移動局１２ａ−１２ｄはＩＰネットワークに向かうことになっているＩＰパケットを発生し、ポイントツーポイントプロトコル（ＰＰＰ）を用いてＩＰパケットをフレームにカプセル化する。
【００１５】
一実施形態において、ＩＰネットワーク２４はＰＤＳＮ２０に接続され、ＰＤＳＮ２０はＭＳＣ１８に接続され、ＭＳＣ１８はＢＳＣ１６およびＰＳＴＮ２２に接続され、ＢＳＣ１６は、例えばＥ１、Ｔ１、非同期転送モード（ＡＴＭ）、ＩＰ、ＰＰＰ、フレームリレイ（Ｆｒａｍｅ Ｒｅｌａｙ）、ＨＤＳＬ、ＡＤＳＬ、またはｘＤＳＬを含むいくつかの公知のプロトコルのいずれかに従って音声および／またはデータパケットの伝送のために構成される有線を介して基地局１４ａ−１４ｃに接続される。他の実施形態において、ＢＳＣ１６はＰＤＳＮ２０に直接接続され、ＭＳＣ１８はＰＤＳＮ２０に接続されない。この発明の他の実施形態において、参照することにより、ここに完全に組み込まれる、ＴＩＡ／ＥＩＡ／ＩＳ−２０００−２−Ａ（ドラフト編集バージョン３０）（１９９９年１１月１９日）として出版された第３世代パートナーシッププロジェクト２「３ＧＰＰ２」、「ｃｄｍａ２０００スペクトル拡散システムのための物理層規格」、３ＧＰＰ２　ドキュメント番号Ｃ．Ｐ０００２−Ａ、ＴＩＡ　ＰＮ−４６９４に規定されるＲＦインタフェースを介して基地局１４ａ−１４ｃと通信する。
【００１６】
無線通信ネットワーク１０の一般的動作の期間、基地局１４ａ−１４ｃは、通話、ウエブブラウジングまたは他のデータ通信に係合された種々の移動局１２ａ−１２ｄから逆方向リンク信号のセットを受信し復調する。所定の基地局１４ａ−１４ｃにより受信された各逆方向リンク信号はその基地局１４ａ−１４ｃ内で処理される。各基地局１４ａ−１４ｃは順方向リンク信号のセットを変調し移動局１２ａ−１２ｄに送信することにより複数の移動局１２ａ−１２ｄと通信することができるようにしてもよい。例えば、図１に示すように、基地局１４ａは第１および第２移動局１２ａ、１２ｂに同時に通信し、基地局１４ｃは第３および第４基地局１２ｃ、１２ｄと同時に通信する。その結果得られたパケットはＢＳＣ１６に送られる。ＢＳＣ１６は一方の基地局１４ａ−１４ｃから他方の基地局１４ａ−１４ｃに特定の移動局１２ａー１２ｄのための呼のソフトハンドオフの調和を含む呼リソース割当ておよび移動度管理機能性を提供する。例えば、移動局１２ｃは２つの基地局１４ｂ、１４ｃと同時に通信している。最終的に移動局１２ｃが基地局の１つ１４ｃから十分に離れて移動すると、その呼は他の基地局１４ｂに渡される。
【００１７】
その送信が一般的な通話であるならば、ＢＳＣ１６はその受信したデータをＭＳＣ１８に経路選択し、ＭＳＣ１８はＰＳＴＮ２２とのインターフェースのためにさらなる経路選択サービスを提供する。その送信がＩＰネットワーク２４に向かうことになっているデータ呼のようなパケットベース送信ならば、ＭＳＣ１８はそのデータパケットをＰＤＳＮ２０に経路選択し、ＰＤＳＮ２０はそのパケットをＩＰネットワーク２４に送るであろう。もう一つの方法として、ＢＳＣ１６はパケットを直接ＰＤＳＮ２０に経路選択し、ＰＤＳＮ２０はパケットをＩＰネットワーク２４に送るであろう。
【００１８】
情報信号が移動局１２から基地局１４に移動する無線通信チャネルは逆方向リンクとして知られる。情報信号が基地局１４から移動局１２に移動する無線通信チャネルは順方向リンクとして知られる。
【００１９】
例示実施形態において、移動局は広帯域符号分割多元接続（Ｗ−ＣＤＭＡ）技術を用いて基地局と通信する。Ｗ−ＣＤＭＡは最近に提案された３Ｇ通信システムである。Ｗ−ＣＤＭＡシステムの一例は、ＩＭＴ−２０００ＣＤＭＡ規格を考慮してＥＴＳＩによりＩＴＵに送られたヨーロッパ電気通信規格協会（ＥＴＳＩ）地上無線アクセス（ＵＴＲＡ）国際電気通信組合（ＩＴＵ）無線送信技術（ＲＩＴ）候補提案に記載されている。Ｗ−ＣＤＭＡシステムの基地局は非同期に動作する。すなわち、Ｗ−ＣＤＭＡ基地局はすべて共通の世界時基準を共有しない。異なる基地局は時間合わせされていない。従って、Ｗ−ＣＤＭＡ基地局はパイロット信号を有するが、Ｗ−ＣＤＭＡ基地局はパイロット信号オフセットだけで識別されないかもしれない。１つの基地局のシステム時間が決定されると、隣接する基地局のシステム時間を推定することに使用することはできない。このため、Ｗ−ＣＤＭＡシステムの携帯電話はシステム内の各基地局と同期化するために３ステップＰＥＲＣＨ取得手続きを使用する。取得手続きの各ステップはＰＥＲＣＨチャネルと呼ばれるフレーム構造内の異なる符合を識別する。符号分割多元接続（ＣＤＭＡ）を用いた無線システムのための工業規格は、その内容が参照することによりここに組み込まれる、「デュアルモード広帯域スペクトル拡散セルラシステムのための移動局−基地局互換性規格」という名称のＴＩＡ／ＥＩＡ暫定基準、ＴＩＡ／ＥＩＡ／ＩＳ−９５およびその子孫（ここでは集合的にＩＳ−９５と呼ばれる）に述べられている。符号分割多元接続通信システムに関するさらなる情報は、この発明の譲受人に譲渡され、参照することによりここに組み込まれる米国特許第４，９０１，３０７号（発明の名称：「衛星または地上レピータを用いたスペクトル拡散多元接続通信システム」）および米国特許第５，１０３，４５９号（発明の名称：「ＣＤＭＡセルラ電話システムにおいて波形を発生するためのシステムおよび方法」）に開示されている。
【００２０】
第三世代ＣＤＭＡ無線通信システムも提案された。ＩＭＴ−２０００ＣＤＭＡ規格を考慮して電気通信産業協会（ＴＩＡ）により国際電気通信組合に送られたｃｄｍａ２０００　ＩＴＵ−Ｒ無線送信技術（ＲＴＴ）候補付託提案はそのような第三世代無線通信システムの例である。ｃｄｍａ２０００のための規格はＩＳ−２０００のドラフトバージョンで与えられ、ＴＩＡにより承認された。ｃｄｍａ２０００提案は多くの点でＩＳ−９５と互換性がある。例えば、ｃｄｍａ２０００とＩＳ−９５の両システムにおいて、各基地局は、その動作をシステム内の他の基地局と時間同期させる。一般には、基地局は、動作を衛星航法システム（ＧＰＳ）シグナリングのような世界時基準に同期させるが、他の機構を使用することができる。同期化時間基準に基づいて、所定の地理的地域の各基地局には、共通の擬似雑音（ＰＮ）パイロットシーケンスが割当てられる。例えば、ＩＳ−９５によれば、２１５チップを有し、２６．６７ミリ秒（ｍｓ）毎に反復するＰＮシーケンスが各基地局によりパイロット信号として送信される。パイロットＰＮシーケンスは各基地局により５１２の起こりうるＰＮシーケンスオフセットの１つで送信される。各基地局はパイロット信号を連続的に送信し、これにより移動局は基地局の送信並びに他の機能を識別することができる。
【００２１】
この発明の例示実施形態において、移動局は複数のアプリケーションを有する。アプリケーションは移動局内に存在し、各アプリケーションは異なるデータストリームを形成する。１つのアプリケーションは１つ以上のデータストリームを形成する。
【００２２】
図２はこの発明の例示実施形態の移動局１２を示す。移動局１２は移動局１２のメモリ４９に存在する音声３２、シグナリング３４、Ｅ−メール３６およびウエブアプリケーション３８を含む。各アプリケーション、音声３２、シグナリング３４、Ｅ−メール３６およびウエブアプリケーション３８はそれぞれ異なるデータストリーム４０、４２、４４、４６を形成する。データストリームはマルチプレクサモジュール４８に結合されてトランスポートストリーム５０と呼ばれる１つのデータストリームになる。トランスポートストリーム５０は逆方向リンクを介して、ベーストランシーバステーション１４（ＢＴＳ）（短く基地局とも呼ばれる）に送られる。
【００２３】
マルチプレクサモジュール４８はデータストリーム４０−４６を相対比率および優先度に従ってトランスポートストリーム５０に結合する。各データストリーム４０−４６は比率値と優先度を有する。比率値はトランスポートストリーム５０のうちでデータストリーム４０−４６が占有するためにスケジュールされる部分の比率を決定する。優先度はスケジュールされたデータストリーム４０−４６が空のときにどのデータストリーム４０−４６がパケットをマルチプレクサモジュール４８に供給するかを決定する。最初に、データストリームの相対比率を用いて、逆方向リンクを介して送信されるデータストリーム４０−４６からフレームをスケジュールする。フレームが空であるデータストリーム４０−４６からスケジュールされるなら、フレームは逆方向リンクを介して送信される最も優先度の高い非ヌルデータストリーム４０−４６からスケジュールされる。
【００２４】
各データストリーム４０−４６は、データストリーム４０−４６が占有するためにスケジュールされるトランスポートストリームの比率を決定する比率値を有する。データストリーム４０−４６が空ならば、マルチプレクサモジュール４８はデータストリーム４０−４６の優先度を用いてどこで次のフレームを得るかを決定する。マルチプレクサモジュール４８は最も優先度の高い非ヌルデータストリーム４０−４６から次のフレームを得る。
【００２５】
データストリーム比率は、データストリームのトランスポートストリームへのマッピングを決定する。マッピングは、マルチプレクサモジュール４８がフレームを得るためにどこを最初に見るかを決定する。この発明の一実施形態において、マッピングはリアルタイムに確立される、すなわちマルチプレクサモジュール４８が処理するデータストリームをアプリケーションが形成するときである。この発明の他の実施形態において、マッピングは、マルチプレクサモジュール４８が処理するデータストリームをアプリケーションが形成する前に確立することができる。当業者には明白であるように、マッピングはリアルタイムである必要はない。例えばマッピングはコンパイル時間で行なうことができる。すなわち、マッピングを行なうためのアルゴリズムはオフラインでコンパイルすることができる。
【００２６】
マッピングテーブル（図示せず）が作られると、マッピングテーブルは、フレーム送信期間、繰り返し有利に参照できるので、各マッピングテーブルエレメントは、どのデータストリームフレームを、マッピングテーブルエレメントに対応したトランスポートフレームスロットに送信すべきかを決定する。
【００２７】
この発明のさらに他の実施形態において、トランスポートストリーム５０にフレームを送信するときマッピングアルゴリズムは連続して実行される。マッピングアルゴリズムを連続して実行する利点は、データストリームの分配を統計的に乱すことなく、データストリーム４０−４６の数の変化および比例混合に迅速に適応するようにマッピングアルゴリズムを高めることができる。しかしながら、このアルゴリズムの使用は、データストリーム４０−４６の数と比例がトランスポートフレームレートに比べてしばしば変化しない時はテーブル方法より効率が悪い。
【００２８】
データストリーム４０−４６の優先度は、空／ヌルであるデータストリーム４０−４６からフレームがくるようにスケジュールされるときのみ、すなわちアプリケーションがこれ以上フレームを形成しないとき、重要である。データストリーム４０−４６が送るべきフレームを持たないとき、そのフレームスロットは、送るべきフレームをもつデータストリーム４０−４６の中で最も高い優先度を持つデータストリームからフレームを送信するのに使用される。すなわち、フレームが空のデータストリーム４０−４６から来るようにスケジュールされるとき、マルチプレクサモジュール３８は、最も優先度の高い非ヌルデータストリーム４０−４６から次のフレームを取る。
【００２９】
この発明の例示実施形態において、マルチプレクサモジュール４８はメディアアクセスコントロール（ＭＡＣ）層内で動作し、高いネットワーク層から比率値とデータストリーム優先度を得る。当業者には明白であるように、データストリームの有線順位は先入れ先だし（ＦＩＦＯ）、後入れ先だし（ＬＩＦＯ）および最短ジョブ優先（ＳＪＦ）のような公知の優先機構を用いて決定することができる。当業者には明白であるように、マルチプレクサモジュール４８は複数のネットワークレベルで動作することができる。
【００３０】
この発明の他の実施形態において、マルチプレクサモジュール４８はハードウエアで実行される。この発明のさらに他の実施形態において、マルチプレクサモジュール４８はソフトウエアとハードウエアの組合せで実行される。当業者には明白であるように、マルチプレクサモジュール４８はソフトウエアとハードウエアのいかなる組合せでも実行できる。
【００３１】
マッピングアルゴリズムは、データストリーム４０−４６からフレームをスケジュールするためにマルチプレクサモジュー４８が使用するスケジュールシーケンスを指定するマップテーブルを作る。各データストリーム４０−４６はフレームをマルチプレクサモジュール４８に供給するようにスケジュールされる。
【００３２】
各データストリームが非ヌル、即ち空でないならば、各データストリーム４０−４６はトランスポートストリーム５０の相対比率を占有するであろう。ｐ１，ｐ２，・・・ｐｎが同じトランスポートストリームを共有するｎデータストリーム４０−４６により取られる相対比率であるとすると、データストリーム１からのｐ１フレーム毎に、データストリーム２からｐ２フレームがあり、データストリーム３からｐ３フレームがあり、・・・、データストリームｎからｐｎフレームがある。
【００３３】
３つの非ヌルデータストリーム４０−４６があるなら、データストリーム１はトランスポートストリーム５０のｐ１／（ｐ１＋ｐ２＋ｐ３）を占有するであろう。ただし、ｐｎはデータストリームｎの比率値である。例えば非ヌルデータストリーム４０−４６、データストリーム１、データストリーム２、およびデータストリーム３が与えられ、データストリーム１が５の比率値（ｐ１＝５）、データストリーム２が３の比率値（ｐ２＝３）、およびデータストリーム３が２の比率値（Ｐ３＝２）であるなら、データストリーム１はトランスポートストリーム５０の５／１０を占有し、データストリーム２はトランスポートストリーム５０の３／１０を占有し、データストリーム３はトランスポートストリーム５０の２／１０を占有するであろう。マップテーブルの長さはｐ１＋ｐ２＋ｐ３であり、この例では１０フレームの長さである。
【００３４】
マップテーブルはマルチプレクサモジュール４８にフレームを提供するようにスケジュールされるデータストリーム４０−４６の数を表す数字の配列である。各配列はトランスポートストリーム５０へのデータストリームフレームのマッピングである。マップテーブル［１，２，３，１，２，１，３，１，２，１］は、第１フレームはデータストリーム１から送られるようにスケジュールされ、第２フレームはデータストリーム２から送られるようにスケジュールされ、第３フレームはデータストリーム３から送られるようにスケジュールされ、第４フレームはデータストリーム１から送られるようにスケジュールされ、第５フレームはデータストリーム２から送られるようにスケジュールされ、第６フレームはデータストリーム１から送られるようにスケジュールされ、第７フレームはデータストリーム３から送られるようにスケジュールされ、第８フレームはデータストリーム１から送られるようにスケジュールされ、第９フレームはデータストリーム２から送られるようにスケジュールされ、および第１０フレームはデータストリーム１から送られるようにスケジュールされることを意味する。
【００３５】
マッピングアルゴリズムは１つのトランスポートストリーム５０にデータフレームの複数のストリーム４０−４６を多重化するので、各ストリーム４０−４６からのフレー０ムは均一に分配される。すなわち、各ストリーム４０−４６のフレームはトランスポートストリーム５０の両端間に均一に分配される。従って、ｐ１＝５、ｐ２＝３、Ｐ３＝２である３つのデータストリームの状況が与えられると、１０トランスポートフレーム毎に、ストリーム１に５つのフレームがあり、ストリーム２に３つのフレームがあり、ストリーム３に２つのフレームがあり、各ストリーム４０−４６に属するフレームはトランスポートストリーム５０に均一に分配される。
【００３６】
マルチプレクサモジュール４８はデータストリームフレームを１つのトランスポートストリームに均一にセットするけれども、複数のデータストリーム４０−４６を１つのトランスポートストリーム５０に公平に分配する１つ以上の方法があるかもしれない。従ってｐ１＝５、ｐ２＝３、およびｐ３＝２の場合、トランスポートストリーム５０に送られた最初の１０フレームは［１，２，３，１，２，１，３，１，２，１］または［１，３，２，１，２，１，３，１，２，１］または［２，１，３，１，２，１，３，１，２，１］または［２，３，１，１，２，１，３，１，２，１］または［３，１，２，１，２，１，３，１，２，１］または［３，２，１，１，２，１，３，１，２，１］であり得る。但し、配列の各数字はデータストリーム番号を表す。配列の左の番号は送られた最初のフレームを表す。マッピングアルゴリズムは公正な分配要件を満足するシーケンスを形成するように有利に変更可能である。
【００３７】
マッピングテーブルが決定されると、マルチプレクサモジュール４８はマッピングテーブルを用いてデータストリーム４０−４６からフレームをスケジュールし、逆方向リンクを介して送るべきデータストリーム４０−４６にフレームがある限りマッピングテーブルシーケンスを反復し続ける。
【００３８】
マッピングアルゴリズムは単一ストリームにデータストリーム４０−４６を多重化するための「バケツ」手法である。各データストリーム４０−４６は「バケツ」により表される。バケツが一杯になると、表されたデータストリーム４０−４６はフレームを供給するようにスケジュール可能である。
【００３９】
データストリーム４０−４６の比率値はデータストリームバケツの深さを決定する。各データストリームバケツはその比率値に反比例する深さを有する。各バケツはバケツの比率値に基づく充填率を有する。充填率はバケツが充填される割合である。各バケツ内のレベルはフレームステップ毎にその充填率でインクリメントされる。データストリームバケツが一杯のときのみ、フレームはマルチプレクサモジュール４８によりデータストリームバケツから取るようにスケジュールすることができる。
【００４０】
この発明の例示実施形態において、マッピングアルゴリズムは以下に示すように擬似コードである。この発明の他の実施形態において、ＳｓとＤｓの初期値はマッピングテーブルのデータストリーム４０−４６のシーケンスを変更するために変更される。
【００４１】
ｐ１，ｐ２，・・・，ｐｎはｎデータストリームの相対比率である。
【００４２】
積を［ｎ＊最小公倍数（ｐ１，ｐ２，・・・，ｐｎ）］（ｐ１，ｐ２，・・・，ｐｎの最小公倍数はアルゴリズムの正当性に影響を与えることなくｐ１，ｐ２，・・・，ｐｎの積により変更可能である。）
ｑ（１）＝積／ｐ１，ｑ（２）＝積／ｐ２，・・・，ｑ（ｎ）＝積／ｐｎとする。
【００４３】
Ｌをｎエレメントを有したリストとする。但し、エレメントの各々は２つのフィールドＳおよびＤを有する。
【００４４】
Ｓｉをリストのｉ番目のエレメントのＳフィールドの値とし、Ｄｉをリストのｉ番目のエレメントのＤフィールドの値とする。リストの最初のエレメントはリストのヘッドと呼ばれる。
【００４５】
コメント：Ｓはストリームを表し、Ｄは深さを表す。
【００４６】
Ｓｉｓの初期値をＳ１＝１，Ｓ２＝２，・・・，Ｓｎ＝ｎと設定する。
【００４７】
Ｄｉｓの初期値をＤ１＝１，Ｄ２＝１，・・・，Ｄｎ＝１と設定する。
【００４８】
各トランスポートフレームスロットの期間：
（ａ）Ｓ１により識別されるデータストリームからフレームを送信する。
【００４９】
Ｄ２？ｑ（Ｓ１）なら、Ｄ２をＤ２−ｑ（Ｓ１）に変更し、次のトランスポートフレームスロットを待つ。
【００５０】
そうでなければ、Ｄ１をｑ（Ｓ１）−Ｄ２に変更し、一時的にリストからヘッドエレメントを除去し、残りのエレメントをそれぞれｉ＝１，２，・・・，のように昇順に索引をつける。（例えば、以前のｉ＋１番目のエレメントが新しいｉ番目のエレメントとなり、以前の２番目のエレメントが新しいヘッドエレメントとなり、３番目のエレメントが新しい２番目のエレメントとなる）、そして、除去したエレメントを以下のようにリストに戻す。
【００５１】
｛Ｄｘを再挿入すべきエレメントのＤフィールドとする。
【００５２】
ｉ＝２エレメントで開始せよ。
【００５３】
ブロック単位でリストＬを参照せよ：
｛　これ以上リストエレメントが無ければ（ｉ？ｎ）：
｛
除去したエレメントをｎ番目のエレメントとして挿入せよ
リスト参照を終了せよ；
｝
そうでなければ
（
Ｄｘ＞Ｄｉならば：
｛
ＤｘをＤｘ−Ｄｉに変更せよ；
次のエレメントに移動せよ（ｉ＝ｉ＋１）；
｝
そうでなければ
｛
ＤｉをＤｉ−Ｄｘに変更せよ；
ｉ番目のエレメントの前に除去したエレメントを挿入せよ；
（（以前のｉ番目のエレメントは新しい（ｉ＋１）番目のエレメントになった））
リスト参照を終了せよ；
｝
｝
｝
次のトランスポートフレームスロットを待て；
｝
図４−５はこの発明の例示実施形態のマッピングアルゴリズムのフローチャートを示す。図４はマッピングアルゴリズムのイニシャライゼーションを示す。
【００５４】
ｐ１，ｐ２，・・・，ｐｎはそれぞれデータストリーム１−ｎの相対比率である１１０。この発明の一実施形態において、積はｎ＊最小公倍数（ｐ１，ｐ２，・・・，ｐｎ）に設定される１１２。他の実施形態において、最小公倍数（ｐ１，ｐ２，・・・，ｐｎ）はｐ１，ｐ２，・・・，ｐｎの積に設定される。
【００５５】
ｑ（１）は積／ｐ１に設定され、ｑ（２）は積／ｐ２に設定され、・・・そしてｑ（ｎ）は積／ｐｎに設定される１１４。リストＬはｎエレメントで作られ、各エレメントは２つのフィールドＳおよびＤを有する１１６。Ｓｉはリストのｉ番目のエレメントのＳフィールドの値を示し、Ｄｉはリストのｉ番目のエレメントのＤフィールドの値を示す１１８。リストの最初のエレメントはリストのヘッドである１２０。
【００５６】
Ｓ１は１に設定され、Ｓ２は２に設定され、・・・Ｓｎはｎに設定される。Ｓフィールドはストリーム番号を表す。Ｄ１は１に設定され、Ｄ２は１に設定され、・・・Ｄｎは１に設定される。Ｄフィールドはストリームの深さを表す１２２。
【００５７】
図５において、フレームはＳ１により識別されるデータストリームから送信される１２４。Ｄ２？ｑ（Ｓ１）ならば１２６、Ｄ１はｑ（Ｓ１）−Ｄ２に設定され１３２、ヘッドエレメントは一時的にリストから除去され、リストの残りのエレメントはそれぞれｉ＝１、２、・・・のように昇順に番号を付け替える１３４。すなわち、以前のｉ＋１番目のエレメントが新しいｉ番目のエレメントとなる。例えば、以前の２番目のエレメントが新しいヘッドエレメントとなり、３番目のエレメントが新しい２番目のエレメントとなる。
【００５８】
Ｄｘは再挿入すべきエレメントのＤフィールドである１３６。ｉは２に設定される１３８。これ以上リストエレメントが無ければ（ｉ？ｎ）１４０、除去されたエレメントはｎ番目のエレメントとして挿入され１４２、アルゴリズムは次のトランスポートフレームを待つ１３０。ｉが？１４０でなければ、ＤｘはＤｉと比較される１４４。Ｄｘ＞Ｄｉならば、ＤｘはＤｘ−Ｄｉに設定されリストの次のエレメントに移動する。すなわちｉはインクリメントされる（ｉ＝ｉ＋１）１４６。Ｄｘ＞Ｄｙでなければ、ＤｉはＤｉ−Ｄｉに設定され１４８、除去されたエレメントはｉ番目のエレメント前に挿入される。アルゴリズムは次のトランスポートフレームスロット１３０を待つ。
【００５９】
次のトランスポートフレームスロットの時間であるとき、すなわち次のトランスポートフレーム条件が真であるとき１３２、フレームはデータストリームＳ１からトランスポートストリーム５０に送信される１２４。
【００６０】
各リストエレメントはＳフィールドにより識別されるデータストリームのためのバケツを表す。バケツの深さはデータストリームの「ｑ」値であり、これはデータストリーム比率値に反比例する。トランスポートフレームスロット毎にすべてのバケツがインクリメントされる。バケツが一番上まで一杯になると、対応するデータストリームのフレームが送信されるようにスケジュールされ、バケツは空から再スタートする。バケツは、バケツを充填するために残された量に従って、昇順に順序づけられる。Ｄフィールドは現在のバケツを充填するために残された量と先行するバケツを充填するために残された量との差分を与える。これは図３に示され、４つのデータストリームに対して４つのバケツがある。バケツＳ１　５２、Ｓ２　５４、およびＳ３　５６は部分的に充填され、バケツＳ４　５８は空である。当業者には明白であるが、マッピングアルゴリズムは一実施形態に従って、メモリ、ソフトウエア、ハードウエアあるいはそれらの組合せにおいて有利に維持することができる。
【００６１】
ｐ１＝１、ｐ２＝２、ｐ３＝３と仮定すると、マッピングアルゴリズムのトレースは以下に示される。
【００６２】
積＝ｎ＊ＬＣＭ＝３＊６＝１８
ｑ（１）＝１８／１＝１８
ｑ（２）＝１８／２＝９
ｑ（３）＝１８／３＝６
図６はイニシャライズされたときのリストを示す。１−１　６０はリストのヘッドである。２−１　６２は第２エレメントである。３−１　６４は第３エレメントである。
【００６３】
Ｓ１は１なので、データストリーム１からのフレームは送信される。
【００６４】
Ｄ２＝１であり、これはｑ（１）＝１８なのでｑ（Ｓ１）より小さい、それゆえＤ１はｑ（Ｓ１）−Ｄ２＝１８−１＝１７に変更される。ヘッドエレメント６０は図７に示すようにリストから除去される。図７とＤｘフィールドは除去したヘッドエレメントのＤフィールドである。今度はｉ＝１を新しいヘッドエレメント２−１と呼び、ｉ＝２を新しい第２エレメント３−１と呼ぶ。
【００６５】
今度はｉ＝２であり、リストが参照されるであろう。ｉ＝２はｎ＝３以上ではないので、ＤｘはＤｉと比較される。図８に示すようにＤｘ＝１７はＤｉ＝Ｄ２＝１より大きいので、Ｄｘ６６はＤｘ−Ｄｉ＝１７−１＝１６に変更される。
【００６６】
次に、アルゴリズムのフローはｉをインクリメントすることによりリスト内の次のエレメントに移動し、リスト参照ブロックに戻る。今度はｉ＝３であり、これはｎ＝３に等しく、それゆえ図９に示すように除去されたエレメントはｎ＝３エレメントとして挿入されリスト参照が終了する。ヘッドエレメントは２−１　６８である。第２エレメントは３−１　７０である。第３エレメントは１−１６　７２である。
【００６７】
次に、アルゴリズムは次のトランスポートフレームスロットを待つ。従って、トランスポートフレームスロットの期間、Ｓ１により識別されたデータストリームからのフレームが送信される。Ｓ１は２であるので、データストリーム２からのフレームが送信される。従ってこの時点におけるマッピングテーブルは［１，２］であり、これは、データストリーム１からのフレームが最初に送信され、データストリーム２からのフレームが２番目に送信されることを意味する。
【００６８】
今度はＤ２＝１であり、ｑ（２）＝９なので、ｑ（Ｓ１）より小さく、それゆえ、Ｄ１はｑ（Ｓ１）−Ｄ２＝９−１＝８に変更される。図１０に示すように、ヘッドエレメント７４はリストから除去され、Ｄｘフィールドは除去したヘッドエレメントのＤフィールドである。今度は、ｉ＝１を新しいヘッドエレメント２−８と呼びｉ＝２を第２エレメント１−１６と呼ぶ。
【００６９】
今度はｉ＝２でありリストが参照される。ｉ＝２はｎ＝３以上ではないので、ＤｘはＤｉと比較される。図１１に示すように、Ｄｘ＝８はＤｉ＝Ｄ２＝１６より大きくないので、ＤｉはＤｉ−Ｄｘ＝１６−８＝８である。ヘッドエレメントは再び２−８　７６である。図１２に示すようにｉ番目のエレメントの前に除去したエレメントが挿入され、リスト参照が終了される。ヘッドエレメントは今度は３−１　７８である。第２エレメントは２−８　８０である。第３エレメントは１−８　８２である。
【００７０】
次に、アルゴリズムは次のトランスポートフレームスロットを待つ。従って、トランスポートフレームスロットの期間、Ｓ１により識別されるデータストリームからのフレームが送信される。Ｓ１は３なので、データストリーム３からのフレームが送信される。従って、この時点におけるマッピングテーブルは［１，２，３］であり、これはデータストリーム１、データストリーム２およびデータストリーム３を意味し、データストリームからのフレームが送信される順番である。
【００７１】
今度はＤ２＝８であり、これはｑ（３）＝６なのでｑ（Ｓ１）より大きく、それゆえ、Ｄ２は図１３に示すようにＤ２−ｑ（Ｓ１）＝８−６＝２　８４に変更される。次にアルゴリズムは次のトランスポートフレームスロットを待つ。従って、トランスポートフレームスロットの期間、Ｓ１により識別されるデータストリームからのフレームが送信される。Ｓ１は３であるので、データストリーム３からのフレームが送信される。従って、この時点のマッピングテーブルは［１，２，３，３］である。
【００７２】
今度はＤ２＝２であり、これはｑ（３）＝６なので、ｑ（Ｓｉ）よりも小さい、それゆえＤ１はｑ（Ｓ１）−Ｄ２＝６−２＝４に変更される。図１４に示すようにヘッドエレメント８６はリストから除去されＤｘフィールドは除去されたヘッドエレメントのＤフィールドである。今度はｉ＝１を新しいヘッドエレメント２−２　８４と呼び、ｉ＝２を新しい第２エレメント１−８　８２と呼ぶ。
【００７３】
今度はｉ＝２であり、リストが参照される。ｉ＝２はｎ＝３以上でないので、ＤｘはＤｉと比較される。Ｄｘ＝４はＤｉ＝Ｄ２＝８より大きくないので、図１５に示すようにＤｉはＤｉ−Ｄｘ＝８−４＝４　８８に変更される。除去されたエレメント８６は図１６に示すようにｉ番目のエレメントの前に挿入され、リスト参照は終了される。
【００７４】
次に、アルゴリズムは次のトランスポートフレームスロットを待つ。従って、トランスポートフレームスロット期間、Ｓ１により識別されるデータストリームからのフレームが送信される。Ｓ１は２なので、データストリーム２からのフレームが送信される。従ってこの時点のマッピングテーブルは［１，２、３，３，２］である。
【００７５】
今度はＤ２＝４であり、ｑ（２）＝９なので、ｑ（Ｓ１）より小さく、それゆえＤ１はｑ（Ｓ１）−Ｄ２＝９−４＝５に変更される。図１７に示すようにヘッドエレメント９０がリストから除去され、Ｄｘフィールドは除去されたヘッドエレメントのＤフィールドである。今度はｉ＝１を新しいヘッドエレメント２−５と呼び、ｉ＝２を新しい第２のエレメント１−４と呼ぶ。
【００７６】
今度はｉ＝２であり、リストが参照される。ｉ＝２はｎ＝３以上でないので、ＤｘがＤｉと比較される。Ｄｘ＝５はＤｉ＝Ｄ２＝４であるので、図１８に示すようにＤｘ９２はＤｘ−Ｄｉ＝５−４＝１に変更される。次に、アルゴリズムのフローはｉをインクリメントすることによりリストの次のエレメントに移動しリスト参照ブロックに戻る。今度はｉ＝３であり、これはｎ＝３に等しく、それゆえ、図１９に示すように、除去されたエレメントはｎ＝３エレメントとして挿入されリスト参照が終了される。
【００７７】
次に、アルゴリズムは次のトランスポートフレームスロットを待つ。従って、トランスポートフレームスロット期間、Ｓ１により識別されるデータストリームからのフレームが送信される。Ｓ１は３であるので、データストリーム３からのフレームが送信される。従って、この時点のマッピングポイントは［１，２、３、３，２、３］であり、これは長さがｐ１＋ｐ２＋ｐ３であるので、最終マッピングテーブルである。
【００７８】
マッピングテーブルはデータストリームからのフレームをスケジュールするために使用される。マッピングアルゴリズムが連続的に実行されるなら、シーケンス［１，２，３，３，２，３］を連続的に形成するであろう。これが真であることを示すために、アルゴリズムのトレースは２以上のフレームに対して示される。この場合リストパターンは自身が反復するように示される。
【００７９】
今度はＤ２＝４であり、これは、ｑ（３）＝６なのでｑ（Ｓ１）より小さく、それゆえ、Ｄ１はｑ（Ｓ１）−Ｄ２＝６−４＝２に変更される。ヘッドエレメント９６は図２０に示すようにリストから除去される。そしてＤｘフィールドは除去されたヘッドエレメントのＤフィールドである。今度はｉ＝１を新しいヘッドエレメント１−４と呼び、ｉ＝２を新しい第２エレメント２と呼ぶ。
【００８０】
今度はｉ＝２であり、リストが参照される。ｉ＝２はｎ＝３以上でないので、ＤｘはＤｉと比較される。Ｄｘ＝２はＤｉ＝Ｄ２＝１より大きいので、図２１に示すように、Ｄｘ９８はＤｘ−Ｄｉ＝２−１＝１に変更される。次に、アルゴリズムのフローはｉをインクリメントすることにより次のエレメントに移動し、リスト参照ブロックに戻る。今度はｉ＝３であり、ｎ＝３に等しく、それゆえ、除去されたエレメントは図２２に示すようにｎ＝３エレメント１００として挿入され、リスト参照が終了される。
【００８１】
次に、アルゴリズムは次のトランスポートフレームスロットを待つ。従って、トランスポートフレームスロット期間、Ｓ１により識別されるデータストリームからのフレームが送信される。Ｓ１は１なので、データストリーム１からのフレームが送信される。
【００８２】
今度はＤ２＝１であり、ｑ（１）＝１８なのでｑ（Ｓ１）より小さく、それゆえＤ１はｑ（Ｓ１）＝１８−１＝１７に変更される。ヘッドエレメント１０２は図２３に示すようにリストから除去され、Ｄｘフィールドは除去されたヘッドエレメントのＤフィールドである。今度はｉ＝１を新しいヘッドエレメント２−１と呼び、ｉ＝２を新しい第２エレメント３−１と呼ぶ。
【００８３】
今度はｉ＝２であり、リストが参照されるであろう。ｉ＝２はｎ＝３以上でないので、ＤｘはＤｉと比較される。ＤｘはＤｉ＝Ｄ２＝Ｄ１より大きいので、図２４に示すようにＤｘ１０４はＤｘ−Ｄｉ＝１７−１＝１６に変更される。次に、アルゴリズムのフローはｉをインクリメントすることによりリストの次のエレメントに移動し、リスト参照ブロックに戻る。今度はｉ＝３であり、これはｎ＝３に等しく、それゆえ除去されたエレメントは図２５に示すようにｎ＝３エレメントとして挿入され、リスト参照が終了される。
【００８４】
次に、アルゴリズムは次のトランスポートフレームスロットを待つ。従って、トランスポートフレームスロット期間、Ｓ１により識別されるデータストリームからのフレームが送信される。Ｓ１は２であるので、データストリーム２からのフレームが送信される。
【００８５】
シーケンス［１，２，３，３，２，３］が送信された後、データストリーム１およびデータストリーム２からのフレームが送信された。図２５は図９と同じであり、アルゴリズムはシーケンスを反復し続けるであろうことを示す。
【００８６】
この発明の他の実施形態において、アルゴリズムはＳｉｓに対して異なるイニシャル値で開始可能であり、ｐ１＝５、ｐ２＝３、ｐ３＝２例に対して他の５つのシーケンスが発生される。例えば、Ｓ１＝２、Ｓ２＝３、Ｓ３＝１の場合、シーケンス［２，１，３，１，２，１，３，１，２，１］が発生される。この発明のさらに他の実施形態において、Ｄｉｓのイニシャル値は異なるシーケンスを発生するように変更することができる。
【００８７】
この発明の一実施形態において、フレームの代わりにパケットが、複数のデータストリームから１つのデータストリームに有利に多重化される。
【００８８】
この発明のさらに他の実施形態において、アルゴリズムは、同じ比率値を有する複数のデータストリームが１つのリストエレメントを共有することを許すように最適化されるので、ｍ以上のデータストリームがあっても（すなわちｍ＜ｎ）であっても多数（ｍ）の固有の比率値がある。従って、すべてのｐｉｓが固有であり、アルゴリズムのＳフィールドが同じ比率値を共有するデータストリームのセットを表すように、アルゴリズムの「ｎ」は「ｍ」に交換すべきである。さらに、アルゴリズムのステップ（ａ）は「セットＳ１に含まれるデータストリームの各々からフレームを送信せよ」に交換される。ｑ（Ｓ１）値は積／ｐｘを表し、ｐｘはセットＳ１のデータストリームにより共有される比率値である。この最適化はアルゴリズム効率を改良する。
【００８９】
この発明の他の実施形態において、バケツサイズは同じだが異なる充填率を採用するマッピングアルゴリズムが使用される。当業者には明白であるように、開示したマッピングアルゴリズムは、バケツが同じサイズを有し、充填率がバケツサイズに反比例して関連し、各データストリームの比率値に基づくように書き換えることが出来る。
【００９０】
この発明の他の実施形態において、２つのデータストリームしか無いとき、上述のアルゴリズムは有利に以下の簡単なアルゴリズムに交換される。ｐ１がｐ２の倍数であるなら、（ａ）と（ｂ）を含めて両者の間のステップを省略することができる。この実施形態に従うマッピングアルゴリズムは以下のように擬似コードで示される。
【００９１】
以下の変数をイニシャライズせよ：
スキップベース（ＳｋｉｐＢａｓｅ）＝ｐ１／ｐ２、但し「／」は整数除算を表す。
【００９２】
初期分数＝ｐ１％ｐ２、但し「％」はモジュロ演算を表す。
【００９３】
スキップカウント（ＳｋｉｐＣｏｕｎｔ）＝０；
分数カウント（ＦｒａｃｔｉｏｎＣｏｕｎｔ）＝０；
各トランスポートフレームスロット期間：
（スキップカウント＝＝０）ならば
｛
データストリーム＃２からフレームを送信せよ；
（ａ）　　　　　　　分数カウント＝分数カウント＋初期分数；
（分数カウント＞＝ｐ２）
｛
スキップカウント＝スキップベース＋１；
分数カウント＝分数カウントーｐ２；
｝
（ｂ）　　　　　　　そうでなければ
｛
スキップカウント＝スキップベース；
｝
｝
そうでなければ
｛
データストリーム＃１からフレームを送信せよ；
スキップカウント＝スキップカウントー１；
｝
当業者に明白であるように、マッピングアルゴリズムはネットワークモジュール間の他の相互接続に適用可能である。それは、モジュールが複数の入力を有し、複数の入力から多重化された出力を形成する状況に適用可能である。例えば、マルチプレクサモジュールはＢＴＳ内に位置することができ、ＢＴＳは複数の移動局からデータストリームを多重化し、ＢＳＣに送信すべき多重化されたデータストリームを形成する。
【００９４】
このようにして、複数のデータストリームを１つのデータストリームに多重化するための新規で改良された方法および装置について記載した。当業者は、ここに開示した実施形態に関連して記載した種々の実例となる論理ブロック、モジュールおよびアルゴリズムステップは電子ハードウエア、コンピュータソフトウエアまたは両者の組合せで実現できることを理解するであろう。種々の実例となる部品、ブロック、モジュール、回路およびステップは一般的にそれらの機能性に関して記載した。機能性がハードウエアとして実現されるかまたはソフトウエアとして実現されるかは特定のアプリケーションおよび全体のシステムに課せられた設計制約に依存する。当業者はこれらの状況下でハードウエアとソフトウエアの機能性の互換性を認識し、そして各特定のアプリケーションに対して記載された機能性をどのように実現するのが最善かを認識する。例として、ここに開示した実施形態に関連して記載した種々の実例となる論理ブロック、モジュール、およびアルゴリズムステップは、ファームウエア命令セットを実行するプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、あるいは他のプログラマブルロジックデバイス、ディスクリートゲートまたはトランジスタロジック、例えばレジスタのようなディスクリートハードウエアコンポーネント、何らかの一般的なプログラマブルソフトウエアモジュールとプロセッサ、またはここに記載した機能を実行するように設計されたそれらのいかなる組合せにより実行することができる。マルチプレクサは便宜的にマイクロプロセッサであってよいが、別の方法では、マルチプレクサはいかなる一般的なプロセッサ、コントローラ、マイクロコントローラあるいは状態機械であってよい。アプリケーションはＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、脱着可能ディスク、ＣＤ−ＲＯＭ、あるいは技術的に知られている何らかの形態の記憶媒体に存在することができる。図２に示すように、基地局１４は、基地局１４から情報を読むように移動局１２に便宜的に接続される。メモリ４９はマルチプレクサ４８と一体化してもよい。マルチプレクサ４８とメモリ４９はＡＳＩＣ（図示せず）に存在してもよい。ＡＳＩＣは電話に存在するかもしれない。
【００９５】
この発明の実施形態の上述の記載は、当業者がこの発明を製作または使用可能にするために提供される。これらの実施形態に対する種々の変更は当業者には容易に明白であり、ここに定義される一般的原理は発明力の使用なしに他の実施形態に適用可能である。従って、この発明はここに示す実施形態に限定することを意図するものではなく、ここに開示する原理および新規な特徴と整合性が取れた最も広い範囲に一致する。
【図面の簡単な説明】
【図１】図１は例示Ｗ−ＣＤＭＡセルラ電話システムの概略図である。
【図２】図２はこの発明の例示実施形態の移動局を示す図である。
【図３】図３は４つのデータストリームの４つのバケツを示す図である。
【図４】図４はフローチャート形態におけるマッピングアルゴリズムのイニシャライゼーションを示す。
【図５】図５はフローチャート形態におけるマッピングアルゴリズムの本体を示す。
【図６】図６はイニシャライズされたときのリストを示す。
【図７】図７はリストから除去されるヘッドエレメントを示す。
【図８】図８は変更された後のＤｘを示す。
【図９】図９はｎ＝３エレメントとして挿入される除去されたエレメントを示す。
【図１０】図１０はリストから除去されたヘッドエレメントを示す。
【図１１】図１１は変更された後のＤ１を示す。
【図１２】図１２はｉ番目のエレメントの前に挿入された除去されたエレメントを示す。
【図１３】図１３は変更された後のＤ２を示す。
【図１４】図１４はリストから除去されたヘッドエレメントを示す。
【図１５】図１５は変更された後のＤ１を示す。
【図１６】図１６はｉ番目のエレメントの前に挿入される除去されたエレメントを示す。
【図１７】図１７はリストから除去されたヘッドエレメントを示す。
【図１８】図１８は変更された後のＤｘを示す。
【図１９】図１９はｎ＝３エレメントとして挿入された除去されたエレメントを示す。
【図２０】図２０はヘッドエレメントがリストから除去されるのを示す。
【図２１】図２１は変更された後のＤｘを示す。
【図２２】図２２はｎ＝３として挿入された除去されたエレメントを示す。
【図２３】図２３はリストから除去されたヘッドエレメントを示す。
【図２４】図２４は変更された後のＤｘを示す。
【図２５】図２５はｎ＝３として挿入された除去されたエレメントを示す。
【図１】
2004503176.tif 000003
【図２】
2004503176.tif 000004
【図３】
2004503176.tif 000005
【図４】
2004503176.tif 000006
【図５】
2004503176.tif 000007
【図６】
2004503176.tif 000008
【図７】
2004503176.tif 000009
【図８】
2004503176.tif 000010
【図９】
2004503176.tif 000011
【図１０】
2004503176.tif 000012
【図１１】
2004503176.tif 000013
【図１２】
2004503176.tif 000014
【図１３】
2004503176.tif 000015
【図１４】
2004503176.tif 000016
【図１５】
2004503176.tif 000017
【図１６】
2004503176.tif 000018
【図１７】
2004503176.tif 000019
【図１８】
2004503176.tif 000020
【図１９】
2004503176.tif 000021
【図２０】
2004503176.tif 000022
【図２１】
2004503176.tif 000023
【図２２】
2004503176.tif 000024
【図２３】
2004503176.tif 000025
【図２４】
2004503176.tif 000026
【図２５】
2004503176.tif 000027
【国際公開パンフレット】
2004503176.tif 000028
2004503176.tif 000029
2004503176.tif 000030
2004503176.tif 000031
2004503176.tif 000032
2004503176.tif 000033
2004503176.tif 000034
2004503176.tif 000035
2004503176.tif 000036
2004503176.tif 000037
2004503176.tif 000038
2004503176.tif 000039
2004503176.tif 000040
2004503176.tif 000041
2004503176.tif 000042
2004503176.tif 000043
2004503176.tif 000044
2004503176.tif 000045
2004503176.tif 000046
2004503176.tif 000047
2004503176.tif 000048
2004503176.tif 000049
2004503176.tif 000050
2004503176.tif 000051
2004503176.tif 000052
2004503176.tif 000053
2004503176.tif 000054
2004503176.tif 000055
2004503176.tif 000056
2004503176.tif 000057
2004503176.tif 000058
2004503176.tif 000059
2004503176.tif 000060
2004503176.tif 000061
2004503176.tif 000062
2004503176.tif 000063
2004503176.tif 000064
2004503176.tif 000065
2004503176.tif 000066
2004503176.tif 000067
【国際公開パンフレット（コレクトバージョン）】
2004503176.tif 000068
【国際調査報告】
2004503176.tif 000069
2004503176.tif 000070
2004503176.tif 000071