Abstract: An approach to inferring relationship between different autonomous systems (AS) from border gateway protocol (BGP) routing tables is proposed. Analyzing BGP input and output routing policies constrained by the AS relationships, an AS path structure is obtained in form of a sequence of AS relationships. The composing rules of AS paths are used to infer AS relationships from the context of the sequence of AS relationships. According to the characteristics of AS path structure as shown in BGP routing tables of different hierarchical ASs, different inference rules are used separately in the relevant BGP routing tables for top-tier ASs and other ASs. The effect due to misconfiguration is considered with several parameters used to infer AS relationships. The algorithm is tested on publicly available BGP routing tables, by which over 80% of the AS relationships could be inferred directly from routing tables for top-tier ASs. A comparison between the results of the ones and another similar algorithm verifies that the algorithm is effective.