On power law reachability analysis at an autonomous system granularity

Abstract

The internet consists of rapidly increasing number of Autonomous Systems(AS) interconnected. Interdomain routing in Internet is coordinated by the Border Gateway Protocol. Which routing table has been growing dramatically. This situation lead us to search a new routing scheme able to support the new requirements. Since each AS administers its reachability information via routing policies, the new routing scheme must consider the reachability of the nodes into the network. These routing policies are constrained by the contractual commercial agreements between ASes. This implies that the relationships among Autonomous System granularity (i.e. Customer-Provider) are an important aspect of Internet structure and affects the reachability of the nodes in the network topology. In this work, we explore the relationship between the times between topology changes in the AS-Level and the reachability over a network based in a customer-provider relationship to characterize the reachability process. We begin with a network generator based in the nodes at 1 hop distance, followed by a routing algorithm to find the shortest path to all available destinations from a particular origin. Afterwards, we run a simulation modifying the reachability state of the nodes over time. We shown that the decrease of reachable Autonomous Systems between topology changes in the nodes obeys a power law distribution that is consequence of the power law observed in the times between topology changes at the interdomain level.