Skip to main content
Open Access Publications from the University of California

Topological Interference Management through Index Coding

  • Author(s): Jafar, Syed A
  • et al.

While much recent progress on interference networks has come about under the assumption of abundant channel state information at the transmitters (CSIT), a complementary perspective is sought in this work through the study of interference networks with no CSIT except a coarse knowledge of the topology of the network that only allows a distinction between weak and significant channels and no further knowledge  of the channel coefficients' realizations. Modeled as a degrees-of-freedom (DoF) study of a partially connected interference network with no CSIT, the problem is found to have a counterpart in the capacity analysis of wired networks with arbitrary linear network coding  at intermediate nodes, under the assumption that the sources are aware only of the end to end topology of the network. The network capacity (wired) and DoF (wireless) region, expressed in dimensionless units as multiples of the capacity (wired) and DoF (wireless) of a single link, are found to be bounded above by the capacity of an index coding problem where the antidotes graph is the complement of the interference graph of the original network and the bottleneck link capacity is normalized to unity. The problems are shown to be equivalent under linear solutions. An interference alignment perspective is then used to translate the existing index coding solutions into the wired network capacity and wireless network DoF solutions, as well as to find new  and unified solutions to different classes of all three problems. For networks with $K$ messages, a study of the extremes -- when each message achieves half the cake, and when each message can achieve no more than $1/K$ of the cake, reveals the necessary and sufficient conditions for each, in terms of alignment graphs and demand graphs, respectively. Half the cake per message is achievable if and only if the alignment graph has no internal conflicts. No more than $1/K$ of the cake is achievable if and only if the network can be relaxed into a $K$-unicast setting with an acyclic demand graph. For half-rate-feasible networks, best case capacity (DoF) improvements over the best orthogonal (TDMA) and multicast (CDMA) solutions are explored for multiple groupcast and multiple unicast settings, and shown to be of polynomial order in the number of messages. For intermediate cases where neither half the cake, nor $1/K$ of the cake per message is capacity (DoF) optimal, the interference alignment perspective is used to characterize the symmetric capacity (DoF) of all cases where each  alignment set either does not contain a cycle or does not contain a fork. A study of linear feasible rates shows duality properties that are used to extend the scope of previous results. For wireless networks, extensions to multiple antenna networks are made in symmetric settings where all nodes are equipped with the same number of antennas. The study of certain topologies of interest, motivated by cellular networks reveals interesting aligned frequency reuse patterns.

Main Content
Current View