(57)【特許請求の範囲】
【請求項１】
パケット伝送ネットワークを介して出発ノードから宛先ノードに向けてパケットを送信する場合に、各ノードのルーチングテーブルをアントネットアルゴリズムに基づき学習により構築するとともに、上記出発ノードおよび該出発ノードから発せられたパケットを受け取ったノードは該ルーチングテーブルを用いて該パケットをルーチングする経路制御方法において、
該複数のノードが隣接ノードを知らない初期状態の場合に、パケット送出に先立ち、各ノードは自ノードのＩＤを含んだ『隣接識別蟻』を全リンクに送出し、該『隣接識別蟻』を受け取った隣接ノードは、該『隣接識別蟻』の中のノードＩＤを見ることにより、該リンクにより隣接するノードを識別し、
各隣接ノードは、該隣接ノードのルーチングテーブルに自分に隣接するノードのＩＤを書き込むことを特徴とするパケット伝送ネットワークの経路制御方法。
【請求項２】
請求項１に記載のパケット伝送ネットワークの経路制御方法において、
出発ノードまたは出発ノードから発せられたパケットを受け取ったノードのルーチングテーブルに、宛先ノードＩＤの記録がない場合には、
該ノードは、該パケットを送出するに先立ち、該宛先ノードＩＤを含む『中継ノード探索蟻』を該パケットが通ったリンク以外の全てのリンクに送出し、
該『中継ノード探索蟻』を受け取ったノードは、該宛先ノードＩＤを見ることにより、自分のルーチングテーブル中に該宛先ノードＩＤがないときには、改めて該『中継ノード探索蟻』を該『中継ノード探索蟻』が通ったリンク以外の全リンクに送出し、
自分のルーチングテーブル中に該宛先ノードＩＤがあるときには、該宛先ノードＩＤを持っているノードの情報と、該『中継ノード探索蟻』を送出したノードから、該宛先ノードＩＤを持っているノードまでの遅延情報と、を持った該『中継ノード探索蟻』を、通過してきた元の経路を通って該『中継ノード探索蟻』を送出したノードまで送り返すことを特徴とするパケット伝送ネットワークの経路制御方法。
【請求項３】
請求項１または２に記載のパケット伝送ネットワークの経路制御方法の処理ステップをプログラムに変換し、変換されたプログラムを記録媒体に格納することを特徴としたプログラム記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、パケット伝送ネットワークの中継などに利用される経路制御方法に関し、特に隣接ノードを識別する蟻、中継ノードの探索を行う蟻を導入したアントネットアルゴリズムを用いる経路制御方法およびそのプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
従来より、蟻エージェントを用いたアントネットアルゴリズムに関する提案としては、例えば“Ｍｏｂｉｌｅ  Ａｇｅｎｔｓ  ｆｏｒ  Ａｄａｐｔｉｖｅ  Ｒｏｕｔｉｎｇ”（Ｇｉａｎｎｉ  Ｄｉ  Ｃａｒｏ  ａｎｄ  Ｍａｒｃｏ  Ｄｏｒｉｇｏ，ｉｎ  Ｐｒｏｃ．ｏｆ  ｔｈｅ  ３１ｓｔ  Ｈａｗａｉｉ  Ｉｎｔ’１Ｃｏｎｆ．ｏｎ  Ｓｙｓｔｅｍｓ  Ｓｃｉｅｎｃｅｓ，ｐｐ．６−９，Ｊａｎ．，１９９８）では、アントネットアルゴリズムを提案している。また、特願平１０−２８５４５８号明細書および図面に記載された『ルータ装置の制御方法及び制御装置』（ＡＴＲ）では、アントネットアルゴリズムに基づくルータ装置において、ルーチングロックを回避する手法を提案している。
上記の従来技術においては、予め決まったネットワーク・トポロジ（網形態）に対するアルゴリズムを提案しているが、複数のノードが隣接ノードを知らない初期状態の場合には、隣接ノードのルーチングテーブルへの登録方法が明らかではなかった。また、経路を知らないノードにパケットを伝送する方法も、明らかではなかった。
【０００３】
【発明が解決しようとする課題】
前述のように、従来の方法では、パケット伝送ネットワークを介して出発ノードから宛先ノードに向けてパケットを送信する場合に、各ノードのルーチングテーブルをアントネットアルゴリズムに基づいて学習により構築することにより、出発ノードおよび出発ノードから発せられたパケットを受け取ったノードは上記ルーチングテーブルを参照して、そのパケットをルーチングするが、これは予め決まったネットワーク・トポロジの場合であって、任意のノードが隣接ノードを知らない初期状態では、隣接ノードに関する情報をルーチングテーブルへ登録する方法が明らかではなく、またルーチングテーブルにエントリのない宛先ノードへパケットを伝送する方法も明らかではなかった。
【０００４】
そこで、本発明の目的は、これら従来の課題を解決し、ルーチングテーブルをアントネットアルゴリズムに基づき学習により構築し、出発ノードおよび出発ノードから発せられたパケットを受け取ったノードがそのルーチングテーブルを用いて該パケットをルーチングする場合に、各ノードが隣接ノードを知らない初期状態から徐々にルーチングテーブルを生成することができ、かつ出発ノード、または出発ノードから発せられたパケットを受け取ったノードが、自己のルーチングテーブルにエントリのない宛先ノードへもパケット伝送を行うことが可能なパケット伝送ネットワークの経路制御方法を提供することにある。
【０００５】
【課題を解決するための手段】
上記目的を達成するため、本発明のパケット伝送ネットワークの経路制御方法は、▲１▼パケット伝送ネットワークを介して出発ノードから宛先ノードに向けてパケットを送信する場合に、各ノードのルーチングテーブルをアントネットアルゴリズムに基づき学習により構築するとともに、上記出発ノードおよび該出発ノードから発せられたパケットを受け取ったノードは該ルーチングテーブルを用いて該パケットをルーチングする経路制御方法において、
該複数のノードが隣接ノードを知らない初期状態の場合に、各ノードは自ノードのＩＤを含んだ『隣接識別蟻』を全リンクに送出し、
かつ、該『隣接識別蟻』を受け取った隣接ノードは、該『隣接識別蟻』の中のノードＩＤを見ることにより、該リンクにより隣接するノードが何かを識別し、
各隣接ノードは、該隣接ノードのルーチングテーブルに自分に隣接するノードのＩＤを書き込むことを特徴としている（請求項１）。
これにより、パケット伝送ネットワークを構成する各ノードが隣接ノードを知らない初期状態に、各ノードが自ノードのＩＤを含んだ『隣接識別蟻』を全リンクに送出することで、隣接ノード双方において相手を認識することができ、その結果、ノードの追加などのトポロジ変化に対応することができる。
【０００６】
また、▲２▼出発ノードまたは出発ノードから発せられたパケットを受け取ったノードのルーチングテーブルに、宛先ノードＩＤの記録がない場合には、
該ノードは、該宛先ノードＩＤを含む『中継ノード探索蟻』を該パケットが通ったリンク以外の全てのリンクに送出し、
該『中継ノード探索蟻』を受け取ったノードは、該宛先ノードＩＤを見ることにより、自分のルーチングテーブル中に該宛先ノードＩＤがないときには、改めて該『中継ノード探索蟻』を該『中継ノード探索蟻』が通ったリンク以外の全リンクに送出し、
自分のルーチングテーブル中に該宛先ノードＩＤがあるときには、該宛先ノードＩＤを持っているノードの情報と、該『中継ノード探索蟻』を送出したノードから、該宛先ノードＩＤを持っているノードまでの遅延情報と、を持った該『中継ノード探索蟻』を、もとの来た経路を通って該『中継ノード探索蟻』を送出したノードまで送り返すことも特徴としている（請求項２）。
これにより、各ノードが予め全てのノードの情報を持つ必要がなく、パケット伝送の必要な際に宛先のエントリを作成することができる。
▲３▼上記▲１▼または▲２▼に記載の処理ステップをプログラムに変換し、そのプログラムを記録媒体に格納することも特徴としている。
これにより、任意のコンピュータに記録媒体を実装することで、本発明を容易に実現できる。
【０００７】
【発明の実施の形態】
以下、本発明の実施例を、図面により詳細に説明する。
図１は、各蟻のパケット構成例を示す図である。
図１（ａ）は『隣接識別蟻』のパケットのデータ内容を示しており、蟻識別子１０と送信元ノードのＩＤ１１が記述されている。図１（ｂ）は『隣接識別蟻』を受け取ったノードが返送する『応答蟻』のパケットのデータ内容を示しており、これも蟻識別子１０（前記蟻識別子とは異なる値）と送信元ノード（隣接識別蟻を受け取ったノード）のＩＤ１１が記述されている。図１（ｃ）は『中継ノード探索蟻』のパケットのデータ内容を示しており、蟻識別子１０（他の２つの蟻識別子と異なる値）と送信元ノードのＩＤ１１と、宛先ノードのＩＤ１２と、シーケンス番号１３と、スタックデータとして、通過ノードのＩＤ１４とトリップ時間１５（１つ前のノードから『通過ノード』までの伝搬遅延時間）と、その他のデータ１６（通過ノード数（中継ノードも含む）に宛先ノード（１つ）を加えた分のスタックデータ）とが記述されている。シーケンス番号１３は、異なる『中継ノード探索蟻』を識別するために送出元が付ける。なお、『中継ノード探索蟻』において、従来の蟻と比較して太枠内のシーケンス番号１３が本発明で新たに必要な項目である。
本発明においては、『隣接識別蟻』を導入することにより、隣接ノードの認識ができるので、ネットワークトポロジ（網形態）の変更、つまりノードの追加にも対応可能となる。また、『中継ノード探索蟻』を導入することにより、予め全てのノード情報を持たなくても、パケット伝送に必要な宛先エントリの作成が可能となる。
【０００８】
（第１の実施例）
図２は、本発明の第１の実施例（請求項１に対応）を示すリンクアップ（応答蟻無し）時の各ノードの処理フローチャートである。
ここで、応答蟻無しとは、リンクの両端ノード（出発ノード）でリンクアップ検知が可能な場合に限定される。
先ず、ノードが立ち上がったならば、またはリンクアップしたならば（ステップ１０１）、リンクの両端のノードは隣接ノードを知るために、自ノードＩＤを含む『隣接識別蟻』を該リンクに送出する（ステップ１０２）。隣接ノードからの『隣接識別蟻』を受け取ったならば（ステップ１０３）、他の処理に比べて最優先で出発ノードＩＤを自分のルーチングテーブルに反映する。また、本蟻の送受信が終了しないうちは、本リンクを使用した蟻やデータパケットの送受信は行わない。各隣接ノードは、受信した『隣接識別蟻』の出発ノードＩＤのノードに対する確率を、本蟻が受信されたリンクに対して１／（受信したリンク数）とし、他のリンクを０とすることで（ステップ１０４）、リセット（リターン）する（ステップ１０５）。
【０００９】
図３（ａ）は、本発明の第１の実施例（請求項１に対応）を示すリンクアップ（応答蟻有り）時の処理フローチャートである。
先ず、ノードが立ち上がったならば、またはリンクアップしたならば（ステップ１１１）、リンクアップを検知したノードは隣接ノードを知るために、自ノードＩＤを含む『隣接識別蟻』を該リンクに送出する（ステップ１１２）。隣接ノードからの『隣接識別蟻』または『応答蟻』を受け取ったならば（ステップ１１４）、他の処理に比べて最優先で出発ノードＩＤを自分のルーチングテーブルに反映する。また、本蟻の送受信が終了しないうちは、本リンクを使用した蟻やデータパケットの送受信は行わない。そして、受信した『隣接識別蟻』または『応答蟻』の出発ノードＩＤに対する確率を、本蟻が受信されたリンクに対して１／（受信したリンク数）とし、他のリンクを０とすることで（ステップ１１４）、受け取った蟻が『応答蟻』であればリセット（リターン）する（ステップ１１９）。一方、受け取った蟻が『隣接識別蟻』であれば（ステップ１１５）、それに対して自ノードＩＤを含んだ『応答蟻』を返送する（ステップ１１６）。そして、リセット（リターン）する（ステップ１１９）。
【００１０】
図３（ｂ）は、応答蟻生処理のフローチャートである。
隣接ノードがリンクアップを検知しない場合には、『応答蟻生成処理』を行って、隣接ノードに対するエントリを生成し、応答蟻を返送する。
すなわち、ノードが『隣接識別蟻』を受信したならば（ステップ１５１）、該ノードに対する確率は蟻を受信したリンクに対して１／（受信したリンク数）とし、他を０とする（ステップ１５２）。次に、自ノードＩＤを含んだ応答蟻を返送する（ステップ１５３）。そして、リセット（リターン）する（ステップ１５４）。
【００１１】
図４（１）（２）は、図２，３におけるリンクアップ時の処理例を示す図である。
ここで、図中のルーチングテーブルのエントリの記載方法について説明すると、ａ，ｎ  Ｐは、リンクｎに対する宛先ａ宛のパケットの送出確率Ｐを意味している。
図４（１）は、図２に示した『応答蟻』無しの場合の処理である。ノードｂとノードｄ間、およびノードｃとノードｄ間において、リンクアップによって『隣接識別蟻』が双方から送出される場合を示している。ノードｂ，ｄ、ノードｃ，ｄの双方から『隣接識別蟻』が送出され、それを受け取ったノードは、ルーチングテーブルにその蟻内に示されたノードＩＤを追加し、かつリンク毎の送出確率を設定する。ここでは、『隣接識別蟻』を受け取ったリンクに対する確率を１．０、他の合計を０．０とする。また、他のノードを宛先とする該リンクに対する送出確率を設定する。ここでは、０．０とする。具体的な確率値は、実装時に変更可能とする。
この場合のノードｂのルーチングテーブルには、最初は宛先ａ，リンク２の確率が１．０、宛先ｃ，リンク２の確率が１．０、のみ登録されていたが、ノードｄからの『隣接識別蟻』のノードＩＤの登録により、宛先ｄ，リンク１の確率が１．０、宛先ｄ，リンク２の確率が０．０、宛先ａ，リンク１の確率が０．０、宛先ｃ，リンク１の確率も０．０が追加されている。ノードｃ、ノードｄのルーチングテーブルについても、ノードｂと全く同じようにして、受け取った『隣接識別蟻』からノードＩＤと送出確率を設定する。
【００１２】
図４（２）は、図３に示した『応答蟻』有りの場合の処理である。立ち上がったノードｄから『隣接識別蟻』がノードｂ側とノードｃ側の双方に送出され、それを受け取ったノードｂ，ｃからは、それに対して自ノードＩＤを含んだ『応答蟻』を返送する。他の処理は図４（１）と同じである。なお、本実施例では、リンクの片側のノードｄのみがリンクアップ検知が可能であるため、ノードｄからのみ『隣接識別蟻』を送出したが、変形例として、双方から『隣接識別蟻』を送出し、それに対して双方から『応答蟻』を返送することも可能である。
図４（１）（２）のルーチングテーブルから明らかなように、『応答蟻』有りと無しとではテーブルは全く同じ内容になる。
【００１３】
（第２の実施例）
図５は、本発明の第２の実施例（請求項２に対応）を示す新規経路生成に関する処理フローチャートである。
図５（ａ）は『中継ノード探索蟻』の前進蟻の処理を示し、図５（ｂ）は新規経路生成を必要とするノードの処理を示し、図５（ｃ）『中継ノード探索蟻』の後退蟻の処理を示す。なお、中継ノードとは、通過ノードとして前進蟻が到着したノードで、最初に宛先ノードへの経路を知っているノードのことである。
前進蟻の処理では、『中継ノード探索蟻』を受け取ったノードは、宛先ノードへの経路を持っていないことを知ったとき、それが通ってきたリンク以外の全リンクに『中継ノード探索蟻』の前進蟻を送出することで、中継ノードを検知する。また、後退蟻の処理では、中継ノードが、いま来た経路を出発ノードに至るまで『中継ノード探索蟻』の後退蟻を送出する。
先ず、図５（ｂ）における『新規経路生成の処理』では、データパケットの出発ノード、または出発ノードから発せられた該パケットを受け取ったノードが、経路を知らない宛先ノードへ、または確率０のノードへ該パケットを送る場合には（ステップ１３１）、パケットを時間ｔ（０より大きな値、必要に応じて決める）の間、一旦、キューイングしておき、自分のＩＤ（送信元ノードＩＤ）と宛先ＩＤ、さらにシーケンス番号を載せて宛先へのパケットを中継するノードを探索する蟻『中継ノード探索蟻』をパケットが到着したリンク以外の全てのリンクへ送出する（ステップ１３２）。以下、前進蟻の処理になる。
【００１４】
前進蟻の処理では、図５（ａ）に示すように、任意のノードが『中継ノード探索蟻』の前進蟻を受信したならば（ステップ１２１）、同一の送信元、シーケンス番号の蟻を既に受信したか否かを判別し（ステップ１２２）、受信していれば、今受信した蟻を捨てる（ステップ１２３）。一方、受信していなければ、自分のルーチングテーブルに送信元ノードＩＤがなければ、それを自分のルーチングテーブルに追加する（確率は１／リンク数）。また、送信元とシーケンス番号のペアでその蟻を覚えておくこととする（ステップ１２４）。これにより、ループを回避すると共に、トポロジ変更後の同じ宛先への蟻にも対処可能とする。
『中継ノード探索蟻』を受け取ったノードは、自分のルーチングテーブルに宛先ＩＤへの経路を持っているか否かを調べる（ステップ１２５）。しかし、持っている場合には、ソースリンク以外で、送出確率が０よりも大きなリンクがあれば（ステップ１２６）、従来の前進蟻の処理に加えて、そのノードが持つ宛先ＩＤと、宛先ＩＤへの伝搬遅延の平均値を載せて、『中継ノード探索蟻』に対する後退蟻を、前進蟻の通過ノードに沿って送出する（ステップ１２７）。また、自分のルーチングテーブルに宛先ＩＤへの経路がないか、あるいはソースリンク以外への送出確率が０であるならば、『中継ノード探索蟻』をコピーしてソースリンク以外の全リンクに送出する（ステップ１２８）。そして、リセット（リターン）する（ステップ１２９）。
【００１５】
一方、図５（ｂ）において、データを時間ｔの間キューイングして、『中継ノード探索蟻』をデータが到着したリンク以外の全リンクに送出した後（ステップ１３２）、時間ｔの間に上記送信元ノードが後退蟻を受け取ったならば（ステップ１３３）、その通過ノードおよび宛先ノードの中で自分のルーチングテーブルにないノードＩＤをルーチングテーブルに反映する（ステップ１３４）。ルーチングテーブルは、この後退蟻が到着する前を等確率であったと仮定して、通常の伝搬遅延情報を更新した後、確率を更新する。そして、ルーチングテーブルに従って、データパケットを送出する（ステップ１３６）。一方、時間ｔの間に後退蟻を受け取らなかった場合には（ステップ１３３）、キューイングされていたデータパケットを破棄する（ステップ１３５）。そして、リセット（リターン）する（ステップ１３７）。
また、図５（ｃ）に示すように、送信元ノード以外のノードが『中継ノード探索蟻』の後退蟻を受信したならば（ステップ１４１）、従来の処理に加えて、その通過ノードおよび宛先ノードの中で自分のルーチングテーブルにないノードＩＤを自分のルーチングテーブルに反映する（ステップ１４２）。ルーチングテーブルは、この後退蟻が到着する前を等確率であったと仮定して、従来手法の伝搬遅延情報を更新した後に、確率を更新する。そして、リセット（リターン）する（ステップ１４３）。
【００１６】
図６および図７は、図５における新規経路生成の例を示す説明図である。
ここで、図６，図７中の蟻の持つ情報を説明すると、〔ｊ  （Ｔｉ，ｊ）〕は、ノードｊのノードＩＤと蟻が通った際のノードｉからノードｊへの遅延を示しており、〔ａ，ｂ，ｓｅｑ〕は、ａからｂ宛の蟻でシーケンス番号ｓｅｑを持つ、ことを示している。
図６、図７では、（１）から（６）へ処理が流れている。送信元ノードｆが宛先ノードａへデータパケットを送りたい場合で、かつａがｆへの経路を持っていない場合には、該パケットを時間ｔだけキューイングして（以上、図６（１）参照）、『中継ノード探索蟻』を全リンクへ送出する。この場合の送信元ノードｆは、データパケットを生成するノードと考えているが、別ノードで生成されたデータパケットを転送途中で受け取ったノードであってもよい。後者の場合には、データパケットが到着したリンク以外へ蟻エージェントを送出する（以上、図６（２）参照）。
【００１７】
該『中継ノード探索蟻』は送信元ノードＩＤｆ、宛先ＩＤａ、シーケンス番号ｓｅｑを持って送信元ノードｆを出発し、途中ノードｄ，ｅにおいて、ノードＩＤと該蟻の伝搬遅延を持って、さらにノードｂ、ｃに到達する（以上、図６（３）参照）。
ノードｂ，ｃは宛先ノードａへの経路を持っており、かつソースリンク２以外への確率が０より大きいので（各ルーチングテーブルのａ，１  １．０参照）、それぞれｂ，ｃが中継ノードとなる。そこで、ｂ，ｃにおいては、ｄからｂ、およびｅからｃまでの実測の伝搬遅延だけでなく、ｂ，ｃからａへの平均伝搬遅延を持って、送信元ノードｆへ従来のアントネットの後退蟻と同一の方法（中継ノード探索蟻の持っている経路の通りに戻る）で戻る。図（４）に示すように、蟻の持つ情報は、ａ  Ｔｂ，ａ、ｂ  Ｔｄ，ｂ、ｄ  Ｔｆ，ｄ、ｆ，ａ，ｓｅｑおよびａ  Ｔｃ，ａ、ｃ  Ｔｅ，ｃ、ｅＴｆ，ｅ、ｆ，ａ，ｓｅｑである（以上、図７（４）参照）。
【００１８】
後退蟻が中継ノードのｂ，ｃからそれぞれ送信元ノードｆに戻る際には、途中ノードｄ，ｅはａへの宛先を持っていないので、それをルーチングテーブルに追加する。その際に、この蟻を受け取る前を等確率（この場合には、各リンクとも０．５）と考えて確率を計算する（以上、図７（５）参照）。すなわち、ノードｄのルーチングテーブルには、ａ，１  ｉ、ａ，２  ｊが追加され、ノードｅのルーチングテーブルには、ａ，１  ｑ、ａ，２  ｒが追加される。
ノードｆに後退蟻が到着したならば、途中ノードと同様にして、ルーチングテーブルに自分の知らないノードＩＤを追加する。どちらか一方の後退蟻が先に送信元ノードｆに到着した時点で、送信元ノードｆはデータパケットを各リンクへ送出確率に従って送出する（以上、図７（６）参照）。ここでは、送信元ノードｆのルーチングテーブルには、ｂ，１  ｋ、ｂ，２  ｌ、ｃ，１  ｍ、ｃ，２  ｎ、ａ，１  ｏ、ａ，２  ｐが追加される。
【００１９】
図２のリンクアップ（応答蟻無し）時の処理フロー、図３のリンクアップ（応答蟻有り）時の処理フロー、および図５の新規経路生成に関する処理フローの各ステップをプログラムに変換し、変換されたプログラムをＣＤ−ＲＯＭなどの記録媒体に格納しておけば、ネットワーク上の任意のノードのコンピュータに上記記録媒体を装着してプログラムを実行させることにより、本発明の経路制御方法を容易に実現できる。また、媒体を装着したコンピュータからネットワークを介して他の任意のコンピュータにプログラムをダウンロードすることによっても、本発明の方法を容易に実現できる。
【００２０】
【発明の効果】
以上説明したように、本発明によれば、パケット伝送ネットワークを介して出発ノードから宛先ノードに向けてパケットを送信する場合、各ノードのルーチングテーブルを蟻エージェントを用いてアントネットアルゴリズムに基づき学習により構築するとともに、出発ノードおよび出発ノードから発せられたパケットを受け取ったノードは該ルーチングテーブルを用いて該パケットをルーチングする際に、これに先立って、パケット伝送ネットワークを構成する各ノードが隣接ノードを知らない初期状態であるとき、各ノードが自ノードのＩＤを含んだ『隣接識別蟻』を全リンクに送出することで、隣接ノード双方で相手を認識できるので、ノードの追加などのトポロジ変化に対応することができる。また、『中継ノード探索蟻』による宛先ノードに対する中継ノードの探索により、各ノードが予め全てのノードの情報を持つ必要がなく、パケット伝送の必要な際に宛先エントリを作成することができる。
【図面の簡単な説明】
【図１】本発明で利用する『隣接識別蟻』『応答蟻』および『中継ノード探索蟻』のデータ構成図である。
【図２】本発明の第１の実施例を示すリンクアップ（応答無し）時の処理フローチャートである。
【図３】本発明の第１の実施例を示すリンクアップ（応答有リ）時の処理フローチャートである。
【図４】図２、図３におけるリンクアップ時の処理例を示す説明図である。
【図５】本発明の第２の実施例を示す新規経路生成に関する処理フローチャートである。
【図６】本発明の第２の実施例を示す新規経路生成の手順（１〜３）説明図である。
【図７】本発明の第２の実施例を示す新規経路生成の手順（４〜６）説明図である。
【符号の説明】
１０…蟻識別子、１１…送信元ノードのＩＤなどの情報、
１２…宛先ノードのＩＤなどの情報、１３…シーケンス番号、
１４…通過ノード、１５…トリップ時間、１６…その他の情報、
ａ〜ｆ…ノード、１，２はリンク番号。
【図１】
0003575682.tif 000002
【図２】
0003575682.tif 000003
【図３】
0003575682.tif 000004
【図４】
0003575682.tif 000005
【図５】
0003575682.tif 000006
【図６】
0003575682.tif 000007
【図７】
0003575682.tif 000008