The setup-trail-avoidance routing (STAR) algorithm is a new simple distributed routing algorithm for connection- oriented mesh networks. In this algorithm, signaling messages used to set up a service (or end-to-end connection) contain a list of nodes, called the setup trail, that have participated in routing the service to its destination. A node receiving such a signaling message will then calculate a shortest-path route to the service's destination using a network topology specific to the type of service, after first removing from the topology other nodes in the service's setup trail. STAR adapts to changing network conditions, choosing efficient routes for services (e.g., asynchronous transfer mode [ATM] virtual paths) while at the same time quickly terminating service setup requests that have little or no chance of being successfully completed. Simulated restoration studies show STAR has the best performance characteristics among many distributed restoration algorithms.