| Presentation | 2014-03-07 Method for Finding Protected Nodes for Network Design Invulnerability against Crash of Some Nodes Tomomi MATSUI, Hiroyoshi MIWA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The high reliability and performance are needed as the Internet becomes an important social infrastructure. However, in many actual networks, there exists the risk of telecommunication blackout by a node failure or attack. To get rid of this risk, it is necessary to design a network so that many nodes can communicate each other even if nodes fail. It is desirable that all nodes have their backup facility, but it needs much cost; therefore, at least critical nodes whose failures segmentalize a network to many small connected components must be protected by backup facility. In our previous work, we addressed a problem to determine protected nodes such that, even if non-protected nodes fail, the minimum size of the connected components of a remaining network is not less than a threshold. In this paper, we propose an approximation algorithm with the approximation ratio of two for the problem restricted to the case that at most two nodes simultaneously fail. Moreover, we evaluate the performance of the approximation algorithm by using actual network topologies. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Node protection / Network design / Optimization / Algorithm |
| Paper # | NS2013-239 |
| Date of Issue |
| Conference Information | |
| Committee | NS |
|---|---|
| Conference Date | 2014/2/27(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Network Systems(NS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Method for Finding Protected Nodes for Network Design Invulnerability against Crash of Some Nodes |
| Sub Title (in English) | |
| Keyword(1) | Node protection |
| Keyword(2) | Network design |
| Keyword(3) | Optimization |
| Keyword(4) | Algorithm |
| 1st Author's Name | Tomomi MATSUI |
| 1st Author's Affiliation | Kwansei Gakuin University() |
| 2nd Author's Name | Hiroyoshi MIWA |
| 2nd Author's Affiliation | Kwansei Gakuin University |
| Date | 2014-03-07 |
| Paper # | NS2013-239 |
| Volume (vol) | vol.113 |
| Number (no) | 472 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |