(57)【特許請求の範囲】
【請求項１】
各出力ポート（OP）毎に用意された論理バッファ（Q１〜Qｎ）を有する入力バッファ部（４）と、第１および第２の２つのスケジューラ（SC1およびSC2）とを入力ポート（IP）毎に備え、且つ第３および第４の２つのスケジューラ（SC3およびSC4）を各出力ポート（OP）毎に備えたスイッチング装置であって、ディジタル化可能な情報をセル単位で伝送・交換するに当り、時刻ｔにおける前記各入力ポート（IP）の送出セル決定時に：
前記各入力ポート（IP）における第１スケジューラ（SC1）において、セル送出権を得ていない入力ポート（IP）は、該入力ポートが送出できるセルを有する全ての出力ポート（OP）に対して、先頭セルの待ち時間を含んだリクエスト信号を送出し；
前記各入力ポート（IP）における第２スケジューラ（SC2）において、セル送出権を得ていない入力ポート（IP）は、該入力ポートが時刻(t-１)における送出セル決定時に、前記第２スケジューラ（SC2）において、或る出力ポートA宛にセル送出権を得ており、且つこの送出権を得ていると云う情報が前記第１スケジューラ（SC1）に移行している場合には、該入力ポートが送出できるセルを有する前記出力ポートA以外の全ての出力ポート（OP）に対して、先頭セルの待ち時間を含んだリクエスト信号を送出し；
前記各入力ポート（IP）における第２スケジューラ（SC2）において、セル送出権を得ていない入力ポート（IP）は、該入力ポートが時刻(t-１)における送出セル決定時に、前記第２スケジューラ（SC2）において、前記出力ポートA宛にセル送出権を得ており、且つこの送出権を得ていると云う情報が、前記第１スケジューラ（SC1）に移行している場合で、且つ、該入力ポートが前記出力ポートA宛のセルを２セル以上保有している場合には、前記出力ポートAに対して、先頭セルから２番目のセルの待ち時間を含んだリクエスト信号を送出し；
前記各入力ポート（IP）における第２スケジューラ（SC2）において、セル送出権を得ていない入力ポート（IP）は、該入力ポートが時刻(t-１)における送出セル決定時に、前記第２スケジューラ（SC2）において、セル送出権を得ていないか、或いはセル送出権を得ていても、その情報が前記第１スケジューラ（SC1）に移行されていない場合には、該入力ポートが送出できるセルを有する全ての出力ポート（OP）に対して、先頭セルの待ち時間を含んだリクエスト信号を送出し；
前記各出力ポート（OP）における第３および第４スケジューラ（SC3およびSC4）において、セル受信権を得ていない出力ポート（OP）が、１つ以上のリクエスト信号を受信した場合には、最も大きな待ち時間を送出した入力ポート（IP）に許可信号を送出し；
前記各入力ポート（IP）における第１および第２スケジューラ（SC1およびSC2）において、セル送出権を得ていない入力ポート（IP）が、1つ以上の許可信号を受信した場合には、最も大きな待ち時間を送出した出力ポート（OP）に確認信号を送出する；
ことを特徴とするスイッチング方法。
【請求項２】
前記リクエスト信号、許可信号および確認信号の送出ステップを1セル時間内にS（>０）回繰り返すことを特徴とする請求項１に記載のスイッチング方法。
【請求項３】
前記時刻ｔにおける送出セル決定時に、前記各入力ポート（IP）における第1スケジューラ（SC1）において、或る出力ポートBへのセル送出権を得た入力ポートCは、前記出力ポートBへセルを送出し、前記各入力ポート（IP）における第2スケジューラ（SC2）において、前記出力ポートBへのセル送出権を得た入力ポートCは、該入力ポートCが前記出力ポートB宛のセルを有する場合に、時刻（ｔ+１）における送出セル決定時に、前記各入力ポート（IP）における第１スケジューラ（SC1）において、前記入力ポートCは送出権を得ており、前記各出力ポート（OP）における第3スケジューラ（SC3）において、前記出力ポートBは受信権を得ているとすることを特徴とする請求項1に記載のスイッチング方法。
【請求項４】
複数個の入力ポート（IP）およびこれらの入力ポートに対応する複数個の出力ポート（OP）を備え、ディジタル化可能な情報をセル単位で伝送・交換する通信方式に用いられるスイッチング装置において、
前記各入力ポート（IP）が、到着セルのヘッダにタイムカウント部（２）により管理される現在の時刻を書き込む時刻情報付与部（１）と、前記到着セルがどの出力ポート（OP）宛のセルであるかを識別して送出するセル識別部（３）と、該セル識別部からのセルを格納する、出力ポート毎の論理バッファ（Q１〜Qｎ）を有する入力バッファ部（４）と、前記論理バッファに格納されているセルのヘッダから時刻情報を読み取る時刻情報読み取り部（５；６）および出力ポート（OP）と情報の交換を行なうことにより、どの論理バッファからセルを送出するかを決定する判定部（７；８）をそれぞれ有している第1および第2のスケジューラ（SC1;SC2）と、前記論理バッファのセル数を読み取るセル数読み取り部（１１）と、該セル数読み取り部の情報と前記第1および第２スケジューラの判定部の情報から、セル送出権の情報を前記第1および第2スケジューラ間で移行させる情報移行部（１０）と、前記第1スケジューラにおける判定部（７）の結果に基づいて、前記入力バッファ部（４）の論理バッファからセルを取り出す制御部（９）とを備え、且つ
前記各出力ポート（OP）が、前記各入力ポート（IP）の第1スケジューラ（SC1）の判定部（７）と情報の交換を行なうことにより、どの入力ポートからセルを受信するかを決定する判定部（１２）を有する第3スケジューラ（SC3）と、前記各入力ポート（IP）の第２スケジューラ（SC2）の判定部（８）と情報の交換を行なうことにより、どの入力ポートからセルを受信するかを決定する判定部（１３）を有する第４スケジューラ（SC4）とを備えていることを特徴とするスイッチング装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、音声、画像、コンピュータ・データ等のような、ディジタル化可能な情報を48バイトずつに区切り、５バイトのヘッダを付けて、計５３バイトのセルと称する単位で伝送・交換する通信方式に用いられるATM（非同期転送モード）スイッチ及びIP（インターネットプロトコル）ルータにおけるスイッチ構成に関するものである。本発明は特に、スイッチ構成法の一つである入力バッファ型スイッチにおいて、次にどのセルを送出すべきかを決定するスイッチング技法に関するものである。
【０００２】
【従来の技術】
スイッチングシステムは、そのバッファ配置法から入力バッファ型スイッチ、出力バッファ型スイッチ、共通バッファ型スイッチ、クロスポイント型スイッチに分類される。これらのうちで、入力ポートにおいてのみバッファを有する入力バッファ型スイッチは、必要とされるメモリ速度が低速で、内部を入力回線速度に比べて高速化する必要がない等の大容量スイッチに適した性能を有している。そして、近年、入力ポートにおけるバッファを出力ポート毎に用意し、これらのバッファを論理バッファで構成する場合に、そのスイッチのスループットが100%になることが証明され（N.McKeown外著による“Achieving 100% throughput in an input-queued switch” Proc. of IEEE  INFOCOM’96 、1996年3月）、そこで使用する送出セル決定アルゴリズムも多数提案されている。ここでは、そのうちの1つであるi-OCFアルゴリズム（N.McKeownによるカリフォルニア大学バークレイ校の学位論文“Scheduling  algorithms  for  input-queued cell  switches”1995年5月）について説明する。
【０００３】
i-OCFアルゴリズムは以下の３つのステップから構成されるものである。
-ステップ１：セル送出権を得ていない入力ポートは、その入力ポートが送出できるセルを有するすべての出力ポートに対して、先頭セルの待ち時間を含んだリクエスト信号を送出する；
-ステップ２：セル受信権を得ていない出力ポートは、その出力ポートが１つ以上のリクエスト信号を受信した場合に、最も大きな待ち時間を送出した入力ポートに許可信号を送出する。
-ステップ３：セル送出権を得ていない入力ポートは、その入力ポートが１つ以上の許可信号を受信した場合に、最も大きな待ち時間を送出した出力ポートに確認信号を送出する。
【０００４】
このようにして、確認信号を送出した入力ポートはセル送出権を有し、確認信号を受信した出力ポートはセル受信権を有することになる。
【０００５】
i-OCFアルゴリズムは、上記３つのステップを１セル時間内にS(>0)回繰り返すようにしている。しかし、回線速度が高速になるにつれて、1セル時間は次第に短くなる。従って、回線速度が高速になればなるほど、Sが取り得る値は小さくなる。つまり、例えば回線速度が150Mbpsの時は、S=8が可能であったが、回線速度が10Gbpsになると、S=2が限界になるということが起こり得る。しかし、このようにSが取り得る値が小さくなると、セル送出権が与えられる入力ポートの数が少なくなり、結果として、スイッチのスループットが低下することになる。そこで、Sが小さくても、多数の入力ポートに送出権を与えることができる送出セル決定アルゴリズムが所望されることになる。
【００１１】
【発明が解決しようとする課題】
本発明の目的は、入力バッファ型スイッチにおいて、回線速度が高速になる場合でも、多数の入力ポートにセル送出権を短時間で与えて、高いスループットを達成し得るスイッチング方法および装置を提供することにある。
【００１２】
【課題を解決するための手段】
本発明は、各出力ポート毎に用意された論理バッファを有する入力バッファ部と、第１および第２の２つのスケジューラとを入力ポート毎に備え、且つ第３および第４の２つのスケジューラを各出力ポート毎に備えたスイッチング装置であって、ディジタル化可能な情報をセル単位で伝送・交換するに当り、時刻ｔにおける前記各入力ポートの送出セル決定時に：
前記各入力ポートにおける第１スケジューラにおいて、セル送出権を得ていない入力ポートは、該入力ポートが送出できるセルを有する全ての出力ポートに対して、先頭セルの待ち時間を含んだリクエスト信号を送出し；
前記各入力ポートにおける第２スケジューラにおいて、セル送出権を得ていない入力ポートは、該入力ポートが時刻(t-１)における送出セル決定時に、前記第２スケジューラにおいて、或る出力ポートA宛にセル送出権を得ており、且つこの送出権を得ていると云う情報が前記第１スケジューラに移行している場合には、該入力ポートが送出できるセルを有する前記出力ポートA以外の全ての出力ポートに対して、先頭セルの待ち時間を含んだリクエスト信号を送出し；
前記各入力ポートにおける第２スケジューラにおいて、セル送出権を得ていない入力ポートは、該入力ポートが時刻(t-１)における送出セル決定時に、前記第２スケジューラにおいて、前記出力ポートA宛にセル送出権を得ており、且つこの送出権を得ていると云う情報が、前記第１スケジューラに移行している場合で、且つ、該入力ポートが前記出力ポートA宛のセルを２セル以上保有している場合には、前記出力ポートAに対して、先頭セルから２番目のセルの待ち時間を含んだリクエスト信号を送出し；
前記各入力ポートにおける第２スケジューラにおいて、セル送出権を得ていない入力ポートは、該入力ポートが時刻(t-１)における送出セル決定時に、前記第２スケジューラにおいて、セル送出権を得ていないか、或いはセル送出権を得ていても、その情報が前記第１スケジューラに移行されていない場合には、該入力ポートが送出できるセルを有する全ての出力ポートに対して、先頭セルの待ち時間を含んだリクエスト信号を送出し；
前記各出力ポートにおける第３および第４スケジューラにおいて、セル受信権を得ていない出力ポートが、１つ以上のリクエスト信号を受信した場合には、最も大きな待ち時間を送出した入力ポートに許可信号を送出し；
前記各入力ポートにおける第１および第２スケジューラにおいて、セル送出権を得ていない入力ポートが、1つ以上の許可信号を受信した場合には、最も大きな待ち時間を送出した出力ポートに確認信号を送出する；
ことを特徴とするスイッチング方法にある。
【００１３】
さらに本発明は、複数個の入力ポートおよびこれらの入力ポートに対応する複数個の出力ポートを備え、ディジタル化可能な情報をセル単位で伝送・交換する通信方式に用いられるスイッチング装置において、
前記各入力ポートが、到着セルのヘッダにタイムカウント部により管理される現在の時刻を書き込む時刻情報付与部と、前記到着セルがどの出力ポート宛のセルであるかを識別して送出するセル識別部と、該セル識別部からのセルを格納する、出力ポート毎の論理バッファを有する入力バッファ部と、前記論理バッファに格納されているセルのヘッダから時刻情報を読み取る時刻情報読み取り部および出力ポートと情報の交換を行なうことにより、どの論理バッファからセルを送出するかを決定する判定部をそれぞれ有している第1および第2のスケジューラと、前記論理バッファのセル数を読み取るセル数読み取り部と、該セル数読み取り部の情報と前記第1および第２スケジューラの判定部の情報から、セル送出権の情報を前記第1および第2スケジューラ間で移行させる情報移行部と、前記第1スケジューラにおける判定部の結果に基づいて、前記入力バッファ部の論理バッファからセルを取り出す制御部とを備え、且つ
前記各出力ポートが、前記各入力ポートの第1スケジューラの判定部と情報の交換を行なうことにより、どの入力ポートからセルを受信するかを決定する判定部を有する第3スケジューラと、前記各入力ポートの第２スケジューラの判定部と情報の交換を行なうことにより、どの入力ポートからセルを受信するかを決定する判定部を有する第４スケジューラとを備えていることを特徴とするスイッチング装置にある。
【００１４】
【発明を実施するための最良の形態】
本発明をより詳細に説述するために、添付の図面に従ってこれを説明する。
【００１５】
図１は本発明の実施例によるスイッチング装置の各入力ポートIPにおけるシステム構成を示したブロック図であり、また、図２はこれに対応する出力ポートOPにおけるシステム構成を示したブロック図である。各入力ポートIPにおける時刻情報付与部１は、セルの到着時に、タイムカウント部２によって管理されている現在の時刻を到着したセルのヘッダに書き込む。セル識別部３は、到着したセルがどの出力ポート宛のセルであるかを識別してから、このセルを入力バッファ部４における対応する論理バッファに入力する。入力バッファ部４は、出力ポート毎の論理キューである論理バッファQ１〜Qｎを有している。
【００１６】
本発明では、各入力ポートIPに２つのスケジューラSC1およびSC2を用立てると共に、各出力ポートOPにも２つのスケジューラSC3およびSC4を用立てる。入力ポートIPの第１スケジューラSC1および第２スケジューラSC2における時刻情報読み取り部５および６は、入力バッファ部４の各論理バッファQ１〜Qｎに格納されているセルのヘッダから時刻情報を読み取る。入力ポートIPの第１スケジューラSC1における判定部７は、出力ポートOPの第３スケジューラSC3における判定部１２と情報を交換することにより、どの論理バッファ（Q１〜Qｎ）からセルを送出するかを決定する。入力ポートIPの第２スケジューラSC2における判定部８は、出力ポートOPの第４スケジューラSC4における判定部１３と情報を交換することにより、どの論理バッファ（Q１〜Qｎ）からセルを送出するかを決定する。入力ポートIPにおける制御部９は、第１スケジューラSC1における判定部７の結果に基づいて、論理バッファQ１〜Qｎから対応するセルを取り出す。入力ポートIPにおける情報移行部１０は、論理バッファのセル数を読み取るセル数読み取り部１１の情報と、第１および第２のスケジューラSC1およびSC2のそれぞれの判定部７および８の情報とから、第２スケジューラSC2の情報を第１スケジューラSC1へ移行するかどうかを判定する。
【００１７】
各出力ポートOPでは、第３スケジューラSC3の判定部１２にて、入力ポートIPの第１スケジューラSC1における判定部７と情報の交換を行なうことにより、どの入力ポートからセルを受信するかを決定する。第４スケジューラSC4の判定部１３は、入力ポートIPの第２スケジューラSC2における判定部８と情報の交換を行なうことにより、どの入力ポートからセルを受信するかを決定する。
【００１８】
次ぎに、図３〜図7に基づいて本実施例を説明するに、以下の例では、入力ポートIPおよび出力ポートOPの個数を、例えば、それぞれ３個ずつとし、且つ例えば時刻t=5で、S=1の開始時点には、どのスケジューラにおいても、送出権を得ている入力ポートおよび受信権を得ている出力ポートは存在しないものとする。また、各セルは、既に時刻情報付与部１およびセル識別部３（図１参照）を通過して、図3に示すように、各入力ポートIPの入力バッファ部における、各出力ポートOP毎の論理バッファQ１〜Q３内にあるものとする。この例では、入力ポートIP１における、入力バッファ部の論理バッファQ１には時刻ｔ＝１に到着した出力ポートOP１宛のセルが格納され、論理バッファQ２には時刻ｔ＝４に到着した出力ポートOP２宛のセルが格納され、論理バッファQ３には時刻ｔ＝３に到着した出力ポートOP３宛のセルが格納されており、以下図示のように、入力ポートIP２における、入力バッファ部の論理バッファQ１には時刻ｔ＝２に到着した出力ポートOP１宛のセルが格納され、論理バッファQ２には時刻ｔ＝１と、ｔ＝３にそれぞれ到着した出力ポートOP２宛のセルが格納され、論理バッファQ３には出力ポートOP３宛のセルは格納されておらず、また、入力ポートIP３における、入力バッファ部の論理バッファQ１には出力ポートOP１宛のセルは格納されておらず、論理バッファQ２には時刻ｔ＝２に到着した出力ポートOP２宛のセルが格納され、論理バッファQ３には時刻ｔ＝１およびｔ＝３にそれぞれ到着したセルが格納されているものとする。このように、各セルに付した数字は、そのセルが各入力ポートに到着した時刻tを表わしており、小さな数ほど待ち時間が長いことになる。また、この例では、スイッチング装置における入力ポートおよび出力ポートの個数を3個ずつとしたが、実際にはかなりの数の入/出力ポートが用いられることは明かである。
【００１９】
時刻t=5における開始時点には、各入力ポートの第１スケジューラSC1において、送出権を得ている入力ポートは存在しないので、これらの各入力ポートIP１〜IP３の第１スケジューラSC1における判定部（７）は、その入力ポートが送出できるセルを有するすべての出力ポートOP１〜OP３にある第３スケジューラSC3の判定部（１２）に対して、時刻情報読み取り部（５）で取得した先頭セルの待ち時間を含んだリクエスト信号を送出する。即ち、この場合には、図４Aに示すように、入力ポートIP１にある第１スケジューラSC1における判定部は、出力ポートOP１、OP２およびOP３にある第３スケジューラSC3における判定部へ、入力ポートIP２にある第１スケジューラSC1おける判定部は、出力ポートOP１およびOP２にある第３スケジューラSC3における判定部へ、入力ポートIP３にある第１スケジューラSC1の判定部は、出力ポートOP２およびOP３にある第３スケジューラSC3の判定部へそれぞれリクエスト信号を送出する。
【００２０】
ｔ＝５の開始時点には、各入力ポートの第２スケジューラSC2において、これら全ての入力ポートIP１〜IP３は送出権を得ておらず、しかも、いずれの情報も第２スケジューラSC2から第１スケジューラSC1へ移行していないので、各入力ポートIP１〜IP３の第２スケジューラSC2における判定部も、その入力ポートが送出できるセルを有する全ての出力ポートOP１〜OP３にある第４スケジューラSC4の判定部に対して、時刻情報読み取り部（６）で取得した先頭セルの待ち時間を含んだリクエスト信号を送出する。即ち、この場合には、図４Aに示すように、入力ポートIP１にある第２スケジューラSC2における判定部は、出力ポートOP１、OP２およびOP３にある第４スケジューラSC4の判定部へ、入力ポートIP２にある第２スケジューラSC2における判定部は、出力ポートOP１およびOP２にある第４スケジューラSC4における判定部へ、入力ポートIP３の第２スケジューラSC2における判定部は、出力ポートOP２およびOP３の第４スケジューラSC4における判定部へそれぞれリクエスト信号を送出する。
【００２１】
ここでなぜ、ｔ＝５の開始時点にいずれの情報も第２スケジューラSC2から第１スケジューラSC1へと移行されていないかが分かるかについて説明すると、それは、第１スケジューラSC1において、全ての入力ポートが送出権を得ていないからである。もし、時刻ｔ＝４の第２スケジューラSC2における情報が第１スケジューラSC1に移行しているならば、時刻t=5における第１スケジューラSC1において、送出権を得ている入力ポートが存在することになるからである。
【００２２】
各入力ポートIP１〜IP３からリクエスト信号を受信しても、受信権を得ている出力ポートは存在しないので、各出力ポートOP１〜OP３の第３スケジューラSC3および第４スケジューラSC4における判定部は、１つ以上のリクエスト信号を受信した場合に、最も大きな待ち時間を送出した入力ポートIP１〜IP３の判定部に許可信号を送出する。即ち、図４Bに示すように、出力ポートOP１にある第３スケジューラSC3および第４スケジューラSC4における判定部は、それぞれ入力ポートIP１およびIP２の第１スケジューラSC1および第２スケジューラSC2における判定部からリクエスト信号を受信したので、これらのリクエスト信号のうちで最も大きな待ち時間（ｔ＝１）でリクエスト信号を送出した入力ポートIP１の第１および第２スケジューラSC1およびSC2の判定部へそれぞれ許可信号を送出する。出力ポートOP２にある第３スケジューラSC3および第４スケジューラSC4における判定部は、入力ポートOP１、OP２およびOP３にある第１スケジューラSC1および第２スケジューラSC2における判定部から、到着時刻ｔ＝４，ｔ＝１およびｔ＝２のリクエスト信号をそれぞれ受信したので、これらのリクエスト信号のうちで最も大きな待ち時間（ｔ＝１）でリクエスト信号を送出した入力ポートIP２の第２スケジューラSC2における判定部へ許可信号を送出する。同様に、出力ポートOP３にある第３スケジューラSC3および第４スケジューラSC4における判定部は、入力ポートIP１およびIP３の第１スケジューラSC1および第２スケジューラSC2における判定部から到着時刻ｔ＝３およびｔ＝１のリクエスト信号を受信したので、これらのリクエスト信号のうちで最も大きな待ち時間（ｔ＝１）でリクエスト信号を送出した入力ポートIP３の第１スケジューラSC1および第２スケジューラSC2における判定部へ許可信号を送出する。
【００２３】
各入力ポートの第１スケジューラSC1および第２スケジューラSC2における判定部が、１つ以上の許可信号を受信した場合には、最も大きな待ち時間を有する許可信号を送出した出力ポートの判定部へ確認信号を送出する。即ち、この場合には、図４Cに示すように、入力ポートIP１の第１スケジューラSC1および第２スケジューラSC2における判定部は、それぞれ出力ポートOP１の第３スケジューラSC3および第４スケジューラSC4における判定部のみから許可信号を受信したので、出力ポートOP１の第３スケジューラSC3および第４スケジューラSC4の判定部へそれぞれ確認信号を送出する。入力ポートIP２の第１スケジューラSC1および第２スケジューラSC2における判定部は、それぞれ出力ポートOP２の第３スケジューラSC3および第４スケジューラSC4の判定部のみから許可信号を受信したので、出力ポートOP２の第３スケジューラSC3および第４スケジューラSC4における判定部へ確認信号をそれぞれ送出する。また、入力ポートIP３の第１スケジューラSC1および第２スケジューラSC2の判定部は、出力ポートOP３の第３スケジューラSC3および第４スケジューラSC4の判定部のみからそれぞれ許可信号を受信したので、出力ポートOP３の第３スケジューラSC3および第４スケジューラSC4の判定部へ確認信号をそれぞれ送出する。その結果、第１スケジューラSC1および第２スケジューラSC2において、入力ポートIP１，IP２およびIP３は、セル送出権を有する入力ポートとなり、第３スケジューラSC3および第４スケジューラSC4において、出力ポートOP１，OP２およびOP３はセル受信権を有する出力ポートとなる。
【００２４】
このようにして、入力ポートIP１〜IP３のセル送出権および出力ポートOP１〜OP３のセル受信権が確立されると、制御部１０（図1）によって、入力ポートIP１は出力ポートOP１へ、入力ポートIP２は出力ポートOP２へ、入力ポートIP３は出力ポートOP３へそれぞれｔ＝１に到着したセルを送出する。その結果、入力ポートIP１〜IP３の入力バッファ部における論理バッファQに残存するセルは図５のようになる。この場合、入力ポートIP１が出力ポートOP１へのセル送出権を得たという第１スケジューラSC2における情報は、入力ポートIP１が出力ポートOP１宛のセルを有していないことがセル数読み取り部１１(図1)により分かるので、情報移行部１０（図1）により第２スケジューラSC1へは移行されない。しかし、入力ポートIP２が出力ポートOP２へ、入力ポートIP３が出力ポートOP３へセル送出権を得たという第２スケジューラSC2における情報は、入力ポートIP２がまだ出力ポートOP２宛のセル(時刻ｔ＝３に到着したセル)を、入力ポートIP３もまだ出力ポートOP３宛のセル(時刻ｔ＝３に到着したセル)を有していることがセル数読み取り部により分かるので、情報移行部により第１スケジューラSC1へと移行される。
【００２５】
時刻ｔ＝６には、第１スケジューラSC1において、入力ポートIP２およびIP３の判定部は既にセル送出権を得ているので、何も行なわないが、入力ポートIP１の第１スケジューラSC1における判定部はセル送出権を得ていないので、送出できるセルを有する全ての出力ポートにある第３スケジューラSC3の判定部に対して、時刻情報読み取り部で取得した先頭セルの待ち時間を含んだリクエスト信号を送出する。即ち、この場合には、図６Aに示すように、入力ポートIP１の第１スケジューラSC1および第２スケジューラSC2における判定部は、出力ポートOP２とOP３にある第３スケジューラSC3および第４スケジューラSC4の判定部へそれぞれリクエスト信号を送出する。
【００２６】
入力ポートIP１の第２スケジューラSC2においては、その判定部は送出権を得ていなく、且つ情報も第１スケジューラSC1に移行していないので、送出できるセルを有する全ての出力ポートにある第４スケジューラSC4の判定部に対して、時刻情報読み取り部で取得した先頭セルの待ち時間を含んだリクエスト信号を送出する。即ち、この場合には、図６Aに示すように、入力ポートIP１の第２スケジューラSC2における判定部は、出力ポートOP２およびOP３にある第４スケジューラSC4の判定部へリクエスト信号を送出する。入力ポートIP２の判定部は、第２スケジューラSC2では送出権を得ていないが、出力ポートOP２への送出権を有するという情報は情報移行部から既に第１スケジューラSC1へ移行されている。よって、入力ポートIP２の第２スケジューラSC2における判定部は、送出できるセルを有する出力ポートOP２以外の全ての出力ポートにある第４スケジューラSC4の判定部に対して、時刻情報読み取り部で取得した先頭セルの待ち時間を含んだリクエスト信号を送出し、出力ポートOP２宛のセルを２セル以上保有している場合に、出力ポートOP２にある第４スケジューラSC4の判定部に対して、時刻情報読み取り部で取得した先頭から２番目のセルの待ち時間を含んだリクエスト信号を送出する。即ち、この場合には、図６Aに示すように、入力ポートIP２の第２スケジューラSC2の判定部は、出力ポートOP１の第４スケジューラSC4の判定部のみにリクエスト信号を送出する。入力ポートIP３の第２スケジューラSC2の判定部は送出権を得ていないが、出力ポートOP３への送出権を有するという情報は、情報移行部により既に第１スケジューラSC1に移行されていることからして、入力ポートIP３の第２スケジューラSC2の判定部は、送出できるセルを有する出力ポートOP３以外の全ての出力ポートにある第４スケジューラSC4の判定部に対して、時刻情報読み取り部で取得した先頭セルの待ち時間を含んだリクエスト信号を送出し、出力ポートOP３宛のセルを2セル以上保有している場合に、出力ポートOP３の第４スケジューラSC4における判定部に対して、時刻情報読み取り部で取得した先頭から2番目のセルの待ち時間を含んだリクエスト信号を送出する。即ち、この場合には、図６Aに示すように、入力ポートIP３の第２スケジューラSC2における判定部は、出力ポートOP２にある第４スケジューラSC4の判定部のみにリクエスト信号を送出する。
【００２７】
第３スケジューラSC3において、出力ポートOP２およびOP３は既にセル受信権を得ており、出力ポートOP１のみが、セルがないから情報が移行されておらず、受信権を得ていないが、出力ポートOP１の判定部は、リクエスト信号を受信しなかったので、許可信号を送出しない。即ち、この場合には図6Bに示すように、出力ポートOP１〜OP３の第３スケジューラSC3における判定部はいずれも入力ポートIP１〜IP３へ許可信号を送出しない。
【００２８】
しかし、スケジューラSC4において、受信権を得ている出力ポートは存在しないので、各出力ポートOP１〜OP３の判定部は、１つ以上のリクエスト信号を受信した場合に、最も大きな待ち時間を送出した入力ポートにある第２スケジューラSC2の判定部に許可信号を送出する。即ち、この場合には図６Bに示すように、出力ポートOP１の第４スケジューラSC4の判定部は、入力ポートIP２にある第２スケジューラSC2の判定部から、到着時刻ｔ＝２のリクエスト信号を受信したので、入力ポートIP２にある第２スケジューラSC2の判定部へ許可信号を送出し、出力ポートOP２の第４スケジューラSC4の判定部は、入力ポートIP１およびIP３にある各第２スケジューラSC2の判定部から、到着時刻ｔ＝４およびｔ＝２のリクエスト信号を受信したので、このうちで最も大きな待ち時間を送出した入力ポートIP３にある第２スケジューラSC2の判定部へ許可信号を送出し、また、出力ポートOP３の第４スケジューラSC4の判定部は、入力ポートIP１にある第１スケジューラSC2の判定部から、到着時刻ｔ＝３のリクエスト信号を受信したので、入力ポートIP１にある第２スケジューラSC2の判定部へ許可信号を送出する。
【００２９】
第１スケジューラSC1においては、どの入力ポートの判定部も許可信号を受信しなかったので、入力ポートIP１〜IP３からは確認信号は送出されない(図6C)。
【００３０】
しかし、各入力ポートIP１〜IP３の第２スケジューラSC2における判定部は、１つ以上の許可信号を受信した場合に、最も大きな待ち時間を送出した出力ポートにある第４スケジューラSC4の判定部へ確認信号を送出するのであって、この場合には図６Cに示すように、入力ポートIP１の第２スケジューラSC2における判定部は、出力ポートOP３にある第４スケジューラSC4の判定部のみから許可信号を受信したので、出力ポートOP３にある第４スケジューラSC4の判定部へ確認信号を送出し、入力ポートIP２の第２スケジューラSC2における判定部は、出力ポートOP１にある第４スケジューラSC4の判定部のみから許可信号を受信したので、出力ポートOP３にある第４スケジューラSC4の判定部へ確認信号を送出し、また、入力ポートIP３の第２スケジューラSC2の判定部は、出力ポートOP２にある第４スケジューラSC4の判定部のみから許可信号を受信したので、出力ポートOP２の第４スケジューラSC4の判定部へ確認信号を送出する。その結果、第１スケジューラSC1において、入力ポートIP２およびIP３はセル送出権を有する入力ポートとなり、第３スケジューラSC3において、出力ポートOP２およびOP３はセル受信権を有する出力ポートとなる。また、第２スケジューラSC2においては、入力ポートIP１が出力ポートOP３に対して、入力ポートIP２が出力ポートOP１に対して、入力ポートIP３が出力ポートOP３に対してそれぞれセル送出権を有する入力ポートとなり、第４スケジューラSC4においては、出力ポートOP１が入力ポートIP２に対して、出力ポートOP２が入力ポートIP３に対して、出力ポートOP３が入力ポートIP１に対してそれぞれセル受信権を有する出力ポートとなる。
【００３１】
このようにして、入力ポートIP１〜IP３のセル送出権および出力ポートOP１〜OP３のセル受信権が確立されると、制御部１０(図１)によって、入力ポートIP２は出力ポートOP２へ、入力ポートIP３は出力ポートOP３へ、それぞれスケジューラSC1とSC3とで選定されたｔ＝３に到着したセルを送出する。その結果、各入力ポートにおける入力バッファ部の論理バッファQに残ったセルは図７のようになる。従って、第２スケジューラSC2における入力ポートIP１が出力ポートOP３へ、入力ポートIP２が出力ポートOP３３へ、入力ポートIP３が出力ポートOP２へセル送出権を得たという情報は、入力ポートIP１が出力ポートOP３宛のセルを、入力ポートIP２が出力ポートOP１宛のセルを、入力ポートIP３が出力ポートOP２宛のセルを有していることがセル数読み取り部１１(図１)により分かるので、情報移行部１０(図１)によって第１スケジューラSC1へ移行される。
【００３９】
【発明の効果】
以上説明したように、本発明によれば、入力バッファ型スイッチにおいて、従来のスイッチング方法よりも短時間で、どの入力ポートからどの出力ポートへセルを送出すべきかを決定することができる。
【図面の簡単な説明】
【図１】  本発明によるスイッチング装置の入力ポートにおけるシステム構成を示すブロック図である。
【図２】  本発明によるスイッチング装置の出力ポートにおけるシステム構成を示すブロック図である。
【図３】  本発明の具体例を説明するためのスイッチング装置の概略図である。
【図４】  A〜Cは、本発明によるスイッチング方法にて、どの入力ポートからどの出力ポートへセルを送出すべきかを決定するためのステップの一過程を示した説明図である。
【図５】  本発明の具体例を説明するためのスイッチング装置の概略図である。
【図６】  A〜Cは、図４A〜ず４Cに続くステップの一過程を示した説明図である。
【図７】  本発明の具体例を説明するためのスイッチング装置の概略図である。
【符号の説明】
IP  入力ポート
OP  出力ポート
SC1  第１スケジューラ
SC2  第２スケジューラ
SC3  第３スケジューラ
SC4  第4スケジューラ
Q１〜Qｎ  論理バッファ
１  時刻情報付与部
２  タイムカウント部
３  セル識別部
４  入力バッファ部
５，６  時刻情報読み取り部
７，８  判定部
９  制御部
１０  情報移行部
１１  セル数読み取り部
１２、１３  判定部
【図１】
0003652237.tif 000002
【図２】
0003652237.tif 000003
【図３】
0003652237.tif 000004
【図４】
0003652237.tif 000005
【図５】
0003652237.tif 000006
【図６】
0003652237.tif 000007
【図７】
0003652237.tif 000008