(57)【特許請求の範囲】
【請求項１】
複数の入力ポート及び出力ポートと、前記複数の入力ポートのそれぞれに対応して設けられ、対応する入力ポートに入力されたパケットが一時格納される複数のバッファと、前記バッファに格納されたパケットを前記複数の出力ポートのうち当該パケットの宛先に応じた出力ポートに出力するスイッチと、前記バッファに格納されたパケットの送出決定処理を行うスケジューラとを有し、前記バッファに格納されたパケットが前記スケジューラにおける決定に従って当該バッファから読み出されて前記スイッチに入力されるパケットスイッチにおいて、
前記複数の入力ポートにおけるパケットの到着数を監視するパケット到着監視部と、
前記パケット到着監視部にて監視されたパケットの到着数に基づいて、前記スケジューラにおける前記送出決定処理の回数を決定する処理回数決定部とを有し、
前記スケジューラは、前記処理回数決定部にて決定した回数だけ前記送出決定処理を行うことを特徴とするパケットスイッチ。
【請求項２】
複数の入力ポート及び出力ポートと、前記複数の入力ポートのそれぞれに対応して設けられ、対応する入力ポートに入力されたパケットが一時格納される複数のバッファと、前記バッファに格納されたパケットを前記複数の出力ポートのうち当該パケットの宛先に応じた出力ポートに出力するスイッチと、前記バッファに格納されたパケット送出決定処理を行うスケジューラとを有し、前記バッファに格納されたパケットが前記スケジューラにおける決定に従って当該バッファから読み出されて前記スイッチに入力されるパケットスイッチにおいて、
前記複数のバッファに格納されたパケットについて前記複数の出力ポート毎のパケットの待ちキュー状態を監視するキュー状態監視部と、
前記キュー状態監視部にて監視されたパケットの平均の待ちキュー長に基づいて、前記スケジューラにおける前記送出決定処理の回数を決定する処理回数決定部とを有し、
前記スケジューラは、前記処理回数決定部にて決定した回数だけ前記送出決定処理を行うことを特徴とするパケットスイッチ。
【請求項３】
請求項１または請求項２に記載のパケットスイッチにおいて、
前記処理回数決定部にて決定した回数に応じて前記スケジューラの動作周波数を指示する動作周波数指示部を有し、
前記スケジューラは、前記動作周波数指示部にて指示された動作周波数で動作することにより、前記処理回数決定部にて決定した回数だけ前記送出決定処理を行うパケットスイッチ。
【請求項４】
請求項１乃至３のいずれか１項に記載のパケットスイッチにおいて、
前記スケジューラは、複数の送出タイミングに関して前記送出決定処理を一括して行うパケットスイッチ。
【請求項５】
複数の入力ポート及び出力ポートと、前記複数の入力ポートのそれぞれに対応して設けられ、対応する入力ポートに入力されたパケットが一時格納される複数のバッファと、前記バッファに格納されたパケットを前記複数の出力ポートのうち当該パケットの宛先に応じた出力ポートに出力するスイッチと、前記バッファに格納されたパケットの送出決定処理を行うスケジューラとを有し、前記バッファに格納されたパケットが前記スケジューラにおける決定に従って当該バッファから読み出されて前記スイッチに入力されるパケットスイッチにおけるパケットスケジューリング方法であって、
前記複数の入力ポートにおけるパケットの到着数に基づいて、前記スケジューラにおける前記送出決定処理の回数を決定し、
前記スケジューラが、当該回数だけ前記送出決定処理を行うパケットスケジューリング方法。
【請求項６】
複数の入力ポート及び出力ポートと、前記複数の入力ポートのそれぞれに対応して設けられ、対応する入力ポートに入力されたパケットが一時格納される複数のバッファと、前記バッファに格納されたパケットを前記複数の出力ポートのうち当該パケットの宛先に応じた出力ポートに出力するスイッチと、前記バッファに格納されたパケット送出決定処理を行うスケジューラとを有し、前記バッファに格納されたパケットが前記スケジューラにおける決定に従って当該バッファから読み出されて前記スイッチに入力されるパケットスイッチにおけるパケットスケジューリング方法であって、
前記複数のバッファに格納されたパケットについての前記複数の出力ポート毎のパケットの平均の待ちキュー長に基づいて、前記スケジューラにおける前記送出決定処理の回数を決定し、
前記スケジューラが、当該回数だけ前記送出決定処理を行うパケットスケジューリング方法。
【請求項７】
請求項５または請求項６に記載のパケットスケジューリング方法において、
前記スケジューラが、前記決定した回数に応じた動作周波数で動作することにより、当該回数だけ前記送出決定処理を行うパケットスケジューリング方法。
【請求項８】
請求項５乃至７のいずれか１項に記載のパケットスケジューリング方法において、
前記スケジューラが、複数の送出タイミングに関して前記送出決定処理を一括して行うパケットスケジューリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットスイッチに関し、特に、入力バッファ型のパケットスイッチにおけるパケットスケジューリング方法に関する。
【背景技術】
【０００２】
到着したパケットを所望の方路に交換するパケットスイッチは、複数のパケットが同時に同一の方路へ出力されて衝突することを防ぐためにバッファを備えていることが多い。このようにバッファを備えたパケットスイッチは、バッファの配備位置によって共有バッファ型、出力バッファ型、入力バッファ型に分類される。共有バッファ型は、バッファメモリを複数の入出力ポート間で共有するため、バッファに用いるメモリ量を抑制することができるが、メモリアクセス速度を入力ポートのバス速度に比べて高速にする必要があり、スイッチポート数の増大をも招く。また、出力バッファ型は、同一出力先に複数のパケットが同時に到着する出力競合による遅延やパケット棄却を小さくできるとされるが、スイッチ内部のバス速度及びメモリアクセス速度を入力ポートのバス速度のポート数倍にする必要がある。これらに対し、入力バッファ型は、スイッチ内部のバス速度及びメモリアクセス速度が入力ポートのバス速度と同速度でよく、実装が容易であるという特長を有する。このため、入力バッファ型は大規模化に適するとして有望視されている。
【０００３】
ところが、入力バッファ型パケットスイッチには、各入力ポートに単一のＦＩＦＯ型バッファを用いた場合、バッファの先頭に存在するパケットが読み出されないために後続パケットの送出権が与えられないＨｏＬ（Head of Line）ブロッキングが生じるという問題があり、入力ポート数を無限大とし、パケットの到着をランダムとした場合、最大スループットは５８．６％という理論限界に制限されてしまう。この問題を解決するために、仮想出力キューイング（ＶＯＱ：Virtual Output Queuing）方式が提案されている（例えば、非特許文献１参照）。
【０００４】
ＶＯＱ方式では、各入力ポートに出力ポート数分のキューが設けられるため、ＶＯＱ方式のＮ×ＮスイッチはＮ2個のキューを有する。このＮ2個のキューから、送出契機毎に最大Ｎ個のキューに送出権を与えるためのスケジューリングによってパケットスイッチの性能が左右されるため、スケジューリングアルゴリズムの設計は重要となる。ＶＯＱ方式の入力バッファ型パケットスイッチのスケジューリングは２部グラフ上のマッチング問題に帰着でき、スケジューリングアルゴリズムは大きくラウンドロビン等を用いて繰り返し処理を行う手法「Iterative Maximal Matching」（例えば、非特許文献２，３参照）と、最大マッチング問題を解く手法「Maximum Matching」（例えば、非特許文献４参照）とに分類することができ、幾つかのアルゴリズムが考えられている。
【先行技術文献】
【特許文献】
【０００５】
【非特許文献１】T. E. Anderson, S. S. Owicki, J. B. Saxe, C. P. Thacker, “High Speed Switch Scheduling for Local Area Networks,” ACM Transactions on Computer Systems, pp.319-352, Nov. 1993.
【非特許文献２】N. McKeown, P. Varaiya, and J. Walrand, “Scheduling cells in an input-queued switch,” IEE Electronics Letters, vol. 29, no. 25, pp. 2174-2175, Dec. 1993.
【非特許文献３】H. J. Chao and J. S. Park, “Centralized contention resolution schemes for a large-capacity optical ATM switch,” Proceedings of IEEE ATM Workshop, Fairfax, VA, May 1998.
【非特許文献４】N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100% Throughput in an Input-Queued Switch,” IEEE Transactions on Communications, vol. 47, pp. 1260-1267, Aug. 1999.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、Maximum Matchingは、計算量が膨大となるため、高速性が求められる場合や大規模スイッチにおいては不適当である。また、Iterative Maximal Matchingは、与えられた時間（パケットの交換時間に依存した、ある限られた時間であり、以下、パケットサイクルと称する）内に送出パケット決定アルゴリズムを何度か繰り返す手法であり、高い性能を得るには多くの繰り返し処理が必須となるため、それに伴い処理全体に要する計算量が増加する。
【０００７】
図９は、Iterative Maximal Matchingアルゴリズムによる送出パケットの繰り返し決定処理の一例の概念を示す図であり、Iterative Maximal MatchingアルゴリズムとしてｉＳＬＩＰ（N. McKeown, “The iSLIP scheduling algorithm for Input-Queued switches,” IEEE/ACM Transactions on Networking, vol. 7, pp. 188-201, Apr. 1999.）を用いた場合の概念を示す。
【０００８】
本例では、図９に示すように、送出パケット決定処理の繰り返し回数ｉ＝４とし、２回目の処理以降では、前回までに既に送出が決定しているパケットの到着した入力ポート及び宛先となる出力ポートを除いた入出力ポート間でＳＬＩＰアルゴリズムを実行する。それにより、１度に送出されるパケット数が増加する。また、送出決定の際は、Ｎ2個のキューから最大Ｎ個が選ばれるため、入出力ポート数が大きな場合や、送出パケットの決定処理の繰り返し回数ｉを大きく設定した場合、計算コストが膨大となることは明らかである。さらに、送出パケットの決定処理の繰り返し回数ｉを大きく設定した場合、通信量（トラヒック）が少ない時に不必要な繰り返し処理によるスケジューラの計算処理の浪費を招くという問題点がある。また、送出パケットの決定処理の繰り返し回数ｉを小さく設定した場合には、トラヒックが多い時に出力性能が低いためにパケット到着数がパケット送出数を上回り、キューの使用領域（以下、待ちキュー長と称する）の増大を招き、遅延特性やパケット棄却特性が悪化するという問題点がある。
【０００９】
本発明は、上述したような技術が有する問題点に鑑みてなされたものであって、高いパケット送出性能を維持しながらも計算量を削減することができるパケットスイッチ及びパケットスケジューリング方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために本発明は、
複数の入力ポート及び出力ポートと、前記複数の入力ポートのそれぞれに対応して設けられ、対応する入力ポートに入力されたパケットが一時格納される複数のバッファと、前記バッファに格納されたパケットを前記複数の出力ポートのうち当該パケットの宛先に応じた出力ポートに出力するスイッチと、前記バッファに格納されたパケットの送出決定処理を行うスケジューラとを有し、前記バッファに格納されたパケットが前記スケジューラにおける決定に従って当該バッファから読み出されて前記スイッチに入力されるパケットスイッチにおいて、
前記複数の入力ポートにおけるパケットの到着数を監視するパケット到着監視部と、
前記パケット到着監視部にて監視されたパケットの到着数に基づいて、前記スケジューラにおける前記送出決定処理の回数を決定する処理回数決定部とを有し、
前記スケジューラは、前記処理回数決定部にて決定した回数だけ前記送出決定処理を行うことを特徴とする。
【００１１】
また、複数の入力ポート及び出力ポートと、前記複数の入力ポートのそれぞれに対応して設けられ、対応する入力ポートに入力されたパケットが一時格納される複数のバッファと、前記バッファに格納されたパケットを前記複数の出力ポートのうち当該パケットの宛先に応じた出力ポートに出力するスイッチと、前記バッファに格納されたパケット送出決定処理を行うスケジューラとを有し、前記バッファに格納されたパケットが前記スケジューラにおける決定に従って当該バッファから読み出されて前記スイッチに入力されるパケットスイッチにおいて、
前記複数のバッファに格納されたパケットについて前記複数の出力ポート毎のパケットの待ちキュー状態を監視するキュー状態監視部と、
前記キュー状態監視部にて監視されたパケットの平均の待ちキュー長に基づいて、前記スケジューラにおける前記送出決定処理の回数を決定する処理回数決定部とを有し、
前記スケジューラは、前記処理回数決定部にて決定した回数だけ前記送出決定処理を行うことを特徴とする。
【００１２】
また、複数の入力ポート及び出力ポートと、前記複数の入力ポートのそれぞれに対応して設けられ、対応する入力ポートに入力されたパケットが一時格納される複数のバッファと、前記バッファに格納されたパケットを前記複数の出力ポートのうち当該パケットの宛先に応じた出力ポートに出力するスイッチと、前記バッファに格納されたパケットの送出決定処理を行うスケジューラとを有し、前記バッファに格納されたパケットが前記スケジューラにおける決定に従って当該バッファから読み出されて前記スイッチに入力されるパケットスイッチにおけるパケットスケジューリング方法であって、
前記複数の入力ポートにおけるパケットの到着数に基づいて、前記スケジューラにおける前記送出決定処理の回数を決定し、
前記スケジューラが、当該回数だけ前記送出決定処理を行う。
【００１３】
また、複数の入力ポート及び出力ポートと、前記複数の入力ポートのそれぞれに対応して設けられ、対応する入力ポートに入力されたパケットが一時格納される複数のバッファと、前記バッファに格納されたパケットを前記複数の出力ポートのうち当該パケットの宛先に応じた出力ポートに出力するスイッチと、前記バッファに格納されたパケット送出決定処理を行うスケジューラとを有し、前記バッファに格納されたパケットが前記スケジューラにおける決定に従って当該バッファから読み出されて前記スイッチに入力されるパケットスイッチにおけるパケットスケジューリング方法であって、
前記複数のバッファに格納されたパケットについての前記複数の出力ポート毎のパケットの平均の待ちキュー長に基づいて、前記スケジューラにおける前記送出決定処理の回数を決定し、
前記スケジューラが、当該回数だけ前記送出決定処理を行う。
【発明の効果】
【００１４】
以上説明したように本発明においては、複数の入力ポートにおけるパケットの到着数や、複数のバッファに格納されたパケットについての複数の出力ポート毎のパケットの平均の待ちキュー長に基づく回数だけ、スケジューラにおいてバッファに格納されたパケットの送出決定処理を行う構成としたため、パケットの到着数が多い場合や、待ちキュー長が増大している場合は、送出決定処理を行う回数を増やしてパケット送出能力を高め、また、パケットの到着数が少ない場合や、待ちキュー長が短い場合は、送出決定処理を行う回数を減らして計算コストを低減することにより、高いパケット送出性能を維持しながらも計算量を削減することができる。これにより、トラヒック状況に応じて適応的なスケジューリングが可能となる。
【図面の簡単な説明】
【００１５】
【図１】本発明のパケットスイッチの実施の一形態を示す図である。
【図２】図１に示した仮想出力キューの構成を示す図である。
【図３】図１に示したスケジューラの構成を示す図である。
【図４】図１に示したパケットスイッチにおけるパケットスケジューリング方法の第１の実施の形態を示すタイミングチャートである。
【図５】図１に示したパケットスイッチにおけるパケットスケジューリング方法の第２の実施の形態を示すタイミングチャートである。
【図６】図１に示したパケットスイッチにおけるパケットスケジューリング方法の第３の実施の形態を示すタイミングチャートである。
【図７】図１に示したパケットスイッチにおいて送出パケット決定処理の回数が固定の場合における、２パケットサイクル一括スケジューリングの概念図である。
【図８】図１に示したパケットスイッチにおいて送出パケット決定処理の回数が可変の場合における、２パケットサイクル一括スケジューリングの概念図である。
【図９】Iterative Maximal Matchingアルゴリズムによる送出パケットの繰り返し決定処理の一例の概念を示す図である。
【発明を実施するための形態】
【００１６】
以下に、本発明の実施の形態について図面を参照して説明する。
【００１７】
図１は、本発明のパケットスイッチの実施の一形態を示す図である。
【００１８】
本形態は図１に示すように、パケットが入力される複数の入力ポート２1〜２Nと、パケットがその宛先毎に出力される複数の出力ポート９1〜９Nと、入力ポート２1〜２Nのそれぞれに対応して設けられ、入力ポート２1〜２Nに入力されたパケットが一時格納される複数のバッファ４1〜４Nと、入力ポート２1〜２Nのそれぞれに対応して設けられ、入力ポート２1〜２Nに入力されたパケットをバッファ４1〜４Nに書き込むバッファ書込部３1〜３Nと、バッファ４1〜４Nに書き込まれたパケットを読み出す書き込むバッファ読出部７1〜７Nと、バッファ４1〜４Nのそれぞれに対応して設けられ、バッファ４1〜４Nに格納されたパケットの出力ポート９1〜９N毎の待ち行列を保持する仮想出力キュー５1〜５Nと、バッファ４1〜４Nに格納されたパケットを複数の出力ポート９1〜９Nのうちそのパケットの宛先に応じた出力ポートに出力するスイッチ８と、バッファ４1〜４Nに格納されたパケットの送出決定処理を行うスケジューラ６とを有しており、バッファ４1〜４Nに格納されたパケットがスケジューラ６における決定に従ってバッファ４1〜４Nから読み出されてスイッチ８に入力されるＮ入力Ｎ出力のパケットスイッチ１である。さらに、本形態は、パケット到着監視部１０と、キュー状態監視部１１と、処理回数決定部１２と、動作周波数指示部１３とを有している。
【００１９】
パケット到着監視部１０は、入力ポート２1〜２Nにおけるパケットの到着数を監視する。
【００２０】
キュー状態監視部１１は、バッファ４1〜４Nに格納されたパケットについて仮想出力キュー５1〜５Nを参照して出力ポート９1〜９N毎のパケットの待ちキュー状態を監視する。
【００２１】
処理回数決定部１２は、パケット到着監視部１０にて監視されたパケットの到着数や、キュー状態監視部１１にて監視されたパケットの平均の待ちキュー長に基づいて、スケジューラ６におけるパケットの送出決定処理の回数を決定する。
【００２２】
動作周波数指示部１３は、処理回数決定部１２にて決定した回数に応じてスケジューラ６の動作周波数を指示する。
【００２３】
上記のように構成されたパケットスイッチ１においては、到着したパケットが入力ポート２1に入力されると、まず、入力ポート２1に入力されたパケットがバッファ書込部３1によってバッファ４1に格納される。この時、パケットが格納されるバッファ４1におけるアドレス情報を示すパケット・ポインタ（以下、ポインタと称する）が、バッファ書込部３1から仮想出力キュー５1に渡され、このポインタの情報が仮想出力キュー５1からスケジューラ６に渡される。
【００２４】
スケジューラ６においては、各仮想出力キュー５1〜５Nから渡されたポインタの情報に基づいて、送出するパケットを決定する送出決定処理が行われる。そして、入力ポート２1に入力された出力ポート９1宛のパケットの送出が決定すると、スケジューラ６からの指示によって、バッファ４1から読み出すパケットのアドレス情報を示すポインタが仮想出力キュー５1からバッファ読出部７1に渡され、バッファ読出部７1によって、仮想出力キュー５1から渡されたポインタに従ってパケットがバッファ４1から読み出され、スイッチ８及び出力ポート９1を経由して送出される。
【００２５】
また、パケット到着監視部１０においては、入力ポート２1〜２Nにおけるパケットの到着数が監視、集計されており、また、キュー状態監視部１１は、バッファ４1〜４Nに格納されたパケットについて仮想出力キュー５1〜５Nを参照して出力ポート９1〜９N毎のパケットの待ちキュー状態が監視されている。そして、パケット到着監視部１０にて監視、集計されたパケット到着数と、キュー状態監視部１１にて監視された平均待ちキュー長は、処理回数決定部１２に伝達される。処理回数決定部１２においては、パケット到着監視部１０やキュー状態監視部１１から伝達された情報に基づいて、Iterative Maximal Matchingの処理回数が決定され、スケジューラ６に渡される。また、動作周波数指示部１３においては、処理回数決定部１２にて決定した値に応じてスケジューラ６の動作周波数が指示される。
【００２６】
図２は、図１に示した仮想出力キュー５1の構成を示す図である。なお、図１に示した仮想キュー５2〜５Nの構成もこれと同様である。
【００２７】
図１に示した仮想出力キュー５1は図２に示すように、出力ポート９1〜９Nのそれぞれに対応してキュー５1−２1〜５1−２Nを具備しており、バッファ書込部３1からポインタを含むパケットに関する情報が渡されると、キュー振分・書込部５1−１において、バッファ書込部３1から渡された情報を用いてそのパケットの宛先となる出力ポートが確認され、パケットの宛先となる出力ポートに対応するキューにポインタが格納されるとともに、どのキューにポインタが格納されているかを示す格納情報がスケジューラ６に渡される。また、スケジューラ６からパケット送出の指示があると、指示を受け取ったキュー読出部５1−３において、指定されたパケットのポインタがキューから読み出され、バッファ読出部７1に渡される。
【００２８】
図３は、図１に示したスケジューラ６の構成を示す図である。
【００２９】
図１に示したスケジューラ６は図３に示すように、キュー管理部６−１と、送出パケット決定部６−２と、動作周波数変更部６−３とを有している。
【００３０】
キュー管理部６‐１は、各仮想出力キュー５1〜５Nのキュー振分・書込部５1−１〜５N−１から渡された格納情報により各仮想出力キュー５1〜５Nの状態を把握し、現状態を送出パケット決定部６−２に開示する。
【００３１】
送出パケット決定部６−２は、処理回数決定部１２によって指示された処理回数でIterative Maximal Matchingを実行し、送出するパケットを決定する。その後、送出パケット決定部６−２は、各仮想出力キュー５1〜５Nのキュー読出部５1−３〜５N−３にパケットの送出指示を出すとともに、パケットの送出情報をキュー管理部６−１に渡す。そして、それにより、キュー管理部６−１における各仮想出力キューの状態が更新される。
【００３２】
動作周波数変更部６‐３は、動作周波数指示部１３からの指示に応じて動作周波数を変更する。
【００３３】
上述したパケットスイッチ１において、状況に応じてIterative Maximal Matchingの処理回数を変化させるパケットスケジューリングを行う。以下に、上述したパケットスイッチ１におけるパケットスケジューリング方法について３つの形態を例に挙げて説明する。
【００３４】
（第１の実施の形態）
図４は、図１に示したパケットスイッチ１におけるパケットスケジューリング方法の第１の実施の形態を示すタイミングチャートである。
【００３５】
本形態においては、上記スケジューラの送出パケット決定処理回数の決定基準として、１つ前のパケットサイクルにおけるパケット到着数を用い、また、Iterative Maximal MatchingアルゴリズムにはｉＳＬＩＰを用いる。
【００３６】
パケットのポインタの仮想出力キュー５1〜５Nへの格納情報が、キュー振分・書込部５1−１〜５N−１からキュー管理部６−１に渡されると（ステップ１）、キュー管理部６−１にて管理されているキュー状態が更新され（ステップ２）、このキュー状態が送出パケット決定部６−２に通知される（ステップ３）。
【００３７】
また、パケット到着監視部１０にて監視、集計された到着パケット数が処理回数決定部１２に渡される（ステップ４）。なお、入力ポート数、パケット到着率をそれぞれ、Ｎ，Ｌとすると、あるパケットサイクルでのパケット到着数はＮ・Ｌで表される。
【００３８】
処理回数決定部１２においては、閾値α及びβ（α＜β）を設け、Ｌとこの閾値との関係によって送出パケット決定処理回数ｉが決定される（ステップ５）。なお、本形態においては、送出パケット決定処理は３回までとする。トラヒックが少なくパケット到着数が少ない場合はｉを１とし、パケット到着数が多く到着数が送出数を大きく上回る恐れがある場合にはｉを３とする。
【００３９】
決定した送出パケット決定処理回数ｉは、処理回数決定部１２から送出パケット決定部６−２に通知される（ステップ６）。
【００４０】
すると、送出パケット決定部６−２において、処理回数決定部１２から通知された処理回数だけｉＳＬＩＰが実行され（ステップ７）、パケット送出が決定した仮想出力キューの情報がキュー管理部６−１に通知され（ステップ８）、キュー管理部６−１にて管理されているキュー状態が更新される（ステップ９）。
【００４１】
また、送出パケット決定部６−２から、各仮想出力キュー５1〜５Nのキュー読出部５1−３〜５N−３にパケットの送出指示が出される（ステップ１０）。
【００４２】
このように、本形態においては、トラヒックが少なくパケット到着数が少ない場合はｉＳＬＩＰの実行回数を１回として不要な計算コストを削減し、また、パケット到着数が多く到着数が送出数を大きく上回る恐れがある場合にはｉＳＬＩＰの実行回数を３回として高い送出数を得る、パケット到着状況に応じた適応的なスケジューリングが実現できる。この場合、ｉＳＬＩＰの実行回数を１回に固定したままの手法に比べて明らかに送出性能が高く、また、ｉＳＬＩＰの実行回数を３回に固定したままの手法と比べると送出数は同程度であり、かつ低計算量なスケジューリングが実現できる。これにより、短期的なトラヒック変動に対応するスケジューリングが実現できる。
【００４３】
また、処理回数の決定は１回ないし２回のパケット到着数と閾値との比較で実現されるため、送出パケット決定処理に比べ、特にＮが大きな場合に処理量は充分少ないといえる。
【００４４】
（第２の実施の形態）
図５は、図１に示したパケットスイッチ１におけるパケットスケジューリング方法の第２の実施の形態を示すタイミングチャートである。
【００４５】
本形態においては、上記スケジューラの送出パケット決定処理回数の決定基準として、スケジューリングを行うパケットサイクルにおける仮想出力キューの待ちキュー長を用い、また、Iterative Maximal MatchingアルゴリズムにはｉＬＱＦ（N. McKeown, “Scheduling algorithms for input-queued cell switches,” Ph.D. Thesis, University of California at Berkeley, 1995.）を用いる。
【００４６】
パケットのポインタの仮想出力キュー５1〜５Nへの格納情報が、キュー振分・書込部５1−１〜５N−１からキュー管理部６−１に渡されると（ステップ２１）、キュー管理部６−１にて管理されているキュー状態が更新され（ステップ２２）、このキュー状態が送出パケット決定部６−２に通知される（ステップ２３）。
【００４７】
また、キュー状態監視部１１にて監視されている平均待ちキュー長が処理回数決定部１２に伝達されると（ステップ２４）、処理回数決定部１２において、閾値γ及びδ（γ＜δ）を設け、各仮想出力キュー５1〜５Nの平均待ちキュー長Ｑとその閾値との関係によって送出パケット決定処理回数ｉが決定される（ステップ２５）。なお、閾値は、バッファ４1〜４N及び仮想出力キュー５1〜５Nのメモリ量によって決定される。第１の実施の形態と同様に、本形態においては送出パケット決定処理は３回までとする。平均待ちキュー長Ｑが短い場合はｉを１とし、平均待ちキュー長Ｑの伸びとともにｉを増加させる。
【００４８】
決定した送出パケット決定処理回数ｉは、処理回数決定部１２から動作周波数指示部１３及び送出パケット決定部６−２に通知される（ステップ２６）。
【００４９】
すると、動作周波数指示部１３において、通知された送出パケット決定処理回数ｉに応じた動作周波数が決定され（ステップ２７）、動作周波数変更部６−３に通知される（ステップ２８）。
【００５０】
すると、動作周波数変更部６−３において、スケジューラ６における送出パケット決定処理を行うための動作周波数が、動作周波数指示部１３から通知された動作周波数に設定される（ステップ２９）。
【００５１】
また、送出パケット決定部６−２において、動作周波数変更部６−３に設定された動作周波数でｉＳＬＩＰが実行され（ステップ３０）、パケット送出が決定した仮想出力キューの情報がキュー管理部６−１に通知され（ステップ３１）、キュー管理部６−１にて管理されているキュー状態が更新される（ステップ３２）。
【００５２】
また、送出パケット決定部６−２から、各仮想出力キュー５1〜５Nのキュー読出部５1−３〜５N−３にパケットの送出指示が出される（ステップ３３）。
【００５３】
このように、本形態においては、平均待ちキュー長が短い場合はｉＳＬＩＰの実行回数を１回として不要な計算コストを削減し、平均待ちキュー長Ｑの伸びとともにｉを増加させて待ちキュー長を抑制する、キュー状態に応じた適応的なスケジューリングが実現できる。これにより長期的なトラヒック変動に対応するスケジューリングが実現できる。この場合、ｉを１に固定したままの手法に比べ明らかに待ちキュー長抑制効果が高く、また、ｉを３に固定したままの手法と比べると待ちキュー長は同程度であり、かつ低計算量なスケジューリングが実現できる。これにより、短期的なトラヒック変動に対応するスケジューリングが実現できる。
【００５４】
また、処理回数の決定は１回ないし２回の待ちキュー長と閾値との比較で実現されるため、送出パケット決定処理に比べ、特にＮが大きい場合に処理量は充分少ないといえる。
【００５５】
また、ｉが１の場合はｉ＝２，３の場合に比べて計算量が少なく、スケジューラが同一の動作周波数でスケジューリングを行った場合に計算所要時間が削減できるため、低速な動作周波数においてもパケットサイクル内に処理が完了する。スケジューラの動作に関する消費電力は動作周波数に依存するため、消費電力の低減が実現できる。
【００５６】
なお、本形態のように、スケジューラ６の動作周波数を制御することで、パケットの送出処理回数を制御することは、第１の実施の形態に示したものにも適用することができる。
【００５７】
（第３の実施の形態）
図６は、図１に示したパケットスイッチ１におけるパケットスケジューリング方法の第３の実施の形態を示すタイミングチャートである。
【００５８】
本形態においては、上記スケジューラの送出パケット決定処理回数の決定基準として、１つ前のパケットサイクルにおけるパケット到着数を用い、また、Iterative Maximal MatchingアルゴリズムにはｉＳＬＩＰを用いる。
【００５９】
パケットのポインタの仮想出力キュー５1〜５Nへの格納情報が、キュー振分・書込部５1−１〜５N−１からキュー管理部６−１に渡されると（ステップ４１）、キュー管理部６−１にて管理されているキュー状態が更新され（ステップ４２）、このキュー状態が送出パケット決定部６−２に通知される（ステップ４３）。
【００６０】
また、パケット到着監視部１０にて監視、集計された到着パケット数が処理回数決定部１２に渡される（ステップ４４）。なお、入力ポート数、パケット到着率をそれぞれ、Ｎ，Ｌとすると、あるパケットサイクルでのパケット到着数はＮ・Ｌで表される。
【００６１】
処理回数決定部１２においては、閾値α及びβ（α＜β）を設け、Ｌと閾値との関係によって、送出パケット決定処理を打ち切る閾値λ、μ、ν（λ＜μ＜ν）が決定される（ステップ４５）。
【００６２】
決定した送出パケット決定処理を打ち切る閾値Ｔｈは、処理回数決定部１２から送出パケット決定部６−２に通知される（ステップ４６）。
【００６３】
すると、送出パケット決定部６−２において、ｉＳＬＩＰが、処理回数決定部１２から通知された閾値を超える回数だけ実行され（ステップ４７，４８）、パケット送出が決定した仮想出力キューの情報がキュー管理部６−１に通知され（ステップ４９）、キュー管理部６−１にて管理されているキュー状態が更新される（ステップ５０）。
【００６４】
また、送出パケット決定部６−２において、次のサイクルのスケジューリングに移行するとともに、各仮想出力キュー５1〜５Nのキュー読出部５1−３〜５N−３にパケットの送出指示が出される（ステップ５１）。
【００６５】
本形態においては、送出パケット決定処理を打ち切る閾値の決定及び送出決定パケット数と閾値との比較の処理は数回の比較で実現されるため、送出パケット決定処理に比べ、特にＮが大きな場合に処理量は充分少ないといえる。
【００６６】
図７は、図１に示したパケットスイッチ１において送出パケット決定処理の回数が固定の場合における、２パケットサイクル一括スケジューリングの概念図である。また、図８は、図１に示したパケットスイッチ１において送出パケット決定処理の回数が可変の場合における、２パケットサイクル一括スケジューリングの概念図である。
【００６７】
図７及び図８に示すように、上述した実施の形態にて示したパケットスケジューリング方法は、２パケットサイクルにて出力される複数のパケットについて、送出パケット決定処理を一括して行う方式に活用可能であり、一定の出力数が得られると判断した時点で処理を打ち切ることでスケジューリングに要する時間を削減可能となる。また、図８に示すように、複数パケットサイクル間でのスケジューリング時間分配及び複数パケットサイクルにおける総計算時間の低減が実現できる。
【符号の説明】
【００６８】
１    パケットスイッチ
２1〜２N    入力ポート
３1〜３N    バッファ書込部
４1〜４N    バッファ
５1〜５N    仮想出力キュー
５1−１〜５N−１    キュー振分・書込部
５1−２1〜５N−２N    キュー
５1−３〜５N−３    キュー読出部
６    スケジューラ
６‐１    キュー管理部
６‐２    送出パケット決定部
６‐３    動作周波数変更部
７1〜７N    バッファ読出部
８    スイッチ
９1〜９N    出力ポート
１０    パケット到着監視部
１１    キュー状態監視部
１２    処理回数決定部
１３    動作周波数指示部
【図１】
0005615764.tif 000002
【図２】
0005615764.tif 000003
【図３】
0005615764.tif 000004
【図４】
0005615764.tif 000005
【図５】
0005615764.tif 000006
【図６】
0005615764.tif 000007
【図７】
0005615764.tif 000008
【図８】
0005615764.tif 000009
【図９】
0005615764.tif 000010