(57)【特許請求の範囲】
【請求項１】
ネットワーク中継装置において、
プライオリティを記憶するプライオリティ記憶手段、
前記プライオリティを、他のネットワーク中継装置のプライオリティと比較し、自身のプライオリティの方が他のネットワーク中継装置のプライオリティより大きい場合に、受信データの中継処理を行うよう制御するプライオリティ比較手段、
前記ネットワーク中継装置の処理負荷を測定する負荷測定手段、及び
前記負荷測定手段による測定結果を使用して、前記ネットワーク中継装置の負荷が高いほど低い値になるようにプライオリティを設定するプライオリティ設定手段とを有することを特徴とするネットワーク中継装置。
【請求項２】
請求項１に記載のネットワーク中継装置において、
前記負荷測定手段が、前記ネットワーク中継装置の資源の使用頻度を測定することを特徴とするネットワーク中継装置。
【請求項３】
請求項２に記載のネットワーク中継装置において、
前記負荷測定手段が、前記ネットワーク中継装置のＣＰＵ使用率を測定することを特徴とするネットワーク中継装置。
【請求項４】
請求項３に記載のネットワーク中継装置において、
前記プライオリティ設定手段が、プライオリティＰＲＩ１を次式によって求めることを特徴とするネットワーク中継装置。
ＰＲＩ１  ＝  ＰＲＩ１（Ｂ）  −  Ｋ１  ＊  Ｗ／１００
但し、ＰＲＩ１（Ｂ）、Ｋ１は、事前に設定される固定値であり、Ｗは前記ＣＰＵ使用率である。
【請求項５】
請求項１に記載のネットワーク中継装置において、
前記負荷測定手段が、前記ネットワーク中継装置が所定時間内に受信する前記受信データの数を測定することを特徴とするネットワーク中継装置。
【請求項６】
請求項５に記載のネットワーク中継装置において、
前記プライオリティ設定手段が、プライオリティＰＲＩ２を次式によって求めることを特徴とするネットワーク中継装置。
ＰＲＩ２  ＝  ＰＲＩ２（Ｂ）  −  Ｋ２  ＊  Ｙ
但し、ＰＲＩ２（Ｂ）、Ｋ２は、事前に設定される固定値であり、Ｙは前記受信データの数である。
【請求項７】
請求項１に記載のネットワーク中継装置において、
前記ネットワーク中継装置がルータであり、前記ルータが、ＶＲＲＰに基づいて前記プライオリティの比較を行い、かつ、受信データの中継処理を行うことを特徴とするネットワーク中継装置。
【請求項８】
請求項１に記載のネットワーク中継装置において、
前記ネットワーク中継装置のそれぞれが仮想識別ＩＤ毎にプライオリティを有し、前記プライオリティの比較が同じ仮想識別ＩＤの間で行われた結果、一のネットワーク中継装置において、他のネットワーク中継装置のプライオリティより大きいプライオリティを有する仮想識別ＩＤが存在する場合に、前記一のネットワーク中継装置が、その仮想識別ＩＤと同じＩＤに関連づけられたノードから送信された前記受信データの中継処理を行うよう制御することを特徴とするネットワーク中継装置。
【請求項９】
ネットワーク中継装置に記憶されたプライオリティを、他のネットワーク中継装置のプライオリティと比較するステップ、
前記ネットワーク中継装置のプライオリティの方が他のネットワーク中継装置のプライオリティより大きい場合に、受信データの中継処理を行うよう制御するステップ、
前記ネットワーク中継装置の処理負荷を測定するステップ、及び
前記負荷測定ステップによる測定結果を使用して、前記ネットワーク中継装置の負荷が高いほど低い値になるようにプライオリティを設定するステップとを有することを特徴とするネットワーク中継装置の負荷分散方法。
【請求項１０】
請求項９に記載のネットワーク中継装置の負荷分散方法において、
前記負荷測定ステップが、前記ネットワーク中継装置の資源の使用頻度を測定することを特徴とするネットワーク中継装置の負荷分散方法。
【請求項１１】
請求項１０に記載のネットワーク中継装置の負荷分散方法において、
前記負荷測定ステップが、前記ネットワーク中継装置のＣＰＵ使用率を測定することを特徴とするネットワーク中継装置の負荷分散方法。
【請求項１２】
請求項９に記載のネットワーク中継装置の負荷分散方法において、
前記負荷測定ステップが、前記ネットワーク中継装置が所定時間内に受信する前記受信データの数を測定することを特徴とするネットワーク中継装置の負荷分散方法。
【請求項１３】
請求項９に記載のネットワーク中継装置の負荷分散方法において、
前記ネットワーク中継装置がルータであり、前記ルータが、ＶＲＲＰに基づいて前記プライオリティの比較を行い、かつ、受信データの中継処理を行うことを特徴とするネットワーク中継装置の負荷分散方法。
【請求項１４】
コンピュータを、
プライオリティを記憶するプライオリティ記憶手段と、
前記プライオリティを、他のネットワーク中継装置のプライオリティと比較し、自身のプライオリティの方が他のネットワーク中継装置のプライオリティより大きい場合に、受信データの中継処理を行うよう制御するプライオリティ比較手段と、
前記ネットワーク中継装置の処理負荷を測定する負荷測定手段と、
前記負荷測定手段による測定結果を使用して、前記ネットワーク中継装置の負荷が高いほど低い値になるようにプライオリティを設定するプライオリティ設定手段とを有するネットワーク中継装置として機能させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ＶＲＲＰ（Virtual Router Redundancy Protocol）を利用したルータにおいて、負荷分散を可能とし、特に、ＶＲＲＰにおいて使用される各ルータのプライオリティを動的に変化させることによってルータ間の負荷を分散させる方法に関する。
【０００２】
【従来の技術】
ＶＲＲＰは、ＩＰ（インターネット・プロトコル）の１つであり、ＲＦＣ２３３８に準拠し、ＬＡＮ上で静的構成のルータを使う場合に、バックアップルータの存在を許すものである。
【０００３】
目的のノードやネットワークにパケットを送信するのに複数の経路があって、送信元のノードが接続されるＬＡＮ上に、その複数の経路に対応する複数のルータが存在する場合、ＶＲＲＰは、そのうちの１つのルータを選択し、送信元のノードからのパケットは、そのルータを経由して目的のノード等に送信される。
【０００４】
これらの複数のルータは、１つの仮想ルータ（Virtual Router）を形成し、送信元のノードからは、１つのＩＰアドレスを有するルータとして取り扱われる。従って、ＶＲＲＰがどのルータを選んでも、送信元のノードからのパケットの送信は、１つのＩＰアドレスに対して行われる。
【０００５】
ＶＲＲＰでは、各ルータ間において一定間隔でハローパケットを交換し、各ルータが正常な状態かどうかをチェックしており、これはヘルスチェックと呼ばれる。また、当該ハローパケットには、ハローパケットを送信したルータのプライオリティが含まれており、各ルータは、これらのプライオリティと自身のプライオリティを比較することによって、どのルータがパケットを処理すべきアクティブ・ルータ（マスタ・ルータ）かを判断する。即ち、正常で最もプライオリティの高いルータを自律的にアクティブ・ルータとして設定し、その他のルータをスタンバイ・ルータ（バックアップ・ルータ）とする。
【０００６】
マスタ・ルータとして設定されたルータは、１つの仮想ルータとして定義された１群のルータを代表して、受信したパケットを処理する。マスタ・ルータが障害等の理由で通信不能となった場合、他のバックアップ・ルータは、マスタ・ルータがハローパケットに応答しないことを検知し、これらのバックアップ・ルータの中で、プライオリティの最も高いルータを、前のマスタ・ルータと同じＩＰアドレスを有する次のマスタ・ルータに設定する。
【０００７】
こうしたＶＲＲＰの機能により、ＩＰアドレスを変更することなく、通信不能となったルータを自動的に通信可能なルータに切り替えることができる。このことによって、１つのルータが障害となっても、パケットの送信を継続することができ、結果的に、ネットワークの信頼性が向上する。
【０００８】
【発明が解決しようとする課題】
上述のように、ＶＲＲＰは、ルータの冗長機能を提供するプロトコルであるが、このプロトコルには２つの問題点がある。
【０００９】
第１の問題点は、マスタ・ルータが完全に通信不能にならないとルータの切替が行われないことである。マスタ・ルータにトラフィックが集中して、パケットの処理効率が著しく低下している場合であっても、他のバックアップ・ルータに切り替わることがないため、特定のルータに処理が集中する傾向にある。
【００１０】
第２の問題点は、ＶＲＲＰに負荷分散機能がないことである。これは、第１の問題点とも密接に関連する問題であるが、第１の問題点で述べたように、ルータの切り替えは、マスタ・ルータが完全に通信不能になったことによって行われるために、マスタ・ルータが稼働している間に、その負荷を判定してルータの切り替えを行い、他のルータに負荷を分散させるような制御はされていない。
【００１１】
【課題を解決するための手段】
従って、本発明は、ＶＲＲＰを使用したルータにおいて、ルータ自身の負荷を判定し、負荷の低いルータがマスタ・ルータとなるようにルータの切り替えを行い、全体としてルータ間の負荷を分散させることができるルータ、負荷分散方法、及び当該方法を実行するプログラムを提供する。
【００１２】
本発明の第１の実施態様によれば、プライオリティを記憶するプライオリティ記憶手段、前記プライオリティを、他のネットワーク中継装置のプライオリティと比較し、自身のプライオリティの方が他のネットワーク中継装置のプライオリティより大きい場合に、受信データの中継処理を行うよう制御するプライオリティ比較手段、前記ネットワーク中継装置の処理負荷を測定する負荷測定手段、及び前記負荷測定手段による測定結果を使用して、前記ネットワーク中継装置の負荷が高いほど低い値になるようにプライオリティを設定するプライオリティ設定手段とを有するネットワーク中継装置が提供される。
【００１３】
これによって、ネットワーク中継装置の負荷が高いほど、そのネットワーク中継装置が処理を担当するデータは少なくなるように自動的に制御され、ネットワーク中継装置間で負荷が分散される。
【００１４】
本発明の第２の実施態様によれば、前記第１の実施態様のネットワーク中継装置において、前記負荷測定手段が、前記ネットワーク中継装置のＣＰＵ使用率を測定するネットワーク中継装置が提供される。
【００１５】
これによって、ネットワーク中継装置の負荷が、ＣＰＵ使用率をもとに把握され、複数のネットワーク中継装置の間で、受信データの処理に関する負荷が分散される。
【００１６】
本発明の第３の実施態様によれば、前記第１の実施態様におけるネットワーク中継装置がルータであり、前記ルータが、ＶＲＲＰに基づいて前記プライオリティの比較を行い、かつ、受信データの中継処理を行うように構成される。
【００１７】
これによって、各ルータは、自動的にルータ間で負荷を分散しながら、ＩＰパケットの中継処理を行う。
【００１８】
本発明の第４の実施態様によれば、ネットワーク中継装置に記憶されたプライオリティを、他のネットワーク中継装置のプライオリティと比較するステップ、前記ネットワーク中継装置のプライオリティの方が他のネットワーク中継装置のプライオリティより大きい場合に、受信データの中継処理を行うよう制御するステップ、前記ネットワーク中継装置の処理負荷を測定するステップ、及び前記負荷測定ステップによる測定結果を使用して、前記ネットワーク中継装置の負荷が高いほど低い値になるようにプライオリティを設定するステップとを有するネットワーク中継装置の負荷分散方法が提供される。
【００１９】
これによって、ネットワーク中継装置の負荷が高いほど、そのネットワーク中継装置が処理を担当するデータは少なくなるように自動的に制御され、ネットワーク中継装置間で負荷が分散される。
【００２０】
本発明の第５の実施態様によれば、プライオリティを記憶するプライオリティ記憶手段と、前記プライオリティを、他のネットワーク中継装置のプライオリティと比較し、自身のプライオリティの方が他のネットワーク中継装置のプライオリティより大きい場合に、受信データの中継処理を行うよう制御するプライオリティ比較手段と、前記ネットワーク中継装置の処理負荷を測定する負荷測定手段と、前記負荷測定手段による測定結果を使用して、前記ネットワーク中継装置の負荷が高いほど低い値になるようにプライオリティを設定するプライオリティ設定手段とを有するネットワーク中継装置としてコンピュータを機能させるプログラムが提供される。
【００２１】
これによって、ネットワーク中継装置の負荷が高いほど、そのネットワーク中継装置が処理を担当するデータは少なくなるように自動的に制御され、ネットワーク中継装置間で負荷が分散される。
【００２２】
【発明の実施の形態】
最初に、図６を参照して、従来のＶＲＲＰの機能について、特に、グループ化されたプライオリティの取り扱いについて詳細に説明する。
【００２３】
図６には２つのルータ（７１、７２）と４つのホスト（８１、８２、８３、８４）がネットワークを介して接続されている。図には示されていないが、ルータ７１、７２は、更に別のルータ、又はネットワークに接続されており、ホストから受信したパケットのルーティングを行い、そのパケットを、決定された適当なルータ、又はネットワークに送信する。
【００２４】
図中、各ホストは、ＶＲＩＤ（１）又はＶＲＩＤ（２）という情報を有しているが、これは、各ホストが、通常ルータとして用いるルータ（デフォルト・ルータ）を識別するための仮想ルータＩＤである。ホスト８１とホスト８２は、ＶＲＩＤ（１）という仮想ルータＩＤを有し、ホスト８３とホスト８４は、ＶＲＩＤ（２）という仮想ルータＩＤを有している。
【００２５】
一方、ルータ７１、７２は、それぞれ前記仮想ルータＩＤ毎に、プライオリティを有している。ルータ７１は、ＶＲＩＤ（１）についてプライオリティＰＲＩ（１−１）を、ＶＲＩＤ（２）についてＰＲＩ（１−２）を有し、ルータ７２は、ＶＲＩＤ（１）についてプライオリティＰＲＩ（２−１）を、ＶＲＩＤ（２）についてＰＲＩ（２−１）を有している。
【００２６】
ここで、ＰＲＩ（１−１）ないしＰＲＩ（２−２）は、互いに比較可能な所定の固定値を表すものである。
【００２７】
従って、この場合、ＶＲＲＰは、ルータ７１とルータ７２の間でハローパケットにより上記プライオリティの値を交換して比較し、他のルータより値が大きければ、そのルータが、対応する仮想ルータＩＤに関してマスタ・ルータとして機能する。
【００２８】
例えば、ＶＲＩＤ（１）について、ＰＲＩ（１−１）＞ＰＲＩ（２−１）であれば、仮想ルータＩＤ＝ＶＲＩＤ（１）に関してマスタ・ルータとして機能するルータは、ルータ７１ということになる。また、ＶＲＩＤ（２）について、ＰＲＩ（１−２）＜ＰＲＩ（２−２）であれば、仮想ルータＩＤ＝ＶＲＩＤ（２）に関してマスタ・ルータとして機能するルータは、ルータ７２になる。
【００２９】
このように仮想ルータＩＤのプライオリティが判定されると、前述のように、ホスト８１とホスト８２は、仮想ルータＩＤ＝ＶＲＩＤ（１）をデフォルト・ルータとするので、これらのホストからのパケットは、ルータ７１を経由して送信先に送信される。一方、ホスト８３とホスト８４は、仮想ルータＩＤ＝ＶＲＩＤ（２）をデフォルト・ルータとするので、これらのホストからのパケットは、ルータ７２を経由することになる。この状態では、２つのホストからのパケットが、１つのルータを経由するように構成され、ある程度、ルータの負荷分散がされているということができる。
【００３０】
ルータ７１とルータ７２の間では、一定の間隔でハローパケットが交換され、そのタイミングで両者のプライオリティが比較される。しかし、前述の通り、ＰＲＩ（１−１）ないしＰＲＩ（２−２）は固定値であるため、これらの値が管理者等によって変更されない限り、上記ホストとルータの対応関係は変更されない。
【００３１】
ここで、ルータ７１に障害が発生し、完全に機能が停止したと仮定すると、ルータ７２は、自身が発したハローパケットの応答がルータ７１からないために、ルータ７１が通信不能になったと判断し、それまでルータ７１が行ってきた仮想ルータＩＤ＝ＶＲＩＤ（１）としての機能を引き継ぎ、結果的に、２つの仮想ルータＩＤ（ＶＲＩＤ（１）、及びＶＲＩＤ（２））のマスタ・ルータとして動作する。即ち、ホスト８１ないしホスト８４は全て、ルータ７２を介してパケットを送信することになる。
【００３２】
この後、ルータ７１が復旧して、元のプライオリティで立ち上がると、ルータ７２がルータ７１に送信したハローパケットの応答がルータ７１から返され、これによって、再びプライオリティの比較が行われ、ルータ７１が再び仮想ルータＩＤ＝ＶＲＩＤ（１）のマスタ・ルータとして機能し始める。
【００３３】
しかし、このような構成では、ルータ７１及びルータ７２の間の負荷の偏りを自動的に是正することはできない。例えば、ホスト８１、及びホスト８２のパケットがルータ７１を経由して送信され、これらのホストからのパケット数がある時点で、他のホストのパケット数に比べて極端に増加し、ルータ７１の処理能力を超えることになっても、ＶＲＲＰではルータ７１が完全に通信不能とならない限り、その処理の一部をルータ７２が分担するような制御は行われない。
【００３４】
次に、図１を参照して、本発明の第１の実施形態のルータについて説明する。
【００３５】
前述のように、従来のＶＲＲＰにおいては、プライオリティは管理者等が設定した固定的な値であったが、本実施形態では、このプライオリティの値がルータのＣＰＵ使用率等の測定値に依存して動的に変化する。
【００３６】
図１のルータは、ルーティング・テーブルを使用したルーティング手段等の一般的手段の他に、ＣＰＵ使用率測定手段１１、及びプライオリティ設定手段１２を有している。
【００３７】
ＣＰＵ使用率測定手段１１は、自身のルータにおけるＣＰＵ使用率を測定し、その結果を０から１００（％）の間の値Ｗで返す機能を有する。ＣＰＵ使用率は、通常は、ホストからのパケット数が増加すれば必然的に増加するものであるが、パケットの宛先が多岐にわたって、ルーティング・テーブルを頻繁に参照する必要がある場合など、受信するパケットの性質にも依存する。
【００３８】
プライオリティ設定手段１２は、ＣＰＵ使用率測定手段１１で測定されたＣＰＵ使用率Ｗを元にして、動的にプライオリティを設定する機能を有する。プライオリティＰＲＩ１は、以下の式１によって求められる。
【００３９】
ＰＲＩ１  ＝  ＰＲＩ１（Ｂ）  −  ＰＲＩ１（Ｈ）      ．．．（式１）
ここで、ＰＲＩ１（Ｂ）（基本プライオリティ）は、予め管理者又は利用者が設定する値であり、ＰＲＩ１（Ｈ）（補正プライオリティ）は、ＣＰＵ使用率Ｗを元にして計算された値であり、以下の式２によって求められる。
【００４０】
ＰＲＩ１（Ｈ）＝  Ｋ１  ＊  Ｗ／１００                ．．．（式２）
但し、Ｋ１は所定の係数である。更に、Ｗは０から１００（％）であるため、Ｗ／１００は、０から１の間の値を有する。
【００４１】
また、ＣＰＵ使用率は、それ自体、所定の時間当たりの利用割合を表すものであるが、ここでは、ある一定時間Ｔの間における、これらの値の最大値、最小値、平均値等が選択的に使用され得る。もちろん、これ以外の基準や、組み合わせによって、ＣＰＵ使用率を表すことも可能である。
【００４２】
また更に、基本プライオリティＰＲＩ１（Ｂ）、係数Ｋ１は、ルータ毎に、そのルータの性能等に応じて設定することができ、また、１つのルータの中でも、仮想ルータＩＤ毎に異なる値を設定することができる。
【００４３】
本発明の第１の実施形態では、ルータの負荷分散を行うために、ルータのＣＰＵ使用率を測定し、その使用率を下げる方向に、即ち、ＣＰＵ使用率の低いルータが、より高いプライオリティを有して、より多いパケットのルーティングを受け持つようにして、ルータ間の負荷を分散させようとするものであるが、ルータの他の資源の使用頻度、例えば、メモリーの使用率やハードディスクのＩ／Ｏデータ量などをもとにしてプライオリティを計算することもできる。
【００４４】
また、こうしたルータの各資源の使用頻度をいくつか組み合わせてプライオリティを計算することも可能である。
【００４５】
プライオリティをルータ間で比較するタイミングは、ＶＲＲＰにおいてハローパケットを受信するタイミング（通常、１秒間隔）が望ましい。従って、ＣＰＵ使用率を測定する一定時間Ｔも、そのタイミング（即ち１秒）とすることができる。
【００４６】
しかし、ルータの性能によっては、このように頻繁にプライオリティを比較してマスタ・ルータの切り替えを行うことが却って全体の性能を劣化させる場合も考えられるので、上記測定タイミングは慎重に調整する必要がある。
【００４７】
また、ＣＰＵ使用率を測定する一定時間Ｔを２秒、５秒等、ある程度長時間に設定し、ＣＰＵ使用率の長期の変動傾向をプライオリティに反映させることもできる。
【００４８】
また更に、上記式１、及び式２は、ＣＰＵ使用率の高いものほどプライオリティが小さくなるように調整された式の一例を示したに過ぎず、本発明の範囲がこれに限られるものではない。当業者であれば、他の多くのパターンを導出することが可能である。
【００４９】
次に、図１、及び図６を参照して、本発明の第１の実施形態のルータの動作について具体的に説明する。
【００５０】
定常状態において、ＰＲＩ（１−１）＞ＰＲＩ（２−１）の関係が成り立っている場合、仮想ルータＩＤ＝ＶＲＩＤ（１）に関しては、ルータ７１がマスタ・ルータとなり、ホスト８１、及びホスト８２のデフォルト・ルータとしてルータ７１が選択される。
【００５１】
同様に、ＰＲＩ（１−２）＜ＰＲＩ（２−２）の関係が成り立っているとすると、仮想ルータＩＤ＝ＶＲＩＤ（２）においては、ルータ７２がマスタ・ルータとなり、ホスト８３、及びホスト８４のデフォルト・ルータとしてルータ７２が選択される。
【００５２】
この状態で、各ホストがパケットを必要に応じてそれぞれ対応するデフォルト・ルータに送信した結果、ルータ７１が高負荷状態となり、一定時間Ｔの間、ＣＰＵ使用率がＷとなったとする（例えば、ここでは、一定時間ＴにおけるＣＰＵ使用率の最小値をＷとする）。
【００５３】
前述した式１、式２により、ＰＲＩ（１−１）を計算した結果、プライオリティの値が減少して、ＰＲＩ（１−１）＜ＰＲＩ（２−１）の関係になると、仮想ルータＩＤ＝ＶＲＩＤ（１）に関しては、ルータ７２がマスタ・ルータとなり、ホスト８１、及びホスト８２からのパケットは、ルータ７２を経由して送信されることになる。
【００５４】
この結果、ルータ７１の高負荷状態を回避することができる。また、このことによって、所定時間経過後の一定時間Ｔにおいて、ルータ７１のＣＰＵ使用率が低下すると同時に、ルータ７２のＣＰＵ使用率が上昇した結果、再びＰＲＩ（１−１）＞ＰＲＩ（２−１）の関係になると、ホスト８１、及びホスト８２のデフォルト・ルータは、再びルータ７１に設定される。
【００５５】
こうしたＶＲＲＰの従来の機能と、プライオリティの動的な制御によって、負荷の高いルータの処理負担を他のルータに動的に分散して、全体として効率のよいパケット処理が実現される。
【００５６】
次に、図２、及び図３を参照して、本発明の第１の実施形態のルータにおける処理フローを説明する。
【００５７】
図２は、ある１つのルータが、他のルータからハローパケットを受信した際に起動されるプロセスのフローを表している。当該プロセスは、受信したハローパケット内に、相手ルータのプライオリティの値が含まれている関係上、このタイミングで起動されることが好ましいが、これ以外のタイミングで起動することも可能である。
【００５８】
また、ここでは、ＣＰＵ使用率を測定する一定時間Ｔが、ハローパケットを受信するタイミング（通常、１秒）と同じであるとして説明する。もちろん、複数の記憶エリアを割り当てることによって、これ以上の時間におけるＣＰＵ使用率を何種類か並行的に記憶することができる。
【００５９】
ハローパケットを他のルータ（例えば、ルータ７２）から受け取ると、ルータ（例えば、ルータ７１）は、まず、ステップＳ１０において、これまで測定していたＣＰＵ使用率をセーブし、ステップＳ１２において、次回のハローパケット受信時に使用する、新たな次の時間ＴのＣＰＵ使用率の測定を開始する。
【００６０】
その後、ステップＳ１４ないしステップＳ２２の処理が、ルータと他のルータとの間で共通する仮想ルータＩＤ毎に、繰り返し行われる。プライオリティの計算やプライオリティの比較が仮想ルータＩＤ毎にされるためである。
【００６１】
ステップＳ１４では、ステップＳ１０でセーブされたＣＰＵ使用率から、前述の式１、式２を使用してプライオリティを計算する。ステップＳ１０でセーブされたＣＰＵ使用率は、前回のハローパケット受信から今回のハローパケット受信まで（時間Ｔ）のＣＰＵ使用率である。
【００６２】
次に、ステップＳ１６では、ハローパケット内の、他のルータのプライオリティと、ステップＳ１４で計算されたプライオリティを比較する。計算された自ルータのプライオリティの方が大きい場合（ステップＳ１８のＹＥＳ）、自ルータを、その仮想ルータＩＤに関してアクティブ・モードにする（ステップＳ２０）。これによって、その仮想ルータＩＤを有するホストからのパケットがそのルータによって取り扱われ、適切な経路で送信される。
【００６３】
それ以外の場合（ステップＳ１８のＮＯ）、自ルータを、その仮想ルータＩＤに関してスタンバイ・モードにする（ステップＳ２２）。この場合、その仮想ルータＩＤのホストから送信されたパケットは、そのルータによって扱われない。
【００６４】
このフローが、各ルータで実行されるため、例えば、１つのルータ７１が、他のルータ７２からハローパケットを受信した際に、ある仮想ルータＩＤに関してスタンバイ・モードを選択したとすると、逆に、他のルータ７２は、ルータ７１からハローパケットを受信した際に、その仮想ルータＩＤに関してアクティブ・モードを選択することになる。これは、ルータ７２の方が、その時点でＣＰＵ使用率が低かったことを示しており、上記仮想ルータＩＤに関しての処理が、ルータ７１の担当からルータ７２の担当に振り向けられたことになる。こうして、ルータ間の負荷分散が自動的に行われ、全体として効率のよいパケット処理が行われる。
【００６５】
また、この例では、理解を容易にするため、２つのルータ、及び４つのホスト（ノード）を用いて説明がされているが、これらの数に制限はない。更に、仮想ルータＩＤの設定方法についても各ルータ間で適宜行うことができるが、冗長性を維持するため、１つの仮想ルータＩＤは、通常複数のルータで定義される。
【００６６】
図３は、ある１つのルータが、他のルータに対してハローパケットを送信したが、応答がなく、当該他のルータに障害が発生したと判断した場合に起動されるプロセスのフローである。当該プロセスは、図２で説明したプロセス同様、これ以外のタイミングでも起動されうる。
【００６７】
ステップＳ３０において、次にハローパケットを正常に受信する場合に備えて、ＣＰＵ使用率の測定を開始する。この場合、他のルータは障害中であって、ハローパケットを正常に送信できるようになるまでには、多くの時間を要する場合がある。従って、その場合には、こうして得られたＣＰＵ使用率から、ハローパケットを受信する直前の一定時間ＴにおけるＣＰＵ使用率を適切に取り出す処理が必要となる。
【００６８】
ステップＳ３２では、自ルータと他のルータとの間で共通する仮想ルータＩＤに関して、自ルータをアクティブ・モードにする。この時点では、他のルータに障害が発生しており、ハローパケットを受け取ることができないため、自ルータは、他のルータの仮想ルータＩＤを全て事前に知っておくことが必要である。
【００６９】
このフローを各ルータが実行することによって、障害の発生したルータが、それまで担当していた仮想ルータＩＤについてのパケットの処理を、いくつかの他のルータで自動的に引き継ぐことができる。この機能は、従来のＶＲＲＰによって実現されるものと同様である。
【００７０】
また、障害の発生したルータが復旧した場合、その時点でルータは、どのパケットの処理も担当していないので、非常に低いＣＰＵ使用率となっていることが予想される。しかし、その後、何回か他のルータとハローパケットの交換を行うことによって、いくつかの仮想ルータＩＤのパケットに関して、処理の担当をすることになり、次第にＣＰＵ使用率も上昇することになる。こうしてＣＰＵ使用率が他のルータと同程度になると、処理する仮想ルータＩＤはほぼ安定する。
【００７１】
この点、従来のＶＲＲＰでは、固定値であるプライオリティを単に比較するだけで、どの仮想ルータＩＤのパケットを担当するかが決められていたが、本発明の第１の実施形態のルータでは、新たな仮想ルータＩＤのパケットを処理することによるＣＰＵ使用率の上昇の程度が加味され、他のルータのＣＰＵ使用率とバランスをとるように、自動的に調整される。
【００７２】
次に、本発明の第２の実施形態のルータについて、図４を参照して説明する。
【００７３】
図４のルータ３０は、パケット測定手段３１、及びプライオリティ設定手段３２を有している。
【００７４】
パケット測定手段３１は、自身のルータで処理されたパケットの数（トラフィック）をカウントし、その数を値Ｙで返す機能を有する。ここでのパケット数は、特定のＩＰアドレスを宛先としたパケットや、特定のアプリケーションのためのパケットのみを対象とした数とすることも可能である。
【００７５】
プライオリティ設定手段３２は、パケット測定手段３１で測定されたパケット数Ｙを元にして、動的にプライオリティを設定する機能を有する。プライオリティＰＲＩ２は、以下の式３によって求められる。
【００７６】
ＰＲＩ２  ＝  ＰＲＩ２（Ｂ）  −  ＰＲＩ２（Ｈ）      ．．．（式３）
ここで、ＰＲＩ２（Ｂ）（基本プライオリティ）は、予め管理者又は利用者が設定する値であり、ＰＲＩ２（Ｈ）（補正プライオリティ）は、パケット数Ｙを元にして計算された値であり、以下の式４によって求められる。
【００７７】
ＰＲＩ２（Ｈ）＝  Ｋ２  ＊  Ｙ                        ．．．（式４）
但し、Ｋ２は所定の係数である。Ｙは、ある一定時間Ｔの間におけるパケット数である。但し、Ｙとして、パケット数を表す他の指標、例えば、時間Ｔを複数のタイムスロットに分割した場合の、各タイムスロットにおけるパケット数の最大値、最小値、あるいは平均値等を使用することもできる。
【００７８】
また更に、基本プライオリティＰＲＩ２（Ｂ）、係数Ｋ２は、ルータ毎に、そのルータの性能等に応じて設定することができ、また、１つのルータの中でも、仮想ルータＩＤ毎に異なる値を設定することができる。
【００７９】
これによって、所定の単位時間当たりに処理するパケット数が多いルータほどプライオリティが低くなり、自動的に、処理パケット数の少ないルータにパケット処理が動的にシフトされる。また、上記式３、及び式４は、パケット数の多いものほどプライオリティが小さくなるように調整された式の一例を示したに過ぎず、本発明の範囲がこれに限られるものではない。当業者であれば、多くの他の類似のパターンを導出することが可能である。
【００８０】
本発明実施形態のルータは、ＣＰＵ使用率を測定する第１の実施形態と比較して、パケット数のカウントのみによってルータの負荷を測定するものであるため、場合によっては、ルータに余分な負荷を与えず、好ましい場合がある。
【００８１】
次に、本発明の第３の実施形態のルータについて説明する。このルータは、第１の実施形態のルータと第２の実施形態のルータとを組み合わせたものである。即ち、各ルータのプライオリティが、そのルータのＣＰＵ使用率、及び処理パケット数を元に計算されるものである。
【００８２】
通常、ＣＰＵ使用率は、処理パケット数が増加すれば高くなるが、パケットの宛先、パケット長、パケットの受信タイミング等によっては、必ずしもそうならない場合がある。そのため、ＣＰＵ使用率とパケット数の両方を、プライオリティ計算のファクターとすることによって、ルータの負荷を総合的にとらえようとするものである。
【００８３】
この場合のプライオリティＰＲＩ３を求める式５は、例えば以下のようなものである。
【００８４】
ＰＲＩ３  ＝  ＰＲＩ３（Ｂ）  −  ＰＲＩ１（Ｈ）  −  ＰＲＩ２（Ｈ）  ．．．（式５）
ここで、ＰＲＩ３（Ｂ）は、予め管理者又は利用者が設定する基本プライオリティであり、ＰＲＩ１（Ｈ）は、式２により求められた、ＣＰＵ利用率による補正プライオリティ、ＰＲＩ２（Ｈ）は、式４により求められた、パケット数による補正プライオリティである。
【００８５】
当該実施形態においては、ルータのＣＰＵ使用率の増加、及びパケット数の増加が、そのルータのプライオリティを下げるように働く式を設定することが必要である。従って、前記式５はそのような式の一例に過ぎず、当業者は、その他の多くのバリエーションを容易に導出することができる。例えば、ＰＲＩ１（Ｈ）とＰＲＩ２（Ｈ）にそれぞれ一定比率を乗じて、これらがＰＲＩ３に及ぼす影響を調整する等の方法が考えられる。
【００８６】
ここまで、本発明の負荷分散方法について、ＩＰの一種であるＶＲＲＰに適用する例について説明してきた。しかし、ルータの負荷を何らかの方法で定量化してルータのプライオリティに反映させ、ルータ間の負荷を分散させる本発明の負荷分散方法は、ルータを利用した他のプロトコル、あるいは通信方法にも十分適用できるものである。従って、本発明は、ＶＲＲＰに適用する場合に限定される必要はなく、プライオリティによってルータにおけるパケット処理の配分を定める全ての方法に適用可能である。また、本発明の方法については、ルータによって実現される例を示してきたが、例えば、ゲートウエイ等の他のネットワーク中継装置に応用することも可能である。
【００８７】
最後に、本発明の各実施形態のルータの構成について、図５を参照して説明する。第１ないし第３の実施形態のルータについて説明してきたが、ルータの物理的構成は基本的に同じである。
【００８８】
図５のルータ５０は、ＣＰＵ５１、メモリ５２、外部記憶装置５３、入力装置５４、出力装置５５、記録媒体駆動装置５６、ネットワーク・インタフェース５７、及びこれらの構成要素５１〜５７を相互に接続するバス５８からなる。
【００８９】
ＣＰＵ５１は、ルータ５０内の各構成要素の制御、及びルーティング処理、その他パケットの処理を実行するのに使用される。
【００９０】
メモリ５２は、前記制御、及び各処理を行うようＣＰＵ５１を制御するプログラム、及び当該プログラムが使用するデータを一時的に記憶する。
【００９１】
外部記憶装置５３は、ルーティング・テーブルや、ＶＲＲＰで使用される仮想ルータＩＤ（ＶＲＩＤ）等を記憶し、更に、本発明の負荷分散方法を実行するのに必要な基本プライオリティ（ＰＲＩ１（Ｂ）、ＰＲＩ２（Ｂ）、ＰＲＩ３（Ｂ））や、係数Ｋ１、Ｋ２などを記憶するハードディスク等の記憶装置である。
【００９２】
入力装置５４は、マウス、キーボード等の、ＣＰＵ５１に特定の指令を与えたり、外部記憶装置５３に記憶するデータを入力するための装置であり、上記仮想ルータＩＤ、基本プライオリティ、及び係数等は、管理者等によって当該入力装置５４を介して入力される。
【００９３】
出力装置５５は、ＣＲＴディスプレイやテレビモニタであるが、ルータの切り替えが生じた場合や、自ルータ、又は他のルータの障害を検知した場合にメッセージが表示される。
【００９４】
記録媒体駆動装置５６は、ＤＶＤ−ＲＯＭ、ＣＤ−ＲＯＭ、フレキシブルディスク等の記録媒体５９の内容を読み出し、必要に応じて前記メモリ５２や外部記憶装置５３にコピーする。本発明の負荷分散方法を実行するためにＣＰＵ５１に指令を与え制御する前記プログラムも当該記録媒体５９に格納される場合があり、必要に応じてメモリ５２にロードされる。ルータ５０は、このメモリ５２内にロードされた当該プログラムによって制御され、ＣＰＵ５１はこのプログラムの命令に従って各種処理を実行し、本発明の方法を実現する。
【００９５】
ネットワーク・インタフェース５７は、ルータ５０をネットワーク６０、又は他のネットワーク機器６１に接続する。ここでは、他のネットワーク機器６１は、例えば、図６に示されるようなホストである。ホストから送出されたパケットは、ネットワーク・インタフェース５７を介してルータ５０に送信され、ルータ５０によって、送信経路が判断され、適当な別なルータ、或いはネットワークに、ネットワーク６０を介して送信される。
【００９６】
前記ＣＰＵ５１に指令を与え、本発明の方法を実現するプログラムは、当該ネットワーク６０、及びネットワーク・インタフェース５７を介してメモリ５２にロードされる場合もある。
【００９７】
【発明の効果】
本発明のルータによって、ＶＲＲＰを使用した場合に、各ルータのプレイ折りティを、そのルータの負荷に応じて調整し、ルータ間の負荷を分散させることができる。
【００９８】
このことにより、従来、ＶＲＲＰでは、マスタ・ルータが完全に通信不能にならないと前述のルータの切替が行われなかったが、マスタ・ルータにトラフィックが集中して、パケットのルーティング処理等の処理効率が著しく低下している場合であっても、そのルータの負荷を判定して、パケットの処理を、自動的に他のバックアップ・ルータに切り替えることができる。
【図面の簡単な説明】
【図１】本発明の第１の実施形態のルータの機能ブロック図である。
【図２】本発明の第１の実施形態のルータにおいて、ハローパケットを受信した際の処理を示すフローチャートである。
【図３】本発明の第１の実施形態のルータにおいて、他のルータの障害を検知した際の処理を示すフローチャートである。
【図４】本発明の第２の実施形態のルータの機能ブロック図である。
【図５】本発明のルータの構成を示すブロック図である。
【図６】従来のＶＲＲＰの機能を説明するための、ルータ及びホストを含むネットワーク構成図である。
【符号の説明】
１０、３０、５０、７１、７２  ルータ
１１  ＣＰＵ使用率測定手段
１２、３２  プライオリティ設定手段
３１  パケット測定手段
５１  ＣＰＵ
５２  メモリ
５３  外部記憶装置
５４  入力装置
５５  出力装置
５６  記録媒体駆動装置
５７  ネットワーク・インタフェース
５８  バス
５９  記録媒体
６０  ネットワーク
６１  ネットワーク機器
８１、８２、８３、８４  ホスト
【図１】
0003646787.tif 000002
【図２】
0003646787.tif 000003
【図３】
0003646787.tif 000004
【図４】
0003646787.tif 000005
【図５】
0003646787.tif 000006
【図６】
0003646787.tif 000007