(57)【要約】  【課題】  膨大なBGP経路更新メッセージの履歴から、不到達などの経路障害を検出し、その障害種別を特定する。  【解決手段】  ステップＳ３１で、i番目のプレフィクスイベントの優先度をP(i)としたときに、P(i)＞P（i+1）かつP（i+1）＜P（i+2）となる現象が２回以上、１回または０回発生したかを検査する。該現象が２回以上の場合には、「振動」障害と判定する。０回で、最後のプレフィクスがWITHDRAWの場合には、「長期的な不到達」、ANNOUNCEの場合には「長期的なマイナー経路への変更」と判定する。１回で、最後のプレフィクスの優先順位が障害検出時点のBGP経路表に含まれている同じプレフィクスのそれより低くなく、かつ履歴にWITHDRAWがある場合には「短期的な不到達」、該履歴にWITHDRAWがない場合には「短期的なマイナー経路への変更」と判定する。  【選択図】  図７ 
2005252863.tif 000002
【特許請求の範囲】
【請求項１】
BGP経路表を参照してBGP経路の障害種別を特定する経路障害種別特定方法であって、
受信したBGP経路更新メッセージの種別がANNOUNCEであり、該ANNOUNCEの優先順位が前記BGP経路表に含まれる同じプレフィクスの優先順位より低い場合障害が起きたと判断し、該プレフィクスに障害フラグを立てると共に、障害継続タイマを起動することを特徴とする経路障害種別特定方法。
【請求項２】
請求項１に記された経路障害種別特定方法において、
前記受信したBGP経路更新メッセージの種別がWITHDRAWの場合、前記BGP経路表に含まれる同じプレフィクスに障害フラグを立てると共に、障害継続タイマを起動することを特徴とする経路障害種別特定方法。
【請求項３】
請求項１または２に記された経路障害種別特定方法において、
前記障害継続タイマは、障害フラグを立てられたプレフィクス毎に起動するすることを特徴とする経路障害種別特定方法。
【請求項４】
請求項１または２に記された経路障害種別特定方法において、
前記障害継続タイマ起動中に再び同じプレフィクスに対するANNOUNCEまたはWITHDRAWを受信した場合、障害継続タイマを再起動することを特徴とする経路障害種別特定方法。
【請求項５】
請求項４に記された経路障害種別特定方法において、
前記障害継続タイマを起動および再起動した時に、少なくともメッセージ種別とプレフィクスとを障害検出部に通知することを特徴とする経路障害種別特定方法。
【請求項６】
請求項５に記された経路障害種別特定方法において、
前記障害継続タイマが予め定められた時間を満了した時に、前記障害フラグをOFFにし、前記障害検出部は障害検出を行うことを特徴とする経路障害種別特定方法。
【請求項７】
BGP経路の障害種別を特定する経路障害種別特定方法であって、
あるプレフィクスに対し連続的に発生した経路変動の時系列から、長期的な不到達、長期的なマイナー経路への変更、短期的な不到達、短期的なマイナー経路への変更および振動の障害の少なくとも一つを分析することを特徴とする経路障害種別特定方法。
【請求項８】
請求項７に記載の経路障害種別特定方法において、
あるプレフィクスに対するBGP経路更新メッセージの時系列において、ｉ番目に受信したBGP経路更新メッセージの優先度をP(i)としたときに、P(i)＞P（i+1）かつP（i+1）＜P（i+2）となる現象が２回以上発生したとき、振動と特定することを特徴とする経路障害種別特定方法。
【請求項９】
請求項７に記載の経路障害種別特定方法において、
あるプレフィクスに対するBGP経路更新メッセージの時系列において、ｉ番目に受信したBGP経路更新メッセージの優先度をP(i)としたときに、P(i)＞P（i+1）かつP（i+1）＜P（i+2）となる現象が０回で、最後のプレフィクスがWITHDRAWの場合には長期的な不到達、ANNOUNCEの場合には長期的なマイナー経路への変更と特定することを特徴とする経路障害種別特定方法。
【請求項１０】
請求項７に記載の経路障害種別特定方法において、
あるプレフィクスに対するBGP経路更新メッセージの時系列において、ｉ番目に受信したBGP経路更新メッセージの優先度をP(i)としたときに、P(i)＞P（i+1）かつP（i+1）＜P（i+2）となる現象が１回で、最後のプレフィクスの優先順位が障害検出時点のBGP経路表に含まれている同じプレフィクスの優先順位より低くなく、かつ履歴にWITHDRAWがある場合には短期的な不到達、該履歴にWITHDRAWがない場合には短期的なマイナー経路への変更と特定することを特徴とする経路障害種別特定方法。
【請求項１１】
請求項７に記載の経路障害種別特定方法において、
あるプレフィクスに対するBGP経路更新メッセージの時系列において、ｉ番目に受信したBGP経路更新メッセージの優先度をP(i)としたときに、P(i)＞P（i+1）かつP（i+1）＜P（i+2）となる現象が１回で、最後のプレフィクスの優先順位が障害検出時点のBGP経路表に含まれている同じプレフィクスの優先順位より低く、かつ最後のプレフィクスがWITHDRAWの場合には長期的な不到達、ANNOUNCEの場合には長期的なマイナー経路への変更と特定することを特徴とする経路障害種別特定方法。
【請求項１２】
請求項７ないし１１のいずれかに記載の経路障害種別特定方法において、
障害判定結果を、障害発生時刻、プレフィクスおよび障害種別とすることを特徴とする経路障害種別特定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は経路障害種別特定方法及び装置に関し、特に膨大なBGP経路更新メッセージの履歴から経路障害を検出し、障害種別を検出する経路障害種別特定方法に関する。
【背景技術】
【０００２】
背景技術として、ルータのBGP（Border  Gateway Protocol)経路表監視機能、zebraのダンプ機能および経路情報公開サーバを説明する。
【０００３】
（1）ルータのBGP経路表監視機能
BGP通信機能を持つルータは、RIB（Routing Information Base)と呼ばれるBGP経路表を内部で管理しており、現在のBGP経路表を確認するための監視用機能を具備している。BGP経路表は、BGP経路（以下、経路と呼ぶ）のリストで構成される。経路には、宛先アドレスの集合を示すプレフィクス（IPアドレスとサブネットマスクのビット数）と、そのプレフィクスに到達するための隣接ルータのアドレスや優先順位などを示すパラメータが含まれる。ある宛先アドレスがBGP経路表に含まれている場合、該当ルータから、その宛先アドレスへの経路が存在し、パケットが到達可能であることを表す。
【０００４】
該BGP経路表監視機能は、ルータにログインし、監視用コマンドを入力することにより実行するため、自身が運用するルータに対してのみ実行可能である。IX（Internet Exchange)等では、Webサーバベースでルータのログインおよび監視コマンドの入力を可能とするサービスを行っている。
【０００５】
（2）zebraのダンプ機能
ソースフリーのルーティングソフトウェアzebra(http://www．zebra．org/）は、相手先ルータから受信したBGP経路更新メッセージ並びにBGP経路表をファイルにダンプ出力する機能を持つ。これらのファイルは、MRTフォーマットと呼ばれる標準フォーマットに格納され、BGP経路表についてはMRT-RIBフォーマット、BGP経路更新メッセージについてはMRT-UPDATEフォーマットに格納される。
【０００６】
（3）経路情報公開サーバ
Route Views（http://www．routeviews．org/)プロジェクトや、RIPE（http://www．ripe．net/)は、多数のAS（Autonomous System)とEBGP(External BGP)接続を行い、各ASが送信するBGP経路更新メッセージを収集し、一定時間毎にファイルに蓄積する。また、各ASから受信したBGP経路更新メッセージをもとに、BGP経路表を作成し、一定時間毎にファイルに蓄積する。Route  Viewsプロジェクトでは、BGP経路更新メッセージを15分毎に、BGP経路表を2時間毎に蓄積し、これらをWebサーバにより公開している。
【０００７】
なお、各種の通信品質の態様（品質要素）にそれぞれ対応した複数のBGP経路表を各BGPルータに配信することを可能とする配信ルートサーバ装置は、特開２００２−２５２６３８号公報に開示されている。
【特許文献１】特開２００２−２５２６３８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
前記ルータのBGP監視機能は、現在、BGP経路表に格納されている経路のみを出力する。ルータは、互いに経路情報を交換する隣接ルータ毎に、プレフィクス毎の最新の経路のみを保持する。従って、ある隣接ルータから、新しい経路情報を受信した場合、その隣接ルータから以前に受信した経路はRIBから削除される。このため、BGP経路表の監視においては、過去に発生した経路変更や経路取り消しなどの情報を得ることはできない。
【０００９】
前記zebraのダンプ出力機能は、相手先ルータから受信した全ての経路更新メッセージをダンプ出力、すなわち何らの加工を施さないでそのまま出力する。しかしながら、経路更新メッセージの数は膨大であり、その多くは、外部ポリシーの変更など、接続性に影響を及ぼさないメッセージである。このため、ダンプ出力された情報から、接続性の紛失などの障害に関連したメッセージのみを抽出することは困難である。前記経路情報公開サーバで公開されるBGP経路更新メッセージも膨大なデータ量であり、障害に関連したメッセージのみを抽出することは困難である。
【００１０】
本発明は、前記した従来技術に鑑みてなされたものであり、その目的は、膨大なBGP経路更新メッセージの履歴から、不到達などの経路障害を検出し、その障害種別を特定する経路障害種別特定方法を提供することにある。
【課題を解決するための手段】
【００１１】
前記した目的を達成するために、本発明は、BGP経路表を参照してBGP経路の障害種別を特定する経路障害種別特定方法であって、受信したBGP経路更新メッセージの種別がANNOUNCEであり、該ANNOUNCEの優先順位が前記BGP経路表に含まれる同じプレフィクスの優先順位より低い場合障害が起きたと判断し、該プレフィクスに障害フラグを立てると共に、障害継続タイマを起動するようにした点に第１の特徴がある。また、前記受信したBGP経路更新メッセージの種別がWITHDRAWの場合、前記BGP経路表に含まれる同じプレフィクスに障害フラグを立てると共に、障害継続タイマを起動するようにした点に第２の特徴がある。
【００１２】
また、BGP経路の障害種別を特定する経路障害種別特定方法であって、あるプレフィクスに対し連続的に発生した経路変動の時系列から、長期的な不到達、長期的なマイナー経路（現在の経路より優先度が低い経路）への変更、短期的な不到達、短期的なマイナー経路への変更および振動の障害の少なくとも一つを分析するようにした点に第３の特徴がある。
【発明の効果】
【００１３】
インターネット上の全経路を受信するBGP経路更新メッセージの数は膨大であるが、本発明によれば、該膨大なBGP経路更新メッセージの中から経路障害が発生したことを簡単に検出することができるようになる。また、該経路障害の種別を簡単に検出することができるようになる。
【００１４】
また、出力結果を、障害発生時刻、プレフィクスおよび障害種別のみに簡略化しているため、障害復旧や原因追及に向けた対応を迅速に行えるようになる。
【発明を実施するための最良の形態】
【００１５】
以下に、本発明を実施形態を用いて詳細に説明する。ルータは経路情報を交換することにより、互いの隣接ルータが送信するアドレスに到達することができる。アドレスは、プレフィクス（IPアドレスとサブネットマスクビット）単位で交換される。経路情報交換に使用される一つのプレフィクスを経路と呼ぶ。経路は、プレフィクスと、そのプレフィクスに到達するための隣接ルータのアドレスや優先順位などを示すパラメータのリストで構成される。このパラメータはASパス属性と呼ばれ、隣接ルータのアドレスを示すNEXT HOP、宛先アドレスに到達するために通過するASの集合を表すASパス、自AS内のポリシーにより設定された経路の優先度を表すLOCAL PREFなどが存在する。
【００１６】
一般に、一つのプレフィクスに対して、ASパス属性が異なる複数の経路が存在する。インターネット全体など、広範囲に経路情報を交換するプロトコルとしては、BGP（Border Gateway Protocol)が用いられている。AS（Autonomous System)間の経路情報の交換には、EBGP(External BGP)、AS内の経路情報の交換にはIBGP(Internal BGP)が使用される。
【００１７】
経路情報の交換は、BGP経路更新メッセージを用いて行われる。BGP経路更新メッセージには、そのプレフィクスへ到達可能であることを表すANNOUNCEメッセージと、過去に到達できたものの到達できない状態に遷移したことを表すWITHDRAWメッセージの２つが存在する。
【００１８】
ANNOUNCEメッセージは、プレフイクスと、ASパス属性で構成される。BGPルータは、あるプレフィクスに対し、複数のBGPルータから受信した経路のうち、最も優先度が高い経路を他のBGPルータに送信する。優先順位の決定は、個々のASパス属性の比較により行われる。
【００１９】
また、他のBGPルータからのWITHDRAWメッセージの受信などにより、あるプレフィクスに到達できる経路がなくなった場合には、WITHDRAWメッセージを送信する。該WITHDRAWメッセージには、ASパス属性は存在しない。これらのメッセージは、他のBGPルータから受信したメッセージ、自BGPルータにおける設定変更、自BGPルータにおけるNIC(Network Interface Card)故障などにより、自BGPルータのBGP経路表が更新されたときに送信される。
【００２０】
さらに、BGPでは、プレフィクスや、ASパス属性などをもとに、受信した経路の優先順位を決定するための入力ポリシーや、他のBGPルータに送信する経路を決定するための出力ポリシーをBGPルータ毎に設定することができる。例えば、AS＃1から受信した経路に高いLOCAL PREF値を付加し優先順位の高い経路とする、AS＃2から受信した経路は他のASには送信しない、といった設定を施すことができる。通常、BGPの運用においては、AS毎に一貫したポリシーを持つため、AS内の全てのBGPルータにおいて、そのポリシーに従った設定が施される。
【００２１】
図1に、複数のBGPルータR1〜R6が接続された構成において、BGP経路更新メッセージが伝播する仕組みを述べる。ルータR1で障害が発生した場合に、プレフィクス10．0．0．0/24に対するBGP経路更新メッセージが複数の経路を伝播し、ルータR6で観測される場合を想定する。なお、ルータR5では、ルータR2から受信する経路を最優先とし、次にR3、その次にR4から受信する経路を優先するようにポリシー設定を行っている。
【００２２】
ルータR1での障害により、R1はR2、R3、R4の全てに、WITHDRAWを送信する。R2、R3、R4は他のBGPルータから、10．0．0．0/24を受信していないため、R5にWITHDRAWを送信する。R5は、R2からWITHDRAWを受信したとき、まだR3、R4からの経路を保持しているため、R3から受信した経路を、ANNOUNCEを用いてR6に送信する。R6は、R5よりASパスが（AS5 AS3 AS1)の経路（図1右下の履歴の（1）の経路）を受信することとなる。次に、R3からWITHDRAWを受信したとき、R4からの経路をR6に送信する。このとき、R6は、R5よりASパスが（AS5 AS4 AS1)の経路（図１の右下の履歴の（2）の経路）を受信する。
【００２３】
さらに、R4からWITHDRAWを受信したとき、経路がなくなったため、R5はWITHDRAWをR6に送信する。R6は(3)で、該WITHDRAWを受信する。
【００２４】
R5が、R2、R3、R4からのWITHDRAWを、異なる順序で受信した場合には、前記（1）および(2)、あるいはそのいずれかが観測されない。これらのメッセージの受信順序は、障害発生元（図1ではRl）と観測点（図1ではR6）の間のBGPルータの数、中継BGPルータの処理能力、各BGPルータ間の回線速度や物理的距離などにより異なる。
【００２５】
一方、障害が復旧し、再びRlが10．0．0．0/24を送信した場合には、R5はR2、R3、R4からのANNOUNCEメッセージを受信し、R4、R3、R2の順で受信した場合には、全てのANNOUNCEメッセージ（図1右下の履歴の（4）（5）（6））をR6に送信する。
【００２６】
経路障害の要因には、(a)ソフトウェアのバグや故障によるルータ機能の停止、(b)ルータのBGP経路入力／出力ポリシーの設定ミス、（c）コマンド投入や大量の経路更新メッセージの受信に伴うルータの過負荷、などが考えられる。
【００２７】
(c)の場合は、BGPのプロトコル手順による復旧が可能なため、短期的な障害となるが、(a)(b)の場合は、人手による復旧が必要なため、障害が長期的に継続する。さらに、(a)(b)の場合には、障害発生元において、WITHDRAWメッセージのみが送信される場合と、WITHDRAWメッセージおよびANNOUNCEメッセージが繰り返し送信される場合が考えられる。
【００２８】
そこで、図２に、観測点で得られるBGP経路更新メッセージ履歴に従い、障害種別を定義した。個々の障害の分類方法を以下に示す。
【００２９】
(i)ルータ機能の停止などにより、あるプレフィクスへの到達性が失われた場合、長期的な不到達となる。この場合、優先度が低くなる順にANNOUNCEメッセージを複数（0も含む）受信した後、WITHDRAWメッセージ受信により不到達となる。なお、経路の優先度は、ANNOUNCEメッセージのパラメータであるLOCAL PREF、ASパス、MEDなどのASパス属性で比較する。例えばASパス長が短い経路ほど優先度が高い。
【００３０】
(ii）上記と同じ障害要因において、障害が発生したASを経由しない代替経路が存在する場合、優先度の低い経路（マイナー経路）への変更となる。この場合、不到達の場合と同様に、優先度が低くなる順にANNOUNCEメッセージを複数（0も含む）受信するが、WITHDRAWメッセージは観測されない。
【００３１】
(iii)ルータの過負荷などの場合、優先度が低くなる順にANNOUNCEメッセージを受信し、次いでWITHDRAWメッセージを受信した後、数分後（例えば、５〜６分後）に優先度が高くなる順にANNOUNCEを複数受信し、障害発生前に受信したBGP経路更新メッセージと同じASパス属性を持つメッセージを受信する。
【００３２】
(iv)上記と同じ障害要因において、優先度が低くなる順にANNOUNCEメッセージを受信した後、数分後に障害発生前に受信したBGP経路更新メッセージと同じASパス属性を持つメッセージを受信する。
【００３３】
(v)ルータの動作が不安定な場合、ANNOUNCEメッセージとWITHDRAWメッセージ、あるいは、複数の異なる優先度のANNOUNCEメッセージを繰り返し受信する現象（すなわち、振動）が発生する。
【００３４】
なお、図中の括弧「（  ）」は受信しないかもしれないことを示し、スラッシュ「／」は、どちらかであることを示す。
【００３５】
次に、本発明の一実施形態の経路障害種別特定装置を図３に示す。本発明では、BGP経路更新メッセージの履歴から、プレフィクス毎に、障害を検出し、その障害種別を特定するようにした点に特徴がある。
【００３６】
本実施形態の装置は、BGP経路更新メッセージの受信方法として２通りを想定し、少なくとも一方を具備する。一つは、経路受信部１を持ち、経路受信部１においてBGPルータとBGP接続を行うことにより、実時間で、BGP経路更新メッセージを受信する方法である。
【００３７】
もう一つは、ファイル入力部２を持ち、zebraのダンプ機能などにより、予め収集したBGP経路表ダンプファイル３、BGP経路更新メッセージダンプファイル４を、非実時間で解析する方法である。BGP経路表ダンプファイル３を入力する場合、ファイル入力部２は、BGP経路表に含まれる経路をBGP経路更新メッセージに分解し、メッセージ処理部３に送信する。BGP経路更新メッセージダンプファイル４を入力する場合には、ファイル入力部２は、そのまま時刻順にメッセージ処理部３に送信する。
【００３８】
メッセージ処理部３は、実時間あるいは非実時間で受信したBGP経路更新メッセージを時間順に処理する。また、BGP経路表４を更新する。該メッセージ処理部３は、本発明により導入した障害フラグ、障害継続タイマの２つの変数を用いて、障害に関するBGP経路更新メッセージの履歴を抽出する。障害フラグは、あるプレフィクスに対して障害に関連するBGP経路更新メッセージの受信が継続しているか否かを示すフラグであり、ON/OFFの２つの値を取り得る。  図４に、前記BGP経路表４の概念図を示す。該BGP経路表４には、プレフィクスと、最新のASパス、すなわち最新の経路が登録される。
図４に、前記BGP経路表４の概念図を示す。該BGP経路表４には、プレフィクスと最新のASパス、すなわち最新の経路が登録され、これらは前記メッセージ処理部３により更新される。
【００３９】
障害継続タイマ部５は、障害に関連するBGP経路更新メッセージの待機時間を設ける等のために用いる。障害判定部６は、前記障害継続タイマ部５がタイマ時間を満了すると前記(i)〜(v)の障害を判定し、判定結果をファイル出力部７に出力する。ファイル出力部７は、ファイルをBGP経路障害ログ８に出力する。
【００４０】
以下に、前記メッセージ処理部３の処理手順を図５のフローチャートを参照して説明する。なお、BGP経路更新メッセージは、図６に示すように、ANNOUNCEメッセージとWITHDRAWメッセージとからなる。また、ANNOUNCEメッセージはプレフィクスの集合で構成されるNLRIとこれらのプレフィクスに共通したASパス属性とからなり、ASパス属性はLOCAL PREFやAS-PATHが含まれる。一方、WITHDRAWメッセージはプレフィクスの集合で構成されるWithdrawn Routesからなり、ASパス属性は存在しない。
【００４１】
BGP経路更新メッセージを受信すると、図５のステップＳ１では、メッセージの種別、すなわち、ANNOUNCEメッセージとWITHDRAWメッセージの判定がなされる。ANNOUNCEメッセージの場合にはステップＳ２に進み、NLRI(Network Layer Reachability Information)を参照してプレフィクスを抽出する。以降の処理はプレフィクス単位で行い、NLRIあるいはWithdrawn Routesに含まれる全てのプレフィクス（プレフィクスリスト）の処理が終了するまで、ステップＳ３〜Ｓ１１までの処理を継続する。一方、WITHDRAWメッセージの場合にはステップＳ１２に進み、Withdrawn Routesよりプレフィクスを抽出する。ステップＳ１２以降の処理はプレフィクス単位で行い、全てのプレフィクス（プレフィクスリスト）の処理が終了するまで、ステップＳ１３〜Ｓ２０までの処理を継続する。
【００４２】
受信したBGP経路更新メッセージがANNOUNCEメッセージの場合、ステップＳ３では、プレフィクスリストが終了したか否かの判断を行い、この判断が否定の時にはステップＳ４に進んで、該プレフィクスの障害フラグがONであるか否かの判断がなされる。この判断が否定、すなわちOFFの時には、該プレフィクスがBGP経路表４中に存在するか否かの判断がなされ、存在する場合にはステップＳ６に進み、存在しない場合にはステップＳ１１に進んでＢＧＰ経路表４に追加される。
【００４３】
ステップＳ６では、BGP経路表４とANNOUNCEメッセージとのASパス属性の比較において、BGP経路表４のものよりANNOUNCEメッセージの優先度が低い場合には何らかの障害があったと考えられるので、ステップＳ７に進んで障害フラグがONにされる。一方、優先度が高いか同じ経路であった場合には、障害がないと考えられるので、ステップＳ１１に進む。なお、優先度の比較はRFC1771に示される経路選択アルゴリズムに従う。初めに、LOCAL PREF値で比較し大きい方が優先とする。同じ値の場合には、ASパス長を比較し小さい方を優先とする。以降、順に別のパラメータを比較していく。
【００４４】
ステップＳ８では、前記BGP経路表４のプレフィクスとＡＳパス属性が、障害判定部６に通知される。ステップＳ４で障害フラグが立っていると判断された場合、または前記ステップＳ８の処理が終わった場合、ステップＳ９に進んで障害継続タイマ５を起動する。なお、障害継続タイマ５は、一定時間以内に連続して受信したメッセージとそうでないメッセージとを識別するために用いる。
【００４５】
ステップＳ１０では、メッセージ種別、プレフィクスおよびASパス属性が障害検出部６に通知される。その後、ステップＳ１１を経て、ステップＳ３に戻りプレフィクスリストが終了したか否かの判断がなされる。ステップＳ１１では、BGP経路表４の該当プレフィクスを、ANNOUNCEメッセージに含まれるASパス属性に更新する。また、BGP経路表４にプレフィクスの経路が存在しない場合（前記ステップＳ５が否定の場合）には、該プレフィクスとASパス属性がBGP経路表４に登録される。
【００４６】
次のプレフィクスが存在する場合には、ステップＳ３の判断は否定になり、該次のプレフィクスに関して、前記ステップＳ４以下の処理が行われる。この場合、既に障害フラグがONにされているプレフィクスであるとステップＳ９で障害継続タイマは再起動、すなわちリセットされる。前記した処理が繰り返し行われ、その後、ステップＳ３の判断が肯定になると、前記一連の処理は終了する。
【００４７】
前記障害継続タイマ５は、所定の時間、例えば１０分間に設定されており、１０分間を計測すると満了し、次の図７のタイマ満了時の処理および障害判定処理に移る。
【００４８】
次に、受信したBGP経路更新メッセージがWITHDRAWメッセージの場合の処理を説明する。WITHDRAWメッセージのプレフィクスの障害フラグがOFFの場合（ステップＳ１４がOFF）でかつBGP経路表４にそのプレフィクスに対する経路が含まれている場合（ステップＳ１５が肯定）、ステップＳ１６で障害フラグをONにして、ステップＳ１７〜Ｓ２０の処理を実行する。一方、前記障害フラグがONの場合には、ステップＳ１８〜Ｓ２０の処理が実行される。また、BGP経路表４にプレフィクスの経路が存在しない場合（ステップＳ１５が否定）には、ステップＳ１３に戻って次のプレフィクスの処理を行う。
【００４９】
前記ステップＳ１７では、BGP経路表４のプレフィクス、ASパス属性が障害判定部６に通知される。次いで、ステップＳ１８で、障害継続タイマ５が起動される。ステップＳ１９では、メッセージ種別（WITHDRAW）、プレフィクスが障害検出部６に通知され、ステップＳ２０では、BGP経路表４の更新処理、すなわちBGP経路表から該当プレフィクスを削除する処理がなされる。次いで、ステップＳ１３に戻って、次のプレフィクスの処理が行われる。
【００５０】
前記ステップＳ１８で起動された障害継続タイマ５が、前記所定の時間、例えば１０分間の計測を満了すると、次の図７のタイマ満了時の処理および障害判定処理に移るのは前記と同様である。
【００５１】
前記障害継続タイマ部５は、前記の説明から明らかなように、プレフィクス単位で障害継続タイマの満了を検出する。メッセージ処理を実時間で行う場合には、装置の内部時計により、非実時間で行う場合には、メッセージに含まれる受信時刻情報の差分により、タイマの満了を判定する。
【００５２】
次に、障害継続タイマ満了時の処理手順および障害判定処理手順を図７のフローチャートを参照して説明する。
【００５３】
図７のステップＳ２１では、タイマ部５は、メッセージ処理部３に障害フラグをOFFにすることを要求する。次に、タイマ部５は、障害判定部６に、障害に関するメッセージ履歴の受信終了を表す信号を送信する。
【００５４】
そうすると、障害判定部６では、障害検出時点（障害フラグをONにした時点）でのBGP経路表４のASパス属性、ならびに、以降に受信したメッセージ種別（ANNOUNCEまたはWITHDRAW）と、ANNOUNCEのASパス属性の組の履歴（履歴内の個々の要素を、プレフィクスイベントと呼ぶ）から、ステップＳ３１〜Ｓ３９の手順に従って障害種別の特定を行う。
【００５５】
ステップＳ３１では、連続するプレフィクスイベントを順に比較し、i番目のプレフィクスイベントの優先度をP(i)としたときに、P(i)＞P（i+1）かつP（i+1）＜P（i+2）となる現象が２回以上発生したとき、振動と特定する（ステップＳ３２）。すなわち、図８(a)のように優先度の高いプレフィクスと低いプレフィクスとを交互に受信する現象が２回以上発生すると「振動」と特定される。なお、図８の縦軸はプレフィクスの優先順位、横軸はプレフィクスイベントを示す。
【００５６】
ステップＳ３１でP(i)＞P（i+1）かつP（i+1）＜P（i+2）となる現象が２回以上発生しなかった時は、長期的な不到達、長期的なマイナー経路への変更、短期的な不到達あるいは短期的なマイナー経路への変更のいずれかである。
【００５７】
前記現象が０回の時にはステップＳ２３に進んで、最後のプレフィックスイベントがWITHDRAWであるか否かの判断がなされ、WITHDRAWの場合、長期的な不到達とする（ステップＳ３４）。一方、最後のプレフィクスイベントがWITHDRAWでない場合、すなわちANNOUNCEであり優先度が低い場合、長期的なマイナー経路への変更とする（ステップＳ３５）。すなわち、図８(b)のように、最後のプレフィクスがWITHDRAWであれば「長期的な不到達」、ANNOUNCEであれば「長期的なマイナー経路への変更」と特定される。
【００５８】
次に、前記現象が１回の場合には、ステップＳ３６に進んで、障害検出時点でのBGP経路表４と最後のプレフィクスイベントとの比較がなされ、後者のプレフィクスイベントの優先度が前者のものと同じか高い場合には、ステップＳ３７に進んで、プレフィクスイベント履歴にWITHDRAWがあるか否かの判断がなされる。そして、この判断が肯定であれば、短期的な不到達と特定する（ステップＳ３８）。一方、否定であれば、短期的なマイナー経路への変更と特定する（ステップＳ３９）。すなわち、図８(c)のような場合で、プレフィクスイベント履歴にWITHDRAWがあれば「短期的な不到達」、なければ「短期的なマイナー経路への変更」と特定される。
【００５９】
さらに、前記ステップＳ３６の判断が肯定の場合、すなわち障害検出時点でのBGP経路表４と最後のプレフィクスイベントとの比較がなされ、後者のプレフィクスイベントの優先度が前者のものより低い場合には、ステップＳ３３に進んで、最後のプレフィクスイベントがWITHDRAWであるかANNOUNCEであるかに従って、長期的な不到達、長期的なマイナー経路への変更と特定される（ステップＳ３４，Ｓ３５）。すなわち、図８(d)に示されるようになる。
【００６０】
上記のようにして、障害判定が行われると、ステップＳ４０に進み、該障害判定結果は、判定部６からファイル出力部７に送信される。図９に、障害判定結果の出力例を示す。図から明らかなように、障害判定結果は、障害発生時刻（図５において、障害フラグをONにした時刻）、プレフィクス、障害種別の情報を含む。出力結果を、障害発生時刻、プレフィクスおよび障害種別のみに簡略化したため、障害復旧や原因追及に向けた対応を迅速に行えるようになる。
【００６１】
前記障害継続タイマの満了時間を１０分としたのは、以下の理由による。BGPルータは、一般に、連続するANNOUNCEメッセージの送信を３０秒程度遅らせる動作を行うため、メッセージが伝播する経路により、観測点でのメッセージの受信時刻にずれが存在する。この値は、長くとも１０分以内と考えられる。また、BGPルータヘのコマンド投入や大量の経路更新メッセージの受信に伴う過負荷による短期的な障害も１０分以内で復旧する現象と考えられる。なお、１０分は本発明に好適な満了時間であり、これに限定されるものではない。
【００６２】
本発明によれば、プレフィクス毎に障害を検出することができる。プレフィクスは、障害が発生したアドレス範囲を表すので、顧客あるいはインターネット上の外部ASのいずれでの障害かを識別することができる。障害種別は、障害の重度を判断するのに利用可能である。例えば、長期的な不到達は、長時間接続性が失われたことを示す重大な障害であるのに対し、短期的なマイナー経路への変更は、一時的に優先度の低い経路を選択したという軽度な障害である。
【図面の簡単な説明】
【００６３】
【図１】BGP経路更新メッセージの伝播状態の一例の説明図である。
【図２】障害種別の定義と、BGP経路更新メッセージ履歴と、障害要因を示す図である。
【図３】本発明を実施するための経路障害種別特定装置の構成を示すブロック図である。
【図４】BGP経路表の概念図である。
【図５】経路障害の発生を検出するためのBGP経路更新メッセージ受信処理を説明するフローチャートである。
【図６】BGP経路更新メッセージの内容を示す説明図である。
【図７】障害継続タイマ満了時の処理および障害判定処理のフローチャートである。
【図８】障害判定の説明図である。
【図９】障害判定結果の出力例を示す図である。
【符号の説明】
【００６４】
１・・・経路受信部、２・・・ファイル入力部、３・・・メッセージ処理部、４・・・BGP経路表、５・・・タイマ部、６・・・障害判定部、７・・・ファイル出力部。
【図１】
2005252863.tif 000003
【図２】
2005252863.tif 000004
【図３】
2005252863.tif 000005
【図４】
2005252863.tif 000006
【図５】
2005252863.tif 000007
【図６】
2005252863.tif 000008
【図７】
2005252863.tif 000009
【図８】
2005252863.tif 000010
【図９】
2005252863.tif 000011