The emerging Federated Learning (FL) enables IoT devices to collaboratively learn a shared model based on their local datasets. However, due to end devices’ heterogeneity, it will magnify the inherent synchronization barrier issue of FL and result in non-negligible waiting time when local models are trained with the identical batch size. Moreover, the useless waiting time will further lead to a great strain on devices’ limited battery life. Herein, we aim to alleviate the negative impact of synchronization barrier through adaptive batch size during model training. When using different batch sizes, stability and convergence of the global model should be enforced by assigning appropriate learning rates on different devices. Therefore, we first study the relationship between batch size and learning rate, and formulate a scaling rule to guide the setting of learning rate in terms of batch size. Then we theoretically analyze the convergence rate of global model and obtain a convergence upper bound. On these bases, we propose an efficient algorithm that adaptively adjusts batch size with scaled learning rate for heterogeneous devices to reduce the waiting time and save battery life. We conduct extensive simulations and testbed experiments, and the experimental results demonstrate the effectiveness of our method.

Data generated at the network edge can be processed locally by leveraging the paradigm of edge computing. To fully utilize the widely distributed data, we concentrate on a wireless edge computing system that conducts model training using decentralized peer-to-peer (P2P) methods. However, there are two major challenges on the way towards efficient P2P model training: limited resources (e.g., network bandwidth and battery life of mobile devices) and time-varying network connectivity due to device mobility or wireless channel dynamics, which receives less attention in recent years. To address these two challenges, this paper studies the impact of topology construction on the P2P training performance. Specifically, we dynamically construct an efficient P2P topology, where model aggregation occurs at the edge. In a nutshell, we first formulate the topology construction for P2P learning (TCPL) problem with resource constraints as an integer programming problem. Then a learning-driven method is proposed to adaptively construct a topology at each training epoch. We evaluate the performance of our proposed algorithm through extensive simulations and physical platform. Evaluation results show that our method can improve the model training efficiency by about 11% with resource constraints, reduce the communication cost by 30% and the network traffic consumption by about 60% under the same accuracy requirement compared to the benchmarks.

Under the paradigm of edge computing, the enormous data generated at the network edge can be processed locally. To make full utilization of these widely distributed data, we focus on an edge computing system that conducts distributed machine learning using gradient-descent based approaches. To ensure the system’s performance, there are two major challenges: how to collect data from multiple data source nodes for training jobs and how to allocate the limited resources on each edge server among these jobs. In this paper, we jointly consider the two challenges for distributed training (without service requirement), aiming to maximize the system throughput while ensuring the system’s quality of service (QoS). Specifically, we formulate the joint problem as a mixed-integer non-linear program, which is NP-hard, and propose an efficient approximation algorithm. Furthermore, we take service placement into consideration for diverse training jobs and propose an approximation algorithm. We also analyze that our proposed algorithm can achieve the constant bipartite approximation under many practical situations. We build a test-bed to evaluate the effectiveness of our proposed algorithm in a practical scenario. Extensive simulation results and testing results show that the proposed algorithms can improve the system throughput 56-69 percent compared with the conventional algorithms.

Data generated at the network edge can be processed locally by leveraging the paradigm of edge computing. To fully utilize the widely distributed data, we concentrate on a wireless edge computing system that conducts model training using decentralized peer-to-peer (P2P) methods. However, there are two major challenges on the way towards efficient P2P model training: limited resources (e.g., network bandwidth and battery life of mobile edge devices) and time-varying network connectivity due to device mobility or wireless channel dynamics, which have received less attention in recent years. To address these two challenges, this paper adaptively constructs a dynamic and efficient P2P topology, where model aggregation occurs at the edge devices. In a nutshell, we first formulate the topology construction for P2P learning (TCPL) problem with resource constraints as an integer programming problem. Then a learning-driven method is proposed to adaptively construct a topology at each training epoch. We further give the convergence analysis on training machine learning models even with non-convex loss functions. Extensive simulation results show that our proposed method can improve the model training efficiency by about 11% with resource constraints and reduce the communication cost by about 30% under the same accuracy requirement compared to the benchmarks.

Mobile edge computing(MEC), as an emerging computing paradigm, pushes services away from centralized remote cloud to distributed edge servers deployed by multiple service providers(SPs), improving user experience and reducing the communication burden on core network. However, this distributed computing architecture also brings some new challenges to the network. In multi-SP MEC system, a SP prefers to use edge servers deployed by itself instead of others, which not only improves service quality but also reduces processing cost. The service placement and request scheduling strategies directly affect the revenue of SPs. Since the service popularity changes over time and the resources of edge servers are limited, the network system needs to make decisions about service placement and request scheduling dynamically to provide better service for users. Owing to the lack of long-term prior knowledge and involving binary decision variables, how to place services and schedule requests to boost the profit of SPs is a challenging problem. We formally formalize this joint optimization problem and propose an efficient online algorithm. First, we invoke Lyapunov optimization technology to convert the long-term optimization problem into a series of subproblems, then a dual-decomposition algorithm is utilized to solve the subproblem. Experimental results show that the algorithm proposed in this paper achieves nearly optimal performance, and it raises 25% and 70% profit compared to greedy and Top-K algorithms, respectively.

Traffic measurement is very important for various applications, such as traffic engineering and attack detection, in software-defined networks. Due to limited resources (e.g., computing, memory) on SDN switches, sketches have been widely used for efficient traffic measurement. Meanwhile, multiple independent sketches are required for different application requirements, such as heavy hitter detection and flow size distribution estimation. To avoid the measurement redundancy, we configure which sketch(es) will measure flow on each switch. If traffic measurement is performed on each switch without considering network routing, due to traffic dynamics, it will cause massive measurement overhead on a switch, which may exceed the switch's computing capacity. In this paper, we study the joint optimization of flow routing and sketch configuration in SDNs. We formulate this problem as an integer linear programming and prove its NP-hardness. To solve this problem, we propose a rounding-based offline algorithm and a primal-dual-based online algorithm for different application scenarios. To deal with bursty traffic, we also design an adaptive sampling mechanism for high-fidelity traffic measurement. We formally analyze the approximation performance or competitive ratio of the proposed algorithms. The extensive simulation results show the high efficiency of our proposed algorithms. For example, the online algorithm can improve the network throughput 30% compared with the state-of-the-art.

There is a fundamental and critical problem in modern mobile applications, in which the battery life of mobile devices is usually limited. Recently, some researchers prolong the life of batteries by offloading computation tasks to edge-servers which are deployed near the mobile devices. However, computing offloading causes extra delay, which may severely downgrade the user experience especially for the delay-sensitive applications. Moreover, the dynamic nature of mobile devices and the limited computation capacity of edge-servers also bring another challenges for tradeoff optimization between energy consumption and task completion latency. In this paper, we propose a dynamic computing offloading (DCL) problem, which aims to minimize the maximum energy consumption of the mobile devices with constraints on computation tasks latency in a Mobile Edge-Computing (MEC) network. To solve the problem, we consider two complementary cases: offline case (we sacrifice response time to achieve better service results) and online case (where we have to make immediate offloading decision for each computation task arrived online). For the offline case, we propose an efficient RMCL algorithm, and prove that our RMCL method achieves at least O((log m)/α + 1) of the optimum with high probability, where m is the number of computation tasks in a time slot, and α is a value depending on the minimum edge-server capacity and the maximum computation task demand, with α ≥ 1 under most practical situations. For the online case, we propose an algorithm, named OMCL, which considers a trade off between the latency and energy consumption. The performance of our proposed algorithms is evaluated by formal analysis and simulation on a small-scale system. The simulation results show that the algorithm can reduce the maximum energy consumption in a set of mobile devices by 40% compared with executing computation tasks locally.

In[1], reference [16] should be replaced as follows: [16] P. Chao, Y. Tan, and L. T. Yang, “New algorithms for the minimum-cost single-source unsplittable flow problem,” inProc. 21st Int. Conf. Adv. Inf. Netw. Appl. Workshops (AINAW), Niagara Falls, ON, Canada, May 2007.

Software defined networking (SDN) separates the data plane and control plane on independent devices. Since the data plane, consisting of switches, is responsible for packets forwarding, previous work often considers the different constraints (e.g., data link capacity and flow-table size) only in the data plane to provide better QoS for users. However, due to limited CPU processing power and low speed of flow-table updating on each switch, the control channels/links between switches and the controller often have very limited capacity, which will cause QoS performance (e.g., response time and throughput) degradation when the switch should handle a high traffic load. The goal of our paper is to achieve better QoS by jointly considering the control link constraint and other different constraints of the data plane in SDNs. We formally define the control link load balancing and low delay route deployment problems, and prove the NP-Hardness. We present two algorithms with bounded approximation factors for each problem and implement the proposed methods on our SDN testbed. Extensive simulation results and experimental results show that our algorithms can reduce control link load by about 50% and response time by about 60%, and increase the network throughput by 65% compared with previous methods.