(57)【要約】【課題】  レイテンシを低減し、スループットの向上を図る。【解決手段】  キュー状態メモリ１２は、すべてのキューＱ１〜Ｑｎに対して、キューＱ１〜Ｑｎのパケット蓄積に関連する情報であるキュー状態情報を格納する。プレスケジューラ１３は、どのキューを選択して蓄積パケットを出力させるかの処理であるスケジューリングに対して、実際のスケジューリングで必要となる可能性があるキューをあらかじめ選択するプレスケジューリングを行って、選択したキューに関するキュー状態情報をキュー状態メモリ１２から読み出す。キャッシュメモリ１４は、プレスケジューラ１３で読み出されたキュー状態情報を一時格納する。スケジューラ１５は、キャッシュメモリ１４に格納されているキュー状態情報を利用してスケジューリングを行う。【選択図】  図１
2006253790.tif 000002
【特許請求の範囲】
【請求項１】
パケット伝送を行うパケット伝送装置において、
パケットを蓄積する複数のキューを含むパケットデータメモリと、
すべてのキューに対して、キューのパケット蓄積に関連する情報であるキュー状態情報を格納するキュー状態メモリと、
どのキューを選択して蓄積パケットを出力させるかの処理であるスケジューリングに対して、実際のスケジューリングで必要となる可能性があるキューをあらかじめ選択するプレスケジューリングを行って、選択したキューに関する前記キュー状態情報を前記キュー状態メモリから読み出すプレスケジューラと、
前記プレスケジューラで読み出された前記キュー状態情報を一時格納するキャッシュメモリと、
前記キャッシュメモリに格納されている前記キュー状態情報を利用してスケジューリングを行うスケジューラと、
入力パケットを前記パケットデータメモリに書き込み、前記スケジューラで選択されたキューからパケットを読み出して出力するパケット書き込み／読み出し部と、
を有することを特徴とするパケット伝送装置。
【請求項２】
前記プレスケジューラは、前記キュー状態メモリへアクセスしてキュー状態情報を取得し、取得したキュー状態情報を前記キャッシュメモリに書き込むまでに要する時間を、１回のプレスケジューリングに要する時間で割った値以上の数のキューをあらかじめ選択することを特徴とする請求項１記載のパケット伝送装置。
【請求項３】
パケット伝送を行うパケット伝送方法において、
パケットを蓄積するすべてのキューに対して、キューのパケット蓄積に関連する情報であるキュー状態情報をキュー状態メモリに格納し、
プレスケジューラは、どのキューを選択して蓄積パケットを出力させるかの処理であるスケジューリングに対して、実際のスケジューリングで必要となる可能性があるキューをあらかじめ選択するプレスケジューリングを行って、選択したキューに関する前記キュー状態情報を前記キュー状態メモリから読み出し、
キャッシュメモリは、読み出された前記キュー状態情報を一時格納し、
スケジューラは、前記キャッシュメモリに格納されている前記キュー状態情報を利用してスケジューリングを行い、
スケジューリングによって選択されたキューからパケットを読み出して出力することを特徴とするパケット伝送方法。
【請求項４】
前記プレスケジューラは、前記キュー状態メモリへアクセスしてキュー状態情報を取得し、取得したキュー状態情報を前記キャッシュメモリに書き込むまでに要する時間を、１回のプレスケジューリングに要する時間で割った値以上の数のキューをあらかじめ選択することを特徴とする請求項３記載のパケット伝送方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット伝送装置及びパケット伝送方法に関し、特にスケジューリングを行ってパケット伝送を行うパケット伝送装置及びスケジューリングを行ってパケット伝送を行うパケット伝送方法に関する。
【背景技術】
【０００２】
近年、インターネットに代表される通信ネットワークは大容量化、広域化が著しく、通信ネットワークを構成するルータ等のパケット伝送装置では、トラフィックの増加にともなうパケット転送の高速性と、様々なサービスの品質（ＱｏＳ：Quality of Service）を実現するための高品質なトラフィック制御が要求されている。
【０００３】
パケット伝送装置は、パケット転送及びトラフィック制御を行うトラフィックマネージャを有しており、トラフィックマネージャは、異なるサービスクラス毎にパケットを蓄積（エンキュー）するための複数のキューを含み、サービスにしたがったトラフィック制御を行うためにキューを選択するスケジューリングを実行する。
【０００４】
図５は従来のトラフィックマネージャの構成を示す図である。トラフィックマネージャ１００は、パケットデータメモリ１０１、パケット書き込み／読み出し部１０２、キュー状態メモリ１０３、スケジューラ１０４から構成される。
【０００５】
パケットデータメモリ１０１は、キューＱ１〜Ｑｎを含み、キューＱ１〜Ｑｎは異なるサービスクラス毎に存在してパケットを格納する。パケット書き込み／読み出し部１０２は、トラフィック優先度に対応したキューＱ１〜Ｑｎに対して、各入力パケットを格納する。また、スケジューラ１０４で選択されたキューからパケットを読み出して出力する。
【０００６】
キュー状態メモリ１０３は、キューＱ１〜Ｑｎのパケット蓄積に関するキュー状態情報を記憶する。スケジューラ１０４は、各々異なったサービスクラスを持つキューＱ１〜Ｑｎに対して、適切なトラフィック制御が行えるように、蓄積されたパケットを出力するキューの選択を行う。
【０００７】
従来のパケットスケジューリング技術としては、パケットキューをインターリーブする技術が提案されている（例えば、特許文献１）。
【特許文献１】特開平１０−０８４３８３号公報（段落番号〔００３１〕〜〔００５４〕，第１図）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
スケジューリング処理では、例えば、優先度の高いキューを選択して、高優先度のキューに格納されているパケットから順に出力するための出力キュー決定制御を行う。
図６は従来のスケジューリングからパケット出力までを示すタイムチャートである。３つのキューＱ０〜Ｑ２がある場合に、キューＱ０、Ｑ１、Ｑ２の順に優先度が高いキューであるとする。
【０００９】
〔Ｓ５１〕スケジューラ１０４は、優先度の最も高いキューＱ０を選択する。
〔Ｓ５２〕スケジューラ１０４は、キュー状態メモリ１０３にアクセスして、キューＱ０に関するキュー状態情報（パケット読み出しアドレスであるリードポインタ等を含む）を取得する。
【００１０】
〔Ｓ５３〕スケジューラ１０４は、パケット書き込み／読み出し部１０２に選択キューの指示を行う（キューＱ０に関するキュー状態情報を送信する）。
〔Ｓ５４〕パケット書き込み／読み出し部１０２は、キュー状態情報にもとづいて、キューＱ０からパケットを読み出して出力する。
【００１１】
〔Ｓ５５〕スケジューラ１０４は、キューＱ０にはパケットが現在蓄積されていないことを認識すると、優先度が２番目に高いキューＱ１を選択する。
〔Ｓ５６〕スケジューラ１０４は、キュー状態メモリ１０３にアクセスして、キューＱ１に関するキュー状態情報を取得する。
【００１２】
〔Ｓ５７〕スケジューラ１０４は、パケット書き込み／読み出し部１０２に選択キューの指示を行う（キューＱ１のキュー状態情報を送信する）。
〔Ｓ５８〕パケット書き込み／読み出し部１０２は、キュー状態情報にもとづいて、キューＱ１からパケットを読み出して出力する。
【００１３】
〔Ｓ５９〕スケジューラ１０４は、最も高優先のキューＱ０にはパケットが現在蓄積されておらず、かつキューＱ１にはまだパケットが格納されているならば、引き続きキューＱ１を選択する。
【００１４】
〔Ｓ６０〕スケジューラ１０４は、キュー状態メモリ１０３にアクセスして、キューＱ１のキュー状態情報を取得する。
〔Ｓ６１〕スケジューラ１０４は、パケット書き込み／読み出し部１０２に選択キューの指示を行う（キューＱ１のキュー状態情報を送信する）。
【００１５】
〔Ｓ６２〕パケット書き込み／読み出し部１０２は、キュー状態情報にもとづいて、キューＱ１からパケットを読み出して出力する。
〔Ｓ６３〕スケジューラ１０４は、キューＱ０、Ｑ１にパケットが現在蓄積されていなければ、優先度が３番目のキューＱ２を選択する。以降、同様な制御が続く。
【００１６】
このようなスケジューリング処理では、一度スケジューリングが開始されると、そのスケジューリングが完全に完了するまで、次のスケジューリングを開始することができない。
【００１７】
スケジューラ１０４では、“キュー選択”“キュー状態情報取得”、“選択キュー指示”といった各段階の処理からなるスケジューリングに対して、例えば、あるキューのパケット格納状態Ｓiにおけるキュー状態情報の取得を行いながら、並列して次のパケット格納状態Ｓi+1におけるキュー選択を行うといったことはできない。
【００１８】
すなわち、スケジューリング処理の性質から、前の処理が終わる前に次の処理を開始するパイプライン処理のような並列処理は実行することはできず、スケジューリング処理＃１（“キュー選択”、“キュー状態情報取得”、“選択キュー指示”からなる処理）→スケジューリング処理＃２（“キュー選択”、“キュー状態情報取得”、“選択キュー指示”からなる処理）→・・・というように、前のスケジューリング処理が完全に終わってから、次のスケジューリング処理を開始することになる。
【００１９】
一方、上記のトラフィックマネージャ１００においては、キューＱ１〜Ｑｎの管理及びスケジューリングに必要な情報としては、例えば、キューＱ１〜Ｑｎに蓄積されているパケット数を示すキューカウント、キューＱ１〜Ｑｎへエンキューするときにパケットデータを書き込むアドレスを示すライトポインタ、キューＱ１〜Ｑｎからデキュー（読み出す）するときにパケットデータを読み出すアドレスを示すリードポインタ等があり、これらはキュー状態情報として、キュー状態メモリ１０３で格納管理される。
【００２０】
これらの情報はキュー毎に必要なため、キューＱ１〜Ｑｎの数によっては、キュー状態情報は膨大な量になるので、内部メモリ（小容量で高速なメモリ）に保持することは困難であり、通常は、低速であるが大容量の外部メモリをキュー状態メモリ１０３に使用している。
【００２１】
スケジューリングは、上述のようにパイプライン処理ができないために、従来では１回のスケジューリング処理を行う毎に、外部メモリ（キュー状態メモリ１０３）にアクセスしてキュー状態情報を読み出して、適切なキューからパケットを出力させるといった動作を行うことになる。
【００２２】
このため、従来のスケジューリングでは、キュー状態メモリ１０３に対するレイテンシ（latency：データのリクエストを行ってから、実際にデータが転送されるまでにかかる遅延時間）が増大し、１回のスケジューリング間隔も長くなり、スループットが低下するといった問題があった。
【００２３】
本発明はこのような点に鑑みてなされたものであり、効率よくスケジューリングを行ってレイテンシを低減し、スループットの向上を図ったパケット伝送装置を提供することを目的とする。
【００２４】
また、本発明の他の目的は、効率よくスケジューリングを行ってレイテンシを低減し、スループットの向上を図ったパケット伝送方法を提供することである。
【課題を解決するための手段】
【００２５】
本発明では上記課題を解決するために、図１に示すような、パケット伝送を行うパケット伝送装置１０において、パケットを蓄積する複数のキューＱ１〜Ｑｎを含むパケットデータメモリ１１と、すべてのキューＱ１〜Ｑｎに対して、キューＱ１〜Ｑｎのパケット蓄積に関連する情報であるキュー状態情報を格納するキュー状態メモリ１２と、どのキューを選択して蓄積パケットを出力させるかの処理であるスケジューリングに対して、実際のスケジューリングで必要となる可能性があるキューをあらかじめ選択するプレスケジューリングを行って、選択したキューに関するキュー状態情報をキュー状態メモリ１２から読み出すプレスケジューラ１３と、プレスケジューラ１３で読み出されたキュー状態情報を一時格納するキャッシュメモリ１４と、キャッシュメモリ１４に格納されているキュー状態情報を利用してスケジューリングを行うスケジューラ１５と、入力パケットをパケットデータメモリ１１に書き込み、スケジューラ１５で選択されたキューからパケットを読み出して出力するパケット書き込み／読み出し部１６と、を有することを特徴とするパケット伝送装置１０が提供される。
【００２６】
ここで、パケットデータメモリ１１は、パケットを蓄積する複数のキューＱ１〜Ｑｎを含む。キュー状態メモリ１２は、すべてのキューＱ１〜Ｑｎに対して、キューＱ１〜Ｑｎのパケット蓄積に関連する情報であるキュー状態情報を格納する。プレスケジューラ１３は、どのキューを選択して蓄積パケットを出力させるかの処理であるスケジューリングに対して、実際のスケジューリングで必要となる可能性があるキューをあらかじめ選択するプレスケジューリングを行って、選択したキューに関するキュー状態情報をキュー状態メモリ１２から読み出す。キャッシュメモリ１４は、プレスケジューラ１３で読み出されたキュー状態情報を一時格納する。スケジューラ１５は、キャッシュメモリ１４に格納されているキュー状態情報を利用してスケジューリングを行う。パケット書き込み／読み出し部１６は、入力パケットをパケットデータメモリ１１に書き込み、スケジューラ１５で選択されたキューからパケットを読み出して出力する。
【発明の効果】
【００２７】
本発明のパケット伝送装置は、実際のスケジューリングで必要となる可能性があるキューをあらかじめ選択するプレスケジューリングを行って、選択したキューに関するキュー状態情報をキュー状態メモリから読み出してキャッシュメモリに格納し、キャッシュメモリに格納されているキュー状態情報を利用してスケジューリングを行う構成とした。これにより、効率よくスケジューリングを行ってレイテンシを低減することができ、スループットの向上を図ることが可能になる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明の実施の形態を図面を参照して説明する。図１はパケット伝送装置の原理図である。パケット伝送装置１０は、パケットデータメモリ１１、キュー状態メモリ１２、キューベクタ１２ａ、プレスケジューラ１３、キャッシュメモリ１４、スケジューラ１５、パケット書き込み／読み出し部１６から構成される。
【００２９】
パケットデータメモリ１１は、パケットを蓄積する複数のキューＱ１〜Ｑｎを含む。キュー状態メモリ１２は、すべてのキューＱ１〜Ｑｎに対して、キューＱ１〜Ｑｎのパケット蓄積に関連する情報であるキュー状態情報を格納する。キューベクタ１２ａは、該当キューにパケットが存在しているか否かの状態を示す。
【００３０】
プレスケジューラ１３は、どのキューを選択して蓄積パケットを出力させるかの処理であるスケジューリングに対して、実際のスケジューリングで必要となる可能性があるキューをあらかじめ選択するプレスケジューリングを行う。そして、選択したキューに関するキュー状態情報をキュー状態メモリ１２から読み出す。
【００３１】
キャッシュメモリ１４は、プレスケジューラ１３で読み出されたキュー状態情報を一時格納する。スケジューラ１５は、各々異なったサービスクラスを持つキューに対して適切なトラフィック制御が行えるように、キャッシュメモリ１４に格納されているキュー状態情報を利用してスケジューリングを行う（すなわち、キューの選択制御を行う）。
【００３２】
パケット書き込み／読み出し部１６は、入力パケットをパケットデータメモリ１１に書き込み（適切なキューにエンキューする）、スケジューラ１５で選択されたキューからパケットを読み出して出力する（該当キューからデキューする）。
【００３３】
プレスケジューラ１３とキャッシュメモリ１４の構成を持つことに特徴を有するパケット伝送装置１０は、実際のスケジューリングを行う前のフェーズ（プレスケジューリングフェーズ）において、実際のスケジューリングで必要となる可能性があるキューをいくつか選択しておく（プレスケジューリング）。このプレスケジューリングでは、実際のスケジューリングのように厳密なスケジューリングを行う必要がない。
【００３４】
また、そのキュー状態情報（以下、キューディスクリプタと呼ぶ）を外部メモリ（キュー状態メモリ１２）から内部メモリ（キャッシュメモリ１４）へ読み出す処理（キャッシュ）を行う。そして、次のフェーズ（スケジューリングフェーズ）では、プレスケジューリングで内部メモリにキャッシュされて得られた情報で、実際のスケジューリングを行う。
【００３５】
このようにプレスケジューリングを行って、実際のスケジューリングで選択される可能性の高いキューに関するキューディスクリプタをあらかじめ選択して、高速メモリであるキャッシュメモリ１４にそのキューディスクリプタを格納しておき、スケジューラ１５は、キャッシュメモリ１４にアクセスしてスケジューリングを行うことで、従来のようにスケジューリングの度に、アクセス時間がかかる外部メモリにアクセスする必要がなくなるので、レイテンシを低減して処理能力の向上を図ることが可能になる。
【００３６】
図２はメモリの内部状態を示す図である。キュー状態メモリ１２（以下、キューディスクリプタメモリ１２と呼ぶ）、キューベクタ１２ａ、キャッシュメモリ１４の内部状態の具体例を示している。
【００３７】
キューベクタ１２ａは、キューにパケットが存在しているか否かの状態を保持する各キュー毎に１ビットで示される内部レジスタである（“１”でパケットあり、“０”でパケットなしとする）。
【００３８】
キューディスクリプタメモリ１２は、キュー番号、キューカウント、ライトポインタ、リードポインタからなるキューディスクリプタの格納管理を行う（すべてのキューＱ１〜Ｑｎに関するキューディスクリプタを格納する）。
【００３９】
なお、キューカウントとは、該当キューに存在するパケットデータの個数である（所定のキューにパケットが格納されるとインクリメントする）。ライトポインタは、次にパケットデータを書き込む際の該当キューに対する書き込みアドレスを示す。リードポインタは、次にパケットデータを読み出す際の該当キューに対する読み出しアドレスを示す。
【００４０】
キャッシュメモリ１４は、プレスケジューラ１３でキャッシュされたキューディスクリプタのみ格納する。図２の例では、プレスケジューラ１３は、実際のスケジューリングで選択される可能性の高いキューとして、キューＱ０、Ｑ２、Ｑ４、Ｑ５を選択し（優先度の高いキューから先に選択する）、これらのキューに関するキューディスクリプタを格納している（エントリ番号０〜３として４つをエントリしている）。
【００４１】
ここで、プレスケジューラ１３におけるキュー選択について説明する。図３はプレスケジューラ１３によるキュー選択を説明するための図である。
プレスケジューラ１３が例えば、キューＱ０を選択して、キューＱ０のキューディスクリプタをキューディスクリプタメモリ１２から読み出し、キャッシュメモリ１４に書き込むとする。スケジューラ１５によるキューＱ０のスケジューリングは、キューＱ０のキューディスクリプタがキャッシュメモリ１４に書き込まれた時点で開始可能である。
【００４２】
したがって、プレスケジューラ１３が、キューディスクリプタメモリ１２へアクセスして１つのキューディスクリプタを取得し、取得したキューディスクリプタをキャッシュメモリ１４に書き込むまでに要する時間をＴ１とし、１回のプレスケジューリングに要する時間をＴ２とすれば、Ｔ１をＴ２で割った値Ａ（小数点切り上げ）以上の数のキューをあらかじめ選択すればよい（メモリアクセス時間Ｔ１を埋められるだけのキューを選択する）。もし、Ａより小さい整数値の数だけキューを選択すると、無駄な空き時間が生じることになる。
【００４３】
例えば、図の場合、Ｔ１／Ｔ２≒４となったら、プレスケジューリングとして、４つのキューを選択することになる（図の例では、キューＱ０の他にキューＱ２、Ｑ４、Ｑ５を選択している）。もし、この場合に２つのキューＱ０、Ｑ２しか選択しなければ、無駄な空き時間（＝Ｔ２×２）が生じることになる。なお、キャッシュメモリ１４は、プレスケジューラ１３で選択されるキューの数以上のキューディスクリプタを格納できる領域があればよい。
【００４４】
次にプレスケジューリング及びスケジューリングの動作について説明する。図４はプレスケジューリング／スケジューリングの動作を示すタイムチャートである。図２に示したキューディスクリプタの値にもとづくタイムチャートを示している。
【００４５】
プレスケジューリングとスケジューリングは図に示すように、それぞれの動作を交互に行う。なお、プレスケジューラ１３が動作している期間はプレスケジューリングフェーズ、スケジューラ１５が動作している期間はスケジューリングフェーズであり、ステップＳ１〜Ｓ６までがプレスケジューリングフェーズ、ステップＳ７〜Ｓ１０までがスケジューリングフェーズの動作である。
【００４６】
〔Ｓ１〕プレスケジューラ１３は、次にスケジュールされる可能性のあるキューを選択する。優先制御を行う場合には、キューにパケットが存在していて、最も優先順位の高いキューＱ０を選択する。
【００４７】
〔Ｓ２〕プレスケジューラ１３は、後段のスケジューラ１５で必要となるキューディスクリプタをキャッシュメモリ１４に保存するため、キューディスクリプタメモリ１２からキューＱ０に関するキューディスクリプタを読み出す。
【００４８】
ここで、キャッシュメモリ１４のエントリにキューＱ０のタグがすでに存在する場合は（キャッシュヒット）、キューディスクリプタメモリ１２から読み出す必要はない。キャッシュメモリ１４にキューＱ０のタグがない場合は、キューディスクリプタメモリ１２から読み出すことになるが、このとき、キャッシュメモリ１４に空きのエントリがない場合は、最も古いエントリの内容をキューディスクリプタメモリ１２に書き戻し（ライトバック）、そのエントリ領域をキューＱ０で使用する。
【００４９】
〔Ｓ３〕キューディスクリプタメモリ１２から読み出したキューＱ０に関するキューディスクリプタをキャッシュメモリ１４に格納する。
〔Ｓ４〕プレスケジューラ１３は、その次にスケジューリングされる可能性のある他のキューＱ２（２番目に優先度が高いキュー）を選択する。
【００５０】
ここで、実際のスケジューリングでは優先度の高いキューにパケットが複数蓄積されていた場合は、続けて同一のキューが選択されるが、プレスケジューラ１３は、この時点ではまだキューディスクリプタメモリ１２に保存されているキューディスクリプタの読みだし処理中であるので、キューカウントがどのように変化しているかわからない。
【００５１】
そこで、プレスケジューラ１３は、スケジューラ１５で選択される可能性のあるキューをすべてキャッシュできるように、この例では優先度が２番目のキューＱ２を選択し、そのキューＱ２のキューディスクリプタをキューディスクリプタメモリ１２から読み出す（すなわち、プレスケジューリングでキューＱ２を選択しても、そのときにキューＱ０にパケットが入力して蓄積されたら、スケジューリングではキューＱ０を選択するので、プレスケジューリングでキューＱ２を選択したことは無駄になるが、プレスケジューリングでキューＱ２を選択した時点では、キューＱ０にあらたにパケットが蓄積したことはわからないので、スケジューラ１５で選択される可能性のあるキューを優先度にしたがって順にすべて選択するということ）。
【００５２】
〔Ｓ５〕キューディスクリプタメモリ１２から読み出したキューＱ２に関するキューディスクリプタをキャッシュメモリ１４に格納する。
〔Ｓ６〕同様に、プレスケジューラはキューＱ４、Ｑ５を選択し、それらのキューディスクリプタをキューディスクリプタメモリ１２から読み出し、キャッシュメモリ１４に格納する。
【００５３】
〔Ｓ７〕スケジューラ１５は、キャッシュメモリ１４に保持されたキューディスクリプタを利用して本来のスケジューリングを行う。この場合、最も優先度の高いキューＱ０を選択し、キャッシュメモリ１４からキューＱ０のキューディスクリプタを読み出して、パケット書き込み／読み出し部１６へ通知する。
【００５４】
パケット書き込み／読み出し部１６は、パケットデータメモリ１１に対して、キャッシュメモリ１４に保持されたキューＱ０のキューディスクリプタのリードポインタによってパケットデータを読み出してデキューする。また、スケジューラ１５は、キャッシュメモリ１４のキューカウントを更新する。さらに、スケジューラ１５は、キューＱ０には、パケットが存在しないので、キューベクタ１２ａの該当ビットを０にして更新する。
【００５５】
〔Ｓ８〕次のスケジューリングでは前回のスケジューリングでキューＱ０が空きになったため、その次に優先度の高いキューＱ２が選択され、前述のスケジューラと同様の処理を行う。
【００５６】
ただし、キャッシュメモリ１４のキューＱ２のエントリに保持されているキューカウントから、このキューにはまだパケットが蓄積されていることがわかるので、キューベクタ１２ａの更新は行わない。
【００５７】
〔Ｓ９〕次のスケジューリングでは、前回のスケジューリングでキューＱ２がまだ空きでないため、同じキューＱ２を選択する。これは、プレスケジューリングの選択順序とは異なるが、同じキュー番号であるため、キャッシュされたキューディスクリプタを利用することができる。このスケジューリングでキューＱ２は空きとなる。
【００５８】
〔Ｓ１０〕次のスケジューリングでは、キューＱ４を選択し、同様の制御を行う。
なお、上記の動作では、プレスケジューリングフェーズではキューＱ５も選択し、キャッシュしていたが、スケジューリングフェーズでは使用しなかった。このようにプレスケジューリングで選択したキューのすべてが実際のスケジューリングで使用されるとは限らないが、その逆のプレスケジューリングで選択されなかったキューが実際のスケジューリングで選択される（キャッシュのミスヒット）ことはない。
【００５９】
以上説明したように、プレスケジューリングを実施しておくことにより、実際のスケジューリング処理で必要となる外部メモリ上の情報を内部メモリへキャッシュしておき、実際のスケジューリング処理では内部メモリ上の情報のみで処理を行うことで、スループットの向上を図ることが可能になる。
【００６０】
なお、上記の説明では、キャッシュされたキューディスクリプタを外部メモリに書き戻すのにライトバック方式を用いているが、他の方式（例えばライトスルー方式）であってもよい。また、優先度によるスケジューリングを例に示したが、DRR（Deficit Round Robbin）などの他のスケジューリング方式であってもよい。
【図面の簡単な説明】
【００６１】
【図１】パケット伝送装置の原理図である。
【図２】メモリの内部状態を示す図である。
【図３】プレスケジューラによるキュー選択を説明するための図である。
【図４】プレスケジューリング／スケジューリングの動作を示すタイムチャートである。
【図５】従来のトラフィックマネージャの構成を示す図である。
【図６】従来のスケジューリングからパケット出力までを示すタイムチャートである。
【符号の説明】
【００６２】
１０  パケット伝送装置
１１  パケットデータメモリ
１２  キュー状態メモリ
１２ａ  キューベクタ
１３  プレスケジューラ
１４  キャッシュメモリ
１５  スケジューラ
１６  パケット書き込み／読み出し部
Ｑ１〜Ｑｎ  キュー
【図１】
2006253790.tif 000003
【図２】
2006253790.tif 000004
【図３】
2006253790.tif 000005
【図４】
2006253790.tif 000006
【図５】
2006253790.tif 000007
【図６】
2006253790.tif 000008