Understanding Edge Connectivity in the Internet through Core Decomposition

ALVAREZ HAMELIN, JOSÉ IGNACIO; BEIRÓ, MARIANO G.; BUSCH, JORGE R.

Internet Mathematics

Taylor & Francis

Lugar: London; Año: 2011 vol. 7 p. 45 - 66

1542-7951

The Internet is a complex network composed of several networks: the autonomous systems. Each of them is designed with the aim of transporting informationefficiently. This information is carried over routes, which are discovered by routingprotocols, such as the border gateway protocol (BGP). The protocols may find possible paths between nodes whenever they exist, or even find paths satisfying specificconstraints, e.g., a certain quality of service (QoS). Here, we study connectivity as anetwork attribute related to both situations; we provide a formal lower bound to itbased on core decomposition and low-complexity algorithms to find it. Then we apply these algorithms to analyze maps obtained from the prominent Internet mappingprojects, and use the LaNet-vi open-source software for their visualization.