(57)【要約】【課題】  スタイナーツリー上のボトルネックリンクの利用帯域を軽減し、エッジルータ間のホップ数が大きい経路を少なくする。【解決手段】  本発明は、スタイナーツリー上の２つのルータ間に、該スタイナーツリー上のリンクを利用しないバイパス経路を作成し、そのバイパス経路にスタイナーツリー上の一部の経路のトラフィックを迂回させる。さらに、スタイナーツリーとバイパス経路が適用されたネットワークドメインの中で他のネットワークドメインとの間の中継を行う境界ルータがある場合は、該境界ルータと、該スタイナーツリーと該バイパス経路上に位置する他ルータとの間に、該スタイナーツリーと該バイパス経路上のリンクを利用しない新バイパス経路を作成し、その新バイパス経路を使ってエッジルータと境界ルータ間の通信を行う。【選択図】  図２
2014086898.tif 000002
【特許請求の範囲】
【請求項１】
ひとつのエッジルータをツリーの始点として、他のすべてのエッジルータを終点とするスタイナーツリーをスタイナーツリーアルゴリズムによって求め、該スタイナーツリーに属するリンクとルータを利用してエッジルータ間の経路を選択する省エネルギー経路選択方法であって、
バイパス経路作成手段、新バイパス経路作成手段を有する装置において、
前記バイパス経路作成手段が、前記スタイナーツリー上の２つのルータ間に、該スタイナーツリー上のリンクを利用しないバイパス経路を作成し、そのバイパス経路にスタイナーツリー上の一部の経路のトラフィックを迂回させるバイパス経路作成ステップを行うことを特徴とする省エネルギー経路選択方法。
【請求項２】
前記バイパス経路作成ステップにおいて、
前記スタイナーツリー上のエッジルータ間で、該ツリー上のホップ数が最も大きい区間から順番に、その区間のネットワーク上の最短経路を求め、当該最短経路パスが該スタイナーツリー上のリンクを使用しない場合には当該最短経路をバイパス経路として作成し、該スタイナーツリー上のリンクを最短経路が使用する場合は、次にホップ数が大きい区間で同じ処理を行い、この処理をバイパス経路が作成されるまで繰り返す
請求項1記載の省エネルギー経路選択方法。
【請求項３】
前記新バイパス経路作成手段が、前記スタイナーツリーと前記バイパス経路作成ステップで作成された前記バイパス経路が適用されたネットワークドメインの中で他のネットワークドメインとの間の中継を行う境界ルータがある場合は、該境界ルータと、該スタイナーツリーと該バイパス経路上に位置する他ルータとの間に、該スタイナーツリーと該バイパス経路上のリンクを利用しない新バイパス経路を作成し、その新バイパス経路を使ってエッジルータと境界ルータ間の通信を行う新バイパス経路作成ステップを更に行う
請求項１または２記載の省エネルギー経路選択方法。
【請求項４】
前記新バイパス経路作成ステップにおいて、
前記境界ルータと、前記スタイナーツリーと前記バイパス経路上のすべてのルータとの間に最短経路を求め、求めた最短経路集合の中で最もホップ数が少ない経路が、該スタイナーツリーと該バイパス経路上のリンクを使用しない場合は、当該最短経路を新バイパス経路として作成し、該スタイナーツリーと該バイパス経路上のリンクを使用する場合は、次にホップ数が小さい最短経路を対象にして、この処理を新バイパス経路が必要本数作成されるまで繰り返す
請求項３記載の省エネルギー経路選択方法。
【請求項５】
ひとつのエッジルータをツリーの始点として、他のすべてのエッジルータを終点とするスタイナーツリーをスタイナーツリーアルゴリズムによって求め、該スタイナーツリーに属するリンクとルータを利用してエッジルータ間の経路を選択する省エネルギー経路選択装置であって、
前記バイパス経路作成手段が、前記スタイナーツリー上の２つのルータ間に、該スタイナーツリー上のリンクを利用しないバイパス経路を作成し、そのバイパス経路にスタイナーツリー上の一部の経路のトラフィックを迂回させるバイパス経路作成手段を有する
ことを特徴とする省エネルギー経路選択装置。
【請求項６】
前記バイパス経路作成手段は、
前記スタイナーツリー上のエッジルータ間で、該ツリー上のホップ数が最も大きい区間から順番に、その区間のネットワーク上の最短経路を求め、当該最短経路パスが該スタイナーツリー上のリンクを使用しない場合には当該最短経路をバイパス経路として作成し、該スタイナーツリー上のリンクを最短経路が使用する場合は、次にホップ数が大きい区間で同じ処理を行い、この処理をバイパス経路が作成されるまで繰り返す手段を含む
請求項５記載の省エネルギー経路選択装置。
【請求項７】
前記スタイナーツリーと前記バイパス経路作成ステップで作成された前記バイパス経路が適用されたネットワークドメインの中で他のネットワークドメインとの間の中継を行う境界ルータがある場合は、該境界ルータと、該スタイナーツリーと該バイパス経路上に位置する他ルータとの間に、該スタイナーツリーと該バイパス経路上のリンクを利用しない新バイパス経路を作成し、その新バイパス経路を使ってエッジルータと境界ルータ間の通信を行う新バイパス経路作成手段を更に有する
請求項５または６記載の省エネルギー経路選択装置。
【請求項８】
前記新バイパス経路作成手段は、
前記境界ルータと、前記スタイナーツリーと前記バイパス経路上のすべてのルータとの間に最短経路を求め、求めた最短経路集合の中で最もホップ数が少ない経路が、該スタイナーツリーと該バイパス経路上のリンクを使用しない場合は、当該最短経路を新バイパス経路として作成し、該スタイナーツリーと該バイパス経路上のリンクを使用する場合は、次にホップ数が小さい最短経路を対象にして、この処理を新バイパス経路が必要本数作成されるまで繰り返す手段を含む
請求項７記載の省エネルギー経路選択装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、省エネルギー経路選択方法及び装置に係り、特に、ネットワーク上のルータとリンクをスリープモードにすることにより、当該ネットワークで利用される電力の削減を実現する省エネルギー経路選択方法及び装置に関する。
【背景技術】
【０００２】
IP(Internet Protocol)ネットワークでは、エッジルータから他のエッジルータまでデータが通信される際に、複数のリンクと複数のコアルータを経由する。しかし、エッジルータ間のトラフィックが少ない場合には、トラフィックが通過しないリンクとルータをスリープモードにすることにより使用電力を削減できる。そのため、エッジルータ間のトラフィック要求の変動に合わせて、スリープできるリンクとコアルータを増やすことを可能とする経路選択方法が求められる。
【０００３】
経路選択方法として、ネットワーク上の一つのエッジルータを起点とし、他のエッジルータをツリーの終点としてスタイナーツリーを作成した後、作成されたスタイナーツリー上のルータとリンクのみを使うという条件でエッジルータ間の経路を決定する方法が提案されている（例えば、非特許文献１参照）
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】H. Matsuura, " Steiner Tree Application to Energy Saving Routing," 電子情報通信学会ソサイエティ大会, BS-5-25, 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献1の経路選択方法には以下の問題がある。一つは、スタイナーツリー上のリンクのみを使うので、１リンクあたりの使用帯域が大きくなる場合がある。例えば図１のネットワークにおいて、エッジルータが楕円で示したr1, r2, r6, r7, r11, r15, r18であり、r18を起点として他のすべてのエッジルータまで至るスタイナーツリーの構成リンクが太線で示されている。この例で、r4-r5, r1-r4のリンクに注目した場合、r2, r6, r15側からr1, r7, r11, r18側に届くトラフィックはすべて、これらのリンクを通過することになる。そのため、これらのリンクの負荷が大きくなる問題がある。
【０００６】
もう一つは、エッジルータ間のホップ数が大きくなる可能性があることである。例えば、r15からr11までの経路はr15-r9-r6-r5-r4-r1-r3-r7-r18-r17-r11となり、ホップ数は10となる。ホップ数が大きくなると遅延が大きくなり、通信品質に影響がでる場合がある。
【０００７】
本発明は、上記の点に鑑みなされたもので、スタイナーツリー上のボトルネックリンクの利用帯域を軽減し、エッジルータ間のホップ数が大きい経路を少なくすることが可能な省エネルギー経路選択方法及び装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するため、本発明（請求項１）は、ひとつのエッジルータをツリーの始点として、他のすべてのエッジルータを終点とするスタイナーツリーをスタイナーツリーアルゴリズムによって求め、該スタイナーツリーに属するリンクとルータを利用してエッジルータ間の経路を選択する省エネルギー経路選択方法であって、
バイパス経路作成手段、新バイパス経路作成手段を有する装置において、
前記バイパス経路作成手段が、前記スタイナーツリー上の２つのルータ間に、該スタイナーツリー上のリンクを利用しないバイパス経路を作成し、そのバイパス経路にスタイナーツリー上の一部の経路のトラフィックを迂回させるバイパス経路作成ステップを行うことを特徴とする省エネルギー経路選択方法である。
【０００９】
また、本発明（請求項２）は、請求項１の前記バイパス経路作成ステップにおいて、
前記スタイナーツリー上のエッジルータ間で、該ツリー上のホップ数が最も大きい区間から順番に、その区間のネットワーク上の最短経路を求め、当該最短経路パスが該スタイナーツリー上のリンクを使用しない場合には当該最短経路をバイパス経路として作成し、該スタイナーツリー上のリンクを最短経路が使用する場合は、次にホップ数が大きい区間で同じ処理を行い、この処理をバイパス経路が作成されるまで繰り返す。
【００１０】
また、本発明（請求項３）は、請求項１または２において、前記新バイパス経路作成手段が、前記スタイナーツリーと前記バイパス経路作成ステップで作成された前記バイパス経路が適用されたネットワークドメインの中で他のネットワークドメインとの間の中継を行う境界ルータがある場合は、該境界ルータと、該スタイナーツリーと該バイパス経路上に位置する他ルータとの間に、該スタイナーツリーと該バイパス経路上のリンクを利用しない新バイパス経路を作成し、その新バイパス経路を使ってエッジルータと境界ルータ間の通信を行う新バイパス経路作成ステップを更に行う。
【００１１】
また、本発明（請求項４）は、請求項３の前記新バイパス経路作成ステップにおいて、
前記境界ルータと、前記スタイナーツリーと前記バイパス経路上のすべてのルータとの間に最短経路を求め、求めた最短経路集合の中で最もホップ数が少ない経路が、該スタイナーツリーと該バイパス経路上のリンクを使用しない場合は、当該最短経路を新バイパス経路として作成し、該スタイナーツリーと該バイパス経路上のリンクを使用する場合は、次にホップ数が小さい最短経路を対象にして、この処理を新バイパス経路が必要本数作成されるまで繰り返す。
【発明の効果】
【００１２】
本発明の請求項１により、スタイナーツリー上のボトルネックとなるリンク内のトラフィックをバイパス経路に迂回することができるので、ボトルネックリンクの利用帯域を軽減することができる。
【００１３】
また、本発明の請求項２により、スタイナーツリー上のホップ数の最も大きい経路にとってかわる最短経路がバイパス経路として利用されるので、ホップ数が大きい経路を少なくすることができる。
【００１４】
また、本発明の請求項３、４は、ネットワークドメイン間通信における境界ルータに繋がる経路に集中するトラフィックを新バイパス経路に迂回することを可能にしている。
【図面の簡単な説明】
【００１５】
【図１】スタイナーツリー適用例である。
【図２】本発明の一実施の形態におけるルーティングサーバの構成図である。
【図３】本発明の一実施の形態におけるバイパス経路作成部のフローチャートである。
【図４】本発明の一実施の形態におけるバイパス経路作成例である。
【図５】本発明の一実施の形態における新バイパス経路作成部のフローチャートである。
【図６】本発明の一実施の形態における新バイパス経路作成例である。
【図７】本発明のバイパス経路適用例である。
【図８】評価ネットワークの例である。
【図９】図８の評価ネットワークにおけるバイパス経路効果の評価結果である。
【発明を実施するための形態】
【００１６】
以下、図面と共に本発明の実施の形態を説明する。
【００１７】
以下では、省エネルギー経路選択装置をルーティングサーバで実現させるものとして説明する。
【００１８】
図２は、本発明の一実施の形態におけるルーティングサーバの構成を示す。
【００１９】
ルーティングサーバ１は、Java（登録商標）のプラットフォームであるJBoss (http://www.redhat.com/products/jbossenterprisemiddleware/application-platform)１１とデータベース１２を有する。
【００２０】
Jboss１１はエッジ間省エネルーティングモジュール１１０とネットワーク情報アクセス関数１２０を有し、当該モジュール１１０は、スタイナーツリー作成部１１１、エッジルータ間経路作成部１１２、バイパス経路作成部１１３、新バイパス経路作成部１１４を有する。
【００２１】
データベース１２には、ネットワークトポロジ情報として、リンク情報１２１とルータ情報１２２が格納されている。
【００２２】
スタイナーツリー作成部１１１がネットワーク情報アクセス関数１２０を用いて、データベース１２内のリンク情報１２１とルータ情報１２２からなるネットワーク情報にアクセスする。リンク情報１２１は、対象リンクのupstream/ downstreamのリンクコストを保持する。また、ルータ情報１２２は対象ルータに繋がっているリンクを保持するとともに、対象ルータがエッジルータかどうかの情報を保持する。
【００２３】
スタイナーツリー作成部１１１は、データベース１２から取得したネットワーク情報に基づいて、すべてのエッジルータを通る条件で図１のようなスタイナーツリーをメモリ（図示せず）上に作成する。スタイナーツリーの作成には、スタイナーツリー作成アルゴリズムを用いることが可能である。
【００２４】
エッジルータ間経路作成部１１２は、メモリ（図示せず）上に作成されたスタイナーツリー上のリンクのみを利用するという条件でエッジルータ間の経路を決定する。
【００２５】
バイパス経路作成部１１３と、新バイパス経路作成部１１４が本発明の主要部である。
【００２６】
バイパス経路作成部１１３は、スタイナーツリー作成部１１１で作成されたスタイナーツリー上の２つのルータ間に、スタイナーツリー上のリンクを利用しないバイパス経路を作成する。
【００２７】
新バイパス経路作成部１１４は、スタイナーツリーとバイパス経路作成部１１３で作成されたバイパス経路が適用されたネットワークドメインの中で、他のネットワークドメインとの間の中継を行う境界ルータがある場合は、境界ルータとスタイナーツリーとバイパス経路上のルータとの間にスタイナーツリーとバイパス経路上のリンクを使用しない新バイパス経路を作成する。
【００２８】
上記の構成における処理を以下に示す。
【００２９】
まず、バイパス経路作成部３の処理について説明する。
【００３０】
図３は、本発明の一実施の形態におけるバイパス経路作成部のフローチャートである。
【００３１】
以下では、予めJboss１１のスタイナーツリー作成部１１１において、メモリ（図示せず）上にスタイナーツリーが作成され、エッジルータ間経路作成部１２でエッジルータ間経路が作成されているものとする。
【００３２】
ステップ１）  バイパス経路作成部１１３は、エッジルータ間経路作成部１１２で作成されたエッジルータ間経路を経由ホップ数順にソーティングする。
【００３３】
ステップ２）  ソーティングされた経路集合中で最大ホップ経路の終点間にダイクストラアルゴリズム（http://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95) 等の最短経路探索アルゴリズムで最短経路を求め、これをバイパス経路とする。
【００３４】
ステップ３）  ステップ２で求めた最短経路が、スタイナーツリー作成部１１１で求めたスタイナーツリー上のリンクを利用する（ツリーと交わる）かどうかをチェックする。もしツリーと交わる場合は、ステップ４に移行し、交わらない場合はステップ５に移行する。
【００３５】
ステップ４）  ステップ２で求めた最短経路を経路集合から削除する。ステップ２に戻り、再度経路集合の中の最短ホップ経路を選択する。
【００３６】
ステップ５）ステップ３において、ステップ２で求めた最短経路がツリーと交わらないと判断された場合はステップ５に進み、最短経路をバイパス経路とする。
【００３７】
ステップ６）ステップ５で作成されたバイパス経路の終端ルータから指定されたradius以内のエッジルータを選択し、選択されたエッジルータ間経路でバイパス経路を挟むものは、バイパス経路経由に変更する。ここで、radiusとは、バイパス経路の２つの終端エッジルータからのホップ数を変数として定義したものである。
【００３８】
図４を用いて図３のフローチャートの動作を例示する。
【００３９】
まず、スタイナーツリー作成部１１１で求められたスタイナーツリー上のリンクが太線で示されている。そのスタイナーツリー上において楕円で示されたルータである、r1,r2,r6,r7,r11,r15,r18の７台のエッジルータ間でスタイナーツリー上の経路のみを通る条件で作られた経路集合が、バイパス経路作成部１１３で経路ホップ数順にソーティングされる（ステップ１）。図６のフローの最初のステップ２で経路集合の中で最もホップ数の大きい経路である。r11-r17-r18-r7-r3-r1-r4-r5-r6-r9-r15が選択され、この経路の２つの終端エッジルータ間の最短経路であるr11-r17-r18-r19-r15が選択される（ステップ２）。しかし、ステップ３でこの選択された最短経路上、r11-r17，r17-r18の２つのリンクがスタイナーツリーで使われていると判断され（ステップ３,Yes）、r11-r17-r18-r7-r3-r1-r4-r5-r6-r9-r15が経路集合から削除され、２度目のステップ２に進む(ステップ４)。
【００４０】
２度目のステップ２では、上記の経路集合の中の最もホップ数が大きい経路であるr18-r7-r3-r1-r4-r5-r6-r9-r15が選択され、この経路の２つの終端エッジルータ経路間の最短経路であるr18-r19-r15が選択される。再度のステップ３でこの選択された最短経路がスタイナーツリーと交わらないことをチェックした後に（ステップ３,No）、このr18-r19-r15がバイパス経路として決定される(ステップ５)。
【００４１】
その後、ステップ６の処理に入るが、図４ではradiusは"２"に設定されている。新バイパス経路作成部１１４は、r15あるいはr18からホップ数が２以内のスタイナーツリー上のエッジノードである、r6,r7,r11を選択し、
r15-r19-r18,
r15-r19-r18-r7,
r15-r19-r18-r17-r11,
r6-r9-r15-r19-r18, 
r6-r9-r15-r19-r18-r7, 
r6-r9-r15-r19-r18-r17-r11
の6つの経路が、作成されたバイパス経路経由で作成される。これらの６つの経路は経路の両端のエッジルータ間の両方向のトラフィック通信に利用される。
【００４２】
上記のように、ネットワーク規模に応じてradiusを変化させることにより、バイパス経路で送信するトラフィックのトラフィック量を調整することを可能にしている。
【００４３】
次に、新バイパス経路作成部１１４の処理を説明する。
【００４４】
図５は、本発明の一実施の形態における新バイパス経路作成部のフローチャートである。
【００４５】
ステップ１１）新バイパス経路作成部４は、当該ネットワークドメイン内の境界ルータからスタイナーツリー＋バイパス上の他ルータまでの最短経路をダイクストラアルゴリズム等の最短経路探索アルゴリズムで求め、その最短経路集合を経路の経由ホップ数でソーティングする。
【００４６】
ステップ１２）ステップ１１で作成した最短経路集合の中で最小経由ホップ数を持つ経路を選択する。
【００４７】
ステップ１３）ステップ１２で選択された経路がスタイナーツリー上あるいはバイパス経路作成部１１３で作成したバイパス上のリンクを使う（スタイナーツリー＋バイパスと交わる）かどうかをチェックする。もし、交わる場合はステップ１４に移行し、もし、ステップ３でスタイナーツリー＋バイパスと交わらない場合は、ステップ１５に移行する。
【００４８】
ステップ１４）  当該最短経路を最短経路集合から削除し、再度ステップ１２の処理を行う。
【００４９】
ステップ１５）ステップ１２選択された当該最短経路を新バイパス経路として新バイパス経路集合に加える。
【００５０】
ステップ１６）新バイパス経路数が要求された数だけ存在するかどうかを判断し、要求数に満たない場合はステップ１４に進み、ステップ１２で選択された最小ホップ経路を最短経路集合から削除し、再度ステップ１２に進む。ステップ１６で新バイパス経路数が要求数に達した場合は、ステップ１７に進む。
【００５１】
ステップ１７）新バイパス経路の境界ルータ以外の終端ルータからradius以内のエッジルータをすべて選択して、それらのエッジルータと境界ルータ間の経路を新バイパス経路を通る経路で再設定する。
【００５２】
図６に、図５の具体的なバイパス経路作成例を示す。ここで、太線で示されたリンクは、スタイナーツリー作成部１１１で作成されたスタイナーツリー上のリンクであり、太い鎖線は、バイパス経路作成部１１３で作成されたバイパス経路上のリンクである。また、境界ルータはr13であり、境界ルータからの新バイパス経路の要求数は３であるとする。また、radiusは３と設定する。
【００５３】
まず、新バイパス経路作成部１１４は、r13からスタイナーツリー＋バイパス上のすべてのルータ（r1,r2,r3,r4,r5,r6,r7,r9,r11,r15,r17,r18,r19）までの最短経路を求め、その１３の経路を経由ホップ数でソーティングして最短経路集合に格納する（ステップ１１）。最短経由ホップ数１を持つr13-r18が選択されたとする（ステップ１２）。この選択された経路がスタイナーツリー＋バイパス経路と交わらないことが確認できるので（ステップ１３、No）、r13-r18は新バイパス経路集合に加えられる(ステップ１５)。新バイパス経路数がまだ１であり、要求数の３に達しないと判断されるので（ステップ１６、No）、経由ホップ数でソーティングされた最短経路集合からr13-r18を削除した後、２度目のステップ１２に進む（ステップ１４）。
【００５４】
２度目のステップ１２では、もう一つの最短経由ホップ数１を持つr13-r9が選択される。この選択された経路がスタイナーツリー＋バイパス経路と交わらないことが確認できるので（ステップ１３,No）、r13-r9は新バイパス経路集合に加えられる(ステップ１５)。新バイパス経路数がまだ２であり、要求数の３に達しないと判断されるので（ステップ１６,No）、経由ホップ数でソーティングされた最短経路集合からr13-r9を削除した後（ステップ１４）、３度目のステップ１２に進む。
【００５５】
３度目のステップ１２では、複数の経由ホップ数が２の経路が存在するが、r13-r9-r6が選択されたとする。この際、リンクr9-r6がスタイナーツリーと交わることが判明するので（ステップ１３,Yes）、r13-r9-r6が経路ホップ数でソーティングされた最短経路集合から削除され、再度ステップ１２に戻る（ステップ１４）。この４度目のステップ１２では経由ホップ数が２のr13-r10-r7が選択されたとする。この場合、この経路がスタイナーツリー＋バイパス経路と交わらないことが判断できるので（ステップ１３,No）、r13-r10-r7が新バイパス経路集合に追加される（ステップ１５）。この時点で新バイパス経路集合には経路数が３となり要求数を満たすので（ステップ１６,Yes）、ステップ１７に進むことになる。
【００５６】
図６の点線で示されたr13-r18, r13-r9, r13-r10-r7の３つの新バイパス経路を経由して境界ルータと通信する経路を決定する（ステップ１７）。これらの新バイパス経路の境界ルータr13以外の終端ルータはそれぞれr18, r9, r7になる。Radiusは"３"に設定されているので、まずr18から３経由ホップ以内のスタイナーツリー＋バイパス上のエッジルータを特定する。この条件ではr11,r15が当てはまる。r7,r1もr18からの距離が３経由ホップ以内ではあるが、r7が他の新バイパス経路の終端になっているので、これらのr7を通らないとたどり着かないエッジルータは対象外とする。よって、新バイパス経路r13-r18を利用する経路はこの経路に加えて、
r13-r18-r17-r11,
r13-r18-r19-r15
の合計３経路となる。これらの経路は経路の２つの終端ルータ間の両方向のトラフィックの送信のために利用される。
【００５７】
r9からの経由ホップ数が３以内でまだ選択されていないエッジルータはr6,r2である。そのため、経路r13-r9-r6、r13-r9-r6-r5-r2の合計２経路が新バイパス経路r13-r9を利用する経路として設定され、境界ルータとエッジルータ間のトラフィック送信に利用される。
【００５８】
r7からの経由ホップ数が３以内でまだ選択されていないエッジルータはr1である。そのため、経路r13-r10-r7とr13-r10-r7-r3-r1が新バイパス経路r13-r10-r7を利用する経路として設定され、境界ルータとエッジルータ間のトラフィック通信に利用される。
【００５９】
上記のように、ネットワーク規模に応じてradiusと新バイパス数を変化させることにより、新バイパス経路で送信するトラフィックのトラフィック量を調整することを可能にしている。
【００６０】
以下に、従来技術と本発明の比較を示す。
【００６１】
図７は、図１のスタイナーツリーにバイパスを張る例を示している。この太鎖線のバイパスr15-r19-r18を張り、スタイナーツリー上のトラフィックの一部をバイパスに回すことにより、負荷分散が図られる。
【００６２】
図８の評価ネットワークでバイパスの効果を評価した結果が図９である。図８において、楕円で示されているr1, r2, r6, r7, r11, r15, r18は、エッジルータであるが、点線で囲まれたr3, r4, r5, r8, r9, r17, r19はその後１台ずつエッジルータとして加えられた。また、各リンク上の2k, 4k, はそれぞれ、リンク帯域が2000, 4000を両方向でもつリンクであることを示す。また、他のリンクは1000のリンク帯域を両方向で保持する。リンクのコストは、upstreamとdownstream毎に割り当てられ、そのリンクコストはリンク帯域の逆数とした。
【００６３】
図９において、SPTは、OSPFのSPT (shortest path tree)を用いたルーティングの結果を示し、Steinerはスタイナーツリーを用いた場合の結果を示し、Steiner(r:2)はバイパスを使った結果を示している。図８に示すようにすべてのエッジルータのケースにおいてバイパスはr15-r19-r18を利用した。また、(r:2)はradiusが2であることを示し、r15から2ホップ以内とr18から2ホップ以内のエッジルータはお互いの間の通信においてバイパスを利用することを示す。
【００６４】
図９(a), (b)から、バイパスを利用した場合、スタイナーツリーのみを利用した場合に比較して、スリープできるルータ数は最大１台、スリープできるリンク数は最大２本減るが、SPTに比較すると大幅にスリープできるルータとリンク数は大きいことがわかる。また、図９(c)のエッジルータ間の経路の平均ホップ数は、スタイナーツリーのみを利用した場合よりも少なくなっている。特に図９(d)の最大利用リンク帯域（ネットワーク上で最も利用帯域が大きいリンクの帯域）はバイパスを使うと大幅に改良され、SPTと同程度まで落ちる場合が多々あることがわかる。
【００６５】
前述の図２のスタイナーツリー作成部１１１、エッジルータ間経路作成部１１２、バイパス経路作成部１１３、新バイパス経路作成部１１４の動作をプログラムとして構築し、省エネルギー経路選択装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００６６】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００６７】
１  ルーティングサーバ
１１  Java（登録商標）プラットフォーム（Jboss）
１２  データベース
１１０  エッジ間省エネルーティングモジュール
１１１  スタイナーツリー作成部
１１２  エッジルータ間経路作成部
１１３  バイパス経路作成部
１１４  新バイパス経路作成部
１２１  リンク情報
１２２  ルータ情報
【図１】
2014086898.tif 000003
【図２】
2014086898.tif 000004
【図３】
2014086898.tif 000005
【図４】
2014086898.tif 000006
【図５】
2014086898.tif 000007
【図６】
2014086898.tif 000008
【図７】
2014086898.tif 000009
【図８】
2014086898.tif 000010
【図９】
2014086898.tif 000011