Paper Abstract and Keywords |
Presentation |
2011-07-21 17:10
Entwork Reliability Evaluation Using Efficient Path Enumeration ALgorithms Toshiki Saitoh, Jun Kawahara, Ryo Yoshinaka, Takeru Inoue (JST), Shin-ichi Minato (Hokkaido Univ.) IN2011-55 |
Abstract |
(in Japanese) |
(See Japanese page) |
(in English) |
Recently, novel algorithms that enumerate all possible paths on a graph have been proposed. They commonly take advantage of Zero-suppressed Binary Decision Diagram, or ZDD, which is an efficient data structure for representing family of sets. These algorithms treat a path as a set of edges, and so ZDD is allowed to handle paths in its own way. ZDD’s efficient algebra is also used in the algorithms to select required paths. We develop a path management system that relies on the ZDD path enumeration algorithm. Our management system accepts some filtering conditions to select paths, and finds the best one from them. The best path is correctly chosen without approximation even if there is a dependency among link failures. Despite of the correctness, our system is quite efficient; 1126509504221649 paths on a grid network of 81 nodes are enumerated in 1.85 seconds, and these paths are filtered and the best one is found in 0.1 seconds. |
Keyword |
(in Japanese) |
(See Japanese page) |
(in English) |
ZDD / path enumeration / network management / / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 111, no. 146, IN2011-55, pp. 57-62, July 2011. |
Paper # |
IN2011-55 |
Date of Issue |
2011-07-14 (IN) |
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 |
IN2011-55 |
Conference Information |
Committee |
IN NV |
Conference Date |
2011-07-21 - 2011-07-22 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Hokkaido University |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
IPv6, Photonic network system, New/Next Generation Network, etc |
Paper Information |
Registration To |
IN |
Conference Code |
2011-07-IN |
Language |
Japanese |
Title (in Japanese) |
(See Japanese page) |
Sub Title (in Japanese) |
(See Japanese page) |
Title (in English) |
Entwork Reliability Evaluation Using Efficient Path Enumeration ALgorithms |
Sub Title (in English) |
|
Keyword(1) |
ZDD |
Keyword(2) |
path enumeration |
Keyword(3) |
network management |
Keyword(4) |
|
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Toshiki Saitoh |
1st Author's Affiliation |
Japan Science and Technology Agency (JST) |
2nd Author's Name |
Jun Kawahara |
2nd Author's Affiliation |
Japan Science and Technology Agency (JST) |
3rd Author's Name |
Ryo Yoshinaka |
3rd Author's Affiliation |
Japan Science and Technology Agency (JST) |
4th Author's Name |
Takeru Inoue |
4th Author's Affiliation |
Japan Science and Technology Agency (JST) |
5th Author's Name |
Shin-ichi Minato |
5th Author's Affiliation |
Hokkaido University (Hokkaido Univ.) |
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 |
2011-07-21 17:10:00 |
Presentation Time |
25 minutes |
Registration for |
IN |
Paper # |
IN2011-55 |
Volume (vol) |
vol.111 |
Number (no) |
no.146 |
Page |
pp.57-62 |
#Pages |
6 |
Date of Issue |
2011-07-14 (IN) |
|