Please use this identifier to cite or link to this item:
For citation please use:
Main Title: Periodic packet routing on trees
Author(s): Peis, Britta
Stiller, Sebastian
Wiese, Andreas
Type: Research Paper
Abstract: In the periodic packet routing problem each of a set of tasks repeatedly emits packets over an infinite time horizon. These have to be routed along their fixed path through a common network. A schedule must resolve the resource conflicts on the arcs, such that the maximal delay any packet experiences can be bounded. We prove that such a schedule exists if and only if a simple to check criterion on the load of each arc is fulfilled. This even holds for the desirable class of template schedules. As in non-periodic packet routing we lay special emphasis on trees as underlying graphs. The scheduling policies themselves must be simple enough to be executed in real-time, i.e., with low computational overhead. We give algorithms to construct good edge- priority schedules and so-called template schedules by carefully balancing the delay among the packets. We can show that our template schedule guarantees a delay of less than c(2 -(1/2)diam(G)/2) and our edge-priority schedule of at most 1.5c -1 (with c the maximal number of tasks using an arc). The latter is shown to be tight by an involved but insightful class of examples. Also for the template schedule we give a lower bound, as for a number of other positive results. All together this yields a fairly complete overview on period packet routing on trees. To compare the power of priority and template schedules we derive imitation theorems, i.e., we show that any bound achieved by a priority schedule on a specific instance can also (almost) be attained by a template schedule.
Subject(s): packet routing
real-time scheduling
Issue Date: 2010
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2010, 08
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 588.21 kB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.