A Dynamic Random Graph Model for Diameter-Constrained Topologies in Networked Systems

Luigi Alfredo Grieco (1) , Mahdi Ben Alaya (2) , Thierry Monteil (2) , Khalil Drira (2)

1 Polytechnic University of Bari / Politecnico di Bari
2 LAAS-SARA - Équipe Services et Architectures pour Réseaux Avancés

Random graphs have been widely investigated in literature because of their relevance to many scientific domains. In this brief, the attention is focused on diameter constrained random graphs, useful to analyze unstructured overlays for delay bounded network applications and systems. To this end, a general process of arrivals is considered to describe the sequence of vertex couples (i.e., node couples) among which a path composed of no more than D edges (i.e., links) has to be established. Accordingly, a topology formation mechanism M is formulated, expressing the rules that drive the addition of new edges, obeying to the constraint on the maximum diameter D. Third, using graph theoretic arguments, an original discrete time model is proposed that describes the evolution of the average network degree (i.e., the number of edges per node) subject to M and D. Fourth, the model is successfully validated using computer simulations in a wide range of scenarios (with up to 2 16 nodes). Finally, concrete examples are provided to illustrate useful applications of the proposed approach, also in the presence of link failures.

Mots clés: Networks; Overlay; Graph theory; Topology

Domaines: Informatique [cs]

Luigi Alfredo Grieco, Mahdi Ben Alaya, Thierry Monteil, Khalil Drira. A Dynamic Random Graph Model for Diameter-Constrained Topologies in Networked Systems. IEEE Transactions on Circuits and Systems II: Express Briefs, 2014, 61 (12), pp.882-886. ⟨10.1109/TCSII.2014.2362676⟩. ⟨hal-01228346⟩