NDLI: BC-GA: A Graph Partitioning Algorithm for Parallel Simulation of Internet Applications

Content Provider	IEEE Xplore Digital Library
Author	Siming Lin Xueqi Cheng
Copyright Year	2008
Description	Author affiliation: Chinese Acad. of Sci., Beijing (Siming Lin; Xueqi Cheng)
Abstract	Static task mapping of parallel simulation is studied as a graph partitioning problem (GPP). However, the existing algorithms are primarily designed for partitioning finite element meshes or random graphs which are essentially different from the Internet-like topologies used in the field of large scale network simulation. In this paper, we present a new genetic algorithm, BC-GA, for effectively partitioning Internet-like topologies based on boundary crossing, a quite different principle inspired by the analysis of characteristic of the Internet topology and its related solutions. All operations of this algorithm are novel, such as pizza-cutting and autogamy propagation. We test this algorithm on a large extent of graphs, including the snapshots of the real AS-level Internet, the topologies produced by the Internet model generator and many traditional benchmark graphs. The experiment shows that our algorithm can outperform traditional approaches on partitioning Internet-like topologies and it is also better than or comparable to those on traditional GPP. The experiment also shows that a genetic algorithm can converge quickly if the domain knowledge is fitly combined.
Starting Page	358
Ending Page	365
File Size	398956
Page Count	8
File Format	PDF
ISBN	9780769530895
ISSN	10666192
DOI	10.1109/PDP.2008.26
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-02-13
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Partitioning algorithms Internet Network topology Genetic algorithms IP networks Algorithm design and analysis Finite element methods Computational modeling Benchmark testing Joining processes genetic algorithms network simulation scale-free network partitioning bisection multilevel
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Graph partitioning with the Party library: helpful-sets in practice

A Topology Partition Algorithm Based on Link Coarsening in Parallel Network Simulation

Fraud Detection on Large Scale Social Networks

Clustering network simulation: graph partitioning approach

Parallel heuristic search in multilevel graph partitioning

Network partitioning and GA heuristic crossover for NoC application mapping

Reaching of topology partition for parallel network simulation

A PROBE-Based Heuristic for Graph Partitioning

Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs

BC-GA: A Graph Partitioning Algorithm for Parallel Simulation of Internet Applications

Similar Documents

Graph partitioning with the Party library: helpful-sets in practice

A Topology Partition Algorithm Based on Link Coarsening in Parallel Network Simulation

Fraud Detection on Large Scale Social Networks

Clustering network simulation: graph partitioning approach

Parallel heuristic search in multilevel graph partitioning

Network partitioning and GA heuristic crossover for NoC application mapping

Reaching of topology partition for parallel network simulation

A PROBE-Based Heuristic for Graph Partitioning

Parallel Multilevel k-way Partitioning Scheme for Irregular Graphs

BC-GA: A Graph Partitioning Algorithm for Parallel Simulation of Internet Applications