(57)【要約】  転送可能なクレジット値システムを使用することにより、それぞれのチャネルが最小帯域幅、最大帯域幅、及び定義されたパケット間遅延範囲内に抑制されるように、到来チャネル（１００〜１０９）のために送出チャネル（１２０）へのアクセスを仲裁するパケットスイッチングシステムにおける方法であって、この方法は、それぞれのチャネルのチャネル値と、マスタ値と、送出チャネル（１２０）を通じてパケットを伝送するべく許容される１つの到来チャネル（１００）を選択する段階と、到来チャネル（１００〜１０９）の１つから送出チャネル（１２０）への伝送が許容された際に、そのチャネルのクレジットを変化させる段階と、マスタ値における対応する変化を実現する段階と、を含んでいる。チャネルは、指定された限度内のチャネル値を有している場合に、パケットを伝送する資格を有することができる。チャネル値は、指定された限度をマスタ値が超過した場合に、リセットされる。
2005510957.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２つの到来チャネルと１つの送出チャネルを含むパケットスイッチング構成であって、
それぞれの到来チャネルごとにクレジット値を保存する第１手段と、
マスタ値を保存する第２手段と、
前記送出チャネルを通じてパケットを伝送するべく許容される１つの到来チャネルの選択を実現するべく適合された第３手段と、
前記到来チャネルの中の１つから前記送出チャネルへの伝送が許容された際に、そのチャネルの前記クレジット値における変化と前記マスタ値における対応する変化を実現するべく適合された第４手段と、
を有するパケットスイッチング構成。
【請求項２】
前記値のそれぞれにおける前記変化は、等しくなることを更なる特徴とする請求項１記載のパケットスイッチング構成。
【請求項３】
それぞれの到来チャネルに対して、第１の選択された値限度が割り当てられることを更なる特徴とし、前記第３手段は、そのチャネルの前記第１値限度の大きさを超過してその初期状態から変化した値を有すると共に、その他のチャネルの第１値限度の大きさを下回ってその初期状態から変化した値を有する少なくとも１つの前記その他の到来チャネルが存在し、該その他のチャネルも、少なくとも１つの伝送を要するパケットを有している場合に、所与の到来チャネルを選択しないように適合されていることを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項４】
前記マスタ値に対して、第２の選択された値限度が割り当てられることを更なる特徴とし、前記第４手段は、前記マスタ値が、前記第２の値限度の大きさを超過してその初期状態から変化した値を有している場合に、それぞれのチャネル値と前記マスタ値をそれらの初期値にリセットするように適合されていることを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項５】
それぞれのチャネル値がリセットされる際に、前記リセット直前のそのチャネルの前記第１値限度を超過した前記チャネル値の量が、当該チャネルの前記チャネル値の前記初期値から差し引かれることを更なる特徴とする前項記載のパケットスイッチング構成。
【請求項６】
前記マスタ値がリセットされる際に、前記リセット直前の前記第２値限度を超過した前記マスタ値の量が、そのチャネルの第１値限度を超過してその初期状態から前記チャネル値を変化させなかったチャネルの前記チャネル値を増加させるように、分配されることを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項７】
選択された伝送要件を有するものとして到来チャネルを特徴付ける手段を有することを更なる特徴とし、前記第３手段は、前記伝送要件を満足させることを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項８】
前記伝送要件は、最大パケット間遅延であることを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項９】
前記伝送要件は、固定パケット間遅延であることを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項１０】
前記伝送要件は、最小帯域幅であることを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項１１】
前記伝送要件は、最大帯域幅であることを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項１２】
それぞれのチャネルに対して保持されている前記値と前記マスタ値は、それぞれのチャネルが、最小帯域幅、最大帯域幅、及び定義されたパケット間遅延範囲内に抑制されるようになっていることを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項１３】
前記第３手段は、それぞれの到来チャネルに状態識別子を割り当てる更なる手段を含んでおり、この識別子は、当初は、そのチャネルの前記伝送要件に基づいて選択されるが、前記チャネルの後の動作に従って変化することを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項１４】
前記状態識別子は、チャネルがパケット間遅延要件を有していることを示す値を取得することができる前項記載のパケットスイッチング構成。
【請求項１５】
前記状態識別子は、チャネルが最小帯域幅要件を有していることを示す値を取得することができる前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項１６】
前記状態識別子は、チャネルがその最小伝送要件を超過したことを示す値を取得することができる前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項１７】
前記状態識別子は、チャネルがその最大帯域幅制約を超過したことを示す値を取得することができる前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項１８】
前記状態識別子は、チャネルが、送信を要するパケットを有していないことを示す値を取得することができる前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項１９】
前記第３手段は、前記チャネルの選択が前記状態識別子に基づいたものになっており、前記パケットの伝送によって、前記状態識別子の異なる値に対して前記チャネルが適格になった場合に、前記選択されたチャネルの前記状態識別子を更新するべく更なる手段が提供されていることを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項２０】
それぞれのチャネルごとに第２チャネル値を保存する手段を有し、到来チャネルに対して、前記第１チャネル値の値が差し引かれた前記第２チャネル値の値に比例して前記チャネルのすべての伝送要件を満足させるのに必要なものを上回る前記送出チャネル上における帯域幅に対するアクセスが付与されることを更なる特徴とする前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項２１】
それぞれのチャネルが最小帯域幅、最大帯域幅、及び定義されたパケット間遅延範囲内に抑制されるように、少なくとも２つの到来チャネルの１つの送出チャネルに対するアクセスを仲裁するパケットスイッチングシステムにおける方法であって、
それぞれのチャネルごとにチャネル値を保存する段階と、
マスタ値を保存する段階と、
前記送出チャネルを通じてパケットを伝送するべく許容される１つの到来チャネルを選択する段階と、
前記到来チャネルの中の１つから前記送出チャネルへの伝送が許容された際に、当該チャネルの前記クレジット値を変化させる段階と、
前記マスタ値における対応する変化を実現する段階と、
を含んでいる方法。
【請求項２２】
それぞれの到来チャネルに対して第１の選択された値限度を割り当てる段階と、
所与の到来チャネルが、そのチャネルの前記第１値限度の大きさを超過してその初期状態から変化したチャネル値を有すると共に、その他のチャネルの第１値限度の大きさを下回ってその初期状態から変化した値を有する少なくとも１つの前記その他の到来チャネルが存在し、前記その他のチャネルも、少なくとも１つの伝送を要するパケットを有している場合に、前記送出チャネルを通じてパケットを伝送するべく許容されるように、前記所与の到来チャネルを選択しない段階と、
を含んでいることを更なる特徴とする直前の請求項記載の方法。
【請求項２３】
第２の選択された値限度を割り当てる段階と、
前記マスタ値が、前記第２値限度の大きさを超過してその初期状態から変化した値を有している場合に、それぞれのチャネル値と前記マスター値をそれらの初期値にリセットする段階と、
前記リセット直前のそのチャネルの前記第１値限度を超過した前記チャネル値の量を、当該チャネルの前記チャネル値の前記初期値から差し引く段階と、
前記リセット直前の前記第２値限度を超過した前記マスタ値の量を、そのチャネルの第１値限度を超過してその初期状態から前記チャネル値を変化させなかったチャネルの前記チャネル値を増加させるべく、配分する段階と、
を含むことを更なる特徴とする直前の２つの請求項の中のいずれか一項記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットスイッチングに関するものである。
【背景技術】
【０００２】
以下、以前に提案されているいくつかのシステムについて説明するが、これらに対するこの引用は、これらのシステムが、現時点で公表されていたり、以前に使用されていたり、或いは、共通の一般的な知識となっていることを認めるものではないことに留意されたい。課題とするところは、トラフィックシェイピングシステムにおいて、最小及び最大帯域幅を実現すると共に、リアルタイム遅延限度に制約を加えるべく試みることである。このためのメカニズムの１つが、ＷＦＱ（Ｗｅｉｇｈｔｅｄ  Ｆａｉｒ  Ｑｕｅｕｉｎｇ）システムである。ＷＦＱにおいては、フローを異なるカテゴリに分け、必要に応じて、それぞれのカテゴリに対して、リンクの比率を付与するべく試みる。これは、この比率に基づいた最小帯域幅がパケットに対して保証されることを意味している。又、これにより、フローの連続したパケット間において遅延限度を算出することも可能である。しかしながら、遅延限度を改善するには、対象のキューに対して付与する有効比率を上げなければならないという点が問題である。即ち、遅延限度が有効な最小帯域幅と緊密に関連しているのである。アプリケーションには、小さな最小帯域幅特性を有する一方で、タイトな遅延限度特性を有しているものが多い。これをＷＦＱによって解決することはできない。
【０００３】
システムからフローを送出する最大レートを制限するには、ＴＢＦ（Ｔｏｋｅｎ  Ｂｕｃｋｅｔ  Ｆｉｌｔｅｒｉｎｇ）を使用することができる。このメカニズムは、一定の最大レートに上限が設定されたレートでバケツ内に配置される概念的なトークンとして説明することができる。パケットを送信しようとする場合には、フローは、まず、バケツから必要な数のトークンを取得しなければならない。このトークンを取得できない場合には、フローは、十分なトークンがバケツ内に蓄積されるまで待機しなければならない。これは、フローが、その最小限保証されたレートを取得可能であることを意味している。但し、バケツが一杯になった場合に、フローがバーストし、システムの瞬間的な容量を上回る速度でデータを伝送する場合がある。そして、このバーストが望ましくないと考えられる状況が存在するのである。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
有用な代替手段を提供することが本発明の目的である。
【０００５】
チャネルバーストが発生する可能性を低下させることが本発明の更なる目的である。
【課題を解決するための手段】
【０００６】
本発明の一態様は、パケットスイッチング構成であり、この構成は、少なくとも２つの到来チャネルと１つの送出チャネルを含み、それぞれの到来チャネルごとにクレジット値を保存する第１手段と、マスタ値を保存する第２手段と、送出チャネルを通じてパケットを伝送するべく許容される１つの到来チャネルの選択を実現するべく適合された第３手段と、到来チャネルの中の１つから送出チャネルへの伝送が許容された際に、そのチャネルのクレジット値における変化と、マスタ値における対応する変化を実現するべく適合された第４手段と、を含んでいる。
【０００７】
好ましくは、これらの値のそれぞれにおける変化は、等しいものになる。
【０００８】
好ましくは、それぞれの到来チャネルには、第１の選択された値限度が割り当てられており、第３手段は、所与の到来チャネルが、そのチャネルの第１値限度の大きさを超過してその初期状態から変化した値を有すると共に、その他のチャネルの第１値限度の大きさを下回ってその初期状態から変化した値を有する少なくとも１つのその他の到来チャネルが存在し、このその他のチャネルも、少なくとも１つの伝送を要するパケットを有している場合に、所与の到来チャネルを選択しないように適合されていることを特徴としている。
【０００９】
好ましくは、マスタ値には、第２の選択された値限度が割り当てられており、第４手段は、マスタ値が、この第２値限度の大きさを超過してその初期状態から変化した値を有している場合に、それぞれのチャネル値とマスタ値をそれらの初期値にリセットするように適合されていることを更なる特徴としている。
【００１０】
好ましくは、それぞれのチャネル値をリセットする際に、リセット直前のそのチャネルの第１値限度を超過したチャネル値の量が、そのチャネルのチャネル値の初期値から差し引かれる。
【００１１】
好ましくは、マスタ値をリセットする際に、リセット直前の第２値限度を超過したマスタ値の量が、チャネルの第１値限度を上回ってその初期状態からチャネル値を変化させなかったチャネルのチャネル値を増加させるべく、分配される。
【００１２】
好ましくは、選択された伝送要件を有するものとして到来チャネルを特徴付ける手段が存在し、第３手段は、これらの伝送要件を満足させることを更なる特徴としている。
【００１３】
好ましくは、伝送要件は、最大パケット間遅延である。
【００１４】
好ましくは、代替実施例において、伝送要件は、固定パケット間遅延である。
【００１５】
好ましくは、伝送要件は、最小帯域幅である。
【００１６】
好ましくは、伝送要件は、最大帯域幅である。
【００１７】
好ましくは、それぞれのチャネルに対して保持される値とマスタ値は、それぞれのチャネルが、最小帯域幅、最大帯域幅、及び定義されたパケット間遅延範囲内に抑制されるようになっている。
【００１８】
好ましくは、第３手段は、それぞれの到来チャネルに状態識別子を割り当てる更なる手段を含んでおり、この識別子は、当初は、当該チャネルの伝送要件に基づいて選択されるが、チャネルのその後の動作に従って変化する。
【００１９】
好ましくは、状態識別子は、チャネルがパケット間遅延要件を有していることを示す値を取ることができる。
【００２０】
好ましくは、状態識別子は、チャネルが最小帯域幅要件を有していることを示す値を取ることができる。
【００２１】
好ましくは、状態識別子は、チャネルがその最小伝送要件を超過したことを示す値を取ることができる。
【００２２】
好ましくは、状態識別子は、チャネルがその最大帯域幅制限を超過したことを示す値を取ることができる。
【００２３】
好ましくは、状態識別子は、チャネルが、送信を要するパケットを有していないことを示す値を取ることができる。
【００２４】
好ましくは、第３手段は、チャネルの選択が状態識別子に基づいて行われ、パケットの伝送によって、チャネルが状態識別子の異なる値に対して適格となった場合に、その選択されたチャネルの状態識別子を更新するべく更なる手段が提供されていることを更なる特徴としている。
【００２５】
好ましくは、それぞれのチャネルの第２チャネル値を保存するための手段が存在しており、到来チャネルに対して、第１チャネル値の値だけ差し引かれた第２チャネル値の値に比例して、すべてのチャネルの伝送要件を満足させるのに必要とされるものを上回る送出チャネル上の帯域幅に対するアクセスが付与される。
【００２６】
又、本発明は、それぞれのチャネルが、最小帯域幅、最大帯域幅、及び定義されたパケット間遅延範囲内に抑制されるように、少なくとも２つの到来チャネルの１つの送出チャネルに対するアクセスを仲裁する方法の形態を取ることも可能であり、この方法は、それぞれのチャネルのチャネル値を保存する段階と、マスタ値を保存する段階と、パケットを送出チャネルを通じて伝送するべく許容される１つの到来チャネルを選択する段階と、到来チャネルの１つから送出チャネルへの伝送が許容された際に、そのチャネルのクレジット値を変更する段階と、マスタ値における対応する変化を実現する段階と、を含んでいる。
【００２７】
好ましくは、この方法は、それぞれの到来チャネルに対して第１の選択された値限度を割り当てる段階と、所与のチャネルが、そのチャネルの第１値限度の大きさを超過してその初期状態から変化したチャネル値を有していると共に、その他のチャネルの第１値限度の大きさを下回ってその初期状態から変化した値を有する少なくとも１つのその他の到来チャネルが存在し、このその他のチャネルも、少なくとも１つの伝送を要するパケットを有している場合に、所与の到来チャネルを送出チャネルを通じてパケットを伝送するべく許容するように選択しない段階と、を更に含んでいる。
【００２８】
好ましくは、この方法は、第２の選択された値限度を割り当てる段階と、マスタ値が、この第２の値限度の大きさを超過してその初期状態から変化した値を有している場合に、それぞれのチャネル値とマスタ値をそれらの初期値にリセットする段階と、リセット直前のそのチャネルの第１値限度を超過したチャネル値の量をそのチャネルのチャネル値の初期値から差し引く段階と、リセット直前の第２値限度を超過したマスタ値の量を分配し、チャネルの第１値限度を超過してその初期状態からチャネル値を変化させなかったチャネルのチャネル値を増加させる段階と、を更に含んでいる。
【発明を実施するための最良の形態】
【００２９】
以下、本発明を十分に理解できるように、好適な実施例との関連で、本発明について説明するが、この特定の実施例は、本発明の一態様を例示するものに過ぎないことを理解されたい。
【００３０】
チャネル１００、１０１、１０２、１０３、１０４、１０５、１０６、１０７、１０８、及び１０９は、論理的なフローであり、１つのチャネルは、特定のトラフィックストリームのパケットの論理的なフローである。チャネルを通じて流れるすべてのパケットは、パケットマーカーを通過した後に、同一のマークを有することになる。本システム内におけるそれぞれのチャネルは、それと関連づけられたパケットキューを有している（例えば、１００を参照されたい）。チャネルによってマーキングされた到来パケットは、更なる処理のために、関連するパケットキュー内に入ることになる。これは、すべてのパケットにとって、本システムに入るため最初のエントリポイントである。
【００３１】
このシステムは、そのＢＷに基づいて、それぞれのチャネルに対して特定量のクレジットを割り当てる。チャネルの状態と使用されるクレジットの量を使用し、システムは、伝送のためにパケットをリリースするべく、チャネルを選択及びスケジュールする。そして、チャネルが、そのパケットを送信するべく許容されると、本システムは、チャネルの状態とクレジットを更新することになる。それぞれのチャネルにおいて送信を要するパケットがなくなるまで、このプロセス全体が繰り返し反復される。
【００３２】
本システムが使用するクレジットのタイプには、次の２つが存在している。
【００３３】
マスタクレジット：これは、トラフィック全体を追跡するために使用されるものであり、パケットが任意のチャネルから送信された際に消費される。このマスタクレジットを所有しているのは、本システムのマスタコントローラである。マスタクレジット限度は、チャネルクレジットの合計と等しい。
【００３４】
チャネルクレジット：これは、特定のチャネルのトラフィックを追跡するのに使用されるものである。それぞれのチャネルは、独自のチャネルクレジットを所有している。
【００３５】
マスタクレジットシステムは、全体的なクレジットの利用状況を追跡し、チャネルによって使用されるチャネルクレジットを戻すタイミングを決定する。チャネルが伝送するそれぞれのパケットにより、チャネルクレジットが消費される。わかりやすくするべく、１クレジット＝１バイトとする。従って、システムが１５００バイトのパケットをチャネルから抽出する場合には、チャネルは、１５００チャネルクレジットを消費することになる。そして、システムがこのパケットを実際に送信した際に、１５００マスタクレジットが消費されることになる。
【００３６】
パケットは、チャネル内にバッファリングされ、システムによる伝送のために待機する。
【００３７】
レートリミッタ１１０、１１２、１１４、１１６、及び１１９は、パケットが前の要素から次の要素に流れるレートを制限するものである。パケットをシステム内の次の場所に送信した結果、設定限度を上回る伝送レートとなる場合には、そのパケットは送信されない。
【００３８】
チャネルは、次の状態の中の１つを有することができる。
【００３９】
ＮＯＮＥ（２０１）：ユーザーによって割り当てられていない。
【００４０】
ＩＤＬＥ（２０２）：使用するべく既に割り当てられているが、そのチャネルのパケットは、まだ受信されていない。
【００４１】
ＲＴ（リアルタイム）（２０４）：このチャネルは既に割り当てられており、リアルタイム保証が付与されている。又、これは、送信を要するパケットを現在有している。
【００４２】
ＢＷ（２０３）：このチャネルは既に割り当てられており、付与されたリアルタイム制約は存在しない。又、これは、送信を要するパケットを現在有している。
【００４３】
ＧＲＥＥＤＹ（２０５）：このチャネルは既に割り当てられているが、そのＲＴ／ＢＷクレジットレベルを既に超過している。これは、送信を要するパケットをより多く現在有している。
【００４４】
ＲＥＳＴＲＩＣＴＥＤ（２０６）：このチャネルは、チャネルレートリミッタの最大スループットを既に超過している。又、これは、送信を要するパケットをより多く有している。
【００４５】
ＢＷサブシステム１２７は、ＢＷサブシステムから送信する次のパケットを選択する責任を担うＢＷチャネルスケジューラ１１１を含んでいる。チャネルは、十分なクレジットを有すると共に（その最小帯域幅を下回っている）、リアルタイムチャネルに分類されない場合に、チャネルブローカ１２６からＢＷサブシステムに入る。
【００４６】
ＲＴチャネルスケジューラ１１３は、ＲＴサブシステム１２８から送信する次のパケットを選択する責任を担っている。チャネルは、十分なクレジットを有すると共に（その最小帯域幅を下回っている）、リアルタイムチャネルに分類される場合に、チャネルブローカ１２６からＲＴサブシステムに入る。
【００４７】
ＧＲＥＥＤＹチャネルスケジューラ１１５は、ＧＲＥＥＤＹサブシステム１２９から送信する次のパケットを選択する責任を担っている。チャネルは、そのＢＷクレジット限度を超過している（その最小帯域幅を上回っている）場合に、チャネルブローカ１２６からＧＲＥＥＤＹサブシステムに入る。これらは、リアルタイム又は非リアルタイムチャネルであってよい。
【００４８】
チャネルは、その最大帯域幅を超過している場合に、チャネルブローカ１２６からＲＥＳＴＲＩＣＴＥＤサブシステム１３０に入る。これらは、システムに再度入るために１１７、十分なクレジットを蓄積するまで、必要な数のクォンタムだけ待機することになる。そして、それが実現すると、これらは、チャネルブローカ１２６に移動し、システムに再配分される。
【００４９】
チャネルは、送信を要するパケットを有していない場合に１２２、チャネルブローカ１２６からＩＤＬＥサブシステム１３１に入る。そして、送信を要するパケットを再度得た場合に、これらは、システム内における再配分のために、チャネルブローカに戻る１２１。
【００５０】
クレジットに基づいたスケジューラ１２５は、システムから送出される次のパケットの選定と、更新のためのチャネルのチャネルブローカへの再配分の責任を担っている。これは、常に、まず、ＲＴサブシステムに対してパケットを要求する。そして、ＲＴサブシステムが、送信を要するパケットを有していない場合には、ＢＷサブシステムに対して要求する。そして、ＲＴ及びＢＷサブシステムが、送信を要するパケットを有していない場合には、ＧＲＥＥＤＹサブシステムに対して、送信を要するパケットを要求する。この結果、パケットは、送出レートリミッタ１１９を通過してインターフェイスカード１２０に送出される。これらのすべてが、マスタコントローラ１２４内に内蔵されている。
【００５１】
本システムの動作については、図２の状態図によって説明することができる。
【００５２】
２０１は、ＮＯＮＥ状態を示している。この状態においては、チャネルは、まだシステムに対して適切に割り当てられていない。２０２は、ＩＤＬＥ状態を示している。ＩＤＬＥ状態のチャネルは、ＩＤＬＥサブシステム１３１内に位置している。２０３は、ＢＷ状態を示している。ＢＷ状態のチャネルは、ＢＷサブシステム１２７内に位置している。２０４は、ＲＴ状態を示している。ＲＴ状態のチャネルは、ＲＴサブシステム１２８内に位置している。２０５は、ＧＲＥＥＤＹ状態を示している。ＧＲＥＥＤＹ状態のチャネルは、ＧＲＥＥＤＹサブシステム１２９内に位置している。２０６は、ＲＥＳＴＲＩＣＴＥＤ状態を示している。ＲＥＳＴＲＩＣＴＥＤ状態のチャネルは、ＲＥＳＴＲＩＣＴＥＤサブシステム１３０内に位置している。
【００５３】
割り当てられると、チャネルは、ＩＤＬＥ状態に移動する２０７。ＩＤＬＥ状態においては、チャネルは、送信を要するパケットを有していない。そして、送信を要するパケットを得た場合に、チャネルは、ＢＷ状態２０８（チャネルが、非リアルタイムチャネルと判定されると共に、そのクレジット限度を下回っている場合（最小帯域幅を下回っている場合））、ＲＴ状態２０９（チャネルがリアルタイムチャネルと判定され、そのクレジット限度を下回っている場合（最小帯域幅を下回っている場合））、及びＧＲＥＥＤＹ状態２１２（チャネルが、そのクレジット限度を超過している場合（最小帯域幅を上回っている場合））のどれかに移動することになる。
【００５４】
ＢＷ、ＲＴ、及びＧＲＥＥＤＹ状態のいずれかから、チャネルは、ＲＥＳＴＲＩＣＴＥＤ状態に移動することができる（それぞれ２１４、２１５、及び２１３）。これは、チャネルがその最大帯域幅を上回っていること、及び、伝送するべく準備が整った適切な状態に戻る（２２０、２２１、又は２１９）までに、一定期間待機しなければならないことを意味している。
【００５５】
ＧＲＥＥＤＹ、ＢＷ、又はＲＴ状態において、チャネルが、伝送を要するパケットをもはや有していない場合には、そのチャネルはＩＤＬＥ状態に戻ることになる（それぞれ、２１８、２１７、及び２１６）。
【００５６】
特定のラウンドにおいて、システム内のマスタクレジットが使用された場合には、ＧＲＥＥＤＹ状態におけるチャネルは、ＢＷ２２２又はＲＴ２２３に戻ることができる。そして、これが発生した場合には、チャネルクレジットは、その状態に関係なく、すべてのチャネルに戻される。
【００５７】
それぞれのチャネルは、使用されたチャネルクレジットを追跡するクレジット利用状況カウンタを有している。又、それぞれのチャネルは、２つの設定可能なクレジット限度をも有している。第１の限度は、ＲＴ／ＢＷ限度であり、もう１つの限度は、ＧＲＥＥＤＹ限度である。ＧＲＥＥＤＹ限度は、常にＲＴ／ＢＷ限度以上である。クレジットの利用状況がこれらの限度を超過すると、チャネル状態の変化の可能性について、マスタコントローラ１２４に通知される。そして、マスタコントローラ１２４は、そのチャネルが別の状態に移動する必要があるかどうかを決定する。
【００５８】
マスタコントローラ１２４は、チャネルから抽出した１つのパケットをカーネルが要求するまで保持するための１パケットキューを有している。そして、そのパケットをカーネルに渡した際に、コントローラは、マスタクレジットを消費すると共に、カーネルからの次の要求に対する準備として、１パケットキューを満たすべく、選定したチャネルに対して別のパケットを要求する。
【００５９】
コントローラ１２４は、設定可能なマスタクレジット利用状況レベルを有している。マスタクレジットの利用状況がこの限度を超過した場合に、すべてのチャネルによって使用されたチャネルクレジットと、使用されたマスタクレジットを戻すように、コントローラ１２４は通知される。その期間内に、割り当てられたクレジット利用状況レベルを超過したチャネルが存在する場合には、超過した量が次の期間に繰り越されることになる。
【００６０】
そして、マスタクレジット限度を超過した量が算出され、その期間内において、ＲＴ／ＢＷクレジットを使い果たすことができなかったチャネルに対して、この量のクレジットが均等に再配分される。
【００６１】
例えば、次のような３つのチャネル１、２、３を有しているとしよう。
【００６２】
・チャネル１：割り当てられた２０００クレジットの中の１０００クレジットを使用している。
【００６３】
・チャネル２：割り当てられた１２００クレジットの中の１５００クレジットを使用している（３００だけ超過している）。
【００６４】
・チャネル３：割り当てられた１８００クレジットの中の２０００クレジットを使用している（２００だけ超過している）。
【００６５】
・使用されたマスタクレジット：４５００、マスタクレジット限度：５０００
【００６６】
チャネル１に対して、１０００クレジットを使用するパケットの送信が許容された場合に、マスタクレジット限度をトリガすることになる。この結果、すべてのチャネルに、そのクレジットが戻され、クレジット利用状況レベルを超過しているチャネルについては、新しい期間に繰り越されることになる。一方、クレジットを使い果たすことができなかったすべてのチャネルは、クレジット限度を超過したチャネルから、クレジットを均等に受け取ることになる。
【００６７】
段階１：マスタクレジット限度をトリガする。
【００６８】
・チャネル１：割り当てられた２０００クレジットの中の２０００クレジットを使用している。
【００６９】
・チャネル２：割り当てられた１２００クレジットの中の１５００クレジットを使用している（３００だけ超過している）。
【００７０】
・チャネル３：割り当てられた１８００クレジットの中の２０００クレジットを使用している（２００だけ超過している）。
【００７１】
・使用されたマスタクレジット：５５００、マスタクレジット限度：５０００
【００７２】
・使用されたマスタクレジットが、５００だけ超過している。
【００７３】
段階２：チャネルクレジットとマスタクレジットをリセットし、超過したクレジットを繰り越す。
【００７４】
・チャネル１：使用されたクレジットは０である。
【００７５】
・チャネル２：使用されたクレジットは、３００である。
【００７６】
・チャネル３：使用されたクレジットは、２００である。
【００７７】
・使用されたマスタクレジット：５００、マスタクレジット限度：５０００
【００７８】
段階３：使用クレジットが超過しなかったチャネルに対して、超過したクレジットを均等に配分する。
【００７９】
・チャネル１：割り当てられた２０００クレジットの中の−５００クレジットが使用されている（即ち、２５００クレジットが利用可能である）。
【００８０】
・チャネル２：割り当てられた１２００クレジットの中の３００クレジットが使用されている（即ち、９００クレジットが利用可能である）。
【００８１】
・チャネル３：割り当てられた１８００クレジットの中の２００クレジットが使用されている（即ち、１６００クレジットが利用可能である）。
【００８２】
・使用されたマスタクレジット：０、マスタクレジット限度：５０００
【００８３】
このケースでは、クレジット限度を超過していないのは、チャネル１のみであり、超過したクレジットは、３００＋２００＝５００であった。従って、チャネル１は、限度を超過しなかった唯一のチャネルであるため、超過したクレジットをすべて受け取ることになる。
【００８４】
このクレジットの利用プロセスは、チャネルから抽出されるそれぞれのパケットについて継続される。
【００８５】
マスタコントローラ１２４内のシステムスケジューラは、チャネルクレジットの利用状況と状態情報を使用し、パケットを送信するチャネルを選択する。チャネルの状態を判定するには、クレジットレベル及び利用状況を使用する。
【００８６】
チャネルブローカは、新しく割り当てられたチャネルのすべてをＩＤＬＥ２０２チャネルスケジューラに移動させる。そして、ＩＤＬＥチャネルのパケットが到来すると、ＩＤＬＥチャネルスケジューラは、チャネルブローカ１２６に対して、その非アイドルチャネルを適切な状態に移動させるように通知する。このチャネルは、そのチャネルに付与されたリアルタイム保証が存在するかどうかに応じて、ＲＴ（２０４、１２８）又はＢＷ（２０３、１２７）状態のいずれかになる。尚、チャネルが、アイドル状態になる前に、ＧＲＥＥＤＹ（２０５、１２９）状態であって場合には、新しいパケットが到来した際に、再度ＧＲＥＥＤＹ（２０５、１２９）状態に移行することになる。
【００８７】
クレジットに基づいたスケジューラ１２５は、チャネルから送信されるパケットを次の順序で選択する。
【００８８】
・ＲＴセレクタ１１３から送信されるべく待機しているＲＴチャネルが存在するかどうかをチェックする。そして、これが存在する場合には、そのパケットを送信し、後処理のために、そのチャネルをチャネルブローカ１２６に転送する。
【００８９】
・ＢＷセレクタ１１１から送信されるべく待機しているＢＷチャネルが存在するかどうかをチェックする。そして、これが存在する場合には、そのパケットを送信し、後処理のために、そのチャネルをチャネルブローカ１２６に転送する。
【００９０】
・ＧＲＥＥＤＹセレクタ１１５から送信されるべく待機しているＧＲＥＥＤＹチャネルが存在するかどうかをチェックする。そして、これが存在する場合には、そのパケットを送信し、後処理のために、そのチャネルをチャネルブローカ１２６に転送する。
【００９１】
チャネルブローカ１２６は、チャネルから、そのチャネルがレベルを超過していることについて通知される。チャネルブローカは、必要に応じて、そのチャネルに新しい状態を付与し、そのチャネルをその新しい状態の適切なチャネルスケジューラに移動させる。
【００９２】
チャネルブローカは、ＲＴ（２０４、１２８）から、２１６を介してＩＤＬＥ（２０２、１３１）へ、２１１を介してＧＲＥＥＤＹ（２０５、１２９）へ、或いは、２１５を介してＲＥＳＴＲＩＣＴＥＤ（２０６、１３０）への状態変化を実行することができる。
【００９３】
更に可能な状態変化は、ＢＷ（２０３、１２７）から、２１７を介してＩＤＬＥ（２０２、１３１）へ、２１０を介してＧＲＥＥＤＹ（２０５、１２９）へ、或いは、２１４を介してＲＥＳＴＲＩＣＴＥＤ（２０６、１３０）である。
【００９４】
ＲＴ／ＢＷチャネルが、送信を要するパケットをもはや有していない場合には、それらのチャネルは、ＩＤＬＥ（２０２、１３１）状態に移動される。
【００９５】
ＲＴ／ＢＷチャネルが、そのＲＴ／ＢＷクレジットレベルを超過している場合には、それらのチャネルは、ＧＲＥＥＤＹ（２０５、１２９）状態に移動される。
【００９６】
ＲＴ／ＢＷチャネルが、そのレートリミッタスループットを超過している場合には、それらのチャネルは、ＲＥＳＴＲＩＣＴＥＤ（２０６、１３０)状態に移動される。
【００９７】
ＧＲＥＥＤＹ（２０５、１２９）チャネルが、送信を要するパケットをもはや有していない場合には、それらのチャネルは、ＩＤＬＥ（２０２、１３１）状態に移動される。
【００９８】
ＧＲＥＥＤＹ（２０５、１２９）チャネルが、チャネルレートリミッタスループットを超過している場合には、それらのチャネルは、ＲＥＳＴＲＩＣＴＥＤ（２０６、１３０）状態に移動される。
【００９９】
マスタクレジットがすべて使用され、すべてのクレジットがチャネルに戻された場合には、チャネルは、ＧＲＥＥＤＹからＢＷ（２０３、１２７）又はＲＴ（２０４、１２８）に移動することができる。
【０１００】
ＲＥＳＴＲＩＣＴＥＤ状態（２０６、１３０）のチャネルは、チャネルブローカ（１２６）によって再割当されるまで、もはやパケットを送信することはできない。これらのチャネルは、それぞれのタイムクォンタムごとに、チャネルブローカ（１２６）によってチェックされ、それらのいずれかがＲＥＳＴＲＩＣＴＥＤ状態（２０６、１３０）から移動可能であるかどうかが確認される。チャネルが移動できるのは、スループットがそのレート限度を下回っている場合のみである。
【０１０１】
チャネルは、ＲＥＳＴＲＩＣＴＥＤ（２０６、１３０）から、２２１を介してＲＴ（２０４、１２８）へ、２２０を介してＢＷ（２０３、１２７）へ、或いは、２１９を介してＧＲＥＥＤＹ（２０５、１２９）へ移動可能である。
【０１０２】
マスタコントローラにより、（マスタクレジット使用状況レベルを超過した後に）それぞれのチャネルにおいてクレジットが回復されると、このクレジットの変化を反映するべく、チャネルの状態が更新される。
【０１０３】
メイン出力には、カーネルを通じて全体的なスループットを制御するべく、マスタレートリミッタ１１９が装着されている。メインスループットがスループット限度を超過した場合には、カーネルが更なるデータを要求した場合にも、パケットの送信は許容されない。システムは、そのスループットが限度を下回った場合に、再度送信することができる。
【０１０４】
それぞれのチャネルスケジューラは、同一状態を有する１つ又は複数のチャネルを制御している。クレジットに基づいたスケジューラ１２５が、チャネルスケジューラに対してチャネルを要求した場合に、特定の選択アルゴリズムに基づいてその制御下のチャネルのプールから１つのチャネルを選択する作業は、チャネルスケジューラに任せられている。それぞれのチャネルスケジューラは、選択用の異なるアルゴリズムを有している。
【０１０５】
ＲＴスケジューラ１１３のアルゴリズムは、リアルタイムネットワークトラフィックの受付及びスケジューリング法に基づいたものになっている。
【０１０６】
ＢＷスケジューラ１２７のアルゴリズムは、次のとおりである。
【０１０７】
・ＢＷ内に移動した場合には、チャネルは、ＢＷチャネルキューの末尾にプッシュされる。
【０１０８】
・データを送信するべく選択される第１チャネルは、常に、ＢＷキューの先頭に位置するチャネルである。
【０１０９】
・ＢＷキューの先頭において選択されたチャネルは、データがマスタコントローラに転送された後に、ＢＷチャネルキューの末尾にプッシュされる。
【０１１０】
ＧＲＥＥＤＹスケジューラ１１５のアルゴリズムは、次のとおりである。
【０１１１】
・優先順位は、正又は負であってよいが、値が大きいほど、チャネルは、伝送可能な上位の優先順位を取得する。次いで、チャネルは、優先順位の降順で、ＧＲＥＥＤＹチャネルキュー内に挿入される。
【０１１２】
・送信するべく選択される第１のチャネルは、常に、ＧＲＥＥＤＹキューの先頭に位置するチャネルである。
【０１１３】
ＲＥＳＴＲＩＣＴＥＤ（２０６、１３０）及びＩＤＬＥ（２０２、１３１）の場合には、パケットを送信するべく選定されないため、チャネルスケジューラを有していない。
【０１１４】
更なる実施例（図示されていない）においては、ＢＷ／ＲＴクレジット及びＧＲＥＥＤＹクレジットに加えて、更なるクレジットタイプを使用し、更なる状態をアルゴリズム状態機械に導入することにより、更に分化したサービスレベルを提供している。
【図面の簡単な説明】
【０１１５】
【図１】本発明のシステムアーキテクチャを示している。
【図２】本システムの状態図を示している。これは、システムを通じてチャネルがどのように流れるかを示すものである。
【図１】
2005510957.tif 000003
【図２】
2005510957.tif 000004
【国際調査報告】
2005510957.tif 000005
2005510957.tif 000006
2005510957.tif 000007