JPS5941079A - シリアルバスのためのデユアルカウント，ラウンドロビン分布裁定技術 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は、一般的にはディジタルデータ処理システムの
分野に係るものである。特定的には、本発明はこのよう
なシステム内、回路網内の各種ユニットの相互接続、及
びこれらのユニットの間の情報転送の制御に係るもので
ある。更に精密に言えば、本発明は回路網内のユニット
が紛争裁定型シリアルパスによって相互接続されている
ようなディジタルデータ処理回路網と、バスに接続され
ている各糧ユニット或はデバイスによってバスへのアク
セスを制御することに係るものである。

ディジタルデータ処理システムは、少なくとも、メモリ
要素、人力・出力要素及びプロセッサ要素からなってお
り、またそれらの何れか或は全てを複数含んでいてよい
。メモリ要素は情報をアドレス可能な記憶位置に記憶す
る。この情報は命令及び返答を含むデータを処理するた
めのデータ及び指令を含んでいる。プロセッサ要素はメ
モリ要素へ及びメモリ要素から情報を転送し、到来情報
をデータ或は命令の何れかとして解読し、そしてこれら
の命令に従ってデータを処理する。入力・出力要素もメ
モリ要素（単拳複）と通信して入力データをシステムへ
及びシステムから転送し、システムからデータを得て処
理する・ 多年に亘って多くの異なる型のディジタルデータ処理シ
ステムが開発されて来た。近年に力って、開発の中に、
異なる位置に配備されることが多い多数のメモリ要素、
入力・出力要素及びプロセッサ要素が互に通信できるよ
うなコンピュータ回路網が含まれるようになった。利用
可能な種々の情報転送方式の型に一般的に要求されるこ
とは、各種要素を相互接続している分割通信資源（即ち
チャンネル或はパス）の使用である。通信資源をこのよ
うに分割すると、通信資源へのアクセスを制御するため
の手順によっては回路網の効率及び利用が大きく影響を
受けることになる。転送が行なわれていない間の待時間
及びオーバーヘッド動作に費やされる他の時間は動作効
率を低下させるものである。

一般に、通信パスを介する２つのユニット間の伝送は、
１つ以上のユニットがこのような接続を生じさせる能力
を有しているために、２つの段階を必要とする。第１段
階はおる程度限定されている間隔の間開始ユニットにパ
スの制御を得るようにするためのものである。一旦この
選択段階が完了すると、選択された開始ユニットによっ
て制御される転送を完了させるために第２（即ち転送）
段階が用いられる。

パスの制御を得るには、パスにアクセスを望んでいる他
のユニットとどちらが週ばれるのかを争い、裁定を受け
そして決定する必要がある。裁定には２つの主な一般的
アプローチがある。これらは中央裁定と分布裁定でおる
。中央裁定では、厘−の中央優先順位回路が全てのパス
アクセス要求を受け、与えられた時点においてどの要求
ユニットに最優先順位を力えてパスの使用を許容するの
かを決定する。一旦ユニットが這択されると、そのユニ
ットはパスを制御して転送を行なうことが許される。こ
れに対して、分布裁定では、パスに接続されている各ユ
ニットには特定の優先膜付が割当てられており、各ユニ
ットはパスを制御することを望む時にパスの制御を得る
のに充分な優先順位を有しているか否かを個々に決定す
る。もし優先順位の高いユニットが同時にパスアクセス
を得ようと努めていれば、優先順位の低いデバイスはそ
れが最高の優先順位要求者となる後刻まで待友なければ
ならない。

米国特許４，２２９，７９１号（１９ａｇ年１０月２１
日付）「データ処理システム用分布裁定回路」に記載さ
れているこのような一方式によれば、例えばパスには裁
定導体を設けてるる。各ユニットは情報交換を行なおう
としているのであるから、この導体に要求信号を送信し
ている筈で、ユニットはその要求レベルと他の全ての要
求とを比較し、高い優先順位レベルの要求が存在してい
なければそのパスの制御を詐可する。

しかし、パスが単一のビット・シリアルラインからなっ
ている場合にけ、別個の裁定導体がないのであるから、
上記システムは作動できない。これらのシステムに採用
されて来た°１つのアプローチは衝突検出を伴なう搬送
波検知多重アクセス（Ｃ３Ｍ＾／ＣＤ）と呼はれるもの
である。

ＣＳ　Ｍ＾／ＣＤ回ＰＲ網では、回路網に接続されてｈ
る各デバイス即ちユニットは、パス（一般的には同軸ケ
ーブルでちる）への自らのアクセスを制御する。パスを
使用する各デｔ４イスは、チャンネル上へ信号を送信す
る装置並びに別のデ／４イスのインターフェイスによっ
てチャンネル上に印加された信号を受信する訣愕を含む
インターフェイスを介してケーブルにＨＢＨされる。各
インターフェイスは、チャンネルを監視して２つのデバ
イスが同時に送信中であればそれを指示する回路を含ん
でいる。送信中のデバイスが、別のデバイスが同時に送
信していることを検出すると、２つのデバイスは送信を
停止し、それらの関連情報源（送信すべき情報を供給中
でめも）に対して送信を停止することｆ、通知する。両
デバイスは、チャンネルがクリアになってから送信を再
び試みる。

チャンネルの使用（即ち送信）を望む各デバイスは、先
ず他の何れかのユニットが送信中で＃−Ｊ：ないかを「
＠守」する。もし他の送信が検出されなければ、ステー
シコン（即ちユニット）はその送信を開始し、同時にチ
ャンネルの「聰守」も開始する。もし別のステーション
が同時に送信を開始したことを検出すれば、両ステーシ
ョンは衝突を検出するので、前述のように送信を停止す
る。衝突が繰返されるのを避けるために１各ステーシコ
ンは暫時待機し、再び試みる。再送信の前の間隔を制御
するために、各ユニットに独特の或は適当な無作為遅延
を割当てる種々のアプローチが知られている。このよう
なシステムは、例えば１９７７年１２月１３日付米国特
許４，０６３，２２０号に示されている。（因みに、Ｃ
３Ｍ＾／ＣＤ回路網に関係して米国で本願と同時出願さ
れたものの一連番号と名称を列挙しておく。

米国特許用Ｗ４２６７．５９４号［搬送波検知多重アク
セス／衝突検出を用いたローカル回路網用送受信機」。

米国特許出願２９２，００３号［搬送波検知多重アクセ
ス／衝突検出を用いたローカル回路網用送受ｑ４機にお
ける衝突検出回路の試験装置」。

米国特許出ＮＭ２９２，００４号［搬送波検知多重アク
セス／衝突検出を用いたローカルデータ回路用用送受信
機のための信頼性向上方法」米国特許出Ｍ２９２，００
５号［ローカルデータ回路網用送受信機のための雷、流
源送信機出力段」米国特許用Ｒ２９２，００６号［電流
及び参照電圧の精密設定方法Ｊ）−。

若干＾なるシステムがミネソタ州のネットワーク・シス
テムズ・コーポレーションによって開発され、また１９
８０年にプレンティス・ホール・インコーホレーデラド
から出版されたＣ、ワイツマンの醜文［分配されたマイ
クロ／ミニコンピユータシスチムニｒ１造、集施及び応
用」の５４．３１８０〜１８３ペーゾに記載されている
。このシステムでは、送（ｉ　ｆ：指示された時、アダ
プタ（即ち同軸ケーブルへのインターフェイス）はチャ
ンネルの使用ｆ：＋ｑって争う。これらのメカニズムは
紛争手順内で用いられる。第１のメカニズムは搬送波検
知である。即ち、もし同軸ケーブルが多忙であれば（即
ち信号が検出されると）、ユニットは送信を開始しない
。第２のメカニズムは、同軸ケーブルが利用可能である
こと１ＦＣ検出しｆＣ，後に、固定された時間だけ送信
を遅らせることを含んでいる。各インターフェイスは、
「ケーブルが多忙ではない」状態を検知した時点から遅
延時間が経、過するまで送ｆｆｌを阻止するハードウェ
ア遅延要素を含んでいる。これにより、受信機は再びパ
スを廻って争うことなくメツセージのＰ端の送信に迅速
に応答する時間が得られ、またケーブルにアクセスして
いるアダプタｄ一連の送信を行なうのにケーブルｆｉｌ
−使用し続けることができる。この固定された遅延は、
ケーブル長の３０Ｃｒｎ（１フイート）当り４ナノ秒で
あり、従って３００ｍ（１０００フイート）のパスでは
８マイクロ秒となる（送信の後端が全長を走行し、応答
の先端も全長を走行できるようにするために必要である
から）。第５のメカニズムは各アダプタに送信優先１に
位を割当てる。パスが多忙ではなくなり、そして固定遅
延時間が経過した後に、各アダプタはタイムパルスを発
生し、この時にパス上に送信しまたその使用のためにパ
スを捕捉することができるようになる。

固定遅延時間の終了の後にパスインターフェイスがタイ
ムパルスを発生して送信開始がｄＩ能となる時間を「ｎ
遅延」と呼ぶ。アダプタ０に対してはｎ遅延は０である
。他の全てのアダプタに対するｎ遅延は次の式によって
与えられるＯ ｎ遅延＝　（ｎ−１遅延）＋（４ナノ秒）（ノードｎ−
１とノードｎとの間の距離（フィート））もしパスが多
忙でなく２つの遅延間隔が経過したものとすれば、アダ
プタは直ちに送信を開始できる。２つのアダプタによる
ほは同時の送信によってイ藺突が発生しても再試行中に
解決され、高い優先１１１１位を有するアダプタがアク
セスを得ることになる。

各アダプタに対する１簀先１１１１’１位はネットワー
ク・システムズ・コーポレーションのアプローチでは予
め指定されているから、１つ或はそｔ１以上のノードは
、他のノードに損害を与えながら意義深い優位を占める
ことができる。実際、あるノードがどれだけ長く開放を
待たなければならないのかは、決定論的ではなく蓋然的
でしか過ぎない。これらは相当な欠陥である。

従って、本発明の目的は、バスに接続されている各ノー
ド即ちユニットがバスアクセスｆ！ｃ得るのにほぼ等し
い平均優先順位を持つようにした大きい公平さを呈する
分布裁定メカニズムを提供することである。

本発明の別の目的は、効率的で且つ再試行を最小に保つ
裁定メカニズムを提供することである。

本発明の別の目的は、信頼性の高い裁定メカニズム金提
供することである。

本発明の別の目的は、単なる統計的挙動ではなく、決定
論的挙動を呈する裁定メカニズムを提供することである
。

本発明の史に別の目的は、あるノードに、そのノードが
交互に通信できる２つ或はそれ以上のバスチャンネルと
争うことができるようにする裁定メカニズムを提供する
ことである。

本発明の別の目的は、１つ或はそれ以上の上記目的を満
足させ、実施が比較的簡単な裁定メカニズムを提供する
ことである。

上記目的を達成するために、本発明はデュアル・カウン
ト、ラウントロピン技術と呼ぶスロット型ｃ　Ｓ　Ｍ　
Ａ　／　Ｇ　ｏシステムを提供する・各ノート９毎が与
えられるように、ラウントロピン式に時々開側スイッチ
される。

ここに用いている「７−ド」とは、バスを通して通信す
るデバイスのことであり、最小限プロセッサ又はメモリ
及びバスインターフェイスを含んでいる。同じような効
果を呈するものに対して用いられる語に「デバイス」及
び「ユニット」カある。

本技術は、他のノード（他の任意の物理的位置にある）
が送信中であるのをあるノードが検知するための最大時
間であるスロット、即ち時間間隔に基づいている。

送信を望んでいるノード（以下に「開始ノード」と呼ぶ
）はバス（或はもし２つのバスが利用ｏＴ［であれば選
択された方のバス）管検査して搬送波が存在しているか
否かを（即ち別のノードが送信中であるか否かを）決定
する。バスが遊休となる（即ち）般送波存在状態から搬
送波非存在状婦への変化が観測される）と、直ち罠開始
ノードは独特な数の「沈黙」スロットを待ち始める。こ
の数はそのノードのアドレスＮに基づいている。待たれ
たスロットの数は２つの値の一方、即ちＮ＋１或はＭ十
Ｎ＋１（ここにＭはバスに接続可能なノードの最大数で
ある）を有している。この値の選択は歴史の関数であり
、即ち、他のノードによる先行送信に依存している。初
めは、待ち期間はＮ十Ｍ−）−１スロツトである。もし
別のノーどの搬送波が検出されることなく待ち期間が経
過すれば開始ノードが裁定に勝ったことになり、そのノ
ードが別の通路上で現在データを受信中でなければ、そ
の・（ケラト（単或は複）を送信する。しかも、もし１
般送波を検出すると裁定が失なわれ、搬送波が検出され
る前に待ったスロットの数のカウントが減じられる。待
ったスロットの数（法Ｍ）マイナス１は送信したノード
、即ち最後に裁定を勝ちとった（ＬＷ）ノードの番号で
ある。開始ノードはそのノード番号とＬＷとを比較し、
この比較に基づいてその待ち時間値をセットする。もし
番号ＬＷが自らのノード番号（Ｎ）よりも小さければ、
新らしい待ち時間値はＮ’＋　１とな夛（即ち待ち時間
値が小さくなって優先順位が高くなる）、ＬＷが自らの
ノード番号（Ｎ）よりも大きければ新らしい待ち時間血
はＮ＋Ｍ＋１となる（即ち待ち時間値が大きくなって優
先順位は低くなる）。或は、この比較は、Ｎに対するＬ
Ｗの相対値を決定することによってより直接的に行なっ
てもよい。

以上のように、バスに対して相当な要望が存在し。

バスがほぼ連続的に使用されているような飽和或はほぼ
飽和状態における衝突は最低化され、アクセスはラウン
トロピン基準で行なわれる。即ち、各７−Ｐはその順番
を待つので高位ノード番号の全てのノードは低い優先順
位に移る前に送信することができる。換言すれば、与え
られた時点にアクセスを望む全てのノードは、何れかの
ノードが第２の機会を持つ前に１．１回はバスにアクセ
スできるのである。同じ優先順位レベル（高いか或は低
い）にある２つのノードが同時に待っている場合には、
低いアドレス（即ちノード番号）を持っている方が勝つ
。時間の若干部分てバスが遊休となるような軽負荷状態
では、システムはバスに対して紛争型の゛アクセスとす
る。即ち必要ならば衝突検知及び再試行を行なわせる。

衝突は、バスが遊休であった場合にのみ生じ得るもので
あり、そこで２つのノードはそノ１らのアドレスが異な
るのと同量だけ異なる時間（スロット数で表わされる）
に亘って争い始める。両者が同時に送電しようとする衝
突が起る。衝突は・母ケットに害を与え、これは受信機
において計算されたものと一致するように・臂ケットと
共に送信される誤り補正コード（これは、例えば周期的
冗長度チェック（ＣＲＣ）コードであってよい）の不首
尾によって検出される・ タイムアウト期間は、あるノードが裁定に勝つことがで
きないような（現在の裁定カウント値では搬送波の不存
在が検出されることがない）情況に対して特定されてい
るＯ裁定タイマが満期になると送信不履行を・指示する
応答をもたらす。タイマ（図示せず）はノードのプロセ
ッサ或はインターフェイスの中に設けてよい。

送信が成功するとパケットの受信を確認するために直ち
に受信証が返送される。即ちノードが情報ノやケラトの
受信に成功すると、その／？チケット受信したことを直
ちに通報する。受ｆ目の通報は受信社則コードを含む特
別な／臂ケットを送信することによって遂行される。受
信証ノ９ケットの送信には裁定は不要であり、送信搬送
波が物理的チャンネルから消滅すると直ちにこのパケッ
トが送信される。受信証は、別のノードが沈黙スロット
に対する裁定を求める程搬送波間隙が充分に長くなる前
に戻さなければならない（この場合ノード０が微妙なノ
ードである）。

以下に添附図ＩＩを参照して本発明の詳細な説明するが
、本発明の上記及び他の目的及び長所が更に理解されよ
う。

本発明が肩用な種類の典型的ネットワークを第１図に示
す。そこでは、ネットワーク１は、ノ９ス１２によって
相互に接続された複数のノード２（ａ）〜、２（ｎ）か
ら構成されている。

信頼性を改善するために、全てのノード２（ａ）〜２（
ｎ）が唯一の通路が代りに複数の通路を持つバスによっ
て接続されるような多重（例えばデュアル）通ｙ＝パス
を用いることができる。本裁定方式は、あるノードに、
そのノードがｒ−夕を送受信できるｉ、２（或は第３Ｓ
第弘等）のシーリアル通路で争う能力を与える。

この方式によれば、そのノードが裁定か行なわれつつあ
る別の通路上でデータを受信中であれば、裁定プロセス
を制御されたやり方で続行させることができる。別の通
路上で受ｆ１及び受信証通報が完了すると、裁定プロセ
スが７９１望通路上で完了してしまえば、ノードは送信
できるようになる。送ｆｄが行なわれる度に、２つの通
路の一方が選択される。経済性の目的から、各ノードの
Ｉ・−ドウエアの大部分はλつの通路間で時分割するこ
とかできる。

これは裁定プロセスを複雑にするので、本説明はデュア
ル通路、分割ノ・−ドウエアバスが含まれているものと
仮定している。もし単一の通路バスが利用可能であれば
、以下に説明する実施例が伺処で、またどのようにして
簡略化できるか、及びどのように２つ以上の通路に拡張
できるかは容易に理解できよう。

本発明の基本的な裁定システムを第２図に示す。

図示のように、裁定は２つの一一■−パス辿路、即ちバ
ス通路Ａ（１２Ａ）及びバス通路Ｂ　（１２Ｂ）−に対
して遂行される。各バス通路はそれ自体のラインレシー
バ１４Ａ、１４Ｂ、及び搬送波検出回路１６Ａ、１６日
を有している。デュアル通路受信は、両通路の搬送波検
出器１６Ａ、１６Ｂが何れかの通路に搬送波の初期の存
在（即ちオフからオンへの遷移）を監視することによっ
て実施される。搬送波スイッチ１７は搬送波検出器１６
Ａ１１６日に応答して、受信処理回路２６を初めに搬送
波初期存在を呈した方の通路へ切替える。両速路上で同
時に搬送波の存在が検出された場合には、先行の紛争に
よって一方の通路が選ばれるようになる。搬送波スイッ
チ１７は、パケットヘッダーがデコードされるまで選ば
れた通路を監視し続ける。受信処理回路２６内の回路は
ヘッダー内の宛先アドレスをデコードし、搬送波スイッ
チ１７はそのパケットが自分のノードに宛てられている
ものか否かに関してその通路の監視を続行し、もしその
パケットが別のノード宛であればその通路から切Ｒ（１
す。搬送波スイッチ１７が受信処理回路２６をある通路
から切離した場合、再び搬送波の初期存在を探す状態忙
突入する。搬送波スイッチ１７は、既に搬送波の存在が
確足されている通路に切替えることはなり０ 低連すれば、本裁定プロセスは両通路に関して同一であ
るから、以下の説明ではバスＡに関する裁定プロセスの
みを詳述するが、パス日は実質的にその鏡像であること
を理解されたい。

また本裁定プロセスを第３図に示すフローチャートに基
づいて説明するから、以下第２図及び第３図を一緒に参
照されたい。

先ず第２図において、特定のノードのための本裁定プロ
セスは制御回路１８が第１の状態５２にある場合から開
始される。この状態においては、送信命令ライン２０が
監視され、ノードが送信を望んでいるか否かの決定がな
される。もし望んでいなけれは、送信命令が検出される
までライン２０のステータスの監視が続けられる。一旦
送信命令が検出されると、プロセスは状態５４に進み、
割切ｊ回路五８によって裁定カウンタ２２にＭ十Ｎ＋１
（Ｍは回路網内のノードの最大数、Ｎはそのノードの番
号）に等しいカウント（即ち裁定カウント値、ＡＣＶ）
がロードされる。以下に説明するように、裁定カウンタ
２２はダウンカウンタである。

カウンタ２２内にロードされる裁定値カウントは、ノー
ドが送信できるようになる前に搬送波が存在していない
ことを観測しなければならない連続するスロットの級で
ある。この基本沈黙スロット期間は、受信ノードが状覇
を切替えて受信証パケットの送信を開始できるように、
また同じ通路で争そ訃うとしている別のノードが沈黙ス
ロットの終了前に受信証の送受を確認できるように、充
分に長くなっている。受信証パケットは、制御のための
最初の裁定を受けることなくバス上に送信される唯一の
、ｆケラトである。

裁定スロットは、送信クロック期間の倍数であるスロッ
ト期間が終ったことを表わしている基本スロットタイマ
２１のキャリーアウト（ＣＯ）オーバー７０−によって
通知される。

制御回路１８は、次に、送信全行ないたいバスの状態を
チェックする（ライン２４上の通路選択信号の状態によ
って示される）。状態（或は段階）５６ては選択された
通路用の搬送波検出器１６Ａ或は１６Ｂがその上に搬送
波が存在していることを指示して別のノードが裁定に勝
ったことを表示していると、制御は段階５８に進み、そ
うでない場合には段階６０に分岐する。

段階５８ではバスの裁定に勝った最終ノードの番号（Ｌ
Ｗ）と、自分のノードの番号（Ｎ）とが比較される。次
で、裁定カウンタ２２に、（ＬＷがＮｊυも少なければ
）Ｎ＋１か、或は（ＬＷがＮよシも大きいか或はＮに等
しければ）Ｍ＋Ｎ＋７１の何れかの新らしい裁定カウン
ト値がロードされる（段階６２Ａ或は６２Ｂ）。裁定カ
ウンタ２２への再ロードが終了すると段階５６に戻され
るＯ 要約すれは、あるノードは次のようにして、どのノード
が最終裁定に勝った（ＬＷ）かを決定するのである。裁
定プロセスの初めに、ノードは自らの裁定カウントダウ
ン値の写しｆ：記憶する（例えばノード番号比較手段２
５の中に）。搬送波の検出によって裁定が終った時の裁
定カウンタ２２内の残り値（法Ｍ）は、裁定に勝つ九ノ
ードのノード番号（ＬＷ）が送信を待っているノードの
７〜ド番号よりも高いのか、或は低いのかを示している
。しかし、搬送波の消滅は各ノードの裁定ロジックと同
期するイベントであるので、このことはバスが活動して
いる場合にのみ真であることに注目されたい。

段階６０では裁定カウンタ２２０カウントが１だけ減ら
される。次に段階６４においてカウンタの内容がオーバ
ーフローしたか、即ち０に達したかどうかが検査される
。カウントが０であることは裁定に成功した（勝った）
ことを表わしている。

これはＡＮＤ）ｒ４−）２３の出力に表示される。もし
カウントが０でなければ、裁定が不成功であり、制御は
段階５６に戻される。

裁定が成功であったものとし、もし両バヌ１２Ａ及び１
２Ｂから受けた情報を処理するのに共通の受信処理回路
２６を用いていれば（両バス間で時分割）、送信機（即
ち制御回路１８）は次に段階６６において交番バスの一
方上で受信機が多忙であるか否かを検査する。もし多忙
でなければ、段階６８において受信処理回路２６は選択
された送信通路に錠止され、送信が開始される。この送
信は段階７０において監視され、送イｄが完ｒすると制
御は裁定プロセスのエントリ点に戻される。

段階６６において受信処理回路が多忙と判ホ畑れれば、
段階７２において裁定カウンタ２２にＭがロードされ、
段階５６に戻される。

受信処理回路２６は、次のことの１つが発生した場合多
忙と判断される。即ち、＋１１９番通路上で搬送波が検
出され、送信が別のノードに宛てられているものと未だ
に決定されていないか、Ｌ２１　／？チケットなわちメ
ツセージを交番通路上においてそ信を完了し、送信機が
受信証パケットの送信を遂行中である場合である。

交番バス通路が利用できる場合、時分割受信処理回路２
６ｔま送信中、及び受信証を受けるが受信証タイマ（図
示せず）が満期になるまで選択された通路に錠止される
。

情報パケットを送信したノードは、その送信が完了する
と直ちに受信証・ぐケラトの受信を企図しなければなら
ない。もし受信証タイムアウト期間内に受信証が受信さ
れなければ、送信は失敗したものとみなされる。これは
無返答（Ｎｏ　Ｒ５Ｐ　）　　受信証と呼ばれる。Ｎｏ
　　Ｒ３Ｐ受信証は、宛先ノードがノ母ケットヲ正しく
受信せず、従ってその・ぐケラトに対して受信証を与え
られないが、或は受信証・やケラトが変形されていた場
合に生ずる。最小裁定タイムアウト時間は、実際の設備
毎に決定される。

Ｎｏ　　Ｒ５Ｐ受信証は、バス雑音（ＣＲＣコード比較
の失敗をもたらす）、複数のノードによる同時送信（即
ち衝突、これはＣＲＣ比較の失敗によって通知される）
、或はあるノードにおいて・母ケットが送信されたバス
通路上でのそのパケットの受信率Ｉｉ１：　（例えば通
路或はインターフェイスハードウェアの故障等による）
の結果として生ずる。

・臂ケットを首尾よく受信したことを表わす受信証には
２つの型がある。第１の型は、受信が成功であったこと
、即ち送信されたパケットが受信ノードのホストコンピ
ュータにおいて利用できることを示す積極的な受信証（
ＡＣに）である。枳２の型は、パケットは正しく受信さ
れたがインターフェイスがそれをバッファできなかった
（即ち、？ケラトが放棄された）ことを示す消極的な受
信証（ＮＡに）である。実際のバッファリングは実装毎
に独自のものであるが、パケットを処理できない過剰イ
ンターフェイスの概念は全ての実装に過用される。イン
ターフェイスにおける過剰は、相互接続媒体上の全ての
ノードに対して利用できる帯域中の量を減少させるので
、その可能性を最小ならしめるべきである。

各受信証メツセージは、それが宛先のノードがら受信さ
れたものであることを確醪するために点検される。（こ
の目的に使用される）母ケットフォーマットの詳細に関
してはＷ、ストレッヵ等の米国特許出願第３７３りざ≠
号（弁理士ドヶット番号８３−２９８）「ダイレクト・
メモリ対メモリ・インターコンピュータ通信方法及び装
置」と参照されたい。） 送信を行なったがＮｏ　　Ｒ３Ｐ或はＮＡにの何れかで
ある場合には、次のアルゴリズムに従っ、て再送信を行
なゎなけれＩ／ｉならない。即ちＮＬＪ　　Ｒ８Ｐの場
合には、その・ｆケラ）Ｋ対して所定数（例えば６４）
よシ少ない連続Ｎｏ　　Ｒ８Ｐが発生したならは再送信
を企図すべきである。ＮＡにの場合には、その・母ケッ
トに対して別の所定数（例えば１２８）よシも少ないＮ
　Ａにが発生したならば（連続である必要はない）再送
（ｉ！を計画すべきである□ パケットが再送信に利用できる場合には「硬貨の表裏を
決定するトス」による決定を行なゎなければならない。

もし結果が１−真」であれば再送信が計画される。もし
「偽」であれば遅延時間を待ってから決定を反覆する。

この遅延時間は最短でもＭスロット時とすべきである。

通常選択されるスロット時の値は、１６ノードの回路網
に対して１２．８マイクロ秒の最短遅延時間を与える例
えば８００ナノ秒に固定されている。最長時間は制限さ
れていないが、通常はスループットに対する考慮がこの
最長時間を制限する。遅延は一貫させる必要がない。こ
れは一定でないサービス潜在力を持った（ボールドシス
テムにおけるような）ソフトウェア或はファームウェア
制御再試行を考慮に入れたものである。最初の決定は特
別な特性を有している。再送信のための決定の時点に、
もし裁定者の同期が送信後も保たれていれば（即ちパス
上の搬送波の最後の立下りに同期を保っていれば）、裁
定が終り次第送信が行なわれる。しかし、もし同期が失
なわれていれば、再送信決定を行なう前に単一の遅延時
間を待つべきである。これは再送信決定に対する一貫し
た裁定妨害を防ぐことになる。もしインターフェイスが
、再送信しなければならないこと全決定するのに常に一
定址の時間紮費やすのであれば、別のノードの送信との
衝突（ノード番号の差Ｘスロット＝再送信決定時間であ
るから）が定常的に発生することになる。無作為に選択
しても成功／失敗は同じ確率になる。

擬態作為ならば最小１６ビツトの発生器を用いれば満足
できる。

本方式は行き詰シを打破するために計画されたものであ
る。再試行限界の選択は、次の基準に合致するようにシ
ミュレーションから計算されたものである。即ち、正し
く機能しているシステムにおける失敗（過剰に起因する
）は、重負荷集群（即ち、回路網）において典型的に遭
遇する要因では、年に１回以上生じ得ないということで
ある。

再送信に失敗した通路はその失敗したノＱケットのため
に再試行する必要はない。そうではなく、配列更新ポー
リング（ｐｏｌｌｉｎｇ　）のためＫどのような周波数
を用いていようともそれを再試行することが適切なので
ある。

以上の説明は本発明の特定の実施例に限定しているが、
本発明は種々の基本構造を有°するデータ処理システム
、或は異なる時間間隔回路或は設計を用いるシステムに
おいて実現可能であり、しかも本発明の前記目的及び長
所の若干或は全てを達成することができる。従って、特
許請求の範囲の目的は、本発明の思想及び範囲内で実現
されるこれらの全ての変化、変形及び明白な改良をカバ
ーしようとするものである。

【図面の簡単な説明】

第１図は本発明が使用できる典型的なネットワークのブ
ロックダイアグ２ム、第２図は本発明によるパス裁定を
遂行するだめの装置のブロックダイアダラム、そして第
３図は裁定プロセスを示すフローチャートである。 １２・・・・・パス通路、１４・・・・・ラインレシー
バ、１６・・・・・搬送波検出回路、１７・・・・・搬
送波スイッチ、１８・・・・・制御回路、２０・・・・
・送イＳ命令ライン、２１・・・・・基本スロットタイ
マ、２２・・・・・裁定カクンタ、２３・・・・・ＡＮ
Ｄゲート１２４・・・・・通路選択ツイン、２５・・・
・・／−１’番号比較手段、２６・・・・・受信処理回
路。 特許庁長官　殿 ■、事件の表示　昭和５８年　特許願　第７９１９７号
３、補正をする者 事件との関係　　出願人 ４、代理人 ５、補正命令の日付　　　昭和５８年８月３０日４６３
−

Claims (1)

1. 【特許請求の範囲】 （１）　　ビット・シリアルバスを介して複数のコンピ
   ュータノードを相互接続するための回路網において；各
   ノードに対する優先順位値の帰すうによってバスへのア
   クセスを制御し、且つ最高優先順位値を有していてアク
   セスを要求しつつあ　（３するノードにアクセスを許可
   するための裁定手段を備え；この裁定手段がバスに対す
   るアクセスの要求が多い状態の下では優先順位値の平均
   が各ノードに対して同一となるように優先順位値を割当
   てるようになっていることを％徴とする改良。 （２）　ビットーシリアルバスケ介して複数のコンピュ
   ータノードを相互接続するための回路網において：パス
   に対する要求が少ない状態の下では各ノードがアクセス
   に関して個別に争って別のノードからの送信との衝突を
   生ずることなく最初の送信するノードがアクセスを得る
   ノードとなるようにバスへのアクセスを制御し、一方バ
   スに対する要求が多い状態の下では任意の時点にバスに
   アクセスを望む全てのノードに対してどのノードもがバ
   スに２回目のアクセスを得る前に、制御されたやり方で
   、バスへ１回アクセスすることを許容するようにアクセ
   スを制御する手段を備えたことを特徴とする改良。 １　ピット・シリアルバスを介して複数のコンピュータ
   ノードを相互接続するための回路網において、バスへの
   アクセスを制御するための装置が； イ、バス上の送信信号の存否を検出する搬送波検出器手
   段、 口、搬送波検出器手段に応答し、バス上の送信信号の消
   滅を検出した時に開始され所定の接続時間に亘って時間
   スロットの経過をカウントする裁定カウンタ手段、 ハ、裁定カウンタ手段に応答し、相対的に低い値及び相
   対的に高い値の２つの考え得る値の一方を有する裁定カ
   ウント値（ＡＣＶ）を発生する手段、 二、搬送波検出器手段に応答し、パス上に送信信号の存
   在を検出した場合には裁定カウンタ手段がカウントする
   のを禁止させる手段、を備え、 ホ、前記載定カウンタ手段が、経過した時間スロットの
   数と裁定カウント値とを比較し、経過した時間スロット
   とそのノードのＡＣＶとが等しいことを見出した場合そ
   のノードに対してバス上での送信開始をｒｔ容する信号
   を発生するようになっており、そして へ、裁定カウンタ手段の県北に応答し１裁定カウンタに
   新らしいＡＣＶを供給する手段、をもＯｆｆえているこ
   とを特徴とする装置。 （４）　　ビット・シリアルバスを介して複数のコンピ
   ュータノードを相互接続するための回路網において、こ
   れらのノードによるパスへのアクセスを制御するための
   方法であって； イ、各ノードがパス上に送信の開始を許可される前にバ
   スを不活動にさせなければなら、ない所定の長さの時間
   スロットの数である裁定カウント値（ＡＣＶ）を各ノー
   ドに割当て、口、各ノードをノード番号によって識別し
   、ハ、あるノードが送信を望んでいる場合、その裁定カ
   ウント値を第１の相対的に高い値にイニシャライズし、
   そして 二、送信を望んでいる各ノードに、パスを不活動ならし
   める時間スロットの数をカウントさせつつ他のノードの
   送信搬送波の有無に関してパスを監視させ、また ｉ　複数の時間スロットのカウントの満期がそのノード
   のＡＣＶに咎しくなる前に別のノードの搬送波を検出し
   た場合には、 （イ）　搬送波が検出されたノードのノード番号（ＬＷ
   ）が、送信を望んでいるノードの７一ド番号Ｎよりも大
   きいか或は小さいかを決定し、 （ロ）　もしＬＷがＮよりも小さければ、送信を望んで
   いるノードのＡＣＶを相対的に低い値に設定し、 （ハ）　もしＬＷがＮよりも大きいか或はＮに等しけれ
   ば、送信を望んでいるノードのＡＣＶを相対的に高い値
   に設定し、そして に）　この段ｉ二の初めに戻し、そしてＩｔ、　　別の
   ノードの搬送波を検出することなく複数の時ｆＭｊスロ
   ットをそのノードのＡＣＶに等しくなるまでカウントし
   た場合には、送信を望んでいるノードに送信を許可する
   、諸段階からなっていることを特徴とする方法。