Capacity Results for Multicasting Nested Message Sets over Combination Networks

The problem of multicasting two nested message sets is studied over a class of wireline networks known as combination networks. A source multicasts two messages, a common and a private message, to several receivers. A subset of the receivers (called the public receivers) only demand the common message and the rest of the receivers (called the private receivers) demand both the common and the private message. Three encoding schemes are discussed which are based on linear superposition schemes. The standard linear superposition scheme is shown to be optimal for networks with two public receivers and any number of private receivers. When the number of public receivers increases, however, this scheme stops being optimal. Two improvements are discussed: one using a pre-encoding at the source followed by a linear superposition scheme, and one using a block Markov encoding scheme. The rate-regions that are achieved by the two schemes are characterized in terms of feasibility problems. Both inner-bounds are shown to be the capacity region for networks with three (or fewer) public and any number of private receivers. Although the inner bounds are not comparable in general, it is shown through an example that the region achieved by the block Markov encoding scheme may strictly include the region achieved by the pre-encoding/linear superposition scheme. The block Markov encoding scheme is further generalized and a new achievable scheme is derived for broadcast channels with two nested message sets. The rate-region that is obtained includes the previously known rate-regions. It remains open whether this inclusion is strict.     «

The problem of multicasting two nested message sets is studied over a class of wireline networks known as combination networks. A source multicasts two messages, a common and a private message, to several receivers. A subset of the receivers (called the public receivers) only demand the common message and the rest of the receivers (called the private receivers) demand both the common and the private message. Three encoding schemes are discussed which are based on linear superposition schemes....     »