Cost Minimization in Multi-Path Communication under Throughput and Maximum Delay Constraints

We consider the scenario where a sender streams a flow at a fixed rate to a receiver across a multi-hop network, possibly using multiple paths. Data transmission over a link incurs a cost and a delay, both of which are traffic-dependent. We study the problem of minimizing network transmission cost subject to a maximum delay constraint and a throughput requirement. The problem is important for leveraging edge-cloud computing platforms to support computationally intensive IoT applications, which are sensitive to three critical performance metrics, i.e., cost, maximum delay, and throughput. Our problem jointly considers the three metrics, while existing ones only account for one or two of them. We first show that our problem is uniquely challenging, as (i) it is NP-complete even to find a feasible solution satisfying all constraints, and (ii) directly extending existing solutions to our problem results in problem-dependent maximum delay violations that can be unbounded. We then design both an approximation algorithm and an efficient heuristic. For any feasible instance, our approximation algorithm will achieve a cost no worse than the optimal, while violating the maximum delay constraint and the throughput requirement only by constant ratios. Meanwhile, our heuristic will construct feasible solutions for a large portion (over 60% empirically) of feasible instances, strictly satisfying the maximum delay constraint and the throughput requirement. We further characterize a condition under which the cost of our heuristic must be within a problem-dependent-ratio gap to the optimal. We simulate representative edge computing platforms, and observe that (i) when sacrificing 3% throughput, our approximation algorithm reduces 32% cost as compared to a greedy baseline, and satisfies the maximum delay constraint for 56% simulated instances; (ii) our heuristic solves 62% of feasible instances, and reduces 24% cost as compared to the baseline while strictly satisfying all constraints.