Loading...
Please wait, while we are loading the content...
Similar Documents
I.: RNG-based searching and broadcasting algorithms over internet graphs and peer-to-peer computing systems (2005)
| Content Provider | CiteSeerX |
|---|---|
| Author | Escalante, Oscar Pérez, Tania Solano, Julio Stojmenovic, Ivan |
| Description | In a broadcasting problem, a message is sent from a source to all the other nodes in the network. Blind flooding is a classical mechanism for broadcasting, where each node retransmits received message to all its neighbors. Despite its important advantages, an increase in the number of requests or the size of the routing area produces communication overheads that limit the scalability of blind flooding, especially in networks with dynamic topologies. In this work we propose a new broadcasting and searching scheme over the Internet based on generalized relative neighborhood graphs (RNG). Messages are forwarded only on RNG links, and a link is in RNG if and only if it is not the ‘longest ’ edge in any triangle. We extend the existing definition of RNG, using geographic distance, by applying more meaningful Internet metrics such as delay. RNG is a sparse connected overlay network which is defined based on local information at each node, which includes distance to each neighbor and distances between neighbors. This new scheme is compared to the existing Flooding and Rumor Mongering (or Gossip) schemes to evaluate its performance. Our parameterless RNG based scheme guarantees delivery to each node with considerably reduced number of messages with respect to flooding, and has comparable amount of message to Rumor Mongering/Gossip scheme that does not guarantee delivery to each node and also uses parameters whose best value depend on underlying network density. 1. |
| File Format | |
| Language | English |
| Publisher Date | 2005-01-01 |
| Publisher Institution | In: The 3rd ACS/IEEE Intl. Conf. on Computer Systems |
| Access Restriction | Open |
| Subject Keyword | Network Density Rng-based Searching Scheme Guarantee Delivery Parameterless Rng Geographic Distance Rumor Mongering Comparable Amount Classical Mechanism Dynamic Topology Meaningful Internet Metric Communication Overhead Rumor Mongering Gossip Scheme Internet Graph Broadcasting Algorithm Important Advantage Blind Flooding New Broadcasting Rng Link Value Depend Local Information Generalized Relative Neighborhood Graph Overlay Network New Scheme Broadcasting Problem |
| Content Type | Text |
| Resource Type | Article |
