Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
JP3315404B2 - ネットワークのトポロジ的特徴を探知する方法 - Google Patents
[go: Go Back, main page]

JP3315404B2 - ネットワークのトポロジ的特徴を探知する方法 - Google Patents

ネットワークのトポロジ的特徴を探知する方法

Info

Publication number
JP3315404B2
JP3315404B2 JP51580191A JP51580191A JP3315404B2 JP 3315404 B2 JP3315404 B2 JP 3315404B2 JP 51580191 A JP51580191 A JP 51580191A JP 51580191 A JP51580191 A JP 51580191A JP 3315404 B2 JP3315404 B2 JP 3315404B2
Authority
JP
Japan
Prior art keywords
sub
network
traffic
networks
subnetwork
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Lifetime
Application number
JP51580191A
Other languages
English (en)
Other versions
JPH05502566A (ja
Inventor
ファール，ピーター
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
HP Inc
Agilent Technologies Inc
Original Assignee
Agilent Technologies Inc
Hewlett Packard Co
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from EP90310699A external-priority patent/EP0477448B1/en
Application filed by Agilent Technologies Inc, Hewlett Packard Co filed Critical Agilent Technologies Inc
Publication of JPH05502566A publication Critical patent/JPH05502566A/ja
Application granted granted Critical
Publication of JP3315404B2 publication Critical patent/JP3315404B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L43/00—Arrangements for monitoring or testing data switching networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H04L45/04—Interdomain routing, e.g. hierarchical routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/42—Centralised routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/46—Cluster building
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/70—Routing based on monitoring results
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L43/00—Arrangements for monitoring or testing data switching networks
    • H04L43/08—Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
    • H04L43/0823—Errors, e.g. transmission errors
    • H04L43/0847—Transmission error

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Seats For Vehicles (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Description

【発明の詳細な説明】 本発明は、複数のサブネットワーク、サブネットワー
クを相互に接続する架橋装置（spanning device）、及
びネットワークに対してトラフィックを発信し及び／ま
たは着信するステーションとを有する形式のネットワー
クのトポロジ的特徴を探知する方法に関するものであ
り、トラフィックは各々が発信元（source）及び着信先
（destination）の情報を含む離散的なメッセージパケ
ットの形をしている。
前述の形式のネットワークは周知であり、その架橋装
置は局所的なトラフィック（すなわち、同じネットワー
ク上のステーションから発信されて着信するトラフィッ
ク）を少くとも或る程度当該サブネットワークに隔離す
る働きをする。このようなネットワークの例には次のも
のがある。
（ａ）イーサネット（Ethernet）アドレスにより識別さ
れるステーションが７層OSI参照モデルのレベル２で動
作するブリッジの形態の架橋装置により相互に接続され
ているサブネットワーク（論理セグメントとも言う）に
接続されているブリッジ接続されたイーサネット、及び （ｂ）「ip」アドレスで識別されるステーションが７層
OSI参照モデルのレベル３で動作するルータまたはゲー
トウェイの形の架橋装置により相互に接続されている
「ip」サブネットワークに接続されているインターネッ
ト（Internet）ネットワーク。
このようなネットワークのトポロジ的特徴（例えば、
サブネットワークへのステーションの接続構成及び架橋
装置によるサブネットワークの相互接続）の知識は、ネ
ットワークの性能をモニタし最適化する際に、また増大
する要求に対応するようその拡張を計画する際に重要な
ものである。しかし、このような知識を得るのは、特に
大規模ネットワークの場合には、困難なことがよくあ
る。例えば、加えられた変更をすべて記録することによ
りネットワークの最新の図面を保持しておくのは時間が
かかるばかりでなく、実際には、完全に正確に行うのが
ほとんど不可能な作業でもある。これに加えて、このよ
うな図面はそのネットワークの意図されている接続状態
を示すことができるだけであり、ステーションをサブネ
ットワークから単に切り離すようなネットワーク要素の
故障を考慮に入れることができない。ネットワークを物
理的に検査してそのトポロジを探知することも、ネット
ワークの多くの部分が床下に隠されていたりまたは遠隔
地に設置されていることがあるので、非常に困難であ
る。
一つだけのサブネットワークから構成されているネッ
トワークの場合には、単にサブネットワーク上のトラフ
ィックをモニタするだけでどのステーションがサブネッ
トワークに接続されているかを探知することが可能であ
る。サブネットワークの外側にはトラフィックの発信元
となるものは他にないので、トラフィックの発信元とな
るステーションは皆明らかにこのサブネットワークに接
続されているのである。しかし、ネットワークが架橋装
置により相互に接続されている数個のサブネットワーク
から成る場合には、或る一つの特定のサブネットワーク
に現われるトラフィックは他のサブネットワークで発生
していることがあるので、このような簡単な推論を行う
ことはもはや不可能である。
複数のサブネットワークから成るネットワークのトポ
ロジ的特徴を探知する比較的簡単な方法を提供するのが
本発明の目的である。
本発明によれば、前述の形式のネットワークのトポロ
ジ的特徴を探知する方法であって、 前述のサブネットワークの少くとも幾つかの上のトラ
フィックをモニタして、そのようにモニタしたトラフィ
ックの少くとも量及び発生元に関するデータを得るステ
ップと、 前述のデータを処理してネットワークの選択されたト
ポロジ的特徴を求めるステップと を設けたことを特徴とする。
モニタステップは該当する各サブネットワークにある
モニタリング装置を使用する。このような装置はそれ自
身独立した装置でもよいし、ま、サブネットワークに接
続されている架橋装置の一部またはステーションでもよ
い。各モニタリング装置は、サブネットワーク上のトラ
フィックに関して発信元及び着信先の双方の情報を集め
るように動作するのが望ましく、次いでこの情報を使用
して部分トラフィックマトリクス、すなわち関連するサ
ブネットワーク上に現われるトラフィックについての発
信ステーションと着信ステーションとの間の相関を作
る。それ故、好適には、モニタステップにより処理ステ
ップに送られるデータは関連するすべてのサブネットワ
ークに付いての部分トラフィックマトリクスの形をして
いる。しかし、処理ステップは、どんなトポロジ的特徴
を探知しようとするかにより、このような部分トラフィ
ックマトリクスに含まれるデータの必らずしもすべてを
必要としないことがあり、それ故本発明を必要なデータ
を部分トラフィックマトリクスの形で処理ステップに提
供することに限定して解釈すべきではないということを
理解すべきである。
各メッセージパケットに入っている発信元情報は一般
に発信ステーションを指示するだけであるが、あるネッ
トワークでは、サブネットワークの識別も発信元情報で
行われる。前者の場合には、本発明の方法を使用してど
のサブネットワークにある選択されたステーションが接
続されているかを探知することができる。これは前述の
モニタステップに、前述の各サブネットワークによって
運ばれる前述の選択されたステーションから発せられる
トラフィックの量を判定させ、前述の処理ステップは前
述の選択されたステーションからの大部分のトラフィッ
クを運ぶザフネットワークを判定し、このサブネットワ
ークを前述の選択されたステーションが接続されている
ものとすることにより達成される。このプロセスを各ス
テーションについて繰返してステーションとサブネット
ワークの接続の完全な描写を作り上げることができる。
本発明の方法は、第１のサブネットワークが架橋装置
により直接第２のサブネットワークに接続されているか
否かを探知するのにも使用することができる。これは、
第１のサブネットワークで発生したトラフィックの構成
要素の幾つかまたは全部について、第２のサブネットワ
ークに現われるそのトラフィックの量を他のすべてのサ
ブネットワーク（すなわち、第１及び第２のサブネット
ワーク以外の）に現われるそのトラフィックの量と比較
することにより行われる。特に、架橋装置を試験する三
つの異なる方法が提供されている。
第１のサブネットワークと第２のサブネットワークと
の間の架橋装置を試験する第１の方法においては、 −前述の方法は、メッセージパケットに入っている前述
の発信元情報を、前述の第１のサブネットワークから発
信されたメッセージパケットを識別するのに使用するこ
とができるようにする関連付け情報を発生するステップ
を含んでおり、 −前述のモニタステップは、前述の第２のサブネットワ
ーク上の、及び前述の第１及び第２のサブネットワーク
以外の前述のすべてのサブネットワークから成るサブネ
ットワークグループ中の各サブネットワーク上のトラフ
ィックをモニタし、これにより、前述の関連付け情報を
使用して、前述の第２のサブネットワーク及び前述のサ
ブネットワークグループ中のサブネットワークにより運
ばれる前述の第１のサブネットワークから発信されたト
ラフィックの量に関するデータを得ることを含んでお
り、 −前述の処理ステップは、前述のデータを使用し、前述
の第２のサブネットワークによって運ばれたところの第
１のサブネットワークから発せられたトラフィックの量
と前述のサブネットワークグループ中のグループにより
運ばれたところの前述の第１のサブネットワークから発
せられたトラフィックをまとめた量を比較するよう動作
し、これらトラフィックの量の内の多い方が前述の第２
のサブネットワークによって運ばれていたとき、処理ス
テップは、架橋装置が直接第１のサブネットワークを第
２のサブネットワークに接続していると判定する。
第１のサブネットワークと第２のサブネットワークと
の間の架橋装置を試験する第２の方法においては、 −前述の方法は、 （ａ）メッセージパケットに入っている前述の発信元情
報を前述の第１のサブネットワークから発生されたメッ
セージパケットを識別するのに使用することができるよ
うにし、また （ｂ）メッセージパケットに入っている前述の着信先情
報を、前述の第２のサブネットワーク以外の着信先を有
するメッセージパケットを識別するのに使用することが
できるようにする 関連付け情報を発生するステップを含んでおり、 −前述のモニタステップは、前述の第２のサブネットワ
ーク上、及び前述の第１及び第２のサブネットワーク以
外のすべてのサブネットワークから構成されているサブ
ネットワークグループ中の各サブネットワーク上のトラ
フィックをモニタし、これにより、前述の関連付け情報
を使用して、前述の第１のサブネットワークから発せら
れ且つ前述の第２のサブネットワーク以外に着信先を有
するトラフィックの内で、前述の第２のサブネットワー
クにより運ばれるトラフィックの量及び及び前述のサブ
ネットワークグループ中のサブネットワークにより運ば
れているトラフィックの量に関するデータを得ることを
含んでおり、 −前述の処理ステップは、前述のデータを使用して、前
述の第１のサブネットワークから発せられ且つ前述の第
２のサブネットワーク以外に着信先を有する前述のトラ
フィックの内で、それぞれ前述の第２のサブネットワー
クによって運ばれたトラフィックの量と前述のサブネッ
トワークのグループにより運ばれたトラフィックをまと
めた量とを比較するよう動作し、処理ステップは、これ
らトラフィックの量の内の多い方の量が前述の第２のサ
ブネットにより運ばれたものであるとき、架橋装置が直
接第１のサブネットワークを第２のサブネットワークに
連結していると判定する。
第１のサブネットワークと第２のサブネットワークと
の間の架橋装置を試験する方法の第３のものは、ネット
ワークに使用されている架橋装置が、接続されているサ
ブネットワークに着信先を有するメッセージパケットが
架橋装置を通過してこのサブネットワークから他のサブ
ネットワークに行くのを阻止するよう完全には働かない
場合に適用できる。架橋装置を試験するこの第３の方法
では、 −前述の方法は、 （ａ）メッセージパケットに入っている前述の発信元情
報を、前述の第１のサブネットワークから発されたメッ
セージパケットを識別するのに使用することができるよ
うにし、また （ｂ）メッセージパケットに入っている前述の着信先情
報を、前述の第１のサブネットワークに着信先を有する
メッセージパケットを識別するのに使用することができ
るようにする、 関連付け情報を発生するステップを含んでおり、 −前述のモニタステップは、前述の第２のサブネットワ
ーク上のトラフィック、及び前述の第１及び第２のサブ
ネットワーク以外のすべての前述のサブネットワークか
ら構成されるサブネットワークグループ中の各サブネッ
トワーク上のトラフィックをモニタし、これにより、前
述の関連付け情報を使用して、前述の第１のサブネット
ワークから発せられ且つ前述の第１のサブネットワーク
上に着信先を有するトラフィックの内で、前述の第２の
サブネットワークによって運ばれたトラフィックの量及
び前述のサブネットワークのグループにより運ばれたト
ラフィックをまとめた量に関するデータを得ることを含
み、 −前述の処理ステップは、前述のデータを使用して、前
述の第１のサブネットワークから発せられ且つ前述の第
１のサブネットワークに着信先を有するトラフィックの
内で、それぞれ前述の第２のサブネットワークによって
運ばれたトラフィックの量と前述のサブネットワークグ
ループにより運ばれたトラフィックをまとめた量を比較
するよう動作し、この処理ステップは、これらトラフィ
ックの量の内の多いほうが前述の第２のサブネットワー
クにより運ばれていたとき架橋装置が直接第１のサブネ
ットワークを第２のサブネットワークに接続していると
判定する。
架橋装置を試験する前述の三つの方法はすべて、存在
している架橋装置を見つけ出すことができないことがあ
るという点でその動作が慎重である（conservative）
が、しかし存在していない架橋装置を見つけ出すことが
ないという点では安全でもある。
架橋装置を試験する三つの方法すべてが必要とする関
連付け情報は、ステーションをサブネットワークに関連
付ける。各メッセージパケットに入っている発信元情報
が発信元サブネットワークの表示を本質的に提供する場
合には、関連付け情報は単に或る予め定められた方式に
従って発信元情報を正しく解釈するのに必要なものであ
る。その他の場合では、先ずステーションとサブネット
ワークとの間のその場限りの関連を（例えば、上に述べ
た本発明の方法に従って）決定して前述の関連付け情報
として記録しなければならない。
架橋装置を試験する三つの方法すべてにおいて、処理
ステップで、前述の第１のサブネットワークから発せら
れるトラフィックのうちで前述のサブネットワークのグ
ループ全体で運ばれたものの妥当な量は幾つかの異なる
方法で獲得することができる。例えば、前述のグループ
中の各サブネットワークについて対応するトラフィック
量を、グループ中の複数のサブネットワークで同じメッ
セージパケットがモニタされた結果起こることがある重
複に関係なしに加え合せることによりこれを獲得するこ
とができる。代りに、この獲得は −前述のグループ中の各サブネットワークについて、前
述の第１のサブネットワークから発せられるサブネット
ワークトラフィックのうちで、そのサブネットワークに
着信する要素と前述の第２のサブネットワークに着信す
る要素を判定し、 −前述のグループ中のすべてのサブネットワークについ
てそのように決定されたサブネットトラフィックの要素
を加え合わせる ことにより行うことができる。
架橋装置を試験する前述の三つの方法のどれでも、サ
ブネットワーク上の発信ステーションに無関係に（すな
わち、すべてのステーションをまとめて）、あるいは各
ステーションを別々に取り上げて、第１のサブネットワ
ーク上のそのステーションから発せられるトラフィック
について試験を行うことにより、行うことができる。
更に、双方向の架橋装置を使用する場合には（すなわ
ち、架橋装置が接続されているサブネットワーク間で両
方向にトラフィックを流すことができる場合には）、第
１のサブネットワークと第２のサブネットワークとの間
の架橋装置についての各試験を第１のネットワークから
発せられるトラフィックについてばかりでなく、他の前
述のサブネットワークから発せられるトラフィックにつ
いても行うことができる。
勿論、同じ組のサブネットワークの間の架橋装置に関
する試験のため、架橋装置を試験する三つの方法すべて
を連続して使用することが可能である（肯定的結果が得
られたらいつでも試験を中止する）。架橋装置を試験す
る前述の方法を考慮の対象のネットワーク中のサブネッ
トワークの各対またはその一部分に適用することによ
り、どのサブネットワークが架橋装置により接続されて
いるかを判定し、これによりネットワークトポロジの完
全な描写を作り上げることができる。
本発明の好適実施例においては、各サブネットワーク
に関するトラフィック情報は、サンプルしたデータを中
央処理ステーションに送り返すサンプリングモニタリン
グ装置により局所的に集められる。処理ステーションは
モニタされているサブネットワークすべてについての部
分トラフィックマトリクスを得、トラフィックマトリク
スに含まれているデータを本発明の方法に従って処理す
る。この処理を行うにあたり、処理ステーションは提示
されたデータのサンプルした性質に照らして仮説試験を
行ってトラフィックの流れを比較する。
本発明の方法を実施する際に使用するのに好適なサン
プリングモニタリング装置は、1990年９月28日に出願さ
れた同時係属中の我々のヨーロッパ特許出願第9031069
9.5号に説明され特許請求されている。
ネットワークのトポロジ的特徴を獲得する処理ステー
ションにより使用される部分トラフィックマトリクス
は、勿論、例えば、これら部分トラフィックマトリクス
それ自身を獲得し記憶させ、次いで部分トラフィックマ
トリクスを集め、処理ステーションに伝えるモニタリン
グ装置によるような他の方法で得ることができる。
ネットワークのトポロジ的特徴を探知する本発明によ
る方法は添付の図式的図面を参照して非限定的な例を使
うことによりこれから説明される。ここに置いて、 図１は処理ステーションと多数のサンプリングを行な
うモニタリング装置が接続されて本発明の方法を実現す
るネットワークモニタリングシステムを形成するネット
ワークの全体図。
図２は図１のネットワーク上で送信されるデータパケ
ットの一般的な形態を説明する図。
図３は図１のサンプリングを行なうモニタリング装置
のブロック図。
図４は図３の装置の制御マイクロプロセッサによって
実行される主割込サービスルーチンを説明するフローチ
ャート。
図５はサンプリングを行なうモニタリング装置からの
データを処理するに当たって図１の処理ステーションに
よって使用される主データ構造を説明する図。
図６は図１のネットワークのサブネットワークについ
ての部分トラフィックマトリクスの例を示す。
図７は処理ステーションによって実行される主プログ
ラムを説明するフローチャート。
図８はサンプリングを行なうモニタリング装置からの
データを受け取ったとき、部分トラフィックマトリクス
を構築するために処理ステーションによって実行される
割込サービスルーチンを説明するフローチャート。
図９は図７のプログラムによって呼ばれ、ステーショ
ンと図１のネットワークのサブネットワークとの間の関
連付けを判定する「ステーション割当」ルーチンを説明
するフローチャート。
図10AはサブネットワークＸとＹがブリッジによって
接続されている場合の、ネットワーク中で起こり得るト
ラフィックの流れを説明する図。
図10Bは図10Aと同様であるが、どのブリッジもサブネ
ットワークＸとＹを相互接続していない場合についての
図。
図11はどのブリッジもサブネットワークＸとＹを相互
接続していない場合に、起こり得るサブネットワークＹ
からの漏れトラフィックを説明する図。
図12は図７のプログラムによって呼ばれて、サブネッ
トワークのどの対がブリッジによって相互接続されてい
るかを判定する「ブリッジ試験」を説明するフローチャ
ート。
図13は図12のルーチンによって呼ばれる「第１のブリ
ッジ試験」サブルーチンを説明するフローチャート。
図14は地点トラフィックマトリクスの導出を説明する
フローチャート。
図１は、複数のステーション11、12、及び13がケーブ
ルセグメント10A、10B、及び10Cにより相互に接続され
ている典型的なローカルエリアネットワークを示す。こ
のネットワークは、ケーブルセグメント10B、10Cのそれ
ぞれの一つをケーブルセグメント10Aに接続するブリッ
ジ（架橋装置）により三つのサブネットワークに分割さ
れている。当業者が周知のように、ブリッジはネットワ
ークのセグメントとセグメントの間を通るトラフィック
をフィルタリングする働きをするので、特定のセグメン
トから発信され同じセグメント上のステーションに宛て
られたメッセージ（局所的なトラフィック）は、一つま
たは複数のブリッジ14を通って他のセグメントに行くこ
とはないが、あるセグメントで発生し他のセグメントに
宛てられたメッセージ（非局所的なトラフィック）はブ
リッジを渡ることができる。このようなブリッジの動作
は一般に不完全であり、通常、或る局所的なトラフィッ
クはブリッジを通して「漏れ出す」こともある。
図示したローカルエリアネットワークでは、ステーシ
ョン11、12、及び13の間のメッセージはネットワーク全
体にわたって放送されるパケットの形で伝えられる。典
型的にはパケットは図２に示す形態をとり、発信元アド
レス（パケットを送出するステーションのアドレス）及
び着信先アドレス（パケットを受信させようとするステ
ーションのアドレス）を備えているパケットヘッダ15
と、受信ステーションに送られるべきデータを備え且つ
通常はエラーチェックコードを含んでいる情報フィール
ド16とを備えている。使用する特定のパケットのフォー
マットによっては他のフィールドも存在することがあ
る。従って、例えば、パケットヘッダ及び情報フィール
ドの両者をカバーするCRC（巡回冗長検査）フィールド
が存在することがある。
図１のネットワークは、例えば、当業者には周知のイ
ーサネットのネットワークでよい。
図１のネットワークは、複数のモニタリング装置（ス
テーション12）及び中央処理ステーション13から成るネ
ットワークモニタシステムによりモニタされるように構
成されている。各モニタリング装置はネットワークのサ
ブネットワークのそれぞれの一つに関連付けられてい
る。以下で明らかになるように、各モニタリング装置
は、それに関連付けられているサブネットワーク上のパ
ケットをランダムにサンプルし、サンプルしたパケット
のデータを処理及び分析のため処理ステーション13に送
り返すように動作する。
各モニタリング装置の形態を図３に示す。この装置に
は、ネットワークインターフェース20、マイクロプロセ
ッサ21、及びROM（不揮発性で予めプログラムされてい
るメモリ）ユニット及びRAM（書き換え可能メモリ）ユ
ニット22及び23が設けられている。これらユニット20な
いし23はすべて、アドレスバス27、データバス28、及び
制御バス29により相互に接続されている。ネットワーク
インターフェース20は、図３のモニタリング装置をネッ
トワークケーブル10に接続し、受信したパケットをRAM2
3の中にあるFIFO（先入れ先出し）バッファ25で形成さ
れた受信待行列に伝えるのに必要な低レベル機能のすべ
てを行うように動作する。ネットワークインターフェー
スは更に、RAM23のFIFOバッファ26により形成される送
信待行列に保持されているパケットを伝送するよう動作
する。ネットワークインターフェース20はこのようにし
てモニタリング装置用のパケット受信手段及びパケット
送信手段を構成している。提示した例では、ネットワー
クインターフェース20はパケットヘッダに含まれている
着信先アドレスに無関係にすべてのパケットを受信する
ように構成されている。更に、ネットワークインターフ
ェース20は、受信した各パケットのヘッダ部分30のみを
受信FIFOバッファ25に送るように動作する。
ネットワークインターフェース20は、マイクロプロセ
ッサコントローラ21と協同して動作するよう構成されて
おり、特に、パケットヘッダが受信FIFOバッファ25に挿
入される毎に、適切な割込制御信号によってマイクロプ
ロセッサ21に知らせる。
ネットワークインターフェース20は、受信したパケッ
トの全個数、CRCフィールドに従えばエラー状態である
受信パケットの個数、最小許容長より短い受信パケット
（RUNTパケット）の個数、及び最大許容長より長い受信
パケット（JABBER）の個数を含む多くのカウンタを保持
する各種カウンタ24をも備えている。
特定のネットワークプロトコルについてのネットワー
クインターフェースの実施例は当業者には周知である。
従って、例えば、イーサネットネットワークについて、
ネットワークインターフェース20をIntel Corporation
のチップ82502、82501、及び82586で構成することがで
き、この場合にはマイクロプロセッサ21を構成する適切
なマイクロプロセッサはIntelプロセッサ80186である。
ROM22はマイクロプロセッサ21により実行されるプロ
グラム及び指数分布に従ってあらかじめ決められている
ランダムな計数値の表を保持している。
プロセッサ21は、プロセッサが何も実行しないバック
グラウンドプログラム（すなわち遊びプログラム）を実
行するよう動作する。プロセッサ21の主作業プログラム
は、ネットワークインターフェース20がプロセッサ割込
みを発生してプロセッサに受信FIFO25に新しいパケット
ヘッダを格納したことを告げる毎に呼出される割込サー
ビスルーチン（ISR）である。割込サービスルーチン
は、以下に更に詳細に説明することにするが、受信パケ
ットヘッダをランダムに選択してこれをカウンタ24の現
在の計数値と一緒にして収集データパケットを形成する
よう動作する。受信パケットヘッダのランダムな選択は
ROM22に格納されている予め定められたランダムな計数
値を利用して行われる。このように形成された収集デー
タパケットは送信待行列FIFO26に置かれ、やがてネット
ワークインターフェース20により処理ステーション13に
送り返される。各収集データパケットのヘッダには、そ
の発信元アドレスとしては関連するモニタリング装置の
アドレスが入っており、着信先アドレスは処理ステーシ
ョンのアドレスである（こうする代りに、処理ステーシ
ョンが聴き耳を立てる（listen）ように設定されている
マルチキャストアドレスを使用することができる）。
モニタリング装置の動作の更に詳細な説明を、マイク
ロプロセッサ21が実行する割込サービスルーチンのフロ
ーチャートである図４を参照して行うことにする。マイ
クロプロセッサ21は、そのバックグラウンド（遊び）プ
ログラムを実行しており且つ内部レジスタにランダムな
計数値の一つを保持している状態にあるものとする（モ
ニタリング装置のスイッチを入れたときに第１の計数値
を取出すことは初期設定ルーチンの一部としてもよ
い）。また受信及び送信のFIFOバッファ25及び26は空で
あると仮定する。
ネットワークケーブル10からバケットを受取ると、ネ
ットワークインターフェース20はパケットヘッダを受信
FIFOバッファ25に送り、そのカウンタ24を更新し、マイ
クロプロセッサ21に対して割込信号を発生する。この割
込を受取ると、マイクロプロセッサ21は図４に示した割
込サービスルーチンを実行する。このルーチンの最初の
ステップ40はバックグラウンドプログラムの揮発性環境
パラメータを保存しまたそれ以上の割込をマスクするこ
とを含むこのようなルーチンに関連する通常のハウスキ
ーピング作業を行う。
次に、マイクロプロセッサは、その内部レジスタに保
持されているランダムな計数値をデクリメントし（ステ
ップ41）、残った値をチェックしてこれが０まで減少し
ているか確かめる（ステップ42）。
計数値がなお０より大きければ、マイクロプロセッサ
21は受信FIFOバッファ25に入っているヘッドエントリを
捨てる（ステップ43）。
その後、マイクロプロセッサは、受信FIFOバッファ25
をチェックして、割込サービスルーチンに先行するいく
つかのステップの間にネットワークインターフェース20
により更に別のパケットヘッダがバッファに入れられた
か確認しなければならない（ステップ44）。一般にこの
ようにはなっておらず、マイクロプロセッサはその割込
サービスルーチンから出てそのバックグラウンド環境を
回復し、自分の割込のマスクを解除する（ステップ4
5）。しかし、受信FIFOバッファ25に更に別のパケット
ヘッダが入っている場合には、割込サービスルーチンは
ステップ44からステップ41に戻る。
マイクロプロセッサ21が自分の内部レジスタに保持さ
れている計数値について試験を行った際に（ステップ4
2）この計数値が０まで減っていることを見つけると、
割込サービスルーチンは受信FIFOバッファ25の最上部に
あるパケットヘッダに関して収集データパケット31を発
生することに進む（ステップ46）。この収集データパケ
ット31は送信FIFOバッファ26で受信パケットヘッダ30、
カウント24からの計数値、モニタリング装置のアドレス
（収集データバケットについての発信元アドレス）、及
び処理ステーションのアドレス（収集データパケットヘ
ッダについての着信先アドレス）から組立てられる。収
集データパケットが組立てられてから、マイクロプロセ
ッサ21はネットワークインターフェース20に合図して送
信準備が整っているパケットが存在していることを指示
する。（ネットワークインターフェース20は、それがで
きるようになったときまたできるときにそのパケットを
送信し、それが行われてしまえば、マイクロプロセッサ
21によってセットされたフラグを取り消す。） 割込サービスルーチンのステップ46を完了してから、
マイクロプロセッサはROM22から新しいランダムな計数
値を取出し、この新しいランダムな計数値をその内部レ
ジスタに格納する（ステップ47）。マイクロプロセッサ
は次にステップ44に進み、割込サービスルーチンの実行
が前述のとおり進行する。
受信及び送信FIFOバッファ25及び26の大きさは極めて
小さくすることができ、例えば、わずか二つか三つのエ
ントリを保持するのに充分な大きさにすることができ
る。受信バッファ25に関してこのようにすることができ
るのは、一般にネットワークインターフェース20により
受信されるパケット間の間隔はマイクロプロセッサ21が
その割込サービスルーチンを実行し受信バッファから最
上部エントリを取除くのに充分であるからである。とも
あれ、受信バッファ25が時折あふれても、パケットが欠
けてもネットワークモニタシステムにより行われている
統計的測定には一般にほとんど影響がないので重大な結
果をもたらさない。このことはあふれが更に発生しそう
もない送信バッファ26にも同等に適用される。それは、
送信バッファのエントリが受信パケットのうちからラン
ダムに選択したものに関するものだけだからであるから
である。
モニタリング装置の上述の実現形態は、収集データパ
ケットに入っているカウンタ24からの計数値が、関連す
るパケットがネットワークインターフェースにより実際
に受信されたときの時点での計数値ではないことがあり
得る（これはパケットヘッダを実際に処理する際に起こ
りうる遅れのためである）ことを意味する。しかし、こ
こにおいても、この点についての違いはもしあっても極
めて小さく、ネットワークモニタシステムにより生ずる
統計的に決まる結果の妥当性にはほとんど影響しない。
勿論、カウンタ24に存在する計数値を受信した各パケッ
トのヘッダと関連づける回路を設計することは可能であ
ろう。しかし、これを行うのに必要とされる回路の複雑
さは一般には正当とはされない。
RAM23の受信及び送信FIFOバッファ25及び26を実現す
るのに使用されるデータ構造は当業者には明らかであ
り、それ故ここでは説明しないことにする。更に、図３
の実施例では着信パケットのランダムな選択は予め定め
られた乱数をROAM22に格納することにより行われている
が、こうする代わりに、これら乱数をプロセッサ21が必
要とする際に発生することができる（ただしこれはプロ
セッサについての余分な必要条件をマイクロプロセッサ
に課すので好ましくない）ことがわかるだろう。典型的
には、この乱数はパケットを一つ選択しては平均99個抜
かすようにさせるようなものである。トラフィックの密
度、サンプリング周期、及び統計的誤差の許容レベルに
より他の値が一層適切なことがある。パケットのランダ
ムな選択は受信したパケットの数ではなく時間に基いて
行うことができる。
モニタリング装置12によりネットワークを通して送出
される収集データパケットはすべて、これらパケットを
格納し、続いて処理及び分析を行う処理ステーション13
により受信される。
処理ステーション13は、例えば、ネットワークを図３
のモニタリング装置12のインターフェース20と同様のネ
ットワークインターフェース（図示せず）により接続す
る標準のワークステーションにより構成されている。こ
のようなワークステーションは、作業データ及びプログ
ラム部分を格納するRAMメモリ、プログラムを永続的に
格納するROMメモリ、RAMメモリに保持されているデータ
をプログラムに従って処理するプロセッサ、及び各種入
出力装置を用いて標準的な仕方で行われる。これら要素
はすべて標準であり当業者には周知であるからここでは
図示もしないし説明もしない。
処理ステーション13は三つの主要な作業を行う。すな
わち、 （１）−受取った収集データパケットに基き各サブネッ
トワークについてトラフィックマトリクスを発生する。
（２）−サブネットワークトラフィックマトリクスを使
用してステーション11を各種サブネットワークと関係づ
ける。
（３）−サブネットワークトラフィックマトリクスを使
用してサブネットワークのすべての対の間のブリッジの
有無を試験する。
これらの作業を行うにあたり処理ステーション13が採
用する主データ構造を図５に図示してあり、このデータ
構造はステーション13のRAMメモリ上で作られ、保持さ
れる。主データ構造は次のとおりである。
入力待行列50−これはステーションのネットワークイン
ターフェースが必要とする収集データパケットの待行列
であり、各パケットは処理を待つ間待行列に一時的に保
持される。
サブネットワークリスト51−これはネットワークの既
知のすべてのサブネットワークのリストであり、各サブ
ネットワークは、サブネットワーク識別情報（identit
y）SN−ID、第１のポインタTM−POINTER、及び第２のポ
インタＳ−POINTERを格納するフィールドを設けたそれ
ぞれのエントリを備えている。
ステーションリスト52−これはネットワークのすべて
の既知のステーション11のリストであり、各ステーショ
ンはステーション識別情報Ｓ−ID及びポインタNEXT−S
POINTERを格納するフィールドを設けたそれぞれのエン
トリを備えている。特定のサブネットワークに関連付け
ようとする第１のステーションは、サブネットワークリ
スト51にある対応するサブネットワークエントリのＳ−
POINTERをステーションリスト52の適切なステーション
エントリを指すようにセットすることによりそのサブネ
ットワークと関係づけられる。更に別のステーションを
同じサブネットワークと関係づけることは、そのサブネ
ットワークに関係付けられている直前のステーションの
NEXT−S POINTERを使用して、このサブネットワークに
関連付けられるべき次のステーションのエントリを指し
示させ、以ってステーションの連結リストを作り上げる
ことにより達成される。
サブネットワークトラフィックマトリクス53−これは
各サブネットワークについて形成された配列であり、そ
のサブネットワークについての部分トラフィックマトリ
クスデータを保持する。サブネットワークに関するトラ
フィックマトリクスアレイはサブネットワークリスト51
中の対応するエントリのポインタTM−POINTERにより指
し示される。図６は各発信元ステーション／着信先ステ
ーション対について所与の時間間隔で関連するサブネッ
トワークによって運ばれるパケットの個数を示す典型的
な部分トラフィックマトリクスである（異なるステーシ
ョン11をここでは11A、11B、11C、……11Nと名付けてあ
る）。
ブリッジリスト54−これはネットワークのすべての既
知のブリッジのリストであり、各ブリッジはブリッジ識
別情報Ｂ−IDを格納するフィールド、及びブリッジによ
り接続されているサブネットワークの識別情報（SN−I
D）を格納する一対のフィールドを設けたそれぞれのエ
ントリを持っている。
処理ステーション13により使用される主データ構造を
概説したが、今度はステーションがこれら構造を使用し
てその作業を行う方法について説明することにする。
処理ステーション13が実行する主プログラムを図７に
示す。プログラムを始動すると、予め定められた時間間
隔、例えば１時間、が計時される（ステップ60、61）。
この時間間隔の間は主プログラムは遊休状態にあるが、
収集データパケットが処理ステーションにより受取られ
て割込サービスルーチンで処理されてネットワークのサ
ブネットワークについてのトラフィックマトリクスを構
成する。予め定められた時間間隔が経過した後、主プロ
グラムはトラフィックマトリクスの統計的処理を行い
（ステップ62）、次いで先ず最初に「ステーション割当
て」ルーチンを使用してステーションをサブネットワー
クと関係付け（ステップ63）、次に「ブリッジ試験」ル
ーチンを使用してブリッジがネットワークのどこに存在
するかを探知する（ステップ64）ことによる、ネットワ
ークのトポロジ的特徴の探知に進み、最後に、主プログ
ラムが終る。
図８は、受信した収集データパケットからサブネット
ワークトラフィックマトリクスを得るのに使用される割
込サービスルーチンを示す。割込サービスルーチンは、
割込の発生に応答してステーション13のネットワークイ
ンターフェースにより呼出され、これにより続いて収集
データパケットを受取り、そのパケットを入力待行列デ
ータ構造50に格納する。割込サービスルーチンが開始さ
れると、主プログラムの揮発性環境を格納し、割込をマ
スクするという通常のハウスキーピング作業が行われる
（ステップ65）。次に、入力待行列の最上部にある収集
データパケットのヘッダが検査される（ステップ66）。
ヘッダに入っている発信元アドレスは収集データパケッ
トを発生したモニタリング装置を識別する。実際、一つ
のモニタリング装置がネットワークの各サブネットワー
クに関連付けられていると仮定すれば、モニタリング装
置のアドレスも関連するサブネットワークを識別するの
に役立つ。従って、モニタリング装置のアドレスはサブ
ネットワークがSN−IDを識別するとき直接的にまたは間
接的に使用される。従って、検査中の収集データパケッ
トのヘッダに入っている発信元アドレスを検査すること
により、サブネットワークリスト51と突き合わせること
で収集データパケットが既知のサブネットワークから来
たか否か、またはパケットが今まで未知のサブネットワ
ークの存在を示しているか否かを判別することができる
（ステップ67）。新しいサブネットワークであることが
判れば、サブネットワークリスト51に新しいエントリが
作られ、新しいサブネットワークトラフィックマトリク
スアレイ53が作り出される（ステップ68）。サブネット
ワークエントリのTM−POINTERが新しいトラフィックマ
トリクスアレイを指すようにセットされ、一方Ｓ−POIN
TERがナル（null）にセットされる。
その後、割込サービスルーチンは考慮の対象の収集デ
ータパケットのデータフィールドの内容の検査に進む
（ステップ69）。データフィールドに保持されている発
信元ステーション及び着信先ステーションのアドレスの
チェックを行い、これらアドレスのいずれかが今まで未
知のステーション、すなわちステーションリスト52に入
っていないステーション、の存在を示しているかどうか
確かめる（ステップ70）。新しいステーションであるこ
とが判れば、ステーションリスト52が更新され（そのNE
XT−S POINTERをナルにセットする）、現存するサブネ
ットワークトラフィックマトリクス53が新しいステーシ
ョンを含むように拡張される（ステップ71）。
前述の準備段階が行われると、割込サービスルーチン
は、（収集データパケットのデータフィールドに保持さ
れているアドレスにより示されている）関連する発信元
ステーション／着信先ステーション対についてのエント
リを歩進させることにより（収集データパケットのヘッ
ダに含まれている発信元アドレスにより識別される）適
切なサブネットワークについてのトラフィックマトリク
ス53を更新する−ステップ72を参照。
モニタリング装置12により提供される情報はサンプル
されたものであるという性質を持っているため、モニタ
リング装置12からの新しいデータを直接使用して構成さ
れるサブネットワークトラフィックマトリクスは統計的
処理を受けるのが望ましい。この処理はサンプリング期
間のタイムアウト時に主プログラムのステップ62で行わ
れる。しかし、この処理を行うためには、サンプリング
期間中に各サブネットワークにより運ばれるパケットの
全数を記録する必要がある。上に説明したように、サブ
ネットワークについての現在のパケットの総計数値は処
理ステーション13に送られる各収集データパケットの情
報フィールドに入っている。サンプリング機関中にサブ
ネットワークにより運ばれたパケットの全数を確認する
ため、割込サービスルーチンのステップ73は、サブネッ
トワークに関して受取った最初の収集データパケットの
現在のパケット計数値及びそのサブネットワークに関し
てサンプリング期間中に受取った直前の収集データパケ
ットの現在のパケット計数値の双方を記録するよう動作
する。これら計数値は、サブネットワークリスト51の対
応するサブネットワークエントリの適切なフィールド
（図示せず）により各ネットワークについて記録するこ
とができる。サンプリング期間の終りに、両計数値の差
を取ることによりサンプリング期間中にサブネットワー
クにより運ばれたパケットの全数が示される。
最後に、入力待行列50をチェックして、割込サービス
ルーチンが実行されている間に新しい収集データパケッ
トを受取らなかったことを確認する（ステップ74）。こ
のような場合には、割込サービスルーチンは主プログラ
ム環境パラメータを回復し、割込のマスクを解除するこ
とにより終結する（ステップ75）。入力待行列が空でな
い場合には、ステップ66から73までが繰返される。
サンプリング期間の終結に続いて、主プログラムはサ
ブネットワークトラフィックマトリクスの統計的処理を
行うルーチンを呼出す（図７のステップ62）。この処理
は、仮定した正規分布についての各サブネットワークト
ラフィックマトリクス平均分散値の各要素を推定するこ
とを含んでおり、これらの値は関連トラフィックマトリ
クスアレイに戻して格納される。これら平均値及び分散
値を計算するためには、各トラフィックマトリクスの要
素により構成されている基本集合サンプル値「OC」（す
なわち、クラス「Ｃ」のサンプルの数）のみならず、関
連するサブネットワークトラフィックマトリクスの発生
に係るサンプルの総数「Ｏ」、及びサンプリング期間中
サブネットワークにより運ばれるパケットの総数「ｆ」
をも知る必要がある。サンプルの総数「Ｏ」は、関連す
るサブネットワークトラフィックマトリクスの全要素を
加算することにより、またはサンプリング期間中の各時
点での総数を把握していることにより得ることができ
る。既に説明したように、パケットの総数「ｆ］は最初
のパケット計数値を最終計数値から差し引くことにより
得られるが、これら二つの値はサブネットワークリスト
51に格納されている。値「OC」、「Ｏ」及び「ｆ」は下
記に従って使用される。
平均の推定値＝fOC/O （１） 分散の推定値＝f2（Ｏ−OC）OC/O3 （２） 「ステーション割当」ルーチンは、トラフィックマト
リクスの処理に続いて主プログラムにより呼出される
が、図９に示してある。このルーチンは、各ステーショ
ンを順番に取り上げ、すべてのサブネットワークマトリ
クスをサーチして、今取り上げているステーションから
発信されるトラフィックを最も多く運ぶサブネットワー
クを識別する。次に、このサブネットワークを当該ステ
ーションが直接に接続されているものとして取り扱
い、、各サブネットワークをそれに関連付けられたステ
ーションにリンクするリンクリスト中に適切なリンクを
作る。更に詳細に説明すれば、ルーチンの開始（ステッ
プ80）に続いて、二つの変数を０に初期設定するが、こ
れらは変数「CC−SUM」及び「CC−ID」である（ステッ
プ81を参照）。変数CC−IDは、ステーション割当ルーチ
ンの実行中の任意の特定の時点において、考慮の対象の
ステーションと関連付けられたサブネットワークである
として現在選択されているサブネットワークの識別情報
（SN−ID）を保持するのに使用される。変数CC−SUM
は、考慮の対象のステーションから発信されたパケット
の現在選択されているサブネットワークについて計算さ
れた合計を保持する。
変数CC−ID及びCC−SUMの初期設定に続き、ステーシ
ョン割当ルーチンはステーションリスト52中の各ステー
ションを順次選択し、各ステーションについてステップ
83から88までを行う。この逐次的な選択及び処理はステ
ップ82及び89の組合せで設定されるループにより行われ
る。各ステーション（識別情報「Ｓ−ID」）について、
サブネットワークリスト51に入っている各サブネットワ
ークを順次考察し、そのトラフィックマトリクスを調べ
る。この逐次的な検査はステップ83及び87が共同して確
立されるループにより遂行される。検査される各サブネ
ットワークトラフィックマトリクスについて、現在選択
されているステーションから発せられるトラフィックを
全着信先ステーションについて加え合せ、その結果得ら
れた数を変数「SUM」に格納する（ステップ84）。次に
「SUM」の値を「CC−SUM」に保持されている値と比較す
る（ステップ85）。「SUM」の値が「CC−SUM」の値より
大きければ、「SUM」に保持されている値を「CC−SUM」
に転送し、考慮の対象のサブネットワークトラフィック
マトリクスに関連付けられたサブネットワークの識別情
報「SN−ID」を変数「CC−ID」に格納する（ステップ8
6）。
「SUM」と「CC−SUM」の比較は、関連する数量の統計
的性質に鑑み、仮説試験法（hypothesis testing）を用
いて行われる。このような方法は当業者には周知であ
り、多数の標準的な著作（例えば、Addison−Wesleyか
ら出版されたMeger著“Introductory Probability and
Stantistical Applications"、第２版、1970）に見るこ
とができる。従って、関連する処理の説明を、ここで
は、比較する平均値が互いに一定の範囲内にある場合に
は、どちらが大きいかに関する妥当な決定を行うことが
できないという判断が行われる、ということを記す他は
示さないことにする。このような判断が行われる場合に
は、関連ステーションを特定のサブネットワークに関係
づける有効な割当を行うことができないということを意
味するので、この旨を記す（勿論、ステーションについ
ての「SUM」の後続値が統計的決断を行うことができる
だけ充分「CC−SUM」より大きければ、これはそのステ
ーションに対して行われた先の「決定不能」の判断をく
つがえす）。
ステップ87は、すべてのサブネットワークトラフィッ
クマトリクスが特定のステーションに関して検査されて
しまうまでプロセスをループさせる。このループを抜け
出すと、変数「CC−ID」にはそのトラフィックマトリク
スが考慮の対象のステーションから発信させたトラフィ
ックについてのエントリを最も多く含んでいるサブネッ
トワークの識別情報が入っている。このサブネットワー
クを考慮の対象のステーションがそこに接続されている
ものとして採用する（ただし、示したとおり、決定を妥
当に行うことができないと判断されなかったものとす
る）。それ故、考慮の対象のステーションが（サブネッ
トワークエントリのポインタＳ−POINTERのナルのセッ
ティングにより示されるように）「CC−ID」により識別
されるサブネットワークに割当てられるべき最初のもの
である場合には、そのサブネットワークエントリについ
てのＳ−POINTERは考慮の対象のステーション（識別情
報「Ｓ−ID」）に対応するステーションリスト52のエン
トリを指すようにセットされる（ステップ88）。考慮の
対象のステーションが「CC−ID」により識別されるネッ
トワークに割当てられるべき最初のものでない場合に
は、サブネットワークに関連付けられ且つ関連するＳ−
POINTERにより指されるステーションの連鎖が連鎖の最
後のステーションエントリまでたどられ、そのステーシ
ョンエントリのNEXT−S POINTERが考慮の対象のステー
ションについてのエントリを指すようにセットされる。
その後、ステップ89はすべてのステーションがサブネ
ットワークに割当てられてしまうまでルーチンをステッ
プ82までループバックさせる。これが行われると、ルー
チンは終る（ステップ19）。
ステーションをサブネットワークに割当ててから、主
プログラム（図７）は、どのサブネットワークの対がブ
リッジにより相互接続されているかを探知するため「ブ
リッジ試験」ルーチンを開始する。このルーチンを詳細
に説明する前に、ブリッジを識別するのに使用される試
験の基礎について説明することにする。
ブリッジが二つのサブネットワークＸ及びＹを、サブ
ネットワークＹの上の非局所的なトラフィックをサブネ
ットワークＸに伝えることができるように直接接続され
ているか否かを確認したい場合を考える。ネットワーク
の残りのサブネットワーク（すなわち、Ｘ及びＹ以外の
サブネットワークのグループ）をグループＲとして考え
れば、ネットワーク及びサブネットワークＹからのトラ
フィックの流れを、ブリッジがサブネットワークＹ及び
Ｘを直接接続している場合図10Aの図表により、及びサ
ブネットワークＹ及びＸを接続するブリッジが存在しな
い場合図10Bの図表により、表わすことができる。これ
らの図表において、各種トラフィックの流れの構成要素
は、文字Ｔの後に、トラフィックの当該構成要素がサブ
ネットワークＹ上の発信元から着信先までにたどるサブ
ネットワークの系列を括弧で囲んだものを付けて表わさ
れる。従って、サブネットワークＹ上から発信され、サ
ブネットワークグループＲを通ってサブネットワークＸ
に伝えられるトラフィック構成要素はＴ（YRX）で表わ
される。
図10Aに示した破線のトラフィック流れ構成要素Ｔ（Y
RX）及びＴ（YRXR）は、ネットワークのトポロジがサブ
ネットワークＸへの直接及び間接の両径路を与えるルー
プを含んでいる場合にのみ存在する。事実、図10Aのト
ラフィック流れ構成成分Ｔ（YR）及びＴ（YXR）は、サ
ブネットワークのグループＲがサブネットワークＸを通
してサブネットワークＹに接続されているだけならば、
存在しないこともある。
ブリッジの三つの試験の中の最初の試験では、サブネ
ットワークＹから来るすべてのトラフィックの中のどの
構成要素が（着信先には関りなく）サブネットワークＸ
上に及びサブネットワークグループＲ上に現われるかに
ついて考察する。この考察では、以下の表現を使用す
る： T1＝着信先に関係なく、サブネットワークＹからのす
べてのトラフィック。
［T1］Ｘ＝T1の中のサブネットワークＸ上に現われる
部分。
T1（Y..）＝T1の中の括弧中に示されるルートをたど
る構成成分。
図10Aを参照することにより、どんな場合にブリッジ
がサブネットワークＹをサブネットワークＸに直接連結
するかということがわかる： ［T1］Ｘ＝T1（YX）＋T1（YXR）＋T1（YRX） ＋T1（YRXR） （３） ［T1］Ｒ＝T1（YR）＋T1（YXR）＋T1（YRX） ＋T1（YRXR） （４） 公式（３）及び（４）は最も一般的な場合を表わして
いる。両公式（３）及び（４）の最後の二つの構成要素
はそのネットワークにはサブネットワークＸへの直接径
路しか存在しないところの非ループネットワークには存
在しない。更に、これら構成要素、更には公式（４）中
の構成要素T1（YR）も、サブネットワークＹからのブリ
ッジがサブネットワークＸに接続しているものだけであ
れば存在しない。
今度は図10Bを参照すると、サブネットワークＹをサ
ブネットワークＸに直接連結するブリッジが存在しない
場合に、 ［T1］Ｘ＝T1（YRX）＋T1（YRXR） （５） ［T1］Ｒ＝T1（YRX）＋T1（YRXR）＋T1（YR） （６） であることがわかる。これから、サブネットワークＹを
サブネットワークＸに接続するブリッジが存在しなけれ
ば、 ［T1］Ｒ＞＝［T1］Ｘ （７） 式（５）が満足されなければ、すなわち、 ［T1］Ｘ＞［T1］Ｒ （８） であれば、サブネットワークＹをサブネットワークＸに
直接接続するブリッジが存在しなければならない。言い
換えればサブネットワークＸで観測されたところのサブ
ネットワークＹ上のステーションからのトラフィック
が、他のグループＲに属するすべてのサブネットワーク
で観測されたものより多ければ、サブネットワークＹと
サブネットワークＸの間にブリッジが存在するとするこ
とができる。この試験は、サブネットワークＹとＸの間
に存在するブリッジを必ずしも識別しないが、多くの場
合に識別を行い、ブリッジが存在しない場合にブリッジ
を見つけることはない。
ブリッジを試験する三つの試験の中の２番目のもの
は、１番目のものと同様であるが、サブネットワークＹ
から発せられるトラフィックのうちの着信先がサブネッ
トワークＸとなっていないものだけを考える。このトラ
フィックをT2と名付ける。着信先がサブネットワークＸ
になっていない図10Bに示すトラフィック構成要素を参
照することにより、サブネットワークＹをサブネットワ
ークＸに連結するブリッジが存在しなければ、 ［T2］Ｘ＝T2（YRXR） （９） ［T2］Ｒ＝T2（YR）＋T2（YRXR） （10） であることがわかる。これから、ブリッジが存在しない
とき ［T2］Ｒ＞＝［T2］Ｘ （11） が得られる。式（11）が満足されなければ、すなわち、 ［T2］Ｘ＞［T2］Ｒ （12） であれば、サブネットワークＹをサブネットワークＸに
直接接続するブリッジが存在しなければならない。換言
すれば、サブネットワークＸで観測されたところの、サ
ブネットワークＹのステーションからのトラフィックの
うちの着信先がサブネットワークＸになっていないトラ
フィックが、残りのグループＲのすべてのサブネットワ
ークで観測された見たものより多ければ、サブネットワ
ークＹとサブネットワークＹの間にブリッジが存在する
とすることができる。この試験も必ずしもブリッジを見
つけないが、ブリッジが存在しなければブリッジを見つ
けることはない。
ブリッジの有無を試験する三つの試験の中の３番目の
ものは、実際のブリッジのほとんどは「漏れを起こしや
すい」、すなわちブリッジに接続されているサブネット
ワークが着信先となっているトラフィックの小部分がそ
のブリッジを越えて接続されたサブネットワークに行っ
てしまう、という事実に頼っている。この漏れたトラフ
ィックは最初の二つの試験に関連するトラフィック構成
要素を考える際には考慮に入れなかった。それは、漏れ
成分は他の成分と比較してわずかであり、且つどんな場
合でも、以下から明らかになるように、これら漏れ成分
が存在しても先に得た試験公式の妥当性は変らないから
である。
サブネットワークＹから発信され着信先をサブネット
ワークＹとするトラフィックをT3と記せば、可能なトラ
フィック構成要素は図11に示すようになる。「漏れ」ト
ラフィックは不確実であり、ネットワークのブリッジの
動作の性質に依存するという宿命に注目しなければなら
ない。従って、ブリッジは漏れトラフィックにフィルタ
動作して、それがネットワークを通ってさらに伝送され
ることを完全に防ぐように働くことができるが、常にそ
のようになるわけではない。従って、図11は、サブネッ
トワークＹに戻ることができる漏れトラフィックのすべ
ての場合の他に、フィルタ動作によって除去される漏れ
トラフィックのすべての場合をも含んでいる。
図11から、サブネットワークＹをサブネットワークＸ
に連結するブリッジが存在しないとき、 ［T3］Ｘ＝T3（YRXRY）＋T3（YRX）＋T3（YRXR） （13） ［T3］Ｒ＝T3（YRXRY）＋T3（YRX）＋T3（YRXR） ＋T3（YR）＋T3（YRY） （14） であることがわかる。これから、ブリッジが存在しない
とき以下が成立する。
［T3］Ｒ＞＝［T3］Ｘ （15） 式（15）が満足されなければ、すなわち、 ［T3］Ｘ＞［T3］Ｒ （16） であれば、サブネットワークＹをサブネットワークＸに
直接接続するブリッジが存在しなければならない。換言
すれば、サブネットワークＸで観測されたところの、着
信先がサブネットワークＹであってサブネットワークＹ
のステーションからのトラフィックが、残りのグループ
Ｒのすべてのネットワークで観測されたものより多けれ
ば、サブネットワークＹとサブネットワークＸの間にブ
リッジが存在するとすることができる。この試験も必ず
しもブリッジを見つけるわけではないが、ブリッジが存
在しなければブリッジを見つけることはない。
公式（16）中の不等号の向きに照らして、漏れトラフ
ィックの流れを第１及び第２のブリッジ試験に関して上
に述べたものと重ねても式（８）及び（12）で得られる
結果は変らない。
図12に示す「ブリッジ試験」ルーチンは、サブネット
ワークの各対を取り上げて、上述の三つのブリッジ試験
の各々を適用して第１のサブネットワークを第２のサブ
ネットワークに連結するブリッジが存在するか否か探知
する。これらの試験の性格は、これらが一方向性である
−すなわち、これらの試験はトラフィックを一つのサブ
ネットワークから他へ一方向に流すブリッジ接続が存在
するか否かを試験する。しかし、図12のルーチンは、最
初に試験をサブネットワーク対にある一方の向きに適用
し次に続いて試験をサブネット対に逆方向に適用するこ
とにより試験を両方向に適用している。
図12を一層詳細に考察すると、サブネットワークリス
ト51の各サブネットワークをブリッジ試験を受けさすべ
きサブネットワーク対の第１のサブネットワークＹとし
て順番に取り上げる（ステップ92）。サブネットワーク
Ｙとして割当てられた各サブネットワークについて、残
りのサブネットワークの各々を試験を受けるべきサブネ
ットワークの対の第２のサブネットワークＸとして順番
に取り上げる（ステップ93）。試験すべきサブネットワ
ークＸ、Ｙの対を組立て終ったら、適切なルーチンを呼
んで第１のブリッジ試験を適用する（ステップ94）。こ
の第１の試験を終了してから、試験が成功したかチェッ
クして確認し、もし成功だったら、第２及び第３の試験
対Ｙ、Ｘに適用しない。しかし、第１の試験でブリッジ
が見つからなければ、第２の試験を実行する（ステップ
96）。
第２の試験が完了しても、YX対の間にブリッジがやは
り見つかっていなければ（ステップ97）、ブリッジの有
無に関する第３の試験を行う（ステップ98）。
こうして、サブネットワーク対YX間のブリッジが見つ
かったか、または三つの試験をすべて行ったがブリッジ
が見つかっていない状況に達する。ブリッジが見つかっ
た場合には、ブリッジリストは関連するブリッジ試験サ
ブルーチンの最終ステップで更新されてしまっている。
その後で、ループバックして次の第２のサブネットワ
ークＸを選択する（ステップ99）か、あるいはすべての
サブネットワーク（現在のＹサブネットワークを除く）
が第２のサブネットワークＸとして使用されてしまって
いる場合には、ループバックして第１のサブネットワー
クＹについての新しいサブネットワークを選択（ステッ
プ100）することによって、次のサブネットワーク対を
取り上げる。
順を追って、すべてのサブネットワーク対を両方向に
試験する。その後、「ブリッジ試験」ルーチンを終了す
る。
図13は「第１のブリッジ試験」サブルーチンを示す。
この第１の試験には第２のサブネットワークＸで観測さ
れたところの、第１のサブネットワークＹから発せられ
たすべてのトラフィックの総計を他のすべてのサブネッ
トワーク（すなわち、Ｘ及びＹを除く）で観測されたと
ころの、サブネットワークＹから発せられるすべてのト
ラフィックの総計と比較することが含まれることを想起
するであろう。サブルーチンの第１のステップ102は、
サブネットワークＸについてのトラフィックマトリクス
にアクセスし、サブネットワークＹから発せられた全て
のトラフィック（このトラフィックはサブネットワーク
Ｙ上にあるステーションから発せられるトラフィックで
あり、これらステーションはサブネットワークＹについ
てのＳ−POINTERで始まる連結リストを参照することに
より識別される）を加え合わせることを含んでいる。そ
の結果できる合計は［T1］Ｘを表わす変数にストアれ
る。
次に、ステップ103及び104で、ネットワークＹ及びＸ
以外の各サブネットワークについてのトラフィックマト
リクスを順番に検査し、サブネットワークＹから発信さ
れた同一のトラフィックが考慮の対象のサブネットワー
クの幾つかで観測されることがあるという事実には関心
を払わずに、サブネットワークＹから発信されるトラフ
ィックについて累積的な総計を求める。これらすべての
サブネットワークトラフィックマトリクスから得られる
全トラフィック値は、［T1］Ｒを表わす変数に格納され
る。次に、［T1］Ｘと［T1］Ｒの値を比較する（ステッ
プ105）。ここでは、処理しているデータの統計的性格
に照らして、この比較を仮説試験法を用いて行う。
［T1］Ｘの値が［T1］Ｒの値より大きければ、トラフィ
ックをサブネットワークＹからサブネットワークＸに直
接流すことができるようにするブリッジが存在すると判
定する。それ故、この新しいブリッジ及びこのブリッジ
が連結する第１及び第２のサブネットワークを識別する
対応するエントリがブリッジリスト中に作られる（ステ
ップ106）。その後、「第１のブリッジ試験」サブルー
チンを終結する。
「第２のブリッジ試験」サブルーチンは、着信先がサ
ブネットワークＸになっているところの、サブネットワ
ークＹから発されたトラフィックだけを、ステップ102
及び103に対応するステップで合計することを除いて、
図13に示すものと同じである。
「第３のブリッジ試験」サブルーチンも図13に示すも
のと同じであるが、やはり着信先がサブネットワークＹ
になっているところの、サブネットワークＹから発信さ
れたトラフィックのみをステップ102及び103に対応する
ステップで合計する。
サブネットワークトラフィックマトリクスは統計デー
タから得られるので、上述のルーチン及びサブルーチン
によりデータについて行われる各種試験は直裁的な比較
ではなく完全に仮説試験を採用することがわかるだろ
う。
上述のトポロジ発見法には多くの変形を行うことがで
きる。例えば、ブリッジについての試験の終りを考慮の
対象のサブネットワーク対Ｙ、ＸのサブネットワークＹ
の特定のステーションからのトラフィックに関して適用
することができ、この試験をサブネットワークＹ上の各
ステーションからのトラフィックについて繰返すことが
できる。更に、トラフィックマトリクスデータをモニタ
リング装置自身が導出し、サンプリング期間の終りに処
理ステーション13に送ることができる。この場合には、
モニタリング装置は、パケットをサンプルするのではな
く各パケット及びすべてのパケットを記録することがで
きる。特定のトポロジ的特徴だけが必要な場合または特
定の試験だけを使用しようとする場合には、サブネット
ワークトラフィックマトリクスに入っているような完全
な範囲のトラフィック情報を提示することは不要であ
る。例えば、第１のブリッジ試験だけを使用し、パケッ
トに入っている発信元情報が直接発信サブネットワーク
を示している場合には、モニタリング装置は、特定のサ
ブネットワークから発せられるパケットがどれだけ観察
されるかを直接記録することができ、このデータを次に
ステーション13に供給して「第１のブリッジ試験」サブ
ルーチン（図13）に直ちに使用することができる。
得られた部分トラフィックマトリクスを使用して地点
トラフィックマトリクス（site traffic matrix）（す
なわち、すべてのサブネットワークについてのトラフィ
ックマトリクス）を得ることができる。図14は、このよ
うな地点トラフィックマトリクスを得る一つの方法を示
しており、以下に示すとおり、この獲得は、上述のステ
ーション割当ルーチンにより得られるかまたは他の何等
かの方法で（例えば、ネットワーク構成データベースか
ら、またはブリッジまたはルータから）得られる、各ス
テーションのサブネットワーク割当の知識を用いて好適
に行われる。しかし、各ステーションの割当の知識は不
可欠ではない。
図14を参照するに、（ステップ110及び120により確立
されたループ構造により）各発信元／着信先ステーショ
ン対を順番に考慮し、次に地点トラフィックマトリクス
の対応するエントリを、発信元ステーション及び着信先
ステーションの一方が既知であるか双方が既知であるか
に依存する態様で今存在する部分トラフィックマトリク
スから得る。
発信元ステーション及び着信先ステーションの双方の
サブネットワークのロケーションが既知で且つ同じであ
れば（ステップ111、112）、この発信元／着信先ステー
ション対についての地点トラフィックマトリクス（site
traffic matrix）のエントリは、両ステーションが共
通に設けられているサブネットワークについての部分ト
ラフィックマトリクスの対応するエントリとして取られ
る（ステップ113）。しかし、両ステーションのロケー
ションが既知ではあるが異なっていれば、このステーシ
ョン対についての地点トラフィックマトリクスのエント
リは、各ステーションがそれぞれ設けられているサブネ
ットワークについての部分トラフィックマトリクスの対
応するエントリを平均することにより得られる（ステッ
プ114）。
前述の説明で開示されている態様で得られるときの部
分トラフィックマトリクスのエントリの統計的性格のた
め、平均操作は次の形態を取る： 平均された平均値＝（m1＋m2）/2 平均された分散＝（V1＋V2）/4 ただしm1、V1は発信元ステーションロケーションの部分
トラフィックマトリクスの関連する平均エントリ及び分
散エントリであり、m2、V2は着信先ステーションロケー
ションの部分トラフィックマトリクスの関連する平均エ
ントリ及び分散エントリである。
発信元ステーションのロケーションだけが既知であれ
ば（ステップ115）、地点トラフィックマトリクスのエ
ントリは、発信元ステーションのサブネットワークにつ
いての部分トラフィックマトリクスの対応するエントリ
として取られる（ステップ116）。同様に、着信先ステ
ーションロケーションだけが既知であれば（ステップ11
7）、地点トラフィックマトリクスのエントリは着信先
ステーションのサブステーションについての部分トラフ
ィックマトリクスの対応するエントリとして取られる。
発信元ステーション及び着信先ステーションのロケー
ションが双方とも未知であれば、地点トラフィックマト
リクスのエントリは、すべてのサブネットワークトラフ
ィックマトリクスのなかで、見つけるべきそのステーシ
ョン対についての最大平均値を識別し、次いで地点トラ
フィックマトリクスについての対応するサブネットワー
クマトリクスのエントリを用いることにより得られる
（ステップ119）。
地点トラフィックマトリクスを得る上述の方法は勿
論、統計的に得られた部分トラフィックマトリクスと共
に使用することができることに加えて、非統計的方法に
より得られる部分トラフィックマトリクスと共に使用す
ることができる。更に、地点トラフィックマトリクスの
獲得は、特にステーションロケーション情報を別に利用
できる場合には、上述のステーション割当作業及びブリ
ッジ識別作業とは無関係に行うことができる。
上に開示したトポロジ発見方法をイーサネットネット
ワークに関連して説明してきたが、この方法は、インタ
ーネットネットワークのような他のネットワークに適用
してネットワークのトポロジ的特徴を探知することがで
きることが認められるであろう。
前述のトポロジ発見方法を、プログラム及びデータを
別々に考える場合に適切なプログラミング方法を使用し
て容易に実現することができるデータ構造について説明
してきたが、説明した方法はオブジェクト志向プログラ
ミングのような手法を使用して実現することができるこ
とが認められるであろう。
フロントページの続き (56)参考文献 特開 平４−263536（ＪＰ，Ａ) 特開 平２−140034（ＪＰ，Ａ) 特開 平１−129550（ＪＰ，Ａ) (58)調査した分野(Int.Cl.7，ＤＢ名) H04L 12/28 - 12/46

Claims (15)

    (57)【特許請求の範囲】
  1. 【請求項１】以下のステップ（ａ）〜（ｃ）を設け、複
    数のサブネットワーク、サブネットワークを相互接続す
    る架橋装置（14）、及びサブネットワークへまたはそこ
    からのトラフィックを発信及び／または着信する様に動
    作するステーション（11）を設け、トラフィックは各々
    が発信元及び着信先情報（15）を含む離散的なメッセー
    ジパケットの形態である形式のネットワークのトポロジ
    的特徴を探知するための方法： （ａ）前記サブネットワークの内の少なくともいくつか
    の上でのトラフィックをモニタして、少なくともその様
    にしてモニタされたトラフィックの発信元に関するデー
    タを導出する、 （ｂ）少なくとも１つの前記ステーションを含む特定の
    発信元からのトラフィックであって、前記ネットワーク
    の複数の部分で観測されるトラフィックの量の測定値、
    または当該観測されるトラフィックから選択された部分
    集合の量の測定値を決定する、 （ｃ）前記測定値を比較して、前記ネットワークのどの
    特定の部分が前記特定の発信元からの問題としているト
    ラフィックのうちのもっとも多くを運んでいるかを判定
    し、これにより前記特定の発信元についてのネットワー
    クの選択されたトポロジ的特徴を判定する。
  2. 【請求項２】前記メッセージパケットに含まれている前
    記発信元情報が前記パケットを発信したステーションを
    識別する働きをする場合に、選択された前記ステーショ
    ン（11）が前記サブネットワークのどれに対して接続さ
    れているかを探知する請求の範囲第１項の方法であっ
    て、前記ステップ（ｂ）（65〜75、84）は前記選択され
    たステーションから発生して前記各サブネットワークに
    よって運ばれたトラフィックの量を判定する働きをし、 また前記ステップ（ｃ）（83〜87）は前記選択されたス
    テーション（11）からのトラフィックを最も多く運ぶサ
    ブネットワークを判定することを含み、このサブネット
    ワークが前記選択されたステーション（11）が接続され
    ているサブネットワークであるとされる。
  3. 【請求項３】前記メッセージパケットに含まれている前
    記発信元情報が前記パケットを発信したステーションを
    識別する働きをする場合に、選択された前記ステーショ
    ン（11）が前記サブネットワークのどれに対して接続さ
    れているかを探知する方法において、 前記方法は前記ステップ（ａ）（40〜47）をすべてのス
    テーションについて同時に行いながら、前記各々のステ
    ーション（11）について請求の範囲第２項の方法を行う
    ことを含む ことを特徴とする請求の範囲第１項記載の方法。
  4. 【請求項４】以下の特徴（ｄ）〜（ｇ）を有し、第１の
    前記サブネットワーク（Ｙ）が前記架橋装置（14）によ
    って直接に第２の前記サブネットワーク（Ｘ）に接続さ
    れているかどうかを探知する請求の範囲第１項の方法： （ｄ）前記方法は前記発信元情報を前記サブネットワー
    クに対応させる関連付け情報を提供するステップ（40〜
    47、65〜75、63）を含み、メッセージパケットに含まれ
    ている前記発信元情報を、前記第１のサブネットワーク
    から発生したメッセージパケットを識別するのに使用で
    きるようにする； （ｅ）前記ステップ（ａ）（40〜47）は前記第２のサブ
    ネットワーク（Ｘ）上のトラフィック及び前記第１及び
    第２のサブネットワーク以外のすべての前記サブネット
    ワークによって作られるグループ（Ｒ）の各サブネット
    ワーク上のトラフィックをモニタすることを含む； （ｆ）前記ステップ（ｂ）（65〜75、102、103）は、前
    記関連付け情報を使用して、前記第１のサブネットワー
    ク（Ｙ）から発信されたトラフィックの内で前記第２の
    サブネットワーク（Ｘ）によって運ばれたトラフィック
    の量とサブネットワークのグループ（Ｒ）によって運ば
    れたトラフィックの量についてのデータを導出すること
    を含む； （ｇ）前記ステップ（ｃ）（94）は前記測定値を使って
    前記第１のサブネットワーク（Ｙ）から発生されたトラ
    フィックの内で、夫々、前記第２のサブネットワーク
    （Ｘ）によって運ばれたものと、前記サブグループのグ
    ループ全体で運ばれたものの量（［T1］Ｘ、［T1］Ｒ）
    を比較するように動作し、前記ステップ（ｃ）はこれら
    のトラフィックの量の中の多い側が前記第２のサブネッ
    トワーク（Ｘ）によって運ばれた場合に架橋装置（14）
    が前記第１のサブネットワーク（Ｙ）を前記第２のサブ
    ネットワーク（Ｘ）に直接に接続していると判定する。
  5. 【請求項５】以下の特徴（ｈ）〜（ｋ）を有し、第１の
    前記サブネットワーク（Ｙ）が前記架橋装置（14）によ
    って直接に第２の前記サブネットワーク（Ｘ）に接続さ
    れているかどうかを探知する請求の範囲第１項の方法： （ｈ）前記方法は前記発信元情報及び前記着信先情報を
    前記サブネットワークに対応させて下記の（ｈ−１）及
    び（ｈ−２）ができるようにする関連付け情報（40〜4
    7、65〜75、63）を提供するステップを含む： （ｈ−１）メッセージパケットに含まれている発信元情
    報を前記第１のサブネットワーク（Ｙ）から発生したメ
    ッセージパケットを識別するために使用する； （ｈ−２）メッセージパケットに含まれている前記着信
    先情報を前記第２のサブネットワーク（Ｘ）以外の着信
    先を持っているメッセージパケットを識別するために使
    用する； （ｉ）前記ステップ（ａ）（40〜47、65〜75、63）は前
    記第２のサブネットワーク（Ｘ）上のトラフィック及び
    前記第１及び第２のサブネットワーク以外のすべての前
    記サブネットワークによって作られるグループ（Ｒ）の
    各サブネットワーク上のトラフィックをモニタすること
    を含む； （ｊ）前記ステップ（ｂ）は、前記関連付け情報を使用
    して、前記第１のサブネットワーク（Ｙ）から発信され
    且つ前記第２のサブネットワーク（Ｘ）以外の着信先を
    有するトラフィックの内で前記第２のサブネットワーク
    （Ｘ）によって運ばれたトラフィックの量と前記サブネ
    ットワークのグループ（Ｒ）のサブネットワークによっ
    て運ばれたトラフィックの量の測定値を導出することを
    含む； （ｋ）前記ステップ（ｃ）（96）は前記測定値を使って
    前記第１のサブネットワーク（Ｙ）から発生され且つ前
    記第２のサブネットワーク（Ｘ）以外の着信先を有する
    トラフィックの内で、夫々、前記第２のサブネットワー
    ク（Ｘ）によって運ばれたものと、前記サブグループの
    グループ全体で運ばれたものの量（［T2］Ｘ、
    ［T2］Ｒ）を比較するように動作し、前記ステップ
    （ｃ）はこれらのトラフィックの量の中の多い側が前記
    第２のサブネットワーク（Ｘ）によって運ばれた場合に
    架橋装置（14）が前記第１のサブネットワーク（Ｙ）を
    前記第２のサブネットワーク（Ｘ）に直接に接続してい
    ると判定する。
  6. 【請求項６】以下の特徴（ｌ）から（ｏ）を有し、ネッ
    トワーク中で使用されている前記架橋装置（14）は接続
    されているサブネットワークに着信先を有するメッセー
    ジパケットがそのサブネットワークから当該架橋装置
    （14）を通り抜けて別のサブネットワークへ行くことを
    完全には阻止しない場合に、第１の前記サブネットワー
    ク（Ｙ）が前記架橋装置（14）によって直接に第２の前
    記サブネットワーク（Ｘ）に接続されているかどうかを
    探知する請求の範囲第１項の方法： （ｌ）前記方法は前記発信元情報及び前記着信先情報を
    前記サブネットワークに対応させて下記の（ｌ−１）及
    び（ｌ−２）ができるようにする関連付け情報（40〜4
    7、65〜75、63）を提供するステップを含む： （ｌ−１）メッセージパケットに含まれている発信元情
    報を前記第１のサブネットワーク（Ｙ）から発生したメ
    ッセージパケットを識別するために使用する； （ｌ−２）メッセージパケットに含まれている前記着信
    先情報を前記第２のサブネットワーク（Ｘ）以外の着信
    先を持っているメッセージパケットを識別するために使
    用する； （ｍ）前記ステップ（ａ）（40〜47）は前記第２のサブ
    ネットワーク（Ｘ）上のトラフィック及び前記第１及び
    第２のサブネットワーク以外のすべての前記サブネット
    ワークによって作られるグループ（Ｒ）の各サブネット
    ワーク上のトラフィックをモニタすることを含む； （ｎ）前記ステップ（ｂ）（65〜75、98）は、前記関連
    付け情報を使用して、前記第１のサブネットワーク
    （Ｙ）から発信され且つ前記第１のサブネットワーク
    （Ｙ）上に着信先を有するトラフィックの内で前記第２
    のサブネットワーク（Ｘ）によって運ばれたトラフィッ
    クの量と前記サブネットワークのグループ（Ｒ）のサブ
    ネットワークによって運ばれたトラフィックの量につい
    ての測定値を導出する； （ｏ）前記ステップ（ｃ）（98）は前記データを使って
    前記第１のサブネットワーク（Ｙ）から発生され且つ前
    記第１のサブネットワーク（Ｙ）上に着信先を有するト
    ラフィックの内で、夫々、前記第２のサブネットワーク
    （Ｘ）によって運ばれたものと、前記サブグループのグ
    ループ全体で運ばれたものの量（［T3］Ｘ、［T3］Ｒ）
    を比較するように動作し、前記ステップ（ｃ）はこれら
    のトラフィックの量の中の多い側が前記第２のサブネッ
    トワーク（Ｘ）によって運ばれた場合に架橋装置（14）
    が前記第１のサブネットワーク（Ｙ）を前記第２のサブ
    ネットワーク（Ｘ）に直接に接続していると判定する。
  7. 【請求項７】前記ステップ（ｂ）（94、96、98）は、前
    記グループ（Ｒ）の各々のサブネットワークについての
    対応するトラフィック量を同一のメッセージパケットが
    そのグループの複数のサブネットワーク上でモニタされ
    ることの結果として起こることのあるいかなる重複も無
    視して足し合わせることにより、前記第１のサブネット
    ワークから発信されたトラフィックの内で前記グループ
    （Ｒ）のサブネットワークによって運ばれるものをまと
    めたところの対応する量を導出することを特徴とする請
    求の範囲第４項、第５項、または第６項の方法。
  8. 【請求項８】請求の範囲第４項記載の方法であって、前
    記関連付け情報は更にメッセージパケットに含まれてい
    る前記着信先情報を使って、パケットの着信先サブネッ
    トワークを識別できるようにし、前記ステップ（ｂ）
    （94）は前記第１のサブネットワーク（Ｙ）から発信さ
    れ前記グループ（Ｒ）によって運ばれたものをまとめた
    前記トラフィックの量を下記により導出する： − 前記グループ（Ｒ）の各々のサブネットワークにつ
    いて、前記第１のサブネットワーク（Ｙ）から発信され
    るサブネットワークトラフィックの構成要素のうちで、
    当該サブネットワークを着信先とするものと前記第２の
    サブネットワーク（Ｘ）を着信先とするものとを判定す
    る； − 前記グループ（Ｒ）のすべてのサブネットワークに
    ついてこのように判定されたサブネットワークトラフィ
    ック構成要素を足し合わせる。
  9. 【請求項９】請求の範囲第５項または第６項の方法であ
    って、前記ステップ（ｂ）は下記によって、前記第１の
    サブネットワーク（Ｙ）から発信されて前記グループ
    （Ｒ）のサブネットワークによって運ばれたものをまと
    めた前記対応するトラフィックの量を導出する： − 前記グループ（Ｒ）の各サブネットワークについ
    て、前記第１のサブネットワークから発信された関連す
    るサブネットワークトラフィックであって、当該サブネ
    ットワークを着信先とする構成要素と、前記第２のサブ
    ネットワークを着信先とする構成要素を判定する； − 前記グループ（Ｒ）のすべてのサブネットワークに
    ついてこのように判定された関連するサブネットワーク
    トラフィック構成要素を足し合わせる。
  10. 【請求項１０】前記関連付け情報（40から47、65〜75、
    63）を提供するステップは、請求の範囲第２項または第
    ３項の方法を含んでステーションを前記第１のサブネッ
    トワークに関連付け、 請求の範囲第２項または第３項によって行われる前記ス
    テップ（ａ）は請求の範囲第４項、第５項、または第６
    項の中の適切なもので述べられた前記ステップ（ａ）と
    独立にあるいはそれと共に行われる ことを特徴とする請求の範囲第４項、第５項、または第
    ６項の方法。
  11. 【請求項１１】前記関連付け情報は、メッセージパケッ
    トに含まれる前記発信元情報を使って前記メッセージパ
    ケットが前記第１のサブネットワーク上のどのステーシ
    ョンから発信されたかを識別できるようにし、 架橋装置（14）が前記第１及び第２のサブネットワーク
    （Ｘ、Ｙ）の間にあるかどうかを判定する前記ステップ
    （ｂ）及びステップ（ｃ）は前記第１のサブネットワー
    クの各ステーションからの個別に取り上げられたトラフ
    ィックについて行われる ことを特徴とする請求の範囲第４項、第５項、または第
    ６項に記載の方法。
  12. 【請求項１２】ネットワークの二つのサブネットワーク
    が双方向の架橋装置（14）によって直接に接続されてい
    るか否かを探知する方法において、 前記方法は前記サブネットワークの一つから発信された
    トラフィックについて請求の範囲第４項、第５項、また
    は第６項の方法を実行して、次に当該方法を他方の前記
    サブネットワークから発信されたトラフィックについて
    繰り返すことを含むことを特徴とする方法。
  13. 【請求項１３】ネットワークの少なくとも一部分につい
    ての、サブネットワーク及び架橋装置によるそれらの相
    互接続という点でのトポロジを探知する方法において、 ネットワークのまたはネットワーク中の考慮の対象であ
    る部分のサブネットワークの各対について、請求の範囲
    第４項、第５項、または第６項のいずれかの方法を実行
    することを含み、以ってどのサブネットワークが架橋装
    置によって相互接続されているかを判定することを特徴
    とする方法。
  14. 【請求項１４】前記ステップ（ａ）（65〜75）は各サブ
    ネットワークについてトラフィックマトリクスを生成す
    ることを含むことを特徴とする請求の範囲第１項ないし
    第13項の何れかに記載の方法。
  15. 【請求項１５】前記ステップ（ａ）（40〜47、65〜75、
    63）はサブネットワーク上のトラフィックをサンプリン
    グすることを含み、 前記ステップ（ｃ）（94、96、98）は仮説試験法を使用
    することによってその判定を行うことを特徴とする請求
    の範囲第１項ないし第14項の何れかに記載の方法。
JP51580191A 1990-09-28 1991-09-24 ネットワークのトポロジ的特徴を探知する方法 Expired - Lifetime JP3315404B2 (ja)

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
EP90310699A EP0477448B1 (en) 1990-09-28 1990-09-28 Network monitoring device and system
AT91301204.3 1991-02-14
EP91301204A EP0480555B1 (en) 1990-09-28 1991-02-14 Method of ascertaining topology features of a network
AT90310699.5 1991-02-14

Publications (2)

Publication Number Publication Date
JPH05502566A JPH05502566A (ja) 1993-04-28
JP3315404B2 true JP3315404B2 (ja) 2002-08-19

Family

ID=26126816

Family Applications (1)

Application Number Title Priority Date Filing Date
JP51580191A Expired - Lifetime JP3315404B2 (ja) 1990-09-28 1991-09-24 ネットワークのトポロジ的特徴を探知する方法

Country Status (3)

Country Link
US (1) US5450408A (ja)
JP (1) JP3315404B2 (ja)
WO (1) WO1992006547A1 (ja)

Families Citing this family (49)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5297138A (en) * 1991-04-30 1994-03-22 Hewlett-Packard Company Determining physical topology across repeaters and bridges in a computer network
US5742760A (en) * 1992-05-12 1998-04-21 Compaq Computer Corporation Network packet switch using shared memory for repeating and bridging packets at media rate
US5437046A (en) * 1993-02-24 1995-07-25 Legent Corporation System and method for resolving the location of a station on a local area network
EP0615362B1 (en) * 1993-03-08 2002-10-09 Hewlett-Packard Company, A Delaware Corporation Network analysis method
JPH06282527A (ja) * 1993-03-29 1994-10-07 Hitachi Software Eng Co Ltd ネットワーク管理システム
US5594426A (en) * 1993-09-20 1997-01-14 Hitachi, Ltd. Network station and network management system
US5684796A (en) * 1994-05-03 1997-11-04 Bay Networks Group, Inc. Method and apparatus for determining and maintaining agent topology information in a multi-segment network
US5751967A (en) * 1994-07-25 1998-05-12 Bay Networks Group, Inc. Method and apparatus for automatically configuring a network device to support a virtual network
EP0738091A1 (en) * 1995-04-11 1996-10-16 Hewlett-Packard Company Discovery method for determining information about a signalling network
AU7558196A (en) 1995-11-16 1997-06-19 Nicholas Dawes Method of determining the topology of a network of objects
US5926462A (en) * 1995-11-16 1999-07-20 Loran Network Systems, Llc Method of determining topology of a network of objects which compares the similarity of the traffic sequences/volumes of a pair of devices
US6131112A (en) * 1996-05-17 2000-10-10 Cabletron Systems, Inc. Method and apparatus for integrated network and systems management
US6188675B1 (en) 1996-08-23 2001-02-13 International Business Machines Corporation System and method for self-identifying and configuring the nodes of a network
US6501753B1 (en) 1996-09-19 2002-12-31 Qwest Communications International, Inc. Architecture and method for using an advanced intelligent network (AIN) to reduce voice switch and trunk loading
US5778058A (en) * 1996-10-07 1998-07-07 Timeplex, Inc. Method of adding a new PBX and new PBX port to an existing PBX network
CA2218218A1 (en) * 1996-11-08 1998-05-08 At&T Corp. Promiscuous network monitoring utilizing multicasting within a switch
US5917808A (en) * 1997-01-17 1999-06-29 Fluke Corporation Method of identifying device types on a local area network using passive monitoring
US6115362A (en) * 1997-03-28 2000-09-05 Cabletron Systems, Inc. Method and apparatus for determining frame relay connections
US6298044B1 (en) 1998-03-31 2001-10-02 Hewlett-Packard Company Method and apparatus for determining if overloaded collision domains can be split to enhance network
EP0975122A1 (de) * 1998-07-22 2000-01-26 Siemens Schweiz AG Verfahren zum Ermitteln von Daten zum Erstellen eines Abbildes eines Netzes
CN1214567C (zh) * 1998-11-24 2005-08-10 尼克桑公司 用于采集和分析通信数据的装置及方法
US6108702A (en) 1998-12-02 2000-08-22 Micromuse, Inc. Method and apparatus for determining accurate topology features of a network
CA2268495C (en) 1998-12-16 2008-11-18 Loran Network Management Ltd. Method for determining computer network topologies
US6480471B1 (en) * 1998-12-21 2002-11-12 Hewlett-Packard Company Hardware sampler for statistical monitoring of network traffic
US6724729B1 (en) 1998-12-30 2004-04-20 Finisar Corporation System analyzer and method for synchronizing a distributed system
US7725570B1 (en) 1999-05-24 2010-05-25 Computer Associates Think, Inc. Method and apparatus for component to service mapping in service level management (SLM)
US20020021675A1 (en) * 1999-10-19 2002-02-21 At&T Corp. System and method for packet network configuration debugging and database
DE60135550D1 (de) * 2000-05-12 2008-10-09 Niksun Inc Sicherheitskamera für ein netzwerk
US7039696B1 (en) * 2000-10-31 2006-05-02 Hewlett-Packard Development Company, L.P. Method and system for processing data for network connections
US6904020B1 (en) * 2000-11-01 2005-06-07 Agilent Technologies, Inc. System and method for monitoring communication networks using data stream characterization
US7069343B2 (en) * 2001-09-06 2006-06-27 Avaya Technologycorp. Topology discovery by partitioning multiple discovery techniques
US7200122B2 (en) * 2001-09-06 2007-04-03 Avaya Technology Corp. Using link state information to discover IP network topology
US20030064718A1 (en) * 2001-09-28 2003-04-03 Haines Robert E. Selective communication in a wireless network based on peer-to-peer signal quality
US6826162B2 (en) * 2001-09-28 2004-11-30 Hewlett-Packard Development Company, L.P. Locating and mapping wireless network devices via wireless gateways
US7421466B2 (en) * 2001-10-29 2008-09-02 Hewlett-Packard Development Company, L.P. Dynamic mapping of wireless network devices
US7002960B1 (en) 2001-10-30 2006-02-21 At&T Corp. Traffic matrix computation for packet networks
US7743139B1 (en) 2001-10-30 2010-06-22 At&T Intellectual Property Ii, L.P. Method of provisioning a packet network for handling incoming traffic demands
US7571239B2 (en) 2002-01-08 2009-08-04 Avaya Inc. Credential management and network querying
US7027396B1 (en) * 2002-02-13 2006-04-11 At&T Corp. Traffic matrix computation for a backbone network supporting virtual private networks
US8578015B2 (en) * 2002-04-29 2013-11-05 Harris Corporation Tracking traffic in a mobile ad hoc network
GB2399708B (en) * 2003-03-20 2006-03-22 Parc Technologies Ltd Assisted determination of data flows in communication/data networks
US7426577B2 (en) * 2003-06-19 2008-09-16 Avaya Technology Corp. Detection of load balanced links in internet protocol netwoks
US8949304B2 (en) * 2003-08-20 2015-02-03 Apple Inc. Method and apparatus for accelerating the expiration of resource records in a local cache
US20050152283A1 (en) * 2004-01-08 2005-07-14 David Ritzenthaler Wireless device discovery
US7292541B1 (en) 2004-01-28 2007-11-06 Novell, Inc. Methods and systems for unnumbered network link discovery
US7729269B1 (en) * 2004-06-09 2010-06-01 Sprint Communications Company L.P. Method for identifying and estimating mean traffic for high traffic origin-destination node pairs in a network
US7756043B1 (en) 2004-06-09 2010-07-13 Sprint Communications Company L.P. Method for identifying high traffic origin-destination node pairs in a packet based network
DE602006019946D1 (de) * 2006-05-02 2011-03-17 Acterna France System und Verfahren zur Überwachung eines Datennetzwerksegments
US20110143768A1 (en) * 2009-12-14 2011-06-16 Lane Sean L Methods and apparatus related to region-specific mobile device and infrastructure detection, analysis and display

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5189414A (en) * 1986-09-30 1993-02-23 Kabushiki Kaisha Toshiba Network system for simultaneously coupling pairs of nodes
US4775973A (en) * 1986-10-22 1988-10-04 Hewlett-Packard Company Method and apparatus for a packet-switched network communications measurement matrix display
US5109483A (en) * 1987-06-15 1992-04-28 International Business Machines Corp. Node initiating xid exchanges over an activated link including an exchange of sets of binding signals between nodes for establishing sessions
JP2865675B2 (ja) * 1988-09-12 1999-03-08 株式会社日立製作所 通信ネットワーク制御方法
JPH02182057A (ja) * 1989-01-09 1990-07-16 Canon Inc ネツトワーク管理方式
US5088091A (en) * 1989-06-22 1992-02-11 Digital Equipment Corporation High-speed mesh connected local area network
JP2782683B2 (ja) * 1989-10-19 1998-08-06 三菱電機株式会社 Ｌａｎにおける通信方法およびノード装置
US5150360A (en) * 1990-03-07 1992-09-22 Digital Equipment Corporation Utilization of redundant links in bridged networks

Also Published As

Publication number Publication date
JPH05502566A (ja) 1993-04-28
WO1992006547A1 (en) 1992-04-16
US5450408A (en) 1995-09-12

Similar Documents

Publication Publication Date Title
JP3315404B2 (ja) ネットワークのトポロジ的特徴を探知する方法
EP0480555B1 (en) Method of ascertaining topology features of a network
CN112311614B (zh) 评估网络节点相关传输性能的系统、方法以及相关设备
EP1603272B1 (en) Communication network event logging systems and methods
US5337309A (en) Port arrival identification for computer network packets
EP0511851B1 (en) Determining physical topology across repeaters and bridges in a computer network
US7426577B2 (en) Detection of load balanced links in internet protocol netwoks
US6205122B1 (en) Automatic network topology analysis
US7864687B2 (en) Methods and apparatus for fault identification in border gateway protocol networks
US6538997B1 (en) Layer-2 trace method and node
US5293635A (en) Detection on a network by a mapping application of a relative location of a first device to a second device
CN112073234B (zh) 一种故障检测方法、装置、系统、设备及存储介质
USRE40148E1 (en) Switched connections diagnostics in a signalling network
CN110224883B (zh) 一种应用于电信承载网的灰色故障诊断方法
CN106612211A (zh) VxLAN中的路径探测方法，控制器和网络设备
US20090003334A1 (en) Analyzing a network with a cache advance proxy
JPH06348622A (ja) ネットワーク解析方法
JPH08116334A (ja) 複数のｌａｎで構成するネットワークにおける監視・障害解析方法及び装置
US6970429B2 (en) Method and apparatus for measuring internet router traffic
US20030033430A1 (en) IP flow discovery for IP probe auto-configuration and SLA monitoring
US5852600A (en) System and method for resolving substantially simultaneous bi-directional requests of spare capacity
WO1992022967A1 (en) Method and apparatus for testing a packet-based network
CN106130791B (zh) 基于服务质量的缓存设备服务能力遍历测试系统及方法
CN112468400A (zh) 一种故障定位方法、装置、设备和介质
AU666186B2 (en) A connectionless server for switching network

Legal Events

Date Code Title Description
R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

S111 Request for change of ownership or part of ownership

Free format text: JAPANESE INTERMEDIATE CODE: R313117

R360 Written notification for declining of transfer of rights

Free format text: JAPANESE INTERMEDIATE CODE: R360

R370 Written measure of declining of transfer procedure

Free format text: JAPANESE INTERMEDIATE CODE: R370

S111 Request for change of ownership or part of ownership

Free format text: JAPANESE INTERMEDIATE CODE: R313117

R350 Written notification of registration of transfer

Free format text: JAPANESE INTERMEDIATE CODE: R350

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20080607

Year of fee payment: 6

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20090607

Year of fee payment: 7

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20090607

Year of fee payment: 7

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100607

Year of fee payment: 8

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100607

Year of fee payment: 8

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110607

Year of fee payment: 9

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120607

Year of fee payment: 10

EXPY Cancellation because of completion of term
FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120607

Year of fee payment: 10