A HierarchicalIPtoAS mapping System一个分层的IP为测绘系统

1、analyzing the impact of granularity on ip-to-as mappingpresented by baobao zhangauthours:baobao zhang, jun bi, yangyang wang, jianping wu1 introductionndoing?nmap the ip address to the as that uses the ipnmeaningnhelp network managers diagnose network failurendiscover the as-level topology with trac

2、eroutensome other applications that need to map ip to asan example2 data collectionndata sourcentraceroute data (from caida)nbgp routing table (from routeviews)nprocessing into pairsnextract the prefixes and as paths from routing tablesnextract the destination ips and ip paths from traceroute datanf

3、ind the longest matching prefix for the destination ipnthe ip path associated with the destination ip and the as path associated with the longest prefix form one pairnorigin ip-to-as mappingnextract the prefixes and its origin ases from routing tablesnmap every prefix to its origin asdata collection

4、ndate: 04/22/2010nduring: one day3 methodologyndefinitionnexact matchnambiguous matchnmismatchnmethodsnprefix-granularity method (pgm)nip-granularity method (igm)nprefix-granularity limit method (pglm)nhierarchical mapping system (hms)nassumptionnthe traceroute path is consistent with the bgp as pat

5、h.methodsnprefix-granularity method (pgm)ni.e. maos methodnbind many ip addresses into one prefixnmap one prefix to many ases by setting thresholdntight couplingnprosncan modify the incorrect mappings for the ips that dont appear in the training dataset nconsnmistakenly modify the originally correct

6、 mappings for the ips that dont appear in the training dataset. (tight coupling)nthreshold. miss to modify the incorrect mappings for the ips that appear in the training datasetnthreshold. bring about ambiguous mappingsmethodsnip-granularity method (igm)nwe propose it for the first timenmap one ip t

7、o one only asnloose couplingnprosneliminate the ambiguous mappingsnconsnonly can modify the mappings for the ips that appear in the training dataset.methodsnprefix-granularity limit method (pglm)none fictitious methodnthe limit of pgm. set the threshold =0nit is only used to be comparedmethodsnhiera

8、rchical mapping system (hms)ncombine the igm with pgmnthree levels (/32 level, /24 level, origin level)nfirstly look up in the /32 level mapping, then /24 level mapping, finally the origin level mappingnprosncomplement the strength of tight coupling and loose coupling nconsn * inherit the characteri

9、stic of ambiguity from pgm4 evaluationndatasetevaluationntraining accuracyevaluationnvalidation accuracyevaluationncompare trained mapping with the origin mappingevaluation5 classification tree analysisnmotivationnquantify the pros and cons for the igm and pgmnanalyze the obstacles in the way of imp

10、roving the accuracy for the igm and pgm nother potential findingsnconstructing classification treetable 7 the improvement gained by correcting the mapping of the types for the pgm vds1gainvds2gainvds3gainvds4gaintype10.00%0.00%0.00%0.00%type20.71%0.02%0.27%0.05%type314.25%8.47%8.15%10.30%type40.00%0

11、.00%0.00%0.00%type52.37%1.55%0.35%2.47%type60.00%0.00%0.00%0.00%type70.80%1.57%1.47%1.05%type8(base)-0.29%(5.66%)-0.64%(7.34%)-0.15%(6.79%)-0.33%(6.20%)type1-2(base)0.00%(1.06%)0.00%(0.61%)0.00%(0.58%)0.00%(1.92%)type2-20.36%0.06%1.01%0.25%type3-20.42%1.12%22.29%15.08%type4-20.00%0.00%0.00%0.00%type

12、5-20.45%0.17%0.25%3.30%type8-2(base)0.00%(2.93%)0.00%(2.38%)-0.03%(2.22%)-0.01%(0.15%)type-all19.85%12.87%35.18%32.94%5.1 quantify the pros and cons for the igm and pgmnpros and consn(+) modify the incorrect mappings for the ips that dont appear in the training dataset (type 8-2, 1-2 for pgm, nothin

13、g for igm)n(-) mistakenly modifies the originally correct mappings for the ips that dont appear in the training dataset. (type 2-2 for pgm , nothing for igm)n(-) miss to modify the incorrect mappings for the ips that appear in the training dataset (type3 for pgm and igm)nquantifyingnfor pgm, base(ty

14、pe8-2)+base(type1-2)-gain(type2-2) is positive. 3.63%, 2.93%, 1.79% and 1.81% npgm(gain(type3)-igm(gain(type3) . 14.00%, 8.38%, 7.94% and 9.81% nconclusionnthe igm is superior to the pgm5.2 analyze the obstacles in the way of improving the accuracy for the igm and pgmnigmntype 7. (ips do not appear

15、in the training dataset) npgmntype 3. (ips appear in the training dataset, but miss to modify due to the tight coupling)ntype 3-2. (ips do not appear in the training dataset) 5.3 other findingsnthe limit of validation accuracy1-gain(type2) -gain(type3)-gain(type5)nfor igm98.87%,97.96%,98.43% ,98.96% nfor pg