One of the fundamental trade-oﬀs in compact routing schemes is between the space used to store the routing table on each node and the stretch factor of the routing scheme – the maximum ratio over all pairs between the cost of the route induced by the scheme and the cost of a minimum cost path between the same pair. All previous routing schemes required storage that is dependent on the diameter of the network. We present a new scale-free routing scheme, whose storage and header sizes are independent of the aspect ratio of the network. Our scheme is based on a decomposition into sparse and dense neighborhoods. Given an undirected network with arbitrary weights and n arbitrary node names, for any integer k ≥ 1 we present the ﬁrst scale-free routing scheme with asymptotically optimal space-stretch tradeoﬀ that does not require edge weights to be polynomially bounded. The scheme uses e O(n1/k) space routing table at each node, and routes along paths of asymptotically optimal linear stretch O(k).