HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item:
Title: Scheduling with deadlines in synchronous networks with given link capacities
Authors: Ngok, Derek Hing-leung
Issue Date: 1996
Abstract: 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.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1996
x, 45 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 1996 Ngok
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat

All items in this Repository are protected by copyright, with all rights reserved.