- Packet Bundling.
- Jens S. Frederiksen and Kim S. Larsen.
In 8th Scandinavian Workshop on Algorithm Theory (SWAT), volume 2368 of Lecture Notes in Computer Science, pages 328-337. Springer, 2002.
When messages, which are to be sent point-to-point in a network, become
available at irregular intervals, a decision must be made each time a new
message becomes available as to whether it should be sent immediately or if it
is better to wait for more messages and send them all together. Because of
physical properties of the networks, a certain minimum amount of time must
elapse in between the transmission of two packets. Thus, whereas waiting
delays the transmission of the current data, sending immediately may delay the
transmission of the next data to become available even more.
We consider deterministic and randomized algorithms for this on-line problem,
and characterize these by tight results under a new quality measure.
It is interesting to note that our results are quite different from earlier
work on the problem where the physical properties of the networks were
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
Other publications by the author.