(57)【特許請求の範囲】
【請求項１】
BGPルータにおける経路表の管理方法であって、
経路表を管理する第一のBGPルータより該経路表に宛先として記載のプレフィックスを収集するステップと、
所定期間に渡り前記第一のBGPルータにて中継された各パケットの宛先IPアドレスを収集するステップと、
前記収集された宛先IPアドレスを前記収集されたプレフィックスに割り当て、各プレフィックスが前記所定期間に渡り宛先として使用された頻度を集計するステップと、
前記頻度が少ないことに関する所定基準を満たすプレフィックスを前記第一のBGPルータにおける経路表から削除すると共に、前記第一のBGPルータにおける経路表に第二のBGPルータを次ホップとするデフォルトルートを設定するステップと、
前記第二のBGPルータにおける経路表にて前記所定基準を満たすプレフィックスを宛先として設定するステップとを備えることを特徴とするBGPルータにおける経路表の管理方法。
【請求項２】
前記宛先ＩＰアドレスを収集するステップ及び前記頻度を集計するステップを再度行うステップと、
当該再度集計された頻度が前記所定基準を満たさなくなったプレフィックスを前記第一のBGPルータにおける経路表に宛先として設定すると共に前記第二のBGPルータにおける経路表から削除するステップと、
当該再度集計された頻度が前記所定基準を満たすようになったプレフィックスを前記第一のBGPルータにおける経路表から削除すると共に前記第二のBGPルータにおける経路表にて宛先として設定するステップとさらに備えることを特徴とする請求項１に記載のBGPルータにおける経路表の管理方法。
【請求項３】
前記第一及び第二のBGPルータは所定のASに属し、前記経路表から削除し、前記経路表に宛先として設定する際の各BGPメッセージが前記AS内に閉じて流れることを特徴とする請求項１または２に記載のBGPルータにおける経路表の管理方法。
【請求項４】
BGPルータにおける経路表の管理サーバであって、
経路表を管理する第一のBGPルータより該経路表に宛先として記載のプレフィックスを収集するBGP受信部と、
所定期間に渡り前記第一のBGPルータにて中継された各パケットの宛先IPアドレスを収集するパケット情報受信部と、
前記収集された宛先IPアドレスを前記収集されたプレフィックスに割り当て、各プレフィックスが前記所定期間に渡り宛先として使用された頻度を集計する頻度集計部と、
前記頻度が少ないことに関する所定基準を満たすプレフィックスを前記第一のBGPルータにおける経路表から削除するBGPメッセージと、前記第一のBGPルータの経路表に第二のBGPルータを次ホップとするデフォルトルートを設定するBGPメッセージと、前記第二のBGPルータにおける経路表にて前記所定基準を満たすプレフィックスを宛先として設定するBGPメッセージとを送信するメッセージ送信部とを備えることを特徴とする管理サーバ。
【請求項５】
前記第二のBGPルータの役割を兼用することを特徴とする請求項４に記載の管理サーバ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、BGP(Border Gateway Protocol)ルータにおける経路表の効率的な管理方法及び管理サーバに関する。
【背景技術】
【０００２】
インターネットにおいてBGPより広告されるプレフィックスは年々増加しており、観測されるプレフィックス数が、ルータのメモリ上の経路表で管理できるプレフィックス数の上限に迫っている問題がある。このため、プレフィックスの効率的な管理が課題となっている。非特許文献１に記載された従来技術は、経路表を複数のルータで分散管理する方法を提案している。
【０００３】
図４は当該従来技術を説明するための図である。通常、デフォルトフリーゾーン（ＤＦＺ；デフォルトルートがないネットワーク）に接続されたBGPルータは、インターネットで観測される全プレフィックスを経路表で管理する。図４の構成では、仮にインターネットで観測される全プレフィックスを192.168.0.0/24〜192.168.5.0/24の計6個と想定し、互いに隣接するルータＡ〜ルータＣにおいて、それぞれ経路表ＴＡ１〜ＴＣ１として示すように、これら全プレフィックスを次ホップと対応づけて管理している。
【０００４】
当該構成に対して、従来技術では、次のような手法によって経路表のプレフィックスを複数のルータＡ〜Ｃで分散管理させる。すなわち、他AS(Autonomous System；自律システム)との接続を持つルータＡおよびルータＢにおいて、6個のプレフィックスを分散管理させる。例えば、ルータＡでは、192.168.0.0/24〜192.168.2.0/24の3個を管理し、ルータＢでは、192.168.3.0/24〜192.168.5.0/24の3個を管理するようにする。ただし、他のルータが保持するプレフィックスに対して、到達性を保証する必要があるため、表Ｔ２に示すように、それぞれ集約できる範囲で集約したプレフィックスを管理する。これにより、ルータＡ及びＢに対してそれぞれ経路表ＴＡ２及びＴＢ２として示すように、各ルータで管理するプレフィックス数を5個に削減できる（5/6に削減）。他のASとの接続を持たない、自AS内のルータＣでは、集約したプレフィックスを全て管理するため、経路表ＴＣ２として示すように、4個に削減できる（4/6に削減）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】FIB Suppression with Virtual Aggregation, Internet Draft, http://tools.ietf.org/id/draft-ietf-grow-va-05.txt
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来技術においては、各ルータで管理するプレフィックス数を効率的に削減するためには、上記手法によるプレフィックスの集約方法に加え、実際の運用に合わせて、各プレフィックスに対して流れるトラヒック量を考慮した上でプレフィックスを分散させる必要があるため、設計が複雑になる課題がある。さらに、分散の処理を自動化するためには、BGPプロトコルの拡張が必要になるという課題がある。
【０００７】
本発明の目的は、上記従来技術の課題を解決し、複雑な設計を必要とすることなく、また、BGPプロトコルの拡張を必要とすることなく、BGPルータで管理するプレフィックス数を効率的に削減することができる、BGPルータにおける経路表の管理方法及び管理サーバを提供することにある。
【課題を解決するための手段】
【０００８】
上記従来技術の課題を解決するために、本発明は、BGPルータにおける経路表の管理方法であって、経路表を管理する第一のBGPルータより該経路表に宛先として記載のプレフィックスを収集するステップと、所定期間に渡り前記第一のBGPルータにて中継された各パケットの宛先IPアドレスを収集するステップと、前記収集された宛先IPアドレスを前記収集されたプレフィックスに割り当て、各プレフィックスが前記所定期間に渡り宛先として使用された頻度を集計するステップと、前記頻度が少ないことに関する所定基準を満たすプレフィックスを前記第一のBGPルータにおける経路表から削除すると共に、前記第一のBGPルータにおける経路表に第二のBGPルータを次ホップとするデフォルトルートを設定するステップと、前記第二のBGPルータにおける経路表にて前記所定基準を満たすプレフィックスを宛先として設定するステップとを備えることを特徴とする。
【０００９】
また、上記従来技術の課題を解決するために、本発明は、BGPルータにおける経路表の管理サーバであって、経路表を管理する第一のBGPルータより該経路表に宛先として記載のプレフィックスを収集するBGP受信部と、所定期間に渡り前記第一のBGPルータにて中継された各パケットの宛先IPアドレスを収集するパケット情報受信部と、前記収集された宛先IPアドレスを前記収集されたプレフィックスに割り当て、各プレフィックスが前記所定期間に渡り宛先として使用された頻度を集計する頻度集計部と、前記頻度が少ないことに関する所定基準を満たすプレフィックスを前記第一のBGPルータにおける経路表から削除するBGPメッセージと、前記第一のBGPルータの経路表に第二のBGPルータを次ホップとするデフォルトルートを設定するBGPメッセージと、前記第二のBGPルータにおける経路表にて前記所定基準を満たすプレフィックスを宛先として設定するBGPメッセージとを送信するメッセージ送信部とを備えることを特徴とする。
【発明の効果】
【００１０】
本発明によれば、パケットの転送が必要となる転送実績のあるプレフィックスのみを第一のBGPルータで管理させることによって、第一のBGPルータにおけるプレフィックス数が削減されると共に、転送実績がなくとも前記所定期間の後に新たに転送の必要が生じうるプレフィックスについては第二のBGPルータで管理させることで、到達可能性も保証される。しかも当該各効果は、BGPプロトコルの拡張が不要で且つ単純な設計により達せられる。
【図面の簡単な説明】
【００１１】
【図１】経路表の管理サーバの機能ブロック図である。
【図２】経路表の管理方法のフローチャートである。
【図３】図２を説明するための図である。
【図４】従来技術を説明するための図である。
【発明を実施するための形態】
【００１２】
図１に、本発明に係る経路表の管理サーバの機能ブロックをBGPルータとのやりとりを含めて示す。管理サーバ１は、BGP受信部２，パケット情報受信部３，頻度集計部４及びメッセージ送信部５を備え、ミラーポート１１を備えるBGPルータ１０と各種の通信を行い、BGPルータ１０の経路表に設定を施して管理する。
【００１３】
図２に、本発明に係る経路表の管理方法のフローチャートを示す。図３は当該フローチャートを説明するための図であり、ここでのネットワーク構成例は図４で示した例と同様である。すなわち、BGPルータ１０の例として、自AS内にそれぞれIPアドレス11.0.0.1, 11.0.0.2及び11.0.0.3を付与されたルータＡ，Ｂ及びＣが存在する。管理対象となる全プレフィックスは192.168.0.0/24〜192.168.5.0/24の計6個であり、本発明を適用しない状態においてはルータＡ〜Ｃが、図４に示すデフォルトルートを有しない経路表ＴＡ１〜ＴＣ１により管理している。また他AS内には、次ホップとなるルータの例としてIPアドレス10.0.01を付与されたルータＺが存在し、ルータＡ及びＢと接続されている。
【００１４】
本発明においては、このような構成の自AS内に管理サーバ１（IPアドレス11.0.0.5）を配置する（１台あればよい）と共に、必要に応じて新たにBGPルータ１０の１つであるルータＤ(IPアドレス11.0.0.6)を導入する。なお、ルータＡ〜Ｃの各々と管理サーバ１又はルータＤとの間、管理サーバ１とルータＤとの間及び管理サーバ１又はルータＤとルータＺとの間はBGPにおける隣接関係にあるものとする。すなわち、管理サーバ１もルータＡ〜Ｄと同様にBGPルータの機能を有する。
【００１５】
なお、当該例においては、自ASに対する他ASは図３では１つのみであり、当該他AS内で自ASに次ホップとして接続しているのは１台のルータＺのみである。より一般に、他AS及び／又は他ASにおいて次ホップとなるルータＺiが複数ある場合(i=1,2,...,n)も、各他ASの各ルータＺiが管理サーバ１又はルータＤと隣接することにより、本発明を一般的に適用できる。
【００１６】
以下、ステップＳ１より開始される図２の各ステップを説明する。ステップＳ２にてBGP受信部２は、隣接するBGPルータ１０と適宜必要なBGPメッセージを交換することでBGPセッションを張り、図４のＴＡ１〜ＴＣ１のような経路表を取得すると共に、経路表に宛先として記載の全プレフィックス(192.168.0.0/24〜192.168.5.0/24)を収集する。ステップＳ３にてパケット情報受信部３は、BGPルータ１０のミラーポート１１より、１日又は１ヶ月といったような所定期間に渡って当該BGPルータが中継したデータパケットの情報、特に各パケットの宛先IPアドレスの情報を受信して収集する。
【００１７】
なお、ステップＳ２及びＳ３では、通信対象となるBGPルータ１０として各ルータＡ〜Ｃの中から任意の１台のみを選んで通信すればよい。例えば図３ではルータＡを対象としている。ステップＳ２では、経路表の全てを受信するのではなく、宛先として記載のプレフィックスのみを受信及び収集してもよい。ステップＳ３では、同様の情報を予めデータベース等として取得又は保存して利用できるようにしておけば、ミラーポート１１から直接リアルタイムに受信しなくともよい。
【００１８】
ステップＳ４にて頻度集計部４は、ステップＳ２で収集した経路表のプレフィックスとステップＳ３にて収集した宛先IPアドレスとを最長一致(Longest Match)アルゴリズムに従ってマッピングし、プレフィックス毎に観測されたパケット数を集計する。すなわち、各プレフィックスがステップＳ３の所定期間に渡り各パケットの宛先として使用された頻度を集計する。ステップＳ４の集計例を図３のテーブルＴ３０に示す。
【００１９】
ステップＳ５では、ステップＳ２で収集した各プレフィックスにつき以降のステップを実行するための識別カウンタiを初期値1に設定する。以下説明し図２中にも記載のように、各プレフィックスiに対して各ケース(1)〜(3)のうちの該当するケースに応じた処理がなされる。
【００２０】
ステップＳ６にて頻度集計部４は、i番目のプレフィックスが削除対象であるかを判定する。ここでは、ステップＳ４の集計結果において頻度が少ない側の所定条件にプレフィックスiが該当する場合に、削除対象であると判定する。図３の例では、テーブルＴ３０に示すように、観測パケット数が０個であり実際には使われていないプレフィックス192.168.3.0/24，192.168.4.0/24及び192.168.5.0/24が削除対象と判定される。所定条件としてはその他例えば、ステップＳ３の所定期間内で観測パケット数が１００個以下であること、等としてもよい。
【００２１】
ステップＳ６で削除対象と判定された場合[ケース(1)]、ステップＳ７にて当該プレフィックスiを各BGPルータ１０（図３ではルータＡ〜Ｃ）の経路表から削除するためのBGPメッセージ、すなわち当該プレフィックスiに対するWithdrawメッセージをメッセージ送信部５が各BGPルータ１０に送信する。この際、Withdrawメッセージの他ASへの流出を防ぐため、COMMUNITY属性としてNO EXPORTを設定する。
【００２２】
なお、ステップＳ７ではまた、当該削除するプレフィックスiが後述のステップＳ１０において追加対象となる場合に備えて、削除プレフィックスiに対する各ルータＡ〜Ｃでの当該時点における経路表に記載の次ホップを管理サーバ１において記録しておくものとする。
【００２３】
なおまた、当該図２のフロー全体を終えた後に、当該削除したプレフィックスiに対して仮に経路変更があった場合は、次のような処理を行うことで、図２のフローを再度繰り返す場合に向けた準備を行う。すなわち、当該経路変更の通知を各ルータＡ〜Ｃ及び管理サーバ１が受信すると、まず一旦、各ルータＡ〜Ｃは管理する経路表に当該プレフィックスiを、当該通知された経路変更を反映させて追加する。管理サーバ１は当該追加の直後に、当該プレフィックスiに対してステップＳ７及び後述のステップＳ８と同様の処理を行い、自身で管理している経路表におけるプレフィックスiにおいて次ホップを変更する等して経路変更を反映させ、経路表を更新する。このようにして、経路変更のあったプレフィックスiは各ルータＡ〜Ｃの経路表には（追加直後に削除されることによって）記載されず、管理サーバ１の経路表において経路変更を反映して管理されることとなる。
【００２４】
ステップＳ８では、当該削除されたプレフィックスiへの到達性を保証するため、各BGPルータ１０(ルータＡ〜Ｃ)に対して、メッセージ送信部５よりデフォルトルート0.0.0.0/0を広報する。この際、デフォルトルートの次ホップとしては、管理サーバ１自身のIPアドレスを、または当初全プレフィックスを管理していたルータＡ〜Ｃと別途にルータＤを追加利用できる場合には、当該ルータＤのIPアドレスを、ルータＡ〜Ｃに広報する。
【００２５】
ステップＳ８ではさらに、次ホップとして設定された管理サーバ１またはルータＤの経路表に、ルータＡ〜Ｃにて削除された当該プレフィックスiを宛先として設定させるBGPメッセージを、メッセージ送信部５が送信する。この際、当該宛先プレフィックスiの次ホップは前記ステップＳ７にて記録した各次ホップのうち、他ASに属するルータ（図３ではIPアドレス10.0.0.1のルータＺ）に設定できる。なお、管理サーバ１自身に設定する場合はBGPメッセージの送信を省略してもよい。
【００２６】
なおまた、ルータＤを追加利用せず管理サーバ１を利用する場合、管理サーバ１は当該追加利用することも検討可能なルータＤのBGPルータとしての役割を兼用しているとみなすことができる。
【００２７】
図３の経路表Ｔ３は、テーブルＴ３０に示す集計結果の場合にパケット数０のプレフィックスを削除対象とした場合の、当該管理サーバ１またはルータDに設定される経路表の例である。
【００２８】
ステップＳ６に戻り、前記所定条件に該当せず、プレフィックスiに所定の使用実績があり削除対象とは判定されなかった場合[ケース(2)または(3)]、ステップＳ９にて当該プレフィックスiが追加対象であるかを頻度集計部４が判定する。
【００２９】
追加対象であると判定されるのは、図２のフロー全体を例えば９月に一度実施して１０月に再度実施するといったように、ステップＳ３における異なる所定期間において2回以上実施しており、当該プレフィックスiが直前の回（例えば９月に実施の回）ではステップＳ６にて削除対象と判定されたが、今回（例えば１０月に実施の回）は削除対象とは判定されなかった場合[ケース(2)]である。
【００３０】
このように判定されるプレフィックスiはルータＡ〜Ｃの経路表から直前の回において削除されており、今回はルータＡ〜Ｃの経路表に戻す必要がある、すなわち追加対象である。そこでステップＳ１０において、メッセージ送信部５が各BGPルータ１０(ルータＡ〜Ｃ)に対して当該プレフィックスiを宛先として設定させるBGPメッセージすなわちAnnounceメッセージを送信する。この際も、Withdrawの場合と同様、Announceメッセージの他ASへの流出を防ぐため、NO EXPORT属性を有効にする。
【００３１】
この際、当該宛先プレフィックスiの次ホップは、直前の回のステップＳ７で削除されると共に管理サーバ１が記録し、前述のようにその後、当該削除されたプレフィックスiに対して経路変更があれば管理サーバ１の経路表において更新した次ホップを、各ルータＡ〜Ｃに設定する。
【００３２】
なお、図２のフロー全体を２回以上実施する場合、２回目以降においては１回目の後の経路変更も反映された、ルータＡ〜Ｃの経路表と管理サーバ１又はルータＤの経路表とによってその時点での全プレフィックスを保持している。よって２回目以降のステップＳ２では、前述のようにルータＡ〜Ｃのいずれかの経路表のみからではなく、さらに管理サーバ１又はルータＤの経路表からBGP受信部２が全プレフィックスを収集するものとする。
【００３３】
ステップＳ９に戻り、追加対象と判断されなかった場合[ケース(3)]、当該プレフィックスiはそのまま各ルータA〜Cの経路表に記載しておくべきプレフィックスであるので、WithdrawもAnnounceも不要であり、経路表における当該プレフィックスiに関する操作は何も行われない。
【００３４】
以上のような、プレフィックスiにつき各ケース(1)〜(3)のいずれかにおける処理を終えると、ステップＳ１１では全プレフィックスにつき処理が完了したかを頻度集計部４が判断し、完了していればステップＳ１３にて当該フローは終了し、完了していなければカウンタiを増分して次のプレフィックスを対象として再度ステップＳ６からフローが繰り返される。
【００３５】
図３の経路表ＴＡ３〜ＴＣ３は、上記のようなフローによりテーブルＴ３０に示す集計結果が得られ、Ｔ３に示す経路表が（ルータＤではなく）IPアドレス11.0.0.5の管理サーバ１に設定された場合の、ルータＡ〜Ｃにおいて設定される経路表の例である。さらに当該フローを再度行い、初回の集計結果Ｔ３０とは異なり例えば192.168.3.0/24のパケット数が０ではなく３００など相当数が得られ且つその他のプレフィックスにおける観測パケット数に関しては同様であり、フローを再度行うまでに経路変更などがなかった場合、各経路表は次のように更新される。
【００３６】
すなわち、経路表ＴＡ３及びＴＢ３において「プレフィックス192.168.3.0/24  次ホップ10.0.0.1」が追加され、経路表ＴＣ３において「プレフィックス192.168.3.0/24  次ホップ11.0.0.1」が追加され、経路表Ｔ３から「プレフィックス192.168.3.0/24  次ホップ10.0.0.1」が削除されることとなる。
【００３７】
なお、ステップＳ７，Ｓ８及びＳ１０の各BGPメッセージの送信及び経路表Ｔ３の構築については、各プレフィックスiにつきケース(1)〜(3)の判断と同時に個別にBGPメッセージ送信及び経路表構築するのではなく、判断のみ全プレフィックスにつき前もって下しておき、該当するプレフィックスをメッセージ内にまとめて格納して一括で行うようにして、送信及び構築の効率化を図ってもよい。
【００３８】
なおまた、図２のフロー全体を２回目以降に実行するに際しては、プレフィックスiが今回、ケース(1)を辿る場合は、ステップＳ９における判断と同様に、今回と前回とで差異が生じたプレフィックスのみを処理対象としてよい。すなわち、今回ケース(1)を辿るプレフィックスiのうち、前回はケース(2)又は(3)を辿り今回新たにケース(1)を辿ることとなったものについてのみ、ステップＳ７及びＳ８を実行するようにし、前回も同じくケース(1)を辿ったものは既にルータＡ〜Ｃの経路表から削除される等しているので、ステップＳ７及びＳ８は省略してもよい。
【００３９】
本発明のより簡素な実施例として、ステップＳ８のデフォルトルートの送信を省略してもよい。この場合作成される経路表は、図３の例ならば経路表ＴＡ３〜ＴＣ３から「プレフィックス0.0.0.0/0  次ホップ11.0.0.5」が削除されたものとなり、宛先がプレフィックス192.168.3.0/24,192.168.4.0/24又は192.168.5.0/24に該当するパケットが当該経路表の適用後に現れた場合にはルータＡ〜Ｃにて破棄されることとなる。代わりに利点として、当該プレフィックスに対応する次ホップを定めたネットワーク構成を管理サーバ１又はルータＤを用いて構築する必要はなくなる。
【００４０】
同様に、デフォルトルートは送信するが、データパケットが管理サーバ１又はルータＤに転送された後の到達可能性は保証しないようにしてもよい。いずれの場合も、削除対象は観測パケット数に基づいて決定しているため、統計的に妥当な所定期間に渡って観測しておけば破棄されるデータパケットは少なく、ルータＡ〜Ｃからなる当初のネットワーク構成のままで大多数のデータパケットを正常に転送しつつ経路表を効率的に削減することができる。
【符号の説明】
【００４１】
１…管理サーバ、２…BGP受信部、３…パケット情報受信部、４…頻度集計部、５…メッセージ送信部、１０…BGPルータ
【図１】
0005676408.tif 000002
【図２】
0005676408.tif 000003
【図３】
0005676408.tif 000004
【図４】
0005676408.tif 000005