(57)【要約】【課題】BGP経路を可用率に基づいて定量的に評価できるBGP経路評価方法および装置を提供する。【解決手段】メッセージ受信部１０１は、BGPスピーカ間で交換されるBGP Updateメッセージを受信する。状態検知部１０２は、BGP Updateメッセージの"Announce（経路通知）"および"Withdraw（経路取消）"に基づいて各BGP経路の可用／非可用状態を検知する。管理テーブル１０４では、各BGP経路の可用／非可用状態が管理されている。更新登録部１０３は、各BGP経路の可用／非可用状態を更新登録する登録部１０３ａと、マルチホームを管理する登録部１０３ｂと、集約経路を管理する登録部１０３ｃと、別途に入力される除外期間情報に基づいて評価除外期間を管理する登録部１０３ｄとを含む。評価部１０５は、管理テーブル１０４に基づいて各BGP経路を評価する。【選択図】図３
2009081638.tif 000002
【特許請求の範囲】
【請求項１】
BGP経路を宛先のアドレス空間ごとに評価するBGP経路評価装置において、
BGP更新メッセージを受信するメッセージ受信手段と、
宛先のアドレス空間ごとにBGP経路の累積可用時間を管理する管理テーブルと、
受信したBGP更新メッセージに基づいて、宛先のアドレス空間ごとにBGP経路の可用状態を検知する可用状態検知手段と、
前記可用状態の検知結果に基づいて、前記管理テーブルの対応するエントリの累積可用時間を更新する更新手段と、
各宛先のアドレス空間へ至るBGP経路の可用率を、その累積可用時間に基づいて算出する評価手段とを含むことを特徴とするBGP経路評価装置。
【請求項２】
宛先のアドレス空間ごとに評価除外期間を検知する手段と、
前記評価除外期間を前記管理テーブルへ登録する手段とを含み、
前記評価手段は、前記評価除外期間を除いた期間の可用率を算出することを特徴とする請求項１に記載のBGP経路評価装置。
【請求項３】
前記管理テーブルにおいて、各エントリがプレフィックスおよびネクストホップのペアごとに管理されていることを特徴とする請求項１または２に記載のBGP経路評価装置。
【請求項４】
宛先のプレフィックスが同一でネクストホップの異なる複数のBGP経路が存在するときに、前記プレフィックスへ至る各BGP経路の少なくとも一つが可用状態であれば可用時間を累積されるマルチホームエントリを管理テーブルに登録するマルチホーム登録手段を含むことを特徴とする請求項３に記載のBGP経路評価装置。
【請求項５】
一のプレフィックスが他のプレフィックスに集約されているときに、前記一のプレフィックスへ至るBGP経路および他のプレフィックスへ至るBGP経路の少なくとも一方が可用状態であれば可用時間を累積される集約経路エントリを管理テーブルに登録する集約経路登録手段を含むことを特徴とする請求項３に記載のBGP経路評価装置。
【請求項６】
BGP経路を宛先のアドレス空間ごとに評価するBGP経路評価方法において、
宛先のアドレス空間ごとにBGP経路の累積可用時間を管理する管理テーブルを備え、
BGP更新メッセージを受信する手順と、
受信したBGP更新メッセージに基づいて、宛先のアドレス空間ごとにBGP経路の可用状態を検知する手順と、
前記可用状態の検知結果に基づいて、前記管理テーブルの対応するエントリの累積可用時間を更新する手順と、
各宛先のアドレス空間へ至るBGP経路の可用率を、その累積可用時間に基づいて算出する手順とを含むことを特徴とするBGP経路評価方法。
【請求項７】
宛先のアドレス空間ごとに評価除外期間を検知する手順と、
前記評価除外期間を前記管理テーブルへ登録する手順とを含み、
前記評価手段は、前記評価除外期間を除いた期間の可用率を算出することを特徴とする請求項６に記載のBGP経路評価方法。
【請求項８】
前記管理テーブルにおいて、各エントリがプレフィックスおよびネクストホップのペアごとに管理されていることを特徴とする請求項６または７に記載のBGP経路評価方法。
【請求項９】
宛先のプレフィックスが同一でネクストホップの異なる複数のBGP経路が存在するときに、前記プレフィックスへ至る各BGP経路の少なくとも一つが可用状態であれば可用時間を累積されるマルチホームエントリを管理テーブルに登録する手順を含むことを特徴とする請求項８に記載のBGP経路評価方法。
【請求項１０】
一のプレフィックスが他のプレフィックスに集約されているときに、前記一のプレフィックスへ至るBGP経路および他のプレフィックスへ至るBGP経路の少なくとも一方が可用状態であれば可用時間を累積される集約経路エントリを管理テーブルに登録する手順を含むことを特徴とする請求項８に記載のBGP経路評価方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、BGP経路を評価するBGP経路評価方法および装置に係、特に、BGP経路を可用率に基づいて定量的に評価できるBGP経路評価方法および装置に関する。
【背景技術】
【０００２】
現在のインターネットは、各組織が保有・運用する小規模な自律ネットワークシステム(AS：Autonomous System)を単位としたドメインの集合であり、各ドメインは特定の他のドメインとBGP(Border Gateway Protocol)を用いたピアリングを行うことで相互に接続されている。
【０００３】
一般的なBGPを用いた対外接続の高信頼化手法として、非特許文献１には、同時に複数のASと接続し、障害時の代替経路を確保するマルチホームが開示されている。このようなマルチホームを用いることで、対外接続の可用性が向上するために高信頼化を図ることが可能となる。非特許文献２には、BGPにおけるベストパス選択アルゴリズムが開示されている。
【非特許文献１】IPv4 Multihoming Practices and Limitations, RFC 4116
【非特許文献２】A Border Gateway Protocol 4 (BGP-4), RFC 4271
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、マルチホームにおけるトラヒック転送は、実際には一つの接続先に対してのみ可能であり、また、障害時の接続先の切り替えは、一定時間の通信断を生じる問題がある。より可用性を向上させるには、最も故障率の低いパスを選択することが望まれるが、非特許文献２に開示されたベストパス選択アルゴリズムでは、運用ポリシーによる制御を除き、最短パスが優先されるので、故障率の低いパスを選択することができなかった。
【０００５】
本発明の目的は、上記した従来技術の課題を解決し、BGP経路を可用率に基づいて定量的に評価できるBGP経路評価方法および装置を提供することにある。
【課題を解決するための手段】
【０００６】
上記した目的を達成するために、本発明は、BGP経路を宛先のプレフィックスごとに評価するBGP経路評価装置において、以下のような手段を講じた点に特徴がある。
【０００７】
(1)BGP更新メッセージを受信するメッセージ受信手段と、宛先のプレフィックスごとにBGP経路の累積可用時間を管理する管理テーブルと、受信したBGP更新メッセージに基づいて、宛先のプレフィックスごとにBGP経路の可用状態を検知する可用状態検知手段と、前記可用状態の検知結果に基づいて、前記管理テーブルの対応するエントリの累積可用時間を更新する更新手段と、各宛先のプレフィックスへ至るBGP経路の可用率を、その累積可用時間に基づいて算出する評価手段とを含むことを特徴とする。
【０００８】
(2)宛先のプレフィックスごとに評価除外期間を検知する手段と、評価除外期間を前記管理テーブルへ登録する手段とを含み、評価手段は、評価除外期間を除いた期間の可用率を算出することを特徴とする。
【０００９】
(3)宛先のプレフィックスが同一でネクストホップの異なる複数のBGP経路が存在するときに、前記プレフィックスへ至る各BGP経路の少なくとも一つが可用状態であれば可用時間を累積されるマルチホームエントリを管理テーブルに登録するマルチホーム登録手段を含むことを特徴とする。
【００１０】
(4)一のプレフィックスが他のプレフィックスに集約されているときに、前記一のプレフィックスへ至るBGP経路および他のプレフィックスへ至るBGP経路の少なくとも一方が可用状態であれば可用時間を累積される集約経路エントリを管理テーブルに登録する集約経路登録手段を含むことを特徴とする。
【発明の効果】
【００１１】
本発明によれば、以下のような効果が達成される。
(1)BGP経路を、その可用率に基づいて定量的に評価できるので、故障率の低いパスを選択できるようになる。
(2)意図的な非可用期間を評価期間から除外できるので、各BGP経路の可用率を正確に算出できるようになる。
(3)マルチホームASに関しては、宛先のプレフィックスへ至る複数のBGP経路を個別に評価できるのみならず、各BGP経路の可用率とは別に、宛先のプレフィックスへの到達性も定量的に評価できる。
(4)一方のプレフィックスが他方のプレフィックスに集約される関係を有する各プレフィックスへ至る各BGP経路を個別に評価できるのみならず、各BGP経路の可用率とは別に、宛先のプレフィックスへの到達性も定量的に評価できる。
【発明を実施するための最良の形態】
【００１２】
以下、図面を参照して本発明の最良の実施の形態について詳細に説明する。図１は、本発明のBGP経路評価方法が適用されるBGPネットワークの一例を示した図であり、AS3からプレフィックス[192.168.0.0/24]，[192.168.2.0/23]および[192.168.2.0/24]へ到達するための次ホップが[10.0.0.1]であり、AS3からプレフィックス[192.168.1.0/23]へ到達するための次ホップが[11.0.0.1]であり、AS3からプレフィックス[192.168.8.0/24]へ到達するための次ホップが[11.0.0.1]および[12.0.0.5]である。すなわち、AS3はAS1およびAS2にマルチホームしている。
【００１３】
AS3のBGPスピーカには、AS3を起点とする各BGP経路の可用率を、宛先のアドレス空間（本実施形態では、プレフィックス）ごとに算出し、この算出結果に基づいて各BGP経路を評価するBGP経路評価装置１が接続されている。
【００１４】
次いで、前記BGP経路評価装置１で算出されるBGP経路可用率について、図２を参照して説明する。
【００１５】
本実施形態では、所定の評価期間(t1〜t6)を対象に、各プレフィックスへ到達するBGP経路の可用状態を、BGP Update（更新）メッセージの"Announce（経路通知）"および"Withdraw（経路取消）"に基づいて検知し、評価期間に占める可用期間の割合が可用率として算出される。
【００１６】
前記可用期間とは、BGP経路が可用状態であった時間であり、場合によっては、図２に示したように複数期間の和となる。例えば、一日のうち、可用状態が６時間毎に変化した場合、可用期間は１２時間、評価期間は２４時間となるので、経路可用率は５０％となる
【００１７】
ただし、実インターネットでは、プレフィックスの新規割当てを始め、接続先ピアの切り替えや定期保守等の様々な理由から、運用者が意図的にBGP Updateメッセージを広報して運用を停止する場合がある。このような意図的は非可用状態が外部情報により把握可能な場合、意図的非可用期間として評価期間から除かれる。なお、非可用状態を外部情報により把握することが困難な場合には、一般的な障害時間を予め定義し、それを上回る期間を意図的非可用期間としてもよい。
【００１８】
図２を例にすれば、評価期間は[t6−t1]であり、可用期間は[t2−t1]および[t4−t3]であり、非可用期間は[t3−t2]および[t5−t4]であり、このうち非可用期間[t5−t4]は意図的な非可用期間なので、可用率は次式(1)で求められる。
【００１９】
【数１】
2009081638.tif 000003
【００２０】
図３は、前記BGP経路評価装置１の主要部の構成を示した機能ブロック図である。メッセージ受信部１０１は、BGPスピーカ間で交換されるBGP UpdateメッセージをAS3のBGPスピーカ経由で受信する。状態検知部１０２は、BGP Updateメッセージの"Announce（経路通知）"および"Withdraw（経路取消）"に登録されているプレフィックスおよびネクストホップのペアに基づいて各BGP経路の可用／非可用状態を検知する。
【００２１】
管理テーブル１０４では、各BGP経路の可用／非可用状態が管理されている。更新登録部１０３は、前記可用／非可用状態の検知結果に基づいて管理テーブル１０４の登録内容を更新する。評価部１０５は、前記管理テーブル１０４の登録内容に基づいて各BGP経路を評価する。
【００２２】
前記更新登録部１０３は、各BGP経路の可用／非可用状態を更新登録する可用／非可用更新登録部１０３ａと、後に詳述するマルチホームを管理するマルチホーム更新登録部１０３ｂと、後に詳述する集約経路を管理する集約経路更新登録部１０３ｃと、別途に入力される除外期間情報に基づいて評価除外期間を管理する除外期間更新登録部１０３ｄとを備えている。
【００２３】
図４は、本実施形態の動作を示したフローチャートであり、主に前記BGP経路評価装置１の動作を示している。ここでは、前記管理テーブル１０４に、図５に示したように３つのエントリが既登録である状態から説明を始める。
【００２４】
ステップＳ１では、BGP経路評価装置１とBGPスピーカとの間にセッションが確立される。ステップＳ２において、BGP Updateメッセージが前記メッセージ受信部１０１によりBGPスピーカ経由で受信されると、ステップＳ３では、前記状態検知部１０２において、当該メッセージの種別が"Announce（経路通知）"および"Withdraw（経路取消）"のいずれであるかが判定される。
【００２５】
AnnounceであればステップＳ４へ進み、新規経路の通知であるか否かが判定される。ここで、Announceに登録されているプレフィックスおよびネクストホップが、それぞれ[192.168.8.0/24]および[11.0.0.1]であれば、当該ペアのエントリが管理テーブル１０４に未登録なので、新規経路と判定されてステップＳ５へ進む。ステップＳ５では、図６に示したように、通知されたプレフィックス[192.168.8.0/24]およびネクストホップ[11.0.0.1]のペアを識別子とするタイプNのエントリが、前記可用／非可用更新登録部１０３ａによって管理テーブル１０４に新規登録され、その評価開始日時欄に現在日時が登録される。
【００２６】
ステップＳ６では、新規登録されたBGP経路のプレフィックス[192.168.8.0/24]が、その登録前から管理テーブル１０４に既登録であったか否かに基づいて、当該新規経路がマルチホームであるか否かが、前記マルチホーム更新登録部１０３ｂにより判定される。ここでは、プレフィックスが前記新規経路のプレフィックス[192.168.8.0/24]と同一のエントリが未登録なので、マルチホームではないと判定されてステップＳ８へ進む。
【００２７】
ステップＳ８では、当該新規経路のプレフィックス[192.168.8.0/24]を包含するプレフィックスのエントリが既登録であるか否かに基づいて、当該新規経路が他の既登録経路に集約可能であるか否かが、前記集約経路更新登録部１０３ｃにより判定される。ここでは、プレフィックス[192.168.8.0/24]を包含できるエントリが未登録と判定されるので、今回の処理を終了する。
【００２８】
次いで、前記ステップＳ２で新たに受信されたAnnounceに登録されているプレフィックスおよびネクストホップが、それぞれ[192.168.8.0/24]および[12.0.0.5]であれば、前記と同様に新規経路と判定されてステップＳ５へ進む。ステップＳ５では、図７に示したように、通知されたプレフィックス[192.168.8.0/24]およびネクストホップ[12.0.0.5]のペアを識別子とするタイプNのエントリが、前記可用／非可用更新登録部１０３ａによって管理テーブル１０４に新規登録され、その評価開始日時に現在日時が登録される。
【００２９】
ステップＳ６では、新規登録された経路のプレフィックス[192.168.8.0/24]が、その登録前から管理テーブル１０４に既登録であり、マルチホームと判定されるのでステップＳ７へ進む。ステップＳ７では、図８に示したように、当該新規経路に関して、そのプレフィックス[192.168.8.0/24]のみを識別子とするタイプMのエントリが、前記マルチホーム更新登録部１０３ｂによって管理テーブル１０４に登録され、その評価開始日時に現在日時が登録される。
【００３０】
このタイプMエントリでは、宛先のプレフィックス[192.168.8.0/24]へ至る複数のBGP経路の少なくとも一つが可用状態であれば可用時間を累積されるので、タイプMエントリの可用率を求めれば、各BGP経路の可用率とは別に、宛先のプレフィックスへの到達性を評価できる。
【００３１】
ステップＳ８では、前記新規経路が他の既登録経路に集約可能であるか否かが判定される。ここでは、プレフィックス[192.168.8.0/24]を包含できるエントリが未登録と判定されるので、今回の処理を終了する。
【００３２】
次いで、前記ステップＳ２で新たに受信されたAnnounceに登録されているプレフィックスおよびネクストホップが、それぞれ[192.168.2.0/24]および[10.0.0.1]であれば、前記と同様に新規経路と判定されてステップＳ５へ進む。ステップＳ５では、図９に示したように、プレフィックス[192.168.2.0/24]およびネクストホップ[10.0.0.1]のペアを識別子とするタイプNのエントリが、前記可用／非可用更新登録部１０３ａによって管理テーブル１０４に新規登録される。
【００３３】
ステップＳ６では、新規登録された経路のプレフィックス[192.168.2.0/24]が、その登録前には管理テーブル１０４に未登録と判定されるのでステップＳ８へ進む。ステップＳ８では、図１５に示したように、当該新規経路のプレフィックス[192.168.2.0/24]のアドレス空間を包含するプレフィックス[192.168.2.0/23]のエントリが管理テーブル１０４に既登録と判定されるのでステップＳ９へ進む。
【００３４】
ステップＳ９では、図１０に示したように、プレフィックス欄が宛先のプレフィックスであり、ネクストホップ欄に集約先のプレフィックス[192.168.2.0/23]が登録されたタイプAのエントリが、前記集約経路更新登録部１０３ｃによって管理テーブル１０４に新規登録される。
【００３５】
このタイプAのエントリでは、宛先のプレフィックスが他のプレフィックスに集約されているとき、宛先のプレフィックスへ至るBGP経路および他のプレフィックスへ至るBGP経路の少なくとも一方が可用状態であれば可用時間を累積されるので、各BGP経路の可用率とは別に、宛先のプレフィックスへの到達性を評価できる。
【００３６】
一方、前記ステップＳ３において、BGP Updateメッセージが"Withdraw（経路取消）"と判定されるとステップＳ１０へ進む。ここでは初めに、Withdrawに登録されているプレフィックスおよびネクストホップが、それぞれ[192.168.8.0/24]および[12.0.0.5]である場合を例にして説明する。
【００３７】
ステップＳ１０では、当該メッセージに登録されているプレフィックスおよびネクストホップのペアで識別されるタイプNのエントリに関して、その経路情報が更新される。ここでは、最終更新日時から現在日時までの経過時間が、既登録の累積可用時間に加算され、最終更新日時が現在日時に更新登録される。なお、最終更新日時が未登録であれば、評価開始日時から現在日時までの経過時間が、既登録の累積可用時間に加算され、最終更新日時として現在日時が新規登録される。
【００３８】
ステップＳ１１では、Withdrawで通知された取消経路がマルチホームであるか否かが判定される。ここでは、プレフィックス[192.168.8.0/24]に関してタイプMのエントリが既登録なので、マルチホームと判定されてステップＳ１２へ進む。ステップＳ１２では、マルチホームの関係にある全てのBGP経路のタイプNエントリが非可用状態であるか否かが判定され、全てのエントリが非可用であればステップＳ１３へ進む。ステップＳ１３では、タイプMエントリの最終更新日時および累積可用時間が、前記と同様にして更新される。
【００３９】
図１１は、タイプMエントリが更新された管理テーブル１０４の登録内容を示した図であり、プレフィックスが[192.168.8.0/24]のエントリに関して、ネクストホップが[12.0.0.5]のタイプNエントリ、およびタイプMエントリの最終更新日時および累積可用時間が更新されている。
【００４０】
これに対して、前記ステップＳ１２において、取消経路とマルチホームの関係にある他のタイプNエントリが可用状態にあると判定されると、図１２に示したように、ネクストホップが[12.0.0.5]のタイプNエントリのみが更新され、タイプMエントリは更新されない。
【００４１】
すなわち、タイプMエントリは、マルチホームの関係にある全てのエントリが非可用状態であるとき以外は可用状態とされて可用時間を累積されるので、タイプNのエントリを参照することで個々のBGP経路の可用状態を評価できるのみならず、タイプMエントリを参照することにより、宛先のプレフィックスへの到達性を評価できる。
【００４２】
ステップＳ１４では、Withdrawで通知された取消経路が集約経路であるか否かが判定されるが、今回の取消経路は集約経路ではないのでステップＳ１９へ進む。
【００４３】
これに対して、Withdrawに登録されていたプレフィックスおよびネクストホップが、それぞれ[192.168.2.0/24]および[10.0.0.1]であれば、前記ステップＳ１０において、対応するタイプNエントリが更新される。ステップＳ１１では、マルチホームではないと判定されるのでステップＳ１４へ進む。ステップＳ１４では、プレフィックスが[192.168.2.0/24]のタイプAエントリが既登録なので、取消経路が集約経路と探偵されてステップＳ１５へ進む。
【００４４】
ステップＳ１５では、取消経路を集約しているエントリ[192.168.2.0/23]が非可用状態であるか否かが判定され、非可用であればステップＳ１６へ進む。ステップＳ１６では、図１３に一例を示したように、タイプAエントリの最終更新日時および累積可用時間が、前記と同様にして更新される。
【００４５】
これに対して、取消経路を集約しているエントリ[192.168.2.0/23]が可用状態と判定されれば、図１４に一例を示したように、タイプNエントリのみが更新され、タイプAエントリは更新されない
【００４６】
すなわち、タイプAエントリは、宛先のプレフィックスが他のプレフィックスに集約されているとき、宛先のプレフィックスに至るBGP経路が非可用であっても、この非可用経路を集約する他のプレフィックスに至るBGP経路が可用状態であれば非可用とされずに可用時間を累積される。したがって、タイプNのエントリを参照することで個々のBGP経路の可用状態を評価できるのみならず、タイプAエントリを参照することにより、宛先のプレフィックスへの到達性を評価できる。
【００４７】
一方、前記ステップＳ４において、受信した"Announce"で通知された経路が新規ではないと判定されるとステップＳ１７へ進み、当該経路が非可用状態であるか否かが判定される。非可用状態であればステップＳ１８へ進み、タイプNの対応エントリに関して、その最終更新日時に現在日時が更新登録され、その状態が非可用から可用に変更される。
【００４８】
ステップＳ１９では、所定の評価期間が完了したか否かが判定され、評価期間が完了するまでは、ステップＳ２へ戻って次のBGP Updateメッセージの受信に備える。評価期間が完了するとステップＳ２０へ進み、前記式(1)に基づいて各エントリの可用率が算出され、その後、可用率に基づいて各BGP経路や各プレフィックスへの到達性が評価される。
【図面の簡単な説明】
【００４９】
【図１】本発明が適用されるBGPネットワークの一例を示した図である。
【図２】BGP経路可用率を説明するための図である。
【図３】BGP経路評価装置の主要部の構成を示した機能ブロック図である。
【図４】本発明の一実施形態の動作を示したフローチャートである。
【図５】管理テーブルの登録内容を模式的に表現した図（その１）である。
【図６】管理テーブルの登録内容を模式的に表現した図（その２）である。
【図７】管理テーブルの登録内容を模式的に表現した図（その３）である。
【図８】管理テーブルの登録内容を模式的に表現した図（その４）である。
【図９】管理テーブルの登録内容を模式的に表現した図（その５）である。
【図１０】管理テーブルの登録内容を模式的に表現した図（その６）である。
【図１１】管理テーブルの登録内容を模式的に表現した図（その７）である。
【図１２】管理テーブルの登録内容を模式的に表現した図（その８）である。
【図１３】管理テーブルの登録内容を模式的に表現した図（その９）である。
【図１４】管理テーブルの登録内容を模式的に表現した図（その１０）である。
【図１５】プレフィックスの集約関係を説明するための図である。
【符号の説明】
【００５０】
１…BGP経路評価装置，１０１…メッセージ受信部，１０２…状態検知部，１０３…更新登録部，１０４…管理テーブル，１０５…評価部
【図１】
2009081638.tif 000004
【図２】
2009081638.tif 000005
【図３】
2009081638.tif 000006
【図４】
2009081638.tif 000007
【図５】
2009081638.tif 000008
【図６】
2009081638.tif 000009
【図７】
2009081638.tif 000010
【図８】
2009081638.tif 000011
【図９】
2009081638.tif 000012
【図１０】
2009081638.tif 000013
【図１１】
2009081638.tif 000014
【図１２】
2009081638.tif 000015
【図１３】
2009081638.tif 000016
【図１４】
2009081638.tif 000017
【図１５】
2009081638.tif 000018