JPH01502380A - 出力コンフリクト解決手段を有するバッチャーバンヤンパケットスイッチ - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 出力コンフリクト解決手段を有する バッチャーバンヤンパケットスイッチ 発明の分野 本発明はバッチャーバンヤン回路網のような内部非阻止パケットスイッチ回路に 関し、詳細には同一のパケットスイッチサイクルにおいてデータパケットを同一 の出力ポートに伝送しようとする回路網の入力ポート間のコンフリクトを解決す るメカニズムに関する。

発明の背景 広帯域の回路サービスを行うに重要な要素は多数の加入者ラインを相互に接続す ることの出来る大容量パケットスイッチ回路である。

そのようなパケットスイッチ回路はｉ個の入力ポート（ｉ−１，２，３，・・・ Ｎ）およびｊ個の出カポ−）（ｊ−１，２，３，・・・Ｎ）を有する。一般にそ のようなパケットスイッチ回路は同期する。１つのパケットスイッチサイクル中 、ｉ個の入力ポートのパケットはパケットスイッチを介してｊ個の出力ポートの 特定のものに送られる。詳細にはパケットスイッチサイクルにおいて、各入力ポ ート１は１つのパケットを成る１つの出力ポートｊに送ろうとする。

パケットスイッチ回路はそのよ、うな要求を出すすべての入力ポートｉについて 出力ポートｊが個別となっているときすべてのパケットを入力ポートｉから要求 された出力ポートｊに分配出来るならば内部的には非阻止である。しかしながら 内部的に非阻止のスイッチ回路は同一出力ボートについて２つの同時的な要求が あれば阻止を行う。この場合、同一の出力ポートに送られた一方または両方のパ ケットが阻止されあるいは破壊される。このように内部的非阻止パケットスイッ チ回路内の出力ポートのコンフリクトを解決するための機構が必要である。

内部的非阻止パケットスイッチ回路の一例がバッチャーバンヤン回路であり、こ れはバッチャ−ソート回路とそれに続くバンヤンルート回路からなる。バッチャ ーバンヤン回路はジェー・デー・ウルマン「コンビ二−テーシジナルＱアスペッ ク・オブーＶＳＬＩＪコンビニータサイエンスプレス、１９８５．ページ２３９ ，２４０およびニー・ファン他「スターライト・ア・ワイド・バンド・ディジタ ル・スイッチＪ１９８４グローブコムコンフェレンス議事録に詳細に述べられて いる。

バッチャーバンヤン回路はパケットを特定の入力ポートから特定の出力ポートへ 、パケットヘッダ内の宛先アドレスにもとづき方向づける自己ルート回路である 。内部的非阻止データパケット伝送はまずパケットをバンヤン回路に向ける前に ソータ回路（例えばバッチャ−回路）内の宛先アドレスに従って非減少順でパケ ットを区分けすることにより行われる。バンヤン回路はこのパケットをパケット ヘッダに含まれる特定の出力ポードアドレスに方向づける。不都合なことに２個 以上のパケットが与えられた任意のパケットスイッチサイクルにおいて１つの特 定のバンヤン出力ボートに宛られるとこのバッチャーバンヤン回路に阻止が生じ る。

そのような出力ポートのコンフリクトを解決するための一つの特別な方法が前記 のファン他の文献で示されており、これはスターライトスイッチに着目するもの である。スターライトスイッチではバッチャ−ソート回路とバンヤンルート回路 を通りパケットが方向づけられる。

バッチャ−回路は宛先アドレスに従って非減少順にパケットを区分けするように 作用する。バンヤン回路の出力に夫々の出力ポートに宛てられた、１個のみのパ ケットが排除され、それ故その排除後には固有の宛先アドレスをもつパケットの みが残る。その結果、バッチャ回路の出力でのパケット宛先アドレスは増加順と なるが排除されたパケットによるシーケンスの穴を併う。穴をもつこのシーケン スは次のバンヤン回路にパケット発振を生じさせることがある。その結果、排除 されたパケットにより生じた穴を埋めるためにトップに向けてすべてのパケット にスキニーをつけるためにバンヤン回路の前段に集中回路が必要になる。そのよ うな集中回路は、バッチャ回路の１つの出力ライン上のパケットの数を計算する ようなむしろ複雑な動作を行う。一般に、集中回路はノードの数としてみるとバ ンヤン回路の程度に複雑である。

スターライトスイッチでは排除されたパケットを分配するために、排除されたパ ケットはバッチャソート回路の出力からスイッチの、排除されたパケットの再加 入用に特につくられたいくつかの入力ポートへと向けられる。

再加入用の入力ポートの数を減らすために、排除されたパケットは集中回路を通 る。

このように、上記の出力ポートのコンフリクト解決法は次のような欠点をもつ。

まず、入力ポートの半分以上がパケットの再入のために用いられる。更に残りの 入力ポートは過度のパケット損を防ぐため約４０％以下の負荷率とならねばなら ない。スターライトスイッチは２個の集中回路とそれらに関連するチップ群およ びサブシステム設計を必要とする。最後に、パケットはスターライトコンフリク ト解決法を用いて無秩序に分配される。

従って、本発明の目的はバッチャーバンヤン回路のような内部的非阻止パケット スイッチ回路内の出力ポートのコンフリクトを解決するための簡単で効率の高い 手段を提供することである。

発明の要約 本発明はバッチャーバンヤン回路のような内部的非阻止パケットスイッチ回路に おける出力ボートコンフリクトを解決する方法である。云い換えると、本発明は 同一のスイッチサイクルにおいて同一の出力ポートにデータパケットを伝送しよ うとする入力ボート間のコクフリクトを解決するために用いることが出来る。本 発明の図に示す実施例では、各バッチャーバンヤンパケットスイッチサイクルが ３つの相に分けられる。第１の相は仲裁相であってそこでは出力ホートコクツリ フトが解決される。

第２の相において、この仲裁相の結果が優勢な入力ポートに送られる。第３の相 はデータパケット伝送ボートであり、ここでは優勢入力ボートからのデータパケ ットがバッチャーバンヤン回路を実際に通される。

仲裁相においてはデータをバッチャーバンヤン回路を通してデータパケットを伝 送しようとする各入力ポートがまずバッチャ−ソート回路を通じて出力ポートリ クエストパケットを伝送する。各リクエストパケットはリクエストパケットの発 生についての入力ポートを示す入力ポードアドレスと、入力ポートがデータパケ ットを伝送しようとする宛先を示す出力ポードアドレスから成る。

バッチャ−ソート回路はリクエストされた宛先に従って非減少順でリクエストポ ケットを区分けし、それによりエストが容易に排除出来る。第２の確認相におい てはこの仲裁の結果が優勢な入力ポートに連絡される。各優勢リクエストパケッ トの入力ポードアドレスからなる確認パケットがバッチャ−回路の出力から優勢 リクエストパケットの発生の入力ポートにもどるように方向づけられる。この確 認パケットのルートは集中回路のような付加的回路を用いることなくバッチャー バンヤン回路自体を用いて与えられる。

データパケット伝送相において、このようにして確認された入力ポートがそれら のデータパケットをバッチャーバンヤン回路を通してコンフリクトを伴うことな く宛先の出力ポートに送る。確認されない入力ポートは少くとも次のパケットス イッチサイクルまでそれらのパケットをバッファする。

本発明の出力ボートコンフリクト解決機構は上述の従来のコンフリクト解決機構 より著しく簡単である。特に、集中回路のような複雑なハードウェアの使用は省 略出来る。

図面の簡単な説明 第１因、第２図および第３図は本発明の一実施例による、バッチャーバンヤン回 路での出力ポートコンフリクトを解決するための３相法を概略的に例示する。第 ４図および第５図は本発明の一実施例を実行するための回路を概略的に例示して いる。

第６図は本発明の他の実施例による、バッチャーバンヤン回路における出力ポー トコンフリクトを解決するための方法および装置を概略的に例示している。

詳細な説明 第１．２および３図はバッチャーバンヤン回路１０における出力ホートコクツリ フトを解決するための３相法を概略的に例示している。第１，２および３図に示 すように、バッチャーバンヤン回路１０はバッチャ−ソート回路１２とバンヤン ルート回路１４から成る。回路１０は４個の入力ポートｉ−１，２，３，４と４ 個の出カポ−）ｊ−１，２，３，４を有する。バッチャ−回路の出力はに−１， ２，３，４で示しである。（４入力ポートと４出力ポートは例示のためのみのも のである。）バッチャ−回路は各パケットのフロントに組込まれたヘッダに含ま れるアドレスに従って非減少順に入来パケットを並べるように作用する。バンヤ ン回路はバッチャ−回路の出力におけるパケットをパケットヘッダに示される特 定の出力ポートｊにルートづけるように作用する。

バッチャーバンヤン回路１０は同期している。本発明においては出力ポートのコ クフリクトを解決するために、各バッチャーバンヤンパケットスイッチサイクル は３つの相に分けられる。第１の相（第１図に示す）は仲裁相であり、そこでは データパケットを同一の出力ポートに方向づけようとする入力ボート間のコンフ リクトが解決される。第２相（第２図に示す）は確認相であって、そこでは優勢 入力ボートに仲裁相の結果が知らされる。第３相（第３図に示す）はデータ伝送 相であって、そこではデータパケットがバッチャーバンヤン回路を通るようにル ートづけされる。

第１図において、入力ポートｉ”−１，２，３，４の夫々はバッチャーバンヤン 回路１０を通じて１つの特定の出力ポートｊにルートづけしようとするデータパ ケットを有する。この特定宛先の出力ポートｊは各データパケットの前端のデー タパケットヘッダ内のアドレスにより示される。このように、入力ポート１のデ ータパケットは出力ポートｊ−３にルートづけされるべきである。同様に、入力 ポート２．　３．４のデータパケットは出力ポートｊ−１，４，３に夫々ルート づけされるべきである。

入力ポートｉ−１，４がそれらのデータパケットを出力ポートｊ−３にルートづ けたいのであるからこれら入力ボート間にはコンフリクトがある。そのようなコ ンフリクトは上に要約した３相法に従って解決される。

第１相において、各入力ポートはバッチャ−ソート回路１２を通してリクエスト パケットをルートづける。各入力ポートによりルートづけされるリクエストパケ ットは一対のアドレスを含んでいる。第１アドレスは出力ポートｊであり、これ に入力ポートがそのデータパケットを送ろうとするものである。第２アドレスは 入力ボート自体のアドレスｉである。このように、各リクエストパケットは宛先 アドレスとソースアドレスの対Ｊ＋　１を含む。かくして、例えば入力ポートｉ −１からのリクエストパケットはアドレス対ｊ　−３，ｉ−１からなる。同様に 、入力ポートｉ−２のリクエストパケットはアドレス対ｊ−１，ｉ−２を有する 。第１図に示すように、リクエストパケットはバッチャ−ソート回路により区分 けされ、それにより、バッチャ−ソート回路の出力において、リクエストパケッ トは宛先アドレスに従って非減少順に区分けられる。このように、バッチャ−ソ ート回路はコンフリクトするリクエストを隣同志として重複リクエストの排除を 隣接するバッチャ−出力での宛先アドレスを比較することにより行う。バッチャ −出力にでの宛先アドレスがバッチャ−出力に−１での宛先アドレスに等しいと きはこのリクエストパケットは出力ボートコンフリクトの解決のため排除される 。このように、第１図において、バッチャ−出力に−３でのリクエストパケット が排除されるのであり、その理由はそれがバッチャ−出力に−２のリクエストパ ケットと同一の宛先、すなわち出力ポードアドレスを有しているからである。い ずれの場合でも宛先アドレスはｊ−３である。これは、入力ポートｉ−１のデー タパケットがこのバッチャーバンヤンサイクルにおいては伝送されないことを意 味する。これで仲裁相が終了する。

第２、すなわち確認相において、優勢な入力ポートに仲裁の結果が知らされる。

そのような確認はその優勢リクエストパケットの夫々のソースアドレス（すなわ ち入力ポードアドレス）部分を用いて行われる。このように、各優勢リクエスト パケットの入力ポードアドレス部分はそれが発生した入力ポートにもどされて仲 裁相において優勢であるとしてその入力ポートを確認する。第１図に示すように 、バッチャ−出力に−１において、入力ポードアドレスｉ−２が確認パケットを 形成する。同様に、バッチャ出力に−２での入力ポードアドレスｉ　−４が確認 パケットを形成し、出力に−４での入力ポードアドレスｉ−３が確認パケットを 形成する。バッチャ出力に−３はそこで０リクエストパケツトが仲裁相において 排除されたから確認パケットを形成しない。

各確認パケットは次にそれにより限定される入力ポードアドレスにもどされる。

これは、バッチャ−出力に−１での確認パケットが最終的に入力ポートｉ−２に ルートづけられることを意味する。同様にバッチャ−出力に−２，４での確認パ ケットは最終的に入力ポートｉ　−４゜１と夫々ルートづけられる。このルート づけは第２図のバッチャーバンヤン回路を用いて行われる。

確認パケットのルートづけは第２図に詳細に示しである。このルートづけの第１ 段階において、バッチャ−出力に−１，２，３，４は、ｋ−１がｉ−１に、ｋ− ２がＬ−２に接続され、以下同様となるようにバッチャ−人力ｉ−１，２，３， ４に接続する。ライン６、　７．８゜９は第２図におけるこれらの接続を示して いる。かくして第２図において、バッチャ−出力に−１，ｋ−２，ｋ−３，に− ４の確認パケットは夫々入カポ−）ｉ−１゜ｉｗ２．ｉ−３，ｉ＝４にルートづ けされる。これら確認パケットは次に入力ポードアドレスｉ−２を含む確認パケ ットが出力ポートｊ　−２に出るようにバッチャーバンヤン回路を通りルートづ けされる。同様に、入力ポードアドレスｉ　−３，ｉ−４を含む確認パケットは 夫々出力ポートｊ−３とｊ−４に生じる。云い換えると、入力ポードアドレスｉ を含む確認パケットは出力ポートｊ　−１に出る。出力ｊ−１，２，３，４は次 にｊ−１がｉ−１に、ｊ−２がｉ−２に、以下同様にして接続するように対応す る入力ｉ−１，２，３，４に接続する。このように、入力ポードアドレスｉ−２ ，３，４を含む確認パケットはこれらアドレスにより限定される入力ポートにル ートづけされる。これでこのバッチャーバンヤンパケットスイッチサイクルの第 ２の、確認相が完了する。この確認相において、夫々の優勢リクエストパケット の入力ポードアドレス部分はそれが生じた入力ポートにもどされてその入力ポー トに、それが仲裁相において勝利したものでありそのデータパケットを伝送しう ろことを知らせる。

第３相はデータ伝送相であり、これにおいて、優勢入力ポートｉ−２，３，４が それらのデータパケットを伝送する。第３図に示すように、これら３つの入力ポ ートからのデータパケットはコンフリクトせずにバッチャーバンヤン回路を通り ルートづけされる。バッチャ−回路の出力において、これらパケットは宛先出力 ポードアドレスに従って増加順序で区分けされる。バンヤン回路は次に区分はリ スト内のパケットをコンフリクトなしに適正な出力ポートにルートづける。入力 ポートｉ−１におけるデータパケットは次のバッチャーバンヤンスイッチサイク ルまでバッファされる。

上記３相のアルゴリズムを行うハードウェアを第４゜５図に概略的に示す。

第４図はバッチャーバンヤン回路１０用の入力／出力ボートインターフェース２ ０を示す。第４図において、ｉ番目のボートインターフェースはバッチャ回路人 力１１バッチャ−回路出力ｋｍｔ、バッチャー回路出力に−１−１およびバンヤ ン回路出力ｊ−１に接続する。

この人力／出力ポートインターフェース回路の詳細を第５図に示す。伝送される べきデータパケットはライン２２によりボートインターフェースに入る。

この３相バツチヤーバンヤンパケツトスイツチサイクルは４：１マルチプレクサ ２４により制御される。ＭＳ−１のとき、ソース、宛先アドレス対を有するリク エストパケットがバッチャ−人力ｉを介してバッチャ回路に入る。ＭＳはリクエ ストパケットのＮ個の入力をもつスイッチ回路については２　ｌ　ｏ　ｇ　２　 Ｎである。期間中、１に設定される。その後にＭＳ−０となり、その結果バッチ ャ回路へのすべての信号を阻止する。リクエストパケット路の出力に移される。

仲裁用のトリガー２６を出すリクエストパケットの直前にバッチャ回路の出力に −ｉとに−１−１から出る２個のリクエストパケットは１ビツトづつ排他ＯＲゲ ート２８で比較される。リクエストされた宛先が異っていれば、この排他ＯＲゲ ートハトリガー２６を値ＷＩＮ−１にセットしてバッチャ出力に−１でのリクエ ストが認められたことを知らせるだめの立上り信号を出す。（これら２つの宛先 が同一であれば、ＷＩＮは０のままであってバッチャ−回路の出力に−ｉのリク エストパケットに関連した出力ポートリクエストが認められないことを示すこと になる。）信号φ１はＮ入力の回路についてｌ　ｏ　ｇ　２　Ｎに等しいリクエ ストパケットの宛先アドレス部分の期間で終る。

第２、即ち確認相はマルチプレクサ２４内でＭＳ−２にセットすることにより開 始する。この確認パケットはバッチャ−回路の出力ｋｍｉのリクエストパケット のソースアドレス部分で形成される。この確認パケットはゲート３０とマルチプ レクサ２４によりバッチャ回路にもどされ、その後バッチャーバンヤン回路を通 される。バ（ｌ　ｏ　ｇ　２　Ｎ　＋　１　）　＋１　ｏ　ｇ　Ｎである。パケ ットはこのバッチャーバンヤンの待ち時間後に入る。確認パケットが入る直前に 、信号φ２がトリガー３２をクリアし、このパケットが入ることによりトリガー 信号ＡＣＫが１１；セットされる。ＡＣＫ−１となると、データパケットが完全 に、データパケットの期間マルチプレクサ２４内でＭＳ−３にセットを行うこと によりバッチャーバンヤン回路に伝送される。仲裁において劣勢とされたボート インタフェースは次のスイッチサイクルまでバッファ３６内にそのデータパケッ トをとどめる。バッファ３６はフレーム回路３８と４０の間に配置されており、 これらフレーム回路はマイクロプロセッサ４２により制御される。

データパケットがバッチャーバンヤン回路を通った後に信号φ３がバンヤン出力 ｊ−１に入るデータパケットをゲート３４を介して外部に伝送されるようにする 。

これら仲裁および確認相はバッチャーバンヤン回路用の総合オーバーヘッド時間 Ｔ−１ｏｇ２Ｎ　（ｌｏｇ２Ｎ＋４）についての仲裁相のオーバーヘッドは 相■のオーバーヘッドは る。

Ｎ−１０２４でありデータパケットの長さしがＬ−１０２４であるときは、オー バーヘッドの率はオーバーヘッドの率は、パケット期間がより長くなれば小さく なる。例えばデータパケットが２０４８ビツトであれば、オーバーヘッド率は７ ％となる。

この３相ルートづけプロセスにはいくつかの変更例がある。その１つは第６図の システムを用いて実施出来る。

この例はバッチャ−回路の出力にと入力ポートｉとの間に確認相においては結線 がない。第６図の実施例において、リクエストパケットは仲裁相中バッチャ−ソ ート回路５Ｏ−ｔ−通される。コンフリクトするリクエストはバッチャ−回路５ ０の出力でパージ回路５２により排除される。集中回路５４はこの排除後にすべ てのホールを消しそしてリクエストパケットがバンヤン回路５６の出力へと通さ れる。これ以外の確認相およびデータパケット伝送相は同じであるが、確認相に おいては確認パケットがバッチャ−出力ではなくバンヤン出力から生じる点だけ 異る。

この変更３相法は次のように２相法にすることが出来る。相Ｉにおいてデータパ ケットを有する各入力ポートは全パケットをこの回路に送る。バッチャ−ソート 回路５０の出力における仲裁で優勢となるパケットはすべて集中回路５４とパン ヤンルート回路５６を通りそれらの宛先ボートに行く。相■ではデータパケット を受ける各出力ポートが確認パケットを前述のように発生入力に送ることにより 受信パケットの発生入力ボートを確認する。

云い換えると、この２相法は分配の保証を伴わずにパケットを送るが、バッファ に送ったパケットのコピーを保持して確認が入ったときにのみそのパケットを消 す。

パケットの優先順位は本発明のパケットルート法においては仲裁相を変更するこ とにより考慮される。高い優先順位のパケットはリクエストパケットの宛先アド レスの末尾につけられた優先フィールドにより優先順位の低いパケットと区別さ れる。優先フィールドを付されたアドレスはバッチャ回路で区分けされ、１つの 特定の出力ポートについての二重のリクエストをもつ複数のパケットを排除する ときにはその結果優先順位の高いパケットを望ましい位置に置く。

この優先順位はバッチャーバンヤン入力ポートの待ちラインブロッキングのヘッ ドを除去するために有効に使用出来る。入力ポートでの待ちラインにおいて第１ パケツトの後のパケットが自由出力ポートに分配されえたがこの待ちラインにお ける第１パケツトが出力ポートのコンフリクトがなくなった結果阻止されるから 分配されなかったときにバッチャーバンヤン回路の利用不足が生じる。入力ポー トの待ちラインにおける第２パケツトの伝送りクエストは次のようにして許可さ れる。仲裁および確認相の後で待ちラインのヘッドでパケットはそれらが阻止さ れるかどうかを知る。夫々の阻止された待ちラインにおける第２パケツトはその とき仲裁および確認相の第２ラウンドにおいてリクエストを出しうるようになる 。

これら第２ラウンドのリクエストは第１ラウンドで許可されたリクエストに干渉 してはならない。この非干渉は第２ラウンドにおいて、第１ラウンドで優勢とさ れたリクエストパケットを与えることにより達成出来、それらが第２ラウンドで 常に優勢となる。これはその待ちライン内の以降のパケットについての第３ラウ ンドでもくり返すことが出来る。しかしながら、これは他の相の適用について必 要なオーバヘッドを正当化しないような先細りリターンを生じさせるかもしれな い。

最後に、本発明の上述の実施例は例示のためのみのものである。多くの他の実施 例は請求された発明の精神と範囲から離れることなく当業者には案出可能である 。

ＦＩＧ、３ ＦＩＧ、５ 補正書の翻訳文提出書（特許法第１８４条の８）平成　１　年　４　月　１４日 Ｉｎ￥ｆ　ＨＫＩＥ　ｔＪｌ、１１ｎええ　惨１、　特許出願の表示 ＰＣＴ／ＵＳ　８７１０１７５３ ２、発明の名称 出力コンフリクト解決手段を有するバッチャーバンヤンパケットスイッチ３、特 許出願人 住　所　アメリカ合衆国二ニーシキーシー州、リビングストン、ウェスト、マウ ント、ブレザント、アベニ二、２９０名称　ベル、コミュニケーションズ、リサ ーチ、インコーホレーテッド ４、代理人 （郵便番号ｌＯの 東京都千代田区丸の内三丁目２番３号 ５、　補正書の提出年月日 １９８８年１０月１４日 ６、添付書類の目録 （１）　補正書の翻訳文　１　通 明細書第１７頁下から第３行〜末行に記載の「最後に・・・可能である。」を特 徴する 請求の範囲 １、　伝送すべきデータパケットを有する各入力ポートについて、出力ボートリ クエストパケットを一つの与えられた出力ポートについて１つを除くすべてのリ クエストを排除するように非内部阻止パケットスイ・ソチ回路（１０）に比較器 要素（２８）を用いて方向づけ、上記回路（１０）を、確認パケットを排除され なかったリクエストパケットの発生入力ポートに方向づけるように利用すること により上記排除段階の結果に関し発生入力ポートを確認し、 そして確認された入力ポートから上記回路（１０）を通じデータパケットを伝送 する、 ことからなることを特徴とする、同一出力ポートに同時にアドレスづけされたデ ータパケットを有する入力ボート間のコンフリクトを回避するように上記回路の 入力ポート（ｉ−１，２，３・・・Ｎ）から出力ポート（ｊ−１゜２．３・・・ Ｎ）へデータパケットを方向づける方法。

２、　前記リクエストパケットの夫々は入力ポートを同定するソースアドレスと 出力ポートを同定する宛先アドレスからなる請求項１記載の方法。

３、　前記内部非阻止回路はバッチャ−ソート回路（１２）とバンヤンソート回 路（１４）とからなるノくツチキーバンヤン回路である請求項１記載の方法。

４、　前記リクエストパケット方向づけ段階はソースアドレスと宛先アドレスか らなるリクエストパケットを前記バッチャ−ソート回路（１２）に方向づけして そこに含まれる宛先アドレスに従って上記リクエストパケットを順序づけること を含む請求項３記載の方法。

５、　前記確認段階は各非排除リクエストパケットのソースアドレス部分を前記 バッチャ−回路（１２）の出力（ｋ−１，２，３・・・Ｎ）からその発生入力へ ともどす段階を含む請求項４記載の方法。

６、　前記バッチャ−回路のｎ番目の出力のリクエストパケットのソースアドレ ス部分はそのバッチャ−回路のｎ番目入力に向けられ、その後にバッチャーバン ヤンを通り、上記ソースアドレス部分と同一のアドレスを有する出力ポートに向 けられるごとくなった請求項５記載の方法。

７、　各リクエストパケットは発生入力ポートを同定するソースアドレスと出力 ポートを同定する宛先アドレスからなり、前記リクエストパケット方向づけ段階 はこれらリクエストパケットと前記バッチャ−回路（１２）を、このバッチャ− 回路（５２，５４）の出力に配置される排除および集中回路、および前記バンヤ ン回路（１４）を通じてその出力に方向づけることを含む、請求項３記載の方法 。

８、　複数の入カポ−）　（ｉ−１，２，３・・・Ｎ）と複数の出力ポート（ｊ −１，２，３・・・Ｎ）間でデータパケットを伝送するための内部的に非阻止の パケットスイッチ回路（１０）を有し、リクエストパケットを上記回路（１０） に送り同一パケットスイッチサイクルにおいて同一出力ボー）　（ｊ＝１．　２ ．　３．・・・、Ｎ）にデータパケットを伝送しようとする入カポ−）　（ｉ＝ １．２，３゜・・・、Ｎ）間のコンフリクトを仲裁するための手段（２４゜３８ ．４２）と、一つの与えられた出力ポートについて１個を除くすべてのリクエス トパケットを排除する比較器手段（２８）と、この仲裁で優勢となった入力ポー トに確認パケットを伝送する手段（２６，３０，２４）と、からなることを特徴 とするパケットスイッチ。

Ａ、’Ｊ！ｗ’ＥＸ　Ｔｏ　ＴＨＥ　ｒＮτＥＲＩＮＡτｌ０ＮＡＬ　５ＥＡＲ ＣＨＦＬＥＰＯＲＴ　ＯＮ

Claims (15)

【特許請求の範囲】
1. １．伝送すべきデータパケットを有する各入力ポートについて、出力ポートリク エストパケットを一つの与えられた出力ポートについて１つを除くすべてのリク エストを排除するように非内部阻止パケットスイッチ回路に方向づけ、上記回路 を確認パケットを排除されなかったリクエストパケットの発生入力ポートに方向 づけるように利用することにより上記排除段階の結果に関し発生入力ポートを確 認し、そして確認された入力ポートから上記回路を通じデータパケットを伝送す る、ことからなる上記回路の入力ポートから出力ポートへデータパケットを方向 づける方法。
2. ２．前記リクエストパケットの夫々は入力ポートを同定するソースアドレスと出 力ポートを同定する宛先アドレスからなる請求項１記載の方法。
3. ３．前記内部非阻止回路はバッチャーソート回路とバンヤンソート回路とからな るバッチャーバンヤン回路である請求項１記載の方法。
4. ４．前記リクエストパケット方向づけ段階はソースアドレスと宛先アドレスから なるリクエストパケットを前記バッチャーソート回路に方向づけしてそこに含ま れる宛先アドレスに従って上記リクエストパケットを順序づけることを含む請求 項３記載の方法。
5. ５．前記確認段階は各非排除リクエストパケットのソースアドレス部分を前記バ ッチャー回路の出力からその発生入力へともどす段階を含む請求項４記載の方法 。
6. ６．前記バッチャー回路のｋ番目の出力のリクエストパケットのソースアドレス 部分はそのバッチャー回路のｋ番目入力に向けられ、その後にバッチャーバンヤ ンを通り、上記ソースアドレス部分と同一のアドレスを有する出力ポートに向け られるごとくなった請求項５記載の方法。
7. ７．各リクエストパケットは発生入力ポートを同定するソースアドレスと出力ポ ートを同定する宛先アドレスからなり、前記リクエストパケット方向づけ段階は これらリクエストパケットと前記バッチャー回路を、このバッチャー回路の出力 に配置される排除および集中回路、および前記バンヤン回路を通じてその出力に 方向づけることを含む、請求項３記載の方法。
8. ８．特定のパケットスイッチサイクル中同一の出力ポートにデータを伝送しよう とするバッチャーバンヤン回路の入力ポート間のコンフリクトを解決するための 下記段階からなる方法。 （ａ）上記パケットスイッチサイクルの仲裁相において上記バッチャーバンヤン 回路の内のバッチャー部分に上記入力ポートの夫々からリクエストパケットを送 り宛先アドレスに従って上記リクエストパケットを順序づけそして一つの与えら れた出力宛先に向けられた１個を除くすべてを排除する段階。 （ｂ）上記パケットスイッチサイクルの確認相においてバッチャーバンヤン回路 によりそのバッチャー回路の出力から非排除パケットの発生した入力ポートに確 認バケットを方向づける段階。 （ｃ）データパケット伝送相において、データパケットを上記バッチャーバンヤ ン回路を通じて確認された入力ポートから伝送する段階。
9. ９．同一パケットスイッチサイクルにおいて同一出力ポートにデータパケットを 伝送しようとする入力ポート間のコンフリクトを解決するためにパケットスイッ チ回路の入力ポートから出力ポートにデータパケットを方向づけするための、下 記段階からなる方法。 （ａ）各スイッチサイクルの仲裁相において、一つの与えられた出力ポートにつ いて１個を除くすべてのリクエストパケットを排除することにより出力ポートの コンフリクトを解決するために上記入力ポートからの出力ポートリクエストパケ ットを上記回路に方向ずける段階。 （ｂ）各スイッチサイクルの確認相において確認パケットを夫々排除されなかっ たリクエストパケットの発生した入力ポートに方向づける段階。 （ｃ）各スイッチサイクルのデータパケット伝送相において、データパケットを 上記確認された入力ポートから上記パケットスイッチ回路を通じて伝送する段階 。
10. １０．同一スイッチサイクルにおいて同一出力ポートにデータパケットを伝送し ようとする入力ポート間のコンフリクトを解決するためにパケットスイッチ回路 の出力ポートにその入力ポートからデータパケットを方向づけるための、下記段 階からなる方法。 上記データパケットを、上記出力ポートにおける分配保証を伴わずに上記入力ポ ートから上記回路に伝送し、その間上記データパケットのコピーをその入力ポー トでバッファする段階。 各出力ポートにアドレスづけされた１個を除きすべてのパケットを排除する段階 。 確認パケットを、データパケットを受ける上記出力ポートから上記入力ポートに 伝送して、パケットが分配されている入力ポートを確認する段階。 上記確認された入力ポートでバッファされた上記パケットを除去する段階。
11. １１．複数の入力ポートと複数の出力ポートを含む内部的に非阻止のパケットス イッチ回路と、リクエストパケットを上記回路に送り同一パケットスイッチサイ クルにおいて同一出力ポートにデータパケットを伝送しようとする入力ポート間 のコンフリクトを仲裁するための手段と、この仲裁で優勢となった入力ポートに 確認パケットを伝送する手段と、からなるパケットスイッチ。
12. １２．前記回路はバッチャーソート回路とバンヤンルート回路からなるバッチャ ーバンヤン回路である請求項１１記載のパケットスイッチ。
13. １３．同一のパケットスイッチサイクルにおいて同一の出力ポートにデータパケ ットを伝送しようとする入力ポート間のコンフリクトを解決するためにデータパ ケットをパケットスイッチ回路の入力ポートから出力ポートに方向づけるための 、下記段階からなる方法。 上記入力ポート間の上記コンフリクトを検出する段階。 上記入力ポート間のコンフリクトを解決する段階。 上記解決段階の結果を上記入力ポートに知らせる段階。
14. １４．パケットスイッチ回路の１サイクルにおいて入力ポートから出力ポートに データパケットを方向づけるための、下記段階からなる方法。 同一出力ポートに向けられたデータパケット間のコンフリクトを検出する段階。 上記回路を通り伝送するための、上記コンフリクト関係にあるデータパケット入 力ポートの１個のみを通知する段階。 次のサイクルでの伝送のため他のコンフリクト関係にあるデータパケットのデー タパケットをバッファする段階。
15. １５．前記パケットスイッチ回路の前記１サイクル内で前記１個の入力ポートか らデータパケットを伝送する段階を更に含む請求項１４記載の方法。