(57)【特許請求の範囲】
【請求項１】
複数の入力と複数の出力との間でパケットを交換する単位スイッチを多段接続して構成されたスイッチネットワークと、複数組の入力ポート及び出力ポート毎に対応して設けられ、対応する入力ポートから入力されたパケットを該スイッチネットワークへ転送し、該スイッチネットワークから出力されたパケットを対応する出力ポートへ転送する、複数のインターフェース装置とを備えたパケット交換装置であって、
各々の前記インターフェース装置は、自装置が扱ったパケットに関する所定の内容の統計情報を前記スイッチネットワークに送出する手段を含み、
前記スイッチネットワークは、前記インターフェース装置の各々から送出された前記統計情報を加味した統計情報を求めてこれを前記インターフェース装置の各々に転送するために、各単位スイッチにおいて、初段の場合には前記インターフェース装置から、初段でない場合には前段の単位スイッチから入力された複数の統計情報を、分散協調的に演算処理して、最終段でない場合には後段の単位スイッチへ、最終段の場合には前記インターフェース装置へ出力する手段を含むことを特徴とするパケット交換装置。
【請求項２】
各々の前記インターフェース装置が前記スイッチネットワークへ送出する前記統計情報は、当該インターフェース装置が、一定時間内に前記スイッチネットワークへ送出した、各出力ポート毎のまたは全出力ポートについての、パケット数またはパケット長であり、
前記スイッチネットワーク内で求める前記インターフェース装置の各々から送出された前記統計情報を加味した統計情報は、各々の前記インターフェース装置が、一定時間内に前記スイッチネットワークへ送出した、各出力ポート毎のまたは全出力ポートについての、パケット数またはパケット長の合計数であり、
前記スイッチネットワーク内の単位スイッチのうち、前記パケット数またはパケット長の合計数が求まるまでの段に該当するものは、入力された複数の統計情報を加算して出力し、前記スイッチネットワーク内の単位スイッチのうち、前記パケット数またはパケット長の合計数が求まった以降のものは、入力された複数の統計情報を加算せずに出力することを特徴とする請求項１に記載のパケット交換装置。
【請求項３】
各々の前記インターフェース装置は、前記スイッチネットワークから転送された前記統計情報に基づいて前記スイッチネットワークへのパケット送出を制御する手段を更に含むことを特徴とする請求項１に記載のパケット交換装置。
【請求項４】
各々の前記インターフェース装置は、
前記スイッチネットワークから転送された前記統計情報に基づいて前記スイッチネットワークへの送出を制限すべきパケットの宛先となる出力ポートの有無を調べる手段と、
自装置が前記スイッチネットワークへ送出すべき各パケットの１つまたは複数の宛先となる前記出力ポートをビットマップで保持する手段と、
送出を制限すべきとされた出力ポートがある場合、前記ビットマップを参照して、送出を制限すべきとされた出力ポートを宛先として持たないパケットを検索する手段と更に含むことを特徴とする請求項１に記載のパケット交換装置。
【請求項５】
複数の入力と複数の出力との間でパケットを交換する単位スイッチを多段接続して構成されたスイッチネットワークと、複数組の入力ポート及び出力ポート毎に対応して設けられ、対応する入力ポートから入力されたパケットを該スイッチネットワークへ転送し、該スイッチネットワークから出力されたパケットを対応する出力ポートへ転送する、複数のインターフェース装置とを備えたパケット交換装置における統計情報処理方法であって、
各々の前記インターフェース装置は、自装置が扱ったパケットに関する所定の内容の統計情報を前記スイッチネットワークに送出し、
前記スイッチネットワーク内の初段の単位スイッチの各々は、前記インターフェース装置のうちの該当する一部のものから入力された複数の統計情報をもとにして、該スイッチネットワーク内の各段の単位スイッチが協調して前記インターフェース装置の各々から送出された前記統計情報を加味した統計情報を求めるために当該段で行うべきものと定められた演算処理を行い、この演算処理の結果を統計情報として後段へ出力し、
前記スイッチネットワーク内の初段より後で最終段より前の各々の段の単位スイッチの各々は、自スイッチに接続されている前段の複数の単位スイッチから入力された複数の前記統計情報をもとにして、当該段で行うべきものと定められた演算処理を行い、この演算処理の結果を統計情報として後段へ出力し、
前記スイッチネットワーク内の最終段の単位スイッチの各々は、自スイッチに接続されている前段の複数の単位スイッチから入力された複数の統計情報をもとにして、当該段で行うべきものと定められた演算処理を行い、この演算処理の結果を統計情報として前記インターフェース装置うちの一部の該当するものへ出力することを特徴とする統計情報処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケットを交換するパケット交換装置及びそのトラヒック制御に用いる統計情報を処理する統計情報処理方法に関する。
【０００２】
【従来の技術】
パケット交換装置では、複数の入力からランダムにパケットが入力されるので、特定の出力にパケットが集中して輻輳状態になってしまうことがある。このような輻輳を回避するため、トラヒック制御装置が用いられる。
【０００３】
従来のパケット交換装置に用いるスイッチネットワークに小規模な単位スイッチを多段接続する構成のものがある。
【０００４】
図２７は、入力ポート毎に入力バッファ２１２０と出力ポート毎に出力バッファ２１３０を持ち、４入力４出力の単位スイッチ２１１０−１−１〜２１１０−１−４，２１１０−２−１〜２１１０−２−４，２１１０−３−１〜２１１０−３−４を接続して構成される多段スイッチを示している。
【０００５】
なお、以下では、単位スイッチ２１１０−１−１〜２１１０−１−４，２１１０−２−１〜２１１０−２−４，２１１０−３−１〜２１１０−３−４の各々を区別せずに言う場合には単位スイッチの参照符号に共通の２１１０の部分のみを用いて単位スイッチ２１１０と呼ぶものとする。また、この参照符号に共通の部分のみを用いる呼び方は本明細書において他の装置や構成部分にも使用するものとする。
【０００６】
各単位スイッチ２１１０は、入力側からパケットデータを受信し、パケットに付けられた宛先に応じて出力側からパケットを送信する。
【０００７】
このようなスイッチネットワークにおいて、パケットは、最初に入力バッファ２１２０に保持され、スイッチネットワークを経由して出力バッファ２１３０に転送される。出力バッファ２１３０から単位スイッチ２１１０の間、単位スイッチ２１１０から単位スイッチ２１１０の間、および単位スイッチ２１１０から入力バッファ２１２０の間では、バックプレッシャー信号が転送され、パケットを受信できないときは、パケットの送出が抑止される。
【０００８】
このようなスイッチネットワークにおいて、ある出力ポートにトラヒックが集中したとき、最初に、（その出力ポートの）出力バッファ２１３０が一杯になる。すると、この出力バッファ２１３０に接続された単位スイッチ２１１０に対してバックプレッシャー信号が転送され、その単位スイッチ２１１０は、その出力ポート２１３０へのパケットの送出を停止する。さらに、この状態が継続すると、この単位スイッチ２１１０も前段の単位スイッチ２１１０に対してバックプレッシャー信号を送出し、パケットの送出を停止させる。さらに、この状態が継続すると、それら前段の単位スイッチ２１１０も更にその前段の単位スイッチ２１１０にバックプレッシャー信号を送出し、パケットの送出を停止させる。すなわち、最初の段のすべての単位スイッチ２１１０−１−１〜２１１０−１−４に対してパケットの送出が停止されるので、スイッチネットワークは、パケットの転送ができなくなってしまう。このように、１つの出力ポートにトラヒックが集中したことによって、その出力ポートと無関係の出力に向かうパケットまで影響を受けてしまうという、好ましくない状態が起こってしまう。
【０００９】
次に、単位スイッチとして共通バッファ型スイッチを用いた場合の例について説明する。共通バッファ型スイッチは、そのパケットバッファを出力で共有するので、特定の出力にパケットが集中した場合に、他の出力が影響を受けるという特徴を持つ。
【００１０】
図２８に示した、単位スイッチとして４入力４出力の共通バッファ型単位スイッチを用いて構成される多段スイッチネットワークを例として説明する。
【００１１】
各単位スイッチ２１１０は、パケットデータを受信してパケットに付けられた宛先に応じて出力からパケットを送信する。
【００１２】
また、図２８の各単位スイッチ２１１０は、パケットを蓄積するバッファを持ち、出力の競合が起きた場合に送信できなかったパケットを保持する。各単位スイッチ２１１０のバッファが一杯になって、パケットを受信できない場合は、送信元の単位スイッチ２１１０に対してバックプレッシャー信号が送信され、パケットの送出が抑制される。
【００１３】
このようなスイッチネットワークにおいて、ある出力ポートにパケットが集中したとき、スイッチネットワーク内の単位スイッチ２１１０のバッファがこの出力ポート行きのパケットで満たされてしまい、他の出力ポート行きのパケットがスイッチネットワークを通過するのを困難にする。例えば、図２８において、出力ポート５行きのパケットが大量に入力された場合について説明する。このような場合、出力ポート５に接続された単位スイッチ２１１０−３−２に出力ポート５行きのパケットが集中し、単位スイッチ２１１０−３−２のバッファは、出力ポート５行きのパケットによって一杯になってしまう。そして、単位スイッチ２１１０−３−２へ接続されている単位スイッチ２１１０−２−１〜２１１０−２−４は、単位スイッチ２１１０−３−２へパケットを送出することができなくなり、これらの単位スイッチも単位スイッチ２１１０−３−２行きのパケット（出力ポート４〜７行きのパケット）で一杯になり、同様に単位スイッチ２１１０−１−１〜２１１０−１−４もバッファが一杯になってしまう。このような状態になると、出力ポート５以外の出力ポート行きのパケットもスイッチネットワークから出力されないようになってしまい、スループットが低下するという問題が生じる。
【００１４】
【発明が解決しようとする課題】
単位スイッチを多段接続して大規模化したスイッチでは、特定の出力ポートにトラヒックが集中するなどしてトラヒックの偏りが発生したときに、スイッチネットワーク内で輻輳が発生し、その特定の出力ポートと関係のない出力ポートに向かうパケットも影響を受け、スループットが低下してしまうという問題がある。
【００１５】
本発明は、上記事情を考慮してなされたもので、トラヒック制御を可能とした単位スイッチを多段接続したスイッチネットワークを持つパケット交換装置及びそのトラヒック制御に用いる統計情報を処理する統計情報処理方法を提供することを目的とする。
【００１６】
【課題を解決するための手段】
本発明は、複数の入力と複数の出力との間でパケットを交換する単位スイッチを多段接続して構成されたスイッチネットワークと、複数組の入力ポート及び出力ポート毎に対応して設けられ、対応する入力ポートから入力されたパケットを該スイッチネットワークへ転送し、該スイッチネットワークから出力されたパケットを対応する出力ポートへ転送する、複数のインターフェース装置とを備えたパケット交換装置であって、各々の前記インターフェース装置は、自装置が扱ったパケットに関する所定の内容の統計情報を前記スイッチネットワークに送出する手段を含み、前記スイッチネットワークは、前記インターフェース装置の各々から送出された前記統計情報を加味した統計情報を求めてこれを前記インターフェース装置の各々に転送するために、各単位スイッチにおいて、初段の場合には前記インターフェース装置から、初段でない場合には前段の単位スイッチから入力された複数の統計情報を、分散協調的に演算処理して、最終段でない場合には後段の単位スイッチへ、最終段の場合には前記インターフェース装置へ出力する手段を含むことを特徴とする。
【００１７】
また、本発明は、複数の入力と複数の出力との間でパケットを交換する単位スイッチを多段接続して構成されたスイッチネットワークと、複数組の入力ポート及び出力ポート毎に対応して設けられ、対応する入力ポートから入力されたパケットを該スイッチネットワークへ転送し、該スイッチネットワークから出力されたパケットを対応する出力ポートへ転送する、複数のインターフェース装置とを備えたパケット交換装置における統計情報処理方法であって、各々の前記インターフェース装置は、自装置が扱ったパケットに関する所定の内容の統計情報を前記スイッチネットワークに送出し、前記スイッチネットワーク内の初段の単位スイッチの各々は、前記インターフェース装置のうちの該当する一部のものから入力された複数の統計情報をもとにして、該スイッチネットワーク内の各段の単位スイッチが協調して前記インターフェース装置の各々から送出された前記統計情報を加味した統計情報を求めるために当該段で行うべきものと定められた演算処理を行い、この演算処理の結果を統計情報として後段へ出力し、前記スイッチネットワーク内の初段より後で最終段より前の各々の段の単位スイッチの各々は、自スイッチに接続されている前段の複数の単位スイッチから入力された複数の前記統計情報をもとにして、当該段で行うべきものと定められた演算処理を行い、この演算処理の結果を統計情報として後段へ出力し、前記スイッチネットワーク内の最終段の単位スイッチの各々は、自スイッチに接続されている前段の複数の単位スイッチから入力された複数の統計情報をもとにして、当該段で行うべきものと定められた演算処理を行い、この演算処理の結果を統計情報として前記インターフェース装置うちの一部の該当するものへ出力することを特徴とする。
【００１８】
なお、各々の単位スイッチにおける演算処理は、その単位スイッチに関する統計情報をも用いて行うようにしてもよい。
【００１９】
また、統計情報としてパケット数を用いるようにしてもよい。また、統計情報としてパケット長を用いるようにしてもよい。統計情報を下位ビットから送出するようにしてもよい。また、統計情報をパケットの一部に含めて転送するようにしてもよい。また、統計情報をバックプレッシャー信号の一部に含めて転送するようにしてもよい。また、インターフェース装置で、出力可能パケット数を計算し、出力可能パケット数までパケットを出力したら、次に計算されるまでパケットを出力しないようにしてもよい。また、可変長のパケットを固定長のパケットに分割してスイッチネットワークへ転送するようにしてもよい。
【００２０】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る本発明は装置に係る発明としても成立する。
【００２１】
本発明では、複数の入力と複数の出力との間でパケットを交換する単位スイッチを多段接続して構成されたスイッチネットワークと、複数組の入力ポート及び出力ポート毎に対応して設けられ、対応する入力ポートから入力されたパケットを該スイッチネットワークへ転送し、該スイッチネットワークから出力されたパケットを対応する出力ポートへ転送する、複数のインターフェース装置とを備えたパケット交換装置において、各々の前記インターフェース装置は、自装置が扱ったパケットに関する所定の内容の統計情報を前記スイッチネットワークに送出し、前記スイッチネットワークにおいて、前記インターフェース装置の各々から送出された前記統計情報を加味した統計情報を求めてこれを前記インターフェース装置の各々に転送するために、各単位スイッチにおいて、初段の場合には前記インターフェース装置から、初段でない場合には前段の単位スイッチから入力された複数の統計情報を、分散協調的に演算処理して、最終段でない場合には後段の単位スイッチへ、最終段の場合には前記インターフェース装置へ出力する。
【００２２】
各々のインターフェース装置は、スイッチネットワークから転送された統計情報を用いて、例えば、出力ポート毎のパケットに関する特性を把握し、必要に応じて出力ポート毎にスイッチネットワークへのパケット送出を制限するなどの制御をすることによって、トラヒックの集中を回避もしくは解消し、輻輳を制御するなどのトラヒック制御ができる。
【００２３】
【発明の実施の形態】
以下、図面を参照しながら発明の実施の形態を説明する。
【００２４】
図１に、本発明の一実施形態に係るパケット交換装置の構成例を示す。
【００２５】
図１に示したパケット交換装置は、スイッチネットワーク１０と、Ｎ個（Ｎは複数）のインターフェース装置２０−１〜２０−Ｎと、Ｎ個の入力ポート３０−１〜３０−Ｎと、Ｎ個の出力ポート４０−１〜４０−Ｎとで構成される。
【００２６】
スイッチネットワーク１０は、例えば図２８に示されたクロスネットワークのように、単位スイッチ１１０が多段接続されて構成される。
【００２７】
図２に、一例として、３入力３出力の単位スイッチ１１０を、各段３個にして３段接続して構成したスイッチネットワーク１０の構成例を示す。なお、図２において、信号線で接続した各装置間ではパケットや統計情報が転送される。
なお、パケット転送用の信号線と統計情報転送用の信号線を別に設ける構成と、例えばパケットと統計情報とを時分割的に転送する、あるいは統計情報をパケットの一部として転送するなどしてパケットと統計情報とで信号線を共用する構成とが可能である。
また、統計情報を、パケットと反対方向に転送する構成も可能である。この場合、例えば、統計情報をバックプレッシャー信号の一部として転送することで、統計情報専用の信号線を不要とすることも可能である。
【００２８】
図３に、各インターフェース装置２０の構成例を示す。図３に示したインターフェース装置２０は、パケット送出装置２１０と、統計情報送出装置２２０と、パケット受信装置２３０と、統計情報受信装置２４０とで構成される。
【００２９】
パケット送出装置２１０は、当該パケット交換装置の対応する入力ポート３０に入力されたパケットを受信し、スイッチネットワーク１０へパケットを送出するためにパケット出力３１０からパケットを送出する。
【００３０】
スイッチネットワーク１０内では、各単位スイッチ１１０が、パケットをその宛先に応じてスイッチングする。
【００３１】
パケット受信装置２３０は、スイッチネットワーク１０から対応するパケット入力３３０に送出されたパケットを受信し、当該パケット交換装置の対応する出力ポート４０からパケットを送出する。
【００３２】
統計情報送出装置２２０は、パケット送出装置２２０から出力されたパケットを観測し、スイッチネットワーク１０へ送出されたパケットの統計情報を収集し、それを処理して、統計情報出力３２０からスイッチネットワーク１０へ送出する。
【００３３】
スイッチネットワーク１０内では、後述するように、単位スイッチ１１０が連携して、統計情報の演算処理を行う。
【００３４】
統計情報受信装置２４０は、スイッチネットワーク１０から送出された統計情報を統計情報入力３４０から受信し、該統計情報をそのまま（あるいはパケットの出力を制御するための制御情報に変換して）パケット送出装置２１０へ転送する。パケット送出装置２１０は、統計情報受信装置２４０から転送された統計情報に基づいて、パケットの出力の制御（例えば、トラフィック制御）を行う。
あるいは、統計情報受信装置２４０は、スイッチネットワーク１０から送出された統計情報を統計情報入力３４０から受信し、該統計情報をそのまま（あるいは適宜変換して）図示しないトラフィック制御装置へ転送する。トラフィック制御装置は、統計情報受信装置２４０から転送された統計情報に基づいて、パケット送出装置２１０におけるパケットの出力を制御する。
【００３５】
図４に、各単位スイッチ１１０の構成例を示す。図４に示した単位スイッチ１１０は、パケットの交換処理を行うパケット処理装置５１０と統計情報の演算処理を行う統計情報処理装置５２０とで構成される。
【００３６】
パケット処理装置５１０は、各パケット入力４１０から入力されたパケットを、それに付けられた宛先情報にしたがって、該当するパケット出力４３０に出力する交換動作を行う。
【００３７】
図５に、単位スイッチ１１０の統計情報処理装置５２０の動作の流れの一例を示す。
【００３８】
ある単位スイッチ１１０において、各統計情報入力４２０から、前段に接続されている単位スイッチ（当該単位スイッチがスイッチネットワークにおける２段目以降の場合）または前段に接続されているインタフェース装置（当該単位スイッチがスイッチネットワークにおける初段の場合）からの統計情報が受信されると（ステップＳ１）、この単位スイッチ１１０の統計情報処理装置５２０は、入力された統計情報に対して所定の演算処理を行い（ステップＳ２）、この演算処理によって得られた結果を統計情報として各統計情報出力４４０に出力する（ステップＳ３）。
【００３９】
なお、統計情報処理装置５２０が、その単位スイッチ１１０についての統計情報を収集する構成もある。例えば、単位スイッチ１１０内にパケットバッファがあり、そのパケットバッファ内に蓄積されているパケット数を統計情報とする場合などである。このような構成の場合には、統計情報処理装置５２０は、ステップＳ２において、必要に応じて自装置にて収集された統計情報をも用いて統計情報の演算処理を行う。
【００４０】
統計情報処理装置５２０の演算処理機能は、組み合わせ回路等でハードウェアにより実現することも可能であり、また、統計情報処理装置５２０にＣＰＵを用意して演算処理プログラムを実行させることによって実現することもできる。
【００４１】
次に、本実施形態のパケット交換装置の動作について説明する。
【００４２】
まず、パケット転送および統計情報の収集に関する動作について説明する。
【００４３】
パケット交換装置の入力ポート３０−ｉ（ｉは１〜Ｎのいずれか）に入力されたパケットは、対応するインターフェース装置２０−ｉに転送される。インターフェース装置２０−ｉは、パケット送出装置２１０に入力されたパケットを、統計情報受信装置２４０からの情報（あるいは図示しないトラヒック制御装置からの制御情報）にしたがって送出する。入力されたパケットが、統計情報受信装置２４０からの情報にしたがって送出が許可となった場合（あるいは図示しないトラヒック制御装置によって送出を許可された場合）は、パケット送出装置２１０は、パケットをパケット出力３１０からスイッチネットワーク１０へ送出する。同時にパケットは統計情報送出装置２２０にも転送され、統計情報送出装置２２０はスイッチネットワーク１０へ送出されたパケットに関する統計情報を収集する。
【００４４】
統計情報には、例えば、パケット出力から出力された全パケット数、パケット出力から出力されたパケットの全パケット長、パケット出力から出力された宛先毎のパケット長、パケット出力から出力された宛先毎のパケット数などが集計される。もちろん、その他にも、統計情報として種々のものが使用可能である。
【００４５】
インターフェース装置２０−ｉからスイッチネットワーク１０に入力されたパケットは、対応する単位スイッチ１１０の対応するパケット入力４１０に入力され、そのパケット処理装置５１０に転送される。パケット処理装置５１０には、複数のパケット入力４１０からのパケットが入力され、パケットに付けられた宛先に応じてパケットを交換する。交換されたパケットは、宛先に応じてパケット出力４３０から出力される。
【００４６】
このような単位スイッチ１１０を所定段数だけ通過した後、パケットは、スイッチネットワーク１０から出力され、対応するインターフェース装置２０のパケット入力３３０に入力され、そのパケット受信装置２３０へ転送される。同時にパケットは統計情報送出装置２２０にも転送され、統計情報送出装置２２０はスイッチネットワーク１０からインターフェース装置２０へ転送されたパケットに関する統計情報を収集する。
【００４７】
なお、前述したように、スイッチネットワーク１０内の各単位スイッチ１１０内で統計情報が収集される場合もある。
【００４８】
次に、各装置が収集した統計情報を扱う動作について説明する。
【００４９】
図６に、インターフェース装置２０の統計情報に関する動作の流れの一例を示す。単位スイッチ１１０の（統計情報処理装置５２０の）統計情報に関する動作の流れの一例は図５に示した通りである。
【００５０】
それぞれのインターフェース装置２０では、集計された統計情報を、図示しない制御装置からの制御信号によって、スイッチネットワーク１０へ送出する（ステップＳ２１）。
【００５１】
それぞれのインターフェース装置２０から送出された統計情報は、スイッチネットワーク１０の初段の対応する単位スイッチ１１０へ対応する統計情報入力４２０から入力され、その統計情報処理装置５２０へ転送される。また、場合によっては、各単位スイッチ１１０において、パケット処理装置５１０から収集された統計情報も統計情報処理装置５２０に入力される。各単位スイッチ１１０の統計情報処理装置５２０では、統計情報の演算処理を行い、演算処理された統計情報を各統計情報出力４４０から出力する（図５のステップＳ１〜Ｓ３）。
【００５２】
スイッチネットワーク全体でみたときの統計情報の演算処理としては、例えば、各インターフェース装置２０で計数されたパケット長やパケット数の加算などを行う。この場合、全体としての演算処理の結果として、各インターフェース装置２０で計数されたパケット長やパケット数の合計値が出力される。スイッチネットワーク内の各単位スイッチ１１０の統計情報処理装置５２０は、全体としての演算処理を実現するために各単位スイッチ１１０に割り当てられた演算処理を行う（すなわち、演算処理の内容は、例えば、単位スイッチごとに、あるいは単位スイッチの段数に応じて、異なる）。
【００５３】
スイッチネットワーク１０内において、それぞれの単位スイッチ１１０のそれぞれの統計情報出力４４０から送出された統計情報は、次段の対応する単位スイッチ１１０の対応する統計情報入力４２０から入力され、上記した初段の単位スイッチ１１０と同様、その段に応じた統計情報の演算処理や、演算処理の結果の転送等が行われる。
【００５４】
上記処理が繰り返され、スイッチネットワーク１０の最終段の各単位スイッチ１１０での演算処理の結果はスイッチネットワーク１０から送出される。
【００５５】
そして、スイッチネットワーク１０から送出された上記処理結果すなわち最終的な統計情報は、各インターフェース装置２０の統計情報入力３４０から入力され、それぞれの統計情報受信装置２４０に転送される（ステップＳ２２）。
【００５６】
それぞれのインターフェース装置２０の統計情報受信装置２４０では、受信した統計情報をそのまま（あるいは適宜変換して）、パケット送出装置２１０（または図示しないトラフィック制御装置）へ転送し、パケット送出装置２１０は、統計情報受信装置２４０からの情報（または図示しないトラフィック制御装置からの制御情報）に基づいて、パケットの出力を制御する（ステップＳ２３）。
【００５７】
ここで、統計情報として各インターフェース装置２０が一定の期間にスイッチネットワーク１０に送出した出力ポート毎のパケット数を用い、スイッチネットワーク１０内の単位スイッチ１１０の統計情報処理装置５２０が協調して、すべてのインターフェース装置２０の統計情報（すなわち上記のパケット数）の合計を求め、その結果を各々のインターフェース装置２０へ転送し、各インターフェース装置２０ではそのパケット数の合計を用いてトラヒック制御を行う場合を例にとって説明する。
【００５８】
それぞれのインターフェース装置２０では、スイッチネットワーク１０へ送出したパケット数を出力ポート毎に計数する。インターフェース装置２０は、図示しない制御装置からの制御信号にしたがって、収集した結果をスイッチネットワーク１０へ送出する。
スイッチネットワーク１０の各単位スイッチ１１０は、スイッチネットワーク１０全体でパケット数の合計値を求めるような演算を行うように動作し（その具体例は後述する）、最終的にそれぞれのインターフェース装置２０から送出された出力ポート毎の送出パケット数を合計をインターフェース装置２０へ転送する。
それぞれのインターフェース装置２０には、スイッチネットワーク１０へ送出された出力ポート毎のパケット数の合計が転送されるので、この値を用いてその出力ポートにトラヒックが集中しているかどうかを判断することができる。例えば、ある出力ポートにトラヒックが集中して輻輳を起こすと判断した場合には、その出力ポートへ向かうパケットの送出を抑制することによって、特定の出力ポートにトラヒックが集中すること制限することが可能となる。
【００５９】
このようにインターフェース装置毎に統計情報を収集し、それをスイッチネットワーク内に分散して配置された統計情報処理装置を用いて処理してインターフェース装置に転送することにより、各々のインターフェース装置がスイッチネットワーク全体のトラヒックの状態を観測でき、その結果に基づいて、スイッチネットワークへ出力されるトラヒックを制御し、スイッチネットワークのスループットを向上させることが可能となる。
【００６０】
次に、本実施形態のインターフェース装置２０の他の構成例について説明する。
【００６１】
ここで説明するインターフェース装置２０は、制限された出力に向かうパケット以外のパケットを選択的に出力することができる機能を有する。
【００６２】
このインターフェース装置２０は、出力毎のビットマップと、パケットまたはパケットへのポインタを関連付けて保持し、制限された出力に対するビットマップを持たないパケットを古い順に検索し、最初に検索されたパケットを出力する機能を実現している。
【００６３】
最初に図７および図８を参照しながら動作について説明する。
【００６４】
図７および図８は、パケットバッファを摸式的に表した図である（図７は入力動作を説明するためのもので、図８は出力動作を説明するためのものである）。左側の部分は、出力を表すビットマップを示し、右側の部分は、パケットを表す。また、これらの情報は、下から上に向かって古い順番で保持されている。図７および図８の例では、６個のパケットを保持できるパケットバッファを表しており、また、４つの出力に対応した出力ビットマップを保持する。
【００６５】
まず、図７を参照しながら、パケットが入力されたときの動作について説明する。
【００６６】
図７（ａ）に示す入力前の状態では、ユニット３に出力ポート３行きのパケット１が、ユニット５に出力ポート１行きと２行きのパケット２（マルチキャスト）が、ユニット６に出力ポート１行きと３行きのパケット３（マルチキャスト）が保持され、ユニット１，２，４は、空きである。
【００６７】
パケットバッファには、古いものが下の方に保持されるように制御されるので、パケット１が１番古く、次にパケット２、そしてパケット３が最も新しいパケットである。
【００６８】
パケット入力時には、下から空きであるユニットの検索を行う。これによってユニット１が空きであることが検索される。それぞれのユニットには、検索結果が転送され、下のユニットで空きが検索されたときは、そのユニットの内容を下のユニットに転送することによって、検索されたユニットより上にあるユニットの内容が１つ下のユニットに転送される。これによって一番上のユニットに空きができ、そこに入力されたパケットが宛先を示すビットマップとともに保持される。図７（ａ）の例では、ユニット１が空きとして検索されたので、図７（ｂ）に示されるように、ユニット２〜６の内容がそれぞれユニット１〜５に転送され（すなわち、それぞれ１ユニットだけシフトされ）、ユニット６には、新たに入力されたパケット４が保持されている。
【００６９】
例えば、４のユニットで空きが最初に検索された場合は、ユニット５，６の内容がそれぞれユニット４，５に転送され、ユニット６に新たに入力されたパケットが入力され、ユニット１〜３の内容は変化しない。
【００７０】
次に、パケットを出力するときの動作について図８を用いて説明する。
【００７１】
パケットを出力するときは、図示しない外部の制御装置から出力が制限された出力ポートを示す信号が入力される。図８（ａ）は、出力ポート３行きのパケットの出力が制限されている場合を示している。この場合、出力が制限されているポートに出力されるパケット以外のパケットが下から検索される。図８（ａ）の例ではユニット２，５に保持されているパケットがいずれも出力ポート３に向かうので、出力ポート３に出力されるパケット以外のパケットには、パケット２とパケット４が該当し、これらの中で最も古いパケットすなわち下の方にあるパケットであるパケット２が検索される。検索されたパケットは、パケット出力バスから出力され、また、検索されたユニットより上にあるユニットの内容が１つ下のユニットに転送される。図８（ａ）の例では、ユニット４が検索されたユニットに該当するので、図８（ｂ）に示されるように、ユニット４より上にあるユニット５，６の内容がそれぞれユニット４，５に転送される。ユニット６は、空きとなる。このような動作によって、制限されるべき出力に向かわないパケットを選択して出力することが可能となる。
【００７２】
図９に、このような動作を実現するインターフェース装置２０の構成例を示す。
【００７３】
図９に示したインターフェース装置２０は、検索機能付パケットバッファ２１２と、パケットバッファ制御装置２１４と、統計情報送出装置２２０と、パケット受信装置２３０と、統計情報受信装置２４０とで構成される。
【００７４】
検索機能付パケットバッファ２１２は、パケットバッファ制御装置２１４から転送される制御信号にしたがってパケットを蓄積し、出力する。出力時には、パケットバッファ制御装置２１４からは、輻輳のため転送できない出力ポートが指示され、検索機能付パケットバッファ２１２は、転送できない出力ポートを宛先とするパケットは出力せずに、それ以外のパケットを古い順に出力する。
【００７５】
図１０に、このような検索機能付パケットバッファ２１２の構成例を示す。図１０に示した検索機能付パケットバッファ２１２は、複数のパケットバッファユニット６１０（６１０−１〜６１０−８）と、検索回路６２０と、制御信号６３０と、パケット出力バス６４０とで構成される。
【００７６】
なお、検索機能付きパケットバッファとして、特開平３−１５９４３７、特開平７−１４１１４５、特開平７−２３５９３２、特開平１１−１５０５４１などがあるが、これらのパケットバッファは、宛先情報に一致するものを検索して出力しているが、本実施形態で用いられるパケットバッファは、制限された出力に該当しないものを選択して出力するものである。
【００７７】
図１１に、パケットバッファユニット６１０の構成例を示す。この例では、出力Ｍ個、パケット長Ｎビットと仮定している（ただし、図１１では、出力の３番目〜Ｍ−１番目についての繰り返しとなる部分およびパケット長４ビット目〜Ｎ−１ビット目までについての繰り返しとなる部分の記述を省略している）。
【００７８】
パケットバッファユニット６１０は、パケットが出力される出力ポートをビットマップとして保持するフリップフロップ７１１−１〜７１１−Ｍと、パケットを保持するフリップフロップ７２１−１〜７２１−Ｎと、それらを制御する論理ゲート７１３−１〜７１３−Ｍ，７２３−１〜７２３−Ｎ，７３１，７３３，７３５，７３７，７３９，７４１，７４３，７４５とで構成される。
【００７９】
ＩｎｐｕｔＭｏｄｅは、パケットを入力するモードであることを示す信号、ＯｕｔｐｕｔＭｏｄｅは、パケットを出力するモードであることを示す信号、ＯｕｔＰｏｒｔ−１〜ＯｕｔＰｏｒｔ−Ｍは、出力が制限された出力ポートを示す信号、Ｐｏｕｔ−１〜Ｐｏｕｔ−Ｎは、パケット出力、ＳｈｉｆｔＩｎＲ−１〜ＳｈｉｆｔＩｎＲ−Ｍは、出力ビットマップのシフト入力、ＳｈｉｆｔＯｕｔＲ−１〜ＳｈｉｆｔＯｕｔＲ−Ｍは、出力ビットマップのシフト出力、ＳｈｉｆｔＩｎＰ−１〜ＳｈｉｆｔＩｎＰ−Ｎは、パケットのシフト入力、ＳｈｉｆｔＯｕｔＰ−１〜ＳｈｉｆｔＯｕｔＰ−Ｎは、パケットのシフト出力である。なお、上側のユニットのＳｈｉｆｔＯｕｔＲ−１〜ＳｈｉｆｔＯｕｔＲ−Ｍがそれぞれ下側のユニットのＳｈｉｆｔＩｎＲ−１〜ＳｈｉｆｔＩｎＲ−Ｍに接続され、同様に、上側のユニットのＳｈｉｆｔＯｕｔＰ−１〜ＳｈｉｆｔＯｕｔＰ−Ｎがそれぞれ下側のユニットのＳｈｉｆｔＩｎＰ−１〜ＳｈｉｆｔＩｎＰ−Ｎに接続される。
【００８０】
フリップフロップ７１１−１〜７１１−Ｍの出力は、ＮＯＲゲート７３１に転送される。ＮＯＲゲート７３１の出力は、空きであることを示す。
【００８１】
また、フリップフロップ７１１−１〜７１１−Ｍの出力は、フリップフロップ７１１−１〜７１１−Ｍのそれぞれに対応したＡＮＤゲート７１３−１〜７１３−Ｍにも転送される。ＡＮＤゲート７１３−１〜７１３−Ｍのもう一方の入力には、制御信号ＯｕｔＰｏｒｔが入力され、それぞれ、ＡＮＤゲート７１３の出力は、制限された出力に向かうパケットであることを示す。これらのＡＮＤゲート７１３−１〜７１３−Ｍの出力は、ＮＯＲゲート７３３に転送される。ＮＯＲゲート７３３の出力は、出力制限された出力に向かわないことを示す。すなわち、ＡＮＤゲート７１３の出力の１つでも‘Ｈ’であれば、出力が制限されるので、ＮＯＲゲート７３３の出力は、‘Ｌ’になる。
【００８２】
ＮＯＲゲート７３１の出力は、ＡＮＤゲート７３７に転送される。ＡＮＤゲート７３７のもう一方の入力には、制御信号ＩｎｐｕｔＭｏｄｅが入力され、ＡＮＤゲート７３７の出力は、入力動作時に空きであることを示す。
【００８３】
また、ＮＯＲゲート７３１の出力は、ＮＯＴゲート７３５にも転送され、その出力は、ＡＮＤゲート７３９に入力される。
【００８４】
ＡＮＤゲート７３９には、ＮＯＲゲート７３３の出力と制御信号ＯｕｔｐｕｔＭｏｄｅも入力され、ＡＮＤゲート７３９の出力は、出力動作時に空きではなく、制限された出力にも向かわないことを示す。
【００８５】
ＡＮＤゲート７３７とＡＮＤゲート７３９の出力は、ＯＲゲート７４３に入力され、ＯＲゲート７４３の出力は、検索条件（すなわち、入力時には空きであり、出力時には制限された出力ポートに向かわないパケットである）に一致したことを示す。
【００８６】
ＯＲゲート７４３の出力は、検索回路６２０に入力される。検索回路６２０は、そのユニットより下に検索条件に一致するユニットがあるかどうかを出力する。すなわち、ＳＯｕｔが‘Ｈ’ならば、このユニットより下のユニットですでに検索条件に一致したユニットが存在することを示し、ＳＯｕｔが‘Ｌ’ならば、このユニットより下のユニットで検索条件に一致するものがなかったことを示す。
【００８７】
したがって、検索条件に一致し、かつ、そのユニットより下に検索条件に一致するものがなかった場合に、そのユニットが検索条件に一致する最も下のユニットである。これは、ＡＮＤゲート７４５によって示され、その結果は、ＯＲゲート７４１と３状態バッファ７２３−１〜７２３−Ｎに転送される。
【００８８】
３状態バッファ７２３−１〜７２３−Ｎでは、検索条件に一致するものの中で最も下にあるユニットのパケットをパケット出力バスＰｏｕｔから出力する。
【００８９】
ＯＲゲート７４１のもう一方の入力には、検索回路６２０からの出力が入力され、その結果は、検索条件に一致する最も下のユニットか、あるいは、下のユニットで検索条件に一致したことを示す。すなわち、ＯＲゲート７４１の出力は、１つ上のユニットから転送された宛先情報およびパケットをフリップフロップ７１１−１〜７１１−Ｍおよびフリップフロップ７２１−１〜７２１−Ｎに保持するための書き込み許可信号として、フリップフロップ７１１−１〜７１１−Ｍおよびフリップフロップ７２１−１〜７２１−Ｎに入力される。
【００９０】
このような構成によって制限された出力に向かわないパケットを選択することが可能となる。また、マルチキャストパケットもユニキャストパケットも区別することなく公平に扱うことが可能となる。
【００９１】
この例では、パケット本体をフリップフロップに保持していたが、パケット本体を別のバッファメモリに保持し、この部分をそのバッファメモリへのポインタにすることも可能である。
【００９２】
また、ポインタの値を図１２に示すように循環させることによって空きポインタを保持するためのメモリを省略することが可能となる。
【００９３】
さらに、図１３に示すように検索機能付パケットバッファ２１２の前に検索機能を持たないＦＩＦＯ方式のパケットバッファ２１３を設けることも可能である。検索機能付パケットバッファ２１２は、ハードウェア規模が大きくなるので、単純なＦＩＦＯ機能だけのバッファを設けることによって大規模なパケットバッファを実現することが可能となる。
【００９４】
本実施形態のパケット交換装置のスイッチネットワーク１０を構成する各単位スイッチ１１０に用いられる統計情報処理装置５２０（図４参照）について説明する。
【００９５】
図１４は、スイッチネットワーク１０を構成する各単位スイッチ１１０内の統計情報処理装置５２０の動作例（処理方法の例）を示した図である。図１４では、３入力３出力の単位スイッチ１１０を用いて９入力９出力のスイッチネットワーク１０を構成した場合の例を示している。なお、図１４の統計情報処理装置５２０−１−１は図２の単位スイッチ１１０−１−１に対応し、他も同様である。
【００９６】
図１４において、統計情報入力と統計情報出力の組４２０−１／４４０−１〜４２０−９／４４０−９にそれぞれ対応するインターフェース装置を２０−１〜２０−９で表すものとする。
【００９７】
統計情報入力４２０−１〜４２０−９からは、それぞれインターフェース装置２０−１〜２０−９（の統計情報送出装置２２０）からの統計情報が入力される。
【００９８】
最初の段の各単位スイッチ１１０内の統計情報処理装置５２０−１−１〜５２０−１−３は、それぞれの統計情報入力４２０から入力された統計情報を合計する。
【００９９】
いま、各インターフェース装置２０−１〜２０−９から出力された統計情報を、それぞれ、ａ１〜ａ９とする。この場合、単位スイッチ１１０−１−１内の統計情報処理装置５２０−１−１においては、ａ１，ａ２，ａ３が入力され、入力されさたａ１，ａ２，ａ３の合計値が計算され、計算された合計値（＝ａ１＋ａ２＋ａ３）が出力される。同様に、単位スイッチ１１０−１−２内の統計情報処理装置５２０−１−２においては、ａ４，ａ５，ａ６が入力され、入力されさたａ４，ａ５，ａ６の合計値が計算され、計算された合計値（＝ａ４＋ａ５＋ａ６）が出力される。同様に、単位スイッチ１１０−１−３内の統計情報処理装置５２０−１−３においては、ａ７，ａ８，ａ９が入力され、入力されさたａ７，ａ８，ａ９の合計値が計算され、計算された合計値（＝ａ７＋ａ８＋ａ９）が出力される。
【０１００】
初段の各単位スイッチ１１０内の統計情報処理装置５２０−１−１，５２０−１−２，５２０−１−３の出力を、それぞれ、ｂ１，ｂ２，ｂ３とする（すなわち、ｂ１＝ａ１＋ａ２＋ａ３、ｂ２＝ａ４＋ａ５＋ａ６、ｂ３＝ａ７＋ａ８＋ａ９である）。
【０１０１】
これらの値は、スイッチネットワーク１０の２段目の単位スイッチ１１０に転送される。
【０１０２】
２段目の各単位スイッチ１１０内の統計情報処理装置５２０−２−１，５２０−２−２，５２０−２−３も、それぞれ入力された統計情報を合計する。この場合、統計情報処理装置５２０−２−１，５２０−２−２，５２０−２−３のいずれにおいても、ｂ１，ｂ２，ｂ３が入力され、入力されさたｂ１，ｂ２，ｂ３の合計値が計算され、計算された合計値（＝ｂ１＋ｂ２＋ｂ３）が出力される。
【０１０３】
統計情報処理装置５２０−１−１，５２０−１−２，５２０−１−３の出力を、ｃ１（＝ｂ１＋ｂ２＋ｂ３）とすると、ｃ１＝ａ１＋…＋ａ９となる。したがって、各インターフェース装置２０から出力された統計情報の合計値が、２段目の各単位スイッチ１１０内の統計情報処理装置５２０−２−１，５２０−２−２，５２０−２−３から出力される。
【０１０４】
これらの値は、スイッチネットワーク１０の３段目の単位スイッチ１１０に転送される。
【０１０５】
３段目の各単位スイッチ１１０内の統計情報処理装置５２０−３−１，５２０−３−２，５２０−３−３には、いずれも、ｃ１の値が入力される。３段目の各単位スイッチ１１０内の統計情報処理装置５２０−３−１，５２０−３−２，５２０−３−３は、いずれも、入力された値をそのまま出力する。なお、例えば、前の段の単位スイッチの計算結果の確認をするために各入力の値が等しいかどうかの比較を行う機能を持たせることも可能である。
【０１０６】
そして、統計情報出力４４０−１〜４４０−９から出力された統計情報（ｃ１）は、それぞれインターフェース装置２０−１〜２０−９（の統計情報受信装置２４０）へ転送される。
【０１０７】
なお、上記では、３段目の各単位スイッチ１１０内の統計情報処理装置５２０が入力された統計情報をそのまま出力するようにしているが、１段目または３段間の各単位スイッチ１１０内の統計情報処理装置５２０が入力された統計情報をそのまま出力するように、各段の各単位スイッチ１１０内の統計情報処理装置５２０に演算処理を割り当てるようにすることも可能である。
【０１０８】
このように、各インターフェース装置２０から出力された統計情報の合計値が、スイッチネットワーク１０の各単位スイッチ１１０内の統計情報処理装置５２０の協調処理によって、求められる。その結果は、各インターフェース装置２０に転送され、各インターフェース装置２０から出力されるパケットの出力制御に用いられる。各インターフェース装置２０から出力された各出力ポートに向かうパケット数を統計情報として出力すれば、スイッチネットワーク１０から出力される統計情報は、各インターフェース装置２０からスイッチネットワーク１０に出力された出力ポート毎のパケット数の合計値となり、例えば、特定の出力ポートについてのこの合計値が大きければ、その出力ポートには多くのパケットが出力されていることになり、その値が出力ポートの出力レートより大きければ、輻輳が発生するので、出力を制限するような制御を行うことができる。
【０１０９】
図１５に、このような統計情報の処理を行うための統計情報処理装置５２０の構成例を示す。
【０１１０】
図１５に示した統計情報処理装置５２０は、下位ビットから直列に入力される統計情報を加算する機能を実現するものである。
【０１１１】
図１５に示した統計情報処理装置５２０は、排他論理和ゲート８１１と、ＡＮＤゲート８１２，８１３，８１４と、ＯＲゲート８１５と、フリップフロップ８１６とで構成される。
【０１１２】
フリップフロップ８１６は、加算結果の繰り上げを保持する。
【０１１３】
３つのＡＮＤゲート８１２，８１３，８１４とＯＲゲート８１５は、入力Ａと入力Ｂと前のビットの繰り上げビットから繰り上げビットを計算し、３入力排他論理和ゲート８１１は、入力Ａと入力Ｂと前のビットの繰り上げビットの加算結果を出力する。
【０１１４】
このような統計情報処理装置５２０をツリー状に接続する（ある統計情報処理装置５２０のＺ出力を後段の統計情報処理装置５２０のＡ入力またはＢ入力に接続する構成を、適宜組み合わせる）ことによって、多入力の場合でも加算処理を行うことができる。
【０１１５】
図１６に、統計情報処理装置５２０の他の構成例を示す。
【０１１６】
図１６に示した統計情報処理装置５２０は、下位ビットから直列に入力される統計情報を乗算する機能を実現するものである。
【０１１７】
図１６に示した統計情報処理装置５２０は、フリップフロップ８２１−１〜８２１−４，８２２−１〜８２２−４と、ＡＮＤゲート８２３−１〜８２３−４と、加算器（ＡＤＤ）８２４−１−１，８２４−１−２，８２４−２−１とで構成される。
【０１１８】
このような統計情報処理装置５２０をツリー状に接続する（ある統計情報処理装置５２０のＺ出力を後段の統計情報処理装置５２０のＡ入力またはＢ入力に接続する構成を、適宜組み合わせる）ことによって、多入力の場合でも乗算処理を行うことができる。
【０１１９】
もちろん、他の論理演算も同様に可能である。
【０１２０】
図１７は、スイッチネットワーク１０を構成する各単位スイッチ１１０内の統計情報処理装置５２０の他の動作例（処理方法の例）を示した図である。
【０１２１】
図１７でも、図１４と同様、３入力３出力の単位スイッチ１１０を用いて９入力９出力のスイッチネットワーク１０を構成した場合の例を示している。なお、図１７の統計情報処理装置５２０−１−１は図２の単位スイッチ１１０−１−１に対応し、他も同様である。
【０１２２】
図１７において、統計情報入力と統計情報出力の組４２０−１／４４０−１〜４２０−９／４４０−９にそれぞれ対応するインターフェース装置を２０−１〜２０−９で表すものとする。
【０１２３】
図１７に示したスイッチネットワーク１０では、インターフェース装置２０−１〜２０−９からの統計情報ｘ１〜ｘ９の他に、各単位スイッチでそれぞれ保持している統計情報ａ１，ａ２，ａ３，ｂ１，ｂ２，ｂ３，ｃ１，ｃ２，ｃ３の合計も加算するようにしたものである。
【０１２４】
この例の場合、統計情報は、２つのフィールドを持ち、各単位スイッチの統計情報処理装置５２０は、それぞれのフィールドに対して処理を行う。
【０１２５】
この例では、まず、３段目の単位スイッチの統計情報処理装置５２０−３−１〜５２０−３−３は、第１のフィールドにその単位スイッチで保持している統計情報ｃ１，ｃ２，ｃ３を出力する。これらの値は、インターフェース装置２０−１〜２０−３，２０−４〜２０−６，２０−７〜２０−９に転送される。
【０１２６】
インターフェース装置２０−１〜２０−３，２０−４〜２０−６，２０−７〜２０−９では（例えば統計情報受信装置２４０および統計情報送出装置２２０によって）、第１のフィールドに各インターフェース装置２０−１〜２０−３，２０−４〜２０−６，２０−７〜２０−９で保持している統計情報ｘ１〜ｘ３，ｘ４〜ｘ６，ｘ７〜ｘ９をそれぞれ出力し、第２のフィールドＸ１，Ｘ２，Ｘ３に３段目の単位スイッチから出力された統計情報ｃ１，ｃ２，ｃ３をそのまま出力する。すなわち、インターフェース装置２０−１〜２０−９は、それぞれ、（ｘ１，ｃ１），（ｘ２，ｃ１），（ｘ３，ｃ１），（ｘ４，ｃ２），（ｘ５，ｃ２），（ｘ６，ｃ２），（ｘ７，ｃ３），（ｘ８，ｃ３），（ｘ９，ｃ３）を送出する。
【０１２７】
これらの値は、スイッチネットワーク１０の１段目の単位スイッチ１１０に転送される。
【０１２８】
１段目の各単位スイッチ１１０内の統計情報処理装置５２０−１−１〜５２０−１−３では、入力された統計情報の第１のフィールドの合計値と第２のフィールドの一つとを合計する（第２のフィールドは、すべて同じ値が保持されているので、任意の一つを選択する）。その結果を統計情報の第２のフィールドに出力する。すなわち、統計情報処理装置５２０−１−１の第２の出力Ａ１は、ｃ１＋ｘ１＋ｘ２＋ｘ３となり、統計情報処理装置５２０−１−２の第２の出力Ａ２は、ｃ２＋ｘ４＋ｘ５＋ｘ６となり、統計情報処理装置５２０−１−３の第２の出力Ａ３は、ｃ３＋ｘ７＋ｘ８＋ｘ９となる。統計情報の第１のフィールドには、各単位スイッチ１１０内の統計情報処理装置５２０−１−１〜５２０−１−３でそれぞれ保持している統計情報ａ１，ａ２，ａ３を出力する。
【０１２９】
これらの値は、スイッチネットワーク１０の２段目の単位スイッチ１１０に転送される。
【０１３０】
２段目の各単位スイッチの統計情報処理装置５２０−２−１〜５２０−２−３では、入力された統計情報の第１のフィールドの合計値と第２のフィールドの合計値を加算する。その結果を、統計情報の第２のフィールドに出力する。すなわち、各単位スイッチ１１０内の統計情報処理装置５２０−２−１〜５２０−２−３の第２の出力Ｂ１には、Ａ１＋Ａ２＋Ａ３＋ａ１＋ａ２＋ａ３＝ｃ１＋ｃ２＋ｃ３＋ｘ１＋…＋ｘ９＋ａ１＋ａ２＋ａ３が出力される。統計情報の第１のフィールドには、各単位スイッチ１１０内の統計情報処理装置５２０−２−１〜５２０−２−３でそれぞれ保持している統計情報ｂ１，ｂ２，ｂ３を出力する。
【０１３１】
これらの値は、スイッチネットワーク１０の３段目の単位スイッチ１１０に転送される。
【０１３２】
３段目の各単位スイッチ１１０内の統計情報処理装置５２０−３−１〜５２０−３−３では、入力された統計情報の第１のフィールドの合計値と第２のフィールドの一つを加算する（第２のフィールドは、すべて同じ値が保持されているので、任意の一つを選択する）。その結果を統計情報の第２のフィールドに出力する。すなわち、３段目の各単位スイッチ１１０内の統計情報処理装置５２０−３−１〜５２０−３−３の第２の出力Ｃ１には、Ｂ１＋ｂ１＋ｂ２＋ｂ３＝ｃ１＋ｃ２＋ｃ３＋ｘ１＋…＋ｘ９＋ａ１＋ａ２＋ａ３＋ｂ１＋ｂ２＋ｂ３が出力される。この値は、すべてのインターフェース装置（２０−１〜２０−９）から出力された統計情報とすべての単位スイッチ（１１０−１−１〜１１０−１−３，１１０−２−１〜１１０−２−３，１１０−３−１〜１１０−３−３）から出力された統計情報の合計値となる。
【０１３３】
なお、第１のフィールドは、前述したように各単位スイッチでそれぞれ保持している統計情報ｃ１，ｃ２，ｃ３を出力する。
【０１３４】
図１８は、スイッチネットワーク１０を構成する各単位スイッチ１１０内の統計情報処理装置５２０のさらに他の動作例（処理方法の例）を示した図である。
【０１３５】
図１８の例は、図１７と等価な統計情報の計算を行うものであるが、図１７と異なり、単位スイッチ１１０を４段にしている。４段目の各単位スイッチ１１０内の統計情報処理装置５２０−４−１〜５２０−４−３は、パケットのバッファリングを行わず、統計情報の処理のみを行う。
【０１３６】
図１７に示した構成例では、３段目の各単位スイッチ１１０内の統計情報処理装置５２０−３−１〜５２０−３−３の統計情報は、インターフェース装置２０−１〜２０−９を経由して１段目の単位スイッチ１１０の統計情報処理装置５２０−１−１〜５２０−１−３で処理していたが、図１８で示した方法では、インターフェース装置２０−１〜２０−９を介さずに統計情報の処理を行うことが可能となる。また、４段目の統計情報処理装置は、単位スイッチ１１０に組み込まずにインターフェース装置の一部として構成することも可能である。
【０１３７】
この場合、まず、インターフェース装置２０−１〜２０−３，２０−４〜２０−６，２０−７〜２０−９では、第１のフィールドに各インターフェース装置２０−１〜２０−３，２０−４〜２０−６，２０−７〜２０−９で保持している統計情報ｘ１〜ｘ３，ｘ４〜ｘ６，ｘ７〜ｘ９をそれぞれ出力する。
【０１３８】
これらの値は、スイッチネットワーク１０の１段目の単位スイッチ１１０に転送される。
【０１３９】
１段目の各単位スイッチ１１０内の統計情報処理装置５２０−１−１〜５２０−１−３では、入力された統計情報の第１のフィールドの値を合計する。その結果を統計情報の第２のフィールドに出力する。すなわち、統計情報処理装置５２０−１−１の第２の出力Ａ１は、ｘ１＋ｘ２＋ｘ３となり、統計情報処理装置５２０−１−２の第２の出力Ａ２は、ｘ４＋ｘ５＋ｘ６となり、統計情報処理装置５２０−１−３の第２の出力Ａ３は、ｘ７＋ｘ８＋ｘ９となる。統計情報の第１のフィールドには、各単位スイッチ１１０内の統計情報処理装置５２０−１−１〜５２０−１−３でそれぞれ保持している統計情報ａ１，ａ２，ａ３を出力する。
【０１４０】
これらの値は、スイッチネットワーク１０の２段目の単位スイッチ１１０に転送される。
【０１４１】
２段目の各単位スイッチの統計情報処理装置５２０−２−１〜５２０−２−３では、入力された統計情報の第１のフィールドの合計値と第２のフィールドの合計値とを合計する。その結果を、統計情報の第２のフィールドに出力する。すなわち、各単位スイッチ１１０内の統計情報処理装置５２０−２−１〜５２０−２−３の第２の出力Ｂ１には、Ａ１＋Ａ２＋Ａ３＋ａ１＋ａ２＋ａ３＝ｘ１＋…＋ｘ９＋ａ１＋ａ２＋ａ３が出力される。統計情報の第１のフィールドには、各単位スイッチ１１０内の統計情報処理装置５２０−２−１〜５２０−２−３でそれぞれ保持している統計情報ｂ１，ｂ２，ｂ３を出力する。
【０１４２】
これらの値は、スイッチネットワーク１０の３段目の単位スイッチ１１０に転送される。
【０１４３】
３段目の各単位スイッチ１１０内の統計情報処理装置５２０−３−１〜５２０−３−３では、入力された統計情報の第１のフィールドの合計値と第２のフィールドの一つを加算する（第２のフィールドは、すべて同じ値が保持されているので、任意の一つを選択する）。その結果を統計情報の第２のフィールドに出力する。すなわち、３段目の各単位スイッチ１１０内の統計情報処理装置５２０−３−１〜５２０−３−３の第２の出力Ｃ１には、Ｂ１＋ｂ１＋ｂ２＋ｂ３＝ｘ１＋…＋ｘ９＋ａ１＋ａ２＋ａ３＋ｂ１＋ｂ２＋ｂ３が出力される。
【０１４４】
これらの値は、スイッチネットワーク１０の４段目の単位スイッチ１１０に転送される。
【０１４５】
４段目の各単位スイッチ１１０内の統計情報処理装置５２０−４−１〜５２０−４−３では、入力された統計情報の第１のフィールドの合計値と第２のフィールドの一つを加算する（第２のフィールドは、すべて同じ値が保持されているので、任意の一つを選択する）。その結果を統計情報の第２のフィールドに出力する。すなわち、４段目の各単位スイッチ１１０内の統計情報処理装置５２０−４−１〜５２０−４−３の第２の出力Ｄ１には、Ｃ１＋ｃ１＋ｃ２＋ｃ３＝ｃ１＋ｃ２＋ｃ３＋ｘ１＋…＋ｘ９＋ａ１＋ａ２＋ａ３＋ｂ１＋ｂ２＋ｂ３が出力される。この値は、すべてのインターフェース装置（２０−１〜２０−９）から出力された統計情報とすべての単位スイッチ（１１０−１−１〜１１０−１−３，１１０−２−１〜１１０−２−３，１１０−３−１〜１１０−３−３）から出力された統計情報の合計値となる。
【０１４６】
次に、単位スイッチ１１０のパケット処理装置５１０の構成例について説明する。
【０１４７】
単位スイッチとしては、入力バッファ型スイッチ、出力バッファ型スイッチ、共通バッファ型スイッチなどを利用することができる。
【０１４８】
ここでは、共通バッファ型単位スイッチの構成例について説明する。
【０１４９】
図１９に、共通バッファ型単位スイッチの構成例を示す。
【０１５０】
図１９に示した共通バッファ型単位スイッチは、複数のパケット入力４１０−１〜４１０−Ｎと、複数のパケット出力４３０−１〜４３０−Ｎと、多重装置９１０と、分離装置９２０と、パケットバッファメモリ９３０と、バッファ管理装置９４０とで構成される。
【０１５１】
パケット入力から入力されたパケットは、多重装置９１０に入力され、多重されてパケットバッファメモリ９３０へ転送され、保持される。また、パケットの交換動作に必要な情報は、バッファ管理装置９４０に転送される。バッファ管理装置９４０は、入力されたパケットの交換情報から、そのパケットが書き込まれるパケットバッファメモリ９３０のアドレスを生成して、パケットバッファメモリ９３０に転送する。パケットバッファメモリ９３０は、多重装置９１０から転送されたパケットを、バッファ管理装置９４０から転送されたアドレスに書き込む。
【０１５２】
また、パケットを読み出すときは、バッファ管理装置９４０が、読み出しアドレスを生成して、パケットバッファメモリ９３０に転送する。パケットバッファメモリ９３０は、バッファ管理装置９４０から転送された読み出しアドレスで指示されたアドレスに保持されているパケットを読み出し、分離装置９２０へ転送する。分離装置９２０では、パケットバッファメモリ９３０から出力された多重されたパケットを分離してパケット出力４３０から出力する。
【０１５３】
このような動作により交換動作を行う。
【０１５４】
図２０に、共通バッファ型単位スイッチの他の構成例を示す。
【０１５５】
図２０に示した共通バッファ型単位スイッチは、図１９に示した共通バッファスイッチに加え、フロー制御入力９５０−１〜９５０−Ｎとフロー制御出力９６０−１〜９６０−Ｎを持つ。
【０１５６】
フロー制御は、パケットの廃棄防止を目的として用いられ、受信側スイッチが送信側に対して受け入れ可能を知らせる方式（ＲＤＹ方式）、送信側がスイッチのパケットを送出し、受信側スイッチが受信を確認したことを知らせる方式（ＡＣＫ方式）などがある。
【０１５７】
この例で用いるフロー制御出力は、バッファ管理装置９４０がパケットバッファメモリ９３０の状態を観測しながら出力する。ＡＣＫ方式の場合は、パケットを受信し、バッファに空きがあり、パケットを保持することが可能なときに受信確認信号を出力する。ＲＤＹ方式の場合は、バッファの状態を観測し、バッファに十分な空きがある場合に受け入れ可能を示す信号を送出し、パケットの出力を促す。
【０１５８】
また、フロー制御入力は、バッファ管理装置９４０に転送され、バッファ管理装置９４０は、フロー制御入力に応じてパケットの出力を制御する。ＡＣＫ方式の場合は、受信確認信号を受け取ると、送出したパケットを廃棄し、受信が拒絶された場合は、再び同じパケットを出力する。ＲＤＹ方式の場合は、受け入れ可能を示す信号を受信したときに、パケットを出力する。
【０１５９】
図２１に、共通バッファ型単位スイッチのさらに他の構成例を示す。
【０１６０】
図２１に示した共通バッファ型単位スイッチは、図２０に示した共通バッファスイッチに加え、パケット入力部に入力毎のパケットバッファ９７０−１〜９７０−Ｎとパケット出力部に出力毎のパケットバッファ９８０−１〜９８０−Ｎを持つ。
【０１６１】
これらのパケットバッファは、フロー制御入力とフロー制御出力を持ち、バッファ管理装置９４０や、他のスイッチ、インターフェース装置とフロー制御信号を送受し、パケット廃棄が起こらないようにフロー制御を行う。
【０１６２】
単位スイッチでは、複数の入力からのパケットを処理しなければならないので、フロー制御信号を生成するのに時間が必要となる。しかし、図２１に示すような入力毎、出力毎のパケットバッファを用いることで、単一の入出力からのフロー制御信号のみを処理すれば良いので、フロー制御信号の生成に要する時間を短くすることができ、迅速なフロー制御を行うことが可能となる。
【０１６３】
次に、輻輳状態の判定方法について説明する。
【０１６４】
輻輳状態の判定方法として、前述した、スイッチネットワーク１０に送出されたそれぞれの出力ポート毎のパケット数の合計値を用いる方法がある。この方法は、合計値が定められたしきい値を越えたときに輻輳と判定する。
【０１６５】
輻輳状態の判定の別の方法に、スイッチネットワーク１０に帯留しているパケット数を用いる方法がある。前述したパケット数の合計値は、一定期間にスイッチネットワーク１０へ送出されたパケットの合計値であるので、スイッチネットワーク１０から送出されたパケット数に関しては、考慮されていない。スイッチネットワーク１０から送出されたパケット数を考慮するために、該当する出力ポートの統計情報送出装置２２０は、スイッチネットワーク１０に送出されたパケット数から、インターフェース装置２０のパケット受信装置２３０で受信されたパケット数を減じた値を統計情報として送出する。これによって、スイッチネットワーク１０内に帯留しているパケット数を計算することができる。この値と定められたしきい値とを比較することによって、輻輳を判定することも可能である。
【０１６６】
図２２に、この場合の動作例を示す。統計情報の処理については図１４の例と同様とする。
【０１６７】
図２２では、出力ポート６に関する統計情報を処理している場合の例を示している。
【０１６８】
出力ポート６以外のインターフェース装置２０−１〜２０−５，２０−７〜２０−９からは、観測周期の間にスイッチネットワーク１０に送出されたパケット数が統計情報として送出される。
【０１６９】
出力ポート６のインターフェース装置２０−６からは、スイッチネットワーク１０に送出されたパケット数からスイッチネットワーク１０からインターフェース装置２０へ送出されたパケット数を減じた値が送出される。図２２では、‘４−１６’と記述されており、これは、スイッチネットワーク１０に４個のパケットが送出され、スイッチネットワーク１０から１６個のパケットが受信されたことを意味しており、実際には、減算を行った結果の‘−１２’という値が送出される。
【０１７０】
１段目の各単位スイッチ１１０内の統計情報処理装置５２０−１−１，５２０−１−２，５２０−１−３では、それぞれの統計情報からの入力された値を合計した値が統計情報（２５，−７，２４）として出力される。
【０１７１】
同様に、２段目の各単位スイッチ１１０内の統計情報処理装置５２０−２−１，５２０−２−２，５２０−２−３でも、それぞれの統計情報からの合計値（４２）が出力される。
【０１７２】
３段目の各単位スイッチ１１０内の統計情報処理装置５２０−３−１，５２０−３−２，５２０−３−３では、入力された統計情報（４２）をそのまま出力する。
【０１７３】
すなわち、結果としてパケット数＝４２個を示す統計情報が各々のインターフェース装置２０−１〜２０−Ｎに送出される。
【０１７４】
これは、この観測周期において、出力ポート６に向かうパケットがスイッチネットワークに４２個帯留したことを意味する。各インターフェース装置２０−１〜２０−Ｎでは、各出力ポート毎のこの帯留パケット数を示す値を積算していくことで、スイッチネットワーク１０内に帯留している全パケット数を把握することができる。この値を用いて輻輳を判定することも可能である。
【０１７５】
次に、インターフェース装置２０でのトラヒックの制限方法について説明する。
【０１７６】
トラヒックの制限方法として、輻輳と判定された場合にトラヒックの送出を停止する方法がある。
【０１７７】
また、別のトラヒックの制限方法として、各インターフェース装置２０毎に送出可能数をカウントするカウンタを持ち、スイッチネットワーク１０から送出された統計情報をもとに、カウンタの値をセットし、スイッチネットワーク１０へパケットを送出するたびにカウンタの値を減じ、カウンタの値が０になったらパケットの送出を停止することによってトラヒックを制限する方法がある。
【０１７８】
図２３に、このようなトラヒック制限を行う、各々のインターフェース装置２０内に設けられるトラヒック制御装置の構成例を示す。
【０１７９】
図２３に示したトラヒック制御装置は、送出可能数計算装置１１４０と、出力ポート毎の送出可能数カウンタ１１１０−１〜１１１０−Ｎと、出力ポート毎の送出許可レジスタ１１３０−１〜１１３０−Ｎとで構成される。
【０１８０】
送出可能数計算装置１１４０には、統計情報受信装置２４０（図９参照）から統計情報が転送される。送出可能数計算装置１１４０は、受信した統計情報に基づいて、スイッチネットワーク１０に送出可能なパケット数を計算する。送出可能なパケット数は、出力ポート毎に設けられた送出可能数カウンタ１１１０−１〜１１１０−Ｎに転送される。また、送出許可レジスタ１１３０−１〜１１３０−Ｎにも転送される。
【０１８１】
各送出可能数カウンタ１１１０−１〜１１１０−Ｎでは、送出可能数計算装置１１４０から転送された送出可能なパケット数を受信し、その値をセットする。また、検索機能付きパケットバッファ２１２（図９参照）から出力されたパケットの宛先情報を受信し、該当する出力ポートが含まれていたらカウンタの値を減じる。各送出可能数カウンタ１１１０−１〜１１１０−Ｎのカウンタの値は、対応する送出許可レジスタ１１３０−１〜１１３０−Ｎに転送される。
【０１８２】
各送出許可レジスタ１１３０−１〜１１３０−Ｎは、対応する出力ポートが出力可能かどうかを示すレジスタである。各送出許可レジスタ１１３０−１〜１１３０−Ｎは、送出可能数計算装置１１４０から転送された送出可能数が１以上であればレジスタの内容を１にセットし、送出可能数カウンタ１１１０−１〜１１１０−Ｎの出力が０であれば０にリセットする。すなわち、送出可能数カウンタ１１１０−１〜１１１０−Ｎの値が０でなければ出力可能で、０になったら出力不可であることを示す。送出許可レジスタ１１３０−１〜１１３０−Ｎの出力は、検索機能付きパケットバッファ２１２に転送され、検索機能付きパケットバッファ２１２では、出力不可の宛先を含まないパケットが選択されて出力される。
【０１８３】
このようなトラヒック制御装置を用いることで、スイッチネットワークに送出するパケット数を制限することができる。
【０１８４】
図２４に、別のトラヒック制限を行う、各々のインターフェース装置２０内に設けられるトラヒック制御装置の構成例を示す。
【０１８５】
図２４に示したトラヒック制御装置は、送出可能数計算装置１１４０と、出力ポート毎の送出パケット数カウンタ１１１５−１〜１１１５−Ｎと、出力ポート毎の送出可能数レジスタ１１２０−１〜１１２０−Ｎと、出力ポート毎の比較装置１１２５−１〜１１２５−Ｎと、出力ポート毎の送出許可レジスタ１１３０−１〜１１３０−Ｎと、輻輳状態判定装置１１４７と、輻輳状態メモリ１１４５とで構成される。
【０１８６】
輻輳状態判定装置１１４７は、統計情報受信装置２４０（図９参照）からの統計情報に基づいて、それぞれの出力ポートの輻輳状態を判定し、その結果を輻輳状態メモリ１１４６に転送する。輻輳状態メモリ１１４６は、輻輳状態判定装置１１４７の結果を保持する。
【０１８７】
送出可能数計算装置１１４０には、輻輳状態メモリ１１４６からの出力、各送出パケット数カウンタ１１１５−１〜１１１５−Ｎからのそれぞれの出力、検索機能付きパケットバッファ２１２（図９参照）からのパケットバッファの状態を示すパケットバッファ状態情報が入力され、これらの情報に基づいて、出力可能数を計算する。
【０１８８】
出力可能数は、各送出可能数レジスタ１１２０−１〜１１２０−Ｎに保持される。送出パケット数カウンタ１１１５−１〜１１１５−Ｎと送出可能数レジスタ１１２０−１〜１１２０−Ｎの出力は、それぞれ、対応する比較回路１１２５−１〜１１２５−Ｎに転送され、比較結果が対応する送出許可レジスタ１１３０−１〜１１３０−Ｎに転送される。各送出許可レジスタ１１３０−１〜１１３０−Ｎは、送出パケット数が送出可能数より少なかった場合に送出許可信号を保持し、送出パケット数が送出可能数より多かった場合に送出不許可を保持する。
【０１８９】
このようなトラヒック制御装置を用いることで、スイッチネットワークに送出するパケット数を制限することができる。
【０１９０】
送出可能数計算装置１１４０は、種々の情報から送出可能数を計算する。送出可能数の計算サイクルをＴとすると、送出可能数は、０からＴまでの値を取る。
【０１９１】
例えば、輻輳状態メモリ１１４５の値によって、計算することができる。輻輳状態のときは、０で、非輻輳状態のときはＴとすることで、輻輳のときは出力停止で、輻輳でないときはいくらでも送出できるようにすることができる。
【０１９２】
また、スイッチネットワーク１０内に帯留しているパケット数の関数として計算することもできる。例えば、図２５に示すような関数（１）を用いることもできる。
ｆ（ｘ）＝Ａ／｛ｅｘｐ（ｘ−Ｂ）Ｃ＋１｝                      …（１）
ここで、Ａ，Ｂ，Ｃは、定数で、ｘは、帯留パケット数である。
【０１９３】
また、送出可能数を、Ｔをアクティブなインターフェース数で分割した値にすることもできる。ここで‘アクティブ’とは、ある出力ポートへ送出するパケットを持つことを意味する。すなわち、ある出力ポートへ出力するパケット数をアクティブなインターフェース数で均等に分割することにより、輻輳を発生させないようにトラヒックを制御することが可能となる。
【０１９４】
また、送出可能数を、それぞれのインターフェース装置からスイッチネットワークへ送出したパケット数に関連させることもできる。ある出力ポートからの送出可能数の最大値はＴであるので、Ｔをそれぞれの送出パケット数の比で分配することによって送出したパケット数の多いインターフェース装置は、多くのパケットを出力することが可能となる。アクティブなインターフェース数で均等に分割した場合は、多くの帯域を必要とするインターフェース装置も、少ない帯域で十分なインターフェースも同様に扱うが、送出したパケット数に関連させれば、必要とされる帯域をそれぞれのインターフェース装置に割り当てることができ、帯域の効率を向上させることができる。
【０１９５】
また、インターフェース装置のパケットバッファに保持されているパケット数から送出可能数を計算することもできる。パケットバッファに蓄積されているそれぞれの出力ポート毎のパケット数を用いて出力可能数を計算する。
【０１９６】
希望帯域を申告する場合は、アクティブなインターフェースの希望帯域を統計情報として送出し、その合計値を計算し、それぞれのインターフェース装置での希望帯域をその合計値でＴを分割した値にすることも可能である。
【０１９７】
さらに、輻輳状態に応じて出力可能数を計算することも可能である。例えば、輻輳が解除されたときに、多数のパケットがパケットバッファに蓄積されている場合がある。このような場合に無制限にパケットの送出を許可すると、再び輻輳を発生させる。このような輻輳の繰り返しを防ぐために、輻輳から解除されたときは、少しずつ送出可能数を増加させるようにすることで輻輳の再発を防止することが可能となる。
【０１９８】
また、送出可能数と送出パケット数と関連させることもできる。例えば、送出可能数をｔとし、送出パケットの合計をｐとし、インターフェース数をｎとする。この場合、すべてのインターフェース装置２０が送出可能数までパケット保持しており、パケットを送出したとすると、ｐ＝ｎ×ｔとなる。しかし、送出するパケットがなかった場合には、ｐ＜ｎ×ｔとなり、ｎ×ｔ−ｐのパケットを送出することが可能である。また、パケットを送出可能なインターフェースがパケットを送出可能数まで出力したと仮定すると、送出したインターフェース数は、ｐ／ｔとなる。これらのインターフェースでｎ×ｔ−ｐを分けると、新たな送出可能数ｔｎｅｗは、ｔｎｅｗ＝（ｎ×ｔ×ｔ）／ｐとなる。このような送出可能数の計算を行うことで、帯域の有効利用を実現することが可能となる。
【０１９９】
次に、可変長パケットを固定長パケットに分割して交換するパケット交換装置に本発明を適用した例について説明する。
【０２００】
パケット交換装置で扱うパケットは、ＩＰパケットのような可変長のパケットとＡＴＭセルのような固定長のパケットがある。
【０２０１】
ハードウェアで処理を行うときに、固定長パケットの方が扱いやすいので、可変長のパケットを固定長に分割して処理をする方法がある。
【０２０２】
この場合のインターフェース装置２０は、可変長のパケットを受信し、固定長のパケットに分割してスイッチネットワークに送出する。
【０２０３】
図２６に、このような機能を実現するインターフェース装置２０の構成例を示す。
【０２０４】
図２６に示したインターフェース装置２０は、パケットバッファ２５０と、パケット書き込み制御装置２５２と、パケットスケジューラ２５４と、パケット読み出し制御装置２５６と、統計情報送出装置２２０と、パケット受信装置２３０と、統計情報受信装置２４０とで構成される。
【０２０５】
インターフェース装置２０にパケットが入力されると、パケットは、パケットバッファ２５０とパケット書き込み制御装置２５２に転送される。パケット書き込み制御装置２５２では、入力されたパケットの長さ情報などからパケットを分割し、分割されたパケットが蓄積される書き込みアドレスを生成し、パケットバッファに転送する。その書き込まれたパケットに関する宛先情報、書き込みアドレスなどをパケットスケジューラ２５４に転送する。
【０２０６】
パケットスケジューラ２５４は、パケットのスケジューリングを行い、出力するパケットを決定し、読み出し制御装置２５６へ通知する。パケットスケジューラ２５４としては例えば図１０に示した検索機能付きパケットバッファを用いることができる。図１０では、パケットを保持していたが、ここでは、パケットの代わりにパケットＩＤを保持することによってパケット単位のスケジューリングを行うことができる。
【０２０７】
読み出し制御装置２５６は、パケットスケジューラ２５４から転送されたパケットＩＤにしたがって出力するパケットの読み出しを行う。パケットの読み出しが完了すると、パケットスケジューラ２５４に対してパケットの読み出しを通知し、パケットスケジューラ２５４は、読み出されたパケットのスケジューリングに必要な情報を開放する。例えば、読み出し制御装置２５６は、パケットをパケットＩＤ毎にリスト構造で保持する。パケットスケジューラ２５４からパケットＩＤを受信すると、そのパケットＩＤに対応するリストをたどって、分割されたパケットの読み出しを、パケットバッファ２５０に対して指示する。読み出された領域は、空きとなるので、空き領域が保持されているパケット書き込み制御装置２５２に転送され保持される。また、パケットＩＤに対応するパケットがすべて読み出されるとそのパケットＩＤは、空きとしてパケット書き込み制御装置２５２に転送され、保持される。
【０２０８】
パケット書き込み制御装置２５２では、パケット読み出し制御装置２５６から転送された空きパケットＩＤ、空き領域を保持し、新たに入力されたパケットの書き込みに用いられる。
【０２０９】
一般的に、多段接続スイッチにおいて、外部の速度より内部の動作速度を高速化することによってスループットが向上する。本発明でも内部速度の高速化を適用することができる。内部速度を高速化した場合、出力側で速度調整のためのバッファが必要となる。
【０２１０】
比較的大きい容量のバッファを持ちその出力行きのパケットが過負荷になっていると、バッファにパケットが溜り始める。すなわち、出力側のパケットバッファに保持されているパケット数によって輻輳状況に関する情報を得ることができる。この情報も、本発明で用いられる統計情報として利用することができる。
【０２１１】
また、統計情報は、パケットと同じ方向にながれても良い。例えば、パケットの一部として転送されることで、専用の信号線を不要とすることも可能である。
【０２１２】
また、統計情報は、パケットと反対方向にながれても良い。例えば、バックプレッシャー信号の一部として転送されることで、専用の信号線を不要とすることも可能である。
【０２１３】
なお、本実施形態の統計情報に関する処理機能やその他の制御機能は、ソフトウェアとしても実現可能である。また、本実施形態の統計情報に関する処理機能やその他の制御機能は、コンピュータに所定の手段を実行させるための（あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるための）プログラムを記録したコンピュータ読取り可能な記録媒体としても実施することもできる。
【０２１４】
本発明は、上述した実施の形態に限定されるものではなく、その技術的範囲において種々変形して実施することができる。
【０２１５】
【発明の効果】
本発明によれば、各インタフェース装置におけるパケットの統計情報を、スイッチネットワーク内の単位スイッチが分散協調的に処理するようにしたので、各インタフェース装置では当該パケット転送装置内の全体的なパケットの統計情報を把握することができ、単位スイッチが多段接続されたスイッチネットワークを持つパケット転送装置においてトラヒック制御を行うことが可能となる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係るパケット交換装置の構成例を示す図
【図２】スイッチネットワークの構成例を示す図
【図３】インターフェース装置の構成例を示す図
【図４】単位スイッチの構成例を示す図
【図５】単位スイッチの統計情報に関する動作の流れの一例を示すフローチャート
【図６】インターフェース装置の統計情報に関する動作の流れの一例を示すフローチャート
【図７】検索機能付きパケットバッファの入力動作例を示す図
【図８】検索機能付きパケットバッファの出力動作を示す図
【図９】インターフェース装置の他の構成例を示す図
【図１０】検索機能付きパケットバッファの構成例を示す図
【図１１】検索機能付きパケットバッファユニットの構成例を示す図
【図１２】検索機能付きパケットバッファの他の構成例を示す図
【図１３】インターフェース装置のさらに他の構成例を示す図
【図１４】統計情報処理装置の動作例を説明するための図
【図１５】加算を行う統計情報処理装置の構成例を示す図
【図１６】乗算を行う統計情報処理装置の構成例を示す図
【図１７】統計情報処理装置の他の動作例を説明するための図
【図１８】統計情報処理装置のさらに他の動作例を説明するための図
【図１９】共通バッファ型の単位スイッチの構成例を示す図
【図２０】共通バッファ型の単位スイッチの他の構成例を示す図
【図２１】共通バッファ型の単位スイッチのさらに他の構成例を示す図
【図２２】統計情報処理装置のさらに他の動作例を説明するための図
【図２３】トラヒック制御装置の構成例を示す図
【図２４】トラヒック制御装置の他の構成例を示す図
【図２５】出力可能数の関数の一例を示す図
【図２６】インターフェース装置のさらに他の構成例を示す図
【図２７】従来の多段接続されたスイッチネットワークの構成例を示す図
【図２８】従来の多段接続されたスイッチネットワークの他の構成例を示す図
【符号の説明】
１０…スイッチネットワーク
２０−１〜２０−Ｎ…インターフェース装置
３０−１〜３０−Ｎ…入力ポート
４０−１〜４０−Ｎ…出力ポート
１１０−１−１〜１１０−１−３，１１０−２−１〜１１０−２−３，１１０−３−１〜１１０−３−３…単位スイッチ
２１０…パケット送出装置
２１２…検索機能付きパケットバッファ
２１３…ＦＩＦＯ方式パケットバッファ
２１４…パケットバッファ制御装置
２２０…統計情報送出装置
２３０…パケット受信装置
２４０…統計情報受信装置
２５０…パケットバッファ
２５２…パケット書き込み制御装置
２５４…パケットスケジューラ
２５６…パケット読み出し制御装置
３１０，４３０−１〜４３０−Ｎ…パケット出力
３２０，４４０−１〜４４０−Ｎ，４４０−１〜４４０−９…統計情報出力
３３０，４１０−１〜４１０−Ｎ…パケット入力
３４０，４２０−１〜４２０−Ｎ，４２０−１〜４２０−９…統計情報入力
５１０…パケット処理装置
５２０，５２０−１−１〜５２０−１−３，５２０−２−１〜５２０−２−３，５２０−３−１〜５２０−３−３，５２０−４−１〜５２０−４−３…統計情報処理装置
６１０−１〜６１０−Ｎ…パケットバッファユニット
６２０…検索回路
６３０…制御信号
６４０…パケット出力バス
７１１−１〜７１１−Ｍ，７２１−１〜７２１−Ｎ，８１６，８２１−１〜８２１−４，８２２−１〜８２２−４…フリップフロップ
７１３−１〜７１３−Ｍ，７３７，７３９，７４５，８１２，８１３，８１４，８２３−１〜８２３−４…ＡＮＤゲート
７２３−１〜７２３−Ｎ…３状態バッファ
７３１，７３３，７３５…ＮＯＴゲート
７４１，７４３，８１５…ＯＲゲート
８１１…排他論理和ゲート
８２４−１−１，８２４−１−２，８２４−２−１…加算器
９１０…多重装置
９２０…分離装置
９３０…パケットバッファメモリ
９４０…バッファ管理装置
９５０−１〜９５０−Ｎ…フロー制御入力
９６０−１〜９６０−Ｎ…フロー制御出力
９７０−１〜９７０−Ｎ…入力ポート毎パケットバッファ
９８０−１〜９８０−Ｎ…出力ポート毎パケットバッファ
１１１０−１〜１１１０−Ｎ…送出可能数カウンタ
１１１５−１〜１１１５−Ｎ…送出パケット数カウンタ
１１２０−１〜１１２０−Ｎ…送出可能数レジスタ
１１２５−１〜１１２５−Ｎ…比較装置
１１３０−１〜１１３０−Ｎ…送出許可レジスタ
１１４０…送出可能数計算装置
１１４５…輻輳状態メモリ
１１４７…輻輳状態判定装置
【図１】
0003559496.tif 000002
【図２】
0003559496.tif 000003
【図３】
0003559496.tif 000004
【図４】
0003559496.tif 000005
【図５】
0003559496.tif 000006
【図６】
0003559496.tif 000007
【図７】
0003559496.tif 000008
【図８】
0003559496.tif 000009
【図９】
0003559496.tif 000010
【図１０】
0003559496.tif 000011
【図１１】
0003559496.tif 000012
【図１２】
0003559496.tif 000013
【図１３】
0003559496.tif 000014
【図１４】
0003559496.tif 000015
【図１５】
0003559496.tif 000016
【図１６】
0003559496.tif 000017
【図１７】
0003559496.tif 000018
【図１８】
0003559496.tif 000019
【図１９】
0003559496.tif 000020
【図２０】
0003559496.tif 000021
【図２１】
0003559496.tif 000022
【図２２】
0003559496.tif 000023
【図２３】
0003559496.tif 000024
【図２４】
0003559496.tif 000025
【図２５】
0003559496.tif 000026
【図２６】
0003559496.tif 000027
【図２７】
0003559496.tif 000028
【図２８】
0003559496.tif 000029