Affordable Access

Detecting Triangle Inequality Violations in Internet Coordinate Systems by Supervised Learning

IFIP Lecture Notes in Computer Science (LNCS)
Publication Date
  • Computer Science


Internet Coordinates Systems (ICS) are used to predict Internet distances with limited measurements. However the precision of an ICS is degraded by the presence of Triangle Inequality Violations (TIVs). Simple methods have been proposed to detect TIVs, based e.g. on the empirical observation that a TIV is more likely when the distance is underestimated by the coordinates. In this paper, we apply supervised machine learning techniques to try and derive more powerful criteria to detect TIVs. We first show that (ensembles of) Decision Trees (DTs) learnt on our datasets are very good models for this problem. Moreover, our approach brings out a discriminative variable (called ), which combines the classical estimation error with the variance of the estimated distance. This variable alone is as good as an ensemble of DTs, and provides a much simpler criterion. If every node of the ICS sorts its neighbours according to , we show that cutting these lists after a given number of neighbours, or when crosses a given threshold value, achieves very good performance to detect TIVs.Full Text at Springer, may require registration or fee

There are no comments yet on this publication. Be the first to share your thoughts.