Sparse Communication Networks and Efficient Routing in the Plane
Yehuda Hassin and David Peleg
To appear at Nineteenth Annual
ACM SIGACT-SIGOPS Symposium on PRINCIPLES OF DISTRIBUTED COMPUTING (PODC
2000), Portland, Oregon, 16-19 July 2000
Abstract
Traditional approaches to network design separate the issues of designing
the network itself and designing its management and control subsystems.
This paper proposes an approach termed routing-oriented network design,
which is based on designing the network topology and its routing scheme
together, attempting to optimize some of the relevant parameters of both
simultaneously. This approach is explored by considering the design of
communication networks supporting efficient routing in the special case
of points located in the Euclidean plane. The desirable network parameters
considered include low degree and small number of communication links.
The desirable routing parameters considered include small routing tables,
small number of hops and low routing stretch. Two rather different schemes
are presented, one based on direct navigation in the plane and the other
based on efficient hierarchical tree covers. On a collection of n sites
with diameter D, these methods yield networks with maximum degree O(log
D) (hence a total of O(n log D) communication links), coupled with routing
schemes with constant routing stretch, O(log n log D) memory bits per vertex
and routes with at most log n or log D hops.