Periodic packet routing on trees

Britta Peis, Sebastian Stiller, and Andreas Wiese

not available

packet routing, real-time scheduling, scheduling

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.

Download as [PDF]