JPH02131048A - アダプタ間のパケツト転送方法、競合解消装置、及びトークン・リング装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は、高速の音声・データ統合パケット・スイッチ
ング・ノードに関する。本発明は、いくつかのスイッチ
ング・ノードを持つネットワークを通じて音声及びデー
タのパケットを伝える方法に関する。

Ｂ６従来技術 今日の通信システムのトレンドは、データ・トラフィッ
クはパケット・スイッチング技術によって運び、音声に
ついては回路スイッチング技術を用いることにある。従
来、パケット・スイッチングによって提供される統計的
マルチプレクシングによって、パケット・スイッチング
はインターラクティブ・データのような突発性をもつト
ラフィックに理想的に適したものになると論じられてい
た。音声のような定常ストリームをなすトラフィックの
場合には、パケットごとに必要とされるノード処理のオ
ーバーヘッドが統計的マルチプレクシングによって達成
されるいかなるバンド幅の節約をも上回りかねないので
、回路スイッチング技術の方がより適切である。１９７
０年代後半に様々な研究・テストがなされたが、以下の
文献はその代表例である。

１　、　Ｄ、　Ｃｏｈｅｎ著、　”Ａ　ｐｒｏｔｏｃｏ
ｌ　ｆｏｒ　ｐａｃｋｅｔｓｗｉｔｃｈｉｎｇ　ｖｏｉ
ｃｅ　ｃｏｍｍｕｎｉｃａｔｉｏｎ、”　Ｃｏｍｐｕｔ
ｅｒＮｅｔｗｏｒｋｓ、　Ｖｏｌ、　２．　ｐｐ、　３
２０−３３１．１９７８年。

２　、　Ｃ，Ｊ、　（Ｎｅｉｎｓｔｅｉｎ、　Ｊ、Ｗ、
　Ｆｏｒｇｉｅ共著。

”Ｅｘｐｅｒｉｅｎｃｅ　ｗｉｔｈ　５ｐｅｅｃｈ　ｃ
ｏｍｍｕｎｉｃａｔｉｏｎ　１ｎｐａｃｋｅｔ　ｎｅｔ
ｗｏｒｋｓ、”ＩＥＥＥ　Ｊｏｕｒｎａｌ　ｏｎＳｅｌ
ｅｃｔｅｒ　Ａｒｅａｓ　ｉｎ　Ｃｏｎ、、　Ｖｏｌ、
　５ＡＣ−１，Ｎｏ、６゜ｐｐ、　　９６３−９８０．
　１９８３年１２月。

３　、　Ｄ、　Ｃｏｎｒａｄｓ、　Ｐ、　Ｋｅｒｍａｎ
ｉ共著　ｊｊＡｆｅａｓｉｂｉｌｉｔｙ　５ｔｕｄｙ　
ｏｆ　ｕｓｉｎｇ　ｓｔｏｒｅ−ａｎｄｆｏｒｗａｒｄ
　ｄａｔａ　ｃｏｍｍｕｎｉｃａｔｉｏｎ　ｎｅｔｗｏ
ｒｋｓ　ｔ。

ｔｒａｎｓｍｉｔ　ｄｉｇｉｔｊ、ｚｅｄ　５ｐｅｅｃ
ｈ、”ＩＢＭ　Ｒｅ５ｅａｒｃｈＲｅｐｏｒｔ、　ＲＣ
９１５７，１９８１年１０月。

これらの研究のほとんどどれもが、パケット・スイッチ
ングが音声に適すると法論づけることに失敗している。

なぜなら、データ転送用に開発された汎用パケット・ス
イッチング技術（ＳＮＡ、ＡＲＰＡ）を使おうとしたか
らである。

４　、　Ｊ、Ｄ、　Ａｔｋｉｎｓ著、　”Ｐａｔｈ　ｃ
ｏｎｔｒｏｌ　−ｔｈｅｎｅｔｗｏｒｋ　１ａｙｅｒ　
ｏｆ　Ｓｙｓｔｅｍ　ＮｅｔｗｏｒｋＡｒｃｈｉｔｅｃ
ｔｕｒｅ、”ｉｎ　Ｃｏｍｐｕｔｅｒ　Ｎｅｔｔｙｏｒ
ｋＡｒｃｈｉｔｅｃｔｕｒｅ　ａｎｄ　Ｐｒｏｔｏｃｏ
ｌｓ、　Ｎｅｗ　Ｙｏｒｋ：Ｐｌｅｎｕｍ、　１９８２
年、　ｃｈ、　１１゜５　、　Ｊ、Ｍ、　ＭｃＱｕｉｌ
ｌｉａｍ、　Ｄ、Ｃ，Ｗａｌｄｅｒ＋共著、　”Ｔｈｅ
ＡＲＰＡ　ｎｅｔｔｉｏｒｋ　ｄｅｓｉｇｎ　ｄｅｃｉ
ｓｉｏｎｓ、”　ＣｏｍｐｕｔｅｒＮｅｔｔｇｏｒｋｓ
、　Ｖｏｌ、１．　ｐｐ、　２４３−２８９．１９７７
年。

これらの方法は汎用プロセッサを用いてパケット・スイ
ッチングをソフトウェアで行っており、その結果、音声
の場合には十分なスループットを得ることができなかっ
た。

音声のパケット・スイッチングの真の可能性を認識した
最初の研究は、Ｊ、Ｓ、　Ｔｕｒｎｅｒ、　Ｌ、Ｆ。

Ｗｙａｔｔ共著、　”Ａ　Ｐａｃｋｅｔ　Ｎｅｔｗｏｒ
ｋ　Ａｒｃｈｉｔｅｃｔｕｒｅｆｏｒ　ｉｎｔｅｇｒａ
ｔｅｄ　５ｅｒｖｉｃｅｓ、”　Ｇｌｏｂｅ　Ｃｏｍｍ
　１９８３゜ｐｐ、　２．１．１．−２．１．６．に記
載されている。この論文では、バケツ１〜・スイッチン
グ・ファンクションを専用ハードウェアにオフ・ロード
する基本的なアイデアが提示されている。米国特許第４
４９４２３０号明細書で開示されている通信方法及びパ
ケット・スイッチング・システムでは、高速デジタル・
トランクによって相互に結ばれたパケット・スイッチン
グ・ネットワークによって、論理アドレスと音声／デー
タ情報を含むパケットがシステム内を通信される。この
特許発明のやり方では、パケットをその宛先にルートす
るのに必要とされる物理的及び論理的アドレスをすべて
のコントローラに分配するために、中央プロセッサが必
須とされている。この分配は、コール・セットアツプの
時点で行われる。パケットが入カドランクに到着すると
、アドレス変換及びテーブル・ルックアップが実行され
、スイッチング・ネットワークを通ずる出カドランクへ
の当該パケットのルーディングが可能になる。パケット
がスイッチング・ネットワークに一旦入ってしまうと、
セルフ・ルーティングのコンセプトが使用され、それに
よってさらなるテーブル・ルックアップや処理を必要と
せずに当該パケットを適当な出力トランクヘルートする
ことが可能になる。したがって、この発明はコール・セ
ットアツプ・プロトコールを必要とする結果、プロトコ
ールの複雑さが増大する。また、この発明は１．５メガ
ビツトのリンクしかサポートしない。さらに、この発明
は、カスタム■ＬＳＩチップを使うデザインを必要とす
るマルチステージ・スイッチング・ネットワークを使用
している。米国特許第４４８８２８９号及び同第４４９
１５４５号はどちらも上記特許発明のシステムを詳述す
るものであり、上記特許発明と同様の評があてはまる。

米国特許第４５１２０１１号も同様の内容であるが、ス
イッチング・ネットワークの複製によって達成される優
れた信頼性を具備している。

米国特許第４５３９６７６号の発明は、バルク・データ
及び音声の転送には回路スイッチングを用いる一方、突
発性（ｂｕｒｓｔｙ）データの転送にはパケット・スイ
ッチングを用いている。したがって、２つの別個のセグ
メントが必須である。伝統的な一 回路スイッチ・セグメントとパケット・スイッチ・セグ
メントである。

米国特許第４５７３１５１号の発明は、音声の転送に回
路スイッチングを用いつつ、リモート・ライン・スイッ
チからセントラル・オフィスへあるスーパーバイザリ、
コントロール情報を転送するときのみパケット・スイッ
チングを用いている。

米国特許第４４００５８７号の発明は、回路スイッチン
グ・ネットワークのみを用いるコール式分散システムに
おけるリルーテイング・コールを扱っている。

米国特許第４３０７４４６号明細書には、デジタル・デ
バイスを相互接続するデジタル・ネットワークが開示さ
れている。このネットワークは１〜２２のエクスペンダ
と２２〜１のマルチプレクサを持ち、それらが結ばれて
スイッチング・ネットワークを形成している。各スイッ
チング・デバイスは、２つの入カポ−１〜と１つの出力
ボートだけをコントロールできるか、またはその逆かで
ある。ソース・アドレスはアービトレーシ玉ンのために
必要である。この発明では、特定宛先からのソース・ア
ドレスが当該特定ソースからの宛先アドレスであること
を要請する。また、ソースと宛先の間で唯一の予定され
たパスのみが使用されることも要請している。該明細書
で開示されているネットワークはジェネリックなパケッ
ト・スイッチング・ネットワークであることを意図して
はいない。

したがって、カスタムＶＬＳＩチップを用いずにＩＧビ
ット台のノード・スループットを提供することのできる
、簡素かつコスト効率のよい゛、プライベート・インテ
グレーテッド・音声／データ・パケット・スイッチング
・ネットワークが求められている。さらに、コール・セ
ットアツプを必要とせずに並列伝送バスでパケットを伝
送する方法も求められている。

なお、以下で説明する本発明の動作環境は、１９８６年
１０月３０日付のＩ　Ｂ　Ｍ　Ｒｅ５ｅａｒｃｈＲｅｐ
ｏｒｔ　ＲＣ１２２７７１に記載されている。このレポ
ートは、１．　Ｃ１ｄｏｎ、　１．　Ｇｏｐａｌ、　Ｈ
，Ｍｅｌｅｉｓの共著であり、タイトルは”ＰＡＲＩＳ
：ＡｎＡｐｐｒｏａｃｈ　ｔｏ　Ｉｎｔｅｇｒａｔｅｄ
　Ｐｒｊ、ｖａｔｅ　Ｎｅｔｗｏｒｋｓ”である。

Ｃ０発明が解消しようとする問題点 本発明は、パケット化された音声及びデータを伝送する
ための、コスト効率がよく、かつ高速の（例えばＩＧビ
ット／秒を越す）通信ネットワークを提供することを目
的とする。

Ｄ１問題点を解決するための手段 本発明は、並列通信バスを通じてソース・アダプタのＦ
ＩＦＯメモリから宛先アダプタのＦＩＦＯメモリにパケ
ットを転送する方法を提供する。

この方法では、パケットが１クロック・サイクルにつき
１ワードずつソース・アダプタのＦＩＦ○メモリから読
み出される。該パケットのすべてのワードは連続するク
ロック・サイクルの間に送信される。該パケットのリン
ク・アドレスは、指定されたワードの中に登場する。該
パケットの先頭ワード及び最終ワードが識別される。該
バスにアクセスし得るすべてのアダプタにおいて、該パ
ケットの指定ワード中のリンク・アドレスと当該アダプ
タ自身のアドレスとが比較される。指定ワード中のリン
ク・アドレスがあるアダプタのリンク・アドレスと一致
したなら、当該パケットのワードが当該宛先アダプタの
ＦＩＦ○メモリに書き込まれていく。

また、本発明は、通信バスにアクセスする複数のアダプ
タの間での競合（コンテンション）を解消するための装
置をも提供する。この装置は、いくつかのセルを環状に
配列し、ｉ番目のセルの出力は（ｉ＋１）番目のセルの
入力となるようにしている。各々のセルは対応するアダ
プタと関連づけられている。各セルは、トークンをスト
アするための手段とトークン転送論理回路を具備してい
る。ストア手段は、対応するアダプタがバスへのアクセ
ス権を持つことを示すトークンをストアするのに用いら
れる。該ストア手段は、先にここへのトークンのストア
が行われた場合でかつ他のアダプタの何れもが通信バス
へのアクセスをリクエストしないとき、または同場合で
かつ対応するアダプタ自身が通信バスへのアクセスをリ
クエストするときに、トークンをストアする。ストア手
段はまた、当該セルに向けてトークンが送信中であって
かつ対応するアダプタが通信バスへのアクセスをリクエ
ストするときにも、トークンをストアする。トークン転
送論理回路は、バスへのアクセスをリクエストするアダ
プタに対応するセルへトークンを転送するのに用いられ
る。所与のセルの上記回路は、対応するアダプタが通信
バスへのアクセスをリクエストしない場合でかつ当該セ
ルに向けてトークンが送信されつつあるとき、または同
場合でかつ当該セルがそのストア手段にトークンをスト
アしているときに、トークンを転送する。

したがって、所与のセルのトークン転送論理回路は、ク
ロック・パルスを待つことなしに別のセルに向けてトー
クンを送信することが可能になる。

その結果、１クロック・サイクルの間に、トークンがバ
スへのアクセスをリクエストするアダプタに対応するセ
ルに向けて、多数のセルを通過することが可能になる。

また、本発明は、あるセルから通信バスへのアクセスを
リクエストするアダプタに対応する別のセルに向けて、
中間セルを通過させることなしにトークンを転送するた
めの装置を提供する。この装置は、中間セルに対応する
アダプタの何れかが通信ネットワークへのアクセスをリ
クエストしているか否かを判断するための手段を具備す
る。また、この装置は、上記判断手段に応答して、対応
するアダプタが何れも通信ネットワークへのアクセスを
リクエストしない中間セルを通過させずに、トークンを
あるセルから別のセルへ直接転送するための手段を含ん
でいる。

Ｅ、実施例 第１図は、３個のスイッチング・ノード１５を持つ通信
ネットワークの概略図である。ネットワークのベーシッ
ク・コンポーネントは、ネットワーク・コントロール・
ユニット５、スイッチング・サブシステム２０、リンク
１２、及びエンド・ポイント・プロセッサ１７である。

ネットワーク・コントロール・ユニーＮＣＵＮＣＵは、
コール・セットアツプの間に呼び出されるすべてのファ
ンクションをインプリメントする。さらに、ＮＣＵは、
これらのファンクションを実行するのに必要な情報（例
えばトラフィック統計）を集める際に他のコンポーネン
トとインターラクトする。また、ＮＣＵは、情報収集時
及びおそらくはファンクション実行時においても他のテ
レコミュニケーション・ネットワーク・ノード（ＴＮＮ
）の中のＮＣＵともインターラクトする。ＮＣＵが実行
するファンクションの中には、新たな音声またはデータ
のネットワークに対するコール・アクセスの許否を判断
するコール・アクセプタンス・ファンクション、コール
がルートされるパス（経路）を決めるルート計算ファン
クション、リモート・ネットワーク・リソースのロケー
ション等の重要なサービスを行うディレクトリ及びその
他のアプリケーション・レベル・ファンクションが含ま
れる。ＮＣＵのプロトコール及びアルゴリズムの多くの
面は、以下の文献の内容と類似である。

Ａ、　Ｅ、　Ｂａｒａｔｚ、　Ｊ、　Ｐ、　Ｇｒａｙ、
　Ｐ、　Ｅ、　Ｇｒｅｅｎ、　Ｊｒ、。

Ｊ、　Ｍ、　Ｊａｆｆｅ及びり、　Ｐ、　ｐｏｚｅｆｓ
ｋｙ著、　”ＩＥＥＥＪｏｕｒｎａｌ　ｏｎ　５ｅｌｅ
ｃｔｅｄ　Ａｒｅａｓ　ｉｎ　Ｃｏｍ、、　　Ｖｏｌ。

５ＡＣ−３，Ｎｏ、　３．　ｐｐ、　ＪＮ６−４２６．
１９８５年５月。

ＮＣＵは、ＩＢＭ社のＰＳ２のような任意の汎用コンピ
ュータであってよい。

スイッチング・サブシステム　５Ｓ ＳＳは、パケットの転送に関係する中間ノード・ファン
クションを実行する（第２図参照）。その中には、パケ
ット・フレーミング、パケット・バッファリング、出力
リンクの決定、入力リンクから出力リンクへのパケット
転送の実際のスイッチング・ファンクション、過剰なパ
ケット待ち行列化（キューイング）を防ぐコンジェスチ
ョン・コントロール、プライオリティ・ファンクション
が含まれる。中間ノード・ファンクションに加えて、Ｓ
Ｓは統計収集を行ってＮＣＵにレポートする。

ＳＳを詳しく説明するために、ＳＳをいくつかのサブ・
コンポーネント、すなわち入力及び出力リンクのアダプ
タ、トラフィック統計を集めるモニタ、及びスイッチン
グ・カーネルに分解することにする。

エンド・ポイント・プロセッサ　ＥＰＰＥＰＰは、パケ
ットを適当なフォーマットに作り、それをネットワーク
に配送する役目を持つ。

すなわち、適切なヘッダ及び区切りフラグの挿入を行い
、また情報フィールドの中に区切りフラグが登場しない
ように情報フィールドに対するビット・スタッフィング
及びデスタッフィングを実行する。さらに、ＥＰＰは、
フロー・コントロール、エラー・リカバリー、及びリア
センブリ／プレイアウト等のエンド・ツウ・エンド・フ
ァンクションを実行する。これらのエンド・ツウ・エン
ドＥＰＰファンクシミンは、伝送中のトラフィックの性
質に敏感である。換言すると、音声用のファンクション
はデータ用のそれとは非常に異なったものとなり得る。

適当な場合には、ＥＰＰファンクションはＳＳ中のリン
ク・アダプターに統合することもあり得る。ＥＰＰファ
ンクションの詳細については、Ｄ、　Ｃｏｈｅｎ著、　
”Ａ　Ｐｒｏｔｏｃｏｌ　ｆｏｒ　ＰａｃｋｅｔＳｗｉ
ｔｃｈｉｎｇ　Ｖｏｉｃｅ　Ｃｏｍｍｕｎｉｃａｔｉｏ
ｎ”、　ＣｏｍｐｕｔｅｒＮｅｔｗｏｒｋｓ、　Ｖｏｌ
、２．　ｐｐ、　３２０−３３１．１９７８年に記載さ
れている。

このパス（ｐａｔｈ）を介しての音声又はデータのコー
ルは、典型的には以下のようにして進行する。

第１図に記されたパスを考えよう。ＴＮＮ　　Ｘに属す
るＥＰＰに付着したユーザーＡが、ＴＮＮＹのユーザー
Ｂとの通信を望んだとする。まず、ユーザーＡは、ユー
ザーＢについてのディレクトリ・サーチを行うべく、ノ
ードＸのＮＣＵとインターラクトする。ユーザーＢがノ
ードＹにいることがわかると、ユーザーＡはノードＹへ
至るルートをＮＣＵから獲得する。ＮＣＵは、ただ次の
ノードを提示するのではなく、完全なパスを提示するも
のと仮定しよう。この情報は、続くセクションで述べる
フオームで符号化され、ＡとＢの間で転送されるすべて
のバケツ１−に盛り込まれる。このプロセスの次のステ
ップでは、エンド・ツ・エンド・コネクションがオープ
ンされる。中間ノードのＮＣＵがこのステップの実行に
かかわる。エンド・ツ・エンド・コネクションが確立さ
れると、ユーザーは有用な情報パケットの交換を開始す
る。

パスに沿うすべてのノードにおいて、情報パケットは、
ＮＣＵに影響を及ぼすことなくＳＳを通過する。エンド
・ポイントＡ及びＢにおいては、ＥＰＰもまたすべての
情報パケットの転送にかかわる。

第２図は本発明で用いるパケットの構造を示す。

重要な点は次のとおりである。

１、パケット境界を画定するための、先頭及び後尾のデ
リミター（フラグ）。

２．２バイト・コントロール。これは、パケット・プラ
イオリティ・レベル（２ビツト）、当該パケットが出力
リンクに伝送されるのに加えてＮＣＵにコピーされるべ
きであるか否かを示すコピー・ビット、当該パケットを
すべての出力リンクに送出させるブロードキャスト・ビ
ットを除いて、現在のところほとんど未使用である。

３、オートマチック・ネットワーク・ルーティング（Ａ
ＮＲ）フィールド。これはｈ個のリンク・アドレスから
なる。各リンク・アドレスの長さは２ビツト以上である
。（ｈは、当該パケットが旅行しなければならないホッ
プの数である。）各リンク・アドレスは、当該パケット
・パスの出力リンクを表わす。次のセクションで、この
フィールドの詳細を述べることにする。

４、可変長の、情報フィールド。現実のインプリメンテ
ーションに応じて、情報フィールドにも最大炎と最小長
がある。典型的には、最大炎は約４にバイトであり、最
小長は約８バイトである。情報フィールドにもヘッダー
とトレイラーがあり、これらはエンド・ツ・エンド・プ
ロトコールに関係する。

ＡＮＲがデザインのキー・ポイントであるので、ＡＮＲ
フィールドについてさらに説明する。上述のように、Ａ
ＮＲはｈ個の一連のリンク・アドレスからなる。ＡＮＲ
フィールドのｉ番目のリンク・アドレスは、パケット・
パスに沿うｉ番目のホップの出力リンク・ラベルを規定
する。出力リンク・ラベルは、本質的には内部スイッチ
ＩＤ、つまり出力リンク・アダプタのリンク・アドレス
（ＳＩＤ）である。したがって、パケット・ヘッダーに
は、パスに沿う各中間ノードの中で当該パケットをルー
ティングするのに必要なすべてのルーティング情報が含
まれている。パケットがネットワークの中を進んでいく
につれて″使用済”ＳＩＤは取り除かれるので、ＡＮＲ
フィールドの冒頭のビットは常に現在ノードについての
ルーティング情報を含んでいる。このプロセスは第１図
に記されている。このようにして、すべてのノードは、
当該バスにおける自身の位置を知らなくても、ヘッダー
のＡＮＲフィールドの指示された場所を調べるのである
。外部テーブルのルックアップや処理は不要になるので
、ノード・デイレイは最小になる。

本実施例では、ＡＮＲフィールドの指定場所は、ＡＮＲ
フィールドの冒頭部分であるように選ばれている。ただ
１つのノードの中だけではなくて、トポロジー・ネット
ワーク全体にわたってヘッダーを用いる点が異なる。

パケットは、いくつかのワードに分割して考よることが
できる。本実施例では、各ワードは３２ビツトである。

この数は、第４図に示される３２ビツトのデータ・バス
に対応する。したがって、−時に１ワードが変換（ｔｒ
ａｎｓｌａｔｅ）され、かつ任意の時点でデータ・バス
を伝送されるパケットは１つだけであるとして、パケッ
トがデータ・バスを伝送されるとき、リンク・アドレス
を含む指定場所は、バスを伝送されるパケットの先頭の
ワードの中で見つかることになる。第２図において、リ
ンク・アドレス（ＳＩＤ１）は、パケットの先頭のワー
ドで見つかる最初のアドレスであることに注意されたい
。特殊な用途のために２つのＳＩＤが予約されている。

予約されたＳＩＤとは、常にＮＣＵアダプタのＳＩＤで
あるところのオール・ゼロのＳＩＤと、ダミーＳＩＤと
呼ばれ常に未使用であるオール・ワンのＳＩＤである。

ＳＩＤの長さが異なる場合に、単一ノードの中でプレフ
イクス・コンデイションを強制することの重要性を考え
てみられたい。つまり、ＳＩＤが同一ノード内での別の
ＳＩＤのプレフィクスでないことを確実にすることは重
要である。このプレフィクス・コンデイションは、ＮＣ
Ｕ　　ＳＩＤ及びダミーＳＩＤについても当てはまる。

ＡＮＲフィールドの最後は２つの連続するダミーＳＩＤ
である。（それらはエンド・ポイントにおいて取り除か
れる。）このようにするのは、パケットを誤導しかねな
いＡＮＲＮシフイールド中ット・エラーのせいでパケッ
トが長時間ネットワーク内を動き回ることがないように
するためである。比較的少数のホップの後、ダミーＳＩ
Ｄが使われてパケットは実在しないリンク・アダプタに
導かれ、該パケットを破棄させる。

簡単のために、我々のプロトタイプでは、ＳＩＤは１バ
イトの固定長にしている。そのうちの４ビツトは、実際
の出力リンクのアドレッシングに用いられる。その他の
４ビツトは選択的コピー及びブロードキャスト・メカニ
ズムに用いられる。

第３図は、第１図のスイッチング・サブシステム２０の
概略図である。第３図には、スイッチング・カーネル３
０、コントロール・ユニット５、ネットワーク・コント
ロール・アダプタ２２、リンク・アダプタ（レシーバ）
２５Ｒ１及びリンク・アダプタ・トランスミツト２５Ｐ
が示されている。

アダプタ”なる語は、リンク・アダプタ・トランスミツ
トまたはリンク・アダプタ・レシーブの一方を指すもの
とする。第３図には、リンク１２に連なるバス２１及び
２３が示されている。ネットワーク・コントロール・ア
ダプタとスイッチング・カーネルの間にもバス２４があ
る。

１、スイッチング・カーネル（ＳＫ）３０は、パケット
をソースから宛先へ転送する基本スイッチング機能を実
行する。ＳＫは３２ビツト・パラレル・バスに準拠して
いる。しかしながら、例えば１６．６４ビツト、それ以
上のパラレル・バスを使うこともできる。バスを介して
行うデータの転送は、通常２０〜５０ＭＨｚで作動する
バス・クロックによって同期化される。バスのほかに、
バスを介して情報を送信し得るのは誰かを決定するコン
テンション・レゾリュージョン・ユニット（ＣＲＵ、競
合解消装置）がある。

２、リンク・アダプタ２５Ｔ、２５Ｒは、それぞれ受信
部、送信部からなる。レシーブ・リンク・アダプタは、
リンクから入力パケットを受は取ってスイッチング・カ
ーネルへ送る。トランスミツト・リンク・アダプタは、
ＳＫからパケットを受は取り、必要に応じてそれらをバ
ッファし、出力リンクを介して送信する。アダプタは、
リンクのスピードで作動するクロック（リンク・クロッ
ク）を有する。アダプタ内のロジックの中にはリンクの
スピードで作動するものもあれば、スイッチのスピード
で作動するものもある。

このようなデザインの背後には、以下の２つの基本的な
動機がある。

１、中間ノードを介して行うパケット転送時間を最小に
する。

２、上記目標を、ハードウェアの複雑化を最小限に押え
て達成する。

上記目標の達成を可能にする、我々のデザインにユニー
クな、キーとなる点がいくつかある。以下、入力リンク
から出力リンクへのパケット転送を追いかけながら、こ
のような点の詳しい説明に努めることにする。

パケットはレシーブ・アダプタに高速シリアル・ビット
・ストリームとして到着する。レシーブ・アダプタが最
初にする仕事は、パケットを認識し、シリアル・ツ・パ
ラレル・トランスファーを実行し、入力バッファにスト
アすることである。ビット・トランスペアレンシイを維
持しつつ、中間ノード処理を最小限にするために、我々
はエンド・ツ・エンド・ビット・スタッフィング・プロ
トコールを採用した。したがって、ＨＤ　Ｌ　Ｃのよう
な従来のリンク・プロトコールにおけるように、各ホッ
プでビット・スタッフィング及びデスタッフィング（ビ
ット充填及び充填解除）を実行するのと違って、我々は
エンド・ツ・エンド・ベースでビット・スタッフィング
、デスタッフィングを１口実行する。スタッフィングは
情報フィールドについてのみ行われる。八ツダー・フィ
ールドは中間ノードで使用されることになっているので
、エンド・ツ・エンドでビット充填することはできない
。このように、我々はへラグ−の構造を強化し、その結
果パケットのヘッダ一部分が全くフラグを含まず、した
がってビット充填の必要がなく、中間ノードによって直
接使用し得ることを確実にした。それ故、レシーバ・ア
ダプタのロジックは比較的シンプルである。レシーバが
完全なパケットをストアすると、レシーバはＣＲＵに対
してバスのコントロールを獲得したい旨を知らせる。”
バスのコントロール”は、”バスへのアクセス″と言う
こともできる。アダプタがバスへのアクセス権を獲得す
ると、アダプタは自分のバッファにストアされているパ
ケットをバスへ送出できる。

ＣＲＵがコントロールをレシーバに割り振る方法は、本
デザインのもう１つのきわめて新規な側面である。（Ｃ
ＲＵの立場からは、レシーバ″はソース″であり、トラ
ンスミッタは”宛先”である。）コンテンションの解決
は、ラウンド・ロビン、トークン・パッシング・タイプ
のスキームによって図られる。トークンは１つだけであ
り、該トークンを得たソースがバスを介してパケットを
送る権利を持つ。トークンはロジカル・リングの中をソ
ースからソースへと渡される。我々のスキームとトーク
ン・リング式ＬＡＮで使用されているスキームとの大き
な違いは、我々のスキームでは送信すべきパケットを持
つソースにだけ１・−クンが渡され（バスされ）、かっ
トークン・パッシングは一定時間で行われることである
。（ソースの数に比例する時間ではないのである。）こ
の−定時間はバス・クロックの数クロック・サイクルの
オーダーである。このトークン・パッシングのスピード
ゆえに、バス・バンド幅のむだは最小になる。後のセク
ションで、トークン・パッシングをさらに速く達成する
ことを可能にするテクニックを説明する。バス・バンド
幅のむだを最小にする別の重要な方法は、パケット送信
及びコントロール権移転における並行性を採用すること
である。

つまり、ソースがパケットを送信している間に送信対象
のバケツ１〜とともにトークンを後続ソースへ送るよう
にしている。こうすると、パケット送信に要する時間の
方がトークン・パッシングに要する時間よりも長いと仮
定するなら、バス・バンド幅のむだは生じない。

ＣＲＵのラウントロピン式オペレーションは付加的な利
点をもたらす。すべてのソースに一定時間内でのバスへ
のアクセスを保障するので、公正である。この方式は、
入力リンクのビット速度に限度があっても、バッファ量
が少しであっても、レシーブ・アダプタにおいてバッフ
ァ・オーバーフローの不発生を保障するのに適当である
。

ソースがバスのコントロール権を握ると、完全なパケッ
トを１つ以上送信し終えるのに要する間、コントロール
権を保持する。パケットはワードの形で送られる。各ワ
ードはバス幅と同じバット数からなり、１バス・クロッ
ク・サイクルにつき１ワードが送られる。このようにパ
ケットを完全なエンティティとして送信することによっ
て、宛先でのコンテンションを除去できるという利点が
得られる。つまり、宛先は一時に１パケツトだけを受信
し，２つの別個のソースから同時にパケットを受信する
可能性を考慮しなくてよい。この結果、宛先（トランス
ミツト・アダプタ）のデザインが相当簡単になる。

第４図に示されるように、特殊なワイヤードＯＲライン
３２が２本あってコントロール用に使われる。１つのラ
インはパケットの終り（ＥＯＰ）を示すラインである。

ソースがパケットを送信中であるときは、このラインは
ローの状態にある。

ソースがパケットの最終ワードを送信すると、ソースは
このＥＯＰラインをハイにする。ハイの状態は、別のパ
ケットが送信されるまで続く。Ｅ○Ｐラインは、宛先ア
ダプタに対して新しいパケットの第１ワードを知らせる
のに用いられる。もう１つのラインは、送信終了（ＥＯ
Ｔ）を示す。このラインは、ソースが最終パケットの最
終ワードを送信しているときにハイになる。ＥＯＴは、
トークンのコントロールを握っていてパケットの送信を
開始することのできるソースに対するトリガーである。

続くクロック・サイクルで、このソースは該パケットの
第１ワードを送信し、ＥＯＴラインをローの状態にする
。すべてのクロック・サイクルが有用な情報の送信に使
われることに注意されたい。

宛先では以下のような動作が行われる。ワイヤード○Ｒ
のＥＯＰラインがロー状態にあって新たなパケットの第
１ワード（第２図参照）を表示していることを感知した
ときはいつでも、ＡＮＲフィールドの現在ＳＩＤを運ん
でいるビット位置に対応する、共用バスのラインを調べ
る。そのようなビットは実質上コントロール・フィール
ドの直後のビットである。自身のＳＩＤのサイズに応じ
て、各アダプタは異なる数のラインを調べることに注意
されたい。自身のＳＩＤとの一致が発見されたなら、ア
ダプタは自身の入力ＦＩＦＯバッファをオープンし、当
該パケットの相次ぐワードをデータ・バスからコピーす
る。パケットの最終ワードが送信されると、ＥＯＰがハ
イになり、宛先におけるコピーはストップする。

あるクラスのトラフィックについてのデイレイを少なく
することを保障するために、２レベルのプライオリティ
を導入する。これは、各宛先においてプライオリティ・
レベルごとにＦＩＦ○バッファを設けることによって達
成される。パケットのへラダーのプライオリティ・ビッ
トに応じて、パケットは２つのバッファの何れかに置か
れる。

完全パケットが集まると、宛先はＦＩＦ○バッファの内
容の読み出しと出力リンクを介しての送信を開始する。

ノン・プレエンブチイブ（先買権のない）プライオリテ
ィが達成され、それ故データＦＩＦＯが読み出されるの
は音声ＦＩＦＯが空であるときに限られる。実際にリン
クを介してパケットを送信する前に、宛先アダプタはい
くつかの特別のタスクを実行しなければならない。まず
、次のホップについてのＳＩＤがパケッ１−内の正しい
ビット位置にあることを確実にするため、現在ＳＩＤは
取り除かれなければならない。次に、パケット開始・終
了デリミテーが再構成されなければならない。最後に、
パラレル・ツ・シリアル変換が実行されなければならな
い。

我々は、スイッチング・カーネルを通じてバケツ１〜・
バスの追跡を完成した。ＮＣＵ行きのコントロール・パ
ケットは、宛先アドレスがネットワーク・コントロール
・アドレス、つまり”ｏｏ。

ｏ　ｏ　ｏ　”であることを除き、同様のやり方で動く
。

モニタは、このデザインの中で、最後の、だが決して重
要性が最低というわけではない部分である。Ｄ、　Ｃｏ
ｈｅｎ著の上記文献では、リンク・ローディングの量に
応じてルーティングを修正する方法が論じられている。

該モニタは、かかる量を集める単純かつ効率のよい方法
を提供する。スイッチが共用バスに準拠するので、バス
を通じてのトラフィックを”観察する″モニタ１つでも
って、平均リンク・ローディング、パケット待ち行列長
さを含む、すべての外向きリンクの状況についてのすべ
ての情報を導くことができる。

スイッチング・カーネル（ＳＫ）の基本構造が第４図に
示されている。ＳＫは、パラレル・データ・バス３４、
コントロール・バス３２、及びコンテンション・レゾリ
ュージョン・ユニット（ＣＲＵ）４０からなる。ＣＲＵ
の詳細はこのセクションの中で後で述べる。データ・バ
スは、ソースから宛先へ転送される情報ワードを運ぶ。

データ・バスの幅はノードに応じて変わり得るものであ
り、システムにおける基本ワード幅を規定する。代表的
な値は、１６．３２、及び６４ラインである。

ここでは、３２を代表数とする。また、第４図には、リ
クエスト・ラインＲＱ　（１）〜ＲＱ　（ｎ）及びグラ
ンド・ラインＧＴ　（１）〜ＧＴ　（ｎ）があり、ＣＲ
Ｕとアダプタの間のハンドシェーキングを行う。

先のセクションで述べたように、いつの時点でもバスの
コントロール権を握れるアダプタは１つだけであり、１
以上の完全パケットの転送に要する時間、コントロール
権を保持する。バスを現在コントロールするアダプタは
、カレント・バス・マスターと呼ばれる。バスを通じて
のデータ転送は、共通バス・クロックによって同期化さ
れる。

つまり、１つのバス・クロック・サイクルが、バスを通
じての基本的なワード転送に対応するタイム・スロッ１
−を規定する。完全パケットの転送に要するタイム・ス
ロットの数は、パケット長に応じて可変である。

データ・バスを通じて転送されるパケットのアドレッシ
ングは、パケット中のＳＩＤを使って実行されることを
思い出されたい。各パケットの第１ワードは、決まった
ビット位置に現在使われるＳＩＤを保持している。この
ＳＩＤは当該パケットがフォワードされるべき宛先アダ
プタを識別する。各アダプタはＳＩＤをラッチし、自身
の識別子と比較する。一致が生じたアダプタがあったと
き、該アダプタは自分がパケットの宛先であると認識し
、パケットを１ワードずつデータ・バスから受は取る。

どの宛先ノードも並行して２以上のパケットを受信でき
ないことに注意されたい。結果として、宛先のためにソ
ース識別子を識別する必要がない。

パケット転送が進行している間、送信可能なパケットを
持つ（カレント・バス・マスターを除く）他のすべての
アダプタは、次のパケット転送のためにバスのコントロ
ール権を得るべく、競争する（なお、送信可能なパケッ
トを持つアダプタをアクティブ・ソースと呼ぶことにす
る。）コントロール・バスとＣＲＵは、アクティブ・ソ
ースの組から次のバス・マスターを選択する手段である
。

ＣＲＵはこの選択のためにラウンド・ロビン・スキーム
を用いるので、ソース割振は″公正”なものとなり、か
つソースにて必要とされるバッファ量は有限でよいこと
になる。

各アダプタには、ＣＲＵとハンドシェークするために、
ユニークな出力リクエスト・ライン（ＲＱ）とユニーク
なグランド・ライン（Ｇ　Ｔ）がある。リクエスト・ラ
インは、ＣＲＵに対して、当該ソースがアクティブであ
って次のバケツ１−転送のためにコントロール権をリク
エストしていることを知らせる。ＣＲＵはアダプタの１
つを後続バス・マスターとして選択するが、そのやり方
は対応するグランド・ラインをアクティブにすることに
よって行われる。選択は、カレント・バス・マスターの
識別子（ＩＤ）とリクエスト・ラインの＝３５− 状態の関数によって決まる。さらに、共通ワイヤードＯ
ＲラインであるＥＯＴが、カレント・バス・マスターが
そのパケット転送を完了したことを後続バス・マスター
に知らせるのに使われる。続くバス・クロック・サイク
ルで、後続バス・マスターがカレント・バス・マスター
になり、自分のパケット転送を開始する。データ転送と
コンテンション・レゾリュージョンのプロセスは並行し
て実行されるので、カレント・バス・マスターがそのパ
ケット転送を完了する前に後続バス・マスターが選ばれ
るのが普通である。この結果、システムの負荷が重いと
きにデータ・バスを千金に活用することができる。ＣＲ
Ｕからのスピード要求の厳しさも減る。後続バス・マス
ター選択プロセスを明瞭に説明すべく、アクティブ・ソ
ースによって実行されるアルゴリズムを記述する。

アクティブ・ソース・アルゴリズム １、ＲＱラインを活性化する。

２．０Ｔを待つ。

３、ＥＯＴであるならば、パケットを送信し、ＲＱライ
ンを非活性化する。

４、最終パケットの最終ワード−ＥＯＴを活性化する。

−ｑヱＵ（７）’も紋 ＣＲＵの構造は、基本的にはハードウェアの複雑さとス
ピードの要請との間の１ヘレード・オフである。スピー
ドの要請は、オペレーションの並行性によって緩和され
た。後続バス・マスターの選択は、カレント・バス・マ
スターが送信を終了するまでに完了されるべきである。

すなわち、選択は、データ・バスを通じてのあり得る最
短パケットの転送よりも速く行われるべきである。普通
、これはバス・クロックの数クロック・サイクル分の時
間である。その結果、共通バス・クロックを分周した遅
いクロックを使ってＣＲＵを動作させることが可能にな
る。ＣＲＵが速ければ速いほど（パケット転送とコント
ロール権移転の並行性が必ずしも可能とは限らない）負
荷の軽いシステムにおいて、デイレイを減らすので、有
利であることに注意されたい。

第５図には、ＣＲＵの概要が示されている。複数のセル
がリンク状に並べられており、ｉ番目のセルの出力４２
が（ｉ＋１）番目のセルの入力４４になっている。同図
には、各セルに対応するレシーブ、アダプタ２５Ｒが、
それぞれのグランド・ラインＧＴ及びリクエスト・ライ
ンＲＱとともに示されている。

トークン転送回路（以後、セルとも呼ぶ）は、第６図に
示すことにする。ここでは、同一のセルが環状に連結さ
れてなるグループが示されている。

各セルは１つのアダプタに対応する。図示されているコ
ンポーネントはすべてスタンダードである。

トークン転送ロジック回路５２はＰＡＬでインプリメン
トされ、下記の論理演算を行なう。その他のコンポーネ
ントはスタンダードのゲートである。

各セルは、記憶手段（より詳しくはＤフリップ・フロッ
プ５４）、トークン転送ロジック回路５２、及び当該セ
ルを環の中の隣接セルとアダプタ（第５図の２５Ｒ参照
）に結びつけるライン（入力ライン４２及び出力ライン
４４）からなる。ロジックは、出力ライン４４及びＤフ
リップ・フロップの内容を、入力ライン４２及びフリッ
プ・フロップの状態に従って更新する。当該ロジックは
以下のプール演算を実行する。

○１＝Ｑｉ−８Ｏ−Ｒてｉ＋ζｉ・Ｉｉ・π℃］Ｄｉ＝
Ｑｉ−ＲＱｉ＋Ｑｉ−丁万・Ｉ　ｉ−Ｑ　ｉ上記式にお
いて、Ｉｉはセルｉへの入力、Ｏｉは出力ライン、Ｄｉ
はＤフリップ・フロップの後続状態入力、ＱｉではＤフ
リップ・フロップの現在状態、ＲＱｉではリクエスト・
ラインを、それぞれ表わしている。ＳＯはＯＲゲート５
６の出力を運ぶラインであり、現在クロック・サイクル
において少なくとも１つのアダプタがバスをリクエスト
していることを示すためのものである。

トークンは、Ｄフリップ・フロップの状態によって表現
される。カレント・バス・マスターは、Ｄフリップ・フ
ロップが２１′にセットされた唯一のセルである。ＳＯ
ラインがハイであり（他のアダプタの中にバス・コント
ロール権を欲するものがあることを示す）、かつ自分自
身のＲＱラインが非活動的であるならば、このセルは出
力ライン０を１１１　にセットする。これは、トークン
を次のアクティブ・ソースに渡すことに対応する。

該セルは自身のフリップ・フロップの後続状態を′０′
にセットし、トークンを渡し終ったことを表わす。トー
クンは直ちにノン・アクティブ・セルの間を駆は巡る。

なぜなら、それらのセルは単純に入力■を出力Ｏに移す
だけだからである。トークンは、環の中の次のアクティ
ブ・セルに到達したときに止まる。各アクティブ・セル
は、常にその出力をＯにセットする。アクティブ・セル
が′１′をその入力ラインエで受は取ると、必ず次のク
ロック・サイクルで自身のフリップ・フロップを２１′
にセットする。これは、当該アクティブ・セルがトーク
ンを受は取り、次のバス・マスターであることを表わす
。当該セルは、パケット転送を開始するまで自身のＲＱ
ラインをアクティブに保ち、しかる後このラインを解放
し、残りのアダプタが新たなパケット転送のために競争
できるようにする。

トークンの転送には、ノン・アクティブ・セルの中での
トークン転送ロジックのプロパゲーション・デイレイの
合計分の時間がかかる。各セルは、約ゲート２個分のデ
イレイをきたす。トークン・ロジックのクロックがバス
・タロツクを分周したスピードで動くならば、１トーク
ン・ロジック・クロック・サイクルの間にトークンは充
分バスされ得る。

トークン転送回路を拡張して、多数のアダプタ及びアダ
プタの数にだけ比例する複雑さの増加を許容することが
できる。しかしながら、プロパゲーションデイレイもま
たこの数に比例して増加する。トークン転送回路をスピ
ード・アップするために、第７図に示す如くルック・ア
ヘッド・ロジックを付加してもよい。この装置は、１つ
のセル、例えばセル（ｉ−１）から、別のセル、例えば
セル（ｉ＋４）へ、中間セルに関連するアダプタの何れ
もがネットワークへのアクセスをリクエストしないとき
にそれら中間セルをバイパスしてトークンを移すことを
可能にする。第７図に示されるように、バイパス可能な
中間セル（すなわち、セルｉ　−３，＋　３　）のリク
エスト・ラインを入力とするＮＯＲゲート７２がある。

また、同図には、セル（ｉ−１）の出力ラインとＮＯＲ
ゲート７２の出力を入力とするＡＮＤゲート７４も示さ
れている。ＯＲゲート７６は、ＡＮＤゲート７４の出力
と、中間セルの１つ、例えばセル（ｉ＋３）の出力を、
その入力としている。ＯＲゲート７６の出力はセル（ｉ
　＋４）の入力となる。この回路によると、どの中間セ
ルもその関連アダプタからのネットワーク・アクセス獲
得リクエストを持っていないことをＮＯＲゲートが表示
するとき、トークンをセル（ｉ−１）からセル（ｉ　＋
４）へ直に渡すことが可能になる。

コンポーネントはスタンダードのオフ・ザ・シェルフ・
ゲートである。ルック・アヘッド・ロジックの本質は、
環の中のアクティブ・セルを持たない部分におけるプロ
パゲーション・デイレイをなくすことである。図では、
プロパゲーション・デイレイを減らすために、４セルの
グループを迂回する方法を説明した。このルック・アヘ
ッド・ロジックは、マルチ・レベルにも拡張することが
できる。

リンク・アダプタ 第８図ないし第１２図に示されるように、リンク・アダ
プタは２つの全く独立した部分、つまりレシーバ２５Ｒ
とトランスミッタ（図１０図の２５Ｔ）からなる。以後
、″アダプタ″なる語は、レシーバとトランスミッタの
組合せ、レシーバ自体、またはトランスミッタ自体を指
すものとする。

また、′ソース・アダプタ”なる語はバスを通じて送信
を行うアダプタを指し、″宛先アダプタ″はバスからパ
ケットを受信するアダプタを指すものとする（第４図の
３４参照）。ＳＳの概論で述べたように、レシーバ（第
８図参照）は、物理的な入力リンク（第１図の１２参照
）を通じてシリアルに受は取るデータ・ストリームを処
理する。

第８図に示すように、レシーバは、パケットを区切り、
シリアル・ツ・パラレル変換を行い、バケツ１〜を３２
ビツト・ワードとしてそのバッファに＝４３ ストアする。完全なパケットをストアすると、レシーバ
は、バス・マスターになるために必要なスイッチング・
カーネルとのハンドシェークを行う。

コントロール権を得た後、レシーバは、その人力バッフ
ァ８３の中のパケットを１ワードずつデータ・バスに転
送する。また、レシーバは、このプロセスにおける、受
信データ・ストリーム中のビット・エラーに起因するい
くつかのエラーの回復をも行う。

トランスミッタ（第１０ないし第１２図参照）は、パケ
ットを外向きの物理リンク（第１０図の１２参照）に送
る役目を果す。トランスミッタはデータバス（第１０図
の２３参照）を通じて自分に向けられてきたパケットを
（ＳＩＤを使って）検出し、プライオリティ（つまり音
声であるかデータであるか）に応じてパケットを分別し
、そしてそれらをバッファ（第１０図の１０４，１０５
参照）にストアする。第１０図のデータ・バス２３は、
第４図のデータ・バス３４とコントロール・バス３２の
１部である。完全に受は取ったバケツトがあるときは、
トランスミッタはプライオリティとファースト・カム・
ファースト・サービス方式に従ってパケットの１つを選
び、物理的な出力リンクを介してシリアル・ビット・ス
トリームとして送信することを開始する。トランスミッ
タはまた当該ビット・ストリームから既使用ＳＩＤ部分
を取り除く。トランスミッタはまたこのプロシージャに
おいて可能性のあるエラー、つまりバッファ・オーバー
フローの回復も行う。

レシーバ レシーバの構造の概略は第８図に示されている。

レシーバの主要部は、フラグ検出ロジック８２を備えた
入力シフト・レジスタ８１、バッファ・セクション８３
と８７、出力三状態データ・レジスタ８４、及び２つの
有限状態コントロール・ユニットＦＳＭＩ　（８５）及
びＦＳＭ２　（８６）である。すべてのシフト・レジス
タ、王状態レジスタ、及びロジック・コンポーネントは
、スタンダードのオフ・ザ・シェルフ・コンポーネント
である。

基本的に、ＦＳＭＩは入力ビット・ストリーム中のパケ
ット境界を検出し、受信したパケットをメモリ・モジュ
ールにストアする。ＦＳＭ２はメモリ・モジュールから
バケツ１〜を受は取り、必要なスイッチング・カーネル
とのハンドシェークを実行した後に、パケットをデータ
・バス（第４図の３２参照）に転送する。どちらのＦＳ
ＭもスタンダードのＰＡＬでインプリメントされる。こ
れらのＦＳＭの状態遷移図が第１３図ないし第１６図に
示されている。バッファ・セクションは、パケットをス
トアするための大きなＦＩＦ○メモリ（パケット・バッ
ファ）と、ＦＳＭＩとＦＳＭ２の間の通信用の小さなＦ
ＩＦ○コントロール・バッファとからなる。ＦＩＦＯは
スタンダードのオフ・ザ・シェルフＦＩＦＯメモリ・チ
ップであり、非同期式リード／ライト能力を持っている
。大きなＦＩＦＯは３２ビツト幅、つまりデータ・バス
分の幅を持っている。このＦＩＦＯは、少なくとも最大
炎のパケットを４個収容できるほどに十分大きくなけれ
ばならない。小さなＦＩＦＯは２ビツト幅である。この
ＦＩＦＯは、大きなＦＩＦＯに存在し得る最小サイズの
パケットと同じ数のワードを収容できなければならない
。実際上は、ＦＩＦＯメモリの大部分をＲＡＭで置き換
えることが好ましいことがある。しかしながら、ＦＩＦ
Ｏメモリを使った場合の方が説明がはかどるし、かつ大
規模ＦＩＦＯメモリは市販されているので、ここではか
かるメモリの使用を仮定する。なお、第８図にはワード
・カウンタ８８とピッ１〜・カウンタ８９があり、パケ
ット中のワード境界を識別するのに用いられる。

以下では、ＦＳＭＩの動作を説明する。長時間パケット
が受信されておらず、ＦＳＭＩが新たなパケットを待っ
ているものと仮定しよう。入ってきたビット・ストリー
ムは入力シフト・レジスタへとシフトされる。フラグの
存在を検出するために、このレジスタの先頭の６ビツト
について論理的なＡＮＤがとられる。フラグは、２つの
相次ぐパケットを分ける１”のシーケンスの始まりを意
味する。フラグを検出すると、ＦＳＭＩは新たなパケッ
トの開始を待つ。この事象のシグナルになるのは、フラ
グの後の出力り。における最初のＯの検出である。この
ことが起こると、新バケツ１〜の第１ワードがメモリに
ストアされる。同時に、ビット・カウンタ及びワード・
カウンタがリセットされる。この時点以後、新たにフラ
グが検出されない限り、ＦＳＭＩは３２リンク・クロッ
ク・サイクルごとに新たなワードをストアする。（３２
ビツトはワード幅を表わすべく選択された典型値である
ことを思い出されたい。）フラグの検出はＦＳＭにとっ
てカレント・パケットの終りを示す。メモリ内でパケッ
トを区別するために、その最も右の部分にフラグ（６個
の連続するＩＩ　Ｉ　ＩＩ　）を持つワードは、必ずパ
ケットの最終ワードの後にストアされる。そのようにす
るため、パケットの終りを示すフラグが検出されたなら
、ＦＳＭＩは（その最も右の部分に当該フラグを含む）
ＳＲの内容をメモリにストアする。同時に、ＦＳＭＩは
、パケットが完全に受信されたことをＦＳＭ２に示すパ
ケット到着（ＰＡ）　、及びパケットが転送または破棄
（デイスカート）されるべきことをＦＳＭ２に示すパケ
ット・アクセプト／デイスカート（Ａ／Ｄ）のフラグを
、コントロール・バッファに書き込む。Ａ／Ｄフラグは
、ワード・カウンタを使ってカウントされたパケットの
ワード長に応じて更新される。パケットのサイズが正し
い値であって（つまり、パケット長の最小値と最大値の
間の数である）当該バケツ１〜がスイッチング・カーネ
ルにフォワードされるべきものであることを示している
場合に、ＦＳＭＩはＡ／Ｄフラグ］−にセットする。そ
の他の場合は、Ａ／ＤフラグはＯにセットされる。ここ
で、ＦＳＭＩは新たなパケット捜しに戻る。

パケット・サイズに上限と下限を設けることは、ビット
・エラーによってパケットが多数の小パケットに分かれ
たり、２以上のパケットが併合されてより大きなパケッ
トになってしまったときに生じる不必要なパフォーマン
ス劣下を避けるのに必要である。ここではＡ／Ｄフラグ
の状態をパケット長のカウントにのみ基づかせているけ
れども、他の基準に基づかせても構わない。特に、ある
種のリアル・タイム・エラー・チェツキングを用いて、
ビット・エラーを検出し、ＳＫに入ってしまう前にパケ
ットを破棄するようにしてもよい。

次に、ＦＳＭ２の動作を説明する６ＦＳＭ２は、コント
ロール・バッファ中のＰＡフラグによってフル・パケッ
トがＦＩＦＯメモリに完全にストアされたことが示され
るときにその動作を開始する。

Ａ／Ｄフラグによってパケットが転送されるべきである
ことが示される場合は、ＦＳＭ２はそのＲＱラインを活
動させてスイッチング・カーネルとのハンドシェークを
実行する。ＦＳＭ２がＥＯＴラインとＧＲラインの両方
がアクティブであることを検知したときは、ワイヤード
○ＲのＥＯＴラインとリクエスト・ラインをローにしく
非活動化し）、ワードのデータ・バスへの転送を開始す
る。

これは、メモリからワードを読み（リード）、かつ三状
態（３Ｓ）レジスタをイネーブル状態にすることによっ
て行われる。ＦＳＭＩは、ＦＩＦＯコントロール・バッ
ファのアクセス箇所を次のロケーションへと進める（ア
ドバンス）。フラグが検出されると、（つまり、パケッ
ト間の分離ワードが読まれると、）ＦＳＭＩはＦＩＦ○
コントロール・バッファの内容をテストする。転送対象
となる別のパケットがあるならば、ＦＳＭ２はコントロ
ール・バッファをアドバンスし、当該パケットの転送を
続ける。フラグが検出され、かつコントロール・バッフ
ァによってメモリ中にもうパケットがないこと、または
次のパケットが破棄されるべきことが示されるときに、
パケットの送信は終了する。かかる事象においては、Ｆ
ＳＭＩは（フラグを含む）最終ワードをデータ・バスへ
転送し、かつＥＯＴラインを活動させる。パケットが破
棄されるべきときは、ＦＳＭ２はフラグが検出されるま
でＦＩＦＯメモリを読み続けるだけである。この場合、
王状態レジスタはディスエーブルのままである。

第９図は、パケットがメモリ内でワードに分かれる様子
を示す。第１３図ないし第１６図は、ＦＳＭＩ及びＦＳ
Ｍ２の状態図である。

第１０図は単にトランスミッタとも呼ばれる１−＝５１ ランスミッタ・アダプタの概略図である。トランスミッ
タの主要部は、データ・レジスタ１０１、Ｖ／Ｄフリッ
プ・フロップ１０２、及びアドレス・レジスタ１０３か
らなる入力ラッチ、音声待ち行列１０４、データ待ち行
列１０５、及び選択回路１０６．１０７からなるバッフ
ァ・セクション、２個の有限状態制御回路ＦＳＭＩ　　
１０８とＦＳＭ２　１０９、出力シフト・レジスタ１１
０及びリンク・マルチプレクサ１１０である。出力シフ
ト・レジスタとリンク・マルチプレクサは、どちらも第
１０図のリンク前処理回路の一部を構成するものである
。リンク・プロセッサの詳細は第１２図に示されている
。第１０図には、バス１１３〜１１５及び比較器１１２
も示されている。コンポーネントはすべてスタンダード
のオフ・ザ・シェルフのデバイスである。以下ではトラ
ンスミッタの動作を説明する。

第１１図は、トランスミッタのうちＦＳＭＩに関連する
部分を詳しく示したものである。ＦＳＭｌ　１０８は、
スタンダードＰＡＬでインプリメントされる。Ｖ／Ｄフ
リップ・フロップ１０２はコントロール・フィールドの
最初のビットを見る。

一方、アドレス・ラッチ１０３はコントロール・フィー
ルドに続く最初の数ビットを見る。（リンク・アドレス
とも呼ばれる）ＳＩＤの長さは一定ではないので、各ト
ランスミッタ・アダプタ内のラッチが見るビット数は異
なっていてよい。各タロツク・サイクル（バス・クロッ
ク）で、新しいデータ・ワードがデータ・レジスタ（第
１０図の１０１参照）にラッチされる。アドレス・レジ
スタ１０３とＶ／Ｄフリップ・フロップ１１６へのラッ
チが行われるのは、ＥＯＰラインがローになった後の最
初のクロック・サイクルにおいてのみである。このワイ
ヤード○Ｒラインはレシーバ・アダプタがパケットの最
終ワードを送信したときにハイになり、後続パケットの
第１ワードがスイッチング・カーネルを介して送られた
ときにローになることを、思い出されたい。Ｖ／Ｄビッ
トは、当該パケットのターゲットとして音声ＦＩＦＯメ
モリかデータＦＩＦＯメモリを選択すべく入力選折回路
１０６をセラ１へするのに用いられる。アドレス・レジ
スタの内容は、比較器１１２によって当該アダプタのＳ
ＩＤと比較される。この比較器の出力、つま、リマッチ
（一致）・ラインは、ＦＳＭｌに供給される。一致した
とき、ＦＳＭｌは、（入力選択回路によって選ばれた）
ＦＩＦＯメモリ１０４または１０５の中へパケットを１
ワードずつストアすることを開始する。ＥＯＰが検出さ
れると、ＦＳＭＩは、選択されたＦＩＦＯコントロール
・バッファ１１７または１１８の中へ、ＰＡ及びＡ／Ｄ
フラグを書き込む。今、どちらも１であるとしよう。こ
の結果、ＦＳＭ２は、パケットが正確に受は取られたこ
と、およびパケットが出力リンクを通じて送信されるべ
きものであることを知る。ＥＯＰの活動化の前にＦＩＦ
Ｏメモリが一杯（フル）になったならば、ＦＳＭＩはＥ
ＯＰ信号を待ち、最終ワードをメモリにストアしくフラ
グが含まれる）、適切なコントロール・バッファにおい
てＰＡフラグを１にセットするとともにＡ／Ｄフラグを
Ｏにセットする。この結果、ＦＳＭ２は、バッファ・オ
ーバーフローのためにパケットが改悪されたので破棄す
べきものであることを知る。

第１２図は、トランスミッタのうちＦＳＭ２に関連する
部分を詳しく示したものである。ＦＳＭ２１０９は、ス
タンダードＰＡＬでインプリメントされる。ＦＳＭ２の
とる行動を説明しよう。

今、ＦＳＭ２が先行パケットを送信し終ったばかりか、
あるいは長時間パケットを送信していなかった場合を考
えよう。このような場合、ＦＳＭ２は出力選択論理回路
１０７のために入力１１１１１を選択している。ＦＩＦ
Ｏメモリ１０３または１０４のうちの１つにてパケット
が待機中であることを（コントロール・バッファから）
検知したとき、ＦＳＭ２は１選択ラインを活動させ、出
力選択回路をして音声またはデータのＦＩＦ○メモリの
何れか、音声またはデータのコントロール・バッファ１
１７，１１８の何れかを、音声パートを優先させつつ、
選択する。対応するＡ／Ｄラインによれば当該パケット
がアクセプトされるべきあるとき、以下のステップが実
行される。まず、第１ワードがメモリからシフト・レジ
スタ１２１にラッチされる。フラグの識別はＡＮＤゲー
ト１２２によって行われる。当該ワードがフラグを含ん
でいるならば、次のワードがメモリからシフト・レジス
タへ直ちにラッチされる。この時点で、ＦＳＭ２はシフ
ト・レジスタのＡ出力を選択し、そのシフトを開始する
。１１ビツトが出力リンク１２に送出された後、ＦＳＭ
２は、リンク・マルチプレクサ１２４への入力であるＭ
ＵＸ選択ライン（Ａ、Ｂ、または１”）を使ってシフト
・レジスタのＢ出力を選択する。このように選択を変え
ることによって、出力シリアル・ビット・ストリームか
ら使用済５ＩＤ（長さは例えば５ビツトである）が除去
される。続いて合計２７リンク・クロック・サイクルが
経過した後、ＦＳＭＩは新しいワードをメモリからシフ
ト・レジスタにラッチする。この時点からフラグが検出
されるまでの間、ＦＳＭ２はシフト・レジスタをシフト
させ、出力Ａを選択し、３２クロック・サイクルごとに
メモリを読む。フラグが検出されると、ＦＳＭＩはコン
トロール・バッファをアドバンスし、１１１１１出力を
選択して、この手順を繰り返す。コントロール・バッフ
ァがＦＳＭ２に対してパケットの破棄を命じるときは、
ＦＳＭ２はフラグが検出されるまでワードをメモリから
シフト・レジスタヘラッチし続ける。この手順の間中、
出力ｎＶｒが選択される。

ビット・カウンタ１２０から延びるライン１２３上の数
字”＝１０”、”＝２６”、”＝　３１　”は、パケッ
トがネットワークのノードから送信されるときの５ＩＤ
（リンク・アドレス）の除去の目的でカウンタのカウン
トを識別する。

トランスミッタの記述を完全にするため、第１３図ない
し第１６図にＦＳＭＩ及びＦＳＭ２の状態図を示す。第
１３図、第１４図、第１５図、第１６図は、それぞれレ
シーバＦＳＭＩ、レシーバＦＳＭ２、トランスミッタＦ
ＳＭＩ、トランスミッタＦＳＭ２の状態図である。第１
８図は、これらの図で用いられる記号の意味を示してい
る。第１７図を参照すると、ＮＣＵは、リンク・アダプ
タによく似たアダプタ２２を介してスイッチング・サブ
システムに接続される。ネットワーク・コントロール・
アダプタは基本的には第３図のリンク・アダプタ２５Ｒ
１２５Ｔと同じである。入力及び出力データＦＩＦＯ１
７２，１７６は、ＮＣＵバス６（この場合は、ＰＳ２バ
ス）のメモリ・アドレス空間に直にマツプされる。した
がって、ＮＣＵはこれらのデータＦＩＦ○に対して直に
読み書きを行うことができる。データＦＩＦ○とバス３
４の間のインターフェースの役をするバス・ドライバ１
７８も図示されている。ネットワーク・コントロール・
アダプタからＣＲＵ４０への接続は、リンク・アダプタ
からＣＲＵへの接続と同様である。実際、ネットワーク
・コントロール・アダプタは、第５図のリンク・アダプ
タの１つとして考えることができる。

ＮＣＵは、パケットを、当該パケットを入力データＦＩ
Ｆ○１７２に書き込むことによって送り、シングル・ワ
ードを状況ＦＩＦ○１７４に書き込むことによって入力
コントロール１７３に合図する。入力コントロールは、
リンク・アダプタにおけるＦＳＭ２と同様に、バスにア
クセスすること、及びバスへパケットを読み出すことに
責任を持つ。

バス３４から受は取ったパケットは、リンク・アダプタ
のＦＳＭ３と同様の出力コントロール１７５によって、
出力データＰＩＦ０１７６へ書き込まれる。完全なパケ
ットが受信されると、ワードが状況ＦＩＦ○１７７に書
き込まれ、ＮＣＵに対し当該事象を知らせる。ＮＣＵは
、当該パケットを、バス・アドレス空間にマツプされた
出力データＦＩＦＯから直に読み取る。

Ｆ、効果 本発明によれば、パケット・スイッチング・ノード等に
おけるアダプタ間の通信におけるデイレイが削減される
という優れた効果が得られる。

【図面の簡単な説明】

第１図は、多数のスイッチング・ノードを持つ通信ネッ
トワークの説明図である。 第２図は、オートマチック・ネットワーク・ルーティン
グ（ＡＮＲ）フィールドを持つバケツ１〜の説明図であ
る。 第３図は、スイッチング・サブシステムの説明図である
。 第４図は、スイッチング・カーネルの説明図である。 第５図は、コンテンション・レゾリュージョン・ユニッ
トの説明図である。 第６図は、リング状に配されたセルの説明図である。 第７図は、中間セルをバイパスして行うトークンのバス
を行うための回路図である。 第８図は、レシーバ・アダプタ（単にレシーバあるいは
アダプタとも言う）の概要の説明図である。 第９図は、レシーバ・アダプタのレシーバ・バッファ内
のパケットの説明図である。 第１０図は、トランスミッタ・アダプタ（単にトランス
ミッタあるいはアダプタとも言う）の概要の説明図であ
る。 第１１図は、１−ランスミッタ・アダプタのうちの有限
状態コントロール回路ＦＳＭＩに関する部分の詳細な説
明図である。 第１２図は、トランスミッタ・アダプタのうちの有限状
態コントロール回路ＦＳＭ２に関する部分の詳細な説明
図である。 第１３図は、トランスミッタＦＳＭＩの状態図である。 第１４図は、トランスミッタＦＳＭ２の状態図である。 第１５図は、レシーバＦＳＭＩの状態図である。 第１６図は、レシーバＦＳＭ２の状態図である。 第１７図は、第２図のネットワーク・コントロール・ア
ダプタの概要の説明図である。 第１８図は、第１３図ないし第１６図で用いる記号の説
明図である。

Claims (3)

【特許請求の範囲】
1. （１）並列通信バスを通じてソース・アダプタのＦＩＦ
   Ｏメモリから宛先アダプタのＦＩＦＯメモリにパケット
   を転送する方法であって、 各転送対象パケットのリンク・アドレスを当該パケット
   内の指定されたワードに含ませておいた上で、以下のス
   テップを実行することを特徴とする方法。 （ａ）転送対象のパケットを上記ＦＩＦＯメモリから１
   クロック・サイクルにつき１ワードずつ読み出すことを
   、上記パケットのすべてのワードが読み出されつくすま
   で繰り返す。 （ｂ）上記パケットの先頭ワードと最終ワードを識別し
   て上記パケットの境界を識別する。 （ｃ）１クロック・サイクルの間に、上記バスにアクセ
   スし得るすべてのアダプタにおいて、上記パケットの上
   記指定ワードにある上記リンク・アドレスと当該アダプ
   タ自身に関するリンク・アドレスとを比較し、両者が一
   致したアダプタにおいて当該アダプタのＦＩＦＯメモリ
   に上記パケットを書き込む。
2. （２）通信バスにアクセスする複数のアダプタ間の競合
   を解消するための、以下の要件からなる装置。 （ａ）上記複数のアダプタと一対一に対応させた複数の
   セルを設け、かつこれらのセルをｉ番目のセルの出力が
   （ｉ＋１）番目のセルの入力となるように環状に配列す
   る。 （ｂ）上記セルの各々には、当該セルに対応するアダプ
   タが上記バスのアクセス権を得たことを示すトークンを
   ストアするためのトークン・ストア手段を設ける。 （ｃ）上記セルの各々には、当該セルに対応するアダプ
   タが上記バスのアクセス権の獲得を欲しない場合におい
   て先行するセルがトークンを当該セルに向けて送信中で
   あるとき、または上記場合において当該セルが上記スト
   ア手段にトークンをストアしているときに、トークンを
   他のセルに転送するトークン転送手段を設ける。
3. （３）通信ネットワークにアクセスする複数のアダプタ
   と一対一に対応させた複数のセルを設け、かつこれらの
   セルを環状に配列し、 上記セルの各々には、当該セルに対応するアダプタが上
   記ネットワークのアクセス権を得たことを示すトークン
   をストアするためのトークン・ストア手段を設け、 上記環において、現在上記バスのアクセス権を獲得して
   いるアダプタに対応する第１のセルと次に上記バスのア
   クセス権の獲得を欲するアダプタに対応する第２のセル
   との間に、上記バスへのアクセス権を欲しない中間セル
   があるときは、該中間セルをバイパスして上記第１のセ
   ルから上記第２のセルへトークンを転送する手段を設け
   たことを特徴とするトークン・リング装置。