Bus and buffer usage in in-home digital networks: applying the Dantzig–Wolfe decomposition

In an in-home digital network several data streams (audio, video) may run simultaneously over a shared communication device, e.g. a bus. The burstiness of a data stream can be reduced by buffering data at the sending and receiving side, thereby allowing a lower bus share allocation for the stream. In this paper we present an algorithm that determines how much of the bus capacity and buffer space should be allocated to each stream, in order to have a feasible transmission schedule for each stream. Furthermore, the algorithm determines a transmission schedule for each stream, indicating how much data is transmitted over time. We model the problem as a linear program and apply a Dantzig–Wolfe decomposition such that the multiple-stream problem can be solved by repeatedly solving single-stream problems. For these single-stream problems we briefly describe efficient algorithms to solve them.