従属部分グラフ列挙によるルール並べ替え法

DOI

書誌事項

タイトル別名
  • A Rule Reordering Method via Dependent Subgraph Enumeration

抄録

パケット分類とは，ネットワーク機器に到着するパケットの振る舞いをポリシーに対応するルールリストによって決定することである．線形探索などによるパケット分類では，パケットとルールとの比較回数が増加するとパケット分類による通信の遅延が生じる．この遅延を最小化するようなルールの順序を求めるルール順序最適化問題が研究されている．この問題はNP困難であることが知られており[1]，様々な発見的解法が提案されてきた[2]〜[8]．この中で，平均的に最も遅延を減少させるSGM [4]は，各ルールから到達可能なルール集合の平均重みを比較することで遅延削減に影響するルールをリストの上位に配置するアルゴリズムである．しかし，到達可能なルールは各ルールから上位方向にあるルールに限られるため，候補となるルールの下位にある重みの大きいルールの影響まではSGMは考慮していない．本論文では，そのようなルールを選択的に評価に加えるルール並べ替え法を提案する．パケット分類アルゴリズムのベンチマークであるClassBench [9]を用いた計算機実験により提案手法の有効性を示す．

収録刊行物

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1390565134842316416
  • DOI
    10.14923/transinfj.2019pdp0019
  • ISSN
    18810225
    18804535
  • 本文言語コード
    ja
  • データソース種別
    • JaLC
    • KAKEN
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ