JP2000516423A - 高速スイッチング装置 - Google Patents

Abstract

(57)【要約】 ネットワークにおいてソース（１０）とデスティネーション（３０）との間でデータパケットをスイッチングするルーター（２０）が複数個の入力ポートを有しており、各入力ポートはデータハンドラーを有している。該データハンドラーは、データパケットを１個又はそれ以上の固定長セルに分割する。ルーター（２０）は、少なくともそのうちの１つがデータパケットをデスティネーション（３０）に対して経路付けするためのものである複数個の出力ポートと、複数個のメモリバンクに分割されているメモリとを有している。入力スイッチは入力ポートから固定長セルを受取り且つ単一の出力スイッチが前記メモリから受取ったセルを適宜の出力ポートに対して経路付けする。

Description

【発明の詳細な説明】 高速スイッチング装置 発明の詳細な説明背景 本発明は、大略、データルーチングシステムに関するものであって、更に詳細 には、ネットワークを介してパケットのルーチング即ち経路付けを行う方法及び 装置に関するものである。 パケット交換通信システムにおいては、ルーターが１つのポート上でデータ又 は制御情報を包含するパケットを受取り、且つ該パケット内に含まれているデス ディネーション情報に基づいて、該パケットを別のポートからデスティネーショ ン（又は中間デスティネーション）へ経路付けを行うスイッチング装置である。 従来のルーターは、特定のパケットに対して適切な出力ポートを決定するため に、パケット内の最初のデータブロック内に含まれているヘッダー情報を評価す ることによってこのスイッチング機能を実行する。 ルーターを介してのパケットの効率的なスイッチングが極めて重要である。図 １ａを参照すると、従来のルーターは、各々が入力バッファ（メモリ）４を包含 している複数個の入力ポート２と、スイッチ ング装置６と、複数個の出力ポート８とを有している。 入力ポート２において受取られたデータパケットは、少なくとも一時的に入力 バッファ４内に格納され、一方各パケットと関連するデスティネーション（宛先 ）情報がデコードされてスイッチング装置６を介しての適切なスイッチングを決 定する。明らかに、デコードプロセスがパケットが受取られる速度と比較して長 くかかり過ぎる場合には、より大きなメモリ要素が必要とされる。更に、パケッ トは、スイッチング装置が接続を行うことが不可能である場合には、デスティネ ーション情報がデコードされた後に入力バッファ内に留まることが強制される場 合がある。ブロッキング（ｂｌｏｃｋｉｎｇ）は、所望の出力ポートが使用不可 能（ポートがビジーであり、例えば、異なる入力ポートからの別のパケットをル ーチングしている）であるために、スイッチにおいて接続を形成することが不可 能な条件のことを意味する。各入力バッファ４の寸法は、例えば、ライン入力速 度、ルックアップ処理の速度、スイッチング装置に対するブロッキング特性等の 多数のファクタに依存する。 然しながら、これらのタイプのルーターは多くの観点において効率が悪い。各 入力ポートは専用の入 力バッファを有しており、且つ入力ポート間のメモリ共有はその設計において設 けられていない。各入力バッファは、与えられたポートに対する最大の処理能力 条件を満足するために寸法決定されねばならない。然しながら、設計トレード（ コスト）が、しばしば、各ポートに対してより小型のバッファとすることを必要 とする。より小型のバッファの場合には、ブロッキング条件のためにパケットが ドロップ即ち落されて削除される可能性が発生する。ルーターにおいては典型的 に余分のメモリ能力が存在しているが（入力ポートの様々な利用に起因して）、 その余分のものを利用する手段が与えられていない。 パケットのドロップ即ち落されることを防止するために、設計者は「非ブロッ キング」ルーターを開発した。図１ｂを参照すると、従来の「非ブロッキング」 ルーターは、各々が入力バッファ（メモリ）４を包含している複数個の入力ポー ト２と、スイッチング装置６と、各々が出力バッファ９を具備する複数個の出力 ポートとを有している。ブロッキング条件を開示するために、各出力ポート８は 出力バッファ９を包含する形態とされている。各出力ポートは同時的にパケット を出力すると共に後の時間において出力するための新たなパケットを受取ること が可能である。出力バッファの寸法が充分に大きなも のである場合には、データパケットがドロップ即ち落されることはない。 然しながら、これらの設計はメモリ容量及びコストの点において更に効率が悪 い。この場合も、各出力ポートは専用の出力バッファを有しており且つ出力ポー ト間のメモリ共有はこの設計においては設けられていない。各出力バッファは、 与えられたポートに対する最大の処理能力条件を満足するために（その「非ブロ ッキング」特性を維持するために）寸法設定されねばならない。典型的に、ルー ターにおいては更に余分のメモリ能力が存在しているが（入力ポート及び出力ポ ートの多様な利用に起因して）、その余分なものを利用する手段が与えられてい ない。これらのタイプの装置を介して移動されるデータの量をサポートするため に必要とされるものよりも２倍の量及び帯域幅のメモリが使用されねばならない 。発明の要約 一般的に、１つの側面においては、本発明は各々がデータハンドラーを包含す る複数個の入力ポートを具備するネットワークにおいてソース（発信元）とデス ティネーション（宛先）との間でデータパケットをスイッチング即ち交換するた めのルーターを提供している。該データハンドラーはデータパケットを１個又は それ以上の固定長のセルへ分割する。 本ルーターは複数個の出力ポートを有しており、少なくともそのうちの１つはデ ータパケットをデスティネーションに対してルーチング即ち経路付けするための ものであり且つ本ルーターは複数個のメモリバンクへ分割されているメモリを有 している。入力スイッチが入力ポートから固定長のセルを受取り且つセルスロッ トタイムスパン内の単一のセルを各メモリバンクへ書込む。出力スイッチがメモ リから受取ったセルを適宜の出力ポートに対して経路付けする。 本発明の側面は以下の特徴を包含している。入力スイッチはメモリ内の非隣接 位置からデータパケットの検索を可能とするためにデータパケット内のセルをリ ンクするためのリンクエンジンを有している。本ルーターは、更に、１個又はそ れ以上の間接セルを発生するための間接セル発生器を有している。該リンクエン ジンは、データパケットの連続するセルが格納されているメモリ内の位置をトラ ッキング即ち追いかけ、且つ間接セル内に格納するためにデータパケット内の各 セルのメモリ内のアドレスを供給する。 本入力スイッチは、メモリに対するデータパケットの書込を時分割多重し、従 って入力ポートからの連続したセルはメモリ内の連続したバンクへ書込ま れる。本入力スイッチは、データパケットと関連する入力スイッチにおいて受取 られた最初のセルからのキー情報を抽出するためのキー読取エンジンを有してい る。本ルーターは、更に、それからキー情報を受取るために入力スイッチへ結合 されている制御器を有している。該制御器は入力スイッチから受取られたキー情 報からデスティネーション情報をデコードし且つメモリから出力ポートへデータ パケットのルーチング即ち経路付けを画定する通知を出力する。 出力ポートは制御器からの通知を受取るための結果プロセサを有しており且つ メモリから出力ポートへのデータパケットの転送を開始させる。本入力スイッチ はメモリから出力スイッチへの転送をスケジュールするための予約テーブルを有 している。該出力スイッチは、出力ポートへの該通知の経路付けを行い、その後 に、出力ポートは入力スイッチに対してメモリからのデータパケットを出力スイ ッチを介して出力ポートへ転送することの要求を発行する。出力ポートからの要 求は予約テーブル内に格納される。メモリから出力スイッチへセルを転送するた めの要求は時間ドメイン多重化され、従って１つのセルスロットタイムスパン期 間中に、高々、単一の読取要求が処理するためにメモリ内の各バンクに対して発 行される。メモリは、１つのセルスロットタイ ムスパン内においてバンク当たり高々単一のセルを出力する。 本発明の１つの利点は、スイッチを介してのパケットを効率的に管理し且つ経 路付けするスイッチングアーキテクチュアを設けることによって高価な高速メモ リ内にパケットを格納することの必要性なしに、ライン速度においてルーターを 介してパケットをスイッチ即ち交換させることが可能であるということである。 その他の利点及び特徴は以下の説明及び請求の範囲から明らかとなる。図面の簡単な説明 図１ａ及び１ｂは従来のルーター装置のブロック図である。 図２ａは本発明の１実施例に基づくデータルーチングシステムの概略ブロック 図である。 図２ｂは本発明の１実施例に基づくルーターの概略ブロック図である。 図３は本発明の１実施例に基づく入力ポートの概略ブロック図である。 図４ａは本発明の１実施例に基づく入力ポートから入力スイッチへ転送するタ イミング及び順番を包含するルーターの概略ブロック図である。 図４ｂは本発明の１実施例に基づく入力ポートと 入力スイッチとの間で転送されるセルに対するデータ構造である。 図５ａは本発明の１実施例に基づく入力スイッチの概略ブロック図である。 図５ｂは本発明の１実施例に基づく入力ポートからメモリへ転送するタイミン グ及び順番を包含するルーターの概略ブロック図である。 図６は本発明の１実施例に基づくキーバッファ内に格納されているルート要求 に対するデータ構造である。 図７は本発明の１実施例に基づく間接セルに対するデータ構造である。 図８は本発明の１実施例に基づく入力スイッチとメモリバンクとの間で転送さ れるセルに対するデータ構造である。 図９は本発明の１実施例に基づく予約テーブルの概略ブロック図である。 図１０は本発明の１実施例に基づく予約テーブルをローディングするプロセス のフローチャートである。 図１１ａは本発明の１実施例に基づくメモリの概略ブロック図である。 図１１ｂは本発明の１実施例に基づく入力ポートからメモリへの転送のタイミ ング及び順番を包含す るルーターの概略ブロック図である。 図１２は本発明の１実施例に基づくメモリバンクから出力スイッチへのセル出 力に対するデータ構造である。 図１３は本発明の１実施例に基づく制御器の概略ブロック図である。 図１４は本発明の１実施例に基づく制御器から出力スイッチへ転送される出力 要求に対するデータ構造である。 図１５は本発明の１実施例に基づく出力スイッチの概略ブロック図である。 図１６は本発明の１実施例に基づく出力スイッチから出力ポートへ転送される セルに対するデータ構造である。 図１７は本発明の１実施例に基づく出力ポートに対する概略ブロック図である 。 図１８は本発明の１実施例に基づくルーターを介してのパケットのルーチング のプロセスに対するフローチャートである。 図１９は本発明の１実施例に基づくルーターの概略ブロック図であって、入力 ポートからそれの適切な出力ポートへパケットを経路付けする場合にルーターに よって実行される動作の流れを追従するためのシーケンス流れ情報を包含する概 略ブロック図で ある。 図２０は本発明の１実施例に基づく多機能ポートの概略ブロック図である。 図２１は本発明の１実施例に基づく多機能ポートを包含するルーターの概略ブ ロック図である。詳細な説明 図２ａを参照すると、パケットスイッチングシステムにおいて、ソース（発信 元）１０が１つ又はそれ以上のデスティネーション（宛先）３０へパケットを送 信するために１個又はそれ以上のルーター２０へ接続されている。各ルーターは 、種々のソース及びデスティネーションへ接続されている複数個のポートを有し ている。ソース１０からのパケットは、そのデスティネーションに到達する前に 、１個を超えるルーターを介して通過することが可能である。 図２ｂを参照すると、各ルーター２０は入力スイッチ１００と、出力スイッチ １０２と、１個又はそれ以上のメモリバンク１０５を包含するメモリ１０４と、 制御器１０６と、複数個の入力及び出力ポート１０７及び１０８とを有している 。ルーチングテーブルを格納するために、制御器メモリ１０９が制御器１０６と 関連している。入力スイッチ１００は各入力ポート１０７へ接続されており、一 方出力スイッチ１０２はルーター２０における各出力ポート１ ０８へ接続されている。１実施例においては、ルーター２０は８個の入力及び出 力ポート１０７及び１０８を有している。 動作について説明すると、パケットが入力ポート１０７において受取られ、入 力スイッチ１００へ転送され、且つ一時的にメモリ１０４内に格納される。該パ ケットがスイッチ１００によって受取られると、そのパケット内の最初のデータ ブロックからキーが読取られ且つ制御器１０６へ転送される。そのキーは、パケ ット内のデータの最初のブロックと関連するヘッダーフィールドから派生される デスティネーション情報及びその他の情報（ソースＩＤ、流れＩＤ等）を包含し ている。 制御器１０６内のルートルックアップエンジン１１０は、キー情報にも基づい てツリーをベースとしたサーチを実行し且つデスティネーションと関連している 出力ポートを含む結果を返す。その結果はルーター２０を介してパケットを経路 付けするためのその他の情報（ソースＩＤ、流れＩＤ、パケット長等）と結合さ れ且つ制御器１０６から出力スイッチ１０２に対する通知として供給される。出 力スイッチ１０２はその通知を識別された出力ポート１０８へ転送する。該通知 情報を受取ると、出力ポート１０８はメモリ１０４から出力スイッチ１０２を介 して適切な 出力ポート１０８へパケットの転送を開始する。 図３を参照すると、各入力ポート１０７はライン入力インターフェース３００ と、データハンドラー３０４と、セル出力ポート３０６とを有している。パケッ トはライン入力インターフェース３００において受取られる。パケットが受取ら れると、データハンドラー３０２は受取ったパケットを固定長セルへ分割する。 本発明の１実施例においては、各セルの長さは８０バイトであり１６バイトが内 部ヘッダー（制御情報）であり且つ６４バイトがセルデータである。データハン ドラーが入って来るパケットを固定長セルへ分割すると、それはセル出力ポート ３０６を介して同期的にセルを入力スイッチ１００へ出力する。 次に、図４ａを参照すると、単一のセル４５０が入力ポート１０７から各セル スロット「Ｔ」において入力スイッチ１００へ転送される。与えられたセルスロ ット「Ｔ」に対して、入力ポート１０７は全部で「Ｎ」のセルを受取り、尚「Ｎ 」は入力ポートの数に等しい。 入力ポート１０７から入力スイッチ１００へ転送される各セル４００に対する データフォマットは、図４ｂに示したように、内部ヘッダー４０２とデータフィ ールド４０４とを有している。内部ヘッダー ４０２はタイプフィールド４０６と、ストリームフィールド４０８とパケットヘ ッダーフィールド４１０とを有している。 タイプフィールド４０６は入力ポートから転送されるべきセルのタイプを表わ す。各セルスロット（１実施例においては２０クロックサイクル）において、入 力ポートがデータセル、間接セルプレースホルダー、又は遅延間接セルホルダー のいずれかを転送することが可能である。データセルは入って来るパケットと関 連するデータを包含している。間接セルプレースホルダーは空のセルであり、且 つメモリ１０４内のセルの格納に対する間接アドレス動作に関連して使用される 。遅延間接セルプレースホルダーは、間接アドレス動作を必要とするデータスト リームが、そのデータストリームと関連する最後の間接アドレス用セルをメモリ １０４へ書込むための指定されている時間の前の時間において終了する場合に発 生する。間接プレースホルダー及び遅延間接プレースホルダーの発生及び動作に ついては図７に関連して後に更に詳細に説明する。 ストリームフィールド４０８はセルデータが属するストリームを表わす。本発 明の１実施例においては、各入力ポートは一度に最大で１６個の別々のデータス トリームを取扱うことが可能である。 パケットヘッダーフィールド４１０は与えられたパケットと関連するヘッダー 情報を包含しており且つスタートオフセット情報と、パケット長と、インターフ ェースインデックス情報とを有している。 図５ａを参照すると、入力スイッチ１００は、ラウンドロビンデータハンドラ ー５００と、１個又はそれ以上の入力ポートインターフェース（５０１−０乃至 ５０１−７、各入力ポート１０７に対して１個）と、１個又はそれ以上のメモリ インターフェース５０２（５０２−０乃至５０２−７、各メモリバンクに関連し て１個）と、同複数個のポインタ５０４（５０４−０乃至５０４−７）と、出力 プロセサ５０５と、１個又はそれ以上の出力ポートインターフェース５０６（５ ０６−０乃至５０６−７）、各出力ポート１０８に対して１個）と、予約テーブ ル５０８と、間接セルプロセサ５１０と、制御器インターフェース５１２と、読 取制御器５１６とを有している。 ラウンドロビンデータハンドラー５００は、各入力ポートからセルを受取り且 つそれらをメモリ１０４内の適宜のメモリバンク１０５に対して出力するために 出力プロセサ５０５へ転送する。ラウンドロビンデータハンドラー５００は、ラ ウンドロビン時分割多重態様で、入力ポートインターフェース５０１ を介して受取った入力（セル）をサービス即ち処理する。即ち、与えられたセル スロットに対して、各入力ポートからの１個のセルがラウンドロビンデータハン ドラー５００において受取られ且つ、その後に、メモリ１０４内のメモリバンク １０５へ次のセルスロットにおいて転送するために出力プロセサ５０５へ転送さ れる。次のタイムセルスロットにおいて、データハンドラー５００は、同一の入 力ポートから受取った次のセルを異なるメモリバンクに対して転送するために出 力プロセサ５０５へ転送する。１実施例においては、受取った次のセルはメモリ アレイ内の次のメモリバンク（数値順において次）へ転送される。一方、同一の 入力ポートから連続するセルの転送を制御するために別の時間依存性順列を使用 することが可能である。 図５ｂを参照すると、入力からメモリへの転送のタイミング及び順番が示され ている。この例の目的のために、セルのシーケンスが各伝送線上に図示されてい る。この例のためにのみ、各伝送線は非常に長いものであると考え且つ２個又は それ以上のセルと関連するデータを包含している。動作について説明すると、該 伝送線は短く且つ与えられた時間において複数個のセルが１本の伝送線上に存在 するものではない。セルスロットＴ４において、一連のセル ４５０−０乃至４５０−７が伝送線４５８の下方へ転送され、尚各入力ポート１ ０７から入力スイッチ１００へ１つである。セルスロットＴ３（時間においてセ ルスロットＴ４のすぐ前のもの）において、一連のセル４５２−０乃至４５２− ７が伝送線４５８下方へ転送され、尚各入力ポート１０７から入力スイッチ１０ ０へ１つである。 入力スイッチ１００内のラウンドロビンデータハンドラー５００及び出力プロ セサ５０５は、伝送線４６０を介してセルをメモリ１００へ転送する。セルスロ ットＴ２において理解することが可能であるように、出力プロセサ５０５は１個 のセル４５４−Ｂ₀乃至４５４−Ｂ₇を単一セルスロットにおいて各メモリバンク へ出力する。「Ｂ_x」指定子はそれから特定のセルが受取られた入力ポートを表 わす。各入力ポートからの１個のセルがセルスロット当たりメモリ１０４へ書込 まれる。時間期間Ｔ１（セルスロットＴ２の前の１つのセルスロット）において 、１個のセル４５６−Ｂ₀乃至４５６−Ｂ₇が各メモリバンクへ書込まれる。ラウ ンドロビンデータハンドラー５００は、同一の入力ポートからの連続したセルが メモリ１０４内の連続したメモリバンク１０５へ書込まれるように、出力プロセ サ５０５への転送を時分割多重処理する。 再度図５ａを参照すると、ポインタ５０４は次のセルが書込まれる関連するメ モリバンク内の位置を表わす。出力プロセサ５０５は関連するポインタ５０４に よって表わされるように、バンク内の次の使用可能なアドレスに基づいて特定の メモリバンク内のメモリ位置へセルを書込む。 ラウンドロビンデータハンドラー５００は、パケット内の最初のセルと関連す るキー情報を決定するためのキー読取エンジン５１４と、同一のパケット内のセ ルをリンクするためのリンクエンジン５１５とを有している。 キー情報を読取るプロセスは当該技術において公知である。与えられたパケッ トに対してそのキーが決定された後に、それはパケット全体がメモリ１０４内に 格納されるまで、入力スイッチ１００内のキーバッファ５１６内に一時的に格納 される。キーバッファ５１６内のエントリ６００に対するデータ構造を図６に示 してある。各エントリ６００はキー６０２と、フルアドレス６０４と、オフセッ ト６０６と、間接セルインジケータ６０８とを有している。 リンクエンジン５１５は、与えられたパケット内の最初のセルに対してメモリ 内の開始アドレス（フルアドレス）を決定する。この開始アドレスはメモリ１０ ４内のバンク番号（ラウンドロビンデータハ ンドラー５００によってセルを格納するために割当てられているバンク番号）及 び指定されたバンク内の最初の使用可能なアドレス位置（関連するポインタ５０ ４によって表わされるように）を有している。開始アドレス（フルアドレス６０ ４）はそのパケットに対する関連するキー６０２と共にキーバッファ５１６内に 格納される。同一のパケットと関連する次のセルがスイッチ１００に到達すると 、セルが書込まれるべきオフセット（フルアドレスと相対的に）と関連するオフ セット６０６が計算され且つキーバッファ５１６内に格納される。本発明の１実 施例においては、最大で４個のオフセット６０６が格納される。各オフセットア ドレスは、メモリ内の最後のセルの位置と書込まれるべき現在のメモリバンクと 関連するポインタ５０４の値との間のメモリ内の相対的なオフセットに基づいて 計算される。 ５個を超えるデータセルが１個のパケット内に包含されている場合には、間接 セルインジケータがセットされ、且つ最後のオフセットはそのパケットと関連す る最初の間接セルが格納されているメモリ内のアドレスを表わす。間接セルは図 ７に関連して以下に更に詳細に説明する。パケットがメモリ内に格納された後に 、キーバッファ５１６内の関連するエントリ（ルートルックアップ要求）が制御 器インター フェース５１２を介して処理するために制御器１０６へ転送される。一方、キー は、最初の５個のセルがメモリ内に格納された後に転送することが可能である。 同一のパケットに対するセルのリンク形成又はスレッド形成は、上述したオフ セット及び間接セルを使用して行われる。オフセットは、パケット内の最初の５ 個のセルをリンクするために使用され、一方間接セルはパケット内の残りのセル をリンクするために使用される。１実施例においては、１個のセルが５個以下の セルを包含している場合には、間接セルを使用することが必要とされることはな い。間接セルプロセサ５１０は与えられたパケットに対してメモリ内のセルのリ ンク形成を行う。間接セルプロセサ５１０はメモリ１０４内に格納するために間 接セルを発生する。間接セルはパケット内の隣接セルの間のメモリ空間における 相対的なオフセットと関連するオフセット情報を包含している。間接セルプロセ サは間接セルを形成する期間中に間接セルデータを格納するための間接セルメモ リ５２０を有している。 次に、図７を参照すると、間接セル７００に対するデータ構造は、リンク形成 フィールド７０２と、複数個のオフセットフィールド７０４と、最後のフ ィールド７０６とを有している。リンク形成フィールド７０２は、セットされて いない場合には、現在の間接セルが与えられたパケットに対する間接セルの遅延 内における最後のセルであることを表わす。セットされている場合には、与えら れたパケットに対して更なる間接セルが存在している。更なる間接セルが存在し ている場合には、最後のフィールド６０６はそのパケットと関連する次の間接セ ルのメモリ内の位置に対するオフセットを表わす。本発明の１実施例においては 、各間接セルはメモリ内の５６個のセルをリンクさせるための５６個のオフセッ トデータブロックを有している。 上述したように、パケットが受取られると、リンクエンジンが最初の５個のセ ルを処理し且つ開始アドレスの形態におけるリンク情報及び４個のオフセットを キーバッファ５１６内に格納する。５個を超える数のセルが１個のパケット内に 包含されている場合には、間接セルプロセサはリンクエンジンにとって代わり且 つそのパケット内の残りのセルが格納されているメモリ内の位置に関連するオフ セットを計算する。ラウンドロビンプロセサ５００はメモリ１０４内の関連する メモリバンクへ転送するためにセルを出力プロセサ５０５へパスする。ラウンド ロビンプロセサ５００は処理中のパケットが５個を超 える数のセルを有している場合（最初のセル内に含まれているヘッダー情報に基 づいて）、間接セルプロセサをイネーブル即ち動作可能状態とさせる。５番目の セルをメモリへ書込む時に、間接セルプロセサ５１０はそれがパケット内の最後 のセルであった場合に５番目のセルが書込まれるであろうメモリ内の位置と関連 するアドレス（「間接セルアドレス」）を間接セルメモリ５２０内に格納する。 間接セルアドレスは、それがフル即ち満杯である場合に（又はそのパケットの最 後のセルが処理された場合に）間接セルが書込まれるべきメモリ内の位置を表わ す。 間接セルがフル即ち満杯である場合（最後のフィールド７０６を除いて全ての 使用可能な位置内にオフセットを格納済）、間接セルプロセサは次の間接セルが 最後のフィールド６０６内に位置されるメモリ内の位置と関連してそのオフセッ トを格納する。その後に、フル即ち満杯の間接セルがメモリ内のその適宜の場所 に書込まれる。間接セルのメモリに対する書込は、関連する入力ポート１０７か らの入力スイッチ１００による間接セルプレースホルダーの受取りと一致する。 このプロセスはパケット内の最後のセルがメモリ内に格納されるまで継続して行 われる。その時に、最後の間接セルがメモリへ書込まれ、且つキーバッファ５１ ６からの関連するエントリ６ ００が処理するために制御器１０６へ転送される。 しばしばそうであるように、パケットの最後のセルは完了した間接セルをメモ リ内にすぐ書込むために必要とされるタイミングと一致するものではない。何故 ならば、パケット長は完全に任意的なものであるからである。パケットの最後は 全体的な間接セルのファイリングと一致する蓋然性はない。パケットが完了し（ 全てのセルが入力スイッチによって受取られている）且つ間接セル内の最後のエ ントリが書込まれる場合には、間接セルはメモリに書込まれるのに自由である。 然しながら、その書込は、適切な時間まで遅延され、従って遅延間接セルと呼ば れる所以である。遅延間接セルは、パケットと関連する最後の間接セルである間 接セルである。それが遅延される理由は、それは、パケットの残部がメモリに書 込まれた後にメモリに書込まれるからである。メモリに対する書込のタイミング は、間接セルに対して予約されているアドレスによって支配される。上述したよ うに、間接セルの作成時にメモリ内の位置が予約される。そのパケットが完了さ れた後に特定のメモリバンクに対して書込むためにその特定の入力ボードに対し て使用可能な次のタイムスロットにおいてメモリに対して書込まれる。遅延間接 セルのメモリに対する書込のタイミングは、適宜の入力ポー ト１０７からの遅延間接プレースホルダーの受取りと一致する。 読取制御器５１７はメモリインターフェース５０２を出て入力スイッチ１００ からメモリ１０４内の個別的なメモリバンクへ流れる読取要求信号の転送を制御 する。読取制御器５１７は出力ポートインターフェース５０６を介して各出力ポ ートからの読取要求を受取る。各要求のフォーマットは、ソースＩＤ（出力ポー ト）及び読取られるべきメモリ内のフルアドレスを有している。各セルスロット において、各出力ポートはメモリ１０４内のメモリ位置を読取るためにスイッチ １００によって処理するための読取要求を発生することが可能であり、その結果 メモリバンク１０５（後のセルスロット上）から出力スイッチ１０２へのセルの 読取（読取応答）が行われる。 入力スイッチ１００から（出力プロセサ５０５を介して）メモリ１０４内のメ モリバンク１０５へ転送されるセルのデータ構造を図８に示してある。各セルス ロットにおいて、出力プロセサ５０５はセル８００を発生し、それは読取要求ソ ースフィールド８０２と、読取アドレス８０４と、書込アドレス８０６と、デー タフィールド（入力ポート１０７から受取られたセルデータ）８０８とを有して いる。読 取要求ソースフィールド８０２は、読取を要求する出力ポート（デスティネーシ ョン出力ポート１０８）を表わす。出力プロセサ５０５は読取制御器５１７から 読取要求を受取り且つその読取要求を同一のメモリバンクに対して意図されてい るラウンドロビンデータハンドラー５００から受取られた何等かの書込要求とバ ンドル即ち結束させる。各セルスロットにおいて、出力プロセサ５０５はセル８ ００を供給し、それはメモリ１０４内の各メモリバンク１０５に対する書込及び 読取要求を有することが可能である。 読取制御器５１７は種々の出力ポート１０８からパケットを転送するための要 求が受取られると予約テーブル５０８をロードする。予約テーブルは、全てのセ ルスロットにおいて、メモリ１０５の各バンクに対して単一の読取要求が発生さ れるようにロードされる。次に図９を参照すると、予約テーブル５０８は、メモ リ１０４内の各メモリバンク１０５に対して１つづつ複数個の列９００と複数個 の行９０２と、プレースホルダー９０４と、ロードされたエントリ９０６とを有 している。各行は単一のセルスロット上で発生されるべき１組の読取要求（メモ リバンク当たり１個）を表わす。各行は各出力ポート１０８に対する単一のエン トリを有している。各セル スロットにおいて、各出力ポートはメモリ１０４における単一のメモリバンク１ ０５からの読取を要求することが可能である。読取ポインタ９０８は予約テーブ ル５０８と関連している。該ポインタは、読取られるべき予約テーブル内の次の 行に対してポイントする。該読取ポインタの前の行は後のセルスロットタイムに おいてキュー即ち行列化される要求に対応している。１実施例においては、該ポ インタは各セルスロットタイムにおいて少なくとも１個の行を移動する。 ロードされているエントリ９０６は出力スイッチ１０２から受取られた予約要 求の結果として実施されるべき読取要求を反映する。プレースホルダー９０４は いまだに要求されていない使用可能な読取要求を表わす。各セルスロットにおい て、読取制御器５１７は３つの機能、即ちテーブル内の最初の使用可能な位置（ 読取ポインタの後）においてエントリを予約テーブル内にローディングすること 、最後の行を出力プロセサ５０５に対する読取要求として出力すること、及び該 テーブルをリフレッシュし、最後の行を外へ移動させ、該行をインクリメントし 且つテーブルのトップに新たな行を作成すること、を実行する。予約テーブル内 の行数は、読取要求を処理する場合の待ち時間とバンク数を掛けた積と同じ 大きさのものでなければならない。１実施例においては、予約テーブル５０８内 に４８個の行が設けられており、それは６個のセルスロットの待ち時間と８個の メモリバンクを有するシステムを反映している。 初期化において予約テーブル５０８は行９０２の全てにおいてプレースホルダ ー９０４を包含している。プレースホルダー９０４はロードされていない予約テ ーブル内の位置である。読取要求が読取プロセサによって処理されると、プレー スホルダー９０４のあるものが読取要求に基づいてロードされたエントリ９０６ へ変換される。ロードされたエントリ９０６は読取要求アドレスを有している。 次に、図１０を参照すると、予約テーブルをローディングするプロセスは、出 力ポートから読取要求（フルアドレス）を受取ることを包含している（１０００ ）。読取制御器は、この読取要求をデコードして、サーチすべき予約テーブル内 の列（それから読み取られるべきメモリバンクに基づいて）を決定する（１００ ２）。読取プロセサは、予約テーブルの底部から開始して、読取要求を発生した 出力ポートに関連する最初のプレースホルダーをサーチする（１００４）。読取 プロセサは、その位置に読取要求のフルアドレスを書込むことによってプレース ホ ルダー９０４をロードしたエントリ９０６へ変換する（１００６）。このプロセ スは、読取制御器によって受取られた各読取要求に対して繰り返し行われる（１ ００８）。 次に、図１１を参照すると、メモリ１０４は複数個のメモリバンク１０５を有 している。各メモリバンクは入力ポート１１０２と出力ポート１１０４とを有し ている。各セルスロットにおいて、各メモリバンクは、入力ポート１１０２を介 して、高々１個の書込及び１個の読取要求を受取る。書込要求は、入力ポート１ ０７から受取られたセルと関連している。読取要求は、メモリバンク１０５から 出力スイッチ１０２へ転送されるべきセルデータに対する要求を反映する。メモ リ１０４から出力スイッチ１０２へ書込まれたセルに関連するデータ構造を図１ ２に示してある。各セル１２００は、出力ポート識別子１２０２とセルデータ１ ２０４とを有している。 １実施例においては、該メモリは、複数個のバンクに分割され、その場合にメ モリバンクの数は入力ポートと出力ポートとの数に等しい。入力ポートと、出力 ポートと、メモリバンクとの間には１対１の関係が存在している。この実施例に おいては、入力スイッチ１００からメモリ１０４へのセルの転送は、時分割多重 態様で行われる。即ち、与えられた入力 ポートからの連続したセルは異なるメモリデスティネーション位置へ指向される 。各時間期間（セルスロット）において、入力スイッチは、各入力ポートからの 単一のセル（使用可能な場合）をメモリ内へ転送する。次の時間Ｔ＋１において 、入力スイッチは、各入力ポートからメモリ内へ再度単一のセルを転送する。同 一の入力ポートからの連続するエントリはメモリ１０４内の異なるメモリバンク １０５へ書込まれる。 次に、図１３を参照すると、制御器１０６は、制御器メモリ１０９と、ルート ルックアップエンジン１１０と、入力スイッチインターフェース１３００と、出 力スイッチインターフェース１３０２とを有している。制御器１０６は、入力ス イッチインターフェース１３００において入力スイッチ１００からルートルック アップ要求を受取る。本発明の１実施例においては、複数個のルートルックアッ プエンジン１１０が制御器１０６内に設けられており、その各々はルーチング即 ち経路付けプロセスを高速化させるためにラウンドロビン態様でルックアップ要 求を受取る。１実施例においては、制御器メモリ１０９はフル即ち満杯の帯域幅 でサービス即ち処理するために３２個のルートルックアップエンジン１１０を必 要とする４バンクスタティックランダムアクセス メモリ（ＳＲＡＭ）である。ルーターを介してのベストマッチのルートを決定す る前にパケットから検索されたキーのマッチングは、１９９６年１２月１６日付 けで出願した発明者がＦｅｒｇｕｓｅｎ ｅｔ ａｌ．の「スイッチング装置に おける高速可変長ベストマッチルックアップ（ＨＩＧＨ ＳＰＥＥＤ ＶＡＲＩ ＡＢＬＥ ＬＥＮＧＴＨ ＢＥＳＴ ＭＡＴＣＨ ＬＯＯＫ−ＵＰ ＩＮ Ａ ＳＷＩＴＣＨＩＮＧ ＤＥＶＩＣＥ」）という名称の同時係属中の特許出願、出 願番号０８／７６７，５７６号により詳細に記載されており、尚、それを引用に よって明示的に本明細書に取込む。 ルートルックアップ要求を処理するルートルックアップエンジンは、ベストマ ッチ即ち最良の位置のルックアップを実行し且つ出力スイッチ１０２に対して出 力スイッチインターフェース１３０２を介して通知を出力する。その通知は、パ ケットをそのデスティネーションへ転送する場合に使用すべき出力ポートを表わ す結果を有している。 次に、図１４を参照すると、制御器１０６によって出力スイッチ１０２へ出力 された通知と関連するデータ構造が示されている。この通知用のデータ構造１４ ００は、マスク１４０２と、次のホップインデックス（ｎｅｘｔ ｈｏｐ ｉｎ ｄｅｘ）ポイン タ１４０４と、フルアドレス１４０６と、オフセット１４０８と、パケット長１ ４０１とを有している。 マスクフィールド１４０２は、出力スイッチ１０２へ接続されているどの出力 ポートがそのパケットを転送すべきかを表わすために使用される。１実施例にお いては、該通知は、１つを超える出力ポートへ送ることが可能であり、その結果 関連するパケットのブロードキャスト即ち同報通信が行われる。 メモリが各出力ポート１０８と関連している。次のホップインデックスポイン タは該メモリ内の１つの位置をポイントする。該メモリは、パケット転送の特定 のタイプと関連するメディアヘッダー情報を格納するために使用される。次のホ ップアドレス及びメディアヘッダーは出力ポート１０８に関連して以下に更に詳 細に説明する。 フルアドレス１４０６は、そのパケット内の最初のセルが格納されているメモ リ内の開始アドレスを表わす。前に説明したように、オフセット１４０８はセル 又はそのパケットと関連している間接セルを検索するためのリンク情報を与える 。 次に、図１５を参照すると、出力スイッチは、制御器インターフェース１５０ ０と、１個又はそれ以上のメモリ入力１５０２（１５０２−０乃至１５０２−７ 、各メモリバンクに対して１個）と、１個又は それ以上の出力１５０４（１５０４−０乃至１５０４−７、各出力ポートに対し て１個）と、結果プロセサ１５０６と出力プロセサ１５０８とを有している。出 力スイッチ１０２は４つの機能、即ち出力結果の受取り、出力結果の処理、メモ リからのセルの受取り、出力ポートへのセルの出力、を実行する。 メモリからのセルはメモリ入力１５０２において受取られ且つ出力プロセサ１ ５０８へ転送される。出力プロセサ１５０８はメモリから受取られたセル情報か らデスティネーション出力ポートをデコードし且つそのセルデータを適宜の出力 １５０２へ転送する。各セルスロットにおいて、出力スイッチ１０２はメモリ１ ０４内の各バンクから処理するためのセルを受取る。 出力スイッチ１０２は制御器インターフェース１５００を介して制御器１０６ からの通知を受取る。結果プロセサ１５０６はその結果（ルート）をデコードし 且つどのポート１０８がそのルートデータを受取るべきかを決定する。その通知 内のマスク１４０２に基づいて、結果プロセサ１５０６はその通知をそのように して示された各夫々の出力ポート１０８へ転送するために出力ポート１５０８へ 転送する。各セルスロットにおいて、出力プロセサ１５０８は（出力１５０４を 介して）ルートを各出力ポート１０８ へ供給する。 出力プロセサ１５０８から出力ポート１０８へ転送されたデータに関連するデ ータ構造を図１６に示してある。セル１６００はヘッダー１６０２とデータフィ ールド１６０４とを有している。ヘッダー１６０２はメモリバンクソース情報１ ６０６とルート情報１６０８とを有している。メモリバンクソース情報は、どの メモリバンクがデータフィールド１６０４内にそのセルを供給したかを表わすソ ース識別子を有している。ルート情報１６０８は、次のホップインデックスと、 パケット長と、フルアドレスと、オフセットとを包含する該通知からのデータを 包含している。 次に、図１７を参照すると、各出力ポート１０８は、出力スイッチインターフ ェース１７００と、入力スイッチインターフェース１７０２と、バッファ１７０ ４と、出力要求プロセサ１７０６と、ライン出力インターフェース１７０８と、 格納装置（メモリ）１７１０と、出力バッファ１７１２と、出力フォーマッター １７１４とを有している。 出力ポート１０８はパケットが出力スイッチインターフェース１７００におい て受取られたセル１６００によって処理されるべきであることの通知を受取る。 出力要求プロセサ１７０６はその要求をバッ ファ１７０４内に格納し且つ、その後に、そのパケットが格納されているメモリ 内の最初のアドレスと関連する入力スイッチ１００に対して読取要求を発生する 。出力要求プロセサ１７０６は出力スイッチ１０２から受取ったフルアドレスに 基づいて最初の読取要求を発生する。その後に、爾後の読取要求はその要求（セ ル１６００から）又は間接セル（以下に説明するように）において与えられたオ フセット情報に基づいて入力スイッチへ転送するために発生される。 セル１６００と共に与えられたルート情報から決定されるように、パケット長 が５個のセルよりも大きい場合には、出力要求プロセサは、最初に、そのパケッ トと関連する最初の間接セルの転送（メモリからの読取）を要求する。このこと は、セル１６００内に与えられたオフセット及びフルアドレスに基づいて間接セ ルのアドレスを計算することによって行われる。間接セル要求が発生された後に 、出力要求プロセサはセル１６００内に与えられたオフセットとフルアドレスに 基づいてパケット内の残りのセルに対する読取要求を発生する。出力スイッチ１ ０２から間接セルを受取ると、出力要求プロセサは間接セル内に包含されている オフセット情報に基づいてそのパケット内の残りのセルに対する読取要求を継 続して発生する。 その後の間接セルは同様の態様で検索される。即ち、次の間接セルの読取を行 う時に、次の間接セルのアドレスが前の間接セル内に格納されている最後のオフ セットに基づいて計算される。間接セルを検索するタイミングは、出力ストリー ム内における遅延が必要とされないように実施される。各その後の間接セルは先 の間接セルの終了前に検索される。このように、出力ストリームが初期化される と、データのバッファ動作が必要とされることはなく、且つ検索プロセサに関連 する待ち時間に起因する中断を経験することはない。 個々のメモリバンクに対する出力要求は厳格に順番通りに処理される。即ち、 出力ポートはメモリバンクに対して発行された各要求をトラッキング即ち追跡す ることが可能であり且つ同一のメモリバンクに対する一連の要求に応答して受取 られたデータはそれらが発行されたシーケンス又はパターンに従って厳格に送給 される。出力要求プロセサは各メモリバンクに対して発生された要求を追跡する 。出力バッファ７１２は複数個のキューを有しており、即ち各メモリバンクに対 して２個設けられており（１個の要求キューと１個の応答キュー）、該キューは 、それらが割当てられている特定のストリームに従っ てメモリから受取られたセルの順番付けを行うために使用される。要求キューは ストリーム番号と読取アドレスとを包含している。メモリに対して要求が発行さ れると、その要求キューからエントリが除去され且つストリーム番号部分が応答 キュー内に配置される。応答が受取られると、応答キューのヘッドにおけるエン トリが除去され且つその応答が応答キューから検索されたストリーム番号によっ て表わされるストリーム番号へ送られる。 出力ポート１０８においてセルが受取られると（読取要求に応答して）、それ らは出力バッファ１７１２内に格納される。与えられたパケットに対して、出力 ポートはストリーム化した出力を与えることを必要とされるセルの数を格納する 。本発明の１実施例においては、出力ポートからの出力（ストリームデータ）を 開始する前に、１２個のセルが格納される。出力バッファ１７１２内に格納する セルの数の選択は読取プロセスにおける待ち時間に基づくものである（出力ポー トからの読取要求とその読取要求と関連しているセルの出力ポートへの到着との 間のクロックサイクル数）。 出力フォーマッター１７１４は出力バッファ１７１２からセルを受取り且つそ のデータをメモリ１７１０内に格納されているメディアヘッダー情報と結合さ せる。出力スイッチ１０２から受取られた各要求（通知）は次のホップインデッ クス（ｎｅｘｔ ｈｏｐ ｉｎｄｅｘ）を有している。この次のホップインデッ クスは、与えられたタイプの送信（パケットのデスティネーションから派生され る）と関連するメディアヘッダー情報のメモリ１７１０内の開始アドレスを表わ す。出力フォーマッター１７１４はメモリから戻されたセルデータを適宜のメデ ィアヘッダーと結合してライン出力インターフェース１７０８を介してルーター ２０から転送するための適切なパケットを発生する。 次に、図１８を参照すると、スイッチを介してパケットをルーチング即ち経路 付けする方法において、パケットが入力ポートにおいて受取られる（１８００） 。入力ポートはそのパケットを固定長セルへ分割し且つ該セルを入力スイッチへ 転送する（１８０２）。入力スイッチは、パケット内の最初のセルからキー情報 を除去し且つそれを一時的にキーバッファ内に格納する（１８０４）。その後に 、本入力スイッチは、該セルを時分割多重化態様でメモリバンクへルーチング即 ち経路付けさせる（１８０６）。本入力スイッチは最初のセルがメモリ内のどこ に書込まれるかに関連する最初のアドレスを格納し且つ次のセルが書込まれる次 の隣接したメモリバンクに 対してメモリ内のオフセットに関連する各付加的なセルに対するオフセットを計 算する（１８０８）。本入力スイッチはパケット長が５個のセルを超えるもので ある場合にそのパケットに対するリンク情報を格納するための間接セルを作成す る（１８１０）。そのセル数が間接セル内における使用可能なオフセットの数を 超える場合には、古い間接セルがメモリ内に格納され且つ新たな間接セルが作成 され且つ入力スイッチにおいて受取られた各新たなセルに対して計算されたオフ セットに基づいてロードされる。 パケット（及び、存在する場合には、その間接セル）がメモリ内に格納される と、キーと、第一セルのフルアドレスと、オフセット情報とがルックアップ要求 として制御器へ転送される（１８１４）。該制御器はベストマッチのルックアッ プを実行し且つそのルックアップの結果を発生する。その結果は、デスティネー ションポート（出力ポート）とアドレスと、オフセット情報と、次のホップイン デックスとを有している（１８１６）。その結果を包含する通知は適宜の出力ポ ートへ転送するために出力スイッチへ転送される（１８１８）。 通知を受取ると、出力ポートはそのパケットと関連するデータに対して入力ス イッチに対し一度に１個のセルの読取要求を発生する（１８２０）。入力 スイッチは、時分割多重態様でその読取要求を発行し、セルスロット当たり各メ モリバンクに対して単一の要求を発生する（１８２２）。メモリバンクが入力ス イッチからの要求を受取ると、その要求及びセルデータと関連している出力ポー トが出力スイッチに対して書込まれる（１８２４）。再度、各セルスロットにお いて、出力スイッチは単一のセルを出力ポートの各々へ転送する。受取ると、出 力ポートはそのセルデータをメディアヘッダー情報と結合し且つそのデータをデ スティネーションへストリームさせる（１８２６）。 変形実施例 本発明の１実施例においては、出力ポートと入力ポートと、メモリバンクとが 単一の装置内に包含されている。このメモリを包含する多機能ポートのアーキテ クチュアを図１９に示してある。特に、多機能ポート１９００はメモリバンク１ ０５と、ライン入力インターフェース３００と、データハンドラー３０２と、バ ッファ１７０４と、出力要求プロセサ１７０６と、ライン出力インターフェース １７０８と、格納装置１７１０と、ＦＩＦＯ１７１２と、出力フォーマッター１ ７１４と、入力スイッチインターフェース１９０２と、出力スイッチインターフ ェース１９０４とを有している。 この多機能ポートは図２０に示したように入力スイッチ、出力スイッチ及び制 御器に関連して使用される。入力ポート、出力ポート及びメモリバンクの種々の 部分的な構成要素は上述した個別的な機能を実行する。然しながら、これらの装 置を単一のユニットへ結合させることはコンポーネント間のインターフェースを 簡単化させる。特に、多機能ポートと入力スイッチとの間での転送に対する改定 したフォーマットを図２１に示してある。 多機能ポート１９００から入力スイッチへ転送されたセル２１００はセルヘッ ダー２１０２とセルデータ２１０４とを包含している。セルヘッダー２１０２は 、図４を参照して上述したフィールドと機能が同様の、タイプフィールド４０６ と、ストリームフィールド４０８と、パケットヘッダーフィールド４１０とを包 含している。更に、セルヘッダー２１０２は出力ポート識別子２１０６及びアド レス２１０８の形態での読取要求を包含している。出力ポート識別子２１０６は その読取要求を発生する出力ポートを識別する。アドレス２１０８は読取られる べきメモリ１０４内のアドレスを表わす。 本発明を特定の実施例について説明したが、それらは本発明の例示的なもので あって制限的なものとして解釈されるべきものではない。その他の実施例 は以下の請求の範囲内のものである。

───────────────────────────────────────────────────── フロントページの続き (31)優先権主張番号 ０８／９０１，０６１ (32)優先日 平成９年７月24日(1997．7．24) (33)優先権主張国 米国（ＵＳ） (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，Ｌ Ｕ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＣＡ，ＪＰ (72)発明者 ファーガソン，デニス シイ. アメリカ合衆国，カリフォルニア 94043, マウンテン ビュー，オーチャード グレ ン コート 203 (72)発明者 レインクレス，ビョルン オー. アメリカ合衆国，カリフォルニア 94303, パロ アルト，グリアー ロード 2731

Claims (1)

1. 【特許請求の範囲】 １．ネットワークにおけるソースとデスティネーションとの間でデータパケ ットをスイッチングするルーターにおいて、 データハンドラーを具備する入力ポートであって、前記ソースからのデータパ ケットを受取り前記データハンドラーが該データパケットを１個又はそれ以上の 固定長セルへ分割する入力ポート、 前記データパケットを前記デスティネーションへルーチングする出力ポート、 複数個のメモリバンクへ分割されているメモリ、 前記入力ポートから前記固定長セルを受取り且つセルスロットタイムスパンに おける単一のセルを各メモリバンクへルーチングする入力スイッチ、 前記メモリから受取ったセルを前記出力ポートに対してルーチングする出力ス イッチ、 を有するルーター。 ２．請求項１において、前記入力スイッチが前記メモリ内の隣接していない 位置から前記データパケットの検索を可能とするために前記データパケット内の セルをリンクさせるリンクエンジンを有していることを特徴とするルーター。 ３．請求項２において、更に、１個又はそれ以上の間接セルを発生する間接 セル発生器を有してお り、前記リンクエンジンが前記データパケットの連続するセルが格納されている 前記メモリ内の位置をトラッキングし且つ間接セル内に格納するために前記デー タパケット内の各セルのメモリ内のアドレスを供給するルーター。 ４．請求項１において、前記入力スイッチが、入力ポートからの連続するセ ルが前記メモリ内の連続するバンクへ書込まれるように、前記メモリに対するデ ータパケットの書込を時分割多重処理するルーター。 ５．請求項１において、前記入力スイッチが、前記データパケットと関連す る入力スイッチにおいて受取られた最初のセルからキー情報を抽出するキー読取 エンジンを有しており、前記ルーターは、更に、前記入力スイッチへ結合されて おり且つそれから前記キー情報を受取る制御器を有しており、前記制御器は前記 入力スイッチから受取ったキー情報からデスティネーション情報をデコードし且 つ前記メモリから前記出力ポートへ前記データパケットのルーチングを画定する 通知を出力するルーター。 ６．請求項５において、前記出力ポートは、前記制御器からの通知を受取り 且つ前記メモリから前記出力ポートへのデータパケットの転送を開始させる結果 プロセサを有しているルーター。 ７．請求項１において、前記入力スイッチが、前記メモリから前記出力スイ ッチへの転送をスケジューリングする予約テーブルを有しているルーター。 ８．請求項７において、更に、前記入力スイッチ及び出力スイッチへ結合さ れており前記入力スイッチから受取られたデスティネーション情報をデコードし 且つ前記メモリから前記出力ポートへのデータパケットのルーチングを画定する 通知用前記出力スイッチへ出力する制御器を有しているルーター。 ９．請求項８において、前記出力スイッチが前記通知を前記出力ポートへ経 路付けし且つその後に前記出力ポートが前記出力スイッチを介してメモリから前 記出力ポートへデータパケットを転送するために前記入力スイッチに対して要求 を発行するルーター。 １０．請求項９において、前記出力ポートからの要求が前記予約テーブル内 に格納されるルーター。 １１．請求項１０において、メモリから前記出力スイッチへセルを転送する ための要求が時分割多重化処理され、従って１つのスロットタイムスパン期間中 に、高々単一の読取要求が処理するために前記メモリ内の各バンクに対して発行 されるルーター。 １２．請求項９において、前記メモリが１つのセルスロットタイムスパンに おいてバンク当たり高々 単一のセルを出力するルーター。 １３．ネットワークにおいてソースとデスティネーションとの間でデータパ ケットをスイッチングするルーターにおいて、 前記ソースからデータパケットを受取るための入力ポートであって、前記デー タパケットを固定長セルへ分割するデータハンドラーを具備している入力ポート 、 複数個のメモリバンクに分割されているメモリ、 リンクエンジンを具備する入力スイッチであって、セルスロットタイムスパン において前記入力ポートから高々単一セルを受取り且つ前記入力ポートからセル スロット内の前記メモリへ高々単一のセルをルーチングし、前記入力ポートから の連続するセルが前記メモリ内の連続するバンクへ書込まれるように前記メモリ に対するセルの書込を時分割多重化処理し、前記データパケット内のセルをリン クさせるリンクエンジンが前記メモリ内の隣接していない位置からデータパケッ トの検索をすることを可能とする入力スイッチ、 前記データパケットと関連するデスティネーション情報をデコードし、本ルー ターを介しての前記データパケットのルーチングを画定する通知を出力する制御 器、前記制御器から前記通知を受取り且つメモ リから前記出力ポートへ前記データパケットの転送を開始させる結果プロセサを 具備している出力ポート、 前記メモリから受取ったセルを前記出力ポートに対してルーチングする出力ス イッチ、 を有しているルーター。 １４．ネットワークにおけるソースとデスティネーションとの間でデータパ ケットをスイッチングするルーターにおいて、 各々がデータハンドラーを具備している複数個の入力ポートであって、第一入 力ポートが前記ソースからのデータパケットを受取り、前記第一入力ポートのデ ータハンドラーが前記データパケットを１個又はそれ以上の固定長セルへ分割す る複数個の入力ポート、 少なくともそのうちの１つが前記データパケットを前記デスティネーションへ ルーチングさせるものである複数個の出力ポート、 複数個のメモリバンクへ分割されているメモリ、 １つ又はそれ以上の入力ポートから固定長セルを受取り且つセルスロットタイ ムスパンにおいて各メモリバンクに対し単一のセルをルーチングさせる入力スイ ッチ、 前記メモリから受取ったセルを適宜の出力ポート へルーチングさせる出力スイッチ、 を有しているルーター。 １５．請求項１４において、前記入力スイッチが、前記メモリ内の隣接して いない位置からのデータパケットからの検索を可能とさせるために前記データパ ケット内のセルをリンクさせるリンクエンジンを有しているルーター。 １６．請求項１５において、更に、１個又はそれ以上の間接セルを発生する 間接セル発生器を有しており、前記リンクエンジンが、前記データパケットの連 続するセルが格納されている前記メモリ内の位置をトラッキングし且つ間接セル 内に格納するために前記データパケット内の各セルのメモリ内のアドレスを供給 するルーター。 １７．請求項１４において、前記入力スイッチが、任意の入力ポートからの 連続するセルが前記メモリ内の異なるバンクへ書込まれるように、前記メモリに 対するセルの書込を時分割多重化処理するルーター。 １８．請求項１４において、前記入力スイッチが前記データパケットに関連 する入力スイッチにおいて受取られた最初のセルからキー情報を抽出するための キー読取エンジンを有しており、本ルーターは、更に、前記入力スイッチへ結合 されており且つ それからキー情報を受取る制御器を有しており、前記制御器は前記入力スイッチ から受取ったキー情報からデスティネーション情報をデコードし且つ前記メモリ から適宜の出力ポートへの前記データパケットのルーチングを画定する通知を出 力するルーター。 １９．請求項１８において、前記出力ポートは、前記制御器から前記通知を 受取り且つ前記メモリから適宜の出力ポートへのデータパケットの転送を開始さ せる結果プロセサを有しているルーター。 ２０．請求項１４において、前記入力スイッチが前記メモリから前記出力ス イッチへの転送をスケジュールする予約テーブルを有しているルーター。 ２１．請求項２０において、更に、前記入力スイッチと出力スイッチとに結 合されており前記入力スイッチから受取ったデスティネーション情報をデコード し且つ前記メモリから適宜の出力ポートへデータパケットのルーチングを画定す る通知を前記出力スイッチへ出力する制御器を有しているルーター。 ２２．請求項２１において、前記出力スイッチが前記通知を前記出力ポート に対して経路付けし且つその後に前記出力ポートが前記出力スイッチを介してメ モリから適宜の出力ポートへデータパケットを転送するために前記入力スイッチ に対して要求を発行するルーター。 ２３．請求項２２において、前記出力ポートからの要求が前記予約テーブル 内に格納されるルーター。 ２４．請求項２３において、メモリから出力スイッチへセルを転送するため の要求が時分割多重化処理され、従って１つのセルスロットタイムスパン期間中 に、高々単一の読取要求が処理するために前記メモリ内の各バンクへ発行される ルーター。 ２５．請求項２２において、前記メモリが１つのセルスロットタイムスパン において、バンク当たり高々単一のセルを出力するルーター。