17 November 2017 in IEEE Transactions on Network Science and Engineering
Identifying influential spreaders in complex networks is of paramount importance for understanding and controlling the spreading dynamics. A challenging and yet inadequately explored task is to detect such influential nodes in multilayer networks, i.e., networks that encompass different types of connections (e.g., different relationships) among the nodes, hence facilitating a multilayer structure. Our purpose is to devise a method that can accurately detect nodes able to exert strong influence over the multilayer network; the method will be based solely on local knowledge of a network's topology in order to be fast and scalable due to the huge size of the network, and thus suitable for both real-time applications and offline mining. Based on our belief that a strong influencer is a node positioned in a well-connected neighborhood, we propose a series of methods which capture in a single number the rich inter- and intra-layer connectivity of the node. Our simulations showed that the proposed measures can detect effective spreaders in both real and synthetic networks, under various settings and against various competitors.
23 March 2016 in IEEE Transactions on Communications
KPKonstantinos Poularakis
The ever increasing demand for content is straining operators' networks, thereby necessitating development of alternative content delivery mechanisms. Distributed caching architectures constitute a promising solution for mitigating the effects of demand growth by placing popular content files in proximity to users, rather than in a central site. In this paper, we study the content placement problem in multiple-level hierarchical caching networks where user requests for files are routed upwards toward content servers, satisfied by intermediate nodes if the latter have cached the requested files. Our goal is to reduce the server load by serving as many requests as possible by the caches. We show that the problem is NP-Hard in its general form, but it can be solved optimally in polynomial-time when the caches are installed on a single hierarchy path. For the general case, we develop an algorithm achieving a provably better approximation ratio than the best-known counterparts. Numerical experiments show up to 56% reduction in server load over existing algorithms, with gains increasing as the content popularity distributions get steeper and more diverse across nodes, and the cache capacities at the upper hierarchy levels increase. Our evaluation code is publicly available for the benefit of research community.
27 November 2023 in Proceedings of the ACM on Networking
In-network computing provides significant performance benefits, load reduction, and power savings. Still, an in-network service's functionality is strictly limited to a single hardware device. Research has focused on enabling on-device functionality, with limited consideration to distributed in-network computing. This paper explores the applicability of distributed computing to in-network computing. We present DINC, a framework enabling distributed in-network computing, generating deployment strategies, overcoming resource constraints and providing functionality guarantees across a network. It uses multi-objective optimization to provide a deployment strategy, slicing P4 programs accordingly. DINC was evaluated using seven different workloads on both data center and wide-area network topologies, demonstrating feasibility and scalability, providing efficient distribution plans within seconds.
26 June 2018 in IEEE Transactions on Mobile Computing
Distributed caching architectures have been proposed for bringing content close to requesters, and the key problem is to design caching algorithms for reducing content delivery delay, which determines to an extent the user Quality of Experience (QoE). This problem obtains an interesting new twist with the advent of advanced layered-video encoding techniques such as Scalable Video Coding. In this paper, we show that the problem of finding the caching configuration of video encoding layers that minimizes delivery delay for a network operator is NP-Hard, and we establish a pseudopolynomial-time optimal solution by using a connection with the multiple-choice knapsack problem. Next, we design caching algorithms for multiple network operators that cooperate by pooling together their co-located caches, in an effort to aid each other, so as to avoid large delays due to fetching content from distant servers. We derive an approximate solution to this cooperative caching problem by using a technique that partitions the cache capacity into amounts dedicated to own and other operators' caching needs. Trace-driven evaluations demonstrate up to 25% reduction in delay over existing caching schemes. As a side benefit, our algorithms achieve smoother playback for video streaming applications, with fewer playback stalls and higher decoded quality.
2 January 2023 in IEEE Transactions on Information Theory
This paper revisits the problem of sampling and transmitting status updates through a channel with random delay under a sampling frequency constraint [2]. We use the Age of Information (AoI) to characterize the status information freshness at the receiver. The goal is to design a sampling policy that can minimize the average AoI when the statistics of delay is unknown. We reformulate the problem as the optimization of a renewal-reward process, and propose an online sampling strategy based on the Robbins-Monro algorithm. We prove that the proposed algorithm satisfies the sampling frequency constraint. Moreover, when the transmission delay is bounded and its distribution is absolutely continuous, the average AoI obtained by the proposed algorithm converges to the minimum AoI when the number of samples K goes to infinity with probability 1. We show that the optimality gap decays with rate O (ln K / K ), and the proposed algorithm is minimax rate optimal. Simulation results validate the performance of our proposed algorithm.
22 February 2024 in IEEE Transactions on Mobile Computing
Federated learning (FL) algorithms usually sample a fraction of clients in each round (partial participation) when the number of participants is large and the server's communication bandwidth is limited. Recent works on the convergence analysis of FL have focused on unbiased client sampling, e.g., sampling uniformly at random, which suffers from slow wall-clock time for convergence due to high degrees of system heterogeneity (e.g., diverse computation and communication capacities) and statistical heterogeneity (e.g., unbalanced and non-i.i.d. data). This paper aims to design an adaptive client sampling algorithm for FL over wireless networks that tackles both system and statistical heterogeneity to minimize the wall-clock convergence time. We obtain a new tractable convergence bound for FL algorithms with arbitrary client sampling probability. Based on the bound, we analytically establish the relationship between the total learning time and sampling probability with an adaptive bandwidth allocation scheme, which results in a non-convex optimization problem. We design an efficient algorithm for learning the unknown parameters in the convergence bound and develop a low-complexity algorithm to approximately solve the non-convex problem. Our solution reveals the impact of system and statistical heterogeneity parameters on the optimal client sampling design. Moreover, our solution shows that as the number of sampled clients increases, the total convergence time first decreases and then increases because a larger sampling number reduces the number of rounds for convergence but results in a longer expected time per-round due to limited wireless bandwidth. Experimental results from both hardware prototype and simulation demonstrate that our proposed sampling scheme significantly reduces the convergence time compared to several baseline sampling schemes. Notably, for EMNIST dataset, our scheme in hardware prototype spends 71% less time than the baseline uniform sampling for reaching the same target loss.