(57)【要約】【課題】入出力回線の回線数または入出力回線の回線速度が増加しても、スイッチのスループットが低下することのないスケジューラ装置を提供する。【解決手段】出力スケジューラ部１１−１、・・・、１１−Ｎは、クロスバースイッチ部２の入力となる入力回線を出力回線毎に１つ選択する。入力スケジューラ部１２−１、・・・、１２−Ｎは前記の選択結果で入力回線が重複した場合に出力回線を入力回線毎に１つ選択し、重複のため選択されなかった出力回線に対応する出力スケジューラ部にキャンセル情報を出力する。出力スケジューラ部はキャンセル情報が入力されたとき、キャンセル情報を出力した入力スケジューラ部に対応する入力回線のリクエストカウンタをカウントアップする。【選択図】図２
2007259073.tif 000002
【特許請求の範囲】
【請求項１】
出力回線ごとに設けられた出力スケジューラ部であって、複数の入力バッファ部から要求されるクロスバースイッチ部の接続設定のスケジューリングリクエストを入力バッファ部毎、すなわち入力回線毎にカウントするリクエストカウンタと、ラウンドロビン規則の最優先回線を示す、入力回線を１つ選択するためのグラントポインタと、前記リクエストカウンタを参照し、当該出力回線のリクエストが存在する入力回線から、前記グラントポインタが指す入力回線を最優先としラウンドロビン規則に従い入力回線を選択する出力スケジューラ制御手段とを含む出力スケジューラ部と、
入力回線ごとに設けられた入力スケジューラ部であって、前記出力スケジューラ部で選択された入力回線をグラントとして前記出力回線毎に保持するグラントレジスタと、ラウンドロビン規則の最優先回線を示す、出力回線を１つ選択するためのアクセプトポインタと、前記グラントレジスタを参照し、当該入力回線がグラントである出力回線から、前記アクセプトポインタが示す出力回線を最優先としラウンドロビン規則に従い出力回線を選択する入力スケジューラ部制御手段とを含む入力スケジューラ部と
を有し、
前記入力スケジューラ部制御手段は、出力回線を選択した時に、当該入力回線がグラントであっても選択されなかった出力回線に対応する前記出力スケジューラ部にキャンセル情報を出力する、
パケットスイッチにおけるスケジューリング装置。
【請求項２】
前記出力スケジューラ部制御手段は、前記入力スケジューラ部制御手段から前記キャンセル情報が入力されたとき、該キャンセル情報を前記入力バッファ部から入力される新規リクエストと同様にリクエストとして判断して、前記キャンセル情報を出力した前記入力スケジューラ部制御手段に対応する入力回線に対応するリクエストカウンタの値を更新し、また選択された入力回線に対応するリクエストカウンタをデクリメントする、請求項１に記載のパケットスイッチにおけるスケジューリング装置。
【請求項３】
前記出力スケジューラ部制御手段は、入力回線を選択した時に、前記グラントポインタが、選択された入力回線の次の入力回線を指すように前記グラントポインタを更新する、請求項１または２に記載のパケットスイッチにおけるスケジューリング装置。
【請求項４】
前記出力スケジューラ部におけるリクエストのカウント処理および入力回線の選択処理と、前記入力スケジューラ部における出力回線の選択処理が互いに独立して行われる、請求項１から３のいずれかに記載のパケットスイッチにおけるスケジューリング装置。
【請求項５】
入力回線ごとに設けられた入力スケジューラ部であって、複数の入力バッファ部から要求されるクロスバースイッチ部の接続設定のスケジューリングリクエストを出力回線毎にカウントするリクエストカウンタと、ラウンドロビン規則の最優先回線を示す、出力回線を１つ選択するためのグラントポインタと、前記リクエストカウンタを参照し、当該入力回線からのリクエストが存在する出力回線から、前記グラントポインタが指す出力回線を最優先としラウンドロビン規則に従い出力回線を選択する入力スケジューラ部制御手段とを含む入力スケジューラ部と、
出力回線ごとに設けられた出力スケジューラ部であって、前記入力スケジューラ部で選択された出力回線をグラントとして入力回線毎に保持するグラントレジスタと、ラウンドロビン規則の最優先回線を示す、入力回線を１つ選択するためのアクセプトポインタと、前記グラントレジスタを参照し、当該出力回線がグラントである入力回線から、前記アクセプトポインタが指す入力回線を最優先としラウンドロビン規則に従い入力回線を選択する出力スケジューラ部制御手段とを含む出力スケジューラ部と
を有し、
前記出力スケジューラ部制御手段は、入力回線を選択した時に、当該出力回線がグラントであっても選択されなかった入力回線に対応する前記入力スケジューラ部にキャンセル情報を出力する、
パケットスイッチにおけるスケジューリング装置。
【請求項６】
前記入力スケジューラ部制御手段は、前記出力スケジューラ部制御手段から前記キャンセル情報が入力されたとき、該キャンセル情報を前記入力バッファ部から入力される新規リクエストと同様にリクエストとして判断して、前記キャンセル情報を出力した前記出力スケジューラ部制御手段に対応する入力回線に対応するリクエストカウンタの値を更新し、また選択された出力回線に対応するリクエストカウンタをデクリメントする、請求項５に記載のパケットスイッチにおけるスケジューリング装置。
【請求項７】
前記入力スケジューラ部制御手段は、出力回線を選択した時に、前記グラントポインタが選択された出力回線の次の出力回線を指すように、前記グラントポインタを更新する、請求項５または６にパケットスイッチにおけるスケジューリング装置。
【請求項８】
前記入力スケジューラ部におけるリクエストのカウント処理および出力回線の選択処理と、前記出力スケジューラ部における入力回線の選択処理が互いに独立して行われる、請求項５から７のいずれかに記載のパケットスイッチにおけるスケジューリング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はパケット通信装置に関し、特に可変長パケットをスイッチングする可変長パケット通信装置に関する。
【背景技術】
【０００２】
近年インターネットの普及、アクセス回線の高速化によりデータトラフィックが急激に増大している。このトラフィックの急激な増大に対応するために、通信路の高速化、ルータを始めとする通信装置の高速・大容量化が望まれている。
【０００３】
一般に、パケットスイッチを実現するバッファは、出力バッファ型、共有バッファ型、クロスポイントバッファ型、入力バッファ型に分類される。スループットの観点から、従来は出力バッファ型や共有バッファ型のパケットスイッチが用いられてきた。しかしながら、近年では回線速度が高速化し、回線数も増加しており、メモリアクセス速度が比較的低速な入力バッファ型のパケットスイッチが見直されている。例えば、出力バッファ型のパケットスイッチのメモリアクセス速度は、回線速度のＮ＋１倍（Ｎは回線数）となる。共通バッファ型のパケットスイッチのメモリアクセス速度は、回線速度の２Ｎ倍となる。これに対して、入力バッファ型のメモリアクセス速度は回線速度の２倍であって、出力バッファ型や共通バッファ型の各パケットスイッチのメモリアクセス速度に比べて低速である。
【０００４】
入力バッファ型のパケットスイッチでは、一般にＨＯＬ（Head of Line）ブロッキングにより、スループットが５８．６％に低下することが知られているが、入力バッファにおけるＦＩＦＯ（First In First Out）を出力回線毎に論理的に分割してＶＯＱ（Virtual Output Queue）を構成することにより、１００％のスループットが得られることが知られている。また、クロスポイントバッファ型のパケットスイッチは、メモリアクセス速度やスループットについては入力バッファ型のパケットスイッチと同等の特性を有するが、各クロスポイント毎にバッファが必要になるため、入力回線数と出力回線数をともにＮとした場合には、Ｎ×Ｎ個のバッファが必要になり、ハードウエア規模が大きくなってしまう。
【０００５】
図１は、一般的な入力バッファ型パケットスイッチの構成を示す図である。図１に示すように、入力バッファ型パケットスイッチは、Ｎ個の入力バッファ部１−１、・・・、１−Ｎと、スケジューラ部３と、クロスバースイッチ部２と、Ｎ個の出力バッファ部４−１、・・・、４−Ｎで構成される。スケジューラ部３はスーリングアルゴリズムとして非特許文献１で提案されているｉＳＬＩＰを用いている。
【０００６】
入力バッファ部１−１、・・・、１−Ｎは、Ｎ本の入力回線＃１〜＃Ｎのそれぞれに対応して設けられており、対応する入力回線から入力された可変長フレームを固定長パケットに分割して格納する。各入力バッファ部１−１、・・・、１−Ｎは入力処理部５−１、・・・、５−Ｎとパケットバッファ６−１、・・・、６−ＮとＶＯＱ管理部７−１、・・・、７−Ｎで構成されている。入力処理部５−１、・・・、５−Ｎは、対応する入力回線から入力される可変長フレームを、１個あるいは複数個の固定長パケットに分割する。パケットバッファ６−１、・・・、６−ＮはそれぞれＮ個のキューを有しており、これらのキューはそれぞれ出力回線＃１〜＃Ｎに対応した論理キューＶＯＱ（Virtual Output Queue）＃１〜＃Ｎであり、それぞれの出力回線が出力先として指定されたパケットが格納される。ＶＯＱ管理部７−１、・・・、７−Ｎは、それぞれのＶＯＱに蓄積されている固定長パケットの数を監視し、スケジューラ部３にスケジューリング要求ＲＥＱ（REQuest）を出力し、スケジューラ部３からのスケジューリング結果ＡＣＣ（ACCept）に含まれる出力回線に対応したＶＯＱから１つの固定長パケットを読み出し、クロスバースイッチ部２へ出力する。
【０００７】
スケジューラ部３は、各入力バッファ部１−１、・・・、１−ＮのＶＯＱ管理部７−１、・・・、７−Ｎから通知されるスケジューリング要求に基づいて、入力バッファ部１−１、・・・、１−Ｎから出力バッファ部４−１、・・・、４−Ｎへパケットを転送するために使用するクロスバースイッチのタイムスロットの競合制御を行う。具体的には、スケジューラ部３は、各タイムスロットでの入力回線と出力回線の接続が重複しないように、Ｎ個の入力バッファ部１−１、・・・、１−Ｎのそれぞれについて許可する出力回線を決定する処理を行う。スケジューリング結果は各入力バッファ部１−１、・・・、１−Ｎとクロスバースイッチ部２に通知される。
【０００８】
クロスバースイッチ部２は、スケジューリング結果に基づいてタイムスロット毎に入力ポートと出力ポートの接続を変更し、各入力バッファ部１−１、・・・、１−Ｎから読み出された固定長パケットをスケジューリング結果で指定された出力バッファ部へ転送する。
【０００９】
出力バッファ部４−１、・・・、４−Ｎは、Ｎ本の出力回線＃１〜＃Ｎのそれぞれに対応して設けられており、Ｎ個のキュー８−１、・・・、８−Ｎと出力処理部９-１、・・・、９−ＮとＶＩＱ管理部１０−１、・・・、１０−Ｎを有している。Ｎ個のキュー８−１、・・・、８−Ｎはそれぞれ入力回線＃１〜＃Ｎに対応した論理キューＶＩＱ（Virtual Input Queue）＃１〜＃Ｎであり、それぞれの入力回線が送信元であるパケットが格納される。クロスバースイッチ部２から各出力バッファ部４−１、・・・、４−Ｎに入力されるパケットは、入力バッファ部１で固定長パケットに変換され、各入力回線の固定長パケットが多重されて入力される。出力処理部９-１、・・・、９−Ｎでは、可変長フレームを構成する複数個の固定長パケットを、到着したものから順に、ＶＩＱから１フレーム分まとめて読み出し、元の可変長フレームを生成し、各出力回線へ出力する。
【００１０】
図１２はスケジューラ部３の従来の詳細な構成を示す図である。図１２に示すように、スケジューラ部３は、Ｎ個の出力スケジューラ部３１−１、・・・、３１−ＮとＮ個の入力スケジューラ部３２−１、・・・、３２−Ｎから構成される。
【００１１】
出力スケジューラ部３１−１は、全ての入力回線＃１〜＃Ｎから出力回線＃１へのリクエストを入力回線毎にカウントするリクエストカウンタ３３−１−１、・・・、３３−１−Ｎと、ラウンドロビン（回転優先）規則の先頭を示すグラントポインタｇ１（３４−１）と、リクエストカウンタ３３−１−１、・・・、３３−１−Ｎとグラントポインタｇ１（３４−１）に対する制御等を行う制御部３７−１で構成される。出力スケジューラ部３１−２、・・・、３１−Ｎは、全ての入力回線＃１〜＃Ｎから該当する出力回線へのリクエストを入力回線毎にカウントするリクエストカウンタ３３−２−１、・・・、３３−Ｎ−Ｎと、ラウンドロビン（回転優先）規則の先頭を示すグラントポインタｇ２〜ｇＮ（３４−２、・・・、３４−Ｎ）と、リクエストカウンタ３３−２−１、・・・、３３−Ｎ−Ｎとグラントポインタｇ２〜ｇＮ（３４−２、・・・、３４−Ｎ）に対する制御等を行う制御部３７−２、・・・、３７−Ｎで構成される。
【００１２】
入力スケジューラ部３２−１は、全ての出力スケジューラ部３１−１、・・・、３１−Ｎの選択結果から入力回線＃１に対するグラント（grant：許可）を抽出し、出力回線毎に保持するグラントレジスタ３５−１−１、・・・、３５−１−Ｎと、ラウンドロビン（回転優先）規則の先頭を示すアクセプトポインタａ１（３６−１）と、グラントレジスタ３５−１−１、・・・、３５−１−Ｎとアクセプトポインタａ１（３６−１）に対する制御等を行う制御部３８−１で構成される。入力スケジューラ部３２−２、・・・、３２−Ｎは、全ての出力スケジューラ部３１−２、・・・、３１−Ｎでの選択結果を受信するグラントレジスタ３５−２−１、・・・、３５−Ｎ−Ｎと、ラウンドロビン規則の先頭を示すアクセプトポインタａ２〜ａＮ（３６−２、・・・、３６−Ｎ）と、グラントレジスタ３５−２−２、・・・、３５−Ｎ−Ｎとアクセプトポインタａ２〜ａＮ（３６−２、・・・、３６−Ｎ）に対する制御等を行う制御部３８−２、・・・、３８−Ｎで構成される。
【００１３】
出力スケジューラ部３１−１の制御部３７−１は、全ての入力回線＃１〜＃ＮのＶＯＱ管理部７−１、・・・、7−Ｎから入力されるスケジューリング要求から宛先が出力回線＃１であるリクエストを抽出し、入力回線毎のリクエストをリクエストカウンタ３３−１−１、・・・、３３−１−Ｎでカウントする。また、入力スケジューラ部３２−１、・・・、３２−Ｎから入力されるキャンセル情報から宛先が出力回線＃１であるキャンセルを抽出し、入力回線毎のリクエストカウンタ３３−１−１、・・・、３３−１−Ｎをカウントアップする。リクエストカウンタ３３−１−１、・・・、３３−１−Ｎでカウント値が１以上であるものから１つを、グラントポインタｇ１（３４−１）を最優先としてラウンドロビン規則に則り選択し、選択された入力回線をグラントとして入力スケジューラ部に出力する。入力スケジューラ部から入力されるスケジューリング結果に応じて、リクエストカウンタとグラントポインタｇ１（３４−１）を更新する。選択された入力回線のリクエストカウンタをデクリメント（−１）し、グラントポインタｇ１（３４−１）を選択された入力回線の次を示す値に更新する。例えば、選択された入力回線が＃１の場合は＃２に、選択された入力回線が＃Ｎの場合は＃１にグラントポインタｇ１（３４−１）を更新する。
【００１４】
出力スケジューラ部３１−２の制御部３７−２は、全ての入力回線＃１〜＃ＮのＶＯＱ管理部７−１〜7−Ｎから入力されるスケジューリング要求から宛先が出力回線＃２であるリクエストを抽出し、入力回線毎のリクエストをリクエストカウンタ３３−２−１、・・・、３３−２−Ｎでカウントする。また、入力スケジューラ部３２−１、・・・、３２−Ｎから入力されるキャンセル情報から宛先が出力回線＃２であるキャンセルを抽出し、入力回線毎のリクエストカウンタ３３−２−１、・・・、３３−２−Ｎをカウントアップする。リクエストカウンタ３３−２−１、・・・、３３−２−Ｎでカウント値が１以上であるものから１つを、グラントポインタｇ２（３４−２）を最優先としてラウンドロビン規則に則り選択し、選択された入力回線をグラントとして入力スケジューラ部３２に出力する。入力スケジューラ部３２から入力されるスケジューリング結果に応じて、リクエストカウンタとグラントポインタｇ２（３４−２）を更新する。選択された入力回線のリクエストカウンタをデクリメント（−１）し、グラントポインタｇ２（３４−２）を選択された入力回線の次を示す値に更新する。例えば、選択された入力回線が＃１の場合は＃２に、選択された入力回線が＃Ｎの場合は＃１にグラントポインタｇ２（３４−２）を更新する。
【００１５】
出力スケジューラ部３１−３、・・・、３１−Ｎの制御部３７−２、・・・、３７−Ｎも出力スケジューラ部３１−１の制御部３７−１、出力スケジューラ部３１−２の制御部３７−２と同様の制御を行う。
【００１６】
入力スケジューラ部３２−１の制御部３８−１は、全ての出力スケジューラ部３１−１、・・・、３１−Ｎから入力されるグラントから送信元が入力回線＃１であるグラントを抽出し、出力回線毎のグラントレジスタ３５−１−１、・・・、３５−１−Ｎに格納する。該当するグラントがない場合は、グラントレジスタをクリア（グラントなし）する。グラントレジスタにグラントが含まれているものから１つを、アクセプトポインタａ１（３６−１）を最優先としてラウンドロビン規則に則り選択する。選択された出力回線の番号をスケジューリング結果として入力バッファ部＃１のＶＯＱ管理部７−１に出力し、アクセプトポインタａ１（３６−１）を選択された出力回線の次を示す値に更新する。例えば、選択された出力回線が＃１の場合は＃２に、選択された出力回線が＃Ｎの場合は＃１にアクセプトポインタａ１（３６−１）を更新する。全てのグラントレジスタ３５−１−１、・・・、３５−１−Ｎがグラント情報なしの場合、スケジューリング結果は未接続として出力し、アクセプトポインタａ１（３６−１）は前値保持とする。
【００１７】
入力スケジューラ部３２−２の制御部３８−２は、全ての出力スケジューラ部３１−１、・・・、３１−Ｎから入力されるグラントから送信元が入力回線＃２であるグラントを抽出し、出力回線毎のグラントレジスタ３５−２−１、・・・、３５−２−Ｎに格納する。該当するグラントがない場合は、グラントレジスタをクリア（グラントなし）する。グラントレジスタにグラントが含まれているものから１つを、アクセプトポインタａ２（３６−２）を最優先としてラウンドロビン規則に則り選択する。選択された出力回線の番号をスケジューリング結果として入力バッファ部＃２のＶＯＱ管理部７−２に出力し、アクセプトポインタａ２（３６−２）を選択された出力回線の次を示す値に更新する。全てのグラントレジスタ３５−２−１、・・・、３５−２−Ｎがグラント情報なしの場合、スケジューリング結果は未接続として出力し、アクセプトポインタａ２（３６−２）は前値保持とする。
【００１８】
入力スケジューラ部３２−３、・・・、３２−Ｎの制御部３８−２、・・・、３８−Ｎも入力スケジューラ部３２−１の制御部３８−１、入力スケジューラ部３２−２の制御部３８−２と同様の制御を行う。
【００１９】
以上説明した出力スケジューラ部３１−１〜３１−Ｎと入力スケジューラ部３２−１〜３２−Ｎは互いに連携して動作し、両者の処理は同一のタイムスロットで行われる。
【００２０】
図１３は図１２のスケジューラ部の処理のシーケンスを示したものである。入力スケジューリング処理（ステップ３）の結果をリクエストのカウント処理（ステップ１）においてリクエストカウンタに、出力スケジューリング処理（ステップ２）においてグラントポインタに反映させた後、次の処理を開始する必要があるため、図１３（ａ）に示すように、３つの処理はシリアルに行なわれる。なお、ｉＳＬＩＰを用いた従来の入力バッファ型パケットスイッチでは、図１３（ｂ）に示すように、スイッチの利用効率を上げるために３つの処理を行った後に選択されていない入力回線と出力回線の間で出力スケジューリング処理、入力スケジューリング処理を複数回さらに行う場合もある。
【００２１】
図１４は以上説明した、リクエストのカウント処理（ステップ１）、出力スケジューリング処理（ステップ２）、入力スケジューリング処理（ステップ３）のフローチャートである。図１４において、「ｚｍｏｄＮ」はｚをＮで割った余りを示す。
【００２２】
次に、図１２のスケジューラ部の動作を図１２および図１４〜図１７を参照して、入出力回線の数Ｎが４の場合について説明する。
【００２３】
まず、出力スケジューラ部３１−１〜３１−４は、ステップ１として、入力バッファ部１−１、・・・、１−４から出力バッファ部４−１、・・・、４−４へのスケジューリング要求をそれぞれカウントする（図１５）。図１５を参照すると、図１５の（ａ）はステップ１の処理を行う前のリクエストカウンタ３３−１−１、・・・、３３−４−４の値を表し、図１５の（ｂ）は各入力バッファ部１−１、・・・、１−４から入力される新規のスケジューリング要求ＲＥＱ＃１、…、ＲＥＱ＃４を表し、図１５の（ｃ）はステップ１の処理を実施後のリクエストカウンタ３３−１−１、・・・、３３−４−４の値を表している。入力回線＃１から出力回線＃１に着目し、リクエストカウンタの値（図１５の（ａ）の１行１列目）１と、リクエストの値（図１５の（ｂ）の１行１列目）１とを加算し、リクエストカウンタの値（図１５の（ｃ）の１行１列目）を２に更新する。入力回線＃１から出力回線＃２に着目し、リクエストカウンタの値（図１５の（ａ）の１行２列目）０と、リクエストの値（図１５の（ｂ）の１行２列目）０とを加算し、リクエストカウンタの値（図１５の（ｃ）の１行２列目）を０に更新する。以下、全ての入力回線と出力回線の組合せに着目し、リクエストカウンタの値を更新する。
【００２４】
次に、出力スケジューラ部３１−１、・・・、３１−４は、ステップ２として、宛先が出力回線＃１、・・・、＃４であるリクエストの中から出力回線毎に１つラウンドロビン規則に従い選択する（図１６）。図１６の（ａ）はステップ２の処理前の各入力回線から各出力回線へのリクエストの有無とグラントポインタを表し、図１６の（ｂ）はステップ２の処理後の各出力回線へのリクエストの選択結果とグラントポインタを表し、図１６の（ｃ）はステップ２の処理後の各出力スケジューラ部３１−１、・・・、３１−４から出力されるグラントを表している。出力スケジューラ部３１−１は、グラントポインタｇ１（３４−１）が示している入力回線＃１からリクエストカウンタの値が１以上である入力回線を探索すると、入力回線＃１からのリクエストカウンタが２なので、入力回線＃１を出力回線＃１へ出力可能な候補として選択する。入力スケジューラ部３２−１に出力するグラントを有効’１’とし（図１６の（ｃ）の１行１列目）、入力スケジューラ部３２−２、３２−３、３２−４に出力するグラントを無効’０’とする（図１６の（ｃ）の２行１列目、３行１列目、４行１列目）。出力スケジューラ部３１−２は、グラントポインタｇ２（３４−２）が示している入力回線＃２からリクエストカウンタの値が１以上である入力回線を探索すると、入力回線＃２からのリクエストカウンタが２なので、入力回線＃２を出力回線＃２へ出力可能な候補として選択する。入力スケジューラ部３２−２に出力するグラントを有効’１’とし（図１６の（ｃ）の２行２列目）、入力スケジューラ部３２−１、３２−３、３２−４に出力するグラントを無効’０’とする（図１６の（ｃ）の１行２列目、３行２列目、４行２列目）。出力スケジューラ部３１−３は、グラントポインタ３４−３が示している入力回線＃３からリクエストカウンタの値が１以上である入力回線を探索すると、入力回線＃３からのリクエストカウンタが２なので、入力回線＃３を出力回線＃３へ出力可能な候補として選択する。入力スケジューラ部３２−３に出力するグラントを有効’１’とし（図１６の（ｃ）の３行３列目）、入力スケジューラ部３２−１、３２−２、３２−４に出力するグラントを無効’０’とする（図１６の（ｃ）の１行３列目、２行３列目、４行３列目）。出力スケジューラ部３１−４は、グラントポインタ３４−４が示している入力回線＃４からリクエストカウンタの値が１以上である入力回線を探索すると、入力回線＃４からのリクエストカウンタが０なので、入力回線＃４は出力可能な候補とできず、ラウンドロビン規則に従い入力回線＃１からのリクエストカウンタの値を参照すると値は１なので、入力回線＃１を出力回線＃４へ出力可能な候補として選択する。入力スケジューラ部３２−１に出力するグラントを有効’１’とし（図１６の（ｃ）の１行４列目）、入力スケジューラ部３２−２、３２−３、３２−４に出力するグラントを無効’０’とする（図１６の（ｃ）の２行４列目、３行４列目、４行４列目）。
【００２５】
次に、入力スケジューラ部３２−１、・・・、３２−４は、ステップ３として、出力スケジューラ部３１−１、・・・、３１−４から入力される有効なグラントの中から入力回線毎に１つラウンドロビン規則に従い選択する（図１７）。図１７の（ａ）はステップ３の処理前の各入力回線から各出力回線への有効なグラントとアクセプトポインタを表し、図１７の（ｂ）はステップ３の処理後のグラントの選択結果とグラントポインタとアクセプトポインタを表し、図１７の（ｃ）はステップ３の処理後のリクエストカウンタの値を表し、図１７の（ｄ）はステップ３の処理後のスケジューリング結果を表している。入力スケジューラ部３２−１は、グラントレジスタ３５−１−１、・・・、３５−１−４で出力スケジューラ部３１−１、・・・、３１−４から入力されるグラントを出力スケジューラ部毎に受け取る。そして、アクセプトポインタａ１（３６−１）が示している出力回線＃２に対するグラントレジスタ３５−１−２を参照すると無効’０’なので、ラウンドロビン規則に従って次の出力回線＃３に対するグラントレジスタ３５−１−３を参照すると無効なので、さらに次の出力回線＃４に対するグラントレジスタ３５−１−４を参照すると有効’１’なので、出力回線＃４を出力可能な回線として選択する。そして、アクセプトポインタａ１の値をラウンドロビン規則に従って出力回線＃１に更新する。さらに、入力バッファ部１−１に出力するスケジューリング結果ＡＣＣ＃１を出力回線＃４のみ有効’１’とし（図１７の（ｄ）の１行４列目）、出力回線＃１、＃２、＃３は無効’０’とする（図１７の（ｄ）の１行１列目、１行２列目、１行３列目）。入力スケジューラ部３２−２は、グラントレジスタ３５−２−１、・・・３５−２−４で出力スケジューラ部３１−１、・・・、３１−４から入力されるグラントを出力スケジューラ部毎に受け取る。そして、アクセプトポインタａ２（３６−２）が示している出力回線＃１に対するグラントレジスタ３５−２−１を参照すると無効’０’なので、ラウンドロビン規則に従って次の出力回線＃２に対するグラントレジスタ３５−２−２を参照すると有効’１’なので、出力回線＃２を出力可能な回線として選択する。そして、アクセプトポインタａ２の値をラウンドロビン規則に従って出力回線＃３に更新する。さらに、入力バッファ部１−２に出力するスケジューリング結果ＡＣＣ＃２を出力回線＃２のみ有効’１’とし（図１７の（ｄ）の２行２列目）、出力回線＃１、＃３、＃４は無効’０’とする（図１７の（ｄ）の２行１列目、２行３列目、２行４列目）。入力スケジューラ部３２−３は、グラントレジスタ３５−３−１、・・・、３５−３−４で出力スケジューラ部３１−１、・・・、３１−４から入力されるグラントを出力スケジューラ部毎に受け取る。そして、アクセプトポインタａ３（３６−３）が示している出力回線＃１に対するグラントレジスタ３５−３−１を参照すると無効’０’なので、ラウンドロビン規則に従って次の出力回線＃２に対するグラントレジスタ３５−３−２を参照すると無効’０’なので、さらに次の出力回線＃３に対するグラントレジスタ３５−３−３を参照すると有効’１’なので、出力回線＃３を出力可能な回線として選択する。そして、アクセプトポインタａ３の値をラウンドロビン規則に従って出力回線＃４に更新する。さらに、入力バッファ部１−３に出力するスケジューリング結果ＡＣＣ＃３を出力回線＃３のみ有効’１’とし（図１７の（ｄ）の３行３列目）、出力回線＃１、＃２、＃４は無効’０’とする（図１７の（ｄ）の３行１列目、３行２列目、３行４列目）。入力スケジューラ部３２−４は、グラントレジスタ３５−４−１、・・・、３５−４−４で出力スケジューラ部３１−１、・・・、３１−４から入力されるグラントを出力スケジューラ部毎に受け取る。そして、アクセプトポインタａ４（３６−４）が示している出力回線＃３に対するグラントレジスタ３５−４−３を参照すると無効’０’なので、ラウンドロビン規則に従って出力回線＃４、＃１、＃２に対するグラントレジスタ３５−４−４、３５−４−１、３５−４−２を参照すると全て無効’０’なので、出力可能な回線は無いと、判断する。そして、アクセプトポインタａ４の値は前値保持とする。さらに、入力バッファ部１−４に出力するスケジューリング結果ＡＣＣ＃４は全ての出力回線＃１、…、＃４で無効’０’とする（図１７の（ｄ）の４行目）。さらに、全てのスケジューリング結果は出力スケジューラ部にも通知され、リクエストカウンタとグラントポインタの更新が行われる。出力スケジューラ部３１−１は、出力回線＃１が宛てのリクエストが選択されていないので、グラントポインタｇ１、リクエストカウンタは前値保持する。出力スケジューラ部３１−２は、入力回線＃２から出力回線＃２へのリクエストが選択されているので、グラントポインタｇ２を入力回線＃３に更新し、入力回線＃２から出力回線＃２へのリクエストカウンタをデクリメントし、０に更新する（図１７の（ｃ）の２行２列目）。出力スケジューラ部３１−３は、入力回線＃３から出力回線＃３へのリクエストが選択されているので、グラントポインタｇ３を入力回線＃４に更新し、入力回線＃３から出力回線＃３へのリクエストカウンタをデクリメントし、１に更新する（図１７の（ｃ）の３行３列目）。出力スケジューラ部３１−４は、入力回線＃１から出力回線＃４へのリクエストが選択されているので、グラントポインタｇ４を入力回線＃２に更新し、入力回線＃１から出力回線＃４へのリクエストカウンタをデクリメントし、０に更新する（図１７の（ｃ）の１行４列目）。
【非特許文献１】"The iSLIP Scheduling Algorithm for Input-Queued Switches", Nick McKeown, IEEE Transactions on Networking, Vol 7, No.2, April 1999, pp. 188-201
【発明の開示】
【発明が解決しようとする課題】
【００２６】
上述した従来のスケジューラは、入出力回線の回線数の増加または入出力回線の回線速度の増加により、スケジューラの演算速度が低下し、スイッチのスループットが低下するという問題がある。その理由は、入出力回線数が増加すると、スケジューラの計算量が著しく増加し、１タイムスロット以内で演算処理を完了することが困難となるためである。また、入出力回線速度が増加すると、１タイムスロットの時間が短くなり、１タイムスロット以内で演算処理を完了することが困難となることも理由である。
【００２７】
本発明の目的は、パケットスイッチにおいて入出力間接続スケジュールを高速に確立できる、パケットスイッチにおけるスケジューリング装置を提供することにある。
【課題を解決するための手段】
【００２８】
上述した目的を達成するために、本発明のパケットスイッチにおけるスケジューリング装置は、
出力回線ごとに設けられた出力スケジューラ部であって、複数の入力バッファ部から要求されるクロスバースイッチ部の接続設定のスケジューリングリクエストを入力バッファ部毎、すなわち入力回線毎にカウントするリクエストカウンタと、ラウンドロビン規則の最優先回線を示す、入力回線を１つ選択するためのグラントポインタと、リクエストカウンタを参照し、当該出力回線のリクエストが存在する入力回線から、グラントポインタが指す入力回線を選択する出力スケジューラ制御手段とを含む出力スケジューラ部と、
入力回線ごとに設けられた入力スケジューラ部であって、出力スケジューラ部で選択された入力回線をグラントとして出力回線毎に保持するグラントレジスタと、ラウンドロビン規則の最優先回線を示す、出力回線を１つ選択するためのアクセプトポインタと、グラントレジスタを参照し、当該入力回線がグラントである出力回線から、アクセプトポインタが示す出力回線を選択する入力スケジューラ部制御手段とを含む入力スケジューラ部と
を有し、
入力スケジューラ部制御手段は、出力回線を選択した時に、当該入力回線がグラントであっても選択されなかった出力回線に対応する出力スケジューラ部にキャンセル情報を出力する。
【００２９】
また、本発明の他のパケットスイッチにおけるスケジューリング装置は、
入力回線ごとに設けられた入力スケジューラ部であって、複数の入力バッファ部から要求されるクロスバースイッチ部の接続設定のスケジューリングリクエストを出力回線毎にカウントするリクエストカウンタと、ラウンドロビン規則の最優先回線を示す、出力回線を１つ選択するためのグラントポインタと、リクエストカウンタを参照し、当該入力回線からのリクエストが存在する出力回線から、グラントポインタが指す出力回線を選択する入力スケジューラ部制御手段とを含む入力スケジューラ部と、
出力回線ごとに設けられた出力スケジューラ部であって、入力スケジューラ部で選択された出力回線をグラントとして入力回線毎に保持するグラントレジスタと、ラウンドロビン規則の最優先回線を示す、入力回線を１つ選択するためのアクセプトポインタと、グラントレジスタを参照し、当該出力回線がグラントである入力回線から、前記アクセプトポインタが指す入力回線を選択する出力スケジューラ部制御手段とを含む出力スケジューラ部と
を有し、
出力スケジューラ部制御手段は、入力回線を選択した時に、当該出力回線がグラントであっても選択されなかった入力回線に対応する入力スケジューラ部にキャンセル情報を出力する。
【００３０】
このような構成により出力スケジューラ部の処理と入力スケジューラ部の処理を分割することにより、１タイムスロットでの演算量を削減し、それぞれの処理を独立に行うことが可能となり、本発明の目的を達成することができる。
【発明の効果】
【００３１】
第１の効果は、スケジューリング判断を高速にできることにある。その理由は、スケジューリング処理をリクエストカウント処理と出力スケジューリング処理と入力スケジューリング処理に分割し、それぞれを異なるタイムスロットで動作させることにより、それぞれの処理の演算量が削減できるためである。
【００３２】
第２の効果は、スケジューリング処理を分散化できることにある。その理由は、リクエストカウント処理と出力スケジューリング処理と入力スケジューリング処理は入力回線単位または出力回線単位に行うので入力バッファ部にスケジューリング機能を分散することができるためである。
【発明を実施するための最良の形態】
【００３３】
次に、本発明の実施の形態について図面を参照して詳細に説明する。
【００３４】
[第１の実施形態]
図２は本発明の第１の実施形態によるスケジューラ（図１のパケットスイッチのスケジューラ部３）の構成を示す図である。図２に示すように、スケジューラ部３は、Ｎ個の出力スケジューラ部１１−１、・・・、１１−ＮとＮ個の入力スケジューラ部１２−１、・・・、１２−Ｎから構成される。
【００３５】
出力スケジューラ部１１−１は、全ての入力回線＃１〜＃Ｎから出力回線＃１へのリクエストを入力回線毎にカウントするリクエストカウンタ１３−１−１、・・・、１３−１−Ｎと、ラウンドロビン（回転優先）規則の先頭を示すグラントポインタｇ１（１４−１）と、リクエストカウンタ１３−１−１、・・・、１３−１−Ｎとグラントポインタｇ１（１４−１）に対する制御等を行う制御部１７−１で構成される。出力スケジューラ部１１−２、・・・、１１−Ｎは、全ての入力回線＃１〜＃Ｎから該当する出力回線へのリクエストを入力回線毎にカウントするリクエストカウンタ１３−２−１、・・・、１３−Ｎ−Ｎと、ラウンドロビン（回転優先）規則の先頭を示すグラントポインタｇ２〜ｇＮ(１４−２、・・・、１４−Ｎ)と、リクエストカウンタ１３−２−１、・・・、１３−Ｎ−Ｎとグラントポインタｇ２〜ｇＮ(１４−２、・・・、１４−Ｎ)に対する制御等を行う制御部１７−２、・・・、１７−Ｎで構成される。入力スケジューラ部１２−１は、全ての出力スケジューラ部１１−１、・・・、１１−Ｎの選択結果から入力回線＃１に対するグラントを抽出し、出力回線毎に保持するグラントレジスタＧＳ（１５−１−１、・・・１５−１−Ｎ）と、ラウンドロビン（回転優先）規則の先頭を示すアクセプトポインタａ１（１６−１）と、グラントレジスタＧＳ（１５−１−１、・・・、１５−１−Ｎ）とアクセプトポインタａ１（１６−１）に対する制御等を行う制御部１８−１で構成される。入力スケジューラ部１２−２、・・・、１２−Ｎは、全ての出力スケジューラ部１１−１、・・・、１１−Ｎでの選択結果を受信するグラントレジスタＧＳ（１５−２−１、・・・、１５−Ｎ−Ｎ）と、ラウンドロビン規則の先頭を示すアクセプトポインタａ２〜ａＮ（１６−２、・・・、１６−Ｎ）と、グラントレジスタＧＳ（１５−２−１、・・・、１５−Ｎ−Ｎ）とアクセプトポインタａ２〜ａＮ（１６−２、・・・、１６−Ｎ）に対する制御等を行う制御部１８−２、・・・、１８−Ｎで構成される。
【００３６】
出力スケジューラ部１１−１の制御部１７−１は、全ての入力回線＃１〜＃ＮのＶＯＱ管理部から入力されるスケジューリング要求から宛先が出力回線＃１であるリクエストを抽出し、入力回線毎のリクエストをリクエストカウンタ１３−１−１、・・・、１３−１−Ｎでカウントする。また、入力スケジューラ部１５−１、・・・、１５−Ｎから入力されるキャンセル情報から宛先が出力回線＃１であるキャンセルを抽出し、入力回線毎のリクエストカウンタ１３−１−１、・・・、１３−１−Ｎをカウントアップする。リクエストカウンタ１３−１−１、・・・、１３−１−Ｎでカウント値が１以上であるものから１つを、グラントポインタｇ１（１４−１）を最優先としてラウンドロビン規則に則り選択し、選択された入力回線のリクエストカウンタをデクリメント（−１）する。選択された入力回線の番号をグラントとして入力スケジューラ部１２−１、・・・、１２−Ｎに出力し、グラントポインタｇ１（１４−１）を選択された入力回線の次を示す値に更新する。例えば、選択された入力回線が＃１の場合は＃２に、選択された入力回線が＃Ｎの場合は＃１にグラントポインタｇ１（１４−１）を更新する。
【００３７】
出力スケジューラ部１１−２の制御部１７−２は、全ての入力回線＃１〜＃ＮのＶＯＱ管理部から入力されるスケジューリング要求から宛先が出力回線＃２であるリクエストを抽出し、入力回線毎のリクエストをリクエストカウンタ１３−２−１、・・・、１３−２−Ｎでカウントする。また、入力スケジューラ部から入力されるキャンセル情報から宛先が出力回線＃２であるキャンセルを抽出し、入力回線毎のリクエストカウンタ１３−２−１、・・・、１３−２−Ｎをカウントアップする。リクエストカウンタ１３−２−１、・・・、１３−２−Ｎでカウント値が１以上であるものから１つを、グラントポインタｇ２（１４−２）を最優先としてラウンドロビン規則に則り選択し、選択された入力回線のリクエストカウンタをデクリメント（−１）する。選択された入力回線の番号をグラントとして入力スケジューラ部に出力し、グラントポインタｇ２（１４−２）を選択された入力回線の次を示す値に更新する。
【００３８】
出力スケジューラ部１１−３、・・・、１１−Ｎの制御部１７−３、・・・、１７−Ｎも出力スケジューラ部１１−１の制御部１７−１、出力スケジューラ部１１−２の制御部１７−２と同様の制御を行う。
【００３９】
入力スケジューラ部１２−１の制御部１８−１は、全ての出力スケジューラ部１１−１、・・・、１１−Ｎから入力されるグラントから送信元が入力回線＃１であるグラントを抽出し、出力回線毎のグラントレジスタ１５−１−１、・・・、１５−１−Ｎに格納する。該当するグラントがない場合は、グラントレジスタをクリア（グラントなし）する。グラントレジスタ１５−１−１、・・・、１５−１−Ｎにグラントが含まれているものから１つを、アクセプトポインタａ１（１６−１）を最優先としてラウンドロビン規則に則り選択する。選択された出力回線の番号をスケジューリング結果として入力バッファ部＃１のＶＯＱ管理部に出力し、アクセプトポインタａ１（１６−１）を選択された出力回線の次を示す値に更新する。例えば、選択された出力回線が＃１の場合は＃２に、選択された出力回線が＃Ｎの場合は＃１にアクセプトポインタａ１（１６−１）を更新する。全てのグラントレジスタがグラント情報なしの場合、スケジューリング結果は未接続として出力し、アクセプトポインタａ１（１６−１）は前値保持とする。また、グラントレジスタにグラントが含まれているが前記の選択処理で選択されなかったものは、キャンセル情報として該当する出力スケジューラ部に出力する。
【００４０】
入力スケジューラ部１２−２の制御部１８−２は、全ての出力スケジューラ部１１−１、・・・、１１−Ｎから入力されるグラントから送信元が入力回線＃２であるグラントを抽出し、出力回線毎のグラントレジスタ１５−２−１、・・・、１５−２−Ｎに格納する。該当するグラントがない場合は、グラントレジスタをクリア（グラントなし）する。グラントレジスタ１５−２−１、・・・、１５−２−Ｎにグラントが含まれているものから１つを、アクセプトポインタａ２（１６−２）を最優先としてラウンドロビン規則に則り選択する。選択された出力回線の番号をスケジューリング結果として入力バッファ部＃２のＶＯＱ管理部に出力し、アクセプトポインタａ２（１６−２）を選択された出力回線の次を示す値に更新する。全てのグラントレジスタがグラント情報なしの場合、スケジューリング結果は未接続として出力し、アクセプトポインタａ２（１６−２）は前値保持とする。また、グラントレジスタにグラントが含まれているが前記の選択処理で選択されなかったものは、キャンセル情報として該当する出力スケジューラ部に出力する。
【００４１】
入力スケジューラ部１２−３、・・・、２１−Ｎの制御部１８−２、・・・、１８−Ｎも入スケジューラ部１２−１の制御部１８−１、入力スケジューラ部１２−２の制御部１８−２と同様の制御を行う。
【００４２】
以上説明した出力スケジューラ部１１−１、・・・、１１−Ｎと入力スケジューラ部１２−１、・・・、１２−Ｎはそれぞれ独立に動作し、リクエストのカウント処理（ステップ１）、出力スケジューリング処理（ステップ２）、入力スケジューリング処理（ステップ３）のそれぞれは、図３に示すように、１タイムスロットに１回行われる。
【００４３】
図４はリクエストのカウント処理（ステップ１）、出力スケジューリング処理（ステップ２）、入力スケジューリング処理（ステップ３）のフローチャートである。
【００４４】
次に、本実施の形態のスケジューラ部の動作を図２および図５〜図７を参照して、入出力回線の数Ｎが４の場合について説明する。
【００４５】
まず、出力スケジューラ部１１−１、・・・、１１−４は、ステップ１として、入力バッファ部１−１、・・・、１−４から出力バッファ部４−１、・・・、４−４へのスケジューリング要求をそれぞれカウントする（図５）。図５を参照すると、リクエストカウンタ（図５の（ａ））はステップ１の処理を行う前のリクエストカウンタ１３−１−１、・・・、１３−４−４の値を表し、リクエスト（図５の（ｂ））は各入力バッファ部１−１、・・・、１−４から入力される新規のスケジューリング要求ＲＥＱ＃１、…、ＲＥＱ＃４を表し、キャンセルは（図５の（ｃ））は入力スケジューラ部１２−１、・・・、１２−４から入力されるキャンセル情報ＣＡＮ＃１、…、ＣＡＮ＃４を表し、リクエストカウンタ（図５の（ｄ））はステップ１の処理を実施後のリクエストカウンタ１３−１−１、・・・、１３−４−４の値を表している。入力回線＃１から出力回線＃１に着目し、リクエストカウンタの値（図５の（ａ）の１行１列目）１と、リクエストの値（図５の（ｂ）の１行１列目）１と、キャンセルの値（図５の（ｃ）の１行１列目）０とを加算し、リクエストカウンタの値（図５の（ｄ）の１行１列目）を２に更新する。入力回線＃１から出力回線＃２に着目し、リクエストカウンタの値（図５の（ａ）の１行２列目）０と、リクエストの値（図５の（ｂ）の１行２列目）０と、キャンセルの値（図５の（ｃ）の１行２列目）０とを加算し、リクエストカウンタの値（図５の（ｄ）の１行２列目）を０に更新する。以下、全ての入力回線と出力回線の組合せに着目し、リクエストカウンタの値を更新する。
【００４６】
次に、出力スケジューラ部１１−１、・・・、１１−４は、ステップ２として、宛先が出力回線＃１、・・・、＃４であるリクエストの中から出力回線毎に一つラウンドロビン規則に従い選択する（図６）。図６の（ａ）はステップ２の処理前の各入力回線から各出力回線へのリクエストの有無とグラントポインタを表し、図６の（ｂ）はステップ２の処理後の各出力回線へのリクエストの選択結果とグラントポインタを表し、図６の（ｃ）はステップ２の処理後のリクエストカウンタの値を表し、図６の（ｄ）はステップ２の処理後の各出力スケジューラ部１１−１、・・・、１１−４から出力されるグラントを表している。出力スケジューラ部１１−１は、グラントポインタｇ１（１４−１）が示している入力回線＃１からリクエストカウンタの値が１以上である入力回線を探索すると、入力回線＃１からのリクエストカウンタが２なので、入力回線＃１を出力回線＃１へ出力可能な候補として選択する。そして、グラントポインタの値をラウンドロビン規則に従って入力回線＃２に更新し、選択した入力回線＃１からのリクエストカウンタ１３−１−１の値をデクリメント（−１）して１（図６の（ｃ）の１行１列目）に更新する。さらに、入力スケジューラ部１２−１に出力するグラントを有効’１’とし（図６の（ｄ）の１行１列目）、入力スケジューラ部１２−２、１２−３、１２−４に出力するグラントを無効’０’とする（図６の（ｄ）の２行１列目、３行１列目、４行１列目）。出力スケジューラ部１１−２は、グラントポインタｇ２（１４−２）が示している入力回線＃２からリクエストカウンタの値が１以上である入力回線を探索すると、入力回線＃２からのリクエストカウンタが２なので、入力回線＃２を出力回線＃２へ出力可能な候補として選択する。そして、グラントポインタの値をラウンドロビン規則に従って入力回線＃３に更新し、選択した入力回線＃２からのリクエストカウンタ１３−１−２の値をデクリメントして１（図６の（ｃ）の２行２列目）に更新する。さらに、入力スケジューラ部１２−２に出力するグラントを有効’１’とし（図６の（ｄ）の２行２列目）、入力スケジューラ部１２−１、１２−３、１２−４に出力するグラントを無効’０’とする（図６の（ｄ）の１行２列目、３行２列目、４行２列目）。
【００４７】
出力スケジューラ部１１−３は、グラントポインタｇ３（１４−３）が示している入力回線＃３からリクエストカウンタの値が１以上である入力回線を探索すると、入力回線＃３からのリクエストカウンタが２なので、入力回線＃３を出力回線＃３へ出力可能な候補として選択する。そして、グラントポインタの値をラウンドロビン規則に従って入力回線＃４に更新し、選択した入力回線＃３からのリクエストカウンタ１３−１−３の値をデクリメントして、１（図６の（ｃ）の２行２列目）に更新する。さらに、入力スケジューラ部１２−３に出力するグラントを有効’１’とし（図６の（ｃ）の３行３列目）、入力スケジューラ部１２−１、１２−２、１２−４に出力するグラントを無効’０’とする（図６の（ｄ）の１行３列目、２行３列目、４行３列目）。出力スケジューラ部１１−４は、グラントポインタｇ４（１４−４）が示している入力回線＃４からリクエストカウンタの値が１以上である入力回線を探索すると、入力回線＃４からのリクエストカウンタが０なので、入力回線＃４は出力可能な候補とできず、ラウンドロビン規則に従い入力回線＃１からのリクエストカウンタの値を参照すると値は１なので、入力回線＃１を出力回線＃４へ出力可能な候補として選択する。そして、グラントポインタの値をラウンドロビン規則に従って入力回線＃２に更新し、選択した入力回線＃１からのリクエストカウンタ１３−４−１の値をデクリメントして、０（図６の（ｃ）の１行４列目）に更新する。さらに、入力スケジューラ部１２−１に出力するグラントを有効’１’とし（図６の（ｄ）の１行４列目）、入力スケジューラ部１２−２、１２−３、１２−４に出力するグラントを無効’０’とする（図６の（ｄ）の２行４列目、３行４列目、４行４列目）。
【００４８】
次に、入力スケジューラ部１２−１、・・・、１２−４は、ステップ３として、出力スケジューラ部１１−１、・・・、１１−４から入力される有効なグラントの中から入力回線毎に一つラウンドロビン規則に従い選択する（図７）。図７の（ａ）はステップ３の処理前の各入力回線から各出力回線への有効なグラントとアクセプトポインタを表し、図７の（ｂ）はステップ３の処理後のグラントの選択結果とアクセプトポインタを表し、図７の（ｃ）はステップ３の処理後のスケジューリング結果を表し、図７の（ｄ）はステップ３の処理後の各入力スケジューラ部１２−１、・・・、１２−４から出力されるキャンセル情報を表している。入力スケジューラ部１２−１は、グラントレジスタ１５−１−１、・・・、１５−１−４で出力スケジューラ部１１−１、・・・、１１−４から入力されるグラントを出力スケジューラ部毎に受け取る。そして、アクセプトポインタａ１（１６−１）が示している出力回線＃２に対するグラントレジスタ１５−１−２を参照すると無効’０’なので、ラウンドロビン規則に従って次の出力回線＃３に対するグラントレジスタ１５−１−３を参照すると無効なので、さらに次の出力回線＃４に対するグラントレジスタ１５−１−４を参照すると有効’１’なので、出力回線＃４を出力可能な回線として選択する。そして、アクセプトポインタａ１の値をラウンドロビン規則に従って出力回線＃１に更新する。さらに、入力バッファ部１−１に出力するスケジューリング結果ＡＣＣ＃１を出力回線＃４のみ有効’１’とし（図７の（ｃ）の１行４列目）、出力回線＃１、＃２、＃３は無効’０’とする（図７の（ｃ）の１行１列目、１行２列目、１行３列目）。さらに、グラントレジスタが有効であるが選択されなかった出力回線＃１のグラントがキャンセルされたことを出力スケジューラ部１１−１に出力する（図７の（ａ）の１行１列目）。入力スケジューラ部１２−２は、グラントレジスタ１５−２−１、・・・、１５−２−４で出力スケジューラ部１１−１、・・・、１１−４から入力されるグラントを出力スケジューラ部毎に受け取る。そして、アクセプトポインタａ２（１６−２）が示している出力回線＃１に対するグラントレジスタ１５−２−１を参照すると無効’０’なので、ラウンドロビン規則に従って次の出力回線＃２に対するグラントレジスタ１５−２−２を参照すると有効’１’なので、出力回線＃２を出力可能な回線として選択する。そして、アクセプトポインタａ２の値をラウンドロビン規則に従って出力回線＃３に更新する。さらに、入力バッファ部１−２に出力するスケジューリング結果ＡＣＣ＃２を出力回線＃２のみ有効’１’とし（図７の（ｃ）の２行２列目）、出力回線＃１、＃３、＃４は無効’０’とする（図７の（ｃ）の２行１列目、２行３列目、２行４列目）。入力スケジューラ部１２−３は、グラントレジスタ１５−３−１、・・・、１５−３−４で出力スケジューラ部１１−１、・・・、１１−４から入力されるグラントを出力スケジューラ部毎に受け取る。そして、アクセプトポインタａ３（１６−３）が示している出力回線＃１に対するグラントレジスタ１５−３−１を参照すると無効’０’なので、ラウンドロビン規則に従って次の出力回線＃２に対するグラントレジスタ１５−３−２を参照すると無効’０’なので、さらに次の出力回線＃３に対するグラントレジスタ１５−３−３を参照すると有効’１’なので、出力回線＃３を出力可能な回線として選択する。そして、アクセプトポインタａ３の値をラウンドロビン規則に従って出力回線＃４に更新する。さらに、入力バッファ部１−３に出力するスケジューリング結果ＡＣＣ＃３を出力回線＃３のみ有効’１’とし（図７の（ｃ）の３行３列目）、出力回線＃１、＃２、＃４は無効’０’とする（図７の（ｃ）の３行１列目、３行２列目、３行４列目）。入力スケジューラ部１２−４は、グラントレジスタ１５−４−１、・・・、１５−４−４で出力スケジューラ部１１−１、・・・、１１−４から入力されるグラントを出力スケジューラ部毎に受け取る。そして、アクセプトポインタａ４（１６−４）が示している出力回線＃３に対するグラントレジスタ１５−４−３を参照すると無効’０’なので、ラウンドロビン規則に従って出力回線＃４、＃１、＃２に対するグラントレジスタ１５−４−４、１５−４−１、１５−４−２を参照すると全て無効’０’なので、出力可能な回線はないと、判断する。そして、アクセプトポインタａ４の値は前値保持とする。さらに、入力バッファ部１−４に出力するスケジューリング結果ＡＣＣ＃４は全ての出力回線＃１、・・・、＃４で無効’０’とする（図７の（ｃ）の４行目）。
【００４９】
本実施形態では、リクエストのカウント処理（図５）と、出力スケジューリング処理（図６）と、入力スケジューリング処理（図７）がそれぞれ独立で動作可能となるように構成され、それぞれの処理を１タイムスロットで行うので、１タイムスロットの演算量が削減できる。
【００５０】
[第２の実施形態]
図８は、本発明の第２の実施形態によるスケジューラ部の詳細な構成図である。図８に示すように、スケジューラ部は、Ｎ個の入力スケジューラ部２１−１、・・・、２１−ＮとＮ個の出力スケジューラ部２２−１、・・・、２２−Ｎから構成される。
【００５１】
入力スケジューラ部２１−１は、入力回線＃１から出力回線＃１〜＃Ｎへのリクエストを出力回線毎にカウントするリクエストカウンタ２３−１−１、・・・、２３−１−Ｎと、ラウンドロビン規則の先頭を示すグラントポインタｇ１（２４−１）と、リクエストカウンタ２３−１−１、・・・、２３−１−Ｎとグラントポインタｇ１（２４−１）に対する制御等を行う制御部２７−１で構成される。入力スケジューラ部２１−２、・・・、２１−Ｎは、該当する入力回線から出力回線＃１〜＃Ｎへのリクエストを出力回線毎にカウントするリクエストカウンタ２３−２−１、・・・、２３−Ｎ−Ｎと、ラウンドロビン規則の先頭を示すグラントポインタｇ２〜ｇＮ（２４−２、…、２４−Ｎ）と、リクエストカウンタ２３−２−１、・・・、２３−Ｎ−Ｎとグラントポインタｇ２〜ｇＮ（２４−２、…、２４−Ｎ）等に対する制御等を行う制御部２７−２、・・・、２７−Ｎで構成される。出力スケジューラ部２２−１は、全ての入力スケジューラ部の選択結果から出力回線＃１に対するグラントを抽出し、入力回線毎に保持するグラントレジスタ２５−１−１、・・・、２５−１−Ｎと、ラウンドロビン規則の先頭を示すアクセプトポインタａ１（２６−１）と、グラントレジスタ２５−１−１、・・・、２５−１−Ｎとアクセプトポインタａ１（２６−１）に対する制御等を行う制御部２８−１で構成される。出力スケジューラ部２２−２、・・・、２２−Ｎは、全ての入力スケジューラ部での選択結果を受信するグラントレジスタ２５−２−１、・・・、２５−Ｎ−Ｎと、ラウンドロビン規則の先頭を示すアクセプトポインタａ２〜ａＮ（２６−２、・・・、２６−Ｎ）と、グラントレジスタ２５−２−１、・・・、２５−Ｎ−Ｎとアクセプトポインタａ２〜ａＮ（２６−２、・・・、２６−Ｎ）に対する制御等を行う制御部２８−２、・・・、２８−Ｎで構成される。
【００５２】
入力スケジューラ部２１−１の制御部２７−１は、入力回線＃１のＶＯＱ管理部から入力されるスケジューリング要求を出力回線毎にリクエストカウンタ２３−１−１、…、２３−１−Ｎでカウントする。また、出力スケジューラ部２２−１、…、２２−Ｎから入力されるキャンセル情報から送信元が入力回線＃１であるキャンセルを抽出し、出力回線毎のリクエストカウンタ２３−１−１、…、２３−１−Ｎをカウントアップする。リクエストカウンタ２３−１−１、…、２３−１−Ｎでカウント値が１以上であるものから１つを、グラントポインタｇ１（２４−１）を最優先としてラウンドロビン規則に則り選択し、選択された出力回線のリクエストカウンタをデクリメント（−１）する。選択された出力回線の番号をグラントとして出力スケジューラ部に出力し、グラントポインタｇ１（２４−１）を選択された出力回線の次を示す値に更新する。例えば、選択された出力回線が＃１の場合は＃２に、選択された出力回線が＃Ｎの場合は＃１にグラントポインタｇ１（２４−１）を更新する。
【００５３】
入力スケジューラ部２１−２の制御部２７−２は、入力力回線＃２のＶＯＱ管理部から入力されるスケジューリング要求を出力回線毎にリクエストカウンタ２３−２−１、…、２３−２−Ｎでカウントする。また、出力スケジューラ部から入力されるキャンセル情報から宛先が入力回線＃２であるキャンセルを抽出し、出力回線毎のリクエストカウンタ２３−２−１、…、２３−２−Ｎをカウントアップする。リクエストカウンタ２３−２−１、…、２３−２−Ｎでカウント値が１以上であるものから１つを、グラントポインタｇ２（２４−２）を最優先としてラウンドロビン規則に則り選択し、選択された出力回線のリクエストカウンタをデクリメント（−１）する。選択された出力回線の番号をグラントとして出力スケジューラ部に出力し、グラントポインタｇ２（２４−２）を選択された出力回線の次を示す値に更新する。
【００５４】
入力スケジューラ部２１−３、・・・、２１−Ｎの制御部２７−３、・・・、２７−Ｎも入力スケジューラ部２１−１の制御部２７−１、入力スケジューラ部２１−２の制御部２７−２と同様の制御を行う。
【００５５】
出力スケジューラ部２２−１の制御部２８−１は、全ての入力スケジューラ部２１−１、・・・、２１−Ｎから出力されるグラントから宛先が出力回線＃１であるグラントを抽出し、入力回線毎のグラントレジスタ２５−１−１、…、２５−１−Ｎに格納する。該当するグラントがない場合は、グラントレジスタをクリア（グラントなし）する。グラントレジスタ２５−１−１、・・・、２５−１−Ｎにグラントが格納されているものから１つを、アクセプトポインタａ１（２６−１）を最優先としてラウンドロビン規則に則り選択する。選択された入力回線の番号をスケジューリング結果として出力バッファ部＃１のＶＯＱ管理部に出力し、アクセプトポインタａ１（２６−１）を選択された入力回線の次を示す値に更新する。例えば、選択された入力回線が＃１の場合は＃２に、選択された入力回線が＃Ｎの場合は＃１にアクセプトポインタａ１（２６−１）を更新する。全てのグラントレジスタ２５−１−１、…、２５−１−Ｎがグラント情報なしの場合、スケジューリング結果は未接続として出力し、アクセプトポインタａ１（２６−１）は前値保持とする。また、グラントレジスタにグラントが含まれているが前記の選択処理で選択されなかったものは、キャンセル情報として該当する入力スケジューラ部に出力する。
【００５６】
出力スケジューラ部２２−２の制御部２８−２は、全ての入力スケジューラ部２１−１、・・・、２１−Ｎから出力されるグラントから送信元が出力回線＃２であるグラントを抽出し、入力回線毎のグラントレジスタ２５−２−１、…、２５−２−Ｎに格納する。該当するグラントがない場合は、グラントレジスタをクリア（グラントなし）する。グラントレジスタ２５−２−１、…、２５−２−Ｎにグラントが格納されているものから１つを、アクセプトポインタａ２（２６−２）を最優先としてラウンドロビン規則に則り選択する。選択された入力回線の番号をスケジューリング結果として出力バッファ部＃２のＶＯＱ管理部に入力し、アクセプトポインタａ２（２６−２）を選択された入力回線の次を示す値に更新する。全てのグラントレジスタがグラント情報なしの場合、スケジューリング結果は未接続として入力し、アクセプトポインタａ２（２６−２）は前値保持とする。また、グラントレジスタにグラントが含まれているが前記の選択処理で選択されなかったものは、キャンセル情報として該当する入力スケジューラ部に出力する。
【００５７】
出力スケジューラ部２２−３、・・・、２２−Ｎの制御部２８−３、・・・、２８−Ｎも入力スケジューラ部２２−１の制御部２８−１、入力スケジューラ部２２−２の制御部２８−２と同様の制御を行う。
【００５８】
以上説明した入力スケジューラ部２１−１、・・・、２１−Ｎおよび出力スケジューラ部２２−１、・・・、２２−Ｎはそれぞれ独立に動作し、それぞれの処理は１タイムスロットに１回行われる。
【００５９】
次に、本実施形態のスケジューラ部の動作について図８および図９から図１１を参照して詳細に説明する。入出力回線の数Ｎが４の場合の動作について説明する。
【００６０】
まず、入力スケジューラ部は、ステップ１として、入力バッファ部１−１、・・・、１−４から出力バッファ部４−１、・・・、４−４へのスケジューリング要求をそれぞれカウントする（図９）。図９を参照すると、リクエストカウンタ（図９の（ａ））はステップ１の処理を行う前のリクエストカウンタ２３−１−１、・・・、２３−４−４の値を表し、リクエスト（図９の（ｂ））は各入力バッファ部１−１、・・・、１−４から入力される新規のスケジューリング要求ＲＥＱ＃１、・・・、ＲＥＱ＃４を表し、キャンセルは（図９の（ｃ））は出力スケジューラ部２２−１、・・・、２２−４から入力されるキャンセル情報ＣＡＮ＃１、…、ＣＡＮ＃４を表し、リクエストカウンタ（図９の（ｄ））はステップ１の処理を実施後のリクエストカウンタ２３−１−１、・・・、２３−４−４の値を表している。入力回線＃１から出力回線＃１に着目し、リクエストカウンタの値（図９の（ａ）の１行１列目）１と、リクエストの値（図９の（ｂ）の１行１列目）１と、キャンセルの値（図９の（ｃ）の１行１列目）０とを加算し、リクエストカウンタの値（図９の（ｄ）の１行１列目）を２に更新する。入力回線＃１から出力回線＃２に着目し、リクエストカウンタの値（図９の（ａ）の１行２列目）０と、リクエストの値（図９の（ｂ）の１行２列目）０と、キャンセルの値（図９の（ｃ）の１行２列目）０とを加算し、リクエストカウンタの値（図９の（ｄ）の１行２列目）を０に更新する。以下、全ての入力回線と出力回線の組合せに着目し、リクエストカウンタの値を更新する。
【００６１】
次に、入力スケジューラ部２１−１、・・・、２１−４は、ステップ２として、宛先が出力回線＃１、…、＃４であるリクエストの中から出力回線毎に一つラウンドロビン規則に従い選択する（図１０）。図１０の（ａ）はステップ２の処理前の各入力回線から各出力回線へのリクエストの有無とグラントポインタを表し、図１０の（ｂ）はステップ２の処理後の各出力回線へのリクエストの選択結果とグラントポインタを表し、図１０の（ｃ）はステップ２の処理後のリクエストカウンタの値を表し、図１０の（ｄ）はステップ２の処理後の各入力スケジューラ部２１−１、・・・、２１−４から出力されるグラントを表している。入力スケジューラ部２１−１は、グラントポインタｇ１（２４−１）が示している出力回線＃１からリクエストカウンタの値が１以上である出力回線を探索すると、出力回線＃１からのリクエストカウンタが２なので、出力回線＃１を入力回線＃１の出力可能な候補として選択する。そして、グラントポインタの値をラウンドロビン規則に従って出力回線＃２に更新し、選択した出力回線＃１へのリクエストカウンタ２３−１−１の値をデクリメント（−１）して、１（図１０の（ｃ）の１行１列目）に更新する。さらに、出力スケジューラ部２２−１に出力するグラントを有効’１’とし（図１０の（ｄ）の１行１列目）、出力スケジューラ部２２−２、２２−３、２２−４に出力するグラントを無効’０’とする（図１０の（ｄ）の１行２列目、１行３列目、１行４列目）。入力スケジューラ部２１−２は、グラントポインタｇ２（２４−２）が示している出力回線＃２からリクエストカウンタの値が１以上である出力回線を探索すると、出力回線＃２からのリクエストカウンタが２なので、出力回線＃２を入力回線＃２の出力可能な候補として選択する。そして、グラントポインタの値をラウンドロビン規則に従って出力回線＃３に更新し、選択した出力回線＃２からのリクエストカウンタ２３−１−２の値をデクリメントして、１（図１０の（ｃ）の２行２列目）に更新する。さらに、出力スケジューラ部２２−２に出力するグラントを有効’１’とし（図１０の（ｄ）の２行２列目）、出力スケジューラ部２２−１、２２−３、２２−４に出力するグラントを無効’０’とする（図１０の（ｄ）の２行１列目、２行３列目、２行４列目）。入力スケジューラ部２１−３は、グラントポインタｇ３（２４−３）が示している出力回線＃３からリクエストカウンタの値が１以上である出力回線を探索すると、出力回線＃３からのリクエストカウンタが２なので、出力回線＃３を入力回線＃３の出力可能な候補として選択する。そして、グラントポインタの値をラウンドロビン規則に従って出力回線＃４に更新し、選択した入力回線＃３からのリクエストカウンタ２３−１−３の値をデクリメントして１（図１０の（ｃ）の２行２列目）に更新する。さらに、出力スケジューラ部２２−３に出力するグラントを有効’１’とし（図１０の（ｄ）の３行３列目）、出力スケジューラ部２２−１、２２−２、２２−４に出力するグラントを無効’０’とする（図１０の（ｄ）の３行１列目、３行２列目、３行４列目）。入力スケジューラ部２１−４は、グラントポインタｇ４（２４−４）が示している出力回線＃４からリクエストカウンタの値が１以上である出力回線を探索すると、出力回線＃４のリクエストカウンタが０なので、出力回線＃４は出力可能な候補とできず、ラウンドロビン規則に従い出力回線＃１のリクエストカウンタの値を参照すると値は０なので、出力回線＃１は出力可能な候補とできず、出力回線＃２のリクエストカウンタの値を参照すると値は１なので、出力回線＃２を入力回線＃４の出力可能な候補として選択する。そして、グラントポインタの値をラウンドロビン規則に従って出力回線＃３に更新し、選択した出力回線＃２からのリクエストカウンタ２３−４−２の値をデクリメントして０（図１０の（ｃ）の４行２列目）に更新する。さらに、出力スケジューラ部２２−２に出力するグラントを有効’１’とし（図１０の（ｄ）の４行２列目）、出力スケジューラ部２２−１、２２−３、２２−４に出力するグラントを無効’０’とする（図１０の（ｄ）の４行１列目、４行３列目、４行４列目）。
【００６２】
次に、出力スケジューラ部２２−１、・・・、２２−４は、ステップ３として、入力スケジューラ部２１−１、・・・、２１−４から入力される有効なグラントの中から出力回線毎に一つラウンドロビン規則に従い選択する（図１１）。図１１の（ａ）はステップ３の処理前の各入力回線から各出力回線への有効なグラントとアクセプトポインタを表し、図１１の（ｂ）はステップ３の処理後のグラントの選択結果とアクセプトポインタを表し、図１１の（ｃ）はステップ３の処理後のスケジューリング結果を表し、図１１の（ｄ）はステップ３の処理後の各出力スケジューラ部２２−１、・・・、２２−４から出力されるキャンセル情報を表している。出力スケジューラ部２２−１は、グラントレジスタ２５−１−１、・・・、２５−１−４で入力スケジューラ部２１−１、・・・、２１−４から入力されるグラントを入力スケジューラ部毎に受け取る。そして、アクセプトポインタａ１（２６−１）が示している入力回線＃１に対するグラントレジスタ２５−１−１を参照すると有効’１’なので、入力回線＃１を出力回線＃１へ出力可能な回線として選択する。そして、アクセプトポインタａ１の値をラウンドロビン規則に従って入力回線＃２に更新する。さらに、入力バッファ部１−１の出力回線＃１に対するスケジューリング結果を有効’１’とし（図１１の（ｃ）の１行１列目）、入力バッファ部１−２、１−３、１−４の出力回線＃１に対するスケジューリング結果を無効’０’とする（図１１の（ｃ）の１行２列目、１行３列目、１行４列目）。
【００６３】
出力スケジューラ部２２−２は、グラントレジスタ２５−２−１、・・・、２５−２−４で入力スケジューラ部２１−１、・・・、２１−４から入力されるグラントを入力スケジューラ部毎に受け取る。そして、アクセプトポインタａ２（２６−２）が示している入力回線＃３に対するグラントレジスタ２５−２−３を参照すると無効’０’なので、入力回線＃３を選択できず、ラウンドロビン規則に従い入力回線＃３に対するグラントレジスタ２５−２−４を参照すると有効’１’なので、入力回線＃４を出力回線＃２へ出力可能な回線として選択する。そして、アクセプトポインタａ２の値をラウンドロビン規則に従って入力回線＃１に更新する。さらに、入力バッファ部１−４の出力回線＃２に対するスケジューリング結果を有効’１’とし（図１１の（ｃ）の４行２列目）、入力バッファ部１−１、１−２、１−３の出力回線＃２に対するスケジューリング結果を無効’０’とする（図１１の（ｃ）の１行２列目、２行２列目、３行２列目）。さらに、グラントレジスタが有効であるが選択されなかった入力回線＃２のグラントがキャンセルされたことを入力スケジューラ部２１−２に出力する（図１１の（ａ）の２行２列目）。
【００６４】
出力スケジューラ部２２−３は、グラントレジスタ２５−３−１、・・・、２５−３−４で入力スケジューラ部２１−１、・・・、２１−４から入力されるグラントを入力スケジューラ部毎に受け取る。そして、アクセプトポインタａ３（２６−３）が示している入力回線＃３に対するグラントレジスタ２５−３−３を参照すると有効’１’なので、入力回線＃３を出力回線＃３へ出力可能な回線として選択する。そして、アクセプトポインタａ３の値をラウンドロビン規則に従って入力回線＃４に更新する。さらに、入力バッファ部１−３の出力回線＃３に対するスケジューリング結果を有効’１’とし（図１１の（ｃ）の３行３列目）、入力バッファ部１−１、１−２、１−４の出力回線＃３に対するスケジューリング結果を無効’０’とする（図１１の（ｃ）の１行３列目、２行３列目、４行３列目）。
【００６５】
出力スケジューラ部２２−４は、グラントレジスタ２５−４−１、・・・、２５−４−４で入力スケジューラ部２１−１、・・・、２１−４から入力されるグラントを入力スケジューラ部毎に受け取る。そして、アクセプトポインタａ４（２６−４）が示している入力回線＃１に対するグラントレジスタ２５−４−１を参照すると無効’０’なので、順次、ラウンドロビン規則に従って入力回線＃２、＃３、＃４のグラントレジスタ２５−３−２、・・・、２５−３−４を参照すると全て無効’０’なので、出力回線＃４へ出力可能な回線はない、と判断する。そして、アクセプトポインタａ４の値は前値保持する。さらに、入力バッファ部１−１、１−２、１−３、１−４の出力回線＃４に対するスケジューリング結果を無効’０’とする（図１１の（ｃ）の１行４列目、２行４列目、３行４列目、４行４列目）。スケジューリング結果は、クロスバースイッチ部２の接続設定としても使用される。
【００６６】
本実施形態では、スケジューリング処理を始めに入力回線に対して行い、その結果で出力回線が重複選択されている場合に１つを選択するというように構成されているため、第１の実施形態と同様の効果がある。
【産業上の利用可能性】
【００６７】
本発明は、入出力回線の速度が高速で多数の回線を収容する入力バッファ型パケットスイッチにおいて、入力回線と出力回線を一対一で接続するための接続設定を高速に判断するといった用途に適用できる。
【図面の簡単な説明】
【００６８】
【図１】一般的な入力バッファ型パケットスイッチの全体構成を示すブロック図である。
【図２】本発明の第１の実施形態によるスケジューラ部のブロック図である。
【図３】図２のスケジューラ部の処理のシーケンス図である。
【図４】図２のスケジューラ部の処理を示すフローチャートである。
【図５】図２のスケジューラ部の動作（ステップ１）の具体例を示す図である。
【図６】図２のスケジューラ部の動作（ステップ２）の具体例を示す図である。
【図７】図２のスケジューラ部の動作（ステップ３）の具体例を示す図である。
【図８】本発明の第２の実施形態によるスケジューラ部のブロック図である。
【図９】図７のスケジューラ部の動作の具体例（ステップ１）示す図である。
【図１０】図７のスケジューラ部の動作の具体例（ステップ２）を示す図である。
【図１１】図７のスケジューラ部の動作の具体例（ステップ３）を示す図である。
【図１２】従来例のスケジューラ部のブロック図である。
【図１３】図１２のスケジューラ部の処理のシーケンス図である。
【図１４】図１２のスケジューラ部の処理を示すフローチャートである。
【図１５】図１２のスケジューラ部の動作の具体例（ステップ１）を示す図である。
【図１６】図１２のスケジューラ部の動作の具体例（ステップ２）を示す図である。
【図１７】図１２のスケジューラ部の動作の具体例（ステップ３）を示す図である。
【符号の説明】
【００６９】
１−１、・・・、１−Ｎ  入力バッファ部
２  クロスバースイッチ部
３  スケジューラ部
４−１、・・・、４−Ｎ  出力バッファ部
５−１、・・・、５−Ｎ  入力処理部
６−１、・・・、６−Ｎ  パケットバッファ
７−１、・・・、７−Ｎ  ＶＯＱ管理部
８−１、・・・、８−Ｎ  パケットバッファ
９−１、・・・、９−Ｎ  出力処理部
１０−１、・・・、１０−Ｎ  ＶＩＱ管理部
１１−１、・・・、１１−Ｎ  出力スケジューラ部
１２−１、・・・、１２−Ｎ  入力スケジューラ部
１３−１−１、・・・、１３−Ｎ−Ｎ  リクエストカウンタ
１４−１、・・・、１４−Ｎ  グラントポインタ
１５−１−１、・・・、１５−Ｎ−Ｎ  グラントレジスタ
１６−１、・・・、１６−Ｎ  アクセプトポインタ
１７−１、・・・、１７−Ｎ  制御部
１８−１、・・・、１８−Ｎ  制御部
２３−１−１、・・・、２３−Ｎ−Ｎ  リクエストカウンタ
２４−１、・・・、２４−Ｎ  グラントポインタ
２５−１−１、・・・、２５−Ｎ−Ｎ  グラントレジスタ
２６−１、・・・、２６−Ｎ  アクセプトポインタ
２７−１、・・・、２７−Ｎ  制御部
２８−１、・・・、２８−Ｎ  制御部
【図１】
2007259073.tif 000003
【図２】
2007259073.tif 000004
【図３】
2007259073.tif 000005
【図４】
2007259073.tif 000006
【図５】
2007259073.tif 000007
【図６】
2007259073.tif 000008
【図７】
2007259073.tif 000009
【図８】
2007259073.tif 000010
【図９】
2007259073.tif 000011
【図１０】
2007259073.tif 000012
【図１１】
2007259073.tif 000013
【図１２】
2007259073.tif 000014
【図１３】
2007259073.tif 000015
【図１４】
2007259073.tif 000016
【図１５】
2007259073.tif 000017
【図１６】
2007259073.tif 000018
【図１７】
2007259073.tif 000019