トポロジーツリー作成装置、プログラム、及び方法
【課題】ネットワークに流れる通常のパケットから、ネットワークトポロジーを高精度に特定するため技術を提供する。
【解決手段】観測されたパケットから、そのパケットが経由したノードの数であるホップ数、及び送信上のボトルネックとなるボトルネック帯域を特定し、ロス障害を検出する。それにより、観測されたパケットを送信したサブネットは、特定したホップ数、及びボトルネック帯域を基に、トポロジーツリー上にノードとして配置する。パケットをロスするロス障害を検出した場合には、そのロス障害が検出されたサブネットのトポロジーツリー上の配置から、不適切に配置されているサブネットを抽出し、抽出したサブネットは不適切性とならないように配置を変更する。
【解決手段】観測されたパケットから、そのパケットが経由したノードの数であるホップ数、及び送信上のボトルネックとなるボトルネック帯域を特定し、ロス障害を検出する。それにより、観測されたパケットを送信したサブネットは、特定したホップ数、及びボトルネック帯域を基に、トポロジーツリー上にノードとして配置する。パケットをロスするロス障害を検出した場合には、そのロス障害が検出されたサブネットのトポロジーツリー上の配置から、不適切に配置されているサブネットを抽出し、抽出したサブネットは不適切性とならないように配置を変更する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サブネットが相互に連結された構成のネットワークのトポロジーを特定するための技術に関する。
【背景技術】
【０００２】
現在、インターネットに代表されるネットワークは、各種サービスを提供するために幅広く用いられている。そのサービスでは、パケットの伝送経路上にスイッチの故障やルータでの輻輳等による障害が発生すると、パケットの受信品質が大きく低下する。例えばパケットロス率が大きくなると、パケットの再送信が必要になることから、パケットの送信に必要な時間がより長くなる、といった不具合が発生する。このことから、伝送経路（ネットワーク）上に発生した障害には迅速に対応することが重要となっている。それにより、ネットワークのトポロジーを把握することは、障害解析上、大変重要となっている。
【０００３】
ネットワークでは、ネットワークを設計構築する設計構築部門と運用管理（障害対応）する運用管理部門とが別々となっていることは多い。運用管理部門は、障害対応に際してネットワークの正確なトポロジー情報を入手できないことは多い。状態解析を実施しようとするネットワークのユーザも、やはりトポロジー情報の入手は困難であるのが普通である。このようなことから近年では、ネットワークのトポロジーを特定（推定）する技術が検討されている。
【０００４】
ネットワークのトポロジーを推定する従来のトポロジー推定方法は、３つに大別される。即ち、tracerouteによる推定方法、ＳＮＭＰ（Simple Network Management Protocol）による推定方法、及びルーティングプロトコルのキャプチャによる推定方法、の３つである。
【０００５】
tracerouteはネットワーク上のある観測地点（調査ノード）から任意の宛先ノードまでの転送経路を、調査ノードからの調査パケットの送信、及びその応答から調べる調査ツール（プログラム）である。それにより、tracerouteによる推定方法では、このツールを多数の宛先ノードに使用し、各宛先ノードで得られた結果を統合することで調査ノードからのネットワークトポロジーを推定する。ここでは、tracerouteとはそのような調査パケットを用いる調査ツールの総称として表記している。
【０００６】
ＳＮＭＰとはネットワーク上のノードが蓄積している統計情報や管理情報（ＭＩＢ：Management Information Base）を要求・取得するためのプロトコルである。ＳＮＭＰによる推定方法では、ＳＮＭＰを用いて、調査ノードからネットワーク上の各ノードに対してＭＩＢの情報を要求・取得しそれを統合することで、ネットワークトポロジーを推定する。なおノードが保持している情報の取得方法、及びその取得に用いるプロトコルにはそれぞれ異なるものが存在するが、ここではＳＮＭＰによる推定方法はそのような異なるものも含む意味で用いている。
【０００７】
ルーティングプロトコルとは、ネットワークの経路情報を交換するためのプロトコルである。ルーティングプロトコルの中でも例えばリンクステート型と言われるプロトコルでは、ネットワークのトポロジー情報とそのコスト情報をノード間で交換することができる。このため、ルーティングプロトコルのキャプチャによる推定方法では、調査ノードにてその交換用のパケットをキャプチャすることでトポロジーを推定する。リンクステート型のルーティングプロトコルの代表的なものとしてＯＳＰＦ（Open Shortest Path First）がある。
【０００８】
上記方法のうち、tracerouteやSNMPによる推定方法では調査ノードからネットワークに対して調査パケット（あるいはリクエスト）を送信する必要がある。このような推定方法のことはアクティブ探索方法と呼ばれる。ネットワークはその管理の方針から、例えばネットワーク管理者により調査のためのパケット送信が制限される場合がある。そのような場合、アクティブ探索方法を用いてネットワークトポロジーを推定することはできない。
【０００９】
また上記方法のうちのルーティングプロトコルのキャプチャによる推定方法は、ネットワークにリンクステート型のルーティングプロトコルのパケットが流れていなければならないが、そのようなネットワークは多くはないのが実情である。したがってこの推定方法は汎用性が低く、ネットワークトポロジーの推定に使用できない可能性が高い。
【００１０】
このようなことから、ネットワークトポロジーの推定では、調査パケット、或いはルーティングプロトコルのパケットといった特別なパケットの送信を前提としないことが望ましいと言える。つまり、ネットワークトポロジーは、ネットワークを流れる普通のパケットから推定することが望ましいと言える。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００２−７７１６１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本発明は、ネットワークを流れる通常のパケットから、ネットワークトポロジーを高精度に推定（特定）するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
開示の１装置では、サブネットが相互に連結された構成のネットワークを流れるパケットを取得し、パケットを送信したサブネットである送信元サブネット毎に、取得したパケットから、そのパケットが経由したノードの数であるホップ数、及びそのパケットの送信上のボトルネックとなっているボトルネック帯域を特定すると共に、パケットをロスするロス障害を検出し、特定したホップ数、及びボトルネック帯域を基に、ネットワークに存在するサブネットのなかで送信元サブネットとして確認されたサブネットをトポロジーツリー上に配置し、ロス障害の検出結果を用いて、トポロジーツリー上に配置したサブネットのなかで該配置が不適切なサブネットを抽出し、該抽出したサブネットの配置を変更する。そのようにして、ネットワークトポロジーの推定（特定）結果として、ネットワークの構成を模擬したトポロジーツリーを作成する。
【発明の効果】
【００１４】
開示の１装置は、ネットワークに流れる通常のパケットから、ネットワークトポロジーを高精度に推定、つまりネットワークの構成を模擬したトポロジーツリーを高精度に作成することができる。
【図面の簡単な説明】
【００１５】
【図１】本実施形態によるトポロジーツリー作成装置が適用されたネットワークのシステム構成を説明する図である。
【図２】本実施形態によるトポロジーツリー作成装置の機能構成を説明する図である。
【図３】パケットのヘッダのフォーマットを説明する図である。
【図４】ＴＣＰヘッダのフォーマットを説明する図である。
【図５】サブネット管理情報リストの構成を説明する図である。
【図６】ＴＣＰコネクション管理情報リストの構成を説明する図である。
【図７】トポロジー情報の構成を説明する図である。
【図８】同時ロス障害発生拠点リストの構成を説明する図である。
【図９】トポロジーツリーの作成・更新方法を説明する図である。
【図１０】ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数と同じ場合のトポロジーツリーへの操作例を説明する図である。
【図１１】ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数より小さい場合のトポロジーツリーへの操作例を説明する図である。
【図１２】ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数より大きい場合のトポロジーツリーへの操作例を説明する図である。
【図１３Ａ】パケット解析処理のフローチャートである。
【図１３Ｂ】パケット解析処理のフローチャートである。
【図１３Ｃ】パケット解析処理のフローチャートである。
【図１４Ａ】トポロジーツリー構成処理のフローチャートである。
【図１４Ｂ】トポロジーツリー構成処理のフローチャートである。
【図１５】本実施形態を適用可能なコンピュータのハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について、図面を参照しながら詳細に説明する。
図１は、本実施形態によるトポロジーツリー作成装置が適用されたネットワークのシステム構成を説明する図である。
【００１７】
大規模なネットワークは普通、複数の小規模のネットワーク（サブネット）が相互に連結された構成となっている。図１のネットワーク１も、多数のサブネットを相互に連結した構成となっている。それにより、ネットワーク１上を流れるパケットを転送するノードであるルータ１１を多数、備えている。
【００１８】
本実施形態によるトポロジーツリー作成装置は、接続された箇所のネットワーク１上を流れる通常のパケットを監視し、監視のために取得したパケットから、ネットワーク１のトポロジーを推定（特定）する。このトポロジーツリー作成装置は、ネットワーク１上に発生した障害等を監視するためのネットワーク監視装置２０上に搭載された形で実現されている。このことから以降、特に断らない限り、ネットワーク監視装置２０はトポロジーツリー作成装置を指す意味で用いる。
【００１９】
図２は、本実施形態によるネットワーク監視装置（トポロジーツリー作成装置）２０の機能構成を説明する図である。図２に示すようにネットワーク監視装置２０は、パケットキャプチャ部２１、ホップ数解析部２２、ボトルネック帯域解析部２３、ロス（loss）障害検出部２４、サブネット情報判定部２５、及びトポロジーツリー構成部２６と、を備えた構成となっている。
【００２０】
パケットキャプチャ部２１は、ネットワーク１上を流れるパケットをキャプチャ（取得）し、キャプチャしたパケットをそれぞれホップ数解析部２２、ボトルネック帯域解析部２３及びロス障害検出部２４に渡す。
【００２１】
ホップ数解析部２２は、渡されたパケットのヘッダを参照した解析により、そのパケットを送信元のサブネットが送信してから通過したノードの数であるホップ数を推定（特定）する。そのノードとは、ＧＷ（GateWay）装置、或いはルータ１１等である。ここでは便宜的に、そのノードとしては、代表的なルータ１１のみを想定する。
【００２２】
図３は、パケットのヘッダのフォーマットを説明する図である。図３に示すように、パケットのヘッダには、そのパケットを送信したデータ処理装置（コンピュータ）を示す送信元アドレス、そのパケットの最終的な送信先のデータ処理装置を示す宛先アドレスをそれぞれ格納するフィールド以外にも、多くのフィールドが存在する。その一つとして、ＴＴＬフィールドがある。以降、パケットの送信元、或いは宛先のデータ処理装置は「ホスト」と総称する。
【００２３】
そのＴＴＬフィールドに格納された値は、ルータ１１を通過する度に１ずつ減算される。その値が０となったパケットは、転送することなく破棄される。パケットを送信するホストは、その初期値として、そのホストが実行するＯＳ（オペレーティングシステム）の種類（ＯＳ種別）に応じた値を格納するのが普通である。その値とは、例えば３１、１２７、或いは２５５などである。このことからホップ数解析部２２は、パケットヘッダのＴＴＬフィールドの値を用いた解析により、ホップ数を推定する。
【００２４】
ネットワーク監視装置２０は、同一の箇所を流れるパケットを監視する。このため、同一サブネット内のホストからそれぞれ送信されたパケットが通過したルータ１１の数は同じか、或いは近い数となる。これは、ＴＴＬフィールドの値（ＴＴＬ値）は、初期値に応じて狭い範囲内に収まることを意味する。つまり、そのルータ数（ホップ数）をｘとすると、ＴＴＬ値には、３１−ｘ、１２７−ｘ、及び２５５−ｘのうちの何れかにより算出される値に偏りが発生する。このことから、ホップ数解析部２２は、サブネット毎、及び送信元ホスト毎に、ＴＴＬ値を用いた逆算によりホップ数、更にはＯＳ種別を推定（特定）する。推定したホップ数、及びＯＳ種別は、サブネット管理情報テーブル３１に格納する。
【００２５】
パケットの伝送には、その伝送速度に応じた時間が掛かる。例えば１５００バイト長のパケットでは、１０M[bps]の伝送速度を持つ回線で伝送する場合には１２[msec]、１Ｇ[bps]の伝送速度を持つ回線であれば０．０１２[msec]の伝送時間がそれぞれ掛かる。また、あるノード１１で回線の伝送速度が１Ｇ[bps]から１０M[bps]に変化する場合、１５００バイト長のパケットが連続して転送されてきたとしても、受信側と送信側とで伝送時間が異なるため、当該ノードで送信待ちとなるパケットが発生することになる。反対に、あるノードで回線の伝送速度が１０M[bps]から１G[bps]に変化する場合には、伝送時間の違いにより、受信待ちとなるパケットが発生することになる。パケットのサイズ（バイト数）は、パケットヘッダにパケット長として格納されている。
【００２６】
このようなことから、受信側と送信側とで伝送速度が異なれば、結果として、遅い方の伝送速度（ボトルネック帯域）でパケットは転送されることになる。パケットヘッダのパケット長が示すサイズのパケットをキャプチャしてから次のパケットをキャプチャするまでの時間は、ボトルネック帯域に応じた長さとなる。例えば１５００バイト長のパケットを観測してから次のパケットを観測するまでの時間が１．２[msec]であれば、ボトルネック帯域は１０M[bps]と推定することができる。ボトルネック帯域解析部２３は、このようにして、ホスト毎にボトルネック帯域を推定する。この推定したボトルネック帯域も同様に、サブネット管理情報テーブル３１に格納される。
【００２７】
図４は、ＴＣＰヘッダのフォーマットを説明する図である。図４に示すように、ＴＣＰ（Transmission Control Protocol）など信頼性のある通信を行うプロトコルでは、そのプロトコル用のヘッダがパケットに格納される。そのヘッダには、通信の一貫性を確保するための番号（シーケンス番号）が格納されるシーケンス番号フィールドが設けられている。送信元ホストは、シーケンス番号として、各パケットに送信順を示す値をそのフィールドに格納する。それにより宛先ホストは、受信したパケットのシーケンス番号から、失われたパケットの存在、及び実際に失われたパケットを特定することができる。
【００２８】
ロス障害検出部２４は、例えば送信元ホスト毎に、送信元ホストから宛先ホストに送信されたパケットの総数、及び失われたパケットの総数を取得し、その比率（＝失われたパケットの総数／送信されたパケットの総数）をロス率として求める。そのようにして求めたロス率を所定の閾値と比較することにより、ロス障害を検出する。それにより、求めたロス率が閾値を越えている場合に、ロス障害が発生したと判定する。このロス障害の判定結果も同様に、サブネット管理情報テーブル３１に格納される。ロス障害が発生したか否かを判定するための閾値は以降「ロス判定閾値」と呼ぶことにする。ロス障害は、これ以外の方法を用いて検出するようにしても良い。
【００２９】
図５は、サブネット管理情報リスト３１の構成を説明する図である。この管理情報リスト３１は、サブネット毎に、サブネット管理情報、つまりそのサブネットから送信されたパケットを観測して得られた情報、及びその情報を解析して得られた推定結果を保存・管理するためのものである。図５に示すように、表形式で表した場合、ホップ数推定、ＬＡＮ／ＷＡＮ、ロス検知、及び推定結果のカラム（項目）を持つデータ構造となっている。理解を容易にするために、図５には１サブネット分のサブネット管理情報のみを示している。
【００３０】
ＬＡＮ／ＷＡＮカラムには、ホスト毎にエントリが作成される。ホップ数推定カラム、ロス検知カラム、及び推定結果カラムは、ＬＡＮ／ＷＡＮカラムのエントリ毎に、一つ以上のエントリが作成されるようになっている。それにより、推定したホップ数、及びＯＳ種別の組み合わせ毎に、観測結果等を管理・保存可能になっている。
【００３１】
ホップ数推定カラムにはＯＳ種別、ホップ数、パケット数のサブカラムがある。パケット数サブカラムには、送信元ホストから送信されたパケットの総数が格納される。
ＬＡＮ／ＷＡＮカラムにはホスト、及びＬＡＮ／ＷＡＮ区別のサブカラムがある。ホストサブカラムには、送信元ホストのアドレス（ホストアドレス）、ＬＡＮ／ＷＡＮ区別サブカラムには、推定したボトルネック帯域から判定したサブネットの種類が格納される。本実施形態では、推定したボトルネック帯域を所定の閾値と比較することにより、サブネットをＬＡＮ及びＷＡＮの何れかと判定する。それにより、推定したボトルネック帯域が閾値を越えていればサブネットは伝送速度が高速なＬＡＮと判定する。この閾値は以降「ＬＡＮ／ＷＡＮ判定閾値」と呼ぶことにする。推定したボトルネック帯域によるサブネットの種類の分類は、ＬＡＮ／ＷＡＮの二者択一とは異なるものであっても良い。つまり３つ以上の種類のなかから選択するようにしても良い。
【００３２】
このように二者択一によりサブネットの種類を判定するのは、ボトルネック帯域として推定した数値をそのまま扱う必要性は低いからである。パケットが他のサブネットを経由している場合、ボトルネック帯域の推定にはパケットが通過した全てのサブネットが影響を及ぼす。それにより、推定したボトルネック帯域には、比較的に大きな誤差が生じやすい。このことも理由の一つである。
【００３３】
ロス検知カラムには、ホスト、及びロス有無のサブカラムがある。ロス有無サブカラムには、上記のように求めたロス率から判定したロス障害の有無を示す情報を格納するようになっている。図５に表記の「無」はロス障害が発生していないと判定、つまりロス障害を検出していないことを表している。ロス障害が発生していると判定した場合にはその旨を示す内容が格納される。以降、ロス障害が発生していないと判定した場合に書き込む情報は「無」、ロス障害が発生していると判定した場合に書き込む情報は「有」とそれぞれ表記する。
【００３４】
推定結果カラムには、ホップ数、ＬＡＮ／ＷＡＮ区別、ロス有無のサブカラムがある。各サブカラムは、対応するサブネット全体に対する最終的な推定結果が格納される。このため、他のカラムの同名のサブカラムに格納された内容とは必ずしも一致しない。
【００３５】
周知のように、ＴＣＰ／ＩＰでコンピュータの住所を表すアドレス（ＩＰアドレス）は、そのコンピュータが存在するサブネットのアドレス(ネットワークアドレス)と、サブネット内でのそのコンピュータ自身のアドレス(ホストアドレス)から構成されている。このことから、サブネット管理情報リスト３１において、１サブネット分のサブネット管理情報はネットワークアドレスにより特定される。
【００３６】
図６は、ＴＣＰコネクション管理情報リストの構成を説明する図である。このリストは、キャプチャしたパケットが送受信されるＴＣＰコネクション毎に、そのＴＣＰコネクションに係わる情報（ＴＣＰコネクション管理情報）を保存するためのものである。図６には便宜的に、１サブネット分のみ示している。各エントリ（レコード）には、ＴＣＰコネクション管理情報として、送信元／送信先のアドレス／ポート番号の組、ＬＡＮ／ＷＡＮ区分、及びロス有無が格納される。他には、特には図示していないが、最後に受信したパケットのシーケンス番号、受信したパケットの総数（以降「受信パケット総数」と呼ぶ）、及び失われたパケットの総数（累算値。以降「喪失パケット総数」と呼ぶ）を格納するようになっている。それにより、ＴＣＰコネクション毎に、ＬＡＮ／ＷＡＮ区分、及びロス有無の各サブカラムの内容を格納するようにしている。
【００３７】
上述したように、図５に示すサブネット管理情報テーブル３１は、ホップ数解析部２２、ボトルネック帯域解析部２３、及びロス障害検出部２４によって更新される。図６に示すＴＣＰコネクション管理情報リストは、例えばロス障害検出部２４によって更新される。
【００３８】
パケットキャプチャ部２１、ホップ数解析部２２、ボトルネック帯域解析部２３、及びロス障害検出部２４は、パケットをキャプチャし、キャプチャしたパケットから必要な情報を抽出し、抽出した情報を用いた各種推定を行う解析部分を構成する。サブネット情報判定部２５及びトポロジーツリー構成部２６は、この解析部分により得られたサブネット管理情報テーブル３１を参照し、ネットワーク１のトポロジーの構成を推定するトポロジーツリー構成部分を構成する。本実施形態では、ネットワーク１のトポロジー構成は、その構成を模擬したツリー（トポロジーツリー）で表現するようにしている。このトポロジーツリーは、ネットワーク監視装置２０から見た場合のものである。
【００３９】
サブネット情報判定部２５は、例えば一定時間毎に、サブネット管理情報テーブル３１を参照することにより、サブネット管理情報テーブル３１が更新されたか否か判定する。それにより、テーブル３１に何らかの更新が行われた場合には、その旨をトポロジーツリー構成部２６に通知する。
【００４０】
トポロジーツリー構成部２６は、サブネット管理情報テーブル３１に登録されたサブネットをノードとして配置したトポロジーツリーを作成・更新する。作成、或いは更新したトポロジーツリーは、トポロジー情報３２として出力、或いは保存する。サブネット、つまりノードの配置は、ホップ数、及びボトルネック帯域（サブネットの種類）を考慮して決定する。
【００４１】
ボトルネック帯域は、パケットが経由するサブネットがＬＡＮ及びＷＡＮの何れであるかによって変化する。ロス障害が発生したサブネットを経由したパケットには、ロスが生じる。このことから、サブネットのなかでロス障害の影響を受けたサブネットを抽出することにより、パケットが経由するサブネットを絞り込むことができる。その絞り込みの結果から、現在のトポロジーツリーのなかで不適切な部分を修正することができる。それにより、トポロジーツリーの更新には、サブネットの追加の他に、既に存在するサブネットの配置を変更する再配置も含まれる。
【００４２】
図９は、トポロジーツリーの作成・更新方法を説明する図である。図９（ａ）はトポロジーツリーの初期状態、図９（ｂ）はパケットが観測されたサブネットを配置した後のトポロジーツリー例、図９（ｃ）はロス障害の発生によりサブネットの配置を変更した後のトポロジーツリー例をそれぞれ示している。図９中の各ノード３０は、パケットが観測されたサブネットに相当する。実際には各ノード３０はそれぞれルータ１１に相当する。
【００４３】
本実施形態では、図９（ａ）に示すように、初期状態のトポロジーツリーは主ツリー（幹）が１本あり、そこからＷＡＮと推定したサブネット群を配置したブランチ（ＷＡＮブランチ）が１本だけ分岐している構成としている。主ツリーは、全てＬＡＮのサブネットが接続されたパケットの伝送経路を示すものとしている。
【００４４】
各ブランチは、ブランチ管理情報を用いて管理している。このブランチ管理情報は、例えば当該ブランチを一意に特定できる識別情報の他に、当該ブランチが主ツリー、或いは他のブランチから分岐する地点（ノード）のネットワーク監視装置２０を基準にしたホップ数（分岐ホップ数）、及びブランチを構成する各ノードを示すノード情報を含む情報である。識別情報としては、例えば当該ブランチを構成する少なくとも１サブネットのネットワークアドレス、或いは全サブネットのネットワークアドレスの組を採用することができる。分岐ホップ数は、当該ブランチのなかで最もネットワーク監視装置２０に近いノード（サブネット）のネットワーク監視装置２０を基準にしたホップ数から１を引いた値である。各ノードのノード情報は、各ノードのネットワークアドレス、或いは一意に割り当てられるノードＩＤ等を採用することができる。このようなブランチ管理情報を１つ予め用意しておくことにより、初期状態のトポロジーツリーが作成可能となる。
【００４５】
ホストアドレスは、サブネットのネットワークアドレスに、そのサブネットに属するホストによって異なる数字列を付加した形となっている。このことから、ネットワークアドレスは、ホストアドレスから必要な部分のみを抽出することで得られる。
【００４６】
図９（ｂ）には、先頭に「１９２．１６８」の数字列を付した４つのノード３０ａ〜ｄを示している。これらのノード３０ａ〜ｄは、パケットが観測されたサブネットに相当する。各数字列は、それぞれ、各サブネットのネットワークアドレス、或いはホストアドレスを表している。ノード３０ａ及び３０ｂは、ボトルネック帯域からＬＡＮと判定したサブネットに相当し、ノード３０ｃ及び３０ｄは、ＷＡＮと判定したサブネットに相当する。このことから、ノード３０ａ及び３０ｂは、主ツリー上のホップ数によって特定される位置にそれぞれ配置され、ノード３０ｃ及び３０ｄは、ＷＡＮブランチ上のホップ数によって特定される位置にそれぞれ配置されている。末端に位置するリーフノードは全て、パケットが観測されたサブネットに相当する。ノード３０ｃを含むブランチの分岐ホップ数は５である。
【００４７】
このようにして本実施形態では、推定したボトルネック帯域によりサブネット（ノード３０。実際にはサブネットを経由する際に中継するルータ１１）のトポロジーツリー上の配置可能な位置を制限している。それにより、推定したボトルネック帯域に矛盾が生じないように、サブネットを配置する。そのようにサブネットを配置可能な位置を制限するため、その制限を設けない場合と比較して、各サブネットはより適切に配置することができる。以降、サブネット（ノード３０）の位置関係は、ネットワーク監視装置２０を基点として表現する。それにより、ネットワーク監視装置２０に近い側は前側と表現し、ホップ数は、ネットワーク監視装置２０から見た場合の値で表現する。
【００４８】
例えばパケットの送信に要する送信時間自体は、パケットが経由した個々のサブネットの伝送速度を推定できる情報ではない。このため、上記のような制限を設けることはできない。このため、各サブネットを配置する精度は低いものとなる。
【００４９】
図９（ｃ）には、新たにノード３０ｅが追加されている。ノード３０ｃ及び３０ｅは、ノード３０ｄを有するＷＡＮブランチとは別の同じノード３０ｖから分岐させたＷＡＮブランチとしている。これは、例えばノード３０ｃ及び３０ｅにそれぞれ相当するサブネットから送信されたパケットの観測により、それらのサブネットでのみロス障害の発生が確認されたためである。そのようにして本実施形態では、既存のブランチを構成する一部のノードに相当するサブネットのロス障害を検出した場合、そのノード全てを有するブランチを生成することにより、ロス障害の検出結果に矛盾しないようにノードの再配置を実現させている。
【００５０】
ノード３０ｅの前の配置は、例えばノード３０ｄの直前の位置である。その前の配置では、相当するサブネットのホップ数は７、ノード３０ｄに相当するサブネットのホップ数は８である。そのような位置関係（接続関係）が実際に存在していれば、ノード３０ｃに相当するサブネットにロス障害が発生した場合には、ノード３０ｄに相当するサブネットが送信したパケットにもロス障害の影響が生じることになる。このことから、ノード３０ｄに相当するサブネットが送信したパケットからロス障害が観測されなければ、そのサブネットから送信されたパケットはノード３０ｅに相当するサブネットを経由することなく伝送されると解釈することができる。これは、現在のノード３０ｄ、及び３０ｅを伝送経路とする配置は不適切であることを意味する。このため、新たにＷＡＮブランチを生成（追加）し、既に存在する２つのノード３０ｃ及び３０ｅを追加したＷＡＮブランチに移動させる配置の変更（再配置）を行っている。
【００５１】
このようにして本実施形態では、発生したロス障害から、そのロス障害が影響する範囲のサブネットの接続関係を推定することにより、推定したネットワーク１のトポロジー（トポロジーツリー）のなかで不適切に配置されたノードを抽出し、その配置を修正するようにしている。ロス障害は、どのサブネットでも発生しうる。時間の経過に伴い、ロス障害が発生していないサブネットの数は少なくなる。このため、最終的には、高精度にトポロジーを推定、つまり高精度なトポロジーツリーを作成することができることとなる。以降ノードは、特に断らない限り、サブネットと同じ意味で用いる。
【００５２】
作成したトポロジーツリーは、トポロジー情報３２として出力、或いは保存される。図７は、そのトポロジー情報３２の構成を説明する図である。
このトポロジー情報３２は、図７に示すように、ノード毎のノード管理情報をまとめたものである。このノード管理情報は、対応するノードの他のノードとのトポロジーツリー上の接続関係等を表すものである。本実施形態では、このノード管理情報は、自ノードに割り当てられたノードＩＤ、親ノード（ネットワーク監視装置２０から見て前側のノード）の親ノードＩＤ、子ノード（ネットワーク監視装置２０から見て後側のノード）の子ノードＩＤ、ホップ数、ＬＡＮ／ＷＡＮ区別、及び含まれるサブネットのアドレスを備えた構成となっている。ホップ数は、ネットワーク監視装置２０を基準にしたものであり、ホップ数の１はネットワーク監視装置２０（ルートノードに相当）から見て１番目のノードであることを表している。含まれるサブネットのアドレスは、ネットワークアドレスである。
【００５３】
子ノードＩＤの数は、トポロジーツリー上の配置によって変化する。例えばリーフノードでは端に位置しているため、存在しないか、或いは１つの定められた値となる。ブランチが接続されたノードでは、接続されたブランチの数に応じて、子ノードＩＤの数は増える。例えば図９（ｃ）のノード３０ｖでは、子ノードＩＤの数は３となる。それら以外のノードでは、子ノードＩＤの数は１である。
【００５４】
パケットが観測されたノードは、推定されたホップ数に従って配置する。パケットが観測されたノードを配置するだけでは、推定されたホップ数に従って配置できない場合がある。具体的には、例えばパケットが観測されたサブネットが一つだけであり、そのサブネットで推定されたホップ数が１０であった場合、そのサブネットの前に９つのパケットが観測されていないサブネットを配置しなければならない。このことから、含まれるサブネットとして格納するネットワークアドレスは、パケットが観測されたサブネットか否かを示すデータとなっている。図７中の“unknown”は、パケットが観測されていないサブネットであることを示している。トポロジーツリー上に不適切に配置したノードの抽出は、パケットが観測されたサブネットのノードのみが対象となる。
【００５５】
トポロジー情報３２はこのような構成である。このため、トポロジーツリーの作成（更新を含む）は、直前の内容から、一つ以上のノード管理情報の操作、つまり追加、削除、或いは更新を行うことに相当する。
【００５６】
図８は、同時ロス障害発生拠点リストの構成を説明する図である。このリストは、ロス障害の発生に対応するために作成するものであり、サブネット毎に、そのアドレス、ホップ数、及びＬＡＮ／ＷＡＮ区別を１エントリ（レコード）に格納した構成である。
【００５７】
トポロジーツリー構成部２６は、サブネット管理情報テーブル３１を参照し、推定結果カラムのロス有無サブカラムが「有」となっているサブネット管理情報をすべて抽出し、同時ロス障害発生拠点リストを作成する。それにより、トポロジーツリーの更新は、このリストも用いて行う。
【００５８】
図１３Ａ〜Ｃは、パケット解析処理のフローチャートである。この解析処理は、ネットワーク１を流れるパケットを観測し、その観測により得られる情報を解析するためにネットワーク監視装置２０が実行する処理を抜粋して示したものである。この解析処理内に示す処理ステップは、そのための機能を搭載したプログラム（パケット監視プログラム）をネットワーク監視装置２０が実行することにより実現される。解析部分を構成するパケットキャプチャ部２１、ホップ数解析部２２、ボトルネック帯域解析部２３、及びロス障害検出部２４は、このプログラムをネットワーク監視装置２０が実行する結果、実現される。次に図１３Ａ〜Ｃを参照して、この解析処理について詳細に説明する。
【００５９】
この解析処理において、パケットキャプチャ部２１はステップＳ１を実行することにより実現される。同様に、ホップ数解析部２２はステップＳ１１〜Ｓ１７、ボトルネック帯域解析部２３はステップＳ２１〜Ｓ２９、ロス障害検出部２４はステップＳ３１〜Ｓ３８をそれぞれ実行することにより実現される。実際には、例えばステップＳ１１〜Ｓ１７、ステップＳ２１〜Ｓ２９、及びステップＳ３１〜Ｓ３８は、それぞれ異なるサブプログラムにより実行され、それらのサブプログラムは、例えばステップＳ１が実行される処理により呼び出されて実行される。
【００６０】
先ず、ステップＳ１では、ネットワーク１を流れるパケットをキャプチャする。それにより、パケットをキャプチャできた場合、ステップＳ１１、Ｓ２１及びＳ３１以降の処理がそれぞれ実行される。これらステップＳ１１、Ｓ２１及びＳ３１への各移行は、パケットキャプチャ部２１がキャプチャしたパケットをホップ数解析部２２、ボトルネック帯域解析部２３及びロス障害検出部２４にそれぞれ渡すことに相当する。特には図示していないが、パケットをキャプチャできなかった場合には、ここでパケット解析処理を終了するようになっている。キャプチャしたパケットは以降「受信パケット」と呼ぶことにする。
【００６１】
ステップＳ１１以降では、以下の処理が実行される。
先ず、ステップＳ１１では、サブネットマスク情報３５を参照して、受信パケットからサブネット情報、つまり受信パケットを送信した送信元サブネットのネットワークアドレスを抽出する。このサブネットマスク情報３５は、受信パケットに格納された送信元アドレスのなかでネットワークアドレスの範囲を表すものである。このことからネットワークアドレスの抽出は、受信パケットの送信元アドレスからサブネットマスク情報３５が示す範囲のアドレスを取り出すことで行われる。そのようにしてネットワークアドレスを抽出した後はステップＳ１２に移行する。
【００６２】
ステップＳ１２では、抽出したネットワークアドレスを持つサブネット管理情報がサブネット管理情報リスト３１に存在しているか否か判定する。ホストサブカラムのデータとして格納されたアドレスのなかにそのネットワークアドレスを含むものが存在する場合、判定はＹＥＳとなってステップＳ１４に移行する。そのようなアドレスが存在しない場合、判定はＮＯとなってステップＳ１３に移行し、受信パケットを送信した送信元サブネットのサブネット管理情報を作成し、サブネット管理情報リスト３１に格納する。その後はステップＳ１４に移行する。ここで作成されるサブネット管理情報は、送信元アドレスであり、その送信元アドレスの格納は、サブネット管理情報リスト３１のＬＡＮ／ＷＡＮカラム、及びロス検知カラムにそれぞれ１エントリ（レコード）を追加して行われる。
【００６３】
ステップＳ１４では、上述したようにして、受信パケットのＴＴＬフィールドの値から、ホップ数、及びＯＳ種別の推定を実施する。次にステップＳ１５に移行し、推定したホップ数とＯＳ種別の組み合わせが既存のものか否か判定する。その組み合わせが対応するサブネット管理情報のホップ数推定カラムのエントリに存在する場合、判定はＹＥＳとなってステップＳ１７に移行する。その組み合わせが存在しない場合には、判定はＮＯとなってステップＳ１６に移行し、ホップ数推定カラムに１エントリを追加して、推定したホップ数、及びＯＳ種別を格納する。その後ステップＳ１７に移行する。
【００６４】
ホップ数、及びＯＳ種別の推定では通常、複数の受信パケットを必要とする。このため、ホップ数、及びＯＳ種別は、推定できるとは限らない。このことから、推定するまでの間、ホップ数、及びＯＳ種別として、推定できていないことを示すデータを格納するようにしている。ここではそのデータも“unknown”と呼ぶことにする。
【００６５】
ステップＳ１７では、ホップ数推定カラムのパケット数サブカラムの値をインクリメントする。それにより、このパケット数サブカラムには、サブネットから送信されたパケットのなかで実際に受信したパケットの総数が格納される。そのインクリメントを行った後、ステップＳ１１以降の一連の処理を終了する。
【００６６】
次に、図１３Ｂを参照して、ステップＳ２１以降の処理について詳細に説明する。
このステップＳ２１では、受信パケットから送信元アドレス、ポート番号、送信先アドレス、ポート番号を抽出する。続くステップＳ２２では、抽出した送信元／送信先のアドレス・ポート番号の組を用いてＴＣＰコネクション管理リストを検索することにより、その組を持つＴＣＰコネクション情報が存在するか否か判定する。その組を持つＴＣＰコネクション情報が存在する場合、判定はＹＥＳとなってステップＳ２４に移行する。そのようなＴＣＰコネクション情報が存在しない場合、判定はＮＯとなってステップＳ２３に移行し、その組を持つＴＣＰコネクション情報を作成し、ＴＣＰコネクション情報リストに追加する。その後はステップＳ２４に移行する。この時点で作成するＴＣＰコネクション情報では、ＬＡＮ／ＷＡＮ区分としてＬＡＮ、ロス有無として「無」を初期値として設定する。
【００６７】
ステップＳ２４では、上述したようにして、ボトルネック帯域の推定を実施し、その実施結果からＬＡＮ／ＷＡＮ区別を判定する。次のステップＳ２５では、判定したＬＡＮ／ＷＡＮ区別の内容を、ＴＣＰコネクション管理情報リストの当該エントリ（ＴＣＰコネクション管理情報）におけるＬＡＮ／ＷＡＮ区別カラムの内容と比較することにより、判定結果が変動しているか否か判定する。それらＬＡＮ／ＷＡＮ区別の内容が異なる場合、判定はＹＥＳとなってステップＳ２６に移行する。それらの内容が一致する場合には、判定はＮＯとなり、ここでステップＳ２１以降の一連の処理を終了する。
【００６８】
ステップＳ２６では、ＴＣＰコネクション管理情報リストの当該エントリのＬＡＮ／ＷＡＮ区別カラムに新しい値、つまり今回の判定結果を上書きする。この判定結果は、サブネット管理情報リスト３１における、ＬＡＮ／ＷＡＮカラムのホストサブカラムに送信元アドレスを格納したエントリのＬＡＮ／ＷＡＮ区別サブカラムの内容としても記入する。続くステップＳ２７では、サブネット管理情報リスト３１からＬＡＮ／ＷＡＮカラムのエントリを読み出し、そのエントリのホストサブカラムのデータとして、受信パケットの送信元アドレスが存在するか否か判定する。その送信元アドレスが何れかのエントリのホストサブカラムのデータとして存在していた場合、判定はＹＥＳとなってステップＳ２９に移行する。その送信元アドレスが存在していなかった場合、判定はＮＯとなってステップＳ２８に移行し、ＬＡＮ／ＷＡＮカラム、及びロス検知カラムにそれぞれ１エントリを追加し、各カラムのホストサブカラムのデータとして送信元アドレスを格納する。ステップＳ２９にはその後に移行する。
【００６９】
ステップＳ２９では、受信パケットの送信元アドレスを持つエントリのＬＡＮ／ＷＡＮ区別サブカラムの内容の書き換えを行う。その書き換えを行った後、ステップＳ２１以降の一連の処理は終了する。
【００７０】
上記書き換えは、受信パケットの送信元アドレスを用いたＴＣＰコネクション管理情報リストの検索によってエントリを抽出し、抽出したエントリのＬＡＮ／ＷＡＮ区別カラムの内容から、書き込むべきＬＡＮ／ＷＡＮ区別サブカラムの内容を特定することで行う。その特定は、例えばＴＣＰコネクション管理情報リストから抽出したエントリのＬＡＮ／ＷＡＮ区別カラムの内容として多いほうを選択する、或いはその内容としてＬＡＮが一つでも存在していればＬＡＮを選択することで行う。後者は、通常、伝送速度は遅くなることはあっても早くなることはないという考えによるものである。その特定は、これら以外の方法を用いて行うようにしても良い。
【００７１】
最後に、図１３Ｃを参照して、ステップＳ３１以降の処理について詳細に説明する。
このステップＳ３１では、受信パケットから送信元アドレス、ポート番号、送信先アドレス、ポート番号を抽出する。続くステップＳ３２では、抽出した送信元／送信先のアドレス・ポート番号の組を用いてＴＣＰコネクション管理情報リストを検索し、その組を格納したエントリを抽出する。その抽出後はステップＳ３３に移行する。
【００７２】
ステップＳ３３では、抽出したエントリの受信パケット総数のインクリメント、或いは喪失パケット総数の更新を行うと共に、発生したロス障害の検出を行う。その検出は、上述したように、抽出したエントリに格納されている喪失パケット総数を受信パケット総数で割ることによってロス率を算出し、算出したロス率をロス判定閾値と比較して行う。その後はステップＳ３４に移行する。
【００７３】
失われたパケットが発生した場合、抽出したエントリのシーケンス番号と受信パケットのシーケンス番号には２以上の差が生じる。このことから、喪失パケット数の更新は、その差から１を引いた値（＝差−１）を求め、現在の喪失パケット総数に加算することで行われる。過去に発生したロス障害が長い期間、影響しないようにするために、受信パケット総数、及ぶ喪失パケット総数は、例えば一定時間毎にクリアすることが望ましい。
【００７４】
ステップＳ３４では、検出結果をＴＣＰコネクション管理リストの当該エントリにおけるロス有無カラムの内容と比較することにより、ロス障害の検出結果は変動しているか否か判定する。それらの内容が一致していた場合、判定はＮＯとなり、ここでステップＳ３１以降の一連の処理を終了する。それらの内容が一致していなかった場合には、判定はＹＥＳとなってステップＳ３５に移行する。
【００７５】
ステップＳ３５では、当該エントリのロス有無カラムの内容として検出結果を上書きする。次のステップＳ３６では、サブネット管理情報リスト３１を参照し、受信パケットの送信元アドレスをＬＡＮ／ＷＡＮカラムのホストサブカラムのデータとして格納したものが有るか否か判定する。その送信元アドレスをホストサブカラムのデータとするエントリが存在した場合、判定はＹＥＳとなってステップＳ３８に移行する。そのようなエントリが存在しない場合、判定はＮＯとなってステップＳ３７に移行し、ＬＡＮ／ＷＡＮカラムに１エントリを作成して、少なくともその送信元アドレスをホストサブカラムのデータとして格納する。その後、ステップＳ３８に移行する。
【００７６】
ステップＳ３８では、上記送信元アドレスを格納したエントリのロス有無サブカラムのデータとして、ロス障害の検出結果を書き込む。その書き込みの後、ステップＳ３１以降の一連の処理を終了する。
【００７７】
図１４Ａ及びＢは、トポロジーツリー構成処理のフローチャートである。この構成処理は、サブネット管理情報リスト３１を参照して、ネットワーク１のトポロジーを模擬するトポロジーツリーの作成、或いは更新するためにネットワーク監視装置２０が実行する処理を抜粋して示したものである。この構成処理内で実行される処理ステップは、そのための機能を搭載したプログラム（トポロジーツリー構成プログラム）をネットワーク監視装置２０が実行することにより実現される。トポロジーツリー構成部分のトポロジーツリー構成部２６は、このプログラムをネットワーク監視装置２０が実行する結果、実現される。次に図１４Ａ及びＢを参照して、この構成処理について詳細に説明する。
【００７８】
この構成処理では、実際には、例えば図１４ＡのステップＳ４１〜Ｓ５１、及び図１４ＢのステップＳ６１〜Ｓ７１は、それぞれ異なるサブプログラムの実行によって実現される。それにより、この構成処理として、２つのサブルーチン処理をまとめて示している。
【００７９】
図１３ＡのステップＳ１が実行される処理は例えばメインルーチン処理であり、そのメインルーチン処理では、例えば一定時間毎に、サブネット管理情報リスト３１の更新を確認するための処理を実行するようになっている。この構成処理として実行される２つのサブルーチン処理は、その確認結果に応じてメインルーチン処理に呼び出されて実行される。その呼び出しは、サブネット情報判定部２５がサブネット管理情報テーブル３１の更新をトポロジーツリー構成部２６に通知することに相当する。
【００８０】
始めに、ステップＳ４１〜Ｓ５１の一連の処理について説明する。この一連の処理は、対象とするサブネットを変更しながら、ロス障害を考慮せずにそのサブネットをトポロジーツリー上に配置するための処理である。これに対し、ステップＳ６１からＳ７１の一連の処理は、トポロジーツリー上のサブネットの配置を、検出されたロス障害に応じて変更するための処理である。ステップＳ４１〜Ｓ５１の一連の処理は、トポロジー情報３２を作成するための処理に相当し、ステップＳ６１からＳ７１の一連の処理は、作成されたトポロジー情報３２を更新するための処理に相当する。
【００８１】
先ず、ステップＳ４１では、対象とするサブネット、つまりサブネット管理情報を選択し、ホップ数推定カラムのエントリのなかにホップ数サブカラムとして格納されたホップ数が異なるエントリが存在するか否か判定する。各エントリに格納されたホップ数が全て同じでなかった場合、判定はＹＥＳとなってステップＳ４３に移行する。全てのエントリでホップ数が同じであった場合には、判定はＮＯとなり、ステップＳ４２でそのホップ数を推定結果コラムのホップ数サブカラムとして格納すべきものと決定する。その後はステップＳ４５に移行する。
【００８２】
ステップＳ４３では、ホップ数推定カラムのエントリのなかにＯＳ種別サブカラムが“unknown”となっているエントリがあるか否か判定する。そのようなエントリが存在する場合、判定はＹＥＳとなってステップＳ４４に移行し、そのエントリを無視して、つまりＯＳ種別サブカラムが“unknown”となっていないエントリのみを対象にしてホップ数を決定する。その後はステップＳ４５に移行する。その決定には、例えばホップ数のなかで最も多いホップ数を選択する、或いはパケット数サブカラムの値が最大のエントリのホップ数を選択する、といった方法を採用すれば良い。一方、ＯＳ種別サブカラムが“unknown”となっているエントリが存在しない場合には、判定はＮＯとなり、ホップ数の推定に対応不可能な誤差が生じているとして、その旨を通知するためのエラー出力を行った後、ステップＳ４１以降の一連の処理を終了する。
【００８３】
ステップＳ４５では、ＬＡＮ／ＷＡＮカラムのエントリのなかにＬＡＮ／ＷＡＮ区別サブカラムの内容がＬＡＮとなっているものが一つでもあるか否か判定する。ＬＡＮ／ＷＡＮ区別サブカラムがＬＡＮとなっているエントリが存在する場合、判定はＹＥＳとなり、ステップＳ４６で推定結果カラムのＬＡＮ／ＷＡＮ区別サブカラムの内容としてＬＡＮを書き込む。その後ステップＳ５０に移行する。そのようなエントリが存在しない場合には、つまり全てのエントリのＬＡＮ／ＷＡＮ区別サブカラムの内容がＷＡＮとなっている場合には、判定はＮＯとなってステップＳ４７に移行する。
【００８４】
このようにして本実施形態では、ＬＡＮ／ＷＡＮ区別サブカラムの内容がＬＡＮとなっているエントリが一つでも存在していれば、サブネットはＬＡＮであると判定する。これは、サブネットのホストのなかに何らかの理由（例えば低速のハブに接続させている、トラフィックが一時的に異常に増大した、といったようなもの）によって伝送速度が遅くなっているものが存在する可能性が考えられるためである。ホスト毎にＬＡＮ／ＷＡＮの分類をするのはこのためである。そのようにホスト毎に分類を行うことにより、サブネットの分類（ボトルネック帯域の推定）をより高精度に行うことができる。
【００８５】
ステップＳ４７では、推定結果カラムのＬＡＮ／ＷＡＮ区別サブカラムとしてＷＡＮを書き込む。続くステップＳ４８では、新たにホップ数を決定したノードの属するＷＡＮブランチの先頭に位置するノードのホップ数（以降「最小ホップ数」と呼ぶ）がより小さい値に更新されているか否か判定する。この最小ホップ数から１を引いた値が当該ＷＡＮブランチのブランチ管理情報として管理する分岐ホップ数より小さい値に更新されている場合、判定はＹＥＳとなってステップＳ４９に移行し、この分岐ホップ数を現在の最小ホップ数から１を引いた値に更新する。この更新により、ＷＡＮブランチを分岐させるノード（以降、ブランチを分岐させるノードを「分岐ノード」と総称する）をネットワーク監視装置２０側に移動させる。その後、ステップＳ５０に移行する。その最小ホップ数から１を引いた値が分岐ホップ数以上の値に更新されている場合には、判定はＮＯとなってステップＳ５０に移行する。それにより、分岐ノードの移動は回避させる。
【００８６】
ステップＳ５０では、ブランチ管理情報を参照し、決定したホップ数、及びＬＡＮ／ＷＡＮの分類に応じて、トポロジーツリー上にサブネット（ノード）を配置する。このとき、主ツリー、或いはブランチにサブネットを配置すべき場所が存在しない場合、ブランチを生成し、生成したブランチに配置する。このことから、サブネットの配置は、対応するノード管理情報の追加、及びその配置が影響する他のサブネットのノード管理情報を更新することで行われる。次のステップＳ５１では、未処理のサブネットのためのループを実現させる処理を実行する。その処理とは、例えば未処理のサブネットが存在するか否か判定する判定処理である。そのような判定処理をステップＳ５１で実行する場合、未処理のサブネットが存在すると判定はＹＥＳとなり、上記ステップＳ４１に戻る。未処理のサブネットが存在しないと判定はＮＯとなり、ここでステップＳ４１以降の一連の処理を終了する。
【００８７】
このようにして本実施形態では、既存のトポロジー情報３２を更新するのではなく、新たにトポロジー情報３２を作成するようにしている。これは、或るサブネットにおけるホップ数やＬＡＮ／ＷＡＮ区別の推定結果の変化が他のサブネットの配置に及ぼす影響が特定し難いからである。その影響が及ぼす範囲を正確に特定し、その範囲内のサブネットのみを対象に配置を変更する形でトポロジー情報３２を更新（作成）しても良い。配置を決定するうえでブランチ管理情報を参照するのは、既に生成したブランチにノードを配置した結果は更新すべき理由が発生しない限り、更新しないようにしているためである。そのようにして、更新すべき理由が発生しない限り、過去に作成したトポロジーツリーを再現できるようにしている。
【００８８】
ここで、新たにトポロジー情報３２を作成することによって生じるトポロジーツリーへの操作、つまり直前のトポロジーツリーからの変更について、例を挙げて具体的に説明する。その変更は、新たにパケットが観測されたサブネットが発生した場合、無条件で行われる。そのようなサブネットが発生していない場合には、変更内容はステップＳ５０に移行する前に実行するステップの処理によって異なる。
【００８９】
新たにパケットが観測されたサブネットが発生した場合、決定されたホップ数、及びＬＡＮ／ＷＡＮの分類結果に応じて、そのサブネットに相当するノードを配置すべき位置を特定し、配置する。このとき、ＬＡＮ／ＷＡＮの分類結果、及びホップ数が同じサブネットが既にトポロジーツリー上に存在していれば、新たにブランチを作成し、作成したブランチに配置することになる。トポロジーツリー上に配置可能な場所が存在していれば、その場所に配置することになる。その場所が既存のブランチに存在していれば、そのブランチのブランチ管理情報は更新されることとなる。そのようにして新たに配置することから、ノード管理情報は追加され、その配置が影響する他のノードのノード管理情報は更新されることとなる。
【００９０】
ステップＳ４６、或いはＳ４８からステップＳ５０に移行した場合、対象とするサブネットで決定されたホップ数、及びＬＡＮ／ＷＡＮの分類結果に応じて、そのサブネットに相当するノードを配置すべき位置を特定し、配置する。このとき、ＬＡＮ／ＷＡＮの分類結果、及びホップ数が同じサブネットが既にトポロジーツリー上に存在していれば、ブランチを作成し、作成したブランチ上に配置すべきサブネットを配置することになる。このため、ブランチを追加する操作が行われる可能性が存在することとなる。
【００９１】
上述したように、伝送速度が何らかの理由によって低下している可能性が考えられることから、ＬＡＮ／ＷＡＮの分類は、ホスト毎に行っている。このことから、ＬＡＮ／ＷＡＮ区別サブカラムの内容がＷＡＮ→ＬＡＮに更新される可能性が存在する。ＷＡＮと分類したサブネット（ノード）はブランチ上に配置しなければならない。しかし、ＬＡＮと分類したサブネットは、他のＬＡＮと分類したサブネットを考慮して、主ツリー上、或いはブランチ上に配置する。このため、ステップＳ４６からステップＳ５０に移行した場合には、ＬＡＮ／ＷＡＮ区別サブカラムの内容がＷＡＮ→ＬＡＮに更新されたケースの操作を行う可能性がある。その操作とは、例えば新たにＬＡＮと分類したサブネットをＷＡＮブランチ上から主ツリー、或いは他のブランチ上に移動させるようなものである。このため、そのような操作を行う場合、配置を変更するノード、及びその変更が影響する他のノードのノード管理情報に加えて、ブランチ管理情報も更新されることとなる。
【００９２】
図９（ｂ）に示す状態では、ＷＡＮブランチはノード３０ａの次のノード３０ｖ、つまりネットワーク監視装置２０から５ホップ目のノード（分岐ホップ数が５であるノード）３０ｖを分岐ノードとして主ツリーから分岐している。ステップＳ４９での分岐させるサブネットの移動、つまり分岐ホップ数の更新は、例えばノード３０ａを新たな分岐ノードとしてＷＡＮブランチを分岐させるような操作に相当する。この場合、結果として、トポロジー情報３２のなかでＷＡＮブランチを構成するノードの全て、及びその分岐ノード３０ａのノード管理情報は直前の内容とは異なるものとなる。これは、全てのノードで少なくともホップ数を更新しなければならないからである。ブランチ管理情報も更新される。
【００９３】
次に図１４Ｂを参照して、ステップＳ６１〜Ｓ７１の一連の処理について詳細に説明する。
ステップＳ６１〜Ｓ７１の一連の処理は、１サブネットを対象に実行される部分を示したものである。それにより、ステップＳ６１〜Ｓ７１の一連の処理もステップＳ４１〜Ｓ５１の一連の処理と同様に、対象とするサブネットを順次、変更していくことにより、サブネット毎に実行される。
【００９４】
上述したように、或るサブネットでロス障害が発生している場合、そのサブネット以外に、そのサブネットを経由してパケットが伝送される他のサブネットもロス障害が発生していると見なされる。このようなことから、発生したロス障害は、パケットの伝送経路となっているサブネット群（リーフノードに相当するサブネットにロス障害が発生したような場合には１サブネットである）を特定するうえで極めて有用な情報である。ステップＳ６１〜Ｓ７１の一連の処理は、このことに着目し、ロス障害のトモグラフィ分析を用いて、ネットワーク１のロス障害が影響する部分のトポロジーを推定（特定）し、その推定結果を既存のトポロジーツリーに反映させるための処理である。
【００９５】
先ず、ステップＳ６１では、ロス検知カラムにおける、対象とするサブネットの各エントリのロス有無サブカラムのデータを参照し、１つでも「無」となっているものがあるか否か判定する。対象とするサブネットに属するホスト毎にロス障害を検出した結果、少なくとも１ホストからロス障害が検出されなかった場合、判定はＹＥＳとなり、ここでステップＳ６１以降の一連の処理を終了する。全てのホストからロス障害が検出された場合には、判定はＮＯとなってステップＳ６２に移行する。
【００９６】
ステップＳ６１の判定がＹＥＳとなった場合、実際には上記ステップＳ５１と同様の処理が実行される。それにより、他の対象としていないサブネットを対象にした処理が行われることになる。これは、「終了」と表記した端子を移行先とする他のステップの処理でも同様である。しかし、ここでは便宜的に、ステップＳ５１と同様の処理については言及しないこととする。
【００９７】
ステップＳ６２では、推定結果カラムのロス有無サブカラムのデータとして「有」を記入する。次のステップＳ６３では、ロス有無サブカラムのデータとして「有」が記入されているエントリ、つまりロス障害が発生しているサブネットを全て抽出し、抽出したサブネットを同時ロス障害発生拠点リストに記入（登録）する。そのようにして、同時ロス障害発生拠点リストを新たに作成した後に移行するステップＳ６４では、記入したサブネットが全てＬＡＮ、或いはＷＡＮで統一されているか否か判定する。記入したサブネットを全てＬＡＮ、或いはＷＡＮと推定していなかった場合、判定はＮＯとなってステップＳ６９に移行する。記入したサブネットが全てＬＡＮ、或いはＷＡＮと推定していた場合には、判定はＹＥＳとなってステップＳ６５に移行する。
【００９８】
このようにして本実施形態では、ロス検知カラムのエントリのなかでロス有無サブカラムの内容が「無」となっているものが１つでも存在していると、サブネット全体ではロス障害が発生していないと見なすようにしている。これは、送信元ホストに発生した不具合によってロス障害を検出してしまう可能性があるためである。言い換えれば、実際にロス障害が発生しているサブネットを高精度に検出するためである。
【００９９】
ステップＳ６５では、同時ロス障害発生拠点リストに記入したサブネット群（一つ以上のサブネット）における最小のホップ数を抽出し、必要に応じて、そのホップ数から１を減算した値をホップ数とするノードを分岐ノードとしたブランチを生成し、このブランチにそのサブネット群を移動（再配置）させる。その移動は以下のようにして行われる。ここでは、図９を参照して具体的に説明する。
【０１００】
図９（ｂ）において、例えばＷＡＮブランチのノード３０ｄにのみロス障害が検出された場合、ノード３０ｄはその直前のノードを分岐ノードとするブランチに移動させる。ノード３０ｄの後に位置するリーフノードで推定したホップ数との矛盾を生じさせないために、移動させるノード３０ｄの元の位置には別のノードを配置する。ＷＡＮブランチの先頭から２つのノードでロス障害がそれぞれ検出された場合、それら２つのノードは新たに作成するＷＡＮブランチに移動し、その移動に合わせて元のＷＡＮブランチには２つのノードを新たに配置する。それにより、図９（ｃ）に示すような状態に更新する。同様に、主ツリーのノード３０ｂにのみロス障害が検出された場合には、ノード３０ｂはその直前のノードを分岐ノードとするブランチ（ＬＡＮブランチ）に移動させ、ノード３０ｂの元の位置には別のノードを配置する。一方、ＷＡＮブランチを構成する全てのノード、或いはリーフノードから連なる１つ以上のノード（例えばノード３０ｄ及びその後のリーフノードといった繋がり）でロス障害が検出された場合には、ブランチを生成する必要がないことから、移動は行わない。
【０１０１】
このようにして本実施形態では、必要に応じてブランチを生成し、ロス障害が検出された１つ以上のノードをそのブランチに移動させることにより、ロス障害から推定したサブネット間の接続関係をトポロジーツリーに反映させる。それにより、より精度の高いトポロジーツリーを得ることができる。
【０１０２】
ブランチを生成した場合には、当該ブランチのブランチ管理情報の作成、移動させるノード、及びその移動が影響するノードのノード管理情報の更新、当該ブランチに移動させるノードが配置されていたブランチのブランチ管理情報の更新等が合わせて行われる。
【０１０３】
ステップＳ６５に続くステップＳ６６では、ロス障害が検出されたサブネット群はＷＡＮか否か判定する。同時ロス障害発生拠点リストに記入したサブネットが何れもＷＡＮと判定したいた場合、判定はＹＥＳとなってステップＳ６７に移行する。記入したサブネットの少なくとも一つをＬＡＮと判定していた場合には、判定はＮＯとなり、ここでステップＳ６１以降の一連の処理を終了する。
【０１０４】
ステップＳ６７では、ノードを移動させたＷＡＮブランチの最小ホップ数がその移動によって更新されているか否か判定する。このＷＡＮブランチの先頭に位置するノードを新たに生成したＷＡＮブランチに移動させるような場合、最小ホップ数から１を引いた値は分岐ホップ数より大きい値となる。このため、判定はＹＥＳとなってステップＳ６８に移行し、分岐ホップ数を現在の最小ホップ数から１を引いた値に更新する。その後、ステップＳ６１以降の一連の処理を終了する。ＷＡＮブランチの先頭に位置するノードを新たに生成したＷＡＮブランチに移動させない場合には、最小ホップ数は分岐ホップ数と同じ値となる。このため、判定はＮＯとなり、ここでステップＳ６１以降の一連の処理を終了する。
【０１０５】
ステップＳ６９では、ロス障害が検出されているサブネット群における最小のホップ数はそのサブネット群を構成する少なくとも１サブネットのノードが配置された既存のブランチの最小ホップ数と同じ、若しくは小さいか否か判定する。その最小のホップ数から１を引いた値が当該ブランチのブランチ管理情報として保持する分岐ホップ数以下であった場合、判定はＹＥＳとなってステップＳ７０に移行する。その最小のホップ数から１を引いた値が分岐ホップ数より大きい場合には、判定はＮＯとなってステップＳ７１に移行する。それにより、ステップＳ７０、及びＳ７１の処理を実行した後、ステップＳ６１以降の一連の処理を終了する。
【０１０６】
ステップＳ７０及びＳ７１では、トポロジーツリー上のロス障害が検出されたサブネットのノードを再配置する操作のための処理が行われる。この再配置の操作例について、図１０〜図１２を参照して具体的に説明する。
【０１０７】
先ず、図１０及び図１１を参照して、ステップＳ７０の処理により行われる操作について説明する。
図１０は、ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数と同じ場合の操作例を説明する図である。図１０において、ノード３０ｆ〜ｈはロス障害が検出されたサブネットに相当する。操作前のノード３０ｆ〜ｈの配置は、例えばノード３０ｆ及び３０ｇはそれぞれノード３０ｉ及び３０ｊの位置であり、ノード３０ｈはノード３０ｉの位置にあったノード３０ｆを分岐ノードとするブランチ上である。これらのノード３０ｆ〜ｈは、ノード３０ｖを分岐ノードとして生成したブランチに再配置する操作により、図１０に示す位置に変更されている。ノード３０ｆ及び３０ｇの再配置により、元の位置には新たにノード３０ｉ及び３０ｊが配置されている。これらノード３０ｉ及び３０ｊは、ノード３０ｆ及び３０ｇと同じく、ＬＡＮと分類されるサブネット用である。
【０１０８】
この例では、トポロジー情報３２中のノード管理情報はノード３０ｇ及び３０ｄのものが更新され、ノード３０ｉ及び３０ｊのものが作成（追加）される。ブランチ管理情報は、新たにノード３０ｉが配置されたブランチでは更新され、新たに生成したブランチでは作成される。
【０１０９】
図１１は、ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数より小さい場合の操作例を説明する図である。図１１では、ロス障害が検出された２つのサブネット群に対してそれぞれ操作を行った後の状態例を表している。この２つのサブネット群に相当するノード群は、ノード３０ｆ〜ｈ（以降「第１のノード群」）と、ノード３０ｄが配置されたブランチを構成するノード群（以降「第２のノード群」）とである。これら２つのノード群は、ロス障害が検出される前は例えば図１０に示すように配置されていたものである。
【０１１０】
第１のノード群は、最小ホップ数（＝分岐ホップ数＋１）が６から３に更新されている。このため、分岐ノードはノード３０ｖからノード３０ｗに移動させている。第２のノード群は、最小ホップ数が６から４に更新されている。このため、分岐ノードはノード３０ｖからノード３０ｕに移動させている。これらのようなホップ数の変化は、例えば何らかの理由により迂回する形でパケットが伝送されていた場合に生じる。
【０１１１】
第２のノード群を構成するノード３０ｄのホップ数は、この移動に係わらず変化していない。このことから、最小ホップ数の差（＝２＝６−４）の数だけノードをノード３０ｄの前に追加している。そのようにして、各ノードで決定したホップ数はトポロジーツリー上で維持させている。
【０１１２】
ステップＳ７０では、上述したような操作をトポロジーツリーに対して実現させるための処理が行われる。その操作内容に応じて、更新すべきブランチ管理情報の更新、及びトポロジー情報３２中の更新すべきノード管理情報の更新等が合わせて行われる。
【０１１３】
次に、図１２を参照して、ステップＳ７１の処理により行われる操作について説明する。この図１２は、ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数より大きい場合の操作例を説明する図である。図１２において、ロス障害の検出により再配置したノードはノード３０ｆ及び３０ｈである。この２つのノード３０ｆ及び３０ｈのそれぞれの元の位置は、例えば図１０に示す位置である。
【０１１４】
本実施形態では、ロス障害が検出されたサブネット群のなかで最小のホップ数が既存のブランチの最小ホップ数より大きい場合、ＬＡＮ／ＷＡＮとで分けて、再配置を行うようにしている。このため、ノード３０ｆ及び３０ｈはそれぞれ生成したブランチ上に再配置し、それらノード３０ｆ及び３０ｈを配置していたブランチは消去している。ノード３０ｆのホップ数は６から７に更新され、ノード３０ｈのホップ数は７から８に更新されている。このことから、ノード３０ｆは、ノード３０ｘを分岐ノードとするブランチを生成し、この生成したブランチ上に移動させている。同様にノード３０ｈは、ノード３０ｊを分岐ノードとするブランチを生成し、この生成したブランチ上に移動させている。
【０１１５】
ステップＳ７１では、上述したような操作をトポロジーツリーに対して実現させるための処理が行われる。その操作内容に応じて、作成すべきブランチ管理情報の作成、削除すべきブランチ管理情報の削除、及び更新すべきノード管理情報の更新等が合わせて行われる。
【０１１６】
本実施形態では、上述したような内容のトポロジーツリー構成処理を随時、例えば一定時間間隔で繰り返し実行する。その繰り返しの実行により、ノードの配置、或いは／及び、再配置、並びにブランチの追加、消去、或いは／及び、移動、が随時、行われる。その結果、作成されるトポロジーツリーは正確なものに徐々に修正されていくことになる。それにより、修正が行われない、或いはその修正がほとんど行われなくなった場合には、高精度なトポロジーツリーが得られていることとなる。
【０１１７】
ロス障害を利用して不適切な配置を解消するための操作は、実際には、図９〜図１２を参照して説明した操作以外にも数多く存在する。このことから、上記の操作例は一例であり、操作はこれに限定されるものではない。
【０１１８】
本実施形態によるプログラム（トポロジーツリー作成プログラム）は、図１３Ａ〜Ｃに示すパケット解析処理を実現させるパケット解析プログラム、並びに図１４Ａ及びＢに示すトポロジーツリー構成処理を実現させるトポロジーツリー構成プログラムをそれぞれサブプログラムとして含むものである。図２に示す機能構成は、ネットワーク監視装置２０として用いられるコンピュータに、本実施形態によるプログラムを実行させることで実現される。ここで図１５を参照して、本実施形態を適用可能なコンピュータ、つまりこのプログラムを実行することでネットワーク監視装置２０（トポロジーツリー作成装置）として使用可能なコンピュータについて具体的に説明する。
【０１１９】
図１５に示すコンピュータは、ＣＰＵ６１、メモリ６２、入力装置６３、出力装置６４、外部記憶装置６５、媒体駆動装置６６、及びネットワーク接続装置６７を有し、これらがバス６８によって互いに接続された構成となっている。図１５に示す構成は一例であり、これに限定されるものではない。
【０１２０】
ＣＰＵ６１は、当該コンピュータ全体の制御を行う。
メモリ６２は、プログラムの実行、データ更新等の際に、外部記憶装置６５（あるいは可搬型の記録媒体７０）に記憶されているプログラムあるいはデータを一時的に格納するＲＡＭ等の半導体メモリである。ＣＰＵ６１は、プログラムをメモリ６２に読み出して実行することにより、全体の制御を行う。
【０１２１】
入力装置６３は、例えば、キーボード、マウス等の操作装置と接続可能なインターフェースである。接続された操作装置に対するユーザの操作を検出し、その検出結果をＣＰＵ６１に通知する。
【０１２２】
出力装置６４は、例えば表示装置と接続された表示制御装置である。ネットワーク接続装置６７は、例えばネットワーク１を介した通信、及びそのネットワーク１を流れるパケットの受信を行えるものである。外部記憶装置６５は、例えばハードディスク装置である。主に各種データやプログラムの保存に用いられる。
【０１２３】
媒体駆動装置６６は、光ディスクや光磁気ディスク等の可搬型の記録媒体７０にアクセスするものである。
【０１２４】
上記トポロジーツリー作成プログラムは、外部記憶装置６５、若しくは記録媒体７０に記録されているか、或いはネットワーク１を介してネットワーク接続装置６７により取得される。そのトポロジーツリー作成プログラムをメモリ６２に読み出してＣＰＵ６１が実行することにより、ネットワーク監視装置２０に搭載されたトポロジーツリー作成装置は実現される。サブネット管理情報３１、トポロジー情報３２、及びサブネットマスク情報３５は、例えば外部記憶装置６５に保存され、必要に応じてメモリ６２に読み出される。トポロジー情報３２の出力は、例えば出力装置６４を介した表示、ネットワーク接続装置６７を介した外部装置への送信、或いは媒体駆動装置６６を介した記録媒体７０への格納によって行われる。
【０１２５】
このトポロジーツリー作成プログラムが外部記憶装置６５に格納されていると想定した場合、パケットキャプチャ部２１は、ＣＰＵ６１、メモリ６２、外部記憶同意６５、ネットワーク接続装置６７及びバス６８によって実現される。他のホップ数解析部２２、ボトルネック帯域解析部２３、ロス障害検出部２４、サブネット情報判定部２５及びトポロジーツリー構成部２６は共に、例えばＣＰＵ６１、メモリ６２、外部記憶同意６５、及びバス６８によって実現される。
【０１２６】
なお、本実施形態は、ネットワーク監視装置２０上に搭載させた形で実現させているが、別の装置上に実現させても良い。専用の装置として実現させても良い。また、サブネット管理情報、或いはトポロジーツリーを更新する手順は、上述したようなものに限定されない。例えば検出されたロス障害により判明した不適切な配置は、ロス障害が検出されたノードの配置を変更することで解消するのではなく、ロス障害が検出されていないノードの配置を変更することで解消しても良い。不適切な配置を解消する方法も特に限定されるものではない。
【符号の説明】
【０１２７】
１ ネットワーク
１１ ルータ（ノード）
２０ ネットワーク監視装置
２１ パケットキャプチャ部
２２ ホップ数解析部
２３ ボトルネック帯域解析部
２４ ロス障害検出部
２５ サブネット情報判定部
２６ トポロジーツリー構成部
３１ サブネット管理情報リスト
３２ トポロジー情報
【技術分野】
【０００１】
本発明は、サブネットが相互に連結された構成のネットワークのトポロジーを特定するための技術に関する。
【背景技術】
【０００２】
現在、インターネットに代表されるネットワークは、各種サービスを提供するために幅広く用いられている。そのサービスでは、パケットの伝送経路上にスイッチの故障やルータでの輻輳等による障害が発生すると、パケットの受信品質が大きく低下する。例えばパケットロス率が大きくなると、パケットの再送信が必要になることから、パケットの送信に必要な時間がより長くなる、といった不具合が発生する。このことから、伝送経路（ネットワーク）上に発生した障害には迅速に対応することが重要となっている。それにより、ネットワークのトポロジーを把握することは、障害解析上、大変重要となっている。
【０００３】
ネットワークでは、ネットワークを設計構築する設計構築部門と運用管理（障害対応）する運用管理部門とが別々となっていることは多い。運用管理部門は、障害対応に際してネットワークの正確なトポロジー情報を入手できないことは多い。状態解析を実施しようとするネットワークのユーザも、やはりトポロジー情報の入手は困難であるのが普通である。このようなことから近年では、ネットワークのトポロジーを特定（推定）する技術が検討されている。
【０００４】
ネットワークのトポロジーを推定する従来のトポロジー推定方法は、３つに大別される。即ち、tracerouteによる推定方法、ＳＮＭＰ（Simple Network Management Protocol）による推定方法、及びルーティングプロトコルのキャプチャによる推定方法、の３つである。
【０００５】
tracerouteはネットワーク上のある観測地点（調査ノード）から任意の宛先ノードまでの転送経路を、調査ノードからの調査パケットの送信、及びその応答から調べる調査ツール（プログラム）である。それにより、tracerouteによる推定方法では、このツールを多数の宛先ノードに使用し、各宛先ノードで得られた結果を統合することで調査ノードからのネットワークトポロジーを推定する。ここでは、tracerouteとはそのような調査パケットを用いる調査ツールの総称として表記している。
【０００６】
ＳＮＭＰとはネットワーク上のノードが蓄積している統計情報や管理情報（ＭＩＢ：Management Information Base）を要求・取得するためのプロトコルである。ＳＮＭＰによる推定方法では、ＳＮＭＰを用いて、調査ノードからネットワーク上の各ノードに対してＭＩＢの情報を要求・取得しそれを統合することで、ネットワークトポロジーを推定する。なおノードが保持している情報の取得方法、及びその取得に用いるプロトコルにはそれぞれ異なるものが存在するが、ここではＳＮＭＰによる推定方法はそのような異なるものも含む意味で用いている。
【０００７】
ルーティングプロトコルとは、ネットワークの経路情報を交換するためのプロトコルである。ルーティングプロトコルの中でも例えばリンクステート型と言われるプロトコルでは、ネットワークのトポロジー情報とそのコスト情報をノード間で交換することができる。このため、ルーティングプロトコルのキャプチャによる推定方法では、調査ノードにてその交換用のパケットをキャプチャすることでトポロジーを推定する。リンクステート型のルーティングプロトコルの代表的なものとしてＯＳＰＦ（Open Shortest Path First）がある。
【０００８】
上記方法のうち、tracerouteやSNMPによる推定方法では調査ノードからネットワークに対して調査パケット（あるいはリクエスト）を送信する必要がある。このような推定方法のことはアクティブ探索方法と呼ばれる。ネットワークはその管理の方針から、例えばネットワーク管理者により調査のためのパケット送信が制限される場合がある。そのような場合、アクティブ探索方法を用いてネットワークトポロジーを推定することはできない。
【０００９】
また上記方法のうちのルーティングプロトコルのキャプチャによる推定方法は、ネットワークにリンクステート型のルーティングプロトコルのパケットが流れていなければならないが、そのようなネットワークは多くはないのが実情である。したがってこの推定方法は汎用性が低く、ネットワークトポロジーの推定に使用できない可能性が高い。
【００１０】
このようなことから、ネットワークトポロジーの推定では、調査パケット、或いはルーティングプロトコルのパケットといった特別なパケットの送信を前提としないことが望ましいと言える。つまり、ネットワークトポロジーは、ネットワークを流れる普通のパケットから推定することが望ましいと言える。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００２−７７１６１号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
本発明は、ネットワークを流れる通常のパケットから、ネットワークトポロジーを高精度に推定（特定）するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
開示の１装置では、サブネットが相互に連結された構成のネットワークを流れるパケットを取得し、パケットを送信したサブネットである送信元サブネット毎に、取得したパケットから、そのパケットが経由したノードの数であるホップ数、及びそのパケットの送信上のボトルネックとなっているボトルネック帯域を特定すると共に、パケットをロスするロス障害を検出し、特定したホップ数、及びボトルネック帯域を基に、ネットワークに存在するサブネットのなかで送信元サブネットとして確認されたサブネットをトポロジーツリー上に配置し、ロス障害の検出結果を用いて、トポロジーツリー上に配置したサブネットのなかで該配置が不適切なサブネットを抽出し、該抽出したサブネットの配置を変更する。そのようにして、ネットワークトポロジーの推定（特定）結果として、ネットワークの構成を模擬したトポロジーツリーを作成する。
【発明の効果】
【００１４】
開示の１装置は、ネットワークに流れる通常のパケットから、ネットワークトポロジーを高精度に推定、つまりネットワークの構成を模擬したトポロジーツリーを高精度に作成することができる。
【図面の簡単な説明】
【００１５】
【図１】本実施形態によるトポロジーツリー作成装置が適用されたネットワークのシステム構成を説明する図である。
【図２】本実施形態によるトポロジーツリー作成装置の機能構成を説明する図である。
【図３】パケットのヘッダのフォーマットを説明する図である。
【図４】ＴＣＰヘッダのフォーマットを説明する図である。
【図５】サブネット管理情報リストの構成を説明する図である。
【図６】ＴＣＰコネクション管理情報リストの構成を説明する図である。
【図７】トポロジー情報の構成を説明する図である。
【図８】同時ロス障害発生拠点リストの構成を説明する図である。
【図９】トポロジーツリーの作成・更新方法を説明する図である。
【図１０】ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数と同じ場合のトポロジーツリーへの操作例を説明する図である。
【図１１】ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数より小さい場合のトポロジーツリーへの操作例を説明する図である。
【図１２】ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数より大きい場合のトポロジーツリーへの操作例を説明する図である。
【図１３Ａ】パケット解析処理のフローチャートである。
【図１３Ｂ】パケット解析処理のフローチャートである。
【図１３Ｃ】パケット解析処理のフローチャートである。
【図１４Ａ】トポロジーツリー構成処理のフローチャートである。
【図１４Ｂ】トポロジーツリー構成処理のフローチャートである。
【図１５】本実施形態を適用可能なコンピュータのハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施形態について、図面を参照しながら詳細に説明する。
図１は、本実施形態によるトポロジーツリー作成装置が適用されたネットワークのシステム構成を説明する図である。
【００１７】
大規模なネットワークは普通、複数の小規模のネットワーク（サブネット）が相互に連結された構成となっている。図１のネットワーク１も、多数のサブネットを相互に連結した構成となっている。それにより、ネットワーク１上を流れるパケットを転送するノードであるルータ１１を多数、備えている。
【００１８】
本実施形態によるトポロジーツリー作成装置は、接続された箇所のネットワーク１上を流れる通常のパケットを監視し、監視のために取得したパケットから、ネットワーク１のトポロジーを推定（特定）する。このトポロジーツリー作成装置は、ネットワーク１上に発生した障害等を監視するためのネットワーク監視装置２０上に搭載された形で実現されている。このことから以降、特に断らない限り、ネットワーク監視装置２０はトポロジーツリー作成装置を指す意味で用いる。
【００１９】
図２は、本実施形態によるネットワーク監視装置（トポロジーツリー作成装置）２０の機能構成を説明する図である。図２に示すようにネットワーク監視装置２０は、パケットキャプチャ部２１、ホップ数解析部２２、ボトルネック帯域解析部２３、ロス（loss）障害検出部２４、サブネット情報判定部２５、及びトポロジーツリー構成部２６と、を備えた構成となっている。
【００２０】
パケットキャプチャ部２１は、ネットワーク１上を流れるパケットをキャプチャ（取得）し、キャプチャしたパケットをそれぞれホップ数解析部２２、ボトルネック帯域解析部２３及びロス障害検出部２４に渡す。
【００２１】
ホップ数解析部２２は、渡されたパケットのヘッダを参照した解析により、そのパケットを送信元のサブネットが送信してから通過したノードの数であるホップ数を推定（特定）する。そのノードとは、ＧＷ（GateWay）装置、或いはルータ１１等である。ここでは便宜的に、そのノードとしては、代表的なルータ１１のみを想定する。
【００２２】
図３は、パケットのヘッダのフォーマットを説明する図である。図３に示すように、パケットのヘッダには、そのパケットを送信したデータ処理装置（コンピュータ）を示す送信元アドレス、そのパケットの最終的な送信先のデータ処理装置を示す宛先アドレスをそれぞれ格納するフィールド以外にも、多くのフィールドが存在する。その一つとして、ＴＴＬフィールドがある。以降、パケットの送信元、或いは宛先のデータ処理装置は「ホスト」と総称する。
【００２３】
そのＴＴＬフィールドに格納された値は、ルータ１１を通過する度に１ずつ減算される。その値が０となったパケットは、転送することなく破棄される。パケットを送信するホストは、その初期値として、そのホストが実行するＯＳ（オペレーティングシステム）の種類（ＯＳ種別）に応じた値を格納するのが普通である。その値とは、例えば３１、１２７、或いは２５５などである。このことからホップ数解析部２２は、パケットヘッダのＴＴＬフィールドの値を用いた解析により、ホップ数を推定する。
【００２４】
ネットワーク監視装置２０は、同一の箇所を流れるパケットを監視する。このため、同一サブネット内のホストからそれぞれ送信されたパケットが通過したルータ１１の数は同じか、或いは近い数となる。これは、ＴＴＬフィールドの値（ＴＴＬ値）は、初期値に応じて狭い範囲内に収まることを意味する。つまり、そのルータ数（ホップ数）をｘとすると、ＴＴＬ値には、３１−ｘ、１２７−ｘ、及び２５５−ｘのうちの何れかにより算出される値に偏りが発生する。このことから、ホップ数解析部２２は、サブネット毎、及び送信元ホスト毎に、ＴＴＬ値を用いた逆算によりホップ数、更にはＯＳ種別を推定（特定）する。推定したホップ数、及びＯＳ種別は、サブネット管理情報テーブル３１に格納する。
【００２５】
パケットの伝送には、その伝送速度に応じた時間が掛かる。例えば１５００バイト長のパケットでは、１０M[bps]の伝送速度を持つ回線で伝送する場合には１２[msec]、１Ｇ[bps]の伝送速度を持つ回線であれば０．０１２[msec]の伝送時間がそれぞれ掛かる。また、あるノード１１で回線の伝送速度が１Ｇ[bps]から１０M[bps]に変化する場合、１５００バイト長のパケットが連続して転送されてきたとしても、受信側と送信側とで伝送時間が異なるため、当該ノードで送信待ちとなるパケットが発生することになる。反対に、あるノードで回線の伝送速度が１０M[bps]から１G[bps]に変化する場合には、伝送時間の違いにより、受信待ちとなるパケットが発生することになる。パケットのサイズ（バイト数）は、パケットヘッダにパケット長として格納されている。
【００２６】
このようなことから、受信側と送信側とで伝送速度が異なれば、結果として、遅い方の伝送速度（ボトルネック帯域）でパケットは転送されることになる。パケットヘッダのパケット長が示すサイズのパケットをキャプチャしてから次のパケットをキャプチャするまでの時間は、ボトルネック帯域に応じた長さとなる。例えば１５００バイト長のパケットを観測してから次のパケットを観測するまでの時間が１．２[msec]であれば、ボトルネック帯域は１０M[bps]と推定することができる。ボトルネック帯域解析部２３は、このようにして、ホスト毎にボトルネック帯域を推定する。この推定したボトルネック帯域も同様に、サブネット管理情報テーブル３１に格納される。
【００２７】
図４は、ＴＣＰヘッダのフォーマットを説明する図である。図４に示すように、ＴＣＰ（Transmission Control Protocol）など信頼性のある通信を行うプロトコルでは、そのプロトコル用のヘッダがパケットに格納される。そのヘッダには、通信の一貫性を確保するための番号（シーケンス番号）が格納されるシーケンス番号フィールドが設けられている。送信元ホストは、シーケンス番号として、各パケットに送信順を示す値をそのフィールドに格納する。それにより宛先ホストは、受信したパケットのシーケンス番号から、失われたパケットの存在、及び実際に失われたパケットを特定することができる。
【００２８】
ロス障害検出部２４は、例えば送信元ホスト毎に、送信元ホストから宛先ホストに送信されたパケットの総数、及び失われたパケットの総数を取得し、その比率（＝失われたパケットの総数／送信されたパケットの総数）をロス率として求める。そのようにして求めたロス率を所定の閾値と比較することにより、ロス障害を検出する。それにより、求めたロス率が閾値を越えている場合に、ロス障害が発生したと判定する。このロス障害の判定結果も同様に、サブネット管理情報テーブル３１に格納される。ロス障害が発生したか否かを判定するための閾値は以降「ロス判定閾値」と呼ぶことにする。ロス障害は、これ以外の方法を用いて検出するようにしても良い。
【００２９】
図５は、サブネット管理情報リスト３１の構成を説明する図である。この管理情報リスト３１は、サブネット毎に、サブネット管理情報、つまりそのサブネットから送信されたパケットを観測して得られた情報、及びその情報を解析して得られた推定結果を保存・管理するためのものである。図５に示すように、表形式で表した場合、ホップ数推定、ＬＡＮ／ＷＡＮ、ロス検知、及び推定結果のカラム（項目）を持つデータ構造となっている。理解を容易にするために、図５には１サブネット分のサブネット管理情報のみを示している。
【００３０】
ＬＡＮ／ＷＡＮカラムには、ホスト毎にエントリが作成される。ホップ数推定カラム、ロス検知カラム、及び推定結果カラムは、ＬＡＮ／ＷＡＮカラムのエントリ毎に、一つ以上のエントリが作成されるようになっている。それにより、推定したホップ数、及びＯＳ種別の組み合わせ毎に、観測結果等を管理・保存可能になっている。
【００３１】
ホップ数推定カラムにはＯＳ種別、ホップ数、パケット数のサブカラムがある。パケット数サブカラムには、送信元ホストから送信されたパケットの総数が格納される。
ＬＡＮ／ＷＡＮカラムにはホスト、及びＬＡＮ／ＷＡＮ区別のサブカラムがある。ホストサブカラムには、送信元ホストのアドレス（ホストアドレス）、ＬＡＮ／ＷＡＮ区別サブカラムには、推定したボトルネック帯域から判定したサブネットの種類が格納される。本実施形態では、推定したボトルネック帯域を所定の閾値と比較することにより、サブネットをＬＡＮ及びＷＡＮの何れかと判定する。それにより、推定したボトルネック帯域が閾値を越えていればサブネットは伝送速度が高速なＬＡＮと判定する。この閾値は以降「ＬＡＮ／ＷＡＮ判定閾値」と呼ぶことにする。推定したボトルネック帯域によるサブネットの種類の分類は、ＬＡＮ／ＷＡＮの二者択一とは異なるものであっても良い。つまり３つ以上の種類のなかから選択するようにしても良い。
【００３２】
このように二者択一によりサブネットの種類を判定するのは、ボトルネック帯域として推定した数値をそのまま扱う必要性は低いからである。パケットが他のサブネットを経由している場合、ボトルネック帯域の推定にはパケットが通過した全てのサブネットが影響を及ぼす。それにより、推定したボトルネック帯域には、比較的に大きな誤差が生じやすい。このことも理由の一つである。
【００３３】
ロス検知カラムには、ホスト、及びロス有無のサブカラムがある。ロス有無サブカラムには、上記のように求めたロス率から判定したロス障害の有無を示す情報を格納するようになっている。図５に表記の「無」はロス障害が発生していないと判定、つまりロス障害を検出していないことを表している。ロス障害が発生していると判定した場合にはその旨を示す内容が格納される。以降、ロス障害が発生していないと判定した場合に書き込む情報は「無」、ロス障害が発生していると判定した場合に書き込む情報は「有」とそれぞれ表記する。
【００３４】
推定結果カラムには、ホップ数、ＬＡＮ／ＷＡＮ区別、ロス有無のサブカラムがある。各サブカラムは、対応するサブネット全体に対する最終的な推定結果が格納される。このため、他のカラムの同名のサブカラムに格納された内容とは必ずしも一致しない。
【００３５】
周知のように、ＴＣＰ／ＩＰでコンピュータの住所を表すアドレス（ＩＰアドレス）は、そのコンピュータが存在するサブネットのアドレス(ネットワークアドレス)と、サブネット内でのそのコンピュータ自身のアドレス(ホストアドレス)から構成されている。このことから、サブネット管理情報リスト３１において、１サブネット分のサブネット管理情報はネットワークアドレスにより特定される。
【００３６】
図６は、ＴＣＰコネクション管理情報リストの構成を説明する図である。このリストは、キャプチャしたパケットが送受信されるＴＣＰコネクション毎に、そのＴＣＰコネクションに係わる情報（ＴＣＰコネクション管理情報）を保存するためのものである。図６には便宜的に、１サブネット分のみ示している。各エントリ（レコード）には、ＴＣＰコネクション管理情報として、送信元／送信先のアドレス／ポート番号の組、ＬＡＮ／ＷＡＮ区分、及びロス有無が格納される。他には、特には図示していないが、最後に受信したパケットのシーケンス番号、受信したパケットの総数（以降「受信パケット総数」と呼ぶ）、及び失われたパケットの総数（累算値。以降「喪失パケット総数」と呼ぶ）を格納するようになっている。それにより、ＴＣＰコネクション毎に、ＬＡＮ／ＷＡＮ区分、及びロス有無の各サブカラムの内容を格納するようにしている。
【００３７】
上述したように、図５に示すサブネット管理情報テーブル３１は、ホップ数解析部２２、ボトルネック帯域解析部２３、及びロス障害検出部２４によって更新される。図６に示すＴＣＰコネクション管理情報リストは、例えばロス障害検出部２４によって更新される。
【００３８】
パケットキャプチャ部２１、ホップ数解析部２２、ボトルネック帯域解析部２３、及びロス障害検出部２４は、パケットをキャプチャし、キャプチャしたパケットから必要な情報を抽出し、抽出した情報を用いた各種推定を行う解析部分を構成する。サブネット情報判定部２５及びトポロジーツリー構成部２６は、この解析部分により得られたサブネット管理情報テーブル３１を参照し、ネットワーク１のトポロジーの構成を推定するトポロジーツリー構成部分を構成する。本実施形態では、ネットワーク１のトポロジー構成は、その構成を模擬したツリー（トポロジーツリー）で表現するようにしている。このトポロジーツリーは、ネットワーク監視装置２０から見た場合のものである。
【００３９】
サブネット情報判定部２５は、例えば一定時間毎に、サブネット管理情報テーブル３１を参照することにより、サブネット管理情報テーブル３１が更新されたか否か判定する。それにより、テーブル３１に何らかの更新が行われた場合には、その旨をトポロジーツリー構成部２６に通知する。
【００４０】
トポロジーツリー構成部２６は、サブネット管理情報テーブル３１に登録されたサブネットをノードとして配置したトポロジーツリーを作成・更新する。作成、或いは更新したトポロジーツリーは、トポロジー情報３２として出力、或いは保存する。サブネット、つまりノードの配置は、ホップ数、及びボトルネック帯域（サブネットの種類）を考慮して決定する。
【００４１】
ボトルネック帯域は、パケットが経由するサブネットがＬＡＮ及びＷＡＮの何れであるかによって変化する。ロス障害が発生したサブネットを経由したパケットには、ロスが生じる。このことから、サブネットのなかでロス障害の影響を受けたサブネットを抽出することにより、パケットが経由するサブネットを絞り込むことができる。その絞り込みの結果から、現在のトポロジーツリーのなかで不適切な部分を修正することができる。それにより、トポロジーツリーの更新には、サブネットの追加の他に、既に存在するサブネットの配置を変更する再配置も含まれる。
【００４２】
図９は、トポロジーツリーの作成・更新方法を説明する図である。図９（ａ）はトポロジーツリーの初期状態、図９（ｂ）はパケットが観測されたサブネットを配置した後のトポロジーツリー例、図９（ｃ）はロス障害の発生によりサブネットの配置を変更した後のトポロジーツリー例をそれぞれ示している。図９中の各ノード３０は、パケットが観測されたサブネットに相当する。実際には各ノード３０はそれぞれルータ１１に相当する。
【００４３】
本実施形態では、図９（ａ）に示すように、初期状態のトポロジーツリーは主ツリー（幹）が１本あり、そこからＷＡＮと推定したサブネット群を配置したブランチ（ＷＡＮブランチ）が１本だけ分岐している構成としている。主ツリーは、全てＬＡＮのサブネットが接続されたパケットの伝送経路を示すものとしている。
【００４４】
各ブランチは、ブランチ管理情報を用いて管理している。このブランチ管理情報は、例えば当該ブランチを一意に特定できる識別情報の他に、当該ブランチが主ツリー、或いは他のブランチから分岐する地点（ノード）のネットワーク監視装置２０を基準にしたホップ数（分岐ホップ数）、及びブランチを構成する各ノードを示すノード情報を含む情報である。識別情報としては、例えば当該ブランチを構成する少なくとも１サブネットのネットワークアドレス、或いは全サブネットのネットワークアドレスの組を採用することができる。分岐ホップ数は、当該ブランチのなかで最もネットワーク監視装置２０に近いノード（サブネット）のネットワーク監視装置２０を基準にしたホップ数から１を引いた値である。各ノードのノード情報は、各ノードのネットワークアドレス、或いは一意に割り当てられるノードＩＤ等を採用することができる。このようなブランチ管理情報を１つ予め用意しておくことにより、初期状態のトポロジーツリーが作成可能となる。
【００４５】
ホストアドレスは、サブネットのネットワークアドレスに、そのサブネットに属するホストによって異なる数字列を付加した形となっている。このことから、ネットワークアドレスは、ホストアドレスから必要な部分のみを抽出することで得られる。
【００４６】
図９（ｂ）には、先頭に「１９２．１６８」の数字列を付した４つのノード３０ａ〜ｄを示している。これらのノード３０ａ〜ｄは、パケットが観測されたサブネットに相当する。各数字列は、それぞれ、各サブネットのネットワークアドレス、或いはホストアドレスを表している。ノード３０ａ及び３０ｂは、ボトルネック帯域からＬＡＮと判定したサブネットに相当し、ノード３０ｃ及び３０ｄは、ＷＡＮと判定したサブネットに相当する。このことから、ノード３０ａ及び３０ｂは、主ツリー上のホップ数によって特定される位置にそれぞれ配置され、ノード３０ｃ及び３０ｄは、ＷＡＮブランチ上のホップ数によって特定される位置にそれぞれ配置されている。末端に位置するリーフノードは全て、パケットが観測されたサブネットに相当する。ノード３０ｃを含むブランチの分岐ホップ数は５である。
【００４７】
このようにして本実施形態では、推定したボトルネック帯域によりサブネット（ノード３０。実際にはサブネットを経由する際に中継するルータ１１）のトポロジーツリー上の配置可能な位置を制限している。それにより、推定したボトルネック帯域に矛盾が生じないように、サブネットを配置する。そのようにサブネットを配置可能な位置を制限するため、その制限を設けない場合と比較して、各サブネットはより適切に配置することができる。以降、サブネット（ノード３０）の位置関係は、ネットワーク監視装置２０を基点として表現する。それにより、ネットワーク監視装置２０に近い側は前側と表現し、ホップ数は、ネットワーク監視装置２０から見た場合の値で表現する。
【００４８】
例えばパケットの送信に要する送信時間自体は、パケットが経由した個々のサブネットの伝送速度を推定できる情報ではない。このため、上記のような制限を設けることはできない。このため、各サブネットを配置する精度は低いものとなる。
【００４９】
図９（ｃ）には、新たにノード３０ｅが追加されている。ノード３０ｃ及び３０ｅは、ノード３０ｄを有するＷＡＮブランチとは別の同じノード３０ｖから分岐させたＷＡＮブランチとしている。これは、例えばノード３０ｃ及び３０ｅにそれぞれ相当するサブネットから送信されたパケットの観測により、それらのサブネットでのみロス障害の発生が確認されたためである。そのようにして本実施形態では、既存のブランチを構成する一部のノードに相当するサブネットのロス障害を検出した場合、そのノード全てを有するブランチを生成することにより、ロス障害の検出結果に矛盾しないようにノードの再配置を実現させている。
【００５０】
ノード３０ｅの前の配置は、例えばノード３０ｄの直前の位置である。その前の配置では、相当するサブネットのホップ数は７、ノード３０ｄに相当するサブネットのホップ数は８である。そのような位置関係（接続関係）が実際に存在していれば、ノード３０ｃに相当するサブネットにロス障害が発生した場合には、ノード３０ｄに相当するサブネットが送信したパケットにもロス障害の影響が生じることになる。このことから、ノード３０ｄに相当するサブネットが送信したパケットからロス障害が観測されなければ、そのサブネットから送信されたパケットはノード３０ｅに相当するサブネットを経由することなく伝送されると解釈することができる。これは、現在のノード３０ｄ、及び３０ｅを伝送経路とする配置は不適切であることを意味する。このため、新たにＷＡＮブランチを生成（追加）し、既に存在する２つのノード３０ｃ及び３０ｅを追加したＷＡＮブランチに移動させる配置の変更（再配置）を行っている。
【００５１】
このようにして本実施形態では、発生したロス障害から、そのロス障害が影響する範囲のサブネットの接続関係を推定することにより、推定したネットワーク１のトポロジー（トポロジーツリー）のなかで不適切に配置されたノードを抽出し、その配置を修正するようにしている。ロス障害は、どのサブネットでも発生しうる。時間の経過に伴い、ロス障害が発生していないサブネットの数は少なくなる。このため、最終的には、高精度にトポロジーを推定、つまり高精度なトポロジーツリーを作成することができることとなる。以降ノードは、特に断らない限り、サブネットと同じ意味で用いる。
【００５２】
作成したトポロジーツリーは、トポロジー情報３２として出力、或いは保存される。図７は、そのトポロジー情報３２の構成を説明する図である。
このトポロジー情報３２は、図７に示すように、ノード毎のノード管理情報をまとめたものである。このノード管理情報は、対応するノードの他のノードとのトポロジーツリー上の接続関係等を表すものである。本実施形態では、このノード管理情報は、自ノードに割り当てられたノードＩＤ、親ノード（ネットワーク監視装置２０から見て前側のノード）の親ノードＩＤ、子ノード（ネットワーク監視装置２０から見て後側のノード）の子ノードＩＤ、ホップ数、ＬＡＮ／ＷＡＮ区別、及び含まれるサブネットのアドレスを備えた構成となっている。ホップ数は、ネットワーク監視装置２０を基準にしたものであり、ホップ数の１はネットワーク監視装置２０（ルートノードに相当）から見て１番目のノードであることを表している。含まれるサブネットのアドレスは、ネットワークアドレスである。
【００５３】
子ノードＩＤの数は、トポロジーツリー上の配置によって変化する。例えばリーフノードでは端に位置しているため、存在しないか、或いは１つの定められた値となる。ブランチが接続されたノードでは、接続されたブランチの数に応じて、子ノードＩＤの数は増える。例えば図９（ｃ）のノード３０ｖでは、子ノードＩＤの数は３となる。それら以外のノードでは、子ノードＩＤの数は１である。
【００５４】
パケットが観測されたノードは、推定されたホップ数に従って配置する。パケットが観測されたノードを配置するだけでは、推定されたホップ数に従って配置できない場合がある。具体的には、例えばパケットが観測されたサブネットが一つだけであり、そのサブネットで推定されたホップ数が１０であった場合、そのサブネットの前に９つのパケットが観測されていないサブネットを配置しなければならない。このことから、含まれるサブネットとして格納するネットワークアドレスは、パケットが観測されたサブネットか否かを示すデータとなっている。図７中の“unknown”は、パケットが観測されていないサブネットであることを示している。トポロジーツリー上に不適切に配置したノードの抽出は、パケットが観測されたサブネットのノードのみが対象となる。
【００５５】
トポロジー情報３２はこのような構成である。このため、トポロジーツリーの作成（更新を含む）は、直前の内容から、一つ以上のノード管理情報の操作、つまり追加、削除、或いは更新を行うことに相当する。
【００５６】
図８は、同時ロス障害発生拠点リストの構成を説明する図である。このリストは、ロス障害の発生に対応するために作成するものであり、サブネット毎に、そのアドレス、ホップ数、及びＬＡＮ／ＷＡＮ区別を１エントリ（レコード）に格納した構成である。
【００５７】
トポロジーツリー構成部２６は、サブネット管理情報テーブル３１を参照し、推定結果カラムのロス有無サブカラムが「有」となっているサブネット管理情報をすべて抽出し、同時ロス障害発生拠点リストを作成する。それにより、トポロジーツリーの更新は、このリストも用いて行う。
【００５８】
図１３Ａ〜Ｃは、パケット解析処理のフローチャートである。この解析処理は、ネットワーク１を流れるパケットを観測し、その観測により得られる情報を解析するためにネットワーク監視装置２０が実行する処理を抜粋して示したものである。この解析処理内に示す処理ステップは、そのための機能を搭載したプログラム（パケット監視プログラム）をネットワーク監視装置２０が実行することにより実現される。解析部分を構成するパケットキャプチャ部２１、ホップ数解析部２２、ボトルネック帯域解析部２３、及びロス障害検出部２４は、このプログラムをネットワーク監視装置２０が実行する結果、実現される。次に図１３Ａ〜Ｃを参照して、この解析処理について詳細に説明する。
【００５９】
この解析処理において、パケットキャプチャ部２１はステップＳ１を実行することにより実現される。同様に、ホップ数解析部２２はステップＳ１１〜Ｓ１７、ボトルネック帯域解析部２３はステップＳ２１〜Ｓ２９、ロス障害検出部２４はステップＳ３１〜Ｓ３８をそれぞれ実行することにより実現される。実際には、例えばステップＳ１１〜Ｓ１７、ステップＳ２１〜Ｓ２９、及びステップＳ３１〜Ｓ３８は、それぞれ異なるサブプログラムにより実行され、それらのサブプログラムは、例えばステップＳ１が実行される処理により呼び出されて実行される。
【００６０】
先ず、ステップＳ１では、ネットワーク１を流れるパケットをキャプチャする。それにより、パケットをキャプチャできた場合、ステップＳ１１、Ｓ２１及びＳ３１以降の処理がそれぞれ実行される。これらステップＳ１１、Ｓ２１及びＳ３１への各移行は、パケットキャプチャ部２１がキャプチャしたパケットをホップ数解析部２２、ボトルネック帯域解析部２３及びロス障害検出部２４にそれぞれ渡すことに相当する。特には図示していないが、パケットをキャプチャできなかった場合には、ここでパケット解析処理を終了するようになっている。キャプチャしたパケットは以降「受信パケット」と呼ぶことにする。
【００６１】
ステップＳ１１以降では、以下の処理が実行される。
先ず、ステップＳ１１では、サブネットマスク情報３５を参照して、受信パケットからサブネット情報、つまり受信パケットを送信した送信元サブネットのネットワークアドレスを抽出する。このサブネットマスク情報３５は、受信パケットに格納された送信元アドレスのなかでネットワークアドレスの範囲を表すものである。このことからネットワークアドレスの抽出は、受信パケットの送信元アドレスからサブネットマスク情報３５が示す範囲のアドレスを取り出すことで行われる。そのようにしてネットワークアドレスを抽出した後はステップＳ１２に移行する。
【００６２】
ステップＳ１２では、抽出したネットワークアドレスを持つサブネット管理情報がサブネット管理情報リスト３１に存在しているか否か判定する。ホストサブカラムのデータとして格納されたアドレスのなかにそのネットワークアドレスを含むものが存在する場合、判定はＹＥＳとなってステップＳ１４に移行する。そのようなアドレスが存在しない場合、判定はＮＯとなってステップＳ１３に移行し、受信パケットを送信した送信元サブネットのサブネット管理情報を作成し、サブネット管理情報リスト３１に格納する。その後はステップＳ１４に移行する。ここで作成されるサブネット管理情報は、送信元アドレスであり、その送信元アドレスの格納は、サブネット管理情報リスト３１のＬＡＮ／ＷＡＮカラム、及びロス検知カラムにそれぞれ１エントリ（レコード）を追加して行われる。
【００６３】
ステップＳ１４では、上述したようにして、受信パケットのＴＴＬフィールドの値から、ホップ数、及びＯＳ種別の推定を実施する。次にステップＳ１５に移行し、推定したホップ数とＯＳ種別の組み合わせが既存のものか否か判定する。その組み合わせが対応するサブネット管理情報のホップ数推定カラムのエントリに存在する場合、判定はＹＥＳとなってステップＳ１７に移行する。その組み合わせが存在しない場合には、判定はＮＯとなってステップＳ１６に移行し、ホップ数推定カラムに１エントリを追加して、推定したホップ数、及びＯＳ種別を格納する。その後ステップＳ１７に移行する。
【００６４】
ホップ数、及びＯＳ種別の推定では通常、複数の受信パケットを必要とする。このため、ホップ数、及びＯＳ種別は、推定できるとは限らない。このことから、推定するまでの間、ホップ数、及びＯＳ種別として、推定できていないことを示すデータを格納するようにしている。ここではそのデータも“unknown”と呼ぶことにする。
【００６５】
ステップＳ１７では、ホップ数推定カラムのパケット数サブカラムの値をインクリメントする。それにより、このパケット数サブカラムには、サブネットから送信されたパケットのなかで実際に受信したパケットの総数が格納される。そのインクリメントを行った後、ステップＳ１１以降の一連の処理を終了する。
【００６６】
次に、図１３Ｂを参照して、ステップＳ２１以降の処理について詳細に説明する。
このステップＳ２１では、受信パケットから送信元アドレス、ポート番号、送信先アドレス、ポート番号を抽出する。続くステップＳ２２では、抽出した送信元／送信先のアドレス・ポート番号の組を用いてＴＣＰコネクション管理リストを検索することにより、その組を持つＴＣＰコネクション情報が存在するか否か判定する。その組を持つＴＣＰコネクション情報が存在する場合、判定はＹＥＳとなってステップＳ２４に移行する。そのようなＴＣＰコネクション情報が存在しない場合、判定はＮＯとなってステップＳ２３に移行し、その組を持つＴＣＰコネクション情報を作成し、ＴＣＰコネクション情報リストに追加する。その後はステップＳ２４に移行する。この時点で作成するＴＣＰコネクション情報では、ＬＡＮ／ＷＡＮ区分としてＬＡＮ、ロス有無として「無」を初期値として設定する。
【００６７】
ステップＳ２４では、上述したようにして、ボトルネック帯域の推定を実施し、その実施結果からＬＡＮ／ＷＡＮ区別を判定する。次のステップＳ２５では、判定したＬＡＮ／ＷＡＮ区別の内容を、ＴＣＰコネクション管理情報リストの当該エントリ（ＴＣＰコネクション管理情報）におけるＬＡＮ／ＷＡＮ区別カラムの内容と比較することにより、判定結果が変動しているか否か判定する。それらＬＡＮ／ＷＡＮ区別の内容が異なる場合、判定はＹＥＳとなってステップＳ２６に移行する。それらの内容が一致する場合には、判定はＮＯとなり、ここでステップＳ２１以降の一連の処理を終了する。
【００６８】
ステップＳ２６では、ＴＣＰコネクション管理情報リストの当該エントリのＬＡＮ／ＷＡＮ区別カラムに新しい値、つまり今回の判定結果を上書きする。この判定結果は、サブネット管理情報リスト３１における、ＬＡＮ／ＷＡＮカラムのホストサブカラムに送信元アドレスを格納したエントリのＬＡＮ／ＷＡＮ区別サブカラムの内容としても記入する。続くステップＳ２７では、サブネット管理情報リスト３１からＬＡＮ／ＷＡＮカラムのエントリを読み出し、そのエントリのホストサブカラムのデータとして、受信パケットの送信元アドレスが存在するか否か判定する。その送信元アドレスが何れかのエントリのホストサブカラムのデータとして存在していた場合、判定はＹＥＳとなってステップＳ２９に移行する。その送信元アドレスが存在していなかった場合、判定はＮＯとなってステップＳ２８に移行し、ＬＡＮ／ＷＡＮカラム、及びロス検知カラムにそれぞれ１エントリを追加し、各カラムのホストサブカラムのデータとして送信元アドレスを格納する。ステップＳ２９にはその後に移行する。
【００６９】
ステップＳ２９では、受信パケットの送信元アドレスを持つエントリのＬＡＮ／ＷＡＮ区別サブカラムの内容の書き換えを行う。その書き換えを行った後、ステップＳ２１以降の一連の処理は終了する。
【００７０】
上記書き換えは、受信パケットの送信元アドレスを用いたＴＣＰコネクション管理情報リストの検索によってエントリを抽出し、抽出したエントリのＬＡＮ／ＷＡＮ区別カラムの内容から、書き込むべきＬＡＮ／ＷＡＮ区別サブカラムの内容を特定することで行う。その特定は、例えばＴＣＰコネクション管理情報リストから抽出したエントリのＬＡＮ／ＷＡＮ区別カラムの内容として多いほうを選択する、或いはその内容としてＬＡＮが一つでも存在していればＬＡＮを選択することで行う。後者は、通常、伝送速度は遅くなることはあっても早くなることはないという考えによるものである。その特定は、これら以外の方法を用いて行うようにしても良い。
【００７１】
最後に、図１３Ｃを参照して、ステップＳ３１以降の処理について詳細に説明する。
このステップＳ３１では、受信パケットから送信元アドレス、ポート番号、送信先アドレス、ポート番号を抽出する。続くステップＳ３２では、抽出した送信元／送信先のアドレス・ポート番号の組を用いてＴＣＰコネクション管理情報リストを検索し、その組を格納したエントリを抽出する。その抽出後はステップＳ３３に移行する。
【００７２】
ステップＳ３３では、抽出したエントリの受信パケット総数のインクリメント、或いは喪失パケット総数の更新を行うと共に、発生したロス障害の検出を行う。その検出は、上述したように、抽出したエントリに格納されている喪失パケット総数を受信パケット総数で割ることによってロス率を算出し、算出したロス率をロス判定閾値と比較して行う。その後はステップＳ３４に移行する。
【００７３】
失われたパケットが発生した場合、抽出したエントリのシーケンス番号と受信パケットのシーケンス番号には２以上の差が生じる。このことから、喪失パケット数の更新は、その差から１を引いた値（＝差−１）を求め、現在の喪失パケット総数に加算することで行われる。過去に発生したロス障害が長い期間、影響しないようにするために、受信パケット総数、及ぶ喪失パケット総数は、例えば一定時間毎にクリアすることが望ましい。
【００７４】
ステップＳ３４では、検出結果をＴＣＰコネクション管理リストの当該エントリにおけるロス有無カラムの内容と比較することにより、ロス障害の検出結果は変動しているか否か判定する。それらの内容が一致していた場合、判定はＮＯとなり、ここでステップＳ３１以降の一連の処理を終了する。それらの内容が一致していなかった場合には、判定はＹＥＳとなってステップＳ３５に移行する。
【００７５】
ステップＳ３５では、当該エントリのロス有無カラムの内容として検出結果を上書きする。次のステップＳ３６では、サブネット管理情報リスト３１を参照し、受信パケットの送信元アドレスをＬＡＮ／ＷＡＮカラムのホストサブカラムのデータとして格納したものが有るか否か判定する。その送信元アドレスをホストサブカラムのデータとするエントリが存在した場合、判定はＹＥＳとなってステップＳ３８に移行する。そのようなエントリが存在しない場合、判定はＮＯとなってステップＳ３７に移行し、ＬＡＮ／ＷＡＮカラムに１エントリを作成して、少なくともその送信元アドレスをホストサブカラムのデータとして格納する。その後、ステップＳ３８に移行する。
【００７６】
ステップＳ３８では、上記送信元アドレスを格納したエントリのロス有無サブカラムのデータとして、ロス障害の検出結果を書き込む。その書き込みの後、ステップＳ３１以降の一連の処理を終了する。
【００７７】
図１４Ａ及びＢは、トポロジーツリー構成処理のフローチャートである。この構成処理は、サブネット管理情報リスト３１を参照して、ネットワーク１のトポロジーを模擬するトポロジーツリーの作成、或いは更新するためにネットワーク監視装置２０が実行する処理を抜粋して示したものである。この構成処理内で実行される処理ステップは、そのための機能を搭載したプログラム（トポロジーツリー構成プログラム）をネットワーク監視装置２０が実行することにより実現される。トポロジーツリー構成部分のトポロジーツリー構成部２６は、このプログラムをネットワーク監視装置２０が実行する結果、実現される。次に図１４Ａ及びＢを参照して、この構成処理について詳細に説明する。
【００７８】
この構成処理では、実際には、例えば図１４ＡのステップＳ４１〜Ｓ５１、及び図１４ＢのステップＳ６１〜Ｓ７１は、それぞれ異なるサブプログラムの実行によって実現される。それにより、この構成処理として、２つのサブルーチン処理をまとめて示している。
【００７９】
図１３ＡのステップＳ１が実行される処理は例えばメインルーチン処理であり、そのメインルーチン処理では、例えば一定時間毎に、サブネット管理情報リスト３１の更新を確認するための処理を実行するようになっている。この構成処理として実行される２つのサブルーチン処理は、その確認結果に応じてメインルーチン処理に呼び出されて実行される。その呼び出しは、サブネット情報判定部２５がサブネット管理情報テーブル３１の更新をトポロジーツリー構成部２６に通知することに相当する。
【００８０】
始めに、ステップＳ４１〜Ｓ５１の一連の処理について説明する。この一連の処理は、対象とするサブネットを変更しながら、ロス障害を考慮せずにそのサブネットをトポロジーツリー上に配置するための処理である。これに対し、ステップＳ６１からＳ７１の一連の処理は、トポロジーツリー上のサブネットの配置を、検出されたロス障害に応じて変更するための処理である。ステップＳ４１〜Ｓ５１の一連の処理は、トポロジー情報３２を作成するための処理に相当し、ステップＳ６１からＳ７１の一連の処理は、作成されたトポロジー情報３２を更新するための処理に相当する。
【００８１】
先ず、ステップＳ４１では、対象とするサブネット、つまりサブネット管理情報を選択し、ホップ数推定カラムのエントリのなかにホップ数サブカラムとして格納されたホップ数が異なるエントリが存在するか否か判定する。各エントリに格納されたホップ数が全て同じでなかった場合、判定はＹＥＳとなってステップＳ４３に移行する。全てのエントリでホップ数が同じであった場合には、判定はＮＯとなり、ステップＳ４２でそのホップ数を推定結果コラムのホップ数サブカラムとして格納すべきものと決定する。その後はステップＳ４５に移行する。
【００８２】
ステップＳ４３では、ホップ数推定カラムのエントリのなかにＯＳ種別サブカラムが“unknown”となっているエントリがあるか否か判定する。そのようなエントリが存在する場合、判定はＹＥＳとなってステップＳ４４に移行し、そのエントリを無視して、つまりＯＳ種別サブカラムが“unknown”となっていないエントリのみを対象にしてホップ数を決定する。その後はステップＳ４５に移行する。その決定には、例えばホップ数のなかで最も多いホップ数を選択する、或いはパケット数サブカラムの値が最大のエントリのホップ数を選択する、といった方法を採用すれば良い。一方、ＯＳ種別サブカラムが“unknown”となっているエントリが存在しない場合には、判定はＮＯとなり、ホップ数の推定に対応不可能な誤差が生じているとして、その旨を通知するためのエラー出力を行った後、ステップＳ４１以降の一連の処理を終了する。
【００８３】
ステップＳ４５では、ＬＡＮ／ＷＡＮカラムのエントリのなかにＬＡＮ／ＷＡＮ区別サブカラムの内容がＬＡＮとなっているものが一つでもあるか否か判定する。ＬＡＮ／ＷＡＮ区別サブカラムがＬＡＮとなっているエントリが存在する場合、判定はＹＥＳとなり、ステップＳ４６で推定結果カラムのＬＡＮ／ＷＡＮ区別サブカラムの内容としてＬＡＮを書き込む。その後ステップＳ５０に移行する。そのようなエントリが存在しない場合には、つまり全てのエントリのＬＡＮ／ＷＡＮ区別サブカラムの内容がＷＡＮとなっている場合には、判定はＮＯとなってステップＳ４７に移行する。
【００８４】
このようにして本実施形態では、ＬＡＮ／ＷＡＮ区別サブカラムの内容がＬＡＮとなっているエントリが一つでも存在していれば、サブネットはＬＡＮであると判定する。これは、サブネットのホストのなかに何らかの理由（例えば低速のハブに接続させている、トラフィックが一時的に異常に増大した、といったようなもの）によって伝送速度が遅くなっているものが存在する可能性が考えられるためである。ホスト毎にＬＡＮ／ＷＡＮの分類をするのはこのためである。そのようにホスト毎に分類を行うことにより、サブネットの分類（ボトルネック帯域の推定）をより高精度に行うことができる。
【００８５】
ステップＳ４７では、推定結果カラムのＬＡＮ／ＷＡＮ区別サブカラムとしてＷＡＮを書き込む。続くステップＳ４８では、新たにホップ数を決定したノードの属するＷＡＮブランチの先頭に位置するノードのホップ数（以降「最小ホップ数」と呼ぶ）がより小さい値に更新されているか否か判定する。この最小ホップ数から１を引いた値が当該ＷＡＮブランチのブランチ管理情報として管理する分岐ホップ数より小さい値に更新されている場合、判定はＹＥＳとなってステップＳ４９に移行し、この分岐ホップ数を現在の最小ホップ数から１を引いた値に更新する。この更新により、ＷＡＮブランチを分岐させるノード（以降、ブランチを分岐させるノードを「分岐ノード」と総称する）をネットワーク監視装置２０側に移動させる。その後、ステップＳ５０に移行する。その最小ホップ数から１を引いた値が分岐ホップ数以上の値に更新されている場合には、判定はＮＯとなってステップＳ５０に移行する。それにより、分岐ノードの移動は回避させる。
【００８６】
ステップＳ５０では、ブランチ管理情報を参照し、決定したホップ数、及びＬＡＮ／ＷＡＮの分類に応じて、トポロジーツリー上にサブネット（ノード）を配置する。このとき、主ツリー、或いはブランチにサブネットを配置すべき場所が存在しない場合、ブランチを生成し、生成したブランチに配置する。このことから、サブネットの配置は、対応するノード管理情報の追加、及びその配置が影響する他のサブネットのノード管理情報を更新することで行われる。次のステップＳ５１では、未処理のサブネットのためのループを実現させる処理を実行する。その処理とは、例えば未処理のサブネットが存在するか否か判定する判定処理である。そのような判定処理をステップＳ５１で実行する場合、未処理のサブネットが存在すると判定はＹＥＳとなり、上記ステップＳ４１に戻る。未処理のサブネットが存在しないと判定はＮＯとなり、ここでステップＳ４１以降の一連の処理を終了する。
【００８７】
このようにして本実施形態では、既存のトポロジー情報３２を更新するのではなく、新たにトポロジー情報３２を作成するようにしている。これは、或るサブネットにおけるホップ数やＬＡＮ／ＷＡＮ区別の推定結果の変化が他のサブネットの配置に及ぼす影響が特定し難いからである。その影響が及ぼす範囲を正確に特定し、その範囲内のサブネットのみを対象に配置を変更する形でトポロジー情報３２を更新（作成）しても良い。配置を決定するうえでブランチ管理情報を参照するのは、既に生成したブランチにノードを配置した結果は更新すべき理由が発生しない限り、更新しないようにしているためである。そのようにして、更新すべき理由が発生しない限り、過去に作成したトポロジーツリーを再現できるようにしている。
【００８８】
ここで、新たにトポロジー情報３２を作成することによって生じるトポロジーツリーへの操作、つまり直前のトポロジーツリーからの変更について、例を挙げて具体的に説明する。その変更は、新たにパケットが観測されたサブネットが発生した場合、無条件で行われる。そのようなサブネットが発生していない場合には、変更内容はステップＳ５０に移行する前に実行するステップの処理によって異なる。
【００８９】
新たにパケットが観測されたサブネットが発生した場合、決定されたホップ数、及びＬＡＮ／ＷＡＮの分類結果に応じて、そのサブネットに相当するノードを配置すべき位置を特定し、配置する。このとき、ＬＡＮ／ＷＡＮの分類結果、及びホップ数が同じサブネットが既にトポロジーツリー上に存在していれば、新たにブランチを作成し、作成したブランチに配置することになる。トポロジーツリー上に配置可能な場所が存在していれば、その場所に配置することになる。その場所が既存のブランチに存在していれば、そのブランチのブランチ管理情報は更新されることとなる。そのようにして新たに配置することから、ノード管理情報は追加され、その配置が影響する他のノードのノード管理情報は更新されることとなる。
【００９０】
ステップＳ４６、或いはＳ４８からステップＳ５０に移行した場合、対象とするサブネットで決定されたホップ数、及びＬＡＮ／ＷＡＮの分類結果に応じて、そのサブネットに相当するノードを配置すべき位置を特定し、配置する。このとき、ＬＡＮ／ＷＡＮの分類結果、及びホップ数が同じサブネットが既にトポロジーツリー上に存在していれば、ブランチを作成し、作成したブランチ上に配置すべきサブネットを配置することになる。このため、ブランチを追加する操作が行われる可能性が存在することとなる。
【００９１】
上述したように、伝送速度が何らかの理由によって低下している可能性が考えられることから、ＬＡＮ／ＷＡＮの分類は、ホスト毎に行っている。このことから、ＬＡＮ／ＷＡＮ区別サブカラムの内容がＷＡＮ→ＬＡＮに更新される可能性が存在する。ＷＡＮと分類したサブネット（ノード）はブランチ上に配置しなければならない。しかし、ＬＡＮと分類したサブネットは、他のＬＡＮと分類したサブネットを考慮して、主ツリー上、或いはブランチ上に配置する。このため、ステップＳ４６からステップＳ５０に移行した場合には、ＬＡＮ／ＷＡＮ区別サブカラムの内容がＷＡＮ→ＬＡＮに更新されたケースの操作を行う可能性がある。その操作とは、例えば新たにＬＡＮと分類したサブネットをＷＡＮブランチ上から主ツリー、或いは他のブランチ上に移動させるようなものである。このため、そのような操作を行う場合、配置を変更するノード、及びその変更が影響する他のノードのノード管理情報に加えて、ブランチ管理情報も更新されることとなる。
【００９２】
図９（ｂ）に示す状態では、ＷＡＮブランチはノード３０ａの次のノード３０ｖ、つまりネットワーク監視装置２０から５ホップ目のノード（分岐ホップ数が５であるノード）３０ｖを分岐ノードとして主ツリーから分岐している。ステップＳ４９での分岐させるサブネットの移動、つまり分岐ホップ数の更新は、例えばノード３０ａを新たな分岐ノードとしてＷＡＮブランチを分岐させるような操作に相当する。この場合、結果として、トポロジー情報３２のなかでＷＡＮブランチを構成するノードの全て、及びその分岐ノード３０ａのノード管理情報は直前の内容とは異なるものとなる。これは、全てのノードで少なくともホップ数を更新しなければならないからである。ブランチ管理情報も更新される。
【００９３】
次に図１４Ｂを参照して、ステップＳ６１〜Ｓ７１の一連の処理について詳細に説明する。
ステップＳ６１〜Ｓ７１の一連の処理は、１サブネットを対象に実行される部分を示したものである。それにより、ステップＳ６１〜Ｓ７１の一連の処理もステップＳ４１〜Ｓ５１の一連の処理と同様に、対象とするサブネットを順次、変更していくことにより、サブネット毎に実行される。
【００９４】
上述したように、或るサブネットでロス障害が発生している場合、そのサブネット以外に、そのサブネットを経由してパケットが伝送される他のサブネットもロス障害が発生していると見なされる。このようなことから、発生したロス障害は、パケットの伝送経路となっているサブネット群（リーフノードに相当するサブネットにロス障害が発生したような場合には１サブネットである）を特定するうえで極めて有用な情報である。ステップＳ６１〜Ｓ７１の一連の処理は、このことに着目し、ロス障害のトモグラフィ分析を用いて、ネットワーク１のロス障害が影響する部分のトポロジーを推定（特定）し、その推定結果を既存のトポロジーツリーに反映させるための処理である。
【００９５】
先ず、ステップＳ６１では、ロス検知カラムにおける、対象とするサブネットの各エントリのロス有無サブカラムのデータを参照し、１つでも「無」となっているものがあるか否か判定する。対象とするサブネットに属するホスト毎にロス障害を検出した結果、少なくとも１ホストからロス障害が検出されなかった場合、判定はＹＥＳとなり、ここでステップＳ６１以降の一連の処理を終了する。全てのホストからロス障害が検出された場合には、判定はＮＯとなってステップＳ６２に移行する。
【００９６】
ステップＳ６１の判定がＹＥＳとなった場合、実際には上記ステップＳ５１と同様の処理が実行される。それにより、他の対象としていないサブネットを対象にした処理が行われることになる。これは、「終了」と表記した端子を移行先とする他のステップの処理でも同様である。しかし、ここでは便宜的に、ステップＳ５１と同様の処理については言及しないこととする。
【００９７】
ステップＳ６２では、推定結果カラムのロス有無サブカラムのデータとして「有」を記入する。次のステップＳ６３では、ロス有無サブカラムのデータとして「有」が記入されているエントリ、つまりロス障害が発生しているサブネットを全て抽出し、抽出したサブネットを同時ロス障害発生拠点リストに記入（登録）する。そのようにして、同時ロス障害発生拠点リストを新たに作成した後に移行するステップＳ６４では、記入したサブネットが全てＬＡＮ、或いはＷＡＮで統一されているか否か判定する。記入したサブネットを全てＬＡＮ、或いはＷＡＮと推定していなかった場合、判定はＮＯとなってステップＳ６９に移行する。記入したサブネットが全てＬＡＮ、或いはＷＡＮと推定していた場合には、判定はＹＥＳとなってステップＳ６５に移行する。
【００９８】
このようにして本実施形態では、ロス検知カラムのエントリのなかでロス有無サブカラムの内容が「無」となっているものが１つでも存在していると、サブネット全体ではロス障害が発生していないと見なすようにしている。これは、送信元ホストに発生した不具合によってロス障害を検出してしまう可能性があるためである。言い換えれば、実際にロス障害が発生しているサブネットを高精度に検出するためである。
【００９９】
ステップＳ６５では、同時ロス障害発生拠点リストに記入したサブネット群（一つ以上のサブネット）における最小のホップ数を抽出し、必要に応じて、そのホップ数から１を減算した値をホップ数とするノードを分岐ノードとしたブランチを生成し、このブランチにそのサブネット群を移動（再配置）させる。その移動は以下のようにして行われる。ここでは、図９を参照して具体的に説明する。
【０１００】
図９（ｂ）において、例えばＷＡＮブランチのノード３０ｄにのみロス障害が検出された場合、ノード３０ｄはその直前のノードを分岐ノードとするブランチに移動させる。ノード３０ｄの後に位置するリーフノードで推定したホップ数との矛盾を生じさせないために、移動させるノード３０ｄの元の位置には別のノードを配置する。ＷＡＮブランチの先頭から２つのノードでロス障害がそれぞれ検出された場合、それら２つのノードは新たに作成するＷＡＮブランチに移動し、その移動に合わせて元のＷＡＮブランチには２つのノードを新たに配置する。それにより、図９（ｃ）に示すような状態に更新する。同様に、主ツリーのノード３０ｂにのみロス障害が検出された場合には、ノード３０ｂはその直前のノードを分岐ノードとするブランチ（ＬＡＮブランチ）に移動させ、ノード３０ｂの元の位置には別のノードを配置する。一方、ＷＡＮブランチを構成する全てのノード、或いはリーフノードから連なる１つ以上のノード（例えばノード３０ｄ及びその後のリーフノードといった繋がり）でロス障害が検出された場合には、ブランチを生成する必要がないことから、移動は行わない。
【０１０１】
このようにして本実施形態では、必要に応じてブランチを生成し、ロス障害が検出された１つ以上のノードをそのブランチに移動させることにより、ロス障害から推定したサブネット間の接続関係をトポロジーツリーに反映させる。それにより、より精度の高いトポロジーツリーを得ることができる。
【０１０２】
ブランチを生成した場合には、当該ブランチのブランチ管理情報の作成、移動させるノード、及びその移動が影響するノードのノード管理情報の更新、当該ブランチに移動させるノードが配置されていたブランチのブランチ管理情報の更新等が合わせて行われる。
【０１０３】
ステップＳ６５に続くステップＳ６６では、ロス障害が検出されたサブネット群はＷＡＮか否か判定する。同時ロス障害発生拠点リストに記入したサブネットが何れもＷＡＮと判定したいた場合、判定はＹＥＳとなってステップＳ６７に移行する。記入したサブネットの少なくとも一つをＬＡＮと判定していた場合には、判定はＮＯとなり、ここでステップＳ６１以降の一連の処理を終了する。
【０１０４】
ステップＳ６７では、ノードを移動させたＷＡＮブランチの最小ホップ数がその移動によって更新されているか否か判定する。このＷＡＮブランチの先頭に位置するノードを新たに生成したＷＡＮブランチに移動させるような場合、最小ホップ数から１を引いた値は分岐ホップ数より大きい値となる。このため、判定はＹＥＳとなってステップＳ６８に移行し、分岐ホップ数を現在の最小ホップ数から１を引いた値に更新する。その後、ステップＳ６１以降の一連の処理を終了する。ＷＡＮブランチの先頭に位置するノードを新たに生成したＷＡＮブランチに移動させない場合には、最小ホップ数は分岐ホップ数と同じ値となる。このため、判定はＮＯとなり、ここでステップＳ６１以降の一連の処理を終了する。
【０１０５】
ステップＳ６９では、ロス障害が検出されているサブネット群における最小のホップ数はそのサブネット群を構成する少なくとも１サブネットのノードが配置された既存のブランチの最小ホップ数と同じ、若しくは小さいか否か判定する。その最小のホップ数から１を引いた値が当該ブランチのブランチ管理情報として保持する分岐ホップ数以下であった場合、判定はＹＥＳとなってステップＳ７０に移行する。その最小のホップ数から１を引いた値が分岐ホップ数より大きい場合には、判定はＮＯとなってステップＳ７１に移行する。それにより、ステップＳ７０、及びＳ７１の処理を実行した後、ステップＳ６１以降の一連の処理を終了する。
【０１０６】
ステップＳ７０及びＳ７１では、トポロジーツリー上のロス障害が検出されたサブネットのノードを再配置する操作のための処理が行われる。この再配置の操作例について、図１０〜図１２を参照して具体的に説明する。
【０１０７】
先ず、図１０及び図１１を参照して、ステップＳ７０の処理により行われる操作について説明する。
図１０は、ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数と同じ場合の操作例を説明する図である。図１０において、ノード３０ｆ〜ｈはロス障害が検出されたサブネットに相当する。操作前のノード３０ｆ〜ｈの配置は、例えばノード３０ｆ及び３０ｇはそれぞれノード３０ｉ及び３０ｊの位置であり、ノード３０ｈはノード３０ｉの位置にあったノード３０ｆを分岐ノードとするブランチ上である。これらのノード３０ｆ〜ｈは、ノード３０ｖを分岐ノードとして生成したブランチに再配置する操作により、図１０に示す位置に変更されている。ノード３０ｆ及び３０ｇの再配置により、元の位置には新たにノード３０ｉ及び３０ｊが配置されている。これらノード３０ｉ及び３０ｊは、ノード３０ｆ及び３０ｇと同じく、ＬＡＮと分類されるサブネット用である。
【０１０８】
この例では、トポロジー情報３２中のノード管理情報はノード３０ｇ及び３０ｄのものが更新され、ノード３０ｉ及び３０ｊのものが作成（追加）される。ブランチ管理情報は、新たにノード３０ｉが配置されたブランチでは更新され、新たに生成したブランチでは作成される。
【０１０９】
図１１は、ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数より小さい場合の操作例を説明する図である。図１１では、ロス障害が検出された２つのサブネット群に対してそれぞれ操作を行った後の状態例を表している。この２つのサブネット群に相当するノード群は、ノード３０ｆ〜ｈ（以降「第１のノード群」）と、ノード３０ｄが配置されたブランチを構成するノード群（以降「第２のノード群」）とである。これら２つのノード群は、ロス障害が検出される前は例えば図１０に示すように配置されていたものである。
【０１１０】
第１のノード群は、最小ホップ数（＝分岐ホップ数＋１）が６から３に更新されている。このため、分岐ノードはノード３０ｖからノード３０ｗに移動させている。第２のノード群は、最小ホップ数が６から４に更新されている。このため、分岐ノードはノード３０ｖからノード３０ｕに移動させている。これらのようなホップ数の変化は、例えば何らかの理由により迂回する形でパケットが伝送されていた場合に生じる。
【０１１１】
第２のノード群を構成するノード３０ｄのホップ数は、この移動に係わらず変化していない。このことから、最小ホップ数の差（＝２＝６−４）の数だけノードをノード３０ｄの前に追加している。そのようにして、各ノードで決定したホップ数はトポロジーツリー上で維持させている。
【０１１２】
ステップＳ７０では、上述したような操作をトポロジーツリーに対して実現させるための処理が行われる。その操作内容に応じて、更新すべきブランチ管理情報の更新、及びトポロジー情報３２中の更新すべきノード管理情報の更新等が合わせて行われる。
【０１１３】
次に、図１２を参照して、ステップＳ７１の処理により行われる操作について説明する。この図１２は、ロス障害が検出されたサブネット群における最小のホップ数が既存のブランチの最小ホップ数より大きい場合の操作例を説明する図である。図１２において、ロス障害の検出により再配置したノードはノード３０ｆ及び３０ｈである。この２つのノード３０ｆ及び３０ｈのそれぞれの元の位置は、例えば図１０に示す位置である。
【０１１４】
本実施形態では、ロス障害が検出されたサブネット群のなかで最小のホップ数が既存のブランチの最小ホップ数より大きい場合、ＬＡＮ／ＷＡＮとで分けて、再配置を行うようにしている。このため、ノード３０ｆ及び３０ｈはそれぞれ生成したブランチ上に再配置し、それらノード３０ｆ及び３０ｈを配置していたブランチは消去している。ノード３０ｆのホップ数は６から７に更新され、ノード３０ｈのホップ数は７から８に更新されている。このことから、ノード３０ｆは、ノード３０ｘを分岐ノードとするブランチを生成し、この生成したブランチ上に移動させている。同様にノード３０ｈは、ノード３０ｊを分岐ノードとするブランチを生成し、この生成したブランチ上に移動させている。
【０１１５】
ステップＳ７１では、上述したような操作をトポロジーツリーに対して実現させるための処理が行われる。その操作内容に応じて、作成すべきブランチ管理情報の作成、削除すべきブランチ管理情報の削除、及び更新すべきノード管理情報の更新等が合わせて行われる。
【０１１６】
本実施形態では、上述したような内容のトポロジーツリー構成処理を随時、例えば一定時間間隔で繰り返し実行する。その繰り返しの実行により、ノードの配置、或いは／及び、再配置、並びにブランチの追加、消去、或いは／及び、移動、が随時、行われる。その結果、作成されるトポロジーツリーは正確なものに徐々に修正されていくことになる。それにより、修正が行われない、或いはその修正がほとんど行われなくなった場合には、高精度なトポロジーツリーが得られていることとなる。
【０１１７】
ロス障害を利用して不適切な配置を解消するための操作は、実際には、図９〜図１２を参照して説明した操作以外にも数多く存在する。このことから、上記の操作例は一例であり、操作はこれに限定されるものではない。
【０１１８】
本実施形態によるプログラム（トポロジーツリー作成プログラム）は、図１３Ａ〜Ｃに示すパケット解析処理を実現させるパケット解析プログラム、並びに図１４Ａ及びＢに示すトポロジーツリー構成処理を実現させるトポロジーツリー構成プログラムをそれぞれサブプログラムとして含むものである。図２に示す機能構成は、ネットワーク監視装置２０として用いられるコンピュータに、本実施形態によるプログラムを実行させることで実現される。ここで図１５を参照して、本実施形態を適用可能なコンピュータ、つまりこのプログラムを実行することでネットワーク監視装置２０（トポロジーツリー作成装置）として使用可能なコンピュータについて具体的に説明する。
【０１１９】
図１５に示すコンピュータは、ＣＰＵ６１、メモリ６２、入力装置６３、出力装置６４、外部記憶装置６５、媒体駆動装置６６、及びネットワーク接続装置６７を有し、これらがバス６８によって互いに接続された構成となっている。図１５に示す構成は一例であり、これに限定されるものではない。
【０１２０】
ＣＰＵ６１は、当該コンピュータ全体の制御を行う。
メモリ６２は、プログラムの実行、データ更新等の際に、外部記憶装置６５（あるいは可搬型の記録媒体７０）に記憶されているプログラムあるいはデータを一時的に格納するＲＡＭ等の半導体メモリである。ＣＰＵ６１は、プログラムをメモリ６２に読み出して実行することにより、全体の制御を行う。
【０１２１】
入力装置６３は、例えば、キーボード、マウス等の操作装置と接続可能なインターフェースである。接続された操作装置に対するユーザの操作を検出し、その検出結果をＣＰＵ６１に通知する。
【０１２２】
出力装置６４は、例えば表示装置と接続された表示制御装置である。ネットワーク接続装置６７は、例えばネットワーク１を介した通信、及びそのネットワーク１を流れるパケットの受信を行えるものである。外部記憶装置６５は、例えばハードディスク装置である。主に各種データやプログラムの保存に用いられる。
【０１２３】
媒体駆動装置６６は、光ディスクや光磁気ディスク等の可搬型の記録媒体７０にアクセスするものである。
【０１２４】
上記トポロジーツリー作成プログラムは、外部記憶装置６５、若しくは記録媒体７０に記録されているか、或いはネットワーク１を介してネットワーク接続装置６７により取得される。そのトポロジーツリー作成プログラムをメモリ６２に読み出してＣＰＵ６１が実行することにより、ネットワーク監視装置２０に搭載されたトポロジーツリー作成装置は実現される。サブネット管理情報３１、トポロジー情報３２、及びサブネットマスク情報３５は、例えば外部記憶装置６５に保存され、必要に応じてメモリ６２に読み出される。トポロジー情報３２の出力は、例えば出力装置６４を介した表示、ネットワーク接続装置６７を介した外部装置への送信、或いは媒体駆動装置６６を介した記録媒体７０への格納によって行われる。
【０１２５】
このトポロジーツリー作成プログラムが外部記憶装置６５に格納されていると想定した場合、パケットキャプチャ部２１は、ＣＰＵ６１、メモリ６２、外部記憶同意６５、ネットワーク接続装置６７及びバス６８によって実現される。他のホップ数解析部２２、ボトルネック帯域解析部２３、ロス障害検出部２４、サブネット情報判定部２５及びトポロジーツリー構成部２６は共に、例えばＣＰＵ６１、メモリ６２、外部記憶同意６５、及びバス６８によって実現される。
【０１２６】
なお、本実施形態は、ネットワーク監視装置２０上に搭載させた形で実現させているが、別の装置上に実現させても良い。専用の装置として実現させても良い。また、サブネット管理情報、或いはトポロジーツリーを更新する手順は、上述したようなものに限定されない。例えば検出されたロス障害により判明した不適切な配置は、ロス障害が検出されたノードの配置を変更することで解消するのではなく、ロス障害が検出されていないノードの配置を変更することで解消しても良い。不適切な配置を解消する方法も特に限定されるものではない。
【符号の説明】
【０１２７】
１ ネットワーク
１１ ルータ（ノード）
２０ ネットワーク監視装置
２１ パケットキャプチャ部
２２ ホップ数解析部
２３ ボトルネック帯域解析部
２４ ロス障害検出部
２５ サブネット情報判定部
２６ トポロジーツリー構成部
３１ サブネット管理情報リスト
３２ トポロジー情報
【特許請求の範囲】
【請求項１】
サブネットが相互に連結されたネットワークの構成を模擬したトポロジーツリーを作成するトポロジーツリー作成装置であって、
前記ネットワークを流れるパケットを取得するパケット取得手段と、
前記パケットを送信したサブネットである送信元サブネット毎に、前記パケット取得手段が取得したパケットから、該パケットが経由したノードの数であるホップ数、及び該パケットの送信上のボトルネックとなっているボトルネック帯域を特定すると共に、該パケットをロスするロス障害を検出する解析手段と、
前記解析手段が特定したホップ数、及びボトルネック帯域を基に、前記ネットワークに存在するサブネットのなかで前記送信元サブネットとして確認されたサブネットをトポロジーツリー上に配置する配置手段と、
前記解析手段による前記ロス障害の検出結果を用いて、前記配置手段が前記トポロジーツリー上に配置したサブネットのなかで該配置が不適切なサブネットを抽出し、該抽出したサブネットの配置を変更する配置修正手段と、
を具備することを特徴とするトポロジーツリー作成装置。
【請求項２】
前記解析手段は、前記ボトルネック帯域の特定結果から、前記送信元サブネットを伝送速度の異なる第１及び第２の種類のうちの何れかに分類し、
前記配置手段は、前記解析手段による分類結果を基に、同一の種類のサブネットを特定されたホップ数に従って配置したブランチを前記トポロジーツリー上に作成する、
ことを特徴とする請求項１記載のトポロジーツリー作成装置。
【請求項３】
前記配置修正手段は、前記不適切なサブネットとして、前記解析手段が前記ロス障害を検出したサブネットのなかで前記トポロジーツリー上、該ロス障害が検出されないサブネットから送信されるパケットの送信経路となるサブネットを抽出する、
ことを特徴とする請求項１、または２記載のトポロジーツリー作成装置。
【請求項４】
前記配置修正手段は、前記不適切なサブネットのうちの少なくとも一つがブランチの一部を構成していた場合に、新たに一つ以上のブランチを作成し、該作成したブランチに該不適切なサブネットのうちの少なくとも一つを移動させる、
ことを特徴とする請求項３記載のトポロジーツリー作成装置。
【請求項５】
前記解析手段は、前記送信元サブネットのなかで前記パケットを送信したデータ処理装置毎に、前記ボトルネック帯域を特定して前記分類を行うことにより、該データ処理装置毎の分類結果から該送信元サブネット全体の分類を行う、
ことを特徴とする請求項１記載のトポロジーツリー作成装置。
【請求項６】
前記解析手段は、前記送信元サブネットのなかで前記パケットを送信したデータ処理装置毎に、前記ホップ数を特定し、該データ処理装置毎の特定結果から該送信元サブネットのホップ数を特定する、
ことを特徴とする請求項１記載のトポロジーツリー作成装置。
【請求項７】
サブネットが相互に連結されたネットワークの構成を模擬したトポロジーツリーを作成するトポロジーツリー作成装置として用いられるコンピュータに、
前記ネットワークを流れるパケットを取得するパケット取得機能と、
前記パケットを送信したサブネットである送信元サブネット毎に、前記パケット取得機能により取得したパケットから、該パケットが経由したノードの数であるホップ数、及び該パケットの送信上のボトルネックとなっているボトルネック帯域を特定すると共に、該パケットをロスするロス障害を検出する解析機能と、
前記解析機能により特定したホップ数、及びボトルネック帯域を基に、前記ネットワークに存在するサブネットのなかで前記送信元サブネットとして確認されたサブネットを前記トポロジーツリー上に配置する配置機能と、
前記解析機能による前記ロス障害の検出結果を用いて、前記配置機能により前記トポロジーツリー上に配置したサブネットのなかで該配置が不適切なサブネットを抽出し、該抽出したサブネットの配置を変更する配置修正機能と、
を実現させるためのプログラム。
【請求項８】
サブネットが相互に連結されたネットワークの構成を模擬したトポロジーツリーをコンピュータにより作成する方法であって、
前記ネットワークを流れるパケットを取得し、
前記パケットを送信したサブネットである送信元サブネット毎に、取得したパケットから、該パケットが経由したノードの数であるホップ数、及び該パケットの送信上のボトルネックとなっているボトルネック帯域を特定すると共に、該パケットをロスするロス障害を検出し、
特定したホップ数、及びボトルネック帯域を基に、前記ネットワークに存在するサブネットのなかで前記送信元サブネットとして確認されたサブネットを前記トポロジーツリー上に配置し、
前記ロス障害の検出結果を用いて、前記トポロジーツリー上に配置したサブネットのなかで該配置が不適切なサブネットを抽出し、該抽出したサブネットの配置を変更する、
ことを特徴とするトポロジーツリー作成方法。
【請求項１】
サブネットが相互に連結されたネットワークの構成を模擬したトポロジーツリーを作成するトポロジーツリー作成装置であって、
前記ネットワークを流れるパケットを取得するパケット取得手段と、
前記パケットを送信したサブネットである送信元サブネット毎に、前記パケット取得手段が取得したパケットから、該パケットが経由したノードの数であるホップ数、及び該パケットの送信上のボトルネックとなっているボトルネック帯域を特定すると共に、該パケットをロスするロス障害を検出する解析手段と、
前記解析手段が特定したホップ数、及びボトルネック帯域を基に、前記ネットワークに存在するサブネットのなかで前記送信元サブネットとして確認されたサブネットをトポロジーツリー上に配置する配置手段と、
前記解析手段による前記ロス障害の検出結果を用いて、前記配置手段が前記トポロジーツリー上に配置したサブネットのなかで該配置が不適切なサブネットを抽出し、該抽出したサブネットの配置を変更する配置修正手段と、
を具備することを特徴とするトポロジーツリー作成装置。
【請求項２】
前記解析手段は、前記ボトルネック帯域の特定結果から、前記送信元サブネットを伝送速度の異なる第１及び第２の種類のうちの何れかに分類し、
前記配置手段は、前記解析手段による分類結果を基に、同一の種類のサブネットを特定されたホップ数に従って配置したブランチを前記トポロジーツリー上に作成する、
ことを特徴とする請求項１記載のトポロジーツリー作成装置。
【請求項３】
前記配置修正手段は、前記不適切なサブネットとして、前記解析手段が前記ロス障害を検出したサブネットのなかで前記トポロジーツリー上、該ロス障害が検出されないサブネットから送信されるパケットの送信経路となるサブネットを抽出する、
ことを特徴とする請求項１、または２記載のトポロジーツリー作成装置。
【請求項４】
前記配置修正手段は、前記不適切なサブネットのうちの少なくとも一つがブランチの一部を構成していた場合に、新たに一つ以上のブランチを作成し、該作成したブランチに該不適切なサブネットのうちの少なくとも一つを移動させる、
ことを特徴とする請求項３記載のトポロジーツリー作成装置。
【請求項５】
前記解析手段は、前記送信元サブネットのなかで前記パケットを送信したデータ処理装置毎に、前記ボトルネック帯域を特定して前記分類を行うことにより、該データ処理装置毎の分類結果から該送信元サブネット全体の分類を行う、
ことを特徴とする請求項１記載のトポロジーツリー作成装置。
【請求項６】
前記解析手段は、前記送信元サブネットのなかで前記パケットを送信したデータ処理装置毎に、前記ホップ数を特定し、該データ処理装置毎の特定結果から該送信元サブネットのホップ数を特定する、
ことを特徴とする請求項１記載のトポロジーツリー作成装置。
【請求項７】
サブネットが相互に連結されたネットワークの構成を模擬したトポロジーツリーを作成するトポロジーツリー作成装置として用いられるコンピュータに、
前記ネットワークを流れるパケットを取得するパケット取得機能と、
前記パケットを送信したサブネットである送信元サブネット毎に、前記パケット取得機能により取得したパケットから、該パケットが経由したノードの数であるホップ数、及び該パケットの送信上のボトルネックとなっているボトルネック帯域を特定すると共に、該パケットをロスするロス障害を検出する解析機能と、
前記解析機能により特定したホップ数、及びボトルネック帯域を基に、前記ネットワークに存在するサブネットのなかで前記送信元サブネットとして確認されたサブネットを前記トポロジーツリー上に配置する配置機能と、
前記解析機能による前記ロス障害の検出結果を用いて、前記配置機能により前記トポロジーツリー上に配置したサブネットのなかで該配置が不適切なサブネットを抽出し、該抽出したサブネットの配置を変更する配置修正機能と、
を実現させるためのプログラム。
【請求項８】
サブネットが相互に連結されたネットワークの構成を模擬したトポロジーツリーをコンピュータにより作成する方法であって、
前記ネットワークを流れるパケットを取得し、
前記パケットを送信したサブネットである送信元サブネット毎に、取得したパケットから、該パケットが経由したノードの数であるホップ数、及び該パケットの送信上のボトルネックとなっているボトルネック帯域を特定すると共に、該パケットをロスするロス障害を検出し、
特定したホップ数、及びボトルネック帯域を基に、前記ネットワークに存在するサブネットのなかで前記送信元サブネットとして確認されたサブネットを前記トポロジーツリー上に配置し、
前記ロス障害の検出結果を用いて、前記トポロジーツリー上に配置したサブネットのなかで該配置が不適切なサブネットを抽出し、該抽出したサブネットの配置を変更する、
ことを特徴とするトポロジーツリー作成方法。
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１４Ａ】
【図１４Ｂ】
【図１５】
【図１】
【図９】
【図１０】
【図１１】
【図１２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１４Ａ】
【図１４Ｂ】
【図１５】
【図１】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２０１１−１４６９２０（Ｐ２０１１−１４６９２０Ａ）
【公開日】平成２３年７月２８日（２０１１．７．２８）
【国際特許分類】
【出願番号】特願２０１０−６０２８（Ｐ２０１０−６０２８）
【出願日】平成２２年１月１４日（２０１０．１．１４）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２３年７月２８日（２０１１．７．２８）
【国際特許分類】
【出願日】平成２２年１月１４日（２０１０．１．１４）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]