(57)【特許請求の範囲】
【請求項１】
データ・パケット宛先情報とペイロードとを含むデータ・パケットをトランスポートするためのスイッチング構成であって、前記データ・パケットが、スイッチング装置（１０）の１つまたは複数の入力ポート（２０）を介して、その１つまたは複数の出力ポート（３０）に向かい、前記スイッチング装置（１０）が、前記着信データ・パケットを前記データ・パケット宛先情報に応じて、前記出力ポート（３０）のうちの少なくとも１つの専用の出力ポートに経路指定することができ、これにより、すべての入力ポート（２０）の全体が、入力ポート（２０）のサブセットに分割され、各サブセットが、１つの前記入力ポート（２０）を含み、前記スイッチング構成が、
各入力ポート（２０）ごとに備えられた入力バッファ（１１）であって、前記スイッチング構成の有している出力ポート（３０）毎の入力待ち行列（１２）を備え、通信回線５０を介して前記入力ポートに着信されるデータ・パケットを前記入力待ち行列（１２）に格納する、入力バッファ（１１）と、
各入力ポート（２０）ごとの入力コントローラ（２５）であって、前記入力待ち行列（１２）から前記スイッチング装置（１０）への前記データ・パケットの多重化の順序を制御する役割をする入力コントローラ（２５）と、
前記スイッチング装置（１０）内の前記入力ポート（２０）の各サブセット毎の、出力バッファ（３５）であって、該出力バッファ（３５）中のアドレスで、前記入力ポート（２０）に着信する各前記データ・パケットの前記ペイロードを格納するための出力バッファ（３５）と、
前記スイッチング装置（１０）の有している出力ポート（３０）と同数の少なくとも１セットの出力待ち行列（１８）であって、その中に、前記出力バッファ（３５）内に格納された各前記ペイロードの前記アドレスを前記データ・パケット宛先情報に応じて分類して格納するための出力待ち行列（１８）と、
前記出力待ち行列（１８）と出力ポート（３０）の間に備えられ、前記出力待ち行列（１８）に格納された前記アドレスに在る前記ペイロードを、前記出力待ち行列（１８）ごとに対応する出力ポート（３０）に送る、共通出力ルータ（１４）と、
を含む、スイッチング構成。
【請求項２】
１つの共通出力ポート（３０）に属するすべての出力待ち行列（１８）の全体における占有された場所のしきい値を超えている場合、入力バッファ（１１）に信号を送るための出力待ち行列しきい値比較器（２２）が設けられることを特徴とする請求項１に記載のスイッチング構成。
【請求項３】
１つの共通出力ポート（３０）に属するすべての出力待ち行列（１８）の全体における占有された場所のしきい値を超えているという、しきい値比較器（２２）からの信号があったとき、前記入力コントローラ（２５）が、前記共通出力ポート（３０）に対応する入力待ち行列（１２）だけが、そのデータ・パケットを前記共通出力ポート（３０）に送信しないようにすることを特徴とする請求項２に記載のスイッチング構成。
【請求項４】
各出力バッファ（３５）ごとに、前記出力バッファ（３５）内の占有されたアドレスのしきい値を超えたことを、前記出力バッファ（３５）に対応する入力ポート（２０）のサブセットの入力バッファ（１１）に信号で知らせるために、出力バッファ・バックプレッシャ生成器が設けられることを特徴とする請求項１ないし３のいずれか一項に記載のスイッチング構成。
【請求項５】
前記１つまたは複数の出力バッファ（３５）の前記アドレスの使用を管理するための少なくとも１つのアドレス・マネージャ（１６）と、前記データ・パケットが、そこで前記１つまたは複数の出力バッファ（３５）内に格納される前記アドレスを前記出力待ち行列（１８）に入力するための少なくとも１つの出力待ち行列ルータ（１７）とをさらに含む請求項１ないし４のいずれか一項に記載のスイッチング構成。
【請求項６】
マルチキャスト・データ・パケットの場合、そのアドレスが、このマルチキャスト・データ・パケットが到達することになっている出力ポート（３０）に対する出力待ち行列（１８）のそれぞれにエントリとして入力可能であることを特徴とし、かつ前記アドレスが、前記マルチキャスト・データ・パケットのすべてのエントリが、前記マルチキャスト・データ・パケットをその指定された出力ポート（３０）に送達するのにうまく使用されたときにのみ、別のデータ・パケットに対する使用のために、アドレス・マネージャ（１６）によって解放可能であることを特徴とする請求項５に記載のスイッチング構成。
【請求項７】
異なる処理優先順位を有するデータ・パケットの場合、優先順位の各クラスごと、および各出力ポートごとに、別々の入力待ち行列（１２）が、入力バッファ（１１）内に設けられることを特徴とする請求項１ないし６のいずれか一項に記載のスイッチング構成。
【請求項８】
出力待ち行列（１８）が、全体で、対応する出力バッファ（３５）が、それぞれ有するアドレスの数よりも多くの、アドレスに対する待ち行列場所を提供することを特徴とする請求項１ないし７のいずれか一項に記載のスイッチング構成。
【請求項９】
少なくとも前記ペイロードを前記出力バッファ（３５）から前記出力ポート（３０）に送達するために、すべての出力バッファ（３５）をすべての出力ポート（３０）と接続する共通出力ルータ（１４）を含む請求項１ないし８のいずれか一項に記載のスイッチング構成。
【請求項１０】
前記着信するデータ・パケットのそれぞれについて、前記入力待ち行列（１２）のうちで前記対応するデータ・パケットの前記パケット宛先情報内で識別されるものにエントリを行うためのデマルチプレクサ（１９）を含み、これにより、各前記入力コントローラ（２５）が、前記入力待ち行列（１２）のうちの異なるものにそのエントリが配置され、かつ同一ペイロードを有するデータ・パケットの同時の伝送を可能にするように設計されている請求項１ないし９のいずれか一項に記載のスイッチング構成。
【請求項１１】
各前記エントリが、対応するデータ・パケットの少なくともペイロードまたは対応するデータ・パケットの少なくとも前記ペイロードがそこに格納されているメモリ・セルに対するポインタを含み、前記メモリ・セルが、好ましくは、共通入力バッファ内に配置されていることを特徴とする請求項１０に記載のスイッチング構成。
【請求項１２】
前記データ・パケットが、マルチキャスト・データ・パケットである場合、デマルチプレクサ（１９）が、前記入力待ち行列（１２）内にいくつかのエントリを行い、かつそのペイロードの１つのエントリのみを前記メモリ・セル内に行うように設計されていることを特徴とする請求項１１に記載のスイッチング構成。
【請求項１３】
スイッチング装置（１０）の１つまたは複数の入力ポート（２０）を介して、その１つまたは複数の出力ポート（３０）に向かうデータ・パケットのためのスイッチング方法であって、すべての入力ポート（２０）の全体が、入力ポート（２０）のサブセットに分割され、各サブセットが、１つの前記入力ポート（２０）を含み、
通信回線５０を介して前記入力ポートに着信されるデータ・パケットを、該データ・パケットの宛先である出力ポート（３０）に応じて、各入力ポート（２０）ごとに備えられた各入力バッファ（１１）の入力待ち行列（１２）内に格納するステップであって、前記入力待ち行列（１２）は前記スイッチング装置（１０）の出力ポート（３０）毎に備えられる、ステップと、
前記データ・パケットを、前記入力待ち行列（１２）から前記スイッチング装置（１０）に対して多重化するステップと、
前記スイッチング装置（１０）内の前記入力ポート（２０）のサブセットごとに存在する別々の出力バッファ（３５）内のアドレスに、前記入力ポート（２０）に着信する各前記データ・パケットの前記ペイロードを格納するステップと、
前記スイッチング装置（１０）内に前記スイッチング装置（１０）の出力ポート（３０）と同数の少なくとも１セットは存在する出力待ち行列（１８）内に、前記出力バッファ（３５）内に格納されている各前記ペイロードの前記アドレスを、前記データ・パケット宛先情報に応じて分類して格納するステップと、
前記出力待ち行列（１８）と出力ポート（３０）の間に備えられた共通出力ルータ（１４）が、前記格納されたペイロードを、前記出力待ち行列（１８）ごとに対応する出力ポート（３０）に送達するステップとを含む方法。
【請求項１４】
１つの共通出力ポート（３０）に属するすべての出力待ち行列（１８）の全体における占有された場所のしきい値を超えている場合、入力バッファ（１１）に信号でそれを知らせるステップを含む請求項１３に記載のスイッチング方法。
【請求項１５】
１つの共通出力ポート（３０）に属するすべての出力待ち行列（１８）の全体における占有された場所のしきい値を超えているという信号があったとき、前記入力バッファ（１１）内で、前記共通出力ポート（３０）に対応する入力待ち行列（１２）だけが、占有された場所の数が減少するまで、前記共通出力ポート（３０）にそのデータ・パケットを送達しないようにすることを特徴とする請求項１３または１４に記載のスイッチング方法。
【請求項１６】
対応する出力バッファ（３５）内での占有されたアドレスのしきい値を超えたことを前記入力ポート（２０）のサブセットの入力バッファ（１１）に信号で知らせるステップを含む請求項１３ないし１５のいずれか一項に記載のスイッチング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、いくつかの入力ポートおよびいくつかの出力ポートを備え、かつ前記出力ポートのうちの１つまたは複数の指定された出力ポートへおよびそこから後続の装置へ着信パケットをトランスポートするために決定されている、データのパケットのためのスイッチング構成に関する。より詳細には、本発明は、出力バッファが、各入力ポートまたは入力ポートの各サブセットごとに別々であるスイッチング構成および方法に関する。データ・パケットとして、特にＡＴＭセルまたは同じくイーサネット（Ｒ）・フレームが受入れ可能である。
【０００２】
【従来の技術】
情報の高速スイッチングは、それがアナログ信号のサンプルであれ、英数字データのサンプルであれ、通信ネットワーク内での重要なタスクである。様々な方向からの回線または伝送リンクが、そこで、それらの間で情報を交換するために相互接続されているネットワーク・ノードは、しばしば、伝送の遅延の原因である。多くのトラフィックが、ノード内に集中する場合、およびそのトラフィックのほどんどが、そのリンクのうちのいくつかだけを通過する場合、増大する遅延、またはさらには、情報の損失がしばしば発生する。したがって、高速の経路指定を可能にするスイッチング・ノードを有することが望ましい。
【０００３】
ＥＰ３１２６２８には、通信ネットワークの複数の着信伝送リンクおよび発信伝送リンクを相互接続するため、または着信および発信のコンピュータ接続リンクおよびワークステーション接続リンクの間で、データを交換するためのスイッチング装置が記載されている。さらに、知られているパケット・フォーマットが記載されている。
【０００４】
従来技術のスイッチング技術の概要が、インターネット・ページwww.zurich.ibm.com/Technology/ATM/SWOCPWP上で与えられており、そこでは、ＰＲＩＺＭＡチップの概要が図示されている。このトピックについての情報の別のソースは、W.E. Denzel、A.P.J. Engbersen、I.Iliadisにより、Computer Networks and ISDN System, (0169-7552/94), Elsevier Science B.V., Vol.27, No.4, pp.611-624で刊行された、「A flexible shared-buffer switch for ATM at Gbit/s rate」である。
【０００５】
ＰＲＩＺＭＡチップは、３００〜４００Ｍｂｉｔ／秒というポート速度を提供する１６の入力ポートおよび１６の出力ポートを有する共用共通出力バッファを含む。このスイッチの原理は、まず、着信パケットを完全並列Ｉ／Ｏ経路指定ツリーを介して着信パケットを経路指定し、次に、この経路指定済みパケットを出力バッファ内で待ち行列に入れることである。これに加えて、このチップは、データ（ペイロード）と制御（ヘッダ）フローの間での分離を利用する。ペイロードだけが、動的に共用される出力バッファリング・ストーレッジに格納される。このアーキテクチャを使用すると、行列の先頭の待ち行列化が回避される。ＰＲＩＺＭＡチップは、スケーラブルなアーキテクチャを有し、また、したがって、ポート速度、ポートの数、およびデータ・スループットをそれで増加させることが可能な、複数の拡張機能を提供する。これらの拡張は、ＰＲＩＺＭＡのモジュラー使用に基づいて実現することができる。また、単一段階または複数段階のスイッチ構成も、モジュラー方式で構成することができる。
【０００６】
ＰＲＩＺＭＡチップは、ＡＴＭ、すなわち、非同期転送モードに基づく広帯域遠隔通信に特に適している。ただし、その概念は、ＡＴＭ指向アーキテクチャの環境に限定されない。ＡＴＭは、しばしば、セルと呼ばれる短い、固定長パケットに基づいており、将来の公衆広帯域統合サービス・デジタル・ネットワーク（Broadband Integrated Services Digital Network）（ＢＩＳＤＮ）のための統合されたスイッチングおよび伝送の規格として適用されることが想定されている。競合解消のためのＰＲＩＺＭＡの接続形態および待ち行列付き構成は、高度の並列性を利用する。その経路指定機能は、分散方式でハードウェア・レベルで実行され、これは自己経路指定と呼ばれる。ＡＴＭパケットは、いくつかのパケット・タイプ、詳細には、異なるペイロード・サイズを有するパケット・タイプに分類され、ＰＲＩＺＭＡチップは、６４バイトまでのペイロードを有するパケットを専門に処理する。ただし、１２バイト、１６バイト、３２バイト、または４８バイトを有するパケット・ペイロードも、しばしば、トランスポートされる。
【０００７】
Ｎ個のポートを有する出力待ち行列付きスイッチの共用メモリを介する帯域幅は、Ｎに個別ポート速度を掛けたものに等しくなければならず、これは、高い回線速度では、かなりの実施上の懸念を生じる。このため、入力待ち行列付きスイッチが、近年、人気を得ている。ＦＩＦＯ待ち行列付きのクロスバー・ベースのスイッチのパフォーマンス限界は、良好なスループットを得るために、仮想出力待ち行列化（ＶＯＱ）などの技法を、集中スケジューリングと組み合わせて適用することによって、大体、克服されている。ＶＯＱは、着信パケットを、その着信パケットの宛先出力に基づいて入力側で分類することを伴う。
【０００８】
出力待ち行列化のみを利用するパケット・スイッチは、その高いメモリ帯域幅要件のため、高いデータ転送速度には、あまりよく拡張することができない。高度の並列性を利用する実施形態は、所望の帯域幅を実現することができるが、単一チップ上に組み込むことができるメモリの量を制限し、これにより、高いパケット損失比および高いトラフィック依存パフォーマンスをもたらす可能性がある。
【０００９】
発明の利点
本請求による本発明の利点は、それが、実質的に良好なパフォーマンスを維持しながら、既知の構成より少ない接続を必要とするスイッチング構成およびスイッチング方法を提供することである。仮想出力待ち行列化スキームが、行列の先頭のブロッキング効果を抑える役割をするので、いくつかの入力ポートの間で共用されるメモリは、それがＶＯＱの無いときに有していた効果をもはや有さない。実際、ＶＯＱを使用すると、出力バッファは、バースト性トラフィックまたはバックプレッシャにつながる条件の場合でさえ、ずっと高い充填度を有する。したがって、共用の利点は、極わずかなものとなる。スイッチング・インフラストラクチャ、すなわち、出力バッファおよびその環境の数を増やすことは、一見、ハードウェア空間の増大につながるが、結局、必要な配線を相当に減らすことになる。各入力ポートごとに出力バッファが、複数のＮ個のアドレスを提供し、Ｎが、入力ポートおよび出力ポートの数である実施形態を例にとると、配線は、Ｎ2分の１に抑えられる。各接続は、通常、１６ビット・バス接続であることを考慮し、Ｎ＝３２を使用すると、これは、完全共用出力バッファでは、３２×１６×１０２４＝５２４２８８の接続になり、これが、本明細書で提案する構成では、１０２４分の１に抑えられて、５１２個になる。各入力ポートのサブセットごとの出力バッファ空間は、このサブセットのサイズに応じて選択することができるので、このサブセットに対する出力バッファは、入力ポートのすべての間で共用されるために使用された出力バッファよりも少なく選択することができる。Ｎ×Ｎの合計出力バッファ・サイズの場合、これは、入力ポート当たり、Ｎ個のアドレスのアドレス空間が予約され、これが、本明細書に記載する各出力バッファごとの構成でも使用され得ることを意味する。各単一入力ポートごとに、独自の出力バッファが配置される実施形態では、これは、それぞれのそうした出力バッファが、Ｎ個のアドレスを提供することになることを意味する。
【００１０】
さらに、スイッチ・インフラストラクチャを倍増することによって、アドレス・マネージャは、Ｎ分の１小さいアドレス空間を扱えばよいことになり、したがって、汎用アドレス・マネージャのビットの半分だけを使用する。また、出力待ち行列も、より小さく、すなわち、より少ない待ち行列場所を有するように設計することが可能である。したがって、この倍増は、結局、空間要件の点で、実際の倍増をもたらさない。したがって、配線の複雑さを抑えることでの前述の利点は、機能グループを倍増することによる空間要件の増加によって打ち消されることはない。
【００１１】
選択は、どれほど大きくそのサブセットを選択するかである。サブセットは、単一入力ポートから成ることが可能であり、これは、入力ポート当たり１つの出力バッファをもたらす。別の選択は、２つの入力ポートを１つのサブセットに一緒に入れることであり得、このサブセットは、この場合、その出力バッファを共用する。また、非一様のサブセットも形成することができ、これは、１つのサブセットが、１つの入力ポートから成り、別のものが、２つを有し、さらに別のものが、４つを有するといったように、実際的であると思われるどのようなものでもよい。すべて同一サイズのサブセットを選択することが、最も有利であると思われる。というのは、この場合、最終レイアウトが一様となり、複雑さが減るからである。最適な解決は、入力ポート当たり１つの出力バッファを有することであるように思われる。
【００１２】
同一の出力ポートに関わるすべての出力待ち行列の充填度を一体化する共通しきい値比較器が有利である。というのは、これにより、この１つの出力ポートに向かう真のトラフィックが測定されて、入力待ち行列に対するフィードバックを作成するのに使用され、これが、競合の場合、有効なトラフィック制御をもたらすからである。
【００１３】
しきい値比較器からのフィードバックを入力待ち行列に選択的な方式で、すなわち、競合がそこで起きた対応する出力ポートに関するデータパケットを保持する入力待ち行列だけに配分することは、バックプレッシャによって不必要なブロッキング効果が導入されないという利点をもたらす。これにより、行列の先頭のブロッキング効果が、競合が起きた場合でさえ、回避される。
【００１４】
出力バッファがいっぱいであることによるデータ・パケットの損失が完全に回避されるということで、出力バッファ・バックプレッシャの生成が、実際的である。
【００１５】
マルチキャスト・データ・パケットの処理は、出力バッファ内に一度だけペイロードを格納して、そのアドレスをこのデータ・パケットが向かうすべての出力ポートの出力待ち行列内に入力することによって解決することが可能である。カウンタを使用することができ、これは、アドレスが出力待ち行列から読み出されるたびに毎回、減分され、ゼロに達したときに、さらなる使用のためにそのアドレスの解放を可能にする。
【００１６】
異なる優先順位を扱うための異なる入力待ち行列が、より高い優先順位のデータ・パケットがより低い優先順位のものを追い越すことを可能にする。
【００１７】
出力待ち行列が、出力バッファの有するアドレスの数よりも多くの待ち行列場所を有するとき、様々な入力待ち行列の間での非均一な分配が、データ・パケットを失うことなしに、処理され得る。各出力待ち行列が、対応する出力バッファ内のアドレスの数に等しい待ち行列場所の数を有する場合、完全非均一な分配を完全にバッファに入れることが可能である。
【００１８】
マルチキャスト・データ・パケットを処理する１つの方式は、各専用出力ポートごとにコピーを対応する入力待ち行列に入れて、出力ポートの状況がそれを許す場合、これらのコピーを同時に多重化することである。
【００１９】
また、入力バッファ１１内で、ヘッダだけを待ち行列化して、共通入力バッファとも呼ばれる別々のメモリ・セクション内にペイロードを格納するシステムも実現可能である。そうした場合、マルチキャスト・データ・パケットのペイロードは、一度、格納されるだけでよく、これは、メモリ空間を節約する。
【００２０】
【発明が解決しようとする課題】
本発明は、データ・パケット宛先情報のセクションおよびペイロード・セクションを含むデータ・パケットを１つまたは複数の出力ポートにトランスポートするためのスイッチング構成を提案する。このスイッチング装置は、着信するデータ・パケットをデータ・パケット宛先情報に応じて、出力ポートのうちの少なくとも１つの専用の出力ポートに経路指定することができる。これは、各入力ポートで、存在する出力ポートの数と少なくとも同じ数の単独入力待ち行列を有する入力バッファと、対応する入力バッファの入力待ち行列からスイッチング装置にデータ・パケットを転送する順序を制御する役割をする、各入力ポートごとの入力コントローラとを含む。
【００２１】
【課題を解決するための手段】
スイッチング装置内の各入力ポートは、少なくとも前記入力ポートに着信する各データ・パケットのペイロードをその中のアドレスで格納するために、その別々の出力バッファを有する。
【００２２】
また、スイッチング装置内の各入力ポートごとに、このスイッチング構成の有している出力ポートの数と同じ数の出力待ち行列が配置されている。これらの出力待ち行列内に、少なくとも、出力バッファ内に格納されている各ペイロードのアドレスが格納され、そのデータ・パケット宛先情報に応じて分類されている。格納されたペイロードは、この時点で、格納されたアドレスの使用下にある、それが向けられた少なくとも１つの出力ポートに送達可能である。
【００２３】
言い換えれば、出力バッファは、各入力ポートが、その他の入力ポートから到達可能ではないそれ独自の出力バッファを有するように分離される。したがって、その出力バッファに適切なエントリを行う役割をする入力ルータも、それに機能を提供し、かつそこからデータ・パケットのペイロードを受け取る入力ポートを１つしか有していないということで、そのサイズが抑えられる。各入力ポートは、また、それ独自のセットの出力待ち行列、およびこの出力待ち行列にエントリを行うための、それ独自の出力待ち行列ルータも有する。
【００２４】
入力ポートは、出力バッファ空間を共用しないが、仮想出力待ち行列の使用により、出力バッファ空間が、１つの入力ポートによって有効に使用されず、したがって、他の入力ポートによって使用され得る確率が、無視できるほど低くなるという利点が生じる。すべての出力ポートが、どの一時点でも、送信するデータ・パケットを有していなければならないという目標が、こうして維持され、より複雑な構成を使用した場合と同様に、それが満たされる。ただし、出力バッファ空間の区分または分割のため、入力バッファとスイッチング装置の間で必要な接続の数が相当に減少する。
【００２５】
前述の概念は、各入力ポートが、その出力バッファを有する実施形態に限定されない。一般的に言って、入力ポートの全体を任意の一組の入力ポートのサブセットに下位分割することができ、次に、これらが、共通出力バッファを有することになる。サブセットとして一緒にグループ化された入力ポートは、したがって、すべてまとめてスイッチング・セクションと呼ばれる、出力バッファ、アドレス・マネージャ、出力待ち行列ルータ、出力待ち行列、および入力ルータなどの、対応するリソースを共用することができる。例えば、ペアになって、入力ポートが、１つだけの共通スイッチング・セクションを有することができる。したがって、既に、複雑さの縮減を見ることができ、他方、パフォーマンスは、原則上、ほとんど、または全く影響を受けない。
【００２６】
アドレスの数が、合計でＮに掛けるＮ個の入力ポートの数を掛けたものに設定されている場合を考慮すると、配線の複雑さは、各入力ポートが、その独自のスイッチング・セクションを有する場合、Ｎ2分の１に抑えられる。
【００２７】
【発明の実施の形態】
下記に、本発明の様々な例としての実施形態を説明する。
【００２８】
図１で、データ・パケットを処理するための入力バッファ付きスイッチング構成を示している。この構成は、Ｎ個の入力ポート２０およびＮ個の出力ポート３０を備えたスイッチング装置１０を含む。「ＩＰ」とラベル付けされた各入力ポート２０に、「ＩＢ」とも呼ばれる入力バッファ１１が構成されている。各入力バッファ１１は、「Ｃｔｒｌ」とも呼ばれる入力コントローラ２５を含み、これは、それ自体、スイッチング装置１０に接続されている。この目的は、入力バッファ１１に通信回線５０を介して着信し、また出力ポート３０のうちの１つまたは複数に着信するものとされるデータ・パケットを、これらの出力ポート３０に導くことである。出力ポート３０から、データ・パケットは、それがさらなるスイッチング装置であれ、受信装置などであれ、後続の装置に送達することができる。
【００２９】
データ・パケットは、パケット・ヘッダ・セクションとパケット・ペイロード・セクションに分割する。パケット・ヘッダ・セクション内には、データ・パケット宛先情報が含まれ、これが、それぞれのデータ・パケットを出力ポート３０のうちのどれに送達するかを指示する。そのデータ・パケット宛先情報に関して、２つのタイプのデータ・パケットが存在し、これは、ユニキャスト・データ・パケットおよびマルチキャスト・データ・パケットである。ユニキャスト・データ・パケットは、出力ポート３０のうちの１つだけを宛先として有するデータ・パケットである。それとは対照的に、マルチキャスト・データ・パケットは、出力ポート３０のうちの複数のものに向けられている。したがって、定義上、マルチキャスト・データ・パケットは、そのペイロードが、いくつかの出力ポート３０に向けられているデータ・パケットである。データ・パケットのパケット・ペイロード・セクション内には、宛先に送達される任意のデータが含まれ得る。
【００３０】
入力バッファ１１は、それぞれ、複数の入力バッファ待ち行列に分割される。すなわち、各入力バッファ１１は、各出力ポート３０ごとに正確に１つの入力待ち行列１２を有する。したがって、各入力バッファ１１は、この場合、Ｎ個の入力待ち行列１２を含む。１つの入力バッファ１１内のこれらの入力待ち行列１２のそれぞれは、その中に、１つの専用出力ポート３０に対する着信データ・パケットを格納する役割をする。したがって、着信データ・パケットは、各入力バッファ１１内で、それらの宛先出力ポート３０に応じて分類される。したがって、ある出力ポート３０に対するユニキャスト・データ・パケットが、この出力ポート３０が使用中であるためにブロックされた場合、この行列の先頭でブロックするユニキャスト・データ・パケットによってブロックされるデータ・パケットは、同一の出力ポート３０に向かうデータ・パケットのみであり、別の出力ポート３０に向かうデータ・パケットは、それとは独立に処理されて、その宛先出力ポート３０に向かうパスが占有されていないとき、スイッチング装置１０に転送され得る。宛先ごとのこの分類は、仮想出力待ち行列化、略してＶＯＱとも呼ばれる。複数の入力待ち行列１２もまとめて、ＶＯＱと呼ばれる。
【００３１】
対応する通信回線５０に着信するデータ・パケットを正しい入力待ち行列１２に分配するため、入力バッファ１１は、入力待ち行列ルータＩＱＲとも呼ばれるデマルチプレクサ１９を含む。入力待ち行列１２からデータ・パケットを選択して、それらを対応する入力ポート２０を介して、スイッチング装置１０に送達するため、入力バッファ１１は、待ち行列セレクタＱＳとも呼ばれるマルチプレクサ２１を含む。マルチプレクサ２１は、任意の特定の時点で入力待ち行列１２のうちの１つを選択して、その入力待ち行列１２から１つのデータ・パケットを選出して、それを、その入力ポート２０を介して、スイッチング装置１０に送信する。この選択処理は、スイッチング装置１０から情報を得ている入力コントローラ２５によって制御される。入力コントローラ２５は、ある時点で、マルチプレクサ２１に、それがデータ・パケットをスイッチング装置１０に送信できるかどうかを合図して、それが可である場合、どの入力待ち行列１２からその出力ポート３０にそのデータ・パケットが送信され得るかを合図する。いくつかの入力待ち行列１２から待ち行列化されたデータ・パケットを取り出す順序は、なによりもまず、出力ポート３０のアクセス可能性、すなわち、その占有状態によって決定される。出力ポート３０がアイドルである場合、それは、データ・ケットを受信できる状態にあり、このことが、入力コントローラ２５に合図される。入力コントローラ２５は、どのデータ・パケットをどの時点で、入力バッファ１１からスイッチング装置１０に送信するかを選択するアービタを表示する。
【００３２】
共通出力バッファを備えた異なる構成では、いくつかの入力コントローラ２５の間で、待ち行列化されたデータ・パケットをスイッチング装置１０に送信する権利をその間で配分するポリシーが適用されなければならないことになる。ただし、本明細書に記載する構成では、各入力バッファ１１は、その他の入力ルータ１３とは独立に動作するそれ独自の入力ルータ１３を有し、またその他の出力バッファ３５とは独立したそれ独自の出力バッファ３５を有する。したがって、出力バッファ３５および入力ルータ１３の分割のため、各入力バッファ１１は、そのデータ・パケットをその他の入力バッファ１１とは独立に、出力バッファ３５に転送することができる。異なる入力バッファ３５間の唯一の依存関係は、下記に説明するバックプレッシャ機構に関わる。
【００３３】
マルチキャスト・データ・パケットは、その対応する出力ポート３０が、データ・パケット宛先ヘッダ内で示される各入力待ち行列１２にエントリを行うことによって、デマルチプレクサ１９で配分することができる。この場合、マルチキャスト・データ・パケットは、単にコピーされて、それ自体、それぞれのそうした入力待ち行列１２に入れられる。これは、複数のｎ個の異なる出力ポート３０に向かう各マルチキャスト・データ・パケットがコピーされて、待ち行列に入れられ、そのｎ個のコピーが、そのデータ・パケットがそこに着信した入力バッファ１１内に駐在することを意味する。マルチプレクサ２１側では、一度に１つだけのデータ・パケットを取り出す原理は、マルチキャスト・データ・パケットの場合、そのいくつかのコピーを一度にスイッチング装置１０に送信するのを許すように、変更することができる。言い換えれば、デマルチプレクサ１９で行われる、マルチキャスト・データ・パケットをコピーして配分することによって導入される欠点が、いくつかの等ペイロード・パケットをマルチプレクサ２１での１つの転送プロセスにマージすることの利点によって打ち消される。別法では、マルチキャスト・データ・パケットは、入力待ち行列１２のうちの１つの中にだけ、または別々のマルチキャスト待ち行列内に格納することができ、また一度だけ、出力バッファ３５内に格納されて、そこからすべてのその宛先出力ポート３０に非破壊方式で読み出すことが可能である。
【００３４】
スイッチング装置１０は、この場合、共通出力ルータ１４を含み、またその入力バッファ１１を備えた各入力ポート５０ごとに、別々のスイッチング・セクション１５を含む。それぞれのそうしたスイッチング・セクション１５は、出力バッファ３５と、入力ルータ１３と、出力待ち行列１８と、出力待ち行列ルータ１７と、アドレス・マネージャ１６とを含む。
【００３５】
各入力バッファ１１は、したがって、「ＩＲ」とも呼ばれるそれ独自の入力ルータ１３を有し、これに、対応する入力ポート２０を介して、入力バッファ１１が接続されている。入力ルータ１３の出力側には、「ＯＢ」とも呼ばれる出力バッファ３５が構成され、これが、入力ルータ１３から来るすべてのデータ・パケットのために機能する。出力バッファ３５の出力側は、「ＯＲ」とも呼ばれる共通出力ルータ１４につながっている。ルータ１３、１４は、この場合、各入力ポート２０ごとに、非ブロッキング方式で各出力ポート３０に到達する可能性を提供する。したがって、任意の時点で、各入力ポート２０は、データ・パケットを、そうしたデータ・パケットが着信している場合、出力ポート３０のうちのどれにでも送信することができる。
【００３６】
入力ルータ１３および出力バッファ３５と並列に、出力待ち行列ルータ１７および出力待ち行列１８が構成される。入力ポート２０は、したがって、出力待ち行列ルータ１７を介して、出力待ち行列１８につながり、またそこから、出力ルータ１４につながる。「ＡＭ」とも呼ばれるアドレス・マネージャ１６が、出力ルータ１４と入力ルータ１３の間、および出力ルータ１４と出力待ち行列ルータ１７の間に構成される。各出力ポート３０ごとに、「ＯＱ」とも呼ばれる出力待ち行列１８が構成されて、これが、出力ルータ１４に対する入力を提供し、また出力待ち行列ルータ１７から入力を受信する。
【００３７】
１つの入力ポート２０から着信するすべてのデータ・パケットは、その入力ルータ１３を介して、その出力バッファ３５に経路指定される。アドレス・マネージャ１６は、入力ルータ１３に、出力バッファ３５内のどの場所で、すなわち、その中のどのアドレスで、その着信データ・パケットが格納されるべきかの情報を提供する。出力バッファ３５内のどのアドレスで、特定の出力ポート３０に向かう各データ・パケットが格納されるかの情報は、出力待ち行列ルータ１７を介して、出力待ち行列１８に書き込まれる。この情報は、順序情報と呼ばれる。出力バッファ３５内に格納される各データ・パケットごとに、そうした順序情報が、このデータ・パケットがそこに送信されるべき出力ポート３０に属する出力待ち行列１８内の１つの場所に入れられる。このようにしてこれらのアドレスは、対応する出力ポート３０に応じて記憶される。それぞれのアドレスに格納されるパケットが目的地とする出力ポート３０に応じて、格納される。出力待ち行列１８のうちのどれに、それぞれのアドレスが付けられるかの分類情報は、入力バッファ１１から導出することができる。というのは、同じ待ち行列化原理が、データ・パケット全体に対して、そこで既に使用されているからである。したがって、待ち行列セレクタ２１の設定を出力待ち行列ルータ１７の設定として使用することができる。
【００３８】
各出力ポート３０は、したがって、それぞれの出力待ち行列１８において、当該出力ポートに到着すべきデータ・パケットの格納されたアドレスを検索することができる。アドレス・マネージャ１６は、この場合、同時に各出力待ち行列１８ごとに一時に１つのアドレスを扱う。これは、また、各入力ポート２０ごとに１つのアドレスが常に利用可能に保持されることも意味しており、これは、それぞれのデータ・パケットが着信する前に、既に行われ得る。行列の先頭で入力ポート２０に着信する各データ・パケットは、したがって、入力ルータ１３によってそこに導かれることになるアドレスを見出す。
【００３９】
このアドレスは、アドレス・マネージャ１６によって、出力待ち行列ルータ１７にも提供され、これが、さらなる入力の一部として、どの出力待ち行列１８に、すべての着信済みデータ・パケットに関する順序情報を入力するかに関するマスクを提供するデータ・パケット宛先情報を受信する。アドレスが入手できない場合は、下記に説明する。
【００４０】
すべての着信データ・パケットは、したがって、アドレス・マネージャ１６によってアドレスを与えられ、このアドレスで、このデータ・パケットが、次に、出力バッファ３５内に格納されて、これにより、そのアドレスは、そのデータ・パケットが向かう出力ポート３０に対応する出力待ち行列１８内の場所で格納される。そのための情報、すなわち、データ・パケット宛先情報は、パケット・ヘッダから導出することができる。出力ルータ１４が、各出力ポート３０ごとに、対応する出力待ち行列１８から次のアドレスを検索して、次に、どのアドレスにあるデータ・パケットを取り出し、それをそのデータ・パケットの宛先である出力ポート３０に送るということで、最終配分の役割をする。
【００４１】
取出しステップは、非破壊読取り処理であることが可能であり、これは、マルチキャスト・データ・パケットが、一度だけ出力バッファ３５内に格納されるが、このデータ・パケットを受信しなければならないすべての出力ポート３０がそれを受信するまで何度も読み取られるということで、マルチキャスト・データ・パケットを処理することを可能にする。データ・パケットを出力バッファ３５から読み取った後、それぞれのアドレスは、このアドレスがアドレス・マネージャ１６に送り戻され、これが、再び、このアドレスを入力ポート２０に、次に着信するデータ・パケットを処理するために割り当てることができるということで、解放される。マルチキャスト・データ・パケットの場合、図面に図示していないカウンタを使用することができ、これは、データ・パケットが格納されると、このデータ・パケットがそこに伝送されるべき出力ポート３０の数に設定され、このデータ・パケットが出力ルータ１４によって取り出されるたびに毎回、減分される。このカウンタが、このデータ・パケットに関して、読取り０に達したとき、対応するアドレスが、再使用のために解放され得る。
【００４２】
マルチキャスト・データ・パケットを処理するため、各格納場所とともに、占有カウンタを維持することができる。これらのカウンタは、ゼロに初期設定する。データ・パケットが着信したとき、アドレス・マネージャが、それが入手可能な場合、空きアドレスを提供し、そのデータ・パケットは、その場所で格納されることになり、入手可能でなければ、そのデータ・パケットは、その全体がドロップされることになる。対応する占有カウンタは、そのデータ・パケットのヘッダによって要求された宛先の数に設定される。アドレスは、データ・パケットがそれに向けられている各ＶＯＱに追加される。
【００４３】
あるアドレスが、出力ルータ３０によって選択されたとき、それに対応するデータ・パケットが、メモリから伝送される。そのアドレス自体は、アドレス・マネージャに戻され、それに、現行のサイクルでそのデータ・パケットがそこに伝送されている宛先の数を示す、出力ルータ３０によって決定されたカウントが付随する。アドレス・マネージャ１６は、この数だけ、占有カウンタを減分する。カウンタがゼロに達した場合、これは、データ・パケットが、そのすべての宛先に送達されたことを示し、そのアドレスが、空きプールに戻される。
【００４４】
いくつかのスイッチング・セクション１５、すなわち、いくつかのセットの出力待ち行列１８を有する場合、図には描いていない出力待ち行列仲裁ユニットを追加することが可能であり、これは、単一出力ポート３０に関して、その専用出力待ち行列１８のうちのどれが、ある時点で、そのエントリをその特定の出力ポート３０に送信することを許されるかを決定する。そうした出力待ち行列仲裁ユニットは、すべてではないにしても、いくつかの出力ポート３０に関する仲裁を処理するように設計することができる。
【００４５】
出力バッファ３５を共用することの原理は、出力待ち行列１８が全体で、出力バッファ３５の有する物理アドレスの数よりも多くの論理待ち行列場所を有するということで、これまで導入した。この処置により、入力待ち行列１２の間でのデータ・パケットの配分での非対称性をバッファに入れることができる。データ・パケットの総トラフィックが、出力バッファ３５の実際の最大容量を超えない限り、パフォーマンスは、向上することになる。というのは、この構成は、極度のトラフィック・パターン変化に関して、ずっと柔軟だからである。詳細には、バースト性のトラフィックをよりよく処理することができる。というのは、データ・パケット損失の確率が、入力待ち行列１２に、その公正な配分が提供するよりも多くの出力バッファ空間を使用することを許すことによって、抑えられるからである。
【００４６】
各入力ポート２０は、仮想出力待ち行列を備えたその入力バッファ１１を有する。すなわち、各入力バッファ１１内にある各出力待ち行列１８ごとに、入力待ち行列１２を備えている。入力バッファ１１は、それ独自の入力ルータ１３に接続されている。各入力バッファ１１は、また、その入力バッファ１１の異なる入力待ち行列１２から発信するデータ・パケットの順序を制御するために、それ独自の入力コントローラ２５も有する。各入力コントローラ２５は、その他の入力コントローラ２５とは独立に動作する。
【００４７】
入力コントローラ２５の独立性は、全体の制御リソースの複雑さを相当に抑える。各入力コントローラ２５は、この場合、所定の決定ポリシーによって着信するデータ・パケットを処理するだけでよく、このポリシーは、公平性優先順位および優先レベル優先順位を備えたラウンド・ロビン・ポリシー、またはＯＣＦ、ＦＩＦＯ、ＬＲＵなどのような、任意の他のポリシーであり得る。入力コントローラ２５のそれぞれは、個々に、それが格納したデータ・パケットのうちのどれを、次に、入力ルータ１３に送信するかを決定する。
【００４８】
１つの特定の出力ポート３０の出力待ち行列１８の全体がいっぱいになった場合、すなわち、この出力ポート３０に対するすべての出力待ち行列１８の充填度に関するあるしきい値を超えている場合、入力バッファ１１に信号を送る役割をするフィードバック機構が構成される。したがって、ＯＱＣＴとも呼ばれる出力待ち行列しきい値比較器２２が構成され、これが、単一出力ポート３０に属する出力待ち行列１８の全体の充填度を収集する。累積充填度が、特定の出力ポート３０に向けられた、スイッチング構成内のすべてのデータ・パケットの数に対する正しい測定値である。この累積数値が、したがって、１つまたは複数の所定しきい値に対して測定されることになり、これが、出力待ち行列しきい値コレクタ２２内で行われる。そのしきい値を超えている場合、前述の信号が生成されて、入力コントローラ２５に転送される。
【００４９】
この信号を受けると、各入力コントローラ２５は、この出力ポート３０に向かうデータ・パケットが、もはや、入力バッファ１１から送信されない、すなわち、占有された出力待ち行列１８に対する、入力待ち行列１２からのデータ・パケットが制止され、他方、その他の入力待ち行列１２は、データ・パケットを送信し続けることができるということで、反応することができる。
【００５０】
バックプレッシャ・スキームは、出力待ち行列１８がまださらなるエントリを受け取ることができるかどうかを信号で合図することによっても、置き換えることができる。
【００５１】
さらなる改良が、入力コントローラ２５に出力待ち行列１８のすべての充填度についてのより詳細な情報を与える信号を、入力コントローラ２５にフィードバックすることによって、実現することができる。任意の時点で、どの出力ポート３０でも、後続段階に送達するデータ・パケットを有することが目標であるので、下記に出力待ち行列１８のセットと呼ぶ、１つの共通出力ポート３０に属する出力待ち行列１８の全体が、空である、またはほとんど空であるという情報を入力コントローラ２５に送ることができ、また、好ましくは、それぞれの出力ポート３０に向かうデータ・パケットを入力ルータ１３に送信するのに、この情報を使用することができる。出力待ち行列１８のこの状況情報は、例えば、１つまたはいくつかの追加のしきい値、例えば、０または０に近い充填度でのしきい値を導入することによって導出することができる。これにより、空の、またはほとんど空のセットの出力待ち行列１８が、入力コントローラ２５に報告されることになり、コントローラは、次に、このセットの出力待ち行列１８が、できる限り早くデータ・パケットを受信するようにそのポリシーを採択することになる。いくつかのそうしたしきい値を導入することが、入力コントローラ２５へのきめの細かい状況報告を可能にし、コントローラは、セットの出力待ち行列１８のそれぞれに対してこの状況報告を使用し、それに応じて、そのデータ・パケット多重化ポリシーに影響を与え得る。したがって、この状況報告は、バックプレッシャの逆のようなもの、つまり低ロード警報またはロード最大化スケジューリング・フィードバック信号として機能する。
【００５２】
バックプレッシャ信号は、この場合、入力バッファ１１に選択的に伝搬することが可能である。つまり、１つの特定の出力ポート３０に対する出力待ち行列１８から発信するバックプレッシャ信号を、入力バッファ１１内の対応する入力待ち行列１２のみに、また複数優先順位の場合は、複数の入力待ち行列１２のみに誘導される。したがって、他のすべての入力待ち行列１２は、このバックプレッシャによってブロックされず、そのデータ・パケットを出力バッファ３５に送信し続けることができる。
【００５３】
入力バッファ１１は、入力バッファ１１とスイッチング装置１０の間での接続回線の数がより少ないため、より容易にスイッチング装置１０から物理的に分離することができるので、より安価なメモリ・チップを使用して実現することができ、したがって、それらのバッファ・サイズは、実際には、同一価格での出力バッファ３５の場合に可能なよりも、ずっと大きく選択することができる。したがって、このスキームを使用すると、有限の入力バッファ１１が、理論的に無限の入力バッファに対するよりよい近似を示す。
【００５４】
データ・パケットの正しい処理を実現するため、データ・パケットに対するフロー制御機構が、やはり出力バッファ３５のために追加されて、これが、図示していない出力バッファ・バックプレッシャ生成器によって実行され、この生成器は、出力バッファ３５からその入力バッファ１１に対して発信される信号を生成し、この信号が、入力バッファ１１に、出力バッファ３５が、もはや、着信データ・パケットをバッファに入れることができないことを合図し、これにより、入力バッファ１１が、その信号によっても誘発されたバックプレッシャが消失するまで、さらなるデータ・パケットを出力バッファ３５に送信しないようにする。バックプレッシャ信号は、出力バッファ３５内でバッファに入れられるデータ・パケットの量が、所定しきい値を超えたときに生成される。このしきい値は、入力バッファ１１内でバックプレッシャを発行させるのにバックプレッシャ信号が必要とする時間中に送信され得るデータ・パケットをバッファに入れることを可能にするため、出力バッファ３５の実際のサイズよりも低く設定される。共用の場合、１つのスイッチング・セクション１５内にあるすべての出力待ち行列１８の場所の数の合計は、出力バッファ３５内のアドレスの数よりも大きいので、どの出力待ち行列１８も、その中に格納されるデータ・パケットに関するそのしきい値に達していなくても、出力バッファ３５がいっぱいになることがあり得る。したがって、出力バッファ３５も、占有されたアドレスに関するしきい値を有し、これは、それが達せられたとき、入力バッファ１１に対するメモリ・フル・バックプレッシャ信号の生成を引き起こし、その場合、この入力バッファは、そのデータ・パケットを出力バッファ３５に入力ルータ１３を介して送信するのを停止しなければならない。占有されたアドレスの数が、しきい値より下に低下するとすぐに、通常の動作を再開することができる。出力バッファ３５に空間が無くなったときはいつでも、バックプレッシャを生成する機構が、各単一出力バッファ３５ごとに、別々に設けられる。
【００５５】
この構成は、すべての入力バッファ１１が、そのデータ・パケットを独立に、その入力ルータ１３を介して、このデータ・パケットのための出力待ち行列１８および共通出力バッファ３５が、そのために、まだ十分な空間を保持しているとき、すなわち、バックプレッシャ信号が生成されていないときはいつでも、送信することを可能にする。
【００５６】
仮想出力待ち行列化を備えた入力バッファ１１は、この場合、本明細書に図示しない、共用あり、または共用無しの追加の共通入力バッファを使用して実現することもできる。これは、着信するデータ・パケットを共通入力バッファ内に格納することができ、他方、その中のそのアドレスは、これらのデータ・パケットがそこに向かう出力ポート３０に応じて配列して、入力待ち行列１２内に格納することができる。したがって、これらのアドレスは、入力待ち行列１２に入力されたデータ・パケットに関するエントリを表す。マルチキャスト・データ・パケットの場合、共通入力バッファ内に１つのエントリだけを行う必要があり、これにより、マルチキャスト・データ・パケットがそこに向かう出力ポート３０に対応するすべての入力待ち行列１２内へのエントリが行われる。入力待ち行列１２内へのこのエントリは、マルチキャスト・データ・パケットまたはそのペイロードが、そこで共通入力バッファ内に格納されている場所に対するポインタである。これらのエントリは、したがって、マルチキャスト・データ・パケットに対しても同一であり、またペイロードは、一度だけ格納すればよいので、メモリ空間が節約される。ペイロードの共通バッファリングを実施するため、出力バッファ３５のための使用するのと同じ、本明細書には図示しない要素、すなわち、アドレス・マネージャ、およびペイロードをこの共通入力バッファに送達するための入力ルータを使用することができる。デマルチプレクサ１９が、入力待ち行列１２に幾分、似通った役割をし、出力待ち行列ルータ１７も、出力待ち行列１８に似通った役割をする。
【００５７】
入力バッファ１１は、通常、入力アダプタまたは単にアダプタとも呼ばれる、スイッチ・アダプタの形態で構成される。この提案する発明では、スイッチ構成ともよぶこの構成を、例えば、１６×１６、すなわち、１６個の入力ポート２０×１６個の出力ポート３０から３２×３２に拡張するのに、すべてのアダプタが、その待ち行列構造を変更するだけでよく、そのアダプタ上の入力バッファ１１を変更する必要はない。適切な予測により、これは、入力待ち行列１２の集合としてこの入力バッファ１１を管理するリンクリストの実際の数が、プログラム可能されるべきことを意味する。いずれにしても、この入力アダプタ上で、複雑さは、Ｎのオーダでスケールする、すなわち、宛先を２倍にすることは、入力待ち行列１２および出力待ち行列１８の数を２倍にすることを意味する。従来のＶＯＱ構成では、スイッチの入力ポート２０および出力ポート３０の数を２倍にすることは、要求の平方増加、すなわち、１６×１６の制御手段は、２５６個の要求を受信し、３２×３２の制御手段は、１０２４個の要求を意味する。
【００５８】
本発明の別の実施形態を図２に図示している。これは、アドレス・マネージャ１６、出力待ち行列１７、および出力待ち行列１８が、入力ポート２０の間で共用されていることで、前述の実施形態とは異なっている。これは、入力ポート２０が、それぞれ、それ自体の入力ルータ１３および出力バッファ３５を有する一方で、１セットの出力待ち行列１８だけが存在し、これが、単一アドレス・マネージャ１６によってフィードされ、また入力バッファ１１のそれぞれから入力を得ている共通出力待ち行列ルータを介して充填されることを意味する。出力待ち行列１８は、その充填度信号を入力コントローラ２５に送達し、そこで、出力待ち行列競合の場合、バックプレッシャ信号が生成される。この場合も、バックプレッシャは、前述の認可機構で置き換えることができる。ＯＱＣＴ２２は、この場合、もはや必要ない。というのは、異なる充填度の加算が必要ないからである。アドレス・マネージャ１６が、そのアドレスを各入力ルータ１３ごとに一度に１つずつ、すべての入力ルータ１３に送達する。もちろん、このアドレス・マネージャ１６は、すべての出力バッファ１５のアドレスを管理し、したがって、出力ルータ１４からフィードバックを得て、そのアドレスが再使用され得る。この場合、出力ルータは、アドレスについての情報をアドレス・マネージャ１６に与えるだけでなく、対応する出力ルータ３５の識別も与える。別法では、すべての出力バッファ３５のアドレス空間をまとめてセットアップして、どのアドレスも２度、出現しないようにすることができる。その場合、いくつかの重なり合うアドレス空間の管理が必要ない。アドレス・マネージャは、使用される次のアドレスをすべての入力ルータ１３に同時に送信することができ、各入力ルータ１３は、着信するアドレスが、その入力ルータ１３によって使用され得るアドレスであるか、まはたそのアドレスが、別の入力ルータ１３によって使用されるように決定されているかを認識する。また、この実施形態は、１セットの出力待ち行列１８を備えているここで述べた実施形態と、入力ポート２０のそれぞれに対して、そうしたセットの出力待ち行列１８を備えている最初に述べた実施形態との中間にある任意の構成を使用できることで、異なっている。したがって、２つまたはそれより多くの入力ポート２０が、１つのアドレス・マネージャ１６、出力待ち行列ルータ１７、および出力待ち行列１８を共用することができる。
【００５９】
スイッチング構成のパフォーマンスは、様々な方式で改善することができる。入力ポートおよび出力ポートの増加の場合、スイッチング構成は、多段階構成または単一段階構成で構成することができる。多段階構成では、必要なスイッチング構成の数は、それに比較し得る単一段階構成でよりも、ゆっくりと増加する。すなわち、ポートの数が増加するのにつれて、多段階構成は、単一段階構成よりも少ない数のスイッチング構成を必要とする。
【００６０】
ただし、多段階構成のパフォーマンスは、より遅い。これは、増大する待ち時間による、また他の宛先を有するデータ・パケットの処理を妨げる１つの接続による出力待ち行列の完全な使用、あるいはすべてのスイッチング構成の入力ポートをブロックして、前の段階に伝搬するパケット・メモリの完全な使用によるバックプレッシャの可能性のためである。このより低いパフォーマンスは、ある程度、加速ファクタによって補償され得る。これは、スイッチング構成が、その環境よりも高速で動作していることを意味する。したがって、出力バッファが、スイッチング装置の背後で、より高速の着信データ・パケットを待ち行列に入れるのに必要とされ、このパケットは、最終段階から発信されて、より遅い速度の後続のハードウェア環境に渡される。別の可能性は、スイッチ内部メモリを増やして、完全な使用が起こりにくくすることである。ただし、そうしたより大きなメモリは、極めて高価であり、また、ある程度、物理的にも制限される。メモリ拡張モードによってスイッチのメモリを増やすことは、物理的制限を回避するが、それでもやはり高価である。多段階構成で、後続のスイッチング構成が込合っている場合（出力メモリがいっぱい、すなわち、アドレスが入手できない、または出力待ち行列がいっぱいである）、すべての入力ポートに対してバックプレッシャ信号が生成される可能性があり、このバックプレッシャ信号が、やはり、すべての先行するスイッチング構成に転送される。いっぱいの出力待ち行列の場合、バックプレッシャは、このいっぱいの出力待ち行列に向かうデータ・パケットだけを選択的にブロックしている可能性がある。いっぱいの出力バッファの場合、すべての入力ポートが、ブロックされることになる。バックプレッシャ信号は、先行するスイッチング構成を、このスイッチング構成が、もはやセルを送信できないことでブロックする。
【００６１】
本明細書に提示したスイッチング構成は、既知の拡張方法のいずれを使用しても拡張することが容易であり、例えば、こうした方法は、背景技術を紹介した章で述べたＰＲＩＺＭＡアーキテクチャで知られている。したがって、速度拡張、ポート拡張、リンク並列、また最後に、それらの任意の組み合わせを適用することができる。記載した実施形態は、スイッチング速度と、短い待ち時間と、高いスループットと、複雑さの低い配線および回路構成とを組み合わせた適切なスイッチング装置を実現するために、その部分または全体を組み合せることができる。
【００６２】
請求項では、いくつかの出力バッファが、１セットの出力待ち行列１８、１つの出力待ち行列ルータ１７、および１つのアドレス・マネージャ１６を共用するケースを、各出力バッファ３５が、その独自セットの出力待ち行列１８と、出力待ち行列ルータ１７と、アドレス・マネージャ１６とを有するケースから区別しており、これは、その両方の形態、すなわち、出力バッファ３５の単一ケースと複数ケースを提示することによって行っている。
【００６３】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００６４】
（１）データ・パケット宛先情報とペイロードとを含むデータ・パケットをトランスポートするためのスイッチング構成であって、前記データ・パケットが、スイッチング装置（１０）の１つまたは複数の入力ポート（２０）を介して、その１つまたは複数の出力ポート（３０）に向かい、前記スイッチング装置（１０）が、前記着信データ・パケットを前記データ・パケット宛先情報に応じて、前記出力ポート（３０）のうちの少なくとも１つの専用の出力ポートに経路指定することができ、これにより、すべての入力ポート（２０）の全体が、入力ポート（２０）のサブセットに分割され、各サブセットが、少なくとも１つの前記入力ポート（２０）を含み、前記スイッチング構成が、
各入力ポート（２０）で、前記スイッチング構成の有している出力ポート（３０）と少なくとも同数の入力待ち行列（１２）を備えた入力バッファ（１１）であって、前記入力待ち行列（１２）が、前記着信データ・パケットをその専用の少なくとも１つの出力ポート（３０）に応じて分類する役割をする入力バッファ（１１）と、
各入力ポート（２０）ごとの入力コントローラ（２５）であって、前記入力待ち行列（１２）から前記スイッチング装置（１０）への前記データ・パケットの多重化の順序を制御する役割をする入力コントローラ（２５）と、
前記スイッチング装置（１０）内の前記入力ポート（２０）の各サブセットに対する、別々の出力バッファ（３５）であって、その中のアドレスで、前記入力ポート（２０）に着信する各前記データ・パケットの少なくとも前記ペイロードを格納するための出力バッファ（３５）と、
前記スイッチング構成の有している出力ポート（３０）と同数の少なくとも１セットの出力待ち行列（１８）であって、その中に、前記出力バッファ（３５）内に格納された各前記ペイロードの少なくとも前記アドレスを前記データ・パケット宛先情報に応じて分類して格納するための出力待ち行列（１８）とを含み、
これにより、前記格納されたペイロードが、前記格納されたアドレスの使用下にあるその専用の少なくとも１つの出力ポート（３０）に送達可能であるスイッチング構成。
（２）１つの共通出力ポート（３０）に属するすべての出力待ち行列（１８）の全体における占有された場所のしきい値を超えている場合、入力バッファ（１１）に信号を送るための出力待ち行列しきい値比較器（２２）が設けられることを特徴とする上記（１）に記載のスイッチング構成。
（３）１つの共通出力ポート（３０）に属するすべての出力待ち行列（１８）の全体における占有された場所のしきい値を超えているという、しきい値比較器（２２）からの信号があったとき、前記入力バッファ（１１）が、指定されて、前記共通出力ポート（３０）に対応する入力待ち行列（１２）だけが、そのデータ・パケットを前記共通出力ポート（３０）に送信しないようにすることを特徴とする上記（２）に記載のスイッチング構成。
（４）各出力バッファ（３５）ごとに、前記出力バッファ（３５）内の占有されたアドレスのしきい値を超えたことを、前記出力バッファ（３５）に対応する入力ポート（２０）のサブセットの入力バッファ（１１）に信号で知らせるために、出力バッファ・バックプレッシャ生成器が設けられることを特徴とする上記（１）ないし（３）のいずれか一項に記載のスイッチング構成。
（５）前記１つまたは複数の出力バッファ（３５）の前記アドレスの使用を管理するための少なくとも１つのアドレス・マネージャ（１６）と、前記データ・パケットが、そこで前記１つまたは複数の出力バッファ（３５）内に格納される前記アドレスを前記出力待ち行列（１８）に入力するための少なくとも１つの出力待ち行列ルータ（１７）とをさらに含む上記（１）ないし（４）のいずれか一項に記載のスイッチング構成。
（６）マルチキャスト・データ・パケットの場合、そのアドレスが、このマルチキャスト・データ・パケットが到達することになっている出力ポート（３０）に対する出力待ち行列（１８）のそれぞれにエントリとして入力可能であることを特徴とし、かつ前記アドレスが、前記マルチキャスト・データ・パケットのすべてのエントリが、前記マルチキャスト・データ・パケットをその指定された出力ポート（３０）に送達するのにうまく使用されたとき、別のデータ・パケットに対する使用のために、アドレス・マネージャ（１６）によってのみ解放可能であることを特徴とする上記（５）に記載のスイッチング構成。
（７）異なる処理優先順位を有するデータ・パケットの場合、優先順位の各クラスごと、および各出力ポートごとに、別々の入力待ち行列（１２）が、入力バッファ（１１）内に設けられることを特徴とする上記（１）ないし（６）のいずれか一項に記載のスイッチング構成。
（８）出力待ち行列（１８）が、全体で、対応する出力バッファ（３５）が、それぞれ有するアドレスの数よりも多くの、アドレスに対する待ち行列場所を提供することを特徴とする上記（１）ないし（７）のいずれか一項に記載のスイッチング構成。
（９）少なくとも前記ペイロードを前記出力バッファ（３５）から前記出力ポート（３０）に送達するために、すべての出力バッファ（３５）をすべての出力ポート（３０）と接続する共通出力ルータ（１４）を含む上記（１）ないし（８）のいずれか一項に記載のスイッチング構成。
（１０）前記着信するデータ・パケットのそれぞれについて、前記入力待ち行列（１２）のうちで前記対応するデータ・パケットの前記パケット宛先情報内で識別されるものにエントリを行うためのデマルチプレクサ（１９）を含み、これにより、各前記入力コントローラ（２５）が、前記入力待ち行列（１２）のうちの異なるものにそのエントリが配置され、かつ同一ペイロードを有するデータ・パケットの同時の伝送を可能にするように設計されている上記（１）ないし（９）のいずれか一項に記載のスイッチング構成。
（１１）各前記エントリが、対応するデータ・パケットの少なくともペイロードまたは対応するデータ・パケットの少なくとも前記ペイロードがそこに格納されているメモリ・セルに対するポインタを含み、前記メモリ・セルが、好ましくは、共通入力バッファ内に配置されていることを特徴とする上記（１０）に記載のスイッチング構成。
（１２）前記データ・パケットが、マルチキャスト・データ・パケットである場合、デマルチプレクサ（１９）が、前記入力待ち行列（１２）内にいくつかのエントリを行い、かつそのペイロードの１つのエントリのみを前記メモリ・セル内に行うように設計されていることを特徴とする上記（１１）に記載のスイッチング構成。
（１３）スイッチング装置（１０）の１つまたは複数の入力ポート（２０）を介して、その１つまたは複数の出力ポート（３０）に向かうデータ・パケットのためのスイッチング方法であって、すべての入力ポート（２０）の全体が、入力ポート（２０）のサブセットに分割され、各サブセットが、少なくとも１つの前記入力ポート（２０）を含み、
その専用の少なくとも１つの出力ポート（３０）に応じて前記データ・パケットを、各入力ポート（２０）で、入力バッファ（１１）の入力待ち行列（１２）内に格納するステップであって、前記バッファ（１１）が、前記スイッチング装置（１０）の有する出力ポート（３０）と少なくとも同数の入力待ち行列（１２）を有するステップと、
前記データ・パケットを前記入力待ち行列（１２）から前記スイッチング装置（１０）に対して多重化するステップと、
前記スイッチング装置（１０）内の前記入力ポート（２０）のサブセットごとに存在する別々の出力バッファ（３５）内のアドレスに、前記入力ポート（２０）に着信する各前記データ・パケットの少なくとも前記ペイロードを格納するステップと、
前記スイッチング装置（１０）内に少なくとも１度は存在する出力待ち行列（１８）内に、前記出力バッファ（３５）内に格納されている各前記ペイロードの少なくとも前記アドレスを、前記データ・パケット宛先情報に応じて分類して格納するステップと、
前記格納されたペイロードを前記格納されたアドレスの使用下にあるその専用の少なくとも１つの出力ポート（３０）に送達するステップとを含む方法。
（１４）１つの共通出力ポート（３０）に属するすべての出力待ち行列（１８）の全体における占有された場所のしきい値を超えている場合、入力バッファ（１１）に信号でそれを知らせるステップを含む上記（１３）に記載のスイッチング方法。
（１５）１つの共通出力ポート（３０）に属するすべての出力待ち行列（１８）の全体における占有された場所のしきい値を超えているという信号があったとき、前記入力バッファ（１１）内で、前記共通出力ポート（３０）に対応する入力待ち行列（１２）だけが、占有された場所の数が減少するまで、前記共通出力ポート（３０）にそのデータ・パケットを送達しないようにすることを特徴とする上記（１３）または（１４）に記載のスイッチング方法。
（１６）対応する出力バッファ（３５）内での占有されたアドレスのしきい値を超えたことを前記入力ポート（２０）のサブセットの入力バッファ（１１）に信号で知らせるステップを含む上記（１３）ないし（１５）のいずれか一項に記載のスイッチング構成。
【図面の簡単な説明】
【図１】入力ポートごとに別々の出力バッファを備え、かつ入力ポートごとに１セットの出力待ち行列を備えた入力バッファ付きスイッチング構成を示す図である。
【図２】入力ポートごとに別々の出力バッファを備え、かつ１セットのみの出力待ち行列を備えた入力バッファ付きスイッチング構成を示す図である。
【符号の説明】
１０  スイッチング装置
１１  入力バッファ
１２  入力待ち行列
１３  入力ルータ
１４  共通出力ルータ
１５  スイッチング・セクション
１６  アドレス・マネージャ
１７  出力待ち行列ルータ
１８  出力待ち行列
１９  デマルチプレクサ
２０  入力ポート
２１  マルチプレクサ
２５  入力コントローラ
３０  出力ポート
３５  出力バッファ
５０  通信回線
【図１】
0004006205.tif 000002
【図２】
0004006205.tif 000003