Distributed QoS routing with imprecise state information

The goal of quality-of-service (QoS) routing is to find a network path which has sufficient resources to satisfy certain constraints on delay, bandwidth and/or other metrics. The network state information maintained at every node is often imprecise in a dynamic environment because of nonnegligible propagation delay of state messages, periodic updates due to overhead concern, and hierarchical state aggregation. The information imprecision makes QoS routing difficult. The traditional shortest-path routing algorithm does not provide satisfactory performance with imprecise state information. We propose a distributed routing scheme, called ticket-based probing, which searches multiple paths in parallel for a satisfactory one. The scheme is designed to work with imprecise state information. It allows the dynamic trade-off between the routing performance and the overhead. The state information of intermediate nodes is collectively used to guide the routing messages along the most appropriate paths in order to maximize the success probability. The proposed algorithm consider not only the QoS requirements but also the cost optimality of the routing path. Extensive simulations show that our algorithm achieve high call-admission ratio and low-cost routing paths with modest overhead. The algorithm can tolerate high degree of information imprecision.