Please use this identifier to cite or link to this item:

Scheduling with deadlines in synchronous networks with given link capacities

Authors Ngok, Derek Hing-leung
Issue Date 1996
Summary 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.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1996
Language English
Format Thesis
Access View full-text via DOI
Files in this item:
File Description Size Format
th_redirect.html 341 B HTML
Copyrighted to the author. Reproduction is prohibited without the author’s prior written consent.