(57)【要約】【課題】ネットワーク指定ルータの自動選択によるオーバーレイ・ネットワークの自動構成のための方法および構造を提供すること。【解決手段】複数の相互接続されたコンピュータを含むネットワークを自動的に構成する方法（および構造）が、複数のコンピュータのうちの複数台が指定ルータの役割を担うように構成するステップであって、この指定ルータが、どのコンピュータがその時点でオンラインかを判定することによってその時点のネットワーク構成を判定するステップと、この判定されたその時点のネットワーク構成を使用して、その時点でオンラインである相互接続されたコンピュータ間の隣接関係を定義するその時点のネットワーク・トポロジを判定するステップと、その時点のネットワーク・トポロジをネットワークに伝えるステップとを含む。またこの方法は、優先順位基準を定義するステップと、この優先順位基準に従って、指定ルータの役割を果たすように複数のコンピュータのうちの１台を自動的に選択するステップとを含む。
2005531199.tif 000002
【特許請求の範囲】
【請求項１】
複数の相互接続されたコンピュータを含むネットワークを自動的に構成する方法において、
前記複数のコンピュータのうちの複数のコンピュータが指定ルータの役割を担うように構成するステップであって、前記指定ルータが、前記相互接続されたコンピュータのうちどのコンピュータがその時点でオンラインかを判定することによってその時点のネットワーク構成を判定し、判定されたその時点のネットワーク構成を使用して、その時点でオンラインである前記相互接続されたコンピュータ間の隣接関係を定義するその時点のネットワーク・トポロジを判定し、前記その時点のネットワーク・トポロジを前記ネットワークに伝えるステップと、
優先順位基準を定義するステップと、
前記優先順位基準に従って、前記指定ルータの役割を果たすように前記複数のコンピュータのうちの１台のコンピュータを自動的に選択するステップとを含む方法。
【請求項２】
前記指定ルータの役割を担うように構成され、かつその時点でオンラインである前記各コンピュータが、前記優先順位基準に従って自分自身の優先順位を判定することによって前記指定ルータを自動的に選択する前記ステップに参加する、請求項１に記載の方法。
【請求項３】
前記指定ルータを自動的に選択する前記ステップが、前記ネットワークの構成が変化するにつれて定期的に更新される、請求項１に記載の方法。
【請求項４】
前記役割を担うように構成された前記複数のコンピュータの各コンピュータ内にリストを記憶するステップであって、前記リストが、前記指定ルータの役割を担うように構成された前記複数のコンピュータのうち自分以外のすべてのコンピュータのＩＤを含むステップをさらに含む、請求項１に記載の方法。
【請求項５】
前記役割を担うように構成された前記各コンピュータが、前記ネットワーク上でオンラインになると常に、最初は自動的に前記役割を担うようにするステップと、
前記役割を担うように構成された前記各コンピュータが、前記ネットワーク上の他のどのコンピュータもその時点で前記役割を果たしていないことを検知すると常に、自動的に前記役割を担うようにするステップと、
前記役割を担うように構成された前記各コンピュータが、優先順位の高い別のコンピュータがその時点で前記役割を果たしているかどうかを定期的にモニタするようにするステップのうち少なくとも１つをさらに含む、請求項１に記載の方法。
【請求項６】
前記自動的に選択するステップが、
前記指定ルータの役割を担ってきた第１のコンピュータ内に、前記第１のコンピュータが、前記役割を担うように構成される第２のコンピュータと通信した後も前記役割を継続する優先順位を有するかどうかを判定するステップを含む、請求項１に記載の方法。
【請求項７】
前記役割を担ってきた前記第１のコンピュータが、前記役割を担うように構成される前記複数のコンピュータのうち少なくとも１台の他のコンピュータとの接触を図るようにするステップと、
前記接触ごとに、前記役割を担ってきた前記コンピュータの１台および前記接触されたコンピュータが、前記優先順位基準の評価に基づいて前記役割の実施をやめるようにするステップとをさらに含む、請求項６に記載の方法。
【請求項８】
前記優先順位を判定するステップが、前記第１のコンピュータの識別番号と前記第２のコンピュータの識別番号との比較を含む、請求項６に記載の方法。
【請求項９】
ネットワーク内で指定ネットワーク・ルータの役割を担うことができるコンピュータにおいて、前記指定ネットワーク・ルータが、その時点のネットワーク・トポロジを判定して伝える機能を有するコンピュータであって、
事前に確立された優先順位基準と前記指定ネットワーク・ルータの役割を果たす際に実行するアルゴリズムとを記憶するストレージ・デバイスであって、前記事前に確立された優先順位基準が、前記役割を担うことができる複数の前記コンピュータ間の優先順位を定義するストレージ・デバイスと、
前記事前に確立された優先順位基準に基づいて、前記コンピュータがその時点で前記役割を果たす優先順位を有するかどうかを評価する判定モジュールとを含むコンピュータ。
【請求項１０】
前記コンピュータが、
前記ネットワーク上でオンラインになるたび、
前記ネットワーク上の他のどのコンピュータもその時点で前記役割を担っていないことを検知するたび、
自分自身よりも優先順位の高いどのコンピュータもその時点で前記役割を果たしていないことを検知するたび、および
前記ネットワーク上の他のいずれかのコンピュータがその時点で前記役割を果たしているかどうかを検知できないたびに、という条件のうち少なくとも１つに応じて自動的に前記役割を担うようにする命令を含む開始モジュール（initiation module）をさらに含む、請求項９に記載のコンピュータ。
【請求項１１】
前記事前に確立された優先順位基準が、その時点でオンラインの相互接続された前記コンピュータの識別番号に基づいて優先順位を定義し、前記判定モジュールが、その時点でオンラインの前記コンピュータが、その時点でオンラインの第２のコンピュータよりも高い優先順位と、その時点でオンラインのすべてのコンピュータに対する最も高い優先順位のうち一方を有するかどうかを評価する、請求項９に記載のコンピュータ。
【請求項１２】
ストレージ・デバイス内に記憶されたリストであって、前記役割を担う複数の前記コンピュータのそれぞれの識別番号を含むリストをさらに含む、請求項９に記載のコンピュータ。
【請求項１３】
前記指定ネットワーク・ルータの役割を果たす際に実行する前記アルゴリズムによって、前記コンピュータが前記リスト上の前記識別番号を使用して、前記リスト上の少なくとも１つの他のコンピュータと接触を図り、前記コンピュータが、
前記少なくとも１つの他のコンピュータと接触を図るための送信機と、
前記少なくとも１つの他のコンピュータから応答を受信するための受信機とをさらに含む、請求項１２に記載のコンピュータ。
【請求項１４】
前記事前に確立された優先順位基準が、その時点でオンラインの相互接続された前記コンピュータの識別番号に基づいて優先順位を定義し、前記判定モジュールが、応答を受信すると、その時点でオンラインの前記コンピュータが、前記受信された応答を送信したコンピュータよりも高い優先順位を有するかどうかを評価する、請求項１３に記載のコンピュータ。
【請求項１５】
自動構成機能を有するネットワークにおいて、
複数のコンピュータであって、前記複数のコンピュータのうちの複数台がそれぞれ、潜在的に前記ネットワーク用の指定ネットワーク・ルータの役割を担うように構成され、前記指定ネットワーク・ルータが、その時点のネットワーク構成を判定した後にその時点のネットワーク・トポロジを判定して伝える機能を有し、事前に確立された優先順位基準を使用して、前記役割を担うように前記複数のコンピュータのうち１台を自動選択することができ、前記自動選択がその時点のネットワーク構成に依存しているコンピュータを含むネットワーク。
【請求項１６】
前記役割を担うように構成された前記複数のコンピュータのそれぞれが、
前記ネットワーク上でオンラインになったこと、
前記ネットワーク上の他のどのコンピュータもその時点で前記役割を担っていないことを検知したこと、
自分自身よりも優先順位の高いどのコンピュータもその時点で前記役割を果たしていないことを検知したこと、および
前記ネットワーク上の他のいずれかのコンピュータがその時点で前記役割を果たしていることを検知できないことのうち少なくとも１つに応じて自動的に前記指定ネットワーク・ルータの役割を担う、請求項１５に記載のネットワーク。
【請求項１７】
複数の区画であって、前記事前に確立された優先順位基準によって前記各区画が自動的に指定ネットワーク・ルータを選択することができ、さらに前記事前に確立された優先順位基準によって、前記区画のいずれかが統合されると常に指定ルータを新たに自動選択できる区画をさらに含む、請求項１５に記載のネットワーク。
【請求項１８】
ネットワークを自動的に構成する方法を実施するためのプログラムであって、前記プログラムが、
事前に確立された優先順位基準を使用して指定ネットワーク・ルータを自動的に選択する機能であって、前記指定ネットワーク・ルータが、その時点のネットワーク・トポロジを判定して伝える機能を有する機能をコンピュータに実現させるプログラム。
【請求項１９】
前記指定ネットワーク・ルータの役割を担うように構成された各コンピュータが、
前記ネットワーク上でオンラインになったこと、
前記ネットワーク上の他のどのコンピュータもその時点で前記役割を担っていないことを検知したこと、
自分自身よりも優先順位の高いどのコンピュータもその時点で前記役割を果たしていないことを検知したこと、および
前記ネットワーク上の他のいずれかのコンピュータがその時点で前記役割を果たしていることを検知できないことのうちいずれか１つに応じて自動的に前記指定ネットワーク・ルータの役割を担うようにさせる機能を前記プログラムがさらに含む、請求項１８に記載のプログラム。
【請求項２０】
前記事前に確立された基準が、識別番号に基づいた優先順位の判定を含む、請求項１８に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にコンピュータ・ネットワークの自動構成に関する。より詳細には、事前に確立された基準に基づく優先順位を使用して、ネットワークの１つのルータが、指定ルータの役割を担うように自動的に指定され、その時点のネットワーク構成を判定し、ネットワーク・トポロジを確立し、次いでそのトポロジをその時点でオンラインである全ルータに伝える。
【背景技術】
【０００２】
ネットワーク・ルータは、ネットワーク同士を接続するコンポーネントである。パケットがネットワーク外のステーションに宛てられているときにのみ、ルータはそのパケットを他のネットワークに転送する。遠隔地のネットワークにデータを送信するのに使用するにはどのネットワークが最良のルートかということについて、ルータは知的な判断を下すことができる。
【０００３】
オーバーレイ・ネットワークは、別のネットワークの上部に常駐する「仮想ネットワーク」である。この「仮想ネットワーク」は、オーバーレイ・ルータ（overlay router）が、オーバーレイ・ネットワーク内の宛先、すなわちネットワーク・トポロジと同様に、互いの存在を認識するように構成されなければならない。従来のシステムでは、このネットワーク構成プロセスは手動で行われる。もしも１つのルータがオフラインになったなら、ネットワーク・トポロジが変わってしまうため、オーバーレイ・ネットワークは機能しなくなる可能性がある。
【０００４】
手動構成には、ルータがオンラインになった場合や、オフラインになった場合、あるいはノード間通信リンクの中断によってノード間の相互通信が失われた場合などの状況変化にオーバーレイ・ネットワークが対応できないという欠点がある。
【０００５】
したがって従来技術に欠けているものは、オーバーレイ・ルータ同士が互いの存在を認識し、他のルータがどこにあるのかを認識し、ネットワーク内の宛先へのパスを認識するように、オーバーレイ・ネットワークを自動的に構成する方法である。ネットワークの変化に応じて動的かつ自動的にネットワークを再構成する方法も、従来技術に欠けているものである。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
前述のような従来のシステムの問題、短所、および欠点に鑑みて、オーバーレイ・ネットワークを自動的に構成できる方法（および構造）を提供することが本発明の目的である。より具体的には、本発明は、事前に確立された基準を使用して、その時点でオンラインであるルータの１つが、ネットワーク・トポロジを定義する役割を有する指定ルータの役割を果たすように自動的に選択される方法を教示する。
【０００７】
本発明の別の目的は、万一その時点で指定されているネットワーク・ルータがオフラインになった際にネットワークを自動的に回復できる方法を提供することである。
【０００８】
本発明の別の目的は、オーバーレイ・ネットワークの自動構成の技法を教示することである。この技法では、各ネットワーク・ルータ候補は、オンラインになると、はじめはネットワーク指定ルータの役割を自分自身に課し、そのタスクの実行を続ける。しかしそのルータは、指定ルータの役割を果たす上でさらに優先順位の高い別のルータに出くわすと、自動的にその役割を放棄する。
【課題を解決するための手段】
【０００９】
前述の目的を達成するために、本発明の第１の態様では、複数の相互接続されたコンピュータを含むネットワークを自動的に構成する方法（および構造）が記載されている。複数のコンピュータのうちの複数台が、指定ルータの役割を担うように構成される。指定ルータは、どのコンピュータがその時点でオンラインかを判定することによってその時点のネットワーク構成を判定し、この判定されたその時点のネットワーク構成を使用して、その時点でオンラインである相互接続されたコンピュータ間の隣接関係（neighborhood relationship）を定義するその時点のネットワーク・トポロジを判定し、その時点のネットワーク・トポロジをネットワークに伝える機能を有する。優先順位基準が定義され、この優先順位基準に従って複数のコンピュータのうちの１台が、指定ルータの役割を果たすように自動的に選択される。
【００１０】
本発明の第２の態様では、前述の方法を実施するためにデジタル処理装置によって実行可能な機械可読命令のプログラムを具体化する信号保持媒体（signal-bearing medium）も記載されている。
【００１１】
本発明の第３の態様では、複数のコンピュータを含むネットワークであって、そのコンピュータのうちの複数台が指定ネットワーク・ルータの役割を担うように構成されるネットワークも記載されている。このネットワークは、前述の方法を使用して指定ネットワーク・ルータの役割を果たすように、１つのルータを動的かつ自動的に指定することができる。
【００１２】
本発明の第４の態様では、ネットワーク内で指定ネットワーク・ルータの役割を担うことができるコンピュータにおいて、前記指定ネットワーク・ルータが、その時点のネットワーク・トポロジを判定して伝える機能を有するコンピュータであって、事前に確立された優先順位基準と前記指定ネットワーク・ルータの役割を果たす際に実行するアルゴリズムとを記憶するストレージ・デバイスであって、前記事前に確立された優先順位基準が、前記役割を担うことができる複数の前記コンピュータ間の優先順位を定義するストレージ・デバイスと、前記事前に確立された優先順位基準に基づいて、前記コンピュータがその時点で前記役割を果たす優先順位を有するかどうかを評価する判定モジュールとを含むことができる。
【００１３】
本発明の第５の態様では、前記コンピュータが、前記ネットワーク上でオンラインになるたび、前記ネットワーク上の他のどのコンピュータもその時点で前記役割を担っていないことを検知するたび、自分自身よりも優先順位の高いどのコンピュータもその時点で前記役割を果たしていないことを検知するたび、および前記ネットワーク上の他のいずれかのコンピュータがその時点で前記役割を果たしているかどうかを検知できないたびに、という条件のうち少なくとも１つに応じて自動的に前記役割を担うようにする命令を含む開始モジュール（initiation module）をさらに含むことができる。
【００１４】
本発明の第６の態様では、前記事前に確立された優先順位基準が、その時点でオンラインの相互接続された前記コンピュータの識別番号に基づいて優先順位を定義し、前記判定モジュールが、その時点でオンラインの前記コンピュータが、その時点でオンラインの第２のコンピュータよりも高い優先順位と、その時点でオンラインのすべてのコンピュータに対する最も高い優先順位のうち一方を有するかどうかを評価することができる。
【００１５】
本発明の第７の態様では、ストレージ・デバイス内に記憶されたリストであって、前記役割を担う複数の前記コンピュータのそれぞれの識別番号を含むリストをさらに含むことができる。
【００１６】
本発明の第８の態様では、前記指定ネットワーク・ルータの役割を果たす際に実行する前記アルゴリズムによって、前記コンピュータが前記リスト上の前記識別番号を使用して、前記リスト上の少なくとも１つの他のコンピュータと接触を図り、前記コンピュータが、前記少なくとも１つの他のコンピュータと接触を図るための送信機と、前記少なくとも１つの他のコンピュータから応答を受信するための受信機とをさらに含むことができる。
【００１７】
前述および他の目的、態様、および利点については、図面を参照しながら本発明の好ましい実施形態に関する後述の詳細な説明を読めば、よりよく理解できるであろう。
【発明を実施するための最良の形態】
【００１８】
図面、より具体的には図１を参照すると、ルータＯ１〜Ｏ７および宛先サブネットＳを有する単純化された典型的なオーバーレイ・ネットワークが示されている。ネットワーク（実線）は複数のノードＮを相互接続する。オーバーレイ・ネットワーク（点線）は、オーバーレイ・ルータ・ノードＯｉとして図１に示されているネットワークの特定のノードのみから構成される。ネットワークの宛先、すなわちインターネット・プロバイダ（ＩＰ）のサブネットＳも図に示されている。各サブネットは、関連付けられたホスト／サーバ・コンピュータ（図示せず）を有し、そのホスト／サーバ・コンピュータはオーバーレイ・ネットワークからそのサブネットへの接点となる。
【００１９】
オーバーレイ・ネットワーク用に最大限の柔軟性を提供する本発明の好ましい典型的な実施形態では、各オーバーレイ・ネットワーク・ルータＯｉは、指定ルータの役割を果たすことができるように構成される。指定ルータは、その時点でオンラインである全ルータ間の隣接関係を確立するマッピングであるネットワーク・トポロジを判定し、そのネットワーク・トポロジをこれらのルータに伝える機能を有する。隣接ルータを確立することによって、データ・パケットを経路指定する際の効率を高めることができる。
【００２０】
図１には示されていないが、ネットワークを分割できることにも留意されたい。そのように分割した場合、複数の指定ルータ、すなわちネットワークの切断された部分ごとに指定ルータが存在することになるだろう。
【００２１】
図２に示すように、本発明によるオーバーレイ・ネットワークを自動構成するために、その時点でオンラインであるルータの１つが、その時点のネットワーク構成を判定し、オンライン・ルータ同士が隣接ルータとしてどのような相互関係を持つかを定義するネットワーク・トポロジを作成するルータとして指定されるだろう。この指定ルータは、この隣接関係を残りのルータに伝える。次いでオーバーレイ・ルータは、隣接ルータとの間でルート・プロトコル・メッセージの交換を始める。
【００２２】
図２のステップ２０１では、ネットワークの様々なルータＯｊは、潜在的に指定ルータとして機能するように構成されている。好ましい実施形態では、すべてのルータＯｊがこの可能性を有している。ステップ２０２では、事前に確立された基準２０３を使用して、これらの構成されたルータの１つが、ネットワーク指定ルータとして機能するように指定される。このネットワーク指定ルータは、ステップ２０４でその時点のネットワーク構成を判定する役割を有する。次いでこの判定されたネットワーク構成は、ステップ２０５でその時点のネットワーク・トポロジを判定するために使用され、この判定されたネットワーク・トポロジは、指定ルータによって、ネットワーク内においてその時点でオンラインである全ルータに伝えられる。
【００２３】
ステップ２０６では、もしも指定ルータがオフラインになった場合、事前に確立された基準２０３によって、ネットワーク・トポロジを維持するタスクを引き継ぐためにステップ２０２において別のルータを指定することができる。指定ルータは、オンラインである場合、ステップ２０４においてその時点のネットワーク構成を定期的に再判定し、必要に応じてステップ２０５においてトポロジを更新する。
【００２４】
この自動構成技法が手動構成を上回る利点を有することは明らかである。様々なルータの任意の１つが参画して、ネットワーク・トポロジを確立する役割を担うことができる。その時点のネットワーク・トポロジは、その時点のネットワーク構成に応じて変化することができる。さらにネットワークは、もしもその時点の指定ルータがオフラインになった場合に回復することができる。
【００２５】
図２に示されている技法２００は、様々な方法で実施することができる。実施可能なバリエーションの第１の例として、事前に確立された基準は、たとえばルータＯ１がオンラインになると自動的に指定ルータとなり、次いで別のルータＯ２がその役割を引き継ぎ、順にルータＯ３、Ｏ４、と進む、といった具合にきわめて単純な優先順位システムとすることができる。この単純な優先順位システムを各ルータＯｊの不揮発性メモリにプログラムすることは簡単であり、これによって各ルータは、指定ルータの役割を担う優先順位がどのオンライン・ルータにあるかを理解することができる。各ルータは、オーバーレイ・ネットワークの参加者としてオンラインになる可能性のある全オーバーレイ・ルータのＩＰ（インターネット・プロトコル）アドレスの完全なリストをメモリ内に含む。その時点でオンラインである全ルータは、メモリ内の優先順位リストを参照することによって、どのルータが指定ルータの役割を担うかがわかる。
【００２６】
第２のバリエーションは、指定ルータがその時点のネットワーク構成を判定するプロセス内に存在する。指定ルータは、たとえば単にネットワーク・トラフィックをモニタすることもできる。さらに踏み込んだ手法としては、すべてのオンライン・ルータの存在を識別するために全オンライン・ルータが応答するよう指定ルータがネットワークに要求する手法もある。実施可能な別のバリエーションとしては、各ルータが、オーバーレイ・ネットワークの参加者としてオンラインになる可能性のある全オーバーレイ・ルータのＩＰアドレスの完全なリストをメモリ内に記憶する。指定ルータはこのリストを参照し、各ルータに対して個別に問合せを行うことができる。あるいは、オンラインになる各ルータは、一般的なネットワーク上の表明として、またはメモリ内の優先順位リストに従って参加し指定ルータとして機能すると目される特定のルータに向けられた伝送として、その存在をネットワーク上に表明することができる。
【００２７】
第３のバリエーションは、その時点のネットワーク・トポロジを判定するために指定ルータによって使用されるプロセス内に存在する。基本的に指定ルータは、その時点でどのルータがオンラインかを判定した後、これらのルータ用の隣接関係のマッピングを判定する。前述の１番目の同時係属出願には、最小のスパンニング・ツリーを構築する典型的な好ましい方法が記載されている。しかし本願の目的のためには、ネットワーク・トポロジの判定は、単にメモリ内のリストを参照して、その時点でどのルータがオンラインであるかによって、以前に計算された様々な標準的なトポロジの１つを選択するのと同じくらい単純にすることができることを考慮に入れれば十分である。
【００２８】
図３は、図２に示す一般化された技法の好ましい実施形態２１０を示し、ここではその時点でオンラインのルータ自体が相対的な優先順位の比較に携わり、指定ネットワーク・ルータを選択する結果となる。ステップ２１１において、ルータＡはオンラインになると自動的に指定ルータの役割を担う。ルータＡは、メモリ内に記憶されたネットワーク・ルータ・リスト２１２を参照することによって、他のどのルータが指定ルータとして機能する可能性があるかを知る。したがってステップ２１３において、ルータＡはルータＢへの接触を図る。ステップ２１４において、ルータＡはルータＢに接触することができたら、事前に確立された基準２１５を使用して、ルータＡの優先順位がルータＢよりも高いかどうかをステップ２１６において判定する。ルータＡの優先順位がルータＢよりも高い場合、ルータＡはステップ２１７において指定ルータの役割を担い続ける。ルータＡの優先順位がルータＢよりも高くない場合、ルータＡはステップ２１８において指定ルータの役割を放棄する。任意のルータＡがオンラインになると常に、優先順位を比較するこのプロセスは、事前に確立された基準２１５を最もよく満たすのはどのオンライン・ルータかをすぐさま判定する結果となり、ルータＡは自分自身が指定ルータの役割を担う優先順位をきわめて迅速に判定できることは明らかであろう。
【００２９】
図３に示されている技法２１０には、潜在的に指定ルータとして機能するようにオーバーレイ・ルータを構成するのに使用されるソフトウェア・パッケージのモジュラー部分として指定プロセスを構築できるという利点がある。
【００３０】
図４は、図２および図３によって教示される技法の典型的な実施形態の詳細２２０を示す。指定ルータの選択用に事前に確立された基準とは、その時点でオンラインであり、かつ最小の識別番号を有するルータが指定ルータの役割を担い続けるということである。ステップ２２１に示すように、オーバーレイ・ネットワークの各ルータＯｉはその役割を担うことができるように典型的に構成されており、指定ルータのＩＤがわからない場合は常にその役割を自動的に担う。したがってステップ２２１において、ルータＯｉはオンラインになると常に、自分自身が指定ルータであると自動的に仮定する。各オーバーレイ・ルータＯｉは、他のすべてのオーバーレイ・ルータのＩＰアドレスの完全なリスト２２２を有する。任意の数のよく知られた技法を使用することができるため、ＩＰアドレスをルータに提供するための精密なメカニズムは重要ではない。
【００３１】
最小の識別番号を有する指定ルータとして負った役割において、ルータＯｉはステップ２２３でリスト上の他の各ルータに対するＴＣＰ（伝送制御プロトコル）接続を確立しようと試みる。これらのＴＣＰ接続は、ネットワーク・トポロジを確立するための情報を収集するために使用される。相互通信用には任意の通信方法またはプロトコルを使用できることに留意されたい。したがって、ＴＣＰは信頼性が高いため、接続を確立する好ましい方法であるが、代わりに他のデータ伝送方法を使用することもできる。
【００３２】
図４の好ましい典型的な実施形態では、ルータＯｉは自分自身がその時点でオンラインの最小の番号のルータであると仮定するため、自分自身よりも高位のアドレスを有する各ルータに対してのみＴＣＰ接続を確立しようと試みる。ステップ２２４では、もしもある指定ルータが番号の小さい指定ルータから接続要求を受信すると、番号の大きいルータはその指定ルータとしての責任を放棄し、自分が指定ルータとして確立した可能性のあるすべてのＴＣＰ接続を閉じ、低位のアドレスのルータが指定ルータとしてのその役割を引き継ぐ。
【００３３】
この除外プロセスによって、ステップ２２５に示すように、最も低位のアドレスを有するルータのみが指定ネットワーク・ルータの役割を提供し続ける。他のすべてのオンライン・ルータは自分自身を除外し、初めてオンラインになったいかなるルータもすぐさま指定ルータとして予期していた役割を放棄するか、あるいは新たな指定ルータとなる。
【００３４】
ステップ２２６では、指定ルータがより番号の大きいあるルータに対してＴＣＰ接続を確立できない場合、指定ルータはより番号の大きいそのルータへの接続を確立しようとある所定の間隔を置いて定期的に試みる。指定ルータは、より番号の大きいそのルータへの接続を確立できたら、ネットワーク・トポロジを再計算するステップと、隣接関係を再伝達するステップに進み、これによって以前は到達不能だった番号の大きいルータがオーバーレイ・ネットワークに含まれる。
【００３５】
このプロセスによって、ダウンしていた別のオーバーレイ・ルータが復帰する際にオーバーレイ・ルーティングを適切に適合させることができる。またこのプロセスによって、分割されていたネットワークが接続されるようになる際にオーバーレイ・ルーティングを適切に適合させることもできる。この場合に指定ルータは、指定ルータとしても機能してきた別のオーバーレイ・ルータへの接続を確立することができる。
【００３６】
したがって、ステップ２２８および２２９に示すように、番号の大きい指定ルータが番号の小さい指定ルータから接続要求を受信すると、番号の大きいルータはもはや自分自身が指定ルータであるべきではないと認識し、番号の大きいルータへの接続をすべて閉じる。同様に、指定ルータへの接続を有するルータが番号の小さい指定ルータから接続要求を受信すると、そのルータは番号の大きい指定ルータへの接続を閉じる。
【００３７】
指定ルータは、新たに到達可能となったルータへの接続を確立すると、ネットワーク・トポロジを再計算する前に他の「到達不能な」ルータへの接続を試みることを選択できる。これによって、分割されていたネットワークが接続されるようになる際に、ネットワーク・トポロジを複数回ではなく１回だけ再計算することができる。
【００３８】
各ルータは定期的なキープアライブを指定ルータに送信し、これによって、ステップ２２７において判定されるようにいつ指定ルータが姿を消すかを判定できるようになる。指定ルータが姿を消せば、別のルータが指定ルータの責任を担い、（ステップ２２１に戻ることによって）前述のメカニズムを再開する。
【００３９】
また指定ルータも定期的なキープアライブを送信し、これによって、いつ通常のルータが姿を消すかを把握することができる。実際にルータが姿を消せば、指定ルータは新たなトポロジを計算し、新たな隣接情報を様々なルータに送信する。
【００４０】
前述の実施可能な変形例の１つとしては、最高位のＩＰアドレスを有する指定ルータを選択し、各ルータが、低位のＩＰアドレスを有するルータへのＴＣＰ接続を確立しようと努める形がある。対話する２つのルータが、指定ルータとして想定された役割を両者のうちどちらが放棄すべきかを判定できる限り、またその基準によって、その時点でオンラインであるルータのうち１つだけをその役割用に最終的に選択できる限り、いかなる判定基準も使用可能であるという点にも留意されたい。
【００４１】
最後に、典型的な実施形態で説明されているのは、各ルータは、どれがその時点の指定ルータかを判定できない場合、まずは指定ルータの役割を担い、優先順位の高い別のルータに出くわすと、その役割を放棄するという形態であることに留意されたい。この説明は、実際に各ルータが、その時点でオンラインである全ルータの中で自分の優先順位が最も高いかどうかを常にモニタし、それに応じてその役割を担うということと同じであることは明らかである。
【００４２】
典型的なハードウェアの実装
図５は、本発明を具体化するために（たとえばルータとして）使用できる情報処理／コンピュータ・システム３００の典型的なハードウェア構成を示す。コンピュータ・システム３００はネットワーク・リンケージ３１０を介して他のルータに相互接続することができ、少なくとも１つのプロセッサすなわち中央演算処理装置（ＣＰＵ）３１１を有することが好ましい。
【００４３】
ＣＰＵ３１１はシステム・バス３１２を介して、ランダム・アクセス・メモリ（ＲＡＭ）３１４、読取り専用メモリ（ＲＯＭ）３１６、（ディスク装置３２１および磁気テープ・ドライブ３４０などの周辺装置をバス３１２に接続するための）入出力（Ｉ／Ｏ）アダプタ３１８、（キーボード３２４、マウス３２６、スピーカ３２８、マイクロホン３３２、または他のユーザ・インターフェース装置、あるいはそのすべてをバス３１２に接続するための）ユーザ・インターフェース・アダプタ３２２、情報処理システムをデータ処理ネットワーク、インターネット、イントラネット、パーソナル・エリア・ネットワーク（ＰＡＮ）などに接続するための通信アダプタ３３４、ならびにバス３１２をディスプレイ装置３３８またはプリンタ３３９（たとえばデジタル・プリンタなど）あるいはその両方に接続するためのディスプレイ・アダプタ３３６と相互接続される。
【００４４】
前述のハードウェア／ソフトウェア環境に加えて、本発明の別の態様は、前述の方法を実施するための、コンピュータで実施する方法を含む。例として、この方法は前述の特定の環境において実施することができる。
【００４５】
このような方法は、たとえばコンピュータを操作して、デジタル・データ処理装置によって具体化されるように、一連の機械可読命令を実行することによって実施することができる。これらの命令は、様々なタイプの信号保持媒体内に常駐することができる。
【００４６】
したがって本発明のこの態様は、本発明の方法を実施するために前述のＣＰＵ３１１およびハードウェアを組み込んだデジタル・データ・プロセッサによって実行可能な機械可読命令のプログラムを具体化する信号保持媒体を含むプログラム製品を対象としている。
【００４７】
たとえばこの信号保持媒体が、たとえばＣＰＵ３１１に接続されたＲＡＭを含むこともできる。あるいはこれらの命令を、ＣＰＵ３１１が直接または間接的にアクセス可能な、磁気データ・ストレージ・ディスケット４００（図６）などの別の信号保持媒体内に含むこともできる。
【００４８】
あるいはこれらの命令を、ＤＡＳＤストレージ（たとえば従来の「ハード・ディスク」またはＲＡＩＤアレイ）、磁気テープ、読取り専用メモリ（たとえばＲＯＭ、ＥＰＲＯＭ、またはＥＥＰＲＯＭ）、光ディスク記憶装置（たとえばＣＤ−ＲＯＭ、ＷＯＲＭ、ＤＶＤ、デジタル光学式テープなど）、紙の「パンチ」・カード、あるいはデジタル通信リンクおよびアナログ通信リンクならびに無線などの伝送媒体を含むその他の適切な信号保持媒体など、様々な機械可読データ記憶媒体上に記憶することもできる。本発明の例示的な実施形態では、この機械可読命令はソフトウェア・オブジェクト・コードを含むことができる。本発明の命令は、ルータ上のネットワーク・インターフェースを介して様々なネットワーク・ルータにダウンロードすることもできるはずである。
【００４９】
本発明はあらゆる種類のネットワーク設計に当てはまり、ルーティング・プロトコルによって使用できることに留意されたい。本発明の応用例は、具体的な技術に応じてきわめて多様である。非限定的な応用例としては、マルチキャスト・テレビ会議（multicast-video conferencing）、コラボレーティブ・アプリケーション（collaborativeapplication）、マルチパーティー・ゲーム（multiparty game）、およびコンテンツ配信などを挙げることができる。
【００５０】
本発明の主な利点は、ネットワークを手動で構成する必要がなくなることである。手動構成は労働集約的であり、エラーが生じやすい。手動で構成されたネットワークにおいてリンクに障害が起きた場合、追加の手動構成が必要となり、言うまでもなくこのようなネットワークは作動不能になるおそれがある。
【００５１】
単一の好ましい実施形態を用いて本発明について説明してきたが、添付した特許請求の範囲の趣旨および範囲から逸脱することなく修正を加えて本発明を実施できることを当業者なら認識するであろう。
【図面の簡単な説明】
【００５２】
【図１】単純化された典型的なオーバーレイ・ネットワークを示す図である。
【図２】本発明の基本技術２００を示すフローチャートである。
【図３】２つのオンライン・ルータ間の優先順位を判定することによって選択が向上する典型的な実施形態２１０を示すフローチャートである。
【図４】その時点でオンラインである最も番号の小さいルータを自動的に指定する典型的な実施形態２２０を示すフローチャートである。
【図５】本発明を内部に組み込むための典型的なハードウェア／情報処理システム３００を示す図である。
【図６】本発明による方法のプログラムのステップを記憶するための信号保持媒体４００（たとえばストレージ・メディア）を示す図である。
【図１】
2005531199.tif 000003
【図２】
2005531199.tif 000004
【図３】
2005531199.tif 000005
【図４】
2005531199.tif 000006
【図５】
2005531199.tif 000007
【図６】
2005531199.tif 000008
【国際調査報告】
2005531199.tif 000009