| Presentation | 2002/6/17 Avoiding Routing Loops on the Internet Takuya YOSHIHIRO, Hiro ITO, Yasuo OKABE, Kazuo IWAMA, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Suppose that some particular link in the Internet is currently congested. Then a natural idea is to try to make packets bypass that link. This can be done by increasing the cost of that link intentionally, say from a_1 to a_2, since the Internet uses the shortest-path routing. Unfortunately, however, this often causes temporary loops for packet traveling, called routing loops. In this paper, we show that routing loops can be avoided by increasing the cost of the link not directly from a_1 to a_2 but through an intermediate value, a_3, i.e., from a_1 to a_3 and then to a_2. We may need several (more than one) intermediate values. We show that in such a occasion, the greedy strategy, namely raising the cost as much as possible in each step, is optimal. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | shortest paths / routing loops / acyclic digraphs / sensitivity analysis |
| Paper # | COMP2002-18 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2002/6/17(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 | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Avoiding Routing Loops on the Internet |
| Sub Title (in English) | |
| Keyword(1) | shortest paths |
| Keyword(2) | routing loops |
| Keyword(3) | acyclic digraphs |
| Keyword(4) | sensitivity analysis |
| 1st Author's Name | Takuya YOSHIHIRO |
| 1st Author's Affiliation | School of Informatics, Kyoto University() |
| 2nd Author's Name | Hiro ITO |
| 2nd Author's Affiliation | School of Informatics, Kyoto University |
| 3rd Author's Name | Yasuo OKABE |
| 3rd Author's Affiliation | Academic center for computing and Media Studies, Kyoto University |
| 4th Author's Name | Kazuo IWAMA |
| 4th Author's Affiliation | School of Informatics, Kyoto University |
| Date | 2002/6/17 |
| Paper # | COMP2002-18 |
| Volume (vol) | vol.102 |
| Number (no) | 140 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |