INFOCOM 2019 Papers

There is an increasing interest in a new machine learning technique called Federated Learning, in which the model training is distributed over mobile user equipments (UEs), and each UE contributes to the learning model by independently computing the gradient based on its local training data. Federated Learning has several benefits of data privacy and potentially a large amount of UE participants with modern powerful processors and low-delay mobile-edge networks. While most of the existing work focused on designing learning algorithms with provable convergence time, other issues such as uncertainty of wireless channels and UEs with heterogeneous power constraints and local data size, are under-explored. These issues especially affect to various trade-offs: (i) between computation and communication latencies determined by learning accuracy level, and thus (ii) between the Federated Learning time and UE energy consumption. We fill this gap by formulating a Federated Learning over wireless network as an optimization problem FEDL that captures both trade-offs. Even though FEDL is non-convex, we exploit the problem structure to decompose and transform it to three convex sub-problems. We also obtain the globally optimal solution by charactering the closed-form solutions to all sub-problems, which give qualitative insights to problem design via the obtained optimal FEDL learning time, accuracy level, and UE energy cost. Our theoretical analysis is also illustrated by extensive numerical results.

vNUMA is the most recent technology used by hypervisors to deal with Non Uniform Memory Access (NUMA) machines, which currently composed most datacenters. vNUMA consists in presenting to the virtual machine (VM) the initial mapping (at boot time) of its virtual resources to physical resources. By this way, all NUMA optimizations implemented by almost all VM’s OS (e.g. Linux) can become effective. However, in order to be effective itself, vNUMA imposes that the initial resource mapping of the VM should remain unchanged during the VM lifetime. Current hypervisors enforce this requirement by avoiding virtual resource migration (between different NUMA nodes, in the same machine), VM migration (between different machines), and memory ballooning.However, we found that memory flipping the most efficient network virtualization approach violates the above requirement. In other words, a VM which performs network operations leads the hypervisor implicitly performs memory page migrations. In this paper, we show that violating this requirement can degrade performance by up to 18%. We present two solutions which mitigate the issue. We prototype these solutions in Xen hypervisor, a popular open source hypervisor, which is widely used by Amazon Web Services. The evaluation results, performed with well known benchmarks, show that our two solutions are able to almost cancel the issue, while keeping memory flipping effective.

We consider in-memory key-value stores used as caches, and their elastic provisioning in the cloud. The cost associated to such caches not only includes the storage cost, but also the cost due to misses: in fact, the cache miss ratio has a direct impact on the performance perceived by end users, and this directly affects the overall revenues for content providers. Our aim is to adapt dynamically the number of caches based on the traffic pattern, to minimize the overall costs.We present a dynamic algorithm for TTL caches whose goal is to obtain close-to-minimal costs. We then propose a practical implementation with limited computational complexity: our scheme requires constant overhead per request independently from the cache size. Using real-world traces collected from the Akamai content delivery network, we show that our solution achieves significant cost savings specially in highly dynamic settings that are likely to require elastic cloud services.

We consider a natural scheduling problem which arises in many distributed computing frameworks. Jobs with diverse resource requirements (e.g. memory requirements) arrive over time and must be served by a cluster of servers, each with a finite resource capacity. To improve throughput and delay, the scheduler can pack as many jobs as possible in the servers subject to their capacity constraints. Motivated by the ever-increasing complexity of workloads in shared clusters, we consider a setting where the jobs' resource requirements belong to a very large number of diverse types or, in the extreme, even infinitely many types, e.g. when resource requirements are drawn from an unknown distribution over a continuous support. The application of classical scheduling approaches that crucially rely on a predefined finite set of types is discouraging in this high (or infinite) dimensional setting. We first characterize a fundamental limit on the maximum throughput in such setting, and then develop oblivious scheduling algorithms that have tow complexity and can achieve at least 1/2 and 2/3 of the maximum throughput, without the knowledge of traffic or resource requirement distribution. Extensive simulation results, using both synthetic and real traffic traces, are presented to verify the performance of our algorithms.

Emerging communication technologies allow to reconfigure the physical network topology at runtime, enabling demand-aware networks (DANs): networks whose topology is optimized toward the workload they serve. However, today, only little is known about the fundamental algorithmic problems underlying the design of such demand-aware networks. This paper presents the first bounded-degree, demand-aware network, ct-DAN, which minimizes both congestion and route lengths. The designed network is provably (asymptotically) optimal in each dimension individually: we show that there do not exist any bounded-degree networks providing shorter routes (independently of the load), nor do there exist networks providing lower loads (independently of the route lengths). The main building block of the designed ct-DAN networks are ego-trees: communication sources arrange their communication partners in an optimal tree, individually. While the union of these ego-trees forms the basic structure of cl-DANs, further techniques are presented to ensure bounded degrees (for scalability).

We consider the problem of allocating wireless and computing resources to a set of autonomous wireless devices in an edge computing system. Devices in the system can decide whether or not to use edge computing resources for offloading computing tasks so as to minimize their completion time, while the edge cloud operator can allocate wireless and computing resources to the devices. We model the interaction between devices and the operator as a Stackelberg game, prove the existence of Stackelberg equilibria, and propose an efficient decentralized algorithm for computing equilibria. We provide a bound on the price of anarchy of the game, which also serves as an approximation ratio bound for the proposed algorithm. Our simulation results show that the joint allocation of wireless and computing resources by the operator can halve the completion times compared to a system with static resource allocation. At the same time, the convergence time of the proposed algorithm is approximately linear in the number of devices, and thus it could be effectively implemented for edge computing resource management.

Identifying the accurate location of small objects is a key element of Internet of Things (IoT). This paper investigates the feasibility of tracking the real-time location of a completely passive retroreflector using visible light for IoT applications. Existing ultra-low power visible light retroreflector systems modulate light with a liquid crystal display (LCD) shutter, which is powered by a solar cell. However, the solar cell costs additional space exclusively for energy harvesting, and it may not be able to supply enough power to the advanced power-hungry LCD shutter and its driver circuit. To eliminate the power supply, we design, implement and evaluate PassiveRETRO, an enhanced retroreflector-based visible light localization system. The PassiveRETRO system completely eliminates the necessity of any electronic component on the IoT devices. Polarization-based modulation and bandpass optical filters are adopted to identify the retroreflected optical signal and create multiple channels. Each IoT device operates on a specific range of the visible light spectrum. Optical rotatory dispersion is further applied to mitigate the mutual interference among different channels. Experimental results from our prototyped system show that PassiveRETRO is robust to environmental reflection and can still achieve centimeter-level location accuracy when multiple IoT devices are deployed.