The main focus of the paper is to investigate the Delay-Constrained Least-Cost Routing (DCLCR) problem in the dynamic environment where the information available for routing selections is inaccurate. DCLCR is to find a least cost path subject to the delay constraint, which is NP-complete. Chen et al. presented a heuristic approach called Ticket-Based Routing (TBR). Later, Xiao et al. improved TBR. The latter is called Enhanced Ticket-Based Routing (ETBR). We propose a new approach called Non-deterministic Multi-probe Routing (NMR). The common feature of these algorithms is to search multiple paths in parallel for a feasible one. The difference is that we determine dynamically the number of probes in the process of probing, and use a "numbering tree" structure to count the total number of probes. By our simulations, NMR spends not only lower overhead than ETBR, but also can achieve better performance than ETBR in terms of call-admission ratio and/or cost of feasible paths. In addition, NMR uses less historic state information than ETBR.
展开▼
