(57)【特許請求の範囲】
【請求項１】
複数のノードがリンクにより相互に接続されたネットワークに備えられた負荷分散サーバであって、
前記複数のノードからネットワーク状態情報を受信し、かつ前記ネットワーク状態情報をもとに最適なリンク・メトリックを判定し、前記最適なリンク・メトリックを前記複数のノードに送信し、
前記各ノードにおいて前記最適なリンク・メトリックに基づき動的経路選択を行なわせることを特徴とする負荷分散サーバ。
【請求項２】
前記ネットワーク状態情報は、
前記ノードの前記各隣接ノードとの接続の形態を表すネットワーク・トポロジー情報と、
前記ノードから前記各隣接リンクに対する送信方向に割り当てられているリンク・メトリックの値を表すリンク・メトリック情報と、
前記ノードにおけるトラフィック特性、並びにトラフィックパラメータを表すトラフィックフロー情報を含むことを特徴とする請求項１に記載の負荷分散サーバ。
【請求項３】
前記ネットワーク状態情報は、
前記ノードの前記各隣接ノードとの接続の形態を表すネットワーク・トポロジー情報と、
前記ノードから前記各隣接リンクに対する送信方向に割り当てられているリンク・メトリックの値を表すリンク・メトリック情報と、
前記ノードに隣接する前記各リンクにおける前記ノードから送信方向の使用帯域、並びに使用可能最大帯域を表すリンク負荷情報と、
前記ノードにおけるトラフィック特性、並びにトラフィックパラメータを表すトラフィックフロー情報を含むことを特徴とする請求項１に記載の負荷分散サーバ。
【請求項４】
前記負荷分散サーバは、
前記ネットワーク内の前記ノード全ての経路選択の動作をエミュレーションする経路選択エミュレータを備え、
前記経路選択エミュレータにより、前記ネットワーク状態情報を参照し、かつ前記経路選択エミュレータ内のリンク・メトリックの値を変化させながらエミュレーションを繰返し行なうことで、前記最適なリンク・メトリックを求めることを特徴とする請求項１乃至３の何れか１項に記載の負荷分散サーバ。
【請求項５】
前記負荷分散サーバは、
前記経路選択エミュレータにより、前記経路選択エミュレータ内のリンク・メトリックの値を、前記ネットワーク内の前記各リンクのリンク負荷の量が等しくなるように変化させながら、前記エミュレーションを繰返し行なうことで、前記最適なリンク・メトリックを求めることを特徴とする請求項４に記載の負荷分散サーバ。
【請求項６】
前記負荷分散サーバは、
前記経路選択エミュレータにより、前記ネットワーク内の前記各リンクの使用帯域の量を実リンク帯域の量で割った値が互いに等しくなるように、前記経路選択エミュレータ内のリンク・メトリックの値を変化させながら、前記エミュレーションを繰返し行なうことで、前記最適なリンク・メトリックを求めることを特徴とする請求項４に記載の負荷分散サーバ。
【請求項７】
前記動的経路選択は、
前記各ノードにおいて、
前記最適なリンク・メトリックに基づき、前記ノードのルーティング・テーブルを更新し、さらに前記最適なリンク・メトリックをルーティング・プロトコルにより前記ノードに隣接する他の前記ノードと相互に通知し、前記隣接ノードからの情報に基づきルーティング・テーブルを更新することを特徴とする請求項１乃至６の何れか１項に記載の負荷分散サーバ。
【請求項８】
前記ネットワーク内の１つ又は複数の前記ノードは、内部に前記負荷分散サーバを実装することを特徴とする請求項１乃至７の何れか１項に記載の負荷分散サーバ。
【請求項９】
前記ネットワーク内の１つ又は複数の前記ノードは、
内部に前記負荷分散サーバを実装し、
かつ前記負荷分散サーバは、
前記ルーティングプロトコルにより、前記負荷分散サーバを実装する前記ノードを、前記負荷分散サーバを実装していない他の各ノードに対し通知し、負荷分散サーバの位置を認識させることを特徴とする請求項７に記載の負荷分散サーバ。
【請求項１０】
前記ネットワークがコネクションオリエンティッドな場合に、
前記最適なリンク・メトリックを前記隣接ノードと相互に通知する時に、既存のコネクションをも前記最適なリンク・メトリックに応じて変更することを特徴とする請求項７又は請求項９に記載の負荷分散サーバ。
【請求項１１】
前記既存のコネクションを変更する際に、前記既存のコネクションのサービスの瞬断を発生しないように、前記既存のコネクションを残したまま新たに最適なコネクションをはり、前記既存のコネクションのサービスを新規の前記最適なコネクションに迂回させた後、前記既存のコネクションを切断することを特徴とする請求項１０に記載の負荷分散サーバ。
【請求項１２】
複数のノードがリンクにより相互に接続され、前記複数のノードからネットワーク状態情報を受信し、かつ前記ネットワーク状態情報をもとに最適なリンク・メトリックを判定し、前記最適なリンク・メトリックを前記複数のノードに送信する負荷分散サーバを備えたネットワークにおけるノードであって、
前記最適なリンク・メトリックに基づき動的経路選択を行なうノード。
【請求項１３】
前記ネットワーク状態情報は、
前記ノードの前記各隣接ノードとの接続の形態を表すネットワーク・トポロジー情報と、
前記ノードから前記各隣接リンクに対する送信方向に割り当てられているリンク・メトリックの値を表すリンク・メトリック情報と、
前記ノードにおけるトラフィック特性、並びにトラフィックパラメータを表すトラフィックフロー情報を含むことを特徴とする請求項１２に記載のノード。
【請求項１４】
前記ネットワーク状態情報は、
前記ノードの前記各隣接ノードとの接続の形態を表すネットワーク・トポロジー情報と、
前記ノードから前記各隣接リンクに対する送信方向に割り当てられているリンク・メトリックの値を表すリンク・メトリック情報と、
前記ノードに隣接する前記各リンクにおける前記ノードから送信方向の使用帯域、並びに使用可能最大帯域を表すリンク負荷情報と、
前記ノードにおけるトラフィック特性、並びにトラフィックパラメータを表すトラフィックフロー情報を含むことを特徴とする請求項１２に記載のノード。
【請求項１５】
前記負荷分散サーバは、
前記ネットワーク内の前記ノード全ての経路選択の動作をエミュレーションする経路選択エミュレータを備え、
前記経路選択エミュレータにより、前記ネットワーク状態情報を参照し、かつ前記経路選択エミュレータ内のリンク・メトリックの値を変化させながらエミュレーションを繰返し行なうことで、前記最適なリンク・メトリックを求めることを特徴とする請求項１２乃至１４の何れか１項に記載のノード。
【請求項１６】
前記負荷分散サーバは、
前記経路選択エミュレータにより、前記経路選択エミュレータ内のリンク・メトリックの値を、前記ネットワーク内の前記各リンクのリンク負荷の量が等しくなるように変化させながら、前記エミュレーションを繰返し行なうことで、前記最適なリンク・メトリックを求めることを特徴とする請求項１５に記載のノード。
【請求項１７】
前記負荷分散サーバは、
前記経路選択エミュレータにより、前記ネットワーク内の前記各リンクの使用帯域の量を実リンク帯域の量で割った値が互いに等しくなるように、
前記経路選択エミュレータ内のリンク・メトリックの値を変化させながら、前記エミュレーションを繰返し行なうことで、前記最適なリンク・メトリックを求めることを特徴とする請求項１５に記載のノード。
【請求項１８】
前記動的経路選択は、
前記各ノードにおいて、
前記最適なリンク・メトリックに基づき、前記ノードのルーティング・テーブルを更新し、さらに前記最適なリンク・メトリックをルーティング・プロトコルにより前記ノードに隣接する他の前記ノードと相互に通知し、前記隣接ノードからの情報に基づきルーティング・テーブルを更新することを特徴とする請求項１２乃至１７の何れか１項に記載のノード。
【請求項１９】
前記ネットワーク内の１つ又は複数の前記ノードは、内部に前記負荷分散サーバを実装することを特徴とする請求項１２乃至１８の何れか１項に記載のノード。
【請求項２０】
前記ネットワーク内の１つ又は複数の前記ノードは、
内部に前記負荷分散サーバを実装し、
かつ前記負荷分散サーバは、
前記ルーティングプロトコルにより、前記負荷分散サーバを実装する前記ノードを、前記負荷分散サーバを実装していない他の各ノードに対し通知し、負荷分散サーバの位置を認識させることを特徴とする請求項１８に記載のノード。
【請求項２１】
前記ネットワークがコネクションオリエンティッドな場合に、前記最適なリンク・メトリックを前記隣接ノードと相互に通知する時に、既存のコネクションをも前記最適なリンク・メトリックに応じて変更することを特徴とする請求項１８又は請求項２０に記載のノード。
【請求項２２】
前記既存のコネクションを変更する際に、前記既存のコネクションのサービスの瞬断を発生しないように、前記既存のコネクションを残したまま新たに最適なコネクションをはり、前記既存のコネクションのサービスを新規の前記最適なコネクションに迂回させた後、前記既存のコネクションを切断することを特徴とする請求項２１に記載のノード。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、リンク・メトリックを基準に最適経路を決定する動的経路選択に関し、特に、ネットワーク管理サーバによりネットワークの状態を監視し、リンク・メトリックを定期的に最適なものに更新することで、ネットワーク全体の負荷分散を実現するネットワーク負荷分散システムに関する。
【０００２】
【従来の技術】
ネットワークにおいてデータを送信するとき、送信先に到達可能な複数の通信経路の中から１つの経路を選択することを経路選択（またはルーティング）と言う。経路選択の方法としては、伝送時間の短縮や伝送路の使用効率の向上を目的として、最適な経路を選択するために各種の方法が使用されている。
【０００３】
静的経路選択は、予め各送信先に対する最適と考えられる通信経路を固定的に定めておく方式である。各送信先に対する通信経路は、ルーティング・テーブルにおいて指示され、このルーティング・テーブルを参照することで経路選択を行なう。
【０００４】
動的経路選択は、ルーティング・テーブルの内容を、トラフィック変動やネットワーク構成の変化に応じて最適なものに更新していく方式である。さらにこのルーティング・テーブルを、ルーティング・プロトコルを用いて各ノード間で交換することにより他のノードの情報を得て、最適な経路選択を行なう。
【０００５】
通信経路における中継装置の数をホップ（Ｈｏｐ）値といい、これによりこの通信経路による送受信ノード間の距離を代表させ、実際に経由する中継装置の数が最小になる経路の中継装置の数をコストという。こうしてリンク・メトリック、つまりネットワーク上の距離を用いて最適な経路選択を行なう。
【０００６】
主なルーティング・プロトコルは、ＲＩＰ（Ｒｏｕｔｉｎｇ  Ｉｎｆｏｍａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ）と、ＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）である。
【０００７】
ＲＩＰは、ホップ値とコストから最適経路を決定する。しかし、コストすなわち中継装置の数が最小であっても伝送時間が最小になるとは限らない。ＯＳＰＦでは、ＲＩＰのこれらの欠点を解決し、回線の輻輳状態を考慮して最適経路を決定する。
【０００８】
従来、この種の動的経路選択によるネットワーク負荷分散システムは、各ノードが自立的に自ノードと隣接ノードの間のリンクの負荷を測定し、負荷がある閾値を超えた時点で、事前に決められたルールに従いリンク・メトリックを適切に増減し、これに対応してルーティング・テーブルを更新し、かつこのリンク・メトリックの変更をネットワーク内の他のノードへ通知するものであった。
【０００９】
また、特開平０５−１３０１４４号公報では、リンクの負荷状態の検出部と、リンク・メトリック変更・送信部とから構成される技術が記載されている。
【００１０】
【発明が解決しようとする課題】
上述したように従来のネットワーク負荷分散システムでは、以下に述べるような問題点があった。
【００１１】
第１に、従来のネットワーク負荷分散システムでは、各ノードの近傍のみでの局所的な負荷分散にすぎず、ネットワーク全体での最適な負荷分散ではないという問題点がある。
【００１２】
その理由は、各ノードが自立的に測定した自ノードと隣接ノードの間のリンクの負荷（つまり近傍リンクのみの負荷）に基づき、自ノードと隣接ノードの間とのリンク・メトリックを局所的な面において適切に増減するものであったので、局所的な負荷分散にすぎず隣接ノード以外のネットワーク状況全体を考慮した負荷分散ができないからである。
【００１３】
第２に、前記特開平０５−１３０１４４号公報に公開された従来技術では、ネットワーク全体の動的変化に応じた最適なリンク・メトリックの決定ができないという問題点がある。
【００１４】
その理由は、前記特開平０５−１３０１４４号公報のネットワーク負荷分散システムでは、リンク負荷がある特定の閾値を超えた場合等に、閾値を超えたリンクのリンク・メトリックを一定値増減するという単純な静的な方法であるため、ネットワーク全体に係る変化であるトポロジー変更やトラフィックの分布変動等に対応する負荷分散ができないからである。
【００１５】
本発明の目的は、上記従来技術の欠点を解決し、ネットワークの伝送効率、信頼性、性能の向上を図るため、ネットワーク全体を考慮した最適な負荷分散が可能なネットワーク負荷分散システムを提供することである。
【００１６】
本発明の他の目的は、上記従来技術の欠点を解決するため、ネットワークのトポロジー変更、トラフィック変動等のネットワーク全体に係る動的変化に追随して、最適なリンク・メトリックを判定し、ルーティング・テーブルの更新が可能なネットワーク負荷分散システムを提供することである。
【００１７】
【課題を解決するための手段】
上記目的を達成するため本発明は、複数のノードがリンクにより相互に接続されたネットワークに備えられた負荷分散サーバであって、前記複数のノードからネットワーク状態情報を受信し、かつ前記ネットワーク状態情報をもとに最適なリンク・メトリックを判定し、前記最適なリンク・メトリックを前記複数のノードに送信し、前記各ノードにおいて前記最適なリンク・メトリックに基づき動的経路選択を行なわせることを特徴とする。
【００１８】
請求項２の本発明の負荷分散サーバは、前記ネットワーク状態情報は、前記ノードの前記各隣接ノードとの接続の形態を表すネットワーク・トポロジー情報と、前記ノードから前記各隣接リンクに対する送信方向に割り当てられているリンク・メトリックの値を表すリンク・メトリック情報と、前記ノードにおけるトラフィック特性、並びにトラフィックパラメータを表すトラフィックフロー情報を含むことを特徴とする。
【００１９】
請求項３の本発明の負荷分散サーバは、ネットワーク状態情報は、ノードの各隣接ノードとの接続の形態を表すネットワーク・トポロジー情報と、ノードから各隣接リンクに対する送信方向に割り当てられているリンク・メトリックの値を表すリンク・メトリック情報と、ノードに隣接する各リンクにおけるノードから送信方向の使用帯域、並びに使用可能最大帯域を表すリンク負荷情報と、ノードにおけるトラフィック特性、並びにトラフィックパラメータを表すトラフィックフロー情報を含むことを特徴とする。
【００２０】
請求項４の本発明の負荷分散サーバは、ネットワーク内のノード全ての経路選択の動作をエミュレーションする経路選択エミュレータを備え、経路選択エミュレータにより、ネットワーク状態情報を参照し、かつ経路選択エミュレータ内のリンク・メトリックの値を変化させながらエミュレーションを繰返し行なうことで、最適なリンク・メトリックを求めることを特徴とする。
【００２１】
請求項５の本発明の負荷分散サーバは、経路選択エミュレータにより、経路選択エミュレータ内のリンク・メトリックの値を、ネットワーク内の各リンクのリンク負荷の量が等しくなるように変化させながら、エミュレーションを繰返し行なうことで、最適なリンク・メトリックを求めることを特徴とする。
【００２２】
請求項６の本発明の負荷分散サーバは、経路選択エミュレータにより、ネットワーク内の各リンクの使用帯域の量を実リンク帯域の量で割った値が互いに等しくなるように、経路選択エミュレータ内のリンク・メトリックの値を変化させながら、エミュレーションを繰返し行なうことで、最適なリンク・メトリックを求めることを特徴とする。
【００２３】
請求項７の本発明の負荷分散サーバは、動的経路選択は、各ノードにおいて、最適なリンク・メトリックに基づき、ノードのルーティング・テーブルを更新し、さらに最適なリンク・メトリックをルーティング・プロトコルによりノードに隣接する他のノードと相互に通知し、隣接ノードからの情報に基づきルーティング・テーブルを更新することを特徴とする。
【００２４】
請求項８の本発明の負荷分散サーバは、１つ又は複数のノードの内部に負荷分散サーバを実装することを特徴とする。
【００２５】
請求項９の本発明の負荷分散サーバは、ネットワーク内の１つ又は複数のノードの内部に負荷分散サーバを実装し、かつ負荷分散サーバは、ルーティングプロトコルにより、負荷分散サーバを実装するノードを、負荷分散サーバを実装していない他の各ノードに対し通知し、負荷分散サーバの位置を認識させることを特徴とする。
【００２６】
請求項１０の本発明の負荷分散サーバは、ネットワークがコネクションオリエンティッドな場合に、最適なリンク・メトリックを隣接ノードと相互に通知する時に、既存のコネクションをも最適なリンク・メトリックに応じて変更することを特徴とする。
【００２７】
請求項１１の本発明の負荷分散サーバは、既存のコネクションを変更する際に、既存のコネクションのサービスの瞬断を発生しないように、既存のコネクションを残したまま新たに最適なコネクションをはり、既存のコネクションのサービスを新規の最適なコネクションに迂回させた後、既存のコネクションを切断することを特徴とする。
【００２８】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００２９】
図１は、本発明の第１の実施の形態によるネットワーク負荷分散システムの構成を示すブロック図である。
【００３０】
図１を参照すると、本発明の第１の実施の形態によるネットワーク負荷分散システムは、リンク２０ａ，２０ｂ、２０ｃ，２０ｄ，２０ｅ，２０ｆにより互いに接続された複数のノード１０ａ，１０ｂ，１０ｃ，１０ｄと、これら複数のノード１０ａ，１０ｂ，１０ｃ，１０ｄに対し接続された負荷分散サーバ３０から構成される。
【００３１】
ノード１０ａ，１０ｂ，１０ｃ，１０ｄは、ルータまたは交換機から成り、各リンク２０ａ，２０ｂ、２０ｃ，２０ｄ，２０ｅ，２０ｆを介してデータを送受信するものである。
【００３２】
負荷分散サーバ３０は、各ノード１０ａ，１０ｂ，１０ｃ，１０ｄからネットワークの状態の情報を受信し、それに応じて最適なリンク・メトリックを計算し、各ノードに通知することにより、負荷分散をはかる仕組みを持つ。
【００３３】
図２は、本発明の第１の実施の形態の負荷分散サーバ３０の構成を示すブロック図である。
【００３４】
図２を参照すると、本発明の第１の実施の形態の負荷分散サーバ３０は、ネットワーク状態受信部３１と、リンク・メトリック判定部３２と、リンク・メトリック送信部３３を備える。
【００３５】
ネットワーク状態受信部３１は、全てのノード１０ａ，１０ｂ，１０ｃ，１０ｄからネットワーク状態情報を受信し、かつ、受信したネットワーク状態情報、つまりネットワーク・トポロジー情報、リンク・メトリック情報、リンク負荷情報、トラフィックフロー情報をリンク・メトリック判定部３２へ送信する。
【００３６】
リンク・メトリック判定部３２は、受信したネットワーク状態を基に、ネットワーク全体のトポロジー、各リンク２０ａ，２０ｂ、２０ｃ，２０ｄ，２０ｅ，２０ｆに現在設定されているリンク・メトリック、リンク負荷、トラフィックフローのトラフィック特性、パラメータを認識し、この情報を用いて各リンク２０ａ，２０ｂ、２０ｃ，２０ｄ，２０ｅ，２０ｆの最適なリンク・メトリックを判定し、このリンク・メトリックをリンク・メトリック送信部３３へ送信する。
【００３７】
リンク・メトリック判定部３２は、内部に経路選択エミュレータ３２１を持ち、この経路選択エミュレータ３２１によりネットワーク上の経路選択のエミュレーションを、エミュレーションで求められるリンク負荷が適正な値となるように、リンク・メトリックの値を少しずつ修正しながらエミュレーションを繰り返し、最適なリンク・メトリックを求める。
【００３８】
リンク・メトリック送信部３３は、リンク・メトリック判定部３２で判定された最適なリンク・メトリックを各ノード１０ａ，１０ｂ，１０ｃ，１０ｄに対し送信する。
【００３９】
図３は、本発明の第１の実施の形態のノード１０ａの構成を示すブロック図である。
【００４０】
図３を参照すると、本発明の第１の実施の形態のノード１０ａは、ネットワーク状態検出部１１と、リンク・メトリック受信部１２と、リンク状態・データベース１３と、ルーティング・テーブル１４と、ルーティング・プロトコル１５と、データ受信部１６と、データ送信部１７を備える。
【００４１】
ノード１０ａによるネットワーク上のデータの送受信は、データ受信部１６と、データ送信部１７により行なわれる。
【００４２】
データ受信部１６は、各リンク２０ａ，２０ｂ、２０ｃによって接続された隣接ノード１０ｂ，１０ｃ，１０ｄから、データを受信する。
【００４３】
データ送信部１７は、同じく各リンク２０ａ，２０ｂ、２０ｃによって接続された隣接ノード１０ｂ，１０ｃ，１０ｄに対し、そのデータの送信先とルーティング・テーブル１４を参照して次に送信する隣接ノードを決定し、データを送信する。
【００４４】
ノード１０ａの、このネットワーク上のデータの送受信を負荷分散するための機能は、残るネットワーク状態検出部１１と、リンク・メトリック受信部１２と、リンク状態・データベース１３と、ルーティング・テーブル１４と、ルーティング・プロトコル１５により行なわれる。
【００４５】
ネットワーク状態検出部１１は、ノード１０ａのネットワークの状態を検出し負荷分散サーバ３０に対し送信する。
【００４６】
ネットワーク状態検出部１１は、ネットワーク・トポロジー検出部１１１と、リンク・メトリック検出部１１２と、リンク負荷検出部１１３と、トラフィックフロー検出部１１４を備える。
【００４７】
ネットワーク・トポロジー検出部１１１は、ノード１０ａが各隣接ノードと、どのリンクでどのように接続されているのかのネットワーク・トポロジー情報を検出する。つまり例えば、ノード１０ａとノード１０ｂの間はリンク２０ａで接続されている等の検出を行なう。
【００４８】
リンク・メトリック検出部１１２は、ノード１０ａから隣接リンク２０ａ，２０ｂ、２０ｃへのそれぞれに対する送信方向に、割り当てられているリンク・メトリックを検出する。方向を規定するのは、同一リンクでも送信方向と受信方向でリンク・メトリックが異なる場合があるためである。
【００４９】
リンク負荷検出部１１３は、リンク２０ａ、２０ｂ、２０ｃのそれぞれにおける、ノード１０ａから送信方向のリンク負荷を検出する。ここでリンク負荷検出部１１３が検出するリンク負荷の種類は、現在の使用帯域、及びリンクの使用可能最大帯域の２種類である。
【００５０】
トラフィックフロー検出部１１４は、トラフィック特性、ならびにトラフィックパラメータをフロー毎に検出する。
【００５１】
リンク・メトリック受信部１２は、負荷分散サーバ３０から送信される最適なリンク・メトリックを受信し、この最適なリンク・メトリックによりリンク状態・データベース１３を更新し、この更新されたリンク状態・データベース１３によりルーティング・テーブル１４を再計算し更新する。ここで、ルーティング・テーブル１４の再計算とは、リンク状態・データベース１３における更新された最適なリンク・メトリックに基づき、ネットワーク全体で最小コストの経路を再計算し求めることである。
【００５２】
さらに、リンク・メトリック受信部１２は、ルーティング・プロトコル１５に基づき、この更新された最適なリンク・メトリックを他のノード１０ｂ，１０ｃ，１０ｄに対し経路選択情報として送信し、かつ逆に、他のノード１０ｂ，１０ｃ，１０ｄにおける更新された最適なリンク・メトリックが、同様に経路選択情報としてノード１０ａに対し送信される。
【００５３】
ルーティング・プロトコル１５として、ルータの場合にはリンクステート型のＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆａｓｔ）ルーティング・プロトコルを用いることができる。交換機の場合にも、例えばリンクステート型のＰＮＮＩ（Ｐｒｉｖａｔｅ  Ｎｅｔｗｏｒｋ−Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ）ルーティング・プロトコルを用いることで同様の処理が実現できる。
【００５４】
次に、第１の実施の形態によるネットワーク負荷分散システムの動作について詳細に説明する。
【００５５】
ここでは、特にノード１０ａと分散サーバ３０との間の動作を説明するが、他のノードとも同様である。
【００５６】
まず、ノード１０ａにおいて、ネットワーク状態検出部１１を用いて、ネットワーク・トポロジー検出部１１１からのネットワーク・トポロジー情報と、リンク・メトリック検出部１１２からの現在のリンク・メトリック情報と、リンク負荷検出部１１３からのリンク負荷情報と、トラフィックフロー検出部１１４からのトラフィックフロー情報の４つのネットワーク状態を検出し負荷分散サーバ３０に対し送信する。
【００５７】
次に、負荷分散サーバ３０において、各ノード１０ａから送信されるネットワーク状態を、ネットワーク状態受信部３１が受信し、リンク・メトリック判定部３２へ送信する。
【００５８】
次に、リンク・メトリック判定部３２では、各ノード１０ａから送信されるネットワーク状態情報から、現在のネットワーク全体の状態を認識し、各リンクの最適リンク・メトリックを判定し、リンク・メトリック送信部３３へその値を通知する。
【００５９】
次に、リンク・メトリック送信部３３は、ノード１０ａに対し、リンク２０ａ，２０ｂ、２０ｃのノード１０ｂから送信方向の最適なリンク・メトリックを、送信する。
【００６０】
再び各ノード１０ａにおいて、リンク・メトリック受信部１２は、最適なリンク・メトリックを負荷分散サーバ３０から受信し、この最適なリンク・メトリックをリンク状態・データベース１３に反映させ、それによりノード１０ａ内のルーティング・テーブル１４を再計算し更新する。ルーティング・テーブル１４は、最適なリンク・メトリックを用いて、ネットワーク全体で最小コスト経路を再計算することで求める。
【００６１】
その後、ルーティング・プロトコル１５により、更新されたリンク・メトリック情報を隣接ノード１０ｂ、１０ｃ、１０ｄへ経路選択情報として配布する。一方、他のノード１０ｂ、１０ｃ、１０ｄも、同様に更新されたリンク・メトリック情報をノード１０ａへ経路選択情報として配布してくるので、その情報をルーティング・プロトコル１５が受信すると、その情報をまずリンク状態・データベース１３へ格納する。
【００６２】
その後、リンク状態・データベース１３の更新に伴い、再び最小コスト経路を再計算してルーティング・テーブル１４を更新する。
【００６３】
以上の手続きにより、すべてのノード１０ａ，１０ｂ，１０ｃ，１０ｄが、自分の新規のリンク・メトリック情報を更新するとともに、その情報を他のノードにも通知し合うことにより、それぞれのノードが新規のリンク・メトリック情報に従ったルーティング・テーブル１４で経路選択を行なう。
【００６４】
つまり、負荷分散サーバ３０内のリンク・メトリック判定部３２の計算した通りに、実際にトラフィックが負荷分散されることとなる。
【００６５】
負荷分散サーバ３０と各ノード１０ａ，１０ｂ，１０ｃ，１０ｄの以上の処理は定期的に実行され、時間が経過する毎にトポロジー、リンク・メトリック、リンク負荷、トラフィックフローの変化に動的に対応し、常にトラフィック負荷分散が図られる。
【００６６】
定期的な実行の周期は、ネットワークの変動のスピードと、負荷分散に対する要求条件にしたがって決める。
【００６７】
図４は、本発明の第１の実施の形態のリンク・メトリック判定部３２の、最適なリンク・メトリックの判定処理を説明するためのフローチャートである。
【００６８】
この判定処理においては、各変数を以下のように定める。
【００６９】
全ノードの数を「Ｎ」、ネットワーク内のノードを、「ノードｉ」、「ノードｊ」（ｉ，ｊ≦Ｎ）、ノードｉとノードｊ間の全経路の数を「Ｋｉｊ」、隣接するノードｉからノードｊへの、現在のリンク・メトリックの値を「Ａｉｊ」、隣接するノードｉからノードｊへの、求める最適化されたリンク・メトリックの値を「Ｂｉｊ」、隣接するノードｉからノードｊへの、現在のリンク負荷を「Ｃｉｊ」、ネットワーク内のノードｉからノードｊへの、経路ｋ（ｋ≦Ｋｉｊ）によるトラフィックフローを「Ｔｉｊｋ」と表す。
【００７０】
まず、リンク・メトリック判定部３２は、ネットワーク状態受信部３１を介して、ネットワークの全ノード（ノード１〜ノードＮ）からネットワーク状態情報を受信する（ステップ４０１）。
【００７１】
このネットワーク状態情報とは、ネットワーク・トポロジー情報と、リンク・メトリック情報｛Ａｉｊ：ノードｉ，ｊは隣接｝と、リンク負荷情報｛Ｃｉｊ：ノードｉ，ｊは隣接｝と、トラフィックフロー情報｛Ｔｉｊｋ：ｉ≠ｊ、ｋ≦Ｋｉｊ｝との全ての情報である。
【００７２】
次に、受信したこれらのネットワーク状態情報を基に、最適な新規リンク・メトリックＢｉｊを以下の手順で計算する。
【００７３】
リンク・メトリック判定部３２の内部の、経路選択エミュレータ３２１のカウンタを”０”にリセットする（ステップ４０２）。
【００７４】
ネットワーク状態情報を内部の経路選択エミュレータ３２１に初期情報として設定する（ステップ４０３）。ここで、変数リンク・メトリック値｛Ａｉｊ｝、リンク負荷｛Ｃｉｊ｝、トラフィックフロー｛Ｔｉｊｋ｝は、経路選択エミュレータ３２１内の計算用のメモリにそれぞれ｛ａｉｊ｝、｛ｃｉｊ｝、｛Ｔｉｊｋ｝として格納する。
【００７５】
経路選択エミュレータ３２１により、実際の全ノード１〜ノードＮが行うルーティング・テーブル１４の計算、並びにこのルーティング・テーブル１４によるデータの経路選択と同一の処理をエミュレートする。
【００７６】
経路選択エミュレータ３２１は、ネットワーク・トポロジー情報とリンク・メトリック｛ａｉｊ｝とから、まず最小コスト経路を計算し、擬似的に経路選択エミュレータ３２１内の全ノードのルーティング・テーブル１４を更新する（ステップ４０４）。
【００７７】
ここでもし複数の経路が同一の最小コスト経路である場合、すべての経路をエミュレータ内ルーティング・テーブル１４に登録し、それら複数の経路をトラフィックが負荷分散するように経路制御を行う。
【００７８】
その後、トラフィックフロー｛Ｔｉｊｋ｝をこのエミュレータ内のノードへ仮想的に流して、それによってトラフィックが具体的にどの経路を流れていくかを計算する（ステップ４０５）。
【００７９】
すべてのトラフィックフロー｛Ｔｉｊｋ｝に対して、新しい経路が決まると、その時点で全ノード１〜ノードＮ間のリンクに予想されるリンク負荷｛ｃｉｊ：ノードｉ，ｊは隣接｝が求められる（ステップ４０６）。
【００８０】
手順２２５では、これら求められたリンク負荷｛ｃｉｊ｝の中で最大の負荷を持つリンク、ノードｘからノードｙ（ｘ≦Ｎ，ｙ≦Ｎ、ノードｘ，ｙは隣接）を選択する。そして、現在のリンク・メトリック｛ａｉｊ｝の値に対して、このリンク｛ｘ、ｙ｝に対応するリンク・メトリックの値ａｘｙのみに正の数δを足し、これを新しいリンク・メトリック｛ａｉｊ｝として定める（ステップ４０７）。
【００８１】
カウンタを１増加させ（ステップ４０８）、もしカウンタがある閾値Ｍ以上ならば、最適なリンク・メトリックを求める反復計算がある一定の回数を超えたものとみなして、エミュレーションの繰返しを終了し（ステップ４０９）、その時点で得られたリンク・メトリック｛ａｉｊ｝を、新規リンク・メトリック｛Ｂｉｊ｝として、リンク・メトリック送信部３３へ送信する（ステップ４１１）。
【００８２】
また、リンク負荷｛ｃｉｊ｝の各リンクでの値がすべて同じとなる場合にも、既に最適なリンク・メトリックが求められたものとしてエミュレーションの繰返しを終了し（ステップ４１０）、その時点で得られたリンク・メトリック｛ａｉｊ｝を、新規リンク・メトリック｛Ｂｉｊ｝として、リンク・メトリック送信部３３へ送信する（ステップ４１１）。
【００８３】
このいずれの場合でもない時には、再びステップ４０４に戻り、新しいリンク・メトリック｛ａｉｊ｝に基づきエミュレーションを繰返す。
【００８４】
以上により得られた最適なリンク・メトリックは、リンク・メトリック送信部３３により各ノード１〜Ｎに送信される。
【００８５】
また、以上説明されたリンク・メトリック判定部３２の判定処理においては、初期情報であるリンク負荷情報｛Ｃｉｊ｝を使用していないが、この情報は、負荷の量を負荷分散を行なうかどうかの判断として用いる場合、つまり、ある負荷を超えるまで負荷分散を行なわない等の場合に用いることができる。さらに、経路選択エミュレータ３２１が１回目のエミュレーションにより求めたリンク負荷｛ｃｉｊ｝の値と、大きな違いがないかを参照することにより、ネットワーク状態情報を正しく受信しているかのチェックに用いることができる。しかしこのため、リンク負荷情報｛Ｃｉｊ｝は、ネットワーク状態情報の中に含めないものとしても良い。
【００８６】
同様に、初期情報であるトラフィックフロー情報｛Ｔｉｊｋ｝は、トラフィックフローの量の情報として、経路別の情報が必要ではなく、全ての二つのノード間の情報が得られれば良いが、これも、経路選択エミュレータ３２１が１回目のエミュレーションにより求めたトラフィックフロー情報｛ｔｉｊｋ｝の値と、大きな違いがないかを参照することにより、ネットワーク状態情報を正しく受信しているかのチェックに用いることができる。しかしこのため、トラフィックフロー情報は、経路別に集めなくとも良い。
【００８７】
以上のように、本実施の形態では、負荷分散サーバ３０がネットワーク内の全ノード１０ａ，１０ｂ、１０ｃ、１０ｄから、ネットワーク状態を集中的に集め、その情報に基づいて、最適なリンク・メトリックを判定し、動的経路選択をするため、ネットワーク全体での最適な負荷分散を行うことができる。
【００８８】
また、本実施の形態では、定期的にネットワーク状態を取得して、最適なリンク・メトリックを判定するため、ネットワークのトポロジー変更や、トラフィック変動等のネットワーク全体に関る動的な変化に素早く対応して負荷分散を行うことができる。
【００８９】
次に、本発明の第２の実施の形態について、図面を参照して詳細に説明する。
【００９０】
図５は、本発明の第２の実施の形態によるネットワーク負荷分散システムの構成を示すブロック図である。
【００９１】
図５を参照すると、本発明の第２の実施の形態によるネットワーク負荷分散システムの、図１における第１の実施の形態によるネットワーク負荷分散システムとの違いは、負荷分散サーバ３０ａを、データ伝送を行なう各ノードから独立に設置せずに、ハードウエア的に任意の１つのノード４０ａの内部に負荷分散サーバ３０ａの機能を実装したことである。
【００９２】
本実施の形態のネットワーク負荷分散システムの機能的には第１の実施の形態と同じ動作を行う。負荷分散サーバ３０ａを実装するノード４０ａの情報を、ルーティング・プロトコル１５によって交換させることにより（たとえばＯＳＰＦではＯｐａｑｕｅ  ＬＳＡを用いて交換可能である）、負荷分散サーバ３０ａを実装しない全てのノード４０ｂ，４０ｃ，４０ｄが自動的に負荷分散サーバ３０ａを実装するノード４０ａの位置を認識し、負荷分散サーバ３０ａとのやりとりを実現する。
【００９３】
また、負荷分散サーバ３０ａを実装するノード４０ａは、１つでなくとも良く複数のノード内に実装させることができる。この複数のノード内に実装させる場合には、各ノードに実装する負荷分散サーバ３０ａはそれぞれ同等のものであっても、機能を分割して各ノードに実装させてもよい。
【００９４】
以上のように、本実施の形態では、ノード４０ａの内部に負荷分散サーバ３０ａの機能を実装するために、負荷分散サーバ３０ａをデータ伝送を行なう各ノードから独立に設置する必要や、また、負荷分散サーバ３０ａと各ノード４０ａ、４０ｂ，４０ｃ，４０ｄとの通信のために特別に回線を繋ぐ必要がない。このため、、第１の実施の形態の効果に加えて、より簡潔な構成で設置も容易なネットーワーク負荷分散システムを実現できる。
【００９５】
本発明の第３の実施の形態について、図面を参照して詳細に説明する。
【００９６】
図６は、本発明の第３の実施の形態によるネットワーク負荷分散システムの構成を示すブロック図である。
【００９７】
図６を参照すると、本実施の形態によるネットワーク負荷分散システムは、ＡＴＭ交換機５０ａ、５０ｂ、５０ｃ、５０ｄを使用したコネクションレス型のネットワークで実施されている。
【００９８】
第１の実施の形態によるネットワーク負荷分散システムでは、主にコネクションレス型の経路選択の場合について説明した。本発明を、ＡＴＭのように、各データの通信経路を伝送開始前にあらかじめ設定する方式であるコネクション型のネットワークで実施する場合には、以下のように一部制御手順を追加することが望ましい。
【００９９】
負荷分散サーバ３０ｂが、ネットワーク状態情報に対応し、最適な新規リンク・メトリックを計算し、各ＡＴＭ交換機５０ａ、５０ｂ、５０ｃ、５０ｄに通知が終わると、第１の実施の形態を直接適応した場合には、ＡＴＭ交換機５０ａ、５０ｂ、５０ｃ、５０ｄは伝送中のセルについては通信経路の設定を変更せず、新規に伝送要求のあったセルに対してのみ、更新された最適なリンク・メトリックを用いて通信経路を設定し負荷分散を行う。
【０１００】
つまり、既存のコネクションには何も変化を加えない手順である。したがって、第３の実施の形態としては、ＡＴＭ交換機５０ａ、５０ｂ、５０ｃ、５０ｄが最適な新規リンク・メトリックを受け取った時点で、既存のコネクションをすべて新規リンク・メトリックに応じてすべて経路選択を行わせる場合がある。
【０１０１】
この実施の形態の場合、経路選択を行っている間、コネクションが切断され、既存のコネクション上のサービスが瞬断する可能性があるため、既存のＶＣＣ（Ｖｉｒｔｕａｌ  Ｃｈａｎｎｅｌ  Ｃｏｎｎｅｃｔｉｏｎ）を残したまま、まず最適なＶＣＣを設定し、既存のサービスを新規設定したＶＣＣ上に迂回が終了した後に、既存のＶＣＣを切断するなどのサービスの瞬断を防ぐ方式を併用する。
【０１０２】
以上のように、本実施の形態では、第１の実施の形態の効果に加えて、コネクション型のネットワークにおいて負荷分散を行なう時に、既に転送中の通信経路が設定されているデータに対しても最新の最適な経路に設定を変更することにより、性能、効率の良いネットーワーク負荷分散システムを実現できる。
【０１０３】
以上好ましい実施の形態及び実施例をあげて本発明を説明したが、本発明は必ずしも上記実施の形態及び実施例に限定されるものではなく、その技術的思想の範囲内において様々に変形して実施することができる。
【０１０４】
例えば、負荷分散の方針は図４に説明された上述の方法と同様にして、ネットワーク管理者の意図に従い、さまざまな方法をとることが可能である。
【０１０５】
負荷分散を行なうかどうかの判断として、ある負荷を超えるまではまったく負荷分散はおこなわず、ある負荷の閾値を超えた瞬間から負荷分散を行う方法や、たとえ負荷が低くても常に負荷分散を行う方法が、負荷分散の初期情報であるネットワーク状態情報中のリンク負荷情報を参照することにより可能である。
【０１０６】
また、負荷の占める相対的な割合を均等にする負荷分散を行う方法や、負荷による残余帯域を均等にする負荷分散を行う方法が、リンク負荷情報をそれぞれ
（使用帯域／実リンク帯域）つまり使用帯域の量を実リンク帯域の量で割った値として設定したり、または負荷による残余帯域の値として設定することで、図４のフロチャートの流れにより同様に負荷分散が可能である。
【０１０７】
また、第３の実施の形態と第２の実施の形態を組合わせることも可能である。つまり第２の実施の形態の方法により、第３の実施の形態の任意の１つのＡＴＭ交換機５０ａの内部に負荷分散サーバ３０ａの機能を持たせることが可能である。
【０１０８】
【発明の効果】
第１に、ネットワーク全体での最適な負荷分散を行うことができる。
【０１０９】
その理由は、負荷分散サーバがネットワーク内の全ノードから、ネットワーク状態を集中的に集め、その情報に基づいて、最適な負荷分散をはかるための最適なリンク・メトリックを判定し、それを各ノードに配布することと、さらに、その最適なリンク・メトリックがルーティング・プロトコルによってすべてのノードに行き渡り、各ノードのルーティング・テーブルがそのリンク・メトリックに基づき更新されるためである。
【０１１０】
第２に、ネットワークのトポロジー変更や、トラフィック変動等のネットワーク全体に関る動的な変化に対応して、最適なリンク・メトリックを決定し、ルーティング・テーブルを変更できる。
【０１１１】
その理由は、定期的にネットワーク状態を取得して、最適なリンク・メトリックの計算を行うためである。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態によるネットワーク負荷分散システムの構成を示すブロック図である。
【図２】本発明の第１の実施の形態の負荷分散サーバの構成を示すブロック図である。
【図３】本発明の第１の実施の形態のノードの構成を示すブロック図である。
【図４】本発明の第１の実施の形態のリンク・メトリック判定部の、最適なリンク・メトリックの判定処理を説明するためのフローチャートである。
【図５】本発明の第２の実施の形態によるネットワーク負荷分散システムの構成を示すブロック図である。
【図６】本発明の第３の実施の形態によるネットワーク負荷分散システムの構成を示すブロック図である。
【符号の説明】
１０ａ、１０ｂ、１０ｃ、１０ｄ、４０ａ、４０ｂ、４０ｃ、４０ｄ  ノード
５０ａ、５０ｂ、５０ｃ、５０ｄ  ＡＴＭ交換機
２０ａ、２０ｂ、２０ｃ、２０ｄ、２０ｅ、２０ｆ  リンク
１１  ネットワーク状態検出部
１１１  ネットワーク・トポロジー検出部
１１２  リンク・メトリック検出部
１１３  リンク負荷検出部
１１４  トラフィックフロー検出部
１２  リンク・メトリック受信部
１３  リンク状態・データベース
１４  ルーティング・テーブル
１５  ルーティング・プロトコル
１６  データ受信部
１７  データ送信部
３０、３０ａ、３０ｂ  負荷分散サーバ
３１  ネットワーク状態受信部
３２  リンク・メトリック判定部
３２１  経路選択エミュレータ
３３  リンク・メトリック送信部
【図１】
0003546764.tif 000002
【図２】
0003546764.tif 000003
【図３】
0003546764.tif 000004
【図４】
0003546764.tif 000005
【図５】
0003546764.tif 000006
【図６】
0003546764.tif 000007