On the design principles of network coordinates systems

[摘要] Since its inception, the concept of network coordinates has been successfully applied to solve a wide variety of problems such as overlay optimization, network routing, network localization, and network modeling. Despite these successes, several practical problems limit the benefits of network coordinates today. First, the Triangle Inequality Violation(TIV) among the Internet delays degrades the application performance of network coordinates, how to reduce the impact of TIV on network coordinates systems? Second, how can network coordinates be stabilized without losing accuracy in a distributed fashion so that they can be cached by applications? Third, how can network coordinates be secured such that legitimate nodes' coordinates are not impacted by misbehaving nodes? Although these problems have been discussed extensively, the solutions are still unclear. This thesis presents analytical studies for understanding these problems and reveals several new findings: (1) the analysis results from existing Internet delay measurements demonstrate the irregular behaviors of TIVs among the Internet delays, which implies the difficulty of modeling TIVs; (2) a new TIV alert mechanism can identify the edges causing severe TIVs and reduce the impact of TIVs on network coordinates; (3) a new model of coordinates stabilization based on error elimination can achieve stability without hurting accuracy; a novel algorithm based on this model is presented; (4) recently proposed statistical detection mechanisms cannot achieve an acceptable level of security against aggressive attacks. (5) an accountability protocol can completely protect coordinates computation and a TIV alert detection mechanism can effectively protect network coordinates against delay attacks. These findings offer guidelines on the design and applications of network coordinates systems.

[发布机构] Rice University

[效力级别] engineering