JPH0241054A - 通信ネツトワークにおいて最小重みのルートを選択する方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明はデータ通信ネットワーク特に、そのようなネッ
トワークを経由するルートの計算中に、等しい重みを有
する複数の最小重み経路から経路を選択する方法に関す
る。

Ｂ、従来技術 下記の説明のために１通信ネットワークとは、通信リン
クを経由して相互接続されたネットワーり・ノード及び
端末ノードの集まりとして定義される。ネットワーク・
ノードは、ネットワーク内である種の機能を提供するデ
ータ処理システムとして特徴付けられる。そのような機
能は例えば、ネットワーク・ノード自身及びその隣接及
び近傍のノードの間でメツセージのルーディングを行う
こと、２つのノードの間で伝送されるメツセージのルー
トの選択を行うこと、並びに接続された末端ノードにデ
ィレクトリ・サービスを提供することである。ノード間
のリンクは、通常のケーブル接続等の恒久的な通信リン
クでも又、ダイヤル式電話接続等の必要な時にだけ使用
可能なリンクでもよい。端末ノードは、ネットワーク中
の他のノードに対してルーディング又はルート選択又は
ディレクトリ・サービスを提供しない、例えば表示端末
、インテリジェント・ワークステーション、プリンタ等
の装置である。ネットワーク・ノード。

端末ノード、及びノード間のリンクは、集合的に、ネッ
トワーク資源と呼ばれる。ネットワーク中の種々のノー
ド及びリンクの特性並びに物理的配置はネットワークの
トポロジー呼ばれる。

１つのノードのユーザーが他のノードの他のユーザーと
データを交換するためには、ネットワークを経由する経
路又はルートが用意されなければならない。ルートは、
第１のユーザーが位置するノード（起点ノード）、第２
のユーザーが位置するノード（宛先ノード）、おそらく
１つ以上のネットワーク・ノード及びルート上のノード
を接続するリンク又は伝送グループを含む。伝送グルー
プは、グループ中の個々のリンクの各々よりも高い能力
を有する単一の論理的リンクを形成する、同様の特性を
有する１組の並列リンクとして通常定義される。しかし
ここでは、伝送グループという用語は単一の物理的リン
クも意味するものとすべきである。これらの用語は下記
の説明中で同義的に使用される。

理想的なネットワークにおいて、第１のユーザーにより
提供されるデータは、２人のユーザーの間のルート中に
どの位多くのノード及び伝送グループが含まれているか
に無関係に、コストなし、ゼロ遅延、完全な信頼性及び
完全な安全性で第２のユーザーに伝送される。不幸な事
に、現実のデータ通信ネットワークはそれらの理想的な
特性を欠いている。異なったルートを用いると、異なっ
た大きさの遅延が導入される。また、ある型の伝送グル
ープは、他よりもコストが高いか又はより大きな遅延を
導入する。伝送されるデータの保全性はある伝送グルー
プ上では他よりも良く保護される。また上記では説明さ
えしなかった他の不完全性が現実のネットワークには存
在する。

現実のネットワーク中のノード及び伝送グループは異な
った特性を有するので、ノード及び伝送グループの両者
に重みを割り当て、その割り当てられた重みを用いて、
１人のユーザーから他のユーザーへのネットワークを経
由する最適又は最小重みのルートを計算することが通常
行われている。

重みは一般に、所定のノード又は伝送グループが、事前
に定められた性能基準をどの程度満足するかを反映して
いる１例えば、重みが遅延特性だけに基づいて割り当て
られるならば、遅延の大きな伝送グループは、遅延の小
さな伝送グループよりも大きな重みが割り当てられる。

あるノードの第１のユーザーから他のノードの第２ユー
ザーへネットワークを経由する「最良」のルートを決定
するために、種々の可能なルート中のノード及び伝送グ
ループの重みが合計される。

重みの総和が最小のルート（これは最小重みのルートと
呼ばれる）がユーザー間の「最良の」ルートと考えられ
る。

起点ノード、宛先ノード、及び特定のクラスのサービス
が与えられると、最小重みルート計算アルゴリズムは、
常に起点ノードから宛先ノードへの単一の最小重みの経
路を計算する。もしネットワークのトポロジーが安定（
即ちネットワークのノード及び中間のルーティング伝送
グループの特性が変化しない）場合、与えられた起点ノ
ード。

宛先ノード及びサービスのクラスに関して繰り返し同じ
経路が計算される。もし起点ノードと宛先ノードとの間
の経路が実際に唯一の最小重みの経路であれば、ルート
計算アルゴリズムにより常にその経路が選択されること
に何の問題もない。

Ｃ０発明が解決しようとする課題 しかし、与えられたクラスのサービスに関して。

起点ノードと宛先ノードとの間に同じ最小重みの複数の
経路が存在する可能性がある。もしルートの計算中に複
数の経路の間の互角性が常に同じ方式で破られるならば
、そのアルゴリズムはルート要求毎に常に同じ経路を選
択するであろう、従って、複数の等しい重みの経路のう
ち１つが、他の最小重み経路を排除して過負荷になる可
能性がある。その結果、他の経路は、正当化できない理
由により、完全には利用されないであろう。

ネットワーク経路の利用をより均一化する１つの方法は
、与えられた経路上の混雑を検出し、トポロジー・デー
タベースに記憶されているノード及び伝送グループの特
性に混雑情報を含ませることである。この方式の欠点は
、混雑情報は、不所望の混雑が既に起きた後でしか得ら
れないことである。

００課題を解決するための手段 本発明は、ルート計算中に、等しい重みの１組のルート
から、より効果的に異なったルートを選択するための改
良された方式に関する。

この方式は１選ばれた始祖ノードを用いてルート計算木
を開始するステップを含む、ネットワーク・ノードと（
まだ木の中に存在しないネットワーク・ノードを木の中
のノードに接続する）伝送グループとの対の集合が確立
される。木の中の始祖ノードから集合の中の各ノードま
での経路の重みが計算される。始祖ノードから最小重み
の経路を有するノードが次のように木に付加される。始
祖ノードから所定のノードへ最小重みを有する１つだけ
の経路しか存在しない場合、その経路が選択される。も
し始祖ノードから所定のノードへ複数の経路が等しい最
小重みを有するならば、それらの複数の経路の１つが、
擬似ランダム操作で選択される。選択されたノード及び
それを木に接続する伝送グループが木に転送される。転
送されたノードに関する。集合中の他のノード−伝送グ
ループ対が集合から除去される。上記にアウトラインを
示したステップは１選択された始祖ノードを用いて木を
開始する初期ステップを除いて、ネットワーク中の全て
のノードが木に転送されるまで繰り返される。

Ｅ、実施例 第１図は最小重みルート計算方法の流れ図である。この
方法の説明は以下定義する用語を用いて行う。

最小重み本は、出発ノード即ち始祖（ｒｏｏｔ）ノード
からネットワーク中の他の各ノードへの最小重みのルー
トのマツプである。木の中の任意の２つのノードは単一
の経路により接続されている。

最小重みのルートを計算する時、木は、始祖ノードから
出発しあらゆるノードが木の中に存在するようになるま
で一時にノードづつ形成される。木は通常、始祖ノード
からネットワーク中の他のノードへのいくつかの枝を含
んでいる。

ノード集合Ｓは、既に木の中にあるノードへ直接接続さ
れたノードのリストである。ノード集合Ｓは、それ自身
水の中にあるノードは含まない。

集合Ｓ中の各ノード・エントリには一時的な先祖ノード
、−時的な先祖伝送グループ及び−時的な重みが付随し
ている。これらの用語は以下定義する。

一時的先祖ノード（ＴＰＮ）は、考慮中の集合Ｓのノー
ドに直接に接続された木ノードである。

−時的先祖伝送グループ（ＴＰＴＧ）は、集合Ｓのノー
ドをその一時的先祖ノードに接続する伝送グループであ
る。

一時的重み（ＴＶ）は、−時的先祖ノード、時的先祖伝
送グループ及び集合Ｓノードを経由する木の重みの和よ
り成る重み値である。

第２図に示した任意に定義したネットワークに対して第
１図の方法を適用することにより、第１図に示した方法
の説明を行う。

ルート計算の開始時に、木及び集合Ｓは、空である。始
祖ノードが選ばれ、集合Ｓに付加される（操作１０）。

操作１２は始祖ノードから木を通って集合Ｓ中のノード
に至る可能な経路の重みを計算する。ルート計算の開始
時に、そのような経路は、存在しない。計算された重み
は、始祖ノード自身に割り当てられる重みである。次に
検査１４が行われ、操作１２中で識別された経路中に２
以上の重みの等しい経路が存在するが否かが調べられる
。集合Ｓ中に始祖ノードしか存在しない場合、２以上の
経路は存在し得ない。もし操作１４で等しい重みの経路
が２以上存在することが示されると、操作１６で擬似ラ
ンダム方式でそれらの経路の１つが選択される。始祖ノ
ードから最小重みの経路を有する集合Ｓ中のノードは、
操作１８で木に転送される。転送されたノードに参照付
けられる集合Ｓ中の他の全てのエントリは操作２０で集
合Ｓから除かれる。

操作１２．１４．１６．１８及び２０の意義はルート計
算の開始時には限定されたものである。

というのは集合Ｓ中には始祖ノードしか存在せず。

始祖ノードしか木に転送できないからである。これらの
操作はルート計算の後のステップを参照しながらより詳
細に説明する。

操作２２で、木のノードに直接接続されたネットワーク
中の全てのノードが識別される。最初のパスでは、これ
は当然始祖ノードに接続されたノードだけを含む。操作
２２で識別されたノードは、そのノードが初期のルート
計算の結果として既に木の中に存在するのでなければ、
集合Ｓに付加される。最初のパスにおいて、始祖ノード
に接続された全てのノードが集合Ｓに付加される。検査
２６は、集合Ｓ中にノードが残っているか否かを見るた
めに行われる。検査２６での否定的な結果は、ルート計
算の終了時にしか生じるべきでない。

１つ以上のノードが集合Ｓ中に存在すると仮定すると、
ルート計算の第２のパスが操作１２から始まる。始祖ノ
ードに２以上のノードが接続されている場合、操作１２
はこれらのノード全での経路の重みを計算する。２番目
以後のパスにおいて、操作１４及び１６はルートの選択
における要因であったりなかったりする。これは後で詳
述する。

操作１８で、最小の重みの経路を有するノードが木に転
送される。もし異なった複数のノードが同じ重みの経路
を経て始祖ノードに接続されているならば、これらのノ
ードの１つが任意に選択され木に転送される。

ルート計算の最終段階で、集合Ｓ中の同じノードに対し
て複数の経路が計算されることがある。

もし任意の与えられた段階でノードが最小重みの経路を
有し、木に転送されるならば、同じノードに対する他の
経路は操作２０で集合Ｓから除かれる。

集合Ｓのノードが木に転送される。毎に、転送されたノ
ードに接続された全てのノードが識別され、もしそれら
が木の中に既に存在するのでなければ、集合Ｓに付加さ
れる。その結果として、ネットワーク中の全てのノード
が木に含まれるので、−時に１枝又は１ノード接続づつ
ルート木が形成される。ネットワーク中の全てのノード
が木に含まれるという事態が起きると、検査２６は集合
Ｓが空であること、即ち木が完成したことを示す。

上記の方法は第２図〜第７図を参照することにより容易
に理解できる。第２図は伝送グループＴ０１〜ＴＧ８に
より相互接続された６個のノードＡ、Ｂ、Ｃ，Ｄ、Ｅ及
びＦを含むネットワークのマツプである。下記の表１は
ノード及び伝送グループに任意に割り当てられた重みの
表である。

退−１ スーーーλ ル−ト十　のステップ 与えられたノードに対して重みの等しい経路が存在しな
いので第２図〜第７図を参照して説明するルート計算に
おいては操作１４及び１６は役割を演じない事に注意す
べきである。操作１４及び１６の役割は最後の図を参照
して説明する。

ルート計算の種々の段階で何が起きているかを理解する
ために図面並びに下記の表２を参照すべきである。

但し、ＴＰＮは一時的先祖ノード。

ＴＰＴＧは一時的先祖伝送グループ、 ＴＶは一時的重み。

ステップＯで、始祖ノード即ちノードＡが第１のパスで
集合Ｓに付加される。始祖ノードに関しては始祖ノード
又は伝送グループが存在しないので、始祖ノードが自動
的に木に転送され、経路の重みは始祖ノードに割り当て
られた重みになる。

ステップ１で、ノードＡに接続されたノード（ノードＢ
、Ｃ１及びＤ）が集合Ｓに付は加えられ、これらのノー
ドの各々に至る経路の重みが計算される０表２から明ら
かなように、ノードＢが、ノードＡへの最小重み経路を
有する。従って、ノードＢが木に転送される。従って木
は第３図に示す単一の枝より構成される。ノードＣ及び
Ｄに関するエントリは集合Ｓ中にとどまる。

ステップ２で、ノードＢに接続されたノードが識別され
る（ノードＡ及びＦ）、ノードＡは既に木の中にあるの
で、ノードＦだけが集合Ｓに付加される。ノードＢを経
由してノードＦに至る経路の重みが計算され、集合Ｓ中
に既に定められた経路の重みと比較される。Ａ−Ｄノー
ド経路は最小の重み値を有するので、ノードＤが木に転
送される。そこで木は第４図に示す形を取る。

ステップ３で、転送されたノードＤに接続されたノード
（ノードＡ、Ｃ及びＥ）が識別される。

ノードＡは既に木の中に存在するので、ノードＣ及びＥ
だけが集合Ｓに付加される。ノードＣに至る２つの異な
った経路の重みが計算されるノードＡを経由するノード
Ｃへの経路が集合Ｓ中の経路の中で最小の重みを有する
ので、第５図に示すようにノードＣが木に転送される。

ノードＣを参照している他の集合Ｓのエントリ（Ｄを経
由してＣに至るもの）は集合Ｓから除去される。

ステップ４でノードＣを経由するノードＦへの付加的な
ルートが集合Ｓに付加される。残りの集合Ｓエントリ中
の最小重みのルート（ノードＢを経由してノードＦ）が
、第６図に示すように木に転送される。ノードＦを参照
する他の集合Ｓエントリ（ノードＣを経由してノードＦ
）が削除される。

ステップＳで、ノードＦを経由する。ノードＥへの付加
的なルートが集合Ｓに付加される。集合Ｓ中の最小重み
ルート（ノードＤを経由してノードＥ）が木に転送され
、（ノードＥを参照する）残りのエントリが集合Ｓから
削除される。この方法は集合Ｓが空になると終了する。

完成した最小重み木は第７図に示されている。

上記の説明中には、１つのノードへ至る等しい重みの経
路は存在しなかった。典型的なデータ通信ネットワーク
では、いくっがの等しい重みの経路が特定のノードに至
ることがある６選択されるルートを、等しい重みの経路
の上により一様に分布させるために、本発明は最小重み
ルート計算方法に１つの変数を付は加える。付加された
変数は、特定のノードに至るネットワーク中の等しい重
みの経路の数に等しい、もし２組以上の等しい重みの経
路が異なった先祖ノードを経由して特定のノードに至る
ならば、それらの組の１つの経路が選択される確率を決
定するために、先祖ノードに関係する変数が使用される
。これは第８図及び表３を参照して説明される。

スー　　３ 第８図は、重み付けられた伝送グループにより相互接続
された６ノードのネットワーク（ノードＡ−Ｆ）を示し
ている。説明のため、ノードにはゼロの重みが割り当て
られると仮定している。表３は、始祖ノードＡから所定
のノードＦへの異なった経路に割り当てられた重みを示
すルート計算表の一部である０表及びネットワーク・マ
ツプを見ると、ノードＡとノードＦとの間に４本の等し
い重みのルートが存在していることが示される。

これらのルートのうち３本は、先祖ノードＥを含む経路
上にあり、１本は先祖ノードＣを経由する経路上にある
。ルート計算でテーブルは、先祖ノードＥを経由するル
ートの組に関係する数値変数（３）及び先祖ノードＣを
経由する経路に関係する数値変数（１）を含んでいる。

もしノードＦ＾のルートがルート計算プロセスの特定の
段階で選択されなければならないならば、等しい重みの
ルートのうち１つが選択される確率を決定するために、
記憶された変数が用いられる。

特にもしＸが、１つの可能なルートの組の中の等しい重
みのルートの数を示す変数であり、Ｙが他の可能な組の
中で等しい重みのルートの数を示す変数であれば、式Ｘ
／　（Ｘ十Ｙ）が、組Ｘがらルートが選択される確率を
定める。

第８図に示すネットワークの場合、この式は、ノードＡ
及びＥを含むルートの組からルートが選択される時は２
５％の確率で、またノードＡがらノードＦへのルートが
選択される時は７５％の確率で、ルートＡＣＦが選択さ
れることを示している。

後のルート計算のために、ノードＦを通る可能な等しい
重みのルートの数を示す、記憶された変数が、Ｆに関す
る異なる先祖を通る等しい重みのルートの和に更新され
なければならない。

同じ方法論が、特定のネットワーク・ノードに至る等し
重みの終点伝送グループの間で選択を行うために使用で
きる。もし与えられた重みＷを有する新しい伝送グルー
プが、やはり重みＷを有するＸ個の可能なルートを既に
含む可能なルートに付は加えられる場合、新しい伝送グ
ループは１／（１＋Ｘ）の確率で選択される。

Ｆ０発明の効果 本発明を用いれば、ネットワークにおいて最小重みの経
路が複数本ある場合に、それらが均一に選択され、特定
のものが再負荷に落ち入ることが避けられる。

【図面の簡単な説明】

第１図は最小重みルート計算方法を示す流れ図。 第２図は最小重みルートの計算を説明するために使われ
る６ノードのネットワークのノード、？ツブ図。 第３図〜第７図は第２図及び表１により定ａされるネッ
トワークに最小重みルート決定のアルゴリズムを適用す
るときに構成される木の種々の段階を示す図、 第８図は別のネットワークを示すノード・マツプ図であ
る。 （タトｌ　１コノ 第２図 第４図 第５図

Claims (1)

【特許請求の範囲】
1. （１）伝送グループにより相互接続されたネットワーク
   ・ノードを含み、上記伝送グループ及び上記ノードに所
   定の重みが与えられた通信ネットワークにおいて最小重
   みのルートを選択する方法であって、 ａ）選択された始祖ノードを木に付加し、 ｂ）既に上記木の中に存在するネットワーク・ノード以
   外の、上記木の中のノードに接続された全てのネットワ
   ーク・ノードより成る集合を求め、 ｃ）上記始祖ノードから上記集合中の各ノードへ至る経
   路の重みを計算し、 ｄ）最小の重みを有する経路を選択するか、又はあるノ
   ードへ至る複数の経路が等しい最小重みを有する場合、
   上記複数の経路の１つを任意に選択し、 ｅ）選択された最小重みの経路中のノードを上記木に転
   送し、 ｆ）上記集合から、転送されたノードに関するその他の
   エントリを取り除き、 ｇ）ネットワーク中の全てのノードが上記木に転送され
   るまで上記ステップｂ〜ｆを含む工程を反復することを
   含む 通信ネットワークにおいて最小重みのルートを選択する
   方法。