| Presentation | 2019-12-13 Computational Complexity of Relaxed Optimal Rule Ordering Takashi Harada, Ken Tanaka, Kenji Mikawa, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The packet classification aims to determine the behavior of the incoming packets of network devices. The linear search classification algorithm assigns prior action to each packet according to the classification policy. This is accomplished by comparing the packet header with classification rules until a match is found. As the processing latency of packet classification is proportional to the number of rules, a large number of rules can result in serious communication latency. To resolve this problem, the packet classification is generalized as optimal rule ordering (ORO), which aims to identify the rule ordering that minimizes the latency caused as a result of packet classification. If two different rules in the rule list match the same packet, interchanging those rules may cause policy violation. Thus, most studies on ORO do not allow the posterior rule to be placed at a position higher than that of the prior rule. However, there exist cases wherein interchanging such rules do not violate the policy. Herein, we will consider the relaxed ORO (RORO) problem wherein some rules that are not interchangeable in conventional ORO can still be interchanged. We prove that the decision problem corresponding to RORO is NP-hard. This result demonstrates the difficulties associated with optimal packet classification and the requirements of heuristics for RORO. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | packet classification / dependent rules / rule ordering / NP-hard |
| Paper # | COMP2019-36 |
| Date of Issue | 2019-12-06 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2019/12/13(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Ikaho Seminar House, Gunma University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| Vice Chair | Shinichi Nakano(Gunma Univ.) |
| Secretary | Shinichi Nakano(Kumamoto Univ) |
| Assistant | Kazuhisa Seto(Seikei Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Computational Complexity of Relaxed Optimal Rule Ordering |
| Sub Title (in English) | |
| Keyword(1) | packet classification |
| Keyword(2) | dependent rules |
| Keyword(3) | rule ordering |
| Keyword(4) | NP-hard |
| 1st Author's Name | Takashi Harada |
| 1st Author's Affiliation | Kochi University of Technology(Kochi Univ. of Tech.) |
| 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 | 2019-12-13 |
| Paper # | COMP2019-36 |
| Volume (vol) | vol.119 |
| Number (no) | COMP-340 |
| Page | pp.pp.47-54(COMP), |
| #Pages | 8 |
| Date of Issue | 2019-12-06 (COMP) |