Reference : Detecting Triangle Inequality Violations in Internet Coordinate Systems by Supervised Le...
Scientific congresses and symposiums : Paper published in a journal
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/23836
Detecting Triangle Inequality Violations in Internet Coordinate Systems by Supervised Learning
English
Liao, Yongjun [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques >]
Kaafar, Mohamed Ali [INRIA Rhone-Alpes > > > >]
Gueye, Bamba [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques > > > > >]
Cantin, François [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques >]
Geurts, Pierre [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation >]
Leduc, Guy mailto [Université de Liège - ULg > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques >]
12-May-2009
Lecture Notes in Computer Science
Springer
5550
352-363
Yes
No
International
0302-9743
Berlin
Germany
IFIP Networking 2009
12-14 May 2009
Aachen
Germany
[en] Internet Coordinate System ; Triangle Inequality Violation ; Decision Trees ; Supervised Learning
[en] 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 OREE), 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 OREE, we show that cutting these lists after a given number of neighbours, or when OREE crosses a given threshold value, achieves very good performance to detect TIVs.
EU FP6
ANA - Autonomic Networking Architecture
Researchers
http://hdl.handle.net/2268/23836
10.1007/978-3-642-01399-7_28
http://www.montefiore.ulg.ac.be/services/stochastic/pubs/2009/LKGCGL09
FP7 ; 223936 - ECODE - Experimental COgnitive Distributed Engine

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
YL-networking2009.pdfAuthor postprint244.86 kBView/Open
Restricted access
liao-networking09.pdfPublisher postprint325.43 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.