Design & analysis of a distributed routing algorithm towards Internet-wide geocast

Bernd Meijerink*, Mitra Baratchi, Geert Heijenk

*Corresponding author for this work

    Research output: Contribution to journalArticleAcademicpeer-review

    Abstract

    Geocast is the concept of sending data packets to nodes in a specified geographical area instead of nodes with a specific address. This forwarding method is valuable in situations where any number of nodes inside a geographic area need to be reached, such as vehicular networking scenarios. To facilitate large scale geocast, a wired network geographic routing algorithm is needed that can route packets efficiently towards a destination area. Our goal is to design an algorithm that can deliver shortest path tree like geographic forwarding while relying purely on distributed data without central knowledge. In this paper we present and implement two algorithms for geographic routing. One algorithm is based purely on distance-vector data. Another, more complicated algorithm is based on path data. We show that our purely distance-vector-based algorithm can come close to the number of links used by a shortest path tree when a small number of routers are present in the destination area. We also show that our path-based algorithm can come close to the link usage of a shortest path tree in almost all geocast situations. We also show that the algorithms converge relatively quickly following link drops.

    Original languageEnglish
    Pages (from-to)201-218
    Number of pages18
    JournalComputer communications
    Volume146
    Early online date30 Jul 2019
    DOIs
    Publication statusPublished - 15 Oct 2019

    Fingerprint

    Routing algorithms
    Parallel algorithms
    Internet
    Routers

    Keywords

    • Geocast
    • Geographic routing
    • Routing

    Cite this

    @article{98dc10d2a6804a1c925f2347e025348a,
    title = "Design & analysis of a distributed routing algorithm towards Internet-wide geocast",
    abstract = "Geocast is the concept of sending data packets to nodes in a specified geographical area instead of nodes with a specific address. This forwarding method is valuable in situations where any number of nodes inside a geographic area need to be reached, such as vehicular networking scenarios. To facilitate large scale geocast, a wired network geographic routing algorithm is needed that can route packets efficiently towards a destination area. Our goal is to design an algorithm that can deliver shortest path tree like geographic forwarding while relying purely on distributed data without central knowledge. In this paper we present and implement two algorithms for geographic routing. One algorithm is based purely on distance-vector data. Another, more complicated algorithm is based on path data. We show that our purely distance-vector-based algorithm can come close to the number of links used by a shortest path tree when a small number of routers are present in the destination area. We also show that our path-based algorithm can come close to the link usage of a shortest path tree in almost all geocast situations. We also show that the algorithms converge relatively quickly following link drops.",
    keywords = "Geocast, Geographic routing, Routing",
    author = "Bernd Meijerink and Mitra Baratchi and Geert Heijenk",
    year = "2019",
    month = "10",
    day = "15",
    doi = "10.1016/j.comcom.2019.07.025",
    language = "English",
    volume = "146",
    pages = "201--218",
    journal = "Computer communications",
    issn = "0140-3664",
    publisher = "Elsevier",

    }

    Design & analysis of a distributed routing algorithm towards Internet-wide geocast. / Meijerink, Bernd; Baratchi, Mitra; Heijenk, Geert.

    In: Computer communications, Vol. 146, 15.10.2019, p. 201-218.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Design & analysis of a distributed routing algorithm towards Internet-wide geocast

    AU - Meijerink, Bernd

    AU - Baratchi, Mitra

    AU - Heijenk, Geert

    PY - 2019/10/15

    Y1 - 2019/10/15

    N2 - Geocast is the concept of sending data packets to nodes in a specified geographical area instead of nodes with a specific address. This forwarding method is valuable in situations where any number of nodes inside a geographic area need to be reached, such as vehicular networking scenarios. To facilitate large scale geocast, a wired network geographic routing algorithm is needed that can route packets efficiently towards a destination area. Our goal is to design an algorithm that can deliver shortest path tree like geographic forwarding while relying purely on distributed data without central knowledge. In this paper we present and implement two algorithms for geographic routing. One algorithm is based purely on distance-vector data. Another, more complicated algorithm is based on path data. We show that our purely distance-vector-based algorithm can come close to the number of links used by a shortest path tree when a small number of routers are present in the destination area. We also show that our path-based algorithm can come close to the link usage of a shortest path tree in almost all geocast situations. We also show that the algorithms converge relatively quickly following link drops.

    AB - Geocast is the concept of sending data packets to nodes in a specified geographical area instead of nodes with a specific address. This forwarding method is valuable in situations where any number of nodes inside a geographic area need to be reached, such as vehicular networking scenarios. To facilitate large scale geocast, a wired network geographic routing algorithm is needed that can route packets efficiently towards a destination area. Our goal is to design an algorithm that can deliver shortest path tree like geographic forwarding while relying purely on distributed data without central knowledge. In this paper we present and implement two algorithms for geographic routing. One algorithm is based purely on distance-vector data. Another, more complicated algorithm is based on path data. We show that our purely distance-vector-based algorithm can come close to the number of links used by a shortest path tree when a small number of routers are present in the destination area. We also show that our path-based algorithm can come close to the link usage of a shortest path tree in almost all geocast situations. We also show that the algorithms converge relatively quickly following link drops.

    KW - Geocast

    KW - Geographic routing

    KW - Routing

    U2 - 10.1016/j.comcom.2019.07.025

    DO - 10.1016/j.comcom.2019.07.025

    M3 - Article

    AN - SCOPUS:85070506362

    VL - 146

    SP - 201

    EP - 218

    JO - Computer communications

    JF - Computer communications

    SN - 0140-3664

    ER -