Network coding is a paradigm in data transport that allows a network node to code information flows before forwarding them. While it has been theoretically proven that network coding saves bandwidth and increases throughput of multicast communication, it does not directly consider the quality of service (QoS) requirements of multicast routing. In this paper, we study the problem of establishing minimum-cost, multiple multicast sessions over coded packet networks to meet the statistical QoS target considering boundedend-to-end statistical delay and jitter from source to each destination. For this purpose, we first propose a path-based formulation for the problem and prove that this problem is NP-hard. Then, in order to obtain an exact solution, we present an effective and efficient decomposition approach in which the problem is decomposed in to master problem and subproblems, and the solution is built up successively by feasible path generation.Computational results on random networks show that the proposed method provides an efficient way for solving the problem, even for relatively large networks.
We consider the fundamental problem of managing a bounded size queue buffer where traffic consists of packets of varying size, each packet requires several rounds of processing before it can be transmitted out, and the goal is to maximize the throughput, i.e., total size of successfully transmitted packets. Our work addresses the tension between two conflicting algorithmic approaches: favoring packets with fewer processing requirements as opposed to packets of larger size. We present a novel model for studying such systems and study the performance of online algorithms that aim to maximize throughput.