Network service provisioning involves the control of network resources through signaling, routing and management protocols that achieve Quality of Service and Traffic Engineering objectives. Network service providers are typically faced with scalability problems due to the explosion in network size and demand. In this paper we propose a new hierarchical distributed protocol for the provisioning of MPLS-based tunnels. The protocol encapsulates the required signaling and routing. The protocol alleviates the scalability problem through extending the current two-tier architecture of the Internet to a multi-level hierarchical one. It enables mechanisms for Quality of Service, and intra- and inter-domain Traffic Engineering. Analytical analysis and simulation results show that the protocol exploits parallelism in routing computation to reduce the setup time of an MPLS path. This comes at the expense of an increased message complexity relative to other hierarchical protocols.