JPH0652899B2 - パケット通信網の相互接続方法 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、一般にいえば複数の独立した通信網〈networ
ks〉を相互接続することにより形成される通信システム
に関するものであり、更に特定していえばトポロシー的
〈topological〉制限を課することなく別個の通信網の
相互接続〈interconnction〉を実現するための方法論及
び構成に関する。

〔従来の技術〕

ローカル・エリア・ネットワーク(LAN) のサービス範囲
を、これらのLAN を相互接続することにより拡大して、
地理的にかなりの広がりをもつ都心部の通信網を創生す
ることがしばしば必要になる。また、例えば複合ビル群
の内部におけるような、別々のLAN を運用している大学
とか会社等の組織では、該複合ビル群の全体で使用でき
る大形LAN を実現するために、これらのLAN を相互接続
することが必要になって来よう。

もし、あるLAN に接続されている（例えばコンピュー
タ、ビデオ端末、電話機等のような）装置類〈device
s〉が、相互接続後に他のLAN の同様の装置類に唯一つ
の路〈path〉しか持たないならば、すなわちループを持
たないトポロジー〈loop-free topology〉を形成するな
らば、蓄積交換〈store-and-forward〉プロトコルを実
行するゲートウェイと呼ばれる関門に通信網の対を接続
することにより、相互接続が達成されよう。このような
相互接続の配置は、リンクされたシステム中の任意の装
置類にとってゲートウェイの存在がはっきり見えるもの
ではなく、その結果として該装置類若しくはそれらによ
り送り出されるメッセージやパケットには何らの変更も
必要としないから、透明な〈transparent〉相互接続と
云われる。

最近、透明な相互接続配置に対する方法論及び関連の回
路網を論じた多数の文献が出ている。それらは例えば： (1) B.Hawe及びB.Stewart による“Local Area Network
Applications”,1984 年９月，Telecommunications誌
所載． (2) Digital Equipment Corporation の技術論文“An A
rchitecture for Transparently Interconnecting IEEE
802 Local Area Networks”,1984年10月，IEEE 802 St
andards Committee に提出． (3) B.Hawe,A.Kirby及びB.Stewart による“Transparen
t Interconnection of Local Networks with Bridge
s”，1984年９月，Journal of Tele communications Ne
tworks 誌所載． 等である。これらの文献では、相互接続された通信網の
物理的〈physical〉トポロジーは技をもつ木〈branchin
g tree〉の形態でなければならぬことを強調している。
ゲートウェイは、LAN とLAN の間に選び得る２つの路が
保持され、従ってループが形成されるようなローカル・
エリア・ネットワークを透明に相互接続することが出来
ない。実際、上記文献(1) には一般的な網状〈mesh〉ト
ポロジーをループを持たないトポロジーに変換してゲー
トウェイが利用できるようにするための技法が示唆され
ている。

システムのトポロジー〈system topology〉がループを
持たないという要求条件は通常は厳しいものであり、結
局は在来型のゲートウェイ配置の実際の適用を限定す
る。チャネル容量の需要を満たし、必要な程度の信頼性
を確保するために、相互接続されたシステムはトポロジ
ーのいくつかの部分にいくつかのループを持つことにな
ろう。在来型のゲートウェイでは常にこれらのループを
検出して排除するので、余裕度と信頼性の改善は妨害さ
れる。物理的又はリンクの層〈physical of linklaye
r〉におけるループすなわち巡回トポロジー〈loop of c
yclic topologies〉の相互接続の問題点は、従来の技術
文献には言及されていなかった。

〔発明が解決しようとする課題及びその手段〕

蓄積交換ゲートウェイを持つローカル・エリア・ネット
ワークの透明な相互接続のためにはループを持たないト
ポロジーが要求されるというこの制約を除くことが、本
発明の目的であり、それはメッセージ・パケットによっ
て運ばれる経路指定情報〈routing information〉を利
用してなされる。

概言すれば、システム全体のトポロジーは無向連結グラ
フ〈undirected connected graph〉によって表され、そ
こでは通信網は節点〈vertices〉（又はノードともい
う）に写像され、ゲートウェイは辺〈edges＞ （又は
技ともいう）に写像される。要求される容量と必要な冗
長度〈redundancy〉とを与えるために、全域木〈spanni
ng trees〉の集合〈set〉が定義される。各全域木は一
意的に定められる。システム全体を通り抜ける各メッセ
ージ・パケットには１つの特定の全域木が割当てられ、
それによってパケットは該特定の全域木に含まれる辺に
沿って節点間を進んで行く。各ゲートウェイは拡張され
た蓄積変換プロトコルを用いてパケットを分析し、それ
により割当てられた全域木を判定して、それに従ってメ
ッセージを進める。本発明の一実施例では、パケットを
発出する装置類は全域木識別子〈identifier〉を特定し
て、これをパケット中に明白な形で又は陰伏的な形で
〈explicitlyorimplicitly〉運ばせる。

通信網に新たに接続された装置類によって不必要である
かも知れない多数の伝送がシステム中を行き来すること
を減らすために、新しい装置類の所在をゲートウェイが
学習するのを許容するような遅延を、プロトコルが含む
こともある。そのときこの拡張されたプロトコルは蓄積
遅延交換〈store-delay-forward〉アルゴリズムを実行
する。

〔実施例〕 本発明の構成及びその運用は以下の詳細な記述を精読し
又添付の図面を参照することにより更によく理解されよ
う。

説明がよく理解されるように、先ず最初に従来型のゲー
トウェイの配置を方法論に重点を置いて記述し、それに
より本発明の基本概念の依って立つ根拠を明らかにする
ことが好適であろう。この根拠が、基礎となる概念及び
用語を導入して、従来の技術とは異なることを理解させ
る実施例の提示を後に容易ならしめる。

１．基本概念 第１図には、それぞれNETWORK Ａ及びNETWORK Ｂと名付
けた２つの通信網 101及び201 があり、これが一対の単
方向ゲートウェイ 102及び202 により相互接続されて全
通信システム100 を形成する。ゲートウェイ 102と202
とは、ゲート102 によりNETWORK Ｂに送り出された信号
にはゲート202は関与しないように、また、ゲート 202
によりNETWORK Ａに送り出された信号にはゲート 102は
関与しないように、リンクしている。

各個別のネットワークは一般的には、ホストと称する多
数の装置類用に使われる。第１図では、ホスト 111と11
2 及びホスト 211と212 はそれぞれ、ネットワーク 101
及び201 に接続し、またそれを介して相互に通信する。
各ホストは固有のアドレスを持つものとし、また各ネッ
トワークは一斉同報通信機能〈broadcast capability〉
を持つものとする、すなわち若しあるホストがパケット
を送り出すと、共通ネットワーク上の他のすべてのゲー
トウェイはそのパケットを受け取る。

ネットワーク上を伝播する各パケットは、現実のメッセ
ージ・データと共に、送出ホスト・アドレスと宛て先ホ
スト・アドレスとを含んでいる。２つのネットワークを
相互接続しているゲートウェイの１つは、所定のネット
ワーク上に送り出された各パケットを受け取るようなっ
ている。例えば第１図では、ゲートウェイ 102はネット
ワーク 101上に送り出されたすべてのパケットを受け取
る。

各ゲートウェイの実行する蓄積変換プロトコルは次のよ
うになっている：すなわち、１つのゲートウェイはそれ
に関連するネットワーク上を伝播して来た各パケットを
先へ進める、但し以前に他のパケットの送出アドレス中
に現れたホスト宛てのパケットはこれを除く、と云うも
のである。従って、あるホストが最初にパケットを送り
出す度毎に、該パケットが通過する各ゲートウェイは、
そのホストの所在位置を「学習」する。次のホストが後
に最初のホストにパケットを送るときには、該パケット
は自動的にシステムを通じて最適の経路を経て前進す
る。

このプロトコルをもう少し詳細に説明するために、第２
図のシステム 300について考察する。この配置には複数
対のゲートウェイにより結合する多数のネットワークが
含まれ、各ゲートウェイは上述のアルゴリズムを実行す
る。

プロトコルを精確に定義するために、次の信号が用いら
れる： Ｎ_i ：ネットワーク番号（引用番号 30iを付す）、但し
ｉ＝1,…,7 である。

Ｇ_ij：ネットワークｉからネットワークｊへのゲートウ
ェイ（引用番号 3ijを付す） A,B,C,D,E ：ホスト・コンピュータ（それぞれ引用番号
381,382,…,385を付す） Ｐ_xy：ホストＸからホストＹへ送られたパケット。

→ ：“〜→…”は「〜は…上へ再送出される」の意
味。

Ｄ_ij：ホストの組。これはＧ_ij内に記憶され、それに対
する送り出しはＧ_ijを通してブロックされる。（Ｄ_ijは
「ドロップ・フィルター」と呼ばれる） 第２図の配置は初期化されていると仮定する、すなわち
すべてのi,jに対しＤ_ij＝φ（空集合）と仮定する。茲
でホストＥからホストＣへの送出があるとする場合に
は： １．Ｐ_ECはＮ₇ を通る。

２．Ｄ₇₃＝｛Ｅ｝且つＧ₇₃によりＰ_EC→Ｎ₃ ３．Ｄ₃₆＝｛Ｅ｝且つＧ₃₆によりＰ_EC→Ｎ₆ Ｄ₃₁＝｛Ｅ｝且つＧ₃₁によりＰ_EC→Ｎ₁ ４．Ｄ₁₂＝｛Ｅ｝且つＧ₁₂によりＰ_EC→Ｎ₂ ５．Ｄ₂₄＝｛Ｅ｝且つＧ₂₄によりＰ_EC→Ｎ₄ Ｄ₂₅＝｛Ｅ｝且つＧ₂₅によりＰ_EC→Ｎ₅ となる。

Ｐ_ECは上述のステップ３で既に宛て先に到着しているの
であるが、更に進行を続けてネットワーク内に氾濫す
る。その模様を第３図に破線で示す。

次に、戻りのパケットＰ_CEについて第４図により考えよ
う： １．Ｐ_CEはＮ₆ を通る。

２．Ｄ₆₃＝｛Ｅ｝且つＧ₆₃によりＰ_CE→Ｎ₃ ３．Ｄ₃₁＝｛C,E｝且つＧ₃₁によりＰ_CEはドロップされ
る。

Ｄ₃₇＝｛Ｃ｝且つＧ₃₇によりＰ_CE→Ｎ₇(及びホストＥ) ホストＥの所在位置はＰ_ECの送出により「既知」であっ
たから、戻りのパケットはネットワークの中で最適の経
路をとる。

最後に考えることとして、次のパケットＰ_ECは第５図に
描かれたようにネットワーク内を通って送り出されるの
で： １．Ｐ_ECはＮ₇ を通る。

２．Ｄ₇₃＝｛Ｅ｝且つＧ₇₃によりＰ_EC→Ｎ₃ ３．Ｄ₃₁＝｛C,E｝且つＧ₃₁によりＰ_ECはドロップされ
る。

Ｄ₃₆＝｛Ｅ｝且つＧ₃₆によりＰ_EC→Ｎ₆(及びホストＣ) となるものと想定される。

実際、任意のｋ≠Ｅに対してＰ_KEは必要なネットワーク
しか通らないであろう。Ｐ_CEはＧ₆₃，Ｇ₃₁及びＧ₃₇だけ
が受け取ったに過ぎないから、全ネットワークの一部の
みがホストＣの所在位置を「知っている」に過ぎない。
しかし、ネットワークの残りの部分はホストＣについ
て、もしそれが他のホストに送り出すならばその時に、
学習するであろう。一旦、確固たる状態〈steady-stat
e〉が達成されたら、各Ｇ_ijはいわゆる「ブロック〈blo
ck〉」リスト又は「ドロップ〈drop〉」リストと呼ばれ
るＤ_ijを持つことになり、これが最適経路選定を司り、
無関係な送出を抑制する。

２．プロトコルの構成の拡張 上述のことから、システム 300は任意の１対のホスト間
に唯１つの経路のみしか持ってはならない、それはパケ
ットが２つのゲートウェイ間に「ループを作ること〈lo
oping〉」を永久に防止するためである、と結論でき
る。更に詳しく云えば、もしネットワークを節点〈vert
ices〉に写像し、ゲートウェイの対を辺〈edges〉に写
像することにより、システムが無向グラフ上に写像され
るならば、その結果のグラフは正確に機能するためルー
プを持たないもの〈loop-free〉でなければならない、
換言すれば、システム 300のトポロジーは非巡回〈acyc
lic〉グラフのそれに限定される。第６図はシステム 30
0のトポロジーをグラフ形式に描いたものである。第２
図のゲートウェイの対を一纏めにして付した番号が第６
図ではグラフの辺（実線）を定義するのに使われてい
る。このグラフは、節点の各対が唯１つの経路のみによ
って結合しているから、非巡回的である。例えばもし、
節点 306及び307 が直接結ばれている（第６図に破線 3
75で示すように）ならば、グラフは巡回的〈cyclic〉に
なるであろう。

巡回的なシステムは、前に論じた蓄積変換プロトコル又
はアルゴリズムに直接利用することができない。例え
ば、節点 306及び307 が直接結ばれている第６図では、
節点 303上のホストから節点 306上のホストへ送られる
パケットは経路303-307-306-303-307 …という永久ルー
プを、或いは経路303-306-307-303-306 …という永久ル
ープを作るであろう。ループを作るパケットはゲートウ
ェイ及びネットワークを飽和させて正常な通信を阻害す
る。

第６図の実線で示した構造は、全域木〈spanningtree〉
と呼ばれ、全域木内では節点の各１対は唯１つの経路の
みによって結ばれる。第７図のグラフは第６図の節点配
置のもう１つの全域木を示す。一般的に任意のグラフは
複数の全域木を持つであろう。

本発明の１つの態様によりゲートウェイ・プロトコルの
構造に改善を施すために、予め定められた指針に従って
巡回的なグラフに対し全域木の１つの集合が選定され
る。各全域木には固有の識別子すなわち番号が割り当て
られて、システムを通る各メッセージには、その識別子
を介して固有の全域木が割り当てられる。このメッセー
ジを受け取るすべてのゲートウェイは該全域木の番号を
確かめて、それからその特定の全域木上にメッセージを
経路指定し、他の全域木の全パケットをドロップする。
典型的には、メッセージを発出する装置が全域木の番号
を、明白な形で又は陰伏的な形で特定する。例えば明白
な形でいう場合には、パケットのヘッダー中に１ビット
余分に設ける等、パケットの仕様に「木番号」フィール
ドを追加することもできよう。陰伏的にいう場合には、
全域木の番号は、パケット中に正常に生じるフィール
ド、例えば発出源アドレス及び宛て先アドレスから生成
させることもできよう。関数の１つの適切な実例として
は、ネットワーク中の全域木の数をＮとするとき、 全域木の番号＝(Nを法として〈modulo N〉の)発出源と
宛て先との排他的論理和 としてもよかろう。これは、１対のホスト間の全トラフ
ィックが唯１つの全域木上のみを通り、従って全システ
ムに亙り占有されるドロップ・リストを最小にするとい
う点で優れている。

第８図の中央のグラフは、節点 303， 306， 307及び辺
364， 374， 375を含む第６図のグラフの一部分の実線
及び破線を再現したものである。第８図のこのグラフは
巡回的である。この新しい配列に到達するには、第２図
のシステム 300を変形して、例えば節点 306と節点 307
とを相互接続するゲートウェイの対（辺 375）を持たせ
たと考えてもよい。辺 375は、節点 306から節点 307へ
のメッセージ・トラフィックが増加して、辺 364及び37
4 が過負荷になることなしには最早それを取り扱えなく
なったのに対処できよう。

第８図のグラフは巡回的だから、１組の全域木が選定さ
れる。このグラフをカバーする２つの全域木が第８図の
左側と右側とにそれぞれグラフ401及びグラフ 402とし
て示されている。Ｓを発出源の節点、Ｄを１組の宛て先
の節点、Ｔを全域木の番号とするとき、記号Ｍ(S;D;T)
を用いて書けば、節点 303， 306， 307に対するメッセ
ージ経路割当てアルゴリズムの１つの可能性はそれぞれ
次の通りになる： Ｍ(303； 306,307,301,…； 2)， Ｍ(306； 303,307,301,…； 1)， Ｍ(307； 303,306,301,…； 2)， この特定の割当ては、恐らく負荷の均衡を目的として、
節点 306から発出するメッセージに対してのみ辺 375を
利用する。もし辺 375が機能しなくなれば、節点 306に
関連する諸装置は Ｍ(306； 303,307,301,…； 1)， への割当て変更を通知されることがあり、それによりシ
ステム内の通信を維持する。巡回的ネットワーク内に複
数の全域木があると、対応するゲートウェイの停止期間
中は行動に若干の損失があるかも知れないが、ある一定
の節点間に冗長度〈redundancy〉を持たせることにな
る。

一般的には、異なる全域木中に出現するゲートウェイ
は、各全域木のそれぞれに対してドロップ・リストを保
持しなければならない。例えば第８図で、ｋ番目の全域
木に対するドロップ・リストをD(k)_ijと書くことにすれ
ば、両方の木の上をホストＣからホストＥへ送られるパ
ケット(P_CE)は、始動に際し、辺 374に対して： D(1)₃₇＝φ， D(2)₃₇＝｛Ｃ｝， D(1)₇₃＝｛Ｃ｝，D(2)₇₃＝φ となっている。一組の中の殆どの全域木を選択して、ど
の辺も２つ以上の全域木には含まれないようにすること
により、多重ドロップ・リストを保持する必要性は緩和
される。

システムが非巡回的な場合においてさえも、実際上は多
重に全域木を利用して十分な通信容量を設けることがし
ばしば必要である。本発明のもう１つの態様はそのよう
な状況を包含している。この場合の実例としては、広い
地理的領域をカバーする公衆電話網又は私設電話網の階
層〈hierarchy〉のような、木の形をした〈tree-shape
d〉システムがある。これらのシステムでは、根〈roo
t〉において又は根の近傍において隘路の生じる傾向が
ある。どの辺も２つ以上の全域木には含まれないよう
な、互いに素の〈disjoint〉全域木を使う代わりに、本
質的には同一の全域木をグラフ上で重ね合わせること
を、容量の考案が要求する。このことが第９図のグラフ
に表示され、これは、３レベルの階層に対して２つの全
域木を（一方は実線で、他方は破線で）示すように、第
６図のグラフを書き直したものである。

この場合には、唯１つのゲートウェイの対のみが２つの
全域木の各々の中で辺 343を形作る。ところが辺 322は
各全域木に対し１つ宛、２つのゲートウェイの対により
形作られる。同様に、辺 353， 364， 347は双方の木に
対し唯１つのゲートウェイ対のみがあるのに対して、辺
332は２つのゲートウェイ対を含む。この戦略的な配置
の故に、辺 343に対するドロップ・リストは（辺 353,3
64,374 に対するドロップ・リストも同じく）、各全域
木に対し同一であり、従って保持しなければならないリ
ストは唯１つだけである。同じように辺 322のドロップ
・リストは（及び辺 332のドロップ・リストも）同一
であるが、この場合には２つの別々のゲートウェイ対が
用いられているからその重要性は小さい。

第９図のネートワークは、輻輳低減のためレベル１と２
の間（辺 322及び332）でゲートウェイを二重化してい
る。しかし輻輳は節点でもやはり生じるだろう。第10図
は、節点 301を二重化して（節点 308を設けて）節点 3
01を通過するトラフィックを低減するようにした第９図
の一部分を示している。このネートワークは、節点301
又は308にホストが接続されない限り正常に動作するだ
ろう。もし節点 301及び308 にホストが接続されたなら
ば、辺 384及び394 にゲートウェイ対を追加して完全な
接続性を具備させなければならない。

システム全体を通して並列に辺及び節点を追加するとい
う戦略には、２重化されるレベルの数や追加される並列
な辺及び節点の数に関して何の限定もない。この性質の
故に、任意の大きさの通過トラフィックを持つネットワ
ークが構築できる。これらのネットワークは、二重化さ
れない辺が使用される全域木の数に無関係に単一のドロ
ップ・フィルターのみを有していればよいという好まし
い性質を持っている。

第11図は、各パケットが全域木（スパン・ツリー）を使
ってシステム中を伝播するステップを説明するフローチ
ャートである。ステップ401 では、先ず該システム用の
全域木（スパン・ツリー）が容量及び信頼性の考慮を満
足させるよう予め選択され、それから各全域木に固有の
識別子が割り当てられることが示される。ステップ411
で示すように、ある装置により発出され、関連のソース
・ネットワーク上を伝播する各パケットは、該パケット
内に予め選定された全域木識別子が付与される。伝播さ
れたパケットを受け取る各ゲートウェイは、ステップ42
1 で示すように、該パケットを発出したソース装置とそ
れを受け取る宛て先装置並びにパケット中に埋め込まれ
た識別子を読み取る。ステップ422 では、パケットの発
出元アドレスをその特定の全域木用のドロップ・リスト
中に、もしそれが未だ入っていなければ、挿入する。次
に、判断ステップ423 では、もしこのゲートウェイがパ
ケット中に見出した該特定の全域木を処理しないなら
ば、そのパケットは落とされる。更に、判断ステップ42
5 で示すように、パケットの宛先が該全域木用のドロッ
プ・リスト中に見出されるならばやはりそのパケットは
落とされるが、見出されないならば、ステップ426 に示
すように、ゲートウェイによりパケットは一斉通報〈br
oadcast〉される。ステップ431 では、パケットが宛先
装置において検出され、一般には確認パケットがソース
装置に返送される。戻りのパケットは必ずしも最初のパ
ケットと同じ全域木を通る必要はないが、効率上にはそ
れが適当である限り同じ木を通るべきである。

大きいシステムにおいて特に然りであるが、いかなるシ
ステムでも、新しいホストがサービスに加わったとき、
該システムが新しいホストの所在位置を学習するまで
は、任意のLAN から該新しいホストへのメッセージがシ
ステムに氾濫するかも知れない。本発明の更にもう１つ
の態様であるこの点を説明するために、第２図の右側の
部分すなわちネットワーク303，306，307(N₃,N₆,N₇)、
ゲートウェイ337，373(G₃₇,G₇₃)、及びホスト384(D)，
ホスト385(E)を考える。ホスト384 が新たにサービスに
加わったものとし、ネットワーク307 を通るパケットＰ
_EDがあうものとする。ゲートウェイＧ₇₃はホスト384 を
未だ学習していないから、換言すればドロップ・フィル
ターはそのリスト中にホストＤを持っていないから、普
通はこのパケットがシステムに氾濫する。しかしもしゲ
ートウェイＧ₇₃がパケットＰ_EDの再送り出しを若干時間
(T_D )だけ遅延させ、その遅延がホスト384 の平均確認
応答時間よりも大きいならば、ゲートウェイＧ₇₃はホス
ト384 をそのドロップ・リスト Ｄ₇₃＝｛E,D,…｝ に追加するであろう。ゲートウェイＧ₇₃によるパケット
Ｐ_EDの再考案により、ネットワーク303 への再送出及び
システム中へのこのパケットの伝播は避けられる。もし
ホスト384 が一般化されて、電話機やデータ端末のよう
な何らかの通信装置を意味し、またネットワーク306，3
07…が市内電話網であるならば、このことは特に重要な
考案である。

この交換前遅延〈delay-before-forwarding〉プロトコ
ルは全域木プロトコルと組み合わせて、本発明の更にも
う１つの態様をもたらすこともできる。第11図で、ステ
ップ425 とステップ426 との間に、蓄積及び遅延〈stor
e-and-delay〉ステップとこれに続くもう１つの判断ス
テップとが挿入される。この新しく挿入された第１のス
テップで予め定められた遅延を経た後、ステップ425 が
したのと同じ条件で、新しい判断ステップが試験を行
う。そのときもし宛先アドレスがドロップ・リスト中に
あるならば、パケットは落とされるし、そうでなければ
パケットはステップ426 で処理される。

本発明の更に別の態様では、ネットワークの氾濫を緩和
し、遅延を減少させるために、ゲートウェイの対はそれ
ぞれのドロップ・リストを相互に通知し合うように配置
することもできる。そうすると、もしホストＤがゲート
ウェイＧ₃₇用のドロップ・リスト中に含まれホストＤは
ネットワーク307 上にはない（Ｄ₃₇｛…,D,…｝）こと
を示すならば、Ｐ_EDは直ちに再送出されるに違いない。
パケットＰ_ED用のゲートウェイ対Ｇ₇₃及びＧ₃₇に対する
通信と遅延との双方を組み合わせた完全なアルゴリズム
は： １．もしＤがＤ₇₃に含まれるなら、パケットＰ_EDは再送
出されない； ２．もしＤがＤ₃₇に含まれるなら、 パケットＰ_ED→Ｎ₃ ； ３．もしＤはＤ₃₇に含まれず、またＤはＤ₇₃にも含まれ
ないならば、パケットＰ_EDは遅延する、すなわちＧ₇₃に
時間T_D の間だけ記憶され、それから再び処理過程に戻
る． となる。

時間遅延を具えるゲートウェイの対に対しては、第11図
のステップ425 の機能を拡張して、逆伝播方向の全域木
用のドロップ・リスト中に宛先装置があるか否かを判定
する試験を、正方向の試験が成功しなかった度毎に実行
することができる。もしこの追加試験が成功であったな
らば、パケットは関連の全域木上を伝播する。もしその
試験が不成功であったならば、パケットは予め選定され
た時間だけ記憶され、それから再びステップ425 に戻っ
て最終的に処理される。

茲に延べた方法論及び関連の配置は、本発明がそれに限
定されることを意味するものではなく、請求の範囲の記
載にのみ限定されるその他の実施例をも包含するもので
ある。

図面の簡単な説明 第１図は、２つのローカル・エリア・ネットワークを相
互接続するための１対のゲートウェイの配置を示す概略
ブロック図であり、 第２図は、多数のローカル・エリア・ネットワークを多
くのゲートウェイ対で相互接続した、ループを持たない
３レベルの典型的な階層システムを示す図であり、 第３図は、所与のローカル・エリア・ネットワークから
の最初のパケットが、ネットワーク初期化後の第２図の
システムを通して伝播するやり方を説明し、ネットワー
クが最初のパケットの所在位置を学習する能力を示す図
であり、 第４図は、第２図のシステムを通しての戻りのパケット
の伝播を示し、ネットワークが応答パケットの所在位置
を「学習」したことを説明する図であり、 第５図は、第２図の所与のローカル・エリア・ネットワ
ークからの２番目のパケットの伝播を示し、また、ゲー
トウェイがパケット源の確認を既に「学習」したこと、
及び、以後は所与の装置から将来のすべてのパケットが
最適の経路選定をすることを論証する図であり、 第６図は、第２図のシステムのグラフによる表現であっ
て、該システムに対する全域木を説明する図であり、 第７図も、第２図のシステムのグラフによる表現であっ
て、該システムに対する第６図とは別の全域木を説明す
る図であり、 第８図は、第２図のシステムの一部に対し、巡回的なグ
ラフの拡張を示し、またその拡張をカバーする２つの非
巡回的なグラフを示す図であり、 第９図は、第２図のシステムを表すグラフであって、シ
ステムの処理能力を高めるために２つの全域木を重ね合
わせたものを示す図であり、 第10図は、第９図の一部分のグラフで、単一の節点にお
けるトラフィックの輻輳を軽減するために節点を二重化
したものを示す図であり、 第11図は、一般的な巡回的システムを通してパケットを
伝播させるためのステップを説明するフローチャートを
示す図である。

101,102 ……通信網（ローカル・エリア・ネットワーク
- LAN） 102,202 ……ゲートウェイ 111,112,211,212 ……ホスト(LANに接続される端末装置
類) Ｎ_i(i＝1,…,7)……ネットワーク（引用番号30_iを付
す） Ｇ_ij……ネットワークｉからネットワークｊへのゲート
ウェイ（引用番号3ij を付す） A,B,C,D,E ……ホスト（コンピュータ）

Claims (6)

【特許請求の範囲】
1. 【請求項１】ゲートウェイにより相互接続されている多
   数のネットワークを含むシステム上に、その各々が送出
   元アドレスと宛先アドレスとを持っているパケットを送
   出する方法において、 該方法は次の諸ステップ、すなわち − 上記ネットワークの１つを宛先とし、また以前にそ
   こを通った上記パケットのうちのどれかに出現した送出
   元アドレスを持ち、且つ該送出元の出現は上記各ゲート
   ウェイ内のドロップ・リストに記憶されているところの
   パケットを除いた、上記各ゲートウェイの受信する任意
   の上記パケットを前進させる経路設定アルゴリズムを実
   行するように、上記各ゲートウェイを配置するステッ
   プ、 − 上記システムに対する全域木の集合を選定するステ
   ップ、 − 上記全域木の１つを指定する識別子を上記パケット
   の各々により運ぶステップ、 そして上記各パケットに対して、 − 上記各ゲートウェイ内で上記各パケットから上記送
   出元アドレスと上記宛先アドレスとを抽出するステッ
   プ、 − もし上記送出元アドレスが上記各ゲートウェイの上
   記ドロップ・リスト中に無いならば、該送出元アドレス
   を上記ドロップ・リストに付け加えるステップ、 − もし上記宛先アドレスが上記ドロップ・リスト中に
   無いならば、上記各パケットを予め定められた期間だけ
   記憶して、その期間中に上記各ゲートウェイにより上記
   パケットの後続のものが処理されるステップ、及び − 上記期間後に上記宛先アドレスが上記ドロップ・リ
   スト中に無いならば必ず、上記識別子に対応する上記全
   域木の１つの上を上記システムを通って上記各パケット
   の経路が上記ゲートウェイにより設定され、またそうで
   ないならば、上記各パケットを上記各ゲートウェイ内に
   はそれ以上記憶しないステップ を持つことを特徴とするパケット送出方法。
2. 【請求項２】特許請求の範囲第１項に記載のパケット送
   出方法において、該方法は更に、 − 確認パケットを、上記全域木の上記１つを通して返
   送するステップ を有することを特徴とするパケット送出方法。
3. 【請求項３】その各々が発出元アドレスと宛先アドレス
   とを持っているパケットを、ゲートウェイにより伝播さ
   せる方法において、 該方法は次の諸ステップ、すなわち − 上記パケットのうち以前にそこを通ったどれか１つ
   に発出元アドレスとして出現した宛先アドレスを持ち、
   該発出元の出現がドロップ・リストに記憶されていると
   ころのすべての上記パケットを除いた、上記ゲートウェ
   イの受信する任意の上記パケットを前進させる経路設定
   アルゴリズムを実行するように、上記ゲートウェイを配
   置するステップ、 そして各パケットに対して、 − 上記ゲートウェイ内で上記パケットから上記発出元
   アドレスと上記宛先アドレスとを抽出するステップ、 − もし上記発出元アドレスが上記ドロッブ・リスト中
   に無いならば、該発出元アドレスを上記ドロップ・リス
   トに付け加えるステップ、 − もし上記宛先アドレスが上記ドロップ・リスト中に
   無いならば、上記パケットを予め定められた期間だけ記
   憶して、その期間中に上記パケットの後続のものが上記
   ゲートウェイにより処理されるステップ、及び − 上記期間後に上記宛先アドレスが上記ドロップ・リ
   スト中に無いならば上記パケットが経路設定され、また
   そうでないならば、上記パケットを上記ゲートウェイ内
   にはそれ以上記憶しないステップ を持つことを特徴とするパケット伝播方法。
4. 【請求項４】１対のゲートウェイのうちの１番目のゲー
   トウェイによってパケットを処理する方法であって、該
   １番目のゲートウェイは２番目のゲートウェイにより読
   み取り可能な１番目のドロップ・リストを持ち、該２番
   目のゲートウェイは上記１番目のゲートウェイにより読
   み取り可能な２番目のドロップ・リストを持ち、上記パ
   ケットは発出元アドレスと宛先アドレスとを有し、各上
   記ドロップ・リストは対応のゲートウェイにより処理さ
   れたところの以前のパケットの発出元アドレスを有する
   パケット処理方法において、 該方法は次の諸ステップ、すなわち − 上記１番目のゲートウェイ内で上記パケットから上
   記発出元アドレスと上記宛先アドレスとを抽出するステ
   ップ、 − もし上記発出元アドレスが上記１番目のドロップ・
   リスト中に無いならば、該発出元アドレスを上記１番目
   のドロップ・リスト中に挿入するステップ、 − 上記２番目のドロップ・リストを読み取り、もし上
   記宛先アドレスが上記２番目のドロップ・リスト中にあ
   るならば、上記パケットを上記１番目のゲートウェイに
   よって前進させるステップ、 − もし上記発出元アドレスが最初には上記１番目のド
   ロップ・リスト中に無く、また上記宛先アドレスが上記
   ２番目のドロップ・リスト中に無いならば、上記パケッ
   トを予め定められた期間だけ上記１番目のゲートウェイ
   が記憶して、その期間中に後続のパケットが上記ゲート
   ウェイ対により処理されるステップ、及び − 上記期間後にもし上記宛先アドレスが上記１番目の
   ドロップ・リスト中に無いならば、上記パケットを前進
   させ、またそうでないならば、上記パケットを上記１番
   目のゲートウェイ内にはそれ以上記憶しないステップ を持つことを特徴とするパケット処理方法。
5. 【請求項５】ゲートウェイにより相互接続されている多
   数のネットワークを含むシステム上にパケットを送出す
   る方法であって、上記ネットワークの１つに接続された
   ソース装置から発出し、上記ネットワークの１つに接続
   された宛先装置に到達する上記パケットは発出元アドレ
   スと宛先アドレスとを含むパケット送出方法において、 該方法は次の諸ステップ、すなわち − システムを表す無向グラフを定義し、該グラフでは
   上記ネットワークはグラフの節点に写像し、上記ゲート
   ウェイはグラフの辺に写像するステップ、 − 上記節点の対は、すべて各々唯１つの上記辺によっ
   てのみ接続されるように、上記グラフ上に全域木を定義
   し、予め定められたシステム指針に従って上記グラフに
   対し複数の全域木を選定するステップ、 − 上記辺の１つを含む各ゲートウェイを持つ全域木の
   番号に対応して、発出元アドレス・リストを具える上記
   各ゲートウェイを配置するステップ、 − 上記パケットを一斉同報通信するために上記ソース
   装置により上記全域木の１つを割り当てて、上記全域木
   の上記１つを指定する識別子を上記パケットに結び付け
   るステップ、 − 上記ソース装置により上記パケットを、上記全域木
   の上記１つの上をシステムを通じて一斉同報通信するス
   テップ、 − 上記パケットを受信した各ゲートウェイに対して、 (1) 各上記パケットに対し、上記発出元アドレスと上
   記宛先アドレスと上記パケット識別子とを決定し、 (2) もし上記受信したゲートウェイが上記識別子を持
   つパケットを処理しないならば、上記パケットを前進さ
   せることを禁止し、またそうでないならば、上記識別子
   に結び付いている上記リストのうちの対応するものの中
   に上記発出元アドレスを挿入し、 (3) もし上記宛先アドレスが上記リストのうちの上記
   対応するものの中にあるならば、上記のパケットを前進
   させることを禁止し、またそうでないならば、予め定め
   られた期間だけ上記パケットを記憶し、それから該パケ
   ットを次項(4) により処理するようにさせ、 (4) もし上記宛先アドレスが上記対応するリストの中
   にあるならば、上記パケットを前進させることを禁止
   し、またそうでないならば、上記受信したゲートウェイ
   により上記パケットを前進させるステップ、及び − 上記宛先装置が上記全域木の上記１つの上に戻りの
   パケットを一斉同報通信することにより、上記パケット
   の受信を確認するステップ を持つことを特徴とするパケット送出方法。
6. 【請求項６】ゲートウェイにより相互接続されている多
   数のネットワークを含むシステム上にパケットを送出す
   る方法であって、上記ネットワークの１つに接続された
   ソース装置から発出し、上記ネットワークの１つに接続
   された宛先装置に到達する上記パケットは、発出元アド
   レスと宛先アドレスとを含むパケット送出方法におい
   て、 該方法は次の諸ステップ、すなわち − システムを表す無向グラフを定義し、該グラフでは
   上記ネットワークはグラフの節点を含み、上記ゲートウ
   ェイはグラフの辺を含むステップ、 − 上記節点の対はすべて各々唯１つの上記辺によって
   のみ接続されるように上記グラフ上に全域木を定義し、
   予め定められたシステム指針に従って上記グラフに対し
   複数の全域木を選定するステップ、 − 上記辺の１つを含む各ゲートウェイを持つ全域木の
   番号に対応して、発出元アドレス・リストを具える上記
   各ゲートウェイを配置し、全域木の上記選定の結果が上
   記各ゲートウェイに対し上記リストの全く同一のものを
   もたらす時には常に、上記リストを共通のリストに纏め
   るステップ、 − 上記パケットを一斉同報通信するために上記ソース
   装置により上記全域木の１つを割り当てて、上記全域木
   の上記１つを指定する識別子を上記パケットに結び付け
   るステップ、及び − 上記パケットを受信した各ゲートウェイに対して、 (1) 各上記パケットに対し、上記発出元アドレスと上
   記宛先アドレスと上記パケット識別子とを決定し、 (2) もし上記受信したゲートウェイが上記識別子を持
   つパケットを処理しないならば、上記パケットを前進さ
   せることを禁止し、またそうでないならば、上記識別子
   に結び付いている上記リストのうちの対応するものの中
   に上記発出元アドレスを挿入し、 (3) もし上記宛先アドレスが上記対応するリストの中
   にあるならば、上記パケットを前進させることを禁止
   し、またそうでないならば、上記受信したゲートウェイ
   により上記パケットを前進させるステップ、 を持つことを特徴とするパケット送出方法。