(57)【要約】【課題】平均遅延時間を短縮することができる入力・クロスポイントバッファ型スイッチを得る。【解決手段】出力ポート毎に用意されている出力スケジューラは、自出力ポート宛セルを格納するクロスポイントバッファの中から、セルを有するクロスポイントバッファを選択し、選択したバッファの先頭のセルを出力ポートに出力した後、自出力ポート宛セルを格納するクロスポイントバッファの内、セルを有するバッファの数をカウントし、自出力ポート宛セルを格納するクロスポイントバッファが管理する変数Ｃをその数に更新し、入力ポート毎に用意されている入力スケジューラは、自入力ポートからのセルを格納するクロスポイントバッファの空き容量とそのクロスポイントバッファが管理している変数Ｃを基にして、格納しているセルの中から、変数Ｃが最小でバッファに空きがあるクロスポイントバッファ宛にセルを出力する。【選択図】        図７
2004343181.tif 000002
【特許請求の範囲】
【請求項１】
入力バッファとクロスポイントバッファを有する入力・クロスポイントバッファ型スイッチであって、
自出力ポート宛セルを格納するクロスポイントバッファの中から、セルを有するクロスポイントバッファを選択し、選択したバッファの先頭のセルを出力ポートに出力した後、自出力ポート宛セルを格納するクロスポイントバッファの内、セルを有するバッファの数をカウントし、自出力ポート宛セルを格納するクロスポイントバッファが管理する変数Ｃをその数に更新する、出力ポート毎に用意されている出力スケジューラと、
自入力ポートからのセルを格納するクロスポイントバッファの空き容量とそのクロスポイントバッファが管理している変数Ｃを基にして、格納しているセルの中から、変数Ｃが最小でバッファに空きがあるクロスポイントバッファ宛にセルを出力する、入力ポート毎に用意されている入力スケジューラと、
を備えることを特徴とする入力・クロスポイントバッファ型スイッチ。
【請求項２】
入力バッファとクロスポイントバッファを有する入力・クロスポイントバッファ型スイッチのスケジューリング方法であって、
出力ポート毎に用意されている出力スケジューラは、自出力ポート宛セルを格納するクロスポイントバッファの中から、セルを有するクロスポイントバッファを選択し、選択したバッファの先頭のセルを出力ポートに出力した後、自出力ポート宛セルを格納するクロスポイントバッファの内、セルを有するバッファの数をカウントし、自出力ポート宛セルを格納するクロスポイントバッファが管理する変数Ｃをその数に更新し、
入力ポート毎に用意されている入力スケジューラは、自入力ポートからのセルを格納するクロスポイントバッファの空き容量とそのクロスポイントバッファが管理している変数Ｃを基にして、格納しているセルの中から、変数Ｃが最小でバッファに空きがあるクロスポイントバッファ宛にセルを出力する
ことを特徴とするスケジューリング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は入力バッファとクロスポイントバッファを有する入力・クロスポイントバッファ型スイッチにおいて、各バッファから出力されるセルを決定する技術に関する。
【０００２】
【従来の技術】
スイッチングシステムはバッファの配置方法により、いくつかの種類に分類できる。それらは、入力バッファのみを有する入力バッファ型スイッチ、出力バッファのみを有する出力バッファ型スイッチ、クロスポイントバッファのみを有するクロスポイントバッファ型スイッチ、入力バッファと出力バッファを有する入力・出力バッファ型スイッチ、入力バッファとクロスポイントバッファを有する入力・クロスポイントバッファ型スイッチである。
【０００３】
これらの中、出力バッファ型スイッチと入力・出力バッファ型スイッチは、他の型のスイッチより、バッファの速度を高速化しなければならないという問題点がある。またクロスポイント型スイッチは、入力バッファ型スイッチ、入力・クロスポイントバッファ型スイッチより、大量のバッファが必要となる問題点がある。更に入力バッファ型スイッチで使用されるスケジューリングアルゴリズムは入力・クロスポイントバッファ型バッファで使用されるものよりも複雑になるという問題がある。他の型のスイッチと比較して優れた性能を有する為、入力・クロスポイントバッファ型スイッチに関する研究が近年数多く発表されている。
【０００４】
入力・クロスポイントバッファ型スイッチを図１に示す。入力バッファはｖｉｒｔｕａｌ  ｏｕｔｐｕｔ  ｑｕｅｕｉｎｇ（ＶＯＱ）となっており、出力ポート毎の論理バッファから構成される。ＶＯＱ［ｉ］［ｊ］は出力ポートｊ宛のセルを格納する入力ポートｉのＶＯＱバッファを表しており、図１の入力・クロスポイント型スイッチ（４×４）の場合は、入力ポート（Ｉｎｐｕｔ  ｐｏｒｔ）０はＶＯＱ［０］［０］〜ＶＯＱ［０］［３］のＶＯＱバッファ（入力バッファ）を有し、・・・、入力ポート（Ｉｎｐｕｔ  ｐｏｒｔ）３はＶＯＱ［３］［０］〜ＶＯＱ［３］［３］のＶＯＱバッファ（入力バッファ）を有する。また、クロスポイントバッファＸＰ［ｉ］［ｊ］は入力ポートｉから出力ポートｊ宛のセルを格納する。図１の入力・クロスポイント型スイッチ（４×４）の場合は、ＸＰ［０］［０］〜ＸＰ［３］［３］の１６個のクロスポイントバッファを有する。なお、図１において入力ポート０〜３の入力バッファＶＯＱ［０］［０］〜ＶＯＱ［３］［３］およびクロスポイントバッファＸＰ［０］［０］〜ＸＰ［３］［３］内に記載した長方形がセル（固定長のデータ転送単位）を表す。図１では、例えば、入力ポート（Ｉｎｐｕｔ  ｐｏｒｔ）３は、出力ポート（Ｏｕｔｐｕｔ  ｐｏｒｔ）１，２，３宛のセルを有していることが分かる。各クロスポイントバッファＸＰ［ｉ］［ｊ］のサイズは１セルである。
【０００５】
入力・クロスポイントバッファ型スイッチでは、２つのスケジューラ、入力スケジューラと出力スケジューラが使用される。入力スケジューラは入力バッファからクロスポイントバッファに出力されるセルを決定し、出力スケジューラはクロスポイントバッファから出力ポートに出力されるセルを決定する。
【０００６】
入力スケジューラ用のアルゴリズムとして、最も早く到着したセルを優先するｏｌｄｅｓｔ  ｃｅｌｌ  ｆｉｒｓｔ（ＯＣＦ）アルゴリズム、キュー長の最も長いバッファのセルを優先するｌｏｎｇｅｓｔ  ｑｕｅｕｅ  ｆｉｒｓｔ（ＬＱＦ）アルゴリズム、ラウンドロビンでセルを選択するラウンドロビンアルゴリズムが提案されており、出力スケジューラ用のアルゴリズムとして、ＯＣＦアルゴリズム、ラウンドロビンアルゴリズムが提案されている。
【０００７】
しかし、上述したどのアルゴリズムの組み合わせを用いても平均セル遅延時間はほとんど変わらないことが報告されている（非特許文献１）。
【０００８】
出力ポート用のラウンドロビンアルゴリズムのフローチャートを図２に、入力ポート用のラウンドロビンアルゴリズムを図３に示す。
【０００９】
出力ポート用のラウンドロビンでは、ポインタが指し示すクロスポイントバッファから順に、そのクロスポイントバッファがセルを有するかどうかチェックし、その条件を満たせば、そのクロスポイントバッファのセルを出力し、ポインタの値を１だけ増やす。
【００１０】
図２は出力ポートａにおける出力スケジューラ用のラウンドロビンアルゴリズム（Ｎ×Ｎスイッチ）である。ここで、ｃｏｕｎｔは変数であり、ＸＰ［ｉ］［ｊ］は入力ポートｉから出力ポートｊ宛のセルを格納するクロスポイントバッファであり、ＸＰ＿Ｌｅｎ［ｉ］［ｊ］は入力ポートｉから出力ポートｊ宛のセルを格納するクロスポイントバッファの長さであり、ａは出力ポートであり、ｐｔｒは出力ポートａのポインタであり、Ｎは入力ポートの数である。
【００１１】
まず、変数ｃｏｕｎｔを０とし（ステップ２１）、入力ポートｐｔｒから出力ポートａ宛のセルを格納するクロスポイントバッファの長さＸＰ＿Ｌｅｎ［ｐｔｒ］［ａ］が正かどうか、すなわち当該クロスポイントバッファがセルを有しているかどうかを判断する（ステップ２２）。ＹＥＳであれば、すなわち当該クロスポイントバッファがセルを有していれば、ＸＰ［ｐｔｒ］［ａ］のセルを出力ポートａへ出力し（ステップ２３）、ポインタｐｔｒの値を１だけ増やし、ｐｔｒ  ｍｏｄ  Ｎを新たにｐｔｒとし（ステップ２４）、終了する。ステップ２２でＮＯであれば、すなわち当該クロスポイントバッファがセルを有していなければ、変数ｃｏｕｎｔの値を１だけ増やし（ステップ２５）、変数ｃｏｕｎｔの値が入力ポートの数Ｎであるかどうか判断し（ステップ２６）、ＹＥＳであれば終了し、ＮＯであればポインタｐｔｒの値を１だけ増やし、ｐｔｒ  ｍｏｄ  Ｎを新たにｐｔｒとし（ステップ２７）、ステップ２２に戻る。
【００１２】
入力ポート用のラウンドロビンでは、ポインタが指し示すＶＯＱから順に、そのＶＯＱがセルを有し、かつそのＶＯＱからのセルを格納するクロスポイントバッファに空きがあるかどうかチェックし、その条件を満たせば、そのＶＯＱの先頭セルを出力し、ポインタの値を１だけ増やす。クロスポイントバッファの空き情報は、フローコントロールが入力スケジューラに対して通知している。
【００１３】
図３は入力ポートａにおける入力スケジューラ用のラウンドロビンアルゴリズム（Ｎ×Ｎスイッチ）である。ここで、ｃｏｕｎｔは変数であり、ＶＯＱ［ｉ］［ｊ］は出力ポートｊ宛のセルを格納する入力ポートｉのＶＯＱバッファであり、ＶＯＱ＿Ｌｅｎ［ｉ］［ｊ］は出力ポートｊ宛のセルを格納する入力ポートｉのＶＯＱバッファの長さであり、ＸＰ［ｉ］［ｊ］は入力ポートｉから出力ポートｊ宛のセルを格納するクロスポイントバッファであり、ＸＰ＿Ｌｅｎ［ｉ］［ｊ］は入力ポートｉから出力ポートｊ宛のセルを格納するクロスポイントバッファの長さであり、ａは入力ポートであり、ｐｔｒは入力ポートａのポインタであり、Ｎは出力ポートの数である。
【００１４】
まず、変数ｃｏｕｎｔを０とし（ステップ３１）、出力ポートｐｔｒ宛のセルを格納する入力ポートａのＶＯＱバッファであるＶＯＱ［ａ］［ｐｔｒ］が正かどうか、すなわち当該ＶＯＱバッファがセルを有しているかどうかを判断する（ステップ３２）。ＹＥＳであれば、すなわち当該ＶＯＱバッファがセルを有していれば、入力ポートａから出力ポートｐｔｒ宛のセルを格納するクロスポイントバッファＸＰ［ａ］［ｐｔｒ］の長さＸＰ＿Ｌｅｎ［ａ］［ｐｔｒ］が０かどうか、すなわち当該クロスポイントバッファが空いているかどうかを判断する（ステップ３３）。ＹＥＳであれば、すなわち当該クロスポイントバッファが空いていれば、ＶＯＱ［ａ］［ｐｔｒ］の先頭のセルをＸＰ［ａ］［ｐｔｒ］へ出力し（ステップ３４）、ポインタｐｔｒの値を１だけ増やし、ｐｔｒ  ｍｏｄ  Ｎを新たにｐｔｒとし（ステップ３５）、終了する。ステップ３３でＮＯの場合、すなわち当該クロスポイントバッファがセルを有していれば、変数ｃｏｕｎｔの値を１だけ増やし（ステップ３６）、変数ｃｏｕｎｔの値が出力ポートの数Ｎであるかどうか判断し（ステップ３７）、ＹＥＳであれば終了し、ＮＯであればポインタｐｔｒの値を１だけ増やし、ｐｔｒ  ｍｏｄ  Ｎを新たにｐｔｒとし（ステップ３８）、ステップ３２に戻る。ステップ３２でＮＯの場合はステップ３６を実行し、ステップ３７の判断でＹＥＳであれば終了し、ＮＯであればステップ３８を実行後ステップ３２に戻る。
【００１５】
【非特許文献１】
Ｉ．  Ｒａｄｕｓｉｎｏｖｉｃ，  Ｍ．  Ｐｅｊａｎｏｖｉｃ，  ａｎｄ  Ｚ．  Ｐｅｔｒｏｖｉｃ，  ”Ｉｍｐａｃｔ  ｏｆ  ｓｃｈｅｄｕｌｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｏｎ  ｐｅｒｆｏｒｍａｎｃｅ  ｏｆ  ｂｕｆｆｅｒｅｄ  ｃｒｏｓｓｂａｒ  ｓｗｉｔｃｈ  ｆａｂｒｉｃｓ，”ＩＥＥＥ  ＩＣＣ  ２００２，ｐｐ．２４１６−２４２０，Ａｐｒｉｌ  ２００２
【００１６】
【発明が解決しようとする課題】
前述のとおり、上述したどのアルゴリズムの組み合わせを用いても平均セル遅延時間はほとんど変わらず、平均セル遅延時間を短縮することが困難であった。本発明の目的は、平均遅延時間を短縮することができる入力・クロスポイントバッファ型スイッチを得ることである。平均遅延時間が短い程、スループットが大きくなる為、本発明の目的は従来のアルゴリズムより、高いスループットを得ることであるとも言える。
【００１７】
【課題を解決するための手段】
前述の目的を達成するために、本発明は出力ポート毎に自出力ポート宛セルを格納するクロスポイントバッファの中、セルを有するバッファの数をカウントし、その数が最も少ない出力ポート宛のセルを入力バッファから優先的に出力するアルゴリズムを用いることによって、従来のアルゴリズムより、短い平均遅延時間を実現する。
【００１８】
本発明の特徴は、入力スケジューラが出力するセルを決定する時、自出力ポート宛のセルを格納するクロスポイントバッファの数が少ない出力ポート宛のセルを優先的に選択することにより、従来のアルゴリズムに比べて、短い平均遅延時間が実現できる点である。
【００１９】
すなわち、本発明の入力・クロスポイントバッファ型スイッチは、自出力ポート宛セルを格納するクロスポイントバッファの中から、セルを有するクロスポイントバッファを選択し、選択したバッファの先頭のセルを出力ポートに出力した後、自出力ポート宛セルを格納するクロスポイントバッファの内、セルを有するバッファの数をカウントし、自出力ポート宛セルを格納するクロスポイントバッファが管理する変数Ｃをその数に更新する、出力ポート毎に用意されている出力スケジューラと、自入力ポートからのセルを格納するクロスポイントバッファの空き容量とそのクロスポイントバッファが管理している変数Ｃを基にして、格納しているセルの中から、変数Ｃが最小でバッファに空きがあるクロスポイントバッファ宛にセルを出力する、入力ポート毎に用意されている入力スケジューラと、を備えることを特徴とする。
【００２０】
また、本発明の入力・クロスポイントバッファ型スイッチのスケジューリング方法は、出力ポート毎に用意されている出力スケジューラは、自出力ポート宛セルを格納するクロスポイントバッファの中から、セルを有するクロスポイントバッファを選択し、選択したバッファの先頭のセルを出力ポートに出力した後、自出力ポート宛セルを格納するクロスポイントバッファの内、セルを有するバッファの数をカウントし、自出力ポート宛セルを格納するクロスポイントバッファが管理する変数Ｃをその数に更新し、入力ポート毎に用意されている入力スケジューラは、自入力ポートからのセルを格納するクロスポイントバッファの空き容量とそのクロスポイントバッファが管理している変数Ｃを基にして、格納しているセルの中から、変数Ｃが最小でバッファに空きがあるクロスポイントバッファ宛にセルを出力することを特徴とする。
【００２１】
従来の技術との差異は、以下の通りである。
・本発明では、出力ポートａの出力スケジューラはセルを出力した後、出力ポートａ宛のセルを有するクロスポイントバッファの数をカウントし、その数Ｃを出力ポートａ宛のセルを格納するクロスポイントバッファに通知することである。一方、従来のアルゴリズムではそのような数をカウントしていない。
・本発明では、入力ポートａの入力スケジューラはクロスポイントバッファが管理する変数Ｃを基にして、どのセルを出力するかを決定する。一方、従来のアルゴリズムではそのような数を基にして決定していない。
【００２２】
【発明の実施の形態】
実施の形態における出力スケジューラのシステム構成を図４に、入力スケジューラのシステム構成を図５に示す。
【００２３】
図４において、出力ポート毎に用意されている判定部４１は、クロスポイントバッファ４２毎に用意されているキュー長測定部４３からキュー長の情報を受け取り、その情報からどのクロスポイントバッファからセルを出力するかを判定する。また判定部４１は出力するセルを決定した後、自身が存在する出力ポート宛のセルを格納するクロスポイントバッファの中、セルを有するバッファの数をカウントし、その値をフローコントロール部４４に伝える。クロスポイントバッファ毎に用意されているフローコントロール部４４は、変数Ｃを管理しており、その値を判定部４１からの情報に更新する。そしてその値と、キュー長測定部４３から得たクロスポイントバッファ４２に空きがあるかどうかの情報を図５の情報受信部５３に伝える。
【００２４】
図５において、判定部５１は、キュー長測定部５２からキュー長の情報を、情報受信部５３から、情報受信部５３が図４のフローコントロール部４４から受け取った情報を受け取り、それらの情報を基にして、入力バッファ５４からクロスポイントバッファ４２に出力するセルを決定する。
【００２５】
図４の判定部４１が出力するセルを決定するアルゴリズムを図６に、図５の判定部５１が出力するセルを決定するアルゴリズムを図７に示す。
【００２６】
図６のアルゴリズムでは、出力スケジューラは、ポインタが指し示すクロスポインタバッファから順に、クロスポイントバッファがセルを有しているかどうかを確認する。
【００２７】
セルを有しているクロスポイントバッファを発見すると、そのクロスポイントバッファからセルを出力し、ポインタの値を更新する。そして、セルを有しているクロスポイントバッファの数をカウントし、各クロスポイントバッファが管理している変数Ｃを更新する。一方セルを有するクロスポイントバッファを発見できなかった場合は変数Ｃを更新しない。
【００２８】
図６は出力ポートａにおける出力スケジューラ用の本実施の形態のアルゴリズム（Ｎ×Ｎスイッチ）である。ここで、ｃｏｕｎｔは変数であり、ＸＰ［ｉ］［ｊ］は入力ポートｉから出力ポートｊ宛のセルを格納するクロスポイントバッファであり、ＸＰ＿Ｌｅｎ［ｉ］［ｊ］は入力ポートｉから出力ポートｊ宛のセルを格納するクロスポイントバッファの長さであり、ａは出力ポートであり、ｐｔｒは出力ポートａのポインタであり、Ｃ［ｉ］［ｊ］はクロスポイントバッファＸＰ［ｉ］［ｊ］が管理する変数Ｃであり、Ｎは入力ポートの数である。
【００２９】
まず、変数ｃｏｕｎｔを０とし（ステップ６０１）、入力ポートｐｔｒから出力ポートａ宛のセルを格納するクロスポイントバッファＸＰ［ｐｔｒ］［ａ］の長さＸＰ＿Ｌｅｎ［ｐｔｒ］［ａ］が正かどうか、すなわち当該クロスポイントバッファがセルを有しているかどうかを判断する（ステップ６０２）。ＹＥＳであれば、すなわち当該クロスポイントバッファがセルを有していれば、ＸＰ［ｐｔｒ］［ａ］のセルを出力ポートａへ出力し（ステップ６０３）、ポインタｐｔｒの値を１だけ増やし、ｐｔｒ  ｍｏｄ  Ｎを新たにｐｔｒとする（ステップ６０４）。
【００３０】
次に、変数ｊを０とし、セルを有しているクロスポイントバッファの数ｎｕｍを０とする（ステップ６０５）。次に、変数ｊが入力ポートの数Ｎより小さいかどうかを判断する（ステップ６０６）。ＹＥＳの場合、すなわち変数ｊが入力ポートの数Ｎより小さい場合は、入力ポートｊから出力ポートａ宛のセルを格納するクロスポイントバッファＸＰ［ｊ］［ａ］の長さＸＰ＿Ｌｅｎ［ｊ］［ａ］が正かどうか、すなわち当該クロスポイントバッファがセルを有するかどうかを判断する（ステップ６０７）。ＹＥＳであれば、すなわち当該クロスポイントバッファがセルを有していれば、セルを有しているクロスポイントバッファの数ｎｕｍの値を１だけ増やし（ステップ６０８）、ｊの値を１だけ増やし（ステップ６０９）、ステップ６０６に戻る。ステップ６０７の判断でＮＯであれば、すなわち当該クロスポイントバッファがセルを有していなければステップ６０９でｊを１だけ増やし（ステップ６０９）、ステップ６０６に戻る。ステップ６０６でＮＯの場合、すなわち変数ｊが入力ポートの数Ｎと等しくなった場合は、ステップ６１０に進む。ステップ６０５〜６０９によりカウントされたｎｕｍは、出力ポートａに接続されているクロスポイントバッファ（図１であれば縦一列）の中でセルを有しているクロスポイントバッファの数である。
【００３１】
次に、変数ｊを０とし（ステップ６１０）、変数ｊが入力ポートの数Ｎより小さいかどうかを判断する（ステップ６１１）。ＹＥＳの場合、すなわちｊが入力ポートの数Ｎより小さい場合は、クロスポイントバッファＸＰ［ｊ］［ａ］が管理する数Ｃ［ｊ］［ａ］をステップ６０５〜６０９でカウントしたセルを有しているクロスポイントバッファの数ｎｕｍとし、ｊに１を加え（ステップ６１２）、ステップ６１１に戻る。ステップ６１１の判断でＮＯの場合、すなわち変数ｊが入力ポートの数Ｎと等しくなった場合は終了する。ステップ６１０〜６１２により、出力ポートａに接続されているＮ個のクロスポイントバッファ（図１であれば縦一列）が管理する数Ｃ［ｊ］［ａ］の全て（ｊ＝０〜Ｎ−１）にｎｕｍ、すなわち出力ポートａに接続されているクロスポイントバッファ（図１であれば縦一列）の中でセルを有しているクロスポイントバッファの数が記憶される。
【００３２】
ステップ６０２でＮＯであれば、すなわち当該クロスポイントバッファがセルを有していなければ、変数ｃｏｕｎｔの値を１だけ増やし（ステップ６１３）、変数ｃｏｕｎｔの値が入力ポートの数Ｎであるかどうか判断し（ステップ６１４）、ＹＥＳであれば終了し、ＮＯであればポインタｐｔｒの値を１だけ増やし、ｐｔｒ  ｍｏｄ  Ｎを新たにｐｔｒとし（ステップ６１５）、ステップ６０２に戻る。
【００３３】
図７のアルゴリズムでは、入力スケジューラは、ポインタが指し示すＶＯＱから順に、そのＶＯＱがセルを有しており、且つそのＶＯＱからのセルを格納するクロスポイントバッファに空きがあるかを調査する。
【００３４】
次に上述した条件を満たすＶＯＱの中から、そのＶＯＱからのセルを格納するクロスポイントバッファが管理する変数Ｃが最小のＶＯＱを探し出す。そしてそのようなＶＯＱが探し出せれば、そのＶＯＱからセルをクロスポイントバッファに出力する。
【００３５】
図７は入力ポートａにおける入力スケジューラ用の本実施の形態のアルゴリズム（Ｎ×Ｎスイッチ）である。ここで、ｃｏｕｎｔ，ｆｌａｇ，ｉｄは変数であり、ＶＯＱ［ｉ］［ｊ］は出力ポートｊ宛のセルを格納する入力ポートｉのＶＯＱバッファであり、ＶＯＱ＿Ｌｅｎ［ｉ］［ｊ］は出力ポートｊ宛のセルを格納する入力ポートｉのＶＯＱバッファの長さであり、ＸＰ［ｉ］［ｊ］は入力ポートｉから出力ポートｊ宛のセルを格納するクロスポイントバッファであり、ＸＰ＿Ｌｅｎ［ｉ］［ｊ］は入力ポートｉから出力ポートｊ宛のセルを格納するクロスポイントバッファの長さであり、Ｃ［ｉ］［ｊ］はクロスポイントバッファＸＰ［ｉ］［ｊ］が管理する変数Ｃであり、ａは入力ポートであり、ｐｔｒは入力ポートａのポインタであり、Ｎは出力ポートの数である。
【００３６】
まず、変数ｃｏｕｎｔを０、変数ｆｌａｇを０、変数ｉｄを０とし（ステップ７０１）、出力ポートｐｔｒ宛のセルを格納する入力ポートａのＶＯＱバッファの長さＶＯＱ＿Ｌｅｎ［ａ］［ｐｔｒ］が正かどうか、すなわち当該ＶＯＱバッファがセルを有しているかどうかを判断する（ステップ７０２）。ＹＥＳであれば、すなわち当該ＶＯＱバッファがセルを有していれば、入力ポートａから出力ポートｐｔｒ宛のセルを格納するクロスポイントバッファＸＰ［ａ］［ｐｔｒ］の長さＸＰ＿Ｌｅｎ［ａ］［ｐｔｒ］が０かどうか、すなわち当該クロスポイントバッファが空いているかどうかを判断する（ステップ７０３）。
【００３７】
ステップ７０３の判断がＹＥＳであれば、すなわち当該クロスポイントバッファが空いていれば、ｆｌａｇが０かどうかを判断する（ステップ７０４）。ＹＥＳであれば、すなわちｆｌａｇが０であれば、ｆｌａｇを１とし（ステップ７０５）、ｉｄをｐｔｒとし（ステップ７０７）、ステップ７０８に進む。
【００３８】
なお、ステップ７０４の判断でｆｌａｇが０のときは１とし、ｆｌａｇが１のときはその後のルーチンでｆｌａｇを変更することはないから、ステップ７０４を実行する場合、すなわちステップ７０２でＹＥＳと判断され、かつステップ７０３でＹＥＳと判断された場合は、必ずｆｌａｇ＝１となる。したがって、ｆｌａｇ＝１は、出力ポートｐｔｒ宛のセルを格納する入力ポートａのＶＯＱバッファであるＶＯＱ［ａ］［ｐｔｒ］にセルがあり、かつ入力ポートａから出力ポートｐｔｒ宛のセルを格納するクロスポイントバッファＸＰ［ａ］［ｐｔｒ］が空いている場合を示しており、ｆｌａｇ＝１であれば入力ポートａからそれに接続されたどれかのクロスポイントバッファにセルが出力可能である。
【００３９】
ステップ７０４の判断がＮＯであれば、すなわち既にどれかのクロスポイントバッファにセルが出力可能となっているときは、クロスポイントバッファＸＰ［ａ］［ｐｔｒ］が管理する変数Ｃ［ａ］［ｐｔｒ］がクロスポイントバッファＸＰ［ａ］［ｉｄ］が管理する変数Ｃ［ａ］［ｉｄ］より小さいかどうか、すなわち当該クロスポイントバッファが管理する変数Ｃが既にセルが出力可能となっているクロスポイントバッファが管理する変数Ｃより小さいかどうかを判断する（ステップ７０６）。
【００４０】
ステップ７０６の判断でＹＥＳであれば、すなわち既にセルを出力可能なクロスポイントバッファが管理する変数Ｃよりも当該クロスポイントバッファが管理する変数Ｃの方が小さければ、ｉｄをｐｔｒとし（ステップ７０７）、ステップ７０８に進む。ステップ７０６の判断がＮＯであれば、そのままステップ７０８に進む。ステップ７０６〜７０７によって、入力ポートａから出力ポートｉｄ宛のセルを格納するクロスポイントバッファＸＰ［ａ］［ｉｄ］が管理する変数Ｃ［ａ］［ｉｄ］がこれまでで最小の値となる。後述のステップ７０８〜７１０により、ステップ７０２〜７０７は出力ポートの数Ｎだけ繰り返される（図１の場合は横一行についてステップ７０２〜７０７の処理が行われる）から、最終的にはクロスポイントバッファＸＰ［ａ］［ｉｄ］が管理する変数Ｃ［ａ］［ｉｄ］が最小となり、このクロスポイントバッファＸＰ［ａ］［ｉｄ］が入力ポートａが出力すべきクロスポイントバッファとなる。
【００４１】
ステップ７０８は、（１）ステップ７０２の判断でＮＯの場合、すなわち出力ポートｐｔｒ宛のセルを格納する入力ポートａのＶＯＱバッファであるＶＯＱ［ａ］［ｐｔｒ］がセルを有していない場合、（２）ステップ７０３の判断でＮＯの場合、すなわち入力ポートａから出力ポートｐｔｒ宛のセルを格納するクロスポイントバッファＸＰ［ａ］［ｐｔｒ］がセルを有している場合、（３）ステップ７０４〜７０７を終了した場合に実行される。ステップ７０８では、変数ｃｏｕｎｔに１が加えられる。次にステップ７０９で変数ｃｏｕｎｔが出力ポートの数Ｎの等しいかどうかが判断される。
【００４２】
ステップ７０９の判断でＮＯの場合、すなわち変数ｃｏｕｎｔが出力ポートの数Ｎより小さい場合は、ポインタｐｔｒの値を１だけ増やし、ｐｔｒ  ｍｏｄ  Ｎを新たにｐｔｒとし（ステップ７１０）、ステップ７０２に戻る。これにより、入力ポートａに接続されている全てのクロスポイントバッファ（図１の場合は横一行のクロスポイントバッファ）についてステップ７０２〜７０７の処理が行われることになる。
【００４３】
ステップ７０９の判断でＹＥＳの場合、すなわち入力ポートａに接続されている全てのクロスポイントバッファ（図１の場合は横一行のクロスポイントバッファ）についてステップ７０２〜７０７の処理が行われた後に、ステップ７１１でｆｌａｇが１と等しいかどうかを判断する。
【００４４】
ステップ７１１の判断でＹＥＳの場合、すなわち入力ポートａからそれに接続されているクロスポイントバッファにセルが出力可能な場合は、ＶＯＱ［ａ］［ｉｄ］の先頭のセルをＸＰ［ａ］［ｉｄ］へ出力する（ステップ７１２）。ここでｉｄはステップ７０６〜７０７でクロスポイントバッファＸＰ［ａ］［ｉｄ］が管理する変数Ｃ［ａ］［ｉｄ］が最小となるように設定されており、クロスポイントバッファＸＰ［ａ］［ｉｄ］が入力ポートａが出力すべきクロスポイントバッファである。そして、ポインタｐｔｒの値を１だけ増やし、ｐｔｒ  ｍｏｄＮを新たにｐｔｒとし（ステップ７１３）、終了する。ステップ７１１でＮＯの場合、すなわち入力ポートａからそれに接続されているクロスポイントバッファにセルが出力可能でない場合は終了する。
【００４５】
出力スケジューラのアルゴリズム、入力スケジューラのアルゴリズムをそれぞれ図２，３のようにした従来方式と出力スケジューラのアルゴリズム、入力スケジューラのアルゴリズムをそれぞれ図６，７のようにした本実施の形態の性能比較評価をコンピュータシミュレーションで行った結果を以下に示す。シミュレーション条件は以下の通りである。
・スイッチサイズＮ：３２
・トラヒック到着パターン：ベルヌーイ課程に従いセルが到着するモデル
・シミュレーション時間：１０の６乗セル時間
図８に負荷（Ｌｏａｄ）と平均セル遅延時間（Ｍｅａｎ  ｃｅｌｌ  ｄｅｌａｙ  ｔｉｍｅ）の関係を示す。○が従来方式のコンピュータシミュレーション結果であり、□が本実施の形態（提案方式）のコンピュータシミュレーション結果である。本実施の形態を用いることにより、平均セル遅延時間を短縮できていることが確認できる。
【００４６】
以上、本発明者によってなされた発明を、前記実施の形態に基づき具体的に説明したが、本発明は、前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【００４７】
【発明の効果】
以上説明したように、本発明によれば、入力・クロスポイントバッファ型スイッチにおいて、従来方式より、平均遅延時間を短縮することができる。
【図面の簡単な説明】
【図１】入力・クロスポイントバッファ型スイッチ（４×４）を示す図である。
【図２】従来の出力ポートａにおける出力スケジューラ用のラウンドロビンアルゴリズム（Ｎ×Ｎスイッチ）を示す図である。
【図３】従来の入力ポートａにおける入力スケジューラ用のラウンドロビンアルゴリズム（Ｎ×Ｎスイッチ）アルゴリズムを示す図である。
【図４】本発明の実施の形態における出力スケジューラのシステム構成を示す図である。
【図５】本発明の実施の形態における入力スケジューラのシステム構成を示す図である。
【図６】本発明の実施の形態の出力ポートａにおける出力スケジューラ用のアルゴリズム（Ｎ×Ｎスイッチ）を示す図である。
【図７】本発明の実施の形態の入力ポートａにおける入力スケジューラ用のアルゴリズム（Ｎ×Ｎスイッチ）を示す図である。
【図８】従来技術と本発明の実施の形態のシミュレーション結果を示す図である。
【符号の説明】
４１…判定部、４２…クロスポイントバッファ、４３…キュー長測定部、４４…フローコントロール部、５１…判定部、５２…キュー長測定部、５３…情報受信部、５４…ＶＯＱ。
【図１】
2004343181.tif 000003
【図２】
2004343181.tif 000004
【図３】
2004343181.tif 000005
【図４】
2004343181.tif 000006
【図５】
2004343181.tif 000007
【図６】
2004343181.tif 000008
【図７】
2004343181.tif 000009
【図８】
2004343181.tif 000010