In designing a routing scheme for a communication network it is desirable to use as short as
possible paths for routing messages, while keeping the routing information stored in the
processors' local memory as succinct as possible. The efficiency of a routing scheme is
measured in terms of its stretch factor—the maximum ratio between the cost of a route
computed by the scheme and that of a cheapest path connecting the same pair of vertices.
This paper presents several simple families of routing schemes for general networks …