ネットワーク品質計測装置およびその計測パス決定方法
【課題】遺伝的アルゴリズムを用いることで、少数の計測パスで効率的に対象ネットワークの通信品質を監視できるネットワーク品質計測装置およびその計測パス決定方法を提供する。
【解決手段】初期解集団生成部１０１は、計測パスの集合を模したビット列の初期解集団を生成する。次世代候補生成部１０２は、前記初期解集団の各ビット列に遺伝的操作を加えて次世代のビット列候補を生成する。適応度評価部１０３は、各ビット列候補の適応度を評価する。選択部１０４は、前記適応度の評価結果に基づいて、ビット列候補の集団の中から次世代に残すビット列を選択する。通信品質計測部１０５は、前記選択された次世代のビット列の集団の中で適応度が最も高いビット列に対応した計測パスの集合にエンドツーエンドの通信品質を計測させ、その計測結果を取得して評価対象ネットワークの品質を計測する。
【解決手段】初期解集団生成部１０１は、計測パスの集合を模したビット列の初期解集団を生成する。次世代候補生成部１０２は、前記初期解集団の各ビット列に遺伝的操作を加えて次世代のビット列候補を生成する。適応度評価部１０３は、各ビット列候補の適応度を評価する。選択部１０４は、前記適応度の評価結果に基づいて、ビット列候補の集団の中から次世代に残すビット列を選択する。通信品質計測部１０５は、前記選択された次世代のビット列の集団の中で適応度が最も高いビット列に対応した計測パスの集合にエンドツーエンドの通信品質を計測させ、その計測結果を取得して評価対象ネットワークの品質を計測する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク品質計測装置およびその計測パス決定方法に係り、特に、遺伝的アルゴリズムを用いて計測パスを決定するネットワーク品質計測装置およびその計測パス決定方法に関する。
【背景技術】
【０００２】
IPネットワークの通信品質の監視を目的として、監視対象のネットワーク内に分散配置した計測端末間でプローブパケット（テストパケット）を送受し、パケットロス率やパケット遅延などの通信品質を計測するシステムが非特許文献１に開示されている。また、ネット対戦型ゲームの通信を利用し、大規模なIPネットワークの通信品質を計測する技術が、非特許文献２に開示されている。さらに、汎用OS(Microsoft Windows(登録商標)など)を搭載しているユーザ端末を計測端末として利用し、ユーザ端末間でプローブパケットを送受してエンドツーエンドの通信品質を計測するシステムが非特許文献３に開示されている。上記のいずれの計測システムにおいても、計測端末の配置方法や計測パスの決定方法が課題となる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】PerfSONAR: http://www.perfsonar.net/
【非特許文献２】Youngki Lee, Sharad Agarwal, Chris Butcher, and Jitu Padhye,"Measurement and Estimation of Network QoS Among Peer Xbox 360 Game Players," In Proc. of PAM 2008.
【非特許文献３】Ritesh Kumar, Jasleen Kaur, "Efficient Beacon Placement for Network Tomography." In Proc. of IMC 2004 pp.181-186.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、このような従来技術を用いた大規模IPネットワークの品質計測では、以下のような技術課題があった。
【０００５】
非特許文献２のように、計測端末としてネット対戦型ゲーム機を利用してIPネットワークの品質を計測するシステムでは、ゲームの対戦相手との通信と同時にネットワークの通信品質が計測される。しかしながら、通常のネット対戦型ゲームでは多数の候補対戦相手の中から通信品質が高い(例えば、パケット遅延が小さい)通信相手が対戦相手として選択されるため、計測データが高品質なネットワーク区間を対象としたものに偏る傾向がある。このため、ネットワーク全体を網羅的に監視する目的には使用できない。
【０００６】
非特許文献３では、監視対象ネットワークに計測端末を設置するシステム(非特許文献１のシステム)を対象に、ネットワーク内の全てのリンクを少なくとも１本の計測パスが通過する計測端末の配置方法および計測パスの決定方法が提案されている。しかしながら、本手法はネットワーク管理者が計測端末を設置することを想定しているため、ネットワークトポロジーが既知であることが前提であり、多数のユーザ端末を任意に計測端末として利用するシステムには適用できない。
【０００７】
本発明の目的は、上記した従来技術の課題を解決し、遺伝的アルゴリズムを用いることで、少数の計測パスで効率的に対象ネットワークの通信品質を監視できるネットワーク品質計測装置およびその計測パス決定方法を提供することにある。
【課題を解決するための手段】
【０００８】
上記の目的を達成するために、本発明は、ネットワーク上に分散配置された計測端末から計測パスのエンドノードとなる複数のペアを選択してエンドツーエンドの通信品質を計測させ、計測結果を収集してネットワーク品質を計測するネットワーク品質計測装置およびその計測パス決定方法において、以下のような手段を講じた点に特徴がある。
【０００９】
(1)本発明のネットワーク品質計測装置は、計測パスの集合を模したビット列の初期解集団を生成する初期解集団生成手段と、初期解集団の各ビット列に遺伝的操作を加えて次世代のビット列候補を生成する次世代候補生成手段と、各ビット列候補の適応度を評価する適応度評価手段と、適応度の評価結果に基づいて、前記ビット列候補の中から次世代に残すビット列を選択する選択手段とを具備し、選択された次世代のビット列集団に前記遺伝的操作を繰り返すことでビット列の世代を進行させ、選択された次世代のビット列集団の中で適応度が最も高いビット列に対応した計測パスの集合にエンドツーエンドの通信品質を計測させる手段を具備した。
【００１０】
(2)本発明の計測パス決定方法は、計測パスの集合を模したビット列の初期解集団を生成する手順と、初期解集団の各ビット列に遺伝的操作を加えて次世代のビット列候補を生成する手順と、各ビット列候補の適応度を評価する手順と、適応度の評価結果に基づいて、前記ビット列候補の中から次世代に残すビット列を選択する手順と、選択された次世代のビット列の集団に前記遺伝的操作を繰り返すことでビット列の世代を進行させる手順と、選択された次世代のビット列の集団の中で適応度が最も高いビット列を計測パスの集合とする手順とを含むことを特徴とする。
【００１１】
(3)各ビット列候補に対応した計測パスの集合に関して、各計測パスが通過するルータやリンクのうち、評価対象のネットワーク内に位置するルータやリンクの総数が多いビット列候補ほど、その適応度を高くすることを特徴とする。
【００１２】
(4)計測パスの通過履歴を有するルータやリンクを多く通過する計測パスを含むビット列候補の適応値を、当該ルータやリンクの数に応じて相対的に低くすることを特徴とする。
【００１３】
(5)計測パスの通過履歴を有しないルータやリンクを多く通過する計測パスを含むビット列候補の適応値を、当該ルータやリンクの数に応じて相対的に高くすることを特徴とする。
【発明の効果】
【００１４】
本発明によれば、以下のような効果が達成される。
【００１５】
(1)本発明のネットワーク品質計測装置によれば、遺伝的アルゴリズムにより最適化された少数の計測パスを用いてネットワーク品質を効率的に計測できるようになる。
【００１６】
(2)本発明の計測パス決定方法によれば、遺伝的アルゴリズムにより最適な計測パスを選択できるので、ネットワーク品質を少数の計測パスで効率的に計測できるようになる。
【００１７】
(3)計測パスの集合であるビット列に関して、次世代に残すビット列を選択する際の指標となる適応度として、評価対象のネットワーク内に位置するルータやリンクを通過する計測パスを多く含むビット列の適応度が高く設定されるので、ネットワーク品質を小数で効率的に計測できる計測パスの集合を選択できるようになる。
【００１８】
(4)計測パスの通過履歴を有するルータやリンクを通過する計測パスを多く含むビット列候補の適応値を低くしたり、計測パスの通過履歴を有しないルータやリンクを通過する計測パスを多く含むビット列候補の適応値を低くしたりするので、監視対象ネットワークの計測カバー率を向上させることが可能になる。
【図面の簡単な説明】
【００１９】
【図１】本発明が監視対象とするネットワークを含むネットワークの構成を示した図である。
【図２】本発明の一実施形態の動作を示したフローチャートである。
【図３】本発明の一実施形態の動作を模式的に表現した機能ブロック図である。
【図４】ビット列候補の適応度fを求める方法を示した図である。
【図５】適応度fの見直し方法を説明するための図である。
【図６】計測管理サーバの機能ブロック図である。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明が監視対象とするネットワークを含む広域ネットワークの構成を示したブロック図である。本発明のネットワーク品質計測システムは、ネットワーク品質計測装置としての計測管理サーバ１と、ネットワーク上に分散配置されて計測端末として機能する多数のクライアント(ユーザ端末)２とで構成される。
【００２１】
各クライアント２は、その起動を契機に計測端末として計測管理サーバ１に登録される。計測管理サーバ１は、登録されている複数の計測端末２の中から計測パスのエンドノードとなる複数のペアを選択してエンドツーエンドの通信品質を計測させる。各計測端末２は、計測管理サーバ１からの指示に従ってプローブパケットを送受することで通信品質を計測し、計測結果を前記計測管理サーバ１にアップロードする。計測管理サーバ１は、各計測端末２からアップロードされた計測結果を集計して監視対象ネットワークの通信品質を評価する。
【００２２】
図２は、本発明の一実施形態の動作を示したフローチャートであり、図３は、主に前記計測管理サーバ１の動作を模式的に表現した機能ブロック図である。
【００２３】
図２において、ステップＳ１では、計測管理サーバ１において、計測パスの組み合わせを模したビット列の初期解集団が生成される。本実施形態では、計測管理サーバ１に登録されているn台の計測端末２に関して次式(1)の行列Rが定義される。ここで、各要素eijはパスの向きを表し、eij=1は計測端末２(i)から２(j)へ向かう計測パスを意味する。
【００２４】
【数１】
【００２５】
さらに、前記行列Rの隣接行列の要素が以下のように符号化される。
【００２６】
【数２】
【００２７】
次いで、各要素eijに{１，０}をランダムに割り当てることでランダムな計測パスの組合せが作成される。ただし、全ての計測端末２に関して、各計測端末２が送出するパスの総数S、および各計測端末２が受信するパスの総数Rは、予め設定された閾値Smax，Rmax（e.g. Smax＝５，Rmax＝５）以下となるように設定され、さらに計測パスの総数Tも、予め設定された閾値Tmax(e.g. Tmax＝１０００)以下となるように設定される。ここでは、同様のビット列が K（＝３０程度）個作成されて初期の解集団（ビット列の集団）とされる。
【００２８】
ステップＳ２では、前記計測管理サーバ１において、現世代のビット列の集団に遺伝的操作を加えることで次世代のビット列候補が作成される。本実施形態では、現在のビット列の集団から、以下の遺伝操作(1)，(2)，(3)を組み合わせて次世代のビット列候補が作成される。
【００２９】
(1)交叉 (crossover)
現在のビット列から所定の交叉確率pcでMc個のペアをランダムに決定して"交叉"が適用される。本実施形態では、K個の[０，１]の乱数 rx (x=1〜K)を発生させてrx＜pcとなる x番目のビット列が親として抽出される。この結果、平均的にpc×K個(≒2×Mc個)のビット列が親として抽出される。このとき、抽出された親が奇数個の場合は、最後の一つを無視するなどして偶数個に調節される。次いで、抽出された順番で親のペアが作成され、両者の間で交叉が行われる。例えば、以下のように交叉点をランダムに２つ選び、２つの交叉点に挟まれている部分を入れ換える２点交叉が行われる。
【００３０】
【数３】
【００３１】
(2)突然変異 (mutation)
現在のビット列に対して"突然変異"を適用し、新たなビット列を作成することで局所解に陥ることが防止される。ここでは、K個のビット列の全ビット(Kｘn)を対象に確率pm(通常は小さい値、 e.g. pm ＝０．００１）に従ってビットが反転される。なお、新たなビット列（ビットの反転が行われたビット列）の数はMm個とする。
【００３２】
(3)コピー (copy)
上記以外のビット列がそのままコピーされる。
【００３３】
ステップＳ３では、前記計測管理サーバ１および計測端末２が協働して、前記次世代の各ビット列候補の適応度が評価される。本実施形態では、遺伝操作前の K個のビット列と遺伝操作により新たに作成された(2×Mc + Mm)個のビット列とに対し、以下の手順で適応度が計算される。
【００３４】
(a)計測管理サーバ１が各計測端末２に対して、要素eij＝１に対応する計測パス[２(i)→２(j)]においてtracert (traceroute)の実行を指示し、経路上のルータの情報(IPアドレスやドメイン情報)を収集する。
【００３５】
(b)計測管理サーバ１が、収集したルータの集合の中から監視対象ネットワークに属するルータ数（あるいは、リンク数）を計算する。ルータの所属ネットワーク情報は、収集したルータ端末メイン情報や、収集したIPアドレスを別途用意しておいたIPアドレス(IPアドレス空間)のリストと比較することで得られる。
【００３６】
(c)計測管理サーバ１が、前記ルータ数を適応度 fとして計算する。すなわち、図４に一例を示したように、監視対象ネットワークに属する５つのルータ（●）を通過するパスの適応度fは「５」に設定される。ただし、各計測端末２の計測パス数、および全計測パス数には上限を設けているため、各上限を超えるような選択に対しては、以下のように低い適応度 (=1)がペナルティとして与えられて次世代へ残りにくくされる。
【００３７】
【数４】
【００３８】
ステップＳ４では、前記計測管理サーバ１において、(K+2×Mc+Mm)個のビット列候補から「良い」ビット列を次世代へ選択的に残すための選択が行われる。本実施形態では、一般的に利用される、適応度の高いビット列を強制的に残す「エリート選択」、および適応度に応じた確率で次世代へ残す「ルーレット選択」の組合せが適用される。具体的には、(K+2×Mc+Mm)個のビット列から適応度の高い上位H個(H＜K)のビット列を次世代に残し、さらに残りのビット列から(K−H)個のビット列がルーレット方式で選択される。
【００３９】
ステップＳ５では、上記のステップＳ２〜Ｓ４が周期的に繰り返される。この繰り返し周期はtracerouteの実行時間を考慮して１０〜数１０秒程度に設定される。この間、計測管理サーバ１において計測端末２の新たな参加／退出が検出されると、対応するビットの追加／削除が行われ、その結果としてビット列の長さが変化する。
【００４０】
前記計測管理サーバ１は定期的に、前記ステップＳ４で残ったビット列の中で適応度が最大のビット列に対応する計測パスの組合せに基づいて、各計測端末２に指示して計測端末間でプローブパケットの送受による通信品質の計測を行う。このとき、採用されたビット列に対応する計測パス上のルータ（もしくはリンク）の集合が履歴情報として記録される。
【００４１】
本実施形態では、通信品質の計測開始後、再び前記ステップＳ２〜Ｓ４を繰り返すことで計測パス（ビット列）の最適化処理が進行する。この間、前記ステップＳ３の適応度計算において、各計測パス上に含まれる監視対象のルータ数（あるいは、リンク数）を集計する際、過去ｙ回以内に計測パスの通過履歴を有するルータやリンクは集計対象から除外する。あるいは、図５に一例を示したように、過去ｙ回以内の品質計測において選択された計測パスが通過して計測済みのルータ（図５では、◎で表記）を多く含む計測パスPxの集合（ビット列）は適応度が相対的に低くされる。あるいは、過去に選択された計測パスが通過していない未計測のルータを多く含む計測パスPyの集合（ビット列）は適応度が相対的に高くされる。これにより、より複数世代の通信品質計測を通して、監視対象ネットワークの計測カバー率を向上させることが可能になる。
【００４２】
図６は、前記計測管理サーバ１の機能ブロック図であり、ここでは、本発明の説明に不要な構成は図示が省略されている。
【００４３】
初期解集団生成部１０１は、計測パスの集合を模したビット列の初期解集団を生成する。次世代候補生成部１０２は、前記初期解集団の各ビット列に、「交叉」や「突然変異」といった遺伝的操作を加えて次世代のビット列候補を生成する。適応度評価部１０３は、各ビット列候補の適応度を評価する。
【００４４】
本発明では、各ビット列候補に対応した計測パスの集合に関して、各計測パスが通過するルータおよびリンクの少なくとも一方のうち、評価対象のネットワーク内に位置するルータおよびリンクの少なくとも一方の総数が多いビット列候補ほど、その適応度が高くされる。
【００４５】
さらに、本発明では前記適応度評価部１０３が適応度見直部を備え、ネットワーク上の各ルータおよびリンクの少なくとも一方を過去に計測パスが通過した履歴を取得し、計測パスの通過履歴を有するルータおよびリンクの少なくとも一方を新たに通過する計測パスを多く含むビット列候補の適応値が、それ以外のビット列候補の適応値よりも相対的に低くされる。同様に、計測パスの通過履歴を有しないルータおよびリンクの少なくとも一方を通過する計測パスを多く含むビット列候補の適応値が、それ以外のビット列候補の適応値よりも相対的に高くされる。
【００４６】
選択部１０４は、前記適応度の評価結果に基づいて、ビット列候補の集団の中から次世代に残すビット列を「エリート選択」や「ルーレット選択」により選択する。本発明では、前記選択された次世代のビット列の集団に対して前記次世代候補生成部１０２により遺伝的操作を繰り返すことでビット列の世代を進行させる。通信品質計測部１０５は、前記選択された次世代のビット列の集団の中で適応度が最も高いビット列に対応した計測パスの集合にエンドツーエンドの通信品質を計測させ、その計測結果を取得して評価対象ネットワークの品質を計測する。
【符号の説明】
【００４７】
１…計測管理サーバ，１０１…初期解集団生成部，１０２…次世代候補生成部，１０３…適応度評価部，１０４…選択部，１０５…通信品質計測部
【技術分野】
【０００１】
本発明は、ネットワーク品質計測装置およびその計測パス決定方法に係り、特に、遺伝的アルゴリズムを用いて計測パスを決定するネットワーク品質計測装置およびその計測パス決定方法に関する。
【背景技術】
【０００２】
IPネットワークの通信品質の監視を目的として、監視対象のネットワーク内に分散配置した計測端末間でプローブパケット（テストパケット）を送受し、パケットロス率やパケット遅延などの通信品質を計測するシステムが非特許文献１に開示されている。また、ネット対戦型ゲームの通信を利用し、大規模なIPネットワークの通信品質を計測する技術が、非特許文献２に開示されている。さらに、汎用OS(Microsoft Windows(登録商標)など)を搭載しているユーザ端末を計測端末として利用し、ユーザ端末間でプローブパケットを送受してエンドツーエンドの通信品質を計測するシステムが非特許文献３に開示されている。上記のいずれの計測システムにおいても、計測端末の配置方法や計測パスの決定方法が課題となる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】PerfSONAR: http://www.perfsonar.net/
【非特許文献２】Youngki Lee, Sharad Agarwal, Chris Butcher, and Jitu Padhye,"Measurement and Estimation of Network QoS Among Peer Xbox 360 Game Players," In Proc. of PAM 2008.
【非特許文献３】Ritesh Kumar, Jasleen Kaur, "Efficient Beacon Placement for Network Tomography." In Proc. of IMC 2004 pp.181-186.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、このような従来技術を用いた大規模IPネットワークの品質計測では、以下のような技術課題があった。
【０００５】
非特許文献２のように、計測端末としてネット対戦型ゲーム機を利用してIPネットワークの品質を計測するシステムでは、ゲームの対戦相手との通信と同時にネットワークの通信品質が計測される。しかしながら、通常のネット対戦型ゲームでは多数の候補対戦相手の中から通信品質が高い(例えば、パケット遅延が小さい)通信相手が対戦相手として選択されるため、計測データが高品質なネットワーク区間を対象としたものに偏る傾向がある。このため、ネットワーク全体を網羅的に監視する目的には使用できない。
【０００６】
非特許文献３では、監視対象ネットワークに計測端末を設置するシステム(非特許文献１のシステム)を対象に、ネットワーク内の全てのリンクを少なくとも１本の計測パスが通過する計測端末の配置方法および計測パスの決定方法が提案されている。しかしながら、本手法はネットワーク管理者が計測端末を設置することを想定しているため、ネットワークトポロジーが既知であることが前提であり、多数のユーザ端末を任意に計測端末として利用するシステムには適用できない。
【０００７】
本発明の目的は、上記した従来技術の課題を解決し、遺伝的アルゴリズムを用いることで、少数の計測パスで効率的に対象ネットワークの通信品質を監視できるネットワーク品質計測装置およびその計測パス決定方法を提供することにある。
【課題を解決するための手段】
【０００８】
上記の目的を達成するために、本発明は、ネットワーク上に分散配置された計測端末から計測パスのエンドノードとなる複数のペアを選択してエンドツーエンドの通信品質を計測させ、計測結果を収集してネットワーク品質を計測するネットワーク品質計測装置およびその計測パス決定方法において、以下のような手段を講じた点に特徴がある。
【０００９】
(1)本発明のネットワーク品質計測装置は、計測パスの集合を模したビット列の初期解集団を生成する初期解集団生成手段と、初期解集団の各ビット列に遺伝的操作を加えて次世代のビット列候補を生成する次世代候補生成手段と、各ビット列候補の適応度を評価する適応度評価手段と、適応度の評価結果に基づいて、前記ビット列候補の中から次世代に残すビット列を選択する選択手段とを具備し、選択された次世代のビット列集団に前記遺伝的操作を繰り返すことでビット列の世代を進行させ、選択された次世代のビット列集団の中で適応度が最も高いビット列に対応した計測パスの集合にエンドツーエンドの通信品質を計測させる手段を具備した。
【００１０】
(2)本発明の計測パス決定方法は、計測パスの集合を模したビット列の初期解集団を生成する手順と、初期解集団の各ビット列に遺伝的操作を加えて次世代のビット列候補を生成する手順と、各ビット列候補の適応度を評価する手順と、適応度の評価結果に基づいて、前記ビット列候補の中から次世代に残すビット列を選択する手順と、選択された次世代のビット列の集団に前記遺伝的操作を繰り返すことでビット列の世代を進行させる手順と、選択された次世代のビット列の集団の中で適応度が最も高いビット列を計測パスの集合とする手順とを含むことを特徴とする。
【００１１】
(3)各ビット列候補に対応した計測パスの集合に関して、各計測パスが通過するルータやリンクのうち、評価対象のネットワーク内に位置するルータやリンクの総数が多いビット列候補ほど、その適応度を高くすることを特徴とする。
【００１２】
(4)計測パスの通過履歴を有するルータやリンクを多く通過する計測パスを含むビット列候補の適応値を、当該ルータやリンクの数に応じて相対的に低くすることを特徴とする。
【００１３】
(5)計測パスの通過履歴を有しないルータやリンクを多く通過する計測パスを含むビット列候補の適応値を、当該ルータやリンクの数に応じて相対的に高くすることを特徴とする。
【発明の効果】
【００１４】
本発明によれば、以下のような効果が達成される。
【００１５】
(1)本発明のネットワーク品質計測装置によれば、遺伝的アルゴリズムにより最適化された少数の計測パスを用いてネットワーク品質を効率的に計測できるようになる。
【００１６】
(2)本発明の計測パス決定方法によれば、遺伝的アルゴリズムにより最適な計測パスを選択できるので、ネットワーク品質を少数の計測パスで効率的に計測できるようになる。
【００１７】
(3)計測パスの集合であるビット列に関して、次世代に残すビット列を選択する際の指標となる適応度として、評価対象のネットワーク内に位置するルータやリンクを通過する計測パスを多く含むビット列の適応度が高く設定されるので、ネットワーク品質を小数で効率的に計測できる計測パスの集合を選択できるようになる。
【００１８】
(4)計測パスの通過履歴を有するルータやリンクを通過する計測パスを多く含むビット列候補の適応値を低くしたり、計測パスの通過履歴を有しないルータやリンクを通過する計測パスを多く含むビット列候補の適応値を低くしたりするので、監視対象ネットワークの計測カバー率を向上させることが可能になる。
【図面の簡単な説明】
【００１９】
【図１】本発明が監視対象とするネットワークを含むネットワークの構成を示した図である。
【図２】本発明の一実施形態の動作を示したフローチャートである。
【図３】本発明の一実施形態の動作を模式的に表現した機能ブロック図である。
【図４】ビット列候補の適応度fを求める方法を示した図である。
【図５】適応度fの見直し方法を説明するための図である。
【図６】計測管理サーバの機能ブロック図である。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明が監視対象とするネットワークを含む広域ネットワークの構成を示したブロック図である。本発明のネットワーク品質計測システムは、ネットワーク品質計測装置としての計測管理サーバ１と、ネットワーク上に分散配置されて計測端末として機能する多数のクライアント(ユーザ端末)２とで構成される。
【００２１】
各クライアント２は、その起動を契機に計測端末として計測管理サーバ１に登録される。計測管理サーバ１は、登録されている複数の計測端末２の中から計測パスのエンドノードとなる複数のペアを選択してエンドツーエンドの通信品質を計測させる。各計測端末２は、計測管理サーバ１からの指示に従ってプローブパケットを送受することで通信品質を計測し、計測結果を前記計測管理サーバ１にアップロードする。計測管理サーバ１は、各計測端末２からアップロードされた計測結果を集計して監視対象ネットワークの通信品質を評価する。
【００２２】
図２は、本発明の一実施形態の動作を示したフローチャートであり、図３は、主に前記計測管理サーバ１の動作を模式的に表現した機能ブロック図である。
【００２３】
図２において、ステップＳ１では、計測管理サーバ１において、計測パスの組み合わせを模したビット列の初期解集団が生成される。本実施形態では、計測管理サーバ１に登録されているn台の計測端末２に関して次式(1)の行列Rが定義される。ここで、各要素eijはパスの向きを表し、eij=1は計測端末２(i)から２(j)へ向かう計測パスを意味する。
【００２４】
【数１】
【００２５】
さらに、前記行列Rの隣接行列の要素が以下のように符号化される。
【００２６】
【数２】
【００２７】
次いで、各要素eijに{１，０}をランダムに割り当てることでランダムな計測パスの組合せが作成される。ただし、全ての計測端末２に関して、各計測端末２が送出するパスの総数S、および各計測端末２が受信するパスの総数Rは、予め設定された閾値Smax，Rmax（e.g. Smax＝５，Rmax＝５）以下となるように設定され、さらに計測パスの総数Tも、予め設定された閾値Tmax(e.g. Tmax＝１０００)以下となるように設定される。ここでは、同様のビット列が K（＝３０程度）個作成されて初期の解集団（ビット列の集団）とされる。
【００２８】
ステップＳ２では、前記計測管理サーバ１において、現世代のビット列の集団に遺伝的操作を加えることで次世代のビット列候補が作成される。本実施形態では、現在のビット列の集団から、以下の遺伝操作(1)，(2)，(3)を組み合わせて次世代のビット列候補が作成される。
【００２９】
(1)交叉 (crossover)
現在のビット列から所定の交叉確率pcでMc個のペアをランダムに決定して"交叉"が適用される。本実施形態では、K個の[０，１]の乱数 rx (x=1〜K)を発生させてrx＜pcとなる x番目のビット列が親として抽出される。この結果、平均的にpc×K個(≒2×Mc個)のビット列が親として抽出される。このとき、抽出された親が奇数個の場合は、最後の一つを無視するなどして偶数個に調節される。次いで、抽出された順番で親のペアが作成され、両者の間で交叉が行われる。例えば、以下のように交叉点をランダムに２つ選び、２つの交叉点に挟まれている部分を入れ換える２点交叉が行われる。
【００３０】
【数３】
【００３１】
(2)突然変異 (mutation)
現在のビット列に対して"突然変異"を適用し、新たなビット列を作成することで局所解に陥ることが防止される。ここでは、K個のビット列の全ビット(Kｘn)を対象に確率pm(通常は小さい値、 e.g. pm ＝０．００１）に従ってビットが反転される。なお、新たなビット列（ビットの反転が行われたビット列）の数はMm個とする。
【００３２】
(3)コピー (copy)
上記以外のビット列がそのままコピーされる。
【００３３】
ステップＳ３では、前記計測管理サーバ１および計測端末２が協働して、前記次世代の各ビット列候補の適応度が評価される。本実施形態では、遺伝操作前の K個のビット列と遺伝操作により新たに作成された(2×Mc + Mm)個のビット列とに対し、以下の手順で適応度が計算される。
【００３４】
(a)計測管理サーバ１が各計測端末２に対して、要素eij＝１に対応する計測パス[２(i)→２(j)]においてtracert (traceroute)の実行を指示し、経路上のルータの情報(IPアドレスやドメイン情報)を収集する。
【００３５】
(b)計測管理サーバ１が、収集したルータの集合の中から監視対象ネットワークに属するルータ数（あるいは、リンク数）を計算する。ルータの所属ネットワーク情報は、収集したルータ端末メイン情報や、収集したIPアドレスを別途用意しておいたIPアドレス(IPアドレス空間)のリストと比較することで得られる。
【００３６】
(c)計測管理サーバ１が、前記ルータ数を適応度 fとして計算する。すなわち、図４に一例を示したように、監視対象ネットワークに属する５つのルータ（●）を通過するパスの適応度fは「５」に設定される。ただし、各計測端末２の計測パス数、および全計測パス数には上限を設けているため、各上限を超えるような選択に対しては、以下のように低い適応度 (=1)がペナルティとして与えられて次世代へ残りにくくされる。
【００３７】
【数４】
【００３８】
ステップＳ４では、前記計測管理サーバ１において、(K+2×Mc+Mm)個のビット列候補から「良い」ビット列を次世代へ選択的に残すための選択が行われる。本実施形態では、一般的に利用される、適応度の高いビット列を強制的に残す「エリート選択」、および適応度に応じた確率で次世代へ残す「ルーレット選択」の組合せが適用される。具体的には、(K+2×Mc+Mm)個のビット列から適応度の高い上位H個(H＜K)のビット列を次世代に残し、さらに残りのビット列から(K−H)個のビット列がルーレット方式で選択される。
【００３９】
ステップＳ５では、上記のステップＳ２〜Ｓ４が周期的に繰り返される。この繰り返し周期はtracerouteの実行時間を考慮して１０〜数１０秒程度に設定される。この間、計測管理サーバ１において計測端末２の新たな参加／退出が検出されると、対応するビットの追加／削除が行われ、その結果としてビット列の長さが変化する。
【００４０】
前記計測管理サーバ１は定期的に、前記ステップＳ４で残ったビット列の中で適応度が最大のビット列に対応する計測パスの組合せに基づいて、各計測端末２に指示して計測端末間でプローブパケットの送受による通信品質の計測を行う。このとき、採用されたビット列に対応する計測パス上のルータ（もしくはリンク）の集合が履歴情報として記録される。
【００４１】
本実施形態では、通信品質の計測開始後、再び前記ステップＳ２〜Ｓ４を繰り返すことで計測パス（ビット列）の最適化処理が進行する。この間、前記ステップＳ３の適応度計算において、各計測パス上に含まれる監視対象のルータ数（あるいは、リンク数）を集計する際、過去ｙ回以内に計測パスの通過履歴を有するルータやリンクは集計対象から除外する。あるいは、図５に一例を示したように、過去ｙ回以内の品質計測において選択された計測パスが通過して計測済みのルータ（図５では、◎で表記）を多く含む計測パスPxの集合（ビット列）は適応度が相対的に低くされる。あるいは、過去に選択された計測パスが通過していない未計測のルータを多く含む計測パスPyの集合（ビット列）は適応度が相対的に高くされる。これにより、より複数世代の通信品質計測を通して、監視対象ネットワークの計測カバー率を向上させることが可能になる。
【００４２】
図６は、前記計測管理サーバ１の機能ブロック図であり、ここでは、本発明の説明に不要な構成は図示が省略されている。
【００４３】
初期解集団生成部１０１は、計測パスの集合を模したビット列の初期解集団を生成する。次世代候補生成部１０２は、前記初期解集団の各ビット列に、「交叉」や「突然変異」といった遺伝的操作を加えて次世代のビット列候補を生成する。適応度評価部１０３は、各ビット列候補の適応度を評価する。
【００４４】
本発明では、各ビット列候補に対応した計測パスの集合に関して、各計測パスが通過するルータおよびリンクの少なくとも一方のうち、評価対象のネットワーク内に位置するルータおよびリンクの少なくとも一方の総数が多いビット列候補ほど、その適応度が高くされる。
【００４５】
さらに、本発明では前記適応度評価部１０３が適応度見直部を備え、ネットワーク上の各ルータおよびリンクの少なくとも一方を過去に計測パスが通過した履歴を取得し、計測パスの通過履歴を有するルータおよびリンクの少なくとも一方を新たに通過する計測パスを多く含むビット列候補の適応値が、それ以外のビット列候補の適応値よりも相対的に低くされる。同様に、計測パスの通過履歴を有しないルータおよびリンクの少なくとも一方を通過する計測パスを多く含むビット列候補の適応値が、それ以外のビット列候補の適応値よりも相対的に高くされる。
【００４６】
選択部１０４は、前記適応度の評価結果に基づいて、ビット列候補の集団の中から次世代に残すビット列を「エリート選択」や「ルーレット選択」により選択する。本発明では、前記選択された次世代のビット列の集団に対して前記次世代候補生成部１０２により遺伝的操作を繰り返すことでビット列の世代を進行させる。通信品質計測部１０５は、前記選択された次世代のビット列の集団の中で適応度が最も高いビット列に対応した計測パスの集合にエンドツーエンドの通信品質を計測させ、その計測結果を取得して評価対象ネットワークの品質を計測する。
【符号の説明】
【００４７】
１…計測管理サーバ，１０１…初期解集団生成部，１０２…次世代候補生成部，１０３…適応度評価部，１０４…選択部，１０５…通信品質計測部
【特許請求の範囲】
【請求項１】
ネットワーク上に分散配置された計測端末から計測パスのエンドノードとなる複数のペアを選択してエンドツーエンドの通信品質を計測させ、計測結果を収集してネットワーク品質を計測するネットワーク品質計測装置において、
計測パスの集合を模したビット列の初期解集団を生成する初期解集団生成手段と、
前記初期解集団の各ビット列に遺伝的操作を加えて次世代のビット列候補を生成する次世代候補生成手段と、
前記各ビット列候補の適応度を評価する適応度評価手段と、
前記適応度の評価結果に基づいて、前記ビット列候補の中から次世代に残すビット列を選択する選択手段とを具備し、
前記選択された次世代のビット列の集団に前記遺伝的操作を繰り返すことでビット列の世代を進行させ、
前記選択された次世代のビット列の集団の中で適応度が最も高いビット列に対応した計測パスの集合にエンドツーエンドの通信品質を計測させる手段を具備したことを特徴とするネットワーク品質計測装置。
【請求項２】
前記適応度評価手段は、各ビット列候補に対応した計測パスの集合に関して、各計測パスが通過するルータおよびリンクの少なくとも一方のうち、評価対象のネットワーク内に位置するルータおよびリンクの少なくとも一方の総数が多いビット列候補ほど、その適応度を高くすることを特徴とする請求項１に記載のネットワーク品質計測装置。
【請求項３】
前記適応度評価手段は、ネットワーク上の各ルータおよびリンクの少なくとも一方を過去に計測パスが通過した履歴を取得する手段を具備し、
前記計測パスの通過履歴を有するルータおよびリンクの少なくとも一方を多く通過する計測パスを含むビット列候補の適応値を、当該ルータおよびリンクの少なくとも一方の数に相対的に低くすることを特徴とする請求項２に記載のネットワーク品質計測装置。
【請求項４】
前記適応度評価手段は、ネットワーク上の各ルータおよびリンクの少なくとも一方を過去に計測パスが通過した履歴を取得する手段を具備し、
前記計測パスの通過履歴を有しないルータおよびリンクの少なくとも一方を多く通過する計測パスを含むビット列候補の適応値を、当該ルータおよびリンクの少なくとも一方の数に応じて相対的に高くすることを特徴とする請求項２または３に記載のネットワーク品質計測装置。
【請求項５】
ネットワーク上に分散配置された計測端末から計測パスのエンドノードとなる複数のペアを選択する計測パス決定方法において、
計測パスの集合を模したビット列の初期解集団を生成する手順と、
前記初期解集団の各ビット列に遺伝的操作を加えて次世代のビット列候補を生成する手順と、
前記各ビット列候補の適応度を評価する手順と、
前記適応度の評価結果に基づいて、前記ビット列候補の中から次世代に残すビット列を選択する手順と、
前記選択された次世代のビット列の集団に前記遺伝的操作を繰り返すことでビット列の世代を進行させる手順と、
前記選択された次世代のビット列の集団の中で適応度が最も高いビット列を計測パスの集合とする手順とを含むことを特徴とするネットワーク品質計測装置の計測パス決定方法。
【請求項１】
ネットワーク上に分散配置された計測端末から計測パスのエンドノードとなる複数のペアを選択してエンドツーエンドの通信品質を計測させ、計測結果を収集してネットワーク品質を計測するネットワーク品質計測装置において、
計測パスの集合を模したビット列の初期解集団を生成する初期解集団生成手段と、
前記初期解集団の各ビット列に遺伝的操作を加えて次世代のビット列候補を生成する次世代候補生成手段と、
前記各ビット列候補の適応度を評価する適応度評価手段と、
前記適応度の評価結果に基づいて、前記ビット列候補の中から次世代に残すビット列を選択する選択手段とを具備し、
前記選択された次世代のビット列の集団に前記遺伝的操作を繰り返すことでビット列の世代を進行させ、
前記選択された次世代のビット列の集団の中で適応度が最も高いビット列に対応した計測パスの集合にエンドツーエンドの通信品質を計測させる手段を具備したことを特徴とするネットワーク品質計測装置。
【請求項２】
前記適応度評価手段は、各ビット列候補に対応した計測パスの集合に関して、各計測パスが通過するルータおよびリンクの少なくとも一方のうち、評価対象のネットワーク内に位置するルータおよびリンクの少なくとも一方の総数が多いビット列候補ほど、その適応度を高くすることを特徴とする請求項１に記載のネットワーク品質計測装置。
【請求項３】
前記適応度評価手段は、ネットワーク上の各ルータおよびリンクの少なくとも一方を過去に計測パスが通過した履歴を取得する手段を具備し、
前記計測パスの通過履歴を有するルータおよびリンクの少なくとも一方を多く通過する計測パスを含むビット列候補の適応値を、当該ルータおよびリンクの少なくとも一方の数に相対的に低くすることを特徴とする請求項２に記載のネットワーク品質計測装置。
【請求項４】
前記適応度評価手段は、ネットワーク上の各ルータおよびリンクの少なくとも一方を過去に計測パスが通過した履歴を取得する手段を具備し、
前記計測パスの通過履歴を有しないルータおよびリンクの少なくとも一方を多く通過する計測パスを含むビット列候補の適応値を、当該ルータおよびリンクの少なくとも一方の数に応じて相対的に高くすることを特徴とする請求項２または３に記載のネットワーク品質計測装置。
【請求項５】
ネットワーク上に分散配置された計測端末から計測パスのエンドノードとなる複数のペアを選択する計測パス決定方法において、
計測パスの集合を模したビット列の初期解集団を生成する手順と、
前記初期解集団の各ビット列に遺伝的操作を加えて次世代のビット列候補を生成する手順と、
前記各ビット列候補の適応度を評価する手順と、
前記適応度の評価結果に基づいて、前記ビット列候補の中から次世代に残すビット列を選択する手順と、
前記選択された次世代のビット列の集団に前記遺伝的操作を繰り返すことでビット列の世代を進行させる手順と、
前記選択された次世代のビット列の集団の中で適応度が最も高いビット列を計測パスの集合とする手順とを含むことを特徴とするネットワーク品質計測装置の計測パス決定方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１１−２１１３５９（Ｐ２０１１−２１１３５９Ａ）
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【出願番号】特願２０１０−７５２０６（Ｐ２０１０−７５２０６）
【出願日】平成２２年３月２９日（２０１０．３．２９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【出願日】平成２２年３月２９日（２０１０．３．２９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]