Login | Register

New Heuristic for Message Broadcasting in Arbitrary Networks


New Heuristic for Message Broadcasting in Arbitrary Networks

Jimborean, Cosmin (2013) New Heuristic for Message Broadcasting in Arbitrary Networks. Masters thesis, Concordia University.

Text (application/pdf)
Jimborean_MCompSc_F2013.pdf - Accepted Version


Efficient information dissemination in interconnection networks is a key research area because of the major role it plays in the modern interconnected world. A vast number of topics ranging from distributed computing to Internet communication rely on efficient information dissemination. Broadcasting is one of the information dissemination primitives. The minimum broadcast time problem in arbitrary networks has been examined since the 1970s. Finding an optimal broadcasting scheme for any originator in an arbitrary network has been proved to be an NP-Hard problem. In the current thesis, a new heuristic that generates broadcast schemes in arbitrary networks is presented. The heuristic has O(|E|log|V|) time complexity, where V is the set of nodes and E is the set of the links of the network. Computer simulations in some commonly used topologies and network models show that compared to the existing heuristics the new heuristic shows better performance in some network models, and comparable performance in other network models, while having a low complexity similar to the best existing heuristics. Another advantage of the new heuristic is that approximately one half of the vertices receive the message via a shortest path from the broadcast originator, while the rest of the vertices receive the message via a path at most three hops longer.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Jimborean, Cosmin
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:11 September 2013
Thesis Supervisor(s):Harutyunyan, Hovhannes
ID Code:977717
Deposited On:26 Nov 2013 15:34
Last Modified:18 Jan 2018 17:45
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Back to top Back to top