(57)【特許請求の範囲】
【請求項１】
メッセージ生成／受信デバイスとスイッチングノードを含む複数のネットワークエンティティを備えたネットワークであって、該スイッチングノードは、メッセージ生成／受信デバイスが相互間で情報を転送できるようにメッセージ生成／受信デバイスを相互接続するように構成されたネットワークにおいて、
Ａ．各前記ネットワークエンティティは、各該エンティティに向けられた識別要求メッセージを受信すると該識別要求メッセージに応答して、自分がそのエンティティであることを示すエンティティ識別情報とそのエンティティが該識別要求メッセージを受信した経路を示している受信経路情報とを含む識別応答メッセージを生成し、該識別応答メッセージをその経路上に送信するように構成されており、
Ｂ．少なくとも１つの前記メッセージ生成／受信デバイスは、
前記ネットワーク内の相互接続トポロジを表しているネットワークトポロジ情報を格納しておくためのネットワークトポロジデータベースと、
前記ネットワークトポロジデータベース用に前記ネットワーク相互接続トポロジ情報を判断するように構成され、一連の繰り返しで動作し、各繰り返しにおいて、前記識別要求メッセージの中で定義された経路の終端にあるネットワークエンティティが前記ネットワーク内に存在するかどうかを判断するために、当該メッセージ生成／受信デバイスが前記ネットワーク内の経路上に前記識別要求メッセージを送信することを可能にし、該識別要求メッセージに応答する前記識別応答メッセージを受信すると、該識別応答メッセージから前記エンティティ識別子と前記受信経路情報を取得し、該取得したエンティティ識別子と受信経路情報を前記ネットワークトポロジデータベースに追加するように構成されているネットワークトポロジ判断プロセッサと、
前記ネットワークトポロジデータベース内の前記ネットワークトポロジ情報を使用して、適切な経路を決定し、かつ前記スイッチングノードの少なくとも１つに格納するための該適切な経路に関連するルーティング情報を生成し、該ルーティング情報を前記スイッチングノードへ送信するように構成されているルーティング情報ジェネレータと
を含むことを特徴とするネットワーク。
【請求項２】
請求項１に記載のネットワークにおいて、前記少なくとも１つのメッセージ生成／受信デバイスは、あるネットワークエンティティから識別応答メッセージを受信した後で、当該ネットワークエンティティに関して設定（configuration）オペレーションを選択的に開始するように構成されたスイッチングノード設定（configuration）プロセッサを更に含んでいることを特徴とするネットワーク。
【請求項３】
請求項２に記載のネットワークにおいて、前記スイッチングノード設定プロセッサは、前記ネットワークエンティティが前記スイッチングノードであるときに、そのネットワークエンティティに関して前記設定オペレーションを開始することを特徴とするネットワーク。
【請求項４】
請求項３に記載のネットワークにおいて、前記スイッチングノード設定プロセッサは、最初にロッキングオペレーションを実行して前記スイッチングノードをロックしようと試みるように構成されていることを特徴とするネットワーク。
【請求項５】
請求項１に記載のネットワークにおいて、
各前記スイッチングノードは、
（ｉ）それぞれのスイッチングノードを通って、あるメッセージ生成／受信デバイスから別のメッセージ生成／受信デバイスに通じるネットワークの経路の少なくとも一部を示している経路情報を収めておくためのルーティングテーブルであって、前記メッセージ生成／受信デバイスに送信されるメッセージが、スイッチングノードに接続されている通信リンクのどの通信リンク上に送信されるかを、各々のメッセージ生成／受信デバイスごとに、示しているルーティングテーブルと、
（ｉｉ）前記メッセージを受信し、前記ルーティングテーブルに入っている前記経路情報を使用して、前記メッセージの各々が前記通信リンクのどの通信リンク上に転送されるかを割り出すメッセージ転送部とを含むことを特徴とするネットワーク。
【発明の詳細な説明】
【０００１】
（発明の分野）
本発明は、一般的にはデジタル通信システムの分野に関し、さらに具体的には、例えば、デジタル画像、オーディオおよびビデオ配信システムとデジタルコンピュータシステム相互間のでデジタルデータ通信を容易化するデジタルネットワークに関する。さらに具体的には、本発明は、デジタル通信ネットワークのための分散スイッチと接続制御構成と方法を提供する。
【０００２】
（発明の背景）
データとプログラムを含む情報を、デジタルコンピュータシステムや他のデジタルデバイス相互間で転送することを容易化するデジタルネットワークはすでに開発されている。種々タイプのネットワークは、種々の情報転送技法を使用して開発され、構築されている。周知のEthernet（イーサネット）などの、いくつかのネットワークでは、ネットワークに接続されたデバイスのすべてを相互接続するためにシングルワイヤ（単線）が使用されている。この方法によると、施設内のネットワークの配線が単純化され、デバイスをネットワークに接続することが単純化されるが、ワイヤはメッセージ形態の情報を、一度に１つのデバイスからしか伝達できないために情報転送が全体的に低速になっている。この点をある程度解消するために、いくつかのEthernet設置施設では、ネットワークはいくつかのサブネットワークに分割され、各サブネットワークが別々のワイヤをもち、これらのワイヤはインタフェースで相互に接続されている。このような施設では、ワイヤはそこに接続されたデバイスに対してメッセージを同時に伝達できるために、同時に転送できるメッセージの数が増加している。２またはそれ以上のサブネットワーク内のワイヤが使用されるのは、あるワイヤに接続されたデバイスが別のワイヤに接続されたデバイスにメッセージを送信する必要があるときだけであるので、ワイヤに接続された他のデバイスはサブネットワークを利用できないようになっている。
【０００３】
この点をさらに緩和するために、網目状のスイッチングノードを通して通信が処理されるようにしたネットワークが開発されている。コンピュータシステムと他のデバイスは種々のスイッチングノードに接続されている。スイッチングノード自体はさまざまなパターンで相互接続されているために、デバイスのペア間で多数の経路 (path) が利用できるので、ある経路が混雑しているとき、別の経路が使用できるようになっている。このような構成では、ネットワークはEthernetネットワークよりも複雑化するが、特に、スイッチングノードとデバイスを相互接続する媒体として光ファイバが使用される場合には、情報転送速度を大幅に高速化することを可能にしている。この種のネットワーク（つまり、網目状のスイッチングノードを通して通信が処理されるネットワーク）については、次のような問題が生じている。その問題とは、あるデバイスが情報を別のデバイスに転送しようとするとき、ネットワークを構成するスイッチングノードを通る経路、望ましくは最適経路、を識別し、その経路上を情報が転送できるようにすることである。代表的なネットワークでは、スイッチングノードは、ネットワークを構成するスイッチングノードの網状機構のトポロジを判断するための機能を備えており、これらは（つまり、スイッチングノード）は、周知のOSPF (open shortest-path first) アルゴリズムなどの、経路判断アルゴリズムを使用して最適経路を判断できるようになっている。一般的に、このようなネットワークでは、各スイッチングノードはネットワークトポロジデータベース(network topology database)（「リンクステート（リンク状態）データベース(link state database)」とも呼ばれている）を設定し、ネットワークトポロジを定義している情報をそのデータベースに格納している。ネットワークが障害に強く(failure-free)、スタチック（静的）であるとすれば、各スイッチングノードのネットワークトポロジは、ネットワークアドミニストレータ（ネットワーク管理者）によって先験的に設定することが可能である。しかし、一般的に、望ましいことはネットワークのトポロジをダイナミック（動的）にすることであり、このようなネットワークでは、各スイッチングノードは、自身であることの識別と、そのスイッチングノードと他のスイッチングノードまたはデバイスとの接続を特定するリンクステート（リンク状態）広告メッセージ(link state advertising message) を定期的に生成し、そのメッセージをネットワーク中に洪水のように伝達（flood）している。各スイッチングノードはリンクステート広告メッセージを受信すると、その受信側スイッチングノードは、リンクステート広告メッセージからの情報で自身のネットワークトポロジデータベースを更新している。
【０００４】
このようなネットワークに関してはいくつかの問題が起こっている。第一の問題は、リンクステート広告メッセージはネットワークの帯域幅を占有するため、デバイス間で情報メッセージを送信するために使用できるはずの帯域幅の量を減少していることである。さらに、もっと一般的には、ネットワークを通る経路をスイッチングノードに判断させ、かかる経路の判断を可能にするために必要なネットワークトポロジデータベースをスイッチングノードに維持させるためには、スイッチングノードに相当量の処理能力と情報記憶能力をもたせる必要があり、このことはスイッチングノードのコストを大幅に増加させることになっている。
【０００５】
（発明の概要）
本発明は、デジタル通信ネットワークのための、新規で改良された分散スイッチ(distributed switch)と接続制御構成(connection control arrangement)および方法を提供する。
【０００６】
要約して簡単に説明すると、一形態によれば、本発明はコンピュータや類似デバイスのように、スイッチングノード（交換ノード）によって相互接続されたデバイスを含んでいるネットワークを提供する。これらのデバイスの少なくとも一部はネットワークのトポロジ（幾何学的な接続形態）を判断するように構成されている。ネットワークのトポロジを判断する際、デバイスは一連の繰り返し(iterations)で動作し、各繰り返しにおいて、要求メッセージを経路上に送信し、追加のエンティティ（構成要素）がネットワークに存在するかどうかを判断するようにしている。追加のエンティティが要求メッセージの中で定義された経路の終端に存在していれば、そのエンティティは応答を生成し、この応答を上記デバイスに送り返す。そのデバイスは、その応答を受信すると、そのエンティティに関する情報を、そのデバイスがネットワークのトポロジを定義するために維持しているネットワークトポロジデータベースに追加する。
【０００７】
別の形態では、本発明が提供するネットワークでは、上述したように、デバイスの少なくとも一部がネットワーク内に追加のスイッチングノードを見つけると、そのスイッチングノードを構成に含めることを試みるようにしている。このオペレーションでは、デバイスはロッキングプロトコル (locking protocol) に従ってスイッチングノードとやりとりして、１つのデバイスだけが各スイッチングノードを構成に含めることを試みるのを保証している。
【０００８】
さらに別の形態では、各デバイスは、ネットワークトポロジを判断したあとで、別のデバイスとの間で情報を転送する必要が起こったとき、そのネットワークトポロジデータベース内のネットワークトポロジ情報を使用して、適切なルートを判断できるようになっている。適切なルートを判断したあと、デバイスはルーティング情報 (routing information) をスイッチングノードにロードし、スイッチングノードが、相互間で転送される情報を収めているメッセージを転送できるようにしている。
【０００９】
（実施形態の詳細説明）
図１は、データを表す信号を多数のデバイスの間で転送するための複数のスイッチングノード１１(1)乃至１１(N)（参照番号１１(n)で総称する）を含んでいるコンピュータネットワーク１０を示す概略図であり、図１に示すように、デバイスはコンピュータ１２(1) 乃至１２(M)（参照番号１２(m) で総称する）で表されている。コンピュータ１２(m) は、従来と同じように、プログラム命令に従ってデータを処理し、処理済みデータを生成する。この処理の際、コンピュータ１２(mS)（下付き文字の''Ｓ''は「ソース（送り元）」を表している）は、ソースコンピュータであるときは、データ、処理済みデータおよび／またはプログラム命令（以下では、これらは「情報」と総称することにする）を、別のデスティネーションコンピュータ１２(mD)（下付き文字の''D''は「デスティネーション（宛先）」を表している）に転送する必要が起こることがあり、また、デスティネーションコンピュータは転送されてきた情報をそのオペレーションで使用する必要が起こることがある。各コンピュータ１２(m) は、全体を参照番号１３(p) で示している通信リンクを介してスイッチングノード１１(n) に接続され、スイッチングノードとの間のデータの送受信を容易化している。スイッチングノード１１(n) はコンピュータ１２(ｍ) からや、他のスイッチングノード１１(n) から送られてきたデータを受信し、受信したデータをバッファに書き込み、転送することによって、コンピュータ１２(m) 間のデータ転送を容易化している。スイッチングノード１１(n) は、これも全体を参照番号１３(p) で示している通信リンクにより相互接続され、そのスイッチノード間のデータ転送を容易化している。通信リンク１３(p) は、都合の良いものであれば、どのデータ伝送媒体でも利用することが可能である。図１に示す各通信リンク１３(p) は双方向であることが好ましく、そのようにすると、スイッチングノード１１(n) はノード相互間で、および同一リンクを利用してそのノードに接続されたコンピュータ１２(m) との間で信号を送受信することができる。この双方向通信リンクを取り入れるために、通信リンク１３(p) ごとに別の媒体を設ければ、各通信リンクは信号を単方向に転送することが可能になる。
【００１０】
一実施形態では、データは周知の "ATM"（"Asynchronous Transfer Mode"：非同期転送モード）転送技法を使用して転送される。この技法は、C. Partridge著「ギガビットネットワーキング(Gigabit Networking)」（Reading MA: Addison Wesley Publishing Company, 1994）の主に第３章と第４章、およびD. McDysan他著「ATMの理論と応用(ATM Theory and Application)」(McGraw Hill, 1995) に詳しく説明されているので、この技法はここで詳しく説明することは省略する。一般的に、ATM技法では、コンピュータ１２(m) とスイッチングノード１１(n) は、ネットワークを介してコンピュータ１２(m)間に確立された「仮想回線(virtual circuit)」によってデータを固定長「セル(cell)」の形で伝送している。各仮想回線は、基本的に、ソースコンピュータ１２(mS) からデスティネーションコンピュータ１２(mD) への経路を、１つまたは２つ以上のスイッチングノード１１(n) を通って、それぞれの通信リンク１３(p) を利用するように定義している。ATMデータ転送技法では、ある情報ブロックがソースコンピュータ１２(mS) からデスティネーションコンピュータ１２(mD) あてに、その間に確立された仮想回線を利用して転送されるとき、ソースコンピュータ１２(mS) はそのデータブロックを１つまたは一連の「セル」に割り当てて、通信リンク１３(p) 上をシリアルに伝送するようにする。ネットワーク１０を通して転送される各セルはヘッダ部分とデータ部分を含み、ヘッダ部分は、ネットワーク１０を通るセルの転送を制御するための仮想回線識別情報のほかに、プロトコルおよび他の制御情報（「メッセージ終わり(end of message  EOM)」フラッグなど）も収めている。データ部分は、セルに入って転送されるデータブロックのデータを収めている。各セルのデータ部分はあらかじめ決めた固定長になっており、一実施形態では、48バイトになっている。ソースコンピュータ１２(mS) はデータをセルのデータ部分に埋め込むか（転送されるデータブロックが１つのセルに収容される場合）、あるいはブロックに含まれるデータ量が各セルのデータ部分のサイズの整数倍になっていないときは、データを一連のセルの最終セルに埋め込むことによって（転送されるデータブロックを収容するために複数のセルが必要な場合）、最終セルのデータ部分が必要とする長さになるようにしている。データブロックを転送するために一連のセルが必要なときは、ソースコンピュータ１２(m) は、一連のセルのデータ部分のデータが転送されるデータブロック内のデータの順序に一致するようにセルを送信する。さらに、これらのセルがデスティネーションコンピュータ１２(mD) に正しく転送されると、デスティネーションコンピュータはセルを同じ順序で受信することになる。一連のセルの中で、データブロックからの情報を収めている最終セルでは、ヘッダ部分のメッセージ終わりフラグがセットされるので、データブロックのデータを収めているセルのすべてを受信したことがデスティネーションコンピュータ１２(mD) に通知される。
【００１１】
本発明が提供する構成によれば、スイッチングノード１１(n)ではなく、コンピュータ１２(m) がネットワークのトポロジを効率的に判断し、そのトポロジを使用してスイッチングノードを通る仮想回線の確立を容易化し、その仮想回線を使用してネットワークを通過するメッセージの転送を可能にしている。一般的に、本発明によるオペレーションは２つの一般的フェーズ（段階）で進められる。第１フェーズは、全体的には、ネットワークトポロジ発見・スイッチングノード設定フェーズ (network topology discovery and switching node configuration phase) で表されているが、このフェーズでは、コンピュータ１２(m) の各々は、他のコンピュータから独立して、ネットワークトポロジ発見 (network topology discovery) オペレーションを実行し、ネットワークのトポロジ、つまり、ネットワークを構成するスイッチングノード群、スイッチングノード１１(n) を相互接続している通信リンク１３(p) のパターン、およびスイッチングノードとコンピュータ１２(m) のそれぞれの間を相互接続している通信リンクのパターンを識別するようにしている。各コンピュータ１２(m) はネットワークのトポロジを判断すると、そのコンピュータはネットワークトポロジデータベースの設定と更新を行うが、このデータベースは第２フェーズ期間に使用される。さらに、第１フェーズ期間に、コンピュータ１２(m) の１つまたは複数はあらかじめ決めた設定 (configuration) オペレーションを実行し、スイッチングノード１１(n) を設定に含めるようにする。
【００１２】
各コンピュータ１２(m)はそれぞれ、複数の繰り返しで再帰的にネットワークトポロジを判断する。第１の繰り返しでは、コンピュータ１２(m1)（これはコンピュータ１２(m) の１つを構成している）は、そこに接続された通信リンク１３(p1) 上に識別要求メッセージを送信する。コンピュータ１２(m1)がその識別要求メッセージに対する応答を受信しないときには、そのコンピュータがネットワークに接続されていないか、あるいはネットワークに接続された動作可能なデバイス、つまり、スイッチングノード１１(n) もコンピュータ１２（ｍ’）も存在しない。他方、識別要求メッセージに対する応答があったときは、その応答には応答したデバイスの識別子（ID） が含まれている。応答側デバイスがスイッチングノード１１(n1) であれば、その応答には、識別要求メッセージがそこを通って受信された通信リンクに接続されている複数のポートの中の１つも示されており（これについては下述する）、そのポートとは、応答がそこから送信されたポートのことである。コンピュータ１２(m1) はこの情報を自分のネットワークトポロジデータベースに追加する。
【００１３】
そのあと、コンピュータ１２(m1) は第２の繰り返しを開始し、その繰り返しでは、最初の繰り返しで識別要求メッセージを受信したスイッチングノードに接続されているスイッチングノード（単数または複数）および／またはコンピュータ（単数または複数）のID を判定する。この繰り返しでは、コンピュータ１２(m1) は、複数の二次（副）繰り返し (sub-iteration) において、識別要求メッセージを生成し、このメッセージをスイッチングノード１１(n1) に送信する。各二次繰り返しでは、この識別要求メッセージはスイッチングノード１１(n1) と他のポートの１つ（つまり、ポートの中でコンピュータ１２(m1) に接続された通信リンク１３(p1) に接続されていないポートの１つ）を特定（identify）している。スイッチングノード１１(n1) は識別要求メッセージを受信すると、特定されたポート(identified  port)からそのメッセージを送信する。デバイスがこの識別要求メッセージに応答したときは、第１の繰り返しと同じように、その応答には応答側デバイスのIDと、応答側デバイスがスイッチングノード１１(n2) であれば、識別要求メッセージがそこから受信されたスイッチングノード１１(n2) のポートが含まれている。他方、スイッチングノード１１(n1) は、受信したメッセージがあれば、それをコンピュータ１２(m1) に転送する。各応答から、コンピュータ１２(m1) は応答側デバイスのIDと、識別要求メッセージがそこから伝送されたスイッチングノード１１(n1)のポートと、応答側デバイスがスイッチングノード１１(n2) であれば、識別要求メッセージがそこからスイッチングノード１１(n2) によって受信されたスイッチングノード１１(n2) のポートのIDとを判定することができ、コンピュータ１２(m1) は、これらのすべてを自身のネットワークトポロジデータベースに追加する。スイッチングノード１１(n1) の特定ポートに向けられた識別要求メッセージに対する応答をコンピュータ１２(m1) が受信しないときには、そのコンピュータ（つまり、コンピュータ１２(m1)）はこのような情報をネットワークトポロジデータベースに追加する必要がない。コンピュータ１２(m1) は一連の繰り返し、二次繰り返し、三次繰り返し(sub-sub-iterations)、以下同様を通してこれらのオペレーションを続行することができ、その場合、各識別要求メッセージには、スイッチングノード１１(n1)、１１(n2)、. . . がシーケンス（一連）になって含まれていると共に、それぞれの識別要求メッセージを送信する際に使用されるそれぞれのポートが含まれており、これらの繰り返しは、コンピュータ１２(m1)が送信した識別要求メッセージに対する応答が受信されなくなるまで続けられる。
【００１４】
コンピュータ１２(m) の各々は上述したオペレーションを実行して、ネットワークトポロジ情報を取得することができる。一般的に、コンピュータ１２(m) とスイッチングノード１１(n) のすべてが、そのオペレーションの実行時に電源が入っていて、動作状態になっていれば、コンピュータ１２(m) の各々は、上述したオペレーションを実行することによってネットワーク全体のネットワークトポロジ情報を取得することができる。しかし、他のコンピュータ１２（ｍ’）がネットワークトポロジ発見・スイッチングノード構成フェーズを実行しようとするときに、例えば、１つまたは２つ以上のコンピュータ１２(m) に電源が入っていなければ、そのコンピュータ１２(m) はコンピュータ１２（ｍ’）から出された識別要求メッセージに応答できないので、その場合には、それがどのコンピュータ１２(m) であるかがコンピュータ１２（ｍ’）のネットワークトポロジデータベースに示されないことになる。しかし、当然に理解されるように、それらコンピュータ１２(m) が以後に動作状態になったとき、それぞれのネットワークトポロジ発見・スイッチングノード構成フェーズを実行することになるので、結局そのプロセスのときに識別要求メッセージを生成し、それがコンピュータ１２（ｍ’）に転送されることになる。従って、自分のネットワークトポロジデータベースにどのコンピュータであるかが特定されていないコンピュータから識別要求メッセージをコンピュータ１２（ｍ’）が受信したときは、そのコンピュータ（つまり、コンピュータ１２（ｍ’））は、コンピュータ１２(m) が接続されているネットワークの、少なくともある部分に関して上述のオペレーションを繰り返すことにより、自分のネットワークトポロジデータベース用の自分のためのネットワークトポロジ情報を取得することができる。
【００１５】
以下では、ネットワークトポロジ発見オペレーション期間にコンピュータ１２(m) とスイッチングノード１１(n) によって実行されるオペレーションの理解を容易にするために、具体的な例を示して説明することにする。この例では、各スイッチングノード１１(n) が最大P個のポートをもつものと想定されているが、当然に理解されるように、コンピュータ１２(m) と別のスイッチングノート１１（ｎ’）のどちらにも、すべてのポートが接続されていなくてもよいことは勿論である。この例では、ネットワークトポロジ発見オペレーションに関連してコンピュータ１２(1) によって実行されるオペレーションが説明する。従って、第１繰り返し期間には、コンピュータ１２(1) は識別要求メッセージを生成し、そのメッセージをこのコンピュータに接続された通信リンク１３(1) 上に送信する。スイッチングノード１１(1) に電源が入っていれば、そのスイッチングノードはこの識別要求メッセージを受信し、自身であることと、識別要求メッセージがそこから受信されたポートとを示している識別応答メッセージを生成する。スイッチングノート１１(1) のID（識別子）が、例えば、SN1であり、スイッチングノード１１(1) がそこから識別要求メッセージを受信したポートが、例えば、P1であれば、スイッチングノード１１(1) から与えられる識別応答メッセージはトポロジ情報<P1,SN1> を含んでいるので、識別要求メッセージが、SN1のIDをもつスイッチングノードによってポートP1から受信されたということが分かる。識別応答メッセージを生成したあと、スイッチングノード１１(1) はそのメッセージを同一ポートP1から送出し、コンピュータ１２(1) に送信されることなる。他方、コンピュータ１２(1) は、その識別応答メッセージからトポロジ情報<P1,SN1> を取得し、それを自分のネットワークトポロジデータベースに格納しておく。以上から理解されるように、このトポロジ情報は、コンピュータ１２(m) がSN1のIDをもつスイッチングノードにポートP1を通して接続されていることを示している。
【００１６】
そのあと、第２繰り返し期間に、コンピュータ１２(1) は、スイッチングノード１１(1) の他のポートP2, . . . , PPに接続されているデバイス（つまり、スイッチングノード１１(n) および／またはコンピュータ１２(m)）のIDを取得することを試みる。この繰り返しでは、コンピュータ１２(1) は、情報<P1,SN1,P2> を収めている識別要求メッセージを初期に生成し、そこに接続されている通信リンク１３(1) 上にそのメッセージを送信する。スイッチングノード１１(1) はその識別要求メッセージを受信するが、このメッセージはそのIDであるSN1を収めているので、スイッチングノードはメッセージをポートP2から転送する。ポートP3が通信リンク１３(8) に接続されていれば、識別要求メッセージはスイッチングノード１１(6) に送信されることになる。スイッチングノード１１(6) に電源が入っていれば、そのスイッチングノードは識別要求メッセージを受信し、識別応答メッセージを生成する。このメッセージには、自身であることと、識別要求メッセージがそこから受信されたポートとがIDで示されている。スイッチングノード１１(6) のIDが、例えば、SN6であれば、スイッチングノード１１(6) から与えられる識別応答メッセージには、<P1,SN1,P2|P3,SN6> という情報が入っているが、これは、基本的に、そのトポロジ情報P3,SN6を、スイッチングノード１１(1) から送られてきた識別要求メッセージに入っている情報P1,SN1,P2に付加したものである。識別応答メッセージを生成したあと、スイッチングノード１１(6) は、識別要求メッセージがそこから受信されたポートP3からその識別応答メッセージを転送することにより、それをスイッチングノード１１(1) に転送する。スイッチングノード１１(1) はその識別応答メッセージを受信すると、そのメッセージをポートP1から転送し、それをコンピュータ１２(1) に転送する。コンピュータ１２(1) は識別応答メッセージを受信すると、その識別応答メッセージからネットワークトポロジ情報P1,SN1,P2|P3,SN6を取得し、それを自分のネットワークトポロジデータベースに格納しておく。以上から理解されるように、このネットワークトポロジ情報は、順番に、コンピュータ１２(1)に接続されたSN1のIDをもつスイッチングノードが、ポートP2を通してSN6のIDをもつスイッチングノードに接続されていることと、SN6のIDをもつスイッチングノードが、ポートP3を通してSN1のIDをもつスイッチングノードに接続されていることを示している。
【００１７】
そのあと、さらに第２の繰り返しで、コンピュータ１２(1) は情報<P1,SN1,P3> を収めている識別要求メッセージを生成し、そのメッセージをこのコンピュータに接続されている通信リンク１３(1) 上に送信する。スイッチングノード１１(1) はこの識別要求メッセージを受信するが、そのメッセージはそのID であるSN1を収めているので、このスイッチングノードはそのメッセージをポートP3から転送する。ポートP3が通信リンク１３(9) に接続されていれば、識別要求メッセージはスイッチングノード１１(3) に送信される。スイッチングノード１１(3) に電源が入っていれば、このスイッチングノードは識別要求メッセージを受信し、自身であることと、識別要求メッセージがそこから受信されたポートを示している識別応答メッセージを生成する。スイッチングノード１１(3) のIDが、例えば、SN3であり、スイッチングノード１１(3) がそこから識別要求メッセージを受信したポートが、例えば、P8であれば、スイッチングノード１１(3) から与えられる識別応答メッセージには、<P1,SN1,P3|P8,SN3> という情報が入っているが、これは、基本的に、そのトポロジ情報P8,SN3を、スイッチングノード１１(1) から送られてきた識別要求メッセージに入っている情報P1,SN1,P3に付加したものである。識別応答メッセージを生成したあと、スイッチングノード１１(3) は識別要求メッセージがそこから受信されたポートP8からその識別応答メッセージを転送することにより、それをスイッチングノード１１(1) に転送する。スイッチングノード１１(1) はこの識別応答メッセージを受信すると、そのメッセージをポートP1から転送することにより、それをコンピュータ１２(1) に転送する。コンピュータ１２(1) は識別応答メッセージを受信すると、その識別応答情報からネットワークトポロジ情報P1,SN1,P3|P8,SN3を取得し、それを自分のネットワークトポロジデータベースに格納しておく。以上から理解されるように、このネットワークトポロジ情報は、SN1のIDをもち、コンピュータに接続されているスイッチングノード１１(1) が、順番に、ポートP3を通してSN3のIDをもつスイッチングノードに接続されていることと、SN3のIDをもつスイッチングノードがポートP8を通してSN1のIDをもつスイッチングノードに接続されていることを示している。
【００１８】
そのあと、さらに第２繰り返しでは、コンピュータ１２(1) は<P1,SN1,P4> という情報を収めている識別要求メッセージを生成し、このコンピュータに接続された通信リンク１３(1) 上にそのメッセージを送信する。スイッチングノード１１(1) はこの識別要求メッセージを受信するが、そのメッセージにはそのID であるSN1が収められているので、メッセージをポートP4から転送する。ポートP4が通信リンク１３(10) に接続されていれば、識別要求メッセージはスイッチングノード１１(2) に送信される。このスイッチングノード１１(2) に電源が入っていれば、識別要求メッセージを受信し、自身であることと、識別要求メッセージがそこから受信されたポートを示している識別応答メッセージを生成する。スイッチングノード１１(2) のIDが、例えば、SN2であり、スイッチングノード１１(2) がそこから識別要求メッセージを受信したポートが、例えば、P6であれば、スイッチングノード１１(2) から与えられる識別応答メッセージには、<P1,SN1,P4|P6,SN2> という情報が入っており、これは、基本的には、スイッチングノード１１(1) から送られてきた識別要求メッセージに入っていた情報P1,SN１,P4にそのトポロジ情報P6,SN2を付加したものである。識別応答メッセージを生成したあと、スイッチングノード１１(2) は、識別要求メッセージがそこから受信されたポートP6からその識別応答メッセージを転送することにより、それをスイッチングノード１１(1) に転送する。スイッチングノード１１(1) はその識別応答メッセージを受信すると、それをポートP1から転送することにより、それをコンピュータ１２(1) に転送する。コンピュータ１２(1) は識別応答メッセージを受信すると、その識別応答メッセージからネットワークトポロジ情報P1,SN1,P4|P6,SN2を取得し、それを自分のネットワークトポロジデータベースに格納しておく。以上から理解されるように、このネットワークトポロジ情報は、順番に、SN1のIDをもち、コンピュータ１１(1) に接続されているスイッチングノードが、SN2のIDをもつスイッチングノードにポートP4を通して接続されていることと、SN2のIDをもつスイッチングノードが、SN1のIDをもつスイッチングノードにポートP６を通して接続されていることを示している。
【００１９】
そのあと、さらに第２繰り返しでは、コンピュータ１２(1) は、それぞれの情報アイテム<P1,SN1,P5>, . . . ,<P1,SN1,PP> を収めている識別要求メッセージを生成し、そこに接続された通信リンク１３(1) 上にそのメッセージを送信することを続ける。スイッチングノード１１(1) はこれらの識別要求メッセージを受信したあと、それぞれのポートP5, . . . ,PPからこれらの識別要求メッセージを送信することを試みる。しかし、これらのポートはコンピュータ１２(m) にも、スイッチングノード１１(n) にも接続されていないので、コンピュータ１２(1) はそのメッセージに対する応答メッセージを受信しない。この識別要求メッセージの各々が送信されたあとに続く、それぞれのタイムアウト期間が経過すると、コンピュータ１２(1) はそれぞれのポートP5, . . . PPが接続されていないと判断し、その情報を自分のネットワークトポロジデータベースに入れておくことができる。
【００２０】
スイッチングノード１２(1) の最終ポートPPで識別要求メッセージに関連するオペレーションが終了すると、コンピュータ１２(1) は第３繰り返しを開始する。第３繰り返しの初期に、コンピュータ１２(1) は、スイッチングノード１１(6) の他のポートP1,P2,P4, . . . PPに接続されているデバイス（つまり、スイッチングノード１１(n) および／またはコンピュータ１２(m)）のIDを取得することを試みる。なお、スイッチングノード１１(6) は、上述したように、ポートP3を通してスイッチングノード１１(1) に接続されている。以上から理解されるように、スイッチングノード１１(6) のポートP3に関してオペレーションを実行する必要がないのは、そのポートがスイッチングノード１１(1) に接続されていると、コンピュータ１２(1) が第２繰り返し時に判断したためである。第３繰り返しでは、コンピュータ１２(1) は、＜P1,SN1,P2|P3,SN6,P1＞ という情報を収めている識別要求メッセージを初期に生成し、このコンピュータに接続されている通信リンク１３(1) 上にそのメッセージを送信する。スイッチングノード１１(1) はこの識別要求を受信するが、メッセージにはそのIDであるSN1が入っているので、そのメッセージを、ポートP2からスイッチングノード１１(6) に転送する。他方、スイッチングノード１１(6) はこの識別要求メッセージを受信するが、メッセージにはさらにそのIDであるSN6が入っているので、そのポートP1からメッセージを転送する。スイッチングノード１１(6) のポートP1が、例えば、通信リンク１３(16) に接続されていれば、スイッチングノード１１(6) はメッセージをスイッチングノード１１(3) に送信する。スイッチングノード１１(3) に電源が入っていれば、識別要求メッセージを受信し、自身であることと、この識別要求メッセージがそこから受信されたポートとを示している識別応答メッセージを生成する。スイッチングノード１１(3) のIDが、例えば、SN3であり、スイッチングノード１１(3) が識別要求メッセージをそこから受信したポートが、例えば、P5であれば、スイッチングノード１１(3) から与えられる識別応答メッセージは＜P1,SN1,P2｜P3,SN6｜P5,SN3＞ という情報を収めており、これは、基本的に、スイッチングノード１１(6) から送られてきた識別要求メッセージに入っているトポロジ情報P1,SN1,P2｜P3,SN6にそのトポロジ情報P5,SN3を付加したものである。識別応答メッセージを生成したあと、スイッチングノード１１(3) は、識別要求メッセージがそこから受信されたポートP5からその識別応答メッセージを転送することにより、それをスイッチングノード１１(6) に転送する。スイッチングノード１１(6) はこの識別応答メッセージを受信すると、そのメッセージをポートP3から転送することにより、それをスイッチングノード１１(1) に転送する。他方、スイッチングノード１１(1) はそのメッセージをポートP1から転送することにより、それをコンピュータ１２(1) に転送する。コンピュータ１２(1) は識別応答メッセージを受信すると、その識別応答情報からネットワークトポロジ情報P1,SN1,P2｜P3,SN6,P1｜P5,SN3を取得し、それを自分のネットワークトポロジデータベースに格納しておく。以上から理解されるように、このネットワークトポロジ情報は、順番に、SN6のIDをもつスイッチングノードがそのポートP1を通してSN1のIDをもつスイッチングノードに接続されていることと、SN3のIDをもつスイッチングノードがポートP５を通してSN６のIDをもつスイッチングノードに接続されていることを示している。
【００２１】
以上から理解されるように、スイッチングノード１１(6) の他のポートP2,P4, . . . ,PPの各々と、第２繰り返し時に見つかったスイッチングノード１１(3) と１１(2) のそれぞれのポートについても、対応するオペレーションが実行される。従って、第３繰り返しの終了時には、コンピュータ１２(1) は次のものを見つけていることになる。
【００２２】
(i)  スイッチングノード１１(6) に関連するオペレーション期間には、
(a)  コンピュータ１２(6)、１２(7) および１２(8) が存在することと、これらのコンピュータとスイッチングノード１１(6) がそこから接続されているスイッチングノード１１(6) のポート、
(b)  スイッチングノード１１(6) とスイッチングノード１１(3) がそこから相互に接続されているこれらのスイッチングノードの、それぞれのポート、および
(c)  スイッチングノード１１(5) が存在することと、スイッチングノード１１(6) とスイッチングノード１１(5) がそこから相互に接続されているこれらのスイッチングノードの、それぞれのポート。
【００２３】
(ｉｉ) スイッチングノード１１(3) に関連するオペレーション期間には、
（ａ） スイッチングノード１１(3) とスイッチングノード１１(5) がそこから相互に接続されているこれらのスイッチングノードの、それぞれのポート、
（ｂ） スイッチングノード１１(3) とスイッチングノード１１(2) がそこから相互に接続されているこれらのスイッチングノードの、それぞれのポート、および
（ｃ） スイッチングノード１１(4) が存在することと、スイッチングノード１１(3) とスイッチングノード１１(4) がそこから相互に接続されているこれらのスイッチングノードの、それぞれのポート。
【００２４】
(iii)  スイッチングノード１１(2) に関連するオペレーション期間には、
(a)  コンピュータ１２(2) が存在することと、そのコンピュータとスイッチングポート１１(2) がそこから相互に接続されているスイッチングノード１１(2)のポート、および
(b)  スイッチングノード１１(2) とスイッチングノード１１(4) がそこから相互に接続されているこれらのスイッチングノードの、それぞれのポート。
【００２５】
第４繰り返し期間には、コンピュータ１２(1) は、スイッチングノード１１(4) と１１(5) がそこから相互に接続されているポートと、これらのスイッチングノードがそこからコンピュータ１２(3) と１２(4)（スイッチングノード１１(4) の場合）および１２(5)（スイッチングノード１１(5) の場合）に接続されているポートを見つける。従って、第４繰り返しの終了時には、コンピュータ１２(1) はネットワーク１０の全トポロジを見つけ、それを自分のネットワークトポロジデータベースにロードしていることになる。
【００２６】
さらに、ネットワークトポロジ発見・スイッチングノード構成フェーズ期間に、コンピュータ１２(m) はスイッチングノード１１(n) を構成に含める。このオペレーションでは、コンピュータ１２(m) はスイッチングノード１１(n) から応答メッセージを受信すると、そのスイッチングノード１１(n) を構成に含めることを試みる。スイッチングノード１１(n) を構成に含める際に、コンピュータ１２(m) はそのスイッチングノードのための選択した制御レジスタに情報をロードすることにより、スイッチングノード１１(n) のための選択した動作パラメータ(operating parameters)をセットする。スイッチングノード１１(n) のための動作パラメータは、一般的に、他のネットワーク内のスイッチングノードに関連して使用される動作パラメータに対応しており、これらはこの分野の精通者に自明のことである。複数のコンピュータが特定のスイッチングノードを構成に含めようとすると起こる矛盾を防止するために、好ましいことは、１つのコンピュータ１２(m) だけがスイッチングノードを構成に含めるようにすることである。一般的に、ネットワーク１０内のコンピュータ１２(m) はいずれもが、スイッチングノードを構成に含めることが可能になっているが、好ましいことは、あるコンピュータ１２(m) がスイッチングノード１１(n) を構成に含めたあと、別のコンピュータ１２（ｍ’）(m'≠m) が、少なくともスイッチングノード１１(n) があとで電源オフにされるか、再初期化されるまでは、そのあとで同じスイッチングノード１１(n) を構成に含めることを許さないようにすることである。
【００２７】
１つのコンピュータ１２(m) だけがスイッチングノード１１(n) を設定に含めることを確実にするために、さらに本発明によれば、コンピュータ１２(m) からの識別要求メッセージに応答してスイッチングノード１１(n) によって生成された応答メッセージをコンピュータ１２(m) が受信したあとの設定オペレーションの開始時に、コンピュータ１２(m) は最初にスイッチングノード１１(n) をロックすることを試みるようにしている。スイッチングノードに電源が入れられ、初期化されるとき、すべてのスイッチングノードはあらかじめ決めた初期化ロック値をもち、その値は、一実施形態では、ゼロになっている。スイッチングノード１１(n) のロックを試みるとき、コンピュータ１２(m) は最初にロック値照会メッセージをスイッチングノード１１(n) に送信し、これを受けて、そのスイッチングノードはスイッチングノードのカレントロック値を収めているロック値応答メッセージを生成し、このメッセージはコンピュータ１２(m) に送信される。ロック値応答メッセージに入っているスイッチングノードのカレントロック値が初期化ロック値とは異なる別の値になっていれば、コンピュータ１２(m) は、最初に、別のコンピュータ１２（ｍ’）（ｍ’≠ｍ）  がスイッチングノード１１(n) を設定に含めようとしているか、あるいはすでに設定に含めていると判断するので、設定オペレーションを続けることを中止するが、その代わりに、ネットワークトポロジ発見オペレーションを上述したように続けることができる。
【００２８】
しかし、ロック値応答メッセージに示されているスイッチングノードのカレントロック値が初期化ロック値に一致しているとコンピュータ１２(m) が判断したときは、そのコンピュータ１２(m) は、スイッチングノード１１(n) が構成に含まれていないと予備的に判断することができる。その場合には、コンピュータ１２(m) は、スイッチングノード１１(n) に送信するためのロック値変更メッセージを生成し、このメッセージには初期化ロック値と新ロック値が含まれている。コンピュータ１２(m) によって生成される新ロック値はコンピュータに固有であるか、あるいは別のコンピュータによって生成されるおそれのない値であることが好ましく、例えば、コンピュータの識別子 (ID)、乱数などにすることができる。スイッチングノード１１(n) がロック値変更メッセージを受信したとき、スイッチングノードのカレントロック値がそのロック値変更メッセージに入っている初期化ロック値に一致していれば、スイッチングノード１１(n)はそのカレントロック値を、ロック値変更メッセージに入っている新ロック値に更新する。他方、スイッチングノードのカレントロック値がロック値変更メッセージに入っている初期化ロック値に一致していなければ、スイッチングノード１１(n)はそのカレントロック値を、ロック値変更メッセージに入っている新ロック値に更新しない。
【００２９】
コンピュータ１２(m) はロック値変更メッセージをスイッチングノード１１(n) に送信したあと、コンピュータ１２(m)は、スイッチングノードのカレントロック値の検索を開始するために、スイッチングノード１１(n) に送信するためのロック値照会メッセージを再び生成する。スイッチングノード１１(n) は、スイッチングノードのカレントロック値を収めているロック値応答メッセージを再び生成し、それをコンピュータ１２(m) に送信する。ロック値応答メッセージに入っているスイッチングノードのカレントロック値が、コンピュータ１２(m) によって以前に与えられた新ロック値に一致していれば、コンピュータ１２(m) はスイッチングノード１１(n) をロックしたと判断できるので、そのスイッチングノード１１(n) を構成に含めることができる。スイッチングノード１１(n) を構成に含めたあと、コンピュータ１２(m) はネットワークトポロジ発見オペレーションを上述したように続けることができる。
【００３０】
他方、スイッチングノード１１(n) からロック値応答メッセージを受信したあと、ロック値応答メッセージに入っているスイッチングノード１１(n) のカレントロック値が、コンピュータ１２(m) によって以前に与えられた新ロック値と異なっているとコンピュータ１２(m) が判断したときは、コンピュータ１２(m) は、スイッチングノード１１(n) から受信した初期ロック値応答メッセージのあとで、別のコンピュータ１２（ｍ’）  （ｍ’’≠ｍ）がスイッチングノード１１（ｎ）  をロックしたと判断する。その場合には、コンピュータ１２（ｍ）  は、別のコンピュータ１２（ｍ’）  （ｍ’’≠ｍ）がスイッチングノード１１（ｎ）  を設定に含めようとしているか、すでに設定に含めていたと判断するので、設定オペレーションを続けることを中止するが、その代わりに、ネットワークトポロジ発見オペレーションを上述したように続ける。
【００３１】
各コンピュータは、各スイッチングノード１１(n) に対して対応するオペレーションを実行することができる。このことから理解されるように、ネットワークトポロジ発見・スイッチングノード構成フェーズの終了時には、コンピュータのすべては、ネットワークトポロジ発見オペレーション期間にスイッチングノードのすべてとコンタクトしていることになる。しかし、上述したスイッチングノードロッキングプロトコルは、各スイッチングノード１１(n) が、多くてもコンピュータ１２(m) の１つによって構成に含められるようにしている。
【００３２】
ネットワークトポロジ発見・スイッチングノード構成フェーズのあと、コンピュータ１２(m) は、第２の通常動作フェーズ期間に、ネットワークを通る仮想回線の確立を制御する過程において、ネットワークを使用して情報を転送する。仮想回線を確立するとき、コンピュータ１２(m) は、コンピュータ間のネットワークを通る経路を、ネットワークトポロジデータベースから決定するが、この経路はコンピュータ１２(m) 間の一連のスイッチングノード１１(n) と通信リンク１３(p)を示している。コンピュータ１２(m) はそれぞれの仮想回線に対する該当経路または最適経路を、従来の経路決定手法 (path determination methodology) を使用して決定することができるが、それらの多くはこの分野の精通者に周知である。それぞれの仮想回線に対する経路が決定されたあと、コンピュータらは協力し合って、仮想回線経路情報をスイッチングノードら１１(n) に提供する。これらスイッチングノード１１(n) は、それぞれのメッセージを構成するセルを転送する際に、コンピュータ１２ら(m) から提供された仮想回線経路情報を使用する。これらのオペレーションにおいて、スイッチングノード１１(n) の各々はルーティングテーブル (routing table) をもっており、このルーティングテーブルは、スイッチングノードが仮想回線に関連するセルを受信するポートごとに、スイッチングノード１１(n) が仮想回線に関連するセルをどのポートから送信するかを示している。コンピュータ１２(m) は仮想回線制御情報をルーティングテーブルにロードし、これは、そのあと、各仮想回線に対するメッセージを転送する際にスイッチングノード１１(n) によって使用される。コンピュータ１２(m) は仮想回線に対する経路を決定し、仮想回線に対するそれぞれの経路に沿ってスイッチングノード１１(n) のルーティングテーブルに仮想回線制御情報をロードするので、スイッチングノード１１(n) は、これを成し遂げるための処理能力をもつ必要がなくなるため、スイッチングノード１１(n) のコストを低減化することができる。
【００３３】
これらのフェーズの各々に関連してコンピュータ１２(m) とスイッチングノード１１(n) によって実行されるオペレーションについては、以下で詳しく説明する。しかし、予備知識として、ネットワーク１０で使用されるコンピュータ１２(m) とスイッチングノード１１(n) の詳細を説明しておくことにする。図２と図３は、それぞれ本発明の一実施形態で使用されるコンピュータ１２(m) とスイッチングノード１１(n) を示す機能ブロック図である。一実施形態では、コンピュータ１２(m) とスイッチングノード１１(n) は、前掲のGutierrez他、Clayton他、およびWilliamsの特許出願に関連して上述したコンピュータとスイッチングノードと類似のものである。図２に示すように、コンピュータ１２(m) はプロセッサ２０、システムメモリ２１、およびネットワークインタフェース２２を搭載し、これらは、すべてが相互接続構成 (interconnection arrangement)２３によって相互接続されている。一実施形態では、相互接続構成２３は従来のPCIバスを含んでいる。コンピュータ１２(m) は、相互接続構成２３に接続された従来の大容量記憶サブシステム（図示せず）を、１つまたは複数搭載することも可能であるが、これは、一般に、プロセッサ２０によって処理可能な情報を長期間保管しておくために使用されている。大容量記憶サブシステムとしては、ディスクやテープのサブシステム、光ディスク記憶装置およびCD-ROM装置のように、情報をそこに格納しておくことおよび／または情報をそこから取り出すことができる装置を含めることができる。また、大容量記憶サブシステムに、オペレータによる取り外しと取り付けが可能である取り外し可能記憶媒体を使用すると、オペレータはプログラムとデータをその媒体からコンピュータ１２(m) にロードし、処理されたデータをコンピュータから取得することができる。
【００３４】
コンピュータ１２(m) は、相互接続構成２３に接続された従来の入出力サブシステム（図示せず）を、１つまたは複数搭載することも可能であり、そのようなものとして、一般に、オペレータとコンピュータ１２(m) とのインタフェースとなっているオペレータ入出力サブシステムがある。具体的には、オペレータ入力サブシステムとしては、例えば、キーボートとマウスデバイスがあり、オペレータはこれを使用すると、対話式で情報をコンピュータ１２(m) に入力して処理させることができる。さらに、オペレータ入力サブシステムは、オペレータがコンピュータ１２(m) を制御することを可能にする機構を備えることができる。オペレータ出力サブシステムとしては、画像表示装置（ビデオディスプレイデバイス）のように、コンピュータ１２(m) が、プロセッサ２０の制御の下で、処理結果をオペレータに対して表示する装置がある。さらに、オペレータに出力をハードコピーで提供するプリンタを装備させることができる。
【００３５】
ネットワークインタフェース２２は、デスティネーションコンピュータ（宛先コンピュータ）１２(m) として動作している他のコンピュータに転送されるデータをシステムメモリ２１から取り出し、そのデータからセルを生成し、生成されたセルを、他のコンピュータに接続された通信リンク１３(p) 上に送信するが、この通信リンクは、図１を参照して上述した通信リンク１３(p) の１つを形成しているものである。さらに、ネットワークインタフェース２２は、図１を参照して上述した通信リンク１３(p) の１つを形成している通信リンク１３(p) からセルを受信し、そのセルからデータを抽出し、そのデータをシステムメモリ２１内の該当のバッファに転送し、そこに保管しておく。本発明の一実施形態で使用されるネットワークインタフェース２２の詳細は、前掲のGutierrez他、Clayton他、およびWilliams特許出願に記載されている。
【００３６】
プロセッサ２０は、全体を参照番号３０で示している１つまたは２つ以上のアプリケーションプログラムを、オペレーティングシステムの制御の下で処理する。アプリケーションプログラム３０のそれぞれを処理する際、プロセッサはネットワークインタフェース２２が、１つまたは２つ以上のATMセルの形でメッセージをそれぞれの仮想回線上に送信し、同じく１つまたは２つ以上のATMセルの形でメッセージをそれぞれの仮想回線上で受信することを可能にする。一実施形態では、プロセッサ２０とネットワークインタフェース２２は、Compaq Computer Corp.、Intel Corp.、およびMicrosoft Corp.によって公表されている仮想インタフェースアーキテクチャ(Virtual Interface Architecture  VIA)仕様、第１版(1997年12月16日)に従って動作し、それぞれの仮想回線を利用したメッセージの送受信を容易化している。
【００３７】
上述したように、本発明によれば、コンピュータ１２(m) はネットワーク１０のトポロジを判断し、そのトポロジを使用してネットワーク上の仮想回線の確立を容易化している。これを可能にするために、プロセッサ２０は、トポロジメッセージジェネレータ・プロセッサ (topology message generator and processor)３１と仮想回線制御メッセージジェネレータ (virtual circuit control message generator)３２と以下では呼ぶことにする、２つの追加エレメントも備えており、システムメモリ２１はネットワークトポロジデータベース３３も含んでいる。トポロジメッセージジェネレータ・プロセッサ３１は、上述したように、第１フェーズ期間に使用され、コンピュータ１２(m) がネットワークトポロジ情報を取得し、その情報（つまり、トポロジ情報）をネットワークトポロジデータベース３３に格納しておくことを可能にする。仮想回線制御メッセージジェネレータ３２は、上述したように、第２フェーズ期間に使用され、データベース３３内のネットワークトポロジ情報を使用して、スイッチングノード１１(n) を通るそれぞれの仮想回線を確立するようにする。
【００３８】
図３は、図１に示すネットワーク１０で使用されるスイッチングノード１１(n) を示す機能ブロック図である。スイッチングノード１１(n) の一実施形態の構造とオペレーションの詳細説明は、前掲のGutierrez他、Clayton他、およびWilliamsの特許出願に記載されている。一般的に、また図３に示すように、スイッチングノード１１(n) は複数の入力ポートモジュール６０(1) 乃至６０(I)（全体を参照番号６０(i) で示している）、複数の出力ポートモジュール６１(1) 乃至６１(I)（全体を参照符号６１(i) で示している）、バッファストア６３、バッファマネージャ６４、および制御ブロック８０を実装し、制御ブロック８０には、ノードロックレジスタ８１、ノードIDレジスタ８２および制御メッセージプロセッサ８３が含まれている。ノードロックレジスタ８１はノードロック値を受け取り、これは、特に、ノードトポロジ発見・スイッチングノード構成フェーズ期間にスイッチングノードへのアクセスを同期化するために使用される。ノードIDレジスタ８２は、ネットワーク１０内のスイッチングノード１１(n) を一意的（ユニーク）に識別しているスイッチングノードID値を受け取る。
【００３９】
各入力ポートモジュール６０(i) および対応するインデックスの付いた出力ポートモジュール６１(i) は一緒になって、スイッチングノード１１(n) の「ポート」を構成している。各入力ポートモジュール６０(i) は通信リンク１３(p) 上でコンピュータ１２(m) またはスイッチングノードからセルを受信するように接続されている。各出力ポートモジュール６１(i) は、同じ通信リンク１３(p) を利用してセルをコンピュータ１２(m) またはスイッチングノードに送信するように接続されている。入力ポートモジュール６０(i) がスイッチングノードからセルを受信し、出力ポートモジュール６１(i) がセルをスイッチングノードに送信するとき、スイッチングノード１１(n) の入力ポートモジュール６０(i) がそこから受信するスイッチングノード、またはスイッチングノード１１(n) の出力ポートモジュール６１(i) からセルが送信される先のスイッチングノードは、好ましくは、別のスイッチングノード１１（ｎ’） (n'≠n) であるが、通信リンク１３(p) がスイッチングノード１１(n) のループバックコネクション (loopback connection) となっている場合は、同じスイッチングノードであっても構わない。
【００４０】
各入力ポートモジュール６０(i) は、そこに接続された通信リンク１３(p) 上でセルを受信したとき、そのセルをバッファストア６３にバッファリングする。各入力ポートモジュール６０(i) は、セルを実際に受信し、そのセルをバッファに置いてからバッファストア６３にセルを転送して、そこに保管しておくようにするセルレシーバ７０と、ルーティングテーブル７４をもつ入力ポートモジュールコントロール７１とを備えており、ルーティングテーブルには、入力ポートモジュール６０(i)がセルを受信する仮想回線に関する仮想回線情報が収められている。セルレシーバ７０がセルを受信すると、入力ポートモジュールコントロール７１はそのセルをバッファストア６３に転送し、そこに保管しておく。一般的に、バッファストア６３は複数のバッファから構成され、各バッファは１つのセルからの情報を保管しておくことができるが、これらのバッファは、バッファマネージャ６４内のバッファリンクヘッダ７５によってリンクリスト (linked list) に編成されている。ルーティングテーブル７４に入っている各仮想回線の仮想回線情報ブロックは、仮想回線に関連するセルがどの出力ポートモジュール６１（ｉ’） から送信されるかも示しており、入力ポートモジュールコントロール７１も、リンクリストを設定したあと、その出力ポートモジュール６１（ｉ’） によって送信されるセルが仮想回線に対して受信されたことを出力ポートモジュール６１（ｉ’）に通知する。
【００４１】
各出力ポートモジュール６１（ｉ’）は、出力ポートモジュール６１（ｉ’）がセルをそこから送信しようとしている仮想回線に対して少なくとも１つのセルがバッファストア６３に置かれているとの通知を、入力ポートモジュール６０(i) の入力ポートモジュールコントロール７１から受信すると、仮想回線に関連するセルをバッファストア６３から取り出すオペレーションを開始し、そのセルをそこに接続されている通信リンク１３(p) 上に送信する。各出力ポートモジュール６１（ｉ’）は出力ポートモジュールコントロール７２とセルトランスミッタ７３を備えている。出力ポートモジュールコントロール７２は、それぞれの入力ポートモジュール６０(i) の入力ポートモジュールコントロール７１から通知を受信する。この通知に応答して、出力ポートモジュールコントロール７２は、入力ポートモジュールコントロール７１によって維持されている仮想回線の仮想回線情報ブロックにアクセスし、仮想回線に関連するリンクリスト内の最初のセルが、バッファストア６３内のどのバッファに置かれているかを判断し、そのセルをバッファストア６３から取り出し、セルを処理と送信のためにセルトランスミッタ７３に転送できるようにする。
【００４２】
以上から理解されるように、入力ポートモジュール６０(i) は、セル以外のメッセージを受信することも可能である。具体的には、 (i) ネットワークトポロジ発見オペレーション期間には、識別要求メッセージと識別要求応答メッセージ、 (ii) スイッチングノード設定オペレーション期間には、ロック値照会メッセージ、ロック値応答メッセージおよびロック値変更メッセージ、および (iii) 仮想回線確立オペレーション期間には、仮想回線確立制御メッセージを受信することが可能である。
【００４３】
入力ポートモジュール６０(i) は識別要求メッセージを受信すると、その識別要求メッセージを制御ブロック８０、具体的には、制御メッセージプロセッサ８３に渡す。この識別要求メッセージを受けて、制御メッセージプロセッサ８３は、スイッチングノード１１(n) が識別応答メッセージを生成しようとしているのか、識別要求メッセージを出力ポートモジュール６１（ｉ’）に転送し、そこから別のスイッチングノードまたはコンピュータに送信しようとしているのかを判断する。スイッチングノード１１(n) が、識別要求メッセージを別のスイッチングノードまたはコンピュータに転送しようとしているのであれば、この識別要求メッセージには、スイッチングノード６０(i) がその識別要求メッセージをそこから送信しようとしているポートのIDが入っているので、制御メッセージプロセッサ８３はその識別要求メッセージを、そのポートの一部を形成している出力ポートモジュール６１（ｉ’）に転送する。そのあと、出力ポートモジュール６１（ｉ’）は識別要求メッセージを送信する。入力ポートモジュール６０(i) によって受信される識別応答メッセージの転送についても、同様なオペレーションが行われる。
【００４４】
他方、スイッチングノード１１(n) が識別応答メッセージを生成するものと制御メッセージプロセッサ８３が判断したときには、その応答メッセージを生成し、このメッセージには、識別要求メッセージからの情報が含まれているほかに、ノードIDレジスタ８２から取得した自己のスイッチングノードのIDと、識別要求メッセージがそこから受信されたポート ("i") のIDも含まれている。識別要求応答メッセージを生成したあと、制御メッセージプロセッサ８３はそのメッセージを、そのポートの一部を形成している出力ポートモジュール６１(i) に転送し、そこから送信される。
【００４５】
入力ポートモジュール６０(i) がロック値照会メッセージ、ロック値応答メッセージまたはロック値変更メッセージを受信したときも、そのメッセージを制御メッセージプロセッサ８３に転送する。メッセージがロック値応答メッセージであると制御メッセージプロセッサ８３が判断し、それが別のスイッチングノード１１（ｎ’）によって生成されたものであれば、制御メッセージプロセッサ８３はそのメッセージを該当の出力ポート６１（ｉ’）に転送し、ロック値応答メッセージがその応答の対象となっているロック値照会メッセージを生成したコンピュータ１２(m) に送信される。同様に、別のスイッチングノード１１（ｎ’）がそれぞれのメッセージに応答するものと制御メッセージプロセッサ８３が判断したときは、そのメッセージを該当の出力ポートモジュール６１（ｉ’）に転送し、そこからそのスイッチングノード１１（ｎ’）に送信される。他方、メッセージがロック値照会メッセージまたはスイッチングノード１１(n)が応答することになっているロック値変更メッセージであると、制御メッセージプロセッサ８３が判断したときには、
【００４６】
(i)  メッセージがロック値照会メッセージであれば、それ（すなわち、制御メッセージプロセッサ８３）はロック値応答メッセージを生成し、ノードロックレジスタ８１からのスイッチングノードのカレントロック値をそのロック値応答メッセージ内にロードしてから、そのロック値応答メッセージを適切な出力ポートモジュール６１（ｉ’） に渡し、そこから送信させる。
【００４７】
(ii)  メッセージがロック値変更メッセージであれば、それ（すなわち、制御メッセージプロセッサ８３）は、ロック値変更メッセージに入っているカレント値とノードロックレジスタに入っている値と比較して、
(a)  ロック値変更メッセージに入っている初期化ロック値がノードロックレジスタ８１に入っているカレントロック値と一致していれば、それ（すなわち、制御メッセージプロセッサ８３）はロック値変更メッセージからの変更ロック値をノードロック値にロードするが、
(b)  ロック値変更メッセージに入っている初期化ロック値がノードロックレジスタ８１に入っているカレントロック値と一致していなければ、それ（すなわち、制御メッセージプロセッサ８３）はロック値変更メッセージからの変更ロック値をノードロック値にロードすることなく、ロック値変更メッセージを無視する。
【００４８】
最後に、入力ポートモジュール６０(i) が仮想回線確立制御メッセージを受信したときは、これ（すなわち、入力ポートモジュール６０(i)）は、そのメッセージがスイッチングノード１１(n) に対する仮想回線確立制御情報を収めているかどうかを最初に判断する。そうであれば、入力ポートモジュール６０(i)は仮想回線情報をそのルーティングテーブル７４にロードする。他方、そのメッセージが、別のスイッチングノード１１（ｎ’）に対する仮想回線確立制御情報を収めていると入力ポートモジュール６０(i)が判断したときは、そのメッセージを制御メッセージプロセッサ８３に転送する。これを受けて、制御メッセージプロセッサ８３は、メッセージがどの出力ポートモジュール６１（ｉ’） から送信されるものであるかを、そのメッセージから判断し、メッセージをその出力ポートモジュール６１（ｉ’）に転送し、そこから送信させる。
【００４９】
図４のフローチャートは、ネットワークトポロジ発見・スイッチングノード構成フェーズに関連してコンピュータ１２(m)によって実行されるオペレーションを示している。図４に示すオペレーションは、この分野の精通者には上記説明から明らかであるので、これ以上詳しく説明することは省略する。
【００５０】
本発明によれば、いくつかの利点が得られる。具体的には、本発明によるメカニズムを利用すると、ネットワーク内のコンピュータおよびネットワークに接続可能な他の「インテリジェント」デバイスは、ネットワークに含まれるスイッチングノードのトポロジを自ら判断できるので、スイッチングノードはその判断の必要性から解放されることになる。さらに、本発明によるメカニズムを利用すると、インテリジェントデバイスはスイッチングノードを構成に含めることができるので、スイッチングノード自身がそのような構成を行わないで済むことになり、また、複数のデバイスがある特定のスイッチングノードについてそのような構成を行うと、構成の試みの間で矛盾起こすおそれがあるので、そのようなことから守られている。さらに、本発明による構成を利用すると、インテリジェントデバイスは仮想回線情報を、それぞれのスイッチングノードのルーティングテーブルに直接にロードできるので、情報を転送できる仮想回線を確立することができる。これらはすべて、本来ならばスイッチングノードに実行させる必要のある処理量を削減するのに役立つので、ネットワーク内で使用されるスイッチングノードのコストの低減化に役立つことができる。さらに、スイッチングノードの構成を、上述したように分散化して行うと、構成「マスタ」を用意しなくても、スイッチングノードの構成を行うことができる。
【００５１】
以上の説明から理解されるように、上述してきたシステムは種々態様に変更することが可能である。例えば、本発明はスイッチングノード１１(n)によって相互接続されたコンピュータ１２(m)を含むものとして説明してきたが、スイッチングノードは多種タイプのデバイスを相互接続して、デバイス間で情報を転送することも可能である。
【００５２】
さらに、以上の説明から理解されるように、ネットワークトポロジ発見オペレーション期間に他の形体の識別要求メッセージと識別応答メッセージを使用することが可能である。例えば、スイッチングノードIDのシーケンス（一連）をポートIDと一緒に識別要求メッセージと応答メッセージの中で明示的に与えるのではなく、当然に理解されるように、識別要求メッセージにスイッチングノードIDを付ける必要はなく、それぞれの識別応答メッセージを生成するスイッチングノードのスイッチングノードIDを識別要求メッセージに付けるだけでよい。このような構成では、コンピュータ１２(m) によって生成される識別要求メッセージには、識別要求メッセージを、識別応答メッセージを生成するスイッチングノード１１(n) にネットワークを通して転送するとき使用されるフォワード（順方向）ルート情報と、識別応答メッセージを、その識別応答メッセージを生成するスイッチングノード１１(n) から識別要求メッセージを生成したコンピュータ１２(m) にネットワークを通して転送するとき使用されるリターン（戻り）ルート情報の両方が含まれることになる。具体的に説明すると、フォワードルート情報は、連続するスイッチングノード１１(n) がそれぞれどのポート（存在する場合）から識別要求メッセージを送信しようとしているのかを示す、一連のゼロ個または１個以上のポートIDを含んでいる。各スイッチングノードは識別要求メッセージを受信すると、フォワードルート情報を調べ、そのフォワードルート情報にポートIDが含まれていると判断したときは、フォワードルート情報に入っている最初のルートIDを削除して、その削除されたルートIDで示されたポートから識別要求メッセージを送信する。他方、フォワードルート情報にポートIDが含まれていないとスイッチングノードが判断したときは、識別要求メッセージを転送しないが、その代わりに、その識別要求メッセージに応答して識別応答メッセージを生成する。
【００５３】
上述したように、コンピュータ１２(m) によって生成された識別要求メッセージに入っているフォワードルート情報は、ポートIDがゼロ個になっていることがある。その場合には、以上から理解されるように、識別応答メッセージは、そのコンピュータ１２(m) に接続されているスイッチングノード１１(n) によって生成される。
【００５４】
同様に、識別要求メッセージの中で与えられるリターンルート情報は、連続するスイッチングノード１１(n) のそれぞれが、識別応答メッセージを生成するスイッチングノードから識別要求メッセージを生成したコンピュータ１２(m) までの経路上に、どのポート（存在する場合）から識別応答メッセージを送信しようとしているのかを示している一連のゼロ個または１個以上のポートIDを含んでいる。スイッチングノードは識別応答メッセージを生成するとき、識別要求メッセージに入っているリターンルート情報を使用し、そのスイッチングノードIDと、スイッチングノードがそこから識別要求メッセージを受信したポートのポートIDを付加する。識別応答メッセージを生成したあと、スイッチングノードは識別要求メッセージを受信したときのポートから識別応答メッセージを送信する。識別要求メッセージの場合と同様に、識別応答メッセージを受信する各スイッチングノードはリターンルート情報に入っている最初のルートIDを削除し、削除したルートIDで示されたポートから識別応答メッセージを送信する。好ましくは、リターンルート情報は、識別要求メッセージを転送するとき使用されたものと同じ、一連のスイッチングノードからなる経路を利用して、スイッチングノードが識別応答メッセージを返送できるようになっているが、識別応答メッセージを生成したスイッチングノードから識別要求メッセージを生成したコンピュータ１２(m) に識別応答メッセージが、反対方向に転送されるようにすることもできる。その場合には、識別応答メッセージを受信したとき、コンピュータ１２(m) は、識別応答メッセージで特定されたスイッチングノードとポートを、その識別応答メッセージが応答となっている識別要求メッセージで特定された経路と関連付けることにより、その経路に関連するネットワークトポロジを判断し、その一部を延長することができる。
【００５５】
さらに、コンピュータ１１(m) は、それぞれの識別応答メッセージがそこから受信されたポートを除く、それぞれのスイッチングノードのポートすべてについて、各々のポートごとに識別要求メッセージを生成するものとして説明してきたが、当然に理解されるように、コンピュータ、スイッチングノード、その他に接続されているそれぞれのポートがスイッチングノードに分かっていて、その情報がコンピュータに渡されるようにすれば、コンピュータは、これらのポートに対する識別要求メッセージを生成するだけで済むことになる。
【００５６】
さらに、コンピュータ１２(m) は、ネットワークトポロジ発見・設定フェーズ期間に設定成を行うものとして説明してきたが、当然に理解されるように、この設定は、ネットワークトポロジ発見オペレーションと同時に行う必要はなく、当然に、別々に行うことも、コンピュータ１２(m)（または他のデバイス）の１つである設定マスタに行わせることも、そのために特別に用意された設定マスタに行わせることも可能である。さらに、コンピュータは、ネットワークトポロジ発見・設定オペレーションを初期フェーズとして実行するものとして説明してきたが、当然に理解されるように、コンピュータは少なくともネットワークトポロジ発見オペレーションを初期フェーズ以外の時点で行い、ネットワークトポロジが変化していれば、それを見つけることも可能である。コンピュータはネットワークトポロジ発見オペレーションを、例えば、定期的に行うようにすることも、自分のネットワークトポロジデータベースなどに示されていないコンピュータからメッセージを受信したといったような、選択したトリガリングイベント（triggering events）が起こったとき行うようにすることも可能である。
【００５７】
さらに、本発明は、情報が仮想回線上に転送されるようなネットワークに関連して説明してきたが、当然に理解されるように、ネットワークは情報を「コネクションレス(connectionless)方式」で転送するようにすることも可能である。その場合には、第２フェーズ期間にルーティングテーブル７４に仮想回線情報を入れておく代わりに、コンピュータ１２(m) が絶対デスティネーションアドレス／出力ポート情報を与え、スイッチングノードが、受信したメッセージパケットをルーティングする際にその情報を使用できるようにすることも可能である。
【００５８】
以上の説明から理解されるように、本発明によるシステムは、その全体または一部を特殊目的ハードウェアまたは汎用コンピュータシステム、あるいはその任意の組み合わせから構築することが可能であり、そのどの部分も適当なプログラムで制御することが可能である。どのプログラムも、その全体または一部を従来と同じようにシステムの一部にすることも、システムに格納しておくことも、あるいはその全体または一部を、従来のように情報を転送するネットワークまたは他のメカニズム上のシステムに送るようにすることも可能である。さらに、以上から理解されるように、システムは、システムに直接に接続可能である、あるいは従来のように情報を転送するネットワークまたは他のメカニズム上のシステムに情報を転送することができる、オペレータ入力エレメント（図示せず）を使用してオペレータが与えた情報で動作させることも、他の方法で制御することも可能である。
【００５９】
上述してきた説明は、本発明の特定の実施形態に限定されるものではなく、当然に理解されるように、本発明は種々態様に変更し、改良することにより、本発明の利点のすべてまたは一部を達成することが可能である。上記およびその他の変更と改良は請求項に記載されているとおりであり、本発明の真の精神と範囲に属するものである。
【図面の簡単な説明】
本発明は具体的には特許請求の範囲に記載されているが、本発明の上記および他の利点を理解しやすくするために、以下では、添付図面を参照して説明することにする。
【図１】  本発明による新規で、改良された分散スイッチと接続制御構成を備えたコンピュータネットワークを示す概略図である。
【図２】  図１に示すネットワークで使用されるコンピュータを示す機能ブロック図である。
【図３】  図１に示すコンピュータで使用されるスイッチングノードを示す機能ブロック図である。
【図４】  本発明に関連して図２に示すコンピュータによって実行されるオペレーションを示すフローチャートである。
【図４Ａ】  本発明に関連して図２に示すコンピュータによって実行されるオペレーションを示すフローチャートである。
【図４Ｂ】  本発明に関連して図２に示すコンピュータによって実行されるオペレーションを示すフローチャートである。
【図４Ｃ】  本発明に関連して図２に示すコンピュータによって実行されるオペレーションを示すフローチャートである。
【図４Ｄ】  本発明に関連して図２に示すコンピュータによって実行されるオペレーションを示すフローチャートである。
【図４Ｅ】  本発明に関連して図２に示すコンピュータによって実行されるオペレーションを示すフローチャートである。
【図１】
0004759135.tif 000002
【図２】
0004759135.tif 000003
【図３】
0004759135.tif 000004
【図４】
0004759135.tif 000005
【図４Ａ】
0004759135.tif 000006
【図４Ｂ】
0004759135.tif 000007
【図４Ｃ】
0004759135.tif 000008
【図４Ｄ】
0004759135.tif 000009
【図４Ｅ】
0004759135.tif 000010