(57)【要約】  まず、ネットワークを構成するノードおよびリンクを座標空間上に固定し、ノードに対して仮想負荷を与える。次に、パスを、パスの送信ノードと受信ノードとを結ぶ線で表して座標空間上に配置し、パスに対して仮想負荷を与える。次に、パスを表す線上の１以上の代表点について、代表点と各ノードとの間に働く引力および斥力の合力から移動ベクトルを計算する。その後、移動ベクトルに応じてパスを表す線上の代表点を座標空間内で移動させることでパスの経路を求める。
2011077897.tif 000002
【特許請求の範囲】
【請求項１】
ノード間がリンクにより接続されたネットワーク上のパスを計算する経路計算装置による経路計算方法であって、
ネットワークを構成するノードおよびリンクを座標空間上に固定し、該ノードに対して仮想負荷を与え、
パスを、該パスの送信ノードと受信ノードとを結ぶ線で表して座標空間上に配置し、該パスに対して仮想負荷を与え、
パスを表す線上の１以上の代表点について、該代表点と各ノードとの間に働く引力および斥力の合力から移動ベクトルを計算し、
前記移動ベクトルに応じてパスを表す線上の代表点を座標空間内で移動させることでパスの経路を求めることを特徴とする経路計算方法。
【請求項２】
請求項１に記載の経路計算方法であって、
座標空間上に固定したリンクに対して仮想負荷を与え、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点と各リンクを表す線分上の１以上の代表点との間に働く引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算方法。
【請求項３】
請求項２に記載の経路計算方法であって、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点と他のパスとの間に働く引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算方法。
【請求項４】
請求項３に記載の経路計算方法であって、
パスを表す線に対して該線の長さに関して単調増加する張力を与え、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点に働く張力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算方法。
【請求項５】
請求項３または４に記載の経路計算方法であって、
前記仮想負荷を、量と属性との組み合わせで表し、２つの仮想負荷の間に働く力の向き（引力、斥力、中性）が両仮想負荷の属性の組み合わせで決定され、２つの仮想負荷の間に働く力の大きさが両仮想負荷の量の積に関して単調増加し、両仮想負荷の間の距離に関して単調減少するように定義することを特徴とする経路計算方法。
【請求項６】
請求項５に記載の経路計算方法であって、
前記パスの経路を求めるに際し、前記移動ベクトルに応じてパスを表す線上の代表点を座標空間内で移動させ、該パスを表す線をノードおよびリンクと密着させることでパスの経路を求めることを特徴とする経路計算方法。
【請求項７】
請求項５または６に記載の経路計算方法であって、
複数のパスに対して、仮想負荷の属性の組み合わせが引力もしくは中性となるように仮想負荷を与えるか、または、仮想負荷の属性の組み合わせが斥力もしくは中性となるように仮想負荷を与えることを特徴とする経路計算方法。
【請求項８】
請求項５から７のいずれか１項に記載の経路計算方法であって、
各パスを表す線の初期位置を、該パスの送信ノードと受信ノードとの間の最短経路とすることを特徴とする経路計算方法。
【請求項９】
請求項５から８のいずれか１項に記載の経路計算方法であって、
各ノードおよび各リンクに仮想負荷を与えるに際して、該仮想負荷の量を、該ノードおよびリンクの物理容量または空き容量に比例する量とすることを特徴とする経路計算方法。
【請求項１０】
請求項９に記載の経路計算方法であって、
パスの経路計算完了後、ノードおよびリンクに線が密着したパスに要求されるトラヒック量が、該ノードおよびリンクの空き容量以下の場合、該ノードおよびリンクの現在の物理容量から、パスに要求されるトラヒック量を減じたものを、該ノードおよびリンクの新たな空き容量とすることを特徴とする経路計算方法。
【請求項１１】
請求項９に記載の経路計算方法であって、
パスの経路計算途中もしくは完了後、ノードおよびリンクに線が密着したパスに要求されるトラヒック量が、該ノードおよびリンクの空き容量よりも大きい場合、該ノードおよびリンクの現在の物理容量に、該パスに要求されるトラヒック量を収容できる物理容量を追加したものを、該ノードおよびリンクの新たな物理容量とすることを特徴とする経路計算方法。
【請求項１２】
請求項９から１１のいずれか１項に記載の経路計算方法であって、
パスを配置した後、該パスと、該パスに要求されるトラヒック量以下の空き容量をもつノードもしくはリンクと、の仮想負荷の属性の組み合わせが斥力あるいは中性になるように、該ノードもしくはリンクの仮想負荷の属性を変更するか、または、該組み合わせと力の向きとの関係性を変更することを特徴とする経路計算方法。
【請求項１３】
請求項９から１１のいずれか１項に記載の経路計算方法であって、
パスを配置した後、該パスと、該パスに要求されるトラヒック量よりも大きな空き容量をもつノードもしくはリンクと、の仮想負荷の属性の組み合わせが引力あるいは中性になるように、該ノードもしくはリンクの仮想負荷の属性を変更するか、または、該組み合わせと力の向きとの関係性を変更することを特徴とする経路計算方法。
【請求項１４】
請求項５から１３のいずれか１項に記載の経路計算方法であって、
パスの経路計算過程においてパスの一部を固定することを特徴とする経路計算方法。
【請求項１５】
請求項５から１４のいずれか１項に記載の経路計算方法であって、
ネットワークおよびパスとは無関係な仮想負荷をもつ負荷点または負荷領域を座標空間上に固定し、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点と負荷点または負荷領域との間に働く引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算方法。
【請求項１６】
ノード間がリンクにより接続されたネットワーク上のパスを計算する経路計算部を有してなる経路計算装置であって、
前記経路計算部は、
ネットワークを構成するノードおよびリンクを座標空間上に固定し、該ノードに対して仮想負荷を与え、
パスを、該パスの送信ノードと受信ノードとを結ぶ線で表して座標空間上に配置し、該パスに対して仮想負荷を与え、
パスを表す線上の１以上の代表点について、該代表点と各ノードとの間に働く引力および斥力の合力から移動ベクトルを計算し、
前記移動ベクトルに応じてパスを表す線上の代表点を座標空間内で移動させることでパスの経路を求めることを特徴とする経路計算装置。
【請求項１７】
請求項１６に記載の経路計算装置であって、
前記経路計算部は、
座標空間上に固定したリンクに対して仮想負荷を与え、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点と各リンクを表す線分上の１以上の代表点との間に働く引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算装置。
【請求項１８】
請求項１７に記載の経路計算装置であって、
前記経路計算部は、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点と他のパスとの間に働く引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算装置。
【請求項１９】
請求項１８に記載の経路計算装置であって、
前記経路計算部は、
パスを表す線に対して該線の長さに関して単調増加する張力を与え、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点に働く張力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算装置。
【請求項２０】
請求項１８または１９に記載の経路計算装置であって、
前記仮想負荷を、量と属性との組み合わせで表し、２つの仮想負荷の間に働く力の向き（引力、斥力、中性）が両仮想負荷の属性の組み合わせで決定され、２つの仮想負荷の間に働く力の大きさが両仮想負荷の量の積に関して単調増加し、両仮想負荷の間の距離に関して単調減少するように定義することを特徴とする経路計算装置。
【請求項２１】
請求項２０に記載の経路計算装置であって、
前記経路計算部は、
前記パスの経路を求めるに際し、前記移動ベクトルに応じてパスを表す線上の代表点を座標空間内で移動させ、該パスを表す線をノードおよびリンクと密着させることでパスの経路を求めることを特徴とする経路計算装置。
【請求項２２】
請求項２０または２１に記載の経路計算装置であって、
前記経路計算部は、
複数のパスに対して、仮想負荷の属性の組み合わせが引力もしくは中性となるように仮想負荷を与えるか、または、仮想負荷の属性の組み合わせが斥力もしくは中性となるように仮想負荷を与えることを特徴とする経路計算装置。
【請求項２３】
請求項２０から２２のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
各パスを表す線の初期位置を、該パスの送信ノードと受信ノードとの間の最短経路とすることを特徴とする経路計算装置。
【請求項２４】
請求項２０から２３のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
各ノードおよび各リンクに仮想負荷を与えるに際して、該仮想負荷の量を、該ノードおよびリンクの物理容量または空き容量に比例する量とすることを特徴とする経路計算装置。
【請求項２５】
請求項２４に記載の経路計算装置であって、
前記経路計算部は、
パスの経路計算完了後、ノードおよびリンクに線が密着したパスに要求されるトラヒック量が、該ノードおよびリンクの空き容量以下の場合、該ノードおよびリンクの現在の物理容量から、パスに要求されるトラヒック量を減じたものを、該ノードおよびリンクの新たな空き容量とすることを特徴とする経路計算装置。
【請求項２６】
請求項２４に記載の経路計算装置であって、
前記経路計算部は、
パスの経路計算途中もしくは完了後、ノードおよびリンクに線が密着したパスに要求されるトラヒック量が、該ノードおよびリンクの空き容量よりも大きい場合、該ノードおよびリンクの現在の物理容量に、該パスに要求されるトラヒック量を収容できる物理容量を追加したものを、該ノードおよびリンクの新たな物理容量とすることを特徴とする経路計算装置。
【請求項２７】
請求項２４から２６のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
パスを配置した後、該パスと、該パスに要求されるトラヒック量以下の空き容量をもつノードもしくはリンクと、の仮想負荷の属性の組み合わせが斥力あるいは中性になるように、該ノードもしくはリンクの仮想負荷の属性を変更するか、または、該組み合わせと力の向きとの関係性を変更することを特徴とする経路計算装置。
【請求項２８】
請求項２４から２６のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
パスを配置した後、該パスと、該パスに要求されるトラヒック量よりも大きな空き容量をもつノードもしくはリンクと、の仮想負荷の属性の組み合わせが引力あるいは中性になるように、該ノードもしくはリンクの仮想負荷の属性を変更するか、または、該組み合わせと力の向きとの関係性を変更することを特徴とする経路計算装置。
【請求項２９】
請求項２０から２８のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
パスの経路計算過程においてパスの一部を固定することを特徴とする経路計算装置。
【請求項３０】
請求項２０から２９のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
ネットワークおよびパスとは無関係な仮想負荷をもつ負荷点または負荷領域を座標空間上に固定し、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点と負荷点または負荷領域との間に働く引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算装置。
【請求項３１】
請求項１６から３０のいずれか１項に記載の経路計算装置と、
前記ノードと、を有することを特徴とする通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワーク（以下、単に「ネットワーク」と称す）を設計する技術に関し、特に、ネットワーク上のパスの経路を計算する技術に関する。
【背景技術】
【０００２】
近年の情報通信技術の普及により、ネットワークはユーザ数の増加とともに大規模化を続けている。ネットワークのトポロジは、ツリー状やリング状からメッシュ状へと遷移しており、パスの送信ノードと受信ノード間には様々な経路候補が存在する。【０００３】
こうした背景の下、ユーザは、通信帯域・遅延・パスの信頼性など、パスの通信品質についての様々な要求を通信サービスプロバイダに対して指定できるようになっている。【０００４】
そのため、通信サービスプロバイダは、ユーザから要求されている品質を考慮しながら、多くのユーザトラヒックを、なるべく少ないコストで収容できるようネットワーク上のパスを設計する。これはネットワーク設計問題として知られている。【０００５】
ネットワーク設計問題の解法には、数理計画法、動的計画法、ヒューリスティック法が用いられる。【０００６】
数理計画法では、ネットワーク設計問題の定式化により厳密な最適解を得ることができるが、変数の数が増えると、計算量が膨大になるため、大規模なネットワーク設計問題では実時間で解を得るのは非常に困難である。【０００７】
動的計画法では、ネットワーク設計問題に含まれるパスを１本ずつ順番に計算する。既に計算したパスは変更しないため計算時間は短いが、解がパスの計算順序に依存し、局所解に陥りやすい。また、トラップトポロジと呼ばれるトポロジ構造をネットワークが有している場合、実際には経路があるにもかかわらず、パスの経路計算に失敗してしまう。【０００８】
ヒューリスティック法では、遺伝的アルゴリズム、ニューラルネットワーク、古典力学のモデルを応用した経路計算方法などが考えられている。これらの方法は、厳密な最適解は保証できないが、状況の変化に対応できるため、動的計画法におけるトラップトポロジの問題を克服でき、実時間で最適な局所解を求めることができるという利点がある。【０００９】
他方、ヒューリスティック法の欠点は、確率的な要素が入ること、計算終了条件があいまいなこと、事前準備が必要なこと、などが挙げられる。【００１０】
遺伝的アルゴリズムでは、突然変異をモデル化するために確率が用いられる。しかし、確率を使用する場合、試行の度に計算結果が変わる可能性があり、再現性がないという問題がある。同一のパスに対して経路計算をする度に経路が変わってしまうと、ネットワーク設計法としての信頼性が損なわれる。また、遺伝的アルゴリズムでは、解候補である遺伝子の交配を反復するが、明確な計算終了条件がない。この反復回数の上限値に理論的な根拠を与えるのは難しいため、十分大きな上限値を選ばざるを得ず、無駄な計算時間を費やすことになる。【００１１】
ニューラルネットワークでは、適切な解を出すために事前に学習過程が必要となる。また、学習方法によっては、出力する解が変化してしまう。【００１２】
したがって、古典力学のモデルのような、不確定要素が少なく、かつ、理論的な裏付けのあるモデルを応用したヒューリスティック法の方が、ネットワーク設計問題の解法には適していると考えられる。【００１３】
古典力学のモデルを応用した経路計算方法の例として、特許文献１に記載の仮想的な力を用いた経路計算方法が挙げられる。この方法は、実際の道路・通路を通過する移動体が壁などの障害物を避けて移動するように、移動体と障害物との間に仮想的な斥力を定義し、この仮想的な斥力を用いて移動体の経路を計算する方法である。【００１４】
また、ポテンシャルフィールド法と呼ばれる、仮想的な力を用いた経路計算方法も存在する（非特許文献１）。この方法は、ロボットアームなどの動作経路を決定するために、ゴール位置からロボットに作用する引力、障害物からロボットに作用する斥力、ロボットを動作範囲内に留める斥力の和からなる仮想的なポテンシャル関数を定義し、そのポテンシャル関数の最急勾配方向に向かう経路を探索する方法である。【００１５】
また、非特許文献２には、仮想的な力を用いたパスの経路計算方法が記載されている。この方法は、パケットを、送信ノードから、隣接ノードのうち受信ノードとの間の地理的距離が一番近いものへとホップバイホップ（hop-by-hop）で転送していく方法である。ただし、ノードの配置によっては、自ノードよりも受信ノードに近い隣接ノードがない状況に陥る場合がある。このような場合に、自ノードよりも受信ノードに近い隣接ノードがないノードとパケットの間に、そのノードとパケットとの間の距離に関して単調減少する斥力を与え、また、受信ノードとパケットの間に、受信ノードとパケットとの間の距離に関して単調減少する引力を与え、それらの合力を加味してパケットの転送先を決定する。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】特開２００６−３３７２９１号公報
【非特許文献】
【００１７】
【非特許文献１】Y.K.Hwang  and  N.Ahuja,  Gross  Motion  Planning  -  A  Survey,  ACM  Computing  Surveys,  vol.  24,  no.  3,  pp.  219-291,  1992
【非特許文献２】Cong  Liu  and  Jin  Wu,  "Virtual-Force-Based  Geometric  Routing  Protocol  in  MANETs,"  IEEE  Transactions  on  Parallel  and  Distributed  Systems,  vol.  20,  no.  4,  pp.  433-445,  April  2009.
【発明の概要】
【発明が解決しようとする課題】
【００１８】
しかし、上記の特許文献１および非特許文献１，２に記載の３つの方法は、単一の移動体やパケットに対して単一の最短経路を求めることしかできないため、一度に１つのパスの経路しか計算できないという課題がある。ネットワーク設計問題では、複数パスの経路を同時に計算できなければならない。また、ネットワーク設計では、通信の信頼性向上のために１つのパスに対して、異なる経路を通る予備パスを計算することもあるが、上記３つの方法ではこのような計算もできない。【００１９】
また、上記３つの方法は、常に出発点から目的点の向きに経路を探索する。このため、行き止まりに当たった場合、経路計算を遡ってやり直す必要があり、経路計算に時間がかかってしまうという課題もある。【００２０】
そこで、本発明の目的は、上述した課題のいずれかを解決することができる経路計算方法、経路計算装置、および通信システムを提供することである。
【課題を解決するための手段】
【００２１】
本発明の経路計算方法は、
ノード間がリンクにより接続されたネットワーク上のパスを計算する経路計算装置による経路計算方法であって、
ネットワークを構成するノードおよびリンクを座標空間上に固定し、該ノードに対して仮想負荷を与え、
パスを、該パスの送信ノードと受信ノードとを結ぶ線で表して座標空間上に配置し、該パスに対して仮想負荷を与え、
パスを表す線上の１以上の代表点について、該代表点と各ノードとの間に働く引力および斥力の合力から移動ベクトルを計算し、
前記移動ベクトルに応じてパスを表す線上の代表点を座標空間内で移動させることでパスの経路を求めることを特徴とする。【００２２】
本発明の経路計算装置は、
ノード間がリンクにより接続されたネットワーク上のパスを計算する経路計算部を有してなる経路計算装置であって、
前記経路計算部は、
ネットワークを構成するノードおよびリンクを座標空間上に固定し、該ノードに対して仮想負荷を与え、
パスを、該パスの送信ノードと受信ノードとを結ぶ線で表して座標空間上に配置し、該パスに対して仮想負荷を与え、
パスを表す線上の１以上の代表点について、該代表点と各ノードとの間に働く引力および斥力の合力から移動ベクトルを計算し、
前記移動ベクトルに応じてパスを表す線上の代表点を座標空間内で移動させることでパスの経路を求めることを特徴とする。【００２３】
本発明の通信システムは、
前記経路計算装置と、
前記ノードと、を有することを特徴とする。
【発明の効果】
【００２４】
本発明によれば、パスを送信ノードと受信ノード間を結ぶ線で表して仮想負荷を与え、パスを表す線上の代表点について、各ノードとの間に働く引力および斥力の合力から移動ベクトルを求め、移動ベクトルに応じてパスの線を移動させることで、パスの経路を求める。【００２５】
したがって、特許文献１および非特許文献１，２に記載の方法のように、出発点から目的点の向きに経路を探索することはしないため、行き止まりに当たって経路計算を遡ってやり直すという事象が発生せず、パスの経路計算の高速化が図れるという効果が得られる。
【図面の簡単な説明】
【００２６】
【図１】本発明の第１の実施形態の経路計算装置の構成を示すブロック図である。
【図２】ネットワークのトポロジとパスの一例を示す図である。
【図３】図２に示したトポロジとパスに与えられる仮想負荷の量と色を表すテーブルを示す図である。
【図４】図３に示した仮想負荷の色の組み合わせと２つの仮想負荷の間に働く力の向きとの関係性を表すテーブルを示す図である。
【図５】本発明の第１の実施形態の経路計算装置による経路計算方法の流れを示すフロー図である。
【図６】図２に示したパスが、経路計算過程で移動する様子を示す図である。
【図７】本発明の第２の実施形態の経路計算装置の構成を示すブロック図である。
【図８】本発明の第２の実施形態の経路計算装置による経路計算方法の流れを示すフロー図である。
【図９Ａ】図８に示した経路計算方法の流れを説明する図である。
【図９Ｂ】図８に示した経路計算方法の流れを説明する図である。
【図９Ｃ】図８に示した経路計算方法の流れを説明する図である。
【図９Ｄ】図８に示した経路計算方法の流れを説明する図である。
【図９Ｅ】図８に示した経路計算方法の流れを説明する図である。
【図１０】本発明の第３の実施形態の経路計算装置による経路計算方法の流れを示すフロー図である。
【図１１Ａ】図１０に示した経路計算方法の流れを説明する図である。
【図１１Ｂ】図１０に示した経路計算方法の流れを説明する図である。
【図１１Ｃ】図１０に示した経路計算方法の流れを説明する図である。
【図１１Ｄ】図１０に示した経路計算方法の流れを説明する図である。
【図１１Ｅ】図１０に示した経路計算方法の流れを説明する図である。
【発明を実施するための形態】
【００２７】
以下に、本発明を実施するための形態について図面を参照して説明する。
（第１の実施形態）
図１は、本発明の第１の実施形態の経路計算装置の構成を示すブロック図である。なお、本発明の経路計算装置は、ネットワーク上で通信システムを構成するノードの内部、または、ノードの外部のサーバ等により実現されるものとする。
【００２８】
図１を参照すると、本実施形態の経路計算装置は、ネットワークＤＢ（Data  Base）  Ｍ１０１と、仮想負荷ＤＢ  Ｍ１０２と、経路計算部Ｍ１０３と、を有している。
【００２９】
ネットワークＤＢ  Ｍ１０１は、ノード、リンク、パスの情報を保持するデータベースである。ネットワークＤＢ  Ｍ１０１では、ノードについては、少なくとも、そのノードの識別子、そのノードの物理容量（単位時間当たりに処理できるビット数。ｂｐｓ）、そのノードの空き容量、および、そのノードの座標の情報を保持する。また、リンクについては、少なくとも、そのリンクの識別子、そのリンクが接続されているノードの識別子、そのリンクの物理容量（ｂｐｓ、あるいは、リンクで収容できる総波長数、総時間枠数、総パケット量等。以下、同じ）、および、そのリンクの空き容量の情報を保持する。また、パスについては、少なくとも、そのパスの識別子、そのパスが接続されている送信ノードと受信ノードの識別子、および、そのパスを流れるトラヒック量の情報を保持する。
【００３０】
ネットワークＤＢ  Ｍ１０１で保持されている情報から、例えば、図２のようにネットワークおよびパスの構成が表現される。図２において、Ｎ１〜Ｎ５はノード、Ｌ１〜Ｌ５はリンク、Ｐ１とＰ２はパスを表す線、ｓ１とｄ１は線Ｐ１、Ｐ２の端点である。図２では、判別しやすくするためにノードおよびパスの端点を丸で示しているが、各ノードは座標点で表現される。リンクは、ノードの座標点間を結ぶ直線であり、パスは、送信ノードと受信ノードの座標点間を結ぶ任意の形状をした線である。ここで、座標空間は二次元または三次元で表現される。
【００３１】
仮想負荷ＤＢ  Ｍ１０２は、仮想負荷に関する情報を保持するデータベースである。仮想負荷は、量（絶対値）と属性との組み合わせで表現され、ノード、リンク、およびパスのそれぞれに与えられる。なお、本明細書では、この仮想負荷の属性を「色」と呼ぶこととする。仮想負荷の量と色の情報は、図３のテーブルのようにして仮想負荷ＤＢ  Ｍ１０２で保持される。また、２つの仮想負荷の色の組み合わせに応じて、両仮想負荷の間に働く仮想力の向きは、引力（＋）、斥力（−）、中性（０）のいずれかに決定される。仮想負荷の色の各組み合わせと仮想力の向きとの関係性の情報は、図４のテーブルのようにして仮想負荷ＤＢ  Ｍ１０２で保持される。
【００３２】
なお、図３では、説明を簡単にするために、ノード同士、リンク同士、パス同士で、仮想負荷の量を同じにしているが、仮想負荷の量は、ノード、リンク、パスで１つ１つ異なる値でも構わない。また、ノードとリンクの仮想負荷には同じ色を与えているが、仮想負荷の色は、ノード、リンクで１つ１つ異なっていても構わない。さらに、パスの仮想負荷には、パス間に働く仮想力が斥力（−）になるように色を与えているが、引力（＋）や中性（０）になるように色を与えても構わない。例えば、パスの仮想負荷の色は、デフォルトでは、パス間に働く仮想力が中性（０）になるようにし、パス同士に同じ経路を通らせる場合は引力（＋）に、また、パス同士に異なる経路を通らせる場合は斥力（−）になるようにしても構わない。また、パスの仮想負荷には、ノードやリンクとの間に働く仮想力が引力（＋）になるように色を与えているが、斥力（−）や中性（０）になるように色を与えても構わない。
【００３３】
経路計算部Ｍ１０３は、経路計算条件（例えば、上述の仮想力の条件、経路計算結果の短さの条件等）が予め設定されている。
【００３４】
そのため、経路計算部Ｍ１０３は、経路計算条件に従って、仮想負荷の量、色、色の組み合わせと仮想力の向きとの関係性を決定し、図３および図４のテーブルのようにして仮想負荷ＤＢ  Ｍ１０２で保持させる。なお、経路計算部Ｍ１０３は、図３および図４のテーブルの値を経路計算の過程で動的に変更しても構わない。
【００３５】
また、経路計算部Ｍ１０３は、経路計算条件に従って、ネットワークＤＢ  Ｍ１０１に保持されたネットワークとパスの情報と、仮想負荷ＤＢ  Ｍ１０２に保持された仮想負荷の情報と、を基にして、ネットワーク上のパスの経路を計算する。
【００３６】
以下、本実施形態の経路計算装置によるパスの経路計算方法について、図５のフロー図を参照して説明する。ここでは、ネットワーク設計問題が図２〜図４で示された状況にあるものとする。
【００３７】
図５を参照すると、まず、ステップＳ１０１において、経路計算部Ｍ１０３は、ネットワークＤＢ  Ｍ１０１からノードＮ１〜Ｎ５の各々の座標の情報を取得し、座標空間上の座標点にノードＮ１〜Ｎ５を配置し固定する。次に、経路計算部Ｍ１０３は、ノードＮ１〜Ｎ５間を結ぶリンクとして、ネットワークＤＢ  Ｍ１０１からリンクＬ１〜Ｌ５を抽出し座標空間上に配置し固定する。次に、経路計算部Ｍ１０３は、座標空間上に配置したノードＮ１〜Ｎ５とリンクＬ１〜Ｌ５に対し、経路計算条件に従って仮想負荷を与え、その仮想負荷の情報を、図３のテーブルのようにして仮想負荷ＤＢ  Ｍ１０２に保持させる。仮想負荷の量には、定数、物理容量に比例する量、もしくは空き容量に比例する量などを用いる。また、経路計算部Ｍ１０３は、ノードＮ１〜Ｎ５とリンクＬ１〜Ｌ５に与えた仮想負荷の色の組み合わせと仮想力の向きとの関係性を、図４のテーブルのようにして仮想負荷ＤＢ  Ｍ１０２に保持させる（Ｔ２０１とＴ２１１の欄）。
【００３８】
次に、ステップＳ１０２において、経路計算部Ｍ１０３は、パスを、トラヒック要求にて要求された送信ノードＮ２と受信ノードＮ５とを結ぶ線Ｐ１、Ｐ２で表して、座標空間上に配置する。線Ｐ１、Ｐ２の形状は直線でも曲線でも構わない。また、送信ノードＮ２と受信ノードＮ５間の最短経路をダイクストラ法などで求め、その最短経路を線Ｐ１、Ｐ２の初期位置としても構わない。さらに、経路計算部Ｍ１０３は、線Ｐ１、Ｐ２を配置した各パスに対し、ノードＮ１〜Ｎ５とリンクＬ１〜Ｌ５と同様、経路計算条件に従って仮想負荷を与え、その仮想負荷の情報を、図３のテーブルのようにして仮想負荷ＤＢ  Ｍ１０２に追加で保持させる。仮想負荷の量には、要求された物理容量やトラヒック量に比例する量などを用いる。また、経路計算部Ｍ１０３は、仮想負荷の色の組み合わせと仮想力の向きとの関係性を、図４のテーブルのようにして仮想負荷ＤＢ  Ｍ１０２に追加で保持させる（Ｔ２０２、Ｔ２０３、Ｔ２１２、Ｔ２１３の欄）。
【００３９】
次に、ステップＳ１０３において、経路計算部Ｍ１０３は、各パスに対して、ノードＮ１〜Ｎ５とリンクＬ１〜Ｌ５から働く仮想力の合力を計算する。仮想力はベクトルで表され、仮想力の合力はベクトル和によって算出される。詳細には、経路計算部Ｍ１０３は、パスを表す線Ｐ１、Ｐ２の各々について、送信ノードＮ２および受信ノードＮ５とは異なる位置に１以上の代表点をとり、各代表点に対してノードＮ１〜Ｎ５とリンクＬ１〜Ｌ５から働く仮想力の合力を求める。代表点の位置の取り方は任意であり、等間隔、変曲点上、ランダムなどがある。また、各代表点には、パスに与えた仮想負荷の量を代表点の数に応じて分配する。
【００４０】
パスを表す線Ｐ１上のある代表点Ｐ１ａに分配される仮想負荷の量をＺａとすると、ノードＮｉ（ｉ＝１，２，…，５）からＰ１ａに対して働く仮想力は、Ｘ＊Ｚａに関して単調増加し、代表点Ｐ１ａとノードＮｉとの間の距離に関して単調減少する。例えば、仮想力をＦとすると、例えば、Ｆ＝ｋ＊（Ｘ＊Ｚａ）／（代表点Ｐ１ａとノードＮｉとの間の距離）、と表すことができる（ｋは係数）。この仮想力は、図４のＴ２０１とＴ２１２の関係から引力として働く。つまり、代表点Ｐ１ａはノードＮｉの向きに引かれる。なお、代表点Ｐ１ａとノードＮｉとの間の距離が大きい場合は、代表点Ｐ１ａとノードＮｉの間に働く仮想力の大きさが非常に小さいため、その仮想力の計算を省略しても構わない。
【００４１】
また、リンクＬｉ（ｉ＝１，２，…，５）から代表点Ｐ１ａに対して働く仮想力はリンクＬｉ上の代表点ＬｉｋがＰ１ａに及ぼす仮想力の合力として算出される。リンクＬｉ上の代表点の取り方ならびにリンクＬｉの仮想負荷量の代表点への分配方法は、パスＰ１上の代表点の取り方と同様である。リンクＬｉ上の代表点Ｌｉｋの仮想負荷量をＸｋとすると、代表点Ｌｉｋが代表点Ｐ１ａに及ぼす仮想力は、Ｘｋ＊Ｚａに関して単調増加し、代表点Ｐ１ａと代表点Ｌｉｋとの間の距離に関して単調減少する。この仮想力は、図４のＴ２０１とＴ２１２の関係から引力として働く。つまり、代表点Ｐ１ａはリンクＬｉの向きに引かれる。なお、代表点Ｐ１ａとＬｉｋとの間の距離が大きい場合は、代表点Ｐ１ａとＬｉｋの間に働く仮想力の大きさが非常に小さいため、その仮想力の計算を省略しても構わない。
【００４２】
次に、ステップＳ１０４において、経路計算部Ｍ１０３は、各パスに対して、他のパスから働く仮想力の合力を計算する。詳細には、経路計算部Ｍ１０３は、ステップＳ１０３でとった線Ｐ１の各代表点に対して、同じくステップＳ１０３でとった線Ｐ２の各代表点から働く仮想力の合力を計算する。線Ｐ２上のある代表点をＰ２ａとし、その仮想負荷量をＺｂとすると、代表点Ｐ２ａが代表点Ｐ１ａに及ぼす仮想力はＺａ＊Ｚｂに関して単調増加し、代表点Ｐ１ａとＰ２ａとの間の距離に関して単調減少する。この仮想力は、図４のＴ２０２とＴ２１３の関係から斥力として働く。つまり、線Ｐ１の代表点Ｐ１ａは線Ｐ２の代表点Ｐ２ａから離れようとする。なお、代表点Ｐ１ａとＰ２ａとの間の距離が大きい場合は、代表点Ｐ１ａとＰ２ａとの間に働く仮想力の大きさが非常に小さいため、その仮想力の計算を省略しても構わない。
【００４３】
ここで、経路計算部Ｍ１０３は、経路計算条件が経路計算結果としてなるべく短い経路を希望することを示している場合、ステップＳ１０６に進む前に、ステップＳ１０５において、各パス自身の張力を計算する。詳細には、経路計算部Ｍ１０３は、ステップＳ１０３でとった線Ｐ１、Ｐ２の各代表点に対して、その代表点に働く張力の合力を計算する。張力はパスの長さに関して単調増加する。例えば、張力は、元の長さ（ｘ０）からの差分（ｘ−ｘ０）に比例し、張力をＴとすると、Ｔ＝ｋ＊（ｘ−ｘ０）、と表すことができる（ｘ０≧０、ｋは係数）。例えば、ｘ０＝０で、かつ、線Ｐ１上に代表点Ｐ１ａが１つだけある場合、代表点Ｐ１ａには、端点ｓ１の方向に端点ｓ１との間の長さに比例する力で引きつける張力と、端点ｄ１の方向に端点ｄ１との間の長さに比例する力で引きつける張力と、が働くため、ステップＳ１０５においては、それらの合力が計算される。
【００４４】
次に、ステップＳ１０６において、経路計算部Ｍ１０３は、まず、パスを表す線Ｐ１、Ｐ２の代表点に対して、ステップＳ１０３、Ｓ１０４で求めた仮想力の合力を求める。このとき、ステップＳ１０５で張力を求めた場合には、経路計算部Ｍ１０３は、その張力をさらに加えて、仮想力の合力を求める。次に、経路計算部Ｍ１０３は、代表点に働く仮想力の合力をスカラー倍（スカラー値は任意の正の実数値）したものを、その代表点の移動ベクトルとして与える。
【００４５】
経路計算部Ｍ１０３は、線Ｐ１、Ｐ２の各代表点を、移動ベクトルに従って移動させ、最終的には、線Ｐ１、Ｐ２を、互いに引き合うノードおよびリンクと密着させて、パスの経路を求めることになる。
【００４６】
もし、全ての代表点の移動ベクトルがゼロベクトルである場合（ステップＳ１０７のＹｅｓ）、移動する代表点が存在しないため、線Ｐ１、Ｐ２のどちらもノードおよびリンクと密着していることになる。よって、経路計算部Ｍ１０３は、ステップＳ１０８において、経路計算を完了する。
【００４７】
一方、少なくとも一つの代表点の移動ベクトルがゼロベクトルでない場合（ステップＳ１０７のＮｏ）、経路計算部Ｍ１０３は、ステップＳ１０９において、各代表点を移動ベクトルに従って移動させ、その後に、ステップＳ１０３の処理に戻る。
【００４８】
図２〜図４の例では、線Ｐ１、Ｐ２はそれぞれノードＮ１〜Ｎ５とリンクＬ１〜Ｌ５に引き付けられる一方、互いに反発し合うため、図６の矢印のように移動する。そして、最終的には、線Ｐ１は、経路Ｎ２−Ｌ１−Ｎ１−Ｌ５−Ｎ５に、線Ｐ２は経路Ｎ２−Ｌ２−Ｎ３−Ｌ３−Ｎ４−Ｌ４−Ｎ５に密着して停止し、この２つの経路がパスの経路として求められることになる。
【００４９】
なお、本実施形態においては、パスが２本であったが、パスの数は１本でも構わないし、３本以上でも構わない。また、ノード数およびリンク数も、本実施形態の例より少なくても多くても構わないし、また、ネットワークのトポロジが異なっても構わない。
【００５０】
また、本実施形態においては、パスの線上の各代表点に対して、ノード、リンクおよび他のパスとの間に働く仮想力の合力から移動ベクトルを求めているが、ノードとの間に働く仮想力の合力のみから移動ベクトルを求めても構わないし、ノードおよびリンクとの間に働く仮想力の合力のみから移動ベクトルを求めても構わない。
【００５１】
また、本実施形態においては、経路計算部Ｍ１０３が、予め設定されている経路計算条件に従って、ノード、リンク、およびパスに仮想負荷を与えているが、ユーザが不図示の操作部を介して、仮想負荷ＤＢ  Ｍ１０２に対して仮想負荷を与えても構わない。この場合、経路計算部Ｍ１０３は各ノード・リンク・パスに対して、仮想負荷ＤＢ  Ｍ１０２から取得した仮想負荷情報に従って仮想負荷を付与する。
【００５２】
上述したように本実施形態においては、パスを送信ノードと受信ノード間を結ぶ線で表して仮想負荷を与え、パスを表す線上の代表点について、少なくともノードとの間に働く引力および斥力の合力から移動ベクトルを求め、移動ベクトルに応じてパスの線を移動させることで、パスの経路を求める。
【００５３】
したがって、特許文献１および非特許文献１，２に記載の方法のように、出発点から目的点の向きに経路を探索することはしないため、行き止まりに当たって経路計算を遡ってやり直すという事象が発生せず、経路計算の高速化が図れるという効果が得られる。
【００５４】
また、パスの線上の各代表点の移動ベクトルの計算に、他のパスとの間に働く引力および斥力も加えた場合には、パス同士の引力および斥力をも考慮して経路計算を行うことができるため、複数パスの経路を同時に計算できるという効果が得られる。
【００５５】
したがって、複数パスの最適な経路を高速に計算することができる。これにより、現用・予備パスの設計、１対他通信用パスの設計、Ｐ２ＭＰ（Point-to-Multipoint）パスの設計、ＶＰＮ（Virtual  Private  Network）の設計などが簡単になるという効果も得られる。
（第２の実施形態）
図７は、本発明の第２の実施形態の経路計算装置の構成を示すブロック図である。
【００５６】
図７を参照すると、本実施形態の経路計算装置は、図１の第１の実施形態と比較して、経路計算過程ならびに経路計算結果を表示する表示部Ｍ１０４と、ユーザが表示部Ｍ１０４を介して経路計算条件を変更する操作を行うための操作部Ｍ１０５と、を追加した点が異なる。
【００５７】
表示部Ｍ１０４および操作部Ｍ１０５の実装方法としては、例えば、画面上に表示したメニューをマウス操作またはキーボード操作する実装でも構わないし、画面をタッチパネルで操作する実装でも構わない。
【００５８】
表示部Ｍ１０４は、操作部Ｍ１０５により経路計算条件を変更する操作が行われた場合、ネットワークＤＢ  Ｍ１０１および仮想負荷ＤＢ  Ｍ１０２に直接アクセスしてネットワークＤＢ  Ｍ１０１および仮想負荷ＤＢ  Ｍ１０２の更新をしても構わないし、経路計算部Ｍ１０３に設定されている経路計算条件を変更し、経路計算部Ｍ１０３にネットワークＤＢ  Ｍ１０１および仮想負荷ＤＢ  Ｍ１０２の更新をさせても構わない。
【００５９】
以下、本実施形態の経路計算装置によるパスの経路計算方法について、図８のフロー図を参照して説明する。なお、図８において、図５と同様のステップには、同様の符号を付している。ただし、図５とは異なり、経路計算するパスは１本であるとする。
【００６０】
図８を参照すると、まず、経路計算部Ｍ１０３は、図５のステップＳ１０１と同様の処理により、ノードＮ１〜Ｎ５とリンクＬ１〜Ｌ５を配置して固定する。
【００６１】
次に、ステップＳ２０１において、経路計算部Ｍ１０３は、ステップＳ１０１が終了した旨を表示部Ｍ１０４へ通知し、表示部Ｍ１０４は、ステップＳ１０１終了時の経路計算過程を画面に表示し、表示画面を更新する。この時の表示画面の例を図９Ａに示す。
【００６２】
この時点で、ユーザは、操作部Ｍ１０５によって、ネットワークのトポロジ、仮想負荷の量または色等の経路計算条件を変更することができる。
【００６３】
次に、経路計算部Ｍ１０３は、図５のステップＳ１０２と同様の処理により、パスを表す線Ｐ１を配置する。
【００６４】
次に、ステップＳ２０２において、経路計算部Ｍ１０３は、ステップＳ１０２が終了した旨を表示部Ｍ１０４へ通知し、表示部Ｍ１０４は、ステップＳ１０２終了時の経路計算過程を画面に表示し、表示画面を更新する。この時の表示画面の例を図９Ｂに示す。
【００６５】
この時点で、ユーザは、操作部Ｍ１０５によって、ネットワークのトポロジ、仮想負荷の量または色、パスの経路等の経路計算条件を変更することができる。
【００６６】
例えば、ユーザは、線Ｐ１のパスと、そのパスに要求されるトラヒック量以下の空き容量をもつノードまたはリンクと、の間に働く仮想力の向きが、斥力（−）または中性（０）になるように、そのノードまたはリンクの仮想負荷の色を変更するか、その色の組み合わせと仮想力の向きとの関係性を変更することができる。あるいは、ユーザは、線Ｐ１のパスと、そのパスに要求されるトラヒック量よりも大きな空き容量をもつノードまたはリンクと、の間に働く仮想力の向きが、引力（＋）または中性（０）になるように、そのノードまたはリンクの仮想負荷の色を変更するか、その色の組み合わせと仮想力の向きとの関係性を変更することができる。この場合、表示部Ｍ１０４または経路計算部Ｍ１０３により、仮想負荷ＤＢ  Ｍ１０２が変更されて更新される。
【００６７】
また、ユーザは、この段階でパスの線上の任意の位置に代表点を作り、その代表点を任意の座標へ移動できる。さらに、その代表点の位置を固定することができる。例えば、配置されたパスＰ１の線上に一つの代表点Ｐ１ｘを取り、この代表点をノードＮ１の座標に移動させ、ノードＮ１に密着した状態で固定することができる。この場合、経路計算部Ｍ１０３は、以降、その代表点をノードＮ１に固定させた状態で、経路計算を行う。あるいは、パスの線上に座標を固定された代表点がある場合、ユーザはその代表点の固定を解除することができる。
【００６８】
さらに、ユーザはこの時点で、ノード・リンクに密着したパスに要求されるトラヒック量に対して、そのノード・リンクの空き容量が不足している場合は物理容量を追加するかどうかのポリシを決めておき、それを経路計算部Ｍ１０３に設定しておくことができる。空き容量が不足する場合は物理容量を追加するように経路計算部Ｍ１０３が設定されている場合、経路計算部Ｍ１０３は、ノード・リンクに密着したパスに要求されるトラヒック量と、そのノード・リンクの空き容量と、を比較し、トラヒック量が空き容量を上回るときは、経路計算部Ｍ１０３がそのノード・リンクに物理容量を追加し、ネットワークＤＢ  Ｍ１０１を更新する。また、ノード・リンクの仮想負荷の量が物理容量や空き容量に基づいて算出されている場合、経路計算部Ｍ１０３はさらに、仮想負荷ＤＢ  Ｍ１０２を更新する。
【００６９】
一方、ユーザが空き容量が不足する場合でも物理容量を追加しないように経路計算部Ｍ１０３を設定している場合、ノード・リンクの仮想負荷の色とパスの仮想負荷の色の組み合わせを、ノード・リンクの空き容量がパスのトラヒック量以上であれば引力（＋）、そうでなければ斥力（−）となるように、仮想負荷ＤＢ  Ｍ１０２を動的に更新する機能を経路計算部Ｍ１０３に具備させることもできる。これにより、パスの線が空き容量不足のノードあるいはリンクに密着するのを防ぐことができる。
【００７０】
以降、経路計算部Ｍ１０３は、図５のステップＳ１０３〜Ｓ１０６と同様の処理により、各代表点の移動ベクトルを計算する。ここでは、例えば、線Ｐ１上の代表点Ｐ１ａには、図９Ｃに示すように、ノードＮ１〜Ｎ５から受ける引力Ｆ１〜Ｆ５と、線Ｐ１の端点ｓ１、ｄ１から受ける張力Ｔ１、Ｔ２と、図示していないが、リンクＬ１〜Ｌ５からの引力または斥力と、が働いており、これらの合力から移動ベクトルが計算される。
【００７１】
もし、少なくとも一つの代表点の移動ベクトルがゼロベクトルでない場合（ステップＳ１０７のＮｏ）、経路計算部Ｍ１０３は、図５と同様のステップＳ１０９の処理により、各代表点を移動ベクトルに従って移動させる。
【００７２】
次に、ステップＳ２０３において、経路計算部Ｍ１０３は、ステップＳ１０９が終了した旨を表示部Ｍ１０４へ通知し、表示部Ｍ１０４は、ステップＳ１０９終了時の経路計算過程を画面に表示し、表示画面を更新する。この時の表示画面の例を図９Ｄに示す。
【００７３】
この時点で、ユーザは、操作部Ｍ１０５によって、ネットワークのトポロジ、仮想負荷の量または色、パスの経路等の経路計算条件を変更することができる。
【００７４】
例えば、ユーザは、この段階でパスの線上に存在する代表点を任意の座標点へ移動できる。さらに、その代表点の位置を固定することができる。また、パスの線上の任意の位置に代表点を追加し、その代表点を任意の座標へ移動できる。さらに、その追加した代表点の位置を固定することができる。これらの場合、経路計算部Ｍ１０３は、以降、固定された代表点を動かすことなく経路計算を行う。あるいは、ユーザは、パスの線上のある代表点が固定されている場合、その固定を解除することができる。
【００７５】
なお、ユーザは、代表点の移動・位置固定および位置固定の解除を、ステップＳ２０２、Ｓ２０３、Ｓ２０４に限らず、経路計算過程の任意のタイミングで行っても構わない。
【００７６】
一方、全ての代表点の移動ベクトルがゼロベクトルである場合（ステップＳ１０７のＹｅｓ）、経路計算部Ｍ１０３は、図５と同様のステップＳ１０８において、経路計算を完了し、ステップＳ２０４において、ステップＳ１０８が終了した旨を表示部Ｍ１０４へ通知し、表示部Ｍ１０４は、ステップＳ１０８終了時の経路計算過程を画面に表示し、表示画面を更新する。この時の表示画面の例を図９Ｅに示す。図９Ｅのように、線Ｐ１は、最終的には、経路Ｎ２−Ｌ１−Ｎ１−Ｌ５−Ｎ５に密着して停止し、この経路がパスの経路となる。
【００７７】
この時点で、ユーザは、操作部Ｍ１０５によって、ネットワークのトポロジ、仮想負荷の量または色、パスの経路等の経路計算条件を変更することができる。なお、この場合、変更した経路計算条件は、次回の経路計算に反映されることになる。
【００７８】
例えば、ユーザは、ノード・リンクに密着したパスに要求されるトラヒック量と、そのノード・リンクの空き容量と、を比較し、トラヒック量が空き容量以下の場合には、そのノード・リンクの現在の物理容量からパスのトラヒック量を減じたものを、そのノード・リンクの新たな空き容量する。このとき、物理容量はそのままとする。一方、トラヒック量が空き容量よりも大きい場合には、ユーザは、そのノード・リンクの現在の物理容量に、パスのトラヒック量を収容できる物理容量を追加できる。この場合、そのノード・リンクの新たな物理容量は、追加前の物理容量とユーザが追加した物理容量の和とする。このとき、そのノード・リンクの新たな物理容量から、パスのトラヒック量を減じたものを、新たな空き容量とする。また、この場合、表示部Ｍ１０４または経路計算部Ｍ１０３により、ネットワークＤＢ  Ｍ１０１が更新される。さらに、ノード・リンクの仮想負荷の量が物理容量や空き容量に基づいて算出されている場合は、表示部Ｍ１０４または経路計算部Ｍ１０３により、仮想負荷ＤＢ  Ｍ１０２が更新される。なお、上記のようなノード・リンクの物理容量と空き容量の更新は、経路計算の完了後に限らず、経路計算の途中にノード・リンクにパスが密着した場合に行っても構わない。
【００７９】
上述したように本実施形態においては、第１の実施形態の構成に加えて、経路計算過程ならびに経路計算結果を表示する表示部Ｍ１０４と、ユーザが表示部Ｍ１０４を介して経路計算条件を変更する操作を行うための操作部Ｍ１０５と、を追加している。
【００８０】
したがって、第１の実施形態の効果に加えて、ユーザが、経路計算の途中ならびに完了後に、経路計算条件を変更できるという効果が得られる。
（第３の実施形態）
本実施形態の経路計算装置の構成自体は、図１の第１の実施形態または図７の第２の実施形態と同様である。
【００８１】
ただし、本実施形態においては、座標空間上に、ネットワークおよびパスとは無関係な仮想負荷をもつ負荷点もしくは負荷領域を配置し、この負荷点もしくは負荷領域から各代表点に対して働く仮想力をさらに加えて、各代表点の移動ベクトルを計算する点が、第１の実施形態および第２の実施形態とは異なる。
【００８２】
以下、本実施形態の経路計算装置によるパスの経路計算方法について、図１０のフロー図を参照して説明する。なお、図１０においては、本実施形態の経路計算装置の構成が図７の第２の実施形態と同様であるものとする。また、図８と同様に、経路計算するパスは１本であるものとし、図８と同様のステップには、同様の符号を付している。
【００８３】
図１０を参照すると、まず、経路計算部Ｍ１０３は、ステップＳ３０１において、図８のステップＳ１０１と同様の処理によりノードＮ１〜Ｎ５とリンクＬ１〜Ｌ５を配置して固定し、さらに、ネットワークおよびパスとは無関係な仮想負荷をもつ負荷点もしくは負荷領域を配置して固定する。ここでは、負荷領域Ａ１を配置するものとする。このとき、経路計算部Ｍ１０３は、負荷領域Ａ１の仮想負荷の情報を仮想負荷ＤＢ  Ｍ１０２に保持させる。ステップＳ３０１終了時の経路計算過程の画面は、ステップＳ２０１において、表示部Ｍ１０４により表示される。この時の表示画面の例を図１１Ａに示す。
【００８４】
次に、経路計算部Ｍ１０３は、図８のステップＳ１０２と同様の処理により、パスを表す線Ｐ１を配置する。ステップＳ１０２終了時の経路計算過程の画面は、ステップＳ２０２において、表示部Ｍ１０４により表示される。この時の表示画面の例を図１１Ｂに示す。
【００８５】
以降、経路計算部Ｍ１０３は、図８のステップＳ１０３〜Ｓ１０６と同様の処理により、各代表点の移動ベクトルを計算する。ここでは、例えば、線Ｐ１上の代表点Ｐ１ａには、図１１Ｃに示すように、ノードＮ１〜Ｎ５から受ける引力Ｆ１〜Ｆ５と、線Ｐ１の端点ｓ１、ｄ１から受ける張力Ｔ１、Ｔ２と、負荷領域Ａ１から受ける斥力Ｆ６と、図示していないが、リンクＬ１〜Ｌ５からの引力または斥力と、が働いており、これらの合力から移動ベクトルが計算される。
【００８６】
もし、少なくとも一つの代表点の移動ベクトルがゼロベクトルでない場合（ステップＳ１０７のＮｏ）、経路計算部Ｍ１０３は、図５と同様のステップＳ１０９の処理により、各代表点を移動ベクトルに従って移動させる。ステップＳ１０９終了時の経路計算過程の画面は、ステップＳ２０３において、表示部Ｍ１０４により表示される。この時の表示画面の例を図１１Ｄに示す。
【００８７】
一方、全ての代表点の移動ベクトルがゼロベクトルである場合（ステップＳ１０７のＹｅｓ）、経路計算部Ｍ１０３は、図５と同様のステップＳ１０８において、経路計算を完了する。ステップＳ１０８終了時の経路計算過程の画面は、ステップＳ２０４において、表示部Ｍ１０４により表示される。この時の表示画面の例を図１１Ｅに示す。図１１Ｅのように、線Ｐ１は、最終的には、経路Ｎ２−Ｌ２−Ｎ３−Ｌ３−Ｎ４−Ｌ４−Ｎ５に密着して停止し、この経路がパスの経路となる。
【００８８】
なお、説明を省略したが、負荷領域Ａ１の仮想負荷等は、ステップＳ２０１〜Ｓ２０４において、ユーザが操作部Ｍ１０５を操作することで追加、変更、および削除することができる。
【００８９】
上述したように本実施形態においては、ネットワークおよびパスとは無関係な仮想負荷をもつ負荷点もしくは負荷領域を配置し、この負荷点もしくは負荷領域から各代表点に対して働く仮想力も加えて、各代表点の移動ベクトルを計算している。
【００９０】
したがって、ネットワークおよびパスとは無関係な負荷点あるいは負荷領域が存在する場合にも、そのような負荷点あるいは負荷領域を考慮した経路計算を行うことができるという効果が得られる。その他の効果は第１および第２の実施形態と同様である。
（第４の実施形態）
本発明の第４の実施形態は、本発明の第１、第２、または第３の実施形態において、リンクが存在しないノード間を通過するパスを認める場合として説明される。このとき、リンクが存在しないノード間の物理帯域は、例えば、無線周波数帯域や、両ノードの無線通信方式による伝送可能な最大帯域などに基づく定数値として与えられる。また、本発明の第２の実施形態に記載されているように、リンクが存在しないノード間において不足する帯域を追加する操作は、両ノードの無線通信方式を拡張ないし、変更することによって実現される。
【００９１】
これにより、例えば無線ネットワークのような、ノード間に有線リンクが存在しないネットワークや、無線ネットワークおよび有線ネットワークを含む有線・無線混合ネットワークにおいても、本発明の第１、第２、または第３の実施形態で示したような経路計算およびネットワークに対する操作を実施できる。
【００９２】
なお、本発明の経路計算装置にて行われる方法は、コンピュータに実行させるためのプログラムに適用してもよい。また、そのプログラムを記憶媒体に格納することも可能であり、ネットワークを介して外部に提供することも可能である。
【００９３】
本出願は、２００９年１２月２１日に出願された日本出願特願２００９−２８９０７０を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2011077897.tif 000003
【図２】
2011077897.tif 000004
【図３】
2011077897.tif 000005
【図４】
2011077897.tif 000006
【図５】
2011077897.tif 000007
【図６】
2011077897.tif 000008
【図７】
2011077897.tif 000009
【図８】
2011077897.tif 000010
【図９Ａ】
2011077897.tif 000011
【図９Ｂ】
2011077897.tif 000012
【図９Ｃ】
2011077897.tif 000013
【図９Ｄ】
2011077897.tif 000014
【図９Ｅ】
2011077897.tif 000015
【図１０】
2011077897.tif 000016
【図１１Ａ】
2011077897.tif 000017
【図１１Ｂ】
2011077897.tif 000018
【図１１Ｃ】
2011077897.tif 000019
【図１１Ｄ】
2011077897.tif 000020
【図１１Ｅ】
2011077897.tif 000021
【手続補正書】
【提出日】平成23年2月22日(2011.2.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ノード間がリンクにより接続されたネットワーク上のパスを計算する経路計算装置による経路計算方法であって、
ネットワークを構成するノードおよびリンクを２次元以上の座標空間上に固定し、該ノードに対して仮想負荷を与え、
パスを、該パスの送信ノードと受信ノードとを結ぶ線で表して前記座標空間上に配置し、該パスに対して仮想負荷を与え、
パスを表す線上の１以上の代表点について、該代表点と各ノードとに与えられた前記仮想負荷に基づいて算出される引力および斥力の合力から移動ベクトルを計算し、
前記移動ベクトルに応じてパスを表す線上の代表点を座標空間内で移動させることでパスの経路を求めることを特徴とする経路計算方法。
【請求項２】
請求項１に記載の経路計算方法であって、
座標空間上に固定したリンクに対して仮想負荷を与え、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該パスを表す線上の代表点と各リンクを表す線分上の１以上の代表点との間に働く、該パスを表す線上の代表点と該各リンクとに与えられた前記仮想負荷に基づいて算出される引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算方法。
【請求項３】
請求項２に記載の経路計算方法であって、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該パスを表す線上の代表点と他のパスとの間に働く、該パスを表す線上の代表点と他のパスとに与えられた前記仮想負荷に基づいて算出される引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算方法。
【請求項４】
請求項３に記載の経路計算方法であって、
パスを表す線に対して該線の長さに関して単調増加する張力を与え、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点に働く張力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算方法。
【請求項５】
請求項３または４に記載の経路計算方法であって、
前記仮想負荷を、量と属性との組み合わせで表し、２つの仮想負荷の間に働く力の向き（引力、斥力、中性）が両仮想負荷の属性の組み合わせで決定され、２つの仮想負荷の間に働く力の大きさが両仮想負荷の量の積に関して単調増加し、両仮想負荷の間の距離に関して単調減少するように定義することを特徴とする経路計算方法。
【請求項６】
請求項５に記載の経路計算方法であって、
前記パスの経路を求めるに際し、前記移動ベクトルに応じてパスを表す線上の代表点を座標空間内で移動させ、該パスを表す線をノードおよびリンクと密着させることでパスの経路を求めることを特徴とする経路計算方法。
【請求項７】
請求項５または６に記載の経路計算方法であって、
複数のパスに対して、仮想負荷の属性の組み合わせが引力もしくは中性となるように仮想負荷を与えるか、または、仮想負荷の属性の組み合わせが斥力もしくは中性となるように仮想負荷を与えることを特徴とする経路計算方法。
【請求項８】
請求項５から７のいずれか１項に記載の経路計算方法であって、
各パスを表す線の初期位置を、該パスの送信ノードと受信ノードとの間の最短経路とすることを特徴とする経路計算方法。
【請求項９】
請求項５から８のいずれか１項に記載の経路計算方法であって、
各ノードおよび各リンクに仮想負荷を与えるに際して、該仮想負荷の量を、該ノードおよびリンクの物理容量または空き容量に比例する量とすることを特徴とする経路計算方法。
【請求項１０】
請求項９に記載の経路計算方法であって、
パスの経路計算完了後、ノードおよびリンクに線が密着したパスに要求されるトラヒック量が、該ノードおよびリンクの空き容量以下の場合、該ノードおよびリンクの現在の物理容量から、パスに要求されるトラヒック量を減じたものを、該ノードおよびリンクの新たな空き容量とすることを特徴とする経路計算方法。
【請求項１１】
請求項９に記載の経路計算方法であって、
パスの経路計算途中もしくは完了後、ノードおよびリンクに線が密着したパスに要求されるトラヒック量が、該ノードおよびリンクの空き容量よりも大きい場合、該ノードおよびリンクの現在の物理容量に、該パスに要求されるトラヒック量を収容できる物理容量を追加したものを、該ノードおよびリンクの新たな物理容量とすることを特徴とする経路計算方法。
【請求項１２】
請求項９から１１のいずれか１項に記載の経路計算方法であって、
パスを配置した後、該パスと、該パスに要求されるトラヒック量以下の空き容量をもつノードもしくはリンクと、の仮想負荷の属性の組み合わせが斥力あるいは中性になるように、該ノードもしくはリンクの仮想負荷の属性を変更するか、または、該組み合わせと力の向きとの関係性を変更することを特徴とする経路計算方法。
【請求項１３】
請求項９から１１のいずれか１項に記載の経路計算方法であって、
パスを配置した後、該パスと、該パスに要求されるトラヒック量よりも大きな空き容量をもつノードもしくはリンクと、の仮想負荷の属性の組み合わせが引力あるいは中性になるように、該ノードもしくはリンクの仮想負荷の属性を変更するか、または、該組み合わせと力の向きとの関係性を変更することを特徴とする経路計算方法。
【請求項１４】
請求項５から１３のいずれか１項に記載の経路計算方法であって、
パスの経路計算過程においてパスの一部を固定することを特徴とする経路計算方法。
【請求項１５】
請求項５から１４のいずれか１項に記載の経路計算方法であって、
ネットワークおよびパスとは無関係な仮想負荷をもつ負荷点または負荷領域を座標空間上に固定し、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点と負荷点または負荷領域との間に働く引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算方法。
【請求項１６】
ノード間がリンクにより接続されたネットワーク上のパスを計算する経路計算部を有してなる経路計算装置であって、
前記経路計算部は、
ネットワークを構成するノードおよびリンクを２次元以上の座標空間上に固定し、該ノードに対して仮想負荷を与え、
パスを、該パスの送信ノードと受信ノードとを結ぶ線で表して前記座標空間上に配置し、該パスに対して仮想負荷を与え、
パスを表す線上の１以上の代表点について、該代表点と各ノードとに与えられた前記仮想負荷に基づいて算出される引力および斥力の合力から移動ベクトルを計算し、
前記移動ベクトルに応じてパスを表す線上の代表点を座標空間内で移動させることでパスの経路を求めることを特徴とする経路計算装置。
【請求項１７】
請求項１６に記載の経路計算装置であって、
前記経路計算部は、
座標空間上に固定したリンクに対して仮想負荷を与え、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該パスを表す線上の代表点と各リンクを表す線分上の１以上の代表点との間に働く、該パスを表す線上の代表点と該各リンクとに与えられた前記仮想負荷に基づいて算出される引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算装置。
【請求項１８】
請求項１７に記載の経路計算装置であって、
前記経路計算部は、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該パスを表す線上の代表点と他のパスとの間に働く、該パスを表す線上の代表点と他のパスとに与えられた前記仮想負荷に基づいて算出される引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算装置。
【請求項１９】
請求項１８に記載の経路計算装置であって、
前記経路計算部は、
パスを表す線に対して該線の長さに関して単調増加する張力を与え、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点に働く張力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算装置。
【請求項２０】
請求項１８または１９に記載の経路計算装置であって、
前記仮想負荷を、量と属性との組み合わせで表し、２つの仮想負荷の間に働く力の向き（引力、斥力、中性）が両仮想負荷の属性の組み合わせで決定され、２つの仮想負荷の間に働く力の大きさが両仮想負荷の量の積に関して単調増加し、両仮想負荷の間の距離に関して単調減少するように定義することを特徴とする経路計算装置。
【請求項２１】
請求項２０に記載の経路計算装置であって、
前記経路計算部は、
前記パスの経路を求めるに際し、前記移動ベクトルに応じてパスを表す線上の代表点を座標空間内で移動させ、該パスを表す線をノードおよびリンクと密着させることでパスの経路を求めることを特徴とする経路計算装置。
【請求項２２】
請求項２０または２１に記載の経路計算装置であって、
前記経路計算部は、
複数のパスに対して、仮想負荷の属性の組み合わせが引力もしくは中性となるように仮想負荷を与えるか、または、仮想負荷の属性の組み合わせが斥力もしくは中性となるように仮想負荷を与えることを特徴とする経路計算装置。
【請求項２３】
請求項２０から２２のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
各パスを表す線の初期位置を、該パスの送信ノードと受信ノードとの間の最短経路とすることを特徴とする経路計算装置。
【請求項２４】
請求項２０から２３のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
各ノードおよび各リンクに仮想負荷を与えるに際して、該仮想負荷の量を、該ノードおよびリンクの物理容量または空き容量に比例する量とすることを特徴とする経路計算装置。
【請求項２５】
請求項２４に記載の経路計算装置であって、
前記経路計算部は、
パスの経路計算完了後、ノードおよびリンクに線が密着したパスに要求されるトラヒック量が、該ノードおよびリンクの空き容量以下の場合、該ノードおよびリンクの現在の物理容量から、パスに要求されるトラヒック量を減じたものを、該ノードおよびリンクの新たな空き容量とすることを特徴とする経路計算装置。
【請求項２６】
請求項２４に記載の経路計算装置であって、
前記経路計算部は、
パスの経路計算途中もしくは完了後、ノードおよびリンクに線が密着したパスに要求されるトラヒック量が、該ノードおよびリンクの空き容量よりも大きい場合、該ノードおよびリンクの現在の物理容量に、該パスに要求されるトラヒック量を収容できる物理容量を追加したものを、該ノードおよびリンクの新たな物理容量とすることを特徴とする経路計算装置。
【請求項２７】
請求項２４から２６のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
パスを配置した後、該パスと、該パスに要求されるトラヒック量以下の空き容量をもつノードもしくはリンクと、の仮想負荷の属性の組み合わせが斥力あるいは中性になるように、該ノードもしくはリンクの仮想負荷の属性を変更するか、または、該組み合わせと力の向きとの関係性を変更することを特徴とする経路計算装置。
【請求項２８】
請求項２４から２６のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
パスを配置した後、該パスと、該パスに要求されるトラヒック量よりも大きな空き容量をもつノードもしくはリンクと、の仮想負荷の属性の組み合わせが引力あるいは中性になるように、該ノードもしくはリンクの仮想負荷の属性を変更するか、または、該組み合わせと力の向きとの関係性を変更することを特徴とする経路計算装置。
【請求項２９】
請求項２０から２８のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
パスの経路計算過程においてパスの一部を固定することを特徴とする経路計算装置。
【請求項３０】
請求項２０から２９のいずれか１項に記載の経路計算装置であって、
前記経路計算部は、
ネットワークおよびパスとは無関係な仮想負荷をもつ負荷点または負荷領域を座標空間上に固定し、
パスを表す線上の代表点の移動ベクトルを算出するに際し、該代表点と負荷点または負荷領域との間に働く引力および斥力をさらに加えて前記合力を求めた上で、該代表点の移動ベクトルを計算することを特徴とする経路計算装置。
【請求項３１】
請求項１６から３０のいずれか１項に記載の経路計算装置と、
前記ノードと、を有することを特徴とする通信システム。
【国際調査報告】
2011077897.tif 000022
2011077897.tif 000023
2011077897.tif 000024
2011077897.tif 000025