(57)【要約】【課題】ネットワークトポロジの構成に必要な経路情報の量を削減して効率的にネットワークトポロジを構成する。【解決手段】自律システムが複数相互接続されたインターネットにおいて、自律システム間で伝搬されている経路情報を用いて、自律システム間の接続関係であるネットワークトポロジを構成するネットワークトポロジ構成方法であって、インターネット上のネットワーク機器と通信して経路情報を収集するステップ１と、前記収集した経路情報を蓄積手段に蓄積するステップ２と、前記蓄積手段に蓄積した経路情報に基づき、一定期間毎にネットワークトポロジを計算するための中間結果を計算し、前記蓄積手段に蓄積するステップ３と、前記蓄積手段に蓄積された中間結果と、前記中間結果の保存時刻から任意の時刻までの経路情報とに基づき、前記任意の時刻におけるネットワークトポロジを計算するステップ４とを有する。【選択図】図２
2010245861.tif 000002
【特許請求の範囲】
【請求項１】
自律システムが複数相互接続されたインターネットにおいて、自律システム間で伝搬されている経路情報を用いて、自律システム間の接続関係であるネットワークトポロジを構成するネットワークトポロジ構成方法であって、
インターネット上のネットワーク機器と通信して経路情報を収集するステップ１と、
前記収集した経路情報を蓄積手段に蓄積するステップ２と、
前記蓄積手段に蓄積した経路情報に基づき、一定期間毎にネットワークトポロジを計算するための中間結果を計算し、前記蓄積手段に蓄積するステップ３と、
前記蓄積手段に蓄積された中間結果と、前記中間結果の保存時刻から任意の時刻までの経路情報とに基づき、前記任意の時刻におけるネットワークトポロジを計算するステップ４とを有することを特徴とするネットワークトポロジ構成方法。
【請求項２】
前記経路情報は、経路ｐと、経路情報がある自律システムによって広報されてから観測先の自律システムで受信されるまでに経由した自律システムを順番に記録したリストであるＡＳ-pathを含み、前記中間結果を計算する時刻をｔ１、Ｐを経路ｐと、ＡＳ-pathの組の集合とするとき、
前記ステップ３は、時刻ｔ１より前の時刻ｔ２において前記蓄積手段に蓄積された中間結果を取得し、当該取得した中間結果をＰの初期値とするステップ３１と、
時刻ｔ２から時刻ｔまでの間に取得した経路情報を、前記蓄積手段から検索・取得するステップ３２と、
前記取得した経路情報を受信時刻の時系列順に並べ、この集合をＭとするステップ３３と、
前記時系列順に並べた経路情報の集合Ｍの中から受信時刻の最も古い経路情報を、処理対象の経路情報ｍとして取り出すステップ３４と、
前記ｍが経路を広報するための経路情報で、かつ、前記ｍ中の経路ｐを含む要素がＰに存在する場合に、経路ｐを含む要素をすべてＰから削除した後、前記ｍに含まれる経路とＡＳ-pathの組をＰに追加するステップ３５と、
前記ｍが経路を広報するための経路情報で、かつ、前記ｍ中の経路ｐを含む要素がＰに存在しない場合に、前記ｍに含まれる経路とＡＳ-pathの組をＰに追加するステップ３６と、
前記ｍが広報済みの経路を削除する経路情報の場合で、前記ｍ中の経路ｐを含む要素がＰに存在しない場合にはなにもせず、前記ｍ中の経路ｐを含む要素がＰに存在する場合に、経路ｐを含む要素をすべてＰから削除するステップ３７とを有し、
前記Ｍ中の経路情報のすべてについて前記ステップ３５ないしステップ３７を実行した後に得られるＰを、時刻t1における中間結果とすることを特徴とする請求項１に記載のネットワークトポロジ構成方法。
【請求項３】
前記経路情報の収集を開始した時刻をｔ０とするとき、前記時刻ｔ１よりも前の時刻に前記蓄積手段に蓄積された中間結果が存在しない場合に、前記ステップ３１、ステップ３２に代えて、
時刻ｔ０から時刻ｔ１までの間に取得した経路情報を、前記蓄積手段から検索・取得するステップ３０を実行した後、前記ステップ３３ないしステップ３７を実行することを特徴とする請求項２に記載のネットワークトポロジ構成方法。
【請求項４】
前記経路情報は、経路ｐと、経路情報がある自律システムによって広報されてから観測先の自律システムで受信されるまでに経由した自律システムを順番に記録したリストであるＡＳ-pathを含み、前記ネットワークトポロジを計算する時刻をｔ１、Ｐを経路ｐと、ＡＳ-pathの組の集合とするとき、
前記ステップ４は、時刻ｔ１より前の時刻ｔ２において前記蓄積手段に蓄積された中間結果を取得し、当該取得した中間結果をＰの初期値とするステップ４１と、
時刻ｔ２から時刻ｔ１までの間に取得した経路情報を、前記蓄積手段から検索・取得するステップ４２と、
前記取得した経路情報を受信時刻の時系列順に並べ、この集合をＭとするステップ４３と、
前記時系列順に並べた経路情報の集合Ｍの中から受信時刻の最も古い経路情報を、処理対象の経路情報ｍとして取り出すステップ４４と、
前記ｍが経路を広報するための経路情報で、かつ、前記ｍ中の経路ｐを含む要素がＰに存在する場合に、経路ｐを含む要素をすべてＰから削除した後、前記ｍに含まれる経路とＡＳ-pathの組をＰに追加するステップ４５と、
前記ｍが経路を広報するための経路情報で、かつ、前記ｍ中の経路ｐを含む要素がＰに存在しない場合に、前記ｍに含まれる経路とＡＳ-pathの組をＰに追加するステップ４６と、
前記ｍが広報済みの経路を削除する経路情報の場合で、前記ｍ中の経路ｐを含む要素がＰに存在しない場合にはなにもせず、前記ｍ中の経路ｐを含む要素がＰに存在する場合に、経路ｐを含む要素をすべてＰから削除するステップ４７と、
前記Ｍ中の経路情報のすべてについて前記ステップ４５ないしステップ４７を実行した後に、得られたＰの要素であるすべてのＡＳ-pathを取り出すステップ４８と、
取り出したＡＳ-pathから自律システム間の二項関係の集合を計算し、計算した集合のすべの和集合を作り、前記時刻ｔ１のネットワークトポロジを求めるステップ４９とを有することを特徴とする請求項１に記載のネットワークトポロジ構成方法。
【請求項５】
前記経路情報の収集を開始した時刻をｔ０とするとき、前記時刻ｔ１よりも前の時刻に前記蓄積手段に蓄積された中間結果が存在しない場合に、前記ステップ４１、ステップ４２に代えて、
時刻ｔ０から時刻ｔ１までの間に取得した経路情報を、前記蓄積手段から検索・取得するステップ４０を実行した後、前記ステップ４３ないしステップ４７を実行することを特徴とする請求項４に記載のネットワークトポロジ構成方法。
【請求項６】
自律システムが複数相互接続されたインターネットにおいて、自律システム間で伝搬されている経路情報を用いて、自律システム間の接続関係であるネットワークトポロジを構成するネットワークトポロジ構成装置であって、
経路情報を蓄積する蓄積手段と、
インターネット上のネットワーク機器と通信して経路情報を収集する手段１と、
前記手段１において収集した経路情報を前記蓄積手段に蓄積する手段２と、
前記蓄積手段に蓄積した経路情報に基づき、一定期間毎にネットワークトポロジを計算するための中間結果を計算し、前記蓄積手段に蓄積する手段３と、
前記蓄積手段に蓄積された中間結果と、前記中間結果の保存時刻から任意の時刻までの経路情報とに基づき、前記任意の時刻におけるネットワークトポロジを計算する手段４とを有することを特徴とするネットワークトポロジ構成装置。
【請求項７】
請求項１ないし請求項５のいずれか１項に記載のネットワークトポロジ構成方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークトポロジ構成方法、ネットワークトポロジ構成装置およびプログラムに係わり、特に、ネットワークトポロジを求める際に有効な技術に関する。
【背景技術】
【０００２】
ネットワークの解析診断を行う場合、現在や過去のネットワークの状態およびその変動の様子を把握することはネットワーク管理者が適切に管理業務を行う上で重要である。
一般に、ネットワークの状態や変動を把握するために、ネットワーク管理者はさまざまな種類の情報を利用する。例えば、ネットワークの負荷やトラフィックの状態を調べるにはルータのログ、パケットアナライザの測定データなどが利用でき、ネットワークの接続性を知るためにはtracerouteコマンドの結果やパケットのＲＴＴ（Round Trip Time）などがよく利用されている。また、これらの状態の時間的な変動が知りたい場合、上記の情報を一定期間分蓄積しておき、それらを解析することによって変動の状態を把握する。
このようなネットワーク解析に使われる情報の一つにＢＧＰというプロトコルによって自律システム（Autonomous System;以下、ＡＳという）間を伝搬している経路情報（以下、ＢＧＰ情報）がある。ＡＳ（Autonomous System）とは、インターネットプロバイダ（ＩＳＰ）や大学などの単一組織によって運営されているネットワークの集合体であり、インターネットはＡＳ間が相互接続することによって構成されている。
ＢＧＰはＡＳ間で経路制御を行うための標準プロトコルであり、それにより伝搬される情報は複数のＡＳが含まれる広域ネットワーク解析には不可欠である。そして、このＢＧＰ情報の主要な利用方法の一つに任意の時刻のＡＳ間の接続関係、すなわちネットワークトポロジの再現がある。ＢＧＰ情報から構成されるネットワークトポロジはインターネット全体の構造を表現しており、広域ネットワークの挙動を知るためには非常に重要な情報である。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】“Visualizing INterdomain Routing with BGPlay”，Journal of  Graph Algorithms and Applications Vol.9 No.1 pp.117-148(2005)
【発明の概要】
【発明が解決しようとする課題】
【０００４】
現在のインターネットでは約３万のＡＳがそれぞれ独立にＢＧＰを用いて自己の持つ経路の広報、変更、取り消しなどを行っている。このようにしてインターネット全体に伝搬されている経路の総数は約２５万であり年々増え続けている。ＢＧＰで伝搬される経路情報にはさまざまな情報が含まれているが、その中の一つにＡＳ-path情報がある。
ＡＳ-path情報とは、ＢＧＰ情報が、あるＡＳによって広報されてから観測先のＡＳで受信されるまでに経由したＡＳを順番に記録したリストである。実際に伝搬されるＢＧＰ情報の例を以下に示す。
[2008/04/07 16:04:53] [UP] [AD] (a.b.c.0/24) ORIGIN=0
AS_PATH=((AS_SEQUENCE x y z)) NEXT_HOP=a.b.c.d 
MED=5 LOCAL_PREF=100
上記情報中のＡＳ-PATHと書かれた項目がＡＳ-path情報であり、この例を用いて説明すると、この経路情報は、ｚというＡＳで生成され、ｙというＡＳを経由して、ｘというＡＳで受信されたことを表している。
本来、ＢＧＰにおけるＡＳ-path情報は情報の経由地を明確にすることで情報伝搬のループなど無駄な伝搬を避けるために用いられるものであるが、このＡＳ-path情報はＡＳ間の接続関係（の一部）を直接表現しているためＡＳ間の接続関係であるネットワークトポロジを構成する目的にも多く利用されている。なお、ＢＧＰ情報からネットワークトポロジを構成する試みについては、前述の非特許文献１に記載されている。
【０００５】
ＢＧＰによる経路情報は前述のように世界中のＡＳがそれぞれのポリシーに基づいて広報、削除、変更を繰り返し行っている。そのため、ＢＧＰ情報に含まれるＡＳ-path情報も常に変動しており、それらを元にして構成されるネットワークトポロジも固定されることなく常に変動している。
そのため、特定の時刻におけるネットワークトポロジを構成するためにはＢＧＰ情報の受信開始から指定時刻までの間に受信したすべてのＢＧＰ情報が必要になる。ところが、一般に一つのＡＳで観測できるＢＧＰ情報の量は非常に多く、１日の受信量が数十万に達することもある。これだけのメッセージを収集解析してネットワークトポロジを構成することは多くの手間と時間がかかるため、より効率的な構成方法が求められていた。
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、ネットワークトポロジ構成方法およびネットワークトポロジ構成装置において、ネットワークトポロジの構成に必要な経路情報の量を削減して効率的にネットワークトポロジを構成することが可能となる技術を提供することにある。
また、本発明の他の目的は、前述のネットワークトポロジ構成方法をコンピュータに実行させるためのプログラムを提供することにある。
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述及び添付図面によって明らかにする。
【課題を解決するための手段】
【０００６】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
（１）自律システムが複数相互接続されたインターネットにおいて、自律システム間で伝搬されている経路情報を用いて、自律システム間の接続関係であるネットワークトポロジを構成するネットワークトポロジ構成方法であって、インターネット上のネットワーク機器と通信して経路情報を収集するステップ１と、前記収集した経路情報を蓄積手段に蓄積するステップ２と、前記蓄積手段に蓄積した経路情報に基づき、一定期間毎にネットワークトポロジを計算するための中間結果を計算し、前記蓄積手段に蓄積するステップ３と、  前記蓄積手段に蓄積された中間結果と、前記中間結果の保存時刻から任意の時刻までの経路情報とに基づき、前記任意の時刻におけるネットワークトポロジを計算するステップ４とを有する。
【０００７】
（２）（１）において、前記経路情報は、経路ｐと、経路情報がある自律システムによって広報されてから観測先の自律システムで受信されるまでに経由した自律システムを順番に記録したリストであるＡＳ-pathを含み、前記中間結果を計算する時刻をｔ１、Ｐを経路ｐと、ＡＳ-pathの組の集合とするとき、前記ステップ３は、時刻ｔ１より前の時刻ｔ２において前記蓄積手段に蓄積された中間結果を取得し、当該取得した中間結果をＰの初期値とするステップ３１と、時刻ｔ２から時刻ｔまでの間に取得した経路情報を、前記蓄積手段から検索・取得するステップ３２と、前記取得した経路情報を受信時刻の時系列順に並べ、この集合をＭとするステップ３３と、前記時系列順に並べた経路情報の集合Ｍの中から受信時刻の最も古い経路情報を、処理対象の経路情報ｍとして取り出すステップ３４と、前記ｍが経路を広報するための経路情報で、かつ、前記ｍ中の経路ｐを含む要素がＰに存在する場合に、経路ｐを含む要素をすべてＰから削除した後、前記ｍに含まれる経路とＡＳ-pathの組をＰに追加するステップ３５と、前記ｍが経路を広報するための経路情報で、かつ、前記ｍ中の経路ｐを含む要素がＰに存在しない場合に、前記ｍに含まれる経路とＡＳ-pathの組をＰに追加するステップ３６と、前記ｍが広報済みの経路を削除する経路情報の場合で、前記ｍ中の経路ｐを含む要素がＰに存在しない場合にはなにもせず、前記ｍ中の経路ｐを含む要素がＰに存在する場合に、経路ｐを含む要素をすべてＰから削除するステップ３７とを有し、前記Ｍ中の経路情報のすべてについて前記ステップ３５ないしステップ３７を実行した後に得られるＰを、時刻ｔ１における中間結果とする。
（３）（２）において、前記経路情報の収集を開始した時刻をｔ０とするとき、前記時刻t1よりも前の時刻に前記蓄積手段に蓄積された中間結果が存在しない場合に、前記ステップ３１、ステップ３２に代えて、時刻ｔ０から時刻ｔ１までの間に取得した経路情報を、前記蓄積手段から検索・取得するステップ３０を実行した後、前記ステップ３３ないしステップ３７を実行する。
【０００８】
（４）（１）において、前記経路情報は、経路ｐと、経路情報がある自律システムによって広報されてから観測先の自律システムで受信されるまでに経由した自律システムを順番に記録したリストであるＡＳ-pathを含み、前記ネットワークトポロジを計算する時刻をｔ１、Ｐを経路ｐと、ＡＳ-pathの組の集合とするとき、前記ステップ４は、時刻ｔ１より前の時刻ｔ２において前記蓄積手段に蓄積された中間結果を取得し、当該取得した中間結果をＰの初期値とするステップ４１と、時刻ｔ２から時刻ｔ１までの間に取得した経路情報を、前記蓄積手段から検索・取得するステップ４２と、前記取得した経路情報を受信時刻の時系列順に並べ、この集合をＭとするステップ４３と、前記時系列順に並べた経路情報の集合Ｍの中から受信時刻の最も古い経路情報を、処理対象の経路情報ｍとして取り出すステップ４４と、前記ｍが経路を広報するための経路情報で、かつ、前記ｍ中の経路ｐを含む要素がＰに存在する場合に、経路ｐを含む要素をすべてＰから削除した後、前記ｍに含まれる経路とＡＳ-pathの組をＰに追加するステップ４５と、前記ｍが経路を広報するための経路情報で、かつ、前記ｍ中の経路ｐを含む要素がＰに存在しない場合に、前記ｍに含まれる経路とＡＳ-pathの組をＰに追加するステップ４６と、前記ｍが広報済みの経路を削除する経路情報の場合で、前記ｍ中の経路ｐを含む要素がＰに存在しない場合にはなにもせず、前記ｍ中の経路ｐを含む要素がＰに存在する場合に、経路ｐを含む要素をすべてＰから削除するステップ４７と、前記Ｍ中の経路情報のすべてについて前記ステップ４５ないしステップ４７を実行した後に、得られたＰの要素であるすべてのＡＳ-pathを取り出すステップ４８と、取り出したＡＳ-pathから自律システム間の二項関係の集合を計算し、計算した集合のすべの和集合を作り、前記時刻ｔ１のネットワークトポロジを求めるステップ４９とを有する。
（５）（４）において、前記経路情報の収集を開始した時刻をｔ０とするとき、前記時刻ｔ１よりも前の時刻に前記蓄積手段に蓄積された中間結果が存在しない場合に、前記ステップ４１、ステップ４２に代えて、時刻ｔ０から時刻ｔ１までの間に取得した経路情報を、前記蓄積手段から検索・取得するステップ４０を実行した後、前記ステップ４３ないしステップ４７を実行する。
【０００９】
（６）自律システムが複数相互接続されたインターネットにおいて、自律システム間で伝搬されている経路情報を用いて、自律システム間の接続関係であるネットワークトポロジを構成するネットワークトポロジ構成装置であって、経路情報を蓄積する蓄積手段と、インターネット上のネットワーク機器と通信して経路情報を収集する手段１と、前記手段１において収集した経路情報を前記蓄積手段に蓄積する手段２と、前記蓄積手段に蓄積した経路情報に基づき、一定期間毎にネットワークトポロジを計算するための中間結果を計算し、前記蓄積手段に蓄積する手段３と、前記蓄積手段に蓄積された中間結果と、前記中間結果の保存時刻から任意の時刻までの経路情報とに基づき、前記任意の時刻におけるネットワークトポロジを計算する手段４とを有する。
（７）（１）ないし（５）のいずれか１項に記載のネットワークトポロジ構成方法をコンピュータに実行させるためのプログラムである。
【発明の効果】
【００１０】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
本発明によれば、ネットワークトポロジの構成に必要な経路情報の量を削減して効率的にネットワークトポロジを構成することが可能となる。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施例のネットワークトポロジ構成方法において、時刻ｔにおける中間結果（snapshot）であるＳｔを計算する手順を説明するためのフローチャートである。
【図２】本発明の実施例のネットワークトポロジを構成する手順を説明するためのフローチャートである。
【図３】本発明の実施例の手法と従来例の手法との違いを説明するため概略図である。
【図４】本発明の実施例のネットワークトポロジ構成装置の概略構成を示すブロック図である。
【図５】従来のＢＧＰ情報のみを用いてネットワークトポロジを構成する手順を説明するためのフローチャートである。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施例を詳細に説明する。
なお、実施例を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
［従来例］
本発明をより分かりやすくするために、本発明を説明する前に、始めに、従来のＢＧＰ情報を用いてネットワークトポロジを構成する手順を説明する。
従来の手順を説明するために以下の定義および前提条件を用いる。ＢＧＰ情報は、ＢＧＰメッセージｍを要素とする集合とし、ｍは、以下の（１）ないし（４）の４つの組として定義する。
（１）ｔ：メッセージの受信時刻
（２）ｐ：メッセージで広報される経路
（３）ａ：メッセージが経由したＡＳ-path
（４）ｋ：メッセージの属性（ＡＤ：経路を広報するためのメッセージ、ＷＤ：広報済みの経路を削除するためのメッセージ）
ネットワークトポロジ計算の中間結果Ｐを、メッセージで広報される経路と、メッセージが経由したＡＳ-pathの組の集合によって定義する。つまり、Ｐ＝｛（ｐｉ、ａｉ）｜１≦ｉ≦ｎ｝とする。
また、以下の説明ではＢＧＰ情報の受信開始時刻をｔ０とし、求めたいネットワークトポロジは時刻ｔ１（ｔ０≦ｔ１）におけるトポロジＴ１とする。また、ｔ０以降に受信したすべてのＢＧＰメッセージはあらかじめデータベースなどの記憶装置に保存されているものとする。
【００１３】
以下、従来のＢＧＰ情報を用いてネットワークトポロジを構成する手順を説明する。
（１）ステップ１；時刻ｔ０から時刻ｔ１において受信したすべてのＢＧＰメッセージを記憶装置から検索し、取得する。
（２）ステップ２；取得したＢＧＰメッセージを受信時刻の時系列順に整理する。
（３）ステップ３；整理したＢＧＰメッセージの集合に対して、メッセージの受信時刻の古いものから順番に以下の処理を行う。処理対象のメッセージｍｉを、ｍｉ＝｛ｔｉ，ｐｉ，ａｉ，ｋｉ｝とする。
（３−１）ＢＧＰメッセージの属性がＡＤ（ｋｉ＝ＡＤ）の場合
（３−１−１）経路ｐｉがすでに別のメッセージによって広報されていた場合、すなわち、（ｐｉ，ａ）（ａはＡＳ-path）がＰに含まれていた場合、そのようなすべての（ｐｉ、ａ）をＰから削除し、ｍｉに含まれる経路とＡＳ-path組、すなわち、（ｐｉ，ａｉ）をＰに追加する。
（３−１−２）経路ｐｉがまだ別のメッセージによって広報されていない場合、すなわち、（ｐｉ，ａ）（ａはＡＳ-path）がＰに含まれていない場合、ｍｉに含まれる経路とＡＳ-pathの組、すなわち、（ｐｉ，ａｉ）をＰに追加する。
（３−２）ＢＧＰメッセージの属性がＷＤ（ｋｉ＝ＷＤ）の場合
経路ｐｉがすでに別のメッセージによって広報されていた場合、すなわち、（ｐｉ，ａ）（ａはＡＳ-path）がＰに含まれていた場合、そのようなすべての（ｐｉ，ａ）をＰから削除し、それ以外の場合は何もしない。
【００１４】
2010245861.tif 000003
【００１５】
【数１】
2010245861.tif 000004
【００１６】
前述の手順を実行するためのフローチャートを図５に示す。以下、図５を用いて、従来のＢＧＰ情報を用いてネットワークトポロジを構成する手順を説明する。
始めに、時刻ｔ０から時刻ｔ１までの間に受信したすべてのＢＧＰメッセージを記憶装置から検索し、取得する（ステップ５０１）。
次に、取得したＢＧＰメッセージを受信時刻の時系列順に並べ、この集合をＭとする（ステップ５０２）。
次に、時系列順に並べたＢＧＰメッセージの集合Ｍの中から受信時刻の最も古いメッセージ（処理対象のメッセージｍ）を一つ取り出す（ステップ５０３）。
次に、ｍ中の経路ｐを含む要素がＰに存在するか否かを判断し（ステップ５０４）、ステップ５０４においてＮＯの場合、即ち、ｍ中の経路ｐを含む要素がＰに存在しない場合は、ステップ５０６に進む。
また、ステップ５０４においてＹＥＳの場合、即ち、ｍ中の経路ｐを含む要素がＰに存在する場合には、経路ｐを含む要素をすべてＰから削除する（ステップ５０５）。
次に、ｍの属性がＡＤ（経路を広報するためのメッセージ）か否かを判断し（ステップ５０６）、ステップ５０６においてＮＯの場合、即ち、ｍの属性がＷＤ（広報済みの経路を削除するためのメッセージ）の場合には、ステップ５０８に進む。
【００１７】
また、ステップ５０６においてＹＥＳの場合、即ち、ｍの属性がＡＤの場合には、ｍに含まれる経路とＡＳ-path ａの組（ｐ，ａ）をＰに追加する（ステップ５０７）。
次に、取得したＢＧＰメッセージの集合Ｍの中に、まだメッセージが残っているか否かを判断し（ステップ５０８）、ステップ５０８においてＹＥＳの場合、即ち、取得したＢＧＰメッセージの集合Ｍの中に、まだメッセージが残っている場合には、ステップ５０３からの処理を繰り返す。
また、ステップ５０８においてＮＯの場合、即ち、取得したＢＧＰメッセージの集合Ｍの中に、メッセージが残っていない場合には、得られたＰの要素である二項目（ＡＳ-path部分）からすべてのＡＳ-pathを取り出す（ステップ５０９）。
次に、取り出したＡＳ-pathからＡＳ間の二項関係の集合を計算し、計算した集合のすべの和集合を作る（ステップ５１０）。
以上の手順により、前述の（１）式に示すネットワークトポロジＴ１を求める。
このように、従来の方法では、時刻ｔ０と時刻ｔ１の差に比例して、ステップ５０１において取得するＢＧＰメッセージの量が増え、構成のための処理時間が増大するという問題がある。
【００１８】
［実施例１］
本発明の実施例のネットワークトポロジ構成方法では、定期的な時刻にネットワークトポロジの中間結果をあらかじめ計算して記憶装置に保存しておく。この計算・保存済みの中間結果をネットワークトポロジのsnapshot（以下、snapshot）と呼ぶ。そして、ある時刻におけるネットワークトポロジを計算する際には、このsnapshotのデータとＢＧＰメッセージを併用する。
始めに、時刻ｔにおけるSnapshotであるＳｔを求める手順を説明する。なお、以下の説明においても、前述の従来例で説明した仮定と定義を用いる。
（１）SnapshotであるＳｔは、前述のステップ３により求められるＰと同等の形式を持つ。すなわち、Ｓｔ＝｛（ｐｉ、ａｉ）｜１≦ｉ≦ｎ｝である。ここで、ｐｉ∈経路、かつ、ａｉ∈ＡＳ-pathである。
（２）Ｓｔは以下の２つの方法により求める。
（２−１）方法１；ＢＧＰメッセージのみから構成する方法
Ｓｔは定義より時刻ｔにおけるネットワークトポロジＴｔを計算する過程で得られる中間結果Ｐと一致する。よって、前述のステップ１ないしステップ４を実行し、得られるＰがＳｔとなる
（２−２）方法２；過去のsnapshotを用いて構成する方法
ｔ−１≦ｔであるような時刻（ｔ−１）に保存されたsnapshotであるＳｔ−１が存在する場合、それを用いて以下のようにＳｔを計算する。
Ｓｔ−１を記憶装置から検索して、取得し、Ｓｔ−１をＰの初期値とする。
次に、時刻（ｔ−１）から時刻ｔまでの間に受信したＢＧＰメッセージの集合を取得し、これらを処理対象のメッセージ集合とする。
以上の条件の元で、前述のステップ３と、ステップ４とを実行し、その時点で得られるＰがＳｔとなる。
【００１９】
前述の手順を実行するためのフローチャートを図１に示す。以下、図１を用いて、本実施例において、時刻ｔにおけるＳｔを計算する手順を説明する。
始めに、時刻ｔより前に保存されたsnapshotデータがあるか否かを判断する。（ステップ１０１）
ステップ１０１においてＮＯの場合、即ち、時刻ｔより前に保存されたsnapshotデータがない場合には、時刻ｔ０から時刻ｔまでの間に受信したすべてのＢＧＰメッセージを記憶装置から検索・取得し（ステップ１０２）、ステップ１０３に進む。
ステップ１０１においてＹＥＳの場合、即ち、時刻ｔより前に保存されたsnapshotデータがある場合には、直前のsnapshotデータを記憶装置から検索し、取得する（ステップ１０４）。ここで、直前のsnapshotデータの保存時刻をｔ−１とする。
次に、取得したsnapshotデータをＰの初期値とし（ステップ１０５）、時刻（ｔ−１）から時刻ｔまでの間に受信したすべてのＢＧＰメッセージを記憶装置から検索し、取得する（ステップ１０６）。
次に、取得したＢＧＰメッセージを受信時刻の時系列順に並べ、この集合をＭとする（ステップ１０３）。
次に、時系列順に並べたＢＧＰメッセージの集合Ｍの中から受信時刻の最も古いメッセージ（処理対象のメッセージｍ）を一つ取り出す（ステップ１０７）。
【００２０】
次に、ｍ中の経路ｐを含む要素がＰに存在するか否かを判断し（ステップ１０８）、ステップ１０８においてＮＯの場合、即ち、ｍ中の経路ｐを含む要素がＰに存在しない場合は、ステップ１１０に進む。
また、ステップ１０８においてＹＥＳの場合、即ち、ｍ中の経路ｐを含む要素がＰに存在する場合には、経路ｐを含む要素をすべてＰから削除する（ステップ１０９）。
次に、ｍの属性がＡＤ（経路を広報するためのメッセージ）か否かを判断し（ステップ１１０）、ステップ１１０においてＮＯの場合、即ち、ｍの属性がＷＤ（広報済みの経路を削除するためのメッセージ）の場合には、ステップ１１２に進む。
また、ステップ１１０においてＹＥＳの場合、即ち、ｍの属性がＡＤの場合には、ｍに含まれる経路とＡＳ-path ａの組（ｐ，ａ）をＰに追加する（ステップ１１１）。
次に、取得したＢＧＰメッセージの集合Ｍの中に、まだメッセージが残っているか否かを判断し（ステップ１１２）、ステップ１１２においてＹＥＳの場合、即ち、取得したＢＧＰメッセージの集合Ｍの中に、まだメッセージが残っている場合には、ステップ１０７からの処理を繰り返す。
また、ステップ１１２においてＮＯの場合、即ち、取得したＢＧＰメッセージの集合Ｍの中に、メッセージが残っていない場合には、得られたＰをsnapshotデータとして出力する（ステップ１１３）。
【００２１】
次に、このsnapshotデータを用いる、本実施例のネットワークトポロジ構成方法について説明する。
（１）始めに、時刻ｔ１より前に保存されたsnapshotデータの中から最新のものを記憶装置から検索・取得する。ここでは、ｔ０≦ｔ２≦ｔ１であるような時刻ｔ２におけるsnapshotであるＳ２があらかじめ計算されて記憶装置に保存されていて、ｔ０からｔ１までに保存されたsnapshotはＳ２のみとする。よって、ここでは、検索結果としてＳ２が得られる。
（２）次に、前のステップで取得したsnapshotデータの保存時刻であるｔ２を用いて「時刻ｔ２から時刻ｔ１までの間に受信したすべてのＢＧＰメッセージ」を記憶装置から検索・取得する。
（３）次に、前のステップで取得したＳ２をＰの初期値とし、さらに、前のステップで取得した「時刻ｔ２から時刻ｔ１までの間に受信したすべてのＢＧＰメッセージ」を対象のメッセージの集合として、前述のステップ３ないしステップ６を実行し、得られたＴが、求めるネットワークトポロジＴ１となる。
【００２２】
前述の手順を実行するためのフローチャートを図２に示す。以下、図２を用いて、本実施例のネットワークトポロジ構成方法について説明する。
始めに、時刻ｔ１より前に保存されたsnapshotデータがあるか否かを判断する。（ステップ２０１）
ステップ２０１においてＮＯの場合、即ち、時刻ｔ１より前に保存されたsnapshotデータがない場合には、時刻ｔ０から時刻ｔ１までの間に受信したすべてのＢＧＰメッセージを記憶装置から検索・取得し（ステップ２０２）、ステップ２０３に進む。
ステップ２０１においてＹＥＳの場合、即ち、時刻ｔ１より前に保存されたsnapshotデータがある場合には、直前のsnapshotデータを記憶装置から検索し、取得する（ステップ２０４）。ここで、直前のsnapshotデータの保存時刻をｔ２とする。
次に、取得したsnapshotデータをＰの初期値とし（ステップ２０５）、時刻ｔ２から時刻ｔ１までの間に受信したすべてのＢＧＰメッセージを記憶装置から検索し、取得する（ステップ２０６）。
次に、取得したＢＧＰメッセージを受信時刻の時系列順に並べ、この集合をＭとする（ステップ２０３）。
次に、時系列順に並べたＢＧＰメッセージの集合Ｍの中から受信時刻の最も古いメッセージ（処理対象のメッセージｍ）を一つ取り出す（ステップ２０７）。
【００２３】
次に、ｍ中の経路ｐを含む要素がＰに存在するか否かを判断し（ステップ２０８）、ステップ２０８においてＮＯの場合、即ち、ｍ中の経路ｐを含む要素がＰに存在しない場合は、ステップ２１０に進む。
また、ステップ２０８においてＹＥＳの場合、即ち、ｍ中の経路ｐを含む要素がＰに存在する場合には、経路ｐを含む要素をすべてＰから削除する（ステップ２０９）。
次に、ｍの属性がＡＤ（経路を広報するためのメッセージ）か否かを判断し（ステップ２１０）、ステップ２１０においてＮＯの場合、即ち、ｍの属性がＷＤ（広報済みの経路を削除するためのメッセージ）の場合には、ステップ２１２に進む。
また、ステップ２１０においてＹＥＳの場合、即ち、ｍの属性がＡＤの場合には、ｍに含まれる経路とＡＳ-path ａの組（ｐ，ａ）をＰに追加する（ステップ２１１）。
次に、取得したＢＧＰメッセージの集合Ｍの中に、まだメッセージが残っているか否かを判断し（ステップ２１２）、ステップ２１２においてＹＥＳの場合、即ち、取得したＢＧＰメッセージの集合Ｍの中に、まだメッセージが残っている場合には、ステップ２０７からの処理を繰り返す。
また、ステップ２１２においてＮＯの場合、即ち、取得したＢＧＰメッセージの集合Ｍの中に、メッセージが残っていない場合には、得られたＰの要素である二項目（ＡＳ-path部分）からすべてのＡＳ-pathを取り出す（ステップ２１３）。
次に、取り出したＡＳ-pathからＡＳ間の二項関係の集合を計算し、計算した集合のすべての和集合を作る（ステップ２１４）。
以上の手順により、前述の（１）式に示すネットワークトポロジＴ１を求める。
【００２４】
本実施例の手法と従来例の手法との違いの図３に示す。なお、図３は、本実施例の手法と従来例の手法との違いを説明するため概略図である。また、図３において、上側が従来手法であり、下側が本実施例の手法である。
本実施例は、ステップ２０６において、「時刻ｔ０から時刻ｔ１」ではなく「時刻ｔ２から時刻ｔ１」のＢＧＰメッセージを検索すればよい点が従来例と異なっている。
従来例であれば、求めたい時刻であるｔ１に対して、常にｔ０−ｔ１間に受信したすべてＢＧＰメッセージを検索、処理しなければならない。このため、ｔ０−ｔ１の差に比例してＢＧＰメッセージの検索時間が増大し、結果として、ネットワークトポロジの構成のための時間も増大していた。
これに対して、本実施例では、時刻ｔ１の値にかかわらずトポロジの構成に必要なＢＧＰメッセージは、直前のsnapshotデータの保存時刻であるｔ２と、時刻ｔ１との間に受信したメッセージだけで十分である。
【００２５】
例えば、図３の上側に示すように、時刻ｔ４におけるネットワークトポロジを求める場合、従来例では、時刻ｔ０から時刻ｔ４までの間に受信したすべてＢＧＰメッセージを検索、処理しなければならない。これに対して、本実施例では、図３の下側に示すように、直前のsnapshotデータの保存時刻であるｔ３と、時刻ｔ４との間に受信したメッセージだけで十分である。
仮に、snapshotを１日毎に定期的に保存した場合、求める時刻ｔ１の値に関わらず、時刻ｔ２と時刻ｔ１の期間は高々１日になるため、時刻ｔ２以降の１日分のメッセージを検索すれば十分である。このことから、本実施例では、求める時刻ｔ１に依存することなくネットワークトポロジの構築に必要な情報の検索時間の上限を見積もることができるという望ましい性質が得られる。
また、本実施例では、従来手法と比べるとsnapshot構築のコストが別にかかるが、前述したように、snapshot自身も別のsnapshotと差分のＢＧＰメッセージから構成できるため、構築のためのメッセージの探索時間や計算量は一定に保たれる。
また、snapshot構築の作業はメッセージ収集などとは独立に行われる上、構築自体も頻繁に行う必要がないので、snapshotの構築が本来の目的であるネットワークトポロジの構築作業に与える影響は殆どない。
【００２６】
図４は、本発明の実施例のネットワークトポロジ構成装置の概略構成を示すブロック図である。
本実施例のネットワークトポロジ構成装置は、情報収集モジュール４０２と、情報解析モジュール４０３と、情報蓄積モジュール４０４と、snapshot計算モジュール４０５と、情報表示モジュール４０６とで構成される。
情報収集モジュール４０２は、ルータなどのネットワーク機器４０１からＢＧＰ情報を収集し、情報解析モジュール４０３に渡す。
情報解析モジュール４０３は、収集したＢＧＰ情報を解析し、解析した結果を情報蓄積モジュール４０４に保存する。
情報蓄積モジュール４０４は、情報解析モジュール４０３から送信された情報を蓄積する。また、ユーザから与えられた検索条件に基づいて情報を検索し情報表示モジュール４０６に渡す。
情報表示モジュール４０６は、ユーザから与えられた検索条件に基づいて情報蓄積モジュール４０４からＢＧＰ情報の検索を行い、ネットワークトポロジを構成してユーザに提示する。
snapshot計算モジュール４０５は、定期的にsnapshotの計算を行って情報蓄積モジュール４０４に保存する。snapshot計算モジュール４０５は、情報蓄積モジュール４０４から過去のsnapshotデータおよび必要なＢＧＰメッセージを検索してsnapshotデータの計算を行う。
【００２７】
以下、本実施例の具体例について説明する。本具体例では、ＢＧＰ情報を時刻ｔ０に開始したとし、その２４×３０時間後である時刻ｔ３０のネットワークトポロジＴ３０を構成する状況を想定する。また、snapshotは、時刻ｔ０から２４時間経過する毎に計算するものとする。
以下では、時刻ｔ０から２４×ｉ（１≦ｉ≦３０）時間経過した時刻をｔｉと表記する。また、ｔｉに作成するsnapshotをＳｉと表記する。
まず、本実施例では、ネットワークトポロジの構成処理とは独立してＢＧＰ情報の収集処理およびsnapshotの計算処理を行う必要がある。はじめに、これらの処理の手順を次に示す。
（１）情報収集モジュール４０２によってＢＧＰ情報を収集する。収集の方法はＢＧＰプロトコルを用いて、ルータなどのネットワーク機器４０１と直接通信して取得する、ルータなどのネットワーク機器４０１のログを解析するなどの方法が考えられる。
（２）情報収集モジュール４０２によって収集されたＢＧＰ情報は、情報解析モジュール４０３によって内容が解析される。具体的には、ＢＧＰメッセージに含まれるＡＳ-path情報や経路情報などネットワーク解析に使う情報をメッセージから抽出する。情報解析モジュール４０３は解析結果を情報蓄積モジュール４０４に保存する。
【００２８】
（３）情報収集処理とは独立にsnapshot計算モジュール４０５は、図１のフローチャートに従い、定期的にsnapshotの計算処理を行う。
（３−１）最初のsnapshotであるＳ１は、時刻ｔ０から２４時間後の時刻ｔ１に計算する。この場合は計算に利用できる過去のsnapshotデータが存在しないので、時刻ｔ０から時刻ｔ１に収集したＢＧＰ情報を用いて、前述した「方法１（ＢＧＰメッセージのみから構成する方法）」により計算を行う。計算結果は情報蓄積モジュール４０４に自動的に保存する。（図１のステップ１０２、ステップ１１３、ステップ１０７〜ステップ１１３）
（３−２）Ｓ２からＳ３０は、それぞれ時刻ｔ２,...,ｔ３０に計算する。Ｓｉ（２≦ｉ≦３０）は、前述した「方法２（過去のsnapshotを用いて構成する方法）」により計算を行う。
（３−２−１）snapshot計算モジュール４０５は、情報蓄積モジュール４０４からＳｉ−１を検索・取得する。（ステップ１０４、ステップ１０５）
（３−２−２）次に、snapshot計算モジュール４０５は、情報蓄積モジュール４０４から「時刻ｔｉ−１から時刻ｔｉまでの間に受信したすべてのＢＧＰメッセージ」を検索し・取得する。（ステップ１０６）
（３−２−３）次に、snapshot計算モジュール４０５は、取得したＳｉ−１と、取得した「時刻ｔｉ−１から時刻ｔｉまでの間のＢＧＰメッセージ」とを入力にして、「方法２」により計算する。その結果、得られたＰが求めるＳｉとなる。（ステップ１０７〜ステップ１１３）
【００２９】
以上の条件の下、情報表示モジュール４０６が、時刻ｔ３０におけるネットワークトポロジＴ３０を計算する手順を以下に説明する。情報表示モジュール４０６は、図２のフローチャートに従い、時刻ｔ３０におけるネットワークトポロジＴ３０を計算する。
ユーザは、情報表示モジュール４０６を通じてシステムにネットワークトポロジＴ３０の計算を要求する。
情報表示モジュール４０６は、情報蓄積モジュール４０４から、時刻Ｔ３０より前に保存された最新のsnapshotを検索する。（図２のステップ２０１）
情報蓄積モジュール４０４は、条件に合致する時刻Ｔ３０より前に保存された最新のsnapshotを返す。この場合は、Ｓ２９がそれに当たる。（図２のステップ２０４）
次に、情報表示モジュール４０６は、Ｓ２９をＰの初期値とする。（図２のステップ２０５）
次に、情報表示モジュール４０６は、Ｓ２９の計算時刻であるｔ２９から時刻ｔ３０までの間に受信したＢＧＰ情報を情報蓄積モジュール４０４に要求する。情報蓄積モジュール４０４は、要求されたメッセージを検索して情報表示モジュール４０６に返す。（図２のステップ２０６）
情報表示モジュール４０６は、取得したＳ２９と、取得したＢＧＰ情報を用いて、図２のステップ２０３、ステップ２０７〜ステップ２１４の手順にしたがい計算を行う。最終的に得られたＴが求めるネットワークトポロジＴ３０となる。
情報表示モジュール４０６は、ネットワークトポロジＴ３０の結果を画面に表示するなどユーザから要求された処理を行う。
【００３０】
なお、前述の説明において、ネットワークトポロジ構成装置はコンピュータに実行させることも可能であり、その場合に、本実施例のネットワークトポロジ構成方法は、コンピュータ内のハードディスクなどに格納されるプログラムを、コンピュータが実行することにより行われる。このプログラムは、ＣＤ−ＲＯＭ、あるいは、ネットワークを介したダウンロードにより供給される。
以上、本発明者によってなされた発明を、前記実施例に基づき具体的に説明したが、本発明は、前記実施例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【符号の説明】
【００３１】
４０１  ネットワーク機器
４０２  情報収集モジュール
４０３  情報解析モジュール
４０４  情報蓄積モジュール
４０５  snapshot計算モジュール
４０６  情報表示モジュール
【図１】
2010245861.tif 000005
【図２】
2010245861.tif 000006
【図３】
2010245861.tif 000007
【図４】
2010245861.tif 000008
【図５】
2010245861.tif 000009