Random graphs have been widely investigated in the literature because of their relevance to many scientific domains. In this brief, the attention is focused on diameter-constrained random graphs, which are useful in analyzing unstructured overlays for delay-bounded network applications and systems. To this end, a general process of arrivals is considered, which describes 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, which describes the evolution of the average network degree (i.e., the average 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 216 nodes). Finally, concrete examples are provided to illustrate useful applications of the proposed approach, also in the presence of link failures.

A Dynamic Random Graph Model for Diameter-Constrained Topologies in Networked Systems / Grieco, Luigi Alfredo; Alaya, M. B.; Monteil, T.; Drira, K.. - In: IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS. II, EXPRESS BRIEFS. - ISSN 1549-7747. - 61:12(2014), pp. 982-986. [10.1109/TCSII.2014.2362676]

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

GRIECO, Luigi Alfredo;
2014-01-01

Abstract

Random graphs have been widely investigated in the literature because of their relevance to many scientific domains. In this brief, the attention is focused on diameter-constrained random graphs, which are useful in analyzing unstructured overlays for delay-bounded network applications and systems. To this end, a general process of arrivals is considered, which describes 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, which describes the evolution of the average network degree (i.e., the average 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 216 nodes). Finally, concrete examples are provided to illustrate useful applications of the proposed approach, also in the presence of link failures.
2014
A Dynamic Random Graph Model for Diameter-Constrained Topologies in Networked Systems / Grieco, Luigi Alfredo; Alaya, M. B.; Monteil, T.; Drira, K.. - In: IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS. II, EXPRESS BRIEFS. - ISSN 1549-7747. - 61:12(2014), pp. 982-986. [10.1109/TCSII.2014.2362676]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11589/4756
Citazioni
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact