(57)【要約】第１のパケット入力部が、外部から入力されるパケットに付与されている識別子に基づいて第１または第２のパケットキュー部にパケットを振り分け、第１のキュー制御部は、第１および第２のパケットキュー部を回転優先制御に基づいて選択して、選択した第１または第２のパケットキュー部の第１または第２のカウント値レジスタおよび蓄積されたパケットの状態によってパケットを取得するとともに選択した第１または第２のパケットキュー部の第１または第２のカウント値レジスタの重みカウント値を変更し、第１のパケット生成部が、第１のキュー制御部が取得したパケットを多重化するようにしている。
2005006672.tif 000002
【特許請求の範囲】
【請求項１】
パケットを蓄積するとともに、当該蓄積するパケットに基づいた重みカウント値を保持する第１のカウント値レジスタを有するｎ（ｎは自然数）個の第１のパケットキュー部と、
パケットを蓄積するとともに、当該蓄積するパケットに基づいた重みカウント値を保持する第２のカウント値レジスタを有し、前記パケットを出力する際に、蓄積したパケットを多重化して出力するｍ（ｍは自然数）個の第２のパケットキュー部と、
外部から入力されるパケットに付与されている識別子に基づいて前記入力されるパケットを前記ｎ個の第２のパケットキュー部およびｍ個の第１のパケットキュー部に振り分ける第１のパケット入力部と、
前記ｎ個の第１のパケットキュー部およびｍ個の第２のパケットキュー部を回転優先制御に基づいて選択して、該選択した第１または第２のパケットキュー部の第１または第２のカウント値レジスタおよび蓄積されたパケットの状態によってパケットを取得するとともに、前記選択した第１または第２のパケットキュー部の第１または第２のカウント値レジスタの重みカウント値を変更する第１のキュー制御部と、
この第１のキュー制御部が取得したパケットを多重化する第１のパケット生成部と、
を備えることを特徴とするスケジューリング装置。
【請求項２】
前記第１のキュー制御部は、
前記ｎ個の第１のパケットキュー部およびｍ個の第２のパケットキュー部の回転優先を示す第１のキュー選択ポインタと、
この第１のキュー選択ポインタが示す第１または第２のパケットキュー部を選択して、この選択した第１のパケットキュー部の第１のカウント値レジスタまたは第２のパケットキュー部の第２のカウント値レジスタの重みカウント値が正数で、かつ選択した第１または第２のパケットキュー部にパケットが蓄積されている場合にパケットを取得して、取得したパケットを前記第１のパケット生成部に出力する第１のキュー選択部と、
この第１のキュー選択部が選択した第１のパケットキュー部の第１のカウント値レジスタまたは第２のパケットキュー部の第２のカウント値レジスタの重みカウント値が正数の場合、この第１または第２のカウント値レジスタの重みカウント値を更新する第１の重みカウント値更新部と、
前記ｎ個の第１のパケットキュー部の各第１のカウント値レジスタおよび前記ｍ個の第２のパケットキュー部の各第２のカウント値レジスタの重みカウント値がすべて０または負数の場合、各第１および第２のカウント値レジスタの重みカウント値を再設定する第１の重みカウント値再設定部と、
を備えることを特徴とする請求の範囲第１項に記載のスケジューリング装置。
【請求項３】
前記第１の重みカウント値更新部は、
前記第１のキュー選択部が選択した第１または第２のパケットキュー部からパケットを取得した場合には、前記取得したパケットのパケット長の値を前記選択した第１のパケットキュー部の第１のカウント値レジスタまたは第２のパケットキュー部の第２のカウント値レジスタの重みカウント値から減算して、減算した値を新たな重みカウント値として前記第１または第２のカウント値レジスタに設定し、前記第１のキュー選択部が選択した第１または第２のパケットキュー部にパケットが蓄積されていない場合には、前記選択した第１または第２のパケットキュー部が蓄積することができる最大パケット長分の重みを前記第１または第２のカウント値レジスタの重みカウント値から減算して、減算した値を新たな重みカウント値として前記第１または第２のカウント値レジスタに設定することを特徴とする特許請求の範囲第２項に記載のスケジューリング装置。
【請求項４】
前記第１の重みカウント値再設定部は、
前記ｎ個の第１のパケットキュー部の第１のカウント値レジスタおよびｍ個の第２のパケットキュー部の第２のカウント値レジスタの重みカウント値毎に、品質および／または帯域に応じて変動するパケットの最大パケット長以上の値を加算して、加算した値を新たな重みカウント値として前記各第１および第２のカウント値レジスタに設定することを特徴とする請求の範囲第２項に記載のスケジューリング装置。
【請求項５】
前記第２のパケットキュー部は、
パケットを蓄積するとともに、当該蓄積するパケットに基づいた重みカウント値を保持する第３のカウント値レジスタを有する複数の第３のパケットキュー部と、
前記第１のパケット入力部から入力されるパケットに付与されている識別子に基づいて前記入力されるパケットを前記複数の第３のパケットキュー部に振り分ける第２のパケット入力部と、
前記複数の第３のパケットキュー部を回転優先制御に基づいて選択して、該選択した第３のパケットキュー部の第３のカウント値レジスタおよび蓄積されたパケットの状態によってパケットを取得するとともに、前記選択した第３のパケットキュー部の第３のカウント値レジスタの重みカウント値を変更する第２のキュー制御部と、
この第２のキュー制御部が取得したパケットを多重化する第２のパケット生成部と、
を備えることを特徴とする特許請求の範囲第１項に記載のスケジューリング装置。
【請求項６】
前記第２のキュー制御部は、
前記複数の第３のパケットキュー部の回転優先を示す第２のキュー選択ポインタと、
この第２のキュー選択ポインタが示す第３のパケットキュー部を選択して、この選択した第３パケットのキュー部の第３のカウント値レジスタの重みカウント値が正数で、かつ選択した第３のパケットキュー部にパケットが蓄積されている場合にパケットを取得して、取得したパケットを前記第２のパケット生成部に出力する第２のキュー選択部と、
この第２のキュー選択部が選択した第３のパケットキュー部の第３のカウント値レジスタの重みカウント値が正数の場合、この第３のカウント値レジスタの重みカウント値を更新する第２の重みカウント値更新部と、
前記各第３のパケットキュー部の第３のカウント値レジスタの重みカウント値がすべて０または負数の場合、各第３のカウント値レジスタの重みカウント値を再設定する第２の重みカウント値再設定部と、
を備えることを特徴とする請求の範囲第５項に記載のスケジューリング装置。
【請求項７】
前記第２の重みカウント値更新部は、
前記第２のキュー選択部が選択した第３のパケットキュー部からパケットを取得した場合には、前記取得したパケットのパケット長の値を前記選択した第３のパケットキュー部の第３のカウント値レジスタの重みカウント値から減算して、減算した値を新たな重みカウント値として前記第３のカウント値レジスタに設定し、前記第２のキュー選択部が選択した第３のパケットキュー部にパケットが蓄積されていない場合には、前記選択した第３のパケットキュー部が蓄積することができる最大パケット長分の重みを前記第３のカウント値レジスタの重みカウント値から減算して、減算した値を新たな重みカウント値として前記第３のカウント値レジスタに設定することを特徴とする特許請求の範囲第６項に記載のスケジューリング装置。
【請求項８】
前記第２の重みカウント値再設定部は、
前記各第３のパケットキュー部の第３のカウント値レジスタの重みカウント値毎に、品質および／または帯域に応じて変動するパケットの最大パケット長以上の値を加算して、加算した値を新たな重みカウント値として前記各第１のカウント値レジスタに設定することを特徴とする請求の範囲第６項に記載のスケジューリング装置。
【発明の詳細な説明】
【技術分野】  この発明は、非同期転送モード（ＡＴＭ：Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｔｒａｎｓｆｅｒ  Ｍｏｄｅ）やＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）パケットなどのパケットを送出するスケジューリング装置に関するものであり、特に、可変長のパケットを送出する順番を制御するスケジューリング装置に関するものである。
【背景技術】  パケットを用いたネットワークにおいては、そのサービスの特性に応じてパケット転送の差別化が図られている。たとえば、ＡＴＭでは、スケジューリング装置が、音声、動画などのリアルタイム性の高いトラフィックのパケットと、インターネットで使用されるＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）の閲覧や電子メールなどのリアルタイム性を要求されないサービスのパケットとをヘッダ内の識別子が示す優先クラスを用いて識別して、これらのパケットの送信順序を変更することで優先制御や帯域制御を実現していた。
インターネットの基本は、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）を用いてすべてのパケットを公平に扱うＢｅｓｔ  Ｅｆｆｏｒｔ型、すなわち、サービスの品質を保証しない通信サービスである。しかし、近年のインターネットの普及に伴い、インターネットを使用したビジネスが展開され、高品質のサービスや音声、動画通信といったリアルタイムのアプリケーションが要求されている。そのため、インターネットにおいても、音声に代表されるリアルタイム性の必要なサービスと、必ずしもリアルタイム性の必要のないサービスとを区別して、通信サービス品質（ＱｏＳ：Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅｓ）を考慮した技術が考えられている。
ＩＰにおいてＱｏＳを実現するために、上述したＡＴＭのスケジューリング装置を用いてパケット単位のスケジューリングを行った場合、優先クラスごとにスケジューラ装置に入力されるパケットの分布が偏ってしまうため、優先クラスごとの公平性を保てないという問題があった。この問題を改善するためには、可変長パケットに対応する必要があり、スケジューリング装置は、パケット長を意識したスケジューリングを行わなければならない。
このようにＩＰにおいてＱｏＳを実現するために可変パケット長に対応した従来技術のスケジューリング装置は、パケットを保持するパケットキューと、２つのスケジューリングキュー部を有するスケジューリング部を備え、スケジューリングキュー部から取得した識別子に基づいてパケットを出力するパケットキューをインターリーブに選択するようにしている。また、入力パケットを、たとえば、リアルタイムクラス、ノンリアルタイムクラスというようにクラス別に分類して、これら分類したクラス毎にスケジューリング部を設けることで、クラス別のスケジューリングを実現するようにしている（たとえば、特許文献１参照）。
【特許文献１】          特開平１０−０８４３８３号公報
しかしながら、上記従来技術では、たとえば、入力パケットを多重して、多重したパケットを１つのパケットとして扱うというような、複数のパケットキューに跨った処理に対する技術は開示されていない。
上記従来技術で、複数のパケットキューに跨った処理を実現する場合、スケジューリング後のパケットを一旦蓄積して、再度スケジューリングを行わなければならない。たとえば、ＡＴＭのアダプレーションレイヤの一つであるＡＡＬ２（ＡＴＭ  Ａｄａｐｔａｔｉｏｎ  Ｌａｙｅｒ２）のＣＰＳ（Ｃｏｍｍｏｎ  Ｐａｃｋｅｔ  Ｓｕｂｌａｙｅｒ）パケットを多重する場合、ＣＰＳパケットは、特定の仮想チャネル識別子（ＶＣＩ：Ｖｉｒｔｕａｌ  Ｃｈａｎｎｅｌ  Ｉｄｅｎｔｉｆｉｅｒ）単位でのみ多重が可能である。そのため、取り出したパケットを多重可能なパケットキューにまとめて１つのグループとしなければならない。上記従来技術のスケジューリング装置において、特定のＶＣＩのパケットのみの多重を実現しようとすると、スケジューリング部の処理が複雑になってしまい、効率的に複数のパケットキューに跨るパケットの処理を行うことができないという問題があった。
本発明は、上記に鑑みて成されたものであって、可変長パケットに対応し、かつ入力された複数のパケットの特定のパケットに対しては多重を行った後にスケジューリングを行うスケジューリング装置を得ることを目的としている。
【発明の開示】
本発明にかかるスケジューリング装置にあっては、パケットを蓄積するとともに、当該蓄積するパケットに基づいた重みカウント値を保持する第１のカウント値レジスタを有するｎ（ｎは自然数）個の第１のパケットキュー部と、パケットを蓄積するとともに、当該蓄積するパケットに基づいた重みカウント値を保持する第２のカウント値レジスタを有し、前記パケットを出力する際に、蓄積したパケットを多重化して出力するｍ（ｍは自然数）個の第２のパケットキュー部と、外部から入力されるパケットに付与されている識別子に基づいて前記入力されるパケットを前記ｎ個の第２のパケットキュー部およびｍ個の第１のパケットキュー部に振り分ける第１のパケット入力部と、前記ｎ個の第１のパケットキュー部およびｍ個の第２のパケットキュー部を回転優先制御に基づいて選択して、該選択した第１または第２のパケットキュー部の第１または第２のカウント値レジスタおよび蓄積されたパケットの状態によってパケットを取得するとともに、前記選択した第１または第２のパケットキュー部の第１または第２のカウント値レジスタの重みカウント値を変更する第１のキュー制御部と、この第１のキュー制御部が取得したパケットを多重化する第１のパケット生成部とを備えることを特徴とする。
この発明によれば、第１のパケット入力部が、入力されるパケットに付与されている識別子に基づいてパケットの品質クラスを識別して、品質クラス毎にｎ個の第１のパケットキュー部またはｍ個の第２のパケットキュー部に振り分ける。第１のキュー制御部は、回転優先制御によって第１または第２のパケットキュー部を選択して、選択した第１または第２のパケットキュー部内部のカウント値レジスタの重みカウント値と蓄積されたパケットの状態によってパケットを取得する。このとき、第２のパケットキュー部は、蓄積した複数のパケットを多重化して新たな１つのパケットを生成し、生成したパケットを第１のキュー制御部が取得するようにしている。
【図面の簡単な説明】  第１図は、この発明におけるスケジューリング装置の構成を示すブロック図であり、第２図は、第１図に示したキュー制御部の構成を示すブロック図であり、第３図は、この発明におけるスケジューリング装置の動作を説明するためのフローチャートである。
【発明を実施するための最良の形態】  本発明をより詳細に説術するために、添付の図面に従ってこれを説明する。
第１図〜第３図を用いて、この発明の本実施の形態を説明する。第１図は、この発明における本実施の形態のスケジューリング装置の構成を示すブロック図である。この発明における本実施の形態のスケジューリング装置は、第１のパケット入力部であるパケット入力部１１−０と、ｎ（ｎは自然数）個の第１のパケットキュー部１２−１〜１２−ｎと、ｍ（ｍは自然数）個の第２のパケットキュー部１５−１〜１５−ｍと、第１のキュー制御部１３であるキュー制御部１３−１と、第１のパケット生成部であるパケット生成部１４−１とを備えている。
パケット入力部１１−０は、入力パケットに付与されている識別子に基づいて入力パケットの品質クラスを識別して、識別した品質クラスに対応する第１のパケットキュー部１２−１〜１２−ｍ、第２のパケットキュー部１５−１〜１５−ｎの何れかに入力パケットを振り分ける。
第１のパケットキュー部１２−１〜１２−ｍは、それぞれに重みカウント値を保持する第１のカウント値レジスタであるカウント値レジスタ１６−１を有しており、パケット入力部１１−０により振り分けられた固定長または可変長のパケットを蓄積する。
第２のパケットキュー部１５−１〜１５−ｎは、それぞれ同じ機能を備えている。第２のパケットキュー部１５−１は、第２のパケット入力部であるパケット入力部１１−１と、第３のパケットキュー部であるａ（ａは自然数）の第１のパケットキュー部１２−０１〜１２−１ａと、第２のキュー制御部であるキュー制御部１３−０１と、第２のパケット生成部であるパケット生成部１４−０１と、第２のカウント値レジスタであるカウント値レジスタ１６−０１とを備えている。また、第２のパケットキュー部１５−ｍは、第２のパケット入力部であるパケット入力部１１−ｍと、第３のパケットキュー部であるｂ（ｂは自然数）の第１のパケットキュー部１２−ｍ１〜ｍｂと、第２のキュー制御部であるキュー制御部１３−０ｍと、第２のパケット生成部であるパケット生成部１４−０ｍと、第２のカウント値レジスタであるカウント値レジスタ１６−０ｍとを備えている。第２のパケットキュー部１５−０１〜１５−ｍの異なる点は、それぞれが有する第１のパケットキュー部の数であるが、それぞれが有する第１のパケットキュー部の数は、同一であってもかまわない。ここでは、第２のパケットキュー部１５−１を例にあげて、第２のパケットキュー部の機能を説明する。
パケット入力部１１−１は、パケット入力部１１−０と同一の機能を備えており、パケット入力部１１−０によって振り分けられたパケットに付与されている識別子に基づいてパケットの品質クラスを識別して、識別した品質クラスに対応する第１のパケットキュー部１２−０１〜１２−０ａのいずれかに振り分ける。
第１のパケットキュー部１２−０１〜１２−０ａは、第１のパケットキュー部１２−１〜１２−ｍと同一の機能を備えている。すなわち、第１のパケットキュー部１２−０１〜１２−０ａは、それぞれに重みカウント値を保持するカウント値レジスタ１６−１を有しており、パケット入力部１１−１によってそれぞれに振り分けられた固定長または可変長のパケットを蓄積する。
キュー制御部１３−０１は、定められた順番に基づいて第１のパケットキュー部１２−０１〜１２−０ｍを選択する。そして、選択した第１のパケットキュー部のカウント値レジスタ１６−１のカウント値に基づいて、選択した第１のパケットキュー部に蓄積されているパケットを取得するとともに、第１のパケットキュー部１２−０１〜１２−０ｍのそれぞれの重みカウント値を設定する。
第２図は、第１図に示したキュー制御部１３−０１の構成を示すブロック図である。キュー制御部１３−０１は、第２のキュー選択部であるキュー選択部１３１と、キュー選択ポインタ１３２と、第２の重みカウント値更新部である重みカウント値更新部１３３と、第２の重みカウント値再設定部である重みカウント値再設定部１３４とを備えている。
キュー選択ポインタ１３２には、キュー選択部１３１が選択する第１のパケットキュー部の順番が定められている。キュー選択部１３１は、キュー選択ポインタ１３２が示す第１のパケットキュー部を選択する。選択した第１のパケットキュー部のカウント値レジスタの値が０より大きい（正数）場合、キュー選択部１３１は、選択した第１のパケットキュー部に蓄積されているパケットを取得するとともに、キュー選択ポインタ１３２の値を更新（インクリメント）する。選択した第１のパケットキュー部に対応するカウント値レジスタの値が０より小さい（０または負数）場合、キュー選択部１３１は、キュー選択ポインタ１３２の値をインクリメントして、新たにキュー選択ポインタ１３２が示す第１のパケットキュー部を選択する。すなわち、キュー選択部１３１は、キュー選択ポインタ１３２により設定されたラウンドロビンにより第１のパケットキュー部１２−０１〜１２−０ｍを順に選択する。
重みカウント値更新部１３３は、キュー選択部１３１がパケットを取得可能な場合（選択した第１のパケットキュー部にパケットが蓄積されている場合）、第１のパケットキュー部のカウント値レジスタの重みカウント値から、取得するパケットのパケット長に相当する重みを減算する。そして、減算した値を新たな重みカウント値としてパケットを取得する第１のパケットキュー部のカウント値レジスタ１６−１に設定する。重みカウント値更新部１３３は、キュー選択部１３１がパケットを取得できない場合（選択した第１のパケットキュー部にパケットが蓄積されていない場合）、第１のパケットキュー部のカウント値レジスタ１６−１の重みカウント値から、選択した第１のパケットキュー部に蓄積可能なパケットの最大パケット長に相当する重みを減算する。そして、減算した値を新たな重みカウント値として選択した第１のパケットキュー部のカウント値レジスタ１６−１に設定する。
重みカウント値再設定部１３４は、第１のパケットキュー部１２−０１〜１２−０ａのすべてのカウント値レジスタ１６−１のカウント値が０または負数になった場合、それぞれの重みカウント値を第１のパケットキュー部１２−０１〜１２−０ａのカウント値レジスタ１６−１に再設定する。再設定の重みカウント値は、入力されることが期待される優先クラスに対して、品質や帯域設定などに応じて変動する少なくとも第１のパケットキュー部１２−０１〜１２−０ａそれぞれが蓄積可能なパケットの最大パケット長以上の指定値を、第１のパケットキュー部１２−０１〜１２−０ａのそれぞれのカウント値レジスタ１６−１の重みカウント値に加算した値とする。
第１図にもどって、パケット生成部１４−０１は、キュー制御部１３−０１が取得したパケットを一つのパケットに生成して、生成したパケットを出力する。
キュー制御部１３−１は、第２図に示したキュー制御部１３−０１と同じ機能を備えている。ただし、キュー制御部１３−１のキュー選択ポインタ１３２は、第１のパケットキュー部１２−１〜１２−ｎ、第２のパケットキュー部１５−１〜１５−ｍを示すものである。また、キュー制御部１３−１のキュー選択部１３１は第１のキュー選択部であり、キュー制御部１３−１の重みカウント値更新部１３３は第１の重みカウント値更新部であり、キュー制御部１３−１の重みカウント値再設定部１３４は第１の重みカウント値再設定部である。
パケット生成部１４−１は、パケット生成部１４−０１〜１４−０ｍと同じ機能を備えており、キュー制御部１３−１が取得したパケットを一つのパケットに生成して、生成したパケットを出力する。
つぎに、この発明における本実施の形態のスケジューリング装置の動作を説明する。まず、図３のフローチャートを参照して、パケットを取得する基本動作を説明する。
スケジューリング装置が動作を開始する際に、キュー制御部１３−１，１３−０１〜１３−０ｍは、それぞれのキュー選択ポインタ１３１を初期化する（ステップＳ１００）。
パケット入力部１１−０は、入力パケットに付与されている識別子に基づいてパケットの品質クラスを識別して、識別した品質クラスに対応する第１のパケットキュー部１２−１〜１２−ｎおよびパケット入力部１１−１〜１１−ｍに入力パケットを振り分ける。たとえば、ＡＴＭセルの場合、パケット入力部１１−０は、ＡＴＭセルのヘッダ部のＶＣＩを識別して、多重可能なＣＰＳパケットを第２のパケットキュー部１５−０のパケット入力部１１−１に振り分け、多重処理のないＯＡＭ（Ｏｐｅｒａｔｉｏｎ  Ａｎｄ  Ｍａｉｎｔｅｎａｎｃｅ）セルを第１のパケットキュー部１２−１に振り分ける。
パケット入力部１１−１〜１１−ｍは、パケット入力部１１−０によって振り分けられたパケットに付与されている識別しに基づいてパケットの品質クラスを識別して、識別した品質クラスに対応する第１のパケットキュー部１２−０１〜１２−０ａ、１２−ｍ１〜１２−ｍｂにパケットを振り分ける。
パケット出力許可信号がアサートになると、キュー制御部１３−１のキュー選択部１３１は、キュー選択ポインタ１３２が示す第１のパケットキュー部または第２のパケットキュー部を選択する（ステップＳ１１０）。
ここで、キュー制御部１３−１のキュー選択ポインタ１３２が第１のパケットキュー部１２−１を示していたとする。キュー制御部１３−１のキュー選択部１３１は、第１のパケットキュー部１２−１を選択して、選択した第１のパケットキュー部１２−１内のカウント値レジスタ１６−１のカウント値を確認する。第１のパケットキュー部１２−１のカウント値レジスタ１６−１の重みカウント値が正数の場合（ステップＳ１２０，Ｙｅｓ）、キュー制御部１３−１のキュー選択部１３１は、第１のパケットキュー部１２−１にパケットが蓄積されているかを確認する。第１のパケットキュー部１２−１にパケットが蓄積されている場合（ステップＳ１３０，Ｙｅｓ）、キュー選択部１３−１の重みカウント値更新部１３３は、第１のパケットキュー部１２−１のカウント値レジスタ１６−１の重みカウント値から、取得するパケットのパケット長に相当する重みを減算する（ステップＳ１４０）。そして、減算した値を新たな重みカウント値として第１のパケットキュー部１２−１のカウント値レジスタ１６−１に設定する。
キュー制御部１３−１のキュー選択部１３１は、第１のパケットキュー部１２−１からパケットを取得して、取得したパケットをパケット生成部１４−１に出力する（ステップＳ１５０）とともに、キュー制御部１３−１のキュー選択ポインタ１３２をインクリメントする（ステップＳ１６０）。
選択した第１のパケットキュー部１２−１のカウント値レジスタ１６−１の重みカウント値が正数（ステップＳ１２０，Ｙｅｓ）、かつ選択した第１のパケットキュー部１２−１にパケットが蓄積されていない場合（ステップＳ１３０，Ｎｏ）、キュー制御部１３−１の重みカウント値更新部１３３は、第１のパケットキュー部１２−１のカウント値レジスタ１６−１の重みカウント値から、第１のパケットキュー部１２−１が蓄積可能なパケットの最大パケット長に相当する重みを減算する（ステップＳ１７０）。そして、減算した値を新たな重みカウント値として第１のパケットキュー部１２−１のカウント値レジスタ１６−１に設定する。また、キュー制御部１３−１のキュー選択部１３１は、キュー制御部１３−１のキュー選択ポインタ１３２をインクリメントする（ステップＳ１６０）。
選択した第１のパケットキュー部１２−１のカウント値レジスタ１６−１の重みカウント値が０または負数の場合（ステップＳ１２０，Ｎｏ）、キュー制御部１３−１のキュー選択部１３１は、キュー選択ポインタ１３２に登録されているすべての第１のパケットキュー部１２−１〜１２−ｎ内のそれぞれのカウント値レジスタ１６−１および第２のパケットキュー部１５−１〜１５−ｍ内のそれぞれのカウント値レジスタ１６−０１〜１６−０ｍのカウント値を確認する。第１のパケットキュー部１２−１〜１２−ｎの各カウント値レジスタ１６−１および第２のパケットキュー部１５−１〜１５−ｍのカウント値レジスタ１６−０１〜１６−０ｍの重みカウント値のうち１つ以上が正数の場合（ステップＳ１８０，Ｎｏ）、キュー制御部１３−１のキュー選択部１３１は、キュー制御部１３−１のキュー選択ポインタ１３２をインクリメントする（ステップＳ１６０）。
キュー制御部１３−１のキュー選択部１３１は、キュー制御部１３−１のキュー選択ポインタ１３２が示すすべての第１のパケットキュー部１２−１〜１２−ｎ内の各カウント値レジスタ１６−１および第２のパケットキュー部１５−１〜１５−ｍのカウント値レジスタ１６−０１〜１６−０ｍの重みカウント値がすべて０または負数になるまで、キュー制御部１３−１のキュー選択キュー選択ポインタ１３２が示す第１のパケットキュー部または第２のパケットキュー部を選択して、選択した第１のパケットキュー部または第２のパケットキュー部のカウント値レジスタを確認して、パケットを取得する動作を繰り返す（ステップＳ１１０〜ステップＳ１８０）。
第１のパケットキュー部１２−１〜１２−ｎの各カウント値レジスタ１６−１および第２のパケットキュー部１５−１〜１５−ｍのカウント値レジスタ１６−０１〜１６−０ｍの重みカウント値がすべて０または負数になると（ステップＳ１８０，Ｙｅｓ）、キュー制御部１３−１の重みカウント値再設定部１３４は、第１のパケットキュー部１２−１〜１２−ｎの各カウント値レジスタ１６−１および第２のパケットキュー部１５−１〜１５−ｍのカウント値レジスタ１６−０１〜１６−０ｍの重みカウント値の再設定処理を行う（ステップＳ１９０）。具体的には、入力されることが期待される優先クラスに対して、品質や帯域設定などに応じて変動する少なくとも各カウント値レジスタを有する第１のパケットキュー部または第２のパケットキュー部に蓄積可能なパケットの最大パケット長以上の指定値を、各カウント値レジスタの重み付けカウント値に加算する。そして、加算した値を新たな重みカウント値として各カウント値レジスタに設定する。なお、第２のパケットキュー部の重みカウント値は、第２のパケットキュー部内の第１のパケットキュー部の重みカウント値の総和を用いてもよいし、独立した値を設定するようにしてもよい。
つぎに、キュー制御部１３−１のキュー選択部１３１が第２のパケットキュー部を選択した時の動作を説明する。キュー制御部１３−１のキュー選択部１３１が第２のパケットキュー部１５−１を選択したとする。キュー制御部１３−１のキュー選択部１３１は、第２のパケットキュー部１５−１のカウント値レジスタ１６−０１の重みカウント値を確認する。
カウント値レジスタ１６−０１の重みカウント値が正数の場合、キュー制御部１３−１のキュー選択部１３１は、選択した第２のパケットキュー部１５−１のキュー制御部１３−０１に処理を移行する。キュー制御部１３−０１のキュー選択部１３１は、キュー制御部１３−０１のキュー選択ポインタ１３２が示す第１のパケットキュー部を選択する。ここで、キュー制御部１３−０１のキュー選択ポインタ１３２が第１のパケットキュー部１２−０１を示していたとする。キュー制御部１３−０１のキュー選択部１３１は、第１のパケットキュー部１２−０１を選択して、第１のパケットキュー部１２−０１内のカウント値レジスタ１６−１の重みカウント値を確認する。
第１のパケットキュー部１２−０１のカウント値レジスタ１６−１の重みカウント値が正数の場合、キュー制御部１３−０１のキュー選択部１３１は、第１のパケットキュー部１２−０１にパケットが蓄積されているかを確認する。第１のパケットキュー部１２−０１にパケットが蓄積されている場合、キュー選択部１３−０１の重みカウント値更新部１３３は、第１のパケットキュー部１２−０１のカウント値レジスタ１６−１の重みカウント値から、取得するパケットのパケット長に相当する重みを減算する。そして、減算した値を新たな重みカウント値として第１のパケットキュー部１２−０１のカウント値レジスタ１６−１に設定する。
キュー制御部１３−０１のキュー選択部１３１は、第１のパケットキュー部１２−０１からパケットを取得して、取得したパケットをパケット生成部１４−０１に出力するとともに、キュー制御部１３−０１のキュー選択ポインタ１３２をインクリメントして、キュー制御部１３−０１のキュー選択ポインタ１３２が示す第１のパケットキュー部を選択する。そして、キュー制御部１３−０１は、選択した第１のパケットキュー部のカウント値レジスタの重みカウント値および選択した第１のパケットキュー部のパケットの有無に基づいてパケットを取得する動作を、第１のパケットキュー部１２−０１〜１２−０ａに蓄積されているパケットがなくなるか、パケット生成部１４−０１がキュー制御部１３−０１から出力されたパケットの多重を行うことができなくなるまで繰り返す。すなわち、キュー制御部１３−０１は、キュー制御部１３−１から処理を移行されると、キュー制御部１３−０１のキュー選択ポインタ１３２が示す第１のパケットキュー部をラウンドロビンにより選択してパケットを取得し、パケット生成部１４−０１が取得したパケットを多重化して１つのパケットを生成する。そして、１つのパケットを生成すると、キュー制御部１３−０１は、キュー制御部１３−１に処理を移行する。
キュー制御部１３−１は、第２のパケットキュー部１５−０のパケット生成部１４−０１が生成したパケットを取得して、パケット生成部１４−１に出力するとともに、キュー制御部１３−１のキュー選択ポインタ１３２をインクリメントする。そして、キュー選択ポインタ１３２が示す第１のパケットキュー部または第２のパケットキュー部を選択する。
このように本実施の形態では、第１のパケット入力部が、入力されるパケットに付与されている識別子に基づいてパケットの品質クラスを識別して、品質クラス毎にｎ個の第１のパケットキュー部またはｍ個の第２のパケットキュー部に振り分ける。第１のキュー制御部は、回転優先制御によって第１または第２のパケットキュー部を選択して、選択した第１または第２のパケットキュー部内部のカウント値レジスタの重みカウント値と蓄積されたパケットの状態によってパケットを取得する。このとき、第２のパケットキュー部は、蓄積した複数のパケットを多重化して新たな１つのパケットを生成し、生成したパケットを第１のキュー制御部が取得するようにしているため、属性の異なるパケットに対して柔軟に対応することができ、特定の属性を有するパケットについては多重化して新たな１つのパケットとして扱うことができる。
また、第１のキュー選択部が、回転優先制御によって選択した第１のパケットキュー部のカウント値レジスタまたは第２のパケットキュー部の第２のカウントレジスタの重みカウント値が正数で、かつ選択した第１または第２のパケットキュー部にパケットが蓄積させている場合にパケットを取得して、第１の重みカウント値更新部が、第１のキュー選択部がパケットを取得した第１のパケットキュー部の第１のカウント値レジスタまたは第２のパケットキュー部の第２のカウント値レジスタの重みカウント値から取得したパケットのパケット長の値を減算した値を新たな重みカウント値として設定し、第１のキュー選択部がパケットを取得できなかった場合には、選択した第１または第２のパケットキュー部が蓄積することができる最大パケット長分の重みを第１または第２のカウント値レジスタの重みカウント値から減算して、減算した値を新たな重みカウント値として第１または第２のカウント値レジスタに設定するようにしているため、可変長パケットのスケジューリングにおいて余剰帯域を効率的に使用することができる。
さらに、第１の重みカウント値設定部は、各第１のパケットキュー部の第１のカウント値レジスタおよび各第２のパケットキュー部の第２のカウント値レジスタの重みカウント値毎に、品質および／または応じて変動するパケットの最大パケット長以上の値を加算して、加算した値を新たな重みカウント値として各第１および第２のカウント値レジスタに設定するようにしているため、設定の変更に対して柔軟にすることができ、帯域を効率よく使用することができる。
さらにまた、第２のパケットキュー部は、パケットを蓄積するとともに、蓄積するパケットに基づいた重みカウント値を保持する第３のカウント値レジスタを有する複数の第３のパケットキュー部と、第１のパケット入力部から入力されるパケットに付与されている識別子に基づいて入力されるパケットを複数の第３のパケットキュー部に振り分ける第２のパケット入力部と、前記複数の第３のパケットキュー部を回転優先制御に基づいて選択して、該選択した第３のパケットキュー部の第３のカウント値レジスタおよび蓄積されたパケットの状態によってパケットを取得するとともに、前記選択した第３のパケットキュー部の第３のカウント値レジスタの重みカウント値を変更する第２のキュー制御部と、この第２のキュー制御部が取得したパケットを多重化する第２のパケット生成部とを備えるようにしたため、異なる属性を有するパケットに対して多段階でのスケジューリングを実行するとともに、複数のパケットキューに跨る処理を効率よく行うことができる。
【産業上の利用可能性】  以上のように、本発明にかかるスケジューリング装置は、ＡＴＭやＩＰパケットなどの可変長のパケットを送出する順番を制御する際に有用であり、特に、入力パケットを多重して新たな１つのパケットとして送出する必要があるパケットのスケジューリングに適している。
【図１】
2005006672.tif 000003
【図２】
2005006672.tif 000004
【図３】
2005006672.tif 000005
【国際調査報告】
2005006672.tif 000006
2005006672.tif 000007