Acyclic Type-of-Relationship Problems on the Internet

We contribute to the study of inferring commercial relationships between autonomous systems (AS relationships) from observable BGP routes. We deduce several forbidden patterns of AS relationships that impose a certain type of acyclicity on the AS graph. We investigate algorithms for solving the

acyclic all-paths type-of-relationship

problem, i.e., given a set of AS paths, find an orientation of the edges according to some types of AS relationships such that the oriented AS graph is acyclic (with respect to the forbidden patterns) and all AS paths are valley-free. As possible AS relationships we include customer-to-provider, peer-to-peer, and sibling-to-sibling. Moreover, we examine a number of problem versions parameterized by sets

K

and

U

where

K

is the set of edge types available for describing explicit pre-knowledge and

U

is the set of edge types available for completion of partial orientations. A complete complexity classification of all 56 cases (8 type sets for pre-knowledge and 7 type sets for completion) is given. The most relevant practical result is a linear-time algorithm for finding an acyclic and valley-free completion using customer-to-provider relations given

any

kind of pre-knowledge. Interestingly, if we allow sibling-to-sibling relations for completions then most of the non-trivial inference problems become NP-hard.