(57)【特許請求の範囲】
【請求項１】
通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードに設けられ，前記通信路のトラフィックに関する情報を収集するトラフィック情報収集装置であって，
自己のノードに接続された通信路のトラフィックに関する情報を収集するトラフィック情報収集部と，
前記通信ネットワーク上の通信プロトコルで使用されるメッセージにより，前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報を他のノードに送信するトラフィック情報送信部と，
他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報を受信するトラフィック情報受信部と，
前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，前記トラフィック情報受信部により受信された前記他のノードに接続された通信路のトラフィックに関する情報とを記憶するトラフィック情報記憶部とを備え，
前記トラフィック情報送信部は，前記他のノードに接続された通信路のトラフィックに関する情報が該他のノードから送信されてきた時に，該他のノードに接続された通信路のトラフィックに関する情報を他のノードに送信するとともに前記自己のノードに接続された通信路のトラフィックに関する情報を送信することを特徴とするトラフィック情報収集装置。
【請求項２】
通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードに設けられ，前記通信路のトラフィック情報を収集するトラフィック情報収集装置であって，
自己のノードに接続された通信路のトラフィックに関する情報を収集するトラフィック情報収集部と，
前記通信ネットワーク上の通信プロトコルで使用されるメッセージにより，前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報を他のノードに送信するトラフィック情報送信部と，
他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報を受信するトラフィック情報受信部と，
前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，前記トラフィック情報受信部により受信された前記他のノードに接続された通信路のトラフィックに関する情報とを記憶するトラフィック情報記憶部とを備え，
前記トラフィック情報送信部は，あらかじめ定められた一定時間間隔ごとに前記自己のノードに接続された通信路のトラフィックに関する情報を送信するとともに，前記他のノードに接続された通信路のトラフィックに関する情報が該他のノードから送信されてきた時に，該他のノードに接続された通信路のトラフィックに関する情報を他のノードに送信するとともに前記自己のノードに接続された通信路のトラフィックに関する情報を送信することを特徴とするトラフィック情報収集装置。
【請求項３】
請求項１または２において，
前記トラフィック情報送信部は，前記他のノードから送信されてきたトラフィックに関する情報を，送信されてきた通信路を除く他の通信路に転送することを特徴とするトラフィック情報収集装置。
【請求項４】
通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードが，前記通信路のトラフィック情報を収集するトラフィック情報収集方法であって，前記ノードが，
自己のノードに接続された通信路のトラフィックに関する情報を収集する工程と，
他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報を受信する工程と，
前記収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，前記受信された前記他のノードに接続された通信路のトラフィックに関する情報とを記憶する工程と，
前記通信ネットワーク上の通信プロトコルで使用されるメッセージにより，前記収集された前記自己のノードに接続された通信路のトラフィックに関する情報を他のノードに送信するトラフィック情報送信工程とを実行し，
前記トラフィック情報送信工程では，前記ノードが，前記他のノードに接続された通信路のトラフィックに関する情報が該他のノードから送信されてきた時に，該他のノードに接続された通信路のトラフィックに関する情報を他のノードに送信するとともに前記自己のノードに接続された通信路のトラフィックに関する情報を送信することを特徴とするトラフィック情報収集方法。
【請求項５】
通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードに，前記通信路のトラフィック情報を収集させるトラフィック情報収集プログラムを記憶した記憶媒体であって，前記ノードを，
自己のノードに接続された通信路のトラフィックに関する情報を収集する手段と，
他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報を受信する手段と，
前記収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，前記受信された前記他のノードに接続された通信路のトラフィックに関する情報とを記憶する手段と，
前記通信ネットワーク上の通信プロトコルで使用されるメッセージにより，前記収集された前記自己のノードに接続された通信路のトラフィックに関する情報を他のノードに送信するトラフィック情報送信手段として機能させ，
前記トラフィック情報送信手段は，前記他のノードに接続された通信路のトラフィックに関する情報が該他のノードから送信されてきた時に，該他のノードに接続された通信路のトラフィックに関する情報を他のノードに送信するとともに前記自己のノードに接続された通信路のトラフィックに関する情報を送信することを特徴とするトラフィック情報収集プログラムを記憶した記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，通信ネットワークにおけるトラフィック情報収集装置，トラフィック情報収集方法，およびトラフィック情報収集プログラムに関し，特に，通信ネットワークにおいて，負荷分散を行うために必要な情報を収集するためのトラフィック情報収集装置，トラフィック情報収集方法，およびトラフィック情報収集プログラムに関する。
【０００２】
また，本発明は，通信ネットワークにおいて，負荷分散を行うために必要な情報を収集する機能を有する，通信ネットワークにおけるノードに関する。
【０００３】
【従来の技術】
インターネットは，コネクションを確立しないコネクションレスなネットワークであり，通信データは，ＩＰ（Internet Protocol）アドレスが付与されたＩＰパケットに分割され送信される。ＩＰパケットは，ＩＰアドレスに基づいてルータ間を中継され，宛先ルータまたはコンピュータ（以下，単に「宛先」という。）に届けられる。
【０００４】
ＩＰアドレスに基づいてルータ間をどのように中継して，ＩＰパケットを宛先まで届けるかは，ルーティング・プロトコルによって決定される。ルーティング・プロトコルとして，現在，ＲＩＰ（Routing Information Protocol）またはＯＳＰＦ（Open Shortest Path First）が一般に使用されている。これらのルーティング・プロトコルは，基本的には，通信ネットワーク内の各リンクのコスト（たとえばホップ数）に基づいて宛先までの最短の経路（ルート，パス）を求め，その最短経路をＩＰパケットの通信経路として設定するものである。
【０００５】
【発明が解決しようとする課題】
しかし，これらのルーティング・プロトコルでは，コストに基づく最短経路が求められるだけであって，各リンクのトラフィックの状況を考慮した経路は求められない。しかも，経路が新たに設定されるのは，通信ネットワークのトポロジーに変化が生じた場合だけであり，リアルタイムに設定／変更が行われるわけではない。一方，インターネットの普及により，インターネット内を行き交うパケットの量（すなわちトラフィック量または負荷）は急激に増加している。
【０００６】
その結果，ルーティング・プロトコルにより設定された経路上で，輻輳が発生するようになっている。
【０００７】
なるほど，ＯＳＰＦには，複数の経路を設定してＩＰパケットを分散する等コスト・マルチパス（Equal Cost Multipath）というルーティングもある。しかし，このルーティングは，コストが等しい経路が複数存在する場合に限られており，また，ＯＳＰＦを使用しているため，リアルタイムの通信ネットワークの負荷の変動に対処できない。
【０００８】
そこで，現在，インターネットにおける輻輳を回避する技術体系として，トラフィック・エンジニアリングが検討されている。このトラフィック・エンジニアリングは，一般に，宛先までの経路を複数設定するとともに，各経路のトラフィックの状況をリアルタイムに監視して，空きのある経路や負荷の小さな経路を選択してＩＰパケットを送信し，複数の経路間で負荷（トラフィック）の分散を行うものである。
【０００９】
一方，このようなトラフィック・エンジニアリングを行うためには，各ルータが，各経路の使用状況を含む，トラフィックに関する情報を知る必要がある。
【００１０】
本発明は，このような状況に鑑みなされたものであり，トラフィックの状況に応じて負荷分散を図ることができるように，通信ネットワーク上のノードがトラフィックに関する情報を収集できるようにすることにある。
【００１１】
【課題を解決するための手段】
前記目的を達成するために，本発明に係る情報収集装置は，通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードに設けられ，前記通信路のトラフィックに関する情報を収集するトラフィック情報収集装置であって，自己のノードに接続された通信路のトラフィックに関する情報を収集するトラフィック情報収集部と，前記通信ネットワーク上の通信プロトコルで使用されるメッセージにより，前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報を他のノードに送信するトラフィック情報送信部と，他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報を受信するトラフィック情報受信部と，前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，前記トラフィック情報受信部により受信された前記他のノードに接続された通信路のトラフィックに関する情報とを記憶するトラフィック情報記憶部と，を備えている。
【００１２】
また，本発明に係る情報収集装置は，通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードに設けられ，前記通信路のトラフィック情報を収集するトラフィック情報収集装置であって，自己のノードに接続された通信路のトラフィックに関する情報を収集するトラフィック情報収集部と，前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報とを記憶するトラフィック情報記憶部と，を備えている。
【００１３】
本発明に係る情報収集装置によると，通信ネットワークにおけるノードは，自己のノードに接続された通信路のトラフィックに関する情報を収集するとともに，他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報を受信し，これらの情報を記憶する。したがって，ノードは，記憶されたこれらの情報に基づいて，通信ネットワーク上の各通信路のトラフィックの状況を知ることができ，その結果，トラフィックの状況に応じた負荷分散制御を行うことが可能となる。
【００１４】
好ましくは，前記他のノードから送信されてきたトラフィックに関する情報を，送信されてきた通信路を除く他の通信路に転送するトラフィック情報転送部が，さらに備えられる。
【００１５】
これにより，あるノードに送信されてきた，他のノードのトラフィックに関する情報を，それ以外の他のノードにも伝達することができ，伝達された他のノードも，トラフィックに関する情報を入手することができる。その結果，通信ネットワーク上のすべてのノードが，該通信ネットワークの各通信路のトラフィックの状況を把握することができる。
【００１６】
【発明の実施の形態】
＜通信ネットワーク１の構成＞
図１は，本発明に係る「情報収集装置」を含んだノードを有する通信ネットワーク１の概略構成を示すブロック図である。この通信ネットワーク１は，本実施の形態ではインターネットの一部を形成するとともに，トラフィック・エンジニアリング（以下「ＴＥ」という。）による負荷分散が行われる通信ネットワークである。また，この通信ネットワーク１は，本実施の形態では，非同期転送モード（Asynchronous Transfer Mode：以下「ＡＴＭ」という。）により，ＩＰパケット（以下，単に「パケット」という。）を送受信する通信ネットワークである。
【００１７】
通信ネットワーク１には，外部の通信ネットワークとして，通信ネットワーク１にパケットを送信する送信側通信ネットワークＡ，ＢおよびＣと，通信ネットワーク１から送信されるパケットを受信する受信側通信ネットワークＤおよびＥとが接続されている。
【００１８】
これら外部の通信ネットワークを「送信側通信ネットワーク」と「受信側通信ネットワーク」とに分けたのは，ＴＥを説明するための便宜上のためであり，送信側通信ネットワークはパケットの送信のみを行うとは限らず，また，受信側通信ネットワークはパケットの受信のみを行うとは限らない。たとえば，通信ネットワーク１から送信側通信ネットワークＡ，ＢおおびＣにパケットが送信される場合もあるし，また，受信側通信ネットワークＤおよびＥから通信ネットワーク１にパケットが送信される場合もある。
【００１９】
これらの送信側通信ネットワークＡ，ＢおよびＣ，ならびに受信側通信ネットワークＤおよびＥは，インターネットの一部を形成し，本実施の形態では，イーサネットで構築されている。
【００２０】
通信ネットワーク１は，「ノード」の一例としてのルータ（後述するラベル・スイッチ・ルータ）を複数備えている。これらのルータには，入側ルータ１１Sと，出側ルータ１１Ｄと，複数の中継ルータ１１Ｒとが含まれている。
【００２１】
入側ルータ１１Ｓは，送信側通信ネットワークＡ，ＢまたはＣ（または入側ルータ１１に接続された図示しないコンピュータ端末）からパケットを受信すると，そのパケットに対してＴＥを実行し，ＴＥに基づいて設定された経路（パス，ルート）上の隣接した中継ルータ１１Ｒに送信するものである。中継ルータ１１Ｒは，入側ルータ１１Ｓと出側ルータ１１Ｄとの間に配置され，入側ルータ１１Ｓからのパケットを中継して出側ルータ１１Ｄに渡すものである。出側ルータ１１Ｄは，入側ルータ１１Ｓから中継ルータ１１Ｒを介して送信されてきたパケットを受信側通信ネットワークＤまたはＥ（または出側ルータ１１Ｄに接続された図示しないコンピュータ端末）に送信するものである。
【００２２】
なお，ここでも，ルータを入側ルータ１１Ｓと，出側ルータ１１Ｄと，中継ルータ１１Ｒとに分けたのはＴＥを説明するための便宜上のためであり，たとえば，入側ルータ１１Ｓが出側ルータとなる場合もあるし，出側ルータ１１Ｄが入側ルータとなる場合もある。また，以下では，これらの入側ルータ１１Ｓ，出側ルータ１１Ｄ，および中継ルータ１１Ｒを区別しない場合には，単に「ルータ１１」と総称することとする。
【００２３】
ルータ１１間には，各ルータを接続する物理的な「通信路」（ないしは「伝送路」）としてのリンクが設けられている。たとえば，入側ルータ１１Ｓには，隣接する３つの中継ルータ１１Ｒとの間に，３つのリンクＬ１〜Ｌ３がそれぞれ接続されている。
【００２４】
このように，入側ルータ１１Ｓは，外部の送信側通信ネットワークＡ，ＢおよびＣ（ならびに入側ルータ１１Ｓに接続されたコンピュータ端末）から送信されてきたパケットに対してＴＥを実行する始点となり，出側ルータ１１Ｄは，ＴＥの終点となる。したがって，入側ルータ１１Ｓから出側ルータ１１Ｄまでの区間は，「ＴＥ区間」と呼ばれることがある。
【００２５】
通信ネットワーク１は，本実施の形態では，ラベル・スイッチ技術の一例としてのＭＰＬＳ（Multi-Protocol Label Switching）を用いて経路を設定するように構成されている。このため，入側ルータ１１Ｓ，出側ルータ１１Ｄ，および中継ルータ１１Ｒは，ラベル・スイッチ・ルータ（Label Switch Router：以下「ＬＳＲ」という。）として構成されている。
【００２６】
ＭＰＬＳは，ＯＳＩ参照モデルにおけるレイヤ３のインターネット・プロトコルのルーティング処理と，ＡＴＭやフレーム・リレー等のレイヤ２のスイッチング処理とを融合させる技術である。ＬＳＲは，パケット転送（パケット交換）情報として，ＩＰアドレスよりも下位のレイヤの情報である「ラベル」を使用する。ＡＴＭスイッチをＬＳＲのパケット転送エンジン（ラベル・スイッチ・エンジン）に使用する場合には，ラベルとしてＶＰＩ／ＶＣＩ（Virtual Path Identifier／Virtual Connection Identifier）が使用される。すなわち，ＩＰアドレスがラベル（ＶＰＩ／ＶＣＩ）にマッピングされ，ラベルを用いてパケット転送が行われる。
【００２７】
ＭＰＬＳでは，ＬＳＰ（Label Switched Path）と呼ばれるあらかじめ設定された経路（仮想コネクション）上でパケットを転送する。このＬＳＰは，ＯＳＰＦのような既存のルーティング・プロトコルにより定められた経路に沿って設定することもできるし，既存のルーティング・プロトコルによる経路とは独立に設定することもできる。また，宛先（ルータまたはコンピュータ端末）まで，複数のＬＳＰを設定することもできる。
【００２８】
したがって，複数のＬＳＰを既存のルーティング・プロトコルとは独立に設定し，これらのＬＳＰ間で負荷（トラフィック）の分散を行うことにより，ＴＥが可能となる。
【００２９】
また，ＭＰＬＳでは，最初から複数のＬＳＰを設定しておくのではなく，通信ネットワーク１内のトラフィック量の状態を随時監視しておき，ある経路のトラフィック量が多くなった場合に，同じ宛先に向かう別の経路を検索して新たなＬＳＰを設定し，このＬＳＰにトラフィックを分散する制御も可能である。これによっても，通信ネットワークのトラフィックの状態に応じたダイナミックなＴＥが可能となる。
【００３０】
ＬＳＰは，１本のリンク内に複数個設定することができる。たとえば，１００［Ｍｂｐｓ（Ｍビット／秒）］の帯域を有する１本のリンク内には，それぞれ２０［Ｍｂｐｓ］のＬＳＰを５個設定することができる。
【００３１】
ＬＳＰの設定には，たとえば，ＲＳＶＰ（Resource Reservation Protocol）またはこれを拡張したＲＳＶＰ−ｔｕｎｎｅｌを用いて，経路上のリンクの帯域を予約することにより行うことができる。
【００３２】
通信ネットワーク１では，このＬＳＰによる経路（ラベル・スイッチ・パス，ＡＴＭにおける仮想コネクション）として，図１に示すように，３つの経路２１〜２３があらかじめ設定され，または，動的に生成されるものとする。すなわち，入側ルータ１１Ｓは，パケットを送信するための３つの経路２１〜２３を有する。
【００３３】
各経路２１〜２３は，１または２以上のリンク内に設けられたＬＳＰから構成される。また，各経路２１〜２３を構成するリンクは，すべて異なるリンクとは限らず，その一部または全部は同一リンク内に設けられた，異なるＬＳＰにより構成される場合もある。
【００３４】
入側ルータ１１Ｓは，ＴＥ区間外にある送信側通信ネットワークＡ，ＢおよびＣとの境界に位置し，これらの送信側通信ネットワークＡ，ＢまたはＣから送信されてきたパケットにラベルを付加し，中継ルータ１１Ｒに送信する。中継ルータ１１Ｒは，ラベルが付加されたパケットをラベル交換して，出側ルータ１１Ｄに向けて転送する。したがって，中継ルータ１１Ｒは，パケットのＩＰアドレスのルーティング・エントリを検索することなく，ラベル情報だけでパケットの転送（ラベル・スイッチ転送）を行うことができる。出側ルータ１１Ｄは，ＴＥ区間外にある受信側通信ネットワークＤおよびＥとの境界に位置し，送信されてきたパケットからラベルを取り除き，受信側通信ネットワークＤまたはＥ（または出側ルータ１１Ｄのコンピュータ端末）にこのパケットを送信する。なお，通信ネットワーク１は，前述したように，ＡＴＭを採用しているので，ここでいうラベルはＶＰＩ／ＶＣＩとなり，またパケットはＡＴＭセルとして転送されることとなる。
【００３５】
通信ネットワーク１のトラフィックの状態に応じて，ＬＳＰによる経路を設定し，トラフィックの負荷分散を行うために，各ルータ１１は，自己に接続されている各リンクおよび各リンク内の各ＬＳＰのトラフィックに関する情報（以下「トラフィックに関する情報」を単に「トラフィック情報」という。）を交換する。このトラフィック情報の交換には，本実施の形態では，ＯＳＰＦ（Open Shortest Path First）における特殊なＬＳＡ（リンク状態広告：Link State Advertisement）であるオペークＬＳＡ（Opaque Link State Advertisement）が使用される。
【００３６】
オペークＬＳＡは，その中に含むことができる情報については，後述するＬＳＡヘッダおよびＬＳＲインタフェース情報を除いて特に規定がなく，自由に使用できる領域を有する。また，オペークＬＳＡは，その伝播（送信）手法としてフラッディング（Flooding）が使用される点を除いて，いつ伝播するかについても規定がなく，各ルータが所望の時に伝播することができる。しかも，オペークＬＳＡは，ＯＳＰＦというプロトコルに従っているので，インターネット等の通信ネットワークにおいて使用することができる。したがって，自由に使用できる領域にトラフィック情報を含めて伝播することにより，インターネット等の既存の通信ネットワーク上の各ルータ間でトラフィック情報を交換することができる。
【００３７】
＜ルータ１１の構成＞
図２は，ルータ１１を代表して，入側ルータ１１Ｓの構成を示すブロック図である。入側ルータ１１Ｓは，処理装置３０と，記憶装置３２と，インタフェース装置４１〜４６とを備えている。また，入側ルータ１１Ｓにコンピュータ端末が接続されている場合には，このコンピュータ端末用のインタフェース装置４７が設けられる。なお，中継ルータ１１Ｒおよび出側ルータ１１Ｄは，インタフェース装置の個数が異なる場合があることと，その接続先が異なる場合があることとを除いて，入側ルータ１１Ｓと同様の構成を有するので，ここでは，入側ルータ１１Ｓの構成についてのみ説明することとする。
【００３８】
記憶装置３２は，ハードディスク装置等で構成され，リンク状態データベース３２ａおよびオペークＬＳＡ用データベース３２ｂを含んでいる。リンク状態データベース３２ａは，ＯＳＰＦで規定されている，リンク状態が格納されるデータベースである。オペークＬＳＡ用データベース３２ｂは，オペークＬＳＡが格納されるデータベースであり，その詳細な説明は後述する。
【００３９】
処理装置３０は，図示しないＣＰＵ，メモリ（ＲＡＭおよびＲＯＭ）等を備えている。この処理装置３０は，その内部のメモリまたは記憶装置３２に記憶されたプログラムに従って，記憶装置３２およびインタフェース装置４１〜４６（４７）の制御を行うとともに，経路の設定，トラフィックの状態に応じた負荷分散制御，パケット（ＡＴＭセル）の送受信，オペークＬＳＡの作成および送受信，受信したＬＳＡによるリンク状態データベースの更新，受信したオペークＬＳＡによるオペークＬＳＡ用データベースの更新等の処理を行う。
【００４０】
インタフェース装置４１〜４６（４７）は，入出力バッファを備え，処理装置３０の制御の下，接続された各リンクを転送されるパケット（ＡＴＭセル）の入出力処理を行う。
【００４１】
なお，パケット（ＡＴＭセル）の送受信（ＡＴＭセルの生成，ラベル（ＶＰＩ／ＶＣＩ）のスイッチングを含む。）は，ハードウェア回路により構成されたハードウェア交換機をルータ１１Ｓ内に設けて，この交換機により行うことができる。
【００４２】
＜オペークＬＳＡのデータ構造＞
トラフィック情報は，前述したように，ＯＳＰＦにおけるオペークＬＳＡを用いてルータ１１間をフラッディングされる。このオペークＬＳＡは，図３に示すデータ構造を有する。図中，最上部に示す数字はビット番号である。したがって，この図３では，オペークＬＳＡを横方向に３２ビット（４バイト）単位で整列して示している。
【００４３】
オペークＬＳＡは，ＬＳＡヘッダおよびＬＳＲインタフェース情報のフィールドを除いては，特に規定がなく，自由に使用できるフィールド（図３のリンク情報のフィールド）を有する。したがって，本実施の形態では，図３に示すデータ構造により，トラフィック情報がルータ１１間をフラッディングされる。
【００４４】
オペークＬＳＡは，大きく分けると，ＬＳＡヘッダとオペーク・フィールドとに分けられる。
【００４５】
ＬＳＡヘッダは，２０バイトからなり，通常のＬＳＡ（オペークＬＳＡ以外のＬＳＡ）と同様のデータ構造を有する。すなわち，ＬＳＡヘッダは，リンク状態エージ（Link State Age），オプション（Option），リンク状態タイプ（Link State Type：ＬＳ Type），オペーク・タイプ（Opaque Type），オペーク識別子（Opaque Id），広告ルータ（Advertising Router），リンク状態番号（LS Sequence Number），リンク状態チェック・サム（LS Checksum），および長さ（Length）の各フィールドから構成されている。
【００４６】
「リンク状態エージ」は，２バイトからなり，このオペークＬＳＡの寿命（秒単位），すなわち有効期限を示している。
【００４７】
「オプション」は，１バイトからなり，ルータがオプション機能をサポートするように設定したり，そのサポート・レベル他のルータに伝えることを可能にするフィールドである。この「オプション」フィールドの第２ビットは，Ｏビットと呼ばれ，そのルータがオペークＬＳＡをサポートしている（Opaque-capable）かどうかを示している。
【００４８】
「リンク状態タイプ」は，１バイトからなり，ＬＳＡのタイプを示している。オペークＬＳＡの場合に，リンク状態タイプの値は，９，１０または１１となり，この値によってフラッディングされる範囲が異なる。
【００４９】
この値が９の場合には，そのオペークＬＳＡのフラッディング範囲（Flooding Scope）は“Link-local”であり，ローカル・ネットワーク内とされる。１０の場合には，フラッディング範囲は“Area-local”であり，そのオペークＬＳＡは，接続しているエリアのボーダ（境界）を超えてフラッディングされることはない。１１の場合には，フラッディング範囲は“Equivalent to AS-external LSA”であり，そのオペークＬＳＡは，ＡＳ（Autonomous System）全体に亘ってフラッディングされる。特に（１）すべての通過領域（Transit area）にフラッディングされ，（２）バックボーン（backbone）からスタブ領域（stub area）にフラッディングされず，（３）あるルータから，そのルータに接続されているスタブ領域に向けては生成されない。
【００５０】
「広告ルータ」は，４バイトとからなり，このオペークＬＳＡを作成し，広告したルータのＩＰアドレスが置かれるフィールドである。リンク状態番号およびリンク状態チェック・サムは，同一の広告ルータが作成した２以上のオペークＬＳＡがある場合に，いずれが最新（時間的に最も後）のものであるかを判定する際に用いられる。「長さ」は，２バイトからなり，このオペークＬＳＡの長さ（バイト数）を示している。
【００５１】
「オペーク・フィールド」は，ＬＳＲインタフェース情報と，そのルータ１１に接続されたリンクの個数分設けられたリンク情報とから構成されている。
【００５２】
ＬＳＲインタフェース情報は，４バイトからなり，上位２バイトのＥ＿Ｂフィールドと，下位２バイトのリンク・カウントのフィールドとから構成されている。「Ｅ＿Ｂフィールド」は，そのルータがエリア・ボーダ・ルータかＡＳバウンダリ・ルータかを示す。「リンク・カウント」は，そのルータに接続されているリンクの個数を示す。
【００５３】
「リンク情報」は，リンク識別子（Link Id），ネット・マスク，コネクション・タイプ，ＬＳＰカウント，およびリンク・データの各フィールドから構成されている。
【００５４】
「リンク識別子」は，４バイトからなり，そのリンクが接続されている隣接ルータまたはコンピュータ端末のＩＰアドレスを示す。「ネット・マスク」は，４バイトからなり，リンク識別子の（サブ）ネット・マスクを示す。「コネクション・タイプ」は，１バイトからなり，そのリンクの接続先がルータか，コンピュータ端末か等を示す。ＬＳＰカウントは，１バイトからなり，そのリンクに設けられたＬＳＰの個数を示す。この値は，通信時に設けられるＬＳＰの個数が変化することに伴い動的に変化する。
【００５５】
「リンク・データ」は，複数のデータから構成されている。図４は，リンク・データのデータ構造を示している。リンク・データは，そのリンクのリンク統計情報と，そのリンク上に形成された各ＬＳＰのＬＳＰ統計情報とを有する。これらのリンク統計情報およびＬＳＰ統計情報は，本発明に係る「トラフィックに関する情報（トラフィック情報）」の一例である。
【００５６】
「リンク統計情報」は，平均使用率（Ave Utilization）と，出力リンク廃棄パケット数（Loss）と，出力リンク帯域（Bwl）との各フィールドを有する。
【００５７】
「平均使用率」は，４バイトからなり，そのリンクの平均使用率を示す。この平均使用率は，以下の式により計算される。
【００５８】
Ave Utilization＝α×CUTY（ｎ）＋（１−α）×CUTY（ｎ−１）  …（１）
この式（１）は，移動平均（moving average）法による計算式である。ここで，αは平滑化（スムージング）係数である。CUTY（ｎ）は現在（すなわち時刻ｎ）のリンク使用率を，CUTY（ｎ−１）は１時刻前（すなわち時刻（ｎ−１））のリンク使用率を，それぞれ示し，以下の式により求められる。
【００５９】
CUTY（ｎ）＝〔時刻（ｎ−１）から時刻ｎまでのリンクへの出力パケット数〕／〔出力リンク帯域〕  …（２）
なお，平均使用率は，観測されたCUTYの最大値とすることもでき，この場合に，平均使用率は以下の式で表される。
【００６０】
Ave Utilization＝ｍａｘ（観測値）  …（３）
「出力リンク廃棄パケット数」は，４バイトからなり，そのリンクの廃棄された出力パケットの合計数を示す。出力リンク廃棄パケット数は，以下の式により計算される。
【００６１】
Loss（ｎ）＝Loss（ｎ−１）＋NLoss  …（４）
ここで，Loss（ｎ−１）は，１時刻前の時刻（ｎ−１）までの出力リンク廃棄パケットの合計数であり，NLossは，時刻（ｎ−１）から時刻ｎまでに生じた出力リンク廃棄パケット数である。
【００６２】
「出力リンク帯域」は，４バイトからなり，出力リンクの帯域［ｂｐｓ（ビット／秒）］を示す。この出力リンク帯域は，各ルータ１１の処理装置３０のメモリまたは記憶装置３２にあらかじめ記憶され，記憶された値がオペークＬＳＡの該フィールドに書き込まれるようになっている。
【００６３】
「ＬＳＰ統計情報」は，ＬＳＰ識別子（Lsp id）と，ＬＳＰ＿ＣＯＳクラス（Cos lsp）と，ＬＳＰ平均使用率（Ave Utility lsp）と，ＬＳＰ出力廃棄パケット数（Loss lsp）と，ＬＳＰ帯域（Bwl lsp）との各フィールドを有する。
【００６４】
「ＬＳＰ識別子」は，２バイトからなり，そのＬＳＰの識別子を示す。「ＬＳＰ＿ＣＯＳクラス」は，２バイトからなり，そのＬＳＰのＣＯＳクラスを示している。
【００６５】
「ＬＳＰ平均使用率」は，４バイトからなり，そのＬＳＰの平均使用率を示し，前記式（１）および（２）において，出力リンクを，リンクではなくＬＳＰに置換した式により求められる。また，前記式（３）と同様に，そのＬＳＰにおける観測値の最大値とすることもできる。
【００６６】
「ＬＳＰ出力廃棄パケット数」は，４バイトからなり，そのＬＳＰの廃棄された出力パケットの合計数を示し，前記式（４）において，出力リンクをＬＳＰに置換することにより求められる。
【００６７】
「ＬＳＰ帯域」は，そのＬＳＰが設定される際に割り当てられた帯域［ｂｐｓ］を示している。このＬＳＰ帯域は，ＬＳＰの設定時に，そのＬＳＰが設定されるリンクを出力リンクとするルータ１１の処理装置３０のメモリまたは記憶装置３２に記憶され，記憶された値がオペークＬＳＡの該フィールドに書き込まれるようになっている。
【００６８】
これまでに述べたリンク平均使用率，出力リンク廃棄パケット数，ＬＳＰ平均使用率，およびＬＳＰ出力廃棄パケット数は，たとえば，各ルータ１１のオペレーティング・システム（ＯＳ：たとえばＬｉｎｕｘ）がリアルタイムで収集し，管理しているシステム状態（ＣＰＵ負荷，転送パケット数等）を表すデータ（ファイル）に基づいて求められる。
【００６９】
図５および図６は，ルータ１１ＳのＯＳがリアルタイムで収集／管理しているシステム状態のデータの一例を示している。図５はルータ１１Ｓに設けられた記憶装置３２のディレクトリ“/proc/net/dev”にあるファイルの内容を，図６は記憶装置３２のディレクトリ“/proc/atm/device”にあるファイルの内容を，それぞれテーブル（表）形式により示している。
【００７０】
これらの図に示す数値は，ある時刻のデータの一例である。また，これらの数値は，ルータ１１Ｓに電源を投入してからの積算値を示し，ＯＳがリアルタイム（一定時間間隔Δｔ）で収集しているので，時々刻々と変化するものである。これらの数値は積算値であるので，たとえば時刻（ｎ−１）にこのテーブルを参照した時の値と時刻ｎにこのテーブルを参照した時の値との差分を求めることにより，時刻（ｎ−１）から時刻ｎまでの１時刻の間の変化量を求めることができる。
【００７１】
図５に示すテーブルの上半分は，“Receive”の文字が示すようにルータ１１Ｓの受信に関するデータを示し，下半分は，“Transmit”の文字が示すようにルータ１１Ｓの送信に関するデータを示す。以下，テーブルの上半分を「受信テーブル」といい，下半分を「送信テーブル」という。
【００７２】
受信テーブルおよび送信テーブルにおける“interface”は，ルータ１１Ｓに接続されているインタフェースの種類を示している。このインタフェースには，“lo”，“eth0”，“eth1”，“eth2”，“atm0”，“atm1”，および“atm2”がある。
【００７３】
“lo”は，“loopback device”の略であり，ルータ１１Ｓに接続されたコンピュータ端末（図1には図示略）とのインタフェースを意味する。“eth0”〜“eth2”は，イーサネットとのインタフェースを意味する。ルータ１１Ｓには，図１に示すように，送信側通信ネットワーク（イーサネット）Ａ〜Ｃが接続されているので，“eth0”は送信側通信ネットワークＡとの，“eth1”は送信側通信ネットワークＢとの，“eth2”は送信側通信ネットワークＣとの，各インタフェースを意味する。
【００７４】
“atm0”〜“atm2”は，ＡＴＭとのインタフェースを意味する。図１に示すように，入側ルータ１１Ｓには，ＡＴＭネットワークで構成された通信ネットワーク１の３つのリンクＬ１〜Ｌ３が接続されているので，“atm0”はリンクＬ１との，“atm1”はリンクＬ２との，“atm2”はリンクＬ３との各インタフェースを意味する。
【００７５】
受信テーブルおよび送信テーブルの“bytes”は，それぞれ，各インタフェース（interface）から受信したバイト数および各インタフェースへ送信したバイト数を示している。たとえば，インタフェース“lo”のデータによると，入側ルータ１１Ｓは，コンピュータ端末から６０８４バイトのデータを受信し，同じバイト数のデータをインタフェース“lo”に送信していることが示されている。
【００７６】
受信テーブルおよび送信テーブルの“packets”は，それぞれ，各インタフェース（interface）から受信したパケット数および各インタフェースへ送信したパケット数を示している。たとえば，インタフェース“eth0”のデータによると，ルータ１１Ｓは，送信側通信ネットワークＡから３２４個のパケットを受信し，２６７個のパケットを送信したことが示されている。
【００７７】
受信テーブルおよび送信テーブルの“errs”は，それぞれ，各インタフェースからの受信パケットのエラー数および各インタフェースへの送信パケットのエラー数を示している。
【００７８】
受信テーブルおよび送信テーブルの“drop”は，それぞれ，各インタフェースからの受信パケットの廃棄数および各インタフェースへの送信パケットの廃棄数を示している。
【００７９】
受信テーブルおよび送信テーブルの“fifo”は，それぞれ，受信処理待ちのパケット数（キュー（ＦＩＦＯ）の長さ）および送信処理待ちのパケット数（キュー（ＦＩＦＯ）の長さ）を示している。
【００８０】
受信テーブルの“frame”は受信フレーム数を，“compressed”は圧縮パケット数を，“multicast”は受信マルチキャスト・パケット数をそれぞれ示している。
【００８１】
送信テーブルの“colls”はイーサネット（ＣＳＭＡ／ＣＤ方式）における衝突（collision）の発生数を，“carrier”はイーサネットにおけるキャリア検出数を，“compressed”は圧縮パケット数を，それぞれ示している。
【００８２】
図６に示すテーブルの“interface type”は，通信ネットワーク１のリンクＬ１〜Ｌ３の３つのＡＴＭインタフェースのタイプを示し，“0 eni”は，インタフェース名“eni”のNo.1であり，“1 eni”は，インタフェース名“eni”のNo.2であり，“2 eni”は，インタフェース名“eni”のNo.３である。
【００８３】
“ESI/"MAC addr"”は，ＭＡＣ（Media Access Control）アドレスを示している。“AAL(Tx, err, Rx, err, drop)”は，ＡＴＭアダプテーション・レイヤ（Adaptation Layer）のパケットに関する統計情報を示している。“Tx”は送信パケット数を，左側の“err”は送信エラー数を，“Rx”は受信パケット数を，右側の“err”は受信エラー数を，“drop”は受信廃棄パケット数を，それぞれ示している。
【００８４】
図５および図６は，ともにリンクに関するデータであるが，ＯＳは，リンク内に設けられた各ＬＳＰに関するデータについても収集することもできる。
【００８５】
このシステム状態は，ＯＳによりリアルタイム（一定時間間隔Δｔごと）で収集されているので，この収集された情報に基づいて，前述したリンク・データの各フィールドのデータが求められる。
【００８６】
たとえば，時刻（ｎ−１）における図５の送信テーブルの“packets”と，時刻ｎにおける送信テーブルの“packets”との差分を求めることにより，前記式（２）の出力パケット数が求められる。また，この差分である出力パケット数をそのリンクの帯域で除算することにより，式（２）のCUTY（ｎ）が求められる。さらに，このCUTY（ｎ）に基づいて，前記式（１）のAve Utilizationが求められる。
【００８７】
また，図５の送信テーブルまたは図６の“drop”は，廃棄パケット数の積算値であるので，時刻ｎの“drop”の値が前記式（４）のLoss（ｎ）となる。
【００８８】
＜オペークＬＳＡのフラッディング方法＞
（１）第１のフラッディング方法
オペークＬＳＡは，フラッディング（flooding）を用いて他のルータに送信される。このフラッディングを行うタイミングは，たとえば，一定時間間隔Ｔthごとにすることができる。この一定時間間隔Ｔthは，システム状態が更新される前記時間Δｔ以上（好ましくはΔｔの正の整数倍）であって，通信ネットワーク１がオペークＬＳＡの送信により輻輳しない間隔であり，かつ，ＴＥを効果的に行うことができる間隔に設定される。その具体的な値は，実験，シミュレーション，計算等により求められる。
【００８９】
図７は，第１のフラッディング方法の処理の流れを示すフローチャートである。この処理は，処理装置３０（図２参照）により実行される。
【００９０】
まず，ルータ１１に電源が投入される等によって，ルータ１１が起動すると，処理装置３０の内部に設けられたタイマ（図示略）が起動され，計時を開始する（ステップＳ１０）。
【００９１】
続いて，タイマの時間ｔがフラッディング時間間隔Ｔthに達しているかどうかが判定される（ステップＳ１２）。達していない場合には(ステップＳ１２でＮＯ)，他のルータ１１からＬＳＡを受信しているかどうかが判定される（ステップＳ２６）。他のルータからＬＳＡを受信していない場合には（ステップＳ２６でＮＯ），ステップＳ１２に戻り，受信している場合には（ステップＳ２６でＹＥＳ），受信したＬＳＡがオペークＬＳＡかどうかが判定される（ステップＳ２８）。この判定は，前述したＬＳＡヘッダのリンク状態タイプの値によって行われる。リンク状態タイプが９，１０または１１の場合には，オペークＬＳＡと判断され，それ以外の場合には，通常のＬＳＡ（オペークＬＳＡ以外のＬＳＡ）と判断される。
【００９２】
オペークＬＳＡである場合には（ステップＳ２８でＹＥＳ），オペークＬＳＡ用データベースの更新処理（後に詳述）が行われ（ステップＳ３０），その後，受信したオペークＬＳＡが，受信したリンク以外のすべてのリンク（出力リンク）に送出（フラッディング）される（ステップＳ３２）。その後，ステップＳ１２に処理が戻る。一方，通常のＬＳＡである場合には（ステップＳ２８でＮＯ），通常のＬＳＡの受信処理が行われ（ステップＳ３４），その後，処理はステップＳ１２に戻る。この通常のＬＳＡの受信処理には，リンク状態データベースの更新処理が含まれている。
【００９３】
ステップ１２でタイマの時間ｔが時間Ｔth以上である場合には（ステップＳ１２でＹＥＳ），他のルータからのＬＳＡが受信されているかどうかが判定される(ステップＳ１４)。
【００９４】
ＬＳＡが受信されている場合には（ステップＳ１４でＹＥＳ），ステップＳ１６からＳ２０およびＳ３６の処理が行われる。これらの処理は，前述したステップＳ２８からＳ３２およびＳ３４とそれぞれ同じである。その後，タイマ時間ｔは一定時間Ｔthを経過しているので，自ルータのオペークＬＳＡが生成され，このオペークＬＳＡがすべてのリンク（出力リンク）に送出（フラッディング）される（ステップＳ２２）。
【００９５】
その後，自ルータのオペークＬＳＡによるオペークＬＳＡ用データベースの更新処理が行われる（ステップＳ２３）。そして，タイマがゼロにリセットされ，処理はステップＳ１２に戻る。
【００９６】
一方，ステップＳ１４において，他のルータからオペークＬＳＡが受信されていない場合には，直ちに自ルータのオペークＬＳＡが生成されて，すべてのリンクに送出された後（ステップＳ２２），自ルータのオペークＬＳＡによるオペークＬＳＡ用データベースの更新処理が行われる（ステップＳ２３）。そして，タイマがリセットされ（ステップＳ２４），処理は，ステップＳ１２に戻る。
【００９７】
（２）第２のフラッディング方法
フラッディング方法には，他のルータからオペークＬＳＡを受信すると，その受信したオペークＬＳＡの送信とともに，自己のルータのトラフィック情報を収めたオペークＬＳＡを生成し，送信する方法（この方法を「第２のフラッディング方法」という。）もある。
【００９８】
図８は，第２のフラッディング方法の処理の流れを示すフローチャートである。前述した図７のフローチャートにおける処理と同じ処理には同じ符号を付し，その詳細な説明を省略することとする。この処理も，処理装置３０により実行される。
【００９９】
まず，ルータ１１に電源が投入される等により，ルータ１１が起動すると，タイマが起動され（ステップＳ１０），タイマの時間ｔが閾値時間Ｔth１に達しているかどうかが判定される（ステップＳ５０）。この閾値時間Ｔth１は，ルータ１１のＯＳがシステム状態を更新する時間Δｔ以上であって，かつ，第１のフラッディング方法における時間間隔Ｔthよりも小さな時間に設定されている。この時間Ｔth１をこのように設定するのは，この一定時間Ｔth１を経過する前に，他のルータから２以上のオペークＬＳＡを受信した場合であっても，自ルータについての同一内容のオペークＬＳＡを２回以上フラッディングさせないためである。
【０１００】
タイマの時間ｔが閾値時間Ｔth１に達している場合には（ステップＳ５０でＹＥＳ），他のルータ１１からのオペークＬＳＡの受信を待って，自己のルータ１１のトラフィック情報を収めたオペークＬＳＡが作成／送信され（ステップＳ１４〜Ｓ２４，Ｓ３６），その後，処理はステップＳ５０に戻る。
【０１０１】
一方，タイマの時間ｔが閾値時間Ｔth１に達していない場合には（ステップＳ５０でＮＯ），他のルータ１１からオペークＬＳＡを受信しても，自己のルータ１１のトラフィック情報を収めたオペークＬＳＡは作成／送信されず（ステップＳ２６〜Ｓ３４），その後，処理はステップＳ５０に戻る。
【０１０２】
（３）第３のフラッディング方法
第１のフラッディング方法と第２のフラッディング方法とを複合させたフラッディング方法もある。すなわち，オペークＬＳＡを一定時間間隔Ｔthで送信する（第１のフラッディング方法）とともに，他のルータ１１からオペークＬＳＡを受信すると，その受信したオペークＬＳＡの送信とともに，自己のルータのトラフィック情報を収めたオペークＬＳＡを生成し，送信する（第２のフラッディング方法）方法である。
【０１０３】
図９および図１０は，第３のフラッディング方法の処理の流れを示すフローチャートである。前述した図７および図８のフローチャートにおける処理と同じ処理には同じ符号を付し，その詳細な説明を省略することとする。この処理も，処理装置３０により実行される。
【０１０４】
タイマのスタート（ステップＳ１０）後，タイマの時間ｔが，第２のフラッディング方法で述べた一定時間Ｔth１を経過しているかどうかが判定される（ステップＳ５０）。
【０１０５】
タイマ時間ｔが一定時間Ｔth１に達していない場合には（ステップS５０でＮＯ），ステップＳ２６からＳ３４までの処理が実行される。すなわち，他のルータ１１からオペークＬＳＡが受信されると，このオペークＬＳＡによりデータベース更新処理が実行されるとともに，このオペークＬＳＡのさらに他のルータに向けて送信する。その後，処理は，ステップＳ５０に戻る。
【０１０６】
一方，タイマ時間ｔが一定時間間隔Ｔth１に達している場合には（ステップＳ５０でＹＥＳ），タイマ時間ｔが，第１のフラッディング方法で述べた一定時間間隔Ｔthと比較される（ステップＳ１２）。
【０１０７】
この一定時間間隔Ｔthに達していない場合には（ステップＳ１２でＮＯ），他のルータ１１からのＬＳＡの受信を待って，この他のルータ１１から受信されたＬＳＡの（データベース更新処理，他のルータへの送信処理等）が実行される（ステップＳ１６からＳ２４，Ｓ３６）。その後，処理は，ステップＳ５０に戻る。
【０１０８】
一方，一定時間間隔Ｔthに達している場合には（ステップＳ１２でＹＥＳ），他のルータからのオペークＬＳＡの受信の有無に関係なく，自己のルータのトラフィックの状態を格納したオペークＬＳＡが作成され，送信される（ステップＳ５２〜Ｓ６４）。なお，ステップＳ５２〜Ｓ６０の処理は，ステップＳ２６〜Ｓ３４の処理とそれぞれ同じであり，ステップＳ６２〜Ｓ６４の処理は，ステップＳ２２〜Ｓ２４の処理と同じである。その後，処理は，ステップＳ５０に戻る。
【０１０９】
＜オペークＬＳＡ用データベースのデータ構造およびその更新処理＞
図１２は，ルータ１１の記憶装置３２に設けられたオペークＬＳＡ用データベース３２ｂのデータ構造を示す。
【０１１０】
オペークＬＳＡ用データベース３２ｂは，ハッシュ・テーブル５０と，各ルータ（自ルータを含む。）１１のオペークＬＳＡを有するオペークＬＳＡデータベース構造体（以下「ＯＬＤＢ構造体」という。）５１ａ〜５１ｃ，５２ａ〜５２ｄ，５３ａおよび５３ｂ等とから構成されている。
【０１１１】
ハッシュ・テーブル５０は，複数の記憶セルを備え，各記憶セルは，受信されたオペークＬＳＡのＬＳＡヘッダにある「広告ルータ」の値（すなわち広告ルータのＩＰアドレス）をハッシュしたハッシュ値ｈ１〜ｈ３等をアドレスとしてアクセスされる。各記憶セルには，ＯＬＤＢ構造体へのポインタが格納される。たとえば，ハッシュ値ｈ１に対応する記憶セルには，ＯＬＤＢ構造体５１ａへのポインタが，ハッシュ値ｈ２に対応する記憶セルには，ＯＬＤＢ構造体５２ａへのポインタが，ハッシュ値ｈ３に対応する記憶セルには，ＯＬＤＢ構造体５３ａへのポインタが，それぞれ格納されている。図示しない他のハッシュ値に対応する記憶セルにも，図示しない他のＯＬＤＢ構造体へのポインタが格納されている。
【０１１２】
ＯＬＤＢ構造体は，受信したオペークＬＳＡの内容（図３および図４に示す各フィールド）を含むとともに，隣接する次のＯＬＤＢ構造体へのポインタ（たとえばＯＬＤＢ構造体５１ａは次のＯＬＤＢ構造体５１ｂへのポインタ），ルートまでの距離（コスト）の計算に必要なフィールド等を含んでいる。１つのＯＬＤＢ構造体には，１つのルータ１１が対応している。
【０１１３】
ハッシュ・テーブル５０のハッシュ値としては，たとえば，ＬＳＡヘッダの「広告ルータ」値（ＩＰアドレス）を整数とみなし，この整数を素数２５１で除算した商（整数値）が用いられる。この場合に，ハッシュ・テーブル５０は，２５１個の記憶セルを有し，通信ネットワーク１内の複数のルータ１１は，２５１個のグループに分類されることとなる。そして，２５１個のグループに分類された各グループに属する複数のルータのＯＬＤＢ構造体は，たとえばＯＬＤＢ構造体５１ａ〜５２ｃのように，ポインタにより連結される。
【０１１４】
なお，同じグループに属する複数のルータは，ＩＰアドレスが近いので，地理的にも近い位置に配置されていることが多い。
【０１１５】
このように，ハッシュ・テーブルを用いることにより，複数のルータをグループに分類することができるので，後述するように，特定のルータのＯＬＤＢ構造体を検索する時に，検索の高速化を図ることができる。
【０１１６】
図１１は，図７から図１０に示すステップＳ１８，Ｓ２３，Ｓ３０，およびＳ６４のオペークＬＳＡ用データベースの更新処理の詳細な処理の流れを示すフローチャートである。この処理は，各ルータ１１の処理装置３０により実行される。
【０１１７】
まず，オペークＬＳＡを格納するＯＬＤＢ構造体の記憶領域を記憶装置３２内に確保可能かどうかが判定される（ステップＳ１００）。確保可能である場合には（ステップＳ１００でＹＥＳ），記憶領域が確保され（ステップＳ１０２），確保された記憶領域に，受信したオペークＬＳＡが格納される（ステップＳ１０４）。
【０１１８】
続いて，オペークＬＳＡを受信したルータのＩＰアドレスがハッシュされ，このハッシュ値をアドレスとするハッシュ・テーブル５０の記憶セルが決定される（ステップＳ１０６）。続いて，決定された記憶セルにポインタにより連結された１または２以上のＯＬＤＢ構造体の中から，受信されたオペークＬＳＡの発信ルータのＩＰアドレスと一致するものがあるかどうかが判定（すなわち検索）される（ステップＳ１０８）。この検索では，検索範囲がハッシュ・テーブル５０の１つの記憶セルに対応するＯＬＤＢ構造体のグループに絞り込まれているので，高速に検索を行うことができる。
【０１１９】
一致するＯＬＤＢ構造体がない場合には（ステップＳ１１８でＮＯ），受信されたオペークＬＳＡを格納したＯＬＤＢ構造体は，ステップＳ１０６で決定された記憶セルに連結されたＯＬＤＢ構造体の最後尾に連結される。たとえば，ハッシュ値が，図１２のハッシュ値ｈ１の場合には，受信されたオペークＬＳＡのＯＬＤＢ構造体は，ＯＬＤＢ構造体５１ｃの後ろに連結され，ＯＬＤＢ構造体５１ｃ内に設けられたポインタには，連結された新たなＯＬＤＢ構造体へのポインタが格納される。
【０１２０】
一方，ステップＳ１０８において，一致するものがある場合には（ステップＳ１０８でＹＥＳ），受信されたオペークＬＳＡが最新（時間的に最も後）のもの（すなわち，最新のトラフィック情報を有するオペークＬＳＡ）かどうかが判定される（ステップＳ１１０）。
【０１２１】
最新でない場合には（ステップＳ１１０でＮＯ），受信されたオペークＬＳＡは廃棄され，ステップＳ１０２で確保された記憶領域は解放される（ステップＳ１１２）。一方，最新である場合には（ステップＳ１１０でＹＥＳ），この最新のＯＬＤＢ構造体が，データベース３２ｂ内に既にある古いＯＬＤＢ構造体と入れ替えられる（ステップＳ１１４）。たとえば，図１２のＯＬＤＢ構造体５１ｂが，受信された新たなオペークＬＳＡを有するＯＬＤＢ構造体（「ＯＬＤＢ構造体ｘ」とする。）によって入れ替えられる場合には，この同じ位置にＯＬＤＢ構造体ｘが挿入される。あるいは，ＯＬＤＢ構造体５１ｃをＯＬＤＢ構造体５１ａの直後に連結するとともに，ＯＬＤＢ構造体５１ｃの直後にＯＬＤＢ構造体ｘを連結することもできる。
【０１２２】
その後，古いオペークＬＳＡのＯＬＤＢ構造体の記憶領域は解放され（ステップＳ１１６），処理は終了する。
【０１２３】
＜負荷分散の一例＞
最後に，オペークＬＳＡ用データベース３２ｂに格納された各ルータ１１のトラフィック情報に基づいて行われる負荷分散の一例について説明する。
【０１２４】
経路１，２，３（図１参照）の各論理帯域（ＬＳＰの帯域）［ｂｐｓ］をそれぞれ１０Ｍ，８Ｍ，２Ｍとする。
【０１２５】
入側ルータ１１Ｓ（処理装置３０）は，ＴＥによる負荷分散制御を行うために，まず経路１，２，３のそれぞれの実効負荷を算出する。ここで，「実効負荷」とは，リンクの使用率とこのリンクにおけるパケット廃棄率（パケット損失率）とから計算される実効的な使用率である。本来的には，リンクの実際の負荷を計測すればよいが，実際には，ルータ１１によって，その内部が多段スイッチ構成になっている場合があり，この場合には，直接的に負荷を計測することは困難であることから，この実効負荷が用いられる。
【０１２６】
この実効負荷は，経路ｉの実効負荷をρ effective path ｉとすると，たとえば以下の式（８）および（９）で求めることができる。
【０１２７】
ρ effective path ｉ＝ρ path ｉ×ｆ（Loss path ｉ）  …（８）
ρ effective path ｉ＝Min（ρ effective path ｉ，ρ ceiling）  …（９）
ここで，ρ path ｉは，経路ｉ（path ｉ）を構成する１または２以上のリンク（link ｊ）全体の平均使用率であり，以下の式により求められる。
【０１２８】
ρ path ｉ＝Average（Ave Utilization（link ｊ，path ｉ））  …（１０）
また，Loss path ｉは，経路ｉを構成する各リンクの廃棄パケット数
（Loss  link ｊ）の合計であり，以下の式により求められる。
【０１２９】
Loss path ｉ＝ΣLoss link ｊ  …（１１）
関数ｆは，パケットの廃棄が発生した場合に，負荷を高めに計算するように修正するための関数である。これは，パケットの廃棄がない場合には，リンクの負荷ρ path ｉと実効負荷とは一致するが，パケットの廃棄が発生すると，負荷を高めに修正する必要があるためである。ρ ceilingは，実効負荷の上限値である。
【０１３０】
今，経路１，２，３の実効負荷を，それぞれρ effective path １＝０．５，ρ effective path ２＝０．２，ρ effective path ３＝０．３とすると，経路１，２，３の実トラフィック［ｂｐｓ］は，それぞれ１０Ｍ×０．５＝５Ｍ，８Ｍ×０．２＝１．６Ｍ，２Ｍ×０．３＝０．６Ｍとなる。
【０１３１】
続いて，ルータ１１Ｓ（処理装置３０）は，負荷調整（Load Adjusting）を行う。まず，経路１，２，３のすべてを仮想的な１つのパイプとみなし，このパイプの平均使用率ρave effectiveが以下の式により求められる。
【０１３２】
ρave effective＝Σ（ρ effective path ｉ×LBW path ｉ）／ΣLBW path ｉ  …（１２）
ここで，LBW path ｉは，経路ｉの論理帯域である。
【０１３３】
式（１２）を上記例に当てはめると，
ρave effective＝（５Ｍ＋１．６Ｍ＋０．６Ｍ）／（１０Ｍ＋８Ｍ＋２Ｍ）＝０．３６
となる。
【０１３４】
次に，経路間で移動する実効帯域ΔEBW path ｉ［ｂｐｓ］が以下の式により算出される。
【０１３５】
ΔEBW path ｉ＝（ρave effective−ρ effective path ｉ×LBW path ｉ）…（１３）
これを経路１，２，３のそれぞれについて算出すると，以下のようになる。
【０１３６】
経路１の移動する実効帯域ΔEBW PATH1＝（０．３６−０．５）×１０Ｍ＝−１．４Ｍ
経路２の移動する実効帯域ΔEBW PATH2＝（０．３６−０．２）×８Ｍ＝＋１．２８Ｍ
経路3の移動する実効帯域ΔEBW PATH3＝（０．３６−０．３）×２Ｍ＝＋０．１２Ｍ
なお，各経路の移動する実効帯域の総和は，−１．４Ｍ＋１．２８Ｍ＋０．１２Ｍ＝０となる。
【０１３７】
この計算結果に基づいて負荷調整を行うと，経路１については，５Ｍ−１．４Ｍ＝３．６Ｍ，経路２については，１．６Ｍ＋１．２８Ｍ＝２．８８Ｍ，経路３については，０．６Ｍ＋０．１２Ｍ＝０．７２Ｍとなり，経路１，２，３について，３．６×Ｇｒ：２．８８×Ｇｒ：０．７２×Ｇｒの比で負荷分散（トラフィックの分配）の変更を行えばよいこととなる。なお，Ｇｒは，負荷調整係数である。
【０１３８】
（付記１）  通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードに設けられ，前記通信路のトラフィックに関する情報を収集するトラフィック情報収集装置であって，
自己のノードに接続された通信路のトラフィックに関する情報を収集するトラフィック情報収集部と，
前記通信ネットワーク上の通信プロトコルで使用されるメッセージにより，前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報を他のノードに送信するトラフィック情報送信部と，
他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報を受信するトラフィック情報受信部と，
前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，前記トラフィック情報受信部により受信された前記他のノードに接続された通信路のトラフィックに関する情報とを記憶するトラフィック情報記憶部と，
を備えているトラフィック情報収集装置。
【０１３９】
（付記２）  付記１において，
前記トラフィック情報送信部は，あらかじめ定められた一定時間間隔ごとに前記自己のノードに接続された通信路のトラフィックに関する情報を送信する，トラフィック情報収集装置。
【０１４０】
（付記３）  付記１において，
前記トラフィック情報送信部は，前記他のノードに接続された通信路のトラフィックに関する情報が該他のノードから送信されてきた時に，前記自己のノードに接続された通信路のトラフィックに関する情報を送信する，
トラフィック情報収集装置。
【０１４１】
（付記４）  付記１において，
前記トラフィック情報送信部は，あらかじめ定められた一定時間間隔ごとに前記自己のノードに接続された通信路のトラフィックに関する情報を送信するとともに，
前記他のノードに接続された通信路のトラフィックに関する情報が該他のノードから送信されてきた時に，前記自己のノードに接続された通信路のトラフィックに関する情報を送信する，
トラフィック情報収集装置。
【０１４２】
（付記５）  通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードに設けられ，前記通信路のトラフィック情報を収集するトラフィック情報収集装置であって，
自己のノードに接続された通信路のトラフィックに関する情報を収集するトラフィック情報収集部と，
前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報とを記憶するトラフィック情報記憶部と，
を備えているトラフィック情報収集装置。
【０１４３】
（付記６）  付記１から５のいずれか１つにおいて，
前記他のノードから送信されてきたトラフィックに関する情報を，送信されてきた通信路を除く他の通信路に転送するトラフィック情報転送部をさらに備えている，
トラフィック情報収集装置。
【０１４４】
（付記７）  付記１から６のいずれか１つにおいて，
前記トラフィックに関する情報が，トラフィックを出力する通信路のトラフィックに関する情報である，
トラフィック情報収集装置。
【０１４５】
（付記８）  付記１から７のいずれか１つにおいて，
前記トラフィック情報収集部が，あらかじめ定められた一定時間間隔ごとに前記自己のノードに接続された通信路のトラフィックに関する情報を収集する，
トラフィック情報収集装置。
【０１４６】
（付記９）  付記１から８のいずれか１つにおいて，
前記トラフィックに関する情報が，通信路の平均使用率，通信路の廃棄されたパケット数，および通信路の帯域，ならびに，通信路を論理的な通信路に分割した場合における該論理的な通信路の平均使用率，廃棄されたパケット数，および該論理的な通信路の帯域を含む，
トラフィック情報収集装置。
【０１４７】
（付記１０）  付記１から９のいずれか１つにおいて，
前記通信プロトコルで使用されるメッセージが，ＯＳＰＦにおけるオペーク・リンク状態広告である，トラフィック情報収集装置。
【０１４８】
（付記１１）  付記１から１０のいずれか１つにおいて，
前記ノードがルータである，トラフィック情報収集装置。
【０１４９】
（付記１２）  付記１から１１のいずれか１つにおいて，
前記トラフィック情報収集装置を有するノードが，前記通信ネットワークにおけるトラフィックの負荷分散制御を行うノードである，
トラフィック情報収集装置。
【０１５０】
（付記１３）  付記１から１２のいずれか１つにおいて，
前記トラフィック情報記憶部が，ハッシュ・テーブルと，前記各ノードのトラフィックに関する情報を有する構造体データとを備え，
前記ハッシュ・テーブルは，前記各ノードをユニークに識別する情報をハッシュしたハッシュ値をアドレスとする記憶セルを有するとともに，各記憶セルには，該記憶セルのハッシュ値に対応するノードのトラフィックに関する情報を有する前記構造体データへのポインタが格納されており，
前記構造体データは，同じハッシュ値に対応する他の構造体データがある場合には，該他の構造体データへのポインタをさらに備えている，
トラフィック情報収集装置。
【０１５１】
（付記１４）  付記１から１３のいずれか１つにおいて，
前記トラフィック情報記憶部は，トラフィックに関する情報を記憶する際に，同じノードのトラフィックに関する情報が既に存在する場合には，それらのうちの時間的に後のトラフィックに関する情報を記憶する，
トラフィック情報収集装置。
【０１５２】
（付記１５）  通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける該ノードであって，
自己に接続された通信路のトラフィックに関する情報を収集するトラフィック情報収集部と，
前記通信ネットワーク上の通信プロトコルで使用されるメッセージにより，前記トラフィック情報収集部により収集された前記自己に接続された通信路のトラフィックに関する情報を他のノードに送信するトラフィック情報送信部と，
他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報を受信するトラフィック情報受信部と，
前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，前記トラフィック情報受信部により受信された前記他のノードに接続された通信路のトラフィックに関する情報とを記憶するトラフィック情報記憶部と，
を備えているノード。
【０１５３】
（付記１６）  通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける該ノードであって，
自己に接続された通信路のトラフィックに関する情報を収集するトラフィック情報収集部と，
前記トラフィック情報収集部により収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報とを記憶するトラフィック情報記憶部と，
を備えているノード。
【０１５４】
（付記１７）  通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードで行われる，前記通信路のトラフィックに関する情報を収集するトラフィック情報収集方法であって，
自己のノードに接続された通信路のトラフィックに関する情報を収集し，
前記通信ネットワーク上の通信プロトコルで使用されるメッセージにより，前記収集された前記自己のノードに接続された通信路のトラフィックに関する情報を他のノードに送信し，
他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報を受信し，
前記収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，前記受信された前記他のノードに接続された通信路のトラフィックに関する情報とを記憶する，
トラフィック情報収集方法。
【０１５５】
（付記１８）  通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードで行われる，前記通信路のトラフィック情報を収集するトラフィック情報収集方法であって，
自己のノードに接続された通信路のトラフィックに関する情報を収集し，
前記収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報とを記憶する，
トラフィック情報収集方法。
【０１５６】
（付記１９）  通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードで実行される，前記通信路のトラフィックに関する情報を収集するトラフィック情報収集プログラムであって，
自己のノードに接続された通信路のトラフィックに関する情報を収集する手順と，
前記通信ネットワーク上の通信プロトコルで使用されるメッセージにより，前記収集された前記自己のノードに接続された通信路のトラフィックに関する情報を他のノードに送信する手順と，
他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報を受信する手順と，
前記収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，前記受信された前記他のノードに接続された通信路のトラフィックに関する情報とを記憶する手順と，
を備えているトラフィック情報収集プログラム。
【０１５７】
（付記２０）  通信される情報を送信，受信または中継する複数のノードと，該複数のノードを接続する通信路とを有する通信ネットワークにおける前記ノードで実行される，前記通信路のトラフィック情報を収集するトラフィック情報収集プログラムであって，
自己のノードに接続された通信路のトラフィックに関する情報を収集する手順と，
前記収集された前記自己のノードに接続された通信路のトラフィックに関する情報と，他のノードから送信されてきた該他のノードに接続された通信路のトラフィックに関する情報とを記憶する手順と，
を備えているトラフィック情報収集プログラム。
【０１５８】
【発明の効果】
本発明によると，通信ネットワーク上のノードが，通信ネットワークにおけるトラフィックに関する情報を収集することができ，該情報により，負荷分散制御を行うことができる。
【図面の簡単な説明】
【図１】本発明に係る情報収集装置を備えたノードを有する通信ネットワーク１の概略構成を示すブロック図である。
【図２】入側ルータの構成を示すブロック図である。
【図３】オペークＬＳＡのデータ構造を示す。
【図４】オペークＬＳＡに含まれるリンク・データのデータ構造を示す。
【図５】ルータのＯＳがリアルタイムで収集／管理しているシステム状態のデータの一例を示す。
【図６】ルータのＯＳがリアルタイムで収集／管理しているデータの一例を示す。
【図７】第１のフラッディング方法の処理の流れを示すフローチャートである。
【図８】第２のフラッディング方法の処理の流れを示すフローチャートである。
【図９】第３のフラッディング方法の処理の流れを示すフローチャートである。
【図１０】第３のフラッディング方法の処理の流れを示すフローチャートである。
【図１１】オペークＬＳＡ用データベース更新処理の流れを示すフローチャートである。
【図１２】オペークＬＳＡ用データベースのデータ構造を示す。
【符号の説明】
１  通信ネットワーク
１１Ｓ  入側ルータ
１１Ｒ  中継ルータ
１１Ｄ  出側ルータ
Ｌ１，Ｌ２，Ｌ３  リンク
２１，２２，２３  経路（仮想コネクション）
３０  処理装置
３２  記憶装置
３２ｂ  オペークＬＳＡ用データベース
４１〜４７  インタフェース装置
【図１】
0004511021.tif 000002
【図２】
0004511021.tif 000003
【図３】
0004511021.tif 000004
【図４】
0004511021.tif 000005
【図５】
0004511021.tif 000006
【図６】
0004511021.tif 000007
【図７】
0004511021.tif 000008
【図８】
0004511021.tif 000009
【図９】
0004511021.tif 000010
【図１０】
0004511021.tif 000011
【図１１】
0004511021.tif 000012
【図１２】
0004511021.tif 000013