Bounds on Linear Codes for Network Multicast
Meir Feder, Dana Ron, Ami Tavory · Electronic colloquium on computational complexity · 2003
Traditionally, communication networks are composed of routing nodes, which relay and duplicate data. Work in recent years has shown that for the case of multicast, an improvement in both rate and code-construction complexity can be gained by replacing these routing nodes by linear coding nodes. These nodes transmit linear combinations of the inputs transmitted to them. In this work, we deal with bounds on the alphabet size and amount of coding necessary for linear codes for multicast. We show that known bounds on maximum distance separable codes can be applied to bound the required alphabet-size. We show upper bounds on the number of “clashes” between flows from source to terminals. Using this, we show upper bounds on the number of nodes in which coding must be performed, and graph-specific upper bounds on the alphabet-size. We show how the addition of a small amount of memory to internal nodes can be used to increase the effective alphabet-size available for coding, and show bounds on the throughput and latency of this technique. Finally, we show that the above bounds also pertain to a case less considered in previous networkmulticast work, static broadcast, wherein the source transmits the same set of data to terminals at different rates.