JPS63173437A

JPS63173437A - 同報通信方式

Info

Publication number: JPS63173437A
Application number: JP62003996A
Authority: JP
Inventors: Kazutoshi Maeno; 前野　和俊
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 1987-01-13
Filing date: 1987-01-13
Publication date: 1988-07-18

Abstract

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

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明は、同報通信方式に関し、特に複数のノードがリ
ンクで接続されているバケットネットワークにおける同
報通信方式に関する。

〔従来の技術〕

従来、複数のノードがリンクで互いに接続されている情
報ネットワークにおける同報通信方式では、ネットワー
クの形状にかかわらずエンドノード・エンドノード間で
信頼性高い通信を行うために、送信元ノードは送信メツ
セージに対する応答をすべての宛先ノードから収集し、
少なくとも１つの応答が受信不成功であったら、その応
答を送出したノードが受信成功するまで繰り返し同一メ
ッセージを送出し、受信不成功のノードが受信成功し、
すべての応答が受信成功応答を返したら送出メツセージ
がすべての宛先ノードで正しく受信されたことを知り、
使用バッファの解放等を行い、次のメツセージを送信し
ていた。これはいわゆる０Ｓ１７層モデルのネットワー
ク層における送達確認を１対多で行う方式である。この
技術については国際標準化機構（ＩＳＯ）の「ワーキン
グドラフト　アデンダム　トウ　Ｉ　Ｓ　０　７４９８
　　オン　マルチピアデータ　トランスミッション（Ｗ
ｏｒｋｉｎｇ　Ｄｒａｆｔ　Ａｄｄｅｎｄｕｍ　ｔｏ　
ＩＳＯ７４９８ｏｎ　Ｍｕｌｔｉ−ｐｅａｒ　Ｄａｔａ
　Ｔｒａｎｓｍｉｓｓｉｏｎ）（１９８６年１月）」で
その概念が紹介されている。ここでメツセージとは１つ
ノハケットや、複数のまとまりを持ったパケットの集合
であるが、ここでは特に規定しない。

図を用いて従来の技術を以下に説明する。第４図（ａｌ
は情報ネットワークの一例を示している。図でＡ、Ｂ、
Ｃ，Ｄ、Ｅ、Ｆ、Ｇはそれぞれノードを示しており、ノ
ードはリンクでそれぞれ接続されている。いまノードｉ
、ｊを接続するノードを（ｉ、ｊ）で表わすことにする
。各リンクにはコストが定義されており、送信元ノード
が決まるとそのノードをルートとし、ネットワークに属
する全てのノードを接続する木（ｔｒｅｅ）が定まる。

これをここでは通信木と呼ぶことにする。第４図（ｂ）
に、第４図（ａｌのネットワークでノードＡを送信元ノ
ードとしたときの通信木の一例を示す。第４図（ｂ）で
、例えばノードＢの隣接上流ノードとはノードＡを示し
、隣接下流ノードとはノードｃ、Ｇをそれぞれ示す。第
４図（ｂ）で、ノードＡは隣接上流ノードを持たない。

このようなノードを通信木のルート（根）と呼ぶ。一方
、ノードＣ，Ｅ、　　Ｆ。

Ｇは隣接下流ノードを持たない。このようなノードをリ
ーフ（葉）と呼ぶ。また通信木はその部分木を持ち、例
えばノードＢ、Ｃ，Ｇを接続する木は、前述の通信木の
部分木であり、ノードＢはこの部分木のルートと呼ばれ
る。図でＡからの同報メツセージは（Ａ、　Ｂ）と（Ａ
、　Ｄ）に分岐されてノードＢ、Ｄに送信され、さらに
ノードＢにおいては（Ｂ、Ｃ）、（Ｂ、Ｇ）にメツセー
ジは分岐されてノードＣ，Ｇに送信される。またノード
Ｄにおいては（Ｄ、　　Ｆ）、（Ｄ、　Ｅ）にメツセー
ジは分岐されてノードＦ、Ｈに送信される。各ノードか
らのメツセージに対するエンド・エンドの応答は前述の
通信木に沿ってメツセージとは逆方向にノードＡに送ら
れる。このときの制御構造を第５図に示す。

このように、従来の同報通信方式は、応答の収集機能も
１つの送信元ノード、上述した例ではノードＡが持ち、
その送信元ノードですべての宛先ノードからの応答を収
集しており、もし、受信不成功のノードが１つでもあっ
たならば、受信に成功するまで繰り返し同一メツセージ
を送出していた。

〔発明が解決しようとする問題点〕

しかし、このような応答の収集、管理を行う同報通信方
式にあっては、信頼性の高い通信を行える反面、次のよ
うな欠点がある。

すなわち、上述した従来の同報通信方式では、送出メツ
セージに対する応答をすべてのノードがら受信してから
次のメツセージを送信しており、例えば第５図に一例を
示したように、ノードＡを送信元とするときはこの送信
元ノードＡですべての宛先ノードＢ、Ｃ，Ｄ、Ｅ、Ｆ、
Ｇからの応答を収集する方式を採るから、ある１つのノ
ードが受信不成功であったら、その応答を送出したノー
ド、すなわち受信不成功のノードが受信成功するまで繰
り返し同一メツセージを送出するため、受信に成功した
ノードにおいてはその間待たされることになり、とくに
ノード数が増加すると待ち時間は増大してしまい、その
ため全体としてのメツセージ送信終了時間は著しく劣化
してしまう。また１つのノードですべての応答を管理す
るので負荷も非常に高くなってしまうという問題点があ
った。

本発明の目的は、応答の収集機能を、同報通信を行う通
信水の１以上の分岐ノードに分散させ、その分岐ノード
においては通信木上で自ノードの下流ノードのすべてか
ら受信したら次のメツセージを送出することを特徴とす
る同報通信方式を提供することにある。

〔問題点を解決するための手段〕

本発明の同報通信方式は、複数のノードがリンクで接続
されている情報ネットワークで送信すべきすべてのノー
ドにメツセージを送信する同報通信方式において、同報通信する場合、光送信を行うノードでは送信元ノー
ドをルートとするすべてのノードにメツセージを送信す
るための通信木上の上流ノードから同報メツセージを受
信すると、その受信回報メッセージに誤りがあれば、前
記上流ノードへ受信不成功であることを示す応答を送信
して同報メッセージの再送を要求し、受信メツセージに
誤りがなければ、前記上流ノードへ受信成功であること
を示す応答を送信し、回報メソ妄−ジを受信すると共に
、通信木上の１以上の下流ノードへその同報メツセージ
を送信し、前記下流ノードからの応答を待ち、受信した
応答のなかで受信不成功を示すものがあるときにはその
応答を送出したノードに前記メツセージを再送し、その
ノードから受信成功の応答を受信することで前記下流ノ
ードすべてから同報メツセージに対する受信成功の応答
を受信したら、この同報メツセージに対する処理を終了
することを特徴としている。

〔作用〕

本発明による同報通信方式によればメツセージのネット
ワーク層での送達確認の機能を同報通信水上の分岐ノー
ドに分散させる。送信元ノードは通信木上の下流ノード
にメッセージを同和し、そのノード間だけでエンドノー
ド・エンドノードのネットワーク層の送達確認を行う。

メツセージを受信したノードはさらに自ノードの下流ノ
ードにメツセージを同報し、そのノード間だけでネット
ワーク層の送達確認を行い、以下同様にして順次下流ノ
ードに回報を行う。このように各ノードは通信木上で、
自ノードの下流ノードに対してメツセージの送信とその
ネットワーク層の送達確認を行って同報を行うため、あ
るノードからの応答が受信不成功であっても、従来のよ
うにすべてのノードが待たされることなく、その影響は
受信不成功なノードをルートとする部分木に属するノー
ドに限定され、効率のよい同報通信を行うことができ、
しかも、従来のように１つのノードにだけ負荷がかかる
ということもない。

〔実施例〕

次に、本発明について図面を参照して説明する。

第１図は本発明の同報通信方式に従う各ノードでの制御
アルゴリズムを示すフローチャートである。図に示すフ
ローチャートでは１００〜１１５の１６個の制御ブロッ
クより構成される。第１図（ａ）は通信水のルートおよ
びリーフノードを除く全てのノードでのアルゴリズムを
示し、（ｂｌはルートノードでのアルゴリズムを、（Ｃ
１はり−フノードでのアルゴリズムをそれぞれ示す。以
下に、第４図（ａ）に示したネットワークを例にして第
１図に示した同報通信アルゴリズムを実施した様子を説
明する。

前述と同様、第４図（ａ）で送信元ノードをＡとし、ノ
ードＡからノードＢ、Ｃ，Ｄ、Ｅ、Ｆ、Ｇにメツセージ
を同報する例を採ることとする。また、この場合のノー
ドＡをルートとする通信水を第４図（ｂ）に、更に、こ
のときの、本発明に従う同報通信方式による基本的な制
御構造を第２図に示す。

制御構成は前記通信水より得られ、ルートとなるノード
ＡではメツセージはノードＢ、Ｄに分岐される。さらに
ノードＢではメツセージはノードＣ２Ｇに分岐され、ノ
ードＤではメツセージはノードＦ、Ｅに分岐される。零
ノード同報通信方式では、ノードＡは隣接下流ノードで
あるノードＢ、Ｄにメツセージを信頬性高く同報する。

すなわちノードＢ、ノードＤにメッセージを送信しく第
１図（１））の制御ブロック１０８）、ノードＢ、ノー
ドＤはこのメツセージを正しく受信したら受信成功を示
す応答（以後ＡＣＫ応答と呼ぶ）をノードＡに返しく第
１図（ａ）の制御ブロック１００　、１０１　、１０３
　）、そのメッセージを正しく受信できなかったら受信
不成功であることを示す応答（以後ＮＡＣＫ応答と呼ぶ
）をノードＡに返す（第１図（ａｌの制御ブロック１０
２）。ノードＡはＮＡＣＫ応答を受信したら、このＮＡ
ＣＫ応答を送信したノードにメツセージを再送しく第１
図（ｂｌの制御ブロック１ｏ９゜１１０　、１１１　）
　、そのノードからＡＣＫ応答を受信するまで再送を繰
り返す。このようにして、ノードＡは通信木上の隣接下
流ノードであるノードＢ１ＤからのＡＣＫ応答がすべて
揃ったらその送信メッセージを格納する等に使用してい
たバッファを解放して次のメツセージを同報する。一方
、ノードＢではノードＡからメツセージを正しく受信す
るとノードＡにＡＣＫ応答を返しく第１図（ａ）の制御
ブロック１０３　）　、同時にこのメツセージをノード
ＡがノードＢ、Ｄに同報したのと同様にして、ノードＣ
，Ｇの同報する（第１図ｔａ）の制御ブロック１０４　
、１０５　、１０６　、１０７　）。また同様にして、
ノードＤもノードＥ、Ｆにメツセージを同報する。

その間ノードＢ、Ｄでは同時にノードＡからの次のメッ
セージの受信処理を行う（第１図（ａｌの制御ブロック
１００　、１０１　、１０２　、１０３　”）。通信水
のリーフであるノードＣ，Ｇ、Ｆ、Ｅではそれぞれ通信
木上の隣接上流ノードであるノードＢ、Ｄからのメツセ
ージを正しく受信したらＡＣＫ応答を返しく第１図（Ｃ
）の制御ブロック１１２　、１１３　、１１５　）、正
しく受信できなかったらＮＡＣＫ応答を返す（第１図（
Ｃ）の制御ブロック１１４）。

このように、複数のノードがリンクで互いに接続されて
いる情報ネットワークですべてのノードにメツセージを
送信する同報通信方式において、各ノードでは送信元ノ
ードをルートとする全てのノードにメツセージを送信す
るための通信木上の隣接上流ノードから同報メツセージ
を受信すると、この受信同報メツセージに誤りがあれば
、隣接上流ノードへ受信不成功であることを示す応答を
送信して同報メッセージの再送を要求し、受信メッセー
ジに誤りがなければ、隣接上流ノードへ受信成功である
ことを示す応答を送信し、同報メツセージを受信すると
共に、通信木上の複数の隣接下流ノードへ前述の同報メ
ッセージを送信し、隣接下流ノードからの応答を待ち、
受信した応答のなかで受信不成功を示すものがあるとき
にはその応答を送出したノードにメッセージを再送し、
このノードから受信成功の応答を受信することで隣接下
流ノードすべてから前述の同報メツセージに対する受信
成功の応答を受信したら、同報メツセージに対する処理
を終了する。

更に、第３図を用いて上述の例における同報通信方式に
よるノード間の信号送受の具体的−例を説明する。図で
ＭＳＧはメッセージを示し、添付の数字はメツセージの
シーケンス番号を表している。例えばＭＳＧＩはシーケ
ンス番号１のメツセージを示し、さらにＡＣＫＩ、ＮＡ
ＣＫｌ、再送１はそれぞれＭＳｏｌに対するＡＣＫ応答
、　ＮＡＣＫ応答、再送メツセージを示す。図では時間
軸４００を用いるが、説明のためメツセージ等の送受は
時刻ｔＨ（ｉ＝Ｑ〜１０）のタイミングで行われ送信遅
延は考えないものとする。まずノードＡは時刻ｔ０でノ
ードＢ、ＤにＭＳＧｌを送信する。

時刻ｔＩ＋Ｌ！ではノードＢはノードＡにＡＣＫ１応答
を返し、ＭＳＣＩを自ノードで受信するとともに、ＭＳ
ＧＩをノードＣ１Ｇに送信する。またノードＤにおいて
も、同様の処理が行われ、ＭＳＣＩを自ノードで受信す
るとともにＭＳＣＩをノードＥ、Ｆに送信する。

このように、各ノードＢ、Ｄでは、隣接上流ノードＡか
ら同報メツセージを受信すると、受信メツセージに誤り
がなければ、隣接上流ノードＡへ受信成功であることを
示す応答を送信し、同報メツセージを受信すると共に、
隣接下流ノードＣ２Ｇ、Ｅ、Ｆへ同報メツセージを送信
する。

ノードＡでは時刻ｔ１で隣接下流ノードであるノードＢ
、ＤよりＭＳＣＩに対するＡＣＫ　１応答を受信したの
で、時刻ｔ２で次のメツセージＭＳＧ２をノードＢ、Ｄ
に送信する。時刻ｔ３では、ノードＢはノードＣよりＡ
ＣＫ　１応答を受信するとともに、ノードＡにＡＣＫ２
ＣＫ２応答。ノードＤでも同様にして、ノードＦよりＡ
ＣＫ　１応答を受信するとともに、ノードＡにＡＣＫ２
ＣＫ２返す。

このようにして、従来の如く１つの送信元ノードですべ
ての宛先ノードからの応答を収集するのではなく、応答
の収集機能を複数の分岐ノードＢ。

Ｄに分散させる。

時刻ｔ４ではノードＡはノードＢ、Ｄに更に次のＭＳＣ
３を送信する。ノードＢではノードＧよりＡＣＫ　１応
答を受信し、ノードＤはノードＥよりＮＡＣＫＩ応答を
受信する。時刻ｔ、ではノードＡはノードＢよりＡＣＫ
３応答を受信し、ノードＤよりＮＡＣＫ３応答を受信す
る。

このように、ノードＤは、隣接上流ノードＡからの同報
メツセージの受信時、受信同報メツセージに誤りがあれ
ば、隣接上流ノードＡへ受信不成功であることを示す応
答を送信して（時刻ｔｓ）回報メッセージの再送を要求
することになる。

この点については、ノードＢ、Ｄ以下の部分においても
同様であり、この第３図の具体例では、上述の如く、ノ
ードＤに対して、時刻ｔ４において、ノードＥからメツ
セージ再送を要求するため受信不成功であることを示す
応答が送信されてきている。

また、ここで、メツセージの送達確認の機能を分担する
ノードＢの側を見ると、ノードＢではＭＳＧｌに対する
ＡＣＫ　１応答をノードＣ，Ｃより受信したので（時刻
ｔ３＋　　ｔ４）ノードＡより受信した次のメツセージ
ＭＳＧ２をノードＣに送信する。

このように、かかる機能を分担したノードＢにおいては
通信水上で自ノードの隣接下流ノードのすべて、この場
合はノードＣ１Ｇから同報メッセージに対する受信成功
応答を受信したら、その同報メッセージに対する処理は
終了し、次の処理に移行するのであり、次のメツセージ
のノードＣへの送信（時刻ｔ、）、ノードＧへの送信を
行う（時刻ｔ、）。

一方、ノードＤの側においては、ノードＢ側で上述のよ
うな処理が進められていくのに対し、前述の如く、時刻
ｔ４で受信不成功の応答が送信されてきているので、時
刻ｔ、の時点ではノードＢ側と同様の処理にはまだ移行
せず、これが行われるのは時刻ｔ、以後である。

すなわち、時刻り、おいて、一方、ノードＤではノード
ＥにＭＳＣＩを再送する。時刻ｔ、では時刻ノードＡは
ノードＤにＭＳＣ３を再送する。

ノードＣはノードＧにＭＳＣ２を送信する。ノードＤは
ノードＥよりＡＣＫ　１応答を受信する。時刻ｔ、では
ノードＡはノードＤよりＡＣＫ３応答を受信し、ノード
ＢはノードＣよりＮＡＣＫ２応答を受信する。またノー
ドＤではＭＳＣ；１に対するＡＣＫ　１応答をノードＥ
、Ｆより受信したので、ここで、ノードＡより受信した
次のメッセージＭＳＧ２をノードＦに送信する。

このように、ノードＤは、前述のように隣接下流ノード
Ｅ、Ｆへ同報メツセージを送Ｉ言したならば（時刻ｔｌ
ｌ　　ｔ２）、その隣接下流ノードＥ。

Ｆからの応答を待ち、受信した応答のなかで受信不成功
を示すものがあるときにはその応答を出したノードにメ
ツセージを再送し、そのノードから受信成功の応答を受
信することにより隣接下流ノードＥ、Ｆすべてから同報
メツセージに対する受信成功の応答を受信したら、この
同報メッセージに対する処理を終了するのである。そし
て、前述したノードＢ側と同様、次のメツセージに対す
る処理に移行することになる。

時刻ｔ、では、ノードＡはノードＢ、Ｄに更に次のＭＳ
Ｃ４を送信し、ノードＢはノードＧよりＡＣＫ２応答を
受信し、ノードＤはノードＥにＭＳＣ２を送信する。時
刻ｔ、ではノードＡはノードＢ、ＤよりＡＣＫ４応答を
受信し、ノードＢはノードＣにＭＳＣ２を再送する。ま
たノードＤはノードＦよりＡＣＫ２応答を受信する。時
刻ｔ１゜ではノードＡはノードＢ、Ｄに更に次のＭＳＣ
５を送信し、ノードＢはノードＣよりＡＣＫ２応答を受
信し、ノードＤはノードＥよりＡＣＫ２応答を受信する
。

このようにして、回報通信を行う。ここで、第４図に示
したネットワークの例で、従来と比較すると、前述した如〈従来の同報通信方式では、ノードＡは通信
木に従ってメツセージを同報し、同報メッセージに対す
る応答をすべての宛先ノードＢ。

Ｃ，Ｄ、　Ｅ、　　Ｆ、　Ｇから受信してから次のメツ
セージを送信していた。このように送信元ノードですべ
ての宛先ノードからの応答を収集する従来の同報通信方
式では、ある１つのノードが受信不成功であったら、そ
の応答を送出したノードが受信成功するまで繰り返し同
一メツセージを送出するため、受信に成功したノードに
おいてはその間待たされていた。とくにノード数が増加
するとｅ指数的に待ち時間は増大してしまい、そのため
全体としてのメツセージ送信終了時間は著しく劣化して
しまい、また１つのノードですべての応答を管理するの
で負荷も非常に多くなっていた。

これに対し、この同報通信方式によればメツセージの送
達確認の機能を同報通信水上の各分岐ノードＢ、Ｄに分
散させ、送信元ノードＡは通信木上の隣接下流ノードＢ
、Ｄにメツセージを回報し、この隣接ノード間だけでエ
ンドノード・エンドノードのネットワーク層の送達確認
を行う。メツセージを受信したノードＢ、Ｄはさらに自
ノードの隣接下流ノードＣ，Ｇ、　　Ｅ、　　Ｆにメツ
セージを回報し、この隣接ノード間だけでネットワーク
層の送達確認を行い、更に、ノードＣ，Ｇ、Ｅ、Ｆに下
流ノードがあれば、以下同様にして順次隣接下流ノード
に回報を行う。

このように、各ノードは通信木上で自ノードの隣接下流
ノードに対してメツセージの送信とその送達確認を行っ
て同報を行うことができ、あるノードからの応答が受信
不成功であっても、すべてのノードが待たされるという
ことはなく、また、通信木の各分岐ノードにメツセージ
の送達確認の機能を分散させることができる。

〔発明の効果〕

以上説明したように、本発明によれば、受信、送信を行
う各ノードは通信木上で、自ノードの下流ノードに対し
てメツセージの送信とその送達確認を行って同報を行う
ため、あるノードからの応答が受信不成功であっても、
従来のようにすべてのノードが待たされることなく、そ
の影響はその受信不成功なノードをルートとする部分木
に属するノードに限定され、効率のよい同報通信を行う
ことができる。また通信木の分岐ノードにメツセージの
送達確認の機能を分散させるため、従来のように１つの
ノードに大きく負荷がかかることもない。

【図面の簡単な説明】

第１図＋ａ）、（ｂ）並びにｆｃ）はそれぞれ本発明の
一実施例の同軸通信方式のルート及びリーフノードを除
く任意のノードでの制御アルゴリズムを示すフローチャ
ート、ルートノードでの制御アルゴリズムを示すフロー
チャート並びにリーフノードでの制御アルゴリズムを示
すフローチャート、第２図は本発明の同報通信方式にお
ける制御構造の一例を示す図、第３図は本発明の同報通信方式によるノード間の信号送
受の具体的−例を示す図、第４図（ａ）及び（ｂｌはそれぞれ情報ネットワークの
一例及び通信木の一例を説明するための図、第５図は従
来の同報通信方式における制御構造を表わす図である。１００〜１１５・・・制御ブロック４００・・・時間軸Ａ〜Ｆ・・・ノード代理人弁理士　　　岩　　佐　　義　　幸第１図（ａ）第１図（ｂ）第４図第５図

Claims

【特許請求の範囲】

（１）複数のノードがリンクで接続されている情報ネッ
トワークで送信すべきすべてのノードにメッセージを送
信する同報通信方式において、同報通信する場合、受送
信を行うノードでは送信元ノードをルートとするすべて
のノードにメッセージを送信するための通信木上の上流
ノードから同報メッセージを受信すると、その受信同報
メッセージに誤りがあれば、前記上流ノードへ受信不成
功であることを示す応答を送信して同報メッセージの再
送を要求し、受信メッセージに誤りがなければ、前記上
流ノードへ受信成功であることを示す応答を送信し、同
報メッセージを受信すると共に、通信木上の１以上の下
流ノードへその同報メッセージを送信し、前記下流ノー
ドからの応答を待ち、受信した応答のなかで受信不成功
を示すものがあるときにはその応答を送出したノードに
前記メッセージを再送し、そのノードから受信成功の応
答を受信することで前記下流ノードすべてから同報メッ
セージに対する受信成功の応答を受信したら、この同報
メッセージに対する処理を終了することを特徴とする同
報通信方式。
（２）特許請求の範囲第１項に記載の同報通信方式にお
いて、複数のノードは互いに接続されており、受送信を行う各
ノードは隣接上流ノードから同報メッセージを受信し、
複数の隣接下流ノードへ前記同報メッセージを送信する
ことを特徴とする同報通信方式。