(57)【特許請求の範囲】
【請求項１】
ノード間に通信リンクを有するノードの階層を備え、前記階層がルーツノードから複数のエンドノードに広がり、前記複数のエンドノードが分散データ構造を提供し、前記階層を通り前記エンドノードにおいて記憶されている特定のデータ要素へ至るルートが各ルートに沿ったノードに記憶されているポインタにより識別可能であり、特定のデータ要素にアクセスするための要求が、前記特定のデータ要素に関連するポインタを有するノードに到達するまで前記階層を通ってエンドノードから前記ルーツノードに向けて送られる検索メッセージをトリガし、その後に前記検索メッセージが前記関連ルートに沿って前記データ要素を含んでいる前記エンドノードに送られるデータアクセスシステムの手段により、分散データ構造中に記憶されているデータ要素にアクセスする方法において、
前記データ要素にアクセスする方法は回復方法を含み、
前記回復方法は、
（ａ）前記階層の少なくとも１つの各子ノードと各親ノードとの間の通信に影響を与える前記階層の故障部分を検出するステップと、
（ｂ）前記子ノードと別のノードとの間に第１の別の通信リンクを確立し、前記別のノードが前記各子ノードに対する第２の各親ノードとなるステップと、
（ｃ）前記第２の親ノードと前記第１の親ノードとの間に第２の別の通信リンクを確立するステップと、
（ｄ）前記第１の親ノードに対して、前記子ノードに対して向けられたメッセージを、前記子ノードに前記メッセージを送り出す前記第２の親ノードに送るように命令するステップと、
（ｅ）前記階層中の前記子ノードの新しい位置に関して、前記第２の親ノードが前記階層の他のノードを周期的に更新するステップとを含むデータ要素にアクセスする方法。
【請求項２】
前記データ要素がそれぞれ、データ構造中におけるデータ記憶位置を識別するアドレスを含む請求項１記載の方法。
【請求項３】
前記データ要素がそれぞれ、通信ネットワーク中の位置を識別するアドレスを含む請求項１記載の方法。
【請求項４】
前記通信ネットワーク中において前記識別された位置への接続を確立することができるように、前記データ要素を含んでいる前記エンドノードにおける前記検索メッセージの受信が、前記通信ネットワーク中の通話制御手段への前記データ要素の伝送をトリガする請求項３記載の方法。
【請求項５】
各ポインタが、前記エンドノードへのルート上の次の通信リンクを示しているリンク識別子とともに、前記関連する特定のエンドノードに記憶されているデータ要素に関連する識別子を含む請求項１ないし請求項４のいずれか１項記載の方法。
【請求項６】
前記データ要素を含んでいる前記エンドノードにおける前記検索メッセージの受信が、前記データ要素のダウンロードをトリガする請求項１記載の方法。
【請求項７】
任意のエンドノードにデータ要素をロードする手段が提供され、データ要素の前記ロードに応答して前記階層の前記ノード中に記憶されているポインタの結果的な更新をトリガするポインタ更新手段が提供される請求項１ないし請求項６のいずれか１項記載の方法。
【請求項８】
請求項１ないし請求項７のいずれか１項記載のデータ要素をアクセスする方法を含む通信ネットワークのための管理方法。
【請求項９】
通信ネットワーク中に個人ナンバリングサービスを提供する際に使用するための請求項８記載の方法。
【請求項１０】
ルートに沿った各ポインタが特定のネットワークユーザに対する個人番号を識別し、前記ルートに沿って送られた検索メッセージが到達した前記エンドノードに位置されている前記データ要素が、前記通信ネットワーク中の前記特定のネットワークユーザに対するハードウェアアドレスを含む請求項９記載の方法。
【発明の詳細な説明】
この発明は、分散データ構造中のデータにアクセスするためのデータ管理システムの構成方法に関する。
多くの異なる構成により、複雑な分散データ構造が提供される。例えば並列処理コンピュータ中の異なるノードにより、複雑な分散データ構造が提供される。一方通信ネットワークでは、ネットワーク中の異なるスイッチングポイントにおいて、例えば公衆ネットワークのローカル交換機において、複雑な分散データ構造が提供される。特定の実施例では、ネットワーク中の論理的または地理的位置に関して自分の位置を変更することができるユーザに対する通話をルーティングするためのルーティング情報を提供するために本発明を使用することができる。
通信ネットワークにより利用できるサービスは益々複雑になっている。顧客が選択的に利用できる一方、過度の計算または通信オーバヘッドをもたらさないような、関連するサービス機構のための管理システムを導入することが重要になっている。この例は、個人用電話ナンバリング方法として知られている。これらの方法では、ユーザがネットワーク中において自分の位置を変えても変更されない電話番号が、各ユーザまたはユーザのグループに割当てられる。
個人ナンバリングのようなサービスに対しては、位置データを容易に変更できることが重要であることは明らかである。ネットワークの観点からすると、位置データは揮発性であるが、その現在のバージョンで、常に迅速にアクセスするできることが必要である。
個人ナンバリングのようなネットワークサービスの別の観点は、スケーラブルであることが重要であることが多いことである。すなわち、より多くの数のユーザ、おそらく無限のユーザに拡張できることが必要である。例えば、約１００万人のユーザをサポートするためにネットワークを成長させることができることが重要であることが多い。またこれらのユーザは可変の負荷を発生させ易い。例えばオフィスに到着したユーザは、自分の個人番号を自宅の位置から自分のオフィスの位置に移したくなる。これは、数時間の間に数１００万のトランザクションを発生させる。固定ネットワークが、セルラ無線ネットワークのものと等価である完全な移動サービスをサポートすると仮定すると、位置情報を更新する際に固定ネットワークにより伝えられるオーバヘッドは、毎時数１００万のトランザクションをもたらす。
個人ナンバリングのようなサービスに関連するデータを保持する中央データベースを維持することが一つの選択である。ネットワーク中の目的地にルーティングされなければならないトラフィックは、このデータベースにアクセスして目的地に対する現在位置を得る。しかしながらこのタイプのシステムは、かなりのオーバヘッドを発生させ、ネットワークは、位置データを更新するかまたは現在のバージョンをダウンロードするために中央データベースに単にアクセスするトラフィックを伝えなければならない。中央制御に基づく構成がオーバヘッドに対して弱いことを明らかである。
セルラ（移動）電話ネットワークで使用される別の方法は、“ホームロケーションレジスタ”として知られているホームレジスタを各ユーザに提供することである。各ホームレジスタは、インテリジェントネットワーク技術においてユーザプロフィールとしてよく知られているタイプの、ユーザに関連するデータを保持する。すなわちホームレジスタは、例えばどのサービスにそのユーザが加入しているかを示し、また一日の異なる時間に異なって適用できる“通話迂回”タイプのサービスに関する一日の時間情報のような詳細情報を提供する。ホームレジスタは、ユーザに対する位置データも持っている。複数のホームレジスタは、一体になって分散データ構造を効果的に提供し、ユーザの通常の位置とネットワーク中におけるユーザのホームレジスタの位置との間にマッピングがあるように配置される。しかしながら、すべての通話が呼び出されたユーザのホームレジスタに自動的に行くので、通常の位置から離れているユーザを取扱う際にはかなりのオーバヘッドが存在したままである。さらにユーザ位置の変更は、ホームレジスタ中の位置データを更新しなければならないことを意味し、これは信号負荷を増加させる。さらに、顧客ベースのサイズが増加する時に問題がある。顧客ベースの増加に対する設計の対応は、ローカルセルサイズを減少させることがである。しかしながら、２乗法則にしたがって信号負荷が劇的に増加するだけでなく、管理手続きの複雑さも増加する。データの完全性および強さを提供することが重要な問題となっている。
“ホームロケーションレジスタ”（ＨＬＲ）構成をわずかだけさらに複雑化したものが提案されており、これには追加のレジスタが設けられ、“ビジットロケーションレジスタ”として知られている。これはＨＬＲの特徴を繰り返すが、呼ばれたユーザが自分の通常の位置から離れている時における通話要求を取り扱うために、ネットワーク中の他の場所に配置される。入通話が発生したネットワーク中の場所に応じて、入通話はこれらの環境におけるいずれかのレジスタに関係する。しかしながら、通話要求がＨＬＲにルーティングされる場合、通話要求は単にビジットロケーションレジスタに送られるだけである。
本発明にしたがうと、
ノード間に通信リンクを有するノードの階層を備え、前記階層がルーツノードから複数のエンドノードに広がり、前記複数のエンドノードが分散データ構造を提供し、前記階層を通り前記エンドノードにおいて記憶されている特定のデータ要素へ至るルートが各ルートに沿ったノードに記憶されているポインタにより識別可能であり、特定のデータ要素にアクセスするための要求が、前記特定のデータ要素に関連するポインタを有するノードに到達するまで前記階層を通ってエンドノードから前記ルーツノードに向けて送られる検索メッセージをトリガし、その後に前記検索メッセージが前記関連ルートに沿って前記データ要素を含んでいる前記エンドノードに送られる、分散データ構造中に記憶されているデータ要素にアクセスするデータアクセスシステムを構成する方法におけるデータアクセスシステムを回復させる方法において、
（ａ）前記階層の少なくとも１つの各子ノードと各親ノードとの間の通信に影響を与える前記階層の故障部分を検出し、
（ｂ）前記子ノードと別のノードとの間に第１の別の通信リンクを確立し、前記別のノードが前記各子ノードに対する第２の各親ノードとなり、
（ｃ）前記第２の親ノードと前記第１の親ノードとの間に第２の別の通信リンクを確立し、
（ｄ）前記第１の親ノードに対して、前記子ノードに対して向けられたメッセージを、前記子ノードに前記メッセージを送り出す前記第２の親ノードに送るように命令し、
（ｅ）前記子ノードが前記階層である場合に新しい位置に関して、前記第２の親ノードが前記階層の他のノードを周期的に更新するステップを具備することを特徴とするデータアクセスシステムを回復させる方法が提供される。
第２の別の通信リンクを確立し、その後、階層における子ノードの新しい位置について階層を周期的に更新することにより、階層を更新するために必要な信号を時間的に分散し、また階層上の“負荷”が軽い期間に制限することができる。別の通信リンクは、子の新しい位置について更新されていないノードから子ノードに対する要求を満たす。
個人ナンバリングは既に上で言及した。これは、将来の通信サービスにおける重要な構成要素であることが期待されている。このようなシステムは、数字またはアドレスを個々のユーザに対して（あるいは可能性としてはユーザのグループに対して）割当てる。そして、そのユーザに対して向けられたトラフィックは、その人がネットワーク中のどこに位置していてもその人に対してルーティングされる。通話が目的地にルーティングされるように、ユーザに関係する現ハードウェアアドレスが必ず存在するが、ハードウェアアドレスは割当てられた個人番号の単なる変換であり、関連ユーザがネットワーク中の位置を移動すると変更される。
本発明の実施例では、ハードウェアアドレスはエンドノードが含んでいるデータ要素より表される。個人ナンバリングシステムでは、入って来る自分への入通話を、異なるローカル交換機に取扱われるネットワーク中のハードウェアアドレスにリダイレクトしてもらうことを望む。ユーザは、関連ハードウェアアドレスがユーザの個人番号と関連するように、新しいローカル交換機におけるエンドノードを更新する。そのエンドノードは、その後、そのユーザの個人番号に対する通話の新しいローカル交換機へのルートを知らせるために、階層のノードにおける関連ポインタを更新し、ユーザが位置していた前のエンドノードにそのユーザの個人番号に対するハードウェアアドレスを取り消すように命令することが好ましい。これは、ユーザに対する位置データが移動し、そして変更されることを意味する。しかしながら、本発明の実施例にしたがったデータアクセスシステムはユーザの動きを追跡し、ハードウェアアドレスの更新バージョンを提供する。この追跡はローカル交換機においてトリガされる。
本発明の実施例にしたがってデータアクセスシステムは、要求に応じて、または故障に応じて、自分自身を自動的に再形成することができ、および／または、その情報“空間”を再構成することができる。例えば、本発明の実施例が階層的な性質を持っている場合、再構成されたシステム中において必要があれば、データの喪失を潜在的に見付け出し、再構成することができるように、“フラッドフィル”検索手続きを全データアクセスシステムにわたって急速に広げることができる。
本発明の実施例は、固定された公衆電話交換ネットワーク（ＰＳＴＮ）中でさえも実時間でネットワーク中の細部レベルにおいてルーティングを変更しなければならない個人ナンバリングのようなサービスのルーティング問題に対して比較的簡単な解法を提供する。さもなければＰＳＴＮでは、開発と変更は、個人ナンバリングのルーティングに対して甚だしい困難性を提起する。
添付図面を参照して、例としてのみ、本発明の実施例として個人ナンバリング用のネットワーク管理システムをこれから説明する。
図１は、ネットワーク管理システムの簡単な４レベルバイナリツリー構成を示したものである。
図２は、図１の構成におけるノードにより実行される簡単な情報検索手続きをフローチャート形式で示したものである。
図３は、図１の構成にしたがった２つのネットワーク管理システムのブリッジングを示している。
図４は、本発明の実施例にしたがった拡張されたネットワーク管理システムを示している。
図５は、図１に示されているような構成にしたがったネットワーク管理システム中の故障に対する対応の例である。
図６は、図１に示されている構成にしたがった複数のネットワーク管理システムを含んでいる情報層を示している。
図７は、本発明にしたがった回復メカニズムの説明において使用される図である。
図８は、データフロー図である。
図９は、図１のネットワーク管理システムを実行することができるインテリジェントネットワークアーキテクチャーのブロック図である。
通信ネットワーク中の個人ナンバリングシステムにおいて、ユーザにより要求されるサービスの特徴は、
１．電話機のようなローカル端末装置が個人向け電話番号用の目的地装置であるようにプログラムする能力、
２．目的地装置として、ホーム電話機のようなネットワーク中の予め定められた位置に戻す能力、
３．個人向け電話番号用の目的地装置をネットワークにおいて意のままに選択する能力である。
これは、ネットワークと関連管理システムとが、入通話を“移動している目標”にルーティングするように協同できなければならないことを意味する。本発明の実施例にしたがったネットワーク管理システムの設計の基本は、ネットワーク基盤のものから情報管理タスクを論理的に分離することであり、簡単に拡張できる一方で分散データベースの制御を取扱うことができる信号ネットワークで実現される。通常、個人ナンバリングにおいて、分析データベースを有する信号ネットワークを含んでいるシステムが、位置付け情報を、個人ナンバリングでは通常これはハードウェア目的地アドレスであるが、一旦持つと、システムはネットワーク基盤またはベアラーネットワークに制御を事実上に戻す。
ベアラーネットワークと管理ネットワークとの間のこの分離の利点は、エンドユーザ制御システムと、移動通信、内部ビジネス、コンピュータネットワークなどのようなネットワークとの結合を促進することである。一般的に管理ネットワークは独立した概念の構造であるので、独立した構造として物理的に取扱うことができ、現在のシステム上に直接設けることができる。したがって、管理ネットワークは、現在のシステムを置換するのではなく、むしろこれを機能的に増強することができる。さらに管理ネットワークは、幾つかの異種ネットワークをまたぐことができ、これらを単一化することができる。
図１を参照すると、ネットワーク管理システムが動作する簡単な基礎はノード１，２，３である。ノード１，２，３は階層的に接続されており、ツリー状信号ネットワークを形成している（ツリー状ネットワークは実際の物理的なネットワーク内で実現することができる論理構造であるが、物理的なネットワークは必ずしもツリー状である必要がないことを心に留めておかなければならない）。すべてのノード１，２，３は、ツリーの“ルーツ”を形成する１つのノード２を除いて、少なくとも１つの親を持っている。ルーツノード２は、親を持っていないという意味のみで特別である。１つの親だけを持っているノードから構成されているこの構造は単純である利点を持っており、複数の親の場合には、なされるべき余分の決定を取扱うためにさらに複雑な制御論理を必要とする。しかしながら、複数の親がある構造は、物理的および論理的故障においてさらに強くなる。本発明の実施例は、単一の親構造と使用する場合に限定されるものではない。
一般的にノード１，２，３は、ベアラーネットワークを直接取扱うエンドノード３を除いて１つ以上の子を持っており、これらは通常、ローカル交換機に配置されている。以下の説明を簡単化するために、これらのエンドノード３は何ら子を持つ必要がなく、子がないとして仮定する。
図１を参照すると、ノード１，２，３とリンクを備えているルーティングネットワークの一般的な原理は、各エンドノード３が潜在的に１人以上のユーザに対する現ハードウェアアドレスを含むことができること（または提供することができること）である。宛先ユーザに対する通話を設定するためにネットワークによって入通話要求が受信された時、ルーティングネットワークは、その宛先ユーザに関連する現ハードウェアアドレスを見つけるために使用される。ルーティングネットワークがこれを行うことができるのは、エンドノード３のいずれか１つを介して宛先ユーザの現ハードウェアアドレスの位置を見つけることができるが、階層中の正しいエンドノード３より上のノード１，２における、正しいエンドノード３に対するポインタの手掛かりにより、正しいエンドノード３がルーティングネットワーク中に知らされるからである。どのエンドノード３において通話要求がネットワークに入ったかには関係なく、通話要求が正しいエンドノード３に向けてたどるポインタの手掛かりに出会うまで、通話要求が単に階層を介して送られるだけである。すなわち、正しいエンドノード３の方へ向かうポインタを含んでいるノード１，２と通話要求が出会うまで、ネットワークを介して通話要求が送られる。そのポインタは通話要求を手掛かりの中の次のノードに向け、同様にして、宛先ユーザの現ハードウェアアドレスを提供することができるエンドノード３に向けて下向きに階層を通って戻るようにする。
すべてのノード１，２，３は同じデータ構造と処理装置を持つことができる。その特定のノードが通話要求を宛先ユーザに向ける役割を担っている場合のみ、データがデータ構造中に存在する。その役割は、
ｉ）通話要求を単にその親ノードに送ること、
ｉｉ）そのノードが目的地にあるものではないが、目的地へのパスの途中にある場合に、目的地へのポインタを提供し、そのポインタにより示されたノードに通話要求を送ること、
または、
ｉｉｉ）対象とされているノードが宛先ユーザのためのエンドノード３である場合には、宛先ユーザの現ハードウェアアドレスを提供することである。
ノードのデータ構造に存在する情報はポインタであり、このポインタは“キー”およびリンク識別子を含んでおり、エンドノード３の場合には、現ハードウェアアドレスを含んでいる（存在する別の情報は、ルーツノードを除き、故障時に使用するための親ノードのリストである。これは以下にさらに論じる。リストの代わりに、ノードは新しい親を探すこともできる）。これまでエンドノード３のみが現ハードウェアアドレスを含んでいたが、一般的にすべてのノードがこれを含むことができるようになる。この説明の後で理解されるように、これは、ルーティングノードが拡張または縮小される場合に、エンドノード３が中間ノード２になり、またこの逆となるからである。“キー”は一般的に、ポインタに関連するユーザを識別する。例えば、キーはそのユーザの個人番号である。リンク識別子は、通話要求が、ルーティングネットワークの次の層に向かうどの下方リンクに送られるべきであるかを識別する。
前に説明したようなルーティングネットワークは明らかに、任意のユーザ向けの“ホームロケーションレジスタ”を提供するものではなく、したがって、ホームレジスタに向かうまたはこれを介する通話要求に伴う付加的な信号負荷を避けるものであることが着目される。
図１に示されている信号ネットワークを使用すると、最も近いローカル交換機のようなエンドノード３により、“Ｐ”のようなユーザが一般的に取扱われる。これは、そのローカル交換機に、ユーザＰの現ネットワークハードウェアアドレスが記憶されることを意味する。ユーザＰは、１つのノードＡにより取扱われるものから、異なるノードＢにより取扱われるものへ移ることを決定する際に、変更を起こさせる。ユーザＰは、ノードＢにアクセスすることにより変化を起こさせ、追加のルーティングをすることなくユーザＰがノードＢから直接得られることを示すように、ノードＢは自己のデータを修正する。そしてノードＢは変更コマンドをその親ノードＤに送り、その結果親ノードＤは、ユーザＰに向けられた通話をノードＡにルーティングする代わりに、ノードＢにルーティングするように自己のデータを変更する。ノードＡに対する親として機能するノードＤは、ノードＤがもはやユーザＰに向けてルーティングせず、したがって、ユーザＰに対するいずれの通話も親ノードＤに送るべきであることを、ノードＡに対して知らせる。
この段階で、ユーザＰは実質的にユーザＰ'になったと考えることができる。ネットワーク上のデータ構造は実質的に変更されず、親ノードＤとともにノードＡとＢのみが影響を受ける。
ノードＢのみがユーザＰを見つけることができる場合がある。これは、ノードＢがユーザＰに合わせるために自己のデータを修正するが、親ノードＤが結果として起こる変化をしていない段階においてである。しかしながら、この場合は非常に短い時間である。
ユーザＰがさらに遠いノードに例えば図１のノードＣに移動した場合、変化は必然的にさらに遠くまで及ぶ。最初にノードＣは、ユーザＰに合わせるために自己のデータベースを変更し、自分の親である図１のノードＨに変更が生じたことを教える。変更は、ノードＨに教えるノードＣ、ノードＧに教えるノードＨ、ノードＦに教えるノードＧ、ツリーのルーツというように、ツリーを伝搬する。そしてノードＦは、ユーザＰ向けの通話を自分の子に１つにもはやルーティングしないことを自分の子ノードＥに知らせることにより、前に存在していたユーザＰへのルートを“破壊”する。順番に、ノードＥは自分の子ノードＤに伝え、ノードＤは自分の子ノードＡに伝える。
起こり得るさらに悪い場合では、これらの変更はさらに多いが、Ｎをツリー中のノードの総数として、関係する変更の数は、２ｌｏｇ2（Ｎ）だけである。重要なことは、変更はローカル的であり、隣接ノード間の通信によりトリガされることである。これは、分散されたルーティングテーブルの更新を非常に効率的にするとともに、現在の技術で行うことができる。
図２を参照すると、ベアラーネットワーク中の宛先ユーザに対する接続を確立するために通話要求がなされたとすると、宛先ユーザの位置を探し当てるためにルーティングネットワークがトリガされる。ルーティングプロセスは通話要求を受信するノードごとに同じであり、ノードは１以上の一連の決定を行い、これらの決定の結果に基づいて機能する。
通話要求を受信する任意の１つのノードにおけるルーティングプロセスは、図２のフローチャート２０に見られる。ノードの最初の応答であるステップ２２は、宛先ユーザに関する情報に対して自分のデータ構造を調べることである。そして起こり得る３つのシナリオは以下に示す通りである。
１．対象とされているノードが、宛先ユーザにあるものでなく、またそれへのパスの途中に位置しているものでもない。
この場合ステップ２２において、情報が存在していないことをノードが知る。通話要求ネットワークのルーツに向けて送られるので、ステップ２３において、その後ノードは自分自身がルーツノードであるかどうかをチェックする。通常の状況は、ステップ２４のようにそのノードがルーツノードではなく、通話要求が単に親ノードに送られるだけである。結果的に通信要求は、ノードのネットワークを介してルーツノード２に向かう上向きの道を作る。
２．対象とされているノードは、宛先ユーザがいるノードへのパスの途中にあるが、自分自身は宛先ユーザのローカル交換機ではない。
この場合では、ノードはステップ２２において、自分が宛先ユーザについての情報を保持していることを知る。したがってノードは、自分自身が宛先ユーザがいるノードであるかどうかのチェックを始める。すなわちステップ２６のように、ノードは自分がローカル交換機であるかどうかをチェックする。このシナリオではステップ２６のように答えは否定であり、ノードは通信要求を存在する情報により示されている子ノードに送る。したがって、この段階における通信要求は、ネットワークルーツノードに送られ、再度、宛先ユーザに向けて下方に送られる（しかしながら、常にルーツノードを介して通信要求をルーティングする必要がないことに留意すべきである）。
３．ノードが宛先ユーザに隣接するノードである。
この場合では、ステップ２２と２５により、ノードは宛先ユーザについての情報を持っており、ローカル交換機でもあることを知る。したがってこのノードは、接続を設定することができるベアラーネットワークに情報をダウンロードする。すなわちこのノードは、通信要求を発生させた呼出し人の位置とその自己の位置情報とをダウンロードする。ステップ２７、２８のように、ルーティングネットワークは動作から離れることができ、そしてベアラーネットワークは通話を自分自身で適切にルーティングする。
前に論じられていない１つの別の結果がある。それは、宛先ユーザについての情報をもっていないが、ルーツノード２であり、それゆえ通信要求を向けるところがないことをノードが確立する場合である。この結果、情報が失われており、通信要求を送る代わりに、ステップ２９のようにノード２がデータ検索を引き起こすことを示している。
前に説明したようなツリーネットワークに基づいたシステムは、並列の概念を使用する。各ノード１，２，３は、それに隣接するものにより起される変更に応答して更新されるデータベースを管理する。階層的構成は、情報を変更させる必要性に制限を強いる。要求されたデータ変更をシステム全体にわたって伝搬させることも可能であるが、変更が制限された結果を持つように構造が設計される。このレベルの並列概念は地理的分解から明らかであるが、正確には、同じ分解をノード１，２，３内に適用することができる。
重要な特徴は、分散データ構造内の変更ができる限りローカル的に取扱われることである。情報の断片が更新される時に、ノード１，２，３の大部分は巻き込まれない。これは、ネットワーク全体にわたる更新に関する負荷を分散させる効果を有する。この結果は、システムがより大きくなる時でさえ、ネットワークへ情報の信号送信が分散されつづけることである。バイナリネットワークの場合では、図１を参照して説明したように、ノード１，２，３当りの信号負荷は、ネットワーク中のノード１，２，３の数と無関係である。
分散メモリ並列コンピュータにより、各の１，２，３を提供してもよい。コンピュータ中の各プロセッサを上記の例で説明した通信ノード１，２，３の１つに直接的に割り振ることができる。コンピュータの制御システムは、ノード１，２，３を動作させるのと同じ方法で、データベースを管理することができる。これは、ローカル交換機レベルを表しているノードであり、より低く一番多いノード３であるツリーの各“リーフ”が、ネットワーク中のより高いノードと同じような方法で問題を解決し、したがって同じ制御プロセッサを使用することを意味する。
これは、常に同じ制御プロセスを使用して、ネットワークの下位のノードを制御するために、各ノードを潜在的に使用することができる点で特に効果がある。したがって、前に説明したように、ルーティングネットワークの範囲を拡張するために、同じアーキテクチャー原理に基づいて新しいネットワークを生成し、新しいルーツノードを生成し、元のネットワークのルーツノードとネットワークとを“降格”して新しいルーツノードより下にすることができる。
図３を参照すると、元のネットワークはルーツノード“Ｒ'”を持っており、新しいネットワークはルーツノード“Ｒ''”を持っている。その後、新しいルーツノード“Ｒ”が新しい層として入れられ、前にルーツノードＲ'およびＲ''であったノードに取って代わり、新しいルーツＲが２つのネットワークに対応するルーツとして機能する。古いルーツノードＲ'およびＲ''はそれぞれ、もはやルーツノードでない事実を記録するために更新されなければならない。その後、システムは適切に機能する。成長および需要を満たすように、地理的に不均一に分散されている現在のルーティングネットワークを拡張するために、同じ原理を使用することができる。したがって、前にローカル交換機を表していたノード３は、その下に別のネットワークを単に加えることにより、ルーティングネットワーク中でより高いノード２に変換される。これは図４に示されており、前はルーティングネットワークのより低い最も多いレベルにあったノード４０が、６つの追加ノード４１，４２より上の中間ノードの役割に変換され、ローカル交換機を表しているより低い最も多いノードは、今度は下の２つの層である。
それぞれの場合において、そのステータスが変更されたそれぞれのノードが知らされさえすれば、構成の変更後に、ルーティングネットワークは落ち着いた状態に実質上なる。
図５を参照すると、ルーティングネットワークは、信号リンクもしくはノード１，２，３の故障、またはネットワークの大部分の故障に強いように設計することができる。
リンク故障を検出する方法は、接続ノードがリンクを使用しようとして失敗したからか、または、ネットワーク管理メカニズムが故障を見つけたからかのいずれかである。後者の例は、従来のＣ７信号システムにおいて供給される“ハートビート”信号である。
例えばエンドノード３'と中間ノード２''との間の１つのリンクに故障がある最も簡単の状況では、エンドノード３'は、故障リンクの反対側にあるその親ノード２''に通常送られる通信要求にもはや応答することができない。通常のルーティングネットワーク構造では、そのエンドノード３'から元の親ノード２''または他の何らかの親ノードへの代わりのリンクは存在しない。
リンク故障の下、ルーティングネットワークを再構成するために、各子ノード２，３が親ノードのリストを持っており、これにより各子ノード２，３はルーティングネットワーク中に再接続を確立しようとすることができる。したがって故障リンクにより影響を受ける子ノード３'は、予備容量を持って機能している親ノードの位置を探し当てられるまで、再接続要求をそのリスト上の各潜在的親ノードに対して順番に発行する。その後、ネットワークを介する子ノード３'へのルートの再接続は、ユーザが１つのエンドノード３から別のエンドノードに移動する時に再接続が確立されるのと同じ方法で設定される。
関連子ノードが含んでいるすべてのポインタに対して再接続要求を発行しなければならないので、実際には、階層中において関連子ノードがどれ位高いところにあるかによって、この再接続の実行は複雑となる。
図５では、新しいリンク５０が確立されている。しかしながら、ルーティングネットワークは、例えば各ノードにおけるアドレスによりリンクが識別される論理的に規定された構造を持っているので、新しいリンク５０が階層の２つの層をまたいでも、新しいリンク５０を生成することに困難性はない。
一方、これは、エンドノード３'に向かう通信要求がルーティングネットワークのどこか他の場所に入り、したがって、故障リンクより下の子ノード３'へまたはこれを介してルーティングする必要がある場合であるかもしれない。新しい親を使用して子ノード３'がすでに再接続の実行をトリガしている場合、その後ネットワークは通常の方法で機能する。しかしながら再接続の実行は、再確立させる必要があるルート数に応じて遅延を発生させる。この実行が完全でなければ、入通話要求は、エンドノード３'に対する親である中間ノード２''に達するが、エンドノード３'には達することができないかもしれない。新しい親に達するために子ノードが新しいリンク５０を起こすことができるのと同じくらい効率的に、中間ノード２''は、子ノードに達するために新しいリンク５１を起こすことができない。これは、新しい子ノードが中間ノード２''中に伝えられるポインタの選択のみに関連しているからである。この場合、子ノードの新しい親２'の位置を探し当てるために、中間ノード２''が“フラッドフィル”検索要求を発行することがより効率的である。
フラッドフィル検索要求は、単にあるノードからこれが接続されている他のすべてのノードに対して発行されるだけである。フラッドフィル検索要求を受信した時、各ノードは関連データまたは関連ポインタを含んでいるかを見るためにチェックを行う。含んでいると、そのノードはその要求に応答する。含んでいないと、そのノードは、自分がこの要求を受けたノードを除く、接続されているすべてのノードに対してフラッドフィル検索要求を送る（フラッドフィル検索要求は実際には、例えば要求を送ることができる回数を制限することにより制限することができる）。
したがって中間ノード２''は、エンドノード３'のための新しい親ノード２'の位置を探し当て、すべての関連ルートを再確立させることができる。
したがって上で説明したメカニズムは、故障を効率よく“バイパス”する新しいリンク５０をネットワーク中に発生させる。
故障したのがリンクであろうとノードであろうと、もちろん同じメカニズムを使用することができる。
故障後にネットワークを再確立するための第２のメカニズムがある。単にネットワーク全体に対して、特定の情報に対するフラッドフィル検索要求を発行することができる。この方法を適用することにより、ネットワークの大規模な再構成を達成することができる。
フラッドフィル検索要求技術を使用すると大きな信号オーバヘッドを発生させるので、あまり強くないネットワーク、すなわち故障し易いものには望ましくない。
ノードが新しい親に対するリンクを確立した時、ノードが“新しい”位置を新しい親ノードに送る必要がある。遅延なく要求がノードに送られる場合、これはできるだけ早く行わなければならない。ノードと新しい親との間の新しい接続の確立がその後に引き続くアドレス変更の後に、ネットワークを更新する必要性が、非常に多くの信号の動きを生じさせる。これは、ノード間の要求をルーティングするネットワークの能力、特に、何らかの現実的なネットワークの場合のように、所定の時間間隔の間に多数の再接続がある場合のネットワークの能力に問題を生じさせる。
本発明は、この問題を解消しようとしてなされたものである。
図７は回復方法を図示している。ルーティングネットワーク７０では、ノード７２と７３との間のリンク７１にリンク故障がある。
回復メカニズムにおける第１のステップは、図８に示されているように、検出ステップ８０である。このステップはノード７３により実行され、ノード７３とその親ノード７２との間のリンク７１が故障していることを検出する。ノード７２は同様にこのステップを実行する。
第２のステップ８１はノード７３により実行され、これは新しい親７５への新しい接続７４の確立である。新しい親は、ノード７３により保持されている潜在的な親のリストから選択される。
そして新しい親ノード７５は、ボックス８２により表されるステップにおいて、古い親７２に対するダイレクトリンク７６を確立する。
そして古い親７２は、ノード７３に対するそのアドレスを更新するように新しい親７５により要求され、古い親７２が受信するすべての要求が、ダイレクトリンク７６を介して新しい親７５に、そして新しい接続７４を介してノード７３に送られる。
したがって、この段階でリンク故障が解消され、ノード７３は再度ネットワーク７０の一部となる。
ボックス８４により表されているような次の段階は、新しい親ノード７５に対するものであり、ノード７３の新しい位置についてネットワーク中の他のノードを周期的に更新することである。代わりに、このプロセスは“要求に応じて”実行される。すなわち、あるノードからノード７３に対する要求が受信された時に、新しい親７５は更新位置メッセージを送信ノードに送る。これは、要求が通話接続要求に対する再位置付けであるか否かに依存させることができる。代わりに、これは予め定められたパターンにしたがって、またはネットワークの活動にしたがって実行することができる。すなわち、ネットワークに多くの信号の動きがない期間に、更新プロセスを実行することができる。
前に説明したネットワーク管理システムすなわちデータアクセスシステムは、データ構造が分散されていることから、比較的信頼性のあるデータ構造を提供する。アクセスされる情報、この場合ネットワークユーザに対するハードウェアアドレスは、１つの特定の位置に保持されない。第１の例では、システムを通ってその情報のデータ要素へ至るルートはただ１つであるが、ルート中の故障は前に説明したように容易に取扱うことができる。提供される付加的な特徴は、ユーザに対する接続の安全性を高めるものであり、バックアップデータ記憶ポイント、すなわちユーザに対する現ハードウェアアドレスを保持する“ゴースト”エンドノードである。これはフラッドフィル検索要求により位置を探し当てることができるので、そのユーザに対する再接続はこれでも確立させることができる。
フラッドフィル検索要求が発行されると、比較的高いレベルの信号トラフィックが発生する。使用を最小にするように、フラッドフィル検索要求は、データ改ざんまたは要求時の場合のみに使用されるかもしれない。前に説明したようなツリー状階層においては、ルーティングネットワークを介してローカル交換機への、すなわち目標ユーザと直接接触するエンドノード３へのパスは、常に２ｌｏｇ2（Ｎ）-1より少なく、この検索手続きでさえ比較的効率的なものにする。
検索に加えて、フラッドフィル検索要求はそれらが通るノード上の特定データに対する何らかのリファレンスを取り除き、これにより、ネットワークのにせルートまたはデータパスを排除する。これに対する唯一の例外は、情報が見つかるローカル交換機すなわちエンドノード３における場合である。この場合、データ（またはデータへのルート）を再構成できるように、位置記録プロセスを起動することができる。さらに、通話構成要求をベアラーネットワークに送り、最初の要求が確実に取扱われるようにすることができる。最悪の場合、通話を接続するためのこの全プロセスは４ｌｏｇ2（Ｎ）-1ステップかかり、完全なネットワークの場合のちょうど２倍である。
大規模の損害はこの方法で再構成することができるが、直接的に再構成するためにルーティング開始要求を使用するとさらに効率的である。両方のプロセスの組合わせは早い回復プロセスを導き、必要なデータはただちに作られ、ネットワーク容量が許容する時に、要求されていないデータをゆっくりと回復させることができる。
説明したタイプの管理システムは容易に拡張することができる。表されている簡単化された場合でさえ、すなわちツリー構造においてさえ、分散情報を検索するメカニズムに対する一般化は、明らかに次のステップである。ダイナミックに情報を再位置付けし、複数のコピーを導入する環境においてさえ、階層制御システムは、要求される情報の最も近い情報源への最も早いアクセスをもたらす。データベースキーまたは位置アドレスを認識しないポイントに対するデータを最初のノードが知らない場合でさえ、このことは真実である。
これは、分散データベースの観点から、前に説明した個人用電話ナンバリングシステムの動作によって最もよく理解できるであろう。ユーザの位置が継続的に監視され更新されているという事実は、管理ネットワーク情報の内部構造を自動化されたデータベースの内部構造にする。データを物理的に分散する、データ源の物理的な分散、すなわちユーザの動きがあるという事実を加えると、これは、各ノードが取扱わなければならないトランザクションの数を最小にする。最終的な結果は、まるで密着したデータベースであるかのように、その遠隔端末のいずれからでもアクセスすることができる分散データ構造となる一方、データトランザクションは並列的に更新される。
直接的な類推をすると、ライブラリに記憶されているような情報も多くの地理的位置に配置されることが多い。このような情報にアクセスするために、情報が記憶されている位置が知られていなければならない。静的な環境ではこれはささいな問題である。しかしながら問題が生じる場合がある。情報の各断片のコピーが１つしかない場合、所定のデータの断片に対する多重同時アクセスがこの問題となる。これに対する明らかな解法は、データを移動させ、このデータの複数のコピーを作ることである。すなわち、人気のあるデータを地理的に離れたいくつかの位置に配置する。これは、アクセス競合とネットワーク負荷を減少させる。再度説明すると、一度だけこれが実行されると、データ源は常に同じ位置にあるので、データ源の位置を所定の位置から見つけることについて心配する必要はない。しかしながら、現実の世界では継続的に変更が必要とされ易い。
情報の断片の人気は一過性のものであることがよく知られている。これは、情報が揮発性であるという事実に直接関係している。情報の断片は新しい場合のみに価値があることが多く、時間が経過し始めると価値がないことが多い。この相対的価値の変化のために、何らかの所定の端末の観点から見たデータの位置は時間的に変化する。位置におけるこれらの変化についてシステムのすべてのユーザに知らせることは、ネットワーク負荷に重いコストを負わせる。したがって、ユーザに知らせることなく情報の位置を変え、同時にユーザが情報へのアクセスを維持することができるシステムが必要とされる。これは正に本発明の実施例の階層的な制御構造がなし得ることであり、結果的にかなり汎用性がある。
データベースに対する“キー”は、文字通りキーとして考えることができる。これは単に、これにより情報が参照される構造となっている。同様に、論文の終りにおける参考文献はキーとして見ることができる。これらは必ずしも理解される必要がないが、判読されるべきまたは少なくとも部分的に判読されるべきどこか他の箇所において取り入れることができる。参照文献を有する論文の例では、司書に対して相談がなされ、司書はライブラリの論文の位置への道を人に教えるか、または正しいタイプのライブラリへの道を人に教える。
このレベルのキータイプにおいてさえ固有の階層がある。異なる制御階層を共通の分散データ源に重ねることが可能である。
図６を参照すると、３つの異なる制御階層のエンドノードレベル６０には、共通の分散データ源がある。３つの制御階層６１，６２，６３は構造的に類似し、それぞれ“トップ”にルーツノードを持ち、共通の分散データ源６０におけるノードのアレイにアクセスする。異なる制御階層は、比較をし、管理情報を共有できる程度まで容易に接続することができる。図６では、子ノード、この場合ではエンドノードの中には、１つのタイプのデータ記憶装置のみを含むものもあり、他のものは３つのタイプのデータ記憶装置を含むが、このことは、これらの“単一の子”が３つのすべてのタイプからのデータにアクセスできないことを意味するものではない。
このシナリオを一般的なデータベース構造のものに発展させることができない理由はない。例えば、異なるデータベースを統合するためにこのようなシステムを使用することはまったく可能なことである。物理的な分散は、アルゴリズム的な分散のものと、すなわちデータのアルゴリズム的な制御が異なる構造に分離される場合のものと、同じデータ管理の困難性を示す。これは通常、サイベースおよびオラクルのような２つの異なるデータベースプログラムに対するリファレンスである。このようなプログラムはすでに共通のインターフェイス言語を共有しており、遠隔端末からの同じ形態のデータ要求に応答する。データ要求は、最初にアプリケーションプログラムによりこの共通言語に構成され、受信データは関連するフォーマットに変換される。各データベースプログラムは、物理的に別個の、すなわち物理的に分離したデータ記憶装置としてして見ることができる。図６に示されているように、２つのシステムを階層的な制御構造に統一するために必要とされるすべてのものは、階層的な制御構造からの要求を関連するデータベース要求に変換する簡単なインターフェイスプログラムである。これにより、非常に簡単な方法で、階層的な制御構造を現在のデータベースシステムに適用することができるようになる。
本発明の実施例にしたがった階層的なルーティング構造は、データ源の位置を必ずしも知ることなく、階層的なルーティングネットワークの何らかの部分からのデータ検索を可能にする、一般的なサービスを提供することができる。この機能性は、ユーザの観点から見ると、例えば、任意のポイントにおいてアクセスできるサービス構造として単に見ることができる。これは、ユーザが任意の物理的なポイントから要求を発行する対象とすることができるシステムとして取扱うことができ、システムはユーザに対して要求を解決する。
ユーザ端末には、階層的な制御ネットワークに対して直接的な接続がある。ユーザ端末はシステムに要求を発行することができ、これらの要求は、ルーティングネットワークのデータ空間に含まれているデータについての問合わせの形式をとる。個人ナンバリングの特定の実施例では、この情報は、ダイヤルされた電話番号により識別されるユーザの現ハードウェアアドレスである。実際には、ルーティングネットワークは通常、現ハードウェアアドレスを返さないが、代わりに、見つけられた現ハードウェアアドレスの位置からの通話の自動的な接続をトリガするように処理を進める。これは他の状況においても適用できる。すなわち、ルーティングネットワークの任意のアプリケーションは、情報の断片が尾一旦見つけられた場合における予め定められた応答をいくつか持っている。応答は情報を問合わせた者に返すことであるが、この情報の返還を別個のタスクとして考えることにより簡単にすることができ、２つの関連アドレス間の情報の現実の転送は、ベアラーネットワークのような、従来の転送プロセスにより取扱われるようにすればよい。ルーティングネットワークのタスクは、単に情報の位置を見つけることである。一旦発見された情報を取扱うためには、異なるメカニズムを使用することができる。
明らかなように、この動きはユーザ端末の位置に無関係である。したがって、ルーティングネットワークは、非ローカル情報のデータベースであるとして見ることができる。さらに重要なことは、このデータベースは特定の位置にデータを保持する必要がないことである。別の位置がさらに最適な記憶位置であることが分かった場合、ユーザ端末のいずれにも、また情報を検索するためにユーザが使用するデータアクセスキーにも影響を与えることなく情報を動かすことができる。
図９を参照して、前に説明した本発明の実施例にしたがったルーティングネットワークの個人ナンバリングへの適用を考えると、ルーティングネットワークは一般的に、インテリジェントネットワークアーキテクチャーのサービス制御ポイント９０に設けることができる。インテリジェントネットワークアーキテクチャー中では、接続は通常、関連サービス制御ポイント９０から得られるルーティング情報を使用したサービススイッチポイント９１により確立される。代わりに、インテリジェントネットワークアーキテクチャーにかなり柔軟性がある場合に、ルーティングネットワークがサービス制御ポイント９０の機能に取って代わり、インテリジェントネットワークアーキテクチャーのどこか他の場所に配置される。ルーティングネットワークの機能を提供するハードウェアは知られており、インテリジェントネットワークアーキテクチャーにおいて既に使用されている。例えば、関連ハードウェアは、ギガバイト容量のハードディスクを備えているＳｕｎ  Ｓｐａｒｃ５のようなＵＮＩＸワークステーションにより提供される。
本発明の実施例により利用可能な重要な特徴は、以下のように列挙することができる。
１．例えば個人ナンバリングサービスネットワーク中の密集した領域に深さを与えるために層を追加することによる、地理的需要に対する最適化。
２．ライブラリの問題において、例えば、文字通りライブラリであるサービスにおいて、または明らかにライブラリタイプのものであるビデオオンデマンドのようなサービスにおいて、需要の効率的な配置を提供することができる。
３．信号負荷が低く保持され、実際、全体としてのネットワークが拡張されても、任意のポイントにおける信号負荷が一定であるように信号負荷を維持することができる。この観点は、需要が増加するにしたがって、ネットワークがローカル的な追加層を発生させることができるからである。
４．本発明の実施例は、従来の技術と既に使用中のソフトウェアをあてにすることができ、したがって、別のプラットフォームの開発を必要としない。
５．強さ。前には説明しなかったが、１つの子ノードに対する親ノードの数を増加させることにより、強さを改善することができる。すなわち、１つの子ノードに関連する２つ以上の親ノードがあってもよい。これは図６に示されている。強さの別の観点は、ルーティングネットワークが自然回復することである。
６．本発明の実施例にしたがって、新しい層をルーティングネットワークの一番上に導入することができるので、異なるネットワークの元のルーツノードを子ノードに変換するように重ねられた共通のルーツノードにより、現在のルーティングネットワークをリンクさせることができる。これは、ネットワークを結合させて、異なる全国地域に拡張できることを意味する。
７．新しいサービスに関してノードを更新させる必要がないので、このタイプのルーティングネットワークにより、新しいサービスの導入が可能になり、ノードは単にルーティングを提供するだけでよく、ルーティング情報を発生させる対象となるデータを知っていなくてもよい。従来のネットワークでは、新しい情報がネットワークに導入された時に更新されなければならない番号変換ファイルをノードが含んでいた。本発明にしたがうと、ネットワーク動作においてこの要求は減少されるか除去される。
上で説明した階層的な構造は一般的にバイナリツリー構造であるが、これらはバイナリでもツリー状でもある必要はない。構造は例えば２次元ではなく３次元としても考えることができ、および／または、バイナリ方法の代わりに多重リンクを備えていてもよい。しかしながら、重要な観点は、“上位”層のノードがより少なく、“下位”層のノードよりも多くの情報を保有しているような階層である。
使用する構造のレイアウトは、実行する必要があるタスクに適合するように最適化することができる。
上で説明した個人ナンバリングサービスに関する実施例は固定ネットワークと関連させて説明したが、固定ネットワークと移動セルラネットワークの統合であるネットワークにも適用することができる。実際、実施例はセルラネットワーク単体に適切である。
【図１】
0003681754.tif 000002
【図３】
0003681754.tif 000003
【図２】
0003681754.tif 000004
【図４】
0003681754.tif 000005
【図５】
0003681754.tif 000006
【図６】
0003681754.tif 000007
【図９】
0003681754.tif 000008
【図７】
0003681754.tif 000009
【図８】
0003681754.tif 000010