On the Memory Requirement of Hop-by-hop Routing: Tight Bounds and Optimal Address Spaces

Kőrösi, Attila [Kőrösi, Attila (Alkalmazott matem...), szerző] Távközlési és Médiainformatikai Tanszék (BME / VIK); Gulyás, András [Gulyás, András (complex networks ...), szerző] Távközlési és Médiainformatikai Tanszék (BME / VIK); Heszberger, Zalán [Heszberger, Zalán (routing science), szerző] Távközlési és Médiainformatikai Tanszék (BME / VIK); Bíró, József [Bíró, József (networks), szerző] Távközlési és Médiainformatikai Tanszék (BME / VIK); Rétvári, Gábor [Rétvári, Gábor (Internet science), szerző] Távközlési és Médiainformatikai Tanszék (BME / VIK)

Angol nyelvű Szakcikk (Folyóiratcikk) Tudományos
Megjelent: IEEE-ACM TRANSACTIONS ON NETWORKING 1063-6692 1558-2566 28 (3) pp. 1353-1363 2020
  • SJR Scopus - Computer Networks and Communications: Q1
Azonosítók
We formulate the optimal address space design problem as the task to set node addresses in order to minimize certain network-wide entropy-related measures. We derive tight space bounds for many well-known graph families and we propose a simple heuristic to find optimal address spaces for general graphs. Our evaluations suggest that in structured graphs, including most practically important network topologies, significant memory savings can be attained by forwarding table compression over our optimized address spaces. According to our knowledge, our work is the first to bridge the gap between computer network scalability and information-theory.
Hivatkozás stílusok: IEEEACMAPAChicagoHarvardCSLMásolásNyomtatás
2025-02-14 12:52