Whereas the theory and application of optimal network coding are well studied for the single-session multicast scenario, there is no known optimal network coding strategy for a more general connection problem where there are more than one session and receivers may demand different sets of information. Though there have been a number of recent studies that demonstrate various utilities of network coding in the multi- session scenario, they rely on very restricted classes of codes in terms of the coding operations allowed and/or the location of decoding. In this paper, we propose a novel inter-session network coding strategy for a general connection problem. Our coding strategy allows fairly general random linear coding over a large finite field, in which decoding is done at receivers and the mixture of information at interior nodes is controlled by evolutionary mechanisms. We demonstrate how our coding strategy may surpass existing end-to-end pairwise XOR coding schemes in terms of effectiveness and practicality.

We present a genetic algorithm which is distributed in two novel ways: along genotype and temporal axes. Our algorithm first distributes, for every member of the population, a subset of the genotype to each network node, rather thana subset of the population to each. This genotype distribution is shown to offer a significant gain in running time. Then, for efficient use of the computational resources in the network, our algorithm divides the candidate solutions intopipelined sets and thus the distribution is in the temporal domain, rather that in the spatial domain. This temporal distribution may lead to temporal inconsistency in selection and replacement, however our experiments yield better efficiency in terms of the time to convergence without incurring significant penalties.

Abstract — We consider the problem of minimizing the resources used for network coding while achieving the desired throughput in a multicast scenario. Since this problem is NPhard, we seek a method for quickly finding sufficiently good solutions. To this end, we take evolutionary approaches based on a Genetic Algorithm. In this paper, we extend the evolutionary algorithm that we previously proposed in three perspectives. First, whereas the previous algorithm can be applied to only acyclic networks, we devise a modified evaluation method that works also with networks with cycles. Second, we introduce a new set of GA components that in our experiments outperforms the one used in the previous algorithm. Third, we present a new framework of the evolutionary approach, where fitness evaluation and population management are done in a decentralized manner with a limited amount of coordination. The new framework enables a network coding protocol where the resources used for coding are optimized in the setup phase as the proposed evolutionary algorithm being loaded and run at each node of the network. We demonstrate the effectiveness of our algorithms by carrying out simulations on a number of different sets of network topologies. I.

We consider the issue of protection in very large networks displaying randomness in topology. We employ random graph models to describe such networks, and obtain probabilistic bounds on several parameters related to reliability. In particular, we take the case of random regular networks for simplicity and consider the length of primary and backup paths in terms of the number of hops. First, for a randomly picked pair of nodes, we derive a lower bound on the average distance between the pair and discuss the tightness of the bound. In addition, noting that primary and protection paths form cycles, we obtain a lower bound on the average length of the shortest cycle around the pair. Finally, we show that the protected connections of a given maximum finite length are rare. We then generalize our network model so that different degrees are allowed according to some arbitrary distribution, and show that the second moment of degree over the first moment is an important shorthand for behavior of a network. Notably, we show that most of the results in regular networks carry over with minor modifications, which significantly broadens the scope of networks to which our approach applies. We present as an example the case of networks with a power-law degree distribution.