Reliability-constrained least-cost routing in multihop networks

Several real-time applications require communication services with guaranteed timeliness and fault-tolerance at acceptable levels of overhead. Different applications/end users may need different levels of fault-tolerance and differ in how much they are willing to pay for the service they get. A control scheme which is used to set up and tear down paths, should not only be fast and efficient, must also be scalable, and should try to minimize the number of blocked connections; while satisfying the requested level of fault-tolerance. In this work we propose a distributed control scheme based on preferred link approach for establishing reliability-constrained least-cost paths, by choosing the reliability of the path to denote the level of fault-tolerance required by the connection request. The scheme is flexible in that a variety of heuristics can be employed to order the neighboring links of any given node. Four heuristics are proposed and their performance is studied through extensive simulation experiments. The proposed heuristics do not require maintenance of any global state information. The simulation results suggest that our heuristics are attractive enough in terms of average call acceptance rate, average path cost, average routing distance, and average connection setup time. Furthermore, if the network service provider feels that he/she can earn more revenue by admitting more number of calls with reliability requirements, he/she can do so by manipulating the parameters of our scheme, such as the maximum number of preferred links used at each node.