By combining edge computing and parallel computing, distributed edge computing has emerged as a new paradigm to exploit the booming IoT devices at the edge. To accelerate computation at the edge,i.e., the inference tasks for DNN-driven applications, the parallelism of both computation and communication needs to be considered for distributed edge computing, and thus, the problem of Minimum Latency joint Communication and Computation Scheduling (MLCCS) is proposed. However, existing works have rigid assumptions that the communication time of each device is fixed and the workload can be split arbitrarily small. Aiming at making the work more practical and general, the MLCCS problem without the above assumptions is studied in this paper. Firstly, the MLCCS problem under a general model is formulated and proved to be NP-hard. Secondly, a pyramid-based computing model is proposed to consider the parallelism of communication and computation jointly, which has an approximation ratio of$1+\delta$, where$\delta$is related to devices' communication rates. An interesting property under such a computing model is identified and proved,i.e., the optimal latency can be obtained under arbitrary scheduling order when all the devices share the same communication rate. When the workload cannot be split arbitrarily, an approximation algorithm with a ratio of at most$2\cdot (1+\delta )$is proposed. Additionally, for handling the dynamically changing network scenarios, several algorithms are also proposed accordingly. Finally, the theoretical analysis and simulation results verify that the proposed algorithm has high performance in terms of latency. Two testbed experiments are also conducted, which show that the proposed method outperforms the existing methods, reducing the latency by up to 29.2% for inference tasks at the edge.

By combing edge computing and parallel computing, distributed edge computing has emerged as a new paradigm to accelerate computation at the edge. Considering the parallelism of both computation and communication, the problem of Minimum Latency joint Communication and Computation Scheduling (MLCCS) is studied recently. However, existing works have rigid assumptions that the communication time of each device is fixed and the workload can be split arbitrarily small. Aiming at making the work more practical and general, the MLCCS problem without the above assumptions is studied in this paper. Firstly, the MLCCS problem under a general model is formulated and proved to be NP-hard. Secondly, a pyramid-based computing model is proposed to consider the parallelism of communication and computation jointly, which has an approximation ratio of 1 + δ, where δ is related to devices’ communication rates. An interesting property under such computing model is identified and proved, i.e., the optimal latency can be obtained under arbitrary scheduling order when all the devices share the same communication rate. When the devices own different communication rates, the optimal scheduling order is also obtained. Additionally, when the workload cannot be split arbitrarily, an approximation algorithm with ratio of at most 2 (1 + δ) is proposed. Finally, the theoretical analysis and simulation results verify that the proposed algorithm has high performance in terms of latency. Two testbed experiments are also conducted, which show that the proposed method outperforms the existing methods, reducing the latency by up to 29.2% in real-world applications.

Multicast is a fundamental function in network traffic engineering, allowing data traffic to be delivered from the source node to multiple destinations efficiently. To ensure the reliability and security of data traffic, NFV-enabled multicast (Network Function Virtualization) has emerged as a promising technology to reduce deployment and maintenance costs in mobile edge clouds, and has drawn extensive researching interests recently. However, existing works all assume that the Service Function Chain (SFC) follows a fixed-order, which greatly limits its application. Therefore, in this paper, we propose the first work to address the sequential SFC embedding problem without a fixed order for NFV-enabled multicasting in mobile edge clouds. Firstly, we formulate such a minimum cost SFC embedding problem and prove it to be NP-hard. Secondly, we propose a min-path breadth-first based progressive embedding algorithm (MBPE) for NFV-enabled multicasting, which achieves an approximation ratio of 1+K, where K represents the approximation ratio of the Steiner tree problem. Finally, the experiments demonstrate the high efficiency of the proposed method compared to the state-of-the-art algorithms.