KeLLy – Efficient, Scalable Link Layer Topology Discovery

Network infrastructures are becoming increasingly flexible and dynamic not only due to softwarization and virtualization, but also due to increasing mobility in 5G and 6G networks, which consider drones and satellites to be part of the core infrastructure. Since the network topology may change frequently, it becomes challenging to get an up-to-date view of its current state. This paper introduces KeLLy, an efficient, scalable link layer topology discovery algorithm focussing on large-scale networks (evaluated up to 100,000 nodes). KeLLy discovers various large topologies in seconds, guarantees discovery of all nodes (and a high percentage of links), while inducing low, predictable overhead by querying only a subset (4%) of nodes.