JP2002204250A - トラフィック情報収集装置およびトラフィック情報収集方法 - Google Patents

Abstract

(57)【要約】 【課題】 通信ネットワーク上のノードがトラフィック
に関する情報を収集できるようにする。 【解決手段】 通信ネットワーク１は，トラフィック・
エンジニアリングによる付加分散制御が行われる通信ネ
ットワークである。通信ネットワーク１に配置された入
側ルータ１１Ｓ，中継ルータ１１Ｒおよび出側ルータ１
１Ｄは，自己に接続された各リンクのトラフィック情報
を収集し，データベースに記憶する。また，これらの各
ルータ１１は，収集したトラフィック情報をオペークＬ
ＳＡによりフラッディングする。オペークＬＳＡを受信
した各ルータ１１は，自己のデータベースにオペークＬ
ＳＡの情報を記憶する。これにより，入側ルータ１１Ｓ
は，各リンクのトラフィックの情報に基づいて負荷分散
制御を行う。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は，通信ネットワーク
におけるトラフィック情報収集装置，トラフィック情報
収集方法，およびトラフィック情報収集プログラムに関
し，特に，通信ネットワークにおいて，負荷分散を行う
ために必要な情報を収集するためのトラフィック情報収
集装置，トラフィック情報収集方法，およびトラフィッ
ク情報収集プログラムに関する。

【０００２】また，本発明は，通信ネットワークにおい
て，負荷分散を行うために必要な情報を収集する機能を
有する，通信ネットワークにおけるノードに関する。

【０００３】

【従来の技術】インターネットは，コネクションを確立
しないコネクションレスなネットワークであり，通信デ
ータは，ＩＰ（Internet Protocol）アドレスが付与さ
れたＩＰパケットに分割され送信される。ＩＰパケット
は，ＩＰアドレスに基づいてルータ間を中継され，宛先
ルータまたはコンピュータ（以下，単に「宛先」とい
う。）に届けられる。

【０００４】ＩＰアドレスに基づいてルータ間をどのよ
うに中継して，ＩＰパケットを宛先まで届けるかは，ル
ーティング・プロトコルによって決定される。ルーティ
ング・プロトコルとして，現在，ＲＩＰ（Routing Info
rmation Protocol）またはＯＳＰＦ（Open Shortest Pa
th First）が一般に使用されている。これらのルーティ
ング・プロトコルは，基本的には，通信ネットワーク内
の各リンクのコスト（たとえばホップ数）に基づいて宛
先までの最短の経路（ルート，パス）を求め，その最短
経路をＩＰパケットの通信経路として設定するものであ
る。

【０００５】

【発明が解決しようとする課題】しかし，これらのルー
ティング・プロトコルでは，コストに基づく最短経路が
求められるだけであって，各リンクのトラフィックの状
況を考慮した経路は求められない。しかも，経路が新た
に設定されるのは，通信ネットワークのトポロジーに変
化が生じた場合だけであり，リアルタイムに設定／変更
が行われるわけではない。一方，インターネットの普及
により，インターネット内を行き交うパケットの量（す
なわちトラフィック量または負荷）は急激に増加してい
る。

【０００６】その結果，ルーティング・プロトコルによ
り設定された経路上で，輻輳が発生するようになってい
る。

【０００７】なるほど，ＯＳＰＦには，複数の経路を設
定してＩＰパケットを分散する等コスト・マルチパス
（Equal Cost Multipath）というルーティングもある。
しかし，このルーティングは，コストが等しい経路が複
数存在する場合に限られており，また，ＯＳＰＦを使用
しているため，リアルタイムの通信ネットワークの負荷
の変動に対処できない。

【０００８】そこで，現在，インターネットにおける輻
輳を回避する技術体系として，トラフィック・エンジニ
アリングが検討されている。このトラフィック・エンジ
ニアリングは，一般に，宛先までの経路を複数設定する
とともに，各経路のトラフィックの状況をリアルタイム
に監視して，空きのある経路や負荷の小さな経路を選択
してＩＰパケットを送信し，複数の経路間で負荷（トラ
フィック）の分散を行うものである。

【０００９】一方，このようなトラフィック・エンジニ
アリングを行うためには，各ルータが，各経路の使用状
況を含む，トラフィックに関する情報を知る必要があ
る。

【００１０】本発明は，このような状況に鑑みなされた
ものであり，トラフィックの状況に応じて負荷分散を図
ることができるように，通信ネットワーク上のノードが
トラフィックに関する情報を収集できるようにすること
にある。

【００１１】

【課題を解決するための手段】前記目的を達成するため
に，本発明に係る情報収集装置は，通信される情報を送
信，受信または中継する複数のノードと，該複数のノー
ドを接続する通信路とを有する通信ネットワークにおけ
る前記ノードに設けられ，前記通信路のトラフィックに
関する情報を収集するトラフィック情報収集装置であっ
て，自己のノードに接続された通信路のトラフィックに
関する情報を収集するトラフィック情報収集部と，前記
通信ネットワーク上の通信プロトコルで使用されるメッ
セージにより，前記トラフィック情報収集部により収集
された前記自己のノードに接続された通信路のトラフィ
ックに関する情報を他のノードに送信するトラフィック
情報送信部と，他のノードから送信されてきた該他のノ
ードに接続された通信路のトラフィックに関する情報を
受信するトラフィック情報受信部と，前記トラフィック
情報収集部により収集された前記自己のノードに接続さ
れた通信路のトラフィックに関する情報と，前記トラフ
ィック情報受信部により受信された前記他のノードに接
続された通信路のトラフィックに関する情報とを記憶す
るトラフィック情報記憶部と，を備えている。

【００１２】また，本発明に係る情報収集装置は，通信
される情報を送信，受信または中継する複数のノード
と，該複数のノードを接続する通信路とを有する通信ネ
ットワークにおける前記ノードに設けられ，前記通信路
のトラフィック情報を収集するトラフィック情報収集装
置であって，自己のノードに接続された通信路のトラフ
ィックに関する情報を収集するトラフィック情報収集部
と，前記トラフィック情報収集部により収集された前記
自己のノードに接続された通信路のトラフィックに関す
る情報と，他のノードから送信されてきた該他のノード
に接続された通信路のトラフィックに関する情報とを記
憶するトラフィック情報記憶部と，を備えている。

【００１３】本発明に係る情報収集装置によると，通信
ネットワークにおけるノードは，自己のノードに接続さ
れた通信路のトラフィックに関する情報を収集するとと
もに，他のノードから送信されてきた該他のノードに接
続された通信路のトラフィックに関する情報を受信し，
これらの情報を記憶する。したがって，ノードは，記憶
されたこれらの情報に基づいて，通信ネットワーク上の
各通信路のトラフィックの状況を知ることができ，その
結果，トラフィックの状況に応じた負荷分散制御を行う
ことが可能となる。

【００１４】好ましくは，前記他のノードから送信され
てきたトラフィックに関する情報を，送信されてきた通
信路を除く他の通信路に転送するトラフィック情報転送
部が，さらに備えられる。

【００１５】これにより，あるノードに送信されてき
た，他のノードのトラフィックに関する情報を，それ以
外の他のノードにも伝達することができ，伝達された他
のノードも，トラフィックに関する情報を入手すること
ができる。その結果，通信ネットワーク上のすべてのノ
ードが，該通信ネットワークの各通信路のトラフィック
の状況を把握することができる。

【００１６】

【発明の実施の形態】＜通信ネットワーク１の構成＞図
１は，本発明に係る「情報収集装置」を含んだノードを
有する通信ネットワーク１の概略構成を示すブロック図
である。この通信ネットワーク１は，本実施の形態では
インターネットの一部を形成するとともに，トラフィッ
ク・エンジニアリング（以下「ＴＥ」という。）による
負荷分散が行われる通信ネットワークである。また，こ
の通信ネットワーク１は，本実施の形態では，非同期転
送モード（Asynchronous Transfer Mode：以下「ＡＴ
Ｍ」という。）により，ＩＰパケット（以下，単に「パ
ケット」という。）を送受信する通信ネットワークであ
る。

【００１７】通信ネットワーク１には，外部の通信ネッ
トワークとして，通信ネットワーク１にパケットを送信
する送信側通信ネットワークＡ，ＢおよびＣと，通信ネ
ットワーク１から送信されるパケットを受信する受信側
通信ネットワークＤおよびＥとが接続されている。

【００１８】これら外部の通信ネットワークを「送信側
通信ネットワーク」と「受信側通信ネットワーク」とに
分けたのは，ＴＥを説明するための便宜上のためであ
り，送信側通信ネットワークはパケットの送信のみを行
うとは限らず，また，受信側通信ネットワークはパケッ
トの受信のみを行うとは限らない。たとえば，通信ネッ
トワーク１から送信側通信ネットワークＡ，ＢおおびＣ
にパケットが送信される場合もあるし，また，受信側通
信ネットワークＤおよびＥから通信ネットワーク１にパ
ケットが送信される場合もある。

【００１９】これらの送信側通信ネットワークＡ，Ｂお
よびＣ，ならびに受信側通信ネットワークＤおよびＥ
は，インターネットの一部を形成し，本実施の形態で
は，イーサネット（登録商標）で構築されている。

【００２０】通信ネットワーク１は，「ノード」の一例
としてのルータ（後述するラベル・スイッチ・ルータ）
を複数備えている。これらのルータには，入側ルータ１
１Sと，出側ルータ１１Ｄと，複数の中継ルータ１１Ｒ
とが含まれている。

【００２１】入側ルータ１１Ｓは，送信側通信ネットワ
ークＡ，ＢまたはＣ（または入側ルータ１１に接続され
た図示しないコンピュータ端末）からパケットを受信す
ると，そのパケットに対してＴＥを実行し，ＴＥに基づ
いて設定された経路（パス，ルート）上の隣接した中継
ルータ１１Ｒに送信するものである。中継ルータ１１Ｒ
は，入側ルータ１１Ｓと出側ルータ１１Ｄとの間に配置
され，入側ルータ１１Ｓからのパケットを中継して出側
ルータ１１Ｄに渡すものである。出側ルータ１１Ｄは，
入側ルータ１１Ｓから中継ルータ１１Ｒを介して送信さ
れてきたパケットを受信側通信ネットワークＤまたはＥ
（または出側ルータ１１Ｄに接続された図示しないコン
ピュータ端末）に送信するものである。

【００２２】なお，ここでも，ルータを入側ルータ１１
Ｓと，出側ルータ１１Ｄと，中継ルータ１１Ｒとに分け
たのはＴＥを説明するための便宜上のためであり，たと
えば，入側ルータ１１Ｓが出側ルータとなる場合もある
し，出側ルータ１１Ｄが入側ルータとなる場合もある。
また，以下では，これらの入側ルータ１１Ｓ，出側ルー
タ１１Ｄ，および中継ルータ１１Ｒを区別しない場合に
は，単に「ルータ１１」と総称することとする。

【００２３】ルータ１１間には，各ルータを接続する物
理的な「通信路」（ないしは「伝送路」）としてのリン
クが設けられている。たとえば，入側ルータ１１Ｓに
は，隣接する３つの中継ルータ１１Ｒとの間に，３つの
リンクＬ１〜Ｌ３がそれぞれ接続されている。

【００２４】このように，入側ルータ１１Ｓは，外部の
送信側通信ネットワークＡ，ＢおよびＣ（ならびに入側
ルータ１１Ｓに接続されたコンピュータ端末）から送信
されてきたパケットに対してＴＥを実行する始点とな
り，出側ルータ１１Ｄは，ＴＥの終点となる。したがっ
て，入側ルータ１１Ｓから出側ルータ１１Ｄまでの区間
は，「ＴＥ区間」と呼ばれることがある。

【００２５】通信ネットワーク１は，本実施の形態で
は，ラベル・スイッチ技術の一例としてのＭＰＬＳ（Mu
lti-Protocol Label Switching）を用いて経路を設定す
るように構成されている。このため，入側ルータ１１
Ｓ，出側ルータ１１Ｄ，および中継ルータ１１Ｒは，ラ
ベル・スイッチ・ルータ（Label Switch Router：以下
「ＬＳＲ」という。）として構成されている。

【００２６】ＭＰＬＳは，ＯＳＩ参照モデルにおけるレ
イヤ３のインターネット・プロトコルのルーティング処
理と，ＡＴＭやフレーム・リレー等のレイヤ２のスイッ
チング処理とを融合させる技術である。ＬＳＲは，パケ
ット転送（パケット交換）情報として，ＩＰアドレスよ
りも下位のレイヤの情報である「ラベル」を使用する。
ＡＴＭスイッチをＬＳＲのパケット転送エンジン（ラベ
ル・スイッチ・エンジン）に使用する場合には，ラベル
としてＶＰＩ／ＶＣＩ（Virtual Path Identifier／Vir
tual Connection Identifier）が使用される。すなわ
ち，ＩＰアドレスがラベル（ＶＰＩ／ＶＣＩ）にマッピ
ングされ，ラベルを用いてパケット転送が行われる。

【００２７】ＭＰＬＳでは，ＬＳＰ（Label Switched P
ath）と呼ばれるあらかじめ設定された経路（仮想コネ
クション）上でパケットを転送する。このＬＳＰは，Ｏ
ＳＰＦのような既存のルーティング・プロトコルにより
定められた経路に沿って設定することもできるし，既存
のルーティング・プロトコルによる経路とは独立に設定
することもできる。また，宛先（ルータまたはコンピュ
ータ端末）まで，複数のＬＳＰを設定することもでき
る。

【００２８】したがって，複数のＬＳＰを既存のルーテ
ィング・プロトコルとは独立に設定し，これらのＬＳＰ
間で負荷（トラフィック）の分散を行うことにより，Ｔ
Ｅが可能となる。

【００２９】また，ＭＰＬＳでは，最初から複数のＬＳ
Ｐを設定しておくのではなく，通信ネットワーク１内の
トラフィック量の状態を随時監視しておき，ある経路の
トラフィック量が多くなった場合に，同じ宛先に向かう
別の経路を検索して新たなＬＳＰを設定し，このＬＳＰ
にトラフィックを分散する制御も可能である。これによ
っても，通信ネットワークのトラフィックの状態に応じ
たダイナミックなＴＥが可能となる。

【００３０】ＬＳＰは，１本のリンク内に複数個設定す
ることができる。たとえば，１００［Ｍｂｐｓ（Ｍビッ
ト／秒）］の帯域を有する１本のリンク内には，それぞ
れ２０［Ｍｂｐｓ］のＬＳＰを５個設定することができ
る。

【００３１】ＬＳＰの設定には，たとえば，ＲＳＶＰ
（Resource Reservation Protocol）またはこれを拡張
したＲＳＶＰ−ｔｕｎｎｅｌを用いて，経路上のリンク
の帯域を予約することにより行うことができる。

【００３２】通信ネットワーク１では，このＬＳＰによ
る経路（ラベル・スイッチ・パス，ＡＴＭにおける仮想
コネクション）として，図１に示すように，３つの経路
２１〜２３があらかじめ設定され，または，動的に生成
されるものとする。すなわち，入側ルータ１１Ｓは，パ
ケットを送信するための３つの経路２１〜２３を有す
る。

【００３３】各経路２１〜２３は，１または２以上のリ
ンク内に設けられたＬＳＰから構成される。また，各経
路２１〜２３を構成するリンクは，すべて異なるリンク
とは限らず，その一部または全部は同一リンク内に設け
られた，異なるＬＳＰにより構成される場合もある。

【００３４】入側ルータ１１Ｓは，ＴＥ区間外にある送
信側通信ネットワークＡ，ＢおよびＣとの境界に位置
し，これらの送信側通信ネットワークＡ，ＢまたはＣか
ら送信されてきたパケットにラベルを付加し，中継ルー
タ１１Ｒに送信する。中継ルータ１１Ｒは，ラベルが付
加されたパケットをラベル交換して，出側ルータ１１Ｄ
に向けて転送する。したがって，中継ルータ１１Ｒは，
パケットのＩＰアドレスのルーティング・エントリを検
索することなく，ラベル情報だけでパケットの転送（ラ
ベル・スイッチ転送）を行うことができる。出側ルータ
１１Ｄは，ＴＥ区間外にある受信側通信ネットワークＤ
およびＥとの境界に位置し，送信されてきたパケットか
らラベルを取り除き，受信側通信ネットワークＤまたは
Ｅ（または出側ルータ１１Ｄのコンピュータ端末）にこ
のパケットを送信する。なお，通信ネットワーク１は，
前述したように，ＡＴＭを採用しているので，ここでい
うラベルはＶＰＩ／ＶＣＩとなり，またパケットはＡＴ
Ｍセルとして転送されることとなる。

【００３５】通信ネットワーク１のトラフィックの状態
に応じて，ＬＳＰによる経路を設定し，トラフィックの
負荷分散を行うために，各ルータ１１は，自己に接続さ
れている各リンクおよび各リンク内の各ＬＳＰのトラフ
ィックに関する情報（以下「トラフィックに関する情
報」を単に「トラフィック情報」という。）を交換す
る。このトラフィック情報の交換には，本実施の形態で
は，ＯＳＰＦ（Open Shortest Path First）における特
殊なＬＳＡ（リンク状態広告：Link State Advertiseme
nt）であるオペークＬＳＡ（Opaque Link State Advert
isement）が使用される。

【００３６】オペークＬＳＡは，その中に含むことがで
きる情報については，後述するＬＳＡヘッダおよびＬＳ
Ｒインタフェース情報を除いて特に規定がなく，自由に
使用できる領域を有する。また，オペークＬＳＡは，そ
の伝播（送信）手法としてフラッディング（Flooding）
が使用される点を除いて，いつ伝播するかについても規
定がなく，各ルータが所望の時に伝播することができ
る。しかも，オペークＬＳＡは，ＯＳＰＦというプロト
コルに従っているので，インターネット等の通信ネット
ワークにおいて使用することができる。したがって，自
由に使用できる領域にトラフィック情報を含めて伝播す
ることにより，インターネット等の既存の通信ネットワ
ーク上の各ルータ間でトラフィック情報を交換すること
ができる。

【００３７】＜ルータ１１の構成＞図２は，ルータ１１
を代表して，入側ルータ１１Ｓの構成を示すブロック図
である。入側ルータ１１Ｓは，処理装置３０と，記憶装
置３２と，インタフェース装置４１〜４６とを備えてい
る。また，入側ルータ１１Ｓにコンピュータ端末が接続
されている場合には，このコンピュータ端末用のインタ
フェース装置４７が設けられる。なお，中継ルータ１１
Ｒおよび出側ルータ１１Ｄは，インタフェース装置の個
数が異なる場合があることと，その接続先が異なる場合
があることとを除いて，入側ルータ１１Ｓと同様の構成
を有するので，ここでは，入側ルータ１１Ｓの構成につ
いてのみ説明することとする。

【００３８】記憶装置３２は，ハードディスク装置等で
構成され，リンク状態データベース３２ａおよびオペー
クＬＳＡ用データベース３２ｂを含んでいる。リンク状
態データベース３２ａは，ＯＳＰＦで規定されている，
リンク状態が格納されるデータベースである。オペーク
ＬＳＡ用データベース３２ｂは，オペークＬＳＡが格納
されるデータベースであり，その詳細な説明は後述す
る。

【００３９】処理装置３０は，図示しないＣＰＵ，メモ
リ（ＲＡＭおよびＲＯＭ）等を備えている。この処理装
置３０は，その内部のメモリまたは記憶装置３２に記憶
されたプログラムに従って，記憶装置３２およびインタ
フェース装置４１〜４６（４７）の制御を行うととも
に，経路の設定，トラフィックの状態に応じた負荷分散
制御，パケット（ＡＴＭセル）の送受信，オペークＬＳ
Ａの作成および送受信，受信したＬＳＡによるリンク状
態データベースの更新，受信したオペークＬＳＡによる
オペークＬＳＡ用データベースの更新等の処理を行う。

【００４０】インタフェース装置４１〜４６（４７）
は，入出力バッファを備え，処理装置３０の制御の下，
接続された各リンクを転送されるパケット（ＡＴＭセ
ル）の入出力処理を行う。

【００４１】なお，パケット（ＡＴＭセル）の送受信
（ＡＴＭセルの生成，ラベル（ＶＰＩ／ＶＣＩ）のスイ
ッチングを含む。）は，ハードウェア回路により構成さ
れたハードウェア交換機をルータ１１Ｓ内に設けて，こ
の交換機により行うことができる。

【００４２】＜オペークＬＳＡのデータ構造＞トラフィ
ック情報は，前述したように，ＯＳＰＦにおけるオペー
クＬＳＡを用いてルータ１１間をフラッディングされ
る。このオペークＬＳＡは，図３に示すデータ構造を有
する。図中，最上部に示す数字はビット番号である。し
たがって，この図３では，オペークＬＳＡを横方向に３
２ビット（４バイト）単位で整列して示している。

【００４３】オペークＬＳＡは，ＬＳＡヘッダおよびＬ
ＳＲインタフェース情報のフィールドを除いては，特に
規定がなく，自由に使用できるフィールド（図３のリン
ク情報のフィールド）を有する。したがって，本実施の
形態では，図３に示すデータ構造により，トラフィック
情報がルータ１１間をフラッディングされる。

【００４４】オペークＬＳＡは，大きく分けると，ＬＳ
Ａヘッダとオペーク・フィールドとに分けられる。

【００４５】ＬＳＡヘッダは，２０バイトからなり，通
常のＬＳＡ（オペークＬＳＡ以外のＬＳＡ）と同様のデ
ータ構造を有する。すなわち，ＬＳＡヘッダは，リンク
状態エージ（Link State Age），オプション（Optio
n），リンク状態タイプ（Link State Type：ＬＳ Typ
e），オペーク・タイプ（Opaque Type），オペーク識別
子（Opaque Id），広告ルータ（Advertising Route
r），リンク状態番号（LS Sequence Number），リンク
状態チェック・サム（LS Checksum），および長さ（Len
gth）の各フィールドから構成されている。

【００４６】「リンク状態エージ」は，２バイトからな
り，このオペークＬＳＡの寿命（秒単位），すなわち有
効期限を示している。

【００４７】「オプション」は，１バイトからなり，ル
ータがオプション機能をサポートするように設定した
り，そのサポート・レベル他のルータに伝えることを可
能にするフィールドである。この「オプション」フィー
ルドの第２ビットは，Ｏビットと呼ばれ，そのルータが
オペークＬＳＡをサポートしている（Opaque-capable）
かどうかを示している。

【００４８】「リンク状態タイプ」は，１バイトからな
り，ＬＳＡのタイプを示している。オペークＬＳＡの場
合に，リンク状態タイプの値は，９，１０または１１と
なり，この値によってフラッディングされる範囲が異な
る。

【００４９】この値が９の場合には，そのオペークＬＳ
Ａのフラッディング範囲（FloodingScope）は“Link-lo
cal”であり，ローカル・ネットワーク内とされる。１
０の場合には，フラッディング範囲は“Area-local”で
あり，そのオペークＬＳＡは，接続しているエリアのボ
ーダ（境界）を超えてフラッディングされることはな
い。１１の場合には，フラッディング範囲は“Equivale
nt to AS-external LSA”であり，そのオペークＬＳＡ
は，ＡＳ（Autonomous System）全体に亘ってフラッデ
ィングされる。特に（１）すべての通過領域（Transit
area）にフラッディングされ，（２）バックボーン（ba
ckbone）からスタブ領域（stub area）にフラッディン
グされず，（３）あるルータから，そのルータに接続さ
れているスタブ領域に向けては生成されない。

【００５０】「広告ルータ」は，４バイトとからなり，
このオペークＬＳＡを作成し，広告したルータのＩＰア
ドレスが置かれるフィールドである。リンク状態番号お
よびリンク状態チェック・サムは，同一の広告ルータが
作成した２以上のオペークＬＳＡがある場合に，いずれ
が最新（時間的に最も後）のものであるかを判定する際
に用いられる。「長さ」は，２バイトからなり，このオ
ペークＬＳＡの長さ（バイト数）を示している。

【００５１】「オペーク・フィールド」は，ＬＳＲイン
タフェース情報と，そのルータ１１に接続されたリンク
の個数分設けられたリンク情報とから構成されている。

【００５２】ＬＳＲインタフェース情報は，４バイトか
らなり，上位２バイトのＥ＿Ｂフィールドと，下位２バ
イトのリンク・カウントのフィールドとから構成されて
いる。「Ｅ＿Ｂフィールド」は，そのルータがエリア・
ボーダ・ルータかＡＳバウンダリ・ルータかを示す。
「リンク・カウント」は，そのルータに接続されている
リンクの個数を示す。

【００５３】「リンク情報」は，リンク識別子（Link I
d），ネット・マスク，コネクション・タイプ，ＬＳＰ
カウント，およびリンク・データの各フィールドから構
成されている。

【００５４】「リンク識別子」は，４バイトからなり，
そのリンクが接続されている隣接ルータまたはコンピュ
ータ端末のＩＰアドレスを示す。「ネット・マスク」
は，４バイトからなり，リンク識別子の（サブ）ネット
・マスクを示す。「コネクション・タイプ」は，１バイ
トからなり，そのリンクの接続先がルータか，コンピュ
ータ端末か等を示す。ＬＳＰカウントは，１バイトから
なり，そのリンクに設けられたＬＳＰの個数を示す。こ
の値は，通信時に設けられるＬＳＰの個数が変化するこ
とに伴い動的に変化する。

【００５５】「リンク・データ」は，複数のデータから
構成されている。図４は，リンク・データのデータ構造
を示している。リンク・データは，そのリンクのリンク
統計情報と，そのリンク上に形成された各ＬＳＰのＬＳ
Ｐ統計情報とを有する。これらのリンク統計情報および
ＬＳＰ統計情報は，本発明に係る「トラフィックに関す
る情報（トラフィック情報）」の一例である。

【００５６】「リンク統計情報」は，平均使用率（Ave
Utilization）と，出力リンク廃棄パケット数（Loss）
と，出力リンク帯域（Bwl）との各フィールドを有す
る。

【００５７】「平均使用率」は，４バイトからなり，そ
のリンクの平均使用率を示す。この平均使用率は，以下
の式により計算される。

【００５８】 Ave Utilization＝α×CUTY（ｎ）＋（１−α）×CUTY（ｎ−１） …（１） この式（１）は，移動平均（moving average）法による
計算式である。ここで，αは平滑化（スムージング）係
数である。CUTY（ｎ）は現在（すなわち時刻ｎ）のリン
ク使用率を，CUTY（ｎ−１）は１時刻前（すなわち時刻
（ｎ−１））のリンク使用率を，それぞれ示し，以下の
式により求められる。

【００５９】 CUTY（ｎ）＝〔時刻（ｎ−１）から時刻ｎまでのリンクへの出力パケット数〕 ／〔出力リンク帯域〕 …（２） なお，平均使用率は，観測されたCUTYの最大値とするこ
ともでき，この場合に，平均使用率は以下の式で表され
る。

【００６０】 Ave Utilization＝ｍａｘ（観測値） …（３） 「出力リンク廃棄パケット数」は，４バイトからなり，
そのリンクの廃棄された出力パケットの合計数を示す。
出力リンク廃棄パケット数は，以下の式により計算され
る。

【００６１】 Loss（ｎ）＝Loss（ｎ−１）＋NLoss …（４） ここで，Loss（ｎ−１）は，１時刻前の時刻（ｎ−１）
までの出力リンク廃棄パケットの合計数であり，NLoss
は，時刻（ｎ−１）から時刻ｎまでに生じた出力リンク
廃棄パケット数である。

【００６２】「出力リンク帯域」は，４バイトからな
り，出力リンクの帯域［ｂｐｓ（ビット／秒）］を示
す。この出力リンク帯域は，各ルータ１１の処理装置３
０のメモリまたは記憶装置３２にあらかじめ記憶され，
記憶された値がオペークＬＳＡの該フィールドに書き込
まれるようになっている。

【００６３】「ＬＳＰ統計情報」は，ＬＳＰ識別子（Ls
p id）と，ＬＳＰ＿ＣＯＳクラス（Cos lsp）と，ＬＳ
Ｐ平均使用率（Ave Utility lsp）と，ＬＳＰ出力廃棄
パケット数（Loss lsp）と，ＬＳＰ帯域（Bwl lsp）と
の各フィールドを有する。

【００６４】「ＬＳＰ識別子」は，２バイトからなり，
そのＬＳＰの識別子を示す。「ＬＳＰ＿ＣＯＳクラス」
は，２バイトからなり，そのＬＳＰのＣＯＳクラスを示
している。

【００６５】「ＬＳＰ平均使用率」は，４バイトからな
り，そのＬＳＰの平均使用率を示し，前記式（１）およ
び（２）において，出力リンクを，リンクではなくＬＳ
Ｐに置換した式により求められる。また，前記式（３）
と同様に，そのＬＳＰにおける観測値の最大値とするこ
ともできる。

【００６６】「ＬＳＰ出力廃棄パケット数」は，４バイ
トからなり，そのＬＳＰの廃棄された出力パケットの合
計数を示し，前記式（４）において，出力リンクをＬＳ
Ｐに置換することにより求められる。

【００６７】「ＬＳＰ帯域」は，そのＬＳＰが設定され
る際に割り当てられた帯域［ｂｐｓ］を示している。こ
のＬＳＰ帯域は，ＬＳＰの設定時に，そのＬＳＰが設定
されるリンクを出力リンクとするルータ１１の処理装置
３０のメモリまたは記憶装置３２に記憶され，記憶され
た値がオペークＬＳＡの該フィールドに書き込まれるよ
うになっている。

【００６８】これまでに述べたリンク平均使用率，出力
リンク廃棄パケット数，ＬＳＰ平均使用率，およびＬＳ
Ｐ出力廃棄パケット数は，たとえば，各ルータ１１のオ
ペレーティング・システム（ＯＳ：たとえばＬｉｎｕ
ｘ）がリアルタイムで収集し，管理しているシステム状
態（ＣＰＵ負荷，転送パケット数等）を表すデータ（フ
ァイル）に基づいて求められる。

【００６９】図５および図６は，ルータ１１ＳのＯＳが
リアルタイムで収集／管理しているシステム状態のデー
タの一例を示している。図５はルータ１１Ｓに設けられ
た記憶装置３２のディレクトリ“/proc/net/dev”にあ
るファイルの内容を，図６は記憶装置３２のディレクト
リ“/proc/atm/device”にあるファイルの内容を，それ
ぞれテーブル（表）形式により示している。

【００７０】これらの図に示す数値は，ある時刻のデー
タの一例である。また，これらの数値は，ルータ１１Ｓ
に電源を投入してからの積算値を示し，ＯＳがリアルタ
イム（一定時間間隔Δｔ）で収集しているので，時々刻
々と変化するものである。これらの数値は積算値である
ので，たとえば時刻（ｎ−１）にこのテーブルを参照し
た時の値と時刻ｎにこのテーブルを参照した時の値との
差分を求めることにより，時刻（ｎ−１）から時刻ｎま
での１時刻の間の変化量を求めることができる。

【００７１】図５に示すテーブルの上半分は，“Receiv
e”の文字が示すようにルータ１１Ｓの受信に関するデ
ータを示し，下半分は，“Transmit”の文字が示すよう
にルータ１１Ｓの送信に関するデータを示す。以下，テ
ーブルの上半分を「受信テーブル」といい，下半分を
「送信テーブル」という。

【００７２】受信テーブルおよび送信テーブルにおける
“interface”は，ルータ１１Ｓに接続されているイン
タフェースの種類を示している。このインタフェースに
は，“lo”，“eth0”，“eth1”，“eth2”，“atm
0”，“atm1”，および“atm2”がある。

【００７３】“lo”は，“loopback device”の略であ
り，ルータ１１Ｓに接続されたコンピュータ端末（図1
には図示略）とのインタフェースを意味する。“eth0”
〜“eth2”は，イーサネットとのインタフェースを意味
する。ルータ１１Ｓには，図１に示すように，送信側通
信ネットワーク（イーサネット）Ａ〜Ｃが接続されてい
るので，“eth0”は送信側通信ネットワークＡとの，
“eth1”は送信側通信ネットワークＢとの，“eth2”は
送信側通信ネットワークＣとの，各インタフェースを意
味する。

【００７４】“atm0”〜“atm2”は，ＡＴＭとのインタ
フェースを意味する。図１に示すように，入側ルータ１
１Ｓには，ＡＴＭネットワークで構成された通信ネット
ワーク１の３つのリンクＬ１〜Ｌ３が接続されているの
で，“atm0”はリンクＬ１との，“atm1”はリンクＬ２
との，“atm2”はリンクＬ３との各インタフェースを意
味する。

【００７５】受信テーブルおよび送信テーブルの“byte
s”は，それぞれ，各インタフェース（interface）から
受信したバイト数および各インタフェースへ送信したバ
イト数を示している。たとえば，インタフェース“lo”
のデータによると，入側ルータ１１Ｓは，コンピュータ
端末から６０８４バイトのデータを受信し，同じバイト
数のデータをインタフェース“lo”に送信していること
が示されている。

【００７６】受信テーブルおよび送信テーブルの“pack
ets”は，それぞれ，各インタフェース（interface）か
ら受信したパケット数および各インタフェースへ送信し
たパケット数を示している。たとえば，インタフェース
“eth0”のデータによると，ルータ１１Ｓは，送信側通
信ネットワークＡから３２４個のパケットを受信し，２
６７個のパケットを送信したことが示されている。

【００７７】受信テーブルおよび送信テーブルの“err
s”は，それぞれ，各インタフェースからの受信パケッ
トのエラー数および各インタフェースへの送信パケット
のエラー数を示している。

【００７８】受信テーブルおよび送信テーブルの“dro
p”は，それぞれ，各インタフェースからの受信パケッ
トの廃棄数および各インタフェースへの送信パケットの
廃棄数を示している。

【００７９】受信テーブルおよび送信テーブルの“fif
o”は，それぞれ，受信処理待ちのパケット数（キュー
（ＦＩＦＯ）の長さ）および送信処理待ちのパケット数
（キュー（ＦＩＦＯ）の長さ）を示している。

【００８０】受信テーブルの“frame”は受信フレーム
数を，“compressed”は圧縮パケット数を，“multicas
t”は受信マルチキャスト・パケット数をそれぞれ示し
ている。

【００８１】送信テーブルの“colls”はイーサネット
（ＣＳＭＡ／ＣＤ方式）における衝突（collision）の
発生数を，“carrier”はイーサネットにおけるキャリ
ア検出数を，“compressed”は圧縮パケット数を，それ
ぞれ示している。

【００８２】図６に示すテーブルの“interface type”
は，通信ネットワーク１のリンクＬ１〜Ｌ３の３つのＡ
ＴＭインタフェースのタイプを示し，“0 eni”は，イ
ンタフェース名“eni”のNo.1であり，“1 eni”は，イ
ンタフェース名“eni”のNo.2であり，“2 eni”は，イ
ンタフェース名“eni”のNo.３である。

【００８３】“ESI/"MAC addr"”は，ＭＡＣ（Media Ac
cess Control）アドレスを示している。“AAL(Tx, err,
Rx, err, drop)”は，ＡＴＭアダプテーション・レイ
ヤ（Adaptation Layer）のパケットに関する統計情報を
示している。“Tx”は送信パケット数を，左側の“er
r”は送信エラー数を，“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に達している場合
には（ステップＳ１２でＹＥＳ），他のルータからのオ
ペークＬＳＡの受信の有無に関係なく，自己のルータの
トラフィックの状態を格納したオペークＬＳＡが作成さ
れ，送信される（ステップＳ５２〜Ｓ６４）。なお，ス
テップＳ５２〜Ｓ６０の処理は，ステップＳ２６〜Ｓ３
４の処理とそれぞれ同じであり，ステップＳ６２〜Ｓ６
４の処理は，ステップＳ２２〜Ｓ２４の処理と同じであ
る。その後，処理は，ステップＳ５０に戻る。

【０１０９】＜オペークＬＳＡ用データベースのデータ
構造およびその更新処理＞図１２は，ルータ１１の記憶
装置３２に設けられたオペークＬＳＡ用データベース３
２ｂのデータ構造を示す。

【０１１０】オペークＬＳＡ用データベース３２ｂは，
ハッシュ・テーブル５０と，各ルータ（自ルータを含
む。）１１のオペークＬＳＡを有するオペークＬＳＡデ
ータベース構造体（以下「ＯＬＤＢ構造体」という。）
５１ａ〜５１ｃ，５２ａ〜５２ｄ，５３ａおよび５３ｂ
等とから構成されている。

【０１１１】ハッシュ・テーブル５０は，複数の記憶セ
ルを備え，各記憶セルは，受信されたオペークＬＳＡの
ＬＳＡヘッダにある「広告ルータ」の値（すなわち広告
ルータのＩＰアドレス）をハッシュしたハッシュ値ｈ１
〜ｈ３等をアドレスとしてアクセスされる。各記憶セル
には，ＯＬＤＢ構造体へのポインタが格納される。たと
えば，ハッシュ値ｈ１に対応する記憶セルには，ＯＬＤ
Ｂ構造体５１ａへのポインタが，ハッシュ値ｈ２に対応
する記憶セルには，ＯＬＤＢ構造体５２ａへのポインタ
が，ハッシュ値ｈ３に対応する記憶セルには，ＯＬＤＢ
構造体５３ａへのポインタが，それぞれ格納されてい
る。図示しない他のハッシュ値に対応する記憶セルに
も，図示しない他のＯＬＤＢ構造体へのポインタが格納
されている。

【０１１２】ＯＬＤＢ構造体は，受信したオペークＬＳ
Ａの内容（図３および図４に示す各フィールド）を含む
とともに，隣接する次のＯＬＤＢ構造体へのポインタ
（たとえばＯＬＤＢ構造体５１ａは次のＯＬＤＢ構造体
５１ｂへのポインタ），ルートまでの距離（コスト）の
計算に必要なフィールド等を含んでいる。１つのＯＬＤ
Ｂ構造体には，１つのルータ１１が対応している。

【０１１３】ハッシュ・テーブル５０のハッシュ値とし
ては，たとえば，ＬＳＡヘッダの「広告ルータ」値（Ｉ
Ｐアドレス）を整数とみなし，この整数を素数２５１で
除算した商（整数値）が用いられる。この場合に，ハッ
シュ・テーブル５０は，２５１個の記憶セルを有し，通
信ネットワーク１内の複数のルータ１１は，２５１個の
グループに分類されることとなる。そして，２５１個の
グループに分類された各グループに属する複数のルータ
のＯＬＤＢ構造体は，たとえばＯＬＤＢ構造体５１ａ〜
５２ｃのように，ポインタにより連結される。

【０１１４】なお，同じグループに属する複数のルータ
は，ＩＰアドレスが近いので，地理的にも近い位置に配
置されていることが多い。

【０１１５】このように，ハッシュ・テーブルを用いる
ことにより，複数のルータをグループに分類することが
できるので，後述するように，特定のルータのＯＬＤＢ
構造体を検索する時に，検索の高速化を図ることができ
る。

【０１１６】図１１は，図７から図１０に示すステップ
Ｓ１８，Ｓ２３，Ｓ３０，およびＳ６４のオペークＬＳ
Ａ用データベースの更新処理の詳細な処理の流れを示す
フローチャートである。この処理は，各ルータ１１の処
理装置３０により実行される。

【０１１７】まず，オペークＬＳＡを格納するＯＬＤＢ
構造体の記憶領域を記憶装置３２内に確保可能かどうか
が判定される（ステップＳ１００）。確保可能である場
合には（ステップＳ１００でＹＥＳ），記憶領域が確保
され（ステップＳ１０２），確保された記憶領域に，受
信したオペークＬＳＡが格納される（ステップＳ１０
４）。

【０１１８】続いて，オペークＬＳＡを受信したルータ
のＩＰアドレスがハッシュされ，このハッシュ値をアド
レスとするハッシュ・テーブル５０の記憶セルが決定さ
れる（ステップＳ１０６）。続いて，決定された記憶セ
ルにポインタにより連結された１または２以上のＯＬＤ
Ｂ構造体の中から，受信されたオペークＬＳＡの発信ル
ータのＩＰアドレスと一致するものがあるかどうかが判
定（すなわち検索）される（ステップＳ１０８）。この
検索では，検索範囲がハッシュ・テーブル５０の１つの
記憶セルに対応するＯＬＤＢ構造体のグループに絞り込
まれているので，高速に検索を行うことができる。

【０１１９】一致するＯＬＤＢ構造体がない場合には
（ステップＳ１１８でＮＯ），受信されたオペークＬＳ
Ａを格納したＯＬＤＢ構造体は，ステップＳ１０６で決
定された記憶セルに連結されたＯＬＤＢ構造体の最後尾
に連結される。たとえば，ハッシュ値が，図１２のハッ
シュ値ｈ１の場合には，受信されたオペークＬＳＡのＯ
ＬＤＢ構造体は，ＯＬＤＢ構造体５１ｃの後ろに連結さ
れ，ＯＬＤＢ構造体５１ｃ内に設けられたポインタに
は，連結された新たなＯＬＤＢ構造体へのポインタが格
納される。

【０１２０】一方，ステップＳ１０８において，一致す
るものがある場合には（ステップＳ１０８でＹＥＳ），
受信されたオペークＬＳＡが最新（時間的に最も後）の
もの（すなわち，最新のトラフィック情報を有するオペ
ークＬＳＡ）かどうかが判定される（ステップＳ１１
０）。

【０１２１】最新でない場合には（ステップＳ１１０で
ＮＯ），受信されたオペークＬＳＡは廃棄され，ステッ
プＳ１０２で確保された記憶領域は解放される（ステッ
プＳ１１２）。一方，最新である場合には（ステップＳ
１１０でＹＥＳ），この最新のＯＬＤＢ構造体が，デー
タベース３２ｂ内に既にある古いＯＬＤＢ構造体と入れ
替えられる（ステップＳ１１４）。たとえば，図１２の
ＯＬＤＢ構造体５１ｂが，受信された新たなオペークＬ
ＳＡを有するＯＬＤＢ構造体（「ＯＬＤＢ構造体ｘ」と
する。）によって入れ替えられる場合には，この同じ位
置にＯＬＤＢ構造体ｘが挿入される。あるいは，ＯＬＤ
Ｂ構造体５１ｃをＯＬＤＢ構造体５１ａの直後に連結す
るとともに，ＯＬＤＢ構造体５１ｃの直後にＯＬＤＢ構
造体ｘを連結することもできる。

【０１２２】その後，古いオペークＬＳＡのＯＬＤＢ構
造体の記憶領域は解放され（ステップＳ１１６），処理
は終了する。

【０１２３】＜負荷分散の一例＞最後に，オペークＬＳ
Ａ用データベース３２ｂに格納された各ルータ１１のト
ラフィック情報に基づいて行われる負荷分散の一例につ
いて説明する。

【０１２４】経路１，２，３（図１参照）の各論理帯域
（ＬＳＰの帯域）［ｂｐｓ］をそれぞれ１０Ｍ，８Ｍ，
２Ｍとする。

【０１２５】入側ルータ１１Ｓ（処理装置３０）は，Ｔ
Ｅによる負荷分散制御を行うために，まず経路１，２，
３のそれぞれの実効負荷を算出する。ここで，「実効負
荷」とは，リンクの使用率とこのリンクにおけるパケッ
ト廃棄率（パケット損失率）とから計算される実効的な
使用率である。本来的には，リンクの実際の負荷を計測
すればよいが，実際には，ルータ１１によって，その内
部が多段スイッチ構成になっている場合があり，この場
合には，直接的に負荷を計測することは困難であること
から，この実効負荷が用いられる。

【０１２６】この実効負荷は，経路ｉの実効負荷をρ e
ffective 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 ｊ …（１１） 関数ｆは，パケットの廃棄が発生した場合に，負荷を高
めに計算するように修正するための関数である。これ
は，パケットの廃棄がない場合には，リンクの負荷ρ p
ath ｉと実効負荷とは一致するが，パケットの廃棄が発
生すると，負荷を高めに修正する必要があるためであ
る。ρ ceilingは，実効負荷の上限値である。

【０１３０】今，経路１，２，３の実効負荷を，それぞ
れρ effective path １＝０．５，ρ effective path
２＝０．２，ρ effective path ３＝０．３とすると，
経路１，２，３の実トラフィック［ｂｐｓ］は，それぞ
れ１０Ｍ×０．５＝５Ｍ，８Ｍ×０．２＝１．６Ｍ，２
Ｍ×０．３＝０．６Ｍとなる。

【０１３１】続いて，ルータ１１Ｓ（処理装置３０）
は，負荷調整（Load Adjusting）を行う。まず，経路
１，２，３のすべてを仮想的な１つのパイプとみなし，
このパイプの平均使用率ρave effectiveが以下の式に
より求められる。

【０１３２】 ρave effective＝Σ（ρ effective path ｉ×LBW path ｉ）／ΣLBW path ｉ …（１２） ここで，LBW path ｉは，経路ｉの論理帯域である。

【０１３３】式（１２）を上記例に当てはめると， ρave effective＝（５Ｍ＋１．６Ｍ＋０．６Ｍ）／
（１０Ｍ＋８Ｍ＋２Ｍ）＝０．３６ となる。

【０１３４】次に，経路間で移動する実効帯域ΔEBW pa
th ｉ［ｂｐｓ］が以下の式により算出される。

【０１３５】 ΔEBW path ｉ＝（ρave effective−ρ effective path ｉ×LBW path ｉ） …（１３） これを経路１，２，３のそれぞれについて算出すると，
以下のようになる。

【０１３６】経路１の移動する実効帯域ΔEBW PATH1＝
（０．３６−０．５）×１０Ｍ＝−１．４Ｍ 経路２の移動する実効帯域ΔEBW PATH2＝（０．３６−
０．２）×８Ｍ＝＋１．２８Ｍ 経路3の移動する実効帯域ΔEBW PATH3＝（０．３６−
０．３）×２Ｍ＝＋０．１２Ｍ なお，各経路の移動する実効帯域の総和は，−１．４Ｍ
＋１．２８Ｍ＋０．１２Ｍ＝０となる。

【０１３７】この計算結果に基づいて負荷調整を行う
と，経路１については，５Ｍ−１．４Ｍ＝３．６Ｍ，経
路２については，１．６Ｍ＋１．２８Ｍ＝２．８８Ｍ，
経路３については，０．６Ｍ＋０．１２Ｍ＝０．７２Ｍ
となり，経路１，２，３について，３．６×Ｇｒ：２．
８８×Ｇｒ：０．７２×Ｇｒの比で負荷分散（トラフィ
ックの分配）の変更を行えばよいこととなる。なお，Ｇ
ｒは，負荷調整係数である。

【０１３８】（付記１） 通信される情報を送信，受信
または中継する複数のノードと，該複数のノードを接続
する通信路とを有する通信ネットワークにおける前記ノ
ードに設けられ，前記通信路のトラフィックに関する情
報を収集するトラフィック情報収集装置であって，自己
のノードに接続された通信路のトラフィックに関する情
報を収集するトラフィック情報収集部と，前記通信ネッ
トワーク上の通信プロトコルで使用されるメッセージに
より，前記トラフィック情報収集部により収集された前
記自己のノードに接続された通信路のトラフィックに関
する情報を他のノードに送信するトラフィック情報送信
部と，他のノードから送信されてきた該他のノードに接
続された通信路のトラフィックに関する情報を受信する
トラフィック情報受信部と，前記トラフィック情報収集
部により収集された前記自己のノードに接続された通信
路のトラフィックに関する情報と，前記トラフィック情
報受信部により受信された前記他のノードに接続された
通信路のトラフィックに関する情報とを記憶するトラフ
ィック情報記憶部と，を備えているトラフィック情報収
集装置。

【０１３９】（付記２） 付記１において，前記トラフ
ィック情報送信部は，あらかじめ定められた一定時間間
隔ごとに前記自己のノードに接続された通信路のトラフ
ィックに関する情報を送信する，トラフィック情報収集
装置。

【０１４０】（付記３） 付記１において，前記トラフ
ィック情報送信部は，前記他のノードに接続された通信
路のトラフィックに関する情報が該他のノードから送信
されてきた時に，前記自己のノードに接続された通信路
のトラフィックに関する情報を送信する，トラフィック
情報収集装置。

【０１４１】（付記４） 付記１において，前記トラフ
ィック情報送信部は，あらかじめ定められた一定時間間
隔ごとに前記自己のノードに接続された通信路のトラフ
ィックに関する情報を送信するとともに，前記他のノー
ドに接続された通信路のトラフィックに関する情報が該
他のノードから送信されてきた時に，前記自己のノード
に接続された通信路のトラフィックに関する情報を送信
する，トラフィック情報収集装置。

【０１４２】（付記５） 通信される情報を送信，受信
または中継する複数のノードと，該複数のノードを接続
する通信路とを有する通信ネットワークにおける前記ノ
ードに設けられ，前記通信路のトラフィック情報を収集
するトラフィック情報収集装置であって，自己のノード
に接続された通信路のトラフィックに関する情報を収集
するトラフィック情報収集部と，前記トラフィック情報
収集部により収集された前記自己のノードに接続された
通信路のトラフィックに関する情報と，他のノードから
送信されてきた該他のノードに接続された通信路のトラ
フィックに関する情報とを記憶するトラフィック情報記
憶部と，を備えているトラフィック情報収集装置。

【０１４３】（付記６） 付記１から５のいずれか１つ
において，前記他のノードから送信されてきたトラフィ
ックに関する情報を，送信されてきた通信路を除く他の
通信路に転送するトラフィック情報転送部をさらに備え
ている，トラフィック情報収集装置。

【０１４４】（付記７） 付記１から６のいずれか１つ
において，前記トラフィックに関する情報が，トラフィ
ックを出力する通信路のトラフィックに関する情報であ
る，トラフィック情報収集装置。

【０１４５】（付記８） 付記１から７のいずれか１つ
において，前記トラフィック情報収集部が，あらかじめ
定められた一定時間間隔ごとに前記自己のノードに接続
された通信路のトラフィックに関する情報を収集する，
トラフィック情報収集装置。

【０１４６】（付記９） 付記１から８のいずれか１つ
において，前記トラフィックに関する情報が，通信路の
平均使用率，通信路の廃棄されたパケット数，および通
信路の帯域，ならびに，通信路を論理的な通信路に分割
した場合における該論理的な通信路の平均使用率，廃棄
されたパケット数，および該論理的な通信路の帯域を含
む，トラフィック情報収集装置。

【０１４７】（付記１０） 付記１から９のいずれか１
つにおいて，前記通信プロトコルで使用されるメッセー
ジが，ＯＳＰＦにおけるオペーク・リンク状態広告であ
る，トラフィック情報収集装置。

【０１４８】（付記１１） 付記１から１０のいずれか
１つにおいて，前記ノードがルータである，トラフィッ
ク情報収集装置。

【０１４９】（付記１２） 付記１から１１のいずれか
１つにおいて，前記トラフィック情報収集装置を有する
ノードが，前記通信ネットワークにおけるトラフィック
の負荷分散制御を行うノードである，トラフィック情報
収集装置。

【０１５０】（付記１３） 付記１から１２のいずれか
１つにおいて，前記トラフィック情報記憶部が，ハッシ
ュ・テーブルと，前記各ノードのトラフィックに関する
情報を有する構造体データとを備え，前記ハッシュ・テ
ーブルは，前記各ノードをユニークに識別する情報をハ
ッシュしたハッシュ値をアドレスとする記憶セルを有す
るとともに，各記憶セルには，該記憶セルのハッシュ値
に対応するノードのトラフィックに関する情報を有する
前記構造体データへのポインタが格納されており，前記
構造体データは，同じハッシュ値に対応する他の構造体
データがある場合には，該他の構造体データへのポイン
タをさらに備えている，トラフィック情報収集装置。

【０１５１】（付記１４） 付記１から１３のいずれか
１つにおいて，前記トラフィック情報記憶部は，トラフ
ィックに関する情報を記憶する際に，同じノードのトラ
フィックに関する情報が既に存在する場合には，それら
のうちの時間的に後のトラフィックに関する情報を記憶
する，トラフィック情報収集装置。

【０１５２】（付記１５） 通信される情報を送信，受
信または中継する複数のノードと，該複数のノードを接
続する通信路とを有する通信ネットワークにおける該ノ
ードであって，自己に接続された通信路のトラフィック
に関する情報を収集するトラフィック情報収集部と，前
記通信ネットワーク上の通信プロトコルで使用されるメ
ッセージにより，前記トラフィック情報収集部により収
集された前記自己に接続された通信路のトラフィックに
関する情報を他のノードに送信するトラフィック情報送
信部と，他のノードから送信されてきた該他のノードに
接続された通信路のトラフィックに関する情報を受信す
るトラフィック情報受信部と，前記トラフィック情報収
集部により収集された前記自己のノードに接続された通
信路のトラフィックに関する情報と，前記トラフィック
情報受信部により受信された前記他のノードに接続され
た通信路のトラフィックに関する情報とを記憶するトラ
フィック情報記憶部と，を備えているノード。

【０１５３】（付記１６） 通信される情報を送信，受
信または中継する複数のノードと，該複数のノードを接
続する通信路とを有する通信ネットワークにおける該ノ
ードであって，自己に接続された通信路のトラフィック
に関する情報を収集するトラフィック情報収集部と，前
記トラフィック情報収集部により収集された前記自己の
ノードに接続された通信路のトラフィックに関する情報
と，他のノードから送信されてきた該他のノードに接続
された通信路のトラフィックに関する情報とを記憶する
トラフィック情報記憶部と，を備えているノード。

【０１５４】（付記１７） 通信される情報を送信，受
信または中継する複数のノードと，該複数のノードを接
続する通信路とを有する通信ネットワークにおける前記
ノードで行われる，前記通信路のトラフィックに関する
情報を収集するトラフィック情報収集方法であって，自
己のノードに接続された通信路のトラフィックに関する
情報を収集し，前記通信ネットワーク上の通信プロトコ
ルで使用されるメッセージにより，前記収集された前記
自己のノードに接続された通信路のトラフィックに関す
る情報を他のノードに送信し，他のノードから送信され
てきた該他のノードに接続された通信路のトラフィック
に関する情報を受信し，前記収集された前記自己のノー
ドに接続された通信路のトラフィックに関する情報と，
前記受信された前記他のノードに接続された通信路のト
ラフィックに関する情報とを記憶する，トラフィック情
報収集方法。

【０１５５】（付記１８） 通信される情報を送信，受
信または中継する複数のノードと，該複数のノードを接
続する通信路とを有する通信ネットワークにおける前記
ノードで行われる，前記通信路のトラフィック情報を収
集するトラフィック情報収集方法であって，自己のノー
ドに接続された通信路のトラフィックに関する情報を収
集し，前記収集された前記自己のノードに接続された通
信路のトラフィックに関する情報と，他のノードから送
信されてきた該他のノードに接続された通信路のトラフ
ィックに関する情報とを記憶する，トラフィック情報収
集方法。

【０１５６】（付記１９） 通信される情報を送信，受
信または中継する複数のノードと，該複数のノードを接
続する通信路とを有する通信ネットワークにおける前記
ノードで実行される，前記通信路のトラフィックに関す
る情報を収集するトラフィック情報収集プログラムであ
って，自己のノードに接続された通信路のトラフィック
に関する情報を収集する手順と，前記通信ネットワーク
上の通信プロトコルで使用されるメッセージにより，前
記収集された前記自己のノードに接続された通信路のト
ラフィックに関する情報を他のノードに送信する手順
と，他のノードから送信されてきた該他のノードに接続
された通信路のトラフィックに関する情報を受信する手
順と，前記収集された前記自己のノードに接続された通
信路のトラフィックに関する情報と，前記受信された前
記他のノードに接続された通信路のトラフィックに関す
る情報とを記憶する手順と，を備えているトラフィック
情報収集プログラム。

【０１５７】（付記２０） 通信される情報を送信，受
信または中継する複数のノードと，該複数のノードを接
続する通信路とを有する通信ネットワークにおける前記
ノードで実行される，前記通信路のトラフィック情報を
収集するトラフィック情報収集プログラムであって，自
己のノードに接続された通信路のトラフィックに関する
情報を収集する手順と，前記収集された前記自己のノー
ドに接続された通信路のトラフィックに関する情報と，
他のノードから送信されてきた該他のノードに接続され
た通信路のトラフィックに関する情報とを記憶する手順
と，を備えているトラフィック情報収集プログラム。

【０１５８】

【発明の効果】本発明によると，通信ネットワーク上の
ノードが，通信ネットワークにおけるトラフィックに関
する情報を収集することができ，該情報により，負荷分
散制御を行うことができる。

【図面の簡単な説明】

【図１】本発明に係る情報収集装置を備えたノードを有
する通信ネットワーク１の概略構成を示すブロック図で
ある。

【図２】入側ルータの構成を示すブロック図である。

【図３】オペークＬＳＡのデータ構造を示す。

【図４】オペークＬＳＡに含まれるリンク・データのデ
ータ構造を示す。

【図５】ルータのＯＳがリアルタイムで収集／管理して
いるシステム状態のデータの一例を示す。

【図６】ルータのＯＳがリアルタイムで収集／管理して
いるデータの一例を示す。

【図７】第１のフラッディング方法の処理の流れを示す
フローチャートである。

【図８】第２のフラッディング方法の処理の流れを示す
フローチャートである。

【図９】第３のフラッディング方法の処理の流れを示す
フローチャートである。

【図１０】第３のフラッディング方法の処理の流れを示
すフローチャートである。

【図１１】オペークＬＳＡ用データベース更新処理の流
れを示すフローチャートである。

【図１２】オペークＬＳＡ用データベースのデータ構造
を示す。

【符号の説明】

１ 通信ネットワーク １１Ｓ 入側ルータ １１Ｒ 中継ルータ １１Ｄ 出側ルータ Ｌ１，Ｌ２，Ｌ３ リンク ２１，２２，２３ 経路（仮想コネクション） ３０ 処理装置 ３２ 記憶装置 ３２ｂ オペークＬＳＡ用データベース ４１〜４７ インタフェース装置

───────────────────────────────────────────────────── フロントページの続き (72)発明者 宗宮 利夫 神奈川県川崎市中原区上小田中４丁目１番 １号 富士通株式会社内 Ｆターム(参考） 5K030 GA13 HA08 HD03 LB05 LE03 MA04 MB09

Claims (5)

【特許請求の範囲】
1. 【請求項１】 通信される情報を送信，受信または中継
   する複数のノードと，該複数のノードを接続する通信路
   とを有する通信ネットワークにおける前記ノードに設け
   られ，前記通信路のトラフィックに関する情報を収集す
   るトラフィック情報収集装置であって，自己のノードに
   接続された通信路のトラフィックに関する情報を収集す
   るトラフィック情報収集部と，前記通信ネットワーク上
   の通信プロトコルで使用されるメッセージにより，前記
   トラフィック情報収集部により収集された前記自己のノ
   ードに接続された通信路のトラフィックに関する情報を
   他のノードに送信するトラフィック情報送信部と，他の
   ノードから送信されてきた該他のノードに接続された通
   信路のトラフィックに関する情報を受信するトラフィッ
   ク情報受信部と，前記トラフィック情報収集部により収
   集された前記自己のノードに接続された通信路のトラフ
   ィックに関する情報と，前記トラフィック情報受信部に
   より受信された前記他のノードに接続された通信路のト
   ラフィックに関する情報とを記憶するトラフィック情報
   記憶部と，を備えているトラフィック情報収集装置。
2. 【請求項２】 通信される情報を送信，受信または中継
   する複数のノードと，該複数のノードを接続する通信路
   とを有する通信ネットワークにおける前記ノードに設け
   られ，前記通信路のトラフィック情報を収集するトラフ
   ィック情報収集装置であって，自己のノードに接続され
   た通信路のトラフィックに関する情報を収集するトラフ
   ィック情報収集部と，前記トラフィック情報収集部によ
   り収集された前記自己のノードに接続された通信路のト
   ラフィックに関する情報と，他のノードから送信されて
   きた該他のノードに接続された通信路のトラフィックに
   関する情報とを記憶するトラフィック情報記憶部と，を
   備えているトラフィック情報収集装置。
3. 【請求項３】 請求項１または２において，前記他のノ
   ードから送信されてきたトラフィックに関する情報を，
   送信されてきた通信路を除く他の通信路に転送するトラ
   フィック情報転送部をさらに備えている，トラフィック
   情報収集装置。
4. 【請求項４】 通信される情報を送信，受信または中継
   する複数のノードと，該複数のノードを接続する通信路
   とを有する通信ネットワークにおける前記ノードで行わ
   れる，前記通信路のトラフィック情報を収集するトラフ
   ィック情報収集方法であって，自己のノードに接続され
   た通信路のトラフィックに関する情報を収集し，前記収
   集された前記自己のノードに接続された通信路のトラフ
   ィックに関する情報と，他のノードから送信されてきた
   該他のノードに接続された通信路のトラフィックに関す
   る情報とを記憶する，トラフィック情報収集方法。
5. 【請求項５】 通信される情報を送信，受信または中継
   する複数のノードと，該複数のノードを接続する通信路
   とを有する通信ネットワークにおける前記ノードで実行
   される，前記通信路のトラフィック情報を収集するトラ
   フィック情報収集プログラムであって，自己のノードに
   接続された通信路のトラフィックに関する情報を収集す
   る手順と，前記収集された前記自己のノードに接続され
   た通信路のトラフィックに関する情報と，他のノードか
   ら送信されてきた該他のノードに接続された通信路のト
   ラフィックに関する情報とを記憶する手順と，を備えて
   いるトラフィック情報収集プログラム。