(57)【特許請求の範囲】
【請求項１】
データ網へのアクセスを競合するトラヒックソースから発出する情報パケットに、競合サイクル内で帯域幅を割り当てる方法であって、
前記トラヒックソースから情報パケットを受信し、前記情報パケットを１以上のソース待ち行列に格納するステップからなり、前記格納された情報パケットの各々は、それぞれ予め定義されたサービス品質パラメータを有し、さらに、
前記ソース待ち行列のうちの１つに格納されそして予め定義された値以上のサービス品質パラメータを有する情報パケットの全てを、サービス保証待ち行列へ割り当てるステップと、
前記サービス保証待ち行列に割り当てられたパケットに必要な保証帯域幅の全てが前記サイクルの間で充足するまで、前記サービス保証待ち行列に割り当てられた情報パケットに前記データ網の帯域幅を割り当てるステップと、
サービス保証待ち行列の全てのサービス要件を満たしたときには、所定の基準に従って、前記ソース待ち行列に格納された情報パケットに前記帯域幅を割り当てるステップとからなることを特徴とする方法。
【請求項２】
請求項１に記載の方法であって、前記サービス保証待ち行列が空であるときに、前記サービス要件が満たされることを特徴とする方法。
【請求項３】
請求項１に記載の方法であって、ある待ち時間要件を有する全てのパケットが送信されたときに、前記サービス要求が満たされることを特徴とする方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明はデータ網の性能を増加させるためのシステム、より詳細には、データ網内での遅延を最小にする一方で、サービス品質保証を満足させるために必要とされる帯域幅を（確保）配達するための方法およびシステムに関する。
【０００２】
【従来の技術】
現存の回路交換網は、固定および保証された帯域幅を、要求ソースに、ある接続の継続期間を通じて、その接続を通じて流れるトラヒックの量と無関係に割り当てる。この理由から、回路交換網では本質的に帯域幅が無駄に消費されることが知られている。狭帯域パケット網は、これとは対象的に、帯域幅を要求ソースに、必要に応じて効率的に割り当てるが、ただし、典型的には、所定の時間期間内に、サービス品質（ＱｏＳ）パラメータによって示されるある量の帯域幅を配達することを完全に保証することはない。
【０００３】
この制約のために、帯域幅保証配達に対する厳しい要件を持つことが知られているリアルタイムトラヒックに対して狭帯域幅パケット網を使用することが阻止されている。帯域幅保証要求を満足し、かつ、網内での遅延を最小にすることに対する努力は、今日に至まで、網設計者の注意をあまり引き付けなかった。これは、異なるアプリケーション（音声あるいはデータ）に対しては、各タイプに対して異なる最適化基準を持つ別個の網を設計する方が得策であると考えられてきたためである。しかしながら、一つの共通なファブリック上に音声、データおよびビデオアプリケーションをサポートする高速パケットデータ網の急速な展開のために、要求ソースに保証帯域幅を配達し、同時に、網遅延を最小にする問題が、今後、非常に重要になると期待される。
【０００４】
【発明が解決しようとする課題】
この問題の一面を解決する努力の中で、幾らかの網設計者は、ＱｏＳを満足させ、トラヒックをトラヒックが受信された順番ではなく、対応するアプリケーション要件に基づいてトラヒックをルートする優先付きパケット脱落（priority and packet-dropping）スキームを設計している。残念ながら、これらスキームは、低優先度のソースあるいはアプリケーションを犠牲に動作し、しばしば、資源の割り当てが、低優先度のソースに効率的に割り当てることが可能な未使用の帯域幅を十分に考慮することなしに、でたらめに行なわれる結果となる。
【０００５】
リアルタイムトラヒックフローを定義する特性がその遅延に対する敏感さであるという認識から、高速パケット網の別の幾らかの設計者は、パケットの喪失を低減し、サービス品質の劣化を最小にするために、過剰な輸送遅延を最小にする目的でキューイングおよびスケジューリングスキームを考案している。例えば、高速パケット網に対する公平キューイングスキームが考案されているが、これは、あるセッションの継続期間を通じてエンド・ツウ・エンド遅延限界を指定および保証することによってリアルタイムトラヒックをサポートする。
【０００６】
これは、新たなトラヒックを受け入れることが、現存のフローに対する遅延限界に影響を与えるべきでないことを含蓄する。この概念は、当分野において、トラヒックフローに対する“分離（isolation ）”要件として知られている。公平キューイングスキームの一つの欠点は、システム帯域幅のフロー間の共有が低減され、このためにコスト高となることである。より具体的には、未使用のシステム帯域幅が共有されないために、システム遅延性能が最適以下となる。従って、従来の技術には、要求ソースがそれらの要求するサービス品質を確保でき、同時に、最適なシステム遅延性能を達成する問題が残される。
【０００７】
【課題を解決するための手段】
本発明は、帯域幅割り当てシステムに関する。このシステムにおいては、共有処理ファブリックへの、このファブリックへのアクセスに対して競合する複数の異なるソースからのトラヒックフローのアクセスが、第一に、各競合するフローに対応する個別の保証帯域幅要件、そして、第二に、全体としてのシステム基準、例えば、複数のトラヒックフロー内のパケットあるいはセルの到着時間、あるいは配達期日、に基づいて決定される。
【０００８】
本発明の原理の一つの実現においては、（あるソース、例えば、ある帯域幅を要求する装置あるいはサブネットワークと対応する）あるフローからのパケットあるいはセルは、別個のバッファ内にキューイングされ、ここで、処理ファブリックへのアクセスを待つ。各タイムスロットにおいて、任意のフローに対するバッファの先頭の所のセルあるいはパケットが、処理ファブリックにアクセスする権利を持つ。このアクセス方針は、セルあるいはパケットに対するサービスの順番を決定するために、例えば、別個のモジュールとして実現される二つのフェーズにて動作する。
【０００９】
第一のフェーズにおいては、要求された帯域幅を各フローに配達する（割り当てる）することを保証するために、処理されなければならないセルあるいはパケットが識別される。これらセルあるいはパケットは、“サービス保証待ち行列（ＧＳＱ）”と称される待ち行列内におかれ、その後、一時に一つづつ、処理ファブリックにアクセスすることを許される。
【００１０】
あるタイムスロットにおいてＧＳＱ（サービス保証待ち行列）が空である場合は、第二のフェーズが起動される。この第二のフェーズにおいては、セルあるいはパケットは、処理ファブリックへのアクセスを、あるあらかじめ定められた基準、例えば、ファーストカムファーストサーブ（ＦＣＦＳ）ベース、に従って得る。例えば、全てのフローの中で最も古いセルあるいはパケットが処理される。これは、各フロー内の回線の先頭の所のセルのシステムへの到着時刻を比較することによって達成される。長所として、このフェーズにおいてセルをＦＣＦＳベースにて処理することによって、その特定のタイムスロットに対して最適なシステム遅延性能が達成される。別の方法として、あるタイムスロットにおいてサービス保証待ち行列が空の場合、最も接近した期日を持つセルあるいはパケットが（セルあるいはパケットの配達期日に基づいて）、共有処理ファブリックにアクセスすることを許されるようにすることも可能である。
【００１１】
【実施例】
図１は本発明の原理を実現するように構成されたコントローラのブロック図を示す。図１に示されるコントローラ１００は入力インタフェース１０５と信号処理装置１１０を含むモジュール型の要素から構成される。
【００１２】
データはコントローラ１００に処理ファブリック１５０へのアクセスを得るためのトラヒックソース１０１−１０４のための入り口点である入力インタフェース１０５を介して入る。トラヒックソース１０１−１０４は、データ端末装置のような処理装置であることも、あるいはデータ通信装置のような通信装置であることも考えられる。これら装置はデジタル入力信号を入力インタフェース１０５にあるあらかじめ定められた物理およびリンクプロトコルに従って送信する。別の構成として、トラヒックソース１０１−１０４は、処理ファブリック１５０によって表される共有バックボーン網へのアクセスに対して競合するサブ網であるこも考えられる。後者の場合は、トラヒックソース１０１−１０４は、異なるトラヒックフローからのデジタル信号を入力インタフェース１０５に終端するアクセスキャリア設備１６１−１６４上に多重化する集信装置であり得る。
【００１３】
トラヒックソース１０１、１０２、１０３、１０４が、デジタル信号を、例えば、セルあるいはグループのセルの形式にて、コントローラ１００に送信すると、コントローラ１００は、受信されたセルを一時的にバッファ１０１−１０４内に格納する。これらバッファは、各トラヒックソースからのトラヒックフロー中のセルに対する待ち行列メモリデバイスとして動作し、各トラヒックソースからのセルは、これらが処理ファブリック１５０へのアクセスを待つあいだ、別個のバッファ内で順番を待たされる。別の構成として、バッファ１０６−１０９をトラヒックソース１０１−１０４内に用意することもできる。バッファ１０６−１０９内に実現されるキューイング方式は、本発明を構成するものではない。重要なことは、各タイムスロット内において、各トラヒックソースと対応する各バッファ待ち行列の先頭のセルのみが処理ファブリック１５０へのアクセスに対する競合権をもつという事実である。各トラヒックソースｉとカウンタｒｉとが対応し、カウンタの値は、例えば、そのトラヒックフローに対するＱｏＳパラメータに基づいて定められる。
【００１４】
入力インタフェース１０５は、さらに、プロセッサ１３６を含むが、これは、クロック１３５のタイミング信号を使用して、各バッファ内のセルに対する競合サイクルの同期をとる。つまり、あるバッファ内のあるセルが競合する状態になると、プロセッサ１３６は、この競合するセルにクロック１３５を使用してタイムスタンプを付加する。ある競合サイクルの開始において、処理ファブリック１５０に伝送されるべき新たなセルをラインの先頭の所に持つ各バッファは、シグナリングリンク１４１−１４４の一つを介して信号処理装置１１０に競合コードを送信する。この競合コードは、例えば、そのセルに対応するQuality-of-Service（ＱｏＳ）パラメータ、そのセルに対するトラヒックフローと対応するカウンタの値、およびそのセルが競合するようになった、あるいは入力インタフェース１０５から受信された時間を示す。
【００１５】
図１にはさらに信号処理装置１１０が含まれるが、これは、帯域幅保証待ち行列（Guaranteed Bandwidth Queuing）モジュール１１１とファーストカム・ファーストサーブ（First-Come-First-Serve、ＦＣＦＳ）待ち行列モジュール１１２を含む。帯域幅保証待ち行列モジュール１１１の心臓部にはマイクロプロセッサ１１４が存在するが、これは、処理ファブリック１５０へのアクセスに対して競合するトラヒックに対する第一のゲートポストとして機能する。より詳細には、マイクロプロセッサ１１４は、メモリ１１３内に格納されているプログラムインストラクションを実行することによって、競合するトラヒックフローに対するＱｏＳパラメータへのアクセス、各競合トラヒックフローによって要求される保証帯域幅の決定、処理ファブリック１５０の所に利用できる帯域幅の調査、および、必要とされる場合は、帯域幅使用カウンタの減分を遂行する。発明のこの点に関しては、後に、詳細に説明される。
【００１６】
マイクロプロセッサ１４４が現在のタイムスロットに対して全ての競合するトラヒックフローに対して要求される全ての保証帯域幅を割り当ててもさらに処理ファブリック１５０上に余分な帯域幅が利用できることを決定すると、マイクロプロセッサ１１４は、この事実をFCFS待ち行列モジュール１１２にシグナリングリンク１５１を介して送信される信号を通じて伝える。ＦＣＦＳ待ち行列モジュール１１２のマイクロプロセッサ１１６は、メモリ１１５内に格納されているプログラムインストラクションを実行する。これらインストラクションには、例えば、ある競合トラヒックフロー内のセルの年令あるいは配達期日に関してアクセスするための手段を含む。後に詳細に説明されるように、マイクロプロセッサ１１６は、各競合トラヒックフローの“競合年令（contending age）”を分析することによって、処理ファブリック１５０上に余分な容量が利用できる場合に、競合トラヒックフローのどれが最初に処理ファブリック１５０へのアクセスを得るべきかを決定する。待ち行列モジュール１１２に対してファーストカム・ファースサーブ（ＦＣＦＳ）スケジューリング構成が示されたが、この代わりに、従来の技術による他の構成、例えば、Hierarchical Round Robin（ＨＲＲ）構成、Weighted Round Robin（ＷＲＲ）構成などを使用することもできる点を注意しておくべきである。
【００１７】
要約すると、処理ファブリック１５０上に余剰の容量が存在する場合、信号処理装置１１０は、コントローラ１００が、ＦＣＦＳ待ち行列モジュール１１２の機能を使用して、例えば、先入れ先出し待ち行列管理アルゴリズムを実現することを許す。全ての時間において、例えば、帯域幅が希少な場合であっても、信号処理装置１１０は、コントローラ１１０が、帯域幅保証待ち行列モジュール１１１の機能を使用して保証された要求帯域幅を配達するために、トラヒックフローを分離することを可能にする。
【００１８】
あるトラヒックフロー内のあるセルが信号処理装置１１０によってある競合サイクルあるいはタイムスロットに対する“勝者”であるものと決定されると、信号処理装置１１０は、入力インタフェース１０５に監督信号を送信する。この信号は、入力インタフェースに、そのバッファ１０６−１０９の一つから勝者セルを取り出して、これを信号バス１３１−１３４の一つおよびシステムバス１３０を介して処理ファブリック１５０に伝送するように指示する。より具体的には、信号処理装置１１０は、プロセッサ１３６に、勝者セルを処理ファブリック１５０に伝送するためにマイクロプロセッサ１１４と１１６によって選択されたバッファから処理ファブリック１５０に伸びるデータ経路を確立することを指令する監督信号を送信する。処理ファブリック１５０は、出力リンク、プロセッサ、バックボーン網、あるいは、例えば、非同期転送モード（ＡＴＭ）プロトコル標準に準拠する通信交換機であり得る。
【００１９】
図２は帯域幅保証待ち行列モジュールのマイクロプロセッサ１１４によって本発明の帯域幅保証機能を実現するために実行される一例としてのプログラムインストラクションの流れ図を示す。各タイムスロットの開始時において、信号処理装置１１０内のマイクロプロセッサプ１１４は、あるトラヒックソースに対して選択されたバッファ内のトラヒックソースカウンタを、ステップ２０１に示されるように、そのトラヒックソースカウンタが０以下であるか調べるために分析する。このステップは各トラヒックソースに対して同時的に遂行することができる。ステップ２０１において、そのカウンタが０以下であると決定された場合は、マイクロプロセッサ１１４は、ステップ２０３において、その選択されたバッファ内にセルが待たされているか否か評価する。待たされている場合は、マイクロプロセッサ１１４は、ステップ２０４において、その選択されたバッファ内の待ち行列内の次のセルをすぐにサービスされるべきであるとマークし、適当な監督信号をプロセッサ１３６に送信する
。
【００２０】
別の方法として、ステップ２０４において、マイクロプロセッサ１１４は、セルを、その後処理ファブリック１５０に伝送するために、メモリ１１３内に（選択されたバッファ内の待ち行列の先頭の所に）待たせることも可能である。この代替実施例においては、メモリ１１３は、競合セルがすぐにサービスされるべきであるとマークされる場合に実現される論理的なサービス保証待ち行列（Guaranteed Service Queue）とは対照的に、物理的なサービス保証待ち行列（ＧＳＱ）となる。選択された実現（マーキングあるいはキューイング）とは無関係に、セルがマークあるいはキューイングされるたびに、ＧＳＱカウンタ（サービス保証待ち行列カウンタ）が増分される。
【００２１】
その後、マイクロプロセッサ１１４は、ステップ２０５において、トラヒックソースカウンタを１．０にリセットし、そのトラヒックフローあるいはトラヒックソースに対する帯域幅使用カウンタを増分する。これは、コントローラ１００のオペレータがある時間期間を通じてあるフローあるいはトラヒックソースからのセルが何個処理されたかを調べることを可能にし、こうして、課金メカニズム、および各トラヒックソースに対する帯域幅保証を検証するための手段を提供する。
【００２２】
長所として、本発明の原理を具現する設計は、トラヒックソースカウンタｉが１．０にリセットされるたびに、ｌ／ｒｉスロット内においてトラヒックソースカウンタｉの値が０．０あるいはそれ以下に達し、フローｉに対するバッファ内にキューイングする次のセルが、即時に、すぐにサービスされるようにマークされることを保証する。結果として、フローｉは、それが要求する帯域幅を保証される。本発明の一つの実際の実現においては、安定なサービス政策を確保するために、全てのフローに対するｒｉが、それらの総和が１．０以下となるように選択される。このｒｉを考慮することによって、コントローラ１００は、また、新たなフローを受け入れるべきか否かを迅速に決定することができる。
【００２３】
あるトラヒックソースと対応するバッファ内のトラヒックソースカウンタｉが０以下でない場合は、トラヒックソースカウンタは、ステップ２０２に示されるように、“トラヒックソースカウンタレートｒｉ”と称される固定された値だけ減分される。この場合は、選択されたバッファ内に待たされているセルは、ステップ２０６に示されるように、次のタイムスロットまで待たなければならない。このｒｉの値は、フローｉによって要求される保証帯域幅に基づいて計算され、フローｉに割り当てられるべき処理ファブリック１５０の割合に等しい。例えば、フローｉが処理ファブリック１５０の容量の十分の一の保証帯域を要求する場合は、ｒｉに対して使用される値は０．１である。一例として、処理ファブリック１５０が１５５Mb/sのバスを持つ非同期転送モード（ＡＴＭ）交換機ファブリックである場合は、典型的なサービスに対するトラヒックソースカウンタレートｒｉは、６Mb/s MPEG-2娯楽ビデオに対しては０．０４、３８４kb/s   ＣＤ品質音響に対しては０．００２、そして１００kb/sの最小スループットを要求するファイル転送セッションに対しては０．００６であると推定される。
【００２４】
図３は図１の信号処理装置１１０のプロセッサによって本発明の原理を実現するために実行される一例としてのプログラムインストラクションの流れ図である。本発明によって考慮されるプロセスは、ステップ３０１において、マイクロプロセッサ１１４が、新たなバッファｊを、そのバッファが現在のタイムスロット内に伝送されるべきセルを含むか否かを判断するために選択するときに開始される。ステップ３０２において、バッファｊが空である（つまり、その中にセルが待たされていない）ことが決定された場合は、マイクロプロセッサ１１４は、ステップ３０３において、選択されるべき残りのバッファが存在するか否か評価する。
【００２５】
存在する場合は、ステップ３０１および３０２に示されるように、新たなバッファｊが選択され、その内容が待たされたセルが存在するか調べるために分析される。ステップ３０２に示されるように、選択されたバッファ内に一つあるいはそれ以上のセルが待たされている場合は、ステップ３０４において、その選択されたバッファ内のトラヒックフローに対応する選択されたバッファカウンタ内の待ち行列の先頭の所のセルが、そのセルがすぐにサービスされるべきであるとマークされているか（図２参照）調べるために分析される。すぐにサービスされるべきであるとマークされている場合は、ステップ３０５において、マイクロプロセッサ１１４は、プロセッサ１３６に、処理ファブリック１５０への伝送のために選択されたバッファに対する待ち行列の先頭の所のセルを取り出すことを指令する信号を送る。
【００２６】
ステップ３０４において、その待ち行列の先頭の所のセルがすぐにサービスされるべきであるとマークされてないことが決定された場合は、マイクロプロセッサ１１４は、ステップ３０６において、ＧＳＱカウンタが０以上であるか照会する。０以上である場合は、選択されたバッファ内の待ち行列の先頭の所のセルは、ステップ３０８に示されるように、処理ファブリック１５０へのアクセスに対する競合のために次のタイムスロットまで待たなければならない。この場合、上に説明されたように（図２のステップ２０２）、そのバッファに対するトラヒックフローに対するトラヒックソースカウンタがトラヒックソースカウンタレートｒｉだけ減分される。ＧＳＱカウンタが、ステップ３０６において０でないことが決定された場合は、マイクロプロセッサ１１６は、ステップ３０７において、選択されたバッファ内のその待ち行列の先頭の所のセルが全てのバッファ内の全てのセルの中で最も古いセルであるか否か評価する。最も古い場合は、マイクロプロセッサ１１６は、プロセッサ１３６に、選択されたバッファから処理ファブリック１５０への伝送のためにその待ち行列の先頭の所のセルを取り出すことを指令する信号を送信する。最も古いセルでない場合は、選択されたバッファ内の待ち行列の先頭の所のセルは、ステップ３０８に示されるように、処理ファブリック１５０へのアクセスに対する競合のために次のタイムスロットまで待たなければならない。
【００２７】
好ましくは、従来の技術によるパケット脱落、および優先スキームが、本発明の帯域幅保証機能との関連で実現される。
【図面の簡単な説明】
【図１】図１は本発明の原理を実現するように構成された装置のブロック図を示す。
【図２】本発明の原理を実現するために図１の装置のプロセッサ内で実行されるプログラムインストラクションの流れ図を示す。
【図３】本発明の原理を実現するために図１の装置のプロセッサ内で実行されるプログラムインストラクションの流れ図を示す。
【図１】
0004354711.tif 000002
【図２】
0004354711.tif 000003
【図３】
0004354711.tif 000004