Evaluation of geocast routing trees on random and actual networks

Berend Jan Meijerink, Mitra Baratchi, Geert Heijenk

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-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 languageEnglish
    Title of host publicationWired/Wireless Internet Communications
    Subtitle of host publication15th IFIP WG 6.2 International Conference, WWIC 2017, Proceedings
    EditorsYevgeni Koucheryavy, Lefteris Mamatas, Ibrahim Matta, Aleksandr Ometov, Panagiotis Papadimitriou
    PublisherSpringer
    Pages127-142
    Number of pages16
    ISBN (Electronic)978-3-319-61382-6
    ISBN (Print)978-3-319-61381-9
    DOIs
    Publication statusPublished - 2017

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume10372
    ISSN (Print)0302-9743

    Fingerprint

    Routing
    Evaluation
    Routing algorithms
    Shortest Path Tree
    Multicast Routing
    Steiner Tree
    Comprehensive Evaluation
    Betweenness
    Minimum Spanning Tree
    Routing Algorithm
    Network Design
    Random Graphs
    Shortest path
    Efficient Algorithms
    Heuristics
    Evaluate
    Vertex of a graph

    Keywords

    • Geocast
    • Multicast
    • Routing
    • Shortest path tree
    • Steiner tree

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

    }

    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. 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 proceedingConference contributionAcademicpeer-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 -

    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). https://doi.org/10.1007/978-3-319-61382-6_11