  Network coding (NC), when combined with multipath routing, enables a linear
programming (LP) formulation for a multi-source multicast with intra-session
network coding (MISNC) problem. However, it is still hard to solve using
conventional methods due to the enormous scale of variables or constraints. In
this paper, we try to solve this problem in terms of throughput maximization
from an algorithmic perspective. We propose a novel formulation based on the
extereme flow decomposition technique, which facilitates the design and
analysis of approximation and online algorithms. For the offline scenario, we
develop a fully polynomial time approximation scheme (FPTAS) which can find a
$(1+\omega )$-approximation solution for any specified $\omega>0$. For the
online scenario, we develop an online primal-dual algorithm which proves
$O(1)$-competitive and violates link capacities by a factor of $O(\log m)$,
where $m$ is the link number. The proposed algorithms share an elegant
primal-dual form and thereby have inherent advantages of simplicity,
efficiency, and scalability. To better understand the advantages of the
extereme flow decomposition approach, we devise delicate numerical examples on
an extended butterfly network. We validate the effects of algorithmic
parameters and make an interesting comparison between the proposed FPTAS and
online algorithm. The results show that the online algorithm has satisfactory
performance while keeping the overall link utilization acceptable compared with
the FPTAS.
