Design and analysis of permutation-based pyramid broadcasting

Periodic broadcasting can be used to support near-video-on-demand for popul ar videos. For a given bandwidth allocation, pyramid broadcasting schemes s ubstantially reduce the viewer latency (waiting) time compared to conventio nal broadcasting schemes. Nevertheless, such pyramid schemes typically have substantial storage requirements at the client end, and this results in se t-top boxes needing disks with high transfer rate capabilities. In this pap er, we present a permutation-based pyramid scheme in which the storage requ irements and disk transfer rates are greatly reduced, and yet the viewer la tency is also smaller. Under the proposed approach, each video is partition ed into contiguous segments of geometrically increasing sizes, and each seg ment is further divided into blocks, where a block is the basic unit of tra nsmission. As in the original pyramid scheme, frequencies of transmission f or the different segments of a video vary in a manner inversely proportiona l to their size. Instead of transmitting the blocks in each segment in sequ ential order, the proposed scheme transmits these blocks in a prespecified cyclic permutation to save on storage requirements in the client end. Perfo rmance analyses are provided to quantify the benefits of the new scheme.