(57)【特許請求の範囲】
【請求項１】
複数のユーザからのパケットを多重化する方法であって、
複数のユーザの各々が複数のカテゴリを有する伝送予算に署名するステップであって、各予算カテゴリがリソース保証レベルとユーザによって最初に選択された各ユーザについての関連信用レベルとを有するものである、ステップと、
前記複数のユーザから所定のサービスクラスを有するパケットを受信するステップと、
(i)前記パケットのサービスクラス、(ii)前記パケットの発信元ユーザ、(iii)前記発信元ユーザの伝送予算カテゴリの信用レベル、及び(iv)各予算カテゴリの現在の利用可能性に基いて、各パケットを前記複数の予算カテゴリのうちの１つに動的に割り当てるステップと、
前記パケットが割り当てられた前記発信元ユーザの予算カテゴリの信用レベルを減少させるステップと、
からなる方法。
【請求項２】
前記所定のサービスクラスが優先順位クラスである、請求項１の方法。
【請求項３】
少なくとも１つの予算カテゴリに関連する前記信用レベルが利用可能なバンド幅の大きさに関するものである、請求項１の方法。
【請求項４】
少なくとも１つの予算カテゴリに関連する前記信用レベルがユーザ間でのバンド幅の分配を決めるウェイトに関するものである、請求項１の方法。
【請求項５】
前記複数の予算カテゴリが、保証予算カテゴリ、調整予算カテゴリ、及び、最善予算カテゴリを含む、請求項１の方法。
【請求項６】
前記保証予算カテゴリ及び前記調整予算カテゴリの信用レベルが利用可能なバンド幅の大きさに関するものであり、前記最善予算カテゴリの信用レベルがユーザ間でのバンド幅の分配を決めるウェイトに関するものである、請求項１の方法。
【請求項７】
パケット多重化システムであって、
複数のユーザからパケットを受信するための入力手段であって、前記パケットの各々が所定のサービスクラスを有し、前記ユーザの各々が関連伝送予算を有するものである、入力手段と、
伝送予算カテゴリに関連付けられた複数のストリームセレクタからなる送信器と、
(i)前記パケットのサービスクラス、(ii)前記パケットの発信元ユーザ、(iii)前記発信元ユーザの伝送予算、及び(iv)前記ストリームセレクタの各々の現在の利用可能性に基いて、受信したパケットの各々を前記ストリームセレクタのうちの１つに動的に割り当てるための少なくとも１つのサービスセレクタと、
からなるパケット多重化システム。
【請求項８】
前記送信器と通信する通信ネットワークをさらに含み、該通信ネットワークが前記送信器から送信されたパケットを受信する、請求項７のパケット多重化システム。
【請求項９】
通信路マルチプレクサであって、
複数クラスのサービスキューと、
１クラスのサービスセレクタ出力端子および複数クラスのサービスセレクタ入力端子を有する１クラスのサービスセレクタと、
複数のストリームセレクタであって、該複数のストリームセレクタのそれぞれがストリームセレクタ出力端子および複数のストリームセレクタ入力端子を有し、該ストリームセレクタ入力端子のそれぞれ1つが前記クラスのサービスセレクタ出力端子と通信する、複数のストリームセレクタと、
からなり、
前記複数クラスのサービスキューのそれぞれが、前記複数クラスのサービスセレクタ入力端子のうちの対応する1つと通信し、
前記複数のストリームセレクタのそれぞれが複数の予算カテゴリのうちの1つに関連し、
複数のストリームセレクタのうちの選択された１つから前記クラスのサービスセレクタへの要求に応答して、前記クラスのサービスセレクタが複数の前記クラスの入力端子のうちの1つから受信したパケットを前記複数のストリームセレクタ入力端子のうちの選択された１つに送信する、通信路マルチプレクサ。
【請求項１０】
前記複数のストリームセレクタが３つのストリームセレクタを含み、前記３つのストリームセレクタのうちの１つが最善予算と関連し、前記３つのストリームセレクタのうちの１つが調整配送予算と関連し、前記３つのストリームセレクタのうちの１つが保証帯域幅予算と関連している、請求項９の通信路マルチプレクサ。
【請求項１１】
出力端子および複数のレベルセレクタ入力端子を有するレベルセレクタをさらに含み、該レベルセレクタ入力端子のそれぞれが前記複数のストリームセレクタのうちの対応する１つの前記ストリームセレクタ出力端子と通信している、請求項９の通信路マルチプレクサ。
【請求項１２】
複数クラスのサービスセレクタをさらに含み、各クラスのサービスセレクタが１クラスのサービスセレクタ出力端子と複数クラスのサービスセレクタ入力端子とを有し、各クラスのサービスセレクタ出力端子が前記複数のストリームセレクタの複数のストリームセレクタ入力端子と通信する、請求項９の通信路マルチプレクサ。
【請求項１３】
速度リミッタをさらに含み、該速度リミッタが複数の速度リミッタ入力端子および複数の速度リミッタ出力端子を有し、前記速度リミッタ入力端子のそれぞれが対応するストリームセレクタの出力端子と通信し、前記速度セレクタ出力端子のそれぞれが前記複数のレベルセレクタ入力端子のうちの対応する１つと通信する、請求項１１の通信路マルチプレクサ。
【請求項１４】
通信ネットワークであって、
１クラスのサービスセレクタ出力端子および複数クラスのサービスセレクタ入力端子を有する１クラスのサービスセレクタと、
複数のストリームセレクタであって、該ストリームセレクタのそれぞれがストリームセレクタ出力端子および複数のストリームセレクタ入力端子を有し、該複数のストリームセレクタのストリームセレクタ入力端子のうちの１つが前記クラスのサービスセレクタ出力端子と通信する、複数のストリームセレクタと、
出力端子および複数のレベルセレクタ入力端子を有するレベルセレクタであって、前記複数のレベルセレクタ入力端子のそれぞれが前記ストリームセレクタ出力端子の対応する１つと通信する、レベルセレクタと、
からなる通信路マルチプレクサと、
複数クラスのサービスキューであって、前記クラスのサービスキューのそれぞれが前記複数クラスのサービスセレクタ入力端子のうちの対応する１つと通信する、複数クラスのサービスキューと、
通信パケットストリームを受信するためのヘッダアナライザ入力端子および複数のヘッダアナライザ出力端子を有するヘッダアナライザであって、前記ヘッダアナライザ出力端子のそれぞれが前記複数クラスのサービスキューのうちの対応する１つと通信する、ヘッダアナライザと、
前記レベルセレクタ出力端子と通信するＭＡＣ入力端子を有するＭＡＣインタフェースと、
からなり、
前記複数のストリームセレクタのそれぞれが複数の予算カテゴリのうちの１つと関連し、
前記クラスのサービスセレクタは、前記複数のストリームセレクタのうちの選択された１つから前記クラスのサービスセレクタで受信した要求に応答して、パケットを前記複数のサービスキューのうちの１つから前記複数のストリームセレクタ入力端子のうちの選択された１つへ送信する、通信ネットワーク。
【請求項１５】
速度リミッタをさらに含み、該速度リミッタが複数の速度リミッタ入力端子および複数の速度リミッタ出力端子を有し、前記複数の速度リミッタ入力端子のそれぞれが前記複数のストリームセレクタのうちの１つの前記ストリームセレクタ出力端子と通信する、請求項１４の通信ネットワーク。
【請求項１６】
速度調節器をさらに含み、該速度調節器が速度調節器入力端子および速度調節器出力端子を有し、前記速度調節器入力端子が前記レベルセレクタ出力端子と通信し、前記速度調節器出力端子が前記ＭＡＣ入力端子と通信する、請求項１４の通信ネットワーク。
【請求項１７】
前記ＭＡＣインタフェースがノード準備出力端子を有し、前記速度調節器出力端子がノード要求入力端子を有し、前記速度調節器は、前記ＭＡＣインタフェースにより前記ノード準備出力端子に供給される信号の少なくとも一部に応答して、パケットを前記速度調節器出力端子に供給する、請求項１６の通信ネットワーク。
【請求項１８】
前記ＭＡＣアドレスインタフェースは、速度調節器入力端子を有する速度調節器を含み、前記速度調節器入力端子が前記ＭＡＣ入力端子である、請求項１４の通信ネットワーク。
【請求項１９】
パケットを多重化する方法であって、該パケットのそれぞれが１クラスのサービスを有するものにおいて、
パケットを複数クラスのサービスキューのうちの１つに受信するステップと、
前記パケットを１クラスのサービスセレクタに受信するステップと、
前記複数のストリームセレクタのうちの１つから前記クラスのサービスセレクタへの送信適格権の利用可能性に応じて、前記パケットを複数のストリームセレクタのうちの１つに割り当てるステップと、
からなる方法。
【請求項２０】
前記パケットを送信するステップはレベルセレクタパケット要求にも責任を負う、請求項１９の方法。
【請求項２１】
前記パケットを前記レベルセレクタに送信するときの速度を調節するステップをさらに含む、請求項２０の方法。
【請求項２２】
前記送信適格権の利用可能性は、前記複数のストリームセレクタへのパケットの事前の割り当てに責任を負う、請求項１９の方法。
【請求項２３】
前記パケットの送信の前に前記パケットの送信適格権利を判定するステップをさらに含む、請求項２０の方法。
【発明の詳細な説明】
【０００１】
本出願は、２０００年２月８日付けの米国特許仮出願番号６０／１８１，００３の出願に基づいて優先権を主張する。
【０００２】
【発明の属する技術分野】
本発明は電気通信の分野に関し、詳しくはユーザシステムの集合体におけるパケット転送の管理に関するものである。
【０００３】
【従来の技術】
ユーザがデジタルデータストリームの転送を望む場合、しばしば広帯域幅の通信路が必要となる。データストリームには、大きな遅延が許容されない高優先順位のデータ（例えば音声通信など）から低優先順位のデータ（例えば電子メールなど）まで、様々な優先順位のデータが含まれる場合がある。
【０００４】
通信ネットワークに対するアクセス手段は、通常、電気通信サービスプロバイダによって提供され、彼らがネットワーク上のノードの設備を保守している。一般に、サービスプロバイダは、ネットワークに対するアクセス手段を複数のユーザに提供する。ユーザは、複数のデータストリームを供給する場合がある。十分な容量（例えば帯域幅など）を確保するため、ユーザは、個々のデータストリームに必要とされる最大予想帯域幅要件を扱うことのできる複数の個別の通信路を契約する場合がある。通常、通信路は、特定の通信に関連する物理回線、時分割多重（ＴＤＭ）システムにおいて割り当てられるタイムスロット、または、周波数分割多重（ＦＤＭ）システムにおける特定の周波数（例えば光波長分割多重（ＷＤＭ）システム波長領域など）である。
【０００５】
【発明が解決しようとする課題】
複数のデータストリームを有するユーザは、各データストリームの最大予想帯域幅を確保するために複数の個別の通信路を用意しなければならないことがある。多くの場合、これらの通信路は最大帯域幅のごく一部で動作している。その結果、ユーザは必要とされる平均帯域幅を大幅に越えて帯域幅容量を購入することになるので、これら個々の通信路が常に最大容量付近で動作していたときに比べてコストが高くなる。
【０００６】
【課題を解決するための手段】
特許請求をする発明は、電気通信ネットワークにおけるデータ転送（即ちトラフィック）を管理する方法に関するものである。個別のエンドユーザのデータストリームを専用の固定帯域幅の通信路でサポートするのではなく、データストリームを他のエンドユーザのデータストリームと共に多重化することにより、通信路の効率的な利用を達成する。帯域幅を様々なユーザに動的に割り当て、ユーザの通信コストを効率的に削減する。電気通信プロバイダは、統計的多重化の改良に関連してリソースの利用効率が向上し、これに関連してサポートコストも低減されるので、利益が得られる。
【０００７】
本発明は、複数のパケットを通信ネットワーク内に多重化するためのマルチプレクサおよび方法に関する。
【０００８】
一実施形態において、本マルチプレクサは、所定のクラスを有するパケットと、該パケットを受信する受信器と、該受信器と通信する送信器とを含む。送信器は、所定の予算および所定のクラスのパケットに応じてパケットを送信する。この実施形態において、所定の予算には複数の所定のクラスが含まれる。他の実施形態では、マルチプレクサには、送信器と通信する通信ネットワークも含まれる。
【０００９】
一実施形態において、本方法は、所定のクラスを有するパケットを受信するステップと、所定の予算および所定のクラスのパケットに応じてパケットを送信するステップとを含む。この実施形態において、所定の予算には、複数の所定のクラスが含まれる。これらの所定のクラスは、優先順位クラスとすることができる。さらに別の実施形態では、所定の予算は、複数の予算のうちの１つである。
【００１０】
一実施形態において、本方法は、所定のクラスを有するパケットを受信するステップと、所定の予算および所定のクラスのパケットに応じて通信ネットワークを介してパケットを送信するステップとを含む。この実施形態において、所定の予算には、複数の所定のクラスが含まれる。
【００１１】
一実施形態において、本マルチプレクサは、１クラスのサービスセレクタと複数クラスのストリームセレクタとを含む。１クラスのサービスセレクタは、複数の入力端子および１つの出力端子を有する。各ストリームセレクタは、予算カテゴリに関連付けられ、複数の入力端子および１つの出力端子を有する。各ストリームセレクタの入力端子のうちの１つは、１クラスのサービスセレクタと通信する。１クラスのサービスセレクタは、選択されたストリームセレクタからの要求に応じて、その入力端子のうちの１つからストリームセレクタのうちの１つの選択された入力端子にパケットを送信する。
【００１２】
一実施形態において、本マルチプレクサは複数クラスのサービスキューを含み、各キューがそのクラスのサービスセレクタの入力端子のうちの１つと通信している。他の実施形態において、マルチプレクサは複数クラスのサービスセレクタを含む。各クラスのサービスセレクタは１つの出力端子および複数の入力端子を有する。そのクラスのサービスセレクタの各出力端子はストリームセレクタの各々の入力端子のうちの１つと通信している。さらに別の実施形態において、マルチプレクサは、複数のストリームセレクタのうちの１つと通信する入力端子と、出力端子とを有する。さらに別の実施形態において、マルチプレクサは、ストリームセレクタの出力端子の１つと通信する入力端子およびレベルセレクタの入力端子の１つと通信する出力端子を有する速度リミッタをさらに含む。
【００１３】
一実施形態において、本方法は、パケットを１クラスのサービスセレクタに受信するステップと、ストリームセレクタからの送信適格権の利用可能性に応じて前記パケットを該ストリームセレクタに割り当てるステップとを含む。さらに別の実施形態において、本方法は、パケットを１クラスのサービスセレクタに受信する前に該パケットを複数クラスのサービスキューのうちの１つに受信するステップをさらに含む場合がある。他の実施形態において、本方法は、パケットがレベルセレクタに送信される速度を調節するステップをさらに含む場合がある。さらに別の実施形態において、本方法は、パケットを送信する前にそのパケットの適格性を判定するステップをさらに含む場合がある。
【００１４】
【発明の実施の形態】
ユーザには、署名したサービスのクラスに従って帯域幅が割り当てられる。ユーザは、通常、送信するデータの重要性（例えば優先順位など）および予想されるトラフィックの量に従って、様々な予算カテゴリに署名する。したがって、ユーザは、１０Ｍビット／秒の保証された帯域幅、１０Ｍビット／秒の調節された帯域幅、および、２０の最善ウェイトに署名する場合がある。最善予算カテゴリのために利用することのできるあらゆる帯域幅は、ユーザの最善署名の相対的なウェイトに従って分散される。
【００１５】
図１を参照すると、ユーザデータストリーム１０’、１０’’、１０’’’（まとめて１０で示す）の各々からのデータパケットは、複数のヘッダアナライザ１４’、１４’’、１４’’’（まとめて１４で示す）のうちの対応する１つに受信される。各ヘッダアナライザ１４は、ユーザデータストリーム１０からのデータパケットのヘッダを読み取る。そして、ヘッダアナライザ１４は、このデータパケットをそのヘッダアナライザ１４と関連する３クラスのサービスキュー１８’、２２’２６’、１８’’、２２’’、２６’’、１８’’’、２２’’’、２６’’’（まとめて１８、２２、２６で示す）のうちの１つに渡す。
【００１６】
それぞれのクラスのサービスキュー１８，２２，２６は、高優先順位、中優先順位および低優先順位からなるデータ優先順位のうちの１つに対応する。これを例示する目的で、サービスキュー１８のクラスが高優先順位データに対応し、サービスキュー２２のクラスが中優先順位データに対応し、サービスキュー２６のクラスが低優先順位データに対応するものとする。ユーザデータストリーム１０からのデータパケットは、そのデータパケットが高優先順位としてマークされていることをパケットヘッダが示す場合、高優先順位のサービスキュー１８に置かれる。同様に、そのパケットが中優先順位または低優先順位としてマークされていることをパケットヘッドが示す場合、そのデータパケットは、中優先順位のサービスキュー２２または低優先順位のサービスキュー２６に置かれる。
【００１７】
パケットは、いったんいずれか１クラスのサービスキュー１８，２２，２６に入ったあと、１クラスのサービスセレクタ３０’、３０’’、３０’’’（まとめて３０で示す）によってそのキュー１８、２２，２６から除去され、ストリームセレクタ５０’、５０’’、５０’’’（全部を５０で示す）に提出される。各クラスのサービスセレクタ３０は、それぞれ４本の線：high ready３４’、３４’’、３４’’’（まとめて３４で示す）、ready３８’、３８’’、３８’’’（まとめて３８で示す）、packet４２’、４２’’、４２’’’（まとめて４２で示す）、および、transmit４４’、４４’’、４４’’’（まとめて４４で示す）を用いてすべてのストリームセレクタ５０と通信する（分かりやすくするため、これら４本の線は、第１のクラスのサービスセレクタ３０のものしか描かれていないことに注意して欲しい）。１クラスのサービスセレクタ３０は、ストリームセレクタ５０から命令を受けると、１クラスのサービスキュー１８、２２、２６から前記パケットを除去して該パケットを前記ストリームセレクタ５０のうちの１つに送信する。各ストリームセレクタ５０は、予算カテゴリ：保証（guaranteed）、調整（regulated）または最善（best effort）のうちの１つに対応している。例示のみの目的で、ストリームセレクタ５０’は保証予算に関連し、ストリームセレクタ５０’’は調整予算に関連し、ストリームセレクタ５０’’’は最善予算に関連している。ストリームセレクタ５０は、パケットをその対応する予算カテゴリに送信するために利用することのできる何らかの帯域幅予算が存在するか否かを判定する。
【００１８】
本システムが最大の柔軟性を示すのは、データパケットを前記クラスのサービスキュー１８、２２、２６からストリームセレクタ５０へ転送するときである。各クラスのサービスキュー１８、２２、２６を唯一のストリームセレクタ５０’、５０’’、５０’’’に関連づけることに代えて、本システムは、各クラスのサービスセレクタ３０がパケットをいずれのストリームセレクタ５０’、５０’’、５０’’’に送信すべきをインテリジェントに選択できるようにしている。各クラスのサービスキュー１８、２２、２６をストリームセレクタ５０’、５０’’、５０’’’から分離することによって、ユーザが異なるクラスのサービストラフィックフロー間でリソースを共有できるようにしている（例えば、高優先順位のトラフィックに利用されていない保証予算を用いて中優先順位または低優先順位のトラフィックを配送するなど）。
【００１９】
例えば、前記クラスのサービスキューの１８が高優先順位のパケットを既にキューに入れていて、前記クラスのサービスキューの２２が中優先順位のパケットを既にキューにいれている場合、前記クラスのサービスセレクタ３０は高優先順位のパケットをキュー１８から第１のストリームセレクタ５０へ転送し、これによりユーザ１０からのパケット転送を可能にする。このストリームセレクタ５０の予算は重要ではなく、すべてのパケットが第１の利用可能なストリームセレクタ５０’を通して出て行く。
【００２０】
保証ストリームセレクタ５０’および調整ストリームセレクタ５０’’の両方がパケットロスを許容するものであるならば、キュー１８のパケットは保証ストリームセレクタ５０’を通して配送される。いずれのストリームセレクタ５０を用いてパケットを送信するかを決めるため、ストリームセレクタ５０をスキャンして転送に利用できる最初のストリームセレクタ５０を見付ける。このスキャンは、まず、保証ストリームセレクタ５０’が利用可能であるか否かを判定し、次に、調整ストリームセレクタ５０’’が利用可能であるか否かを判定する。保証ストリームセレクタ５０’が第１のパケットの後すぐに第２のパケットを出力することを許可しない場合、キュー２２のパケットは調整ストリームセレクタ５０’’を通して渡すことができる。しかし、１クラスのサービスキュー１８が高優先順位のパケットをキューに入れてなく、１クラスのサービスキュー２２が中優先順位のパケットをキューに入れていた場合、１クラスのサービスセレクタ３０は中優先順位のパケットを保証カテゴリストリームセレクタ５０’に転送する。よって、ユーザのデータトラフィック間でサービス優先順位を保存しつつ、ユーザはそのユーザによって署名される最高の予算カテゴリが許可される。
【００２１】
データパケットがストリームセレクタ５０に転送されると、ストリームセレクタ５０は、レベルセレクタ７４の命令に基づいてそのデータを送信する。ストリームセレクタ５０’、５０’’はレベル速度調節器７０を通してレベルセレクタ７４と通信する。レベル速度調節器７０は、調整カテゴリの過剰予約が実際に存在しなければ、いくらかの最小帯域幅を最善予算カテゴリのために保存する。この最小帯域幅をゼロに設定すると最善の欠乏を導く可能性があり、最終的には上位のプロトコル層（例えばＴＣＰ）でタイムアウトが生じて、接続損失が生じる。最善カテゴリに対応するストリームセレクタ５０’’’は、レベル速度調節器を介することなくレベルセレクタ７４と直接通信する。ストリームセレクタ５０は、４本の線：eligible５４’、５４’’、５４’’’（まとめて５４で示す）、high-eligible５８’、５８’’、５８’’’（まとめて５８で示す）、packet６２’、６２’’、６２’’’（まとめて６２で示す）およびtransmit６８’、６８’’、６８’’’（まとめて６８で示す）を用いてレベルセレクタ７４と通信する。レベルセレクタ７４は、３本の線：eligible８２、packet８６およびtransmit９０を用いてこのパケットをＭＡＣ層１００に送信する。一実施形態において、この転送は速度調節器７８を通して行なわれる。
【００２２】
動作時において、サービスキュー１８のクラスにおける高優先順位のパケットの存在によって、サービスセレクタ３０のクラスは、high ready線３４をストリームセレクタ５０に設定することにより転送することのできるパケットが存在することを示す。続いて、利用可能な予算が存在するならば、ストリームセレクタ５０は、high eligible線５４を設定することによりパケットを転送する準備ができたことをレベルセレクタ７４に示す。続いて、レベルセレクタ７４はeligible線８２をＭＡＣ層１００に設定する。
【００２３】
ＭＡＣ層１００は、transmit線９０を設定してパケットの転送をレベルセレクタ７４に通知する。そして、レベルセレクタ７４は、transmit線６６をストリームセレクタ５０に設定する。同様にストリームセレクタ７４は、transmit線４８をサービスセレクタ３０の階層に設定する。そして、サービスセレクタ３０の階層は、パケットをサービスキュー１８の階層から除去し、線４２を用いてこれをストリームセレクタ５０に渡し、同様に線６２を用いてこれをレベルセレクタ７４に渡す。レベルセレクタ７４は、線８６を用いてパケットをＭＡＣ層１００に渡す。
【００２４】
本発明の一実施形態による帯域幅割り当ての例を示す図２Ａを参照すると、ユーザＡ、ＢおよびＣは、保証、調整および最善の予算に対するユーザの署名を定義する個々のサービスレベル承諾（ＳＬＡ）に入る。図に示した全てのパーセンテージは、ノードの全帯域幅の相対的な部分を表している。ユーザＡは、保証予算の下ではノード帯域幅の２５％を有し、調整予算の下ではノード帯域幅の０％を有し、１の最善ウェイトを有する。ユーザＢは、保証予算の下ではノート帯域幅の２５％を有し、調整予算の下ではノード帯域幅の０％を有し、４の最善ウェイトを有する。ユーザＣは、保証予算の下ではノード帯域幅の５０％を有し、調整予算の下ではノード帯域幅の０％を有し、１の最善ウェイトを有する。すべてのユーザＡ，ＢおよびＣが、ユーザの保証帯域幅によってサポートされ得るデータよりも多くのデータを同時に転送しようと試みると、各ユーザには、ユーザのＳＬＡによる記述に従って保証帯域幅が正確に割り当てられ、ノード帯域幅は保証カテゴリトラフィックによって飽和される。その結果、最善予算セレクタを通過するトラフィックはなくなる。その結果、ユーザＡ、ＢおよびＣの間転送されるデータの割合は１：１：２になる。
【００２５】
図２Ｂを参照すると、ユーザＡがノード帯域幅の２０％で送信し、ユーザＢおよびＣがそれぞれノード帯域幅の１００％で送信する場合、ユーザＡが利用することのできない５％の余剰帯域幅は、ユーザＢおよびＣの最善署名の比率に従って割り当てられる。よって、ユーザＡ、ＢおよびＣは、それぞれ全ノード帯域幅の２０％、２９％および５１％を利用する。ユーザＢが利用する２９％は、２５％が保証予算セレクタを通して配送され、４％が最善予算セレクタを通して配送されるように分割される。ユーザＢが利用する５１％は、５０％が保証予算カテゴリセレクタを通して配送され、１％が最善予算セレクタを通して配送されるように分割される。ユーザＢは、ノード帯域幅の１００％で送信することを試みているが、ノード帯域幅の２９％しか割り当てられていないため、ユーザＢにより供給される残りの７１％のトラフィックは、バッファリングされるか、あるいは、バッファサイズによっては失われる。ユーザＢは、ユーザＢのデータの２９％より多くが高優先順位のデータであるならば、高優先順位のデータしか失われることはない。
【００２６】
上記の例では、ユーザＡ、ＢまたはＣの中で調整予算カテゴリに署名したユーザはいなかった。この例において、何らかのユーザＳＬＡにおける調整予算帯域幅の何らかの割り当ては、過剰予約のために残された非保証帯域幅が存在しないので、果てしない過剰予約を表す。
【００２７】
本発明の一実施形態による帯域幅割り当ての別の例を示す図３Ａを参照すると、ユーザＡは、保証予算用にノード帯域幅の１２．５％を有し、調整予算用にノード帯域幅の２０％を有し、１の最善ウェイトを有する。ユーザＢは、保証予算用にノード帯域幅の１２．５％を有し、調整予算用にノード帯域幅の２０％を有し、４の最善ウェイトを有する。ユーザＣは、保証予算用にノード帯域幅の２５％を有し、調整予算用にノード帯域幅の２０％を有し、１の最善ウェイトを有する。調整予算カテゴリに対する署名はノード帯域幅の６０％を表しているが、保証予算を考慮した後は５０％しか利用することができないので、調整予算カテゴリの過剰予約は１２０％である。
【００２８】
図３Ｂを参照すると、ユーザＡ、ＢおよびＣのそれぞれが全ノード帯域幅の１００％を必要とするトラフィックを提出する場合、保証予算の下で彼らにはそれぞれ１２．５％、１２．５％および２５％が割り当てられる。全ノード帯域幅のうちの残りの５０％は、調整割合２０：２０：２０に従って割り当てられ、各ユーザＡ、ＢおよびＣには、全ノード帯域幅の約１６．６７％のさらなる帯域幅が割り当てられる。その結果、最善セレクタは、まったく用いられることがなく、全ノード帯域幅は、それぞれ２９．１７％、および、４１．６７％に従って、ユーザＡ、ＢおよびＣに割り当てられる。
【００２９】
図３Ｃを参照すると、ユーザＡは何もデータを提出しないが、ユーザＢおよびＣのそれぞれが全ノード帯域幅の１００％を提出する場合、ユーザＢには、その保証予算および調整予算を通して３２．５％が割り当てられ、ユーザＣには、その保証予算および調整予算を通して４５％が割り当てられる。全ノード帯域幅の残りの２２．５％は、ユーザＢおよびＣの最善ウェイトの割合４：１にしたがって、ユーザＢとユーザＣとの間で分割される。その結果、全ノード帯域幅の５０．５％がユーザＢに割り当てられ、全ノード帯域幅の４９．５％がユーザＣに割り当てられる。
【００３０】
ユーザＢが全ノード帯域幅の４０％のみを高優先順位のパケットで提出する場合、１２．５％が保証予算セレクタを通して配送され、２０％が調整予算セレクタを通して配送され、残りは最善セレクタを通して低優先順位のパケットで配送される。
【００３１】
再び図１を参照すると、ストリームセレクタ５０のうちの１つは、パケットの利用可能性、利用可能なパケットの優先順位および各ユーザ（クライアント）のＳＬＡに従って、パケットをキュー１８、２２、２６のうちの１つからＭＡＣ層１００へ渡すことに用いられている。特に、レベルセレクタ７４は、送信することが適当なパケットを見付けるまですべてのストリームセレクタ５０を下降優先順位でスキャンする。図４は、図１のストリームセレクタをスキャンするためのイベントのシーケンス示すフロー図である。ステップ２０２において、レベルセレクタ７４は、ストリームセレクタ５０をスキャンする前に、所定の更新時間Δだけ待機する。まず、保証ストリームセレクタ５０’がパケットを送信することの適格性を判定する（ステップ２０４）。保証ストリームセレクタ５０’が適格であったならば、パケットをキュー１８、２２、２６からＭＡＣ層１００へ送信する（ステップ２０６）。その後、時間Δ後の時点でスキャンを再開する（ステップ２０２）。もし保証ストリームセレクタ５０’が送信を行うのに不適格であったならば、調整ストリームセレクタ５０’’の適格性を判定する（ステップ２０８）。保証ストリームセレクタ５０’が適格であったならば、パケットを送信し（ステップ２１０）、時間Δ後の時点でスキャンを再開する（ステップ２０２）。ここでも調整ストリームセレクタ５０’’が送信を行うのに不適格であったならば、最善セレクタ５０’’’を用いた送信の適格性を次に判定する（ステップ２１２）。同様に、最善セレクタ５０’’’が適格であったならば、パケットを送信し（ステップ２１４）、そうでなければパケットは送信せず、時間Δ後の時点でスキャンを再開する（ステップ２０２）。
【００３２】
ストリームセレクタ５０のそれぞれに対して１以上のトークンカウンタが用いられ、トークンカウンタのそれぞれが予算カテゴリに対応している。これらのトークンカウンタは、ストリームセレクタが所定のクライアントからパケットを送信することの適格性を判定するために用いられる。図５は、図１の通信回線マルチプレクサ５のためのトークンカウンタ１０４’、１０４’’、１０４’’’、１０４’’’’（まとめて１０４で示す）を示す概略図である。各トークンカウンタ１０４はトークンカウンタ値を有し、トークンカウンタ値は、システムクロックとデータパケットの送信との両方に応答して周期的に加算または除去される。
【００３３】
各更新時刻において、トークンカウンタ値は、所定の更新値に従って各クライアントおよび各予算に対して増加すなわち記入される。各トークンカウンタ１０４の更新値は通常、関連するクライアントの予算カテゴリに対する割り当てに応じて決まる。例えば、第１のクライアントが第２のクライアントの保証割合の２倍に署名した場合、第１のクライアントの保証トークンカウンタ１０４は通常、毎回の更新の際に第２のクライアントの保証トークンカウンタ１０４の２倍の割合で記入される。トークンカウンタ値が増加して所定値以上になると、そのクライアントのキュー１８、２２，２６にあるパケットは、対応する予算カテゴリに対して送信を行うことが適格となる。トークンカウンタ値が増加し続けて第２の所定値に達すると、トークンカウンタ値を変更する際のトークンカウンタ値のさらなる記入は無効にされる。従って、トークンカウンタ１０４が第２の所定値に達すると、データパケットが送信されるまでトークンカウンタはその値のままになる。一実施形態において、第１の所定値は第２の所定値と等しい。パケットが送信された後、トークンカウンタ値はそのデータパケットの長さに比例した量だけ減少させられる。
【００３４】
調整予算および最善予算は固定帯域幅の割り当てを提供しないので、これらの予算カテゴリの適格性の判定には、アダプティブなトークンカウンタ１０４’’’、１０４’’’’として実施される公正な方法が用いられる。固定帯域幅に対応する保証予算、従って非アダプティブなトークンカウンタが必要とされる。なぜなら、保証ストリームセレクタ５０’および調整ストリームカウンタ５０’’が適格ではなく、アダプティブトークンカウンタ１０４’’’’が最善予算に対して用いられたときにのみ、最善ストリームセレクタ５０’’を用いてパケットが送信されるからである。
【００３５】
所定値１０８はすべてのバケット１０４と共に用いられる。所定値１０８は、それに関連する予算カテゴリによって異なる場合がある。トークンカウンタ値はパケットが対応するセレクタ５０を通して送信されたときに減少されるので、前のパケットが送信され終わった直後にキュー１８，２２，２６に到着するパケットは、十分な時間が経過してトークンカウンタ値が再び所定値１０８に達するまで同じセレクタ５０を通して送信することができない。この遅延を回避するため、保証トークンカウンタ１０４’は高優先順位のパケットのために予約された第２の所定値１１２を有する。この高優先順位しきい値１１２は、所定値よりも低い値に設定される。
【００３６】
表１は、図５に示した実施例のトークンカウンタ１０４の送信適格性を判定するために使用されるビットインジケータを一覧にしている。ビットインジケータPktPendingおよびPktHiPendingは、パケットおよび高優先順位のパケットをクライアントのキュー２２，２６および高優先順位のキュー１８にそれぞれ入れることができるか否かを示すものである。G_RegulatorEligibleおよびR_RegulatorEligibleは、保証トークンカウンタ１０４’および調整トークンカウンタ１０４’’が所定値１０８と一致するか否かまたは超えているか否かをそれぞれ示すものである。同様に、R_FairnessEligibleおよびB_FairnessEligibleは、調整アダプティブトークンカウンタ１０４’’’および最善アダプティブトークンカウンタ１０４’’’’が所定値１０８に達しているか否かをそれぞれ示すものである。G_RegulatorHiEligibleは、保証トークンカウンタ値が第２の所定値１１２を超えているか否かを示すものである。G_Eligible、R_EligibleおよびB_Eligibleは、他のビットインジケータとの論理的関係によって定義され、保証セレクタ、調整セレクタおよび最善セレクタ５０’、５０’’、５０’’’がデータパケットを送信するのに適格であるか否かをそれぞれ示すものである。
【表１】
0004115703.tif 000002
【００３７】
図６は、クライアントが保証予算を用いてデータパケットおよび高優先順位のパケットを送信することの適格性を判定するために使用される一連のステップの実施例（図５および表１による実施例）を表すフロー図である。これらの適格性は、G_RegulatorEligibleおよびG_RegulatorHiEligibleにそれぞれ得られる。ステップ３０２において、クライアントの保証トークンカウンタが、そのクライアントの保証割合トークン解像度を加算することにより記入される。保証割合トークン解像度は各クライアントについて異なり、通常はクライアントの保証帯域幅割り当てに応じて決められる。保証トークンカウンタ値は、所定値１０８よりも大きい場合、所定値に設定する（ステップ３０４）。G_RegulatorEligibleおよびG_RegulatorHiEligibleを論理FALSEに設定する（ステップ３０６）。保証トークンカウンタ値が第２の所定値１１２を超えている場合、G_RegulatorHiEligibleを論理TRUEに設定する（ステップ３０８）。保証トークンカウンタ値が所定値１０８以上である場合、G_RegulatorEligibleの値を論理TRUEに設定する（ステップ３１０）。現時点でスキャンされるべき１以上のクライアントが残っているならば、ステップ３０２に戻り、保証予算に対する適格性の判定を継続する。クライアントは、次の２つの状態のうちのいずれかを満たすならば、保証予算を用いて送信することが適格とされる：１）G_RegulatorEligibleがTRUEで、かつ、クライアントのキュー１８、２２、２６のうちの１つに入れることのできるパケットが存在する場合、２）G_RegulatorEligibleがTRUEで、かつ、高優先順位のキュー１８に入れることのできる高優先順位のパケットが存在する場合。
【００３８】
調整予算カテゴリを用いて送信することの適格性は、調整トークンカウンタ１０４’’と調整アダプティブトークンカウンタ１０４’’’との両方を検査することにより判定される。調整トークンカウンタ１０４’’が記入される速度は、クライアントのＳＬＡに定義されたクライアントの調整予算により異なる。アダプティブトークンカウンタ１０４’’’が記入される速度は、調整予算の使用を試みるトラフィックに応じて決まる。調整予算カテゴリは、クライアントが利用可能な調整帯域幅を余分に確保することを意図するものであるから、調整予算カテゴリに対して大量のトラフィックを生成する複数のクライアントは、割り当てられた帯域幅の合計を超える帯域幅が必要になる可能性がある。その結果、データパケットが転送を待っている間にバッファが一杯になる可能性があり、後続のデータパケットが失われることになる。調整予算カテゴリに基づいてユーザに対して公平を保証するため、アダプティブトークンカウンタ１０４’’’、１０４’’’’の速度が記入される（即ちアダプティブ速度が減少される）。こうした環境下では、Stressと呼ばれるパラメタを用いてバックログまたはユーザ負荷を特徴付ける。一実施形態では、Stressは、調整予算を通して送信することが適格であるクライアントの数として定義される。過剰予約が問題にならないこと（例えばStressがゼロに等しい）をStress値が示す場合、アダプティブ速度はクライアントの調整速度以上である。
【００３９】
調整トークンカウンタ１０４’’、１０４’’’は、第２の所定値１１２との比較を行わないことを除き、保証トークンカウンタ１０４’について上述したのと同様の一連のステップを使用して検査される（即ち、ステップ３０８に対応する同等のステップは存在しない）。調整トークンカウンタ１０４’’が所定値１０８よりも小さい場合、R_RegulatorEligibleは論理TRUEに設定される。同様に、調整アダプティブトークンカウンタ１０４’’’が所定値１０８以上である場合、R_RateFairnessEligibleは論理TRUEに設定される。クライアントは、次の３つの条件をすべて満たすならば、その調整予算を用いて送信することが適格であるとされる：（１）R_RegularEligibleがTRUE、（２）R_RateFairnessEligibleがTRUE、（３）PktPendingがTRUEまたはPktHiPendingがTRUE。
【００４０】
最善予算カテゴリの適格性は、最善アダプティブトークンカウンタ１０４’’’’を検査することにより判定される。このトークンカウンタ１０４’’’’は、調整アダプティブカウンタ１０４’’’について上述したステップを用いて検査される。最善アダプティブトークンカウンタ１０４’’’’の増加速度は、Stressを増加させることに応じて減少される。調整予算のStressパラメタと最善予算のStressパラメタは、別々に定義することができる。一実施形態において、調整予算に用いられるStressは調整予算について適格なクライアントの数として定義され、最善予算に用いられるStressは最善予算を通して送信することが適格であるクライアントの数として定義される。最善アダプティブトークンカウンタ１０４’’’’が所定値１０８以上であるならば、B_RateFairnessEligibleは論理TRUEに設定される。クライアントは、B_RateFairnessEligibleがTRUEであり、かつ、そのクライアントのキュー１８、２２、２６のうちの１つに入れることのできるパケットが存在するならば、その最善予算を用いて送信することが適格であるとされる。
【００４１】
例として、表２は３つのクライアントに対するＳＬＡ割り当てを定義している。クライアントＡは、１ミリ秒当たり１０００オクテット（即ち１０００  ８ビットバイト）の保証速度に署名している。クライアントＢは、１ミリ秒当たり２０００オクテットの保証速度および１ミリ秒当たり５０００オクテットの調整速度に署名している。クライアントＣは１ミリ秒当たり３０００オクテットの保証速度、１ミリ秒当たり９０００オクテットの調整速度および１の最善ウェイトに署名している。クライアントＡおよびクライアントＢはいずれも最善割り当てには署名していない。この例の場合、すべてのクライアントが１０００オクテット長のパケットを送信し、最大パケットは２０００オクテット長である。
【表２】
0004115703.tif 000003
【００４２】
表３は、表２に定義されたクライアントのパケット転送の例を示す時刻表である。Ａ（Ｇ）、Ｂ（Ｇ）およびＣ（Ｇ）の見出しをつけた列は、クライアントＡ、ＢおよびＣに対する保証トークンカウンタ値にそれぞれ対応している。Ｂ（Ｒ）、Ｂ（Ａ）、Ｃ（Ｒ）およびＣ（Ａ）と見出しをつけた列は、クライアントＢおよびＣのそれぞれに対する調整トークンカウンタ値およびアダプティブトークンカウンタ値にそれぞれ対応している。Stressは、調整予算および最善予算の下で送信することが適格なクライアントの数を示している。この例の場合、所定値は０であり、第２の所定値は−２０００である。
【表３】
0004115703.tif 000004
【００４３】
この例の場合、動作速度は１ミリ秒当たり１００イベント（動作）である。パケットが保証ストリームセレクタ５０を通して送信された後、対応する保証トークンカウンタは、そのパケット×長さ解像度だけ減少させられる。Ａには１０００オクテット／ｍｓが割り当てられるので、保証トークンカウンタ値は、１ミリ秒につき１回、所定値に達するはずである。クライアントＡの速度トークン解像度を１０に設定して、このトークンカウンタ増加速度を達成している。従って、Ａのトークンカウンタ値は、送信後に１０００だけ減らされ、１００回の動作（１．００ｍｓ）後に元の値に戻る。クライアントＢおよびＣのトークン速度解像度も、同様に判定される。クライアントＡ、ＢおよびＣについてのトークン速度解像度が表４に一覧されている。−２０００の高優先順位しきい値（即ち第２の所定値）は、保証トークンカウンタに対してのみ設定され、２０００オクテットの最大パケットサイズに基づいている。
【表４】
0004115703.tif 000005
【００４４】
この例の場合、時刻＝０の時点で、３つのクライアントすべてはアクティブかつ未処理（飽和）であり、クライアントＡおよびＢが高優先順位のパケットのみを有し、クライアントＣが低優先順位のパケットのみを有する。ノード速度は１００００オクテット／ｍｓであり、従ってパケットは約０．１ｍｓに１回送信される。クライアントＡおよびＢの両方が高優先順位のパケットを送信する可能性があるが、保証セレクタ５０は、これらのクライアントのうちの一方を選択して直列方式（ラウンドロビン方式）で配送することしかできない。各送信の後、対応する保証トークンカウンタが１０００だけ減少させられる。従って、クライアントＡがパケットを送信した後、０．１ｍｓ後にクライアントＢはパケットを送信する。この交互の送信シーケンスは、クライアントＡおよびＢの保証トークンカウンタ値が−２０００より大きい限り継続される。
【００４５】
時刻＝０．６ｍｓの時点で、クライアントＡおよびＢは、いずれも高優先順位しきい値より大きい保証トークンカウンタ値を持たない。クライアントＣは、その保証予算を用いて低優先順位のパケットを最後に送信することができる。時刻＝０．７ｍｓの時点で、クライアントＢは−１８００の保証トークンカウンタ値を有し、高優先順位のパケットを送信できるようになる。
【００４６】
時刻＝０．８ｍｓの時点で、クライアントＡ、ＢおよびＣは、自身の保証予算を使い果たし、従って、ＢおよびＣの調整カテゴリが次に送信するクライアントを決める。ノードが過剰予約されている（即ちStressがゼロより大きい）ので、クライアントＢおよびＣは、パケットを自身が要求した速度で供給することができなくなる。通信回線マルチプレクサ５は、その速度をアダプティブトークンカウンタに記入された速度（即ちアダプティブ動作速度）に低下させることにより応答する。パケットは調整予算の下でクライアントＢから送信され、Ｂはもはや調整予算の下で適格ではないので、Stressが１まで減少される。時刻０．８５ｍｓの時点で、クライアントＢの調整トークンカウンタ値は、速度の増加の差に起因して、調整アダプティブトークンカウンタ値よりも高速に増加している。
【００４７】
時刻＝０．９ｍｓの時点で、クライアントＣは、他のすべてのクライアント予算がそれらのしきい値よりも小さいので、調整予算を通してパケットを送信する。時刻＝１．０ｍｓの時点で、クライアントＣは、対応するトークンカウンタ値がゼロしきい値まで回復しているので、保証予算を通してパケットを送信する。時刻表にはさらなる時間が含まれ、中継線マルチプレクサ５の動作原理をさらに例示している。
【００４８】
ここまで特定の好ましい実施形態を参照しつつ本発明を詳しく提示および説明してきたが、当業者には、付記した特許請求の範囲に規定される本発明の思想および範囲から外れることなく形態および細部に様々な変更を施せることが分かるはずである。
【図面の簡単な説明】
【図１】  本発明の一実施形態に従って通信路上でパケットを多重化するシステムの高レベルブロック図である。
【図２Ａ〜２Ｂ】  本発明の一実施形態に従って帯域幅を複数のユーザに割り当てる例についての予算カテゴリ署名およびノード帯域幅割り当てをそれぞれ示す図である。
【図３Ａ〜３Ｃ】  本発明の一実施形態に従って帯域幅を複数のユーザに割り当てる別の例についての予算カテゴリ署名およびノード帯域幅割り当てを示す図である。
【図４】  本発明の一実施形態に従ってストリームセレクタをスキャンするためのイベントのシーケンスを示すフロー図である。
【図５】  本発明の一実施形態によるトークンカウンタを示す図である。
【図６】  本発明の一実施形態に従ってクライアント送信適格性を判定するためのステップのシーケンスを示すフロー図である。
【図１】
0004115703.tif 000006
【図２Ａ】
0004115703.tif 000007
【図２Ｂ】
0004115703.tif 000008
【図３Ａ】
0004115703.tif 000009
【図３Ｂ】
0004115703.tif 000010
【図３Ｃ】
0004115703.tif 000011
【図４】
0004115703.tif 000012
【図５】
0004115703.tif 000013
【図６】
0004115703.tif 000014