Policy relationship annotations of predefined AS-level topologies

The contractual relationships between autonomous systems (AS) cannot be ignored in the research of large-scale communication protocols and architectures. It has been widely recognized that disregarding policy relationships leads to unrealistic routing paths in simulated communication networks and thus to inaccurate conclusions about the investigated problem. Current AS-level topology generators either completely overlook the relationships or make the annotation process inherent in topology generation. We propose a novel algorithm for annotating random graphs. Our approach differs from previous studies in focusing on the annotation process rather than on the topology generation, which enables reuse of the state-of-the-art topology generators. We identify five properties of viable annotations and formulate the problem as a type-of-relationship problem in random graphs (TRR) by analogy with the related problem of inferring AS relationships from measured routing data. We propose an annotation algorithm for solving the TRR problem by taking advantage of the stochastic properties found in the inferred annotations provided by the cooperative association for internet data analysis (CAIDA). The evaluation provides the evidence of high resemblance of our annotations to the measured ones.