Optimal Smoothing for Guaranteed Service

We consider a scenario where multimedia data is sent over a network offering a guaranteed service such as ATM VBR or the guaranteed service of the IETF. A smoothing device writes the stream into a networking device for transmission, possibly with some pre-fetching; at the destination, the decoder waits for an initial playback delay and reads the stream from the receive buffer. We consider the problem of whether there exists a smoothing which minimizes the playback delay and the receive buffer size over all possible strategies, given that we know a service curve property for the flow in the network. We show that there does exist such an optimal smoothing. It can be expressed using the deconvolution operator of min-plus algebra. We obtain the smallest playback delay which can be achieved by smoothing, provided that the information about the network is reduced to its service curve . We also give a constructive expression for the deconvolution operator, using a time inversion transform, introduced in the paper. We illustrate on some examples the difference with optimal shaping, a smoothing strategy which aims at minimizing buffer and delay on the sender side but does not allow pre-fetching. We apply the theory to the determination of the minimum T-SPEC required to support a given flow with admissible playback delay or decoding buffer size constraints.