The aim of this document is to present the recent research results in the field of navigability
of complex network models. We have used an investigated the well known Krioukov
hyperbolic random network model, which turned out to be a good modeling and predictive
framework for many networks occured in real life, e.g. the Internet AS level topology. More
definitely, the entropy and the memory requirements of the forwarding tables (FIB) placed at
nodes of the greedy routing are investigated, lower and upper bounds are to be determined.
First, we have determined for an arbitrary node the greedy next hop set, the set of nodes
which elements can act greedy next hops towards other non-neighboring nodes, in an
averaged network in the Krioukov hyperbolic model. Then, based on the greedy next hops
and the expected number of nodes covered by these greedy next hopes, the FIB entropy
the function of the considered node is determined, which depends on the node hyperbolic
coordinates, the average degree in the network, and the total number of nodes and disk
radius as model parameters.
Based on the investigation of the entropy function we have shown that lower and upper
bounds on the memory requirements of greedy routing can be determined, both for node and
network level. These bounds can help to set up and assess a FIB based greedy routing
framework from the viewpoint of computational complexity, speed and memory requirements.
Bíró József, egyetemi tanár, Távközlési és Médiainformatikai Tanszék, biro@tmit.bme.hu
2015. december 27.