Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14464
For citation please use:
Main Title: Throughput maximization for periodic packet scheduling
Author(s): Peis, Britta
Wiese, Andreas
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15691
http://dx.doi.org/10.14279/depositonce-14464
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: In the periodic packet routing problem a number of tasks periodically create packets which have to be transported through a network. Due to capacity constraints on the edges, it might not be possible to find a schedule which delivers all packets of all tasks in a feasible way. In this case one aims to find a feasible schedule for as many tasks as possible, or, if weights on the tasks are given, for a subset of tasks of maximal weight. In this paper we investigate this problem on trees and grids with row-column paths. We distinguish between direct schedules (i.e., schedules in which each packet is delayed only in its start vertex) and not necessarily direct schedules. For these settings we present constant factor approximation algorithms, separately for the weighted and the cardinality case.
Subject(s): throughput maximization
packet routing
real-time scheduling
approximation algrithms
trees
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, 13
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:
Report-013-2010.pdf
Format: Adobe PDF | Size: 298.22 kB
DownloadShow Preview
Thumbnail

Item Export Bar

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