ALCOMFT-TR-02-60

Jens S. Frederiksen and Kim S. Larsen
Packet Bundling
Århus. Work packages 2 and 4. May 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.

Postscript file: ALCOMFT-TR-02-60.ps.gz (106 kb).