図面 (/)

技術 コンピュータ実施方法、コンピュータプログラム製品及びコンピュータ

出願人 エンチュイティリミテッド
発明者 ローパー,ジェフリー,ジョン
出願日 2014年4月17日 (6年8ヶ月経過) 出願番号 2016-508179
公開日 2016年7月7日 (4年5ヶ月経過) 公開番号 2016-519911
状態 特許登録済
技術分野 広域データ交換
主要キーワード クエリ信号 最終スイッチ モニタコンピュータ セグメントカウンタ プッシング 込みインデックス 出口インタフェース 初期ラベル
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2016年7月7日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

解決手段

本方法は、フォーカスデバイスの出口ポートを識別するコンピュータ実施方法であって、フォーカスデバイスに対するクエリメッセージを発生し、クエリメッセージは、フォーカスデバイスを識別するアドレスと、クエリキーとを含み、クエリメッセージがフォーカスデバイスで受信された場合、宛先にアドレス指定されたメッセージ用の出口ポートの識別を更に含む結果メッセージを戻すためにフォーカスデバイスで読み取り可能な命令を含むことと、結果メッセージを受信することと、結果メッセージを読み取ることと、結果メッセージが出口ポートを識別しない場合に、少なくとも1つの次のクエリメッセージを自律的に発生することと、を行い、フォーカスデバイスの出口ポートを識別するために充分なクエリメッセージを発生させる。

概要

背景

コンピュータネットワークは、多種多様な状況において、IT(情報技術)インフラストラクチャ基盤を形成する。このようなコンピュータネットワークは、相互接続された様々なタイプのデバイスを含んでいる。ネットワークの目的は、ネットワーク上で情報、アプリケーション、及びサービス等を配信するように、それらのデバイス間のメッセージフローサポートすることである。ネットワークを管理するために複数の技法を利用することができる。
この状況において、ネットワークの管理は、ネットワークを監視して障害点及びホットスポット等の他の問題のある領域を識別すること、並びに、その問題を修正できるようにネットワークの管理者及びユーザに情報を提供することを含む。ネットワークトポロジを提供するために利用可能な複数のツールがある。ネットワークトポロジは、ネットワーク内のデバイスがどのように物理的又は論理的に相互接続されるかを識別する。
このため、ある特定の単一のデバイスは、隣接デバイスに対して1つ以上の接続を有し得る。ネットワークを「発見する」コンピュータ化ツールが利用可能であり、それらは、ネットワーク内のデバイスの相互接続及びそれらのデバイスの性質を規定するネットワークトポロジを生成する。

概要

本発明は、コンピュータネットワーク内で接続されたフォーカスデバイスの出口ポートを識別するコンピュータ実施方法に関する。本方法は、フォーカスデバイスの出口ポートを識別するコンピュータ実施方法であって、フォーカスデバイスに対するクエリメッセージを発生し、クエリメッセージは、フォーカスデバイスを識別するアドレスと、クエリキーとを含み、クエリメッセージがフォーカスデバイスで受信された場合、宛先にアドレス指定されたメッセージ用の出口ポートの識別を更に含む結果メッセージを戻すためにフォーカスデバイスで読み取り可能な命令を含むことと、結果メッセージを受信することと、結果メッセージを読み取ることと、結果メッセージが出口ポートを識別しない場合に、少なくとも1つの次のクエリメッセージを自律的に発生することと、を行い、フォーカスデバイスの出口ポートを識別するために充分なクエリメッセージを発生させる。

目的

ネットワークの目的は、ネットワーク上で情報、アプリケーション、及びサービス等を配信するように、それらのデバイス間のメッセージフローをサポートすることである

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

コンピュータネットワーク内で接続されたフォーカスデバイス出口ポート識別するコンピュータ実施方法であって、前記コンピュータネットワークに接続されたモニタコンピュータにおいて実施され、前記フォーカスデバイスに対するクエリメッセージを発生し、前記クエリメッセージは、前記フォーカスデバイスを識別するアドレスと、宛先識別子に基づいて構築されたクエリキーとを含み、前記クエリメッセージが前記フォーカスデバイスで受信された場合には、前記宛先識別子において識別される宛先にアドレス指定されたメッセージ用の出口ポートの識別を更に含む結果メッセージを戻すために前記フォーカスデバイスで読み取り可能な命令を含むことと、前記モニタコンピュータにおいて結果メッセージを受信することと、前記結果メッセージを読み取ることと、前記結果メッセージが出口ポートを識別しない場合に、(i)前記コンピュータネットワーク内で接続された異なるデバイスのための異なるアドレスと(ii)前記モニタコンピュータにより選択された異なるクエリキーとの少なくとも1つを含む、少なくとも1つの次のクエリメッセージを自律的に発生することと、を行い、前記フォーカスデバイスの前記出口ポートを識別するために充分なクエリメッセージを発生させる、コンピュータ実施方法。

請求項2

前記異なるクエリキーは、前記フォーカスデバイスで異なる転送テーブルアクセスするために同一の宛先識別子に基づいて構築されている、請求項1に記載のコンピュータ実施方法。

請求項3

前記異なるクエリキーは、前記フォーカスデバイスにアクセスするために異なる宛先識別子に基づいて構築されている、請求項1に記載のコンピュータ実施方法。

請求項4

前記フォーカスデバイスがルーティングデバイスであり、前記クエリメッセージが前記ルーティングデバイスのルーティングテーブルに向けて送られ、前記結果メッセージが前記宛先識別子に対するルートタイプが間接的であることの指示を含み、前記結果メッセージを読み取るステップが、間接タイプを検出することと、異なる宛先識別子に基づいて構築されたクエリキーによって次のクエリメッセージを発生することとを含む、請求項3に記載のコンピュータ実施方法。

請求項5

前記結果メッセージが、前記コンピュータネットワークにおける前記フォーカスデバイスからのネクストホップのためのルーティングアドレスを含み、前記次のクエリメッセージが前記異なる宛先識別子としての前記ネクストホップのためのルーティングアドレスに基づいて構築されている、請求項3に記載のコンピュータ実施方法。

請求項6

前記次のクエリメッセージが、異なるクエリキーによって前記フォーカスデバイスを識別するアドレスを含む、請求項5に記載のコンピュータ実施方法。

請求項7

前記次のクエリメッセージが、同一のクエリキーによって前記異なるデバイスを識別する異なるアドレスを含む、請求項5に記載のコンピュータ実施方法。

請求項8

前記次のクエリメッセージが前記ネクストホップのためのルーティングアドレスによって識別される前記フォーカスデバイスにおけるマッピングテーブルに向けて送られ、前記マッピングテーブルが、ルーティングアドレスプロトコルに従った宛先識別子を、スイッチングアドレスプロトコルに従った宛先識別子に割り振る、請求項5から7の何れか1項に記載のコンピュータ実施方法。

請求項9

前記クエリメッセージにおける前記宛先識別子がルーティングアドレスプロトコルに従ったものであり、前記異なるクエリキーがスイッチングアドレスプロトコルに従ったものである異なる宛先識別子に基づいて構築されている、請求項1に記載のコンピュータ実施方法。

請求項10

前記少なくとも1つの次のクエリメッセージが、前記マッピングテーブルにクエリを実行して、前記フォーカスデバイス上のどのインタフェースから前記ネクストホップアドレスのためのルーティングアドレスとスイッチングアドレスとの間のマッピング導出したかを確認するように構築されている、請求項8に記載のコンピュータ実施方法。

請求項11

前記結果メッセージが出口ポートを識別する場合、ネットワークトポロジに基づいて前記出口ポートに接続されたデバイスを識別しようとする、請求項1に記載のコンピュータ実施方法。

請求項12

前記結果メッセージにおいて戻された前記出口ポートが接続されたデバイスを一意に識別しないと判定される場合、前記少なくとも1つの次のクエリメッセージが前記フォーカスデバイスの上位層及び/又は下位層のポートの関連付けを要求する、請求項11に記載のコンピュータ実施方法。

請求項13

出口ポート識別ユーティリティを実施するコンピュータプログラムを備えるコンピュータプログラム製品であって、コンピュータにより実行された場合に請求項1から12の何れか1項に記載のコンピュータ実施方法を実施する、コンピュータプログラム製品。

請求項14

コンピュータであって、少なくとも1つのフォーカスデバイスを含むネットワークと接続するためのネットワークインタフェースと、コンピュータプログラムを実行して、請求項1から12の何れか1項に記載のコンピュータ実施方法を実施するように構成されたプロセッサと、を有する、コンピュータ。

技術分野

0001

本発明は、コンピュータネットワークにおいてデバイスにおける出口ポート識別することに関する。

背景技術

0002

コンピュータネットワークは、多種多様な状況において、IT(情報技術)インフラストラクチャ基盤を形成する。このようなコンピュータネットワークは、相互接続された様々なタイプのデバイスを含んでいる。ネットワークの目的は、ネットワーク上で情報、アプリケーション、及びサービス等を配信するように、それらのデバイス間のメッセージフローサポートすることである。ネットワークを管理するために複数の技法を利用することができる。
この状況において、ネットワークの管理は、ネットワークを監視して障害点及びホットスポット等の他の問題のある領域を識別すること、並びに、その問題を修正できるようにネットワークの管理者及びユーザに情報を提供することを含む。ネットワークトポロジを提供するために利用可能な複数のツールがある。ネットワークトポロジは、ネットワーク内のデバイスがどのように物理的又は論理的に相互接続されるかを識別する。
このため、ある特定の単一のデバイスは、隣接デバイスに対して1つ以上の接続を有し得る。ネットワークを「発見する」コンピュータ化ツールが利用可能であり、それらは、ネットワーク内のデバイスの相互接続及びそれらのデバイスの性質を規定するネットワークトポロジを生成する。

課題を解決するための手段

0003

本発明者らは、(ルーティングプロトコルの詳細についてのクエリ(query)実行とは対照的に)フォーカスデバイスにクエリを実行して、それが仮想パケットとどのような関係を持つかを判定することによって、デバイスからの出口ポートを識別するための手法を開発した。第1のクエリが使用可能な答えを戻さない場合、モニタコンピュータにおいて実行されるユーティリティによって次(第2)のクエリを自動的に構築する。

0004

本発明の一態様によれば、コンピュータネットワーク内で接続されたフォーカスデバイスの出口ポートを識別するコンピュータ実施方法が提供される。このコンピュータ実施方法は、コンピュータネットワーク内で接続されたフォーカスデバイスの出口ポートを識別するコンピュータ実施方法であって、上記コンピュータネットワークに接続されたモニタコンピュータにおいて実施され、上記フォーカスデバイスに対するクエリメッセージを発生し、上記クエリメッセージは、上記フォーカスデバイスを識別するアドレスと、宛先識別子に基づいて構築されたクエリキーとを含み、上記クエリメッセージが上記フォーカスデバイスで受信された場合には、上記宛先識別子において識別される宛先にアドレス指定されたメッセージ用の出口ポートの識別を更に含む結果メッセージを戻すために上記フォーカスデバイスで読み取り可能な命令を含むことと、上記モニタコンピュータにおいて結果メッセージを受信することと、上記結果メッセージを読み取ることと、上記結果メッセージが出口ポートを識別しない場合に、(i)上記コンピュータネットワーク内で接続された異なるデバイスのための異なるアドレスと(ii)上記モニタコンピュータにより選択された異なるクエリキーとの少なくとも1つを含む、少なくとも1つの次のクエリメッセージを自律的に発生することと、を行い、上記フォーカスデバイスの上記出口ポートを識別するために充分なクエリメッセージを発生させる。

0005

このコンピュータ実施方法は、モニタコンピュータにインストールされたコンピュータプログラムの形態の出口ポート識別ユーティリティを実行することにより実施可能である。また、本発明は、コンピュータにインストールされた場合に上記で規定した方法を実施するコンピュータプログラム製品も提供する。本発明は、更に、少なくとも1つのフォーカスデバイスを含むネットワークに接続するためのインタフェースと、上記で規定した方法を実施するコンピュータプログラムを実行するように構成されたプロセッサと、を有するモニタコンピュータを提供する。

0006

上記異なるクエリキーは、上記フォーカスデバイスで異なる転送テーブルアクセスするために同一の宛先識別子に基づいて構築することができる。あるいは、上記異なるクエリキーは、上記フォーカスデバイスにアクセスするために異なる宛先識別子に基づいて構築することができる。

0007

上記フォーカスデバイスがルーティングデバイスである場合、上記クエリメッセージは、上記ルーティングデバイスのルーティングテーブルに向けて送ることができる。その場合、結果メッセージは、宛先識別子に対するルートタイプが間接的であることの指示を含むことができ、結果メッセージを読み取るステップは、間接タイプを検出することと、異なる宛先識別子に基づいて構築されたクエリキーによって次のクエリメッセージを発生することとを含む。

0008

結果メッセージが、上記コンピュータネットワークにおける上記フォーカスデバイスからのネクストホップ(next hop)のためのルーティングアドレスを含む場合、上記次のクエリメッセージは、上記異なる宛先識別子としてのネクストホップのためのルーティングアドレスに基づいて構築することができる。上記次のクエリメッセージは、異なるクエリキーによって上記フォーカスデバイスを識別するアドレスを含むことができる。あるいは、上記次のクエリメッセージは、同一のクエリキーによって異なるデバイスを識別する異なるアドレスを含むことができる。

0009

上記次のクエリメッセージは、上記ネクストホップのためのルーティングアドレスによって識別される上記フォーカスデバイスにおけるマッピングテーブルに向けて送ることができ、マッピングテーブルは、ルーティングアドレスプロトコルに従った宛先識別子を、スイッチングアドレスプロトコルに従った宛先識別子に割り振る(マッピング)。

0010

上記クエリメッセージにおける宛先識別子がルーティングアドレスプロトコルに従ったものである場合、上記異なるクエリキーがスイッチングアドレスプロトコルに従ったものである異なる宛先識別子に基づいて構築することができる。これによって、いわゆるレイヤ2/レイヤ3調査(layer2/layer 3 investigation)をモニタコンピュータで自律的に実行することができる。

0011

上記少なくとも1つの次のクエリメッセージが、マッピングテーブルにクエリを実行するように構築されている場合、これは、上記フォーカスデバイス上のどのインタフェースから上記フォーカスデバイスがネクストホップアドレスのためのルーティングアドレスとスイッチングアドレスとの間のマッピングを導出したかを確認するようにセットアップすることができる。

0012

上記結果メッセージが出口ポートを識別する場合、このコンピュータ実施方法は、結果メッセージにおいて戻された出口ポートが接続されたデバイスを一意に識別しないと判定するように構成することができる。その場合、自律的に発生された次のクエリメッセージは、上記フォーカスデバイスの上位層及び/又は下位層のポートの関連付けを要求することができる。

0013

各デバイスに送信されるクエリは、各デバイスにクエリを実行して、上記宛先識別子により識別される宛先にアドレス指定された仮想メッセージのためにデバイスが用いる出口ポートを表す1つの出口ポートの識別子を明らかにするように構成されている。クエリが実行されるデバイスのネットワーク内の位置に応じて、所定のクエリについての宛先識別子は、ターミナルデバイスの宛先識別子か又はそれ以外とすることができる。これは、デバイスがルータである場合に、クエリを受信した時にそのアクティブなルーティングテーブル内に何があるかを問い合わせることによって実行可能である。上記宛先識別子は、例えばIP(インターネットプロトコル)アドレス等、ルーティングテーブル又はARPテーブルに用いられる転送アドレスである。

0014

クエリ自体は、モニタコンピュータからクエリ対象のデバイス(フォーカスデバイス)に送信されるメッセージ又は信号内に収容することができる。クエリメッセージ又は信号は、経路が決定されるメッセージフローを構成しない。各クエリは、宛先識別子(転送アドレス)を含み、これは、フォーカスデバイスの転送テーブルにクエリを実行して、クエリの受信時にフォーカスデバイスが決定する必要がある場合にその宛先にアドレス指定された仮想メッセージをどのように処理するかを明らかにする。
したがって、フォーカスデバイスは、その宛先にアドレス指定された実メッセージにその時使われるはずの直接(immediate)出口ポートを識別する結果を戻す。クエリは、ネットワークがアクティブでありメッセージフローが所定の位置にある状態で送信することができる。
しかしながら、メッセージフロー自体がアクティブでない場合にクエリを送信することも可能である。つまり、この技法は、どちらの状況でも使用可能である。

0015

クエリがメッセージ又はパケットの形態である場合、例えばメッセージが宛先IPアドレスを有するSNMPメッセージであり得る場合、クエリは、それ自体の宛先アドレスを搬送し、モニタコンピュータからフォーカスデバイスまでネットワーク上で配信することができる。その場合、クエリメッセージの宛先アドレスはフォーカスデバイスのものである。これは、クエリ自体に含まれる宛先識別子(転送アドレス)と同じものではない。代替的な構成では、1つ又は複数のクエリ信号を、モニタコンピュータから、CLI又はXMLAP機構等の直接接続を介してフォーカスデバイスに送信することができる。

0016

ユーティリティは、本明細書において「推論的なキーイング(speculative keying)」と定義する技法を用いて向上させることができる。これによって、推論的なキーの有界リスト(bounded list)を発生して、トラフィック転送テーブルのクエリ実行を簡略化すると共に、そのようなキーに必要なコンピュータネットワーク上のトラフィックを軽減することが可能となる。推論的なキーの小さい有界リストを発生させることによって、全ての要求を順次でなく並列発行することができる(すなわち、一般的なクエリメッセージに複数のクエリキーを含ませることができる)。

0017

転送アドレスを表すビットシーケンスを、埋め込みインデックスを表すビットシーケンスと論理的に組み合わせることによって、宛先識別子(転送アドレス)を各埋め込みインデックスと組み合わせることができる。

0018

転送テーブルがルーティングテーブルである場合、ルーティングテーブル内の各インデックスは、ネットマスクである。クエリメッセージ内で用いるキーは、転送アドレスを表すビットシーケンスを、ネットマスクを表すビットシーケンスと論理的に組み合わせることで発生させた一意のキーのみから選択することができる。転送アドレスは、IP(インターネットプロトコル)アドレスとすればよく、転送テーブルは、レイヤ3ルーティングデバイス用のものとすればよい。

0019

推論的なキーイング技法は、埋め込みインデックスがルータ等のトラフィック転送デバイスにおけるARPテーブルのインタフェースインデックスである場合にも適用可能である。

0020

ユーティリティが特に有用であるのは、特定のメッセージフローについて相互接続デバイスのネットワークに採用される経路を識別するために本発明者等が開発した新規の手法において用いられる場合である。この技法は、「前もって」収集された最少量のデータ、すなわちスタティックなネットワークトポロジとエンドホスト位置(どのクライアント及びサーバがどのアクセススイッチエッジスイッチに接続されているか)だけに頼っており、そのような極めてダイナミックなデータの必要に応じて、要求されるものは実行中に極めて選択的に収集する。
最新のダイナミック環境では、直ちにすなわちリアルタイムエンドツーエンド経路を計算する能力は応用範囲が広い。大規模な実世界ネットワークと共に用いる場合、データ収集及びその処理は、アルゴリズムが実用的な価値を持つために非常に迅速でなければならない。

0021

特定のデバイスにおける挙動を、「ホップごとの振舞いPHB:per hop behaviour)」と呼ぶ。これは、この出口ポート識別ユーティリティの特に有益な点である。PHBは単独でエンドツーエンド経路を提供することはできない。しかしながら、パケットがデバイスを出ていく特定のインタフェースを知ることは、そのインタフェースにどのデバイス及びインタフェースが接続されているかわからない場合に有用であり得る。PHBと組み合わせてネットワークトポロジを用いることで、アプリケーションフローについてネットワークを通るエンドツーエンド経路を直接計算することが可能となる。

0022

ネットワークトポロジの決定は、多くの方法で実行することができる。ネットワーク接続性の優れた表現を与えるために個別に又は組み合わせて利用可能な技法は、例えば以下を含む。
シスコ検出プロトコル(CDPCisco Discovery Protocol)
リンクレイヤ検出プロトコル(LLDP:Link Layer Discovery Protocol)
・SoNMP(SynOptics Network Management Protocol)
スパニングツリープロトコル(STP:Spanning Tree Protocol)
・IP Traceroute
・IPv6近隣探索(IPv6 Neighbour Discovery)
・ユーザによる追加/変更/削除

0023

ネットワークのトポロジを知ることは、極めて有用であるが、起こり得る全ての問題に対する解決策を提供するわけではない。ネットワークは、遠い地理的位置間で長距離にわたって又は複数の相互接続デバイスを用いた極めて複雑なネットワークにおいて、アプリケーション及びサービスの配信をサポートするインフラストラクチャを提供するためにますます用いられるようになっている。ネットワーク管理者及びユーザは、必ずしもネットワークの全ての詳細を知ることでなく、ネットワーク上でのアプリケーション及びサービスの配信の性能の理解に関心を持つようになっている。したがって、いわゆる「エンドツーエンド」モニタリングはいっそう一般的なものとなっている。「エンドツーエンド」モニタリングでは、ソースデバイスから宛先デバイスへのメッセージフローを伴うアプリケーションは、そのソース及び宛先デバイス間で配信される際に性能が監視される。性能パラメータを用いてネットワークでの起こり得る障害について推定又は推測することができるが、パラメータはそういった障害の位置についての具体的な情報を与えないので、直接に解決策を示すわけではない。

0024

多くの場合、ソースデバイスは特定のサービスを提供するサーバであり、宛先デバイスは、ネットワークを介してサーバに接続されてそのサービスを用いる必要があるクライアント端末である。本明細書において用いる場合、「デバイス」という言葉は、ネットワークにおいて接続可能ないかなるデバイスも包含することを意図している。「サーバ」という言葉は、サービス又はアプリケーションの配信を担当するデバイスを示すために用いる。「クライアント」という言葉は、そのアプリケーション又はサービスに依存するデバイス(ユーザベースの又は別の依存したマシンもしくはサーバ)を示すために用いる。

0025

アプリケーションの性能が低下していることがわかった場合に問題がどこにあるか推測する際の大きな困難は、そのアプリケーションのためのメッセージフローにより採用された可能性のあるネットワーク内の経路についての理解の不足である。ネットワークは、エンドポイントデバイスを接続するために多くのタイプのネットワークデバイス(例えばルータ、スイッチ、ファイアウォールサーバ負荷分散装置ロードバランサ)等)に依存するので、いかなる所定のソースエンドポイントについても、そのエンドポイントからのメッセージがどのようにネットワーク内を所定の宛先エンドポイントまでルーティングされるかを示すことは極めて難しい。このような経路決定の複雑さは、複数の代替経路冗長経路ロードバランシング等を用いることで更に悪化する。

0026

特定のパケットがネットワーク内をどのようにルーティングされるかを予測する試みが行われてきた。このような予測は、ネットワークトポロジの複雑なモデルと、特定のデバイスがネットワーク内でどのように振舞うかに関するデバイスごとの指示に基づく。ネットワークデバイスは極めて高性能である場合があり、特定のデバイスにおけるルーティング戦略を決定するために複数の複雑なアルゴリズムが開発されてきた。更に、ルーティング戦略は、ネットワークに影響を与えるトラフィック及びその他の環境的な要素(他のデバイスの障害等)に依存し得る。ルーティング戦略を決定するためデバイスによって利用可能である複雑なアルゴリズムは、例えば以下を含み得る。
入口インタフェース及び入口インタフェース技術
パケットヘッダ(L2、L3、MPLS、ATM等)
・スタティック及び直接接続ルート
共有ルーティングテーブル(BGP、OSPFRIP、EIGRP等の完全な知識。アクティブなネイバーリンク状態ルートコスト、ルート重量等)
・学習されたMAC転送テーブル
アクセス制御リスト
・ネットワークオーバーレイ技術(例えばMPLS、802.1qVLAN)等
ループ回避技術 例えばPVSTP
トンネリングプロトコル(MPLS、IPSEC、SSL、GRE)
ロードバランス冗長リンク
・デフォルトゲートウェイ

0027

しかしながら、過去には原則として所定のパケットが次にどの特定デバイス転送されるか予測できたとしても、これには収集に時間がかかる膨大な量のデータが必要であり、ルーティングデバイス動作の即時性によってすぐに時代遅れになり得る。更に、このデータを獲得するだけでも、ネットワークデバイス及びネットワークの双方に著しい負荷がかかっていた。

0028

本明細書に記載するユーティリティは、複数の有用なネットワーク解析技法を可能とする。これによってオンデマンドの経路決定を行えるので、特定のアプリケーションについて経路を決定しようとする管理者は、ある程度瞬時にモニタコンピュータに質問し、経路の結果を受信することができる。

0029

これは、複数の経路の発見を可能とする。すなわち、ネットワーク内に環境変化があるので、ルーティングデバイスはそういった変化に応じて異なるようにメッセージフローをルーティングし得る。したがって、経路を識別するための第1のクエリセットが第1の経路を記録するのに対し、第2のクエリセットは、第2の経路を識別することがあり、これは第1及び第2のクエリセットが時間的に極めて近い場合であっても当てはまる。共通のエンドポイント(すなわち同一のソースデバイス及び同一の宛先デバイス)間の複数の経路についての情報をグラフ又は画像によって提示して、各経路を特定のメッセージフローのために採用した場合の経路の性質だけでなく時間の割合をユーザに示すことができる。これが容易に達成可能であるのは、クエリ自体がネットワークの著しいオーバーヘッドとならないので、性能に大きな影響を及ぼすことなく複数のクエリセットのディスパッチ発信)が可能だからである。

0030

本方法では、迅速な合理的(legitimate)経路変更の検出が可能である。すなわち、ネットワークを調節して経路を変更することができ、これを検出して視覚的なグラフィカルユーザインタフェースでユーザに対してフラグ表示することができる。

0031

共通のソースデバイスと宛先デバイスとの間に複数の経路がある場合、経路は異なる待ち時間を有する可能性がある。時として、インテリジェントなルーティングを実行するルーティングデバイスは、特定のメッセージが経路から経路に頻繁にスイッチングする「ルートフラップ」として知られる現象を起こすことがある。例えば、そのような経路変更がエンドツーエンド待ち時間に及ぼす影響のため、及びそのような「ジッター」がVoIP(Voice over IP)電話会話に及ぼす影響のため、ネットワーク管理者は、そのような発生を識別することが有用であり得る。

0032

本方法を用いて経路障害の位置を特定することができる。すなわち、この方法の好適な実施形態においては、デバイスが宛先デバイスとして識別されるまで、クエリをディスパッチし、結果を受信及び解析して、次のデバイスを識別する。しかしながら時として、ネットワークに障害があるために、ネットワークは、メッセージフローを宛先デバイスまで配信しない。この方法は、エンドツーエンド経路を横断できなくなるまで経路に沿って動作することによってその状況を識別することができ、続いて、このネットワーク位置を管理者に通知することができる。

0033

更に、本方法は、ネットワークトポロジに基づいた推定を用いて、その経路における次のデバイスで再出発する可能性を与えることができる。次に、その障害点から宛先デバイスに到達するまで再び経路発見(経路識別)法を採用すればよい。このように、モニタリングコンピュータが認知性を持たないネットワーク部分(例えば適切な管理インタフェースを持たないデバイス、又は異なる組織に属するデバイス)は迂回することができ、経路解析を継続する。

0034

また、本方法は、非対称ルーティング識別を可能とする。ソースデバイスと宛先デバイスとの間のメッセージフローが、その方向に応じて異なる経路を採用することは珍しくない。すなわち、ソースデバイスから宛先デバイスへのメッセージフローにはフォワード経路を用い、宛先デバイスからソースデバイスまでは異なる戻り経路を用いることができる。

0035

経路は、メモリに記録するか、モニタコンピュータに記憶するか、又はモニタコンピュータによりアクセス可能である。経路記録は接続デバイスとインタフェースのセットを含む。これは、2つのエンドポイント間に配列したデバイス(ネットワークコンポーネント)の一覧の形態で提示することができる。これにより、イベント通知報告、SLA(サービスレベル合意)を含むネットワーク経路可用性モニタリング故障デバイスの報告、ハイデバイスCPU、ローデバイスメモリ、ポート輻輳等、及びインパクト分析キャパシティプランニング、「what−if」分析)を含む事前対応ネットワーク管理が可能となる。

0036

ネットワークにより配信されるアプリケーション又はサービスとネットワークデバイス又はコンポーネント自体とのマッピングを経路の識別によって確認可能であることは顕著な利点である。これは、ネットワークの管理において大きな前進となる。

0037

本発明をよりいっそう理解し、これをどのように実行し得るかを示すため、ここで一例として添付図面を参照する。

図面の簡単な説明

0038

ネットワークの概略図である。
経路発見アルゴリズムの説明図である。
経路発見アルゴリズムの説明図である。
経路発見アルゴリズムの説明図である。
経路発見アルゴリズムのフローチャートである。
1つの発見された経路を示す説明図である。
線形ルーティングテーブルの構造を示す説明図である。
宛先アドレスを複数のルートマスクと組み合わせることから得られる結果セットを示す説明図である。
ARPテーブルの構造を示す説明図である。
モニタコンピュータの概略図である。
レイヤ3ルータの概略図である。
レイヤ2スイッチの概略図である。
モニタコンピュータで実行されるユーティリティのフローチャートである。
モニタコンピュータで実行されるユーティリティのフローチャートである。
モニタコンピュータで実行されるユーティリティのフローチャートである。
モニタコンピュータで実行されるユーティリティのフローチャートである。
ループ実行プログラムのフローチャートである。
ループ実行プログラムの終端プロセスを示すフローチャートである。
ループ実行プログラムのオプションCを示すフローチャートである。
ループ実行プログラムのオプションSを示すフローチャートである。
オプションSのプロセスの続きを示すフローチャートである。
ループ実行プログラムのオプションのプロセスを示すフローチャートである。
図17のプロセスの続きを示すフローチャートである。
ループ実行プログラムのオプションcのプロセスを示すフローチャートである。
オプションAのプロセスを示すフローチャートである。
VLANヒントを取得するためのプロセスを示す説明図である。
接続ポート及び接続デバイスを取得して経路記録に記憶するためのプロセスを示す説明図である。
接続ポート及び接続デバイスを取得して経路記録に記憶するためのプロセスを示す説明図である。
前出のオプションのいくつかで利用される、ルートを見つけるための繰り返しプロセスを示すフローチャートである。
プライミングプロセス(priming process)を示す説明図である。
プライミングプロセスを示す説明図である。
プライミングプロセスを示す説明図である。
繰り返しルート探索プロセスで用いられるルート探索プロセスを示すフローチャートである。
フォーカスデバイスの転送データベースエントリ検索するためのプロセスを示す説明図である。

実施例

0039

図1は、ネットワークの概略図である。このネットワークは、複数の異なる地理的位置にわたっている。各端部の地理的位置には、エンドポイントデバイス及びネットワークデバイス又はノードがある。ネットワークデバイスは、ルータ及びスイッチを含む。ネットワークのコアは、複数のネットワークデバイスを備える。ロンドン表記した地理的位置について考えると、クライアント端末2は、エンドポイントデバイスとして機能することができる。同様に、サーバ4は、エンドポイントデバイスとして機能することができ、プリンタ6は、エンドポイントデバイスと見なすことができる。
同様のデバイスが、異なるレイアウトのパリ及びニューヨークの地理的位置に示されている(ニューヨークにはサーバファーム又はデータセンタが示されている)。ニューヨークの位置では、複数のサーバ8が重要なアプリケーション又はサーバエンドポイントデバイスを表すことに留意すべきである。

0040

図1に示すネットワークは、一例として与えていることを理解すべきである。使用可能なネットワークが多種多様に存在し、本発明は、いかなる相互接続デバイスのネットワークにおいても使用可能である。特に、エンドポイントデバイス及び特定のネットワークデバイス又はノードの性質は様々に変動し得る。開示されている特定のネットワークでは、ネットワークデバイスは、レイヤ3又はレイヤ2のデバイスとすることができる。

0041

開放型システム間相互接続OSI:Open Systems Interconnection)モデルは、通信ステムのプロトコルを特徴付けることができる7つのレイヤを定義している。ここで記載される経路発見アルゴリズム(path finding algorithm)は、レイヤ2及びレイヤ3において利用可能な情報を用いてネットワーク経路を計算する。

0042

レイヤ2(データリンクレイヤ)で動作するデバイスは、直接隣接したデバイスの情報を有し、あるレイヤ2デバイスから次のレイヤ2デバイスへのパケットの取得(レイヤ2MAC(メディアアクセス制御)アドレスに基づいて)を担っている。

0043

レイヤ3(ネットワークレイヤ)で動作するデバイスは、ネットワーク内のあるポイントからネットワーク内の別のポイント(多くの場合、数十又は数百のデバイスを隔てている)へのパケット伝搬を担っている。
所定のレイヤ3経路にどのデバイスが参加するべきか(本明細書では「レイヤ3ホップ」と称する)を計算するため、レイヤ3デバイスは、ルーティング情報交換し、ルーティングプロトコルを用いて最も望ましい経路(複数の経路)を計算する。経路内の連続したレイヤ3デバイス間でパケットを渡すために、レイヤ2で動作しているデバイスが用いられる。多くの場合、各レイヤ3デバイス間には複数のレイヤ2デバイスが存在する(本明細書では「レイヤ2ホップ」と称する)。

0044

したがって、大きいネットワークは、効果的に複数のセグメントに分割され、その各々は通常、レイヤ3デバイスにより接続された複数のレイヤ2デバイスを含んでいる。

0045

図9は、レイヤ3ルーティングデバイスの概略図である。このデバイスは、例えば制御コードファームウェアを実行するマイクロプロセッサ、又は他の何れかの適切な実施の形態のコントローラ90を備えている。コントローラ90は、後に図5を参照して更に詳しく検討するルーティングテーブル92にアクセスすることができる。
レイヤ3ルーティングデバイスは、ポートPi/Poを有する。各ポートは、図1のネットワークに示すように、物理リンクに接続されている。この表記において、Piは「入口」ポートを示し、Poは「出口」ポートを示す。これは表記の便宜上のものであり、実際には、通常デバイス入口ポート又は出口ポートとして専用のポートを有するわけではなく、それらが入口であるか出口であるかは、その時に転送しているデータに依存する。多くのポートはいつでも出口及び入口として機能する。

0046

入口ポートPiに到達するパケットは、例えばバス94を介してコントローラ90により読み取られるIP(インターネットプロトコルアドレス)のような宛先識別子を有し得る。コントローラ90は、ルーティングテーブル92にアクセスし、そこから導出された情報に基づいて、着信パケット送り出すルーティングスイッチ96を制御する。
次に、ルーティングスイッチ96は、ルーティングテーブル内の情報に応じて、着信パケットを適切な出口ポートPoにルーティングする。このルーティングデバイスは、以降のルーティングのためにレイヤ3アドレスをレイヤ2のアドレスに割り振るマッピングテーブル91を含む。
このようなルーティングデバイスの動作は、当技術分野において既知であるので、本明細書でこれ以上は説明しない。この状況では、モニタコンピュータからリンクを介して入口ポートPiに到達したパケットをコントローラ90で傍受(intercept)することによって、そのようなパケットによりルーティングテーブルのクエリが実行され得ることに留意すべきである。そのようなクエリパケットは、更なるルーティングのためルーティングスイッチ96に供給されるのではなく応答を発生し、この応答がルーティングデバイスから出力され、出口ポートからネットワークを介して問い合わせ側の対象物に戻される。
この場合、その問い合わせ側の対象物は、モニタコンピュータ16である。ネットワークを介して伝達される全てのパケット(クエリパケットを含む)は、ソース及び宛先アドレスを含む。すなわちクエリパケットは、モニタコンピュータに対応したソースアドレスと、クエリが実行されるデバイスに対応した宛先アドレスと、を有する。応答を送信する必要がある場合、ソースアドレス及び宛先アドレスを交換して、ソースアドレスをクエリ実行対象デバイスとすると共に、宛先アドレスをモニタコンピュータとする。

0047

図10は、レイヤ2スイッチをより図式化した説明図である。レイヤ3ルーティングデバイスと同様に、レイヤ2スイッチは、ポートPi/Poを有し、その各々は、例えば図1のネットワークに示すように、物理リンクに接続されている。上述のように、ポートは通常、入力専用又は出力専用ではない。入口ポートPiの着信パケットは、スイッチ100に送り出される。スイッチ100は、パケット内の宛先識別子(通常はヘッダ)に基づいてどのようにパケットをルーティングするかを決定するため、レイヤ2転送データベース(FDB)102にアクセスすることができる。レイヤ2転送データベースは、着信パケットの識別子を、このパケットを転送すべき出口ポートに割り振る。
既に説明したように、OSIモデルによれば、レイヤ3ルーティングデバイスの識別子は、IPアドレスであり、レイヤ2デバイスの識別子は、MACアドレスである。

0048

レイヤ3デバイスの場合と同様に、レイヤ2は当技術分野において既知であり、したがって、本明細書でこれ以上は検討しない。しかしながら、レイヤ3デバイスと同様に、更にまた、それらは入口ポートPiでパケット内のクエリを受信し、出口ポートPoにおけるレイヤ2スイッチからの出力に、そのクエリに対する応答を発生できることに留意すべきである。したがって、クエリパケット自体は、スイッチにおいてルーティングされるのではなく、クエリ側のデバイス(この場合はモニタコンピュータ16)に返される応答を発生する。

0049

スイッチにおけるスイッチコントローラ101は、トラフィックの転送及び応答の発生を担っている。

0050

更に最新のデバイスの中には、レイヤ3及びレイヤ2の機能を実行可能なものがある。

0051

以下に記載する本発明の実施形態は、所定のソースデバイスと所定の宛先デバイスとの間でメッセージフローが進む経路を識別する方法を提供する。例えばエンドポイントXをソースデバイスと考え、エンドポイントYを宛先デバイスと考えることができる。図1のネットワークを見ると、既に述べたように、何れかの所定時間かつ所定の環境条件のセットのもとで、それらのエンドポイント間でネットワーク内のどの経路を採用するかを確定することは決して些細なタスクではない。
図1は、そのような経路を発見し記録することができる経路発見プログラムを実行するモニタコンピュータ16を示す。図8は、モニタコンピュータ16をより図式化した説明である。コンピュータ16は、マイクロプロセッサ80を備え、これは、このプロセッサにより実行されるコードが記憶されたメモリ82にアクセスすることができる。この場合、そのコードは、経路発見プログラムを含む。メモリ82は、経路発見プログラムにより生成された経路記録81も記憶している。コンピュータは、ユーザインタフェース(UI)84を有し、これは、マウス又はキーボード等のユーザ入力デバイスと、ユーザに対して情報を表示するためのディスプレイと、を含むことができる。特に、本明細書において更に詳しく検討するように、ユーザインタフェース84において、経路発見プログラムの後の警告(アラート)又は経路発見プログラムに関する情報をユーザに表示することができる。図2aから図2cは、経路のステップを示す。次にこれらについて説明する。

0052

水準のアルゴリズムは「フォーカスデバイス」の概念を用いる。フォーカスデバイスは、仮想パケットを次にどこに送信するか(すなわち、どのインタフェースから仮想パケットを送信するか)に関して現在クエリが実行されているデバイスである。アルゴリズムは、ソースデバイスから開始し、各フォーカスデバイスを順番に評価することによって、ターミナルデバイス(すなわちパケットの最終的な宛先)へと進む。
デバイスがレイヤ3で動作している場合、レイヤ3のネクストホップ(NHL3)行きのパケットを送信するためにどのインタフェース(出口ポート)を用いるかについてクエリが実行される。デバイスがレイヤ2で動作している場合、次レイヤ3ホップのレイヤ2(MAC)アドレス(NHL2)行きのパケットを送信するためにどのインタフェース(出口ポート)を用いるかについてクエリが実行される。フォーカスデバイスの応答をネットワークトポロジと関連付けて用いて、経路内の次のデバイスを決定することができる。このようにして、アルゴリズムは、レイヤ2デバイスを用いながらレイヤ3経路に沿って動作して、連続したレイヤ3ノード間をナビゲートする。

0053

主要なアルゴリズムを開始する前に、ソースデバイス及びターミナルデバイスの位置を特定する。これは単純でない場合があり、これを達成するための技法について後に検討する。

0054

主要なアルゴリズムに従って第1ホップの位置を特定する。経路をシードし(seed)、ループカウントをゼロに設定する。ループリミットが、経路識別ループ(後に検討する)を実行する回数を定める。

0055

[レイヤ3における第1ホップの探索]
レイヤ3における最初のネクストホップ(ソースデバイスからのネクストホップ)(NHL3)を見つけることで、第1ホップの位置を特定する。以下の説明では「クエリ」という言葉を頻繁に用いる。クエリは、後で更に詳しく説明するように発生され構築される。クエリの目的は、クエリがアドレス指定されるフォーカスデバイスから、ネクストホップアドレス及び出口ポートの位置を特定することである。
最初のNHL3アドレスは、まず宛先IPアドレスを用いてソースデバイスXにクエリを実行することで決定できる。すなわち、ソースデバイスのルーティングテーブルにNHL3及び出口ポートについてクエリを実行する試みが行われる。
ルートが見つからず、かつソースデバイスがレイヤ3アクセススイッチを有する場合、宛先IPアドレスを用いて、このレイヤ3アクセススイッチにNHL3についてのクエリを実行する。これが成功しない場合、NHL3を確認するためにソースデバイスのデフォルトゲートウェイにクエリを実行する。これが成功しない場合、宛先IPアドレスを用いてアクセススイッチにデフォルトゲートウェイについてのクエリを実行する。NHL3アドレスが見つからない場合、これは障害と見なされるが、アルゴリズムが失敗したことを意味するのではなく、経路内の障害点がこのポイントで識別されたことを意味する。あるいは、NHL3が見つからなかった他の理由がある場合もある。

0056

[経路のシード(seed)]
経路をシードするため、ソースデバイスの位置が特定されたら、これを経路に追加する。すなわち、ソースデバイスの出口インタフェースの位置が特定され経路に追加される。ソースデバイスのルーティングテーブルからNHL3が見つかった場合、このNHL3アドレスに対するソースデバイス出口インタフェースは、経路に追加される。後に説明するように、レイヤ3アドレス(NHL3)に対応したレイヤ2アドレス(NHL2)を確認することができる。ソースデバイスのルーティングテーブルからNHL3の出口ポートが見つからない場合、NHL2についてのソースデバイスのレイヤ2転送テーブルは、出口ポートを見つけるために用いられる。出口ポートが見つかったら、その出口ポートを経路に追加する。

0057

[経路発見アルゴリズムの概要]
図2aにおいて、モニタコンピュータ16からソースデバイスXにディスパッチされたクエリは、直接の矢印として示されるが、実際にこれを実施するには、図1のネットワークにおいてモニタコンピュータ16がソースデバイスXにアドレス指定されたメッセージ又はパケットを発行すればよい。
上述したように、クエリは、宛先ポイントYのレイヤ3アドレスであるターミナルIP(宛先IP)のためのネクストホップIP(及び出口ポート)についてソースデバイスに質問する。その目的は、ソースデバイスXに、NHL3及びNHL3のための出口ポート(ターミナルIPアドレス)を含む応答を提供させることである(図3のステップS1及び図2aを参照)。

0058

上述したように、ソースデバイスが必要な情報を供給できない状況があり得る。第1の「フォーカス」デバイスを取得するための上述した他の可能性は、接続されたアクセススイッチに対してレイヤ3ルーティング情報についてのクエリを実行すること(アクセススイッチがレイヤ3スイッチである場合)を含み、これが失敗した場合、アルゴリズムは、接続されたアクセススイッチに対して、デフォルトゲートウェイ及び第1のNHL3として用いられるデフォルトゲートウェイのIPアドレスについてのクエリを実行する。

0059

ステップS2では、NHL3アドレスからネクストホップレイヤ2(MAC)アドレスを決定し、NHL2をこのMACアドレスに設定する。これは、L3アドレスをL2アドレスに割り振るマッピングテーブル91にクエリを実行することで達成可能である。そのようなマッピングテーブルの1つは、ARPテーブルである(他には「直接マッピング」及び近隣探索が含まれる)。これは、後述のARPクエリを用いた、ソースデバイスARP、次L3ホップデバイスARP、又はグローバルキャッシュARPであり得る。
ステップS1では、識別した出口ポートを経路記録に追加する(S1A)。ステップS3では、キャッシュしたエンドホスト位置(スイッチCAMクエリからの)を用いて開始ネットワークスイッチ(及びポート)を見つけ、フォーカスデバイスとして設定する。
ステップS4では、キャッシュしたエンドホスト位置(スイッチCAMクエリからの)を用いてターミナルネットワークスイッチを見つける。開始スイッチは、経路記録に追加される。

0060

本方法は、現時点で、経路識別ループに入る準備ができた状態にある。ステップS5では、NHL2が既知であるか否かを判定する。既知である場合、ループは、ステップS5Aに進む。既知でない場合、プロセスは、ステップS5Bを実行して、フォーカスデバイス又はNHL3デバイスにおけるARPクエリによってNHL2を決定する。
図7を参照して、レイヤ3アドレスをレイヤ2アドレスに相関付けるためのクエリの発生について更に詳しく検討する。簡単に言うと、クエリを実行するデバイスについて、ネットワークトポロジから、又はデバイス自体のインタフェーステーブルからインタフェースインデックス(ifIndex)をウォークする(walk)ことによって、インデックスのリストが取得される。デバイスの各ifIndexは、デバイスへのクエリに含めるためのキーのセットを生成するために、NHL3アドレスと組み合わされる。これにより、これらのキーを含むクエリが構築され、フォーカスデバイスに送信される。フォーカスデバイスは、ゼロ又は成功応答(1)を生成する。

0061

NHL2を決定するための上述の2つの技法が失敗した場合、グローバルARPは、アクセスされる。ステップS5Aでは、アドレスNHL3が現在のフォーカスデバイス上にあるか否かを判定する。

0062

NHL3が現在のデバイス上にない場合、ステップS6において、プロセスは、出口ポートを得るためNHL2についてのレイヤ2FDBエントリを見つけるためのクエリをディスパッチする。レイヤ2でのクエリの発生については、後述する。これが成功した場合、出口ポートを経路記録に追加し(S6A)、キャッシュしたトポロジ3を用いてリンク終端のポート及びデバイスを見つけ(S7)、デバイスを経路に追加し(S7A)、リンク端部で位置特定したばかりのデバイスをフォーカスデバイスに設定する(L2ホップ)。ステップS6A、S7、及びS7AをL2ホップと称することがあり得る。この点については図2bを参照のこと。
ステップS5Aでは、フォーカスデバイスはデバイスAである。これは、レイヤ2FDBエントリを見つけるためのクエリを受信し、出口ポートを戻す。そのリンク端部にあると判定されたデバイスは、デバイスBであり(図2c)、これは、依然として宛先IPアドレスに設定されているNHL3のクエリを受信する。

0063

レイヤ2FDBエントリが見つからなかった場合、又はS5AにおいてNHL3がフォーカスデバイス上でホストされていると判定された場合、ステップS8でルートクエリを実行して、フォーカスデバイス上で宛先IPアドレスへのL3ルートが見つかったか否かを判定する。ルートクエリは、単一ルート又は再帰的ルートクエリであり得る。これらについては後に説明する。これは、ネクストホップIP及び出口インタフェースを確定する。L3ルートが見つからない場合、壊れた経路が示され、プロセスは停止する(S8A)。

0064

ステップS9(L3ホップ)では、ルーティングテーブル出口インタフェースを経路に追加し、NHL3を新しいネクストホップIPアドレスに設定し、プロセスはデバイスに対しクエリを実行してNHL3のレイヤ2アドレスを確認する。NHL2を決定できない場合、NHL2を「未知」に設定する。
ステップS10では、現在のNHL3アドレスを宛先IPアドレスと比較する。NHL3が宛先IPでない(すなわち経路発見アルゴリズムがまだ最終L2セグメント上にない)場合、ステップS11では、キャッシュしたトポロジを用いてリンク端部のポート及びデバイスを見つけ、デバイスを経路記録に追加し、このデバイスをフォーカスに設定する。次に、プロセスは、フォーカスデバイスがターミナルデバイスであるか問い合わせる(S12)。フォーカスデバイスがターミナルデバイスでない場合、プロセスはステップS5に戻るが、ステップ9で設定したNHL3及びNHL2を用いる。

0065

[終端(termination)]
ターミナルデバイスに到達し、ターミナルポート及び宛先サーバを経路に追加すると、アルゴリズムは終了する。他の終端条件により、アルゴリズムのループ処理を無期限に阻止する。経路の各繰り返しでは、スイッチフラグに、ルートフラグを偽に設定することで繰り返しが開始する。L2ホップが行われると(S7)、スイッチフラグは真に設定される。L3ホップが行われると(S9)、ルートフラグは真に設定される。
既に述べたように、出口ポートをフォーカスデバイスから決定し、ネットワークトポロジを用いて結合されたデバイス(attached device)及び結合されたデバイスの入口ポートを見つける。各繰り返しについて、「フォーカスデバイス、NHL2、NHL3」の組み合わせを記憶する。

0066

フォーカスデバイス、NHL2、又はNHL3が変化し、「フォーカスデバイス、NHL2、NHL3」の新しい組み合わせが見つかった場合、ループ検出イベントを生成し、ループを停止する。ループ限度に到達しておらず、ルーティング又はスイッチングの何れかが実行され(すなわちルートフラグ又はスイッチフラグが真である)、更に、フォーカスデバイスがターミナルデバイスに等しくない場合、再び繰り返しを行う。繰り返しのたびに、繰り返しループ限度に到達したか否かを査定する。到達した場合、アルゴリズムは終端する。

0067

繰り返しが終了すると、フォーカスデバイスがターミナルデバイスである場合は、ターミナルデバイスは、経路に追加される。フォーカスデバイスがターミナルデバイスでないがアルゴリズムが停止した場合、経路発見アルゴリズムは予想外の位置で終端するのでエラーが報告される。ターミナルデバイスがアクセススイッチである場合、アクセススイッチ出口ポートを「宛先の位置特定」(S4)から経路に追加し、アクセススイッチ出口ポートから導出された宛先デバイスを経路に追加する。そして、アルゴリズムは終了する。ターミナルデバイスが宛先デバイスと等しい場合、アルゴリズムは終了する。次に、アルゴリズムの詳細について更に詳しく検討する。

0068

[具体例]
図4は、経路発見アルゴリズムの動作の1つの結果を示す。すなわちこれは、経路発見アルゴリズムがネットワークにクエリを実行した時に、宛先デバイスYにアドレス指定されたソースデバイスXからのデータパケットがネットワーク上で進むルートを提供する。経路は、経路記録の一部を形成するデバイスA〜Jを含むように示されている。経路記録は、それらのデバイスの各々からの入口ポート及び出口ポートを含む。

0069

再び、図1の元のネットワークを見ると、図4に示す経路記録の第1の部分は図1のネットワークから導出されたと考えられる。対応する文字を用いて、前のスイッチ又はルーティングデバイスにより選択されるデバイスを示す。経路発見アルゴリズムが動作した時、ルーティングデバイスBは、パケットをスイッチCに送信すると決定している。
しかしながら、本発明を用いない場合、これをリアルタイムで達成することは極めて難しい。ルーティングデバイスBには同様に、パケットをコアネットワーク内のルータFにルーティングするオプションがあった。宛先Yにアドレス指定された仮想パケットに基づいて、リアルタイムで(又はある程度はリアルタイムで)ルーティングデバイスBにクエリを実行することにより、ルーティングデバイスBは、そのアドレスを有する実パケットが到達した場合に行われていたはずの決定を戻す。
ルーティングデバイスBがパケットをスイッチCにディスパッチすると確認し、それから、スイッチCがその出口ポートの遠端でルーティングデバイスDに接続していると確定することにより、C及びDは経路記録81に追加されている。
このように、パケット識別アルゴリズムは、ネットワーク内のデバイスにクエリを実行した時に仮想パケットが採用する経路内を1つずつ進んでいく。ルーティングデバイスDに隣接した囲み枠は、NHL3及びNHL2の設定を示す。
すなわち、NHL3は、現在ルーティングデバイスDでアクティブであるルーティングテーブルに基づいてデバイスDの遠端デバイスとして確定されているデバイスEのIPアドレスに設定されている。NHL2は、デバイスEのARPエントリについてデバイスDにクエリを実行することにより、デバイスEのMACアドレスとして確定されている。

0070

[ネットワークトポロジ]
上述したように、ネットワークトポロジは、ネットワークデバイス相互接続性及びエンドホスト位置の双方を含む。ネットワークトポロジ3は、ポートツーポート(port−to−port)接続の詳細を与えるトポロジサーバによって提供することができる。このため、あるデバイスにおいて出口ポートが識別されると、トポロジで識別されるポートツーポート接続を用いて、接続されたデバイスの入口ポートを確認することができる。
出口ポート及び入口ポートの双方を経路記録に追加することができる。トポロジサーバは、グローバルCAM、グローバルARP、及びデバイス認証情報も提供する。更に、トポロジに記録された各デバイスについて、インタフェースインデックス(IfIndex)リスト及びVLAN(仮想ローカルエリアネットワーク)リストがあることが好ましい。VLANデバイスについては、まだ検討していない。それらについては本明細書で更に検討する。
モニタコンピュータ16に応答が戻されると、モニタコンピュータは、処理レイヤ2が応答した場合に以下の順序でトポロジ3にクエリを実行する。この状況では、レイヤ2応答は、レイヤ2スイッチデバイスからの出口ポートを識別した応答である。クエリ実行の順序は、CDP、LLDP、STP、及びSONMP、IPv6 NDである。

0071

[ソースデバイスの位置特定]
上述したように、経路内の第1のデバイス(ソースデバイスに接続されたデバイス)の位置特定は、必ずしも単純ではない。一実施形態では、モニタコンピュータ16は、アルゴリズムを実施して、まず接続されたホストとしてソースを見つけようとし、これが失敗するとネットワークデバイスとしてソースを見つけようとする。
接続されたホストとしてソースを見つけようとする場合、ソースIPのレイヤ2(MAC)アドレスについて、ソースデバイスにクエリを実行する。これは、ステップS5Bで上述したようなフォーカスデバイスに対するクエリと同じ方法で達成可能である。すなわち、プロセスは、ソースIPアドレスについてのARPエントリを見つけるためのクエリをディスパッチする。

0072

ソースデバイスからのレイヤ2アドレスがない場合、トポロジサーバにおけるグローバルキャッシュARPテーブルにクエリを実行する。上述の実施形態では、これらはARPテーブルとされるが、レイヤ3アドレスをレイヤ2アドレスに割り振るいかなるテーブルも利用可能である。
ソースIPアドレスに対応するMACアドレスが見つかった場合、このMACアドレスからのトラフィックを認識したポートを見つけるためにトポロジサーバのグローバルキャッシュレイヤ2転送テーブルにクエリを実行することで、ソースIPのMAC位置についてトポロジサーバにクエリを実行する。
トポロジサーバは、複数の一致(ソースMACが複数のポート上で認識された)を除去すること、トランクとフラグされたポート、過剰な数のMACを有するポート(アクセススイッチポートのFDBエントリは典型的に単一の「認識された(seen)」MACアドレスを有する)、ネットワーク間トポロジを有するポート(例えばポートがCDP隣接情報を有する場合、これはアクセススイッチ上のポートではあり得ない)等を取り除くことによって、一意のソースMAC位置を戻すことが予想される。

0073

接続されたホストとしてソースが見つからない場合、ネットワークデバイスとしてソースを見つける試みを行う。これは、全ての管理されたネットワークデバイス上で見つかる全てのIPアドレスについてトポロジサーバにクエリを実行して、IPアドレスがネットワークデバイス上にあるか否かを調べることにより達成可能である。そうである場合、そのネットワークデバイスをフォーカスデバイスとして設定する。

0074

[宛先デバイスの位置特定]
同様の考察が宛先デバイスの位置特定にも当てはまる。まず、接続されたホストとして宛先デバイスを見つける試みを行う。これが失敗すると、ネットワークデバイスとして宛先を見つける試みを行う。接続されたホストとして宛先デバイスを見つけるため、そのレイヤ2アドレスについて宛先デバイスにクエリを実行し、又はトポロジサーバにおいてグローバルキャッシュレイヤ3−レイヤ2マッピングテーブルにクエリを実行する(上述のソースデバイスと同様)。次に、トポロジサーバ上のグローバルキャッシュレイヤ2転送テーブルにクエリを実行して、このMACからのトラフィックを認識したポートを見つける(これもソースデバイス位置に関しての説明と同様)。

0075

上記が失敗した場合にネットワークデバイスとして宛先を見つけるため、全ての管理されたデバイス上で見つかる全てのIPアドレスについてトポロジサーバにクエリを実行して、IPアドレスがネットワークデバイス上にあるか否かを調べればよい。次に、ネットワークをターミナルデバイスとして設定することができる。

0076

[ホップごとのユーティリティ]
経路発見アルゴリズムを実施するため、モニタコンピュータ16は、上述したようなコンピュータプログラムを実行する。このコンピュータプログラムは、「ホップごとの(per hop)」クエリを処理するユーティリティを提供する。すなわち、経路発見アルゴリズムは、モニタコンピュータからフォーカスデバイスにクエリをディスパッチし、トポロジへのアクセスに使用可能な出口ポートをフォーカスデバイスから受信することに頼っている。これは、必ずしも単一のクエリによって達成することはできない。
上述のように、アルゴリズムは、レイヤ3における最初のネクストホップを必要とする(NHL3)。ユーティリティは、宛先IPアドレスを用いて、NHL3及び出口ポートについてソースデバイス上のルーティングテーブルに対するクエリの実行を試みる。ルートが見つからなければ、アクセススイッチがレイヤ3スイッチである場合、このアクセススイッチ上のルーティングテーブルにクエリを実行する(これはNHL3についてソースデバイスに接続された第1のデバイスである)。
ここで、ルートが見つからない場合、NHL3のデフォルトゲートウェイについてソースデバイスにクエリを実行する。ルートが見つからない場合、デフォルトゲートウェイについて第1のデバイスにクエリを実行する。
(上述したように)ルーティングテーブルにクエリを実行してNHL3を見つけるため、後に説明する推論的なキーイング技法を用いてルーティングデバイスにクエリを実行することによって、当該IPアドレス(「探索対象の」IPアドレス)のためのルートを見つける。
ルートが見つかったが、出口ポートが特定されない場合、ネクストホップIPアドレスを戻し、NHL3として用いる。ルートが見つかり、出口インタフェースifIndexがゼロより大きい場合、出口ポートをNHL3アドレスと共に戻し、出口ポートは、経路に追加される。ルートが見つかり、出口インタフェースifIndexがゼロに等しい場合、ユーティリティは、探索対象のIPを(前のクエリからの)ネクストホップIPに設定し、(後に説明するような)推論的なキーイングを用いてデバイスにクエリを実行して探索対象のIPのためのルートを見つけることによって、何度も繰り返す。これは、戻されるifIndexがゼロ以外の値になるまで繰り返される。

0077

探索対象のIPのためのルートを見つけるステップは、推論的なキーイング技法を用いてルートエントリを戻す。ルートエントリが見つかると、ユーティリティは、ipRouteNextHop.NetworkAddressからのネクストホップアドレスに対してポーリング(例えば、通信回線共有する各端末に順次問い合わせて端末を特定すること)する。ユーティリティは、ipRouteIfindex.NetworkAddressからの出口インタフェースに対して、及びipRouteType.NetworkAddressに対してもポーリングする。ipRouteTypeが「直接(direct)」である場合、探索対象のIPをネクストホップに設定する。IPルートタイプ「直接」は、これがネットワークセグメントに直接接続されていることを示すからである。

0078

デバイス上のルーティングテーブルから複数の一致が戻される可能性がある。この場合、例えばデバイスがトラフィックのロードバランシングを担っている場合、複数のルートが用いられているか否かを判定することが適切である。単一のルートのみがアクティブに用いられている場合、このアクティブなルートが決定されるはずである。
複数のルートが用いられている場合、この時点で経路を分割することができ、経路記録は、この時点以降に見つかる全てのルートに適用される経路発見アルゴリズムの結果を含むことができる。
多くの場合、デバイスにおけるルーティングのための複数のオプションは、デバイスが様々な測定基準メトリクス)に基づいてインテリジェントにルーティングされることを示している。これらの測定基準にもクエリを実行し、モニタコンピュータでの記録のために戻すことができる。

0079

また、ユーティリティは、フォーカスデバイスにおいてレイヤ3−レイヤ2マッピングテーブル91にクエリを実行して、レイヤ2における最初のネクストホップ探索を担っている。
レイヤ2アドレスが見つからず、フォーカスデバイスがソースデバイスである場合、ユーティリティは、アクセススイッチにクエリを実行する(これがレイヤ3スイッチである場合、レイヤ3からレイヤ2へのマッピングを提供するはずである)。レイヤ2アドレスが見つからない場合、ユーティリティは、トポロジサーバ3上のグローバルキャッシュARPテーブルにクエリを実行する。デバイス上のレイヤ2アドレスについてのクエリは、ステップS5Bを参照して上述したように実行される。

0080

NHL3アドレスがフォーカスデバイス上にない場合、ユーティリティは、レイヤ2アドレスNHL2のための出口ポートについてフォーカスデバイスに対してポーリングする。出口ポートNHL2についてフォーカスデバイスに対してポーリングするステップは、VLAN(仮想ローカルエリアネットワーク)に特定的なポーリングを含む。
すなわち、これは、デバイスが、トポロジ3に従って、デバイスにおける記録どおりに、どのVLANに参加しているかを確定するステップを含む。これらのVLANは、特定のVLANについての転送テーブルのエントリの探索に役立てるために用いられる(FDBは多くの場合、どのVLANに関連しているかに従って分割される。例えば、VLANごとのスパニングツリープロトコル(PVSTP:Per VLAN Spanning Tree Protocol)では、各VLANが一致を見つけようとする状況でFDBクエリを実行する必要がある)。

0081

(特定的なVLAN又はネイティブVLANを用いて)出口ポートがレイヤ2FDBから見つからない場合、ユーティリティは、ipNetToMediaPhysAddress71に対するポーリングにより、どのインタフェースがARP記録からNHL2に向かうかを見つけようとする(図7)。すなわち、ユーティリティは、どのインタフェースからレイヤ2とレイヤ3との関係が学習されたかを学ぼうとする。

0082

ユーティリティは、レイヤ2アドレスを用いて出口ポートを見つけたら、この出口ポートを経路記録に追加し、トポロジサーバ3を用いて出口ポートに結合されたリモートポートを見つける。このリモートポートは、次のデバイス上の入口ポートとして記録される。

0083

[ポートチャネル多重化ポート]
リモートポートが見つからない場合、又は出口ポート名が上位層もしくは下位層レイヤのポートの使用を命令する場合、ユーティリティは、下位層レイヤのポート又は上位層レイヤのポートをチェックする。すなわち、仮想経路出力が物理ポートにマッピングされる状況があり得る。経路発見アルゴリズムを成功させるため、トポロジサーバにアクセスするための物理出口ポートを識別する必要がある。
下位層レイヤのポートのチェックによって下位層レイヤのポートの存在が明らかになった場合、これらの下位層レイヤのポートを出口ポートとして用いることができる。トポロジサーバにアクセスして、出口ポートに結合されたリモートポート(次のデバイスの入口ポート)を見つける。この時点で、経路は複数の別個の経路に分割され、それらの各々はこの時点から別々にトレースされる。

0084

上位層レイヤのポートが識別された場合、上位層レイヤのポートを出口ポートに用いる。トポロジサーバを用いて、この上位層レイヤの出口ポートに結合されたリモートポートを見つける。

0085

[ネクストホップ]
ルートフラグ及びスイッチフラグフラッグを偽に設定する。トポロジサーバ又はフォーカスデバイスに対する直接クエリを用いて、フォーカスデバイスがそのポートの何れかでNHL3IPアドレスをホストするか否かを確認する。これがNHL3 IPアドレスをホストする場合、ユーティリティは続いて、推論的なキーイング技法を用いることにより、宛先IPへのルートについてフォーカスデバイスルーティングテーブルにクエリを実行する。
ユーティリティが候補ルートの位置を特定したら、レイヤ3からレイヤ2へのマッピングについてフォーカスデバイス(又はグローバルキャッシュARPテーブル)にクエリを実行することで、次のレイヤ2アドレスNHL2を設定し、ルートフラグを真に設定する。NHL3が宛先IPと等しい場合、これは、ユーティリティが宛先に最も近い最後のレイヤ3デバイスに到達したことを示すので、ネクストホップはレイヤ2ホップであり、もうこのデバイスを進める必要はない。
したがって、ユーティリティは候補ルートの出口ポートを経路に追加する。NHL3が宛先IPと等しくない場合、これが最終的なレイヤ2セグメントでないことが示され、候補ルートの出口ポートを経路に追加する。

0086

この繰り返しの間にルーティングが行われなかった(ルートフラグがまだ偽のままである)場合、ユーティリティは、レイヤ2アドレスNHL2のための出口ポートについてフォーカスデバイスに対してポーリングする。出口ポートNHL2についてフォーカスデバイスに対してポーリングするステップは、VLAN(仮想ローカルエリアネットワーク)に特定的なポーリング(上述のような)を含む。
(特定的なVLAN又はネイティブのVALNを用いて)レイヤ2FDBから出口ポートが見つからない場合、ユーティリティは、ipNetToMediaPhysAddress71に対してポーリングすることによりARP記録からどのインタフェースがNHL2に向かうかを見つけようとする。
すなわち、ユーティリティは、どのインタフェースからレイヤ2とレイヤ3の関係が学習されたかを学ぼうとする。
ユーティリティは、レイヤ2アドレスを用いて出口ポートを見つけたら、この出口ポートを経路記録に追加し、トポロジサーバ3を用いて出口ポートに結合されたリモートポートを見つける。このリモートポートは、次のデバイス上の入口ポートとして記録される。FDBクエリ又はARPクエリを用いて出口ポートが見つかったら、スイッチフラグを真に設定する。

0087

トポロジサーバにクエリを実行した場合にリモートポートが見つからない場合、又は出口ポート名が上位層もしくは下位層レイヤのポートの使用を命令する場合、上述のように下位層レイヤ又は上位層レイヤのポートをチェックする。出口ポートが見つかった場合、これを経路に追加し、ポートを含むデバイスを経路に追加し、フォーカスデバイスをリモートデバイスに設定する。

0088

「ネクストホップ」ステップは、繰り返し数既定限度に達するまで、又は経路が終了に達する(すなわちスイッチングもルーティングも行われない)まで、繰り返される。

0089

プロセスが以前に識別したターミナルデバイスにおいて終了し、そのデバイスがアクセススイッチである場合、出口ポートは、「宛先の位置特定」から経路記録に追加され、宛先デバイスは経路記録に追加される。ターミナルデバイスが宛先デバイス自体である場合、ユーティリティは終了する。

0090

図11aから図11dは、モニタコンピュータで実行されるユーティリティの動作のフローチャートを示す。

0091

[ロードバランサ(サーバ負荷分散装置)]
上述したように、フォーカスデバイスがターミナルデバイスである場合、ターミナルデバイスを宛先と共に経路記録に追加する。ターミナルデバイスがロードバランサである場合、ロードバランサのための仮想IP−サーバプールマッピングを取得する。これによって、ロードバランサのためのサーバ−物理サーバのマッピング(割り振り)を識別することができる。経路は、「ルート」経路である限り(ロードバランサデバイスまで)維持される。次に、各物理サーバIPアドレスについて、ロードバランサから物理サーバIPアドレスまで追加の経路発見ユーティリティを実行し、各追加経路先頭に「ルート」経路を付け加える。

0092

[ルーティングテーブルクエリ]
経路アルゴリズムを特に効率的なものとする要因の1つは、ルーティングデバイスに対するクエリを効率的に発生する、すなわち、著しいオーバーヘッドなく短時間でルーティングデバイスが応答することができるクエリを発生する能力である。
図5は、SNMPによってアドレス指定可能な線形ルートテーブルの構造を示す。特定の宛先へのルートを確定するため、ipRouteDestがルートテーブル内への必要なインデックスである。
これは図5において48で示されている。テーブル内の対象となるエントリは、出口インタフェースを規定するipRouteIfindex50、ネクストホップのIPアドレス(ネクストホップIP)を規定するipRouteNextHop52、及びルーティングエントリのタイプ(無効/直接/間接)を規定するipRouteType54である。通常、テーブル内へのアクセスには、ipRouteMask56の知識が必要である。これによって特定のネットワークIPの位置を特定することができる。
しかしながら、図5に見られるように、ipRouteMask自体は、ipRouteEntryに埋め込まれているので、クエリ内でセットアップされることは知られていない。必要なのは、テーブルへのインデックスを表すIpRouteDestキー48を見つけるため、以下に対する一致を見つけることである。
<対象のIP>&<ipRouteMask.X> == <ipRouteDest.X>

0093

図27は、プロセスを示す。

0094

本発明者等により観察されたように、IpRouteMaskには、33通りのみの可能性がある(/32.../0)。すなわち、255.255.255.255、255.255.255.254、255.255.255.252、...0.0.0.0.である。
IPアドレス内のゼロの数のために、これら複数により同一のIPアドレスについて複製ネットワークIDが生成される。全ての可能な33通りのネットマスクのリストを生成し(Z2)、IPアドレスに適用する(Z3)。
図6は、IPアドレス10.44.1.213=OA.2C.01.D5=0000 1010 0010 1100 0000 0001 1101 0101に対する33の全てのネットマスクの適用を示す。

0095

これは、12個の固有値(標識された32、31、29、27、25、24、23、13、12、10、6、4)を生成する。したがって、ここでは、ルートを見つけるために12個の固有値のSNMPクエリ(これは単一クエリパケットに提示することができる)を生成するだけでよい。
ステップZ4からZ5において、デフォルトルート許可されているかを判定し、これに応じてネットワークを除去した後、12個の固有値の結果をフォーカスデバイスのルートテーブルと照合して、一致が見つかったら、必要な要素ipRouteIfIndex(egressIfindex)、ipRouteNextHop、及びipRouteTypeを検索し(Z12)、モニタコンピュータ16に対する応答で戻す。

0096

この結果のインタフェースをegressInterfaceに設定する(Z13)。

0097

ルートを見つけるために必要なクエリ数の削減を、本明細書において「推論的なキーイング」と称する。これによって、極めて効率的なリアルタイムのルートテーブルクエリ処理の実行が可能となる。

0098

実ルーティングテーブルを調べる場合、所定のIPアドレスについて見つかったルートが有効な出口インタフェースを持たずにネクストホップアドレスを与えるのみであることは珍しくない。これらの場合、ネクストホップアドレスをルーティングテーブルの次のクエリで用いて、そのネクストホップアドレスのための出口インタフェースを取得する試みを行う。このネクストホップアドレスの再使用を、出口インタフェースが取得されるまで繰り返す。

0099

この手法によれば、第1のステップにおいて単一ルート探索クエリは、概説したように推論的なキーイングを用いて、指定されたIPアドレス(IPx)のためのルーティングエントリを見つける。関連するipRouteTypeが「直接」である場合、IPx(及びipRouteIfindexx)は、ネクストホップとしてモニタコンピュータへの応答で返される。すなわち、これは直接接続されているので、レイヤ3ネクストホップを有しない。

0100

関連するipRouteTypeが直接でない場合、ipRouteNextHop及びipRouteIfIndexは、モニタコンピュータへの応答で返される。

0101

ルート探索(経路発見)プロセスでは、クエリの実行が更に難しいIPクラスレドメイン間ルーティング(IP Classless Inter−Domain Routing)テーブルも考慮している。
この場合、ステップZ10の結果としてIPアドレスが得られないならば、プロセスは、ステップZ14に移り、IPcidrRouteDest+ネットワークアドレス+ネットマスクを用いて、SNMPクエリ(Get Next(次を取得))をデバイスに発行する。
結果がIPアドレスでない場合、プロセスは、ループを戻ってステップZ7に移り、再びステップZ8、Z9、Z10と進んでいく。結果がIPアドレスである場合、戻されたOIDからネットワークアドレスを抽出する。
次に、OIDのネットワークアドレスがクエリのネットワークアドレスに一致するか否かを判定する。一致しない場合、プロセスはステップZ7に戻る。一致する場合、見つかったルートを真に設定し、戻されたクエリのOIDにCIDRキーを設定し、IPcidrRouteDestすなわちCIDRルートテーブルに対するインデックスを除去する。次に、プロセスは、SNMPクエリが、ネクストホップ、出口ifIndex、及びルートタイプを取得することを可能とする。

0102

図に示すように、FindRouteIterative(ルート探索繰り返し)プロセスにおいて、必要なIPアドレス(IPx)についてFindRoute(ルート探索)ステップF1を行う。ルートが見つからない場合、失敗を戻す。ルートが見つかったが出口インタフェースがない場合、ipRouteNextHopを戻す。ルートが見つかると共にipRouteIfindexがゼロに等しい場合、ipRouteNextHopのIPアドレスについてFindRouteIterativeステップを行う。これには同一の4つの結果があり得る。

0103

推論的なキーイングは、大きいデータセットの効率的なクエリ処理のための特に良好な技法であるが、その主な適用範囲は、部分的なキーが既知である導出キーによってインデックスが付されたデータにクエリを実行する場合である。これは、SNMPルートテーブル解析及びSNMPARPテーブルクエリ処理の関係で特に有用となるからである。しかしながら、例えばCLIアクセス及びXMLAPIのような他のクエリ処理技法を用いて、迅速なネットワークデバイスごとの転送挙動も確認することができる。

0104

[ARPクエリ]
ここで図7を参照して、推論的なキーイングを用いてARPテーブルにクエリを実行するための効率的な技法について説明する。クエリの発生については、後で図7を参照して更に詳しく検討する。クエリを実行するデバイスについて、ネットワークトポロジから、又はデバイス自体のインタフェースインデックス(IfIndex)を移動することで、Ifindexのリストを取得する。
デバイスの各ifIndexをNHL3アドレスと組み合わせて、デバイスへのクエリに含ませるキーのセットを発生する。これにより、これらのキーを含むクエリが構築され、フォーカスデバイスに送信される。フォーカスデバイスは、ゼロ又は1の成功応答を発生する。
図7は、ipNetToMediaEntryテーブルフォーマットを示し、これは原則としていかなる所定のIPアドレスについてもMACアドレスを決定することができる。どのインタフェースからARPエントリが学習されたかが既知でない限り、特定のIPアドレスについて、一意のエントリを見つけることはできないので、各IPアドレスをデバイス上の全てのifIndexと組み合わせることによって推論的なキーイングを用いる。
つまり、IPアドレスをifIndexと組み合わせることで各クエリキーを生成することができる。このように、SNMPクエリの数はデバイス上のインタフェースの数であり、これは典型的にデバイス上のARPエントリ数よりはるかに少なく、したがって、極めて高効率である。

0105

推論的なキーイングでは、単一のクエリメッセージ内に複数のクエリキーを含ませることができる。

0106

次に、経路識別のための代替的なアルゴリズムについて説明する。図12を参照して、ループ繰り返しプロセスを説明する。メインループへのエントリは、図12の上部でエントリ矢印4により示されている。エントリ矢印4は、後で説明するプライミングプロセスの終了時の状態を示す。エントリ状態は以下を含む。
<オプション、フォーカスデバイス、NHL3、NHL2、VLAN>

0107

これらのアイテムは、後で説明するプライミングプロセスによって設定される。これらを以下では「状態変数」と称する。「オプション」と呼ぶ状態変数は、配列したループオプションのシーケンスを有する。本例では、配列シーケンスはCSRAcrを備える。

0108

「VLAN」と呼ぶ状態変数は、経路のこのポイントで仮想パケットに現在タグ付けしているVLANの仮想ローカルエリアネットワーク識別子(数字)である。

0109

ループのステップL01では、第1のオプション(リストの先頭)を選択して実行する。これらのオプションについては後述する。オプションの実行後、リストオプションの先頭により実施される処理ステップの後に、プロセスは、リターンポイントL02に戻って新しい状態を生成する(L03)。この状態が以前に発生したか否かを判定し(L04)、発生していない場合は状態を記憶する(L05)。状態が以前に発生している場合は「ループ発見」報告を発生し、ループ限度をゼロに設定する。これはループを終了させる結果となる。

0110

ステップL07では、ループ限度をデクリメントする。ループ限度がゼロ以下である場合、又はオプションシーケンス内にもう利用可能なオプションがない場合、又はフォーカスデバイスがターミナルデバイスと等しい場合、「終端は真に等しい」条件を設定する。
ステップL08では、終端条件のチェックを実行し、終端条件が真である場合、メインループは終端する。他の場合、ステップL03で生成した新しい状態を用いてメインループエントリポイントに戻る。

0111

ループ繰り返しにおける各オプションの実行において、オプション実行の第1のステップは、オプション状態変数において配列シーケンスからそのオプションを除去することであることに留意すべきである。

0112

オプションの処理ステップの終了時、オプション及び処理ステップの結果に応じて、そのオプションは、シーケンス内にリセットされるか又は永久に除去される可能性がある。

0113

また、オプションの処理ステップ実行において、他の状態変数(フォーカスデバイス、NHL2、NHL3、VLAN)を個別に又は全体的に変更可能であることにも留意すべきである。何れかの状態変数を変更すると新しい状態が生じ、これは次のループ繰り返しのための新しいエントリ状態を構成することができる。

0114

これより図13を参照してメインループプロセスの第2の部分について説明する。ステップL09では、予想されたターミナルデバイスに到達したか否かを判定する。到達した場合、ステップL10で、ターミナルデバイスがサーバIPに接続されたアクセススイッチであるか否かを判定する。そうでない場合、経路発見の完了成功を示した後にプロセスは終端し、経路完了を戻す。ターミナルデバイスがサーバIPに接続されたアクセススイッチである場合、アクセスポート接続及びサーバIPを経路に追加し、プロセスは、次に進んで経路発見成功で完了し、経路完了を戻した後に停止ステップで終了する。

0115

ステップL09で予想されたターミナルデバイスに到達していないと判定した場合、ステップL14においてNHL3がサーバIPであるか否かを質問する。そうでない場合、経路発見の完了が不成功であったと判定し、一部の経路を戻した後に停止する。NHLがサーバIPであった場合、これは、プロセスが最終LSセグメントにあることを示すので、プロセスは、スキップセグメントカウンタインクリメントすると共にフォーカスデバイスをNHL3に設定することで、宛先へとスキップすることができる。

0116

図14は、オプションCを示す。第1のステップC1では、オプション変数のシーケンスからオプションを除去する。ステップC2では、ネットワークアドレスが宛先(サーバIP)と一致する単一のインタフェースがあるかについてチェックする。
単一のインタフェースがある場合、これは、アルゴリズムが最終スイッチネットワーク部分に到達したことを示すので、NHL3をサーバIPに設定する。
ステップC3では、フォーカスデバイスにクエリを実行してサーバIPのためのARPエントリを見つけ、その結果をNHL2に設定する。次に、プロセスは、メインループ(C4)に戻り、別のオプションによって出口インタフェースを決定することができる。フォーカスデバイス上のSNMP−ARPテーブルを用いてフォーカスデバイスへのクエリを行うか、又は見つからない場合は、ネットワーク管理システムARPキャッシュにクエリを行う。これらのクエリは、後で更に充分に説明する技法に従ったものである。

0117

ステップC2において、宛先サーバIPの単一のインタフェースのチェックが失敗した場合、単一のインタフェースは識別されない。状態変数は全く更新されない。この場合、オプション「C」を評価(及び廃棄)し、これが非生産的であることを認識するだけである。

0118

図15は、オプションSを示す。ステップS101に従って、オプションSを配列シーケンスから除去する。ステップS102では、ネットワーク管理システムにクエリを実行し、又はフォーカスデバイスへのSNMPクエリを用いて、フォーカスデバイスがNHL3をホストするか否かを見出す
NHL3がフォーカスデバイス上にある場合、プロセスは、メインループリターンポイントに戻る(S104)。ルーティングアドレスNHL3がフォーカスデバイス上にない場合、スイッチングアドレスNHL2が設定されているか否かを判定し、NHL3が与えられたNHL2についてマッピングテーブル(ARP)でフォーカスデバイスにクエリを実行する。
クエリについては後で更に充分に説明する。ステップS106では、VLANヒントが設定されているか否かを判定する。VLANヒントについては後述する。設定されていない場合、フォーカスデバイスから又はネットワーク管理システムからフォーカスデバイス上のVLANリストを求める。リストからVLANを選択し、フォーカスデバイス、NHL2、及びVLANを用いて、転送データベースエントリの検索を実行する。ステップS109に示す転送データベースエントリの検索については、図Xのフローチャートに示す。
ステップS106に戻ると、VLANヒントが設定されている場合、プロセスは直接ステップS110に進む。これは、ステップS109と同様のFDBの検索であるが、FDB内でクエリ実行したVLANとしてVLANヒントを用いる。
ステップS112(及びS111)では、転送データベース内でエントリが見つかったか否かを判定する。見つかった場合、プロセスは、図16に示すオプションSの第2の部分(エントリ矢印5)に進む。ステップS111でFDBエントリが見つからない場合、FDBエントリがあるか否か判定されるまで、又はプロセスがメインループに戻ると判定されるまで、VLANループに入る。オプションSの第2の部分に対するエントリポイントを図15の下部に矢印5で示す。
これは、図16の上部にも示されている。上述したように、転送データベースエントリが見つかった場合、これは経路の出口ポートを示している(S115)。これを用いて、ネットワークトポロジから次の接続デバイスを得ることができる。これについては、ステップS117に示し、後で更に充分に説明する。ステップS116は、図2に示し後述するVLANヒントを得るステップである。

0119

ステップS117では、接続されたポートを取得するための処理を示すフローチャートが図22a、bに示されており、それゆえ、出力ポートに基づいて、ネットワーク管理システムから後続の接続デバイスは、接続ポートが転送データベースから返される。
ステップS118で接続ポートが見つかった場合、接続ポート及び接続デバイスを識別した経路に追加し(ステップS119)、ステップS120では、フォーカスデバイスを変更して接続デバイスとする。ステップS121では、ループオプションをCSRAcrにリセットする。
次に、プロセッサは、ステップS122でメインループに戻る。ステップS118に戻ると、接続ポートが見つからない場合、プロセスは、スキップセグメントカウンタ89(図8)をインクリメントすると共にフォーカスデバイスをNHL3に変更することで、NHL3へとスキップする。スキップセグメントカウンタは、管理コンピュータにおいてハードウェア、ファームウェア、又はソフトウェアで実施され、以前のプロセスステップから次の接続デバイスが容易に確認できないことが明白である場合に経路のセグメントをスキップすることを表すことができる。
ステップS124では、フォーカスデバイスが宛先(サーバIP)でないか否かを判定する。宛先でない場合、ステップS125でループオプションをCSRAcrにリセットする。フォーカスデバイスが宛先サーバである場合、ステップS126では、宛先が既知のアクセススイッチ上にあるか否かを判定し、ある場合、NHL3をサーバアクセススイッチアドレスに設定する。
ステップS125でループオプションを設定した後、ステップS128では、フォーカスデバイスのARPテーブル又はNMSにクエリを行うことで、ステップS127で設定したNHL3アドレスを用いてNHL2についてフォーカスデバイスにクエリを実行する。

0120

オプションSは、ステップS101で利用可能オプションからこのオプションを除去すること、更に処理ステップの結果に基づいてステップS121及びステップS125で利用可能オプションにこのオプションをリセットすることを含むことに留意すべきである。

0121

これより図17を参照してオプションR及びオプションrについて説明する。これらのオプションの各々は、ステップR1、r1において配列したオプション変数のシーケンスからそのオプションを除去することで開始する。
ステップR2、r2では、プロセスに、図に示す繰り返しルート探索プロセスを用いて宛先IP(サーバIP)へのルートを探させる。オプションRでは、プロセスは、デフォルトのルートが許可されていない場合に動作する(デフォルトルート許可は偽に等しい)。オプションrでは、プロセスはデフォルトのルートを許可する(デフォルトルート許可は真に等しい)。ルートが見つからない場合、ステップR3においてプロセッサはメインループに戻る。ルートが見つかった場合、ルートが見つかったルーティングテーブルから求めた候補NHL3を用いて、フォーカスデバイスにクエリをディスパッチする。このクエリは、候補NHL3に対応した候補NHL2を求めるためにデバイスのARPテーブルに対して行われる。
候補NHL2が見つからない場合、プロセスは、オプションR/rの第2の部分のエントリポイント6に移る。ARPクエリから候補NHL2が見つかった場合、ステップR8において、候補NHL2が、プロセスR/rへのエントリ状態で状態変数として記録されているNHL2と同じであるか否かを判定するためにチェックを行う。それらが同じである場合、プロセスは、エントリポイント6に進む。
それらが同じでない場合、ステップR8の後、候補NHL2がエントリ状態NHL2と同じでない場合、NHL3を候補ルートのネクストホップIPに設定し、NHL2を候補NHL2に設定する。ステップR10では、R2及びr2におけるルーティングテーブルのクエリによって出口ポートが与えられたか否かを判定する。与えられた場合、プロセスはエントリポイント6に進む。与えられなかった場合、ステップR11でオプションをCSRAcrにリセットする。
図18では、図の上部にエントリポイント6を示す。次のステップR12では、ルーティングテーブルにより出口ポートが与えられるか否かを判定する。与えられない場合、プロセスはメインループに戻る。ステップR13では、図21に従って、かつ後述するように、VLANヒント取得プロセスを行う。

0122

次に、図22a、bに示すように接続ポート取得プロセスを行う。ステップR15では、接続ポートが見つかったか否かを判定する。見つかった場合、出口ポート、接続ポート、及び接続デバイスを経路に追加する。フォーカスデバイスを接続デバイスに変更し、ループオプションをCSRAcrにリセットする。接続ポートが見つからない場合、この段階では何も行わない。プロセスはステップS20に進み、NHL3が更新されているか否かを判定する。更新されていない場合、プロセスはメインループに戻る。更新されている場合、ルーティングテーブルからの候補NHL3があるとして、候補NHL2について古いフォーカスデバイスにクエリを実行する。そのステップの後、NHL2を決定した場合、プロセスはメインループに戻る。そうでない場合は、候補NHL3があるとして、候補NHL2について新しいフォーカスデバイスにクエリを実行する。

0123

次に図19を参照してオプションcについて説明する。第1のステップc1では、状態変数のオプションから「c」を除去する。ステップc2では、ネットワークアドレスがNHL3ネットワークアドレスと一致する単一のインタフェースについてチェックを行う。一意のインタフェースが見つからない場合、プロセスはメインループに戻る。一意のインタフェースが見つかり、出口インタフェース名がある場合、図21を参照して記載するVLANヒントプロセスを実行する。ステップC4の後、図22a、bに示す接続ポート取得プロセスを用いて接続ポートを得る。

0124

ステップc7では、ピアポート(peered port)が見つかったか否かを判定する。見つかった場合、出口ポート、ピアポート、及びピアデバイスを経路に追加し、フォーカスデバイスをピアデバイスに設定する。c8において、利用可能オプションをCSRAcrにリセットする。ステップc7でピアポートが見つからない場合、プロセスはメインループに戻る。

0125

次に、図20を参照してオプションAについて説明する。ステップA1では、状態変数のオプションシーケンスからオプションAを除去する。ステップA2では、NHL3からNHL2へのマッピングのためのSNMPARPエントリを見つける。マッピングが見つからない場合、プロセスはメインループに戻る。

0126

マッピングが見つかった場合、プロセスはSNMPを用いて、関係が学習されたインタフェースのifIndexを見つける。ステップA5では、一意のインタフェースが見つかったか否かを判定する。見つからなかった場合、プロセスはメインループに戻る。見つかった場合、プロセスはステップA6に進んで、利用可能な出口インタフェース名が存在するか否かを判定する。存在する場合、図21を参照して説明するようにVLANヒントプロセスを実行させる。次に、A8において、図22a、bに示すように接続ポート取得プロセスを実行させる。

0127

接続ポート取得プロセスの結果としてピアポートが見つかった場合、出口ポートを経路に追加し、ピアポート及びピアデバイスを経路に追加し、フォーカスデバイスをピアデバイスに設定する。更に、利用可能オプションをCSRAcrにリセットする。ピアポートが見つからない場合、プロセスはメインループに戻る。

0128

次に、図21を参照してVLANヒントプロセスについて説明する。このプロセスは、オプションAのステップA7、オプションcのステップc5、オプションR/rのステップR13、及びオプションSのステップS116で用いられた。更に、これは、まだ検討していないプライミングプロセスの1つにおいても用いられる。プロセスは、ステップVL1でアクセスポート名から開始する。ステップVL2では、名前が「VL+数字」の形態であるか否かを判定し、そうである場合、ステップVL3でこの数字を抽出してVLANヒントとして記憶する。

0129

そうでない場合、ネットワーク管理システムでは、インタフェース上の全てのVLANのリストが要求される。ステップVL5は、競合するVLANが存在するかについてチェックする。存在しない場合、ステップVL6で一意のVLANをVLANヒントとして記憶する。競合するVLANが存在する場合、既に記憶されているVLANヒントを変更せずに残す。

0130

VLANヒントは、ネットワークのスイッチ部分(レイヤ2)で論理ループを防止する(トラフィックが無限にループするのを回避する)ために用いられるスパニングツリープロトコル(STP)と呼ばれるスイッチング技法を用いたネットワークで生じ得る問題に対処する。このプロトコルは、スイッチングデバイスが所定のパケットをどこに転送するべきかを決定するために用いられる。

0131

すなわち、デバイスがスイッチングしている場合、スイッチはレイヤ2(MAC/イーサネット登録商標))ヘッダを調べると共に宛先レイヤ2アドレス(NHL2)を調べてから、内部データベース(FDBすなわち転送データベース)に照会して、どのポートからパケットを送信するかを確認する。多くの企業は、PVSTP(VLANごとのスパニングツリープロトコル)と呼ばれるSTPの拡張版を使用し、これによって各パケットにVLAN識別子も付ける。スイッチは別個のFDBをVLANごとに1つ維持する。

0132

これは、一部には効率のため、一部にはいっそう複雑な仮想トポロジを可能とするために実行される。したがって、同一のレイヤ2宛先を有する2つのパケットが異なるポートによって配信することは完全に可能である(と共に、珍しいことではない)。それらの宛先が同一デバイス/ポートであっても、異なるVLANにタグ付けされているからである。

0133

この結果、一致が見つかるまで、このプロセスは、VLANごとのFDBの全てを徹底的に探す(trawl)ことができない。パケットがどのVLANのメンバであるとタグ付けされているかを即座(アプリオリ)に知ることは重要である。

0134

このVLANタグ付けはネットワーク内の様々な場所で行われ得る。例えばこれは、ソースアクセスポートで、すなわちソースデバイスが物理的に接続されている箇所で、又はネットワーク内の別の場所で行われ得る。あるVLANタグが別のもので置換されることは珍しいことではない(これはVLAN間ルーティングと呼ばれる)。

0135

例えば、パケットがネットワークデバイスDに到着した場合(経路A→B→C→D)、AからのパケットがDに到達した時点で位置するVLANが既知である場合、Dには現在の出口インタフェースについてクエリを実行するだけでよい。例えば、AがVLAN100にパケットを配置し、Bが(VLAN100を用いて)これを送り、次に、Cが100を200に変更し、次に、DがVLAN200を用いてこれをスイッチングするという場合がある。

0136

このため、ソースデバイスから宛先デバイスまでネットワーク中で、追跡する仮想パケットの一部としてVLANヒントを「運ぶ」必要がある。したがって、適用可能な場合にVLANヒントの使用、取り消し、リセット、又は更新が行われる。

0137

既に述べたように、図23は、オプションR及びオプションrで用いられるfindRouteIterativeプロセスを示す。このプロセスは、ステップF1で開始してルート限度チェックF2で終端するルート探索ループを含む。次に、プロセスfindRouteIterativeは、ルートが見つかったか否かを判定し、ルートに関連した出口インデックスの位置を特定することができる。

0138

メインループを開始する前に、ループの第1の繰り返しのエントリ状態を設定するために実施する3つのプライミングプロセスがある。図24に第1のプライミングプロセスを示す。これは、(図24でクライアント側と称される)ソースデバイスについて識別されるアクセススイッチ又はネットワークデバイスを開始ポイントとして設定する。同様に、図24でサーバ側と称される宛先デバイスに基づいて、アクセススイッチ又はネットワークデバイスを停止ポイントとして記憶する。図24では、クライアントIP及びサーバIPはそれぞれソース及び宛先のアドレスである。

0139

図25は、初期エントリ状態NHL3及びNHL2アドレスをセットアップするためのプライミングプロセスである。

0140

図26は、初期エントリ状態についてフォーカスデバイスを設定する第3のプライミングプロセスを示す。

0141

図24の第1のプライミングプロセスは、図25の第2のプライミングプロセスに至り、図25の第2のプライミングプロセスは、図26の第3のプライミングプロセスに至ることに留意すべきである。第3のプライミングプロセスは、図Aに示すメインループのメインエントリポイント4に至る。

0142

[追加の技術/プロトコル]
経路発見アルゴリズムは、上述のように利用された場合、一般的に既知のネットワークプロトコルに従って動作している相互接続デバイスのネットワーク内で特定のパケット又はメッセージが取り得る特定の経路を識別する効果的な方法を提供する。何らかの理由で、経路発見アルゴリズムが特定の問題に直面する状況が生じる。これらの問題のいくつかについて以下で検討する。

0143

場合によっては、アルゴリズムにおいて実行されるユーティリティは、マルチプロトコルラベルスイッチング(MPLS:Multi−Protocol Label Switched)ネットワークセグメントを横断しなければならない。これを達成するため、(トラフィックがMPLSセグメントに入るポイントで)初期ラベル割り当てを見つけ、ラベルポッピングプッシング、及び転送のホップごとの詳細を用いたホッピングによってMPLSネットワーク中で追跡する。これを、トラフィックがその最終ラベルをポッピングしてMPLSセグメントから出るまで続ける。

0144

別の問題は、NATデバイスNATテーブルのポーリングによって達成され得るNAT境界の横断である。これは、ダイナミックNATについてリアルタイムの推論的なポーリング(speculative polling)を必要とする場合があるが、スタティックNATではバックグラウンドポーリングを用いることが可能であり得る。

0145

IPSEC/GRE/SSL等のトンネルプロトコルにおいて、ユーティリティは、トンネルの一端から他端までの直接ルートについてチェックする(典型的に、それらの間の全ノードを表す1つの未知のレイヤ3ホップによる)。ユーティリティは、更に、プロトコルに特有トポロジ情報をチェックし、ルーティングテーブル/インタフェースにおいて暗号トンネル(crypto/tunnelling)ホップが存在するかチェックする。

0146

別の問題は仮想化である。アルゴリズムが物理的な出口ポートを識別して、出口ポートに接続された物理デバイスにトポロジからアクセス可能とすることは重要である。多くのネットワークは、様々な異なる仮想化レイヤで動作する。追加のAPIを用いて仮想スイッチにクエリを実行することができる。トポロジサーバがエンドホスト位置に関するタイムリーな情報を有することを確実とするため、トポロジサーバは仮想化管理プラットフォーム一体化して仮想マシン再配置に関する更新を実行し、影響を受ける仮想スイッチ上のエンドホスト位置の事前対応型ポーリングを可能とすることが必要であり得る。

0147

ユーティリティは、特定のVRF(virtualized routing and forwarding)識別子に必要である適切なIP転送(ルーティングテーブル)にクエリを実行することで、仮想化ルーティング及び転送テーブル(VRF)をネゴシエートする。例えばSNMPにおいて、これはVRFコンテキストコミュニティストリングを用いて実行可能である。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ