JPS62500902A - パケット・スイッチド・マルチポ−ト・メモリｎ×ｍスイッチ・ノ−ド及び処理方法 - Google Patents

パケット・スイッチド・マルチポ−ト・メモリｎ×ｍスイッチ・ノ−ド及び処理方法

Info

Publication number
JPS62500902A
JPS62500902A JP60504505A JP50450585A JPS62500902A JP S62500902 A JPS62500902 A JP S62500902A JP 60504505 A JP60504505 A JP 60504505A JP 50450585 A JP50450585 A JP 50450585A JP S62500902 A JPS62500902 A JP S62500902A
Authority
JP
Japan
Prior art keywords
logic
port
output port
memory
data packets
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP60504505A
Other languages
English (en)
Other versions
JPH0638607B2 (ja
Inventor
マクミラン，ロバート・ジエイ
ロスマン，アンドリユウ
Original Assignee
ヒユ−ズ・エアクラフト・カンパニ−
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by ヒユ−ズ・エアクラフト・カンパニ− filed Critical ヒユ−ズ・エアクラフト・カンパニ−
Publication of JPS62500902A publication Critical patent/JPS62500902A/ja
Publication of JPH0638607B2 publication Critical patent/JPH0638607B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/10—Packet switching elements characterised by the switching fabric construction
    • H04L49/103—Packet switching elements characterised by the switching fabric construction using a shared central buffer; using a shared memory
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/30—Peripheral units, e.g. input or output ports
    • H04L49/3009—Header conversion, routing tables or routing tags
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/40—Constructional details, e.g. power supply, mechanical construction or backplane

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Computer Hardware Design (AREA)
  • Signal Processing (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Mathematical Physics (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Multi Processors (AREA)
  • Use Of Switch Circuits For Exchanges And Methods Of Control Of Multiplex Exchanges (AREA)

Abstract

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

Description

【発明の詳細な説明】 パケット・スイッチド・マルチボート・メモリＮＸＭスイッチ・ノード及び処理 方法 発′明の背景 本発明は一般に、マルチ・プロセッサ及びパラレル・コンピュータ・システム、 及びディジタル通信システム、等に使用されるパケット・スイッチング・ネット ワークに関し、特にデータ・パケットをストアし且つ複数の出力ボートに転送す るために使用され、且つ同一の入力ボートに達するデータ・パケット間での出力 ボート争奪を減するマルチボート・メモリ及びそれに結合された制御ロジックを 使用するパケット・スイッチング・ノードに関する。
コンピュータ・チクノロシイに於いては、大スケールの。
マルチ・プロセッサ・ベースに分解される。且つパラレルのコンピュータ・シス テムの設計及び開発の領域がＲ１ｉ！途上にある。典型的なこの種類のコンピュ ータ・システム及び構成上のアブＯ−チとしては、単一命令列、複数データ列（ ＳＩＭＤ）コンピュータ構成及び複数命令列、！！ｉ数データ列（ＭＩＭＤ）コ ンピュータ構成がある。
ＳＩＭＤコンピコンピュータ的に、制御ユニット、Ｎｇの処理Ｈ置、Ｎｌｌ１の メモリ・モジュール及び相互接続ネットワークを具備している。上記制御ユニッ トは、上記処理装置の全てに命令を与え、全てのアクティブな処理装置が同時に 同じ命令を実行する。アクティブな処理装置はそれぞれ、それ自身に関連するメ モリ・セジュール内のデータに基いて上記、Ｉｆｒｌ令を実行する。上記相互接 続ネットワークは、上記９Ｉｊｋ理装置とメモリ・モジュールのための通信［’ ｌＪを提供している。
ＭＩＭＯコンピュータは典型的に、Ｎ個の処理装置とＮｆＩ］のメモリとを具備 し、それぞれの処理装置は独立した命令列を実行する。、Ｊ：記処理装置のそれ ぞれは、いずれの他の処理装置とも通信可能である。同様の相互接続ネットワー クが、該ＭＩＭＤコンピュータに使用されることができる。
種々の相互接続ネットワークは、どちらかのタイプのコンピュータ・システムに 使用された処理装置とメモリとを相互接続するために使用されることかできる。
これらの相互接続ネットワークは、例えば、デルタ・ネットワーク、オメガ・ネ ットワーク、間接２進ｎキユーブ・ネットワーク、フリップ・ネットワーク、キ ューブ・ネットワーク及びバニュアン・ネットワークを含む。
前述のネットワークは、以下の刊行物に詳述されている。
即ち刊行物とは、”ＬＳＩ　ｉ＋口ｐｌｃ＋ｌ１ｅｎｌａｔｉｏｎ　ｏｆ　１１ ｏｄｕｌａｒ　１ｎｔｅｒ−ｃｏｎｎｃｃｔｉｏｎ　ｎｅｔｗｏｒｋｓ　ｆｏｒ 　ＨＩＮＤ　１ａｃｈｉｎｅｓ、”　１９８０　１ｎｔ’１Ｃｏｎｆ、Ｐａｒａ ｌｌｅｌ　Ｐｒｏｃｅｓｓｉｎｏ、八ＬＩ０．　１９８０．　００、１６１−１ ６２　。
°＾ｎａｌｙｓｉｓ　ａｎｄ　５ｔＩｌｕｌａｔｉｏｎ　ｏｆ　ｂｕｆｆｅｒｅ ｄ　ｄｅｌｔａ　ｎｅｔｗｏｒｋｓ、”ＩＥＥＥ　Ｔｒａｎｓ、Ｃｏ　ｐｕｔｅ ｒｓ、Ｖｏｌ、Ｃ−３０，ＤＤ、２７３−２８２．　八ｐｒｉ１１９８１；　” Ｐｒｏｃｅｓｓｏｒ−ｎｅｎｏｒｙ　１ｎｔｅｒｃｏｎｎｅｃｔｉｏｎｓ　ｆｏ ｒ　１１ｕｌｔｉ−ｐｒｏｃｅｓｓｏｒｓ、”　１３ｔｈ　Ａｎｎｕａｌ　Ｉｎ ｔ’ｌ　Ｓｙｕ、Ｃｏ　ｐｕｔｅｒ　＾ｒｃｈｉｔｏｃ−ｔｕｒｅ、＾ｐｒｉｌ 　１９７９．　ｐｐ、１６８−１７７；　”Ｄｅｓｉｇｎ　ａｎｄ　１ｌｉｐｌ ｅｌｌ（Ｉｎｔａ−ｔｉｏｎ　ｏｆ　ｔｈｅ　ｂａｎｙａｎ　１ｎｔｅｒｃｏｎ ｎｅｃｔｉｏｎ　ｎｅｔｖｏｒｋ　ｉｎ　ＴＲＡＣ，”ＡＦＩＰＳ　１９８０　 Ｎａｔ’ｌ　Ｃｏｕｕｔｅｒ　Ｃｏｎｆ、、Ｊｕｎｅ　１９８０．　ｐｐ、１３ ４３−６５３；”Ｔｈｅ　ｎｕｌｔｉｓｔａｇｅ　ｃｕｂｅ：　ａ　ｖｅｒｓａ ｔｉｌｅ　１ｎｔｅｒｃｏｎｎｅｃ口ｏｎ　ｎｅｔ−Ｃｏｎｐｕｔｉｎｇ　ａｎ ｄ　Ｃｏｎｔｒｏｌ　５ｙｎｐ、、　Ｄｅｃ、　１９８０．　ｐｐ、　１１−２ ２；及び”Ｐｅｒｆｏｒｎａｎｃｅ　ａｎｄ　１ｎｐｌｅｉｅｎｔａｔｉｏｎ　 ｏｆ　４ｘ４　ｓｓｖｉｔｃｈｉｎｇ　ｎｏｄｅｓ色々なタイプのデータ・スイ ッチング・テクニックが、パケット・スイッチング、メツセージ・スイッチング 、時分割回路スイッチング又は空間弁？１回路スイッチングを含む、Ｓ　ＩＭＤ 及びＭＩＭＤコンビコータ等に於いてデータを転送するために使用されることが できる。バケツ！−・スイッチングは、上記システムを介して同時に一つ以上の ワードのデータを送ることを伴う。
普通のパケット・スイッチング相互接続ネットワーク及びノードは、該ネットワ ークを通るｔｔ’ｉ報伝達速度を伴う良く知られた問題を有している。普通のデ ザインでは、信号パケットをストアし且つ出力ボートの全てに転送づるために、 上記ネットワークのそれぞれの入力ボートに結合されたたった−っの待ち行列を 典型的に使用している。上記待ち行列システムに於いては、例えば、出力ボート １に指定された信号パケットが上記待ち行列中の出力ボート２に指定された信号 パケットよりも物理的に前にあり、且つそれがボート１を介してまだ出ていない ので、上記出力ボート２に指定された信号パケットが、そのボートを介して出る ことがらブロックされてしまうという事のために、回線争奪問題が発生する。こ の回線争奪問題は、不必要な輸送遅延を引起こし、従ってシステム・スループッ トを減じてしまう。
この問題を克服するために試みられた成るパケット・スイッチング・ノードが、 Ｒ，Ｊ、　Ｈｃ旧１１ｅｎによって発明され、本発明の譲り受け人に譲渡された ’Ｐａｃｋｅｔ　５ｉｖｉｔｃｈｅｄ　ｍｕｌｔｉｐｌｅｑｕｅｕｅ　ＮｘＭ　 ５ｗ１ｔｃｈ　ｎｏｄｅ”と題された現在審査中の特許出願に述べられている。
この発明は、出力ボート指定に従って信号パケットを分類するように入ツノボー トのそれぞれに個々に接続された複数の待ち行列セットを利用する。しかしなが ら、このノードがそれを使用するコンピュータ・システムの通信Ｑｌｉ力を向上 さ−せるとはいえ、それは大きなバッフ戸リング能力を必要とする。これは、ロ ジック回路の多数のストレージ・トランジスタの使用を意味する。
ｌ匪ユ厘力 従来のスイッチング・ノードの制限を克服するために、本発明は、データ・パケ ットが加えられるべき出力ボート指定を示す経路指定タグ信号を含む加えられた データ・パケットを処理するバケツ１〜・スイッチング・ノードを提供する。上 記バケツｌ−・スイッチング・ノードは、複数の入力ポートと複数の出カポ−１ −とを具備しでいる。マルチボート・メモリが、上記入カポ−１・と出力ボート との間に結合されている。
上記メモリは、上記人力ボートの（れぞれに加えられたデータ・パケットの記憶 のために利用できる、所定の数のメｔす・ロケーションを有している。上記メモ リのデータ・パケッｈの記憶を制御する制御ロジックが、上記入力ボート、出力 ボート及びマルチボート・メモリに結合されている。上記制御ロジックはまた、 上記経路指定タグ信号に従って、上記出力ボートに対する上記データ・バウーツ トの経路指定を制御する。
上記制御ロジックは、ト記経路指定タグイｊＢと上記メモリのメモリ・ロケーシ ョンのそれぞれのフル／エンプティ・ステータスを示づステータス信号との両方 を記憶するための、上記入力ポートと上記メモリとに結合されたステータス・レ ジスタ・ロジックを含む。上記制御ロジックはまた、上記入力ボート、メモリ及 びステータス・レジスタ・ロジックに結合された優先順位エンコーダ・ロジック を含む。上記優先順位エンコーダ・ロジックは、上記メモリ・ロケーションのフ ル／エンプティ・ステータスを監視し、上記ステータス・レジスタ・ロジックの レジスタに経路指定タグ信号をライトし、且つ選択されたメモリ・ロケーション に上記経路指定タグ信号に対応するデータ・パケットをライトする。
上記制御ロジックはさらに、上記ステータス・レジスタ。
メモリ及び出カポ−１〜に結合された裁定（ａｒｂｉｔｒａｔｉｏｎ）ロジック を含む。該裁定ロジックは、所定の優先順位裁定要綱に基かれた対応する経路指 定タグ信号で確認された出力ボートに、上記メモリ・ロケーションから上記デー タ・パケットを移す。上記裁定ロジックは、同一出力ボートからの出力のために 争う同一人力ボートに入る経路指定タグ間で裁定するバッフ１裁定ロジツクを含 む。上記裁定ロジックは、それらからの特定の経路指定タグを、統計的な意味で 及び成る期間で区切ればランダムに選択する。その上、ボート裁定ロジックが、 上記バッファ裁定ロジックに結合されるもので、同−出力ボートのために争い且 つその特定の出力ボートからの出力のためにそれらから成る経路指定タグを選択 する、上記バッフ１裁定ロジツクによって伝達された全ての経路指定タグ間で裁 定する。このボート裁定は、全ての出力ボートのために同時に行なわれる。
上記裁定ロジックはまた、上記ボート裁定ロジックによって選択されたそれらの 経路指定タグ信号に対応してデータ・パケットのための適当な出力ボートを通る データ・パケットの出力を制りｐするリード・アドレスを発生するアドレス発生 及びラッチ・ロジックを含む。上記ラッチ・ロジックに結合されたステータス更 新ロジックが、上記出力ボートのいずれかに加えられたデータ・パケットに対応 して上記レジスタのフル／エンプティ・ステータスをリセットする信号を発生ず る。
一般に、本発明は、Ｎ個の入力ポートのいずれかでデータ。
パケットを受理し、且つＭ＠の出力ボートのいずれかにそれぞれ経路指定するＮ ＸＭのスイッチ・ノードを含む。選択された出力は、上記パケット中の経路指定 タグ信号によって決定される。上記制御ロジックは、上記データ・パケットがそ れらの所望の出力ボート指定に従って効果的に分類されるように設計されている 。上記裁定ロジックは、同一出力ボートに向けられているいずれかのデータ・パ ケット間で、統１的な意味でランダムに選択する。上記裁定ロジックによって実 行されたアルゴリズムは、データ・パケットが上記スイッチ・ノードから経路指 定されることを無期限に待たないように段重されている。
動作に於いては、上記制御ロジックは、それが接続された他のスイッチ・ノード や処理装置等とハンドシェーキングする。上記制御ロジックは、上記メモリにア ドレスを発生し、データ・パケット間で裁定する。上記スイッチ・ノードへの全 ての入って来る要求は、上記経路指定タグ信ｑを同行する。
これらの経路指定タグ信号は、上記データ・パケット中の所定の数のビットであ る。フル／エンプティ・ステータス・ビットに加えて、これらのビットは、上記 ステータス・レジスタ・ロジックにストアされる。上記ステータス・レジスタは 、ＮＸＰのセルを持っているもので、ここでＮは入力ポートの数であり、Ｐは入 力ポート毎に許されたストレージ・ロケージョンの数である。それぞれのセルは 、上記マルチボー１〜・メモリのメモリ・ロケーションに対応し、特定のメモリ ・ロケーションにストアされたデータ・パケットに対応するステータス・ピッ１ −と・タグ・ビットどの両方をストアする。
上記優先順位エンコーダ・ロジックは、要求が受取られた時、所定の入力ボート のために割当てられた第１の利用できるセルを選択する。特定の入力ボートと関 連するステータス・ピッ１−が全てフルでない間は、許可信号が発送ノード叩ら ノードに送られる。要求パケットが次に、メモリのその指定されたロケーション にライトされ、タグ・ビットが上記ステータス・レジスタにライトされ、そして 対応するフル／エンプティ・ビットが゛フル”にセラ１〜される。
パケット間での裁定は、２つのステップで起こる。第１に、フル・セルの全ての タグ・ビットが所望の出力ポートに従って、デコードされ且つグループされる。
次に、上記バッファ裁定ロジックは、同一出力ポートに指定されてもいる同一人 力ボー！・に入９たパケット間でランダムに選択する。第２のステップに於いて は、上記ボート裁定ロジックは、同一出力ボー１−に指定されるバッファ裁定ロ ジックによるさらなる裁定のため選択されたいずれかのバケツ１−間でランダム に選択する。裁定要綱の重要な特徴は、同一人力ボートに入るデータ・バケツ１ −が異なった出カポ−］・を望む限りは、裁定の第２のステップに於いて関係す ることを全てが許されるということである。従って、メモリのそれらの位置のた めにブロックされない。パケットは、同一出力ボーｌ〜のため別のパケットどの 回、線争奪のためにのみブロックされることができる。
最後に、上記裁定処理の結果がラッチされ、要求がパケットによって望まれたそ れらの出力ポートのために発生される。
適当なリード・アドレスが、使用されるべきそれぞれの出カポ−１−のために発 生される。発生されたそれらの要求のために、適当なフル／エンプティ・ステー タス・ビットが、゛エンプティ″にリセットされる。いずれの要求も許可されな いならば、上記バケツ１−はメモリに残り、次のサイクルの間、上記裁定処理を 繰返寸。
従って、本発明のパケット・スイッチング・ノードは、指定が異なった出力ポー トであるその入力ボートのいずれかに着くデータ・パケット間の回線争奪の問題 を除去する。上記パケット・スイッチング・ノードは、回線争奪を減するような 出力ボート指定に従って、加えられＪ、：Ｙ−タ・パケットをストアし、従って システム性能及びスルーブツトを向上する。
本発明が、コンピュータ・システム及び構成でその使用に関して特に述べられて いると−はいえ、本発明はこれに限定されるものではない。本発明はまた、通１ ３分野を伴う適用に使用されることができる。特に、本発明に使用する相互接続 ネットワークは、電話ネットワークの加入溝間のディジタル化された音声及び／ 又はデータ・パケットをルートするために使用されることができる。上記データ ・パケットは、加入者と相互に配匠されたコンピュータ又は他の同様の装置によ りて送られる。
その上、本発明は、上記データ・パケットが加えられるべきである出力ボート指 定を示１′経路指定タグ信号を含む加えられたデータ・パケットを処理づ゛る方 法を企図している。該方法は、上記経路指定タグ信号に基いて、適当な出力ポー トにデータ・パケットを経路指定でるように動作する。該・方法は、所定の利用 できるメモリ・ロケーションの入力ボートのそれぞれに着くデータ・パケットを ストアするステップを含む。第２のステップは、同一出力ポートに指定される同 一人力ボートに入るデータ・パケット間で選択することを含む。
第３のステップは、異なった入力ボートに入り、且つ同一出力ポートに指定され る第１の選択処理から現れるデータ・パケット間で選択することを含む、Ｒ後に 、該方法の最後のステップは、上記経路指定タグ信号で１ｉ１ｆＱされた出力ポ ートに選択されたデータ・パケットを加えることを含む。
あるいは、上記方法は、前記経路指定タグ信号に含まれたそれらの出力ボート指 定に基いてデータ・パケットをストアづ゛るステップを含む。次に上記方法は、 同一人力ボートに入り且つ同一出力ボー１−に指定されたデータ・パケット間で 裁定することを含む。上記方法は次に、異なった入力ボートに入り且つ同一出力 ポートに指定された全てのデータ・パケット間で裁定することを企図する。最後 のステップは、上記経路指定タグ信号で確認された出力ポートに上記２つの裁定 処理の間、選択されたデータ・パケットを経路指定することを含む。
第３の代わりの方法は、所定のメモリ・ロケーションにデータ・パケットをスト アするステップを含む。第２のステップは、経路指定タグ信号に含まれたそれら の出力ボート指定に暴いてストアされたデータ・パケットを分類することを含む 。第３のステップは、同一人力ポートに入り且つ同一出力ポートに指定されたそ れらのデータ・パケット間で裁定することを含む。次のステップは、異なった入 力ボートに入り且つ同一出力ポートに指定されたデータ・パケット間で裁定づる ことを含む。最後のステップは、経路指定タグ信号で確認された出力ポートに上 記メモリ・ロケーションから上記裁定処理の間、選択されたデータ・パケットを 経路指定することを企図する。
鳳１１とｌ斐」口１皿 本発明の種々の目的及び特徴は、同一の参照符ｑが同一の構成要素に何された添 削図面に関連して行なわれた以下の詳細な説明に関してさらに容易に理解される ことができる。
第１図は、本発明の原理に従ったＮＸＭのマルチボート・メモリ°パケット・ス イッチング・ノードの一般的な態様を示している。
第２図は、第１図のパケット・スイッグーング・ノードの４人力、４出力実現の ブロック図を示している。
第３図（ａ）及び第３図ｆｂ）は、第２図のパケット・スイツチング・ノードに 使用するための制御ロジックの詳１＠なブロック図を示している。
第４図（ａ）及び第４図ｆｂ）は、第３図の制御ロジックに使用するためのステ ータス、バッファ裁定及び優先順位エンコーダ・ロジックのデザインを示してい る。
第５図（ａ）及び第５図（ｂ）は、第３図の１ｌＩｌｌ罪ロジツクに使用するた めのボート裁定及びラッチ・ロジックのデザインを示している。
第６図（ａ）及び第６図（ｌ］）は、第３図の制御ロジックに使用されたステー タス更新（クリア）ロジックのデザインを示している。
第７図は、第４図のバッファ裁定ロジックに使用するためのデマルチプレクサの デザインを示している。
第８図は、第４図のバッファ裁定ロジックに使用でるだめの３対１マルチプレク サのデザインを示している。
第９図は、第４図のバッファ裁定ロジックに使用するための３を法としだカウン タのデザインを示している。
第１０図は、第４図のバッファ裁定回路に使用するための３人力裁定回路のデザ インを示している。
第１１図は、第６図のステータス更新ロジックに使用するための４対１２デマル チプレクサのデザインを示している。
第１２図は、第２図のスイッチ・ノードに使用するためのマルチボート・メモリ のデザインを示している。
第１３図（ａ）及び第１３図（ｂ）は、第１２図のメモリに使用するための１２ ｘ４ｘ３ビツト・アレイのデザインを示している。
第１４図（ａ）及び第１４図（ｂ）は、第１３図のビット・アレイに使用するた めの４×３メモリ・アレイのデザインを示している。
第１５図は、第１２図のメモリに使用するためのライト・アドレス選択デコード ・ロジックのデザインを示している。
第１６図は、ｍ１５図のロジック回路に使用するためのデマルチプレクサのデザ インを示している。
第１７図は、第１２図のメモリに使用づるためのリード・アドレス行及び列選択 デコード・ロジックのデザインを示している。
第１８図は、第１７図のロジック回路に使用するためのデコーダのデザインを示 している。
第１９図は、第２図のスイッチ・ノードのためのタイミング図を示している。
好ましい実施例の説明 第１図には、本発明の原理に従ったＮＸＭマルチボート・メモリ・パケット・ス イッチング・ノード２０の一般的な態様が示されている。該ノード２０は、複数 の入力ポート２１及び複数の出力ポート２２を具備する。上記入力ポート２１と 出力ポート２２の間に、マルチボート・メモリ２３が結合されている。上記メモ リ２３は、上記入力ボート２１のそれぞれに供給されたデータ・パケットの記憶 のために利用し得る所定の数のメモリ・ロケーションを有している。上記人。
出力ボート２１．２２及びマルチボート・メモリ２３に、制御ロジック２４が結 合されており、これは上記メモリ２３のデータ・パケットのストレージを制御す る。上記制御ロジック２４はまた、上記データ・パケットに含まれる経路指定タ グ信号に従って、上記出力ポート２２への上記データ・バヶッ）・の経路指定も 制御する。
上記入力ポート２１によってデータ・パケットを受取るための伝達プロ１〜コル は、上記制皿ロジック２４に結合された複数の受信ハンドシェーク信号４！２５ によって行なわれる。
同様に、上記出力ポート２２からデータ・パケットを送るための伝達プロトコル は、上記制御１ｏシック２４にまた結合された複数の発信ハンドシェーク信号線 ２６によって行なわれる。
上記制御ロジック２４は、上記入力ポート２１、受信ハンドシェーク信号線２５ ．及びメモリ２３に結合されたタグ・ステータス・ロジック・レジスタ３０を含 むもので、該レジスタ３０は、上記経路指定タグ信号と、上記メモリ２３のメモ リ・ロケーションのそれぞれのフル／エンプティ・ステータスを表わすステータ ス信号との両方をストアする。上記１１１１制御ロジツク２４はまた、上記入力 ボート２１．メモリ２３及びステータス・レジスタ・ロジック３ｏに結合された 優先順位エンコーダ・ロジック３１も含む、該優先順位エンコーダ・ロジック３ １は、上記メモリ・ロケーションのフル／エンプティ・ステータスを監視し、上 記ステータス・レジスタ３０のレジスタに上記経路指定タグ信号をライトし、且 つ選択されたメモリ・ロケーションに上記経路指定タグ信号に対応するデータ・ パケットをライトするようなものである。
上記制御ロジック２４はさらに、上記タグ・ステータス・レジスタ・ロジック３ ０とラッチ・ロジック３６とに結合された裁定ロジック３２を含む。該裁定ロジ ック３２は、上記ステータス・ロジック３０にストアされた経路指定タグを検査 し、所定の優先順位裁定要綱に基いて相争う要求を解決するようなものである。
該裁定処理に於いては、リード・アドレスが発生され、それらが上記裁定ロジッ ク３２によって選択された経路指定タグ信号に対応するように、適当な出力ポー ト２２を通るデータ・パケットの出力を決定する上記ラッチ・ロジック３６にス トアされる。
上記裁定ロジック３２は、同一出力ボート２２からの出力のために争う同一人力 ボート２１に入る経路指定タグ間で裁定するようにデザインされているバッファ 裁定ロジック３３を含む。上記裁定ロジック３２は、それらからの特定の経路指 定タグをランダムに選択する。その上、ボー！−哉定ロシック３４が、上記バッ フ戸裁定０シック３３に、及び同一出力ボート２２のために争う上記バッファ裁 定ロジック３３によって送られた全ての経路指定タグ間で裁定するようなもので ある上記ラッチ・ロジック３６に結合され、その特定の出力ボート２２からの出 力のため、それらからの成る経路指定タグとその関連するバケツ１−とを選択す る。
上記ラッチ・ロジック３６と発信ハンドシェーク４３号線２６とに、ステータス 更新ロジック３５が結合されている。
上記ステータス更新ロジック３５は、上記出力ボート２２のいずれかに加えられ 且つそれから送られるデータ・パケットに対応するレジスタのフル／エンプティ ・ステータスをリセットする信号を発生するようにデザインされている。
動作に於いては本発明は、Ｎ個の入力ボート２１のいずれかでデータ・バケッｌ −を受理し、Ｍ個の出力ボート２２のいずれかにそれぞれ経路指定するＮｘＭの スイッチ・ノードとして使用されることができる。選択された出力ボート２２は 、データ・バケツ１−の経路指定タグ信ｑによって決定される。
」−２制御ロジック２４は、データ・バヶッ１へかそれらの所望の出力ボート指 定に従って効果的に分類されるようにデザインされている。上記裁定ロジック３ ２は、同一出力ボート２２に向けられるデータ・バケット間で、統計的な意味で ランダムに選択する。、Ｆ２裁定ロジック３２によって実行されるアルゴリズム は、データ・パケットが」−記スイッチ・ノード２０から経路指定されることを 無期限に待たないだろう。
上記制御ロジック２４は、該ノード２ｏが接続される他のスイッチ・ノードや処 Ｊ！！！ａａ、等とハンドシェークする。上記制御ロジック２４は、上記メモリ ２３にアドレスを発生し、データ・バケット間で裁定する。上記スイッチ・ノー ド２゜に入って来る全ての要求は、十記経路指定タグ信号を同行する。これらの 経路指定タグイｊ号は、データ・パケットの所定の数のじツ１〜である。フル、 ／Ｌンブティ・ステート・ピッ１〜と一１賭に、これらのピッ１〜は、ト記タグ ・ステータス・レジスタ・ロジック３０にス１ヘアされる。上記ステータス・レ ジスタ・ロジック３０は、Ｎ　Ｘ　Ｐのセルを含むもので、ここでＮは入カポ− １−２１の数であり、Ｐは入力ポー１−２１毎に許されたス１〜レージ・ロケー ションの数である。それぞれのセルは、メモリ・ロケーシ」ンに対応し、上記ス テータス・ビットとタグ・ピッ１〜との両方をストアする。
上記優先順位エンＴ】−ダ・［］シック３１は、要求が受取られた時、所定の入 カポ−１−２１のために割当てられた第１の利用できるセルを選択する。上記ス テータス・ビットが全てフルでない閂は、“ノット・フル″、即ち許可信号が上 記発信ノード又は処理装置に送られ、これは処理を続けることを意味する。上記 要求バケットは次に、上記メモリ２３の指定ロケーションにライトされ、上記タ グ・ピッ１〜が上記タグ・ステータス・レジスタ・ロジック３０にライトされ、 ぞして対応するフル／エンプティ・ビットが゛′フル”にセットされる。
バケット間での裁定は、２つのステップで起こる。第１に、フル・セルのタグ・ ビットがデフードされ、所望の出力ボート２２に従って分類される。次に、上記 バッファ裁定ロジック３３が、同一人力ボート２１に入り且つ同一出力ボート２ ２に指定もまたされるバケット間間でランダムに選択する。
第２のステップに於いては、−上記ボー１〜ｆ、！定ロジック３４は、同一出力 ボー！−２２に指定される上記バラフッ・裁定ロジック２３によって与えられる いずれかのバケット間でランダムに選択する。同一人力ボート２１に入るデータ ・バケツ１〜が、異なった出カポ−１−２２に指定される限りは、上記裁定の第 ２のステップに関係することを全てが許される。。従って、何も上記メモリ２３ のそれらのポジョンのためにブロックされない。パケットは、同一出力ボート２ ２のための他のパケットどの回線争奪のためにのみブロックされることができる 。
上記裁定処理の結果が、−に記うッチ・ロジック３６にラッチされ、上記データ ・バケツ１−によって望まれたそれらの出力ボート２２のための要求が発生され る。適当なリード・アドレスが、使用されるべきそれぞれの出カポ−１−２２の ために発生される。許可されたそれらの要求のために、適当なフル／エンプティ ・ステータス・ビットが、パエンブティ″′にリセットされる。どの要求も許可 されないならば、上記パケットは上記メモリ２３に残り、次のサイクルの間１− 記載定処理を繰返す。
第２図は、Ｎ＝Ｍ＝４であり、月っ４マルチ・ボー１−・メモリ・スイッチ・ノ ードを含む、第１図の目下好ましい態様のブロック図を示している。第３図には 、第２図のパケット・スイッチング・ノードに使用されることができる上記制御 ロジック２４の最高に詳細なブロック図が示されている。第３図は、本発明に利 用される上記１！ｉｌ　ａｎロジック２４の種々のロジック部を含む、上記ステ ータス更新ロジック３５．タグ・ステータス・レジスタ・ロジック３０．１先順 位エンコーダ・ロジック３１．バッファ裁定ロジック３３．ボー１−裁定ロジッ ク３４及びラッチ・ロジック３６を組込む複数のロジック・ブロックの相互接続 を示している。
第３図に示されたロジック回路番よ、一つのへカポ−１−２５に関連する上記タ グ・ステータス・レジスタ・ロジック３０゜優先順位エンコーダ・ロジック３１ 及びバッフ１裁定ロジツク３３が、４個の入力ボート・ロジック部７０ａ−ｄを 含む４個の同一のロジック・モジュールを形成するように−ａめにされるように 分に」されている。同様に、それぞれの出カポ−ｈ　２６に関連する上記ボート 裁定ロジック３４及びラッチ・ロジック３６のこれらの部分は、４個の出力ボー ト・ロジック部７１ａ−ｄを含む４個の同一のロジック・モジュールを形成する ように一纏めにされている。
他の必翌な信号１１！！は、クロック及びリセッ］−信号線を含んで示されてい る。第３図に示された種々のロジック部の詐細な配置？２図は、本明′ａ占中の 以下の第４図から第１１図に示されている。第３図の信号線参照記号と第４図か ら第１１図に使用された信号線参照記号との間に、１対１の対応がある。
図面の残りは、全てのスイッチ・ノード２０のそれらの動作及び握能を説明する ために必要な範囲を除いては、明白に詳細には述べられないだろう。
第４図は、一つの入カボート部７０の詳細なロジック・デザインを示している。
上記ステータス・レジスタ・ロジック３０は、タグ・デコーダ即ちデマルチプレ クサ７３ａ−ｃと、複数のナンド・ゲー１−７８　ａ−Ｇを使用する優先順位１ ンコーダ・ロジックとに結合された９個のフリップ・フロップ７２ａ−ｉを含む 。デコードされたタグ信号は、バッファ裁定ロジック回路７４ａ−ｄを含む上記 バッファー裁定ロジック３３に、上記デマルチプレクサ７３から供給される。レ ジスタ７５ａ−ｈを含む中間ステータス・レジスタ・ロジックは、上記信号の制 止タイミングを確実にするために使用される。
３を法としだカウンタ７６は、上記バッフ１裁定ロジック回路７４．　ａ　−ｄ によって使用された現在の優先順位を決定するために使用され、カウンタ・イネ ーブル・ロジック７７によってイネーブルされる。上記優先順位エンコーダ・ロ ジック３１は、タグ・ステータス・レジスタ・ロジック・クロック・イネーブル ・ロジック７９に、上記中間ステータス・レジスタ７５　ｆ−ｈを介して結合さ れている。上記タグ・ステータス・レジスタ・ロジック３０に利用されたフル／ １ンブテイ・フリップ・フロップ７２ａ−ｉは、ステータス・リセット・ロジッ ク８０にＪ：っでクリアされる。
第４図のロジック回路は、以下のように動作する。第４図に示された上記入力ボ ート・ロジック部７０ａは、フリップ・フロップ７２ａ−ｉを含む上記タグ・ス テータス・レジスタ・ロジック３０の３＠のロケーションの一つに、３ビツト・ タグとそれに関連づ゛る要求イｅｒ　Ｐ３をス１〜アリ−る。特定のス１〜レー ジ・ロケ−シコンは、ノーンド・ゲー１−７８とクロック・イネーブル・ロジッ ク７９を含む上記優先順位１ンコーダ・［〕コシツク１によって決定される。上 記優先順位１ノコーダ・［］コシツク１は、第１の利用できる１１ケージ１ンを 示づ゛２ビット・アドレスと、イれらが無いかどうかを示すための信号を生成す る。これらの３個の４３号はまた、上記マルチボー１・・メモリ２３に提供され 、対応づる入カポ−１−２１のためのライｌ−・アドレスを形成する。
上記タグ・ステータス・レジスタ・［コシツク３０にストアされたタグは、上記 デマルチプレクサ７３によってそれぞれデコードされる。ｔいぜい、それぞれの γマルチプレクサ７３から出力された一つの１３号がアクティブであり、所望の 出力ボート２２に対応するだろう。上記ｆマルプブレク１）７３からの信号線は 、対応する出力ボート２２によって物理的に纏められ、上記バッフＩ裁定［」シ ック３３を含む、それぞれ胃なった出力ボート２２に関連された４ｇのバッファ 裁定ロジック回路７４に入力される。それぞれのバラフッ・裁定ロジック回路７ ４によって使用された優先順位は、３を法とするカウンタ７６によって提供され る。それぞれのバッファ裁定ロジック回路７４は、いずれかのタグがその出力ボ ート２２を所望であるかどうかを示す４ｉＰｉに加えて、選択されたタグと対応 するバケツ（・の２ビツト・アドレスを出力する。
上記３を法とするカウンタ７６はインクリメン！〜され、これ故に、カウンタ・ イネーブル・ロジック７７から得られた信号に従って、優先順位が変化する。最 も高い優先順位のロケーションが、上記タグ・ステータス・レジスタ・ロジック ・フル／エンプティ・フリップ・フロップ７２ｇ−１によって示されるようなエ ンプティであるならば、又は最も高い優先順位のＤケージ１ンのパケッ１−が伝 達されるということを示ず上記ステータス更新ロジック３５によってクリア信号 が生成されるならば、上記３を法としたカウンタ７６はイネーブルされる。上記 ステータス更新ロジック３５からのクリア信号は、マスター・リセット信号と、 ステータス・リセット・ロジック８０のクロック信号とを結合させる。
第５図には、出カポ−１−・ロジック部７１の詳細なロジック・デザインが示さ れている。４対１アドレス・マルチプレクサ９３ａ−ｂと、上記ボート裁定ロジ ック３４を含むゲート９ｏとが、フリップ・フロップ９４ａ−ｈを含む上記ラッ チ・ロジック３６に結合されている。上記ボート哉定ロジック３４の出力端もま た、上記アドレス・マルチプレクサ９３ａ−ｂに直接結合されている。４を法と しだカウンタ９１が、上記ボート裁定ロジック３４に結合され、現在の優先順位 を決定する。カウンタ・イネーブル・ロジック９２は、上記４を法としたカウン タ９１がインクリメンＩ〜されるがどうかを側面する。
動作に於いては、それぞれの出力ボート・ロジック部７１は、成るアドレスを受 取り、第３図に示されるように、それぞれの入力ボート・ロジック部７０からの 信号を要求する。
要求信号は、上記４を法としだカウンタ９１によって示される優先順位に従って 、上記ボー１−裁定ロジック３４によって処理される。選択された入力ボート２ １の２ビツト・アドレスは、いずれかの要求があるかどうかを示す要求信号に加 えて、上記ラッチ・ロジック３６に出力される。この２ビツト入力ボート・アド レスはまた、上記ラッチ・ロジック３６にもまた出力される選択された入力ボー ト２１からの対応する２ビツト・ステータス・レジスタ・アドレスを選択するこ とを、上記４対１アドレス・マルチプレクサ９３に許す。４ビツトのアドレスが 、選択されたタグ・ビットに関連するバケットをアクセスするように上記マルチ ボー１・・メモリ２３の対応する出力ボート２２に結合されたリード・アドレス を形成する。
上記４を法としだカウンタ９１はインクリメントされ、上記カウンタ・イネーブ ル・ロジック９２からの信号に従って、上記ボート裁定ロジック３４によって使 用された優先順位を変化する。上記カウンタ・イネーブル・ロジック９２は、最 も高い優先順位を有する入力ボート２１が関連する出力ボート２２のための要求 を持たない時、あるいは引受けられる要求をそれが持つ時、及びパケットが伝達 される時には何時でも、インクリメント信号を生成する。ＦＵＬＬＩ信号が、関 連する出力ボート２２に取付けられた出力デバイス即ちスイッチノードが゛′ノ ット・フル″であることを示す、真（ＴＲＵＥ　）である限りは、選択された要 求が送られるだろう。さもな（：ｌれば、上記出力デバイスがもはやフルでなく なるまで、要求は待たれねばならない。
第６図には、上記ステータス更新ロジック３５の訂ｔｉｌｌなロジック・デザイ ンが示されている。それは、クリア化す合併ロジック９８に結合された４ｇの同 一のリード・アドレス・デコーダ９７ａ−ｄから成っている。ｖ）作に於いては 、それぞれのリード・アドレス・デコーダ９７は、入力端にリード・アドレスに 関連覆る要求が有り且つ上記゛′ノット・フル″信号が真であるならば、上記タ グ・スフ゛−タス・レジスタ・ロジック３０の１２個のフリップ・フロップの一 つに対応するたった一つの信号をイネーブル１Ｊる。上記リード・アドレス−ｆ ローダ９フの全てからのクリア信号は、第４図のステータス・りセット・ロジッ ク８Ｑ及びカウ〕／夕・イネーブル・ロジック７７に接続された信号のたった一 つのじットに合併される。せいぜい４個の、かつてアクティブなりリア信号があ る。
第７図に（よ、第４図の入力ボート・ロジック７０に使用されたデマルチプレク サ７３のデザインが示されている。第８図は、第４図の入力ボート・ロジック７ ０に使用された３対１マルチプレクサ７７のデザインを示している。第９図は、 第４図の入力ボート・ロジック７０に使用された３を法としだカウンタ７６のデ ザインを示している。第１０図は、第４図の入力ボート・ロジック７０に使用さ れた３人力裁定ロジック７４のデザインを示しでいる。第１１図は、第６図のス テータス更新ロジック３５に使用するための４対１２デマルチプレクサ回路９７ のデザインを示している。
第１２図には、上記マルチボー１−・メモリ２３の詳細なロジック・デザインが 示されている。上記メモリ２３は、ライ１−・アドレス選択デコード・ロジック ４０と、１２Ｘ４Ｘ３ビツト・アレイ４２に結合されたリード・アドレス行及び 列選択デコード・ロジック４１とから成っている。上記マルチボート・メモリ２ ３は、入力ボート２１でそれぞれのライ１−・アドレスに関連するデータ・バケ ツ１へを含む４個のライト・アドレス及び１２ビツトまで、及び４個のリード・ アドレスまで受入れ、且つそれぞれのりＤツク・サイクルの間出力ボート２２に ４個の対応する１２ピッ１−・データ・パケットを生成するように、デザインさ れている。それぞれのライト・アドレスは、３本のメモリ・セル・アドレス線の １本がイネーブルされるように、上記ライＩ−・アドレス・ロジック４０でデコ ードされる。それぞれのリード・アドレスは、４本の行選択線の１本及び３本の 列選択線の１本がイネーブルされるように、」−３己リード・アドレス・ロジッ ク４１でデコードされる。上記行及び列選択線の交点で上記メモリ・セルは、対 応する出力ボート２２にその内容を！ｊえる。第１２図に示された種々のロジッ ク・ブロックの詳細な配線図は、以下の第１３図から第１８図に示されている。
第１３図は、上記１２Ｘ４Ｘ３ビツト・アレイ４２の構成を示している。それは 、４×３ビツト・メモリ・アレイ５０の１２個の同一の複製品から成っている。
ライト、行、及び列選択線は、それぞれの４×３ビツト・メモリ・アレイ５０に 全て接続されている。第１４図は、上記４×３メモリ・アレイ５０の詳細なロジ ック・デザインを示している。フリップ・フロップ６０ａ−＋は、それぞれ１ビ ツトの情報をストアするために使用される。それぞれの入力ボート２１は、６０ ａ−ｃ、６０ｄ−（等によって示された同一列である３個のフリップ・７０ツブ に対応するライト可能な３個のメモリ・ロケーシ旦ンの排他的セットを持ってい る。それらは、イネーブルされた行及び列選択線の交点に対応するフリップ・フ ロップ６０のビットの値を出力するそれぞれの出力ボート２２のために１つの、 メモリ読出フリップ・７０ツブ選択ロジック６１ａ−ｄの４個の同一の複製品で ある。
第１５図は、４個の同一の２対３デマルチプレクサ５１から成る上記ライト・ア ドレス選択デコード・ロジック４０の詳細なデザインを示している。上記２対３ デマルヂプレクサ５１の詳細なロジック・デザインは、第１６図に示されている 。第１７図は、４個の同一の行及び列デコーダ５２がら成る上記リード・アドレ ス行及び列選択デコード・ロジック４１の詳細なデザインを示している。行及び 列デコーダ５２の詳細なロジック・デザインは、第１８図に示されている。
第１９図は、第２図のマルチボート・メモリ・パケット・スイッチング・ノード ２０のためのタイミング図を示している。外部で発生されたシステム・クロック は、２個のオーバーラツプしない位相φ１及びφ２から成る。φ１の立上り縁は 、全てのリード及びライト・アドレスの発生を起こす。いずれのデータ・パケッ トも及びその対応するタグ及び要求信号も、φ２の立上り縁の前に安定しなけれ ばならない。φ２の立上り縁で、新しいデータ・パケットは上記マルチボー１・ ・メモリ２３にライトされ、上記タグ・ステータス・レジスタ・ロジック３０は 更新される。タグ間の争いは、この時消滅される。上記バッファ及びボート優先 順位もまた、この時イネーブルされたならば、変化される。
従って、マルチ・プロセッサ即ちパラレル・コンピュータ応用のスイッチ・ノー ドとして使用されることができる新規且つ改良されたパケット・スイッチング・ ノードが開示された。上記パケット・スイッチング・ノードは、それらの出力ポ ー１−指定に基いてデータ・パケットをストアし且つ分類するためにマルチ・メ モリに使用する。上記パケツｌ−・スイッチング・ノードは、指定が異なった出 力ボートであるノードの入カポ−１・に到達するデータ・パケット間の回線争奪 の問題を排除する。本発明はまた、改良された性能及びより高いスルーブツトを イｉするバケツ１〜・スイッチング・ノードを提供する。
前述の実施例は、木光明の原理の応用を示している多くの特定の実施例のいくつ かを単に示しているということが理解されるべきである。明らかに、多種多様の 他の配置が、木発明の精神及び範囲から逸脱することなしに、当業考によッテ容 易に工夫されることができる。例えば、本発明は、コンピュータのための相互接 続デバイスにのみに関する使用に限定されない。それはまた、遠距離通信分野の 応用を有しており、遠距離通信装置２等での使用のために適合されることもでき る。特に、本発明を使用する相互接続ネツ１、ワークは、データ、パケットとじ てデータと音声情報の両方を伝達するテレホン・システムを接続するために使用 されることができる。
１８表昭６２−５００９０２　（１３）Ｆｉｇ、　１８゜

Claims (12)

    【特許請求の範囲】
  1. １．データ・パケットが加えられるべき出力ポート指定を表わす信号を含む加え られたデータ・パケットを処理するパケット・スイッチ・ノードで、 複数の入力ポートと、 複数の出力ポートと、 前記入力ポートと出力ポートとの間に結合されたマルチポート・メモリで、前記 入力ポートのそれぞれに加えられた前記データ・パケットのストレージのために 利用できる所定の数のメモリ・ロケーションを有する、マルチポート・メモリと 、及び 前記メモリのデータ・パケットのストレージを、及び前記経路指定タグ信号に従 って前記出力ポートヘのそれらの経路指定を制御するために、前記入力ポート、 出力ポート及び前記マルチポート・メモリに結合された制御ロジックと、を具備 するパケット・スイッチング・ノード。
  2. ２．前記制御ロジックは、 前記経路指定タグ信号と、前記メモリのメモリ・ロケーションのそれぞれのフル ／エンブティ・ステータスを表わすステータス信号とをストアするための、前記 入力ポート及び前記メモリに結合されたステータス・レジスタを具備する、請求 の範囲第１項のパケット・スイッチング・ノード。
  3. ３．前記制御ロジックはさらに、 前記メモリ・ロケーションのフル／エンブティ・ステータスを監視し、前記ステ ータス・レジスタのレジスタに前記経路指定タグ信号をライトし、且つ選択され たメモリ・ロケーションに前記経路指定タグ信号に対応するデータ・パケットを ライトするための、前記入力ポート，前記メモリ及び前記ステータス・レジスタ に結合された優先順位エンコーダ・ロジック を具備する、請求の範囲第２項のパケット・スイッチング・ノード。
  4. ４．前記制御ロジックはさらに、 前記メモリ・ロケーションから前記データ・パケットをリードし且つ所定の優先 順位裁定要綱に基いて対応する経路指定タグ信号の確認された出力ポートにそれ らを加えるための、前記ステータス・レジスタ．前記メモリ及び前記出力ポート に結合された裁定ロジック を具備する、請求の範囲第３項のパケット・スイッチング・ノード。
  5. ５．前記裁定ロジックはさらに、 同一出力ポートからの出力のために争い且つそれらからの特定の経路指定タグを ランダムに選択する同一入力ポートに入る経路指定タグ問で裁定するバッファ裁 定ロジックと、及び 同一出力ポートのために争い且つその特定の出力ポートからの出力のためにそれ らからの一つの経路指定タグを選択する、前記バッファ裁定ロジックによって伝 達された全ての経路指定タグ間で裁定する前記パッファ裁定ロジックに結合され たポート裁定ロジックと、 を具備する、請求の範囲第４項のパケット・スイッチング・ノード。
  6. ６．前記裁定ロジックはさらに、 前記ポート裁定ロジックによって選沢されたそれらの経路指定タグ信号に対応す るデータ・パケットのための適当な出力ポートを通るデータ・パケットの出力を 制御するリード・アドレスを発生するアドレス発生ロジックを具備する、請求の 範囲第５項のパケット・スイッチング・ノード。
  7. ７．上記出力ポートのいずれかに加えられた上記データ・パケットに対応する上 記レジスタのフル／エンブティ・ステータスをリセットする信号を発生するステ ータス更新ロジック をさらに具備する、請求の範囲第６項のパケット・スイッチング・ノード。
  8. ８．データ・パケットが加えられるべき出力ポート指定を表わす信号を含む加え られたデータ・パケットを処理するパケット・スイッチ・ノードで、 複数の入力ポートと、 複数の出力ポートと、 前記入力ポートと出力ポートとの間に結合されたマルチポート・メモリで、前記 入力ポートのそれぞれに加えられた前記データ・パケットのストレージのために 利用できる所定の数のメモリ・ロケーションを有する、マルチポート・メモリと 、及び 前記メモリのデータ・パケットのストレージを、及び前記経路指定タグ信号に従 って前記出力ポートヘのそれらの経路指定を制御するために、前記入力ポート、 出力ポート及び前記マルチポート・メモリに結合され、前記経路指定タグ信号を ストアするためのストレージ・レジスタと、前記マルチポート・メモリにストア されたデータ・パケットの出力優先順位を決定するための裁定ロジックとを具備 する制御ロジックと、 を具備するパケット・スイッチング・ノード。
  9. ９．データ・パケットが加えられるべき出力ポート指定を表わす経路指定信号を 含む加えられたデータ・パケットを処理するパケット・スイッチ・ノードで、複 数の入力ポートと、 複数の出力ポートと、 前記入力ポートと出力ポートとの間に結合されたマルチポート・メモリで、前記 入力ポートのそれぞれに加えられた前記データ・パケットのストレージのために 利用できる所定の数のメモリ・ロケーションを有する、マルチポート・メモリと 、 前記データ・パケットのそれぞれに関連する前記経路指定タグ信号をストアする ための、ステータス・レジスタと、同ー出力ポートからの出力のために争う同一 入力ポートに入るデータ・パケットに対応する経路指定タグ問で裁定し、且つそ れらからの特定の経路指定タグをランダムに選択する、前記ステータス・レジス タに結合されたバッファ裁定ロジックと、及び データ・パケットが同一出力ポートのために争われた、上記バッファ裁定ロジッ クによって伝達された全ての経路指定タグ間で裁定し、且つその特定の出力ポー トからの出力のために選択されたデータ・パケットに対応するそれらからーつの 経路指定タグを選択する、前記バッファ裁定ロジックに結合されたポート裁定ロ ジックと を具備する、パケット・スイッチング・ノード。
  10. １０．加えられたデータ・パケットが適当な出力ポートに前記データ・パケット を経路指定するために加えられるべきである出力ポート指定を表わす経路指定タ グ信号を含む加えられたデータ・パケットを処理するための方法で、前記経路指 定タグ信号に従って、所定のメモリ・ロケーションに前記入力ポートのそれぞれ に達する前記データ・バケットをストアすることと、 同一入力ポートに入り、且つ同一出力ポートのために争うデータ・パケット間で 選択することと、同一出力ポートのために争う異なった入力ポートに入ったデー タ・パケット間で選択することと、及び前記経路指定タグ信号で確認された出力 ポートに前記選択されたデータ・パケットを加えることと、のステップを具備す る方法。
  11. １１．加えられたデータ・パケットが適当な出力ポートに前記データ・パケット を経路指定するために加えられるべきである出力ポート指定を表わす経路指定タ グ信号を含む加えられたデータ・パケットを処理するための方法で、前記経路指 定タグ信号に含まれたそれらの出力ポート指定に基いて前記データ・パケットを ストアすることと、同一入力ポートに入り、且つ同一出力ポートに指定されたデ ータ・パケット間で裁定することと、異なった入力ポートに入り、且つ同一出力 ポートに指定されたデータ・パケット間で裁定することと、及び前記経路指定タ グ信号で確認された前記出力ポートに対する上記２つの裁定処理の間、選択され たデータ・パケットを経路指定することと、 のステップを具備する方法。
  12. １２．加えられたデータ・パケットが適当な出力ポートに前記データ・パケット を経路指定するために加えられるべきである出力ポート指定を表わす経路指定タ グ信号を含む加えられたデータ・パケットを処理するための方法で、所定のメモ リ・ロケーションに前記データ・パケットをストアすることと、 前記経路指定タグ信号に含まれたそれらの出力ポート指定に基いて前記データ・ パケットをストアすることと、同一入力ポートに入り、且つ同一出力ポートに指 定されたそれらのデータ・パケット間で裁定することと、異なった入力ポートに 入り、且つ同一出力ポートに指定されたそれらのデータ・パケット間で裁定する ことと、及び前記経路指定タグ信号で確認された前記出力ポートヘの、前記メモ リ・ロケーションからの上記裁定処理の間、選択されたデータ・パケットを経路 指定することと、のステップを具備する方法。
JP50450585A 1984-10-18 1985-09-26 パケット・スイッチド・マルチポ−ト・メモリｎ×ｍスイッチ・ノ−ド及び処理方法 Expired - Lifetime JPH0638607B2 (ja)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US661996 1984-10-18
US06/661,996 US4630258A (en) 1984-10-18 1984-10-18 Packet switched multiport memory NXM switch node and processing method
PCT/US1985/001840 WO1986002512A1 (en) 1984-10-18 1985-09-26 PACKET SWITCHED MULTIPORT MEMORY NxM SWITCH NODE AND PROCESSING METHOD

Publications (2)

Publication Number Publication Date
JPS62500902A true JPS62500902A (ja) 1987-04-09
JPH0638607B2 JPH0638607B2 (ja) 1994-05-18

Family

ID=24655970

Family Applications (1)

Application Number Title Priority Date Filing Date
JP50450585A Expired - Lifetime JPH0638607B2 (ja) 1984-10-18 1985-09-26 パケット・スイッチド・マルチポ−ト・メモリｎ×ｍスイッチ・ノ−ド及び処理方法

Country Status (8)

Country Link
US (1) US4630258A (ja)
EP (1) EP0198010B1 (ja)
JP (1) JPH0638607B2 (ja)
KR (1) KR900006791B1 (ja)
DE (1) DE3576775D1 (ja)
IL (1) IL76532A0 (ja)
SG (1) SG38090G (ja)
WO (1) WO1986002512A1 (ja)

Families Citing this family (53)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4837676A (en) * 1984-11-05 1989-06-06 Hughes Aircraft Company MIMD instruction flow computer architecture
US4696000A (en) * 1985-12-12 1987-09-22 American Telephone And Telegraph Company, At&T Bell Laboratories Nonblocking self-routing packet and circuit switching network
BE904100A (fr) * 1986-01-24 1986-07-24 Itt Ind Belgium Systeme de commutation.
US4748618A (en) * 1986-05-21 1988-05-31 Bell Communications Research, Inc. Telecommunications interface
US4754451A (en) * 1986-08-06 1988-06-28 American Telephone And Telegraph Company, At&T Bell Laboratories N-by-N "knockout" switch for a high-performance packet switching system with variable length packets
JPH08214008A (ja) * 1987-02-06 1996-08-20 Fujitsu Ltd 自己ルーチングスイッチ
US4763122A (en) * 1987-03-18 1988-08-09 International Business Machines Corporation Parallel switching with round robin priority
US4831616A (en) * 1987-03-31 1989-05-16 Huber David R Multiplexed fiber optics wideband data distribution system
US4910731A (en) * 1987-07-15 1990-03-20 Hitachi, Ltd. Switching system and method of construction thereof
US5365519A (en) 1991-03-05 1994-11-15 Hitachi, Ltd. ATM switch1ng system connectable to I/O links having different transmission rates
US6330240B1 (en) 1987-04-24 2001-12-11 Hitachi, Ltd. ATM cell switching system
US5117420A (en) * 1987-04-27 1992-05-26 Thinking Machines Corporation Method and apparatus for routing message packets
US4984235A (en) * 1987-04-27 1991-01-08 Thinking Machines Corporation Method and apparatus for routing message packets and recording the roofing sequence
USRE36751E (en) * 1987-07-15 2000-06-27 Hitachi, Ltd. ATM switching system connectable to I/O links having different transmission rates
US5367688A (en) * 1987-09-04 1994-11-22 Digital Equipment Corporation Boot system for distributed digital data processing system
US5136718A (en) * 1987-09-04 1992-08-04 Digital Equipment Corporation Communications arrangement for digital data processing system employing heterogeneous multiple processing nodes
US4887076A (en) * 1987-10-16 1989-12-12 Digital Equipment Corporation Computer interconnect coupler for clusters of data processing devices
US4845722A (en) * 1987-10-16 1989-07-04 Digital Equipment Corporation Computer interconnect coupler employing crossbar switching
US4885739A (en) * 1987-11-13 1989-12-05 Dsc Communications Corporation Interprocessor switching network
JP2667868B2 (ja) * 1988-04-06 1997-10-27 株式会社日立製作所 セル・スイッチング・システム
US5233603A (en) * 1988-04-21 1993-08-03 Nec Corporation Packet switch suitable for integrated circuit implementation
US4891803A (en) * 1988-11-07 1990-01-02 American Telephone And Telegraph Company Packet switching network
US5046000A (en) * 1989-01-27 1991-09-03 International Business Machines Corporation Single-FIFO high speed combining switch
US5249292A (en) * 1989-03-31 1993-09-28 Chiappa J Noel Data packet switch using a primary processing unit to designate one of a plurality of data stream control circuits to selectively handle the header processing of incoming packets in one data packet stream
DE4004956A1 (de) * 1990-02-19 1991-08-22 Philips Patentverwaltung Koppelelement fuer ein asynchrones zeitvielfachuebermittlungssystem
EP0521027A4 (en) * 1990-03-22 1994-10-19 Australian & Overseas Telecom Multicasting method for a telecommunications network
US5265257A (en) * 1990-06-22 1993-11-23 Digital Equipment Corporation Fast arbiter having easy scaling for large numbers of requesters, large numbers of resource types with multiple instances of each type, and selectable queuing disciplines
JP2770936B2 (ja) * 1990-12-18 1998-07-02 インターナショナル・ビジネス・マシーンズ・コーポレイション 通信ネットワークおよび通信チャンネルをつくる方法
US5825773A (en) * 1991-03-20 1998-10-20 Hitachi, Ltd. Switching system for transferring broadcast packet held in broadcast buffer received from input port to output ports according to the state of each output port
US5321813A (en) * 1991-05-01 1994-06-14 Teradata Corporation Reconfigurable, fault tolerant, multistage interconnect network and protocol
JP3679813B2 (ja) * 1991-07-22 2005-08-03 株式会社日立製作所 並列計算機
SE515148C2 (sv) * 1993-06-23 2001-06-18 Ericsson Telefon Ab L M Styrning av cellväljare
DE4343588A1 (de) * 1993-12-21 1995-06-22 Sel Alcatel Ag Verfahren und Einrichtung zur zufälligen Auswahl einer von N gleichen Einheiten, sowie Koppelelement, Koppelnetz und Vermittlungsstelle damit
WO1996007139A1 (en) * 1994-09-01 1996-03-07 Mcalpine Gary L A multi-port memory system including read and write buffer interfaces
JP3269273B2 (ja) * 1994-09-02 2002-03-25 三菱電機株式会社 セル交換装置及びセル交換システム
US5566171A (en) * 1995-03-15 1996-10-15 Finisar Corporation Multi-mode high speed network switch for node-to-node communication
GB2300088B (en) * 1995-04-19 1999-06-16 Northern Telecom Ltd Telecommunications switches
US6185222B1 (en) * 1995-09-28 2001-02-06 Cisco Technology, Inc. Asymmetric switch architecture for use in a network switch node
SE520465C2 (sv) * 1997-07-11 2003-07-15 Ericsson Telefon Ab L M Redundansterminering i flerstegsväxel för ATM-trafik
US6611895B1 (en) * 1998-06-08 2003-08-26 Nicholas J. Krull High bandwidth cache system
US6301637B1 (en) * 1998-06-08 2001-10-09 Storage Technology Corporation High performance data paths
US6563818B1 (en) * 1999-05-20 2003-05-13 Advanced Micro Devices, Inc. Weighted round robin cell architecture
US6412002B1 (en) 1999-11-15 2002-06-25 Ncr Corporation Method and apparatus for selecting nodes in configuring massively parallel systems
US6418526B1 (en) 1999-11-15 2002-07-09 Ncr Corporation Method and apparatus for synchronizing nodes in massively parallel systems
US6519697B1 (en) 1999-11-15 2003-02-11 Ncr Corporation Method and apparatus for coordinating the configuration of massively parallel systems
US6745240B1 (en) 1999-11-15 2004-06-01 Ncr Corporation Method and apparatus for configuring massively parallel systems
US6717951B2 (en) * 1999-12-29 2004-04-06 Intel Corporation Method and apparatus for determining priority of network packets
CN1366402B (zh) * 2002-02-05 2010-10-13 威盛电子股份有限公司 分组交换的负载平衡装置
DE10212374B4 (de) * 2002-03-20 2005-12-08 Siemens Ag Lastverteilung auf periphere Einrichtungen eines paketbasierten Vermittlungssystems
US20050166252A1 (en) * 2004-01-06 2005-07-28 Sharp Laboratories Of America, Inc. Personal video recorder
US20140050221A1 (en) * 2012-08-16 2014-02-20 Stmicroelectronics, Inc. Interconnect arrangement
CN112383474B (zh) * 2020-10-15 2022-11-01 中国科学院国家空间科学中心 一种多端口的SpaceFibre路由IP
CN114826930B (zh) * 2022-04-20 2024-02-23 山东云海国创云计算装备产业创新中心有限公司 一种实现扁平式蝴蝶型网络拓扑的系统及方法

Family Cites Families (24)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3629846A (en) * 1970-06-11 1971-12-21 Bell Telephone Labor Inc Time-versus-location pathfinder for a time division switch
US4153932A (en) * 1974-03-29 1979-05-08 Massachusetts Institute Of Technology Data processing apparatus for highly parallel execution of stored programs
US3962706A (en) * 1974-03-29 1976-06-08 Massachusetts Institute Of Technology Data processing apparatus for highly parallel execution of stored programs
US4145733A (en) * 1974-03-29 1979-03-20 Massachusetts Institute Of Technology Data processing apparatus for highly parallel execution of stored programs
US4149240A (en) * 1974-03-29 1979-04-10 Massachusetts Institute Of Technology Data processing apparatus for highly parallel execution of data structure operations
FR2305907A1 (fr) * 1975-03-27 1976-10-22 Materiel Telephonique Dispositif de controle destine a un reseau de commutation pour voies multiplexees dans le temps
US3979733A (en) * 1975-05-09 1976-09-07 Bell Telephone Laboratories, Incorporated Digital data communications system packet switch
US4074233A (en) * 1976-06-30 1978-02-14 Norlin Music, Inc. Selection switch memory circuit
US4130885A (en) * 1976-08-19 1978-12-19 Massachusetts Institute Of Technology Packet memory system for processing many independent memory transactions concurrently
US4128882A (en) * 1976-08-19 1978-12-05 Massachusetts Institute Of Technology Packet memory system with hierarchical structure
US4201890A (en) * 1978-03-17 1980-05-06 International Telephone And Telegraph Multiport digital switching element
US4229790A (en) * 1978-10-16 1980-10-21 Denelcor, Inc. Concurrent task and instruction processor and method
FR2447652A1 (fr) * 1979-01-24 1980-08-22 Materiel Telephonique Operateur pour reseau de commutation de donnees numeriques par paquets
FR2458196A1 (fr) * 1979-06-01 1980-12-26 Materiel Telephonique Niveau de commutation d'un operateur pour reseau de commutation de donnees numeriques par paquets
US4365292A (en) * 1979-11-26 1982-12-21 Burroughs Corporation Array processor architecture connection network
US4314233A (en) * 1979-12-18 1982-02-02 Burroughs Corporation Four-wire speed independent arbiter switch for digital communication networks
US4450554A (en) * 1981-08-10 1984-05-22 International Telephone And Telegraph Corporation Asynchronous integrated voice and data communication system
JPS5857940A (ja) * 1981-10-03 1983-04-06 松下電工株式会社 積層板
JPS58150349A (ja) * 1982-03-02 1983-09-07 Mitsubishi Electric Corp パケツト通信ネツトワ−ク
US4482996A (en) * 1982-09-02 1984-11-13 Burroughs Corporation Five port module as a node in an asynchronous speed independent network of concurrent processors
FR2538976A1 (fr) * 1982-12-29 1984-07-06 Servel Michel Systeme de commutation de paquets synchrones de longueur fixe
JPS59135953A (ja) * 1983-01-26 1984-08-04 Fujitsu Ltd デ−タ送出経路決定方式
FR2549673B1 (fr) * 1983-07-19 1989-06-30 Thomson Csf Mat Tel Commutateur elementaire pour autocommutateur utilisant une technique de multiplexage asynchrone
JP5857940B2 (ja) 2012-10-31 2016-02-10 株式会社デンソー 無線通信機

Also Published As

Publication number Publication date
KR900006791B1 (ko) 1990-09-21
US4630258A (en) 1986-12-16
WO1986002512A1 (en) 1986-04-24
IL76532A0 (en) 1986-01-31
EP0198010A1 (en) 1986-10-22
EP0198010B1 (en) 1990-03-21
DE3576775D1 (de) 1990-04-26
SG38090G (en) 1990-08-03
KR880700566A (ko) 1988-03-15
JPH0638607B2 (ja) 1994-05-18

Similar Documents

Publication Publication Date Title
JPS62500902A (ja) パケット・スイッチド・マルチポ−ト・メモリｎ×ｍスイッチ・ノ−ド及び処理方法
KR900006792B1 (ko) 패킷 스위칭 노드용 로드 평형 회로장치
KR900006793B1 (ko) 패킷 스위치 다중 대기행렬 NxM 스위치 노오드 및 처리 방법
Tamir et al. High-performance multi-queue buffers for VLSI communications switches
Tamir et al. Dynamically-allocated multi-queue buffers for VLSI communication switches
EP0334954B1 (en) Layered network
Mukherjee et al. The Alpha 21364 network architecture
CN105005546B (zh) 一种内置交点队列的异步axi总线结构
JPH02503244A (ja) メッセージパケットのルーティング方法とその装置
JPH05508497A (ja) 非順次源アクセスのための方法およびその装置
Coates et al. The Post Office experience: Designing a large asynchronous chip
JPH07210527A (ja) クラスタ制御装置およびクラスタ接続多重処理システム
Bartic et al. Highly scalable network on chip for reconfigurable systems
JPH05506528A (ja) 並列処理アレイ用のスケーリング可能なプロセッサ間及びプロセッサ・ｉ／ｏメッセージシステム
Lang et al. Nonuniform traffic spots (NUTS) in multistage interconnection networks
US11704270B2 (en) Networked computer with multiple embedded rings
JPH0818565A (ja) データ処理装置
Gavrilovska Attaining high performance communications: a vertical approach
US6976142B1 (en) Method and system to provide simultaneous access by multiple pipelines to a table
Theiss Modularity, routing and fault tolerance in interconnection networks
Cohen et al. ATOMIC: A Low-Cost, Very High-Speed LAN
Juang et al. Resource sharing interconnection networks in multiprocessors
Liu An On-Chip Packet Router for a Large-Scale Neuromorphic Computer
EP0293616A2 (en) Dynamic switch with task allocation capability
Oral Performance modeling and analysis of multicast infrastructure for high-speed cluster and grid networks