JPH063913B2

JPH063913B2 - データの転送方法

Info

Publication number: JPH063913B2
Application number: JP61063882A
Authority: JP
Inventors: ロナルド・アール・ホツヒスプルング; ローレンス・エイ・ケニヨン，ジユニア; アラン・ビイ・オツペンハイマー; ガーシヤラン・エス・シドウ
Original assignee: Apple Computer Inc
Current assignee: Apple Inc
Priority date: 1985-03-21
Filing date: 1986-03-20
Publication date: 1994-01-12
Anticipated expiration: 2009-01-12
Also published as: AU574892B2; DE3608173A1; US4661902A; SG63389G; GB2172778B; JPS61287355A; CA1265257A; FR2579341B1; GB8602808D0; GB2172778A; DE3608173C2; AU5334686A; FR2579341A1; HK36590A

Description

【発明の詳細な説明】〔利用分野〕本発明は、ソースと複数の受信データ処理装置の間でデ
ータを転送する装置および方法に関するものであり、更
に詳しくいえば複数のデータ処理装置および複数の周辺
装置の間でローカリ・エリア・ネットワークに沿ってデ
ータを転送することに関するものである。

〔技術的背景〕

コンピュータ業界においては、たとえばコンピュータ、
プリンタ、メモリ等のような複数のデータ処理装置の間
でのデータと命令との転送は、全く普通のことである。
コンピュータおよび他の周辺装置の間の相互接続は、コ
ンピュータ・ネットワーキング装置の出現により、主と
して１９７０年代の初期に開発された。そのコンピュー
タ・ネットワーキング装置により、隣接するメインフレ
ームコンピュータをこえて処理リソースに対するアクセ
スの分配ができるようになった。

種々のユーザーが大型の時分割装置に対するアクセスを
行うとともに、それらの装置の間でのデータの転送を行
うために、ARPAネットワークのようなネットワークが開
発された。地理的に局地的なネットワークの場合には、
典型的には同じ建物または隣接する建物内に配置されて
いる一群のコンピュータ、端末装置および周辺装置を一
緒に接続するためにいわゆる「ローカル・エリア・ネッ
トワーク」(LAN)が開発された。そのローカル・エリア
・ネットワークによりそれらの各装置はそれらの装置相
互間で、かつ他のネットワークに取りつけられている他
の装置との間で通信できることになる。ネットワークに
より分散コンピューティングないし分布コンピューティ
ングを実現できる。言い換えると、ローカル・エリア・
ネットワークに結合されているいくつかの装置を、ファ
イル格納、データベース管理、端末装置の取扱い等のよ
うな特殊な機能の実行に専用させることができる。種々
のタスクを実行する異なるマシンを有することにより、
分布コンピューティングはシステムの実現を一層容易か
つ効率良く行うことができる。

ローカル・エリア・ネットワークは、長距離伝送を行う
同種のネットワークとはいくつかの面で異なる。決定的
な差異は、ARPAネットワークのような長距離伝送ネット
ワークの設計者が、経済的な理由および法令上の理由に
より、それが技術的に妥当かどうかとは無関係に公衆電
話ネットワークを使用することを余儀なくされることで
ある。これとは対照的に、ほとんどのローカル・エリア
・ネットワークは、LANに結合されている種々の装置の
間でデータグラムサービスを行うことができるように自
身の広い帯域幅のケーブルを使用する。キャリヤ・セン
ス・ローカル・エリア・ネットワーク用の最も一般的な
伝送媒体は、同軸ケーブル、より線対ケーブル、および
光ファイバである。直線状（リニア）、背骨状（スパイ
ン）、樹状（ツリー）、環状（リング）およびセグメン
ト状のような各種のケーブル配列が可能である。また、
他の大規模なネットワークにおいては固有のものである
長い伝播遅延がローカル・エリア・ネットワークには無
いから、チャネルの利用度を大規模なネットワークのそ
れより高くできる。

ローカル・エリア・ネットワークはデータ処理装置の間
の分布処理および通信を有望にするものではあるが、イ
ーサネット(ETHERNET)（米国特許第４０６３２２０号）
のようなローカル・エリア・ネットワークが広く用いら
れ、受け容れられることの妨げになるいくつかの要因が
ある。たとえば、VLSIを使用することによりコストを低
減しようとする努力にもかかわらず、典型的なLANノー
ドはパーソナルコンピュータの全費用のかなりの割合を
占めることがある。したがって、パーソナルコンピュー
タの市場においては、ローカル・エリア・ネットワーク
は実現が阻害されるほど高かった。また、ほとんどのロ
ーカル・エリア・ネットワークは複雑なケーブル配線技
術を利用しており、LANシステムの設置、更新および保
守についての教育を受けたシステム管理者を必要とす
る。更に、LANに結合されている各種の装置が種々の条
件の下で通信できるようにするために、多くのローカル
・エリア・ネットワークは比較的複雑なプロトコルを利
用している。

〔発明の概要〕

本発明は、種々のコンピュータ、補助装置、ディスク、
プリンタ、モデム、およびその他のデータ処理装置の間
の通信およびリソース共用のためのローカル・エリア・
ネットワークを提供するものである。本発明は広範囲の
ローカル・エリア・ネットワークのサービスを支援し、
ブリッジ装置を用いることにより大規模なネットワーク
と通信できるようにするものである。本発明は、経済的
で、信頼度が高く、機械的に簡単な、これまで知られて
いなかったローカル・エリア・ネットワークを提供する
ものである。

この明細書においては、ケーブルのような通信媒体に接
続されているデータ処理装置（エージェント）の間でデ
ータを転送する次の方法が開示される。

本発明によれば、次の転送方法が提供される。

すなわち、 (A)送出のデータ処理装置が、通信媒体上に他のデータ
処理装置からのデータが存在しているか否かを、通信媒
体上の同期信号の検出によって決定する過程と； (B)送出のデータ処理装置が、通信媒体上に同期信号を
送出したときは、受信のデータ処理装置への通信媒体を
介したデータ転送を延期し、過程(A)へ戻り； (C)送出のデータ処理装置が、通信媒体上に同期信号を
検出しないときは、第１の所定期間待機し、その第１の
所定期間中も通信媒体上の同期信号の検出を行う、第１
の待機・検出の過程と； (D)送出のデータ処理装置が、第１の所定期間中に、通
信媒体上に同期信号を検出したときは、過程(C)を繰り
返し、 (E)送出のデータ処理装置が、第１の所定期間中に、通
信媒体上に同期信号を検出しないときは、次の乱数Ｒに
対応した付加待機期間の通過、すなわち、送出のデータ
処理装置において、(1)所定の範囲内で且つ(2)送出のデ
ータ処理装置についての送出したいデータに関する衝突
および延期の履歴に応じて発生される乱数Ｒに対応した
付加待機期間の経過を持ち、その付加待機期間中も通信
媒体上の同期信号の検出を行う、付加待機・検出の過程
と； (F)送出のデータ処理装置が、付加待機期間中に、通信
媒体上に同期信号を検出したときは、前記乱数Ｒの調整
用動作を行い且つ過程(B)へ戻り、 (G)送出のデータ処理装置が、付加待機期間中に、通信
媒体上に同期信号を検出しないときは、次の動作を生じ
させる第１の信号、すなわち、受信のデータ処理装置に
よりその第１の信号が受信されると受信のデータ処理装
置から送信のデータ処理装置へ通信媒体を介して第２の
信号を返送する動作を生じさせる第１の信号を、受信の
データ処理装置へ通信媒体を介して送出する過程と； (H)送出のデータ処理装置が、受信のデータ処理装置へ
の第１の信号の送出から始まる第２の所定期間にわたっ
て、受信のデータ処理装置から返送される第２の信号を
受信するために待機し、もし第２の所定期間内に第２の
信号が受信されなければ衝突の発生と判断するための過
程と； (I)送出のデータ処理装置が、第２の所定期間内に受信
のデータ処理装置からの第２の信号を受けたときは、そ
の受けた時点から始まる第３の所定期間内に、受信のデ
ータ処理装置へ通信媒体を介してデータを転送する過程
と； (J)送出のデータ処理装置が、第２の所定期間内に受信
のデータ処理装置からの第２の信号を受けず、従って衝
突の発生と判断されるときは、前記乱数Ｒの調整用動作
を行い且つ過程(C)へ戻る過程とを備える、データの転送方法が提供される。

このデータの転送方法により、簡単な構成により、効率
良く衝突の発生を最小限にすることができるから、共通
ケーブルに結合されている複数のデータ処理装置間でデ
ータを確実かつ経済的に送信する方法が提供される。

〔実施例〕

この明細書においては、共通のケーブルに結合されてい
る複数のデータ処理リソースの間でデータを転送する装
置および方法を含むローカル・エリア・ネットワークを
開示するものである。以下の説明においては、本発明を
完全に理解できるようにするために、特定の数、バイ
ト、レジスタ、アドレス、時間、信号、および書式（フ
ォーマット）等が述べてある。しかし、そのような特定
の詳細事項なしに本発明を実施できることが当業者には
明らかであろう。その他の場合には、本発明を不必要に
詳しく説明して本発明をあいまいにしないようにするた
めに、周知の回路および装置はブロック図で示した。

以下、図面を参照して本発明を詳しく説明する。

まず第１図を参照して、本発明は、複数のデータ処理装
置２５〜２８と、プリンタ３０のような周辺装置（また
は、たとえば広域メモリ(globalmemory)、ディスクドラ
イブ等のような他の装置）とを含むことができる。説明
のために、本発明のローカル・エリア・ネットワークに
結合されている全てのデータ処理装置および全ての周辺
装置をまとめてエージェントと呼ぶことにする。図示の
ように、データ処理装置２５〜２８とプリンタ３０は、
相互にデータを転送するために共通ケーブル３２により
相互結合される。種々の装置は接続モジュール３４によ
りケーブル３２に結合される。ここで説明している実施
例においては、その接続モジュール３４は受動結合トラ
ンスと、抵抗性および容量性の回路を含む。それらの受
動結合トランスと、抵抗性および容量性の回路は、各デ
ータ処理装置およびその他の装置をケーブル３２に結合
するためのものとしてこの分野において知られているも
のである。信号の反射を無くすためにケーブル３２は適
切に終端させられる。ここで説明している実施例におい
ては、ケーブル３２はより線対ケーブルにより構成さ
れ、１００オームの抵抗により終端させられる。ケーブ
ル３２は、同軸ケーブル、光ファイバ、無線チャネル等
のような共用され得る媒体で構成できる。ここで説明し
ている実施例においては、エージェントはケーブル３２
へ受動的に結合されるから、エージェントまたは接続モ
ジュールが故障しても、ケーブル３２上の通信を中断さ
せることはない。

後で説明するように、プロトコルと、衝突回避および検
出の方法と装置とを用いて、データ処理装置２５〜２８
およびプリンタのようなその他の周辺装置の間の同期直
列通信、およびデータ転送を行えるようにするローカル
・エリア・ネットワークを本発明は提供するものであ
る。本発明のアーキテクチャおよびプロトコルは、従来
の装置に共通のハンドシェイキングと衝突検出技術をで
きるだけ簡単にし、衝突の発生を最小限に押さえて効率
的にケーブル３２に沿う直列通信を行えるようにするも
のである。ここで説明している実施例においては、本発
明はシールドされたより線対ケーブル３２を介して１秒
間当り約230Ｋビットで動作し、EIA規格RS-422平衡電圧
仕様に従ってドライブされる。

次に第２図を参照する。典型的な持続時間が4.34マイク
ロ秒である各ビットセルがそれの端部において状態を変
えるように、FM-0として知られているセルフクロッキン
グ技術（双位相スペース）を用いてケーブル３２におい
て符号化されて送信され、それにより受信器へ必要なタ
イミング情報を与える。図示のように、各4.34マイクロ
秒のセルに対して２つの零交差が検出されるように、中
間セルに付加零交差遷移を加えることにより零が符号化
される。同様に、論理１が、それの端部のみにおける零
交差遷移により特定のセルへ与えられる。したがって、
FM-0符号化を使用することにより、クロッキング情報が
データ信号自体により運ばれ、本発明が同期モードで動
作できるようにする。

次に第３図を参照する。本発明は「フレーム」として知
られているデータ伝送の基本単位を利用する。フレーム
３６は、２個またはそれ以上の同期（「フラッグ」）バ
イト３８，４０より成るプリアンブルを含む。ここで説
明している実施例においては、各同期バイトはビット01
111110を含む。知られているように、同期バイト３８，
４０は、ケーブル３２に結合されている受信データ処理
装置がそれの受信回路を同期することおよび（FM-0符号
化を用いて）必要なクロック情報を受けることを許す。
同期バイト３８，４０の後に８ビットの宛先アドレス(D
ST・ADD)４１が続く。その宛先アドレスは、このフレー
ムが意図するデータ処理エージェントのアドレスを指定
する。ソースアドレス(SRC・ADD)４２が、情報のフレー
ムを送るエージェントの８ビットアドレスを含む。種々
の符号を用いることにより送られるフレームの種類を指
定するために「種類」フレーム４５が設けられる。たと
えば、種類フレーム４５は確認応答(ACK)フレームと、
質問(ENQ)フレームと、RTSフレームと、CTSフレームと
を指定できる。これについては後で詳しく説明する。種
類フレームの後にマルチバイト・データフレーム（零長
であり得る）が続く。そのマルチバイト・データフレー
ムはケーブル３２に結合されているエージェントの間で
送るべき生データ、メッセージ等を含む。データフレー
ム４８の後に１６ビットのフレーム検査シーケンス５０
が続く。そのフレーム検査シーケンスはソースアドレ
ス、宛先アドレス、種類フレームおよびデータフレーム
の内容の関数である。ここで説明している実施例におい
ては、フレーム検査シーケンス(FCS)は標準CRC-CCITT多
項式(polynominal)を用いて定められる。フレーム検査
シーケンス５０の後に８ビット同期（「フラッグ」）ト
レイラー５２（論理ビット01111110より成る）と、アボ
ート(abort)・シーケンス５３が続く。そのアボート・
シーケンスは行に並べられた１１個またはそれ以上の１
より成る。アボート・シーケンス５３は、ケーブル３２
に結合されているエージェントへのフレーム３６の終り
を描写するために使用される。後で説明するように、制
御フレームのハンドシェイキング・シーケンスを用いて
直列同期のやり方でケーブル３２に沿ってフレーム３６
が送られる。制御フレームの後に第３図に示されている
データフレーム３６が続く。

第４図に示すように、あるフレームの送信前に、ケーブ
ル３２に結合されている送信エージェントが同期パルス
５６を送る。この同期パルスの後に２ビット時間より長
く、１０ビット時間より短い遊び期間が続く。同期パル
ス５６は零交差を含む任意の信号を含むことができる。
ここで説明している実施例においては、第１０図に示さ
れているように、ケーブル３２に結合されている各エー
ジェントはザイログ(Zilog)Z8530 SCC直列通信制御チッ
プ７９を利用し、ラインドライバ８０とライン受信器８
２を介してケーブル３２をアクセスする。（ザイログ・
テクニカル・マニュアル(Zilog Technical Manual)Z803
0/Z8530 SCC直列通信制御器(Z8030/Z8530 SCC Serial C
ommunication Controller)1983年1月参照。）Z8530 SCC
装置７９は、「ハント(hunt)」モードにある時に同期
（フラッグ）ビットを探索する回路を含む。前記したよ
うに、本発明はビット状態01111110を有する同期（フラ
ッグ）バイトを利用する。また、直列通信制御器は失わ
れたクロック・サイクルを検出する性能と、与えられた
零交差の後に、入来信号Ｒ_ＸＤの引き続く零交差なし
に、予め定められている時間（１ビット時間より長い）
が経過したとすると、失われたクロックビットを装置内
にセットする性能を有する。

ケーブル３２に結合されている送信エージェントにより
与えられる同期パルス５６は、全ての受信エージェント
によりクロックとしてとられる。しかし、その同期パル
スの後に２ビット時間より長い遊び時間が続くから、ク
ロックの抜けが検出され、そのクロックの抜けビット
は、ケーブル３２に結合されている各エージェートのSC
C装置７９内にセットされることにより、ケーブル３２
が使用中であることをエージェントに知らせる。ここで
説明している実施例においては、ラインドライバ８０を
少くとも１ビット時間の間一時的に可能状態にすること
により同期パルス５６は得られる。これにより、パルス
持続時間中、信号Ｔ_ＸＤをケーブル３２へ送信させて、
同期パルス５６中に少くとも１つの零交差を確保する。
また、同期（フラッグ）ビット（すなわち、３８と４
０）が検出されると、Z8530装置中の「ハント」ビット
がクリヤされ、フレームの送信前にケーブル３２が現在
使用中であるか否かをケーブル３２に結合されている各
エージェントが一層効果的に検出できるようにするとと
もに、受信エージェントが入来データフレームに対して
自身をクロックすることを許すために必要な同期ビット
を与える。失われたクロックパルスと同期バイトを検出
するために本発明はZ8530 SCC装置を現在使用している
が、別の回路を同じ機能のために同様に使用できること
がわかるであろう。

ケーブル３２に結合されている各エージェントはケーブ
ルに沿う独特の２進アドレスにより識別される。本発明
の１つの特徴は、ケーブル３２に結合されているエージ
ェントが予め定められている永久アドレスを必要としな
いことである。したがって、たとえば装置２７をケーブ
ル３２から切離し、それから、アドレスを構成する必要
なしにその装置２７を別の場所の別のケーブルに再び結
合できる。ケーブル３２にあるエージェントが新に結合
されると、あるアドレスがダイナミックに発生されて、
エージェント自身により割当てられるように独特のプロ
トコルが続く。ここで説明している実施例においては、
各エージェントのアドレスは８ビット識別子（エージェ
ントが零アドレスまたはアドレス２５５を有しない場
合）を用いて識別される。

ここで第６図を少し参照する。この図には、アドレスを
決定して、自身にそのアドレスを割当てるためにエージ
ェントが利用する動作シーケンスが示されている。サー
ビスの途絶を阻止するためには、既に機能しているエー
ジェントと同じアドレスを得ることができるエージェン
トはないことが明らかである。実際には、エージェント
のアドレスは、全体的なデータ処理装置と、メインフレ
ームその他のマシンを備えることができる「サーバー(s
erver)」の間で割当てることができる。ここで説明して
いる実施例においては、アドレス１〜127が汎用エージ
ェントに割当てられ、アドレス128〜254がサーバーによ
る使用のために割当てられる。第６図に示すように、ケ
ーブル３２に結合された時に各エージェントは、予め定
められている範囲内の任意の乱数を発生し、またはある
長期間持久するメモリ（たとえば読出し専用メモリまた
は磁気媒体）から「ヒント(hint)」と呼ばれるスタート
数を得る。その乱数（または「ヒント」）は「仮り」の
アドサスとして取扱われ、それからエージェントは質問
(ENQ)フレームを送る。その質問フレームは仮りのアド
レスを宛先アドレスとして利用する。送られる質問フレ
ームは第５図に示されているような態様のものであっ
て、第３図を参照して先に述べた同期（フラッグ）バイ
ト３８，４０に対して少なくとも２ビット時間だけ分離
・先行したパルス５６を含む。第５図の宛先アドサス４
１とソースアドレス４２は、ランダムに発生された、ま
たはヒントを介して発生された仮りのアドレスを含む。
第５図の種類フレーム４５は、第５図のフレームをアド
レス割当てのために使用するための「質問」(ENQ)フレ
ームとして識別する２進符号を含むことに注意された
い。そのENQフレームはケーブル３２を介して送られ
る。別のエージェントが仮りのアドレスを既に割当てら
れているものとすると、そのエージェントはENQフレー
ムを受け、それに応答して確認応答(ACK)フレームを送
信エージェントへ送り返えす。実際には、バケットをAC
Kとして識別する２進符号を種類バイトが含んでいるこ
とを除き、ACKフレームは第５図に示されているENQフレ
ームと同様に構成される。

第６図に示すようにACKフレームが送信エージェントに
より受けられると、そのエージェントは別の乱数を仮り
のアドレスとして発生せねばならず、その新しい仮りの
アドレスのケーブル３２に沿う送信を繰り返えす。ACK
フレームが受信されない時は、ケーブルに新に結合され
たエージェントは、ある予め定められている最大数の試
行が行われるまで、ENQフレームのケーブルへの送り出
しを続ける。ある予め定められた回数の試行数もACKフ
レームが受信されないとすると、送信エージェントはそ
の仮りのアドレスを、ケーブル３２に沿う将来の全ての
通信に対するそれの最後のアドレスとして割当てる。EN
Qフレームの反復送信は、その仮りのアドレスを使用で
きる特定のエージェントが現在ビジー状態であり、した
がって質問の受信をし損じるという場合を避けるために
用いられる。

エージェントは、（仮でない確定した）アドレスを割り
当てられると、ケーブル３２に結合されている他のエー
ジェントと、以下に説明するハンドシェイキング・プロ
トコルおよび衝突回避機構を用いて通信できる。次に第
７図，第８ａ図，第８ｂ図，第９図を参照する。ケーブ
ル３２に結合されているエージェントの間の通信は、第
１の待機期間（フロントエンド待機オペレーション），
付加の待機期間，第２の待機期間を含む三段階ハンドシ
ェイキング法により行われる。このハンドシェイキング
・シーケンスの目的は、衝突発生の確率の低下を狙った
秩序正しいやり方で共用ケーブル３２に対してのアクセ
スの制御をすることである。ハンドシェイキングを伴う
送信（「ダイアログ(dialogue)」として知られてい
る。）相互間は最短のダイアログ間隔（ＩＤＧすなわち
Inter-Dialogue-Gap）だけ分離されていなければならな
い。以下に説明する実施例ではＩＤＧは４００マイクロ
秒である。また、１つの送信（ダイアログ）内でのフレ
ーム相互の間隔は、所定の最長のフレーム間隔（ＩＦＧ
すなわちInterframe Gap）内でなければならない。ここ
ではＩＦＧは２００マイクロ秒である。２つ以上のエー
ジェントが同時にケーブル３２に送信すれば衝突が発生
する。

第７図，第８ａ図，第８ｂ図を参照して、ケーブルに結
合されている他のエージェント（受信のデータ処理装
置）との通信を望む送信エージェント（送信のデータ処
理装置）、例えばデータ処理装置２５は、第８ａ図，第
８ｂ図に示されているオペレーションを実行する。送信
エージェントは、まず、Ｚ８５３０ＳＣＣのような適切
なハードウエア内の「ハント」ビットにより、ケーブル
３２上に同期（フラッグ）バイトのような同期信号が検
出されるか否かを判定する。同期（フラッグ）バイトが
検出され、それにアボート・バイトが続かなければ、ケ
ーブル３２は現在使用されており、送信エージェントは
送信の「延期「ディファー）」をする。同期パルス５６
または同期（フラッグ）バイト（３８，４０）が検出さ
れなければ、送信を望んでいる送信エージェントは、第
８ａ図に特に示されるフロントエンド待機オペレーショ
ンを実行する。フロントエンド待機オペレーションは、
一連の４つの単位待機期間より成る第１の待機期間を与
える。ここで説明している実施例では、単位待機期間の
長さは１００マイクロ秒であって、各単位待機期間の経
過後に、同期（フラッグ）バイトがケーブル３２に与え
られたか否かを調べるために、フラッグ検出ビット（ハ
ントビット）が調べられる。同期（フラッグ）バイトが
検出されていれば、それは他のエージェントによりケー
ブル３２が使用されていることを示すものである。その
場合には、送信エージェントは、フラッグ検出ビット
（ハントビット）のクリアを待たなければならない。ク
リアによりケーブル３２の使用が終了したことが示され
ていれば、第８ａ図，第８ｂ図に示される全フロントエ
ンド待機シーケンスが繰り返される。

一方、フロントエンド待機オペレーション中に同期（フ
ラッグ）バイトが検出されないことは、フロントエンド
待機中すなわち第１の待機期間中に、ケーブル３２を使
用しようとした他のエージェントが無いことを示すか
ら、付加の待機期間すなわちランダムな待機動作が実行
される。なお、フロントエンド待機オペレーション中、
最初の１００マイクロ秒の待機の経過後に同期パルス検
出がクリアされる。

ランダムな付加的待機動作には、先ず、ランダムな待機
数すなわち送出したいデータに関する衝突および延期の
履歴に応じた乱数Ｒが発生される（Ｒの発生については
後で説明する。）。図示のように、乱数Ｒに対応してい
るランダムな付加の待機期間では、１００マイクロ秒の
ベースの待機期間が経過してから、フラッグが検出され
たか否か（ハントビットはクリア済み）を調べる。任意
の時点でフラッグが検出されたとすると、他のエージェ
ントによりケーブル３２が使用されているのであるか
ら、送信のエージェントは「送信延期」をしなければな
らない。しかし、ランダムな付加待機期間の経過後に、
ケーブルがなお使用されていなければ、同期パルスが検
出されたかどうかを調べるための最終的な検査を行い、
それからＲＴＳフレームを送る。

乱数Ｒに対応している付加待機期間中ずっとケーブル３
２が遊び状態のままであるとすると、送信のエージェン
トは、同期パルス５６の送信に移り、それに続いて「Ｒ
ＴＳ」フレームがケーブル３２を介して受信のエージェ
ントへ送られる。ＲＴＳフレームは第５図に示されてい
るＥＮＱフレームとほぼ同様に構成されるが、種類フレ
ームは、（ＥＮＱではなく）ＲＴＳフレームとして識別
する２進符号を含む。受信エージェントは、送信エージ
ェントからＲＴＳフレームを受けると、最長フレーム間
間隔（ＩＦＧ）時間内に「ＣＴＳ」フレームを当該送信
エージェントへ送り返す。ＲＴＳフレームの場合におけ
るように、受信エージェントにより送られるＣＴＳフレ
ームは、種類フレームにＣＴＳフレームとして識別する
ための符号が含まれることを除き、第５図図示のＥＮＱ
フレームの構造と同様である。当該送信エージェントた
とえばデータ処理装置２５は、返送されたＣＴＳフレー
ムを受けると、第３図に示されているフル・データフレ
ーム３６を、ＣＴＳフレーム受信時点からＩＦＧ時間以
内に受信エージェントへ送る。ＩＦＧ時間中に、ＣＴＳ
フレームの返送が行われなかったり、データフレーム３
６の送信が行われなかったりすると、それは、衝突が起
きたこと、ないし宛先の受信のエージェントが使用可能
な状態にないことを示すものとして、送信のエージェン
トは想定する。

ケーブル３２に結合されている全てのエージェントに対
しての全体放送を行う場合には、送信のエージェントは
２５５なる宛先アドレスを有するＲＴＳフレームを全エ
ージェントへ送り、ＩＦＧ時間の経過を待ってから、２
５５なる宛先アドレスを有するデータフレーム３６を送
信する。ケーブル３２に沿う全体放送の場合には、送信
エージェントはＣＴＳフレームの戻りを待たずに、ＩＦ
Ｇ時間が経過すると直ちに全体放送を実行する。ここ
で、放送専用のアドレスを示す特定の数（上記の２５
５）を宛先アドレス４１として設定することにより、ケ
ーブル３２に沿った全てのエージェントに対してただ１
つのＲＴＳフレームを送ることが必要とされるだけであ
る。

以上に説明した三段階ハンドシェイキング・プロトコル
の目的は、衝突が生じないであろうところの期間（特に
ＲＴＳフレームとＣＴＳフレームとの交換の期間）を見
いだすことにより衝突を回避するものであり、そして、
送信の開始前でケーブルの遊び状態を待っている複数の
送信エージェントがケーブル・アクセスを行う時点の分
散を合理的に図るものであることが、当業者にはわかる
であろう。ＲＴＳフレームとＣＴＳフレームの交換の成
功は衝突が生じなかったことを意味し、それらのフレー
ムの送信は、送信を望んでいる他の送信エージェントに
より検出され、従って、他の送信のエージェントは、デ
ータ交換の完了を待ってから（衝突を避けるようにし
て）ケーブルのアクセスのための動作を始めることにな
る。

ＲＴＳフレームとＣＴＳフレームの交換中に、万一、他
の送信のエージェントが送信を開始したとすると、ＣＴ
Ｓフレームは適切に受信されない（たとえばフレーム検
査シーケンスが無効となる）から、衝突が起きたこと
を、上記のＲＴＳフレームを送信したエージェントは想
定できる。衝突によりＲＴＳフレームとＣＴＳフレーム
の完全な交換が阻止され、それにより正しいハンドシェ
イキングの達成が阻止される。しかし、常軌の場合に
は、データをケーブル３２へ送信することを望んでいる
エージェントは、ケーブル３２が使用中であることを検
出すると、ケーブル３２が遊び状態になるまでＲＴＳフ
レームの送信を延期する（第１１図，第12図参照）。従
って衝突の発生は最小にされる。

次に第９図，第１３ａ図および第１３ｂ図を参照して、
ランダムな待機数すなわち（第８ａ図および第８ｂ図を
参照して説明した）乱数Ｒの値を得るために本発明によ
り実行されるオペレーション・シーケンスについて説明
する。本発明は、ランダムな待機数すなわち乱数Ｒを、
最近のケーブルトラヒック履歴に応じて動的に修正する
ものであることがわかるであろう。本発明の実施例で利
用される方法は、最近に送信されたデータフレームに関
して衝突が生じたとされていれば、ケーブル３２に大き
な負荷が現在かかっていて高いバス競合状態にあるとい
う想定に立つものである。そして、乱数Ｒは、ケーブル
の使用に関して競合している諸エージェントがバスへア
クセスする時点を分散させる。したがって、第１３ａ図
および第１３ｂ図に示されているオペレーションが実行
されて、第８ａ図および第８ｂ図を参照して説明したオ
ペレーション・シーケンスに従って利用されるランダム
な待機数Ｒを調整する。本発明においては、衝突と、各
エージェントについての延期履歴を見失しなわないよう
にするために、シフトレジスタが設けられる。説明のた
めに、変数「C」は、あるエージェントが送信することを
試みた最後の８個のデータメッセージに対する衝突履歴
を見失しなわないようにするために利用される８ビット
シフトレジスタを示し、変数「D」は、送信することを試
みられた最後の８個のメッセージに対する延期履歴を表
す８ビットシフトレジスタを示す。前記したように、RT
S−CTSフレーム・ハンドシェイキング・プロトコルがIF
G期間中に起こることが失敗したとすると衝突が起きた
と仮定され、エージェントがメッセージの送信の前にフ
ラッグバイトすなわち同期パルス５６を検出したとする
と、延期が起きたとみなされ、ケーブルが使用中である
ことを示す。変数「G」は、エージェントが送信しようと
試みた以前の全てのメッセージを表す修正係数を示す数
を表す４ビットの包括的マスクとして定義される。変数
「L」は、ケーブル３２に結合されているエージェントに
よる現在のメッセージを送信する試みを表す局部的なマ
スクとして定義される。また、Ｎ_Ｃは特定のデータパケ
ットに対して仮定された衝突の回数として定義され、Ｎ
_Ｄは現在のデータパケットの送信前に行った延期の回数
として定義される。

第１３ａ図および第１３ｂ図に最もよく示されているよ
うに、新しいデータパケットの送信前には、変数Ｇが下
記のようにして調整される。

８ビットレジスタ「C」にセットされたビット数（すなわ
ち、１に等しい）が２より大きいと、変数「G」を定める
４ビットシフトレジスタ中の全てのビットが左（最下位
ビット(LSB)から最上位ビット(MSB)へ向かって）へ１ビ
ットだけ桁送りされる。また、Ｇ_０（４ビットシフトレ
ジスタＧの最下位ビット）が１にセットされ、変数Ｃを
構成する８ビットが０にセットされる。

８ビットシフトレジスタ「C」にセットされたビットの数
が２より小さいか、２に等しいとすると、Ｄが調べら
れ、「シフトレジスタ「D」にセットされたビットの数が
２より小さいと、本発明はシフトレジスタの内容を右へ
（MSBからLSBへ向かって）桁送りし、Ｇ_３（ＧのMSB)を
０にセットし、Ｄの値を２５５に等しくセットする。

Ｇがひとたび調整されると、本発明はシフトレジスタＤ
とＣの内容を左へ(MSBへ向かって）桁送りさせ、ＣとＤ
の最下位ビット(LSB)を０に等しくセットする。同様
に、送るべき特定のメッセージに対する衝突回数を示す
変数Ｎ_Ｃと、延期回数を示す変数Ｎ_Ｄも０に等しくセッ
トされる。更に、第１３ａ図および第１３ｂ図に示すよ
うに、Ｌの値がＧの値に等しくセットされる。

第８ａ図に示されているフロントエンド待機シーケンス
を開始する前に、フラッグ検出（すなわち、フラッグバ
イト）がケーブル３２に沿って検出されたか否かを本発
明は判定する。フラッグバイトが検出されなかった場合
には、フロントエンド待機期間のために、本発明は第８
ａ図に示されているオペレーション・シーケンスを実行
する。固定フロントエンド待機シーケンスに続く所定の
範囲内に本発明は乱数「r」を発生し、それからｒの値を
Ｌ（局部的マスク変数）の以前に決定された値との論理
積をとることにより「R」の値を計算する。Ｒの値が決定
されると、本発明は、第８ｂ図に示されているランダム
な待機サイクルに追従して、ランダムな待機期間が終る
と、第１３ｂ図に示すようにRTSフレームを送信する。

前記IFG期間中にＣＴＳフレームが送信エージェントに
より受けられると、データフレームが送信されて、メッ
セージ・ダイアログが完了させられる。一方、フロント
エンド待機シーケンスの前にフラッグが検出されたとす
ると、延期調整が行われ、Ｄ_０（レジスタＤのLSB）が
１にセットされ、Ｌ_０が１にセットされる。また、延期
調整は、Ｎ_ＤをＮ_Ｄ＋１に等しくセットすることを含
む。フラッグ検出（ハントビット）が再度検査される。
第１３ａ図および第１３ｂ図に示されているように、送
信前にラインがビジーであることが判定された場合にそ
の延期調整が行われる。

RTS/CTSのハンドシェイキングが成功しない場合には、
衝突が起きたと仮定されて、衝突し調整が行われる。Ｃ
_０が１に等しくセットされ、Ｌの値が左（LSBからMSB）
へ１ビット桁送りされる。また、第１３ｂ図に示すよう
に、Ｌ_０は１に等しくセットされ、Ｎ_ＣがＮ_Ｃ＋１に等
しくセットされる。

第１３ａ図および第１３ｂ図に示されているステップを
利用することにより、送信を試みるまでに待つフロント
エンドに加えてエージェントが待つ時間（１００マイク
ロ秒増分）が最近のケーブルトラヒック履歴に従って修
正されるように、ランダムに発生されたｒの値が動的に
調整される。ランダムな待機期間のこの修正は、RTS/CT
Sフレーム交換が成功する確率を大幅に高くし、それに
よりケーブル３２に沿う衝突を回避する。

以上、ローカル・エリア・ネットワークに関連して使用
した場合にとくに有用である装置と方法について説明し
た。本発明は、ケーブルの任意の点に任意のエージェン
トを結合できるようにし、かつそのエージェントに独特
のアドレスを割当てるネットワークを提供するものであ
る。また、本発明の新規な衝突回避プロトコルはケーブ
ル上で起こる衝突の確率を最低にし、衝突が起きた場合
も、以後の再送信が成功する確率を高くするものであ
る。

【図面の簡単な説明】

第１図は本発明を利用するようにされたローカル・エリ
ア・ネットワークを示す線図、第２図は周波数変調(FM-
0)符号化に本発明を使用した様子を示すタイミング波形
図、第３図はローカル・エリア・ネットワークに結合さ
れている種々のデータ処理装置へデータを転送するため
に本発明により利用されるフレーム書式を示す線図、第
４図はフレームの送信前における同期パルスの本発明の
使用を示す線図、第５図はダイナミック・アドレス割当
中に本発明により利用される質問(ENQ)フレームの線
図、第６図はダイナミック・アドレス割当中に本発明の
装置に結合されたデータ処理装置により利用されるオペ
レーションのシーケンスを示す流れ図、第７図はデータ
フレームの送信の前に送信データ処理装置と受信データ
処理装置の間のハンドシェイキング信号の本発明の使用
を示す線図、第８ａ図および第８ｂ図はケーブルのアク
セスを行うために送信装置のオペレーションのシーケン
スを示す流れ図、第９図は遊びケーブルを検出した後の
送信装置による「RTS」フレームの送信を示す線図、第１
０図はローカル・エリア・ネットワークに結合された直
列制御器の本発明への使用を示すブロック図、第１１図
は延期を含む本発明の衝突回避方法を示す線図、第12図
は２つのRTS信号がローカル・エリア・ネットワークに
沿って衝突している状況を示す本発明の衝突および解決
機構を示す線図、第１３ａ図および第１３ｂ図はランダ
ムな待機期間の発生を示す流れ図である。２５〜２８・・・・データ処理装置、３０・・・・プリ
ンタ、３２・・・・ケーブル、７９・・・・直列通信制
御チップ、８０・・・・ラインドライバ、８２・・・ラ
イン受信器。

───────────────────────────────────────────────────── フロントページの続き (72)発明者アラン・ビイ・オツペンハイマーアメリカ合衆国 95014 カリフオルニア州・カツパチーノ・グレンビユアヴエニユウ・10461 (72)発明者ガーシヤラン・エス・シドウアメリカ合衆国 94025 カリフオルニア州・メンロパーク・スタンフオードアヴエニユウ・811

Claims

【特許請求の範囲】

【請求項１】送出のデータ処理装置から、受信のデータ
処理装置へと、それらを含めて複数のデータ処理装置が
結合されている通信媒体を介して、データを転送する方
法において： (A)送出のデータ処理装置が、通信媒体上に他のデータ
処理装置からのデータが存在しているか否かを、通信媒
体上の同期信号の検出によって決定する過程と； (B)送出のデータ処理装置が、通信媒体上に同期信号を
送出したときは、受信のデータ処理装置への通信媒体を
介したデータ転送を延期し、過程(A)へ戻り； (C)送出のデータ処理装置が、通信媒体上に同期信号を
検出しないときは、第１の所定期間待機し、その第１の
所定期間中も通信媒体上の同期信号の検出を行う、第１
の待機・検出の過程と； (D)送出のデータ処理装置が、第１の所定期間中に、通
信媒体上に同期信号を検出したときは、過程(C)を繰り
返し、 (E)送出のデータ処理装置が、第１の所定期間中に、通
信媒体上に同期信号を検出しないときは、次の乱数Ｒに
対応した付加待機期間の経過、すなわち、送出のデータ
処理装置において、(1)所定の範囲内で且つ(2)送出のデ
ータ処理装置についての送出したいデータに関する衝突
および延期の履歴に応じて発生される乱数Ｒに対応した
付加待機期間の経過を持ち、その付加待機期間中も通信
媒体上の同期信号の検出を行う、付加待機・検出の過程
と； (F)送出のデータ処理装置が、付加待機期間中に、通信
媒体上に同期信号を検出したときは、前記乱数Ｒの調整
用動作を行い且つ過程(B)へ戻り、 (G)送出のデータ処理装置が、付加待機期間中に、通信
媒体上に同期信号を検出しないときは、次の動作を生じ
させる第１の信号、すなわち、受信のデータ処理装置に
よりその第１の信号が受信されると受信のデータ処理装
置から送信のデータ処理装置へ通信媒体を介して第２の
信号を返送する動作を生じさせる第１の信号を、受信の
データ処理装置へ通信媒体を介して送出する過程と； (H)送出のデータ処理装置が、受信のデータ処理装置へ
の第１の信号の送出から始まる第２の所定期間にわたっ
て、受信のデータ処理装置から返送される第２の信号を
受信するために待機し、もし第２の所定期間内に第２の
信号が受信されなければ衝突の発生と判断するための過
程と； (I)送出のデータ処理装置が、第２の所定期間内に受信
のデータ処理装置からの第２の信号を受けたときは、そ
の受けた時点から始まる第３の所定期間内に、受信のデ
ータ処理装置へ通信媒体を介してデータを転送する過程
と； (J)送出のデータ処理装置が、第２の所定期間内に受信
のデータ処理装置からの第２の信号を受けず、従って衝
突の発生と判断されるときは、前記乱数Ｒの調整用動作
を行い且つ過程(C)へ戻る過程とを備え、衝突の発生の最小化することを特徴とするデー
タの転送方法。（２）特許請求の範囲第１項記載の方法において、乱数
Ｒは、式Ｒ＝ｒΛＬ（ここで、ｒは所定の範囲内の乱数を示し；Λは論理積
操作を示し；Ｌは、ローカル変数であって、送出のデー
タ処理装置についての送出したいデータに関する衝突お
よび延期の履歴を表すもので、(1)当初は、送出のデー
タ処理装置についてのそれまでに転送された全てのデー
タに関する衝突および延期の履歴を表す包括的マスク変
数Ｇに等しく設定され、(2)その後は、それまでのデー
タの転送試行において衝突とされた回数Ｃおよび延期さ
れた回数Ｄに関して調整されるものであり、そして包括
的マスク変数Ｇはデータの転送前に調整される。）により計算されるものであることを特徴とするデータの
転送方法。（３）特許請求の範囲第２項記載の方法において、包括
的マスク変数Ｇは４ビットから成り、それまでのデータ
の転送試行において衝突とされた回数Ｃおよび延期され
た回数Ｄ関して、 (1)変数Ｃ中の１に等しいビットの数が２より大きい場
合に、 (a)変数Ｇの各ビットを、上位桁(MSB)の方へと１ビット
桁送りし、 (b)変数Ｇの最下位ビット(LSB)を、１にセットし、 (c)変数Ｃの全てのビットを、０にセットし； (2)変数Ｃ中の１に等しいビットの数が２より小さく、
変数Ｄ中の１に等しいビット数が２より小さい場合に、 (d)変数Ｇの各ビットを、下位桁(LSB)の方へと１ビット
桁送りし、 (e)変数Ｇの最上位ビット(MSB)を、０にセットし、 (f)変数Ｄを、２５５にセットすることを特徴とするデータの転送方法。（４）特許請求の範囲第３項記載の方法において、 (i)）変数Ｃ中の各ビットを、上位桁(MSB)の方へと１ビ
ット桁送りし、 (ii)変数Ｄ中の各ビットを、上位桁(MSB)の方へと１ビ
ット桁送りし、 (iii)変数Ｃの最下位ビット(LSB)を、０にセットし、 (iv)変数Ｄの最下位ビット(LSB)を、０にセットする過程を含むことを特徴とするデータの転送方法。（５）特許請求の範囲第３項記載の方法において、前記
過程(J)における乱数Ｒの調整用動作は、 (i)）変数Ｃ中の最下位ビット(LSB)を、１にセットし、 (ii)変数Ｌ中の各ビットを、上位桁(MSB)の方へと１ビ
ット桁送りし、 (iii)変数Ｌ中の最下位ビット(LSB)を、１にセットし、 (iv)変数Ｃに１を加える過程を含むことを特徴とするデータの転送方法。（６）特許請求の範囲第３項記載の方法において、前記
過程(B)は、乱数Ｒの調整用動作の過程を含むことを特
徴とするデータの転送方法。（７）特許請求の範囲第６項記載の方法において、前記
過程(B)および(F)における乱数Ｒの調整用動作は、 (i)変数Ｄの最下位ビット(LSB)を、１にセットし、 (ii)変数Ｌの最下位ビット(LSB)を、１にセットし、 (iii)変数Ｄに１を加える過程を含むことを特徴とするデータの転送方法。（８）特許請求の範囲第１項記載の方法において、同期
信号は、同期パルスおよびこの同期パルスに続くフラッ
グ信号を含み、第１の信号および第２の信号それぞれ
は、他の信号に先行する同期信号を含むことを特徴とす
るデータの転送方法。