(57)【特許請求の範囲】
【請求項１】
複数のルータのうちの１つのルータのルーティングテーブルを更新する際に使用する方法であって、前記ルーティングテーブルが、少なくとも１つの宛先用に使用されるルートを備え、ルーティング情報を伴う更新メッセージが、前記複数のルータ、典型的にはＢＧＰルータ間で送信され、ルータで下記のステップ、すなわち、
宛先への経路、または経路の取消しを含む更新メッセージを受信するステップと、
（取り消された）経路が経路探索イベントに関連するかどうか判定するステップと、
判定の結果を考慮に入れてルーティングテーブルの更新を決定するステップとが実施され、ルータにおいて、さらに次のステップ、すなわち、
判定の結果を考慮に入れて、他のルータに送る更新メッセージに含めるルーティング情報を決定するステップが実施される、方法。
【請求項２】
判定ステップが、発生確率信号モデルを使用する、請求項１に記載の方法。
【請求項３】
判定ステップが、隠れマルコフモデル（ＨＭＭ）を使用する、請求項２に記載の方法。
【請求項４】
経路探索イベントが、いくつかの非最適な過渡的経路に関連付けられ、過渡的経路の最長の連続経路系列が識別され、ルーティングテーブルの更新の決定が、更新メッセージに含まれた経路を選択すべきかどうか判定するために前記識別された系列をも考慮に入れる、請求項１に記載の方法。
【請求項５】
更新メッセージが新しい経路を広告し、新しい経路が経路探索イベントに関連すると判定される場合、決定ステップが、新しい経路をルーティングテーブルに含めないステップを備える、請求項１に記載の方法。
【請求項６】
決定ステップが、他のルータに送る更新メッセージ内に新しい経路を含めないステップを備える、請求項１または５に記載の方法。
【請求項７】
モデルが、複数の通信チャネルをモデル化するために複数の状態を使用し、前記複数の通信チャネルが、宛先用に使用される経路を選択するのに使用される出力を有し、受信された更新メッセージ、およびルーティングテーブル内の情報が、状態に関する確率論的データを提供するために使用される、請求項２に記載の方法。
【請求項８】
ルータが、いくつかのピアと、
インバウンド更新メッセージからのルーティング情報を格納するＡｄｊ−ＲＩＢｓ−Ｉｎ部分、
ルーティングテーブル、すなわち選択されたルートを格納するＬｏｃ−ＲＩＢ部分、および
そのＢＧＰピアに送る更新メッセージに含めるルーティング情報を格納するＡｄｊ−ＲＩＢｓ−Ｏｕｔ部分
を備えるルーティング情報ベースとを有するＢＧＰルータであり、
受信された更新メッセージの経路系列が、Ａｄｊ−ＲＩＢｓ−Ｉｎ部分に格納され、
Ｌｏｃ−ＲＩＢ部分およびＡｄｊ−ＲＩＢｓ−Ｏｕｔ部分が、この判定の結果を考慮に入れて更新される、請求項１に記載の方法。
【請求項９】
ＨＭＭが、
１≦ｉ≦Ｎとして、少なくとも４つの隠れ状態Ｓｉの数Ｎであって、そのグループが経路探索イベントに関連するルータの上流のルータのグループのルーティング状態を特徴付ける隠れ状態の数Ｎと、
隠れ状態ごとの観測シンボルＯの数Ｍであって、前記観測シンボルが、更新メッセージで受信された経路系列に対応する観測シンボルＯの数Ｍと、
１≦ｉ、ｊ≦Ｎとして、状態遷移確率分布ａｉｊ＝Ｐ（ｑｊ，ｔ＋１｜ｑｉ，ｔ）であって、
Ｐ（ｑｊ，ｔ＋１｜ｑｉ，ｔ）が、時間ｔ＋１のときの実際の状態がＳｊに等しく、また時間ｔのときの直前の実際の状態が時間ｔのときにＳｉであった確率である、状態遷移確率分布と、
１≦ｊ≦Ｎとして、状態ｊにおける観測確率分布、ｂｊ（Ｏ）＝Ｐ（Ｏｔ｜ｑｊ，ｔ）であって、Ｐ（Ｏｔ｜ｑｊ，ｔ）が、時間ｔのときの観測Ｏを時間ｔのときの実際の状態ｑｊで出力する確率である、状態ｊにおける観測確率分布と、
１≦ｉ≦Ｎとして、初期状態分布πｉ＝Ｐ（ｑｉ，ｌ）であって、Ｐ（ｑｉ，ｌ）が、初期状態Ｓｉを有する確率である、初期状態分布とを使用する、請求項３に記載の方法。
【請求項１０】
状態の数が、
経路に変更がないことを示す第１の状態Ｓ１と、
再初期化を示す第２の状態Ｓ２と、
経路の長さの増加を示す第３の状態Ｓ３と、
経路探索イベントの存在を示す第４の状態Ｓ４と、
任意選択で、経路探索イベントにつながらない経路の取消しを示す第５の状態とを備える、請求項９に記載の方法。
【請求項１１】
更新メッセージが、いくつかの経路属性および／または経路の取消しを含む経路の告知を備えることができ、観測シンボルが、
経路または経路属性に変更がない宛先の告知Ａと、
経路長が増加する経路を有する宛先の告知Ａ＋と、
同じ経路であるが、異なる経路属性を有する宛先の告知Ａ＊と、
同じ長さの異なる経路を有する宛先の告知Ａ０と、
所与の宛先への経路Ａの取消しＷ（Ａ）とを備える、請求項９に記載の方法。
【請求項１２】
少なくとも１つの宛先用に使用されるルートを備えるルーティングテーブルを有するルータ、典型的にはＢＧＰルータであって、ルーティング情報を伴う更新メッセージを送受信するように構成され、
宛先について経路または経路の取消しを含む更新メッセージを受信する受信手段と、
（取り消された）経路が経路探索イベントに関連するかどうか判定する判定手段（１３）と、
判定手段と通信しており、判定の結果を考慮に入れてルーティングテーブルの更新を決定する決定手段（１６）とを備え、
ルータは、ルーティングテーブル（Ｌｏｃ−ＲＩＢ）がＲＩＢの一部であり、ＲＩＢが、宛先について受信された（取り消された）経路を格納するためのＡｄｊ−ＲＩＢ−Ｉｎと、Ａｄｊ−ＲＩＢ−Ｏｕｔとをさらに備え、
決定手段が、新しい経路または取消しが経路探索イベントに関連する場合は、新しい経路または経路の取消しをＬｏｃ−ＲＩＢおよびＡｄｊ−ＲＩＢ−Ｏｕｔに格納しないように構成される、ルータ。
【請求項１３】
判定手段が、確率論的モデリング手段を備える、請求項１２に記載のルータ。
【請求項１４】
判定手段が、請求項９から１１のいずれかに記載の方法に従って機能するように構成されたＨＭＭモデリング手段を備える、請求項１２に記載のルータ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルーティングシステム収束の向上のために複数のルータのうちの１つのルータのルーティングテーブルを更新する際に使用する方法に関する。本発明は、ルータ、典型的にはＢＧＰルータにも関する。
【背景技術】
【０００２】
経路探索は、どんな経路ベクトルルーティングプロトコルにも関連する固有の現象である。その悪影響を定量化し、緩和するために、過去１０年間、多くの努力が払われてきた。基本的には、その影響を緩和する手法には３つの種類がある：
−  知らされたＡＳ経路選択を実施し、またはＡＳ経路に追加の「経路依存性」情報で注釈を付けるための根本原因通知
−  収束を固定するためのＭＲＡＩ時間の短縮：しかしながら、ＭＲＡＩをある閾値より下に減少させると、収束時間およびＢＧＰ更新数の面で逆の効果が生じることになり、したがって経路探索現象が悪化する。
−  バックアップ／マルチＡＳ経路（ＡＳ経路多様性の増加）：この解決策は、管理されるＲＩＢ状態の数に影響を及ぼし、したがって、ルーティングスケーラビリティに対して逆の効果がもたらされる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】ＲＦＣ４２７１（ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ４２７１）
【非特許文献２】Ｒ．Ｒａｂｉｎｅｒ、「Ａ  Ｔｕｔｏｒｉａｌ  ｏｎ  Ｈｉｄｄｅｎ  Ｍａｒｋｏｖ  Ｍｏｄｅｌｓ  ａｎｄ  Ｓｅｌｅｃｔｅｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｉｎ  Ｓｐｅｅｃｈ  Ｒｅｃｏｇｎｉｔｉｏｎ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＩＥＥＥ、７７巻、２号、１９８９年２月
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の目的は、ルーティング収束時間を信頼できるやり方で減少させることを可能にする方法およびシステムを提供することである。
【課題を解決するための手段】
【０００５】
本発明の一実施形態によれば、複数のルータのうちの１つのルータのルーティングテーブルを更新する際に使用する方法が提供され、前記ルーティングテーブルが、少なくとも１つの宛先用に使用されるルートを備え、ルータで下記のステップが実施される：
−  宛先への経路、または経路の取消しを含む更新メッセージを受信するステップと、
−  （取り消された）経路が経路探索イベントに関連するかどうか判定するステップと、
−  判定の結果を考慮に入れてルーティングテーブルの更新を決定するステップ。
【０００６】
探索過程の一部である、受信された更新メッセージが新しい経路または経路の取消しを含むかどうか検出すること、およびこの検出に応じて決定過程を行うことによって、収束時間が確実に減少され得る。
【０００７】
本出願では、経路探索は、典型的には宛先が最初に広告されるとき、またはネットワーク内で宛先が取消しされるときに生じる現象として定義されてよい。これは、ノードトポロジに亘って様々な伝播／処理遅延が生じて、その結果、次に最適な経路が選択されるまで過渡的な経路の次善の選択が行われることに起因する。取消しの場合、宛先への経路がもはや存在しないことが起こり得ることに留意されたい。
【０００８】
本発明の一実施形態によれば、（ＡＳ経路系列の系列としてモデル化された）ＢＧＰ更新系列内で経路探索現象を検出し、ＢＧＰ収束時間に対する経路探索の悪影響を取り除くためにＢＧＰ選択処理を加速するための技法が提供される。
【０００９】
好ましい一実施形態によれば、経路探索イベントは、いくつかの非最適な過渡的な経路に関連し、過渡的な経路の最長の連続経路系列が識別される。次いで、ルーティングテーブルの更新の決定は、更新メッセージに含まれた経路を選択すべきかどうか判定するために前記識別された系列をも考慮に入れる。
【００１０】
好ましい一実施形態によれば、更新メッセージが新しい経路を広告し、新しい経路が経路探索イベントに関連すると判定される場合、決定ステップは、新しい経路をルーティングテーブルに含めないステップを備える。さらに、この方法は好ましくは、判定の結果を考慮に入れて、他のルータに送られる更新メッセージに含めるルーティング情報を決定するステップをも備え、新しい経路が経路探索イベントに関連すると判定される場合は、新しい経路を、他のルータに送られる更新メッセージに含めない。
【００１１】
好ましい一実施形態によれば、判定ステップは、発生確率信号モデル、好ましくは隠れマルコフモデル（ＨＭＭ：Ｈｉｄｄｅｎ  Ｍａｒｋｏｖ  Ｍｏｄｅｌ）を使用する。発生確率モデルは、観測の活用を可能にするという利点を有し、この場合では、観測は、更新メッセージから導出された情報など、トポロジ情報を備える。条件付き確率場（ＣＲＦ：Ｃｏｎｄｉｔｉｏｎａｌ  Ｒａｎｄｏｍ  Ｆｉｅｌｄ）と名付けられたＨＭＭ識別の等価物も使用されてよいことに留意されたい。しかしながら、通常ＣＲＦは、ラベルなしのデータを組み込むことは容易ではないのでそれほど適したモデルではなく、また典型的には、ＣＲＦが良好な性能精度を達成するには多くの訓練データが必要である。
【００１２】
本発明のさらに進展した実施形態によれば、このモデルは、複数の通信チャネルをモデル化するために複数の状態を使用し、前記複数の通信チャネルが、宛先用に使用される経路を選択するのに使用される出力を有し、受信された更新メッセージ、およびルーティングテーブル内の情報が、状態に関する確率論的データを提供するために使用される。ＨＭＭモデルが使用される場合、ＨＭＭは好ましくは、下記を備える：
−  １≦ｉ≦Ｎとして、好ましくは少なくとも４つの隠れ状態Ｓｉの数Ｎであって、そのグループが経路探索イベントに関連するルータの上流のルータのグループのルーティング状態を特徴付ける隠れ状態の数Ｎと、
−  隠れ状態ごとの観測シンボルＯの数Ｍであって、前記観測シンボルが、更新メッセージで受信された経路系列に対応する、観測シンボルＯの数Ｍと、
−  １≦ｉ、ｊ≦Ｎとして、状態遷移確率分布ａｉｊ＝Ｐ（ｑｊ，ｔ＋１｜ｑｉ，ｔ）であって、Ｐ（ｑｊ，ｔ＋１｜ｑｉ，ｔ）が、時間ｔ＋１のときの実際の状態がＳｊに等しく、また時間ｔのときの直前の実際の状態が時間ｔのときにＳｉであった確率である、状態遷移確率分布と、
−  １≦ｊ≦Ｎとして、状態ｊにおける観測確率分布、ｂｊ（Ｏ）＝Ｐ（Ｏｔ｜ｑｊ，ｔ）であって、Ｐ（Ｏｔ｜ｑｊ，ｔ）が、時間ｔのときの観測Ｏを時間ｔのときの実際の状態ｑｊで出力する確率である、状態ｊにおける観測確率分布と、
−  １≦ｉ≦Ｎとして、初期状態分布πｉ＝Ｐ（ｑｉ，ｌ）であって、Ｐ（ｑｉ，ｌ）が、初期状態Ｓｉを有する確率である、初期状態分布。
使用される状態の数は典型的には、４または５である。可能な状態および観測シンボルについては、下記の詳細な図の説明においてさらに述べられる。
【００１３】
ルータが、いくつかのピアおよびルーティング情報ベース（ＲＩＢ）を有するＢＧＰルータである場合には、このＲＩＢは典型的に：
−  インバウンド更新メッセージからのルーティング情報を格納するＡｄｊ−ＲＩＢ−Ｉｎ部分と、
−  ルーティングテーブル、すなわち選択されたルートを格納するＬｏｃ−ＲＩＢ部分と、
−  そのＢＧＰピアに送られる更新メッセージに含められるルーティング情報を格納するＡｄｊ−ＲＩＢｓ−Ｏｕｔ部分とを備え、
受信された更新メッセージの経路系列が、Ａｄｊ−ＲＩＢｓ−Ｉｎ部分に格納され、
Ｌｏｃ−ＲＩＢ部分およびＡｄｊ−ＲＩＢｓ−Ｏｕｔ部分が、この判定の結果を考慮に入れて更新される。
【００１４】
さらに、本発明は、少なくとも１つの宛先用に使用されるルートを備えるルーティングテーブルを有するルータ、典型的にはＢＧＰルータに関し、このルータは、ルーティング情報を伴う更新メッセージを送受信するように構成され：
−  宛先について経路または経路の取消しを含む更新メッセージを受信する受信手段と、
−  （取り消された）経路が経路探索イベントに関連するかどうか判定する判定手段と、
−  判定手段と通信しており、判定の結果を考慮に入れてルーティングテーブルの更新を決定する決定手段とを備える。
【００１５】
好ましい一実施形態によれば、判定手段は、使用されるモデルの上記に開示された諸実施形態のいずれかに従って機能するように構成された確率論的モデリング手段、好ましくはＨＭＭモデリング手段を備える。
【００１６】
さらに進展した実施形態によれば、ルータはＢＧＰルータであり、ルーティングテーブル（Ｌｏｃ−ＲＩＢ）はＲＩＢの一部であり、ＲＩＢは、宛先について受信された、告知された（取消しされた）経路を格納するためのＡｄｊ−ＲＩＢ−Ｉｎと、Ａｄｊ−ＲＩＢ−Ｏｕｔとをさらに備え、決定手段が、新しい経路または取消しが経路探索イベントに関連する場合は、新しい経路または経路の取消しをＬｏｃ−ＲＩＢおよびＡｄｊ−ＲＩＢ−Ｏｕｔに格納しないように構成される。
【００１７】
添付の図面は、本発明の現在好まれている非限定的な例示的実施形態を示すために用いられている。本発明の上記およびその他の利点または特徴および目的は、添付の図面と併せ読めば下記の詳細な説明からより明らかになり、本発明についてよりよく理解されよう。
【図面の簡単な説明】
【００１８】
【図１Ａ】従来技術のルーティングシステムの経路探索を示すトポロジグラフである。
【図１Ｂ】従来技術のルーティングシステムの経路探索を示すトポロジグラフである。
【図１Ｃ】従来技術のルーティングシステムの経路探索を示すトポロジグラフである。
【図２】図１Ａ−図１Ｃの例について、従来技術の方法を使用する場合のルーティング情報ベース（ＲＩＢ）の内容を示す。
【図３】図１Ａ−図１Ｃの例について、本発明の方法の一実施形態を使用する場合のルーティング情報ベース（ＲＩＢ）の内容を示す。
【図４Ａ】図４Ａに示された第２の例示的なトポロジを有するネットワーク上に適用された本発明の方法の一実施形態を示す。
【図４Ｂ】図４Ａに示された第２の例示的なトポロジを有するネットワーク上に適用された本発明の方法の一実施形態を示す。
【図４Ｃ】図４Ａに示された第２の例示的なトポロジを有するネットワーク上に適用された本発明の方法の一実施形態を示す。
【図５】経路探索イベントの検出に使用されたＨＭＭの一実施形態を示す。
【図６】本発明のルータの一実施形態の概略図である。
【発明を実施するための形態】
【００１９】
本発明の現在好ましい実施形態によれば、境界ゲートウェイプロトコル（ＢＧＰ：Ｂｏｒｄｅｒ  Ｇａｔｅｗａｙ  Ｐｒｏｔｏｃｏｌ）が、ルータ内のルーティング情報を更新するために使用される。ＢＧＰは、引用により本明細書に組み込まれるコメント要求（ＲＦＣ：Ｒｅｑｕｅｓｔ  ｆｏｒ  Ｃｏｍｍｅｎｔｓ）４２７１（ｈｔｔｐ：／／ｗｗｗ．ｉｅｔｆ．ｏｒｇ／ｒｆｃ／ｒｆｃ４２７１）に記載されている。ＢＧＰは、自律システム（ＡＳ：Ａｕｔｏｎｏｍｏｕｓ  Ｓｙｓｔｅｍ）間のネットワーク到達可能性を指定するＩＰネットワークまたはプレフィックスのテーブルを管理するインターネットのルーティングプロトコルである。ＢＧＰは、インターネットドメイン間／ＡＳ間ルーティングプロトコルである。ルートは、宛先の集合を、これらの宛先への経路の属性と対にする情報の単位として定義される。ルート（ネットワーク到達可能性情報）は、ＵＰＤＡＴＥメッセージで、ＢＧＰルータ間に広告される。このネットワーク到達可能性情報は、到達可能性情報が横断する自律システムのリストについての情報を含む。より具体的には、宛先の集合までの実際の経路は、ＢＧＰ  ＵＰＤＡＴＥメッセージを介して到達可能性情報が横断したＡＳ番号の系列を列挙するＡＳ経路属性で報告される情報である。この情報は、ルーティングループがそこから検出され回避され得るＡＳ接続性のグラフ、すなわちＡＳルーティングトポロジを構築するのに十分である。
【００２０】
ルートは、主としてＡｄｊ−ＲＩＢｓ−Ｉｎ、Ｌｏｃ−ＲＩＢおよびＡｄｊ−ＲＩＢｓ−Ｏｕｔからなるルーティング情報ベース（ＲＩＢ）に格納される。Ａｄｊ−ＲＩＢｓ−Ｉｎは、他のＢＧＰスピーカから受信されたインバウンドＵＰＤＡＴＥメッセージから学習されたルーティング情報を格納する。それらの内容は、決定過程への入力として使用可能なルートを表す。Ｌｏｃ−ＲＩＢは、ＢＧＰスピーカが、そのＡｄｊ−ＲＩＢｓ−Ｉｎに含まれたルーティング情報にルート選択規則およびローカルポリシーを適用することによって選択したローカルルーティング情報を含む。これらは、ローカルＢＧＰスピーカによって使用されるルートである。Ａｄｊ−ＲＩＢ−Ｏｕｔは、ローカルＢＧＰスピーカがそのピアに広告するために選択した情報を格納する。Ａｄｊ−ＲＩＢｓ−Ｏｕｔに格納されたルーティング情報は、ＵＰＤＡＴＥメッセージを介してそのピアに広告される。ＵＰＤＡＴＥメッセージが非空のＷＩＴＨＤＲＡＷＮ  ＲＯＵＴＥＳフィールドを含む場合、このフィールドにその宛先が含まれている以前に広告されたルートは、Ａｄｊ−ＲＩＢ−Ｉｎから取り除かれるものとする。次いで、ＢＧＰスピーカは、以前に広告されたルートがもはや使用可能ではないので、その決定過程を実行する。ＵＰＤＡＴＥメッセージが実現可能なルートを含む場合、Ａｄｊ−ＲＩＢ−Ｉｎは、このルートで更新され、それは、新しいルートがＡｄｊ−ＲＩＢ−Ｉｎにまだ格納されていない場合には、置換または追加であってよい。ＢＧＰスピーカがＡｄｊ−ＲＩＢ−Ｉｎを更新すると、スピーカは、その決定過程を実行するものとし、この決定過程は、ローカルポリシー情報ベース（ＰＩＢ）内のポリシーを、そのＡｄｊ−ＲＩＢｓ−Ｉｎに格納されたルートに適用することによって後続の広告のルートを選択することにある。ピアに広告される選択されたルートは、Ａｄｊ−ＲＩＢｓ−Ｏｕｔに格納される。
【００２１】
換言すると、ＢＧＰは、ＢＧＰ  ＵＰＤＡＴＥメッセージに含まれたＡＳ経路情報を使用して、検出によってループ回避を提供するポリシーベースの最短ＡＳ経路ベクトルルーティングプロトコルである。しかしながら、ＡＳ（またはＡＳ経路）のベクトルのこの交換によって、経路探索現象がもたらされる。この現象は、観測されたＢＧＰ収束時間遅延の根本原因である。
【００２２】
この経路探索現象について、図１Ａ−図１Ｃを参照して説明される。図１Ａに概略的に示されたように、時間ｔ０で、ノード２を通って宛先Ｄに到達することができる。時間ｔ１で、ノード２は、ノード２を介した経路を使用して宛先Ｄに到達できることをそのピアに知らせるために、広告ＵＰＤＡＴＥメッセージＡ：［２；Ｄ］を送る。この広告は、ノード１で受信され、その結果として、ノード１は、ルーティングテーブルが経路［２；Ｄ］を含むように、時間ｔ２でそのルーティングテーブルを更新する。また、時間ｔ３で、ノード１は、さらなる広告Ａ：［１，２；Ｄ］をそのピアに送る。
【００２３】
図１Ｂを参照すると、時間ｔ４でノード２を介して宛先Ｄにもはや到達できないと仮定されている。結果として、ノード２は、時間ｔ５で、取消しＵＰＤＡＴＥメッセージＷ：［２；Ｄ］をそのピア（ノード１および３）に送る。しかしながら、ノード３は、ノード２と宛先の間の障害についてまだ知らされていないので、ノード１に広告ＵＰＤＡＴＥメッセージＡ：［３，２；Ｄ］を送っている。したがって、ノード１は、そのルーティングテーブルから［２；Ｄ］を削除するが、［３，２；Ｄ］を追加する。また、ノード１は、時間ｔ７で、さらなる広告Ａ：［１，３，２；Ｄ］をそのピアに送る。
【００２４】
同様に、図１Ｃに示されたように、ノード３は、時間ｔ７’で、取消しメッセージＷ：［３，２；Ｄ］をそのピアに送る。しかしながら、ノード４は、障害についてまだ知らされておらず、時間ｔ７″とほぼ同じときに、Ａ：［４，３，２；Ｄ］をノード１に広告する。結果として、ノード１は、そのルーティングテーブルからルート［３，２；Ｄ］を削除するが、時間ｔ８に、そのルーティングテーブルにルート［４，３，２；Ｄ］を追加する。さらに、時間ｔ９で、広告ＵＰＤＡＴＥメッセージＡ：［１，４，３，２；Ｄ］が、ノード１によってそのピアに送られる。こうした経路探索によって収束が非常に遅くなることが明らかであろう。
【００２５】
換言すると、典型的には、特定の宛先プレフィックスに向かうＡＳ経路に含まれたノードが相関しているという事実にも拘らず、ＢＧＰ更新は、空間的には調整されていない。同じ宛先に向かうそれぞれ異なるＡＳ経路間のノードに関するトポロジ相関は、典型的なＡＳトポロジのメッシュ性（ｍｅｓｈｅｄｎｅｓｓ）によってもたらされる。それぞれ異なる経路間のトポロジ相関に結合された空間レベルの調整が行われないこの欠如によって、トポロジが変化するとき、同じ宛先に向かう各経路が探索されるという過渡的な段階が生じることになる。
【００２６】
経路探索は、宛先が最初に広告されるときと、宛先が取消しされるときの両方で行われ得る：
−  宛先広告時間では、ノードトポロジに亘る差異伝播／処理遅延によって、最適経路が受信されるまで、次善の選択が行われる結果になり得る。
−  宛先取消し時では、図１Ａ−図１Ｃに示されたように、まずＢＧＰ取消しＵＰＤＡＴＥメッセージの発信元のＢＧＰルータとローカルＢＧＰルータの間でいくつかの過渡的経路が、他の過渡的経路が存在しなくなるまで選択される。
【００２７】
所与の宛先について両方の場合において、時間ｔ（ｉ）における第１の告知／取消しと、時間ｔ（ｉ＋ｊ）（ｊ＞０）における同じ宛先について新しく選択された経路との間の依存性によって、次に最良の好ましい経路に到達するまで、すべての中間経路の過渡的な探索が潜在的に行われることになる。
【００２８】
下記に詳細に説明されるように、本発明の方法の一実施形態は、ルーティングシステム収束に有害なドメイン間ＢＧＰルーティング更新の系列の抑制を強化するために、経路探索系列検出の技法を提供する。より具体的には、本発明の一実施形態によれば、ローカルＢＧＰ収束時間は、ｔ＿ｃｏｎｖｅｒｇｅｎｃｅから確率的時間ｔ＿ｐｒｏｂまで減少し、ただし、
ｔ＿ｃｏｎｖｅｒｇｅｎｃｅ＝（Ｍａｘ＿ＡＳ経路−Ｍｉｎ＿ＡＳ経路）×ＭＲＡＩであり、ＭＲＡＩは最小ルート広告間隔、すなわちノードによって送られる広告ＵＰＤＡＴＥメッセージ間の間隔であり、
ｔ＿ｐｒｏｂ＝検出時間＋代替の最良経路選択時間である。
【００２９】
本発明の一実施形態によれば、ＢＧＰ  ＵＰＤＡＴＥ系列内の経路探索現象が検出される。より具体的には、入ってくるＡＳ経路系列が経路探索イベントに関連するか否かが判定される。本発明の方法のこの実施形態のさらなる好ましいステップは、学習ステップを行うことにあり、下流隣接ノードに対する対応するＢＧＰ更新の影響を期待通りに最小限に抑えるために、経路探索イベントの終了に達する前にこのイベントに関連する最長の連続ＡＳ経路部分系列が識別される。図１Ａの例示的なトポロジでは、学習段階の間、各中間状態について取消しが観測される「最短経路」［２；Ｄ］と「最長の経路」［４，３，２；Ｄ］が決定されている。したがって、最長の差異部分系列は［４，３］である。実行時、学習段階の後、部分系列［４，３］の第１の要素が観測されるとき、ルート選択過程は、宛先Ｄに到達するためのその系列に関連するどんな経路をも取り除く。やはり実行時に、学習は継続することができ、選択過程はさらに最適化され得ることに留意されたい。
【００３０】
方法のこの実施形態のさらなる進展によれば、ルート選択過程のＢＧＰ決定は、経路探索イベント検出および識別（特徴付け）が行われるときに予想される。これは典型的には、ＢＧＰに広告される代替の最良ＡＳ経路の選択など、下流のノードの出入り（ｃｈｕｒｎ）を抑制するための措置を伴う。
【００３１】
本発明につながる基礎をなす考えのうちの１つは、経路探索イベントの間、ＢＧＰルーティングシステムが異なる状態間で遷移し、異なる状態間のこの遷移がマルコフ連鎖によって支配されるという認識に基づく。しかしながら、経路探索イベントが非通知のＢＧＰ更新処理の結果生じるので、このマルコフ連鎖は、直接的に観測可能ではなく、すなわちそれは隠れている。それにも拘らず、ＡＳ経路の受信系列は、ＢＧＰルーティングシステム、または少なくとも関心のあるネットワークの上流部分の現在の状態に関する確率的情報を提供する。
【００３２】
本発明の一実施形態によれば、ＢＧＰルーティングシステム状態が利用される隠れマルコフモデル（ＨＭＭ）が使用され、このＢＧＰルーティングシステム状態は、入ってくるＢＧＰ通信チャネル、したがってローカルＢＧＰ決定過程に対するすべてのＢＧＰ  ＵＰＤＡＴＥメッセージ交換の影響を表す。ローカルルータ決定過程は、グローバルルーティングシステム状態を直接的に使用するものでも、それについての知識を有するものでもなく、したがって、ルーティングシステムステータスモデルは、隠れ変数である。この隠れ変数は、ＢＧＰ通信チャネルによって生成された観測系列を介してローカルルータによってのみ知覚され得るものであり、その系列出力は、入ってくるＢＧＰ  ＵＰＤＡＴＥメッセージからローカルルート選択過程によって受信されたＡＳ経路系列を表す。
【００３３】
観測が状態の確率的関数である、すなわち結果として生じるモデルが、観測可能でない（それが隠れている）が、観測系列を生成する確率過程の別の集合を介してのみ観測可能である基礎となる確率過程と二重に埋め込まれた確率過程であるケースを含めるために、このモデルは、隠れマルコフモデル（ＨＭＭ）に拡張される。こうしたモデルは、確率的系列をマルコフ連鎖として表し、このマルコフ連鎖では、状態が直接的には観測されないが、確率密度関数（ｐｄｆ：ｐｒｏｂａｂｉｌｉｔｙ  ｄｅｎｓｉｔｙ  ｆｕｎｃｔｉｏｎ）に関連付けられる。
【００３４】
次いで、ランダム系列が生成されるのは、状態を訪れるごとにチェーン内をランダムウォークする（すなわち、状態のランダム系列および描画（出力と呼ばれる）をざっと見ること）の結果である。関心量である状態系列は、各状態へと定義された確率過程によって観測され得る（すなわち、典型的には、各状態のｐｄｆのパラメータは、状態Ｑの系列を観測Ｏの系列に関連付け可能となる前に知られていなくてはならない）。したがって、真の状態系列は、確率過程の第１の層によって隠されている。
【００３５】
本発明の好ましい一実施形態によれば、隠れマルコフモデル（ＨＭＭ）が、経路探索イベントの検出に使用される。本発明においてＨＭＭがどのように使用されるか詳細に説明する前に、本発明についてよりよく理解するために離散マルコフ連鎖に関する理論について簡潔に見てみる。論文、Ｒ．  Ｒａｂｉｎｅｒ、「Ａ  Ｔｕｔｏｒｉａｌ  ｏｎ  Ｈｉｄｄｅｎ  Ｍａｒｋｏｖ  Ｍｏｄｅｌｓ  ａｎｄ  Ｓｅｌｅｃｔｅｄ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｉｎ  Ｓｐｅｅｃｈ  Ｒｅｃｏｇｎｉｔｉｏｎ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＩＥＥＥ、７７巻、２号、１９８９年２月をさらに参照されたい。
【００３６】
離散マルコフ連鎖
いずれのときもＮ個の離散状態（Ｓｉ，Ｓ２，…，ＳＮ）の集合のうちの１つとして表すことができるシステムについて考慮されたい。規則的に間隔を置いた離散時間に、システムは、状態に関連する確率の集合に従って状態の変化を経る。典型的には、こうしたシステムは、状態遷移確率の集合によって特徴付けられる。ａｉｊ＝Ｐ（時間ｔ＋１のときのｑｊ｜時間ｔのときのｑｉ）＝Ｐ（ｑｊ，ｔ＋１｜ｑｉ，ｔ）（式１）
１≦ｉ、ｊ≦Ｎ、
【数１】
0005509340.tif 000002
であり、
ただし、時間ｔ＋１のときのｑｊは、実際の状態が、時間ｔ＋１のときにＳｊに等しいことを意味し、時間ｔのときのｑｉは、直前の実際の状態が、時間ｔのときにＳｉであったことを意味する。
【００３７】
この確率過程は、過程の出力が各時間インスタンスにおける状態の集合であるので観測可能マルコフモデルと呼ばれることがあり、各状態が物理的な（観測可能な）事象に対応する。
【００３８】
隠れマルコフモデル
モデル化されているシステムの物理出力に対応する状態ごとにＮ個の隠れ状態およびＭ個の離散観測シンボルを有する隠れマルコフモデル（ＨＭＭ）は、３つの確率分布によって定義される：
−  （状態）遷移確率分布Ａ＝｛ａｉｊ｝、ａｉｊで、状態ｉ（ｑｉ）から状態ｊ（ｑｊ）に移る確率がＰ（時間ｔ＋１のときのｑｊ｜時間ｔのときのｑｉ）＝Ｐ（ｑｊ，ｔ＋１｜ｑｉ，ｔ）、１≦ｉ、ｊ≦Ｎによって与えられる。
−  観測確率分布：Ｂ＝｛ｂｊ（Ｏ）｝、ただし、ｂｊ（Ｏ）＝Ｐ（時間ｔのときのＯ｜時間ｔのときのｑｊ）＝Ｐ（Ｏｔ｜ｑｊ，ｔ）、すなわち、ｂｊは、状態ｊにおいて観測ベクトルＯを出力する確率分布。離散的な場合では、各観測Ｏｔは、モデル化されるシステムの物理出力に対応するＭ個の観測シンボルのライブラリからその値を取る。出力確率は、各状態ｑｊを特徴付けるｐｄｆである。
−  初期状態分布：Π＝｛πｉ｝、ただし、πｉ＝Ｐ（ｔ＝１のときのｑｉ）＝Ｐ（ｑｉ，ｌ）によって初期確率が与えられる。
【００３９】
実世界の応用に有用なものにするには、モデルλ＝（Α，Β，Π）について解かなければならない３つの基本的問題がある。
【００４０】
問題１：観測系列Ｏ＝Ｏ１，Ｏ２，…，ＯＴおよびモデルλ＝（Α，Β，Π）が与えられたとき、問題は、Ρ（Ｏ｜λ）、モデルλが与えられたときの観測系列Ｏの確率を計算することである。この問題は典型的には、前向きアルゴリズムおよび後向きアルゴリズムによって解かれる。
【００４１】
問題２：観測系列Ｏ＝Ｏ１，Ｏ２，…，ＯＴおよびモデルλ＝（Α，Β，Π）が与えられたとき、所与の観測系列に関連する最適な状態系列Ｑ＝ｑ１，ｑ２，…，ｑＴを見つける。（モデルλが与えられたときＰ（Ｑ｜Ｏ）を最大化する）単一の最適な状態系列を見つけるための形式的な技法が、ビタビアルゴリズムと呼ばれる動的プログラミング法に基づいて存在する。
【００４２】
問題３：モデルパラメータＡ、ＢおよびΠを、モデルが与えられたときに観測系列Ｏの確率を最大化するように調整する方法を決定する。観測系列の確率を最大化するモデルについて解析的に解くための知られているやり方はない。実際に、訓練データとして任意の有限の観測系列が与えられたとき、モデルパラメータを推定する最適なやり方はない。しかしながら、ボームウェルチ法のなどの反復手順を使用してΡ（Ｏ｜λ）が局所的に最大化されるようにλ＝（Α，Β，Π）を選ぶことができる。
【００４３】
本発明の実施形態で使用されたＨＭＭ
ＨＭＭは、観測ＯとルーティングシステムイベントＱの同時発生の可能性をモデル化し、すなわち、それは、結合分布Ｐ（Ｏ，Ｑ）を表すものである。問題は、目的として経路探索系列の加速された検出、および最小数の経路探索ヒットに達した後に続く適切なＡＳ経路の選択（または生成）と共に、観測されたＡＳ経路系列を分類することにある。
【００４４】
ＢＧＰルーティングシステムの各状態は、ＨＭＭ状態としてモデル化される。４つまたは５つの隠れ状態が、ＨＭＭについて定義される。ＨＭＭの出力は、Ｌｏｃ−ＲＩＢに取り込まれる（ｐｏｐｕｌａｔｅ）。モデルは、宛先プレフィックスまたはプレフィックスのクラスタごとに適用されてよいことに留意されたい。
【００４５】
観測Ｏは、ＢＧＰルート選択過程によって受信されたＡＳ経路として、したがってＢＧＰルート選択過程の実行前にモデル化される。ＡＳ経路属性情報は、宛先ごとのプレフィックスに基づいて抽出されることに留意されたい。以下を定義する：
−  Ａ：プレフィックスの告知（ＡＳ経路または属性に変更なし）
−  Ａ＋：ＡＳ経路長が増加するプレフィックスの告知（より長いＡＳ経路への変更）
−  Ａ＊：ＡＳ経路は同じであるが、属性が異なるプレフィックスの告知（属性の更新）
−  Ａ０：同じ長さの異なる経路を有するプレフィックスの告知（同じ長さの異なるＡＳ経路への更新）
−  Ｗ（Ａ）：所与のプレフィックスについてのＡＳ経路Ａの取消し
【００４６】
次いで、経路探索の普及した形は、（既に告知されたプレフィックスについて）ＡＳ経路長が増加し、その後に取消しＷが続く系列であり、それらの観測は、時間的に密結合される：Ａ，｛Ａ＋，Ａ０，Ａ＊｝，Ｗ。Ａ＋、Ａ０およびＡ＊更新は、過渡的なルーティング状態を表す中間の更新である。関心のある告知／取消しの一般的な系列、すなわち経路探索イベントの特性は、下記の通り表されてよい：
Ａｏ，Ｗ（Ａｏ），｛Ａ＋，Ａ０，Ａ＊｝１，Ｗ（Ａ１），｛Ａ＋，Ａ０，Ａ＊｝２，Ｗ（Ａ２），…
【００４７】
一般に、この系列は、取消し、またはＡ，｛Ａ＋，Ａ０，Ａ＊｝ｃとして定義された新しく好まれる最良の経路に安定化することで終了することができ、ただし、ｃは、集合｛Ａ＋，Ａ０，Ａ＊｝から取られたイベントのうちの１つの反復を示す正の整数値であり、ただし、整数ｃの最小値は１であり、整数ｃの最大値はｎ−１である。実際に、経路探索現象の間、ローカルＡＳは、長さＣ２のサイクル（Ｍｉｎ＿ＡＳ経路＋１）からＣｎ−１（Ｍａｘ＿ＡＳ経路）へのすべての状態を探索することができる。
【００４８】
この時点で、ＡＳ経路のこうした系列は、Ｌｏｃ−ＲＩＢに取り込まれるＢＧＰルート選択過程の結果であることに留意されたい。Ａｄｊ−ＲＩＢ−Ｉｎにおいて管理される、入ってくるＢＧＰルーティング更新の実際の系列は、たとえば
Ａｄｊ−ＲＩＢ−Ｉｎ：Ａ０，｛Ａ＋，Ａ０，Ａ＊｝１，…，｛Ａ＋，Ａ０，Ａ＊｝ｍ，Ｗ（Ａ０），Ｗ（Ａ１），…，Ｗ（Ａｍ−１），Ｗ（Ａｍ）の形である。
【００４９】
図１Ａ−図１Ｃの例について、連続した時間的瞬間に下記の観測が、図２および図３に示されたように、宛先ＤのＡｄｊ−ＲＩＢ−Ｉｎに置かれる。
Ａｄｊ−ＲＩＢ−Ｉｎ：［２］，［３，２］，Ｗ［２］，［４，３，２］，Ｗ［３，２］，Ｗ［４，３，２］
【００５０】
従来技術によるＢＧＰルート選択過程によって選択された対応するＡＳ経路は下記である：
Ｌｏｃ−ＲＩＢ：Ａ０，｛Ａ０｝１，…，｛Ａ０｝ｍ，Ａ１，Ａ２，…，Ａｍ，なし
【００５１】
図１Ａ−図１Ｃの例について、連続した瞬間に、宛先Ｄへの選択された経路が、図２に示されている：
Ｌｏｃ−ＲＩＢ：［２］，［２］，［３，２］，［３，２］，［４，３，２］，なし
【００５２】
ローカルＢＧＰルータによってその下流の隣接ノードに広告される告知／取消しの系列は、（Ａ１＝｛Ａ＋，Ａ０，Ａ＊｝１，…，Ａｍ＝｛Ａ＋，Ａ０，Ａ＊｝ｍとして）
Ａｄｊ−ＲＩＢ−Ｏｕｔ：Ａ０，｛Ａ０｝１，…，｛Ａ０｝ｍ，Ｗ（Ａ０），Ａ１，Ｗ（Ａ１），…，Ｗ（Ａｍ−１），Ａｍ，Ｗ（Ａｍ）である。
【００５３】
図１Ａ−図１Ｃの例について、宛先Ｄへの広告された経路が、図２に示されている：
Ａｄｊ−ＲＩＢ−Ｏｕｔ：［１，２］，［１，２］，Ｗ［１，２］，［１，３，２］，［１，３，２］，Ｗ［１，３，２］，［１，４，３，２］，Ｗ［１，４，３，２］
【００５４】
本発明の一実施形態によれば、一度Ａｄｊ−ＲＩＢ−Ｉｎパターンが知られると、目的は、入ってくるＢＧＰ  ＵＰＤＡＴＥのフローの一部として、出ていくＢＧＰ  ＵＰＤＡＴＥのこうしたパターンにつながるＡＳ経路（系列）を検出することである。換言すると、ある観測系列Ｏ：Ｐ（ｑ｜Ｏ）が与えられたとき、「経路探索ヒット」到達への最も確率の高い状態系列を決定することが望ましい。次いで、対応する観測系列が、たとえば、過渡的であるローカルな決定を公開しないＢＧＰ  ＵＰＤＡＴＥに直接つながるように、ＢＧＰルート選択過程から取り除かれる。
【００５５】
Ａｄｊ−ＲＩＢ−Ｉｎに維持された、入ってくるＢＧＰルーティング更新の実際の系列は、従来技術と同じであってよい：Ａ０，｛Ａ＋，Ａ０，Ａ＊｝１，…，｛Ａ＋，Ａ０，Ａ＊｝ｍ，Ｗ（Ａ０），Ｗ（Ａ１），…，Ｗ（Ａｍ−１），Ｗ（Ａｍ）。
【００５６】
観測部分系列｛Ａ＋，Ａ０，Ａ＊｝１，…，｛Ａ＋，Ａ０，Ａ＊｝ｍ，Ｗ（Ａ０），…，Ｗ（Ａｍ）が、観測系列の一部であることを検出することによって、ＢＧＰルート選択過程によって選択された対応するＡＳ経路は、下記の告知系列によって与えられたＡＳ経路である：
Ｌｏｃ−ＲＩＢ：Ａ０，｛Ａ０｝１，…，｛Ａ０｝ｍ，なし
【００５７】
本発明の方法の一実施形態を使用する場合の１図Ａ−図１Ｃの例について、連続した瞬間に宛先Ｄへの選択された経路が、図３に示されている：
Ｌｏｃ−ＲＩＢ：［２］，［２］，なし
【００５８】
次いで、ローカルＢＧＰルータによってその下流の隣接ノードに広告される告知／取消しの系列は
Ａｄｊ−ＲＩＢ−Ｏｕｔ：Ａ０，｛Ａ０｝１，…，｛Ａ０｝ｍ，Ｗ（Ａ０）になる。
【００５９】
本発明の方法の一実施形態を使用する場合の図１Ａ−図１Ｃの例について、宛先Ｄへの広告された経路が、図２に示されている：
Ａｄｊ−ＲＩＢ−Ｏｕｔ：［１，２］，［１，２］，Ｗ［１，２］
【００６０】
図４Ａは、図１Ａ−図１Ｃの例と比べた場合、いくつかの追加ノード（ノード５−９）を備える別の例示的なトポグラフィを示している。この例では、図４Ｂに示された学習段階の間、部分系列［５，４，３］が識別されている。図４Ｃに示された通常の実行の間、下記の経路が
Ｌｏｃ−ＲＩＢ：［２］，［３，２］，［６，７，８，９］
Ａｄｊ−ＲＩＢ−Ｏｕｔ：［１，２］，Ｗ［１，２］，［１，３，２］，Ｗ［１，３，２］，［６，７，８，９］に置かれるように選択されている。
【００６１】
ここでは経路［３，２］は、図３の例の場合のようにすぐには取り消されないことに留意されたい。学習段階によっては、（偽陽性を減らすため）探索イベントが生じる場合、これはすぐに確かになるとは限らないことがある（こうした状態は典型的には、トポロジ変更に相関しないポリシー変更の結果として生じる）。こうした場合では、図４Ａ−図４Ｃの例の経路［３，２］などの経路が選択されてよいが、この経路は実際には、もはや使用可能でない。しかしながら、［４，３，２］および［５，４，３，２］が取り除かれ、直ちに［６，７，８，９］に収束するという事実から明らかであるように、経路探索の悪影響は大幅に減少される。
【００６２】
ルーティングシステムをモデル化するＨＭＭの実施形態
本発明の一実施形態によれば、宛先プレフィックスごとに、または同じ状態遷移を経る宛先プレフィックスの集合ごとにルーティングシステム状態をモデル化するために提案されたＨＭＭは、下記のように特徴付けられる：
−  Ｎ（モデルの隠れ状態の数）：４または５
これらの４つの状態は、下記のように定義される（図５も参照）：
状態１（Ｓ１）：ＡＳ経路変更なし
状態２（Ｓ２）：再初期化
状態３（Ｓ３）：ＡＳ経路増加
状態４（Ｓ４）：経路探索ヒット
【００６３】
これらの状態は実際に、ローカルＢＧＰルータで直接には観測可能でない隠れたグローバルルーティング状態を特徴付ける。用語「グローバル」は、経路探索イベントに関与するＡＳに対してローカルルータの「上流に」あるルーティングシステムの部分としてここでは理解されたい。
【００６４】
モデルをさらに改良するために、「探索なし」取消しについて説明する第５の状態Ｓ５が追加されてよく：典型的には、すべての取消しが、経路探索ヒットにつながる状態系列の一部と見なされるべきとは限らない。実際に、ＨＭＭは典型的には、Ｗ（Ａ０）だけが探索ヒットのトリガとなる見なすべきであり、Ｗ（Ａ０）の前に行われる告知Ａ１，…，Ａｍに関連する中間状態の取消しは、探索系列の一部とは見なされないものとする。この影響を考慮することが、第５の状態を我々のモデルに取り入れられることにつながる。
−  Ｍ（状態当たりの離散観測シンボルの数）：これらのシンボルは、ＢＧＰ  ＵＰＤＡＴＥメッセージで受信され、Ａｄｊ−ＲＩＢ−Ｉｎに格納され、Ｌｏｃ−ＲＩＢを埋めるＢＧＰルート選択過程によって処理されたＡＳ系列に対応する。
−  Ａ：状態遷移確率分布ａｉｊ＝Ｐ（ｑｊ，ｔ＋１｜ｑｉ，ｔ）、１≦ｉ、ｊ≦Ｎは、ルーティングシステム状態の個々の状態遷移に対応する。
−  Ｂ：状態ｊの観測確率分布、ｂｊ（Ｏ）＝Ｐ（Ｏｔ｜ｑｊ，ｔ）
−  Π：初期状態分布
【００６５】
Ａ、ＢおよびΠの初期値パラメータは、当業者にはよく知られている技法を使用して決定されてよい。ＡおよびΠは典型的には一様に選択されるが、Ｂについては、最大尤度およびＫ平均法が、最も使用される技法である。
【００６６】
学習モデルおよびＡＳ経路系列の分類
分類子は、観測されたＡＳ経路（Ｏ）をＢＧＰ状態イベントクラスにマッピングする関数ｈである。学習過程の目標は、新しいＡＳ経路のクラスｈ（Ｏ）を正確に予測する関数ｈを見つけることである。
【００６７】
この学習過程の訓練例は、対（Ｏ，ｑ）であり、ただし、ｑは状態を指し、ラベルに関連する。訓練データの例など、Ｎの集合に言及する。訓練データは実際は、（Ｏ，ｑ）対の系列からなる。これらの系列は、経路探索現象には特徴的である系列相関を示す。すなわち、Ｏおよびｑに近い値は、互いに関連する可能性が高い。たとえば、トポロジ変化が発生する前、ｑ個のラベル値のすべては、「ＡＳ経路変更なし」となる。その後、ｑラベル値はすべて、「ＡＳ経路増加」となる。こうしたパターンは、分類子の予測精度を向上させるのに活用され得る。この場合では、典型的な（正当な）系列の分布を見ることによって系列を探索し、次いで、ＢＧＰルーティング状態が変化するときにこの分布が変化することを見ることが可能である。目標は、入力系列Ｏが与えられたとき、新しいラベル系列ｑ＝ｈ（Ｏ）を正確に予測できる分類子ｈを構築することである。
【００６８】
コスト関数Ｌ（ｉ，ｊ）が、その真のラベルがｊである例に状態レベル値ｉを割り当てるコストを与えると仮定する。目標は、最小の期待コストを有する分類子ｈを見つけることである。コスト関数は、経路探索系列（の一部）を含むＢＧＰルートの選択に関連するペナルティ：欠落した経路探索イベント、偽陽性検出（分類が、実際には存在しない場合に経路探索イベントを宣言し、こうした誤りは典型的に、決定があまりに急速に行われるときに発生する）および偽陰性検出（分類が、実際にはそうである場合にイベントを経路探索イベントであると宣言せず、こうした誤りは典型的に、決定があまりに遅く行われるときに発生する）を評価する。
【００６９】
ＨＭＭは、結合確率密度推定量Ｐ（Ｏ，Ｑ）の表現であるので、条件付き確率密度推定量Ｐ（Ｑ｜Ｏ）を使用して、任意の特定の観測系列Ｏが与えられたときの任意の特定の状態ｑの確率を計算するために使用されてよい。次いで、新しい観測系列Ｏの分類が、観測Ｏが与えられたときの最適値ｑ’を予測する数式（ＨＭＭに関する節で上記に定義された問題２も参照）によって提供された最小期待コストを有するクラスを選択することによって実施される：
ｑ’＝ａｒｇｍｉｎｑｉΣｑｊＰ（ｑｊ｜Ｏ）Ｌ（ｑｉ，ｑｊ）
したがって、コスト関数をＡＳ経路系列の分類タスクに組み込むことは、出力系列：Ｐ（ｑｊ｜Ｏ）内の（状態）ラベルのすべての（条件付き）結合分布の予測することにある。この結合分布が正確に予測可能である場合、コスト関数は評価可能であり、観測系列Ｏに最適な決定が選択され得る。
【００７０】
実際に、系列の長さＴが非常に長くなり得るので、この数式を直接に評価するには、Ｏ（ＮＴ）回の確率の評価（ただし、Ｎはラベルの数である）を必要とし、それは非実用的である。しかしながら、コスト関数が系列全体に依存する場合、すなわちコスト関数が系列全体の分類にだけ関係する場合、この計算は、Ｏ（Ｎ２Ｌ）時間で実施されてよく、ただし、Ｌは、観測系列Ｏの長さである。この場合、最も高い確率を有するｑ’を見つけることは、次式を計算することにある：
ｑ’＝ａｒｇｍａｘｑｉＰ（ｑｉ｜Ｏ）
【００７１】
この表現は、第２のＨＭＭ問題に対応するビタビアルゴリズムによって計算されてよい。（ベルマンの動的プログラミングアルゴリズムの適用による）計算は、各クラスおよび時間間隔［０，ｔ］の各時間ステップに、最も可能性の高い状態遷移系列の確率を割り当てることにある。アルゴリズムは、系列の末尾に到着するときには、時間０から時間ｔへの最も可能性の高い経路およびその確率を計算している。換言すると、ある観測系列Ｏが与えられたときの最も確率の高い状態系列を決定することによって、「経路探索ヒット」に対応する観測系列を分離し、ＢＧＰルート選択過程からそれらの差を取り除くことができる。
【００７２】
本発明のルータシステムの簡略化された実施形態
最後に、図６は、本発明によるルータシステムの一実施形態を示しており、本発明に関連する部分だけが示されている。ルータシステムは、ＲＩＢ  １１を使用し、このＲＩＢ  １１は、処理手段１２によって、とりわけ状態データベース１４およびポリシー情報ベース１５からの情報を使用して更新される。処理手段１２は、Ｌｏｃ−ＲＩＢおよびＡｄｊ−ＲＩＢ−Ｏｕｔに置かれる経路を適切に選択できるようにするために、経路が経路探索イベントに関連するかどうか判定するためのＨＭＭ関数１３を備える。これは、選択関数を備える決定手段１６によって行われる。
【００７３】
本発明の原理について特定の実施形態に関連して上記に述べられているが、この説明は、例示するためだけに行われており、添付の特許請求の範囲に定められた保護の範囲を限定するものではないことを明らかに理解されたい。
【図１Ａ】
0005509340.tif 000003
【図１Ｂ】
0005509340.tif 000004
【図１Ｃ】
0005509340.tif 000005
【図２】
0005509340.tif 000006
【図３】
0005509340.tif 000007
【図４Ａ】
0005509340.tif 000008
【図４Ｂ】
0005509340.tif 000009
【図４Ｃ】
0005509340.tif 000010
【図５】
0005509340.tif 000011
【図６】
0005509340.tif 000012