Path selection for real-time communication in wormhole networks

For real-time communication, we must be able to guarantee timely delivery of messages. In a previous paper, Kim et al. presented a real-time communication method for networks which uses a deterministic wormhole routing algorithm It would be more desirable to be able to use an adaptive wormhole routing algorithm. However, the use of an adaptive algorithm results in highly unpredictable communication delays because the path used by each message cannot be known in advance. Thus, an alternative is to use a flexible wormhole routing algorithm, in which one of a set of predefined paths is chosen tin advance) for each pair of communicating nodes. With flexible routing, real-time communication guarantees are again possible while making more effective use of the available network resources than deterministic routing. This paper examines the problem of selecting a set of paths to maximize the probability of meeting real-time communication guarantees for a set of communicating nodes. Since this problem is NP-hard, a heuristic solution is proposed and compared with previous path selection algorithms. Simulation results are used to show that the proposed path selection algorithm outperforms all previous algorithms.