JP6438375B2 - 通信システム、通信装置、制御装置、トラフィック観測方法及びプログラム - Google Patents

Description

通信ネットワークを流れるトラフィックの観測技術に関する。

従来の観測技術は、送信元と受信先のペア（以下、フローと呼ぶ。）ごとにトラフィックを分類し、評価している（例えば、非特許文献１参照。）。ここでは簡単のために、フローが送受信「装置」のペアである場合について説明する。実際のフローは、５−ｔｕｐｌｅなどのように、アドレスとポート番号の組によって決められる「論理的な接続終端点のペア」をもって定義されることが多い。各ネットワーク機器は通過するトラフィックを送受信ペアごとに分類し、パケット数やバイト数をカウントする。本発明は特定種のネットワーク機器に限定されないが、簡単のために、本明細書においては、ネットワーク機器をスイッチと呼ぶ。

図１の例を説明する。端末Ａ〜ＦがスイッチＳＷ_Ｒ〜ＳＷ_Ｔによって接続されている。各スイッチは、フローごとにパケット数をカウントしている。ここで、端末Ａから端末ＣへのパケットがスイッチＳＷ_ＲとＳＷ_Ｓを通過すると、スイッチＳＷ_Ｒ及びＳＷ_Ｓは、フローＡ→Ｃのカウンタを１６から１７へと増加させる。このカウンタ値は、通信ネットワークの障害解析などに利用される。たとえば、スイッチＳＷ_ＲとスイッチＳＷ_Ｔのカウンタを比較すると、フローＣ→Ｆのパケット数が大きく異なり、両者の間に障害の原因があると推測できる。

近年の端末増に伴ってフロー数は膨大になっており、すべてを観測するのは難しくなっている。たとえば、各フローの計測に必要なメモリを１００バイトとし、フロー数が１０００万に達すると、すべてのフローを管理するには１ＧＢが必要になる。一方、ＣＰＵキャッシュに使われるような高速メモリは数十ＭＢであり、大幅に足りない。このため、パケットを間引いて観測する「サンプリング」を行うが、これには重要な障害を見逃すリスクがある。

次に、複数フローをまとめてカウンタ表の行数を削減する可能性を考える。図１の通信ネットワーク８１の内には、端末数に関わらず６通りの経路しか存在しない。具体的には、ＳＷ_Ｒ→ＳＷ_Ｓ、ＳＷ_Ｓ→ＳＷ_Ｒ、ＳＷ_Ｒ→ＳＷ_Ｔ、ＳＷ_Ｔ→ＳＷ_Ｒ、ＳＷ_Ｓ→ＳＷ_Ｒ→ＳＷ_Ｔ、ＳＷ_Ｔ→ＳＷ_Ｒ→ＳＷ_Ｓである。同じ経路を通過するトラフィックは各スイッチで同様に処理されるため、障害の原因分析などでは区別する必要がない。ＱｏＳなどにより同じ物理経路を通過するフローでも異なる処理が行われる場合、それぞれを別の論理経路として考えればよい。経路数がフロー数よりも少なければ、経路ごとにパケット数をカウントすることで、カウンタ表の行数を大幅に削減できる。

たとえば、図１の全端末ペアで通信が行われるとすると、ＳＷ_Ｒを通過するフローは２４本（Ａ→Ｃ、Ａ→Ｄ、Ａ→Ｅ、Ａ→Ｆ、Ｂ→Ｃ、Ｂ→Ｄ、…、Ｆ→Ｃ、Ｆ→Ｄ）であり、スイッチＳＷ_Ｒのカウンタ表は２４行になる。しかし、スイッチＳＷ_Ｒを通過する経路は６本しかない。そこで、図２のように、送信元と受信先のペアで定められるフローを通信ネットワーク８１内の経路としてまとめてカウントする。たとえば、図１では別フローとしてカウントされていたＣ→ＥとＣ→Ｆを、図２では通信ネットワーク８１内の同じ経路ＳＷ_Ｓ→ＳＷ_Ｒ→ＳＷ_Ｔとしてまとめてカウントする。すると、スイッチＳＷ_Ｒにおけるカウンタ表の行数は６に抑えられる。

特願２０１４−１３２６０３

Ｙ． Ｇｕ， Ｌ． Ｂｒｅｓｌａｕ， Ｎ． Ｄｕｆｆｉｅｌｄ， ａｎｄ Ｓ． Ｓｅｎ， "Ｏｎ ｐａｓｓｉｖｅ ｏｎｅ−ｗａｙ ｌｏｓｓ ｍｅａｓｕｒｅｍｅｎｔｓ ｕｓｉｎｇ ｓａｍｐｌｅｄ ｆｌｏｗ ｓｔａｔｉｓｔｉｃｓ"， Ｉｎ ＩＥＥＥ ＩＮＦＯＣＯＭ， ｐｐ． ２９４６−２９５０， Ａｐｒｉｌ ２００９． Ｔ． Ｉｎｏｕｅ， Ｔ． Ｍａｎｏ， Ｋ． Ｍｉｚｕｔａｎｉ， Ｓ． Ｍｉｎａｔｏ， ａｎｄ Ｏ． Ａｋａｓｈｉ， "Ｒｅｔｈｉｎｋｉｎｇ ｐａｃｋｅｔ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｆｏｒ ｇｌｏｂａｌ ｎｅｔｗｏｒｋ ｖｉｅｗ ｏｆ ｓｏｆｔｗａｒｅ−ｄｅｆｉｎｅｄ ｎｅｔｗｏｒｋｉｎｇ"， Ｉｎ ＩＥＥＥ ＩＣＮＰ， ｐｐ． ２９６−３０７， ２０１４． Ｈ． Ｙａｎｇ ａｎｄ Ｓ． Ｌａｍ， "Ｒｅａｌ−ｔｉｍｅ ｖｅｒｉｆｉｃａｔｉｏｎ ｏｆ ｎｅｔｗｏｒｋ ｐｒｏｐｅｒｔｉｅｓ ｕｓｉｎｇ ａｔｏｍｉｃ ｐｒｅｄｉｃａｔｅｓ"， ｉｎ ＩＥＥＥ ＩＣＮＰ， ｐｐ． １−１１， ２０１３． Ａ． Ｓｒｉｎｉｖａｓａｎ， Ｔ． Ｋａｍ， Ｓ． Ｍａｌｉｋ， ａｎｄ Ｒ． Ｂｒａｙｔｏｎ， "Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｄｉｓｃｒｅｔｅ ｆｕｎｃｔｉｏｎ ｍａｎｉｐｕｌａｔｉｏｎ"， ｉｎ ＩＥＥＥ ＩＣＣＡＤ， ｐｐ． ９２−９５， １９９０．

カウンタ表の行数を削減するこのアイデアは一見有望そうである。しかし、パケットを通信ネットワーク内の経路ごとに分類することは現実には非常に難しい問題であるため、現在の高速通信ネットワークに適用できる高速な分類技術は存在しない（例えば、非特許文献２参照。）。このため、通信ネットワーク内の経路ごとにカウンタを管理できておらず、非特許文献１のようにフローごとに管理している。

本発明は、フロー数が膨大であっても、間引くことなくトラフィックをカウントすることを可能にすることを目的とする。

発明者らは、ＭＤＤ（Ｍｕｌｔｉ−ｖａｌｕｅｄ Ｄｅｃｉｓｉｏｎ Ｄｉａｇｒａｍ）というデータ構造を用いれば、毎秒１０００万パケットを通信ネットワーク内の経路ごとに分類できることを発見した（例えば、特許文献１参照。）。本願発明は、パケットを通信ネットワーク内の経路ごとに分類可能なＭＤＤ（Ｍｕｌｔｉ−ｖａｌｕｅｄ Ｄｅｃｉｓｉｏｎ Ｄｉａｇｒａｍ）というデータ構造を利用し、通信ネットワーク内の経路ごとのカウンタ値をスイッチ間で比較して、矛盾を検出する。

本発明に係る通信システムは、
複数のスイッチが接続されている通信ネットワークに備わる前記スイッチ及び前記スイッチに接続されている制御装置を備える通信システムであって、
前記複数のスイッチが、
パケットのヘッダ空間における領域ごとに出力方路を定めた動作設定表を前記制御装置に送信する送信部と、
パケットのヘッダ空間における領域で定められる前記通信ネットワーク内の経路を、前記制御装置の生成した多分決定木を用いて特定する経路特定部と、
前記経路特定部の特定した経路のカウンタ値を増加させるカウンタ表と、を備え、
前記制御装置が、
前記動作設定表を前記複数のスイッチから取得し、前記複数のスイッチの前記動作設定表を用いて、パケットのヘッダ空間における領域を定めるビット列を非終端ノードとしかつ前記通信ネットワーク内の経路を終端ノードとする多分決定木を生成する経路導出部と、
前記複数のスイッチから前記カウンタ表を取得してカウンタ集計表を作成し、前記通信ネットワーク内の経路ごとのカウンタ値がスイッチ間で一致するか否かを判定するカウンタ評価部と、を備える。

本発明に係る通信システムでは、
前記経路導出部は、
前記ヘッダ空間における領域を定めるビット列を二分決定木に変換し、前記二分決定木の各終端ノードに割り当てられている前記通信ネットワーク内の経路毎に、根ノードから各終端ノードへのパスが共通する二分決定木の終端ノードに到達しうる二分決定木を生成する二分決定木生成部と、
前記パスの異なる各二分決定木のうちのビット列の共通する非終端ノードを共有させ、根ノードから各終端ノードへの多分決定木を構築する多分決定木構築部と、
前記多分決定木構築部で構築した前記多分決定木の根ノードから終端ノードのパス方向に隣接する複数の非終端ノードを１つの非終端ノードに集約するビット集約部と、
を備えていてもよい。

本発明に係る通信装置は、
複数のスイッチが接続されている通信ネットワークに備わる前記スイッチとして機能する通信装置であって、
パケットのヘッダ空間における領域ごとに出力方路を定めた動作設定表と、
パケットのヘッダ空間における領域で定められる前記通信ネットワーク内の経路を、前記複数のスイッチに接続されている制御装置の生成した多分決定木を用いて特定する経路特定部と、
前記経路特定部の特定した経路のカウンタ値を増加させるカウンタ表と、
を備え、
前記多分決定木は、前記複数のスイッチに備わる動作設定表を用いて構成される、パケットのヘッダ空間における領域を定めるビット列を非終端ノードとしかつ前記通信ネットワーク内の経路を終端ノードとする多分決定木である。

本発明に係る制御装置は、
複数のスイッチが接続されている通信ネットワークに備わる前記スイッチに接続されている制御装置であって、
パケットのヘッダ空間における領域ごとに出力方路を定めた動作設定表を前記複数のスイッチから取得する受信部と、
前記複数のスイッチの前記動作設定表を用いて、パケットのヘッダ空間における領域を定めるビット列を非終端ノードとしかつ前記通信ネットワーク内の経路を終端ノードとする多分決定木を生成する経路導出部と、
前記多分決定木を前記複数のスイッチに送信する送信部と、
前記通信ネットワーク内の経路ごとにカウンタ値が記載されたカウンタ表を前記複数のスイッチから取得してカウンタ集計表を作成し、前記通信ネットワーク内の経路ごとのカウンタ値がスイッチ間で一致するか否かを判定するカウンタ評価部と、
を備える。

本発明に係るトラフィック観測方法は、
複数のスイッチが接続されている通信ネットワークに備わる前記スイッチが実行するトラフィック観測方法であって、
パケットのヘッダ空間における領域で定められる前記通信ネットワーク内の経路を、前記複数のスイッチに接続されている制御装置の生成した多分決定木を用いて特定し、特定した経路のカウンタ値をカウンタ表において増加させるカウント手順と、
前記カウンタ表を前記制御装置に送信する送信手順と、
を順に有し、
前記多分決定木は、前記複数のスイッチに備わる動作設定表を用いて構成される、パケットのヘッダ空間における領域を定めるビット列を非終端ノードとしかつ前記通信ネットワーク内の経路を終端ノードとする多分決定木である。

本発明に係るトラフィック観測方法は、
複数のスイッチが接続されている通信ネットワークに備わる前記スイッチと接続されている制御装置が実行するトラフィック観測方法であって、
パケットのヘッダ空間における領域ごとに出力方路を定めた動作設定表を前記複数のスイッチから取得し、前記複数のスイッチの前記動作設定表を用いて、パケットのヘッダ空間における領域を定めるビット列を非終端ノードとしかつ前記通信ネットワーク内の経路を終端ノードとする多分決定木を生成し、前記複数のスイッチに送信する経路導出手順と、
前記多分決定木を用いて特定された経路のカウンタ値を含むカウンタ表を前記複数のスイッチから取得してカウンタ集計表を作成し、前記通信ネットワーク内の経路ごとのカウンタ値がスイッチ間で一致するか否かを判定する判定手順と、
を順に有する。

本発明に係るプログラムは、コンピュータを、本発明に係る通信装置に備わる各機能部として機能させるためのプログラムである。

本発明に係るプログラムは、コンピュータを、本発明に係る制御装置に備わる各機能部として機能させるためのプログラムである。

本発明によれば、フロー数が膨大になっても、間引くことなくトラフィックをカウントでき、障害などの原因箇所を推定できる。特に、各スイッチが管理するカウンタ表の行数が、フロー数に依存しなくなる。

フローごとにカウンタを管理するシステム構成の一例を示す。 経路ごとのカウンタを管理するシステム構成の一例を示す。 コントローラに備わるカウンタ集計表の一例を示す。 実施形態１に係るトラフィック監視シーケンスの一例を示す。 実施形態に係る通信ネットワークの構成の一例を示す。 スイッチＳＷ_Ａに備わる動作設定表の一例を示す。 パケットのヘッダ空間を２次元座標で表現した場合のスイッチＳＷ_Ａの動作の一例を示す。 スイッチＳＷ_Ｂに備わる動作設定表の一例を示す。 パケットのヘッダ空間を２次元座標で表現した場合のスイッチＳＷ_Ｂの動作の一例を示す。 スイッチＳＷ_Ｃに備わる動作設定表の一例を示す。 パケットのヘッダ空間を２次元座標で表現した場合のスイッチＳＷ_Ｃの動作の一例を示す。 通信ネットワーク８３中の経路の組み合わせの一例を示す。 図１２に示す各経路の説明図である。 スイッチの一例を示す構成図である。 スイッチの動作の一例を示すフローチャートである。 コントローラの一例を示す構成図である。 コントローラの動作の一例を示すフローチャートである。 経路導出部の一例を示す。 ＢＤＤ集合をひとつのＭＤＤに変換するフローチャートの一例を示す。 実施形態に係るＢＤＤ構造の一例を示す。 実施形態に係るＭＤＤ構造の一例を示す。 実施形態に係るＢＤＤをＭＤＤに置換した場合の一例を示す。 実施形態に係る各経路を示すＭＤＤを１つのＭＤＤに纏めた場合の一例を示す。 本発明の実施形態に係る各経路を示すＭＤＤを１つのＭＤＤにまとめる場合のアルゴリズムの一例を示す。 本発明の実施形態に係る各経路を示すＭＤＤを１つのＭＤＤにまとめる場合のアルゴリズムの他の例を示す。 本発明の実施形態に係るＭＤＤにおいてビット集約を行う場合のアルゴリズムの一例を示す。 本発明の実施形態に係るＭＤＤにおいてＭＤＤ更新を行う場合のアルゴリズムの一例を示す。 本発明の実施形態に係るＭＤＤにおいてＭＤＤを辿り、与えられたパケットヘッダに対応する経路を検索する場合のアルゴリズムの一例を示す。 本発明の実施形態に係るＭＤＤにおいて、６ビットのパケットヘッダを２ビットごとの配列で扱う場合の一例を示す。

以下、本発明の実施形態について、図面を参照しながら詳細に説明する。なお、本発明は、以下に示す実施形態に限定されるものではない。これらの実施の例は例示に過ぎず、本発明は当業者の知識に基づいて種々の変更、改良を施した形態で実施することができる。なお、本明細書及び図面において符号が同じ構成要素は、相互に同一のものを示すものとする。

（実施形態１）
本実施形態に係る通信システムは、図２に示すように、通信ネットワーク８１を構成するスイッチと、各スイッチを管理するコントローラ８２と、を備える。スイッチは通信装置として機能し、コントローラ８２は制御装置として機能する。コントローラ８２は、図３に示すようなカウンタ集計表を備える。本実施形態の装置はコンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、通信ネットワークを通して提供することも可能である。

図４に、本実施形態に係るトラフィック監視シーケンスの一例を示す。本実施形態に係るトラフィック監視シーケンスは、経路導出手順（Ｓ３０１〜Ｓ３０３）、カウント手順（Ｓ３０４）、及び、判定手順（Ｓ３０５〜Ｓ３０６）を順に有する。

経路導出手順では、コントローラ８２が、各スイッチから動作設定表を取得し（Ｓ３０１）、動作設定表を用いてＭＤＤ及び経路一覧を生成する（Ｓ３０２）。ここでのＭＤＤは、パケットのヘッダ空間における領域を定めるビット列を非終端ノードとしかつ通信ネットワーク８１内の経路を終端ノードとする多分決定木である。これにより、各スイッチが、コントローラ８２からＭＤＤ及び経路一覧を取得する（Ｓ３０３）。
カウント手順では、各スイッチが、ＭＤＤを用いてパケットの経路を特定し、特定した経路ごとにパケットをカウントする（Ｓ３０４）。
判定手順では、コントローラ８２が、各スイッチからカウンタ表を取得して図３に示すようなカウンタ集計表を作成し（Ｓ３０５）、経路ごとのカウンタ値をスイッチ間で比較して、通信ネットワーク内の経路ごとのカウンタ値がスイッチ間で一致するか否かを判定する（Ｓ３０６）。

実施形態に係る通信システムは、各スイッチがＭＤＤを用いて通信ネットワーク８１内の経路を特定する。ＭＤＤというデータ構造を用いれば、毎秒１０００万パケットを通信ネットワーク内の経路ごとに分類することができる（例えば、特許文献１参照。）。このため、実施形態に係る通信システムは、フロー数が膨大であっても、間引くことなくトラフィックをカウントすることができる。

まず、ＭＤＤについて簡単に説明する。図５に示す通信ネットワーク８３の例を用いて説明する。本実施形態では、特許文献１に記載の「パケットの振る舞い（ｂｅｈａｖｉｏｒ）」を、直観的に理解しやすいように「経路」と表記する。「振る舞い」は、異なるスイッチから送られたパケットの経路が途中で合流したり、パケットが廃棄される状況も包含する概念である。本実施形態では、トラフィックの観測という目的に合わせて、「振る舞い」を「経路」という。

本実施形態に係る通信ネットワーク８３は、スイッチＳＷ_Ａ、ＳＷ_Ｂ及びＳＷ_Ｃによって構成されている。それぞれ３つのインタフェース（Ｐ_Ａ１など）を備えた３台のスイッチＡ〜Ｃからなる通信ネットワークを考える。図５では、端末は省略されている。簡単のため、２個の３−ｂｉｔ領域によってパケットのフローを識別できるとする。すなわち、３−ｂｉｔの送信アドレス及び受信アドレスで区別すると考えてよい。

図６〜図１１に、各スイッチにおける動作設定の一例を示す。各スイッチは、パケットを受信すると、２個の３−ｂｉｔ領域によってパケットを識別し、図６、図８及び図１０に示す動作設定表に基づいてパケットに対応する動作を決定し、実行する。図７、図９及び図１１は、２個の３−ｂｉｔ領域によって定められるヘッダ空間を２次元座標で表現した場合の各スイッチの動作を示す。図６〜図１１において、Ｐ_Ａ１などは出力方路を示す。

各スイッチは、パケットのヘッダ空間における領域ごとに動作を決定する。これにより、各スイッチにおける動作設定表が作成される。通信ネットワーク８３全体を通過する経路を決定するのと異なり、各スイッチでの動作を決定するのは容易である。通信ネットワーク８３内の経路は、すべてのスイッチで行われる動作の組合せとなるため、個別の動作よりも複雑になる。図６〜図１１の例では、図１２及び図１３に示すように、通信ネットワーク８３内のパケットはＩからＸＩＩまで１２種類の経路のいずれかに分類される。各スイッチの動作を組み合わせると、この通信ネットワーク８３にはＩからＸＩＩまで１２種類の経路が存在するとわかる。細かいことをいうと、グラフとしては１２より多くの経路が存在しうるが、各スイッチの設定からパケットが流れ得ない経路は無視した。

ＭＤＤの役割は、パケットを与えられると、パケットのフローに対応する通信ネットワーク内の経路を返すことである。これにより、各スイッチは受信したパケットの経路を高速で分類でき、図３のような経路に基づくカウンタ表を実現できるようになる。ＭＤＤを構築するための入力は、図６、図８及び図１０に示す全スイッチの動作設定表である。出力として、後述する図２３に示すようなＭＤＤと経路一覧が得られる。

続いて、ＭＤＤを用いたトラフィック観測技術を説明する。図２に示すネットワーク８１の全体を管理する装置をコントローラ８２と呼ぶことにする。コントローラ８２は、すべてのスイッチと通信可能であるとする。

図１４はスイッチの構成図である（動作設定表は省略する）。本実施形態に係るスイッチは、パケット送受信部２１、経路特定部２２及びカウンタ表２３を備える。

パケット送受信部２１が、ＭＤＤ及び経路一覧をコントローラ８２から受信する。経路特定部２２は、ＭＤＤ及び経路一覧を保持する。

カウント手順における各スイッチの動作を、図１５のフローチャートに示す。パケット送受信部２１がパケットを受信すると（Ｓ２０１）、経路特定部２２がパケットに対応する経路に分類し（Ｓ２０２）、カウンタ表２３が対応する経路のカウンタの値を増加させる（Ｓ２０３）。なお、カウンタ表２３は、パケット数をカウントしてもよいが、バイト数をカウントしてもよい。カウンタ表２３は、更新後のカウンタ表を、パケット送受信部２１を介してコントローラ８２に送信する。

図１６は、コントローラ８２の構成図である。コントローラ８２は、パケット送受信部１１、経路導出部１２、カウンタ集計表１４、カウンタ評価部１５及び警報発生部１６を備える。

経路導出部１２は、パケット送受信部１１から各スイッチの動作設定表の情報を収集する。経路導出部１２は、各スイッチの動作設定表に含まれるフローを用いて通信ネットワーク８１のＭＤＤを構築し、パケット送受信部１１を介して各スイッチに設定する。これにより、各スイッチは、カウント手順においてパケットのヘッダ空間から経路を特定することが可能になる。

また、コントローラ８２は、各スイッチのカウンタ表を集計してカウンタ集計表１４を作成し、これを用いて監視を行う。判定手順におけるコントローラ８２の動作を、図１７のフローチャートに示す。カウンタ集計表１４は、図３の表のように、定期的に全スイッチのカウンタ表を集計する。そしてカウンタ評価部１５が、通信ネットワーク内の経路ごとにカウンタ値の妥当性を評価する（Ｓ１０２）。たとえば、以下のようにカウンタ値の矛盾に基づく評価方法が考えられる。矛盾が見つかった場合には、警報発生部１６は、警報を出し（Ｓ１０３）、必要に応じてより詳細な分析を行う。

カウンタ評価部１５は、経路に含まれないスイッチのカウンタがゼロであることを確認する。例えば、図３の経路Ｒ→Ｓをみると、パケットが通過するはずのないスイッチＳＷ_Ｔのカウンタが「３」となっており、ゼロではない。これは、パケットが間違った経路を通っていることを示しており、スイッチＳＷ_Ｔ周辺でなんらかの障害が発生していると考えられる。

カウンタ評価部１５は、経路上にある全スイッチのカウンタが（ほぼ）一致していることを確認する。図３の経路Ｓ→Ｒ→Ｔをみると、スイッチＳＷ_Ｒ及びＳＷ_Ｓのカウンタ値は「４９８２３」であるが、スイッチＳＷ_Ｔのカウンタ値は「３８２９４」であり、スイッチＳＷ_ＴはスイッチＳＷ_Ｒ及びＳＷ_Ｓよりもかなり小さくなっている。これは、経路Ｒ→Ｔ間で多くのパケットが廃棄されていることを示している。

カウンタ評価部１５は、経路の下流のカウンタ値が上流を超えていないことを確認する。図３の経路Ｔ→Ｒをみると、上流のスイッチＳＷ_Ｔのカウンタ値より下流のスイッチＳＷ_Ｒのカウンタ値のほうが大きい。これは、通信ネットワーク８１中でパケットが不正に生成されていることを示している。

なお、伝送遅延やｑｕｅｕｅｉｎｇ遅延があるため、スイッチ間でカウンタ値が完全に一致するとは限らない。実際には、これらの遅延を考慮して評価を行う。

以上説明したように、本実施形態によれば、コントローラ８２を操作するネットワークオペレータは、カウンタ集計表１４を用いて、継続的にトラフィックを観測し、妥当性を評価することができる。特に、トラフィック観測により障害などの原因箇所を推定することができる。これにより、ネットワークオペレータは、通信ネットワークが正しく機能していることを確認することができる。

（実施形態２）
本実施形態では、経路導出部１２の詳細について説明する。図１８に本実施形態に係る経路導出部１２の一例を示す。本実施形態に係る経路導出部１２は、二分決定木生成部１２１と、多分決定木構築部１２２と、ビット集約部１２３とを備える。二分決定木生成部１２１と、多分決定木構築部１２２と、ビット集約部１２３が、多分決定木構築手順を実行する。

経路導出部１２は、コンピュータを、二分決定木生成部１２１、多分決定木構築部１２２、ビット集約部１２３として機能させることで実現してもよい。この場合、コントローラ８２のＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）が記憶部（不図示）に記憶されたコンピュータプログラムを実行することで、各構成を実現する。

二分決定木生成部１２１は、パケットの経路を特定するためのヘッダ空間に記載されたビット列を二分決定木に変換し、二分決定木の各終端ノードに割り当てられている通信ネットワーク内のパケットの経路毎に、経路が共通する二分決定木の終端ノードに到達しうる二分決定木を生成する。ビット列から二分決定木への変換は、例えば、非特許文献３のアルゴリズム３などによって、パケット受信部１１が受信するパケットの各経路に対応するＢＤＤを構築することで行う。具体的には、本実施形態に係る二分決定木生成部１２１は、パケットの経路を特定するためのヘッダ空間に記載されたビット列をＢＤＤに変換し、ＢＤＤの各終端ノードに割り当てられているパケットの経路毎に、経路が共通するＢＤＤの終端ノードに到達しうるＢＤＤを生成する。

このＢＤＤ集合が本実施形態の多分決定木構築部１２２の入力になる。多分決定木構築部１２２は、ＢＤＤ集合を、ひとつのＭＤＤに変換する。以降、ＢＤＤをＭＤＤに変換する手法を述べ、最後にＭＤＤを辿るアルゴリズムを述べる。変換手法については、図１９に示すフローチャートに従って説明する。

（ＢＤＤ及びＭＤＤについて）
図２０及び図２１を用いてＢＤＤとＭＤＤ（ｍｕｌｔｉ−ｖａｌｕｅｄ ｄｅｃｉｓｉｏｎ ｄｉａｇｒａｍ）という圧縮データ構造を説明する。ここで、ＢＤＤとは二分決定木であり、ＭＤＤとは多分決定木である。二分決定木生成部１２１は、パケットヘッダのビット列から、図２０のＢＤＤを生成する。図２０は、図１２の領域Ｉを表すＢＤＤである。ＢＤＤ中の非終端ノードＮ_０〜Ｎ_８に書かれた数値は、パケットヘッダのビット番号を表す（ビット番号は０から数えることにする）。そのビットが０であれば点線を、１であれば実線を辿る。

最終的に終端ノードＮＥ_１に到達した場合、そのビットパターンが領域Ｉに合致する。一方、終端ノードＮＥ_２に到達した場合、そのビットパターンは領域Ｉに合致しない。たとえば、図２０の太線で示したパス（ｐａｔｈ）は０１０１１＊というビットパターンを表し、領域Ｉの経路に合致する。領域Ｉ内の５番目ビットの＊はワイルドカードを表す。ビットがワイルドカードである場合、そのビットの値は任意である。この場合、対応するＢＤＤノードは省略される。そのため、図２０には、終端ノードＮＥ_１に実線で繋がるＢ_５ノードは省略されている。このように上のノードから下のノードへのパスによって、ヘッダのビットパターンを表す。なお、ＢＤＤ上のパスは、ヘッダ空間における矩形に対応する。すべてのパスを辿ることで、重なりのない矩形ルールを列挙できる。

ＢＤＤは、共通する「部分パス」を共有することで、「圧縮」を行うため、二分決定木生成部１２１は、膨大な数の矩形をコンパクトに表現できる。たとえば、図２０の太線で示した０１０１１＊というパスと、０１１１１＊というパスは、０１という先頭部分と１＊という末尾部分を共有している。このＢＤＤには１４のパスがあるが、たった９つの非終端ノードＮ_０〜Ｎ_８で表現できている。

すでに述べたように、ＢＤＤは通信ネットワーク内の経路ごとに構築される。図２０にはひとつのＢＤＤしか示さないが、図１２のヘッダ空間を表すためには１２個のＢＤＤが構築されることになる。図２１は、図１２のヘッダ空間全体を表すＭＤＤである。図２１のＭＤＤは、多分決定木構築部１２２が、二分決定木生成部１２１で生成したＢＤＤから構築する。

ＭＤＤでは、ＢＤＤと異なり、終端ノードの種類は任意であり、今回は通信ネットワーク内のパケットの経路に対応づける。図１２には１２種類の経路があったので、終端ノードはＮＴ_ＩからＮＴ_ＸＩＩの１２種類である。このＭＤＤでは、Ｋ＝２個の連続するビットをひとつにまとめている。このため、各ノードには２つのビット番号が記され、２ビットで表現できる０−３の矢印が出ている。図２１の太線で示したパスは０１０１１１というビットパターンを表し、領域Ｉのパスに従い終端ノードＮＴ_Ｉに到達している。ＢＤＤと同様に、ＭＤＤも部分パスを共有して、圧縮を行う。ＢＤＤやＭＤＤの「サイズ」は、非終端ノードの数と定義する。

（ＭＤＤ初期構築（ｃｏｎｓｔｒｕｃｔｉｏｎ））
まず、ＭＤＤの初期構築（ｃｏｎｓｔｒｕｃｔｉｏｎ）を説明する。本実施形態に係る多分決定木構築部１２２は、根ノードから各終端ノードへのＭＤＤを構築する。パケットヘッダのビット数をＬとし、Ｌビットのヘッダ空間をχ＝｛０，１｝^Ｌと表す（図５〜図１１はＬ＝３＋３である）。あるヘッダを表すビットパターンをｘ∈χとする。

経路の集合をＰ＝｛Ｉ，ＩＩ，・・・｝とし、ヘッダｘが領域ｉ∈Ｐに合致するか否かを表す論理関数をｆ_ｉ（ｘ）とする。

であれば合致し、

であれば合致しない。この論理関数ｆ_ｉをＢＤＤで表す。たとえば、ヘッダｘ＝０１０１１１は図２０の太線のパスに対応し、

となることで領域Ｉに合致することを表す。

図２０のように、通信ネットワーク内のすべての経路ｆ_ｉ,∀_ｉ∈ＰがＢＤＤで表現されているとする。多分決定木構築部１２２は、このＢＤＤ ｆ_ｉを、根ノードから各終端ノードへの全てのパスで、関数としての意味を変えずにＭＤＤ Ｆ_ｉに単純変換して、根ノードから各終端ノードへのＭＤＤを構築する（図２２）。ここで、Ｆ_ｉ（ｘ）はヘッダｘを領域ｉに対応づける関数とし、Ｆ_ｉ（ｘ）＝ｉであればヘッダｘは領域ｉに合致し、Ｆ_ｉ（ｘ）＝ｎｉｌであれば合致しない（ｎｉｌは未定義の経路を表すとする）。この変換操作は、図２０のＢＤＤの終端ノード

を図２２のようにＩ、ｎｉｌに置き換えればよい。

（ＭＤＤ統合（ｕｎｉｆｉｃａｔｉｏｎ））
次に、多分決定木構築部１２２は、通信ネットワーク８３内の各経路を表すＭＤＤのうち、ビット列の共通する非終端ノードを共有させることでひとつにまとめ（ｕｎｉｆｉｃａｔｉｏｎ）、図２３のＭＤＤを得る。ふたつのＭＤＤ Ｆｉ，Ｆｊが与えられたとき、ヘッダｘの経路が、Ｆ_ｉ，Ｆ_ｊのいずれかで定義されていれば（ｎｉｌでなければ）、その経路に対応づければよい。このような

演算を統合演算と呼ぶことにし、次の式（１−１）のように定義する。

ここで、非特許文献４が提案するＣＡＳＥというアルゴリズムフレームワークを用いる。ＣＡＳＥは、ふたつのＭＤＤに対して任意の「演算」を実行し、計算結果として新たなＭＤＤを出力する。ＣＡＳＥを用いて式（１−１）を計算するアルゴリズムを、図２４のアルゴリズム１に示す。

アルゴリズム１について説明する。アルゴリズム１では、ＦｉとＦｊの両方が終端ノードの場合には、式（１−１）に従って、Ｆ_ｉ（ｘ）とＦ_ｊ（ｘ）の統合を求め、Ｆ_ｉ（ｘ）とＦ_ｊ（ｘ）の統合を出力する。ＦｉとＦｊの両方が終端ノードでない場合には、ｘ’が０から２^ｋ−１の範囲で、Ｆ_ｉの子ノードＦ_ｉ．ｃｈｉｌｄ［ｘ’］とＦ_ｊの子ノードＦ_ｊ．ｃｈｉｌｄ［ｘ’］の統合を計算してＦ．ｃｈｉｌｄ［ｘ’］とする。計算終了後、Ｆを出力する。なお、アルゴリズム１において、「／＊」及び「＊／」に挟まれた部分はコメントである。

通信ネットワーク８３内のすべての経路に対してこの統合演算を行うことで、ヘッダ空間全体χをいずれかの経路に対応づけられる。そのような関数をＦとする。関数Ｆを以下の式（１−２）のように定義する。

通信ネットワーク８３内の各経路を表すＭＤＤ Ｆ_ｉに対して繰り返し統合演算を適用していくことで、図２２のようなＭＤＤの集合を、図２３に示すひとつのＭＤＤにまとめられる。このＭＤＤは関数Ｆを表す。この演算は結合的でありかつ数学的に可換であるため、任意の順序で計算できる。たとえば、図２５に示したような順序でＭＤＤをふたつずつ選んで演算を行い、最終的にＦを表すひとつのＭＤＤを得ることもできる。なお、図２５に示した順序とは、この図をトーナメント表だと思うと、まず１回戦を行い、

次に２回戦

３回戦、と繰り返し、決勝戦を終えるとＦが決まる。ここで、ＭＤＤ Ｆのサイズを｜｜Ｆ｜｜と表記し、非終端ノード数と定義する。

図２５の下部に、各経路に対応づけられたＭＤＤ Ｆ_ｉのサイズ｜｜Ｆ｜｜を示してある。このように、小さいＭＤＤから順に演算を行うことで、全体の計算量を最少化できる（証明は非特許文献３のＴｈｅｏｒｅｍ １でなされている）。なお、ＣＡＳＥの計算量は、ＭＤＤサイズに依存するが、ＭＤＤに含まれるパス数（矩形数）には依存しない。

（ビット集約（ａｇｇｒｅｇａｔｉｏｎ））
本実施形態に係る経路導出部１２はビット集約部１２３を備えることが好ましい。ここまで、ＢＤＤやＭＤＤの各ノードは、ひとつのビットに対応づけられていた（図２２、図２３のように）。ここで、本実施形態に係るビット集約部１２３は、多分決定木構築部１２２で構築した多分決定木の根ノードから終端ノードのパス方向に隣接する複数のビットに対応づけて集約する。例えば、各終端ノードを複数のビットに対応付けて集約し、図２３のＭＤＤを図２１のＭＤＤに変換する。このことにより、根ノードから終端ノードのパスを短くし、パケットヘッダに対応する通信ネットワーク８３内の経路を短時間で突き止められるようになる。

このビット集約操作を、図２６のアルゴリズム２によって行う。このアルゴリズムは、ＭＤＤのｒｏｏｔ ｎｏｄｅ Ｆが与えられると（ここではＦは関数ではなく、ＭＤＤのｒｏｏｔ ｎｏｄｅとする）、Ｋビット分だけ先にある２^Ｋ個の子ノードを見つけ、それらを新たな子ノードとして設定する。

この計算を再帰的に行い、ＭＤＤ全体を再構築する。このアルゴリズムを同じノードに対して繰り返し行わないように、計算済みノードはキャッシュしておく。たとえば、図２３のｒｏｏｔ ｎｏｄｅについて説明する。Ｋ＝２ビット先の子ノードとは、太線の丸で示したノードである（ビット番号２のノードが省略されているときは、その次のノードとする）。これらを新たな子ノードとして設定する（図２３の太線の丸で示した４つのノードである）。さらにそれぞれの子ノードについてアルゴリズム２を再帰的に適用する。

アルゴリズム２について説明する。アルゴリズム２では、Ｆが終端ノードでない場合又はＦがキャッシュ内にない場合には、ｘ’が０から２^ｋ−１の範囲で、再帰的にビット集約を行い、その結果をキャッシュにＦ^（Ｋ）を出力する。

このようにして再構築したＭＤＤをＦ^（Ｋ）と表すことにする。アルゴリズム２の計算量は、ＭＤＤサイズに依存するが、ＭＤＤに含まれるパス数（矩形数）には依存しない。なお、本実施形態では、ビット集約を行うか否かは任意であり、例えば、ＭＤＤの規模が小さな場合にはビット集約を行わなくてもよい。

（ＭＤＤ更新（ｕｐｄａｔｅ））
上記のようにして構築した図２３のようなＭＤＤ ＦあるいはＦ^（Ｋ）を、新たな通信ネットワーク８３内の経路を表すＭＤＤ Ｆ′で更新する。新たな通信ネットワーク８３内の経路が定義されたヘッダ空間、Ｘ′＝｛ｘ∈χ：Ｆ′（ｘ）≠ｎｉｌ｝、では、新たな通信ネットワーク８３内の経路を適用し、それ以外は元のままとする。このとき、ＣＡＳＥを用いて下記の演算を適用すればよい。

ＣＡＳＥを用いて式（２）を計算するアルゴリズムを、図２７のアルゴリズム３に示す。Ｆ′の取得方法を説明する。まず、ｆ_ｉからＦ_ｉを得た方法と同じように、ｆ′から変換してＦ′を得る。Ｆ^（Ｋ）がＫ＞１であれば、図２６のアルゴリズム２を適用して、Ｆ′のＫをＦ^（Ｋ）に揃える。

アルゴリズム３について説明する。アルゴリズム３では、Ｆ’とＦの両方が終端ノードの場合には、式（１−１）に従って、

を求めて出力する。Ｆ’とＦの両方が終端ノードでない場合には、ｘ’が０から２^ｋ−１の範囲で、

を計算し、計算後のＦ’’を出力する。

（実施形態３）
本実施形態では、経路特定部２２におけるＭＤＤ検索の詳細について説明する。
経路特定部２２は、パケット受信部２１の受信したパケットの通信ネットワーク内の経路を、当該パケットのヘッダ空間に記載されたビット列に従って、ＭＤＤを検索して辿りついた終端ノードに割当てられている経路に設定する。例えば、ＭＤＤ Ｆ^（Ｋ）を辿り、与えられたパケットヘッダｘに対応する通信ネットワーク８３内の経路を検索する（図２８に示すアルゴリズム４）。このアルゴリズム４では、入力となるヘッダのビット列を、Ｋビットごとに区切った「配列」パケットヘッダｐｋｔとみなす。図２９に、６ビットのパケットヘッダをＫ＝２ビットごとの配列で扱う例を示す。パケットヘッダｐｋｔ［０］とすると０、１番目の２ビット（０１）を得られ、パケットヘッダｐｋｔ［１］で２、３番目の２ビット（０１）を得られる。一般には、パケットヘッダｐｋｔ［ｉ］は［Ｋｉ，Ｋ（ｉ＋１）−１］の範囲のビット列を表す。

Ｆ．ｂは、ＭＤＤ ｎｏｄｅ Ｆに対応づけられたビットのうち、もっとも小さい値を表す。たとえば、図２１のＭＤＤ のｒｏｏｔ ｎｏｄｅは０、１番目のビットに対応づけられているので、Ｆ．ｂ＝０となる。アルゴリズム４は、配列アクセスだけによって高速に子ノードを辿り、終端ノードに到達して通信ネットワーク８３内のパケットの経路を得る。

アルゴリズム４について説明する。アルゴリズム４では、Ｆ^（ｋ）が終端ノードでない期間、ｘ’＝パケットヘッダｐｋｔ［Ｆ^（ｋ）．ｂ/Ｋ］及びＦ^（ｋ）＝Ｆ^（ｋ）．Ｃｈｉｌｄ［ｘ’］を計算することにより経路探索を行い、検索結果Ｆ^（ｋ）を出力する。

図２９のパケットヘッダを用いて、図２１のＭＤＤ Ｆ^（Ｋ）を辿る例を説明する。まず、ｒｏｏｔ ｎｏｄｅはＦ^（Ｋ）．ｂ＝０であるから、パケットヘッダｐｋｔ［０／Ｋ］＝１となり、Ｆ^（Ｋ）．ｃｈｉｌｄ［１］によってＦ^（Ｋ）を更新する。

この更新操作は、図２１の太いパスをひとつ進むことに相当する。次のノードではＦ^（Ｋ）．ｂ＝２であり、パケットヘッダｐｋｔ［２／Ｋ］＝１を得て、Ｆ^（Ｋ）．ｃｈｉｌｄ［１］でパスをまたひとつ進む。最後は、Ｆ^（Ｋ）．ｂ＝４、パケットヘッダｐｋｔ［４／Ｋ］＝３となり、Ｆ^（Ｋ）．ｃｈｉｌｄ［３］＝Ｉであり、領域Ｉに対応する通信ネットワーク８３内の経路を得る。アルゴリズム４の計算量は、ＭＤＤのパス長に依存するが、ＭＤＤに含まれるパス数（矩形数）には依存しない。

本実施形態に係る経路特定部２２は受信したパケットの通信ネットワーク８３内の経路を、ＭＤＤ Ｆ^（Ｋ）を検索することにより辿りついた終端ノードに割り当てられている経路に設定する。ここで、経路特定部２２が用いるＭＤＤ Ｆ^（Ｋ）は、多分決定木構築部１２２で構築したＭＤＤ Ｆ^（Ｋ）又は多分決定木構築部１２２で構築した後、ビット集約部１２３でビット集約したＭＤＤ Ｆ^（Ｋ）である。

なお、パケット送受信部２１は、動作設定表に基づいてパケットを転送してもよいが、経路特定部２２の設定した通信ネットワーク８３内の経路に基づいて、パケット送受信部２１が受信したパケットを転送してもよい。

本発明は情報通信産業に適用することができる。

１１：パケット送受信部
１２：経路導出部
１２１：二分決定木生成部
１２２：多分決定木構築部
１２３：ビット集約部
１４：カウンタ集計表
１５：カウンタ評価部
１６：警報発生部
２１：パケット送受信部
２２：経路特定部
２３：カウンタ表
８１、８３：通信ネットワーク
８２：コントローラ

Claims (8)

1. 複数のスイッチが接続されている通信ネットワークに備わる前記スイッチ及び前記スイッチに接続されている制御装置を備える通信システムであって、
   前記複数のスイッチが、
   パケットのヘッダ空間における領域ごとに出力方路を定めた動作設定表を前記制御装置に送信する送信部と、
   パケットのヘッダ空間における領域で定められる前記通信ネットワーク内の経路を、前記制御装置の生成した多分決定木を用いて特定する経路特定部と、
   前記経路特定部の特定した経路のカウンタ値を増加させるカウンタ表と、を備え、
   前記制御装置が、
   前記動作設定表を前記複数のスイッチから取得し、前記複数のスイッチの前記動作設定表を用いて、パケットのヘッダ空間における領域を定めるビット列を非終端ノードとしかつ前記通信ネットワーク内の経路を終端ノードとする多分決定木を生成する経路導出部と、
   前記複数のスイッチから前記カウンタ表を取得してカウンタ集計表を作成し、前記通信ネットワーク内の経路ごとのカウンタ値がスイッチ間で一致するか否かを判定するカウンタ評価部と、を備える、
   通信システム。
2. 前記経路導出部は、
   前記ヘッダ空間における領域を定めるビット列を二分決定木に変換し、前記二分決定木の各終端ノードに割り当てられている前記通信ネットワーク内の経路毎に、根ノードから各終端ノードへのパスが共通する二分決定木の終端ノードに到達しうる二分決定木を生成する二分決定木生成部と、
   前記パスの異なる各二分決定木のうちのビット列の共通する非終端ノードを共有させ、根ノードから各終端ノードへの多分決定木を構築する多分決定木構築部と、
   前記多分決定木構築部で構築した前記多分決定木の根ノードから終端ノードのパス方向に隣接する複数の非終端ノードを１つの非終端ノードに集約するビット集約部と、
   を備える請求項１に記載の通信システム。
3. 複数のスイッチが接続されている通信ネットワークに備わる前記スイッチとして機能する通信装置であって、
   パケットのヘッダ空間における領域ごとに出力方路を定めた動作設定表と、
   パケットのヘッダ空間における領域で定められる前記通信ネットワーク内の経路を、前記複数のスイッチに接続されている制御装置の生成した多分決定木を用いて特定する経路特定部と、
   前記経路特定部の特定した経路のカウンタ値を増加させるカウンタ表と、
   を備え、
   前記多分決定木は、前記複数のスイッチに備わる動作設定表を用いて構成される、パケットのヘッダ空間における領域を定めるビット列を非終端ノードとしかつ前記通信ネットワーク内の経路を終端ノードとする多分決定木である、
   通信装置。
4. 複数のスイッチが接続されている通信ネットワークに備わる前記スイッチに接続されている制御装置であって、
   パケットのヘッダ空間における領域ごとに出力方路を定めた動作設定表を前記複数のスイッチから取得する受信部と、
   前記複数のスイッチの前記動作設定表を用いて、パケットのヘッダ空間における領域を定めるビット列を非終端ノードとしかつ前記通信ネットワーク内の経路を終端ノードとする多分決定木を生成する経路導出部と、
   前記多分決定木を前記複数のスイッチに送信する送信部と、
   前記通信ネットワーク内の経路ごとにカウンタ値が記載されたカウンタ表を前記複数のスイッチから取得してカウンタ集計表を作成し、前記通信ネットワーク内の経路ごとのカウンタ値がスイッチ間で一致するか否かを判定するカウンタ評価部と、
   を備える制御装置。
5. 複数のスイッチが接続されている通信ネットワークに備わる前記スイッチが実行するトラフィック観測方法であって、
   パケットのヘッダ空間における領域で定められる前記通信ネットワーク内の経路を、前記複数のスイッチに接続されている制御装置の生成した多分決定木を用いて特定し、特定した経路のカウンタ値をカウンタ表において増加させるカウント手順と、
   前記カウンタ表を前記制御装置に送信する送信手順と、
   を順に有し、
   前記多分決定木は、前記複数のスイッチに備わる動作設定表を用いて構成される、パケットのヘッダ空間における領域を定めるビット列を非終端ノードとしかつ前記通信ネットワーク内の経路を終端ノードとする多分決定木である、
   トラフィック観測方法。
6. 複数のスイッチが接続されている通信ネットワークに備わる前記スイッチと接続されている制御装置が実行するトラフィック観測方法であって、
   パケットのヘッダ空間における領域ごとに出力方路を定めた動作設定表を前記複数のスイッチから取得し、前記複数のスイッチの前記動作設定表を用いて、パケットのヘッダ空間における領域を定めるビット列を非終端ノードとしかつ前記通信ネットワーク内の経路を終端ノードとする多分決定木を生成し、前記複数のスイッチに送信する経路導出手順と、
   前記多分決定木を用いて特定された経路のカウンタ値を含むカウンタ表を前記複数のスイッチから取得してカウンタ集計表を作成し、前記通信ネットワーク内の経路ごとのカウンタ値がスイッチ間で一致するか否かを判定する判定手順と、
   を順に有するトラフィック観測方法。
7. コンピュータを、請求項３に記載の通信装置に備わる各機能部として機能させるためのプログラム。
8. コンピュータを、請求項４に記載の制御装置に備わる各機能部として機能させるためのプログラム。

Images