JPH0955733A

JPH0955733A - 通信網の分割方法及び通信網の分割システム

Info

Publication number: JPH0955733A
Application number: JP20623995A
Authority: JP
Inventors: Masato Matsuo; 真人松尾
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: Nippon Telegraph and Telephone Corp
Priority date: 1995-08-11
Filing date: 1995-08-11
Publication date: 1997-02-25

Abstract

(57)【要約】【課題】本発明は、信頼性向上と故障分析及び管理の
効率化のためノード間の接続形態を考慮し、複数の管理
法を反映させる通信網の分割方法の提供を目的とする。【解決手段】本発明の通信網の分割方法は、第１のク
ラスタの中の第１のノードが第１のクラスタの隣接する
第２のクラスタとの接続の度合いを表わす隣接情報を生
成する段階（ステップ１０）と、上記生成された隣接情
報に適用するクラスタ間の従属関係設定規則を判定する
段階（ステップ１２）と；上記適用された従属関係設定
規則に応じて上記第１のクラスタと上記第２のクラスタ
の中の一方を従属させるクラスタに割り当て他方を管理
するクラスタに割り当てる段階（ステップ２０）と、上
記従属させるクラスタが上記管理するクラスタに従属す
る新しいクラスタを形成する段階（ステップ２２）とか
らなる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は通信網を構成する方
法に係り、特に、網の構成が変化し得る通信網の分散管
理形態を形成する方法及びシステムに関する。

【０００２】

【従来の技術】従来、ノード群と、ノード群を接続する
リンク群とからなる通信網において、少なくとも一つの
隣接するノードから構成されるクラスタを形成すること
により網を分割する方法として、固定した通信網に対し
集中的な計算を行なう網の分割法、即ち、通信網の管理
形態が知られている。かかる管理形態では、クラスタ内
に一つの管理ノードが設けられている。

【０００３】この固定した通信網に対する集中的な計算
は、（１）網全体が把握できていること、（２）管理ノ
ードが固定されていること、及び、（３）分割の対象は
ノードであることが前提とされている。従って、上記前
提による網分割を行い得る通信網の形態は種々の形で限
定されている。

【０００４】網全体の把握とは、網分割を集中的に行な
うために、網分割を行なうノードが網全体の構成を把握
している必要があることを意味する。従って、網を構築
する過程で上記従来の管理形態を導入することは困難で
ある。また、網の拡張又は縮退等の網構成の変更毎に網
全体の分割をやり直す必要があり、分割のために必要な
コストが大きい。

【０００５】管理ノードの固定とは、分割された網を管
理又は代表する管理ノードが当該網を構成するノードと
は別の独立した専用ノードとして取り扱われることを意
味する。そのため、一度適切な箇所に適切な数の管理ノ
ードを配置した後に網構成が変化した場合、網の分割形
態と管理ノードの対応関係が崩れ、新しい管理ノードを
設けることが必要とされ、或いは、既に導入された管理
ノードが不要になる等の管理ノードの無駄が生じる。一
方、構成が変化し得る通信網の場合、一度導入された管
理ノードをそのまま利用しようとすると、網分割そのも
のが管理ノードの数や配置箇所に特化した形態となり、
適切な管理ができなくなる。

【０００６】分割の対象がノードであるとは、従来の管
理形態の対象は個々のノードの動作であることを意味す
る。従って、網分割は、例えば、分割網に含まれるノー
ドの数、管理ノードからの通信距離等のような管理対象
となるノードと管理ノードの関係で決定される。このよ
うに、従来の網分割は、本来的に網の特徴を表わす網の
構成、即ち、ノード間の接続形態を考慮した網分割とは
異なるので、大量の情報を交換している複数のノード、
即ち、ノード群が別々の管理ノードによって管理される
場合がある。従って、ノード群中のあるノードが故障し
た場合、故障分析或いはルーティング変更等の故障回避
措置を複数の管理ノードで協調して行なう必要が生じ、
適切な処置を迅速に行なえない可能性がある。

【０００７】更に、上記従来の網分割によれば、通信網
を管理し得るのは特定の１キャリアであることが暗黙的
に想定されている。従って、複数の管理者の存在を考慮
して複数の管理ポリシ（管理方策）を取り入れることが
困難である。上記従来の通信網の分割方法に対し、各ノ
ードが管理機能と呼処理機能とを有し、ノード間で協調
しながら管理権限を委譲し合う、大規模通信網における
ボトムアップ的なクラスタリング手法が知られている。
かかるボトムアップ的な分割法によれば、管理領域がボ
トムアップ的に決定されるので、網全体を把握する必要
はなく、網構成が変化し得る場合にも利用することが可
能である。また、管理ノードは、固定的ではなく、動的
に決定されるので、専用の管理ノードを設ける必要はな
い。

【０００８】

【発明が解決しようとする課題】しかしながら、上記集
中的な計算による分割法を改良するボトムアップ的な分
割管理の場合、管理ノードを決定するためのロジックに
おいてノード間の接続関係は考慮されていない。また、
網の初期構成に対する管理ノードの集約化だけを対象と
しているので、網構成の変化に追従して管理ノードを動
的に変更することは困難である。更に複数の管理ポリシ
を取り入れることは想定されていない。

【０００９】従って、従来の大規模通信網の分割管理に
は以下の問題点がある。第１に、従来の大規模通信網の
分割管理は、網分割がノード間の接続形態を考慮してい
ないので、信頼性向上、故障分析や管理の効率化を図る
ことが困難であり、第２に、網構成が自由に変更され得
る通信網には適用することができず、第３に、複数の管
理ポリシを取り入れることが困難である。

【００１０】本発明は、上記従来の大規模通信網の分割
管理の問題点に鑑み、各ノードが管理機能と呼処理機能
とを有し、ノード間で協調しながら管理権限を委譲し合
う、大規模通信網におけるボトムアップ的なクラスタリ
ング手法において、信頼性向上と、故障分析及び管理の
効率化のために、ノード間の接続形態を考慮し、かつ、
複数の管理ポリシを反映させる通信網の分割方法及び分
割システムの提供を目的とする。

【００１１】更に、本発明は、通信網の網構成の変化に
容易に追従し得る通信網の分割方法及び分割システムの
提供を目的とする。

【００１２】

【課題を解決するための手段】図１は本発明の原理説明
図である。本発明の通信網の分割方法は、複数のノード
と、上記複数のノードの間を接続するリンクとからなる
通信網において、第１のノードが隣接する第２のノード
を認識し、上記第１のノードと上記隣接する第２のノー
ドが情報を交換する隣接関係認識段階（ステップ１）
と；上記第１のノードと上記隣接する第２のノードがク
ラスタを形成するクラスタ形成段階（ステップ２）とか
らなる。

【００１３】本発明の通信網の分割方法は、ノード間の
接続形態を考慮し、かつ、複数の管理ポリシを反映させ
た網分割を実現するために、上記隣接関係認識段階（ス
テップ１）は、第１のクラスタの中の上記第１のノード
が上記第１のクラスタの隣接する第２のクラスタとの接
続の度合いを表わす隣接情報を生成する隣接情報生成段
階（ステップ１０）と、上記生成された隣接情報に適用
するクラスタ間の従属関係設定規則を判定する従属関係
判定段階（ステップ１２）とを更に有し；上記クラスタ
形成段階（ステップ２）は、上記適用された従属関係設
定規則に応じて、上記第１のクラスタと上記第２のクラ
スタの中の一方を従属させるクラスタに割り当て、他方
を管理するクラスタに割り当てる段階（ステップ２０）
と、上記従属させるクラスタが上記管理するクラスタに
従属する新しいクラスタを形成する段階（ステップ２
２）とからなる。

【００１４】更に、本発明の通信網の分割方法は、上記
クラスタ形成段階（ステップ２）において形成された上
記新しいクラスタを新たな第１のクラスタとし更なる新
しいクラスタを形成する場合に、上記隣接関係認識段階
（ステップ１）と、上記クラスタ形成段階（ステップ
２）を繰り返し実行させるクラスタ階層化段階（ステッ
プ３）を更に有する。

【００１５】更に、上記隣接情報生成段階（ステップ１
０）は、上記第１のノード毎に全ての上記第２のクラス
タとの相対的な上記接続の度合いを表わす隣接度からな
る上記隣接情報を生成する。上記の如く、本発明の通信
網の分割方法は、従来のボトムアップ的なクラスタリン
グ方法に基づき、更に、クラスタを形成する際に、個々
のクラスタの隣接情報を元に従属関係を設定することに
よって故障分析や管理を効率的に行なうためのクラスタ
を形成し、かつ、複数の管理ポリシをクラスタ形成に反
映させる点に特徴がある。

【００１６】本発明によれば、従属関係の設定規則に
は、例えば、隣接する全てのクラスタが持つクラスタ情
報、及び、クラスタ間を接続するリンクの容量比、距離
比から求められる隣接度からなる隣接情報に基づいてい
る従属関係設定規則と、各管理ポリシに基づくクラスタ
構成時の制限及び従属規則等が導入されている。

【００１７】本発明の通信網の分割方法は、上記従属関
係判定段階（ステップ１２）が、適用結果を得るため予
め定められた優先度に従って上記従属関係設定規則を適
用する従属関係設定規則適用段階（ステップ１２０）
と；上記適用結果と、上記隣接する第２のクラスタから
の従属関係の設定申請とに基づいて、採用する従属関係
を判定する採用従属関係判定段階（ステップ１２２）と
を更に有する。これにより、クラスタ自体が保持してい
る隣接情報と、従属関係設定規則の適用状況と、他のク
ラスタからの従属関係の設定申請の状況とに基づいて、
現在の状況に最適な従属関係設定規則を選択することが
できる。更に、本発明の通信網の分割方法は、上記従属
関係判定段階（ステップ１２）が、上記従属関係設定規
則を判定した後、上記隣接情報が変化しているかどうか
を判定し、上記隣接関係が変化していると判定された場
合、上記変化した隣接情報に適用するクラスタ間の従属
関係設定規則を再び判定する従属関係再判定段階（ステ
ップ１２４）を更に有する。従って、クラスタリング過
程で刻々と変化する接続関係に対し意図したクラスタリ
ングを行なうことが可能になる。

【００１８】更に、本発明の通信網の分割法によれば、
上記クラスタ形成段階（ステップ２）が上記従属させる
クラスタに割り当てられた下位階層のクラスタが上記新
しいクラスタを形成する際に適用された上記下位階層の
クラスタに関する情報を保存する段階（ステップ２４）
を更に有し、上記通信網においてクラスタが形成された
後、最下位階層から順次上記下位階層のクラスタのノー
ドの隣接情報の変化を検知する隣接情報変化検出段階
と、上記下位階層のクラスタを上記第１のクラスタとし
て、上記隣接関係判定段階と、上記クラスタ形成段階を
実行するクラスタ再分割段階（ステップ４）を更に有す
る。

【００１９】上記クラスタ再分割段階は、上記変化を検
出された隣接情報に適用し得るクラスタ間の従属関係設
定規則の判定後、上記下位階層のクラスタに関する情報
として保存された上記従属関係設定規則よりも優先度の
高い従属関係設定規則を適用できるかどうかを判定し、
優先度の高い従属関係設定規則が適用できないと判定さ
れた場合、上記下位階層のクラスタに関する情報として
保存された上記従属関係設定規則を上記変化を検出され
た下位階層のクラスタに対する従属関係設定規則として
維持できるかどうかを判定する従属関係確認段階を有す
る。上記クラスタ再分割段階は、更に、優先度の高い従
属関係設定規則が適用できると判定された場合、上記変
化が検出された下位階層のクラスタが属する上位階層の
クラスタを全て解消し、上記適用できるとされた優先度
の高い従属関係設定規則を適用し、新たなクラスタを形
成するよう上位クラスタ形成段階を実行し、維持できる
と判断された場合、上記変化が検出された下位階層の次
の階層のクラスタに対し上記従属関係確認段階を繰り返
し実行し、維持できないと判断された場合、上記変化が
検出された下位階層のクラスタが属する上位階層のクラ
スタを全て解消し、上記隣接情報変化検出段階に戻る段
階を有する。

【００２０】かかる本発明の通信網の分割方法の再分割
段階により、クラスタを構成するサブクラスタはそのク
ラスタを構成する際に適用した従属関係設定規則と隣接
情報を常に保持し、隣接情報の変化を検知して従属関係
設定規則を再適用することができるので、網構成の変化
に容易に追従し得るようになる。即ち、個々のクラスタ
は自律的に、現状態を常に更新し、最適な従属関係を採
用するよう動作することが可能である。

【００２１】

【発明の実施の形態】以下に添付図面を参照して本発明
の実施例について説明する。図２は本発明が適用される
通信網の構成を説明するための図である。同図に示すよ
うに、通信網１０１は、ノード群１０２と、ノード群の
ノード間を接続するリンク群１０３とにより構成されて
いる。

【００２２】図３は本発明の一実施例の通信網分割シス
テムが適用される通信網のクラスタ構成を説明する図で
ある。クラスタは少なくとも一つの隣接するノードから
構成され、網分割前の初期状態では各ノードが一つのク
ラスタに対応する。図３には、クラスタリングが途中ま
で行なわれた状態のクラスタリング構成が示されてい
る。同図において、クラスタ２１１はノード２０１とノ
ード２０２から、クラスタ２１２はノード２０３とノー
ド２０４から、クラスタ２１４はクラスタ２１１とクラ
スタ２１２から、クラスタ２１３はノード２０６とノー
ド２０７から、クラスタ２１５はノード２０５から、ク
ラスタ２１６はノード２０８から夫々構成されている。

【００２３】例えば、クラスタ２１１は、クラスタ２１
２とクラスタ２１３に「隣接」するクラスタである。ク
ラスタ２１２は、クラスタ２１１とクラスタ２１５に
「隣接」している。このように、「隣接」とは、クラス
タとクラスタがリンクを介し直接的に接続されている状
態を示している。

【００２４】クラスタ２１１では、ノード２０１がノー
ド２０２に従属している。この場合、ノード２０２をク
ラスタ２１１を代表する代表ノードと呼ぶ。同様に、ク
ラスタ２１２の代表ノードはノード２０３であり、クラ
スタ２１３の代表ノードはクラスタ２０６である。

【００２５】分割処理はノード単位及びクラスタ単位の
両方で想定することができ、クラスタ単位での処理は、
そのクラスタを代表する代表ノードに対する処理として
取り扱うことによって、ノードとクラスタを統一的に取
り扱うことが可能である。例えば、クラスタ２１１が隣
接クラスタ、即ち、クラスタ２１２及びクラスタ２１３
と情報交換を行なう場合、クラスタ２１１の代表ノード
２０２が、クラスタ２１２の代表ノード２０３及びクラ
スタ２１３の代表ノード２０６と、夫々のクラスタ内の
リンク又はクラスタ間を接続するリンクを介して情報交
換する。

【００２６】複数のクラスタ、例えば、クラスタ２１１
とクラスタ２１２が新たなクラスタ２１４を形成する場
合、元のクラスタの代表ノード、即ち、ノード２０２又
はノード２０３の中のいずれか一つが新たに形成された
クラスタ２１４の代表ノードになる。クラスタは、少な
くとも一つのノードとクラスタとから構成され、一つの
代表ノードを含んでいる。新しいクラスタは、一方のク
ラスタの代表ノードと別のクラスタの代表ノードとの間
に、上記の如くの従属関係が生じる場合に形成される。
本発明ではこのように代表ノードがそのクラスタ内に属
するノード及びクラスタを管理する管理クラスタとな
り、代表ノードどうしが従属関係を設定することで階層
的な管理形態を実現する。新しいクラスタが形成された
場合に、新しいクラスタの代表ノードを含むクラスタが
管理クラスタと呼ばれ、それ以外のクラスタは従属クラ
スタと呼ばれる。例えば、同図において、ノード２０３
が新しいクラスタの代表ノードであり、クラスタ２１２
が管理クラスタ、クラスタ２１１が従属クラスタと呼ば
れる。

【００２７】図４は本発明の一実施例の通信網分割シス
テムの構成図である。同図において、クラスタ２は、隣
接クラスタ間リンク６を介して隣接クラスタ群４と隣接
し、代表ノード１０と、クラスタ内ノード群１２と、ク
ラスタ内リンク群１４とから構成される。代表ノード１
０は、クラスタ内ノード群１２から選択された一つのノ
ードである。

【００２８】例えば、クラスタ２は、代表ノード１０だ
けから構成される場合もある。その場合、クラスタ内ノ
ード群１２の他のノード、及びクラスタ内リンク群１４
は存在しない。クラスタ内ノード群１２の中の一つのノ
ードである代表ノード１０は、クラスタ内リンク群１４
及び隣接クラスタ間リンク６を介して隣接クラスタ群４
を認識し、隣接クラスタ群４との間で隣接情報、クラス
タ情報等を授受する情報送受信部２０と；従属関係設定
規則部２４を管理し、現在のクラスタの状態に関し適用
可能な従属関係設定規則部２４の従属関係設定規則を判
別する適用規則判断部２２と；当該クラスタ２自体の隣
接情報を算出し、現在の隣接情報及び適用規則、他のク
ラスタから得られた従属関係申請の状況等の現在の処理
状況を管理する状態保持部２６と；状態保持部２６で管
理された情報を参照し、規則の再適用や現状態の更新、
従属関係設定処理への移行を制御する従属関係設定判断
制御部２８と；従属関係設定処理を行なう従属関係設定
処理部３０とからなる。

【００２９】従属関係設定処理部３０は、当該クラスタ
が他のクラスタに従属する従属クラスタである場合に従
属処理を行なう従属処理部３２と、当該クラスタが管理
クラスタである場合に管理処理を行なう管理処理部３４
とからなる。図５は本発明の一実施例の通信網分割シス
テムの網分割動作のフローチャートである。

【００３０】情報送受信部２０は、隣接クラスタ群４を
認識し、当該クラスタ２自体のクラスタを識別するクラ
スタ情報を通知する（ステップ２００）。ここで、クラ
スタ情報は、例えば、当該クラスタ２を特定できるよう
階層的なクラスタ構造を反映したクラスタ名を含む。

【００３１】状態保持部２６は、情報送受信部２０を介
して、全隣接クラスタからの情報を集計し、隣接情報を
算出し、かかる算出された隣接情報を現状態として記録
する（ステップ２０２）。隣接情報としては、例えば、
隣接クラスタ群４を構成するノードのリストからなる隣
接リスト、当該クラスタ２が有する隣接クラスタ間リン
ク群６の全体容量に対する個々の隣接クラスタへのリン
クの容量比（隣接度）を用いることができる。

【００３２】従属関係設定判断制御部２８からの指示に
従って、適用規則判断部２２は、従属関係設定規則部２
４の規則の適用を試み、その結果を状態保持部２６に記
録する（ステップ２０４）。本発明の一実施例によれ
ば、以下の従属関係設定規則が隣接クラスタ毎に当ては
められる。規則の優先度は、規則１、規則２、規則３の
順序である。

【００３３】規則１：隣接度≧α（０．５≦α≦１）な
らば、当該クラスタは隣接クラスタに従属する。規則２：当該クラスタの隣接リストにおいて、隣接クラ
スタの隣接リストに含まれている要素の比率がβ（０．
５≦β≦１）以上ならば、当該クラスタと隣接クラスタ
との間に従属関係を設定する。

【００３４】規則３：隣接クラスタの隣接リストの中
で、一致している部分の隣接度がγ（０．５≦γ≦１）
以上のクラスタが存在するならば、当該クラスタはその
中の何れかのクラスタを従属する。上記規則２及び規則３を適用する場合、隣接クラスタの
隣接リスト等の隣接情報を情報送受信部２０を介して取
得する。

【００３５】従属関係設定判断制御部２８は、新たに情
報送受信部２０を介して得られた隣接情報に変化がある
かどうかが判定され（ステップ２０６）、隣接状態に変
化がある場合、ステップ２０２に戻り、隣接情報を再び
算出し、規則の適用をやり直す。

【００３６】従属関係設定判断制御部２８は、新たに得
られた隣接情報に変化がない場合、適用規則判断部２２
における従属関係設定規則の適用結果を受け、状態保持
部２６を参照し、適用規則判断部２２で選択された規則
と、その時点で隣接クラスタ群４から提案されている従
属関係設定申請の中で適用優先度が高いものを選択する
（ステップ２０８）。

【００３７】従属関係設定判断制御部２８は、採用でき
る規則があるかどうかを判定し（ステップ２１０）、採
用できるものがひとつも存在しない場合、現状態を保持
し（ステップ２１２）、隣接クラスタ群４に変化が起き
るのを待機する（ステップ２１４）。隣接クラスタ群４
からの情報通知があればステップ２０２に戻る。

【００３８】採用できる規則が存在する場合、従属関係
設定処理部３０は、採用された規則に基づいて従属関係
を設定する。採用した規則が規則１又は２であるかどう
かを判定し、規則１又は２の場合、従属処理部３２は従
属申請、それ以外の場合、管理申請を行い、他のクラス
タからの管理申請又は従属申請を考慮して、当該クラス
タが管理クラスタ又は従属クラスタの何れになるかを判
定し（ステップ２１６）、従属クラスタであると判定さ
れた場合、従属処理部３２が従属関係を設定し（ステッ
プ２１８）、新しいクラスタを形成するよう当該クラス
タ２の保持する隣接情報を管理クラスタに転送し（ステ
ップ２２０）、クラスタリング処理を終了する。

【００３９】当該クラスタは管理クラスタであると判定
された場合、管理処理部３４は従属関係を設定する（ス
テップ２２２）。次いで、管理処理部３４は、従属する
クラスタから通知された隣接情報を収集し、当該クラス
タ２の隣接情報に加え、新たに形成されるクラスタに対
するクラスタ構成リストと隣接情報を作成し、状態保持
部２６に記憶させ、隣接クラスタとのクラスタリングを
行なうための新たなクラスタ情報を隣接クラスタに通知
する（ステップ２２４）。終了条件かどうかを判定し
（ステップ２２６）、終了条件の場合、クラスタリング
を終了する。終了条件を満たさない場合、ステップ２０
２に戻ってクラスタリング処理を継続する。

【００４０】尚、上記ステップ２１６において従属申請
が行なわれ、隣接クラスタ群４からも従属申請を受けた
場合には、例えば、隣接度の小さいクラスタを管理クラ
スタとなるよう定めることによって、管理クラスタ又は
従属クラスタのいずれであるかを判定することができ
る。

【００４１】図６は、図３に示した通信網１０１に対し
リンク群に適当なリンク容量を与え、上記本発明の一実
施例の通信網分割システムの網分割動作を実行して得ら
れた通信網の一例を示す図である。本発明の一実施例を
図３の通信網１０１に適用することにより、図６に示す
ような接続関係に基づいた階層的なクラスタが形成さ
れ、管理ポリシに基づいて任意の階層のクラスタを単位
として網分割が行なえる。

【００４２】図５に示した上記本発明の一実施例の通信
網分割システムの網分割動作の変形例を以下に説明す
る。上記ステップ２００において情報送受信部２０によ
って通知されるクラスタ情報は、クラスタを識別するた
めの階層的なクラスタ構造を反映させたクラスタ名に加
えて、同じ管理形態にするかどうかを指定するクラスタ
リングソース名と、無条件に同じクラスタにすることを
明示するクラスタキーと、必ず代表ノードになることを
明示する代表ノード属性を有してもよい。

【００４３】更に、上記従属関係設定規則の規則０とし
て、規則０：同一クラスタキーを持つ場合には、接続形態と
は無関係に無条件でクラスタリングを行なう。を加えて
もよい。

【００４４】かかる規則０が採用された場合、ステップ
２１８において従属処理部３２が起動され、従属申請が
行なわれる。更に、当該クラスタの代表ノード属性に対
し代表ノードが指定された場合、必ず代表ノードになる
よう定め得る。従って、上記本発明の一実施例の変形に
よれば、従属関係設定規則適用段階における従属関係設
定と、上記クラスタ形成段階における上記管理するクラ
スタのクラスタの決定は、管理ポリシに基づくクラスタ
構成時の制限又は従属規則を含む上記従属関係設定規則
に基づいて行なわれる。

【００４５】次いで、本発明の他の実施例による通信網
の再分割法について説明する。通信網を再分割するため
には、一旦分割された現状態を保持する必要がある。こ
のため、再分割法では、図５で説明した本発明の一実施
例の通信網の分割方法のステップ２２４において新たな
クラスタを作成したときの情報は網分割フェーズとして
記録され、この網分割フェーズとは別に再クラスタリン
グフェーズ１及び２をが設けられている。

【００４６】図７は本発明の他の実施例の通信網の再分
割法における再分割判断法を説明するフローチャートで
ある。ステップ３００：情報送受信部２０はクラスタ情報の通
知を受けると、現在の再クラスタリングフェーズにおけ
る当該クラスタ２に関し、隣接状態の変化を調べる。こ
こで、再クラスタリングフェーズが設定されていない場
合には、個々のノードの階層に対するクラスタリングと
して処理される。隣接状態に変化がある場合には、状態
保持部２６において隣接情報を更新し記録する。ここで
更新、記録された情報は、再クラスタリングフェーズ１
として、通常の網分割段階で記録された情報とは別個に
記録される。隣接状態に変化がない場合には、再分割の
対象となるクラスタをより上位のクラスタに変更して処
理を継続する。

【００４７】ステップ３０２：適用規則判断部２２は、
現在の再クラスタリングフェーズのラスタ階層で適用し
ている従属関係規則よりも適用優先度が高い規則が適用
できるかどうかを調べ、適用できない場合には、ステッ
プ３０４へ進む。より高い規則が適用できる場合には、
ステップ３０８に進む。

【００４８】ステップ３０４：新たな隣接情報に対し、
現在の再クラスタリングフェーズのクラスタ階層で既設
の従属関係が維持できるかどうかを調べる。維持できる
場合はステップ３０６へ進む。維持できない場合にはス
テップ３１０へ進む。ステップ３０６：上位クラスタへ隣接情報を通知し、上
位クラスタ処理を移行し、上位階層でのクラスタ情報を
隣接情報の変化をもたらした隣接クラスタへ通知する。
上位クラスタは、サブクラスタから受けた隣接情報に基
づいてステップ３００の処理を行なう。

【００４９】ステップ３０８：適用優先度の高い規則が
適用されるので、既設の従属関係を解消し、従属関係の
新設を行なうようステップ３１４に進む。ステップ３１０：既設の従属関係を維持できないので、
既設の従属関係を解消し、他の規則を適用するようステ
ップ３１２に進む。

【００５０】ステップ３１２：再クラスタリングフェー
ズ１で更新された隣接情報等に基づいて再クラスタリン
グフェーズ２に移行する。再クラスタリングフェーズ２
は、既設の従属関係を参照することなく、再クラスタリ
ングフェーズ１の隣接情報だけに基づいてクラスタリン
グを行なう。クラスタ情報を更新し、隣接クラスタへク
ラスタ情報を通知し、図５に示した通常の網分割法を再
クラスタリングフェーズ２で実行する。再クラスタリン
グフェーズ２では、他の規則が適用できるかどうかを判
定し、他の規則が適用できる場合は、その規則に基づい
てクラスタリングを行なう。一方、他の規則が適用でき
ない場合は、新たな隣接情報の変化を検出した後、ステ
ップ３００に戻り再クラスタリングフェーズ１を実行す
る。

【００５１】ステップ３１４：再クラスタリングフェー
ズ１で更新された隣接情報等に基づいて再クラスタリン
グフェーズ２に移行する。再クラスタリングフェーズ２
は、既設の従属関係を参照することなく、再クラスタリ
ングフェーズ１の隣接情報だけに基づいてクラスタリン
グを行なう。クラスタ情報を更新し、隣接クラスタへク
ラスタ情報を通知し、図５に示した通常の網分割法を再
クラスタリングフェーズ２で実行する。従属関係設定を
行なうことが予め定められているので、従属関係の新設
を行なう。再クラスタリングフェーズ１のクラスタがこ
の再クラスタリングフェーズ２からの従属関係申請を受
けた場合には、図９に記載されたステップ３５０に進
む。

【００５２】図８は本発明の他の実施例の再分割法にお
いて従属関係を解消した場合の管理クラスタ処理のフロ
ーチャートである。上位クラスタに対しクラスタ解消の
旨を通知する（ステップ３３０）。クラスタ解消の通知
を受けた上位クラスタは、その階層で管理するサブクラ
スタにクラスタ解消の旨を通知し、サブクラスタとの従
属関係を解消することで、その階層でのクラスタを解消
する（ステップ３３２）。

【００５３】クラスタ解消の旨を受けたクラスタは、ス
テップ３１２の再クラスタリングフェーズ２におけるク
ラスタリングの処理を実行し（ステップ３３４）、ステ
ップ３３０に戻る。図９は本発明の他の実施例の再分割
法において従属関係を新設する場合の相手側の再クラス
タリングフェース１における処理のフローチャートであ
る。

【００５４】申請を受けたクラスタは、従属関係設定判
断制御部２８において現在の再クラスタ階層で従属関係
設定申請を受けるかどうかを判断する（ステップ３５
０）。既設の従属関係よりも優先度が同じか低ければ、
申請を拒否してステップ３０６へ進む（ステップ３５
２）。当該クラスタ自体が従属関係を設定している規則
よりも適用優先度が高ければステップ３０８に進む（ス
テップ３５４）。

【００５５】以下では、図１０乃至１２を用いて上記本
発明の他の実施例の通信網の再分割方法を適用して得ら
れる通信網の変化を説明する。図１０は、本発明の一実
施例の網分割法により得られた通信網の一例を示す図で
あり、図６に示した通信網に対し、ノード９０１だけか
ら構成されるクラスタ９０５及びリンク群９０２がノー
ド９０３及びノード９０４に隣接させる形で追加されて
いる。図１１は、図７乃至９に示された本発明の他の実
施例による再分割法を図１０に示した通信網に対し適用
した場合に得られるクラスタ再構成状況の経過を表わす
図である。一方、図１２は、上記再分割法を適用して得
られた最終的な通信網を示す図である。

【００５６】最初に、ステップ３００においてノード９
０３、ノード９０４は、ノード９０１からのクラスタ情
報の受信によりノード自身の隣接情報の変化を調べる。
ノード９０４は隣接情報の変化によってクラスタ５０６
を維持できなくなるので、ステップ３１０においてクラ
スタ５０６を解消する。一方、ノード９０３は隣接情報
の変化によって既存の従属関係を維持できなくなるの
で、ステップ３０８においてクラスタ５０４を解消す
る。

【００５７】ステップ３１４において、ノード９０１は
隣接するクラスタであるノード９０３とノード９０４の
中で、ノード９０４と従属関係を結ぶ。この時点で通信
網１０１は、図１１に示すように、ノード９０４とノー
ド９０１からなるクラスタ１００１と、ノード９０３だ
けで構成されるクラスタ１００２と、クラスタ５０１
と、クラスタ５０２とから構成されている。

【００５８】クラスタ５０６が解消されたことによっ
て、クラスタ１００１と、クラスタ１００２と、クラス
タ５０１は、再クラスタリングフェーズ２にあり、クラ
スタ１００１及びクラスタ５０１から新たなクラスタ情
報を受けているクラスタ５０５に含まれるノード群は、
再クラスタリングフェーズ１にあり、ステップ３００乃
至３０６を繰り返し実行し、クラスタ５０５を維持して
いる。

【００５９】次いで、クラスタ１００２は、クラスタ１
００１のクラスタ情報を受け、クラスタ１００１との新
たな従属関係の設定を判断し、新たなクラスタ１１０１
を構成する（ステップ３１４）。更に、クラスタ１１０
１とクラスタ５０１が従属関係を設定し、クラスタ１１
０２を構成する（ステップ３１４）。

【００６０】更に、本発明の他の実施例による通信網の
再分割法によれば、リンク容量の変更、リンク又はノー
ドの削除によって網構成に変更が生じた場合にも、隣接
情報の更新をトリガとして同様に対応することが可能で
ある。尚、上記本発明の実施例の説明にされた通信網１
０１のリンク群１０３は、例えは、ＡＴＭ網の仮想パ
ス、或いは、仮想チャネルと置換してもよい。

【００６１】

【発明の効果】上記説明の如く、本発明によれば、ノー
ド間の接続形態を考慮した従属関係設定規則を扱い、更
に、適用優先度を設定し、接続形態がより良く反映され
た従属関係が設定されるので、ノード間の接続形態を十
分考慮した網分割が実現され、通信網の故障分析や管理
の効率化が図られ、信頼性の向上が得られる。

【００６２】更に、管理者の管理ポリシを反映させた従
属関係設定規則を併用することにより、網分割に際し管
理者の意図を反映させた管理形態が得られる。更に、既
存の従属関係に基づいて、隣接情報の更新に応じて従属
関係設定規則の最適用を行なうことにより、局所的な対
応だけで網構成の変化に追従できるという利点が得られ
る。

【図面の簡単な説明】

【図１】本発明の原理説明図である。

【図２】本発明が適用される通信網の構成の説明図であ
る。

【図３】本発明の一実施例の通信網分割システムが適用
される通信網のクラスタ構成の説明図である。

【図４】本発明の一実施例の通信網分割システムの構成
図である。

【図５】本発明の一実施例の通信網分割システムの網分
割動作のフローチャートである。

【図６】図３に示した通信網に対し適当なリンク容量を
与え、本発明の一実施例の網分割動作を実行して得られ
た通信網の一例を示す図である。

【図７】本発明の他の実施例の通信網の再分割法におけ
る再分割判断法を説明するフローチャートである。

【図８】本発明の他の実施例による従属関係を解消した
場合の管理クラスタ処理のフローチャートである。

【図９】本発明の他の実施例の再分割法において従属関
係を新設する場合の相手側の再クラスタリングフェーズ
１における処理のフローチャートである。

【図１０】本発明の一実施例の網分割法により得られた
通信網の一例を示す図である。

【図１１】本発明の他の実施例による再分割法を図１０
に示した通信網に対し適用した場合に得られるクラスタ
再構成状況の経過を表わす図である。

【図１２】本発明の他の実施例による再分割法を図１０
に示した通信網に対し適用して得られた最終的な通信網
を示す図である。

【符号の説明】

２クラスタ４隣接クラスタ群６隣接クラスタ間リンク１０代表ノード１２クラスタ内ノード群１４クラスタ内リンク群２０情報送受信部２２適用規則判断部２４従属関係設定規則部２６状態保持部２８従属関係設定判断制御部３０従属関係設定処理部３２従属処理部３４管理処理部１０１通信網１０２ノード群１０３リンク群２０１，２０２，２０３，２０４，２０５，２０６，２
０７，２０８ノード２１１，２１２，２１３，２１４，２１５，２１６
クラスタ

Claims

【特許請求の範囲】

【請求項１】複数のノードと、上記複数のノードの間
を接続するリンクとからなる通信網において、第１のノ
ードが隣接する第２のノードを認識し、上記第１のノー
ドと上記隣接する第２のノードが情報を交換する隣接関
係認識段階と、上記第１のノードと上記隣接する第２の
ノードがクラスタを形成するクラスタ形成段階とからな
る、通信網の分割方法であって、上記隣接関係認識段階は、第１のクラスタの中の上記第
１のノードが上記第１のクラスタの隣接する第２のクラ
スタとの接続の度合いを表わす隣接情報を生成する隣接
情報生成段階と、上記生成された隣接情報に適用するクラスタ間の従属関
係設定規則を判定する従属関係判定段階とを更に有し、上記クラスタ形成段階は、上記適用された従属関係設定
規則に応じて、上記第１のクラスタと上記第２のクラス
タの中の一方を従属させるクラスタに割り当て、他方を
管理するクラスタに割り当てる段階と、上記従属させる
クラスタが上記管理するクラスタに従属する新しいクラ
スタを形成する段階とからなる、通信網の分割方法。
【請求項２】上記クラスタ形成段階において形成され
た上記新しいクラスタを新たな第１のクラスタとし、更
なる新しいクラスタを形成するため上記隣接関係認識段
階と、上記クラスタ形成段階を繰り返し実行するクラス
タ階層化段階を更に有する請求項１記載の通信網の分割
方法。
【請求項３】上記隣接情報生成段階において生成され
る上記隣接情報は、上記第１のノード毎に全ての上記第
２のクラスタとの相対的な上記接続の度合いを表わす隣
接度を有する請求項２記載の通信網の分割方法。
【請求項４】上記従属関係判定段階は、適用結果を得
るため予め定められた優先度に従って上記従属関係設定
規則を適用する従属関係設定規則適用段階と；上記適用
結果と、上記隣接する第２のクラスタからの従属関係の
設定申請とに基づいて、採用する従属関係を判定する採
用従属関係判定段階とからなる請求項３記載の通信網の
分割方法。
【請求項５】上記クラスタ形成段階は、上記従属させ
るクラスタに割り当てられた下位階層のクラスタが上記
新しいクラスタを形成する際に適用された上記下位階層
のクラスタに関する情報を保存する段階を更に有し、上記通信網においてクラスタが形成された後、最下位階
層から順次上記下位階層のクラスタのノードの隣接情報
の変化を検知する隣接情報変化検出段階を実行し、上記
下位階層のクラスタを上記第１のクラスタとして上記隣
接関係判定段階及び上記クラスタ形成段階を実行するク
ラスタ再分割段階を更に有する、請求項３記載の通信網
の分割方法。
【請求項６】上記クラスタ再分割段階は、上記変化を検出された隣接情報に適用し得るクラスタ間
の従属関係設定規則の判定後、上記下位階層のクラスタ
に関する情報として保存された上記従属関係設定規則が
上記変化が検出された下位階層のクラスタに適用する従
属関係設定規則として維持できるかどうかを判定する従
属関係確認段階と；維持できると判定された場合、上記
変化が検出された下位階層の次の階層のクラスタに対し
上記従属関係確認段階を繰り返し実行し、維持できない
と判断された場合、上記変化が検出された下位階層のク
ラスタが属する上位階層のクラスタを全て解消し、上記
隣接情報変化検出段階に戻る段階とを更に有する請求項
５記載の通信網の分割方法。
【請求項７】上記従属関係判定段階は、適用結果を得
るため予め定められた優先度に従って上記従属関係設定
規則を適用する従属関係設定規則適用段階と；上記適用
結果と、上記隣接する第２のクラスタからの従属関係の
設定申請とに基づいて、採用する従属関係を判定する採
用従属関係判定段階とからなる請求項５記載の通信網の
分割方法。
【請求項８】上記クラスタ再分割段階は、上記変化を検出された隣接情報に適用し得るクラスタ間
の従属関係設定規則の判定後、上記下位階層のクラスタ
に関する情報として保存された上記従属関係設定規則よ
りも優先度の高い従属関係設定規則を適用できるかどう
かを判定し、優先度の高い従属関係設定規則が適用でき
ないと判定された場合、上記下位階層のクラスタに関す
る情報として保存された上記従属関係設定規則を上記変
化を検出された下位階層のクラスタに対する従属関係設
定規則として維持できるかどうかを判定する従属関係確
認段階と；優先度の高い従属関係設定規則が適用できる
と判定された場合、上記変化が検出された下位階層のク
ラスタが属する上位階層のクラスタを全て解消し、上記
適用できるとされた優先度の高い従属関係設定規則を適
用し、新たなクラスタを形成するよう上位クラスタ形成
段階を実行し、維持できると判断された場合、上記変化
が検出された下位階層の次の階層のクラスタに対し上記
従属関係確認段階を繰り返し実行し、維持できないと判
断された場合、上記変化が検出された下位階層のクラス
タが属する上位階層のクラスタを全て解消し、上記隣接
情報変化検出段階に戻る段階とを更に有する請求項７記
載の通信網の分割方法。
【請求項９】上記従属関係判定段階は、上記従属関係
設定規則を判定した後、上記隣接情報が変化しているか
どうかを判定し、上記隣接関係が変化していると判定さ
れた場合、上記変化した隣接情報に適用するクラスタ間
の従属関係設定規則を再び判定する従属関係再判定段階
を更に有する請求項４又は７記載の通信網の分割方法。
【請求項１０】上記従属関係設定規則適用段階におけ
る従属関係設定と、上記クラスタ形成段階における上記
管理するクラスタの決定は、管理方策に応じたクラスタ
構成時の制限又は従属規則を含む上記従属関係設定規則
に基づいて行なわれる請求項４又は７記載の通信網の分
割方法。
【請求項１１】上記採用従属関係判定段階において採
用し得る従属関係が得られない場合、上記隣接する第２
のクラスタの変化に応じて通知された情報に基づいて上
記隣接情報を算出し、上記従属関係判定段階を再び実行
させる段階を更に有する請求項４又は７記載の通信網の
分割方法。
【請求項１２】複数のノードと、上記複数のノードの
間を接続する論理的に設定された仮想パスとからなる通
信網において、第１のノードが隣接する第２のノードを
認識し、上記第１のノードと上記隣接する第２のノード
が情報を交換する隣接関係認識段階と、上記第１のノー
ドと上記隣接する第２のノードがクラスタを形成するク
ラスタ形成段階とからなる、通信網の分割方法であっ
て、上記隣接関係認識段階は、第１のクラスタの中の上記第
１のノードが上記第１のクラスタの隣接する第２のクラ
スタとの接続の度合いを表わす隣接情報を生成する隣接
情報生成段階と、上記生成された隣接情報に適用するクラスタ間の従属関
係設定規則を判定する従属関係判定段階とを更に有し、上記クラスタ形成段階は、上記適用された従属関係設定
規則に応じて、上記第１のクラスタと上記第２のクラス
タの中の一方を従属させるクラスタに割り当て、他方を
管理するクラスタに割り当てる段階と、上記従属させる
クラスタが上記管理するクラスタに従属する新しいクラ
スタを形成する段階とからなる、通信網の分割方法。
【請求項１３】複数のノードと、上記複数のノードの
間を接続する論理的に設定された仮想チャネルとからな
る通信網において、第１のノードが隣接する第２のノー
ドを認識し、上記第１のノードと上記隣接する第２のノ
ードが情報を交換する隣接関係認識段階と、上記第１の
ノードと上記隣接する第２のノードがクラスタを形成す
るクラスタ形成段階とからなる、通信網の分割方法であ
って、上記隣接関係認識段階は、第１のクラスタの中の上記第
１のノードが上記第１のクラスタの隣接する第２のクラ
スタとの接続の度合いを表わす隣接情報を生成する隣接
情報生成段階と、上記生成された隣接情報に適用するクラスタ間の従属関
係設定規則を判定する従属関係判定段階とを更に有し、上記クラスタ形成段階は、上記適用された従属関係設定
規則に応じて、上記第１のクラスタと上記第２のクラス
タの中の一方を従属させるクラスタに割り当て、他方を
管理するクラスタに割り当てる段階と、上記従属させる
クラスタが上記管理するクラスタに従属する新しいクラ
スタを形成する段階とからなる、通信網の分割方法。
【請求項１４】隣接クラスタ間リンクを介して隣接ク
ラスタ群と隣接し、クラスタ内ノード群と、上記クラス
タ内ノード群から選択された代表ノードと、クラスタ内
リンク群とから構成されるクラスタを有する通信網の分
割システムであって、上記代表ノードは、上記クラスタ内リンク群及び上記隣接クラスタ間リンク
を介して上記隣接クラスタ群を認識し、上記隣接クラス
タ群との間で隣接情報、クラスタ情報を授受する情報送
受信部と、従属関係設定規則を管理し、現在のクラスタの状態に関
し適用可能な従属関係設定規則を判別する適用規則判断
部と、上記クラスタ自体の隣接情報を算出し、現在の隣接情報
及び適用規則、他のクラスタから得られた従属関係申請
の状況等の現在の処理状況を管理する状態保持部と、従属関係設定処理を行なう従属関係設定処理部と、上記状態保持部で管理された情報を参照し、規則の再適
用や現状態の更新、上記従属関係設定処理への移行を制
御する従属関係設定判断制御部とからなる、通信網の分
割システム。