Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2008 Research Summary

Fundamental Constraints on Multicast Capacity Regions

View Current Project Information

Leonard Henry Grokop and David Tse

The broadcast channel has predominantly been studied in the context of unicast messaging, where the transmitter wishes to send one private message to each of the L receivers. However, in certain applications, particularly in networks, the transmitter may wish to send different messages to different subsets of receivers. We refer to this as multicasting. The most general multicast structure comprises of 2L - 1 messages. The multicast capacity region for a broadcast channel is then the set of 2L - 1 dimensional rate vectors that are achievable. Unlike the unicast capacity region, however, the multicast capacity region exhibits a certain, over-specified structure that stems from the fact that certain messages are universally interchangeable with others. For two and three receiver broadcast channels/networks we precisely characterize this structure, together with the complete set of operations that interchange messages. We show that whereas for two receiver channels, all operations are akin to relabeling, for three or more receiver channels, some operations require a form of network coding.

Figure 1
Figure 1: The capacity region of a 2-receiver broadcast channel with private and common messages has the following property: the achievability of one rate point always implies the achievability of the set of rate points shown above.

L. Grokop and D. N. C. Tse, "Fundamental Constraints on Multicast Capacity Regions," Prov. Allerton Conference, Monticello, IL, September 2007.