Name
Abstract | ||
|---|---|---|
Recent techniques for inferring business relationships between ASs [1,2] have yielded maps that have extremely few invalid BGP paths in the terminology of Gao[3]. However, some relationships inferred by these newer algorithms are incorrect, leading to the deduction of unrealistic AS hierarchies. We investigate this problem and discover what causes it. Having obtained such insight, we generalize the problem of AS relationship inference as a multiobjective optimization problem with node-degree-based corrections to the original objective function of minimizing the number of invalid paths. We solve the generalized version of the problem using the semidefinite programming relaxation of the MAX2SAT problem. Keeping the number of invalid paths small, we obtain a more veracious solution than that yielded by recent heuristics. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11427186_12 | WEA'05 Proceedings of the 4th international conference on Experimental and Efficient Algorithms |
Keywords | DocType | Volume |
invalid bgp path,lively beginning,max2sat problem,invalid path,recent technique,multiobjective optimization problem,recent heuristics,dead end,node-degree-based correction,inferring business relationship,newer algorithm,generalized version | Journal | abs/cs/0507047 |
ISSN | ISBN | Citations |
WEA 2005; LNCS 3503, p. 113, 2005 | 3-540-25920-1 | 29 |
PageRank | References | Authors |
2.78 | 11 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xenofontas Dimitropoulos | 1 | 1015 | 79.84 |
| Dmitri Krioukov | 2 | 1138 | 90.70 |
| Bradley Huffaker | 3 | 646 | 54.28 |
| Kimberly C. Claffy | 4 | 445 | 66.00 |
| George Riley | 5 | 414 | 41.53 |