Offline real-time channel establishment in packet-switched networks

In this paper, the problem of real-time channel establishment in point-to-point connected networks using packet-switched store-and-forward routing is considered. Each message is associated with a real-time channel, which is an abstraction used to represent a source to destination connection. An offline real-time channel establishment algorithm that produces a feasible ordering, where all channels meet their deadline guarantees is presented. When scheduling a new channel, we allow partial reordering of previously scheduled channels, thereby increasing the size of the feasible set of channels compared to other methods. Alternative minimal routing paths when a channel cannot be scheduled on a path are also analyzed. Simulations show that our algorithm results in reducing the number of unschedulable messages compared to other existing algorithms. For the 2D mesh, the percentage of failed messages using our algorithm drops by as much as 65.69% compared to a previous algorithm [1]. Allowing offline adaptive paths results in reducing the percentage of failed messages for all methods and topologies examined, compared to non-adaptive routing. (C) 1998 Elsevier Science B.V.