On Cycles in AS Relationships

摘要

Several users of our AS relationship inference data [1], released with [2], asked us why it contained AS relationship cycles, e.g., cases where AS A is a provider of AS B, B is a provider of C, and C is a provider of A, or other cycle types. Having been answering these questions in private communications, we have eventually decided to write down our answers here for future reference.rnFormally, the heuristics in [2] do not produce acyclic relationships because neither do the techniques that [2] is based on [3, 4, 5], and because we did not try to impose any no-cycle constraints that can certainly be enforced [6]. Below we explain why we did not try to do that, and thus behaved somewhat counter-intuitive.rnFirst, we have to emphasize that AS relationship cycles by no means imply or induce routing or traffic forwarding loops, since the BGP's routing loop avoidance mechanism, i.e., AS path checking, does not depend on any AS relationships. Another problem with BGP causes some confusion sometimes. BGP can diverge due to policy conflicts [7], where policy refers to a ranking of prefixes that can be used to reach a destination. As AS relationships determine export policies, they may also influence prefix rankings, e.g., an AS typically prefers to reach a destination via its customer, then peer, then provider. However, this influence by no means leads to BGP divergence, which is a separate problem with BGP that can only appear in the presence of non-shortest-path routing and conflicting path selection policies. AS relationship cycles present or not, the default BGP path selection mechanism that chooses shortest paths, or many other possible safe rankings [7] result in stable and loop-free routing.