(57)【要約】  パケット間遅延要件を有するリアルタイムチャネルをシステム内に受け入れ可能かどうかを判定する方法を含むパケットスイッチングシステムを開示している。又、これらのパケット間遅延要件に基づいて、パケットを送信するチャネルをスケジューリングする方法及び手段についても提示している。更には、パケットに対して選択されたジッタ要件を提供する変形についても開示している。
2005510959.tif 000002
【特許請求の範囲】
【請求項１】
パケットスイッチング構成であって、
それぞれの到来チャネルの選択された最大パケット間遅延を保存するべく適合された第１手段と、
送出チャネル上において利用可能なビットレートに比例した第１値と、それぞれの到来チャネルに関連付けられており、それぞれがその対応する到来チャネル上において可能な最大パケットサイズに比例すると共に、その同じ対応する到来チャネルの選択された最大ビットレートに反比例する複数の第２値と、を保存する第２手段と、
最後の選択されたチャネルを包含した結果、選択されている到来チャネルのそれぞれの前記第２値の合計が、前記第１値の選択された範囲内になるか或いはこれを超過することのない場合に、それぞれが前記送出チャネルを通じたパケットの伝送が許容されている到来チャネルのグループに対する参加が許容される到来チャネルを選択するべく適合された第３手段と、
前記送出チャネル上においてパケットを伝送する前記到来チャネルのグループから１つのチャネルを選択する第４手段であって、任意の到来チャネルが経験する任意のパケット間遅延が当該チャネルの選択された最大パケット間遅延を上回らないことが確実なチャネルのみを選択するべく更に適合されている第４手段と、
を有するパケットスイッチング構成。
【請求項２】
前記第１値は、前記送出チャネルのビットレートによって乗算された到来チャネルの最大指定可能遅延に等しいクレジット値である請求項１記載のパケットスイッチング構成。
【請求項３】
前記第２値は、選択された到来チャネルに許容されている最大パケットサイズ（単位：ビット）に、任意の到来チャネルの最大指定可能遅延を乗算し、その結果を当該チャネルの選択された最大パケット間遅延によって除算することによって算出されたクレジット値である前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項４】
前記第４手段は、任意の所与のタイムクォンタムにおいて、既に選択されている到来チャネルは、再度選択されることにはならず、前記タイムクォンタムにおいてまだ選択されていないチャネルに、送信するパケットを有する別の到来チャネルが存在していることによって更に特徴付けられる前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項５】
前記第４手段は、現在のタイムクォンタムにおいてパケットを送信する候補である到来チャネル用の第１キューと、後続のタイムクォンタムまでパケットを送信する候補ではない到来チャネル用の第２キューと、を含み、前記現在のタイムクォンタムの終了時点において、パケットの送信を許容するべく既に選択されているチャネルは、前記第１キューから前記第２キューに移動され、前記第２キュー内のすべてのチャネルは、前記第１キュー内に移動される前項までの請求項中のいずれか一項記載のパケットスイッチング構成。
【請求項６】
前記第４手段は、それぞれの到来チャネルが前記第１キュー内に移動する際に、それぞれの到来チャネルに対して、当該チャネルの最大許容可能遅延に比例した値によってタイムスタンプを付与する手段と、タイムスタンプ値によって前記キューをソートする手段と、前記ソートされたキューに沿って移動可能なポインタと、を含み、このようにポイントされたチャネルは、前記送出チャネル上におけるパケットの伝送を許容するベく選択される請求項５記載のパケットスイッチング構成。
【請求項７】
前記タイムスタンプは、「現在時刻」＋「当該到来チャネルの最大許容可能遅延値」である請求項６記載のパケットスイッチング構成。
【請求項８】
前記ポインタは、タイムスタンプとして前記現在時刻を有しているエントリを超えて前記キューに沿って更に移動することはない請求項６記載のパケットスイッチング構成。
【請求項９】
パケットスイッチング方法であって、
それぞれの到来チャネルの選択された最大パケット間遅延を保存する段階と、
送出チャネル上において利用可能なビットレートに比例した第１値と、それぞれが到来チャネルに関連付けられており、それぞれがその対応する到来チャネル上において可能な最大パケットサイズに比例すると共に、その同じ対応する到来チャネルの選択された最大ビットレートに反比例する複数の第２値と、を算出する段階と、
最後の選択されたチャネルを包含した結果、選択されている到来チャネルのそれぞれの前記第２値の合計が、前記第１値の選択された範囲内になるか或いはこれを超過することのない場合に、それぞれが前記送出チャネルを通じたパケットの伝送が許容されている到来チャネルのグループに対する参加が許容される到来チャネルを選択する段階と、
前記送出チャネル上においてパケットを伝送する前記到来チャネルのグループからの１つのチャネルの選択を実現する段階と、
任意の到来チャネルが経験する任意のパケット値遅延が当該チャネルの選択された最大パケット間遅延を上回らないことが確実なチャネルのみの選択を実現する段階と、
を含むパケットスイッチング方法。
【請求項１０】
前記第１値は、前記送出チャネルのビットレートによって乗算された任意の到来チャネルの最大指定可能遅延に等しいクレジット値である請求項９記載のパケットスイッチング方法。
【請求項１１】
前記第２値は、選択された到来チャネルに許容された最大パケットサイズ（単位：ビット）に、任意の到来チャネルの最大指定可能遅延を乗算し、その結果を当該チャネルの選択された最大パケット間遅延によって除算することによって算出されたクレジット値である請求項９又は１０の中のいずれか一項記載のパケットスイッチング方法。
【請求項１２】
任意の所与のタイムクォンタムにおいて、前記送出チャネル上においてパケットを伝送するべく既に選択されている到来チャネルは、そのように再度選択されることにはならず、前記タイムクォンタムにおいてまだ選択されていないチャンネルに、送信するパケットを有する別の到来チャネルが存在していることによって更に特徴付けられる請求項９、１０、又は１１の中のいずれか一項記載のパケットスイッチング方法。
【請求項１３】
現在のタイムクォンタムにおいてパケットを送信する候補である到来チャネルを第１キュー内に配置する段階と、
後続のタイムクォンタムまでパケットを送信する候補ではない到来チャネルを第２キュー内に配置する段階と、
を更に含み、
現在のタイムクォンタムの終了時点において、パケットの送信を許容するべく既に選択されているチャネルは、前記第１キューから前記第２キューに移動され、前記第２キュー内のすべてのチャネルは、前記第１キュー内に移動される請求項９、１０、１１、又は１２の中のいずれか一項記載のパケットスイッチング方法。
【請求項１４】
それぞれの到来チャネルが前記第１キュー内に移動する際に、それぞれの到来チャネルに対して、当該チャネルの最大許容可能遅延に比例した値によってタイムスタンプを付加する段階と、
タイムスタンプ値によって前記キューをソートする段階と、
前記ソートされたキューに沿って移動可能なポインタを使用する段階と、
を含み、
このようにポイントされたチャネルは、前記送出チャネル上におけるパケットの伝送を許容するべく選択される請求項１３記載のパケットスイッチング方法。
【請求項１５】
前記タイムスタンプは、「現在時刻」＋「当該到来チャネルの最大許容可能遅延値」である請求項１４記載のパケットスイッチング方法。
【請求項１６】
前記ポインタは、タイムスタンプとして前記現在時刻を有するエントリを超えて更に前記キューに沿って移動することがない請求項１４記載のパケットスイッチング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットスイッチング構成に関し、更に詳しくは、選択された限度内にパケット間遅延が限定されているパケットスイッチング構成に関するものである。
【背景技術】
【０００２】
リアルタイムフローのスケジューリングは、これまで、ＥＤＤ（Ｅａｒｌｉｅｓｔ  Ｄｕｅ  Ｄａｔｅ）スケジューラによって行われている。ＥＤＤスケジューラは、システムを通過するパケットの遅延識別を提供するメカニズムである。それぞれのチャネルは、関連付けられた遅延限度を有している。特定の時刻に到来した特定クラスのパケットには、到来時刻に遅延限度を加算することにより、デッドラインタグが付与される。そして、デッドラインタグの昇順に、パケットが転送される。この構成の欠点は、小さな遅延限度を有するチャネルが送出チャネル上の予備容量を独占し、長い遅延限度を有する同一のチャネルに比べて、大きな平均伝送帯域幅を実現する傾向を有していることである。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
このような１つ又は複数の問題点を少なくともある程度軽減する（或いは、有用な代替手段を少なくとも提供する）ことが本発明の目的である。
【課題を解決するための手段】
【０００４】
本発明の一態様は、パケットスイッチング構成であり、これは、それぞれの到来チャネルの選択された最大パケット間遅延を保存するべく適合された第１手段と；送出チャネル上において利用可能なビットレートに比例した第１値と、それぞれが到来チャネルに関連付けられており、それぞれがその対応する到来チャネル上において可能な最大パケットサイズに比例すると共に、その同一の対応する到来チャネルの選択された最大ビットレートに反比例する複数の第２値を保存する第２手段と；最後に選択されたチャネルを包含した結果、選択された到来チャネルのそれぞれの第２値の合計が、第１値の選択範囲内になるか或いはこれを超過することがない場合に、それぞれが送出チャネルを通じたパケットの伝送が許容されている到来チャネルのグループに対する参加が許容される到来チャネルを選択するべく適合された第３手段と；送出チャネル上におけるパケットの伝送が許容されて到来チャネルのグループから１つのチャネルを選択する第４手段であって、任意の到来チャネルが経験する任意のパケット間遅延が、当該チャネルの選択された最大パケット間遅延を上回らないことが確実なチャネルのみを選択するべく更に適合されている第４手段と；を有している。
【０００５】
好ましくは、第１値は、送出チャネルのビットレートによって乗算された任意の到来チャネルの最大指定可能遅延に等しいクレジット値である。
【０００６】
好ましくは、第２値は、選択された到来チャネルに許容されている最大パケットサイズ（単位：ビット）に、任意の到来チャネルの最大指定可能遅延を乗算し、その結果を当該チャネルの選択された最大パケット間遅延によって除算することによって算出されたクレジット値である。
【０００７】
好ましくは、パケットを伝送するチャネルを選択する手段は、任意の所与のタイムクォンタムにおいて、既に選択されている到来チャネルが再度選択されることにはならず、このタイムクォンタムにおいてまだ選択されていないチャネルに、送信するパケットを有する別の到来チャネルが存在していることによって更に特徴付けられている。
【０００８】
好ましくは、パケットを伝送するチャネルを選択する手段は、現在のタイムクォンタムにおいてパケットを送信する候補である到来チャネル用の第１キューと、後続のタイムクォンタムまでパケットを送信する候補ではない到来チャネル用の第２キューを含み、現在のタイムクォンタムの終了時点においてパケットの送信を許容するべく既に選択されているチャネルは、第１キューから第２キューに移動され、第２キュー内のすべてのチャネルは、第１キュー内に移動される。
【０００９】
好ましくは、パケットを送信するチャネルを選択する手段は、それぞれの到来チャネルが第１キュー内に移動する際に、それぞれの到来チャネルに対して、そのチャネルの最大許容可能遅延に比例した値によってタイムスタンプを付加する手段と、タイムスタンプ値によってキューをソートする手段と、ソートされたキューに沿って移動可能なポインタと、を更に含み、このようにポイントされたチャネルは、送出チャネル上においてパケットを伝送することを許容するべく選択される。
【００１０】
好ましくは、タイムスタンプは、「現在時刻」＋「当該到来チャネルの最大許容可能遅延値」である。
【００１１】
好ましくは、代替実施例において、ポインタは、タイムスタンプとして現在時刻を有するエントリを超えて更にキューに沿って移動することはない。
【００１２】
又、本発明によれば、パケットスイッチング方法も提供され、この方法は、それぞれの到来チャネルの選択された最大パケット間遅延を保存する段階と；送出チャネル上において利用可能なビットレートに比例する第１値と、それぞれが到来チャネルと関連付けられており、それぞれが、その対応する到来チャネル上において可能な最大パケットサイズに比例すると共に、その同一の対応する到来チャネルの選択された最大ビットレートに反比例する複数の第２値を算出する段階と；最後の選択されたチャネルを包含した結果、選択されている到来チャネルのそれぞれの第２値の合計が、第１値の選択された範囲内になるか或いはこれを超過することがない場合に、それぞれが送出チャネルを通じてパケットを伝送することを許容される到来チャネルのグループに対する参加が許容される到来チャネルを選択する段階と；送出チャネル上においてパケットを伝送する到来チャネルのグループから１つのチャネルを選択する段階と；任意の到来チャネルが経験する任意のパケット間遅延がそのチャネルの選択された最大パケット間遅延を上回らないことが確実なチャネルのみを選択する段階と；を含んでいる。
【００１３】
好ましくは、第１値は、送出チャネルのビットレートによって乗算された任意の到来チャネルの最大指定可能遅延に等しいクレジット値である。
【００１４】
好ましくは、第２値は、選択された到来チャネルに許容されている最大パケットサイズ（単位：ビット）に、任意の到来チャネルの最大指定可能遅延を乗算し、その結果を当該チャネルの選択された最大パケット間遅延によって除算することによって算出されたクレジット値である。
【００１５】
好ましくは、任意の所与のタイムクォンタムにおいて、送出チャネル上においてパケットを伝送するべく既に選択されている到来チャネルは、再度そのように選択されることにはならず、当該タイムクォンタムにおいてまだ選択されていないチャネルに、送信するパケットを有する別の到来チャネルが存在している。
【００１６】
好ましくは、現在のタイムクォンタムにおいてパケットを送信する候補である到来チャネルは、第１キュー内に配置され、後続のタイムクォンタムまでパケットを送信する候補ではない到来チャネルは、第２キュー内に配置され、現在のタイムクォンタムの終了時点において、パケットの送信を許容するべく既に選択されているチャネルは、第１キューから第２キューに移動され、第２キューのすべてのチャネルは、第１キュー内に移動される。
【００１７】
好ましくは、この方法は、それぞれの到来チャネルが第１キュー内に移動する際に、それぞれの到来チャネルに対して、当該チャネルの最大許容可能遅延に比例した値によってタイムスタンプを付加する段階と、タイムスタンプ値によってキューをソートする段階と、ソートされたキューに沿って移動可能なポインタを使用する段階と、を含み、このようにポイントされたチャネルは、送出チャネル上におけるパケットの伝送を許容するべく選択される。
【００１８】
好ましくは、タイムスタンプは、「現在時刻」＋「当該到来チャネルの最大許容可能遅延値」である。
【００１９】
好ましくは、代替実施例において、ポインタは、タイムスタンプとして現在時刻を有するエントリを超えて更にキューに沿って移動することはない。
【００２０】
以下、本発明を十分に理解できるように、添付の図面を参照し、好適な実施例との関連で、本発明について説明するが、これらの特定の実施例は、本発明の一態様を例示するものに過ぎないことを理解されたい。
【発明を実施するための最良の形態】
【００２１】
到来リンク１７は、送出リンク１８へのアクセスを求める多くのチャネルを搬送している。クレジットに基づいたシステムを使用し、チャネルをシステム内に受け入れ可能かどうか（即ち、送出リンクに対するアクセス権を付与するかどうか）を判定する。クレジットの合計数は、システムの送出ビットレートによって乗算された最大指定可能遅延（これは、任意に選定される）に等しくなる。この値は、ソフトウェアモジュール１５によって算出並びに保存される。
【００２２】
それぞれのチャネルは、チャネル識別モジュール１３によって算出及び保存されたいくつかのクレジットを有することになる。このクレジット値は、アレイ１１内に保存されている当該チャネルの最大パケットサイズ（単位：ビット）に、最大指定可能遅延を乗算し、アレイ１０内に保存されている当該チャネルが許容可能な最大パケット間遅延によって除算した結果であり、アレイ１２内に保存される。
【００２３】
これらの値はチャネル仲裁モジュール１４に伝達される。本システムは、１５に保存されている本システムの合計クレジットが、含まれているすべてのチャネルのクレジット値の合計以下である場合に、すべてのチャネルの要求を満足することができる。受け入れ可能なチャネルの組は、チャネル仲裁モジュールによって保存される。
【００２４】
又、本システムが受け入れた到来チャネルの既存の組が存在する場合に、新しいチャネルの最大パケットサイズが判明している場合には、本システムは、新しい到来チャネルに対して提供可能なパケット間遅延の最大限度を容易に算出することができる。逆にいえば、その新しいチャネルの最大パケット遅延が指定されている場合には、新しいチャネルの最大許容可能パケットサイズを容易に算出することができる。
【００２５】
スケジューリングモジュール１６は、低遅延要件のみを理由として、低遅延要件を有するチャネルに対して大きな帯域幅を付与することなしに、それぞれのチャネルのパケット間遅延要件を満足するべく、パケットの伝送を許容するチャネルを選択する。以下、その動作を説明する。
【００２６】
本システムには、次の２つのポインタが存在している。
【００２７】
Ｔ（１０３）：現在のカーネル時刻ポインタである。これは、現在のカーネル時刻の値を有している。これは、個々のタイムクォンタムにおいて、カーネルによって更新される。
【００２８】
Ｐ（１０４）：チャネル処理ポインタである。これは、次に処理するチャネルをポイントする。これには、最先タイムスタンプを有するチャネルのタイムスタンプ値が格納される。
【００２９】
リアルタイムチャネルは、システム内に受け入れられ、（Ｔ＋チャネル最大遅延）の値によってタイムスタンプが付加され、タイムスタンプの昇順で、キュー（１０８）内に挿入される。従って、２ｍｓの最大遅延を有するチャネル（１００）には、値「Ｔ＋２ｍｓ」によってタイムスタンプが付加されることになる。
【００３０】
後述する特定の基準に基づいて、Ｐは、送信する次のチャネルをポイントする。
【００３１】
Ｐは、常に最先タイムスタンプを有するチャネルをポイントするように設定されている。
【００３２】
現在のタイムクォンタムにおいて（即ち、Ｔの値が更に変化する前の段階において）選択される資格を有するチャネル用のスケジューリングキュー（１０８）と、待機キュー（１０５）という２つのキューを保持している。パケットを送信するべく選択した際に、１つのチャネルがスケジューリングキューから取り出され、待機キューに挿入されることになる。これは、Ｔが変化するまで、再度リスケジューリングされることはない。この結果、それぞれのチャネルが、公平なチャンスを獲得することができ、更なるパケットの送信を所望する場合に、その他の等価なリアルタイムチャネルと比べて、益々低い優先順位を取得するようになる。
【００３３】
Ｔの変化を検出すると、待機キュー内のすべてのチャネルは、この新しいＴ値に関連してリスケジューリングされる。この結果、直前のタイムクォンタムにおいて送信するべく選択されなかったチャネルは、Ｔの値が変化する前の段階で選択された等価なチャネルに比べて、小さなタイムスタンプを有することになる。
【００３４】
本システムが、スケジューリングキュー内のすべてのチャネルについてパケットを送信可能である場合も存在するが、この場合には、すべてのチャネルが待機キュー内に位置することになる。そして、パケットを送信するための更なる要求を取得すると、本システムは、待機キューから適切なタイムスタンプを有するすべてのチャネルをスケジューリングキューに戻す。
【００３５】
プロセッサの負荷が重いために、システムがチャネルを処理することができず、Ｔが実際に１つ又は複数のチャネルのタイムスタンプを超過してしまう場合も存在する。これは、スケジューラがこれらのチャネルのリアルタイム遅延要件を満足しないことを意味している。この場合には、Ｐは、最小のタイムスタンプを有するチャネルをポイントするベく再調節され、Ｔの値に接近するべく試みることになる。スケジューラは、最低のタイムスタンプを有するチャネルからパケットを送信する。そして、これらのチャネルは、その他のチャネルが処理されている間に、待機キューに移動される。そして、これらの「遅延」したチャネルは、通常のチャネルのように取り扱われ、それらの次のスケジュールは、新しいＴに関連したものとなる。送信するパケットを有する新しいチャネルは、「Ｔ＋チャネル遅延」に関連して挿入されて、Ｔを上回ることが保証されているため、高い優先順位を取得することにはならない。従って、Ｐは、まず、遅延したチャネルをスケジューリングするチャンスを得ることになるのである。
【００３６】
リアルタイムスケジューラが、遅延したパケットをドロップする実施例においては、本システムは、以前の段階をスキップし、遅延したチャネルからパケットをドロップし、新しいＴに関連してそれらを即座に再度リスケジューリングすることになろう。
【００３７】
図面を参照すれば、次の状況が存在している。すべてのパケットが最大伝送単位又はパケットサイズ（ＭＴＵ）を伝送しており、本システムは、１ミリ秒当たり、２ＭＴＵのサイズのパケットを伝送することができると仮定する。次の５つのチャネルが存在しており、チャネルＡは、２ｍｓの最大遅延限度を有しており、チャネルＢは、２ｍｓの最大遅延限度を有しており、チャネルＣは、４ｍｓの最大遅延限度を有しており、チャネルＤは、４ｍｓの最大遅延限度を有しており、チャネルＥは、４ｍｓの最大遅延限度を有している。
【００３８】
図２に示されているように、チャネルＤ（１０６）及びＥ（１０７）は、待機キュー（１０５）内に位置している。これは、２つのパケットが、既に１０００ｍｓタイムスロット内において送信されていることを意味している。本システムは、１ミリ秒当たり、２つのパケットしか送信できないため、時刻は１００１ｍｓに進む。
【００３９】
図３において、時刻によってソートされたリスト（２０７）内に、チャネルＤ及びＥを戻さなければならない。これらは、４ｍｓチャネルであり、現在時刻Ｔが１００１ｍｓ（２０５）であるため、これらは、リストの１００５ｍｓ（２０９）の部分に移動する。ポインタＰ（２０６）は、リスト内の次に送信するチャネルをポイントする。そして、リスト内の２つのチャネルが、１００１ｍｓ時間スロット内においてパケットを送信するべく許容される。これは、チャネルＡ（２０１）とＢ（２００）である。
【００４０】
図４には、チャネルＡ（３０７）とチャネルＢ（３０８）が、それぞれのパケットの送信を完了し、待機キュー内に位置していることが示されている。
【００４１】
図５においては、時刻が１ｍｓだけ進んでいる。チャネルＡ（４０１）とＢ（４００）がリスト上において再ソートされ、このプロセスは継続する。
【００４２】
遅延の下限がゼロを上回る代替実施例において（図示されてはいない）、Ｐは、最小遅延限度値に加算された現在のカーネル時刻値を有している。この実施例は、パケット間遅延の優れた限定性（即ち、小さなジッタ）が要求されている場合に使用されることになる。Ｐの値は、Ｔの値を超過することができない。即ち、送信するチャネルを示すポインタが、タイムスタンプが現在時刻であるものを超えて更にスケジューリングキューに沿って移動することは決してない。
【図面の簡単な説明】
【００４３】
【図１】本システムのブロックダイアグラムを示している。
【図２】本システムの初期状態を示している。時刻は、１０００ｍｓであり、送信する複数のパケットを有する本システム内には、５つのチャネルが存在している。
【図３】１０００ｍｓタイムクォンタム後の本システムを示している。以前のタイムクォンタムにおいてパケットを送信した２つのチャネルは、その最大遅延に基づいてリスケジューリングされる。
【図４】１００３ｍｓタイムクォンタム後のシステムを示しており、チャネルリスケジューリングの実行が完了する前の段階である。
【図５】１００３ｍｓタイムクォンタムのリスケジューリング後のシステムを示しており、１００４ｍｓタイムクォンタムが始まる前の段階である。
【図１】
2005510959.tif 000003
【図２】
2005510959.tif 000004
【図３】
2005510959.tif 000005
【図４】
2005510959.tif 000006
【図５】
2005510959.tif 000007
【国際調査報告】
2005510959.tif 000008
2005510959.tif 000009