(57)【要約】トランクによって接続された様々なノードを有する電話交換網の交換装置のコール・ルーティング・テーブルを自動構成するためのシステムであって、シグナリング・メッセージが周期的にトランク上に送信されて、接続されたノードにネットワーク・トポロジが通知され、トランク・グループを作成できるようにされ、かつネットワーク・ルーティング・テーブルが作成される。次いで、コールをネットワーク中で、ダイヤルされたアドレスに基づいてルーティングすることができ、このアドレスはルーティング・ディジットに、ルーティング・テーブルに格納されたルーティング構成に基づいて変換される。この構成が周期的に更新され、それにより手動の管理の必要性がなくなる。
2004519872.tif 000002
【特許請求の範囲】
【請求項１】
複数の相互接続されたノードを含むネットワークを自己構成することに備える遠隔通信システムであって、前記ノードの各々はトランク回線によって相互接続され、前記ノードの各々は、前記トランクの各々に関連付けられたシグナリング・メッセージを前記他のノードに送信する手段を有し、前記ノードの各々は前記シグナリング・メッセージを受信する手段を有し、前記ノードの各々は、後に送信されるシグナリング・メッセージの内容を決定するために前記受信されたシグナリング・メッセージを解釈し、かつそれによってコールをネットワークにおいてルーティングすることができるトランク・ルーティング情報を得る処理手段を有するシステム。
【請求項２】
シグナリング・メッセージの初期コンテンツが一意識別ノード番号のみであり、各トランクについて受信されたシグナリング・メッセージがノード番号サブツリーとして格納され、後続のシグナリング・メッセージが、前記識別ノード番号とその後に続く連結ノード番号サブツリーのリストからなる、請求項１に記載のシステム。
【請求項３】
等しいノード番号サブツリーのシグナリング・メッセージを受信するトランクが、トランク・ルーティングのために共通のグループに入れられる、請求項２に記載のシステム。
【請求項４】
刈り込みプロセスを連結ノード番号サブツリーにおいて、後続のシグナリング・メッセージの送信前に実行し、それにより循環ルーティング・パターンを除去する手段をさらに含む、請求項２に記載のシステム。
【請求項５】
前記送信する手段が、個々のコールのルーティング中にシグナリング情報の送信のために動作可能であり、これは、各ノードで蓄積されたノード番号サブツリー情報から計算されたルーティング・ディジット・セットを送信することを含み、ルーティング・ディジット・セットがコールのルーティングをネットワーク中でガイドして、循環ルーティング挙動を回避する、請求項２に記載のシステム。
【請求項６】
クランクバック代替ルーティングが、前記個々のコールのルーティングが成功するまで前記ルーティング・ディジット・セットを保持することによって提供され、前記コールを、クランクバック信号が前記コールにおいて受信された場合、現行ノードから再ルーティングできるようにする、請求項５に記載のシステム。
【請求項７】
前記ノード番号サブツリーおよび前記ルーティング・ディジット・セットが、特定の前記トランク回線におけるシグナリングのために使用される信号方式と互換性のある信号に変換される、請求項５に記載のシステム。
【請求項８】
前記ノード番号サブツリーのシグナリング・メッセージを前記他のノードに送信する速度が、サブツリーが不変である場合、低減され、前記速度の低減が、メッセージ帯域幅要件を低減するための機能を果たす、請求項２に記載のシステム。
【請求項９】
前記識別ノード番号がサブネットワーク識別コードを組み込んで、サブネットワーク識別コードが合致しないとき、前記ノード番号サブツリーを送信するのではなくサブネットワーク識別コードのみを前記他のノードに送信することによってネットワーク分割を可能にする、請求項２に記載のシステム。
【発明の詳細な説明】
【０００１】
（明細書）
本発明は、遠隔通信交換システムに関し、詳細には、トランクによって接続された交換装置の交換網であって、装置に接続されたポートの間でコールをルーティングするために自動的に自己構成する交換網に関する。
【０００２】
本発明は特に、「Ｇｕｅｌｄｅｎｐｆｅｎｎｉｇ他」の米国特許第４，２２８，５３６号および「Ｂｒｅｉｄｅｎｓｔｅｉｎ他」の米国特許第４，２２９，８１６号に記載されたモジュラー交換装置による使用に適する。これらの特許は、主として電話交換システムとして使用される時分割デジタル通信システムを開示しており、そのモジュラー、分散型のアーキテクチャにより、小さいポート・サイズでの特に魅力のあるコスト／ポート挙動を特徴とする。この電話交換システムはＩＧＸ（Ｉｎｔｅｇｒａｔｅｄ Ｓｅｒｖｉｃｅｓ Ｄｉｇｉｔａｌ Ｎｅｔｗｏｒｋ Ｇａｔｅｗａｙ ｅＸｃｈａｎｇｅ）として知られている。
【０００３】
これらのＩＧＸシステムは多数のタイプのネットワークに適用されており、これには固定および移動の戦術的軍事施設が含まれる。これらの軍用システムの構成は特に、高速な「現場で」の配備に対していくつかの課題を提示する。構成プロセスは、ネットワーク内でコールをルーティングする（トランク・ルーティング）ために大規模なデータベースを交換システム内で作成することを含む。このデータベースが各現場またはネットワーク・ノードで構築されるときにのみ、コールを適切に、そのノードを通じてルーティングすることができる。これを複雑にするものは、訓練を受けた人員が各ノードで必要であること、およびこの作業を「砲火を浴びて」いるときに行う難点である。戦術的ネットワーク・トポロジはまた本来大変に動的でもあり、ノードが消滅し、場合によってはネットワーク内の異なる場所で再度出現する。
【０００４】
本発明は、このようなネットワークを本質的に自己構成するものにして、ノードを、ネットワーク中でコールをルーティングできるようにするために、最小限の現場での構成（ＡＤＭＩＮｉｓｔｒａｔｉｏｎ）が必要とされるようにするためのシステム（方法および装置）を提供する。本発明は、ネットワークの個々の各ノードがその場所をネットワーク内で自動的に決定できるようにし、トランク・ルーティング・テーブルを構築してネットワーク全体のコールのルーティングを可能にする。これは、コールを処理するためのこのようなシステムにおいてすでに設けられたコントロール・ソフトウェアに加えて、交換システム・コントロール・ソフトウェア内に存在するソフトウェア・アルゴリズムを通じて実施される。
【０００５】
簡単に言えば、本発明によるシステムは情報を周期的に、そのトランク（ノードを相互接続する回線）のあらゆるものにおける各ノードから送出し、ローカル・ノードおよびそれが学習した全てのノードについての情報を与える。この情報は同様に周期的に各ノードによって受信され、ネットワークについてのそのローカル情報を更新するために使用される。次いで、この更新された情報が、次の世代の更新が起こるとき、送出される。最終的に、各ノードがネットワーク全体のトポロジを学習しているようになり、コールをネットワークのすべての部分にルーティングすることが可能となる。更新プロセスが継続するので、ネットワーク・トポロジにおけるいかなる変化も自動的に取り上げられ、結果として「自己回復」ネットワークとなる。本発明は、ソフトウェア・アルゴリズムまたはプログラムにおいて実施され、これらがネットワークの自己構成に影響を及ぼすデータを処理する。
【０００６】
本発明の前述および他の特徴は、以下の記載を添付の図面と共に読むときにより明らかになるであろう。
図３はＩＧＸネットワークの個々のノード１ないし７を示す。このシステムは、各ノードがその場所をネットワーク内で自動的に決定できるようにし、トランク・ルーティング・テーブルを構築してネットワーク全体のコールのルーティングを可能にする。この目的は、ネットワークのルーティングに関係するすべてのトランクのＡＤＭＩＮを、排除しないまでも、最小限にすることである。
【０００７】
各ＩＧＸノード（分散したスイッチ）は、一意のコード番号を獲得することを必要とする。ノード番号はネットワーク内のノードを一意に識別し、ネットワーク・ルーティングのためのオフィス・コードとして動作することができる。
【０００８】
その各ＡＴＲＣ（Ａｕｔｏｍａｔｉｃ Ｔｒｕｎｋ Ｒｏｕｔｅ Ｃｏｎｆｉｇｕｒａｔｉｏｎ）トランクについて、ＩＧＸノードは、そのトランクが接続されるＩＧＸネットワーク・セグメントのノード番号サブツリーを決定することができなければならない。トランク・グループ分割およびグルーミングが導入するであろう複雑化を回避するため、各トランクが単独であると見なされるようになり、実際にはこのスキームにおいて予め定められたトランク・グループはない。さらに、トランク回線およびレジスタ・シグナリングをチャネルにより関連付けて、トランクの宛先を、そのトランクを介して受信された数値によって明白に決定できるようにしなければならない。これは、機能がアトミックに処理される場合、プライマリ・レート（ＰＲＩ）ＩＳＤＮ信号方式など、代替信号方式の使用をあらかじめ除外するものではない。
【０００９】
ノード番号サブツリーがトランクについて決定された後、このトランクを、動的に作成されたトランク・グループに追加しなければならず、このメンバは等しいノード番号サブツリーを共有する。トランク・グループのサブツリーを含む宛先ノード番号は、ＩＧＸによるそのグループにおけるトランクの選択を、コールをそれらのノードにルーティングするときに可能にする。
【００１０】
次いで、コールをネットワーク全体で決定論的に、ダイヤルされたアドレスに基づいてルーティングすることができ、このアドレスは、ノード番号とその後に続くステーション番号からなる。これがルーティング・ディジットに変換され、コールがその宛先に進行する。
【００１１】
図３のネットワークについての例示的ノード番号およびディジットの割り当てが、以下の表において与えられる。
例示的ネットワーク：
【００１２】
【表１】
2004519872.tif 000003
一意のノード番号の取得の考察
ノードが一意のノード番号を得ることができるいくつかの手段がある。１つの方法は、ノード番号をシェルフ・ゼロの（ｓｈｅｌｆ ｚｅｒｏ’ｓ）システム・コントローラ・ボード・シリアル番号（これは、システム・ソフトウェアが読み取ることができるシリアル番号を含む回路基板であり、常にＩＧＸノードに存在する）から導出し、なんとかしてこれを「小さい」一意の番号に低減することである。ノード番号は小さくするべきであり、これは、ルーティングのために使用され、ステーション番号の最初のアドレス・ディジットを形成するからである。
【００１３】
この方法は、ＡＤＭＩＮを必要としないので魅力があるが、現実世界では実施不可能であるように思われる。作業現場に設定されたコントローラ・ボードが、いずれかの理由のために置換された場合、そのノードにおけるすべての電話番号が変更になる。さらに、シリアル番号が使用されるとき、電話番号簿をあらかじめ準備することはできない。ノード番号を、実施可能にするために現場でＡＤＭＩＮする必要があるように思われる。ＩＧＸは現在、データベースにおいて定義された「ネットワーク」番号を有する。これは通常ゼロに設定されるが、容易にノード番号としての機能を果たすことができる。
ノード番号サブツリーの決定の考察
ノード番号サブツリーの決定には、ネットワークの各ノードが３つのタスクを同時かつ連続的に実行することが必要である。
【００１４】
第１に、各ローカルＡＴＲＣトランクが、ローカル・ノード番号サブツリーをそのリモート・ピアに周期的に送信しなければならない。リモート・ノードによって受信されたとき、これがこのＡＴＲＣトランクについてのリモート・ノード番号サブツリーとなり、そのトランクについて格納されたいかなる既存のものにも取って代わる。最初は、送信されたローカル・ノード番号サブツリーは、単にローカル・ノード番号自体である。
【００１５】
第２に、各ノードが、すべてのＡＴＲＣトランクから受信されたリモート・ノード番号サブツリーをマージし、その結果をこのノードのノード番号に追加しなければならない。次いで、これがこのノードについての単一のローカル・ノード番号サブツリーとなる。このプロセスは、ローカル・ノードを含むいかなるサブツリーも除去するために刈り込みして、循環（ｒｉｎｇ−ａｒｏｕｎｄ−ｔｈｅ−ｒｏｓｙ）パターンを防止することを含まなければならない。
【００１６】
第３に、各ローカルのＡＴＲＣトランクが、リモート・ノード番号サブツリーをそのリモート・ピアから周期的に受信し、これを格納し、これをトランクに関連付けなければならない。
【００１７】
上の３つのステップを連続的に繰り返さなければならず、これは、送信された最初のノード番号サブツリーが単一のリモート・ノード番号しか含まないからである。メッセージの２回目のラウンドの後にのみ、次のレベル以降の接続ノードが含まれるようになる。最終的に、ネットワーク全体のトポロジが、所与のノードにおけるすべてのＡＴＲＣトランクにおいて受信されたリモート・ノード番号サブツリーのセットにおいて反映されるようになる。
【００１８】
この動的ルーティング方法についてのアルゴリズムを記載（かつ次いで実施）する助けとするために、ノード番号サブツリーの表現のための表記法が採用される。ノード番号サブツリーは、単一のノード番号として、あるいは単一のノード番号とその後に続く、カンマによって分離され、かつ（）で囲まれた１つまたは複数のノード番号サブツリーのリストとして、形式的に定義することができる。バッカス記法（ＢＮＦ）におけるこの再帰的定義を、以下のように与えることができる。
【００１９】
【数１】
2004519872.tif 000004
この表記法におけるいくつかの有効なノード番号サブツリーは、以下の通りである。
【００２０】
１２
１２（４，６，７）
１２（４，６（２），７）
１２（４，６（２，３（９，８，１１）），７）
この表記法を使用して、ノード番号サブツリーを送信、受信かつ処理する反復的プロセスが記載される（この単純な実施例は、先に与えられたネットワークの実施例ではない）。
【００２１】
１）ノードがブートした直後、これはすべてのそのＡＴＲＣトランクについてのノード番号サブツリーをクリアし、そのローカル・ノード番号（たとえば、５）を決定し、これがそのノードのローカル・ノード番号サブツリーの初期値となる。
【００２２】
２）ローカル・ノード番号サブツリーがすべてのＡＴＲＣトランクにおいて送出される。
３）これらのトランクに関連付けられたリモート・ノードがこのノード番号サブツリーを受信かつ格納し、これを、それが受信されたところの各トランクに関連付ける。以下の値が格納される。
【００２３】
５
４）同時に、ローカル・ノード５が、ノード番号サブツリーをそのＡＴＲＣトランクから受信中となり、それらを（３）に記載したように格納する。ローカル・ノード５が以下のノード番号サブツリーをその（たとえば、３）ＡＴＲＣトランクにおいて受信すると仮定する。
【００２４】
Ｔｒｕｎｋ Ａ：４
Ｔｒｕｎｋ Ｂ：７
Ｔｒｕｎｋ Ｃ：８
５）次いで、マージ・プロセスがノード５についてのローカル・ノード番号サブツリーを、受信されたばかりのサブツリーをローカル・ノード番号に追加することによって更新し、以下の結果となる。
【００２５】
古いローカル・ノード番号サブツリー：５
新しいローカル・ノード番号サブツリー：５（４，７，８）
６）（２）に進む。
【００２６】
コールのルーティングは、現行のノード番号サブツリーに基づいて即時に開始することができる。このプロセスが何回か（ネットワークのサイズおよびトポロジに応じて）反復した後、ローカル・ノード・サブツリーが安定し、次いでこれを使用してネットワークのいかなる部分にもルーティングすることができる。格納されたノード番号サブツリーが等しいトランクが動的グループに入れられ、そのグループに関連付けられたノード番号サブツリーにおいて番号が現れるいかなるノードも、このグループ内のトランクから到達可能であるとわかる。さらに、ノード番号サブツリー内で左から右に走査するとき、ノード番号を発見する前に横切られた「（」の数が、そのノードへのホップの数を示す。このホップ・カウントを使用して、代替のものが存在するときに最適なルートを選択するために、特定のルートの相対的コストを判断することができる。
【００２７】
送信、受信、マージ、送信などのプロセスが連続的に起こるので、いかなるトランクの再配置、ネットワーク機能停止またはネットワーク追加も自動的に取り上げられ、ＡＤＭＩＮがほとんどあるいはまったく必要とされない真に自己構成するネットワークが作成される。
【００２８】
前述のように、ローカル・ノード番号サブツリーの刈り込みが、循環パターンの作成を防止するために必要とされる。これは、ローカル・ノード番号サブツリーにおいて、ローカル・ノード番号で開始するいかなるサブツリーも含まないことによって実現される。
【００２９】
以前に図示したネットワークについてのローカル・ノード番号サブツリーの発展を示す一実施例は、プロセス全体を例示するための機能を果たす。世代０（Ｇｅｎｅｒａｔｉｏｎ ０）は、ローカル・ノード番号サブツリーがローカル・ノード番号に設定される初期状態である。
【００３０】
【数２】
2004519872.tif 000005
2004519872.tif 000006
2004519872.tif 000007
2004519872.tif 000008
2004519872.tif 000009
2004519872.tif 000010
2004519872.tif 000011
続く世代は、ネットワーク構成が新しいノードの出現または既存のノードの損失により変化しない限り、不変のローカル・ノード番号サブツリーを生成する。
【００３１】
送信する必要のあるデータの量はネットワーク・サイズと共に増大するが、高速送信技術が使用される場合（プライマリ・レートＩＳＤＮ（総合サービス・デジタル網）「Ｄ」チャネルなど）これは問題にならない。さらに、各ノードにネットワーク全体のトポロジを所有させることには、以下のような著しい利点がある。
【００３２】
１）各ノードがネットワーク全体を知っており、遠隔のノードが到達不可能となる場合、局所的な動作を取ることができる。たとえば、重大なリソースが、到達不可能となっているノードに存在する場合、局所的な警報を与えることができる。
【００３３】
２）いかなるノードへの物理ホップ・カウントも容易に決定され、代替ルーティングをガイドするために使用することができる。
３）ネットワーク・ルーティングが常に決定論的であり、ノードが最近到達不可能になっていない限り、無駄なルーティングの試みはなくなる。
動的に作成されたトランク・グループへのトランクの追加の考察
等しいノード番号サブツリーを共有するＡＴＲＣトランクが動的グループに入れられ、これは、これらのトランクが共通の宛先を共有することがわかっているからである。このプロセスはまた、ネットワークにおける既知の各ノードについてのディジット・テーブルの作成も含む。これらのディジット・テーブルは、宛先ノードへの最も直接の（ホップ・カウントによって決定された）ルートを有する動的トランク・グループを、宛先ノードへのそのホップ・カウントがより高い他の動的トランク・グループへの代替ルーティング（望むなら）と共に指示する。
【００３４】
これらの動的トランク・グループの作成では、トランクのノード番号サブツリーの最も左のノード番号を比較して、適切なグループ・メンバーシップを決定することのみが必要であり、これはその番号が、トランクが接続される先のノードを表すからである。これはまた、擬似的トランク・グループが、より最近のサブツリー情報を有するトランクの結果として作成されることを、トランクが同じ宛先ノードに通じるとしても防止する。このスキームでは、動的グループと共に格納されたノード番号サブツリーが、グループ・メンバのいずれかにおいて受信された最長のものとなり、これは、より長いサブツリーがより多くの情報を含むからである。
【００３５】
これらのグループおよびディジット・テーブルの作成は既存のシステム管理機能に取って代わるのではなくその機能を補い、全体のシステム・オペレーションが無矛盾かつ予測可能のままとなるようにすることができる。この機能を概念上、ＡＤＭＮの上の層として処理するべきである。
ＡＴＲＣプログラムは、交換システム・アーキテクチャ内で統合される。
【００３６】
参照のため、図１は好ましい実施形態の、時分割デジタル通信システムにすることができる電話交換システムを示し、これは「Ｇｕｅｌｄｅｎｐｆｅｎｎｉｇ他」の米国特許第４，２２８，５３６号および「Ｂｒｅｉｄｅｎｓｔｅｉｎ他」の米国特許第４，２２９，８１６号において教示されている。しかし、本発明のＡＴＲＣシステムは決して特定のシステム・アーキテクチャに依拠せず、ただし中央処理装置（ＣＰＵまたはマイクロプロセッサ）が存在すると仮定される程度までは依拠することに留意されたい。複数のトランク回線の間の音声／データ交換に備える交換マトリクスがある。これらのトランク回線は、ネットワーク要素としてこれらのノードからなる通信ネットワークの近接したノードに外部的に接続する。交換マトリクスおよびトランク回線がその入力／出力インターフェイスを通じてシステム・コントローラと接続し、かつこれによってコントロールされる。システム・コントローラは、これらの入力／出力インターフェイスに加えて、マイクロプロセッサにすることができる中央処理装置（ＣＰＵ）、およびその関連付けられた読み取り専用およびリード／ライト・メモリからなる。読み取り専用メモリは、コール処理タスクの実行においてＣＰＵに指図するためのコントロール・プログラムを含む。リード／ライト・メモリは、進行中のコールに関連付けられた一時的データの一時記憶域のためのスクラッチパッド・エリア、コールのルーティングを決定するためのデータベース・ルーティング・テーブル、入力または出力の前のデータおよび経時的に変化する可能性がある他のデータを保持するためのバッファを含む。読み取り専用およびリード／ライト・メモリの間の区別は機能上のものでしかなく、システムにおいて実際に使用されるメモリのタイプに反映するものではない。たとえば、すべてのメモリをリード／ライト・タイプにすることができるが、そのメモリのコントロール・プログラム格納部は慣例により、初期プログラム・ロード・オペレーションが行われた後に書き込まれることはない。
【００３７】
図２は、ＡＴＲＣ機能がシステムに統合されるときの追加の要件を示すことによってメモリ割り振りを詳説する。読み取り専用エリアには特殊なＡＴＲＣタスクがある。このタスクは、本発明の主題であるアルゴリズムを実施する。通常、タスク・スケジューラが、必要とされるときにコントロールを標準コール処理タスクへ渡し、これはすでにシステムにおいて、必要とされたコール処理機能を実行するために存在するものである。特殊ＡＴＲＣタスクの追加には、スケジューラがコントロールをそのタスクに定期的に渡して、それがその機能を実行できるようにすることが必要となる。これらの機能は、すべてのＡＴＲＣトランク上のローカル・ノード番号サブツリーを他のネットワーク・ノードに送出すること、ＡＴＲＣトランクにおいて他のネットワーク・ノードから入力されたサブツリーを受信かつ処理すること、ＡＴＲＣトランク・グループおよびこれらのグループについてのルーティング・ディジット・セットを決定すること、および最終的にＡＴＲＣルート変換を、ルート変換データベース部内でこの目的のために予約されたリード／ライト・メモリに戻すように書き込むことからなる。このメモリ・エリアを図２において、これを特殊ＡＴＲＣタスクにリンクする矢印により示し、これはそのメモリがそのタスクによってコントロールされるからである。
コールのルーティングは、以下のように実施される。
【００３８】
単に宛先ノード番号およびステーション番号を送信することができ、かつコールを中間ノードで、単にその宛先に最も直接的に通じるトランクを選択することによってルーティングすることができると思われる可能性がある。この方法は実際には、１つの追加の規則が追加された場合、実施例のネットワーク（図３）において機能し、この規則は、決してコールが到着したところと同じトランク・グループ上に戻るようにルーティングしないことである。たとえば、ノード２からノード５へのコールでは、コールがノード３に、ノード１を介して到達し、かつすべての「Ｄ」トランクがビジーであった場合、この規則が、ノード４を介してノード５に到達するための努力においてノード１に戻るようにルーティングすることを防止する。
【００３９】
しかし、実施例のネットワークが、トランク「Ｈ」をノード３および４の間に追加することによって修正された場合、この簡素な規則は失敗する。すべての「Ｄ」および「Ｅ」トランクのビジー状態に遭遇するノード２からノード５へのコールはこのとき、ノード１から３から４から１から３から４へなど循環的にルーティングすることができる。この病的な挙動は、発信ノードからのルーティング情報ではなく中間ノードでのローカル・ルーティング情報を使用する結果として生じる。発信ノードからのルーティング情報の使用は、ネットワーク中のコールによって取られた先行するパスを考慮に入れる。
【００４０】
この解決策は、ルーティング情報（ルーティング・ディジット・セット）を発信側から送信し、その情報をいかなる中間ノードでも使用することである。このルーティング・ディジット・セットは発信ノードにおけるローカル・ノード番号サブツリーから、かつ宛先ノード番号から導出される。参照のため、以下は、修正された実施例のネットワークについてのノード番号サブツリーの完成した最終状態である。
【００４１】
Ｇｅｎｅｒａｔｉｏｎ ６（トランクＨをノード３および４の間に追加）
【００４２】
【数３】
2004519872.tif 000012
2004519872.tif 000013
ノード２からノード５へのコールについて、ノード２についてのノード番号サブツリーが以下のように必要とされる。
【００４３】
【数４】
2004519872.tif 000014
このサブツリーおよび宛先ノード（５）から、以下のルーティング・ディジット・セットを導出することができる。
【００４４】
（２１４５，２１４３５，２１３５，２１３４５）
このルーティング・ディジット・セットは、ノード２からノード５へのすべての可能なルートを与え、この完全なディジットのセットはノード２（もちろんその後にステーション番号が続く）によってこのコールのためのアドレス・ディジットとして送出されなければならない。このスキームでコールを受信すると、ノードはディジット・サブストリングにおける次のノード番号を使用して、出力の動的トランク・グループを選択し、サブストリングの長さを最も直接のルートの指示として考慮に入れる。次いで、可能であればコールがそのグループにおけるトランクにルーティングされ、送信されたルーティング・ディジット・セットは、すでに使用されたルーティング・ディジットを削除した後に選択されたノードを有するサブストリングに残っているディジットからなる。一実施例は、以下のように明らかにする。
【００４５】
ノード２で、以下を有する。
（２１４５，２１４３５，２１３５，２１３４５）ＳＴＮ
ノード２は発信ノードであり、そのノード番号を処理の前に除去し、以下を残す。
【００４６】
（１４５，１４３５，１３５，１３４５）ＳＴＮ
次いで、ノード２が次のディジット（１）を使用して出力のトランク・グループを選択する。この場合、選択肢がないので、ノード１へのトランクが選択され、以下のルーティング・ディジット・セットがノード１に送信される。
【００４７】
（４５，４３５，３５，３４５）ＳＴＮ
次いで、ノード１が次のディジット（４）または（３）を使用して出力のトランク・グループを選択する。両方の文字列のセットが同じ長さを有し、そのためこれらのルートは同じ優先度を有する。ノード１はノード４へのトランクを選択し、以下のルーティング・ディジット・セットがノード４に送信される。
【００４８】
（５，３５）ＳＴＮ
次いで、ノード４が次のディジット（５）または（３）を使用して出力のトランク・グループを選択する。サブストリング（５）が（３５）より短く、そのためノード５への直接のルートが優先度を有する。しかし、その動的グループにおけるすべてのトランクがビジーであると仮定しよう。そこで、ノード４はノード３へのトランクを選択し、以下のルーティング・ディジット・セットがノード３に送信される。
【００４９】
（５）ＳＴＮ
次いで、ノード３が次のディジット（５）を使用して、ノード５への出力のトランク・グループを選択し、以下のルーティング・ディジット・セットがノード５に送信される。
【００５０】
ＳＴＮ
次いで、ノード５はコールを、ステーション番号が付けられたＳＴＮにルーティングする。ＳＴＮはステーション番号、または、コールされたアドレスを適切に識別するために必要とされる他のいずれかの情報を表す。
【００５１】
ノード番号サブツリーを生成するため、かつルーティング・ディジット・セットをそれらから抽出するためのアルゴリズムは、構造化ＢＡＳＩＣ言語において書かれたネットワーク・シミュレーション・プログラムに組み込まれている。上で与えられた実施例のノード番号世代およびルーティング・ディジット・セットは実際には、そのプログラムからの出力である。このプログラムがここで与えられ、その後に行毎の記述が続く。
【００５２】
【数５】
2004519872.tif 000015
2004519872.tif 000016
2004519872.tif 000017
2004519872.tif 000018
2004519872.tif 000019
2004519872.tif 000020
2004519872.tif 000021
2004519872.tif 000022
上のプログラムが書かれる構造化ＢＡＳＩＣ言語はある組み込み関数を有し、これらが上のプログラムにおいて依拠される。したがって、上のプログラムにおいて使用された組み込み関数を以下に記述する。
【００５３】
本発明のアルゴリズムを記述するためにＢＡＳＩＣを選択することは恣意的なものであり、いかなる言語を使用することもできることが指摘されるべきである。したがって、このＢＡＳＩＣの使用は、いかなる制限の意味にも取られるべきではない。
【００５４】
上のプログラムにおいて使用された組み込みのＢＡＳＩＣ関数の簡単な定義は以下の通りである。
ＬＥＦＴ（ｓｔｒｉｎｇ＄，ｌｅｎｇｔｈ）
文字列「ｓｔｒｉｎｇ＄」の左から長さ「ｌｅｎｇｔｈ」分の文字からなる左方のサブストリングを返す。
ＣＶＴ＄＄（ｓｔｒｉｎｇ＄，−１）
文字列「ｓｔｒｉｎｇ＄」からなる文字列から、すべてのスペース、タブおよび特殊文字が除去され、かつ小文字が大文字に変換されたものを返す。
ＣＶＴ＄＄（ｓｔｒｉｎｇ＄，２）
文字列「ｓｔｒｉｎｇ＄」からなる文字列から、すべてのスペースおよびタブが除去されたものを返す。
ＬＥＮ（ｓｔｒｉｎｇ＄）
文字列「ｓｔｒｉｎｇ＄」の長さを返す。
ＩＮＳＴＲ（ｐｏｓ，ｓｔｒｉｎｇ１＄，ｓｔｒｉｎｇ２＄）
文字列「ｓｔｒｉｎｇ１＄」内の「ｐｏｓ」の位置で探索を開始して、文字列「ｓｔｒｉｎｇ１＄」内の文字列「ｓｔｒｉｎｇ２＄」の位置を返す。文字列「ｓｔｒｉｎｇ２＄」が文字列「ｓｔｒｉｎｇ１＄」に含まれていない場合、０を返す。
ＭＩＤ（ｓｔｒｉｎｇ＄，ｐｏｓ，ｌｅｎｇｔｈ）
位置「ｐｏｓ」から開始し、かつ長さ「ｌｅｎｇｔｈ」分の文字からなる「ｓｔｒｉｎｇ＄」のサブストリングを返す。
ＲＩＧＨＴ（ｓｔｒｉｎｇ＄，ｐｏｓ）
位置「ｐｏｓ」から開始する文字列「ｓｔｒｉｎｇ＄」のすべての文字からなる右方のサブストリングを返す。
ＮＵＭ＄（ｎｕｍｂｅｒ）
数「ｎｕｍｂｅｒ」の１０進文字表現を返す。正の値ではスペースが数の先頭にあり、負の数では「−」が数の先頭にある。
【００５５】
以下は、プログラムの行毎の記述である。
１０〜３０行
ネットワーク・シミュレーション（Ｓ）または手動データ入力を使用したアルゴリズムのテスト（Ｍ）がリクエストされるかどうかを決定する。
【００５６】
４０〜２５０行
手動データ入力モード。最初に、ノード番号がリクエストされる。次いで、ノード番号サブツリーがリクエストされる。サブツリーはカンマによって分離され、括弧で囲まれ、以前に生のローカル・ノード番号サブツリーを得るために記述したようにノード番号に追加される。次いでこれが刈り込みされて、いかなる循環ルーティング・パターンも除去され、次いでクリーン・アップされて、サブツリーがその標準の形式に戻される。次いで、この結果がプリントされる。
【００５７】
２７０〜３４０行
ネットワーク・シミュレーション・モード。１から７まで付番された７つのノードが作成される。
【００５８】
３５０〜６２０行
ネットワーク・シミュレーション・モード。ローカル・ノード番号サブツリーの現行の値が、近接したノードに通じる各トランク・グループについてのサブツリーと共にプリントされる。
【００５９】
６３０〜７８０行
ネットワーク・シミュレーション・モード。ローカル・ノード番号サブツリーがトランク・グループに割り当てられ、ローカル・ノード番号サブツリーを近接したノードに周期的に送信することがシミュレートされる。
【００６０】
７９０〜８５０行
ネットワーク・シミュレーション・モード。ローカル・ノード番号サブツリーの次世代が生成され、これはカンマによって分離された受信サブツリーを連結し、その結果を括弧で囲み、その結果をローカル・ノード番号に追加し、次いでクリーン・アップして、結果として生じるサブツリーをそれらの標準の形式に戻すことによって行われる。
【００６１】
８６０〜１０２０行
ネットワーク・シミュレーション・モード。新世代のローカル・ノード番号サブツリーが、以前の世代に対してチェックされる。いずれかのサブツリーが変化していた場合、シミュレーション・ループが別の世代について継続する。そうでない場合、サブツリーは安定しており、ネットワーク全体がサブツリーの現行の世代によって表され、シミュレーション・ループが終了する。
【００６２】
１０３０〜１２５０行
ネットワーク・シミュレーション・モード。ルーティング・ディジット・セットが各ソースおよび宛先ルートの組み合わせについて計算され、プリントされる。次いで、プログラムが終了する。
【００６３】
１２６０〜１３２０行
ＦＮＣＬＥＡＮＵＰ＄（ＮＴＲＥＥ＄）関数。この関数は、生のノード番号サブツリーＮＴＲＥＥ＄のクリーン・アップを、刈り込みプロセスの結果から生じるいかなる空のサブツリー・コンポーネントも除くことによって実行する。これは、サブツリーを標準の形式に戻して後の構文解析を容易にし、サブツリーの長さが「ジャンク」コンポーネントのために増大することを防止する。
【００６４】
１３３０〜１５２０行
ＦＮＰＲＵＮＥ＄（ＴＲＥＥ＄）関数。この関数はノード番号サブツリーＴＲＥＥ＄を刈り込みして、現行ノードを含むいかなるサブツリー・コンポーネントも除く。これは、循環のルーティング・パターンの発展を防止するために行われる。コンポーネントが現行ノード番号を含むとき、現行の括弧レベルの下のコンポーネントのすべての文字が削り取られ、その結果が、次のループ反復のための新しいノード番号サブツリーとなる。この関数は、現行ノード番号を含むコンポーネントがサブツリーに残っていないとき、戻る。
【００６５】
１５３０〜１６００行
ＦＮＲＥＰＬ＄（ＩＴＥＭ＄，ＴＥＸＴ＄，ＲＥＰＬ＄）関数。この関数は、ＦＮＣＬＥＡＮＵＰ＄関数によって使用される。これは、文字列ＩＴＥＭ＄内で見つかった文字列ＴＥＸＴ＄のすべての発生を、置換文字列ＲＥＰＬ＄で置き換える。
【００６６】
１６１０〜１７１０行
ＦＮＲＯＵＴＥ（ＴＲＥＥ＄）関数。この関数は、ローカル・ノード番号サブツリーＴＲＥＥ＄を与えられると、シミュレーションにおける７つの各宛先ノードに対して送信されるルーティング・ディジット・セットを計算する。各宛先ノードについて、別の関数ＦＮＤＩＧＳがコールされて、その宛先についてのルーティング・ディジット・セットがプリントされる。
【００６７】
１７２０〜１８５０行
ＦＮＤＩＧＳ（ＤＩＧＩＴＳ＄）関数。ＴＲＥＥ＄、ＰＯＳおよびＤＥＳＴ＄は、この関数の暗黙の引数である。この関数は、ローカル・ノード番号サブツリーＴＲＥＥ＄内の文字位置ＰＯＳで開始して、宛先ノードＤＥＳＴ＄のためのルーティング・ディジット・セットを計算かつプリントする。これは、サブツリーにおける各カンマ区切りノード番号についてループし、これを宛先ノードと比較し、それが合致する場合、それをプリントする。サブツリーにおける最後の右括弧が見つかるとき、関数が戻る。複合サブツリー（すなわち、単独のノード番号からなるのではなく、ノード番号とその後に続く括弧で囲まれたノード番号のリストからなるもの）に遭遇した場合、ＦＮＤＩＧＳが再帰的にコールされてサブツリーが処理される。このようにして、ローカル・ノード番号サブツリー全体がトラバースされ、宛先へのすべての可能なルートが発見され、プリントされる。
「クランクバック」代替ルーティングの考察
クランクバック代替ルーティングは、所与のノードにおいて宛先へのすべてのトランクがビジーであると判明するとき、コールを完了する確率を増す方法であり、これは、先行するノードにバック・アップすること、および代替ルートをそこで試行することによって行われる。
【００６８】
クランクバック代替ルーティングは、従来技術において実施することが困難であり、これはネットワーク・ノードによるネットワーク全体のトポロジの知識の欠如のためである。しかし、クランクバック代替ルーティングは容易にＡＴＲＣスキームにおいて提供される。コールをルーティングするとき、ノードは単にコールのためのルーティング・ディジット・セットを、そのコールがうまく完了されるかあるいは放棄されてしまうまで保持する。ノードが、宛先への使用可能なすべてのトランク・グループにおけるすべてのトランクがビジーであることを発見するとき、話中音または表示を発信者に返すのではなく、ノードはクランクバック指示を返す。先行するノードがこの指示を受信し、そのグループにおけるすべてのトランクがビジーであったかのように進行し、次の代替ルートを選択するか、あるいは、すべての代替物が試行されている場合、先行するノードにクランクバック指示を返す。
【００６９】
各ノードが適切なルーティング・ディジット・セットを使用してコールをルーティングし続けるので、最適なルートを選択することができ、循環のルーティングを回避することができる。
ノード番号サブツリーおよびルーティング・ディジット・セットの送信の考察
電話方式において使用される従来の信号方式の範囲は従来、０〜９のディジット、およびシステムによって変わるいくつかの追加のコントロール信号を送信することに限定されてきた。これらは通常、任意のＡＳＣＩＩ（情報交換用米国標準コード）文字を送信することができず、これらはノード番号サブツリーにおいて使用される開および閉括弧、およびカンマ、および本発明において定義されたようなルーティング・ディジット・セット表記法などである。この問題を、いくつかの方法で回避することができる。
【００７０】
第１の方法は、表記法における括弧およびカンマ文字の代わりに、遭遇された最も共通の信号方式から選択された固有の制御文字を使用する。よりよい方法は、以前に定義したような抽象的な表記法を保持し、適切な制御文字を、トランクにおける送信または受信のときに必要とされる特定の信号方式の代わりに使用することである。２つの実施例が、このプロセスを例示するための機能を果たす。第１のものは、ノード番号サブツリー表記法のＤＴＭＦ（デュアル・トーン多重周波数）信号への可能な変換を示す。これは共通して使用された信号方式であり、押しボタン式電話器用の標準でもある。
【００７１】
４（１（２，３（５）），５（３（１（２））），６（７））
が、以下のようになる。
４＊１＊２Ａ３＊５＃＃Ａ５＊３＊１＊２＃＃＃Ａ６＊７＃＃
以下の実施例は、ＤＴＭＦに変換されたルーティング・ディジット・セットを示す。
【００７２】
（１４５，１４３５，１３５，１３４５）１２１２
が、以下のようになる。
＊１４５Ａ１４３５Ａ１３５Ａ１３４５＃１２１２
両方の実施例において、「（」がＤＴＭＦの「＊」に変換されており、「）」がＤＴＭＦの「＃」に変換されており、「，」がＤＴＭＦの「Ａ」に変換されている。他の変換ももちろん可能である。
ＡＴＲＣメッセージ・トラフィックの低減の考察
ＡＴＲＣスキームの潜在的に高いメッセージ帯域幅要件を、多数のメッセージ送信速度を使用することによって低減することができる。たとえば、ローカル・ノード番号サブツリーが変化するときには、新しいセットの出力のメッセージがタイマＡによってスケジュール送信される。しかし、いくつかの等しいローカル・ノード番号サブツリーが連続して計算されるとき、出力のメッセージをタイマＢによってスケジュールすることができ、ただしＢはＡより長い持続時間のタイマである。このようにして、メッセージ・トラフィックを平均して低減することができるが、新しいノードおよびトランクの出現に対する高速の応答は保持される。
ネットワークの分割の考察
大規模なネットワークを複数のサブネットワークへ、それらを接続するゲートウェイ・トランクにより分割することはしばしば望ましい。この利点は、ゲートウェイを介して渡される情報をサブネットワーク識別のみに制限し、それにより外側のネットワークをサブネットワークのネットワーク・トポロジから隠すための能力である。これは、渡されるＡＴＲＣ情報の量を低減し、サブネットワークが外側のネットワークによって他のサブネットワークへの縦列のルーティングのために使用されることを効果的に防止する。
【００７３】
これを実施するため、ノード番号の概念が、ネットワークおよび／またはサブネットワーク識別を表す追加のディジットを含むように拡張される。これらをＡＤＭＩＮによって各ノードで入力することができる。
【００７４】
ノードがＡＴＲＣトランクにおける入力のノード番号サブツリーを受信するとき、これはこのとき、追加のネットワーク識別ディジット（文字列におけるまさに最初のノード番号の一部）をそれ自体のものに対して比較する。これらが同じであった場合、近接したノードが同じサブネットワークの一部であることがわかり、上に記載した標準ＡＴＲＣプロセスが適用される。しかし、サブネットワークが異なった場合、トランクがネットワーク間のゲートウェイ・トランクであることがわかり、サブネットワーク識別ディジットのみが、ローカル・ノード番号サブツリーの代わりに周期的に送信される。
【図面の簡単な説明】
【図１】本発明を実施する遠隔通信ネットワークの各ノードにおいて使用される交換装置のブロック図である。
【図２】図１に示す装置のメモリのより詳細なブロック図である。
【図３】図１および２に示すタイプの装置にすることができる各ノードの例示的ネットワークの図である。
【図４】図３のネットワークの修正を示す図である。
【図１】
2004519872.tif 000023
【図２】
2004519872.tif 000024
【図３】
2004519872.tif 000025
【図４】
2004519872.tif 000026
【国際公開パンフレット】
2004519872.tif 000027
2004519872.tif 000028
2004519872.tif 000029
2004519872.tif 000030
2004519872.tif 000031
2004519872.tif 000032
2004519872.tif 000033
2004519872.tif 000034
2004519872.tif 000035
2004519872.tif 000036
2004519872.tif 000037
2004519872.tif 000038
2004519872.tif 000039
2004519872.tif 000040
2004519872.tif 000041
2004519872.tif 000042
2004519872.tif 000043
2004519872.tif 000044
2004519872.tif 000045
2004519872.tif 000046
2004519872.tif 000047
2004519872.tif 000048
2004519872.tif 000049
2004519872.tif 000050
2004519872.tif 000051
2004519872.tif 000052
2004519872.tif 000053
2004519872.tif 000054
2004519872.tif 000055
2004519872.tif 000056
2004519872.tif 000057
2004519872.tif 000058
2004519872.tif 000059
2004519872.tif 000060
2004519872.tif 000061
2004519872.tif 000062
2004519872.tif 000063
2004519872.tif 000064
2004519872.tif 000065
2004519872.tif 000066
2004519872.tif 000067
2004519872.tif 000068
2004519872.tif 000069
2004519872.tif 000070
【国際公開パンフレット（コレクトバージョン）】
2004519872.tif 000071
2004519872.tif 000072
【国際調査報告】
2004519872.tif 000073
2004519872.tif 000074