JPH04219036A - ネットワークにおけるメッセージ送信設備及びその経路選択制御方法 - Google Patents
ネットワークにおけるメッセージ送信設備及びその経路選択制御方法Info
- Publication number
- JPH04219036A JPH04219036A JP3061087A JP6108791A JPH04219036A JP H04219036 A JPH04219036 A JP H04219036A JP 3061087 A JP3061087 A JP 3061087A JP 6108791 A JP6108791 A JP 6108791A JP H04219036 A JPH04219036 A JP H04219036A
- Authority
- JP
- Japan
- Prior art keywords
- node
- message
- nodes
- links
- messages
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims description 14
- 230000005540 biological transmission Effects 0.000 title claims description 5
- 238000004891 communication Methods 0.000 description 9
- 238000010586 diagram Methods 0.000 description 5
- 235000008694 Humulus lupulus Nutrition 0.000 description 1
- 238000007689 inspection Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/02—Details
- H04L12/16—Arrangements for providing special services to substations
- H04L12/18—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast
- H04L12/1854—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast with non-centralised forwarding system, e.g. chaincast
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L12/00—Data switching networks
- H04L12/02—Details
- H04L12/16—Arrangements for providing special services to substations
- H04L12/18—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast
- H04L12/1886—Arrangements for providing special services to substations for broadcast or conference, e.g. multicast with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】本発明は、データ通信ネットワー
クに関し、特に、データ通信ネットワークにおけるメッ
セージの経路選択技術に関する。
クに関し、特に、データ通信ネットワークにおけるメッ
セージの経路選択技術に関する。
【０００２】
【従来の技術】任意のトポロジに構成した通信ノード（
ノード）のネットワークにおける無接続サービスの提供
に際して、例えば、従来の同報通信は、ソースノードが
同報通信メッセージのコピーをネットワーク内の他のノ
ードの各々へ送信するようにソースノードを構成するこ
とによって行われている。
ノード）のネットワークにおける無接続サービスの提供
に際して、例えば、従来の同報通信は、ソースノードが
同報通信メッセージのコピーをネットワーク内の他のノ
ードの各々へ送信するようにソースノードを構成するこ
とによって行われている。
【０００３】
【発明が解決しようとする課題】上記のようなサービス
の提供に際しての一般的な問題は、同報通信メッセージ
をソースノードから他のノードのそれぞれに対して効率
よく経路選択できないことである。すなわち、上記の同
報通信の例において、同報通信メッセージを１コピーだ
け各ノードに送信するという目的は達成されるが、同報
通信メッセージの多数のコピーを目的の宛先に届けるの
に同一経路を用いるので、ネットワークの帯域幅が有効
に利用されていないという問題点があった。
の提供に際しての一般的な問題は、同報通信メッセージ
をソースノードから他のノードのそれぞれに対して効率
よく経路選択できないことである。すなわち、上記の同
報通信の例において、同報通信メッセージを１コピーだ
け各ノードに送信するという目的は達成されるが、同報
通信メッセージの多数のコピーを目的の宛先に届けるの
に同一経路を用いるので、ネットワークの帯域幅が有効
に利用されていないという問題点があった。
【０００４】
【課題を解決するための手段】本発明は、任意トポロジ
のノードネットワークにおける無接続同報通信メッセー
ジの経路選択についての従来技術を改良し、ネットワー
クの各ノードが、所定の条件が満たされた場合にのみ、
隣接ノードにメッセージを送信するように、ネットワー
クの各ノードを構成することによって従来の問題点を解
決するものである。
のノードネットワークにおける無接続同報通信メッセー
ジの経路選択についての従来技術を改良し、ネットワー
クの各ノードが、所定の条件が満たされた場合にのみ、
隣接ノードにメッセージを送信するように、ネットワー
クの各ノードを構成することによって従来の問題点を解
決するものである。
【０００５】すなわち、ノードＸは、ノードＸとメッセ
ージ源のノードとの間の距離が、隣接ノードＹとメッセ
ージ源のノードとの間の距離よりも近いときのみ、メッ
セージをノードＹに送る。ノードＹの他の隣接ノードに
ついても同様である。ノードＹの他の少なくとも１つの
隣接ノードＺについてもこの条件が満たされる場合は、
所定の因子に基づき、ノードＸ又はＺの一方のみがメッ
セージをノードＹに送信する。例えば、ノードＸ及びＺ
の内、ネットワークにおける最小アドレス番号を有する
ノードがメッセージをノードＹに送信する。
ージ源のノードとの間の距離が、隣接ノードＹとメッセ
ージ源のノードとの間の距離よりも近いときのみ、メッ
セージをノードＹに送る。ノードＹの他の隣接ノードに
ついても同様である。ノードＹの他の少なくとも１つの
隣接ノードＺについてもこの条件が満たされる場合は、
所定の因子に基づき、ノードＸ又はＺの一方のみがメッ
セージをノードＹに送信する。例えば、ノードＸ及びＺ
の内、ネットワークにおける最小アドレス番号を有する
ノードがメッセージをノードＹに送信する。
【０００６】
【実施例】図１は、それぞれの通信リンク（パス）１０
１から１０７までを経て相互接続された１、２、及び５
から８までの複数のノードからなるデータネットワーク
をブロック図の形で示す。以下に示すように、これらノ
ードの各々はいわゆるローカルネットワーク（ＬＡＮ）
である。ＬＡＮ内では、そのＬＡＮ例えばノード１によ
って表されるＬＡＮに含まれるデータモジュールがデー
タメッセージを相互に交換する。これに加えて、データ
モジュールは、他のノード、例えばノード８に含まれる
モジュールともメッセージ交換を行う。
１から１０７までを経て相互接続された１、２、及び５
から８までの複数のノードからなるデータネットワーク
をブロック図の形で示す。以下に示すように、これらノ
ードの各々はいわゆるローカルネットワーク（ＬＡＮ）
である。ＬＡＮ内では、そのＬＡＮ例えばノード１によ
って表されるＬＡＮに含まれるデータモジュールがデー
タメッセージを相互に交換する。これに加えて、データ
モジュールは、他のノード、例えばノード８に含まれる
モジュールともメッセージ交換を行う。
【０００７】データネットワークの運用中に、データモ
ジュールが、関連するモジュールと、他のノードの各々
に含まれるモジュールとにメッセージを同報通信する場
合がしばしばある。上記のように、全てのノードがメッ
セージを確実に受信できるようにするため、あるノード
が受信した同報通信メッセージ、すなわち無接続メッセ
ージの各々をネットワーク内の他のノードに経路選択し
て送信するようにノードを構成することができる。この
場合、ノードは同一の同報通信メッセージを何回も受信
することになる。その結果、同報通信メッセージがネッ
トワークにあふれ、そのため他のメッセージの送信が遅
れることになる。
ジュールが、関連するモジュールと、他のノードの各々
に含まれるモジュールとにメッセージを同報通信する場
合がしばしばある。上記のように、全てのノードがメッ
セージを確実に受信できるようにするため、あるノード
が受信した同報通信メッセージ、すなわち無接続メッセ
ージの各々をネットワーク内の他のノードに経路選択し
て送信するようにノードを構成することができる。この
場合、ノードは同一の同報通信メッセージを何回も受信
することになる。その結果、同報通信メッセージがネッ
トワークにあふれ、そのため他のメッセージの送信が遅
れることになる。
【０００８】本発明による構成においては、ノードは同
報通信メッセージを１回だけ受信する。すなわち、本発
明による構成において、例えばノード１は、自身が受信
した同報通信メッセージを隣接するノード（例えばノー
ド２）に転送するが、この転送は、本発明によれば（ａ
）ノード１がノード２よりもメッセージ源のノードに近
く、且つ（ｂ）ノード２の全ての隣接ノードの内で、ノ
ード１を経てメッセージ源のノードからノード２に至る
距離が最も短い場合にのみ行われる。
報通信メッセージを１回だけ受信する。すなわち、本発
明による構成において、例えばノード１は、自身が受信
した同報通信メッセージを隣接するノード（例えばノー
ド２）に転送するが、この転送は、本発明によれば（ａ
）ノード１がノード２よりもメッセージ源のノードに近
く、且つ（ｂ）ノード２の全ての隣接ノードの内で、ノ
ード１を経てメッセージ源のノードからノード２に至る
距離が最も短い場合にのみ行われる。
【０００９】例えば、もしノード１が、ノード６によっ
て作られた同報通信メッセージをリンク１０１を経て受
信した場合、ノード１は受信した同報通信メッセージを
リンク１０２を通してノード２に転送（再送信）する。 ノード１がこのように転送するのは、ノード１が同報通
信メッセージ源のノード６に対してノード２よりも近い
ことと、ノード２に隣接する全てのノード７、８、１の
間で、ノード１を経由する場合がメッセージ源からノー
ド２までの距離を最も短くできることとからである。
て作られた同報通信メッセージをリンク１０１を経て受
信した場合、ノード１は受信した同報通信メッセージを
リンク１０２を通してノード２に転送（再送信）する。 ノード１がこのように転送するのは、ノード１が同報通
信メッセージ源のノード６に対してノード２よりも近い
ことと、ノード２に隣接する全てのノード７、８、１の
間で、ノード１を経由する場合がメッセージ源からノー
ド２までの距離を最も短くできることとからである。
【００１０】次に、ノード２は同報通信メッセージを受
信しても、ノード８には転送しない。その理由は、ノー
ド２がメッセージ源のノード６に対してノード８よりも
近くないからである。この場合、ノード８にはノード５
がメッセージを転送する。その理由は、ノード８に隣接
する全ノードの間でノード５がメッセージ源のノード６
に、ノード２に比較して１リンクだけ近いからである。
信しても、ノード８には転送しない。その理由は、ノー
ド２がメッセージ源のノード６に対してノード８よりも
近くないからである。この場合、ノード８にはノード５
がメッセージを転送する。その理由は、ノード８に隣接
する全ノードの間でノード５がメッセージ源のノード６
に、ノード２に比較して１リンクだけ近いからである。
【００１１】更に、ノード１はノード６をメッセージ源
とする同報通信メッセージをノード５には転送しない。 その理由は、ノード１とノード６とがノード６から同一
距離（すなわちそれぞれ１つのリンク１０１及び１０４
からなる）にあるからである。したがって、ノード６は
同報通信メッセージをノード１とノード５との両方へ送
信する。
とする同報通信メッセージをノード５には転送しない。 その理由は、ノード１とノード６とがノード６から同一
距離（すなわちそれぞれ１つのリンク１０１及び１０４
からなる）にあるからである。したがって、ノード６は
同報通信メッセージをノード１とノード５との両方へ送
信する。
【００１２】ここにおいて、用語「距離」はあるノード
の、メッセージ源のノードからのリンクの数を意味する
ものとする。この用語は又、パス（経路）の「重み」も
意味するものとし、この場合、パスを構成する各リンク
には、それぞれのリンクに関連する所定の条件に基づい
て、単位重み、又はホップを持たせる。すなわち、リン
クの重みは、あるリンクでは「重み１」の場合もあり、
又別のリンクでは伝搬遅れの結果として「重み２」の場
合もあり得る。したがって、ある特定のパスの重み又は
距離は、そのパスを構成するリンクの重みの合計を意味
する。このように、用語「距離」と「重み」とは以下の
説明で交互に入れ換えて用いることがある。
の、メッセージ源のノードからのリンクの数を意味する
ものとする。この用語は又、パス（経路）の「重み」も
意味するものとし、この場合、パスを構成する各リンク
には、それぞれのリンクに関連する所定の条件に基づい
て、単位重み、又はホップを持たせる。すなわち、リン
クの重みは、あるリンクでは「重み１」の場合もあり、
又別のリンクでは伝搬遅れの結果として「重み２」の場
合もあり得る。したがって、ある特定のパスの重み又は
距離は、そのパスを構成するリンクの重みの合計を意味
する。このように、用語「距離」と「重み」とは以下の
説明で交互に入れ換えて用いることがある。
【００１３】追加例として、図２に、図１のネットワー
クのノード１及びノード５にそれぞれリンク１０８及び
１０９を経て接続されたノード９を図１に追加したネッ
トワークを示す。ノード９を同報通信メッセージ源とす
ると、ノード９はノード１とノード５との両方にメッセ
ージを送信する。図２から分かるように、ノード１とノ
ード５とは両方共ノード９から同一距離にあり、ノード
６からも同一距離にある。したがって、あるノードが同
報通信メッセージを隣接するノードすなわちノード６に
転送するかどうかを制御する条件は、ノード１とノード
５との両方に同等に当てはまる。
クのノード１及びノード５にそれぞれリンク１０８及び
１０９を経て接続されたノード９を図１に追加したネッ
トワークを示す。ノード９を同報通信メッセージ源とす
ると、ノード９はノード１とノード５との両方にメッセ
ージを送信する。図２から分かるように、ノード１とノ
ード５とは両方共ノード９から同一距離にあり、ノード
６からも同一距離にある。したがって、あるノードが同
報通信メッセージを隣接するノードすなわちノード６に
転送するかどうかを制御する条件は、ノード１とノード
５との両方に同等に当てはまる。
【００１４】このため、ノード６が１回だけメッセージ
を受信するようにするには、ノード９をメッセージ源と
する同報通信メッセージをノード１又はノード５のいず
れのノードが転送すべきかの問題が発生する。
を受信するようにするには、ノード９をメッセージ源と
する同報通信メッセージをノード１又はノード５のいず
れのノードが転送すべきかの問題が発生する。
【００１５】このような状況下で、いずれのノードがノ
ード６へ同報通信メッセージを転送するかの決定には、
本発明の態様によれば、ネットワークのこれらノードに
共通のパラメータを用いる。共通パラメータの一例は「
ノード識別」で、ここでノードはそれぞれのネットワー
クスイッチ番号で識別される。すなわち、上記のように
条件（規則）がいくつかのノードに同等に適合する場合
には、本発明の上記態様により、例えば最も小さいスイ
ッチ番号のノードが同報通信メッセージを転送する。
ード６へ同報通信メッセージを転送するかの決定には、
本発明の態様によれば、ネットワークのこれらノードに
共通のパラメータを用いる。共通パラメータの一例は「
ノード識別」で、ここでノードはそれぞれのネットワー
クスイッチ番号で識別される。すなわち、上記のように
条件（規則）がいくつかのノードに同等に適合する場合
には、本発明の上記態様により、例えば最も小さいスイ
ッチ番号のノードが同報通信メッセージを転送する。
【００１６】したがって、ノード９をメッセージ源とす
るメッセージを受信すると、ノード５ではなく、ノード
１がメッセージをノード６に転送する。その理由は、ノ
ード１に割り当てられたネットワークスイッチ番号（す
なわち値１）がノード５に割り当てられたネットワーク
スイッチ番号（すなわち値２）よりも小さいからである
。
るメッセージを受信すると、ノード５ではなく、ノード
１がメッセージをノード６に転送する。その理由は、ノ
ード１に割り当てられたネットワークスイッチ番号（す
なわち値１）がノード５に割り当てられたネットワーク
スイッチ番号（すなわち値２）よりも小さいからである
。
【００１７】又、上記の例と逆に、大きい方のスイッチ
番号のノードが同報通信メッセージを転送するように決
めることも可能であることは容易に理解されよう。
番号のノードが同報通信メッセージを転送するように決
めることも可能であることは容易に理解されよう。
【００１８】あるノードが同報通信メッセージをその隣
接するノードに転送すべきかどうかの決定は、本発明の
原理に基づき、又関連するネットワークのトポロジの知
識に基づきそのノードが構築する経路選択表に基づいて
行われる。この場合、トポロジは任意で、時に応じて変
化する。ノードは、このようなトポロジの知識を与えて
くれるいくつかの周知の方法の一つを用いてこの知識を
得て、この知識によって動的に経路選択表を作成する。 本発明の一実施例において、ネットワークの各ノードは
、一般に「排他的最小スパニング樹」法といわれる方法
を用いて関連するネットワークのトポロジを判定する。 この方法は、１９８４年８月１４日付けでリドル（Ｇ．
Ｇ．Ｒｉｄｄｌｅ）に対して発行された米国特許第４，
４６６，０６０号に開示されており、ここに引用文献と
する。
接するノードに転送すべきかどうかの決定は、本発明の
原理に基づき、又関連するネットワークのトポロジの知
識に基づきそのノードが構築する経路選択表に基づいて
行われる。この場合、トポロジは任意で、時に応じて変
化する。ノードは、このようなトポロジの知識を与えて
くれるいくつかの周知の方法の一つを用いてこの知識を
得て、この知識によって動的に経路選択表を作成する。 本発明の一実施例において、ネットワークの各ノードは
、一般に「排他的最小スパニング樹」法といわれる方法
を用いて関連するネットワークのトポロジを判定する。 この方法は、１９８４年８月１４日付けでリドル（Ｇ．
Ｇ．Ｒｉｄｄｌｅ）に対して発行された米国特許第４，
４６６，０６０号に開示されており、ここに引用文献と
する。
【００１９】上記特許の構成を簡単に説明すると、隣接
するノード同士が、メッセージ源のノードを含むノード
の内の、あるノード間を相互に接続するリンクについて
記述するメッセージを交換するが、メッセージを受信す
べきノードに関連するリンクは除外される。
するノード同士が、メッセージ源のノードを含むノード
の内の、あるノード間を相互に接続するリンクについて
記述するメッセージを交換するが、メッセージを受信す
べきノードに関連するリンクは除外される。
【００２０】すなわち、図１のノード１の場合、ノード
１は隣接するノード２、５、６の各々から排他的最小ス
パニング樹について記述するメッセージを受信する。こ
のメッセージにおいて上記の後者のノードすなわちノー
ド２、５、６の各々は、それぞれのスパニング樹の根に
位置づけられている。一方、ノード１は、本発明に基づ
き、受信したメッセージから経路選択表を構築する。こ
のような排他的最小スパニング樹を記述するメッセージ
のフォーマット例を図３に示す。
１は隣接するノード２、５、６の各々から排他的最小ス
パニング樹について記述するメッセージを受信する。こ
のメッセージにおいて上記の後者のノードすなわちノー
ド２、５、６の各々は、それぞれのスパニング樹の根に
位置づけられている。一方、ノード１は、本発明に基づ
き、受信したメッセージから経路選択表を構築する。こ
のような排他的最小スパニング樹を記述するメッセージ
のフォーマット例を図３に示す。
【００２１】具体的に説明すると、図３から分かるよう
に、経路選択メッセージのフォーマットは、特に「見出
し」とそれに続くデータフィールドとからなっている。 各メッセージの「見出し」は、Ｓ、Ｄ、Ｔフィールドを
含むいくつかのフィールドから構成されている。
に、経路選択メッセージのフォーマットは、特に「見出
し」とそれに続くデータフィールドとからなっている。 各メッセージの「見出し」は、Ｓ、Ｄ、Ｔフィールドを
含むいくつかのフィールドから構成されている。
【００２２】まず、Ｓフィールドは、メッセージ源（発
信元）を表す。本実施例においては、メッセージ３０１
から３０３までのＳフィールドの数字はそれぞれ、ノー
ド２、５、６を表す。次のＤフィールドは、メッセージ
の受信者を表す。Ｄフィールド欄のゼロ（０）は、この
メッセージが、このメッセージを受信する最初のノード
、すなわちノード１向けであることを示している。更に
、Ｔフィールドは、メッセージの形式を表す。Ｔフィー
ルド欄のＲはメッセージが経路選択（ｒｏｕｔｉｎｇ）
に関するメッセージであることを表している。
信元）を表す。本実施例においては、メッセージ３０１
から３０３までのＳフィールドの数字はそれぞれ、ノー
ド２、５、６を表す。次のＤフィールドは、メッセージ
の受信者を表す。Ｄフィールド欄のゼロ（０）は、この
メッセージが、このメッセージを受信する最初のノード
、すなわちノード１向けであることを示している。更に
、Ｔフィールドは、メッセージの形式を表す。Ｔフィー
ルド欄のＲはメッセージが経路選択（ｒｏｕｔｉｎｇ）
に関するメッセージであることを表している。
【００２３】見出しに続くデータフィールドである「サ
ービス区域」（ＳＡ）のフィールドは、排他的最小スパ
ニング樹について記述している。ここにおいて、「サー
ビス区域」のフィールドは、順位付けした一連番号から
なっていて、これら一連番号は、メッセージを送ってい
るノードに関連する排他的最小スパニング樹を表す。メ
ッセージ源は「サービス区域」フィールドにおけるゼロ
の位置によっても表される。残りのデータ位置に含まれ
る値は、「サービス区域」フィールドのバイト順によっ
て識別されるノードの親ノード（上位ノード）を表す。
ービス区域」（ＳＡ）のフィールドは、排他的最小スパ
ニング樹について記述している。ここにおいて、「サー
ビス区域」のフィールドは、順位付けした一連番号から
なっていて、これら一連番号は、メッセージを送ってい
るノードに関連する排他的最小スパニング樹を表す。メ
ッセージ源は「サービス区域」フィールドにおけるゼロ
の位置によっても表される。残りのデータ位置に含まれ
る値は、「サービス区域」フィールドのバイト順によっ
て識別されるノードの親ノード（上位ノード）を表す。
【００２４】すなわち、メッセージ３０１における、デ
ータ位置７と８の欄の値「２」は、ノード２からノード
１に送られた排他的最小スパニング樹メッセージに関連
して、ノード２がノード７と８の親ノードであることを
示している。メッセージ３０１における、データ位置５
及び６の欄のそれぞれの値「８」と「５」は、ノード２
に関連してノード５と６の親ノードがそれぞれノード８
とノード５であることを示している。
ータ位置７と８の欄の値「２」は、ノード２からノード
１に送られた排他的最小スパニング樹メッセージに関連
して、ノード２がノード７と８の親ノードであることを
示している。メッセージ３０１における、データ位置５
及び６の欄のそれぞれの値「８」と「５」は、ノード２
に関連してノード５と６の親ノードがそれぞれノード８
とノード５であることを示している。
【００２５】メッセージ３０２及び３０３も、ノード５
と６からノード１に送られたそれぞれの排他的最小スパ
ニング樹メッセージに関連して、類似の情報を含んでい
る。
と６からノード１に送られたそれぞれの排他的最小スパ
ニング樹メッセージに関連して、類似の情報を含んでい
る。
【００２６】メッセージ３０１から３０３までによって
記述されている排他的最小スパニング樹を図形で表した
ものが図４である。ノード１は、これらの排他的最小ス
パニング樹に基づき、且つ本発明の原理を用いて、図５
に示す経路選択表を構築する。ノード１は、この表を用
いて、最終転送先のノードまでの無接続同報通信メッセ
ージの経路選択を制御する。
記述されている排他的最小スパニング樹を図形で表した
ものが図４である。ノード１は、これらの排他的最小ス
パニング樹に基づき、且つ本発明の原理を用いて、図５
に示す経路選択表を構築する。ノード１は、この表を用
いて、最終転送先のノードまでの無接続同報通信メッセ
ージの経路選択を制御する。
【００２７】図１及び図５を参照して具体的に説明すれ
ば、経路選択表５０１の行５０２において、ノード１は
リンク１０２を経て同報通信メッセージを受け入れるが
それは、その同報通信メッセージがノード２、７、又は
８で作られた場合のみであり、それ以外の同報通信メッ
セージは全て拒絶することが示されている。例えば、も
しノード１が、ノード５の作った同報通信メッセージを
リンク１０２を経て受信した場合、ノード１はそのメッ
セージを拒絶する。
ば、経路選択表５０１の行５０２において、ノード１は
リンク１０２を経て同報通信メッセージを受け入れるが
それは、その同報通信メッセージがノード２、７、又は
８で作られた場合のみであり、それ以外の同報通信メッ
セージは全て拒絶することが示されている。例えば、も
しノード１が、ノード５の作った同報通信メッセージを
リンク１０２を経て受信した場合、ノード１はそのメッ
セージを拒絶する。
【００２８】更に表５０１の行５０３において、ノード
１がノード１、５、又は６の作った同報通信メッセージ
をリンク１０２を経て送信することが示され、又これら
のメッセージは他のリンク１０５又は１０１の内のいず
れかのリンクを通して受信してもよいことも示されてい
る。
１がノード１、５、又は６の作った同報通信メッセージ
をリンク１０２を経て送信することが示され、又これら
のメッセージは他のリンク１０５又は１０１の内のいず
れかのリンクを通して受信してもよいことも示されてい
る。
【００２９】同様に、行５０４に示すように、ノード１
は、リンク１０５を経て受信された同報通信メッセージ
がノード５によって作られた同報通信メッセージである
場合のみ、この同報通信メッセージを受け入れる。又、
行５０５に示すように、ノード１は、ノード１、２、又
は７によって作られた同報通信メッセージのみをリンク
１０５を通して送信する。
は、リンク１０５を経て受信された同報通信メッセージ
がノード５によって作られた同報通信メッセージである
場合のみ、この同報通信メッセージを受け入れる。又、
行５０５に示すように、ノード１は、ノード１、２、又
は７によって作られた同報通信メッセージのみをリンク
１０５を通して送信する。
【００３０】リンク１０１についていえば、表５０１の
行５０６が示すように、ノード１は、リンク１０１を経
て受信された同報通信メッセージがノード６によって作
られた同報通信メッセージの場合のみ、この同報通信メ
ッセージを受け入れる。又、行５０７に示すように、ノ
ード１は、ノード１、２、又は７によって作られた同報
通信メッセージのみをリンク１０１を通して送信する。
行５０６が示すように、ノード１は、リンク１０１を経
て受信された同報通信メッセージがノード６によって作
られた同報通信メッセージの場合のみ、この同報通信メ
ッセージを受け入れる。又、行５０７に示すように、ノ
ード１は、ノード１、２、又は７によって作られた同報
通信メッセージのみをリンク１０１を通して送信する。
【００３１】例えば、もしノード１が、ノード６によっ
て作られた同報通信メッセージをリンク１０１を経て受
信した場合、ノード１は表５０１に応じてメッセージを
受け入れ、このメッセージをその内部母線（図示しない
）上に載せる。リンク１０１、１０２、１０５と関連す
るノード１の回路は、表５０１中の対応する行のコピー
を内蔵して、上記母線を監視し、蓄積されたメッセージ
を読み取る。
て作られた同報通信メッセージをリンク１０１を経て受
信した場合、ノード１は表５０１に応じてメッセージを
受け入れ、このメッセージをその内部母線（図示しない
）上に載せる。リンク１０１、１０２、１０５と関連す
るノード１の回路は、表５０１中の対応する行のコピー
を内蔵して、上記母線を監視し、蓄積されたメッセージ
を読み取る。
【００３２】リンク１０１、１０５と関連するノード１
の回路は、ノード６によって作られた、母線上の同報通
信メッセージを調査し、その後は廃棄する。その理由は
、表５０１の５０６ー５０７及び５０４ー５０５のそれ
ぞれの行によって指定されたように、ノード６によって
作られた同報通信メッセージはリンク１０１と１０５を
介して送信されないからである。
の回路は、ノード６によって作られた、母線上の同報通
信メッセージを調査し、その後は廃棄する。その理由は
、表５０１の５０６ー５０７及び５０４ー５０５のそれ
ぞれの行によって指定されたように、ノード６によって
作られた同報通信メッセージはリンク１０１と１０５を
介して送信されないからである。
【００３３】一方、リンク１０２に関連するノード１の
回路は、表５０１の行５０２及び５０３によって指定さ
れたように同報通信メッセージを母線から取り去り、リ
ンク１０２を通して送信する。このようにして、図１に
関連して初めに述べたように、ノード１はノード６によ
って作られた同報通信メッセージをノード２に送信する
が、ノード５へは送信しない。すなわち、同報通信メッ
セージの経路選択の制御についての本発明の原理は、表
５０１が指定する経路選択に具体化されている。
回路は、表５０１の行５０２及び５０３によって指定さ
れたように同報通信メッセージを母線から取り去り、リ
ンク１０２を通して送信する。このようにして、図１に
関連して初めに述べたように、ノード１はノード６によ
って作られた同報通信メッセージをノード２に送信する
が、ノード５へは送信しない。すなわち、同報通信メッ
セージの経路選択の制御についての本発明の原理は、表
５０１が指定する経路選択に具体化されている。
【００３４】上記のように、ノード、例えばノード１は
、本発明の原理に基づき、又関連するネットワークのト
ポロジの知識に基づき、関連する経路選択表を構築する
。ノードがこのような表を構築する方法を、図４及び図
５に関連して、例えばノード１の場合について以下に簡
単に説明する。
、本発明の原理に基づき、又関連するネットワークのト
ポロジの知識に基づき、関連する経路選択表を構築する
。ノードがこのような表を構築する方法を、図４及び図
５に関連して、例えばノード１の場合について以下に簡
単に説明する。
【００３５】まず、ノード１は、図４のスパニング樹を
用いて、ノード１から別のノード（活動ノード（ＡＮ）
）、例えばノード２、に至る第１のパスの「重み」、及
びノード１に隣接するノード（隣接ノード（ＮＮ））の
内の特定のノード、例えばノード５、からノード１を通
らずに、しかし他ノード（０Ｎ）、例えばノード８、を
通ってノード２に至る第２のパスの「重み」を定める。 次にノード１は、第二のパスの「重み」と［第１のパス
の「重み」＋１］とを比較する。ここに、「＋１」はノ
ード１から特定の隣接するノードに至るパスの「重み」
を表す。
用いて、ノード１から別のノード（活動ノード（ＡＮ）
）、例えばノード２、に至る第１のパスの「重み」、及
びノード１に隣接するノード（隣接ノード（ＮＮ））の
内の特定のノード、例えばノード５、からノード１を通
らずに、しかし他ノード（０Ｎ）、例えばノード８、を
通ってノード２に至る第２のパスの「重み」を定める。 次にノード１は、第二のパスの「重み」と［第１のパス
の「重み」＋１］とを比較する。ここに、「＋１」はノ
ード１から特定の隣接するノードに至るパスの「重み」
を表す。
【００３６】この場合、ノード１は両方の「重み」が等
しいことを見いだす。しかし、ノード１は、ノード１が
ノード２によって作られた同報通信メッセージをリンク
１０２を経て受け入れるべきこと、又、ノード２によっ
て作られた同報通信メッセージをリンク１０５を経て送
信すべきことを決定することになる。その理由は、ノー
ド１のアドレスの値がノード８のアドレスの値よりも小
さいからである（すなわち１＜８）。
しいことを見いだす。しかし、ノード１は、ノード１が
ノード２によって作られた同報通信メッセージをリンク
１０２を経て受け入れるべきこと、又、ノード２によっ
て作られた同報通信メッセージをリンク１０５を経て送
信すべきことを決定することになる。その理由は、ノー
ド１のアドレスの値がノード８のアドレスの値よりも小
さいからである（すなわち１＜８）。
【００３７】別の例として、もしノード１に隣接するノ
ードがノード６であり（ＮＮ）、第２のパスがノード５
（ＯＮ）を経由すると仮定すると、第２のパスの「重み
」は［第１のパスの「重み」＋１］よりも大きい。その
結果、ノード１はノード２によって作られたメッセージ
をリンク１０１を通して送信すべきとの結論に達し、そ
のことを表５０１の行５０７に記録する。
ードがノード６であり（ＮＮ）、第２のパスがノード５
（ＯＮ）を経由すると仮定すると、第２のパスの「重み
」は［第１のパスの「重み」＋１］よりも大きい。その
結果、ノード１はノード２によって作られたメッセージ
をリンク１０１を通して送信すべきとの結論に達し、そ
のことを表５０１の行５０７に記録する。
【００３８】更に別の例として、もしノード１に隣接す
るノードがノード２であり（ＮＮ）、メッセージがノー
ド６（ＡＮ）によって作られ、第１のパスがノード５（
ＯＮ）を経由すると仮定すると、［第１のパスの「重み
」＋１］が第２のパスの「重み」よりも小さい。その結
果、ノード１はノード６によって作られたメッセージを
リンク１０２を通して送信すべきとの結論に達し、その
ことを表５０１の行５０３に記録する。同様に、ノード
１はノード６によって作られたメッセージをリンク１０
１を通して受信すべきとの結論に達し、そのことを表５
０１の行５０６に記録する。
るノードがノード２であり（ＮＮ）、メッセージがノー
ド６（ＡＮ）によって作られ、第１のパスがノード５（
ＯＮ）を経由すると仮定すると、［第１のパスの「重み
」＋１］が第２のパスの「重み」よりも小さい。その結
果、ノード１はノード６によって作られたメッセージを
リンク１０２を通して送信すべきとの結論に達し、その
ことを表５０１の行５０３に記録する。同様に、ノード
１はノード６によって作られたメッセージをリンク１０
１を通して受信すべきとの結論に達し、そのことを表５
０１の行５０６に記録する。
【００３９】ノード１は、表５０１の構築、すなわち５
０２から５０７までの行の記入、が完了するまで、上記
の手順を図４のスパニング樹について繰り返し実施する
。これらの手順の実施については、以下に更に詳しく説
明する。次いでノード１は、表中の該当する行を、リン
ク１０１、１０２、１０５の個々の回路に接続するそれ
ぞれのノード１の回路に記憶する。
０２から５０７までの行の記入、が完了するまで、上記
の手順を図４のスパニング樹について繰り返し実施する
。これらの手順の実施については、以下に更に詳しく説
明する。次いでノード１は、表中の該当する行を、リン
ク１０１、１０２、１０５の個々の回路に接続するそれ
ぞれのノード１の回路に記憶する。
【００４０】ノード２も隣接するノード、すなわちノー
ド１、７、８からそれぞれの排他的最小スパニング樹の
詳細を記述した経路選択メッセージ（図示しない）を受
信する。上記と同様に、ノード２は受信した排他的最小
スパニング樹のメッセージを用いて、図６に示すような
ノード２の経路選択表を構築する。ノード２は、行６０
２に指定された経路選択情報によって、リンク１０２を
経て受信した同報通信メッセージがノード１、５、また
は６によって作られたメッセージである場合にのみこの
メッセージを受け入れることが分かる。
ド１、７、８からそれぞれの排他的最小スパニング樹の
詳細を記述した経路選択メッセージ（図示しない）を受
信する。上記と同様に、ノード２は受信した排他的最小
スパニング樹のメッセージを用いて、図６に示すような
ノード２の経路選択表を構築する。ノード２は、行６０
２に指定された経路選択情報によって、リンク１０２を
経て受信した同報通信メッセージがノード１、５、また
は６によって作られたメッセージである場合にのみこの
メッセージを受け入れることが分かる。
【００４１】表６０１を調べると、行６０３に示すよう
に、ノード６によって作られた同報通信メッセージがリ
ンク１０６を介してノード２によってのみ送信されるこ
とが分かる。表６０１を更に調べると、ノード２がノー
ド５に接続されたリンク１０７を通してこれらのメッセ
ージを送信しないことが分かる。このようにして、ネッ
トワークの各ノードが、本発明の原理により構築された
それぞれの経路選択表に従って同報通信メッセージを経
路選択することが分かる。
に、ノード６によって作られた同報通信メッセージがリ
ンク１０６を介してノード２によってのみ送信されるこ
とが分かる。表６０１を更に調べると、ノード２がノー
ド５に接続されたリンク１０７を通してこれらのメッセ
ージを送信しないことが分かる。このようにして、ネッ
トワークの各ノードが、本発明の原理により構築された
それぞれの経路選択表に従って同報通信メッセージを経
路選択することが分かる。
【００４２】次に、図７は、図１及び２に示すノードの
どれにも用い得るデータノード７００を示す。このノー
ド７００には、例えばＡＴ＆Ｔ社から入手可能な周知の
、データキット（Ｄａｔａｋｉｔ） 仮想回路スイッチ
を用いる。簡単に説明すると、ノード７００は複数の回
路モジュールと、それぞれクロックモジュール７０１、
回路（ポート）モジュール７０２−１〜７０２−Ｎ及び
制御スイッチモジュール７０３を受けるためのコネクタ
ーを備えたいわゆるプリント配線背面板とからなる。プ
リント配線背面板はコンテンション母線７０４及び同報
通信母線７０５を具体化したものである。プリント配線
背面板は又、クロックモジュール７０１から他のモジュ
ールへの信号配分も行う。
どれにも用い得るデータノード７００を示す。このノー
ド７００には、例えばＡＴ＆Ｔ社から入手可能な周知の
、データキット（Ｄａｔａｋｉｔ） 仮想回路スイッチ
を用いる。簡単に説明すると、ノード７００は複数の回
路モジュールと、それぞれクロックモジュール７０１、
回路（ポート）モジュール７０２−１〜７０２−Ｎ及び
制御スイッチモジュール７０３を受けるためのコネクタ
ーを備えたいわゆるプリント配線背面板とからなる。プ
リント配線背面板はコンテンション母線７０４及び同報
通信母線７０５を具体化したものである。プリント配線
背面板は又、クロックモジュール７０１から他のモジュ
ールへの信号配分も行う。
【００４３】背面板コネクターにプラグインされた、例
えば７０２−１のようなモジュールは自動的に母線７０
４及び７０５に接続される。母線７０４は、ポートモジ
ュールの一つによって母線７０４上に記憶されたデータ
メッセージを制御スイッチモジュール７０３に送る。一
方、母線７０５は、データメッセージをスイッチモジュ
ール７０３から、母線７０５を監視するポートモジュー
ル７０２−０〜７０２−Ｎに送る。母線７０４の制御は
モジュール番号を用いる優先コンテンション要綱に基づ
くもので、ポートモジュール７０２−１〜７０２−Ｎの
各々によって行われる。
えば７０２−１のようなモジュールは自動的に母線７０
４及び７０５に接続される。母線７０４は、ポートモジ
ュールの一つによって母線７０４上に記憶されたデータ
メッセージを制御スイッチモジュール７０３に送る。一
方、母線７０５は、データメッセージをスイッチモジュ
ール７０３から、母線７０５を監視するポートモジュー
ル７０２−０〜７０２−Ｎに送る。母線７０４の制御は
モジュール番号を用いる優先コンテンション要綱に基づ
くもので、ポートモジュール７０２−１〜７０２−Ｎの
各々によって行われる。
【００４４】すなわち、ポート７０２−１は、メッセー
ジを他のポートモジュール例えばポート７０２−２に送
るための母線の制御を求めて争う。ポート７０２−１が
この制御権を獲得すると、送りだしポートは母線７０４
上にメッセージを定義するパケットを置く。メッセージ
受信後、制御スイッチモジュール７０３は、一般に経路
選択制御メモリといわれるものを用いて、メッセージ源
と受信側との接続を行う。
ジを他のポートモジュール例えばポート７０２−２に送
るための母線の制御を求めて争う。ポート７０２−１が
この制御権を獲得すると、送りだしポートは母線７０４
上にメッセージを定義するパケットを置く。メッセージ
受信後、制御スイッチモジュール７０３は、一般に経路
選択制御メモリといわれるものを用いて、メッセージ源
と受信側との接続を行う。
【００４５】ポートモジュールは個々に、図１及び図２
に示すリンクのような、別のノードへつながるリンクに
対して対応作動する。このように、リンクに対して対応
作動するポートは、関連するリンクを経て同報通信メッ
セージを受信して受け入れ、このメッセージを母線に載
せてスイッチ７０３に送り、スイッチ７０３はこのメッ
セージを母線７０５に載せる。上記のように各ポートモ
ジュールは母線７０５を監視しているので、受信モジュ
ール以外の他のリンクモジュールの一つがその経路選択
表に基づいて母線７０５からこのメッセージを取り去り
、そのモジュール自身が対応しているリンクを通して送
る。
に示すリンクのような、別のノードへつながるリンクに
対して対応作動する。このように、リンクに対して対応
作動するポートは、関連するリンクを経て同報通信メッ
セージを受信して受け入れ、このメッセージを母線に載
せてスイッチ７０３に送り、スイッチ７０３はこのメッ
セージを母線７０５に載せる。上記のように各ポートモ
ジュールは母線７０５を監視しているので、受信モジュ
ール以外の他のリンクモジュールの一つがその経路選択
表に基づいて母線７０５からこのメッセージを取り去り
、そのモジュール自身が対応しているリンクを通して送
る。
【００４６】次に、図８〜１０は、図１１に示すように
組み合わせて、ネットワークの各ノードにおいて本発明
を実施するためのプログラムの流れ図を示す。以下の説
明において、あるノード（現ノード（ＣＮ）と呼ぶ）が
他のネットワークノードからそれぞれの排他的最小スパ
ニング樹メッセージを受信し、関連する経路選択表を構
築するためのプログラムを呼び出す、と仮定する。又、
ネットワーク内に現ノード（ＣＮ）以外にＮ個のノード
（活動ノード（ＡＮ））があり、更に、現ノード（ＣＮ
）はＭ個の隣接ノード（ＮＮ）を有する、と仮定する。 ここに、Ｍ及びＮは、Ｍ，Ｎ≧１である。
組み合わせて、ネットワークの各ノードにおいて本発明
を実施するためのプログラムの流れ図を示す。以下の説
明において、あるノード（現ノード（ＣＮ）と呼ぶ）が
他のネットワークノードからそれぞれの排他的最小スパ
ニング樹メッセージを受信し、関連する経路選択表を構
築するためのプログラムを呼び出す、と仮定する。又、
ネットワーク内に現ノード（ＣＮ）以外にＮ個のノード
（活動ノード（ＡＮ））があり、更に、現ノード（ＣＮ
）はＭ個の隣接ノード（ＮＮ）を有する、と仮定する。 ここに、Ｍ及びＮは、Ｍ，Ｎ≧１である。
【００４７】図８〜１０を参照して説明すると、プログ
ラムは、ブロック８００において開始され、ブロック８
０１において、ループ変数「ｉ」を、第１の活動ノード
（ＡＮ）に対して１に等しく設定する。（プログラムは
入れ子構造のＩＦ／ＥＬＳＥステートメントを用いてコ
ード化されている。）プログラムがブロック８０１の処
理を終わると、ブロック８０２に進み、ここで、パラメ
ータ「ｒ」を、プログラムが処理する可能性のあるどの
パスの最小重み（ホップ数）よりも大きい値を表す任意
の数（例として９９９９）に等しく設定する。
ラムは、ブロック８００において開始され、ブロック８
０１において、ループ変数「ｉ」を、第１の活動ノード
（ＡＮ）に対して１に等しく設定する。（プログラムは
入れ子構造のＩＦ／ＥＬＳＥステートメントを用いてコ
ード化されている。）プログラムがブロック８０１の処
理を終わると、ブロック８０２に進み、ここで、パラメ
ータ「ｒ」を、プログラムが処理する可能性のあるどの
パスの最小重み（ホップ数）よりも大きい値を表す任意
の数（例として９９９９）に等しく設定する。
【００４８】次にプログラムはブロック８０３に進み、
ここで排他的最小スパニング樹を処理する。すなわち、
プログラムがノードＡＮ［ｉ］ を選択してから、ノー
ドＣＮとノードＡＮ［ｉ］ との間のパスの最小重み（
ＣＮＤＩＳＴ）を定める。次いでブロック８０４に進み
、ここで第２のループ変数「ｊ」を、第１の隣接ノード
（ＮＮ）に対して１に等しく設定する。プログラムはそ
の後ブロック８０５に進む。
ここで排他的最小スパニング樹を処理する。すなわち、
プログラムがノードＡＮ［ｉ］ を選択してから、ノー
ドＣＮとノードＡＮ［ｉ］ との間のパスの最小重み（
ＣＮＤＩＳＴ）を定める。次いでブロック８０４に進み
、ここで第２のループ変数「ｊ」を、第１の隣接ノード
（ＮＮ）に対して１に等しく設定する。プログラムはそ
の後ブロック８０５に進む。
【００４９】ブロック８０５においてプログラムは、ノ
ードＮＮ［ｊ］ からノードＣＮを経由せずにノードＡ
Ｎ［ｉ］ に到達できるかどうかを判定する。もし到達
しない（ＮＯ）なら、図９のブロック８１４に進む。到
達する（ＹＥＳ）なら、ブロック８０６に進む。ブロッ
ク８０６においてプログラムは、ノードＮＮ［ｉ］ と
ノードＡＮ［ｊ］ との間の最短パス（ＮＮＤＩＳＴ）
を判定する。ここでいうパスには、現ノードＣＮ以外の
他ノード（ＯＮ）を含む。
ードＮＮ［ｊ］ からノードＣＮを経由せずにノードＡ
Ｎ［ｉ］ に到達できるかどうかを判定する。もし到達
しない（ＮＯ）なら、図９のブロック８１４に進む。到
達する（ＹＥＳ）なら、ブロック８０６に進む。ブロッ
ク８０６においてプログラムは、ノードＮＮ［ｉ］ と
ノードＡＮ［ｊ］ との間の最短パス（ＮＮＤＩＳＴ）
を判定する。ここでいうパスには、現ノードＣＮ以外の
他ノード（ＯＮ）を含む。
【００５０】プログラムは次にブロック８０７に進み、
ここで「ＮＮＤＩＳＴの値」を「ＣＮＤＩＳＴの値＋１
」と比較する。そして、前者の値が後者の値より大きい
（ＹＥＳ）なら、ブロック８０８に進む。大きくない（
ＮＯ）なら、９図のブロック８０９に進む。ブロック８
０８においてプログラムは、ノードＣＮが、ノードＡＮ
［ｉ］ の作った無接続同報通信メッセージ全てをノー
ドＮＮ［ｊ］ に送るべきであるとの結論を出し、この
結論を関連する経路選択表に上記の方法で記録する。そ
の後、プログラムは図９のブロック８１４に進む。
ここで「ＮＮＤＩＳＴの値」を「ＣＮＤＩＳＴの値＋１
」と比較する。そして、前者の値が後者の値より大きい
（ＹＥＳ）なら、ブロック８０８に進む。大きくない（
ＮＯ）なら、９図のブロック８０９に進む。ブロック８
０８においてプログラムは、ノードＣＮが、ノードＡＮ
［ｉ］ の作った無接続同報通信メッセージ全てをノー
ドＮＮ［ｊ］ に送るべきであるとの結論を出し、この
結論を関連する経路選択表に上記の方法で記録する。そ
の後、プログラムは図９のブロック８１４に進む。
【００５１】図９のブロック８０９において、プログラ
ムは、再び「ＮＮＤＩＳＴの値」を「ＣＮＤＩＳＴの値
＋１」と比較する。そして、前者の値が後者の値より小
さい（ＹＥＳ）なら、ブロック８１０に進む。小さくな
い（ＮＯ）なら、ブロック８１１に進む。ブロック８１
０において、プログラムは、ノードＯＮが、ノードＡＮ
［ｉ］ の作った無接続同報通信メッセージ全てをノー
ドＮＮ［ｊ］ に送るべきであるとの結論を出し、その
後、プログラムはブロック８１４に進む。
ムは、再び「ＮＮＤＩＳＴの値」を「ＣＮＤＩＳＴの値
＋１」と比較する。そして、前者の値が後者の値より小
さい（ＹＥＳ）なら、ブロック８１０に進む。小さくな
い（ＮＯ）なら、ブロック８１１に進む。ブロック８１
０において、プログラムは、ノードＯＮが、ノードＡＮ
［ｉ］ の作った無接続同報通信メッセージ全てをノー
ドＮＮ［ｊ］ に送るべきであるとの結論を出し、その
後、プログラムはブロック８１４に進む。
【００５２】ブロック８１１において、プログラムは、
ノードＯＮに割り当てられた上記の一般的パラメータ、
例えばアドレス、の値を現ノードＣＮに割り当てられた
値と比較する。前者の値が後者の値より大きい（ＹＥＳ
）なら、ブロック８１２に進む。そうでない（ＮＯ）な
ら、ブロック８１３に進む。ブロック８１２において、
プログラムは、ノードＣＮが、ノードＡＮ［ｉ］ の作
った無接続同報通信メッセージ全てをノードＮＮ［ｊ］
に送るべきであるとの結論を出し、この結論を関連す
る経路選択表に上記の方法で記録する。
ノードＯＮに割り当てられた上記の一般的パラメータ、
例えばアドレス、の値を現ノードＣＮに割り当てられた
値と比較する。前者の値が後者の値より大きい（ＹＥＳ
）なら、ブロック８１２に進む。そうでない（ＮＯ）な
ら、ブロック８１３に進む。ブロック８１２において、
プログラムは、ノードＣＮが、ノードＡＮ［ｉ］ の作
った無接続同報通信メッセージ全てをノードＮＮ［ｊ］
に送るべきであるとの結論を出し、この結論を関連す
る経路選択表に上記の方法で記録する。
【００５３】ブロック８１３において、プログラムは、
ノードＯＮが、ノードＡＮ［ｉ］ の作った無接続同報
通信メッセージ全てをノードＮＮ［ｊ］ に送るべきで
あるとの結論を出し、その後、プログラムはブロック８
１４に進む。
ノードＯＮが、ノードＡＮ［ｉ］ の作った無接続同報
通信メッセージ全てをノードＮＮ［ｊ］ に送るべきで
あるとの結論を出し、その後、プログラムはブロック８
１４に進む。
【００５４】ブロック８１４からブロック８１９までの
ブロックは、本プログラム中、無接続同報通信メッセー
ジをノードＡＮ［ｉ］ から受信すべきかどうかを判定
する段階を設定する部分である。まずブロック８１４に
おいて、もし現ＮＮＤＩＳＴの値がパラメータ「ｒ］の
値より小さい（ＹＥＳ）なら、プログラムはブロック８
１５に進む。そうでない（ＮＯ）なら、ブロック８１７
に進む。
ブロックは、本プログラム中、無接続同報通信メッセー
ジをノードＡＮ［ｉ］ から受信すべきかどうかを判定
する段階を設定する部分である。まずブロック８１４に
おいて、もし現ＮＮＤＩＳＴの値がパラメータ「ｒ］の
値より小さい（ＹＥＳ）なら、プログラムはブロック８
１５に進む。そうでない（ＮＯ）なら、ブロック８１７
に進む。
【００５５】ブロック８１５において、プログラムは、
パラメータ「ｒ］を現ＮＮＤＩＳＴの値に設定して、ブ
ロック８１６に進む。ブロック８１６において、プログ
ラムは、Ｒノードを隣接ノードＮＮ［ｊ］ の識別子（
アドレス）に等しく設定して図１０のブロック８２０に
進む。
パラメータ「ｒ］を現ＮＮＤＩＳＴの値に設定して、ブ
ロック８１６に進む。ブロック８１６において、プログ
ラムは、Ｒノードを隣接ノードＮＮ［ｊ］ の識別子（
アドレス）に等しく設定して図１０のブロック８２０に
進む。
【００５６】ブロック８１７においてプログラムは、も
し現ＮＮＤＩＳＴの値がパラメータ「ｒ］の値に等しい
（ＹＥＳ）なら、プログラムはブロック８１８に進む。 そうでない（ＮＯ）なら、ブロック８２０に進む。ブロ
ック８１８において、プログラムは、もし隣接ノードＮ
Ｎ［ｊ］ に割り当てられたアドレスの値がＲノードの
値より小さい（ＹＥＳ）なら、ブロック８１９に進む。 そうでない（ＮＯ）ならブロック８２０に進む。ブロッ
ク８１９において、プログラムは、Ｒノードを隣接ノー
ドＮＮ［ｊ］ の識別子（アドレス）に等しく設定して
図１０のブロック８２０に進む。
し現ＮＮＤＩＳＴの値がパラメータ「ｒ］の値に等しい
（ＹＥＳ）なら、プログラムはブロック８１８に進む。 そうでない（ＮＯ）なら、ブロック８２０に進む。ブロ
ック８１８において、プログラムは、もし隣接ノードＮ
Ｎ［ｊ］ に割り当てられたアドレスの値がＲノードの
値より小さい（ＹＥＳ）なら、ブロック８１９に進む。 そうでない（ＮＯ）ならブロック８２０に進む。ブロッ
ク８１９において、プログラムは、Ｒノードを隣接ノー
ドＮＮ［ｊ］ の識別子（アドレス）に等しく設定して
図１０のブロック８２０に進む。
【００５７】ブロック８２０において、プログラムは、
「ｊ］の値をＭの値と比較する。もし値が互いに等しい
（ＹＥＳ）なら、ブロック８２２に進む。そうでない（
ＮＯ）なら、ブロック８２１に進む。ブロック８２１に
おいて、「ｊ］の値を「１」だけ増加させ、図８のブロ
ック８０５に進む。ブロック８０５において、プログラ
ムは、現ノードＣＮが、ノードＡＮ［ｉ］ の作った無
接続同報通信メッセージの全てを次に隣接するＮＮ［ｊ
＋１］ に送るべきかどうかを判定する。
「ｊ］の値をＭの値と比較する。もし値が互いに等しい
（ＹＥＳ）なら、ブロック８２２に進む。そうでない（
ＮＯ）なら、ブロック８２１に進む。ブロック８２１に
おいて、「ｊ］の値を「１」だけ増加させ、図８のブロ
ック８０５に進む。ブロック８０５において、プログラ
ムは、現ノードＣＮが、ノードＡＮ［ｉ］ の作った無
接続同報通信メッセージの全てを次に隣接するＮＮ［ｊ
＋１］ に送るべきかどうかを判定する。
【００５８】ブロック８２２において、プログラムは、
現ノードＣＮが、Ｒノードに関連するリンクを経てノー
ドＡＮ［ｉ］ から無接続同報通信メッセージの全てを
受信すべきであることを、関連する経路選択表に記録す
る。 次にプログラムは、ブロック８２３に進み、そこで「ｉ
」の値を活動ノードの数の値と比較する。もしこれらの
値が互いに等しい（ＹＥＳ）なら、ブロック８２４を経
てプログラムは終了する。そうでない（ＮＯ）なら、ブ
ロック８２５に進み、そこで「ｉ」の値を「１」だけ増
加させ、図８のブロック８０２に進む。
現ノードＣＮが、Ｒノードに関連するリンクを経てノー
ドＡＮ［ｉ］ から無接続同報通信メッセージの全てを
受信すべきであることを、関連する経路選択表に記録す
る。 次にプログラムは、ブロック８２３に進み、そこで「ｉ
」の値を活動ノードの数の値と比較する。もしこれらの
値が互いに等しい（ＹＥＳ）なら、ブロック８２４を経
てプログラムは終了する。そうでない（ＮＯ）なら、ブ
ロック８２５に進み、そこで「ｉ」の値を「１」だけ増
加させ、図８のブロック８０２に進む。
【００５９】このようにして、プログラムは、ＩＦステ
ートメントの外側の一つのステートメントを介してＡＮ
［ｉ］ からＡＮ［Ｎ］ までのノードを一つづつ選択
した後、内側のＩＦステートメントを介してノードＣＮ
が、ノードＡＮ［ｉ］ が作った無接続同報通信メッセ
ージをＮＮ［ｊ］ からＮＮ［Ｍ］ までの隣接ノード
の各々に送るべきかどうかを判定する。同様に、現ノー
ドＣＮは、ノードＡＮ［ｉ］ が作った無接続同報通信
メッセージを受信すべきかどうかを判定する。
ートメントの外側の一つのステートメントを介してＡＮ
［ｉ］ からＡＮ［Ｎ］ までのノードを一つづつ選択
した後、内側のＩＦステートメントを介してノードＣＮ
が、ノードＡＮ［ｉ］ が作った無接続同報通信メッセ
ージをＮＮ［ｊ］ からＮＮ［Ｍ］ までの隣接ノード
の各々に送るべきかどうかを判定する。同様に、現ノー
ドＣＮは、ノードＡＮ［ｉ］ が作った無接続同報通信
メッセージを受信すべきかどうかを判定する。
【００６０】以上の説明は、本発明の一実施例に関する
もので、この技術分野の当業者であれば、本発明の種々
の変形例を考え得るが、それらはいずれも本発明の技術
的範囲に包含される。
もので、この技術分野の当業者であれば、本発明の種々
の変形例を考え得るが、それらはいずれも本発明の技術
的範囲に包含される。
【００６１】
【発明の効果】以上述べたごとく、本発明によれば、ネ
ットワークの各ノードが、予め定義した条件が満たされ
た場合にのみ、隣接するノードにメッセージを送信する
ように、ネットワークの各ノードを構成しているので、
メッセージの送受信転送を効率よく行うことができる。 したがって、同報通信メッセージ送信の際、ノードは同
じメッセージを１回だけ受信し、何回も受信することが
ないので、メッセージがネットワークにあふれて他のメ
ッセージの送信が遅れるような不具合が解消される。
ットワークの各ノードが、予め定義した条件が満たされ
た場合にのみ、隣接するノードにメッセージを送信する
ように、ネットワークの各ノードを構成しているので、
メッセージの送受信転送を効率よく行うことができる。 したがって、同報通信メッセージ送信の際、ノードは同
じメッセージを１回だけ受信し、何回も受信することが
ないので、メッセージがネットワークにあふれて他のメ
ッセージの送信が遅れるような不具合が解消される。
【図１】本発明の通信ネットワークのブロック図である
。
。
【図２】本発明の通信ネットワークのブロック図である
。
。
【図３】図１及び図２のノードのようなネットワークノ
ード間に排他的最小スパニング樹情報を送信する本発明
の実施例用のメッセージフォーマットの説明図である。
ード間に排他的最小スパニング樹情報を送信する本発明
の実施例用のメッセージフォーマットの説明図である。
【図４】図３のメッセージに含まれる情報から得られた
排他的最小スパニング樹の説明図である。
排他的最小スパニング樹の説明図である。
【図５】本発明により図４のスパニング樹から得られた
経路選択表である。
経路選択表である。
【図６】本発明により図４のスパニング樹から得られた
経路選択表の別の例である。
経路選択表の別の例である。
【図７】本発明の実施例の通信ノードのブロック図であ
る。
る。
【図８】図１１に示すように、図９及び図１０と組み合
わせて、図７のノードに記憶されている、本発明実施用
のプログラムの流れ図を示す。
わせて、図７のノードに記憶されている、本発明実施用
のプログラムの流れ図を示す。
【図９】図１１に示すように、図８及び図１０と組み合
わせて、図７のノードに記憶されている、本発明実施用
のプログラムの流れ図を示す。
わせて、図７のノードに記憶されている、本発明実施用
のプログラムの流れ図を示す。
【図１０】図１１に示すように、図８及び図９と組み合
わせて、図７のノードに記憶されている、本発明実施用
のプログラムの流れ図を示す。
わせて、図７のノードに記憶されている、本発明実施用
のプログラムの流れ図を示す。
【図１１】図８、図９、及び図１０を組み合わせて、図
７のノードに記憶されている、本発明実施用のプログラ
ムの流れ図を示す際の、組合せの関係位置を示す。
７のノードに記憶されている、本発明実施用のプログラ
ムの流れ図を示す際の、組合せの関係位置を示す。
１，２，３，４，５，６，７，８，９ ノード（節点
）１００ 通信ネットワーク １０１，１０２，１０３，１０４，１０５，１０６，１
０７ リンク １０８，１０９ 通信リンク（パス）３０１，３０２
，３０３ 排他的最小スパニング樹メッセージ ４０１，４０２，４０３ 排他的最小スパニング樹５
０１，６０１ 経路選択表 ７００ ノード
）１００ 通信ネットワーク １０１，１０２，１０３，１０４，１０５，１０６，１
０７ リンク １０８，１０９ 通信リンク（パス）３０１，３０２
，３０３ 排他的最小スパニング樹メッセージ ４０１，４０２，４０３ 排他的最小スパニング樹５
０１，６０１ 経路選択表 ７００ ノード
Claims (6)
- 【請求項１】 それぞれのリンクを経て相互接続され
た複数のノードからなるネットワーク内で、前記複数の
ノードの内の第１ノードにおいて受信されたメッセージ
を前記複数のノードの内の少なくとも前記第１ノードに
隣接する第２ノードに送信するメッセージ送信設備にお
いて、前記メッセージが前記複数のノードの内の第３ノ
ードによって作られ、前記リンクの内の関連するリンク
を経て前記メッセージを受信する第１ノード内の受信手
段と、前記第１ノードと前記第３ノードとの間のリンク
の数が前記第２ノードと前記第３ノードとの間のリンク
の数より少なく、且つ前記第３ノードと前記第２ノード
の他の隣接ノードとの間のリンクの数より少ないときに
、前記メッセージを前記第２のノードに送信する第１ノ
ード内の送信手段とからなることを特徴とする、メッセ
ージ送信設備。 - 【請求項２】 前記送信手段が、前記第１のノードと
前記第３のノードとの間のリンクの数が前記第３のノー
ドと前記第２のノードの少なくとも１つの他の隣接ノー
ドとの間のリンクの数に等しいときに作動可能状態にあ
り、前記第１のノードに与えられた共通パラメータの値
が前記少なくとも１つの他の隣接ノードに与えられた共
通パラメータの値より少なければ、前記メッセージを前
記第２のノードに送信する手段を有することを特徴とす
る請求項１の設備。 - 【請求項３】 前記共通パラメータがアドレスである
ことを特徴とする請求項１の設備。 - 【請求項４】 前記複数のノードの各々が、それぞれ
の排他的最小スパニング樹を特徴付けるメッセージを相
互に交換する手段を有し、前記第１のノードが、前記複
数のノードの内の他のノードから受信したスパニング樹
メッセージを用いて前記リンクの数の各々を判定するこ
とを特徴とする請求項１の設備。 - 【請求項５】 前記交換する手段が、それぞれの経路
選択表を、前記複数のノードの内の他のノードから受信
したメッセージの内容の関数として作成し、前記複数の
ノードの各々が、それぞれの経路選択表を用いて、前記
複数のノードの内の他のノードが発信したメッセージの
受け入れ及び送信を制御することを特徴とする請求項４
の設備。 - 【請求項６】 それぞれのリンクを経て相互接続され
た複数のノードからなるネットワークにおける、メッセ
ージの経路選択の制御方法であって、前記メッセージが
前記複数のノードの内のメッセージ源ノードによって作
られ且つ前記複数のノードの内の少なくとも１つの他の
ノードにおいて受信され、前記少なくとも１つの他のノ
ードが少なくとも１つの隣接ノードを有するような、前
記ネットワークにおける前記メッセージの経路選択の制
御方法において、前記少なくとも１つの他のノードが、
自身と前記メッセージ源ノードとの間のリンクの数ｘと
、前記隣接ノードと前記メッセージ源ノードとの間のリ
ンクの数ｙとを判定できるように、前記少なくとも１つ
の他のノードを配置する過程と、前記少なくとも１つの
他のノードが、前記メッセージ源ノードと、前記隣接ノ
ードに隣接する他のノードのそれぞれとの間のリンクの
数ｚを判定できるように、前記少なくとも１つの他のノ
ードを配置する過程と、ｘの値がｙの値より小さく且つ
各ｚの値より小さい場合にのみ、前記少なくとも１つの
他のノードが前記隣接ノードに前記メッセージを送信す
るようにさせる過程と、からなることを特徴とするメッ
セージの経路選択の制御方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US488187 | 1990-03-05 | ||
| US07/488,187 US5245607A (en) | 1990-03-05 | 1990-03-05 | Data network message broadcast arrangement |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04219036A true JPH04219036A (ja) | 1992-08-10 |
| JP2513933B2 JP2513933B2 (ja) | 1996-07-10 |
Family
ID=23938683
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3061087A Expired - Lifetime JP2513933B2 (ja) | 1990-03-05 | 1991-03-04 | ネットワ―クにおけるメッセ―ジ送信設備及びその経路選択制御方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5245607A (ja) |
| EP (1) | EP0445468A3 (ja) |
| JP (1) | JP2513933B2 (ja) |
| CA (1) | CA2031303C (ja) |
Families Citing this family (20)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2875598B2 (ja) * | 1990-06-27 | 1999-03-31 | 富士通株式会社 | ノードにおけるネットワーク経路設定方式 |
| US6400702B1 (en) * | 1991-10-01 | 2002-06-04 | Intermec Ip Corp. | Radio frequency local area network |
| JPH05167585A (ja) * | 1991-12-16 | 1993-07-02 | Nec Corp | ローカルエリアネットワーク同報フレーム通信装置及び方法 |
| US5563881A (en) * | 1993-08-06 | 1996-10-08 | Rolm Company | Multihop distribution lists |
| US5920822A (en) * | 1996-01-18 | 1999-07-06 | Telefonaktiebolaget Lm Ericsson (Publ) | Formatting of short message service messages in a cellular telephone network |
| US5850396A (en) * | 1996-06-24 | 1998-12-15 | Gateway 2000, Inc. | Multicast message distribution in a polynomial expansion manner |
| US5903562A (en) * | 1996-12-13 | 1999-05-11 | Hewlett-Packard Company | Multicasting employing publication title to create numeric destination address for computer network system frame |
| US6130877A (en) * | 1997-05-23 | 2000-10-10 | Nortel Networks Corporation | Rate controlled broadcast for activation of entities in large scale data networks |
| EP0913965A1 (en) * | 1997-11-03 | 1999-05-06 | Canon Kabushiki Kaisha | Reduction of the message traffic in a distributed network |
| EP0935368A1 (en) | 1997-11-03 | 1999-08-11 | Canon Kabushiki Kaisha | Path detection in a distributed network |
| US6480502B1 (en) * | 1998-05-15 | 2002-11-12 | Compaq Information Technologies Group, L.P. | Method for avoiding broadcast deadlocks in a mesh-connected network |
| US6487172B1 (en) * | 1998-08-21 | 2002-11-26 | Nortel Networks Limited | Packet network route selection method and apparatus using a bidding algorithm |
| US6304552B1 (en) * | 1998-09-11 | 2001-10-16 | Nortel Networks Limited | Memory and apparatus for input based control of discards in a lossy packet network |
| US6721314B1 (en) * | 1999-05-20 | 2004-04-13 | Lucent Technologies Inc. | Method and apparatus for applying once-only processing in a data network |
| EP1107508A1 (en) * | 1999-12-06 | 2001-06-13 | Telefonaktiebolaget Lm Ericsson | System, method and computer program product for sending broadcast messages |
| FR2804811B1 (fr) * | 2000-02-07 | 2002-05-10 | Rene Duranton | Procede et dispositif pour l'attribution automatique d'adresses a une pluralite de modules interconnectes par reseau de communication a topologie complexe |
| US7386621B1 (en) | 2000-08-31 | 2008-06-10 | Sharp Laboratories Of America, Inc. | Efficient and reliable transmission via a hybrid broadcast-point-to-point system |
| US20030088620A1 (en) * | 2001-11-05 | 2003-05-08 | Microsoft Corporation | Scaleable message dissemination system and method |
| US9191236B2 (en) | 2010-05-20 | 2015-11-17 | International Business Machines Corporation | Message broadcasting in a clustered computing environment |
| CN114845349B (zh) * | 2022-03-30 | 2025-05-30 | 西安宇飞电子技术有限公司 | 一种无线网格网络自组网的通信方法及系统 |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6423647A (en) * | 1987-07-20 | 1989-01-26 | Fujitsu Ltd | Autonomous distributed communication system |
| JPH01162452A (ja) * | 1987-12-18 | 1989-06-26 | Fujitsu Ltd | 自律形ルーチング方式 |
| JPH01238247A (ja) * | 1988-03-18 | 1989-09-22 | Nippon Telegr & Teleph Corp <Ntt> | 同報通信ルート決定処理方法 |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4251861A (en) * | 1978-10-27 | 1981-02-17 | Mago Gyula A | Cellular network of processors |
| US4412285A (en) * | 1981-04-01 | 1983-10-25 | Teradata Corporation | Multiprocessor intercommunication system and method |
| US4466060A (en) * | 1982-02-11 | 1984-08-14 | At&T Bell Telephone Laboratories, Incorporated | Message routing in a computer network |
| US4740954A (en) * | 1986-12-31 | 1988-04-26 | Bell Communications Research, Inc. | Multicast routing algorithm |
| US5101348A (en) * | 1988-06-23 | 1992-03-31 | International Business Machines Corporation | Method of reducing the amount of information included in topology database update messages in a data communications network |
-
1990
- 1990-03-05 US US07/488,187 patent/US5245607A/en not_active Expired - Lifetime
- 1990-11-30 CA CA002031303A patent/CA2031303C/en not_active Expired - Lifetime
- 1990-12-11 EP EP90313459A patent/EP0445468A3/en not_active Ceased
-
1991
- 1991-03-04 JP JP3061087A patent/JP2513933B2/ja not_active Expired - Lifetime
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6423647A (en) * | 1987-07-20 | 1989-01-26 | Fujitsu Ltd | Autonomous distributed communication system |
| JPH01162452A (ja) * | 1987-12-18 | 1989-06-26 | Fujitsu Ltd | 自律形ルーチング方式 |
| JPH01238247A (ja) * | 1988-03-18 | 1989-09-22 | Nippon Telegr & Teleph Corp <Ntt> | 同報通信ルート決定処理方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP2513933B2 (ja) | 1996-07-10 |
| US5245607A (en) | 1993-09-14 |
| CA2031303C (en) | 1996-06-25 |
| CA2031303A1 (en) | 1991-09-06 |
| EP0445468A3 (en) | 1995-01-04 |
| EP0445468A2 (en) | 1991-09-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP2513933B2 (ja) | ネットワ―クにおけるメッセ―ジ送信設備及びその経路選択制御方法 | |
| US6639897B1 (en) | Communication network of linked nodes for selecting the shortest available route | |
| US7171476B2 (en) | Protocol and structure for self-organizing network | |
| US5398012A (en) | Distributed processing of route selection across networks and subnetworks | |
| US7096251B2 (en) | Calculation of layered routes in a distributed manner | |
| JPH11510348A (ja) | 通信網におけるルート探し | |
| EP0720332A2 (en) | Bidirectional mesh network | |
| JPH10126439A (ja) | パケット交換通信網のルート選択装置 | |
| JPS62502303A (ja) | パケット通信網の相互接続方法 | |
| JPH11511618A (ja) | 電気通信ネットワークにおける最適復旧ルートの決定論的選択 | |
| Tode et al. | Multicast routing algorithm for nodal load balancing | |
| CN113810274B (zh) | 一种路由处理方法及相关设备 | |
| US5717687A (en) | Data communication system with adaptive routing, and switching node intended to be used in such a system | |
| EP1185041B1 (en) | OSPF autonomous system with a backbone divided into two sub-areas | |
| US7336614B2 (en) | Method and device for controlling route and computer program therefor | |
| CN101815040A (zh) | 在混合交换机网络中转发分组的方法和交换机 | |
| US5289467A (en) | Manhattan street network with loop architecture | |
| KR19990036307A (ko) | 노드 통신망의 추가 루트 결정 방법 및 사용 노드 | |
| CN110391981B (zh) | 为网状网络中的网关节点建立源路由树的设备、方法及介质 | |
| Feamster et al. | Network-wide BGP route prediction for traffic engineering | |
| CN110912823B (zh) | 一种面向异构有线无线融合网络的SDN与IPv6可靠路由方法 | |
| JP2019121923A (ja) | 優先方路決定方法および優先方路決定装置 | |
| Seeger et al. | Reducing routing overhead in a growing DDN | |
| CN108496391B (zh) | 无线网格通信网络的路由 | |
| CN113556796A (zh) | 配置路由域标识的方法及设备 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080430 Year of fee payment: 12 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090430 Year of fee payment: 13 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100430 Year of fee payment: 14 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100430 Year of fee payment: 14 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110430 Year of fee payment: 15 |
|
| EXPY | Cancellation because of completion of term |