Routing in Generalized Geometric Inhomogeneous Random Graphs

Sevilla De Pablo, Andres and Fernández Anta, Antonio (2020). Routing in Generalized Geometric Inhomogeneous Random Graphs. In: "NETYS 2020. The 8th Edition of International Conference on NETworked Systems", 03-06-2020 / 05-06-2020, Marrakech, Morocco. ISBN 978-3-030-67087-0. pp. 368-373. https://doi.org/10.1007/978-3-030-67087-0_25.

Description

Title: Routing in Generalized Geometric Inhomogeneous Random Graphs
Author/s:
  • Sevilla De Pablo, Andres
  • Fernández Anta, Antonio
Item Type: Presentation at Congress or Conference (Article)
Event Title: NETYS 2020. The 8th Edition of International Conference on NETworked Systems
Event Dates: 03-06-2020 / 05-06-2020
Event Location: Marrakech, Morocco
Title of Book: Networked Systems. NETYS 2020
Date: 2020
ISBN: 978-3-030-67087-0
Volume: 12129
Subjects:
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (203kB) | Preview

Abstract

In this paper we study a new random graph model that we denote (k, p)-KG and new greedy routing algorithms (of deterministic and probabilistic nature). The (k,p)-KG graphs have power-law degree distribution and small- world properties. (k,p)-KG roots on the Geometric Inhomogeneous Random Graph (GIRG) model, and hence they both preserve the properties of the hyperbolic graphs and avoid the problems of using hyperbolic cosines. In order to construct (k, p)-KG graphs, we introduce two parameters k and p in the process of building a (k,p)-KG graph. With these parameters we can generate Klein- berg and power-law networks as especial cases of (k, p)-KG. Also, we propose two new greedy routing algorithms to reduce the fail ratio and maintaining a good routing performance. The first algorithm is deterministic and the second is, in essence, a weighted random walk. We use simulation techniques to test our network model, and evaluate the new routing algorithms on the two graph models (GIRG and (k, p)-KG). In our simulations, we evaluate the number of hops to reach a destination from a source and the routing fail ratio, and measure the impact of the parameters (k and p) on the performance of the new routing algorithms. We observe that our graph model (k, p)-KG is more flexible than GIRG, and the new routing algorithms have better performance than the routing algorithms previously proposed.

Funding Projects

TypeCodeAcronymLeaderTitle
Madrid Regional GovernmentP2018/TCS-4499EDGEDATA-CMUnspecifiedUna infraestructura para sistemas híbridos altamente descentralizados
Government of SpainTIN2017-88749-RUnspecifiedUnspecifiedAlmacenamiento y computación distribuida en el borde (de la red)

More information

Item ID: 66058
DC Identifier: http://oa.upm.es/66058/
OAI Identifier: oai:oa.upm.es:66058
DOI: 10.1007/978-3-030-67087-0_25
Official URL: http://netys.net/history/netys2020/netys.net/index.html
Deposited by: Memoria Investigacion
Deposited on: 26 Feb 2021 09:48
Last Modified: 26 Feb 2021 09:49
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM