UNLV ECG 702 - Scheduling Time-Constrained Communication i Linear Network

Unformatted text preview:

Scheduling Time-Constrained Communication in Linear Networks Micah Adler* Dept. of Computer Science, Univ. of Toronto, Toronto ON, M5S3G4, Canada Ramesh K. Sitaramant Dept. of Computer Science, Univ. of Massachusetts, Amherst, MA 0 1003 Abstract We study the problem of centrally scheduling multiple messages in a linear network, when each message has both a release time and a deadline. We show that the problem of transmitting optimally many messages is NP-hard, both when messages may be buffered in transit and when they may not be; for either case, we present effi- cient algorithms that produce approximately optimal schedules. In particular, our bufferless scheduling algorithm achieves throughput that is within a factor of two of optimal. We show that buffering can improve throughput in general by a logarithmic factor (but no more), but that in several significant special cases, such as when all messages can be released immediately, buffering can help by only a small constant factor. Finally, we show how to convert our centralized, offline bufferless schedules to equally productive fully * Email: micah@cs. toronto edu. Supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada, and by ITRC, an Ontario Centre of Excellence. Thts research was conducted in part while he was at the Heinz Nixdorf Institute Graduate College, D-33095 Paderborn, Germany. ’ Email: rsnbrg@cs .umass edu. Supported in pan by NSF Grant CCR-97- 10367. t Email: ramesh@cs umass edu. Supported in part by an NSF CAREER Award No. CCR-97-03017. A portion of the research of the second and third author was done while visiting the Dept. of Mathematics and Infotmatik, Univ. of Paderhorn, Paderbom, Germany. 5 Emal: quacksOil.informatik.rwth-aachen.de The work was carried out white the author was a member of the research group of B. Monien at the University of Paderbom. This work and the visits of the second and third author was partially supported by the German Research Association (DFG) within the SFB 376 “Massive Parallelit%t: Algorithmen, Entwurfsmethoden, Anwendungen”. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the fti page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission an&or a fee. SPAA 98 Puerto Vallarta Mexico Copyright ACM 1998 O-89791-989-0/98/ 6...$5.00 Arnold L. Rosenberg+ Dept. of Computer Science, Univ. of Massachusetts, Amherst, MA 01003 Walter Unger§ Lehrstuhl fur Informatik I, RWTH Aachen, Ahomstr. 55, 52074 Aachen, Germany distributed online buffered ones. Most of our results extend readily to ring-structured networks. 1 The Time-Constrained Communication Problem 1.1 Introduction Communication and interconnection networks are currently under- going a transition from traditional best-effort data networks to net- works capable of routing messages with timing constraints. In the area of communication networks, this shift is motivated by mul- timedia applications that use continuous media such as video and audio [27]; for instance, a real-time audio packet in a teleconferenc- ing application must reach its destination within a specified win- dow of time for it to have any utility. The analogous shift in the development of interconnection networks is motivated by emerg- ing real-time applications that rely on time-constrained communi- cation, such as industrial process control, avionics, and automated manufacturing [41]. In this paper, we consider the scheduling of the transmission of a given set of time-constrained messages in a multi-node network. Our goal is to deliver as many of the given messages as possible, within the following framework: l Each message consists of a single packet. A network node may send many messages to each of the other nodes. l Each message m has, in addition to a source-node sm and a destination-node d,, a release time, which is the earliest moment at which m can start its journey from sm to d,, and a deadline, beyond which no purpose is served by delivering m. This means that a message should be dropped as soon as it can no longer be delivered by its deadline. Our framework allows us to model multiple classes of messages with differing timing requirements-a feature that is essential to modeling multimedia traffic. We can also mode1 messages for which conventional best-effort transmission is sufficient, by setting these messages’ associated deadlines to co. Our framework should be contrasted with that of more traditional routing problems, which seek to optimize global objectives such as overall completion time 269or average message latency, and do not associate time constraints with individual messages. The Network Model. We focus on routing messages in linear networks-although most of our results apply also to ring-structured networks. This focus on linear topologies is a first step towards considering more complex interconnection topologies proposed in the literature, such as higher-dimensional arrays [41]. There are often also other rationales for the focus, such as the following. (a) When routing messages in electro-optical interconnection networks such as hierarchical rings [22] or meshes [41], or their relatives, one might have each packet follow a path composed predominantly of long (inexpensive) bufferless hops, punctuated by a very few (costly) optical-electric conversions at certain nexus nodes. In a mesh, for instance, one might employ a dimension-order routing strategy [41] which uses our near-optimal bufferless routing along rows and along columns but that performs a single optical-electric conversion to change dimensions, (b) In less regularly structured communication


View Full Document
Download Scheduling Time-Constrained Communication i Linear Network
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Scheduling Time-Constrained Communication i Linear Network and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Scheduling Time-Constrained Communication i Linear Network 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?