In this paper, we propose a path-vector protocol for multiconstraint QoS routing. The protocol allows nodes in the network to exchange paths, and constructs new paths using our distributed algorithm. Explicit paths provided by the protocol could be used for both multiconstraint QoS and best-effort services. To deal with scalability, we introduce an algorithm to reduce the number of paths by using a clustering method. The method searches and removes paths based on similarity of measurements of path metrics. Simulation results show that our path-vector protocol is scalable and capable to provide explicit paths for multiconstraint QoS routing. Success rate of QoS path setup in simulated heterogeneous networks could be as high as 92 percents.