Online packet routing on linear arrays and rings

Title:
Online packet routing on linear arrays and rings
Authors:
Havill, Jessen T.
Citation:
J. Havill, Online packet routing on linear arrays and rings, Automata, Languages and Programming, Proc. 28th ICALP, LNCS 2076, pp. 773-784, 2001.
Publisher:
28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedings
DATE ISSUED:
2001
PERMANENT LINK:
http://hdl.handle.net/2374.DEN/4999; http://hdl.handle.net/2374
Type:
Article; Book chapter
Language:
en_US
Description:
In contrast to classical offline k-k routing, the online packet routing problem allows for an arbitrary number of packets with arbitrary end points and release times. We study this problem on linear array and ring networks. We generalize an earlier result for the offline problem by showing that Farthest First (FF) scheduling is optimal with respect to makespan on linear arrays. We also show that two other algorithms (Longest in System (LIS) and Moving Priority (MP)) have competitive ratio 2 with respect to makespan on linear arrays. For bidirectional rings, we show that, the competitive ratio of shortest path routing combined with LIS or MP scheduling is in [2.5, 3) and the competitive ratio of shortest path routing combined with FF scheduling is 2. The latter algorithm is optimal among deterministic memoryless algorithms and all algorithms of which we are aware in the literature.
ISSN:
9783540482246
ISBN:
9783540422877
Appears in Collections:
Faculty Publications

Full metadata record

DC FieldValue Language
dc.contributor.authorHavill, Jessen T.en
dc.date.accessioned2013-01-02T16:08:54Zen
dc.date.accessioned2013-12-18T21:04:49Z-
dc.date.available2013-01-02T16:08:54Zen
dc.date.available2013-12-18T21:04:49Z-
dc.date.created2001en
dc.date.issued2001en
dc.identifier.citationJ. Havill, Online packet routing on linear arrays and rings, Automata, Languages and Programming, Proc. 28th ICALP, LNCS 2076, pp. 773-784, 2001.en_US
dc.identifier.isbn9783540422877en
dc.identifier.issn9783540482246en
dc.identifier.urihttp://hdl.handle.net/2374.DEN/4999en
dc.identifier.urihttp://hdl.handle.net/2374-
dc.descriptionIn contrast to classical offline k-k routing, the online packet routing problem allows for an arbitrary number of packets with arbitrary end points and release times. We study this problem on linear array and ring networks. We generalize an earlier result for the offline problem by showing that Farthest First (FF) scheduling is optimal with respect to makespan on linear arrays. We also show that two other algorithms (Longest in System (LIS) and Moving Priority (MP)) have competitive ratio 2 with respect to makespan on linear arrays. For bidirectional rings, we show that, the competitive ratio of shortest path routing combined with LIS or MP scheduling is in [2.5, 3) and the competitive ratio of shortest path routing combined with FF scheduling is 2. The latter algorithm is optimal among deterministic memoryless algorithms and all algorithms of which we are aware in the literature.en_US
dc.language.isoen_USen_US
dc.publisher28th International Colloquium, ICALP 2001 Crete, Greece, July 8–12, 2001 Proceedingsen_US
dc.relation.ispartofFaculty Publicationsen_US
dc.titleOnline packet routing on linear arrays and ringsen_US
dc.typeArticleen_US
dc.typeBook chapteren_US
dc.contributor.institutionDenison Universityen_US
dc.date.digitized2013-01-02en
dc.contributor.repositoryDenison Resource Commonsen_US
All Items in The Five Colleges of Ohio Digital Repository are protected by copyright, with all rights reserved, unless otherwise indicated.