| Presentation | 2009-03-03 A Design Method of Robust Networks against Performance Deterioration in Failures Nozomu KATAYAMA, Takeshi FUJIMURA, Hiroyoshi MIWA, Noriaki KAMIYAMA, Haruhisa HASEGAWA, Hideaki YOSHINO, |
|---|---|
| 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. But it is known that, in many real networks, there exists the risk that the quality of service drastically deteriorates when the length of paths increases by a link failure. To get rid of this risk, it is necessary to design a network that the maximum increasing rate of the length of all paths in a link failure is small. Such a network must be constructed by adding some links to a network, because it is impossible to reconstruct a network which is in operation. In this paper, we formalize this network design problem as the optimization problem that determines the edges added to a graph so that the maximum increasing rate of the lengths of all paths in an edge deletion is not more than a threshold. First, we prove that this problem is NP-complete. Next, we propose an approximation algorithm for this problem and evaluate its performance by applying the algorithm to some real ISP networks. As a result, the proposed algorithm shows the good performance. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | quality of service / backbone network / optimization problem / NP-complete / approximation algorithm |
| Paper # | NS2008-164 |
| Date of Issue |
| Conference Information | |
| Committee | NS |
|---|---|
| Conference Date | 2009/2/24(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) | A Design Method of Robust Networks against Performance Deterioration in Failures |
| Sub Title (in English) | |
| Keyword(1) | quality of service |
| Keyword(2) | backbone network |
| Keyword(3) | optimization problem |
| Keyword(4) | NP-complete |
| Keyword(5) | approximation algorithm |
| 1st Author's Name | Nozomu KATAYAMA |
| 1st Author's Affiliation | Kwansei Gakuin University() |
| 2nd Author's Name | Takeshi FUJIMURA |
| 2nd Author's Affiliation | Kwansei Gakuin University |
| 3rd Author's Name | Hiroyoshi MIWA |
| 3rd Author's Affiliation | Kwansei Gakuin University |
| 4th Author's Name | Noriaki KAMIYAMA |
| 4th Author's Affiliation | NTT Service Integration Laboratories |
| 5th Author's Name | Haruhisa HASEGAWA |
| 5th Author's Affiliation | NTT Service Integration Laboratories |
| 6th Author's Name | Hideaki YOSHINO |
| 6th Author's Affiliation | NTT Service Integration Laboratories |
| Date | 2009-03-03 |
| Paper # | NS2008-164 |
| Volume (vol) | vol.108 |
| Number (no) | 457 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |