(57)【特許請求の範囲】
【請求項１】
複数のフィールドを含むパケットヘッダを有するパケットについて、パケットが属するフローを検索するためのフロー検索方法において、
各フィールドに対して複数のフローに該当する条件の範囲を示す下限及び上限が定められ、複数のフローに関する条件の下限及び上限により複数領域に区切られた各フィールド空間が形成され、領域毎に各フローの条件に一致するか否かを示すための各フローに対応したビットマップが形成され、全ての領域毎に該ビットマップが括りつけられたビットマップテーブルが記憶され、
パケットヘッダ内の各フィールドが各フィールド空間中のどの領域に属するかを検索し、
前記ビットマップテーブルを参照して、各フィールドが属しているフィールド空間の領域に括りつけられているビットマップを読み出し、
対象とされる全フィールドについて読出された複数のビットマップに対してビット毎に論理積演算を行い、論理積演算の結果第1の値となるビットに対応する全フローをフローの条件に一致するフローとして決定し、
条件が一致した全フローに対し該当するアクションを実行する
ことを特徴とするフロー検索方法。
【請求項２】
前記ビットマップテーブルの各領域に対するビットマップは、フローの種類分のビット数を含み、１ビットが１フローに対応し、フローの条件が一致する場合に第１の値をとり、一致しない場合に第２の値をとることを特徴とする請求項１に記載のフロー検索方法。
【請求項３】
複数のフィールドを含むパケットヘッダを有するパケットについて、パケットが属するフローを検索するためのフロー検索方法において、
各フィールドに対して複数のフローに該当する条件の範囲を示す下限及び上限が定められ、各フィールドを複数のサブフィールドに区切り、各サブフィールドの取り得る値全てに対して該サブフィールドがフローの条件に一致するか否かを示すための各フローに対応したビットマップが形成され、全てのサブフィールド毎に該ビットマップを括りつけたビットマップテーブルが記憶され、
前記ビットマップテーブルを参照して、パケットヘッダ内のフィールドを区切った各サブフィールド値に基づき、対応するビットマップを読み出し、
対象とされる全サブフィールドのビットマップに対してビット毎に論理積演算を行い、論理積演算の結果第1の値となるビットに対応する全フローをフローの条件に一致するフローとして決定し、
条件が一致した全フローに対し該当するアクションを実行する
ことを特徴とするフロー検索方法。
【請求項４】
前記ビットマップテーブルの各サブフィールドに対するビットマップは、サブフィールド値をアドレスとして全サブフィールドが取りうる全てに対して展開され、各サブフィールド値に対して、フローの種類分のビット数を含み、１ビットが１フローに対応し、フローの条件が一致する場合に第１の値をとり、一致しない場合に第２の値をとるデータを含むことを特徴とする請求項３に記載のフロー検索方法。
【請求項５】
各フローに括りつけられたアクションは、条件が一致したパケット数を含む統計データの採取処理であり、各フローに対応して統計データを記憶する統計フローテーブルに、採取された統計データを記憶することを特徴とする請求項１乃至４のいずれかに記載のフロー検索方法。
【請求項６】
複数のフローをフロー番号の小さい順に予め定められた範囲でグループ分けし、各グループ単位でパケットの属するフローを検索し、条件が一致したフローに対するアクションを実行する処理を全グループに対し行うことを特徴とする請求項１乃至５のいずれかに記載のフロー検索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、フロー検索方法に係り、特に、ネットワーク中継装置内で、パケットヘッダ内の送信元アドレス、宛先アドレス等の複数のフィールドに基づきパケットのフローを識別し、フローの条件が成立した全てのフローに対しフロー毎に統計採取等のアクションを行うようにしたパケットのフロー検索方法に関する。
【０００２】
【従来の技術】
一般に、ネットワークシステムにおいては、複数のルータやブリッジ等のネットワーク中継装置が相互に接続され、末端には、パーソナルコンピュータ、サーバ等のパケットの送信元、及び／又は宛先となる端末装置が接続される。ルータ等のネットワーク中継装置は、接続されているネットワークから受け取ったパケットの宛先アドレスを調べてパケットの次転送先を決定してパケットを転送する。このようなネットワークシステムにおいては、パケットの中継に複数の装置が関与するため、ネットワーク内でどの位置又は装置が混雑・輻輳しているかの特定が難しい。
【０００３】
そこで、ネットワーク内の中継装置内で中継或いは廃棄したパケットのパケット数、バイト数に関する統計を採取する機能が必要であり、そのためにＲＭＯＮ（Remote Network Monitoring）１、ＲＭＯＮ２等の統計機能に関する標準仕様が決められ、この仕様により、各ネットワーク中継装置内に採られた統計情報を、ネットワークに接続した管理装置がＳＮＭＰ(Simple Network Management Protocol)等の標準のインターフェースを用いて集計することができるようになっている。
【０００４】
また、ＲＭＯＮ１、ＲＭＯＮ２等の標準の統計仕様を含め、一般的に各ネットワーク中継装置で有効な統計仕様として、パケットヘッダ内の複数のフィールドを見てフローを識別し、フロー毎に統計を採取する、という仕様がある。例えば、転送元ＩＰアドレスが指定された範囲内で、かつ、宛先ＩＰアドレスが指定された範囲内で、かつ、宛先ＴＣＰポート番号が指定された値、という条件に属するパケットの統計を採ると、特定のサイトから特定のサイトへの特定のアプリケーションに属するパケットがどのくらい流れたかを知ることができ、ネットワークの高負荷の原因になっているアプリケーションの特定や、高負荷になっている装置や回線の特定ができる。また、この統計を継続的に観測することにより、ネットワーク負荷の増加傾向が把握でき、高負荷によるパケットロス、遅延増大等が顕在化する前に、ネットワークの設備増強計画を立てることができる。
【０００５】
このような、統計採取のためのフロー検索仕様である、パケットヘッダの各フィールド毎の範囲が全て一致するパケットを検索するという仕様は、パケットのフィルタ機能でも使用される。この仕様をパケットのフィルタ機能に適用した場合の高速化手法に関する発明として、Tirunell V.Lakshman等のUS Patent Number ５、９５１、６５１ PACKET FILTER SYSTEM USING BITMAP VECTOR OF FILTER RULES FOR ROUTING PACKET THROUGH NETWORKが挙げられる。パケットのフィルタ機能では、パケットのフローに番号を付け、条件が一致したフローの内、フローの番号が最も小さいフローに対応するアクション(例えば、通過させるか廃棄させるか)をとる、という仕様の検索を行う。
【０００６】
他に、従来よりフロー検索にはＣＡＭ(Contents Addressable Memory)を使用する方法がある。一般にフロー検索を行うためのＣＡＭは、各エントリの各ビットに"１で一致／０で一致／常に一致"の３つの一致条件のどれかを設定でき、ＣＡＭの１エントリを１フローに対応させて、２５６ビット等の大きな幅の検索データの全ビットに対し、上記一致条件で一致したエントリを条件一致とし、検索結果として、条件一致となったエントリの内エントリの番号が最も小さいエントリの番号を出力するという機能がある。フローに括りつけられたアクションを得るには、出力されたエントリ番号からアクションを引くテーブルをＣＡＭの外に持ち、このテーブルの出力結果に従いアクションを行うようにする。フィルタ検索の場合にはアクションは通過させるか廃棄させるかの区別だけである。或いは、通過／廃棄の区別には１ビットの情報があれば十分なので、この情報をＣＡＭ内に持ち、ＣＡＭから検索結果としてこの情報を出させるようにする。
【０００７】
【発明が解決しようとする課題】
従来技術では、パケットヘッダ内の複数のフィールド毎にフロー毎に指定される範囲に入っているか否かを検索し、全フィールドで範囲内に入っているフローを求めるという仕様のフロー検索をフィルタにしか使用していない。そのため、従来仕様の検索では、一般的に複数のフローが同時に条件一致となるが、条件一致となったフローの内、最もフローの番号が小さいフローを抽出し、そのフローに括りつけられたアクション(通過させるか廃棄させるか)を取る、という仕様の検索を行う。
【０００８】
そこで、本発明は、複数のフローが条件一致となったときに、条件一致となった全てのフローに対し統計採取を行うことを目的とする。
フロー検索を行うのにＣＡＭを使用した場合、ＣＡＭとＣＡＭの制御論理とのデータ信号線は６４本程度しか持てないことから複数のエントリが条件一致となった場合に条件一致となったエントリの番号を全部出力するという仕様にはできず、通常は、複数の一致したエントリのエントリの内、最もエントリ番号が小さいエントリの番号を出力する、という仕様になっており、条件一致となったエントリ全てに対し、統計を採る等のアクションを取りたい場合には、ＣＡＭは使いにくかった。このような処理をＣＡＭで実現するには、条件一致となったＣＡＭのエントリを無効化し、再度検索するという処理を条件一致となるエントリが無くなるまで繰り返す必要があり、多大な時間が掛かるという課題があった。ＣＡＭの機能として、エントリの無効化等の限られた単純な処理に関しては、条件一致となった全エントリに対し同時に処理を行う機能が備わっていたが、統計を採る等の複雑な処理はサポートされていなかった。また条件一致となった全エントリに対し同時に実行できる機能は、ＣＡＭの機能として元々備わっている機能だけであり、条件一致となった全エントリに対し行いたい機能をＣＡＭの外部に設けた制御機構で自由に実現することはできなかった。ＣＡＭの機能として元々備わっている、条件一致となった全エントリに対し同時に実行できる機能の例としては、条件一致となった全エントリを無効化する、という機能が挙げられる。
【０００９】
そこで、本発明は、フィルタのようにヒットしたフローの内、最もフロー番号が小さいものをだけを求めるのではなく、ヒットした全フローを同時に求めることにより、ヒットした全フローに対し、同時にアクションを取れるようにすることを目的とする。
また、従来のフロー検索手法では、ビットマップを括りつける領域の数がフロー条件数に比例し増加し、各領域に括りつけられるビットマップの長さもフロー条件数に比例することから、ビットマップ全体のデータ量がフロー条件数の２乗で増加し、フロー条件の数を大きくできない、という課題がある。
【００１０】
そこで、本発明では、フロー条件の数が大きくなった場合にも、ビットマップのデータ量の増加を抑え、多くのフロー条件を検索可能なフロー検索手段を提供することを目的とする。
さらに、公知例に示したフロー検索手法では、パケット受信時に、そのパケットがビットマップを括りつける領域の内のどの領域に属するかを検索する必要があり、この領域の検索のために検索時間が掛かるという課題と、領域検索機構手段及び検索手段が検索を行うためのテーブルメモリが必要であるという課題があった。
【００１１】
そこで、本発明は、パケットに対し条件一致となるフローの検索を行う時に、フローの一致条件をビットマップに展開することにより高速化を図る検索方法において、各フィールド毎にパケットが属する領域を検索する、という処理を無くすことにより、領域の検索時間のを無くすことと、領域検索機構手段及び検索手段が検索を行うためのテーブルメモリを無くすことを目的とする。
【００１２】
【課題を解決するための手段】
パケットヘッダ内の複数のフィールドを範囲で検索し、全フィールドで範囲内に入っているパケットを求めるという仕様のフロー検索を高速に実行するために、各フィールド毎に空間を区切り、この区切られた領域毎にビットマップを括りつけ、パケットを受信したときには、パケットヘッダ内の各フィールド毎にどの領域に属すかを検索し、それぞれの属している領域に括りつけられているビットマップを読み出し、各フィールドのビットマップを全フィールド分、ビット毎に論理積演算を行う、という方式のフロー検索手法を、一般的に複数のフロー条件の検索の高速化に適用するため、同時にヒットした複数のフローに対応するビットの内の最もフロー番号が小さいビットを抽出する機構を無くし、論理積演算の結果１が立っているビットに対応するフロー全てに対し、アクションを行うものとする。アクションの種類としては例えば、ヒットしたフロー毎にパケット数、及び／又はバイト数の統計を採取する、というアクションが挙げられる。
【００１３】
また、上記フロー検索手法で、ビットマップのデータ量が、フロー条件の数の２乗で増加し、ビットマップの作成処理時間が増大すること、及びビットマップを保持しておくメモリ量が増大することからフロー条件の数を大きくできないという問題に対しては、全フローを一度に検索するのではなく、フローの番号の小さい順に、ある程度ずつ、例えば２５６個ずつに区切り、区切られたグループ毎にフロー番号の小さい順に検索することにより、ビットマップ全体のデータ量がフロー条件の数の１乗でしか大きくならないようにでき、フロー条件の数を例えば４０９６条件程度まで大きくしても実用に耐えられる程度のビットマップのデータ量にできる。
【００１４】
さらに、上記フロー検索手法で、パケット受信時に、そのパケットがビットマップを括りつける領域の内のどの領域に属するかを検索する必要があり、この領域の検索のために検索時間が掛かるという問題と、領域検索機構手段及び検索手段が検索を行うためのテーブルメモリが必要であるという問題に対しては、送信元ＩＰアドレス、宛先ＩＰアドレス、送信元ポート番号、宛先ポート番号等の検索に必要なフィールドを例えば８ビット程度の少ないビット数のフィールドに区切り、この区切られた各フィールドを各フロー条件の範囲の境界で区切るのでは無く、各フィールド空間を全部テーブル上に展開し、各フィールド値に対し、ビットマップを括りつけるようにする。
【００１５】
【発明の実施の形態】
図１に、本発明の実施の形態のルータ装置が適用されるネットワークシステム全体の概念図を示す。このシステムは、パケットの送信元および受信先になり得るホスト１〜３、パケットのヘッダ内に記述されている宛先アドレスに従いパケットを転送するルータ４、５、ホストおよびルータが直接接続され、ホストおよびルータ間のデータを伝送するサブネットワーク６〜８を備える。なお、ルータ４、５もパケットの送信元および受信先になり得る。
【００１６】
例えば、ホスト１からホスト２にパケットを転送する場合、ホスト１はインターフェース１０からサブネットワーク６を介して繋がるルータ４に向かってパケットを送出する。ルータ４はサブネットワーク６に繋がるインターフェース４０からパケットを受け取り、インターフェース４１からサブネットワーク７を介して繋がるルータ５に向かってパケットを転送する。同様にルータ５はインターフェース５０からサブネットワーク８を介して繋がるホスト２に向かってパケットを転送する。ホスト２はインターフェース２０からパケットを受け取る。サブネットワーク内の特定のルータまたはホストの特定のためにはサブネットワーク内のアドレスが使用される。
【００１７】
図２に、ルータ内部の全体ブロック図を示す。ルータ４は、パケットの入出力のインターフェースを行うネットワークインターフェースボード(ＮＩＦ： Network Interface Board)４５０〜４５５、パケットのヘッダ情報からパケットの転送先を検索しパケットを転送するルーティングプロセッサ(ＲＰ： Routing Processor) ４４０〜４４２、ルータ全体の管理、各ＲＰの制御、および、ルーティングプロトコル等の制御パケットの送受信を行い経路情報の管理等を行うルーティングマネージャ(ＲＭ： Routing Manager)４２、および各ＲＰおよびＲＭを接続し、ＲＰ間およびＲＭ、ＲＰ間のパケットの転送を行うクロスバスイッチ(ＣＳＷ： Crossbar Switch)４３を備える。各ネットワークインターフェースボード４５０〜４５５からはネットワークインターフェース４００〜４０５が繋がる。図２のＮＩＦ４００〜４０５は、図１のネットワークインターフェース４０、４１に対応するものである。ネットワークインターフェースの種類には、イーサネット等のＬＡＮ(Local Area Network)、ＷＡＮ(Wide Area Network)、ＡＴＭ(Asynchronous Transfer Mode)等があり、各ＮＩＦ４５０〜４５５はインターフェースの種類毎に異なるハードウエアで構成される。ＲＭ４２内のプロセッサ４２０はＲＭの管理を実際に実行するプロセッサであり、統計フローテーブル４２１にはルータ４で中継されるパケットの統計採取の条件が設定され、ルータ４の構成定義等により設定される。プロセッサ４２０は統計フローテーブル４２１の内容を読んで、各ＲＰ４４０、４４１、４４２に統計フローテーブルの情報を配布する。
【００１８】
図３および図４に、ＲＰ４４０の内部のブロック図（１）および（２）を示す。図３はＮＩＦから入ってきたパケットを転送するパケット転送ユニット４４００とＣＳＷから入ってきたパケットを転送するパケット転送ユニット４４０１を別々に設ける場合のＲＰの構成例であり、一方、図４は一つのパケット転送ユニット４４１０がＮＩＦから入ってきたパケットとＣＳＷから入ってきたパケットのどちらの転送処理も行う場合のＲＰの構成例である。パケット転送ユニット４４００及び４４０１（図３）、４４１０（図４）はＲＰ内でパケットのヘッダ情報からパケットの宛先を検索し、パケットを転送するという処理を実行する。統計フローテーブル４４０３は、ＲＭ（図２の符号４２参照）内の統計フローテーブル４２１の内容をＲＭ内のプロセッサ４２０が各ＲＰ（図２の符号４４０、４４１、４４２参照）に配布したものが格納される。プロセッサ４４０２は、統計フローテーブル４０３の内容に従い、パケット転送ユニット４４００、４４０１、４４１０内の統計フロー検索用のテーブルを設定する。
【００１９】
図５、図６、図７に、パケット転送ユニット４４００、４４０１および４４１０の構成図をそれぞれ示す。パケット転送ユニット４４００、４４０１および４４１０は、パケットヘッダ操作機構４４０００、４４０１０、４４０２０と、パケット検索ユニット４４００１、４４０１１、４４０２１と、統計採取ユニット４４００２、４４０１２、４４１０２を備える。パケットヘッダ操作機構４４０００、４４０１０、４４０２０はパケットのヘッダ部分を抽出し、パケット検索ユニット４４００１、４４０１１、４４０２１に渡す。
【００２０】
パケット検索ユニット４４００１は、パケットヘッダ操作機構４４０００から渡されたパケットヘッダ情報に基づき、入力フィルタ／ＱｏＳ(Quality of Service)検索機構４４００１０によりパケットを廃棄するか転送するかの検索(フィルタリング検索)およびパケットを出力するときの出力順の優先順位の検索(ＱｏＳ検索)を行うと同時に、経路検索機構４４００１１によりパケットの次転送先の検索を行い、パケットを廃棄するか否かの情報、パケットの出力優先順位、パケットの転送先、等をパケットヘッダ操作機構４４０００に渡す。パケットヘッダ操作機構４４０００はパケット検索ユニット４４００１から渡されたパケットの転送先、パケットを廃棄するか転送するか等の情報に従い、パケットを転送、または廃棄する。
【００２１】
パケット検索ユニット４４０１１はパケットヘッダ操作機構４４０１０から渡されたパケットヘッダ情報に基づき、出力フィルタ／ＱｏＳ検索機構４４０１１０によりパケットを廃棄するか転送するかの検索(フィルタリング検索)およびパケットを出力するときの出力順の優先順位の検索（ＱｏＳ検索）を行うと同時に、出力回線表／ＡＲＰ検索機構４４０１１１により出力回線が通信可能か否かの状態、出力回線の種類(イーサネット等のＬＡＮ(Local Area Network)、ＷＡＮ(Wide Area Network)、ＡＴＭ(Asynchronous Transfer Mode)等)の検索及び出力回線への出力時に必要となる次転送先のＭＡＣアドレスの検索を行い、パケットを廃棄するか否かの情報、パケットの出力優先順位、次転送先のＭＡＣアドレス、等をパケットヘッダ操作機構４４０１０に渡す。パケットヘッダ操作機構４４０１０はパケット検索ユニット４４０１１から渡されたパケットの転送先、パケットを廃棄するか転送するか等の情報に従い、パケットを転送、または廃棄する。
【００２２】
パケット検索ユニット４４１０１は、パケット検索ユニット４４００１と４４０１１の両方の検索動作を一連の動作として行い、検索結果をパケットヘッダ操作機構４４１００に渡す。パケットヘッダ操作機構４４１００はパケット検索ユニット４４１０１から渡されたパケットの転送先、パケットを廃棄するか転送するか等の情報に従い、パケットを転送、または廃棄する。
【００２３】
ここで、入力フィルタ／ＱｏＳ検索機構４４００１０、４４０２１０、及び出力フィルタ／ＱｏＳ検索機構４４０１１１、４４０２１２は、受信したパケットのヘッダ条件に従いパケットを分類し、この分類(以後フローと呼ぶ)毎に、フローに括りつけられているアクションを行う、という処理を行うことにより、フィルタリング検索及びＱｏＳ検索を実現する。入力フィルタ／ＱｏＳ検索機構及び出力フィルタ／ＱｏＳ検索機構で実現されるアクションの種類の例としては、廃棄させるか通過させるかの動作をさせるフィルタ機能、パケットをデスティネーションＩＰアドレスによる経路検索により決まる通常の次転送先に転送するのではなく明示的に次転送先を指定するポリシールーティング機能、パケットを送信するときに出力ポートが輻輳していたときにどのパケットを優先して送信するか或いは出力キューにパケットが溜まってきたときにどのパケットを優先して廃棄させるかを指定するＱｏＳ(Quality of Service)値を出力するＱｏＳ検索機能、或いはパケットの入力帯域を監視し、決められた帯域以上に入ってきたパケットを廃棄する、あるいは廃棄されやすくなるように廃棄に関するＱｏＳ値を下げる、あるいはＩＰヘッダ内のＴＯＳ(Type of Service)値を変える、等が挙げられる。ここで、上記決められた帯域とは、ルータの管理者がルータに監視帯域を設定する、或いはネットワーク内で、ネットワーク全体のトラフィックを管理するポリシーサーバから設定する、等の方法により設定されるものである。
【００２４】
また、ネットワーク業者が各契約ユーザが各フローに対応するようにＱｏＳのフロー条件を設定し、各フロー毎にデータ転送速度の監視を行い、このフローのデータ転送速度がこのフローを流しているユーザとの間で契約している帯域以上のパケットを廃棄したり輻輳時に優先して廃棄するようにする機能(帯域監視機能)、またはネットワークユーザがネットワーク業者のネットワークにパケットを送信する時にルータから各フローに属するパケットデータを出力する速度をネットワーク業者との間で契約している帯域以内に制限する機能(シェイピング機能)がある。
【００２５】
上記のようにパケット検索ユニット４４００１、４４０１１、４４１０１で経路検索、入力フィルタ／ＱｏＳ検索、出力回線表／ＡＲＰ検索、出力フィルタ／ＱｏＳ検索を行った結果、中継あるいは廃棄されたパケットのパケット数、および／またはバイト数の統計を採取するユニットが、統計採取ユニット４４００２、４４０１２、４４１０２である。
統計採取ユニット４４００２、４４０１２、４４１０２では、統計を採取する単位としてフローという概念を導入し、パケットがどのフローに属するかを検索し、条件一致となったフロー毎に通過パケット数、および／またはバイト数、廃棄パケット数、および／またはバイト数を採取する。
【００２６】
図８に、フィルタリングの統計フローテーブルの説明図の一例を示す。パケットの属するフローの検索仕様の例として、図示の通り、送信元ＩＰアドレス範囲がＳＩＰ（送信元ＩＰアドレス）範囲０、宛先ＩＰアドレス範囲がＤＩＰ（宛先ＩＰアドレス）範囲０という条件のフロー(フロー０)、送信元ＩＰアドレス範囲がＳＩＰ範囲１、宛先ＩＰアドレス範囲がＤＩＰ範囲１という条件のフロー(フロー１)、送信元ＩＰアドレス範囲がＳＩＰ範囲２、宛先ＩＰアドレス範囲がＤＩＰ範囲２という条件のフロー(フロー２)が定義された統計フローテーブルを検索する場合を考える。この例では、各フロー毎に中継パケット数、廃棄パケット数の統計カウンタが括りつけられているが、さらに、中継バイト数、廃棄バイト数の統計カウンタを設ける例も考えられる。
【００２７】
図９は、図８に示す各フローが、送信元ＩＰアドレス×宛先アドレス空間内の、どの領域でヒットするかを示した図である。各フロー条件は一般的には排他ではないので、複数のフローに同時にヒットする場合もある。領域９０、９１、９２はフロー０、１、２の条件一致領域であり、領域９０２はフロー０と２の条件一致領域、領域９１２はフロー１と２の条件一致領域、領域９０１２はフロー０、１、２の条件一致領域である。
【００２８】
送信元ＩＰアドレスと宛先ＩＰアドレスが領域９０、９１、９２内にあるパケットに対しては、フロー０、１、２に対する統計を採取する必要があるので、領域９０２内にあるパケットに対してはフロー０と２に対する統計を採取し、領域９１２内にあるパケットに対してはフロー１と２に対する統計を採取し、領域９０１２内にあるパケットに対してはフロー０、１と２に対する統計を採取する必要がある。
【００２９】
図１０に、図８及び図９に示す統計フロー検索方法を示す図である。この方法では、全フローの送信元ＩＰアドレス範囲の境界で送信元ＩＰアドレス空間９４を区切り、この区切られた各領域９４１、９４２、９４３、９４４、９４５、９４６に対し、各フローで送信元ＩＰアドレスがヒットするか否かをビットマップ９４１１、９４２１、９４３１、９４４１、９４５１、９４６１として括りつける。宛先ＩＰアドレスに関しても同様に、全フローの宛先ＩＰアドレス範囲の境界で宛先ＩＰアドレス空間９５を区切り、この区切られた各領域９５１、９５２、９５３、９５４、９５５、９５６、９５７に対し、各フローで宛先ＩＰアドレスがヒットするか否かをビットマップ９５１１、９５２１、９５３１、９５４１、９５５１、９５６１、９５７１として括りつける。
【００３０】
パケットを受信したときにはまず、パケットヘッダ内の送信元ＩＰアドレス９４０、宛先ＩＰアドレス９５０がそれぞれ、送信元ＩＰアドレス空間内、宛先ＩＰアドレス空間内で属している領域９４５、９５４を検索する。つぎに、それぞれの属している領域に括りつけられているビットマップ９４５１、９５４１を読み出し、論理積機構９６によりビット毎に論理積演算を行い、論理積演算の結果、１が立っているビットに対応するフローを全てヒットとし、このフロー毎に統計採取を行う。この例では、フロー０及び２にヒットしている。
【００３１】
図１１に、図１０に示したフロー検索アルゴリズムを実現するハードウエア機構の構成図を示す。送信元ＩＰアドレス領域境界テーブル２１０には、図１０の送信元ＩＰアドレス範囲の境界９４１２、９４２２、９４３２、９４４２、９４５２、９４６２が格納されている。宛先ＩＰアドレス領域境界テーブル２２０は図１０の宛先ＩＰアドレス範囲の境界９５１２、９５２２、９５３２、９５４２、９５５２、９５６２、９５７２が格納されている。領域検索機構２１１は、送信元ＩＰアドレス領域境界テーブル２１０を読んで、送信元ＩＰアドレスが領域９４１、９４２、９４３、９４４、９４５、９４６の内のどの領域内にあるかを検索する。領域検索機構２２１は、宛先ＩＰアドレス領域境界テーブル２２０を読んで、宛先ＩＰアドレスが領域９５１、９５２、９５３、９５４、９５５、９５６、９５７の内のどの領域内にあるかを検索する。送信元ＩＰアドレスビットマップテーブル２１２は、領域検索機構２１１で検索された領域（図１０の符号９４５参照）からその領域に括りつけられたビットマップ（図１０の符号９４５１参照）を引く。宛先ＩＰアドレスビットマップテーブル２２２は、領域検索機構２２１で検索された領域（図１０の符号９５４参照）からその領域に括りつけられたビットマップ（図１０の９５４１）を引く。論理積機構２５は、各ビットマップ９４５１、９５４１の各ビット毎に論理積をとる。統計カウンタ２６は、論理積演算の結果１が立っているビットに対応するフローの統計カウンタ値を更新させるように動作する。
【００３２】
送信元ＩＰアドレス領域境界テーブル２１０、宛先ＩＰアドレス領域境界テーブル２２０、送信元ＩＰアドレスビットマップテーブル２１２、宛先ＩＰアドレスビットマップテーブル２２２には、ＲＰ内のプロセッサ（図３、図４の符号４４０２参照）が統計フローテーブル４４０３に格納された図８のような形式の統計フローテーブルから図１０に示すような形式に展開したテーブル内容を格納する。
【００３３】
次に、図１２に、領域検索機構２１１の動作を示す図である。この図は図１１の領域検索機構２１１が、送信元ＩＰアドレス９４０が送信元ＩＰアドレス領域境界テーブル２１０内のどの境界の間にあるかを検索するときの動作の概念図であり、どの境界の間にあるかが判らない状態から領域を絞り込んでいくことにより、どの領域の境界にあるかを得る、という動作を示している。領域絞り込み１回目では送信元ＩＰアドレス９４０と領域境界テーブルエントリの中間のエントリ９４４２との大小比較をし、どちら側の領域にあるかを判定する。領域絞り込み２回目では送信元ＩＰアドレス９４０と１回目に絞り込まれた範囲９４４２〜最大値（１６進表示で０ｘ１００００００００）の中間のエントリ９４５２との大小比較をし、どちら側の領域にあるかを判定する。同様に絞り込み３回目では送信元ＩＰアドレス９４０と２回目に絞り込まれた範囲９４５２〜最大値（１６進表示で０ｘ１００００００００）の中間のエントリ９４６２との大小比較をし、どちら側の領域にあるかを判定する。３回の領域絞り込みにより、送信元ＩＰアドレス９４０は隣接する領域境界９４５２と９４６２の間にあること、即ち領域９４５内にあることが判る。図１２で、黒丸は送信元ＩＰアドレスが領域境界に一致する場合を含み、白丸は領域境界に一致する場合を含まない、という意味である。
【００３４】
なお、上述の実施の形態では、フロー検索に用いるフィールドとして、送信元ＩＰアドレスと宛先ＩＰアドレスの２個を用いたが、一般的には、フィールドの数はこれだけに限られる訳では無く、例えば、送信元ＩＰアドレス、宛先ＩＰアドレスに、ＴＣＰ又はＵＤＰの送信元ポート番号、宛先ポート番号を加えた４個を用いる場合も有り得る。この場合、各フィールド毎にそれぞれの空間を、全フローの各フィールドの範囲の境界で区切り、この区切られた各領域に対し、各フローがヒットするか否かをビットマップとして括りつける。パケットを受信したときには、パケットヘッダ内の各フィールド毎に、どの領域に属すかを検索し、それぞれの属している領域に括りつけられているビットマップを読み出し、各フィールドのビットマップを全フィールド分、ビット毎に論理積演算を行い、論理積演算の結果、１が立っているビットに対応するフローを全てヒットとし、このフロー毎に統計採取を行う。
【００３５】
次に、図１３に、フローの送信元ＩＰアドレス範囲とビットマップとの対応を表す図を示す。この例では、送信元ＩＰアドレス、宛先ＩＰアドレス、送信元ポート番号、宛先ポート番号等の検索に必要なフィールドを例えば８ビット程度の少ないビット数のフィールドに区切り、この区切られた各フィールドを各フロー条件の範囲の境界で区切るのでは無く、各フィールド空間を全部テーブル上に展開し、各フィールド値に対し、ビットマップを括りつけるという技術内容を説明する。
【００３６】
例えば、フロー０の送信元ＩＰアドレス範囲１１０が１６進表示で０ｘ０１２３４５６７〜０ｘ０１２３４５８９（”０ｘ”  ＋  ０〜Ｆの文字列で１６進表示であることを示す）、フロー１の送信元ＩＰアドレス範囲１１１が０ｘ０１２３４５００〜０ｘ０１２３６７ＦＦ、フロー２の送信元ＩＰアドレス範囲１１２が０ｘ８９ＡＢ００００〜０ｘ８９ＣＤＦＦＦＦの場合を想定する。この場合、送信元ＩＰアドレス範囲のそれぞれを２の３１乗〜２の２４乗ビット、２の２３乗〜２の１６乗ビット、２の１５乗〜２の８乗ビット、２の７乗〜２の０乗ビットで区切り、区切られた各フィールド（以下サブフィールドと呼び、それぞれのサブフィールドをビットの重みが重い方から順にＳＩＰ０、ＳＩＰ１、ＳＩＰ２、ＳＩＰ３と呼ぶ）毎に、フィールドが取り得る値全て、即ち１６進表示で０ｘ００〜０ｘＦＦの全ての値に対し、フィールドの値がフローに属する場合に１、属さない場合に０の値をとるビットマップ９８０、９８１、９８２、９８３を作成する。
【００３７】
例えばフロー０はＳＩＰ０サブフィールド値（１１００）、ＳＩＰ１サブフィールド値（１１０１）、ＳＩＰ２サブフィールド値（１１０２）、ＳＩＰ３サブフィールド値（１１０３）としてそれぞれ０ｘ０１、０ｘ２３、０ｘ４５、０ｘ６７〜０ｘ８９をとるので、フロー０のＳＩＰ０サブフィールドに対応するビットマップはサブフィールド値が０ｘ０１のところだけ１で他は０というビットマップになり、ＳＩＰ１サブフィールド値に対応するビットマップはサブフィールド値が０ｘ２３のところだけ１で他は０というビットマップになり、ＳＩＰ２サブフィールド値に対応するビットマップはサブフィールド値が０ｘ４５のところだけ１で他は０というビットマップになり、ＳＩＰ３サブフィールド値に対応するビットマップはサブフィールド値が０ｘ６７〜０ｘ８９のところだけ１で他は０というビットマップになる。フロー１、フロー２についても同様にビットマップに展開すると、図示のように、各々ＳＩＰ０、ＳＩＰ１、ＳＩＰ２、ＳＩＰ３サブフィールドに対応するビットマップは９８０、９８１、９８２、９８３に示す通りとなる。
【００３８】
受信したパケットに対し検索を行うときには、受信パケットの送信元ＩＰアドレス９４０について、各ＳＩＰ０、ＳＩＰ１、ＳＩＰ２、ＳＩＰ３サブフィールド値９４００、９４０１、９４０２、９４０３をアドレスとして、各サブフィールド毎のビットマップのテーブル９８０、９８１、９８２、９８３を引き（参照し）、つぎに、各サブフィールド毎に得られたビットマップを、各ビット毎に全フィールドに対し論理積を取るようにする。例えば、受信パケットの送信元ＩＰアドレス９４０が０ｘ０１２３４５７８の場合、ＳＩＰ３、ＳＩＰ２、ＳＩＰ１、ＳＩＰ０サブフィールド値９４００、９４０１、９４０２、９４０３はそれぞれ０ｘ０１、０ｘ２３、０ｘ４５、０ｘ７８であり、各サブフィールド値をアドレスとしてＳＩＰ０、ＳＩＰ１、ＳＩＰ２、ＳＩＰ３のビットマップ９８０、９８１、９８２、９８３を引いたビットマップの値９８００、９８１０、９８２０、９８３０はそれぞれ１１０、１１０、１１１、１１１となり、論理積演算９６を行うと１１０となり、送信元ＩＰアドレス０ｘ０１２３４５７８に対してはフロー０と１が条件に一致するという結果が得られる。宛先ＩＰアドレス、送信元ポート番号、宛先ポート番号等の他のフィールドについても同様の方法で受信パケットが条件一致となるフローが得られ、全フィールドについて得られたビットマップの論理積を取ることにより、全フィールドに対し条件一致となるフローを得ることができる。
【００３９】
つぎに、図１４に、図１３に示したフロー検索アルゴリズムを実現するハードウエア機構の構成図を示す。ビットマップテーブル２１２０、２１２１、２１２２、２１２３は、それぞれＳＩＰ０、ＳＩＰ１、ＳＩＰ２、ＳＩＰ３サブフィールドに対応し、それぞれ送信元ＩＰアドレスのＳＩＰ０、ＳＩＰ１、ＳＩＰ２、ＳＩＰ３サブフィールド値をアドレスとしてビットマップテーブルを読むことにより、送信元ＩＰアドレスのＳＩＰ０、ＳＩＰ１、ＳＩＰ２、ＳＩＰ３サブフィールドが条件一致となるフローに対応するビットに１が立っているビットマップが得られる。宛先ＩＰアドレスに対しても同様に、ビットマップテーブル２２２０、２２２１、２２２２、２２２３により、宛先ＩＰアドレスの２の３１乗〜２４ビット、２の２３乗〜２の１６乗ビット、２の１５乗〜２の８乗ビット、２の７乗〜２の０乗ビット（以下サブフィールドと呼び、それぞれのサブフィールドをビットの重みが重い方から順にＤＩＰ０、ＤＩＰ１、ＤＩＰ２、ＤＩＰ３と呼ぶ）が条件一致となるフローに対応するビットに１が立っているビットマップが得られる。論理積機構２５は、これらの全ビットマップを全サブフィールド分、ビット毎に論理積演算を行う。統計カウンタ２６は、論理積演算の結果１が立っているビットに対応するフローの統計カウンタ値を更新させるように動作する。
【００４０】
ＳＩＰ０、ＳＩＰ１、ＳＩＰ２、ＳＩＰ３、ＤＩＰ０、ＤＩＰ１、ＤＩＰ２、ＤＩＰ３についてのビットマップテーブル２１２０、２１２１、２１２２、２１２３、２２２０、２２２１、２２２２、２２２３には、ＲＰ内のプロセッサ（図３、図４の４４０２）が統計フローテーブル４４０３に格納された図１の１１の形の統計フローテーブルから図１３に示す形に展開したテーブル内容を格納する。
【００４１】
つぎに、図１５に、フローを区切ってフロー条件を検索するフロー検索方法の概念図を示す。この図では、図１０に示した、各フィールドに対し全フローの範囲の境界で各フィールドの空間を区切り、この区切られた各領域にビットマップを括りつけるフロー検索手法では、空間を分割する範囲の境界の数がフロー条件の数に比例し増加し、括りつけられた各ビットマップの長さもフロー条件数の数に比例し増加するので、ビットマップ全体のデータ量がフロー条件の数の２乗で増加し、ビットマップの作成処理時間が増大すること、及びビットマップを保持しておくメモリ量が増大することからフロー条件の数を大きくできないという点を回避するための方法を示す。このフロー検索方法では、全フロー１１を一度に検索するのではなく、フローの番号の小さい順にある程度ずつ（例えば、２５６個ずつ）に区切り、区切られたグループ１１０、１１１、１１１、１１Ｆ毎にビットマップ１２０、１２１、１２２、１２Ｆに展開し、フロー番号の小さい順に検索することにより、ビットマップ全体のデータ量がフロー条件の数の１乗でしか大きくならないようにでき、フロー条件の数を（例えば４０９６条件程度まで）大きくしても実用に耐えられる程度のビットマップのデータ量にできる。
【００４２】
本実施の形態のように、検索に必要なフィールドを例えば８ビット程度の少ないビット数のフィールドに区切り、この区切られた各フィールド空間を全部テーブル上に展開し、各フィールド値に対しビットマップを括りつけるというフロー検索手法では、空間を範囲に分割するという操作を行わないので、ビットマップ全体のデータ量は、各ビットマップの長さに比例、即ちフロー条件の数に比例にでき従来技術の検索手法でビットマップ全体のデータ量がフロー条件の２乗に比例して増加したのに対し、データ量の増加を抑えるという効果が元々備わっている。従ってこの検索方法ではフロー条件の数をある程度ずつ区切る上記方法を採用してもビットマップの増加を抑えるという効果は新たには生じない。
【００４３】
【発明の効果】
本発明によると、例えば、パケットヘッダ内の複数のフィールドを範囲で検索し、全フィールドで範囲内に入っているパケットを求めるという仕様のフロー検索を高速に実行するために、一致条件をフィールド毎にビットマップに展開し、各フィールド毎にフロー条件に一致するか否かをビットマップとして得て、これらのビットマップを全フィールド分、論理積を取ることにより全フィールドについて条件一致となるフローを求めるというフロー検索手段により、複数のフローが同時に条件一致となった場合にも、全フローの番号を同時に得ることができ、条件一致となった全フローに対し同時にアクションを行うことができる。
【００４４】
また、本発明によると、全フローを一度に検索するのではなく、フローの番号の小さい順に、ある程度ずつ（例えば２５６個ずつ）に区切り、区切られたグループ毎にフロー番号の小さい順に検索することにより、ビットマップ全体のデータ量をフロー条件の数の１乗でしか大きくならないようにでき、フロー条件の数を（例えば４０９６条件程度まで）大きくしても実用に耐えられる程度のビットマップのデータ量にできる。
【００４５】
本発明によると、送信元ＩＰアドレス、宛先ＩＰアドレス、送信元ポート番号、宛先ポート番号等の検索に必要なフィールドを（例えば８ビット程度の）少ないビット数のフィールドに区切り、この区切られた各フィールド毎に条件一致となるか否かのビットマップを、区切られた各フィールドの値をアドレスとして引くようにテーブル展開できる量にまで小さくできるので、パケットがビットマップを括りつける領域の内のどの領域に属するかを検索するという処理を不要にでき、検索処理を高速化でき、また、領域検索機構及び検索機構が検索を行うためのテーブルメモリを削減できるという効果がある。
【００４６】
さらに、本発明によると、各フィールド毎に全フローの範囲の境界で空間を区切るという処理が無いので、ビットマップ全体のデータ量は各フィールド値でアドレッシングされるビットマップの長さに比例してしか増加せず、即ちフロー条件数の１乗でしか増加せず、フロー条件の数を（例えば４０９６条件程度まで）大きくしても実用に耐えられる程度のビットマップのデータ量にできる。
【図面の簡単な説明】
【図１】本実施の形態のルータが適用されるネットワークシステム全体図。
【図２】本実施の形態のルータ全体の内部構成ブロック図。
【図３】本実施の形態のルーティングプロセッサ内部ブロック図(転送方向によりパケット転送ユニットを独立に持つ場合のブロック図)。
【図４】本実施の形態のルーティングプロセッサ内部ブロック図(一つのパケット転送ユニットが、両方向のパケット転送処理を行う場合のブロック図)。
【図５】本実施の形態のパケット転送ユニットの内部ブロック図(上り処理のみを行う場合)。
【図６】本実施の形態のパケット転送ユニットの内部ブロック図(下り処理のみを行う場合)。
【図７】本実施の形態のパケット転送ユニットの内部ブロック図(上り処理と下り処理の両方を行う場合)。
【図８】フィルタリングの統計フローテーブルの説明図。
【図９】送信元×宛先ＩＰアドレス空間内でフロー条件が一致する領域を示す図。
【図１０】ビットマップを用いたフロー条件の一致検索処理を示す図(条件一致したフローを全て同時に得る方法)。
【図１１】本実施の形態の統計採取ユニットの内部ブロック図。
【図１２】本実施の形態の統計採取ユニット内の領域検索機構の動作を示す図。
【図１３】本実施の形態のフローの送信元ＩＰアドレス範囲とビットマップとの対応を表す図(送信元ＩＰアドレスを８ビットずつ区切る方法)。
【図１４】本実施の形態の統計採取ユニット内の領域検索機構の動作を示す図(送信元ＩＰアドレスを８ビットずつ区切る方法)。
【図１５】本実施の形態のフローを区切って検索するフロー検索法の概念図。
【符号の説明】
１１．統計フローテーブル
９．送信元×宛先ＩＰアドレス空間
９０．フロー０条件一致領域
９１．フロー１条件一致領域
９２．フロー２条件一致領域
９０２．フロー０と２の条件一致領域
９１２．フロー１と２の条件一致領域
９０１２．フロー０、１と２の条件一致領域
９４．送信元ＩＰアドレス空間
９５．宛先ＩＰアドレス空間
９４０．パケットの送信元ＩＰアドレス
９５０．パケットの宛先ＩＰアドレス
９６．論理積機構
１〜３．ホスト
４〜５．ルータ
６〜８．サブネットワーク
４００〜４０５．ネットワークインターフェース
４２．ルータ制御部(ＲＭ)
４２０．プロセッサ
４２１．統計フローテーブル
４３．クロスバスイッチ(ＣＳＷ)
４４０〜４４２．ルーティングプロセッサ
４５０〜４５５．ネットワークインターフェースボード(ＮＩＦ)
４４００、４４０１、４４１０．パケット転送ユニット
４４０２．プロセッサ
４４０３．統計フローテーブル
４４０００、４４０１０、４４１００．パケットヘッダ操作機構
４４００１、４４０１１、４４１０１．パケット検索ユニット
４４００２、４４０１２、４４１０２．統計採取ユニット
４４００１０、４４１０１０．入力フィルタ／ＱｏＳ検索機構
４４００１１、４４１０１１．経路検索機構
４４０１１０、４４１０１２．出力フィルタ／ＱｏＳ検索機構
４４０１１１、４４１０１３．出力回線表／ＡＲＰ検索機構
２１０．送信元ＩＰアドレス領域境界テーブル
２１１．領域検索機構
２１２．送信元ＩＰアドレスビットマップテーブル
２２０、宛先ＩＰアドレス領域境界テーブル
２２１．領域検索機構
２２２．宛先ＩＰアドレスビットマップテーブル
２５．論理積機構
２６．統計カウンタ
１１０、１１１、１１２．フロー０、１、２の送信元ＩＰアドレス範囲
１１００、１１１０、１１２０．フロー０、１、２に対応するＳＩＰ０サブフィールドの範囲
１１０１、１１１１、１１２１．フロー０、１、２に対応するＳＩＰ１サブフィールドの範囲
１１０２、１１１２、１１２２．フロー０、１、２に対応するＳＩＰ２サブフィールドの範囲
１１０３、１１１３、１１２３．フロー０、１、２に対応するＳＩＰ３サブフィールドの範囲
９４００、９４０１、９４０２、９４０３．送信元ＩＰアドレスのＳＩＰ０、ＳＩＰ１、ＳＩＰ２、ＳＩＰ３サブフィールド値
９８０、９８１、９８２、９８３．ＳＩＰ０、ＳＩＰ１、ＳＩＰ２、ＳＩＰ３サブフィールド値に対し条件一致となるフローを展開したビットマップテーブル
９８００、９８１０、９８２０、９８３０．受信パケットの各サブフィールド値に対し検索したビットマップ
２１２０．ＳＩＰ０ビットマップテーブル
２１２１．ＳＩＰ１ビットマップテーブル
２１２２．ＳＩＰ２ビットマップテーブル
２１２３．ＳＩＰ３ビットマップテーブル
２２２０．ＤＩＰ０ビットマップテーブル
２２２１．ＤＩＰ１ビットマップテーブル
２２２２．ＤＩＰ２ビットマップテーブル
２２２３．ＤＩＰ３ビットマップテーブル
１１０、１１１、１１２、１１Ｆ．２５６個ずつ纏められたフローのグループ
１２０、１２１、１２２、１２Ｆ．２５６個ずつに纏められたフローに対応するビットマップ
【図１】
0004410432.tif 000002
【図２】
0004410432.tif 000003
【図３】
0004410432.tif 000004
【図４】
0004410432.tif 000005
【図５】
0004410432.tif 000006
【図６】
0004410432.tif 000007
【図７】
0004410432.tif 000008
【図８】
0004410432.tif 000009
【図９】
0004410432.tif 000010
【図１０】
0004410432.tif 000011
【図１１】
0004410432.tif 000012
【図１２】
0004410432.tif 000013
【図１３】
0004410432.tif 000014
【図１４】
0004410432.tif 000015
【図１５】
0004410432.tif 000016