Consider a small subset of shortest-path distance observations between a set of vertices on a graph structure, where we would like to infer all pairwise distances from these observations.  We show that when vertices of the graph naturally partition into clusters with a small number of egress points, while the overall distance matrix will have high rank, the submatrices of between-cluster distances can have very low rank.  These low rank submatrices permit the application of matrix completion theory and methods.  Using cluster assignment knowledge, it is possible to accurately and reliably recover most of the distances from a very small observation subset of pairwise distances.  An example of this type of clustering arises in the Internet due to the nature of connections between autonomous system networks.  On an empirical real world dataset, we show that our methods can estimate over 55% of the unseen distances between routers in the Internet to within a single link.