| Presentation | 2017-06-19 Computing the Number of Packets that match A Filtering Rule via MTZDDs Takashi Harada, Ken Tanaka, Kenji Mikawa, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A filtering policy is denoted as a filtering rule list and is achieved by linear search of the rule list. The increase in the number of filtering rules causes a latency. Thus various methods for optimizing the rule order have been developed to minimize the latency. In the proposed methods, the weight of the filtering rule is assigned randomly or according to the Zipf distribution. The number of packets that match an $i$th filtering rule means that the number of packets that match an $i$th rule and not through the first rule to the $(i-1)$th rule in a rule list $bd{R}$. So the above methods of assignment are inappropriate. In this paper, we prove that the problem of computing the number of packets that match a filtering rule is $#mathcal{P}$-complete and propose a method for computing the number of packets via Multi-terminal Zero-suppressed Binary Decision Diagrams (MTZDDs). The method construct a MTZDD for the rule list $bd{R}$ and computes the number of packets that match an $i$th rule by the {it count} operation on the MTZDDs. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | packet filtering / MTZDDs / filtering rule order |
| Paper # | CAS2017-9,VLD2017-12,SIP2017-33,MSS2017-9 |
| Date of Issue | 2017-06-12 (CAS, VLD, SIP, MSS) |
| Conference Information | |
| Committee | SIP / CAS / MSS / VLD |
|---|---|
| Conference Date | 2017/6/19(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Niigata University, Ikarashi Campus |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Masahiro Okuda(Univ. of Kitakyushu) / Mitsuru Hiraki(Renesas) / Morikazu Nakamura(Univ. of Ryukyus) / Hiroyuki Ochi(Ritsumeikan Univ.) |
| Vice Chair | Shogo Muramatsu(Niigata Univ.) / Naoyuki Aikawa(TUS) / Hideaki Okazaki(Shonan Inst. of Tech.) / Shigemasa Takai(Osaka Univ.) / Noriyuki Minegishi(Mitsubishi Electric) |
| Secretary | Shogo Muramatsu(Chiba Inst. of Tech.) / Naoyuki Aikawa(Takushoku Univ.) / Hideaki Okazaki(Renesas) / Shigemasa Takai(Shonan Inst. of Tech.) / Noriyuki Minegishi(Toshiba) |
| Assistant | Masayoshi Nakamoto(Hiroshima Univ.ひろ) / Yohei Nakamura(Hitachi) / Hideki Kinjo(Okinawa Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Signal Processing / Technical Committee on Circuits and Systems / Technical Committee on Mathematical Systems Science and its applications / Technical Committee on VLSI Design Technologies |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Computing the Number of Packets that match A Filtering Rule via MTZDDs |
| Sub Title (in English) | |
| Keyword(1) | packet filtering |
| Keyword(2) | MTZDDs |
| Keyword(3) | filtering rule order |
| 1st Author's Name | Takashi Harada |
| 1st Author's Affiliation | Kanagawa University(Kanagawa Univ.) |
| 2nd Author's Name | Ken Tanaka |
| 2nd Author's Affiliation | Kanagawa University(Kanagawa Univ.) |
| 3rd Author's Name | Kenji Mikawa |
| 3rd Author's Affiliation | Niigata University(Niigata Univ.) |
| Date | 2017-06-19 |
| Paper # | CAS2017-9,VLD2017-12,SIP2017-33,MSS2017-9 |
| Volume (vol) | vol.117 |
| Number (no) | CAS-96,VLD-97,SIP-98,MSS-99 |
| Page | pp.pp.45-50(CAS), pp.45-50(VLD), pp.45-50(SIP), pp.45-50(MSS), |
| #Pages | 6 |
| Date of Issue | 2017-06-12 (CAS, VLD, SIP, MSS) |