(57)【要約】      （修正有）【課題】ネットワークのある地点(端末もしくはルータ等)からあるリンクをパケットが通過することが可能か不可能かを判定場合に、そのパケットがそのリンクを通過できるか否かを迅速に判定することが可能である。【解決手段】パケットに記された宛先に基づきパケットの送出方向が決定されるネットワークに接続された端末（２）から送出されるパケットが、ネットワークのリンク（５）を通過することができるか否かを判定する。ここにおいて、リンク（５）の端点となるパケット中継器（３ｎ−１、３ｎ）（Ｒ２、Ｒ３）へそれぞれ到達する２つのパケットが、それぞれリンク（５）のいずれかの端点に到達する前に通過するパケット中継器（３１）を特定する。そして、次に転送されるパケット中継器（３２）が、２つのパケットで異なる場合に、端末（２）から送出したパケットはリンク（５）を通過しないと判定する。【選択図】図１
2008113278.tif 000002
【特許請求の範囲】
【請求項１】
パケットに記された宛先に基づき前記パケットの送出方向が決定されるネットワークに接続された端末から送出される前記パケットが、前記ネットワークのリンクを通過することができるか否かを判定するネットワークリンク通過判定方法であって、
前記リンクの端点となるパケット中継器へそれぞれ到達する２つのパケットが、それぞれ前記リンクのいずれかの端点に到達する前に通過するパケット中継器において、
次に転送されるパケット中継器が前記２つのパケットで異なる場合に、前記端末から送出したパケットは前記リンクを通過しないと判定することを特徴とする
ネットワークリンク通過判定方法。
【請求項２】
請求項１に記載のネットワークリンク通過判定方法において、
前記リンクのいずれかの端点に到達する前に通過する全てのパケット中継器において、
前記２つのパケットが次に転送されるパケット中継器が前記２つのパケットで等しい場合に、前記端末から送出したパケットは前記リンクを通過する判定することを特徴とする
ネットワークリンク通過判定方法。
【請求項３】
請求項２に記載のネットワークリンク通過判定方法において、
前記リンクの２つの端点のうち、端末から見た経路で、先に到達するパケット中継器に接続された端点を始点とよび、後に到達する端点を終点としたときに、
あるリンクの通過／不通過を判定し、
前記リンクについて、パケットを通過させることが可能と判定した場合、
前記リンクの終点が接続されるパケット中継器に接続された未判定のリンクを新たな判定対象リンクとし、
この際、先の判定で作成した宛先集合をこの判定に引き継ぎ、
先に判定されたリンクの始点となるパケット中継器において、先に判定されたリンクの終点が接続されるパケット中継器以外に転送される宛先群を宛先集合に加え、
この宛先集合を参照し、新たな判定対象リンクの終点となるアドレスが宛先集合に含まれた場合に、前記端末から新たな判定対象リンクを通過するパケットは送出することはできないと判定し、
また、この宛先集合を参照し、新たな判定対象リンクの終点となるアドレスが宛先集合に含まれない場合に、前記端末から新たな判定対象リンクを通過するパケットは送出することはできると判定することを特徴とする
ネットワークリンク通過判定方法。
【請求項４】
請求項１または２に記載のネットワークリンク通過判定方法において、
前記２つのパケットの宛先として、前記リンクの端点となるパケット中継器が持つアドレスをそれぞれ利用することを特徴とする
ネットワークリンク通過判定方法。
【請求項５】
請求項１に記載のネットワークリンク通過判定方法において、
前記端末から前記リンクの端点となるパケット中継器へ到達するパケットが前記リンクの端点に到達する前に通過するパケット中継器において、
前記リンクの一つの端点となるパケット中継器へ到達するパケットが次に転送されるパケット中継器Ｈを調査し、このパケット中継器Ｈに転送されない宛先集合を作成し、
前記宛先集合に前記リンクのもう一つの端点となる宛先が含まれた場合、前記端末から送出したパケットは前記リンクを通過しないと判定することを特徴とする
ネットワークリンク通過判定方法。
【請求項６】
請求項５に記載のネットワークリンク通過判定方法において、
前記端末から前記リンクの端点となるパケット中継器へ到達するパケットが前記リンクの端点に到達する前に通過する全てのパケット中継器において、
前記リンクの一つの端点となるパケット中継器へ到達するパケットが次に転送されるパケット中継器Ｈを調査し、このパケット中継器Ｈに転送されない宛先集合を作成し、
前記宛先集合に前記リンクのもう一つの端点となる宛先が含まれない場合、前記端末から送出したパケットは前記リンクを通過すると判定することを特徴とする
ネットワークリンク通過判定方法。
【請求項７】
請求項６に記載のネットワークリンク通過判定方法において、
前記リンクの２つの端点のうち、端末から見た経路で、先に到達するパケット中継器に接続された端点を始点とよび、後に到達する端点を終点としたときに、
あるリンクの通過／不通過を判定し、
前記リンクについて、パケットを通過させることが可能と判定した場合、
前記リンクの終点が接続されるパケット中継器に接続された未判定のリンクを新たな判定対象リンクとし、
この際、先の判定で作成した宛先集合をこの判定に引き継ぎ、
先に判定されたリンクの始点となるパケット中継器において、先に判定されたリンクの終点が接続されるパケット中継器以外に転送される宛先群を宛先集合に加え、
この宛先集合を参照し、新たな判定対象リンクの終点となるアドレスが宛先集合に含まれた場合に、前記端末から新たな判定対象リンクを通過するパケットは送出することはできないと判定し、
また、この宛先集合を参照し、新たな判定対象リンクの終点となるアドレスが宛先集合に含まれない場合に、前記端末から新たな判定対象リンクを通過するパケットは送出することはできると判定することを特徴とする
ネットワークリンク通過判定方法。
【請求項８】
請求項１〜７の何れか一項に記載のネットワークリンク通過判定方法を実施するネットワークリンク通過判定装置。
【請求項９】
請求項１〜７の何れか一項に記載のネットワークリンク通過判定方法を実施するネットワークリンク通過判定プログラム。
【請求項１０】
ネットワークを介して送受信されるパケットが前記ネットワークを構成するリンクを通過するか否かを判定するネットワークリンク通過判定装置であって、
ルーティングテーブルを保持し前記パケットの入出力制御するパケット入出力制御部と、
前記ルーティングテーブルに基づいて判定対象のリンクを特定し、前記リンクの一端を示す第１アドレスを宛先とする第１パケットと、前記リンクの他端を示す第２アドレスを宛先とする第２パケットとを生成するルーティングテーブル解析部と、
前記第１パケットと前記第２パケットとを中継する第１中継器に保持されている第１中継器ルーティングテーブルを読み出すルーティングテーブル取得部と、
前記第１中継器から前記第１アドレスまでの経路に備えられた第２中継器のアドレスを保持する探査方向記憶部と
を具備し、
前記ルーティングテーブル解析部は、
前記第１パケットが前記第２中継器に転送されるときに、前記第２パケットが前記第２中継器のアドレスと異なるアドレスに転送されるか否かに基づいて、前記パケットが前記リンクを通過するか否かを判定する
ネットワークリンク通過判定装置。
【請求項１１】
請求項１０に記載のネットワークリンク通過判定装置において、さらに、
前記第１中継器に接続される複数のノードのアドレスをアドレス集合として保持する別方向アドレス集合記憶部を具備し、
前記ルーティングテーブル解析部は、
前記第１中継器ルーティングテーブルを参照して、前記第２中継器のアドレスを第２中継器アドレスとして特定し、前記第２中継器アドレスを前記探査方向記憶部に格納し、
前記第２中継器アドレス以外のアドレスを前記別方向アドレス集合記憶部に格納し、
前記別方向アドレス集合記憶部に前記第２アドレスが含まれていないとき、前記パケットが前記リンクを通過すると判定する
ネットワークリンク通過判定装置。
【請求項１２】
請求項１１に記載のネットワークリンク通過判定装置において、
前記ルーティングテーブル解析部は、
前記リンクの前記一端に接続されるリンク第１中継器のアドレスを前記第１アドレスとし、前記他端に接続されるリンク第２中継器のアドレスを前記第２アドレスとする
ネットワークリンク通過判定装置。
【請求項１３】
請求項１２に記載のネットワークリンク通過判定装置において、
前記ルーティングテーブル解析部は、
前記第２中継器を新たな第１中継器とし、
前記新たな第１中継器に接続される中継器を新たな第２中継器として前記パケットが前記リンクを通過するか否かを判定する
ネットワークリンク通過判定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークリンク通過判定方法及びネットワークリンク通過判定装置に関する。
【背景技術】
【０００２】
情報通信技術の進歩に伴って、コンピュータネットワークが広く普及してきている。コンピュータネットワークでは、複数のコンピュータが網目状に接続され、組織化されている。例えば、インターネットもコンピュータネットワークの一種である。
【０００３】
ネットワークは複数のコンピュータを接続線でつなぐことで構成される。一般的に、コンピュータのように、通信の処理を行う機器は、ノードと呼ばれている。例えば、パソコン、サーバ、プリンタ、ルータおよびスイッチなどがノードとして例示される。また、ノードの間をつなぐ接続線はリンクと呼ばれている。リンクは、有線と無線に大別される。有線としてのリンクは、例えば、銅線でできたツイストペアケーブル、光ファイバでできた光ケーブルなどが主に使われている。また、無線はワイヤレスとも呼ばれ、規格で定められた周波数の無線電波が使われている。
【０００４】
インターネットなどのネットワークでは、端末から送出されたパケットがネットワーク中のいずれのリンクを通過するかを端末から制御することが基本的にはできない。そのため、端末間でいずれのリンクを通過したかを調査する必要が生じる場合がある。リンクを調査する技術が知られている（例えば、特許文献１〜４参照）。特許文献１（特開２００２−１１８５８６号公報）には、ネットワーク上の任意のリンクについて、パケットの通過状況を監視することで、そのリンクの利用率を測定する技術が開示されている。また、特許文献２（特開２００３−０１８２０１号公報）には、ネットワーク上のリンクの使用状況（帯域）を監視する技術が示唆されている。また、特許文献３（特開２００５−０８６８０３号公報）には、ネットワーク上の任意のリンクについて、パケットの通過状況を監視することで、そのリンクの使用を監視する技術が開示されている。更に、特許文献４（特開２００６−１９７２７９号公報）には、ネットワーク上の任意のリンクについて、パケットの通過状況を監視することで、そのリンクの利用率を測定する技術が開示されている。
【０００５】
ある端末からのパケットがネットワーク内のあるリンクを通過するかを判定するためには、Tracerouteコマンドなどが利用されている。このコマンドを実行すると、端末から検査対象のリンクの両端などに向けて、調査のためのパケットが出力される。その端末は、出力したパケットが通過した経路を調査する。これによって、その端末から送出したパケットが通過できるリンクを調査することができる。
【０００６】
Tracerouteコマンドなどによるリンクの調査では、調査パケットが通過できないリンクを明に知ることが困難な場合があった。したがって、ネットワークの大部分のリンクを網羅的に調査することで、通過できないリンクを確認していた。ネットワークの大部分のリンクを網羅的に調査するには、そのネットワークに多くの調査パケットを送出しなければならない。そのため、リンクの調査を実行すると、そのネットワークのトラヒックのコストを増大させてしまうことがあった。また、そのネットワークに多くの調査パケットを送出しなければならないため、調査に時間がかかってしまうことがあった。
【０００７】
また、あるルータのルーティングテーブルを参照することで、パケットがどの方向のルータ(ルータに接続されたリンク)に送出されるかを確認する技術が知られている。転送されるパケットは、端末から送出された後、通過するルータにて転送される方向（宛先）が順次決定されていく。そのため、ルーティングテーブルを参照したルータにパケットが到達しルーティングがなされるとは限らない。したがって、ルーティングテーブルを参照してパケットの転送経路を確認する方法では、端末から出力されるパケットが、任意のリンクを通過するか否かを判定することが困難である。
【０００８】
【特許文献１】特開２００２−１１８５８６号公報
【特許文献２】特開２００３−０１８２０１号公報
【特許文献３】特開２００５−０８６８０３号公報
【特許文献４】特開２００６−１９７２７９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上述したように、Tracerouteコマンドなどを用いたリンク調査では、ある端末からネットワーク内のリンクを通過できるか否かを判定するために、網羅的な調査パケットを送出して調査する必要がある。そのため、リンク調査を行なう場合に、そのネットワークのトラヒックのコストを増大させてしまうことがあった。またこのとき、網羅的な調査パケットを送出する必要があるため、調査に時間を要することがあった。
【００１０】
Tracerouteコマンドなどを用いることなく、ルータのルーティングテーブルを参照することによってリンク調査を行おうとする場合、端末から任意のリンクを通過するパケットを送出できるか否かを判定できないことがある。
【００１１】
本発明が解決しようとする課題は、そのネットワークのトラヒックのコストや調査時間を増大させることなく、リンクを通過するパケットを送出することができるか否かを調査する技術を提供することにある。
【課題を解決するための手段】
【００１２】
以下に、［発明を実施するための最良の形態］で使用される番号を用いて、課題を解決するための手段を説明する。これらの番号は、［特許請求の範囲］の記載と［発明を実施するための最良の形態］との対応関係を明らかにするために付加されたものである。ただし、それらの番号を、［特許請求の範囲］に記載されている発明の技術的範囲の解釈に用いてはならない。
【００１３】
上記課題を解決するために、以下の方法でネットワークリンク通過判定を実行する。そのネットワークリンク通過判定方法では、パケットに記された宛先に基づき前記パケットの送出方向が決定されるネットワークに接続された端末（２）から送出される前記パケットが、前記ネットワークのリンク（５、Ｌ１〜Ｌ５）を通過することができるか否かを判定する。ここにおいて、前記リンク（５、Ｌ１〜Ｌ５）の端点となるパケット中継器（３ｎ−１、３ｎ）（Ｒ２、Ｒ３）へそれぞれ到達する２つのパケットが、それぞれ前記リンク（５、Ｌ１〜Ｌ５）のいずれかの端点に到達する前に通過するパケット中継器（３１）を特定する。そして、次に転送されるパケット中継器（３２）が、前記２つのパケットで異なる場合に、前記端末（２）から送出したパケットは前記リンク（５、Ｌ１〜Ｌ５）を通過しないと判定する。
【００１４】
そのネットワークリンク通過判定方法において、前記リンク（５、Ｌ１〜Ｌ５）のいずれかの端点（３ｎ−１、３ｎ）（Ｒ２、Ｒ３）に到達する前に通過する全てのパケット中継器において、前記２つのパケットが次に転送されるパケット中継器が、前記２つのパケットで等しい場合に、前記端末（２）から送出したパケットは前記リンク（５、Ｌ１〜Ｌ５）を通過する判定することを特徴とする。
【００１５】
そのネットワークリンク通過判定方法において、前記リンク（５、Ｌ１〜Ｌ５）の２つの端点のうち、端末（２）から見た経路で、先に到達するパケット中継器（３ｎ−１）に接続された端点を始点とよび、後に到達するパケット中継器（３ｎ）に接続された端点を終点としたときに、あるリンク（５、Ｌ１〜Ｌ５）の通過／不通過を判定する。
また、前記リンク（５、Ｌ１〜Ｌ５）について、パケットを通過させることが可能と判定した場合、前記リンク（５、Ｌ１〜Ｌ５）の終点が接続されるパケット中継器（３ｎ）に接続された未判定のリンクを新たな判定対象リンク（Ｌ２）とする。そして、この際、先の判定で作成した宛先集合をこの判定に引き継ぐ。そのうえで、先に判定されたリンク（５、Ｌ１）の始点となるパケット中継器（３ｎ−１）（Ｒ１）において、先に判定されたリンク（５、Ｌ１）の終点が接続されるパケット中継器（３ｎ）（Ｒ２）以外に転送される宛先群を宛先集合に加える。
これによって、この宛先集合を参照し、新たな判定対象リンク（Ｌ２）の終点となるアドレスが宛先集合に含まれた場合に、前記端末（２）から新たな判定対象リンク（Ｌ２）を通過するパケットは送出することはできないと判定する。また、この宛先集合を参照し、新たな判定対象リンク（Ｌ２）（５、Ｌ１〜Ｌ５）の終点となるアドレスが宛先集合に含まれない場合に、前記端末（２）から新たな判定対象リンク（Ｌ２）（５、Ｌ１〜Ｌ５）を通過するパケットは送出することはできると判定する。
【００１６】
そのネットワークリンク通過判定方法において、前記２つのパケットの宛先として、前記リンク（５、Ｌ１〜Ｌ５）の端点となるパケット中継器が持つアドレスをそれぞれ利用することが好ましい。
【００１７】
そのネットワークリンク通過判定方法において、前記端末（２）から前記リンク（５、Ｌ１〜Ｌ５）の端点となるパケット中継器へ到達するパケットが前記リンク（５、Ｌ１〜Ｌ５）の端点に到達する前に通過するパケット中継器を特定する。その中継器において、前記リンク（５、Ｌ１〜Ｌ５）の一つの端点となるパケット中継器へ到達するパケットが次に転送されるパケット中継器を調査し、このパケット中継器に転送されない宛先集合を作成する。また、前記宛先集合に前記リンク（５、Ｌ１〜Ｌ５）のもう一つの端点となる宛先が含まれた場合、前記端末（２）から送出したパケットは前記リンク（５、Ｌ１〜Ｌ５）を通過しないと判定することを特徴とする。
【００１８】
そのネットワークリンク通過判定方法において、前記端末（２）から前記リンク（５、Ｌ１〜Ｌ５）の端点となるパケット中継器へ到達するパケットが、前記リンク（５、Ｌ１〜Ｌ５）の端点に到達する前に通過する全てのパケット中継器を特定する。そして、それらの中継器において、前記リンク（５、Ｌ１〜Ｌ５）の一つの端点となるパケット中継器へ到達するパケットが次に転送されるパケット中継器を調査し、このパケット中継器に転送されない宛先集合を作成する。また、前記宛先集合に前記リンク（５、Ｌ１〜Ｌ５）のもう一つの端点となる宛先が含まれない場合、前記端末（２）から送出したパケットは前記リンク（５、Ｌ１〜Ｌ５）を通過すると判定する。
【００１９】
そのネットワークリンク通過判定方法において、前記リンク（５、Ｌ１〜Ｌ５）の２つの端点のうち、端末（２）から見た経路で、先に到達するパケット中継器（３ｎ−１）に接続された端点を始点とよび、後に到達するパケット中継器（３ｎ）に接続された端点を終点とする。このとき、あるリンク（５、Ｌ１〜Ｌ５）の通過／不通過を判定し、前記リンク（５、Ｌ１〜Ｌ５）について、パケットを通過させることが可能と判定した場合、前記リンク（５、Ｌ１〜Ｌ５）の終点が接続されるパケット中継器（３ｎ）（Ｒ２）に接続された未判定のリンク（Ｌ２）を新たな判定対象リンク（Ｌ２）とする。そして、この際、先の判定で作成した宛先集合をこの判定に引き継ぎ、先に判定されたリンク（５、Ｌ１）の始点となるパケット中継器において、先に判定されたリンク（５、Ｌ１）の終点が接続されるパケット中継器以外に転送される宛先群を宛先集合に加える。
そのうえで、この宛先集合を参照し、新たな判定対象リンク（Ｌ２）の終点となるアドレスが宛先集合に含まれた場合に、前記端末（２）から新たな判定対象リンク（Ｌ２）を通過するパケットは送出することはできないと判定する。また、この宛先集合を参照し、新たな判定対象リンク（Ｌ２）の終点となるアドレスが宛先集合に含まれない場合に、前記端末（２）から新たな判定対象リンク（Ｌ２）を通過するパケットは送出することはできると判定する。
【００２０】
上述のネットワークリンク通過判定方法を実施するネットワークリンク通過判定装置を構成することが好ましい。
【００２１】
上述のネットワークリンク通過判定方法を実施するネットワークリンク通過判定プログラムを構成することが好ましい。
【００２２】
また、上記課題を解決するために、ネットワークを介して送受信されるパケットが前記ネットワークを構成するリンク（５、Ｌ１〜Ｌ５）を通過するか否かを判定するネットワークリンク通過判定装置（２）を構成する。ここにおいて、そのネットワークリンク通過判定装置（２）は、ルーティングテーブルを保持し前記パケットの入出力制御するパケット入出力制御部（１１）と、前記ルーティングテーブルに基づいて判定対象のリンク（５、Ｌ１〜Ｌ５）を特定し、前記リンク（５、Ｌ１〜Ｌ５）の一端を示す第１アドレスを宛先とする第１パケットと、前記リンク（５、Ｌ１〜Ｌ５）の他端を示す第２アドレスを宛先とする第２パケットとを生成するルーティングテーブル解析部（１３）と、前記第１パケットと前記第２パケットとを中継する第１中継器（３１）に保持されている第１中継器ルーティングテーブルを読み出すルーティングテーブル取得部（１２）と、前記第１中継器（３１）から前記第１アドレスまでの経路に備えられた第２中継器（３２）のアドレスを保持する探査方向記憶部（１５）とを具備することが好ましい。
ここで、前記ルーティングテーブル解析部（１３）は、前記第１パケットが前記第２中継器（３２）に転送されるときに、前記第２パケットが前記第２中継器（３２）のアドレスと異なるアドレスに転送されるか否かに基づいて、前記パケットが前記リンク（５、Ｌ１〜Ｌ５）を通過するか否かを判定する。
【００２３】
そのネットワークリンク通過判定装置（２）において、さらに、前記第１中継器（３１）に接続される複数のノードのアドレスをアドレス集合として保持する別方向アドレス集合記憶部を具備する構成であることが好ましい。ここにおいて、前記ルーティングテーブル解析部（１３）は、前記第１中継器ルーティングテーブルを参照して、前記第２中継器（３２）のアドレスを第２中継器アドレスとして特定し、前記第２中継器アドレスを前記探査方向記憶部（１５）に格納する。また、前記第２中継器アドレス以外のアドレスを前記別方向アドレス集合記憶部に格納する。そして、前記別方向アドレス集合記憶部に前記第２アドレスが含まれていないとき、前記パケットが前記リンク（５、Ｌ１〜Ｌ５）を通過すると判定する。
【００２４】
そのネットワークリンク通過判定装置（２）において、前記ルーティングテーブル解析部（１３）は、前記リンク（５、Ｌ１〜Ｌ５）の前記一端に接続されるリンク第１中継器（３ｎ−１）のアドレスを前記第１アドレスとし、前記他端に接続されるリンク第２中継器（３ｎ）のアドレスを前記第２アドレスとする。
【００２５】
そのネットワークリンク通過判定装置（２）において、前記ルーティングテーブル解析部（１３）は、前記第２中継器（３２）を新たな第１中継器（３１）とし、前記新たな第１中継器（３１）に接続される中継器を新たな第２中継器（３２）として前記パケットが前記リンク（５、Ｌ１〜Ｌ５）を通過するか否かを判定する。
【００２６】
換言すると、上記課題を解決するために、本発明によるネットワークリンク通過判定方法では、あるリンクに着目する。そして、その着目したリンクに、端末から送出したパケットを通過させることが可能か不可能かを判定する。ここにおいて、その端末は、そのリンクへ至る経路上のルータのルーティングテーブルを参照し、そのリンクと異なる方向へと送出される別方向アドレス集合を作成する。これをその経路上のルータについて繰り返し、順次その別方向アドレス集合を更新する。ただし、そのリンクの始点となるルータは調査対象から除く。
【００２７】
このとき、そのリンクの終点となるアドレスが別方向アドレス集合に含まれていた場合、その端末から出力されるパケットは、そのリンクを通過することが不可能であると判定する。この調査では、そのリンクの終点となるアドレスが別方向アドレス集合に含まれた時点で調査を終了させることで、ルーティングテーブルの検索回数を削減することが可能である。
【００２８】
また、本発明によるネットワークリンク通過判定方法では、通過可能と判定したリンクの終点となるルータに接続されている未判定リンクを新たな判定対象とする。このとき、別方向アドレス集合を引き継ぐ。そして、リンクの終点となるルータのみのルーティングテーブルを参照して新たな判定対象とするリンクと異なる方向に送出されるアドレス群を加え別方向アドレス集合を更新する。このような判定を実施することで、ネットワーク内のリンクについて順次判定することができる。この方法により、ネットワークに接続されたそれぞれの端末から調査パケットを送出することなく、任意のリンクを通過させるパケットが送出可能かを判定することができる。また、ネットワーク内のリンクを効率よく順次判定することが可能となる。
【発明の効果】
【００２９】
本発明によると、共通のメトリックに基づくルーティングがなされているネットワークにおいて、そのネットワークのトラヒックのコストや調査時間を増大させることなく、リンクを通過するパケットを送出することができるか否かを調査することが可能となる。
【００３０】
また、本発明によると、ネットワークのある地点(端末もしくはルータ等)からあるリンクをパケットが通過することが可能か不可能かを判定場合に、そのパケットがそのリンクを通過できるか否かを迅速に判定することが可能である。
【発明を実施するための最良の形態】
【００３１】
［第１の実施形態］
以下に、図面を参照して、本発明を実施するための形態について説明を行う。図１は、本実施形態のネットワークリンク通過判定方法及びネットワークリンク通過判定装置を適用するネットワークシステム１の構成を例示するブロック図である。図１を参照すると、本実施形態におけるネットワークシステム１は、端末装置２と、複数のルータ（第１ルータ３１〜第ｎルータ３ｎ）と、複数のネットワーク（第１ネットワーク４１〜第ｎネットワーク４ｎ）とを含んで構成されている。また、ルータなどのノードは、リンクを介して接続されている。以下の実施形態において、ネットワークシステム１はパケット通信に対応しているものとする。また、ネットワークシステム１を構成する複数のリンクは、有線または無線によって構成されているものとする。
【００３２】
以下に述べる実施形態では、端末装置２から送出されたパケットが、リンク５を通過することができるかできないかを判定する場合に対応して説明を行う。図１に示されているように、リンク５の両端には、始点アドレス６と［７］があたえられているものとする
図２は、端末装置２の構成を例示するブロック図である。端末装置２は、パケット入出力制御部１１と、ルーティングテーブル取得部１２と、ルーティングテーブル解析部１３と、探査方向記憶部１４と、別方向アドレス記憶部１５とを含んで構成されている。
【００３３】
パケット入出力制御部１１は、ネットワークシステム１に供給されるパケットの入出力を制御する。
【００３４】
ルーティングテーブル取得部１２は、ネットワークシステム１を構成するネットワークを介してルーティングテーブルの情報を収集する。
【００３５】
ルーティングテーブル解析部１３は、収集したルーティングテーブルの情報を解析し、端末装置２から通過可能もしくは通過不可能なリンクを判定する。また、ルーティングテーブル解析部１３は、リンク５の始点アドレス６と終点アドレス７とを別方向アドレス記憶部１５に格納する。パケット入出力制御部１１に保持されているルーティングテーブルを参照し、始点アドレス６を宛先に持つパケットが、次に転送されるルータ（本実施形態においては第１ルータ３１）のアドレスを取得する。
【００３６】
探査方向記憶部１４は、経路上のルータにおいて、判定対象とするリンクと別方向に出力されるアドレスの集合を格納する。
【００３７】
別方向アドレス記憶部１５は、経路上のルータにおいて、ネットワークシステム１のあるルータから、判定対象とするリンクへと向かう方向(次のルータのアドレス)を示すデータ格納する。
【００３８】
通過可能／不可能リンク表１６は、端末から送出したパケットが判定対象とするリンクを通過できるか通過できないかを示すデータを格納する。
【００３９】
以下に、図面を参照して本実施形態の動作に関して説明を行う。以下に述べる動作は、端末装置２が、ネットワークリンク通過判定方法を実行するためのコンピュータプログラムに示される手順に従って動作することで実施される。また、以下の説明では、判定対象のリンクをリンク５とし、端末装置２から出力されるパケットがリンク５を通過するか否かを判定する場合の動作を例示する。
【００４０】
図３を参照すると、ステップＳ１０１において、端末装置２のルーティングテーブル解析部１３は、別方向アドレス記憶部１５に示されている情報に基づいて、判定対象のリンク（リンク５）の始点アドレス６と終点アドレス７とを特定する。そして、ルーティングテーブル解析部１３は、ルーティングテーブル取得部１２を介してパケット入出力制御部１１にあるルーティングテーブルを参照する。ルーティングテーブル解析部１３は、そのルーティングテーブルに示されている情報に基づいて、リンク５の始点アドレス６を宛先とするパケット（以下、第１パケットと呼ぶ。）が転送されるルータ（第１ルータ３１）のアドレスを抽出する。
【００４１】
ここにおいて、ルーティングテーブル解析部１３は、第１パケットが転送される経路のルータをルータＲ（ｋ）としたときに、ｋ＝１として、
ルータＲ（ｋ）＝第１ルータ３１
のアドレスを得る。ルーティングテーブル解析部１３は、第１ルータ３１に接続し、その第１ルータ３１に保持されているルーティングテーブル（以下、第１ルーティングテーブルと呼ぶ。）を読み出す。
【００４２】
ルーティングテーブル解析部１３は、第１ルータ３１から第１ルーティングテーブルを取得するようにルーティングテーブル取得部１２に命令する。ルーティングテーブル取得部１２は、その命令に応答して、第１ルーティングテーブル要求メッセージを、パケット入出力制御部１１を介して第１ルータ３１に送る。ルーティングテーブル取得部１２は、その第１ルーティングテーブル要求メッセージに応答して供給された第１ルーティングテーブルを取得する。ルーティングテーブル取得部１２は、第１ルーティングテーブルをルーティングテーブル解析部１３に渡す。
【００４３】
本実施形態では、端末装置２から送出されるパケットが、全て第１ルータ３１へ転送される場合を例示する。一般的に、端末のルーティングテーブルとルータのルーティングテーブルとは、同様な形式で構成されている。したがって、ネットワークシステム１を構成する任意の端末のパケット入出力制御部１１を、ルータとして同様に扱うことも可能である。なお、ルータのルーティングテーブルを参照することは、ＳＮＭＰなどを用いることや、ルーティングプロトコルに参加することで一般的に可能である。
【００４４】
ステップＳ１０２において、ルーティングテーブル解析部１３は、第１ルーティングテーブルを参照して、第１パケットが次に転送されるルータ（以下、第２ルータ３２と呼ぶ。）のアドレス（第２ルータアドレス）を読み出す。ルーティングテーブル解析部１３は、その第２ルータアドレスを示す情報を別方向アドレス記憶部１５に格納する。
【００４５】
ステップＳ１０３において、ルーティングテーブル解析部１３は、第１ルーティングテーブルに基づいて、第２ルータ３２と異なるルータへと転送されるアドレス群を取得する。ルーティングテーブル解析部１３は、取得したアドレス群を探査方向記憶部１４に保持されているアドレス集合データに追加して、そのアドレス集合データを更新する。
【００４６】
ステップＳ１０４において、ルーティングテーブル解析部１３は、アドレス集合データに終点アドレス７が含まれるか否かの判断を行う。その判断の結果、終点アドレス７がアドレス集合データに含まれている場合、処理はステップ１０５に進む。また、終点アドレス７がアドレス集合データに含まれていない場合には、処理はステップＳ１０６に進む。
【００４７】
ステップＳ１０５において、ルーティングテーブル解析部１３は、探査方向記憶部１４のアドレス集合データに終点アドレス７が含まれている場合、端末装置２から出力されるパケットは、リンク５を通過することができないと判断する。ルーティングテーブル解析部１３は、その判断の結果を通過可能／不可能リンク表１６に格納し、処理は終了する。このときルーティングテーブル解析部１３は、判定対象リンク（リンク５）の始点／終点のアドレス（始点アドレス６、終点アドレス７）と、端末装置２のアドレスと、通過不可能を示すフラグとを関連付けたデータを生成して通過可能／不可能リンク表１６に格納する。
【００４８】
ステップＳ１０６において、ルーティングテーブル取得部１２は、第１ルーティングテーブルに、始点アドレス６が含まれているか否かの判断を実行する。その判断の結果、第２ルーティングテーブルに始点アドレス６が含まれている場合、処理はステップＳ１０８に進む。また、第２ルーティングテーブルに始点アドレス６が含まれていない場合、処理はステップＳ１０７に進む、
ステップＳ１０７において、ルーティングテーブル解析部１３は、第２ルータを新たな第１ルータとする。処理はステップＳ１０１に戻り、ルーティングテーブル解析部１３は、その新たな第１ルータに対応して、パケットの通過判定処理を継続する。
【００４９】
ステップＳ１０８において、ルーティングテーブル解析部１３は、端末装置２から出力されるパケットは、リンク５を通過することができる判断する。ルーティングテーブル解析部１３は、その判断の結果を、通過可能／不可能リンク表１６に格納し、処理は終了する。このときルーティングテーブル解析部１３は、判定対象リンク（リンク５）の始点／終点のアドレス（始点アドレス６、終点アドレス７）と、端末装置２のアドレスと、通過可能を示すフラグとを関連付けたデータを生成して通過可能／不可能リンク表１６に格納する。
【００５０】
このように、本実施形態のネットワークシステム１では、同一のメトリックに基づくルーティングがなされている限り、（例えば、最小ホップ数に基づくルーティングがなされている限り、）リンクの始点アドレス向けのパケットとリンクの終点アドレス向けのパケット経路が再び同じルータで重なる可能性はない。従って、終点アドレス向けパケットは、第ｎ−１ネットワーク４ｎ−１を経由した後、第ｎルータ３ｎに到達する。また、第ｎルータ３ｎの後段に接続される第ｎネットワーク４ｎ向けのパケットも、終点アドレス７を持つ第ｎルータ３ｎを経由する。
【００５１】
例えば、始点アドレス６を宛先とするパケット（第１パケット）が、第１ルータ３１、第２ルータ３２…第ｎルータ３ｎに順に転送されるようルーティングが設定されているとする。そして、終点アドレス７を宛先とするパケット（第２パケット）も、第１ルータ３１、第２ルータ３２…第ｎルータ３ｎで、同様に転送されるよう設定されているとする。その場合は、別方向アドレス集合に終点アドレス７が含まれない。そのため、ルーティングテーブル解析部１３は、リンク５を通過可能なパケットを端末装置２が送出できると判定される。
【００５２】
また、第１パケットが、第１ルータ３１、第２ルータ３２…第ｎルータ３ｎに順に転送されるようルーティングが設定されているとする。そして、第２パケットが、第１ルータ３１、第２ルータ３２…第ｎルータ３ｎに順に転送されず、いずれかで分岐して転送されるよう設定されているとする。この場合は、別方向アドレス集合に終点アドレス７が含まれる。そのため、ルーティングテーブル解析部１３は、リンク５を通過可能なパケットを端末装置２が送出できないと判定する。
【００５３】
以下に、具体的なネットアークアドレスを用いて、本実施形態の動作について説明を行う。なお、以下の説明においては、ネットワークシステム１が、ＩＰアドレスを用いてデータ通信を行うネットワークである場合を例示する。
【００５４】
図４は、第１ルータ３１に保持されているルーティングテーブルの構成を例示している。そのルーティングテーブルには、第１ルータ３１から他のルータ（または、他の端末）へパケットを送ろうとする場合に、そのパケットを中継させるルータ（または端末）を決定するための情報が示されている。第１ルータ３１は、最終的なアドレス（例えば、始点アドレス６）が自ネットワーク内に無い場合、そのルーティングテーブルを参照して次の中継器を決定している。
【００５５】
図５は、ＩＰアドレスを含むネットワークシステム１の構成を例示している。図５を参照すると、リンク５の始点アドレス６は、(192．168．3．1)であり、終点アドレス７は(192．168．3．2)である。始点アドレス６を宛先とするパケット（第１パケット）は、第２ルータ３２のアドレス(192．168．2．1)に向けて転送される。このとき、終点アドレス７を宛先とするパケット（第２パケット）は、第１ネットワーク４１に備えられたゲートウェイアドレス(192．168．4．1)に向けて送出される。この場合、ルーティングテーブル解析部１３は、リンク５を通過するパケットを端末装置２から送出することはできないと判定する。
【００５６】
本実施形態において、端末装置２は、各ルータのルーティングテーブルを順次探索している。それによって、端末装置２から出力されるパケットが、ある特定のリンク（例えば、上述のリンク５）を通過することができるか否かを、端末装置２から多数の調査パケットを送出することなく判定することができる。
【００５７】
［第２の実施形態］
以下に、本願発明の第２の実施形態について説明を行う。以下に述べる第２実施形態では、あるリンクの判定を実行した後、未判定のリンクを新たな判定対象としてその未判定リンクの通過可能性を判定する場合の構成・動作を例示している。また、第２実施形態の説明に参照する図面には、第１実施形態の説明に用いた参照符号と同じ符号が付されている構成要素が記載されている。この構成要素は、第１実施形態と同様の構成・動作である。したがって、以下の説明においては、この構成要素に関して重複する説明は省略する。
【００５８】
図６は、第２実施形態のネットワークシステム１の構成を例示するブロック図である。第２実施形態におけるネットワークシステム１は、端末装置２と、複数のネットワーク（第１ネットワークＮＷ１〜第３ネットワークＮＷ３）と、複数のルータ（第１ルータＲ１〜第５ルータＲ５）と、複数のリンク（第１リンクＬ１〜第５リンクＬ５）とを含んで構成されている。第２ネットワークＮＷ２には、第１ゲートウェイアドレスを有する第１ゲートウェイが備えられている。第３ネットワークＮＷ３には、第２ゲートウェイアドレスを有する第２ゲートウェイが備えられている。第２実施形態において、各ノード間は、パケット通信が実行できるように接続されている。
【００５９】
以下に述べる第２実施形態においては、上述の複数のリンク（第１リンクＬ１〜第５リンクＬ５）のうち、第１リンクＬ１に対するパケット通過判定処理が終了している場合を例示する。また、端末装置２から出力されるパケットが、第１リンクＬ１を通過することができることが明らかである場合を例示して第２実施形態に関する説明を行う。
【００６０】
端末装置２は、第１実施形態と同様の構成要素を備えている。端末装置２のルーティングテーブル解析部１３は、収集したルーティングテーブルの情報を解析し、端末装置２から通過可能もしくは通過不可能なリンクを判定する。ここにおいて、第２実施形態のルーティングテーブル解析部１３は、複数のリンクに対し、パケットが通過可能か否かを順次判定している。また、第２実施形態の別方向アドレス記憶部１５は、複数のリンクに関する情報を、判定対象とするリンクのリストとして保持している。通過可能／不可能リンク表１６は、複数のリンクを既に判定対象としたか否かを示すフラグと、端末から送出したパケットが判定対象とするリンクを通過できるか通過できないかを示すフラグとを保持している。
【００６１】
ここにおいて、ある端末にパケットを通過させることが可能であると判定されたリンクのリスト（以下、これを通過可能リンクリスト２２と呼ぶ。）があるものとする。また、通過可能リンクリスト２２には、通過可能リンクに関する情報として、始点ルータＲＳ、終点ルータＲＥ、別方向アドレスリストＡ（ＲＥ）とが関連付けられて登録されているものとする。
【００６２】
始点ルータＲＳは、通過可能リンクにおいて、端末装置２から出力されるパケットを受けるルータを示している。終点ルータＲＥは、通過可能リンクにおいて、始点ルータＲＳが受けたパケットを他のノードに供給するルータを示している。別方向アドレスリストＡ（ＲＥ）は、始点ルータのアドレス以外の方向を示している。
【００６３】
図７は、第２実施形態における探査方向記憶部１４の構成を例示するブロック図である。図７を参照すると、探査方向記憶部１４は、別方向アドレス集合２１を含んで構成されている。図７に示されているように、別方向アドレス集合２１には、端末装置２から第１リンクＬ１までの経路とは別方向に転送される情報が、アドレス集合として保持されている。
【００６４】
図８は、第２実施形態における別方向アドレス記憶部１５の構成を例示するブロック図である。図８を参照すると、別方向アドレス記憶部１５は、通過可能リンクリスト２２と、新規通過可能リンクリスト２３と、未判定リンクリスト２４とを含んで構成されている。通過可能リンクリスト２２には、通過可能リンクであることを示すように第１リンクＬ１が記載されている。新規通過可能リンクリスト２３は、新たな判定対象リンクに関する情報を示している。未判定リンクリスト２４は、未判定のリンクに関する情報を示している。
【００６５】
図９は、第２実施形態における通過可能／不可能リンク表１６の構成を例示するブロック図である。図９を参照すると、通過可能／不可能リンク表１６は、判定済リンク情報２５を含んで構成されている。判定済リンク情報２５には、第１リンクＬ１が判定済みで、通過可能である等の情報が記載されている。
【００６６】
以下に、図面を参照して第２実施形態の動作について説明を行う。図１０は、第２実施形態の動作を例示するフローチャートである。図１０Ａおよび図１０Ｂは、端末装置２が第２リンクＬ２を判定する場合の動作を例示している。また、図１０Ａおよび図１０Ｂに示される動作は、端末装置２が、所定のコンピュータプログラムに示される手順に対応して動作することによって実行される。
【００６７】
図１０Ａを参照すると、ステップＳ２０１において、通過可能リンクリスト２２に判定済リンクに関する情報が存在するか否かの判断を実行する。その判断の結果、通過可能リンクリスト２２に判定済リンクが存在しない場合、処理はステップＳ２０２に進む。また、通過可能リンクリスト２２に判定済リンクが存在する場合、処理はステップＳ２０３に進む。
【００６８】
ステップＳ２０２において、ルーティングテーブル解析部１３は、新規通過可能リンクリスト２３が構成されている場合に、その新規通過可能リンクリスト２３を通過可能リンクリスト２２に置換して処理は終了する。
【００６９】
ステップＳ２０３において、ルーティングテーブル解析部１３は、通過可能リンクリスト２２に示されているリンクから、任意のリンク（以下、特定リンクと呼ぶ）を特定する。上述したように、通過可能リンクリスト２２には、判定済リンクとして第１リンクＬ１が示されている。したがって、以下においては、特定リンクが第１リンクＬ１である場合に対応して本実施形態の動作を説明する。
【００７０】
ステップＳ２０４において、ルーティングテーブル解析部１３は、通過可能／不可能リンク表１６を参照して第１リンクＬ１の始点ルータのアドレス（始点アドレス）と終点ルータのアドレス（終点アドレス）とを読み出す。また、ルーティングテーブル解析部１３は、探査方向記憶部１４から別方向アドレス集合２１を読み出す。これによってルーティングテーブル解析部１３は、第１リンクＬ１に関する情報として、
始点ルータＲＳ＝第１ルータＲ１、
終点ルータＲＥ＝第２ルータＲ２、
とし、さらに、端末装置２から第１リンクＬ１までの経路における別方向アドレス集合を、
別方向アドレス集合Ｅ（Ｒ１）＝（１９２．１６８．３．０／２４）
とする。
【００７１】
ステップＳ２０５において、ルーティングテーブル取得部１２は、ルーティングテーブル解析部１３からの命令に応答して第１ルータＲ１に保持されているルーティングテーブル（第１ルーティングテーブル）を読み出す。ルーティングテーブル取得部１２は、読み出した第１ルーティングテーブルをルーティングテーブル解析部１３に供給する。ルーティングテーブル解析部１３は、その第１ルーティングテーブルに基づいて、終点アドレス以外のアドレスを別方向アドレス部分集合として特定する。ルーティングテーブル解析部１３は、その別方向アドレス部分集合を別方向アドレス集合に追加することで、その別方向アドレス集合を更新する。
【００７２】
具体的には、ルーティングテーブル解析部１３は、
始点ルータＲＳ＝第１ルータＲ１
とし、そのルーティングテーブルを調査する。上述のように、第２ルータＲ２が終点ルータＲＥに対応する。このとき、ルーティングテーブル解析部１３は、第２ルータＲ２に関する別方向アドレス部分集合として以下のアドレス情報を取得する。
【００７３】
別方向アドレス部分集合ａ（ＲＥ）＝１９２．１６８．４．０／２４
ここで、
別方向アドレス集合
＝別方向アドレス集合（ＲＳ）＋別方向アドレス部分集合ａ（ＲＥ）
とし、
別方向アドレス集合（ＲＳ）
＝（１９２．１６８．３．０／２４、１９２．１６８．４．０／２４）とする。
【００７４】
ステップＳ２０６において、ルーティングテーブル取得部１２は、第２ルータＲ２のルーティングテーブル（第２ルーティングテーブル）を読み出す。ルーティングテーブル取得部１２は、その第２ルーティングテーブルをルーティングテーブル解析部１３に供給する。ルーティングテーブル解析部１３は、第２ルーティングテーブルと通過可能／不可能リンク表１６とに基づいて、特定リンクの終点ルータ（＝第２ルータＲ２）の後段に未判定のリンクが存在するか否かを判断する。その判断の結果、終点ルータの後段に未判定リンクが存在しない場合、処理はステップＳ２０７に進む。また、終点ルータの後段に未判定リンクが存在する場合、処理はステップＳ２０８に進む。
【００７５】
第２実施形態のネットワークシステム１を参照すると、ルーティングテーブル解析部１３は、第２ルータＲ２の後段のリンクとして第２リンクＬ２と第３リンクＬ３とを抽出する。ルーティングテーブル解析部１３は、通過可能／不可能リンク表１６を参照し、これらのリンク（第２リンクＬ２、第３リンクＬ３）に、判定済みフラグが立っているか否かを確認する。第２実施形態において、これらリンクには、判定済みフラグが立っていない。そのため、ルーティングテーブル解析部１３は、別方向アドレス記憶部１５の未判定リンクリスト２４に第２リンクＬ２と第３リンクＬ３を登録する。
【００７６】
ステップＳ２０７において、ルーティングテーブル解析部１３は、第１リンクＬ１に接続される未判定リンクが存在しないと判断する。ルーティングテーブル解析部１３は、その判断に基づいて、ステップＳ２０３で特定した通過可能リンクを通過可能リンクリスト２２から削除する。その後、処理はステップＳ２０１に戻る。
【００７７】
図１０Ｂを参照すると、ステップＳ２０８において、未判定リンクが複数存在する場合、任意の未判定リンクをと、その終点アドレス（以下、未判定終点アドレスと呼ぶ。）を特定する。ステップＳ２０９において、その未判定終点アドレスが別方向アドレス集合に含まれるか否かの判断を実行する。その判断の結果、その未判定終点アドレスが別方向アドレス集合に含まれる場合、処理はステップＳ２１０に進む。また、その未判定終点アドレスが別方向アドレス集合に含まれていない場合、処理はステップＳ２１１に進む。
【００７８】
ステップＳ２１０において、ルーティングテーブル解析部１３は、その未判定終点アドレスが別方向アドレス集合に含まれるため、その未判定リンクを通過不可能リンクと判定する。ルーティングテーブル解析部１３は、その未判定リンクを判定済リンクとするように、通過可能／不可能リンク表１６を更新する。
【００７９】
ステップＳ２１１において、ルーティングテーブル解析部１３は、その未判定リンクを通過可能リンクと判定する。ルーティングテーブル解析部１３は、その未判定リンクを新たな判定済リンクとするように、通過可能／不可能リンク表１６を更新する。ステップＳ２１２において、ルーティングテーブル解析部１３は、その新たな判定済リンクを新規通過可能リンクリスト２３に登録する。
【００８０】
ルーティングテーブル解析部１３は、その新たな判定済リンクが、第２リンクＬ２である場合、その始点ルータ（＝第２ルータＲ２）のアドレスと、終点ルータ（＝第３ルータＲ３）のアドレスとを特定する。また、ルーティングテーブル解析部１３は、端末装置２から第２リンクＬ２に向かう経路における、最新の別方向アドレス集合を探査方向記憶部１４に格納する。その後、処理はステップＳ２０６に戻る。
【００８１】
第２実施形態に示すネットワークシステム１において、第２リンクＬ２が未判定リンクである場合、その終点ルータ（第３ルータＲ３）のアドレスを特定する（ステップＳ２０８）。ルーティングテーブル解析部１３は、別方向アドレス集合に第３ルータＲ３のアドレスが含まれているか否かを調査する（ステップＳ２０９）。
【００８２】
本実施形態においては、第３ルータＲ３のアドレスは、別方向アドレス集合に含まれていない。そのため、処理はステップＳ２１１に進む。ステップＳ２１１では、ルーティングテーブル解析部１３は、この未判定リンク（第２リンクＬ２）を通過可能なパケットを端末装置２から送出できると判定する。また、ルーティングテーブル解析部１３は、その判定結果を通過可能／不可能リンク表１６に格納する。
【００８３】
ルーティングテーブル解析部１３は、この未判定リンク（第２リンクＬ２）を判定済みリンクとし、未判定リンクリスト２４から削除する。また、ルーティングテーブル解析部１３は、新規通過可能リンクリスト２３に第２リンクＬ２を登録する。このとき、ルーティングテーブル解析部１３は、第２リンクＬ２に関する情報として、その始点ルータ（＝第２ルータＲ２）のアドレスと、終点ルータ（＝第３ルータＲ３）のアドレスとを新規通過可能リンクリスト２３に格納する。また、ルーティングテーブル解析部１３は、端末装置２から第２リンクＬ２に向かう経路における、最新の別方向アドレス集合を探査方向記憶部１４に格納する（ステップＳ２１２）。
【００８４】
その後、処理はステップＳ２０６に戻り、第２リンクＬ２と同様に、未判定リンクリスト２４にある第３リンクＬ３に対する判定を行う。第２実施形態において、第３リンクＬ３も通過可能リンクとして判定された場合、その第３リンクＬ３を示す情報が新規通過可能リンクリスト２３に格納される。そして、未判定リンクリスト２４から第３リンクＬ３を示す情報が削除される。
【００８５】
このとき、第２実施形態における未判定リンクリスト２４から、未判定であったリンク（第２リンクＬ２、第３リンクＬ３）を示す情報が全て削除されたことになる。したがって、ステップＳ２０６における判断の結果、処理はステップＳ２０７に進む。このとき、ルーティングテーブル解析部１３は、着目したリンク（第１リンクＬ１）を通過可能リンクリストから削除する。そして、処理はステップＳ２０１に戻る。通過可能リンクリスト２２が空になっているため、ステップＳ２０１では、新規通過可能リンクリスト２３を通過可能リンクリスト２２に置換する。つまり、新規通過可能リンクリスト２３に格納されていた第２リンクＬ２、第３リンクＬ３を含む通過可能リンクリスト２２を構成する。
【００８６】
以上の手順により、判定済みの通過可能リンク（第１リンクＬ１）の終点ルータ（第２ルータＲ２）に接続されているリンクを対象とした判定を完了する。第２リンクＬ２や第３リンクＬ３を特定リンクとして上述の動作を繰り返す。つまり、第２リンクＬ２の終点ルータである第３ルータＲ３や、第３リンクＬ３の終点ルータである第５ルータＲ５を特定する。第３ルータＲ３に接続されている第４リンクＬ４や、第５ルータＲ５に接続されている第５リンクＬ５に対して、同様の判定を実行する。
【００８７】
第２実施形態のネットワークシステム１を参照すると、第４リンクＬ４については、通過可能であると判定される。ここにおいて、第５リンクＬ５については、ステップＳ２０９の判断において、終点となるルータ（第５ルータＲ５）が別方向アドレス集合に含まれることになる。そのため、ルーティングテーブル解析部１３は、第５リンクＬ５を通過不可能リンクであると判定する。
【００８８】
以上の手順により、本発明による通過可能リンク判定方式は、ある端末から送出したパケットがネットワーク内のリンクを通過することができるかを順次判定することが可能となる。
【００８９】
上述してきたように、本実施形態によるネットワークリンク通過判定方法は、共通のメトリックに基づくルーティングがなされているネットワークに適用可能である。このようなネットワークでは、対象とするリンクの２つの端点を宛先としたパケットで、転送される経路が一度分岐した後は、再び経路が合流することがないという性質を利用している。
【００９０】
本実施形態によるネットワークリンク通過判定方法では、任意の端末から判定対象のリンクに向かうパケットの経路を比較している。そして、判定対象のリンクの始点に到達するまでの経路が等しい場合に、その端末からそのリンクを通過するパケットが送出可能であるとしている。また、その経路が異なる場合には、そのリンクを通過するパケットを送出することができないと判定している。
【００９１】
これによって、本実施形態のネットワークリンク通過判定方法及び装置は、そのネットワークのトラヒックのコストや調査時間を増大させることなく、リンクを通過するパケットを送出することができるか否かを調査することが可能となる。
【００９２】
例えば、複数の端末がTracerouteコマンドなどを用いたリンク調査を行う場合、各端末から調査パケットが送出される。それらの端末数をＮとすると、２Ｎ個の調査パケットが必要であった。また、ネットワーク内の全てのリンクを対象とし判定を実施する場合には、リンク数をＭとして２Ｍ個の調査パケットが必要だった。
【００９３】
本実施形態のネットワークリンク通過判定方法及び装置では、各端末からそのリンクへ到達するルータのルーティングテーブルを参照することでパケットの通過可否を判定をしている。そのため、ルーティングテーブルが既知である場合は、調査パケットが不要となる。ルーティングテーブルを参照するための調査パケットを利用するとしても、ルータと同数の調査パケットで調査が可能である。例えば、ネットワーク内の全てのリンクを対象とし判定を実施する場合に、そのネットワーク中のルータ数をＸ個とすると、Ｘ個の調査パケットですむ。一般的にルータ数はリンク数よりも小さいため、調査パケットの数は、従来のTracerouteコマンドなどを用いたリンク調査に比較して少なくなる。
【００９４】
また、従来は、ルータのルーティングテーブルを参照するだけでは、ある端末から送出されたパケットがルータを通過するかを判定することが困難であった。つまり、参照したルーティングテーブルに基づく転送が、端末から出力されるパケットに対してなされるとは限らない。そのため、端末が、そのリンクを通過するパケットを送出することができるか判定することが非常に困難であった。
【００９５】
本実施形態のネットワークリンク通過判定方法及び装置では、各端末からそのリンクへ到達する経路上のルータについて、上述のアドレス集合を作成し、判定を行うため、通過可能リンクの判定が可能となった。
【００９６】
更に、本実施形態のネットワークリンク通過判定方法及び装置では、通過可能であると判定済みリンクの終点となるルータに接続されるリンクを新たな判定対象としている。そして、以前の判定までに作成した別方向アドレス集合を利用し、これに１つのルーティングテーブルを参照して作成した別方向アドレス部分集合を加えている。それによって順番に判定が行えるため、ルーティングテーブルの参照回数が、判定するリンク数と等しくなる。これによって、効率の良い判定をすることが可能である。
【図面の簡単な説明】
【００９７】
【図１】図１は、本実施形態を適用するネットワークシステム１の構成を例示するブロック図である。
【図２】図２は、端末装置２の構成を例示するブロック図である。
【図３】図３は、本実施形態の動作を例示するフローチャートである。
【図４】図４は、第１ルータ３１に保持されているルーティングテーブルの構成を例示する図である。
【図５】図５は、ＩＰアドレスを含むネットワークシステム１の構成を例示するブロック図である。
【図６】図６は、第２実施形態のネットワークシステム１の構成を例示するブロック図である。
【図７】図７は、第２実施形態の探査方向記憶部１４の構成を例示するブロック図である。
【図８】図８は、第２実施形態の別方向アドレス記憶部１５の構成を例示するブロック図である。
【図９】図９は、第２実施形態の通過可能／不可能リンク表１６の構成を例示するブロック図である。
【図１０Ａ】図１０Ａは、第２実施形態の動作を例示するフローチャートである。
【図１０Ｂ】図１０Ｂは、第２実施形態の動作を例示するフローチャートである。
【符号の説明】
【００９８】
１…ネットワークシステム
２…端末装置
３１…第１ルータ
３２…第２ルータ
３ｎ−１…第ｎ−１ルータ
３ｎ…第ｎルータ
４１…第１ネットワーク
４２…第２ネットワーク
４ｎ−１…第ｎ−１ネットワーク
４ｎ…第ｎネットワーク
５…リンク
６…始点アドレス
７…終点アドレス
１１…パケット入出力制御部
１２…ルーティングテーブル取得部
１３…ルーティングテーブル解析部
１４…探査方向記憶部
１５…別方向アドレス記憶部
１６…通過可能／不可能リンク表
２１…別方向アドレス集合
２２…通過可能リンクリスト
２３…新規通過可能リンクリスト
２４…未判定リンクリスト
２５…判定済リンク情報
ＮＷ１…第１ネットワーク
ＮＷ２…第２ネットワーク
ＮＷ３…第３ネットワーク
Ｌ１…第１リンク
Ｌ２…第２リンク
Ｌ３…第３リンク
Ｌ４…第４リンク
Ｌ５…第５リンク
Ｒ１…第１ルータ
Ｒ２…第２ルータ
Ｒ３…第３ルータ
Ｒ４…第４ルータ
Ｒ５…第５ルータ
【図１】
2008113278.tif 000003
【図２】
2008113278.tif 000004
【図３】
2008113278.tif 000005
【図４】
2008113278.tif 000006
【図５】
2008113278.tif 000007
【図６】
2008113278.tif 000008
【図７】
2008113278.tif 000009
【図８】
2008113278.tif 000010
【図９】
2008113278.tif 000011
【図１０Ａ】
2008113278.tif 000012
【図１０Ｂ】
2008113278.tif 000013