A distributed inter-domain constraints-based routing technique is provided herein. A problem solving request is sent to nodes in a plurality of network domains that have a potential path between a source node and the destination node. The problem solving request includes one or more constraints associated with a routing function for traffic between the source node and destination node. Local path solutions are generated at nodes in domains that receive the problem solving request, where the local path solutions representing possible paths from a previous neighbor network domain to a next neighbor network domain that satisfy the one or more constraints. Based on the local path solutions, a determination is made as to whether there is at least one path from the source node to the destination node that satisfies the one or more constraints.