The routing strategy used in today's Internet is best-effort service, where all data packets are treated equally. This type of service is not suited for applications such as video conferencing, and video on demand, that requires the availability of certain resources (such as bandwidth) to be guaranteed for them to function properly. The routing in this context, called Quality-of-Service (QoS) Routing, is the problem of finding suitable paths that meet the application's resource requirements. The majority of proposed QoS routing schemes operate by maintaining the global state of the network, and using this knowledge to compute the QoS route. However, all these schemes suffer from the inherent drawback of scalability, because of the need for each node to collect state information about the complete network. The other type of QoS routing schemes do not maintain network state information, but instead flood the network with QoS connection establishment requests. This type of scheme suffers from excessive message overhead during QoS connection establishment. In this thesis, we present a new QoS routing algorithm that is a combination of the above-mentioned two schemes (i.e., global state and flooding based). The algorithm aims at minimizing the message overhead associated with these two schemes and still maintaining the positive aspects of both of them. The basic idea of the algorithm is: to reach to a destination, the path(s) will always pass through a specific set of intermediate nodes. The algorithm discovers such intermediate nodes (limited by a hop count threshold value needed to reach there). When a QoS connection request arrives at a node, it selects the feasible path leading to the intermediate node for the requested destination. The QoS connection establishment message (or routing message) is forwarded along this path. When the message arrives at the intermediate node, the further path is decided through same logic. To decide the path that leads to the intermediate node, the algorithm maintains the link state related to these intermediate nodes, and link state updates are restricted only with regard to these intermediate nodes. Because of this restriction in link state updation, one has less message overhead, compared to the global state based routing scheme. Further, the algorithm tries to group these intermediate nodes in such a way that the routing message need be sent to only one of the grouped intermediate nodes, and still makes sure that all the possible paths are covered. Therefore, one has a reduced message overhead because of grouping.