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