We study a scheduling problem for message delivery in synchronous directed networks with given link capacities. Given the source, destination and deadline for each message to be transmitted, we have to find a schedule under which all messages arrive at their destinations on time. The scheduling allows each processor to send, at each step in the synchronous execution, a number of messages that will not exceed its outgoing link capacity. We show that the greedy algorithm, that gives priority to the most urgent messages, determines a feasible schedule if one exists. Moreover, we prove that this algorithm maximizes the minimal possible gain of a message (which is the number of time units in which a message arrives at its destination prior to its deadline). The results are shown to be applic...[ Read more ]

We study a scheduling problem for message delivery in synchronous directed networks with given link capacities. Given the source, destination and deadline for each message to be transmitted, we have to find a schedule under which all messages arrive at their destinations on time. The scheduling allows each processor to send, at each step in the synchronous execution, a number of messages that will not exceed its outgoing link capacity. We show that the greedy algorithm, that gives priority to the most urgent messages, determines a feasible schedule if one exists. Moreover, we prove that this algorithm maximizes the minimal possible gain of a message (which is the number of time units in which a message arrives at its destination prior to its deadline). The results are shown to be applicable to any bottleneck-free network as well as ring network with uniform link capacities. A processor is bottleneck if the sum of all incoming link capacities is greater the capacity of any outgoing link. For networks with bottlenecks, we study the relationships among different types of chain and tree networks. We determine a necessary condition for solving scheduling problems in these networks and prove that the problem is equivalent in different types of tree networks. Finally, the routing problem of message delivery in certain ring networks are shown to be NP-Complete.