Presentation | 2008-03-06 Are Internet Coordinate Embedding Systems Really Accurate? Eng Keong Lua, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Internet coordinate embedding systems embed latency such as Round-Trip-Times (RTTs) between nodes into some geometric space so that unmeasured RTTs can be estimated using distance computation in that space. If accurate, such techniques would allow us to predict Internet RTTs without extensive measurements. The published techniques appear to work very well when accuracy is measured by stress or absolute relative error. However, our own experience with using these algorithms has been disappointing in several respects. First, results are often unpredictable in the sense that many nodes obtain good distance estimates while a few obtain very bad results - and in a real-world setting nodes cannot determine the quality of their distance estimates without doing the kind of fully-meshed probing that coordinate embedding systems are intended to eliminate. Another lack of predictability is related to scalability-how the accuracy of an embedding change as the number of participating nodes grows or shrinks. Since difficulties of these kinds are often "averaged away" by accuracy metrics such as absolute relative error we propose several new metrics that we believe more closely capture the inaccuracies that are important to many applications. For example, applications may not need distances that are accurate in absolute terms, but only require that the relative distances of other nodes, while other applications may require that only the closest neighbors be accurately preserved. We analyze and compare the accuracy of several proposed coordinate embedding schemes using these new metrics. The results can be very poor, even in simple tree-like networks. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | |
Paper # | IN2007-166 |
Date of Issue |
Conference Information | |
Committee | IN |
---|---|
Conference Date | 2008/2/28(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 | Information Networks (IN) |
---|---|
Language | ENG |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Are Internet Coordinate Embedding Systems Really Accurate? |
Sub Title (in English) | |
Keyword(1) | |
1st Author's Name | Eng Keong Lua |
1st Author's Affiliation | NTT Service Integration Laboratories Nippon Telegraph and Telephone Corporation (NTT)() |
Date | 2008-03-06 |
Paper # | IN2007-166 |
Volume (vol) | vol.107 |
Number (no) | 525 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |