Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2020 Nov 9;15(11):e0240100.
doi: 10.1371/journal.pone.0240100. eCollection 2020.

Generation of 2-mode scale-free graphs for link-level internet topology modeling

Khalid Bakhshaliyev  1 , Mehmet Hadi Gunes  2
Affiliations

Generation of 2-mode scale-free graphs for link-level internet topology modeling

Khalid Bakhshaliyev et al. PLoS One. .

Abstract

Comprehensive analysis that aims to understand the topology of real-world networks and the development of algorithms that replicate their characteristics has been significant research issues. Although the accuracy of newly developed network protocols or algorithms does not depend on the underlying topology, the performance generally depends on the topology. As a result, network practitioners have concentrated on generating representative synthetic topologies and utilize them to investigate the performance of their design in simulation or emulation environments. Network generators typically represent the Internet topology as a graph composed of point-to-point links. In this study, we discuss the implications of multi-access links on the synthetic network generation and modeling of the networks as bi-partite graphs to represent both subnetworks and routers. We then analyze the characteristics of sampled Internet topology data sets from backbone Autonomous Systems (AS) and observe that in addition to the commonly recognized power-law node degree distribution, the subnetwork size and the router interface distributions often exhibit power-law characteristics. We introduce a SubNetwork Generator (SubNetG) topology generation approach that incorporates the observed measurements to produce bipartite network topologies. In particular, generated topologies capture the 2-mode relation between the layer-2 (i.e., the subnetwork and interface distributions) and the layer-3 (i.e., the degree distribution) that is missing from the current network generators that produce 1-mode graphs. The SubNetG source code and experimental data is available at https://github.com/netml/sonet.

PubMed Disclaimer

Conflict of interest statement

The authors have declared that no competing interests exist.

Figures

Fig 1
Fig 1. Sample topologies.
Fig 2
Fig 2. Interface, subnetwork and degree distribution of sample topologies.
Fig 3
Fig 3. Sample interface distributions with power-laws of 2, 2.5, 3.
Fig 4
Fig 4. Sample subnetwork distributions with power-laws of 2, 2.5, 3.
Fig 5
Fig 5. Change in the power law exponent with a 40% cut-off.
Fig 6
Fig 6. Sample bipartite graph.
Fig 7
Fig 7. Correlation among the distributions.
Fig 8
Fig 8. Feasible αI and αS exponents for a connected network.
Fig 9
Fig 9. Iteration of algorithm 2 on a sample network.
Fig 10
Fig 10. Multi-access vs. point-to-point links.
Fig 11
Fig 11. Clique size distributions of Internet2.
Fig 12
Fig 12. Clique Size Distribution of the AS 8928.
Fig 13
Fig 13. Interface distribution of AS 1221, AS 8928 and AS 2828.
Fig 14
Fig 14. Subnetwork distribution of AS 1221, AS 8928 and AS 2828.
Fig 15
Fig 15. Degree distribution of AS 1221, AS 8928 and AS 2828.
Fig 16
Fig 16. Distributions of a synthetic network based on AS 1221.
Fig 17
Fig 17. Distributions of a synthetic network based on AS 2828.
Fig 18
Fig 18. Distributions of a synthetic network based on AS 8929.
Fig 19
Fig 19. Interface, subnetwork and degree distribution of generated networks with 1K, 10K, 100K and 1M nodes.
See this image and copyright information in PMC

References

    1. Pastor-Satorras R., Vespignani A., Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge, Cambridge University Press, 2004. 10.1017/CBO9780511610905 - DOI
    1. Newman M., Networks: An Introduction, Oxford University Press, Inc, 2010
    1. Gunes M. H., Bilir S., Sarac K., Korkmaz T., A measurement study on overhead distribution of value-added internet services, Computer Networks, Volume 51, Issue 14, 2007, Pages 4153–4173. 10.1016/j.comnet.2007.05.001 - DOI
    1. L. Cheng, N.C. Hutchinson, M. R. Ito, RealNet: A Topology Generator Based on Real Internet Topology, 22nd International Conference on Advanced Information Networking and Applications—Workshops (AINA workshops 2008), Okinawa, 2008, pp. 526-532. 10.1109/WAINA.2008.66 - DOI
    1. N. Hidaka, S. Arakawa, M. Murata, A Modeling Method for ISP Topologies Based on Network-Cost Optimization, Fourth International Conference on Autonomic and Autonomous Systems (ICAS’08), Gosier, 2008, pp. 169-174. 10.1109/ICAS.2008.7 - DOI

Publication types