(57)【要約】【課題】最短経路の計算にかかる負荷をルータから取り除き、ルータを本来の経路制御処理に専念させることができるようにする。【解決手段】経路計算装置２００は、リンク状態を示すデータ（リンク状態データベース１）に基づいて最短経路を計算する処理を実行する専用の装置として、ルータ１０１，１０２，および１０３とは別個に設けられる。ルータ１０１，１０２，および１０３の各々は、経路計算装置２００の存在によって最短経路の計算にかかる負荷が取り除かれて本来の経路制御処理に専念できる構成を持ち、経路計算装置２００の計算結果を取得することによって自身が始点である最短経路の集合を経路表２に保持することができる。【選択図】　　　　図１
2004032569.tif 000002
【特許請求の範囲】
【請求項１】
ＯＳＰＦによる経路制御が行われるネットワークシステムにおいて、
リンク状態を示すデータに基づいて最短経路を計算する処理を実行する専用の装置として、ルータとは別個に設けられる経路計算装置と、
前記経路計算装置の存在によって最短経路の計算にかかる負荷が取り除かれて本来の経路制御処理に専念できる構成を持ち、前記経路計算装置の計算結果を取得することによって自身が始点である最短経路の集合を保持することができる各ルータと
を有することを特徴とするＯＳＰＦによる経路制御システム。
【請求項２】
ＯＳＰＦによる経路制御が行われるネットワークシステムにおいて、
自ルータが存在しているエリアに属する全ルータおよび全ネットワークのリンク状態を表すデータ群を有している各ルータ内のリンク状態データベースと、
前記リンク状態データベースに基づいて計算された「自ルータが始点の最短経路集合」を示す情報を保持している各ルータ内の経路表と、
ＯＳＰＦにおける「リンク状態データベースの構築を行う機能」を有し、前記リンク状態データベースを構築する各ルータ内のリンク状態データベース構築部と、
自ルータが計算装置接続ルータである場合に、自ルータが持つ前記リンク状態データベースの複製を経路計算装置に送信する各ルータ内のリンク状態データベース送信部と、
自ルータが計算装置接続ルータである場合に、前記経路計算装置によって計算された全ルータに関する最短経路集合を示す経路表情報を前記経路計算装置から受信し、受信した経路表情報中の自ルータに関する最短経路集合を自ルータ内の前記経路表に登録する各ルータ内の経路表情報受信部と、
自ルータが受信した経路表情報から自ルータに関する最短経路集合を削除した残りの経路表情報を隣接するルータに送信する各ルータ内のルータ間経路表情報送信部と、
隣接するルータから送信されてくる経路表情報を受信し、受信した経路表情報中の自ルータに関する最短経路集合を自ルータ内の前記経路表に登録する各ルータ内のルータ間経路表情報受信部と、
計算装置接続ルータから送られてくる前記リンク状態データベースの複製を受信するリンク状態データベース受信部と、前記リンク状態データベース受信部により受信された前記リンク状態データベースの複製に基づいて最短経路の計算を行って全ルータに関する最短経路集合を生成する最短経路計算部と、前記最短経路計算部により計算・生成された最短経路集合を示す経路表情報を計算装置接続ルータに送信する経路表情報送信部とを持ち、１つのエリアに１つ設けられている前記経路計算装置と
を有することを特徴とするＯＳＰＦによる経路制御システム。
【請求項３】
ルータ間経路表情報受信部が、「受信した経路表情報から抽出した自ルータに関する最短経路集合を経路表に登録する処理」を行う際に、「その登録対象の情報がすでに登録済みであるか否かをチェックし、当該チェックで「登録済みである」と判定した場合には、当該登録処理を行うことなくルータ間経路表情報送信部に制御を渡し、当該チェックで「登録済みでない」と判定した場合には当該登録処理を行う」という付加的な動作を行うことを特徴とする請求項２記載のＯＳＰＦによる経路制御システム。
【請求項４】
ＯＳＰＦによる経路制御が行われるネットワークシステムにおいて、
自ルータが存在しているエリアに属する全ルータおよび全ネットワークのリンク状態を表すデータ群を有している各ルータ内のリンク状態データベースと、
前記リンク状態データベースに基づいて計算された「自ルータが始点の最短経路集合」を示す情報を保持している各ルータ内の経路表と、
ＯＳＰＦにおける「リンク状態データベースの構築を行う機能」を有し、前記リンク状態データベースを構築する各ルータ内のリンク状態データベース構築部と、
自ルータが持つ前記リンク状態データベースの複製を自ルータに接続している経路計算装置に送信する各ルータ内のリンク状態データベース送信部と、
自ルータに接続している前記経路計算装置によって計算された全ルータに関する最短経路集合を示す経路表情報を自ルータに接続している前記経路計算装置から受信し、受信した経路表情報中の自ルータに関する最短経路集合を自ルータ内の前記経路表に登録する各ルータ内の経路表情報受信部と、
ルータから送られてくる前記リンク状態データベースの複製を受信するリンク状態データベース受信部と、前記リンク状態データベース受信部により受信された前記リンク状態データベースの複製に基づいて最短経路の計算を行って全ルータに関する最短経路集合を生成する最短経路計算部と、前記最短経路計算部により計算・生成された最短経路集合を示す経路表情報をルータに送信する経路表情報送信部とを持ち、全ルータの各々に対して１台ずつ設けられている前記経路計算装置と
を有することを特徴とするＯＳＰＦによる経路制御システム。
【請求項５】
各ルータ内にリンク状態データベース，経路表，リンク状態データベース構築部，リンク状態データベース送信部，経路表情報受信部，ルータ間経路表情報送信部，およびルータ間経路表情報受信部を設け、さらに、各ルータに固有の経路計算装置を接続しうるようにした上で、「１つのエリアに１つだけ経路計算装置を設ける」という請求項２記載の発明における処理の態様にも、「各ルータに対してそれぞれ固有の経路計算装置を設ける」という請求項４記載の発明における処理の態様にも対処しうるようにすることを特徴とするＯＳＰＦによる経路制御システム。
【請求項６】
ＯＳＰＦによる経路制御が行われるネットワークシステムにおいて、
ルータとは別個に設けられる専用の装置である経路計算装置を、リンク状態を示すデータに基づいて最短経路を計算する処理を実行するように機能させるための経路計算装置用プログラムと、
各ルータを、前記経路計算装置の存在によって最短経路の計算にかかる負荷が取り除かれて本来の経路制御処理に専念できる構成を持ち、前記経路計算装置の計算結果を取得することによって自身が始点である最短経路の集合を保持することができるように機能させるためのルータ用プログラムと
を有することを特徴とするＯＳＰＦによる経路制御システム。
【請求項７】
ＯＳＰＦによる経路制御が行われるネットワークシステムにおいて、
自ルータが存在しているエリアに属する全ルータおよび全ネットワークのリンク状態を表すデータ群を有している各ルータ内のリンク状態データベースならびに前記リンク状態データベースに基づいて計算された「自ルータが始点の最短経路集合」を示す情報を保持している各ルータ内の経路表が存在することになることを前提として、
各ルータを、ＯＳＰＦにおける「リンク状態データベースの構築を行う機能」を有し、前記リンク状態データベースを構築するリンク状態データベース構築部，自ルータが計算装置接続ルータである場合に、自ルータが持つ前記リンク状態データベースの複製を経路計算装置に送信するリンク状態データベース送信部，自ルータが計算装置接続ルータである場合に、前記経路計算装置によって計算された全ルータに関する最短経路集合を示す経路表情報を前記経路計算装置から受信し、受信した経路表情報中の自ルータに関する最短経路集合を自ルータ内の前記経路表に登録する経路表情報受信部，自ルータが受信した経路表情報から自ルータに関する最短経路集合を削除した残りの経路表情報を隣接するルータに送信するルータ間経路表情報送信部，および隣接するルータから送信されてくる経路表情報を受信し、受信した経路表情報中の自ルータに関する最短経路集合を自ルータ内の前記経路表に登録するルータ間経路表情報受信部として機能させるためのルータ用プログラムと、
１つのエリアに１つ設けられている経路計算装置を、計算装置接続ルータから送られてくる前記リンク状態データベースの複製を受信するリンク状態データベース受信部，前記リンク状態データベース受信部により受信された前記リンク状態データベースの複製に基づいて最短経路の計算を行って全ルータに関する最短経路集合を生成する最短経路計算部，および前記最短経路計算部により計算・生成された最短経路集合を示す経路表情報を計算装置接続ルータに送信する経路表情報送信部として機能させるための経路計算装置用プログラムと
を有することを特徴とするＯＳＰＦによる経路制御システム。
【請求項８】
ＯＳＰＦによる経路制御が行われるネットワークシステムにおいて、
自ルータが存在しているエリアに属する全ルータおよび全ネットワークのリンク状態を表すデータ群を有している各ルータ内のリンク状態データベースならびに前記リンク状態データベースに基づいて計算された「自ルータが始点の最短経路集合」を示す情報を保持している各ルータ内の経路表が存在することになることを前提として、
各ルータを、ＯＳＰＦにおける「リンク状態データベースの構築を行う機能」を有し、前記リンク状態データベースを構築するリンク状態データベース構築部，自ルータが持つ前記リンク状態データベースの複製を自ルータに接続している経路計算装置に送信するリンク状態データベース送信部，および自ルータに接続している前記経路計算装置によって計算された全ルータに関する最短経路集合を示す経路表情報を自ルータに接続している前記経路計算装置から受信し、受信した経路表情報中の自ルータに関する最短経路集合を自ルータ内の前記経路表に登録する経路表情報受信部として機能させるためのルータ用プログラムと、
全ルータの各々に対して１台ずつ設けられている経路計算装置を、ルータから送られてくる前記リンク状態データベースの複製を受信するリンク状態データベース受信部，前記リンク状態データベース受信部により受信された前記リンク状態データベースの複製に基づいて最短経路の計算を行って全ルータに関する最短経路集合を生成する最短経路計算部，および前記最短経路計算部により計算・生成された最短経路集合を示す経路表情報をルータに送信する経路表情報送信部として機能させるための経路計算装置用プログラムと
を有することを特徴とするＯＳＰＦによる経路制御システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ルータ（経路制御装置）とネットワーク（ルータとルータとを接続する回線群および端末群）との接続状態であるリンク状態に基づいて経路制御を行うリンク状態経路制御プロトコルの１つであるＯＳＰＦ（Ｏｐｅｎ　Ｓｈｏｒｔｅｓｔ　Ｐａｔｈ　Ｆｉｒｓｔ）によって実現される経路制御システム（ＯＳＰＦによる経路制御システム）に関する。
【０００２】
【従来の技術】
リンク状態経路制御プロトコルの１つであるＯＳＰＦは、比較的大規模なネットワークシステムにおいて経路制御を行うために考案された経路制御プロトコルである。
【０００３】
すなわち、ＯＳＰＦは、ＩＥＴＦ（Ｉｎｔｅｒｎｅｔ　ＥｎｇｉｎｅｅｒｉｎｇＴａｓｋ　Ｆｏｒｃｅ）によりＲＦＣ（Ｒｅｑｕｅｓｔ　Ｆｏｒ　Ｃｏｍｍｅｎｔｓ）２３２８として公開されているリンク状態経路制御に関する経路制御プロトコルである。
【０００４】
このＯＳＰＦの特徴は、従来の距離ベクトル型経路制御プロトコルが、自身の持つ経路表全体の複製をルータ間で交換するのに対して、ルータ間でリンク状態のみを交換し、最短経路の計算は個々のルータが行う点にある。
【０００５】
これにより、ＯＳＰＦは、従来の距離ベクトル型アルゴリズムに比べ、「ルータ間で交換するデータ量が非常に小さく、また、その大きさがネットワークシステムの規模に拠らず小さくできる」という利点を生じさせている。
【０００６】
上述のようなＯＳＰＦは、ＯＳＰＦが動作するルータの集合であるＡＳ（Ａｕｔｏｎｏｍｏｕｓ　Ｓｙｓｔｅｍ。自律システム）を複数のエリアと呼ばれる領域に分割し、あるエリアに所属する全てのルータが同一のリンク状態データベースを持つようにし、個々のルータがそのリンク状態データベースに基づいて自身から全ての宛先への最短経路を計算することを可能にしている。
【０００７】
【発明が解決しようとする課題】
上述した従来の技術（ＯＳＰＦによる経路制御システム）には、ルータのＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）資源を大量に消費するという問題点があった。
【０００８】
このような問題点が存在する理由は、距離ベクトル型アルゴリズムが経路情報の受信および登録を行うだけであるのに対して、リンク状態経路制御プロトコルによると、リンク状態が変更されるたびに全てのルータ上で最短経路の再計算が行われるためである。
【０００９】
この問題点により、最短経路の再計算時には、経路制御プロトコルのタスクがＣＰＵ資源を占有し、ルータ上で動作する他のタスクが動作できなくなるという状況が起きるおそれが生じる。
【００１０】
本発明の目的は、上述の点に鑑み、リンク状態経路制御プロトコルであるＯＳＰＦを動作させているルータ（経路制御装置）を有するネットワークシステムにおいて、リンク状態から最短経路を計算する処理ステップを専用の装置（経路計算装置）に行わせること（最短経路計算用に専用の装置を設け、ルータ自身は最短経路の計算を行わないようにすること）により、最短経路の計算にかかる負荷をルータから取り除き、ルータを本来の経路制御処理に専念させることができるようにし、かつ、各ルータに最短経路の計算をさせることなしに全ルータに最短経路の情報を行き渡らせる（持たせる）ことを可能にし、上記の問題点を解決することができるＯＳＰＦによる経路制御システムを提供することにある。
【００１１】
【課題を解決するための手段】
本発明のＯＳＰＦによる経路制御システムは、ＯＳＰＦによる経路制御が行われるネットワークシステムにおいて、自ルータ（自己が存在するルータ）が存在しているエリアに属する全ルータおよび全ネットワークのリンク状態を表すデータ群を有している各ルータ内のリンク状態データベースと、前記リンク状態データベースに基づいて計算された「自ルータが始点の最短経路集合」を示す情報を保持している各ルータ内の経路表と、ＯＳＰＦにおける「リンク状態データベースの構築を行う機能」を有し、前記リンク状態データベースを構築する各ルータ内のリンク状態データベース構築部と、自ルータが計算装置接続ルータである場合に、自ルータが持つ前記リンク状態データベースの複製を経路計算装置に送信する各ルータ内のリンク状態データベース送信部と、自ルータが計算装置接続ルータである場合に、前記経路計算装置によって計算された全ルータに関する最短経路集合を示す経路表情報を前記経路計算装置から受信し、受信した経路表情報中の自ルータに関する最短経路集合（自ルータが始点の最短経路集合）を自ルータ内の前記経路表に登録する各ルータ内の経路表情報受信部と、自ルータが受信した経路表情報から自ルータに関する最短経路集合を削除した残りの経路表情報を隣接する（自ルータとネットワークによって接続されている）ルータに送信する各ルータ内のルータ間経路表情報送信部と、隣接するルータから送信されてくる経路表情報を受信し、受信した経路表情報中の自ルータに関する最短経路集合（自ルータが始点の最短経路集合）を自ルータ内の前記経路表に登録する各ルータ内のルータ間経路表情報受信部と、計算装置接続ルータから送られてくる前記リンク状態データベースの複製を受信するリンク状態データベース受信部と、前記リンク状態データベース受信部により受信された前記リンク状態データベースの複製に基づいて最短経路の計算を行って全ルータに関する最短経路集合を生成する最短経路計算部と、前記最短経路計算部により計算・生成された最短経路集合を示す経路表情報を計算装置接続ルータに送信（返送）する経路表情報送信部とを持ち、１つのエリアに１つ設けられている前記経路計算装置とを有する。
【００１２】
また、本発明のＯＳＰＦによる経路制御システムは、ＯＳＰＦによる経路制御が行われるネットワークシステムにおいて、自ルータが存在しているエリアに属する全ルータおよび全ネットワークのリンク状態を表すデータ群を有している各ルータ内のリンク状態データベースと、前記リンク状態データベースに基づいて計算された「自ルータが始点の最短経路集合」を示す情報を保持している各ルータ内の経路表と、ＯＳＰＦにおける「リンク状態データベースの構築を行う機能」を有し、前記リンク状態データベースを構築する各ルータ内のリンク状態データベース構築部と、自ルータが持つ前記リンク状態データベースの複製を自ルータに接続している経路計算装置に送信する各ルータ内のリンク状態データベース送信部と、自ルータに接続している前記経路計算装置によって計算された全ルータに関する最短経路集合を示す経路表情報を自ルータに接続している前記経路計算装置から受信し、受信した経路表情報中の自ルータに関する最短経路集合（自ルータが始点の最短経路集合）を自ルータ内の前記経路表に登録する各ルータ内の経路表情報受信部と、ルータから送られてくる前記リンク状態データベースの複製を受信するリンク状態データベース受信部と、前記リンク状態データベース受信部により受信された前記リンク状態データベースの複製に基づいて最短経路の計算を行って全ルータに関する最短経路集合を生成する最短経路計算部と、前記最短経路計算部により計算・生成された最短経路集合を示す経路表情報をルータに送信（返送）する経路表情報送信部とを持ち、全ルータの各々に対して１台ずつ設けられている前記経路計算装置とを有するように構成することも可能である。
【００１３】
なお、本発明のＯＳＰＦによる経路制御システムは、より一般的には、ＯＳＰＦによる経路制御が行われるネットワークシステムにおいて、リンク状態を示すデータに基づいて最短経路を計算する処理を実行する専用の装置として、ルータとは別個に設けられる経路計算装置と、前記経路計算装置の存在によって最短経路の計算にかかる負荷が取り除かれて本来の経路制御処理に専念できる構成を持ち、前記経路計算装置の計算結果を取得する（受け取る）ことによって自身が始点である最短経路の集合を保持することができる各ルータとを有すると表現することができる。
【００１４】
また、本発明は、ＯＳＰＦによる経路制御が行われるネットワークシステムにおいて、ルータとは別個に設けられる専用の装置である経路計算装置を、リンク状態を示すデータに基づいて最短経路を計算する処理を実行するように機能させるための経路計算装置用プログラムと、各ルータを、前記経路計算装置の存在によって最短経路の計算にかかる負荷が取り除かれて本来の経路制御処理に専念できる構成を持ち、前記経路計算装置の計算結果を取得することによって自身が始点である最短経路の集合を保持することができるように機能させるためのルータ用プログラムとを有するＯＳＰＦによる経路制御システムとして実現することも可能である。
【００１５】
【発明の実施の形態】
次に、本発明について図面を参照して詳細に説明する。
【００１６】
（１）　第１の実施の形態
【００１７】
図１は、本発明の第１の実施の形態に係るＯＳＰＦによる経路制御システムの構成を示すブロック図である。
【００１８】
また、図２は、本実施の形態に係るＯＳＰＦによる経路制御システムが適用されるネットワークシステムの構成を示す図である。
【００１９】
図１および図２を参照すると、本実施の形態に係るＯＳＰＦによる経路制御システムは、ルータ群（ルータ１０１，ルータ１０２，およびルータ１０３）と、ネットワーク群（ネットワーク１０４，ネットワーク１０５，およびネットワーク１０６）と、経路計算装置２００とを含んで構成されている。
【００２０】
図２に示すように、上記のルータ１０１，ルータ１０２，およびルータ１０３は、ＯＳＰＦ上の概念である「エリア」の１つ（「エリア１００」とする）に属しているものとする。
【００２１】
なお、ルータの数やルータとネットワークとの接続態様が図示するものに限定されないことはいうまでもない。さらに、経路計算装置２００はルータ１０１に接続されているが、これは固定的なものではなく、各ルータ間の関係は対等なものである（ルータ１０１が特別なルータというわけではない）。
【００２２】
各ルータ（ルータ１０１／１０２／１０３）は、相互にリンク状態を示す情報を交換し、また、後述の経路表２を用いて経路制御を行う。
【００２３】
各ネットワーク（ネットワーク１０４／１０５／１０６）は、回線群および端末群によって構成されており、ルータ間を接続する。
【００２４】
経路計算装置２００は、１つのエリア（本実施の形態では、エリア１００）に対して１つ配置されており、当該エリア１００に含まれるルータ群中の任意の１つのルータであるルータ１０１（計算装置接続ルータ）に接続されており、当該計算装置接続ルータから受信したリンク状態データベース１の複製（コピーデータ）を用いて最短経路集合を示す経路表情報を生成し、当該経路表情報を当該計算装置接続ルータに返送（送信）する。
【００２５】
ルータ１０１／１０２／１０３は、それぞれ、リンク状態データベース１および経路表２を保持しており、リンク状態データベース構築部３と、リンク状態データベース送信部４と、経路表情報受信部５と、ルータ間経路表情報送信部６と、ルータ間経路表情報受信部７とを含んで構成されている。ここで、リンク状態データベース構築部３によって実現される機能は従来の技術（ＯＳＰＦに関する技術）においても存在する機能であるが、リンク状態データベース送信部４，経路表情報受信部５，ルータ間経路表情報送信部６，およびルータ間経路表情報受信部７によって実現される機能は本発明における新たな機能である。
【００２６】
リンク状態データベース１は、エリア１００に属する全ルータおよび全ネットワークのリンク状態を表すデータ群を有している。リンク状態データベース１の内容は、全ルータにおいて同一のものとなっている。
【００２７】
経路表２は、リンク状態データベース１に基づいて計算された自ルータ（自己が存在するルータ）が始点の最短経路集合を示す情報を保持している。
【００２８】
リンク状態データベース構築部３は、従来の技術においても存在した「リンク状態データベースの構築を行う機能」を有し、従来と同様の手順に従ってリンク状態データベース１を構築する。
【００２９】
リンク状態データベース送信部４は、自ルータが計算装置接続ルータである場合に、自ルータが持つリンク状態データベース１の複製を経路計算装置２００に送信する機能を持つ。
【００３０】
経路表情報受信部５は、自ルータが計算装置接続ルータである場合に、経路計算装置２００によって計算された全ルータに関する最短経路集合（経路表情報）を経路計算装置２００から受信し、受信した経路表情報中の自ルータに関する最短経路集合（自ルータが始点の最短経路集合）を自ルータ内の経路表２に登録する機能を持つ。
【００３１】
ルータ間経路表情報送信部６は、自ルータが受信した経路表情報から自ルータに関する最短経路集合を削除した残りの経路表情報を隣接する（自ルータとネットワークによって接続されている）ルータに送信する機能を持つ。
【００３２】
ルータ間経路表情報受信部７は、隣接するルータから送信されてくる経路表情報を受信し、受信した経路表情報中の自ルータに関する最短経路集合（自ルータが始点の最短経路集合）を自ルータ内の経路表２に登録する機能を持つ。
【００３３】
経路計算装置２００は、リンク状態データベース受信部８と、最短経路計算部９と、経路表情報送信部１０とを含んで構成されている。
【００３４】
リンク状態データベース受信部８は、計算装置接続ルータから送られてくるリンク状態データベース１の複製を受信する機能を持つ。
【００３５】
最短経路計算部９は、従来の技術（ＯＳＰＦに関する技術）においてもルータ上に存在した「最短経路の計算を行う機能」を持ち、リンク状態データベース受信部８により受信されたリンク状態データベース１の複製に基づいて最短経路の計算を行い、全ルータに関する最短経路集合を生成する。
【００３６】
経路表情報送信部１０は、最短経路計算部９により計算・生成された最短経路集合を示す経路表情報を計算装置接続ルータに送信（返送）する機能を持つ。
【００３７】
図３は、本実施の形態に係るＯＳＰＦによる経路制御システムの処理を示す流れ図である。この処理は、リンク状態データベース構築ステップＡ１と、リンク状態データベース複製送信ステップＡ２と、最短経路計算ステップＡ３と、経路表情報送信ステップＡ４と、自ルータ始点最短経路集合抽出ステップＡ５と、経路表登録ステップＡ６と、最短経路集合削除ステップＡ７と、最短経路集合空判定ステップＡ８と、経路表情報隣接ルータ送信ステップＡ９とからなる。
【００３８】
図４は、本実施の形態に係るＯＳＰＦによる経路制御システムの具体的な動作を説明するためのブロック図である。
【００３９】
次に、図１〜図４を参照して、上記のように構成された本実施の形態に係るＯＳＰＦによる経路制御システムの全体の動作について詳細に説明する。
【００４０】
ルータ１０１，ルータ１０２，およびルータ１０３内のリンク状態データベース構築部３は、従来のＯＳＰＦが持つ機能と同様の機能により、図４中の矢線Ａに示すように、リンク状態データベース１を作成（構築）する（図３のステップＡ１）。
【００４１】
ここで、このリンク状態データベース１は、エリア１００に属する全てのルータ（ルータ１０１，ルータ１０２，およびルータ１０３）において、内容が完全に一致している。
【００４２】
次に、計算装置接続ルータ（ルータ１０１）内のリンク状態データベース送信部４は、図４中の矢線Ｂに示すように、ステップＡ１で作成されたリンク状態データベース１の複製（コピーデータ）を経路計算装置２００に送信する（ステップＡ２）。
【００４３】
経路計算装置２００内のリンク状態データベース受信部８は、ステップＡ２で送信されたリンク状態データベース１の複製を受信する。
【００４４】
最短経路計算部９は、リンク状態データベース受信部８により受信されたリンク状態データベース１の複製を用いて、エリア１００に属する全ルータに関する最短経路である「ルータ１０１から全ての宛先への最短経路（ルータ１０１が始点の最短経路集合）」，「ルータ１０２から全ての宛先への最短経路（ルータ１０２が始点の最短経路集合）」，および「ルータ１０３から全ての宛先への最短経路（ルータ１０３が始点の最短経路集合）」を計算する（ステップＡ３）。
【００４５】
経路表情報送信部１０は、ステップＡ３で計算された全ての最短経路の集合（最短経路集合）を、経路表情報として、図４中の矢線Ｃに示すように、計算装置接続ルータ（ルータ１０１）に送り返す（送信する）（ステップＡ４）。
【００４６】
計算装置接続ルータ内の経路表情報受信部５は、ステップＡ４で送信された経路表情報を受信し、受信した経路表情報（最短経路集合）から自ルータに関する最短経路集合（自ルータが始点である全ての最短経路の集合）を抽出し（ステップＡ５）、図４中の矢線Ｄに示すように、抽出した情報（自ルータが始点の最短経路集合）を自ルータ内の経路表２に登録する（ステップＡ６）。
【００４７】
さらに、当該ルータ（ここでは、ルータ１０１）内のルータ間経路表情報送信部６は、ステップＡ５で抽出された最短経路集合（自ルータが始点の最短経路集合）を、経路表情報受信部５またはルータ間経路表情報受信部７（ここでは、経路表情報受信部５）によって受信された経路表情報から削除し（ステップＡ７）、ステップＡ７の削除処理の後の経路表情報中の最短経路集合が空であるか否かをチェック（判定）する（ステップＡ８）。
【００４８】
ルータ間経路表情報送信部６は、ステップＡ８のチェックで「当該最短経路集合が空である」と判定した場合には、図３に示す処理を終了させる。
【００４９】
一方、ルータ間経路表情報送信部６は、ステップＡ８のチェックで「当該最短経路集合が空ではない」と判定した場合には、図４中の矢線Ｅに示すように、自ルータ（ここでは、ルータ１０１）と隣接するルータ（ここでは、ルータ１０２およびルータ１０３）にステップＡ７の削除処理の後の経路表情報を送信する（ステップＡ９）。
【００５０】
当該経路表情報を受信したルータ１０２およびルータ１０３は、ルータ１０１における上記の動作（ステップＡ５〜ステップＡ９の動作）と同様の動作を行うことによって、自ルータに関する最短経路集合（自ルータが始点の最短経路集合）を自ルータ内の経路表２に登録する。
【００５１】
すなわち、例えば、ルータ１０２においては、ルータ間経路表受信部７は、ルータ１０１から送信されてきた経路表情報を受信して、その経路表情報中の最短経路集合から、自ルータ（ルータ１０２）に関する最短経路集合（自ルータが始点である全ての最短経路の集合）を抽出し（ステップＡ５）、図４中の矢線Ｆに示すように、抽出した情報（最短経路集合）を自ルータ内の経路表２に登録する（ステップＡ６）。
【００５２】
さらに、ルータ２内のルータ間経路表情報送信部６は、ステップＡ５で抽出された最短経路集合を、ルータ間経路表情報受信部７により受信された経路表情報から削除し（ステップＡ７）、ステップＡ７の削除処理の後の経路表情報中の最短経路集合が空であるか否かをチェックし（ステップＡ８）、「空である」と判定した場合には図３の処理を終了させ、「空でない」と判定した場合には自ルータ（ルータ１０２）と隣接するルータ（自ルータへの経路表情報の送信元であるルータ１０１を除く）であるルータ１０３に当該経路表情報（ステップＡ７の削除処理の後の経路表情報）を送信する（ステップＡ９）。
【００５３】
なお、上記の第１の実施の形態においては、自ルータに関する最短経路集合が経路表２に登録済みであるにもかかわらず、ルータ間経路表情報受信部７が、自ルータに関する最短経路集合を含む経路表情報を受信する場合が生じうる。このような場合にも、同一の情報が重ねて登録されるにすぎず不都合な結果は生じないが、さらに適切に対処するために、以下のａ〜ｃに示すような特徴（付加的な動作）を有する変形形態を考えることができる。
【００５４】
ａ．各ルータ内のルータ間経路表情報受信部７が、「受信した経路表情報から抽出した自ルータに関する最短経路集合を経路表２に登録する処理」（図３中のステップＡ５およびステップＡ６参照）を行う際に、その登録対象の情報がすでに登録済みであるか否かをチェックする。すなわち、図３における一連の処理の中で、ステップＡ５の処理の次に、ステップＡ５で抽出した情報（自ルータが始点の最短経路集合）が自ルータ内の経路表２にすでに登録済みであるか否かを判定する「登録済み判定ステップＡ５’」を設ける。
【００５５】
ｂ．上述のステップＡ５’で「登録済みである」と判定された場合には、同一の情報の再登録（上書き）を行う無駄を省くために、ルータ間経路表情報送信部６に制御が渡される（図３中のステップＡ６の処理（登録処理）が行われることなく、ステップＡ７の処理に制御が移行する）。
【００５６】
ｃ．上述のステップＡ５’で「登録済みでない」と判定された場合には、先述の処理の通り、図３中のステップＡ６における「経路表２への最短経路集合の登録処理」が行われる。
【００５７】
（２）　第２の実施の形態
【００５８】
図５は、本発明の第２の実施の形態に係るＯＳＰＦによる経路制御システムの構成（動作を説明するための矢線を含む）を示すブロック図である。
【００５９】
また、図６は、本実施の形態に係るＯＳＰＦによる経路制御システムが適用されるネットワークシステムの構成を示す図である。
【００６０】
図５および図６を参照すると、本実施の形態に係るＯＳＰＦによる経路制御システムは、ルータ群（ルータ１０１，ルータ１０２，およびルータ１０３）と、ネットワーク群（ネットワーク１０４，ネットワーク１０５，およびネットワーク１０６）と、経路計算装置群（経路計算装置２０１，経路計算装置２０２，および経路計算装置２０３）とを含んで構成されている。
【００６１】
図６に示すように、上記のルータ１０１，ルータ１０２，およびルータ１０３は、ＯＳＰＦ上の概念である「エリア」の１つ（「エリア１００」とする）に属しているものとする。
【００６２】
図１および図２と図５および図６とを対比して参照すると、第１の実施の形態では１つのエリア（エリア１００）につき１台の経路計算装置（経路計算装置２００）が用意されていたのに対して、本実施の形態（第２の実施の形態）ではエリア１００に属する全ルータに１台ずつ経路計算装置が用意されている点で、両者は異なっている。すなわち、図５および図６に示すように、経路計算装置２０１，経路計算装置２０２，および経路計算装置２０３が、それぞれ、ルータ１０１，ルータ１０２，およびルータ１０３に接続されている。
【００６３】
なお、ルータの数やルータとネットワークとの接続態様が図示するものに限定されないことはいうまでもない。
【００６４】
各ルータ（ルータ１０１／１０２／１０３）は、相互にリンク状態を示す情報を交換し、また、後述の経路表２を用いて経路制御を行う。
【００６５】
各ネットワーク（ネットワーク１０４／１０５／１０６）は、回線群および端末群によって構成されており、ルータ間を接続する。
【００６６】
各経路計算装置（経路計算装置２０１／２０２／２０３）は、自己が接続しているルータ１０１／１０２／１０３から受信したリンク状態データベース１の複製（コピーデータ）を用いて最短経路集合を示す経路表情報を生成し、当該経路表情報を当該ルータ１０１／１０２／１０３に返送（送信）する。
【００６７】
ルータ１０１／１０２／１０３は、それぞれ、リンク状態データベース１および経路表２を保持しており、リンク状態データベース構築部３と、リンク状態データベース送信部４と、経路表情報受信部５とを含んで構成されている。これらの各構成要素は、第１の実施の形態におけるルータ１０１／１０２／１０３中の同名の各構成要素（図１参照）と同様のものである。
【００６８】
経路計算装置２０１／２０２／２０３は、それぞれ、リンク状態データベース受信部８と、最短経路計算部９と、経路表情報送信部１０とを含んで構成されている。これらの各構成要素は、第１の実施の形態における経路計算装置２００中の同名の各構成要素（図１参照）と同様のものである。
【００６９】
図７は、本実施の形態に係るＯＳＰＦによる経路制御システムの処理を示す流れ図である。この処理は、ルータ１０１＆経路計算装置２０１側処理Ｂ１０と、ルータ１０２＆経路計算装置２０２側処理Ｂ２０と、ルータ１０３＆経路計算装置２０３側処理Ｂ３０とからなる（ルータ１０１＆経路計算装置２０１側処理Ｂ１０，ルータ１０２＆経路計算装置２０２側処理Ｂ２０，およびルータ１０３＆経路計算装置２０３側処理Ｂ３０は並列的に存在する）。
【００７０】
ルータ１０１＆経路計算装置２０１側処理Ｂ１０，ルータ１０２＆経路計算装置２０２側処理Ｂ２０，およびルータ１０３＆経路計算装置２０３側処理Ｂ３０の各々は、リンク状態データベース構築ステップＢ１１／Ｂ２１／Ｂ３１と、リンク状態データベース複製送信ステップＢ１２／Ｂ２２／Ｂ３２と、最短経路計算ステップＢ１３／Ｂ２３／Ｂ３３と、経路表情報送信ステップＢ１４／Ｂ２４／Ｂ３４と、自ルータ始点最短経路集合抽出ステップＢ１５／Ｂ２５／Ｂ３５と、経路表登録ステップＢ１６／Ｂ２６／Ｂ３６とからなる。
【００７１】
次に、図５〜図７を参照して、上記のように構成された本実施の形態に係るＯＳＰＦによる経路制御システムの全体の動作について説明する。
【００７２】
先に述べた第１の実施の形態では、計算装置接続ルータであるルータ１０１は、図３中のステップＡ７〜ステップＡ９の処理および判定によって、経路表情報（最短経路集合）を隣接するルータ２およびルータ３に送信している。
【００７３】
これに対して、本実施の形態（第２の実施の形態）では、全てのルータ（ルータ１０１，ルータ１０２，およびルータ１０３）の各々が、直接的に、自己が接続している経路計算装置（経路計算装置２０１，経路計算装置２０２，および経路計算装置２０３の各々）から最短経路集合を示す経路表情報を受信する。したがって、ルータ（例えば、ルータ１０１）から隣接するルータ（例えば、ルータ１０２およびルータ１０３）に経路表情報を送信することに関する動作が不要となる。
【００７４】
一方、本実施の形態では、全てのルータ＆経路計算装置（ルータ１０１／１０２／１０３とそれに接続している経路計算装置２０１／２０２／２０３との組み合わせ）において、第１の実施の形態におけるステップＡ１〜ステップＡ４の処理（図３参照）が必要となる。
【００７５】
すなわち、本実施の形態では、ルータ１０１および経路計算装置２０１が、図７中のステップＢ１１〜ステップＢ１６や図５中のルータ１０１および経路計算装置２０１に関する矢線で示すように、第１の実施の形態におけるルータ１０１および経路計算装置２００による図３中のステップＡ１〜ステップＡ６の動作（処理）と同一の動作を行う。
【００７６】
さらに、本実施の形態では、ルータ１０２および経路計算装置２０２が、図７中のステップＢ２１〜ステップＢ２６や図５中のルータ１０２および経路計算装置２０２に関する矢線で示すように、ルータ１０１および経路計算装置２０１における図７中のステップＢ１１〜ステップＢ１６の動作と同一の動作を行う。同様に、ルータ１０３および経路計算装置２０３が、図７中のステップＢ３１〜ステップＢ３６や図５中のルータ１０３および経路計算装置２０３に関する矢線で示すように、ルータ１０１および経路計算装置２０１における図７中のステップＢ１１〜ステップＢ１６の動作と同一の動作を行う。ここで、これらのステップＢ１１〜ステップＢ１６の処理（ルータ１０１＆経路計算装置２０１側処理Ｂ１０），ステップＢ２１〜ステップＢ２６の処理（ルータ１０２＆経路計算装置２０２側処理Ｂ２０），およびステップＢ３１〜ステップＢ３６の処理（ルータ１０３＆経路計算装置２０３側処理Ｂ３０）は、並列的に実現される。
【００７７】
上記のように、本実施の形態に係るＯＳＰＦによる経路制御システムでは、各々のルータが、自身に接続されている経路計算装置に個々にリンク状態データベースの複製を送信し、当該経路計算装置で計算された最短経路集合（経路表情報）を受信する。したがって、ルータ同士での最短経路集合の送受信の必要がなくなる。これにより、ネットワークシステム上で流通するデータ量を減少させることができ、他の通信への影響を少なくできるという特有の効果が生じる。また、各々のルータの経路表に情報が登録されるまでの遅延が少なくなるという効果も、同時に得られる。
【００７８】
（３）　第３の実施の形態
【００７９】
上述の第１の実施の形態および第２の実施の形態に係るＯＳＰＦによる経路制御システムに基づいて、以下のような第３の実施の形態に係るＯＳＰＦによる経路制御システムを考えることができる。
【００８０】
すなわち、本発明の第３の実施の形態として、各ルータに図１に示した構成要素（リンク状態データベース１，経路表２，リンク状態データベース構築部３，リンク状態データベース送信部４，経路表情報受信部５，ルータ間経路表情報送信部６，およびルータ間経路表情報受信部７）を設け、さらに、図５に示すように各ルータに固有の経路計算装置を接続しうるようにした上で、「１つのエリアに１つ（１台）だけ経路計算装置を設ける」という第１の実施の形態の態様にも、「各ルータに対してそれぞれ固有の経路計算装置を設ける（接続する）」という第２の実施の形態の態様にも対処しうるようにする実施の形態を考えることができる。
【００８１】
この場合には、例えば、本発明が適用されるネットワークシステムの要求・指示に応じて、上記の２態様のうちのどちらの態様で本発明のＯＳＰＦによる経路制御システムを実現するかが決定されることとなる。
【００８２】
（４）　第４の実施の形態
【００８３】
図８は、本発明の第４の実施の形態に係るＯＳＰＦによる経路制御システムの構成を示すブロック図である。
【００８４】
図８を参照すると、本発明の第４の実施の形態に係るＯＳＰＦによる経路制御システムは、図１に示した第１の実施の形態に係るＯＳＰＦによる経路制御システムに対して、ルータ用プログラム８１０および経路計算装置用プログラム８２０を備える点が異なっている。
【００８５】
ルータ用プログラム８１０は、各ルータ（ルータ１０１／１０２／１０３）に読み込まれ、当該各ルータの動作を、リンク状態データベース構築部３，リンク状態データベース送信部４，経路表情報受信部５，ルータ間経路表情報送信部６，およびルータ間経路表情報受信部７として制御する（リンク状態データベース構築部３によってリンク状態データベース１が構築されることとなり、経路表情報受信部５またはルータ間経路表情報受信部７によって経路表２が設定されることとなる）。ルータ用プログラム８１０の制御による各ルータの動作は、第１の実施の形態における各ルータ内のリンク状態データベース構築部３，リンク状態データベース送信部４，経路表情報受信部５，ルータ間経路表情報送信部６，およびルータ間経路表情報受信部７の動作と全く同様になるので、その詳しい説明を割愛する。
【００８６】
経路計算装置用プログラム８２０は、経路計算装置２００に読み込まれ、当該経路計算装置２００の動作を、リンク状態データベース受信部８，最短経路計算部９，および経路表情報送信部１０として制御する。経路計算装置用プログラム８２０の制御による各経路計算装置の動作は、第１の実施の形態における経路計算装置２００内のリンク状態データベース受信部８，最短経路計算部９，および経路表情報送信部１０の動作と全く同様になるので、その詳しい説明を割愛する。
【００８７】
（５）　第５の実施の形態
【００８８】
図９は、本発明の第５の実施の形態に係るＯＳＰＦによる経路制御システムの構成を示すブロック図である。
【００８９】
図９を参照すると、本発明の第５の実施の形態に係るＯＳＰＦによる経路制御システムは、図５に示した第２の実施の形態に係るＯＳＰＦによる経路制御システムに対して、ルータ用プログラム９１０および経路計算装置用プログラム９２０を備える点が異なっている。
【００９０】
ルータ用プログラム９１０は、各ルータ（ルータ１０１／１０２／１０３）に読み込まれ、当該各ルータの動作を、リンク状態データベース構築部３，リンク状態データベース送信部４，および経路表情報受信部５として制御する（リンク状態データベース構築部３によってリンク状態データベース１が構築されることとなり、経路表情報受信部５によって経路表２が設定されることとなる）。ルータ用プログラム９１０の制御による各ルータの動作は、第２の実施の形態における各ルータ内のリンク状態データベース構築部３，リンク状態データベース送信部４，および経路表情報受信部５の動作と全く同様になるので、その詳しい説明を割愛する。
【００９１】
経路計算装置用プログラム９２０は、各経路計算装置（経路計算装置２０１／２０２／２０３）に読み込まれ、当該各経路計算装置の動作を、リンク状態データベース受信部８，最短経路計算部９，および経路表情報送信部１０として制御する。経路計算装置用プログラム９２０の制御による各経路計算装置の動作は、第２の実施の形態における各経路計算装置内のリンク状態データベース受信部８，最短経路計算部９，および経路表情報送信部１０の動作と全く同様になるので、その詳しい説明を割愛する。
【００９２】
【発明の効果】
以上説明したように、本発明によると、以下に示すような効果が生じる。
【００９３】
第１の効果は、ＯＳＰＦを動作させているルータの負荷を減少させることができるということにある。この結果、ルータが本来の経路制御処理に専念できるようになり、ルータの処理速度が向上する。
【００９４】
このような効果が生じる理由は、従来技術においてルータが最も処理能力を消費していた「リンク状態データベースに基づいて最短経路を計算する処理」を別の装置（経路計算装置）に行わせ、ルータはその装置によって計算された最短経路集合から自身に関する情報（自身が始点となる最短経路集合）を単純に抜き出して、その抽出した情報を自分の経路表に登録するだけでよくなるからである。
【００９５】
第２の効果は、ネットワークシステムにおける経路制御障害時の調査が容易になるということにある。
【００９６】
このような効果が生じる理由は、あるエリアに属する各ルータが持つべき経路表の全ての複製を、１台の経路計算装置が持つことにより、経路制御障害時に経路表の調査が必要になった場合に、従来技術におけるような「複数のルータに散在する経路表を調査すること」が不要になり、経路計算装置が持つ経路表情報を調査するだけでよくなるからである。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態に係るＯＳＰＦによる経路制御システムの構成を示すブロック図である。
【図２】図１に示すＯＳＰＦによる経路制御システムが適用されるネットワークシステムの構成を示す図である。
【図３】図１に示すＯＳＰＦによる経路制御システムの処理を示す流れ図である。
【図４】図１に示すＯＳＰＦによる経路制御システムの具体的な動作を説明するためのブロック図である。
【図５】本発明の第２の実施の形態に係るＯＳＰＦによる経路制御システムの構成を示すブロック図である。
【図６】図５に示すＯＳＰＦによる経路制御システムが適用されるネットワークシステムの構成を示す図である。
【図７】図５に示すＯＳＰＦによる経路制御システムの処理を示す流れ図である。
【図８】本発明の第４の実施の形態に係るＯＳＰＦによる経路制御システムの構成を示すブロック図である。
【図９】本発明の第５の実施の形態に係るＯＳＰＦによる経路制御システムの構成を示すブロック図である。
【符号の説明】
１　リンク状態データベース
２　経路表
３　リンク状態データベース構築部
４　リンク状態データベース送信部
５　経路表情報受信部
６　ルータ間経路表情報送信部
７　ルータ間経路表情報受信部
８　リンク状態データベース受信部
９　最短経路計算部
１０　経路表情報送信部
１００　エリア
１０１，１０２，１０３　ルータ
１０４，１０５，１０６　ネットワーク
２００，２０１，２０２，２０３　経路計算装置
８１０，９１０　ルータ用プログラム
８２０，９２０　経路計算装置用プログラム
【図１】
2004032569.tif 000003
【図２】
2004032569.tif 000004
【図３】
2004032569.tif 000005
【図４】
2004032569.tif 000006
【図５】
2004032569.tif 000007
【図６】
2004032569.tif 000008
【図７】
2004032569.tif 000009
【図８】
2004032569.tif 000010
【図９】
2004032569.tif 000011