| Presentation | 2010-03-05 Traffic Engineering by Polynomially Solvable Link Metric Optimization AKIRA Noguchi, Takeshi FUJIMURA, Hiroyoshi MIWA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Open Shortest Path First (OSPF) is the most commonly used intra-domain internet routing protocol. As the routes of paths are determined by basically only the link metrics, many paths may pass a link with small metric; therefore, there is high possibility that it causes the congestion of the link. It is essential that the number of the paths with large traffic in a link is limited to avoid a congestion; therefore, it is important to determine the link metrics so as to limit the number of the paths in a link. In this paper, we define this link metric decision problem, and we prove that it is NP-complete. In addition, when we restricted this problem to determine the metric of only a link, we show that it can be solved in polynomial time. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | OSPF / NP-complete / polynomial-time algorithm / optimization problem |
| Paper # | NS2009-229 |
| 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) | Traffic Engineering by Polynomially Solvable Link Metric Optimization |
| Sub Title (in English) | |
| Keyword(1) | OSPF |
| Keyword(2) | NP-complete |
| Keyword(3) | polynomial-time algorithm |
| Keyword(4) | optimization problem |
| 1st Author's Name | AKIRA Noguchi |
| 1st Author's Affiliation | Department of Science and Technology, Kwansei Gakuin University() |
| 2nd Author's Name | Takeshi FUJIMURA |
| 2nd Author's Affiliation | Department of Science and Technology, Kwansei Gakuin University |
| 3rd Author's Name | Hiroyoshi MIWA |
| 3rd Author's Affiliation | Department of Science and Technology, Kwansei Gakuin University |
| Date | 2010-03-05 |
| Paper # | NS2009-229 |
| Volume (vol) | vol.109 |
| Number (no) | 448 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |