JPH11161622A

JPH11161622A - 通信システム

Info

Publication number: JPH11161622A
Application number: JP10243659A
Authority: JP
Inventors: Richard C Waters; リチャード・シー・ウォーターズ; David Anderson; デビッド・アンダーソン
Original assignee: Mitsubishi Electric Information Technology Corp; Mitsubishi Electric Research Laboratories Inc
Current assignee: Mitsubishi Electric Information Technology Corp; Mitsubishi Electric Research Laboratories Inc
Priority date: 1997-08-29
Filing date: 1998-08-28
Publication date: 1999-06-18
Also published as: EP0909069A2; US6006254A; EP0909069A3

Abstract

(57)【要約】【課題】１グループのプロセスの間でオブジェクト状
態情報を高速で効率的に及び高い信頼性で通信するシス
テムを提供する。【解決手段】システムは、高速ではあるが損失が多く
従って信頼性の低い通信チャネルの使用と、１グループ
のプロセス及びそのグループと結合したサーバを組み合
わせて、マルチキャスティングにおいて失われたデータ
を提供する。中央サーバが、信頼性及び迅速な参加を支
援する一方で、ＵＤＰのマルチキャストのメッセージン
グを用いて、迅速な相互作用と小さい帯域幅が達成され
る。損失の多いチャネルを通じて示差メッセージが送ら
れ、いくつかの前の状態のうちのいずれかからどのよう
にオブジェクトの新しい状態を計算するかをコンパクト
に記述する。このような記述は、前の記述のうちのいく
つかが受け取られていなくとも解釈することができるの
で、明示の往復メッセージの修理の必要が非常に低減
し、帯域幅も保存される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、ネットワークシ
ステムに関し、より詳細には、それぞれのプロセスが実
行されているネットワークの１つのノードから他のノー
ドに、オブジェクトに関するデータを高速で高い信頼性
で転送する通信システムに関するものである。

【０００２】

【従来の技術】ネットワーク上の多数のユーザが、バー
チャル・リアリティのシーンでグラフィックのオブジェ
クト等のデータを共有しようと思い、そういったオブジ
ェクトにおける変更をそれぞれのノードにおいて実行さ
れているプロセスに通信しようと思う場合、１人のユー
ザがどのような変更を送信したいと思っているかを、そ
れぞれのユーザが素早く高い信頼性で知ることができる
ように、高速で信頼性の高い更新システムが必要とされ
る。例えば、分散共有メモリの共有データ−オブジェク
トモデルまたはプロセスがオブジェクトを共有する何か
同様の共有モデルを経由した１グループの非対称プロセ
ス相互作用があると仮定すれば、そしてさらに、このグ
ループがネットワークを通じて通信しているかもしれ
ず、地理的に離れていて、分散バーチャル環境に参加し
ているかもしれないと仮定すれば、目的は、次のことを
同時に達成する、ということである。すなわち、第１
に、ほぼリアルタイムの相互作用を達成するために、迅
速な相互作用を行ってオブジェクトの変更の通信速度を
最大にする。第２に、帯域幅を小さくして、使用する通
信帯域幅を最小にする。第３に、信頼性を高くして、オ
ブジェクトの変更が、低速のときもあるとしても結局
は、新しいユーザが通信グループに参加し他のすべての
プロセスが知っていることについて最新の情報を迅速に
得ることができるようにする。

【０００３】以下の説明において、双方向で取り組まれ
るべきデータは、いかなる与えられた瞬間においても共
有されているすべてのオブジェクトの組を記述するのに
用いられる世界モデル（world model）にある、と仮定
する。

【０００４】上記目的をどのように達成するかを考える
上で、オブジェクトが以下の多様な方法で変化すること
ができるということを考慮することが重要である。通信
の解決策は、この多様なもののすべての点において受け
入れられる程度に機能しなければならず、ある特定のア
プリケーションで一番適当な点が何であっても、その点
において特にうまく機能するべきである。

【０００５】一方の極端では、非常に頻繁に、例えば１
秒間に何十回もまたはそれ以上、変化するオブジェクト
がある。多くのアプリケーションについて、１つの変更
を記述するある特定の失われたメッセージを回復する、
ということはあまり重要ではない、というのも、その変
更が古いものになる前にそのようにすることはできない
だろうからである。むしろ、常に最新の情報を到着する
とすぐに利用することができる、ということに焦点を合
わせるべきである。さらに、無用の修理の試みに用いる
資源はできるだけ少なくするべきである。アプリケーシ
ョンに特有の知識を用いて、いくつかの失われたメッセ
ージが修理する値打ちがないと判断される、というの
も、それらは次の変更によって古いものになってしまっ
ているからである、ということが、オブジェクトをベー
スにした修理、と呼ばれる戦略にとって主要なことであ
る。

【０００６】他方の極端では、非常にめったに、例えば
数分または数時間ごとに１回しか、変化しないオブジェ
クトがある。この状態では、変化が起こるその正確な瞬
間は重要であるかもしれないし重要でないかもしれない
が、変化が起こったという事実は確かに重要である。そ
れぞれの個々の変更が通信される、ということが非常に
重要である。ある特定の変更について情報が失われる場
合には、次の変化が起こるよりもずっと前にそのことが
検出される、ということも重要である。この状態では、
失われたメッセージを検出するのに、ある種の積極的な
認識体系が必要である。

【０００７】この両者の中間にあるのは、適度の速度
で、例えば数秒ごとに１回程度、変化するオブジェクト
である。ここでは、修理することが重要であり、その修
理は比較的適時に行わなければならない。これは、この
多様なもののうちでうまく支援するのが特に困難な部分
である。幸いにも、この多様なもののうちの中間のもの
よりも、両極端の方をよく利用するアプリケーションが
多いと思われる。

【０００８】単一のオブジェクトは、しばらくの間迅速
に変化し、次に少しの間変化が低速であったりあるいは
全く変化しないかもしれない、ということが理解される
べきである。従って、汎用の方法では、前もってどのオ
ブジェクトがどの種の挙動を示すかを知っておく、とい
うことに依存することはできない。それどころか、起こ
っていることが何であろうともそれに動的に適応しなけ
ればならない。

【０００９】分散データベースおよび共有メモリ技術に
関して、上記目的に取り組む方法の１つは、標準の(sta
ndard)分散データベースまたは共有メモリ技術を用い
る、というものである。これらの方法においては、何に
もまして重要な目的は、１つの与えられた共有オブジェ
クトに２つのプロセスがアクセスするいかなる瞬間にお
いても、この２つのプロセスが常に同じ値を得る、とい
うことを保証する、ということである。この目的を満た
すために、ロックを用いて、各プロセスが誤った時にオ
ブジェクトにアクセスできないようにしなければならな
い。

【００１０】例えば、プロセスＰ１がオブジェクトＡを
修正したいと仮定する。これを行うためには、Ｐ１は以
下のことを行わなければならない。

【００１１】１．必要であれば、ロックが解除されるま
で待機し、他のプロセスがどれもＡをロックしていない
ということをチェックする。

【００１２】２．Ａをロックして、他のプロセスがＡに
アクセスできないようにする。

【００１３】３．グループ内の他のプロセスすべてに、
ロックが設定されていることを通知するメッセージを送
る。

【００１４】４．ロックを認識する戻りメッセージを他
のプロセスすべてから受け取るまで待機する。これによ
って、どれか他のプロセスがロックを最初に取っている
ということを発見する結果になるかもしれない、という
ことに注意されたい。その場合には、Ｐ１は上のステッ
プ１に戻らなければならない。

【００１５】５．Ａに所望の変更を行う。

【００１６】６．他のプロセスすべてに、その変更を指
定するメッセージを送る。

【００１７】７．変更のメッセージの受け取りを認識す
る戻りメッセージを他のプロセスすべてから受け取るま
で待機する。

【００１８】８．Ａにかけたロックを解除する。

【００１９】９．ロックが解除されたというメッセージ
を他のプロセスすべてに送る。

【００２０】このハンドシェーキングでは、帯域幅が浪
費され、相互作用が劇的に低速になる。Ａにロックを設
定したり解除したりするには、Ｐ１とグループ内の他の
プロセスの間で多数のメッセージが送られなければなら
ない。このように行ったり来たりの通信を行うと、Ｐ１
がＡを変更しようと判断してから、他のプロセスのうち
のどれかがその変更にアクセスできるようになる最も早
い待ち時間が、非常に増大する。それぞれのメッセージ
は完全に高い信頼性で送られねばならず、それによって
帯域幅の使用量と待ち時間がさらに増大する。

【００２１】最後に、待ち時間は、１グループ内のプロ
セス数が増大するにつれて、急激に増大する。その結
果、標準の分散データベースまたは共有メモリの方法
は、ある程度数の多いプロセスがほぼリアルタイムで相
互作用するのには用いることができない。

【００２２】適度の数のプロセスの間でもほぼリアルタ
イムの相互作用を達成するためには、１つの与えられた
共有オブジェクトに２つのプロセスがアクセスするとき
にはこの２つのプロセスが常に同じ値を得る、という、
別の状況では望ましい要求事項を、捨てなければならな
い。むしろ、プロセス間のロックなしで済ませねばなら
ず、オブジェクトに関連する値についてプロセス間で一
時的に不一致があっても許容しなければならない。特
に、プロセスＰ１がオブジェクトＡを修正する場合に
は、他のプロセスＰ２がこの変更について知るまでには
短い時間があり、その時間の間に、Ｐ１およびＰ２がＡ
にアクセスするときに得る値が異なってしまう。

【００２３】また、それぞれのオブジェクトが自分のプ
ロセスを有しておりそのプロセスのみがそのオブジェク
トを修正することができる、と仮定することが都合がよ
い。これによって、書き出しプログラム間の問題が回避
され、同時に行われる変更の間で調停する手段が一切必
要ないということが意味される。１つのアプリケーショ
ンが、１つの与えられたオブジェクトを変更することが
できるプロセスをいくつか有したい場合には、そのオブ
ジェクトの所有権をあるプロセスから他のプロセスに移
転することができる。または、単一のプロセスを、その
オブジェクトの変更の各要求の調停者として指定し、そ
ういった要求をベースにした変更を実際に行うプロセス
となるようにしてもよい。これは本質的に、多数のプロ
セスが直接オブジェクトを変更するということが行われ
る場合には起こるであろうことを正確に模倣している、
というのも、その場合には、何らかの調停方法がなけれ
ばならないからである。説明のために、以下では、いか
なる与えられた瞬間においても、それぞれのオブジェク
トは自身を変更することができるプロセスは１つしか有
していない、と仮定する。

【００２４】平等性の制約を緩めて、いくつかの方法、
すなわち、中央サーバシステム、分散対話型シミュレー
ション（ＤｉｓｔｒｉｂｕｔｅｄＩｎｔｅｒａｃｔｉ
ｖｅＳｉｍｕｌａｔｉｏｎ：ＤＩＳ）、および信頼性の
高いマルチキャスト、を用いて、上記目的の達成が図ら
れてきた。

【００２５】中央サーバの方法では、グループ内のそれ
ぞれのプロセスに、自らが行う変更を中央サーバに通信
させ、中央サーバは他のプロセスに通知する。この方法
では、各プロセスが知る情報をそのプロセスにできるだ
け接近して保つ、ということがうまく行われる。

【００２６】この方法ではまた、迅速な参加をさせる、
ということもうまく行われる、というのも、新しいプロ
セスは中央サーバから自らが知っているものと考えられ
ているすべてのことについての迅速なダウンロードを受
け取ることができるからである。さらに、ＴＣＰ等の信
頼性の高いプロトコルを用いてメッセージをサーバへお
よびサーバから送ることによって、中央サーバの方法
は、情報の信頼性の高い到着を容易に保証することがで
きる。

【００２７】しかし、この中央サーバの方法には、２つ
の問題がある。第１に、相互作用の速度がかなり制限さ
れる、というのも、すべてのメッセージは、まず中央サ
ーバに行き、次にグループ内の他のプロセスに行かなけ
ればならないからである。この方法では、メッセージを
あるプロセスから他のプロセスに直接送るのと比較し
て、メッセージの伝達時間(flight time)が長くなり、
サーバが入メッセージを解釈し、それに対してどうする
べきかを判断し、出メッセージを生成するのに必要な時
間も余分にかかる。

【００２８】第２に、グループ内の他のプロセスだけで
なく中央サーバにもメッセージを送らなければならない
ということのために、必要な帯域幅がいくぶん増大す
る。

【００２９】分散対話型シミュレーション基準、ＤＩ
Ｓ、Standard for Information Technology, Protocols
for Distributed Interactive Simulation, DIS ANSI/
IEEE Standard 1278-1993, American National Standar
ds Institute, 1993に適合するシステムは、ＵＤＰプロ
トコルを用いて効率的にメッセージをマルチキャストす
るものを用いて、オブジェクトの変更に関するメッセー
ジをあるプロセスから他のプロセスに直接に送る。実際
には、初期のＤＩＳシステムは、メッセージをあるサブ
ネットワークから他のサブネットワークに転送する特別
な橋渡しをするハードウェア／ソフトウェアを有する専
用サブネットワーク内での同報を用いているが、これは
本質的に、マルチキャストが可能なネットワークのルー
タ(routers)が行うことである。

【００３０】ＤＩＳの方法の主な長所は、できる限り最
大の速度でプロセス間で情報を通信する、ということで
ある。さらに、マルチキャストであれば、多数のポイン
トツーポイント接続よりも、用いるシステムの帯域幅が
かなり小さい。しかし、ＵＤＰメッセージの到着を保証
するのもではない。従ってＤＩＳは、１つのプロセスが
行う変更が常に、１つの与えられた他のプロセスによっ
て知られるようになる、ということを保証するものでは
ない。

【００３１】この信頼性の問題に対処するために、ＤＩ
Ｓは２つのことを行う。第１に、送られるそれぞれのメ
ッセージは、１つのオブジェクトに関するフルの情報を
含んでおり、そのオブジェクトに関する前のメッセージ
が失われている場合であっても、常にすべての情報を理
解することができる。第２に、ＤＩＳシステムは、それ
ぞれのオブジェクトの現在の状態を指定する「キープア
ライブ」メッセージを、頻繁に、通常５秒ごとに１回、
送出する。これは、失われた情報が通常５〜１０秒内に
修理される、ということを意味している。これはまた、
新しいプロセスは、知らなければならないすべてのこと
を５−１０秒内に知らされる、ということも意味してい
る。

【００３２】上記のことにもかかわらず、ＤＩＳにはま
だ４つの重要な問題が残っている。第１に、示差メッセ
ージを用いることはできず、従ってそれぞれのメッセー
ジはオブジェクトをフルに記述しなければならない、と
いう事実のために、多くの帯域幅が浪費される、という
のも、あるオブジェクトのごく一部のみが変化している
場合であっても、そのオブジェクト全体の記述が頻繁に
送られているからである。

【００３３】第２に、キープアライブのメッセージは多
くの帯域幅を浪費する、というのも、あるオブジェクト
が全く変化していない場合であっても、そのオブジェク
ト全体を記述するメッセージが繰り返し送られるからで
ある。

【００３４】第３に、キープアライブのメッセージによ
って結果として修理がされることになるが、速い修理が
されるようにするものではない。従って、そのグループ
内の各プロセスは、それらが共有しているデータについ
て信じていることについて(in what they believe abou
t the data they share)同期からかなり外れ得、ほぼリ
アルタイムの相互作用は損なわれる。

【００３５】第４に、迅速に参加することができない、
というのも、新しいプロセスが、他のプロセスが知って
いることを知るには、５−１０秒かかるからである。

【００３６】ＤＩＳの優れた部分は、中央サーバのプロ
セスが全くなく、いかなるプロセスも他のプロセスがど
んな情報を受け取っているかを理解する必要がない、と
いうことである。それどころか、すべてのプロセスは、
他のプロセスを知らずに猛烈に進む(forge ahead)だけ
である。失われるメッセージがほとんどない場合には、
かなりのさらなる帯域幅を犠牲にしてではあるが、物事
は非常にうまく行く。かなりの数のメッセージが失われ
る場合にも、リアルタイムの相互作用が低減はするが、
帯域幅の使用量が増大することなく、物事はなおもうま
く行く。

【００３７】関連する従来技術のうちの最後のものは、
信頼性の高いマルチキャストのプロトコルについての研
究である。この技術において、主要な目的は、マルチキ
ャストのメッセージを用いて帯域幅の小さい動作を達成
することであるが、信頼性を保証するハンドシェーキン
グを組み込むことである。これを行うには、２つの基本
的な方法がある。すなわち、肯定応答のメッセージ、Ａ
ＣＫを用いるもの、または、否定応答のメッセージ、Ｎ
ＡＫを用いるもの、である。

【００３８】ＡＣＫをベースにした方法においては、そ
れぞれの受け取り手が、自らに送られたメッセージの受
け取りの明示のＡＣＫを送る。ＴＣＰ等のプロトコルに
おいては、これによって、何を誰に再送しなければなら
ないかを送り手が正確に知ることができる。しかし、こ
の問題点は、「ＡＣＫの爆発(explosion)」と呼ばれる
ものである。

【００３９】プロセスＰがＮ個の他のプロセスにメッセ
ージを送っていると仮定する。Ｐが１つメッセージを送
るごとに、Ｎ個のＡＣＫが生成される。これによってか
なりの帯域幅が使用され、Ｐは、１つメッセージを送出
するごとに、処理しなければならないメッセージをＮ個
受け取ることになる。このグループ全体では、データを
保持するメッセージの個数のＮ倍のＡＣＫメッセージが
ある、ということに注意されたい。その結果、グループ
が大きくなってくると、ＡＣＫメッセージがすぐにすべ
ての通信を支配してしまう。ＡＣＫ自体がマルチキャス
トによって送られる場合には、すべてのプロセスがすべ
てのＡＣＫを処理しなければならない。ＡＣＫが様々な
プロセスから直接送信元のプロセスに送り返される場合
には、これは、Ｎの２乗の１対１のチャネルが開いてい
ることを意味しており、ＡＣＫを通信するのに必要な帯
域幅は増大する。

【００４０】ＮＡＫをベースにした方法においては、メ
ッセージが失われたときのみに制御メッセージが送られ
る。具体的には、プロセスＰ２が、他のプロセスＰから
のメッセージＭを受け取らなかったということに気づい
た場合、プロセスＰ２は、そのメッセージの再送を要求
するＮＡＫを送る。この方法の利点は、メッセージが受
け取られる場合には、ＡＣＫを送って帯域幅が浪費され
ることがない、ということである。しかし、それでもま
だ重要な問題がある。

【００４１】第１に、Ｐ２がＭを受け取らなかったとい
うことを知る主要な方法は、Ｍの後にＰが送る異なった
メッセージを受け取る、ということである。ＡＣＫを用
いる場合と比較すると、本方法では、Ｍの損失を検出し
従って修理することができる時間が遅れる。この問題
は、ＰがＭの後に何らメッセージを送らない場合には、
特に深刻となる。その場合、Ｐ２はＭが失われたという
ことにずっと気づかないかもしれない。この問題に対処
するために、各プロセスが受け取っておくべきであるも
のを指定するような、ある種のメッセージが送られなけ
ればならない。純粋なＮＡＫをベースにした方法は、そ
れぞれのプロセスが規則正しくメッセージを送り続ける
場合にのみ可能である。

【００４２】第２に、ＡＣＫと同様に、ＮＡＫ自体がマ
ルチキャストによって送られる場合には、すべてのプロ
セスがすべてのＮＡＫを処理しなければならない。ＮＡ
Ｋが様々なプロセスから直接送信元のプロセスに送り戻
される場合には、これは、Ｎの２乗の１対１のチャネル
が開いていることを意味しており、ＮＡＫを通信するの
に必要な帯域幅は増大する。いずれにせよ、あるメッセ
ージが全く失われた場合に送信元に集中するＮ個のＮＡ
Ｋは、「ＮＡＫの爆縮(implosion)」と呼ばれている。
このトラヒックが存在することによって、通信をそもそ
も失敗させた原因がなんにせよ、その原因以外にさらに
通信を妨げ得る困難が送信元において引き起こされる。

【００４３】

【発明が解決しようとする課題】このような視野から、
信頼性の高いマルチキャストのプロトコルには、いくつ
か重大な問題がある。第１に、これらの大部分は、ほぼ
リアルタイムの相互作用や迅速な参加については、支援
を図ろうともしておらず、その代わりに、信頼性および
帯域幅が小さいことに焦点を当てている。

【００４４】第２に、これらの多くは、到着の順番等、
信頼性の特徴を保証するのにかなりの資源を費やしてい
るが、そういったものは、上述の問題の解決には有用で
はない。

【００４５】第３に、ＡＣＫを用いる場合には、それに
よって、失われているメッセージがほとんどない場合で
あっても、かなりの量の帯域幅が用いられてしまう。か
なりの数のメッセージが失われている場合には、失われ
たメッセージを再送しなければならないために、帯域幅
の使用量は更に増す。ＮＡＫが用いられる場合には、物
事がうまく行っている場合には、帯域幅の使用量はＡＣ
Ｋを用いる場合よりもずっと小さいが、メッセージが失
われるにつれて、メッセージの再送に加えて多くのＮＡ
Ｋを送り始めなければならないために、帯域幅の使用量
の増加の勾配はずっと急である。

【００４６】どちらの場合においても、メッセージが失
われている場合にはより多くの帯域幅を必要とする、と
いう基本的な挙動は、不利である、というのも、帯域幅
が制限されるということは、メッセージが失われる主な
原因の１つだからである。特に、ＮＡＫをベースにした
方法においては、このことが、最初に起こった問題が次
々と問題を呼ぶ悪循環を引き起こし得る。

【００４７】第４に、これが最も大きい問題かもしれな
いが、マルチキャストのメッセージ自体の信頼性を直接
高くしようと努力しても、上述の問題の核心をつかんだ
ことにはならない。例えば、プロセスＰ１が時間Ｔ１に
おいてオブジェクトＡを変更し、この変更を記述するメ
ッセージＭを送ると仮定する。ＮＡＫをベースにした方
法において、Ｔ１よりも後のある時Ｔ２において、プロ
セスＰ２がＭを受け取っていないことを発見すると仮定
する。するとＰ２は、Ｍの再送信を要求するＮＡＫを送
る。これは仕方がないことではあるが、Ｐ２が本当に得
たいのは、Ｍではなく、Ｔ２におけるＡの状態である。
すなわち、所望される信頼性とは、必ずしもそれぞれの
メッセージを受け取ることではなく、むしろＡについて
可能な限り最新の情報を常に得る、ということである。

【００４８】

【課題を解決するための手段】上述の問題の基本的な解
決策は、中央サーバを用いて、信頼性および迅速な参加
を支援する一方で、ＵＤＰマルチキャストメッセージン
グを用いて、迅速な相互作用と小さい帯域幅が達成され
る。示差メッセージを用いて、さらに小さい帯域幅が達
成され、オブジェクトをベースにした修理を用いて、不
必要な修理が回避される。

【００４９】具体的には、１グループのプロセスの間で
オブジェクト状態情報を高速で効率的におよび高い信頼
性で通信するシステムは、高速ではあるが損失が多く従
って信頼性の低いマルチキャストのリンクと、１グルー
プのプロセスおよびそれらのプロセスと結合したサーバ
を組み合わせて、マルチキャスティングにおいて失われ
たデータを提供する。一実施例において、中央サーバが
信頼性および迅速な参加を支援する一方で、ＵＤＰのマ
ルチキャストのメッセージングを用いて迅速な相互作用
と小さい帯域幅が達成される。示差メッセージを用いて
変更および失われたデータの検出ができ、示差メッセー
ジにおいては、いくつか前の状態のうちのいずれかから
どのようにオブジェクトの新しい状態を計算するかを記
述する、示差記述が作り出され、前の記述のうちのいく
つかが受け取られていなくとも、記述を解釈することが
できるようになっており、さらに小さい帯域幅が達成さ
れる。一実施例において、中央サーバが送出する、いつ
情報が失われたかを高い信頼性で知るためのメッセージ
によって、キープアライブのメッセージが必要ないよう
にしている。

【００５０】本システムの一実施例において、いつ情報
が失われたかを高い信頼性で知るために、サーバは、そ
れぞれのプロセスが受け取っておくべきであるものを指
定するメッセージを送る。

【００５１】キープアライブのメッセージは、適時に修
理したり真に迅速な参加を可能にすることなく帯域幅を
浪費するので、避けられる。予想される状況では、オブ
ジェクトは何度も変化するがそれぞれは小さな変更に過
ぎないので、オブジェクトのフルの状態ではなく変更自
体のみを記述する示差オブジェクト記述を用いることに
よって、帯域幅は大幅に減少する。

【００５２】最も簡単な示差オブジェクト記述では、オ
ブジェクトの新しい状態を前の状態からどのように計算
するかを指定する。この種の記述を用いる場合には、プ
ロセスは、前の記述を受け取っていなければ示差記述Ｄ
を解釈することができない。しかし、いくつか前の状態
のうちのどれかからオブジェクトの新しい状態を計算す
る示差記述を作り出すことができる。もしこれができる
ならば、直前の記述が受け取られていなくとも、記述Ｄ
を解釈することができる。

【００５３】帯域幅は、信頼性が高いレベルで導入され
て、低レベルでの強い力(brute force)を用いるよりも
その特定のドメインの制約を最大限に利用することがで
きる場合に、最も低減することができる。

【００５４】特に、信頼性は、各プロセスが実際にすべ
ての低レベルのメッセージを受け取ることを保証するよ
うようにではなく、各プロセスがそれぞれのオブジェク
トについて最新の状態の値で終わることを保証するよう
に追加される。例えば、失われてはいるが次のオブジェ
クト状態メッセージによってすぐに古いものになるオブ
ジェクト状態メッセージは、再送される必要がなく、従
って再送されるべきではない。

【００５５】大域共有環境(global shared environmen
t)において高い信頼性で相互作用するために、オブジェ
クトはグローバリ・ユニーク・ＩＤ(Globally Unique I
Ds)すなわちＧＵＩＤによって識別される。空間におい
ても時間においても真に唯一であるためには、ＧＵＩＤ
は例えば１００またはそれより多くのビットを有しなけ
ればならない。

【００５６】あいにく、これに対抗することを何もしな
ければ、このようなＧＵＩＤを用いるとメッセージに多
くの帯域幅を使い尽くし得る。本発明においては、ＧＵ
ＩＤは、１つの与えられたメッセージにおいて用いられ
るＧＵＩＤの間で共用するビットが多くなるように割り
当てられる。従って、ＧＵＩＤは、コンパクトで圧縮さ
れた形式で表すことができる。

【００５７】一実施例において、コンパクトな示差メッ
セージは、オブジェクトの現在の状態を、いくつかの前
の状態のうちのどれかからの最新版として記述する。こ
れによって、システム内でメッセージは失われたり順番
が狂って到着したりしてもよくなり、システム内での待
ち時間が低減する。これによって、順番が狂ったメッセ
ージが到着したり失われたメッセージが修理または再送
されるのを待機する必要がなく、メッセージは到着する
とすぐに解釈され用いられることができる。また、これ
によって、メッセージが失われた場合には、失われたメ
ッセージを修理する必要さえない粗い挙動も許される、
というのも、メッセージレベルではなくオブジェクトを
ベースにして修理をすることができるからである。

【００５８】この技術は、メッセージが順番に到着する
ような信頼性の高い通信チャネルについて用いても利益
にならない、ということに注意されたい。そのような状
況では、普通のデルタで十分である。他方で、本システ
ムでは、メッセージが失われたり順番が狂って到着する
かもしれない場合に価値がある冗長性がいくらか導入さ
れる。

【００５９】本システムにおいては、それぞれのサイク
ルで変化したビットマスクまたは語の論理和をとること
によって、変化したものを効率的に計算する技術が用い
られている。１つまたはそれより多いフィールドが繰り
返し変化している場合、これは普通であるが、この場合
には、我々の符号化では、多くの前の状態に関してさか
のぼるコストは、直前の状態までのデルタを記述するコ
ストと比較して、余分にかかることはない。

【００６０】このようにＩＳＴＰにおいて示差メッセー
ジを用いることにおいて、圧縮性を増大するために、メ
ッセージは、同じメッセージにおいてＧＵＩＤ間で多く
の冗長性がみられるように配置される。

【００６１】以下では、本システムのベースである、領
域をベースにした通信への全体的な手引きを説明する。
１つまたはそれより多いノードが、制御するオブジェク
トについての情報を更新し、１つまたはそれより多いノ
ードがそういった更新を受け取る必要がある、ネットワ
ーク化したコンピュータシステムにおいては、本システ
ムは、そういった更新を、以前の技術よりも速く小さな
帯域幅で送るという方法で、高い信頼性で通信する。

【００６２】重要な点に関しては、マルチキャストで、
グループをベースにした、ピア間での通信であって、サ
ーバがその通信を聞いている。この中央サーバは信頼性
の中心であって、マルチキャストは、待ち時間が短く帯
域幅の小さい相互作用に用いられる。

【００６３】メッセージレベルの修理と対立するものと
してのオブジェクトをベースにした信頼性によって、不
要な修理が回避される。修理が必要な場合、失われた情
報よりも最新の情報が今では入手可能なときには、それ
を代わりに提供することができる。

【００６４】本システムにおいて、除去されたオブジェ
クトについて参加者が覚えておかなければならない情報
量は、遅すぎるメッセージをすべて自動的に拒絶し、オ
ブジェクトをベースにした修理を用いていかなる失われ
た情報も回復することによって、制限されている。

【００６５】セッションへの入力は、すべての現在のセ
ッション状態の即時のダウンロードを、進行中の更新が
送られているマルチキャストのグループに新しいクライ
エントを参加させることと組み合わせることによって、
できるだけ迅速に行われる。このダウンロードには、す
べての最近除去されたオブジェクトについての情報が含
まれているので、新しいクライエントは、そういったオ
ブジェクトについての後から到着してくるマルチキャス
トの更新に惑わされることはない。

【００６６】サーバは、そのグループが用いるマルチキ
ャストのアドレスを選択する責任があり、干渉を回避し
たり態度の悪い参加者を駆逐するためにチャネルを次々
と替えることができる。これは、コードレス電話が干渉
を回避するためにチャネルを選択する機構を拡張したも
のである。

【００６７】本発明のこれらのおよび他の特徴は、図面
と共に、詳細な説明を考慮すると、よりよく理解されよ
う。

【００６８】

【発明の実施の形態】実施の形態１．次に図１を参照し
て、ネットワーク１６につながれた一連のコンピュータ
１０、１２、１４上で、ネットワーク化された一連のプ
ロセスが実行されており、一実施例において、プロセス
は、モニタ２０、２２、２４に表示されたバーチャル・
リアリティーのシーン１８を含む。それぞれのコンピュ
ータ１０、１２、１４のユーザＡ、Ｂ、Ｃは、バーチャ
ル・リアリティーのシーンを作り出すのに参加してお
り、それぞれのユーザ、従ってそれぞれのコンピュータ
は、関連する世界モデル２６、２８、３０を有してい
る。それぞれの世界モデルは、いくつかの部分に分割さ
れていて、それらについてはそれぞれのユーザに責任が
ある。

【００６９】わかるように、それぞれの世界モデルは、
従って、セクションＡ、Ｂ、Ｃに分割されており、ユー
ザＡは、グラフィック要素、この場合は犬３２、を付け
加えることによって、このバーチャル・リアリティーの
シーンを修正しようとしている。変更３４は、２８’お
よび３０’で示すように、それぞれのユーザの世界モデ
ルに送信されることになる。

【００７０】本実施の形態は、多数のユーザによるバー
チャル・リアリティーのシーンの創作の点から説明する
ということが理解されようが、多数のユーザの間ででの
いかなる修正または変更されることになるデータの送信
も、好ましくは、信頼性の高い、待ち時間の短い、帯域
幅の小さい送信が必要である。

【００７１】このような送信は、これまで、データおよ
び／またはその変更をサーバに送信してそれをすべての
ユーザに再送信することによって、試みられてきた。こ
れは、中央サーバシステムと呼ばれ、図２を参照して後
に説明する。

【００７２】このデータおよび／またはその変更を送信
する第２の一般的な方法は、同報またはマルチキャスト
のネットワーキングの利用によるものであり、データま
たは変更は直接それぞれのユーザに通信される。前述の
分散対話型シミュレーション基準、ＤＩＳは、この方法
を用いるプロトコルであり、図３を参照して後に説明す
る。

【００７３】次に図２を参照して、ユーザによって指定
された世界モデル４０への変更が、サーバ４２に送信さ
れ、サーバ４２は単に変更されたデータまたは変更をネ
ットワーク上の様々なユーザに送信する。前述したよう
に、このような方法の主な問題は、変更をサーバを通じ
てそれぞれのユーザに送るのに必要な時間が増大すると
いうことと、このようなシステムを多数のユーザに大規
模化する(scaling)とサーバが隘路を作ってしまうとい
うことである。

【００７４】次に図３を参照して、世界モデル４０への
変更は、直接それぞれのコンピュータ１０、１２、１４
とピアツーピアの方法で通信され、適切なアドレスに申
し込む(subscribing)すべてのプロセスが新しいデータ
を受け取る。これまでは、図３に説明したタイプのマル
チキャストシステムは、データへの変更を示す示差メッ
セージではなく、オブジェクト全体を送信することに依
存してきた、ということに注意されたい。

【００７５】次に図４を参照して、本システムにおい
て、ユーザＡが自らの世界モデル２６を変更したいと仮
定すると、この変更は同時に、サーバ５０に、そして直
接コンピュータ１２、１４に送信される。この送信は、
いかなる従来技術の同報またはマルチキャストのプロト
コルの形式をとってもよい。送信されるのは、ユーザＡ
がユーザＢ、Ｃに有してもらいたいと思う変更されたデ
ータである。上述のとおり、マルチキャスティングでは
一般的に、送信は比較的適時であるが、データが失われ
たりデータの順番が狂う結果になり得る。

【００７６】それぞれのコンピュータ１０、１２、１４
には、未着データ検出装置５２がつながれており、２つ
の機能を果たす。第１の機能は、ユーザからのデータを
サーバが受け取っていない場合を検出する、というもの
である。第２の機能は、与えられたコンピュータに保存
されたデータが、他のユーザが指定した変更を含んでい
ない場合を検出する、というものである。

【００７７】次に図５を参照して、未着データ検出装置
５２の２つの機能を説明する。サーバ５０からそれぞれ
のコンピュータに、前回そのようなオブジェクト状態要
約を送ってからサーバが処理した一連のオブジェクト状
態の更新を記述するオブジェクト状態要約メッセージ５
８が送られる。この場合、ユーザＡは、データＡ’にお
ける変更を指定している。サーバは、いったんこの変更
を受け取ると、この変更を自らの次のオブジェクト状態
要約メッセージに含める。オブジェクト状態要約のこの
予想される部分がない場合には、未着データ検出装置５
２’が、更新が失われたと判定することができる。一実
施例において、これは次に、５６で示すように、示差メ
ッセージを直接サーバに送ることによって修理される。

【００７８】ユーザＢ、Ｃに関して、ユーザＡからユー
ザＢ、Ｃに直接送られたメッセージが失われている場合
には、サーバ５０からの要約５８が、失われたデータの
存在をユーザＢ、Ｃに知らせる。失われたメッセージに
おいて記述されたデータのバージョンがコンピュータ１
２または１４にないと判定して、サーバ５０には、その
更新が失われたオブジェクトに関連する最新のデータを
供給せよという要求６０が行われる。

【００７９】その結果、本システムは、第１にそれぞれ
のユーザに直接変更を同報し、次にその変更を提供され
た中央サーバを利用することによって失われたメッセー
ジが修理できるようにすることによって、信頼性が高く
適時のデータ変更を多くのネットワーク化されたユーザ
に送信することができる。

【００８０】一般的に、オブジェクトはオブジェクト状
態を含む多数のフィールドを有しており、普通の場合に
は、与えられたある時間には、１つまたは少数のフィー
ルドしか変化しない、ということが理解されよう。しか
し、今述べた様々な困難のために、図３と共に言及した
ＤＩＳプロトコルでは、変化の性質にかかわらず、常に
完全なオブジェクト状態を送っている。これは、簡単だ
という長所があるが、多くのアプリケーションにおいて
は、順番が狂ったメッセージを到着したときに処理する
ことができるようにすることによって、帯域幅を温存す
ると共に変更の処理のスピードアップも図ることができ
るような方法で、オブジェクト変更を符号化することが
できるのが好ましい、ということは明らかである。図４
および５は、中央サーバをどのように利用して本システ
ムが高い信頼性で動作するかを要約している。図６ない
し図１１では、オブジェクトの更新を符号化する体系の
詳細を説明する。

【００８１】この図５に示すネットワークのアーキテク
チャを、示差メッセージおよびオブジェクトをベースに
した修理と結びつけることによって、さらなる利点が得
られる。データへの変更は、そのオブジェクトのどのフ
ィールドが変更されたかを記述するメッセージの形で送
信してもよい、ということが理解されよう。しかし、普
通のオブジェクトのデルタに行う改良は、マルチをベー
スにした示差メッセージング技術を利用することによっ
て達成することができ、その技術においては、それぞれ
のメッセージに十分な冗長情報が含まれており、間にあ
る更新がいくつか失われてしまっている場合であっても
完全なオブジェクト状態を再構成することができるよう
になっている。

【００８２】次に図６を参照して、従来技術において、
あるオブジェクトが、それぞれの段階においてオブジェ
クト変更のフィールドを１つまたはそれより多く有して
おり、それぞれのメッセージが直前の段階からの状態の
変更のみを記述していると仮定すると、単一のメッセー
ジＭ２が失われると、オブジェクトの状態全体を再構成
することができなくなる。この、最も簡単な場合の示差
メッセージングは、シングルベースの示差メッセージと
呼ばれる。シングルベースの示差メッセージが順番が狂
って到着する場合には、それぞれのメッセージはそれよ
り前のメッセージがすべて処理されるまで処理できない
ので、早く到着したものを到着したときに処理するとい
う機会は失われてしまう、ということに注意されたい。
シングルベースの示差メッセージは、ＴＣＰ等の信頼性
の高いネットワークのプロトコルを背景にしているとき
にのみ有用である。

【００８３】次に図７を参照して、単一のメッセージの
損失は何ら問題を起こさない、デュアルベースの示差メ
ッセージを説明する。例えば、Ｍ２が失われているまた
は遅れている場合であっても、Ｍ３は処理することがで
きる、というのも、Ｍ３は、Ｍ１における状態とＭ２に
おける状態の両方に関してその段階におけるそのオブジ
ェクトの状態を記述しているからである。

【００８４】次に図８を参照して、Ｆ１ないしＦ６の６
つのフィールドを有するオブジェクトが時間Ｔ１ないし
Ｔ５における一連の変更を受けている、ということがわ
かる。この表では、それぞれの時間段階におけるこのオ
ブジェクトの完全な状態がわかる。

【００８５】次に図９を参照して、これは、図８のオブ
ジェクトの、時間Ｔ４における、完全な記述である。そ
れぞれのフィールドの値は指定されている。

【００８６】次に図１０を参照して、これは、図８のオ
ブジェクトの、時間Ｔ４における、時間Ｔ３に関する、
シングルベースの示差記述である。この場合、新しい状
態は、フィールドＦ３が値Ｃに設定されていること以外
は、直前の状態である。

【００８７】次に図１１を参照して、図８のオブジェク
トの示差状態記述を示し、これは、時間Ｔ４における、
これより前の時間Ｔ１、Ｔ２、またはＴ３のうちのどれ
かに関する状態を記述している。これらの前の３つの状
態のうちのいずれかを記述するメッセージを受け取った
いかなるコンピュータも、この記述を適切に復号するこ
とができる。この記述のこういった受け取り手は、それ
によって、そのコンピュータにおいて前の状態としてど
れがあろうとも、そこからスタートして、フィールドＦ
３をＣに設定し、フィールドＦ５をＨに設定することに
よって、新しい状態に達する、と教えられる。この示差
状態記述は、図９のフルの状態記述よりもはるかにコン
パクトであり、信頼性の低いネットワークでの送信に
は、図１０のシングルベースの示差記述よりもはるかに
有用である、ということが理解されよう。

【００８８】一実施例においておよびより詳細には、参
加者は、サーバＳおよびｎ個の通信するプロセスＰ１・
・・Ｐｎである。本システムが用いるメッセージングの
プロトコルは、本明細書においては、対話型共有転送プ
ロトコル（ＩｎｔｅｒａｃｔｉｖｅＳｈａｒｉｎｇ
ＴｒａｎｓｆｅｒＰｒｏｔｏｃｏｌ：ＩＳＴＰ）、と
呼ぶことに注意されたい。それぞれのプロセスＰｊは、
多数のオブジェクトを所有しており、Ｐｊがそれらのオ
ブジェクトを変更するときはいつでも、そのオブジェク
トの記述を送出する。

【００８９】それぞれのプロセスは、他のプロセスか
ら、他のプロセスが所有しているオブジェクトについて
のメッセージを受け取る。

【００９０】それぞれのプロセスＰｊは、サーバＳとの
１対１のＴＣＰ接続を有している。これは、制御情報を
高い信頼性で通信するために用いられる。さらに、マル
チキャスト通信グループ内のプロセスＰｊは、Ｓが選択
したアドレスを用いてマルチキャスト通信に参加する。

【００９１】この解決策には、いくつか重要な部分があ
る。すなわち、オブジェクト状態に関する情報の通信方
法、マルチキャストのメッセージの送出および受け取り
方法、各プロセスが知っておくべきものを知る方法、メ
ッセージ損失の修理方法、各プロセスの通信グループへ
の参加方法、各プロセスの通信グループからの退出方
法、である。

【００９２】これらの各部分のそれぞれを、以下に別個
に説明する。説明の一部として、以下の３種類のメッセ
ージを用いる。１．オブジェクト状態 − オブジェクトの状態を記述２．オブジェクト状態要約 − 各プロセスが知ってお
くべきものを指定３．場所入力 − 新しいプロセスがグループに参加す
るときの各種セットアップ

【００９３】ａ．オブジェクト状態に関する情報の通信
方法１つまたはそれより多いオブジェクトの状態は、オブジ
ェクト状態メッセージ内で通信される。オブジェクト状
態メッセージのフォーマットは、以下のとおりである。
オブジェクト状態メッセージフィールド：Ｍｅｓｓａｇ
ｅＴｙｐｅＩＤ：１６ビット − 値１は、これがオブ
ジェクト状態メッセージであることを示す。

【００９４】ＳｅｎｄｅｒＩＤ：３２ビット − 送り
手のｓｐＣｏｍを識別する圧縮ＧＵＩＤ。

【００９５】ＳｅｎｄＴｉｍｅ：３２ビット − １週
間を法とする、ミリ秒での送られる時間メッセージ。

【００９６】ＮｕｍｂｅｒＯｆＧＵＩＤＰｒｅｆｉｘｅ
ｓ：１６ビット − ＧＵＩＤＴａｂｌｅにおける接頭
部Ｇの数。

【００９７】ＮｕｍｂｅｒＯｆＤｅｓｃｒｉｐｔｉｏｎ
ｓ：１６ビット − メッセージの本体(body)の記述Ｄ
の数。

【００９８】ＧＵＩＤＴａｂｌｅ：Ｇ個のＧＵＩＤＰｒ
ｅｆｉｘ入力 − それぞれ９６ビット。

【００９９】ＴａｂｌｅＥｎｔｒｙＩｎｄｅｘ：１６ビ
ット − 圧縮ＧＵＩＤに用いる。

【０１００】ＧＵＩＤＰｒｅｆｉｘ：８０ビット −
メッセージにおいて多くのＧＵＩＤに潜在的に共有され
ている接頭部。

【０１０１】Ｄｅｓｃｒｉｐｔｉｏｎｓ：Ｄ個のオブジ
ェクト記述 − 長さはまちまち。

【０１０２】それぞれのＩＳＴＰメッセージは、与えら
れたメッセージがどの種類のＩＳＴＰメッセージかを指
定する１６ビットのメッセージのタイプで始まる。さら
なるタイプを用いてＩＳＴＰプロトコルの拡張バージョ
ンを支援することができるように、十分なビット数が設
けられている。

【０１０３】ＳｅｎｄｅｒＩＤは、そのメッセージの送
り手を識別する、ｓｐＣｏｍオブジェクト（以下参照）
のＧＵＩＤ（以下参照）である。すべてのＩＳＴＰメッ
セージは、自らがどんな通信接続上で受け取られたかを
知る必要なしに十分に解釈できるという特性を有してい
る、ということに注意されたい。

【０１０４】ＳｅｎｄＴｉｍｅは、１週間、すなわち６
０４，８００，０００ミリ秒、を法とする、そのメッセ
ージが送られたときのミリ秒での局所時間である。Ｎｕ
ｍｂｅｒＯｆＧＵＩＤＰｒｅｆｉｘｅｓは、ＧＵＩＤＴ
ａｂｌｅにおける入力数を指定する。

【０１０５】ＮｕｍｂｅｒＯｆＤｅｓｃｒｉｐｔｉｏｎ
ｓは、記述されるオブジェクトの数を指定する。

【０１０６】ＧＵＩＤＴａｂｌｅは、そのメッセージの
残りの部分における、ＳｅｎｄｅｒＩＤを含む、ＧＵＩ
Ｄのコンパクトな表示ができる(allow for)入力を含
む。

【０１０７】Ｄｅｓｃｒｉｐｔｉｏｎｓは、絶対または
相対のどちらかの記述を用いてオブジェクトの現在の状
態を記述する（以下参照）。

【０１０８】オブジェクト記述を理解するためには、ま
ず、ＩＳＴＰにおけるオブジェクトについての以下の事
実を理解しなければならない。様々なアプリケーション
は、多くの種類のオブジェクトを用いると思われる。特
に、新しい種類のオブジェクトを規定することができる
ようになっている。しかし、ＩＳＴＰにとって重要なオ
ブジェクトのタイプはほんの少しである。ｓｐオブジェ
クトとｓｐＣｌａｓｓオブジェクトは、最も重要なもの
のうちの２つである。

【０１０９】ｂ．ＧＵＩＤＩＳＴＰにおけるすべてのオブジェクトは、グローバリ
・ユニーク・ＩＤすなわちＧＵＩＤによって識別され
る。ＩＳＴＰは、空間においても時間においても唯一で
ある、９６ビット、すなわち１２バイト、３語のＧＵＩ
Ｄを用いている。これは、ＩＰｖ６の下では１９２ビッ
トに拡張することができる。ＧＵＩＤは、以下の２つの
部分から成っている。

【０１１０】ＰＲＯＣＥＳＳＩＤ：ＩＳＴＰプロセス
に対応して８０ビット。これは、ＩＰｖ６の下では１７
６ビットに拡張することができる。この値は、新しいプ
ロセスがスタートするときにはいつでも割り当てられ、
例えば１世紀の間、空間においても時間においても唯一
であることが保証されている。この値は、不透明(opaqu
e)である。プロセス識別子しか有していなければ、ある
プロセスについて何らかの情報を得るのにいかなる方法
も指定されない。

【０１１１】プロセス識別子０、ゼロ、は、組み込みオ
ブジェクト−−−すなわち、組み込みクラス、を指示す
るのに割り当てられている。

【０１１２】ＯＢＪＥＣＴＩＤ：１６ビット。ＩＳＴ
Ｐプロセスは新しいオブジェクトを作り出すので、プロ
セス識別子を一定にしておいて名前のオブジェクトＩＤ
部分を変更することによって、新しいオブジェクトの名
前を生成する。名前は再使用されることはない。いった
ん２＾１６個の名前が生成されると、プロセスＩＤが変
更される。

【０１１３】ＩＳＴＰは、ＧＵＩＤのプロセスＩＤ部分
がどのように生成されるべきかを特定するものではな
い。しかし、妥当と思われる方法の１つは、以下のよう
にインターネットアドレスを用いて８０ビットのプロセ
スＩＤを作り上げることである。これは、ＩＰｖ６の下
では１７６ビットに拡張することができる。

【０１１４】ＩＮＴＥＲＮＥＴＡＤＤＲＥＳＳ −
ＩＳＴＰプロセスがその上で実行されているマシンのも
の。現在は３２ビットである。これは、ＩＰｖ６の下で
は１２８ビットに拡張される。

【０１１５】ＰＯＲＴＮＵＭＢＥＲ − １６ビッ
ト。ＩＳＴＰプロセスは、始動するときには、ポートに
取り付けられる。このポートは、マシン上の多数のプロ
セスを識別するのに用いられる。

【０１１６】ＧＥＮＥＲＡＴＩＯＮＣＯＵＮＴＥＲ
− ＩＳＴＰプロセスが１つの与えられたマシン上でス
タートするごとに異なっていることが保証される３２ビ
ット。最初は近似値(approximation)として、これに秒
での時間を用いるかもしれない。しかし、後には、信頼
されるサーバとのファイルシステムの相互作用および／
または通信をも含む何かを用いるべきである、というの
も、時計は止まったり逆向きに設定されたりし得るから
である。

【０１１７】生成カウンタは秒での時間であるので、プ
ロセスが再スタートする場合に名前が思いがけなく衝突
してしまう危険を冒すことなく、１秒につき１回インク
リメントすることができる。これによって、プロセス
は、１秒につき２＾１６個のオブジェクトの名前を用い
ることができる。

【０１１８】メモリおよび通信の効率を向上させるため
に、ＧＵＩＤは常に以下の圧縮された形式で表される。

【０１１９】ＰＲＯＣＥＳＳＩＤＴＡＢＬＥＰＯ
ＩＮＴＥＲ：プロセスＩＤのテーブルへの入力を示す１
６ビット。プロセスＩＤテーブルポインタ０、ゼロ、
は、組み込みオブジェクトを指示するのに割り当てられ
ている。

【０１２０】ＯＢＪＥＣＴＩＤ：オブジェクトの１６
ビットのオブジェクトＩＤ。

【０１２１】プロセスＩＤのテーブルは、圧縮されたオ
ブジェクトの名前におけるプロセスＩＤテーブルポイン
タを解釈するのに用いられる。世界モデルのコピーにお
いて、プロセスＩＤテーブルポインタは、このテーブル
へのインデックスである。メッセージにおいて、テーブ
ル全体のうちでそのメッセージにおける圧縮されたオブ
ジェクトの名前を理解するために必要な部分は、プロセ
スＩＤテーブルポインタ／プロセスＩＤのペアのベクト
ルとして、散在して(sparsely)表される。

【０１２２】いくつかのオブジェクトメッセージを含む
オブジェクト状態メッセージにおいては、プロセスＩＤ
テーブルポインタ／プロセスＩＤのペアを統一するベク
トルは１つしかない、ということに注意されたい。

【０１２３】上記ＧＵＩＤは、名前が衝突しないか心配
する必要なく１つを無限に用いることができるように設
計されている。しかし、そうしないことが実際的には重
要である。ＧＵＩＤをＩＳＴＰにおいて用いる方法の重
要な利点の１つは、概ね非常に大きいものであったとし
ても、実際の通信に必要な帯域幅は大きくない、という
ことである。この利点は、１つの与えられたプロセスが
所有する名前はほとんど全部が同じプロセスＩＤを有し
ているという前提に決定的に依存している。

【０１２４】極端な話として、もしすべてのオブジェク
トがそれぞれ異なるプロセスＩＤを有しているとするな
らば、帯域幅の使用量は、必要な量よりもはるかに大き
くなるであろう。もし名前が永久的に使用されるとする
ならば、時間が経過すると共に、プロセスＩＤの使用中
の名前に対する割合は１．０に向かって激しく上昇し、
結果が不利なものになる。このようにはせずに、可能な
ときにはいつでも、機会を利用して、古いオブジェクト
を除去して新しいオブジェクトを作り出し、それに現在
活動状態の名前のスペースからの新しい名前を付けるべ
きである。

【０１２５】ｃ．共有オブジェクトのフィールドそれぞれの共有オブジェクトは、クラスｓｐのサブクラ
スの１例である。クラスｓｐは、それぞれの共有オブジ
ェクトが以下のフィールドを含んでいるということを指
定しており、これらのフィールドはオブジェクト記述の
基礎である。すべての共有オブジェクトは、プロセス間
で共有される以下のフィールドを有している。

【０１２６】Ｃｏｕｎｔｅｒ：１６ビット − オブジ
ェクトが変化するときにはいつでもインクリメントされ
る。

【０１２７】ＤｅｓｃｒｉｐｔｉｏｎＬｅｎｇｔｈ：１
６ビット − バイトでの共有データの全大きさ。

【０１２８】Ｎａｍｅ：３２ビット − そのオブジェ
クトについての圧縮ＧＵＩＤ。

【０１２９】Ｃｌａｓｓ：３２ビット − そのオブジ
ェクトのクラスについての圧縮ＧＵＩＤ。

【０１３０】Ｏｗｎｅｒ：３２ビット − 所有者であ
るプロセスを識別する圧縮ＧＵＩＤ。

【０１３１】ＳｈａｒｅＢｉｔｓ：１６ビット − 論
理値を表す。

【０１３２】ＩｓＲｅｍｏｖｅｄ：最低位の桁のビッ
ト、ビットゼロ − １である場合には、そのオブジェ
クトが除去されてしまっていることを示す。

【０１３３】カウンタ値は、オブジェクトＡの状態の識
別子として用いられる。Ａの何らかの共有部分が修正さ
れる時ごとに、Ａのカウンタがインクリメントされる。

【０１３４】ＤｅｓｃｒｉｐｔｉｏｎＬｅｎｇｔｈは、
そのオブジェクト内のデータのフルの記述がどれくらい
長くなければならないかを指定する。以下で明らかにな
るとおり、これは、１３ビットの無署名の(unsigned)整
数に限定されている。記述の長さが１３ビットであるの
で、オブジェクトの長さは４ｋバイトにすることができ
る。フルの記述は、単一のＵＤＰパケットにぴったり入
るように限定されているので、この長さで全く十分であ
る。

【０１３５】他のオブジェクトのフィールドから、およ
び様々なＩＳＴＰメッセージにおいて、１つのオブジェ
クトを一意的に(uniquely)指すのに用いられるオブジェ
クトの名前は、ＧＵＩＤである。

【０１３６】それぞれのオブジェクトは、上述のものに
加えて多くのフィールドを有している。Ｃｌａｓｓは、
そのオブジェクトのフィールド全体がどんなものである
かを記述する、マシンが操作可能なｓｐＣｌａｓｓのオ
ブジェクトである、以下参照。ＩＳＴＰは、任意のアプ
リケーションに特有のオブジェクトを、そのｓｐＣｌａ
ｓｓ記述を参照して操作することができる。

【０１３７】オブジェクトの所有者は、そのオブジェク
トを所有しているプロセスを一意的に指すのに用いられ
るＧＵＩＤである。ここでの説明の見方からは、この唯
一の重要な面は、それぞれのプロセスがどのオブジェク
トを所有しており、そして所有していないかを判定する
ことができるようにしている、ということである。

【０１３８】ＳｈａｒｅＢｉｔｓは、様々な論理値をコ
ンパクトに表すのに用いられる。こういった値のうち、
ここで関連するのは、最低位の桁のビットただ１つであ
り、これは、オブジェクトが除去されてしまったかどう
かを指定する。

【０１３９】カウンタのインクリメントおよび比較は、
２＾１６を法とする算術を用いて行われ、正のカウンタ
値の最大のものから最小値に戻るようになっている。こ
れに対応するために、すべての比較は合同算術を用いて
行われる。すなわち、０＜Ｄ−Ｃ＜２＾１５またはＤ−
Ｃ＜−２＾１５であれば、カウンタＣはＤよりも小さ
い、すなわち、Ｃ＜Ｄである。カウンタ値ゼロは、オブ
ジェクトＡについて何も知られていない状態を意味する
のに割り当てられる。１つのオブジェクトについてのカ
ウンタは、１からスタートし、最後までカウントして元
に戻るときには値ゼロをスキップする。

【０１４０】１６ビットの状態カウンタによって、２＾
１５＝３２ｋのオブジェクト状態を正確に配列すること
ができる。１つのオブジェクトについて１秒当たり３０
回状態が変化する速度では、これは１６分間の変化の値
打ちがある(is 16 minutes worth of changes)。これ
は、ＩＳＴＰのオブジェクト通信の時間範囲が数秒程度
であることを考えると、非常に長い時間である。

【０１４１】ｄ．ｓｐＣｌａｓｓオブジェクトオブジェクトのクラスは、ｓｐＣｌａｓｓオブジェクト
を用いて記述される。ここではその詳細については説明
せず、ｓｐＣｌａｓｓオブジェクトはオブジェクトにお
けるすべてのフィールドの位置およびタイプを指定する
というにとどめておく。クラスは、組み込まれているも
のもあるが、大部分はアプリケーションによって規定さ
れている。フィールドのうちの２つのタイプのものは、
特に注意するのに値する。

【０１４２】他のオブジェクトを指すフィールドは、上
述のようにそういったオブジェクト用の圧縮ＧＵＩＤを
含む。時間を含むフィールドは、そういった時間を、３
２ビットの整数を用いて表し、その単位は１週間を法と
するミリ秒である。

【０１４３】それぞれの受け取るプロセスＰｋは、プロ
セスＰｊがメッセージＭを送る時間からＰｋがそのメッ
セージを処理する時間の間に通常過ぎ去ってしまう、全
時間の推定値ＤＴｊを維持する。

【０１４４】これは、それぞれの受け取られたメッセー
ジのＳｅｎｄＴｉｍｅと、そのメッセージが処理される
Ｐｋの場所時間の間の差を観測して、移動平均を計算
し、異常値を無視することによって、計算される。この
推定値ＤＴｊは、第１に、ＰｊからＰｋへのメッセージ
の伝達時間、第２に、メッセージが処理される前のＰｋ
における平均遅延、第３に、ＰｊおよびＰｋの時計のセ
ッティングにおける絶対差、を意識的に融合している、
ということに注意されたい。最後の要因があるため、Ｄ
Ｔｊは負になり得る。

【０１４５】時間の推定値ＤＴｊは、R. C. Waters, Ti
me Synchronization In Spline, MERL TR 96-09, MERL
Cambridge MA, April 1996において説明されているよう
に、Ｐｊの時間枠からＰｋの時間枠までのオブジェクト
記述において指定された各時間を調整するのに用いられ
る。

【０１４６】ｅ．フルのオブジェクト記述フルのオブジェクト記述は、そのオブジェクトについて
のいかなる他の情報にも言及することなく、単独で理解
されることができる。以下の形式を有しているが、すべ
ての記述が、その記述の種類を指定する３ビットでスタ
ートすることに注意されたい。

【０１４７】フルの記述は、以下のものを含む。

【０１４８】ＤｅｓｃｒｉｐｔｉｏｎＦｏｒｍａｔＣｏ
ｄｅ：３ビット − フルの記述については０に等し
い。

【０１４９】ＤｅｓｃｒｉｐｔｉｏｎＬｅｎｇｔｈ：１
３ビット − 記述、従って共有データ、におけるバイ
ト。

【０１５０】Ｃｏｕｎｔｅｒ：１５ビット − オブジ
ェクトについてのカウンタ値。

【０１５１】Ｎａｍｅ：３２ビット − オブジェクト
の名前である圧縮ＧＵＩＤ。

【０１５２】Ｃｌａｓｓ：３２ビット − オブジェク
トのｓｐＣｌａｓｓについての圧縮ＧＵＩＤ。

【０１５３】Ｄａｔａ：バイト［］ − オブジェクト
における他のデータフィールド。

【０１５４】フルの記述は、問題のオブジェクトからす
べての共有データを単にコピーすることによって構成さ
れる、トリビアルなものである(trivial)。それらは、
反対方向にコピーすることによって解釈しても等しくト
リビアルである。ただ１つ複雑なのは、上述のとおりＧ
ＵＩＤおよび時間を経由して他のオブジェクトへの参照
を処理する(dealing with reference to)、ということ
である。

【０１５５】ｆ．示差オブジェクト記述示差記述は、オブジェクトの、１つの状態から他の状態
への変更を記述する。

【０１５６】示差記述は、以下のものを含む。

【０１５７】ＤｅｓｃｒｉｐｔｉｏｎＦｏｒｍａｔＣｏ
ｄｅ：３ビット − 示差記述については、１。

【０１５８】ＢａｓｅＣｏｕｎｔｅｒＤｅｌｔａ：５ビ
ット − 基準オブジェクト状態からのデルタ。

【０１５９】ＦｉｒｓｔＣｏｄｅ：８ビット − 変化
が起こったところを記述する第１のバイト。

【０１６０】Ｃｏｕｎｔｅｒ：１６ビット − オブ
ジェクトについてのカウンタ値。

【０１６１】Ｎａｍｅ：３２ビット − オブジェクト
の名前である圧縮ＧＵＩＤ。

【０１６２】ＯｔｈｅｒＣｏｄｅｓ：バイト［］ −
変更の位置を示す残りのバイト。整列を保存するために
４つのグループにする。

【０１６３】Ｄａｔａ：ロング(long)［］： − 変更
を表す新しい語データ。

【０１６４】ＢａｓｅＣｏｕｎｔｅｒＤｅｌｔａは、ど
のような前の状態に関して、示差記述を復号することが
できるかを指定する。

【０１６５】ＢａｓｅＣｏｕｎｔｅｒＤｅｌｔａ＝
０の場合には、その記述は単独で解釈することができ
る。

【０１６６】ＢａｓｅＣｏｕｎｔｅｒＤｅｌｔａ＝
１の場合には、その記述は、直前のオブジェクト状態が
入手可能でなければ、理解することができない。

【０１６７】ＢａｓｅＣｏｕｎｔｅｒＤｅｌｔａ＝
Ｎの場合には、その記述は、最後のＮ個のオブジェクト
状態のうちのいずれかをベースにして解釈することがで
きる。この方法を用いることに伴う不利益は、符号化が
より困難になり、最終サイクルにおいては変化しておら
ずもっと前のサイクルにおいてのみ変化しているデータ
が含まれているかもしれない、ということである。しか
し、利益は、待ち時間が低減され、メッセージの流れ
が、いくつかの記述を損失してしまうということに対し
て強靱である(robust)、ということである。これは、オ
ブジェクトが迅速に動き回っている場合等に用いること
ができるであろう。Ｘ−Ｙ−Ｚの位置のみが変化する場
合には、記述の長さを増大することなく、ＢａｓｅＣｏ
ｕｎｔｅｒＤｅｌｔａを非常に大きくすることができ
る。

【０１６８】バイト変更コードは、以下の形式を有す
る。正のバイトは、最初のものについての開始から残り
のものについての最後の変更後までのオフセットを示
す。負のバイトは、それらの絶対値によって、実行長さ
(run length)を示す。ゼロバイトは、変更バイトの終わ
りを知らせる。１行に２つの負でないバイトがある場合
には、第１のオフセットと関連する長さは１である。特
別な場合として、まさに最初のバイトが負の場合には、
それはまだオフセットとして扱われ、長さは１であり、
変更コードの組は、この１バイトのみから成る。この特
別な場合によって、１語の変更をたった３語で指定する
ことができる。それぞれの変更は、最後の変更の後の語
に関するオフセットとして指定される。データの各語
は、記述内で整列し、バイトコードによって指定される
とおりオブジェクト内にコピーされる。

【０１６９】例えば、＜１３，−３０，１２０３＞＜
８８０８８＞＜Ａ＞は、オブジェクト８８０８８の状態
１２０３は、状態１２００、１２０１、または１２０２
から語Ａを３０＊４＝１２０のオフセットで書き込むこ
とによって計算することができるということを指定して
いる。この１２バイトのメッセージは、最小示差記述の
一例であり、４バイトの変更を指定する。

【０１７０】より複雑な例としては、＜１１，８
０；１２０３＞＜８８０８８＞＜−３，１０，０，
０＞＜Ａ＞＜Ｂ＞＜Ｃ＞＜Ｄ＞は、オブジェクト８８０
０８８の状態１２０３は、状態１２０２から、語Ａを８
０＊４＝３２０のオフセットで書き込み、語Ｂを８１＊
４＝３２４のオフセットで書き込み、語Ｃを８２＊４＝
３２８のオフセットで書き込み、語Ｄを９３＊４＝３７
２のオフセットで書き込むことによって、計算すること
ができる、ということを指定している。

【０１７１】この２８バイトのメッセージは、１６バイ
トの変更を指定する。第１の変更が１つのオブジェクト
内への１２７語よりも多いものである場合には、実変更
の途中でダミー変更を用いなければならない。同様に、
１語の変更の後の変更は、そのオブジェクトの下に１２
７語をさらに動かすことができるのみである。しかし、
各オブジェクトが、なお送らなければならないことが多
いフルの記述が単一のＵＤＰパケットにぴったり入るこ
とができるよう、十分短くなければならないとすれば、
ここには問題はほとんどないであろう。

【０１７２】示差記述を構成することは、フルの記述を
計算するよりも困難である、というのも、そのオブジェ
クト内のどの語が変化したかを正解に知る必要があるか
らである。ＢａｓｅＣｏｕｎｔｅｒＤｅｌｔａが１の場
合の記述を計算するには、どの語が変化したか、例えば
ビットマップ内に記録されたか（変更された語が示され
る）、を直接知るか、あるいは、直前の状態の記録を得
て、比較することによってどの語が変化したかを明らか
にするか、のどちらかを行わなければならない。上記の
うちのどちらかが与えられれば、示差記述の構成は簡単
で(straightforward)ある。

【０１７３】ＢａｓｅＣｏｕｎｔｅｒＤｅｌｔａが２の
場合の記述を計算するには、最後の２つの状態変更のう
ちのどちらかによってどの語が変化したかを知らなけれ
ばならない。ある語が変化したがその後その元の値に戻
った場合には、受け取り手が最後から２つ目の状態では
なく最後の状態を入手しているといけないので、そのこ
とはなお記述に含まなければならないということに注意
されたい。

【０１７４】Ｎおよびそれより小さいＢａｓｅＣｏｕｎ
ｔｅｒＤｅｌｔａを支援する簡単な方法の１つは、Ｎ個
の前の状態変更を要約するビットマップを保管する、と
いうことである。そうすれば、これらは一緒に論理和が
とられて、Ｎよりも小さいかＮに等しいいかなるＢａｓ
ｅＣｏｕｎｔｅｒＤｅｌｔａについても、どの語を送る
かの仕様が与えられる。与えられた瞬間に、もっと大き
いＢａｓｅＣｏｕｎｔｅｒＤｅｌｔａが必要な場合に
は、フルの記述の仕様に頼ることができる。１つのオブ
ジェクトが変更されるごとに、新しいビットマップが計
算されてオブジェクト当たりの待ち行列に保管され、Ｎ
個よりも多いビットマップがある場合には、最も古いビ
ットマップが廃棄される。

【０１７５】示差メッセージを有することによって、記
述におけるＧＵＩＤおよび時間の取り扱いが複雑にな
る、というのも、記述内のどこにそれらがあるかを計算
するのがより困難であるからである。しかし、帯域幅を
節約することができるということは、このように余分に
複雑になることを補って余りある。

【０１７６】示差メッセージの重要な場合の１つは、オ
ブジェクトが除去されたということを指定する、という
ものである。その状況では、重要なのは、ＩｓＲｅｍｏ
ｖｅｄビットが設定されるということだけである。他の
フィールドの値は無関係である。その結果、ＢａｓｅＣ
ｏｕｎｔｅｒＤｅｌｔａが０である短い示差メッセージ
を構成することができる。

【０１７７】差を示す性質の、特別な種類のフルの記述
を既に有している、ということに注意すべきである。除
去されたオブジェクトに関するメッセージは、オブジェ
クトの破壊を求めるので、フルの状態を含む必要はな
い。そのオブジェクトが除去されるということを指定す
るビットを示せばよいだけである。従って、この情報の
みを含む示差メッセージを送ることができる。

【０１７８】ｇ．マルチキャストのメッセージの送出お
よび受け取り方法頻繁なベースで、例えば３０〜１００ミリ秒ごとに１
回、プロセスＰｊは、自らが最後にメッセージを送った
ときから変更したすべてのオブジェクトを記述する、１
つまたはそれより多いオブジェクト状態メッセージを送
出する。同じ速度で、プロセスＰｊは、他のプロセスが
送るオブジェクト状態メッセージを処理する。

【０１７９】各メッセージは、ＵＤＰマルチキャストパ
ケットを用いて送出される。それぞれのメッセージは、
単一のパケットに入れて送られ、それぞれのパケット
は、１つのメッセージのみを含む。用いるアドレスは、
以下に説明するとおり、サーバＳによって指定される。

【０１８０】重要な要求事項の１つは、それぞれのオブ
ジェクト状態メッセージは、単一のＵＤＰパケットにぴ
ったり入らなければならない、ということである。言い
換えれば、最大送信ユニットすなわちＭＴＵよりも小さ
くなくてはならない。ＭＴＵの大きさは、送信媒体によ
って決まる。現在ＭＴＵは、モデムについての数百バイ
トから、イーサネットについての１，５００バイト、そ
してそれ以上までと、様々に幅広い。ＩＰｖ６の下で
は、最小ＭＴＵは６００バイトとなろう。

【０１８１】与えられた瞬間において、どのオブジェク
トも修正されていない場合には、メッセージは送られな
い。変化したオブジェクトがいくつかある場合には、そ
れぞれのメッセージにできるだけ多くの記述が詰め込ま
れる。グルーピング記述では帯域幅の使用量がかなり増
大し、受け取り手における処理性能が改良される、とい
うことに注意されたい。

【０１８２】帯域幅を最小にするために、可能なときに
はいつでも、示差記述が用いられる。１つのオブジェク
トが最初にそのグループと通信する、すなわち、そのオ
ブジェクトが最初に作り出される、ときには、フルの記
述を用いなければならない。示差記述が可能になった後
は、実用的な場合にはいつでも、そのオブジェクトの最
後の状態のみに関するのではなく、最初のフルのメッセ
ージまでずっとさかのぼって、またはそれができない場
合には、少なくともいくつかの状態までさかのぼって関
するような、示差メッセージが構成される。

【０１８３】最後から２つ目の状態をベースにして解釈
することができる示差記述を有することは、すべてのメ
ッセージを受け取る必要があるようなただ１つの状態の
みにさかのぼることと比べて、メッセージが失われるこ
とを許容することができるという点で、明らかに大きな
進歩である。２つよりも多い状態にさかのぼることに
は、利点もあるが、明らかな収穫逓減がある。とは言っ
ても、１つのオブジェクトのある小さな部分が迅速に変
化している場合には、余分にコストがかかることなし
に、多くの状態にわたって解釈することができる示差記
述を有することができるかもしれない。

【０１８４】ＵＤＰは信頼性の高いプロトコルではない
ので、Ｐｊによって送られる１つの与えられたメッセー
ジＭは、Ｐｋに、全く到着しないかもしれないし、何度
も到着するかもしれないし、および／またはＰｊが送る
他のメッセージに関して順番が狂って到着するかもしれ
ない。Ｐｋは、こういった状況のすべてを処理すること
ができなければならない。これは主に、メッセージ当た
りのベースではなく、オブジェクト当たりの記述をベー
スにして行われるが、１つ重要なことが、全体としての
メッセージについて行われる。

【０１８５】受け取り手のプロセスＰｋは、それぞれの
他のプロセスＰｊから受け取るメッセージの送りおよび
受け取りの時間の経過を追っている。ＰｋがＰｊから、
Ｐｊから既に受け取っている何か他のメッセージよりも
早いＳｅｎｄＴｉｍｅを有するメッセージＭを受け取る
場合には、Ｍは順番が狂って受け取られている。２つの
メッセージが同じＳｅｎｄＴｉｍｅを有している場合に
は、同じ時に送られており、ＩＳＴＰにとっては両者の
順番は問題ではない。

【０１８６】ＩＳＴＰのパラメータの１つは、最大遅延
ＭａｘＤｅｌａｙであり、これは通常数秒程度である。
遅れて到着するメッセージＭが、ＭよりもＳｅｎｄＴｉ
ｍｅが遅い同じ源から何らかのこれまでに到着したメッ
セージからＭａｘＤｅｌａｙ秒よりも遅れて到着する場
合には、Ｍは処理されることなく廃棄される。メッセー
ジの遅れについてこのように制限を課すことは、以下に
説明する多くの理由により重要である。

【０１８７】一例として、以下の表を検討する。

【０１８８】表１Ｐｊにおけるメッセージの 	ＰｋにおけるメッセージのＳｅｎｄＴｉｍｅ 	到着時間１１１２１７３１３４１７５１５６１６

【０１８９】２および４において送られたメッセージは
順番が狂って到着する。ＭａｘＤｅｌａｙ＝３の場合に
は、４において送られたメッセージは、到着するとまだ
用いることができる。しかし、２において送られたメッ
セージは、３において送られたメッセージよりも４秒後
に到着するので、廃棄される。ＭａｘＤｅｌａｙ＝５の
場合には、両方のメッセージを用いることができる。

【０１９０】ＭａｘＤｅｌａｙ＝１の場合には、両方の
メッセージを拒絶しなければならない。メッセージにお
ける時間は、１週間を法として表されるので、上記を検
出することができるのは、３．５日以上遅れて到着する
メッセージはないという仮定にかかっている。これは、
測定される遅れが通常数秒に過ぎないとすれば、非常に
無難な仮定である。

【０１９１】この遅れによって、ＭａｘＤｅｌａｙが限
定され、入メッセージについて履歴情報を記録するのに
必要なテーブルの大きさが限定される、ということに注
意されたい。特に、ＭａｘＤｅｌａｙ秒よりも前に受け
取ったメッセージは、このテーブルに１つよりも多く存
在する必要はない。

【０１９２】１つのメッセージＮがＭａｘＤｅｌａｙ秒
よりも前に受け取られた場合には、そのことによって、
Ｎよりも前に送られたいかなるメッセージも、到着時に
廃棄される。Ｎよりも遅れて送られ、これもまたＭａｘ
Ｄｅｌａｙ秒よりも前に受け取られた何か他のメッセー
ジＮ’がある場合には、Ｎはテーブルから外してもよ
い、というのも、Ｎによってなされるいかなるメッセー
ジ廃棄も、Ｎ’によってもまたなされるからである。例
えば、上の例でＭａｘＤｅｌａｙ＝３の場合には、時間
１６において保持される必要のある情報は、３、５、６
において送られたメッセージについての情報のみであ
る。

【０１９３】１つのメッセージが、遅れすぎているとい
う理由によって廃棄されない場合には、その中のオブジ
ェクト記述が、以下のとおり個別に処理される。

【０１９４】与えられた記述Ｄが、Ｐｋにおけるオブジ
ェクトについての現在のカウンタ値よりも小さいか、ま
たはそれと等しいカウンタ値を有する場合には、Ｄは無
視される。通常これは、Ｄが順番が狂って到着したり１
回よりも多く到着したメッセージの中にある場合に起こ
る。

【０１９５】Ｄにおけるカウンタ値が、Ｐｋにおけるオ
ブジェクトについての現在のカウンタ値よりも大きい場
合には、またはそのようなオブジェクトがない場合に
は、Ｄ内の情報が以下のとおり用いられる。Ｄがフルの
記述の場合には、常に即座に処理して、問題のオブジェ
クトを更新したり作り出したり除去することができる。
示差記述の場合には、現在既知のオブジェクト状態に関
して解釈可能である限りは、即座に処理することができ
る。そうでない場合には、まだ到着していない何か間に
入る記述がなければならない。即座に解釈可能でない記
述は、オブジェクト当たりの待ち行列に保管され、後に
欠けている間に入る記述が到着すると用いられる。

【０１９６】いったん１つの記述が用いられると、関連
するオブジェクト記述の待ち行列が調査され、現在用い
ることができる記述が他にないか調べられる。即座に用
いることができない示差記述は、単に廃棄する、という
ことを選択することもできる。このほうが簡単であろう
が、本システムの、順番が狂ったメッセージを利用する
能力が低減しよう。示差記述がいくつかの状態にわたっ
ている場合には、このようにしても問題がないかもしれ
ない。

【０１９７】示差記述がいくつかの状態にわたると、１
つの記述を、その直前の記述が失われたり遅延したメッ
セージ内にある場合であっても、用いて即座に行動する
ことが可能なことが多い。こうすることによって、失わ
れたおよび遅延したメッセージについて欠けていること
を検出したり再送する必要なしに、そういったメッセー
ジによる被害が制限される。

【０１９８】特に説明が必要な問題の１つは、共有オブ
ジェクトが除去される時に起こる事柄である。１つのオ
ブジェクトが除去される場合には、常に解釈することが
できる示差記述を用いることができる、というのも、そ
のオブジェクトに関して関連する唯一の事実は、それが
除去されるということだからである。いったんオブジェ
クトが除去されると、潜在的な問題が起こり得る。

【０１９９】除去されたオブジェクトＡのすべての形跡
が、プロセスＰｋから除去されてしまったと仮定する。
もしそうなら、次にＡの順番の狂ったフルの記述が受信
されると、Ａの創造を指定するメッセージのように見
え、ＡがＰｋのメモリ内に誤って再び現れてしまうであ
ろう。これを避けるために、ＭａｘＤｅｌａｙ秒の間、
Ａの除去についての記録が維持され、そのように遅れて
到着してきた記述があっても、うまく無視することがで
きるようになっている。もし遅れを制限するＭａｘＤｅ
ｌａｙがないとすると、順番の狂った記述の拒絶を支援
するために、Ｐｋは、除去されたすべてのオブジェクト
を永久に覚えておかなければならないであろう。

【０２００】上記のマルチキャストのオブジェクト状態
メッセージは、グループ内の他のプロセスだけではな
く、サーバＳも受信する、ということに注意されたい。

【０２０１】様々なプロセスとちょうど同じように、Ｓ
はこのメッセージを用いて、すべてのオブジェクトの現
在の状態の記録を維持する。

【０２０２】ｈ．各プロセスが知っておくべきものを知
る方法プロセスＰｋが知っておくべきものを知らせるために、
サーバは、ＭａｘＤｅｌａｙ秒ごとに１回、定期的なオ
ブジェクト状態要約メッセージを送出する。

【０２０３】オブジェクト状態要約メッセージのフィー
ルドは、以下のとおりである。

【０２０４】ＭｅｓｓａｇｅＴｙｐｅＩＤ：１６ビット
− 値２が、これがオブジェクト状態要約であるとい
うことを示す。

【０２０５】ＳｅｎｄｅｒＩＤ：３２ビット − 受け
取り手のｓｐＣｏｍを識別する圧縮ＧＵＩＤ。

【０２０６】ＳｅｎｄＴｉｍｅ：３２ビット − １週
間を法とする、ミリ秒での送られる時間メッセージ。

【０２０７】ＮｕｍｂｅｒＯｆＧＵＩＤＰｒｅｆｉｘｅ
ｓ：１６ビット − ＧＵＩＤＴａｂｌｅにおける接頭
部Ｇの数。

【０２０８】ＮｕｍｂｅｒＯｆＮｅｗＥｎｔｒｉｅｓ：
１６ビット − 本体における新しいオブジェクト入力
の数Ｎ。

【０２０９】ＮｕｍｂｅＯｆＯｂｊｅｃｔＣｈａｎｇｅ
ｓ：１６ビット − オブジェクトの変更の数Ｃ。

【０２１０】ＧＵＩＤＴａｂｌｅ：Ｇ個のＧＵＩＤＰｒ
ｅｆｉｘ入力 − それぞれ９６ビット。

【０２１１】ＧＵＩＤＴａｂｌｅＥｎｔｒｙＩｎｄｅ
ｘ：１６ビット − 圧縮ＧＵＩＤに用いる。

【０２１２】ＧＵＩＤＰｒｅｆｉｘ：８０ビット −
メッセージにおいて多くのＧＵＩＤに潜在的に共有され
ている接頭部。

【０２１３】ＮｅｗＥｎｔｒｉｅｓ：Ｎ個の新しいオブ
ジェクト要約 − それぞれ６４ビット。

【０２１４】ＯｂｊｅｃｔＴａｂｌｅＩｎｄｅｘ：１６
ビット − オブジェクトについてのテーブル位置を指
定。

【０２１５】ＣｏｕｎｔｅｒＶａｌｕｅ：１６ビット
− オブジェクトについてのカウンタ値。

【０２１６】ＣｏｍｐｒｅｓｓｅｄＧＵＩＤ：３２ビッ
ト − 新しいオブジェクトを識別。

【０２１７】ＯｂｊｅｃｔＣｈａｎｇｅｓ：ショー
ト［］ − Ｃ個のオブジェクト変更要約。

【０２１８】メッセージのタイプ、ＳｅｎｄｅｒＩＤ、
ＳｅｎｄＴｉｍｅ、ＮｕｍｂｅｒＯｆＧＵＩＤＰｒｅｆ
ｉｘｅｓ、ＧＵＩＤＴａｂｌｅは、以下のことを除けば
オブジェクト状態メッセージと全く同じである。すなわ
ち、メッセージのタイプの有する値が異なり、Ｓｅｎｄ
ｅｒＩＤが、オブジェクト状態要約メッセージを受け取
るプロセスＰｋが最初にサーバＳとコンタクトしたとき
にＰｋが用いたｓｐＣｏｍである。従って、Ｓｅｎｄｅ
ｒＩＤは、送り手を間接的に識別するに過ぎない。

【０２１９】ＮｕｍｂｅｒＯｆＮｅｗＥｎｔｒｉｅｓ
は、メッセージのＮｅｗＥｎｔｒｉｅｓの部分において
記述されている新しいテーブル入力の数を指定する。

【０２２０】ＮｕｍｂｅｒＯｆＯｂｊｅｃｔＣｈａｎｇ
ｅｓは、メッセージのＯｂｊｅｃｔＣｈａｎｇｅｓの部
分において記述されているオブジェクト変更の数を指定
する。

【０２２１】ＮｅｗＯｂｊｅｃｔのフィールドは、Ｓか
らの最後のオブジェクト状態要約メッセージの後どのよ
うな新しいオブジェクトが現れてきたかを記述する。

【０２２２】ＯｂｊｅｃｔＣｈａｎｇｅｓは、Ｓからの
最後のオブジェクト状態要約メッセージの後どのような
オブジェクトが変化したかを記述する。これについては
以下で詳細に説明する。オブジェクト状態要約メッセー
ジのペイロードを説明する前に、それぞれのプロセスＰ
ｋにおいて維持されているオブジェクトテーブルを説明
することが必要である。このテーブルは、存在するそれ
ぞれのオブジェクトの圧縮ＧＵＩＤおよびその関連する
現在のカウンタ値をリストしている。このテーブルは、
どのオブジェクトが存在するか、および、それらのオブ
ジェクトについて送出された最後のオブジェクト状態要
約メッセージ内のカウンタを、正確にコンパクトに要約
している。

【０２２３】同一のテーブルが、通信グループにおける
サーバＳおよびそれぞれのプロセスＰｋ内に維持されて
いる。後のセクションで説明するように、１つのプロセ
スＰｋについてのオブジェクトテーブルは、最初は、Ｐ
ｋが通信グループに参加するときにどのようなオブジェ
クトが存在するかを知ることの一部として構成される。
Ｓは、そのオブジェクトテーブルの自らのマスターコピ
ーを、オブジェクトについての新しい情報を知る度ごと
に更新することによって、インクリメントして構成す
る。

【０２２４】オブジェクト状態要約メッセージは、オブ
ジェクトテーブルにおける変更を指定する、示差タイプ
のメッセージである。要約メッセージを用いて、それぞ
れのＰｋにおけるオブジェクトテーブルの、Ｓにおける
テーブルとの同期が保たれ、従って、それぞれのＰｋ
に、オブジェクトすべてについて最新情報を有していな
いかが尋ねられる。

【０２２５】ＮｅｗＥｎｔｒｉｅｓのフィールドは、オ
ブジェクトテーブルのインデックス、ＣｏｕｎｔｅｒＶ
ａｌｕｅｓ、およびＣｏｍｐｒｅｓｓｅｄＧＵＩＤｓの
３倍量(triples)を含んでいる。これは、示されたデー
タで新しい入力が作り出されるということを指定してい
る。前に廃棄された入力は、できるだけ多く再使用され
る。動的テーブル拡張が必要であるかもしれない。

【０２２６】新しいオブジェクトが現れるのは、オブジ
ェクトが変化するよりも頻度がずっと低い事象であると
思われる。１つのオブジェクトが単一の時間間隔内で現
れて消えていく、ということは、可能性としてはある
が、非常にまれなことである。その状況では、除去され
たオブジェクトに対応するカウンタ値を指定する新しい
オブジェクト入力があるであろう。

【０２２７】なんらかの理由で、新しい入力が指定する
ものが、現在のエントリーの１つと衝突してしまう場合
には、新しい方の入力情報が、現在の入力に取って代わ
る。サーバがこれを用いて、１つのプロセス内で−−−
例えば、再初期化の間に、オブジェクトテーブルにおい
て任意に変更を行うことができる。

【０２２８】ＯｂｊｅｃｔＣｈａｎｇｅｓのフィールド
は、最もコンパクトになるように設計されている。一連
のバイトコードを用いて、オブジェクトについてのＣｏ
ｕｎｔｅｒＶａｌｕｅｓにおける変更を指定する。バイ
トは、以下のように復号される。

【０２２９】コードには、コンパクトコードとフルコー
ドという、２つの基本的な種類がある。

【０２３０】事例Ａ：１つのコードの最高位の桁のビッ
トが０である場合には、第１のバイトを用いて、インデ
ックスされたオブジェクトと関連するカウンタがインク
リメントされる。用いるインデックスは、第２の無署名
のバイトを、用いる最後のテーブルインデックスに加え
ることによって、計算される。テーブルインデックスは
ゼロからスタートする、ということに注意されたい。

【０２３１】事例Ｂ：１つのインデックスコードの最高
位の桁のビットが１である場合には、第１の２つのバイ
トは、用いる最後のテーブルインデックスから減じるデ
ィクレメントとして解釈される。そして、次の２つのバ
イトは、インデックスされたオブジェクト入力について
の絶対カウンタ値として用いられる。テーブル内の２＾
１５個以上の入力をスキップするために、２つのフルの
入力を一緒につなぎ合わさなければならない。その第１
のものは、関連するＣｏｕｎｔｅｒＶａｌｕｅを変化さ
せずにおく。上のＡとＢのいずれの事例においても、コ
ードのカウンタ部がゼロである場合には、オブジェクト
テーブル内のインデックスされた入力は廃棄されるべき
であるということが示されている。

【０２３２】事例Ｂが有用であるためには、通常１つの
テーブル内のオブジェクトの少なくとも数パーセントは
変化しており、変更されなければならない入力は合理的
に互いに近くにあるという事実に依存している、という
ことに注意されたい。さらに、２つのオブジェクト状態
要約メッセージ間で１２７より多くカウンタが増加する
ことはありそうにない、という事実にも依存している。
１秒当たり３０個の変更がある場合には、２５５個の変
更を行うには、８秒以上必要である。

【０２３３】事例Ｂが適用可能であり、作られなければ
ならない新しいオブジェクト入力がない場合には、オブ
ジェクト状態要約メッセージは、２８バイトのヘッダを
有し、−ＳｅｎｄｅｒＩＤについて１つのＧＵＩＤＰｒ
ｅｆｉｘが必要である−従って、２８＋２Ｎバイトのみ
を使ってＮ個の変更されたオブジェクトを記述すること
ができる。

【０２３４】もし、１００個のオブジェクトが頻繁に変
化しており、オブジェクト状態要約メッセージが１秒に
１回送出されているとすると、これによって、Ｓからそ
れぞれのプロセスＰｊに１．８ｋｂｐｓのトラヒックが
生じることになる。

【０２３５】オブジェクト変更符号化の一例として、以
下の＜２８，０５，２０１００，−１０００４
４５５５＞を検討する。

【０２３６】これは、８番目のテーブル入力はカウンタ
を２だけインクリメントするべきであり、１３番目のテ
ーブル入力は廃棄されるべきであり、１１３番目のテー
ブル入力はカウンタを２０だけインクリメントするべき
であり、１１１３番目のテーブル入力はカウンタを４５
５５に設定するべきである、ということを指定してい
る。オブジェクト要約メッセージは、以下のように処理
される。Ｐｋは、新しいオブジェクト入力がもしあれば
それを処理する。これらの入力によって、新しいオブジ
ェクトテーブル入力を作り出すことが指定される。Ｓ
は、これらの入力の位置を探し出し、可能なときにはフ
リーのスロットを再利用できるように、しかしながらま
だ使用中の以前から存在する入力とは衝突しないように
する。新しい入力は、指定されたインデックス、カウン
タ、およびＧＵＩＤで作り出される。

【０２３７】次に、それぞれのオブジェクト変更入力
が、以下のように処理される。その入力が、オブジェク
トＡが変化したということを指定している場合には、局
所オブジェクトテーブルにおけるＣｏｕｎｔｅｒＶａｌ
ｕｅが更新される。または、オブジェクト変更が、その
入力が廃棄されるべきであるということを指定している
場合には、その入力は廃棄される。

【０２３８】廃棄される入力は、ゼロのＧＵＩＤおよび
ＣｏｕｎｔｅｒＶａｌｕｅｓを与えられることによって
タグがつく、ということに注意されたい。また、テーブ
ル入力を廃棄することは、オブジェクトを除去すること
とは非常に異なる、ということにも注意されたい。オブ
ジェクトＡが排除される場合には、このことは、Ａが排
除されるということを指定するオブジェクト記述によっ
て指定される。この除去の次に、サーバは結局、関連す
るオブジェクトテーブル入力を廃棄するが、そうするま
でにサーバはかなりの時間待機するべきである。特にサ
ーバは十分長い時間待機して、プロセスＰｋがＡが除去
されたことを知ることができるようにするべきである。

【０２３９】特に、Ｓが、１つのオブジェクトが除去さ
れた後そのテーブル入力を再利用するまでに１０＊Ｍａ
ｘＤｅｌａｙ程度の時間待機する、ということが提案さ
れる。このようにすると、かなりの確率で、そのテーブ
ル入力が再使用される前にそれぞれのプロセスＰｋがそ
のオブジェクトが除去されたということを知ることが保
証されるであろう。しかし、この情報を得ていないプロ
セスがあるとしても、以下で説明する、オブジェクトテ
ーブル入力を有しないオブジェクトを除去する機構のた
めに、そのオブジェクトはいずれにせよ結局は排除され
る。

【０２４０】場所オブジェクトテーブルにおけるＣｏｕ
ｎｔｅｒＶａｌｕｅが変更される度ごとに、以下のチェ
ックが行われる。Ｐｋが、そのＣｏｕｎｔｅｒＶａｌｕ
ｅＣが変化していないオブジェクトＡを所有していない
場合には、Ｐｋは、自らがＡについての最新情報を有し
ているかどうかをチェックして調べる。ＰｋがＡについ
て全く知らない、またはＡについてもっと小さいカウン
タ値しか有していない場合には、ＰｋはＳに、次のセク
ションにおいて記述された最新情報を求める要求を送
る。Ｐｋは、もっと大きいカウンタ値を有しているかも
しれない、ということに注意されたい、というのも、Ａ
の所有者から、Ｓからの要約にはまだ含まれていない情
報を有しているかもしれないからである。

【０２４１】ＰｋがＡについて状態Ｃであるオブジェク
ト状態要約メッセージＭを受け取るためには、Ａを所有
するプロセスＰｊは、Ｓが受け取り処理した、Ａが状態
ＣであるメッセージＮを送出していなければならない。
Ｐｋは、メッセージをＰｊからＳへ、そして次にＳから
Ｐｋへと送るには、常にメッセージをＰｊから直接Ｐｋ
に送るよりも長い時間がかかるという仮定の下に、Ｍを
受け取る前にＮを受け取って処理できているはずであ
る。

【０２４２】Ｐｋが、そのＣｏｕｎｔｅｒＶａｌｕｅ
Ｃが変化してしまったオブジェクトＡを所有している場
合には、オブジェクト状態要約は、ＰｋによってＳに送
られた情報の受け取りの肯定応答としての役割をする。
Ｐｋは、Ａが除去されているとしても、Ｃ以上または同
等のＣｏｕｎｔｅｒＶａｌｕｅを知っていなければなら
ない。

【０２４３】Ｐｋがもっと大きいＣｏｕｎｔｅｒＶａｌ
ｕｅを有している場合には、Ａについて送出された最新
のメッセージが失われてしまい、従ってＳに達しなかっ
たかもしれない。または、そのメッセージは送られてい
る途中であるが、オブジェクト状態要約メッセージが作
り出されるよりも前にはＳには到着していなかっただけ
なのかもしれない。Ｐｋは、これら２つの状況のうちの
どちらが一番可能性があるかを判断しなければならな
い。Ｐｋは、自らとＳの間のメッセージの伝達時間を推
定してそれをベースにしてこれを行うことができる。現
在のインターネット上では、この伝達時間は非常に長い
ものになり得る、ということに注意されたい。Ｐｋが、
メッセージが失われていると結論を出した場合には、Ｐ
ｋは次のセクションにおいて説明するとおりそのメッセ
ージを再送する。Ｐｋはまた、自らが所有するオブジェ
クトについてオブジェクトテーブルに全く入らない情報
を有している場合にも、メッセージが失われていないか
どうかを検討しなければならない、ということに注意さ
れたい。

【０２４４】ＰｋがオブジェクトＡを除去する場合に
は、Ａが除去されたということをＳが知っているという
肯定応答を受け取るのにどれだけ長い時間が必要であっ
ても、この事実を覚えておかなければならない、という
ことに注意されたい。このことは通常、Ｐｋが順番の狂
った記述を拒絶することのみを行っているとするならば
その場合に必要なよりもずっと長い間、Ａが除去された
ということを覚えておくということを必要とする。Ｐｋ
が、肯定応答を得る前にＡについて忘れてしまったり、
除去を指定するメッセージがどういうわけかＳに到着し
なかった場合には、次のオブジェクト状態要約メッセー
ジがＡが誤って再び現れるようにしてしまい得る。

【０２４５】オブジェクトテーブルが用いられる最後の
方法は、Ｐｋの世界モデル内にはあるがテーブル内には
ないオブジェクトに関する。オブジェクトＡが存在する
が、テーブル入力は有していないと仮定する。これは、
ＡがＰｋまたは他のプロセスによって作り出されたばか
りであって、まだＡがオブジェクト状態要約メッセージ
内に存在していない場合には、普通に起こることであ
る。しかし、この状況は長くは続かないであろう。

【０２４６】ＰｋがＡを所有している場合には、Ｐｋは
結局はＡについての情報をＳにＴＣＰを経由して送るの
で、問題は解決されよう。

【０２４７】ＰｋがＡを所有しておらず、しかしながら
かなりの時間、例えば１０＊ＭａｘＤｅｌａｙ、の間オ
ブジェクトテーブルにないままである場合には、Ａはど
ういうわけか誤った方法で生じている。このようなこと
になり得る一連の事柄は込み入っており、どのようなプ
ロセスがどのようなオブジェクトを所有しているかにつ
いて矛盾した情報を様々なプロセスが有する瞬間の間に
プロセスがクラッシュする等のことが含まれている。い
ずれにせよ、Ｐｋは、Ａを自らの世界モデルから除去す
ることによってこの状況を修正する。何らかの理由によ
って、Ａが本当にその世界モデル内にあるべきである場
合には、Ａは結局はオブジェクト状態要約に入り、再び
現れる。

【０２４８】上記の機構は、すべてのプロセスが結局は
どのようなオブジェクトが存在しているかについて同意
することを確かめる最後の手段として、ＩＳＴＰに含ま
れている。

【０２４９】上記のものの重要なパラメータの１つは、
オブジェクト状態要約メッセージが送られる頻度であ
る。修理の素早さと使用する帯域幅の間にトレードオフ
がある。

【０２５０】要約の間隔が非常に小さい、例えば１秒の
何分の１かである、場合には、修理は非常に素早く行わ
れるが、その要約を送るのにはかなりの量の帯域幅が用
いられ、おそらくさらに悪いことには、しないほうが具
合がよい修理、というのもすぐに古くなるからである、
を行うために、資源が拡張される。

【０２５１】オブジェクト状態要約自体に用いられる帯
域幅は、変化したり新しく付け加えられたオブジェクト
がないとサーバが考える場合には全く要約を送らないよ
うにすることによって、低減することはできる。しか
し、これを行うと、各プロセスは、オブジェクト状態要
約メッセージがないことから自らが送っている情報がＳ
に達していないのではないかと推測する準備ができてい
なければならない。

【０２５２】要約の間隔が非常に大きい、例えば何秒も
であるばあいには、修理は適時にはならないが、要約メ
ッセージと修理の両方に用いられる帯域幅は最小にな
る。

【０２５３】パラメータであるＭａｘＤｅｌａｙを用い
て、要約の間隔が制御される、というのも、両方の間隔
が同じであることは道理にかなっているからである。順
番が狂ったメッセージについて情報を覚えておく見方か
ら、ＭａｘＤｅｌａｙを大きくしてもコストはほとんど
かからない。一方で、明示の修理が行われるよりも長い
待ち時間で順番の狂ったメッセージを取り扱っても、そ
れにはもしあるとしてもほとんど価値がない。特定のネ
ットワークおよびアプリケーション環境における実験の
みが、ＭａｘＤｅｌａｙの最適値を生み出すことができ
る。しかし、すべてのものが１から数秒の値であるのが
最良であると思われる。オブジェクト状態要約メッセー
ジはインクリメンタルであるので、自らが１００％の信
頼性で通信される場合にのみ信頼性を保証する。

【０２５４】ＴＣＰ輸送を行うコードは、十分留意して
これを保証しなければならない。ＴＣＰ通信に何らかの
割り込みが起これば、これは通信におけるブレークとし
て報告されて続いて完全な再スタートおよび再初期化が
行われるようにしなければならない。

【０２５５】ｉ．メッセージ損失の修理方法プロセスＰｊが送るＵＤＰメッセージは、途中で失われ
るかもしれないし、他のプロセスＰｋに向かっているか
もしれない。この２つの場合では、損失の修理方法が異
なる。

【０２５６】上で触れたように、プロセスＰｊは、自ら
が所有するオブジェクトＡについて自らが送出した１つ
またはそれより多い記述が、そういった記述がＳからの
オブジェクト状態要約メッセージ内に反映されないまま
時間が経過し過ぎる場合には、Ｓによって受け取られて
いないと判定する。以下の２つのうちの１つが一般に行
われている。

【０２５７】１番目は、オブジェクトテーブル内のＡに
ついての最高のカウンタ値がＣであり、ＰｊはＡが状態
Ｄにあることを知っていて、Ｄ＞Ｃであるということで
ある。これには、Ａが除去されているということを状態
Ｄが指定している場合が含まれる、ということに注意さ
れたい。その場合には、Ｐｊは、Ａの、状態Ｃが与えら
れた状態で理解することができる記述を、Ｓに送る。こ
れは、ＰｊからＳへのＴＣＰ接続を通じてオブジェクト
状態メッセージに入れて送られ、取っておくことが保証
される。

【０２５８】２番目は、Ａがオブジェクトテーブル内に
なく、ＰｊはＡが状態Ｄにあることを知っている、とい
うことである。これにはまた、考えてみれば、Ａが既に
除去されている状態も含まれる可能性がある、というこ
とに注意されたい。その場合には、Ｐｊは、Ａの、以前
の情報が全く与えられない状態で理解することができる
フルの記述を、Ｓに送る。ここでもまた、これは、Ｐｊ
からＳへのＴＣＰ接続を通じてオブジェクト状態メッセ
ージに入れて送られ、取っておくことが保証される。

【０２５９】これもまた上で触れたように、プロセスＰ
ｋは、オブジェクト状態要約メッセージを経由して、自
らが所有していないオブジェクトＡについての１つまた
はそれより多い記述を受け取っていないと判定する。要
約において、そのオブジェクトが削除されているという
ことを発見する場合には、要約内の情報のみをベースに
してこれを処理することができる。そうでない場合に
は、Ｐｋは、ＴＣＰを経由して、Ｐｋが既に知っている
ことを述べるオブジェクト状態要約メッセージをＳに送
る。Ｓは、ＴＣＰを経由して、適切な示差メッセージを
含むオブジェクト状態メッセージで返答する。すべての
失われた情報を更新するのに、１対のメッセージで十分
である。

【０２６０】Ｐｋが送るオブジェクト状態要約メッセー
ジは、構文的にＳが送るものと同一である。これはま
た、Ｐｋが自らが所有していないオブジェクトについて
知っていることを正確に要約しているという意味におい
て、意味的に同一である。しかし、これは異なる方法で
用いられる、というのも、Ｓにおいてオブジェクトテー
ブルを更新するのに用いられるのではないからである。
それどころか、ＳはＰｋにメッセージを送って、Ｐｋに
おける世界モデルのコピーを更新する。Ｐｋが送るオブ
ジェクト状態要約内のＳｅｎｄｅｒＩＤは、Ｐｋのｓｐ
Ｃｏｍオブジェクトであり、新しいオブジェクト入力も
Ｐｋが所有するオブジェクトへの参照も全くない、とい
うことにも注意されたい。

【０２６１】オブジェクトＡについてＳが知っている最
も最近の状態が、カウンタＥに対応していると仮定す
る。さらに、ＳがＰｋから、ＰｋがＡの状態Ｃ（Ｃ＜
Ｅ）についてのみ知っているということを指定するオブ
ジェクト状態要約メッセージを受け取ると仮定する。そ
の場合、Ｓは、Ａの、状態Ｅの、Ｃに関して理解するこ
とができる記述を、Ｐｋに送る。Ｐｋは、状態Ｃ＝０を
用いて、Ａについて何も知らないということを示すこと
ができる。これによって、ＳがＳのフルの記述を送るよ
うにされる。

【０２６２】各メッセージがＳとＰｋの間を伝わると
き、到着する各ＵＤＰメッセージから、ＳとＰｋの両方
がＡについてより知るようになっているかもしれない。
もしそうなら好都合なことである。いかなる瞬間におい
ても、ＳおよびＰｋは、自らが持っている最良の情報を
ベースに応答する。

【０２６３】上記はＩＳＴＰにおける明示のメッセージ
の修理の方法であるが、これが唯一の修理方法ではな
く、多くの状況においては最も重要な修理方法でさえも
ない、ということを理解することが重要である。特に、
迅速に変化するオブジェクトについての情報は、失われ
たメッセージを参照せずに理解することができる記述に
よって古くなってしまうことが多い。これによって、い
くつかの前の状態をベースにして理解することができる
示差メッセージを作り出す以外に余分な行動をとらず
に、多くの修理を効率的に行うことができる。

【０２６４】ｊ．各プロセスの通信グループへの参加方
法Ｐｊは、ある通信グループのサーバへのＴＣＰ接続を、
まだ存在していない場合には、開き、自らが接続を希望
していることを表すｓｐＣｏｍオブジェクトを含むオブ
ジェクト状態メッセージを送ることによって、そのグル
ープに参加する。他の世界モデルのオブジェクトとは異
なり、ｓｐＣｏｍオブジェクトはマルチキャストで通信
されることはなく、各プロセスとサーバの間のＴＣＰ接
続を経由してのみ通信される、ということに注意された
い。

【０２６５】ｓｐＣｏｍオブジェクトは、プロセス間で
共有される以下のフィールドを有する。

【０２６６】・・・何らかの共有オブジェクト内のすべ
てのフィールドであって、以下のものを含む。

【０２６７】ＳｈａｒｅＢｉｔｓ：１６ビット − 論
理値を表す。

【０２６８】Ｉｎｉｔｉａｌｉｚｅ：最低位から２番目
の桁のビット、ビット１ − １である場合には、初期
化を強制する。

【０２６９】Ｄｉｓｃｏｎｎｅｃｔ：ビット２ − １
である場合には、そのプロセスが切断していることを示
す。

【０２７０】ＰｒｏｃＡｄｄｒｅｓｓ：３２＋１６ビッ
ト − プロセスのインターネットアドレスおよびポー
ト番号。

【０２７１】ＭａｘＤｅｌａｙ：３２ビット − １週
間を法とする、ミリ秒での要求されたＭａｘＤｅｌａｙ
時間。

【０２７２】以下に説明するとおり、Ｉｎｉｔｉａｌｉ
ｚｅビットは、そのグループ内の通信を初期化または再
初期化するのに必要なすべての情報をサーバが送ること
を要求する、以下参照。

【０２７３】以下で説明するように、切断ビットは、そ
のプロセスが切断していることを示す。

【０２７４】ＰｒｏｃＡｄｄｒｅｓｓは、そのプロセス
に情報を送るときにそのサーバが用いる通信アドレスを
指定している。これは、用いるＴＣＰ通信リンクを識別
するのに役立つ。

【０２７５】ＭａｘＤｅｌａｙフィールドを用いて、１
つのプロセスにある特定のＭａｘＤｅｌａｙ値を要求す
ることができる。または、ゼロに設定して、その選択を
サーバに全く委ねることができる。ＩＳＴＰにおいて
は、すべてのプロセスがクライエントとサーバの両方に
なることができる、ということに注意されたい。プロセ
スは、自らが所有していないｓｐＣｏｍオブジェクトが
自らに送られるので、サーバになることを要求されてい
るということを発見する。この場合、そのプロセスは、
その要求を拒絶する決定をすることができ、その場合に
は、さらなる行動は不要である。そうでない場合には、
以下に説明するようにそのグループへの接続を開始す
る。プロセスは、ＴＣＰ接続を求める最初の要求もま
た、拒絶または応じる(forward)ことができる、という
ことに注意されたい。

【０２７６】あるグループ内での通信を求める要求に応
じるためには、サーバはまずそのプロセスに、場所入力
メッセージを送る。

【０２７７】場所入力メッセージのフィールドは、以下
のとおりである。

【０２７８】ＭｅｓｓａｇｅＴｙｐｅＩＤ：１６ビット
− 値３は、これが場所入力メッセージであることを
示す。

【０２７９】ＳｅｎｄｅｒＩＤ：３２ビット − 接続
を要求するｓｐＣｏｍの圧縮ＧＵＩＤ。

【０２８０】ＳｅｎｄＴｉｍｅ：３２ビット − １週
間を法とする、ミリ秒での送られる時間メッセージ。

【０２８１】Ｂｉｔｓ：１６ビット − 論理値を表
す。

【０２８２】Ｉｎｉｔｉａｌｉｚｅ：最低位から２番目
の桁のビット、ビット１ − １である場合には、初期
化を強制する。

【０２８３】Ｄｉｓｃｏｎｎｅｃｔ：ビット２ − １
である場合には、切断を強制する。

【０２８４】ＮｕｍｂｅｒＯｆＧＵＩＤＰｒｅｆｉｘｅ
ｓ：１６ビット − ＧＵＩＤＴａｂｌｅにおける接頭
部Ｇの数。

【０２８５】ＧＵＩＤＴａｂｌｅ：Ｇ個のＧＵＩＤＰｒ
ｅｆｉｘ入力 − それぞれ９６ビット。

【０２８６】ＧＵＩＤＴａｂｌｅＥｎｔｒｙＩｎｄｅ
ｘ：１６ビット − 圧縮ＧＵＩＤに用いる。

【０２８７】ＧＵＩＤＰｒｅｆｉｘ：８０ビット −
メッセージにおいて多くのＧＵＩＤに潜在的に共有され
ている接頭部。

【０２８８】ＭｕｌｔｉｃａｓｔＡｄｄｒｅｓｓ：３２
＋１６ビット − インターネットアドレスおよびポー
ト番号。

【０２８９】ＭａｘＤｅｌａｙ：３２ビット − １週
間を法とする、ミリ秒でのＭａｘＤｅｌａｙ時間。

【０２９０】ＭｅｓｓａｇｅＴｙｐｅＩＤ、Ｓｅｎｄｅ
ｒＩＤ、ＳｅｎｄＴｉｍｅ、ＮｕｍｂｅｒＯｆＧＵＩＤ
Ｐｒｅｆｉｘｅｓ、およびＧＵＩＤＴａｂｌｅは、他の
メッセージのタイプと同様である。要求を開始したｓｐ
Ｃｏｍオブジェクトを用いて、その要求に応じる場所入
力メッセージが識別される。

【０２９１】Ｉｎｉｔｉａｌｉｚｅビットは、そのグル
ープ内の通信を初期化または再初期化するのに必要なす
べての情報をそのプロセスＰｊが送るかまたは再送する
べきであるということを指定する、以下参照。

【０２９２】Ｄｉｓｃｏｎｎｅｃｔビットは、そのプロ
セスができるだけ速く切断するべきであるということを
示す。そのようにしない場合には、サーバが強制的にそ
のプロセスを駆逐するかもしれない。

【０２９３】このメッセージにおける重要なフィールド
は、ＭｕｌｔｉｃａｓｔＡｄｄｒｅｓｓである。これ
は、オブジェクトの変更についての情報を送ったり受け
取ったりするときに用いるアドレスを指定する。

【０２９４】ＭａｘＤｅｌａｙフィールドは、Ｍｕｌｔ
ｉｃａｓｔＡｄｄｒｅｓｓ上で通信されるメッセージに
ついてＰｊが用いるべきであるＭａｘＤｅｌａｙ値を指
定する。

【０２９５】サーバは、そのグループが用いるべきマル
チキャストのアドレスを選択する。このアドレスで他の
トラヒックからの干渉を検出する場合には、新しいアド
レスを選択して、そのグループのメンバーが用いている
アドレスを変更するべきであるということを指定する新
しい場所入力メッセージを送ることができる。

【０２９６】このチャネルを飛ばす方法は、劣悪なプロ
セスをそのグループから駆逐するのにも用いることがで
きる。

【０２９７】サーバはまた、用いるＭａｘＤｅｌａｙを
選択する。単一のサーバは、グループ全体についての１
つの固定値を選択することができる。または、サーバは
個々のプロセスの必要を評価してプロセスごとの遅延を
選択することができる。いずれにせよ、サーバがこうい
った決定を行って、あるプロセスについてのＭａｘＤｅ
ｌａｙと対応するオブジェクト状態要約メッセージの速
度が適切な同期をとるようにすることが重要である。

【０２９８】場所入力メッセージの直後に、サーバは、
そのグループが共有しているそれぞれのオブジェクトの
フルの記述を含む、オブジェクト状態メッセージを送
る。この、潜在的に非常に大きいメッセージが、Ｐｊに
おける世界モデルを現在の状態に初期化する。いったん
これが行われると、Ｐｊはあたかも常にこのグループ内
にいたかのように動き始めることができる。

【０２９９】オブジェクト状態メッセージの次に、サー
バは、Ｐｊにおけるオブジェクトテーブルを適切に初期
化するオブジェクト状態要約メッセージを送る。このメ
ッセージは、テーブル内のすべてのオブジェクトが新し
いので、やや大きい。

【０３００】場所入力メッセージを受け取るとすぐに、
プロセスは自らが所有するオブジェクトについての情報
を送出したり、他のオブジェクトについての情報を聞い
たりすることを開始することができる。しかし、サーバ
からダウンロードされた現在の状態を得るまでは、入っ
てくる示差メッセージを理解することはできない。

【０３０１】場所入力メッセージが初期化ビットを有し
ている場合には、Ｐｊは、指定されたアドレス上の、自
らが所有しているすべてのオブジェクトについてのフル
のメッセージを送出しなければならない。

【０３０２】上記のグループ接続方法について、特に触
れておく価値があるものがいくつかある。第１に、参加
は、実際的にできる限り速い。特に、ダウンロードは、
できるだけ速い信頼性の高い手段によって行われる。参
加にかかる完全な時間には、指定されたマルチキャスト
のアドレスへの接続も含まれる。これは、関連するルー
タがどのように動くかによってかなりの時間がかかる可
能性があるが、これはＩＳＴＰの支配下にはないことで
ある。

【０３０３】第２に、最初の情報のダウンロードが、過
去にＭａｘＤｅｌａｙ秒たたないうちに除去されたすべ
てのオブジェクトの記述を含み、これらのオブジェクト
についての遅れたメッセージによってＰｊ内にこれらが
誤って現れることがないようにしなければならない。

【０３０４】ｋ．各プロセスの通信グループからの退出
方法通信グループから退出するには、プロセスＰｊはまず、
自らが所有するいかなるオブジェクトを変更することも
中止し、従ってグループのアドレスにメッセージを送る
ことを中止しなければならない。次に待機して、サーバ
が、これらのオブジェクトの最終状態についての情報を
得ていることを確認し、必要であればこの情報をＴＣＰ
によってＳに送る。いったんＳが必要な情報を得ると、
ＰｊはＳに、切断ビットを有する適切なｓｐＣｏｍオブ
ジェクトを含むオブジェクト状態メッセージを送り、そ
の後単にＳとの接続をブレークする。

【０３０５】通常Ｐｊは、グループから退出する前に、
自らのすべてのオブジェクトを除去するか、自らの所有
権を他のプロセスに譲渡すると思われる。実行する所有
者がいない状態でオブジェクトが残ってしまう場合に
は、ＩＳＴＰはそれらがどうなるべきかを指定すること
はない。サーバは、それらのオブジェクトの存在を維持
するか、または除去するかを選択することができる。

【０３０６】プロセスＰｊがクラッシュしたり別の方法
でＳから切断される場合には、これはサーバＳによって
比較的速く検出することができる、というのも、サーバ
はもはやＰｊにオブジェクト状態要約を送ることができ
なくなるからである。ここでもまた、ＩＳＴＰは、この
状況においてはどうなるべきかを正確に指定することは
ない。上記のように、サーバは、ＰｊがすぐにＳに再接
続すると考えてＰｊのオブジェクトの存在を維持する
か、または除去するかを選択することができる。

【０３０７】ｌ．信頼性制御ＩＳＴＰにおける信頼性のレベル対速度の詳細なアプリ
ケーションレベル制御を行うために、それぞれの共有オ
ブジェクトには、以下の２つのさらなる共有制御ビット
が与えられる。

【０３０８】すべての共有オブジェクトは、プロセス間
で共有される以下のフィールドを有する。

【０３０９】ＳｈａｒｅＢｉｔｓ：１６ビット − 論
理値を表す。

【０３１０】ＦｏｒｃｅＲｅｌｉａｂｌｅ：最低位から
２番目の桁のビット、ビット１ −１である場合には、
変更がＴＣＰによってサーバを経由して通信されるよう
強制する。

【０３１１】ＩｎｈｉｂｉｔＲｅｌｉａｂｉｌｉｔｙ：
ビット２ − １である場合には、サーバが、変更が高
い信頼性で通信されるということを保証することが禁止
される。

【０３１２】ＦｏｒｃｅＲｅｌｉａｂｌｅビット、これ
はデフォールトによって非設定である、が、変更がこれ
から通信される時に１つのオブジェクト内に設定される
場合には、その変更はＴＣＰによってサーバに通信さ
れ、サーバはその変更を、ＴＣＰを用いてグループ内の
他のプロセスに通信する。これは、マルチキャストがシ
ミュレーションされなければならないときに用いられる
のと同種の通信である、以下参照。ＦｏｒｃｅＲｅｌｉ
ａｂｌｅビットは共有されなければならない、というこ
とに注意されたい、というのも、サーバはそれがオンで
ある時を知る必要があるからである。これは、マルチキ
ャストを用いて情報を通信するよりも時間がかかり、必
要な帯域幅も大きくなるが、グループ内のすべてのプロ
セスがその変更が起こったということを知るまでの時間
は最小になる。この通信の以下のいくつかの面は、わか
りにくいが重要である。

【０３１３】第１に、一般的に、この特徴はなるべく使
わないようにするということが意図されている。ある意
味では、ＩＳＴＰ全体の目的は、この種の通信を不要に
するということである。

【０３１４】第２に、Richard C. Watersによる１９９
５年１１月９日出願の、その参照により本明細書に組み
込まれる、米国特許出願番号第０８／５５６，２２７号
の主題であるビーコンは、ビーコンサーバを経由してこ
のスタイルで常に通信される。多くの状況において、ビ
ーコンは、プロセス間で信頼性の高い通信を行うのによ
りえり抜きの方法を提供する。

【０３１５】第３に、クライエントまたはサーバが、Ｔ
ＣＰを用いてオブジェクトの変更を通信するときにはい
つでも、通信される必要のあるすべてのオブジェクト
は、単一のオブジェクト状態メッセージ内に置くことに
よって、同時に一緒に通信される。これによって、すべ
ての変更が同時に受け取られるということが保証され
る。その結果、ＦｏｒｃｅＲｅｌｉａｂｌｅビットは同
期用に用いることができる。

【０３１６】いくつかのオブジェクトが一緒に変更さ
れ、ＦｏｒｃｅＲｅｌｉａｂｌｅビットがそれぞれのオ
ブジェクト内でオンに設定される場合には、すべての変
更は一緒に通信され、他のプロセスはすべて、それらの
変更を、ばらばらなものとしてではなく１グループとし
てみなす。もしＵＤＰが用いられているとすると、これ
を保証することは困難であろう、ということに注意され
たい、というのも、変更の中には他の変更よりも前に受
け取られるものがあり得、そういった変更を有するメッ
セージは失われ得るからである。

【０３１７】第４に、ＦｏｒｃｅＲｅｌｉａｂｌｅビッ
トによってＴＣＰが強制される場合には、帯域幅を最小
にするために、示差メッセージが用いられる。しかし、
それらのメッセージが常に受け取り手によって復号され
るということを保証するためには、単に最後のメッセー
ジだけではなく、もしあれば最後のＦｏｒｃｅＲｅｌｉ
ａｂｌｅメッセージに関して示差的でなければならな
い。この理由は、もし最後のメッセージが信頼性が低い
とすると、最後のメッセージを得ていない受け取り手が
あるかもしれないから、ということである。

【０３１８】その結果、ＦｏｒｃｅＲｅｌｉａｂｌｅビ
ットが、しばらくの間オフであった後オンに設定される
場合には、フルのオブジェクトメッセージを送らなけれ
ばならない可能性が高い。これによって、ＦｏｒｃｅＲ
ｅｌｉａｂｌｅビットを設定するコストが非常に高くな
り得る。オブジェクトは、最も最近高い信頼性で送られ
たカウンタ値が何かを指定する、関連するフィールドを
有さなければならない、または、システムのコアが、直
前のメッセージが高い信頼性で送られなかった場合には
いつでも、フルのメッセージを用いなければならない。

【０３１９】第５に、ＦｏｒｃｅＲｅｌｉａｂｌｅビッ
トがオンに設定される場合には、自動的にオフになるの
ではなくオンのままである。再びオフにしたい場合に
は、明示的に行わなければならない。

【０３２０】ＦｏｒｃｅＲｅｌｉａｂｌｅビット、これ
はデフォールトによって非設定である、が、１つのオブ
ジェクト内に設定される場合には、そのオブジェクトに
おける変更についての情報はマルチキャストによって通
信され、システムは、メッセージが受け取られることを
保証するのに費やす努力を最小にする。特に、Ｉｎｈｉ
ｂｉｔＲｅｌｉａｂｌｅビットを設定した変更について
サーバが発見する場合には、オブジェクト状態要約メッ
セージ内には新しいカウンタ値を含まない。Ｉｎｈｉｂ
ｉｔＲｅｌｉａｂｌｅビットは共有されなければならな
い、ということに注意されたい、というのも、サーバは
それがオンである時を知る必要があるからである。これ
は、各プロセスはマルチキャストの変更メッセージを得
るが、ＩｎｈｉｂｉｔＲｅｌｉａｂｌｅビットがオンで
ある変更についてのメッセージをたまたま捕らえそこな
ったプロセスは、自らが何かを捕らえ損なったというこ
とを知ることはなく、従ってこの情報を得ようとして資
源を費やすことはない、ということを意味する。この通
信の以下のいくつかの面は、わかりにくいが重要であ
る。

【０３２１】第１に、一般的に、この特徴はなるべく使
わないようにするということが意図されている。ある意
味では、ＩＳＴＰの重要な目的は、信頼性の高い通信を
安価にして、信頼性の低い通信を不要にするということ
である。それでも、非常に迅速な位置の更新等を送る場
合であって、情報が非常に迅速に古くなってしまい、情
報を信頼性の高いものにしても無駄である場合には、Ｉ
ｎｈｉｂｉｔＲｅｌｉａｂｌｅビットを設定することが
適切である。

【０３２２】第２に、サーバがいくつかの変更を得て、
そのうち最後のもののみにＩｎｈｉｂｉｔＲｅｌｉａｂ
ｌｅが設定されている場合には、サーバの次のオブジェ
クト状態要約メッセージに最後から２番目の変更のカウ
ンタを含まなければならない、という点において複雑で
ある。サーバは、ＩｎｈｉｂｉｔＲｅｌｉａｂｌｅが設
定された変更を受け取る時には自らのオブジェクトテー
ブルを更新しない、ということによってこれを達成する
ことができる。

【０３２３】第３に、ＩｎｈｉｂｉｔＲｅｌｉａｂｌｅ
を用いる場合には、きっと示差メッセージも用いたいと
思われている、ということにおいても複雑である。しか
し、こういったメッセージは、最後の信頼性の高いメッ
セージにずっとさかのぼって高い信頼性で示差的である
はずであり、常に復号できるはずである。または、各プ
ロセスは、変更が起こっているということを知らせるオ
ブジェクト状態要約メッセージを得ていない時であって
も、復号できない示差メッセージを得ているときには、
サーバからの更新を求めることができるようにならなけ
ればならない。後者の方はＩＳＴＰによって確かに容認
されているが、誤りが起きやすく、支援できない。

【０３２４】第４に、１つのオブジェクトについてＩｎ
ｈｉｂｉｔＲｅｌｉａｂｌｅが常に設定されている場合
であっても、高い信頼性で送らなければならない変更が
ある。特に、１つのオブジェクトの最初の創造およびそ
れを結局除去するときには、常に高い信頼性で通信され
る。もしこれらの変更が高い信頼性で送られないとする
と、各プロセスは完全に混乱してしまうかもしれない。

【０３２５】第５に、ＩｎｈｉｂｉｔＲｅｌｉａｂｌｅ
ビットがオンに設定される場合には、自動的にオフにな
るのではなくオンのままである。再びオフにしたい場合
には、明示的に行わなければならない。

【０３２６】第６に、単にカウンタ値を変更しないだけ
でも、ＩｎｈｉｂｉｔＲｅｌｉａｂｌｅビットには同様
の影響があるが、そうすると、示差メッセージが正しく
働くことも、各プロセスが、重複するメッセージから来
る重複するカウンタ値を有する記述を扱うこともできな
くなる。

【０３２７】ＦｏｒｃｅＲｅｌｉａｂｌｅおよびＩｎｈ
ｉｂｉｔＲｅｌｉａｂｌｅビットが共に１つのオブジェ
クト内に設定されている場合には、変更はＴＣＰおよび
マルチキャストのＵＤＰの両方によって送られる。これ
は帯域幅の点ではコストが高いが、通信の待ち時間が最
小になること、および最小時間内でのフルの信頼性が保
証される。

【０３２８】ｍ．所有権の譲渡ＩＳＴＰの見方から、比較的小さなことではあるが、オ
ブジェクトの所有権は変更することができる。これは、
現在所有しているプロセスＰｊに、所有者のフィールド
がどれか他のプロセスＰｋに変更されたメッセージを送
出させることによって行われる。しかし、以下のいくつ
かのことを覚えておく必要がある。

【０３２９】第１に、所有権の変更後は、Ｐｊはそのオ
ブジェクトについていかなる他のメッセージも送出する
ことはできない。ただし、Ｐｊは、必要な限り長く、所
有権が変化したオブジェクトの状態を覚えておいて、サ
ーバＳがその変更またはその後の状態について知ること
を保証しなければならない。

【０３３０】いったんそうなると、Ｐｊのそのオブジェ
クトについてのすべての責任は終わる。これが進行中お
よびその後、Ｐｋがそのオブジェクトについてのメッセ
ージを送出することができる。

【０３３１】第２に、上記説明において、１つのオブジ
ェクトを所有しているプロセスＰｊについて述べるとき
にはいつでも、その意味するところは、プロセスＰｊが
自らがオブジェクトを所有していると「思う」とき、と
いうことである。すなわち、プロセス内の世界モデル
が、そのプロセスがそのオブジェクトを所有していると
指定しているときである。これは、所有権の何かグロー
バルな概念とは別個のものである。

【０３３２】プロセスＰｊがＰｋに所有権を引き渡す場
合には、Ｐｊは、Ｐｋまたはいかなる他のプロセスがＰ
ｋが所有者であるということを知ることができるよりも
前に、自らがもはや所有者ではないということを知って
いる、ということに注意されたい。従って、どのプロセ
スも自らが１つの与えられたオブジェクトの所有者であ
ると考えていない短い期間が存在する。しかし、２つの
プロセスが両方とも１つのオブジェクトの所有者である
と考える、ということは起こり得ない。

【０３３３】もし、ＭａｘＤｅｌａｙよりも後の、順番
の狂ったメッセージが処理されるとすると、その結果と
して、所有者が多数、同時に存在する、等の異様なこと
が生じる可能性がある、ということに注意されたい。

【０３３４】ｎ．模擬マルチキャスト簡単のために、上記では、１つのグループ内のすべての
プロセスが互いにマルチキャスト通信をすることができ
ると仮定した。しかし、インターネットの現在の状態で
は、これは多くの理由で不可能である。理由の１つは、
マルチキャストが可能でないルータが多く、マルチキャ
ストのトラヒックが通過できない「防火壁」が多い、と
いうことである。従って、ＩＳＴＰには、実際のＵＤＰ
マルチキャストではなくＴＣＰを用いた模擬マルチキャ
ストを経由して通信を行うことができる、ということが
含まれる。

【０３３５】模擬マルチキャストモードにおいては、プ
ロセスＰｊは、自らのすべての通信を、他のプロセスＰ
ｋと直接ではなく、サーバＳと行う。特に、上記仮定で
はＵＤＰマルチキャストによって送ることになっている
オブジェクト状態メッセージはすべて、その代わりに、
ＴＣＰ接続を通じて直接サーバに送られる。同様に、上
記仮定ではマルチキャストによってＰｊが受け取ること
になっているメッセージはすべて、その代わりに、ＴＣ
Ｐ接続を通じて受け取られる。これを促進するために、
各メッセージが、どのような通信チャネルに到着しよう
とも正確に解釈されるように、ＩＳＴＰにおいてすべて
が手配されている。

【０３３６】模擬マルチキャストモードにおいては、Ｉ
ＳＴＰは本質的には中央サーバモードで動作し、他の中
央サーバの設計よりも優れた通信速度上の利点はない。
このモードは、与えられたプロセスがグループ内の他の
プロセスとマルチキャスト通信をすることができない場
合に、劣化が適切なものになるようにとのためだけに、
ＩＳＴＰに含まれている。

【０３３７】プロセスの１グループが与えられたとする
と、マルチキャストの可能性を含む状況は、非常に複雑
である、ということに注意されたい。すなわち、サブグ
ループ内でマルチキャストが可能な多数の接続されてい
ないサブグループ、マルチキャストを送ることはできる
が受け取ることはできない、そして、受け取ることはで
きるが送ることはできない、プロセス、および、各プロ
セスがある瞬間にはマルチキャスト通信が可能であるが
他の瞬間には不可能な、動的な変更、が存在している。
ＩＳＴＰは、この状況すべてにおいてマルチキャストを
最適に用いようとするものではなく、すべての状況にお
いて正確に働きつつ、いくつかのよくある状況において
うまく働こうとするものである。

【０３３８】特に、通信グループは以下の２つの部分に
分割される。１つは、サーバを含まなければならない部
分であり、すべてのプロセスが、他のそれぞれにおよび
他のそれぞれからマルチキャストで送り受け取ることが
できる部分である。残りのもう１つは、すべての通信に
ＴＣＰが用いられる部分である。従って、それぞれのプ
ロセスＰｊには、マルチキャスト通信を用いるかそうで
ないかのどちらかのタグがついている。マルチキャスト
可能から不可能への自動切り替えは支援されるが、その
逆の自動支援はない。

【０３３９】以下では、模擬マルチキャストの方法、模
擬マルチキャストの使用のトリガの方法、および、１つ
のプロセスが模擬マルチキャストに切り替えられた後マ
ルチキャスト動作を再開する方法、を詳細に正確に説明
する。

【０３４０】場所入力オブジェクトは、上で説明してい
ない以下のさらなるビットフィールドを有している。

【０３４１】場所入力メッセージのフィールドは、以下
のとおりである。

【０３４２】Ｂｉｔｓ：１６ビット − 論理値を表
す。

【０３４３】ＵｓｅＴＣＰ：ビット３ − １である場
合には、すべての通信をＴＣＰ経由に強制する。

【０３４４】プロセスＰｊが、ＵｓｅＴＣＰビットがオ
ンの状態で場所入力メッセージを受け取る場合には、自
らの関連する出力をマルチキャストを経由して送ること
を中止し、その代わりに、そのすべてを、ＴＣＰを経由
して直接サーバに送る。ＵｓｅＴＣＰビットがオンであ
る場合には、ＭｕｌｔｉｃａｓｔＡｄｄｒｅｓｓのフィ
ールドの値は無関係である。Ｐｊは、そのアドレスへの
接続を開こうとはせず、その上で送ることも受け取るこ
ともしない。マルチキャスト接続が開いていた場合に
は、Ｐｊはそれを閉じる。

【０３４５】ＵｓｅＴＣＰがオンの状態の場所入力メッ
セージが到着して通信が開始されたり、通信の真っ最中
に到着するかもしれない、ということに注意されたい。
Ｐｊが次にＵｓｅＴＣＰがオフの状態の場所入力メッセ
ージを受け取る場合には、Ｐｊはマルチキャストの使用
を再開しようとする。

【０３４６】サーバＳが、プロセスＰｊに、マルチキャ
ストを使用しないように命令している場合には、Ｓは他
のプロセスＰｋから生じたＰｊへの情報をすべて、ＴＣ
Ｐを経由して送り、Ｐｊから情報を取って、グループ内
のマルチキャストが可能な各プロセスにそれをマルチキ
ャストする。

【０３４７】１つのプロセスＰｊがマルチキャストを用
いるかどうかの判断は、ＰｊとサーバＳが一緒になって
行う。直接の要求によって、どちらかの当事者が一方的
に判断してもよい。特に、Ｓは、上述のように、Ｐｊに
マルチキャストを用いないように命令することができ
る。同様に、Ｐｊは、マルチキャストが用いられないよ
うに要求することができる。この目的のために、ｓｐＣ
ｏｍオブジェクトにおいて、上では説明していないさら
なるビットが存在する。

【０３４８】ｓｐＣｏｍオブジェクトは、プロセス間で
共有される以下のフィールドを有する。

【０３４９】ＳｈａｒｅＢｉｔｓ：１６ビット − 論
理値を表す。

【０３５０】ＵｓｅＴＣＰ：ビット３ − １である場
合には、すべての通信をＴＣＰ経由に強制する。

【０３５１】サーバが、ＵｓｅＴＣＰビットがオンの状
態でｓｐＣｏｍオブジェクトを受け取る場合には、サー
バはこれを、ＵｓｅＴＣＰビットがオンでもある場所入
力メッセージで応答せよという非常に強い要求であると
みなすべきである。プロセスＰｊは、自らがマルチキャ
スト可能ではないということを知る相当の理由がある場
合には、このビットの初期設定をオンにしておくべきで
ある。さもなければ、以下で説明するように、ＩＳＴＰ
がＰｊを自動的にＴＣＰモードに切り替える前に、低品
質の通信の期間が存在してしまう。

【０３５２】このようなｓｐＣｏｍを送って、通信を開
始したり、通信中に変更をトリガすることができる、と
いうことに注意されたい。ｓｐＣｏｍが、ＴＣＰに、そ
の後にマルチキャスト通信の再開を要求するものが続く
よう要求することが可能である。上記の各ビットを用い
て、Ｐｊがそのグループに参加した瞬間から、Ｐｊまた
はＳのいずれかが、ＴＣＰの使用を指定することができ
る。しかし、もっと楽天的に、最初はマルチキャストを
試みて、マルチキャストができない場合にのみＴＣＰに
切り替えるようにしたいと思うことが多いかもしれな
い、と思われる。これを行うには、ＰｊおよびＳがマル
チキャストでスタートして、通信におけるエラー率を観
測する。

【０３５３】Ｐｊが、Ｓからのオブジェクト状態要約メ
ッセージをベースにして、そのマルチキャスト出力がＳ
に到着する割合が低いということに気づく場合には、Ｐ
ｊは、ＴＣＰへの切り替えを要求する新しいｓｐＣｏｍ
を送るべきである。

【０３５４】Ｓが、Ｐｊからのオブジェクト更新の要求
をベースにして、他のプロセスからＰｊに送られるデー
タがＰｊに到着する割合が低いということに気づく場合
には、Ｓは、ＰｊをＴＣＰモードに切り替える新しい場
所入力メッセージを送るべきである。性能を最適化する
ためには、Ｓは、グループ内のプロセスのそれぞれの１
対の間で行われている通信を個々に監視するべきである
が、大部分の状況においてはこれはおそらく不要であろ
う。

【０３５５】上記のことを用いれば、マルチキャストか
らＴＣＰモードに動的に切り替えるのは容易である。し
かし、いったん１つのプロセスＰｊがＴＣＰモードにな
ると、Ｐｊとのマルチキャスト通信の試みはそれ以上は
なくなってしまい、従って、マルチキャストモードに切
り替え戻してもうまくいくと判断するベースがなくなっ
てしまう。しかし、このような判断を行うのに用いるこ
とができる様々な方法がある。

【０３５６】第１に、サーバが時々Ｐｊをマルチキャス
トモードに切り替え戻してうまく行くかどうかを確認す
ることが可能である。これを行うことの代償は、通信の
有効性が低減する期間が長くなる、ということであろ
う。従って、Ｓがこの方法をとる場合には、一貫して失
敗(failure)する場合には、確認の試みの頻度を下げる
べきである。

【０３５７】第２に、ＴＣＰ動作の間、Ｐｊのマルチキ
ャストポートを開いたままにしておいて、何か実験的な
トラヒックを特に作り出して、マルチキャスト通信がう
まく行きだしているかどうかを評価することが可能であ
る。第１のものよりもこちらの方が複雑ではあるが、ア
プリケーションに低品質の通信になる期間ができるのを
強制することなく、マルチキャスト接続を評価すること
ができる。

【０３５８】マルチキャストがうまくいっていたのに突
然うまく行かなくなった場合には、上の方法のうちの１
つを用いるのがよい考えかもしれない。しかし、マルチ
キャストがうまく行くことがなかった場合には、これら
の方法をわざわざ用いてみる価値はおそらくないであろ
う。

【０３５９】ｏ：場所（Locales）簡単のために、上記では、それぞれのプロセスＰｊが単
一の通信グループのみに参加すると仮定した。しかし、
このグループの大きさは、サーバが扱う(serve)ことが
できるプロセスの数によって制限されてしまう。これ
は、大規模化可能性(scalability)に対する基本的な制
限である。ＩＳＴＰの重要な面の１つは、１９９５年８
月２８日に出願されその参照によって本明細書に組み込
まれる、Barrus J. W.およびWaters R. C.による米国特
許出願番号第０８／５２０，０９９号、「場所を利用し
てバーチャル環境を設計するシステム」に説明されてい
るように、１つのバーチャル世界を「場所」と呼ばれる
多くの塊(chunks)に分けることによって、大規模化可能
性を達成する、ということである。それぞれの場所は、
別個のマルチキャスト通信グループと関連しており、１
つの与えられたプロセスは、これらグループのうちのい
くつかに属すると思われる。

【０３６０】場所の重要な面は、上述のすべてのもの
が、１回だけではなく、場所当たりで動作する、という
ことである。例えば、１つの与えられたプロセスは、１
つのサーバへの接続を１つ有しているだけではなく、い
くつかのサーバへの接続をいくつか有している。

【０３６１】同様に、１つのプロセスは１つのｓｐＣｏ
ｍを有しているだけではなく、いくつか有している。世
界モデル内のそれぞれのオブジェクトは、明示のフィー
ルドによって、多くても１つの場所内にあるものとして
識別される。１つのオブジェクトに関するすべての通信
は、そのオブジェクトが入っている場所に関連する通信
グループ内で起こる。通信グループを支配する、マルチ
キャストのアドレスを含む情報は、関連する場所オブジ
ェクト内にキャッシュされる。

【０３６２】ｓｐＣｏｍオブジェクトは、他のいかなる
ものとも同様に、場所内にある。それらによって、この
場所と関連する通信グループ内の通信がトリガされる。

【０３６３】それぞれの場所は、１つのサーバと関連し
ている。１つの与えられたサーバは、いくつかの場所を
扱ってもよい。場所オブジェクトは、とりわけ、どのよ
うなサーバのプロセスがその場所を扱うかを指定する。

【０３６４】一般的に、場所通信グループを多数同時に
有しても、基本的に複雑になることはない。しかし、取
り組まなければならない重要な問題が１つある−−−１
つのオブジェクトが１つの場所から別の場所に動くとき
に何が起こるか、ということである。

【０３６５】第１に、１つのオブジェクトが場所を変更
するときにはいつでも、そのオブジェクトを記述するフ
ルのメッセージを新しい方の場所に送らねばならず、そ
のオブジェクトが古い方の場所を離れたということを指
定するひょっとしたら示差のメッセージを、古い方の場
所に送らなければならない。

【０３６６】第２に、オブジェクトの除去についてＭａ
ｘＤｅｌａｙ時間の間覚えておかなければならないのと
同様に、１つの場所から１つのオブジェクトが離れると
いうことも、ＭａｘＤｅｌａｙ時間の間覚えておいて、
順番の狂ったメッセージによって誤ってオブジェクトが
その場所に再び現れることがないようにしなければなら
ない。

【０３６７】第３に、１つの場所内のオブジェクトにつ
いての情報の最初のダウンロードには、最近除去された
オブジェクトについての情報が含まれなければならない
のと同様に、その場所を最近離れたオブジェクトについ
ての情報も含まれなければならない。

【０３６８】第４に、提案されるＭａｘＤｅｌａｙ間隔
は、場所オブジェクトの一部として指定されることがで
きる。

【０３６９】本発明のいくつかの実施の例およびその修
正や変形を説明したが、当業者には、前述のことは単に
例示的であるに過ぎず、限定的なものではなく、例とし
てのみ述べられたものである、ということが明らかであ
ろう。当業者であれば、多くの修正および他の実施の例
を考えることが可能であり、それらは本発明の範囲内に
あると考えられる。本発明の範囲は、添付の特許請求の
範囲およびそれらの同等物によってのみ限定される。

【０３７０】

【発明の効果】この発明に係る通信システムは、以上説
明したとおり、１グループのユーザの間でオブジェクト
状態情報を高速で効率的におよび高い信頼性で通信する
通信システムにおいて、ネットワーク及びそれぞれが前
記ネットワークとつながれたコンピュータを有し前記ネ
ットワークのノードにおける複数のユーザと、前記ユー
ザのそれぞれにおいて記憶されそれぞれのコンピュータ
につながれたオブジェクトを含む世界モデルと、前記世
界モデルのオブジェクトが変化するように、該世界モデ
ルのオブジェクトを変更することによって、前記ユーザ
において前記世界モデルを変更する手段と、変化したオ
ブジェクトの現在の状態を損失の多い直接のリンクを通
じて他のユーザに通信するメッセージを含む、前記オブ
ジェクトの現在の状態を前記他のユーザに迅速に通信す
る手段と、ユーザにおいてオブジェクト状態を記述する
メッセージが失われた時を検出する手段と、前記損失の
多い直接のリンクにつながれて、前記オブジェクト状態
を記憶し、ユーザが要求した場合にはそのユーザに最新
のオブジェクト状態を損失のないリンクを通じて送信す
るサーバとを備え、それによって、前記損失の多いリン
クを通じて送信され失われた情報は、前記サーバからの
情報によって回復することができるので、高速で効率的
におよび高い信頼性で通信することができるという効果
を奏する。

【０３７１】また、この発明に係る通信システムは、以
上説明したとおり、前記サーバが、オブジェクト状態要
約メッセージを前記ユーザに送る手段を含み、オブジェ
クト状態を記述するメッセージが失われた時を検出する
前記手段が、前記要約メッセージをユーザにおける現在
のオブジェクト状態と比較する手段を含み、情報の再送
信が、すべての失われたメッセージを再送信することで
はなく、オブジェクトについて最も最新の情報を得るこ
とをベースに行われるようになっているので、高速で効
率的におよび高い信頼性で通信することができるという
効果を奏する。

【０３７２】また、この発明に係る通信システムは、以
上説明したとおり、前記要約メッセージが、それぞれの
オブジェクトについて、前記サーバが知っている状態の
最新版を識別するカウンタ値を指定するので、高速で効
率的におよび高い信頼性で通信することができるという
効果を奏する。

【０３７３】また、この発明に係る通信システムは、以
上説明したとおり、前記要約メッセージが、最後の要約
メッセージから変化したオブジェクトのみの状態を指定
する示差メッセージであるので、高速で効率的におよび
高い信頼性で通信することができるという効果を奏す
る。

【０３７４】また、この発明に係る通信システムは、以
上説明したとおり、前記オブジェクト状態メッセージ
が、直前の状態から異なっている状態の部分のみを指定
する示差メッセージであるので、高速で効率的におよび
高い信頼性で通信することができるという効果を奏す
る。

【０３７５】また、この発明に係る通信システムは、以
上説明したとおり、前記オブジェクト状態メッセージ
が、前のＮ（Ｎは１よりも大きい数）個の状態のうちの
いずれかから異なっている状態の部分のみを示す示差メ
ッセージであり、それによって、直前のメッセージが失
われた時であっても示差メッセージを解釈することがで
き、すべての失われたメッセージを再送信する必要がな
いようになっているので、高速で効率的におよび高い信
頼性で通信することができるという効果を奏する。

【０３７６】また、この発明に係る通信システムは、以
上説明したとおり、前記サーバが、前記オブジェクト状
態における変更の要約を前記ユーザに送信する手段を含
み、それぞれのユーザにおいて前記サーバからの要約を
前記損失の多い直接のリンクの結果として前記ユーザに
おいて記憶されている同様の要約と比較し、従って失わ
れたメッセージを検出し、前記失われたメッセージの検
出に応答して更新されたメッセージを前記サーバに送信
させる手段をさらに含むので、高速で効率的におよび高
い信頼性で通信することができるという効果を奏する。

【０３７７】また、この発明に係る通信システムは、以
上説明したとおり、前記オブジェクトが、グラフィック
のオブジェクトであるので、高速で効率的におよび高い
信頼性で通信することができるという効果を奏する。

【０３７８】この発明に係る通信システムは、以上説明
したとおり、１グループのプロセスの間でオブジェクト
状態情報を高速で効率的におよび高い信頼性で通信する
通信システムにおいて、ネットワーク及びそれぞれが前
記ネットワークとつながれたコンピュータを有し前記ネ
ットワークのノードにおける複数のユーザと、前記ユー
ザのそれぞれにおいて記憶されそれぞれのコンピュータ
につながれたオブジェクトを含む世界モデルと、前記世
界モデルのオブジェクトが変化するように、該世界モデ
ルのオブジェクトを変更することによって、前記ユーザ
において前記世界モデルを変更する手段と、変化したオ
ブジェクトの現在の状態を損失の多い直接のリンクを通
じて他のユーザに通信するメッセージを含む、前記オブ
ジェクトの現在の状態を前記他のユーザに迅速に通信す
る手段とを備え、前記オブジェクト状態メッセージが、
前のＮ（Ｎは１よりも大きい数）個の状態のうちのいず
れかから異なっている状態の部分のみを示す示差メッセ
ージであり、それによって、直前のメッセージが失われ
た時であっても示差メッセージを解釈することができ、
すべての失われたメッセージを再送信する必要がないよ
うになっているので、高速で効率的におよび高い信頼性
で通信することができるという効果を奏する。

【０３７９】また、この発明に係る通信システムは、以
上説明したとおり、ユーザにおいて、順番が狂って所定
量の時間よりも大きく遅延して到着するオブジェクト状
態を記述するメッセージを拒絶し、それによって前記ユ
ーザがオブジェクトが除去されたという記録を維持して
おかなければならない期間を限定し、該オブジェクトに
ついての順番が狂ったメッセージを拒絶することができ
るようにする手段をさらに含むので、高速で効率的にお
よび高い信頼性で通信することができるという効果を奏
する。

【０３８０】また、この発明に係る通信システムは、以
上説明したとおり、ユーザの前記グループが動的に変化
することができ、前記サーバが、ユーザが要求した場合
にはそのユーザに世界モデルにおけるすべてのオブジェ
クトの現在の状態をダウンロードする手段を含むので、
高速で効率的におよび高い信頼性で通信することができ
るという効果を奏する。

【０３８１】また、この発明に係る通信システムは、以
上説明したとおり、前記損失の多い直接の通信リンク
が、マルチキャストを利用しているので、高速で効率的
におよび高い信頼性で通信することができるという効果
を奏する。

【０３８２】また、この発明に係る通信システムは、以
上説明したとおり、前記サーバが、直接的なマルチキャ
スト通信が不可能な前記ユーザにマルチキャスト通信を
シミュレーションする手段を含むので、高速で効率的に
および高い信頼性で通信することができるという効果を
奏する。

【０３８３】また、この発明に係る通信システムは、以
上説明したとおり、前記オブジェクトがＧＵＩＤによっ
て識別され、ＧＵＩＤのオブジェクトへの割り当てが、
与えられたユーザによって修正されたすべてのオブジェ
クトについてのＧＵＩＤが多くのビットを共通に有する
ようにし、それによって、表されるべきオブジェクト状
態を記述するメッセージがより完成するようにする手段
を含むので、高速で効率的におよび高い信頼性で通信す
ることができるという効果を奏する。

【０３８４】さらに、この発明に係る通信システムは、
以上説明したとおり、オブジェクト状態を記述する前記
示差メッセージを作り出す前記手段が、前記Ｎ個の前の
状態のそれぞれの間での送信においてオブジェクトのど
の構成要素が変化したかを表すビットマスクを含み、そ
れによって、該ビットマスクを論理和演算と組み合わせ
ることによって、オブジェクト状態を記述する前記示差
メッセージにどのような情報を含む必要があるかを迅速
およびコンパクトに判定することができるので、高速で
効率的におよび高い信頼性で通信することができるとい
う効果を奏する。

【図面の簡単な説明】

【図１】この発明の実施の形態１に係る、参加してい
るノードのうちの１つによって共有バーチャル世界に付
け加えらている新しいオブジェクトの概略図である。

【図２】共有世界モデルを実施する中央サーバの方法
の概略図である。

【図３】ピアツーピアのメッセージング、すなわちマ
ルチキャスト、を用いて、フルに分散された世界モデル
をＤＩＳのスタイルで実行する概略図である。

【図４】マルチキャストを用いてオブジェクト更新情
報を１つのグループのピアの間で共有し、サーバがそれ
を聞いていることを示す、本発明の概略図である。

【図５】サーバがどのようにそれぞれのクライエント
のノードと相互動作してオブジェクトレベルでシステム
全体の信頼性を保証しているかを示す、本発明の概略図
である。

【図６】１つのメッセージが直前のメッセージに依存
してオブジェクト状態の変更の従来技術による符号化を
形成する、一連の示差メッセージを示す、概略図であ
る。

【図７】前のメッセージが失われたり遅れている場合
に、示差メッセージが１つより多い前のメッセージをベ
ースにして、データが再構成できるようにする、本シス
テムの概略図である。

【図８】それぞれの時間段階においてオブジェクトの
フィールドが変化する、オブジェクトの一連の経時変化
を示す図である。

【図９】図８のオブジェクトのＴ４におけるフルの状
態の記述のリスティングであり、時間Ｔ４において存在
するフィールドを示す図である。

【図１０】図８のオブジェクトの、時間Ｔ４におけ
る、直前の、時間Ｔ３における状態に関する状態を示す
リスティングであって、変更を示す図である。

【図１１】図８のオブジェクトの、時間Ｔ４におけ
る、３つの前の状態のうちのどれかに関する状態を示す
リスティングであって、フィールドＦ３およびフィール
ドＦ５の変更を示す図である。

【符号の説明】

１０、１２、１４コンピュータ、２０、２２、２４
モニタ、２６、２８、３０、４０世界モデル、４２、
５０サーバ、５２未着データ検出装置、５６示差
メッセージ、５８オブジェクト状態要約メッセージ。

───────────────────────────────────────────────────── フロントページの続き (71)出願人 597067574 201 ＢＲＯＡＤＷＡＹ，ＣＡＭＢＲＩＤＧＥ，ＭＡＳＳＡＣＨＵＳＥＴＴＳ 02139，Ｕ．Ｓ．Ａ. (72)発明者リチャード・シー・ウォーターズアメリカ合衆国、マサチューセッツ州、コンコード、ディーコン・ヘインズ・ロード 266 (72)発明者デビッド・アンダーソンアメリカ合衆国、マサチューセッツ州、ベルモント、フェアビュー・レイン 70

Claims

【特許請求の範囲】

【請求項１】１グループのユーザの間でオブジェクト
状態情報を高速で効率的におよび高い信頼性で通信する
通信システムにおいて、ネットワーク及びそれぞれが前記ネットワークとつなが
れたコンピュータを有し前記ネットワークのノードにお
ける複数のユーザと、前記ユーザのそれぞれにおいて記憶されそれぞれのコン
ピュータにつながれたオブジェクトを含む世界モデル
と、前記世界モデルのオブジェクトが変化するように、該世
界モデルのオブジェクトを変更することによって、前記
ユーザにおいて前記世界モデルを変更する手段と、変化したオブジェクトの現在の状態を損失の多い直接の
リンクを通じて他のユーザに通信するメッセージを含
む、前記オブジェクトの現在の状態を前記他のユーザに
迅速に通信する手段と、ユーザにおいてオブジェクト状態を記述するメッセージ
が失われた時を検出する手段と、前記損失の多い直接のリンクにつながれて、前記オブジ
ェクト状態を記憶し、ユーザが要求した場合にはそのユ
ーザに最新のオブジェクト状態を損失のないリンクを通
じて送信するサーバとを備え、それによって、前記損失の多いリンクを通じて送信され
失われた情報は、前記サーバからの情報によって回復す
ることができる通信システム。
【請求項２】前記サーバは、オブジェクト状態要約メ
ッセージを前記ユーザに送る手段を含み、オブジェクト
状態を記述するメッセージが失われた時を検出する前記
手段が、前記要約メッセージをユーザにおける現在のオ
ブジェクト状態と比較する手段を含み、情報の再送信
が、すべての失われたメッセージを再送信することでは
なく、オブジェクトについて最も最新の情報を得ること
をベースに行われるようになっている請求項１記載の通
信システム。
【請求項３】前記要約メッセージは、それぞれのオブ
ジェクトについて、前記サーバが知っている状態の最新
版を識別するカウンタ値を指定する請求項２記載の通信
システム。
【請求項４】前記要約メッセージは、最後の要約メッ
セージから変化したオブジェクトのみの状態を指定する
示差メッセージである請求項２記載の通信システム。
【請求項５】前記オブジェクト状態メッセージは、直
前の状態から異なっている状態の部分のみを指定する示
差メッセージである請求項１記載の通信システム。
【請求項６】前記オブジェクト状態メッセージは、前
のＮ（Ｎは１よりも大きい数）個の状態のうちのいずれ
かから異なっている状態の部分のみを示す示差メッセー
ジであり、それによって、直前のメッセージが失われた
時であっても示差メッセージを解釈することができ、す
べての失われたメッセージを再送信する必要がないよう
になっている請求項１記載の通信システム。
【請求項７】前記サーバは、前記オブジェクト状態に
おける変更の要約を前記ユーザに送信する手段を含み、
それぞれのユーザにおいて前記サーバからの要約を前記
損失の多い直接のリンクの結果として前記ユーザにおい
て記憶されている同様の要約と比較し、従って失われた
メッセージを検出し、前記失われたメッセージの検出に
応答して更新されたメッセージを前記サーバに送信させ
る手段をさらに含む請求項６記載の通信システム。
【請求項８】前記オブジェクトは、グラフィックのオ
ブジェクトである請求項１記載の通信システム。
【請求項９】１グループのプロセスの間でオブジェク
ト状態情報を高速で効率的におよび高い信頼性で通信す
る通信システムにおいて、ネットワーク及びそれぞれが前記ネットワークとつなが
れたコンピュータを有し前記ネットワークのノードにお
ける複数のユーザと、前記ユーザのそれぞれにおいて記憶されそれぞれのコン
ピュータにつながれたオブジェクトを含む世界モデル
と、前記世界モデルのオブジェクトが変化するように、該世
界モデルのオブジェクトを変更することによって、前記
ユーザにおいて前記世界モデルを変更する手段と、変化したオブジェクトの現在の状態を損失の多い直接の
リンクを通じて他のユーザに通信するメッセージを含
む、前記オブジェクトの現在の状態を前記他のユーザに
迅速に通信する手段とを備え、前記オブジェクト状態メッセージは、前のＮ（Ｎは１よ
りも大きい数）個の状態のうちのいずれかから異なって
いる状態の部分のみを示す示差メッセージであり、それ
によって、直前のメッセージが失われた時であっても示
差メッセージを解釈することができ、すべての失われた
メッセージを再送信する必要がないようになっている通
信システム。
【請求項１０】ユーザにおいて、順番が狂って所定量
の時間よりも大きく遅延して到着するオブジェクト状態
を記述するメッセージを拒絶し、それによって前記ユー
ザがオブジェクトが除去されたという記録を維持してお
かなければならない期間を限定し、該オブジェクトにつ
いての順番が狂ったメッセージを拒絶することができる
ようにする手段をさらに含む請求項１記載の通信システ
ム。
【請求項１１】ユーザの前記グループが動的に変化す
ることができ、前記サーバが、ユーザが要求した場合に
はそのユーザに世界モデルにおけるすべてのオブジェク
トの現在の状態をダウンロードする手段を含む請求項１
記載の通信システム。
【請求項１２】前記損失の多い直接の通信リンクが、
マルチキャストを利用している請求項１記載の通信シス
テム。
【請求項１３】前記サーバは、直接的なマルチキャス
ト通信が不可能な前記ユーザにマルチキャスト通信をシ
ミュレーションする手段を含む請求項１記載の通信シス
テム。
【請求項１４】前記オブジェクトがＧＵＩＤによって
識別され、ＧＵＩＤのオブジェクトへの割り当てが、与
えられたユーザによって修正されたすべてのオブジェク
トについてのＧＵＩＤが多くのビットを共通に有するよ
うにし、それによって、表されるべきオブジェクト状態
を記述するメッセージがより完成するようにする手段を
含む請求項９記載の通信システム。
【請求項１５】オブジェクト状態を記述する前記示差
メッセージを作り出す前記手段は、前記Ｎ個の前の状態
のそれぞれの間での送信においてオブジェクトのどの構
成要素が変化したかを表すビットマスクを含み、それに
よって、該ビットマスクを論理和演算と組み合わせるこ
とによって、オブジェクト状態を記述する前記示差メッ
セージにどのような情報を含む必要があるかを迅速およ
びコンパクトに判定することができる請求項９記載の通
信システム。