JP2001524272A

JP2001524272A - Method and apparatus for generating a network topology

Info

Publication number: JP2001524272A
Application number: JP52067998A
Authority: JP
Inventors: ジョーゼフＡエクストロム; Ｊバーナードギル; トーマスＧマクニール; フイヤン
Original assignee: ヴィピーエヌエックスドットコムインコーポレイティッド
Priority date: 1996-10-28
Filing date: 1997-10-27
Publication date: 2001-11-27
Also published as: EP0876649A4; WO1998018306A3; WO1998018306A2; EP0876649A2

Abstract

(57)【要約】コンピュータネットワークのトポロジーを決定するための方法がコンピュータネットワークの少なくとも１つのサブセットに於ける各装置からポート転送用データを読み取ることを含んでいる。次いでこのポート転送用データは、コンピュータネットワークの少なくとも当該サブセットのトポロジーを派生させるために処理、並びに解析される。ポート転送用データの読み取りは、好適には後続の解析のために最大限に利用可能なポート転送用データを供給するため、コンピュータネットワークの少なくとも当該サブセットに於ける全てのスイッチを発見することによって進行される。トポロジー的解析は帰納的関数を使用し、発見されたスイッチを、スイッチの相互接続を効果的に表示可能な樹木構造に配置することによって、派生したポート転送用データからトポロジーを派生させる。 SUMMARY A method for determining a topology of a computer network includes reading port forwarding data from each device in at least one subset of the computer network. The port forwarding data is then processed and analyzed to derive the topology of at least the subset of the computer network. Reading the port forwarding data preferably proceeds by discovering all switches in at least that subset of the computer network to provide the maximum available port forwarding data for subsequent analysis. Is done. Topological analysis uses a recursive function to derive the topology from the derived port forwarding data by placing the discovered switches in a tree structure that can effectively display the switch interconnections.

Description

【発明の詳細な説明】ネットワークトポロジーを生成するための方法と装置技術分野本発明は、概してコンピュータネットワークシステムに関し、さらに特定的にはコンピュータネットワークシステム内部の装置間の相互接続を決定し表示するための方法と装置に関する。背景技術図１では、先行技術の一例であるコンピュータネットワークシステム10が、第１ローカルエリアネットワーク（「LAN」）12と、第2LAN14と、ワイドエリアネットワーク（「WAN」）16とを含んでいる。LAN（LAN12、14等）とWAN（WAN16等）との間の区別は必ずしも明確ではないが、一般的にはLANは１つの建物内部または小規模の建物グループ内部といった地理的に比較的狭い領域で使用され、WANは１つの地方、州、国または時として全世界規模に及ぶ地理的に大規模な領域で使用される。LANとWANは、ネットワークに於けるデータ通信のためのデジタル装置の相互接続に関しては双方共に同様の機能を実行するが、こうした２タイプのネットワークの構成及び使用装置は、後述の通り幾分異なる傾向がある。例として図１のLAN12について言えば、LANは概して複数の「スイッチ」18を含み、その各スイッチが複数の「ポート」20を有している。ポートの幾つかまたは全ては、他の装置、例えば他のスイッチ18やコンピュータ22に接続されている。スイッチ18（時に「ブリッジ」とも呼ばれる）は、ローカルエリアネットワーク 12を別個の領域またはローカルエリアネットワーク12のサブセットに分割し、コンピュータシステムの相互接続媒体24上に於けるデータ衝突を減少させる機能を働かせる。この媒体24（一般に、ツイストペア線、同軸ケーブルまたは光ファイバを装備している）は、一度に１つのネットワーク装置向けにしかデータを伝送することができないため、所定位置にある媒体の使用を一定時間内に数個の装置が試行している場合は通信ボトルネックが発生する結果となる。スイッチ18は、個々の媒体24をローカルエリアネットワーク12の他の各々の媒体24から隔離して１つの媒体上のデータ通信が必ずしも他の媒体上のデータ通信に影響しないようにすることにより、この問題を軽減している。スイッチ18は、理論上は比較的単純な方法で作動する。スイッチ18は、そのポート20の１つに於いてデータ通信を検知すると、そのデータをどのポートに（もしあれば）進めるべきかを決定する。例えば、特定ポートに見い出されるデータが既にそのポートに結合されている装置に関するものである（即ち、送信側装置と受信側装置が同じ媒体24上にある）場合でも、そのデータはスイッチの他のポートへと進められることはないため、ネットワークの他の媒体上の不必要なトラフィックが除去される。他の例で、スイッチが第２のポートに結合された装置向けのデータを第１ポートで受信すると、スイッチはそのデータをこの第２ポートに進める(「切換する」)。従って、第１ポート媒体と第２ポート媒体に接続された装置だけが、このデータ転送によって影響される。スイッチ18が第１のポートでデータを受信し、しかもそのデータをどの装置に送信するか解らない場合、スイッチは一般にデータをその全ポートから出し、受信装置からの応答を待ってその装置が所在するポートを決定する。次に、今後は当該装置向けのデータを適正ポートに直接送信できるように、当該装置のポート番号が「テーブル」に格納される。大形LANは、意識喪失性の複雑さを有する「トポロジー」を想定することができる。本書で使用しているように、「トポロジー」は、コンピュータネットワークシステム10内部、LAN内部またはLANのサブセット内部に於ける様々な装置の相関的な物理的相互接続を意味している。トポロジーの適正な「ドメイン」は一般にLAN（またはLANのサブセット）として言及されるが、本発明は、同報通信ドメインを限定する任意のスイッチセットのトポロジーを決定することができる。当業者には周知のように、「同報通信ドメイン」は、当該ドメインの同報通信アドレス宛てに送信されたデータパケットを受信する装置セットである。「装置」とは、ネットワークに接続され、少なくともネットワークのその部分内部で固有のネットワークアドレスを提供されているデジタル式電子装置を意味している。従って、例えばLAN12に図示されている装置は、スイッチ18とコンピュータ22とを含んでいる。無論、コンピュータネットワークシステムでは、他の装置も使用が可能である。典型的には、１つまたは複数のコンピュータ22が媒体24に結合され、媒体24がスイッチ18の１つまたは複数のポート20に結合されている。媒体24に多数のコンピュータが結合されている場合、媒体は「共有媒体」と呼ばれる。例によっては、図１のバックボーン26が示すように、スイッチ18間に「バックボーン」接続（即ち媒体）が生成されているものがある。バックボーン26の目的は、ローカルエリアネットワーク12の様々なスイッチ間に超高速通信を提供して大量のデータを高速で転送することにある。スイッチ18は超高速ではあるがデータ通信に於いて遅延または「待ち時間」を生成することから、こうしたバックボーン26接続は有用である。 WAN16は、一般にデータ通信のために多数のLANネットワークを結合するために使用される。最も良く知られているWANはいわゆるインターネット（Internetョ）であり、何千ものコンピュータ及びLANを結合してデータ通信を行っている。典型的には、WANはルータ28として知られる他のタイプのネットワーク装置を使用して、１つのLANからのデータを他のLANに向けて転送する。インターネット用のルータの大部分は、カリフォルニア州サンホセ所在のシスコシステムズ社が提供している。但し、スイッチの方が元来ルータよりも高速であることから、WAN 内部でもこのデータ配向機能の実行に際してスイッチ（スイッチ18に類似するもの）を使用することが広まってきている。大部分のLAN及びWANは、データを「パケット」と呼ばれる離散的塊で送信している。WANのルータ28は、データパケットの宛先を読み、このデータパケットを直接または間接的に宛先であるLANまたは他のコンピュータ装置へと方向付ける。先述のように、インターネットは世界で最も大規模な、最も良く知られた、また最もよく利用されているWANである。インターネットは、TCP／IPとして知られるプロトコルを利用してそのルータを通じてデータ伝送を行っている。従って、インターネットWAN16を通じて通信しようとするLAN12またはLAN14は、適当なTCP／IPプロトコルを使用しWAN接続30または32を通じてデータを送受信する必要がある。LAN及びその他異なるタイプの多数の装置は、汎用プロトコルを供給しインターネットを通じてデータ伝送を行うことにより、全世界的なWANを通じて互いに効果的に通信することができる。図1aは、先行技術による典型的なスイッチ18のブロック図である。スイッチ18 は、論理34と、受信バッファ36と、前方向テーブル38と、スパニング樹テーブル 40とを含んでいる。論理34は、42、44、46とラベリングされたバスを通じて、それぞれ受信バッファ36、前方向テーブル38及びスパニング樹テーブル40と通信する。当然のことながら、バス42−46は論理バスを示しており、物理的に同一の導線の幾つか、または全てを共用することができる。受信バッファ36は「n」個のポートを有し、典型的にはこれに０からｎ−１までが付番されている。こうしたポートの幾つかまたは全ては、ネットワークの媒体24に接続することができる。受信バッファ36のポートの１つ{O::ｎ−1}でデータを受信すると、論理34は前方向テーブル38（メモリに保存されている）を読み、そのデータをどのポートに前進させるべきかを決定する。例えば、ポート１で受信したデータは、前方向テーブル38によりポートｎ−２上の装置に向けて前進させるように決定が可能である。次いで論理34は受信バッファ36に、データをポート１からポートｎ−２へと前進させるように命令する。時として、特定ポートに於けるデータが、他の多数のポートへと向けられることがある。論理34はまた、これを前方向テーブル38から決定することができる。前方向テーブル38に特定のデータパケットの宛先が存在しない場合は、論理34は受信バッファにデータを全ポートから出すように命令し、宛先装置からの応答を待つ。スイッチの１ポート上で応答を受信すると、以後、スイッチの当該受信ポートをその装置に関連づけるように前方向テーブルが更新される。先述のように、コンピュータネットワークは多数のプロトコルを使用して通信する。世界最大のWANであるインターネットはTCP／IPプロトコルを使用して通信を行っているが、多くのLANは、ノベルIPXネットワークプロトコル、アップルトークプロトコル等の他のプロトコルを使用している。但し、プロトコルに関わらず、データは離散的塊または図1aのパケット48のような「パケット」で送信される傾向がある。パケット48は、宛先Ｄアドレスと、発生源Ｓアドレスと、送信されるデータであるDATAを含んでいる。データは一般に、ネットワークの媒体及び他の資源のより良き共用を促進するためにネットワーク上を「パケット」で送信される。スパニング樹テーブル40（やはりメモリに保存されている）は、ネットワークのトポロジーによる「樹木」構造の想定を保証している。当業者には周知であるように、樹木構造は、ネットワーク上に制御不能なパケットの重複を生成する可能性のあるループを含まない類のものである。従って、スパニング樹テーブルによるスイッチ18を有するネットワークは、最終的に規則的な樹木構造を形成するものと想定することができる。スパニング樹の規格は、規格802.IDのIEEE802.1 委員会によって規定されている。本規格はニューヨーク（ニューヨーク州）の電気電子学会（IEEE）で入手可能であり、参照用として本明細書に編入されている。先行する論議からも明らかであるように、ネットワークトポロジーは、急速に極めて複雑になる可能性がある。スイッチは、数個から何百個までのポートを有することができる。数個のポートしか保有していないスイッチは「ブリッジ」と呼ばれることが多く、多数のポートを有する場合は通常「スイッチ」または「スイッチングハブ」と呼ばれる。例えば数百のコンピュータシステムと、おそらくは１ダースのスイッチを有するLANの場合、可能な相互接続の数は何千にもなる。 LANを適正に管理及び／或いは診断するには、LANの様々な装置間に於ける実際の物理的相互接続を知る必要がある。媒体の物理的トレースは可能ではあるが、規模に関わらずLANにとってこれは膨大な作業である。代替として、ブラウン他による米国特許第5,226,120号は、自動的にLANのトポロジーを生成する方法を教示している。ブラウン他が提案した解法は、そのネットワークの各「ハブ」に特殊化されたソフトウェアを供給して制御卓に表示可能なトポロジー情報を提供しようというものであった。しかしながら、ブラウン他が開示した方法には、幾つか欠点がある。第１に、ハブには制御卓へトポロジー情報を供給するための特殊化されたソフトウェアを装備する必要がある。ハブはその中核である切換機能の実行に加えて計算タスクを供給しなければならないことから、これはハブの複雑さを増大させ、性能を低減させる。さらに、ブラウン他の解法では、各ハブがトポロジー収集プロトコルに同意する必要があり、これは単一のメーカーからのネットワーク装置しか使用できないことを意味している。単一のLANで多様なメーカーからの装置（スイッチ、ハブ、ブリッジ、ルータ等）を使用することのあるローカルエリアネットワークの不均一構造に於いては、これは不利である。発明の開示本発明は、ワイヤトレーシングを行なうことなく、また個々の装置上で特殊化されたトポロジーソフトウェアを実行する必要なしに不均一または均一装置によるネットワークのトポロジーを効果的に決定するための方法と装置を提供する。その結果、LANマネジャーまたはLANコンサルタントは、診断及びネットワークの最適化を目的としたローカルエリアネットワークのトポロジーを迅速に決定することができる。広義的には、コンピュータネットワークのトポロジーを決定する方法は、コンピュータネットワークの少なくとも１つのサブセットに於いて各装置からポート転送用データを読み取ることを含んでいる。次いでこのポート転送用データは、少なくともコンピュータネットワークの当該サブセットのトポロジーを派生させるために処理、解析される。好適には、ポート転送用データの読み取りに先だって少なくともコンピュータネットワークの当該サブセットに於ける全てのスイッチを発見し、後続解析のために利用可能な最大のポート転送データを供給する。さらに詳しく言えば、コンピュータネットワークの少なくとも当該サブセットに対応するアドレス領域内の装置アドレスを照会（即ち「ピンギング」）し、応答のための監視を行なうことにより、装置を全て発見する。応答する装置はそれぞれ、配置された装置タイプ（スイッチタイプまたはホストタイプ等）及び未知の装置タイプの内の１つとして分類される。装置に関する情報はサブネット装置リストに保存され、装置がスイッチであれば情報もまたサブネットスイッチリストに保存される。当業者には周知であるように、インターネットプロトコル（「IP」）の文脈に於いては、「サブネット」は同報通信ドメイン内部に於ける１つのアドレス群である。ノーべルIPXプロトコルの文脈では、同一の構造体（即ち本書に於いて「サブネット」として言及しているもの）が「ネットワーク」と呼ばれる。サブネット装置リストに於ける各装置の場合、装置の各ポートにそのポートに関連したアドレス及びマスクを伴ったポート目的が生成される。装置がスイッチタイプであれば、アドレスはそのスイッチタイプに関連している。さらに詳しく言えば、ネットワークが層３プロトコルで作動する場合、ポートに付随するアドレスは媒体アクセス制御（「MAC」）アドレスとプロトコルアドレスを含み、マスクはIPプロトコル特有のサブネットマスクを装備している。本発明の好適な方法は、帰納的関数を使用して合成ポート転送用データからトポロジーを生じさせる。さらに詳しく言えば、帰納的関数が装置を効果的に樹木構造に配置するため、スイッチの物理的相互接続を効率的に表示することができる。さらに本発明は、上述の方法を実行するための、コンピュータシステム用プログラム命令を含む媒体を読み取ることのできるコンピュータを含んでいる。さらに、本発明に従ってコンピュータネットワークのトポロジーを決定するための装置は、コンピュータシステムを使用して上述の方法を実行する。先述のように、本発明の優位点は、どんなタイプの装置を有するネットワークであっても作動し、ネットワークのトポロジーの展開に際して特殊化されたトポロジーソフトウェアを実行する装置を使用する必要がないことにある。例えば、ネットワークコンサルタントは、本発明の方法を実行する携帯式コンピュータを使用して任意タイプの装置を有するローカルエリアネットワークに（WANを通じて直接、または間接的に）接続ができ、また診断及び／或いは最適化目的でネットワークのトポロジーを効果的に展開することができる。本発明のこうした優位点及びその他の優位点は、以下の詳細な説明を読み、種々の図面を検討することにより明確になるであろう。図面の簡単な説明図１は、幾つかのローカルエリアネットワーク（LAN）とワイドエリアネットワーク（WAN）を含む先行技術によるコンピュータネットワークシステムの一例である。図1aは、ローカルエリアネットワークに使用する先行技術によるスイッチを示している。図２は、コンピュータネットワークのLANのトポロジーを決定するためにコンピュータネットワークに接続した本発明による装置を示している。図2aは、図２の装置のブロック図である。図３は、コンピュータネットワークのトポロジーを決定するための、本発明による工程の系統図である。図４は、図３の「切換されたLANに於けるスイッチを全て発見せよ」について示した工程系統図である。図５は、本発明の工程によって展開される装置ポインタリストとスイッチポインタリストを示している。図5a、5b及び5cは、それぞれ本発明の総称的ホスト目的、特定スイッチモジュール目的及び総称的スイッチモジュール目的の装置目的を示している。図６は、図３の「LANの各スイッチからポート転送用データを読み取ること」について示した工程系統図である。図6aは、図６の工程の動作説明に使用するものである。図７は、図３の「ポート転送用データから切換LANのトポロジーを派生させよ」について示した工程系統図である。図８は、図７の帰納的関数「PlaceInSubtree(サブツリー内に配置せよ)」の工程系統図である。図９は、図８の方法「isBelow」の工程系統図である。図10は、本発明の方法によって発見されるべきネットワークトポロジーの一例である。図11a及び11bは、図10のトポロジーの装置リストと走査リストである。図12a−12dは、図７の工程を使用した切換LANのトポロジーの逐次的展開を示している。図13は、図３のステップ「トポロジー情報を提供せよ」を示している。図14は、図13の関数「CreateMedia(媒体を生成せよ)」を示している。図15は、本発明の工程によって派生したトポロジー情報のディスプレイを示している。発明を実施するための最良の形態図１及び図1aについては、先行技術に関連して先に説明した。図２では、本発明による装置50が同報通信ドメインまたはLAN12の少なくとも一部またはそのサブセットのトポロジーを決定するために使用されている。装置50は、LAN12のトポロジーを決定するために52が示すように直接LAN12に結合することもできるが、やはりLAN12のトポロジーを展開するため52aが示すようにLAN14を通じて、或いは52bが示すようにWAN16を通じて間接的にLAN12に結合することもできる。図2aは、本発明の装置50のブロック図を示している。この図2aのブロック図は、本発明の方法を実施するプログラミング命令の制御下で本発明の望ましい機能性を実行する典型的なパーソナルコンピュータ（PC）を例示したものであることに留意しなければならない。この他にも、本発明による方法を実行可能なコンピュータ構成を使用することができる。図2aでは、本発明による装置50がマイクロプロセッサ54を含み、マイクロプロセッサ54がバス58によって高速メモリバス56に、またバス62によって入力／出力（I／O）バス60に結合されている。マイクロプロセッサ54としては、インテル「ｘ−86」互換性マイクロプロセッサ、モトローラのパワーPCマイクロプロセッサ、SPARCプロセッサ等一般に使用されている多数のマイクロプロセッサの内の何れをも使用することができる。マイクロプロセッサ54は「チップセット」として知られる特殊なチップ（図示していない）によって、メモリバス56及びI／Oバス 60に結合されている。このチップは、データの流れを制御し、またコンピュータ装置50内部で他の機能を実行する。ランダムアクセスメモリ（RAM）64と読み取り専用メモリ（ROM）66は、一般にメモリバス56に結合されている。見ての通り、RAM64はバス68によって、ROM66はバス70によってメモリバス56に結合されている。RAM64は一般に非持久メモリまたは「スクラッチパッド」メモリであるが、ROMは持久メモリであり、装置50の「ブーティング」開始命令を含むことが多い。 I／Oバス60には、多数の装置を結合することができる。こうした装置は、一般に「周辺」機器と呼ばれる。こうした周辺機器の例としては、フロッピードライブ72、CD ROMドライブ74、ハードディスクドライブ76、ネットワークカード78、その他総称的に80で示したI／Oインタフェース等がある。その各々が独自のバスでI／Oバス60に結合されている。即ち、周辺機器72、74、76、78、80は各々、バス82、84、86、88、90によってI／Oバス60に結合されている。フロッピードライブ72及びCD ROMドライブ74といった幾つかの周辺機器は、出し入れが可能なコンピュータ読み出し可能媒体を装備している。さらに詳しく言えば、フロッピードライブ72にはフロッピーディスク92の形式であるコンピュータ読み出し可能媒体が装備され、CD ROMドライブ74にはCD ROMディスク94の形式である取り外し式のコンピュータ読み出し可能媒体が装備される。ハードドライブ76は一般に出し入れする媒体を保有しない、即ちそのコンピュータ読み出し可能媒体はハードドライブ装置内部に固定されている。ネットワークカード78は装置50をコンピュータネットワークに結合するために使用される。例えば、ネットワークカード78はローカルエリアネットワーク12の媒体24に結合することができる。総称的I／Oインタフェース80は、例えばイーサネットカード、RS−232ポート等とすることができ、バス96によって外部装置に結合される。図面では、RAM64及びROM66といった従来型メモリが高速メモリバスに結合され、また「周辺機器」がI／Oバスに結合された形を示しているが、多くの最新式パーソナルコンピュータ構造では他のバスがサポートされる。また、メモリバス56 にはリアルタイムのビデオデータを扱う周辺機器のような高速の周辺機器を結合することができ、またI／Oバス60にはある種の拡張メモリを結合することができる。従って、図2aが示す構造は、本発明による装置50のための適正なハードウェアを例示したものであって、限定的なものではない。事実上本発明の装置50に於ける全ての装置が、何らかの形式のメモリ機能を提供することができる点に留意すべきである。RAM64、ROM66、フロッピードライブ 72、CD ROM74及びハードドライブ76は極く一般的な「メモリ装置」であり、ネットワークカード70及びI／Oインタフェース80のような他の周辺機器もまた、一般にマイクロプロセッサ50による直接または間接的アクセスが可能なバッファ及び他のメモリを含んでいる。さらに、メモリにはネットワークを通じてネットワークカード78から、またI／Oインタフェース80を介して他の装置からアクセスすることができる。従って、「メモリ」という用語は、本明細書に於いてはマイクロプロセッサ54による直接または間接的アクセスが可能な任意形式のデジタル記憶装置を意味している。同様に、「コンピュータ読み出し可能媒体」という表現は、本明細書ではメモリをサポートする任意の装置または媒体について言及する場合に使用している。従来のコンピュータ読み出し可能媒体には、フロッピーディスク92、CD ROM94、ハードドライブ76の内容、RAM64及びROM66が含まれる。但し、コンピュータ読み出し可能媒体はまた、ネットワークを通じてネットワークカード78により、或いはI／Oインタフェース80を通じて他の装置からアクセスすることができる。図３では、本発明による工程98が100で始まり、ステップ102で切換されたLAN の少なくとも１つのサブセットに於いて全てのスイッチを発見する。次にステップ104で、LANに於ける各スイッチからポート転送用データを読み取る。ステップ 106では、ポート転送用データから切換されたLANのトポロジーを派生し、ステップ108でトポロジー情報を提供する。次いで本行程は110で完了する。従って、広義的には、本発明に従ったコンピュータネットワークのトポロジーを決定するための方法は、コンピュータネットワークの少なくとも１つのサブセットに於ける各装置からポート転送用データを読み取ることを含んでいる。次にこのポート転送用データは、コンピュータネットワークの少なくとも当該サブセットのトポロジーを派生させるために処理され、解析される。好適には、ポート転送用データの読み取りは、コンピュータネットワークの少なくとも当該サブセットに於ける全スイッチを発見し、後続の解析のために利用可能な最大のポート転送用データを提供することにより促進する。この後、トポロジーは便宜的な任意形式による処理、表示が可能である。図４は、図３の工程102を詳細に示したものである。詳しく説明すると、工程1 02は112で始まり、114で反復ループが開始される。反復ループでは、カウンタi が０に初期化され、対象LAN（またはLANのサブセット）内部のアドレス数NUM ＿ADDRESSESと比較される。こうしたアドレスは一般に継続的に割り当てられ、オフセットアドレスOFFSETで開始される。カウンタiが処理対象アドレスの総数より下位である場合、ステップ116がADDRESS（OFFSET＋i）で装置を「ピング」する。「ピング」という用語は当業者には周知のものであり、指定されたアドレスにメッセージを送り(即ち装置のアドレスを「問合せ」)、応答を待つことを意味している。「時間切れ」期間までにステップ118によって返答または応答が検出されなければ、工程制御が反復ループ114にまで戻り、カウンタiが１で反復される。ステップ116のピングに対する応答がステップ118によって検出されると、次いでステップ120に於いてこれがMIB−II装置であるかどうかが決定される。MIB−I I装置は、当業者には周知の工業規格「単純ネットワーク管理プロトコル」または「SNMP」仕様に於いて定義されており、本明細書にも参照用として編入している。ステップ120がこれをMIB−II装置ではないとした場合、ステップ122が１ポートで未知の装置目的を生成し、IPアドレスをセーブする。ステップ120がそれをMIB−II装置であると決定した場合は、ステップ124がそのMIB−II装置が認識されたスイッチであるかどうかを決定する。この決定は、MIB−II目的に対しSNM P「要求を受容せよ」を生成することによって行われる。要求が成功すれば、その装置はMIB−IIをサポートしている。ステップ124がスイッチを認識すれば、ステップ126に於いて特定のスイッチモジュール目的が生成される。ステップ124がスイッチを認識しない場合は、装置が「ブリッジMIBグループ」をサポートするか否かについてステップ128が決定する。「ブリッジMIBグループ」もまた、「インターネット・エンジニアリング・タスクフォース（「IETF」）の注釈要求(RFC) 」によって定義されている。IETF RFCはまた、IPマスクとサブネットマスクについても定義している。装置が「ブリッジMIBグループ」をサポートしているとステップ128が決定すれば、ステップ132に於いて総称的スイッチモジュール目的が生成される。ステップ128が装置による「ブリッジMIBグループ」のサポートを決定しない場合は、ステップ130に於いて総称的ホスト目的が生成される。本発明はSNMPプロトコル及びMIB−II目的を使用しているが、他の管理プロトコルも使用可能である。例えば、同様の目的でCMIP、OSI管理プロトコルを使用することができる。OSIモデルとその関連プロトコルについては、例えば本明細書にも参照用として編入しているマーシャル・ローズ著「オープンブック(The Open Book)」に説明されている。ステップ122、126、130、132が完了すると、装置目的は、ステップ134に於いてサブネット装置リストに配置される。ステップ136は装置がスイッチであるか否かを決定し、スイッチであればこのスイッチがサブネットスイッチリストに入る。ステップ136がこの装置をスイッチでないと決定した場合、或いはステップ1 38の完了後は、工程制御が反復ループステップ114に戻り、カウンタiが反復される。カウンタがアドレス総数NUM＿ADDRESSESを全て進行し終えると、工程は140 の表示によって完了する。図５は、本発明による装置ポインタリスト及びスイッチポインタリストのデータ構成を示している。さらに詳しく言えば、装置ポインタリスト142が多数のポインタ144を含み、それがステップ102によって発見された「n」個の装置を指示している。同様に、スイッチポインタリスト146も多数のポインタ148を含み、それがステップ102によって発見されたスイッチを指示している。従って、装置ポインタリスト142は装置０から装置ｎ−１に及ぶ装置、即ち｛O::n−1｝を指示するエンドポインタを含むことになる。スイッチポインタリスト146は、装置が全てスイッチである場合以外は、装置ポインタリストよりも含む装置の数が少ない。この例では、装置０はスイッチでないことから、装置０は装置ポインタリストにあるが、スイッチポインタリストにはない。図5a、5b、5cは、各々本発明の方法102によって製造された装置目的150、152 、154を示している。図5aの装置目的150は総称的ホスト目的であり、総称的ホスト目的150によって象徴されるIPアドレス、MACアドレス、装置のタイプ、装置の名称及び装置のポート数を含んでいる。図5bの装置目的152は特定のスイッチモジュール目的であり、IPアドレス、MACアドレス、装置のタイプ、装置の名称、装置のポート数及び総称的方法を含んでいる。図5cの装置目的154は総称的スイッチモジュール目的であり、IPアドレス、MACアドレス、装置のタイプ、装置の名称、ポート数及び総称的方法を含んでいる。用語「IPアドレス」は前述の IETF RFCに於いて定義され、「MACアドレス」は前述のIEEE 802.1D規格に定義されている。当業者には周知の通り、ソフトウェア「目的」は、所定の属性を有しまた外部のコール及びパラメータに応答して指定された機能を実行するデータ及び方法（即ち特殊化されたソフトウェア手順）を含む構成物である。本発明に於いては、本発明の工程をスケーリング可能な方法でフレキシブル且つ強力に実行するために目的指向プログラミングを使用している。工程または方法102は、本明細書では交互に本発明の工程の「位相Ｉ」として記述している。位相Ｉの基本目標は、図５が示すような装置タイプのリストを構成することである。以下の表Ｉでは、疑似コードを使用して図４の工程を例示している。当業者には認識されるであろうが、疑似コードはＣ＋＋のような高レベル目的指向言語へと容易に翻訳が可能である。表１−位相Ｉ疑似コード（装置タイプリストの構成）ピングに応答する各IPアドレスに関して： MIB−II取得を試行せよ MIB−II装置でない場合１ポートで未知の装置を生成せよ。ポートでIPアドレスをセーブせよ。これ以外はMIB−II装置である MIB−IIシステムグループを読みとれスイッチタイプを認識した場合特定のスイッチモジュール目的を生成せよその他ブリッジMBグループをサポートしている場合総称的スイッチ目的を生成せよその他は総称的ホスト目的を生成せよサブネットの装置リストに装置を入れよそれがスイッチである場合は、やはりそれをサブネットのスイッチリストに入れよ従って、位相Ｉの終わりでは、サブネットの装置リストがサブネットのスイッチリストと同じく供給されることは明らかである。図６は、図３の工程104を詳細に示したものである。工程104は156で始まり、反復ループステップ158に於いてカウンタiが０に初期化される。次いでステップ 160に於いて、DEVICE（i）のポート数NUMPORTS（i）が取得される。次に反復ループステップ162に於いてカウンタjが０に初期化され、ステップ164でポートPOR TOBJECT（j）が生成される。次いでステップ166に於いてMACアドレス、IPアドレス及びサブネットマスクが取得され、OBJECT（j）に配置される。次いでステップ168が、DEVICE（i）がスイッチであるか否かを決定し、スイッチでなければ工程制御が反復ステップ168に戻ってカウンタjが反復される。 DEVICE（i）がスイッチである場合は、ステップ170がビジブルMACアドレスセットを取得する。「ビジブル」とは、発信テーブルがMACアドレスとそれが最終で見受けられたポートを含んでいることを意味している。MACアドレスがこのポートの発信テーブルにない場合は、この定義に於いてはそれがこのポートに関して「ビジブル」でない。次いでステップ172は、可能であればIPアドレスをMACアドレスに結合させる。どのサブネットに於いても、IPアドレスはただ１つのMAC アドレスとしか「結合」されない。その間の任意の時点で、システムは結合した MACアドレスを知ることなくIPアドレスを「知る」ことができ、またその逆も可能である。双方が知られていれば、当業者には明らかであるように「結合」ステップ172は簡単なタスクである。例えば、多くの装置がこの結合情報に関する問合せが可能なARPキャシュを含んでいる。工程制御は、カウンタjがNUMPORT（i）を下回るまで反復ステップ162に戻り、カウンタjがNUMPORT（i）を下回った時点で、Ａで示されるように工程制御が反復ループステップ168に戻る。カウンタjが NUM＿DEVに等しいとき、反復ループ158が励起され、174で示されるように工程10 4が完了する。図6Aは、工程104によって生成されるデータ構成を示している。工程104によって生成される装置目的176は、ポート数と装置のポートリストポインタを含んでいる。ポートリストポインタはポートリスト178を指示し、ポートリスト178はポート目的180を指示している。各ポートに関してポート目的180が１つ生成される。つまり、装置にｎ個のポートがあるとすると、｛O::n−1｝の範囲のポート目的が生成される。さらに、各々のポート目的が「ポートチャイルドリスト」18 2と「MACアドレス認識」リスト184とを指示する。ポートチャイルドリストは、図３の工程106によって埋められる。MACアドレス認識リスト184は、MAC番号とそのMAC番号に付随するIPアドレスを含んでいる。図6aの例では、MAC番号０はIPアドレスを伴っておらず、MACアドレス１はアドレス128.203.124.001を伴い、MAC アドレス２はIPアドレスを伴っていない。当業者には認識されるであろうが、サブネット装置リストに於ける各装置では、装置の各ポートに対してポート目的及びそのポートに付随するアドレス及びマスクが生成される。装置がスイッチタイプであれば、アドレスはそのスイッチタイプに関連している。さらに詳しく言えば、ネットワークが層３プロトコルで動作する場合、アドレスはポートに関連しまた媒体アクセス制御（「MAC」）とプロトコルアドレスを含み、マスクはIPのサブネットマスクを装備している。層３プロトコル（プロトコルアドレスを含む）は、IETF、ISO、ノベル社及びアップルコンピュータ社を含む様々な組織によって定義されている。例としては、IETF I P、ノベルのIPX及びアップル社のアップルトーク層３プロトコル等がある。本発明の工程104はまた、本明細書に於いては「位相II」としても言及しているが、本質的に切換されたLANの装置に関する詳細情報を収集する。以下の表II は、工程104をさらに疑似コードで例示している。この場合もやはり、当業者には、この疑似コードがＣ＋＋のような目的指向プログラミング言語に於いて実行可能であることは明らかであろう。表２−位相２疑似コード（装置に関する詳細情報の収集）サブネットに於ける各装置についてポート数を取得せよ各ポートについてポート目的を生成せよ各ポートについて MACアドレスを取得せよ IPアドレスを取得せよサブネットマスクを取得せよそれがスイッチである場合 MACアドレスのビジブルセットを取得せよ可能であればIPアドレスをMACに結合せよ位相IIの終わりでは、切換されたLANの全装置に関する詳細情報が収集されている。位相Ｉによって完全な装置リストが生成されていれば位相IIに於いて追加情報を派生させることができるため、このデータは、好適には位相Ｉとは異なるパスで完了される。図７では、図３の工程106が186で始まり、ステップ188で連結樹の任意根rが選択される。例えば、リスト上の最初の装置を根rとして、或いはリスト上の他の何れかの任意装置を根rとして選択することができる。次に、反復ループステップ190でカウンタosが０に初期化される。次いで、ステップ192でosが連結樹の根 rに等しいか否かが決定される。等しければ工程制御が反復ループ190に戻り、カウンタosが増分される。osがrでないときは、ステップ194に於いてスイッチosの帰納的関数PlaceInSubtree（os）が呼び出される。帰納的関数194は、後続の詳細説明の通り、スイッチを連結樹に適正に配置する。帰納的関数194が完了すると、工程制御は反復ステップ190に戻り、カウンタosが反復される。osがスイッチ数NUMSWITCHに等しければ196が示すように工程は完了する。図８では、筆写体関数「PlaceInSubtree」が198で入力され、ステップ200で変数pr及びpsが初期化される。変数prは電流スイッチがsを認識するポートである。変数psはsがこのスイッチを認識するポートである。次いで、関数isBelow202 が呼び出され、sがpcの下位であるか否かを決定する。但し、pcはprの子の１つである。関数isBelowについては図９を参照して詳述する。簡単に言えば、関数i sBe1ow202はsがpc（pcはprの子の１つである）より下位であれば「真」を返し、 sがpcの下位でなければ「偽」を返す。関数202が真を返す場合は、pcを保有するスイッチ上のパラメータsによってPlaceInSubtreeに対して再帰的呼び出しが行われる。次いで206に於ける表示の通り本工程が完了する。関数isBelowが偽を返す場合は、ステップ208がprの子であるポートpcrを獲得する。但し、sはpcr上で認識可能である。次いで、ステップ210で全てのポートが処理されたか否かが決定される。処理されていなければステップ212がpcrをpr の子として除外し、スイッチs上にパラメータswを送る関数PlaceInSubtreeに対して再帰的呼び出しが行われる。パラメータswは、pcrが結合されるスイッチである。関数呼び出し214が返されると、処理制御はステップ208に戻る。ステップ 210が全ポートの処理済みを決定すると、206に於ける表示の通り工程194は完了する。図９は、関数isBelow202を詳細に示したものである。関数isBelowは216で始まり、ステップ218に於いて変数sp及びstが初期化される。変数spは、ｐが結合されるスイッチである。変数stは、受信機ポートが結合されるスイッチである。次いで、ステップ220に於いてstが受信機ポート上でｐを認識するか否かが決定される。認識すれば、ステップ222の関数によって偽が返され、224に於いてこの工程は完了する。 stが受信機ポート上でｐを認識しない場合は、ステップ226が受信機ポートではないstのポートpcを獲得する。次いで、ステップ228によって全ポートが処理されたか否かが決定され、処理されていればステップ222で偽が返され、224に於いて本工程は完了する。全ポートの処理が完了していない場合、ステップ230はp c上でspがビジブルであるか否かを決定する。「ビジブル」とは先述の通りの意味で使用している。ビジブルでない場合、工程制御はステップ226に戻る。但し、ステップ230による決定の通りにspがpc上でビジブルであれば、ステップ232によって真が返され、224に於いて工程が完了する。結果的に関数222は、sがpcより下位であれば真を返し、sがpcより上位または同レベルであれば偽を返す。図10はネットワークトポロジーの簡単な例を示している。このネットワーク例には７つのスイッチ、即ちスイッチＲ、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆがある。各スイッチのポートには番号が付いている。例えば、スイッチＲは１、２、３と付番された３つのポートを有している。スイッチＡ、Ｂは１、２と付番されたポートを有し、スイッチＣ、Ｄ、Ｅ、Ｆは１と付番された単ポートを有している図11a及び11bは、本発明の位相Ｉ及びIIによって展開された装置リスト及び走査リストを示している。図11aの装置リストは、機器Ｒ、Ｆ、Ｃ、Ｄ、Ｂ、Ｅを含んでいる。図11bの走査リストは、変数スイッチの様々なポート上にどのスイッチが認識されるかを示している。このリストには、２桁の記号でスイッチとポートが表示されている。例えば、スイッチＲのポート１は「R1」である。従って、本例に於いてはR1がスイッチＡ及びＤを、R2がスイッチＢ、Ｅ及びＦを、R3がＣを、A1がＲを、A2がＤを、B1がＲを、B2がＥ及びＦを、C1がＲを、F1がＲ、Ｂ及びＥを、D1がＡ及びＲを認識する。後続説明の通り、こうしたリストは図10が示すようなネットワークのトポロジーを適正に生成するために、図７の工程106 によって使用される。図12aが示すように、装置は適宜シーケンス順に図11aの装置リストから読み取られる。まず、スイッチＲが樹木の根として配置される。次いで装置Ｆが選択され、ステップ106の方法によってスイッチＲのポート２の下位になるように樹木内に配置される。次に、装置リスト11aから装置Ｃが選択され、工程106によって R3に配置される。次いで、装置Ｄがリストから選択されR1に配置される。先の例からも明らかなように、走査リストは後続スイッチが根のどのポートで認識されるかを決定するために使用され、こうした後続スイッチが配置される。引き続き本例について説明すると、図12bでは図11aの装置リストから装置Ｄが選択され、工程106がＤをスイッチＡより下位であると決定し、そのようにスイッチＤを配置する。次いで図12cが示すように、図11aの装置リストからスイッチＢが選択され、工程106がＦをスイッチＢより下位であると決定し、そのように配置する。最後に、図12dのように、装置リスト11aから装置Ｅが選択され、工程10 6かＥをＢより下位であるがＦより下位でないと決定する。従って、装置Ｅ及びＦが同レベルでスイッチＢより下位に配置される。ステップ106は、先述のように本明細書では「位相III」としても言及されている。下記の表３は、位相III工程を表す疑似コードを示している。本質的に、この位相III工程は、交換LANのトポロジーの導出である。ポート方法isBelowも下記の表４に疑似コードで表されている。表３及び表４の疑似コードが簡単にＣ＋＋のような目的指向プログラミング言語に翻訳できることは当業者によって理解されるであろう。 LANのスイッチのスパンニング樹アルゴリズムはループを防止するため、ネットワークの実際のトポロジーが樹木構造であることは知られている。位相III方法の目的は、連結樹を得ることである。サイクルが無いため、どんなスイッチでもこの連結樹の根として機能することができる。樹木の枝はポート連結性によって限定される。各スイッチはその子と称される関連ポートセットを有している。子ポートは他のポートセットに結合され、次にはこれがスイッチに結合される。従ってスイッチは、間にポートを有する親／子階層と考えることができる。表３−位相III疑似コード（トポロジー導出）連結樹の根となるスイッチrを選択せよ他の各スイッチosについて、パラメータとしてosをパスする根の上にPlaceInSub treeを呼び出せ PlaceInSubtreeを、受信機が根である部分樹木にスイッチsを配置するスイッチクラス向けの方法とせよ prを当該スイッチがsを認識するポートとせよ psをsが当該スイッチを認識するポートとせよ sがpcより下位であり、pcがprの子の１つである場合 sをパラメータとしてパスするpcを有するスイッチ上にPlaceInSubtreeを呼び出せでなければ prの子であり、そのためsが-pcrでビジブルである各ポートpcrに関してはprの子としてpcrを除去せよ pcrの接続先であるスイッチswをパラメータとしてパスするスイッチs上にPlaceI nSubtreeを呼び出せ。表４ポート方法疑似コード isBelowを、ポートｐをパラメータとして受容するポートクラス向けの方法とする。本方法はｐの接続先であるスイッチが受信機ポートより下位のスイッチセットにある場合に真を返す。ｐの接続先であるスイッチをspとせよ受信機ポートの接続先であるスイッチをstとせよ stが受信機ポート上にｐを認識した場合は偽を返せそうでない場合、受信機ポートでないstの各ポートpcに関して、 spがpc上でビジブルであれば、真を返せその他は、偽を返せ図13は、図３の工程108を詳細に示したものである。工程108は234で始まり、ステップ236ではアップリンクがヌルに等しい根上でCreateMediaに対して関数呼び出しが行われる。この関数呼び出し236については、図14を参照して詳細に論じる。次いでステップ238は、ネットワークのトポロジーを更新し表示する。ステップ240はディスプレイ上のユーザー入力を検出し(即ちディスプレイは対話式である)、ユーザー入力に応答してステップ238で更新及び表示を行う。ユーザー入力は例えば、マウスまたは他のポインティング装置、或いはキーボードの命令によって行うことができる。図14では、図13の工程236が242で始まり、ステップ244でパラメータｕが受容される。反復ループのステップ246はカウンタiを０に初期化し、ステップ248では媒体目的Ｍが生成される。p＝uであれば、工程制御は反復ループのステップ24 6に戻り、カウンタiが反復される。ステップ250はpがuに等しくないことを決定し、ｐはステップ252で目的Ｍに加算され、ステップ254がｐの子pcを取得する。ステップ256が全ての子の処理済みを決定した場合、工程制御は反復ループのステップ246に戻りカウンタiが反復される。全ての子の処理が完了していないとステップ256が決定した場合は、ステップ258が目的Ｍにpcを加算する。次いで、工程制御はステップ254に戻る。iがNUMPORT（s）に等しいと反復ループのステップ 246が決定すると、ステップ260に於ける指示の通り工程が完了する。図15は、図13のステップ138によって作成が可能な１つのディスプレイを表している。無論、ネットワークトポロジーを表示する方法としては、他にも当業者には周知のものが多く存在する。このディスプレイでは、262に多くの媒体が表され、264に多くのポートが示されている。図15に示したディスプレイは、好適にはマウスまたは他のポインティング装置型システムで使用される対話式インタフェースである。この例では、媒体イーサネット０が選択されており、またp1ポートをイーサネット０媒体に接続する２つの点266により２つの装置のポートp1がイーサネット０に結合されて表されている。幾つかの好適な実施例に関連して本発明を説明してきたが、本発明の範囲内にある変更、置換及び等価物が存在する。また、本発明の工程及び装置の双方を実施するためには多くの代替方法があることにも留意すべきである。従って、以下のクレームは、本発明の真の精神と範囲内にある全ての変更、置換及び等価物を包含するものとして解釈されるべきものである。DETAILED DESCRIPTION OF THE INVENTION Method and apparatus for generating a network topology Technical field The present invention relates generally to computer network systems, and more particularly to computer network systems. Determines and displays interconnections between devices within a computer network system Method and apparatus. Background art In FIG. 1, a computer network system 10, which is an example of the prior art, has a 1 local area network (“LAN”) 12, second LAN 14, wide area network Network (“WAN”) 16. LAN (LAN12, 14 etc.) and WAN (WAN16 etc.) The distinction between is not always clear, but in general a LAN is inside a building or Used in relatively small geographic areas, such as inside small building groups, WANs For use in one local, state, national or sometimes globally large geographic area. Used. LAN and WAN are digital devices for data communication in networks Although both perform similar functions with respect to the interconnection of The configuration of the network and the equipment used tend to be somewhat different, as described below. As an example, referring to LAN 12 in FIG. 1, a LAN generally includes a plurality of “switches” 18. Each switch has a plurality of “ports” 20. Some of the ports or All are connected to other devices, such as other switches 18 and computers 22. Switch 18 (sometimes called a “bridge”) is a local area network 12 into separate areas or subsets of the local area network 12 A function to reduce data collisions on the interconnect medium 24 of the computer system. Work. This medium 24 (typically a twisted pair, coaxial cable or optical fiber ) Transmits data to only one network device at a time Cannot use the media at the specified position within a certain period of time. If this is attempted, a communication bottleneck results. Switch 18 Separate individual media 24 from each other media 24 of local area network 12 Ensure that data communication on one medium does not necessarily affect data communication on another medium By doing so, this problem is reduced. Switch 18 operates in a relatively simple manner in theory. Switch 18 is When one of the ports 20 detects data communication, the data is sent to any port (to any port). Decide if you want to proceed). For example, data found on a specific port Is for a device already coupled to that port (ie, the transmitting device And the receiving device are on the same medium 24). Unnecessary traffic on other media of the network because it is not Fick is removed. In another example, a switch is connected to a device coupled to a second port. When the switch receives the data on the first port, the switch transfers the data to the second port. Proceed to (switch). Therefore, the first port medium and the second port medium are connected. Only devices are affected by this data transfer. Switch 18 is the first port If you receive data and do not know which device to send it to, Switches generally send data out of all of their ports, wait for a response from the receiving device, Determine the port where the device is located. Next, data for the device will be The port number of the device is stored in the “table” so that it can be sent directly to the port. You. Large LANs can assume a “topology” with the complexity of unconsciousness. Wear. As used in this document, a "topology" is a computer network. Phase of various devices within the system 10, within the LAN, or within a subset of the LAN. It implies a relevant physical interconnection. The correct "domain" of the topology is general Although referred to as a LAN (or a subset of a LAN), the present invention does not The topology of any switch set that limits the ins can be determined. This As is well known to traders, a “broadcasting domain” is a broadcast address for that domain. This is a device set for receiving a data packet transmitted to the address. "Equipment" Is connected to the network and is unique at least within that part of the network A digital electronic device provided with a network address. Thus, for example, the device shown in LAN 12 is Contains. Of course, other devices are also used in computer network systems Is possible. Typically, one or more computers 22 are coupled to media 24, Coupled to one or more ports 20 of switch 18. Multiple controls on media 24 When the computers are connected, the medium is called a "shared medium." In some cases 1, as shown by the backbone 26 of FIG. 1, a "backbone" connection between the switches 18 ( That is, some media have been generated. The purpose of backbone 26 is to Provides ultra-high-speed communication between various switches in the rear network 12 to transfer large amounts of data It is to transfer at high speed. Switch 18 is very high speed, but in data communication These backbone 26 connections are useful because they create delay or “latency”. It is for. WAN16 is generally used to connect multiple LAN networks for data communication. used. The best known WAN is the so-called Internet. ), And thousands of computers and LANs are connected for data communication. Typically, WANs use other types of network equipment, known as routers 28. To transfer data from one LAN to another LAN. For Internet Most of the Cisco routers are provided by Cisco Systems, Inc. of San Jose, California. I am offering. However, since switches are inherently faster than routers, WAN A switch (similar to switch 18) is also used internally to perform this data orientation function. The use of is becoming widespread. Most LANs and WANs send data in discrete chunks called "packets". I have. The WAN router 28 reads the destination of the data packet, and Directly or indirectly direct to a destination LAN or other computing device . As mentioned earlier, the Internet is one of the largest, best-known Is the most commonly used WAN. The Internet is known as TCP / IP The data is transmitted through the router using the protocol. Therefore, LAN12 or LAN14 trying to communicate through Internet WAN16, Send and receive data over WAN connection 30 or 32 using the appropriate TCP / IP protocol Need to be LAN and many other devices of different types use generic protocols. Supply and transmit data through the Internet to create a global WAN Can communicate effectively with each other. FIG. 1a is a block diagram of a typical switch 18 according to the prior art. Switch 18 Is a logical 34, a receive buffer 36, a forward table 38, and a spanning tree table. Includes 40 and. Logic 34, through buses labeled 42, 44, 46, Communicate with the receive buffer 36, forward direction table 38 and spanning tree table 40, respectively. You. Of course, buses 42-46 represent logical buses, and are physically identical. Some or all of the lines can be shared. The reception buffer 36 has "n" It has ports, which are typically numbered from 0 to n-1. These Some or all of the ports may be connected to the network medium 24. When data is received on one of the ports {O :: n-1} of the receive buffer 36, the logic 34 Reads the direction table 38 (stored in memory) and assigns the data to any port Decide if you want to move forward. For example, data received on port 1 Table 38 allows a decision to be made toward the device on port n-2. You. Logic 34 then places the data in receive buffer 36 from port 1 to port n-2. Command to move forward. Sometimes, data at a particular port is directed to many other ports. There is. Logic 34 can also determine this from forward table 38. If there is no specific data packet destination in the forward direction table 38, the logic 34 Instructs the receive buffer to output data from all ports, and sends a response from the destination device. wait. When a response is received on one port of the switch, thereafter, the switch The forward direction table is updated to associate the port with the device. As mentioned earlier, computer networks communicate using a number of protocols. I do. The Internet, the world's largest WAN, communicates using the TCP / IP protocol But many LANs use the Novell IPX network protocol, Apple Other protocols, such as a work protocol. However, regardless of the protocol Data is sent in discrete chunks or “packets” such as packet 48 in FIG. Tend to be trusted. Packet 48 includes a destination D address, a source S address, Contains the data to be transmitted, DATA. Data is generally stored in network media. "Packets" on the network to promote better sharing of body and other resources Sent by The spanning tree table 40 (also stored in memory) It guarantees the assumption of the "tree" structure based on the above topology. Well known to those skilled in the art As such, tree structures can create uncontrolled packet duplication on the network. It does not contain any potential loops. Therefore, the spanning tree table The network with switches 18 according to the final form a regular tree structure Can be assumed. Standard of spanning tree is standard 802. IEEE802.ID 1 Stipulated by the Commission. This standard applies to New York (New York) Available at the Institute of Electrical and Electronics Engineers (IEEE) and incorporated herein by reference. . As is evident from the preceding discussion, the network topology is rapidly Can be quite complex. Switches can have several to hundreds of ports. can do. A switch that has only a few ports is called a “bridge” Often referred to as "switches" or "switches" when there are many ports. It is called "the switching hub". For example, hundreds of computer systems and maybe Can have thousands of possible interconnects for a LAN with a dozen switches . In order to properly manage and / or diagnose the LAN, it is necessary to implement Need to know the physical interconnection of Physical tracing of the media is possible, This is a huge task for LANs of any size. As an alternative, Brown et al. U.S. Pat. No. 5,226,120 teaches how to automatically generate LAN topologies. Is shown. The solution proposed by Brown et al. Is specific to each "hub" of the network. Provides specialized software to provide topological information that can be displayed on the control console It was like that. However, the method disclosed by Brown et al. Has several disadvantages. First, Hubs have specialized software to supply topology information to the control console. Must be equipped. Hubs perform computational tasks in addition to performing their core switching functions. This increases the complexity of the hub and reduces performance Decrease Let it. In addition, Brown et al.'S solution uses each hub as a topology collection protocol. Must agree, this is only for use with network equipment from a single manufacturer It means you can't. Devices (switches) from various manufacturers on a single LAN , Hubs, bridges, routers, etc.) This is disadvantageous in the non-uniform structure of the workpiece. Disclosure of the invention The present invention is specialized without wire tracing and on individual devices Non-uniform or uniform equipment without the need to run customized topology software Method and apparatus for effectively determining the topology of a network. As a result, the LAN manager or LAN consultant can Quickly determine local area network topology for optimization be able to. Broadly speaking, the method of determining the topology of a computer network is A port from each device in at least one subset of the computer network Including reading the data for transfer. Next, this port transfer data is Derive the topology of at least that subset of the computer network Is processed and analyzed. Preferably, prior to reading the port forwarding data At least all switches in that subset of the computer network. And provides the largest port forwarding data available for subsequent analysis. More specifically, at least a subset of the computer network (Ie, "pinging") the device address in the address area corresponding to All devices are discovered by monitoring for Each responding device Device type (switch type or host type, etc.) Classified as one of the device types. Device information can be found in the subnet device If the device is a switch, the information is also stored in the subnet switch list. Is stored in As is well known to those skilled in the art, Internet Protocol ("IP") In the context of), a "subnet" is an address within the broadcast domain. It is a dress group. In the context of the Nobel IPX protocol, the same structure (ie At (Referred to as a "subnet") is called a "network." For each device in the subnet device list, connect each port of the device to that port. A port purpose with an associated address and mask is created. Device is a switch If so, the address is associated with that switch type. Learn more In other words, if the network operates with a layer 3 protocol, the address associated with the port Address includes the media access control ("MAC") address and protocol address, The network is equipped with a subnet mask specific to the IP protocol. The preferred method of the present invention uses a recursive function to convert data Produces a porology. More specifically, recursive functions can be used to effectively The physical layout of the switches can be displayed efficiently because they are arranged in a structure. You. The invention further provides a computer system program for performing the above method. And a computer capable of reading a medium containing the program instructions. Further A device for determining the topology of a computer network according to the invention The apparatus performs the method described above using a computer system. As mentioned above, the advantage of the present invention is that the network with any type of device Work even with specialized topologies as the network topology evolves. In that it does not require the use of a device that executes the logic software. For example, The network consultant provides a portable computer for performing the method of the present invention. Use a local area network with any type of device (through WAN (Directly or indirectly) and for diagnostic and / or optimization purposes. Network topology can be deployed effectively. These and other advantages of the present invention can be obtained from a reading of the following detailed description. It will be clear from a review of the various drawings. BRIEF DESCRIPTION OF THE FIGURES Figure 1 shows some local area networks (LANs) and wide area networks Example of prior art computer network system including work (WAN) It is. FIG. 1a shows a prior art switch for use in a local area network. are doing. FIG. 2 is a schematic diagram of a computer network for determining the LAN topology. 1 shows a device according to the invention connected to a computer network. FIG. 2a is a block diagram of the device of FIG. FIG. 3 illustrates an embodiment of the invention for determining the topology of a computer network. FIG. Fig. 4 shows "Discover all switches in the switched LAN" in Fig. 3. It is the process flow chart shown. FIG. 5 shows a device pointer list and a switch pointer developed by the process of the present invention. Shows a business operator. FIGS. 5a, 5b and 5c respectively illustrate the generic host purpose, specific switch module of the present invention. 7 shows the device purpose for the rule purpose and the generic switch module purpose. Fig. 6 shows "Reading port transfer data from each LAN switch" in Fig. 3. FIG. FIG. 6A is used to explain the operation of the process of FIG. FIG. 7 derives the topology of the switching LAN from the data for port transfer shown in FIG. FIG. FIG. 8 is a diagram of the recursive function “PlaceInSubtree” shown in FIG. FIG. FIG. 9 is a process flow chart of the method “isBelow” of FIG. FIG. 10 shows an example of a network topology to be discovered by the method of the present invention. It is. 11a and 11b are a device list and a scan list of the topology of FIG. 12a-12d show the sequential evolution of the switched LAN topology using the process of FIG. are doing. FIG. 13 shows the step "provide topology information" of FIG. FIG. 14 shows the function “CreateMedia (create a medium)” of FIG. FIG. 15 shows a display of topology information derived by the process of the present invention. ing. BEST MODE FOR CARRYING OUT THE INVENTION 1 and 1a have been described above in relation to the prior art. In FIG. Device 50 is at least part of the broadcast domain or LAN 12 or its support. Used to determine the subset topology. The device 50 is a LAN12 Although it can be directly coupled to LAN12 as shown by 52 to determine the topology, Through LAN 14, as also indicated by 52a, to deploy the LAN 12 topology, or Alternatively, it can be indirectly coupled to the LAN 12 through the WAN 16 as shown by 52b. FIG. 2a shows a block diagram of the device 50 of the present invention. The block diagram in Figure 2a is Desired function of the invention under the control of programming instructions for implementing the method of the invention Exemplifies a typical personal computer (PC) that performs You have to keep in mind. In addition, a computer capable of performing the method according to the invention A computer configuration can be used. In FIG. 2a, the device 50 according to the invention comprises a microprocessor 54, Processor 54 is input / output via bus 58 to high-speed memory bus 56 and via bus 62 (I / O) is coupled to the bus 60. As the microprocessor 54, Intel " x-86 "compatible microprocessor, Motorola PowerPC microprocessor Of the many microprocessors commonly used, including SPARC processors They can also be used. Microprocessor 54 is a “chipset” Depending on the special chip (not shown) known, the memory bus 56 and the I / O bus Combined with 60. This chip controls the flow of data and Perform other functions inside the device 50. Random access memory (RAM) 64 and read-only memory (ROM) 66 It is coupled to a memory bus 56. As you can see, RAM 64 is by bus 68 and ROM 66 is It is coupled to the memory bus 56 by a bus 70. RAM64 is generally non-volatile memory. Or "scratch pad" memory, while ROM is non-volatile memory It often includes a "booting" start instruction. Many devices can be coupled to the I / O bus 60. These devices are generally Called "peripheral" devices. Examples of such peripherals include floppy dry 72, CD ROM drive 74, hard disk drive 76, network card 78, In addition, there is an I / O interface or the like generally indicated by 80. Each of them has its own bus To the I / O bus 60. That is, the peripheral devices 72, 74, 76, 78, 80 Buses 82, 84, 86, 88, 90 to the I / O bus 60. Some peripherals, such as the floppy drive 72 and CD ROM drive 74, are Equipped with readable computer readable media. Further words For example, the floppy drive 72 has a computer in the form of a floppy disk 92. The CD ROM drive 74 is equipped with a CD-ROM disk 94 format. And a removable computer readable medium. Hard dry Unit 76 generally does not have a medium to access, ie its computer readable The active medium is fixed inside the hard drive device. Network card 78 is Used to couple device 50 to a computer network. For example, net Work card 78 can be coupled to medium 24 of local area network 12 You. The generic I / O interface 80 is, for example, an Ethernet card, an RS-232 port. Or the like, and is coupled to an external device by a bus 96. In the drawing, conventional memories such as RAM64 and ROM66 are coupled to a high-speed memory bus. And "peripherals" are shown coupled to the I / O bus, but many modern Other buses are supported in the personal computer structure. Also, the memory bus 56 Combines high-speed peripherals such as those that handle real-time video data The I / O bus 60 can be combined with some kind of extended memory. You. Thus, the structure shown in FIG. 2a shows the proper hardware for the device 50 according to the invention. A is an example, and is not limiting. Virtually all of the devices in device 50 of the present invention provide some form of memory function. It should be noted that they can be provided. RAM64, ROM66, floppy drive 72, CD ROM 74 and hard drive 76 are very common "memory devices" Other peripherals such as a network card 70 and an I / O interface 80 Also, generally, a bus that can be directly or indirectly accessed by the microprocessor 50. Buffer and other memory. In addition, memory Access from network card 78 and other devices via I / O interface 80 Can be accessed. Thus, the term "memory" is used herein for Is any type of data that can be accessed directly or indirectly by the microprocessor 54. Digital storage device. Similarly, "computer readable media" Is used herein to refer to any device or medium that supports memory. Used when referring. Traditional computer readable media includes Includes oppey disk 92, CD ROM 94, contents of hard drive 76, RAM 64 and ROM 66 It is. However, computer readable media may also be accessed over a network. Network card 78 or from other devices through the I / O interface 80. Can be accessed. In FIG. 3, the process 98 according to the invention starts at 100 and the LAN switched at step 102. Find all switches in at least one subset of. Next, In step 104, port transfer data is read from each switch in the LAN. Steps In 106, the topology of the switched LAN is derived from the port forwarding data, and the Step 108 provides topology information. The process is then completed at 110. Therefore, broadly, the topology of a computer network according to the present invention The method for determining at least one sub-set of a computer network comprises: Reading data for port transfer from each device in the network. next This port transfer data is stored in at least the Is processed and analyzed to derive the topology of the unit. Preferably the port The reading of the transfer data is performed by at least the Discovers all switches in the network and the largest port available for subsequent analysis Facilitate by providing data for transfer. After this, the topology is a matter of convenience. Processing and display in any format are possible. FIG. 4 shows the step 102 of FIG. 3 in detail. To explain in detail, step 1 02 starts at 112 and the iteration loop starts at 114. In an iterative loop, the counter i Is initialized to 0 and the number of addresses in the target LAN (or a subset of LANs) NUM Compared with _ADDRESSES. These addresses are generally assigned on an ongoing basis, Start at offset address OFFSET. Counter i is the total number of addresses to be processed If lower, step 116 "pings" the device with ADDRESS (OFFSET + i) I do. The term "ping" is well known to those skilled in the art and Sends a message to the server (ie, "queries" the device address) and waits for a response. are doing. Reply or response detected by step 118 before "time out" period If not, the process control returns to the iteration loop 114 and the counter i is repeated at 1 You. When a response to the ping of step 116 is detected by step 118, In step 120 it is determined whether this is a MIB-II device. MIB-I I devices are based on the industry standard "Simple Network Management Protocol" or Is defined in the "SNMP" specification and is incorporated herein by reference. You. If step 120 determines that this is not a MIB-II device, step 122 Create unknown device objectives with port and save IP address. Step 120 is it If it is determined that the MIB-II device is a MIB-II device, step 124 To determine if the switch has been activated. This decision is based on SNM for MIB-II purposes. This is done by generating a P "Accept Request". If the request is successful, This device supports MIB-II. If step 124 recognizes the switch, At step 126 a particular switch module purpose is created. Step 124 If the switch does not recognize, the device supports "Bridge MIB Group" Step 128 determines whether or not. The Bridge MIB Group is also Internet Engineering Task Force ("IETF") Annotation Request (RFC) Is defined by The IETF RFC also addresses IP masks and subnet masks. Is defined. If the device supports "Bridge MIB Group", Once step 128 has been determined, the generic switch module purpose is Generated. Step 128 determines that the device supports the "Bridge MIB Group" If not, a generic host purpose is generated in step 130. Although the present invention uses the SNMP protocol and MIB-II purpose, other management Tocol can also be used. For example, use CMIP and OSI management protocols for similar purposes. Can be used. For details on the OSI model and related protocols, see The Open Book (The Book Open Book). Upon completion of steps 122, 126, 130, 132, the device objective is to go to step 134 Is placed in the subnet device list. Step 136 is if the device is a switch The switch is included in the subnet switch list. You. If step 136 determines that this device is not a switch, or step 1 After the completion of 38, the process control returns to the iteration loop step 114, and the counter i is repeated. You. When the counter has advanced through the total number of addresses NUM_ADDRESSES, the process proceeds to 140 Is completed by the display of. FIG. 5 shows the data of the device pointer list and the switch pointer list according to the present invention. 2 shows a data configuration. More specifically, the device pointer list 142 has a large number of pointers. Includes interface 144, which points to "n" devices found by step 102 are doing. Similarly, the switch pointer list 146 includes a large number of pointers 148, and This indicates the switch found by step 102. Therefore, the device Interlist 142 points to devices ranging from device 0 to device n-1, ie {O :: n-1}. End pointer. The switch pointer list 146 indicates that all devices are Unless the device is a switch, the number of devices included in the device pointer list is smaller. . In this example, device 0 is not a switch, so device 0 But not in the switch pointer list. 5a, 5b, 5c show apparatus objects 150, 152, respectively, produced by the method 102 of the present invention. , 154 are shown. The device purpose 150 in FIG. 5a is a generic host IP address, MAC address, device type, device Includes the name and port number of the device. The device purpose 152 in FIG. Module, IP address, MAC address, device type, device name, Includes device port numbers and generic methods. Device objective 154 in FIG. 5c is a generic switch. Switch module, IP address, MAC address, device type, device Includes names, port numbers and generic methods. The term "IP address" Defined in the IETF RFC, the `` MAC address '' is defined in IEEE 802. Defined in 1D standard Have been. As is well known to those skilled in the art, software "purpose" has a predetermined attribute and Data and methods that perform specified functions in response to calls and parameters of That is, a component including a specialized software procedure). In the present invention, To perform the process of the present invention flexibly and powerfully in a scalable manner Uses goal-oriented programming. Step or method 102 is herein alternatively referred to as “Phase I” of the inventive step. Has been described. The basic goal of Phase I consists of a list of device types as shown in FIG. It is to do. Table I below illustrates the steps of FIG. 4 using pseudo code. ing. As will be appreciated by those skilled in the art, pseudo-code is a high level code such as C ++. It can be easily translated into an object-oriented language. Table 1-Phase I pseudo code (Structure of device type list) For each IP address that responds to the ping: Try MIB-II If not a MIB-II device Create an unknown device with one port. Save the IP address on the port. Others are MIB-II devices Read MIB-II system group When the switch type is recognized Generate a specific switch module purpose Other When the bridge MB group is supported Generate Generic Switch Objective Others Generate Generic Host Objective Enter the device in the device list of the subnet If it is a switch, put it in the switch list for the subnet as well. Yo Therefore, at the end of Phase I, the device list for the subnet is Obviously it will be supplied as well as Chirist. FIG. 6 shows the step 104 of FIG. 3 in detail. Step 104 begins at 156, In an iterative loop step 158, a counter i is initialized to zero. Then step At 160, the number of ports NUMPORTS (i) of DEVICE (i) is obtained. Then repeat In step 162, the counter j is initialized to 0, and in step 164, the port POR TOBJECT (j) is generated. Next, in step 166, the MAC address and the IP address And the subnet mask are obtained and placed in OBJECT (j). Next, Step 168 determines whether or not DEVICE (i) is a switch. The control returns to the repetition step 168, and the counter j is repeated. If DEVICE (i) is a switch, step 170 is To get "Visible" means that the outgoing table contains the MAC address and the last Includes ports found in. The MAC address is If it is not in the outgoing table of the port, it is not defined in this definition for this port. Is not "visible". Step 172 then proceeds to assign the IP address to the MAC address if possible. Attach to the dress. In any subnet, the IP address is only one MAC Only "bound" to addresses. At any point during that time, the system has joined You can "know" your IP address without knowing the MAC address, and vice versa Noh. If both are known, the "coupling" step will be apparent to those skilled in the art. Step 172 is a simple task. For example, many devices have questions about this binding information. Includes ARP cache that can be matched. In the process control, the counter j is NUMPORT (i) Returns to the iteration step 162 until the value of the counter j falls below NUMPORT (i). Then, the process control returns to the iterative loop step 168 as indicated by A. Counter j When equal to NUM_DEV, the iterative loop 158 is excited and step 10 as shown at 174 4 is completed. FIG. 6A shows a data structure generated by the step 104. By step 104 The generated device purpose 176 includes the number of ports and the port list pointer of the device. In. The port list pointer points to port list 178, and port list 178 Indicating port purpose 180. One port purpose 180 is created for each port You. That is, if the device has n ports, the ports in the range of {O :: n−1} The purpose is generated. In addition, each port purpose is a "port child list". 2 and "MAC address recognition" list 184. The Port Child List is Filled in by step 106 in FIG. The MAC address recognition list 184 contains the MAC number and its Includes the IP address associated with the MAC number. In the example of FIG. MAC address 1 is 128. 203. 124. Accompanied by 001, MAC Address 2 does not have an IP address. As will be appreciated by those skilled in the art, for each device in the subnet device list, For each port of the device, the port purpose and the address and A disk is generated. If the device is a switch type, the address is Related to Ip. More specifically, the network operates on a layer 3 protocol. Address, the address is associated with the port, and the media access control ("MAC") and Includes the IP address, and the mask is equipped with the IP subnet mask. Layer 3 Protocols (including protocol addresses) are available from IETF, ISO, Novell and Apple It is defined by various organizations, including computer companies. For example, IETF I P, Novell's IPX, and Apple's AppleTalk Layer 3 protocol. Step 104 of the present invention is also referred to herein as "Phase II." But essentially collects detailed information about the switched LAN devices. Table II below Exemplifies step 104 in pseudo code. Again, in this case, Runs this pseudo code in an object-oriented programming language such as C ++. Clearly, it is possible. Table 2 Phase 2 pseudo code (Collect detailed information about the device) About each device in the subnet Get the number of ports Generate a port purpose for each port About each port Get MAC address Get an IP address Get Subnet Mask If it is a switch Get a visible set of MAC addresses Bind IP address to MAC if possible At the end of phase II, detailed information about all devices on the switched LAN is collected I have. Added in phase II if complete device list was generated by phase I This data is preferably different from phase I, since the information can be derived Completed with a pass. In FIG. 7, the process 106 of FIG. 3 starts at 186, and at step 188, an arbitrary root r of the connected tree is selected. Selected. For example, the first device on the list as the root, or another device on the list Any arbitrary device can be selected as the root r. Next, the iterative loop step In step 190, the counter os is initialized to zero. Then, in step 192, os is the root of the connected tree It is determined whether it is equal to r. If they are equal, the process control returns to the iterative loop 190, The counter os is incremented. If os is not r, switch os is turned on in step 194. The inductive function PlaceInSubtree (os) is called. The recursive function 194 is As described in detail, switches are properly arranged in the connection tree. Inductive function 194 is completed Then, the process control returns to the iteration step 190, and the counter os is repeated. os switches If the number of switches is equal to NUMSWITCH, the process is completed as indicated by 196. In FIG. 8, the cursive body function “PlaceInSubtree” is input at 198 and changed at step 200. The numbers pr and ps are initialized. The variable pr is the port where the current switch recognizes s . The variable ps is the port where s recognizes this switch. Then the function isBelow202 Is called to determine if s is subordinate to pc. Where pc is one of the children of pr It is. The function isBelow will be described in detail with reference to FIG. Simply put, the function i sBe1ow202 returns "true" if s is lower than pc (pc is one of the children of pr), Returns "false" if s is not lower than pc. If function 202 returns true, own pc Against PlaceInSubtree by parameter s on switch A recursive call is made. Next, as shown at 206, this step is completed. If function isBelow returns false, step 208 acquires port pcr, a child of pr I do. However, s can be recognized on pcr. Then, in step 210, all ports Is determined. If not, step 212 pr pcr To the function PlaceInSubtree that sends a parameter sw on switch s And a recursive call is made. The parameter sw is the switch to which pcr is coupled is there. Upon return of the function call 214, processing control returns to step 208. Steps If 210 determines that all ports have been processed, step 194 is completed as indicated at 206 I do. FIG. 9 shows the function isBelow202 in detail. The function isBelow starts at 216 Then, in step 218, the variables sp and st are initialized. The variable sp is the concatenation of p Switch. The variable st is the switch to which the receiver port is coupled. Next In step 220, it is determined whether st recognizes p on the receiver port. It is. If recognized, the function of step 222 returns false, and the The process is completed. If st does not recognize p on the receiver port, step 226 Not get st port pc. Next, all ports are processed in step 228. It is determined whether or not the processing has been performed. This step is completed. If all ports have not been processed, step 230 Determine if sp is visible on c. "Visible" means Used for taste. If not visible, process control returns to step 226. However If sp is visible on pc as determined by step 230, then go to step 232 Thus, true is returned and the process is completed at 224. As a result, s is pc Returns true if lower than, and returns false if s is higher or equal to pc. FIG. 10 shows a simple example of a network topology. This network example Has seven switches: switches R, A, B, C, D, E, and F. Each sui The switch ports are numbered. For example, switch R is numbered 1, 2, 3 It has three ports. Switches A and B connect ports numbered 1 and 2 And switches C, D, E, and F have single ports numbered 1 FIGS. 11a and 11b show the device list and scan developed by phases I and II of the present invention. 3 shows a review list. The device list in FIG. 11a shows devices R, F, C, D, B, and E. Contains. The scan list in Figure 11b shows which switches on the various ports of the variable switch Switch is recognized. This list contains switches and pointers with two-digit symbols. Is displayed. For example, port 1 of switch R is “R1”. Therefore In this example, R1 is switches A and D, R2 is switches B, E and F, and R3 is C, A1 is R, A2 is D, B1 is R, B2 is E and F, C1 is R, F1 is R, B And E, and D1 recognizes A and R. As explained later, such a list is shown in FIG. To properly generate the network topology as shown, step 106 in FIG. Used by As shown in FIG.12a, the devices are read from the device list of FIG.11a as appropriate in sequence. Can be First, the switch R is arranged as a tree root. Then device F is selected. The tree is set to be lower than port 2 of switch R by the method of step 106. Is placed within. Next, the device C is selected from the device list 11a, and Located in R3. Next, device D is selected from the list and placed at R1. As can be seen from the previous example, the scan list is Used to determine what will be recognized, such subsequent switches will be located. Continuing with the description of this example, in FIG. 12b, device D is selected from the device list in FIG. 11a. Step 106 determines that D is below switch A and so switches Position D. Then, as shown in FIG. 12c, switch B from the device list of FIG. Is selected, and step 106 determines that F is below switch B, and so is arranged. Place. Finally, the device E is selected from the device list 11a as shown in FIG. 6 or E is determined to be below B but not below F. Therefore, the devices E and F is arranged at the same level and below switch B. Step 106 is also referred to herein as "Phase III" as previously described. You. Table 3 below shows the pseudo code representing the Phase III step. In essence, this Phase III is the derivation of the switching LAN topology. Port method isBelow below This is shown in pseudo code in Table 4 above. The pseudo code in Tables 3 and 4 is easily converted to C + It is understood by those skilled in the art that it can be translated into an object-oriented programming language such as + Be done Will. LAN switch spanning tree algorithm to prevent loops, It is known that the actual topology of the network is a tree structure. Phase III The purpose of the law is to obtain a connected tree. Because there is no cycle, with any switch Can also function as the root of this connected tree. Tree branches are connected by port connectivity. Limited. Each switch has an associated set of ports called its children. The child port is coupled to another set of ports, which in turn is coupled to the switch. Thus, a switch can be thought of as a parent / child hierarchy with ports in between. Table 3-Phase III pseudo code (Derived topology) Select the switch r that is the root of the connected tree For each other switch os, PlaceInSub on the root that passes os as a parameter Call tree PlaceInSubtree, a switch that places a switch s in the subtree where the receiver is the root A way for the class Let pr be the port where the switch recognizes s Let ps be the port where s recognizes the switch s is lower than pc and pc is one of the children of pr Call PlaceInSubtree on switch with pc passing s as parameter Let If not a child of pr, so for each port pcr that s is visible with -pcr, a child of pr Remove pcr as PlaceI on the switch s that passes the switch sw to which pcr is connected as a parameter Call nSubtree. Table 4 Port method pseudo code isBelow is a method for a port class that accepts port p as a parameter and I do. In this method, the switch to which p is connected is a switch cell lower than the receiver port. Tsu Returns true if it is in the list. Let sp be the switch to which p is connected Let st be the switch to which the receiver port is connected If st recognizes p on the receiver port, return false Otherwise, for each port pc of st that is not a receiver port, If sp is visible on pc, return true Others return false FIG. 13 shows step 108 of FIG. 3 in detail. Step 108 begins at 234, In step 236, a function call is made to CreateMedia on the root where the uplink is equal to null. An extrusion is performed. This function call 236 will be discussed in detail with reference to FIG. I will. Step 238 then updates and displays the topology of the network. S Step 240 detects user input on the display (i.e., the display ), Update and display in step 238 in response to user input. user The input may be, for example, a mouse or other pointing device, or a keyboard command. Can be done by In FIG. 14, step 236 of FIG. 13 begins at 242 and at step 244 the parameter u is accepted. Is done. Step 246 of the iterative loop initializes counter i to 0, and step 248 Generates a media purpose M. If p = u, the process control proceeds to step 24 of the iterative loop. Returning to 6, the counter i is repeated. Step 250 determines that p is not equal to u Then, p is added to the objective M in step 252, and step 254 obtains a child pc of p. If step 256 determines that all children have been processed, process control returns to the iteration loop. Returning to step 246, the counter i is repeated. If all child processes have not been completed, If step 256 is determined, step 258 adds pc to destination M. Then, The control returns to step 254. If i is equal to NUMPORT (s), steps in the iterative loop When 246 is determined, the process is completed as instructed in step 260. FIG. 15 illustrates one display that can be created by step 138 of FIG. ing. Of course, other ways to view the network topology There are many well-known ones. This display shows many media on 262 Sa And 264 shows many ports. The display shown in FIG. Is an interactive interface used in mouse or other pointing device type systems. Ace. In this example, medium Ethernet 0 is selected and p1 port The two points 266 connecting the ports to the Ethernet 0 medium connect the ports p1 of the two devices. It is shown coupled to Ethernet 0. Although the invention has been described with reference to certain preferred embodiments, it is within the scope of the invention. Certain modifications, permutations, and equivalents exist. In addition, both the process and the apparatus of the present invention are implemented. It should also be noted that there are many alternatives to do. Therefore, The following claims are intended to cover all modifications, permutations, and equivalents that fall within the true spirit and scope of the invention. It is to be interpreted as including.

───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.⁷ 識別記号ＦＩテーマコート゛(参考）Ｈ０４Ｌ 12/56 12/66 (72)発明者マクニールトーマスＧアメリカ合衆国ユタ州94097 オレム、 1072ノース1000イースト (72)発明者ヤンフイアメリカ合衆国ユタ州94103 ソルトレークシティー、835イーストファーストストリートＢ４番──────────────────────────────────────────────────続き Continued on the front page (51) Int.Cl. ⁷ Identification FI FI Theme Court ゛ (Reference) H04L 12/56 12/66 (72) Inventor McNeill Thomas G United States 94097 Orem, Utah United States 1072 North 1000 East (72 Inventor Jan Huy 94103 Salt Lake City, Utah USA 835 East First Street B4

Claims

[Claims] 1. A method for determining the topology of a computer network. From each switch in at least one subset of the computer network. Reading the data for port transfer, and reading the data for port transfer from the computer. Deriving the topology of at least one said subset of the network , How to configure. 2. Each switch in at least said subset of the computer network Before reading the port forwarding data from the 2. The method of claim 1, further comprising: finding all switches in the subset. A method for determining a topology of a computer network according to claim 1. 3. Make sure that all switches have been discovered by at least Inquires the device address within the address range corresponding to the unit and monitors the response. And for each device address that responded, the device at that address Categorized as one of switch type, host type and unknown device type Determining the topology of the computer network of claim 2 comprising: Method to determine. 4. The above switch type is for switch module purpose and generic switch module The host type is represented by one of the purposes, and the host type is represented by a generic host purpose. 4. Determine the topology of the computer network of claim 3, expressed as Way to. 5. For each device address that responded from the device, enter it in the subnet device list. Information about the device, and if the device is a switch type, Store information about the switch type in the net switch list; A method for determining a topology of a computer network according to claim 4. 6. Reading of port data is performed for each device in the subnet device list. To create a port purpose for each port of the device and for each port the port The address and mask associated with the port and the device is a switch type 6. The computer network of claim 5, including associating the address with the address, if any. To A method for determining the topology of a work. 7. The network operates according to the Layer 3 protocol, and the The dorse includes a MAC address and a protocol address, and the mask includes a subnet. 7. The computer network topology of claim 6, comprising a network mask. The way to decide. 8. The layer 3 protocol is a TCP / IP protocol and the protocol address is I 8. The computer network topology according to claim 7, which is a P address. The way to decide. 9. The MAC address whose association with the address is visible at the port Get the set and, if possible, make the IP address of the port visible 3. The computer network of claim 2, further comprising: A method for determining the topology of a network. 10. Claim that the derivation of the topology of at least one subnet includes a recursive function Item 3. A method for determining a topology of a computer network according to Item 1. 11. The contractor wherein the recursive function includes placing a switch-type device in a tree structure. A method for determining a topology of a computer network according to claim 10. 12. To determine the topology of the computer network, Containing program instructions for a computer system coupled to the A computer readable medium, wherein at least one of the computer networks Read port forwarding data from each switch in one subset For computer systems coupled to a computer network RAM instructions and the port transfer data to at least a computer network. Said computer system for deriving a topology of said one subset as well. The computer-readable medium comprising: a computer program instruction. 13. Each switch in at least said subset of the computer network Before reading port forwarding data from the Is also a program instruction for finding all switches in the subset. A computer readable medium comprising the program instructions of claim 12 comprising . 14. The program instructions for discovering all switches are executed on a computer network. Device address within the address range corresponding to at least the subset of Querying for responses, monitoring responses, and for each device address that responded The device at the address, switch type, host type and unknown device type. 14. The program instructions of claim 13, including categorizing as one of the types. A computer-readable medium including: 15.The switch type includes switch module purpose and generic switch purpose. 15. The program of claim 14, wherein the host type includes a generic host purpose. Computer readable media containing ram instructions. 16.For each device address returned from the device, enter the subnet device list. Program instructions exist for storing information about the device at the device. If the switch is a switch type, the switch 16. The method of claim 15, wherein there are program instructions for storing information about the type. A computer readable medium containing the program instructions. 17. The program instruction for reading port data is transmitted from the subnet device. For each device in the list, create a port purpose for each port of the device, Obtain the address and mask associated with the port for the port, and 17.The method according to claim 16, comprising associating the address with the address if the location is a switch type. A computer-readable medium containing the described program instructions. 18. The network operates according to the TCP / IP protocol and is associated with each port The address includes a MAC address and an IP address, and the mask includes a subnet. Computer-readable instructions comprising the program instructions of claim 17, comprising a computer mask. Possible medium. 19. The program instruction for associating the address at the port Obtain a set of visible MAC addresses and, if possible, the port Combining said IP address with said MAC address that is visible. A computer readable medium containing the program instructions of 3. 20. The program for deriving at least one subset of the topology A computer comprising program instructions according to claim 12, wherein the program instructions comprise recursive functions. Ta Readable media. 21. The program instructions for the recursive function place the switch-type device in a tree structure 21. A computer readable program comprising the program instructions of claim 20, comprising: Possible medium. 22. A method for determining the topology of a computer network. From each switch in at least one subset of the computer network Reading the port transfer data; and Deriving the topology of at least one said subset of the computer network And a step for producing. 23. Each switch in at least said subset of the computer network Before reading port forwarding data from the Also comprises a step for finding all switches in the subset. 23. A method for determining a topology of a computer network according to claim 22. Method. 24. The above steps for discovering all switches are Device address within the address range corresponding to at least the subset of For querying and monitoring responses, and the addresses of each device that responded Regarding the device at the address, switch type, host type and unknown Categorizing as one of the following device types: A method for determining the topology of the described computer network. 25. The switch types include switch module purpose and generic switch purpose The computer of claim 24, wherein the host type includes a generic host purpose. A method for determining the topology of a network. 26. For each device address responded by the device, enter it in the subnet device list. There is a step for storing information about the device in the If it is a switch type, the switch type in the subnet switch list 26. The computer of claim 25, wherein there is a step for storing information to be performed. A method for determining the topology of a network. 27. Read the port data for each device in the subnet device list. I Generating a port purpose for each port of the device; Obtaining an address and a mask associated with the port for If the device is a switch type, a step for associating with said address. 27. A method for determining a topology of a computer network according to claim 26, comprising: Method. 28. The network operates according to the TCP / IP protocol and is associated with each port The address includes a MAC address and an IP address, and the mask is a subnet mask. Determining the topology of the computer network of claim 27, including Way to. 29. The step of associating the address is Obtaining a set of MAC addresses, For binding the IP address of the router to the MAC address that is visible Determining the topology of the computer network of claim 23, comprising: Way for. 30. Said steps for deriving the topology of at least one subset 23. The computer of claim 22, wherein said step comprises performing said recursive function. To determine the topology of a data network. . 31. The steps for performing an inductive function tree switch type device 31. The computer network topologies of claim 30, comprising the steps of: Method for determining the logic. 32.A device for determining the topology of a computer network. From each switch in at least one subset of the computer network Means for reading the data for port transfer; Deriving the topology of at least one of said subsets of the computer network And means for causing the device to comprise. 33. Each switch in at least said subset of the computer network Before reading port forwarding data from the Further comprising means for discovering all switches in said subset, An apparatus for determining a topology of a computer network according to claim 32. Place. 34. If the means for discovering all switches is a computer network At least in the address range corresponding to the subset, the device address is checked. To monitor the response, and for each device address that responded The device at the address, switch type, host type and unknown device type. Means for categorizing as one of the types. A device for determining the topology of a computer network. 35.The switch type includes switch module purpose and generic switch purpose. 35. The computer of claim 34, wherein the host type comprises a generic host purpose. A device for determining the topology of a network. 36. For each device address that responded from the device, enter it in the subnet device list. Means for storing information about the device, wherein the device is a switch. If it is a type, it refers to the switch type in the subnet switch list 36. The computer network of claim 35, wherein there is a means for storing information. A device for determining the topology of a network. 37. Reading the port data is performed for each device in the subnet device list. Means for generating a port purpose for each port of said device; Means for obtaining an address and a mask associated with said port. Means for associating with the address if it is a switch type. 36. The apparatus for determining a topology of a computer network according to 36. 38. The network operates according to the TCP / IP protocol and is associated with each port The address includes a MAC address and an IP address, and the mask is a subnet mask. Determining the topology of the computer network according to claim 37, comprising: Equipment for 39. The means for associating the address is visible at the port. Means for obtaining a set of MAC addresses and, if possible, the IP of said port Means for binding an address to said MAC address that is visible. Apparatus for determining a topology of a computer network according to claim 33. . 40. The means for deriving at least one subset of the topologies may be 33. The computer network of claim 32, comprising said means for performing a recursive function. A device for determining the topology of a network. 41. Said means for performing an inductive function deploys a switch-type device in a tree structure. 41. The topology of a computer network according to claim 40, comprising means for placing A device for determining. 42. A device for determining the topology of a computer network. A central processing unit; a program instruction memory coupled to the central processing unit; A data memory for port transfer coupled to the central processing unit, and coupled to the central processing unit I / O port, the central processing unit, and the program instruction memory. Switch port reader with program instructions Switch to port forwarding data in at least one subset of the network. The port transfer data to the port transfer data memory. Connect to the computer network through the I / O port for storage Switch port reading device, the central processing unit, and the program. Data analyzer program instructions for port transfer stored in the Using the port transfer data stored in the port transfer data memory. Derive the topology of at least said subset of the computer network A data analyzer for port transfer.