Packet bundling

Description:

Jens S. Frederiksen and Kim S. Larsen. Packet bundling. In Proceedings of the Eighth Scandinavian Workshop on Algorithm Theory (SWAT 2002), volume 2368 of Lecture Notes in Computer Science, pages 328-337. Springer-Verlag, 2002.

Abstract:

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 emphasized less.

Copyright:

This paper is © Springer-Verlag.

Availability:

Available as ps (158 KB), ps.gz (64 KB), and pdf (189 KB).
Also available at SpringerLink.
The slides of my talk are available as ps (174 KB), ps.gz (68 KB), and pdf (77 KB).

Related Papers:

• Dynamic TCP acknowledgment in the LogP model (Journal Paper)
• Packet bundling (Technical Report)