On Identifying which Intermediate Nodes Should Code in Multicast Networks

Network coding has the potential to enhance energy efficiency of multicast sessions by providing optimal communication subgraphs for the transmission of the data. However, the coding requirement at intermediate nodes may introduce additional complexity and energy consumption in order to code the data packets. Previous work has shown that in lossless wireline networks, the performance of tree-packing mechanisms is comparable to network coding, albeit with added complexity at the time of computing the trees. This means that most nodes in the network need not code. Thus, mechanisms that identify intermediate nodes that do require coding is instrumental for the efficient operation of coded networks and can have a significant impact in overall energy consumption. We present a distributed, low complexity algorithm that allows every node to identify if it should code and, if so, through what output link should the coded packets be sent. Our algorithm uses as input the optimal subgraph determined by Lun et al's optimization formulation [13]. Numerical results are provided using common Internet Service Provider (ISP) network topologies and also random network deployments. Our results show that the number of coding nodes in the expectation is very low (typically below 1) and that the number of sessions that require coding is limited, e.g., less than 15% for sessions of 4 receivers for the ISP networks and below 0.1% for networks with random node deployments in a square of 1 × 1 km2 with of up to 30 nodes and up to 20 receivers.