Abstract
Hybrid networks are a promising architecture that builds
ad hoc, wireless networks around the existing cellular tele-
phony infrastructure and supporting massive deployment
for ad hoc networking. In this paper we present a rout-
ing protocol, DST, for hybrid networks that maintains a
close to optimal spanning tree of the network by using dis-
tributed topology trees. DST is fully dynamic and generates
only O(log n) messages per update operation. We demon-
strate experimentally that the performance of DST scales
well with the network size and activity, making it ideal for
the metropolitan environment hybrid networks are expected
to operate in.
