JP5015853B2

JP5015853B2 - 通信帯域算出方法および装置

Info

Publication number: JP5015853B2
Application number: JP2008110343A
Authority: JP
Inventors: 雅之辻野
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: Nippon Telegraph and Telephone Corp
Priority date: 2008-04-21
Filing date: 2008-04-21
Publication date: 2012-08-29
Anticipated expiration: 2028-04-21
Also published as: JP2009260890A

Description

本発明は、通信技術に関し、特に将来必要となる通信帯域を算出する技術に関する。

通信網を管理する上で、ノードペアを結ぶ任意の通信リンクについて、将来におけるトラヒックの充足性を担保するのに必要な通信帯域を正確に算出する技術が必要となる。
将来必要となる通信帯域を算出する場合、その算出結果に対する正確性の観点から、障害のない通常時に選択される現用パスだけでなく、障害時に選択される迂回用パスのトラヒックも考慮することが必要となる。また、通信網において、トラヒックを転送する現用パスおよび迂回用パスの情報が与えられており、障害がない状況で現用パスを流れるトラヒックが、通信リンクにおいて観測されているが、個々のSource-Destinationノードペアで流れるトラヒックが分からない場合も多い。

通信パスの通信帯域を算出する技術として、リング型ネットワークにおいて、逆方向に流れるトラヒックの通信リンクでの最大値を想定するなど、自明な解を用いてトラヒックの上限値を導出する方法がある。しかしながら、この方法で得られる解は、単に、現用パスで必要となる通信帯域の上限を求めるものであり、障害時に選択される迂回用パスによるトラヒックが考慮されていない。また、ケースによっては、過剰な量の帯域を算出する場合もある。

従来、個々のSource-Destinationノードペアに流れるトラヒックを推定する技術として、通信リンクを流れるトラヒックの情報に基づき、Source-Destinationノードペアの交流トラヒックを推定するNetwork Tomographyという方法が提案されている（例えば、非特許文献１など参照）。したがって、このNetwork Tomographyにより推定された交流トラヒックを利用して、迂回用パスのトラヒックを考慮した通信帯域を求める方法も考えられる。

Rui Castro 他, "Network Tomography: Recent Development", Statistical Science, Vo1.19, No.3, pp.499-517 (2004) 今野浩, "線形計画法", 目科技連出版社 (1987)

しかしながら、このようなNetwork Tomographyにより求められる交流トラヒックは、過去の大量の情報に基づく最尤推定を用いて求めたものであり、必要帯域の上限値を保証するものではない。したがって、求めた交流トラヒックをそのまま、将来必要となる通信帯域の上限値として用いることができないという問題点があった。
本発明はこのような課題を解決するためのものであり、個々のノードペアに流れるトラヒックが分からない場合でも、迂回用パスのトラヒックを考慮した通信帯域上限値を算出することができる通信帯域算出方法および装置を提供することを目的としている。

このような目的を達成するために、本発明にかかる通信帯域算出方法は、複数のノードと、これらノードからなるノードペアを結ぶ複数の通信リンクとからなる通信網について、当該通信網上の任意の対象通信リンクにおける通信帯域上限値を算出する通信帯域算出装置で用いられる通信帯域算出方法であって、データ取得部が、各ノードペアで用いる現用パスおよび迂回用パスが経由する通信リンクを示すパス情報と、対象通信リンクを経由する現用パスから発生したトラヒックの観測トラヒック量を示すトラヒック情報とを取得して、記憶部に保存するデータ取得ステップと、通信帯域算出部が、パス情報とトラヒック情報とを参照して、対象通信リンクの観測トラヒック量と、当該対象通信リンクを経由する現用パスにおけるトラヒック需要との関係に基づいて、当該対象通信リンクの観測トラヒック量に関する観測トラヒック量制約条件を生成する観測トラヒック量制約条件生成ステップと、通信帯域算出部が、パス情報を参照して、各ノードペアにおけるトラヒック需要に関するトラヒック需要制約条件を生成するトラヒック需要制約条件生成ステップと、通信帯域算出部が、パス情報を参照して、対象通信リンクを経由する現用パスおよび迂回用パスにおけるトラヒック需要に基づいて、当該対象通信リンクのトラヒック量に関する目的関数を生成する目的関数生成ステップと、通信帯域算出部が、観測トラヒック量制約条件およびトラヒック需要制約条件が成立する場合における目的関数の最大値を通信帯域上限値として算出する目的関数最大値算出ステップとを備えている。

この際、通信網内の通信リンクの集合をＡ、対象通信リンクをａ、ａの観測トラヒック量をＣａ、トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄ、ｄの現用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｙｄ^aとした場合、観測トラヒック量制約条件として、Σ_d∈DＸｄ・ｙｄ^a＝Ｃａ，ｆｏｒａ∈Ａを用いてもよい。

また、トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄとした場合、トラヒック需要制約条件として、Ｘｄ≧０，ｆｏｒｄ∈Ｄを用いてもよい。

また、通信網内の通信リンクの集合をＡ、対象通信リンクをａ、トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄ、ｄの現用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｙｄ^a、ｄの迂回用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｚｄ^aとした場合、目的関数として、Σ_d∈DＸｄ・（ｙｄ^a＋ｚｄ^a）を用いでもよい。

また、本発明にかかる通信帯域算出装置は、複数のノードと、これらノードからなるノードペアを結ぶ複数の通信リンクとからなる通信網について、当該通信網上の任意の対象通信リンクにおける通信帯域上限値を算出する通信帯域算出装置であって、各ノードペアで用いる現用パスおよび迂回用パスが経由する通信リンクを示すパス情報と、対象通信リンクを経由する現用パスから発生したトラヒックの観測トラヒック量を示すトラヒック情報とを取得して、記憶部に保存するデータ取得部と、パス情報とトラヒック情報とを参照して、対象通信リンクの観測トラヒック量と、当該対象通信リンクを経由する現用パスにおけるトラヒック需要との関係に基づいて、当該対象通信リンクの観測トラヒック量に関する観測トラヒック量制約条件を生成し、パス情報を参照して、各ノードペアにおけるトラヒック需要に関するトラヒック需要制約条件を生成するトラヒック需要制約条件生成ステップと、通信帯域算出部が、パス情報を参照して、対象通信リンクを経由する現用パスおよび迂回用パスにおけるトラヒック需要に基づいて、当該対象通信リンクのトラヒック量に関する目的関数を生成し、観測トラヒック量制約条件およびトラヒック需要制約条件が成立する場合における目的関数の最大値を通信帯域上限値として算出する通信帯域算出部とを備えている。

また、通信網内の通信リンクの集合をＡ、対象通信リンクをａ、トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄ、ｄの現用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｙｄ^a、ｄの迂回用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｚｄ^aとした場合、目的関数として、Σ_d∈DＸｄ・（ｙｄ^a＋ｚｄ^a）を用いてもよい。

本発明によれば、個々のノードペアに流れるトラヒックが分からない場合でも、迂回用パスのトラヒックを考慮した、より正確な通信帯域上限値を算出することができる。

次に、本発明の実施の形態について図面を参照して説明する。
まず、図１を参照して、本発明の一実施の形態にかかる通信帯域算出装置について説明する。図１は、本発明の一実施の形態にかかる通信帯域算出装置の構成を示すブロック図である。

図１において、通信網５０は、複数のノードと、これらノードからなるノードペアを結ぶ複数の通信リンクとからなるネットワークである。
オペレーションシステム（以下、ＯＳという）１０は、サーバ装置などの情報処理装置からなり、通信網５０内のノードから、ネットワークトポロジー情報や、各通信リンクのトラヒック量および各通信リンクでの障害有無の時系列情報などの各種ネットワーク情報をネットワークデータ管理部１１により収集して、ネットワーク情報データベース（以下、ネットワーク情報ＤＢという）１２に保存し、通信帯域算出装置２０からの要求に応じて、ネットワークデータ管理部１１により、ネットワーク情報ＤＢ１２内の任意のネットワーク情報を提供する機能を有している。

通信帯域算出装置２０は、サーバ装置などの情報通信装置からなり、ＯＳ１０や管理端末３０とデータ通信を行う機能と、管理端末３０からの指示に応じて、ＯＳ１０から取得した各種情報に基づき、通信網５０上の任意の対象通信リンクで必要とされる通信帯域、すなわち通信帯域上限値を算出する機能とを有している。
管理端末３０は、ネットワーク運用者や設計者が用いるＰＣ端末などの情報処理装置からなり、制御部３１により、通信帯域算出装置２０に対して通信帯域の算出を指示するとともに、算出結果として得られた通信帯域を表示部３２により画面表示し、あるいは算出結果として得られた通信帯域を用いた、通信網５０の運用管理処理やネットワーク設計処理を行う機能を有している。

本実施の形態は、通信網５０を構成するノードペアで用いる現用パスおよび迂回用パスが経由する通信リンクを示すパス情報と、対象通信リンクを経由する現用パスから発生したトラヒックの観測トラヒック量を示すトラヒック情報とをＯＳ１０から取得して、対象通信リンクの観測トラヒック量に関する観測トラヒック量制約条件と、各ノードペアにおける未知のトラヒック需要に関するトラヒック需要制約条件とを生成するとともに、当該対象通信リンクのトラヒック量に関する目的関数を生成し、これら観測トラヒック量制約条件およびトラヒック需要制約条件が成立する場合における目的関数の最大値を、対象通信リンクの通信帯域上限値として算出する。

［本実施の形態の構成］
次に、図１を参照して、本発明の一実施の形態にかかる通信帯域算出装置の構成について説明する。
この通信帯域算出装置２０には、主な機能部として、データ取得部２１、パス情報データベース（以下、パス情報ＤＢという）２１、トラヒック情報データベース（以下、トラヒック情報ＤＢという）２２、および通信帯域算出部２４が設けられている。

データ取得部２１は、定期的あるいは通信帯域算出部２４からの指示に応じて、通信網５０に関するネットワーク情報ＤＢ１２のうち、各ノードペアで用いる現用パスおよび迂回用パスが経由する通信リンクを示すパス情報と、対象通信リンクを経由する現用パスから発生したトラヒックの観測トラヒック量を示すトラヒック情報とを取得して、それぞれパス情報ＤＢ２２およびトラヒック情報ＤＢ２３へ保存する機能を有している。

図２は、通信網の一部構成を示す説明図である。ここでは、通信網５０の一部構成として、ノードＡ（ｎ１）、ノードＢ（ｎ２）、およびノードＣ（ｎ３）と、ノードＡＢ間を結ぶ通信リンクａ１、ノードＡＣ間を結ぶ通信リンクａ２、およびノードＢＣ間を結ぶ通信リンクａ３が示されている。
通信リンクａ１〜ａ３には、ノードペアのデータ通信に用いる通信パスとして、障害のない通常時に選択される現用パスや、障害時に選択される迂回用パスを複数重畳することが可能である。図２の例では、通信パスａ１に、ノードＡＢ間の現用パスｐ１２とノードＡＣ間の迂回用パスｑ１３が重畳されている。また、通信パスａ２には、ノードＡＣ間の現用パスｐ１３とノードＡＢ間の迂回用パスｑ１２が重畳されており、通信パスａ３には、ノードＡＢ間の迂回用パスｑ１２とノードＡＣ間の迂回パスｐ１３が重畳されている。

パス情報ＤＢ２２は、データ取得部２１によりＯＳ１０から取得したパス情報を記憶する機能を有している。
図３は、パス情報の構成例であり、図２に示した通信網の構成例におけるパス情報の具体例が示されている。パス情報は、通信網５０における任意のノードペアを示すノードペアＩＤと、当該ノードペアの現用パスを示す現用パス情報と、当該ノードペアの迂回用パスを示す迂回用パス情報との組からなり、ノードペアごとにパス情報ＤＢ２２に登録されている。

現用パス情報および迂回用パス情報には、それぞれの現用パスおよび迂回用パスのパスＩＤに加え、これらパスが経由する通信リンクのリンクＩＤが列挙されている。これにより、ノードペアＡＢについては、その現用パスｐ１２が通信リンクａ１を経由し、迂回用パスｑ１２が通信リンクａ２，ａ３を経由していることがわかる。また、ノードペアＡＣについては、その現用パスｐ１３が通信リンクａ２を経由し、迂回用パスｑ１３が通信リンクａ１，ａ３を経由していることがわかる。

トラヒック情報ＤＢ２３は、データ取得部２１によりＯＳ１０から取得したトラヒック情報を記憶する機能を有している。
図４は、トラヒック情報の構成例であり、図２に示した通信網の構成例におけるパス情報の具体例が示されている。トラヒック情報は、通信網５０における任意の通信リンクを示す通信リンクＩＤと、当該通信リンクで観測された現用パスによる観測トラヒック量との組からなり、通信リンクごとにトラヒック情報ＤＢ２３に登録されている。例えば、通信リンクａ１の観測トラヒック量としてＣ１が登録されており、通信リンクａ２，ａ３の観測トラヒック量としてＣ２，Ｃ３がそれぞれ登録されている。

この観測トラヒック量は、障害が発生していない状態で観測されたトラヒック量であり、迂回用パスにより発生したトラヒック量は含まれていない。ＯＳ１０のネットワーク情報ＤＢ１２には、各通信リンクのトラヒック量とともにその障害有無が時系列で保存されており、ＯＳ１０からトラヒック情報を取得する際、障害が発生していない状態における観測トラヒック量をトラヒック情報として取得すればよい。

通信帯域算出部２４は、管理端末３０から指示に応じて、パス情報ＤＢ２２とトラヒック情報ＤＢ２３とを参照し、対象通信リンクの観測トラヒック量と、当該対象通信リンクを経由する現用パスの未知のトラヒック需要との関係に基づいて、当該対象通信リンクの観測トラヒック量に関する観測トラヒック量制約条件を生成する機能と、パス情報ＤＢ２２を参照して、各ノードペアにおける未知のトラヒック需要に関するトラヒック需要制約条件を生成する機能と、パス情報ＤＢ２２を参照して、対象通信リンクを経由する現用パスおよび迂回用パスの未知のトラヒック需要に基づいて、当該対象通信リンクのトラヒック量に関する目的関数を生成する機能と、観測トラヒック量制約条件およびトラヒック需要制約条件が成立する場合における目的関数の最大値を、対象通信リンクの通信帯域上限値として算出し、管理端末３０へ出力する機能とを有している。

通信帯域算出装置２０の機能部のうち、データ取得部２１および通信帯域算出部２４は、ＣＰＵとプログラムとが協働してなる演算処理部、さらにはデータ通信用の通信回路部から実現される。
また、パス情報ＤＢ２２およびトラヒック情報ＤＢ２３は、ハードディスクやメモリなどの記憶装置から実現される。これらは、別個の記憶装置で実現してもよく、同一の記憶装置で実現してもよい。

［本実施の形態の動作］
次に、図５を参照して、本発明の一実施の形態にかかる通信帯域算出装置の動作について説明する。図５は、本発明の一実施の形態にかかる通信帯域算出装置における通信帯域算出処理を示すフローチャートである。
通信帯域算出装置２０の通信帯域算出部２４は、管理端末３０からの指示に応じて、図５の通信帯域算出処理を実行する。

通信帯域算出部２４は、まず、パス情報ＤＢ２２から各ノードペアに関するパス情報を取得するとともに、トラヒック情報ＤＢ２３から対象通信リンクに関する観測トラヒック量を取得する（ステップ１００）。対象通信リンクについては、管理端末３０からの指示で指定されたリンクを選択してもよく、予め記憶部（図示せず）に設定されているリンクを選択しいもよい。以下では、対象通信リンクとして通信リンクａ１が指定された場合を例として説明する。

次に、通信帯域算出部２４は、取得したパス情報と観測トラヒック情報とに基づいて、対象通信リンクａ１の観測トラヒック量Ｃ１と、当該対象通信リンクａ１を経由する現用パスにおける未知のトラヒック需要との関係に基づいて、当該対象通信リンクａ１の観測トラヒック量Ｃ１に関する観測トラヒック量制約条件を生成する（ステップ１０１）。

対象通信リンクａ１の観測トラヒック量Ｃ１は、前述したように、障害が発生していない状態で観測されたトラヒック量であることから、この観測トラヒックＣ１は、当該対象通信リンクａ１を経由するすべての現用パスで発生するトラヒック需要の和に等しい。したがって、この関係から当該対象通信リンクａ１の観測トラヒック量Ｃ１に関する観測トラヒック量制約条件を生成することができる。

この際、任意の対象通信リンクを経由する現用パスを持つノードペアについては、パス情報の現用パス情報から検索でき、ノードペアｄごとに当該現用パスが対象通信リンクａを経由するか否かをフラグｙｄ^aで表すことができる。また、個々のノードペアで発生するトラヒック需要は未知であることから、ノードペアｄごとにトラヒック需要をＸｄと定義すればよい。

したがって、通信網５０内の通信リンクの集合をＡ、対象通信リンクをａ、観測トラヒック値をＣａ、トラヒック需要が発生するノード間の集合をＤ、Ｄに属するノード間をｄ、ｄで発生する未知のトラヒック需要をＸｄ、ｄの現用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｙｄ^aとした場合、観測トラヒック量制約条件は、次の式（１）で表すことができる。
Σ_d∈DＸｄ・ｙｄ^a＝Ｃａ，ｆｏｒａ∈Ａ …（１）

また、通信帯域算出部２４は、取得したパス情報に基づいて、各ノードペアにおける未知のトラヒック需要に関するトラヒック需要制約条件を生成する（ステップ１０２）。
前述したように、各ノードペアｄのトラヒック需要Ｘｄは未知であるが、その値は必ず０以上であり、負値をとることはない。したがって、トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄとした場合、トラヒック需要制約条件は、次の式（２）で表すことができる。
Ｘｄ≧０，ｆｏｒｄ∈Ｄ …（２）

また、通信帯域算出部２４は、取得したパス情報に基づいて、対象通信リンクａ１を経由する現用パスおよび迂回用パスにおける未知のトラヒック需要に基づいて、当該対象通信リンクのトラヒック量に関する目的関数を生成する（ステップ１０３）。
対象通信トラヒックａ１における実際のトラヒック量は、現用パスだけでなく迂回用パスから発生するトラヒック量も含まれる。したがって、対象通信パスａ１を経由する現用パスおよび迂回用パスのトラヒック需要の総和の最大値が、対象通信リンクで必要とされる通信帯域、すなわち通信帯域上限値に相当する。

この際、任意の対象通信リンクを経由する現用パスや迂回用パスを持つノードペアについては、パス情報の現用パス情報や迂回用パス情報から検索できる。このため、ノードペアｄごとに当該現用パスが対象通信リンクａを経由するか否かをフラグｙｄ^aで表すことができるとともに、ノードペアｄごとに当該迂回用パスが対象通信リンクａを経由するか否かをフラグｚｄ^aで表すことができる。また、個々のノードペアで発生するトラヒック需要は未知であることから、ノードペアｄごとにトラヒック需要をＸｄと定義すればよい。

したがって、通信網５０内の通信リンクの集合をＡ、対象通信リンクをａ、トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄ、ｄの現用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｙｄ^a、ｄの迂回用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｚｄ^aとした場合、目的関数は、次の式（３）で表すことができる。
Σ_d∈DＸｄ・（ｙｄ^a＋ｚｄ^a） …（３）

このようにして、観測トラヒック量制約条件、トラヒック需要制約条件、および目的関数を生成した後、通信帯域算出部２４は、線形計画法に基づいて（非特許文献２など参照）、これら観測トラヒック量制約条件とトラヒック需要制約条件が成立する場合の目的関数の最大値を、対象通信リンクａ１の通信帯域上限値として算出して、管理端末３０へ出力し（ステップ１０４）、一連の通信帯域算出処理を終了する。

［本実施の形態の効果］
このように、本実施の形態では、通信網５０を構成するノードペアで用いる現用パスおよび迂回用パスが経由する通信リンクを示すパス情報と、対象通信リンクを経由する現用パスから発生したトラヒックの観測トラヒック量を示すトラヒック情報とをＯＳ０から取得して、通信帯域を算出する対象となる対象通信リンクの観測トラヒック量に関する観測トラヒック量制約条件を生成するとともに、各ノードペアにおける未知のトラヒック需要に関するトラヒック需要制約条件を生成し、当該対象通信リンクのトラヒック量に関する目的関数を生成し、これら観測トラヒック量制約条件およびトラヒック需要制約条件が成立する場合における目的関数の最大値を、対象通信リンクの通信帯域上限値として算出するようにしたので、個々のノードペアに流れるトラヒックが分からない場合でも、迂回用パスのトラヒックを考慮した、より正確な通信帯域上限値を算出することができる。

また、本実施の形態では、観測トラヒック量として、対象通信リンクについて観測したトラヒック量を用いる場合を例として説明したが、実際にトラヒックが流出入する端点ノードでは、当該端点ノードにおける流出入トラヒック量の総和を観測することが可能な場合もある。
このような場合には、通信帯域算出部２４において、当該端点ノードで流出入するトラヒック需要Ｘｄの総和が、当該端点ノードで観測された流出入トラヒック量と等しいという関係から新たな制約条件を生成し、この新たな制約条件と、観測トラヒック量制約条件およびトラヒック需要制約条件とが成立する場合の目的関数の最大値を、対象通信リンクの通信帯域上限値として算出してもよい。

また、本実施の形態では、観測トラヒック量として、対象通信リンクについて観測したトラヒック量を用いる場合を例として説明したが、実際にトラヒックが流出入する端点ノードでは、上記流出入トラヒック量のうちから任意のノードペアで流れるトラヒック量を観測することが可能な場合もある。
このような場合には、通信帯域算出部２４において、前述した式（２）のトラヒック需要制約条件として、任意のノードペアｄのトラヒック需要Ｘｄが、当該端点ノードで観測されたノードペアｄのトラヒック量と等しいという制約条件を生成し、観測トラヒック量制約条件およびトラヒック需要制約条件が成立する場合の目的関数の最大値を、対象通信リンクの通信帯域上限値として算出してもよい。

また、本実施の形態では、観測トラヒック量制約条件を生成する際、対象通信リンクの観測トラヒックと、当該対象通信リンクを経由するすべての現用パスで発生するトラヒック需要の和に等しいと定義したが、この定義に統計多重効果を加えてもよい。
マルチメディア通信、特に、インターネットの利用や動画像通信など情報の量が時間的に大きく変化する場合、例えばＡＴＭ方式で多重することにより、合計の通信速度が平滑化され、ＳＴＭ方式に比べ、一定の帯域で多くの情報を送ることが可能となり、このような効果を「統計多重効果」と言う。

したがって、例えば対象通信リンクに重畳する各トラヒックの組合せごとに、得られる統計多重効果を示す削減率を予め導出しておき、前出した式（１）の右辺に、当該対象通信リンクで得られる削減率を乗算するようにしてもよい。これにより、統計多重効果を考慮した通信帯域上限値を得ることができ、ネットワーク資源の有効活用を実現できる。
また、統計多重効果については、観測トラヒック量制約条件だけでなく、前述した式（３）の目的関数を生成する場合についても、上記と同様に適用でき、同様の作用効果を得ることが可能となる。

本発明の一実施の形態にかかる通信帯域算出装置の構成を示すブロック図である。通信網の一部構成を示す説明図である。パス情報の構成例である。トラヒック情報の構成例である。本発明の一実施の形態にかかる通信帯域算出装置における通信帯域算出処理を示すフローチャートである。

符号の説明

１０…ＯＳ、１１…ネットワークデータ管理部、１２…ネットワーク情報ＤＢ、２０…通信帯域算出装置、２１…データ取得部、２２…パス情報ＤＢ、２３…トラヒック情報ＤＢ、２４…通信帯域算出部、３０…管理端末、３１…制御部、３２…表示部。

Claims

複数のノードと、これらノードからなるノードペアを結ぶ複数の通信リンクとからなる通信網について、当該通信網上の任意の対象通信リンクにおける通信帯域上限値を算出する通信帯域算出装置で用いられる通信帯域算出方法であって、
データ取得部が、前記各ノードペアで用いる現用パスおよび迂回用パスが経由する通信リンクを示すパス情報と、前記対象通信リンクを経由する現用パスから発生したトラヒックの観測トラヒック量を示すトラヒック情報とを取得して、記憶部に保存するデータ取得ステップと、
通信帯域算出部が、前記パス情報と前記トラヒック情報とを参照して、前記対象通信リンクの観測トラヒック量と、当該対象通信リンクを経由する現用パスにおけるトラヒック需要との関係に基づいて、当該対象通信リンクの観測トラヒック量に関する観測トラヒック量制約条件を生成する観測トラヒック量制約条件生成ステップと、
前記通信帯域算出部が、前記パス情報を参照して、各ノードペアにおけるトラヒック需要に関するトラヒック需要制約条件を生成するトラヒック需要制約条件生成ステップと、
前記通信帯域算出部が、前記パス情報を参照して、前記対象通信リンクを経由する現用パスおよび迂回用パスにおけるトラヒック需要に基づいて、当該対象通信リンクのトラヒック量に関する目的関数を生成する目的関数生成ステップと、
前記通信帯域算出部が、前記観測トラヒック量制約条件およびトラヒック需要制約条件が成立する場合における前記目的関数の最大値を前記通信帯域上限値として算出する目的関数最大値算出ステップと
を備えることを特徴とする通信帯域算出方法。
請求項１に記載の通信帯域算出方法において、
前記通信網内の通信リンクの集合をＡ、前記対象通信リンクをａ、ａの前記観測トラヒック量をＣａ、トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄ、ｄの現用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｙｄａとした場合、前記観測トラヒック量制約条件として、
Σｄ∈ＤＸｄ・ｙｄａ＝Ｃａ，ｆｏｒａ∈Ａ
を用いることを特徴とする通信帯域算出方法。
請求項１に記載の通信帯域算出方法において、
トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄとした場合、前記トラヒック需要制約条件として、
Ｘｄ≧０，ｆｏｒｄ∈Ｄ
を用いることを特徴とする通信帯域算出方法。
請求項１に記載の通信帯域算出方法において、
前記通信網内の通信リンクの集合をＡ、前記対象通信リンクをａ、トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄ、ｄの現用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｙｄａ、ｄの迂回用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｚｄａとした場合、前記目的関数として、
Σｄ∈ＤＸｄ・（ｙｄａ＋ｚｄａ）
を用いることを特徴とする通信帯域算出方法。
複数のノードと、これらノードからなるノードペアを結ぶ複数の通信リンクとからなる通信網について、当該通信網上の任意の対象通信リンクにおける通信帯域上限値を算出する通信帯域算出装置であって、
前記各ノードペアで用いる現用パスおよび迂回用パスが経由する通信リンクを示すパス情報と、前記対象通信リンクを経由する現用パスから発生したトラヒックの観測トラヒック量を示すトラヒック情報とを取得して、記憶部に保存するデータ取得部と、
前記パス情報と前記トラヒック情報とを参照して、前記対象通信リンクの観測トラヒック量と、当該対象通信リンクを経由する現用パスにおけるトラヒック需要との関係に基づいて、当該対象通信リンクの観測トラヒック量に関する観測トラヒック量制約条件を生成し、前記パス情報を参照して、各ノードペアにおけるトラヒック需要に関するトラヒック需要制約条件を生成するトラヒック需要制約条件生成ステップと、
前記通信帯域算出部が、前記パス情報を参照して、前記対象通信リンクを経由する現用パスおよび迂回用パスにおけるトラヒック需要に基づいて、当該対象通信リンクのトラヒック量に関する目的関数を生成し、前記観測トラヒック量制約条件およびトラヒック需要制約条件が成立する場合における前記目的関数の最大値を前記通信帯域上限値として算出する通信帯域算出部と
を備えることを特徴とする通信帯域算出装置。
請求項５に記載の通信帯域算出装置において、
前記通信網内の通信リンクの集合をＡ、前記対象通信リンクをａ、ａの前記観測トラヒック量をＣａ、トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄ、ｄの現用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｙｄａとした場合、前記観測トラヒック量制約条件として、
Σｄ∈ＤＸｄ・ｙｄａ＝Ｃａ，ｆｏｒａ∈Ａ
を用いることを特徴とする通信帯域算出装置。
請求項５に記載の通信帯域算出装置において、
トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄとした場合、前記トラヒック需要制約条件として、
Ｘｄ≧０，ｆｏｒｄ∈Ｄ
を用いることを特徴とする通信帯域算出装置。
請求項５に記載の通信帯域算出装置において、
前記通信網内の通信リンクの集合をＡ、前記対象通信リンクをａ、トラヒック需要が発生するノードペアの集合をＤ、Ｄに属するノードペアをｄ、ｄで発生する未知のトラヒック需要をＸｄ、ｄの現用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｙｄａ、ｄの迂回用パスがａを経由する場合に１となりａを経由しない場合に０となるフラグをｚｄａとした場合、前記目的関数として、
Σｄ∈ＤＸｄ・（ｙｄａ＋ｚｄａ）
を用いることを特徴とする通信帯域算出装置。