Abstract
Efficient geocast routing schemes are needed to transmit messages to mobile networked devices in geographically scoped areas. To design an efficient geocast routing algorithm a comprehensive evaluation of different routing tree approaches is needed. In this paper, we present an analytical study addressing the efficiency of possible routing trees for geocast packets. We evaluate the Shortest Path Tree, Minimum Spanning Tree and a Steiner Heuristic based routing tree for geocast packet distribution on real world networks and random graphs. We compare the results to those for multicast routing for which such evaluations have been performed in the past. Our results show that due to the correlation of geographic distance and network distance in most wired networks, Shortest Path forwarding efficiency can come close to an ideal Steiner Tree. We also identify a correlation between the forwarding efficiency and network characteristics such as the node degree and betweenness. This information could be useful in deciding on a choice of routing method or even help with network design.
| Original language | English |
|---|---|
| Title of host publication | Wired/Wireless Internet Communications |
| Subtitle of host publication | 15th IFIP WG 6.2 International Conference, WWIC 2017, Proceedings |
| Editors | Yevgeni Koucheryavy, Lefteris Mamatas, Ibrahim Matta, Aleksandr Ometov, Panagiotis Papadimitriou |
| Publisher | Springer |
| Pages | 127-142 |
| Number of pages | 16 |
| ISBN (Electronic) | 978-3-319-61382-6 |
| ISBN (Print) | 978-3-319-61381-9 |
| DOIs | |
| Publication status | Published - 2017 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 10372 |
| ISSN (Print) | 0302-9743 |
Fingerprint
Keywords
- Geocast
- Multicast
- Routing
- Shortest path tree
- Steiner tree
Cite this
}
Evaluation of geocast routing trees on random and actual networks. / Meijerink, Berend Jan; Baratchi, Mitra; Heijenk, Geert.
Wired/Wireless Internet Communications: 15th IFIP WG 6.2 International Conference, WWIC 2017, Proceedings. ed. / Yevgeni Koucheryavy; Lefteris Mamatas; Ibrahim Matta; Aleksandr Ometov; Panagiotis Papadimitriou. Springer, 2017. p. 127-142 (Lecture Notes in Computer Science; Vol. 10372).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review
TY - GEN
T1 - Evaluation of geocast routing trees on random and actual networks
AU - Meijerink, Berend Jan
AU - Baratchi, Mitra
AU - Heijenk, Geert
PY - 2017
Y1 - 2017
N2 - Efficient geocast routing schemes are needed to transmit messages to mobile networked devices in geographically scoped areas. To design an efficient geocast routing algorithm a comprehensive evaluation of different routing tree approaches is needed. In this paper, we present an analytical study addressing the efficiency of possible routing trees for geocast packets. We evaluate the Shortest Path Tree, Minimum Spanning Tree and a Steiner Heuristic based routing tree for geocast packet distribution on real world networks and random graphs. We compare the results to those for multicast routing for which such evaluations have been performed in the past. Our results show that due to the correlation of geographic distance and network distance in most wired networks, Shortest Path forwarding efficiency can come close to an ideal Steiner Tree. We also identify a correlation between the forwarding efficiency and network characteristics such as the node degree and betweenness. This information could be useful in deciding on a choice of routing method or even help with network design.
AB - Efficient geocast routing schemes are needed to transmit messages to mobile networked devices in geographically scoped areas. To design an efficient geocast routing algorithm a comprehensive evaluation of different routing tree approaches is needed. In this paper, we present an analytical study addressing the efficiency of possible routing trees for geocast packets. We evaluate the Shortest Path Tree, Minimum Spanning Tree and a Steiner Heuristic based routing tree for geocast packet distribution on real world networks and random graphs. We compare the results to those for multicast routing for which such evaluations have been performed in the past. Our results show that due to the correlation of geographic distance and network distance in most wired networks, Shortest Path forwarding efficiency can come close to an ideal Steiner Tree. We also identify a correlation between the forwarding efficiency and network characteristics such as the node degree and betweenness. This information could be useful in deciding on a choice of routing method or even help with network design.
KW - Geocast
KW - Multicast
KW - Routing
KW - Shortest path tree
KW - Steiner tree
UR - http://www.scopus.com/inward/record.url?scp=85021716548&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-61382-6_11
DO - 10.1007/978-3-319-61382-6_11
M3 - Conference contribution
AN - SCOPUS:85021716548
SN - 978-3-319-61381-9
T3 - Lecture Notes in Computer Science
SP - 127
EP - 142
BT - Wired/Wireless Internet Communications
A2 - Koucheryavy, Yevgeni
A2 - Mamatas, Lefteris
A2 - Matta, Ibrahim
A2 - Ometov, Aleksandr
A2 - Papadimitriou, Panagiotis
PB - Springer
ER -