情報処理装置、情報処理方法、およびプログラム
【課題】ネットワーク資源を効率的に利用することができるようにする。
【解決手段】コントローラ１１１およびノード１１２は、最大ランク数と各リンクのリンク利用率に基づいて、ランク表を構築する。ノード１１２は、自ノードのリンク利用率が変化した場合、変化したリンク利用率が他ノードに広告する必要があるリンク情報であるか否かを判定し、広告する必要のあるリンク情報のみを広告する。また、他ノードからリンク情報を受信した場合、コントローラ１１１およびノード１１２は、ランク表を更新する。本発明は、OSPFネットワークに適用することができる。
【解決手段】コントローラ１１１およびノード１１２は、最大ランク数と各リンクのリンク利用率に基づいて、ランク表を構築する。ノード１１２は、自ノードのリンク利用率が変化した場合、変化したリンク利用率が他ノードに広告する必要があるリンク情報であるか否かを判定し、広告する必要のあるリンク情報のみを広告する。また、他ノードからリンク情報を受信した場合、コントローラ１１１およびノード１１２は、ランク表を更新する。本発明は、OSPFネットワークに適用することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、およびプログラムに関し、特に、ネットワーク資源を効率的に利用することができる情報処理装置、情報処理方法、およびプログラムに関する。
【背景技術】
【０００２】
Open Shortest Path First(OSPF)ネットワークにおいては、トラヒック需要の変化に対してリンク利用効率を向上させるために、ネットワーク内のリンク利用率の最大値である、最大リンク利用率に基づきネットワークが管理される。なお、最大リンク利用率は、ネットワーク輻輳率ともいう。
【０００３】
非特許文献１乃至４に開示されているOSPFネットワークは、ネットワーク制御装置および複数のノードから構成される。OSPFネットワークにおいて、適切なルーチングはネットワークスループットおよびリソース利用効率を向上させる。ルーチング性能を向上させるアプローチとして、最大リンク利用率を最小化する手法がある（非特許文献４）。ネットワーク制御装置は、最大リンク利用率を有するリンクを特定し、そのリンクに流れるトラヒック量を低減させることにより、ネットワークスループットおよびリソース利用効率を向上させることができる。
【０００４】
OSPFネットワークにおいて、各ノードおよびネットワーク制御装置は、リンクの両端のノードを表すリンク識別情報であるリンクID(Identification)と、そのノードにおけるリンク利用率を含むリンク情報を保持している。なお、リンク情報は、OSPF Traffic Engineering（OSPF-TE）のメカニズムにより実現される（非特許文献４）。
【０００５】
非特許文献３に開示されている技術によれば、各ノードおよびネットワーク制御装置が、ネットワーク内のすべてのリンク情報を保持している。そして、ネットワーク内のいずれかのリンクのリンク利用率が変化するたびに、変化したリンク情報が各ノードおよびネットワーク制御装置に広告される。
【０００６】
各ノードおよびネットワーク制御装置は、リンク利用率が変化したことを伝えるリンク情報を受信すると、最大リンク利用率を更新する。ネットワーク制御装置は最大リンク利用率を活用して、ルーチング制御を行う。
【０００７】
従来の技術について、図１乃至図３を用いて説明する。図１は、OSPFネットワーク１の構成例を示す図である。
【０００８】
図１のネットワーク１は、コントローラ１１およびノード１２−１乃至１２−４から構成されている。
【０００９】
コントローラ１１は、ネットワーク１全体を制御するネットワーク制御装置である。コントローラ１１は、ネットワーク１全体のリンク情報を保持している。コントローラ１１は、最大リンク利用率を有するリンクを特定し、そのリンクに流れるトラヒック量を低減させる管理を行う。
【００１０】
ノード１２−１乃至１２−４は、ネットワーク１に接続されている、例えばルータ、クロスコネクト装置、レイヤ２スイッチ等により構成される。以下、ノード１２−１乃至１２−４を特に区別する必要のない場合、まとめてノード１２と称する。なお、コントローラ１１も、ノード１２の一種である。
【００１１】
図２は、従来の技術におけるネットワーク１のリンク利用率を示す図である。
【００１２】
図２の各ノード１２間の矢印はリンクの方向を示しており、矢印に付されている数字は、そのリンクのリンク利用率を示している。
【００１３】
一例として、ノード１２−１からノード１２−２に向かうリンクのリンク利用率は、０．８２である。なお、以下、リンクの両端のノード表すリンクIDは、リンク元のノード（以下、発ノードと称する）ｉからリンク先のノード（以下、着ノードと称する）ｊの順に（i,j）として表現される。
【００１４】
即ち、ノード１２−１からノード１２−２に向かうリンクのリンクIDは、（１２−１,１２−２）と表現される。
【００１５】
図２の例においては、リンク１２−１が発ノードであるリンクID（１２−１,１２−２）のリンク利用率は０．８２、リンクID（１２−１，１２−３）のリンク利用率は０．７１である。
【００１６】
リンク１２−２が発ノードであるリンクID（１２−２,１２−１）のリンク利用率は０．９８、リンクID（１２−２,１２−３）のリンク利用率は０．６４、リンクID（１２−２，１２−４）のリンク利用率は０．７７である。
【００１７】
リンク１２−３が発ノードであるリンクID（１２−３,１２−１）のリンク利用率は０．３９、リンクID（１２−３，１２−２）のリンク利用率は０．８６、リンクID（１２−３，１２−４）のリンク利用率は０．６９である。
【００１８】
リンク１２−４が発ノードであるリンクID（１２−４,１２−２）のリンク利用率は０．２２、リンクID（１２−４，１２−３）のリンク利用率は０．１０である。
【００１９】
すべてのノード１２は、自身のノード（以下、自ノードともいう）を発ノードとするリンクのリンクIDと、リンク利用率を含むリンク情報を、コントローラ１１を含むすべての自ノード以外のノード１２（以下、他ノードともいう）に広告する。
【００２０】
具体的には、ノード１２−１は、自ノードが発ノードとなるリンクID（１２−１,１２−２）およびリンクID（１２−１,１２−３）のリンク情報を、接続されているノードであるコントローラ１１、ノード１２−２および１２−３に広告する。
【００２１】
ノード１２−２は、ノード１２−１からリンクID（１２−１,１２−２）およびリンクID（１２−１,１２−３）のリンク情報を受信すると、さらにそのリンク情報を、接続されているノードであるノード１２−３およびノード１２−４に広告する。
【００２２】
また、ノード１２−２は、自ノードが発ノードとなるリンクID（１２−２,１２−１）、リンクID（１２−２,１２−３）およびリンクID（１２−２,１２−４）のリンク情報を、接続されているノードであるノード１２−１、ノード１２−３および１２−４に広告する。
【００２３】
このようにして、リンク情報がノード１２間を順次伝播し、最終的にはすべてのノード（コントローラ１１を含む）に、各ノード１２のリンク情報が広告される。このように、自ノードが広告したリンク情報を、他ノード間を順次伝播させてすべての他ノードに広告することを、以下、単に他ノードに広告する、とも表現する。
【００２４】
図３は、従来の技術におけるリンク利用率のランク表を示す図である。ランク表とは、広告されたリンク情報に基づいて、コントローラ１１およびノード１２が構築する表である。コントローラ１１およびノード１２は、受信したすべてのリンク情報に含まれるリンクIDとリンク利用率を用いて、リンク利用率の高い順に順位づけを行い、ランク表を構築する。
【００２５】
図３の例においては、最もリンク利用率の高いリンクID（１２−２,１２−１）のリンク利用率０．９８がランク１位となり、次にリンク利用率の高いリンクID（１２−３,１２−２）のリンク利用率０．８６がランク２位となる。さらに、次にリンク利用率の高いリンクID（１２−１,１２−２）のリンク利用率０．８２がランク３位となる。このようにして、ネットワーク１に接続されている全部で１０のリンクについて、１０位までのランク表が構築される。
【００２６】
図４は、従来の技術におけるネットワーク１のリンク利用率を示す図である。図４は、図２に示されるネットワーク１において、リンクID（１２−３，１２−４）のリンク利用率が、０．６９から０．３０に変化した状態を表している。
【００２７】
この場合、発ノードであるノード１２−３が、接続されているノードであるノード１２−１、ノード１２−２およびノード１２−４に、リンクID（１２−３，１２−４）のリンク情報を広告する。ノード１２−１は、リンク情報をノード１２−３から受信すると、受信したリンク情報を、接続されているノードであるコントローラ１１およびノード１２−２に広告する。
【００２８】
このようにして、順次リンク情報が各ノード１２に接続されているノード１２に広告され、最終的に、リンク情報は、コントローラ１１および全てのノード１２に広告される。そして、コントローラ１１およびノード１２は、受信したリンク情報に基づいて、ランク表を更新する。
【００２９】
図５は、従来の技術におけるリンク利用率のランク表を示す図である。図５は、図４を参照して説明したリンク利用率の変化に伴い、コントローラ１１およびノード１２が再構築したランク表を表している。
【００３０】
リンクID（１２−３，１２−４）のリンク利用率は、図３に示すランク表において、６位であったが、リンク利用率が変化したことにより、図５に示すランク表においては、８位に降下している。
【先行技術文献】
【非特許文献】
【００３１】
【非特許文献１】J.Moy, “OSPF Version 2,”RFC 2328,Apr.1998.
【非特許文献２】D.Katz,K.Kompella,and K.Kompella“Traffic Engineering(TE)Extensions to OSPF Version2,”RFC 3630,Sep.2003
【非特許文献３】Y.Koizumi,T.Miyamura,S.Arakawa,E.Oki,K.Shiomoto,and M.Murata, “Adaptive Virtual Network Topology Control Based on Attractor Selection,”IEEE/OSA J.Light.Tech.,vol.28,no.11,pp1720-1731,Jun.2010.
【非特許文献４】E.Oki and A.Iwaki, “Load-Balanced IP Routing Scheme Based on Shortest Paths in Hose Model,”IEEE Trans.Commum.,vol.58,no.7,pp.2088-2096,Jul.2010.
【発明の概要】
【発明が解決しようとする課題】
【００３２】
しかしながら、コントローラ１１は、上述したように、ネットワーク１を管理するのに最大リンク利用率のみを必要とする。それにも関わらず、最大でないリンク利用率についても頻繁に広告されており、広告されるリンク情報が膨大な量になることで、ネットワーク資源が浪費されている。
【００３３】
本発明はこのような状況に鑑みてなされたものであり、ネットワーク資源を効率的に利用することができるようにするものである。
【課題を解決するための手段】
【００３４】
本発明の一側面の情報処理装置は、ネットワークのリンクを、その利用率が高い順に順位付けて登録リンクとして登録したランク表であって、前記ネットワークの全リンク数より少ない数の、前記リンクを登録する最大の数である最大リンク数が予め定められている前記ランク表を構築し、前記利用率が変化した前記リンクである変化リンクが発生した場合、前記ランク表を再構築する構築部を備え、前記構築部は、前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、前記登録リンク数が前記最大リンク数の範囲内になるように前記ランク表を書き換え、前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より低い値に変化した場合、前記変化リンクを前記登録リンクから削除して、前記ランク表を書き換える。
【００３５】
前記変化リンクを前記登録リンクから削除した結果、前記登録リンクの数がゼロになった場合、前記ネットワークのすべての前記リンクの利用率に基づいて前記ランク表を初期化することができる。
【００３６】
前記変化リンクが前記登録リンクである場合、並びに前記登録リンクでない前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、他の情報処理装置に前記変化リンクの前記リンク利用率およびリンク識別情報を広告することができる。
【００３７】
前記最大リンク数は、１以上且つ前記ネットワークに存在するリンク数以下の範囲内で、変化リンクが発生する回数に対する広告される回数の割合を最小にする数にすることができる。
【００３８】
本発明の一側面である情報処理装置の情報処理方法とプログラムのそれぞれは、上述した本発明の情報処理装置に対応する方法とプログラムのそれぞれである。
【００３９】
本発明の一側面においては、ネットワークのリンクを、その利用率が高い順に順位付けて登録リンクとして登録したランク表であって、前記ネットワークの全リンク数より少ない数の、前記リンクを登録する最大の数である最大リンク数が予め定められている前記ランク表が構築され、前記利用率が変化した前記リンクである変化リンクが発生した場合、前記ランク表が再構築される。前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、前記登録リンク数が前記最大リンク数の範囲内になるように前記ランク表が書き換えられ、前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より低い値に変化した場合、前記変化リンクが前記登録リンクから削除されて、前記ランク表が書き換えられる。
【発明の効果】
【００４０】
本発明によれば、ネットワーク資源を効率的に利用できるようになる。
【図面の簡単な説明】
【００４１】
【図１】OSPFネットワークの構成例を示す図である。
【図２】従来の技術におけるネットワークのリンク利用率を示す図である。
【図３】従来の技術におけるリンク利用率のランク表を示す図である。
【図４】従来の技術におけるネットワークのリンク利用率を示す図である。
【図５】従来の技術におけるリンク利用率のランク表を示す図である。
【図６】本発明の一実施形態に係るネットワークの構成例を示す図である。
【図７】本発明の一実施形態に係るノードの構成例を示すブロック図である。
【図８】ノードの機能的構成例を示すブロック図である。
【図９】ノードの初期化処理について説明するフローチャートである。
【図１０】ランク表の例を示す図である。
【図１１】リンク情報を広告する条件について説明する図である。
【図１２】広告判定処理について説明するフローチャートである。
【図１３】ネットワークのリンク利用率を示す図である。
【図１４】ランク表再構築処理１について説明するフローチャートである。
【図１５】ネットワークのリンク利用率を示す図である。
【図１６】ランク表の例を示す図である。
【図１７】ランク表再構築処理２について説明するフローチャートである。
【図１８】ネットワークのリンク利用率を示す図である。
【図１９】ランク表の例を示す図である。
【図２０】ネットワークのリンク利用率を示す図である。
【図２１】ランク表の例を示す図である。
【図２２】ネットワークのリンク利用率を示す図である。
【図２３】ランク表の例を示す図である。
【図２４】ランク表の例を示す図である。
【図２５】ランク表再構築処理３について説明するフローチャートである。
【図２６】ネットワークのリンク利用率を示す図である。
【図２７】ランク表の例を示す図である。
【図２８】ランク数の推移を示す図である。
【図２９】IPネットワークバックボーンの一例を示す図である。
【図３０】最大ランク数と広告率の関係を示す図である。
【図３１】最大ランク数とランク表リセット率の関係を示す図である。
【発明を実施するための形態】
【００４２】
以下、本発明を実施するための形態について説明する。
【００４３】
[ネットワークの構成例]
図６は、本発明の一実施形態に係るネットワーク１０１の構成例を示す図である。
【００４４】
図６のネットワーク１０１は、コントローラ１１１およびノード１１２−１乃至１１２−４から構成されている。
【００４５】
コントローラ１１１は、ネットワーク１０１全体を制御するネットワーク制御装置である。コントローラ１１１は、ネットワーク１０１全体のリンク情報を保持している。コントローラ１１１は、最大リンク利用率を有するリンクを特定し、そのリンクに流れるトラヒック量を低減させる管理を行う。
【００４６】
ノード１１２−１乃至１１２−４は、ネットワーク１０１に接続されている、例えばルータ、クロスコネクト装置、レイヤ２スイッチ等により構成される。以下、ノード１１２−１乃至１１２−４を特に区別する必要のない場合、まとめてノード１１２と称する。なお、コントローラ１１１も、ノード１１２の一種である。
【００４７】
図６の各ノード１１２間の矢印はリンクの方向を示しており、矢印に付されている数字は、そのリンクのリンク利用率を示している。
【００４８】
図６のネットワーク１０１において、リンク１１２−１が発ノードであるリンクID（１１２−１,１１２−２）のリンク利用率は０．８２、リンクID（１１２−１，１１２−３）のリンク利用率は０．７１である。
【００４９】
リンク１１２−２が発ノードであるリンクID（１１２−２,１１２−１）のリンク利用率は０．９８、リンクID（１１２−２,１１２−３）のリンク利用率は０．６４、リンクID（１１２−２，１１２−４）のリンク利用率は０．７７である。
【００５０】
リンク１１２−３が発ノードであるリンクID（１１２−３,１１２−１）のリンク利用率は０．３９、リンクID（１１２−３，１１２−２）のリンク利用率は０．８６、リンクID（１１２−３，１１２−４）のリンク利用率は０．６９である。
【００５１】
リンク１１２−４が発ノードであるリンクID（１１２−４,１１２−２）のリンク利用率は０．２２、リンクID（１１２−４，１１２−３）のリンク利用率は０．１０である。なお、図６に示される各リンクのリンク情報を、以下、初期状態と称する。
【００５２】
[情報処理装置の構成例]
図７は、本発明の一実施形態に係るノード１１２の構成例を示すブロック図である。
【００５３】
図７において、CPU（Central Processing Unit）１３１は、ROM１３２に記憶されているプログラム、または記憶部１３８からRAM１３３にロードされたプログラムに従って各種の処理を実行する。RAM１３３にはまた、CPU１３１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【００５４】
CPU１３１、ROM１３２、およびRAM１３３は、バス１３４を介して相互に接続されている。このバス１３４にはまた、入出力インタフェース１３５も接続されている。
【００５５】
入出力インタフェース１３５には、ボタンやスイッチなどよりなる操作部１３６、LED（Light Emitting Diode）などよりなるインジケータ１３７、ハードディスクなどより構成される記憶部１３８、ユーザが所有するパーソナルコンピュータやCE（Consumer Electronics）機器との通信を制御するLAN（Local Area Network）通信部１３９、並びに図示せぬモデムを介したバスなどとの通信を制御するWAN（Wide Area Network）通信部１４０が接続されている。
【００５６】
入出力インタフェース１３５にはまた、必要に応じてドライブ１４１が接続され、磁気ディスク１５１、光ディスク１５２、光磁気ディスク１５３、或いは半導体メモリ１５４などが適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部１３８にインストールされる。
【００５７】
図８は、ノード１１２の機能的構成例を示すブロック図である。図８に示す機能部のうちの少なくとも一部は、図７のCPU１３１により所定のプログラムが実行されることによって実現される。
【００５８】
図８において、CPU１３１は、検出部１６１、受信部１６２、判定部１６３、構築部１６４および出力部１６５を含むように構成されている。
【００５９】
検出部１６１は、自ノードが発ノードとなるリンクに関するリンク情報を検出する。また、検出部１６１は、検出したリンク情報を、判定部１６３に出力する。
【００６０】
受信部１６２は他ノードから広告されたリンク情報を受信する。受信部１６２は、受信したリンク情報を、判定部１６３および出力部１６５に出力する。
【００６１】
判定部１６３は、検出部１６１から供給されたリンク情報が他ノード（コントローラ１１１およびノード１１２）に広告すべきリンク情報であるか否かを判定する。他ノードに広告すべきリンク情報であった場合、判定部１６３は、リンク情報を出力部１６５に出力する。また、判定部１６３は、受信部１６２から供給されたリンク情報が、ランク表を再構築する複数のケースのうち、何れのケースに該当するかを判定する。
【００６２】
構築部１６４は、判定部１６３から受信したリンク情報およびランク表が保持する最大のランク数である、最大ランク数に基づき、リンク利用率の高い順にランク表を構築する。即ち、リンク情報をランク表に登録リンクとして登録する。構築部１６４は、構築したランク表を保持する。
【００６３】
出力部１６５は、判定部１６３から出力されたリンク情報を、他ノードに出力する。換言すると、出力部１６５は、判定部１６３により他ノードに広告すべきと判定されたリンク情報を、他ノードに広告する。
【００６４】
また、出力部１６５は、受信部１６２から出力された、他ノードから広告されたリンク情報を、広告を発したノード以外の他ノードに出力する。
【００６５】
［情報処理装置の動作］
図９は、ノード１１２の初期化処理について説明するフローチャートである。初期化処理とは、ノード１１２がランク表を最初に構築する場合に実行する処理である。初期化処理は、例えば、ネットワーク管理者等により命令がなされた場合に開始される。
【００６６】
ステップＳ１において、検出部１６１は、自ノードのリンク情報を検出する。即ち、自ノードを発ノードとするリンクのリンク情報を検出する。具体的には、リンク利用率が検出される。
【００６７】
ステップＳ２において、出力部１６５は、自ノードのリンク情報を広告する。即ち、検出部１６１が検出した自ノードを発ノードとするリンクのリンク情報を、他ノードに広告する。
【００６８】
ステップＳ３において、受信部１６２は、全ノードのリンク情報を受信する。即ち、初期化処理はすべてのノード１１２において実行されるので、すべての他ノードからリンク情報が送信されてきた場合、これが受信される。
【００６９】
ステップＳ４において、構築部１６４は、リンク利用率の大きい順にランク表を構築する。即ち、受信部１６２が受信した全てのノード１１２のリンク情報に基づき、リンク利用率の大きい順にランク表を構築する。
【００７０】
ステップＳ５において、構築部１６４は、最大ランク数のリンク情報を保持し、それ以下のリンク情報を破棄する。以上で、初期化処理は終了する。最大ランク数は、初期化処理を実行するにあたり、予め設定されている値である。なお、ネットワーク１０１に最適な最大ランク数についての詳細は、図２９乃至図３１を参照して後述する。
【００７１】
次に、図９を参照して説明した初期化処理時に構築されたランク表の一例を、図１０を参照して説明する。
【００７２】
図１０は、ランク表の例を示す図である。図１０に示されるランク表は、図６のネットワーク１０１におけるリンク情報に基づいて構築されている。
【００７３】
図６に示された初期状態について、図９を参照して説明した初期化処理のステップＳ４の処理により、構築部１６４は、リンク利用率の高い順に順位付けを行う。
【００７４】
即ち、リンクID（１１２−２，１１２−１）のリンク利用率０．９８がランク１位であり、換言すると、リンクID（１１２−２，１１２−１）のリンク利用率０．９８がネットワーク１０１における最大リンク利用率である。また、リンクID（１１２−３，１１２−２）のリンク利用率０．８６がランク２位、リンクID（１１２−１，１１２−２）のリンク利用率０．８２がランク３位となる。
【００７５】
なお、図１０の例では、最大ランク数が３と定義されているとする。よって、ランク表には、ランク３位までのリンク情報しか保持されない。図９を参照して説明した初期化処理のステップＳ５の処理により、ランク４位以下のリンク情報は、破棄される。このようにして、初期化処理時に図１０に示されるランク表が構築され、保持される。
【００７６】
次に、初期化処理終了後に、ネットワーク１０１において何れかのリンクのリンク利用率が変化した場合、即ち、リンク利用率が変化した変化リンクが発生した場合について、図１１乃至図３５を参照して説明する。
【００７７】
図１１は、リンク情報を広告する条件について説明する図である。即ち、図１１は、ノード１１２が、自ノードを発ノードとするリンクにおいてリンク利用率が変化した場合に、他ノードにリンク情報を広告するか否かを判断する基準を示している。
【００７８】
変化したリンク利用率がランク表の最下位のリンク利用率より高く、且つ変化したリンク利用率のリンクIDとランク表にあるリンクIDが一致した場合（以下、ケース１と称する）、ノード１１２は、変化したリンクのリンク利用率とリンクIDを含むリンク情報を、他ノードに広告する。ケース１の具体的な例については、図１５および１６を参照して後述する。
【００７９】
変化したリンク利用率がランク表の最下位のリンク利用率と同じか低く、且つ変化したリンク利用率のリンクIDとランク表にあるリンクIDが一致した場合（以下、ケース２と称する）、ノード１１２は、変化したリンク利用率とリンクIDを含むリンク情報を、他ノードに広告する。ケース２の具体的な例については、図１８乃至図２４を参照して後述する。
【００８０】
変化したリンク利用率がランク表の最下位のリンク利用率より高く、且つ、変化したリンク利用率のリンクIDとランク表にあるリンクIDが一致しない場合（以下、ケース３と称する）、ノード１１２は、変化したリンク利用率を含むリンク情報を、他ノードに広告する。ケース３の具体的な例については、図２６および２７を参照して後述する。
【００８１】
変化したリンク利用率がランク表の最下位のリンク利用率と同じか低く、且つ変化したリンク利用率のリンクIDとランク表にあるリンクIDが一致しない場合（以下、ケース４と称する）、ノード１１２は、変化したリンク利用率を含むリンク情報を、他ノードに広告しない。この場合の具体的な例については、図１３を参照して後述する。
【００８２】
換言すると、上述したケース１乃至ケース３においては、変化リンクの発生によりランク表を再構築する必要があるため、ノード１１２はリンク情報を広告する。
【００８３】
一方、ケース４の場合、変化リンクの発生によりランク表を再構築する必要がないため、ノード１１２はリンク情報を広告しない。
【００８４】
なお、ケース１乃至ケース３の区分は、広告されたリンク情報を受信してランク表を再構築する処理においても利用される。ケース１乃至ケース３の区分を利用してランク表を再構築する処理については、図１４乃至図２７を参照して後述する。
【００８５】
以上、図１１を参照して、ノード１１２が、自ノードを発ノードとするリンクにおいてリンク利用率が変化した場合に、他ノードにリンク情報を広告するか否かを判断する基準について説明した。
【００８６】
図１２は、広告判定処理について説明するフローチャートである。広告判定処理とは、ネットワーク１０１においてリンク利用率が変化した場合に、ノード１１２が他ノードにリンク情報を広告するか否かを判定し、さらに他ノードからリンク情報を受信した場合にランク表を再構築する処理である。広告判定処理は、初期化処理終了後に実施される。
【００８７】
ステップＳ１１において、検出部１６１は、リンク利用率が変化したかを判定する。即ち、検出部１６１が、自ノードのリンク利用率の変化を検出した場合、ステップＳ１１においてＹＥＳであると判定され、処理はステップＳ１２に進む。
【００８８】
ステップＳ１２において、判定部１６３は、変化したリンク利用率のリンクIDと、ランク表のリンクIDが一致するかを判定する。即ち、判定部１６３は、構築部１６４が保持しているランク表に基づき、リンク利用率が変化したリンクIDが、ランク表に登録されているかを判定する。
【００８９】
リンク利用率が変化したリンクIDが、ランク表に登録されている場合、ステップＳ１２においてＹＥＳであると判定され、処理はステップＳ１３に進む。即ち、変化したリンク利用率のリンクIDが、ランク表に登録されている場合は、図１１を参照して上述したように、ケース１またはケース２に該当する。よって、判定部１６３は、他ノードに広告するケースであると判断する。
【００９０】
ステップＳ１３において、出力部１６５は、他ノードにリンク情報を広告する。その後、処理はステップＳ１５に進む。ステップＳ１５以降の処理については後述する。
【００９１】
一方、ステップＳ１２の処理においてＮＯであると判定された場合、即ち、リンク利用率が変化したリンクIDが、ランク表に登録されていない場合、処理はステップＳ１４に進む。ステップＳ１４において、判定部１６３は、変化したリンク利用率は、ランク表の最下位のリンク利用率よりも高いかを判定する。
【００９２】
変化したリンク利用率が、ランク表の最下位のリンク利用率よりも高い場合、ステップＳ１４においてＹＥＳであると判定され、処理はステップＳ１３に進む。即ち、この場合、変化したリンク利用率のリンクIDと、ランク表のリンクIDが一致せず（ステップＳ１２の処理）、且つ、変化したリンク利用率が、ランク表の最下位のリンク利用率よりも高い。よって、図１１を参照して上述したように、この場合はケース３に該当する。従って、判定部１６３は、他ノードに広告する。
【００９３】
それに対し、変化したリンク利用率が、ランク表の最下位のリンク利用率と同じか低い場合、ステップＳ１４においてＮＯであると判定され、処理はステップＳ１５に進む。即ち、この場合、変化したリンク利用率のリンクIDと、ランク表のリンクIDが一致せず（ステップＳ１２の処理）、且つ、変化したリンク利用率が、ランク表の最下位のリンク利用率と同じか低い。よって、図１１を参照して上述したように、判定部１６３は、この場合は広告しないケース（ケース４）に該当すると判断する。この場合、リンク情報は広告されず、受信部１６２は、広告されたリンク情報を受信しない。よって、ステップＳ１５においてＮＯであると判定され、処理はステップＳ１１に戻る。
【００９４】
ここで、図１３を参照して、ステップＳ１２およびステップＳ１４の一連の処理で広告しないケース（ケース４）であると判定される場合について具体的に説明する。
【００９５】
図１３は、ネットワーク１０１のリンク利用率を示す図である。図１３は、図６を参照して説明した初期状態から、リンクID（１１２−４，１１２−２）のリンク利用率が、０．２２から０．５０に変化した状態を表している。
【００９６】
上述したように、初期状態において、初期化処理時に構築されたランク表は、図１０に示されたランク表である。
【００９７】
即ち、リンクID（１１２−２，１１２−１）のリンク利用率０．９８がランク１位であり、リンクID（１１２−３，１１２−２）のリンク利用率０．８６がランク２位、リンクID（１１２−１，１１２−２）のリンク利用率０．８２がランク３位である。
【００９８】
ここで、リンクID（１１２−４，１１２−２）のリンク利用率が、０．２２から０．５０に変化した場合について説明する。
【００９９】
リンクID（１１２−４，１１２−２）は、ランク表に登録されていない。また、リンクID（１１２−４，１１２−２）のリンク利用率０．５０は、ランク３位のリンク利用率０．８２より低い。従って、変化したリンク利用率は、ランク表に何ら変化をもたらさない。よって、判定部１６３は、広告しないケース（ケース４）であると判定する。
【０１００】
図１２のフローチャートの説明に戻る。以上、ステップＳ１１の処理においてＹＥＳであると判定された場合の処理について説明した。ステップＳ１１においてＮＯと判定された場合、即ち、リンク利用率が変化していない場合には、リンク表を再構築する必要がないので、ステップＳ１２乃至１４の処理は実行されず、処理はステップＳ１５に進む。この場合、リンク情報は広告されず、受信部１６２は、広告されたリンク情報を受信しない。よって、ステップＳ１５においてＮＯであると判定され、処理はステップＳ１１に戻る。
【０１０１】
ステップＳ１５において、受信部１６２は、リンク情報を受信したかを判定する。即ち、受信部１６２が、他ノードからリンク情報を受信した場合、ステップＳ１５においてＹＥＳであると判定され、処理はステップＳ１６に進む。つまり、ステップＳ１３で広告されたリンク情報を受信した他ノードも、ステップＳ１６以降の処理を実行することになる。
【０１０２】
ステップＳ１６において、判定部１６３は、リンク情報のリンクIDが一致したかを判定する。つまり、判定部１６３は、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致するか否かを判定する。即ち、判定部１６３は、構築部１６４が保持しているランク表に基づき、受信したリンク情報のリンクIDが、ランク表に登録されているかを判定する。
【０１０３】
受信したリンク情報のリンクIDが、ランク表に登録されている場合、ステップＳ１６においてＹＥＳであると判定され、処理はステップＳ１７に進む。即ち、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致した場合は、図１１を参照して上述したように、ケース１またはケース２に該当すると判断される。
【０１０４】
ステップＳ１７において、判定部１６３は、受信したリンク情報のリンク利用率は、最下位のリンク利用率より高いかを判定する。
【０１０５】
受信したリンク情報のリンク利用率が、最下位のリンク利用率より高い場合、ステップＳ１７においてＹＥＳであると判定され、処理はステップＳ１８に進む。
【０１０６】
即ち、この場合、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致し（ステップＳ１６の処理）、且つ、変化したリンク利用率が、ランク表の最下位のリンク利用率よりも高い。よって、この場合はケース１に該当する。
【０１０７】
ステップＳ１８において、構築部１６４は、ランク表再構築処理１を実行する。ランク表再構築処理１の詳細については、図１４を参照して後述するが、これによりランク表が再構築される。ランク表再構築処理１は、ランク表に登録されているリンク情報に対して、ランク表の順位を入れ替える処理である。
【０１０８】
それに対し、受信したリンク情報のリンク利用率が、最下位のリンク利用率より同じか低い場合、ステップＳ１７においてＮＯであると判定され、処理はステップＳ１９に進む。
【０１０９】
即ち、この場合、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致し（ステップＳ１６の処理）、且つ、変化したリンク利用率が、ランク表の最下位のリンク利用率と同じか低い。よって、この場合はケース２に該当する。
【０１１０】
ステップＳ１９において、構築部１６４は、ランク表再構築処理２を実行する。ランク表再構築処理２の詳細については、図１７を参照して後述するが、これによりランク表が再構築される。ランク表再構築処理２は、ランク表に登録されていたリンクIDのリンク利用率が変化することにより、登録されていたリンク情報がランク外になって削除される処理である。また、ランク表再構築処理２は、順次リンク情報が削除されてランク数がゼロになった場合に、初期化処理を実行する処理である。
【０１１１】
ステップＳ１６の処理においてＮＯであると判定された場合、即ち、受信したリンク情報のリンクIDが、ランク表に登録されていない場合、処理はステップＳ２０に進む。
【０１１２】
即ち、受信したリンク情報のリンクIDが、ランク表に登録されていないので、ケース３に該当すると判断される。
【０１１３】
ステップＳ２０において、主に構築部１６４は、ランク表再構築処理３を実行する。ランク表再構築処理３の詳細については、図２５を参照して後述するが、これによりランク表が再構築される。ランク表再構築処理３は、ランク表に新たなリンク情報が登録され、ランク外となったリンク情報が削除される処理である。
【０１１４】
このようにして、ステップＳ１８，Ｓ１９，およびＳ２０において、ランク表再構築処理１、ランク表再構築処理２、およびランク表再構築処理３がそれぞれ実行されると、処理はステップＳ１１に戻る。
【０１１５】
以上、説明したように、ノード１１２は、リンク利用率が変化した場合、図１２のステップＳ１１乃至Ｓ１４の処理により広告処理を行い、他のノード１１２から広告されたリンク利用率を受信した場合には、ランク表を再構築する処理を実行する。
【０１１６】
図１４は、ランク表再構成処理１について説明するフローチャートである。ランク表再構築処理１は、図１２のフローチャートのステップＳ１８の処理である。また、ランク表再構築処理１は、図１１を参照して説明したケース１の場合に、構築部１６４がランク表を再構築する処理である。
【０１１７】
ステップＳ３１において、構築部１６４は、リンク情報を更新する。即ち、リンク利用率が新しい値に書き換えられる。その後、処理はステップＳ３２に進む。
【０１１８】
ステップＳ３２において、構築部１６４は、ランク表を再構築する。即ち、順位が書き換えられ、処理は図１２のフローチャートのステップＳ１１に戻る。
【０１１９】
構築部１６４がランク表再構築処理１を実行し、ランク表を再構築する場合の具体的な例について、図１５を参照して説明する。
【０１２０】
図１５は、ネットワーク１０１のリンク利用率を示す図である。図１５は、図６を参照して説明した初期状態から、リンクID（１１２−２，１１２−１）のリンク利用率が、０．９８から０．８４に変化した状態を表している。
【０１２１】
図１０に示された、初期化処理時に構築されたランク表によると、ランク１位のリンクID（１１２−２，１１２−１）と、変化したリンク利用率のリンクID（１１２−２，１１２−１）は、一致している。さらに、変化したリンク利用率０．８４は、ランク表の最下位のリンク利用率０．８２より高い。よって、この場合はケース１に該当すると判定され、ランク表再構築処理１が実行される。
【０１２２】
図１６は、ランク表の例を示す図である。図１６は、図１５を参照して説明したリンク利用率の変化に伴い、ランク表再構築処理１の処理によって、図１０に示されるランク表が再構築されたランク表を表している。
【０１２３】
図１０においてランク１位であったリンクID（１１２−２，１１２−１）のリンク利用率が０．９８から０．８４に変化したことにより、リンク情報が更新される。即ち、リンク利用率の値が０．９８から０．８４に変更される。そして、ランク２位であったリンクID（１１２−３，１１２−２）のリンク利用率０．８６がランク１位となり、リンクID（１１２−２，１１２−１）のリンク利用率０．８４がランク２位となる。ランク３位であったリンクID（１１２−１，１１２−２）のリンク利用率０．８２は、ランク３位のまま変わらない。
【０１２４】
以上説明したように、構築部１６４は、ケース１の条件でリンク利用率が変化した場合、ランク表に登録されているリンク情報の順位を入れ替える。
【０１２５】
図１７は、ランク表再構成処理２について説明するフローチャートである。ランク表再構築処理２は、図１２のフローチャートのステップＳ１９の処理である。また、ランク表再構成処理２は、図１１を参照して説明したケース２の場合に、主に構築部１６４がランク表を再構築する処理である。
【０１２６】
ステップＳ４１において、構築部１６４は、対象となるリンク情報を削除する。即ち、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致し（ステップＳ１６の判定）、且つ、変化したリンク利用率が、ランク表の最下位のリンク利用率と同じか低い（ステップＳ１７の判定）ので、ランク表に登録されていたリンク情報が削除される。
【０１２７】
ステップＳ４２において、構築部１６４は、ランク表のランク数がゼロかを判定する。
【０１２８】
ランク表のランク数がゼロでない場合、ステップＳ４２においてＮＯであると判定され、処理はステップＳ４３に進む。
【０１２９】
ステップＳ４３において構築部１６４はランク表を再構築する。即ち、順位が書き換えられる。
【０１３０】
ここで、処理がステップＳ４１からステップＳ４２に進み、ステップＳ４２でＮＯと判定され、ステップＳ４３に進んだ場合の具体的な例について、図１８乃至図２１を参照して説明する。
【０１３１】
図１８は、ネットワーク１０１のリンク利用率を示す図である。図１８は、図６を参照して説明した初期状態から、リンクID（１１２−２，１１２−１）のリンク利用率が、０．９８から０．７０に変化した状態を表している。
【０１３２】
図１０の初期化処理時に構築されたランク表によると、ランク１位のリンクID（１１２−２，１１２−１）と、変化したリンク利用率のリンクID（１１２−２，１１２−１）は、一致している。しかし、変化したリンク利用率０．７０は、ランク表の最下位のリンク利用率０．８２より低い。よって、この場合はケース２に該当すると判定され、ランク表再構築処理２が実行される。
【０１３３】
図１９は、ランク表の例を示す図である。図１９は、図１８を参照して説明したリンク利用率の変化に伴い、ランク表再構築処理２の処理によって図１０に示されるランク表が再構築されたランク表を表している。
【０１３４】
図１９に示されるように、図１０のランク表においてランク１位のリンク情報は削除され、ランク表のランク数は２となる。
【０１３５】
即ち、図１０においてランク１位であったリンクID（１１２−２，１１２−１）のリンク利用率が０．９８から０．７０に変化し、このリンク利用率は最下位のリンク利用率である０．８２より小さいので、このリンクは管理対象とする必要がなくなったことになる。そこで、それまでランク１位であったリンクID（１１２−２，１１２−１）のリンク情報が削除され、それまでランク２位であったリンクID（１１２−３，１１２−２）のリンク利用率０．８６がランク１位となる。また、それまでランク３位であったリンクID（１１２−１，１１２−２）のリンク利用率０．８２は、ランク２位となる。
【０１３６】
図２０は、ネットワーク１０１のリンク利用率を示す図である。図２０は、図１８のネットワーク１０１において、さらにリンクID（１１２−３，１１２−２）のリンク利用率が、０．８６から０．７８に変化した状態を表している。
【０１３７】
この場合も、図１９に示されるランク表のランク１位のリンクID（１１２−３，１１２−２）と、変化したリンク利用率のリンクID（１１２−３，１１２−２）は、一致している。しかし、変化したリンク利用率０．７８は、ランク表の最下位のリンク利用０．８２より低い。よって、ケース２に該当すると判定され、ランク表再構築処理２が実行される。
【０１３８】
図２１は、ランク表の例を示す図である。図２１は、図２０を参照して説明したリンク利用率の変化に伴い、ランク表再構築処理２の処理によって、図１９に示されるランク表が再構築されたランク表を表している。
【０１３９】
図２１に示されるように、図１９に示されるランク表においてランク１位のリンク情報は削除され、ランク表のランク数は１となる。
【０１４０】
即ち、図１９においてランク１位であったリンクID（１１２−３，１１２−２）のリンク利用率が０．８６から０．７８に変化し、このリンク利用率は最下位のリンク利用率である０．８２より小さいので、このリンクは管理対象とする必要がなくなったことになる。そこで、それまでランク１位であったリンクID（１１２−３，１１２−２）のリンク情報が削除され、それまでランク２位であったリンクID（１１２−１，１１２−２）のリンク利用率０．８２がランク１位となる。
【０１４１】
このように、ケース２の条件が発生する度に、ランク表のランク数は減少していく。その結果、ケース２が３回発生すると、ついにはランク数がゼロになる。
【０１４２】
図１７のランク表再構築処理２のフローチャートの説明に戻る。ステップＳ４２において、ランク表のランク数がゼロである場合、ＹＥＳであると判定され、処理はステップＳ４４に進む。
【０１４３】
ステップＳ４４において、検出部１６１、受信部１６２、構築部１６４、および出力部１６５は、初期化処理を実行する。
【０１４４】
ここで、ステップＳ４２においてＹＥＳであると判定され、処理がステップ４４に進み、初期化処理が実行される場合の具体的な例について、図２２乃至図２４を参照して説明する。
【０１４５】
図２２は、ネットワーク１０１のリンク利用率を示す図である。図２２は、図２０のネットワーク１０１において、さらにリンクID（１１２−１，１１２−２）のリンク利用率が、０．８２から０．８０に変化した状態を表している。
【０１４６】
この場合も、図２１に示されるランク表のランク１位のリンクID（１１２−１，１１２−２）と、変化したリンク利用率のリンクID（１１２−１，１１２−２）は、一致している。そして、変化したリンク利用率０．８０は、ランク表の最下位のリンク利用０．８２より低い。よって、ケース２に該当すると判定され、ランク表再構築処理２が実行される。
【０１４７】
図２３は、ランク表の例を示す図である。図２３は、図２２を参照して説明したリンク利用率の変化に伴い、ランク表再構築処理２の処理によって、図２１に示されるランク表が再構築されたランク表を表している。
【０１４８】
図２３に示されるように、図２１のランク表においてランク１位のリンク情報は削除され、ランク表のランク数は０となる。
【０１４９】
即ち、図２１においてランク１位であったリンクID（１１２−１，１１２−２）のリンク利用率が０．８２から０．８０に変化し、このリンク利用率は最下位のリンク利用率である０．８２より小さいので、このリンクは管理対象とする必要がなくなったことになる。そこで、それまでランク１位であったリンクID（１１２−１，１１２−２）のリンク情報が削除される。
【０１５０】
このようにして、ランク表のランク数がゼロになったため、ランク表再構築処理２のステップＳ４２において、ＹＥＳであると判定される。
【０１５１】
そして、ランク表再構築処理２のステップＳ４４において初期化処理が実行される。初期化処理の内容は、図９を参照して説明したとおりである。
【０１５２】
図２４は、ランク表の例を示す図である。図２４は、構築部１６４によりランク表再構築処理２が最大ランク数と同じ数だけ繰り返された結果、ランク数がゼロとなり、初期化処理が実行された場合のランク表を表している。
【０１５３】
即ち、図２２のネットワーク１０１のリンク情報に基づき、リンクID（１１２−１，１１２−２）のリンク利用率０．８０がランク１位に、リンクID（１１２−３，１１２−２）のリンク利用率０．７８がランク２位に、リンクID（１１２−２，１１２−４）のリンク利用率０．７７がランク３位として、構築部１６４は、図２４に示されるランク表を再構築する。
【０１５４】
以上説明したように、構築部１６４は、ケース２の条件でリンク利用率の変化した場合、ランク外になったリンク情報を削除する。また、構築部１６４は、リンク情報が繰り返し削除され、ランク数がゼロになった場合、初期化処理を実行し、新たなランク表を構築する。
【０１５５】
図２５は、ランク表再構築処理３について説明するフローチャートである。ランク表再構築処理３は、図１２のフローチャートのステップＳ２０の処理である。また、ランク表再構築処理３は、図１１を参照して説明したケース３の場合に、構築部１６４がランク表を再構築する処理である。
【０１５６】
ステップＳ５１において、構築部１６４は、リンク情報を追加する。図１２を参照して説明したように、変化したリンク利用率のリンクIDと、ランク表のリンクIDが一致せず（ステップＳ１２でＮＯ）、且つ、変化したリンク情報のリンク利用率が、最下位のリンク利用率と同じか低い場合（ステップＳ１４でＮＯ）は、広告しないケース（ケース４）に該当する。このため、この場合はそもそも広告がなされない。つまり、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致しない（ステップＳ１６の処理）としてランク表再構成処理３が実行される場合は、図１２のステップＳ１４でＹＥＳと判定された場合（受信したリンク利用率が、最下位のリンク利用率より高い場合）である。このため、ステップＳ５１において、受信した（広告された）リンク情報は、ランク表に追加される。
【０１５７】
ステップＳ５２において、構築部１６４は、ランク表を再構築する。即ち、ランク表の順位が調整される。
【０１５８】
ステップＳ５３において、構築部１６４は、ランク外となったリンク情報を削除して、ランク表を書き換える。
【０１５９】
図２６および２７を参照して、構築部１６４がランク表再構築処理３を実行し、ランク表を再構築する場合の具体的な例について説明する。
【０１６０】
図２６は、ネットワーク１０１のリンク利用率を示す図である。図２６は、図６を参照して説明した初期状態から、リンクID（１１２−４，１１２−２）のリンク利用率が、０．２２から０．８４に変化した状態を表している。
【０１６１】
図１０の初期化処理時に構築されたランク表によると、ランク１位のリンクID（１１２−２，１１２−１）、ランク２位のリンクID（１１２−３，１１２−２）およびランク３位のリンクID（１１２−１，１１２−２）と、変化したリンク利用率のリンクID（１１２−４，１１２−２）は、一致していない。さらに、変化したリンク利用率０．８４は、ランク表の最下位のリンク利用０．８２より高い。よって、この場合はケース３に該当すると判定され、ランク表再構築処理３が実行される。
【０１６２】
図２７は、ランク表の例を示す図である。図２７は、図２６を参照して説明したリンク利用率の変化に伴い、ランク表再構築処理３の処理によって、図１０に示されるランク表が再構築されたランク表を表している。
【０１６３】
図１０においてランク外であったリンクID（１１２−４，１１２−２）のリンク利用率が０．２２から０．８４に変化したことにより、リンク情報が追加される。即ち、リンクID（１１２−４，１１２−２）のリンク利用率０．８４がランク表に追加される。これにより、それまでランク１位であったリンクID（１１２−２，１１２−１）のリンク利用率０．９８と、それまでランク２位であったリンクID（１１２−３，１１２−２）のリンク利用率０．８６のランクはそのまま変化しない。そして、それまでランク外であったリンクID（１１２−４，１１２−２）のリンク利用率０．８４が追加されて、ランク３位となる。リンク情報追加前にはランク３位であったリンクID（１１２−１，１１２−２）のリンク利用率０．８２は、削除される。
【０１６４】
以上説明したように、構築部１６４は、ケース３の条件でリンク利用率が変化した場合、新たなリンク情報を追加登録し、ランク外になったリンク情報を削除する。
【０１６５】
図２８は、以上のようにしてネットワークを管理した場合におけるランク数の推移を示す図である。なお、図２８において、最大ランク数は３と定義されているとする。
【０１６６】
ノード１１２が初期化処理を実行した場合、ランク数は、最大ランク数である３である。
【０１６７】
初期化処理実行後、リンク利用率が変化して、ケース１と判定された場合、ランク数は３のまま変化しない。また、さらにリンク利用率が変化して、ケース３と判定された場合も、ランク数は３のまま変化しない。
【０１６８】
次に、リンク利用率が変化して、ケース２と判定された場合、ランク数はランク表再構築処理２の処理により、ランク数が１減少し、ランク数は２となる。また次にリンク利用率が変化して、ケース１と判定された場合、ランク数は２のまま変化しない。
【０１６９】
次にリンク利用率が変化して、ケース２と判定された場合、ランク数はさらに１減少し、ランク数は１となる。また次にリンク利用率が変化して、ケース２と判定された場合、ランク数はさらに１減少し、ランク数は０となる。そして、ランク表再構築処理２の処理により、初期化処理が実行され、ランク数は最大ランク数である３に戻る。
【０１７０】
次にリンク利用率が変化して、ケース３と判定された場合、ランク数は３のまま変化しない。また次にリンク利用率が変化して、ケース１と判定された場合、ランク数は３のまま変化しない。
【０１７１】
即ち、ランク表のランク数は、リンク利用率が変化しても、ケース１およびケース３の場合は、現状維持のまま推移する。それに対し、ケース２の条件でリンク利用率が変化した場合、ランク表のランク数は、１ずつ減少する。そしてランク表のランク数がゼロになると、初期化処理が実行されてランク数は最大ランク数に戻る。
【０１７２】
このように、本発明では、最大リンク利用率によりネットワークを管理するネットワーク制御方法において、所定のランク以内に入っているリンク利用率のみをコントローラ１１１およびノード１１２が保持する、LLR(link load ranking)法が用いられる。LLR法を適用した本発明によれば、リンク利用率が変化したときの広告されるリンク情報の数（以下、広告数と称する）を削減することができる。
【０１７３】
[コンピュータ・シミュレーションによる性能評価]
LLR法を適用した本発明による、広告数の削減の効果について、図２９乃至図３１を参照して説明する。
【０１７４】
図２９は、IPネットワークバックボーンの一例を示す図である。LLR法を適用した本発明の性能を評価するためのシミュレーションの対象として、図２９に示すIPネットワークバックボーンが適用された。
【０１７５】
ネットワーク２０１は、２４のノード（ノード１１２−１乃至１１２−２４）および４３の双方向リンクにより構成される。即ち、片方向のリンク数は、８６である。
【０１７６】
シミュレーションは、タイムスロット（単位時間）以内に、最も遠いノード１１２（例えばノード１１２−２４）からネットワーク制御装置（例えばノード１１２−１）にリンク情報が到達すると仮定して実施された。また、シミュレーションは、実施時間を１０００タイムスロット時間とし、リンク利用率が単位時間内に変化する確率Pを０．０５、０．２、および０．５として実施された。
【０１７７】
図３０は、最大ランク数と広告率の関係を示す図である。広告率とは、リンク利用率が変化する回数に対する、リンク情報が広告される回数の割合である。図３０は、図２９のネットワーク２０１におけるシミュレーションの結果得られた、最大ランク数と広告率の関係を表している。
【０１７８】
従来の技術では、リンク利用率が変化する度に、リンク情報が広告されるので、広告率は１．０である。
【０１７９】
図２９のネットワーク２０１のリンク数が８６であるので、広告率１．０というのは、LLR法においては最大ランク数８６に該当する。換言すると、従来の技術における広告の回数と、LLR法における最大ランク数８６の場合の広告の回数が一致し、広告率は１．０となる。
【０１８０】
よって、ネットワーク２０１の例においては、LLR法を適用すると、最大リンク数は、１から８５の範囲を取り得る。
【０１８１】
図３０の最大ランク数と広告率の関係を参照すると、以下のことが分かる。即ち、リンク利用率が単位時間内に変化する確率Pが０．０５および０．２の場合には、最大ランク数が１から４の範囲において、広告率は、最大ランク数の増加に伴い減少する。そして、広告率は、最大ランク数４で最小値を取った後、最大ランク数の増加に伴い増加する。
【０１８２】
また、リンク利用率が単位時間内に変化する確率Pが０．５の場合には、最大ランク数が１から６の範囲において、広告率は、最大ランク数の増加に伴い減少する。そして、広告率は、最大ランク数６で最小値を取った後、最大ランク数の増加に伴い増加する。
【０１８３】
最大ランク数が小さいと、リンク利用率が変化する回数に対してリンク情報が広告される回数は減少する。しかしながら、最大ランク数が小さすぎると、上述したケース２に該当する場合が増え、ランク数が１ずつ減少された結果、初期化処理が実行される回数が増える。このため、結果的に広告数が増大する場合がある。
【０１８４】
図３１は、最大ランク数とランク表リセット率の関係を示す図である。ランク表リセット率とは、全タイムスロット数に対するランク表が初期化処理される回数の割合である。
【０１８５】
リンク利用率が単位時間内に変化する確率Pが０．０５，０．２，０．５のいずれの場合においても、ランク表リセット率はランク数が１の時に最大となる。
【０１８６】
また、同一のランク数の場合には、リンク利用率が単位時間内に変化する確率Pが大きいほど、ランク表リセット率が大きくなる。これは、リンク利用率が単位時間内に変化する確率Pが大きいほど、リンク利用率が変化しやすく、ランク数が減少する確率が高くなるためである。
【０１８７】
このように、最大ランク数がある値以下であれば、初期化処理が実行される機会が増え、広告数が増加する。また、最大ランク数が大きすぎると、広告される対象のリンク数が増加するため、広告数が増大する。従って、広告率を最小化することのできる最適な最大ランク数が存在するのである。
【０１８８】
例えば、図３０に示された広告率と最大ランク数の関係においては、リンク利用率が単位時間内に変化する確率Pが０．０５および０．２の場合には、最適な最大ランク数は４である。また、リンク利用率が単位時間内に変化する確率Pが０．５の場合には、最適な最大ランク数は６である。
【０１８９】
[最適な最大ランク数]
広告を最小化する最大ランク数は、以下の式（１）で求められる。
【０１９０】
なお、式（１）において、各リンクのリンク利用率が単位時間内に変化する確率をP、ネットワーク１０１のリンク数をLとする。最大ランク数Rmaxの範囲は、１≦Rmax≦Lである。また、リンク利用率が変化する回数に対して、広告される回数の割合（広告率）をθ（P, Rmax）とする。式（１）の最適最大ランク数Rmaxoptは、θ（P, Rmax）を最小化する最適な最大ランク数Rmaxである。
【０１９１】
【数１】
【０１９２】
以上、図２９乃至図３１を参照して説明したシミュレーションの結果、LLR法を適用した本発明によれば、従来の技術に比べ、広告数を最大９２％削減することができた。
【０１９３】
換言すると、LLR法を適用した本発明によれば、リンク情報をリンク利用率によってランク付けし、所定のランク以内に入っているリンク情報のみを保持することにより、ネットワーク資源を有効に利用することができるようになる。
【０１９４】
［変形例等］
上述した一連の処理は、ハードウェアにより実行することもできるし、ソフトウェアにより実行することもできる。一連の処理をソフトウェアにより実行する場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、汎用のパーソナルコンピュータなどにインストールされる。
【０１９５】
インストールされるプログラムは、図７の磁気ディスク１５１、光ディスク１５２、光磁気ディスク１５３、或いは半導体メモリ１５４等に記録して提供される。また、ローカルエリアネットワーク、インターネット、デジタル放送といった、有線または無線の伝送媒体を介して提供されるようにしてもよい。プログラムは、ROM１３２や記憶部１３８に、あらかじめインストールしておくことができる。
【０１９６】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０１９７】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０１９８】
１ ネットワーク， １１ コントローラ， １２ ノード， １０１ ネットワーク， １１１ コントローラ， １１２ ノード， １３１ CPU， １３２ ROM， １３３ RAM， １３４ バス， １３５ 入出力インタフェース， １３６ 操作部， １３７ インジケータ， １３８ 記憶部， １３９ LAN通信部， １４０ WAN通信部， １４１ ドライブ， １５１ 磁気ディスク， １５２ 光ディスク， １５３ 光磁気ディスク， １５４ 半導体メモリ， １６１ 検出部， １６２ 受信部， １６３ 判定部， １６４ 構築部， １６５ 出力部， ２０１ ネットワーク
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、およびプログラムに関し、特に、ネットワーク資源を効率的に利用することができる情報処理装置、情報処理方法、およびプログラムに関する。
【背景技術】
【０００２】
Open Shortest Path First(OSPF)ネットワークにおいては、トラヒック需要の変化に対してリンク利用効率を向上させるために、ネットワーク内のリンク利用率の最大値である、最大リンク利用率に基づきネットワークが管理される。なお、最大リンク利用率は、ネットワーク輻輳率ともいう。
【０００３】
非特許文献１乃至４に開示されているOSPFネットワークは、ネットワーク制御装置および複数のノードから構成される。OSPFネットワークにおいて、適切なルーチングはネットワークスループットおよびリソース利用効率を向上させる。ルーチング性能を向上させるアプローチとして、最大リンク利用率を最小化する手法がある（非特許文献４）。ネットワーク制御装置は、最大リンク利用率を有するリンクを特定し、そのリンクに流れるトラヒック量を低減させることにより、ネットワークスループットおよびリソース利用効率を向上させることができる。
【０００４】
OSPFネットワークにおいて、各ノードおよびネットワーク制御装置は、リンクの両端のノードを表すリンク識別情報であるリンクID(Identification)と、そのノードにおけるリンク利用率を含むリンク情報を保持している。なお、リンク情報は、OSPF Traffic Engineering（OSPF-TE）のメカニズムにより実現される（非特許文献４）。
【０００５】
非特許文献３に開示されている技術によれば、各ノードおよびネットワーク制御装置が、ネットワーク内のすべてのリンク情報を保持している。そして、ネットワーク内のいずれかのリンクのリンク利用率が変化するたびに、変化したリンク情報が各ノードおよびネットワーク制御装置に広告される。
【０００６】
各ノードおよびネットワーク制御装置は、リンク利用率が変化したことを伝えるリンク情報を受信すると、最大リンク利用率を更新する。ネットワーク制御装置は最大リンク利用率を活用して、ルーチング制御を行う。
【０００７】
従来の技術について、図１乃至図３を用いて説明する。図１は、OSPFネットワーク１の構成例を示す図である。
【０００８】
図１のネットワーク１は、コントローラ１１およびノード１２−１乃至１２−４から構成されている。
【０００９】
コントローラ１１は、ネットワーク１全体を制御するネットワーク制御装置である。コントローラ１１は、ネットワーク１全体のリンク情報を保持している。コントローラ１１は、最大リンク利用率を有するリンクを特定し、そのリンクに流れるトラヒック量を低減させる管理を行う。
【００１０】
ノード１２−１乃至１２−４は、ネットワーク１に接続されている、例えばルータ、クロスコネクト装置、レイヤ２スイッチ等により構成される。以下、ノード１２−１乃至１２−４を特に区別する必要のない場合、まとめてノード１２と称する。なお、コントローラ１１も、ノード１２の一種である。
【００１１】
図２は、従来の技術におけるネットワーク１のリンク利用率を示す図である。
【００１２】
図２の各ノード１２間の矢印はリンクの方向を示しており、矢印に付されている数字は、そのリンクのリンク利用率を示している。
【００１３】
一例として、ノード１２−１からノード１２−２に向かうリンクのリンク利用率は、０．８２である。なお、以下、リンクの両端のノード表すリンクIDは、リンク元のノード（以下、発ノードと称する）ｉからリンク先のノード（以下、着ノードと称する）ｊの順に（i,j）として表現される。
【００１４】
即ち、ノード１２−１からノード１２−２に向かうリンクのリンクIDは、（１２−１,１２−２）と表現される。
【００１５】
図２の例においては、リンク１２−１が発ノードであるリンクID（１２−１,１２−２）のリンク利用率は０．８２、リンクID（１２−１，１２−３）のリンク利用率は０．７１である。
【００１６】
リンク１２−２が発ノードであるリンクID（１２−２,１２−１）のリンク利用率は０．９８、リンクID（１２−２,１２−３）のリンク利用率は０．６４、リンクID（１２−２，１２−４）のリンク利用率は０．７７である。
【００１７】
リンク１２−３が発ノードであるリンクID（１２−３,１２−１）のリンク利用率は０．３９、リンクID（１２−３，１２−２）のリンク利用率は０．８６、リンクID（１２−３，１２−４）のリンク利用率は０．６９である。
【００１８】
リンク１２−４が発ノードであるリンクID（１２−４,１２−２）のリンク利用率は０．２２、リンクID（１２−４，１２−３）のリンク利用率は０．１０である。
【００１９】
すべてのノード１２は、自身のノード（以下、自ノードともいう）を発ノードとするリンクのリンクIDと、リンク利用率を含むリンク情報を、コントローラ１１を含むすべての自ノード以外のノード１２（以下、他ノードともいう）に広告する。
【００２０】
具体的には、ノード１２−１は、自ノードが発ノードとなるリンクID（１２−１,１２−２）およびリンクID（１２−１,１２−３）のリンク情報を、接続されているノードであるコントローラ１１、ノード１２−２および１２−３に広告する。
【００２１】
ノード１２−２は、ノード１２−１からリンクID（１２−１,１２−２）およびリンクID（１２−１,１２−３）のリンク情報を受信すると、さらにそのリンク情報を、接続されているノードであるノード１２−３およびノード１２−４に広告する。
【００２２】
また、ノード１２−２は、自ノードが発ノードとなるリンクID（１２−２,１２−１）、リンクID（１２−２,１２−３）およびリンクID（１２−２,１２−４）のリンク情報を、接続されているノードであるノード１２−１、ノード１２−３および１２−４に広告する。
【００２３】
このようにして、リンク情報がノード１２間を順次伝播し、最終的にはすべてのノード（コントローラ１１を含む）に、各ノード１２のリンク情報が広告される。このように、自ノードが広告したリンク情報を、他ノード間を順次伝播させてすべての他ノードに広告することを、以下、単に他ノードに広告する、とも表現する。
【００２４】
図３は、従来の技術におけるリンク利用率のランク表を示す図である。ランク表とは、広告されたリンク情報に基づいて、コントローラ１１およびノード１２が構築する表である。コントローラ１１およびノード１２は、受信したすべてのリンク情報に含まれるリンクIDとリンク利用率を用いて、リンク利用率の高い順に順位づけを行い、ランク表を構築する。
【００２５】
図３の例においては、最もリンク利用率の高いリンクID（１２−２,１２−１）のリンク利用率０．９８がランク１位となり、次にリンク利用率の高いリンクID（１２−３,１２−２）のリンク利用率０．８６がランク２位となる。さらに、次にリンク利用率の高いリンクID（１２−１,１２−２）のリンク利用率０．８２がランク３位となる。このようにして、ネットワーク１に接続されている全部で１０のリンクについて、１０位までのランク表が構築される。
【００２６】
図４は、従来の技術におけるネットワーク１のリンク利用率を示す図である。図４は、図２に示されるネットワーク１において、リンクID（１２−３，１２−４）のリンク利用率が、０．６９から０．３０に変化した状態を表している。
【００２７】
この場合、発ノードであるノード１２−３が、接続されているノードであるノード１２−１、ノード１２−２およびノード１２−４に、リンクID（１２−３，１２−４）のリンク情報を広告する。ノード１２−１は、リンク情報をノード１２−３から受信すると、受信したリンク情報を、接続されているノードであるコントローラ１１およびノード１２−２に広告する。
【００２８】
このようにして、順次リンク情報が各ノード１２に接続されているノード１２に広告され、最終的に、リンク情報は、コントローラ１１および全てのノード１２に広告される。そして、コントローラ１１およびノード１２は、受信したリンク情報に基づいて、ランク表を更新する。
【００２９】
図５は、従来の技術におけるリンク利用率のランク表を示す図である。図５は、図４を参照して説明したリンク利用率の変化に伴い、コントローラ１１およびノード１２が再構築したランク表を表している。
【００３０】
リンクID（１２−３，１２−４）のリンク利用率は、図３に示すランク表において、６位であったが、リンク利用率が変化したことにより、図５に示すランク表においては、８位に降下している。
【先行技術文献】
【非特許文献】
【００３１】
【非特許文献１】J.Moy, “OSPF Version 2,”RFC 2328,Apr.1998.
【非特許文献２】D.Katz,K.Kompella,and K.Kompella“Traffic Engineering(TE)Extensions to OSPF Version2,”RFC 3630,Sep.2003
【非特許文献３】Y.Koizumi,T.Miyamura,S.Arakawa,E.Oki,K.Shiomoto,and M.Murata, “Adaptive Virtual Network Topology Control Based on Attractor Selection,”IEEE/OSA J.Light.Tech.,vol.28,no.11,pp1720-1731,Jun.2010.
【非特許文献４】E.Oki and A.Iwaki, “Load-Balanced IP Routing Scheme Based on Shortest Paths in Hose Model,”IEEE Trans.Commum.,vol.58,no.7,pp.2088-2096,Jul.2010.
【発明の概要】
【発明が解決しようとする課題】
【００３２】
しかしながら、コントローラ１１は、上述したように、ネットワーク１を管理するのに最大リンク利用率のみを必要とする。それにも関わらず、最大でないリンク利用率についても頻繁に広告されており、広告されるリンク情報が膨大な量になることで、ネットワーク資源が浪費されている。
【００３３】
本発明はこのような状況に鑑みてなされたものであり、ネットワーク資源を効率的に利用することができるようにするものである。
【課題を解決するための手段】
【００３４】
本発明の一側面の情報処理装置は、ネットワークのリンクを、その利用率が高い順に順位付けて登録リンクとして登録したランク表であって、前記ネットワークの全リンク数より少ない数の、前記リンクを登録する最大の数である最大リンク数が予め定められている前記ランク表を構築し、前記利用率が変化した前記リンクである変化リンクが発生した場合、前記ランク表を再構築する構築部を備え、前記構築部は、前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、前記登録リンク数が前記最大リンク数の範囲内になるように前記ランク表を書き換え、前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より低い値に変化した場合、前記変化リンクを前記登録リンクから削除して、前記ランク表を書き換える。
【００３５】
前記変化リンクを前記登録リンクから削除した結果、前記登録リンクの数がゼロになった場合、前記ネットワークのすべての前記リンクの利用率に基づいて前記ランク表を初期化することができる。
【００３６】
前記変化リンクが前記登録リンクである場合、並びに前記登録リンクでない前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、他の情報処理装置に前記変化リンクの前記リンク利用率およびリンク識別情報を広告することができる。
【００３７】
前記最大リンク数は、１以上且つ前記ネットワークに存在するリンク数以下の範囲内で、変化リンクが発生する回数に対する広告される回数の割合を最小にする数にすることができる。
【００３８】
本発明の一側面である情報処理装置の情報処理方法とプログラムのそれぞれは、上述した本発明の情報処理装置に対応する方法とプログラムのそれぞれである。
【００３９】
本発明の一側面においては、ネットワークのリンクを、その利用率が高い順に順位付けて登録リンクとして登録したランク表であって、前記ネットワークの全リンク数より少ない数の、前記リンクを登録する最大の数である最大リンク数が予め定められている前記ランク表が構築され、前記利用率が変化した前記リンクである変化リンクが発生した場合、前記ランク表が再構築される。前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、前記登録リンク数が前記最大リンク数の範囲内になるように前記ランク表が書き換えられ、前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より低い値に変化した場合、前記変化リンクが前記登録リンクから削除されて、前記ランク表が書き換えられる。
【発明の効果】
【００４０】
本発明によれば、ネットワーク資源を効率的に利用できるようになる。
【図面の簡単な説明】
【００４１】
【図１】OSPFネットワークの構成例を示す図である。
【図２】従来の技術におけるネットワークのリンク利用率を示す図である。
【図３】従来の技術におけるリンク利用率のランク表を示す図である。
【図４】従来の技術におけるネットワークのリンク利用率を示す図である。
【図５】従来の技術におけるリンク利用率のランク表を示す図である。
【図６】本発明の一実施形態に係るネットワークの構成例を示す図である。
【図７】本発明の一実施形態に係るノードの構成例を示すブロック図である。
【図８】ノードの機能的構成例を示すブロック図である。
【図９】ノードの初期化処理について説明するフローチャートである。
【図１０】ランク表の例を示す図である。
【図１１】リンク情報を広告する条件について説明する図である。
【図１２】広告判定処理について説明するフローチャートである。
【図１３】ネットワークのリンク利用率を示す図である。
【図１４】ランク表再構築処理１について説明するフローチャートである。
【図１５】ネットワークのリンク利用率を示す図である。
【図１６】ランク表の例を示す図である。
【図１７】ランク表再構築処理２について説明するフローチャートである。
【図１８】ネットワークのリンク利用率を示す図である。
【図１９】ランク表の例を示す図である。
【図２０】ネットワークのリンク利用率を示す図である。
【図２１】ランク表の例を示す図である。
【図２２】ネットワークのリンク利用率を示す図である。
【図２３】ランク表の例を示す図である。
【図２４】ランク表の例を示す図である。
【図２５】ランク表再構築処理３について説明するフローチャートである。
【図２６】ネットワークのリンク利用率を示す図である。
【図２７】ランク表の例を示す図である。
【図２８】ランク数の推移を示す図である。
【図２９】IPネットワークバックボーンの一例を示す図である。
【図３０】最大ランク数と広告率の関係を示す図である。
【図３１】最大ランク数とランク表リセット率の関係を示す図である。
【発明を実施するための形態】
【００４２】
以下、本発明を実施するための形態について説明する。
【００４３】
[ネットワークの構成例]
図６は、本発明の一実施形態に係るネットワーク１０１の構成例を示す図である。
【００４４】
図６のネットワーク１０１は、コントローラ１１１およびノード１１２−１乃至１１２−４から構成されている。
【００４５】
コントローラ１１１は、ネットワーク１０１全体を制御するネットワーク制御装置である。コントローラ１１１は、ネットワーク１０１全体のリンク情報を保持している。コントローラ１１１は、最大リンク利用率を有するリンクを特定し、そのリンクに流れるトラヒック量を低減させる管理を行う。
【００４６】
ノード１１２−１乃至１１２−４は、ネットワーク１０１に接続されている、例えばルータ、クロスコネクト装置、レイヤ２スイッチ等により構成される。以下、ノード１１２−１乃至１１２−４を特に区別する必要のない場合、まとめてノード１１２と称する。なお、コントローラ１１１も、ノード１１２の一種である。
【００４７】
図６の各ノード１１２間の矢印はリンクの方向を示しており、矢印に付されている数字は、そのリンクのリンク利用率を示している。
【００４８】
図６のネットワーク１０１において、リンク１１２−１が発ノードであるリンクID（１１２−１,１１２−２）のリンク利用率は０．８２、リンクID（１１２−１，１１２−３）のリンク利用率は０．７１である。
【００４９】
リンク１１２−２が発ノードであるリンクID（１１２−２,１１２−１）のリンク利用率は０．９８、リンクID（１１２−２,１１２−３）のリンク利用率は０．６４、リンクID（１１２−２，１１２−４）のリンク利用率は０．７７である。
【００５０】
リンク１１２−３が発ノードであるリンクID（１１２−３,１１２−１）のリンク利用率は０．３９、リンクID（１１２−３，１１２−２）のリンク利用率は０．８６、リンクID（１１２−３，１１２−４）のリンク利用率は０．６９である。
【００５１】
リンク１１２−４が発ノードであるリンクID（１１２−４,１１２−２）のリンク利用率は０．２２、リンクID（１１２−４，１１２−３）のリンク利用率は０．１０である。なお、図６に示される各リンクのリンク情報を、以下、初期状態と称する。
【００５２】
[情報処理装置の構成例]
図７は、本発明の一実施形態に係るノード１１２の構成例を示すブロック図である。
【００５３】
図７において、CPU（Central Processing Unit）１３１は、ROM１３２に記憶されているプログラム、または記憶部１３８からRAM１３３にロードされたプログラムに従って各種の処理を実行する。RAM１３３にはまた、CPU１３１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【００５４】
CPU１３１、ROM１３２、およびRAM１３３は、バス１３４を介して相互に接続されている。このバス１３４にはまた、入出力インタフェース１３５も接続されている。
【００５５】
入出力インタフェース１３５には、ボタンやスイッチなどよりなる操作部１３６、LED（Light Emitting Diode）などよりなるインジケータ１３７、ハードディスクなどより構成される記憶部１３８、ユーザが所有するパーソナルコンピュータやCE（Consumer Electronics）機器との通信を制御するLAN（Local Area Network）通信部１３９、並びに図示せぬモデムを介したバスなどとの通信を制御するWAN（Wide Area Network）通信部１４０が接続されている。
【００５６】
入出力インタフェース１３５にはまた、必要に応じてドライブ１４１が接続され、磁気ディスク１５１、光ディスク１５２、光磁気ディスク１５３、或いは半導体メモリ１５４などが適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部１３８にインストールされる。
【００５７】
図８は、ノード１１２の機能的構成例を示すブロック図である。図８に示す機能部のうちの少なくとも一部は、図７のCPU１３１により所定のプログラムが実行されることによって実現される。
【００５８】
図８において、CPU１３１は、検出部１６１、受信部１６２、判定部１６３、構築部１６４および出力部１６５を含むように構成されている。
【００５９】
検出部１６１は、自ノードが発ノードとなるリンクに関するリンク情報を検出する。また、検出部１６１は、検出したリンク情報を、判定部１６３に出力する。
【００６０】
受信部１６２は他ノードから広告されたリンク情報を受信する。受信部１６２は、受信したリンク情報を、判定部１６３および出力部１６５に出力する。
【００６１】
判定部１６３は、検出部１６１から供給されたリンク情報が他ノード（コントローラ１１１およびノード１１２）に広告すべきリンク情報であるか否かを判定する。他ノードに広告すべきリンク情報であった場合、判定部１６３は、リンク情報を出力部１６５に出力する。また、判定部１６３は、受信部１６２から供給されたリンク情報が、ランク表を再構築する複数のケースのうち、何れのケースに該当するかを判定する。
【００６２】
構築部１６４は、判定部１６３から受信したリンク情報およびランク表が保持する最大のランク数である、最大ランク数に基づき、リンク利用率の高い順にランク表を構築する。即ち、リンク情報をランク表に登録リンクとして登録する。構築部１６４は、構築したランク表を保持する。
【００６３】
出力部１６５は、判定部１６３から出力されたリンク情報を、他ノードに出力する。換言すると、出力部１６５は、判定部１６３により他ノードに広告すべきと判定されたリンク情報を、他ノードに広告する。
【００６４】
また、出力部１６５は、受信部１６２から出力された、他ノードから広告されたリンク情報を、広告を発したノード以外の他ノードに出力する。
【００６５】
［情報処理装置の動作］
図９は、ノード１１２の初期化処理について説明するフローチャートである。初期化処理とは、ノード１１２がランク表を最初に構築する場合に実行する処理である。初期化処理は、例えば、ネットワーク管理者等により命令がなされた場合に開始される。
【００６６】
ステップＳ１において、検出部１６１は、自ノードのリンク情報を検出する。即ち、自ノードを発ノードとするリンクのリンク情報を検出する。具体的には、リンク利用率が検出される。
【００６７】
ステップＳ２において、出力部１６５は、自ノードのリンク情報を広告する。即ち、検出部１６１が検出した自ノードを発ノードとするリンクのリンク情報を、他ノードに広告する。
【００６８】
ステップＳ３において、受信部１６２は、全ノードのリンク情報を受信する。即ち、初期化処理はすべてのノード１１２において実行されるので、すべての他ノードからリンク情報が送信されてきた場合、これが受信される。
【００６９】
ステップＳ４において、構築部１６４は、リンク利用率の大きい順にランク表を構築する。即ち、受信部１６２が受信した全てのノード１１２のリンク情報に基づき、リンク利用率の大きい順にランク表を構築する。
【００７０】
ステップＳ５において、構築部１６４は、最大ランク数のリンク情報を保持し、それ以下のリンク情報を破棄する。以上で、初期化処理は終了する。最大ランク数は、初期化処理を実行するにあたり、予め設定されている値である。なお、ネットワーク１０１に最適な最大ランク数についての詳細は、図２９乃至図３１を参照して後述する。
【００７１】
次に、図９を参照して説明した初期化処理時に構築されたランク表の一例を、図１０を参照して説明する。
【００７２】
図１０は、ランク表の例を示す図である。図１０に示されるランク表は、図６のネットワーク１０１におけるリンク情報に基づいて構築されている。
【００７３】
図６に示された初期状態について、図９を参照して説明した初期化処理のステップＳ４の処理により、構築部１６４は、リンク利用率の高い順に順位付けを行う。
【００７４】
即ち、リンクID（１１２−２，１１２−１）のリンク利用率０．９８がランク１位であり、換言すると、リンクID（１１２−２，１１２−１）のリンク利用率０．９８がネットワーク１０１における最大リンク利用率である。また、リンクID（１１２−３，１１２−２）のリンク利用率０．８６がランク２位、リンクID（１１２−１，１１２−２）のリンク利用率０．８２がランク３位となる。
【００７５】
なお、図１０の例では、最大ランク数が３と定義されているとする。よって、ランク表には、ランク３位までのリンク情報しか保持されない。図９を参照して説明した初期化処理のステップＳ５の処理により、ランク４位以下のリンク情報は、破棄される。このようにして、初期化処理時に図１０に示されるランク表が構築され、保持される。
【００７６】
次に、初期化処理終了後に、ネットワーク１０１において何れかのリンクのリンク利用率が変化した場合、即ち、リンク利用率が変化した変化リンクが発生した場合について、図１１乃至図３５を参照して説明する。
【００７７】
図１１は、リンク情報を広告する条件について説明する図である。即ち、図１１は、ノード１１２が、自ノードを発ノードとするリンクにおいてリンク利用率が変化した場合に、他ノードにリンク情報を広告するか否かを判断する基準を示している。
【００７８】
変化したリンク利用率がランク表の最下位のリンク利用率より高く、且つ変化したリンク利用率のリンクIDとランク表にあるリンクIDが一致した場合（以下、ケース１と称する）、ノード１１２は、変化したリンクのリンク利用率とリンクIDを含むリンク情報を、他ノードに広告する。ケース１の具体的な例については、図１５および１６を参照して後述する。
【００７９】
変化したリンク利用率がランク表の最下位のリンク利用率と同じか低く、且つ変化したリンク利用率のリンクIDとランク表にあるリンクIDが一致した場合（以下、ケース２と称する）、ノード１１２は、変化したリンク利用率とリンクIDを含むリンク情報を、他ノードに広告する。ケース２の具体的な例については、図１８乃至図２４を参照して後述する。
【００８０】
変化したリンク利用率がランク表の最下位のリンク利用率より高く、且つ、変化したリンク利用率のリンクIDとランク表にあるリンクIDが一致しない場合（以下、ケース３と称する）、ノード１１２は、変化したリンク利用率を含むリンク情報を、他ノードに広告する。ケース３の具体的な例については、図２６および２７を参照して後述する。
【００８１】
変化したリンク利用率がランク表の最下位のリンク利用率と同じか低く、且つ変化したリンク利用率のリンクIDとランク表にあるリンクIDが一致しない場合（以下、ケース４と称する）、ノード１１２は、変化したリンク利用率を含むリンク情報を、他ノードに広告しない。この場合の具体的な例については、図１３を参照して後述する。
【００８２】
換言すると、上述したケース１乃至ケース３においては、変化リンクの発生によりランク表を再構築する必要があるため、ノード１１２はリンク情報を広告する。
【００８３】
一方、ケース４の場合、変化リンクの発生によりランク表を再構築する必要がないため、ノード１１２はリンク情報を広告しない。
【００８４】
なお、ケース１乃至ケース３の区分は、広告されたリンク情報を受信してランク表を再構築する処理においても利用される。ケース１乃至ケース３の区分を利用してランク表を再構築する処理については、図１４乃至図２７を参照して後述する。
【００８５】
以上、図１１を参照して、ノード１１２が、自ノードを発ノードとするリンクにおいてリンク利用率が変化した場合に、他ノードにリンク情報を広告するか否かを判断する基準について説明した。
【００８６】
図１２は、広告判定処理について説明するフローチャートである。広告判定処理とは、ネットワーク１０１においてリンク利用率が変化した場合に、ノード１１２が他ノードにリンク情報を広告するか否かを判定し、さらに他ノードからリンク情報を受信した場合にランク表を再構築する処理である。広告判定処理は、初期化処理終了後に実施される。
【００８７】
ステップＳ１１において、検出部１６１は、リンク利用率が変化したかを判定する。即ち、検出部１６１が、自ノードのリンク利用率の変化を検出した場合、ステップＳ１１においてＹＥＳであると判定され、処理はステップＳ１２に進む。
【００８８】
ステップＳ１２において、判定部１６３は、変化したリンク利用率のリンクIDと、ランク表のリンクIDが一致するかを判定する。即ち、判定部１６３は、構築部１６４が保持しているランク表に基づき、リンク利用率が変化したリンクIDが、ランク表に登録されているかを判定する。
【００８９】
リンク利用率が変化したリンクIDが、ランク表に登録されている場合、ステップＳ１２においてＹＥＳであると判定され、処理はステップＳ１３に進む。即ち、変化したリンク利用率のリンクIDが、ランク表に登録されている場合は、図１１を参照して上述したように、ケース１またはケース２に該当する。よって、判定部１６３は、他ノードに広告するケースであると判断する。
【００９０】
ステップＳ１３において、出力部１６５は、他ノードにリンク情報を広告する。その後、処理はステップＳ１５に進む。ステップＳ１５以降の処理については後述する。
【００９１】
一方、ステップＳ１２の処理においてＮＯであると判定された場合、即ち、リンク利用率が変化したリンクIDが、ランク表に登録されていない場合、処理はステップＳ１４に進む。ステップＳ１４において、判定部１６３は、変化したリンク利用率は、ランク表の最下位のリンク利用率よりも高いかを判定する。
【００９２】
変化したリンク利用率が、ランク表の最下位のリンク利用率よりも高い場合、ステップＳ１４においてＹＥＳであると判定され、処理はステップＳ１３に進む。即ち、この場合、変化したリンク利用率のリンクIDと、ランク表のリンクIDが一致せず（ステップＳ１２の処理）、且つ、変化したリンク利用率が、ランク表の最下位のリンク利用率よりも高い。よって、図１１を参照して上述したように、この場合はケース３に該当する。従って、判定部１６３は、他ノードに広告する。
【００９３】
それに対し、変化したリンク利用率が、ランク表の最下位のリンク利用率と同じか低い場合、ステップＳ１４においてＮＯであると判定され、処理はステップＳ１５に進む。即ち、この場合、変化したリンク利用率のリンクIDと、ランク表のリンクIDが一致せず（ステップＳ１２の処理）、且つ、変化したリンク利用率が、ランク表の最下位のリンク利用率と同じか低い。よって、図１１を参照して上述したように、判定部１６３は、この場合は広告しないケース（ケース４）に該当すると判断する。この場合、リンク情報は広告されず、受信部１６２は、広告されたリンク情報を受信しない。よって、ステップＳ１５においてＮＯであると判定され、処理はステップＳ１１に戻る。
【００９４】
ここで、図１３を参照して、ステップＳ１２およびステップＳ１４の一連の処理で広告しないケース（ケース４）であると判定される場合について具体的に説明する。
【００９５】
図１３は、ネットワーク１０１のリンク利用率を示す図である。図１３は、図６を参照して説明した初期状態から、リンクID（１１２−４，１１２−２）のリンク利用率が、０．２２から０．５０に変化した状態を表している。
【００９６】
上述したように、初期状態において、初期化処理時に構築されたランク表は、図１０に示されたランク表である。
【００９７】
即ち、リンクID（１１２−２，１１２−１）のリンク利用率０．９８がランク１位であり、リンクID（１１２−３，１１２−２）のリンク利用率０．８６がランク２位、リンクID（１１２−１，１１２−２）のリンク利用率０．８２がランク３位である。
【００９８】
ここで、リンクID（１１２−４，１１２−２）のリンク利用率が、０．２２から０．５０に変化した場合について説明する。
【００９９】
リンクID（１１２−４，１１２−２）は、ランク表に登録されていない。また、リンクID（１１２−４，１１２−２）のリンク利用率０．５０は、ランク３位のリンク利用率０．８２より低い。従って、変化したリンク利用率は、ランク表に何ら変化をもたらさない。よって、判定部１６３は、広告しないケース（ケース４）であると判定する。
【０１００】
図１２のフローチャートの説明に戻る。以上、ステップＳ１１の処理においてＹＥＳであると判定された場合の処理について説明した。ステップＳ１１においてＮＯと判定された場合、即ち、リンク利用率が変化していない場合には、リンク表を再構築する必要がないので、ステップＳ１２乃至１４の処理は実行されず、処理はステップＳ１５に進む。この場合、リンク情報は広告されず、受信部１６２は、広告されたリンク情報を受信しない。よって、ステップＳ１５においてＮＯであると判定され、処理はステップＳ１１に戻る。
【０１０１】
ステップＳ１５において、受信部１６２は、リンク情報を受信したかを判定する。即ち、受信部１６２が、他ノードからリンク情報を受信した場合、ステップＳ１５においてＹＥＳであると判定され、処理はステップＳ１６に進む。つまり、ステップＳ１３で広告されたリンク情報を受信した他ノードも、ステップＳ１６以降の処理を実行することになる。
【０１０２】
ステップＳ１６において、判定部１６３は、リンク情報のリンクIDが一致したかを判定する。つまり、判定部１６３は、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致するか否かを判定する。即ち、判定部１６３は、構築部１６４が保持しているランク表に基づき、受信したリンク情報のリンクIDが、ランク表に登録されているかを判定する。
【０１０３】
受信したリンク情報のリンクIDが、ランク表に登録されている場合、ステップＳ１６においてＹＥＳであると判定され、処理はステップＳ１７に進む。即ち、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致した場合は、図１１を参照して上述したように、ケース１またはケース２に該当すると判断される。
【０１０４】
ステップＳ１７において、判定部１６３は、受信したリンク情報のリンク利用率は、最下位のリンク利用率より高いかを判定する。
【０１０５】
受信したリンク情報のリンク利用率が、最下位のリンク利用率より高い場合、ステップＳ１７においてＹＥＳであると判定され、処理はステップＳ１８に進む。
【０１０６】
即ち、この場合、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致し（ステップＳ１６の処理）、且つ、変化したリンク利用率が、ランク表の最下位のリンク利用率よりも高い。よって、この場合はケース１に該当する。
【０１０７】
ステップＳ１８において、構築部１６４は、ランク表再構築処理１を実行する。ランク表再構築処理１の詳細については、図１４を参照して後述するが、これによりランク表が再構築される。ランク表再構築処理１は、ランク表に登録されているリンク情報に対して、ランク表の順位を入れ替える処理である。
【０１０８】
それに対し、受信したリンク情報のリンク利用率が、最下位のリンク利用率より同じか低い場合、ステップＳ１７においてＮＯであると判定され、処理はステップＳ１９に進む。
【０１０９】
即ち、この場合、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致し（ステップＳ１６の処理）、且つ、変化したリンク利用率が、ランク表の最下位のリンク利用率と同じか低い。よって、この場合はケース２に該当する。
【０１１０】
ステップＳ１９において、構築部１６４は、ランク表再構築処理２を実行する。ランク表再構築処理２の詳細については、図１７を参照して後述するが、これによりランク表が再構築される。ランク表再構築処理２は、ランク表に登録されていたリンクIDのリンク利用率が変化することにより、登録されていたリンク情報がランク外になって削除される処理である。また、ランク表再構築処理２は、順次リンク情報が削除されてランク数がゼロになった場合に、初期化処理を実行する処理である。
【０１１１】
ステップＳ１６の処理においてＮＯであると判定された場合、即ち、受信したリンク情報のリンクIDが、ランク表に登録されていない場合、処理はステップＳ２０に進む。
【０１１２】
即ち、受信したリンク情報のリンクIDが、ランク表に登録されていないので、ケース３に該当すると判断される。
【０１１３】
ステップＳ２０において、主に構築部１６４は、ランク表再構築処理３を実行する。ランク表再構築処理３の詳細については、図２５を参照して後述するが、これによりランク表が再構築される。ランク表再構築処理３は、ランク表に新たなリンク情報が登録され、ランク外となったリンク情報が削除される処理である。
【０１１４】
このようにして、ステップＳ１８，Ｓ１９，およびＳ２０において、ランク表再構築処理１、ランク表再構築処理２、およびランク表再構築処理３がそれぞれ実行されると、処理はステップＳ１１に戻る。
【０１１５】
以上、説明したように、ノード１１２は、リンク利用率が変化した場合、図１２のステップＳ１１乃至Ｓ１４の処理により広告処理を行い、他のノード１１２から広告されたリンク利用率を受信した場合には、ランク表を再構築する処理を実行する。
【０１１６】
図１４は、ランク表再構成処理１について説明するフローチャートである。ランク表再構築処理１は、図１２のフローチャートのステップＳ１８の処理である。また、ランク表再構築処理１は、図１１を参照して説明したケース１の場合に、構築部１６４がランク表を再構築する処理である。
【０１１７】
ステップＳ３１において、構築部１６４は、リンク情報を更新する。即ち、リンク利用率が新しい値に書き換えられる。その後、処理はステップＳ３２に進む。
【０１１８】
ステップＳ３２において、構築部１６４は、ランク表を再構築する。即ち、順位が書き換えられ、処理は図１２のフローチャートのステップＳ１１に戻る。
【０１１９】
構築部１６４がランク表再構築処理１を実行し、ランク表を再構築する場合の具体的な例について、図１５を参照して説明する。
【０１２０】
図１５は、ネットワーク１０１のリンク利用率を示す図である。図１５は、図６を参照して説明した初期状態から、リンクID（１１２−２，１１２−１）のリンク利用率が、０．９８から０．８４に変化した状態を表している。
【０１２１】
図１０に示された、初期化処理時に構築されたランク表によると、ランク１位のリンクID（１１２−２，１１２−１）と、変化したリンク利用率のリンクID（１１２−２，１１２−１）は、一致している。さらに、変化したリンク利用率０．８４は、ランク表の最下位のリンク利用率０．８２より高い。よって、この場合はケース１に該当すると判定され、ランク表再構築処理１が実行される。
【０１２２】
図１６は、ランク表の例を示す図である。図１６は、図１５を参照して説明したリンク利用率の変化に伴い、ランク表再構築処理１の処理によって、図１０に示されるランク表が再構築されたランク表を表している。
【０１２３】
図１０においてランク１位であったリンクID（１１２−２，１１２−１）のリンク利用率が０．９８から０．８４に変化したことにより、リンク情報が更新される。即ち、リンク利用率の値が０．９８から０．８４に変更される。そして、ランク２位であったリンクID（１１２−３，１１２−２）のリンク利用率０．８６がランク１位となり、リンクID（１１２−２，１１２−１）のリンク利用率０．８４がランク２位となる。ランク３位であったリンクID（１１２−１，１１２−２）のリンク利用率０．８２は、ランク３位のまま変わらない。
【０１２４】
以上説明したように、構築部１６４は、ケース１の条件でリンク利用率が変化した場合、ランク表に登録されているリンク情報の順位を入れ替える。
【０１２５】
図１７は、ランク表再構成処理２について説明するフローチャートである。ランク表再構築処理２は、図１２のフローチャートのステップＳ１９の処理である。また、ランク表再構成処理２は、図１１を参照して説明したケース２の場合に、主に構築部１６４がランク表を再構築する処理である。
【０１２６】
ステップＳ４１において、構築部１６４は、対象となるリンク情報を削除する。即ち、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致し（ステップＳ１６の判定）、且つ、変化したリンク利用率が、ランク表の最下位のリンク利用率と同じか低い（ステップＳ１７の判定）ので、ランク表に登録されていたリンク情報が削除される。
【０１２７】
ステップＳ４２において、構築部１６４は、ランク表のランク数がゼロかを判定する。
【０１２８】
ランク表のランク数がゼロでない場合、ステップＳ４２においてＮＯであると判定され、処理はステップＳ４３に進む。
【０１２９】
ステップＳ４３において構築部１６４はランク表を再構築する。即ち、順位が書き換えられる。
【０１３０】
ここで、処理がステップＳ４１からステップＳ４２に進み、ステップＳ４２でＮＯと判定され、ステップＳ４３に進んだ場合の具体的な例について、図１８乃至図２１を参照して説明する。
【０１３１】
図１８は、ネットワーク１０１のリンク利用率を示す図である。図１８は、図６を参照して説明した初期状態から、リンクID（１１２−２，１１２−１）のリンク利用率が、０．９８から０．７０に変化した状態を表している。
【０１３２】
図１０の初期化処理時に構築されたランク表によると、ランク１位のリンクID（１１２−２，１１２−１）と、変化したリンク利用率のリンクID（１１２−２，１１２−１）は、一致している。しかし、変化したリンク利用率０．７０は、ランク表の最下位のリンク利用率０．８２より低い。よって、この場合はケース２に該当すると判定され、ランク表再構築処理２が実行される。
【０１３３】
図１９は、ランク表の例を示す図である。図１９は、図１８を参照して説明したリンク利用率の変化に伴い、ランク表再構築処理２の処理によって図１０に示されるランク表が再構築されたランク表を表している。
【０１３４】
図１９に示されるように、図１０のランク表においてランク１位のリンク情報は削除され、ランク表のランク数は２となる。
【０１３５】
即ち、図１０においてランク１位であったリンクID（１１２−２，１１２−１）のリンク利用率が０．９８から０．７０に変化し、このリンク利用率は最下位のリンク利用率である０．８２より小さいので、このリンクは管理対象とする必要がなくなったことになる。そこで、それまでランク１位であったリンクID（１１２−２，１１２−１）のリンク情報が削除され、それまでランク２位であったリンクID（１１２−３，１１２−２）のリンク利用率０．８６がランク１位となる。また、それまでランク３位であったリンクID（１１２−１，１１２−２）のリンク利用率０．８２は、ランク２位となる。
【０１３６】
図２０は、ネットワーク１０１のリンク利用率を示す図である。図２０は、図１８のネットワーク１０１において、さらにリンクID（１１２−３，１１２−２）のリンク利用率が、０．８６から０．７８に変化した状態を表している。
【０１３７】
この場合も、図１９に示されるランク表のランク１位のリンクID（１１２−３，１１２−２）と、変化したリンク利用率のリンクID（１１２−３，１１２−２）は、一致している。しかし、変化したリンク利用率０．７８は、ランク表の最下位のリンク利用０．８２より低い。よって、ケース２に該当すると判定され、ランク表再構築処理２が実行される。
【０１３８】
図２１は、ランク表の例を示す図である。図２１は、図２０を参照して説明したリンク利用率の変化に伴い、ランク表再構築処理２の処理によって、図１９に示されるランク表が再構築されたランク表を表している。
【０１３９】
図２１に示されるように、図１９に示されるランク表においてランク１位のリンク情報は削除され、ランク表のランク数は１となる。
【０１４０】
即ち、図１９においてランク１位であったリンクID（１１２−３，１１２−２）のリンク利用率が０．８６から０．７８に変化し、このリンク利用率は最下位のリンク利用率である０．８２より小さいので、このリンクは管理対象とする必要がなくなったことになる。そこで、それまでランク１位であったリンクID（１１２−３，１１２−２）のリンク情報が削除され、それまでランク２位であったリンクID（１１２−１，１１２−２）のリンク利用率０．８２がランク１位となる。
【０１４１】
このように、ケース２の条件が発生する度に、ランク表のランク数は減少していく。その結果、ケース２が３回発生すると、ついにはランク数がゼロになる。
【０１４２】
図１７のランク表再構築処理２のフローチャートの説明に戻る。ステップＳ４２において、ランク表のランク数がゼロである場合、ＹＥＳであると判定され、処理はステップＳ４４に進む。
【０１４３】
ステップＳ４４において、検出部１６１、受信部１６２、構築部１６４、および出力部１６５は、初期化処理を実行する。
【０１４４】
ここで、ステップＳ４２においてＹＥＳであると判定され、処理がステップ４４に進み、初期化処理が実行される場合の具体的な例について、図２２乃至図２４を参照して説明する。
【０１４５】
図２２は、ネットワーク１０１のリンク利用率を示す図である。図２２は、図２０のネットワーク１０１において、さらにリンクID（１１２−１，１１２−２）のリンク利用率が、０．８２から０．８０に変化した状態を表している。
【０１４６】
この場合も、図２１に示されるランク表のランク１位のリンクID（１１２−１，１１２−２）と、変化したリンク利用率のリンクID（１１２−１，１１２−２）は、一致している。そして、変化したリンク利用率０．８０は、ランク表の最下位のリンク利用０．８２より低い。よって、ケース２に該当すると判定され、ランク表再構築処理２が実行される。
【０１４７】
図２３は、ランク表の例を示す図である。図２３は、図２２を参照して説明したリンク利用率の変化に伴い、ランク表再構築処理２の処理によって、図２１に示されるランク表が再構築されたランク表を表している。
【０１４８】
図２３に示されるように、図２１のランク表においてランク１位のリンク情報は削除され、ランク表のランク数は０となる。
【０１４９】
即ち、図２１においてランク１位であったリンクID（１１２−１，１１２−２）のリンク利用率が０．８２から０．８０に変化し、このリンク利用率は最下位のリンク利用率である０．８２より小さいので、このリンクは管理対象とする必要がなくなったことになる。そこで、それまでランク１位であったリンクID（１１２−１，１１２−２）のリンク情報が削除される。
【０１５０】
このようにして、ランク表のランク数がゼロになったため、ランク表再構築処理２のステップＳ４２において、ＹＥＳであると判定される。
【０１５１】
そして、ランク表再構築処理２のステップＳ４４において初期化処理が実行される。初期化処理の内容は、図９を参照して説明したとおりである。
【０１５２】
図２４は、ランク表の例を示す図である。図２４は、構築部１６４によりランク表再構築処理２が最大ランク数と同じ数だけ繰り返された結果、ランク数がゼロとなり、初期化処理が実行された場合のランク表を表している。
【０１５３】
即ち、図２２のネットワーク１０１のリンク情報に基づき、リンクID（１１２−１，１１２−２）のリンク利用率０．８０がランク１位に、リンクID（１１２−３，１１２−２）のリンク利用率０．７８がランク２位に、リンクID（１１２−２，１１２−４）のリンク利用率０．７７がランク３位として、構築部１６４は、図２４に示されるランク表を再構築する。
【０１５４】
以上説明したように、構築部１６４は、ケース２の条件でリンク利用率の変化した場合、ランク外になったリンク情報を削除する。また、構築部１６４は、リンク情報が繰り返し削除され、ランク数がゼロになった場合、初期化処理を実行し、新たなランク表を構築する。
【０１５５】
図２５は、ランク表再構築処理３について説明するフローチャートである。ランク表再構築処理３は、図１２のフローチャートのステップＳ２０の処理である。また、ランク表再構築処理３は、図１１を参照して説明したケース３の場合に、構築部１６４がランク表を再構築する処理である。
【０１５６】
ステップＳ５１において、構築部１６４は、リンク情報を追加する。図１２を参照して説明したように、変化したリンク利用率のリンクIDと、ランク表のリンクIDが一致せず（ステップＳ１２でＮＯ）、且つ、変化したリンク情報のリンク利用率が、最下位のリンク利用率と同じか低い場合（ステップＳ１４でＮＯ）は、広告しないケース（ケース４）に該当する。このため、この場合はそもそも広告がなされない。つまり、受信したリンク情報のリンクIDと、ランク表のリンクIDが一致しない（ステップＳ１６の処理）としてランク表再構成処理３が実行される場合は、図１２のステップＳ１４でＹＥＳと判定された場合（受信したリンク利用率が、最下位のリンク利用率より高い場合）である。このため、ステップＳ５１において、受信した（広告された）リンク情報は、ランク表に追加される。
【０１５７】
ステップＳ５２において、構築部１６４は、ランク表を再構築する。即ち、ランク表の順位が調整される。
【０１５８】
ステップＳ５３において、構築部１６４は、ランク外となったリンク情報を削除して、ランク表を書き換える。
【０１５９】
図２６および２７を参照して、構築部１６４がランク表再構築処理３を実行し、ランク表を再構築する場合の具体的な例について説明する。
【０１６０】
図２６は、ネットワーク１０１のリンク利用率を示す図である。図２６は、図６を参照して説明した初期状態から、リンクID（１１２−４，１１２−２）のリンク利用率が、０．２２から０．８４に変化した状態を表している。
【０１６１】
図１０の初期化処理時に構築されたランク表によると、ランク１位のリンクID（１１２−２，１１２−１）、ランク２位のリンクID（１１２−３，１１２−２）およびランク３位のリンクID（１１２−１，１１２−２）と、変化したリンク利用率のリンクID（１１２−４，１１２−２）は、一致していない。さらに、変化したリンク利用率０．８４は、ランク表の最下位のリンク利用０．８２より高い。よって、この場合はケース３に該当すると判定され、ランク表再構築処理３が実行される。
【０１６２】
図２７は、ランク表の例を示す図である。図２７は、図２６を参照して説明したリンク利用率の変化に伴い、ランク表再構築処理３の処理によって、図１０に示されるランク表が再構築されたランク表を表している。
【０１６３】
図１０においてランク外であったリンクID（１１２−４，１１２−２）のリンク利用率が０．２２から０．８４に変化したことにより、リンク情報が追加される。即ち、リンクID（１１２−４，１１２−２）のリンク利用率０．８４がランク表に追加される。これにより、それまでランク１位であったリンクID（１１２−２，１１２−１）のリンク利用率０．９８と、それまでランク２位であったリンクID（１１２−３，１１２−２）のリンク利用率０．８６のランクはそのまま変化しない。そして、それまでランク外であったリンクID（１１２−４，１１２−２）のリンク利用率０．８４が追加されて、ランク３位となる。リンク情報追加前にはランク３位であったリンクID（１１２−１，１１２−２）のリンク利用率０．８２は、削除される。
【０１６４】
以上説明したように、構築部１６４は、ケース３の条件でリンク利用率が変化した場合、新たなリンク情報を追加登録し、ランク外になったリンク情報を削除する。
【０１６５】
図２８は、以上のようにしてネットワークを管理した場合におけるランク数の推移を示す図である。なお、図２８において、最大ランク数は３と定義されているとする。
【０１６６】
ノード１１２が初期化処理を実行した場合、ランク数は、最大ランク数である３である。
【０１６７】
初期化処理実行後、リンク利用率が変化して、ケース１と判定された場合、ランク数は３のまま変化しない。また、さらにリンク利用率が変化して、ケース３と判定された場合も、ランク数は３のまま変化しない。
【０１６８】
次に、リンク利用率が変化して、ケース２と判定された場合、ランク数はランク表再構築処理２の処理により、ランク数が１減少し、ランク数は２となる。また次にリンク利用率が変化して、ケース１と判定された場合、ランク数は２のまま変化しない。
【０１６９】
次にリンク利用率が変化して、ケース２と判定された場合、ランク数はさらに１減少し、ランク数は１となる。また次にリンク利用率が変化して、ケース２と判定された場合、ランク数はさらに１減少し、ランク数は０となる。そして、ランク表再構築処理２の処理により、初期化処理が実行され、ランク数は最大ランク数である３に戻る。
【０１７０】
次にリンク利用率が変化して、ケース３と判定された場合、ランク数は３のまま変化しない。また次にリンク利用率が変化して、ケース１と判定された場合、ランク数は３のまま変化しない。
【０１７１】
即ち、ランク表のランク数は、リンク利用率が変化しても、ケース１およびケース３の場合は、現状維持のまま推移する。それに対し、ケース２の条件でリンク利用率が変化した場合、ランク表のランク数は、１ずつ減少する。そしてランク表のランク数がゼロになると、初期化処理が実行されてランク数は最大ランク数に戻る。
【０１７２】
このように、本発明では、最大リンク利用率によりネットワークを管理するネットワーク制御方法において、所定のランク以内に入っているリンク利用率のみをコントローラ１１１およびノード１１２が保持する、LLR(link load ranking)法が用いられる。LLR法を適用した本発明によれば、リンク利用率が変化したときの広告されるリンク情報の数（以下、広告数と称する）を削減することができる。
【０１７３】
[コンピュータ・シミュレーションによる性能評価]
LLR法を適用した本発明による、広告数の削減の効果について、図２９乃至図３１を参照して説明する。
【０１７４】
図２９は、IPネットワークバックボーンの一例を示す図である。LLR法を適用した本発明の性能を評価するためのシミュレーションの対象として、図２９に示すIPネットワークバックボーンが適用された。
【０１７５】
ネットワーク２０１は、２４のノード（ノード１１２−１乃至１１２−２４）および４３の双方向リンクにより構成される。即ち、片方向のリンク数は、８６である。
【０１７６】
シミュレーションは、タイムスロット（単位時間）以内に、最も遠いノード１１２（例えばノード１１２−２４）からネットワーク制御装置（例えばノード１１２−１）にリンク情報が到達すると仮定して実施された。また、シミュレーションは、実施時間を１０００タイムスロット時間とし、リンク利用率が単位時間内に変化する確率Pを０．０５、０．２、および０．５として実施された。
【０１７７】
図３０は、最大ランク数と広告率の関係を示す図である。広告率とは、リンク利用率が変化する回数に対する、リンク情報が広告される回数の割合である。図３０は、図２９のネットワーク２０１におけるシミュレーションの結果得られた、最大ランク数と広告率の関係を表している。
【０１７８】
従来の技術では、リンク利用率が変化する度に、リンク情報が広告されるので、広告率は１．０である。
【０１７９】
図２９のネットワーク２０１のリンク数が８６であるので、広告率１．０というのは、LLR法においては最大ランク数８６に該当する。換言すると、従来の技術における広告の回数と、LLR法における最大ランク数８６の場合の広告の回数が一致し、広告率は１．０となる。
【０１８０】
よって、ネットワーク２０１の例においては、LLR法を適用すると、最大リンク数は、１から８５の範囲を取り得る。
【０１８１】
図３０の最大ランク数と広告率の関係を参照すると、以下のことが分かる。即ち、リンク利用率が単位時間内に変化する確率Pが０．０５および０．２の場合には、最大ランク数が１から４の範囲において、広告率は、最大ランク数の増加に伴い減少する。そして、広告率は、最大ランク数４で最小値を取った後、最大ランク数の増加に伴い増加する。
【０１８２】
また、リンク利用率が単位時間内に変化する確率Pが０．５の場合には、最大ランク数が１から６の範囲において、広告率は、最大ランク数の増加に伴い減少する。そして、広告率は、最大ランク数６で最小値を取った後、最大ランク数の増加に伴い増加する。
【０１８３】
最大ランク数が小さいと、リンク利用率が変化する回数に対してリンク情報が広告される回数は減少する。しかしながら、最大ランク数が小さすぎると、上述したケース２に該当する場合が増え、ランク数が１ずつ減少された結果、初期化処理が実行される回数が増える。このため、結果的に広告数が増大する場合がある。
【０１８４】
図３１は、最大ランク数とランク表リセット率の関係を示す図である。ランク表リセット率とは、全タイムスロット数に対するランク表が初期化処理される回数の割合である。
【０１８５】
リンク利用率が単位時間内に変化する確率Pが０．０５，０．２，０．５のいずれの場合においても、ランク表リセット率はランク数が１の時に最大となる。
【０１８６】
また、同一のランク数の場合には、リンク利用率が単位時間内に変化する確率Pが大きいほど、ランク表リセット率が大きくなる。これは、リンク利用率が単位時間内に変化する確率Pが大きいほど、リンク利用率が変化しやすく、ランク数が減少する確率が高くなるためである。
【０１８７】
このように、最大ランク数がある値以下であれば、初期化処理が実行される機会が増え、広告数が増加する。また、最大ランク数が大きすぎると、広告される対象のリンク数が増加するため、広告数が増大する。従って、広告率を最小化することのできる最適な最大ランク数が存在するのである。
【０１８８】
例えば、図３０に示された広告率と最大ランク数の関係においては、リンク利用率が単位時間内に変化する確率Pが０．０５および０．２の場合には、最適な最大ランク数は４である。また、リンク利用率が単位時間内に変化する確率Pが０．５の場合には、最適な最大ランク数は６である。
【０１８９】
[最適な最大ランク数]
広告を最小化する最大ランク数は、以下の式（１）で求められる。
【０１９０】
なお、式（１）において、各リンクのリンク利用率が単位時間内に変化する確率をP、ネットワーク１０１のリンク数をLとする。最大ランク数Rmaxの範囲は、１≦Rmax≦Lである。また、リンク利用率が変化する回数に対して、広告される回数の割合（広告率）をθ（P, Rmax）とする。式（１）の最適最大ランク数Rmaxoptは、θ（P, Rmax）を最小化する最適な最大ランク数Rmaxである。
【０１９１】
【数１】
【０１９２】
以上、図２９乃至図３１を参照して説明したシミュレーションの結果、LLR法を適用した本発明によれば、従来の技術に比べ、広告数を最大９２％削減することができた。
【０１９３】
換言すると、LLR法を適用した本発明によれば、リンク情報をリンク利用率によってランク付けし、所定のランク以内に入っているリンク情報のみを保持することにより、ネットワーク資源を有効に利用することができるようになる。
【０１９４】
［変形例等］
上述した一連の処理は、ハードウェアにより実行することもできるし、ソフトウェアにより実行することもできる。一連の処理をソフトウェアにより実行する場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、汎用のパーソナルコンピュータなどにインストールされる。
【０１９５】
インストールされるプログラムは、図７の磁気ディスク１５１、光ディスク１５２、光磁気ディスク１５３、或いは半導体メモリ１５４等に記録して提供される。また、ローカルエリアネットワーク、インターネット、デジタル放送といった、有線または無線の伝送媒体を介して提供されるようにしてもよい。プログラムは、ROM１３２や記憶部１３８に、あらかじめインストールしておくことができる。
【０１９６】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０１９７】
本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【符号の説明】
【０１９８】
１ ネットワーク， １１ コントローラ， １２ ノード， １０１ ネットワーク， １１１ コントローラ， １１２ ノード， １３１ CPU， １３２ ROM， １３３ RAM， １３４ バス， １３５ 入出力インタフェース， １３６ 操作部， １３７ インジケータ， １３８ 記憶部， １３９ LAN通信部， １４０ WAN通信部， １４１ ドライブ， １５１ 磁気ディスク， １５２ 光ディスク， １５３ 光磁気ディスク， １５４ 半導体メモリ， １６１ 検出部， １６２ 受信部， １６３ 判定部， １６４ 構築部， １６５ 出力部， ２０１ ネットワーク
【特許請求の範囲】
【請求項１】
ネットワークのリンクを、その利用率が高い順に順位付けて登録リンクとして登録したランク表であって、前記ネットワークの全リンク数より少ない数の、前記リンクを登録する最大の数である最大リンク数が予め定められている前記ランク表を構築し、前記利用率が変化した前記リンクである変化リンクが発生した場合、前記ランク表を再構築する構築部を備え、
前記構築部は、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、前記登録リンク数が前記最大リンク数の範囲内になるように前記ランク表を書き換え、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より低い値に変化した場合、前記変化リンクを前記登録リンクから削除して、前記ランク表を書き換える
情報処理装置。
【請求項２】
前記変化リンクを前記登録リンクから削除した結果、前記登録リンクの数がゼロになった場合、前記ネットワークのすべての前記リンクの利用率に基づいて前記ランク表を初期化する
請求項１に記載の情報処理装置。
【請求項３】
前記変化リンクが前記登録リンクである場合、並びに前記登録リンクでない前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、他の情報処理装置に前記変化リンクの前記リンク利用率およびリンク識別情報を広告する
請求項２に記載の情報処理装置。
【請求項４】
前記最大リンク数は、１以上且つ前記ネットワークに存在するリンク数以下の範囲内で、変化リンクが発生する回数に対する広告される回数の割合を最小にする数である
請求項３に記載の情報処理装置。
【請求項５】
情報処理装置の情報処理方法であって、
ネットワークのリンクを、その利用率が高い順に順位付けて登録リンクとして登録したランク表であって、前記ネットワークの全リンク数より少ない数の、前記リンクを登録する最大の数である最大リンク数が予め定められている前記ランク表を構築し、前記利用率が変化した前記リンクである変化リンクが発生した場合、前記ランク表を再構築する構築部を備え、
前記構築部が、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、前記登録リンク数が前記最大リンク数の範囲内になるように前記ランク表を書き換え、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より低い値に変化した場合、前記変化リンクを前記登録リンクから削除して、前記ランク表を書き換える
ステップを含む情報処理方法。
【請求項６】
情報処理用のプログラムであって、
コンピュータに、
ネットワークのリンクを、その利用率が高い順に順位付けて登録リンクとして登録したランク表であって、前記ネットワークの全リンク数より少ない数の、前記リンクを登録する最大の数である最大リンク数が予め定められている前記ランク表を構築し、前記利用率が変化した前記リンクである変化リンクが発生した場合、前記ランク表を再構築する構築部
として機能させるためのプログラムであって、
前記構築部が、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、前記登録リンク数が前記最大リンク数の範囲内になるように前記ランク表を書き換え、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より低い値に変化した場合、前記変化リンクを前記登録リンクから削除して、前記ランク表を書き換える
処理を実行させるプログラム。
【請求項１】
ネットワークのリンクを、その利用率が高い順に順位付けて登録リンクとして登録したランク表であって、前記ネットワークの全リンク数より少ない数の、前記リンクを登録する最大の数である最大リンク数が予め定められている前記ランク表を構築し、前記利用率が変化した前記リンクである変化リンクが発生した場合、前記ランク表を再構築する構築部を備え、
前記構築部は、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、前記登録リンク数が前記最大リンク数の範囲内になるように前記ランク表を書き換え、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より低い値に変化した場合、前記変化リンクを前記登録リンクから削除して、前記ランク表を書き換える
情報処理装置。
【請求項２】
前記変化リンクを前記登録リンクから削除した結果、前記登録リンクの数がゼロになった場合、前記ネットワークのすべての前記リンクの利用率に基づいて前記ランク表を初期化する
請求項１に記載の情報処理装置。
【請求項３】
前記変化リンクが前記登録リンクである場合、並びに前記登録リンクでない前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、他の情報処理装置に前記変化リンクの前記リンク利用率およびリンク識別情報を広告する
請求項２に記載の情報処理装置。
【請求項４】
前記最大リンク数は、１以上且つ前記ネットワークに存在するリンク数以下の範囲内で、変化リンクが発生する回数に対する広告される回数の割合を最小にする数である
請求項３に記載の情報処理装置。
【請求項５】
情報処理装置の情報処理方法であって、
ネットワークのリンクを、その利用率が高い順に順位付けて登録リンクとして登録したランク表であって、前記ネットワークの全リンク数より少ない数の、前記リンクを登録する最大の数である最大リンク数が予め定められている前記ランク表を構築し、前記利用率が変化した前記リンクである変化リンクが発生した場合、前記ランク表を再構築する構築部を備え、
前記構築部が、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、前記登録リンク数が前記最大リンク数の範囲内になるように前記ランク表を書き換え、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より低い値に変化した場合、前記変化リンクを前記登録リンクから削除して、前記ランク表を書き換える
ステップを含む情報処理方法。
【請求項６】
情報処理用のプログラムであって、
コンピュータに、
ネットワークのリンクを、その利用率が高い順に順位付けて登録リンクとして登録したランク表であって、前記ネットワークの全リンク数より少ない数の、前記リンクを登録する最大の数である最大リンク数が予め定められている前記ランク表を構築し、前記利用率が変化した前記リンクである変化リンクが発生した場合、前記ランク表を再構築する構築部
として機能させるためのプログラムであって、
前記構築部が、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より高い値に変化した場合、前記登録リンク数が前記最大リンク数の範囲内になるように前記ランク表を書き換え、
前記変化リンクの前記利用率が、前記ランク表に登録されている最下位の前記利用率より低い値に変化した場合、前記変化リンクを前記登録リンクから削除して、前記ランク表を書き換える
処理を実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【公開番号】特開２０１２−２５７０９２（Ｐ２０１２−２５７０９２Ａ）
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願番号】特願２０１１−１２９２１０（Ｐ２０１１−１２９２１０）
【出願日】平成２３年６月９日（２０１１．６．９）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、総務省「管理型自己組織化技術に基づく多様なサービスを収容する光ネットワーク制御技術の研究開発」産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０４１３３１１０）国立大学法人電気通信大学 (383)
【Ｆターム（参考）】
【公開日】平成２４年１２月２７日（２０１２．１２．２７）
【国際特許分類】
【出願日】平成２３年６月９日（２０１１．６．９）
【国等の委託研究の成果に係る記載事項】（出願人による申告）平成２２年度、総務省「管理型自己組織化技術に基づく多様なサービスを収容する光ネットワーク制御技術の研究開発」産業技術力強化法第１９条の適用を受ける特許出願
【出願人】（５０４１３３１１０）国立大学法人電気通信大学 (383)
【Ｆターム（参考）】
[ Back to top ]