JPH10513334A - 切換方法及び装置 - Google Patents

Abstract

(57)【要約】 切換用装置を開示している。切換用装置は、パケットを切り換えるＬ個のスイッチングモジュールからなり、ここでＬ≧２の整数である。ある実施例では、Ｌ個のスイッチングモジュールは、それぞれ他のどのスイッチングモジュールとも無関係にパケットを切り換えるので、Ｌ個のスイッチングモジュールに沿ってパケットが分散的に切り換えられる。この装置はまた、Ｌ個のスイッチングモジュールのそれぞれに接続される相互接続モジュールからなる。相互接続モジュールは、Ｌ個のスイッチングモジュールの間に接続性を与える。ある実施例では、相互接続モジュールは、Ｌ個のスイッチングモジュールの間に空間・時間多重化接続性を与える。もう１つの実施例では、相互接続モジュールは、スイッチングモジュールの最終的な数を予め知らなくても拡大できる。更にもう１つの実施例では、Ｌ個のスイッチングモジュール間の接続性について、相互接続モジュールをプログラムし直すことが可能である。本発明は、切換装置を作成する方法に関するものである。その方法は、第１及び少なくとも第２のスイッチングモジュールを相互接続モジュールに接続させる過程からなる。次に、相互接続モジュールをプログラムして、第１及び第２のスイッチングモジュール間に相互接続モジュールへの所望の接続性を生み出す過程がある。次に、相互接続モジュール及び第１及び第２のスイッチングモジュールを通じてパケットを転送させる過程がある。次に、少なくとも１つの追加スイッチングモジュールを相互接続モジュールに接続させる過程がある。次に、相互接続モジュールをプログラムし直して、第１、第２及び第３のスイッチングモジュールの間に相互接続モジュールへの所望の接続性を発生させる過程がある。本発明は、パケットを導く方法に関するものである。

Description

【発明の詳細な説明】 切換方法及び装置発明の分野 本発明は、パケットを方向づけるためのスイッチ及び方法に関するものである 。より具体的には、本発明は、スイッチングモジュール間の接続性をプログラム し直すことができ、分散制御(distributed control)を行い、スイッチモジュー ルの最終的な数を予め知らなくても拡大できるスイッチに関するものである。発明の背景 例えばＷＷＷ（ワールドワイドウェブ）の如く、まもなく行われる応用のお陰 で、インターネットのトラフィックが増加し、多様化するにつれて、ＡＴＭスイ ッチ等のＡＴＭパケットスイッチへの需要の増加が予想される。現在の高性能パ ケットスイッチの標準型はＡＴＭである。ＡＴＭ市場では、近頃派手な宣伝が繰 り広げられている。しかし、この騒ぎが静まれば、顧客は、現在のＡＴＭ製品が いくつかの理由で不適当であることをはっきりと知るであろう。これらの製品は 、実用の点でもコストの点でも、真のモジュラリティ(modularity)や増設可能性 (scalability)がない。理想的なＡＴＭスイッチでは、顧客は初めに小型のスイ ッチを買い、必要に応じてサイズを拡大することができる。この際、以前の装置 が旧式にな ったり、後日の拡大を見越して大きな初期投資をする必要はない。本発明は、こ れらの顧客が今望んでいるもの、つまり、ネットワークの性能や制御の複雑さを 低下させることなく、経済的な方法で拡大できるようなスイッチを提供する、新 規なパケットスイッチアーキテクチャーである。 高帯域幅の接続部を、ローカルエリアネットワークからより大きなネットワー クへ移行すると、ＡＴＭ（非同期転送モード）スイッチのサイズの条件は増加さ れる。現在市販されているＡＴＭスイッチ製品の増設可能性は限られている。そ れは、一般的には、共用バッファメモリに必要なアクセス率が高く、スイッチ要 素相互間の相互接続部が複雑なためである。 既存のＡＴＭスイッチアーキテクチャは、複数のポートを時間多重化(time-mu ltiplexed)バスによって相互接続させることにより、スイッチのサイズを大きく するものである。従って、これらのスイッチにおけるポートの数は、中枢バスの 帯域幅によって制限されている。更に、スイッチコントローラの速度は、スイッ チのサイズが大きくなるに従って早くなる。増設可能性が限られているだけでな く、スイッチをモジュール方式で対応することは、一般的には困難である。例え ば、ある顧客が将来１２８ポートのＡＴＭスイッチへ展開する予定であれば、１ ２８ポート付きスイッチフレーム及び中枢バスを購入 する必要があり、必要に応じてＩ／Ｏカードを追加購入する必要がある。従って 、顧客に初めにかかるコストは非常に高く、最終スイッチのサイズは、スイッチ を展開する初期段階で決まってしまう。既存のＡＴＭスイッチ製品は、現時点の 小型スイッチから大型スイッチへ発展するための明確な方針を提供していない。 顧客は、初期投資を無駄にするか、又は事前に計画を立て、最初に大きな投資を 行わなければならない。それでも、現在のＡＴＭスイッチ製品は、そのスイッチ の最大サイズに達した後は、増設可能性を与えない。 ここに提案するスイッチには、いくつかの利点がある。まず第１に、提案のス イッチは、真に増設可能であり、モジュール化できる。顧客は、最低１６ポート 付きの安価なスイッチから始めて、既に投資した部分に大きな修正を加えること なく、最大２０４８ポート付きのスイッチにまで拡大することができる。より大 きいスイッチに拡大するためのコストは直線比例的で、スイッチは最初に投資の 大部分を行う必要はない。スイッチアーキテクチャは、多重スイッチングモジュ ールにより構成され、これらのモジュールは、単純で低コストの空間・時間多重 化(space and time-multiplexed)バックプレーンにより相互に接続される。スイ ッチの主なコストは、スイッチングモジュールにかかり、低コストのバックプレ ーンは、スイッチのサイズが大きくなるに従って、自動的に 再構成される。スイッチのサイズは、最終サイズについて予め知らなくても追加 のスイッチングモジュールを既存のモジュールに単に附加することにより、拡大 することができる。スイッチングモジュールは、次に、低コストのプログラマブ ルな中枢であるＩＭ（相互接続モジュール）を介して、互いに接続される。低コ ストのＩＭは、能動成分を含まず、受動成分により構成される。ＩＭは、所望の スイッチサイズのために低コストで取り換えられたり、大きめのＩＭが初めにイ ンストールされておれば、追加のスイッチングモジュールにプログラムし直すこ とができる。このように、最終のサイズをどうすべきかを初めに決定せずに、ス イッチのサイズを拡大することができる。 本発明のスイッチのもう１つの主な利点は、効率よく異種トラフィックを処理 する強力な作業性及び能力である。スイッチに用いられる待ち行列の法則は、部 分共用バッフアリング(partially shared buffering)である。スイッチは、メモ リ空間全体のサブセットを共用し、同時に、異種トラフィックシナリオにおける 全てのユーザに公平なアクセスを保証する。既存の共用メモリスイッチは、メモ リを食う(hogging)問題があるため、重い負荷(load)のトラフィックを持つユー ザを優遇し、軽い負荷のトラフィックにはサービスの質を低下させることが判明 している。従って、既存の共用メモリスイッチでは、 交通渋滞及び不公平なアクセスを避けるために、複雑な制御構造を必要とする。 本発明のスイッチのもう１つの重要な利点は、その分散制御にある。スイッチは 分散制御を行い、スイッチのサイズが大きくなっても制御の複雑さは増加しない 。既存のスイッチでは、集中制御器が、入力ポートから出力ポートにパケットを スイッチする。更に、より多くのポートを設けるためには、プロセッサ及びメモ リの速度が一層早くなければならない。本発明のスイッチアーキテクチャでは、 各スイッチングモジュールは、いかに多くのスイッチングモジュールが存在して いても、他のスイッチングモジュールの状態とは無関係に作動する。各スイッチ ングモジュールは、入力パケットを、その目的地アドレスを用いて処理する。従 って、スイッチングモジュールは、それ自身の一定数の入力ポートによって決ま るパケットに対処するだけでよい。各スイッチングモジュールにおける制御プロ セッサ及びメモリの速度は、スイッチのサイズが大きくなっても増加しない。分 散制御は、プロセッサ及びメモリの速度が制限されているため、どんな増設可能 アーキテクチャにとっても大きな利点となる。更に、低速の部品で製られる分散 制御スイッチを実行するためのコストは、高速の部品で製られる集中制御のコス トよりもずっと低い。 ここに提案するスイッチアーキテクチャは、多重スイッチングモジュールから なり、それらは、単純で低コス トの空間・時間多重化バックプレーンによって相互に接続されている。スイッチ の主なコストは、スイッチングモジュールによって占められる。低コストのバッ クプレーンは、スイッチのサイズが大きくなるに従って、自動的に再構成される 。各スイッチングモジュールは内部バッファを含み、それは、他のスイッチング モジュール間で共用される。このスイッチアーキテクチャは、一組の空間・時分 割多重化(division multiplexing)を通じて、異なるスイッチングモジュール間 に接続可能性を付与する。これらのスイッチングモジュールを通じて、セルをイ ンテリジェントルーティングすると、ランダムトラフィックの下、より高価な出 力待ち行列スイッチに匹敵する高いスループットが得られ、作業の遅延を減らす ことができる。満杯(bursty)であって、しかも一定でないトラフィックの下では 、スイッチは自動的に再構成し、複雑なバッファ制御機構を用いずに、既存のス イッチアーキテクチャに内在する作業能率の低下を、バッファを操縦することに よって、避ける。更に、マルティキャスト(multicast)なトラフィックが容易に 達成され、ルーティングが効率的に行われ、スイッチを最大限に利用することが できる。 本発明のスイッチアーキテクチャを考察するもう１つの方法は、時分割切換と 空間分割切換とを共に用いて、増設可能性を提供することである。スイッチング モジュ ールは、多重中枢バスを通じて構成され、様々に相互接続されて、所望の性能を 得る。スイッチングモジュールを対称に相互接続することによって、ホップの遅 延をできるだけ減らすことが出来、平衡したトラフィックを得るようにしてもよ い。これが、後述するモジュロＴデザインである。しかし、これらのスイッチン グモジュールを、異なるトラフィック条件を利用できるような構成にしてもよい 。顧客−サーバ間のトラフィックシナリオでは、酷使されたスイッチングモジュ ール間で、より多くの帯幅を割り当てることができる。従って、構成は結果的に 非対称になる。中枢の相互接続はプログラマブルなので、スイッチは、同じハー ドウェア要素を用いながら、異なるトラフィックパターンに適合して、必要な作 業を行うことができる。発明の要旨 切換用装置が開示されている。切換用装置は、パケットを切り換えるＬ個のス イッチングモジュールからなり、ここでＬ≧２の整数である。ある実施例では、 Ｌ個のスイッチングモジュールが、それぞれ他のどのスイッチングモジュールと も無関係にパケットを切り換えるので、Ｌ個のスイッチングモジュールを横切っ てパケットの切換えが分散する。 この装置はまた、Ｌ個のスイッチングモジュールのそれぞれに接続された相互 接続モジュールからなる。相互 接続モジュールは、Ｌ個のスイッチングモジュールの間に接続性を与える。ある 実施例では、相互接続モジュールは、Ｌ個のスイッチングモジュールの間に空間 ・時間多重化接続性を与える。もう１つの実施例では、相互接続モジュールは、 スイッチングモジュールの最終的な数について予め知らなくても、拡大できる。 更にもう１つの実施例では、Ｌ個のスイッチングモジュール間の接続性について 、相互接続モジュールをプログラムし直すことが可能である。 本発明は、切換装置を作成する方法に関するものである。その方法は、第１及 び少なくとも第２のスイッチングモジュールを相互接続モジュールに接続させる 過程からなる。次に、相互接続モジュールをプログラムして、第１及び第２のス イッチングモジュール間に相互接続モジュールへの所望の接続性を生み出す過程 がある。次に、相互接続モジュール及び第１及び第２のスイッチングモジュール を通じてパケットを転送させる過程がある。次に、少なくとも１つの追加スイッ チングモジュールを相互接続モジュールに接続させる過程がある。次に、相互接 続モジュールをプログラムし直して、第１、第２及び第３のスイッチングモジュ ールの間に相互接続モジュールへの所望の接続性を発生させる過程がある。 本発明は、パケットを導く方法に関するものである。図面の簡単な説明 添付の図面には、本発明の望ましい実施例及び本発明を実施するための望まし い方法が説明されている。 図１は、従来のバスに基づくアーキテクチャの概略図である。 図２は、本発明のアーキテクチャの概略図である。 図３は、スイッチングモジュールの概略図である。 図４は、スイッチングモジュール内通信の概略図である。 図５は、スイッチングモジュール間通信の概略図である。 図６は、２進相互接続の構成(scheme)を示す概略図である。 図７は、２進ルーティングの一例を示す概略図である。 図８は、パケットオーバーヘッドフォーマットの概略図である。 図９は、マルティキャスト仮想回線の準備段階の概略図である。 図１０は、マルティキャストルーティングの一例を示す概略図である。 図１１は、Ｔ＝３の時の、２７×２７のスイッチの構成を示す概略図である。 図１２は、１６×１６、６４×６４、２５６×２５６及び１０２４×１０２４ について、一定のトラフィックで、１ポート当たり１０バッファを用いた時の、 遅延と スループットとの関係を示す性能グラフである。 図１３は、１６×１６、６４×６４、２５６×２５６及び１０２４×１０２４ について、一定のトラフィックで、１ポート当たり１０バッファを用いた時の、 セル損失確率と加えられた負荷との関係を示す性能グラフである。 図１４は、１６×１６、６４×６４、２５６×２５６及び１０２４×１０２４ について、満杯状態のトラフィック（バーストの長さ＝８）で、２００バッファ を用いた時の、セル損失確率と加えられた負荷との関係を示す性能グラフである 。 図１５は、１６×１６、６４×６４、２５６×２５６及び１０２４×１０２４ について、満杯状態のトラフィック（バーストの長さ＝２０）で、２００バッフ ァを用いた時の、セル損失確率と加えられた負荷との関係を示す性能グラフであ る。 図１６は、スイッチ全体の概略図である。 図１７は、パケットフォーマットの概略図である。 図１８は、パケットフォーマットとスイッチオーバーヘッドの概略図である。 図１９は、構成し直された適応可能なスイッチを示す概略図である。 図２０は、ＦＰＧＡの構成を示す概略図である。 図２１は、８×８のスイッチをプログラマブルなＩＭ を用いて実施した概略図である。 図２２ａ及び図２２ｂは、プログラマブルな相互接続モジュールを用いて、８ ×８スイッチを１６×１６スイッチへスケーリングした概略図である。 図２３は、公平なアクセスの一例を示す概略図である。 図２４は、全体的な切換システムの概略図である。 図２５は、バスを基本とするスイッチアーキテクチャに基づくスイッチングモ ジュールの概略図である。 図２６は、共有メモリスイッチアーキテクチャに基づくスイッチングモジュー ルの概略図である。好適な実施例の説明 図面を参照すると、同様の符号は、いくつかの図面に亘って類似又は同一の部 分を示している。図２を特に参照すると、切換用装置(10)が示されている。この 切換用装置(10)は、パケットを切り換えるＬ個のスイッチングモジュール(12)か らなる。ここで、Ｌ≧２の整数である。ある実施例では、Ｌ個のスイッチングモ ジュール(12)は、それぞれ他の全てのスイッチングモジュールと無関係にパケッ トを切り換えるので、Ｌ個のスイッチングモジュール(12)を横切ってパケットの 切換えが分散している。即ち、各スイッチングモジュールは、他のどのスイッチ ングモジュールの動作とも無関係に、それが受け取ったパケットについて作動す る。 装置(10)はまた、Ｌ個のスイッチングモジュール(12) のそれぞれに接続される相互接続モジュール(14)からなる。相互接続モジュール (14)は、Ｌ個のスイッチングモジュール(12)の間に接続性を与える。１つの実施 例において、相互接続モジュール(14)は、Ｌ個のスイッチングモジュール(12)の 間に空間・時間多重化接続性を与える。もう１つの実施例では、相互接続モジュ ール(14)は、スイッチングモジュール(12)の最終的な数について予め知ることな しに拡大可能である。更にもう１つの実施例では、相互接続モジュール(14)は、 Ｌ個のスイッチングモジュールの間の接続性をプログラムし直すことができる。 相互接続モジュール(14)は、増設可能であることが望ましい。各スイッチング モジュール(12)は、ユーザと接続するためのｍ個のＩ／Ｏポート(15)（ｍ≧２の 整数、各Ｉ／Ｏポート(15)の速度は一定）及び相互接続モジュール(14)と接続す るためのＴ個の相互接続モジュールアクセスポート(16)（Ｔ≧２の整数）を有し ていることが望ましい。 図４を参照すると、各スイッチングモジュール(12)はまた、バッファメモリを 有していることが望ましい。バッファメモリは、入力バッファ(18)メモリ及び出 力バッファ(20)メモリにより構成されることが望ましく、それらはＩ／Ｏポート (15)及び相互接続モジュールアクセスポート(16)に接続する相互接続モジュール アクセスポートバッファメモリ(22)に接続されている。相互接続モジ ュールアクセスボート(16)は、一定の速度Ｓで作動するのが望ましく、ここでＳ ≧各Ｉ／Ｏポート(15)の速度である。各スイッチングモジュール(12)は、公平な 待ち行列(fair queue)を含んでいることが望ましい。 相互接続モジュール(14)は、パケットを所望のＩ／Ｏポート(15)に最大ｌｏｇ_T Ｎ回のホップで到達させることが望ましい。相互接続モジュールアクセスポー ト(16)の数は、パケットがスイッチングモジュール(12)及び相互接続モジュール (14)により所望の行先へルーティングされる方法に対応していることが望ましい 。スイッチングモジュール(12)及び相互接続モジュール(14)は、モジュロＴで作 動することが望ましい。各スイッチングモジュール(12)及び相互接続モジュール (14)は、パケットをマルティキャストできるのが望ましい。 図１６に示すように、装置(10)は、同期をとって入力パケットのエラーをチェ ックするＩ／Ｏパケットプロセッサ(30)を含んでいるのが望ましい。Ｉ／Ｏパケ ットプロセッサ(30)は、各スイッチングモジュール(12)に接続されている。装置 (10)はまた、パケットが所望の行先に到達できるように、少なくとも１つのスイ ッチングモジュール(12)内に接続性を設定するようなスイッチコントローラ(32) を含んでいることが望ましい。 各スイッチングモジュール(12)は、該スイッチングモジュール(12)において接 続性が適正に設定されるように、 パケットの行先アドレスが復号されるような論理チャネル翻訳を行うルーティン グテーブル(34)を有していることが望ましい。更に、各スイッチングモジュール (12)は、パケットを緩衝するためのパケットメモリ(36)を有していることが望ま しい。 本発明は、切換装置(10)を作成する方法に関するものである。その方法は、第 １及び少なくとも第２のスイッチングモジュール(12)を相互接続モジュール(14) に接続させる過程からなる。次に、相互接続モジュール(14)をプログラムして、 第１及び第２のスイッチングモジュール(12)間に相互接続モジュールへの所望の 接続性を発生させる過程がある。次に、相互接続モジュール(14)及び第１・第２ のスイッチングモジュール(12)を通じて、パケットを転送させる過程がある。次 に、少なくとも１つの追加スイッチングモジュール(12)を相互接続モジュール(1 4)に接続させる過程がある。次に、相互接続モジュール(14)をプログラムし直し て、第１、第２及び第３のスイッチングモジュール(12)の間に相互接続モジュー ル(14)への所望の接続性を生み出す過程がある。 図７，図９及び図１０を例示の目的で参照すると、本発明は、パケットを導く 方法に関するものである。その方法は、行先アドレスを持つパケットを増分させ 、カウンタビットを第１のスイッチングモジュール(12)に加える過程からなる。 次に、パケットの行先アドレスが、第 １のスイッチングモジュール(12)に存在するかどうかをチェックする過程がある 。次に、カウンタビットを読み取る過程がある。次に、行先アドレスのｉ番目の ビットを読み取る過程がある。ｉ番目のビットはカウンタビットに対応し、ここ でＩ≧１の整数である。次に、スイッチングモジュール(12)のポートからパケッ トを送り出す過程があり、該スイッチングモジュール(12)の値は、ｉ番目のビッ トの値に対応する。次に、相互接続モジュール(14)を通じて、パケットを第２の スイッチングモジュール(12)に転送する過程がある。次に、カウンタビットを１ つ増分させる過程がある。次に、行先アドレスを見つかるまで探索する過程があ る。 本発明は、パケットを導く方法に関するものである。その方法は、アドレスビ ット、カウンタビット及び決定コードにより定義される複数の行先アドレスを持 つパケットを、第１のスイッチングモジュール(12)に入力する過程からなる。次 に、パケットの行先アドレスの何れかが第１のスイッチングモジュール(12)に存 在するかどうかをチェックする過程がある。次に、カウンタビットを読み取る過 程がある。次に、行先アドレスのｉ番目のビットを読み取る過程がある。ｉ番目 のビットはカウンタビットに対応し、ここでＩ≧１の整数である。次に、セルの 決定コードを行先アドレスビットのｉ番目のビットに対応するように設定する過 程がある。次に、スイッチ ングモジュール(12)の各ポートからパケットを送り出す過程があり、該スイッチ ングモジュール(12)の値は、決定コードに対応する。次に、相互接続モジュール (14)を通じて、パケットを第２のスイッチングモジュール(12)に転送する過程が ある。次に、カウンタビットを１つ増分させる過程がある。次に、パケットの行 先アドレスの何れかが第２のスイッチングモジュール(12)に存在するかどうかを チェックする過程がある。次に、カウンタビットを読み取る過程がある。次に、 行先アドレスビットのｉ番目＋１のビットを読み取る過程がある。次に、セルの 決定コードを行先アドレスビットのｉ番目＋１のビットに対応するように設定す る過程がある。次に、行先アドレスを見つかるまで探索する過程がある。 本発明の実施に関して、ＡＴＭを必要とする従来のバスに基づくスイッチアー キテクチャは、図１に示すように、時間多重化中枢バスを通じてスイッチ要素を 相互接続する。セルの読み取り又はセルへの書き込みを行うためにポートがバス にアクセスしている際は、バス全体がその特定ポートの専用になり、その他のポ ートは順番を待つ。このように、各ポートは周期的にバスにアクセスし、セルを 切換して、それぞれの適切な行先ポートへ向ける。バスの帯幅は、各入力ポート の速度のＮ倍でなければならない。装置(10)は、バスに基づくアーキテクチャと は異なり、空間・時間多重化スキームに基づくイン テリジェント相互接続モジュール(14)を用いる。装置(10)の主な要素は、インテ リジェント相互接続モジュール(14)及び分散制御アルゴリズムである。更に、相 互接続モジュール(14)は、ポート(16)の数及び所望の性能に従って、自動的に再 構成する。 図２は、装置(10)の全体的なアーキテクチャを示している。任意の大きさのス イッチングモジュール(12)は、再構成可能な相互接続モジュールによって相互接 続されている。同じスイッチングモジュール内のポート間での接続を望む場合、 入力パケットは、スイッチングモジュール内で局所的に切り換えられる。入力パ ケットの行先が他のスイッチングモジュール内のポートならば、入力パケットは 、ルーティングアルゴリズムによる相互接続モジュールを通じて、適当なスイッ チングモジュールに切り換えられる。セルがその行先に到達するためには、１又 は多数のホップが必要となるかもしれない。装置(10)は、行先に到達するのに必 要なホッブの数を減らすことができる分散ルーティングアルゴリズムにより制御 される。ホップの最大数は、装置(10)の大きさ及び構成によって決まる。ルーテ ィングアルゴリズムの詳しい説明を以下に行う。 スイッチングモジュール（ＳＭ）(12)は、入出力ポートを具えた任意のスイッ チアーキテクチャのものでもよい。スイッチングモジュールは、図３に示すよう に、ユ ーザと接続するためのＩ／Ｏポート及び相互接続モジュールアクセスポート（Ｉ ＭＡＰ）を有している。スイッチングモジュール内には３つの仮想バッファメモ リ、即ち、入力バッファ(18)、出力バッファ(20)及びＩＭＡＰバッファ(22)があ る。 局所通信（即ちスイッチングモジュール(12)内の接続部）のため、入力セルは 、入出力バッファ(20)を通じてＩ／ＯポートからＩ／Ｏポートへ切り換えられる 。十分な数の利用可能な出力ポートがあれば、パケットはバッファをバイパスし 、瞬時に切換(switch out)される。しかし、同じＩ／Ｏポートを行先とする多数 のパケットがあれば、余分なパケットは出力バッファ(20)に保存され、後の周期 で切り換えられる。 ＳＭ(12)間の通信のために、入力セルはＩ／ＯポートからＩＭＡＰに切り換え られ、相互接続モジュールを通じて他のスイッチングモジュールに到達する。Ｓ Ｍ(12)間ルーティングのためのアルゴリズムを以下に説明する。図４及び図５は 、それぞれＳＭ(12)内通信及びＳＭ(12)間通信のオペレーションを示している。 ｍは、ＩＭＡＰの数又は各リンクが入力ポートとして同じ帯幅を持つと仮定した ときの、ＩＭＡＰの集合体帯幅とする。ｍは、ＩＭＡＰのスループット及びスイ ッチ全体の性能を決定する。ＩＭＡＰの帯幅は、様々な要領で実行できる。入力 ポートとして、正確にｍ個のリンクを同じ速度で実行 してもよく、或いはｋ個のリンクを入力ポートの速度のｍ／ｋ倍で実行させても よい。このように、相互接続モジュールは、スイッチングモジュールのための混 成(hybrid)空間・時間多重化相互接続モジュールを提供することができる。 相互接続モジュールは、スイッチングモジュールのための受動バックプレーン を提供する。これは、Ｉ／Ｏ集中ＦＰＧＡにより容易に実行できる。相互接続モ ジュールに必要なロジック又は遅延の条件はなく、ピンの接続性だけが必要とさ れる。このように、相互接続モジュールは、単に、スイッチの大きさが変わると 再構成するプログラマブルな１個のチップを用いることで実行できる。再構成ア ルゴリズムは、以下に述べるルーティングアルゴリズムに従って実行される。 ルーティングアルゴリズムは、スイッチングモジュール間で分散される。アル ゴリズムの複雑さは、スイッチの大きさに拘わらず一定であり、増設可能なスイ ッチアーキテクチャが可能になる。ルーティングアルゴリズムは、ホップの数を 最小限にし、ネットワーク内の渋滞が避けられる。まず、２進ルーティングアル ゴリズムについての考察を行い、それは更に一般化できる。各スイッチングモジ ュールは、２つの入力ポート、２つの出力ポート及び２つのＩＭＡＰポートを有 すると仮定する。スイッチングモジュールは、図２に示すパターンで相互接 続される。その特定のパターンは、入力セルが最大ｌｏｇ₂Ｎ回のホップで行先 ポートへ導かれるようにしている。ここでＮは、Ｉ／Ｏポートの総数である。 装置(10)のユニキャストなルーティングオペレーションは、以下の通りである 。各入力パケットは、ｌｏｇ₂Ｎビットである行先ポートアドレスを持つ(即ち、 Ｎ＝８のときのｄ１、ｄ２、ｄ３)。パケットはまた、１に初期化されるホップ カウンタｉ_hをもつ。各スイッチングモジュールは、パケットの行先アドレスが そのＩ／Ｏポートのどちらかと整合するかどうかを、まずチェックする。行先ア ドレスがＩ／Ｏポートと整合すれば、スイッチングモジュールは、パケットを適 当なＩ／Ｏポートへ送り出すか、又は、そのＩ／Ｏポートが使用中であれば、パ ケットを出力バッファ(20)に保存する。行先アドレスがそのＩ／Ｏポートのどち らとも整合しなければ、それは行先アドレスのｉ_h番目のビットをチェックし、 ｉ_h番目のビットがそれぞれ“Ｏ”又は“１”であれば、パケットをＩＭＡＰポ ートの“Ｏ”又はＩＭＡＰポートの“１”に切り換える。図７は、２進ルーティ ングアルゴリズムを示している。入力ポート“Ｏ”(000)にある出力ポート“５ ”(101)を行先とするパケット及び入力ポート“７”(111)にある出力ポート“６ ”を行先とするパケットがあると仮定する。第１のサイクルでは、パケットの行 先アドレスは出力ポート“６”と整合するので、入力ポー ト“７”は、パケット(110)を出力ポート“６”(110)に切り換える。このように 、パケット(110)は、ＩＭＡＰポートを通らずに、第１のサイクルで切り換えら れる。第１のビットは“１”（ｉ_h＝１）なので、入力ポート“Ｏ”は、パケッ ト(101)をＩＭＡＰポートの“１”に送る。スイッチングモジュールはまた、ホ ップカウンタを１つ増分させる（ｉ_h＝２）。第２のサイクルでは、行先アドレ スのｉ_h番目のビット（ｉ_h＝２）は“Ｏ”なので、第２のスイッチングモジュー ルはＩＭＡＰの“Ｏ”に切り換え、パケットは第３のスイッチングモジュールに 達する。第３のサイクルでは、パケットの行先アドレスは出力ポート“５”と整 合するので、パケットは最終的に出力ポート“５”に切り換えられる。 各パケットが行先ポートに到達するのに要するホップの最大数がｌｏｇ₂Ｎ（ 例ではｌｏｇ₂８＝３）であることは、容易に証明される。しかし、パケットが その行先ポートへ到達するのに要するホップ数は、ホップの最大数よりも通常は ずっと少ない。多数のパケットが、同じ出力ポート又は同じＩＭＡＰポートに同 時にアクセスしようとする可能性がある。ポートのコンテンションによる性能の 低下を避けるには、より高いクロック速度又はより広いデータ経路を用いること により、ＩＭＡＰポートの速度を僅かに早める必要がある。後述するように、増 速因子Ｎを要する出力待ち配列スイッチの性能に到達 するのに必要なのは、速度を小さな定数ずつ増速させることだけである。このよ うに、スイッチの速度はＮと共に増えないので、所望の性能を提供することがで きる。同じパケットの流れに属するセルは、スイッチの初めから終わりまで同じ 経路を通るので、パケットの順番は、スイッチ内で維持される。 スイッチ内のセルのマルティキャストルーティングは、ユニキャストルーティ ングアルゴリズムを単純に延長したものである。ヘッダーのルーティング情報は 、パケットがマルティキャストパケットかユニキャストパケットのどちらである かを示しているビットを必要とする。マルティキャストビットが設定されると、 図８に示すように、以下のフィールドがマルティキャスト識別子として用いられ る。マルティキャストビットが“０”であれば、上記のユニキャストルーティン グスキームに従って、ユニキャストアドレスビットが用いられる。マルティキャ ストビットが“１”であれば、テーブルルックアップメモリから得られる制御情 報に従って、スイッチングモジュールがマルティキャストルーティングアルゴリ ズムに続く。仮想回線が設定されている時、各スイッチングモジュールのメモリ への入口は、適正な出力ポートを示すように作られている。例えば、メモリ内の 入口は、ある特定の仮想回線への入力パケットが、出力ポート及びある特定のＩ ＭＡＰポートに同時に切り換えられなければ ならないことを示すことができる。２進ルーティングアルゴリズムの場合には、 どちらかへ延びる木(binary spanning tree)を設定することにより、どんなマル ティキャストルーティングでも実行できる。各スイッチングモジュールは、マル ティキャスト識別子を２ビットの決定コードに写像することができる。決定コー ド“０１”は、パケットがＩＭＡＰポートの“１”に切り換えられるべきである ことを示している。“１０”は、パケットがＩＭＡＰポート“０”に切り換えら れるべきであることを示している。“１１”は、パケットが両ＩＭＡＰポートに 切り換えられるべきであることを示している。 図９は、ルックアップテーブルにおける入口の設定を示している。ポート“０ １０”、“０１１”及び“１０１”を行先とするパケットがあると仮定する。第 １のサイクルでは、スイッチングモジュールは、行先アドレスの第１のビットを チェックする。第１のビットが全て“１”又は全て“０”であれば、決定コード はそれぞれ“０１”又は“１０”に設定される。第１のビットが“１”及び“０ ”の両方を含んでいるなら、決定コードは“１１”に設定される。この例では、 第１のサイクルで、第１のモジュールは決定コードを“１１”に設定し、“０１ ０，０１１”がＩＭＡＰ“０”に送られ、“１０１”がＩＭＡＰ“１”に送られ る。第２のサイクルでは、第１のモジュールは行先アドレス“０１０，０１１” の第２の ビットをチェックする。どちらのビットも“１”であるため、決定コードは“０ １”に設定され、両パケットアドレスは、ＩＭＡＰ(1)に送られる。第２のスイ ッチングモジュールは、行先アドレス“１０１”の第２のビットをチェックする 。決定コードは、“１０”に設定され、スイッチングモジュールは、第２のビッ トが“０”であるため、“１０１”をＩＭＡＰ“０”に送る。第３のサイクルで は、パケットアドレス“０１０，０１１”は、スイッチングモジュールの出力ポ ートアドレスと整合し、決定コードは“００”に設定され、パケットが出力ポー トに送られることを示す。パケットアドレス“１０１”もまた、出力ポートアド レスと整合し、決定コードは“００”に設定され、パケットが出力ポートへ送ら れることを示す。マルティキャストルーティングパターンは、既に説明した単純 な分散制御アルゴリズムを用いて設定される。しかし、同じ経路を共有できるな ら、多数サイクルを単一のサイクルに結合することにより、より効率よくマルテ ィキャスティングできる方法がある。例えば、パケット“０１０，０１１”はま た、ＩＭＡＰ“１”を経由して、１つ後のサイクルでのみ、パケット“１０１” として、第２のスイッチングモジュールに導かれる。“０１０，０１１”パケッ トを遅延させる必要はなく、より効率よくマルティキャスティングするために、 このオペレーションを第１のサイクルで結合することができる。 この効率的なマルティキャスティングは、次の例で説明される。 異なる決定コードは、仮想回線設定段階で発見され、マルティキャスト接続パ ターンに従って、スイッチングモジュールに記憶される。図１０は、装置(10)に おけるマルティキャストルーティングの一例を示している。入力ポート“０”が 、行先アドレス“０１０”、“０１１”及び“１０１”を持つマルティキャスト パケットを有すると仮定する。第１のスイッチングモジュールにおける決定コー ドは、仮想回線設定段階で“０１”と設定され、パケットをＩＭＡＰポート(1) に切り換える。第２のサイクルでは、第２のスイッチングモジュールにおける決 定コードは“１０”であり、パケットはＩＭＡＰポート(0)及び両出力ポート“ ０１０”“０１１”に切り換えられる。第３のサイクルでは、パケットは出力ポ ート“１０１”に切り換えられ、パケットのマルティキャスティングは終了する 。決定コードをマルティキャスティングに用いることの利点は、トラフィックを 容易に且つ柔軟に管理できることである。追加のルックアップテーブルメモリに コストがかかる。しかし、マルティキャストルーティングのための追加メモリは 、既存のＡＴＭスイッチ製品でも同様に必要なものであった。装置(10)では、追 加メモリはハードウェアのコストを僅かに増加させるに過ぎない。何故なら、マ ルティキャスト決定ルーティ ングは、ＶＣ／ＶＰテーブルルックアッブメモリに組み込まれているからである 。このように、２、３の追加ビットのマルティキャスト情報が、スイッチングモ ジュール内に既に存在しているＶＣ／ＶＰルックアップメモリに追加される。 装置(10)で、マルティキャスティングを管理する他の方法がある。例えば、行 先ポートアドレスは、ヘッダーに記憶でき、状況に応じて切り換えるために各ス イッチングモジュールで復号できる。しかし、このスキームは、スイッチの大き さやマルティキャスト数が増加するに従って複雑になる。装置(10)は、必要に応 じて、他のどんなマルティキャストスキームでも採用できる程に柔軟なものであ る。 ここまでは、説明を簡略にするために、２進構成及び２進ルーティングアルゴ リズムを用いて、装置(10)の作動及びアーキテクチャについての説明を行ってき た。より多様な大きさのスイッチを収容するため、そして異なる質のサービスを 満足させるために、装置(10)を一般的なものにしてもよい。Ｎを装置(10)全体の ポートの数とする。Ｍを各スイッチングモジュールのユーザＩ／Ｏポートの数と する。そこで、Ｎ＝ΣＭとなる(Σは、ＳＭの総数について実行)。Ｔをスイッチ ングモジュールのＩＭＡＰポートの数とする。Ｓ個のスイッチングモジュールが あると仮定する。例えば、ＩＭＡＰであるｉは、最 小限のホップ対称構成(hop symmetric configuration)のため、ＩＭＡＰポート （ｋＳ≦ｉ≦（ｋ＋１）Ｓ−１に関するＴ×残り（ｉ／ｓ）＋ｋ。但し０≦ｋ≦ Ｔ）に接続される。 Ｔが２であれば、相互接続モジュールの構成は２進数であり、ルーティングは 、前の項目で説明された２進アルゴリズムに従って行われる。Ｔが３であれば、 スイッチングモジュールは３進スキームに従って相互接続され、ルーティングは ３進アルゴリズムによって制御される。図１１は、Ｔが３のときに２７のポート 付き装置(10)の構成を示している。 一般的なアーキテクチャのパケットのルーティングは、２進ルーティングアル ゴリズムのアーキテクチャに類似している。ルーティングの目的で、２進法の代 わりにモジュロＴ進法が用いられる。各ポートは、モジュロＴ進法によって番号 を付され、到着パケット(arriving packet)は、モジュロＴ行先ポートアドレス を持っている。第１のサイクルでは、スイッチングモジュールは行先ポートの第 １のビットをチェックし、その行先ビットと同じラベルを持つＩＭＡＰに切り換 える。モジュロＴアドレスを持つ分散ルーティングの概念は、上述した２進アル ゴリズムの概念と同じである。 装置(10)の性能は、コンピュータシミュレーションにより評価される。装置(1 0)のスループット、遅延、パケ ット損失確率等の様々な性能パラメータが、広範なシミュレーションにより得ら れる。パケットの長さは一定であると仮定する（つまり、各ＡＴＭセルにつき５ ３バイト）。スイッチの性能を評価するために、様々なトラフィックパターンが 用いられる。ランダムトラフィックは、ベルヌーイ法と定義される。ベルヌーイ 法では、パケットはランダムに到着し、後続の到着は独立したものである。更に 、到着パケットも同様に、全ての出力ポートに行くことになっている。低い割合 のデータ及び音声は、ランダムトラフィックとしてシミュレートすることができ る。その理由は、これらのパケット間の間隔はかなり大きいので、同じ源から続 く到着間の依存度は低いからである。もう１つのトラフィックパターンで興味深 いのは、バースティトラフィックである。バースティトラフィックでは、パケッ トの到着には大きな相互関係がある。従って、パケットのバーストが連続して到 着するのがよく見られる。バーストの平均長さは、平均割合及び平均バースト長 さを満たす適当なパラメータを持つ幾何学的分布に従って分布される。バースト の到着方法は、マルコフの方法をモデルとし、それに従ってシミュレートされた 。装置(10)の性能はまた、異種トラフィックパターンの下でも評価される。異種 トラフィックでは、バースティトラフィックとランダムトラフィックとが混合さ れ、異なるサービスを混合したものをシミュレートする。 図１２は、ランダムトラフィックの下、様々なスイッチについて、パケットの 平均遅延とスループットとの関係を示す曲線である。１６×１６、６４×６４、 ２５６×２５６及び１０２４×１０２４のスイッチについての平均遅延は、７０ ％のスループットまでは、それぞれ約２、３、４及び５である。より高い９０％ の負荷でも、任意のサイズのスイッチの平均遅延は１０より小さい。 図１３は、パケット損失確率と与えられた負荷との関係を示す曲線である。装 置(10)は、１ポート当たり１０のパケットバッファを持っている(つまり、１ポ ート当たり１０ＡＴＭセルについて、約５４０バイトのメモリ)。明らかに、よ り多くのバッファをスイッチで用いることができるが、妥当な時間の枠内でシミ ュレーション結果を得るために、１０バッファに限定されている。より多くのバ ッファを用いると、パケット損失確率が減少し、このためシミュレーション時間 を著しく増加させる。この図は、スイッチ性能に対する参考点として用いるべき である。パケット損失確率は、１６×１６、６４×６４、２５６×２５６及び１ ０２４×１０２４のスイッチについて、増速因子が４のときに得られる。装置(1 0)が１５５Ｍｂｐｓで作動しているなら、増速因子の４は、確かに、ＣＭＯＳ技 術を用いた実用化の範疇にある。図に示すように、１０２４×１０２４のスイッ チ構成についてのパケット損失確率は、与えられた負荷が０．６ （又は、全容量の６０％のスイッチ利用度）のとき、１０^-6より小さい。図１３ に示すように、より小さいサイズのスイッチのパケット損失確率は、更に低くな る。バッファの数を増加させることにより、ハードウェアの複雑さに大きな影響 を与えることなく、これらのパケット損失確率を更に低下させることができる。 現在のＡＴＭスイッチ製品は、所望のセル損失確率を得るために、１ポートにつ き、１，０００から１００，０００のセルバッファを持っている。 図１４及び図１５は、様々なサイズ（１６×１６から１０２４×１０２４）の スイッチに関して、バースティトラフィックの下、平均バースト長さがそれぞれ ８及び２０のときの、パケット損失確率と与えられた負荷との関係を示している 。このトラフィックは、全てのポートが、スイッチを通じてパケットを同時にバ ーストしているという点で、最悪のトラフィックパターンを示している。全ての 高速度ユーザが、同時にファイルの転送をバーストするというシナリオを想像す る人もいるであろう。装置(10)は、図に示すごとく、最悪の場合のシナリオでも 、妥当な損失で作動する。バースト長さが８の装置(10)の性能は、予想どおり、 バースト長さが２０のものよりも優れている。図１４において、コンピュータシ ミュレーション中に負荷が８０％のとき、１６×１６及び６４×６４のサイズの スイッチのパケットの損失はない。 シミュレーション中に、２０００万パケットが生み出された。 バースティトラフィックとランダムトラフィックとの混合トラフィックについ て、更なるコンピュータシミュレーションが行われる。シミュレーション結果は 、バースティトラフィックの割合が減少するに従い、パケット損失確率が減少す ることを示している。これらの結果からの観察される重要点は、パケット損失確 率は、トラフィックパターンによる影響をあまり受けないということである。こ のように、装置(10)は、異なるトラフィックパターンの混合の下で、強力な性能 を提供する。これは、全ての経路に公平なアクセスを与えるのに非常に重要な性 質である。例えば、高度にバースティなトラフィックのユーザは、完全に共用さ れたメモリスイッチ内にある他のユーザの能力を低下させる可能性がある。これ らのスイッチがこのような問題を解決するためには、複雑なバッファ管理機構を 必要とする。更に、これらのスイッチは、装置(10)のアーキテクチャにおいて提 供されるような増設可能性を提供できない。 ２進ルーティングアルゴリズムを用いた対称の設計に構成される装置(10)の実 施例を、ここに示す。装置(10)全体は、Ｉ／Ｏパケットブロセッサ(30)、スイッ チコントローラ(32)、ルーティングテーブル(34)及びパケットメモリ(36)を具え たスイッチングモジュール及び相互接 続モジュールにより構成される。パケットブロセッサ(30)は同期をとって、入力 パケットのエラーをチェックして、それらを装置(10)に提示する。ルーティング テーブル(34)は、論理チャネル翻訳を提供し、切換目的でパケットの行先アドレ スが復号されるようにしている。パケットメモリ(36)は、コンテンションの際に 、パケットを緩衝するために用いられている。スイッチング論理回路は、パケッ トの復号ヘッダ情報を用いて、それに従ってルーティングを行う。スイッチコン トローラ(32)は、スイッチングモジュールに埋め込むか、もしくは独立のモジュ ールに存在することができ、それは、基本的には、接続要求が到着するときに、 呼び出しを設定する。 図１７に示すように、入力パケットは、オーバヘッド及び情報ペイロードとし て、チャネル識別及びユニキャスト／マルティキャストルーティングビットを含 んでいる。パケットが入力ポートに到着すると、ヘッダ情報（チャネル識別及び ユニキャスト／マルティキャストビット）は、ルーティングテーブル内のルーテ ィング情報をチェックされる。次に、図１８に示すように、オーバヘッド情報は パケットに添付される。 このオーバヘッド情報は、スイッチング論理回路によって利用され、パケット をスイッチングモジュールの出力ポートへ送るか、もしくは相互接続モジュール を経由して、パケットを他のスイッチングモジュールに送る。 ２進ルーティングスキームでは、オーバヘッドは、ホップカウンタ及び、パケッ トが特定の出力ポート又はＩＭＡＰポートのどちらへ行く予定であるかを示す３ つのビットからなる。第１のビット“１”は、パケットの行先が出力ポートであ ることを示し、“０”は、パケットの行き先がＩＭＡＰポートであることを示し ている。第２及び第３のビット“０１”は、下側のポート（第１のビットが“１ ”であれば、下側の出力ポート）を示し、“１０”は、上側のポートを示してい る。“１１”は、マルティキャストな目的のため、パケットが両方のポートで行 く予定であることを示している。この表記法は、２進ルーティングアルゴリズム のために示されているが、この表記法を同様にモジュロＴデザインにも適用する ことができる。パケットオーバヘッドがルーティングテーブル(34)から得られた 後に、パケットは、上述のルーティングアルゴリズムに従って切り換えられる。 ここまでは、バランスのとれたトラフィックシナリオのために、対称のスイッ チ構成を説明してきた。装置(10)は、相互接続モジュールのプログラマビリティ を利用できるように、構成し直すことができる。クライエントーサーバのモデル では、少数のポートが高い帯幅のＩ／Ｏを必要とし、大いに利用されることがで きる。この場合、スイッチの構成を、渋滞や遅延を最小限にするようにするよう なものにすることができ、それは、ＩＭＡＰ をプログラムし直し、他のモジュールの帯幅を減少させて、高い帯幅の接続性を 提供することにより可能となる。例えば、重い負荷をかけられたポート１、２及 び４を持つ８×８のスイッチ（８入力、８出力）は、図１９に示すように再構成 することができる。濃い線は、薄い線が示すよりも、高帯幅の接続部を示してい る。このように、ポート１、２及び４は、より少ない遅延で、より高いスループ ットを得ることができる。 相互接続モジュールは、装置(10)のサイズが大きくなるに従って再構成するこ とができるように具体化することができる。この項目では、相互接続モジュール の具体化について説明する。プログラマブルな相互接続モジュールは、単数又は 多数のＦＰＧＡ（フィールド プログラマブル ゲート アレー）チップにより 構成され、装置(10)のサイズが大きくなるに従って、適当な相互接続パターンに プログラムし直すことができる。図２０に示すように、ＦＰＧＡのＩ／Ｏポート は、所望の接続パターンを設定できるようにプログラムすることができる。 例えば、８×８のスイッチの構成は、図２１に示すように、１つのＦＰＧＡ及び モード２の構成を持つ４つのスイッチングモジュールを用いたものにすることが できる。例えば、スイッチのサイズが１６×１６に拡大すると、図２２ａに示さ れる４つのスイッチングモジュールに、更に４つの追加用スイッチングモジュー ルが追加され、 従って、ＦＰＧＡは、そのパートをプログラムし直すことにより、所望の接続パ ターンを提供することができる。 図２２ｂを参照のこと。 スイッチは、本来的に、公平なアクセスを入力ポートに提供するものである。 特定の入出力接続部に重い負荷がかかり、このことがスイッチにおける渋滞の原 因ならば、スイッチは、同じ経路を共有して対になっている他の入出力接続部の 性能を低下させる。しかし、他の対の接続部は、この渋滞による影響を受けない 。このように、装置(10)は、対の接続部に与える渋滞を隔離し、その他の対の接 続部の性能の低下を防ぐ。図２３は、公平なアクセスの一例を示している。入力 ポート(l)から出力ポート(2)への接続部に重い負荷がかかり、装置(10)に渋滞を 生じると、第１及び第２のスイッチングモジュールを必要とする接続部だけが、 その渋滞による影響を受ける。装置(10)の残りの部分は、渋滞から隔離されてい る。何故なら、全ての対の接続部が、影響を受けたスイッチングモジュールを通 るわけではないからである。影響を受けたスイッチングモジュールにおける接続 部の性能は、影響を受けたスイッチ要素内で、公平な待ち行列(fairqueue)など のよく知られた公平な緩衝法を任意に採用することにより、必要に応じて向上さ せることができる。 図２４に示すように、切換システム(40)のスイッチングモジュール(12)に、任 意のスイッチアーキテクチャを 用いることができる。ユーザ(42)はいかなるＰＣ、ワークステーション又は会話 型テレビ等でもよいが、これらのユーザ(42)は、ＡＴＭ又はパケットを用いて互 いに通信する。ユーザ(42)は、各スイッチングモジュール(12)に接続され、次に スイッチングモジュール(12)は、上述したように、ＩＭＡＰ(14)を通じて相互接 続されている。特に、従来技術で知られているどんな切換技術でも、スイッチン グモジュールとして用いることができる。スイッチングモジュールの例は、図２ ７及び図２８に示している。スイッチングモジュールは少数のポート（４×４又 は８×８）を持つので、図２５に示すように、バスに基づくスイッチをスイッチ ングモジュールとして用いることができる。図２６に示すように、従来技術で知 られている共有メモリアーキテクチャも、同様にスイッチングモジュールとして 用いることができる。Ｉ／Ｏ（入出力）ポートは、入力パケットの同期を処理し 、これに従って、デジタル情報を伝送媒体へ転送する。パケットメモリ(36)は、 スイッチングモジュール(12)内で、パケットバッファとして用いられる。制御論 理は、前述のルーティングアルゴリズムに従って、入力パケットを適当な出力ポ ートへ切り換える。 ＡＴＭの一般的な説明については、Martin De Prycker，"Asynchronous Trans fer Mode Solution for Broadband ISDN"，Second Edition，Ellis Horwood Pub lisher， New York及びCCITT Recommendation，I Series(B-ISDN)，Nov．1990を参照のこ と。何れもここに引用することにより、出願と一体となる。 ＡＴＭ切換アーキテクチャの説明については、J.J．Degan，G.W.J．Luderer a nd A.K．Valdya，"Fast Packet Technology for Future Switches"，AT&T Techn ical Journal，Vol．68，No．2，pp．36-51，March/April 1989; K.A．Lutz，Co nsiderations on ATM Switching Techniques，International Journal of Digit al and Analog Cabled Systems 1:237-243，1988; F．Tobagi，"Fast packet ar chitectures for broadband integrated services digital networks"，Proceed ings of the IEEE，Vol．78，No．1，pp．133-167，January 1990; J.S．Turner ，"Design of a Broadcast Packet Switching Network"，In Proceedings of IN FOCOM '86，pages 667-675，IEEE，March，1986を参照のこと。何れもここに引 用することにより、出願と一体となる。 上記の実施例において、例示の目的で本発明の詳しい説明を行ってきたが、こ のような詳細な説明は、全くの例示のためのものであって、当該分野の専門家で あれば、以下の請求の範囲に記載する以外の事柄については、本発明の精神の範 囲から逸脱することなく、実施例の変形を行うことができることを理解すべきで ある。

【手続補正書】 【提出日】１９９７年８月２５日 【補正内容】 【図１３】 【図１４】 【図１５】

───────────────────────────────────────────────────── 【要約の続き】 ールに接続させる過程からなる。次に、相互接続モジュ ールをプログラムして、第１及び第２のスイッチングモ ジュール間に相互接続モジュールへの所望の接続性を生 み出す過程がある。次に、相互接続モジュール及び第１ 及び第２のスイッチングモジュールを通じてパケットを 転送させる過程がある。次に、少なくとも１つの追加ス イッチングモジュールを相互接続モジュールに接続させ る過程がある。次に、相互接続モジュールをプログラム し直して、第１、第２及び第３のスイッチングモジュー ルの間に相互接続モジュールへの所望の接続性を発生さ せる過程がある。本発明は、パケットを導く方法に関す るものである。

Claims (1)

1. 【特許請求の範囲】 １． パケットを切り換えるＬ個のスイッチングモジュール（Ｌ≧２の整数）と 、該Ｌ個のスイッチングモジュールのそれぞれに接続される相互接続モジュール とを具えている切換用装置であって、 相互接続モジュールは、Ｌ個のスイッチングモジュールの間に空間・時間 多重化接続性を与え、該相互接続モジュールは、Ｌ個のスイッチングモジュール 間の接続性について、プログラムし直すことが可能である切換用装置。 ２． 相互接続モジュールは増設可能である請求項１に記載の装置。 ３． 各スイッチングモジュールは、ユーザと接続するためのｍ個のＩ／Ｏポー ト（ｍ≧２の整数、各Ｉ／Ｏポートの速度は一定）及び相互接続モジュールと接 続するためのＴ個の相互接続モジュールアクセスポート（Ｔ≧２の整数）を有し ている請求項２に記載の装置。 ４． 各スイッチングモジュールは、バッファメモリを有している請求項３に記 載の装置。 ５． バッファメモリは、入力バッファメモリ及び出力バッファメモリにより構 成され、それらはＩ／Ｏポート及び相互接続モジュールアクセスポートに接続す る相互接続モジュールアクセスポートバッファメモリに 接続されている請求項４に記載の装置。 ６． 相互接続モジュールアクセスポートは、一定の速度Ｓ（Ｓ≧各Ｉ／Ｏポー ト(15)の速度）で作動する請求項５に記載の装置。 ７． 相互接続モジュールは、パケットを所望のＩ／Ｏポートに最大ｌｏｇ_TＮ 回のホップで到達させる請求項６に記載の装置。 ８． 相互接続モジュールアクセスポートの数は、パケットがスイッチングモジ ュール及び相互接続モジュールにより所望の行先へルーティングされる方法に対 応している請求項７に記載の装置。 ９． スイッチングモジュールは、公平な待ち行列(fair queue)を含んでいる請 求項７に記載の装置。 10． スイッチングモジュール及び相互接続モジュールは、モジュロＴで作動す る請求項７に記載の装置。 11． 装置は、同期をとって入力パケットのエラーをチェックするＩ／Ｏパケッ トプロセッサを含んでおり、該Ｉ／Ｏパケットプロセッサは、各スイッチングモ ジュールに接続されている請求項１に記載の装置。 12． 装置は、パケットが所望の行先に到達できるように、少なくとも１つのス イッチングモジュール内に接続性を設定するようなスイッチコントローラを含ん でいる請求項１１に記載の装置。 13． 各スイッチングモジュールは、該スイッチングモ ジュールにおいて接続性が適正に設定されるように、パケットの行先アドレスが 復号されるような論理チャネル翻訳を行うルーティングテーブル有している請求 項１２に記載の装置。 14． 各スイッチングモジュールは、パケットを緩衝するためのパケットメモリ を有している請求項１３に記載の装置。 15． 各スイッチングモジュール及び相互接続モジュールは、パケットをマルテ ィキャストできる請求項１４に記載の装置。 16． パケットを切り換えるＬ個のスイッチングモジュール（Ｌ≧２の整数）と 、該Ｌ個のスイッチングモジュールのそれぞれに接続される相互接続モジュール とを具えている切換用装置であって、 Ｌ個のスイッチングモジュールは、それぞれ他のどのスイッチングモジュ ールとも無関係にパケットを切り換えるので、Ｌ個のスイッチングモジュールを 横切ってパケットが分散的に切り換えられ、 相互接続モジュールは、Ｌ個のスイッチングモジュールの間に接続性を与 え、該相互接続モジュールは、スイッチングモジュールの最終的な数を予め知ら なくても拡大できる切換用装置。 17． 切換装置を作成する方法であって、 第１及び少なくとも第２のスイッチングモジュー ルを相互接続モジュールに接続させる過程、 相互接続モジュールをプログラムして、第１及び第２のスイッチングモジ ュール間に相互接続モジュールを通じて所望の接続性を生み出す過程、 相互接続モジュール及び第１及び第２のスイッチングモジュールを通じて パケットを転送させる過程、 少なくとも１つの追加スイッチングモジュールを相互接続モジュールに接 続させる過程及び 相互接続モジュールをプログラムし直して、第１、第２及び第３のスイッ チングモジュールの間に相互接続モジュールを通じて所望の接続性を発生させる 過程 からなる切換装置を作成する方法。 18． パケットを導く方法であって、 行先アドレス及びカウンタビットを持つパケットを第１のスイッチングモ ジュールに入力する過程、 パケットの行先アドレスが、第１のスイッチングモジュールに存在するか どうかをチェックする過程、 カウンタビットを読み取る過程、 行先決定コードのｉ番目のビットを読み取る過程であり、該ｉ番目のビッ トはカウンタビットに対応し、ｉ≧１の整数であり、 スイッチングモジュールのポートからパケットを送り出す過程であり、該 スイッチングモジュールの値は、ｉ番目のビットの値に対応し、 相互接続モジュールを通じて、パケットを第２のスイッチングモジュール に転送する過程、 カウンタビットを１つ増分させる過程及び 行先アドレスを見つかるまで探索する過程からなるパケットを導く方法。 19． パケットを導く方法であって、 アドレスビット、カウンタビット及び決定コードにより定義される複数の 行先アドレスを持つパケットを、第１のスイッチングモジュールに入力する過程 、 パケットの行先アドレスの何れかが第１のスイッチングモジュールに存在 するかどうかをチェックする過程、 カウンタビットを読み取る過程、 行先アドレスのｉ番目のビットを読み取る過程であり、該ｉ番目のビット はカウンタビットに対応し、ｉ≧１の整数であり、 セルの決定コードを行先アドレスビットのｉ番目のビットに対応するよう に設定する過程、 スイッチングモジュールの各ポートからパケット送り出す過程であり、該 スイッチングモジュールの値は、決定コードに対応し、 相互接続モジュールを通じて、パケットを第２のスイッチングモジュール に転送する過程、 カウンタビットを１つ増分させる過程、 パケットの行先アドレスの何れかが第２のスイッチングモジュールに存在 するかどうかをチェックする過程、 カウンタビットを読み取る過程、 行先アドレスビットのｉ番目＋１のビットを読み取る過程、 セルの決定コードを行先アドレスビットのｉ番目＋１のビットに対応する ように設定する過程及び 行先アドレスを見つかるまで探索する過程 からなるパケットを導く方法。