Multicast Network Coded Flow In Grid Graphs

Network coding, a relatively new paradigm for transmitting information through communication networks, allowing intermediate nodes in the network to combine data received on separate incoming channels before transmitting on outgoing channels. When compared with traditional routing paradigms, network coding can result in benefits such as higher throughput, fault-tolerance, and security. In this paper, we focus on studying network coding properties on a specific class of graphs called grid graphs. Network coding properties are related to well-known Steiner properties in graphs. Specifically, Steiner properties of grid graphs are studied, because they model VLSI layout design, which makes network coding properties a natural extension of this investigation. In particular, we looked at the maximum size of a communication group that is possible in a grid graph, given a specific desired transmission rate. Letting ρk (G) be the maximum fraction of nodes in graph G that can be included in a network coded multicast group with an integral flow of size k, we prove that ρ2(G)< 1, ρ3(G)< 2 , and ρ4(G)< 1 3 . In the first two cases, we construct families of communication groups on grid graphs which approach these bounds. In the latter case, we present a family of communication groups approaching a density of 4 .