Are internet coordinate embedding systems really accurate? (情報ネットワーク)

概要

論文の詳細を見る
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.
社団法人電子情報通信学会の論文
2008-02-28

Are internet coordinate embedding systems really accurate? (情報ネットワーク)

スポンサーリンク

概要

著者

関連論文

スポンサーリンク