JP2007243489A - 経路変動判定装置及びコンピュータプログラム - Google Patents

Abstract

【課題】インターネット経路制御における不安定経路を特定することにより、その経路の生成元への連絡と対処を迅速に行い、インターネット経路制御の安定化に貢献する。
【解決手段】経路変動判定装置３０は、複数のＢＧＰルータ４０から受信したＢＧＰ経路更新メッセージから、ルートフラップ発生時の特徴的なメッセージパターンを抽出することにより、ルートフラップ発生の有無や発生場所を特定する。またルートフラップ発生時のＢＧＰ経路更新メッセージの受信パターンの特性を把握する。
【選択図】図３

Description

本発明は、経路変動判定装置及びコンピュータプログラムに関する。

インターネットは、図１４に示されるように、自律システム（ＡＳ：Autonomous System）と呼ばれる独立した管理単位（ＡＳ１００〜ＡＳ５００）が結合して構成されたネットワークである。ＡＳ間では、ＢＧＰ（Border Gateway Protocol）と呼ばれる経路制御プロトコルを利用して経路情報の交換を行うことで、ネットワークの接続性を維持している。ＢＧＰでは、経路情報が変更された場合のみＢＧＰ経路更新メッセージにより隣接するＢＧＰルータに変更された経路情報を通知する。また、ＢＧＰでは、ある宛先（プレフィックス）へ到達可能となった場合、または経路の属性（ＡＳパス等）が変更された場合、Announceメッセージとして通知され、プレフィックスへの到達性がなくなった場合はWithdrawメッセージとして通知される。なお、経路情報の変更は、ＢＧＰルータの故障等により発生する不安定な経路情報だけでなく、設定変更等で発生する正常な経路変動の通知も含まれる。

ところで、不安定な経路情報のうち、頻繁に経路のAnnounce、Withdrawを繰り返す経路変動（ルートフラップ）と呼ばれる現象がある。ルートフラップが発生すると、多くのＢＧＰ経路更新メッセージが各ＢＧＰルータに伝搬されるため、ＢＧＰルータの負荷増大や、インターネット全体の経路制御の不安定を誘発する可能性がある。従ってルートフラップを検知することは、インターネット経路制御の安定性を維持するために重要となる。

一方、ルートフラップによるＢＧＰ経路更新メッセージ増加を抑える手法として、ルートフラップダンピングと呼ばれる手法がある（例えば、非特許文献１参照）。ルートフラップダンピングは、ＡＳ内にそれぞれ設けられるＢＧＰルータに実装され、各ＢＧＰ接続先からＢＧＰ経路更新メッセージで受信するプレフィックスの経路毎に、それが安定しているか否かを判定する。ルートフラップダンピングでは、プレフィックスはその経路が変動するたびにペナルティが与えられる。

図１５は、ルートフラップダンピングにおけるペナルティの変化をグラフ表示したものである。図１５において、ペナルティがあらかじめ決められた抑制値に達したときに経路は抑制され、他のＢＧＰルータに広報されなくなる。また、ペナルティは指数的に減少し、その値が再利用値より小さくなったとき、経路は再び広報される。また、ルートフラップダンピングにより、頻繁に経路変動が発生するプレフィックスの広報が抑制され、その結果、ＢＧＰ経路更新メッセージも減少する。
ＲＦＣ２４３９"ＢＧＰ Ｒｏｕｔｅ Ｆｌａｐ Ｄａｍｐｉｎｇ"

上記したルートフラップダンピングは、一つのＢＧＰ接続先から受信するＢＧＰ経路更新メッセージの受信頻度のみで、その経路がフラップしているか否かを判定する。しかしながら、実際には正常な経路変動であっても、ＢＧＰの接続トポロジーや、ＢＧＰルータに設定された経路ポリシー、あるいは、ＢＧＰ経路更新メッセージの受信や送信タイミング等により、伝搬されるＢＧＰ経路更新メッセージの数が増える場合がある。その結果、あるＢＧＰルータでは、あるプレフィックスに関して複数のＢＧＰ経路更新メッセージを受信し、その結果、その経路がフラップしていると判断され、経路が抑制されてしまう場合がある。

その現象に関し、図１６を用いて説明する。図１６は、ＢＧＰ経路更新メッセージがＡＳ間を伝播するにつれ、ＢＧＰ経路変動メッセージ数が増加する様子を示した図である。なお、図１６中の数字はＡＳ番号を、「Ｗ」はWithdrawを、｛｝内の数字列はAnnounceにおける経路のＡＳパスをそれぞれ示している。図１６において、例えば、ＡＳ１においてＢＧＰルータの再起動を実行した場合、そのＢＧＰルータから広報される経路は、一度、Withdrawされた後、ルータの起動後、再びAnnounceされる。この一度の経路変動は、ＢＧＰ経路更新メッセージによって隣接するＡＳ２、ＡＳ３、ＡＳ４に広報される。ＡＳ５では、ＡＳ２とＡＳ３からＢＧＰ経路更新メッセージを受信するが、ＡＳ５の経路ポリシーによりＡＳ３からの経路を優先すると仮定する。ここでＡＳ５がWithdrawを受信後、先にＡＳ２からAnnounceを受信し、ＡＳ３からはAnnounceを受信していないとすると、ＡＳ５は隣接のＡＳ９に対してＡＳ２からの経路を広報する。その後ＡＳ５がＡＳ３からAnnounceを受信したとすると、ＡＳ５はＡＳ９に対してＡＳ３からの経路を広報する。その結果、ＡＳ９ではＡＳ１での一度の経路変動により、３つのＢＧＰ経路変動メッセージを受信することになる。同様に、ＡＳ１１はＡＳ１０からＢＧＰ経路変動メッセージを受信するが、ＡＳ１０でのＢＧＰ経路変動メッセージの受信や送信タイミングにより、ＡＳ１１は４つのＢＧＰ経路変動メッセージを受信する。

このように、正常な一度の経路変動であっても、あるＡＳでは複数のＢＧＰ経路更新メッセージを受信する場合があり、そこでルートフラップダンピングが実施されているとすると、その経路がフラップしていると判定され、不必要に経路が抑制されてしまう。

本発明は、このような事情を考慮してなされたもので、その目的は、インターネット経路制御における不安定経路を特定することにより、その経路の生成元への連絡と対処を迅速に行い、インターネット経路制御の安定化に貢献することのできる経路変動判定装置を提供することにある。

また、本発明の他の目的は、本発明の経路変動判定装置をコンピュータを利用して実現するためのコンピュータプログラムを提供することにある。

上記の課題を解決するために、本発明に係る経路変動判定装置は、独立した管理単位であるＡＳ（Autonomous System）が結合して構成されるネットワークシステムにおいて、ある特定のプレフィックスに関してルートフラップが発生しているか否かを判定する経路変動判定装置であって、観測点の前記ＡＳに隣接する複数のＢＧＰ(Border Gateway Protocol)ルータから、ＢＧＰ経路更新メッセージを取得するメッセージ取得部と、前記取得した複数のＢＧＰ経路更新メッセージからルートフラップ発生時の特徴的なメッセージパターンを抽出し、前記ある特定のプレフィックスに関してルートフラップが発生しているか否かを判定する経路変動判定部とを備えたことを特徴とする。

本発明に係る経路変動判定装置においては、前記経路変動判定部は、前記ある特定のプレフィックスにルートフラップが発生していると判定したとき、前記ルートフラップの発生場所を特定することを特徴とする。

本発明に係る経路変動判定装置においては、前記メッセージ取得部は、前記複数のＢＧＰルータと接続を行い、それぞれのＢＧＰルータからＢＧＰ経路更新メッセージを受信することを特徴とする。

本発明に係る経路変動判定装置においては、前記メッセージ取得部は、あらかじめ前記複数のＢＧＰルータから取得されファイルに格納されているＢＧＰ経路更新メッセージを、取得することを特徴とする。

本発明に係る経路変動判定装置においては、前記取得したＢＧＰ経路更新メッセージをプレフィックス毎に分類し、少なくとも、時間と経路の属性に関する情報を抽出して前記経路変動判定部へ出力するか、若しくは前記プレフィックス毎に少なくとも時間と経路の属性に関する情報を持つ一つのＢＧＰ経路更新メッセージファイルを生成し保存するメッセージ処理部を更に備えたことを特徴とする。

本発明に係る経路変動判定装置においては、前記経路変動判定部は、前記ＢＧＰ経路更新メッセージを新たに取得したとき、前に取得したＢＧＰ経路更新メッセージとの間隔により、該新たに取得したＢＧＰ経路更新メッセージが、前記複数のＢＧＰルータから受信したＢＧＰ経路更新メッセージを時系列に並べた場合の時間的に所定の条件を満たすメッセージ群をグルーピングしたイベントに属するか否かを判定し、前記イベントに属さないと判定したとき、前記イベントの最後に取得したＢＧＰ経路更新メッセージとの間隔が所定の値以下の場合に関連イベントと判定し、前記所定の値を越えた場合、更に、ある接続先から受信したＢＧＰ経路更新メッセージにおいて、前記イベント内に同じ属性を持つ経路が存在するか否かを判定し、存在しないときに、前記イベントはルートフラップよるイベントでないと判定することを特徴とする。

本発明に係る経路変動判定装置においては、前記経路変動判定部は、前記イベント内に同じ属性を持つ経路が存在する場合、全ての接続先ＢＧＰルータから最後にWithdrawを受信するイベントは、そのプレフィックスの生成元でのルートフラップによるイベントであると判定することを特徴とする。

本発明に係る経路変動判定装置においては、前記経路変動判定部は、前記イベント内に同じ属性を持つ経路が存在する場合、少なくとも一つの接続先ＢＧＰルータから最後にWithdrawを受信するイベントは、経路途中でのルートフラップによるイベントであると判定することを特徴とする。

本発明に係る経路変動判定装置においては、前記経路変動判定部は、ルートフラップによるイベントであると判定された前記イベントについて、前記関連するＢＧＰ経路更新メッセージからルートフラップ発生時の特徴的なメッセージパターンを抽出し、その結果をログとして保存することを特徴とする。

本発明に係るコンピュータプログラムは、独立した管理単位であるＡＳ（Autonomous System）が結合して構成されるネットワークシステムにおいて、ある特定のプレフィックスに関してルートフラップが発生しているか否かを判定する経路変動判定処理を行うためのコンピュータプログラムであって、観測点の前記ＡＳに隣接する複数のＢＧＰ(Border Gateway Protocol)ルータから、ＢＧＰ経路更新メッセージを取得する機能と、前記取得した複数のＢＧＰ経路更新メッセージからルートフラップ発生時の特徴的なメッセージパターンを抽出し、前記ある特定のプレフィックスに関してルートフラップが発生しているか否かを判定する機能とをコンピュータに実現させることを特徴とする。
これにより、前述の経路変動判定装置がコンピュータを利用して実現できるようになる。

本発明によれば、複数のＢＧＰルータから受信したＢＧＰ経路更新メッセージから、ルートフラップ発生時の特徴的なメッセージパターンを抽出することにより、ルートフラップ発生の有無や発生場所を特定することができる。またルートフラップ発生時のＢＧＰ経路更新メッセージの受信パターンの特性を把握することができる。したがって、インターネット経路制御における不安定経路を特定することで、その経路の生成元への連絡と対処を迅速に行うことが可能となり、インターネット経路制御の安定化維持に貢献することができる。

以下、図面を参照し、本発明の一実施形態について説明する。

初めに、ルートフラップが発生した場合の、ＢＧＰ経路更新メッセージの伝達モデルについて、図１、図２を参照しながら説明する。
あるプレフィックスＰ０に関するルートフラップは、プレフィックスＰ０の生成元で発生する場合と、経路途中で発生する場合が考えられる。前者の原因としてＢＧＰルータのインタフェース故障等があり、後者の原因としては、ＲＦＣ３３４５で説明されているRoute Oscillationと呼ばれる現象による発生等が考えられる。前者の例を図１に、後者の例を図２に示す。

図１に示されるように、ルートフラップがプレフィックスの生成元で発生した場合、観測点となる、あるＡＳでは、プレフィックスＰ０に関してAnnounce（Ａ）とWithdraw（Ｗ）を繰り返し受信する。ここで、ルートフラップダンピングを実施するＢＧＰルータが経路上に存在すると仮定し、ルートフラップダンピング実施ルータでプレフィックスＰ０のペナルティが抑制値に達すると、プレフィックスＰ０関してWithdrawが送信された後、一定期間プレフィックスＰ０に関するＢＧＰ経路更新メッセージは抑制される。その結果、観測点では、経路が異なる全てのＢＧＰ接続先からプレフィックスＰ０に関してWithdrawを受信した後、一定期間プレフィックスＰ０に関するＢＧＰ経路更新メッセージは受信されなくなる。

一方、図２に示されるように、ルートフラップが経路途中で発生した場合、ルートフラップダンピング実施ルータが経路上に存在するとしても、観測点では、プレフィックスＰ０に関してルートフラップ発生地点を通らない安定した経路（ＡＳ５→ＡＳ４）をAnnounce（Ａ）メッセージで受信する可能性がある。

図３は、本発明の一実施形態に係る経路変動判定装置３０の構成を示すブロック図である。
図３において、経路変動判定装置３０は、メッセージ取得部Ａ（３１）と、メッセージ取得部Ｂ（３２）と、メッセージ処理部３３と、ファイル格納部３４と、経路変動判定部３５と、ファイル出力部３６とを備える。

メッセージ取得部Ａ（３１）は、隣接するＢＧＰルータ４０（１〜ｎ）と接続を行い、それぞれのＢＧＰルータ４０（１〜ｎ）からＢＧＰ経路更新メッセージを受信し、受信したＢＧＰ経路更新メッセージを標準フォーマットに変換してメッセージ処理部３３へ出力する。

メッセージ取得部Ｂ（３２）は、ＢＧＰ経路更新メッセージダンプファイル４１から標準フォーマットに変換済みのＢＧＰ経路更新メッセージを取得してメッセージ処理部３３へ出力する。ＢＧＰ経路更新メッセージダンプファイル４１には、あらかじめ、ＢＧＰルータ４０（１〜ｎ）から取得されたＢＧＰ経路更新メッセージが標準フォーマットに変換されて格納されている。

メッセージ処理部３３は、メッセージ取得部Ａ（３１）、メッセージ取得部Ｂ（３２）によって取得されたメッセージをプレフィックス毎に分類し、少なくとも、時間と経路の属性情報を抽出して経路判定部３５へ出力するか、若しくは、プレフィックス毎に、少なくとも、時間と経路の属性に関する情報を持つ一つのＢＧＰ経路更新メッセージファイルを生成してファイル格納部３４へ保存する。

経路変動判定部３５は、後述するように、取得した複数のＢＧＰ経路更新メッセージからルートフラップ発生時の特徴的なメッセージパターンを抽出し、ある特定のプレフィックスに関してルートフラップが発生しているか否かを判定し、ある特定のプレフィックスにルートフラップが発生していると判定したとき、ルートフラップの発生場所を推定演算してファイル出力部３６へ出力する機能を有する。

また、経路変動判定部３５は、関連するＢＧＰ経路更新メッセージからルートフラップ発生時の特徴的なメッセージパターンを抽出し、その結果を、ファイル出力部３６により、ＢＧＰ経路変動ログ４２として保存する機能もあわせ持つ。

以下、図３に示す本実施形態に係る経路変動判定装置３０の動作について説明する。
ここでは、以下に説明するいずれかの方法に従い、ＢＧＰ経路更新メッセージを収集することができるものとする。一つは、図１、図２に示す観測点において、複数のＢＧＰルータ４０（１〜ｎ）とＢＧＰ接続を行い、各ＢＧＰルータ４０（１〜ｎ）からＢＧＰ経路更新メッセージを受信する方法である。この場合、メッセージ取得部Ａ（３１）において、受信したＢＧＰ経路更新メッセージをＭＲＴフォーマットと呼ばれる標準フォーマットに変換して保存する。他の一つは、あらかじめ収集しておいた、ＢＧＰ経路更新メッセージのダンプファイル４１を入力する方法である。ＢＧＰ経路更新メッセージダンプファイル４１には、複数のＢＧＰルータ４０（１〜ｎ）ルータから受信したＢＧＰ経路更新メッセージがＭＲＴフォーマットに変換され格納されている。

図４に、ＭＲＴフォーマットで表記されたＢＧＰ経路更新メッセージの一例が示されている。図４に示されるように、ＭＲＴフォーマットで表されたメッセージには、メッセージの受信時刻（TIME）、メッセージの送信元（FROM）、ＡＳパス（ASPATH）、ＭＥＤ値（MULTI_EXIT_DISC）、コミュニティ値（COMMUNITY）、広報されるプレフィックス（ANNOUNCE）、取り消されるプレフィックス（WITHDRAW）等の情報が含まれている。

上記の方法で収集したＢＧＰ経路更新メッセージは、メッセージ処理部３３においてプレフィックス毎に分類され、必要な情報が抽出される。その後、実時間で経路変動判定を実行する場合、メッセージ処理部３３は、処理後のメッセージを経路変動判定部３５に出力し、一方、非実時間で経路変動判定を実行する場合は、プレフィックス毎に一つのＢＧＰ経路更新メッセージファイルとして編集し、ファイル格納部３４にメッセージファイルとして保存する。このメッセージファイルの一例が図５に示されている。

図５において、ファイルを構成する各エントリが一つのＢＧＰ経路更新メッセージを表しており、情報として、メッセージの受信日時、メッセージの種別（AnnounceまたはWithdraw）、接続先、ＭＥＤ値（ここではmed）、ＡＳパス（ここではaspath）、コミュニティ値(ここではcommunity)が含まれる。なお、メッセージがWithdrawの場合は、記録される情報はメッセージの受信日時と接続先のみである。

図６、図７は、経路変動判定部３５によるルートフラップ判定処理の流れをフローチャートで示した図である。
以下、図６、図７のフローチャートを参照しながら、経路変動判定部３５によるルートフラップ判定処理を詳細に説明する。

まず、経路変動判定部３５は、メッセージ取得部Ａ（３１）、あるいはメッセージ取得部Ｂ（３２）を介して取得される新規ＢＧＰ経路更新メッセージが到着したか否かを判定する（図６のステップＳ６０１）。ここで、新規ＢＧＰ経路更新メッセージが到着した場合、経路変動判定処理部３５は、前に到着したＢＧＰ経路更新メッセージとの間隔を参照する（ステップＳ６０２）。ここで、その間隔が、ある閾値Ｉｓよりも大きい場合（ステップＳ６０２“ＹＥＳ”）、新規に到着したＢＧＰ経路更新メッセージは、新しいイベントに属すると判定し（ステップＳ６０３）、閾値Ｉｓ以下の場合は（ステップＳ６０２“ＮＯ”）、新たに到着したＢＧＰ経路更新メッセージは前のＢＧＰ経路更新メッセージと同じイベントに属すると判定する（ステップＳ６０８）。

なお、閾値Ｉｓは、ＢＧＰルータでのＢＧＰ経路更新メッセージの送出間隔から、３０〜５０秒程度に設定されるものとする。また、「イベント」とは、本実施形態に係る経路変動判定装置３０が、複数のＢＧＰルータ４０（１〜ｎ）から受信したＢＧＰ経路更新メッセージを時系列に並べた場合の、時間的に一定の条件を満たすメッセージ群を一纏めにしたものとする。

ここで、新しいイベントが発生した場合、前のイベントがルートフラップにより発生したイベントであるか否かの判定処理を行う。
まず、前のイベントの最後のＢＧＰ経路更新メッセージとの間隔を参照する（ステップＳ６０４）。それがある閾値Ｒｓ以下の場合（ステップＳ６０４“ＮＯ”）、新たなイベントは、前のイベントとの関連イベントであると推定し（ステップＳ６０９）、ここではルートフラップ判定は行わない。ここで、閾値Ｒｓは、ＢＧＰルータでのルートフラップダンピングによって抑制された経路が再広報される時間を考慮し、１０〜３０分程度に設定されるものとする。

一方、前のイベントの最後のＢＧＰ経路更新メッセージとの間隔がＲｓよりも大きい場合には（ステップＳ６０４“ＹＥＳ”）、ある接続先から受信したＢＧＰ経路更新メッセージにおいて、イベント内に同じＡＳパス、属性を持つ経路が存在するか否かを判定する（図７のステップＳ６０５）。この判定の意図について、以下に説明する。
正常な経路変動の場合は、イベント内に同じ経路が繰り返し現れることはないと考えられる。しかしながら、ルートフラップが発生した場合は、例えば、図８において、ＡＳ３がＡＳ１とＡＳ２からＢＧＰ経路更新メッセージを受信する場合、そのＢＧＰ経路更新メッセージの受信タイミングや観測点へのメッセージ送信タイミングにより、観測点で同じイベント内に同一経路が観測される場合が考えられる。ここで同一経路とは、ＢＧＰ経路更新メッセージ内に含まれる情報（ＡＳパス、ＭＥＤ値、Ｃｏｍｍｕｎｉｔｙ値）が全て同じメッセージのことをいう。なお、図８は、イベント内の同一経路について説明するために引用した概念図である。

説明を、図６、図７のフローチャートに戻す。ステップ６０５の処理において、イベント内に同じＡＳパス、属性を持つ経路が存在しない場合（ステップＳ６０５“ＮＯ”）、前のイベントはルートフラップによるイベントではないと判定し、判定処理を終了する（ステップＳ６１４）。

一方、イベント内に同じＡＳパス、属性を持つ経路が存在する場合には（ステップＳ６０５“ＹＥＳ”）、次に、全ての接続先から最後にWithdrawを受信しているか否かを判定する（ステップＳ６０６）。上記のように、プレフィックス生成元でルートフラップが発生した場合、経路上でルートフラップダンピングが実行されているとすれば、接続先からのイベントの最後のメッセージはWithdrawとなる。また、例えば、図９に示す接続先＃２のように、あるイベントにおいて接続先からメッセージを全く受信しなかった場合は、直前のイベントにおける最後の受信メッセージを参照し、それがWithdrawであれば本条件を満たすものと考える。なお、図９は、メッセージ間隔、イベント間隔を説明するために引用した概念図である。

このことから、経路変動判定部３５は、全ての接続先から最後にWithdrawを受信しているか否かを判定し（ステップＳ６０６）、ここで、ＹＥＳの場合、イベントは、プレフィックス生成元でのルートフラップによるイベントであると判定する（ステップＳ６１２）。また、経路変動判定部３５は、少なくとも一つの接続先から最後にWithdrawを受信しているか否かを判定し（ステップＳ６０７）、ここで、ＹＥＳの場合、イベントは、経路途中でのルートフラップによるイベントであると判定し（ステップＳ６１３）、一方、全ての接続先から最後にAnnounceを受信している場合は（ステップＳ６０７“ＮＯ”）、ルートフラップによるイベントではないと判定する（ステップＳ６１４）。

なお、参考として、図１０に、プレフィックス生成元でのルートフラップによるイベントの場合のＢＧＰ経路更新メッセージのパターン例を示し、また、図１１に、経路途中でのルートフラップによるイベントの場合のＢＧＰ経路更新メッセージのパターン例を、また、図１２に、ルートフラップイベントではない場合のＢＧＰ経路更新メッセージのパターン例をそれぞれ示す。図１０、図１１、図１２に示す例では、４つの接続先（ＩＰアドレスは、10.0.0.1、10.0.0.2、10.0.0.3、10.0.0.4）とＢＧＰ接続を行い、ＢＧＰ経路更新メッセージを受信している場合を示している。

説明を、図６、図７に示すフローチャートに戻す。新規のＢＧＰ経路更新メッセージが到着しない場合においては（図６のステップＳ６０１“ＮＯ”）、前のイベントの最後のＢＧＰ経路更新メッセージとの間隔を参照し（ステップＳ６１１）、それが閾値Ｒｓ以下の場合は（ステップＳ６１１“ＮＯ”）、ここではルートフラップ判定は行わない。一方、閾値Ｒｓよりも大きい場合には（ステップＳ６１１“ＹＥＳ”）、ある接続先から受信したＢＧＰ経路更新メッセージにおいて、イベント内に同じＡＳパス、属性を持つ経路が存在するか否かを判定する（ステップＳ６０５）。以降の処理は上記と同様であるため、その説明を省略する。

最後に、経路変動判定部３５は、ルートフラップと判定されたイベントであるＢＧＰ経路更新メッセージ群をファイル出力部３６に出力する。ファイル出力部３６は、ルートフラップと判定されたイベントについて必要な情報を抽出し、ＢＧＰ経路変動ログ４２として保存する。ここで、抽出し、保持する情報は、図１３に示されるように、プレフィックス、ルートフラップの発生場所、イベントの開始時刻、終了時刻、継続時間、イベントに含まれるメッセージ数、等が考えられる。

上述したように、本実施形態によれば、単一のＢＧＰルータからではなく、複数のＢＧＰルータから受信したＢＧＰ経路更新メッセージから、ルートフラップ発生時の特徴的なメッセージパターンを抽出することにより、ルートフラップ発生の有無や発生場所を特定し、また、ルートフラップ発生時のＢＧＰ経路更新メッセージの受信パターンを抽出し、保存する。
このことにより、ルートフラップ発生の有無や発生場所を特定することができ、また、ルートフラップ発生時のＢＧＰ経路更新メッセージの受信パターンの特性を把握することができる。したがって、インターネット経路制御における不安定経路を特定することで、その経路の生成元への連絡と対処を迅速に行うことが可能となり、インターネット経路制御の安定化維持に貢献することができる。

なお、本実施形態において、経路変動判定部３５が、参照し、判定し、特定する機能は、いずれも経路変動判定装置３０がハードウェアとして持つ演算装置が実行するものであり、また、ファイル格納部３４により生成されるファイル、および、ＢＧＰ経路更新メッセージダンプファイル４１、ＢＧＰ経路変動ログ４２は、ともに記憶装置に割り当てられ格納されるものである。ここでは、演算装置、記憶装置とも図示省略してある。

また、図３に示す経路変動判定装置３０の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、経路変動判定処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。

さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。

以上、本発明の実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。

ルートフラップが発生した場合におけるＢＧＰ経路更新メッセージの伝達モデルについて説明するために引用した図である。 ルートフラップが発生した場合におけるＢＧＰ経路更新メッセージの伝達モデルについて説明するために引用した図である。 本発明の一実施形態による経路変動判定装置３０の構成を示すブロック図である。 ＭＲＴフォーマットで表されるＢＧＰ経路更新メッセージの一例を示す図である。 図３に示す経路変動判定装置３０により生成されるメッセージファイルの一例を示す図である。 本発明の一実施形態に係る経路変動判定処理の流れ示すフローチャートである。 本発明の一実施形態に係る経路変動判定処理の流れ示すフローチャートである。 本発明の一実施形態に係る経路変動判定処理を説明するために引用した図であり、イベント内の同一経路を表した図である。 本発明の一実施形態に係る経路変動判定処理を説明するために引用した図であり、メッセージ間隔、イベント間隔を表した図である。 本発明の一実施形態に係るＢＧＰ経路更新メッセージのパターンの一例を示す図である。 本発明の一実施形態に係るＢＧＰ経路更新メッセージのパターンの一例を示す図である。 本発明の一実施形態に係るＢＧＰ経路更新メッセージのパターンの一例を示す図である。 図３に示す経路変動判定装置３０により生成されるＢＧＰ経路変動ログのデータ構造の一例を示す図である。 ネットワーク構成をＡＳ単位で表現した図である。 ルートフラップダンピングにおけるペナルティの変化を説明するために引用した図である。 ＢＧＰ経路更新メッセージがＡＳ間を伝搬するにつれ、メッセージ数が増加する様子を説明するために引用した図である。

符号の説明

３０…経路変動判定装置、３１…メッセージ取得部Ａ、３２…メッセージ取得部Ｂ、３３…メッセージ処理部、３４…ファイル格納部、３５…経路変動判定部、３６…ファイル出力部、４０…ＢＧＰルータ、４１…ＢＧＰ経路更新メッセージダンプファイル、４２…ＢＧＰ経路変動ログ

Claims (10)

1. 独立した管理単位であるＡＳ（Autonomous System）が結合して構成されるネットワークシステムにおいて、ある特定のプレフィックスに関してルートフラップが発生しているか否かを判定する経路変動判定装置であって、
   観測点の前記ＡＳに隣接する複数のＢＧＰ(Border Gateway Protocol)ルータから、ＢＧＰ経路更新メッセージを取得するメッセージ取得部と、
   前記取得した複数のＢＧＰ経路更新メッセージからルートフラップ発生時の特徴的なメッセージパターンを抽出し、前記ある特定のプレフィックスに関してルートフラップが発生しているか否かを判定する経路変動判定部と、
   を備えたことを特徴とする経路変動判定装置。
2. 前記経路変動判定部は、
   前記ある特定のプレフィックスにルートフラップが発生していると判定したとき、前記ルートフラップの発生場所を特定することを特徴とする請求項１に記載の経路変動判定装置。
3. 前記メッセージ取得部は、
   前記複数のＢＧＰルータと接続を行い、それぞれのＢＧＰルータからＢＧＰ経路更新メッセージを受信することを特徴とする請求項１に記載の経路変動判定装置。
4. 前記メッセージ取得部は、
   あらかじめ前記複数のＢＧＰルータから取得されファイルに格納されているＢＧＰ経路更新メッセージを、取得することを特徴とする請求項１に記載の経路変動判定装置。
5. 前記取得したＢＧＰ経路更新メッセージをプレフィックス毎に分類し、少なくとも、時間と経路の属性に関する情報を抽出して前記経路変動判定部へ出力するか、若しくは前記プレフィックス毎に少なくとも時間と経路の属性に関する情報を持つ一つのＢＧＰ経路更新メッセージファイルを生成し保存するメッセージ処理部、
   を更に備えたことを特徴とする請求項１から４のいずれかの項に記載の経路変動判定装置。
6. 前記経路変動判定部は、
   前記ＢＧＰ経路更新メッセージを新たに取得したとき、前に取得したＢＧＰ経路更新メッセージとの間隔により、該新たに取得したＢＧＰ経路更新メッセージが、前記複数のＢＧＰルータから受信したＢＧＰ経路更新メッセージを時系列に並べた場合の時間的に所定の条件を満たすメッセージ群をグルーピングしたイベントに属するか否かを判定し、
   前記イベントに属さないと判定したとき、前記イベントの最後に取得したＢＧＰ経路更新メッセージとの間隔が所定の値以下の場合に関連イベントと判定し、前記所定の値を越えた場合、更に、ある接続先から受信したＢＧＰ経路更新メッセージにおいて、前記イベント内に同じ属性を持つ経路が存在するか否かを判定し、存在しないときに、前記イベントはルートフラップよるイベントでないと判定することを特徴とする請求項１または２に記載の経路変動判定装置。
7. 前記経路変動判定部は、
   前記イベント内に同じ属性を持つ経路が存在する場合、全ての接続先ＢＧＰルータから最後にWithdrawを受信するイベントは、そのプレフィックスの生成元でのルートフラップによるイベントであると判定することを特徴とする請求項６に記載の経路変動判定装置。
8. 前記経路変動判定部は、
   前記イベント内に同じ属性を持つ経路が存在する場合、少なくとも一つの接続先ＢＧＰルータから最後にWithdrawを受信するイベントは、経路途中でのルートフラップによるイベントであると判定することを特徴とする請求項６に記載の経路変動判定装置。
9. 前記経路変動判定部は、
   ルートフラップによるイベントであると判定された前記イベントについて、前記関連するＢＧＰ経路更新メッセージからルートフラップ発生時の特徴的なメッセージパターンを抽出し、その結果をログとして保存することを特徴とする請求項７又は８に記載の経路変動判定装置。
10. 独立した管理単位であるＡＳ（Autonomous System）が結合して構成されるネットワークシステムにおいて、ある特定のプレフィックスに関してルートフラップが発生しているか否かを判定する経路変動判定処理を行うためのコンピュータプログラムであって、
    観測点の前記ＡＳに隣接する複数のＢＧＰ(Border Gateway Protocol)ルータから、ＢＧＰ経路更新メッセージを取得する機能と、
    前記取得した複数のＢＧＰ経路更新メッセージからルートフラップ発生時の特徴的なメッセージパターンを抽出し、前記ある特定のプレフィックスに関してルートフラップが発生しているか否かを判定する機能と、
    をコンピュータに実現させることを特徴とするコンピュータプログラム。
    
    
    

Images