Evaluation of geocast routing trees on random and actual networks

Berend Jan Meijerink; Mitra Baratchi; Geert Heijenk

doi:10.1007/978-3-319-61382-6_11

Evaluation of geocast routing trees on random and actual networks

Berend Jan Meijerink, Mitra Baratchi, Geert Heijenk

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

1 Citation (Scopus)

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	https://doi.org/10.1007/978-3-319-61382-6_11
Publication status	Published - 2017
Event	15th International Conference on Wired/Wireless Internet Communications, WWIC 2017 - St. Petersburg, Russian Federation Duration: 21 Jun 2017 → 23 Jun 2017 Conference number: 15

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	10372
ISSN (Print)	0302-9743

Conference

Conference	15th International Conference on Wired/Wireless Internet Communications, WWIC 2017
Abbreviated title	WWIC 2017
Country/Territory	Russian Federation
City	St. Petersburg
Period	21/06/17 → 23/06/17

Keywords

Geocast
Multicast
Routing
Shortest path tree
Steiner tree

Access to Document

10.1007/978-3-319-61382-6_11

Cite this

Meijerink, B. J., Baratchi, M., & Heijenk, G. (2017). Evaluation of geocast routing trees on random and actual networks. In Y. Koucheryavy, L. Mamatas, I. Matta, A. Ometov, & P. Papadimitriou (Eds.), Wired/Wireless Internet Communications: 15th IFIP WG 6.2 International Conference, WWIC 2017, Proceedings (pp. 127-142). (Lecture Notes in Computer Science; Vol. 10372). Springer. https://doi.org/10.1007/978-3-319-61382-6_11

Meijerink, Berend Jan ; Baratchi, Mitra ; Heijenk, Geert. / Evaluation of geocast routing trees on random and actual networks. Wired/Wireless Internet Communications: 15th IFIP WG 6.2 International Conference, WWIC 2017, Proceedings. editor / Yevgeni Koucheryavy ; Lefteris Mamatas ; Ibrahim Matta ; Aleksandr Ometov ; Panagiotis Papadimitriou. Springer, 2017. pp. 127-142 (Lecture Notes in Computer Science).

@inproceedings{369bf7a5ccd9491ca8fc3480becb6a74,

title = "Evaluation of geocast routing trees on random and actual networks",

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.",

keywords = "Geocast, Multicast, Routing, Shortest path tree, Steiner tree",

author = "Meijerink, {Berend Jan} and Mitra Baratchi and Geert Heijenk",

year = "2017",

doi = "10.1007/978-3-319-61382-6_11",

language = "English",

isbn = "978-3-319-61381-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "127--142",

editor = "Yevgeni Koucheryavy and Lefteris Mamatas and Ibrahim Matta and Aleksandr Ometov and Panagiotis Papadimitriou",

booktitle = "Wired/Wireless Internet Communications",

address = "Germany",

note = "15th International Conference on Wired/Wireless Internet Communications, WWIC 2017, WWIC 2017 ; Conference date: 21-06-2017 Through 23-06-2017",

}

Meijerink, BJ, Baratchi, M & Heijenk, G 2017, Evaluation of geocast routing trees on random and actual networks. in Y Koucheryavy, L Mamatas, I Matta, A Ometov & P Papadimitriou (eds), Wired/Wireless Internet Communications: 15th IFIP WG 6.2 International Conference, WWIC 2017, Proceedings. Lecture Notes in Computer Science, vol. 10372, Springer, pp. 127-142, 15th International Conference on Wired/Wireless Internet Communications, WWIC 2017, St. Petersburg, Russian Federation, 21/06/17. https://doi.org/10.1007/978-3-319-61382-6_11

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

N1 - Conference code: 15

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

T2 - 15th International Conference on Wired/Wireless Internet Communications, WWIC 2017

Y2 - 21 June 2017 through 23 June 2017

ER -

Meijerink BJ, Baratchi M, Heijenk G. Evaluation of geocast routing trees on random and actual networks. In Koucheryavy Y, Mamatas L, Matta I, Ometov A, Papadimitriou P, editors, Wired/Wireless Internet Communications: 15th IFIP WG 6.2 International Conference, WWIC 2017, Proceedings. Springer. 2017. p. 127-142. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-61382-6_11

Evaluation of geocast routing trees on random and actual networks

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this