skip to main content
10.4108/ICST.SIMUTOOLS2009.5672guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
research-article
Free access

Simulation of scale-free networks

Published: 02 March 2009 Publication History

Abstract

In this paper, we present a new simulation tool for scale-free networks composed of a high number of nodes. The tool, based on discrete-event simulation, enables the definition of scale-free networks composed of heterogeneous nodes and complex application-level protocols. To satisfy the performance and scalability requirements, the simulator supports both sequential (i.e. monolithic) and parallel/distributed (i.e. PADS) approaches. Furthermore, appropriate mechanisms for the communication overhead-reduction are implemented. To demonstrate the efficiency of the tool, we experiment with gossip protocols on top of scale-free networks generated by our simulator. Results of the simulations demonstrate the feasibility of our approach. The proposed tool is able to generate and manage large scale-free networks composed of thousands of nodes interacting following real-world dissemination protocols.

References

[1]
R. Albert, H. Jeong, and A.-L. Barabási. Error and attack tolerance of complex networks. Nature, 406, July 2000.
[2]
ARTÌS: Advanced RTI System Homepage. http://pads.cs.unibo.it, 2009.
[3]
A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286, 1999.
[4]
A.-L. Barabási, R. Albert, and H. Jeong. Scale-free characteristics of random networks: the topology of the world-wide web. Physica A: Statistical Mechanics and its Applications, 281(1-4), Jun 2000.
[5]
L. Bononi, M. Bracuto, G. D'Angelo, and L. Donatiello. A new adaptive middleware for parallel and distributed simulation of dynamically interacting systems. In DS-RT '04: Proc. of the 8th IEEE International Symposium on Distributed Simulation and Real-Time Applications. IEEE, 2004.
[6]
L. Bononi, M. Bracuto, G. D'Angelo, and L. Donatiello. Performance analysis of a parallel and distributed simulation framework for large scale wireless systems. In MSWiM '04: Proc. of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems. ACM, 2004.
[7]
L. Bononi, M. Bracuto, G. D'Angelo, and L. Donatiello. Exploring the effects of Hyper-Threading on parallel simulation. In DS-RT 06: Distributed Simulation and Real-Time Applications, IEEE International Symposium on. IEEE, 2006.
[8]
L. Bononi, G. D'Angelo, and L. Donatiello. HLA-based adaptive distributed simulation of wireless mobile systems. In Proc. 17th ACM/IEEE/SCS Workshop on Parallel and Distributed Simulation. IEEE Press, 2003.
[9]
A. Boukerche and S. Das. Dynamic load balancing strategies for conservative parallel simulations. In PADS '97: Proc. of the eleventh workshop on Parallel and distributed simulation. IEEE, 1997.
[10]
A. Brayner and R. Menezes. Balancing energy consumption and memory usage in sensor data processing. In SAC '07: Proc. of the 2007 ACM symposium on Applied computing, New York, NY, USA, 2007. ACM.
[11]
A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web. Computer Networks, 33(1), June 2000.
[12]
W. Cai, S. Turner, and B. Gan. Hierarchical federations: an architecture for information hiding. Parallel and Distributed Simulation, 2001. Proceedings. 15th Workship on, 2001.
[13]
R. Cohen, S. Havlin, and D. Ben-avraham. Structural properties of scale-free networks. In In Handbook of Graphs and Networks. Wiley, 2003.
[14]
E. Deelman and B. Szymanski. Dynamic load balancing in parallel discrete event simulation for spatially explicit problems. SIGSIM Simul. Dig., 28(1), 1998.
[15]
R. Dobrescu, S. Taralunga, and S. Mocanu. Web traffic simulation with scale-free network models. In AIC'07: Proc. of the 7th Conference on 7th WSEAS International Conference on Applied Informatics and Communications. WSEAS, 2007.
[16]
A. Fabbri and A. Boukerche. Partitioning parallel simulation of wireless networks. In Proc. of Winter Simulation Conference. IEEE Press, 2000.
[17]
M. Faloutsos, P. Faloutsos, and C. Faloutsos. On power-law relationships of the Internet topology. SIGCOMM, Aug-Sept. 1999.
[18]
R. Fujimoto. Parallel and Distributed Simulation Systems. Wiley & Sons, 2000.
[19]
G. D'Angelo and M. Bracuto. Distributed simulation of large scale and detailed models. To appear, International Journal of Simulation and Process Modelling (IJSPM), 2009.
[20]
B. Gan, Y. Low, S. Jain, S. Turner, W. Cai, W. Hsu, and S. Huang. Load balancing for conservative simulation on shared memory multiprocessor systems. In PADS '00: Proc. of the fourteenth workshop on Parallel and distributed simulation. IEEE, 2000.
[21]
B. Garbinato, D. Rochat, and M. Tomassini. Impact of scale-free topologies on gossiping in ad hoc networks. In NCA. IEEE Computer Society, 2007.
[22]
Hyper-Threading Technology. http://www.intel.com/technology/platform-technology/hyper-threading/index.htm, 2009.
[23]
IEEE 1516 Standard, Modeling and Simulation (M&S) High Level Architecture (HLA), 2000.
[24]
R. J. Short and L. Kleinrock. Mobile wireless network system simulation. Wireless Networks, 1(4), 1995.
[25]
D. Jefferson. Virtual time. ACM Transactions Program. Lang. Syst., 7(3), 1985.
[26]
M. Jelasity, A. Montresor, and O. Babaoglu. Gossip-based aggregation in large dynamic networks. ACM Transaction Computer Systems, 23(3), 2005.
[27]
H. Jeong, S. Mason, A.-L. Barabási, and Z. Oltvai. Lethality and centrality in protein networks. Nature, 411, 2001.
[28]
R. K. Kincaid and N. M. Alexandrov. Scale-free networks: A discrete event simulation approach. In International Conference on Computational Science (1), 2005.
[29]
B. Kumova. Dynamically adaptive partition-based data distribution management. In PADS '05: Proc. of the 19th Workshop on Principles of Advanced and Distributed Simulation. IEEE, 2005.
[30]
F. Liljeros, C. Edling, L. Amaral, H. Stanley, and Y. Aberg. The web of human sexual contacts. Nature, 411, 2001.
[31]
B. Logan and G. Theodoropoulos. The distributed simulation of multi-agent systems. In Proc. of the IEEE, 2001.
[32]
J. Misra. Distributed discrete event simulation. ACM Computing Surveys, 18(1), 1986.
[33]
M. E. J. Newman. The structure and function of complex networks. SIAM Review, 45, 2003.
[34]
P. Peschlow, T. Honecker, and P. Martini. A flexible dynamic partitioning algorithm for optimistic distributed simulation. In PADS '07: Proc. of the 21st International Workshop on Principles of Advanced and Distributed Simulation. IEEE, 2007.
[35]
D. J. Price. Networks of scientific papers. Science, 149(3683), July 1965.
[36]
G. Riley and M. Ammar. Simulating large networks: How big is big enough? In Proc. of First International Conference on Grand Challenges for Modeling and Simulation, Jan 2002.
[37]
R. L. Bagrodia and R. Meyer. PARSEC: A parallel simulation environment for complex system. IEEE Computer, 31(10), 1998.
[38]
M. Shanaker, R. Padman, and W. Kelton. Efficient distributed simulation through dynamic load balancing. IIE Transactions, 33(3), 2001.
[39]
T. Som and R. Sargent. Model structure and load balancing in optimistic parallel discrete event simulation. In PADS '00: Proc. of the fourteenth workshop on Parallel and distributed simulation. IEEE, 2000.
[40]
B. K. Szymanski, A. Saifee, A. Sastry, Y. Liu, and K. Madnani. Genesis: a system for large-scale parallel network simulation. In PADS '02: Proc. of the sixteenth workshop on Parallel and distributed simulation. IEEE, 2002.
[41]
S. Verma and W. T. Ooi. Controlling gossip protocol infection pattern using adaptive fanout. In ICDCS '05: Proc. of the 25th IEEE International Conference on Distributed Computing Systems. IEEE, 2005.

Cited By

View all
  • (2019)Efficient Parallel Simulation over Large-scale Social Contact NetworksACM Transactions on Modeling and Computer Simulation10.1145/326574929:2(1-25)Online publication date: 18-Apr-2019
  • (2017)Efficient Parallel Simulation over Social Contact Network with Skewed Degree DistributionProceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3064911.3064934(65-75)Online publication date: 16-May-2017
  • (2016)Research Challenges in Parallel and Distributed SimulationACM Transactions on Modeling and Computer Simulation10.1145/286657726:4(1-29)Online publication date: 2-May-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image Guide Proceedings
Simutools '09: Proceedings of the 2nd International Conference on Simulation Tools and Techniques
March 2009
720 pages
ISBN:9789639799455

Sponsors

  • Create-Net
  • ICST

Publisher

ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering)

Brussels, Belgium

Publication History

Published: 02 March 2009

Author Tags

  1. parallel and distributed simulation
  2. performance evaluation
  3. scale-free networks
  4. simulation

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)59
  • Downloads (Last 6 weeks)10
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Efficient Parallel Simulation over Large-scale Social Contact NetworksACM Transactions on Modeling and Computer Simulation10.1145/326574929:2(1-25)Online publication date: 18-Apr-2019
  • (2017)Efficient Parallel Simulation over Social Contact Network with Skewed Degree DistributionProceedings of the 2017 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/3064911.3064934(65-75)Online publication date: 16-May-2017
  • (2016)Research Challenges in Parallel and Distributed SimulationACM Transactions on Modeling and Computer Simulation10.1145/286657726:4(1-29)Online publication date: 2-May-2016
  • (2016)Link Partitioning in Parallel Simulation of Scale-Free NetworksProceedings of the 20th International Symposium on Distributed Simulation and Real-Time Applications10.1109/DS-RT.2016.17(77-84)Online publication date: 21-Sep-2016
  • (2016)Fault-Tolerant Adaptive Parallel and Distributed SimulationProceedings of the 20th International Symposium on Distributed Simulation and Real-Time Applications10.1109/DS-RT.2016.11(37-44)Online publication date: 21-Sep-2016
  • (2014)Efficient network generation under general preferential attachmentProceedings of the 23rd International Conference on World Wide Web10.1145/2567948.2579357(695-700)Online publication date: 7-Apr-2014
  • (2013)A practical simulation method for social networksProceedings of the First Australasian Web Conference - Volume 14410.5555/2527208.2527212(27-34)Online publication date: 29-Jan-2013
  • (2013)On the parallel simulation of scale-free networksProceedings of the 1st ACM SIGSIM Conference on Principles of Advanced Discrete Simulation10.1145/2486092.2486115(179-188)Online publication date: 19-May-2013
  • (2013)Shaping opportunistic networksComputer Communications10.1016/j.comcom.2012.12.00636:5(481-503)Online publication date: 1-Mar-2013
  • (2012)A contact-network-based simulation model for evaluating interventions under "what-if" scenarios in epidemicProceedings of the Winter Simulation Conference10.5555/2429759.2430298(1-12)Online publication date: 9-Dec-2012
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media