(57)【要約】【課題】性能を改善し、ハードウェア要件の大幅な節減を実現可能な、ルーティングプロトコルメッセージを計測する手法を提供する。【解決手段】本発明は、ＢＧＰピアからのＢＧＰメッセージを記録する方法を提供する。この方法は、ＢＧＰピアと受動的なリンクを確立するステップと、メッセージが到着した際に、ＢＧＰピアからのすべてのＢＧＰメッセージにタイムスタンプを付加し、該メッセージを記録するステップと、選択されたＢＧＰエラーにわたってＢＧＰピアとのリンクを維持するステップと、を有する。【選択図】図１
2006129478.tif 000002
【特許請求の範囲】
【請求項１】
ＢＧＰピアからのＢＧＰメッセージを記録する方法であって、
ＢＧＰピアと受動的なリンクを確立するステップと、
メッセージが到着した際に、ＢＧＰピアからのすべてのＢＧＰメッセージにタイムスタンプを付加し、該メッセージを記録するステップと、
選択されたＢＧＰエラーにわたってＢＧＰピアとのリンクを維持するステップと、
を有する方法。
【請求項２】
選択されたＢＧＰエラーにわたってＢＧＰピアとのリンクを維持する前記ステップが、ＢＧＰエラーに関連して設定可能である、請求項１記載の方法。
【請求項３】
送出ＢＧＰメッセージにタイムスタンプを付加し、該メッセージを記録する、請求項１記載の方法。
【請求項４】
ＢＧＰピアからのＢＧＰメッセージを記録するための改良型ＢＧＰルートレコーダであって、
ＢＧＰピアとの受動的なリンクを確立する手段と、
ＢＧＰピアからＢＧＰメッセージを受信する手段と、
メッセージが到着した際に、ＢＧＰピアからのすべてのＢＧＰメッセージにタイムスタンプを付加し、該メッセージを記録する手段と、
選択されたＢＧＰエラーにわたってＢＧＰピアとのリンクを維持する手段と、
を有するＢＧＰルートレコーダ。
【請求項５】
ＢＧＰルートレコーダにおいてＢＧＰメッセージトラフィックを処理するための実行可能な命令を含むコンピュータ読取り可能媒体であって、
前記ＢＧＰルートレコーダ及びＢＧＰピア間に受動的なリンクを確立するコードと、
ＢＧＰピアからＢＧＰメッセージを受信するコードと、
メッセージが到着した際に、ＢＧＰピアからのすべてのＢＧＰメッセージにタイムスタンプを付加し、該メッセージを記録するコードと、
選択されたＢＧＰエラーにわたってＢＧＰピアとのリンクを維持するコードと、
を有するコンピュータ読取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明による実施例は、一般に、パケット交換ネットワークに関し、更に詳しくは、インターネットプロトコル（Internet Protocol、ＩＰ）交換ネットワークにおける境界ゲートウェイプロトコル（Border Gateway Protocol、ＢＧＰ）ルーティングプロトコルメッセージ（routing protocol message）の収集と記録に関するものである。
【背景技術】
【０００２】
パケット交換デジタルネットワークは、インターネットのバックボーンである。パケット交換ＩＰネットワークにおいては、発信元から宛先に向かって流れるデジタル情報は、一連のパケットに分割される。そして、これらのパケットは、多数のルーター及びスイッチを通じてネットワーク内をルーティングされるが、パケットが同一のルートを辿るという保証は存在しない。ルーティング（並びに、ルート管理）は、パケットが辿るルートを制御し、それらのルートが、ローディング（loading）や障害（failure）などのネットワークの状態に対して、どのように変化、適合、及び応答するかを制御する。
【０００３】
パケットのトラフィックは、ルーター間において交換される。ルーターとは、データパケットをその宛先に転送するべくハードウェアとソフトウェアを組み合わせたコンピュータネットワーク装置である。ルーターは、その他のルーターに対して接続されるが、ＢＧＰを使用する場合には、これらのルーターをピア（Peer）と呼ぶ。この初期ピアリング（initial peering）は、一般に、手動設定によって確立される。それぞれのルーターは、ネットワークの到達可能性を表すネットワーク又はプリフィックス（prefix）のテーブルを維持管理している。そして、ピアリングされているルーターは、ＲＦＣ１７７１に規定されているＢＧＰに従ってメッセージを交換することによって、これらのテーブルを管理している。
【０００４】
ルート管理は、インターネットコミュニティにおける積極的な研究領域であり、且つ、ネットワークサービスプロバイダ（Network Service Provider、ＮＳＰ）にとっても、関心のある領域である。ルーティングを監視及び管理することにより、従来のネットワーク要素及びサービス監視によっては見逃されていた問題を追跡すると共に、ピアリングを評価する際に有用な情報を収集することができる。ルーティング情報の管理は、境界ゲートウェイルーティングプロトコル（Border Gateway Routing Protocol）に関係しているため、有意なルーティング管理を実施するには、ピアルーターから個々のルーティング更新情報を収集する必要がある。
【０００５】
ルーティング情報を記録するソフトウェアツールは、少なくとも２つの供給源から入手可能である。第１のものは、Zebra又はQuaggaであり、これは、機能を完備したルーティングプロトコルスイートであって、ルーティング更新情報を記録する能力をも具備している。そして、ミシガン大学のＭＲＴパッケージの一部であるMrtdも、ルーティング更新情報を記録する能力を有している。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、これらのツールは、いずれも、ネットワークの計測手段として使用した場合に、問題を有している。即ち、第１に、これらは、単にルートを記録するのに必要とされるものをはるかに上回る内容を実行するべく構築されている。従って、両ツールは、完全なＢＧＰルーティング機能を実行する能力を有しており、基本的に、この付加されている処理に起因して、十分なスケーラビリティを有していない。そして、第２の問題点として、これらのツールの動作により、これらのツールが記録するべく試みる計測が妨げられることになる。即ち、これらのツールは、いずれも、ピアからエラーを受信した際に、ＢＧＰの仕様に準拠して、ＢＧＰピアリングセッションを破壊するのである。
【課題を解決するための手段】
【０００７】
本発明によれば、ＢＧＰルートレコーダ（BGP Route Recorder、ＢＲＲ）は、すべての到来及び送出ＢＧＰメッセージを記録し、タイムスタンプを付加する。複数のエラーにわたってピアリングセッションを維持可能であり、ＢＲＲに許容されているのは、ピアリングセッションの初期化の際に受動的にリスン（listen）することのみである。
【発明を実施するための最良の形態】
【０００８】
本発明は、添付の図面との関連で、以下の本発明による実施例に関する詳細な説明を参照することにより、十分に理解することができよう。
【０００９】
本発明は、パケット交換ＩＰネットワークにおけるＢＧＰメッセージの記録に関するものである。尚、以下の説明は、当業者が本発明を実施及び使用できるようにするべく提示するものであり、特許出願及びその要件の観点において提供されている。当業者には、本明細書に開示される実施例に対する様々な変更が容易に明らかであり、本明細書の一般的な原理は、その他の実施例にも適用可能である。従って、本発明は、開示されている実施例に限定されるものではなく、本発明には、添付の請求項及び本明細書に記述されている原理及び特徴と一致する最も広範な範囲の付与を要するものである。
【００１０】
ＢＧＰルーターの動作については、ＲＦＣ１７７１に定義されている。尚、ＲＦＣ１７７１の現在の改訂版は、１９９５年３月に公表されたＢＧＰ−４であり（この内容は、本引用によって本明細書に包含される）、以下、これをＲＦＣ１７７１と呼ぶこととする。
【００１１】
このＲＦＣ１７７１によれば、２つのピアが、互いの間において接続を形成する。これらは、ＢＧＰメッセージを交換することによって、その間の接続をオープンし、パラメータを確認する。個々のルーター設定に応じて、初期データフローは、完全な（entire）ＢＧＰルーティングテーブルである。そして、追加的な更新情報が、ルーティングテーブル変更情報として、定期的に送信されることになる。ＢＧＰは、完全なＢＧＰルーティングテーブルの定期的なリフレッシュを必要としていない。従って、ＢＧＰシステムは、それぞれのピアから送信されるすべてのＢＧＰルーティングテーブルの総合的なビューを保持すると共に、接続の持続時間にわたるそれぞれのピアからのテーブルバージョン番号を追跡しなければならない。接続を存続させるべく、キープアライブ（KeepAlive）メッセージが定期的に送信される。又、エラーや特殊な状態に応答して、ノティフィケーション（Notification）メッセージが送信される。そして、接続がエラー状態になった場合には、ノティフィケーションメッセージが送信され、その接続はクローズされることになる。
【００１２】
尚、ＲＦＣ１７７１によれば、接続がエラー状態になると、ピア間の接続がクローズされることに留意されたい。そして、ＲＦＣ１７７１によれば、接続が、最初にオープンされる際、又は、エラーから回復して再オープンされる際には、そのピア用の完全なＢＧＰルーティングテーブルが送信されることになる。このようなエラーには、キープアライブメッセージに対するタイムリーな応答の欠如、メッセージヘッダエラー（タイプ１）、アップデートエラー（タイプ３）、ホールドタイマ満了エラー（タイプ４）、及び有限状態機械エラー（タイプ５）が含まれる。
【００１３】
ZebraやMrtdなどの既存のルーティングスイートは、ＢＧＰトラフィックの一部を記録する能力を具備しているが、すべてを記録する能力は具備してはいない。そして、この記録能力は、全ＢＧＰルーティング機能を具備する既存のプログラム上に追加されたものであるため、記録されたＢＧＰトラフィックには、これらによって雑音とエラーが混入することになる。
【００１４】
本発明の実施例は、ピアからのすべてのＢＧＰメッセージを記録するＢＧＰルートレコーダ（BGP Route Recorder、ＢＲＲ）を提供するものである。この本発明によるＢＲＲは、ＢＧＰ更新情報に基づいたものはなく、ピアリングされているシステムからのＢＧＰメッセージと、それ自体のキープアライブ、ノティフィケーション、及びクローズメッセージを記録する。特に重要な点は、このＢＲＲの場合には、自身が送信するはずのノティフィケーションメッセージを記録するが、そのノティフィケーションメッセージを実際には送信しないという点である。このノティフィケーションメッセージには、エラーが発生した理由が含まれている。従って、例えば、アップデートエラーを受信した際のＢＲＲの動作は、受信されたオリジナルのアップデートメッセージを記録すると共に、そのエラーに応じた正しいタイプ（この場合には、タイプ３）のノティフィケーションメッセージを記録することであり、ＢＲＲは、ノティフィケーションを送信したり、セッションを破壊したりはしない。そして、エスケープを伴わないエラー状態の連続した再発は危険な状態であるため、この動作は設定可能である。従って、一実施例においては、ノティフィケーションメッセージが実際に送信されてセッションが破壊される前にエラーを受信可能な回数をユーザーが設定可能である。
【００１５】
本発明の一実施例においては、可能な限り早期に（好ましくは、ネットワーク通信スタックのソケットレベルにおいて）、ＢＧＰメッセージに対してタイムスタンプが付加される。ZebraやMrtdなどのシステムの場合には、タイムスタンプの付加は、メッセージをディスクに書き込む時点において実行され、これは、受信から何分もが経過した後のことである。
【００１６】
ZebraやMrtdなどのシステムの主な機能は、ルーターとしてのものであり、ＢＧＰの記録は付加的な機能である。従って、ルーティング動作及びルーティングトラフィックが、システム能力の大きな部分を占有している場合には、ＢＧＰメッセージが記録されない場合がある。実際に、ZebraやMrtdなどのシステムに伴う周知の問題点は、高負荷状態において、これらが、ピアとの間のＢＧＰ キープアライブメッセージの生成に失敗し、この結果、そのピアとのセッションがリセットされ、破壊されてしまうということである。この場合、セッションは、自動的に再確立され、そのピア用の完全なテーブルが再送信されることになるが、この結果、ＢＧＰプロトコルの動作を計測するべく試みる際に雑音が混入するだけでなく、セッションをリセットすると共に個々に完全なルーティング更新情報を受信することによって記録装置の負荷（load）が増大し、多数の障害が発生することにもなる。又、現在の方法は、全ルーティングスイートを実装するプログラムを使用しているため、これらのプログラムは、受信するそれぞれのルートごとにルーティングを維持し判定しなければならない。一方、本発明の実装は、タイムスタンプを付加し、ルーティングメッセージを記録するのみであって、ルーティングアルゴリズムを使用したり、ルーティングテーブルを維持する必要がない特化型の（purpose built）計測手段を提供しており、この結果、大幅な性能の改善と、ハードウェア要件の大幅な節減を実現可能である。又、ZebraやMrtdなどのルーターにおいては、誤ったメッセージを受信したり、そのピアに対してエラーを報告した場合に、これらのＢＧＰメッセージは、記録されないか、或いは、ヌル（null）フィールドとして記録されることになる。このように、メッセージ（特に、エラーを通知したり結果的にエラーをもたらすもの）を記録しないという点は、計測装置と計測にとって致命的である。一方、本発明によるＢＲＲの場合には、エラーについて通知したり、結果的にエラーをもたらすものを含むすべてのＢＧＰメッセージを取得する。
【００１７】
ＲＦＣ１７７１によれば、サイトは、起動する際に、すべての設定されているピアとの間のＢＧＰセッションをオープンするべく試みる。そして、それぞれのセッションがオープンすると、ピア間において、ＢＧＰルーティングテーブルが交換される。従って、多数のピアが存在する場合には、これは、大量のトラフィックとなる。一方、本発明によるＢＲＲの動作は、ＲＦＣ１７７１に規定されているものを逸脱している。即ち、本発明によるＢＲＲは、受動モードにおいて起動し、トラフィックをリスン（listen）して記録するが、ピアがＢＧＰセッションをオープンするまで待機する。
【００１８】
図１は、本発明の実施例において使用するのに適した有限状態機械（finite state machine）を示している。動作の際には、それぞれのピアリングされている接続ごとに、状態機械の１つのインスタンス（instance）が存在している。
【００１９】
１つのピアリングされた接続を表している状態機械のそれぞれのインスタンスには、現在の状態が関連付けられている。そして、すべての状態機械は、アイドル状態１から始まることになる。図１に示されている有限状態機械は、次の６つの状態を具備している。
【００２０】
１．アイドル（Idle）
２．コネクト（Connect）（未使用）
３．アクティブ（Active）
４．オープンセント（OpenSent）
５．オープンコンファーム（OpenConfirm）
６．エスタブリッシュド（Established）
【００２１】
尚、図１には、記録セッションの終了時のイグジット（Exit）処理が、参照符号７として示されている。それぞれの状態と関連付けられているのは、イベントと遷移テーブルの組である。この図１に示されている有限状態機械に適した状態、イベント、及び遷移テーブルの組が、付属書１として添付されている。尚、状態及びイベントは、ＲＦＣ１７７１に記述されているものと同一であるが、本発明において使用される遷移テーブルは、ＲＦＣにおけるものとは異なっていることに留意されたい。
【００２２】
図１の有限状態機械と関連するイベントの組は、次のとおりである。
【００２３】
１．ＢＧＰスタート
２．ＢＧＰストップ
３．ＢＧＰ転送接続オープン
４．ＢＧＰ転送接続クローズ
５．ＢＧＰ転送接続オープン失敗
６．ＢＧＰ転送決定的エラー（fatal error）
７．コネクションリトライ（ConnectionRetry）タイマ満了（expired）
８．ホールド（Hold）タイマ満了
９．キープアライブ（KeepAlive）タイマ満了
１０．オープン（Open）メッセージ受信
１１．キープアライブ（KeepAlive）メッセージ受信
１２．アップデート（Update）メッセージ受信
１３．ノティフィケーション（Notification）メッセージ受信
【００２４】
それぞれの状態ごとに、付属書１の関連遷移テーブルは、どのイベントがどの状態に遷移するかを規定しており、イベントが処理された際に発生するその他の処理の詳細についても記述している。すべての到来（incoming）及び送出（outgoing）ＢＧＰメッセージは、ノティフィケーションとして記録される。通常の有限状態機械の実装と同様に、すべての状態においてすべてのイベントが許容されているわけではない。ＲＦＣ１７７１に準拠するルーターにおいては、エラー及び／又は禁止された遷移の場合には、結果的に、ＢＧＰピアリングセッションが終了することになる。本発明によるＢＲＲの場合には、このようなエラーが記録される。そして、本発明によるＢＲＲの場合には、エラーが発生した場合に、ＢＧＰピアとのリンクを維持するべく設定可能である。
【００２５】
すべてのピアリングされている接続（並びに、従って、それぞれのピアリングされている接続用の状態機械）は、アイドル状態１から始まることになる。そして、ＢＧＰスタートイベントにより、状態機械は、アクティブ状態３に遷移する。一方、その他のイベントの場合には、状態機械は、アイドル状態１に留まることになる。
【００２６】
コネクト状態２は、本発明によるＢＲＲは使用しないが、ＲＦＣ１７７１に準拠するＢＧＰルーターが使用する。
【００２７】
アクティブ状態３においては、ＢＧＰスタートイベントを受信した場合には、アクティブ状態３に留まることになる。ＢＧＰストップイベントを受信した場合には、アイドル状態１に遷移する。ＢＧＰ転送接続オープンイベントを受信した場合には、オープンプロセスが始まり、オープンセント状態４に遷移する。ＢＧＰ転送接続オープン失敗イベントを受信した場合には、アクティブ状態３に留まる。そして、その他のすべてのイベントの場合には、アイドル状態１に遷移することになる。
【００２８】
オープンセント状態４は、全ＢＧＰピアリングセッションの確立プロセスにおける次の部分である。ＢＧＰスタートイベントを受信した場合には、オープンセント状態４に留まることになる。ＢＧＰストップイベントを受信した場合には、ノティフィケーションとクリーンナップの後に、アイドル状態１に遷移する。ＢＧＰ転送接続クローズ、ＢＧＰ転送接続オープン失敗、又はＢＧＰ転送決定的エラーイベントを受信した場合には、アクティブ状態３に遷移する。ホールド又はキープアライブタイマ満了イベントを受信した場合には、オープンセント状態４に留まる。オープンイベントを受信した場合には、オープンコンファーム状態５に遷移し、オープン及びキープアライブメッセージを送信し、キープアライブ及びホールドタイマを起動するか、或いは、エラー通知の後に、アイドル状態１に遷移することになる。そして、その他のイベントを受信した場合には、ノティフィケーションを生成し、アイドル状態１に遷移する。
【００２９】
オープンコンファーム状態５においては、ＢＧＰピアリングセッションの処理を継続する。ＢＧＰスタート、ホールドタイマ満了、キープアライブタイマ満了、又はアップデートイベントを受信した場合には、付属書１に示されている付加的な動作と共に、オープンコンファーム状態５に留まることになる。ＢＧＰストップを受信した場合には、示されている通知（ノティフィケーション）及びクリーンナップ動作を実行し、アイドル状態１に遷移する。Holdタイマ満了イベントを受信した場合には、通知し、holdタイマを起動して、オープンコンファーム状態５に留まる。キープアライブタイマ満了イベントを受信した場合には、キープアライブタイマを再起動して、キープアライブメッセージをＢＧＰピアに送信し、オープンコンファーム状態５に留まる。キープアライブイベントを受信した場合には、Holdタイマを再起動し、エスタブリッシュド状態６に遷移することになる。
【００３０】
エスタブリッシュド状態６は、確立されたＢＧＰピアリングセッションを表している。ＢＧＰストップ又はノティフィケーションイベントを受信した場合には、通知、クリーンナップ、及びアイドル状態１への遷移が実行される。そして、その他のイベントを受信した場合には、示されている処理と共に、エスタブリッシュド状態６に留まることになる。
【００３１】
本発明の以上の詳細な説明は、例示を目的として提供されているものであって、そのすべてを網羅することを意図するものではなく、且つ、開示された実施例そのままに本発明を限定するものでもない。従って、本発明の範囲は、添付の請求項に定義されているとおりである。
【００３２】
（付属書１）
ＢＧＰルートレコーダの有限状態機械（finite state machine、ＦＳＭ）の状態遷移及び動作
【００３３】
本付属書は、ＢＧＰイベントに応答したＢＧＰのＦＳＭの状態間における遷移について記述するものである。以下は、取り決められた「ホールドタイム（Hold Time）」値が非ゼロの場合のこれらの状態及びイベントのリストである。
【００３４】
（ＢＧＰ状態）
１．アイドル
２．コネクト（未使用）
３．アクティブ
４．オープンセント
５．オープンコンファーム
６．エスタブリッシュド
【００３５】
（ＢＧＰイベント）
１．ＢＧＰスタート
２．ＢＧＰストップ
３．ＢＧＰ転送接続オープン
４．ＢＧＰ転送接続クローズ
５．ＢＧＰ転送接続オープン失敗
６．ＢＧＰ転送決定的エラー
７．コネクションリトライタイマ満了
８．ホールドタイマ満了
９．キープアライブタイマ満了
１０．オープンメッセージ受信
１１．キープアライブメッセージ受信
１２．アップデートメッセージ受信
１３．ノティフィケーションメッセージ受信
【００３６】
以下のテーブルは、ＢＧＰのＦＳＭの状態遷移と、これらの遷移によってトリガされる動作について記述するものである。
【００３７】
【表１】
2006129478.tif 000003
【００３８】
コネクト（２）
この状態は使用されない。
【００３９】
【表２】
2006129478.tif 000004
【００４０】
【表３】
2006129478.tif 000005
【００４１】
【表４】
2006129478.tif 000006
【００４２】
【表５】
2006129478.tif 000007
【図面の簡単な説明】
【００４３】
【図１】本発明の実施例において使用する有限状態機械を示している。
【図１】
2006129478.tif 000008