| Presentation | 2015-03-02 Polynomial-time Algorithm for Traffic Engineering by Link Metric Update Shinya KURIMOTO, Hiroyoshi MIWA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In general, a route determined by an internet routing protocol such as OSPF and BGP is the shortest path that the sum of the metrics of the links contained in the path is the minimum. If a link has small metrics, many routes may pass the link, and it may cause the congestion of the link. Therefore, the number of the routes in a link must be restricted to avoid a congestion. The link metric decision problem to determine the link metrics so as to limit the number of the paths in a link was denned and analyzed by an author before. It was proved that this problem is NP-hard and that the problem can be solved in polynomial time when the metric of only a link must be determined. In this paper, we present a polynomial-time algorithm to this problem when the number of links whose metrics must be determined is restricted and the number of node pairs whose routes must be determined is restricted. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Link Metric / OSPF / Traffic Control / Polynomial-time Algorithm / NP-complete / Optimization problem |
| Paper # | NS2014-185 |
| Date of Issue |
| Conference Information | |
| Committee | NS |
|---|---|
| Conference Date | 2015/2/23(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) | Polynomial-time Algorithm for Traffic Engineering by Link Metric Update |
| Sub Title (in English) | |
| Keyword(1) | Link Metric |
| Keyword(2) | OSPF |
| Keyword(3) | Traffic Control |
| Keyword(4) | Polynomial-time Algorithm |
| Keyword(5) | NP-complete |
| Keyword(6) | Optimization problem |
| 1st Author's Name | Shinya KURIMOTO |
| 1st Author's Affiliation | Kwansei Gakuin University() |
| 2nd Author's Name | Hiroyoshi MIWA |
| 2nd Author's Affiliation | Graduate School of Science and Technology, Kwansei Gakuin University |
| Date | 2015-03-02 |
| Paper # | NS2014-185 |
| Volume (vol) | vol.114 |
| Number (no) | 477 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |