分散型スイッチファブリックシステム
【課題】 各交換部が非同期動作する分散型スイッチにおいて、交換容量が低下しない分散・復元動作を実現し、複数スイッチから順不同に到着するセルをフロー内及びパケット内で元通りに復元する復元動作を、小容量のハードウェアで実現する。
【解決手段】 分散部１００では同じ宛先への可変長パケットを固定長セルに分割後、スイッチ数の整数倍個ずつ送信し、整列部３００では各交換部（交換部１〜交換部Ｍ）から順不同に到着するセルを受信バッファに保持したまま、ヘッダ情報だけを分離して再検査キューに保持し、受信時の順番検査またはキューの再検査でフロー中の先頭と判明したら対応するセル本体を受信バッファから抜出してセル順番を復元し、パケットを再生する。
【解決手段】 分散部１００では同じ宛先への可変長パケットを固定長セルに分割後、スイッチ数の整数倍個ずつ送信し、整列部３００では各交換部（交換部１〜交換部Ｍ）から順不同に到着するセルを受信バッファに保持したまま、ヘッダ情報だけを分離して再検査キューに保持し、受信時の順番検査またはキューの再検査でフロー中の先頭と判明したら対応するセル本体を受信バッファから抜出してセル順番を復元し、パケットを再生する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルータ、サーバ、ストレージ装置などにおいて、装置内部に有する複数の機能ブロックを動的に相互に接続するスイッチ技術に関する。特に、独立動作する複数のスイッチを利用し、宛先でデータの到着順序が入れ替わる場合に、順番通りに並べ替えるための技術に関する。
【背景技術】
【０００２】
ルータなどのネットワーク転送装置やサーバ装置、複数のディスクアレイを接続するストレージ装置などでは、装置内部の機能ブロック間でデータ交換を行うためにスイッチファブリックが利用される。スイッチファブリックの交換容量は、ポート数とポート容量（回線速度）の積で表現され、大交換容量を実現するためには、ポート数とポート容量のいずれか片方、もしくは両方を増加させる必要がある。
【０００３】
ポート数を増加させるには、要素スイッチを多段結合し、オメガ網やクロス網、ファットツリー網等を形成することにより実現が可能である。また、スイッチＬＳＩ（Large Scale Integration）のポート容量を増加させることでポート容量を増加させることも可能であるが、ＬＳＩに実装可能なピン数は、その時代のＣＭＯＳ（Complementary MOS）の実装限界によって制限されるため、大容量ポートを実現すると、スイッチＬＳＩあたりのポート数は減少する。
【０００４】
ここで、大容量ポートを少数持つスイッチＬＳＩを多段結合することでスイッチファブリック全体の交換容量を向上することは可能であるが、総ポート数を大きくするに従って接続段数が大きくなり、結果としてスイッチファブリック通過のレイテンシが大きくなる問題、また、宛先が異なってもスイッチファブリック内で衝突が発生してスループットが低下する問題が発生する。これらの問題を回避して、目的の交換容量を実現する方法として、分散型スイッチ(パラレルパケットスイッチ)が知られている。
【０００５】
分散型スイッチでは、要求容量の1／Ｍの容量のポートを備える比較的低速なスイッチＬＳＩをＭ個用意し、スイッチファブリックの入力にあたる分散部において、入力データを分割して各スイッチへ分散して通過させることで所望の大交換容量を実現する。一般に、ネットワーク装置で利用されるスイッチの場合、入力データは可変長のパケットであり、パケットは固定長のセルと呼ばれる単位に分割される。
【０００６】
分散型スイッチを最も容易に構成する場合、交換部用に用いる複数のスイッチＬＳＩを完全に同期させ、更に完全に同一の宛先調停動作を実施する。よって、宛先には、完全に予測可能なタイミングで順番通りにセルが到着するため、容易にパケットを元通りに復元可能であり、更にフロー内のパケット順番も容易に復元可能である。
【０００７】
ところが、近年、スイッチに要求されるポート容量、交換容量は非常に大きくなっており、分散型スイッチを構成する各スイッチＬＳＩ自体も高速してきている。例えば、ＬＳＩ間の通信には、ＳｅｒＤｅｓ（SERialization/DE-Serialization）と呼ばれる高速シリアル伝送が利用されたり、セルの交換処理ピッチも短縮化されたりしているため、各スイッチＬＳＩを完全同期させることが事実上困難である。よって、各スイッチが非同期動作する、すなわち、各スイッチが独立して宛先調停を行なう分散型スイッチが必要である。
【０００８】
各交換部が非同期動作する分散型スイッチでは、スイッチファブリックの入力にあたる分散部でのセルの送信順番と、スイッチファブリックの出力にあたる整列部でのセルの到着順番が一致することが保証されない。よって、同一送信元から同一宛先を目指すパケット群（フロー）内のセルの順番を元通りに復元し（フロー復元）、更にパケットを元通りに復元（パケット復元）しなくてはならない。
【０００９】
ＵＳ２００４/０１４３５９３（Ａ１）では、パケットのシーケンス番号（整理番号）、送信元番号、ルーティングインデックス（単一の宛先、もしくは複数の宛先の組合せを参照するための値）、優先度を利用して、宛先において各フローのパケットを十分な量溜め込んだのち、パケット順番を元通りに復元する方法が開示されている。しかしながら、ＵＳ２００４/０１４３５９３（Ａ１）のパケット順番復元方法は、送信元番号、ルーティングインデックス、優先度の積で表現される数のフローについて、十分な量のパケット保持機構が必要と考えられ、ハードウェア量が多くなりうる課題を持つ。
【００１０】
ＷＯ０２/４３３２９（Ａ１）では、同一のパケットから生成したセルには、宛先番号、送信元番号、セル分割番号の他、同一のタイムスタンプを付加し、スイッチファブリックの各部で共通の時計を利用して、スイッチ内ではタイムスタンプの古いものを優先して選択し、スイッチの宛先では、同一のフローに属するセル、パケットをタイムスタンプの値が古いものから順に順序復元を行う方法が開示されている。しかしながら、ＷＯ０２/４３３２９（Ａ１）のセル、パケット順番復元方法は、送信元番号、ルーティングインデックスの積で表現される数のフローについて、十分な量のパケット保持機構が必要と考えられ、ハードウェア量が多くなりうる課題を持つ。また、スイッチファブリック各部で共通の時計を利用し、その時刻を元に並べ替えを行う点も、パケットやセルの転送速度が向上するにつれて困難になりうる課題を持つ。
【００１１】
ＵＳＰ６８３２２６１（Ｂ１）では、セル、パケット順序復元用のデバイスを複数個用いて、互いに交信しつつセル、パケットの順序復元を行う方法が開示されている。ＵＳＰ６８３２２６１（Ｂ１）の実施例から、送信元スロット（送信元番号）、シーケンス番号（整理番号）、宛先スロット（宛先番号）の積で表現される数のフローについて、十分な量のパケット保持機構が必要と考えられ、ハードウェア量が多くなりうる課題を持つ。
【００１２】
また、ＵＳＰ６８３２２６１（Ｂ１）は、スイッチファブリックの出力にあたる整列部を主眼にかかれているため、明記されていないが、ＵＳ２００４/０１４３５９３（Ａ１）とＷＯ０２/４３３２９（Ａ１）では、各スイッチの負荷に応じて、スイッチファブリックの入力にあたる分散部においてロードバランスを取りながら分散動作を行うことが開示されている。しかしながら、一般に、単純なロードバランス動作を行うと、輻輳状態にあるスイッチに溜まっているセルやパケットが目的の宛先、すなわち、スイッチファブリックの出力にあたる整列部に到着する前に、後続のセルやパケットが非輻輳状態のスイッチを経由して到着しうる。よって、整列部においてセルやパケットの順番を復元するために、整列部は大量のセルやパケットの保持が必要であり、ハードウェア量が多くなりうる課題を持つ。
【００１３】
以上のように、従来の、各交換部が非同期動作する分散型スイッチでは、整列部におけるフロー復元、パケット復元の手法に関して開示されているが、いずれの手法もハードウェア量が多くなりうる課題を持っている。分散型スイッチは、スイッチ全体の交換容量を向上させることが本来の目的であるため、分散動作、復元動作によって交換容量が低下しないように潤沢なハードウェアを搭載していると考えることもできるが、装置を低コスト化するためには、より小規模のハードウェアで実現可能な整列部を持つ分散型スイッチが望まれる。
【００１４】
【特許文献１】ＵＳ２００４/０１４３５９３（Ａ１）
【特許文献２】ＷＯ０２/４３３２９（Ａ１）
【特許文献３】ＵＳＰ６８３２２６１（Ｂ１）
【発明の開示】
【発明が解決しようとする課題】
【００１５】
各交換部が非同期動作する分散型スイッチにおいて、交換容量が低下しない分散動作、復元動作を実現することが課題である。また、複数のスイッチから順不同に到着するセルを、フロー内及びパケット内で元通りに復元する方法を小容量のハードウェアで実現することが課題である。
【課題を解決するための手段】
【００１６】
スイッチファブリックの入力部で、同じ宛先への1個以上の可変長データを固定長データに分割後、スイッチ数の整数倍個ずつ送信し、スイッチファブリックの各交換部で同一送信元の固定長データは順番を維持したまま、固定長データ単位で宛先毎出力調停を行う。スイッチファブリックの出力部では、受信バッファに固定長データを保持したまま、固定長データの送信元番号とフロー番号によってフローの区別を行い、現在の先頭番号を、当該固定長データの整理番号と比較し、一致すればフローの先頭とみなす。不一致であれば当該固定長データを一時保持し、後続の固定長データの整理番号の確認とともに、一時保持した固定長データの整理番号の再確認を繰り返し、最終的に一致したものをフローの先頭とみなす。フロー先頭となった固定長データは、更に送信元番号とフロー番号が同じものの中でパケット先頭及びパケット末尾を検出してパケットを復元する。
【発明の効果】
【００１７】
本発明を利用することにより、各スイッチが非同期動作する分散型スイッチにおいて、交換容量が低下しない分散動作、復元動作を実現可能となる。また、複数のスイッチから順不同に到着するセルを、フロー内及びパケット内で元通りに復元する方法を小容量のハードウェアで実現することが可能となる。よって、従来方法より少ないコストで、高い交換容量の分散型スイッチを構成可能となる。
【発明を実施するための最良の形態】
【００１８】
以下、より詳細な内容を添付図面に基づいて実施例で説明する。
【実施例１】
【００１９】
本発明における分散型スイッチ構成の一実施例を図１に示す。分散型スイッチは、スイッチファブリックの入力にあたるN個の分散部１００、データ交換を行うM個の交換部２００、スイッチファブリックの出力にあたるN個の整列部３００で構成する。尚、図１は、構成を明快にするために分散型スイッチの一部のみを図示しているが、入出力の数、交換部の数は様々な組合せが可能であり、例えば、入出力が４個、交換部が３個の分散型スイッチを構成する場合の全体像は、図２に示す通りである。すなわち、４個の分散部１００−｛１〜４｝、３個の交換部２００−｛１〜３｝、４個の整列部３００−｛１〜４｝で構成される。
【００２０】
まず、各部の役割を簡単に紹介する。分散部１００は、受信した可変長のパケットを固定長のセルに分割し、複数の交換部２００へ送信し、宛先の整列部３００では、受信したセルを元通りの順番に直してパケットとして出力する。図２で、交換部２００−｛１〜３｝は互いに独立に動作する、すなわち、入力セルに対して互いに独立に宛先調停を自立的に行うため、スイッチファブリック全体では非同期型の分散スイッチとして振る舞うことになる。
【００２１】
ここで、各スイッチが非同期動作する分散型スイッチにおいて、交換容量が低下しない分散動作、復元動作を実現しつつ、複数のスイッチから順不同に到着するセルを、フロー内及びパケット内で元通りに復元する方法を小容量のハードウェアとメモリで実現するためには、次の２点を満足する必要がある。
【００２２】
１点目は、スイッチファブリックの交換帯域を完全に活用すること、すなわち、各分散部が、各交換部に対して同量のセルを分散し、各整列部が、各交換部から同量のセルを受信できるようにすることである。２点目は、各整列部が受信するセルの順番乱れの量を極力少なくすることである。
【００２３】
各スイッチが非同期動作する一般的な分散型スイッチでは、各交換部２００に可変長パケットをそのまま分散してしまうと、長いパケットを送信した交換部２００は負荷が高く、短いパケットを送信した交換部２００は負荷が低くなる。そこで、可変長パケットを固定長のセルに分割し、１セルずつ順番に各交換部２００へ送信することで前記不均衡を緩和できる。
【００２４】
しかしながら、単純に１セルずつ順番に各交換部２００へ送信するだけでは、ある分散部１００から、ある整列部３００へ到着するセルは、特定の交換部２００だけを経由することがありうる。例えば、図２の分散型スイッチでも、パケット長が短く、１パケットから１セルだけが生成され、全分散部１００に入力される各パケットの宛先が、１、２、３、１、２、３、１、２、３と繰り返される場合、各分散部１００は、全ての交換部２００に順次セルを送り出すのだが、宛先１行きのセルは、交換部２００−１だけしか通過しない。同様に宛先２行きのセルは、交換部２００−２だけしか通過しないし、宛先３行きのセルは、交換部２００−３だけしか通過しない。整列部３００−１からみると、全ての分散部１００−１、１００−２、１００−３、１００−４からのセルが交換部２００−１からだけ到着するように見える。
【００２５】
前記状況は、分散部１００から観測すると、ある宛先に対しては、特定の交換部２００の負荷が高くなるように見えるため、後続のパケットから生成したセルを負荷が低い別の交換部２００を経由して整列部３００へ送信して、全ての交換部２００に対する不均衡をなくすような動作が必要になる。この不均衡をなくすため動作は、一般にロードバランスをとる動作として知られている。
【００２６】
一旦、ロードバランス動作が発生すると、ある宛先から早期に送信されたセルがある交換部２００に滞留している間に、後続のセルが別の交換部２００を経由して先に目的の整列部３００に届きうるため、整列部３００におけるセルの到着順番を大きく乱す原因にもなる。そして、背景技術でも述べたように、整列部３００でのセルの到着順番が大きく乱れる場合、整列部３００はセルやパケットの順番を復元するために、大量のセルやパケットの保持が必要であり、ハードウェア量が多くなりうる課題を持つ。
【００２７】
そこで、本発明では、分散部１００から、全ての交換部２００に、同一宛先のセルを可能な限り均等に送信することによって、全ての交換部２００の均等利用、及び、整列部３００の各送信元１００から全ての交換部２００を経由したセルの均等受信を実現する。
【００２８】
分散部１００における、より具体的なセル分散方法について図３を利用して説明する。可変長パケットはネットワーク１１１を経由して分散部１００に入力され、フロー番号割当器１１０に到着する。フロー番号割当器１１０では、整列部３００で受信セルの属する元のパケットの種類を区別するために、フロー番号を割当てる。宛先がひとつであるユニキャストを扱うだけであれば、前記区別のためにフロー番号は必要ないが、宛先が複数であるマルチキャストを扱う場合、整列部３００では、どのパケットに属するセルか区別するためのフロー番号が必要となる。フロー番号は、最大で２のポート数乗のオーダーの数が必要であるが、実際にはあらゆる宛先の組み合わせのマルチキャストパケットが連続して出現するわけではないので、２の８乗から１０乗程度のフロー番号があれば十分である。
【００２９】
パケットにフロー番号を付与したあと、スイッチファブリックの宛先、及び優先度毎に独立したＦＩＦＯ（FＦｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）キューであるＶｉｒｔｕａｌ Ｏｕｔｐｕｔ Ｑｕｅｕｅ（ＶＯＱ）１２０の対応するＶＯＱへパケットを保持する。マルチキャスト用のＶＯＱは、優先度毎に１本ずつであり、どのような宛先の組み合わせのマルチキャストも、対応する優先度の前記マルチキャスト用ＶＯＱに保持する。各ＶＯＱには、パケットのたまり具合を検出するために、パケット量カウンタを備える。また、パケットが入力されてから取り出しが行なわれるまでの時間を計測するタイマーを備える。
【００３０】
ＶＯＱ１２０では、各ＶＯＱのパケットの溜まり具合を監視し、可変長パケットを固定長セルに分割した際に、前記セルの数が交換部２００の数、例えば、図２の場合は、３を越えた場合に当該ＶＯＱを出力対象とする。複数のＶＯＱが出力対象となっている場合は、優先度の高いものの中からラウンドロビンなどのアルゴリズムを利用してひとつを選択する。そして、クレジットテーブル１６０を参照し、交換部２００群の当該宛先がセルを受信可能かどうか調査する。
【００３１】
クレジットテーブルとは、宛先の受信バッファの空き容量を前記受信バッファが受信可能なセルの数をクレジットと呼んで管理するための機構である。図２のスイッチファブリックの場合のクレジットテーブル１６０の例を図９に示す。クレジットテーブルのエントリは、宛先毎に独立しており、更に各交換部用に独立している。本例では、いずれも８ずつクレジットを持っていることを示しており、各宛先の各交換部は、８個までセルを受信可能であることを示す。また、ＶＯＱ１２０が参照するための宛先毎に全交換部のクレジットを合計したＶＯＱ参照用合計クレジット１６５を持つ。
【００３２】
図４に示すフローチャートを利用して、ＶＯＱからのパケット抜出し方法の一実施形態を説明する。まず、ステップＳ６００において、ＶＯＱ１２０の中にタイマーがあらかじめ設定した時間を経過した（タイムアウトした）ものがあれば、最優先で選択候補とする。そして、ステップＳ６０５において、何らかのアルゴリズムで選択したＶＯＱのＶＯＱ参照用合計クレジット１６５が正であれば、ステップＳ６０６において、選択したＶＯＱから溜まっているパケット群を取り出し、パケット分割器１３０の対応するＦＩＦＯキューに書き込み、書き込んだＦＩＦＯキューをタイムアウト扱いにする。また、取り出した分のパケットに相当するクレジットを対応するＶＯＱ参照用合計クレジット１６５から減算する。
【００３３】
ステップＳ６００において、タイムアウトしたＶＯＱが無ければ、ステップＳ６０１においてマルチキャスト用のＶＯＱ群にパケットがあれば選択候補とする。そして、ステップＳ６０３において、該当する宛先全てのＶＯＱ参照用合計クレジット１６５が正であれば、ステップＳ６０４において、選択したＶＯＱから溜まっているパケット群を取り出し、パケット分割器１３０の対応するＦＩＦＯキューに書き込む。また、取り出した分のパケットに相当するクレジットを対応するＶＯＱ参照用合計クレジット１６５から減算する。
【００３４】
ステップＳ６０１においてマルチキャスト用のＶＯＱ群にパケットがなく、ステップＳ６０２において、ユニキャストＶＯＱのいずれかのパケット群から生成されるセル量が交換部の数以上であれば選択候補とする。そして、ステップＳ６０３において、何らかのアルゴリズムで選択したユニキャストＶＯＱのＶＯＱ参照用合計クレジット１６５が正であれば、ステップＳ６０４において、選択したＶＯＱから溜まっているパケット群を取り出し、パケット分割器１３０の対応するＦＩＦＯキューに書き込む。また、取り出した分のパケットに相当するクレジットを対応するＶＯＱ参照用合計クレジット１６５から減算する。
【００３５】
尚、ＶＯＱ１２０で消費したＶＯＱ参照用合計クレジット１６５は、交換部から配線２７０経由で回復クレジットが到着した際に、回復クレジットに示されている量だけ回復させる。
【００３６】
パケット分割器１３０は、パケットをセルに分割するための機構である。各宛先へのユニキャスト用のＦＩＦＯキューを１本ずつ持ち、マルチキャスト用のＦＩＦＯキューを１本だけ持つ。各ＦＩＦＯキューの入力はパケット、出力はセルであり、セル化途中のパケットを保持する。また、各ＦＩＦＯキューは、パケットが入力されてから当該パケットが取り出されるまでの時間を計測するタイマーを備える。
【００３７】
図５に示すフローチャートを利用して、パケット分割器１３０の各ＦＩＦＯキューのセル出力方法の一実施形態を説明する。まず、ステップＳ６１０において、タイマーがタイムアウトしたＦＩＦＯキューがあれば、最優先で選択候補とする。タイムアウトしたものがなく、マルチキャストのＦＩＦＯキューにパケットが存在すれば、ステップＳ６１１においてマルチキャストのＦＩＦＯキューを選択する。マルチキャストのエントリも無く、ユニキャストのＦＩＦＯキューにエントリがあれば、ユニキャストＦＩＦＯキューのエントリがあるものの中から、ひとつを選択する（Ｓ６１３）。
【００３８】
ここで、セル割当器１４０について先に説明を加える。パケット分割器１３０のもつ各ＦＩＦＯキューに対応するＦＩＦＯキューがセル割当器１４０にもあり、こちらのＦＩＦＯキューはセルだけを保持する。セル割当器１４０のＦＩＦＯキューが一杯で受付不能の場合、同じ宛先のパケット分割器１３０のＦＩＦＯキューにバックプレッシャを与え、当該ＦＩＦＯキューからのセルをセル割当器１４０へ渡すことを禁止する。
【００３９】
再び、図５のフローチャートのステップＳ６１４の説明に戻る。先に説明したセル割当器１４０からステップＳ６１３で選択したＦＩＦＯキューがバックプレッシャを受けていれば、ステップＳ６１８へ進み、当該ＦＩＦＯキューのタイマーがスタートしていなければタイマーをスタートさせ、当該ＦＩＦＯキューからのセル抜出しを行なわず、ステップＳ６１０のチェックに戻る。
【００４０】
そうでなければ、ステップＳ６１５へ進み、選択したＦＩＦＯキューの先頭のパケットをあらかじめ定めた固定長に分割し、ヘッダ情報を追加してセル化し、まず１セル分だけセル割当器１４０へ送信する。ここで追加する前記ヘッダ情報は、当該パケットの属するフローのフロー番号と整理番号、パケットの先頭セルならＨｅａｄ情報、パケットの末尾セルならＴａｉｌ情報である。セル化が終了したパケットは消去する。尚、セル化を行っているＦＩＦＯキューがタイムアウトしているならば、セル割当器１４０の該当するＦＩＦＯキューもタイムアウト扱いにする。
【００４１】
ここで、前記のフロー番号は、フロー番号割当器１１０で得た値である。
【００４２】
また、前記の整理番号は、フロー番号毎にエントリを持つ整理番号管理メモリ１５０をフロー番号でアクセスすることによって獲得する値である。整理番号管理メモリ１５０の各エントリが管理する整理番号は、ゼロから始め、当該エントリにアクセスがあるたびに１ずつ増やしていき、最大値（セルがスイッチファブリックを通過する間に同じ番号が出現しない程度の値）に達したら再びゼロに戻す。
【００４３】
次にステップＳ６１６へ進み、選択していたＦＩＦＯキューのパケットのセル化が終了していなければ再度ステップＳ６１４へ戻る。ステップＳ６１６で、全パケットのセル化が完了すれば当該ＦＩＦＯキューのタイマーを（もしスタートしていれば）クリアし、ステップＳ６１０へ戻る。
【００４４】
次に、図６に示すフローチャートを利用して、セル割当器１４０の各ＦＩＦＯキューのセル受信方法の一実施形態を説明する。まず、ステップＳ６２０において、パケット分割器１３０からセル入力があるのを待つ。セル入力があれば、ステップＳ６２１において、当該ＦＩＦＯキューのタイマーが停止していればタイマーをスタートさせる。そしてステップＳ６２２において、当該ＦＩＦＯキューのエントリにセルを保持し、待機セル数を１増やす。また、ステップＳ６２３において、受信セルがタイムアウト情報を持っていれば、当該ＦＩＦＯキューをタイムアウト扱いにする。
【００４５】
次に、図７に示すフローチャートを利用して、セル割当器１４０の各ＦＩＦＯキューからのセル出力方法の一実施形態を説明する。セル割当器１４０は、セルを適切な交換部に割り当て、セル送信するための機構である。まず、ステップＳ６３０において、タイマーがタイムアウトしたＦＩＦＯキューがひとつ以上あれば、その中のひとつを選択する（Ｓ６４０）。タイムアウトしたものがなく、マルチキャストのＦＩＦＯキューにセルが存在すれば、ステップＳ６３１においてマルチキャストのＦＩＦＯキューを選択する（Ｓ６４０）。
【００４６】
セル割当器１４０は、セルを送信する交換部２００を指し示すためのスイッチポインタを備え、１セル送信する毎に次の交換部を指すようスイッチポインタを移動させる。例えば、図２に示すように交換部が三つある場合、スイッチポインタはセルを送信するたびに、交換部１→交換部２→交換部３→交換部１と順に移動させていく。ここで、ステップＳ６４１において、クレジットテーブル１６０を参照し、スイッチポインタの指す交換部の全ての対象となる宛先のクレジット１６１が正であるか確認する。
【００４７】
前記のクレジット１６１が負であれば、セルを送信することができないので当該ＦＩＦＯキューのセル送信は中断し、ステップＳ６３０へ戻る。
【００４８】
前記のクレジット１６１が正であれば、ステップＳ６４２において、選択したＦＩＦＯキューの先頭のセルに対し、追加のヘッダ情報として交換部番号（スイッチポインタの示す交換部番号）を付加し、対象となる交換部２００へ当該セルを送信する。そして、スイッチポインタを１ずらし、選択したＦＩＦＯキューの待機セル数を１減少させる。また、クレジットテーブル１６０の対象となる宛先の対象となる交換部のクレジット１６１を１減少させる。前記のセル送信により、選択したＦＩＦＯキューの待機セル数がゼロでなければ、ステップＳ６４３から、再度ステップＳ６４１に戻ってセル送信チェックを続ける。
【００４９】
ステップＳ６４３で、選択したＦＩＦＯキューの待機セル数がゼロになれば、全セルを送信したことになるので、ステップＳ６３７へ進み、当該ＦＩＦＯキューのタイマーをクリアし、ステップＳ６３０へ戻る。
【００５０】
ステップＳ６３１において、マルチキャストのＦＩＦＯにセルが存在しなければ、ステップＳ６３２に進み、待機セル数が交換部の数以上のユニキャストＦＩＦＯがあるか調べ、無ければステップＳ６３０へ戻る。あれば、ステップＳ６３３にて対象ＦＩＦＯのひとつを選択し、クレジットテーブル１６０の対象宛先の全ての交換部のクレジット１６１が正であるか確認する。全てが正でなければ、セル送信することはせず、ステップＳ６３０へ戻る。
【００５１】
対象宛先の全ての交換部のクレジット１６１が正であれば、ステップＳ６３５へ進み、選択したＦＩＦＯキューの先頭のセルに対し、追加のヘッダ情報として交換部番号（スイッチポインタの示す交換部番号）を付加し、対象となる交換部２００へ配線２４０経由で当該セルを送信する。そして、スイッチポインタを１ずらし、選択したＦＩＦＯキューの待機セル数を１減少させる。また、クレジットテーブル１６０の対象となる宛先の対象となる交換部のクレジット１６１を１減少させる。ここでは、セルを交換部と同じ数だけ送信するまでステップＳ６３５の操作を繰り返す。そして、ステップＳ６３７へ進み、当該ＦＩＦＯキューのタイマーをクリアし、ステップＳ６３０へ戻る。
【００５２】
尚、セル割当器１４０で消費した交換部毎のクレジット１６１は、交換部２００から配線２７０経由で回復クレジットが到着した際に、回復クレジットに示されている量だけ回復させる。
【００５３】
分散部１００と整列部３００を同一ＬＳＩ上に構成する場合、交換部２００から、整列部１００のクレジットテーブル１６０へ回復クレジットを送信する配線２７０は、交換部２００から整列部３００へセルを送信する配線２５０を共用することが可能である。具体的には、配線２５０経由で交換部２００から整列部３００へ送信するセルのヘッダ情報の一部に、交換部２００から分散部１００への回復クレジットを相乗りさせて送信することができる。
【００５４】
分散部１００と整列部３００を異なるＬＳＩ上に構成する場合、前記の回復クレジットを送信する配線２７０は、交換部２００から整列部３００へセルを送信する配線２５０とは別の専用の配線を利用する。
【００５５】
また、図８に、本発明におけるセル割当器１４０からパケット分割器１３０へのバックプレッシャ信号生成方法の一実施形態を示すフローチャートを示す。まず、ステップＳ６５０において、待機セル数が交換部の数より多いＦＩＦＯキューがあるか検査する。前記条件を満たせば、ステップＳ６５３においてパケット分割器１３０の対応するＦＩＦＯキューへバックプレッシャをかける。前記条件を満たさなければ、ステップＳ６５１において待機セル数と交換部数のＦＩＦＯキューがあるか調べ、該当するＦＩＦＯキューがあり、そのＦＩＦＯキューにセル出力が無く、セル入力があれば、ステップＳ６５３においてパケット分割器１３０の対応するＦＩＦＯキューへバックプレッシャをかける。ステップＳ６５１、ステップＳ６５２いずれの条件も満たさなければ、ステップＳ６５４において、パケット分割器１３０の対応するＦＩＦＯキューへのバックプレッシャを解除する。
【００５６】
以上、分散部１００において可変長パケットを固定長セルに分割し、全ての交換部２００に、同一宛先のセルを可能な限り均等に送信する具体的な実施例について説明した。本発明によれば、ユニキャストのパケットは、スイッチファブリックの備える交換部２００と同じ数ずつのセル単位で分散部１００から各交換部２００へ送信することができる。
【００５７】
あるパケットから交換部２００の数と異なる数のセルが生成される場合でも、ＶＯＱ１２０、パケット分割器１３０、セル分散器１４０の仕組みにより、余りとなるセルは次の同一宛先のユニキャストパケットから生成されるセルと一緒に、交換部２００の数と同じ数ずつだけ、各交換部２００へ送信することができる。また、前記の余りとなるセルが存在するときに、次の同一宛先のユニキャストパケットが到着しない場合は、タイムアウトの仕組みにより強制的に交換部２００へ送信することもできる。すなわち、交換部２００と同じ数のセル群の単位で送信した余りのセルが残った際にタイマを起動し、タイマの時間が所定の閾値に達したら、同一宛先の次のパケットの到着を待って待機しているこれら余りのセル群を、もはや待機させずに交換部２００に強制送信する強制送信機構を付け加える。
【００５８】
マルチキャストパケットの場合は、同じ複数の宛先の組合せのマルチキャストパケットが常に続くとは限らないため、ユニキャストパケットとは異なり、すぐに分散部１００から各交換部２００へ、送信するための仕組みを持たせている。
【００５９】
次に、図１０を用いて交換部２００の一実施例について説明する。交換部２００は、宛先毎のメモリ２１０で構成し、各入力からのセルは対応する宛先メモリ２１０に格納する。マルチキャストのセルの場合、対応するすべての宛先用メモリ２１０に格納する。各メモリ２１０の中は送信元毎に格納領域が決まっており、セルを受信後、各メモリでは、ラウンドロビンのような公平な選択アルゴリズムにより一つのセルを選び、当該宛先の整列部３００の受信バッファに空きがあれば、選択したセルを送信する。そして、前記の選択したセルの送信元である対応する分散部１００に対し、対応する配線２６０経由で回復クレジットを１セルにつき１ずつ返却する。
【００６０】
前記の宛先毎のメモリ２１０は、メモリ容量を削減するために、複数の宛先で共有し、時分割で利用してもよい。時分割でメモリ２１０を利用する場合、メモリ容量が削減される分、クレジットテーブル２２０が管理するクレジット量も減少する。
【００６１】
尚、前記の整列部３００の受信バッファに空きがあるか否かは、交換部２００が備えるクレジットテーブル２２０によって調べる。交換部２００の備えるクレジットテーブル２２０の構成例を図１１に示す。クレジットテーブル２２０は、各宛先毎に独立しており、それぞれの中で各送信元用のクレジット２２１を最低１ずつ、また、各送信元に共通のクレジット２２２を複数（図１１の例では８）備える。
【００６２】
交換部２００から整列部３００へセルを送信する際、送信するセルに対応する送信元用のクレジット２２１がゼロでなければ対応する送信元用のクレジット２２１を１減らし、ゼロであれば共通のクレジット２２２を１減らす。尚、クレジットは、整列部３００から回復クレジットが到着した際に、回復させる送信元の番号に対応する送信元用のクレジット２２１が最大値でなければ（図１１の例では１でなければ）、その対応する送信元用のクレジット２２１を１回復させる。そうでなければ、共通のクレジット２２２を１回復させる。
【００６３】
尚、分散部１００と整列部３００を同一ＬＳＩ上に構成する場合、整列部３００の回復クレジット生成器３７０から、交換部２００のクレジットテーブル２２０へ回復クレジットを送信する配線２６０は、分散部１００から交換部２００へセルを送信する配線２４０を共用することが可能である。具体的には、配線２４０経由で分散部１００から交換部２００へ送信するセルのヘッダ情報の一部に、整列部３００から交換部２００への回復クレジットを相乗りさせて送信することができる。
【００６４】
分散部１００と整列部３００を異なるＬＳＩ上に構成する場合、前記の回復クレジットを送信する配線２６０は、分散部１００から交換部２００へセルを送信する配線２４０とは別の専用の配線を利用する。
【００６５】
交換部２００の各宛先メモリ２１０は、セルを選択する際に、クレジットテーブル２２０の各送信元の共通クレジット２２２が正であれば、どのセルを選択してもよい。しかし、前記の共通クレジット２２２がゼロであれば、対応する送信元用のクレジット２２１が正であるセルの中からのみ選択する。このルールは、整列部３００でセルの順番復元を行なう際に、ある送信元からのセルが、他の送信元からのセルに邪魔されて交換部２００から永久に送信されずにデッドロックする状況を防ぐために用いる。
【００６６】
次に、図１２を用いて本発明の整列部３００の一実施形態を示す。整列部３００の概略動作についてまず説明する。整列部３００は、各交換部２００から配線２５０経由でセルを受信バッファ３１０へ受信する。そして、受信したセル本体は受信バッファ３１０に保持したまま、セルのヘッダ情報の一部と追加の情報をセレクタ３２０経由でフロー復元器３３０へ渡し、ひとつ以上のフロー復元器３３０にてフロー毎の先頭となるセルを検出する。
【００６７】
先頭セルを検出すると、そのうちひとつをセレクタ３４０で選び、受信バッファ３１０から該当するセルを抜出し、セレクタ３５０経由でパケット復元器３６０に前記のセルを渡す。同時に、対応する受信バッファ３１０に空き領域ができたことを回復クレジット生成器３７０に教える。回復クレジット生成器３７０は、セルを出力した受信バッファ３１０に対応する交換部２００に対し、前記のセルの持つ送信元番号を含めた回復クレジットを生成し、配線２６０経由で送信する。
【００６８】
パケット復元器３６０では、フロー毎にセルを一次保持する手段を持ち、分散部１００で付与したＨｅａｄ情報のセルを先頭に送信元番号とフロー番号の一致するセルを順番に保持し、同じく分散部１００で付与したＴａｉｌ情報のセルを受信したところでパケットとして復元を完了し出力する。
【００６９】
本発明の特長は、小規模の資源でフロー復元を可能にする点である。従来方法では、少なくとも、送信元番号、フロー番号の積で表現される数のフローにつき、順番乱れが発生した際に吸収可能な量のメモリ、例えば１００セル分格納できるメモリ、が必要である。よって、従来方法では、ハードウェア量、特に利用するメモリ量が非常に多くならざるを得ない。
【００７０】
本発明の整列部３００は、交換部２００と整列部３００の間でセルを送信し、回復クレジットを返信するまでの間に各交換部２００から送信される総セル量と同等程度の量の受信バッファ３１０のメモリだけで、セルの順番乱れを元通りに復元する仕組みを提供する。本発明の整列部３００が必要とする前記のメモリ量は、従来の整列部が持つメモリ量（少なくとも、送信元番号、フロー番号、順番乱れが発生した際に吸収可能なエントリ数の積で示されるメモリ量）より遥かに少なく、十分な低コスト化が望める。
【００７１】
尚、整列部３００に前記の非常に少ないメモリ量しか搭載しなくても、整列部３００において、セル順番復元が滞らないようにするためには、通常の状態において、非常に大きな順番乱れが発生しないようなセル分散が行われることが必須である。本発明では、分散部１００において、全ての宛先に対して、可能な限り全ての交換部２００を経由させるセル分散を行っているため、非常に大きな順番乱れは発生しにくいため、通常の状態では、問題を引き起こさない。
【００７２】
以下に、前記の非常に少ない受信バッファ３１０のメモリだけでセル順番を復元するフロー復元器３３０の詳細について説明する。
【００７３】
フロー復元器３３０は、送信元である分散部１００と同じ数だけ備えるのが望ましいが、複数の送信元で共有しても構わない。例えば、送信元が１６個ある場合、フロー復元器３３０を１６個備えるのが理想であるが、論理量の増加を抑えるために、フロー復元器３３０を８個だけ備え、特定の２個の送信元で特定の１個のフロー復元器３３０を共有させても構わない。同様に、フロー復元器３３０を４個だけ備え、特定の４個の送信元で特定の１個のフロー復元器３３０を共有させても構わない。
【００７４】
フロー復元器３３０の一実施例を図１３に示す。フロー復元器３３０は、整理番号管理メモリ３３２、整理番号比較器３３３、受信バッファ読み出しキュー３３５、再検査キュー３３６を備える。
【００７５】
交換部２００から受信したセルのヘッダ情報の一部と追加の情報を、入力４００経由で対応するフロー復元器３３０へ入力する。一般に、セル本体に比べセルのヘッダ情報はサイズが小さいため、数マシンサイクルに１回の割合で入力があることになる。ここで、前記のセルのヘッダ情報とは、送信元番号、フロー番号、整理番号である。また、前記の追加の情報とは、セル本体を記録した受信バッファ３１０内のアドレス、当該セルが通過した交換部２００の番号である。
【００７６】
フロー復元器３３０の内部では、前記の各種の情報を、キー情報、整理番号、データ情報の３種類の情報に分類する。
【００７７】
ここで、キー情報とは、整理番号管理メモリ３３２をアクセスするためのインデックスであり、本実施例では、送信元番号とフロー番号を結合したものである。
【００７８】
また、データ情報とは、受信バッファ３１０からセル本体を読み出すための情報であり、本実施例では、受信バッファ３１０内のアドレスと交換部２００の番号である。
【００７９】
ここで、図１４のフローチャートを利用して、図１３のフロー復元器３３０の動作に関して説明する。ステップＳ７００で、入力４００経由で交換部２００からのセル入力があれば、当該セルヘッダのキー情報で整理番号管理メモリ３３２を参照し、そのフローの現在の先頭にあたる整理番号を読み出す。
【００８０】
そして、ステップＳ７０３で、比較器３３３にて、入力したセルの整理番号と一致するか検査する。整理番号同士が一致すれば、ステップＳ７０４で、当該セルのデータ情報を受信バッファ読出しキュー３３５へ記録し、ステップＳ７０５で、加算器３３４を利用して、読み出していた整理番号に１を加え、整列番号管理メモリ３３２に書き戻す。
【００８１】
ステップＳ７０３で整理番号同士が一致しなければ、ステップＳ７０６で、当該セルのキー情報、整理番号、データ情報を再検査キュー３３６に積む。
【００８２】
また、ステップＳ７００で、入力４００経由で交換部２００からセル入力がなく、再検査キュー３３６にエントリがあれば、ステップＳ７０２で再検査キュー３３６の先頭のエントリを読出し、入力４２０経由で、前記の説明同様、整理番号管理メモリ３３２を参照し、ステップＳ７０３〜Ｓ７０５、またはＳ７０６の動作を繰り返す。
【００８３】
以上の動作を繰り返すことで、フロー復元器３３０に入力される、フロー順番の乱れたセル群は、各送信元の各種のフロー毎に送信された順番通りに受信バッファ読出しキュー３３５に積みなおされる。そして、受信バッファ読出しキュー３３５の先頭のエントリから順に出力４３０経由でデータ情報を読み出し、該当する受信バッファ３１０のセル本体を読み出せば、フロー内のセルの順番を完全に復元することができる。
【００８４】
図１７(a)、(b)に、本発明を利用した場合にパケットがどのように分散型スイッチファブリックを通過するかというイメージ図を、分散部１００−３、分散部１００−４から、整列部３００−１、整列部３００−２行きのパケットがあるという前提で示す。また、いずれのパケットもユニキャストパケットであるとしている。パケットを示す長方形や角丸長方形には、宛先が整列部３００−１であればＤ１、整列部３００−２であればＤ２とし、宛先毎のフロー内の番号をそのあとに記載している。可変長パケットから生成される固定長セル内に記載の番号も、同様であるが、セルに記載している「宛先毎のフロー内の番号」は、本実施例の文中に登場するフロー毎の「整理番号」である。尚、本例では、長方形は分散部１００−３入力、角丸長方形は分散部１００−４入力としている。
【００８５】
分散部１００−３入力の可変長パケット群５００−３、分散部１００−４入力の可変長パケット群５００−４は、各分散部１００において、それぞれ、対応する個数の固定長セル群５１０−３、５１０−４に分割される。
【００８６】
各分散部１００は、交換部２００が３個あるため、宛先毎に３の整数倍ずつセルを選んでセル群５２０−｛３、４｝｛Ａ、Ｂ、Ｃ｝として対応する交換部２００へ出力する。もともとのパケット長が３の倍数にならないような場合、一定時間が経過してタイムアウトが発生した際に出力する。例えば、分散部１００−３出力のＤ２−４のセルは、前記のタイムアウトが発生して出力されている様子を示している。前記のタイムアウトイベント発生後は、再び、宛先毎に３の整数倍ずつセルが選択できる状態であるので、Ｄ１−１０、Ｄ１−１１、Ｄ１−１２の３セルが連続して出力されている。
【００８７】
各交換部２００では、各分散部１００からの入力順番は維持したまま、宛先毎に出力調停を行い、セル群５３０｛Ａ、Ｂ、Ｃ｝−｛１、２｝として宛先である整列部３００へ送信する。
【００８８】
各整列部３００では、受信したセルを送信元毎、また、フロー毎（この場合は、ユニキャストが１フローずつあるのみ）に分類し、フロー内のセル順番を元通りのセル群５４０−｛１、２｝に復元し、更にそれぞれ元のパケット群５５０−｛１、２｝を復元する。
【００８９】
以上、本発明によるセル分散型スイッチについて詳細な説明を行った。本説明は、実施の一形態に過ぎず、本発明の技術的思想および技術的範囲から離れることなく、様々な変形が可能である。
【実施例２】
【００９０】
実施例１で説明した整列部３００よりも短時間でフロー復元可能な整列部を備える分散型スイッチファブリックを実施例２として説明する。ここで、実施例２の分散部１００、交換部２００の構成は図１等を用いて説明した実施例１のものと同一である。また、整列部３００の構成は、整列部３００内のフロー復元器を除いて同一である。よって、ここでは実施例２におけるフロー復元器３３０′の構成と動作を詳細に説明する。
【００９１】
実施例２のフロー復元器３３０′は、図１５に示すように、整理番号管理メモリ３３２、整理番号比較器３３３、受信バッファ読み出しキュー３３５、再検査キュー３３６に加え、連続整理番号生成器３３７、チェックエントリ３３８Ａ〜３３８Ｋ、連鎖選択器３４１を備える。ここで、チェックエントリとは、フローの先頭でなかったセルの、送信元番号、フロー番号、整理番号、セル本体を記録した受信バッファ３１０内のアドレス、当該セルが通過した交換部２００の番号を一時的に記録するための機構である。前記の各種情報は、交換部２００から受信して先頭検査を行なって先頭でなかった場合に記録する。以後、交換部２００からセルを受信するたびにチェックエントリ３３８Ａ〜３３８Ｋに一次記録してある情報も全て同時に検査を行う。
【００９２】
交換部２００からセルが当該フローの先頭であった場合、チェックエントリ３３８Ａ〜３３８Ｋのいずれかの内容がその次の先頭、更に別のチェックエントリの内容がその次の先頭、という具合に、次々と先頭が見つかる可能性がある。図１５のフロー復元器３３０では、交換部２００からセルが当該フローの先頭であった場合、更に、同時にチェックエントリ３３８Ａ〜３３８Ｋの中から最大で３個の連続する先頭セルを検出する。３個の連続する先頭セルの整理番号は、連続整理番号生成器３３７を利用して生成する。
【００９３】
尚、チェックエントリ３３８Ａ〜３３８Ｋで連鎖的に４個目以降の先頭セルが発見されうる。そこで、チェックエントリ３３８Ａ〜３３８Ｋの各々は、連鎖ビットと呼ぶ情報用のフィールドを備える。連鎖ビットは、前記の３個目の先頭であることを検出した時点で有効化する。そして、連鎖選択器３４１によって、連鎖ビットが有効になっているいずれかのチェックエントリの情報を選択し、入力４４０経由で、整理番号管理メモリ３３２で先頭検査を行なうことで、前記４個目以降の先頭セルの有無を調査する。
【００９４】
また、実施例２における受信バッファ読出しキュー３３５は、多入力１出力である。図１５に示す構成例では、３入力１出力である。３入力である理由は、チェックエントリ３３８の利用により、同時に、あるフローの先頭、その次、更にその次の３個の連続するセルが発見されうるためである。１出力である理由は、対応する受信バッファ３１０からセル本体を３個同時では無く、１個ずつ読み出すためである。尚、正確には、受信バッファ読出しキュー３３５からは同時に３情報を読み出し、整理番号＋０位置、整理番号＋１位置、整理番号＋２位置の順にひとつずつ出力４３０経由で出力し、対応する受信バッファ３１０のセル本体を読み出すことになる。
【００９５】
ここで、図１６のフローチャートを利用して、図１５のフロー復元器３３０′の動作に関して説明する。ステップＳ８００で、入力４００経由で交換部２００からセル入力があれば、当該セルヘッダのキー情報で整理番号管理メモリ３３２を参照し、そのフローの現在の先頭にあたる整理番号を読み出す。
【００９６】
そして、ステップＳ８０５で、比較器３３３にて、入力したセルの整理番号と一致するか検査する。整理番号同士が一致すれば、ステップＳ８１０で、当該セルのデータ情報を受信バッファ読出しキュー３３５の整理番号＋０位置へ記録する。また、当該セルとキー情報が同一であるチェックエントリ３３８の保持する整理番号が、連続整理番号生成器３３７で生成した「整理番号＋１」、「整理番号＋２」、「整理番号＋３」と一致するか検査する。
【００９７】
「整理番号＋１」、「整理番号＋２」、「整理番号＋３」全てがいずれかのチェックエントリで一致すれば、「整理番号＋１」のチェックエントリのデータ情報を受信バッファ読出しキュー３３５の整理番号＋１位置へ記録する。また、「整理番号＋２」のチェックエントリのデータ情報を受信バッファ読出しキュー３３５の整理番号＋２位置へ記録する。そして、「整理番号＋１」と「整理番号＋２」のチェックエントリの内容を消去し、「整理番号＋３」のチェックエントリの連鎖ビットを有効にする。整理番号管理メモリ３３２へは、当該フローのその後の先頭番号として「整理番号＋３」を書き戻す。（ステップＳ８１１→Ｓ８１２→Ｓ８１３→Ｓ８２２）
ステップＳ８１１の条件を満たさなければ、ステップＳ８２０で「整理番号＋１」、「整理番号＋２」両方がいずれかのチェックエントリで一致すれば、「整理番号＋１」のチェックエントリのデータ情報を受信バッファ読出しキュー３３５の整理番号＋１位置へ記録する。また、「整理番号＋２」のチェックエントリのデータ情報を受信バッファ読出しキュー３３５の整理番号＋２位置へ記録する。そして、「整理番号＋１」と「整理番号＋２」のチェックエントリの内容を消去する。整理番号管理メモリ３３２へは、当該フローのその後の先頭番号として「整理番号＋３」を書き戻す。（ステップＳ８１１→Ｓ８２０→Ｓ８２１→Ｓ８２２）
ステップＳ８２０の条件を満たさなければ、ステップＳ８３０で「整理番号＋１」がいずれかのチェックエントリで一致すれば、「整理番号＋１」のチェックエントリのデータ情報を受信バッファ読出しキュー３３５の整理番号＋１位置へ記録する。そして、「整理番号＋１」のチェックエントリの内容を消去する。整理番号管理メモリ３３２へは、当該フローのその後の先頭番号として「整理番号＋２」を書き戻す。（ステップＳ８１１→Ｓ８２０→Ｓ８３０→Ｓ８３１→Ｓ８３２）
ステップＳ８３０の条件を満たさなければ、ステップＳ８４０で整理番号管理メモリ３３２へは、当該フローのその後の先頭番号として「整理番号＋１」を書き戻す。（ステップＳ８１１→Ｓ８２０→Ｓ８３０→Ｓ８４０）
ステップＳ８０５で整理番号同士が一致しなければ、ステップＳ８０６で、チェックエントリ３３８のいずれかに空きエントリがあるか検査し、空きエントリがあれば、ステップＳ８０７にて、空きエントリのいずれかに、当該セルのキー情報、整理番号、データ情報を記録する。
【００９８】
また、ステップＳ８０６で、チェックエントリ３３８のいずれかに空きエントリがあるか検査し、空きエントリがなければ、ステップＳ８０８にて、再検査キュー３３６に、当該セルのキー情報、整理番号、データ情報を記録する。
【００９９】
また、ステップＳ８００で、入力４００経由で交換部２００からセル入力がなければ、ステップＳ８０１にて、チェックエントリ３３８Ａ〜３３８Ｋの連鎖ビットを検査する。そして、いずれかの連鎖ビットが有効であれば、ステップＳ８０４にて、それら有効な連鎖ビットをもつ、つまり連鎖ヒットしているチェックエントリの中からいずれかひとつを連鎖選択器３４１で選択し、選択したチェックエントリの保持する全情報を入力４４０経由でフロー復元器に再入力し、選択したチェックエントリの内容は消去する。
【０１００】
前記のチェックエントリ３３８Ａ〜３３８Ｋのいずれかから入力した整理番号は、連鎖ビットが有効であり、必ず整理番号管理メモリの対象となる整理番号と一致するので、ステップＳ８０５、ステップ８１０以下、先ほどの説明と同様の処理を行なう。
【０１０１】
また、ステップＳ８０１で、いずれのチェックエントリ３３８の連鎖ビットも有効になっていなければ、ステップＳ８０２において、再検査キュー３３６にエントリがあるかどうか検査する。
【０１０２】
再検査キュー３３６にエントリがあれば、ステップＳ８０３で再検査キュー３３６の先頭のエントリを読出し、ステップＳ８０５において、入力４２０経由で読み出した整理番号と、整理番号管理メモリ３３２の当該フローの整理番号が一致するかどうか検査し、以下、前記の説明同様、ステップＳ８０６以降、または、ステップＳ８１０以降の動作を繰り返す。
【０１０３】
以上、チェックエントリ３３８Ａ〜３３８Ｋを利用して、実施例１で説明した整列部３００より、短時間でフロー復元可能な整列部について詳細な説明を行なった。チェックエントリや、連続整理番号生成器３３７等はその搭載量に比例して論理資源が大規模化するため、十数個程度のチェックエントリ、＋３〜４程度の連続整理番号生成器３３７がリーズナブルと考えられる。チェックエントリ不足は、再検査キュー３３６の設置によって補うことができる。尚、論理資源の大規模化が共用範囲以内であると判断できれば、再検査キュー３３６は搭載せず、ある程度大量のチェックエントリ３３８を備える構成もとりうる。
以上、本発明によるセル分散型スイッチのフロー復元器について詳細な説明を行った。本説明は、実施の一形態に過ぎず、本発明の技術的思想および技術的範囲から離れることなく、様々な変形が可能である。
【産業上の利用可能性】
【０１０４】
本発明によるセル分散型スイッチにおける再整列方法は、大容量回線を利用したデータ交換が必要なシステムで利用することができる。例えば、ルータやスイッチに代表されるネットワーク装置内のスイッチファブリックや、サーバやストレージ機器の装置内のスイッチファブリック等での利用が考えられる。
【図面の簡単な説明】
【０１０５】
【図１】本発明の分散型スイッチの一実施形態の一部を示すブロック図である。
【図２】本発明の分散型スイッチの一実施形態を示すブロック図である。
【図３】本発明における整列部の一実施形態を示すブロック図である。
【図４】本発明におけるＶＯＱ抜出し方法の一実施形態を示すフローチャートである。
【図５】本発明におけるパケット分割器の出力方法の一実施形態を示すフローチャートである。
【図６】本発明におけるセル割当器の受信方法の一実施形態を示すフローチャートである。
【図７】本発明におけるセル割当器の出力方法の一実施形態を示すフローチャートである。
【図８】本発明におけるセル割当器からパケット分割器へのバックプレッシャ信号生成方法の一実施形態を示すフローチャートである。
【図９】本発明の分散部が管理する交換部のクレジットの説明図である。
【図１０】本発明の交換部の一実施形態を示すブロック図である。
【図１１】本発明の交換部が管理する整列部のクレジットの説明図である。
【図１２】本発明の整列部の一実施形態を示すブロック図である。
【図１３】本発明のフロー復元器の一実施形態を示すブロック図である。
【図１４】図１２のフロー復元の一実施形態を示すフローチャートである。
【図１５】本発明のチェックエントリを含むフロー復元器の一実施形態を示すブロック図である。
【図１６】図１４のフロー復元の一実施形態を示すフローチャートである。
【図１７ａ】本発明におけるパケット、セルの流れを示す説明図である。
【図１７ｂ】本発明におけるパケット、セルの流れ(続き)を示す説明図である。
【符号の説明】
【０１０６】
１００：分散部
１１０：フロー番号割当器
１２０：ＶＯＱ
１３０：パケット分割器
１４０：セル割当器
１５０：分散部の整理番号管理メモリ
１６０：分散部が管理する交換部のクレジットテーブル
２００：交換部
２１０：交換部が管理する整列部のクレジットテーブル
３００：整列部
３１０：受信バッファ
３３０：フロー復元器
３３２：整列部の整理番号管理メモリ
３３５：受信バッファ読出しキュー
３３６：再検査キュー
３３８：チェックエントリ
３６０：パケット復元器
３７０：回復クレジット生成器
５００：分散部入力パケット
５１０：分散部入力パケットに対応するセル
５２０：分散部出力セル
５３０：交換部出力セル（＝整列部入力セル）
５４０：整列済みセル
５５０：整列部出力パケット。
【技術分野】
【０００１】
本発明は、ルータ、サーバ、ストレージ装置などにおいて、装置内部に有する複数の機能ブロックを動的に相互に接続するスイッチ技術に関する。特に、独立動作する複数のスイッチを利用し、宛先でデータの到着順序が入れ替わる場合に、順番通りに並べ替えるための技術に関する。
【背景技術】
【０００２】
ルータなどのネットワーク転送装置やサーバ装置、複数のディスクアレイを接続するストレージ装置などでは、装置内部の機能ブロック間でデータ交換を行うためにスイッチファブリックが利用される。スイッチファブリックの交換容量は、ポート数とポート容量（回線速度）の積で表現され、大交換容量を実現するためには、ポート数とポート容量のいずれか片方、もしくは両方を増加させる必要がある。
【０００３】
ポート数を増加させるには、要素スイッチを多段結合し、オメガ網やクロス網、ファットツリー網等を形成することにより実現が可能である。また、スイッチＬＳＩ（Large Scale Integration）のポート容量を増加させることでポート容量を増加させることも可能であるが、ＬＳＩに実装可能なピン数は、その時代のＣＭＯＳ（Complementary MOS）の実装限界によって制限されるため、大容量ポートを実現すると、スイッチＬＳＩあたりのポート数は減少する。
【０００４】
ここで、大容量ポートを少数持つスイッチＬＳＩを多段結合することでスイッチファブリック全体の交換容量を向上することは可能であるが、総ポート数を大きくするに従って接続段数が大きくなり、結果としてスイッチファブリック通過のレイテンシが大きくなる問題、また、宛先が異なってもスイッチファブリック内で衝突が発生してスループットが低下する問題が発生する。これらの問題を回避して、目的の交換容量を実現する方法として、分散型スイッチ(パラレルパケットスイッチ)が知られている。
【０００５】
分散型スイッチでは、要求容量の1／Ｍの容量のポートを備える比較的低速なスイッチＬＳＩをＭ個用意し、スイッチファブリックの入力にあたる分散部において、入力データを分割して各スイッチへ分散して通過させることで所望の大交換容量を実現する。一般に、ネットワーク装置で利用されるスイッチの場合、入力データは可変長のパケットであり、パケットは固定長のセルと呼ばれる単位に分割される。
【０００６】
分散型スイッチを最も容易に構成する場合、交換部用に用いる複数のスイッチＬＳＩを完全に同期させ、更に完全に同一の宛先調停動作を実施する。よって、宛先には、完全に予測可能なタイミングで順番通りにセルが到着するため、容易にパケットを元通りに復元可能であり、更にフロー内のパケット順番も容易に復元可能である。
【０００７】
ところが、近年、スイッチに要求されるポート容量、交換容量は非常に大きくなっており、分散型スイッチを構成する各スイッチＬＳＩ自体も高速してきている。例えば、ＬＳＩ間の通信には、ＳｅｒＤｅｓ（SERialization/DE-Serialization）と呼ばれる高速シリアル伝送が利用されたり、セルの交換処理ピッチも短縮化されたりしているため、各スイッチＬＳＩを完全同期させることが事実上困難である。よって、各スイッチが非同期動作する、すなわち、各スイッチが独立して宛先調停を行なう分散型スイッチが必要である。
【０００８】
各交換部が非同期動作する分散型スイッチでは、スイッチファブリックの入力にあたる分散部でのセルの送信順番と、スイッチファブリックの出力にあたる整列部でのセルの到着順番が一致することが保証されない。よって、同一送信元から同一宛先を目指すパケット群（フロー）内のセルの順番を元通りに復元し（フロー復元）、更にパケットを元通りに復元（パケット復元）しなくてはならない。
【０００９】
ＵＳ２００４/０１４３５９３（Ａ１）では、パケットのシーケンス番号（整理番号）、送信元番号、ルーティングインデックス（単一の宛先、もしくは複数の宛先の組合せを参照するための値）、優先度を利用して、宛先において各フローのパケットを十分な量溜め込んだのち、パケット順番を元通りに復元する方法が開示されている。しかしながら、ＵＳ２００４/０１４３５９３（Ａ１）のパケット順番復元方法は、送信元番号、ルーティングインデックス、優先度の積で表現される数のフローについて、十分な量のパケット保持機構が必要と考えられ、ハードウェア量が多くなりうる課題を持つ。
【００１０】
ＷＯ０２/４３３２９（Ａ１）では、同一のパケットから生成したセルには、宛先番号、送信元番号、セル分割番号の他、同一のタイムスタンプを付加し、スイッチファブリックの各部で共通の時計を利用して、スイッチ内ではタイムスタンプの古いものを優先して選択し、スイッチの宛先では、同一のフローに属するセル、パケットをタイムスタンプの値が古いものから順に順序復元を行う方法が開示されている。しかしながら、ＷＯ０２/４３３２９（Ａ１）のセル、パケット順番復元方法は、送信元番号、ルーティングインデックスの積で表現される数のフローについて、十分な量のパケット保持機構が必要と考えられ、ハードウェア量が多くなりうる課題を持つ。また、スイッチファブリック各部で共通の時計を利用し、その時刻を元に並べ替えを行う点も、パケットやセルの転送速度が向上するにつれて困難になりうる課題を持つ。
【００１１】
ＵＳＰ６８３２２６１（Ｂ１）では、セル、パケット順序復元用のデバイスを複数個用いて、互いに交信しつつセル、パケットの順序復元を行う方法が開示されている。ＵＳＰ６８３２２６１（Ｂ１）の実施例から、送信元スロット（送信元番号）、シーケンス番号（整理番号）、宛先スロット（宛先番号）の積で表現される数のフローについて、十分な量のパケット保持機構が必要と考えられ、ハードウェア量が多くなりうる課題を持つ。
【００１２】
また、ＵＳＰ６８３２２６１（Ｂ１）は、スイッチファブリックの出力にあたる整列部を主眼にかかれているため、明記されていないが、ＵＳ２００４/０１４３５９３（Ａ１）とＷＯ０２/４３３２９（Ａ１）では、各スイッチの負荷に応じて、スイッチファブリックの入力にあたる分散部においてロードバランスを取りながら分散動作を行うことが開示されている。しかしながら、一般に、単純なロードバランス動作を行うと、輻輳状態にあるスイッチに溜まっているセルやパケットが目的の宛先、すなわち、スイッチファブリックの出力にあたる整列部に到着する前に、後続のセルやパケットが非輻輳状態のスイッチを経由して到着しうる。よって、整列部においてセルやパケットの順番を復元するために、整列部は大量のセルやパケットの保持が必要であり、ハードウェア量が多くなりうる課題を持つ。
【００１３】
以上のように、従来の、各交換部が非同期動作する分散型スイッチでは、整列部におけるフロー復元、パケット復元の手法に関して開示されているが、いずれの手法もハードウェア量が多くなりうる課題を持っている。分散型スイッチは、スイッチ全体の交換容量を向上させることが本来の目的であるため、分散動作、復元動作によって交換容量が低下しないように潤沢なハードウェアを搭載していると考えることもできるが、装置を低コスト化するためには、より小規模のハードウェアで実現可能な整列部を持つ分散型スイッチが望まれる。
【００１４】
【特許文献１】ＵＳ２００４/０１４３５９３（Ａ１）
【特許文献２】ＷＯ０２/４３３２９（Ａ１）
【特許文献３】ＵＳＰ６８３２２６１（Ｂ１）
【発明の開示】
【発明が解決しようとする課題】
【００１５】
各交換部が非同期動作する分散型スイッチにおいて、交換容量が低下しない分散動作、復元動作を実現することが課題である。また、複数のスイッチから順不同に到着するセルを、フロー内及びパケット内で元通りに復元する方法を小容量のハードウェアで実現することが課題である。
【課題を解決するための手段】
【００１６】
スイッチファブリックの入力部で、同じ宛先への1個以上の可変長データを固定長データに分割後、スイッチ数の整数倍個ずつ送信し、スイッチファブリックの各交換部で同一送信元の固定長データは順番を維持したまま、固定長データ単位で宛先毎出力調停を行う。スイッチファブリックの出力部では、受信バッファに固定長データを保持したまま、固定長データの送信元番号とフロー番号によってフローの区別を行い、現在の先頭番号を、当該固定長データの整理番号と比較し、一致すればフローの先頭とみなす。不一致であれば当該固定長データを一時保持し、後続の固定長データの整理番号の確認とともに、一時保持した固定長データの整理番号の再確認を繰り返し、最終的に一致したものをフローの先頭とみなす。フロー先頭となった固定長データは、更に送信元番号とフロー番号が同じものの中でパケット先頭及びパケット末尾を検出してパケットを復元する。
【発明の効果】
【００１７】
本発明を利用することにより、各スイッチが非同期動作する分散型スイッチにおいて、交換容量が低下しない分散動作、復元動作を実現可能となる。また、複数のスイッチから順不同に到着するセルを、フロー内及びパケット内で元通りに復元する方法を小容量のハードウェアで実現することが可能となる。よって、従来方法より少ないコストで、高い交換容量の分散型スイッチを構成可能となる。
【発明を実施するための最良の形態】
【００１８】
以下、より詳細な内容を添付図面に基づいて実施例で説明する。
【実施例１】
【００１９】
本発明における分散型スイッチ構成の一実施例を図１に示す。分散型スイッチは、スイッチファブリックの入力にあたるN個の分散部１００、データ交換を行うM個の交換部２００、スイッチファブリックの出力にあたるN個の整列部３００で構成する。尚、図１は、構成を明快にするために分散型スイッチの一部のみを図示しているが、入出力の数、交換部の数は様々な組合せが可能であり、例えば、入出力が４個、交換部が３個の分散型スイッチを構成する場合の全体像は、図２に示す通りである。すなわち、４個の分散部１００−｛１〜４｝、３個の交換部２００−｛１〜３｝、４個の整列部３００−｛１〜４｝で構成される。
【００２０】
まず、各部の役割を簡単に紹介する。分散部１００は、受信した可変長のパケットを固定長のセルに分割し、複数の交換部２００へ送信し、宛先の整列部３００では、受信したセルを元通りの順番に直してパケットとして出力する。図２で、交換部２００−｛１〜３｝は互いに独立に動作する、すなわち、入力セルに対して互いに独立に宛先調停を自立的に行うため、スイッチファブリック全体では非同期型の分散スイッチとして振る舞うことになる。
【００２１】
ここで、各スイッチが非同期動作する分散型スイッチにおいて、交換容量が低下しない分散動作、復元動作を実現しつつ、複数のスイッチから順不同に到着するセルを、フロー内及びパケット内で元通りに復元する方法を小容量のハードウェアとメモリで実現するためには、次の２点を満足する必要がある。
【００２２】
１点目は、スイッチファブリックの交換帯域を完全に活用すること、すなわち、各分散部が、各交換部に対して同量のセルを分散し、各整列部が、各交換部から同量のセルを受信できるようにすることである。２点目は、各整列部が受信するセルの順番乱れの量を極力少なくすることである。
【００２３】
各スイッチが非同期動作する一般的な分散型スイッチでは、各交換部２００に可変長パケットをそのまま分散してしまうと、長いパケットを送信した交換部２００は負荷が高く、短いパケットを送信した交換部２００は負荷が低くなる。そこで、可変長パケットを固定長のセルに分割し、１セルずつ順番に各交換部２００へ送信することで前記不均衡を緩和できる。
【００２４】
しかしながら、単純に１セルずつ順番に各交換部２００へ送信するだけでは、ある分散部１００から、ある整列部３００へ到着するセルは、特定の交換部２００だけを経由することがありうる。例えば、図２の分散型スイッチでも、パケット長が短く、１パケットから１セルだけが生成され、全分散部１００に入力される各パケットの宛先が、１、２、３、１、２、３、１、２、３と繰り返される場合、各分散部１００は、全ての交換部２００に順次セルを送り出すのだが、宛先１行きのセルは、交換部２００−１だけしか通過しない。同様に宛先２行きのセルは、交換部２００−２だけしか通過しないし、宛先３行きのセルは、交換部２００−３だけしか通過しない。整列部３００−１からみると、全ての分散部１００−１、１００−２、１００−３、１００−４からのセルが交換部２００−１からだけ到着するように見える。
【００２５】
前記状況は、分散部１００から観測すると、ある宛先に対しては、特定の交換部２００の負荷が高くなるように見えるため、後続のパケットから生成したセルを負荷が低い別の交換部２００を経由して整列部３００へ送信して、全ての交換部２００に対する不均衡をなくすような動作が必要になる。この不均衡をなくすため動作は、一般にロードバランスをとる動作として知られている。
【００２６】
一旦、ロードバランス動作が発生すると、ある宛先から早期に送信されたセルがある交換部２００に滞留している間に、後続のセルが別の交換部２００を経由して先に目的の整列部３００に届きうるため、整列部３００におけるセルの到着順番を大きく乱す原因にもなる。そして、背景技術でも述べたように、整列部３００でのセルの到着順番が大きく乱れる場合、整列部３００はセルやパケットの順番を復元するために、大量のセルやパケットの保持が必要であり、ハードウェア量が多くなりうる課題を持つ。
【００２７】
そこで、本発明では、分散部１００から、全ての交換部２００に、同一宛先のセルを可能な限り均等に送信することによって、全ての交換部２００の均等利用、及び、整列部３００の各送信元１００から全ての交換部２００を経由したセルの均等受信を実現する。
【００２８】
分散部１００における、より具体的なセル分散方法について図３を利用して説明する。可変長パケットはネットワーク１１１を経由して分散部１００に入力され、フロー番号割当器１１０に到着する。フロー番号割当器１１０では、整列部３００で受信セルの属する元のパケットの種類を区別するために、フロー番号を割当てる。宛先がひとつであるユニキャストを扱うだけであれば、前記区別のためにフロー番号は必要ないが、宛先が複数であるマルチキャストを扱う場合、整列部３００では、どのパケットに属するセルか区別するためのフロー番号が必要となる。フロー番号は、最大で２のポート数乗のオーダーの数が必要であるが、実際にはあらゆる宛先の組み合わせのマルチキャストパケットが連続して出現するわけではないので、２の８乗から１０乗程度のフロー番号があれば十分である。
【００２９】
パケットにフロー番号を付与したあと、スイッチファブリックの宛先、及び優先度毎に独立したＦＩＦＯ（FＦｉｒｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）キューであるＶｉｒｔｕａｌ Ｏｕｔｐｕｔ Ｑｕｅｕｅ（ＶＯＱ）１２０の対応するＶＯＱへパケットを保持する。マルチキャスト用のＶＯＱは、優先度毎に１本ずつであり、どのような宛先の組み合わせのマルチキャストも、対応する優先度の前記マルチキャスト用ＶＯＱに保持する。各ＶＯＱには、パケットのたまり具合を検出するために、パケット量カウンタを備える。また、パケットが入力されてから取り出しが行なわれるまでの時間を計測するタイマーを備える。
【００３０】
ＶＯＱ１２０では、各ＶＯＱのパケットの溜まり具合を監視し、可変長パケットを固定長セルに分割した際に、前記セルの数が交換部２００の数、例えば、図２の場合は、３を越えた場合に当該ＶＯＱを出力対象とする。複数のＶＯＱが出力対象となっている場合は、優先度の高いものの中からラウンドロビンなどのアルゴリズムを利用してひとつを選択する。そして、クレジットテーブル１６０を参照し、交換部２００群の当該宛先がセルを受信可能かどうか調査する。
【００３１】
クレジットテーブルとは、宛先の受信バッファの空き容量を前記受信バッファが受信可能なセルの数をクレジットと呼んで管理するための機構である。図２のスイッチファブリックの場合のクレジットテーブル１６０の例を図９に示す。クレジットテーブルのエントリは、宛先毎に独立しており、更に各交換部用に独立している。本例では、いずれも８ずつクレジットを持っていることを示しており、各宛先の各交換部は、８個までセルを受信可能であることを示す。また、ＶＯＱ１２０が参照するための宛先毎に全交換部のクレジットを合計したＶＯＱ参照用合計クレジット１６５を持つ。
【００３２】
図４に示すフローチャートを利用して、ＶＯＱからのパケット抜出し方法の一実施形態を説明する。まず、ステップＳ６００において、ＶＯＱ１２０の中にタイマーがあらかじめ設定した時間を経過した（タイムアウトした）ものがあれば、最優先で選択候補とする。そして、ステップＳ６０５において、何らかのアルゴリズムで選択したＶＯＱのＶＯＱ参照用合計クレジット１６５が正であれば、ステップＳ６０６において、選択したＶＯＱから溜まっているパケット群を取り出し、パケット分割器１３０の対応するＦＩＦＯキューに書き込み、書き込んだＦＩＦＯキューをタイムアウト扱いにする。また、取り出した分のパケットに相当するクレジットを対応するＶＯＱ参照用合計クレジット１６５から減算する。
【００３３】
ステップＳ６００において、タイムアウトしたＶＯＱが無ければ、ステップＳ６０１においてマルチキャスト用のＶＯＱ群にパケットがあれば選択候補とする。そして、ステップＳ６０３において、該当する宛先全てのＶＯＱ参照用合計クレジット１６５が正であれば、ステップＳ６０４において、選択したＶＯＱから溜まっているパケット群を取り出し、パケット分割器１３０の対応するＦＩＦＯキューに書き込む。また、取り出した分のパケットに相当するクレジットを対応するＶＯＱ参照用合計クレジット１６５から減算する。
【００３４】
ステップＳ６０１においてマルチキャスト用のＶＯＱ群にパケットがなく、ステップＳ６０２において、ユニキャストＶＯＱのいずれかのパケット群から生成されるセル量が交換部の数以上であれば選択候補とする。そして、ステップＳ６０３において、何らかのアルゴリズムで選択したユニキャストＶＯＱのＶＯＱ参照用合計クレジット１６５が正であれば、ステップＳ６０４において、選択したＶＯＱから溜まっているパケット群を取り出し、パケット分割器１３０の対応するＦＩＦＯキューに書き込む。また、取り出した分のパケットに相当するクレジットを対応するＶＯＱ参照用合計クレジット１６５から減算する。
【００３５】
尚、ＶＯＱ１２０で消費したＶＯＱ参照用合計クレジット１６５は、交換部から配線２７０経由で回復クレジットが到着した際に、回復クレジットに示されている量だけ回復させる。
【００３６】
パケット分割器１３０は、パケットをセルに分割するための機構である。各宛先へのユニキャスト用のＦＩＦＯキューを１本ずつ持ち、マルチキャスト用のＦＩＦＯキューを１本だけ持つ。各ＦＩＦＯキューの入力はパケット、出力はセルであり、セル化途中のパケットを保持する。また、各ＦＩＦＯキューは、パケットが入力されてから当該パケットが取り出されるまでの時間を計測するタイマーを備える。
【００３７】
図５に示すフローチャートを利用して、パケット分割器１３０の各ＦＩＦＯキューのセル出力方法の一実施形態を説明する。まず、ステップＳ６１０において、タイマーがタイムアウトしたＦＩＦＯキューがあれば、最優先で選択候補とする。タイムアウトしたものがなく、マルチキャストのＦＩＦＯキューにパケットが存在すれば、ステップＳ６１１においてマルチキャストのＦＩＦＯキューを選択する。マルチキャストのエントリも無く、ユニキャストのＦＩＦＯキューにエントリがあれば、ユニキャストＦＩＦＯキューのエントリがあるものの中から、ひとつを選択する（Ｓ６１３）。
【００３８】
ここで、セル割当器１４０について先に説明を加える。パケット分割器１３０のもつ各ＦＩＦＯキューに対応するＦＩＦＯキューがセル割当器１４０にもあり、こちらのＦＩＦＯキューはセルだけを保持する。セル割当器１４０のＦＩＦＯキューが一杯で受付不能の場合、同じ宛先のパケット分割器１３０のＦＩＦＯキューにバックプレッシャを与え、当該ＦＩＦＯキューからのセルをセル割当器１４０へ渡すことを禁止する。
【００３９】
再び、図５のフローチャートのステップＳ６１４の説明に戻る。先に説明したセル割当器１４０からステップＳ６１３で選択したＦＩＦＯキューがバックプレッシャを受けていれば、ステップＳ６１８へ進み、当該ＦＩＦＯキューのタイマーがスタートしていなければタイマーをスタートさせ、当該ＦＩＦＯキューからのセル抜出しを行なわず、ステップＳ６１０のチェックに戻る。
【００４０】
そうでなければ、ステップＳ６１５へ進み、選択したＦＩＦＯキューの先頭のパケットをあらかじめ定めた固定長に分割し、ヘッダ情報を追加してセル化し、まず１セル分だけセル割当器１４０へ送信する。ここで追加する前記ヘッダ情報は、当該パケットの属するフローのフロー番号と整理番号、パケットの先頭セルならＨｅａｄ情報、パケットの末尾セルならＴａｉｌ情報である。セル化が終了したパケットは消去する。尚、セル化を行っているＦＩＦＯキューがタイムアウトしているならば、セル割当器１４０の該当するＦＩＦＯキューもタイムアウト扱いにする。
【００４１】
ここで、前記のフロー番号は、フロー番号割当器１１０で得た値である。
【００４２】
また、前記の整理番号は、フロー番号毎にエントリを持つ整理番号管理メモリ１５０をフロー番号でアクセスすることによって獲得する値である。整理番号管理メモリ１５０の各エントリが管理する整理番号は、ゼロから始め、当該エントリにアクセスがあるたびに１ずつ増やしていき、最大値（セルがスイッチファブリックを通過する間に同じ番号が出現しない程度の値）に達したら再びゼロに戻す。
【００４３】
次にステップＳ６１６へ進み、選択していたＦＩＦＯキューのパケットのセル化が終了していなければ再度ステップＳ６１４へ戻る。ステップＳ６１６で、全パケットのセル化が完了すれば当該ＦＩＦＯキューのタイマーを（もしスタートしていれば）クリアし、ステップＳ６１０へ戻る。
【００４４】
次に、図６に示すフローチャートを利用して、セル割当器１４０の各ＦＩＦＯキューのセル受信方法の一実施形態を説明する。まず、ステップＳ６２０において、パケット分割器１３０からセル入力があるのを待つ。セル入力があれば、ステップＳ６２１において、当該ＦＩＦＯキューのタイマーが停止していればタイマーをスタートさせる。そしてステップＳ６２２において、当該ＦＩＦＯキューのエントリにセルを保持し、待機セル数を１増やす。また、ステップＳ６２３において、受信セルがタイムアウト情報を持っていれば、当該ＦＩＦＯキューをタイムアウト扱いにする。
【００４５】
次に、図７に示すフローチャートを利用して、セル割当器１４０の各ＦＩＦＯキューからのセル出力方法の一実施形態を説明する。セル割当器１４０は、セルを適切な交換部に割り当て、セル送信するための機構である。まず、ステップＳ６３０において、タイマーがタイムアウトしたＦＩＦＯキューがひとつ以上あれば、その中のひとつを選択する（Ｓ６４０）。タイムアウトしたものがなく、マルチキャストのＦＩＦＯキューにセルが存在すれば、ステップＳ６３１においてマルチキャストのＦＩＦＯキューを選択する（Ｓ６４０）。
【００４６】
セル割当器１４０は、セルを送信する交換部２００を指し示すためのスイッチポインタを備え、１セル送信する毎に次の交換部を指すようスイッチポインタを移動させる。例えば、図２に示すように交換部が三つある場合、スイッチポインタはセルを送信するたびに、交換部１→交換部２→交換部３→交換部１と順に移動させていく。ここで、ステップＳ６４１において、クレジットテーブル１６０を参照し、スイッチポインタの指す交換部の全ての対象となる宛先のクレジット１６１が正であるか確認する。
【００４７】
前記のクレジット１６１が負であれば、セルを送信することができないので当該ＦＩＦＯキューのセル送信は中断し、ステップＳ６３０へ戻る。
【００４８】
前記のクレジット１６１が正であれば、ステップＳ６４２において、選択したＦＩＦＯキューの先頭のセルに対し、追加のヘッダ情報として交換部番号（スイッチポインタの示す交換部番号）を付加し、対象となる交換部２００へ当該セルを送信する。そして、スイッチポインタを１ずらし、選択したＦＩＦＯキューの待機セル数を１減少させる。また、クレジットテーブル１６０の対象となる宛先の対象となる交換部のクレジット１６１を１減少させる。前記のセル送信により、選択したＦＩＦＯキューの待機セル数がゼロでなければ、ステップＳ６４３から、再度ステップＳ６４１に戻ってセル送信チェックを続ける。
【００４９】
ステップＳ６４３で、選択したＦＩＦＯキューの待機セル数がゼロになれば、全セルを送信したことになるので、ステップＳ６３７へ進み、当該ＦＩＦＯキューのタイマーをクリアし、ステップＳ６３０へ戻る。
【００５０】
ステップＳ６３１において、マルチキャストのＦＩＦＯにセルが存在しなければ、ステップＳ６３２に進み、待機セル数が交換部の数以上のユニキャストＦＩＦＯがあるか調べ、無ければステップＳ６３０へ戻る。あれば、ステップＳ６３３にて対象ＦＩＦＯのひとつを選択し、クレジットテーブル１６０の対象宛先の全ての交換部のクレジット１６１が正であるか確認する。全てが正でなければ、セル送信することはせず、ステップＳ６３０へ戻る。
【００５１】
対象宛先の全ての交換部のクレジット１６１が正であれば、ステップＳ６３５へ進み、選択したＦＩＦＯキューの先頭のセルに対し、追加のヘッダ情報として交換部番号（スイッチポインタの示す交換部番号）を付加し、対象となる交換部２００へ配線２４０経由で当該セルを送信する。そして、スイッチポインタを１ずらし、選択したＦＩＦＯキューの待機セル数を１減少させる。また、クレジットテーブル１６０の対象となる宛先の対象となる交換部のクレジット１６１を１減少させる。ここでは、セルを交換部と同じ数だけ送信するまでステップＳ６３５の操作を繰り返す。そして、ステップＳ６３７へ進み、当該ＦＩＦＯキューのタイマーをクリアし、ステップＳ６３０へ戻る。
【００５２】
尚、セル割当器１４０で消費した交換部毎のクレジット１６１は、交換部２００から配線２７０経由で回復クレジットが到着した際に、回復クレジットに示されている量だけ回復させる。
【００５３】
分散部１００と整列部３００を同一ＬＳＩ上に構成する場合、交換部２００から、整列部１００のクレジットテーブル１６０へ回復クレジットを送信する配線２７０は、交換部２００から整列部３００へセルを送信する配線２５０を共用することが可能である。具体的には、配線２５０経由で交換部２００から整列部３００へ送信するセルのヘッダ情報の一部に、交換部２００から分散部１００への回復クレジットを相乗りさせて送信することができる。
【００５４】
分散部１００と整列部３００を異なるＬＳＩ上に構成する場合、前記の回復クレジットを送信する配線２７０は、交換部２００から整列部３００へセルを送信する配線２５０とは別の専用の配線を利用する。
【００５５】
また、図８に、本発明におけるセル割当器１４０からパケット分割器１３０へのバックプレッシャ信号生成方法の一実施形態を示すフローチャートを示す。まず、ステップＳ６５０において、待機セル数が交換部の数より多いＦＩＦＯキューがあるか検査する。前記条件を満たせば、ステップＳ６５３においてパケット分割器１３０の対応するＦＩＦＯキューへバックプレッシャをかける。前記条件を満たさなければ、ステップＳ６５１において待機セル数と交換部数のＦＩＦＯキューがあるか調べ、該当するＦＩＦＯキューがあり、そのＦＩＦＯキューにセル出力が無く、セル入力があれば、ステップＳ６５３においてパケット分割器１３０の対応するＦＩＦＯキューへバックプレッシャをかける。ステップＳ６５１、ステップＳ６５２いずれの条件も満たさなければ、ステップＳ６５４において、パケット分割器１３０の対応するＦＩＦＯキューへのバックプレッシャを解除する。
【００５６】
以上、分散部１００において可変長パケットを固定長セルに分割し、全ての交換部２００に、同一宛先のセルを可能な限り均等に送信する具体的な実施例について説明した。本発明によれば、ユニキャストのパケットは、スイッチファブリックの備える交換部２００と同じ数ずつのセル単位で分散部１００から各交換部２００へ送信することができる。
【００５７】
あるパケットから交換部２００の数と異なる数のセルが生成される場合でも、ＶＯＱ１２０、パケット分割器１３０、セル分散器１４０の仕組みにより、余りとなるセルは次の同一宛先のユニキャストパケットから生成されるセルと一緒に、交換部２００の数と同じ数ずつだけ、各交換部２００へ送信することができる。また、前記の余りとなるセルが存在するときに、次の同一宛先のユニキャストパケットが到着しない場合は、タイムアウトの仕組みにより強制的に交換部２００へ送信することもできる。すなわち、交換部２００と同じ数のセル群の単位で送信した余りのセルが残った際にタイマを起動し、タイマの時間が所定の閾値に達したら、同一宛先の次のパケットの到着を待って待機しているこれら余りのセル群を、もはや待機させずに交換部２００に強制送信する強制送信機構を付け加える。
【００５８】
マルチキャストパケットの場合は、同じ複数の宛先の組合せのマルチキャストパケットが常に続くとは限らないため、ユニキャストパケットとは異なり、すぐに分散部１００から各交換部２００へ、送信するための仕組みを持たせている。
【００５９】
次に、図１０を用いて交換部２００の一実施例について説明する。交換部２００は、宛先毎のメモリ２１０で構成し、各入力からのセルは対応する宛先メモリ２１０に格納する。マルチキャストのセルの場合、対応するすべての宛先用メモリ２１０に格納する。各メモリ２１０の中は送信元毎に格納領域が決まっており、セルを受信後、各メモリでは、ラウンドロビンのような公平な選択アルゴリズムにより一つのセルを選び、当該宛先の整列部３００の受信バッファに空きがあれば、選択したセルを送信する。そして、前記の選択したセルの送信元である対応する分散部１００に対し、対応する配線２６０経由で回復クレジットを１セルにつき１ずつ返却する。
【００６０】
前記の宛先毎のメモリ２１０は、メモリ容量を削減するために、複数の宛先で共有し、時分割で利用してもよい。時分割でメモリ２１０を利用する場合、メモリ容量が削減される分、クレジットテーブル２２０が管理するクレジット量も減少する。
【００６１】
尚、前記の整列部３００の受信バッファに空きがあるか否かは、交換部２００が備えるクレジットテーブル２２０によって調べる。交換部２００の備えるクレジットテーブル２２０の構成例を図１１に示す。クレジットテーブル２２０は、各宛先毎に独立しており、それぞれの中で各送信元用のクレジット２２１を最低１ずつ、また、各送信元に共通のクレジット２２２を複数（図１１の例では８）備える。
【００６２】
交換部２００から整列部３００へセルを送信する際、送信するセルに対応する送信元用のクレジット２２１がゼロでなければ対応する送信元用のクレジット２２１を１減らし、ゼロであれば共通のクレジット２２２を１減らす。尚、クレジットは、整列部３００から回復クレジットが到着した際に、回復させる送信元の番号に対応する送信元用のクレジット２２１が最大値でなければ（図１１の例では１でなければ）、その対応する送信元用のクレジット２２１を１回復させる。そうでなければ、共通のクレジット２２２を１回復させる。
【００６３】
尚、分散部１００と整列部３００を同一ＬＳＩ上に構成する場合、整列部３００の回復クレジット生成器３７０から、交換部２００のクレジットテーブル２２０へ回復クレジットを送信する配線２６０は、分散部１００から交換部２００へセルを送信する配線２４０を共用することが可能である。具体的には、配線２４０経由で分散部１００から交換部２００へ送信するセルのヘッダ情報の一部に、整列部３００から交換部２００への回復クレジットを相乗りさせて送信することができる。
【００６４】
分散部１００と整列部３００を異なるＬＳＩ上に構成する場合、前記の回復クレジットを送信する配線２６０は、分散部１００から交換部２００へセルを送信する配線２４０とは別の専用の配線を利用する。
【００６５】
交換部２００の各宛先メモリ２１０は、セルを選択する際に、クレジットテーブル２２０の各送信元の共通クレジット２２２が正であれば、どのセルを選択してもよい。しかし、前記の共通クレジット２２２がゼロであれば、対応する送信元用のクレジット２２１が正であるセルの中からのみ選択する。このルールは、整列部３００でセルの順番復元を行なう際に、ある送信元からのセルが、他の送信元からのセルに邪魔されて交換部２００から永久に送信されずにデッドロックする状況を防ぐために用いる。
【００６６】
次に、図１２を用いて本発明の整列部３００の一実施形態を示す。整列部３００の概略動作についてまず説明する。整列部３００は、各交換部２００から配線２５０経由でセルを受信バッファ３１０へ受信する。そして、受信したセル本体は受信バッファ３１０に保持したまま、セルのヘッダ情報の一部と追加の情報をセレクタ３２０経由でフロー復元器３３０へ渡し、ひとつ以上のフロー復元器３３０にてフロー毎の先頭となるセルを検出する。
【００６７】
先頭セルを検出すると、そのうちひとつをセレクタ３４０で選び、受信バッファ３１０から該当するセルを抜出し、セレクタ３５０経由でパケット復元器３６０に前記のセルを渡す。同時に、対応する受信バッファ３１０に空き領域ができたことを回復クレジット生成器３７０に教える。回復クレジット生成器３７０は、セルを出力した受信バッファ３１０に対応する交換部２００に対し、前記のセルの持つ送信元番号を含めた回復クレジットを生成し、配線２６０経由で送信する。
【００６８】
パケット復元器３６０では、フロー毎にセルを一次保持する手段を持ち、分散部１００で付与したＨｅａｄ情報のセルを先頭に送信元番号とフロー番号の一致するセルを順番に保持し、同じく分散部１００で付与したＴａｉｌ情報のセルを受信したところでパケットとして復元を完了し出力する。
【００６９】
本発明の特長は、小規模の資源でフロー復元を可能にする点である。従来方法では、少なくとも、送信元番号、フロー番号の積で表現される数のフローにつき、順番乱れが発生した際に吸収可能な量のメモリ、例えば１００セル分格納できるメモリ、が必要である。よって、従来方法では、ハードウェア量、特に利用するメモリ量が非常に多くならざるを得ない。
【００７０】
本発明の整列部３００は、交換部２００と整列部３００の間でセルを送信し、回復クレジットを返信するまでの間に各交換部２００から送信される総セル量と同等程度の量の受信バッファ３１０のメモリだけで、セルの順番乱れを元通りに復元する仕組みを提供する。本発明の整列部３００が必要とする前記のメモリ量は、従来の整列部が持つメモリ量（少なくとも、送信元番号、フロー番号、順番乱れが発生した際に吸収可能なエントリ数の積で示されるメモリ量）より遥かに少なく、十分な低コスト化が望める。
【００７１】
尚、整列部３００に前記の非常に少ないメモリ量しか搭載しなくても、整列部３００において、セル順番復元が滞らないようにするためには、通常の状態において、非常に大きな順番乱れが発生しないようなセル分散が行われることが必須である。本発明では、分散部１００において、全ての宛先に対して、可能な限り全ての交換部２００を経由させるセル分散を行っているため、非常に大きな順番乱れは発生しにくいため、通常の状態では、問題を引き起こさない。
【００７２】
以下に、前記の非常に少ない受信バッファ３１０のメモリだけでセル順番を復元するフロー復元器３３０の詳細について説明する。
【００７３】
フロー復元器３３０は、送信元である分散部１００と同じ数だけ備えるのが望ましいが、複数の送信元で共有しても構わない。例えば、送信元が１６個ある場合、フロー復元器３３０を１６個備えるのが理想であるが、論理量の増加を抑えるために、フロー復元器３３０を８個だけ備え、特定の２個の送信元で特定の１個のフロー復元器３３０を共有させても構わない。同様に、フロー復元器３３０を４個だけ備え、特定の４個の送信元で特定の１個のフロー復元器３３０を共有させても構わない。
【００７４】
フロー復元器３３０の一実施例を図１３に示す。フロー復元器３３０は、整理番号管理メモリ３３２、整理番号比較器３３３、受信バッファ読み出しキュー３３５、再検査キュー３３６を備える。
【００７５】
交換部２００から受信したセルのヘッダ情報の一部と追加の情報を、入力４００経由で対応するフロー復元器３３０へ入力する。一般に、セル本体に比べセルのヘッダ情報はサイズが小さいため、数マシンサイクルに１回の割合で入力があることになる。ここで、前記のセルのヘッダ情報とは、送信元番号、フロー番号、整理番号である。また、前記の追加の情報とは、セル本体を記録した受信バッファ３１０内のアドレス、当該セルが通過した交換部２００の番号である。
【００７６】
フロー復元器３３０の内部では、前記の各種の情報を、キー情報、整理番号、データ情報の３種類の情報に分類する。
【００７７】
ここで、キー情報とは、整理番号管理メモリ３３２をアクセスするためのインデックスであり、本実施例では、送信元番号とフロー番号を結合したものである。
【００７８】
また、データ情報とは、受信バッファ３１０からセル本体を読み出すための情報であり、本実施例では、受信バッファ３１０内のアドレスと交換部２００の番号である。
【００７９】
ここで、図１４のフローチャートを利用して、図１３のフロー復元器３３０の動作に関して説明する。ステップＳ７００で、入力４００経由で交換部２００からのセル入力があれば、当該セルヘッダのキー情報で整理番号管理メモリ３３２を参照し、そのフローの現在の先頭にあたる整理番号を読み出す。
【００８０】
そして、ステップＳ７０３で、比較器３３３にて、入力したセルの整理番号と一致するか検査する。整理番号同士が一致すれば、ステップＳ７０４で、当該セルのデータ情報を受信バッファ読出しキュー３３５へ記録し、ステップＳ７０５で、加算器３３４を利用して、読み出していた整理番号に１を加え、整列番号管理メモリ３３２に書き戻す。
【００８１】
ステップＳ７０３で整理番号同士が一致しなければ、ステップＳ７０６で、当該セルのキー情報、整理番号、データ情報を再検査キュー３３６に積む。
【００８２】
また、ステップＳ７００で、入力４００経由で交換部２００からセル入力がなく、再検査キュー３３６にエントリがあれば、ステップＳ７０２で再検査キュー３３６の先頭のエントリを読出し、入力４２０経由で、前記の説明同様、整理番号管理メモリ３３２を参照し、ステップＳ７０３〜Ｓ７０５、またはＳ７０６の動作を繰り返す。
【００８３】
以上の動作を繰り返すことで、フロー復元器３３０に入力される、フロー順番の乱れたセル群は、各送信元の各種のフロー毎に送信された順番通りに受信バッファ読出しキュー３３５に積みなおされる。そして、受信バッファ読出しキュー３３５の先頭のエントリから順に出力４３０経由でデータ情報を読み出し、該当する受信バッファ３１０のセル本体を読み出せば、フロー内のセルの順番を完全に復元することができる。
【００８４】
図１７(a)、(b)に、本発明を利用した場合にパケットがどのように分散型スイッチファブリックを通過するかというイメージ図を、分散部１００−３、分散部１００−４から、整列部３００−１、整列部３００−２行きのパケットがあるという前提で示す。また、いずれのパケットもユニキャストパケットであるとしている。パケットを示す長方形や角丸長方形には、宛先が整列部３００−１であればＤ１、整列部３００−２であればＤ２とし、宛先毎のフロー内の番号をそのあとに記載している。可変長パケットから生成される固定長セル内に記載の番号も、同様であるが、セルに記載している「宛先毎のフロー内の番号」は、本実施例の文中に登場するフロー毎の「整理番号」である。尚、本例では、長方形は分散部１００−３入力、角丸長方形は分散部１００−４入力としている。
【００８５】
分散部１００−３入力の可変長パケット群５００−３、分散部１００−４入力の可変長パケット群５００−４は、各分散部１００において、それぞれ、対応する個数の固定長セル群５１０−３、５１０−４に分割される。
【００８６】
各分散部１００は、交換部２００が３個あるため、宛先毎に３の整数倍ずつセルを選んでセル群５２０−｛３、４｝｛Ａ、Ｂ、Ｃ｝として対応する交換部２００へ出力する。もともとのパケット長が３の倍数にならないような場合、一定時間が経過してタイムアウトが発生した際に出力する。例えば、分散部１００−３出力のＤ２−４のセルは、前記のタイムアウトが発生して出力されている様子を示している。前記のタイムアウトイベント発生後は、再び、宛先毎に３の整数倍ずつセルが選択できる状態であるので、Ｄ１−１０、Ｄ１−１１、Ｄ１−１２の３セルが連続して出力されている。
【００８７】
各交換部２００では、各分散部１００からの入力順番は維持したまま、宛先毎に出力調停を行い、セル群５３０｛Ａ、Ｂ、Ｃ｝−｛１、２｝として宛先である整列部３００へ送信する。
【００８８】
各整列部３００では、受信したセルを送信元毎、また、フロー毎（この場合は、ユニキャストが１フローずつあるのみ）に分類し、フロー内のセル順番を元通りのセル群５４０−｛１、２｝に復元し、更にそれぞれ元のパケット群５５０−｛１、２｝を復元する。
【００８９】
以上、本発明によるセル分散型スイッチについて詳細な説明を行った。本説明は、実施の一形態に過ぎず、本発明の技術的思想および技術的範囲から離れることなく、様々な変形が可能である。
【実施例２】
【００９０】
実施例１で説明した整列部３００よりも短時間でフロー復元可能な整列部を備える分散型スイッチファブリックを実施例２として説明する。ここで、実施例２の分散部１００、交換部２００の構成は図１等を用いて説明した実施例１のものと同一である。また、整列部３００の構成は、整列部３００内のフロー復元器を除いて同一である。よって、ここでは実施例２におけるフロー復元器３３０′の構成と動作を詳細に説明する。
【００９１】
実施例２のフロー復元器３３０′は、図１５に示すように、整理番号管理メモリ３３２、整理番号比較器３３３、受信バッファ読み出しキュー３３５、再検査キュー３３６に加え、連続整理番号生成器３３７、チェックエントリ３３８Ａ〜３３８Ｋ、連鎖選択器３４１を備える。ここで、チェックエントリとは、フローの先頭でなかったセルの、送信元番号、フロー番号、整理番号、セル本体を記録した受信バッファ３１０内のアドレス、当該セルが通過した交換部２００の番号を一時的に記録するための機構である。前記の各種情報は、交換部２００から受信して先頭検査を行なって先頭でなかった場合に記録する。以後、交換部２００からセルを受信するたびにチェックエントリ３３８Ａ〜３３８Ｋに一次記録してある情報も全て同時に検査を行う。
【００９２】
交換部２００からセルが当該フローの先頭であった場合、チェックエントリ３３８Ａ〜３３８Ｋのいずれかの内容がその次の先頭、更に別のチェックエントリの内容がその次の先頭、という具合に、次々と先頭が見つかる可能性がある。図１５のフロー復元器３３０では、交換部２００からセルが当該フローの先頭であった場合、更に、同時にチェックエントリ３３８Ａ〜３３８Ｋの中から最大で３個の連続する先頭セルを検出する。３個の連続する先頭セルの整理番号は、連続整理番号生成器３３７を利用して生成する。
【００９３】
尚、チェックエントリ３３８Ａ〜３３８Ｋで連鎖的に４個目以降の先頭セルが発見されうる。そこで、チェックエントリ３３８Ａ〜３３８Ｋの各々は、連鎖ビットと呼ぶ情報用のフィールドを備える。連鎖ビットは、前記の３個目の先頭であることを検出した時点で有効化する。そして、連鎖選択器３４１によって、連鎖ビットが有効になっているいずれかのチェックエントリの情報を選択し、入力４４０経由で、整理番号管理メモリ３３２で先頭検査を行なうことで、前記４個目以降の先頭セルの有無を調査する。
【００９４】
また、実施例２における受信バッファ読出しキュー３３５は、多入力１出力である。図１５に示す構成例では、３入力１出力である。３入力である理由は、チェックエントリ３３８の利用により、同時に、あるフローの先頭、その次、更にその次の３個の連続するセルが発見されうるためである。１出力である理由は、対応する受信バッファ３１０からセル本体を３個同時では無く、１個ずつ読み出すためである。尚、正確には、受信バッファ読出しキュー３３５からは同時に３情報を読み出し、整理番号＋０位置、整理番号＋１位置、整理番号＋２位置の順にひとつずつ出力４３０経由で出力し、対応する受信バッファ３１０のセル本体を読み出すことになる。
【００９５】
ここで、図１６のフローチャートを利用して、図１５のフロー復元器３３０′の動作に関して説明する。ステップＳ８００で、入力４００経由で交換部２００からセル入力があれば、当該セルヘッダのキー情報で整理番号管理メモリ３３２を参照し、そのフローの現在の先頭にあたる整理番号を読み出す。
【００９６】
そして、ステップＳ８０５で、比較器３３３にて、入力したセルの整理番号と一致するか検査する。整理番号同士が一致すれば、ステップＳ８１０で、当該セルのデータ情報を受信バッファ読出しキュー３３５の整理番号＋０位置へ記録する。また、当該セルとキー情報が同一であるチェックエントリ３３８の保持する整理番号が、連続整理番号生成器３３７で生成した「整理番号＋１」、「整理番号＋２」、「整理番号＋３」と一致するか検査する。
【００９７】
「整理番号＋１」、「整理番号＋２」、「整理番号＋３」全てがいずれかのチェックエントリで一致すれば、「整理番号＋１」のチェックエントリのデータ情報を受信バッファ読出しキュー３３５の整理番号＋１位置へ記録する。また、「整理番号＋２」のチェックエントリのデータ情報を受信バッファ読出しキュー３３５の整理番号＋２位置へ記録する。そして、「整理番号＋１」と「整理番号＋２」のチェックエントリの内容を消去し、「整理番号＋３」のチェックエントリの連鎖ビットを有効にする。整理番号管理メモリ３３２へは、当該フローのその後の先頭番号として「整理番号＋３」を書き戻す。（ステップＳ８１１→Ｓ８１２→Ｓ８１３→Ｓ８２２）
ステップＳ８１１の条件を満たさなければ、ステップＳ８２０で「整理番号＋１」、「整理番号＋２」両方がいずれかのチェックエントリで一致すれば、「整理番号＋１」のチェックエントリのデータ情報を受信バッファ読出しキュー３３５の整理番号＋１位置へ記録する。また、「整理番号＋２」のチェックエントリのデータ情報を受信バッファ読出しキュー３３５の整理番号＋２位置へ記録する。そして、「整理番号＋１」と「整理番号＋２」のチェックエントリの内容を消去する。整理番号管理メモリ３３２へは、当該フローのその後の先頭番号として「整理番号＋３」を書き戻す。（ステップＳ８１１→Ｓ８２０→Ｓ８２１→Ｓ８２２）
ステップＳ８２０の条件を満たさなければ、ステップＳ８３０で「整理番号＋１」がいずれかのチェックエントリで一致すれば、「整理番号＋１」のチェックエントリのデータ情報を受信バッファ読出しキュー３３５の整理番号＋１位置へ記録する。そして、「整理番号＋１」のチェックエントリの内容を消去する。整理番号管理メモリ３３２へは、当該フローのその後の先頭番号として「整理番号＋２」を書き戻す。（ステップＳ８１１→Ｓ８２０→Ｓ８３０→Ｓ８３１→Ｓ８３２）
ステップＳ８３０の条件を満たさなければ、ステップＳ８４０で整理番号管理メモリ３３２へは、当該フローのその後の先頭番号として「整理番号＋１」を書き戻す。（ステップＳ８１１→Ｓ８２０→Ｓ８３０→Ｓ８４０）
ステップＳ８０５で整理番号同士が一致しなければ、ステップＳ８０６で、チェックエントリ３３８のいずれかに空きエントリがあるか検査し、空きエントリがあれば、ステップＳ８０７にて、空きエントリのいずれかに、当該セルのキー情報、整理番号、データ情報を記録する。
【００９８】
また、ステップＳ８０６で、チェックエントリ３３８のいずれかに空きエントリがあるか検査し、空きエントリがなければ、ステップＳ８０８にて、再検査キュー３３６に、当該セルのキー情報、整理番号、データ情報を記録する。
【００９９】
また、ステップＳ８００で、入力４００経由で交換部２００からセル入力がなければ、ステップＳ８０１にて、チェックエントリ３３８Ａ〜３３８Ｋの連鎖ビットを検査する。そして、いずれかの連鎖ビットが有効であれば、ステップＳ８０４にて、それら有効な連鎖ビットをもつ、つまり連鎖ヒットしているチェックエントリの中からいずれかひとつを連鎖選択器３４１で選択し、選択したチェックエントリの保持する全情報を入力４４０経由でフロー復元器に再入力し、選択したチェックエントリの内容は消去する。
【０１００】
前記のチェックエントリ３３８Ａ〜３３８Ｋのいずれかから入力した整理番号は、連鎖ビットが有効であり、必ず整理番号管理メモリの対象となる整理番号と一致するので、ステップＳ８０５、ステップ８１０以下、先ほどの説明と同様の処理を行なう。
【０１０１】
また、ステップＳ８０１で、いずれのチェックエントリ３３８の連鎖ビットも有効になっていなければ、ステップＳ８０２において、再検査キュー３３６にエントリがあるかどうか検査する。
【０１０２】
再検査キュー３３６にエントリがあれば、ステップＳ８０３で再検査キュー３３６の先頭のエントリを読出し、ステップＳ８０５において、入力４２０経由で読み出した整理番号と、整理番号管理メモリ３３２の当該フローの整理番号が一致するかどうか検査し、以下、前記の説明同様、ステップＳ８０６以降、または、ステップＳ８１０以降の動作を繰り返す。
【０１０３】
以上、チェックエントリ３３８Ａ〜３３８Ｋを利用して、実施例１で説明した整列部３００より、短時間でフロー復元可能な整列部について詳細な説明を行なった。チェックエントリや、連続整理番号生成器３３７等はその搭載量に比例して論理資源が大規模化するため、十数個程度のチェックエントリ、＋３〜４程度の連続整理番号生成器３３７がリーズナブルと考えられる。チェックエントリ不足は、再検査キュー３３６の設置によって補うことができる。尚、論理資源の大規模化が共用範囲以内であると判断できれば、再検査キュー３３６は搭載せず、ある程度大量のチェックエントリ３３８を備える構成もとりうる。
以上、本発明によるセル分散型スイッチのフロー復元器について詳細な説明を行った。本説明は、実施の一形態に過ぎず、本発明の技術的思想および技術的範囲から離れることなく、様々な変形が可能である。
【産業上の利用可能性】
【０１０４】
本発明によるセル分散型スイッチにおける再整列方法は、大容量回線を利用したデータ交換が必要なシステムで利用することができる。例えば、ルータやスイッチに代表されるネットワーク装置内のスイッチファブリックや、サーバやストレージ機器の装置内のスイッチファブリック等での利用が考えられる。
【図面の簡単な説明】
【０１０５】
【図１】本発明の分散型スイッチの一実施形態の一部を示すブロック図である。
【図２】本発明の分散型スイッチの一実施形態を示すブロック図である。
【図３】本発明における整列部の一実施形態を示すブロック図である。
【図４】本発明におけるＶＯＱ抜出し方法の一実施形態を示すフローチャートである。
【図５】本発明におけるパケット分割器の出力方法の一実施形態を示すフローチャートである。
【図６】本発明におけるセル割当器の受信方法の一実施形態を示すフローチャートである。
【図７】本発明におけるセル割当器の出力方法の一実施形態を示すフローチャートである。
【図８】本発明におけるセル割当器からパケット分割器へのバックプレッシャ信号生成方法の一実施形態を示すフローチャートである。
【図９】本発明の分散部が管理する交換部のクレジットの説明図である。
【図１０】本発明の交換部の一実施形態を示すブロック図である。
【図１１】本発明の交換部が管理する整列部のクレジットの説明図である。
【図１２】本発明の整列部の一実施形態を示すブロック図である。
【図１３】本発明のフロー復元器の一実施形態を示すブロック図である。
【図１４】図１２のフロー復元の一実施形態を示すフローチャートである。
【図１５】本発明のチェックエントリを含むフロー復元器の一実施形態を示すブロック図である。
【図１６】図１４のフロー復元の一実施形態を示すフローチャートである。
【図１７ａ】本発明におけるパケット、セルの流れを示す説明図である。
【図１７ｂ】本発明におけるパケット、セルの流れ(続き)を示す説明図である。
【符号の説明】
【０１０６】
１００：分散部
１１０：フロー番号割当器
１２０：ＶＯＱ
１３０：パケット分割器
１４０：セル割当器
１５０：分散部の整理番号管理メモリ
１６０：分散部が管理する交換部のクレジットテーブル
２００：交換部
２１０：交換部が管理する整列部のクレジットテーブル
３００：整列部
３１０：受信バッファ
３３０：フロー復元器
３３２：整列部の整理番号管理メモリ
３３５：受信バッファ読出しキュー
３３６：再検査キュー
３３８：チェックエントリ
３６０：パケット復元器
３７０：回復クレジット生成器
５００：分散部入力パケット
５１０：分散部入力パケットに対応するセル
５２０：分散部出力セル
５３０：交換部出力セル（＝整列部入力セル）
５４０：整列済みセル
５５０：整列部出力パケット。
【特許請求の範囲】
【請求項１】
それぞれが非同期に宛先調停を行う複数の交換部を有する分散型スイッチファブリックシステムにおいて、
スイッチファブリックの入力にあたる分散部に、同じ宛先への可変長のパケットを1個以上の固定長のセルに分割し、交換部の数の整数倍個以上となるまで前記同じ宛先へのセル群を一時保持したあと、交換部数の整数倍個ずつ前記セル群を前記複数の交換部へ送信する機構を備え、
スイッチファブリックの各交換部に、同一送信元のセル群の間の送信順番を維持したまま、セル単位で宛先毎出力調停する機構を備え、
スイッチファブリックの出力にあたる整列部に、
受信セルの順番検査用の情報を利用して先頭であるか否かの順番検査を行なう機構と、
非先頭であれば検査に利用した情報を一時記録する先入れ先出しキュー機構と、
先頭であれば当該セルを抽出し、更に前記の一時記録した先入れ先出しキューの先頭の情報から順に検査し、更なる続きの先頭となるセルを抽出するする機構と、
前記の先頭として抽出されたセルに対し、パケットの区切り情報を利用して元のパケットを復元する機構とを備えたことを特徴とする分散型スイッチファブリックシステム。
【請求項２】
それぞれが非同期に宛先調停を行う複数の交換部を有する分散型スイッチファブリックシステムにおいて、
スイッチファブリックの入力にあたる分散部に、同じ宛先への可変長のパケットを1個以上の固定長のセルに分割し、スイッチ数の整数倍個以上となるまで前記同じ宛先へのセル群を一時保持したあと、スイッチ数の整数倍個ずつ前記セル群を送信する機構を備え、
スイッチファブリックの各交換部に、同一送信元のセル群の間の送信順番を維持したまま、セル単位で宛先毎出力調停する機構を備え、
スイッチファブリックの出力にあたる整列部に、
受信セルの順番検査用の情報を利用して先頭であるか否かの順番検査を行なう機構と、
前記受信セルが非先頭であれば検査に利用した情報を一時記録する一時記録機構と、
前記受信セルが先頭であれば当該セルを抽出し、更に前記一時記録機構に記録した非先頭セルの情報を全検査し、更なる続きの先頭となるセルを抽出する機構と、
前記の先頭として抽出されたセルに対し、パケットの区切り情報を利用して元のパケットを復元する機構とを備えたことを特徴とする分散型スイッチファブリックシステム。
【請求項３】
前記分散部は、 宛先が複数であるマルチキャストパケットの場合は、前記パケットを固定長セルに分割後、スイッチ数の整数倍個以上のセルに達しなくても複数の交換部へ送信する機構を更に備えたことを特徴とする請求項１もしくは第２項のいずれかに記載の分散型スイッチファブリックシステム。
【請求項４】
前記分散部は、 固定長セルに分割して待機中のセル群が、設定した閾値時間を経過しても出力されない場合に、前記待機中のセル群を強制的に複数の交換部へ送信する機構を更に備えたことを特徴とする請求項１もしくは第２項のいずれかに記載の分散型スイッチファブリックシステム。
【請求項５】
前記整列部で利用する受信セルの順番検査用の情報として、送信元番号と、各分散部で単一の宛先、もしくは複数の宛先の組合せ毎に一意に決定するフロー番号と、前記フロー内の整理番号とを利用することを特徴とする請求項１もしくは第２項のいずれかに記載の分散型スイッチファブリックシステム。
【請求項６】
前記整列部に、受信セルが先頭であるか否かの順番検査を行う機構と、非先頭であった前記セルを一時記録する先入れ先出しキュー機構と、更なる続きの先頭となるセルを検査する機構とをそれぞれ複数備え、
前記先入れ先出しキューにエントリがある場合、受信セルの入力がないタイミングで前記先入れ先出しキューの先頭の情報から順に先頭検査を行う機構を備えた請求項１記載の分散型スイッチファブリックシステム。
【請求項７】
前記整列部に、受信セルが先頭であるか否かの順番検査を行う機構と、前記一時記録機構と、更なる続きの先頭となるセルを抽出する機構とをそれぞれ複数備え、
前記一時記録機構にセルがある場合、受信セルが先頭であったら、前記一時記録機構の全セルの整理番号と現在の先頭の整理番号に１から特定の整数までの各整数値を加えた値とをそれぞれ比較検査し、１を加えた整理番号のセルから順に、一致した整理番号のセルまでを、先頭から連続する整理番号のセルとして選択し、前記の一時記録機構から削除する機構を備えた分散型スイッチファブリックシステム。
【請求項８】
前記整列部に、前記一時記録機構のエントリが非先頭であったセルの情報で満杯の時に、非先頭であった前記セルの情報を一時記録する先入れ先出しキュー機構を更に備え、受信セル及び前記一時記録機構に記録された情報の検査の合間に前記先入れ先出しキュー機構のセル情報の検査により更なる続きの先頭セルの抽出を行うことを特徴とする請求項２記載の分散型スイッチファブリックシステム。
【請求項９】
前記交換部で受信可能なセルの数、及び前記整列部で受信可能なセルの数を、それぞれ前記分散部と前記交換部がクレジットとして管理し、セル送信のたびにクレジットを削減し、交換部と整列部のセル受信バッファからセルが送信された時に、それぞれ整列部と交換部に空き領域が出来たことを通知し、整列部と交換部でクレジットを回復する機構を備えた請求項１もしくは請求項２にいずれかに記載の分散型スイッチファブリックシステム。
【請求項１０】
前記交換部が管理する整列部用クレジットは送信元毎に最低1個、また、各送信元共通で複数個管理する請求項９の分散型スイッチファブリックシステム。
【請求項１１】
それぞれが非同期に宛先調停を行う複数の交換部を有する分散型スイッチにおいて、
スイッチファブリックの入力にあたる分散部には、同じ宛先への可変長のパケットを1個以上の固定長のセルに分割し、スイッチ数の整数倍個ずつ前記セル群を複数の交換部へ送信する機構を備え、
スイッチファブリックの出力にあたる整列部には、受信したセルを、フローの先頭となるまで保持、先頭の再確認を繰り返し、正しい順番に並べ替える機能を備えた分散型スイッチファブリックシステム。
【請求項１】
それぞれが非同期に宛先調停を行う複数の交換部を有する分散型スイッチファブリックシステムにおいて、
スイッチファブリックの入力にあたる分散部に、同じ宛先への可変長のパケットを1個以上の固定長のセルに分割し、交換部の数の整数倍個以上となるまで前記同じ宛先へのセル群を一時保持したあと、交換部数の整数倍個ずつ前記セル群を前記複数の交換部へ送信する機構を備え、
スイッチファブリックの各交換部に、同一送信元のセル群の間の送信順番を維持したまま、セル単位で宛先毎出力調停する機構を備え、
スイッチファブリックの出力にあたる整列部に、
受信セルの順番検査用の情報を利用して先頭であるか否かの順番検査を行なう機構と、
非先頭であれば検査に利用した情報を一時記録する先入れ先出しキュー機構と、
先頭であれば当該セルを抽出し、更に前記の一時記録した先入れ先出しキューの先頭の情報から順に検査し、更なる続きの先頭となるセルを抽出するする機構と、
前記の先頭として抽出されたセルに対し、パケットの区切り情報を利用して元のパケットを復元する機構とを備えたことを特徴とする分散型スイッチファブリックシステム。
【請求項２】
それぞれが非同期に宛先調停を行う複数の交換部を有する分散型スイッチファブリックシステムにおいて、
スイッチファブリックの入力にあたる分散部に、同じ宛先への可変長のパケットを1個以上の固定長のセルに分割し、スイッチ数の整数倍個以上となるまで前記同じ宛先へのセル群を一時保持したあと、スイッチ数の整数倍個ずつ前記セル群を送信する機構を備え、
スイッチファブリックの各交換部に、同一送信元のセル群の間の送信順番を維持したまま、セル単位で宛先毎出力調停する機構を備え、
スイッチファブリックの出力にあたる整列部に、
受信セルの順番検査用の情報を利用して先頭であるか否かの順番検査を行なう機構と、
前記受信セルが非先頭であれば検査に利用した情報を一時記録する一時記録機構と、
前記受信セルが先頭であれば当該セルを抽出し、更に前記一時記録機構に記録した非先頭セルの情報を全検査し、更なる続きの先頭となるセルを抽出する機構と、
前記の先頭として抽出されたセルに対し、パケットの区切り情報を利用して元のパケットを復元する機構とを備えたことを特徴とする分散型スイッチファブリックシステム。
【請求項３】
前記分散部は、 宛先が複数であるマルチキャストパケットの場合は、前記パケットを固定長セルに分割後、スイッチ数の整数倍個以上のセルに達しなくても複数の交換部へ送信する機構を更に備えたことを特徴とする請求項１もしくは第２項のいずれかに記載の分散型スイッチファブリックシステム。
【請求項４】
前記分散部は、 固定長セルに分割して待機中のセル群が、設定した閾値時間を経過しても出力されない場合に、前記待機中のセル群を強制的に複数の交換部へ送信する機構を更に備えたことを特徴とする請求項１もしくは第２項のいずれかに記載の分散型スイッチファブリックシステム。
【請求項５】
前記整列部で利用する受信セルの順番検査用の情報として、送信元番号と、各分散部で単一の宛先、もしくは複数の宛先の組合せ毎に一意に決定するフロー番号と、前記フロー内の整理番号とを利用することを特徴とする請求項１もしくは第２項のいずれかに記載の分散型スイッチファブリックシステム。
【請求項６】
前記整列部に、受信セルが先頭であるか否かの順番検査を行う機構と、非先頭であった前記セルを一時記録する先入れ先出しキュー機構と、更なる続きの先頭となるセルを検査する機構とをそれぞれ複数備え、
前記先入れ先出しキューにエントリがある場合、受信セルの入力がないタイミングで前記先入れ先出しキューの先頭の情報から順に先頭検査を行う機構を備えた請求項１記載の分散型スイッチファブリックシステム。
【請求項７】
前記整列部に、受信セルが先頭であるか否かの順番検査を行う機構と、前記一時記録機構と、更なる続きの先頭となるセルを抽出する機構とをそれぞれ複数備え、
前記一時記録機構にセルがある場合、受信セルが先頭であったら、前記一時記録機構の全セルの整理番号と現在の先頭の整理番号に１から特定の整数までの各整数値を加えた値とをそれぞれ比較検査し、１を加えた整理番号のセルから順に、一致した整理番号のセルまでを、先頭から連続する整理番号のセルとして選択し、前記の一時記録機構から削除する機構を備えた分散型スイッチファブリックシステム。
【請求項８】
前記整列部に、前記一時記録機構のエントリが非先頭であったセルの情報で満杯の時に、非先頭であった前記セルの情報を一時記録する先入れ先出しキュー機構を更に備え、受信セル及び前記一時記録機構に記録された情報の検査の合間に前記先入れ先出しキュー機構のセル情報の検査により更なる続きの先頭セルの抽出を行うことを特徴とする請求項２記載の分散型スイッチファブリックシステム。
【請求項９】
前記交換部で受信可能なセルの数、及び前記整列部で受信可能なセルの数を、それぞれ前記分散部と前記交換部がクレジットとして管理し、セル送信のたびにクレジットを削減し、交換部と整列部のセル受信バッファからセルが送信された時に、それぞれ整列部と交換部に空き領域が出来たことを通知し、整列部と交換部でクレジットを回復する機構を備えた請求項１もしくは請求項２にいずれかに記載の分散型スイッチファブリックシステム。
【請求項１０】
前記交換部が管理する整列部用クレジットは送信元毎に最低1個、また、各送信元共通で複数個管理する請求項９の分散型スイッチファブリックシステム。
【請求項１１】
それぞれが非同期に宛先調停を行う複数の交換部を有する分散型スイッチにおいて、
スイッチファブリックの入力にあたる分散部には、同じ宛先への可変長のパケットを1個以上の固定長のセルに分割し、スイッチ数の整数倍個ずつ前記セル群を複数の交換部へ送信する機構を備え、
スイッチファブリックの出力にあたる整列部には、受信したセルを、フローの先頭となるまで保持、先頭の再確認を繰り返し、正しい順番に並べ替える機能を備えた分散型スイッチファブリックシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７ａ】
【図１７ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７ａ】
【図１７ｂ】
【公開番号】特開２００８−２７８３８７（Ｐ２００８−２７８３８７Ａ）
【公開日】平成２０年１１月１３日（２００８．１１．１３）
【国際特許分類】
【出願番号】特願２００７−１２２０１４（Ｐ２００７−１２２０１４）
【出願日】平成１９年５月７日（２００７．５．７）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２０年１１月１３日（２００８．１１．１３）
【国際特許分類】
【出願日】平成１９年５月７日（２００７．５．７）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]