Article (Scientific journals)
Towards a bipartite graph modeling of the internet topology
Tarissan, Fabien; Quoitin, Bruno; Mérindol, Pascal et al.
2013In Computer Networks, 57 (11), p. 2331-2347
Peer Reviewed verified by ORBi
 

Files


Full Text
COMNET.pdf
Author preprint (1.73 MB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Network Topology; Measurement; Bipartite Modeling; mrinfo; Topology Generator
Abstract :
[en] Modeling the properties of the Internet topology aims at generating large scale artificial IP networks that mimic properties of real ones for simulation purposes. Current models typically consider the Internet as a simple graph where edges are point-to-point connections between routers. This approach does not take into account point-to-multipoint connections that exist at lower layers in the network, e.g. layer-2 clouds, such as Ethernet switches or MPLS networks. Instead, such physical point-to-multipoint connections are modeled as several logical IP level point-to-point connections. In this paper, we rely on recent developments in topology discovery based on IGMP probing that allows for revealing part of the network’s layer-2 structure. We take advantage of this additional knowledge for proposing an Internet model based on bipartite graphs considering both point-to-point and point-to-multipoint connections. Our model remains simple: it only takes as input the node degree sequence for both layer-2 and layer-3 nodes, randomly generates a bipartite graph respecting those distributions, and then derives the corresponding layer-3 topology. We show that, despite the simplicity of our model, realistic network properties, such as high local density, emerge naturally. This is in contrast with the now common belief that such properties can only appear with more intricate models or if explicitly injected in random models. Besides, we also provide evidences of how the analysis performed at the bipartite level might shed light on important properties of the real network structure. Finally, we propose and evaluate a bipartite graph generator based on our model that only takes two synthetic node degree distributions as input.
Disciplines :
Computer science
Author, co-author :
Tarissan, Fabien
Quoitin, Bruno
Mérindol, Pascal
Donnet, Benoît  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Algorithmique des grands systèmes
Pansiot, Jean-Jacques
Latapy, Matthieu
Language :
English
Title :
Towards a bipartite graph modeling of the internet topology
Publication date :
August 2013
Journal title :
Computer Networks
ISSN :
1389-1286
eISSN :
1872-7069
Publisher :
Elsevier Science, Amsterdam, Netherlands
Volume :
57
Issue :
11
Pages :
2331-2347
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 02 July 2013

Statistics


Number of views
174 (13 by ULiège)
Number of downloads
517 (7 by ULiège)

Scopus citations®
 
12
Scopus citations®
without self-citations
7
OpenCitations
 
14

Bibliography


Similar publications



Contact ORBi