図面 (/)

技術 データストリームにおいてデータパターンを検出する装置、方法、及びネットワークサーバ

出願人 テレフオンアクチーボラゲットエルエムエリクソン(パブル)
発明者 スザボ,ゲザアントネロ,ラファエルフェルナンデス,ステニオサドク,ドジャメル
出願日 2012年9月28日 (6年11ヶ月経過) 出願番号 2015-533458
公開日 2015年11月19日 (3年10ヶ月経過) 公開番号 2015-533243
状態 特許登録済
技術分野 検索装置
主要キーワード 簡略版 シンボル範囲 入力アルファベット 転送ループ ルックアップ処理 状態遷移テーブル 非決定性有限オートマトン データ格納量
関連する未来課題
重要な関連分野

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

図面 (7)

課題・解決手段

アルファベット文字表現する複数のデータシンボルを有するデータストリーム(37)におけるデータパターンを検出する装置(30)、方法、ネットワークサーバ(42,43,44,46,48)であり、前記装置(30)は決定性有限オートマトンを実行する。前記装置は、開始状態(11)と少なくとも1つの受入状態(14)とを含む複数の状態(11,12,13,14,15)と、前記データストリーム(37)のデータシンボルによりトリガされる初期状態から目標状態への状態遷移(16a、16b、16c)とを有する状態遷移レジスタ(31)を有する。前記装置(30)はさらに、前記状態遷移レジスタ(31)の各状態の各データシンボルに関し、前記アルファベットにおける対応する文字位置を決定する文字位置決定手段(32)を有し、さらに同じ目標状態への遷移にトリガをかける前記アルファベットにおいて対応する後続の文字位置(18b)をもつデータシンボルに関するデータシンボル範囲(18x,18y)を含ませるように前記状態遷移レジスタ(31)を更新する更新手段(33)を有する。前記装置(30)はまた、前記データストリーム(37)のデータシンボルが前記更新された状態遷移レジスタ(37)のデータシンボル範囲(18x,18y)に含まれるかどうかを判断し、前記更新された状態遷移レジスタの前記対応する目標状態を決定する範囲決定手段(34)と、前記データパターンを検出するために前記初期状態から前記決定された目標状態への状態遷移(16a,16b,16c)にトリガをかけるトリガ手段(35)とを有する。

概要

背景

通信ネットワークにより送信されるデータ量は急速に増加している。高速大容量パケットデータネットワークサーバとが採用されて、これらのデータを転送している。なかんずく試験監視を行う目的で、所望の、あるいは、合意したサービス品質QoSを保証するために、例えば、発信元アドレス宛先アドレスについてのパケットヘッダ情報だけでは要求された情報を取得するためには不十分である。ある場合には、データパケットペイロードが、例えば、特定のデータパターンに関して検査される必要がある。データマイニング、データウィルスの検出や他の悪意のあるデータは、パケットデータの検査を必要とする別の例である。

パケットを検査する方法は、有限オートマトンを採用することによるものである。有限オートマトン、あるいは、単純にステートマシンは、状態遷移テーブルまたは状態遷移レジスタに従って複数の状態で動作するアブストラクトステートマシンとして採用されるコンピュータにより制御される方法である。そのような状態遷移テーブルは、--有限オートマトンの複数の状態に関し−、現在の状態において特定のデータシンボルを入力するとき現在の初期状態から次の目標状態への遷移を有し、実際には入力データシンボルの特定の文字列のデータパターンの一致へと導くものとなる。そのようなデータシンボルは、例えば、公知のコンピュータ用アルファベット情報交換のための米国標準コード、略してASCIIのようなアルファベットに含まれるデータシンボルである。そのようなものとして、後続の目標状態への状態遷移は、非転送遷移(non-forwarding transition)と呼ばれるオートマトンの同じ状態への遷移にも関与するかもしれない。そのような場合、その状態遷移は、初期状態が目標状態に等しい遷移であり、例えば、同じ状態への非転送ループである。

一般に、2つのタイプの有限オートマトンは、決定性有限オートマトンDFA)と非決定性有限オートマトン(NFA)に区別される。DFAは、一定量のメモリアクセスだけを必要とする一方、パケットペイロード解析するので、処理速度では好ましい。そのような計算効率のコストは、状態の数と状態遷移の数とが指数関数的にメモリ要件を増大させるので、メモリ格納量が大きいことである。NFAはメモリ格納量の要件は少ないが、各状態からの次の状態は並行的に多数のものがあり得るので、可能性のある全ての場合をチェックするために多くの計算資源を必要とする。

DFAとNFAとは両方とも長所と短所とがあり、データパケット検査システムに対するソフトウェアツールにおいて採用される。

通信ネットワークにより送信されるデータ量が急速に増大しているので、有限オートマトンを使用するネットワークサーバ余りにも多くの資源、即ち、メモリ格納量、一般にはメモリ容量として示されるメモリアクセスコントローラとを必要とする。従って、有限オートマトンを実行することによりデータパターンを検出するための改善された方法が必要である。

概要

アルファベットの文字を表現する複数のデータシンボルを有するデータストリーム(37)におけるデータパターンを検出する装置(30)、方法、ネットワークサーバ(42,43,44,46,48)であり、前記装置(30)は決定性有限オートマトンを実行する。前記装置は、開始状態(11)と少なくとも1つの受入状態(14)とを含む複数の状態(11,12,13,14,15)と、前記データストリーム(37)のデータシンボルによりトリガされる初期状態から目標状態への状態遷移(16a、16b、16c)とを有する状態遷移レジスタ(31)を有する。前記装置(30)はさらに、前記状態遷移レジスタ(31)の各状態の各データシンボルに関し、前記アルファベットにおける対応する文字位置を決定する文字位置決定手段(32)を有し、さらに同じ目標状態への遷移にトリガをかける前記アルファベットにおいて対応する後続の文字位置(18b)をもつデータシンボルに関するデータシンボル範囲(18x,18y)を含ませるように前記状態遷移レジスタ(31)を更新する更新手段(33)を有する。前記装置(30)はまた、前記データストリーム(37)のデータシンボルが前記更新された状態遷移レジスタ(37)のデータシンボル範囲(18x,18y)に含まれるかどうかを判断し、前記更新された状態遷移レジスタの前記対応する目標状態を決定する範囲決定手段(34)と、前記データパターンを検出するために前記初期状態から前記決定された目標状態への状態遷移(16a,16b,16c)にトリガをかけるトリガ手段(35)とを有する。

目的

本発明の目的は、データストリームにおけるデータパターンを検出する改善された装置と方法を提供する

効果

実績

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

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

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

請求項1

アルファベット文字表現する複数のデータシンボルを有するデータストリーム(37)におけるデータパターンを検出し、決定性有限オートマトンを実行する装置(30)であって、開始状態(11)と少なくとも1つの受入状態(14)とを含む複数の状態(11,12,13,14,15)と、前記データストリーム(37)のデータシンボルによりトリガされる初期状態から目標状態への状態遷移(16a、16b、16c)とを有する状態遷移レジスタ(31)と、前記状態遷移レジスタ(31)の各状態の各データシンボルに関し、前記アルファベットにおける対応する文字位置を決定する文字位置決定手段(32)と、同じ目標状態への遷移にトリガをかける、前記アルファベットにおける対応する後続の文字位置(18b)をもつデータシンボルに関するデータシンボル範囲(18x,18y)を含ませるように前記状態遷移レジスタ(31)を更新する更新手段(33)と、前記データストリーム(37)のデータシンボルが前記更新された状態遷移レジスタ(31)のデータシンボル範囲(18x,18y)に含まれるかどうかを判断し、前記更新された状態遷移レジスタの前記対応する目標状態を決定する範囲決定手段(34)と、前記データパターンを検出するために前記初期状態から前記決定された目標状態への状態遷移(16a,16b,16c)にトリガをかけるトリガ手段(35)とを有することを特徴とする装置。

請求項2

記文位置決定手段(32)は、前記アルファベットにおける前記対応する文字位置に従って前記状態遷移レジスタ(31)の各状態に関し全てのデータシンボル(17a)をソートするよう構成されることを特徴とする請求項1に記載の装置。

請求項3

前記アルファベットは、コンピュータ用のアルファベット、特に、ACSII又は拡張ASCIIのアルファベットを含むことを特徴とする請求項1又は2に記載の装置。

請求項4

前記装置(30)は、前記データシンボル範囲における前記データシンボルの決定と前記状態遷移にトリガをかけることとには関係なく、前記文字位置の決定と前記状態遷移レジスタの更新とを実行するよう構成されることを特徴とする請求項1乃至3のいずれか1項に記載の装置。

請求項5

前記装置(30)は、前記決定性有限オートマトンの受入状態(14)への状態遷移(16a,16b,16c)がトリガされると、前記データパターンの前記検出を最終決定するよう構成されることを特徴とする請求項1乃至4のいずれか1項に記載の装置。

請求項6

前記装置(30)は、前記検出されたデータパターンに従って前記データストリーム(37)を処理するよう構成されることを特徴とする請求項1乃至5のいずれか1項に記載の装置。

請求項7

前記装置(30)は、通信ネットワーク(40)で動作し、前記通信ネットワーク(40)のデータストリーム(37)におけるデータパターンを検出するネットワークサーバ(42,43,44,47,48)であることを特徴とする請求項1乃至6のいずれか1項に記載の装置。

請求項8

コンピュータ(30)により受信される、アルファベットの文字を表現する複数のデータシンボルを有するデータストリーム(37)におけるデータパターンを検出し、前記コンピュータ(30)が、開始状態(11)と少なくとも1つの受入状態(14)とを含む複数の状態(11,12,13,14,15)と、前記データストリーム(37)のデータシンボルによりトリガされる初期状態から目標状態への状態遷移(16a、16b、16c)とを有する圧縮状態遷移レジスタ(31)を有する決定性有限オートマトンを実行する、コンピュータにより制御される方法(20)であって、前記圧縮状態遷移レジスタ(31)は少なくとも1つのデータシンボル範囲を含み、前記方法は、前記コンピュータ(30)により、前記圧縮状態遷移レジスタ(31)から、前記データストリームのデータシンボルが前記圧縮状態遷移レジスタ(31)のデータシンボル範囲(18a)に含まれるかどうかを判断し(21)、前記圧縮状態遷移レジスタの前記目標状態(18b)を決定する(22)工程と、前記コンピュータ(30)により、前記データパターンを検出するために前記初期状態から前記決定された目標状態への状態遷移(16a,16b,16c)にトリガをかける(22)工程とを有することを特徴とする方法。

請求項9

請求項8に記載の圧縮状態遷移レジスタ(31)を生成するコンピュータ(30)により制御される方法であって、前記コンピュータ(30)により、前記圧縮状態遷移レジスタ(31)の各状態の各データシンボルに関し、前記アルファベットにおける対応する文字位置を決定する工程と、前記コンピュータ(30)により、同じ目標状態への遷移(16b)にトリガをかける、前記アルファベットにおける対応する後続の文字位置をもつ複数のデータシンボルに関する複数のデータシンボル範囲(18x)を含ませるように前記圧縮状態遷移レジスタ(31)を更新する工程とを有することを特徴とする方法。

請求項10

前記アルファベットにおける前記対応する文字位置に従って、前記圧縮状態遷移レジスタ(31)の各状態に関し、前記コンピュータ(30)により全てのデータシンボル(17a)をソートする工程をさらに有することを特徴とする請求項9に記載の方法。

請求項11

前記圧縮状態遷移レジスタ(31)から状態(15)に対する各状態遷移を除去する工程をさらに有し、全ての対応する状態遷移に関しては、前記初期状態は前記目標状態に等しいことを特徴とする請求項9又は10に記載の方法。

請求項12

前記圧縮状態遷移レジスタ(31)から状態(15)に対する各状態遷移を除去する工程をさらに有し、対応する状態遷移は、結果として受入状態(14)になることはできないことを特徴とする請求項9又は10に記載の方法。

請求項13

前記圧縮状態遷移レジスタ(31)から状態(15)に対する各状態遷移を除去する工程をさらに有し、前記初期状態(14)は最終状態(14)であることを特徴とする請求項9又は10に記載の方法。

請求項14

データ記憶デバイスに格納されたコンピュータプログラムコードデータが電子的処理ユニットメモリにロードされ、前記電子的処理ユニットにより実行されるとき、請求項8乃至13のいずれか1項に記載の方法を実行するように構成された前記コンピュータプログラムコードデータを有するコンピュータプログラム

請求項15

請求項7に記載のネットワークサーバ(42、43、44、45、46)を有することを特徴とする通信ネットワーク(40)。

技術分野

0001

本発明はデータ処理に関し、特に、決定性有限オートマトンを用いてデータストリームにおけるデータパターン検出のための装置及びコンピュータにより制御される方法に関する。

背景技術

0002

通信ネットワークにより送信されるデータ量は急速に増加している。高速大容量パケットデータネットワークサーバとが採用されて、これらのデータを転送している。なかんずく試験監視を行う目的で、所望の、あるいは、合意したサービス品質QoSを保証するために、例えば、発信元アドレス宛先アドレスについてのパケットヘッダ情報だけでは要求された情報を取得するためには不十分である。ある場合には、データパケットペイロードが、例えば、特定のデータパターンに関して検査される必要がある。データマイニング、データウィルスの検出や他の悪意のあるデータは、パケットデータの検査を必要とする別の例である。

0003

パケットを検査する方法は、有限オートマトンを採用することによるものである。有限オートマトン、あるいは、単純にステートマシンは、状態遷移テーブルまたは状態遷移レジスタに従って複数の状態で動作するアブストラクトステートマシンとして採用されるコンピュータにより制御される方法である。そのような状態遷移テーブルは、--有限オートマトンの複数の状態に関し−、現在の状態において特定のデータシンボルを入力するとき現在の初期状態から次の目標状態への遷移を有し、実際には入力データシンボルの特定の文字列のデータパターンの一致へと導くものとなる。そのようなデータシンボルは、例えば、公知のコンピュータ用アルファベット情報交換のための米国標準コード、略してASCIIのようなアルファベットに含まれるデータシンボルである。そのようなものとして、後続の目標状態への状態遷移は、非転送遷移(non-forwarding transition)と呼ばれるオートマトンの同じ状態への遷移にも関与するかもしれない。そのような場合、その状態遷移は、初期状態が目標状態に等しい遷移であり、例えば、同じ状態への非転送ループである。

0004

一般に、2つのタイプの有限オートマトンは、決定性有限オートマトン(DFA)と非決定性有限オートマトン(NFA)に区別される。DFAは、一定量のメモリアクセスだけを必要とする一方、パケットペイロード解析するので、処理速度では好ましい。そのような計算効率のコストは、状態の数と状態遷移の数とが指数関数的にメモリ要件を増大させるので、メモリ格納量が大きいことである。NFAはメモリ格納量の要件は少ないが、各状態からの次の状態は並行的に多数のものがあり得るので、可能性のある全ての場合をチェックするために多くの計算資源を必要とする。

0005

DFAとNFAとは両方とも長所と短所とがあり、データパケット検査システムに対するソフトウェアツールにおいて採用される。

0006

通信ネットワークにより送信されるデータ量が急速に増大しているので、有限オートマトンを使用するネットワークサーバ余りにも多くの資源、即ち、メモリ格納量、一般にはメモリ容量として示されるメモリアクセスコントローラとを必要とする。従って、有限オートマトンを実行することによりデータパターンを検出するための改善された方法が必要である。

0007

本発明の目的は、データストリームにおけるデータパターンを検出する改善された装置と方法を提供することにある。

0008

本発明の目的は、特に、高速データストリームにおいて決定性有限オートマトンを実行するように構成されたデータパターンを検出する装置とコンピュータにより制御される方法を提供することにある。

0009

第1の側面からすれば、それは、アルファベットの文字を表現する複数のデータシンボルを有するデータストリームにおけるデータパターンを検出する装置である。その装置は決定性有限オートマトンを実行し、次の構成を有する。状態遷移レジスタは、開始状態と少なくとも1つの受入状態とを含む複数の状態と、前記データストリームのデータシンボルによりトリガされる初期状態から目標状態への状態遷移とを有する。その装置はさらに、 前記状態遷移レジスタの各状態の各データシンボルに関し、前記アルファベットにおける対応する文字位置を決定する文字位置決定手段と、同じ目標状態への遷移にトリガをかける、前記アルファベットにおける対応する後続の文字位置をもつデータシンボルに関するデータシンボル範囲を含ませるように前記状態遷移レジスタを更新する更新手段とを有する。その装置はさらに、前記データストリームのデータシンボルが前記更新された状態遷移レジスタのデータシンボル範囲に含まれるかどうかを判断し、前記更新された状態遷移レジスタの前記対応する目標状態を決定する範囲決定手段と、前記データパターンを検出するために前記初期状態から前記決定された目標状態への状態遷移にトリガをかけるトリガ手段とを有する。

0010

複数のデータパターンを検出するための装置でデータストリームを処理することに関し、その装置はデータストリームに含まれるデータシンボルと状態遷移テーブルに格納されたデータシンボルとを比較するように構成される。始めに、有限オートマトンは第1の状態、即ち、開始状態にあり、その開始状態に関し、そして、有限オートマトンの更なる各状態に関し、状態遷移テーブルは状態遷移についての情報を有する。このことは、各状態に関し、目標状態とそれに対応するデータシンボルとの組み合わせが、そのレジスタに含まれることを意味する。データストリームのデータシンボルは処理され、例えば、解析され、そして、その時点で状態遷移レジスタに格納されているデータシンボルと比較される。そのレジスタ一致するデータシンボルは対応する目標状態を有し、そして、そのようなものとして、その目標状態への遷移にトリガがかけられる。それから、その処理が繰り返され、データストリームの次のデータシンボルが処理され、例えば、状態遷移レジスタと比較される。

0011

そのデータストリームのデータシンボルが拡張ASCIIのアルファベットのようなコンピュータ用のアルファベットに含まれているなら、各データシンボルは、256個の異なる文字の1つである。そのようなものとして、メモリに格納された状態遷移テーブルは、有限オートマトンの各状態に関し、これら256文字全てに関する目標状態を含む。例えば、相対的に短い単純な5文字のACSII文字列を検出する状態遷移レジスタは、5×256=1280個の状態遷移についての情報を保持する。従って、だれでもは広大な文字列や多数の文字列を検出するためには、メモリ要求が急速に増大することを想像できる。

0012

本発明を1つの側面から見れば、メモリ資源の要件が小さい状態遷移レジスタに情報を格納する代替的な方法が見いだされる。状態遷移レジスタに格納される状態遷移はしばしば、同じ目標状態に対して複数の遷移を含む。そのようなものとして、そのレジスタに格納される情報の少なくとも一部は圧縮されやすい。

0013

データストリームのデータシンボルと、そのようなものとして状態遷移レジスタに格納されたデータシンボルは、例えば、(拡張)ASCIIのアルファベットの文字として表現される。そのアルファベットの中で、各文字は後続の番号をもつ。例えば、データシンボル“A”は65番目ASCII文字コードの表現であり、データシンボル“B”は66番目のASCII文字コードの表現である。発明者は、ほとんどの場合、文字の可能性よりも小さい目標状態があるので、複数の単一データシンボルの表現としてデータシンボルの範囲の利用がなされるなら、状態遷移テーブルにおけるデータシンボルの格納が圧縮できるという内を利用した。そのようなものとして、同じ対応する目標状態をもつアルファベットにおいては、後続の文字位置をもつデータシンボルがグループ化されて単一表現となる。

0014

複数の文字はアルファベット内で固定された後続の位置をもつので、文字の範囲はグループ化され同じ目標状態にトリガをかけることができる。

0015

本発明の第1の側面に従う装置は、状態遷移レジスタに含まれる全てのデータシンボルの文字位置を決定する手段を有する。その状態遷移レジスタの状態に関し、全ての記録がチェックされ、データシンボルのどのシリーズが同じ対応する目標状態をもつ後続する文字位置を参照しているのかを決定する。例えば、もし状態1のデータシンボル“A”、“B”、“C”、“D”、“E”が目標状態2への遷移にトリガをかけるなら、これらのシンボルはグループ化され、より小さいメモリ容量で表現される。データシンボルは文字位置65から69までを表現し、例えば、単一のデータシンボル範囲はそこに含まれる全てのシンボルに対して指示することができる。状態遷移レジスタは、より少ない、強力なメモリ参照で更新され、そのようにして、メモリ資源の削減がその装置により達成される。

0016

圧縮された、例えば、更新された状態遷移テーブルを実行する際、その装置は、データストリームのデータシンボルが更新された状態遷移レジスタのデータシンボル範囲に含まれているかどうかを決定する手段を有し、その後にそのレジスタの対応する目標状態を判断する。トリガをかける手段を用いることで、その装置は、目標状態に従った有限オートマトンを実行し、その目標状態への遷移にトリガをかける。そのようなものとして、有限オートマトンは実行され、データストリームにおいて状態遷移レジスタに従ってデータパターンを検出する。

0017

更なる例では、前記決定する手段は、状態遷移レジスタの各状態に関し、アルファベットにおける対応する文字位置に従って全てのデータシンボルをソートするよう構成されている。

0018

データシンボルがアルファベットの文字として表現されるので、それらはアルファベットの中に定義された文字位置をもつ。状態遷移レジスタを更新してデータシンボルの範囲を後続する文字位置をもつデータシンボルに対する表現として含めるためには、アルファベットの中でそれらの相対位置に従ってデータシンボルをまずソートすることには利点がある。複数の状態遷移、即ち、対応する目標状態を備える複数のデータシンボルのセットがその文字位置又はアルファベットに従う文字コード表現に従ってソートされるなら、その装置はどの状態遷移がグループ化されるのかをより簡単に決定することができるので、このことは処理を増やすものとなる。

0019

別の例では、アルファベットはコンピュータ用のアルファベット、特に、ASCII又は拡張ASCIIのアルファベットを含む。

0020

アルファベットは、装置により処理されるどんなアルファベットでも良い。即ち、コンピュータはデータパターンを検出するコンピュータに実装された方法を実行する。とりわけ、そのアルファベットは人間により解読可能などんなアルファベットでも良く、例えば、ラテン語のアルファベットやギリシャ語のアルファベットでも良い。人間が解読可能なアルファベットの中で、データシンボル、例えば、文字はしばしば、照合の方法としてアルファベット順としても知られている、シンボルの標準的な順序に従って関係づけられる。

0021

アルファベットはまた、コンピュータ又は数学的なアルファベットでも良く、これは文字が文字符号化に従って、即ち、ASCIIの順序、又は、辞書編纂的な順序に従って順序づけられることを意味する。例えば、文字符号化ASCIIと拡張ASCIIはしばしば通信ネットワークで用いられている。より現代的な符号化のタイプ、例えば、ISO/IEC10646ユニバーサル文字セットとUnicode、又は、より具体的に言えば、ISO/IEC 8859−1〜16、又は、UTF−8、又は、UTF−16に従う符号化が用いられても良い。

0022

更なる例では、そのデータシンボルはASCIIアルファベット、特に、拡張ASCIIアルファベットの文字を表現する。ここで、その文字位置は、ASCII文字の2進法8進法10進法、又は16進法のコードで表現する。アルファベットの符号化に従って、例えば、アルファベットの順番に従って、2進8進10進、又は16進コード表現の夫々が利用される。

0023

別の例では、その装置は、文字位置の決定と、データシンボル範囲におけるデータシンボルの決定に係らず状態遷移テーブルの更新と、状態遷移のトリガとを実行するように構成される。

0024

第1の例では、その装置は、どの有限オートマトンが実行されるのかに従う状態遷移を有する状態遷移レジスタを読取るよう構成される。その状態遷移テーブルはメモリ容量を少なくするために範囲が定められたデータシンボルを含めるよう更新される。さらに、その装置は、更新/圧縮される状態遷移レジスタに従って有限オートマトンを実行する。その有限オートマトンの出力結果、例えば、データパターンが一致するかどうかは、もし初期の状態遷移レジスタに従って実行されるなら、更新される状態遷移テーブルに従って実行されるときと同じである。

0025

一旦更新されたなら、状態遷移テーブルは更なる有限オートマトンの実行において再利用される。従って、前記装置又はいずれの装置も状態遷移レジスタを更新してデータシンボル範囲を含むように構成され、そして、異なるタイミング、又は、異なる装置では、更新された状態遷移レジスタが用いられてデータパターンを検出できる。そのようなものとして、単一の装置に実装されるなら、その装置は、範囲が定められたデータシンボルを含む圧縮された状態遷移テーブルレジスタを用いて有限オートマトンを実行するとともに、範囲が定められたデータシンボルを含めるよう状態遷移レジスタを更新するよう構成される。もし、その装置が同じ状態遷移レジスタにより含まれる更なる有限オートマトンを実行するなら、それは、その更新ステップを実行する代わりに更新された状態遷移レジスタを再利用することができる。

0026

また更なる例では、その装置は、決定性有限オートマトンの受入状態への状態遷移がトリガされると、データパターンの検出を最終決定するよう構成される。

0027

有限オートマトン理論は、全てのデータシンボルが、検出されたパターンの一致があったかなかったかの結果が与えられる前に処理されることを規定している。このことは、たとえオートマトンがそれは決して受入状態となる結果にはなり得ない状態に達するとしても、データストリームの全ての入力データシンボルが処理される必要があることを意味している。このことは、オートマトンの解析速度に大きな影響を与える。

0028

いくつかの応用によれば、その装置は、標準オートマトン理論に従って動作するよう構成される。しかしながら、そのいくつかの正式の要件が緩和されるなら、状態遷移レジスタにおいて、より高圧縮が達成される。例えば、パケット検査の領域において、しばしば入力データシンボルストリームにおけるパターン一致の全ての事例をレポートする必要はない。最初の一致、即ち、受入状態である有限オートマトンにより達する第1の状態は、有限オートマトンを終了させ、その結果をレポートするには十分である。

0029

その結果、検出が最終決定され、即ち、有限オートマトンがその開始状態に戻るというリターン機能を実装することにより、更なる状態遷移が状態遷移レジスタから除去される。都合のよいことに、このことは更なる圧縮ができるという結果になり、そのようなものとして、更にメモリ容量を小さくすることができる。

0030

別の例では、データストリームがコンピュータにより検出されるデータパケットに従って処理される。この方法を実行するコンピュータは複数のサービス、例えば、ゲートウェイにおける設定においてトラフィックフィルタをかけるために用いられる。そのようなものとして、コンピュータはデータストリームにおける望まれないトラフィックを検出することができる。データストリームはコンピュータにより受信され、データパターンに従う一致がとられる。もし、パターンが一致するなら、そして、そのようなものとして、望まれないトラフィックが検出されるなら、コンピュータはそのデータストリームに更なる作用を実行させることができる。そのパターンに依存して、適切な動作が実行される。例えば、望まれないプロトコルウィルスについてのデータが一致したものは削除したり、経路変更できる。

0031

第2の例では、コンピュータにより受信されるアルファベットの文字を表現する複数のデータシンボルを有するデータストリームにおけるデータパターンを検出するコンピュータにより制御される方法であって、前記コンピュータが、開始状態と少なくとも1つの受入状態とを含む複数の状態と、前記データストリームのデータシンボルによりトリガされる初期状態から目標状態への状態遷移とを有する圧縮状態遷移レジスタを有する決定性有限オートマトンを実行し、前記圧縮状態遷移レジスタは少なくとも1つのデータシンボル範囲を含む方法であって、前記方法は、
前記コンピュータにより、前記圧縮状態遷移レジスタから、前記データストリームのデータシンボルが前記圧縮状態遷移レジスタのデータシンボル範囲に含まれるかどうかを判断し、前記圧縮状態遷移レジスタの対応する前記目標状態を決定する工程と、
前記コンピュータにより、前記データパターンを検出するために前記初期状態から前記決定された目標状態への状態遷移にトリガをかける工程とを有することを特徴とする方法が呈示される。

0032

上記工程に従う方法を用いれば、データパターンがその方法を実行するコンピュータにより受信されるデータストリームにおいて検出される。オートマトン理論に従えば、状態遷移レジスタがコンピュータに存在するが、本発明の一側面に従えば、そのレジスタは圧縮状態遷移レジスタであり、データシンボルの少なくとも1つのセットがデータシンボル範囲によって表現される。その方法は、その時点で処理されるデータストリームのデータシンボルに従ってオートマトンの次の目標状態を決定するためのルックアップ処理を実行する工程を有する。オートマトン理論に従えば、そのデータシンボルは状態遷移レジスタにおける一致するデータシンボルに対して比較される。対応する目標状態は、有限オートマトンがトリガされる状態である。

0033

しかしながら、第2の例によれば、オートマトン理論は決定する工程に従って実施され、入力データストリームのデータシンボルに対して、それがどのグループに属するのかが決定される。このことは、もしそれがデータシンボル範囲により表現されるなら、その対応する目標状態を決定することを意味する。もし、データシンボル範囲により表現されないなら、標準的なオートマトン理論に従って決定するのは目標状態である。それから、更なる工程では、目標状態への遷移がそれに応じてトリガされる。

0034

第3の例では、上記記載の圧縮状態遷移レジスタを生成するコンピュータにより制御される方法が呈示され、その方法は、
前記コンピュータにより、前記圧縮状態遷移レジスタの各状態の各データシンボルに関し、前記アルファベットにおける対応する文字位置を決定する工程と、
前記コンピュータにより、同じ目標状態への遷移にトリガをかける前記アルファベットにおいて対応する後続の文字位置をもつ複数のデータシンボルに関する複数のデータシンボル範囲を含ませるように前記圧縮状態遷移レジスタを更新する工程とを有する。

0035

一旦、状態遷移レジスタが更新されたなら、それは、データパターンを検出するために有限オートマトンを実行する元々の状態遷移レジスタに対する代替品として用いられる。そのようなものとして、前記方法の更新する工程は、更新されたレジスタを用いて有限オートマトンを実行する工程を実行する方法と同じコンピュータにより実行される。しかしながら、それらの工程は、異なるコンピュータにより別々に実行されても良い。例えば、第1のコンピュータは、状態遷移レジスタを圧縮する、即ち、ライブラリの単一の或いは複数の状態遷移レジスタをを解析するよう構成され、そして、第2のコンピュータはライブラリの単一の又は複数の更新/圧縮レジスタに従って有限オートマトンを実行するよう構成される。

0036

そのようなものとして、例えば、決定がアルファベットの順序であるように、アルファベットにおけるデータシンボルの文字位置を決定することと、そのアルファベットにおける対応する後続の文字位置をもつデータシンボルに対するシンボル範囲を含むように状態遷移レジスタを更新することと、同じ目標状態への遷移にトリガをかけることを含むコンピュータにより制御された方法は、有限オートマトンの実行に係りなく実行されるという利点がある。

0037

更なる例では、その方法は、コンピュータにより、状態遷移レジスタの各状態に関し、アルファベットにおける対応する文字位置に従って全てのデータシンボルをソートする工程を有する。

0038

そのデータストリームのデータシンボルは、アルファベットの文字形式で表現される。そのようなものとして、それらはアルファベットの中に特有の位置をもつ。データシンボル範囲を含むように状態遷移レジスタを更新することは、これらの位置に従って実行される。アルファベットにおけるその位置に従ってデータシンボルをソートすること、例えば、アルファベット順にすること、又は、アルファベットの順序で配置することは、レジスタの後続するデータシンボルの変化しない目標状態に関して、状態遷移のグループ、例えば、データシンボル範囲が形成されるので、レジスタの解析速度が速まると言う利点をもつ。

0039

更に別の例では、その方法はさらに、状態遷移テーブルから状態に関する各状態遷移を除去する工程を有し、全ての対応する状態遷移に対して、初期状態は目標状態に等しい。

0040

説明したように、非圧縮の状態遷移レジスタは、有限オートマトンの各状態に関し、データシンボルと対応する目標状態とを有する。本発明の一例に従う圧縮状態遷移レジスタもまた、少なくとも1つのデータシンボル範囲を有する。幾つかの状態に関し、各状態遷移はさらなる状態への遷移を含んではいない。このことは、有限オートマトンが廃線に入ってしまい、そのようなものとして、その状態に居続けるか、又は、各データシンボルにおいて非転送遷移としても知られる同じ状態への遷移にトリガをかけることを意味する。その状態遷移レジスタに含まれるこの情報はデータパターンの検出には何の貢献もしないのであるから、そのような情報を除去することには利点がある。そのようなものとして、全ての更なる状態遷移が、有限オートマトンが異なる状態への遷移にトリガをかけることのできないレジスタから除去され、そのような場合には、目標状態は初期である。

0041

別の例では、その方法はさらに、状態遷移テーブルから状態についての各状態遷移を除去する工程を有し、その場合にはどんな対応する状態遷移も受入状態にはなれない。

0042

転送状態に関する状態遷移を除去することに加えて、これらの状態に続く状態もまた状態遷移テーブルから除去される。さらに、それらの状態遷移もまた除去され、その場合には、有限オートマトンのトラックの後続する状態においてどんなものも受入状態を有することはない。このことは、データパターンを検出する例において、有限オートマトンが特有の状態に入り、その状態からは、全ての直接的な目標状態に関し、現在の状態がソース状態であり、その全ての更なる目標状態に関し、どの状態も受入状態ではない。従って、データパターンにおいて一致する機会はなく、そこで、対応する情報、即ち、その状態にあるデータシンボルと目標状態とを、状態遷移レジスタから除去し、更なる圧縮を達成することには利点がある。

0043

更なる例では、その方法は状態遷移テーブルから各状態遷移を除去する工程をさらに有し、初期状態は最終状態である。幾つかの応用に関しては、有限オートマトンの最初のヒットで十分である。例えば、最初の受入状態に入ったときデータパターンにおける一致が呈示される。そのような応用では、状態遷移レジスタは、その応用では検出されたパターンについて必要な情報を付加することはないので、さらにそのレジスタの全ての後続する状態遷移を除去することによってさえも構成される。

0044

第4の例では、コンピュータプログラムコードデータが電子的処理ユニットのメモリにロードされ、前記電子的処理ユニットにより実行されるとき、上述した特徴のいずれかに従う方法を実行するように構成された前記コンピュータプログラムコードデータを格納するデータ記憶デバイスに格納されるコンピュータプログラムが呈示される。

0045

第5の例では、上述の例に従うネットワークサーバを有する通信ネットワークが呈示される。

0046

次に、本発明について添付図面を参照しながら多数の代表的な実施例を用いて以下に詳細に説明する。

図面の簡単な説明

0047

5つの状態とその状態の間での状態遷移を含む単純化された有限オートマトンを示す図である。
さらに状態遷移レジスタを有する単純化された有限オートマトンを示す図である。
さらに範囲が定められた/圧縮された状態遷移レジスタを有する単純化された有限オートマトン示す図である。
本発明の側面に従うフローチャートである。
本発明の更なる側面に従うネットワークサーバを示す図である。
本発明の別の側面に従う通信ネットワークを示す図である。

実施例

0048

図1では、有限オートマトン10の表現の例が開示される。有限オートマトンはデータストリーム、即ち、通信ネットワークにおけるデータトラフィックにおけるデータパターンを識別するために用いられる。そのような識別は、例えば、ウィルス又はスパイウェア検出、侵入検出システムコンテンツフィルタリング、プロトコルマッチングなどにおいて適用される。

0049

図1に示される有限オートマトン10は、複数の状態11、12、13、14、15を有する。これらの状態はまた、ノードとしても言及される。データパターンマッチング処理は有限オートマトン10の開始状態11で開始する。開始状態はエントリ動作が存在しない状態、即ち、結果的にその状態に遷移することはないという状態として定義される。図1において、状態11はそのような開始状態である。

0050

コンピュータにより処理されるデータストリームは、データシンボルのシーケンスを有する。これらのデータシンボル又は文字はコンピュータにより受信され、一度に1回、有限オートマトン10の現在の状態への入力として用いられ、状態遷移16a、16b、16cにトリガをかける。パターンマッチング処理の開始時には、開始状態11は現在の状態又は初期状態である。データストリームの最初のデータシンボルは状態遷移16を決定する。例えば、最初のデータシンボルがASCIIテーブルの文字“0”、即ち、文字コード“0”を参照するなら、開始状態である状態0(ゼロ)11から第1の状態15への状態遷移16cにトリガがかけられる。しかしながら、第1のデータシンボルが文字(コード)1を参照するなら、第2の状態12への状態遷移16bにトリガがかけられる。第1の状態遷移16b、16cの後、その遷移にトリガがかけられる状態、即ち、状態12又は15がその時点での現在の状態である。

0051

そのとき、再び現在の状態、即ち、状態12に関し、データストリームの次のデータシンボルが次の状態遷移を決定するために用いられる。もし、次のデータシンボルが文字コード“5”であれば、第1の状態15への状態遷移にトリガがかけられ、範囲0−7における全ての文字と範囲10−255における全ての文字に対して同じ事を考慮する。しかしながら、そのデータストリームにおける次のデータシンボルが文字の8又は9であるなら、第3の状態13への状態遷移にトリガがかけられる。それから、第3のデータシンボルに関し、文字0−2、5−255の全てについては第1の状態への状態遷移にトリガがかけられる。しかしながら、もし第3のデータシンボルが文字3又は4であれば、第4の状態14に入る。これは受入状態又は最終状態であり、二重丸により表現されている。

0052

受入状態に到達したなら、有限オートマトンが有限オートマトンに従ってデータパターンについての一致を与える。この例では、これは正規の表現では{[1−5],[8−9],[3−4]}での一致であり、それは最初のデータシンボルに対して文字1−5のいずれか、それから、第2のデータシンボルに対して文字8又は9、最後に第3のデータシンボルに対して文字3又は4である。

0053

複数の有限オートマトンが存在し、複数のプロトコル、データ文字列、ウィルスなどを判断するための複数のデータパターンを生じさせることができる。図1に開示された有限オートマトンは、図示された一定量の遷移と状態だけが存在するので、有限オートマトンの簡略版である。実際には、完全な有限オートマトンは、可能性のある入力データシンボル全てに対しての状態遷移を表示する。それゆえに、ACCII文字のアルファベットの256個の可能性があるデータシンボルに対して、有限オートマトンの全ての状態は、256個の状態遷移をもつ。しかしながら、たいていの状態遷移は同じ後続の状態への遷移にトリガをかけ、それゆえに、単一の範囲として視覚的に表示される。図1の例では、状態0(ゼロ)11から第1の状態15への状態遷移は2つの状態遷移からなり、1つは文字0に対する単一の状態遷移と、6から255の範囲における全ての文字に対する範囲の定められた状態遷移である。

0054

図1に表示されたグラフは、状態図の形式での有限オートマトンであるが、それは表示の例に過ぎない。別のタイプの表示が存在する。従来技術による有限オートマトンがもっと形式的な方法でコンピュータに格納される、図1に表示される状態図は、各状態に対する限定された量だけの状態遷移を表示する。コンピュータに格納された有限オートマトンの実施形である従来技術による状態遷移テーブルは、各状態に対する可能性のある全ての状態遷移に対する記録を保持する。状態図をもつ、そのようなレジスタを表示することが不明確なので、その状態図は状態遷移レジスタの簡略化された表現形式となる。しかしながら、状態遷移レジスタは図1に示された可視化された表現によるのと同じ正規の表現形式を含ませるためのより形式的で機能的な方法である。状態遷移レジスタは、一定の入力がある際の状態に対する出力を定義する真偽表のようなものである。

0055

有限オートマトンを実装するコンピュータにより処理されているデータストリームのデータシンボルは文字として表現される。これらの文字は、“1”、“a”、“β”のような知られた文字であって良いが、それらはまた、“>”、“−”、“「”のようなコンピュータ用の文字でも良い。これらの文字は、標準的な固定のデータシンボルのセットを含むアルファベットの一部を構成する。複数のアルファベット、例えば、アラビア語、シリア語、キリル語、ヘブライ語、ラテン語のアルファベットのような、よく知られた人間が識別可能である自然のアルファベットが存在する。しかしながら、コンピュータ用のアルファベットもそのようなアルファベットと考えられ、それらには、数字、一般的な句読点、特定の自然の言語における記号に対応しない制御文字を含むより多くの文字を含んでいる。

0056

そのようなものとして、本発明によれば、アルファベットとは最も広い意味でのシンボルの集合であると考えられる。コンピュータシステムでは、アルファベットは、複数の文字の順序と文字情報の単位とのうちの少なくともいずれかにより文字要素を表現することにより符号化される。その文字は次に、コンピュータ内部で2進数で表現される。文字をバイナリデータに変換するシステムは、文字セット符号化、文字符号化、又は、文字符号化方式である。

0057

情報交換のための米国標準コード(ASCII)は標準的な文字符号化の例であり、文字、数字、句読点などが表現される。各文字、即ち、各データシンボルはそれが示されることによってユニークな番号をもつ。そのようなものとして、各データシンボルは、このコード方式の内部に、所定の固定位置をもつ。ASCIIは単に文字符号化方式の例に過ぎず、拡張ASCII、ユニコード変換フォーマット(UTF)のような他の符号化方式もまた、そのアルファベット内でのデータシンボルに対する文字位置、例えば、符号方式が知られている限り、固定のユニークな番号表現に従ってデータシンボル指示のために用いられる。

0058

図1によれば、データシンボルの256個の異なるコード表現、例えば、0−255がある。符号化方式に依存して、それらは異なる文字を表現できる。例えば、ASCII符号方式が用いられるなら、10進コードで97は文字“a”を表現する。そのようなものとして、有限オートマトンを実行するコンピュータがデータストリームを処理し、その入力データストリームにおける現在のデータシンボルとして文字“a”を読み取るなら、その10進表現は97、例えば、ASCII符号化方式によれば、そのアルファベット内の97番目の位置となる。可能性のある全てのデータシンボルはその符号化方式の内で、そして、そのようなものとしてのアルファベット内のユニークな位置を表現し、その方式に従ってソートされる。

0059

図2では、図1の状態図10が開示されているが、そこでは対応する状態遷移テーブル17も付与されている。その状態遷移テーブルは、あるデータシンボルを現在の初期状態に入力する際にどんな状態遷移がトリガされることになるのかについての情報を格納するのと類似の真偽表と考えられる。この図に開示された単純化された状態遷移テーブル17は2つの行17a、17bを有する。第1行17aはアルファベットの全てのデータシンボル、例えば、その10進数表記により表現される拡張ASCIIテーブルに含まれる256個のデータシンボルの有限なセットを含む。それから、第2行17bにおけて、全てのデータシンボルに関し、対応する状態が呈示される。これは、もし対応するデータシンボルがデータストリームのデータシンボルであるなら、状態遷移にトリガがかけられる状態である。そのようなものとして、各状態に関し、そのような情報が状態遷移テーブルに含まれる。

0060

複数の状態遷移テーブル、例えば、一次元状態テーブル、二次元状態テーブルが存在する。その状態遷移テーブルは状態遷移レジスタの形式で有限オートマトンを実行するコンピュータのメモリに含まれる。そのようなものとして、本発明に従う状態遷移テーブルは、例えば、図2に開示された状態遷移テーブル17として定義される。

0061

状態遷移レジスタは、処理されるデータストリームの可能性のある各状態とデータシンボルに関して状態遷移を保持するので、単純な正規の表現方法でもかなり大きな記憶容量を必要とする。ある応用では、大容量の正規の表現がそのようなものとして処理される必要があり、有限オートマトンに対するメモリ容量(状態遷移レジスタ)は大きい。そのメモリ容量を少なくし、メモリ量に制限のない有限オートマトンを処理できるために、状態遷移レジスタの圧縮は有利である。

0062

図1図2の有限オートマトンを呈示するために用いられる目に見える工夫はまた、本当の状態遷移レジスタを圧縮するためにも適合される。単一の文字コードのための状態遷移として呈示される状態遷移と文字コードの範囲に対する状態遷移との間には区別がつけられる。例えば、図1図2とにおける状態遷移16cは単一での状態遷移である。図1図2の状態遷移16aと16bは、250個の異なる文字(16a)と5個の異なる文字(16b)とをそれぞれに表現する範囲の定められた状態遷移である。

0063

本発明の第1の側面からすれば、単一での遷移とグループ化された又は範囲が定められた遷移との間のそのような区別が実施される。範囲の定められた状態遷移の各表現に関し、データ格納量の削減と、そのようなメモリ容量削減が得られる。決定性有限オートマトンについて範囲の定められた状態遷移を実装することは、標準的なオートマトン理論とは少し異なっている。なぜなら、標準的なオートマトン理論は全ての単一での遷移についての格納量を規定するものであるからである。

0064

範囲の定められた状態遷移は同じ目標状態へと向かう状態遷移をユニークな範囲の定められた遷移として表現する。複数の状態遷移を状態遷移レジスタ内の範囲の定められた状態遷移へと変換することについて、既に計算された決定性有限オートマトンが用いられる。そこでは、決定性有限オートマトンの全ての状態が反復される。各状態に関し、入力アルファベットに存在する全てのデータシンボルに関してユニークな位置を配列アレイに備える。アルファベットにおける各データシンボルについて、そのアルファベットの後続するデータシンボル、即ち、文字コードテーブルに従う次の文字が、決定性有限オートマトンの同じ目標状態に向かうなら、範囲の定められた遷移が作成される。それから、個々の状態の代わりに範囲の定められた状態だけがそのレジスタに格納され、それを用いるとサイズ削減が得られ、その結果、メモリ容量をより小さくする。

0065

圧縮状態遷移レジスタを用いることは、オートマトン理論の公式な実施形に従う状態遷移レジスタと比較して、多少異なる。圧縮状態遷移レジスタの使用によれば、その第1のステップは、入力データストリームのデータシンボルが、そのレジスタ内の範囲の定められた遷移又は単一での遷移の内に含まれるかどうかを判断することである。圧縮状態遷移レジスタ内で、コンピュータはそのデータシンボル、即ち、その文字コードが単一での文字遷移の代わりに、ある範囲に属しているかどうかを判断する。

0066

その範囲は複数の方法で決定できる。例えば、各範囲は初期の文字コード表現、即ち、コード41と最終の文字コード表現、即ち、コード48とを有し、これにより表現された文字コードの範囲を記述できる。コンピュータは入力データシンボルが状態遷移レジスタ17内のデータがシンボル17aを順番に解析することにより、その範囲に含まれているかどうかを判断できる。もし、現在の文字コードと過去の処理された文字コードとが非連続的であり、入力データシンボルがそこに含まれているなら、ヒットが発生し、対応する状態17bが初期化のために読み出され、例えば、そこへの遷移にトリガをかける。さらに、その範囲はまた、開始文字コード表現の定義のみによっても判断できる。後続する文字コードから、単一のデータシンボル又は範囲が状態遷移テーブルに格納されているのかどうかが判断される。

0067

図3は、そのような圧縮された、例えば、範囲が定められた、状態遷移テーブルを示しており、対応する状態図10に関し、アルファベット内の連続する文字コード位置によりトリガがかけられるある状態から同じ目標状態への状態遷移が範囲18x,18yとして表現されている。

0068

初期のゼロ(0)状態11に関し、可能性のある256個のデータシンボル、即ち、ACSII文字コードの10進表記に従って、256個の状態遷移が可能である。その図から、これら256個の遷移は、目標状態“1”15又は目標状態“2”12への遷移だけになるという結果になることは明らかである。そのようなものとして、全てのデータシンボルがこれらの状態に従ってグループ化される。しかしながら、どのデータシンボルがどのグループに属するのかを決定するために、レジスタ全体が繰り返し解析される必要がある。アルファベット内の相対位置に従って、レジスタにおけるデータシンボルをソートすることにより、そのような反復的な解析はスキップされる。レジスタ18のデータシンボル18aが順番に解析され、遷移がトリガされることになる状態の直接アドレスを与える。

0069

図4には、圧縮状態遷移レジスタ、即ち、同じ目標状態への遷移にトリガをかける後続のデータシンボルについての範囲の定められた状態遷移を含めるために更新される状態遷移レジスタを用いる方法のステップが説明されている。そこで、最初のステップ21では、更新された又は圧縮された状態レジスタから、入力データストリームのデータシンボルがそのレジスタのデータシンボル範囲に含まれるかどうかを判断する。

0070

第2のステップ22では、コンピュータは有限オートマトンが遷移のトリガをかける対応する目標状態を決定する。この目標状態は前のステップ21において決定されたデータシンボル又はデータシンボル範囲に対応している。

0071

最後のステップ23では、有限オートマトンが、ステップ22において決定された目標状態への遷移にトリガをかける。そのようなものとして、コンピュータはデータストリームのデータシンボルを処理し、そのストリームでの次のデータシンボルについての処理を続け、再び方法のステップ21〜23を開始する。

0072

図5は本発明に従うコンピュータにより制御される方法を実行するコンピュータ30の簡略的な図である。そのコンピュータは、図5には開示されておらずコンピュータ、又は、特にネットワークサーバや通常の動作のための通信ネットワークにおけるノードには存在する中央処理ユニットのような更なるユニットを含む。

0073

コンピュータ30は状態遷移レジスタ31を含み、そこには有限オートマトンの全ての状態に関する状態遷移が格納される。コンピュータはリンク37により通信ネットワーク36に接続される。通信ネットワーク36はどんなネットワークでも良く、そこではデータがパーティ間、ノード間、或いは、その組み合わせたものの間で送信される。ネットワーク36内では、特に、ネットワーク接続37により、データストリームが転送される。これらのデータストリームは有限オートマトンを実行するコンピュータ30により処理される。そのコンピュータには文字位置決定手段32が備えられる。それを用いてデータストリーム37のデータシンボルが処理され解析される。各データシンボルは文字により表現され、その文字は文字符号化方式に従ってアルファベット内の文字コードを表現する。データストリームについてある瞬間に処理されたデータシンボルは、例えば、文字“a”であるかもしれない。コンピュータ30は、特に、文字位置決定手段32は、どの文字コード方式が用いられるのか、例えば、どんなアルファベットを適用するのかを判断する。もし、例えば、ASCII文字符号化方式が用いられるなら、文字位置決定手段32はデータストリーム37のデータシンボルをASCIIコードテーブルと比較し、その位置を決定する。即ち、文字“a”に対しては10進位置97と決定する。

0074

コンピュータ30の更新手段33は状態遷移テーブルを読み出し、そして、文字位置決定手段32の符号化方式に従って、そのレジスタに含まれるデータシンボルの位置を決定する。符号化方式に従った後続の位置をもつデータシンボルに関し、即ち、“a”−“e”はそのASCIIコードが97−101であり、そして、対応する目標状態が同じであるものについては、更新手段33は単一のデータシンボルの代わりにコードの範囲を含ませるように状態遷移レジスタ31を更新するよう構成される。オリジナルのデータシンボルがレジスタからは除去され、これにより、そこに格納される情報量を削減し、そのようにしてメモリ容量を小さくする。

0075

範囲決定手段34は、有限オートマトンの実行時、データストリーム37のデータシンボルが状態遷移レジスタの範囲内に含まれているかどうかを決定するよう構成される。もし、その状態遷移レジスタが単一のデータシンボルだけを含むなら、コンピュータはただそのデータシンボルを順々に解析し、それらを入力データストリームと比較する。範囲決定手段34はトリガ手段35にどの対応する目標状態への遷移がトリガされるべきであるのかを通知する。そのとき、トリガ手段はこの遷移を実行する。そのとき、コンピュータ30はデータストリームの次のデータシンボルを処理するよう続行できる。

0076

図5に示されたコンピュータ30はいくつかのユニットを有している。これらのユニット各々は自分自身のユニークなタスクをもっている。しかしながら、1つの側面からすれば、コンピュータ30はこれらユニット32、33、34、35のわずかだけを有することもできる。例えば、範囲の定められた遷移を有する更新状態遷移レジスタへと状態遷移レジスタ31を更新するユニット32と33だけを有することできる。コンピュータ30はまた、従来の状態遷移レジスタを圧縮されたレジスタに更新することなく、有限オートマトンを圧縮状態遷移レジスタを用いて実行するユーザ34と35を有することもできる。

0077

図6は通信ネットワーク40における複数のネットワークサーバ又はノード42、43、44、47、48を示している。各ネットワークサーバはそのネットワーク内において一定のタスクを実行することができるように具体的に構成されている。その例は、ゲートウェイ汎用パケット無線サービス(GPRS)サポートノード(GGSN)であり、図には参照番号42で示されている。GGSNはインターネット41のような外部ネットワークGPRSネットワークのデータストリームを接続したりルーティングすることを担当するゲートウェイである。GGSNはゲートウェイとしてのその機能において、データストリームを通過させる。そのデータストリームに含まれるデータパケットに関し、GGSNは、少なくともその宛先に気づいているが、ほとんどの場合、そのパケットに含まれる実際のペイロードには注意を払わない。

0078

ペイロード依存の処理を実行することについて、GGSNのようなネットワークサーバには図5に図示されたコンピュータ30に従うユニットが装備されている。そのようなものとして、状態遷移レジスタを含むように構成されるなら、ネットワークサーバは削減されたメモリ容量で有限オートマトンを実行するよう構成される。

0079

図6はさらに、あるエリア内で複数の移動局との間でデータパケットを配信するよう構成されたサーバGPRSサポートノード(SGSN)43、一定量のデジタル加入者ラインのデータを寄せ集めるデジタル加入者ラインアクセスマルチプレクサ(DSLAM)48、それらのデータを単一のネットワークリンクによりトランスポートするためのDSLモデム無線基地局(RBS)43、又は、ブロードバンドリモートアクセスサーバ(BRAS)47のような他のネットワークサーバを示している。複数の端末45、46、50の間での通信を可能にするこれらサーバ各々は少なくとも図5に示したユニットを有することにより本発明の一側面に従った方法を実行するように構成されている。しかしながら、図6に示されたネットワークサーバはただ例示としてのみ示されている。本発明の一側面に従う方法がこの図に示されたネットワークサーバに限定されるものではく、複数のネットワークサーバにおいて実行されても良い。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

  • 三菱電機株式会社の「 情報処理装置および情報処理方法」が 公開されました。( 2019/08/08)

    【課題・解決手段】情報処理装置(10)は、時系列データである入力データを取得するデータ取得部(101)と、時系列データである学習データから抽出した部分列である複数の学習部分列の中で類似する学習部分列を... 詳細

  • オムロン株式会社の「 センシングデバイス管理装置」が 公開されました。( 2019/08/08)

    【課題・解決手段】センサ側メタデータに相当するデータカタログの生成が簡単且つ適正に行えるセンシングデバイス管理装置を提供する。デバイス情報取得機能部11dが、測定対象をセンシングするセンシングデバイス... 詳細

  • オムロン株式会社の「 マッチング処理装置」が 公開されました。( 2019/08/08)

    【課題・解決手段】利活用対象のセンシングデータによる容易なセンサマッチングを行うマッチング処理部50が提供される。マッチング処理部50は、提供側端末11により入力された提供側センシングデータを取得する... 詳細

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

関連性が強い 技術一覧

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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