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. The scheduling policies themselves must be simple enough to be executed in real-time, i.e., with low computational overhead. We compare the potential of two natural classes of policies, namely, template schedules and priority schedules by giving algorithms and lower bounds.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andrews, M., Fernández, A., Harchol-Balter, M., Leighton, F., Zhang, L.: General dynamic routing with per-packet delay guarantees of O (distance + 1/session rate). SIAM Journal of Computing 30, 1594–1623 (2000)
Busch, C., Magdon-Ismail, M., Mavronicolas, M., Spirakis, P.: Direct routing: Algorithms and complexity. Algorithmica 45, 45–68 (2006)
Buttazzo, G.C.: Hard Real-time Computing Systems: Predictable Scheduling Algorithms And Applications. Real-Time Systems Series. Springer, Santa Clara (2004)
di Ianni, M.: Efficient delay routing. Theoretical Computer Science 196, 131–151 (1998)
Leighton, F.T., Maggs, B.M., Rao, S.B.: Packet routing and job-scheduling in O(congestion + dilation) steps. Combinatorica 14, 167–186 (1994)
Leighton, F.T., Maggs, B.M., Richa, A.W.: Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica 19, 375–401 (1999)
Leighton, F.T., Makedon, F., Tollis, I.G.: A 2n − 2 step algorithm for routing in an n ×n array with constant size queues. In: Proceedings of the 1st Annual Symposium on Parallel Algorithms and Architectures, pp. 328–335 (1989)
Leung, J.Y.-T.: Handbook of Scheduling: Algorithms, Models and Performance Analysis (2004)
Mansour, Y., Patt-Shamir, B.: Greedy packet scheduling on shortest paths. Journal of Algorithms 14 (1993)
Peis, B., Skutella, M., Wiese, A.: Packet routing: Complexity and algorithms. In: Proceedings of the 7th Workshop on Approximation and Online Algorithms (2009)
Peis, B., Skutella, M., Wiese, A.: Packet routing on the grid. In: Proceedings of the 9th Latin American Theoretical Informatics Symposium (2010)
Peis, B., Stiller, S., Wiese, A.: Periodic packet routing on trees. Technical Report 008-2010, Technische Universität Berlin (April 2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Peis, B., Stiller, S., Wiese, A. (2010). Policies for Periodic Packet Routing. In: Cheong, O., Chwa, KY., Park, K. (eds) Algorithms and Computation. ISAAC 2010. Lecture Notes in Computer Science, vol 6507. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17514-5_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-17514-5_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17513-8
Online ISBN: 978-3-642-17514-5
eBook Packages: Computer ScienceComputer Science (R0)