Paper Abstract and Keywords |
Presentation |
2017-06-19 14:10
Computing the Number of Packets that match A Filtering Rule via MTZDDs Takashi Harada, Ken Tanaka (Kanagawa Univ.), Kenji Mikawa (Niigata Univ.) CAS2017-9 VLD2017-12 SIP2017-33 MSS2017-9 |
Abstract |
(in Japanese) |
(See Japanese page) |
(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) |
(in English) |
packet filtering / MTZDDs / filtering rule order / / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 117, no. 96, CAS2017-9, pp. 45-50, June 2017. |
Paper # |
CAS2017-9 |
Date of Issue |
2017-06-12 (CAS, VLD, SIP, MSS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
CAS2017-9 VLD2017-12 SIP2017-33 MSS2017-9 |
Conference Information |
Committee |
SIP CAS MSS VLD |
Conference Date |
2017-06-19 - 2017-06-20 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Niigata University, Ikarashi Campus |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
|
Paper Information |
Registration To |
CAS |
Conference Code |
2017-06-SIP-CAS-MSS-VLD |
Language |
Japanese |
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 |
Keyword(4) |
|
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
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.) |
4th Author's Name |
|
4th Author's Affiliation |
() |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2017-06-19 14:10:00 |
Presentation Time |
20 minutes |
Registration for |
CAS |
Paper # |
CAS2017-9, VLD2017-12, SIP2017-33, MSS2017-9 |
Volume (vol) |
vol.117 |
Number (no) |
no.96(CAS), no.97(VLD), no.98(SIP), no.99(MSS) |
Page |
pp.45-50 |
#Pages |
6 |
Date of Issue |
2017-06-12 (CAS, VLD, SIP, MSS) |
|