| Presentation | 2014-03-07 Approximation Algorithm for Finding Protected Links to Keep Small Increase of Path Length during Link Failures Kohei NISHIDA, Hiroyoshi MIWA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A telecommunication network should be reliable, since it is important as social infrastructure. However, in many actual networks, there exists the risk that the quality of service drastically degrades when the length of paths increases by a link failure. To get rid of this risk, it is necessary to design a network so that the maximum increase rate of the length of all paths is small even if a link fails. Therefore, the critical links whose failures significantly degrade the performance must be protected by rapid recovery so that the failures cannot be detected over the IP layer. The number of protected links should be small to restrict the investment cost for facilities and operational cost for Internet service providers. In this paper, we formulate this link protection problem. In addition, we propose an approximation algorithm to solve the problem that the number of simultaneous link failures is restricted to two. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | network / quality of service / link failure / increase of path length / optimization / approximation algorithm |
| Paper # | NS2013-241 |
| 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) | Approximation Algorithm for Finding Protected Links to Keep Small Increase of Path Length during Link Failures |
| Sub Title (in English) | |
| Keyword(1) | network |
| Keyword(2) | quality of service |
| Keyword(3) | link failure |
| Keyword(4) | increase of path length |
| Keyword(5) | optimization |
| Keyword(6) | approximation algorithm |
| 1st Author's Name | Kohei NISHIDA |
| 1st Author's Affiliation | Graduate School of Science and Tecnology, Kwansei Gakuin University() |
| 2nd Author's Name | Hiroyoshi MIWA |
| 2nd Author's Affiliation | Graduate School of Science and Tecnology, Kwansei Gakuin University |
| Date | 2014-03-07 |
| Paper # | NS2013-241 |
| Volume (vol) | vol.113 |
| Number (no) | 472 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |