Treffer: Understanding edge-connectivity in the Internet through core-decomposition
Title:
Understanding edge-connectivity in the Internet through core-decomposition
Contributors:
Facultad de Ingeniería [Buenos Aires] (FIUBA), Universidad de Buenos Aires [Buenos Aires] (UBA), UBACyT 2008-2010 (I413)
Source:
Internet Mathematics. 7(1):45-66
Publisher Information:
CCSD; Taylor & Francis, 2011.
Publication Year:
2011
Collection:
collection:TDS-MACS
Subject Terms:
connectivity, core-decomposition, algorithm, visualization, ACM: G.: Mathematics of Computing, G.2: DISCRETE MATHEMATICS, G.2.2: Graph Theory, G.2.2.3: Network problems, G.2.2.0: Graph algorithms, [INFO.INFO-DM]Computer Science [cs], Discrete Mathematics [cs.DM], [INFO.INFO-NI]Computer Science [cs], Networking and Internet Architecture [cs.NI]
Original Identifier:
ARXIV: 0912.1424
HAL:
HAL:
Document Type:
Zeitschrift
article<br />Journal articles
Language:
English
ISSN:
1542-7951
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/0912.1424; info:eu-repo/semantics/altIdentifier/doi/10.1080/15427951.2011.560786
DOI:
10.1080/15427951.2011.560786
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00439597v1
Database:
HAL
Weitere Informationen
Internet is a complex network composed by several networks: the Autonomous Systems, each one designed to transport information efficiently. Routing protocols aim to find paths between nodes whenever it is possible (i.e., the network is not partitioned), or to find paths verifying specific constraints (e.g., a certain QoS is required). As connectivity is a measure related to both of them (partitions and selected paths) this work provides a formal lower bound to it based on core-decomposition, under certain conditions, and low complexity algorithms to find it. We apply them to analyze maps obtained from the prominent Internet mapping projects, using the LaNet-vi open-source software for its visualization.