(57)【要約】【課題】ネットワークトポロジの切断点に相当する特定ノード以降におけるトラヒック集中を回避できるようにする。【解決手段】経路制御装置２０の経路選択部２２で、任意のノードｕの最適化パラメータ値を算出する際、記憶部２４から読み出した、すでに経路が選択されておりかつノードｕとリンクを介して隣接するノードｖの最適化パラメータ値と、ノードｖからノードｕへのリンクのリンク情報と、ノードｕの最適化パラメータ値とから、ノードｕの新たな最適化パラメータ値を算出し、経路選択部２２で選択された経路について、当該経路を構成する各ノードの最適化パラメータ値が基準ホップ数にわたるノード間で変化していない場合、記憶部２４に記憶されている、経路が選択されていないノードの最適化パラメータ値を当該ノードに隣接する経路選択済みのノードとの間のリンクのリンク情報に基づき初期化する。【選択図】  図２
2006074125.tif 000002
【特許請求の範囲】
【請求項１】
リンクを介して網状に接続された複数のノードからなるパケット通信ネットワークに設けられ、パケット通信を行う送信元ノードから次のノードへの経路を当該ネットワークから順次選択していくことにより、前記送信元ノードから所望の宛先ノードまでの経路を選択する経路制御装置であって、
前記各リンクでのパケット転送状況を示すリンク情報を前記各ノードから収集するリンク情報収集部と、
送信元ノードから任意のノードへの経路を選択する際、当該ノードへの経路をそれぞれ評価する最適化パラメータ値に基づき、前記ノードへの経路のいずれかを当該ノードへの経路として選択する経路選択部と、
前記リンク情報収集部で収集されたリンク情報、経路が選択されていないノードの最適化パラメータ値、および前記経路選択部で選択された前記ノードへの経路とその経路を構成する各ノードの最適化パラメータ値を記憶する記憶部とを備え、
前記経路選択部は、任意のノードｕの最適化パラメータ値を算出する際、前記記憶部から読み出した、すでに経路が選択されておりかつ前記ノードｕとリンクを介して隣接するノードｖの最適化パラメータ値と、前記ノードｖから前記ノードｕへのリンクのリンク情報と、前記ノードｕの最適化パラメータ値とから、前記ノードｕの新たな最適化パラメータ値を算出し、
前記経路選択部で選択された前記経路について、当該経路を構成する各ノードの最適化パラメータ値が基準ホップ数にわたるノード間で変化していない場合、前記記憶部に記憶されている、前記経路が選択されていないノードの最適化パラメータ値を、当該ノードに隣接する経路選択済みのノードとの間のリンクのリンク情報に基づき初期化することを特徴とする経路制御装置。
【請求項２】
請求項１に記載の経路制御装置において、
前記経路選択部は、
前記ノードｕの最適化パラメータ値を算出する際、ＭＩＮ−ＭＡＸアルゴリズムに基づいて、前記記憶部に記憶されている前記ノードｖから前記ノードｕへのリンクのリンク情報から得た当該リンクの評価を示すリンクコストと、前記記憶部に記憶されている前記ノードｖの最適化パラメータ値とのいずれか最小値を選択し、この最小値と前記記憶部に記憶されている前記ノードｕの最適化パラメータ値とのいずれか最大値を前記ノードｕの新たな最適化パラメータ値として算出することを特徴とする経路制御装置。
【請求項３】
請求項１に記載の経路制御装置において、
前記経路選択部は、
前記ノードｕの最適化パラメータ値を算出する際、ＭＩＮ−ＭＡＸアルゴリズムに基づいて、前記記憶部に記憶されている前記ノードｖから前記ノードｕへのリンクのリンク情報から得た当該リンクの評価を示すリンクコストと、前記記憶部に記憶されている前記ノードｖの最適化パラメータ値とのいずれか最大値を選択し、この最大値と前記記憶部に記憶されている前記ノードｕの最適化パラメータ値とのいずれか最小値を前記ノードｕの新たな最適化パラメータ値として算出することを特徴とする経路制御装置。
【請求項４】
リンクを介して網状に接続された複数のノードからなるパケット通信ネットワークに設けられた経路制御装置で、パケット通信を行う送信元ノードから次のノードを順次選択することにより、所望の宛先ノードまでの経路を選択する経路選択方法であって、
前記各リンクでのパケット転送状況を示すリンク情報を前記各ノードから収集するリンク情報収集ステップと、
送信元ノードから任意のノードへの経路を選択する際、当該ノードへの経路をそれぞれ評価する最適化パラメータ値に基づき、前記ノードへの経路のいずれかを当該ノードへの経路として選択する経路選択ステップと、
前記リンク情報収集ステップで収集されたリンク情報、経路が選択されていないノードの最適化パラメータ値、および前記経路選択ステップで選択された前記ノードへの経路とその経路を構成する各ノードの最適化パラメータ値を記憶部で記憶する記憶ステップとを備え、
前記経路選択ステップは、任意のノードｕの最適化パラメータ値を算出する際、前記記憶部から読み出した、すでに経路が選択されておりかつ前記ノードｕとリンクを介して隣接するノードｖの最適化パラメータ値と、前記ノードｖから前記ノードｕへのリンクのリンク情報と、前記ノードｕの最適化パラメータ値とから、前記ノードｕの新たな最適化パラメータ値を算出するパラメータ算出ステップと、前記経路選択ステップで選択された前記経路について、当該経路を構成する各ノードの最適化パラメータ値が基準ホップ数にわたるノード間で変化していない場合、当該経路を構成する各ノードの最適化パラメータ値が基準ホップ数にわたるノード間で変化していない場合、前記記憶部に記憶されている、前記経路が選択されていないノードの最適化パラメータ値を、当該ノードに隣接する経路選択済みのノードとの間のリンクのリンク情報に基づき初期化するパラメータ初期化ステップとを有することを特徴とする経路選択方法。
【請求項５】
請求項４に記載の経路選択方法において、
前記パラメータ算出ステップは、ノードｕの最適化パラメータ値を算出する際、ＭＩＮ−ＭＡＸアルゴリズムに基づいて、前記記憶部に記憶されている前記ノードｖから前記ノードｕへのリンクのリンク情報から得た当該リンクの評価を示すリンクコストと、前記記憶部に記憶されている前記ノードｖの最適化パラメータ値とのいずれか最小値を選択し、この最小値と前記記憶部に記憶されている前記ノードｕの最適化パラメータ値とのいずれか最大値を前記ノードｕの新たな最適化パラメータ値として算出することを特徴とする経路選択方法。
【請求項６】
請求項４に記載の経路選択方法において、
前記パラメータ算出ステップは、前記ノードｕの最適化パラメータ値を算出する際、ＭＩＮ−ＭＡＸアルゴリズムに基づいて、前記記憶部に記憶されている前記ノードｖから前記ノードｕへのリンクのリンク情報から得た当該リンクの評価を示すリンクコストと、前記記憶部に記憶されている前記ノードｖの最適化パラメータ値とのいずれか最大値を選択し、この最大値と前記記憶部に記憶されている前記ノードｕの最適化パラメータ値とのいずれか最小値を前記ノードｕの新たな最適化パラメータ値として算出することを特徴とする経路選択方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット通信技術に関し、特にパケット通信に用いる最適経路を選択する経路選択技術に関する。
【背景技術】
【０００２】
近年、インターネットの利用者数の急増や、大容量データをやり取りするアプリケーションの急速な普及により、インターネットの中心部にある大規模なバックボーンネットワークのトラヒック量が爆発的に増加している。したがって、バックボーンネットワークのトラヒック収容能力の向上が求められている。
【０００３】
このようなインターネットで用いられる一般的なルーチングプロトコルでは、トラヒック量を考慮せず、ネットワークトポロジのみを考慮した最適な経路として、例えば合計ホップ数が最短な経路などを選択している。このため、トラヒック量の増加と変動により、特定のリンクやノードに負荷が集中して通信品質が劣化する。
これに対して、通信ネットワークに設備投資を行い、収容できるトラヒック量を増大させることも考えられる。しかしながらこのような方法では、トラヒック増加に比例してネットワークの利用効率が低下し、コスト上昇を招くため、インターネットサービス料金の価格競争力をそぐ可能性がある。
【０００４】
このような状況を打開するための方法として、ネットワーク内のトラヒック状況に応じて、動的にトラヒックを分散させるトラヒックエンジニアリング技術が検討されている（例えば非特許文献１など参照）。
この種のトラヒックエンジニアリング技術では、ＭＰＬＳ（Multi-Protocol Label Switching）等の技術を用い、同一宛先に対する経路を複数設定し、各経路上を構成するリンクおよびノードを、それぞれのトラヒック状況に応じて動的に指定することで、動的にトラヒックをネットワーク内に分散配置させている。
【０００５】
従来、このような経路制御で用いられる最適経路選択方法では、Ｄｉｊｋｓｔｒａアルゴリズムを基本とし、経路上のリンクコストの最小値を保持し、その値が最も大きい経路を選択するＭＩＮ−ＭＡＸアルゴリズムがある。このアルゴリズムでは、リンクの評価値としてリンクの物理的帯域幅や負荷の逆数に代表されるリンクコストを用い、経路を構成する各リンクのリンクコストの最小値に基づき当該経路を評価するための最適化パラメータ値を算出し、その最適化パラメータ値が最大となる経路を選択することにより、多くのパケット通信のトラヒックを収容することの可能な経路を選択していた（例えば、特許文献１など参照）
【０００６】
なお、出願人は、本明細書に記載した先行技術文献情報で特定される先行技術文献以外には、本発明に関連する先行技術文献を出願時までに発見するには至らなかった。
【特許文献１】特開２００１−２４４９７４号公報
【非特許文献１】「次世代インターネットとトラヒック工学」、電子情報通信学会論文誌VOL.J85-B No.6、pp875-889、電子情報通信学会、2002年6月
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、このような従来技術では、任意のノードへの新たな経路を選択する際、すでに送信元ノードからの経路が選択確定されたノードの最適化パラメータ値を用いて、任意のノードの最適化パラメータ値を算出していたため、切断点で分離されるネットワークトポロジでは、その切断点以降は特定リンクにトラヒックが集中してしまい、通信品質の劣化やネットワーク利用効率の低下が発生する可能性が高く、バックボーンネットワークのサービス品質低下を招くという問題があった。
【０００８】
例えば、経路選択にＭＩＮ−ＭＡＸアルゴリズムを用いた場合、送信元ノードから任意のノードまでのリンクコストの最小値が最適化パラメータ値として保持され、その最適化パラメータ値を用いて次のノードへの経路が選択される。このため、複数の経路候補が切断点となる特定ノードを必ず通らなければならないようなトポロジで、かつ送信元ノードから特定ノードまでのコストの最小値が特定ノード以降の最小値より小さい場合、特定ノード以降はどの経路候補を選択してもリンクコストの最小値が変わらなくなってしまう。したがって、特定ノード以降については特定ノードまでのコスト最小値を持ついずれかの経路候補が常に選択されて、特定のリンクにトラヒックが集中してしまうことになる。
【０００９】
また、この問題は、複数の切断点で分離されるネットワークにおいて、切断点の影響が経路選択に複数回影響する。例えば、ＩＳＰ（Internet Service Provider）のバックボーン網における地域間接続など、エリア間がいくつかの少数のリンクで接続されているネットワークにおいて、エリア間をまたがるトラヒックを分散配置するための経路をＭＩＮ−ＭＡＸアルゴリズムを用いて選択する際に顕著に表れる。このため、全国にまたがるＩＳＰのバックボーン網において、地域間の経路を分散させることが難しいという現実的な問題があった。
【００１０】
本発明はこのような課題を解決するためのものであり、ネットワークトポロジの切断点に相当する特定ノード以降におけるトラヒック集中を回避でき、トラヒックエンジニアリング技術を用いた負荷分散効果を高めることができる経路制御装置および経路選択方法を提供することを目的としている。
【課題を解決するための手段】
【００１１】
このような目的を達成するために、本発明にかかる経路制御装置は、リンクを介して網状に接続された複数のノードからなるパケット通信ネットワークに設けられ、パケット通信を行う送信元ノードから次のノードへの経路を当該ネットワークから順次選択していくことにより、送信元ノードから所望の宛先ノードまでの経路を選択する経路制御装置であって、各リンクでのパケット転送状況を示すリンク情報を各ノードから収集するリンク情報収集部と、送信元ノードから任意のノードへの経路を選択する際、当該ノードへの経路をそれぞれ評価する最適化パラメータ値に基づき、ノードへの経路のいずれかを当該ノードへの経路として選択する経路選択部と、リンク情報収集部で収集されたリンク情報、経路が選択されていないノードの最適化パラメータ値、および経路選択部で選択されたノードへの経路とその経路を構成する各ノードの最適化パラメータ値を記憶する記憶部とを備え、経路選択部で、任意のノードｕの最適化パラメータ値を算出する際、記憶部から読み出した、すでに経路が選択されておりかつノードｕとリンクを介して隣接するノードｖの最適化パラメータ値と、ノードｖからノードｕへのリンクのリンク情報と、ノードｕの最適化パラメータ値とから、ノードｕの新たな最適化パラメータ値を算出し、経路選択部で選択された経路について、当該経路を構成する各ノードの最適化パラメータ値が基準ホップ数にわたるノード間で変化していない場合、記憶部に記憶されている、経路が選択されていないノードの最適化パラメータ値を、当該ノードに隣接する経路選択済みのノードとの間のリンクのリンク情報に基づき初期化している。
【００１２】
この際、経路選択部で、ノードｕの最適化パラメータ値を算出する際、ＭＩＮ−ＭＡＸアルゴリズムに基づいて、記憶部に記憶されているノードｖからノードｕへのリンクのリンク情報から得た当該リンクの評価を示すリンクコストと、記憶部に記憶されているノードｖの最適化パラメータ値とのいずれか最小値を選択し、この最小値と記憶部に記憶されているノードｕの最適化パラメータ値とのいずれか最大値をノードｕの新たな最適化パラメータ値として算出するようにしてもよい。
【００１３】
あるいは、経路選択部で、ノードｕの最適化パラメータ値を算出する際、ＭＩＮ−ＭＡＸアルゴリズムに基づいて、記憶部に記憶されているノードｖからノードｕへのリンクのリンク情報から得た当該リンクの評価を示すリンクコストと、記憶部に記憶されているノードｖの最適化パラメータ値とのいずれか最大値を選択し、この最大値と記憶部に記憶されているノードｕの最適化パラメータ値とのいずれか最小値をノードｕの新たな最適化パラメータ値として算出するようにしてもよい。
【００１４】
また、本発明にかかる経路選択方法は、リンクを介して網状に接続された複数のノードからなるパケット通信ネットワークに設けられた経路制御装置で、パケット通信を行う送信元ノードから次のノードを順次選択することにより、所望の宛先ノードまでの経路を選択する経路選択方法であって、各リンクでのパケット転送状況を示すリンク情報を各ノードから収集するリンク情報収集ステップと、送信元ノードから任意のノードへの経路を選択する際、当該ノードへの経路をそれぞれ評価する最適化パラメータ値に基づき、ノードへの経路のいずれかを当該ノードへの経路として選択する経路選択ステップと、リンク情報収集ステップで収集されたリンク情報、経路が選択されていないノードの最適化パラメータ値、および経路選択ステップで選択されたノードへの経路とその経路を構成する各ノードの最適化パラメータ値を記憶部で記憶する記憶ステップとを備え、経路選択ステップは、任意のノードｕの最適化パラメータ値を算出する際、記憶部から読み出した、すでに経路が選択されておりかつノードｕとリンクを介して隣接するノードｖの最適化パラメータ値と、ノードｖからノードｕへのリンクのリンク情報と、ノードｕの最適化パラメータ値とから、ノードｕの新たな最適化パラメータ値を算出するパラメータ算出ステップと、経路選択ステップで選択された経路について、当該経路を構成する各ノードの最適化パラメータ値が基準ホップ数にわたるノード間で変化していない場合、記憶部に記憶されている、経路が選択されていないノードの最適化パラメータ値を、当該ノードに隣接する経路選択済みのノードとの間のリンクのリンク情報に基づき初期化するパラメータ初期化ステップとを有している。
【００１５】
この際、パラメータ算出ステップで、ノードｕの最適化パラメータ値を算出する際、ＭＩＮ−ＭＡＸアルゴリズムに基づいて、記憶部に記憶されているノードｖからノードｕへのリンクのリンク情報から得た当該リンクの評価を示すリンクコストと、記憶部に記憶されているノードｖの最適化パラメータ値とのいずれか最小値を選択し、この最小値と記憶部に記憶されているノードｕの最適化パラメータ値とのいずれか最大値をノードｕの新たな最適化パラメータ値として算出するようにしてもよい。
【００１６】
あるいは、パラメータ算出ステップで、ノードｕの最適化パラメータ値を算出する際、ＭＩＮ−ＭＡＸアルゴリズムに基づいて、記憶部に記憶されているノードｖからノードｕへのリンクのリンク情報から得た当該リンクの評価を示すリンクコストと、記憶部に記憶されているノードｖの最適化パラメータ値とのいずれか最大値を選択し、この最大値と記憶部に記憶されているノードｕの最適化パラメータ値とのいずれか最小値をノードｕの新たな最適化パラメータ値として算出するようにしてもよい。
【発明の効果】
【００１７】
本発明によれば、任意のノードｕの最適化パラメータ値を算出する際、記憶部から読み出した、すでに経路が選択されておりかつノードｕとリンクを介して隣接するノードｖの最適化パラメータ値と、ノードｖからノードｕへのリンクのリンク情報と、ノードｕの最適化パラメータ値とから、ノードｕの新たな最適化パラメータ値が算出され、経路選択部で選択された経路について、当該経路を構成する各ノードの最適化パラメータ値が基準ホップ数にわたるノード間で変化していない場合、記憶部に記憶されている、経路が選択されていないノードの最適化パラメータ値が、当該ノードに隣接する経路選択済みのノードとの間のリンクのリンク情報に基づき初期化されるため、ネットワークトポロジの切断点に相当する特定ノード以降における経路選択に用いられる最適化パラメータ値の固定化を回避できる。
したがって、特定ノード以降におけるトラヒック集中を回避でき、トラヒックエンジニアリング技術を用いた負荷分散効果を高めることが可能となる。
【発明を実施するための最良の形態】
【００１８】
次に、本発明の実施の形態について図面を参照して説明する。
［ネットワークモデル］
まず、図１を参照して、本発明の一実施の形態にかかる経路制御装置が適用される通信ネットワークについて説明する。図１は、本発明の一実施の形態にかかる経路制御装置が適用される通信ネットワークのネットワークモデル例を示すブロック図である。
この通信ネットワークは、ユーザ収容装置３０，３６、中継装置３１〜３５、経路制御装置２０から構成され、各ユーザ端末１０，１１は、それぞれユーザネットワーク２０１，２０２にあるリンク１００，１０１を介して、ユーザ収容装置３０，３６に収容されている。
【００１９】
ユーザ収容装置３０，３６間は、リンク１０２〜１０９と中継装置３１〜３５によって接続されている。また経路制御装置２０は、管理ネットワーク３００を介して、ユーザ収容装置３０，３６および中継装置３１〜３５と接続されている。
以下では、ユーザ収容装置３０，３６、中継装置３１〜３５、およびユーザ収容装置３０，３６と中継装置３１〜３５との間を接続するリンク１０２〜１０９から構成されるバックボーンネットワークをコアネットワーク２００とする。また、ユーザ収容装置３０，３６、中継装置３１〜３５をコアネットワーク２００を構成するノードという。
【００２０】
［経路制御装置］
次に、図２を参照して、本発明の一実施の形態にかかる経路制御装置について説明する。図２は、本発明の一実施の形態にかかる経路制御装置の構成を示すブロック図である。
この経路制御装置２０は、全体としてコンピュータを有する情報処理装置からなり、リンク情報収集部２１、経路選択部２２、経路制御部２３、および記憶部２４が設けられている。このうちリンク情報収集部２１、経路選択部２２、および経路制御部２３は、ＣＰＵでプログラムを実行することによりハードウェアとプログラムとを協働させて機能部を実現させる演算処理部（図示せず）や、管理ネットワーク３００を介して制御用パケットを送受信する通信インターフェース部（図示せず）から構成されている。
【００２１】
リンク情報収集部２１は、上記演算処理部により実現される機能部からなり、上記通信インターフェース部から管理ネットワーク３００を経由して、ユーザ収容装置３０，３６および中継装置３１〜３５から各リンクでのパケット転送状況例えばトラヒック量を示すリンク情報を収集する機能と、収集したリンク情報から得たコスト値（例えばトラヒック量の逆数）に基づき記憶部２４に格納されているリンクコストテーブルを更新する機能を有している。
【００２２】
経路選択部２２は、上記演算処理部により実現される機能部からなり、パケット通信の送信元ノード（発側ノード）から宛先ノード（着側ノード）ヘの経路をＭＩＮ−ＭＡＸアルゴリズムで選択する機能と、経路選択結果である経路と経路上のノードの最適化パラメータ値とを記憶部２４の最適化パラメータテーブルに格納する機能と、最適化パラメータテーブルを検索して経路上の各ノードの最適化パラメータ値の変化状況を確認する機能と、基準ホップ数の間に最適化パラメータ値が変化していない場合、選択候補となる各ノードの最適化パラメータ値を、当該ノードに隣接する経路選択済みのノードとの間のリンクのリンク情報に基づき初期化して経路選択を継続する機能とを有している。
【００２３】
なお、本発明でいう最適化パラメータ値とは、パケット通信の送信元ノードから任意のノードｕへの経路を選択する際、その選択基準に用いられる値であり、当該ノードｕへの経路を評価する評価値である。例えば、ＭＩＮ−ＭＡＸアルゴリズムでは、任意のノードｕへの経路を選択する際、ノードｕへの各経路ごとに最適化パラメータ値を求め、最適化パラメータ値が最大の経路を選択する。このとき、ノードｕにリンクを介して隣接している、すでに経路選択済みのノードｖまでの経路については、例えば送信元ノードからノードｖまでの選択済み経路を構成するリンクのコストの最小値すなわちノードｕの最適化パラメータ値が用いられる。
【００２４】
経路制御部２３は、上記演算処理部により実現される機能部からなり、記憶部２４に格納された各経路から所望の経路を検索する機能と、検索された経路を上記通信インターフェース部から管理ネットワーク３００を経由して、ユーザ収容装置３０，３６および中継装置３１〜３５に設定する機能とを有している。
記憶部２４は、ハードディスクやメモリなどの記憶装置からなり、リンクコストテーブル２４Ａ、最適化パラメータテーブル２４Ｂ、およびＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃをデータベースで管理し、リンク情報収集部２１、経路選択部２２、経路制御部２３からのアクセスに応じて、管理している値を提供したり、変更して保存したりする機能を有している。
【００２５】
図３は、記憶部２４で管理されているリンクコストテーブル２４Ａの構成例であり、図４は、記憶部２４で管理されている最適化パラメータテーブル２４Ｂの構成例である。いずれの場合も、それぞれ経路選択開始前の値の例が示されている。
リンクコストテーブル２４Ａでは、ユーザ収容装置３０，３６および中継装置３１〜３５の間を接続するリンク１０２〜１０９ごとにそのリンクの評価値として、リンク情報収集部２１で収集されたリンク情報から得たリンクコストが管理される。最適化パラメータテーブル２４Ｂでは、ユーザ収容装置３０，３６および中継装置３１〜３５を宛先ノードとする経路およびその経路を構成する各ノードの最適化パラメータ値が管理されている。ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃは、ＭＩＮ−ＭＡＸアルゴリズムで用いる各種パラメータとして、例えば選択結果である経路や各ノードの最適化パラメータ値が管理されている。
【００２６】
本実施の形態では、経路制御装置２０の経路選択部２２で、任意のノードｕの最適化パラメータ値を算出する際、記憶部２４から読み出した、すでに経路が選択されておりかつノードｕとリンクを介して隣接するノードｖの最適化パラメータ値と、ノードｖからノードｕへのリンクのリンク情報と、ノードｕの最適化パラメータ値とから、ノードｕの新たな最適化パラメータ値を算出し、経路選択部２２で選択された経路について、当該経路を構成する各ノードの最適化パラメータ値が基準ホップ数にわたるノード間で変化していない場合、記憶部２４に記憶されている、経路が選択されていないノードの最適化パラメータ値を、当該ノードに隣接する経路選択済みのノードとの間のリンクのリンク情報に基づき初期化するようにしている。
【００２７】
これにより、送信元ノードから宛先ノードへの経路を選択中に、任意のノードへの経路を構成するノードの最適化パラメータ値の変化を確認し、最適化パラメータ値が基準ホップ数にわたって変動しなくなった場合に、最適化パラメータ値を初期化して経路選択を継続することが可能になる。
したがって、ネットワークトポロジの切断点に相当する特定ノードの通過を確率的に判断して、その特定ノード以降におけるトラヒック集中を回避でき、トラヒックエンジニアリング技術を用いた負荷分散効果を高めることが可能となる。
【００２８】
［経路制御装置の動作］
次に、図５を参照して、本発明の一実施の形態にかかる経路制御装置の動作について説明する。図５は、本発明の一実施の形態にかかる経路制御装置での経路選択処理を示すフローチャートである。
以下、前述した図１の通信ネットワークのうち、送信元ノードとなるユーザ収容装置３０から当該パケットの宛先ノードとなるユーザ収容装置３６への各経路のうちから、ＭＩＮ−ＭＡＸアルゴリズムに基づき最適経路を選択する場合を例として説明する。
【００２９】
まず、経路制御装置２０は、リンク情報収集部２１により、管理ネットワーク３００を介してユーザ収容装置３０，３６および中継装置３１〜３５から、各リンク１０２〜１０９のリンク情報を収集し、そのリンク情報から得た、例えばトラヒック量の逆数からなるリンクコストを記憶部２４のリンクコストテーブル２４Ａに格納する（ステップ５００）。この例では、初期状態におけるリンクコストテーブル２４Ａとして、前述した図３に示した内容のリンクコストがそれぞれ記憶されているものとする。
【００３０】
次に、経路制御装置２０は、ＭＩＮ−ＭＡＸアルゴリズム（例えば、特許文献１など参照）を用いて、送信元ノードから任意のノードへの経路を当該ネットワークから順次選択していくことにより、送信元ノードから所望の宛先ノードまでの経路を選択する。この際、送信元ノードから任意のノードへの経路として、当該ノードへの経路のうち、それぞれの経路を構成する各リンクのコストの最小値が最大となる経路が選択される。
図６は、この際に用いるＭＩＮ−ＭＡＸアルゴリズムに関する定義および表記を示す説明図である。なお、この表記において、装置とはユーザ収容装置または中継装置を意味する。
【００３１】
ＭＩＮ−ＭＡＸアルゴリズムの処理開始時において、各パラメータは初期化される。図７に、初期状態におけるＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃの記憶内容を示す。図８に、初期状態における最適化パラメータテーブル２４Ｂの記憶内容を示す。
この際、図７におけるＭＩＮ−ＭＡＸアルゴリズムパラメータの値は、図６の定義に示されたパラメータの値と同じである。このうち、集合Ｖは経路選択対象となる全装置の集合である。また、集合Ｕは経路が確定した装置の集合であり、初期状態においてΦ（空集合）である。したがって集合Ｖ−Ｕは、経路未確定すなわち経路選択候補である装置の集合となる。経路は、経路選択処理により確定した任意の装置への経路であり、Ｃは各装置への最適化パラメータ値である。なお、図５の経路選択動作において、最適化パラメータ値の初期化要否を判断するための基準ホップ数は「３」とする。
【００３２】
［ＭＩＮ−ＭＡＸアルゴリズムの１ステップ目］
まず、経路制御装置２０は、ＭＩＮ−ＭＡＸアルゴリズムを用いて、１ステップ目の経路選択処理を行う。図７のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃにおいて、集合Ｖ−Ｕに含まれる装置のうち、ユーザ収容装置３０の持つコストＣ（３０）＝「∞（無限大）」が最大であるため、ユーザ収容装置３０が集合Ｕに含められる。これにより、送信元ノードであるユーザ収容装置３０から経路選択対象ノードの１つであるユーザ収容装置３０への経路として「３０→３０」が求まる（ステップ５０１）。この時点で、リンクのコストの最小値が最大である経路は、ユーザ収容装置３０からユーザ収容装置３０に至る経路であるが、リンクが含まれないので実質的にはまだ求まっていない。
【００３３】
続いて、集合Ｖ−Ｕに含まれている装置のうち、集合Ｕに含まれる任意の装置ここではユーザ収容装置３０とリンクを介して隣接する装置のコストすなわち最適化パラメータ値を、ＭＩＮ−ＭＡＸアルゴリズムに基づき、当該装置に至る経路上にあるリンクのコストの最小値に更新する。この場合、ユーザ収容装置３０に隣接する中継装置３１のコストＣ（３１）は、図３のリンクコストテーブル２４Ａのリンク１０２より「３」となる。また、ユーザ収容装置３０に隣接する中継装置３２のコストＣ（３２）は、同じくリンク１０３より「４」となる（ステップ５０１）。
【００３４】
このようにして、ＭＩＮ−ＭＡＸアルゴリズムで１ステップ分だけ経路選択処理を行った後、その選択結果として得られた経路を、当該時点での各装置の最適化パラメータ値とともに記憶部２４の最適化パラメータテーブル２４Ｂへ記憶する（ステップ５０２）。この時点における、ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃおよび最適化パラメータテーブル２４Ｂは、それぞれ図９および図１０の値を取る。
【００３５】
続いて、図９の最適化パラメータテーブル２４Ｂを検索し、上記で決定した経路について、最適化パラメータ値が基準ホップ数にわたり変化していない箇所があるか調べる（ステップ５０３）。この最適化パラメータテーブル２４Ｂでは、ユーザ収容装置３０への経路において、最適化パラメータ値が変化していない箇所は「３０（∞）→３０（∞）」の最大０ホップ分であり基準ホップ数「３」より小さいことから（ステップ５０３：ＮＯ）、ステップ５０５へ移行する。ここで、目的の宛先ノードであるユーザ収容装置３６への経路がまだ選択されていないため（ステップ５０５：ＮＯ）、ステップ５０１へ戻る。
【００３６】
［ＭＩＮ−ＭＡＸアルゴリズムの２ステップ目］
次に、経路制御装置２０は、ＭＩＮ−ＭＡＸアルゴリズムを用いて、２ステップ目の経路選択処理を行う。まず、図９のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃにおいて、集合Ｖ−Ｕに含まれる装置のうち、中継装置３２の持つコストＣ（３２）＝「４」が最大であるため、中継装置３２が集合Ｕに含められる。これにより、ユーザ収容装置３０から中継装置３２に至る経路として「３０→３２」が求まる（ステップ５０１）。
【００３７】
続いて、集合Ｖ−Ｕに含まれている装置のうち、集合Ｕに含まれる任意の装置ここでは中継装置３２とリンクを介して隣接する装置のコストすなわち最適化パラメータ値を、ＭＩＮ−ＭＡＸアルゴリズムに基づき、当該装置に至る経路上にあるリンクのコストの最小値に更新する。この場合、中継装置３２に隣接する中継装置３３のコストＣ（３３）は、図３のリンクコストテーブル２４Ａから、中継装置３２と中継装置３３を接続するリンク１０５のコスト「５」と、中継装置３２までの経路上のリンクコスト「４」とのうち、その最小値「４」が選択される。この際、ユーザ収容装置３０から中継装置３３に至る経路は他に見つかっておらず、中継装置３２を経由する経路の最小値が最大となり、この値が中継装置３３のコストＣ（３３）すなわち最適化パラメータ値となる（ステップ５０１）。
【００３８】
このようにして、ＭＩＮ−ＭＡＸアルゴリズムで１ステップ分だけ経路選択処理を行った後、その選択結果として得られた経路を、当該時点での各装置の最適化パラメータ値とともに記憶部２４の最適化パラメータテーブル２４Ｂへ記憶する（ステップ５０２）。この時点における、ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃおよび最適化パラメータテーブル２４Ｂは、それぞれ図１１および図１２の値を取る。
【００３９】
続いて、図１１の最適化パラメータテーブル２４Ｂを検索し、上記で決定した経路について、最適化パラメータ値が基準ホップ数にわたり変化していない箇所があるか調べる（ステップ５０３）。この最適化パラメータテーブル２４Ｂでは、中継装置３２への経路において、最適化パラメータ値が変化していない箇所は「３０（∞）→３２（４）」の最大１ホップ分であり基準ホップ数「３」より小さいことから（ステップ５０３：ＮＯ）、ステップ５０５へ移行する。ここで、目的の宛先ノードであるユーザ収容装置３６への経路がまだ選択されていないため（ステップ５０５：ＮＯ）、ステップ５０１へ戻る。
【００４０】
［ＭＩＮ−ＭＡＸアルゴリズムの３ステップ目］
次に、経路制御装置２０は、ＭＩＮ−ＭＡＸアルゴリズムを用いて、３ステップ目の経路選択処理を行う。まず、図１１のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃにおいて、集合Ｖ−Ｕに含まれる装置のうち、中継装置３３の持つコストＣ（３３）＝「４」が最大であるため、中継装置３３が集合Ｕに含められる。これにより、ユーザ収容装置３０から中継装置３３に至る経路として「３０→３２→３３」が求まる（ステップ５０１）。
【００４１】
続いて、集合Ｖ−Ｕに含まれている装置のうち、集合Ｕに含まれる任意の装置ここでは中継装置３３とリンクを介して隣接する装置のコストすなわち最適化パラメータ値を、ＭＩＮ−ＭＡＸアルゴリズムに基づき、当該装置に至る経路上にあるリンクのコストの最小値に更新する。この場合、中継装置３３に隣接する中継装置３１のコストＣ（３１）は、図３のリンクコストテーブル２４Ａからのリンク１０４のコスト「７」と、中継装置３３までの経路上のリンクコスト「４」とのうち、その最小値「４」が選択される。
【００４２】
この際、ユーザ収容装置３０から中継装置３１に至る経路としてリンク１０２が存在するが、図３のリンクコストテーブル２４Ａからリンク１０２のコストは「３」であり、中継装置３２が選択された時点でリンク１０２の経路は却下されている。したがって、最大値「４」である上記中継装置３２，３３経由の経路が選択される（ステップ５０１）。
同様にして、中継装置３３に隣接する中継装置３４，３５のコストＣ（３４），Ｃ（３５）が算出される。これらの場合も、前述と同様に、上記中継装置３２，３３経由の経路が選択され、いずれのコストも「４」となる（ステップ５０１）。
【００４３】
このようにして、ＭＩＮ−ＭＡＸアルゴリズムで１ステップ分だけ経路選択処理を行った後、その選択結果として得られた経路を、当該時点での各装置の最適化パラメータ値とともに記憶部２４の最適化パラメータテーブル２４Ｂへ記憶する（ステップ５０２）。この時点における、ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃおよび最適化パラメータテーブル２４Ｂは、それぞれ図１３および図１４の値を取る。
【００４４】
続いて、図１３の最適化パラメータテーブル２４Ｂを検索し、上記で決定した経路について、最適化パラメータ値が基準ホップ数にわたり変化していない箇所があるか調べる（ステップ５０３）。この最適化パラメータテーブル２４Ｂでは、中継装置３３への経路において、最適化パラメータ値が変化していない箇所は「３０（∞）→３２（４）→３３（４）」の最大２ホップ分であり基準ホップ数「３」より小さいことから（ステップ５０３：ＮＯ）、ステップ５０５へ移行する。ここで、目的の宛先ノードであるユーザ収容装置３６への経路がまだ選択されていないため（ステップ５０５：ＮＯ）、ステップ５０１へ戻る。
【００４５】
［ＭＩＮ−ＭＡＸアルゴリズムの４ステップ目］
次に、経路制御装置２０は、ＭＩＮ−ＭＡＸアルゴリズムを用いて、４ステップ目の経路選択処理を行う。まず、図１３のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃにおいて、集合Ｖ−Ｕに含まれる装置として、同一の最大コスト「４」を持つ中継装置３１，３４，３５が存在する。このようにコストが同じ場合、各ノードの識別子の順序になどの次の基準に基づき任意のノードが選択される。この例では、中継装置３１、３４、３５のうち中継装置３１が選択されて中継装置３１が集合Ｕに含められる。これにより、ユーザ収容装置３０から中継装置３１に至る経路として「３０→３２→３３→３１」が求まる（ステップ５０１）。
【００４６】
続いて、集合Ｖ−Ｕに含まれている装置のうち、集合Ｕに含まれる任意の装置ここでは中継装置３２とリンクを介して隣接する装置のコストすなわち最適化パラメータ値を、ＭＩＮ−ＭＡＸアルゴリズムに基づき、当該装置に至る経路上にあるリンクのコストの最小値に更新する。この場合、当該経路上の中継装置３１に隣接する装置すなわちユーザ収容装置３０および中継装置３３への経路はすべて確定しているため、最適化パラメータ値は変更されない（ステップ５０１）。
【００４７】
このようにして、ＭＩＮ−ＭＡＸアルゴリズムで１ステップ分だけ経路選択処理を行った後、その選択結果として得られた経路を、当該時点での各装置の最適化パラメータ値とともに記憶部２４の最適化パラメータテーブル２４Ｂへ記憶する（ステップ５０２）。この時点における、ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃおよび最適化パラメータテーブル２４Ｂは、それぞれ図１５および図１６の値を取る。
【００４８】
続いて、図１５の最適化パラメータテーブル２４Ｂを検索し、上記で決定した経路について、最適化パラメータ値が基準ホップ数にわたり変化していない箇所があるか調べる（ステップ５０３）。この最適化パラメータテーブル２４Ｂでは、中継装置３１への経路において、最適化パラメータ値が変化していない箇所は「３０（∞）→３２（４）→３３（４）→３１（４）」の最大３ホップ分であり基準ホップ数「３」以上である（ステップ５０３：ＮＯ）。
【００４９】
［最適化パラメータ値の初期化］
したがって、この場合は、図１５のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃのうち、集合Ｖに含まれる経路未選択（未確定）のノード、ここでは中継装置３４，３５およびユーザ収容装置３６のコストＣ（３４），Ｃ（３５），Ｃ（３６）すなわち最適化パラメータ値を、それぞれのノードに隣接する経路選択済みのノードへのリンクのリンクコストで初期化する（ステップ５０４）。
例えば、中継装置３４は、経路選択済みの中継装置３３とリンク１０６を介して隣接しているため、中継装置３４のコストＣ（３４）すなわち最適化パラメータ値が、リンク１０６のリンクコスト「６」で初期化される。同様にして、中継装置３５のコストＣ（３５）は、リンク１０７のリンクコスト「７」で初期化される。
【００５０】
また、ユーザ収容装置３６については経路選択済みのノードと接続されておらず、現状のままかゼロに初期化される。この際、経路未選択のすべてのノードについて初期化してもよく、少なくとも過去に最適化パラメータ値を算出したノードすなわち中継装置３４，３５についてのみ初期化してもよい。
この時点における、ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃおよび最適化パラメータテーブル２４Ｂは、それぞれ図１７および図１８の値を取る。そして、目的の宛先ノードであるユーザ収容装置３６への経路がまだ選択されていないため（ステップ５０５：ＮＯ）、ステップ５０１へ戻る。
【００５１】
［ＭＩＮ−ＭＡＸアルゴリズムの５ステップ目］
次に、経路制御装置２０は、ＭＩＮ−ＭＡＸアルゴリズムを用いて、５ステップ目の経路選択処理を行う。まず、図１７のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃにおいて、集合Ｖ−Ｕに含まれる装置のうち、中継装置３５の持つコスト（３５）＝「７」が最大であるため、中継装置３５が集合Ｕに含められる。これにより、ユーザ収容装置３０から中継装置３５に至る経路として「３０→３２→３３→３５」が求まる（ステップ５０１）。
【００５２】
続いて、集合Ｖ−Ｕに含まれている装置のうち、集合Ｕに含まれる任意の装置ここでは中継装置３５とリンクを介して隣接する装置のコストすなわち最適化パラメータ値を、ＭＩＮ−ＭＡＸアルゴリズムに基づき、当該装置に至る経路上にあるリンクのコストの最小値に更新する。この場合、中継装置３５に隣接するユーザ収容装置３６のコストＣ（３６）は、図３のリンクコストテーブル２４Ａから、中継装置３５とユーザ収容装置３６を接続するリンク１０９のコスト「８」と、中継装置３５までの経路上のリンクコスト「７」とのうち、その最小値「７」が選択される。この際、ユーザ収容装置３０から中継装置３２に至る経路は他に見つかっておらず、中継装置３５を経由する経路の最小値が最大となり、この値がユーザ収容装置３６のコストＣ（３６）すなわち最適化パラメータ値となる（ステップ５０１）。
【００５３】
このようにして、ＭＩＮ−ＭＡＸアルゴリズムで１ステップ分だけ経路選択処理を行った後、その選択結果として得られた経路を、当該時点での各装置の最適化パラメータ値とともに記憶部２４の最適化パラメータテーブル２４Ｂへ記憶する（ステップ５０２）。この時点における、ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃおよび最適化パラメータテーブル２４Ｂは、それぞれ図１９および図２０の値を取る。
【００５４】
続いて、図１９の最適化パラメータテーブル２４Ｂを検索し、上記で決定した経路について、最適化パラメータ値が基準ホップ数にわたり変化していない箇所があるか調べる（ステップ５０３）。この最適化パラメータテーブル２４Ｂでは、中継装置３５への経路において、最適化パラメータ値が変化していない箇所は「３０（∞）→３２（４）→３３（４）→３５（７）」の最大２ホップ分であり基準ホップ数「３」より小さいことから（ステップ５０３：ＮＯ）、ステップ５０５へ移行する。ここで、目的の宛先ノードであるユーザ収容装置３６への経路がまだ選択されていないため（ステップ５０５：ＮＯ）、ステップ５０１へ戻る。
【００５５】
［ＭＩＮ−ＭＡＸアルゴリズムの６ステップ目］
次に、経路制御装置２０は、ＭＩＮ−ＭＡＸアルゴリズムを用いて、６ステップ目の経路選択処理を行う。まず、図１９のＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃにおいて、集合Ｖに含まれる装置のうち、ユーザ収容装置３６の持つコストＣ（３６）が最大であるため、ユーザ収容装置３６が集合Ｕに含められる。これにより、送信元ノードであるユーザ収容装置３０から所望の宛先ノードであるユーザ収容装置３６への経路として「３０→３２→３３→３５→３６」が求まる（ステップ５０１）。
【００５６】
続いて、集合Ｖ−Ｕに含まれている装置のうち、集合Ｕに含まれる任意の装置ここではユーザ収容装置３６とリンクを介して隣接する装置のコストすなわち最適化パラメータ値を、ＭＩＮ−ＭＡＸアルゴリズムに基づき、当該装置に至る経路上にあるリンクのコストの最小値に更新する。この場合、ユーザ収容装置３６に隣接する中継装置３４のコストＣ（３４）は、図３のリンクコストテーブル２４Ａから、ユーザ収容装置３６と中継装置３４を接続するリンク１０８のコスト「７」と、ユーザ収容装置３６までの経路上のリンクコスト「７」とのうち、その最小値「７」が選択される。ここで、すでに見つかっているユーザ収容装置３６への経路でのコスト「６」と比較され、ユーザ収容装置３６を経由する経路側の最大値「７」が中継装置３３のコストＣ（３３）すなわち最適化パラメータ値となる（ステップ５０１）。
【００５７】
このようにして、ＭＩＮ−ＭＡＸアルゴリズムで１ステップ分だけ経路選択処理を行った後、その選択結果として得られた経路を、当該時点での各装置の最適化パラメータ値とともに記憶部２４の最適化パラメータテーブル２４Ｂへ記憶する（ステップ５０２）。この時点における、ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル２４Ｃおよび最適化パラメータテーブル２４Ｂは、それぞれ図２１および図２２の値を取る。
【００５８】
続いて、図２１の最適化パラメータテーブル２４Ｂを検索し、上記で決定した経路について、最適化パラメータ値が基準ホップ数にわたり変化していない箇所があるか調べる（ステップ５０３）。この最適化パラメータテーブル２４Ｂでは、ユーザ収容装置３６への経路において、最適化パラメータ値が変化していない箇所は「３０（∞）→３２（４）→３３（４）→３５（７）→３６（７）」の最大２ホップ分であり基準ホップ数「３」より小さいことから（ステップ５０３：ＮＯ）、ステップ５０５へ移行する。ここで、目的の宛先ノードであるユーザ収容装置３６への経路が選択されていることから（ステップ５０５：ＹＥＳ）、一連の経路選択処理を終了する。
【００５９】
このように、本実施の形態では、経路制御装置２０の経路選択部２２で、任意のノードｕの最適化パラメータ値を算出する際、記憶部２４から読み出した、すでに経路が選択されておりかつノードｕとリンクを介して隣接するノードｖの最適化パラメータ値と、ノードｖからノードｕへのリンクのリンク情報と、ノードｕの最適化パラメータ値とから、ノードｕの新たな最適化パラメータ値が算出され、経路選択部２２で選択された経路について、当該経路を構成する各ノードの最適化パラメータ値が基準ホップ数にわたるノード間で変化していない場合、記憶部２４に記憶されている、経路が選択されていないノードの最適化パラメータ値が、当該ノードに隣接する経路選択済みのノードとの間のリンクのリンク情報に基づき初期化される。
【００６０】
これにより、送信元ノードから宛先ノードへの経路を選択中に、任意のノードへの経路を構成するノードの最適化パラメータ値の変化を確認し、最適化パラメータ値が基準ホップ数にわたって変動しなくなった場合に、最適化パラメータ値を初期化して経路選択を継続することができる。
したがって、ネットワークトポロジの切断点に相当する特定ノードの通過を確率的に判断して、その特定ノード以降におけるトラヒック集中を回避でき、トラヒックエンジニアリング技術を用いた負荷分散効果を高めることが可能となる。
【００６１】
仮に、本実施の形態にかかる経路選択処理を適用しない従来のＭＩＮ−ＭＡＸアルゴリズムの場合、前述したＭＩＮ−ＭＡＸアルゴリズムの４ステップ目の時点で、経路選択の対象となるノードここでは中継装置３４，３５の最適化パラメータ値Ｃ（３４），Ｃ（３５）が初期化されないため、これら最適化パラメータ値はいずれも中継装置３３以前の経路でのリンク最小値「４」になる。したがって、この例では、最適化パラメータ値の次の選択基準、例えばノード識別子の値に基づきいずれかの中継装置を選択してしまい、中継装置３３から中継装置３４への経路を確定してしまう。
【００６２】
このように、従来のＭＩＮ−ＭＡＸアルゴリズムでは、中継装置の識別子の値という、経路を構成する各リンクのトラヒック量などの適正な評価値に関係しない基準に基づいて、中継装置３３以降の経路が確定してしまうため、特定のノード、リンクへトラヒックが集中してしまう問題がある。
本実施の形態を適用すれば、このような問題を解決して、適正な評価値に基づき最適な経路を選択することができ、トラヒックの集中を回避することが可能となる。
【００６３】
なお、以上では、経路選択用アルゴリズムとしてＭＩＮ−ＭＡＸアルゴリズムを用いた場合を例として説明したが、これに限定されるものではなく、経路を評価する最適化パラメータ値を用いて次のノードを順次選択するアルゴリズムであれば、前述と同様にして本発明を適用でき、前述と同様の作用効果が得られる。
【００６４】
また、以上では、ＭＩＮ−ＭＡＸアルゴリズムとして、図６に示したように、任意の経路を構成するリンクのうちリンクコストの最小値を当該経路の最適化パラメータ値とし、各経路のうち最適化パラメータ値が最大となる経路を最適経路として選択する場合について説明したがこれに限定されるものではない。判断基準の大小を逆転させて、任意の経路を構成するリンクのうちリンクコストの最大値を当該経路の最適化パラメータ値とし、各経路のうち最適化パラメータ値が最小となる経路を最適経路として選択するＭＩＮ−ＭＡＸアルゴリズムを用いる場合でも、前述と同様にして本発明を適用でき、前述と同様の作用効果が得られる。
【図面の簡単な説明】
【００６５】
【図１】本発明の一実施の形態にかかる経路制御装置が適用される通信ネットワークののネットワークモデル例を示すブロック図である。
【図２】本発明の一実施の形態にかかる経路制御装置の構成を示すブロック図である。
【図３】リンクコストテーブルの構成例である。
【図４】最適化パラメータテーブルの構成例である。
【図５】本発明の一実施の形態にかかる経路制御装置での経路選択処理を示すフローチャートである。
【図６】ＭＩＮ−ＭＡＸアルゴリズムに関する定義および表記を示す説明図である。
【図７】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（初期状態）である。
【図８】最適化パラメータテーブルの記憶内容例（初期状態）である。
【図９】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（１ステップ目終了時）である。
【図１０】最適化パラメータテーブルの記憶内容例（１ステップ目終了時）である。
【図１１】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（２ステップ目終了時）である。
【図１２】最適化パラメータテーブルの記憶内容例（２ステップ目終了時）である。
【図１３】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（３ステップ目終了時）である。
【図１４】最適化パラメータテーブルの記憶内容例（３ステップ目終了時）である。
【図１５】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（４ステップ目終了時）である。
【図１６】最適化パラメータテーブルの記憶内容例（４ステップ目終了時）である。
【図１７】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（４ステップ目：初期化後）である。
【図１８】最適化パラメータテーブルの記憶内容例（４ステップ目：初期化後）である。
【図１９】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（５ステップ目終了時）である。
【図２０】最適化パラメータテーブルの記憶内容例（５ステップ目終了時）である。
【図２１】ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブルの記憶内容例（６ステップ目終了時）である。
【図２２】最適化パラメータテーブルの記憶内容例（６ステップ目終了時）である。
【符号の説明】
【００６６】
１０，１１…ユーザ端末、２０…経路制御装置、２１…リンク情報収集部、２２…経路選択部、２３…経路制御部、２４…記憶部、２４Ａ…リンクコストテーブル、２４Ｂ…最適化パラメータテーブル、２４Ｃ…ＭＩＮ−ＭＡＸアルゴリズムパラメータテーブル、３０，３６…ユーザ収容装置（ノード）、３１〜３５…中継装置（ノード）、１００〜１０９…リンク、２００…コアネットワーク、２０１，２０２…ユーザネットワーク、３００…管理ネットワーク。
【図１】
2006074125.tif 000003
【図２】
2006074125.tif 000004
【図３】
2006074125.tif 000005
【図４】
2006074125.tif 000006
【図５】
2006074125.tif 000007
【図６】
2006074125.tif 000008
【図７】
2006074125.tif 000009
【図８】
2006074125.tif 000010
【図９】
2006074125.tif 000011
【図１０】
2006074125.tif 000012
【図１１】
2006074125.tif 000013
【図１２】
2006074125.tif 000014
【図１３】
2006074125.tif 000015
【図１４】
2006074125.tif 000016
【図１５】
2006074125.tif 000017
【図１６】
2006074125.tif 000018
【図１７】
2006074125.tif 000019
【図１８】
2006074125.tif 000020
【図１９】
2006074125.tif 000021
【図２０】
2006074125.tif 000022
【図２１】
2006074125.tif 000023
【図２２】
2006074125.tif 000024