単一の連からなるRBTのリストによるパケット分類法
8
0
0
全文
(2) Vol.2018-AL-167 No.3 2018/3/8. 情報処理学会研究報告 IPSJ SIG Technical Report. 表 1. ビットマスクルール. 表 2 単一の連からなるルール. Filter R. 要である．任意の位置にビットマスクを含むビットマスク ルールで構成されたルールリストの例を表 1 に示す．我々 の手法は，連とよばれるルール中で 0, 1 が連続する部分に. Filter R. r1. 0∗1∗. r1. 01∗∗. 注目する．. r2. 0000. r2. 0000. 定義 2.1 r ∈ {0, 1, ∗}w を長さ w のビットマスクルー. r3. ∗00∗. r3. ∗00∗. ∗1∗0. r4. ∗∗10. ル と す る ．下 記 の 二 つ の 条 件 を 満 た す r の 部 分 列. r4 r5. 1∗1∗. r5. 11∗∗. r6. ∗∗1∗. r6. ∗1∗∗. ri ri+1 . . . rj (1 ≤ i ≤ j ≤ w) を r の連と呼ぶ． • rk = 0 ∨ rk = 1. (i ≤ k ≤ j). • (i ≥ 2 ⇒ ri−1 = ∗) ∧ (j ≤ w − 1 ⇒ rj+1 = ∗) 例えば，長さ 16 のビットマスクルール. とを確かめられないので，ルールリストに一旦追加された. ∗101∗∗001∗1∗∗010. ルールは削除されない．これよりフィルタリングルールリ. は，2 番目，7 番目，11 番目，14 番目から始まる四つ. ストのルール数は増える一方なので，探索時間もそれに応. の連 101, 001, 1, 010 を含む．ルール ri の k 個の連を. じて増大していく．よって今後増大するセキュリティルー. ri1 , ri2 , . . . , rik (1 ≤ k ≤ ⌈ w2 ⌉) と表す．我々の探索法の基本. ルに対応するためには，分類時間がルール数に依存しない. 的な考えは，パケットのビット列がルールリスト中のどの. フィルタリングアルゴリズムが不可欠である．. 連と合致するかを調べ，すべての連が合致するルールを調. このような状況に対して我々は，任意のビットマスク. べ，合致するルールの中で一番優先度の高いルールを返す，. ルールに適したデータ構造 RBT とこれを用いた探索法を. というものである．パケットのビット列がどの連と合致す. 提案し，分類時間がルール数に依存しない手法を提案し. るかを調べるために，ルールリスト中の連の開始位置毎に. た [1]．この手法 [1] に対しては，RBT から構成される決. w 個のトライを構成する．. 定木の領域計算量が O(n ) と膨大になるという問題点 [1]. 長さ w のルールを n 個含むルールリスト R =. と，RBT の探索には入力系列を余分に参照する問題点が. [r1 , r2 , . . . , rn ] から構成した w 個のトライを T1 , T2 , . . . , Tw. あった．そこで我々は，RBT から構成される決定木の領. とする．トライ Tk はルールリストに含まれる連の中で k. w. 域計算量を O(n ) から O(3 ) へと減少させる決定木の枝. ビット目から始まる連で構成される．この w 個のトライ. 刈り法 [5] と，ポインタと連を RBT に付与することにより. T1 , T2 , . . . , Tw の集まりを Run-Based Trie (RBT) という．. w. w. RBT 探索の探索時間計算量を O(w + nw) から O(nw) へ. 表 1 から構成した RBT を図 1 に示す．図 1 の破線は 0 枝. と減少させる手法を提案した [6]．. を実線は 1 枝を表す．. 2. けれども，枝刈り法を適用した決定木の空間計算量は. RBT は長さ w，ルール数 n のルールリストに含まれる連. O(3 ) と指数オーダで現実的ではなく，ポインタを付与し. から構成され，かつ RBT においてそれぞれの連は一カ所. た RBT を用いた探索法の時間計算量は O(nw) とルール数. にのみ出現するので，RBT の領域計算量は O(nw) である. w. n に依存している．そこで，与えられたルールリストの各 ルールが単一の連からなるルールならば，探索時間計算量 が O(w) とルール数 n に依存しない探索法を提案した [7]．. 2.1 Simple Search 我々が Simple Search と呼んでいる RBT の探索法は，T1 から Tw の順にトライ Ti を入力パケットのビット列で辿. この手法を単一の連からなる RBT 探索とよぶ． 本稿では初めに，単一の連からなる RBT の改善手法を提. り，入力パケットに合致する連を集めて合致するルールを. 案する．次に，単一の連からなる RBT 探索を複数の連か. 探し，合致したルールの中で最優先のルールを返す，という. らなるルールリストにも適用できるように，ルールリスト. 探索法である．探索に先立って各ルールの連の添字を格納. R を k 個の単一の連からなるルールリスト R1 , R2 , . . . , Rk. する配列 A[n] と最優先ルールを格納する変数 B を用意し，. へと分割する手法を示す．そして，R1 , R2 , . . . , Rk に対し. それぞれ A[i] := 0 (1 ≤ i ≤ n), B = n + 1 と初期化する．. て k 個の単一の連からなる RBT を含むリストを構築し，. そして，各トライ Ti (1 ≤ i ≤ w) を入力パケット p の i 番. このリストによるパケット分類法を提案する．また，計算. 目からのビット列 p[i]p[i + 1] . . . p[w] で辿る．各トライを. 機実験により提案手法の有効性を確かめる．. 辿るとき，トライの節点に連の印 ri が付いていたら，連の. j. 添字 j の値と配列 A[i] の値とを比較して，j = A[i − 1] + 1. 2. Run-Based Trie. ならば，A[i] := j とする．さらに，連の印に下線が引いて. 任意の位置にビットマスク’∗’ を含むビットマスクルー. あり i < B ならば，B := i とする．全てのトライを辿り終. ル r ∈ {0, 1, ∗} とパケットのビット列 p ∈ {0, 1} との照. えたときの B の値が，入力パケットに対する最優先のルー. 合を行う際には，ルールのビットマスク ∗ 部分は省略でき. ルとなる．. w. w. るので，ビットマスクルール r の ∗ 以外の 0, 1 の部分が重 ⓒ 2018 Information Processing Society of Japan. Simple Search の探索時間計算量を考える．各トライ. 2.
(3) Vol.2018-AL-167 No.3 2018/3/8. 情報処理学会研究報告 IPSJ SIG Technical Report. T1 r11. T2 r51 T3 r41 T4 r12 , r52 , r61. r31 r21. r42 図 1 表 1 のルールリストから構成される Run-Based Trie. T1 T2 r1. r6. r5. T3 T4. r3 r4. r2 図 2. 表 2 のルールリストから構成される RBT. T1 , T2 , . . . , Tw を探索するのに w + (w − 1) + · · · + 1 ステッ 2. 一つだけの連を持つ．二つの連 ri , rj (i < j) が同一の節点. プ必要なので，各トライ Ti の探索時間は O(w ) である．. にある場合は，連 rj が冗長なので削除できる．表 2 のルー. そして，ビット長 w のルールを n 個含むルールリストの. ルリストから構成される RBT を図 2 に示す．. 連の総数は高々 nw なので，合致した連と配列との比較に. Simple Search には入力パケット p の系列を何度も参照. 必要な時間計算量は O(nw) である．また，合致したルー. するという問題点がある．Simple Search は，トライ Tk を. ルと最優先ルールとの比較回数は高々ルール数分の n 回. 深さ d の節点まで探索しても，Tk を探索した後はトライ. なので，最優先ルールを見つけるのに必要な時間計算量. Tk+1 の根から探索を行う．けれども，トライ Tk を深さ. は O(n) である．よって，Simple Search の時間計算量は. d まで探索したということは，p[1] から p[k + d − 1] まで. 2. O(w + nw) となる．. 参照していることを意味するので，トライ Tk+1 での深さ. d − 1 までの探索は冗長である．この点に注目して，入力パ. 3. 単一の連からなる RBT. ケット p の系列を一度だけ参照する探索法を提案した [6]． 2. Simple Search の時間計算量が O(nw + w ) とルール数 n に依存してしまうのは，RBT の節点に連が高々. n⌈ w2 ⌉. 個，. 図 2 の RBT へ 0, 1 枝を新たに追加し，T2 の r3 を T1 へ加 えた RBT を図 3 に示す．この RBT の探索法は，Simple. 散らばって存在し，節点に連が存在する度に照合を行わな. Search と同様である．Simple Search が Tk の探索を終え. ければならないからである．. たあとに Tk+1 の根から探索を行うのに対して，0, 1 枝を. 本章では，ルールリスト中の各ルールが表 2 のように 一つの連だけからなる場合を考える．これより，Simple. Search でトライを探索していて連. rij. に合致したときに，. ルール ri に合致しているかを判定する必要がない．各ルー ルの連の数が一つだと連. rij. の j は 1 となり冗長なので，以. 追加した RBT の探索法は，T1 の根節点から 0, 1 枝を辿れ なくなるまで高々長さ w だけ探索する．. 0, 1 枝を追加した図 3 の RBT において，T1 の r1 に合致 した場合は，以降の探索において r1 よりも優先度の高い 連に合致する可能性がない．よって，r1 がある節点に対す. 降はルール ri の連から j を削除して ri と表す．また，各. る 0, 1 枝を削除して，この節点を終端節点とする．さらに，. ルールの連の数が一つだけであると，RBT の各節点は高々. T4 に rn+1 の連を持つ終端節点を追加して，任意の非終端. ⓒ 2018 Information Processing Society of Japan. 3.
(4) Vol.2018-AL-167 No.3 2018/3/8. 情報処理学会研究報告 IPSJ SIG Technical Report. T1 T2 r1. T3. r6. r5. T4 r3. r3. r2. r4 図 3 図 2 の RBT 全体に枝と T1 に r3 を追加. T1 T2 r1. T3. r6. r5. T4 r3. r3 r2. r4. r7. 図 4 図 3 の T4 に r7 と終端節点を追加，r1 を持つ節点から 0, 1 枝を削除. 節点が 0, 1 枝を持つようにした単一の連からなる RBT を. て，単一の連からなる RBT の探索法を，終端節点まで探. 提案した [7]．図 3 から不要な枝を削除し，T4 に r7 を追加. 索するのではなく，T1 の根から 0, 1 枝を辿れなくなるまで. した RBT を図 4 に示す．ただし，黒丸は終端節点を表す．. 探索するように変更する．図 4 の単一の連からなる RBT. 単一の連からなる RBT によるパケット分類は，入力パ. から不要な節点と枝を削除した単一の連からなる RBT を. ケットの系列に従って T1 の根から終端節点まで高々長さ w だけ探索を行う．単一の連からなる RBT の各節点は高々 一つだけ連を持つので，単一の連からなる RBT の探索時. 図 5 に示す．. 4. 単一の連からなる RBT のリスト. 間計算量は O(w) となり，ルール数 n に依存しない．また，. 単一の連からなる RBT は，与えられたルールリストの. 構成される節点の数は高々 nw で，連の数も高々 n なので，. 各ルールが一つの連だけからなる場合にのみ適用できる．. 単一の連からなる RBT の領域計算量は O(nw) となる．. けれども，与えられるルールリストは一般に単一の連か らなるルールリストではない．本章では，単一の連からな. 3.1 単一の連からなる RBT の不要な節点と枝の削除. るルールリストではないルールリスト R を単一の連から. 単一の連からなる RBT では，節点 v が連 ri を持ち，vi. なるルールリスト R1 , R2 , . . . , Rk へと分割し，各ルール. の 0, 1 枝の両方から到達可能な節点に ri よりも優先度の. リスト Ri に対する単一の連からなる RBT Fi を含むリス. 高いルールが存在しないときに v を非終端節点とする [7]．. ト L = [F1 , F2 , . . . , Fk ] を生成し，リスト L を探索してパ. けれども，図 4 の T1 の r5 を持つ節点 v5 の 0 枝から到達. ケット分類を行う手法を提案する．. 可能な節点に r5 よりも優先度の高いルールは存在しない ので，v5 の 0 枝は不要である．これより，節点 v が連 ri を. 4.1 Consecutive Ones Property. 持ち，v の b 枝から到達可能な節点に ri よりも優先度の高. ルールリスト R の列を並べ替えることにより，単一の連. いルールが存在しない場合は，b 枝を削除するように枝の. からなるルールリスト R へ変換できるかという問題を考. 削除規則を変更する．これに伴い，Tw に rn+1 を追加する. える．この問題は，ルールの 0, 1 を 1，∗ を 0 へと変換す. ことを止め，非終端節点と終端節点の区別も止める．そし. ることにより，ブール行列が Consecutive Ones Property. ⓒ 2018 Information Processing Society of Japan. ′. 4.
(5) Vol.2018-AL-167 No.3 2018/3/8. 情報処理学会研究報告 IPSJ SIG Technical Report. T1 T2 r1. T3. r6. r5. T4 r3. r3. r2. r4 図 5. 図 4 の単一の連からなる RBT の不要な節点と枝を削除. (C1P)[8], [9] を満たすかという問題へと帰着できる． ブール行列 M が C1P を満たすとは，M の各行の 1 が. ような区間の割当 I が存在するとき，G は区間グラフであ るという．. 連続するように M の列を並び替えられることをいう．表. 図 6 のグラフは，図 7 のような節点に対する区間の割当が. 3 の行列は，表 4 に示すように c1 , c3 , c2 , c4 の順に列を並べ. 存在するので区間グラフである．図 7 は，r1 に区間 [0, 3]. れば，各行の 1 が連続するので，C1P を満たす．これに対. を，r3 に区間 [3, 6] を割り当てることを意味する．. して，表 5 の行列はどのように列を並べても，各行の 1 を. 定義 4.2 S をサイズ n の集合とし，S の順序を [n] から. 連続させられないので C1P を満たさない．. S への全単射とする．ただし，[n] = {1, 2, ..., n} とする．. 表 1 のルールリストに対して，0, 1 を 1 に，∗ を 0 に変. G = (V, E) を n 個の節点からなるグラフとし，σ を V の順. 換して生成されるブール行列は表 3 のブール行列となる．. 序とする．G の順序 σ について，任意の i, k ∈ [n] に対し て，σ(i)σ(k) ∈ E ならば任意の j ∈ [i + 1, k − 1] に対して. 4.2 区間グラフ. σ(i)σ(j) ∈ E が成り立つとき，σ は I-ordering であるとい. 文献 [9] の定理 2 より，ブール行列 M が C1P を満たす ˜ ) が区間グラフであることが同値である．ただ ことと G(( M ) M ˜ し，M = であり，G(M ) は，M の各行 ri を節点 I とし，Mik と Mjk が共に 1 となるような k が存在すると. う．ただし，整数 i, j に対して [i, j] = {k | i ≤ k ≤ j, k ∈ Z}. き，ri と rj が隣接するようなグラフである．表 6 の行列. M に対するグラフ G(M ) を図 6 に示す．表 6 の行列 M に おいて，r1 と r8 は 1 列目が共に 1 なので，グラフ G(M ). 定理 4.2 ([10]). グラフ G が区間グラフであるとき，また. そのときに限り G は I-ordering を持つ． 図 6 のグラフは区間グラフであり， ( 1 2 3 4 5 6 7 σ= 7 1 5 2 6 9 3. 8. 9. 10. 8. 4. 10. ). はこのグラフの I-ordering である．. で r1 と r8 は隣接する． 定理 4.1 ([9], Theorem 2). とする．. 任意のブール行列 M に対. 定義 4.3 グ ラ フ G. =. (V, E) の 極 大 ク リ ー ク. して以下は同値である：. C1 , C2 , . . . , Ck の 列 S に つ い て ，任 意 の v ∈ V に 対. ( 1 ) G(M ) は区間グラフであり，M は G(M ) の極大クリー. して v を含むクリークが S において連続しているとき，S. ク行列である．. ( 2 ) M の列は全て極大であり，M は C1P を満たす．. をクリークチェインという． 図 6 のグラフにおいて，極大クリークは. グラフ G の極大クリーク行列 M とは，行列 M の行 ri が. C1 = {r1 , r2 , r5 , r7 },. G の節点であり，列 cj において 1 となる行の集合が G の. C2 = {r2 , r3 , r4 , r8 },. 極大クリークとなり，Mij = 1 ならば ri が極大クリーク cj に含まれる行列のことである．行列 M の列 ci が極大であ. C3 = {r1 , r2 , r3 , r5 , r6 , r9 },. るとは，ci ⊂ cj となるような列 cj が存在しない列のこと. C4 = {r2 , r4 , r10 }. をいう．ただし，列 cj = {i | Mij = 1} とする．例えば， 表 3 の行列において，列 c1 , c4 は極大ではなく，c2 , c3 は極 大である． 定義 4.1 グ ラ フ G = (V, E) に 対 し て ，任 意 の 節 点. x, y ∈ V について，I(x) ∩ I(y) ⇐⇒ xy ∈ E となる. ⓒ 2018 Information Processing Society of Japan. の四つであり，C1 , C3 , C2 , C4 の列がクリークチェインと なる． 以上より，与えられたルールリスト R を単一の連か ′. らなるルールリスト R へと変換できるかは，G(MR ) が. I-ordering を持つかを判定すれば良い．ただし，MR は，R 5.
(6) Vol.2018-AL-167 No.3 2018/3/8. 情報処理学会研究報告 IPSJ SIG Technical Report. 表 3 C1P を満たす行列 c1 c2 c3 c4. 表 4. 表 3 の列を並び替えた行列 c1 c3 c2 c4. 表 5 C1P を満たさない行列 c1 c2 c3 c4. 1. 0. 1. 0. 1. 1. 0. 0. 1. 1. 0. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 0. 1. 1. 0. 0. 1. 1. 0. 0. 1. 1. 1. 0. 1. 0. 1. 0. 0. 1. 1. 0. 0. 1. 1. 1. 0. 1. 0. 1. 1. 0. 0. 0. 1. 1. 0. 0. 0. 1. 0. 0. 1. 0. 0. 0. 1. 0. 1. 表 6. 表 3 の行列に単位行列 I を追加 c1 c2 c3 c4. 0. 1. 2. 3. 4. 5. 6. 7. r1. 1. 0. 1. 0. r7. r2. 1. 1. 1. 1. r1. r3. 0. 1. 1. 0. r5. r4. 0. 1. 0. 1. r5. 1. 0. 1. 0. r6. 0. 0. 1. 0. r7. 1. 0. 0. 0. r8. 0. 1. 0. 0. r3 r8. r9. 0. 0. 1. 0. r10. 0. 0. 0. 1. 8. r2 r6 r9. r4 r10. r5. 図 7. r1. 図 6 の節点に対する割当. Ci < Cj ≡ Ci = ∅ ∨. r7. Ci ⊂ Cj ∨ ( ) σ min{σ −1 (x) | x ∈ Ci △ Cj } ∈ Ci. r9. (1). のように定める．ただし，X △ Y = (X \ Y ) ∪ (Y \ X). r3. r6. である．たとえば，C1 = {1, 2, 5, 7}, C3 = {1, 2, 3, 5, 6, 9},. σ −1 = (2 4 7 9 3 5 1 8 6 10) に対して min{σ −1 (x) | x ∈ C1 △ C3 } = min{σ −1 (x) | x ∈ {3, 6, 7, 9}}. r2. = min{7, 5, 1, 6}. r10. =1. r8. r4. で，σ(1) = 7 ∈ C1 より，C1 < C3 となる．順序 1 に従っ て，極大クリーク C1 , C2 , . . . , Ck をソートするとクリーク. 図 6. 表 6 の行列 M に対するグラフ G(M ). の 0, 1 を 1，∗ を 0 へと変換することにより生成した行列. チェインが得られる．. 4.3 ルールリスト分割. に，単位行列 Iw を追加した行列である．提案手法では，グ. ルールリスト R を単一の連からなるルールリストのリ. ラフ G が I-ordering を持つかの判定に，文献 [11] のアルゴ. スト LR = [R1 , R2 , . . . Rk ] へと分割するアルゴリズムを. リズムを用いた．文献 [11] のアルゴリズムは，与えられた. Algorithm1 に示す．Algorithm1 において，R が C1P を満. グラフ G が区間グラフであれば，G の I-ordering を返す．. たすとは，ルールリスト R から生成したブール行列 MR. 定理 4.1 より，行列 M の列 ci と G(M ) の極大クリーク. が C1P を満たすことをいう．ルール数が 3 未満のルールリ. は Ci が対応しており，G(M ) のクリークチェインの順に. ストは必ず C1P を満たすので，ルールリストのサイズ |R|. M の列を並べれば，M の各行の 1 が連続する．これより，. が 3 未満ならば，R のみを含むルールリストのリスト LR. M の各行の 1 が連続する列の順序を求めるためには，グラ. を返す．ルールリスト R のルール数が 3 以上の場合は，5. フの I-ordering σ からクリークチェインを求めればよい．. から 8 行目で R の先頭と先頭の次のルールから成るルー. I-ordering σ における極大クリークの順序関係を. ルリスト S を LR に挿入する．11 から 17 行目は，C1P を. ⓒ 2018 Information Processing Society of Japan. 6.
(7) Vol.2018-AL-167 No.3 2018/3/8. 情報処理学会研究報告 IPSJ SIG Technical Report. Algorithm 1: Rulelist Partiion. 1. input : Rulelist R output: List of Rulelist consisting of Single Run LR make an empty list of rulelist LR ;. 2. if |R| < 3 then. Algorithm 2: List of Single-RBT Search. 1. input : List of RBT consisting of Single Run LF , packet p output: highest priority rule number cand ← n + 1 // n is the number of rules ;. 3. add R to LR ;. 2. i←0;. 4. return LR ;. 3. while i < |LF | do. end. 4. c ← Fi (p) ;. make a new rulelist S;. 5. 5 6. add head(R) to S and remove head(R) ;. 7. add head(R) to S and remove head(R) ;. 8. add S to LR ;. 9. while R ̸= ∅ do. if c < cand then cand ← c; end. 6. r ← head(R) ;. return cand ;. 6 Linear Seach Proposed Method. it ← LR .begin ; flag = false ;. 11. while it ̸= LR .end do if ∗it ∪ {r} holds C1P then. 12 13. add r to ∗it ;. 14. flag = true ; break ;. 15. 5. Classification Time (s). 10. 4. 3. 2. end it ← it.next ;. 16. 1. end 17. if flag ̸= true then. 18. make a new rulelist S;. 19. add r to S ;. 20. add S to LR ; end. 21. 22. remove r from R ;. 0 100. 200. 300. 400. 500. The number of Rules (n). 図 8 分類時間（秒）. 機実験を行った．実験環境は，主記憶容量が 24GB，CPU. end. が Intel Core i7-980X 3.33 GHz の上 CentOS Release 6.2. return LR ;. である．ルール数が 100, 200, 300, 400, 500 のルールリスト とヘッダ数が十万のヘッダリストを Class Bench[12] を用 いて生成した．. 満たすルールリスト R1 , R2 , . . . Rk の先頭から，ルール r. 線型探索 (Linear Search) と提案手法による分類時間を. を加えても C1P を満たすルールリスト Ri を探し，そのよ. 図 8 に示す．ただし，単位は秒である．なお，提案手法. うなルールリストがあれば，そのルールリストに r を加え. のルールリスト分割によって生成されたルールリストの. る．そのようなルールリストがなければ，r のみから成る. 数は，ルール数 100, 200, 300, 400, 500 に対してそれぞれ. ルールリスト S を新たに生成し，S を LR に加える．. 5, 5, 6, 6, 6 である．. 4.4 単一の連からなる RBT のリストによる探索. の数より，少ない数のルールリストへとルールリストを分. 図 8 とルールリスト分割により生成されたルールリスト 前節の Algorithm1 で生成されるルールリストのリスト. LR = [R1 , R2 , . . . Rk ] の各 Ri に対して，単一の連からな る RBT Fi を構築する．この単一の連からなる RBT のリ. 割できれば提案手法は有効である．. 6. まとめ. スト LF = [F1 , F2 , . . . Fk ] を用いたパケット分類アルゴリ. 本稿では，単一の連からなる RBT を改善し，単一の連. ズムを Algorithm2 に示す．4 行目の Fi (p) は，パケット p. からなる RBT のリストによるパケット分類法を提案した．. で単一の連からなる RBT Fi を探索して得られるルール番. 提案手法は，ルールリストを単一の連からなるルールリス. 号を返す．. トのリスト LR = [R1 , R2 , . . . Rk ] へと分割し，各 Ri に対. 5. 計算機実験 提案手法の有効性を確かめるために C 言語を用いて計算 ⓒ 2018 Information Processing Society of Japan. して，単一の連からなる RBT Fi を構築する．分割数 k が 少ないときに提案手法の探索時間計算量がルール数 n に依 存しないことを計算機実験で確かめた．. 7.
(8) Vol.2018-AL-167 No.3 2018/3/8. 情報処理学会研究報告 IPSJ SIG Technical Report. 今後の主な課題は，提案手法を線型探索だけでなく他の. Vol. 15, No. 3, pp. 499–511 (2007).. パケット分類手法と比較すること，Algorithm1 のような 逐次探索よりも分割数を小さくするルールリスト分割アル ゴリズムを考案すること，単一の連からなる RBT のリス トを Algorithm2 のように素朴に探索するよりも効率よく 探索する手法を考案すること，の三つである． 参考文献 [1]. [2]. [3]. [4]. [5]. [6]. [7]. [8]. [9]. [10]. [11]. [12]. MIKAWA, K. and TANAKA, K.: Run-Based Trie Involving the Structure of Arbitrary Bitmask Rules, IEICE Transactions on Information and Systems, Vol. E98.D, No. 6, pp. 1206–1212 (online), DOI: 10.1587/transinf.2013EDP7087 (2015). Taylor, D. E.: Survey and Taxonomy of Packet Classification Techniques, ACM Comput. Surv., Vol. 37, No. 3, pp. 238–275 (2005). Li, W. and Li, X.: HybridCuts: A Scheme Combining Decomposition and Cutting for Packet Classification, 2013 IEEE 21st Annual Symposium on HighPerformance Interconnects, pp. 41–48 (online), DOI: 10.1109/HOTI.2013.12 (2013). Inoue, T., Mano, T., Mizutani, K., Minato, S. and Akashi, O.: Rethinking Packet Classification for Global Network View of Software-Defined Networking, 2014 IEEE 22nd International Conference on Network Protocols, pp. 296–307 (online), DOI: 10.1109/ICNP.2014.52 (2014). 原田崇司， 田中賢，三河賢治：Run-Based Trie から構 成される決定木の枝刈り法 (技術と社会・倫理)，電子情 報通信学会技術研究報告 = IEICE technical report : 信 学技報， Vol. 115, No. 294, pp. 11–17 (2015). 原田崇司， 田中賢，三河賢治：ポインタ付与による Run-Based Trie 探索の高速化 (回路とシステム)，電子情 報通信学会技術研究報告 = IEICE technical report : 信 学技報， Vol. 116, No. 315, pp. 13–18 (2016). 原田崇司， 田中賢，三河賢治：単一の連からなる RunBased Trie によるルール探索の高速化，研究報告アルゴ リズム (AL)， Vol. 2017, No. 2, pp. 1–7 (2017). Booth, K. S. and Lueker, G. S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Journal of Computer and System Sciences, Vol. 13, No. 3, pp. 335 – 379 (online), DOI: https://doi.org/10.1016/S00220000(76)80045-1 (1976). Habib, M., McConnell, R., Paul, C. and Viennot, L.: Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition and Consecutive Ones Testing, Theor. Comput. Sci., Vol. 234, No. 1-2, pp. 59–84 (online), DOI: 10.1016/S0304-3975(97)00241-7 (2000). Ramalingam, G. and Rangan, C.: A unified approach to domination problems on interval graphs, Information Processing Letters, Vol. 27, No. 5, pp. 271 – 274 (online), DOI: https://doi.org/10.1016/00200190(88)90091-9 (1988). Li, P. and Wu, Y.: A four-sweep LBFS recognition algorithm for interval graphs, Discrete Mathematics & Theoretical Computer Science, Vol. Vol. 16 no. 3 (online), available from ⟨http://dmtcs.episciences.org/2094⟩ (2014). Taylor, D. E. and Turner, J. S.: ClassBench: A Packet Classification Benchmark, IEEE/ACM Trans. Netw.,. ⓒ 2018 Information Processing Society of Japan. 8.
(9)
図
関連したドキュメント
Standard domino tableaux have already been considered by many authors [33], [6], [34], [8], [1], but, to the best of our knowledge, the expression of the
We shall give a method for systematic computation of γ K , give some general upper and lower bounds, and study three special cases more closely, including that of curves with
A NOTE ON SUMS OF POWERS WHICH HAVE A FIXED NUMBER OF PRIME FACTORS.. RAFAEL JAKIMCZUK D EPARTMENT OF
The objective of this study is to address the aforementioned concerns of the urban multimodal network equilibrium issue, including 1 assigning traffic based on both user
Restricting the input to n-vertex cubic graphs of girth at least 5, we apply a modified algorithm that is based on selecting vertices of minimum degree, using operations that remove
The set of families K that we shall consider includes the family of real or imaginary quadratic fields, that of real biquadratic fields, the full cyclotomic fields, their maximal
A lemma of considerable generality is proved from which one can obtain inequali- ties of Popoviciu’s type involving norms in a Banach space and Gram determinants.. Key words
Y ang , The existence of a nontrivial solution to a nonlinear elliptic boundary value problem of p-Laplacian type without the Ambrosetti–Rabinowitz condition, Non- linear Anal.
