(57)【特許請求の範囲】
【請求項１】
Ｎ個の受信ポート及びＮ個の送信ポートを持ち、受信ポートに到着したパケットを送信ポートに伝送するＮ×Ｎ多段相互接続網において：
各段がＮ／２のＭ×Ｍスイッチング素子（ここで、Ｍは前記各素子の入力あるいは出力ポートの数）で構成される少なくともlogMＮのスイッチング段を具備する多段スイッチング網を含み；
前記各段の前記スイッチング素子の各々はＸの通過入力ポート、（Ｍ−Ｘ）の入力ルーティングポート、Ｘの通過出力ポート及び（Ｍ−Ｘ）の出力ルーティングポートを持ち（ここでは、Ｘは１あるいはそれ以上の定数）、前記各段内の前記各素子の通過出力ポートは次の段内で同一行に配置された素子の前記通過入力ポートと接続され、前記各段内の前記各素子の前記出力ルーティングポートはその次の段内の素子の前記入力ルーティングポートと完全シャフル接続により各々接続され、
前記各パケットは前記網で経路選択された回数（Ｎroute）を示すための第１情報フィールド及び前記網で滞留した時間を示すための第２情報フィールドを持つことを特徴とする多段相互接続網。
【請求項２】
前記各スイッチング素子は、経路選択する際に少なくとも前記パケットの第１情報フィールド値を１増加させることを特徴とする請求項１に記載の多段相互接続網。
【請求項３】
前記各スイッチング段と関連された最小ルーティング（ＭＲＮ）情報を発生し、前記ＭＲＮ情報を前記各段の前記スイッチング素子に供給する手段を含む請求項２に記載の多段相互接続網。
【請求項４】
前記各スイッチング素子は、出力ルーティングポートへの伝送を希望するパケットの中の前記第１情報フィールド値及び前記第２情報フィールド値が一番高いパケットを前記出力ルーティングポートで優先的に伝送することを特徴とする請求項３に記載の多段相互接続網。
【請求項５】
Ｎ個の受信ポート及びＮ個の送信ポートを持ち、受信ポートに到着したパケットを送信ポートに伝送するＮ×Ｎ多段相互接続網において：
各段がＮ／２のＭ×Ｍスイッチング素子（ここで、Ｍは前記各素子の入力あるいは出力ポートの数）で構成される少なくともlogMＮのスイッチング段を具備する多段スイッチング網を含み；
前記各段の前記スイッチング素子の各々はＸの通過入力ポート、（Ｍ−Ｘ）の入力ルーティングポート、Ｘの通過出力ポート及び（Ｍ−Ｘ）の出力ルーティングポートを持ち（ここでは、Ｘは１あるいはそれ以上の定数）、前記各段内の前記各素子の通過出力ポートは次の段内で同一行に配置された素子の前記通過入力ポートと接続され、前記各段内の前記各素子の前記出力ルーティングポートはその次の段内の素子の前記入力ルーティングポートと完全シャフル接続により各々接続され、
前記多段パケットスイッチング網はＳtotal−logMＮ＋１の出力アクセス点（ここで、Ｓtotalはスイッチング段の数）を持つことを特徴とする請求項１に記載の多段相互接続網。
【請求項６】
ターミナルからの原型パケットを受け入れ、前記受け入れた原型パケットにルーティングと関連した情報フィールドを付加してスイッチングパケットに変換する入力モジュールと；
各段がＮ／２のＭ×Ｍスイッチング素子（ここで、Ｍは前記各素子の入力あるいは出力ポートの数）で構成される少なくともlogMＮのスイッチング段を具備した前記スイッチングパケットのルーティング遂行する多段パケットスイッチング網と；
前記各段の前記スイッチング素子の各々はＸの通過入力ポート、（Ｍ−Ｘ）の入力ルーティングポート、Ｘの通過出力ポート及び（Ｍ−Ｘ）の出力ルーティングポートを持ち（ここで、Ｘは１あるいはそれ以上である定数）、前記各段内の前記素子の前記通過出力ポートは次の段内で同一行に配置された素子の前記通過入力ポートと接続され、前記各段内の前記各素子の前記ルーティングの前記出力ルーティングポートはその次の段内の前記素子の前記入力ルーティングポートと完全シャフル接続により各々接続され、前記スイッチング段中の一番目の段の素子の前記入力ルーティングポートは前記入力モジュールと接続され；
前記各スイッチング段と関連された最小ルーティング回数（ＭＲＮ）情報を発生し、前記ＭＲＮ情報を前記各段の前記スイッチング素子に供給するＭＲＮ発生ロジック及び；
前記多段パケットスイッチング網から前記スイッチングパケットを受け入れ、前記受け入れたスイッチングパケットから前記付加された情報フィールドを除去して前記原型パケットに変換する出力モジュールを含むパケットスイッチシステム。
【請求項７】
前記各スイッチング素子は前記スイッチングパケットを格納するためのＦＩＦＯ(first-in first-out)バッファ格納手段を含む請求項６に記載のパケットスイッチシステム。
【請求項８】
前記各スイッチング素子及び前記出力モジュールは前記スイッチングパケットが過度に到着することを防ぐための信号を前の素子に伝送する請求項６に記載のパケットスイッチシステム。
【請求項９】
前記各出力モジュールは前記スイッチングパケットの格納のためのバッファ格納手段を具備する請求項６に記載のパケットスイッチシステム。
【請求項１０】
前記各入力モジュールは前記原型パケットの格納のためのバッファ格納手段を具備する請求項９に記載のパケットスイッチシステム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はパケットスイッチング網（packet switching network) に関するものであり、より詳しくは複数のスイッチング段（several switching stages) を持つ多段相互接続網（multi-stage interconnection network)に関するものである。
【０００２】
【従来の技術】
高速パケットスイッチは広域総合情報通信網（Broad-band Intergated Services Digital Network:B-IDSN)のための核心技術である。近年非同期伝送モード（asynchronous transfer mode: ATM)が次世代の通信技術として注目を受けている。ATM は未来の遠隔通信標準（future telecommunication standards) を提示するアメリカのCCITT(現在はITU-T)により規定された。ATM の基本プロトコルデータユニット(protocol data unit : PDU)（通常‘セル’と呼ばれる）は５３バイトの固定された長さを持つ。ATM スイッチは上位概念ではパケットスイッチに分類される。高速パケットスイッチの必要条件としては、容易な実施及び良質のサービスのためのモジュラー構造及び信頼性の高い障害時無停止方式（high fault tolerance) などをあげられる（Peter Newman. "ATM technilogy for corporate networks"IEEE Communications Magazine, pages 90-101, April, 1992参照）。
【０００３】
パケットスイッチは、伝送リンク（transmission links）に接続されるシステムとして、スイッチと伝送リンク及びターミナル（terminal）からなるパケットスイッチング網の動作のための処理を実行する。伝送リンクはマルチプレクサ（multiplexer）あるいはディマルチプレクサ（demultiplexer）と同じ網装置（network equipment）に接続される。ターミナルマルチプレクサ／ディマルチプレクサに接続されたり、パケットスイッチングシステムに接続することができる。一般的に、パケットスイッチは入／出力リンクコントローラー及びスイッチング網で構成される。入力及び出力リンクコントローラーはプロトコル終了（protocol termination）,トラフィック管理（traffic management）、作業（jobs）と関連したシステム運営（system administration）などを遂行する。このコントローラーはパケットに対していくつかの処理を遂行して、スイッチング網からの内部スイッチングを助ける。スイッチング網は各パケットをそれの送信元リンク（source link）からそれの着信先リンク（destination link）に転換する空間分割スイッチング（space-division switching）を遂行する。
【０００４】
多くのパケットスイッチング網構造が知られている。これらのスイッチング網の重要な特徴は、高速スイッチング、小さい遅延、低い遅延変化のための自己ルーティング（self-routing) 、高品質のサービスのための良好な信頼性の高い障害時無停止方式及び維持補修(maintenance) の容易性のための高い規則性（regularity) 等があげられる。一般的に、パケットスイッチング網は数多くのスイッチング段で構成され、隣接したスイッチング段は相互接続される。そして、これらの網を‘多段相互接続網’と称する。各段は数多くの基本スイッチング素子として構成される。これら素子は自己ルーティングのためのスイッチング動作を遂行する。自己ルーティングは中央制御方式（central control scheme) がなくても各パケットが配置されたスイッチング素子により処理されることができるようになっている。これにより、高速スイッチングができる。
【０００５】
一方、パケットスイッチング網は、バッファリング方式（buffering scheme) により、入力キューイング（input queuing)、出力キューイング、入力及び出力キューイング、交差点キューイング（cross point queuing), 中央キューイング(central queuing) 、内部キューイング(internal queuing)構造などに分類することができる。入力キューイングでは、ヘッドオブライン（head of line;HOL) 問題が発生する。このHOL 問題は最大スループット（maximum throughput) を制限する。HOL 問題は入力FIFO（First in first out) バッファからのラインヘッド内のパケットが出力衝突により遮断される時に発生する。このパケットはそれらのルーティングのためラインヘッド位置に至る時まで待機し、それらの目的する出力ポートは他のパケットにより占有されない。出力キューイングの性能は入力キューイングのそれよりは良好であるが、それのバッファサイズは入力ポート数の増加により増加しなければならない。また、内部キューイング及びクロスキューイングでは、ポート数に応じてハードウェアの複雑化が増加する。中央キューイングでは、ポート数に比例してメモリアクセス回数が増加するため、メモリアクセス速度の低下が発生する。
【０００６】
また、パケットスイッチング網は‘時間分割及び空間分割方式’で分類することができる。各分割方式として、多くの構造のスイッチング網が提案されている（Peter Newman. “ATM technology for corporate networks”IEEE Communications Magazine, pages90-101,April 1992参照）。時間分割技術は大容量スイッチングシステム（large scale switching system）には不適切である。また、空間分割方式の単一経路網（single path network）は最大スループットが低く、ハードウェアが複雑になるなどのような問題点を持っている。これに反して、時間分割技術、空間分割技術中のマトリックス（S.Nojima, et al., "intergrated services packet network using bus matrix switch", IEEE Journal on Selected Area in Communications Magazine, 22(4):24-31, April 1984）構造及び完全に相互接続された構造は優秀な性能を持ち、基本素子の設計に適用されている。
【０００７】
多重経路スイッチング網中で、再循環方式（recirculating scheme)(A. Huang and S.Knauer, "STARLITE:a wideband digital switch. GLOBECOM, pages 121-125, November 1984参照）は再循環されるラインによりインレット（inlet)数の増加をもたらすので、大容量スイッチング網としては不適切である。一方、タンデムベニアン網（tandem banyan network)(F. A. Tobagi, et at., "Architecture, performance, and implemention of the tandem banyan fast packet switch", IEEE Journal on Selected Area in Communications, 9(8):1173-1193, October 1991.; U.S. Pat. No. 5,541,914 参照），並列ベニアン網（parallel banyan network)(Y. C. Jung and C. K.Un, "Analysis of out-of-sequence problem and preventative schemes in parallel switch architecture for high-speed ATM network", IEE-Proceeding-Communications, 141(1):29-38, February 1994参照),負荷分割網（load sharing network)(M. Kumar and J. R. Jump, "Performance of unbuffered shuffle-exchange networks", IEEE Transactions on Computer, c-35(6): 573-577, June 1986参照),膨張網（dilated network)(T. T. Lee and S. C. Liew, "Broadband packet switches based on dilated interconnection network", IEEE Transactions on Communications, 42(2.3.4):732-744,1994参照) 及びクロス網(Clos network)(T. T. Lee, "A modular architecture for very large packet switches", IEEE Transactions on Communications, 38(7) : 1097-1106,1990参照) の構造は大容量ATM スイッチングシステムとして使用される。
【０００８】
多中継路スイッチング網において、１つの入力ポートから１つの出力ポートへの経路の数を性能の１つの尺度とすることができる。ベニアン網は入力ポートから出力ポートへのただ１つの経路だけを持つ網である。タンデムベニアン網は直列に接続された網である。従って、多段ルーティング試しができる。並列ベニアン網は数多くの網が並列に接続される。再循環（recirculation）すなわち、リルーティング（rerouting）網では、各ベニアン網が重畳される。これにより、ルーティング試しで失敗したパケットが次の段からそのルーティング経路を通じてリルーティングすることができる。このリルーティング網は同一なハードウェア構成であるとき、一番大きい数のルーティング経路を持つ。
【０００９】
Lawrieは同時に多数のデータをアクセスするアレイプロセッサー(array processor) でデータアクセス及び構成（data access and alignment)のためのオメガ網（omega network)を発表した。（Duncan H. Lawrie, "Access and alignment of data in an array processor", IEEE Transactions on Computers, C-24(12):1145-1155, December 1975 参照）. オメガ網はn(=log2N) の段（stages) で構成される。ここで、Ｎは入力ポート数である。オメガ網の入力ポート数と出力ポート数は同一である。すなわち、オメガ網はいわば正方形サイズ（square size)である。オメガ網の各段はｎ／２の基本スイッチング素子として構成され、各スイッチング素子は２×２スイッチングを遂行する。
【００１０】
図１は２つの完全シャフル接続（two perfect shuffle connections)で構成したオメガ網を示している。オメガ網は両方向ルーティング（bidirectional routing)を支援し、完全シャフル接続の数は段の数と同一である。しかし、単一方向ルーティング支援を省略すれば、１つの完全シャフル接続を省略できる。Ｎ種の配線（wires)の完全シャフリングは上部のｎ／２種の配線からの下部のｎ／２種の配線を分離することにより、厳密に最下部に存在する最下部配線を２つのブロックの間に挿入することにより得られる。（S. W. Golomb, "Permutation by cutting and shuffling", SIAM Review, 3(4):293-297, October 1961).
【００１１】
また、完全シャフル接続は次のように説明することができる。各段で最上部から最下部スイッチング素子を２進数（ bn-1b n-2…b1) に番号をつけると、各スイッチング素子の上部出力ポートは番号（ bn-2b n-3…b10)を持つ次の段のスイッチング素子に接続され、それの下部出力ポートは番号（ bn-2b n-3…b11)を持つ次の段のスイッチング素子に接続される（C. L. Wu and T. Y. Feng, "On a class of multistage interconnection networks", IEEE Transaction on Computer, C-29(8):694-702, August 1980参照) 。すなわち、図１で、第２段（STG102) のスイッチング素子"10"は上部出力接続を通じて、第３段（STG103) のスイッチング素子"00"STG103"01"(baseline network), フリップ網(flip network)、改良されたデータ処理機(modified data manipulator)(F. A. Tobagi, et al., "Architecture, Performance, and implementation of the tandem banyan fast switch", IEEE Journal on Selected Area in Communications, 9(8):1173-1193, October 1991 参照 )、間接２進ｎキューブ網(indirect binary n-cube network)(M. C. Pease III, "The indirect binary n-cube microprocessor array", IEEE Transaction on Computers, C-26(5):458-473, May 1977 参照),そして、正規SWベニアン網(C. L. Wu and T. Y. Feng, "On a class of multistage interconnection networks", IEEE Transaction on Computer, C-29(8):694-702, August 1980 参照）に対応する。また、オメガ網は入力ポートから出力ポートへの唯一な１つの経路を持つベニアン網である。
【００１２】
オメガ網は図２に図示されたように特性を持つ。例示されたパケットは送信元ポート（source port)"011" から始まって、各段のスイッチング素子"01", "10"及び"00"を順次に通過した後、自分の目的地ポート(destination port)"001" に到達する。ルーティングタグ(routing tag) が目的地アドレス(destination address) であり、それの最上位ビットは最小段で使用され、最下位ビットはそれの最終段で使用される。ここで、各中間ルーティングスイッチング素子から目的地までの相対的距離が一律的に減少しないことを注目する必要がある。このような特性は各パケットが物理的な距離で目的地に向かって単純に接近する改良されたデータ処理機と対比される。たとえば、図２で例示されたパケットは、第２段（STG202) では目的地から１つのロー(one row) くらい離れているが、第１段(STG201)では目的地からより離れている。しかし、例示されたパケットは一段ずつ一段ずつ目的地へ向って接近していく。このような接近は目的地に対した物理的な距離でパケットが通過する接続配線の番号と類似する。相互接続配線（interconnection wires)にはそれらの最上部から最下部まで、（ bn-1b n-2…b1) の番号は付けられる。例示されたパケットの目的地への接近は、図２に図示されたように、ルーティング経路010 →100 →00１を通じて成立される。ここで、下線のビット数は経路選択された段の数が増加すればするほど、それとともに増加し、例示されたパケットがｎのルーティング段を全て通過した時、相互接続配線のアドレスが目的地アドレスになる。
【００１３】
半導体処理技術の急激な進歩と共に、大部分の電子的なシステムはVLSI(Very Large Scale Integration)チップを備えるようになった。このようなVLSI化の主な理由は早い応答速度、低い費用、小さい空間占有及び妥当性からである。公衆通信網（public network) 用パケットスイッチのサイズは非常に大きい。（R. J. Vetter, "ATM concepts, architecture, and protocols", Communications of the ACM,38(2):30-38, 109, February 1995参照）大容量システムを実現するためには、VLSI化が必須不可欠であり、VLSI用網構造を設計することには十分な注意が要求される。網構造設計の初期段階で、設計者は網を構成する基本VLSIチップのロジック分割（logic partition)を用意しなければならない。言い換えれば、VLSI化に適合した網構造が切実に要求されている。
【００１４】
ＶＬＳＩ化に適した構造としては、ハードウェアが複雑ではなく、単一のチップとしての機能的分割が容易なモジュラー構造をあげることができる。安価な金額及び維持保守の容易性のため、できるだけチップの種類の数を減らすことが必要である。システム具現の観点から見たとき、チップの数やチップの種類の数はシステム費用に大きな影響を及ぼす。チップの数はスイッチ構造の全体的なハードウェアを非常に複雑にし、チップの種類の数は構成のモジュール性により定められる。最近、単一チップとしての機能的ロジック分割は分割ブロックのロジックゲートの数ではなく、分割ブロックのインターフェースピンの総数により制限されている。単一チップからのロジックゲート数は半導体処理技術の急速な発展のおかげで非常に増加しているが、１つのチップの総ピンの数は器具的な限界により制限されている。モジュール内で、あるいは、ウェハ上で複雑に接続された多重チップモジュール（multi-chip module）やウェハの集積化（wafer scale integration）のようないくつかの技術が提示されたことがあるが、総ピン数は５００を超えることはない。例えば、よく知られている多種チップモジュールであるIntel社のペンティアム（登録商標）プロ（PentiunPro）プロセッサは約５５０万個のトランジスターを具備しているが、それのピン数は３７８である。スイッチング網は数多くのチップで具現するのに困難な構造になっている。なぜならば、スイッチング網が非常に多くの相互接続配線を持つので、それが１つのチップで分割される場合、多くのインターフェースピンを必要とするからである。それにもかかわらず、スイッチング網で一番重要なことは、高速スイッチングに対する要求を満足させることができる高性能を持つことである。
【００１５】
図３は単一チップにおける機能的分割の困難性を示している。図３で、単一チップの機能的分割のためＭ１、Ｍ２、及びＭ３中の１つが選択された場合、いくつの特定設計を考えなければ、チップが製造された後にはチップ内のスイッチ素子に含まれた相互接続方式を変更することが不可能であるので、図３で図示した８×８スイッチを単一種類のチップだけで具現することができない。チップとしての機能分割が‘Ｍ４’である場合、チップ内では相互接続部が含まれていないので、１種類のチップだけでも十分に８×８スイッチを具現することができる。ここでは、機能的分割方法だけで、図３のモジュール性を得られる場合を説明したが、そのようなモジュール性は多段相互接続網の相互接続方式に大いに依存される。
【００１６】
種々のシステムにおいて、高い信頼性は非常に重要なものであるが、大容量パケットスイッチではそれがもっと切実に要求される。なぜならば、そのような大容量パケットスイッチは基本的な社会的インフラである公衆通信網として使用されるからである。高い信頼性とチップとしての機能分割の容易性のためには、モジュラー構造が非常に重要である。
【００１７】
図４は改良されたデータ処理機からの故障修理の非効率性を見せている。図４で図示されたように、システム内で故障した素子があっても、システム性能の低下を防止し、高品質のサービスを提供するためにそのシステムから故障した素子を除去しなければならない。故障した素子がチップで集積化されたように代替が不可能であると、その時は、そのシステム内の基本モジュラーブロックであるモジュールを廃棄しなければならない。万一、ベニアン網が最小モジュラーブロックであると、その時には代替のために故障した素子を持つベニアン網自体を廃棄しなければならない。１つのモジュールを代替するためには、数多くの作業が必要であるので、電源衝撃（power shock）から新しいモジュールを保護し、システム安定性を最大に考えるならばシステム中断は不可避である。しかしながら、継続的なサービスのためには故障による代替をシステム中断（system shutdown）なしにオンラインで実行しなければならない。
【００１８】
【発明が解決しようとする課題】
本発明の目的は高集積化ができる構造の多段相互接続網を提供することであり、高信頼性を備えた多段相互接続網を提供することである。
【００１９】
本発明の他の目的は高いモジュラー特性を持つことにより、単一チップとしての機能的分割が容易なパケットスイッチシステムを提供することであり、低いパケット損失率（packet loss ratio)を持つパケットスイッチされる自己ルーティング多段接続網（packet-switched self-routing multistage interconnection network)を提供することである。
【００２０】
【課題を解決するための手段】
目的を達成するための本発明の１つの特徴によると、Ｎ個の受信ポート（incoming ports）及びＮ個の送信ポート（outgoing ports）を持ち、受信ポートに到着したパケットを送信ポートへ伝送するＮ×Ｎ多段相互接続網は：各段がｎ／２個のＭ×Ｍスイッチング素子（ここで、Ｍは各素子の入力あるいは出力ポートの数）で構成される少なくともlogMＮのスイッチング段を具備する多段パケットスイッチング網を含む。
【００２１】
各段のスイッチング素子各々はＸの入力バイパスポート、（Ｍ−Ｘ）の入力ルーティングポート、Ｘの通過出力ポート及び（Ｍ−Ｘ）の出力ルーティングポートを持ち（ここで、Ｘは１あるいはそれ以上の定数）、各段内の各素子の通過出力ポートは次の段内で同一行に配置された素子の通過入力ポートと接続され、各段内の各素子のルーティング出力ポートはその次の段内の素子の入力ルーティングポートと完全シャフル接続により各々接続される。各パケットは自身が網で経路選択された回数（Ｎroute）を示すための第１情報フィールド及び自身が網で滞留した時間を示すための第２情報フィールドを持つ。各スイッチング素子は自分により経路選択される少なくとも１つのパケットの第１情報フィールドの値を１増加させる。また、多段相互接続網は各スイッチング段と関連された最小ルーティング回数（minimum routing number；ＭＲＮ）情報を発生し、ＭＲＮ情報を各段のスイッチング素子に供給するロジックを加えて持つ。各スイッチング素子はその１つの出力ルーティングポートへの伝送を希望するパケット中の第１情報フィールド値及び第２情報フィールド値が一番高いルーティング出力ポートに優先的に伝送する。多段パケットスイッチング網はＳtotal−logMＮ＋１の出力アクセス点（ここで、Ｓtotalはスイッチング段の数）を持つ。
【００２２】
他の特徴によると、本発明のパケットスイッチシステムはターミナルからの原型パケット（original packets）を受け入れ、受け入れた原型パケットにルーティングと関連した情報フィールドを付加してスイッチングパケットに変換する入力モジュールと；各段がｎ／２のＭ×Ｍスイッチング素子（ここで、Ｍは各素子の入力あるいは出力ポートの数）で構成される少なくともlogMＮのスイッチング段を具備し、スイッチングパケットのルーティングを遂行する多段パケットスイッチング網と；各スイッチング段と関連した最小ルーティング回数（ＭＲＮ）情報を発生し、ＭＲＮ情報を各段のスイッチング素子に供給するＭＲＮ発生ロジック及び；多段パケットスイッチング網からスイッチングパケットを受け入れ、受け入れたスイッチングパケットから付加された情報フィールドを除去し、原型パケットに変換する出力モジュールを含む。各段のスイッチング素子各々はＸの入力バイパスポート、（Ｍ−Ｘ）の入力ルーティングポート、Ｘの通過出力ポート及び（Ｍ−Ｘ）の出力ルーティングポートを持ち、（ここで、Ｘは１あるいはそれ以上の定数）、各段内の各素子の通過出力ポートは次の段内で同一な行に配置された素子の通過入力ポートと接続され、各段内の各素子のルーティング出力ポートはその次の段内の素子の入力ルーティングポートと完全シャフル接続により各々接続され、スイッチング段中の一番目の段の素子の入力ルーティングポートは入力モジュールと接続される。各スイッチング素子はスイッチングパケット格納のためのＦＩＦＯ（first-in first-out）バッファ格納手段を具備する。各スイッチング素子及び出力モジュールはスイッチングパケットを過度に到着することを防ぐためのバックプレシング信号（back-pressing signals）を前の素子に伝送する。
【００２３】
【発明の実施の形態】
次に、添付図面を参照して本発明の実施の形態に対して詳細に説明する。
【００２４】
図５は本発明によるバイパスオメガ網（bypassing omega network:BON)あるいはスプレッドオメガ網（spread omega network) で使用されるＭ×Ｍ基本スイッチング素子の例を簡単なブロック図で図示したものである。図５に図示された例ではＭは３である。図示されたスイッチング素子500 は３つの入力ポート(501-1,501-2,501-3) 及び３つの出力ポート(501-1,501-2,501-3) を備え、３×３スイッチングを遂行する。スイッチング素子500 の出力ポート(501-1,501-2,501-3) には'0','1' 及び'2' の番号が付けられている。番号'0' 及び'1' が付けられた２つの出力ポート、すなわち、ルーティングポート（routing ports)(502-1, 502-3)は次の段に完全シャフルに接続され、番号'2' が付けられた余りの１つの出力ポートすなわち、バイパスポート（bypassing port)(502-2)は次の段で同一な位置にある素子のバイパス入力ポートと接続される。
【００２５】
図６は本発明によるS total のスイッチング段を持つＮ×Ｎバイパスオメガ網の１つの実施の形態を簡単なブロック図形態に見せている。図６に図示された特定の例で、Ｎは８である。このバイパスオメガ網（BON)(600) は総スイッチング段の数（S total ）が４であり、入力（あるいは出力）ポートの数（Ｎ）が８である。すなわち、このバイパスオメガ網（BON)は４つのスイッチング段（STG601〜STG604),８つの入力ポート（601-1, 601-2, …, 601-8)及び８つの出力ポート(602-1, 602-2,…, 602-8)を具備している。各段（STG601〜STG604) は、ｎ／２すなわち、4(＝８／２) の３×３（Ｍ×Ｍ）スイッチング素子で構成される。前述したように、各スイッチング素子（603-1,…, 603-4; 604-1, …, 604-4; 605-1, …, 605-4; 606-1, …, 604-4)は３×３スイッチングを遂行する。
【００２６】
この網(600) で、スイッチング段の総数（Ｓtotal ）はn(＝log2N)より大きいかまたは同じでなければならない。近接な二段の相互接続は完全シャフル接続と水平接続される。完全シャフル接続はこの明細書の従来技術の欄ですでに述べたように同一な方式からなる。各スイッチング素子の中央出力ポートは次の段の同一な位置に配置されたスイッチング素子に水平的に接続される。
【００２７】
スイッチング素子間の接続を説明するために、図６で、各段の最上部から最下部への素子に２進数（b n-1bn-2 …b1) の番号を付ける。要するに、第２段（STG602) で、最上位スイッチング素子（604-１）の番号は"00"であり、最下位スイッチング素子（604-4 ）の番号は"11"である。すでに、図５を参照して説明したように、各スイッチング素子の出力ポートには、‘０’、‘１’及び‘２’の番号が付けられている。従って、近接した２つのスイッチング素子の間の各相互接続配線には番号（b n-1bn-2 …b1ｔ）を付ける。ここで、（ bn-1b n-2…b1) は先行する段のスイッチング素子番号であり、ｔは先行するスイッチング素子の出力ポート番号である。スイッチング素子番号（ bn-1b n-2…b1) は２進数であり、ｔは基数（radix ）３の数、すなわち、３進数（ternary number) である。あるスイッチング素子の出力ポートｔ(=0,1,2)に接続される次の段のスイッチング素子の番号をNSW (t) (SE)と定義すると、このバイパスオメガ網(600) の各スイッチング素子の接続は次の式で表示することができる。
【００２８】
【数１】
NSW (0) （ bn-1b n-2…b1) ＝（ bn-2bn-3 …b1０）
NSW (0) （ bn-1bn-2 …b1) ＝（ bn-2bn-3 …b1１）
NSW (0) （ bn-1bn-2 …b1) ＝（ bn-1bn-2 …b1)
例えば、図６で、第３段(STG603)のスイッチング素子(605-3) は太い実線で示された３つの接続配線を持っている。スイッチング素子(605-3) の各出力ポートに各々接続される次の段(STG604)のスイッチング素子の番号は数１により決定することができる。スイッチング素子(605-3) の出力ポート‘０’は番号"00"の次の段スイッチング素子(606-1) と接続され、ポート‘１’は番号"01"の素子(606-2) と接続される。すべてのスイッチング素子の出力ポート‘２’は次の段の同一な位置に配置されたスイッチング素子の対応する入力ポートに接続される。ここで、各スイッチング素子の入力ポートの順序には特別な意味がない。すなわち、３つの入力ポートの順序が任意の順序により決定されてもその順序はシステム動作においては何ら困難はない。
【００２９】
バイパスオメガ網(BON)(600)は１つの出力ポートに対してＫの多重出力アクセス点(multiple output access points) を持つ。言い換えれば、バイパスオメガ網(600) の１つの排出通路(sink)として網に接続される出力ポート(602-1, 602-2,…, 602-8)各々はタイムスロット(time-slot) 方式にＫのパケットを受け入れることができる。図６に示したように、各出力接続配線は各スイッチング素子の出力ルーティング配線から導出され、下の方向に延長して、各出力ポート(602-1, 602-2,…, 602-8)に至る。出力アクセス点の数Ｋは次の式で示すことができる。
【００３０】
【数２】
Ｋ＝Ｓtotal −ｎ＋１
ここで、ｎ＝log2Ｎ
例えば、図６では、Ｋが２である。バイパスオメガ網(BON)(600)に接続される各出力ポート(602-1, 602-2,…, 602-8)は後の部分にあるＫ個の段からのＫ個の入力を持たなければならない。図６で、番号"000" の出力ポート(602-1) のために２つの出力アクセス点が導出されるが、それらの中で１つ(607-1) は第３段(STG603)のスイッチング素子(605-1) の相互接続配線から導出され、他の１つ(607-2) は第４段(STG604)のスイッチング素子(606-1) の相互接続配線から導出される。これら２つの相互接続配線(607-1, 607-2)にはそれらと接続される出力ポート(602-1) のアドレス"000" と同一な番号が付けられる。
【００３１】
次は、図７を参照して本発明によるバイパスオメガ網(BON) のルーティング原理に対して説明する。図７に示されたバイパスオメガ網は図６と同一な構成になっている。本発明のバイパスオメガ網で、各スイッチング素子はパケットに対して自己ルーティング、バイパス(bypassing) 、偏向(deflection)及び廃棄(discarding)処理を遂行する。このバイパスオメガ網は目的地アドレスをルーティングタグとして使用するにより自己ルーティングを支援する。しかし、この網は１つの入力ポートと１つの出力ポートの間にただ１つの経路だけを持つ従来のオメガ網（図１参照）とは異なり、多数の経路を持つ多重経路網である。このバイパスオメガ網のルーティング原理は次のようである。すなわち、２つあるいはそれ以上のパケットが同一な出力ポートを目的地として同時にそこに向く時、スイッチング素子ルーティング競争（routing contention) で負けたパケット（あるいはパケット）を次の段に通過させる。例えば、図７で、１つの示されたパケット‘Ａ’は送信元あるいは入力ポート(701-1) から出発してアドレス"111" の出力ポート(702-8) に向き、他の１つの例示されたパケット‘Ｂ’は入力ポート(701-6) から出発してアドレス"110" の出力ポート(702-7) に向く。例示された各パケットは自分の目的地アドレスをルーティングタグとして使用し、目的地に向かって伝送される。
【００３２】
図７で、パケットＡは第１段(STG701)で、目的地アドレス"111" の最上位ビット、すなわち、ルーティングビット‘１’により、番号"001" の配線に接続されたスイッチング素子(703-1) の下位ルーティングポートへ伝送される。第２段(STG702)及び第３段(STG703)で、パケットＡは目的地アドレス"111" の中間ビット‘１’及び最下位ビット‘１’により該当スイッチング素子(704-2, 704-3)の下位出力ポートに順次伝送される。２つの例示されたパケットＡ及びＢは第２段(STG702)のスイッチング素子(704-2) でそれの同一な出力ルーティングポート（すなわち、下位ルーティングポート）を得るために相互競争する。このルーティング競争で、パケットＡが勝ち、パケットＢが負けたとすると、パケットＡは希望するルーティングポート、すなわち、素子(704-2) の下位ルーティングポートを得て、パケットＢは素子(704-2) のバイパスポートを得る。結局、第２段(STG702)で、パケットＢはバイパスポートを通じて、第３段(STG703)の同一位置スイッチング素子(705-2) に運ばれる。第１，第３及び第４段(STG701, STG703, STG704)のスイッチング素子(703-3, 705-2, 706-4) はパケットＢを経路選択し、第２段(STG702)のスイッチング素子(704-2) はパケットＢを通過させる。従って、第１、第３及び第４段(STG701, STG703, STG704)は‘ルーティング段’と呼ばれ、第２段(STG702)は‘バイパシング段’と呼ばれる。
【００３３】
パケットルーティング経路はそのパケットが通過した相互接続配線の番号の順序で表示されることができる。パケットＡのルーティング経路は"001" →"011" →"111" である。パケットＢのルーティング経路は"101" →"012" →"011" →"110" である。２つのルーティング経路の差は通過された相互接続配線の番号と下線の相互接続配線番号の増加する順序である。パケットＡのルーティング経路は図２を参照して説明した従来のオメガ網のように相互接続配線アドレスの下線のビットの数が順次的に増加する。これとは対照的に、パケットＢのルーティング経路の相互接続配線アドレスの下線の数は順次的に増加しない。これは、目的地ポートへの接近は断絶なしに成立されないことを意味する。
【００３４】
第２段（ＳＴＧ７０２）で、以前の相互接続配線番号が“００１”であったが、段（ＳＴＧ７０２）次の相互接続配線番号が“０１２”であったので、目的地ポートへの接近が中断された。下線の数字の個数はルーティングビットとして処理された目的地アドレスビットの個数を意味する。例えば、第２段で、パケットＡのルーティング経路に属する配線番号“０１１”の２つの下線のビット“１１”は目的地アドレス中の２ビットがルーティングタグとして処理されたことを意味する。パケットＢを通過させた段（ＳＴＧ７０２）を省略する場合、パケットＢのルーティング経路は‘１０１’→（‘０１２’）→‘０１１’→‘１１０’のようにオメガ網のルーティング経路と同一になる。
【００３５】
ルーティング経路中の相互接続配線番号の最後の数‘２’はパケットＢが第２段(STG702)のスイッチング素子(704-2) から第３段(STG703)の同一位置スイッチング素子(705-2) に移動することを意味する。従って、パケットＢの処理完了されたルーティング情報は廃棄されない。ルーティング情報を保存するこのような動作はルーティングポート獲得競争の敗者がすでに処理されたすべてのルーティング情報を失う従来のリルーティング網及びタンデムベニアン網のそれとは違う。網は、処理完了されたリルーティング情報の損失を最小化するため、段数の増加によりルーティング距離がもっと短く改良されたデータ処理を行った。とにかく、図７で、パケットＡ及びＢ各々は３つのルーティング段（これらの段で各パケットはバイパスポートではない正確なルーティングポートを探す）を通過した後、互いの目的地に至る。
【００３６】
このようなバイパスオメガ網で、アドレス"dn-1dn-2 …d0" の目的地に向くパケットがｋ番目ルーティング段で、d1ビットにより経過選択されたり、次の段の同一な位置のスイッチング素子に通過されると、ルーティング段の間にいくつのバイパシング段が挿入されているとしても、パケットｎ個のルーティング段を通過した後に自分の目的地に到達する。ここで、i はn-k で定義される。
【００３７】
前に説明したように、本発明のバイパスオメガ網はＫ個の多重出力アクセス点を持つ。言い換えれば、このバイパスオメガ網は多数のパケットが１つの目的地、すなわち、出力ポートに到達するようにする。このような多重到着のための出力ポートのため、数多くの入力ポートを用意しなければならないし、スイッチング素子はいくつもの機能をもたなければならない。出力ポートはパケットの目的地のアドレスと同一なアドレスを持つ相互接続配線に到着したパケットを捕獲する。各スイッチング素子は捕獲したパケットを出力ポートにより逃がさなければならない。
【００３８】
このバイパスオメガ網を通過するパケットは、各スイッチング素子からのスイッチング動作のために図８に示したような固定されたフォーマットを持つ。ターミナルにより発生される原型パケット(original packet) との区別のために、このパケットは一般に“スイッチングパケット”と呼ばれる。以後、特別に必要な場合を除いては、“パケット”という用語を“スイッチングパケット”と区別なしに使用する。スイッチングパケットは、図示したように活性ビット(activity bit)、目的地アドレスであるルーティングタグ、パケットをルーティングした段の個数（すなわち、パケットが経路選択された回数）を示すルーティング回数Ｎroute 、そして、伝送ラインを通じて、到着した原型パケットデータフィールドからなる。スイッチングパケットがバイパスオメガ網に供給される時、パケットのルーティング回数Ｎroute は０で設定される。その後、パケットが入力した各スイッチング素子でパケットが正確な出力ルーティングポートにより出力されたときのみパケットがルーティングされた段の数を示すルーティング回数Ｎroute を１つずつ増加する。パケットの通過最終段を除いては他の段でも増加することはできるが、あるパケットがあまり多くの段を通過すると、そのパケットは自分の目的地に到達できないので、すべてのパケットが次の段へ通過するとは限らない。図９は"000" 送信元ポート(901-1) を出発して"111" の目的地ポート(902-8) へ向かうパケットの２つのルーティング経路ＰA 及びＰB を示している。１つのルーティング経路ＰA は"001" →"012" →"011" →"112" →"111" であり、他の１つのルーティング経路ＰB は"001" →"012" →"012" →"011" である。経路ＰA はパケットをそれの目的地に完璧に伝送するが、経路ＰB はパケットを正確に伝送しない。経路ＰA からのルーティング段の総数は３であり、経路ＰB からのそれは２である。
【００３９】
上述したように、このバイパスオメガ網では、各パケットがｎ個の段を通じて、伝送された後に自分の目的地に到達する。それで、このバイパスオメガ網で、あるパケットが１つの入力ポートからＮ個の出力ポート中のどこかに到達するためには、前で説明したオメガ網やよく知られているデルタ網(J．H. Patel,"Performance of processor-memory interconnections for multiprocessors", IEEE IEEE Transactions on Computers, C-30(10):771-780, October 1981参照) と同じように、少なくともn(=log2N) の段が存在しなければならない。従って、バイパスオメガ網を通過するすべてのパケットが少なくとも、ｎ回のルーティングを行なう方法がなければならない。ある段からの通過と関連した最小ルーティング回数(Minimum Routing Number; MRN) は、過度バイパシング(excessive bypassing) 動作を抑制する。最小ルーティング回数(MRN) を定義する前、余分の段数(extra stage number)Ｓextra を次の式のように定義する。
【００４０】
【数３】
Ｓextra ＝Ｓtotal − log2 Ｎ
余分の段数Ｓextra はこのバイパスオメガ網からの多重経路のための付加的な段の数を示す。例えば、図９に図示された網の余分段数Ｓextra は2(=5-log28) であり、最後２つの段(STG904, STG905)が付加的な段である。任意の段からの最小ルーティング回数(MRN) は次のように定義される。
【００４１】
【数４】
MRN(s)=max(0, s − Sextra )
ここで、s は段番号である。
ここで、数４から、各段は自分の段番号で付加的な段の数を除いた値と同一な最小ルーティング回数(MRN) あるいは０を持つ。具体的に例を示すと、図９で第１段(STG901)ないし第５段(STG905)が各々１ないし５の番号ｓを持つ時、図示された網の余分段数(Sextra ) は2(=5-log28) であるので、第１段(STG901)乃至第５段(STG905)と関連したMRN(1)乃至MRN(5)は各々0,0,1,2,３である。
【００４２】
このバイパスオメガ網において、あるパケットが番号ｓの任意の段から次の段に通過する場合、パケットのルーティング回数Ｎroute が最小ルーティング回数MRN(s)より大きくてもまた同じでも、過度バイパシングによりパケットはそれの目的値に到達する。
【００４３】
このバイパスオメガ網で、例えば３つのパケットがスイッチング素子に到着し、それら全部が同一な出力ポートに向かって伝送する場合があるかもしれない。この場合、３つのパケットの中で、ただ１つだけが正確なルーティングポートを取ることができ、他の１つのパケットはバイパス出力ポートを取る。しかし、残りの１つのパケットは分配効果(distribution effect)(T. Lang and L. Kurisaki, "Nonuniform traffic sports(nuts)in multistage interconnection networks", Journal of parallel and distributed computing, 10(1):55-57, 1990参照) により強制的に不正確なリルーティングポートへ伝送される。
【００４４】
図１０で、第２段(STG1002) のスイッチング素子(1004-2)に３つのパケットが同時に到着して下位ルーティングポートを得るために競合する。１つの希望ポートを得て、他の１つのパケットは次の段(STG1003) に通過される。これらの２つのパケットのルーティング経路は各々"101" →"011" →"111" と"012" →"012" →"101" →"111" →"110" である。だが、入力ポート(1001-1)から出発する余りの１つのパケットのルーティング経路"001" →"010" →"101" →"011" →"111" である。この経路で、接続配線の下線のビットの数が一律的に増加せず、第２段(STG1002) 以後の接続配線の下線のビット数が増加する。言い換えれば、最後のパケットはたとえそれのルーティングタグが‘１’としても第２段(STG1002) で不正確なルーティングポート、すなわち、スイッチング素子(1004-2)の上部ルーティングポートに伝達される。このような動作を‘偏向’という。偏向が発生された時、第１段で処理されたルーティング回数は喪失される（下線のない相互接続配線番号"010" 参照）。しかし、偏向されたパケットは連続した３つのルーティング段(STG1003, STG1004, STG1005) を通過した後、自分の目的地に到着する。従って、０のMRN(s)を持つ番号ｓのある段でパケットが偏向されてもそのパケットは自分の目的地に到達することができる。
【００４５】
このバイパスオメガ網で、パケットは自分の目的地に到達するまで、段を通じて伝送される。この時、そのパケットは各段でルーティング、通過及び偏向動作で処理される。しかし、いくつのパケットはポート獲得競争のため、何の処理も受けない。スイッチング素子内にバッファと同じ記憶素子がないと、これらのパケットは廃棄しなければならない。このようなパケットの廃棄はパケット損失をもたらす。パケット損失率はパケットスイッチシステムの非常に重要な性能指標(performance index) として、よりよい性能のためにその値が最小化されなければならない。このバイパスオメガ網のスイッチング素子はバッファがないので、廃棄されなければならないパケットを格納するための内部バッファを持つと、この網のパケット損失率は減少する。これに対しては後で説明する。
【００４６】
以上で説明したように、本発明のバイパスオメガ網で、入力ポートに入ったパケットは目的地住所（ｂn-1ｂn-2 ．．．ｂ0）により、経路選択されるが、この時、万一パケットのルーティング回数Ｎrouteが０であると、第１段でパケットが経路選択され、それのルーティング回数Ｎrouteをｄとすると、第ｄ＋１段からそれが経路選択される。各スイッチング素子は、入力されたパケットのルーティング回数Ｎrouteによりそのパケットを出力ルーティングポートを通じて伝送する際に、該当パケットのルーティング回数Ｎrouteを１増加する。万一、あるスイッチング素子に入力された２つ以上のパケットが同一なルーティング回数を持つと、そのスイッチング素子は１つのパケットだけを希望する出力ルーティングポートに送ることができる。この時、希望するルーティングポートをチャージできないパケットはバイパスポートを通じて、次の段の同一位置のスイッチング素子に伝達され、通過されるパケットのルーティング回数Ｎrouteは変化しない。１つの出力ルーティングポートをいくつかのパケットが同時に希望する時は大きいルーティング回数Ｎrouteを持つパケットに高い優先順位を与える。万一、出力ポート獲得競争で負けたパケットの数がバイパスポートの数より大きいと、スイッチング素子は余りのパケットのルーティング回数を０にした後、それらを任意のポートを通じて、次の段に伝送する。そして、もう一度言うと、残余パケットは偏向される。
【００４７】
入力されたパケットのルーティング回数Ｎroute がn(=logb Ｎ、ここで、ｂは各スイッチング素子の出力ルーティングポート数であり、Ｎはバイパスオメガ網の入力ポート数である）であると、各スイッチング素子は入力されたパケットを廃棄する。バイパスオメガ網の各出力モジュールはＳtotal -n+1の後尾の段の出力ポートからＮroute がｎであるパケットを検出して受け入れる。このような動作原理により本発明のバイパスオメガ網はすべてのパケットの自己ルーティングを遂行する。
【００４８】
本発明のバイパスオメガ網は故障に強い。高い故障許容性を得るために次のような２つの方法をとっている。すなわち、１つは故障した素子を迂回することであり、他の１つは故障した素子を除去することである。提案された網で、追加に提供された経路を通じて、パケットが故障した素子を迂回するが、そうするためには、十分な余分の経路が必要である。後者の方法では、故障した素子を検出するためのオンライン故障検出能力と誤動作なしにスイッチシステムからその故障した素子を除去する動作が必要である。
【００４９】
図１１は本発明のバイパスオメガ網の高い故障許容度を説明するための図面である。図１１では故障した素子(1105-3)がハッチングで示されている。図示されたシステムはスイッチング素子(1105-3)が故障してウォッチドックタイマ(watch-dog-timer) （図示されていない）の計測時間に達した時、‘ハイ’になる各スイッチング素子が自己診断ピン(self-diagnosing pin) を監視することにより、故障した素子を検出する。
【００５０】
故障した素子が検出されると、誤動作防止のために故障した段を除去しなければならない。このように故障した段はそれのすぐ前の段の出力リンクとそれのすぐ後の段の入力リンクの間リンク（１１１１）を選択するデジタルスイッチ（１１１０）により、オンラインに即時に除去されることができる。故障した段が除去されると、スイッチング段の総数（Ｓtotal）が減少するので、最小ルーティング回数ＭＲＮ（ｓ）も変更しなければならない。故障が発生した時、ＭＲＮ（ｓ）は実線箱の中の数字から点線箱の中の数字に変更される。
【００５１】
以上のように、バイパスオメガ網はそれの運用中に故障した段が検出された場合、故障した段のオンライン除去が可能である。従って、本発明のバイパスオメガ網を使用すると、網の維持補修が容易であるとともに高品質のサービスを提供できる。
【００５２】
スイッチング網の全体的なハードウェア複雑度はスイッチング段及び出力アクセス点の数により左右される。出力アクセス点の数が増加すると、出力モジュールからのハードウェア複雑度が増す。だが、ハードウェア複雑度の加重係数(weighting factor)は出力アクセス点が増加する場合より段の数が増加する場合により大きくなる。段の総数を減らすためにパケットの早期到着(early arriving)を試す。
【００５３】
スイッチングシステムの入力ポートでは出発パケット(starting packets)各々が自分の目的地から少し距離をおいて配置される。この時、各パケットの距離は互いに違う。言い換えれば、いくつのパケットはｎより小さい段でそれらの目的地に到着することができる。これは一番目のスイッチング素子のアドレス(sn-1sn-2 …s1) が目的地のアドレス(dn-1dn-2 …d0) と多少同一なパターンを持つことができるからである。例えば、あるパケットの出発アドレス(starting source address)(s2s1) が目的地アドレス(dn-1dn-2)と同一であるとすると、ルーティングタグｄn-2 によってパケットはすぐｎ−２ルーティング段でそれの目的地に到達することができる。これを‘早期到着’と呼ぶ。
【００５４】
図１２は早期到着のためのバイパスオメガ網の構造を示したものである。図１２を参照すると、このバイパスオメガ網１２００は図６の網６００の構成に比べて、第２段ＳＴＧ１２０２から導出される出力アクセス点を備えている。数２より増加した出力アクセス点の数が１つである時、アドレスｓn-1ｓn-2．．．ｓ1の入力モジュール（後で説明される）はアドレスｄn-1ｄn-2．．．ｄ1の目的地へ向かうパケットの相対的距離を調べる。入力モジュールはアドレスｓn-1ｓn-2．．．ｓ1の左側から右側にアドレスｄn-1ｄn-2．．．ｄ1をシフト（shift）させる。そして、ｄn-1ｄn-2．．．ｄn-dr-aとｓnrｓnr-1．．．ｓ1が同一になる最大数ｄrを計算する。続いて、入力モジュールはｄrをパケットのルーティング回数Ｎrouteに設定する。そうすると、パケットはｎ−ｄr番目段を通過する時、自身の目的地に到達するようになる。
【００５５】
段の数を減らすための他の方法としてはスイッチング素子の大きさを増加させる方法がよく知られている。従来のオメガ網で、スイッチング素子の大きさはqrの対象に対するｑのシャフルを投入することにより増加することができる。(J. H. Patel, "Performance of processor-memory interconnections for multiprocessors", IEEE Transactions on Computers, C-30(10):771-780, October 1981参照）ここで、ｑ及びｒは２の累乗整数(power interger)である。例えば、64×64オメガ網が４×４スイッチング素子で構成されると、オメガ網の総段数はlog4 64 である。相互接続は６４個のポートの４シャフルにより構成される。すなわち、６４のポートを１６ポートずつ４つの束ねで割り、最上位非接続されたポートを次のスイッチング素子の入力ポートに接続する。このような構造によりバイパス接続を行なうと、網は本発明のバイパスオメガ網になる。このように、スイッチング素子の大きさを増加させると、網の段数を非常に減らすことができる。
【００５６】
〈出力バッファリング方式を備えたバイパスオメガパケットスイッチシステム〉図１３はスイッチング網として本発明のバイパスオメガ網を使用して出力バッファリング方式を採用したパケットスイッチシステムを簡略して図示したものである。パケットスイッチシステム1300は入力モジュール1310，バイパスオメガ網1320、MRN 発生ロジック1330、そして出力モジュール1340を具備している。入力モジュール1310は伝送ライン1301からパケットを受け入れる。各入力モジュール1310は、前に説明したように受信したパケットに必要な情報を付加してスイッチングパケットに変換する。また、各入力モジュールはアドレス解釈に必要な動作やプロトコル終了と関連した他の動作を遂行することができる。MRN 発生ロジック1330は各段へMRN(s)を供給する。このパケットスイッチシステム1300のためのスイッチングパケットのフォーマットが図１４に図示されている。
【００５７】
図１４を参照すると、スイッチングパケットは活性ビットフィールド、ルーティングタグフィールド、ルーティング回数（すなわち、経路選択された段の数）Ｎroute フィールド、年齢(age) フィールド、そして、データフィールドで構成される。年齢フィールドはパケット無秩序問題(packet disordering problem)を最小化させるための付加されたものである。このパケット無秩序は競争関係にあるパケット間の年齢フィールドを比較することにより、各スイッチング素子からのパケット順序を維持するにより、防止したり緩和することができる。例えば、バイパスオメガ網1320内の各スイッチング素子1321は小さい入力バッファ（後で説明される）を持っているが、このバッファ内でパケットは数多くのタイムスロット(time-slots)で遅延される可能性がある。ここで、タイムスロットというのはパケットスイッチングシステム内の相互接続配線の１つの地点でパケットを通過させるのにかかる期間(duration)を言う。２つのパケットが１つのスイッチング素子に同時に到着した場合でも、その中のある１つが他の１つよりまず先にそのスイッチング素子を離れる場合が発生することがある。このようなスイッチング素子からの可変的な遅延は無秩序問題と呼ばれる。内部バッファリング方式を使用してもこのような問題を克服することができない。この無秩序問題は、入力モジュールによりパケットがバイパスオメガ網に供給された時間から、スイッチングシステムで消費されたタイムスロット数を計算(count) する‘年齢フィールド’を投入することにより、緩和することができる。
【００５８】
年齢フィールドのビット幅はシステム内の帯域幅(bandwidth) を最小化するためにｎビットに制限される。ルーティング数(Nroute ) フィールドの最大ビット幅がｎであるので、Ｎroute フィールドの最小ビット幅はＮ×Ｎパケットスイッチシステムから経路選択される段の数を示すlog2n である。
【００５９】
パケットがｎのルーティング段を通過すると、出力モジュール1340に排出され、次の段では到着されたパケットが廃棄される。このような動作が容易に成立するようにするため、パケットがアイドルパケット(idle packet) であるか、あるいは活性パケット(active packet) であるかを示す到着ビット(arrived bit) を活性ビットの次に位置する。相互接続配線1302に接続された出力モジュール1340はパケットを横取りして、次の段のスイッチング素子のパケットの到着ビットが‘１’である時、そのパケットを廃棄する。しかし、出力モジュールは次の段のスイッチング素子のパケットの到着ビットが‘０’である時はそのパケットを廃棄しない。
【００６０】
このパケットスイッチシステムで、スイッチングパケットの長さは一定であるが、各フィールドでパケットはスイッチング段を通じて進行することができる。一般的に、ルーティングタグが１ビットずつ右側にシフトされることにより、各ルーティング段の各スイッチング素子が同一位置のビットによりパケットを経路選択することができる。パケットの偏向のためには、次の段からパケットが再出発できるように（全体のルーティングタグを）変更しなければならない。従って、ルーティングタグはスイッチング網全体で一定でなければならない。しかし、各段からのルーティングビットは経路選択された段の番号と共にいつでも抽出することができる。
【００６１】
出力バッファリング方式を持つパケットスイッチシステムのスイッチング素子1321は図１５に図示したように、各入力ポートに対して内部バッファリングを遂行するいわば‘テールスペアードバッファ(tail-spared buffer)’と呼ばれる入力バッファ1501を具備している。テールスペアードバッファ1501はFIFO(first-in first-out)として動作し、Ｂs のパケットを格納することができる。パケット 150１の最後尾空間は出力バッファリングのために次のタイムスロットに到着するかもしれないパケットのためにいつも空いている状態にする。あるスイッチング素子がパケットを次の段へあるいは出力モジュールに伝送する前に、そのスイッチング素子が次の段のスイッチング素子内のテールスペアードバッファ1501のその空間が空いているかどうかを調査しない。このようなスイッチング素子の動作は、入力ポート制御器(input port controller)1502 及び優先順位仲裁器(central priority arbitrator)150３の動作による。
【００６２】
入力ポート制御器1502は、まず、順位仲裁器1503の助けを受け、入力ポートからパケットを受け入れ、格納したりマルチプレックサ1504を通じて出力ポートにパケットを経路選択する。図１６は入力ポート制御器1502の動作を示すフローチャートである。図１６を参照して、任意のタイムスロットで、入力ポート制御器1502はパケットを受け入れる（段階、S160１）。HOL(head of line) パケットの受信が完了されると、制御器1502はアクセスできるルーティングポートが存在するかを調査する（段階、S1602 ）。この段階で、アクセスができるルーティングポートが存在すると、フローは段階S1603 に進行する。この段階では、入力ポート制御器1502がHOL パケットのルーティング回数Ｎroute を１増加させた後、パケットを経路選択する。段階S1602 で、アクセスできるルーティングポートが存在しない場合、フローは段階S1604 に進む。この段階では、制御器1502が対応するバッファ1501の状態が充満(full)であるかを調べる。この時、そうでなければ、パケットはバッファ1501に格納される（段階S1605 ）。段階S1604 で、バッファが充満状態にあると、フローは段階S1606 に進む。この段階で、制御器1502は受信されたHOL パケットが通過可能なパケットであるか、またアクセス可能なバイパスポートが存在するかを調べる。この時、‘ＹＥＳ’であると、HOL パケットは通過処理される（段階、S1607 ）。段階S1606 で‘ＮＯ’であると、フローは段階S1608 に進む。この段階では制御器1502は受信されたHOL パケットが偏向可能なパケットであるか、またアクセス可能なルーティングポートが存在するかを調べる。この時、‘ＹＥＳ’であると、HOL パケットは偏向処理される（段階、S1609 ）。段階S1608 で‘ＮＯ’であると、HOL パケットは廃棄される（段階、S1610 ）。
【００６３】
１つのスイッチング素子内で、３つの入力ポート制御器１５０２は各々独立的にルーティング、通過、偏向及び格納動作の中のいずれかを実行する。優先順位仲裁器１５０３は制御器１５０２に対して仲裁を遂行する。各入力ポート制御器１５０２はＨＯＬパケットの伝送方向、そのパケットが通過可能であるかの可否に対した情報、そのパケットの年齢及びルーティング回数（Ｎroute）フィールドを優先順位仲裁器１５０３に伝送する。決定手続きが終了し、受信するパケットの最後の部分が到着する前、優先順位仲裁器１５０３で選択された動作が始まる。このような動作を“仮想通過（virtual cut-through）”と呼ぶ。この仮想通過では、パケット全体データがまだ到着しなかったが、それの制御データが到着すれば、そのパケットは次の目的地に伝送される。年齢算出動作（aging operation）は毎タイムスロットごとに遂行される。それで、該当タイムスロットで、テールスペアードバッファに格納され、出力ポートへ伝送されないすべてのパケットはそれらの年齢フィールドに各々１が加えられて年齢（age）が高くなる。
【００６４】
優先順位仲裁器1503は同一なルーティングポートを獲得しようと競合する３つの入力ポート制御器1502にそれらの優先順位を決定する。図１７では、優先順位仲裁器1503は３つのHOL パケットが存在するかを調査する（段階、S170１）。この時、３つのHOL パケットが存在すると、フロー段階S170２へ進む。この段階では、仲裁器1503がすべてのパケットの伝送方向が同一であるかを調査する。もし、伝送方向が同一であれば、仲裁器1503は１つのパケットをルーティングさせ、他の１つのパケットを通過するようにし、余りの１つのパケットを偏向する。この時、一番多い年齢と一番大きいルーティング回数（Ｎroute ）を持つパケットがルーティングポートに伝送され、その次に多い年齢と目的地により近いパケットが次の段に通過する。段階S170２で、伝送方向が同一でないと、フローは段階S1704 に進む。この段階では、仲裁器1503は２つのパケットをルーティングし、余りの１つのパケットを通過する。
【００６５】
再び、段階S1701 で、３つのHOL パケットが存在していないと、フローは段階S1705 に進行して、２つのHOL パケットが存在するかが調査される。無ければ、フローは段階S1706 に進んで１つのパケットがルーティングされる。段階S1705 で、２つのHOL パケットがあれば、フロー段階S1707 に進行する。この段階では、２つの伝送方向が同一であるかが調査される。この時、同一方向でなければ、フローは段階S1708 に進行して２つのパケット全てがルーティングされる。段階S1707 で、同一方向であれば、フローが段階S1709 に進行して１つのパケットはルーティングされ、余りの１つのパケットは通過する。本発明のバイパスオメガ網で、偏向はMRN(s)が０であるスイッチング段だけである。もう一度言うと、偏向は網の前に位置した段だけで行なわれるが、通過は最終段を除いたどの段でも行なうことができる。
【００６６】
再び図１３に戻って、出力モジュール１３４０はバイパスオメガ網１３２０からパケットを受け入れる。各出力モジュール１３４０はタイムスロットでＫ個のパケットを同時に受け入れ、付加されたルーティング回数を除いた後、出力伝送ライン１３０３に伝達する。出力モジュール１３４０のＫ個の入力ポート１３４１の各々は、出力モジュールと同一なアドレスを持つ内部接続配線１３０２と接続される。各入力ポート１３４１はパケットフィルタ（図示されていない）を具備している。フィルタは到着ビットが１であるパケットを除く。また、出力モジュール１３４０Ｂ0のパケットを格納することができる共有バッファを持つ。この共有バッファは数多くのメモリブロック１３４２で構成される。パケット集中のため、よく知られているノックアウトスイッチ（Knockout switch）（Y. H. Yeh, et al., "The Knockout Switch: A simple, Modular Architecture for High-Performance Packet Switching", IEEE Journal on Selected Area in Communications, SAC-5(8):1274-1283, October 1987参照）の集中器（concentrator）が使用される。
【００６７】
HOL 問題にもかかわらず、入力バッファリング方式に比べて、いろいろな長所を持つ。ラインのヘッドから、すなわち入力バッファの前端でパケットの待機が長くなることを避けられる良好な性能のスイッチング網を使用するにより、HOL 問題を処理することができる。このような入力バッファリングはスイッチング段のどこかで、損失するパケットによりスイッチング資源(switching resource)が浪費されることを許さない。一般的に、高品質のフロー制御を遂行する場合、出力バッファリングより入力バッファリングがより適切なことが知られている。また、純粋出力バッファリングではパケット損失を減らすためにむしろ大容量スイッチング構造(large switching fabric)が必要であるが、入力バッファリングでは入力トラフィックの調定(input traffic shaping) によりスイッチング構造の複雑性を減らすことができる。その上、入力バッファリング方式では、プロトコル終了、アドレス解釈、ルーティング回数の追加などのための高密度メモリチップがすでに製造されているので、低廉な費用で大容量入力バッファを構成することができる。それにもかかわらず、各出力に対した多重出力アクセス点が提供されないと、スイッチング構造が急激に混雑になり、スループットが深刻な影響を受けるので、高いスループットを得るためには出力バッファリングの採用が不可欠である。
【００６８】
〈入力及び出力バッファリング方式を持つオメガパケットスイッチシステム〉
図１８はスイッチング網として本発明のバイパスオメガ網を使用し、入力及び出力バッファリング方式を採用したパケットスイッチシステムを示している。図示されたパケットスイッチシステム1800は入力モジュール1810、バイパスオメガ網1820、MRN 発生ロジック1830、そして、出力モジュール1840を具備している。このシステム1800は、図１３のシステム1300とは異なり、共有された入力通過リンク1802を持っている。入力バッファリングを遂行するために、各スイッチング素子1821はそれの内部バッファが充満状態である時、パケットが過度に到着することを防ぐためのバックプレシング(back-pressing) 信号を発生する。たとえば、図１８にはバックプレシング信号が図示されており、各スイッチング素子1821及び出力モジュール1840はバックプレシング信号を発生する。
【００６９】
入力モジュール1810の一般的な動作は図１３の出力バッファリングパケットスイッチシステム1300のそれと類似する。しかし、入力モジュール1810は大きさＢi のバッファを具備し、スイッチングパケットを伝送する前に一番目のスイッチング段から次のスイッチング素子が空間を持っているかの有無を調査する。各入力モジュールは近接なスイッチング素子と通過入力リンク1802を共有する。要するに、奇数番目のモジュールは奇数番目タイムスロットで入力リンク1802を使用し、偶数番目モジュールは偶数番目タイムスロットで入力リンク1802を使用する。各入力モジュールはバッファ占有水準が５０％を超過する場合、入力バッファ水準を急速に低くするためにこの共有された通過リンクを使用する。バイパスオメガ網1820で解釈されるスイッチングパケットのフォーマットは図１４に図示された出力バッファリングパケットスイッチシステムのそれと同一である。しかし、ルーティング回数Ｎroute が０ではない時、このパケットシステム1800では偏向が許容されないので、（後で説明される）、前で説明した出力バッファリングパケットスイッチシステム1300のようにルーティングタグが固定されることはない。
【００７０】
図１８に図示したパケットスイッチシステムのスイッチング素子1821は、図１９に図示したように、各入力ポートにおけるバッファリングを遂行するための入力バッファ1901を持つ。しかし、バッファ1901は図１５に図示されたスイッチング素子のテールスペアードバッファとは異なる。各スイッチング素子1821の内部バッファ1901は図１９に図示したようにバックプレシング信号(FULL)をセットすることにより、システムに対する‘バックプレシャ（backpressure) ’を遂行する。また、各スイッチング素子1821は接続配線によりスイッチング素子に接続された次の段のスイッチング素子と出力モジュールからFULL信号を受け入れる。スイッチング網1820で、スイッチング素子1821の入力バッファ1901がオバーフローになる時を除いてはパケットは廃棄されない。
【００７１】
このシステム1800で使用されるスイッチング素子1821の動作は入力ポート制御器1902及び優先順位仲裁器1903の動作で簡単に説明することができる。入力ポート制御器1902は、優先仲裁器1903により、入力ポートからパケットを受け入れ、格納したり、マルチプレックサ1904を通じて、出力ポートにパケットを経路選択する。図２０には入力ポート制御器1902の動作が図示されている。
【００７２】
図２０を参照すると、任意のタイムスロットで、入力ポート制御器１９０２はパケットを受け入れ始める（段階、Ｓ２００１）。ＨＯＬパケットの受信が完了すると、制御器１９０２はアクセス可能なルーティングポートが存在するかを調査する（段階、Ｓ２００２）。この段階で、アクセス可能なルーティングポートが存在すると、フローは段階Ｓ２００３に進行する。この段階では、入力ポート制御器１９０２がＨＯＬパケットのルーティング回数Ｎrouteを１増加させ、ＦＵＬＬ信号をリセットさせ、ルーティングタグを左側にシフトさせた後、ＨＯＬパケットを経路選択する。段階Ｓ２００２で、アクセス可能なルーティングポートが存在しないと、フローが段階Ｓ２００４に進行する。この段階で、制御器１９０２は受信したＨＯＬパケットが通過できるパケットであるか、またアクセス可能なバイパスポートが存在するかを調べる。この時、ＹＥＳ'であると、ＦＵＬＬ信号はリセットされ、ＨＯＬパケットは通過処理される（段階Ｓ２００５）。段階Ｓ２００４で、ＮＯ'であると、フローは段階Ｓ２００６に進行する。この段階では、制御器１９０２が受信されたＨＯＬパケットが偏向できるか、そして、アクセスできるルーティングポートが存在するかを調査する。この時、ＹＥＳ'であると、ＦＵＬＬ信号はリセットされ、ＨＯＬパケットは偏向処理される（段階Ｓ２００７）。段階Ｓ２００６で、ＮＯ'であると、制御器１５０２は対応するバッファ１９０１の状態が充満であるかを調査する。この場合、ＹＥＳ'であれば、ＦＵＬＬ信号はセットされＳ２００９、ＮＯ'であれば、ＦＵＬＬ信号はリセットされる（段階Ｓ２０１０）。
【００７３】
図１５のスイッチング素子とは対照的に、このスイッチング素子ではルーティングタグが左側にシフトされる。従って、全てのスイッチング素子はルーティングタグの固定されたビットをルーティングビットとして考えることができない。これはパケットのルーティング回数Ｎroute が０である時だけに偏向を許可するからである。このようなシステムは各スイッチング素子のハードウェア複雑度を減らす。
【００７４】
優先順位仲裁器1903の動作は図１５に図示された仲裁器1503のそれと類似する。しかし、この仲裁器1903はFULL信号が０である時だけにルーティング、通過及び偏向処理を許可する。万一、あるパケットがルーティングによりスイッチング素子を通過した後に自分の目的地に到達すると、スイッチング素子は出力モジュールから供給されるFULL信号により出力バッファに空きが有るか否かを調査しなければならない。
【００７５】
再び、図１８を参照して、出力モジュール1840はB0のパケットを格納することができる共有バッファを持つ。この出力モジュール1840の動作はバックプレシング信号FULLを除いては、図１３に図示された出力モジュール1340のそれと同一である。共有バッファの残余空間がｋ（＜ｋ）である時には、出力モジュール1840に接続された一番目のｋのスイッチング段が出力モジュールにパケットを伝送することができる。
【００７６】
次は、図１３及び図１８に各々図示された２つのバイパスオメガスイッチシステムと従来のタンデムベニアン及びリルーティングスイッチシステムとの比較をコンピュータシミュレーションにより説明する。
【００７７】
〈内部バッファリング方式を持たないバイパスオメガスイッチシステムの性能〉図２１はテールスペアードバッファのサイズＢS が１であり、入力付加（Ｐ）が可変される時、出力アクセス点の数によりパケット損失率を見せている。図２１で、本発明のバイパスオメガ網は内部バッファを具備していないし、出力バッファリング方式を持つ。リルーティング網より本発明のバイパスオメガ網はパケット損失率がより早く減少する。そして、入力付加（Ｐ）が減少すると、リルーティング網からよりバイパスオメガ網でパケット損失率の差がより早く減少する。しかし、必要なアクセス点の数は１０のバッファサイズ（Ｂr ）の再循環バッファを持つタンデムベニアン網で一番小さい。
【００７８】
図２２は入力負荷が変わるとき、段の数によるパケット損失率を見せている。もう一度言うと、図２１は同一パケット損失率に対する総段数を見せている。図２１及び図２２を参照すると、タンデムベニアン網が一番小さい出力アクセス点を必要とする反面、これは一番大きい段数を必要とする。リルーティング網は一番大きい数の出力アクセス点を必要とし、大きい数の総段数を必要とする。しかし、本発明のバイパスオメガ網は従来の網に比べて、小さい数の出力アクセス点及び段数を必要とする。
【００７９】
〈出力バッファリング方式を持つオメガスイッチシステムの性能〉
このシミュレーション結果を得るために、各出力ポートに均一に向くベルヌイトラッフィックソース(Bernoulli traffic source)及び1024×1024パケットスイッチシステムが使用された。図２３は各出力ポートに均一に向くベルヌイトラッフィックソースを持つ出力アクセス点の数によるパケット損失率を見せている。テールスペアードバッファのサイズＢs が１である場合、本発明のスイッチシステムでは出力アクセス点が１８である時、最大スループットが１であるが、リルーティング網では最大アクセス点が３３である。バイパスオメガ網では、テールスペアードバッファサイズＢs が増加すると、最大スループットが急速に１になる。バッファサイズＢs １で２に増加させる時、利益が一番大きい。テールスペアードバッファサイズＢs が１である時、バッファが次のタイムスロットから到着するかもしれないパケットのために自分の空間をいつも空けておくので、本発明のバイパスオメガ網は内部バッファを持たないことと同じになる。図２３からバッファサイズＢs がたとえ１としても本発明のバイパスオメガ網が採用される場合には段の数を非常に減らすことが知られる。しかし、内部バッファリング方式を用いると、段数をより多く減らすことができる。
【００８０】
図２４は各出力ポートに均一に向くベルヌイトラッフィックソースを持つ総段の数によるパケット損失率を見せている。入力ポート数Ｎが増加することにより、総段数の始め番号が増加し、パケット損失率も増加する。同一な性能を得るためには、段の数を増加することは直観的に知られている。その理由はＮが増加すればするほど、内部衝突がより多く発生されるからである。
【００８１】
図２４のｘ−軸目盛りを出力アクセス点の数にすると、図２５と同じになる。図２５は各出力ポートに均一に向くベルヌイトラッフィックソースを持つ出力アクセス点の数によるパケット損失率を見せるグラフとして、Ｎが増加する時、必要な段の数が増加することをより明確に示している。
【００８２】
図２６はＢs が変わる時、各出力ポートに均一に向くベルヌイトラッフィックソースを持つ段の数によるパケット損失率を示している。図２６を参照すると、１５個の段から構成される1024×1024バイパスオメガスイッチシステムにおいて、スイッチング素子内の各バッファのサイズＢs が８であり、出力バッファのサイズが800 であり、入力トラッフィック負荷が0.9 である時、10-8のパケット損失率が得られた。これは同一なパケット損失率(10 -8 )を得ることに必要な段の数が約55であるリルーティング網と比較して、顕著な差を示している。
【００８３】
〈入力及び出力バッファリング方式を持つバイパスオメガスイッチシステムの性能〉
このシミュレーション結果を得るために、１０のバスティニス(burstiness)を持つ２進数トラフィックソースが使用され、性能比較のために従来の網にも同一なトラフィックソースが適用された。
【００８４】
図２７はシステムの入力ポート数Ｎが１２８であり、入力バッファサイズＢi が１００であり、出力バッファサイズＢ0 は制限せず、スイッチング素子の各入力バッファのサイズＢs が８である時、段の数による最大スループットを示している。図２７に図示したように同一なスループットの従来のシステムに比べて、本発明のバイパスオメガシステムはもっと小さい段となる。
【００８５】
図２８は入力トラフィック負荷が0.8 であり、出力バッファサイズＢ0 が可変の時、段の数によるパケット損失率を示している。段の数が１０以上になると、本発明のバイパスオメガ網のパケット損失率は出力バッファサイズを減らすことにより、非常に大きく減少する。だが、リルーティング網とタンダムベニアン網では、出力バッファサイズを増加しても、段の数が３２になる時まではほとんどパケット損失率の減少効果を得られない。このようなパケット損失は主に２つの理由、すなわち、スイッチング構造(switching fabric)からのルーティング経路の不十分及びバッファのオーバフローに起因する。図２８で、段の数が３２を超過し、出力バッファサイズＢ0 が500 である場合には、急激なトラッフィック増加により出力バッファがオーバフローするので、リルーティング網のパケット損失率は飽和状態になる。リルーティング網で、段の数が３２を超すまでは、不十分なルーティング経路により、その網のパケット損失率を減らすことが難しい。図２８に図示したように、出力バッファサイズＢ0 を500 、入力バッファサイズＢi を100 、スイッチング素子の各入力バッファサイズＢS を８とした場合、本発明のバイパスオメガ網は１１個の段だけを持つとしても10-6のパケット損失率を得ることができる。
【００８６】
図２９は等価ハードウェア複雑度によるパケット損失率を示している。リルーティング及びタンデムベニアン網の基本スイッチング素子が２×２スイッチングを遂行するに反して、本発明のバイパスオメガ網のスイッチング素子は３×３スイッチングを遂行する。各基本スイッチング素子のハードウェア複雑度は素子の入力ポートの数と出力ポートの数のかけ算で簡単に示すことができる。図２９は図２８から基本スイッチング素子ハードウェア複雑度の比、すなわち、（３×３）／（２×２）（＝２．２５）に本発明のバイパスオメガ網の段数を計算(scaling) するにより得られた。図２８はパケット損失率が10-3以下である領域で従来のシステムに比べて、本発明のバイパスオメガスイッチシステムのハードウェア複雑度がより低いことを示している。
【００８７】
【発明の効果】
以上で説明したように、本発明のバイパスオメガ網は数多くのパケットが１つの目的地に到達するようにする多重出力アクセス点を持つ。また、このバイパスオメガ網で必要な段の数が従来のリルーティング及びタンデムベニアン網のそれに比べて、非常に減少するので、このバイパスオメガ網の総接続配線数は従来の網のそれより小さい。その上、このバイパスオメガ網はそれの運用中に障害段が検出された場合でも、故障した段をオンライン除去ができるので、網の維持補修が容易であり、高品質のサービスを提供できる。
【図面の簡単な説明】
【図１】２つの完全シャフル接続が発生する従来のオメガ網の構成を示すブロック図。
【図２】図１に図示された網の自己ルーティング特性を示すブロック図。
【図３】チップ種類の数を減らすためのシステムモジュール性の重要性を説明するための図。
【図４】故障許容的な動作のためのシステムモジュール性の重要性を説明するための図。
【図５】本発明によるバイパスオメガ網に使われるＭ×Ｍ基本スイッチング素子（例えば、Ｍ＝３）を示すブロック図。
【図６】本発明によるＮ×Ｎバイパスオメガ網（例えば、Ｎ＝８）の１つの実施の形態を簡単なブロック図で示した図。
【図７】図６に図示された網のルーティング原理を説明するための図。
【図８】本発明によるバイパスオメガ網でスイッチングされるパケットのフォーマットの一例を見せる図。
【図９】本発明によるバイパスオメガ網において、正確なルーティング経路及び、過度バイパスによる不正確なルーティング経路を例示する図。
【図１０】本発明によるバイパスオメガ網の偏向動作を説明するための図。
【図１１】本発明によるバイパスオメガ網の故障許容性を説明するための図。
【図１２】本発明によってバイパスオメガ網の他の実施の形態を簡単なブロック図で示した図。
【図１３】スイッチング網として本発明のバイパスオメガ網を使用して出力バッファリング方式を採用したパケットスイッチングシステムを簡単なブロック図で示した図。
【図１４】図１３のスイッチシステムのためのパケットのフォーマットを見せる図。
【図１５】図１３のスイッチシステムで使用されるスイッチング素子の構成を示すブロック図。
【図１６】図１５に図示した入力ポート制御器の動作を示すフローチャート。
【図１７】図１５に図示した優先順位仲裁器の動作を示すフローチャート。
【図１８】スイッチング網で本発明のバイパスオメガ網を使用し、入力及び出力バッファリング方式を採用したパケットスイッチシステムを簡単なブロック図で示した図。
【図１９】図１８のスイッチシステムで使用されるスイッチング素子の構成を簡単なブロック図で示した図。
【図２０】図１９に図示された入力ポート制御器動作を示すフローチャート。
【図２１】バッファサイズＢS が１であり、入力負荷が可変される時、出力アクセス点の数によるパケット損失率を示すグラフ。
【図２２】入力負荷が可変される時、段の数によるパケット損失率を示すグラフ。
【図２３】出力バッファリングパケットスイッチシステムで、各出力ポートに均一に向くベルヌイトラフィックソースを持つ出力アクセス点の数によるパケット損失率を示すグラフ。
【図２４】出力バッファリングパケットスイッチシステムで、各出力ポートに均一に向くベルヌイトラフィックソースを持つ総段の数によるパケット損失率を示すグラフ。
【図２５】出力バッファリングパケットスイッチシステムで、各出力ポートに均一に向くベルヌイトラフィックソースを持つ出力アクセス点の数によるパケット損失率を示すグラフ。
【図２６】出力バッファリングパケットスイッチシステムで、ＢS が変わる時、各出力ポートに均一に向くベルヌイトラフィックソースを持つ数によるパケット損失率を示すグラフ。
【図２７】入力及び出力バッファリングパケットスイッチシステムで、段の数による最大スループットを示すグラフ。
【図２８】入力及び出力バッファリングパケットスイッチシステムで、段の数によるパケット損失率を示すグラフ。
【図２９】入力及び出力バッファリングパケットスイッチシステムで、等価ハードウェア複雑度によるパケット損失率を示すグラフ。
【符号の説明】
1310    入力モジュール
1320    バイパスオメガ網
1330    ＭＲＮ発生ロジック
1340    出力モジュール
【図１】
0003874922.tif 000002
【図２】
0003874922.tif 000003
【図３】
0003874922.tif 000004
【図４】
0003874922.tif 000005
【図５】
0003874922.tif 000006
【図６】
0003874922.tif 000007
【図７】
0003874922.tif 000008
【図８】
0003874922.tif 000009
【図９】
0003874922.tif 000010
【図１０】
0003874922.tif 000011
【図１１】
0003874922.tif 000012
【図１２】
0003874922.tif 000013
【図１３】
0003874922.tif 000014
【図１４】
0003874922.tif 000015
【図１５】
0003874922.tif 000016
【図１６】
0003874922.tif 000017
【図１７】
0003874922.tif 000018
【図１８】
0003874922.tif 000019
【図１９】
0003874922.tif 000020
【図２０】
0003874922.tif 000021
【図２１】
0003874922.tif 000022
【図２２】
0003874922.tif 000023
【図２３】
0003874922.tif 000024
【図２４】
0003874922.tif 000025
【図２５】
0003874922.tif 000026
【図２６】
0003874922.tif 000027
【図２７】
0003874922.tif 000028
【図２８】
0003874922.tif 000029
【図２９】
0003874922.tif 000030