Inferring AS Relationships: Dead End or Lively Beginning?

Details Inferring AS Relationships: Dead End or Lively Beginning? Inferring AS Relationships: Dead End or Lively Beginning?

2005-07-19

arxiv.org/abs/cs/0507047v1

WEA 2005; LNCS 3503, p. 113, 2005

Computer Science

Networking and Internet Architecture

Scientific paper

10.1007/11427186_12

Recent techniques for inferring business relationships between ASs have yielded maps that have extremely few invalid BGP paths in the terminology of Gao. 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.

Affiliated with

Also associated with

No associations

Rating

Inferring AS Relationships: Dead End or Lively Beginning? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Inferring AS Relationships: Dead End or Lively Beginning?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inferring AS Relationships: Dead End or Lively Beginning? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-287365