米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 日本電気テレコムシステム株式会社

発明の名称 ノード間のルート検索方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平9−18474
公開日 平成9年(1997)1月17日
出願番号 特願平7−160452
出願日 平成7年(1995)6月27日
代理人 【弁理士】
【氏名又は名称】京本 直樹 (外2名)
発明者 井上 治子 / 大江 靖之 / 野田 正人
要約 目的
ルート検索フレーム信号により複数のルートの中で時間的に最短のルートを選択して行うことにより、2ルート間の最短ルートを決定する。

構成
ノード1を検索元ノード、ノード3を検索先ノードとした場合、先ず、ノード1からルート検索フレーム信号をノード2,4へ送信する。ノード2,4はそれぞれノード3,4、、ノード2,3へ転送する。この時それぞれノード4,2からも信号を受信するが時間的に速いノード1からの信号のみを受信しルーティングテーブルに保持する。ノード3はノード2,4より信号を受信するが、時間的に速いノード4からの信号のみ受信し、ルーティングテーブルに保持し、同時に応答信号をノード4に返信する。ノード4は保持して方路のノード1にこれを転送し、ノード1はこれを受信しそれぞれルーティングテーブルに保持し全体のルートを決定する。
特許請求の範囲
【請求項1】 複数のノードから構成されるネットワークの任意の2ノード間で時間的に最短の通信ルートを求めるルート検索方法において、検索を行う検索元ノードと検索先の検索先ノードとを結ぶ総てのルート上にある各中継ノードの中の前記検索元ノードに隣接する各前記中継ノードに対し検索元ノード番号および検索先ノード番号を含むルート検索フレーム信号を送信し、前記ルート検索フレーム信号を受信した各前記中継ノードは時間的に最初に受信した方路を復路の送信方路としてルーティングテーブルに保持すると同時に前記ルート検索フレーム信号を次の前記中継ノードに転送し、次の各前記中継ノードは先の前記中継ノードと同様処理を実行し前記ルート検索フレーム信号を次の前記中継ノードに転送し、次以降の前記中継ノードも順次同様処理を実行して行き、前記検索先ノードに至り転送されて来た前記ルート検索フレーム信号を時間的に最初に受信した方路を復路の送信方路としこれをルーティングテーブルに保持すると同時にこの送信方路に対し前記ルート検索フレーム信号と同一構成の応答信号を返送し、この応答信号を受信した前記中継ノードはこの受信方路を往路の送信方路として前記ルーティングテーブルに保持すると同時に前記応答信号を前記ルーティングテーブルに保持された復路の送信方路に転送し、次以降の前記中継ノードも順次同様処理を実行して行き、前記検索元ノードに至り前記中継ノードから転送されて来た前記応答信号を受信しこの受信方路を往路の送信方路としてルーティングテーブルに保持し、このようにして各ノードが保持した前記ルーティングテーブルにより通信ルートが決定されることを特徴とするノード間のルート検索方法。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明はノード間のルート検索方法に関し、特にネットワークの2ノード間で時間的に最短のルートを求めるルート検索方法に関する。
【0002】
【従来の技術】従来、この種のノード間のルート検索方法は、複数のノードにより複雑な経路を構成するネットワークにおいて、ネットワークの監視装置のオペレータが自らの手により最適なノード間の通信ルートをその都度決定することは困難であるため、これを解消することを目的として自動的にこれを決定する方法が実用化されている。
【0003】例えば、特開平03−123999号公報に示されるように、最適なルートを算出する評価式を用いて始点から終点までのルート検索を行う方式がある。また特開昭58−166849号公報に示されるように、複数のノードの集合体であるエリアに対し付与された識別番号を管理するエリア番号管理テーブルとエリア内の各ノードの識別番号を管理するノード番号管理テーブルとを保持し、ルート設定要求メッセージに格納された相手先のエリア番号とノード番号をキーにして、各中継ノード毎にこの階層化された管理テーブルより出回線を求める方法がある。
【0004】更に特開昭63−174446号公報と特開昭62−168267号公報に示されるように、行列演算により最短経路長を算出することによりルート検索を行う方式がある。
【0005】
【発明が解決しようとする課題】このように従来のノード間ルート検索方法は、いくつかの方法があるが、例えば、公開平03−123999号公報では、評価式を用いて最適なルートの検索を行っているが、評価式の中で推定値を用いてルート検索を行っているため、中継ノードの状態によっては現実との差が発生し、最適なルートを検索ができないという問題がある。
【0006】また、行列式を用いてルート検索を行っている公開昭63−174446号公報と公開昭62−168267号についても、複雑なネットワーク構成の場合では行列式で充分表現しきれない部分があり同様な問題がある。
【0007】更に、公開昭58−166849号公報でも、エリア番号管理テーブルとノード番号管理テーブルを作成する際、例えばこのノードを何れのエリアに入れたら良いのか、ネットワークが複雑な構成であると難かしい場合があり、適確なテーブルを作成することが困難である。また、ノードの追加、故障等によるネットワーク構成の変化にすみやかに対処できない問題がある。
【0008】このように従来例においては、ルート決定に使用されるテーブルあるいは計算式がネットワーク構成が複雑になると、現実とのかい離が発生して適確なルート検索ができない、またノード構成に変化があった場合にこれに直ちに対応することができないという問題がある。
【0009】
【課題を解決するための手段】本発明のノード間ルート検索方法は、複数のノードから構成されるネットワークの任意の2ノード間で時間的に最短の通信ルートを求めるルート検索方法において、検索を行う検索元ノードと検索先の検索先ノードとを結ぶ総てのルート上にある各中継ノードの中の前記検索元ノードに隣接する各前記中継ノードに対し検索元ノード番号および検索先ノード番号を含むルート検索フレーム信号を送信し、前記ルート検索フレーム信号を受信した各前記中継ノードは時間的に最初に受信した方路を復路の送信方路としてルーティングテーブルに保持すると同時に前記ルート検索フレーム信号を次の前記中継ノードに転送し、次の各前記中継ノードは先の前記中継ノードと同様処理を実行し前記ルート検索フレーム信号を次の前記中継ノードに転送し、次以降の前記中継ノードも順次同様処理を実行して行き、前記検索先ノードに至り転送されて来た前記ルート検索フレーム信号を時間的に最初に受信した方路を復路の送信方路としこれをルーティングテーブルに保持すると同時にこの送信方路に対し前記ルート検索フレーム信号と同一構成の応答信号を返送し、この応答信号を受信した前記中継ノードはこの受信方路を往路の送信方路として前記ルーティングテーブルに保持すると同時に前記応答信号を前記ルーティングテーブルに保持された復路の送信方路に転送し、次以降の前記中継ノードも順次同様処理を実行して行き、前記検索元ノードに至り前記中継ノードから転送されて来た前記応答信号を受信しこの受信方路を往路の送信方路としてルーティングテーブルに保持し、このようにして各ノードが保持した前記ルーティングテーブルにより通信ルートを決定している。
【0010】
【実施例】次に、本発明の一実施例について図面を参照して説明する。図1は、本実施例の構成を示すブロック図である。本図は説明を簡単に分り易くするため単純なネットワーク例とし、4つのノード1〜4による構成の場合を示す。アルファベット小文字は各ノードの通信方路を示す。
【0011】図2は各ノードが保持するルーティングテーブルのフォーマット図、図3はルート検索フレーム信号の構成図である。次に図1〜図4を参照してノード1からノード3への通信ルートを検索する方法を説明する。
【0012】先ず、検索元ノードであるノード1がノード2,4へ図3に示す検索フレーム信号を送信する。このルート検索フレーム信号は主信号に先立って送信され、図3に図示するようにフレーム識別子とこの信号の検索元ノードを識別する検索元ノード番号と検索先ノードを識別する検索先ノード番号とこの検索信号の番号を識別するフレーム識別番号とで構成されている。
【0013】このルート検索フレーム信号をノード2は方路bから受信し、ノード4は方路gから受信する。これによりルーティングテーブルには図4(a)に示すようにノード2の送信方路に方路bが、ノード4の送信方路には方路gがそれぞれ保持される。この場合方路b,gは受信方路であるが、復路での送信方路となり、これがここで保持される。
【0014】次にノード2は方路c,jへ、ノード4は方路f,iへルート検索フレーム信号を転送する。ノード2は方路jからノード4は方路iから再び受信するが、フレーム識別番号が先ほど受信したフレームと同じであるためこのフレーム信号を廃棄する。
【0015】検索先ノードであるノード3はノード4からのフレーム信号を方路eから、またノード2からのフレーム信号を方路dから受信する。ノード3は先に受信したフレーム信号の方路eを図4(b)に示すルーティングテーブルに保持し、この後受信するフレーム信号は廃棄する。ここでは、方路eからの受信が速かったとした例である。
【0016】ノード3はノード1への応答フレーム信号を方路eへ送信する。応答フレーム信号はフレーム検索フレーム信号と同じ構成である。ノード4は方路fから応答フレーム信号を受信する。これによりノード3への往路の送信方路を方路fと判断し、図4(c)に示すルーティングテーブルの送信方路に方路fを保持する。又、ルーティングテーブルを検索し、ルート応答フレーム信号を先に保持した方路gへ転送する。
【0017】ノード1は方路hから応答フレーム信号を受信する。これによりノード3への往路の送信方路は方路hと判断し、図4(d)に示すルーティングテーブルの送信方路に方路hを保持する。
【0018】これにより、ノード1からノード3へのルート検索は終了し、各ルーティングテーブルは、図4(d)となり、方路h−g−f−eのルートが設定される。
【0019】このルーティングテーブルに保持された設定ルートは時間的に最短のルートである。これ以後のノード1,3回の通信は、主信号のデータ列前頭部に配置されたルーティング信号により、各ノードに保持されたルーティングテーブルが参照されて送信方路が自動的に決定される。
【0020】尚、実際のネットワークではノード数はもっと多く複雑なネットワークを構成するが、この場合もあらかじめ通信を行う2ノード間の総てについて、上記方法でルーティングテーブルを作成し、これを各ノードが保持することにより、通信に先立って最短ルートが自動的に設定される。
【0021】
【発明の効果】以上説明したように、本発明のノード間のルート検索方法は、ルート検索フレーム信号を用いて多ルートの中で常に時間的に速く着信するルートを選択して行きルートを決定しているので、実際のルートで正確に最短のルートを決定することができ、またノード構成の変更があった場合も直ちに最短ルートを再設定できるという効果がある。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013