| Presentation | 2015-10-19 Efficient Network Policy Checking with Multi-dimensional Graph Traversal Algorithm Chen Richard, Takeru Inoue, Toru Mano, Kimihiro Mizutani, Hisashi Nagata, Osamu Akashi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Since network operators find much difficulty in guaranteeing tocorrectly configure their complex networks, they are stronglydemanding a new technology to automatically check the networkconfiguration. The technology must be very efficient in terms oftime, because there can be a number of policies configured in anetwork for performance and security reasons. In this paper, weintroduce a novel graph traversal algorithm to make the checkingprocess very efficient. Since network policies are often represnetedas a compressed graph for space limitation, our algorithm well suitsfor the high-speed policy checking. Our algorithm extends thewell-established dynamic programming paradigm to enumerate all thepolicies matched to a given condition. We conduct thoroughexperiments with real network datasets, and reveal that our algorithmis one hundred times faster than the state-of-the art. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | network policy checking / graph traversal / dynamic programming |
| Paper # | IA2015-34 |
| Date of Issue | 2015-10-12 (IA) |
| Conference Information | |
| Committee | IA |
|---|---|
| Conference Date | 2015/10/19(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Takeda Hall, Takeda Bldg. 5F, Hongo Campus, Univ. of Tokyo |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | Network R&D Testbed Operation and Utilization, etc. (cosponsored by ADVNET) |
| Chair | Ken-ichi Yoshida(Univ. of Tsukuba) |
| Vice Chair | Hiroyuki Osaki(Kwansei Gakuin Univ.) / Masahiro Jibiki(NICT) / Yutaka Nakamura(Kyushu Inst. of Tech.) |
| Secretary | Hiroyuki Osaki(Tokyo Inst. of Tech.) / Masahiro Jibiki(Osaka Univ.) / Yutaka Nakamura |
| Assistant | Yuichiro Hei(KDDI R&D Labs.) / Hiroshi Yamamoto(Ritsumeikan Univ.) / Toshiki Watanabe(NEC) |
| Paper Information | |
| Registration To | Technical Committee on Internet Architecture |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Efficient Network Policy Checking with Multi-dimensional Graph Traversal Algorithm |
| Sub Title (in English) | |
| Keyword(1) | network policy checking |
| Keyword(2) | graph traversal |
| Keyword(3) | dynamic programming |
| 1st Author's Name | Chen Richard |
| 1st Author's Affiliation | Nippon Telegraph and Telephone Corporation(NTT) |
| 2nd Author's Name | Takeru Inoue |
| 2nd Author's Affiliation | Nippon Telegraph and Telephone Corporation(NTT) |
| 3rd Author's Name | Toru Mano |
| 3rd Author's Affiliation | Nippon Telegraph and Telephone Corporation(NTT) |
| 4th Author's Name | Kimihiro Mizutani |
| 4th Author's Affiliation | Nippon Telegraph and Telephone Corporation(NTT) |
| 5th Author's Name | Hisashi Nagata |
| 5th Author's Affiliation | Nippon Telegraph and Telephone Corporation(NTT) |
| 6th Author's Name | Osamu Akashi |
| 6th Author's Affiliation | Nippon Telegraph and Telephone Corporation(NTT) |
| Date | 2015-10-19 |
| Paper # | IA2015-34 |
| Volume (vol) | vol.115 |
| Number (no) | IA-256 |
| Page | pp.pp.25-30(IA), |
| #Pages | 6 |
| Date of Issue | 2015-10-12 (IA) |