Distributed route selection for establishing real-time channels

To guarantee the delivery of real-time messages before their deadline, a re al-time channel or connection must be established before the transmission o f any message belonging to the connection. During this channel establishmen t phase, one must first select a route between the source and destination o f this channel and then reserve sufficient resources along this route so th at the worst-case end-to-end delay over the selected route may not exceed t he user-specified delay bound. We propose an efficient distributed route se lection scheme that is guaranteed to find a "qualified" route, if any, sati sfying the performance requirement of the requested channel without comprom ising any of the existing guarantees. The proposed scheme can also eliminat e the common reliability/performance bottleneck of a centralized route sele ction scheme while improving efficiency over the centralized and other dist ributed schemes. Although the proposed solution starts with searching all p ossible routes in parallel, it prunes infeasible routes quickly, and its wo rst-case operational overhead is shown to be only a linear function of the number of links in the network. Several examples and simulation results are presented to demonstrate the effectiveness of the proposed distributed rou te selection scheme as compared to sequential route-search schemes.