(57)【要約】【課題】  負荷分散の対象となるサイト（ノード）間の各パスをプローブパケットを用いて状態監視する際、障害発生の検出に時間がかかり、また正常なパスを障害と誤判断した場合の訂正が遅い。【解決手段】  正常、検査、禁止の３つの状態を設ける。正常状態では、Tnorm毎にプローブ要求メッセージを送信する。そして、タイムアウトが生じたら検査状態に遷移して直ちにプローブ要求パケットを複数個(Ｍ個)まとめて（時間間隔をあけずに、連続的に）送って応答を待つ。Ｍ個のプローブ要求パケットが全てタイムアウトしたら禁止状態に遷移する。検査状態、禁止状態において、プローブ応答パケットを受信したら、それがタイムアウトしているかどうかに関わらず正常状態へ復帰する。【選択図】      図１
2005057514.tif 000002
【特許請求の範囲】
【請求項１】
WANを挟んだ一組のノード間のトラヒックを、前記ノード間に存在する複数のパスを利用して負荷分散するマルチホーミング負荷分散方法において、
Ingressノードによって前記複数のパスの内のあるパスに送出されたプローブ要求メッセージに対するEgressノードからのプローブ応答メッセージが一定時間内に戻ってこない場合は、前記Ingressノードから前記あるパスに複数のプローブ要求メッセージを連続的に送出し、該連続的に送出した複数のプローブ要求メッセージおのおのに対するプローブ応答メッセージが一定時間内にいずれも戻ってこない場合は、前記あるパスは障害であると判断して、前記一組のノード間のトラヒックを負荷分散する対象から除外することを特徴とするマルチホーミング負荷分散方法。
【請求項２】
請求項１記載のマルチホーミング負荷分散方法において、
前記あるパスに送出したプローブ要求メッセージに対してプローブ応答メッセージがもどってきた場合は、そのパスは正常と判断することを特徴とするマルチホーミング負荷分散方法。
【請求項３】
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスにプローブ要求メッセージを送出する際は、そのパスのIngressノードが送信時刻を前記プローブ要求メッセージに記入し、それを受信した前記パスのEgressノードはそれをそのまま前記Ingressノードに返信し、前記Ingressノードはプローブ応答メッセージを受信したら現在の時刻と前記記入されている送信時刻との差分で往復遅延時間（RTT）を算出し、次に前記RTTの推定平均値とRTTの推定最小値を更新し、次にRTTの推定平均値とRTTの推定最小値との差分から輻輳RTTを算出し、同一Egressノードとの間にある複数のパスのなかで前記輻輳RTTが最小のパスをその時点で割り当てるべきパスとすることを特徴とするマルチホーミング負荷分散方法。
【請求項４】
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスのEgressノードが受信したプローブ要求メッセージに対して前記パスのIngressノードに返送するプローブ応答メッセージには、少なくとも、前記パスが経由し前記Egressノードが終端するアクセスリンクBにおける平均受信レートDを書き込み、前記Ingressノードは前記プローブ応答メッセージを受信したら、自Ingressノードが終端し、かつ前記パスが経由するアクセスリンクAのリンク容量と平均送信レートCとの差分で空き帯域Xを算出すると共に前記アクセスリンクBのリンク容量と前記プローブ応答メッセージ内に書かれている平均受信レートDとの差分で空き帯域Yを算出し、前記空き帯域Xと前記空き帯域Yとの最小値で前記パスの実効空き帯域を算出し、同一ノードとの間に複数存在するパスの間で前記実効空き帯域が最大のパスをその時点で割り当てるべきパスとすることを特徴とするマルチホーミング負荷分散方法。
【請求項５】
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスのEgressノードが受信したプローブ要求メッセージに対して前記パスのIngressノードに返送するプローブ応答メッセージには、少なくとも、前記パスが経由し前記Egressノードが終端するアクセスリンクBにおける平均受信レートDを書き込み、前記Ingressノードは前記プローブ応答メッセージを受信したら、自Ingressノードが終端し、かつ前記パスが経由するアクセスリンクAのリンク容量で平均送信レートCを割って得られる商で利用率Uを算出すると共に前記アクセスリンクBのリンク容量で前記プローブ応答メッセージ内に書かれている平均受信レートDを割って得られる商で利用率Vを算出し、前記利用率Uと前記利用率Vとの最大値で前記パスの実効利用率を算出し、同一ノードとの間に複数存在するパスの間で前記実効利用率が最小のパスをその時点で割り当てるべきパスとすることを特徴とするマルチホーミング負荷分散方法。
【請求項６】
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスを監視するプローブ応答メッセージは少なくとも前記パスに関する送信データ総量、送信時刻、受信データ総量、受信時刻を含み、現在および前回受信したそれぞれのプローブ応答メッセージにおける送信データ総量の差分と送信時刻の差分との商で入力スループットを算出すると共に現在および前回受信したそれぞれのプローブ応答メッセージにおける受信データ総量の差分と受信時刻の差分との商で出力スループットを算出し、前記出力スループットと前記入力スループットとの商で網効率を算出し、同一ノードとの間に複数存在するパスの中で前記網効率が最大のパスをその時点で割り当てるパスとすることを特徴とするマルチホーミング負荷分散方法。
【請求項７】
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスを監視するプローブ応答メッセージは少なくとも前記パスに関する送信データ総量、受信データ総量を含み、現在および前回受信したそれぞれのプローブ応答メッセージにおける送信データ総量の差分と受信データ総量の差分とからデータ廃棄率を算出し、同一ノードとの間に複数存在するパスの中で前記データ廃棄率が最小のパスをその時点で割り当てるパスとすることを特徴とするマルチホーミング負荷分散方法。
【請求項８】
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスへ送出したプローブ要求メッセージに対するプローブ応答メッセージが戻るたびに、そのメッセージに含まれる情報から第１の輻輳尺度および第２の輻輳尺度を算出し、同一ノードに対して複数あるうちのあるパスが輻輳状態にある場合は、第１の輻輳尺度もしくは第２の輻輳尺度をパス選択尺度とし、前記パスが非輻輳状態にある場合は、輻輳状態で選択されなかった輻輳尺度をパス選択尺度とすることを特徴とするマルチホーミング負荷分散方法。
【請求項９】
複数あるWANにそれぞれ異なるアクセスリンクで接続されるノードAが、アクセスリンクBに障害を検出した場合は、他の正常なアクセスリンク上にリンク状態メッセージを送出し、他のノードCがこれを受け取ったら、前記ノードCは前記ノードAに対して利用可能なパスから前記アクセスリンクBを経由するパスを除外することを特徴とするマルチホーミング負荷分散方法。
【請求項１０】
WANが単一プロバイダーが提供するIP-VPNで与えられる場合は、あるサイトのアクセスリンクと別のサイトのアクセスリンクの組み合わせに対して設定されたIPもしくはGREトンネルで実現されるパスを負荷分散の対象とすることを特徴とする請求項１乃至８の何れか１項に記載のマルチホーミング負荷分散方法。
【請求項１１】
WANがインターネットVPNで与えられる場合は、あるサイトのアクセスリンクと別のサイトのアクセスリンクの組み合わせに対して設定されたIPsec付きのIPトンネルもしくはGREトンネルで実現されるパスを負荷分散の対象とすることを特徴とする請求項１乃至８の何れか１項に記載のマルチホーミング負荷分散方法。
【請求項１２】
WANを挟んだ一組のノード間のトラヒックを、前記ノード間に存在する複数のパスを利用して負荷分散するマルチホーミング負荷分散装置において、
Ingressノードによって前記複数のパスの内のあるパスに送出されたプローブ要求メッセージに対するEgressノードからのプローブ応答メッセージが一定時間内に戻ってこない場合は、前記Ingressノードから前記あるパスに複数のプローブ要求メッセージを連続的に送出し、該連続的に送出した複数のプローブ要求メッセージおのおのに対するプローブ応答メッセージが一定時間内にいずれも戻ってこない場合は、前記あるパスは障害であると判断して、前記一組のノード間のトラヒックを負荷分散する対象から除外するパス監視手段を備えたことを特徴とするマルチホーミング負荷分散装置。
【請求項１３】
請求項１２記載のマルチホーミング負荷分散装置において、
前記パス監視手段は、前記あるパスに対して送出したプローブ要求メッセージに対してプローブ応答メッセージがもどってきた場合は、そのパスは正常と判断する構成を有することを特徴とするマルチホーミング負荷分散装置。
【請求項１４】
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスにプローブ要求メッセージを送出する際に、そのパスのIngressノードが送信時刻を前記メッセージに記入するプローブ送信手段と、
プローブ要求メッセージを受信したらそれをそのままIngressノードに返信する手段と、
プローブ応答メッセージを受信したら現在の時刻と前記記入されている送信時刻との差分で往復遅延時間（RTT）を算出し、次に前記RTTの推定平均値とRTTの推定最小値を更新し、次にRTTの推定平均値とRTTの推定最小値との差分から輻輳RTTを算出するパス監視手段と、
同一ノードとの間にある複数のパスのなかで前記輻輳RTTが最小のパスをその時点で割り当てるべきパスとするパス選択手段とを備えることを特徴とするマルチホーミング負荷分散装置。
【請求項１５】
WANを挟んだ一組のノード間のトラヒックを、前記ノード間に存在する複数のパスを利用して負荷分散するマルチホーミング負荷分散装置において、
受信したプローブ要求メッセージに対してIngressノードに返送するプローブ応答メッセージに、少なくとも前記パスが経由し前記Egressノードが終端するアクセスリンクBにおける平均受信レートDを書き込むパケット転送処理手段と、
前記プローブ応答メッセージを受信したら、前記パスが経由し前記Ingressノード終端するアクセスリンクAのリンク容量と平均送信レートCとの差分で空き帯域Xを算出すると共に前記アクセスリンクBのリンク容量と前記プローブ応答メッセージ内に書かれている平均受信レートDとの差分で空き帯域Yを算出し、前記空き帯域Xと前記空き帯域Yとの最小値で前記パスの実効空き帯域を算出するパス監視手段と、
同一ノードとの間に複数存在するパスの間で前記実効空き帯域が最大のパスをその時点で割り当てるべきパスとするパス選択手段とを備えることを特徴とするマルチホーミング負荷分散装置。
【請求項１６】
WANを挟んだ一組のノード間のトラヒックを、前記ノード間に存在する複数のパスを利用して負荷分散するマルチホーミング負荷分散装置において、
受信したプローブ要求メッセージに対してIngressノードに返送するプローブ応答メッセージに、少なくとも前記パスが経由し前記Egressノードが終端するアクセスリンクBにおける平均受信レートDを書き込むパケット転送処理手段と、
前記プローブ応答メッセージを受信したら、前記パスが経由し前記Ingressノード終端するアクセスリンクAのリンク容量で平均送信レートCを割って得られる商で利用率Uを算出すると共に前記アクセスリンクBのリンク容量で前記プローブ応答メッセージ内に書かれている平均受信レートDを割って得られる商で利用率Vを算出し、前記空き帯域Uと前記空き帯域Vとの最大値で前記パスの実効利用率を算出するパス監視手段と、
同一ノードとの間に複数存在するパスの間で前記実効利用率が最小のパスをその時点で割り当てるべきパスとするパス選択手段とを備えることを特徴とするマルチホーミング負荷分散装置。
【請求項１７】
WANをはさんだ一組のノード間に複数存在して負荷分散の対象となるおのおののパスを監視するプローブメッセージに少なくとも前記パスに関する送信データ総量、送信時刻、受信データ総量、受信時刻を書き込むパケット転送処理手段と、
現在および前回受信したそれぞれのプローブ応答メッセージにおける送信データ総量の差分と送信時刻の差分との商で入力スループットを算出すると共に現在および前回受信したそれぞれのプローブ応答メッセージにおける受信データ総量の差分と受信時刻の差分との商で出力スループットを算出し、前記出力スループットと前記入力スループットとの商で網効率を算出するパス監視手段と、
同一ノードとの間に複数存在するパスの中で前記網効率が最大のパスをその時点で割り当てるパスとするパス選択手段とを備えることを特徴とするマルチホーミング負荷分散装置。
【請求項１８】
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスに対して、少なくとも前記パスに関する送信データ総量、受信データ総量を書き込むパケット転送処理手段と、
現在および前回受信したそれぞれのプローブ応答メッセージにおける送信データ総量の差分と受信データ総量の差分とからデータ廃棄率を算出するパス監視手段と、
同一ノードとの間に複数存在するパスの中で前記データ廃棄率が最小のパスをその時点で割り当てるパスとするパス選択手段とを備えることを特徴とするマルチホーミング負荷分散装置。
【請求項１９】
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスへ送出したプローブ要求メッセージに対するプローブ応答メッセージが戻るたびに、そのメッセージに含まれる情報から第１の輻輳尺度および第２の輻輳尺度を算出し、同一ノードに対して複数あるうちのあるパスが輻輳状態にある場合は、第１の輻輳尺度もしくは第２の輻輳尺度をパス選択尺度とし、前記パスが非輻輳状態にある場合は、輻輳状態で選択されなかった輻輳尺度をパス選択尺度とするパス監視手段を備えることを特徴とするマルチホーミング負荷分散装置。
【請求項２０】
複数あるWANにそれぞれ異なるアクセスリンクで接続されるノードAが、アクセスリンクBに障害を検出した場合は、他の正常なアクセスリンク上にリンク状態メッセージを送出する手段と、前記リンク状態メッセージを受信したら、前記ノードAに対して利用可能なパスの中から前記アクセスリンクBを経由するパスを除外するテーブル管理手段とを備えることを特徴とするマルチホーミング負荷分散装置。
【請求項２１】
WANが単一プロバイダーが提供するIP-VPNで与えられる場合は、負荷分散の対象となるパスを実現するために、あるサイトのアクセスリンクと別のサイトのアクセスリンクの組み合わせに対してIPもしくはGREトンネルを終端するパケット転送処理手段を備えることを特徴とする請求項１２乃至１９の何れか１項に記載のマルチホーミング負荷分散装置。
【請求項２２】
WANがインターネットVPNで与えられる場合は、負荷分散の対象になるパスを実現するために、あるサイトのアクセスリンクと別のサイトのアクセスリンクの組み合わせに対してIPsec付きのIPもしくはGREトンネルを終端するパケット転送処理手段を備えることを特徴とする請求項１２乃至１９の何れか１項に記載のマルチホーミング負荷分散装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークにおける負荷分散技術に関し，特にプロバイダーのVPNサービスにマルチホーミングを行うサイトを含むプライベート網において、各サイト間の制御のみで実現されるマルチホーミング負荷分散方法および装置に関する。
【背景技術】
【０００２】
図３５〜図３７は、プロバイダーが提供するVPN（Virtual Private Network）サービスを用いて構築されたプライベート網１７１〜１７３を示す。ここでプライベート網１７１〜１７３の例としては、企業等が本店と地理的に散らばる複数の支店とをつなぐために構築したものがある。プライベート網１７１〜１７３はサイト１１〜１３と、アクセスリンク２１〜２６と、WAN(Wide Area Network)３１〜３５とから構成される。WAN３１〜３５には複数のサイト１１〜１３がアクセスリンク２１〜２６を用いて接続される。ここでWANはプロバイダーが設備として持つ物理的実体をさし、一方VPNはその上でユーザに提供されるサービス機能をさすものとして区別する。
【０００３】
次に、WAN３１〜３５について説明する。これは、各サイト１１〜１３が基本的に単一のアクセスリンク２１〜２６でWAN３１〜３５に接続していれば任意のサイト間でのデータ通信が可能になる機能を提供する（例えば、非特許文献１参照）。なお、北米では、Jon Harrison, ”VPN Technologies- A comparison”, Data Connection, white paper, Feburuary 2003,＜http://www.dataconnection.com/iprouting/wpdl.htm ＞にあるように、これらをそれぞれ、Vritual Private LAN Service, BGP/MPLS VPN, CE-based VPNと呼ぶ場合がある。
【０００４】
広域イーサネット（登録商標）はイーサネット技術に基づいてレイヤ２レベルで各サイト１１〜１３間を接続するVPNサービスである。またIP-VPNは、転送プロトコルをIPに限定して、サイト１１〜１３間を接続するVPNサービスである。ここではRFC ２５４７BGP/MPLS VPNs、 March 1999に基づき、各サイト１１〜１３のアクセスリンクを収容するWAN３１〜３５側のプロバイダーエッジルータ間にはMPLSのLSPが設定されている。
【０００５】
広域イーサネットおよびIP-VPNがいずれもプロバイダーが運用する専用網上で提供される一方で、インターネットVPNは、プロバイダーがインターネット接続サービス用に運用する公衆網上で、各サイト間にRFC2406、 IP encapsulating security payload(ESP)， November 1998でその暗号化および認証方法が規定されているIPsecトンネルモードによるパスを設定したものである。この暗号化および認証で用いる鍵や利用するアルゴリズムはESPヘッダー内のSPIフィールドで指定される。
【０００６】
図３５は２つの異なるプロバイダーが提供するWAN３１，３２を用いて構築されたプライベート網１７１であり、各サイト１１〜１３は、それぞれのWAN３１，３２に異なるアクセスリンク２１〜２６で接続されている。ここでは、後述の負荷分散の説明を容易にするため、アクセスリンク２１，２２はWAN３１，３２からサイト１１方向を強調した矢印で示しているが、双方向のトラヒックを流す。また、同じ理由で、アクセスリンク２３〜２６はサイト１２，１３からWAN３１，３２方向を強調した矢印で示しているが、双方向のトラヒックを流す。この２つのWAN３１，３２には広域イーサネット、IP-VPN、インターネットVPNの中から任意の２つの組み合わせがありうる。
【０００７】
図３６は同一のプロバイダーのWAN３４が広域イーサネットで実現されている場合のプライベート網１７２である。この場合、各サイト１１〜１３に２本ずつあるアクセスリンク２１〜２６は、それぞれ、同一WAN３４の中の異なるVLAN１およびVLAN２に接続されている。
【０００８】
図３８はイーサネットフレームとVLANフレームの説明図である。イーサネットフレームは、宛先MACアドレス、発信MACアドレス、Type/Length、データ、FCSの各フィールドからなる。Type/Lengthはデータのプロトコルの識別子、もしくはデータ長が入る。データには、IPパケットもしくはIP-ARPフレームが入る。FCSはCRCチェックを行うための情報が入っている。一方、VLANフレームは、イーサネットフレームの発信MACアドレスとType/Lengthフィールドの間にTPID(Tag Protocol Identifier)とTCI(Tag Control Information)が挟まれる。TPIDはイーサネットの場合は「0x8100」を設定する。そのイーサネットのデータフィールドに含まれるプロトコルはTypeで識別される場合がある。TPIDが「0x8100」 以外ならば、そのフレームはTPID,TCIを含まない通常のイーサネットフレームとして処理される。例えば、TPIDが「0x800」ならば、それはIPパケットをデータフィールドにもつ通常のイーサネットフレームとなる。TCIは更に優先ビット、TRビット、VLAN-IDの各フィールドから構成される。
【０００９】
図３７はWAN３５が、同一のプロバイダーのIP-VPN、もしくはインターネットVPNで実現されているプライベート網１７３である。各サイト１１〜１３に２本ずつあるアクセスリンク２１〜２６は同時にWAN３５に接続されている。
【００１０】
図３９はサイト１１の構成例を示すブロック図であり、ノード４と、アクセスリンク２１，２２と、LAN５１，５２と、内部リンク１１１，１１２とから構成される。
【００１１】
ノード４は、LAN５１，５２と内部リンク１１１，１１２で接続されると同時に、複数のWANにアクセスリンク２１，２２で接続される。LAN５１，５２は、１つもしくは複数のデータ端末を収容する。ここでデータ端末の例としてはデスクトップPCや業務用サーバがある。ノード４はWANからのトラヒックを各LAN５１，５２に振り分けるエッジルーチングの機能と、LAN５１，５２から他のサイト向けのトラヒックを各WANに振り分ける負荷分散の役割とを果たす。
【００１２】
図４０はノード４の構成を示すブロック図である。ノード４は、内部リンク１１１，１１２と、エッジルータ１２１，１２２と、レイヤ３スイッチ１３とから構成される。エッジルータ１２１，１２２は、WANとアクセスリンク２１，２２で接続され、各アクセスリンク２１，２２のレイヤ２プロトコルを終端する。これには、イーサネット、PPP等がある。レイヤ３スイッチ１３は、内部リンク１１１，１１２でLAN５１，５２やエッジルータ１２１，１２２に接続され、その上でイーサネットに基づくレイヤ２プロトコルを終端する。そしてLAN５１，５２内のトラヒックに対するレイヤ２スイッチング、および異なるLAN５１，５２間のトラヒックに対するレイヤ３スイッチングを行うとともに、他のサイト向けのトラヒックをエッジルータ１２１および１２２に振り分ける負荷分散の役割を果たす。
【００１３】
次に、各サイト１１〜１３を複数のアクセスリンク２１〜２６でWAN３１〜３５に接続することはマルチホーミングと呼ばれるが、以下その目的を説明する。これは各サイト１１〜１３間の通信経路（以下パスと呼ぶ場合もある）のどこかで障害が発生しても、別の通信経路を用いることで通信の可用性を維持することを目的とする。
【００１４】
具体的には、図３５では、各サイト１１〜１３が異なるプロバイダーが提供するWAN３１，３２にそれぞれ接続されている。一方、図３６は、各サイト１１〜１３が、同一のプロバイダーが提供するWAN３４に２本のアクセスリンク２１〜２６で接続されている。そこで、図３５において、サイト１１とサイト１２の間で、アクセスリンク２１、WAN３１、およびアクセスリンク２３を経由するパス１６５上で障害が発生すれば、いままでそのパスに振り分けられていたトラヒックはすべて、アクセスリンク２２、WAN３２、およびアクセスリンク２４を含むパス１６６に振り向けられる。これを障害切替と呼ぶ。
【００１５】
ところが、こうした２つのパスを現用と予備という形で片方のみを使っている場合は、予備のアクセスリンクに無駄が生じるため、各サイト１１〜１３では負荷分散を行い、２本あるアクセスリンクを同時に使用する。例えば、図３５に示すように、サイト１２からサイト１１へのトラヒックにおいて、アクセスリンク２３、WAN３１、およびアクセスリンク２１を経由するパス１６５には５０％を振り分け、アクセスリンク２４、WAN３２、およびアクセスリンク２２を経由するパス１６６には５０％を振り分ける。またサイト１３からサイト１１へのトラヒックにおいて、アクセスリンク２５、WAN３１、およびアクセスリンク２１を経由するパス１６７には２０％を割り振り、アクセスリンク２６、WAN３２、およびアクセスリンク２２を経由するパス１６８には８０％を割り振る。
【００１６】
サイト１２、およびサイト１３がそれぞれ、アクセスリンク２３，２４のサイト１２から各WAN方向、およびアクセスリンク２５、２６のサイト１３から各WAN方向の負荷分散のみを考えるのであれば、ローカルなアクセスリンクの状況のみを用いる負荷分散装置がある（例えば、非特許文献２参照）。
【００１７】
しかし、宛先サイト１１のアクセスリンク２１，２２における、各WAN３１，３２からサイト１１方向の負荷も考えると、これでは不十分である。その理由について説明する。サイト１１においてアクセスリンク２１，２２の各WAN３１，３２からサイト１１の方向の負荷を制御するとすれば、ここへはサイト１２および１３からそれぞれトラヒックが流れてくるため、サイト１２，１３は、それぞれローカルなアクセスリンク２３，２４および２５，２６のみならず、宛先のサイト１１につながるアクセスリンク２１，２２の状況も考慮して、負荷分散の比率を決定する必要がある。これはすなわち各アクセスリンクのWANへの上りおよびWANからの下り側の双方の負荷を均衡させるには、各宛先サイトに対して複数あるパス単位で分散比率を決める必要があることを意味する。
【００１８】
次に、同一のリモートサイト単位で複数あるパス１６５〜１６８に対して上記のように与えられた比率で負荷分散する方法について説明する（例えば、非特許文献３参照）。まず前提条件として、あるリモートサイト向けのパケットに対してパスを選択する際は、少なくとも同一宛先アドレスを持つパケットの順序の入替えを防止するように行われる。このために、同一の宛先アドレス、もしくは同一の宛先アドレスと発信アドレスの組と言った識別情報が同一であるパケットの集合をフローと定義し、同一フローに属するパケットは同一パスに転送する。こうしたフローの識別情報の別の例としては、IPヘッダーに含まれるプロトコル番号と、TCP(Transmission Control Protocol),UDP(User Datagram Protocol)に含まれる送信ポートアドレス、受信ポートアドレスを、前述の送信IPアドレスと受信IPアドレスに加えた５項の組み合わせがある。
【００１９】
同一フローに属するパケットを同一パスに転送することを実現するため、あらかじめ、リモートサイト毎に、識別子に対するハッシュ値で構成される空間を分割しておく。この分割は各パスに割り当てる分割比に比例して行われる。そしてフローの識別情報に対するハッシュ値が同じものをストリームと呼び、同一ストリームは同一パスに転送するようにする。例えばハッシュ値としてCRC８による剰余を用いる場合、図３５でサイト１２から１１へ転送すべきパケットに対しては、ハッシュ値が０から１２７のストリームにはパス１６５を割り当て、ハッシュ値が１２８から２５５のストリームにはパス１６６を割り当てることで、負荷分散比率を５０：５０にする。またサイト１３から１１へ転送すべきパケットに対しては、ハッシュ値が０から５１のストリームにはパス１６７を割り当て、ハッシュ値が５２から２５５のストリームはパス１６８を割り当てることで、負荷分散比率を２０：８０にする。なお、この場合OSPFを運用していてもかまわない。一般にOSPFではコストが等しい複数のパスに対しては、負荷状況を把握するメカニズムをもともと持たないのでトラヒックを等分するのが基本であるが、このようなハッシュ空間の分割による等分ではない負荷分散をすることもできる。なお、これはパスを各ストリームに対して固定的に割り当てるものであり、静的負荷分散と呼ぶ。
【００２０】
次に、プライベート網１７１上でOSPFを運用することで実現する障害切替について説明する。OSPFは図３５でWAN３１、３２がいずれも広域イーサネットサービスで提供される場合に用いられる。ここで各WANは一つのブロードキャストネットワークとして扱われる。あるサイト１１のエッジルータ１２１が、他のサイト１３の別のエッジルータ１２２との間で、Helloプロトコルによる交換メッセージが一定時間内に受信できなかった場合は、その障害情報を反映したリンク状態メッセージを他のエッジルータ１２２やレイヤ３スイッチ１３に通知する。これを受けたレイヤ３スイッチ１３は障害状態にあるパスへのパケットの転送をやめる。
【００２１】
なお図３７でWAN３５がIP-VPNで提供される場合には、各サイト１１〜１３からみると他のサイトにつながるアクセスリンク毎にパスを明示的に設定する仕組みが無い。よって、WAN３５から各サイト向けのトラヒックに対しては、プロバイダーがサービスを提供するWAN３５との間でBGPメッセージをやりとりしてユーザとプロバイダーの各装置が連携をとることでアクセスリンク上での負荷分散／障害回復が実現される（例えば、非特許文献４参照）。一方、各サイト１１〜１３からWAN３５向けのトラヒックは、先に示したようにハッシングに基づいて２つあるアクセスリンク上にパケットを振り分けることができる。
【００２２】
図４１はインターネットVPNにおける信頼性向上の方法を説明する図である（例えば、非特許文献５参照）。単一もしくは複数のプロバイダーが提供するインターネットによって構成されるWAN３６に対して、各サイトは複数のアクセスリンク２１〜２６で接続している。なお、WAN３６は単一のISP網だけではなく、複数のISP網から構成されていてもよい。その場合、各サイトの各々のアクセスリンクは異なるISP網に接続される場合がある。各サイトに設置されたノード４３〜４５は、それぞれVPN装置１４１〜１４３と、負荷分散装置１５１〜１５３と、エッジルータ１２１〜１２６とから構成される。
【００２３】
各サイトのVPN装置１４１〜１４３間ではIPsecに基づくトンネルが１本のみ設定される。一方、各サイトの負荷分散装置１５１〜１５３間には、対向するエッジルータ１２１〜１２６の組み合わせ単位にパスが設定される。例えば、図４１に示すように、負荷分散装置１５１，１５２の間には、エッジルータ１２１と１２２、および１２３と１２４との４つの組み合わせに応じて、４本のパスが設定されている。
【００２４】
図４２は各パス上での負荷分散の仕組みを説明する図である。これは図４１からノード４３，４４のエッジルータ１２１〜１２４と負荷分散装置１５１，１５２のみを取り出したものである。各パス１６１〜１６４にはプローブパケットを転送してそのパスの輻輳／障害情報を把握する。パス１６１では矢印で示すように、負荷分散装置１５１が他のサイト１の負荷分散装置１５２に送信タイムスタンプを記入したプローブ要求メッセージ（具体的にはICMP(Internet Control and Management Protocol) Echo request）を出し、それに対するプローブ応答メッセージ（具体的にはICMP Echo reply）が負荷分散装置１５２から戻ってきたら、現時刻から送信タイムスタンプを引いて、往復時間であるRTT（Round Trip Time）を算出する。これを定期的に各パスで測っておき、あらたにフローが発生した場合は、その時点で正常なパスであって、かつRTTが最も小さなパスを割り当てる。なお、同じフローに属するパケットでも、到着間隔が一定時間以上あいた場合は、その時点でRTTが最小であるパスを新たに割当てる。こうしたパスの割当て方は、先にハッシュ値に基づくパスの割当て方を静的負荷分散と呼ぶのに対して、動的負荷分散と呼ぶ。なお、プローブパケットを実現する手段としてはICMP EchoもしくはTCPのsyn, syn+ackセグメントがある。ここで、ノード４３のようにプローブ要求パケットを送出するノードをIngressノード、ノード４４のようにそれを受信してプローブ応答パケットを返送するノードをEgressノードと呼ぶことにする。
【００２５】
図４３はプローブパケットに基づいてパスが正常か障害かを監視するための状態遷移図である。これはhttp://www.nagios.org/にあるNagioと呼ばれるサーバ監視ツールにおける死活監視をパスの状態監視に応用したものである。状態は正常と障害とからなる。いずれの状態においても各ノードはパス毎かつ一定時間Tsend毎にプローブ要求メッセージ（具体的にはICMP Echo request）を転送し、それに対するプローブ応答メッセージ（具体的にはICMP Echo reply）が戻ってくるのを待つ。正常状態において、あるプローブ要求メッセージを送信してからM*Tsend以内に任意のプローブ応答メッセージが戻らない（タイムアウト発生）の場合は、障害状態に遷移して、そのパスを負荷分散対象から除外する。また、障害状態においてプローブ要求メッセージを送信してからM*Tsend時間以内に任意のプローブ応答パケットを受信した場合は正常状態に遷移させ、そのパスを負荷分散の対象として新たにベストなパスを決定する。タイムアウト判定時間を送出間隔より大きな値にするのは、１回のプローブパケットのタイムアウトだけでは必ずしも障害か、輻輳により廃棄されるもしくは遅延したのか区別がつけがたいので、Ｍ個のプローブパケットが連続してタイムアウトしたら障害と判断することで、システムを安定に動作させるためである。
【非特許文献１】日経コミュニケーション、2002年12月2日、ｐ．54〜71
【非特許文献２】F5社<サイトhttp://www.f5.com/f5products/bigip/LinkController/>
【非特許文献３】Curtis Villaminzer, “OSPF（Opens Shortest Path First） Optimized Multipath”, IETF Internet-draft draft-ietf-ospf-omp-03, January 2002
【非特許文献４】「IP-VPNを支える技術とサービスの活用法」〜エクストラネットとVoIPを実現するMPLS・BGPのルーティング設計〜鈴木淳也、2003年1月10日、<http://www.atmarkit.co.jp/fnetwork/tokusyuu/17ipevent/ipevent03.html>
【非特許文献５】「Mulit-Link Technology」、StoneSoft社、2001年10月
【発明の開示】
【発明が解決しようとする課題】
【００２６】
第１番目の課題は、障害検出が遅いことである。なぜなら、まずOSPFやBPGでは、ルータ間で障害が発生したことを隣接ルータからメッセージが届かないことで検出する仕組みがあるが、それは数十秒と設定されており、その時間分だけ遅れるからである。その上、そのリンク状態に基づいた情報が各サイトのルータに通知され、さらにそれが到達したルータで経路表を書き換えるのに時間がかかるからである。また、OSPFもBGPも運用されていない状況で、プローブパケットにより障害検出する場合でも、少なくともプローブ送出間隔のM倍の時間待つ必要があるからである。
【００２７】
第２番目の課題は、RTTの最小なパスを選択する負荷分散方法では、WANがボトルネックにならず、かつ負荷が比較的小さな範囲では、伝搬遅延の小さなパス、もしくは経由するアクセスリンクの容量が大きなパスに負荷が偏るおそれがある。以下その理由について説明する。RTTは
RTT=（伝搬遅延の往復の合計）＋（プローブパケットの各アクセスリンクの上り／下りにおける伝送時間）＋（各アクセスリンクの上り／下りにおける転送待ちによる時間）
で与えられ、上記転送待ちによる遅延は、アクセスリンクの負荷が小さければ、伝搬遅延やパケット送信時間に比べて無視できる。よって、輻輳レベルが低いと、伝搬遅延の小さい、もしくは容量が大きなアクセスリンクを経由するパスのRTTは絶えず小さくなるからである。
【００２８】
第３番目の課題は、プローブパケットによる障害検出に時間がかかるということである。なぜなら、プローブ要求メッセージの送信間隔Tに対して、障害検出までにそのＭ倍の時間がかかるからである。
【００２９】
第４番目の課題は、ノードの構成が複雑になる。なぜなら、アクセスリンク毎にエッジルータを設置し、それらに対してレイヤ３スイッチもしくは負荷分散装置を設置して負荷分散しなければならないからである。
【００３０】
第５番目の課題は、図３７のプライベート網１７３において、WAN３５が特にIP-VPNサービスで実現され、あるサイト１１が同一の前記WAN３５に複数のアクセスリンク２１，２２で接続する場合、前記WAN３５からそのサイト向けのトラヒックをサイト間のみの制御で負荷分散することができないことである。なぜなら、サイト間で異なるアクセスリンクの組み合わせ毎にパスを識別する仕組みが、IP-VPNサービスからは提供されないからである。また、たとえ、プロバイダー網との連携でできたとしても、その粒度は宛先ネットワークアドレス単位である。なぜなら、BGPは宛先ネットワークアドレス単位でベストパスを唯一選択する仕組みにもとづくからである。
【００３１】
そこで、本発明の目的は、対地毎に、障害／輻輳状況に基づいて高速かつ適切にかつネットワークアドレスよりも細かい粒度でパス割り当てできるようにすることにある。
【課題を解決するための手段】
【００３２】
本発明にかかる第１のマルチホーミング負荷分散装置は、パスの障害を迅速に検出できるようにするため、
WANを挟んだ一組のノード間のトラヒックを、前記ノード間に存在する複数のパスを利用して負荷分散するマルチホーミング負荷分散装置において、
Ingressノードによって前記複数のパスの内のあるパスに送出されたプローブ要求メッセージに対するEgressノードからのプローブ応答メッセージが一定時間内に戻ってこない場合は、前記Ingressノードから前記あるパスに複数のプローブ要求メッセージを連続的に送出し、該連続的に送出した複数のプローブ要求メッセージおのおのに対するプローブ応答メッセージが一定時間内にいずれも戻ってこない場合は、前記あるパスは障害であると判断して、前記一組のノード間のトラヒックを負荷分散する対象から除外するパス監視手段を備える。
【００３３】
また、本発明にかかる第２のマルチホーミング負荷分散装置は、実際には正常なパスを、誤って正常でないと判断した状態から正常と判断するまでの時間を早めるため、第１のマルチホーミング負荷分散装置において、
前記パス監視手段は、前記あるパスに対して送出したプローブ要求メッセージに対してプローブ応答メッセージがもどってきた場合は、そのパスは正常と判断する構成を有する。
【００３４】
本発明にかかる第３のマルチホーミング負荷分散装置は、輻輳RTTが最小のパスを選択できるようにするため、
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスにプローブ要求メッセージを送出する際に、そのパスのIngressノードが送信時刻を前記メッセージに記入するプローブ送信手段と、
プローブ要求メッセージを受信したらそれをそのままIngressノードに返信する手段と、
プローブ応答メッセージを受信したら現在の時刻と前記記入されている送信時刻との差分で往復遅延時間（RTT）を算出し、次に前記RTTの推定平均値とRTTの推定最小値を更新し、次にRTTの推定平均値とRTTの推定最小値との差分から輻輳RTTを算出するパス監視手段と、
同一ノードとの間にある複数のパスのなかで前記輻輳RTTが最小のパスをその時点で割当てるべきパスとするパス選択手段とを備える。
【００３５】
また、本発明にかかる第４のマルチホーミング負荷分散装置は、実効空き帯域が最大のパスを選択できるようにするため、
WANを挟んだ一組のノード間のトラヒックを、前記ノード間に存在する複数のパスを利用して負荷分散するマルチホーミング負荷分散装置において、
受信したプローブ要求メッセージに対してIngressノードに返送するプローブ応答メッセージに、少なくとも前記パスが経由し前記Egressノードが終端するアクセスリンクBにおける平均受信レートDを書き込むパケット転送処理手段と、
前記プローブ応答メッセージを受信したら、前記パスが経由し前記Ingressノード終端するアクセスリンクAのリンク容量と平均送信レートCとの差分で空き帯域Xを算出すると共に前記アクセスリンクBのリンク容量と前記プローブ応答メッセージ内に書かれている平均受信レートDとの差分で空き帯域Yを算出し、前記空き帯域Xと前記空き帯域Yとの最小値で前記パスの実効空き帯域を算出するパス監視手段と、
同一ノードとの間に複数存在するパスの間で前記実効空き帯域が最大のパスをその時点で割り当てるべきパスとするパス選択手段とを備える。
【００３６】
また、本発明にかかる第５のマルチホーミング負荷分散装置は、実効利用率が最も低いパスを選択できるようにするため、
WANを挟んだ一組のノード間のトラヒックを、前記ノード間に存在する複数のパスを利用して負荷分散するマルチホーミング負荷分散装置において、
受信したプローブ要求メッセージに対してIngressノードに返送するプローブ応答メッセージに、少なくとも前記パスが経由し前記Egressノードが終端するアクセスリンクBにおける平均受信レートDを書き込むパケット転送処理手段と、
前記プローブ応答メッセージを受信したら、前記パスが経由し前記Ingressノード終端するアクセスリンクAのリンク容量で平均送信レートCを割って得られる商で利用率Uを算出すると共に前記アクセスリンクBのリンク容量で前記プローブ応答メッセージ内に書かれている平均受信レートDを割って得られる商で利用率Vを算出し、前記空き帯域Uと前記空き帯域Vとの最大値で前記パスの実効利用率を算出するパス監視手段と、
同一ノードとの間に複数存在するパスの間で前記実効利用率が最小のパスをその時点で割り当てるべきパスとするパス選択手段とを備える。
【００３７】
また、本発明にかかる第６のマルチホーミング負荷分散装置は、網効率が最大のパスを選択できるようにするため、
WANをはさんだ一組のノード間に複数存在して負荷分散の対象となるおのおののパスを監視するプローブメッセージに少なくとも前記パスに関する送信データ総量、送信時刻、受信データ総量、受信時刻を書き込むパケット転送処理手段と、
現在および前回受信したそれぞれのプローブ応答メッセージにおける送信データ総量の差分と送信時刻の差分との商で入力スループットを算出すると共に現在および前回受信したそれぞれのプローブ応答メッセージにおける受信データ総量の差分と受信時刻の差分との商で出力スループットを算出し、前記出力スループットと前記入力スループットとの商で網効率を算出するパス監視手段と、
同一ノードとの間に複数存在するパスの中で前記網効率が最大のパスをその時点で割り当てるパスとするパス選択手段とを備える。
【００３８】
また、本発明にかかる第７のマルチホーミング負荷分散装置は、データ廃棄率が最小のパスを選択できるようにするため、
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスに対して、少なくとも前記パスに関する送信データ総量、受信データ総量を書き込むパケット転送処理手段と、
現在および前回受信したそれぞれのプローブ応答メッセージにおける送信データ総量の差分と受信データ総量の差分とからデータ廃棄率を算出するパス監視手段と、
同一ノードとの間に複数存在するパスの中で前記データ廃棄率が最小のパスをその時点で割り当てるパスとするパス選択手段とを備える。
【００３９】
本発明にかかる第８のマルチホーミング負荷分散装置は、伝送遅延の小さなパスや、容量が大きなリンクが含まれるパスに負荷が偏らないようにするため、
WANをはさんだ一組のノード間に複数存在して前記ノード間のトラヒックを負荷分散する対象となるパスへ送出したプローブ要求メッセージに対するプローブ応答メッセージが戻るたびに、そのメッセージに含まれる情報から第１の輻輳尺度および第２の輻輳尺度を算出し、同一ノードに対して複数あるうちのあるパスが輻輳状態にある場合は、第１の輻輳尺度もしくは第２の輻輳尺度をパス選択尺度とし、前記パスが非輻輳状態にある場合は、輻輳状態で選択されなかった輻輳尺度をパス選択尺度とするパス監視手段を備える。
【００４０】
本発明にかかる第９のマルチホーミング負荷分散装置は、障害の発生したパスを迅速に検出できるようにするため、
複数あるWANにそれぞれ異なるアクセスリンクで接続されるノードAが、アクセスリンクBに障害を検出した場合は、他の正常なアクセスリンク上にリンク状態メッセージを送出する手段と、前記リンク状態メッセージを受信したら、前記ノードAに対して利用可能なパスの中から前記アクセスリンクBを経由するパスを除外するテーブル管理手段とを備える。
【００４１】
本発明にかかる第１０のマルチホーミング負荷分散装置は、IP-VPNにおいて、ユーザのノード間のみの制御でアクセスリンクにWANからノード（サイト方向）の負荷分散も可能にするため、
WANが単一プロバイダーが提供するIP-VPNで与えられる場合は、負荷分散の対象となるパスを実現するために、あるサイトのアクセスリンクと別のサイトのアクセスリンクの組み合わせに対してIPもしくはGREトンネルを終端するパケット転送処理手段を備える。
【００４２】
本発明にかかる第１１のマルチホーミング負荷分散装置は、インターネットVPNにおいて、ユーザのノード間のみの制御でアクセスリンクにWANからノード（サイト方向）の負荷分散も可能にするため、
WANがインターネットVPNで与えられる場合は、負荷分散の対象になるパスを実現するために、あるサイトのアクセスリンクと別のサイトのアクセスリンクの組み合わせに対してIPsec付きのIPもしくはGREトンネルを終端するパケット転送処理手段を備える。
【００４３】
図１はパスの状態管理を行うための状態遷移図である。ここではパスの監視状態を、正常、検査、禁止の３状態を設け、それぞれの状態でプローブ要求メッセージを送出し、それに対するプローブ応答メッセージの返り方に応じて状態遷移を行う。ここで、検査状態をもうけるのは、保守目的でそのパスを意図的に使用不能にしている場合も考慮してのことである。正常状態でTnorm毎にプローブ要求メッセージを送出し、それから一定時間Tprob内にプローブ応答メッセージを受信できない場合（タイムアウト発生）は、検査状態に遷移する。ここではタイムアウト発生の原因が、障害なのか輻輳なのかを判別するために、プローブ要求メッセージをまとめてＭ個（複数）生成して連続的に送出し、それらすべてにタイムアウトが発生した場合は禁止に状態遷移する。禁止状態ではTfail時間毎にプローブ要求メッセージを送出し、タイムアウトした場合はその状態にとどまる。任意の状態においてプローブ応答メッセージ一つでも戻ってきた場合は、それがタイムアウトの如何にかかわらずTprobを更新して正常状態にする。
【００４４】
検査状態をもうけたのは、図４３に状態遷移図を示した従来技術が一定時間毎に送出するＭ個のプローブパケットがすべてタイムアウトしたら障害と見なすのに対して、Ｍ個のパケットを、時間間隔をあけずに、連続的にまとめて送信し、全てタイムアウトしたら障害と見なすことで、障害検出を早めるためである。更に、タイムアウトする時間を適応的に変更することでも、障害検出時間を早めようとしている。また、従来技術と異なり、監視状態が禁止もしくは検査においてプローブ要求メッセージが戻ってきてそれがタイムアウトしていても監視状態を正常に復帰させる。こうして輻輳を障害と誤判断する確率を下げている。
【００４５】
図２はリンク状態管理に基づく障害切替の原理を説明する図である。ノード４１は、アクセスリンク２１に障害を検出したら(a)、ノード４２宛のトラヒックをパス１６１に振り分けるのをやめ、ノード４２宛のトラヒックはすべてパス１６２に振り分けるようにする(b)。それと同時に別の正常なアクセスリンク２２を経由してノード４２にアクセスリンク２１が障害であることを通知する（c）。これを受信したノード４２は、直ちにノード４１宛のトラヒックをパス１６１に振り分けることをやめ、ノード４１宛のトラヒックは全てパス１６２に送る。
【発明の効果】
【００４６】
第１の効果は、パスの障害を迅速に検出できることである。なぜなら、従来は、一定時間毎に送出していたＭ個のプローブパケットが全てタイムアウトしたら障害と見なすのに対して、本発明では、Ｍ個のプローブパケットを連続的にまとめて送出し、全てがタイムアウトしたら障害と見なすようにしているからである。
【００４７】
第２の効果は、プローブパケットのタイムアウトにより障害と誤判断（輻輳を障害と誤判断）しても、そこから正常と正しく判断するまでの時間が早まることである。なぜなら、タイムアウトにより障害と判断後は直ちに１つもしくは複数のプローブ要求メッセージを送出し、それに対して１つでもプローブ応答メッセージが戻ってきたら正常と判断するからである。
【００４８】
第３の効果は、輻輳レベルが低い場合、伝搬遅延の小さなパス、あるいは容量の大きなリンクが含まれるパスに負荷が偏らないことである。なぜなら、加わる負荷が小さく輻輳レベルが低い状態では、測定される負荷に基づいてパス選択を行ない、加わる負荷が大きく輻輳レベルが高い状態では、輻輳による遅延に基づいてパス選択を行うからである。
【００４９】
第４の効果は遅延のみならずスループットを考慮したパス選択が可能となることである。なぜなら、各アクセスリンクの転送レートの情報をフィードバックさせるからである。
【００５０】
第５の効果は、IP-VPNにおいてユーザのエッジノード間のみの制御で、アクセスリンクのWANからサイト方向へのへの負荷分散が可能になることである。なぜなら、各サイト間でのアクセスリンクの組み合わせの単位でIPもしくはGREトンネルを設定するからである。
【００５１】
第６の効果は特にリモートノードのアクセスリンクが障害を起こした場合、パスの障害切替が高速になることである。なぜなら、アクセスリンクの障害を検知したノードは、直ちに他のサイトのノードにそれを通知するからである。
【発明を実施するための最良の形態】
【００５２】
次に本発明の実施の形態について図面を参照して詳細に説明する。
【００５３】
〔第１の実施の形態〕
先ず、本発明の第１の実施の形態について詳細に説明する。図３は本発明の第１の実施の形態の全体構成例を示すブロック図であり、複数のノード４１〜４３と、WAN３３と、複数のアクセスリンク２１〜２３，２５，２６とから構成されている。
【００５４】
ノード４１，４３は、それぞれ２本のアクセスリンク２１，２２及びアクセス２５，２６でWAN３３に接続され、ノード４２は１本のアクセスリンク２３でWAN３３に接続されている。また、異なるノードを接続するアクセスリンクの組み合わせ毎にパスが設定されている。即ち、ノード４１，４３間にはパス１６１〜１６４が、ノード４１，４２間にはパス１６５，１６６が、ノード４２，４３間にはパス１６７，１６８が設定されている。なお、ノード４１〜４３はそれぞれ異なるサイトのノードである。
【００５５】
ところで、WAN３３がIP-VPNやインターネットVPNである場合、一般に、ユーザ側のノードでは、そのままではWAN３３から出て行くアクセスリンクを指定できない。そこで、異なるノードに接続するアクセスリンクの組み合わせ毎にIPトンネルもしくはGREトンネルを用いてパスを設定し、それらのパスを負荷分散および障害切替の対象にする。
【００５６】
図４はパケットフォーマットを示す図である。IPトンネルの場合は、RFC2003 IP Encapsulation within IP １９９６年１０月に従い、転送すべきIPパケットに対するトンネルIPヘッダーにおけるプロトコル番号はIPを示す４を指定する。またGREトンネルの場合は、RFC2784、Generic Routing Encapsulation（GRE）、2000年３月に従い、先ず転送すべきIPパケットの外側にGREヘッダーを付け、更にその外側にIPトンネルヘッダーを付ける。GREヘッダー内のプロトコルタイプには転送すべきIPパケットのIPプロトコルを示す「0x800」を指定する。またIPトンネルヘッダー内のプロトコル番号はGREを示す４７をつける。
【００５７】
一方、WAN３３がインターネットVPNである場合、パス１６１〜１６４は１組のノード間の異なるアクセスリンクの組毎にIPトンネルもしくはGREトンネルをIPsecトランスポートモードで認証／暗号化したパスを設定する。ここで、オリジナルデータに対して最初にIPもしくはGREトンネルを設定し、つぎにそれをIPsecトランスポートモードで認証／暗号化するのは、経路選択と認証／暗号化とを分離独立化するためである。これは文献Joe Touch, “Dynamic internet overlay deployment and management using X-box,” Computer Networks, July 2001, pp. 177-135に出ている。なお、いずれの場合も、ESPに対するトンネルIPヘッダー内のプロトコル番号はRFC2406に従い５０をつける。
【００５８】
上記、いずれのトンネルの場合も、後述するパス管理テーブル７３（図７参照）におけるリモート／ローカルIPアドレス（アクセスリンクのIPアドレス）が、トンネル終端アドレスとして、トンネルIPヘッダーの送受信アドレスに用いられる。なおプローブパケットではIP/GREトンネルは行わない。なぜなら、トンネル終端アドレスを送受信アドレスに用いるからである。
【００５９】
このように、各ノード４１〜４３間での異なるアクセスリンクの組み合わせ毎にトンネルを設定することにより、アクセスリンクによって異なるプロバイダーが提供するWANの区別が付かない場合、例えば同一プロバイダーが提供するWANに複数のアクセスリンクで接続するノードがある場合でも、それらの複数のアクセスリンクのWANからの下り方向へも負荷分散を行うことが可能となる。
【００６０】
図５は図３に示したノード４１の内部構成例を示すブロック図である。なお、他のノード４２，４３も同様の構成を有している。ノード４１は、転送装置８１〜８４と、制御装置９と、パケットスイッチ１０とから構成される。
【００６１】
転送装置８１〜８４は、アクセスリンク２１、２２もしくは内部リンク１１１、１１２から受け取ったパケットの少なくとも宛先アドレスにもとづいて、そのパケットを転送すべき他の転送装置を決定する。また、ある転送装置が他の転送装置から受け取ったパケットは、アクセスリンク２１、２２もしくは内部リンク１１１、１１２上にそのまま転送される。
【００６２】
制御装置９は、自装置が収容されているノード４１に接続されている各パス１６１〜１６６やアクセスリンク２１、２２の状態を監視し、その結果に基づいて適切なパス状態メッセージを各転送装置８１〜８４に送出する。各転送装置８１〜８４は、このパス状態メッセージに基づいて転送処理に必要な各種テーブルを構成する。テーブルの詳細については後述する。
【００６３】
パケットスイッチ１０は、１組の転送装置間、もしくは転送装置と制御装置９との間で送受信すべきパケットを転送するものである。なおパケットスイッチ１０が転送装置８１〜８４および制御装置９を収容する部分をポートと呼び、パケットスイッチ１０内部で一意に決まるポートIDが付与される。
【００６４】
図６は図５に示したノード４１内の転送装置８１の構成例を示すブロック図である。なお、他の転送装置８２〜８４も同様の構成を有する。同図に示すように、転送装置８１は、パケット転送処理手段６１と、テーブル管理手段６２と、転送テーブル７１と、ストリームテーブル７２と、パス管理テーブル７３とから構成される。
【００６５】
パケット転送処理手段６１は、転送すべきパケットに対して、上記すべてのテーブル７１〜７３を参照して、パケット／フレームを組み立ててしかるべき転送装置にパケットスイッチ１０を介してパケットを転送する。
【００６６】
テーブル管理手段６２は、制御装置９からのパス状態メッセージに基づいてパス管理テーブル７３上でパスの使用状態の書き換えを行う。
【００６７】
図７（ａ）は、転送テーブル７１のフォーマットの一例を示す図であり、宛先のネットワークアドレスに到達するために、次に転送すべき装置のアドレスが示されている。この例では、IPアドレス接頭辞（プレフィックス）に対して、次に転送すべき装置のIPアドレスが設定されている。宛先ネットワークアドレスに対して複数のパスを持つものに対しては、WAN側のノードIDが付与される。
【００６８】
図７（ｂ）は、ストリームテーブル７２のフォーマットの一例を示す図である。このストリームテーブル７２は、パケット転送処理手段６１が転送テーブル７１でWAN側ノードIDを引いたとき、それをキーとして引かれる。そして、転送すべきパケットのフローの識別情報に対するハッシング値で与えられるストリームIDに対して割当てたパスのIDが登録されている。よって、各ノードIDの値毎に、ハッシュ空間数分のエントリーがある。ストリームIDのエントリーが参照された時刻も書かれているのは、一定時間以上そのエントリーが参照されない場合にそのパス割当てを解除するためである。
【００６９】
図７（ｃ）は、パス管理テーブル７３のフォーマットの一例を示す図である。転送テーブル７１で解決したノードIDと、ストリームテーブル７２で解決したパスIDをキーとして引かれる。そして引かれたエントリーには、パケット／フレームを組み立てるためのアドレス情報や、また転送すべき転送装置８１〜８４もしくは制御装置９を収容するポートのIDがある。使用状態はパスの状態を示し、ベスト、正常、禁止の３種類がある。この状態は制御装置９からパス状態メッセージが届くと、テーブル管理手段６２によって書き換えられる。
【００７０】
図８は本実施の形態でやり取りされるプローブパケットのフォーマットの一例を示す。プローブパケットは、IPヘッダとプローブメッセージからなる。プローブメッセージはICMP Echoメッセージに基づいている。プローブ要求メッセージではICMPタイプに８を、プローブ応答メッセージではICMPタイプに０をそれぞれ入れる。コードには通常のICMP Echoとは区別するために１を用いる。識別子には、後述する制御装置９内のプローブ管理テーブル７６（図１４（ｂ）参照）で管理されているノードIDとパスIDが含まれる。順序番号は、同一識別子に対してプローブ要求メッセージが送信される毎に１つずつ増加させる。プローブメッセージの中でICMPヘッダー以外の部分はデータフィールドと呼び、プローブ要求送信タイムスタンプとプローブ要求受信タイムスタンプのフィールドがある。プローブ要求送信タイムスタンプおよびプローブ要求受信タイムスタンプは、Ingress側およびEgress側のノードがそのメッセージを転送処理した時の時刻を記入する。なお、プローブ要求メッセージとプローブ応答メッセージとでは送信側IPインタフェイスアドレスを入れ替える。プローブ要求メッセージの送信側／受信側IPインタフェイスアドレスには、監視するパス（ノードIDとパスIDの組で識別）に対して、プローブ管理テーブル７６で管理しているリモート／ローカルIPアドレスを入れる。
【００７１】
図９はパケット転送処理手段６１におけるパケット転送処理のアルゴリズムの一例を示すフローチャートである。ここでTstreamは、ストリームからパス割当を解除するまでのタイムアウト値である。この値以上、同一ストリームに属するパケットが到着しない場合は、パス割当を解除する。なお、スタート時はパス割当てがないので、ストリームテーブル７２の選択パスIDには全て０００を記入しておく。
【００７２】
パケット転送処理手段６１は、転送すべきパケットを受信したら（ステップS10１）、宛先アドレスが自分宛かどうか調べ（ステップS102）、そうである場合はステップS111に行く。ステップS102で自分宛でない場合は、転送テーブル７１を引いて次ホップがWAN側ノードであるかどうか調べ(ステップS103)、そうでない場合はステップS108にいく。ステップS103でWAN側ノードである場合は、転送テーブル７１でノードIDを解決し、ハッシングでストリームIDを算出後、ノードIDをキーとしてストリームテーブル７２を引き、ストリームIDに対するパス割当てを調べる（ステップS104）。次にストリームテーブル７２上でそのストリームIDに対してパス割当てがあり、かつパス管理テーブル７３上でパスが割当ててある場合はそれが禁止パスではなく、かつパス割当てがタイムアウトしていない（（現時刻）―（参照時刻）≦Tstream）かどうか調べ(ステップS105)、これを満たす場合はパス管理テーブル７３上でノードIDとパスIDから解決される情報を参照してパケット/フレームを組み立て、しかるべきポートに転送する（ステップS107）。なお、このステップS107については、後で図１０を参照して詳細に説明する。ステップS105で条件が一つでも満たされない場合は、パス管理テーブル７３を参照することにより上記ノードIDによって特定されるノードとの間の、使用状態がベストであるパスのパスIDを解決し、ストリームテーブル７２上で、上記ノードIDとストリームIDに対して、上記パスIDと現時刻を、それぞれ選択パスIDと参照時刻として登録して（ステップS106）、ステップS107に行く。
【００７３】
ステップS108では、プローブ要求メッセージであるかどうか調べ、そうでない場合は転送テーブル７１が示す次ホップのアドレスに従ってパケットを転送する(ステップS110)。これに対して、ステップS108でプローブ要求メッセージである場合は、Ingress側項目を記入して（ステップS109）、ステップS110へ行く。
【００７４】
ステップS111では、ペイロードにさらにIPパケットが含まれトンネル終端すべきかどうか調べ、そうである場合はパケットを取り出して(ステップS112)、ステップS103にいく。ステップS111でトンネル終端ではない場合は、ICMPメッセージかどうか調べ（ステップS113）、そうでない場合はメッセージに従った処理を行う（ステップS115）。例えば、パス状態メッセージの場合は、それをテーブル管理手段６２に渡す。ステップS113でICMPメッセージの場合は、プローブ要求メッセージであるかどうか調べ(ステップS114)、そうである場合はEgress側項目を記入してプローブ応答メッセージを作成して返送する(ステップS116)。ステップS114でプローブ要求メッセージではなくプローブ応答メッセージの場合は、それを制御装置９に転送する（ステップS117）。
【００７５】
図１０は、図９のステップS107において、パケット転送処理手段６１が、パケット組立て／転送の必要がある場合に、パス管理テーブル７３を参照しながら組立て／転送処理を行うためのアルゴリズムを示すフローチャートである。パケット組立て／転送要求があると（ステップS118）、パス管理テーブル７３上で、ノードIDとパスIDからWANタイプを参照する(ステップS119)。その際WANタイプに応じて処理が異なる。WANタイプが広域イーサネットの場合は、L2タイプを参照する(ステップS120)。そして、イーサネットの場合は、リモート／ローカルMACアドレスを参照してイーサネットフレームを組立て（ステップS121）、参照したポートIDにパケットスイッチ１０を用いてフレームを転送する（ステップS122）。これに対して、ステップS120でL2タイプがVLANの場合は、リモート/ローカルMACアドレスとVLAN-IDとを参照してVLANタグのついたイーサネットフレームを組立て(ステップS123)、ステップS122に行く。ステップS119でWANタイプがIP-VPNの場合はステップS126に行く。ステップS119でWANタイプがIP-VPNのIP/GREトンネルの場合はリモート/ローカルIPアドレスを参照してIP/GREトンネルヘッダーを付け（ステップS124）、ステップS126に行く。ステップS119でWANタイプがIPsec付きトンネルの場合は、リモート／ローカルIPアドレスおよびSPIを参照してIP/GREトンネルパケットに対するIPsecトランスポートモードのヘッダー処理を行い(ステップS125)、ステップS126に行く。ステップS126ではL2タイプを参照する。そして、イーサネットの場合はリモート／ローカルMACアドレスを参照してMACフレームを組立て(ステップS127)、ステップS122に行く。これに対して、ステップS126でL2タイプがPPPの場合はPPPフレームを組み立てて(ステップS128)、ステップS122に行く。
【００７６】
図１１はパス状態メッセージのフォーマットの一例である。ノードIDと、そのノードIDによって特定されるノードにおいて使用状態が変更されたパス数と、使用状態が変更されたパスIDと使用状態との組がパス数分だけ並ぶ。
【００７７】
図１２は転送装置８１においてテーブル管理手段６２が行う処理アルゴリズムの一例を示すフローチャートである。制御装置９からの図１１に示すようなパス状態メッセージを、パス転送処理手段６１を介して受信したら(ステップS201)、パス管理テーブル７３上で該当するノードの各パスの使用状態をコピーする（ステップS202）。
【００７８】
図１３は図５に示したノード４１内の制御装置９の構成例を示すブロック図である。同図に示すように、制御装置９は、プローブ送信手段６５と、パス監視手段６６と、パス選択手段６７と、プローブ管理テーブル７６と、パス管理テーブル７７とから構成される。
【００７９】
プローブ送信手段６５は、プローブ要求メッセージ送出の要求がパス監視手段６６からあると、パス管理テーブル７７を参照してパケット/フレームを組み立ててしかるべきポート宛てに送出する。パス監視手段６６は、プローブ管理テーブル７６を随時参照した結果、あるいはプローブ応答メッセージを受信処理した結果に基づいて、図１に示すパス状態遷移の処理を行なう。パス選択手段６７は、パス監視手段６６からの通知に基づいてベストパスの算出、および以前と状態変化があったパスの状態をパス状態メッセージを用いて転送装置へ通知する役割をはたす。
【００８０】
図１４（ａ）は、制御装置９におけるパス管理テーブル７７のフォーマットの一例を示す図であり、図７（ｃ）に示した制御装置のパス管理テーブル７３と全く同じフォーマットである。
【００８１】
図１４（ｂ）は、プローブ管理テーブル７６のフォーマットの一例を示す図であり、ノードID、パスID、リモート／ローカルIPアドレス、送信時刻、識別子、プローブタイプ、監視状態、輻輳尺度値を含む。識別子、プローブタイプはプローブ要求メッセージ内に書き込んだものをコピーしておく。輻輳尺度値は、パス監視手段６６がベストパスを選択する際に使用する値であり、本実施の形態では、後述する輻輳RTTを採用することにする。監視状態には図１で示した正常、検査、禁止のいずれかが記入される。
【００８２】
次に、制御装置９における動作について説明する。図１５はパス監視手段６６がプローブ管理テーブル７６を監視する際の処理アルゴリズムの一例を示すフローチャートである。
【００８３】
パス監視手段６６は、定期的にプローブ管理テーブル７６の各パスに関するエントリーを上から順番に参照し、参照した各エントリーそれぞれについて、図１５のフローチャートに示す処理を行う。先ず、参照したエントリーに対応するパスが、送信タイムアウトしていないかどうかを、そのエントリーに記録されている送信時刻および監視状態と、監視状態に対応するタイムアウト値と、現在時刻とに基づいて判断する（ステップS402）。即ち、（現時刻−送信時刻≦Tnorm/Tfail）かどうか調べることにより、送信タイムアウトしているか否かを判断する。ここでTnorm/Tfailは、監視状態がそれぞれ正常／禁止の場合のタイムアウト値である。ステップS402で送信タイムアウトしていない場合はステップS404へ行く。ステップS402で送信タイムアウトしている場合は、プローブ送信手段６５に当該パスに対する１個プローブ送信要求を出し（ステップS403）、ステップS404に行く。ステップS404ではプローブ応答受信がタイムアウトしていない（現時刻−送信時刻≦Tprob）かどうか調べ、タイムアウトしていない場合は終わる。ステップS404でタイムアウトしている場合は、そのパスの監視状態によって各ステップに行く（ステップS405）。
【００８４】
監視状態が正常の場合は、プローブ管理テーブル７６上で当該パスの監視状態を検査とし、プローブ送信手段６５にＭ個プローブ要求転送の通知をする(ステップS406)。ステップS405で監視状態が検査の場合は、プローブ管理テーブル７６上で当該パスの監視状態を禁止にし、パス選択手段６７に当該パスの監視状態（禁止）を通知する(ステップS407)。ステップS405で監視状態が禁止の場合は終わる。
【００８５】
図１６はパス監視手段６６によるプローブパケット受信処理のアルゴリズムの一例を示すフローチャートである。プローブパケットを受信したら（ステップS501）、パス管理テーブル７７上で識別子内のノードID＋パスIDに対するリモート/ローカルIPアドレスが、プローブパケットのDA/SAと一致するかどうか調べ(ステップS502)、一致する場合はステップS503に行く。一致しない場合は廃棄する(ステップS508)。これは不正パケットの恐れがあるからである。
【００８６】
ステップS503では、プローブ管理テーブル７６上でプローブ応答メッセージ内の識別子からノードID＋パスIDを識別し、次にプローブ応答メッセージ内の送信タイムスタンプを参照して当該パスのプローブタイムアウト値Tprobおよび必要ならば輻輳RTTを更新する。次に、輻輳尺度値を計算して記入する (ステップS504)。本実施の形態では、輻輳RTTを輻輳尺度値とするので、ステップS503で求めた輻輳RTTをプローブ管理テーブル７６に登録する。次に、監視状態が正常であるかどうか調べ（ステップS505）、そうである場合は、当該パスに関してパス選択手段６７に当該パスの監視状態を通知する(ステップS507)。ステップS505で監視状態が正常でない場合はプローブ管理テーブル７６上で当該パスの監視状態を正常にし、次に当該ノードに対して他に正常パスがあればその送信時刻を当該パスのエントリーにコピーし(ステップS506)、ステップS507に行く。ここで、ステップS506で送信時刻のコピーを行うのは、各パスへのプローブ要求メッセージの送信タイミングをほぼ等しくするためである。
【００８７】
次に、上記ステップS503で行う、プローブ受信タイムアウト値Tprobと輻輳RTTの算出法を示す。ここで輻輳RTTとはRTTの推定平均値からその推定最小値を差し引いたものである。ここでRTTの最小値は往復伝搬遅延に往復経路上でのプローブパケット自体の転送時間を加えたものになる。 
【００８８】
まず、RTTの測定値をeRTTであらわすと、これは次式で示される。
eRTT←(現時刻)−（プローブ応答メッセージ内のプローブ要求送信タイムスタンプ）
またRTT推定平均値をaRTTであらわし、
（aRTTの初期値）←（eRTTの初期値）
とする。RTT推定平均偏差をvRTTであらわし、
（vRTTの初期値）←０
とする。また、RTT推定最小値をsRTTで表し、
（sRTTの初期値）←（eRTTの初期値）
とする。そして次の指数移動平均法で、新たにプローブ応答メッセージを受信する毎に次のように更新する。
Δ←eRTT-aRTT、
aRTT←aRTT+Δ/8、
vRTT←vRTT+(|Δ|-vRTT)/4、
sRTT←min(sRTT, eRTT)
そして、
Tprob←aRTT+4*vRTT、
輻輳RTT←aRTT-sRTT
とする。なおタイムアウト値の計算法はVan Jacobson and M. J. Karels, "Congestion avoidance and control" November 1998, SINGCOM 88からとったものである。
【００８９】
図１７はプローブ送信手段６５のプローブ送信処理アルゴリズムの一例を示すフローチャートである。プローブ送信手段６５は、パス監視手段６６が図１５のステップS406で出力したＭ個プローブ送信要求を受信すると（ステップS601）、パス管理テーブル７７を参照して上記Ｍ個プローブ送信要求によって指定されているパスに対するプローブ要求メッセージをＭ個生成し（プローブ要求送信タイムスタンプに現在の時刻を記入）、パス管理テーブル７７で指定されるポートに連続的に（時間間隔を空けずに）転送するとともに、プローブ管理テーブル７６上で当該パスのエントリーにおいて識別子、プローブタイプ、およびＭ個中最後に転送したプローブ要求メッセージの送信時刻を記入する（ステップS602）。また、パス監視手段６６が図１５のステップS403で出力した１個プローブ送信要求を受信した場合も、プローブ送信手段６５は、上記した処理と同様の処理を行う。但し、この場合は、１個のプローブ要求メッセージのみを送信する。
【００９０】
図１８はパス選択手段６７によるパス状態通知処理アルゴリズムを示すフローチャートである。パス選択手段６７は、パス監視手段６６が図１５のステップS407或いは図１６のステップS507で出力したパスの監視状態を受信すると（ステップS701）、パス管理テーブル７７を参照し、先ずそのノードの全パスの使用状態をコピーして保持し、次に当該ノードのパスの中で使用状態がベストであるものを正常に戻し、最後に当該パスのエントリーの使用状態に通知のあった監視状態をコピーする（ステップS702）。次に、プローブ管理テーブル７６上で当該ノードで監視状態が正常である全パスの輻輳尺度値（輻輳RTT）を参照してベストパスを決定し（輻輳RTTが最小のパスをベストパスとする）、パス管理テーブル７７上で当該ノードのベストパスに選ばれたパスの使用状態をベストに変更する(ステップS703)。次に当該ノードに対し、保持していた全パスの使用状態と現在のパス管理テーブル７６上の全パスの使用状態に差分があるかどうか調べ(ステップS704), 無い場合はおわる。ステップS704で差分がある場合は、使用状態に差分のあるパスのみその新たな使用状態をパス状態メッセージを用いて各転送装置８１〜８４に送る(ステップS705)。
【００９１】
次に、本実施の形態の効果について説明する。実際は正常であっても、それを正常でないと判断した状態から正常と判断するまでの時間が早まる。なぜなら、もしくはタイムアウトで検査もしくは禁止と一旦遷移しても、プローブ応答パケットが戻ってきたら、それがタイムアウトであっても、正常に復帰させるからである。一方、従来は、正常状態をタイムアウトによりそうでないと誤判断しても、判断の修正は次のプローブの時間内到着にゆだねるため、プローブ送出時間間隔だけ待つ必要があった。
【００９２】
〔第２の実施の形態〕
次に、本発明の第２の実施の形態について説明する。本実施の形態は、輻輳尺度として実効リンク空き帯域あるいは実効利用率を使用することを特徴とする。
【００９３】
本実施の形態は、輻輳尺度として実効リンク空き帯域あるいは実効利用率を使用するため、プローブパケットのフォーマットおよび転送装置の構成が第１の実施の形態と異なっている。
【００９４】
図１９は本実施の形態で使用するプローブパケットのフォーマットの一例を示す。本実施の形態のプローブパケットと、図８に示した第１の実施の形態のプローブパケットとの相違点は、コードが２となっている点、データフィールドにリンク送信平均レートSR、送信側リンク容量SC、リンク受信平均レートRRおよび受信側リンク容量RCが追加されている点である。平均レートは一定時間内に送受信したデータ量をその時間で割ったものである。
【００９５】
図２０はプローブパケットの処理の過程を説明する図である。まずIngressノード４１内の制御装置９でプローブ要求送信タイムスタンプを書き込み(a)、次にIngressノード４１内のWAN側転送装置８１ａでIngress項目（ここではSR,SC）を記入してEgressノード４２に送信する(b)。Egressノード４２のWAN側転送装置８５ａがこれを受信すると、Egress項目（ここではRR,RC）を記入して、プローブ応答メッセージを作成し、Ingressノード４１に返送する(c)。返送されたプローブパケットを受け取ったIngressノード４１のWAN側転送装置８１ａは、さらにこれを制御装置９に渡し、そこで輻輳尺度の算出とベストパスの算出が行われる。
【００９６】
図２１は、図２０に示したWAN側の転送装置８１ａの構成例を示したブロック図である。本実施の形態の転送装置８１ａと、図６に示した第１の実施の形態の転送装置８１との相違点は、リンク管理テーブル７４及びリンク統計手段６３が追加された点と、パケット転送処理手段６１の代わりにパケット転送処理手段６１ａを備えた点である。なお、本実施の形態で使用するLAN側の転送装置は、第１の実施の形態の転送装置８１と同じ構成を有する。
【００９７】
リンク統計手段６３は、パケット転送処理手段６１ａが、WAN側のアクセスリンクに対してパケットの送受信を行うたびにそのデータ長（レイヤ２ヘッダーを含む）の情報をもらって加算し、一定時間後のデータ合計量をその時間間隔で割って平均レートを計算して、リンク管理テーブル７４に書き込む。
【００９８】
図２２にリンク管理テーブル７４のフォーマットの一例を示す。同図に示すように、リンク管理テーブル７４には、自転送装置８１ａのポートIDと、送信リンク容量と、リンク送信レートと、受信リンク容量と、リンク受信レートとが格納される。
【００９９】
パケット転送処理手段６１ａは、リンク管理テーブル７４を参照し、図９のステップS109においてプローブ要求メッセージにSC,SRを書き込み、ステップS116においてプローブ応答メッセージにRC,RRを書き込む。なお、パケット転送処理手段６１ａは、上記した２つのステップS109,S116以外は、パケット転送処理手段６１と同様の処理を行う。
【０１００】
これらに基づいた輻輳尺度の計算は、制御装置９内のパス監視手段６６が行う。即ち、パス監視手段６６は、図１６のステップS504において、受信したプローブパケット中のSC,SR,RC,RRに基づいて輻輳尺度値を計算し、計算した輻輳尺度値をプローブ管理テーブル７６に登録する。前述したように、本実施の形態では、輻輳尺度として実効リンク空き帯域あるいは実効リンク利用率を使用する。実効リンク空き帯域は、上記プローブパケットをやり取りする際に使用されたIngressノードのアクセスリンクの空き帯域およびEgressノードのアクセスリンクの空き帯域の内の最小値であり、min{SC-SR,RC-RR}で与えられる。また、実効リンク利用率は、上記プローブパケットをやり取りする際に使用されたIngressノードのアクセスリンクのリンク利用率およびEgressノードのアクセスリンクのリンク利用率の内の最大値であり、max{SR/SC,RR/RC}で与えられる。
【０１０１】
また、制御装置９内のパス選択手段６７は、図１８のステップS703においてベストパスを選択する際、輻輳尺度として実効リンク空き帯域を使用している場合は、それが最も大きいパスを選択し、実効リンク利用率を使用している場合は、それが最も小さいパスを選択することになる。
【０１０２】
次に本実施の形態の効果について説明する。アクセスリンクにおける空き帯域もしくは利用率に基づいた負荷分散が可能となる。なぜならプローブパケットを用いてEgressノードでのデータの転送レートの情報をIngressノードにフィードバックするからである。
【０１０３】
〔第３の実施の形態〕
次に本発明の第３の実施の形態について説明する。本実施の形態は、輻輳尺度として網効率あるいはデータ廃棄率を用いることを特徴とする。
【０１０４】
本実施の形態では、輻輳尺度として網効率あるいはデータ廃棄率を使用するため、プローブパケットのフォーマットおよび転送装置の構成が第１の実施の形態と相違している。
【０１０５】
図２３は本実施の形態で使用するプローブパケットのフォーマットの一例を示す。本実施の形態のプローブパケットと、図８に示した第１の実施の形態のプローブパケットとの相違点は、コードが３になっている点、データフィールドにデータ送信タイムスタンプST、パス送信データ総量SB, データ受信タイムスタンプRT, パス受信データ総量RBが追加されている点である。ここで、STはIngressノードがプローブ要求パケットを送信する直前に送信したデータパケットの送信開始時刻であり、RTはEgressノードがプローブ要求パケットを受信した直前に受信したデータパケットの受信完了時刻である。ST,SB、およびRT、RBはそれぞれIngresおよびEgressノードのWAN側転送装置が記入する。この場合、輻輳尺度には、網効率もしくはデータ廃棄率を用いる。網効率の最大のパス、もしくはデータ廃棄率が最小のパスをベストとする。
【０１０６】
図２４は本実施の形態におけるWAN側の転送装置８１ｂの構成例を示すブロック図である。図６に示した第１の実施の形態の転送装置８１との相違点は、パス統計手段６４が追加された点、パス転送処理手段６１の代わりにパス転送処理手段６１ｂを使用する点、およびパス管理テーブル７３の代わりにパス管理テーブル７３ｂを使用する点である。なお、本実施の形態におけるLAN側の転送装置は、第１の実施の形態の転送装置８１と同じ構成を有する。
【０１０７】
パス管理テーブル７３ｂのフォーマットの一例を図２５に示す。図７(c)に示した第１の実施の形態のパス管理テーブル７３との相違点は、パス送信データ総量SBおよびデータ受信データ総量RBが追加されている点である。
【０１０８】
パス統計手段６４は、パケット転送処理手段６１ｂがWANに対するリンク上でパケットを送受信するたびに、パケット転送処理手段６１ｂから統計処理を行うための情報をもらう。
【０１０９】
図２６はパス統計手段６４がパス毎に送受信したデータ量の統計処理を行うアルゴリズムの一例を示すフローチャートである。パス統計手段６４は、パケット転送処理手段６１ｂからヘッダー情報（レイヤ２およびレイヤ３）とデータ長（レイヤ２ヘッダーを含む）とポートIDとをもらうと(ステップS301)、パス管理テーブル７３ｂを上から参照して行き、ポートIDからWANタイプを解決する（ステップS302）。
【０１１０】
次に、WANタイプが広域イーサネットならそのフレームがVLANフレームかどうか調べる(ステップS303)。そして、VLANでない場合は、パス管理テーブル７３ｂ上でデータの送受信MACアドレスからノードIDとパスIDを解決して（ステップS304）、ステップS307に行く。ステップS303でVLANフレームの場合は、パス管理テーブル７３ｂ上で、データの送受信MACアドレスとVLAN-IDからノードIDとパスIDを解決して(ステップS305)、ステップS307に行く。また、ステップS302でWANタイプがIP-VPNもしくはIPsecのトンネルリングの場合は、パス管理テーブル７３ｂ上で、送受信トンネル終端IPアドレスからノードIDとパスIDを解決して(ステップS306)、ステップS307に行く。ステップS307では、ノードIDとパスIDとによって特定されるパス管理テーブル７３ｂ中のエントリーのSB若しくはRBに、送信もしくは受信パケット長を加算する。
【０１１１】
パケット転送処理手段６１ｂは、パス管理テーブル７３ｂを参照し、図９のステップS109においてプローブ要求メッセージにSBを書き込み、ステップS116においてプローブ応答メッセージにRBを書き込む。上記ステップS109、S116以外の処理は、第１の実施の形態におけるパケット転送処理手段６１と同じである。
【０１１２】
次に、網効率およびデータ廃棄率の計算方法を示す。これらの計算は、制御装置９内のパス監視手段６６が、図１６のステップS504で行う。パス監視手段６６は、最後に受信したプローブ応答メッセージを記憶しておき、これに関するデータを添え字oldで表し、次式で網効率を計算する。
送信スループット:λnew＝(SBnew-SBold）/(STnew-STold)
受信スループット：μnew＝（RBnew-RBold）/（RTnew-RTold)
（網効率）＝ μnew ／λnew
（データ廃棄率）＝(RBnew-RBold) /(SBnew-SBold)
【０１１３】
また、制御装置９内のパス選択手段６７が図１８のフローチャートのステップS703において行うベストパスの選択では、輻輳尺度として網効率を用いる場合はそれが最大のパスをベストパスとする。また、輻輳尺度としてデータ廃棄率を用いる場合はそれが最小のパスをベストパスとする。
【０１１４】
次に本実施の形態の効果について説明する。各パスのスループットに基づく負荷分散が可能となる。なぜならプローブパケットを用いてパスの出力スループットに関する情報をIngress側にフィードバックするからである。
【０１１５】
〔第４の実施の形態〕
次に本発明の第４の実施の形態について説明する。本実施の形態は、輻輳状況に応じて、ベストパスの選択に用いる輻輳尺度の種別を選択することを特徴とする。このベストパス選択に用いられる輻輳尺度を特にパス選択尺度と呼ぶことにする。
【０１１６】
本実施の形態は、輻輳状況に応じてパス選択尺度を変更できるようにするため、第２の実施の形態に下記の変更を行っている。なお、本実施の形態では、２種類の輻輳尺度（輻輳RTTと、実効リンク空き帯域）の中からパス選択尺度を選択するものとする。
【０１１７】
・図１４（ｂ）に示したプローブ管理テーブル７６の代わりに、図２７に示したプローブ管理テーブル７６ｃを使用する。
・制御装置９内のパス監視手段６６が、図１６のステップS504において、図２８のフローチャートに示す処理も行う。
【０１１８】
以下、変更点について詳しく説明する。
【０１１９】
本実施の形態で使用する図２７に示すプローブ管理テーブル７６ｃと、図１４（ｂ）に示した第２の実施の形態で使用するプローブ管理テーブル７６との相違点は、輻輳フラグとパス選択尺度IDの欄が加わった点、および、２種類の輻輳尺度（ここでは、輻輳RTTと実効リンク空き帯域）をパス選択尺度として使い分けるので、尺度IDと輻輳尺度値の欄が１つ増えている点である。ベストパス選択に用いる輻輳尺度値は、尺度IDがパス選択尺度IDと一致するものを用いる。
【０１２０】
制御装置９内のパス監視手段６６は、図１６のステップS504において、あるノードに対して、パス選択尺度を選択する要求が発生すると（図２８、ステップS508）、輻輳RTTが最大のパスを選択し(ステップS509)、次に輻輳フラグＦが立っているか否か調べる（ステップS510）。そして、立っている場合はステップS511に、立っていない場合はステップS514に行く。
【０１２１】
ステップS511ではステップS509で選ばれたパスの輻輳RTTがRTT推定最小値sRTTのＮ倍以上かどうか調べ、そうである場合は輻輳フラグＦを立てて、輻輳RTTをパス選択尺度とし、それを示すパス選択尺度IDをプローブ管理テーブル７６ｃに書き込む(ステップS512)。ステップS510でＮ倍以上でない場合は、実効リンク空き帯域をパス選択尺度とし、それを示すパス選択尺度IDをプローブ管理テーブル７６ｃに書き込む(ステップS513)。なお、ステップS511で使用する定数Ｎは、例えば、１≦Ｎ≦４とすることができる。
【０１２２】
また、ステップS514ではステップS509で選らばれたパスの輻輳RTTがRTT推定最小値sRTTのＭ倍以上かどうか調べ、そうである場合は輻輳フラグＦを降ろし、実効リンク空き帯域をパス選択尺度とし、それを示すパス選択尺度IDをプローブ管理テーブル７６ｃに書き込む(ステップS516)。ステップS514でＭ倍以上でない場合は、輻輳RTTをパス選択尺度とし、それを示すパス選択尺度IDをプローブ管理テーブル７６ｃに書き込む(ステップS515)。なお、ステップS514で使用する定数Ｍは、例えば、１≦Ｍ≦４とすることができる。
【０１２３】
次に本実施の形態の効果について説明する。輻輳レベルが低い場合、伝搬遅延の小さなパス、あるいは容量の大きなリンクが含まれるパスに負荷が偏らなくなる。なぜなら、加わる負荷が小さく輻輳レベルが低い状態では、測定される負荷に基づいてパス選択を行ない、加わる負荷が大きく輻輳レベルが高い状態では、輻輳による遅延に基づいてパス選択を行うからである。
【０１２４】
〔第５の実施の形態〕
次に、本発明の第５の実施の形態について説明する。本実施の形態は、リンク状態パケットを使用して障害の発生したリンクを他のノードに通知することを特徴とする。
【０１２５】
図２９は、本実施の形態で使用する転送装置８１ｄの構成例を示すブロック図であり、テーブル管理手段６２の代わりにテーブル管理手段６２ｄを備えている点が図６に示した転送装置８１と相違している。
【０１２６】
図３０は、本実施の形態で使用するリンク状態パケットのフォーマットの一例を示す図である。リンク状態メッセージは、ICMPにもとづく。ただし、ICMPタイプとして４１番を新たに確保する。コードは禁止を０、正常を１とする。ICMPデータフィールドには、状態変化したアクセスリンクのIPインタフェイスアドレスを入れる。
【０１２７】
図３１はLAN側の転送装置８１ｄにおけるテーブル管理手段６２ｄの処理アルゴリズムの一例を示すフローチャートである。制御装置９よりリンク状態メッセージを受信したら(ステップS801)、パス管理テーブル７３上で該当するリモートもしくはローカルのIPアドレスが一致する全エントリーの使用状態を、前記パケットのコードが示す状態に書き換える(ステップS802)。
【０１２８】
図３２は本実施の形態で使用する制御装置９ｄの構成例を示すブロック図であり、リンク監視手段６９と、パス管理テーブル７８と、リンク管理テーブル７９とからなる。
【０１２９】
リンク監視手段６９はWAN側転送装置８１ｄが終端するアクセスリンクの状態を随時監視する。そしてリンク状態メッセージをWAN側転送装置８１ｄを経由して送受信するとともに、LAN側の転送装置８３ｄには、リモートのノードから受信したリンク状態メッセージをそのまま転送する。パス管理テーブル７８は、リンク監視手段６９がリンク状態メッセージを組み立て、送信するためのもので、そのフォーマットは本発明の第１の実施の形態の図７と同じである。
【０１３０】
図３３はリンク管理テーブル７９のフォーマットの一例を示す図である。これはリンク監視手段６９がリンクの状態を保持するためのものである。
【０１３１】
図３４はリンク監視手段６９の処理アルゴリズムの一例を示すフローチャートである。リンク監視手段６９は、ローカルリンクの障害発生／復旧を検知したら(ステップS901)、リンク管理テーブル７９の状態を書き換え(ステップS902)、LAN側の全転送装置にリンク状態メッセージを送信し(ステップS903)、最後にパス管理テーブル７８を参照してリモートノード毎に、リンク状態メッセージをＬ個生成して正常なパスを選んで連続転送する(ステップS904)。
【０１３２】
また、リモートノードよりリンク状態メッセージを受信した場合は(ステップS905)、リンク管理テーブル７９を参照して、メッセージが示す状態と異なっているかどうか調べ(ステップS906)、異なっていればリンク管理テーブル７９の状態を書き換えて、LAN側の全転送装置にリンク状態メッセージを転送する(ステップS907)。ステップS906で状態が同じならば処理を終える。
【０１３３】
次に本実施の形態の効果について説明する。リモートサイトのリンクが障害を起こしても、迅速なパス切替が可能となる。なぜなら、アクセスリンクの障害を検知したら、直ちに他のサイトにそれを通知するからである。
【図面の簡単な説明】
【０１３４】
【図１】本発明が、障害検出を高速化でき、且つ、正常パスを障害パスと誤認識しても、そこから正常であると正しく判断するまでの時間を短くすることができる原理を説明するための状態遷移図である。
【図２】本発明が、リモートノードのアクセスリンクに障害が発生した場合、パスの障害切替を高速に行うことができる原理を説明するためのブロック図である。
【図３】本発明の第１の実施の形態の全体構成例を示すブロック図である。
【図４】トンネルに関するパケットフォーマットを示す図である。
【図５】第１の実施の形態におけるノード４１の構成例を示すブロック図である。
【図６】第１の実施の形態における転送装置８１の構成例を示すブロック図である。
【図７】転送テーブル７１、ストリームテーブル７２、パス管理テーブル７３の一例を示す図である。
【図８】第１の実施の形態で使用するプローブパケットのフォーマットの一例を示す図である。
【図９】第１の実施の形態におけるパケット転送処理手段６１の処理例を示すフローチャートである。
【図１０】第１の実施の形態におけるパケット転送処理手段６１の処理例を示すフローチャートである。
【図１１】パス状態メッセージのフォーマットの一例を示す図である。
【図１２】第１の実施の形態におけるテーブル管理手段６２の処理例を示すフローチャートである。
【図１３】第１の実施の形態における制御装置９の構成例を示すブロック図である。
【図１４】プローブ管理テーブル７６、パス管理テーブル７７の一例を示す図である。
【図１５】第１の実施の形態におけるパス監視手段６６の処理例（プローブ管理テーブル監視時）を示すフローチャートである。
【図１６】第１の実施の形態におけるパス監視手段６６の処理例（プローブパケット受信時）を示すフローチャートである。
【図１７】第１の実施の形態におけるプローブ送信手段６５の処理例を示すフローチャートである。
【図１８】第１の実施の形態におけるパス選択手段６７の処理例を示すフローチャートである。
【図１９】第２の実施の形態で使用するプローブパケットのフォーマットの一例を示す図である。
【図２０】第２の実施の形態の動作を説明するための図である。
【図２１】第２の実施の形態における転送装置８１ａの構成例を示すブロック図である。
【図２２】リンク管理テーブル７４の一例を示す図である。
【図２３】第３の実施の形態で使用するプローブパケットのフォーマットの一例を示す図である。
【図２４】第３の実施の形態で使用する転送装置８１ｂの構成例を示すブロック図である。
【図２５】パス管理テーブル７３ｂの一例を示す図である。
【図２６】第３の実施の形態におけるパス統計手段６４の処理例を示すフローチャートである。
【図２７】第４の実施の形態で使用するプローブ管理テーブル７６ｃの一例を示す図である。
【図２８】第４の実施の形態におけるパス監視手段６６の処理例を示すフローチャートである。
【図２９】第５の実施の形態で使用する転送装置８１ｄの構成例を示す図である。
【図３０】第５の実施の形態で使用するリンク状態パケットのフォーマットの一例を示す図である。
【図３１】テーブル管理手段６２ｄの処理例を示すフローチャートである。
【図３２】第５の実施の形態で使用する制御装置９ｄの構成例を示すブロック図である。
【図３３】リンク管理テーブル７９の一例を示す図である。
【図３４】リンク監視手段６９の処理例を示すフローチャートである。
【図３５】従来のプライベート網の構成を示すブロック図である。
【図３６】従来のプライベート網の構成を示すブロック図である。
【図３７】従来のプライベート網の構成を示すブロック図である。
【図３８】イーサネットフレームの説明図である。
【図３９】従来のサイトの構成を示すブロック図である。
【図４０】従来のノードの構成を示すブロック図である。
【図４１】従来のインターネットVPNにおける負荷分散の構成を示すブロック図である。
【図４２】従来のプローブパケットの動作を説明する図である。
【図４３】従来のプローブパケットによるパス状態管理を説明する図である。
【符号の説明】
【０１３５】
２１〜２６…アクセスリンク
３１〜３５…WAN
４１〜４３…ノード
６１、６１ａ、６１ｂ…パケット転送処理手段
６２、６２ｄ…テーブル管理手段
６３…リンク統計手段
６４…パス統計手段
６５…プローブ送信手段
６６…パス監視手段
６７…パス選択手段
６９…リンク監視手段
７１…転送テーブル
７２…ストリームテーブル
７３、７３ｂ…パス管理テーブル
７４、７９…リンク管理テーブル
７６、７６ｃ…プローブ管理テーブル
７７、７８…パス管理テーブル
７９…リンク管理テーブル
８１〜８４、８１ａ、８５ａ、８１ｂ、８１ｄ、８３ｄ…転送装置
９、９ｄ…制御装置
１０…パケットスイッチ
１１１、１１２…内部リンク
１６１〜１６６…パス
【図１】
2005057514.tif 000003
【図２】
2005057514.tif 000004
【図３】
2005057514.tif 000005
【図４】
2005057514.tif 000006
【図５】
2005057514.tif 000007
【図６】
2005057514.tif 000008
【図７】
2005057514.tif 000009
【図８】
2005057514.tif 000010
【図９】
2005057514.tif 000011
【図１０】
2005057514.tif 000012
【図１１】
2005057514.tif 000013
【図１２】
2005057514.tif 000014
【図１３】
2005057514.tif 000015
【図１４】
2005057514.tif 000016
【図１５】
2005057514.tif 000017
【図１６】
2005057514.tif 000018
【図１７】
2005057514.tif 000019
【図１８】
2005057514.tif 000020
【図１９】
2005057514.tif 000021
【図２０】
2005057514.tif 000022
【図２１】
2005057514.tif 000023
【図２２】
2005057514.tif 000024
【図２３】
2005057514.tif 000025
【図２４】
2005057514.tif 000026
【図２５】
2005057514.tif 000027
【図２６】
2005057514.tif 000028
【図２７】
2005057514.tif 000029
【図２８】
2005057514.tif 000030
【図２９】
2005057514.tif 000031
【図３０】
2005057514.tif 000032
【図３１】
2005057514.tif 000033
【図３２】
2005057514.tif 000034
【図３３】
2005057514.tif 000035
【図３４】
2005057514.tif 000036
【図３５】
2005057514.tif 000037
【図３６】
2005057514.tif 000038
【図３７】
2005057514.tif 000039
【図３８】
2005057514.tif 000040
【図３９】
2005057514.tif 000041
【図４０】
2005057514.tif 000042
【図４１】
2005057514.tif 000043
【図４２】
2005057514.tif 000044
【図４３】
2005057514.tif 000045