ネットワーク分割方法、装置およびプログラム
【課題】ネットワーク分割を各部分ネットワーク間の交流トラヒックを考慮して高速に実現できるネットワーク分割方法、装置およびプログラムを提供する。
【解決手段】ネットワーク分割部３は、交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させた後、ネットワーク上の他の各ノードを、部分ネットワーク間の交流トラヒックが最大となるように、前記いずれかの部分ネットワークNWpに順次に所属させることでネットワークNWを２分割する。このような２分割処理を、ネットワークNWが予定数の部分ネットワークNWpに分割されるまで、各部分ネットワークに対して繰り返すことで、ネットワークNWを予定数の部分ネットワークNWpに分割する。
【解決手段】ネットワーク分割部３は、交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させた後、ネットワーク上の他の各ノードを、部分ネットワーク間の交流トラヒックが最大となるように、前記いずれかの部分ネットワークNWpに順次に所属させることでネットワークNWを２分割する。このような２分割処理を、ネットワークNWが予定数の部分ネットワークNWpに分割されるまで、各部分ネットワークに対して繰り返すことで、ネットワークNWを予定数の部分ネットワークNWpに分割する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを複数の部分ネットワークに分割する方法、装置およびプログラムに係り、特に、部分ネットワーク間の交流トラヒックに注目してネットワークを分割する方法、装置およびプログラムに関する。
【背景技術】
【０００２】
非特許文献１には、無線マルチホップネットワークにおいて、ルーチングの効率化、無線リソース利用の効率化などを図ることを目的として、ネットワーク分割を行う手法が提案されている。
【０００３】
非特許文献２には、並列ネットワークシミュレーションにおいて、各プロッセサ負荷の均等化、プロッセサ間通信量の削減を目的として、ネットワーク分割を行う手法が提案されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】A. A. Abbasi and M. Younis, "A survey on clustering algorithms for wireless sensor networks," Elsevier Computer Communications, vol. 30, pp. 2826-2841, June 2007.
【非特許文献２】P. Peschlow, T. Honecker, and P. Martini, "A flexible dynamic partitioning algorithm for optimistic distributed simulation," Proc. of IEEE PADS'07, pp. 219-228, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１では、ネットワーク分割によって生成される各部分ネットワークの大きさを均等化できるが、各部分ネットワーク間の交流トラヒックを考慮したネットワーク分割を実現できない。
【０００６】
非特許文献２では、ネットワーク分割によって生成される各部分ネットワーク間の交流トラヒックを考慮したネットワーク分割を高速に実現できない。
【０００７】
本発明の目的は、上記した従来技術の課題を解決し、ネットワーク分割を各部分ネットワーク間の交流トラヒックを考慮して高速に実現できるネットワーク分割方法、装置およびプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記の目的を達成するために、本発明のネットワーク分割方法は、分割対象のネットワークにおいて、交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させる第１ステップと、一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと他方側の部分ネットワークとの交流トラヒック、および前記他方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと一方側の部分ネットワークとの交流トラヒックを比較し、交流トラヒックが最大となる未所属ノードを、その隣接ノードと同じ部分ネットワークに所属させる第２ステップと、ネットワーク上の全てのノードの所属が確定するまで、前記第２ステップを繰り返させる第３ステップと、ネットワークが予定数の部分ネットワークに分割されるまで、前記各部分ネットワークを分割対象のネットワークと見なして前記第１ないし第３ステップを繰り返させる第４ステップとを含む。
【発明の効果】
【０００９】
本発明によれば、ネットワークを、各部分ネットワーク間の交流トラヒックが最大化または最小化されるように、複数の部分ネットワークに分割できるようになる。
【図面の簡単な説明】
【００１０】
【図１】本発明のネットワーク分割方法、装置およびプログラムの一実施形態に係る機能ブロック図である。
【図２】ネットワークが本発明により複数の部分ネットワークに順次に分割される様子を模式的に表現した図である。
【図３】本発明に係るネットワーク分割方法の第１実施形態（交流トラヒックの最大化）の手順を示したフローチャートである。
【図４】第１実施形態における所属ネットワークの決定方法を示したフローチャートである。
【図５】ネットワーク分割の手順を模式的に示した図（その１）である。
【図６】ネットワーク分割の手順を模式的に示した図（その２）である。
【図７】ネットワーク分割の手順を模式的に示した図（その３）である。
【図８】ネットワーク分割の手順を模式的に示した図（その４）である。
【図９】ネットワーク分割の手順を模式的に示した図（その５）である。
【図１０】ネットワーク分割の手順を模式的に示した図（その６）である。
【図１１】ネットワーク分割の手順を模式的に示した図（その７）である。
【図１２】ネットワーク分割の手順を模式的に示した図（その８）である。
【図１３】ネットワーク分割の手順を模式的に示した図（その９）である。
【図１４】本発明に係るネットワーク分割方法の第２実施形態（交流トラヒックの最小化）の手順を示したフローチャートである。
【図１５】第２実施形態における所属ネットワークの決定方法を示したフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明のネットワーク分割方法、装置およびプログラムの一実施形態に係る機能ブロック図であり、図２は、ネットワークが複数の部分ネットワークに順次に分割される様子を模式的に表現した図である。
【００１２】
本発明では、部分ネットワーク間の交流トラヒックが最大化または最小化されるように、ネットワークNWが予定数の部分ネットワークNWpに分割されるが、ここでは初めに、部分ネットワーク間の交流トラヒックが最大化されるようにネットワークNWが分割される場合を例にして説明する。
【００１３】
図１において、入力インターフェース１には、分割対象となるネットワークNWのトポロジ情報および各ネットワークノード間のトラヒック量がネットワーク情報として予め入力される。交流トラヒック算出部２は、前記ネットワーク情報に基づいて、ネットワークNW上の各ノードペア間の交流トラヒックや部分ネットワークNWp間の交流トラヒックを算出する。
【００１４】
ネットワーク分割部３は、交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させた後、ネットワーク上の他の各ノードを、部分ネットワーク間の交流トラヒックが最大となるように、前記いずれかの部分ネットワークNWpに順次に所属させることで、図２(a)に示したようにネットワークNWを２分割する。そして、このような２分割処理を、前記ネットワークNWが予定数の部分ネットワークNWpに分割されるまで、同図(b)，(c)のように各部分ネットワークに対して繰り返すことで、前記ネットワークNWが最終的に予定数の部分ネットワークNWpに分割される。
【００１５】
図３は、本発明の第１実施形態に係るネットワーク分割方法の手順を示したフローチャートであり、主に前記ネットワーク分割部３の動作を示している。
【００１６】
ステップＳ１では、分割対象のネットワークNWの中から、交流トラヒックが最大となるノードペア[Na，Nb]が抽出される。この交流トラヒックは、発ノードと着ノードとの関係にあるノードペアに限定して算出されるものではなく、あるトラヒックが発ノードから複数の中継ノードを経由して着ノードに到達する場合、経路上の全てのノードのペアについて、そのトラヒック量が交流トラヒックとして算出される
【００１７】
ステップＳ２では、一方のノードペアNaが一方側の部分ネットワークNMp0に所属する中心ノードに設定され、他方のノードペアNbが他方側の部分ネットワークNMp1に所属する中心ノードに設定される。ステップＳ３では、部分ネットワークNMp0，NMp1間の交流トラヒックが最大化されるように、ネットワーク上の全てのノードについて、その所属ネットワークが前記２つの部分ネットワークNMp0，NMp1のいずれかに順次に決定される。
【００１８】
図４は、前記ステップＳ３における所属ネットワークの決定方法を示したフローチャートである。
【００１９】
ステップＳ３０１では、一方側の部分ネットワークNMp0への所属が決定しているノードを隣接ノードとする全ての未所属ノード、および他方側の部分ネットワークNMp1への所属が決定しているノードを隣接ノードとする全ての未所属ノードが抽出される。ここでは、図５に示したように、一方側の部分ネットワークNMp0への所属が決定している中心ノードNaに隣接する２つの未所属ノードN1，N2、および他方側の部分ネットワークNMp1への所属が決定している中心ノードNbに隣接する２つの未所属ノードN3，N4が抽出される。
【００２０】
ステップＳ３０２では、図６に示したように、各未所属ノードの交流トラヒックとして、ノードN1，N2を、その隣接ノードNaと同じ部分ネットワークNMp0に所属させた場合の部分ネットワークNMp1との交流トラヒックQ1，Q2、およびノードN3，N4を、その隣接ノードNbと同じ部分ネットワークNMp1に所属させた場合の部分ネットワークNMp0との交流トラヒックQ3，Q4が、それぞれ算出される。
【００２１】
ステップＳ３０３では、前記各交流トラヒックQ1，Q2，Q3，Q4が比較され、交流トラヒックが最大となるノードについて、その所属先が隣接ノードと同じに決定される。ここでは、ノードN1と部分ネットワークNMp1との交流トラヒックQ1が最大値を示したものとし、図７に示したように、ノードN1の所属先が部分ネットワークNMp0に決定されたものとして説明を続ける。
【００２２】
なお、交流トラヒックが最大値を示す未所属ノードが複数存在する場合は、全ての未所属ノードとの交流トラヒックの総和をそれぞれ算出し、この総和が最大となる未所属ノードのみを隣接ノードと同じ部分ネットワークに所属させる。
【００２３】
図３へ戻り、ステップＳ４では、ネットワークNW上の全てのノードについて、その所属先の部分ネットワークの決定が完了したか否かが判定される。ここでは、未だ完了していないと判定されるのでステップＳ３へ戻り、上記の各処理が繰り返される。
【００２４】
すなわち、ステップＳ３０１では、図８に示したように、部分ネットワークNMp0への所属が決定しているノードNa，N1を隣接ノードとする全ての未所属ノードN2，N5，N6、および部分ネットワークNMp1への所属が決定しているノードNbに隣接する全ての未所属ノードN3，N4が抽出される。
【００２５】
ステップＳ３０２では、各未所属ノードをその隣接ノードと同じ部分ネットワークに所属させた場合の交流トラヒックとして、ノードN2，N5，N6を部分ネットワークNMp0に所属させた場合の部分ネットワークNMp1との交流トラヒックQ1，Q2，Q3、およびノードN3，N4を部分ネットワークNMp1に所属させた場合の部分ネットワークNMp0との交流トラヒックQ4，Q5が、それぞれ算出される。
【００２６】
ステップＳ３０３では、前記各交流トラヒックQ1，Q2，Q3，Q4，Q5が比較され、交流トラヒックが最大となるノードの所属先が、その隣接ノードと同じに決定される。ここでは、ノードN4と部分ネットワークNMp0との交流トラヒックQ5が最大値を示したものとし、図９に示したように、ノードN4の所属先が部分ネットワークNMp1に決定されたものとして説明を続ける。
【００２７】
図３へ戻り、ステップＳ４では、ネットワークNW上の全てのノードについて、その所属先のネットワークの決定が完了したか否かが判定される。ここでも、未だ完了していないと判定されるのでステップＳ３へ戻り、上記の各処理が繰り返される。
【００２８】
すなわち、図１０に示したように、部分ネットワークNMp0への所属が決定しているノードNa，N1を隣接ノードとする全ての未所属ノードN2，N5，N6、および部分ネットワークNMp1への所属が決定しているノードNb，N4に隣接する全ての未所属ノードN3，N7，N8の中から、交流トラヒックが最大となる未所属ノードの所属先が、その隣接ノードと同じ部分ネットワークに決定される。
【００２９】
なお、前記ステップＳ３において、図１１に一例を示したように、一方側の部分ネットワークNMp0に所属するノードNdを隣接ノードとするノードN12が、他方側の部分ネットワークNMp1に所属するノードNeをも隣接ノードとする場合は、以下のようにして所属先の部分ネットワークが決定される。
【００３０】
本実施形態では、当該時点において、部分ネットワークNMp0への所属が決定しているノードNc，Ndを隣接ノードとする未所属ノードN11，N12と部分ネットワークNMp1との交流トラヒックQ1，Q3、部分ネットワークNMp1への所属が決定しているノードNe，Nfを隣接ノードとする未所属ノードN12，N13と部分ネットワークNMp0との交流トラヒックQ4，Q2が比較される。
【００３１】
そして、例えばノードN12と部分ネットワークNMp1との交流トラヒックQ3が最大値を示せば、当該注目ノードN12の所属ネットワークが部分ネットワークNMp0に決定される。また、ノードN12と部分ネットワークNMp0との交流トラヒックQ4が最大値を示せば、当該ノードN12の所属ネットワークが部分ネットワークNMp1に決定される。
【００３２】
図３へ戻り、以上のようにして、ネットワークNW上の全てのノードの所属先が部分ネットワークNMp0，NMp1のいずれかに決定されるとステップＳ５へ進み、所属先ネットワークの見直しが実施される。
【００３３】
ここでは、図１２(a)に一例を示したように、一方側の部分ネットワークNMp0に所属するノードNcと他方側の部分ネットワークNMp1に所属するノードNdとが隣接関係にあるとき、同図(b)に示したように、ノードNdの所属先を一方側の部分ネットワークNMp0に変更することにより部分ネットワーク間の交流トラヒックが増加するならば、前記ノードNdの所属先が一方側の部分ネットワークNMp0に変更される。
【００３４】
同様に、同図(c)に示したように、ノードNcの所属先を他方側の部分ネットワークNMp1に変更することにより、部分ネットワーク間の交流トラヒックが増加するならば、前記ノードNcの所属先が他方側の部分ネットワークNMp1に変更される。本実施形態では、このような所属ネットワークの見直しが、互いに異なる部分ネットワークに所属して隣接関係にある全てのノードペアに対して行われる。
【００３５】
ただし、図１３(a)に一例を示したように、ノードペアNc，Ndは、互いに異なる部分ネットワークに所属して隣接関係にあるものの、同図(b)に示したように、ノードNdの所属先を部分ネットワークNWp0に変更してしまうと、ノードNfは、自身が所属する部分ネットワークNWp1内に隣接ノードを持てなくなって孤立し、部分ネットワークNWp1内の他のノードと通信する際でも、必ず他の部分ネットワークNWp0を中継しなければならなくなってしまう。すなわち、ノードNfは実質的に部分ネットワークNWp1を構成できなくなる。
【００３６】
このような場合、本実施形態では同図(c)に示したように、ノードNdと共に前記孤立ノードNfも同時に、その所属先を部分ネットワークNWp0に変更することにより、ネットワーク内でのノードの孤立化を防止するようにしている。
【００３７】
ただし、このように複数ノードNd，Nfの所属ネットワークを同時に変更する処理は、ノードNd，Nfが変更前の部分ネットワークNWp1に所属しているときの部分ネットワークNWp0との交流トラヒックよりも、部分ネットワークNWp0に所属させたときの部分ネットワークNWp1との交流トラヒックの方が増加する場合に限定され、それ以外の場合には、ノードペアNc，Ndに関する所属先の見直しは見送られる。
【００３８】
図３へ戻り、ステップＳ６では、ネットワークNWが予定の部分ネットワーク数まで分割されたか否かが判定される。分割数が不足していればステップＳ１へ戻り、各部分ネットワークNWp0，NWp1を新たに分割対象と見なし、分割数が予定数に達するまで上記の２分割処理が繰り返される。
【００３９】
なお、上記の実施形態では、部分ネットワーク間の交流トラヒックが最大化されるように各ネットワークノードの所属先を順次に決定することでネットワークが分割されたが、本発明はこれのみに限定されるものではなく、部分ネットワーク間の交流トラヒックが最小化されるように各ネットワークノードの所属先を順次に決定することでネットワークが分割されるようにしても良い。
【００４０】
図１４，１５は、ネットワークNWを部分ネットワーク間の交流トラヒックが最小化されるように分割する第２実施形態の手順を示したフローチャートであり、ステップＳ１ａでは、分割対象のネットワークNWの中から、交流トラヒックが最小となるノードペア[Na，Nb]が抽出される。
【００４１】
ステップＳ２では、一方のノードペアNaが一方側の部分ネットワークNMp0に所属する中心ノードに設定され、他方のノードペアNbが他方側の部分ネットワークNMp1に所属する中心ノードに設定される。ステップＳ３ａでは、ネットワーク上の全てのノードについて、その所属ネットワークが、部分ネットワーク間の交流トラヒックが最小化されるように、前記２つの部分ネットワークNMp0，NMp1のいずれかに順次に決定される。
【００４２】
ステップＳ４では、ネットワークNW上の全てのノードについて、その所属先の部分ネットワークの決定が完了したか否かが判定され、完了するまではステップＳ３へ戻って上記の各処理が繰り返される。
【００４３】
ネットワークNW上の全てのノードの所属先が部分ネットワークNMp0，NMp1のいずれかに決定されるとステップＳ５ａへ進み、所属先ネットワークの見直しが、部分ネットワーク間の交流トラヒックが最小化するように実施される。ステップＳ６では、ネットワークNWが予定の部分ネットワーク数まで分割されたか否かが判定される。分割数が不足していればステップＳ１ａへ戻り、各部分ネットワークNWp0，NWp1を新たに分割対象と見なし、分割数が予定数に達するまで上記の２分割処理が繰り返される。
【００４４】
なお、前記図１１を参照して説明したように、一方側の部分ネットワークNMp0に所属するノードNdを隣接ノードとするノードN12が、他方側の部分ネットワークNMp1に所属するノードNeをも隣接ノードとする場合は、例えばノードN12と部分ネットワークNMp1との交流トラヒックQ3が最小値を示せば、当該注目ノードN12の所属ネットワークが部分ネットワークNMp0に決定される。また、ノードN12と部分ネットワークNMp0との交流トラヒックQ4が最小値を示せば、当該ノードN12の所属ネットワークが部分ネットワークNMp1に決定される。
【００４５】
同様に、前記図１２を参照して説明したように、一方側の部分ネットワークNMp0に所属するノードNcと他方側の部分ネットワークNMp1に所属するノードNdとが隣接関係にあるとき、同図(b)に示したように、ノードNdの所属先を一方側の部分ネットワークNMp0に変更することにより部分ネットワーク間の交流トラヒックが減少するならば、前記ノードNdの所属先が一方側の部分ネットワークNMp0に変更される。
【００４６】
同様に、同図(c)に示したように、ノードNcの所属先を他方側の部分ネットワークNMp1に変更することにより、部分ネットワーク間の交流トラヒックが減少するならば、前記ノードNcの所属先が他方側の部分ネットワークNMp1に変更される。
【００４７】
ただし、図１３(b)に示したように、ノードNdの所属先を部分ネットワークNWp0に変更してしまうと、ノードNfは、自身が所属する部分ネットワークNWp1内に隣接ノードを持てなくなって孤立する場合は、同図(c)に示したように、ノードNdと共に前記孤立ノードNfも同時に、その所属先を部分ネットワークNWp0に変更することにより、ネットワーク内でのノードの孤立化を防止するようにしている。
【００４８】
ただし、このように複数ノードNd，Nfの所属ネットワークを同時に変更する処理は、ノードNd，Nfが変更前の部分ネットワークNWp1に所属しているときの部分ネットワークNWp0との交流トラヒックよりも、部分ネットワークNWp0に所属させたときの部分ネットワークNWp1との交流トラヒックの方が減少する場合に限定され、それ以外の場合には、ノードペアNc，Ndに関する所属先の見直しは見送られる。
【００４９】
上記の各実施形態に係るネットワーク分割方法および装置は、前記各フローチャートで説明した処理をコンピュータが実行可能な言語で記述されたプログラムとしても実現できる。このようなネットワーク分割プログラムは、光学式の記録媒体を介して、または有線、無線のネットワークを介してコンピュータの記憶領域にインストールし、これをＣＰＵが順次に読み取ることで実行される。
【符号の説明】
【００５０】
１…入力インターフェース，２…交流トラヒック算出部，３…ネットワーク分割部
【技術分野】
【０００１】
本発明は、ネットワークを複数の部分ネットワークに分割する方法、装置およびプログラムに係り、特に、部分ネットワーク間の交流トラヒックに注目してネットワークを分割する方法、装置およびプログラムに関する。
【背景技術】
【０００２】
非特許文献１には、無線マルチホップネットワークにおいて、ルーチングの効率化、無線リソース利用の効率化などを図ることを目的として、ネットワーク分割を行う手法が提案されている。
【０００３】
非特許文献２には、並列ネットワークシミュレーションにおいて、各プロッセサ負荷の均等化、プロッセサ間通信量の削減を目的として、ネットワーク分割を行う手法が提案されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】A. A. Abbasi and M. Younis, "A survey on clustering algorithms for wireless sensor networks," Elsevier Computer Communications, vol. 30, pp. 2826-2841, June 2007.
【非特許文献２】P. Peschlow, T. Honecker, and P. Martini, "A flexible dynamic partitioning algorithm for optimistic distributed simulation," Proc. of IEEE PADS'07, pp. 219-228, 2007.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１では、ネットワーク分割によって生成される各部分ネットワークの大きさを均等化できるが、各部分ネットワーク間の交流トラヒックを考慮したネットワーク分割を実現できない。
【０００６】
非特許文献２では、ネットワーク分割によって生成される各部分ネットワーク間の交流トラヒックを考慮したネットワーク分割を高速に実現できない。
【０００７】
本発明の目的は、上記した従来技術の課題を解決し、ネットワーク分割を各部分ネットワーク間の交流トラヒックを考慮して高速に実現できるネットワーク分割方法、装置およびプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
上記の目的を達成するために、本発明のネットワーク分割方法は、分割対象のネットワークにおいて、交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させる第１ステップと、一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと他方側の部分ネットワークとの交流トラヒック、および前記他方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと一方側の部分ネットワークとの交流トラヒックを比較し、交流トラヒックが最大となる未所属ノードを、その隣接ノードと同じ部分ネットワークに所属させる第２ステップと、ネットワーク上の全てのノードの所属が確定するまで、前記第２ステップを繰り返させる第３ステップと、ネットワークが予定数の部分ネットワークに分割されるまで、前記各部分ネットワークを分割対象のネットワークと見なして前記第１ないし第３ステップを繰り返させる第４ステップとを含む。
【発明の効果】
【０００９】
本発明によれば、ネットワークを、各部分ネットワーク間の交流トラヒックが最大化または最小化されるように、複数の部分ネットワークに分割できるようになる。
【図面の簡単な説明】
【００１０】
【図１】本発明のネットワーク分割方法、装置およびプログラムの一実施形態に係る機能ブロック図である。
【図２】ネットワークが本発明により複数の部分ネットワークに順次に分割される様子を模式的に表現した図である。
【図３】本発明に係るネットワーク分割方法の第１実施形態（交流トラヒックの最大化）の手順を示したフローチャートである。
【図４】第１実施形態における所属ネットワークの決定方法を示したフローチャートである。
【図５】ネットワーク分割の手順を模式的に示した図（その１）である。
【図６】ネットワーク分割の手順を模式的に示した図（その２）である。
【図７】ネットワーク分割の手順を模式的に示した図（その３）である。
【図８】ネットワーク分割の手順を模式的に示した図（その４）である。
【図９】ネットワーク分割の手順を模式的に示した図（その５）である。
【図１０】ネットワーク分割の手順を模式的に示した図（その６）である。
【図１１】ネットワーク分割の手順を模式的に示した図（その７）である。
【図１２】ネットワーク分割の手順を模式的に示した図（その８）である。
【図１３】ネットワーク分割の手順を模式的に示した図（その９）である。
【図１４】本発明に係るネットワーク分割方法の第２実施形態（交流トラヒックの最小化）の手順を示したフローチャートである。
【図１５】第２実施形態における所属ネットワークの決定方法を示したフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１は、本発明のネットワーク分割方法、装置およびプログラムの一実施形態に係る機能ブロック図であり、図２は、ネットワークが複数の部分ネットワークに順次に分割される様子を模式的に表現した図である。
【００１２】
本発明では、部分ネットワーク間の交流トラヒックが最大化または最小化されるように、ネットワークNWが予定数の部分ネットワークNWpに分割されるが、ここでは初めに、部分ネットワーク間の交流トラヒックが最大化されるようにネットワークNWが分割される場合を例にして説明する。
【００１３】
図１において、入力インターフェース１には、分割対象となるネットワークNWのトポロジ情報および各ネットワークノード間のトラヒック量がネットワーク情報として予め入力される。交流トラヒック算出部２は、前記ネットワーク情報に基づいて、ネットワークNW上の各ノードペア間の交流トラヒックや部分ネットワークNWp間の交流トラヒックを算出する。
【００１４】
ネットワーク分割部３は、交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させた後、ネットワーク上の他の各ノードを、部分ネットワーク間の交流トラヒックが最大となるように、前記いずれかの部分ネットワークNWpに順次に所属させることで、図２(a)に示したようにネットワークNWを２分割する。そして、このような２分割処理を、前記ネットワークNWが予定数の部分ネットワークNWpに分割されるまで、同図(b)，(c)のように各部分ネットワークに対して繰り返すことで、前記ネットワークNWが最終的に予定数の部分ネットワークNWpに分割される。
【００１５】
図３は、本発明の第１実施形態に係るネットワーク分割方法の手順を示したフローチャートであり、主に前記ネットワーク分割部３の動作を示している。
【００１６】
ステップＳ１では、分割対象のネットワークNWの中から、交流トラヒックが最大となるノードペア[Na，Nb]が抽出される。この交流トラヒックは、発ノードと着ノードとの関係にあるノードペアに限定して算出されるものではなく、あるトラヒックが発ノードから複数の中継ノードを経由して着ノードに到達する場合、経路上の全てのノードのペアについて、そのトラヒック量が交流トラヒックとして算出される
【００１７】
ステップＳ２では、一方のノードペアNaが一方側の部分ネットワークNMp0に所属する中心ノードに設定され、他方のノードペアNbが他方側の部分ネットワークNMp1に所属する中心ノードに設定される。ステップＳ３では、部分ネットワークNMp0，NMp1間の交流トラヒックが最大化されるように、ネットワーク上の全てのノードについて、その所属ネットワークが前記２つの部分ネットワークNMp0，NMp1のいずれかに順次に決定される。
【００１８】
図４は、前記ステップＳ３における所属ネットワークの決定方法を示したフローチャートである。
【００１９】
ステップＳ３０１では、一方側の部分ネットワークNMp0への所属が決定しているノードを隣接ノードとする全ての未所属ノード、および他方側の部分ネットワークNMp1への所属が決定しているノードを隣接ノードとする全ての未所属ノードが抽出される。ここでは、図５に示したように、一方側の部分ネットワークNMp0への所属が決定している中心ノードNaに隣接する２つの未所属ノードN1，N2、および他方側の部分ネットワークNMp1への所属が決定している中心ノードNbに隣接する２つの未所属ノードN3，N4が抽出される。
【００２０】
ステップＳ３０２では、図６に示したように、各未所属ノードの交流トラヒックとして、ノードN1，N2を、その隣接ノードNaと同じ部分ネットワークNMp0に所属させた場合の部分ネットワークNMp1との交流トラヒックQ1，Q2、およびノードN3，N4を、その隣接ノードNbと同じ部分ネットワークNMp1に所属させた場合の部分ネットワークNMp0との交流トラヒックQ3，Q4が、それぞれ算出される。
【００２１】
ステップＳ３０３では、前記各交流トラヒックQ1，Q2，Q3，Q4が比較され、交流トラヒックが最大となるノードについて、その所属先が隣接ノードと同じに決定される。ここでは、ノードN1と部分ネットワークNMp1との交流トラヒックQ1が最大値を示したものとし、図７に示したように、ノードN1の所属先が部分ネットワークNMp0に決定されたものとして説明を続ける。
【００２２】
なお、交流トラヒックが最大値を示す未所属ノードが複数存在する場合は、全ての未所属ノードとの交流トラヒックの総和をそれぞれ算出し、この総和が最大となる未所属ノードのみを隣接ノードと同じ部分ネットワークに所属させる。
【００２３】
図３へ戻り、ステップＳ４では、ネットワークNW上の全てのノードについて、その所属先の部分ネットワークの決定が完了したか否かが判定される。ここでは、未だ完了していないと判定されるのでステップＳ３へ戻り、上記の各処理が繰り返される。
【００２４】
すなわち、ステップＳ３０１では、図８に示したように、部分ネットワークNMp0への所属が決定しているノードNa，N1を隣接ノードとする全ての未所属ノードN2，N5，N6、および部分ネットワークNMp1への所属が決定しているノードNbに隣接する全ての未所属ノードN3，N4が抽出される。
【００２５】
ステップＳ３０２では、各未所属ノードをその隣接ノードと同じ部分ネットワークに所属させた場合の交流トラヒックとして、ノードN2，N5，N6を部分ネットワークNMp0に所属させた場合の部分ネットワークNMp1との交流トラヒックQ1，Q2，Q3、およびノードN3，N4を部分ネットワークNMp1に所属させた場合の部分ネットワークNMp0との交流トラヒックQ4，Q5が、それぞれ算出される。
【００２６】
ステップＳ３０３では、前記各交流トラヒックQ1，Q2，Q3，Q4，Q5が比較され、交流トラヒックが最大となるノードの所属先が、その隣接ノードと同じに決定される。ここでは、ノードN4と部分ネットワークNMp0との交流トラヒックQ5が最大値を示したものとし、図９に示したように、ノードN4の所属先が部分ネットワークNMp1に決定されたものとして説明を続ける。
【００２７】
図３へ戻り、ステップＳ４では、ネットワークNW上の全てのノードについて、その所属先のネットワークの決定が完了したか否かが判定される。ここでも、未だ完了していないと判定されるのでステップＳ３へ戻り、上記の各処理が繰り返される。
【００２８】
すなわち、図１０に示したように、部分ネットワークNMp0への所属が決定しているノードNa，N1を隣接ノードとする全ての未所属ノードN2，N5，N6、および部分ネットワークNMp1への所属が決定しているノードNb，N4に隣接する全ての未所属ノードN3，N7，N8の中から、交流トラヒックが最大となる未所属ノードの所属先が、その隣接ノードと同じ部分ネットワークに決定される。
【００２９】
なお、前記ステップＳ３において、図１１に一例を示したように、一方側の部分ネットワークNMp0に所属するノードNdを隣接ノードとするノードN12が、他方側の部分ネットワークNMp1に所属するノードNeをも隣接ノードとする場合は、以下のようにして所属先の部分ネットワークが決定される。
【００３０】
本実施形態では、当該時点において、部分ネットワークNMp0への所属が決定しているノードNc，Ndを隣接ノードとする未所属ノードN11，N12と部分ネットワークNMp1との交流トラヒックQ1，Q3、部分ネットワークNMp1への所属が決定しているノードNe，Nfを隣接ノードとする未所属ノードN12，N13と部分ネットワークNMp0との交流トラヒックQ4，Q2が比較される。
【００３１】
そして、例えばノードN12と部分ネットワークNMp1との交流トラヒックQ3が最大値を示せば、当該注目ノードN12の所属ネットワークが部分ネットワークNMp0に決定される。また、ノードN12と部分ネットワークNMp0との交流トラヒックQ4が最大値を示せば、当該ノードN12の所属ネットワークが部分ネットワークNMp1に決定される。
【００３２】
図３へ戻り、以上のようにして、ネットワークNW上の全てのノードの所属先が部分ネットワークNMp0，NMp1のいずれかに決定されるとステップＳ５へ進み、所属先ネットワークの見直しが実施される。
【００３３】
ここでは、図１２(a)に一例を示したように、一方側の部分ネットワークNMp0に所属するノードNcと他方側の部分ネットワークNMp1に所属するノードNdとが隣接関係にあるとき、同図(b)に示したように、ノードNdの所属先を一方側の部分ネットワークNMp0に変更することにより部分ネットワーク間の交流トラヒックが増加するならば、前記ノードNdの所属先が一方側の部分ネットワークNMp0に変更される。
【００３４】
同様に、同図(c)に示したように、ノードNcの所属先を他方側の部分ネットワークNMp1に変更することにより、部分ネットワーク間の交流トラヒックが増加するならば、前記ノードNcの所属先が他方側の部分ネットワークNMp1に変更される。本実施形態では、このような所属ネットワークの見直しが、互いに異なる部分ネットワークに所属して隣接関係にある全てのノードペアに対して行われる。
【００３５】
ただし、図１３(a)に一例を示したように、ノードペアNc，Ndは、互いに異なる部分ネットワークに所属して隣接関係にあるものの、同図(b)に示したように、ノードNdの所属先を部分ネットワークNWp0に変更してしまうと、ノードNfは、自身が所属する部分ネットワークNWp1内に隣接ノードを持てなくなって孤立し、部分ネットワークNWp1内の他のノードと通信する際でも、必ず他の部分ネットワークNWp0を中継しなければならなくなってしまう。すなわち、ノードNfは実質的に部分ネットワークNWp1を構成できなくなる。
【００３６】
このような場合、本実施形態では同図(c)に示したように、ノードNdと共に前記孤立ノードNfも同時に、その所属先を部分ネットワークNWp0に変更することにより、ネットワーク内でのノードの孤立化を防止するようにしている。
【００３７】
ただし、このように複数ノードNd，Nfの所属ネットワークを同時に変更する処理は、ノードNd，Nfが変更前の部分ネットワークNWp1に所属しているときの部分ネットワークNWp0との交流トラヒックよりも、部分ネットワークNWp0に所属させたときの部分ネットワークNWp1との交流トラヒックの方が増加する場合に限定され、それ以外の場合には、ノードペアNc，Ndに関する所属先の見直しは見送られる。
【００３８】
図３へ戻り、ステップＳ６では、ネットワークNWが予定の部分ネットワーク数まで分割されたか否かが判定される。分割数が不足していればステップＳ１へ戻り、各部分ネットワークNWp0，NWp1を新たに分割対象と見なし、分割数が予定数に達するまで上記の２分割処理が繰り返される。
【００３９】
なお、上記の実施形態では、部分ネットワーク間の交流トラヒックが最大化されるように各ネットワークノードの所属先を順次に決定することでネットワークが分割されたが、本発明はこれのみに限定されるものではなく、部分ネットワーク間の交流トラヒックが最小化されるように各ネットワークノードの所属先を順次に決定することでネットワークが分割されるようにしても良い。
【００４０】
図１４，１５は、ネットワークNWを部分ネットワーク間の交流トラヒックが最小化されるように分割する第２実施形態の手順を示したフローチャートであり、ステップＳ１ａでは、分割対象のネットワークNWの中から、交流トラヒックが最小となるノードペア[Na，Nb]が抽出される。
【００４１】
ステップＳ２では、一方のノードペアNaが一方側の部分ネットワークNMp0に所属する中心ノードに設定され、他方のノードペアNbが他方側の部分ネットワークNMp1に所属する中心ノードに設定される。ステップＳ３ａでは、ネットワーク上の全てのノードについて、その所属ネットワークが、部分ネットワーク間の交流トラヒックが最小化されるように、前記２つの部分ネットワークNMp0，NMp1のいずれかに順次に決定される。
【００４２】
ステップＳ４では、ネットワークNW上の全てのノードについて、その所属先の部分ネットワークの決定が完了したか否かが判定され、完了するまではステップＳ３へ戻って上記の各処理が繰り返される。
【００４３】
ネットワークNW上の全てのノードの所属先が部分ネットワークNMp0，NMp1のいずれかに決定されるとステップＳ５ａへ進み、所属先ネットワークの見直しが、部分ネットワーク間の交流トラヒックが最小化するように実施される。ステップＳ６では、ネットワークNWが予定の部分ネットワーク数まで分割されたか否かが判定される。分割数が不足していればステップＳ１ａへ戻り、各部分ネットワークNWp0，NWp1を新たに分割対象と見なし、分割数が予定数に達するまで上記の２分割処理が繰り返される。
【００４４】
なお、前記図１１を参照して説明したように、一方側の部分ネットワークNMp0に所属するノードNdを隣接ノードとするノードN12が、他方側の部分ネットワークNMp1に所属するノードNeをも隣接ノードとする場合は、例えばノードN12と部分ネットワークNMp1との交流トラヒックQ3が最小値を示せば、当該注目ノードN12の所属ネットワークが部分ネットワークNMp0に決定される。また、ノードN12と部分ネットワークNMp0との交流トラヒックQ4が最小値を示せば、当該ノードN12の所属ネットワークが部分ネットワークNMp1に決定される。
【００４５】
同様に、前記図１２を参照して説明したように、一方側の部分ネットワークNMp0に所属するノードNcと他方側の部分ネットワークNMp1に所属するノードNdとが隣接関係にあるとき、同図(b)に示したように、ノードNdの所属先を一方側の部分ネットワークNMp0に変更することにより部分ネットワーク間の交流トラヒックが減少するならば、前記ノードNdの所属先が一方側の部分ネットワークNMp0に変更される。
【００４６】
同様に、同図(c)に示したように、ノードNcの所属先を他方側の部分ネットワークNMp1に変更することにより、部分ネットワーク間の交流トラヒックが減少するならば、前記ノードNcの所属先が他方側の部分ネットワークNMp1に変更される。
【００４７】
ただし、図１３(b)に示したように、ノードNdの所属先を部分ネットワークNWp0に変更してしまうと、ノードNfは、自身が所属する部分ネットワークNWp1内に隣接ノードを持てなくなって孤立する場合は、同図(c)に示したように、ノードNdと共に前記孤立ノードNfも同時に、その所属先を部分ネットワークNWp0に変更することにより、ネットワーク内でのノードの孤立化を防止するようにしている。
【００４８】
ただし、このように複数ノードNd，Nfの所属ネットワークを同時に変更する処理は、ノードNd，Nfが変更前の部分ネットワークNWp1に所属しているときの部分ネットワークNWp0との交流トラヒックよりも、部分ネットワークNWp0に所属させたときの部分ネットワークNWp1との交流トラヒックの方が減少する場合に限定され、それ以外の場合には、ノードペアNc，Ndに関する所属先の見直しは見送られる。
【００４９】
上記の各実施形態に係るネットワーク分割方法および装置は、前記各フローチャートで説明した処理をコンピュータが実行可能な言語で記述されたプログラムとしても実現できる。このようなネットワーク分割プログラムは、光学式の記録媒体を介して、または有線、無線のネットワークを介してコンピュータの記憶領域にインストールし、これをＣＰＵが順次に読み取ることで実行される。
【符号の説明】
【００５０】
１…入力インターフェース，２…交流トラヒック算出部，３…ネットワーク分割部
【特許請求の範囲】
【請求項１】
ネットワークを複数の部分ネットワークに分割するネットワーク分割方法において、
分割対象のネットワークにおいて、交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させる第１ステップと、
前記一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと他方側の部分ネットワークとの交流トラヒック、および前記他方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと一方側の部分ネットワークとの交流トラヒックを比較し、交流トラヒックが最大となる未所属ノードを、その隣接ノードと同じ部分ネットワークに所属させる第２ステップと、
ネットワーク上の全てのノードの所属が確定するまで、前記第２ステップを繰り返させる第３ステップと、
前記ネットワークが予定数の部分ネットワークに分割されるまで、前記各部分ネットワークを分割対象のネットワークと見なして前記第１ないし第３ステップを繰り返させる第４ステップとを含むことを特徴とするネットワーク分割方法。
【請求項２】
前記第２ステップでは、前記一方側の部分ネットワークへの所属が決まっているノードおよび他方側の部分ネットワークへの所属が決まっているノードの双方に隣接する未所属ノードを、他方側の部分ネットワークとの交流トラヒックが最大となれば一方側の部分ネットワークに所属させ、一方側の部分ネットワークとの交流トラヒックが最大となれば他方側の部分ネットワークに所属させることを特徴とする請求項１に記載のネットワーク分割方法。
【請求項３】
前記第２ステップにおいて、一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードの中で、他方側の部分ネットワークとの交流トラヒックが最大となる未所属ノードが複数検出されると、当該複数の未所属ノードの中で、他の未所属ノードとの交流トラヒックの総和が最大となる未所属ノードを前記一方側の部分ネットワークに所属させることを特徴とする請求項１または２に記載のネットワーク分割方法。
【請求項４】
相互に隣接し、所属する部分ネットワークが互いに異なるノードペアについて、その一方が所属する部分ネットワークを変更することにより部分ネットワーク間の交流トラヒックが増加する場合、前記ノードペアの一方が所属する部分ネットワークを変更する第５ステップをさらに含むことを特徴とする請求項１ないし３のいずれかに記載のネットワーク分割方法。
【請求項５】
前記第５ステップでは、前記ノードペアの一方が所属する部分ネットワークを変更することにより、所属変更前の部分ネットワークにおいて、当該ネットワーク内に隣接ノードが存在しなくなる孤立ノードが発生する場合には、前記孤立ノードの所属する部分ネットワークも同時に変更されることを特徴とする請求項４に記載のネットワーク分割方法。
【請求項６】
前記所属する部分ネットワークを同時に変更されるノードペアの一方および孤立ノードについて、部分ネットワークの変更後における変更前の部分ネットワークとの交流トラヒックの総和が、変更前における変更後の部分ネットワークとの交流トラヒックの総和を下回ると、前記部分ネットワークの所属変更が行われないことを特徴とする請求項５に記載のネットワーク分割方法。
【請求項７】
ネットワークを複数の部分ネットワークに分割するネットワーク分割方法において、
分割対象のネットワークにおいて、交流トラヒックが最小となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させる第１ステップと、
前記一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと他方側の部分ネットワークとの交流トラヒック、および前記他方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと一方側の部分ネットワークとの交流トラヒックを比較し、交流トラヒックが最小となる未所属ノードを、その隣接ノードと同じ部分ネットワークに所属させる第２ステップと、
ネットワーク上の全てのノードの所属が確定するまで、前記第２ステップを繰り返させる第３ステップと、
前記ネットワークが予定数の部分ネットワークに分割されるまで、前記各部分ネットワークを分割対象のネットワークと見なして前記第１ないし第３ステップを繰り返させる第４ステップとを含むことを特徴とするネットワーク分割方法。
【請求項８】
前記第２ステップでは、前記一方側の部分ネットワークへの所属が決まっているノードおよび他方側の部分ネットワークへの所属が決まっているノードの双方に隣接する未所属ノードを、他方側の部分ネットワークとの交流トラヒックが最小となれば一方側の部分ネットワークに所属させ、一方側の部分ネットワークとの交流トラヒックが最小となれば他方側の部分ネットワークに所属させることを特徴とする請求項７に記載のネットワーク分割方法。
【請求項９】
前記第２ステップにおいて、一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードの中で、他方側の部分ネットワークとの交流トラヒックが最小となる未所属ノードが複数検出されると、当該複数の未所属ノードの中で、他の未所属ノードとの交流トラヒックの総和が最小となる未所属ノードを前記一方側の部分ネットワークに所属させることを特徴とする請求項７または８に記載のネットワーク分割方法。
【請求項１０】
相互に隣接し、所属する部分ネットワークが互いに異なるノードペアについて、その一方が所属する部分ネットワークを変更することにより部分ネットワーク間の交流トラヒックが減少する場合、前記ノードペアの一方が所属する部分ネットワークを変更する第５ステップをさらに含むことを特徴とする請求項７ないし９のいずれかに記載のネットワーク分割方法。
【請求項１１】
前記第５ステップでは、前記ノードペアの一方が所属する部分ネットワークを変更することにより、所属変更前の部分ネットワークにおいて、当該ネットワーク内に隣接ノードが存在しなくなる孤立ノードが発生する場合には、前記孤立ノードの所属する部分ネットワークも同時に変更されることを特徴とする請求項１０に記載のネットワーク分割方法。
【請求項１２】
前記所属する部分ネットワークを同時に変更されるノードペアの一方および孤立ノードについて、部分ネットワークの変更後における変更前の部分ネットワークとの交流トラヒックの総和が、変更前における変更後の部分ネットワークとの交流トラヒックの総和を上回ると、前記部分ネットワークの所属変更が行われないことを特徴とする請求項１１に記載のネットワーク分割方法。
【請求項１３】
ネットワークを複数の部分ネットワークに分割するネットワーク分割プログラムにおいて、
分割対象のネットワークにおいて、交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させる第１ステップと、
前記一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと他方側の部分ネットワークとの交流トラヒック、および前記他方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと一方側の部分ネットワークとの交流トラヒックを比較し、交流トラヒックが最大となる未所属ノードを、その隣接ノードと同じ部分ネットワークに所属させる第２ステップと、
ネットワーク上の全てのノードの所属が確定するまで、前記第２ステップを繰り返させる第３ステップと、
前記ネットワークが予定数の部分ネットワークに分割されるまで、前記各部分ネットワークを分割対象のネットワークと見なして前記第１ないし第３ステップを繰り返させる第４ステップとを、コンピュータに実行させるネットワーク分割プログラム。
【請求項１４】
ネットワークを複数の部分ネットワークに分割するネットワーク分割プログラムにおいて、
分割対象のネットワークにおいて、交流トラヒックが最小となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させる第１ステップと、
前記一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと他方側の部分ネットワークとの交流トラヒック、および前記他方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと一方側の部分ネットワークとの交流トラヒックを比較し、交流トラヒックが最小となる未所属ノードを、その隣接ノードと同じ部分ネットワークに所属させる第２ステップと、
ネットワーク上の全てのノードの所属が確定するまで、前記第２ステップを繰り返させる第３ステップと、
前記ネットワークが予定数の部分ネットワークに分割されるまで、前記各部分ネットワークを分割対象のネットワークと見なして前記第１ないし第３ステップを繰り返させる第４ステップとを、コンピュータに実行させるネットワーク分割プログラム。
【請求項１５】
ネットワークを複数の部分ネットワークに分割するネットワーク分割装置において、
前記ネットワークのトポロジ情報および各ノード間のトラヒック量をネットワーク情報として取得する入力インターフェースと、
前記ネットワーク情報に基づいて、ネットワーク上の各ノードペア間の交流トラヒックを算出する交流トラヒック算出手段と、
前記交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、前記ノードペアの他方を他方側の部分ネットワークに所属させた後、ネットワーク上の他の各ノードを、部分ネットワーク間の交流トラヒックが最大となるように前記いずれかの部分ネットワークに順次に所属させることでネットワークを２分割するネットワーク分割手段とを具備し、
前記ネットワーク分割手段は、前記ネットワークが予定数の部分ネットワークに分割されるまで、各部分ネットワークに前記２分割を繰り返すことを特徴とするネットワーク分割装置。
【請求項１６】
ネットワークを複数の部分ネットワークに分割するネットワーク分割装置において、
前記ネットワークのトポロジ情報および各ノード間のトラヒック量をネットワーク情報として取得する入力インターフェースと、
前記ネットワーク情報に基づいて、ネットワーク上の各ノードペア間の交流トラヒックを算出する交流トラヒック算出手段と、
前記交流トラヒックが最小となるノードペアの一方を一方側の部分ネットワークに所属させ、前記ノードペアの他方を他方側の部分ネットワークに所属させた後、ネットワーク上の他の各ノードを、部分ネットワーク間の交流トラヒックが最小となるように前記いずれかの部分ネットワークに順次に所属させることでネットワークを２分割するネットワーク分割手段とを具備し、
前記ネットワーク分割手段は、前記ネットワークが予定数の部分ネットワークに分割されるまで、各部分ネットワークに前記２分割を繰り返すことを特徴とするネットワーク分割装置。
【請求項１】
ネットワークを複数の部分ネットワークに分割するネットワーク分割方法において、
分割対象のネットワークにおいて、交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させる第１ステップと、
前記一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと他方側の部分ネットワークとの交流トラヒック、および前記他方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと一方側の部分ネットワークとの交流トラヒックを比較し、交流トラヒックが最大となる未所属ノードを、その隣接ノードと同じ部分ネットワークに所属させる第２ステップと、
ネットワーク上の全てのノードの所属が確定するまで、前記第２ステップを繰り返させる第３ステップと、
前記ネットワークが予定数の部分ネットワークに分割されるまで、前記各部分ネットワークを分割対象のネットワークと見なして前記第１ないし第３ステップを繰り返させる第４ステップとを含むことを特徴とするネットワーク分割方法。
【請求項２】
前記第２ステップでは、前記一方側の部分ネットワークへの所属が決まっているノードおよび他方側の部分ネットワークへの所属が決まっているノードの双方に隣接する未所属ノードを、他方側の部分ネットワークとの交流トラヒックが最大となれば一方側の部分ネットワークに所属させ、一方側の部分ネットワークとの交流トラヒックが最大となれば他方側の部分ネットワークに所属させることを特徴とする請求項１に記載のネットワーク分割方法。
【請求項３】
前記第２ステップにおいて、一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードの中で、他方側の部分ネットワークとの交流トラヒックが最大となる未所属ノードが複数検出されると、当該複数の未所属ノードの中で、他の未所属ノードとの交流トラヒックの総和が最大となる未所属ノードを前記一方側の部分ネットワークに所属させることを特徴とする請求項１または２に記載のネットワーク分割方法。
【請求項４】
相互に隣接し、所属する部分ネットワークが互いに異なるノードペアについて、その一方が所属する部分ネットワークを変更することにより部分ネットワーク間の交流トラヒックが増加する場合、前記ノードペアの一方が所属する部分ネットワークを変更する第５ステップをさらに含むことを特徴とする請求項１ないし３のいずれかに記載のネットワーク分割方法。
【請求項５】
前記第５ステップでは、前記ノードペアの一方が所属する部分ネットワークを変更することにより、所属変更前の部分ネットワークにおいて、当該ネットワーク内に隣接ノードが存在しなくなる孤立ノードが発生する場合には、前記孤立ノードの所属する部分ネットワークも同時に変更されることを特徴とする請求項４に記載のネットワーク分割方法。
【請求項６】
前記所属する部分ネットワークを同時に変更されるノードペアの一方および孤立ノードについて、部分ネットワークの変更後における変更前の部分ネットワークとの交流トラヒックの総和が、変更前における変更後の部分ネットワークとの交流トラヒックの総和を下回ると、前記部分ネットワークの所属変更が行われないことを特徴とする請求項５に記載のネットワーク分割方法。
【請求項７】
ネットワークを複数の部分ネットワークに分割するネットワーク分割方法において、
分割対象のネットワークにおいて、交流トラヒックが最小となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させる第１ステップと、
前記一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと他方側の部分ネットワークとの交流トラヒック、および前記他方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと一方側の部分ネットワークとの交流トラヒックを比較し、交流トラヒックが最小となる未所属ノードを、その隣接ノードと同じ部分ネットワークに所属させる第２ステップと、
ネットワーク上の全てのノードの所属が確定するまで、前記第２ステップを繰り返させる第３ステップと、
前記ネットワークが予定数の部分ネットワークに分割されるまで、前記各部分ネットワークを分割対象のネットワークと見なして前記第１ないし第３ステップを繰り返させる第４ステップとを含むことを特徴とするネットワーク分割方法。
【請求項８】
前記第２ステップでは、前記一方側の部分ネットワークへの所属が決まっているノードおよび他方側の部分ネットワークへの所属が決まっているノードの双方に隣接する未所属ノードを、他方側の部分ネットワークとの交流トラヒックが最小となれば一方側の部分ネットワークに所属させ、一方側の部分ネットワークとの交流トラヒックが最小となれば他方側の部分ネットワークに所属させることを特徴とする請求項７に記載のネットワーク分割方法。
【請求項９】
前記第２ステップにおいて、一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードの中で、他方側の部分ネットワークとの交流トラヒックが最小となる未所属ノードが複数検出されると、当該複数の未所属ノードの中で、他の未所属ノードとの交流トラヒックの総和が最小となる未所属ノードを前記一方側の部分ネットワークに所属させることを特徴とする請求項７または８に記載のネットワーク分割方法。
【請求項１０】
相互に隣接し、所属する部分ネットワークが互いに異なるノードペアについて、その一方が所属する部分ネットワークを変更することにより部分ネットワーク間の交流トラヒックが減少する場合、前記ノードペアの一方が所属する部分ネットワークを変更する第５ステップをさらに含むことを特徴とする請求項７ないし９のいずれかに記載のネットワーク分割方法。
【請求項１１】
前記第５ステップでは、前記ノードペアの一方が所属する部分ネットワークを変更することにより、所属変更前の部分ネットワークにおいて、当該ネットワーク内に隣接ノードが存在しなくなる孤立ノードが発生する場合には、前記孤立ノードの所属する部分ネットワークも同時に変更されることを特徴とする請求項１０に記載のネットワーク分割方法。
【請求項１２】
前記所属する部分ネットワークを同時に変更されるノードペアの一方および孤立ノードについて、部分ネットワークの変更後における変更前の部分ネットワークとの交流トラヒックの総和が、変更前における変更後の部分ネットワークとの交流トラヒックの総和を上回ると、前記部分ネットワークの所属変更が行われないことを特徴とする請求項１１に記載のネットワーク分割方法。
【請求項１３】
ネットワークを複数の部分ネットワークに分割するネットワーク分割プログラムにおいて、
分割対象のネットワークにおいて、交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させる第１ステップと、
前記一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと他方側の部分ネットワークとの交流トラヒック、および前記他方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと一方側の部分ネットワークとの交流トラヒックを比較し、交流トラヒックが最大となる未所属ノードを、その隣接ノードと同じ部分ネットワークに所属させる第２ステップと、
ネットワーク上の全てのノードの所属が確定するまで、前記第２ステップを繰り返させる第３ステップと、
前記ネットワークが予定数の部分ネットワークに分割されるまで、前記各部分ネットワークを分割対象のネットワークと見なして前記第１ないし第３ステップを繰り返させる第４ステップとを、コンピュータに実行させるネットワーク分割プログラム。
【請求項１４】
ネットワークを複数の部分ネットワークに分割するネットワーク分割プログラムにおいて、
分割対象のネットワークにおいて、交流トラヒックが最小となるノードペアの一方を一方側の部分ネットワークに所属させ、ノードペアの他方を他方側の部分ネットワークに所属させる第１ステップと、
前記一方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと他方側の部分ネットワークとの交流トラヒック、および前記他方側の部分ネットワークへの所属が決まっているノードを隣接ノードとする未所属ノードと一方側の部分ネットワークとの交流トラヒックを比較し、交流トラヒックが最小となる未所属ノードを、その隣接ノードと同じ部分ネットワークに所属させる第２ステップと、
ネットワーク上の全てのノードの所属が確定するまで、前記第２ステップを繰り返させる第３ステップと、
前記ネットワークが予定数の部分ネットワークに分割されるまで、前記各部分ネットワークを分割対象のネットワークと見なして前記第１ないし第３ステップを繰り返させる第４ステップとを、コンピュータに実行させるネットワーク分割プログラム。
【請求項１５】
ネットワークを複数の部分ネットワークに分割するネットワーク分割装置において、
前記ネットワークのトポロジ情報および各ノード間のトラヒック量をネットワーク情報として取得する入力インターフェースと、
前記ネットワーク情報に基づいて、ネットワーク上の各ノードペア間の交流トラヒックを算出する交流トラヒック算出手段と、
前記交流トラヒックが最大となるノードペアの一方を一方側の部分ネットワークに所属させ、前記ノードペアの他方を他方側の部分ネットワークに所属させた後、ネットワーク上の他の各ノードを、部分ネットワーク間の交流トラヒックが最大となるように前記いずれかの部分ネットワークに順次に所属させることでネットワークを２分割するネットワーク分割手段とを具備し、
前記ネットワーク分割手段は、前記ネットワークが予定数の部分ネットワークに分割されるまで、各部分ネットワークに前記２分割を繰り返すことを特徴とするネットワーク分割装置。
【請求項１６】
ネットワークを複数の部分ネットワークに分割するネットワーク分割装置において、
前記ネットワークのトポロジ情報および各ノード間のトラヒック量をネットワーク情報として取得する入力インターフェースと、
前記ネットワーク情報に基づいて、ネットワーク上の各ノードペア間の交流トラヒックを算出する交流トラヒック算出手段と、
前記交流トラヒックが最小となるノードペアの一方を一方側の部分ネットワークに所属させ、前記ノードペアの他方を他方側の部分ネットワークに所属させた後、ネットワーク上の他の各ノードを、部分ネットワーク間の交流トラヒックが最小となるように前記いずれかの部分ネットワークに順次に所属させることでネットワークを２分割するネットワーク分割手段とを具備し、
前記ネットワーク分割手段は、前記ネットワークが予定数の部分ネットワークに分割されるまで、各部分ネットワークに前記２分割を繰り返すことを特徴とするネットワーク分割装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２０１２−２４４５７５（Ｐ２０１２−２４４５７５Ａ）
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願番号】特願２０１１−１１５７５６（Ｐ２０１１−１１５７５６）
【出願日】平成２３年５月２４日（２０１１．５．２４）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２４年１２月１０日（２０１２．１２．１０）
【国際特許分類】
【出願日】平成２３年５月２４日（２０１１．５．２４）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]