Abstract. In network coding based multicast, coding operations are expected to be minimized as they not only incur additional computational cost at corresponding nodes in network but also increase data transmission delay. On the other hand, delay constraint must be concerned particularly in delay sensitive applications, e.g. video conferencing. In this paper, we study the problem of minimizing the amount of coding operations required while meeting the end-to-end delay constraint in network coding based multicast. A population based incremental learning (PBIL) algorithm is developed, where a group of best so far individuals, rather than a single one, is maintained and used to update the probability vector, which enhances the global search capability of the algorithm. Simulation results demonstrate the effectiveness of our PBIL. Keywords: multicast; network coding; population based incremental learning Network coding has been attracting an increasing research attention since 2000 [1] . Instead of simply replicating and forwarding data packets at the network layer, network coding allows any intermediate node, if necessary, to perform mathematical operations to recombine data packets received from different incoming links. By doing so, the maximized multicast throughput is always obtained [2] . In most of the previous research on network coding, coding is performed at all coding-possible nodes without concerning issues raised in real life applications. One such issue is that, to obtain an expected multicast throughput, coding may only be necessary at a subset of coding-possible nodes [3, 4, 5] . As they consume public resources, e.g. buffer and computational resources, coding operations should be minimized to leave more public resources for other network applications. Another issue in real time applications is that transmission delays, especially in delay sensitive applications, e.g. video conferencing and distributed game, should be bounded. It is therefore important to minimize coding operations while meeting the end-to-end delay requirement. However, such problem has not drawn enough research attention. A number of algorithms have been proposed to minimize coding resources, however, without concerning the delay constraint. In [6] and [7] , original topologies were decomposed and transformed into secondary graphs, based on which greedy
Even though network coding is performed at all the nodes in some relevant literature, an remarkable observation is that a maximum download rate can be achieved by performing the coding operation at relatively small portion of the network REF .
A Population Based Incremental Learning for Delay Constrained Network Coding Resource Minimization
EvoApplications
Computer Science