JPH1174934A - ルーティング方法、ネットワークノード及び通信システム - Google Patents

Abstract

(57)【要約】 【課題】 ネットワーク構成を簡単にでき、対象とする
ネットワーク・トポロジーが限定されない、効率的であ
って、故障や輻輳に対して容易に対応できるルーティン
グ方法を提供する。 【解決手段】 各ノードは、宛先アドレスとなり得るア
ドレス毎に、各出力リンクを選択するための判断に供す
る確率情報と、これら確率情報を更新させる方法の判断
に供する評価値とを管理している。各ノードは、入力パ
ケットの送信元アドレスに対応した評価値を取り出し、
パケット中の累積コスト値との比較を行い、比較結果に
応じて、送信元アドレスに係る確率情報を更新し、ま
た、評価値を入力パケット中の累積コスト値に応じて更
新する。各ノードは、宛先アドレスに対応した確率情報
における最大要素のリンクにパケットを出力し、その
際、パケットの累積コスト値も更新する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、ルーティング方
法、ネットワークノード及び通信システムに関するもの
である。

【０００２】

【従来の技術】送信元端末からのパケットをネットワー
クを介して宛先端末に送信する通信システムにおいて
は、ネットワーク内を無駄なくパケットが通過させるよ
うにするルーティング方法が重要となっている。このよ
うなルーチング方法を分類すると、以下のように分類す
ることができる（文献１参照）。

【０００３】文献１『Ｃｅｓｕｒ Ｂａｒａｎｓｅｌ他
著、「Ｒｏｕｔｉｎｇ ｉｎ Ｍｕｌｔｉｈｏｐ Ｐａ
ｃｋｅｔ Ｓｗｉｔｃｈｉｎｇ Ｎｅｔｗｏｒｋｓ：Ｇ
ｂ／ｓ Ｃｈａｌｌｅｎｇｅ」、ＩＥＥＥ Ｎｅｔｗｏ
ｒｋ Ｍａｙ／Ｊｕｎｅ１９９５、ｐｐ．３８−４１』 （ａ）テーブルに基づく方法 パケット到着時に、ノードは、自己が有する又はネット
ワーク管理部が集中して管理しているルーティングテー
ブルを調べて、出力回線を選択するルーティング方法が
ある。このルーティング方法には、（ａ１）ショーテス
ト・パス・ルーティング方法や、（ａ２）最適ルーティ
ング方法等がある。

【０００４】ショーテスト・パス・ルーティング方法と
は、個々のノードで、到着パケットに示された宛先アド
レスと、伝達距離、ホップ数（中継スイッチ数）、リン
ク容量、更にはリンクの輻輳状況の特性を考慮した距離
的な評価値により、どの出力回線が最適化を決定して出
力回線を選択する方法である。

【０００５】一方、最適ルーティング方法とは、個々の
ノードで、リンク使用率や伝達遅延等に基づく通信コス
トを評価値とし、コストを最小にする出力回線を選択す
る方法である。

【０００６】（ｂ）セルフルーティングによる方法 セルフルーティングによる方法は、ネットワークのデー
タベースにアクセスすることなく、各ノードがパケット
をルーティングする方法である。

【０００７】例えば、（ｂ１）規則性のあるトポロジー
をもったネットワークの場合には、各ノードは、ネット
ワーク内の他のノードの位置を記述したデータなしに、
ネットワーク構成を知ることができ、自律的にルーティ
ングを行うことができる。また、（ｂ２）フラッディン
グ・ネットワーク」の場合には、各ノードにおける到着
パケットは到着した回線以外の全ての回線に出力され、
これにより宛先端末に確実にパケットが伝送される。

【０００８】

【発明が解決しようとする課題】ところで、ルーティン
グ方法を実現する場合には、以下のような各種の要求が
ある。

【０００９】（１）各ノード間で共通のアクセスするデ
ータベースを持たない方が、ネットワーク構成を簡単に
できて好ましい。

【００１０】（２）対象とするネットワーク・トポロジ
ーが限定されず、自由度があった方が任意のネットワー
クを構成できて好ましい。

【００１１】（３）各ノード間で、ルーティングのため
の情報交換が少ない方が効率的であって好ましい。例え
ば、ネットワークにおけるノードの追加情報等わざわざ
追加ノードや管理装置から各ノードに送るよりは、追加
された以外のノードが自律的に追加されたことを知得で
きることの方が好ましい。

【００１２】（４）ネットワーク内で発生した故障や輻
輳に対して容易に対応できるルーティング方法であるこ
とが望ましい。

【００１３】しかしながら、従来のルーティング方法に
おいては、これら要求の多くを共に満足することが困難
であった。そのため、ルーティング方法に求められる技
術的要求の多くに応えることができるルーティング方法
が求められており、また、そのルーティング方法を実現
するネットワークノード及び通信システムが望まれてい
る。

【００１４】

【課題を解決するための手段】かかる課題を解決するた
め、第１の本発明は、各ネットワークノードが、入力パ
ケットに挿入されている宛先アドレスに応じて自ノード
からの出力リンクを決定するルーティング方法におい
て、各ネットワークノードは、（１）宛先アドレスとな
り得るアドレス毎に、各出力リンクを選択するための判
断に供する確率情報と、これら確率情報を更新させる方
法の判断に供する評価値とを管理しており、（２）他ネ
ットワークノードから単一の宛先アドレスを有するパケ
ットが入力された場合に、（２−１）その入力パケット
の送信元アドレスに対応した上記評価値を取り出し、そ
のパケットに挿入されている累積コスト値との比較を行
い、入力パケットの今回の経路が適しているという比較
結果を得たときに、送信元アドレスに係る確率情報の要
素のうち、入力パケットが入力されたリンクに係る要素
の値を高め、他の要素の値を低め、入力パケットの今回
の経路が適していないという比較結果を得たときに、送
信元アドレスに係る確率情報の要素のうち、入力パケッ
トが入力されたリンクに係る要素の値を低め、他の要素
の値を高め、また、送信元アドレスに対応した上記評価
値を入力パケットに挿入されている累積コスト値に応じ
て更新すると共に、（２−２）入力パケットの宛先アド
レスに対応した確率情報における値が最大の要素に係る
リンクを入力パケットを出力するリンクとして決定し、
その決定されたリンクに対応したコスト分だけ入力パケ
ットの累積コスト値を更新し、更新後のパケットを決定
されたリンクに送出することを特徴とする。

【００１５】また、第２の本発明は、入力パケットに挿
入されている宛先アドレスに応じて自ノードからの出力
リンクを決定するネットワークノードにおいて、（１）
宛先アドレスとなり得るアドレス毎の各出力リンクを選
択するための判断に供する確率情報と、宛先アドレスと
なり得るアドレス毎のこれら確率情報を更新させる方法
の判断に供する評価値と、各出力リンクに対応した上乗
せコスト分情報とを少なくとも格納している情報格納手
段と、（２）他ネットワークノードからパケットが入力
された場合に、その入力パケットの送信元アドレスに対
応した上記評価値を取り出し、そのパケットに挿入され
ている累積コスト値との比較を行い、入力パケットの今
回の経路が適しているという比較結果を得たときに、送
信元アドレスに係る確率情報の要素のうち、入力パケッ
トが入力されたリンクに係る要素の値を高め、他の要素
の値を低め、入力パケットの今回の経路が適していない
という比較結果を得たときに、送信元アドレスに係る確
率情報の要素のうち、入力パケットが入力されたリンク
に係る要素の値を低め、他の要素の値を高め、また、送
信元アドレスに対応した上記評価値を入力パケットに挿
入されている累積コスト値に応じて更新する確率情報更
新手段と、（３）入力パケットの宛先アドレスに対応し
た確率情報における値が最大の要素に係るリンクを入力
パケットを出力するリンクとして決定し、その決定され
たリンクに対応したコスト分だけ入力パケットの累積コ
スト値を更新し、更新後のパケットを決定されたリンク
に送出するパケット出力手段とを有することを特徴とす
る。

【００１６】さらに、第３の本発明は、第２の本発明の
複数のネットワークノードを有し、これらネットワーク
ノードが任意のネットワーク・トポロジーに従って接続
されていることを特徴とする。

【００１７】

【発明の実施の形態】以下、本発明によるルーティング
方法、ネットワークノード及び通信システムの一実施形
態を図面を参照しながら詳述する。

【００１８】この実施形態の通信システム（ネットワー
ク）も、図示は省略するが、交換機や端末等の複数のネ
ットワークノード（以下、単にノードと呼ぶ）と、ノー
ド間を適宜結ぶリンクとからなり、送信元端末からのパ
ケットを適宜ルーティングして宛先端末に転送するもの
である。この実施形態の場合、通信システム（ネットワ
ーク）のトポロジーは任意であって良い。

【００１９】各ノードは、ハードウェア的には、従来と
ほぼ同様な構成を有する。すなわち、各ノードは、図２
に示すように、他のノード又は送信端末からのパケット
を受信処理する入力部１０、入力部１０が受信したパケ
ットを交換処理するスイッチ部（バッファメモリを内蔵
する）１１、スイッチ部１１が交換処理したパケットを
他のノードに向けて送出する出力部１２、入力部１０が
受信したパケットのヘッダ（パケットが情報パケットで
はなく制御パケットであれば制御パケットの全体）が与
えられ、それに対してルーティングやその他の制御動作
を実行する制御部１３、及び、制御部１３が各種の制御
動作で利用する各種情報を格納しているデータベース部
１４を有する。

【００２０】しかし、この実施形態の各ノードは、ルー
ティング処理面からの機能的には、図１に示す詳細構成
（機能モデル）を有する。

【００２１】図１において、ノード２０は、大きくは、
基本レイヤ処理部２１と、知識レイヤ処理部２２とから
なり、外部環境２３からの入力パケットをその宛先に応
じて外部環境２３に出力する。ここで、外部環境２３と
は、自ノード２０以外の他のノードを総称して呼んでい
る。

【００２２】基本レイヤ処理部２１は、確率的学習オー
トマトン（ＳｔｏｃｈａｓｔｉｃＬｅａｒｎｉｎｇ Ａ
ｕｔｏｍａｔａ；以下、ＳＬＡと略称する；文献２参
照）による自律的学習機構によって出力リンク選択確率
を学習すると共に、学習動作を通じて適宜更新されてい
る出力リンク選択確率に基づいて、今回の入力パケット
に対する出力リンクを決定するものである。すなわち、
ユニキャスト通信におけるルーティング処理を行うもの
である。

【００２３】文献２『久保正男他、「蟻の餌争奪ゲーム
によるマルチエージェントシステムの協調動作評価」、
情報処理学会論文誌、Ｖｏｌ．８５、Ｎｏ．８、１９９
４年８月』 一方、知識レイヤ処理部２２は、基本レイヤ処理部２１
の基本ルーティング機能を利用しつつ、ユニキャスト通
信以外の高度な通信におけるルーティング機能等を実現
するものである。例えば、マルチキャスト通信や閉域通
信におけるルーティング機能を実行したり、その時点で
の外部環境２３等の状況に応じて、基本レイヤ処理部２
１が選択した出力リンク以外のリンクにパケットを送出
するように制御したりする。また、知識レイヤ処理部２
２は、受信した制御情報（例えば、隣接ノードの故障、
新規ノードの追加、既存ノードの削除）に基づいて、自
ノード２０が管理するルーティングに関する情報を適宜
更新制御したりするものである。

【００２４】基本レイヤ処理部２１は、詳細には、以下
のような機能要素でなる。すなわち、ヘッダ抽出部３
０、逆方向リンク評価部３１及び出力リンク決定部３２
からなる。

【００２５】ヘッダ抽出部３０は、図３に例示するよう
なフォーマットに従う入力パケットｘにおけるヘッダ部
の情報を抽出し、ヘッダ部内の各情報をその情報に応じ
た各部に与えるものである。また、パケットのデータ部
の内容も、パケット種類によって定まる各部に与えるも
のである。

【００２６】図３において、この実施形態のパケット
は、例えば、情報パケットか制御パケットかを示すパケ
ット種別、送信元端末を規定する送信元アドレス、宛先
端末を規定する宛先アドレス、送信元ノードから直前ノ
ードまでの累積コスト値（自ノード２０に到達するまで
の累積コスト値）等を含むヘッダ部と、転送データ本体
が挿入されているデータ部とからなっている。ここで、
コストとは、例えば、パケットの伝達遅延時間、ノード
間距離等に従う伝送コスト及び交換コストの総和を言
う。

【００２７】ここで、ヘッダ抽出部３０は、送信元アド
レスや宛先アドレスに対応した、内部テーブルのアドレ
スとなる値の集合φ＝｛φ０，φ１，…，φＮ−１｝を
格納しており、送信元アドレスｉや宛先アドレスｄが与
えられたときに、アドレス値φｉやφｄを出力するよう
になされている。但し、Ｎはネットワーク内でのノード
数を表している。なお、アドレス値φｉやφｄとして、
送信元アドレスｉや宛先アドレスｄをそのまま用いるよ
うにしても良い。

【００２８】逆方向リンク評価部３１は、評価アルゴリ
ズム処理部（Ａ）３１ａと、アドレス別評価値テーブル
（Ｃ）３１ｂとからなる。

【００２９】アドレス別評価値テーブル（Ｃ）３１ｂに
は、各アドレス値φ０，φ１，…，φＮ−１に対応付け
て、今回の送信元端末から前回にきたパケットにおける
累積コスト値｛Ｃ０，Ｃ１，…，ＣＮ−１｝を判断基準
評価値として格納しているものである（後述する図６参
照）。

【００３０】評価アルゴリズム処理部（Ａ）３１ａは、
入力パケットｘに挿入されている累積コスト値ｃと、そ
のパケットｘの送信元アドレスｉ（ψｉ）に対応してア
ドレス別評価値テーブル３１ｂに格納されている判断基
準評価値Ｃｉとの比較により、後述する送信元アドレス
ｉ（ψｉ）に対応した出力リンク選択確率ベクトルＰｉ
の更新方法を規定する強化信号βを形成するものであ
る。なお、強化信号βは、この実施形態の場合、０又は
１をとるものである。

【００３１】出力リンク決定部３２は、確率ベクトル集
合管理部３２ａ及びリンク出力処理部３２ｂからなる。

【００３２】確率ベクトル集合管理部３２ａは、各ノー
ド（各アドレスψｉ）に対応したノード数に等しい数の
出力リンク選択確率ベクトルＰ０，Ｐ１，…，ＰＮ−１
の集合Ｐを格納している（後述する図６参照）。各出力
リンク選択確率ベクトルＰｎ（ｎは０〜Ｎ−１）はそれ
ぞれ、当該ノード２０に接続されているリンク数ｌ＋１
だけの要素Ｐｎ０，Ｐｎ１、…，Ｐｎｌからなってい
る。

【００３３】確率ベクトル集合管理部３２ａは、強化信
号βが与えられたときには、今回の入力パケットｘにお
ける送信元アドレスψｉに係る出力リンク選択確率ベク
トルＰｉを以下のように更新する。

【００３４】確率ベクトル集合管理部３２ａは、強化信
号βが１であるときは、出力リンク選択確率ベクトルＰ
ｉにおける、今回の入力パケットｘが入力されたリンク
Ｌ（Ｌは０〜ｌ）に係る要素ＰｉＬの値を高め、他の要
素Ｐｉｊ（ｊは０〜Ｌ−１、Ｌ＋１〜ｌのいずれか）の
値を低めるように更新する。一方、確率ベクトル集合管
理部３２ａは、強化信号βが０であるときは、出力リン
ク選択確率ベクトルＰｉにおける、今回の入力パケット
ｘが入力されたリンクＬに係る要素ＰｉＬの値を低め、
他の要素Ｐｉｊを高めるように更新する。

【００３５】以上のような更新を実行できるものであれ
ば、その更新方法はいずれの方法であっても良いが、い
くつかを例示すると以下の通りである。

【００３６】強化信号βが１であるときは、（１）式に
示す強化学習関数Ｆｉｊを用いた（３）式に従って、出
力リンク選択確率ＰｉＬ、Ｐｉｊを更新し、強化信号β
が０であるときは、（２）式に示す強化学習関数Ｇｉｊ
を用いた（４）式に従って、出力リンク選択確率Ｐｉ
Ｌ、Ｐｉｊを更新する。なお、（３）式及び（４）式に
おける総和Σは、ｊ（ｊは０〜Ｌ−１、Ｌ＋１〜ｌ）に
ついてである。また、（２）式及び（３）式におけるｒ
ｅｗａｒｄ及びｐｅｎａｌｔｙはそれぞれ、０〜１の範
囲内の定数である。さらに、ｔは時刻パラメータであ
る。

【００３７】 Ｆｉｊ＝ｒｅｗａｒｄ＊Ｐｉｊ（ｔ） …（１） Ｇｉｊ＝ｐｅｎａｌｔｙ＊Ｐｉｊ（ｔ） …（２） β＝１のとき ＰｉＬ（ｔ＋１）＝ＰｉＬ（ｔ）＋ΣＦｉｊ Ｐｉｊ（ｔ＋１）＝Ｐｉｊ（ｔ）−Ｆｉｊ …（３） β＝０のとき ＰｉＬ（ｔ＋１）＝ＰｉＬ（ｔ）−ΣＧｉｊ Ｐｉｊ（ｔ＋１）＝Ｐｉｊ（ｔ）＋Ｇｉｊ …（４） 他の方法例としては、０〜１の範囲内の定数であるｒｅ
ｗａｒｄ及びｐｅｎａｌｔｙを用いる代わりに、（５）
式及び（６）式で表される動的に変化するｒｅｗａｒｄ
及びｐｅｎａｌｔｙを用いて、（１）式〜（４）式によ
って更新する方法を挙げることができる。但し、ａ及び
ｂは０〜１の範囲内の定数である。また、ｃは入力パケ
ットｘに挿入されている累積コスト値であり、Ｃｉは前
回その送信元から到着したパケットに挿入されていた累
積コスト値である。

【００３８】 ｒｅｗａｒｄ＝ａ＊｜ｃ−Ｃｉ｜／｜ｃ＋Ｃｉ｜ …（５） ｐｅｎａｌｔｙ＝ｂ＊｜ｃ−Ｃｉ｜／｜ｃ＋Ｃｉ｜ …（６） リンク出力処理部３２ｂは、高度の通信以外の通常の通
信（ユニキャスト通信）においては、入力パケットｘの
宛先アドレスｄ（ψｄ）に係る出力リンク選択確率ベク
トルＰｄの要素のうち、最大確率値の要素を見つけだ
し、その最大確率要素に係るリンクをパケットの出力リ
ンクｋとして決定するものである。

【００３９】リンク出力処理部３２ｂは、各リンクにパ
ケットを出力する際に、入力パケットｘにおける累積コ
スト値に上乗せする各リンク別のコストα０〜αｌの集
合αを内部格納しており、決定した出力リンクｋの妥当
性を知識レイヤ処理部２２によって確認された際には、
リンク出力処理部３２ｂは、入力パケットｘにおける累
積コスト値ｃを出力リンクｋについての上乗せコストα
ｋ分だけ増大させ、かかる処理後のパケットをリンクｋ
に出力する。

【００４０】なお、リンク出力処理部３２ｂは、知識レ
イヤ処理部２２から複数のリンクに対する出力処理が起
動されたときには（例えば、マルチキャスト通信や閉域
通信による）、各出力リンク毎に上述のような累積コス
ト値の更新処理を行う。

【００４１】また、リンク出力処理部３２ｂは、自己が
決定した出力リンクｋではなく、他のリンクへの出力を
知識レイヤ処理部２２によって指示されたときには、そ
の出力リンクへの出力処理を実行する。

【００４２】以下、基本レイヤ処理部２１でのユニキャ
スト通信時のルーティング処理を、図４及び図５のフロ
ーチャート並びに図６の処理概念図をも用いて説明す
る。なお、基本レイヤ処理部２１でのユニキャスト通信
時のルーティング処理は、大きくは、出力リンク選択確
率ベクトルの更新処理と、パケットの出力処理とに分け
ることができ、図４及び図５のフローチャートの例は、
出力リンク選択確率ベクトルの更新処理、パケットの出
力処理の順序で処理を行うものを示しているが、この処
理順序はこれに限定されるものではない。

【００４３】パケットｘが入力されると、入力パケット
ｘに付加されている送信元アドレスｉ、宛先アドレス
ｄ、累積コスト値ｃ、及び、当該パケットｘが入力され
たリンク番号Ｌを認識する（ステップ１００）。その
後、送信元アドレスｉをキーとしてアドレス集合φを検
索し、検索によって得られたアドレスφｉに対応する出
力リンク選択確率ベクトルＰｉを確率ベクトル集合Ｐか
ら特定する（ステップ１０１）。

【００４４】そして、対応するアドレスφｉ及び出力リ
ンク選択確率ベクトルＰｉが存在するか否かを判断する
（ステップ１０２）。

【００４５】存在していないときには、アドレス集合ψ
に今回の送信元アドレスｉに係る新たな要素ψｉを追加
すると共に、確率ベクトル集合Ｐにも、今回の送信元ア
ドレスｉに係る新たな要素Ｐｉを追加して後述するステ
ップ１１０に移行する（ステップ１０３）。ここで、追
加される出力リンク選択確率ベクトルＰｉとしては、当
該パケットｘが入力されたリンクＬの確率を最も大きな
値としている初期用のものを適用する。

【００４６】これに対して、アドレスφｉ及び出力リン
ク選択確率ベクトルＰｉが存在する場合には、アドレス
φｉをキーとしてアドレス別評価値テーブルＣから前回
の累積コスト値Ｃｉを取り出し（ステップ１０４）、こ
の前回の累積コスト値Ｃｉと、入力パケットｘに挿入さ
れている累積コスト値ｃとを比較する（ステップ１０
５）。そして、ｃ＝＜Ｃｉならば値が１の強化信号βを
出力し（ステップ１０６）、一方、ｃ＞Ｃｉならば値が
０の強化信号βを出力する（ステップ１０７）。

【００４７】ここで、判断基準を緩やかにするために、
前回の累積コスト値Ｃｉにオフセット値ｙを加えた値Ｃ
ｉ＋ｘと、入力パケットｘに挿入されている累積コスト
値ｃとを比較して強化信号βを形成するようにしても良
い。

【００４８】以上のような比較処理が終了すると、アド
レス別評価値テーブルＣにおけるアドレスφｉに対応し
た値Ｃｉを、入力パケットｘに挿入されている累積コス
ト値ｃに更新する（ステップ１０８）。

【００４９】その後、強化信号βの値の従って、上述し
た方法により、今回の送信元アドレスｉに係る出力リン
ク選択確率ベクトルＰｉの値を更新する（ステップ１０
９）。上述したように、当該パケットｘが入力されたリ
ンク番号Ｌのリンクの出力リンク選択確率ＰｉＬの更新
が中心として行われる。すなわち、送信元（ｉ）とリン
クＬとの結びつきを確率ベクトルＰｉのリンクＬの対応
部を更新することにより変更する。このような出力リン
ク選択確率ベクトルＰｉの更新は、今回の送信元アドレ
スｉを宛先アドレスｄとする将来の到着パケットの出力
リンクの決定に反映される。

【００５０】図７は、出力リンク選択確率ベクトルの更
新処理の具体例を示す説明図である。この例の場合、送
信元アドレスｉが２５、宛先アドレスｄが１０、累積コ
スト値ｃが３０のパケットが、リンク番号Ｌが１のリン
クから入力された場合である。送信元アドレス２５に対
応した評価値（前回の累積コスト値）Ｃｉ（Ｃ２５）が
４０であると、今回の入力パケットにおける累積コスト
値ｃ＝３０の方が小さいので、強化信号βの値は１とな
る。その結果、送信元アドレス２５に対応した出力リン
ク選択確率ベクトルＰｉ（Ｐ２５）の内のリンク番号１
の要素の確率が増大され（０．２５から０．５５）、他
のリンク番号の要素の確率が減少される（０．２５から
０．１５）。その後、送信元アドレス２５に対応した評
価値Ｃｉ（Ｃ２５）が、今回の入力パケットにおける累
積コスト値３０に更新される。

【００５１】以上のような出力リンク選択確率ベクトル
Ｐｉの更新処理が終了すると、パケット出力処理に移行
する。パケット出力処理ではまず、宛先アドレスｄをキ
ーとしてアドレス集合φを検索し、検索によって得られ
たアドレスφｄに対応する出力リンク選択確率ベクトル
Ｐｄを確率ベクトル集合Ｐから特定する（ステップ１１
０）。なお、閉域通信の対象パケットであれば、検索す
るアドレス集合ψとして閉域通信用のアドレス集合を検
索するようにすれば良い。

【００５２】そして、対応するアドレスφｄ及び出力リ
ンク選択確率ベクトルＰｄが存在するか否かを判断する
（ステップ１１１）。

【００５３】存在していないときには、入力パケットを
廃棄する（ステップ１１２）。なお、閉域通信である場
合を除き、存在していないときに、入力リンク以外の全
てのリンクを出力リンクに決定するようにしても良い。
この場合には、例えば、各ノードにおいて、パケットに
挿入されているタイムスタンプと現在時刻との比較等に
よって、長期に亘って宛先ノードに到達しない迷走パケ
ットを検出してこの段階でパケット廃棄するようにす
る。

【００５４】これに対して、アドレスφｄ及び出力リン
ク選択確率ベクトルＰｄが存在する場合には、出力リン
ク選択確率ベクトルＰｄ中の最も確率値が高い要素にか
かるリンクを出力リンクとして決定して知識レイヤ処理
部２２に通知する（ステップ１１３）。

【００５５】このとき、知識レイヤ処理部２２は、内蔵
するリンクの障害情報等に基づいて、その決定されたリ
ンクを出力リンクとすることの妥当性を確認する（ステ
ップ１１４）。妥当でない場合には、次の確率値のリン
クに変更する。

【００５６】その後、知識レイヤ処理部２２によって妥
当性の判断処理がなされた出力リンクｋについてのリン
ク別コスト値αｋを、入力パケットｘの累積コスト値ｃ
に加算してパケットの累積コスト値ｃをその加算値ｃ＋
αｋに更新し（ステップ１１５）、更新後のパケットｘ
をリンクｋに送出する（ステップ１１６）。

【００５７】次に、知識レイヤ処理部２２が実行するマ
ルチキャスト通信時における各宛先についての出力リン
クの決定処理（ルーティング処理）を、図８のフローチ
ャートを用いて説明する。

【００５８】なお、図８に示す処理は、自ノード２０が
マルチキャストの送信元となって全ての他のノードに送
信するる場合や、他ノードから与えられたパケットにマ
ルチキャスト通信に供する複数の宛先アドレスが挿入さ
れている場合や、パケットには具体的な宛先アドレスは
挿入されていないがマルチキャスト通信を指示する情報
が挿入されており、内蔵する格納情報によってマルチキ
ャスト通信に供する複数の宛先アドレスを認識した場合
等に実行される。また、マルチキャストに供するパケッ
トが他ノードから到来したものである場合には、図８に
示す処理を実行する前に、上述したような出力リンク選
択確率ベクトルＰｉの更新処理が実行されている。

【００５９】知識レイヤ処理部２２はまず、マルチキャ
ストに供する全ての宛先アドレスｄ１〜ｄｍ（ｍは宛先
数）に対応した出力リンク選択確率ベクトルＰｄ１〜Ｐ
ｄｍをそれぞれ取り出す（ステップ２００）。

【００６０】その後、各宛先アドレスについての出力リ
ンク選択確率ベクトルＰｄ１、…、Ｐｄｍのそれぞれの
出力リンクに対応している全ての要素Ｐｄ１１〜Ｐｄ１
ｌ、…、Ｐｄｍ１〜Ｐｄｍｌ（代表させて符号ｐｉで表
す）を、その出力リンクを採用するか否かの判断閾値Ｔ
Ｈ（ＴＨは０以上の固定値）と比較し、その比較結果に
応じて送出フラグｆｄ１１〜ｆｄ１ｌ、…、ｆｄｍ１〜
ｆｄｍｌ（代表させて符号ｆｉで表す）の値を設定する
（ステップ２０１）。すなわち、ｐｉ＞ＴＨならばｆｉ
＝１とし、ｐｉ＝＜ＴＨならばｆｉ＝０とする。

【００６１】次に、各出力リンク０、…、ｌごとに、そ
の時点でパケットの送出が実行されていない全ての宛先
アドレスの送出フラグを合計し、合計値が最大である出
力リンクＬｍａｘを１つ決定する（ステップ２０２）。

【００６２】そして、決定された出力リンクＬｍａｘへ
の送出フラグが１となっている全ての宛先アドレスを、
出力パケットの宛先アドレスフィールドに挿入し、出力
リンクＬｍａｘに送信する（ステップ２０３）。

【００６３】その後、パケットの送信が終了していない
マルチキャスト通信に供する宛先アドレスが残っている
か否かを判断する（ステップ２０４）。残っていなけれ
ば、一連の処理を終了する。これに対して、残っている
場合には、上述したステップ２０２に戻って、出力に供
する出力リンクＬｍａｘ（上述したものと異なる）の探
索を行う。

【００６４】上記実施形態によれば、以下の効果を奏す
ることができる。 （１）各ノードにおいて自律的にルーティング処理して
いるので、各ノード間で共通のアクセスするデータベー
スを設ける必要がなく、ネットワーク構成を簡単にでき
る。

【００６５】（２）各ノードにおいてネットワーク・ト
ポロジーを考慮することなくルーティング処理を行うの
で、処理対象とするネットワーク・トポロジーが限定さ
れず、自由度がある。すなわち、任意のネットワーク・
トポロジーに対してこの実施形態を適用できる。

【００６６】（３）各ノード間で、ルーティングのため
に回線の使用状況等の情報を授受する必要がない。すな
わち、ルーティングのための情報交換が少なく、情報転
送が効率的である。また、送信元が追加ノードであれ
ば、新規な送信元アドレスを認識してルーティングに必
要な情報を自動的に設定するので、追加ノード等がわざ
わざ追加されたことを通知することが不要である。

【００６７】（４）制御パケットの授受等により、ネッ
トワーク内で発生した故障や輻輳のために使用禁止の出
力リンクを知識レイヤ処理部に登録しておくことによ
り、ネットワーク内で発生した故障や輻輳に対して容易
に対応できる。また、このような制御パケットを授受し
ない場合であっても、故障や輻輳により故障や輻輳に係
るリンクが使用されなくなると、出力リンク選択確率ベ
クトルにおけるそのリンク要素の値が０に近付き、その
リンクが益々使用されないようになる。

【００６８】（５）マルチキャスト通信や、閉域通信
や、出力リンク等の変更に対して容易に対応することが
できる。

【００６９】上記実施形態の説明においても、上記実施
形態を変形した種々の実施形態に言及したが、さらに、
以下のような変形実施形態を挙げることができる。

【００７０】上記実施形態においては、評価値Ｃｉを、
今回の入力パケットｘに挿入されている累積コスト値ｃ
に更新するものを示したが、今までの評価値Ｃｉと今回
の入力パケットｘに挿入されている累積コスト値ｃとの
重み付け加算等によって評価値Ｃｉを更新するようにし
ても良い。

【００７１】また、上記実施形態においては、出力リン
ク選択確率ベクトルの各要素の値が０〜１の範囲内の任
意の値をとるものを示したが、メモリ容量の削減のため
に、以下のようなテンプレートベクトルを利用するよう
にしても良い。

【００７２】すなわち、出力リンク選択確率ベクトルの
各要素が取り得る値を限定し、パターン化した組み合わ
せを複数規定し、テンプレートベクトルとし、各々に番
号を付与し、強化信号に応じて、入力リンクの確率値を
１段だけ高めた又は低めたテンプレートベクトルに更新
し、記憶はテンプレートベクトル番号で行うようにして
メモリ容量を削減させるようにしても良い。なお、テン
プレートベクトル自体を格納するようにしても、各要素
値の取り得る値が限定されているので（ビット数が少な
いので）、メモリ容量を削減できる。

【００７３】テンプレートベクトルを用いた場合には、
出力リンク選択確率ベクトルの更新は、学習強化関数を
利用した更新ではないので、出力リンク選択時における
選択精度が落ちる場合がある。

【００７４】これを補正するために、補正対象ノードを
決め、そのノードからのリンクごとの入力パケット数を
監視し、実際の出力リンク選択確率ベクトルを計算し、
現在使用されているテンプレートベクトルと比較し、両
者のマンハッタン距離、あるいはユークリッド距離があ
る値よりも大きい場合は現在使用しているテンプレート
ベクトルを変更するようにすれば良い。変更方法として
は、マンハッタン距離あるいはユークリット距離がより
近いテンプレートベクトルを選択するか、テンプレート
ベクトルを採用せずに実際の観測値を用いる方法に変換
する。

【００７５】さらに、上記実施形態においては、出力パ
ケットにおける宛先アドレスが入力パケットと同じもの
を示したが、特殊アドレスから一般アドレスへの変換の
ようにアドレス変換を行った出力パケットを送出するよ
うにしても良い。このような変換処理は、知識レイヤ処
理部が実行する。

【００７６】さらにまた、マルチキャスト通信時におけ
る出力リンクの決定方法は、上記実施形態のものに限定
されない。例えば、各宛先アドレス毎にユニキャスト通
信時と同様にして出力リンクを決定し、出力リンクへの
出力時に、同一の出力リンクに決定された１又は複数の
宛先アドレスをパケットに挿入するようにしても良い。

【００７７】

【発明の効果】以上のように、本発明のルーティング方
法、ネットワークノード及び通信システムによれば、各
ノード間で共通のアクセスするデータベースを持たない
のでネットワーク構成を簡単にでき、対象とするネット
ワーク・トポロジーが限定されず、各ノード間で、ルー
ティングのための情報交換が少なく効率的であり、ネッ
トワーク内で発生した故障や輻輳に対して容易に対応で
きるルーティング方法、ネットワークノード及び通信シ
ステムを実現できる。

【図面の簡単な説明】

【図１】実施形態の機能的構成を示すブロック図であ
る。

【図２】実施形態のハードウェア的構成を示すブロック
図である。

【図３】実施形態のパケットフォーマット例を示す説明
図である。

【図４】実施形態のユニチャスト通信時のルーティング
処理を示すフローチャート（１）である。

【図５】実施形態のユニチャスト通信時のルーティング
処理を示すフローチャート（２）である。

【図６】実施形態のユニチャスト通信時のルーティング
処理の説明補助図である。

【図７】実施形態の出力リンク選択確率ベクトルの更新
例を示す説明図である。

【図８】実施形態のマルチキャスト通信時における出力
リンクの決定処理を示すフローチャートである。

【符号の説明】

２０…ノード、２１…基本レイヤ処理部、２２…知識レ
イヤ処理部、３０…ヘッダ抽出部、３１…逆方向リンク
評価部、３１ａ…評価アルゴリズム処理部、３１ｂ…ア
ドレス別評価値テーブル、３２…出力リンク決定部、３
２ａ…確率ベクトル集合管理部、３２ｂ…リンク出力処
理部。

Claims (5)

【特許請求の範囲】
1. 【請求項１】 各ネットワークノードが、入力パケット
   に挿入されている宛先アドレスに応じて自ノードからの
   出力リンクを決定するルーティング方法において、 各ネットワークノードは、 宛先アドレスとなり得るアドレス毎に、各出力リンクを
   選択するための判断に供する確率情報と、これら確率情
   報を更新させる方法の判断に供する評価値とを管理して
   おり、 他ネットワークノードから単一の宛先アドレスを有する
   パケットが入力された場合に、 その入力パケットの送信元アドレスに対応した上記評価
   値を取り出し、そのパケットに挿入されている累積コス
   ト値との比較を行い、入力パケットの今回の経路が適し
   ているという比較結果を得たときに、送信元アドレスに
   係る確率情報の要素のうち、入力パケットが入力された
   リンクに係る要素の値を高め、他の要素の値を低め、入
   力パケットの今回の経路が適していないという比較結果
   を得たときに、送信元アドレスに係る確率情報の要素の
   うち、入力パケットが入力されたリンクに係る要素の値
   を低め、他の要素の値を高め、また、送信元アドレスに
   対応した上記評価値を入力パケットに挿入されている累
   積コスト値に応じて更新すると共に、 入力パケットの宛先アドレスに対応した確率情報におけ
   る値が最大の要素に係るリンクを入力パケットを出力す
   るリンクとして決定し、その決定されたリンクに対応し
   たコスト分だけ入力パケットの累積コスト値を更新し、
   更新後のパケットを決定されたリンクに送出することを
   特徴とするルーティング方法。
2. 【請求項２】 同一のパケットを複数の宛先に送出する
   場合において、各宛先アドレスについての確率情報の要
   素の値が閾値以上であるリンク順に、パケットを出力す
   るリンクを決定し、決定したリンクに対して、そのリン
   クに係る確率情報の要素の値が閾値以上である全ての宛
   先アドレスを挿入したパケットを出力することを特徴と
   する請求項１に記載のルーティング方法。
3. 【請求項３】 入力パケットに挿入されている宛先アド
   レスに応じて自ノードからの出力リンクを決定するネッ
   トワークノードにおいて、 宛先アドレスとなり得るアドレス毎の各出力リンクを選
   択するための判断に供する確率情報と、宛先アドレスと
   なり得るアドレス毎のこれら確率情報を更新させる方法
   の判断に供する評価値と、各出力リンクに対応した上乗
   せコスト分情報とを少なくとも格納している情報格納手
   段と、 他ネットワークノードからパケットが入力された場合
   に、その入力パケットの送信元アドレスに対応した上記
   評価値を取り出し、そのパケットに挿入されている累積
   コスト値との比較を行い、入力パケットの今回の経路が
   適しているという比較結果を得たときに、送信元アドレ
   スに係る確率情報の要素のうち、入力パケットが入力さ
   れたリンクに係る要素の値を高め、他の要素の値を低
   め、入力パケットの今回の経路が適していないという比
   較結果を得たときに、送信元アドレスに係る確率情報の
   要素のうち、入力パケットが入力されたリンクに係る要
   素の値を低め、他の要素の値を高め、また、送信元アド
   レスに対応した上記評価値を入力パケットに挿入されて
   いる累積コスト値に応じて更新する確率情報更新手段
   と、 入力パケットの宛先アドレスに対応した確率情報におけ
   る値が最大の要素に係るリンクを入力パケットを出力す
   るリンクとして決定し、その決定されたリンクに対応し
   たコスト分だけ入力パケットの累積コスト値を更新し、
   更新後のパケットを決定されたリンクに送出するパケッ
   ト出力手段とを有することを特徴とするネットワークノ
   ード。
4. 【請求項４】 同一のパケットを複数の宛先に送出する
   場合において、各宛先アドレスについての確率情報の要
   素の値が閾値以上であるリンク順に、パケットを出力す
   るリンクを決定し、決定したリンクに対して、そのリン
   クに係る確率情報の要素の値が閾値以上である全ての宛
   先アドレスを挿入したパケットを出力するマルチキャス
   ト処理手段をさらに有することを特徴とする請求項３に
   記載のネットワークノード。
5. 【請求項５】 請求項３又は４に記載の複数のネットワ
   ークノードを有し、これらネットワークノードが任意の
   ネットワーク・トポロジーに従って接続されていること
   を特徴とする通信システム。