A routing architecture is described for very large communications networks with greater than 10,000 routing nodes and 100,000 end nodes. This architecture, called the Traveler Architecture, is designed to be independent of network configuration and to be robust even under conditions of rapid reconfiguration. Traveler is an extension of the ISO routing protocols. The Traveler architecture is designed to work with traffic characteristic of existing large networks, such as the Internet. While Traveler does not require a particular routing algorithm, it is designed to work in conjunction with families of distributed routing algorithms. Because Traveler is based on the paradigm of a human traveler, it attempts to use non-deterministic and heuristic methods rather than purely algorithmic methods to determine high quality routes between two points. Traveler builds on the Landmark and Area routing architectures.