Scheduling multipacket frames with frame deadlines |
| |
Authors: | Łukasz Jeż Yishay Mansour Boaz Patt-Shamir |
| |
Affiliation: | 1.Institute of Computer Science,University of Wroc?aw,Wroc?aw,Poland;2.Blavatnik School of Computer Science,Tel Aviv University,Tel Aviv,Israel;3.Microsoft Research,Herzlia,Israel;4.School of Electrical Engineering,Tel Aviv University,Tel Aviv,Israel |
| |
Abstract: | We consider scheduling information units called frames, each with a delivery deadline. Frames consist of packets, which arrive online in a roughly periodic fashion, and compete on allocation of transmission slots. A frame is deemed useful only if all its packets are delivered before its deadline. We focus on a “proportional” variant, where the value of each frame is proportional to its size, but the sizes and periods of the frames are arbitrary. We give a constant-competitive algorithm for this setting, assuming bounded jitter and some slack in the frames’ deadlines, the latter of which is necessary. Using standard techniques, our algorithm yields polylog-competitive algorithms for general instances with slack and bounded jitter. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|