| Presentation | 2010-03-05 Design Method of Smallest Robust Networks against Performance Deterioration during 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. We proposed an approximation algorithm for a network design problem that constructs such a network by adding some links to a network in our previous paper. On the other hand, when we construct a network from scratch, we must consider not only the quality of the failure time but also that of the normal time. In this paper, we formalize this network design problem as the optimization problem that determines a graph with a constrained degree and diameter 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 / path length / optimization problem / NP-complete / approximation algorithm |
| Paper # | NS2009-228 |
| Date of Issue |
| Conference Information | |
| Committee | NS |
|---|---|
| Conference Date | 2010/2/25(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) | Design Method of Smallest Robust Networks against Performance Deterioration during Failures |
| Sub Title (in English) | |
| Keyword(1) | quality of service |
| Keyword(2) | path length |
| 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 | 2010-03-05 |
| Paper # | NS2009-228 |
| Volume (vol) | vol.109 |
| Number (no) | 448 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |