輻輳制御を備えるパケット中継装置、輻輳制御方法およびネットワークシステム

【課題】各ＩＰ中継装置がネットワーク全体の構成情報を保持しない場合、従来技術では、適切な迂回経路を発見することは困難であり、発見した経路を設定したとしても、ループを構成する可能性がある。
【解決手段】パケット転送装置を通過するトラヒックの宛先装置についての情報に基づいて、宛先装置を迂回先装置として前記迂回先装置に至る迂回経路を探索する為の探索パケットを生成して迂回経路を探索するパケット転送装置。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット交換ネットワークに関し、より詳細にはネットワーク内で輻輳が発生した場合の制御に関する。
【背景技術】
【０００２】
近年、ＴＣＯ削減の意識の向上に伴い、企業ＩＰ網の拡充、パケット交換ネットワークプロトコルであるＩＰ上でのデータ通信と音声通信の統合や、ＩＰ−ＶＰＮの普及が進み、輻輳制御やＱｏＳ制御など、パケット交換ネットワークの通信品質を保証する技術が重要視されている。
【０００３】
このうち、ＩＰネットワークにおいて輻輳を回避する技術については、従来、ネットワーク上のリンク情報を一元管理する集中管理方式と、各ＩＰ中継装置の隣接装置のリンク情報をお互いに交換しあうことで管理する分散管理方式がある。一般的に、ＩＰネットワークでは、パケットを転送するために、ＩＰ中継装置がパケットの宛先ＩＰアドレスを用いて中継装置の保持する経路表で経路検索を行い、パケットを出力すべき何れかのリンク（ネクストホップ）を決定する。
【０００４】
ここで輻輳を回避するためには、輻輳の発生に応じて、ＩＰ中継装置が、パケットを複数のリンクに割り振り、リンク毎の通信負荷を分散させる方法が有効である。また、通信負荷を分散させる際には、重要度の高い通信を優先的に保護すべきである。しかし、ＩＰ中継装置がネクストホップを決定する際、経路情報として反映されていないリアルタイムの通信経路の負荷を考慮することは難しい。
【０００５】
前述した分散管理方式において、この問題解決を目的とする技術として、特許文献１がある。当該技術では、輻輳を検知したＩＰ中継装置が、隣接する同装置に通知パケットを送信する。通知パケットを受信したＩＰ中継装置は、通知パケットが指定するパケットのネクストホップを変更し、通知パケットを更に他の同装置に送信する。しかしこの手法では、輻輳迂回経路を発見する前にパケットの経路を変更するため、変更後の経路がパケットのループを引き起こす可能性がある。
【０００６】
同様に、輻輳を検知したＩＰ中継装置が、隣接する同装置に通知パケットを送信する技術として特許文献２がある。当該技術では、各ＩＰ中継装置はネットワーク全体のリンク構成情報を持つ。通知パケットは入力キューが輻輳しているＩＰ中継装置のＩＰアドレスを持つ。通知パケットを受信した別のＩＰ中継装置は、輻輳装置を迂回するよう、通知パケットが指定するパケットの経路を変更する。さらに当該技術におけるＩＰ中継装置は、特定パケットの経路のみを変更させないための処理も備えている（〔００５０〕段落）。当該手法では迂回経路がパケットのループを引き起こす可能性を回避できるが、各ＩＰ中継装置がネットワーク全体の構成情報を持つ必要があるため、各装置の必要メモリ量が増大してしまう。さらに、当該手法における特定パケットの経路のみを変更させないための処理は、変更しないトラヒックの条件をすべて記述することで実現しているが、このような記述を通知パケットに含めることは通信の増大につながってしまう。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００３−９２５９３
【特許文献２】特開２００２−２５２６４０
【発明の概要】
【発明が解決しようとする課題】
【０００８】
各ＩＰ中継装置がネットワーク全体の構成情報を保持しない場合、従来技術では、適切な迂回経路を発見することは困難であり、発見した経路を設定したとしても、ループを構成する可能性がある。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、例えば特許請求の範囲に記載の構成を採用する。
本願は上記課題を解決する手段を複数含んでいるが、その一例を挙げるならば、ネットワークに接続されて使用するパケット転送装置であって、経路情報を記録する記憶部と、パケットの送受信手段と、前記転送装置を通過するトラヒックの宛先装置についての情報に基づいて、宛先装置を迂回先装置として前記迂回先装置に至る迂回経路を探索する為の探索パケットを生成し、前記送受信手段によって前記ネットワークに送信する探索パケット生成手段と、前記送受信手段を介して受信されたパケットが探索パケットまたは経路書換パケットであることを判別する受信パケット判別手段と、前記受信されたパケットが探索パケットであると前記受信パケット判別手段で判別された場合、前記受信した探索パケットが探索する経路の迂回先装置の情報が、前記転送装置の隣接装置の情報と一致するかどうかを判別する迂回先装置隣接判別手段と、前記転送装置の隣接装置と前記受信された探索パケットが探索する経路の迂回先装置とが一致すると、前記迂回先装置隣接判別手段で判別された場合、前記受信された探索パケットの経由装置を宛先とした経路書換パケットを生成し、前記送受信手段によってネットワークに送信する経路書換パケット生成手段と、前記転送装置の隣接装置と前記受信された探索パケットが探索する経路の迂回先装置とが一致しないと、前記迂回先装置隣接判別手段で判別された場合、前記受信された探索パケット内に、前記転送装置を経由したことを記録し、前記送受信手段によってネットワークに送信する探索パケット転送手段と、前記受信されたパケットが経路書換パケットであると前記受信パケット判別手段で判別された場合、前記受信された経路書換パケットに従って、前記経路情報を書き換える経路情報書換手段と、を備えることを特徴とする。
【発明の効果】
【００１０】
各ＩＰ中継装置がネットワーク全体の構成情報を保持しない場合であっても、適切な迂回経路を発見し、経路を書き換えることを可能にする。
【図面の簡単な説明】
【００１１】
【図１】本発明による、迂回経路設定における、探索パケットと経路書換パケットの動きとＩＰ中継装置の動作
【図２】実施例１におけるネットワーク構成
【図３】実施例１における輻輳を検知したＩＰ中継装置の動作手順
【図４】実施例１における探索パケットを受信したＩＰ中継装置の動作手順
【図５】実施例１における経路書換パケットを受信したＩＰ中継装置の動作手順
【図６】実施例１における探索パケットの構成例
【図７】実施例１における経路書換パケットの構成例
【図８】実施例１におけるＩＰ中継装置毎の探索パケットの構成の遷移
【図９】実施例１におけるＩＰ中継装置毎の経路書換パケットの構成の遷移
【図１０】経路変更するパケットフローを決定する手順
【図１１】本発明の実施に必要な装置構成
【図１２】実施例２におけるネットワーク構成
【図１３】実施例２における迂回経路設定における、探索パケットと経路書換パケットと探索応答パケットの動きとＩＰ中継装置の動作
【図１４】実施例２における探索パケットを受信したＩＰ中継装置の動作手順
【図１５】実施例２における探索応答パケットの構成例
【図１６】実施例２における探索応答パケットを受信したＩＰ中継装置の動作手順
【図１７】実施例２における経路書換パケットの構成例
【図１８】実施例３におけるネットワーク構成
【図１９】実施例３における探索パケットの構成例
【図２０】実施例３における設定変更通知に使用するパケットの構成例
【発明を実施するための形態】
【実施例１】
【００１２】
図２は、本発明の第１の実施形態を表した全体図である。本発明におけるネットワークは、メッシュ状に装置を接続してなるパケット通信網であり、送信元装置４０と宛先装置４１の間は経路とＩＰ中継装置１０−Ｎから構成される。また、各装置は、通信の要求に応じて、ＩＰ中継装置、送信元装置または宛先装置となることができる。
【００１３】
図１１は、実施例における個別のＩＰ中継装置の図面である。
【００１４】
ＩＰ中継装置５００が持つ受信ポート５０１とパケット転送機能部５０２、送信ポート５０５は、従来のＩＰ中継装置と同様の機能を持つ。ＩＰ中継装置５００は更に、迂回経路設定パケット処理部５２１と、経路変更パケットフロー決定部５２０を持つ。迂回経路設定パケット処理部５２１は、探索パケットと、経路書換パケットの処理を行う。迂回経路設定パケット処理部５２１が持つ迂回経路設定パケット監視部５０７と、輻輳検知部が持つ輻輳検知部５０６とサンプリング機能部５０９は、受信ポート５０１を監視する。
【００１５】
迂回経路設定パケット監視部５０７が、経路を探索する探索パケットを検知したとき、迂回経路設定パケット判定部５１６は、経路終端判定部５１１において探索パケットが迂回経路を発見したかどうかを判定する。ループ判定部５１２では、探索パケットがループしているかを判定する。迂回経路選択部５１５では、探索パケットを複数受信したときに、探索パケットが示唆する迂回経路の中から迂回経路を一つ選択する。迂回経路設定パケット生成部５１３では、ネットワークに再送出する探索パケットおよび経路書換パケットを生成し、または後述する経路変更パケットフロー決定部５２０の指示に応じて探索パケットを生成する。
【００１６】
経路書換部５０８は、迂回経路設定パケット判定部５１６において、経路書換パケットを検知したときに呼び出される。経路書換部５０８は、経路変更するパケットフロー情報を、経路表５０３に書き込む。
【００１７】
経路変更パケットフロー決定部５２０の輻輳検知部５０６は、受信ポート５０１からの情報に基づき輻輳を検知する。サンプリング機能部５０９は受信ポート５０１の情報から一定の条件の下でサンプリングしたパケットフローの情報を輻輳検知部５０６からの指示に基づき、経路変更パケットフロー計算部５１４に送る。当該情報と、優先度情報テーブル５１０にて保持される優先度情報を用いて、経路変更パケットフロー計算部５１４は、経路変更するパケットフローを決定し、迂回経路設定パケット生成部５１３に探索パケットの生成を要求する。
【００１８】
図６は、実施例における探索パケットの構成例を表した図である。
【００１９】
探索パケット２５０は、ＭＡＣヘッダやＩＰヘッダなどの従来手法によるヘッダの他、探索パケットであることを示すフラグ情報２５１と、目的の宛先装置のＩＰアドレス情報２５２、輻輳リンクのＩＰアドレス情報２５３、通過したＩＰ中継装置から探索パケットが収集した情報２５４、経路変更するパケットフローの情報２５５を持つ。探索パケットが収集した情報２５４は、探索パケットが通過したＩＰ中継装置が持つＩＰアドレス等の識別情報、または探索パケットが通過するリンクにおける帯域使用率やバッファの空き容量等の輻輳情報、あるいはその組み合わせのリストである。
【００２０】
図７は、実施例における経路書換パケットの構成例を示した図である。
【００２１】
経路書換パケット３００は、ＭＡＣヘッダやＩＰヘッダなどの従来手法によるヘッダの他、経路書換パケットであることを示すフラグ情報３０１、目的の宛先装置のＩＰアドレス情報３０２、輻輳を検知したＩＰ中継装置のＩＰアドレス情報３０３、迂回経路情報３０４、経路変更するパケットフロー情報３０５を持つ。目的の宛先装置のＩＰアドレス情報３０２、輻輳を検知したＩＰ中継装置のＩＰアドレス情報３０３、迂回経路情報３０４、経路変更するパケットフロー情報３０５は、それぞれ対応する探索パケット２５０に保持されていた目的の宛先装置のＩＰアドレス情報２５２、輻輳リンクのＩＰアドレス情報２５３、通過したＩＰ中継装置から探索パケットが収集した情報２５４、経路変更するパケットフローの情報２５５と同等の情報である。
【００２２】
図３は、実施例のＩＰ中継装置における、輻輳検知時の動作を示したフロー図である。
【００２３】
ＩＰ中継装置５００は輻輳検知部５０６において、輻輳を検知した後（ステップ１００）、経路変更パケットフロー計算部５１４において、経路変更するパケットフローを決定する（ステップ１０１）。ここでパケットフローとは、パケットの送信元ＩＰアドレスや宛先ＩＰアドレスの組み合わせか、ToSフィールドやプロトコル番号の値か、その他パケットのＩＰヘッダに含まれる情報かその組み合わせによって定義可能なパケット群を指す。ネットワーク中のパケットフローの数はネットワークの規模によっては１０万通りを超えることもあるため、輻輳の回避に効果的なフローを選定しなければ、パケットフローの経路制御に必要なメモリ量を増大させてしまう。経路変更するパケットフローの決定手順は図１０を用いて後述する。
【００２４】
経路変更するパケットフローの決定後、ＩＰ中継装置５００は、迂回経路設定パケット生成部５１３において探索パケットを生成する（ステップ１０２）。探索パケット生成後、ＩＰ中継装置５００は、送信ポート５０５より、輻輳が検知されたリンク以外の隣接するＩＰ中継装置に対して探索パケットを送信する（ステップ１０３）。
なお、輻輳を検知したＩＰ中継装置５００は、図６の探索パケット２５０に、探索パケットのホップ数を記述したフィールドを追加してもよい。もし探索パケット２５０内に探索ホップ数を記述したフィールドを追加するとき、ＩＰ中継装置はホップ数に対して、あらかじめ設定した規定値を持つ。ＩＰ中継装置は、探索パケット２５０を生成するときに最大ホップ数を探索パケットに書き込み、探索パケットを受信したＩＰ中継装置は、受信した探索パケットのホップ数の値を削減する。もし、探索パケットのホップ数の値が、あらかじめ設定した規定値よりも小さくなったときは、ＩＰ中継装置は探索パケットを生成しない。本操作により、探索パケットが無制限に生成、送信されてしまうことを防ぐこともできる。
【００２５】
図１０は、実施例の経路変更パケットフロー決定部５２０において、経路変更をするパケットフローを決定する動作を示したフロー図である。
【００２６】
ＩＰ中継装置５００は、サンプリング機能部５０９によりパケットのサンプリングを行い、帯域使用率の大きいパケットフロー情報を取得しておく（ステップ４５０）。ＩＰ中継装置５００は、輻輳検知部５０６において輻輳を検知した後（ステップ４５１）、サンプリング機能部５０９によってサンプリングしたパケットフロー情報と優先度テーブル５１０が持つパケットフローの優先度情報を比較し（ステップ４５２）優先度情報に含まれる、あらかじめ設定したポリシーに従って経路変更パケットフロー計算部５１４において経路変更するパケットフローを決定する（ステップ４５３）。
【００２７】
経路変更するパケットフローの選び方は一意ではなく、ポリシーによって様々なバリエーションがある。例えば、もし設定したポリシーが、優先度の高いパケットフローの経路を維持させるというポリシーのときは、帯域使用率が大きく優先度の低いパケットフローの経路を変更する。また、もし設定したポリシーが、優先度の高いパケットフローを迂回経路に避難させるというポリシーのときは、優先度の高いパケットフローの経路を変更する。その他のポリシーのときに経路変更するパケットフローを選択する方法として、優先度テーブルに含まれるパケットフローのうち、サンプリング結果に含まれるパケットフローを選択する方法と、優先度テーブルに含まれるパケットフローのうち、サンプリング結果に含まれないパケットフローを選択する方法と、サンプリング結果に含まれるパケットフローのうち、優先度テーブルに含まれないパケットフローを選択する方法と、サンプリング結果に含まれないパケットフローのうち、優先度テーブルに含まれないパケットフローを選択する方法とがある。
【００２８】
経路制御するパケットフローを選定して、経路変更の対象とするトラヒック条件を指定することで、迂回経路発見処理ならびに経路書き換え処理に伴う通信量が大きくなってしまう課題に対して、パケットフローの制御に必要なメモリ量を抑制して通信量の削減をすることが可能となり、優先度の高いパケットフローの通信経路が不用意に書き換えられることを回避しやすくなる効果が得られる。
【００２９】
図４は、実施例のＩＰ中継装置における、探索パケット受信時の動作を示したフロー図である。
【００３０】
例えば、ＩＰ中継装置１０−２において、迂回経路設定パケット監視部５０７にて探索パケットを受信した後（ステップ１５０）、経路終端判定部５１１において、経路表５０３を確認し、まず探索パケットが持つ目的の宛先装置のＩＰアドレス情報２５２を用いて目的の宛先装置が隣接しているかを確認する。目的の宛先装置が隣接しているとき迂回経路を発見したとし、隣接していないとき迂回経路は未発見とする（ステップ１５１）。以下、未発見の場合を述べる。
【００３１】
ループ判定部５１２は、探索パケットを受信したときに、当該探索パケットの中に記録された探索パケットが収集した情報２５４を参照し、自装置のＩＰアドレスが格納されていた場合には、自装置を一度経由したものとして探索パケットのループを防ぐため、探索パケットを破棄する（ステップ１５２）。一致する情報が存在しないときは、迂回経路設定パケット生成部５１３において、受信した探索パケットのコピーにおける収集情報部分２５４に自ＩＰ中継装置の情報を追加で書き込み（ステップ１５３）、送信ポート５０５から探索パケットを受信したリンク以外の、隣接するＩＰ中継装置に探索パケットを送信する（ステップ１５４）。
【００３２】
ここで、図８にＩＰ中継装置１０−１、１０−２、１０−３が送信した探索パケットの構成を示す。探索パケット３０−１、３０−２、３０−３の相違点は、通過したＩＰ中継装置から収集した情報３５３−１、３５３−２、３５３−３である。探索パケットフラグ情報３５０、目的の宛先装置のＩＰアドレス情報３５１、輻輳リンクのＩＰアドレス情報３５２、経路変更するパケットフロー情報３５４は同じ内容である。探索パケットが目的の宛先装置を発見したとき、探索パケット３０−３がＩＰ中継装置から収集した情報３５３−１、３５３−２、３５３−３が迂回経路で経由すべきＩＰ中継装置のアドレスとなる。
【００３３】
次に、ステップ１５１において、迂回経路を発見した場合の動作を述べる。
【００３４】
ＩＰ中継装置１０−４は目的の宛先装置が隣接しているため、迂回経路を発見した場合の動作手順を取る（ステップ１５１でＮＯへ遷移）。ＩＰ中継装置１０−４は、迂回経路を発見した後、一定時間待機動作を取り、他の探索パケットを受信するのを待つ（ステップ１５５）。待機動作後、受信した探索パケットが１つであったとき、その探索パケットが収集した迂回経路情報である経由すべきＩＰ中継装置のＩＰアドレス３５３−１〜３に基づいて迂回経路を選択する。一方、受信した探索パケットが複数であったとき、迂回経路選択部５１５においてあらかじめ設定されたアルゴリズムに従い、迂回経路を選択する（ステップ１５６）。迂回経路を選択するアルゴリズムは、経路上のＩＰ中継装置の数が最も小さいものを選択するアルゴリズム、経路の帯域使用率が最も小さいものを選択するアルゴリズム、あるいは探索パケットが収集した輻輳に関する他の情報を使って、最も遅延の小さい経路あるいは最も輻輳が発生しにくい経路を選択するアルゴリズムのほか、従来手法を用いても良い。
【００３５】
迂回経路選択部５１５において迂回経路を決定した後、迂回経路設定パケット生成部は、経路書換パケットを生成する（ステップ１５７）。送信ポート５０５は、生成した経路書換パケットをＩＰ中継装置１０−３に送信する（ステップ１５８）。
【００３６】
図５は、実施例のＩＰ中継装置における、探索パケット受信時の動作を示したフロー図である。
【００３７】
例えば、ＩＰ中継装置１０−３において、迂回経路設定パケット監視部５０７にて経路書換パケットを受信した後（ステップ２００）、経路書換部５０８は、パケット転送機能部５０２に保持された経路表５０３を、経路書換パケットが持つ経路変更するパケットフロー情報３０５に該当するパケットフローに対して、ネクストホップをＩＰ中継装置１０−４に書き換える処理を行う（ステップ２０１）。その後、経路終端判定部５１１は、輻輳を検知したＩＰ中継装置のＩＰアドレス３５２と自ＩＰ中継装置のＩＰアドレスを比較する。両ＩＰアドレスが一致するとき、迂回経路の設定は終了とし、それ以外のときは迂回経路の設定は終了していないとする（ステップ２０２）。迂回経路設定時は動作手順が完了するため、以下迂回経路の設定が完了していない場合について説明する。ＩＰ中継装置１０−３においては、ステップ２０２でのＩＰアドレス比較の結果が一致しないため、迂回経路の設定は終了していないときの動作手順を取る（ステップ２０２でＮＯへ遷移）。迂回経路の設定が未完了であった場合、迂回経路設定パケット生成部５１３は、受信した経路書換パケットのコピーから、ＩＰ中継装置１０−４のＩＰアドレス情報４０３−４を削除し（ステップ２０３）、送信ポート５０５は、ＩＰ中継装置１０−２に経路書換パケットを送信する（ステップ２０４）。
【００３８】
ここで、図９にＩＰ中継装置１０−４、１０−３、１０−２が送信する経路書換パケットの構成を示す。経路書換パケット３１−１、３２−２、３３−３の相違点は、迂回経路情報４０３−１、４０３−２、４０３−３、４０３−４のみであり、経路書換パケットであること示すフラグ４００、目的の宛先装置のＩＰアドレス４０１、輻輳リンクのＩＰアドレス４０２、経路変更するパケットフロー情報４０４は同じ内容である。迂回経路情報４０３−１、４０３−２、４０３−３、４０３−４は、迂回経路の設定に使用された後不要となるため、ＩＰ中継装置を通過するたびに削除されていく。なお、本実施例では削除される場合を示したが、削除せずそのまま転送しても経路書換パケットの情報量は多くなるが、目的には十分であり、差し支えない。
【００３９】
次に、ステップ２０２において迂回経路の設定が完了したと判定した場合の動作について説明する。
【００４０】
ＩＰ中継装置１０−１は、自ＩＰ中継装置のＩＰアドレスと経路書換パケットが持つ輻輳リンクのＩＰアドレス４０２が一致する。そのため迂回経路の設定が終了したときの動作手順を取り（ステップ２０２でＹＥＳへ遷移）、迂回経路設定処理を終了する。
【００４１】
図１は、本実施例において、各ＩＰ中継装置が動作する様子を表したシーケンス図である。本図面では、ＩＰ中継装置１０−１が輻輳を検知した場合に、迂回経路を探索する探索パケットの経路と、迂回経路を設定する経路書換パケットの経路と、各パケットを受信した場合のＩＰ中継装置の動作を示す。
【００４２】
ＩＰ中継装置１０−１において輻輳を検知した場合（２０）、前述の方法によって経路変更パケットフローが決定され（２１）、探索パケットが生成されて、ネットワークに送出される（３０−１）。探索パケットを受け取ったＩＰ中継装置１０−２〜３は、探索パケットを受信した場合の動作手順に従って、情報の書き込みを行い（２２−１〜２）、再び探索パケットをネットワークに送出する（３０−２〜３）。ＩＰ中継装置１０−４において、受け取った探索パケットに基づき、迂回経路を発見した場合（２３）、迂回経路発見時の動作手順に従い、経路書換パケットを生成し、探索パケットの直近の送信元であるＩＰ中継装置１０−３に送出する（３１−１）。経路書換パケットを受信したＩＰ中継装置１０−３〜２は、それぞれ受け取った経路変更パケットの情報に基づき、経路を変更し（２４−１〜２）、再び経路変更パケットをネットワークに送出する（３１−２〜３）。最後に、当初の探索パケットの送出元であるＩＰ転送装置１０−１で、経路書換パケットを受信し、経路変更処理を行うことで（２４−３）、一連のシークエンスは完了する。
【００４３】
以上、本実施の形態によれば、ＩＰ中継装置が輻輳を検知したときでも、迂回経路が発見されないときは経路の変更を行わないことが可能となる。輻輳を検知したＩＰ中継装置が、まず、探索パケットにより迂回経路を特定した後で、経路書換パケットにより迂回経路の設定を行うことにより、迂回経路を確実に設定することが可能となる。また、本実施の形態によれば、ＩＰ中継装置は、迂回経路の情報を探索パケットにより収集するため、ＩＰ中継装置は迂回経路を発見するために、ネットワーク全体の構成情報を保持する必要がない。
【実施例２】
【００４４】
図１２は、本発明の第２の実施形態を示した全体図である。宛先装置５６１が複数のＩＰ中継装置５５０−１、５５０−２、５５０−３に接続している。この実施形態では、ＩＰ中継装置５５０−１が輻輳を検知した場合、ＩＰ中継装置５５０−１からの探索パケットを受信し、迂回経路を発見したと判定したＩＰ中継装置５５０−３あるいは５５０−２がそれぞれ経路書換パケットをネットワークに送信する。そのため、二種類の経路書換パケットが経路を変更するため、適切な迂回経路が設定されない可能性がある。そこで、本実施の形態では、宛先装置が複数のＩＰ中継装置に接続しているときに、適切な迂回経路を設定することを可能とする。
【００４５】
ＩＰ中継装置の構成は、第１の実施形態において説明した図１１と同一である。本実施例におけるＩＰ中継装置においては一部構成の機能が異なる。迂回経路設定パケット監視部５０７は、さらに探索応答パケットの受信を監視する。迂回経路設定パケット生成部５１３は、さらに、探索応答パケットを生成する。
【００４６】
図１５は、実施例における探索応答パケットの構成例を示した図である。
【００４７】
探索応答パケット７００は、探索応答パケットであることを示すフラグ情報７０１、目的の宛先装置のＩＰアドレス７０２、輻輳を検知したＩＰ中継装置のＩＰアドレス情報７０３、迂回経路情報７０４、経路変更するパケットフローの条件７０５を持つ。迂回経路情報７０４は、第１の実施例における経路書換パケット３００の迂回経路情報３０４と同等の情報を有しており、当該情報は、当該探索応答パケットが生成される際に基となった探索パケット２００における探索パケットが収集した情報２５４と同等の情報である。
【００４８】
図１７は、実施例における経路書換パケットの構成例を示した図である。
【００４９】
経路書換パケット８００は、経路書換パケットフラグ８０１、目的の宛先装置のＩＰアドレス８０２、迂回経路情報８０４、経路変更するパケットフロー条件８０５を持つ。ここで、本実施形態の経路書換パケット８００が、第１の実施形態に属する図７の経路書換パケット３００と異なる点は、輻輳を検知したＩＰ中継装置のＩＰアドレス３０３ではなく、探索応答パケットの送信元ＩＰアドレス８０３を持つ点である。
【００５０】
図１４は、実施例のＩＰ中継装置における探索パケット受信時の動作を示したフロー図である。
【００５１】
探索パケットを迂回経路設定パケット監視部５０７で受信したＩＰ中継装置が迂回経路を発見したかどうかを、迂回経路設定パケット判定部５１６で判断するまでの動作手順（ステップ６５０、６５１）は、図４に示す実施例１の手順（ステップ１５０、１５１）と同様である。例えば、ＩＰ中継装置５５０−２は目的の宛先装置５６１と隣接するため、迂回経路を発見した時の動作手順を取る（ステップ６５１でＮＯへ遷移）。ＩＰ中継装置５５０−２は、迂回経路を発見した後、迂回経路設定パケット生成部５１３は、探索パケットが収集した迂回経路情報を使って探索応答パケットを生成する（ステップ６５２）。送信ポート５０５は、生成した探索応答パケットを、輻輳を検知したＩＰ中継装置５５０−１に向けて送信する（ステップ６５３）。経路終端判定部５１１において、迂回経路を発見していないと判定した場合（ステップ６５１でＹＥＳへ遷移）以降の動作フローは、図４に示す実施例１の手順と同様であるので省略する。
【００５２】
図１６は、実施例のＩＰ中継装置における探索応答パケット受信時の動作を示したフロー図である。ＩＰ中継装置は探索応答パケットを迂回経路設定パケット監視部５０７で受信した後（ステップ７５０）、迂回経路設定パケット判定部５１６は、探索応答パケットが持つ、輻輳を検知したＩＰ中継装置のＩＰアドレス７５３と自ＩＰ中継装置のＩＰアドレスを比較する。両ＩＰアドレスが一致するとき、探索応答パケットが経路変更の開始地点に到着したと判断する（ステップ７５１）。
【００５３】
両ＩＰアドレスが一致しないときは、受信した探索応答パケットが持つ迂回経路情報８５４を基に、当該パケットに対応する探索パケットが自装置を通過する前に通過したＩＰ中継装置のアドレス情報を取得して、迂回経路設定パケット生成部５１３は、次に転送すべきＩＰ中継装置宛の同内容の探索応答パケットを生成し（ステップ７５７）、送信ポート５０５は、迂回経路に沿って生成した探索応答パケットを送信する（ステップ７５８）。
【００５４】
例えば、ＩＰ中継装置５５０−１では、輻輳を検知したＩＰ中継装置のＩＰアドレス７０３と自ＩＰ中継装置のＩＰアドレスが一致するため、経路変更の開始地点に探索応答パケットが到着したと判断する（ステップ７５１でＹＥＳへ遷移）。探索応答パケットが経路変更の開始地点に到着したと判定した後、ＩＰ中継装置５５０−１は一定時間待機動作を取り、他の探索応答パケットを受信するのを待つ（ステップ７５２）。もし受信した探索応答パケットの数が１つだったとき、迂回経路選択部５１５は、受信した探索応答パケットが持つ迂回経路情報を選択する。もし受信した探索応答パケットの数が複数だったときにおいては、迂回経路選択部５１５においてあらかじめ設定されたアルゴリズムに従い、探索応答パケットが持つ迂回経路情報の中から適切な迂回経路を１つ選択する（ステップ７５３）。迂回経路を選択するアルゴリズムは、経路上のＩＰ中継装置の数を用いるアルゴリズム、経路の帯域使用率を用いるアルゴリズム、探索パケットが収集したその他の情報を用いるアルゴリズム、または従来手法を用いてもよい。
【００５５】
迂回経路選択部５１５において、迂回経路選択後、経路書換部５０８は、経路表５０３を、受信した探索応答パケットが持つ経路変更するパケットフローに対して、ネクストホップをＩＰ中継装置５５０−２または３に書き換える処理を行う（ステップ７５４）。経路書換後、迂回経路設定パケット生成部、経路書換パケットを生成する（ステップ７５５）。送信ポート５０５は、生成した経路書換パケットをネクストホップに設定したＩＰ中継装置に対して送信する（ステップ７５６）。
【００５６】
経路書換パケットに伴う動作フローは、実施例１と同様であるので省略する。
【００５７】
図１３は、本実施例において、各ＩＰ中継装置が動作する様子を示したシーケンス図である。
【００５８】
本図面では、ＩＰ中継装置５５０−１が輻輳を検知した場合に、迂回経路を探索する探索パケットの経路と、迂回経路を設定する経路書換パケットの経路と、各パケットを受信した場合のＩＰ中継装置の動作を示す。
【００５９】
ＩＰ中継装置５５０−１において輻輳を検知した場合（６００）、前述の方法によって経路変更パケットフローが決定され（６０１）、探索パケットが生成されて、ネットワークに送出される（６１０−１）。探索パケットを受け取ったＩＰ中継装置５５０−２〜３において、受け取った探索パケットに基づき、迂回経路を発見した場合（６０２〜６０３）、迂回経路発見時の動作手順に従い、探索応答パケットを生成し、探索パケットの直近の送信元であるＩＰ中継装置５５０−１に送出する（６２０−１〜２）。探索応答パケットを受信したＩＰ中継装置５５０−１は、一定時間待機後、受信した全ての探索応答パケットの情報を基に、迂回経路をＩＰ中継装置５５０−２に定め、ネクストホップを変更のうえ、経路書換パケット６３０を送出する。最後に、ＩＰ転送装置５５０−２で、経路書換パケットを受信し、経路変更処理を行うことで（６０６）、一連のシークエンスは完了する。
【００６０】
以上、本実施の形態によれば、輻輳を検知したＩＰ中継装置に迂回経路情報を通知する探索応答パケットを使用し、輻輳を検知したＩＰ中継装置が、探索応答パケットを受信した後、経路書換パケットを迂回経路に送信することで、目的の宛先装置に複数のＩＰ中継装置が接続されているときでも、適切な迂回経路を設定することが可能となる。
【実施例３】
【００６１】
第３の実施の形態では、ＩＰ中継装置が、探索パケット内に、探索パケットが通る経路を指定経路としてあらかじめ書き込み、探索パケットを受信したＩＰ中継装置が探索パケット内の指定経路に従って探索パケットを送信することで、特定の経路の情報を収集し、迂回経路を設定することを可能とする。
【００６２】
図１８は、本発明の第３の実施形態におけるネットワーク構成を示す。宛先装置までの経路として、経路８７０と、経路８７０の予備経路８８０−１、８８０−２がある。経路８７０で輻輳が発生したとき、ＩＰ中継装置８５０−１は、予備経路８８０−１と予備経路８８０−２に沿ってそれぞれ探索パケットを送信することを特徴とする。探索パケットは指定経路上のＩＰ中継装置とリンクの情報を収集し、ＩＰ中継装置８５０−４は受信した探索パケットの中から、迂回経路を一つ選択する。
【００６３】
図１９は、本実施例における探索パケットの構成例を表した図である。
【００６４】
探索パケット９００は、ＭＡＣヘッダやＩＰヘッダなどの従来手法によるヘッダの他、探索パケットであることを示すフラグ情報９０１と、探索パケットの指定経路情報９０２、通過したＩＰ中継装置から探索パケットが収集した情報９０３、経路変更するパケットフローの情報９０４を持つ。このうち、実施例１に属する図６の図示と異なる点は、目的の宛先装置のＩＰアドレス情報２５２の代わりに、予め探索パケットが経由すべきＩＰ中継装置を指定した指定経路情報９０２を持つことである。
【００６５】
経路書換パケットの構成例は、実施例１と同様であるので省略する。
【００６６】
ＩＰ中継装置の構成は、実施例１において説明した図１１と同一である。本実施例におけるＩＰ中継装置においては一部構成の機能が異なる。迂回経路設定パケット生成部５１３は、さらに、指定経路情報のデータベースをもち、当該データベースに基づいて生成する探索パケットに指定経路情報９０２として記載する。指定経路情報のデータベースは、外部装置あるいはシステム管理者からの設定変更通知により設定される。設定変更通知パケットを受信した迂回経路設定パケット監視部５０７は、設定変更通知パケットの内容を迂回経路設定パケット判定部５１６に通知し、迂回経路設定パケット判定部５１６は指定経路情報を迂回経路設定パケット生成部５１３のデータベースに登録する。
【００６７】
図２０は、本実施例において、予備経路８８０−１を設定する際の設定変更通知に使用するパケットの構成例である。設定変更通知に使用するパケット９５０は、設定変更通知フラグ９５１と、予備経路８８０−１上のIP中継装置８５０−３のIPアドレス９５２と、予備経路８８０−１上のIP中継装置８５０−４のIPアドレス９５３とを含む。輻輳を検知したＩＰ中継装置８５０−１は、探索パケットを生成する。探索パケットの生成フローは、実施例１における図３と同様である。ステップ１０２において、探索パケットを生成する際に、前述したとおり、探索パケットに指定経路情報９０２を格納する。
【００６８】
探索パケットを受信したＩＰ中継装置の処理フローは、実施例１の図４と同様である。ここで、ステップ１５３において、迂回経路設定パケット生成部５１３が、探索パケットに自ＩＰ中継装置の情報を書き込んだ後、受信した探索パケットが持つ、探索パケットの指定経路情報９０２が示す、次のＩＰ中継装置を宛先として、探索パケットを生成し、生成した探索パケットを送信する（ステップ１５４）。
【００６９】
探索パケットの指定経路９０２の終端である、ＩＰ中継装置８５０−４は、予備経路８８０−１と予備経路８８０−２からそれぞれ探索パケットを受信する。ＩＰ中継装置８５０−４は、受信した二つの探索パケットが持つ、探索パケットが収集した情報９０３を使い、実施例１と同様に、あらかじめ設定したアルゴリズムに従い、迂回経路を選択する（ステップ１５６）。迂回経路を選択した後、ＩＰ中継装置８５０−４は、経路書換パケットを生成し（ステップ１５７）、生成した経路書換パケットを選択した迂回経路に沿って送信し（ステップ１５８）、迂回経路の設定を行う。
【００７０】
以上、本実施の形態によれば、探索パケットの経路をあらかじめ指定することで、特定の経路に対し、経路上の輻輳情報を収集し、迂回経路を設定することが可能となる。
【符号の説明】
【００７１】
２５０探索パケット
３００経路書換パケット
５００ＩＰ中継装置
５０１受信ポート
５０２パケット転送機能部
５０３経路表
５０５送信ポート
５０６輻輳検知部
５０７迂回経路設定パケット監視部
５０８経路書換部
５０９サンプリング機能部
５１０優先度情報テーブル
５１１経路終端判定部
５１２ループ判定部
５１３迂回経路設定パケット生成部
５１４経路変更パケットフロー計算部
５１５迂回経路選択部
５１６迂回経路設定パケット判定部
５２０経路変更パケットフロー決定部
５２１迂回経路設定パケット処理部
７００探索応答パケット
９００予備経路情報を持つ探索パケット
９５０設定変更通知に使用するパケット

【特許請求の範囲】
【請求項１】
ネットワークに接続されて使用するパケット転送装置であって、
経路情報を記録する記憶部と、
パケットの送受信手段と、
前記転送装置を通過するトラヒックの宛先装置についての情報に基づいて、宛先装置を迂回先装置として前記迂回先装置に至る迂回経路を探索する為の探索パケットを生成し、前記送受信手段によって前記ネットワークに送信する探索パケット生成手段と、
前記送受信手段を介して受信されたパケットが探索パケットまたは経路書換パケットであることを判別する受信パケット判別手段と、
前記受信されたパケットが探索パケットであると前記受信パケット判別手段で判別された場合、前記受信した探索パケットが探索する経路の迂回先装置の情報が、前記転送装置の隣接装置の情報と一致するかどうかを判別する迂回先装置隣接判別手段と、
前記転送装置の隣接装置と前記受信された探索パケットが探索する経路の迂回先装置とが一致すると、前記迂回先装置隣接判別手段で判別された場合、前記受信された探索パケットの経由装置を宛先とした経路書換パケットを生成し、前記送受信手段によってネットワークに送信する経路書換パケット生成手段と、
前記転送装置の隣接装置と前記受信された探索パケットが探索する経路の迂回先装置とが一致しないと、前記迂回先装置隣接判別手段で判別された場合、前記受信された探索パケット内に、前記転送装置を経由したことを記録し、前記送受信手段によってネットワークに送信する探索パケット転送手段と、
前記受信されたパケットが経路書換パケットであると前記受信パケット判別手段で判別された場合、前記受信された経路書換パケットに従って、前記経路情報を書き換える経路情報書換手段と、
を備えるパケット転送装置。
【請求項２】
請求項１に記載のパケット転送装置であって、
前記探索パケット生成手段は、前記探索パケットに、前記迂回先装置のアドレスと、前記経由装置のアドレスと、前記経由装置の経由順序情報とを少なくとも記述し、
前記探索パケット転送手段における、前記転送装置を経由したことの記録は、前記転送装置のアドレスを記録することを特徴とするパケット転送装置。
【請求項３】
請求項２に記載のパケット転送装置であって、
前記経路書換パケット生成手段は、前記経路書換パケットに、前記探索パケットに記述された前記迂回先装置のアドレスと、前記経由装置のアドレスと、前記経由装置の経由順序情報を少なくとも記述し、前記経路書換パケットは前記経由順序情報を元に、最後に経由した装置のアドレスを宛先アドレスとして生成することを特徴とするパケット転送装置。
【請求項４】
請求項３に記載のパケット転送装置であって、
前記経路情報書換手段は、前記受信された経路書換パケットに記述された迂回先装置アドレスに関する前記転送装置の経路情報を、前記受信された経路書換パケットの送出元装置を経由とする情報に書き換えることを特徴とし、
さらに、
前記受信された経路書換パケットに記述された前記経由順序情報を元に、前記転送装置の前に前記受信された経路書換パケットに関する探索パケットが経由した装置のアドレスを、前記受信された経路書換パケットの宛先アドレスとして再設定し、前記送受信手段によってネットワークに送出する経路書換パケット転送手段と、
を備えることを特徴とするパケット転送装置。
【請求項５】
請求項１に記載のパケット転送装置であって、
前記探索パケット転送手段は、前記受信された探索パケットの中に既に前記転送装置を経由したことを示す情報が記録されていない場合に、前記記録を行うことを特徴とするパケット転送装置。
【請求項６】
請求項５に記載のパケット転送装置であって、
さらに、
前記受信された探索パケットの中に既に前記転送装置を経由したことを示す情報が記録されている場合に、前記受信された探索パケットを前記転送装置で破棄し、前記ネットワーク上に再送出しないことを特徴とするパケット転送装置。
【請求項７】
請求項１に記載のパケット転送装置であって、
前記探索パケット生成手段は、前記探索パケットの宛先にブロードキャストアドレスを設定することを特徴とするパケット転送装置。
【請求項８】
請求項１に記載のパケット転送装置であって、
前記探索パケット生成手段は、前記探索パケットの最大ホップ数を設定することを特徴とするパケット転送装置。
【請求項９】
請求項１に記載のパケット転送装置であって、
さらに、パケット蓄積部と、
前記パケット蓄積部が輻輳状態になったことを検知する輻輳状態検知手段と、を備え、
前記トラヒックは、前記パケット蓄積部で輻輳状態が検知された場合に、輻輳を惹起したトラヒックであることを特徴とするパケット転送装置。
【請求項１０】
請求項９に記載のパケット転送装置であって、
前記探索パケット生成手段は、前記パケット蓄積部においてパケットサンプリングを行い、当該サンプリングされたパケットに基づいて高利用率のトラヒックであると判別されたトラヒックについて、迂回経路を探索する為の探索パケットを生成することを特徴とするパケット転送装置。
【請求項１１】
請求項１０に記載のパケット転送装置であって、
前記記憶部に、さらにトラヒック優先情報を備え、
前記探索パケット生成手段は、前記判別されたトラヒックのうち、前記トラヒック優先情報に記載がないトラヒックのみを対象とすることを特徴とするパケット転送装置。
【請求項１２】
請求項１０に記載のパケット転送装置であって、
前記探索パケットは、前記判別されたトラヒックの情報を少なくとも備えることを特徴とするパケット転送装置。
【請求項１３】
請求項１に記載のパケット転送装置であって、
前記記憶部は、宛先装置毎の予備経路情報を記録し、
前記探索パケット生成手段は、さらに、前記宛先装置毎の予備経路情報を探索パケットに記録し、
前記探索パケット転送手段は、前記探索パケットに記録された予備経路情報に基づいてパケットを転送することを特徴とするパケット転送装置。
【請求項１４】
複数のパケット転送装置を有するネットワークにおいてパケット転送の迂回経路を設定する方法であって、
第１のパケット転送装置を通過するトラヒックの宛先装置についての情報に基づいて、宛先装置を迂回先装置として前記迂回先装置に至る迂回経路を探索する為の探索パケットを生成し、前記ネットワークに送信する第１の工程と、
第２のパケット転送装置が前記探索パケットを受信した場合に、前記受信した探索パケットが探索する経路の迂回先装置の情報が、前記転送装置の隣接装置の情報と一致するかどうかを判別し、前記第２のパケット転送装置の隣接装置と前記探索パケットが探索する経路の迂回先装置とが一致すると判別された際には、前記探索パケットの経由装置を宛先とした経路書換パケットを生成して前記ネットワークに送信し、前記第２のパケット転送装置の隣接装置と前記探索パケットが探索する経路の迂回先装置とが一致しないと判別された際には、前記探索パケット内に、前記第２のパケット転送装置を経由したことを記録して、前記探索パケットを前記ネットワークに送信する第２の工程と、
前記第１のパケット転送装置または第３のパケット転送装置が前記経路書換パケットを受信した場合に、前記経路書換パケットに従って、前記第１または第３のパケット転送装置の経路情報を書き換える第４の工程と、を備えた迂回経路設定方法。
【請求項１５】
請求項１４に記載の迂回経路設定方法であって、
前記探索パケットは、前記迂回先装置のアドレスと、前記経由装置のアドレスと、前記経由装置の経由順序情報とを少なくとも記述し、
前記第３の工程において、前記転送装置を経由したことの記録は、前記第１または第３のパケット転送装置のアドレスを記録することを特徴とする、迂回経路設定方法。
【請求項１６】
請求項１４に記載の迂回経路設定方法であって、
前記第３の工程において、前記探索パケットの中に既に前記第２のパケット転送装置を経由したことを示す情報が記録されている場合に、前記探索パケットを前記第２のパケット転送装置で破棄し、前記ネットワーク上に再送出しないことを特徴とする、迂回経路設定方法。
【請求項１７】
請求項１４に記載の迂回経路設定方法であって、
前記第１の工程は、さらに前記第１のパケット転送装置の備えるパケット蓄積部において輻輳状態となったことを検知し、前記パケット蓄積部においてパケットサンプリングを行い、サンプリングされたパケットに基づいて高利用率のトラヒックであると判別されたトラヒックについて、迂回経路を探索する為の探索パケットを生成することを特徴とする、迂回経路設定方法。
【請求項１８】
ネットワークに接続されて使用するパケット転送装置であって、
経路情報を記録した記憶部と、
パケットの送受信手段と、
前記転送装置を通過するトラヒックの宛先装置についての情報に基づいて、宛先装置を迂回先装置として前記迂回先装置に至る迂回経路を探索する為の探索パケットを生成し、前記送受信手段によって前記ネットワークに送信する探索パケット生成手段と、
前記送受信手段を介して受信したパケットが探索パケット、探索応答パケットまたは経路書換パケットであることを判別する受信パケット判別手段と、
前記受信されたパケットが探索パケットであると前記受信パケット判別手段で判別された場合、前記受信した探索パケットが探索する経路の迂回先装置の情報が、前記転送装置の隣接装置の情報と一致するかどうかを判別する迂回先装置隣接判別手段と、
前記転送装置の隣接装置と前記受信された探索パケットが探索する経路の迂回先装置とが一致すると、前記迂回先装置隣接判別手段で判別された場合、前記受信された探索パケットの送信元装置を宛先とした探索応答パケットを生成し、前記送受信手段によってネットワークに送信する探索応答パケット生成手段と、
前記転送装置の隣接装置と前記受信された探索パケットが探索する経路の迂回先装置とが一致しないと、前記迂回先装置隣接判別手段で判別された場合、前記受信された探索パケット内に、前記転送装置を経由したことを記録し、前記送受信手段によってネットワークに送信する探索パケット転送手段と、
前記受信されたパケットが探索応答パケットであると前記受信パケット判別手段で判別された場合、前記受信した探索応答パケットに従って、前記受信した探索応答パケットに記述された前記探索パケットの経由装置を宛先とした前記経路情報を書き換える経路書換パケットを生成し、前記送受信手段によってネットワークに送信する経路書換パケット生成手段と、
前記受信されたパケットが経路書換パケットであると前記受信パケット判別手段で判別された場合、前記受信された経路書換パケットに従って、前記経路情報を書き換える経路情報書換手段と、
を備えるパケット転送装置。
【請求項１９】
請求項１８に記載のパケット転送装置であって、
前記経路書換パケット生成手段は、前記受信されたパケットが探索応答パケットであると前記受信パケット判別手段で判別された場合、一定時間の間、前記送受信手段が第２のパケットを受信し、前記受信パケット判別手段が第２のパケットが第２の探索応答パケットであると判別されるか否かを待機し、受信された第２のパケットが第２の探索応答パケットであると判別された場合、前記探索応答パケットと前記第２の探索応答パケットのうち一を選択して、当該選択されたパケットの情報に基づき経路書換パケットを生成することを特徴とするパケット転送装置。

【図１】