(57)【要約】【課題】トラヒック需要の変動に対するネットワークの耐性を、ネットワークトポロジの多様性を指標として評価するネットワーク設計方法及びシステムを提供する。【解決手段】ネットワーク管理部１０は、監視対象のネットワークのトポロジを管理する。ネットワーク監視部２０は、監視対象ネットワークについてリンク毎のトラヒック流量、ノード毎のトラヒック流量およびノード毎の回線負荷等を測定し、その結果に基づいて障害箇所を検知する。追加候補箇所選択部３０は、ノードやリンクの輻輳、切断といった障害またはその可能性が報告されると、当該障害箇所に対する迂回経路を新規構築または増強できるノードおよび／またはリンクの追加候補箇所を複数選択する。追加箇所決定部４０は、各候補箇所にノードおよび／またはリンクを追加した際のネットワークの多様性を相互情報量に基づいて判断し、相互情報量が最小となる候補箇所を追加箇所に決定する。【選択図】図１
2015130551.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークトポロジをノードおよび／またはリンクの追加により変更するネットワーク設計システムにおいて、
ネットワークトポロジを取得する手段と、
ノードおよび／またはリンクの追加候補箇所ごとにネットワークトポロジの多様性を評価する手段と、
複数の追加候補箇所の中からネットワークトポロジの多様性に基づいて追加箇所を決定する手段とを具備したことを特徴とするネットワーク設計システム。
【請求項２】
前記追加箇所を決定する手段は、ネットワークトポロジの多様性がより高くなる追加候補箇所を追加箇所に決定することを特徴とする請求項１に記載のネットワーク設計システム。
【請求項３】
前記追加箇所を決定する手段は、ネットワークトポロジの多様性を当該ネットワークトポロジの相互情報量で代表することを特徴とする請求項１または２に記載のネットワーク設計システム。
【請求項４】
前記追加箇所を決定する手段は、ノードおよび／またはリンクの追加によりネットワークトポロジの相互情報量が最小となる追加候補箇所を追加箇所に決定することを特徴とする請求項３に記載のネットワーク設計システム。
【請求項５】
前記追加箇所を決定する手段は、各追加候補箇所にノードおよび／またはリンクを追加した時の接続先ノードの次数の相互情報量に基づいて追加箇所を決定することを特徴とする請求項４に記載のネットワーク設計システム。
【請求項６】
ネットワークのトラヒック変動を監視する手段と、
前記トラヒック変動の監視結果に基づいて、ノードおよび／またはリンクの追加候補箇所を選択する手段とを具備したことを特徴とする請求項１ないし５のいずれかに記載のネットワーク設計システム。
【請求項７】
前記追加候補箇所を選択する手段は、前記トラヒック変動を監視する手段により検知された障害箇所を通過するフローが、ノードおよび／またはリンクの追加により当該障害箇所よりも前ホップにおいて他の経路に迂回できる追加候補箇所を選択することを特徴とする請求項６に記載のネットワーク設計システム。
【請求項８】
ネットワークトポロジをノードおよび／またはリンクの追加により変更するネットワーク設計方法において、
ネットワークトポロジを取得する手順と、
ノードおよび／またはリンクの追加候補箇所ごとにネットワークトポロジの多様性を評価する手順と、
複数の追加候補箇所の中からネットワークトポロジの多様性に基づいてノード追加箇所を決定する手順とを含むことを特徴とするネットワーク設計方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク設計方法及びシステムに係り、特に、トラヒック需要の変動に対するネットワークの耐性を、ネットワークトポロジの多様性を指標として評価するネットワーク設計方法及びシステムに関する。
【背景技術】
【０００２】
非特許文献１には、相互情報量が相対的に高いネットワーク(AT&T 0.3)と低いネットワーク(AT&T original)とを用意して各ネットワークにトラヒック需要を模擬し、トラヒック量を増やした際の設備の増設量を比較した結果から、トラヒック需要の変動に対するネットワークの耐性は、残存次数のエントロピーを確率変数とする相互情報量で代表できることが研究報告されている。
【０００３】
特許文献１には、高効率な障害復旧方式を実現する通信網の設計方法が開示されている。特許文献２には、ノード間の通信路を多重化しながら、経済的な通信網を設計する方法が開示されている。特許文献３には、既存のトポロジから、接続要件を満たす、かつ、リンクコスト最小のトポロジを生成し、逐次的に適切なトポロジ、すなわち通信網を設計する方法が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開2003-244201号公報
【特許文献２】特開2003-16121号公報
【特許文献３】特開2010-206581号公報
【非特許文献】
【０００５】
【非特許文献１】信学技報, vol. 112, no. 392, NS2012-157, pp. 93-98, 2013年1月「残存次数の相互情報量にもとづくトポロジー構造の多様性が設備増設量に与える影響の評価」
【発明の概要】
【発明が解決しようとする課題】
【０００６】
特許文献１，２に開示されたネットワーク設計方法は、比較的小規模、例えば数十〜百ノード程度のネットワークを対象とした設計方法である。加えて、単一ノードの障害や予め想定したトラヒックの需要増など、想定した変化に対して適用するネットワーク設計方法である。
【０００７】
特許文献３では、所望のトポロジを生成するにいたるまでに、複数回の異なるトポロジを計算したり、また設計のために予め複数のパラメータを設定したりする必要がある。これらパラメータの最適設定は事前の計算や主観的な設定が必要となる。さらに、一般的に現状において通信事業者等で従来利用されているネットワーク設計方式は、必ずしも大規模ネットワークに適しているものではない。
【０００８】
例えば、ノード間のトラヒック量などの通信状況に関する情報（制御情報）を集約し、最適化問題を解いてルータ配置やルータ間の通信容量を設計する方法では、ノード規模が大きくなると計算時間が爆発する。また、大規模ネットワークでは通信状況に関する情報を集めること自体が困難、高負荷である。
【０００９】
そもそも最適性は、通信状況が固定ないしは想定される範囲内の変化を前提とした時にのみ確保されるものであり、ネットワーク状況が時々刻々と変化し、将来のトラヒック需要の変動が予期できない中で、最適性を目指した設計方式には限界ある。このため、現在ではヒューリスティック＋over-provisioningといった場当たり的な設備増強手法が採用され、急伸的なサービスによるトラヒック増加や、想定しない故障などへの対処が困難であった。また、性能指標の最適化に基づく設計では、設計時の環境下では良くても、環境が変化すると適正が低下してしまうという問題がある。
【００１０】
本発明の目的は、上記の技術課題を解決し、ノード規模の大きなネットワークへの対応が容易であり、ネットワーク環境の変化にかかわらず最適なネットワーク設計を可能にするネットワーク設計方法及びシステムを提供することにある。
【課題を解決するための手段】
【００１１】
上記の目的を達成するために、本発明は、ネットワークトポロジをノードおよび／またはリンクの追加により変更するネットワーク設計システムにおいて、以下の構成を具備した点に特徴がある。
【００１２】
(1) ネットワークトポロジを取得する手段と、ノードおよび／またはリンクの追加候補箇所ごとにネットワークトポロジの多様性を評価する手段と、追加候補箇所の中からネットワークトポロジの多様性に基づいて追加箇所を決定する手段とを具備した。
【００１３】
(2) 追加箇所を決定する手段は、ネットワークトポロジの多様性を相互情報量で代表し、相互情報量が最小となる追加候補箇所を追加箇所に決定するようにした。
【００１４】
(3) 追加箇所を決定する手段は、各追加候補箇所にノードおよび／またはリンクを追加した時の接続先ノードの次数の相互情報量に基づいて追加箇所を決定するようにした。
【００１５】
(4) ネットワークのトラヒック変動を監視する手段と、トラヒック変動の監視結果に基づいて、ノードおよび／またはリンクの追加候補箇所を選択する手段とを具備した。
【００１６】
(5) 追加候補箇所を選択する手段は、トラヒック変動を監視する手段により検知された障害箇所を通過するフローが、ノードおよび／またはリンクの追加により当該障害箇所よりも前ホップにおいて他の経路に迂回できる追加候補箇所を選択するようにした。
【発明の効果】
【００１７】
発明によれば、以下のような効果が達成される。
(1) ネットワークへノードやリンクを追加してトポロジを変更する際に、ネットワークトポロジの多様性に基づいて追加箇所が決定されるので、ノード追加やリンク追加の影響を広く波及させてトラヒックを広範囲に分散させることができ、その結果、トラヒック変動に対する耐性が高いネットワークトポロジを獲得できるようになる。
【００１８】
(2) ネットワークトポロジの多様性が相互情報量に基づいて定量的に評価されるので、ネットワークトポロジの多様性が高くなる追加箇所を正確に決定できるようになる。
【００１９】
(3) トラヒックの監視結果に基づいて、トラヒック変動後の需要トラヒックを収容できる追加候補箇所が選択されるようにしたので、トラヒック変動に対する耐性の獲得のみならず、トラヒック変動後の需要トラヒックも収容できるようになる。
【００２０】
(4) ネットワークのトポロジさえ取得できれば追加箇所を決定できるので、大規模ネットワークへも容易に適用できる。また、ネットワークトポロジは短時間で変動するものではないので、追加箇所をオンラインかつリアルタイムで決定できるようになる。
【図面の簡単な説明】
【００２１】
【図１】本発明の一実施形態に係るネットワーク設計システムの構成を示した図である。
【図２】ノードやリンクの追加候補箇所の選択例を示した図（その１）である。
【図３】ノードやリンクの追加候補箇所の選択例を示した図（その２）である。
【図４】追加箇所決定部の機能ブロック図である。
【図５】追加次数を説明するための図である。
【発明を実施するための形態】
【００２２】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明の一実施形態に係るネットワーク設計システムの主要部の構成を示したブロック図であり、汎用のコンピュータやサーバに各機能を実現するアプリケーション（プログラム）を実装して構成しても良いし、あるいはアプリケーションの一部がハードウェア化またはROM化された専用機や単能機として構成しても良い。
【００２３】
ネットワーク管理部１０は、監視対象のネットワークのトポロジを管理する。ネットワーク監視部２０は、監視対象ネットワークについてリンク毎のトラヒック流量、ノード毎のトラヒック流量およびノード毎の回線負荷等を測定し、輻輳や障害の有無、箇所をノード単位、リンク単位で検知する。
【００２４】
なお、前記ネットワークのトポロジ、リンク毎およびノード毎のトラヒック流量などは、通常のネットワーク運用に必要不可欠な情報であり、別途に監視されている場合には、その監視データを取得して利用するようにしても良い。
【００２５】
追加候補箇所選択部３０は、ノードやリンクの輻輳、切断といった障害またはその可能性、あるいは将来のトラヒック需要予測などが前記ネットワーク監視部２から報告されると、当該障害箇所に対する迂回経路を新規構築または増強できるノード追加および／またはリンク追加の候補箇所を複数選択する。
【００２６】
このとき、ノードやリンクに障害が発生してフローが途切れた場合には、フロー確保を条件にノード追加やリンク追加の候補箇所が選択される。また、輻輳やトラヒック需要増への対応であれば、追加されるノードやリンクの能力に基づいて、需要トラヒックが満たされることを条件に複数の追加候補箇所が選択される。
【００２７】
図２は、前記追加候補箇所選択部３０によるノード追加の候補箇所の選択例を示した図であり、同図(a)のネットワークトポロジにおいて、ノードN2，N3間のリンクL23に輻輳や障害が発生し、これが前記ネットワーク監視部２０により検知されると、当該リンクを迂回する経路、補強する経路を確保するために、ノードN2，N3を中継するノードN6[同図(b)]が候補箇所として選択される。
【００２８】
また、監視対象がフロー管理の可能なネットワークであって、エンド／エンドのトラヒックフローを管理できるならば、ノードN1，N3を中継するノードN7[同図(c)]のように、障害箇所を含む複数のノードや経路を迂回する箇所が候補箇所として選択されるようにしても良い。
【００２９】
さらに、フロー管理の可能なネットワークであれば、障害箇所を通過するフローがその数ホップ前に通過するリンクやノードを判別できる。したがって、このような環境下では上記のように障害箇所やその周辺にノードを追加してトポロジを変更するのではなく、図３(a)に示した追加ノードN8のように、障害箇所の数ホップ前のトポロジを変更することでフローを障害箇所から予め遠ざけられる箇所が選択されるようにしても良い。
【００３０】
図３(b)，(c)は、前記図２(b)，(c)に示したノード追加に代えてリンク追加する場合の候補箇所の選択例を示している。また、図示は省略するが、ノードおよびリンクの双方が追加されるようにしても良い。
【００３１】
追加箇所決定部４０は、前記選択された各候補箇所にノードやリンクを追加した際のネットワークの多様性を相互情報量に基づいて判断し、相互情報量が最小となる１ないし複数の候補箇所をノードやリンクの追加箇所に決定する。
【００３２】
図４は、前記追加箇所決定部４０の機能ブロック図であり、本実施形態では、トラヒック需要の変動に対するネットワークの耐性がネットワークトポロジの多様性で代表される。ネットワークの耐性とは、トラヒック需要が増えた時に、これが一部のノードやリンクに集中せず、より広範なノードやリンクに分散できる性質を意味する。
【００３３】
そして、ネットワークトポロジの多様性を、ノード追加やリンク追加によるエントロピーを変数とする相互情報量を指標として評価することにより、トラヒック需要の変動に対する耐性の高いネットワークを獲得できる追加箇所を前記候補箇所の中から決定する。
【００３４】
ここでは初めに、ネットワークトポロジの多様性と相互情報量との関係について説明し、その後、追加箇所決定部４０の機能について説明する。
【００３５】
相互情報量とは、２つの確率変数ｘ，ｙがあったときに、yの値を知った時のｘの「不確かさの減少分」、すなわち「情報量の増加分」と定義される。したがって、これをネットワークトポロジの変更に当てはめれば、「相互情報量Iが大きい」とは、yの値を知ることでxの不確かさが大きく減少すること、換言すればトポロジの構造に多様性がないことを意味する。また、「相互情報量Iが小さい」とは、yの値を知ることでxの不確かさが少しだけ減少すること、換言すればトポロジの構造に多様性があることを意味する。
【００３６】
そこで、本発明では相互情報量を、トポロジの構造の一部（yに相当）を知ることで得られる残りのトポロジの構造(xに相当)の情報量と見立てることで、トポロジが有する構造の多様性を定量的に測るようにした。
【００３７】
追加次数分布計算部４１は、ノードやリンクの追加候補箇所ごとに、当該箇所にノードやリンクを接続したときの次数分布、すなわち追加次数分布q(k)を算出する。本実施形態では、各ノードに接続されたリンク数が「次数」であり、図５に示したように、ネットワーク上の各候補箇所にノード（あるいはリンク）を追加したときに当該追加ノード（あるいはリンク）と接続される隣接ノードの次数が「追加次数」となる。
【００３８】
追加次数分布q(k)は、次数分布P（P1，P2…，PK）を用いて次式(1)で表される。ただし、符号P1はリンク数が「１」のノード総数、符号P２はリンク数が「２」のノード総数…、符号Kは最大次数であり、いずれもネットワークトポロジから求められる。
【００３９】
【数１】
2015130551.tif 000003
【００４０】
相互情報量算出部４２は、追加次数の相互情報量I(q)を算出する。相互情報量I(q)は、追加数分布q=(q(1),…，q(i)，…q(K))を用いて次式(2)で表される。
【００４１】
【数２】
2015130551.tif 000004
【００４２】
上式(2)における右辺第１項のH(q)は追加次数のエントロピーを表しており、追加次数分布q(k)を用いて次式(3)で表される。このエントロピーH(q)は、リンクの接続先のノード次数の多様性を計っており、ノード次数が多様になればなるほどH(q)は大きくなる。
【００４３】
【数３】
2015130551.tif 000005
【００４４】
上式(2)における右辺第２項のHcは、追加次数の条件付きエントロピーであり、次式(4)で表される。ただし、π(k｜k')は、追加次数k'を持つノードと接続されている追加次数がkである条件付き確率である。
【００４５】
【数４】
2015130551.tif 000006
【００４６】
追加箇所選択部４３は、ノードやリンクの追加候補箇所ごとに求められた相互情報量Iを比較し、最小の相互情報量Iを与える追加候補箇所を追加箇所として選択する。
【００４７】
なお、上記の実施形態では、ネットワーク監視部２０により検知された障害箇所近傍または関連箇所に複数の追加候補箇所を予め設定し、当該追加候補箇所の中から追加箇所が決定されるものとして説明した。
【００４８】
しかしながら、本発明はこれのみに限定されるものではなく、ネットワークのトラヒック状況とは無関係に、既存のネットワークトポロジを将来のトラヒック需要予測に合わせて拡張する際のノードやリンクの追加箇所の決定にも利用できる。この場合、全ての追加可能箇所を追加候補箇所として評価し、相互情報量の小さくなる上位N箇所が追加箇所として決定されるようにしても良い。
【符号の説明】
【００４９】
１０…ネットワーク管理部，２０…ネットワーク監視部，３０…追加候補箇所選択部，４０…追加箇所決定部，４１…追加次数分布計算部，４２…相互情報量算出部，４３…追加箇所選択部
【図１】
2015130551.tif 000007
【図２】
2015130551.tif 000008
【図３】
2015130551.tif 000009
【図４】
2015130551.tif 000010
【図５】
2015130551.tif 000011