Space Information Flow

Network information flow emerged as a fertile research ground over a decade ago, with the advent of network coding that allows information flows to be encoded when they meet within a data network. In this talk, I will introduce `space information flow’ — the transmission of information flows in free space, instead of in a fixed, existing network topology. Information flows are free to propagate along any trajectories in space, and may be encoded wherever they meet. The goal is to minimize a natural bandwidth-distance sum- product, while sustaining end-to-end unicast and multicast communication demands among terminals at known coordinates. We show that space information flow models the fundamental problem of information network design, which deserves renewed research attention for taking into account the unique encodable property of information flows. We relate space information flow to network information flow, and compare the benefits of network coding in them. We prove the multiple unicast conjecture, a well known conjecture in network information flow, in the space information flow paradigm. For multicast communication demands, we show that designing an information network is indeed different from designing a transportation network. In particular, an optimal multicast network does not necessarily correspond to a Steiner tree, as assumed in past literature. We prove such a difference by demonstrating that the cost advantage (ratio of min network cost without coding over that with coding) can be strictly larger than 1 in the space model. We further prove upper-bounds for the cost advantage in different scenarios of multicast network design.