In unstructured networks, gossiping protocols prescribe that a message, received by a node, is not forwarded with certainty to all its neighbors (as happens in flooding protocols), but only with some finite probability. Typically, in order to make the protocol adaptive, the packet forwarding probability is computed on the fly, as a function of the current node's degree, taken as an indicator of the node's capability of propagating information. This approach improves over flooding protocols, by reducing the traffic overhead, however it is plagued by a problem called early gossip termination, which occurs when the information propagation stops, before the message has reached all the intended target nodes. In the present work, we argue that early gossip termination takes place because the node degree is an inaccurate estimator of the information propagation capability of the node. Specifically: in those cases where this capability happens to be overestimated, the forwarding probability gets set to an insufficient value, which causes information propagation to fade out too early. We propose an approach relying on two interrelated prescriptions, which, being based on the local topological structure of the network, help in better quantifying the information propagation capability of a node. The first prescription consists in using, in place of the actual node degree, an effective node degree, defined on the basis of the nearest neighbors' degree information. The second prescription consists in taking into account the node clustering coefficient to identify special topological situations, which deserve specific treatment. We validated our approach by simulation, using ns2 in several operational scenarios: the results show that the approach can yield significant performance improvements.
Improving gossiping performance by means of local topology information / D. Kifle, G. Gianini, M. Libsie - In: MEDES '15 : proceedingsPrima edizione. - New York : ACM, 2015. - ISBN 9781450334808. - pp. 142-147 (( Intervento presentato al 7. convegno International Conference on Management of computational and collective intElligence in Digital EcoSystems tenutosi a Caraguatatuba nel 2015 [10.1145/2857218.2857252].
Improving gossiping performance by means of local topology information
G. GianiniSecondo
;
2015
Abstract
In unstructured networks, gossiping protocols prescribe that a message, received by a node, is not forwarded with certainty to all its neighbors (as happens in flooding protocols), but only with some finite probability. Typically, in order to make the protocol adaptive, the packet forwarding probability is computed on the fly, as a function of the current node's degree, taken as an indicator of the node's capability of propagating information. This approach improves over flooding protocols, by reducing the traffic overhead, however it is plagued by a problem called early gossip termination, which occurs when the information propagation stops, before the message has reached all the intended target nodes. In the present work, we argue that early gossip termination takes place because the node degree is an inaccurate estimator of the information propagation capability of the node. Specifically: in those cases where this capability happens to be overestimated, the forwarding probability gets set to an insufficient value, which causes information propagation to fade out too early. We propose an approach relying on two interrelated prescriptions, which, being based on the local topological structure of the network, help in better quantifying the information propagation capability of a node. The first prescription consists in using, in place of the actual node degree, an effective node degree, defined on the basis of the nearest neighbors' degree information. The second prescription consists in taking into account the node clustering coefficient to identify special topological situations, which deserve specific treatment. We validated our approach by simulation, using ns2 in several operational scenarios: the results show that the approach can yield significant performance improvements.File | Dimensione | Formato | |
---|---|---|---|
2015 - Dawit Kifle - Improving Gossiping performance by means of local topology information - PUBLISHED VERSION.pdf
accesso riservato
Descrizione: Articolo principale
Tipologia:
Publisher's version/PDF
Dimensione
465.48 kB
Formato
Adobe PDF
|
465.48 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.