(57)【要約】【課題】ＡＳ内のルータ数の増加に対して設備の大幅な更改を抑制でき、プレフィックスごとの経路情報を全て把握でき、ＡＳ内の経路情報を統一する技術を提供する。【解決手段】ＡＳ１は、経路情報の収集および経路選択の管理を行う複数のルートサーバ１０Ｄ，１０Ｅおよび複数のルータ２０を備えている。ルートサーバ１０Ｄ，１０Ｅは、それぞれ、ルータ２０Ｈ，２０ＩがＡＳ２から受信したプレフィックスＰ１を含む経路情報と、ルータ２０Ｊ，２０ＫがＡＳ３から受信したプレフィックスＰ９を含む経路情報とを分担して収集する。また、各ルータ２０は、パケットを受信したとき、ルートサーバ１０Ｄ，１０Ｅに問い合わせて、ルートサーバ１０Ｄ，１０Ｅによって決定された経路情報を取得する。そのため、ＡＳ内のルータ数の増加に対して設備の大幅な更改を抑制することができ、ＡＳ内の経路情報を統一することができる。【選択図】 図１
2010199800.tif 000002
【特許請求の範囲】
【請求項１】
ＩＰ（Internet Protocol）ネットワークを構成するＡＳ（Autonomous System）内で、他のＡＳから該他のＡＳのアドレスの集合であるプレフィックスを含む経路情報を収集しルーティングを行う経路情報管理システムにおいて用いられる経路情報管理方法であって、
前記経路情報管理システムは、前記他のＡＳのルータに直結する複数の境界ルータと、前記境界ルータによって取得された前記他のＡＳの経路情報を収集して、その収集した前記経路情報に基づいてデータの転送経路を決定する複数の経路管理装置とを備え、
前記境界ルータは、取得した前記経路情報に含まれる前記プレフィックスを用いて所定の演算を行い、その演算結果に基づいて該プレフィックスに対応付けられた経路管理装置に前記経路情報を送信し、
前記経路管理装置は、受信した該経路情報を記憶し、前記境界ルータから前記データの転送経路を問い合わせる問い合わせ情報を受けたときに、前記記憶した経路情報に基づいて転送経路を決定し、その決定した転送経路を含む経路決定情報を返信し、
前記問い合わせをした境界ルータは、該経路決定情報に基づいて前記データのルーティングを行う
ことを特徴とする経路情報管理方法。
【請求項２】
前記経路情報管理システムは、さらに、自ＡＳ内に前記境界ルータとは別に中継ルータを備え、
前記境界ルータまたは中継ルータは、データを受信したとき、そのデータに含まれるプレフィックスを抽出し該プレフィックスを用いた前記所定の演算を行い、そのプレフィックスに対応付けられた経路管理装置に前記データの転送経路を問い合わせる問い合わせ情報を送信し、前記問い合わせ情報に対する応答として前記経路管理装置から送信される前記経路決定情報を受信して、その受信した前記経路決定情報に基づいて前記データのルーティングを行う
ことを特徴とする請求項１に記載の経路情報管理方法。
【請求項３】
前記境界ルータおよび中継ルータは、処理部と前記経路管理装置を識別する経路管理装置ＩＤを記憶する記憶部とを備え、
前記処理部が、前記プレフィックスの値を所定のハッシュ関数に適用してハッシュ値ｋを算出し、前記ハッシュ値ｋと記憶部に記憶してある前記経路管理装置ＩＤとを比較して、前記ハッシュ値ｋ以上の範囲において最小の値となる前記経路管理装置ＩＤを算出することによって、前記プレフィックスを用いた前記所定の演算を実行する
ことを特徴とする請求項１または請求項２に記載の経路情報管理方法。
【請求項４】
前記経路管理装置は、処理部と記憶部とを備え、
前記記憶部に記憶される前記経路情報には該経路情報を受信した境界ルータの識別情報およびその受信に使用されたプロトコル種別と、前記境界ルータおよびルータ間の経路に付与されたコスト情報とを含み、さらに、前記記憶部にＡＳ内のトポロジ情報を記憶し、
前記処理部が、
前記問い合わせ情報を受け付けて前記データの転送経路を決定するとき、
（１）前記問い合わせ情報の送信元が境界ルータの場合には、
（１−１）当該境界ルータがｅＢＧＰで受信した経路情報を検索し、この検索した経路情報を用いて転送経路を選択する手順を実行し、
当該手順によって複数の転送経路が選択された場合には、
（１−２）さらに、前記トポロジ情報を参照して、該問い合わせ情報の送信元の境界ルータのトポロジ上の位置を特定し、前記転送経路の候補となる経路に付与されるコストの最も小さい経路を転送経路として選択する手順を実行して、転送経路を決定し、
（２）前記問い合わせ情報の送信元が中継ルータの場合には、前記トポロジ情報を参照して、該問い合わせ情報の送信元の境界ルータのトポロジ上の位置を特定し、前記転送経路の候補となる経路に付与されるコストの最も小さい経路を転送経路として選択する手順を実行して、転送経路を決定する
ことを特徴とする請求項２に記載の経路情報管理方法。
【請求項５】
前記経路管理装置は、少なくとも２つの転送経路を含む経路決定情報を前記境界ルータまたは前記中継ルータに送信し、
該経路決定情報を受信した前記境界ルータまたは前記中継ルータは、ネクストホップとの通信が切断したときに、送信されてきた該経路決定情報に含まれる別の転送経路に切り替える
ことを特徴とする請求項４に記載の経路情報管理方法。
【請求項６】
ＩＰ（Internet Protocol）ネットワークを構成するＡＳ（Autonomous System）内で、他のＡＳから該他のＡＳのアドレスの集合であるプレフィックスを含む経路情報を収集しルーティングを行う経路情報管理システムであって、
前記経路情報管理システムは、前記他のＡＳのルータに直結する複数の境界ルータと、前記境界ルータによって取得された前記他のＡＳの経路情報を収集して、その収集した前記経路情報に基づいてデータの転送経路を決定する複数の経路管理装置とを備え、
前記境界ルータは、取得した前記経路情報に含まれる前記プレフィックスを用いて所定の演算を行い、その演算結果に基づいて該プレフィックスに対応付けられた経路管理装置に前記経路情報を送信し、
前記経路管理装置は、受信した該経路情報を記憶し、前記境界ルータから前記データの転送経路を問い合わせる問い合わせ情報を受けたときに、前記記憶した経路情報に基づいて転送経路を決定し、その決定した転送経路を含む経路決定情報を返信し、
前記問い合わせをした境界ルータは、該経路決定情報に基づいて前記データのルーティングを行う
ことを特徴とする経路情報管理システム。
【請求項７】
前記経路情報管理システムは、さらに、自ＡＳ内に前記境界ルータとは別に中継ルータを備え、
前記境界ルータまたは中継ルータは、データを受信したとき、そのデータに含まれるプレフィックスを抽出し該プレフィックスを用いた前記所定の演算を行い、そのプレフィックスに対応付けられた経路管理装置に前記データの転送経路を問い合わせる問い合わせ情報を送信し、前記問い合わせ情報に対する応答として前記経路管理装置から送信される前記経路決定情報を受信して、その受信した前記経路決定情報に基づいて前記データのルーティングを行う
ことを特徴とする請求項６に記載の経路情報管理システム。
【請求項８】
前記境界ルータおよび中継ルータは、処理部と前記経路管理装置を識別する経路管理装置ＩＤを記憶する記憶部とを備え、
前記処理部が、前記プレフィックスの値を所定のハッシュ関数に適用してハッシュ値ｋを算出し、前記ハッシュ値ｋと記憶部に記憶してある前記経路管理装置ＩＤとを比較して、前記ハッシュ値ｋ以上の範囲において最小の値となる前記経路管理装置ＩＤを算出することによって、前記プレフィックスを用いた前記所定の演算を実行する
ことを特徴とする請求項６または請求項７に記載の経路情報管理システム。
【請求項９】
前記経路管理装置は、処理部と記憶部とを備え、
前記記憶部に記憶される前記経路情報には該経路情報を受信した境界ルータの識別情報およびその受信に使用されたプロトコル種別と、前記境界ルータおよびルータ間の経路に付与されたコスト情報とを含み、さらに、前記記憶部にＡＳ内のトポロジ情報を記憶し、
前記処理部が、
前記問い合わせ情報を受け付けて前記データの転送経路を決定するとき、
（１）前記問い合わせ情報の送信元が境界ルータの場合には、
（１−１）当該境界ルータがｅＢＧＰで受信した経路情報を検索し、この検索した経路情報を用いて転送経路を選択する手順を実行し、
当該手順によって複数の転送経路が選択された場合には、
（１−２）さらに、前記トポロジ情報を参照して、該問い合わせ情報の送信元の境界ルータのトポロジ上の位置を特定し、前記転送経路の候補となる経路に付与されるコストの最も小さい経路を転送経路として選択する手順を実行して、転送経路を決定し、
（２）前記問い合わせ情報の送信元が中継ルータの場合には、前記トポロジ情報を参照して、該問い合わせ情報の送信元の境界ルータのトポロジ上の位置を特定し、前記転送経路の候補となる経路に付与されるコストの最も小さい経路を転送経路として選択する手順を実行して、転送経路を決定する
ことを特徴とする請求項７に記載の経路情報管理システム。
【請求項１０】
前記経路管理装置は、少なくとも２つの転送経路を含む経路決定情報を前記境界ルータまたは前記中継ルータに送信し、
該経路決定情報を受信した前記境界ルータまたは前記中継ルータは、ネクストホップとの通信が切断したときに、送信されてきた該経路決定情報に含まれる別の転送経路に切り替える
ことを特徴とする請求項９に記載の経路情報管理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰ（Internet Protocol）ネットワークにおいて、ＡＳ（自律システム；Autonomous System）内で、別のＡＳ（一つの経路選択プロトコルによって経路を管理しているネットワークの範囲のこと）の経路情報を管理する技術に関する。
【背景技術】
【０００２】
インターネット等のＩＰネットワークは、異なる組織によって運営される多数のＡＳが接続されて形成されている。ＡＳ内にはルータが配置され、データを送信する場合、どの経路でそのデータを伝達するかが、ルーティングプロトコルによって決定される。ルーティングプロトコルは、大きく分けて、ＡＳ内用のＩＧＰ（Interior Gateway Protocol）とＡＳ間用のＢＧＰ（Border Gateway Protocol）とに分けられる。ＩＧＰはデータをＡＳ内の宛先に送信する場合に用いられ、ＢＧＰは異なるＡＳ間でデータを送信する場合に用いられる。そして、ＩＧＰおよびＢＧＰは、データを送信するルータ間に隣接関係（ピア）を結んで、互いの経路情報を交換し、交換した経路情報に基づいて、データを所定の宛先に伝達する経路を決定する。ＢＧＰでは、異なるＡＳ間で用いるＢＧＰをｅＢＧＰ（external BGP）と呼び、ＡＳ内で用いるＢＧＰをｉＢＧＰ（internal BGP）と呼んで区別している。なお、ｉＢＧＰは、ＢＧＰの情報を、他のＡＳから別のＡＳに転送する場合に用いられる。
【０００３】
ＩＧＰやＢＧＰで交換される経路情報は、プレフィックス(prefix)とパス属性情報とを含んで形成される。プレフィックスは、ネットワークアドレスとそのネットワークアドレスのネットマスクによって表記される宛先のアドレスの集合である。また、パス属性情報は経路情報に付加される当該経路の属性情報であり、経路を選択する際に用いられるパラメータである。
【０００４】
ここで、ＢＧＰに基づくＡＳ内の経路情報管理の従来技術について説明する。
例えば、図１２に示すように、ＡＳ１ａ内に、複数のルータＲ１ａ，Ｒ２ａ，Ｒ３ａ，・・，Ｒｎａが配置され、ルータＲ１ａ〜Ｒｎａが相互に接続されているものとする。いま、プレフィックス情報Ｐ１ａを含む経路情報がＡＳ２ａからＡＳ１ａ内のルータＲ１ａにｅＢＧＰを用いて広告されたとき、ルータＲ１ａは、ｉＢＧＰを用いて、ＡＳ１ａ内の他のルータＲ２ａ〜Ｒｎａに、「ルータＲ１ａにデータを送れば、プレフィックスＰ１に届けられる旨」の経路情報を広告する。ただし、ｉＢＧＰを用いてルータＲ１ａ〜Ｒｎａ間で広告する場合には、ＩＧＰによってルータＲ１ａ〜Ｒｎａ間が通信可能に接続されている必要がある。このようにして、各ルータＲ１ａ〜Ｒｎａは、広告された経路情報を記憶して、その記憶した経路情報に基づいて、データの転送経路を決めている。ただし、ｉＢＧＰでは、一般的にＡＳ１ａ内のルータＲ１ａ〜Ｒｎａ間をフルメッシュにピアを結んで運用される。そのため、ルータ数が増加傾向にあるＡＳにおいては、ルータ記憶容量を大きなものに更改したり、経路計算のために演算速度の早い高性能なものに更改したり、また、回線を通信帯域の広いものに更改したり、つまり設備の更改を行う必要が発生するという問題がある。
【０００５】
そこで、数百ルータによって構成されるようなＡＳの場合には、ルートリフレクタ（ＲＲ）（非特許文献１参照）またはＡＳコンフェデレーション（非特許文献２参照）が用いられている。ルートリフレクタ（ＲＲ）は、広告された経路情報をピアを結んだルートリフレクタクライアントに転送する。しかし、ルートリフレクタクライアント同士はピアを確立しないでよいため、ＡＳ内に確立すべきピア数をフルメッシュの場合より減少することが可能となる。また、ＡＳコンフェデレーションは、ＡＳ内にいくつかのサブＡＳを構成することによって、ピア数を減少することが可能である。そのため、ルータの記憶容量の増加や演算速度の高速化や回線の広帯域化を抑制することが可能となる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】T.Bates, E.Chen, and R.Chandra,“BGP Route Reflection : An Alternative to Full Mesh Internal BGP (IBGP)”，RFC4456，IETF，2006年4月
【非特許文献２】P.Traina, D.McPherson, and J.Scudder，“Autonomous System Confederations for BGP”，RFC5065，IETF，2007年8月
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、非特許文献１に記載のルートリフレクタ（ＲＲ）を用いる方法、および非特許文献２に記載のＡＳコンフェデレーションを用いる方法では、ｉＢＧＰトポロジがフルメッシュでなくなり、また情報を交換する際にＴＣＰによって張られるｉＢＧＰセッションにおいてプレフィックスごとに１つの経路しか広告されない。そのため、ＡＳ内の各ルータが経路情報の一部しか記憶しないことに起因する問題が発生する。すなわち、ＡＳ内の各ルータは、経路選択を行う際に、経路情報の一部に基づいて経路計算を行ってしまうという問題がある。さらに、その一部の経路情報から選択された経路情報が、ＩＧＰによってＡＳ内のルータに広告され、また、ｉＢＧＰによっても広告される。このような状態において、ＩＧＰおよびｉＢＧＰによって広告される経路情報が異なるタイミングでルータに届けられた場合には、ｉＢＧＰピアのルータ間で異なる経路情報を保持してしまい、広告しあうことによって、経路決定がいつまでも収束しないという問題がある。
【０００８】
また、ルートリフレクタを用いる方法では、ルートリフレクタが、パケットの転送元ルータからではなく、自身から見た最適経路を選択して各ルータに通達するので、ｉＢＧＰトポロジとＩＧＰトポロジとが乖離してしまう。この場合、パケットが境界ルータへ向かって転送されていくＩＧＰ経路上のルータにおいて意図しない境界ルータが選択されてしまうことが発生する。これによって、ＡＳ内でループが発生する問題や、ＡＳ間経路制御のポリジにおいて一般的に用いられる外部ＡＳ宛のパケットはできるだけ早く他のＡＳに送出するルーティングができない問題、すなわち、ホットポテトルーティングができない問題が発生する。
【０００９】
そこで、本発明の課題は、前記した問題を解決するために、ＡＳ内のルータ数の増加に対して設備の大幅な更改を抑制でき、経路情報を全て把握できるようにしてＡＳ内の経路情報を統一する技術を提供することを目的とする。
【課題を解決するための手段】
【００１０】
前記課題を解決するために、請求項１に記載の発明は、ＩＰ（Internet Protocol）ネットワークを構成するＡＳ（Autonomous System）内で、他のＡＳから該他のＡＳのアドレスの集合であるプレフィックスを含む経路情報を収集しルーティングを行う経路情報管理システムにおいて用いられる経路情報管理方法であって、前記経路情報管理システムが、前記他のＡＳのルータに直結する複数の境界ルータと、前記境界ルータによって取得された前記他のＡＳの経路情報を収集して、その収集した前記経路情報に基づいてデータの転送経路を決定する複数の経路管理装置とを備え、前記境界ルータが、取得した前記経路情報に含まれる前記プレフィックスを用いて所定の演算を行い、その演算結果に基づいて該プレフィックスに対応付けられた経路管理装置に前記経路情報を送信し、前記経路管理装置が、受信した該経路情報を記憶し、前記境界ルータから前記データの転送経路を問い合わせる問い合わせ情報を受けたときに、前記記憶した経路情報に基づいて転送経路を決定し、その決定した転送経路を含む経路決定情報を返信し、前記問い合わせをした境界ルータは、該経路決定情報に基づいて前記データのルーティングを行うことを特徴とする。
【００１１】
また、請求項６に記載の発明は、ＩＰ（Internet Protocol）ネットワークを構成するＡＳ（Autonomous System）内で、他のＡＳから該他のＡＳのアドレスの集合であるプレフィックスを含む経路情報を収集しルーティングを行う経路情報管理システムであって、前記経路情報管理システムが、前記他のＡＳのルータに直結する複数の境界ルータと、前記境界ルータによって取得された前記他のＡＳの経路情報を収集して、その収集した前記経路情報に基づいてデータの転送経路を決定する複数の経路管理装置とを備え、前記境界ルータが、取得した前記経路情報に含まれる前記プレフィックスを用いて所定の演算を行い、その演算結果に基づいて該プレフィックスに対応付けられた経路管理装置に前記経路情報を送信し、前記経路管理装置が、受信した該経路情報を記憶し、前記境界ルータから前記データの転送経路を問い合わせる問い合わせ情報を受けたときに、前記記憶した経路情報に基づいて転送経路を決定し、その決定した転送経路を含む経路決定情報を返信し、前記問い合わせをした境界ルータが、該経路決定情報に基づいて前記データのルーティングを行うことを特徴とする。
【００１２】
このような構成によれば、ＡＳ内の複数の経路管理装置は、プレフィックスごとに経路情報を分担して収集することができる。そのため、従来のルータでは、一部の経路情報しか収集できなかったのに対して、経路管理装置は、収集したプレフィックスに係る経路情報については全てを管理し、その経路情報に基づいてＡＳ内の全てのルータに共通の転送経路を決定することが可能となる。つまり、経路決定がいつまでも収束しないという問題およびループの発生を防ぐことができる。また、複数の経路管理装置を備えることによって、経路管理装置一台あたりの分担する経路情報の量を抑制することができ、ＡＳ内のルータ数の増加に対して設備の大幅な更改を抑制することができる。
【００１３】
請求項２に記載の発明は、請求項１に記載の経路情報管理方法において、前記経路情報管理システムが、さらに、自ＡＳ内に前記境界ルータとは別に中継ルータを備え、前記境界ルータまたは中継ルータが、データを受信したとき、そのデータに含まれるプレフィックスを抽出し該プレフィックスを用いた前記所定の演算を行い、そのプレフィックスに対応付けられた経路管理装置に前記データの転送経路を問い合わせる問い合わせ情報を送信し、前記問い合わせ情報に対する応答として前記経路管理装置から送信される前記経路決定情報を受信して、その受信した前記経路決定情報に基づいて前記データのルーティングを行うことを特徴とする。
【００１４】
また、請求項７に記載の発明は、請求項６に記載の経路情報管理システムにおいて、前記経路情報管理システムが、さらに、自ＡＳ内に前記境界ルータとは別に中継ルータを備え、前記境界ルータまたは中継ルータが、データを受信したとき、そのデータに含まれるプレフィックスを抽出し該プレフィックスを用いた前記所定の演算を行い、そのプレフィックスに対応付けられた経路管理装置に前記データの転送経路を問い合わせる問い合わせ情報を送信し、前記問い合わせ情報に対する応答として前記経路管理装置から送信される前記経路決定情報を受信して、その受信した前記経路決定情報に基づいて前記データのルーティングを行うことを特徴とする。
【００１５】
このような構成によれば、ＡＳ内の境界ルータまたは中継ルータが、データに含まれるプレフィックスに対応付けられた経路管理装置に問い合わせ情報を送信し、その問い合わせ情報に対する応答として、経路決定情報を受信できる。そのため、ＡＳ内の全ての境界ルータおよび中継ルータにとって共通の転送経路を決定することが可能となる。つまり、経路決定がいつまでも収束しないという問題およびループの発生を防ぐことができる。
【００１６】
請求項３に記載の発明は、請求項１または請求項２に記載の経路情報管理方法において、前記境界ルータおよび中継ルータが、処理部と前記経路管理装置を識別する経路管理装置ＩＤを記憶する記憶部とを備え、前記処理部が、前記プレフィックスの値を所定のハッシュ関数に適用してハッシュ値ｋを算出し、前記ハッシュ値ｋと記憶部に記憶してある前記経路管理装置ＩＤとを比較して、前記ハッシュ値ｋ以上の範囲において最小の値となる前記経路管理装置ＩＤを算出することによって、前記プレフィックスを用いた前記所定の演算を実行することを特徴とする。
【００１７】
また、請求項８に記載の発明は、請求項６または請求項７に記載の経路情報管理システムにおいて、前記境界ルータおよび中継ルータが、処理部と前記経路管理装置を識別する経路管理装置ＩＤを記憶する記憶部とを備え、前記処理部が、前記プレフィックスの値を所定のハッシュ関数に適用してハッシュ値ｋを算出し、前記ハッシュ値ｋと記憶部に記憶してある前記経路管理装置ＩＤとを比較して、前記ハッシュ値ｋ以上の範囲において最小の値となる前記経路管理装置ＩＤを算出することによって、前記プレフィックスを用いた前記所定の演算を実行することを特徴とする。
【００１８】
このような構成によれば、ＡＳ内の経路管理装置にＩＤを割り振るだけで、経路管理装置が分担するプレフィックスを決定することができ、複数の経路管理装置を容易に設定することが可能となる。
【００１９】
請求項４に記載の発明は、請求項２に記載の経路情報管理方法において、前記経路管理装置が、処理部と記憶部とを備え、前記記憶部に記憶される前記経路情報には該経路情報を受信した境界ルータの識別情報およびその受信に使用されたプロトコル種別と、前記境界ルータおよびルータ間の経路に付与されたコスト情報とを含み、さらに、前記記憶部にＡＳ内のトポロジ情報を記憶し、前記処理部が、前記問い合わせ情報を受け付けて前記データの転送経路を決定するとき、（１）前記問い合わせ情報の送信元が境界ルータの場合には、（１−１）当該境界ルータがｅＢＧＰで受信した経路情報を検索し、この検索した経路情報を用いて転送経路を選択する手順を実行し、当該手順によって複数の転送経路が選択された場合には、（１−２）さらに、前記トポロジ情報を参照して、該問い合わせ情報の送信元の境界ルータのトポロジ上の位置を特定し、前記転送経路の候補となる経路に付与されるコストの最も小さい経路を転送経路として選択する手順を実行して、転送経路を決定し、（２）前記問い合わせ情報の送信元が中継ルータの場合には、前記トポロジ情報を参照して、該問い合わせ情報の送信元の境界ルータのトポロジ上の位置を特定し、前記転送経路の候補となる経路に付与されるコストの最も小さい経路を転送経路として選択する手順を実行して、転送経路を決定することを特徴とする。
【００２０】
また、請求項９に記載の発明は、請求項７に記載の経路情報管理システムにおいて、前記経路管理装置が、処理部と記憶部とを備え、前記記憶部に記憶される前記経路情報には該経路情報を受信した境界ルータの識別情報およびその受信に使用されたプロトコル種別と、前記境界ルータおよびルータ間の経路に付与されたコスト情報とを含み、さらに、前記記憶部にＡＳ内のトポロジ情報を記憶し、前記処理部が、前記問い合わせ情報を受け付けて前記データの転送経路を決定するとき、（１）前記問い合わせ情報の送信元が境界ルータの場合には、（１−１）当該境界ルータがｅＢＧＰで受信した経路情報を検索し、この検索した経路情報を用いて転送経路を選択する手順を実行し、当該手順によって複数の転送経路が選択された場合には、（１−２）さらに、前記トポロジ情報を参照して、該問い合わせ情報の送信元の境界ルータのトポロジ上の位置を特定し、前記転送経路の候補となる経路に付与されるコストの最も小さい経路を転送経路として選択する手順を実行して、転送経路を決定し、（２）前記問い合わせ情報の送信元が中継ルータの場合には、前記トポロジ情報を参照して、該問い合わせ情報の送信元の境界ルータのトポロジ上の位置を特定し、前記転送経路の候補となる経路に付与されるコストの最も小さい経路を転送経路として選択する手順を実行して、転送経路を決定することを特徴とする。
【００２１】
このような構成によれば、従来はルータが、自分を起点として経路選択を行っていたのに対して、経路管理装置は、他のルータを起点として、トポロジ上のルータの位置を考慮した転送経路を決定することが可能となる。
【００２２】
請求項５に記載の発明は、請求項４に記載の経路情報管理方法において、前記経路管理装置が、少なくとも２つの転送経路を含む経路決定情報を前記境界ルータまたは前記中継ルータに送信し、該経路決定情報を受信した前記境界ルータまたは前記中継ルータが、ネクストホップとの通信が切断したときに、送信されてきた該経路決定情報に含まれる別の転送経路に切り替えることを特徴とする。
【００２３】
また、請求項１０に記載の発明は、請求項９に記載の経路情報管理システムにおいて、前記経路管理装置が、少なくとも２つの転送経路を含む経路決定情報を前記境界ルータまたは前記中継ルータに送信し、該経路決定情報を受信した前記境界ルータまたは前記中継ルータが、ネクストホップとの通信が切断したときに、送信されてきた該経路決定情報に含まれる別の転送経路に切り替えることを特徴とする。
【００２４】
このような構成によれば、ルータは、複数の転送経路を含む経路決定情報を取得するので、ネクストホップとの通信が切断した際に残りの経路に容易に切り替えることが可能となる。
【発明の効果】
【００２５】
本発明によれば、ＡＳ内のルータ数の増加に対して設備の大幅な更改を抑制でき、経路情報を全て把握できるようにしてＡＳ内の経路情報を統一する技術を提供することができる。
【図面の簡単な説明】
【００２６】
【図１】本実施形態の概要を説明する図である。
【図２】本実施形態における経路情報管理システムの構成例を示す図である。
【図３】ルートサーバ決定方法の例を示す図である。
【図４】ルートサーバの追加方法の例を示す図である。
【図５】ルートサーバの機能ブロックの例を示す図である。
【図６】経路表の例を示す図である。
【図７】ルータの機能ブロックの例を示す図である。
【図８】ルートサーバの経路情報収集手順の例を示す図である。
【図９】ルータの経路決定情報取得手順の例を示す図である。
【図１０】ルートサーバにおける経路決定手順処理の例を示す図である。
【図１１】経路決定手順処理の具体例を示す図である。
【図１２】従来のＡＳ内の経路情報管理を示す図である。
【発明を実施するための形態】
【００２７】
次に、本発明を実施するための形態（以降「本実施形態」と称す）について、適宜図面を参照しながら詳細に説明する。
【００２８】
≪本実施形態の概要≫
初めに、本実施形態の概要について、図１を用いて説明する。
図１に示すように、経路情報管理システム３０は、ＡＳ１内に、経路情報の収集およびルーティングの管理を行う複数のルートサーバ（経路管理装置）１０Ｄ，１０Ｅおよび複数のルータ２０（２０Ｈ，２０Ｉ，２０Ｊ，２０Ｋ，２０Ｌ等）を備えている。そして、各ルートサーバ１０Ｄ，１０Ｅは、ルータ２０と通信可能に接続される。また、各ルータ２０間は、実線（直線）で示されるように通信可能に接続されている。なお、図１は一例であり、ルートサーバ１０Ｄ，１０Ｅの台数、ルータ２０の台数はこれに限られない。また、ルータ２０間の接続は、図１に示した状態に限られない。
【００２９】
図１の破線に示すように、ＡＳ１内のルータ２０Ｈ，２０Ｉが、ＡＳ２からプレフィックスＰ１を含む経路情報をｅＢＧＰによって受信したものとする。そして、受信したプレフィックスＰ１を含む経路情報は、ルートサーバ１０Ｄに収集される。また、ＡＳ１内のルータ２０Ｊ，２０Ｋが、ＡＳ３からプレフィックスＰ９を含む経路情報をｅＢＧＰによって受信したものとする。そして、受信したプレフィックスＰ９を含む経路情報は、ルートサーバ１０Ｅに収集される。すなわち、ルートサーバ１０Ｄ，１０Ｅは、それぞれ、異なるプレフィックスに係る経路情報を収集する。なお、どのルートサーバ１０Ｄ，１０Ｅが、どのプレフィックスＰ１，Ｐ９を含む経路情報を収集するかを決定するルートサーバ決定方法については、後記する。
【００３０】
このようにして、各ルートサーバ１０Ｄ，１０Ｅは、プレフィックスＰ１，Ｐ９ごとの全ての経路情報を収集できるので、全ての経路情報に基づいて転送経路の決定を行うことが可能となる。つまり、前記した従来のルータに見られるような一部の経路情報しか取得できず、その一部の経路情報に基づいて転送経路の決定を行うというようなことは起きない。また、ルートサーバ１０Ｄ，１０ＥがプレフィックスＰごとの経路情報を分散して担当するので、ＡＳ内のルータ台数が増加しても、ルートサーバ一台あたりの記憶容量の増加や処理負荷の増加を抑制することが可能となる。また、ルートサーバが複数備えられるため、経路情報の送受信が分散されて、回線の通信帯域の増加を抑制することも可能となる。つまり、ＡＳ内のルータ数の増加に対して設備の大幅な更改を抑制することができる。
【００３１】
次に、各ルータ２０は、パケットを受信したとき、ルートサーバ１０Ｄ，１０Ｅに問い合わせて、ルートサーバ１０Ｄ，１０Ｅによって決定された経路情報を取得する。各ルータ２０が、どのルートサーバ１０Ｄ，１０Ｅに問い合わせればよいかについては、後記するルートサーバ決定方法に基づいて、決定される。
例えば、図１に示すように、ルータ２０ＬにプレフィックスＰ１を宛先とするパケットが到着した（図１の（１）参照）とき、ルータ２０Ｌは、後記するルートサーバ決定方法に基づいて、プレフィックスＰ１に係る経路情報を取得しているルートサーバ１０Ｄへ、問い合せを行う（図１の（２）参照）。そして、ルートサーバ１０Ｄは、後記する経路決定手順に基づいて、ルータ２０Ｌのネクストホップがルータ２０Ｈであるとする転送経路を決定し、その決定した結果（経路決定情報）を返信する（図１の（３）参照）。そして、ルータ２０Ｌは、受信した経路決定情報に基づいて、パケットをルーティングする。このようにして、プレフィックスＰ１については、ルートサーバ１０Ｄが転送経路を決定し、問い合わせてきたルータ２０にその転送経路に係る経路情報（経路決定情報）を返信することによって、ＡＳ１内の経路情報を統一することができる。
【００３２】
また、ルートサーバ１０Ｄ，１０Ｅが最適経路を決定する場合に、ルータの位置を考慮した後記する経路決定手順を用いる。さらに、その経路決定手順において、最適経路のみを選択するのではなく、次善の経路を選択するようにする。そして、最適経路および次善の経路に係る経路情報（経路決定情報）を、ｉＢＧＰの拡張機能を用いて、問い合わせてきたルータ２０に返信する。このことによって、ルータ２０は、ネクストホップのルータとの通信が切断した際に、新しい経路として次善の経路に直ちに切り替えることができる。
【００３３】
≪経路情報管理システム３０の構成例≫
次に、本実施形態における経路情報管理システムの構成例を、図２を用いて説明する。図２に示すように、ＡＳ１内の経路情報管理システム３０は、３つのルートサーバ１０（１０Ａ，１０Ｂ，１０Ｃ）と７つのルータ２０（２０Ａ，２０Ｂ，２０Ｃ，２０Ｄ，２０Ｅ，２０Ｆ，２０Ｇ）とを含んで構成される。なお、図２に示したルータ２０は、他のＡＳから経路情報をｅＢＧＰで受信する境界ルータのみであって、ＡＳ１内の他のルータの記載を省略している。また、図２では、実線矢印や破線矢印によって、情報の流れを示している。したがって、図２では、ルートサーバ１０とルータ２０との接続表記を省略しているが、実線矢印で示した箇所はｉＢＧＰによる通信を可能とし、破線矢印で示した箇所はｅＢＧＰによる通信を可能とする。なお、ルータ２０は、他のＡＳのルータと直結されている。
【００３４】
図２に示すように、ルートサーバ１０は、ルートサーバ１０Ａ，１０Ｂ，１０Ｃごとに、ルートサーバ１０を識別する経路管理装置ＩＤ（ＩＤ）＝５，１０，１５が付与されている。なお、経路管理装置ＩＤは、ＡＳ１のネットワークを管理しているオペレータによって付与される。そして、各ルートサーバ１０は、ルータ２０に対して、自身がルートサーバ１０であることおよびその経路管理装置ＩＤを、ＩＧＰを用いて広告する。
【００３５】
ルートサーバ１０は、経路情報を、プレフィックスごとに分担して管理している。図２の例では、説明を簡単にするために、各ルートサーバ１０Ａ，１０Ｂ，１０Ｃは、それぞれプレフィックスＰ１〜Ｐ５，Ｐ６〜Ｐ１０，Ｐ１１〜Ｐ１５を含む経路情報を管理するものとする。なお、本実施形態では、各ルートサーバ１０によって管理されるプレフィックスＰは、後記するルートサーバ決定方法を用いて決定される。
【００３６】
図２に示すように、ルータ２０は、ｅＢＧＰによって、外部のプレフィックスＰを含む経路情報を受け取ると、ＩＢＧＰを用いて、該当するプレフィックスＰを管理するルートサーバ１０に、その経路情報を広告する。なお、ルータ２０は、後記するルートサーバ決定方法を用いて、広告すべきルートサーバ１０を特定する。図２では、プレフィックスＰ１，Ｐ２を含む経路情報はルートサーバ１０Ａに広告され、プレフィックスＰ６，Ｐ９を含む経路情報はルートサーバ１０Ｂに広告され、プレフィックスＰ１２を含む経路情報はルートサーバ１０Ｃに広告される。これによって、各ルートサーバ１０は、自身の担当するプレフィックスＰに係る経路情報の全てを収集することが可能となる。
【００３７】
≪ルートサーバ決定方法≫
ここで、ルータ２０におけるルートサーバ決定方法について、図３を用いて説明する。
図３は、○印で示すノードとそれをカバーするハッシュ空間を表している。図３中の○印の中の数字は、ＩＤ番号（経路管理装置ＩＤ）を示している。したがって、図２に示すルートサーバ１０Ａ（ＩＤ＝５），１０Ｂ（ＩＤ＝１０），１０Ｃ（ＩＤ＝１５）はそれぞれ、図３の５，１０，１５にマッピングされる。
【００３８】
そして、まず、next(ｋ)という関数を導入する。next(ｋ)はハッシュ空間においてハッシュ空間を時計回り（つまりＩＤを大きくする方向）で次のノードのＩＤを返す。例えば、next(2)=5、next(6)=10、next(15)=15となる。すなわち、next(ｋ)は、ハッシュ空間のある値ｋ以上の範囲において最小の値となるＩＤ（経路管理装置ＩＤ）を返す。
ここで、ｋは、プレフィックスＰの値をハッシュ関数に代入して算出されたハッシュ値である。ただし、図３では、０＜ｋ≦１５とする。
【００３９】
そして、図３に示すように、ハッシュ空間におけるルートサーバ１０Ａの分担範囲は０超え５以下、ルートサーバ１０Ｂの分担範囲は５超え１０以下、ルートサーバ１０Ｃの分担範囲は１０超え１５以下となる。このようにして、ルートサーバ１０のＩＤを予め決めておけば、プレフィックスＰに関する経路情報を問い合わせるルートサーバ１０を特定することが可能となる。
【００４０】
なお、本実施形態では、ルートサーバ１０を複数設ける構成としているので、ルートサーバ１０の追加や削除を容易に行える必要がある。そこで、まず、ルートサーバ１０の追加について、図４を用いて説明する。
図４に示すように、ＩＤ＝８のルートサーバ１０Ｆが新たに追加設定される場合について説明する。まず、ＩＤ＝８のルートサーバ１０Ｆは、next(k=8)として、時計回り（つまりＩＤを大きくする方向）で次のノードのＩＤ（図４ではルートサーバ１０Ｂ（ＩＤ＝１０））に自分の存在をＩＧＰを用いて広告する。そして、ルートサーバ１０Ｆは、ルートサーバ１０Ｂの分担範囲であった５＜ｋ≦１０の中から、５＜ｋ≦８の経路情報を分けてもらう。また、ルートサーバ１０Ｂは、分担範囲を８＜ｋ≦１０に変更する。なお、本実施形態では、各ルートサーバ１０は、ＡＳ１内のルータ２０に対して、ＩＧＰを用いて、自身がルートサーバ１０であることおよび自身のＩＤを広告する。
【００４１】
次に、ＩＤ＝８のルートサーバ１０Ｆが削除される場合について図４を用いて説明する。削除の場合を想定して、予め、各ルートサーバ１０が、少なくとも、反時計回りで次のノードのＩＤの経路情報を記憶しているようにしておく。すなわち、ルートサーバ１０Ｂが、ＩＤ＝８のルートサーバ１０Ｆの経路情報を記憶していれば、ＩＤ＝８のルートサーバ１０Ｆが故障等によって削除されても、５＜ｋ≦８に係る経路情報が失われることはない。
【００４２】
≪ルートサーバ１０の機能≫
次に、本実施形態の経路情報管理システムに用いられるルートサーバ１０の機能について、図５を用いて説明する。図５は、図２のルートサーバ１０の機能ブロック図である。なお、図５は、本実施形態において特徴となる、ルートサーバ１０の主要な機能のみを示し、ｉＢＧＰやＩＧＰ等に係る機能については記載を省略している。
【００４３】
図５に示すように、ルートサーバ１０は、経路情報や経路決定情報等の各種データの入出力を司る入出力部１１と、経路情報の収集や収集した経路情報に基づいて決定した経路決定情報を生成する処理部１２と、記憶部１３とを備える。
入出力部１１は、ルータ２０等とのデータ入出力を行う入出力インタフェースである。入出力部１１におけるデータ入出力は、処理部１２からの指示に基づいて行われる。
【００４４】
処理部１２は、ルートサーバ１０が備える図示しないＣＰＵ（Central Processing Unit）と図示しないメインメモリによって構成されている。そして、このＣＰＵがメインメモリにアプリケーションプログラムを展開して、それを実行することにより種々の演算処理を具現化する。なお、アプリケーションプログラムは、記憶部１３に格納されている。
【００４５】
また、処理部１２は、少なくとも、経路情報収集部１２１と経路決定部１２２とを機能として備えている。
経路情報収集部１２１は、ルータ２０から自身のルートサーバ１０に広告されてくる経路情報を受信する。なお、ルータ２０から広告されてくる経路情報は、予め、ルータ２０によって広告先のルートサーバ１０を選択されたものとなっている。そして、経路情報収集部１２１は、受信した経路情報を記憶部１３の経路表１３１に記憶する。
経路決定部１２２は、ルータ２０から、転送経路の問い合わせを受けたときに、記憶部１３から経路表１３１に記憶されている経路情報とトポロジ情報１３２とを読み出して、予め決めておいた所定の経路決定手順に基づいて、問い合わせをしてきたルータ２０を起点とする最適経路情報および次善の経路情報（経路決定情報）を生成する。そして、生成した経路決定情報を、問い合わせをしてきたルータ２０に返信する。
【００４６】
記憶部１３は、少なくとも、経路表１３１（図６参照）およびトポロジ情報１３２を記憶している。この経路表１３１は、図６に示すように、例えば、プレフィックスとパス属性情報とを含んでいる。パス属性情報は、Local_pref、AS-path、ＭＥＤ（Multi_Exit_Disc）、この経路情報を受信したルータ２０を識別する情報および受信に使用されたプロトコル種別（ｅＢＧＰ／ｉＢＧＰ）、ネクストホップに至る経路に割り当てられたコスト等である。そして、パス属性情報は、プレフィックスＰごとに関連付けられている。また、トポロジ情報１３２は、ＡＳ内のルータ２０間の接続状態を表す情報である。
【００４７】
パス属性情報のうち、Local_prefは、同じＡＳ内のルータ２０間で通知される属性である。同じプレフィックスに対して複数の経路が存在する場合、Local_prefが大きい経路ほど優先される。
AS-pathは、経由してきたＡＳを記録しておくためのものであり、ＡＳを経由するごとにＡＳ番号が追加される。そして、AS-pathに記録されたＡＳ番号の数が少ない方の経路が優先して用いられる。
ＭＥＤは、接続相手のＡＳとの間に複数のピアが存在するときに、どのピアを使うかを相手のＡＳが指定するときに使われる。ルータ２０は、ｅＢＧＰによって同じ宛先の経路情報を複数受信すると、ＭＥＤ値が小さい方の経路が優先される。
【００４８】
図６に示す「受信したルータの識別情報および受信に使用されたプロトコル種別（ｅＢＧＰ／ｉＢＧＰ）」は、問い合わせをしてきたルータ２０の識別情報と一致するか否かの判定に使われる。すなわち、問い合わせをしてきたルータ２０がｅＢＧＰで受信した経路情報が、他のルータ２０によって受信された経路情報よりも優先される。なお、識別情報に一致するものがない場合には、ｉＢＧＰによって受信された経路情報が選択される。ここで、ルータの識別情報とは、例えば、問い合わせを行うときにパケットのヘッダ等に付けられる論理アドレスや物理アドレスや名称等である。
図６に示す「ネクストホップに至る経路に割り当てられたコスト」は、ネクストホップに至る経路について、経路を構成するリンクごとに割り当てられたコストを合計した値である。コストの合計が小さい経路が優先される。
【００４９】
≪ルータ２０の機能≫
次に、本実施形態における経路情報管理システムに用いられるルータ２０（境界ルータおよびＡＳ内に配置されるルータ）の機能について、図７を用いて説明する。図７は、図２のルータ２０の機能ブロック図である。なお、図７は、本実施形態において特徴となる、ルータ２０の主要な機能のみを示し、他のルータ２０との間のデータ送受信やｉＢＧＰやＩＧＰ等に係る機能については記載を省略している。
【００５０】
図７に示すように、ルータ２０は、経路情報や経路決定情報等の各種データの入出力を司る入出力部２１と、経路情報の収集や収集した経路情報の広告先の決定等を行う処理部２２と、記憶部２３とを備える。
入出力部２１は、ルートサーバ１０とのデータ入出力を行う入出力インタフェースである。入出力部２１におけるデータ入出力は、処理部２２からの指示に基づいて行われる。
【００５１】
処理部２２は、ルータ２０が備える図示しないＣＰＵ（Central Processing Unit）と図示しないメインメモリによって構成されている。そして、このＣＰＵがメインメモリにアプリケーションプログラムを展開して、それを実行することにより種々の演算処理を具現化する。なお、アプリケーションプログラムは、記憶部２３に格納されている。
【００５２】
また、処理部２２は、少なくとも、経路情報収集部２２１、ルートサーバ選択部２２２、経路問い合わせ部２２３、および経路決定情報受信部２２４を機能として備えている。
経路情報収集部２２１は、他のＡＳのルータ２０からｅＢＧＰによって広告されてくる経路情報を受信する。そして、経路情報収集部２２１は、他のＡＳから受信した経路情報を記憶部２３に記憶する。
ルートサーバ選択部２２２は、経路情報収集部２２１が他のＡＳのルータ２０からｅＢＧＰによって広告されてくる経路情報を受信したときに、前記したルートサーバ決定方法に基づいて、この経路情報を広告すべきルートサーバ１０を選択する。そして、ルートサーバ選択部２２２は、他のＡＳから受信した経路情報を、選択したルートサーバ１０へ広告する。
【００５３】
経路問い合わせ部２２３は、パケットを受信したとき、そのパケットに含まれている宛先（プレフィックスＰ）を抽出して、前記したルートサーバ決定方法に基づいて、パケットの転送経路の問い合わせ情報を送信すべきルートサーバ１０を選択する。そして、経路問い合わせ部２２３は、受信したパケットの転送経路を問い合わせるために、選択したルートサーバ１０に、宛先（プレフィックスＰ）に係る情報を含む問い合わせ情報を送信する。なお、問い合わせ情報には、問い合わせ情報を送信するルータ２０を識別する情報（例えば、ＩＰアドレス等）が含まれている。
【００５４】
経路決定情報受信部２２４は、経路問い合わせ部２２３によって送信した問い合わせ情報に対する回答情報を、ルートサーバ１０から受信する。回答情報とは、すなわち、経路決定情報（最適経路情報および次善の経路情報）である。経路決定情報受信部２２４は、受信した経路決定情報を記憶部２３の経路表２３１に記憶する。ただし、経路決定情報受信部２２４は、公知のｉＢＧＰセッションを利用して経路決定情報を受信するので、特別な機能を追加される必要はない。
【００５５】
記憶部２３は、少なくとも、ルートサーバ１０によって決定された経路決定情報を格納する経路表２３１およびルートサーバ１０のＩＤを格納するルートサーバＩＤ表２３２を記憶する。なお、ルートサーバ１０によって決定された経路決定情報がルーティングにおいて参照されるため、記憶部２３は、広告されてきた経路情報を記憶する必要がなくなる。また、経路表２３１は、経路決定情報以外にも、パケットを転送する方路を決定するための情報を記憶している。また、ルートサーバＩＤ表２３２は、ＩＤとルートサーバ１０とを関連付けた情報を格納しており、前記したルートサーバ決定方法において、ルータ２０がルートサーバ１０のＩＤを参照するときに用いられる。
【００５６】
≪ルートサーバ１０の経路情報収集手順≫
次に、ルートサーバ１０が、ルータ２０から経路情報を収集する手順について、図８を用いて説明する。
図８に示すように、まず、ルータ２０（境界ルータ）が、他のＡＳから経路情報を取得する（ステップＳ７０１）。次に、該ルータ２０は、取得した経路情報に含まれるプレフィックスＰを抽出して、前記したルートサーバ決定方法に基づいて、広告すべきルートサーバ１０を選択する（ステップＳ７０２）。そして、該ルータ２０は、選択したルートサーバ１０に経路情報を広告する（ステップＳ７０３）。ルートサーバ１０は、広告された経路情報を受信し、経路表１３１（図５参照）に記憶する（ステップＳ７０４）。
【００５７】
≪ルータ２０の経路決定情報取得手順≫
次に、ルータ２０が、ルートサーバ１０から経路決定情報を取得する手順について、図９を用いて説明する。
図９に示すように、まず、ルータ２０がパケットを受信する（ステップＳ８０１）。次に、該ルータ２０は、受信したパケットに含まれる宛先のプレフィックスＰを抽出し、その抽出したプレフィックスＰを用いて、前記したルートサーバ決定方法に基づいて、広告すべきルートサーバ１０を選択する（ステップＳ８０２）。そして、選択したルートサーバ１０に転送すべき経路を問い合わせ情報を送信する（ステップＳ８０３）。
【００５８】
問い合わせを受けたルートサーバ１０は、後記する経路決定手順処理を実行する（ステップＳ８０４）。そして、ルートサーバ１０は、経路決定手順処理に基づいて決定した経路情報を含む経路決定情報を、問い合わせてきたルータ２０に送信する（ステップＳ８０５）。
該ルータ２０は、経路決定情報を受信する（ステップＳ８０６）。そして、受信した経路決定情報に基づいて、パケットを転送する（ステップＳ８０７）。
【００５９】
≪経路決定手順処理≫
次に、ルートサーバ１０における経路決定手順処理の詳細について、図１０を用いて説明する（適宜図２，図５，図６参照）。なお、経路決定手順処理は、図９のステップＳ８０４における処理のことである。
まず、ルートサーバ１０は、宛先へ向かう経路が一つか否かを判定する（ステップＳ９０１）。宛先へ向かう経路が１つでない場合（ステップＳ９０１でＮｏ）、ルートサーバ１０は、Local_Prefの値が最も大きい経路を選択する（ステップＳ９０２）。次に、ルートサーバ１０は、ステップＳ９０２において選択した経路が一つか否かを判定する（ステップＳ９０３）。選択した経路が１つでない場合（ステップＳ９０３でＮｏ）、ルートサーバ１０は、AS-pathの値が最も短い経路を選択する（ステップＳ９０４）。
【００６０】
次に、ルートサーバ１０は、ステップＳ９０４において選択した経路が一つか否かを判定する（ステップＳ９０５）。選択した経路が１つでない場合（ステップＳ９０５でＮｏ）、ルートサーバ１０は、ＭＥＤの値が最も小さい経路を選択する（ステップＳ９０６）。次に、ルートサーバ１０は、ステップＳ９０６において選択した経路が一つか否かを判定する（ステップＳ９０７）。選択した経路が１つでない場合（ステップＳ９０７でＮｏ）、ルートサーバ１０は、ｅＢＧＰで受信した経路を優先して選択し、該当するものがない場合は、ｉＢＧＰで受信した経路を選択する（ステップＳ９０８）。
【００６１】
つまり、ステップＳ９０８では、ルートサーバ１０の経路決定部１２２は、経路表１３１（図６参照）を参照して、問い合わせ情報を送信してきたルータ２０について「ルータの識別情報」に一致するもがあるか否かを検索し、「ルータの識別情報」に一致するものがあった場合には、ｅＢＧＰで受信した経路情報があるか否かを検索する。そして、ｅＢＧＰで受信した経路情報がない場合には、ｉＢＧＰによって受信された経路情報が検索される。すなわち、ｅＢＧＰで受信した経路が、ｉＢＧＰで受信された経路よりも優先される。なお、「ルータを識別情報」に一致するものがない場合には、他のルータ２０によって受信された経路が選択される。
【００６２】
次に、ルートサーバ１０は、ステップＳ９０８において選択した経路が一つか否かを判定する（ステップＳ９０９）。選択した経路が１つでない場合（ステップＳ９０９でＮｏ）、ルートサーバ１０は、ネクストホップに至る経路に割り当てられたコストの最も小さい経路を選択する（ステップＳ９１０）。つまり、ステップＳ９１０では、経路決定部１２２が、トポロジ情報１３２を参照して、問い合わせをしてきたルータ２０または図示しない境界ルータ以外のＡＳ１内のルータのトポロジ上の位置を特定し、転送経路の候補となる経路に付与されるコストの最も小さい経路を転送経路として選択する。次に、ルートサーバ１０は、ステップＳ９１０において選択した経路が一つか否かを判定する（ステップＳ９１１）。このステップＳ９１０によっても、トポロジ上のルータの位置が考慮されることになる。そして、選択した経路が１つでない場合（ステップＳ９１１でＮｏ）、ルートサーバ１０は、いずれか１つの経路を決定または複数の経路を決定する（ステップＳ９１２）。
【００６３】
なお、ステップＳ９０１、ステップＳ９０３、ステップＳ９０５、ステップＳ９０７、ステップＳ９０９、ステップＳ９１１において、選択した経路が１つとなった場合（前記各ステップでＹｅｓ）、処理はステップＳ９１３へ進む。
そして、ルートサーバ１０は、決定した経路情報を含む経路決定情報をルータ２０に送信する（ステップＳ９１３）。なお、ステップＳ９１３の処理は、図９に示すステップＳ８０５の処理と同じである。
【００６４】
ただし、ステップＳ９０１、ステップＳ９０３、ステップＳ９０５、ステップＳ９０７、ステップＳ９０９、ステップＳ９１１において、選択した経路が１つとなった場合（前記各ステップでＹｅｓ）、次善の経路を選択するためには、既に最適経路として選択された経路を除いて、ステップＳ９０１からの経路決定手順処理を行う必要がある。
【００６５】
≪具体例≫
図１０に示す経路決定手順処理の具体例について、図１０および図１１を用いて説明する。
まず、図１１に示すように、経路情報管理システム３０は、ＡＳ１内に、経路情報の収集およびルーティングの管理を行うルートサーバ１０Ｄおよび複数のルータ２０を備えている。そして、ルートサーバ１０Ｄは、ルータ２０と通信可能に接続される。また、各ルータ２０間は、実線（直線）で示されるように通信可能に接続されている。そして、実線（直線）の近傍に記されている数値（１，１０，１００）は、その経路のコストを表している。なお、図１１は一例であり、ルートサーバ１０Ｄ以外のルートサーバの記載を省略している。
【００６６】
いま、ＡＳ１内のルータ２０Ｈ，２０Ｉ，２０Ｍ，２０Ｎが、プレフィックスＰ１を含む経路情報をｅＢＧＰによって受信したものとする。そして、受信したプレフィックスＰ１を含む経路情報は、ルートサーバ１０Ｄに収集される。なお、ルートサーバ１０Ｄに収集されたプレフィックスＰ１を含む経路情報が、いずれもLocal_prefおよびAS-pathが同じで、ＭＥＤが設定されていないものとする。
いま、ルータ２０Ｌに宛先がプレフィックスＰ１のパケットが到着したとき、ルータ２０Ｌは、プレフィックスＰ１に係る経路情報を有しているルートサーバ１０Ｄへ、問い合せを行う。
【００６７】
次に、図１０に移って、経路決定手順処理の経過について説明する。
まず、ステップＳ９０１では、プレフィックスＰ１を宛先とする経路情報は、４つ（ルータ２０Ｈ，２０Ｉ，２０Ｍ，２０Ｎが受信したもの）ある。したがって、ステップＳ９０２へ進む。ステップＳ９０２では、Local_prefの値は４つとも同じであるので、全て選択され、ステップＳ９０４へ進む。ステップＳ９０４では、AS-pathが４つとも同じであるので、全て選択され、ステップＳ９０６へ進む。ステップＳ９０６では、４つともＭＥＤが設定されていないので、全て選択され、ステップＳ９０８へ進む。
ステップＳ９０８では、ルータ２０Ｌの識別情報を含む経路情報は存在しない（ルータ２０Ｌは、プレフィックスＰ１の経路情報を受信していない）ので、４つとも選択され、ステップＳ９１０に進む。
【００６８】
そして、ステップＳ９１０では、ネクストホップに至る経路に割り当てられたコストの最も小さい経路が選択される。すなわち、図１１に示される構成では、ルータ２０Ｌからルータ２０Ｈ，２０Ｉまでのコストの合計は１０２（＝１＋１００＋１）となり、ルータ２０Ｌからルータ２０Ｍ，２０Ｎまでのコストの合計は２０２（＝１＋１００＋１００＋１）となる。すなわち、ステップＳ９１０において、ルータ２０Ｈ，２０Ｉが選択され、ステップＳ９１２に進む。そして、ステップＳ９１２では、最適経路および次善の経路が選択される。次に、ステップＳ９１３において、ステップＳ９１２において選択された最適経路および次善の経路を含む経路決定情報が、ルータ２０Ｌに送信される。
【００６９】
図１１に戻って、ルートサーバ１０Ｄから、経路決定情報として、［プレフィックス：Ｐ１、ネクストホップ：ルータ２０Ｈ、プレファレンス値：100、・・］、および［プレフィックス：Ｐ１、ネクストホップ：ルータ２０Ｉ、プレファレンス値：50、・・］が、ルータ２０Ｌに送信される。ルータ２０Ｌは、プレファレンス値を比較して、大きい方（プレファレンス値１００）を優先して（最適経路と判定して）、ルーティングを行う。なお、プレファレンス値５０の経路は、次善の経路と判定され、ルータ２０Ｈが利用できなくなったときに用いられる。
【００７０】
以上、本実施形態の経路情報管理システム３０によれば、ＡＳ内に複数の経路管理装置を備えているため、ＡＳ内のルータ数の増加に対して設備の大幅な更改を抑制でき、プレフィックスごとの経路情報を全て把握できるようにし、ＡＳ内の経路情報を統一し、ネクストホップとの通信が切断した際に新しい経路に容易に切り替える技術を提供することが可能となる。
【００７１】
なお、本実施形態は、これらに限定されるものではなく、その趣旨を変えない範囲で実施することができる。
例えば、本実施形態では、ルートサーバ１０の識別番号（ＩＤ）は、ＡＳ１のネットワークを管理しているオペレータによって付与されるものとしたが、各ルートサーバ間で、分担範囲がほぼ均等あるいは既に付与されているＩＤの中央となるＩＤを割り振るというように、ＩＤの決め方を予め定めたルールに基づいて特定のルートサーバが自動的に割り振るようにしても構わない。
【符号の説明】
【００７２】
１      ＡＳ
１０    ルートサーバ（経路管理装置）
１２    処理部
１３    記憶部
２０    ルータ（境界ルータ、中継ルータ）
２２    処理部
２３    記憶部
３０    経路情報管理システム
１２１  経路情報収集部
１２２  経路決定部
１３１  経路表
１３２  トポロジ情報
２２１  経路情報収集部
２２２  ルートサーバ選択部
２２３  経路問い合わせ部
２２４  経路決定情報受信部
２３１  経路表
２３２  ルートサーバＩＤ表
【図１】
2010199800.tif 000003
【図２】
2010199800.tif 000004
【図３】
2010199800.tif 000005
【図４】
2010199800.tif 000006
【図５】
2010199800.tif 000007
【図６】
2010199800.tif 000008
【図７】
2010199800.tif 000009
【図８】
2010199800.tif 000010
【図９】
2010199800.tif 000011
【図１０】
2010199800.tif 000012
【図１１】
2010199800.tif 000013
【図１２】
2010199800.tif 000014