JPH07122862B2 - ネットワークにおけるコンピュータ及びその運用方法 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は互いに連結された複数の
コンピュータ・ノードからなるネットワークにおいて１
つのノードを形成するコンピュータの運用法方に関連す
る。

【０００２】

【従来の技術】過去数年間パーソナル・コンピュータや
ワークステーションをネットワークに接続し、異なった
端末機間で通信を行うことが一般的になってきた。典型
的な方法は、コンピュータ間でファイル転送やその他の
機能を提供するローカル・エリア・ネットワーク（ＬＡ
Ｎ）である。他のタイプの接続、例えばサービス総合デ
ジタル網（ＩＳＤＮ）も知られている。このようなネッ
トワークはユーザに対して新しい形のアプリケーション
の可能性を提供し、例えば欧州特許ＥＰＡ４７５５８１
は、１台又は多くの異なった端末機が同時に且つ組み合
わせた形で１つのプログラム（例えば表計算）上で仕事
をする協同作業環境について述べている。また別の可能
性は、マルチメジア・ビデオ・ディスプレイを備えたパ
ーソナル・コンピュータを使ったテレビ会議である。

【０００３】

【発明が解決しようとする課題】最大限の柔軟性と便宜
性を達成するために、このような協同作業及びマルチメ
デイア・アプリケーションはコミュニケーション・サブ
システムに大きな要求を課すことになる。同様にネット
ワークは複数の物理的ネットワークを使用できなければ
ならない。例えば１つの場所におけるＬＡＮ上のワーク
ステーションは、ＩＳＤＮ回線を通して他のＬＡＮと接
続できる（注意を要するのは、ここで使われている「ネ
ットワーク」という用語は電線でつながれた物理的ネッ
トワークでなく、互いに通信を行っている一群の論理的
ノードである）。このようなネットワーク環境の提供
は、多くの技術的問題点をもたらす。例えば、どのよう
にして端末機に固有の名前を与えて、ネットワーク上の
他の端末機から識別できるようにするかという問題であ
る。

【０００４】ネットワークは雑多で（複数のタイプの物
理的接続と複数のコンピュータに基づいている）である
ため、特定のハードウエア・システムの識別子（例えば
ＩＳＤＮにおける電話番号やＬＡＮにおけるＬＡＮカー
ド識別子）を使うことは不可能である。更にネットワー
クがダイナミックであるという本質から、端末機が秩序
良くネットワークに参加し、或いは離脱できなければな
らない。勿論、ネットワークは通信回線や端末機がネッ
トワーク上で故障し、実際上ネットワークを分離すると
いった状況にも対処できなければならない。

【０００５】

【課題を解決するための手段】従って本発明は、最小ス
パン・ツリー構造に接続されたネットワークにおけるノ
ードを形成するコンピュータの運用に関して次のステッ
プからなる運用法方を提供する：コンピュータに接続さ
れた第１のノードからメッセージを受信し、そのメッセ
ージを識別する情報を記憶し、そのコンピュータに接続
された他のノードへメッセージを転送し、上記他のノー
ドからそのメッセージに対する応答を受信し、上記他の
ノードから受信した応答と記憶した情報とを一緒にして
単一の応答を生成し、その単一の応答を上記第１のノー
ドへ送信する。

【０００６】このようにして、ネットワーク上の各ノー
ドが最初にメッセージを発信したノードに対して応答を
繰り返すことなく、経路上のブランチ・ノード（ノン・
リーフ）で単一の応答にとりまとめられる。従ってどの
ノードからの応答も、最初に発信したノードへの経路上
で通過する一群のノードに関する状況を要約する。この
方法は、各応答がとりまとめられる前に、隣接したノー
ドへ送られるだけなので明らかにネットワーク上の通信
量を節減する。更に、応答を処理する負担も、最初に発
信したノードに集中するよりもネットワーク上に分散さ
れる。

【０００７】この方法は、更に次のステップを含むこと
が望ましい。：上記他のノードの１つへの通信回線断に
よって通信が遮断されたことを検出し、遮断されたノー
ドからの応答が未処理であるメッセージがあるかどうか
検査し、もしあれば、新しいネットワークの構成に対し
て適切で、そのノードからの実質的応答を生成する。こ
のようにして、回線断が発生し、その結果ネットワーク
の１部の接続が遮断されたら、ネットワークは遮断され
た部分を含まないように実際上再編成される（このこと
は勿論自分自身のネットワーク上で行われる）。１度１
つのノードが、接続されているネットワークの１部が遮
断されたということを検出すると、そのノードはネット
ワークのその部分からの応答を待っているメッセージが
あるかどうか探す。どんな未処理の応答でも、そのメッ
セージの性質に基づいて、そのノード自身によって用意
される。１例として、メッセージがネットワーク内で固
有の識別子を予約する要求である場合を考える。各ノー
ドはその識別子が使用可能かどうかを伝えるよう応答す
る。応答はまとめて一緒にされるので、否定の応答を受
け取るどのノードもそれを否定の応答として転送しなけ
ればならない。しかしながら、もし通信回線が故障する
と、その特定の通信回線に関して肯定の応答（すなわ
ち、その識別子は使用可能である）を挿入しても安全で
ある。なぜなら、ネットワークのその部分は実際上死ん
でおり、それ故重複した識別子を持ち得ないからであ
る。しかしながら、もし通信回線が復旧したとき、重複
した識別子をなくする注意が必要である。

【０００８】１つの可能性は、１つのネットワーク・セ
グメントから他のセグメントへノードの数を１つずつ増
やして、各ノードについて識別子の予約処理を行うこと
である。メッセージが、そのコンピュータに特定の動作
をするよう指示している場合、本発明の方法は更に、メ
ッセージに対する応答を他のノードから受信した後、上
記動作を実行するステップを含むことが望ましい。特定
の現象が発生したことを知らせるようなメッセージに関
しては、ひとまとめにするための確認の応答を受信する
前に、そのコンピュータが、適切な行動（構成表の更新
など）をすることは可能である（これは外方向の反作用
戦略として参照される）。

【０００９】しかしながら、いくつかのメッセージに関
しては、しかるべき行動をとる前に応答がひとまとめに
されることが適切である。例えば、もしメッセージがノ
ードの削除を要求するものであり、通常の動作をすると
（直ちに消してしまうと）そのコンピュータとそのノー
ドの通信の妨げになる場合には、その動作は全ての応答
を受信し終わるまで待つべきである。このことによっ
て、もし１つのノードが、削除されるべきノードとメッ
セージの交換中であるという理由で、否定の応答を送る
と、コンピュータが、これらのメッセージをどのように
処理するかを知っているということが確かめられる。

【００１０】本発明はまた、最小スパン・ツリー構造に
接続されたネットワークにおけるノードを形成するコン
ピュータ・ワークステーションを提供する。そのワーク
ステーションは、次のものから構成される。：コンピュ
ータに接続された第１のノードからメッセージを受信す
る手段と、そのメッセージを識別する情報を記憶する手
段と、そのコンピュータに接続された他のノードへメッ
セージを転送する手段と、上記他のノードからそのメッ
セージに対する応答を受信する手段と、上記他のノード
から受信した応答と記憶した情報とを一緒にして単一の
応答を生成する手段と、その応答を上記第１のノードへ
送信する手段。

【００１１】

【実施例】本発明の具体例について図面を参照しながら
説明する。図１はコンピュータ・ネットワークに参加し
ている一群のワークステーション（Ａ，Ｂ，Ｃ，・・
Ｋ）を示す。接続の形態は「最小スパン・ツリー」とし
て知られている。このようなネットワークは、閉じたル
ープがないという特徴があり、２つのノード間にはただ
１つの経路しかない。最小スパン・ツリーの使用によっ
て複雑な経路手法の必要がなくなる。（ネットワーク構
成の詳細については、１９８８年Ｐrentice-Ｈall,ＡＳ
Ｔanenbsaum による［Ｃomputer Ｎetworks 」を参照
されたい。）特に図１のネットワークにおける接続は全
て同じタイプのものではない。

【００１２】例えば、Ｂ−Ｅ，Ｅ−Ｆ及びＦ−Ｇの接続
は，ＩＳＤＮ回線であり一方Ａ−Ｂ，Ｂ−Ｃ及びＢ−Ｄ
はＬＡＮの１部であり、Ｅ−Ｊ及びＥ−Ｋは別のＬＡＮ
の１部、Ｇ−Ｈ及びＧ−Ｉは第３のＬＡＮの１部である
場合がある。これらの通信回線は、たとえ名目上は同一
ＬＡＮ上の同一タイプのメンバーであっても、異なった
帯域幅であったり、異なった通信量であったりし、その
結果伝送効率が異なる。Ｘ．２５のような他の多くのタ
イプの通信回線もそのネットワークに接続できる（ここ
で述べる「ネットワーク」は一群の論理的ノードを表
し、物理的に接続された端末のセットではないことに注
意されたい）。

【００１３】図２は図１のネットワークにおいてノード
を形成するワークステーション１０を示す。これは典型
的には、プロセッサ，メモリ及びネットワーク施設（こ
の場合ＬＡＮ６及びＩＳＤＮ４への接続のためのアダプ
タ・カード等）を有する一般的コンピュータである。ま
た図２には、３つの処理レイヤー、アプリケーション２
０、ネットワーク制御レイヤー２２（ＮＣＬ）及び共通
通信レイヤー２４（ＣＣＬ）が描かれている。アプリケ
ーションは、ユーザが実際わかっていることであるが、
最初にネットワークへの接続を要求し、他の端末へ伝送
するためのデータを生成し、受信したデータを処理す
る。ＮＣＬは、本発明の目的に最も重要なものである
が、ネットワークを論理的実体として管理する。

【００１４】すなわち、どのノードがネットワークに接
続されているかといった記録などを維持する。ＣＣＬ
は、簡単に言えば、ネットワークとの物理的相互作用を
制御する。メッセージは、他の端末へ送るために、アプ
リケーションからＮＣＬを通ってＣＣＬへ渡される。Ｃ
ＣＬは、メッセージをセグメントやデータ・バッファに
分割したり、アドレス情報を追加したりして実際の伝送
の準備をする。データ・バッファの保証され且つ順序正
しい伝達を提供するマルチ・ポイント・ネットワーク
は、図１に示すポイント・ツー・ポイント通信回線のセ
ットから形成されなければならない。この能力は、雑多
な基礎的通信回線上に如何なる統一された普遍的アドレ
ス体系なしに与えられなければならず、またネットワー
クの動的再編成を許さなければならない。

【００１５】これによるネットワーク効率への影響は最
小でなければならない。ネットワーク内の各ノードは、
多くの他のノードに接続する能力を有し、他のノードは
更に他のノードに接続でき、これらが一緒になってネッ
トワークを構成する。このネットワークは、データ・バ
ッファの目的地への伝達を保証する能力を持たねばなら
ない（ユーザがある程度の誤った伝達や必要に応じて再
送を想定しなければならないような信頼性のない通信体
系とは対照的に）。ネットワークはまた、伝送に関して
ユーザによって提出された順序と同じ順序でバッファを
伝達しなければならない。（ネットワークは、ユーザに
対して多くのデータ経路を１つの通信回線に多重伝送す
る能力を提供することに注意されたい。ネットワーク
は、これら多重化されたデータ経路のそれぞれについて
は順序どおりの伝達を行うけれども、必ずしも全体の多
重データ経路に関しては、元の順序には固執しない。）
従って、ネットワークは、その独自のアドレス体系を持
たねばならず、データの保証された、順序どおりの伝達
に関する上記の目的を損なうことなく、ネットワークに
おけるノードの「進行中」の追加、削除処理をサポート
しなければならない。上記要件にあうように、表１から
表５の通信プロトコルが開発された。これは、一群の事
前に設定された制御メッセージであり、ネットワークの
制御のためＮＣＬレベルでノード間で交換される。プロ
トコルは、多くのプロトコル・データ・ユニット（ＰＤ
Ｕ）からなり、それらは一般的慣習に従って名付けられ
ている。

【００１６】例えば、ノードに対して何らかの行動を要
求するＰＤＵはＲＥＱＥＳＴと、要求に対する応答は、
ＲＥＳＰＯＮＳＥというように命名される。要求されて
いないＰＤＵ、ある現象が発生したことの通知或いは、
ネットワーク上のデータの通知をＩＮＤＩＣＡＴＩＯＮ
と名付ける。ある種の通知には確認のＰＤＵが含まれ
る。これらはＣＯＮＦＩＲＭＡＴＩＯＮと名付けられ
る。いくつかのＰＤＵの目的はかなり明白であるが、他
の説明を要するＰＤＵについては以下詳しく述べる。

【００１７】図３は、図１におけるネットワークのノー
ドＥに関してＮＣＬ２２によって記憶された情報を示し
ている。ＮＣは２つの表３０、３２を維持し、経路表３
０はネットワーク構成に関するＥの知識を含んでいる。

【００１８】この表は、Ｅに直接接続されているノード
（Ｂ，Ｋ，Ｊ，Ｆ）を列記している。直接接続されたこ
れらノードに付随して、依存ノードすなわち特定の直接
接続されたノードを経由してＥと接続しているノードが
ある。もしＥがメッセージをＩへ送ろうとすると、Ｅは
Ｆ経由でＩに到達できることが分かり、メッセージをＦ
へ送ることになる。ノードＦもまた経路表を持ってお
り、その経路表にはＥとＧが直接接続のノード、（Ａ，
Ｂ，Ｃ，Ｄ，Ｊ，Ｋ）及び（Ｈ，Ｉ）を２つの依存ノー
ドのセットとして記述されている。この場合Ｆはメッセ
ージをＧへ転送するよう決定し、Ｇは最終目的地である
Ｉへ送る。

【００１９】新規のノードがネットワークに参加すると
きはいつでも、ＮＣＬ・ＩＮＤ・ＭＥＭ・ＩＮＦＯメッ
セージがネットワークに流され、各ノードはその経路表
を更新する。同様の処理がノードをネットワークから削
除するときも行われる。ネットワークは、複数の伝達経
路に対処するための高等な経路手法の必要がないよう
に、最小スパン・ツリーに限定される。このことはま
た、ネットワークにおける応答の監視を簡略化する。ど
のノードからの応答も、要求の元の発信者へ到達するた
めにとり得るネットワーク上の経路は１つしかないの
で、応答が要求が通ってきた経路を逆にたどることは明
らかである。（ネットワーク構造がその期間中変わらな
いと言う前提で、このことは後に述べる方向的反作用戦
略によって保証されている。）このことは、複数キャス
トの要求に対する応答を扱うのに単純な方法の使用を容
易にしている。

【００２０】複数の回線へ向けて要求を発したノード
は、要求を出した先の各回線からの応答を待ち、全ての
回線が応答を返したときだけ、応答を作成しそのノード
が元の要求を受信した相手のノードへその応答を返す。
この処理を「とりまとめ」と名付ける。とりまとめ役の
ノードが生成する応答の状態は、そのノードがとりまと
める応答の組み合わせの中で最悪の場合の状態である。
このことは図３の第２の表を使って行われ、第２の表を
「とりまとめの表」３２と名付ける。この表には、その
ノードを通過し、応答（応答又は確認）を待っている全
てのメッセージが記載される。各メッセージは情報４
２，４４を有し、情報４２，４４は例えば起点のノード
（或いは少なくともＥにメッセージを転送したノード）
に関する他の情報同様メッセージを識別し、データ経路
を識別する。（データ経路は、２つのノード間の論理チ
ャネルである。）更に各メッセージに関して、メッセー
ジが送られたノードのリスト４６とそれぞれのノードに
関する応答（もしあれば）４８が記憶されている。こう
して、ノードＢから受信したと思われるメッセージ１に
関して、Ｆ，Ｊ，Ｋからの応答を待っているということ
が分かる。（Ｆからの応答は、Ｆ，Ｇ，Ｈ及びＩからの
応答をとりまとめたものであることに注意されたい。）
恐らくノードＫが生成したものと思われるメッセージ２
に関しては、Ｊ，Ｆからの応答をすでに受信し、Ｂから
の応答は未着である。特定のメッセージについて全ての
応答がとりまとめられると、ＮＣＬはその支線に関する
全体の応答を生成することができ、応答を伝送し、その
メッセージをとりまとめ表から削除することができる。

【００２１】このネットワークに重要な機能の１つは、
応答がない場合を処理する能力があるということであ
る。要求或いは通知を発信又は中継するノードが応答或
いは確認の受信に失敗する理由は２つある。１つは、ネ
ットワーク上のどこかのノードが中断している場合であ
り、もう１つは、回線接続が切れた場合である。前者の
場合では、要求或いは通知を出したノードでタイム・ア
ウトとなる（タイム・アウトは手動の場合も自動の場合
もあり得る）。後者の場合には、ＮＣＬが自動的に応答
或いは確認の生成を行う。もしネットワーク上の通信回
線の接続が切断されると、切断された回線に隣接する各
ノードは、未処理の要求或いは通知を探し、新しい回線
構成にあった応答或いは確認のＰＤＵを生成する。

【００２２】回線断の現象に対して適切であると考えら
れる応答或いは確認のタイプは、要求或いは通知の本質
に依存する。要求が識別子（グループ，メンバー又はデ
ータ経路）の使用に関するものである場合、適切な応答
は、回線によりネットワークから削除されたノードは、
そのネットワーク内で識別子の使用に関して競合するこ
とはないので、結果良好の状態コード（識別子が使え
る）である。図３のメッセージ２の例では、もしＢへの
回線が切断されると、識別子の要求に対してＮＣＬは、
実際上Ｂからの応答［ＯＫ］を挿入する。Ｊ及びＦから
の応答は［ＯＫ］であるので、ＮＣＬは今やＫに対して
［ＯＫ］を送る立場にある。他のいくつかのタイプの要
求或いは通知（例えば新しいノードの参入を通知する）
に関しては、応答或いは確認の本質はそれほど重要でな
い。

【００２３】応答或いは確認が到着した（或いは回線障
害のため到着しなかった）という知識が要求或いは通知
を満足する情報として充分であり、その要求或いは通知
は単にグループ内の全てのノードが、次の行動を起こす
前に、要求或いは通知を受け取ったという知らせを待っ
ているだけである（ネットワーク内の同期）。この場合
の回線断では、進行しても安全であることは実際上明白
であり、ここでもまた適切な応答が生成され得る。最後
に、回線障害が要求動作の失敗を意味する要求のタイプ
があり、そのときは該ノードは元の発信者に対して否定
の応答を生成し返送する。図１のＢ−Ｅのように、回線
断が検出されると、各隣接するノード（この場合Ｂと
Ｅ）は、そのとりまとめ表内に、遮断されたノードから
の応答が未処理であるメッセージを探す。

【００２４】メッセージのタイプに基づいて、ネットワ
ークから離脱した支線に関する適切な応答が挿入され、
やがて正常な手順に従って応答が生成される。上記処理
は、ＮＣＬが２つの異なった論理レイヤーに分割される
という事実によって援助されている。下層レイヤーは、
単にデータのルーティング、応答のとりまとめ及び回線
分離を含むネットワークの維持に関連している。２つの
概念的レイヤーのうちの上層レイヤーは、ネットワーク
・ユーザに代わって行動を起こし、下層レイヤーに対し
て要求を行う。要求或いは通知の起点は、ノードの上層
のレイヤーにあるので、ネットワークにおける起点の位
置（構造的）は、回線の分離を処理する上で下層レイヤ
ーがとった行動とは関係ない。

【００２５】起点の実体は、回線分離を取り行うノード
に位置づけることもできるし、他のどこかに位置づけて
も良い。起点は単に自分が送ったメッセージに対する応
答或いは確認を待っているだけであり、受け取る応答
が、離脱したノードに代わって代理のノードによって生
成されたという事実には影響されない。更にまた起点
は、代理のノードが自分自身のノードの下層レイヤーで
あるかも知れないという事実によっても影響されない。
上記処理の例に従って、ネットワークのアドレス体系の
生成を検討する。雑多なネットワークの使用は、個々の
ノードがはっきり識別される普遍的で、事前に設定され
たアドレス体系の有効性を排除する。

【００２６】従って、固有で、共有の（すなわち、ネッ
トワーク中に知られている）の識別子或いは相関子をダ
イナミックに生成することが重要であり、２つ又はそれ
以上のコンピュータに同一の識別子を与えないように、
本質的競合状態を克服することが重要である。最初の問
題は、ノードが多くのネットワークに（同時に）参加す
る場合があるので、これらノードははっきり特定のネッ
トワークを識別することができなければならない。１対
のノード間の相関子を交換する共通の方法は、任意に大
きな数のノードをサポートしているかも知れないネット
ワークの複数の、役割という本質から適当でない（ノー
ドの数はパフォーマンスと語長など実施上の詳細のみに
よって制限される）。

【００２７】ネットワークは共通の識別子、グループＩ
Ｄによって識別される。全てのノードはネットワークを
識別するため同一のグループＩＤを使う。グループの起
点（すなわちネットワークの最初のノード）が単純にグ
ループＩＤを選択し（順番に或いは順不同に）、そのグ
ループＩＤがネットワークに加わる全てのノードによっ
て採用されるので、グループＩＤを決めるのは、容易で
ある。１つのノードがネットワークとしてのグループＩ
Ｄでネットワークに加わり、そのノードが、すでにネッ
トワークの１部であるとき衝突が起きる。この場合、そ
のノードが加わろうとするネットワークのグループＩＤ
は、以下に述べるように変えられなければならない。

【００２８】ネットワークが固有に識別されると、ネッ
トワーク内でノードを識別するための１つの体系が必要
である（「メンバー識別子」という）。従って、各ノー
ドは、新しいノードを加える（既存の）ノードによって
ネットワーク固有の識別子が割り当てられる。従って、
既存のノードは、ネットワークに固有の識別子を生成す
る何らかの手段を持たなければならない。１つの可能性
は、識別子を階層的に連結することであるが、これは識
別子をいくらでも長くしてしまう。従って、非階層的識
別子セットを作成するため調停的体系が用いられる。各
既存のノードは、ＮＣＬ・ＲＥＱ・ＭＥＭ・ＩＤという
ＰＤＵをネットワーク内の全ノードに送ることによって
新しいノードのために選んだ識別子がネットワーク固有
のものであることを確認する。

【００２９】このＰＤＵは、その識別子が現在使用中か
どうか訪ねるためのものである。この要求を受信した各
ノードでは、その識別子が、もし使用可能であれば、要
求者に代わって予約され、その要求はネットワーク内で
次々に回される。どこかのノードでその識別子がすでに
予約中又は使用中であると、その要求は次に回されるこ
となく、代わりにその要求が到着した支線を通して否定
の応答が返される。

【００３０】もしその要求がネットワークのリーフ・ノ
ード（他に１つのノードにだけ接続しているノードで、
図１のＡ，Ｃ，Ｄ，Ｋ，Ｊ，Ｉ及びＨ）に到着し、その
識別子がリーフ・ノードで使用可能であれば、その識別
子は要求者に代わって予約される。リーフ・ノードは、
肯定の応答を返し、その肯定の応答はネットワークの支
線を通って返される。

【００３１】複数の支線をサポートしているノードは、
上述のように応答のとりまとめを行う。どのノードも否
定の応答を受信したら、要求者に対して否定の応答を返
す。要求者は、要求を送った全ての支線から肯定の応答
を受信するまで待ち、それから、その識別子が他の対象
を識別するのに使用するノードは存在しないということ
を言明できる。もし要求者が１つでも否定の応答を受信
すれば、その識別子を解放し、異なった識別子で別の要
求を送る。元の識別子は、ＮＣＬ・ＲＥＬ・ＭＥＭ・Ｉ
ＤというＰＤＵを送ることによって解放される。要求者
が複数の、同時に生きている要求を持つことを許されて
いれば、明白な解放が必要である。別のやり方では、要
求者による新しい要求が、前に予約した識別子を暗黙の
うちに解放するということを許すこともできる。

【００３２】もし図３のメッセージ２がＮＣＬ・ＲＥＱ
・ＭＥＭ・ＩＤというＰＤＵを表すと想定し、Ｂとの接
続が切断されているとすれば、Ｂと付随する支線はネッ
トワークの１部ではないので、Ｅが肯定的に応答を返す
ことは許される（Ｊ、Ｆ及びＥ自身が肯定であると想定
した場合）。もし回線接続が復旧したら、新しいノード
をネットワークに追加する処理を適用して、Ｂとそれに
付随する支線をネットワークへ戻さなければならない。
このことによって、重複した識別子が検出され、解決さ
れることが保証される。ネットワーク内のノードに関す
る固有のアドレス体系の確立に従って、ネットワークに
送られたトランザクションを識別する手段を提供するこ
とは簡単である。

【００３３】１つの可能な体系は、各ノードがそのノー
ドに固有の（連続した）識別子のセットを維持し、ネッ
トワーク固有のトランザクション識別子を提供するため
に、ネットワーク固有のノード識別子とノード固有のト
ランザクション識別子とを合成してトランザクションを
識別することである。上記体系に対する別の可能性とし
て、とりまとめのノードが充分な情報を取得し次第、応
答を生成することである。例えば、もしとりまとめのノ
ードが、識別子が使用可能でないことを表すメッセージ
を受信すれば、そのノードは直ちに、他のノードからの
応答を待たずに、否定の応答を送ることができる（他の
ノードからの応答は最終の応答に影響しない）。

【００３４】更に別の変更は、回線接続が切断された場
合、そのノードから既に受信した応答で、とりまとめを
待っているものを検査して、いぜん正当であるかどうか
を調べることである。ネットワークは、多くの独立した
ノードを有し、最大の効率を得るために、ネットワーク
構成とデータ経路の変更が「進行中」に行われるので、
異なったノードが、１つの資源について争うという状況
が発生する（例えば、同一の識別子を要求する）。この
ような衝突を検出して、解決する手段がなければならな
い。資源が、使用中又は予約済みであるということは、
どの特定のノードにおいても容易に示されるので、検出
は簡単である。この問題の解決は、事前に準備された
「後戻り戦略」によって達成される。この戦略は、重複
している要求に関する１つの要求の優位性に基づいてい
る。

【００３５】どちらの要求が優位であるかの決定は、メ
ンバーＩＤがネットワーク固有であるので、単純にメン
バーＩＤに依存する。低いメンバーＩＤに優位性が与え
られる。実施上の詳細にもよるが、最も長くメンバーに
なっているノードに成功が許され、一方より最近加わっ
たノードは、後戻りして再試行する。どちらのノードが
優位かというこの明確な決定方法は、ノードによる不必
要な後戻りを防いでいる。いったん優位性が決定される
と、不成功であったノードは、そのノードがネットワー
クの状態に与えた如何なる変更をも取り消すことができ
なければならない。例えば、予約した識別子を取り消
し、或いはグループＩＤの重複の場合には、新しいグル
ープＩＤを調停し、現在使用中のそれと置き換えて使用
する。

【００３６】１つの非常に重要な通信プロトコルの局面
は、方向的反作用戦略の採用である。ある種の行動（例
えば、データ経路の設定）は、その行動がネットワーク
内を流れて、資源が設定されるので、その行動を起こす
ノードから出されなければならない。これは、ノードが
データ経路を知るようになり、資源が割り当てられるの
で、そのデータ経路を知っているノードの間で、データ
経路が機能することを保証している。「外方向」の反作
用戦略を使用するその他の行動は、識別子の使用に関す
る要求である。しかしながら、「内方向」の反作用戦略
を必要とするその他の行動もある。

【００３７】これらは、ノードの削除のような操作を含
み、その操作は、回線構成情報から、ノードの削除を実
施していない隣接してないノードが、既にノードをネッ
トワーク上の視界から削除している１つ又は複数のノー
ドによって分離されるという状況を作ってはならない。
例えばＢが、Ｄがネットワークからはずれることを通知
するメッセージＮＣＬ・ＲＥＱ・ＭＥＭ・ＤＥＬＥＴＥ
を送ったと想定する。例えばもし、ＨからＤへ行く途中
のメッセージがあったとすると、メッセージが伝達され
る前にＧ，Ｅ，Ｆが実際上Ｄを削除しない限り、Ｈがメ
ッセージの送信を継続して進めてしまっているというこ
とは、重要である。この状況を避けるために、ネットワ
ーク内の各ノン・リーフ・ノードは、削除メッセージを
記憶する（とりまとめ表と類似した方法で）。

【００３８】メッセージがリーフ・ノードに到達したと
き、これらのノードは、Ｄをネットワークからはずすた
めの適切なステップを実施する。それからノン・リーフ
・ノードは、Ｂにたいして応答を「内方向に」送り返
す。各ノン・リーフ・ノードは、上述のとりまとめ作業
と全く同じ方法で、分離操作を行う前に「内方向」のメ
ッセージを関連した隣接ノードから受信するまで待つ。
この戦略は、端末機が早まって実際上Ｄを分離する（例
えば、Ｄをその経路表から削除する）ことを回避する。
もしネットワークがユーザに、他だ一様な優先順位でな
く、一定の範囲のレベルで伝送データに優先順位を与え
る場合は、通信プロトコルに関して重大な複雑さが生ず
る。

【００３９】このような優先順位の範囲の設定によっ
て、急務のタスクが、他の急務でないタスク（例えば、
背景のファイル転送）に比べて、優れた疎通時間により
大きな利便を受ける。しかしながら、もしデータ・メッ
セージに異なった優先順位が与えられると、到着順序が
予測できなくなるので、通信制御メッセージにどんな優
先順位を与えるかを決定する必要がある。実際、制御情
報が送られる優先順位は、その制御情報に関連する行動
に依存する。ある行動は、制御ＰＤＵが少なくとも最高
の優先順位のデータのレベルと同じ優先順位で送られる
ことを必要とし、一方他のものは、最低のデータ・レベ
ルと同程度で送られるべきである。これは、如何なる種
類の資源を設定する制御も、その資源を使用するデータ
と同じように早く到着し、資源を削除する制御は常にそ
の資源を使うデータに対して資源が開放される前にネッ
トワークを通過することを許すためである。

【００４０】例えば、リーフ・ノードがデータをノード
へ送り、このノードに関する削除確認メッセージを送る
とすると、第２のメッセージはデータを追い越さないよ
うに充分ゆっくり送らなければならない。通信プロトコ
ルの最後の局面は、最適ネットワーク利用を達成するた
めのマルチ・キャスト流れ制御技術の必要性である。２
つのレベルの流れ制御があり、それらはネットワーク・
レイヤー自身の容量と基礎となるポイント・ツー・ポイ
ントの通信回線の容量に関連している。ノードが、その
容量がすでに満杯のためデータを受信できない場合は、
そのノードはＩＮＤ・ＦＬＯＷ・ＣＯＮＴＲＯＬ・ＯＮ
なるＰＤＵを隣接するノードへ送り、それらのノードが
更にデータを送ることを防止することができる。

【００４１】しかしながら、満杯のノードは依然とし
て、隣接のノードもまた同様の容量問題を抱えているか
も知れないために、同様の流れ制御通知を受信しなけれ
ばならないのでこれは充分ではない。このような通知を
無視すると、ノードの１つが正常な動作を再開したとき
に、データの紛失を起こす可能性がある。従って、この
問題を解決するため、流れ制御カウントが導入された。
ノードは隣接ノードがＩＮＤ・ＦＬＯＷ・ＣＯＮＴＲＯ
Ｌ・ＯＮのＰＤＵを送ると流れ制御カウントを増加させ
る。ノードは、ＩＮＤ・ＦＬＯＷ・ＣＯＮＴＲＯＬ・Ｏ
ＦＦのＰＤＵを受信すると流れ制御カウントを減少させ
る。流れ制御カウントがゼロに到達したときのみ、その
ノードは伝送を再開できる。

【００４２】

【表１】

【００４３】

【表２】

【００４４】

【表３】

【００４５】

【表４】

【００４６】

【表５】

【００４７】

【発明の効果】複数のタイプの物理的接続と複数のコン
ピュータに基づいているネットワークにおいて、ダイナ
ミックにノード（端末機）の識別子を割り当てることに
より、端末機が秩序良くネットワークに参加し、或いは
離脱でき、通信回線や端末機がネットワーク上で故障
し、実際上ネットワークを分離するといった状況にも対
処できる。更に本発明によれば、各応答がとりまとめら
れる前に、隣接したノードへ送られるだけなので明らか
にネットワーク上の通信量を節減する。

【図面の簡単な説明】

【図１】最小スパン・ツリー構造を有するネットワー
ク。

【図２】ネットワークへの接続に関するコンピュータ・
ワークステーションの処理レイヤーのダイアグラム。

【図３】図２の処理レイヤーに記憶された情報。

【符号の説明】

１０ ワークステーション ２０ アプリケーション ２２ ネットワーク制御レイヤー ２４ 共通通信レイヤー ３０ 経路表 ３２ とりまとめ表

───────────────────────────────────────────────────── フロントページの続き (72)発明者 グラハム デレック ウオリス イギリス国 ハンプシャ エス・オー３, ６ピー・ビーサウサンプトン ロックス・ ヘルス ラレー・ロード75

Claims (6)

【特許請求の範囲】
1. 【請求項１】 最小スパン・ツリー構造に接続された複
   数のノードから成るネットワークにおけるノードを形成
   するコンピュータにおいて、 上記コンピュータに接続された第１のノードからメッセ
   ージを受信し、 そのメッセージを識別する情報を記憶し、 上記コンピュータに接続された他のノードへそのメッセ
   ージを転送し、 上記他のノードからそのメッセージに対する応答を受信
   し、 上記他のノードから受信した応答と記憶した情報とを一
   緒にして単一の応答を生成し、 その単一の応答を上記第１のノードへ送信する、ステッ
   プから成るコンピュータの運用方法。
2. 【請求項２】 上記他のノードの１つが、そのノードと
   接続する回線の障害のため、遮断されていることを検出
   し、 その遮断されたノードからの応答が依然として未処理で
   あるメッセージがあるかどうか検査し、もしあれば、新
   しいネットワークの構成に対して適切な、そのノードか
   らの実際上の応答を生成するステップを含む請求項１に
   記載のコンピュータの運用方法。
3. 【請求項３】 上記メッセージがネットワークにおける
   固有の識別子を予約するための要求であり、遮断された
   ノードのために生成された実際上の応答が、その識別子
   が使用可能であることを確認するステップである請求項
   ２に記載のコンピュータの運用方法。
4. 【請求項４】 上記メッセージが、上記コンピュータに
   特定の行動を実行することを命令し、そのメッセージに
   対する応答を上記他のノードから受信した後、上記行動
   を実行するステップを含む請求項１に記載のコンピュー
   タの運用方法。
5. 【請求項５】 上記メッセージが、ネットワークからノ
   ードを削除することを命令するものである請求項４に記
   載のコンピュータの運用方法。
6. 【請求項６】 最小スパン・ツリー構造に接続された複
   数のノードから成るネットワークにおいて、 コンピュータに接続された第１のノードからメッセージ
   を受信する手段と、 そのメッセージを識別する情報を記憶する手段と、 上記コンピュータに接続された他のノードへメッセージ
   を転送する手段と、 上記他のノードからそのメッセージに対する応答を受信
   する手段と、 上記他のノードから受信した応答と記憶した情報とを一
   緒にして単一の応答を生成する手段と、 その応答を上記第１のノードへ送信する手段と、を備え
   たコンピュータ・ワークステーション。