Packet bundling

Description:

Jens S. Frederiksen and Kim S. Larsen. Packet bundling. Technical Report PP-2002-09, Department of Mathematics and Computer Science, University of Southern Denmark, Odense, 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. It turns out that the flow-time cost function, which is the standard measure for problems of this type, cannot distinguish between the different algorithms. This leads us to develop an alternative quality measure under which we analyze our algorithms and determine which are best by obtaining tight results.

It is interesting to note that our results are very different from earlier works on the problem where the physical properties of the networks were emphasized less.

Availability:

Available as ps.gz (88 KB) and pdf (239 KB).
Also available at the DMF Preprint Server.

Related Papers:

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