Search for: All records

The ever-increasing needs of supporting real-time applications have spurred new studies on minimizing Age-of-Information (AoI), a novel metric characterizing the data freshness of the system. This work studies the single-queue information update system and strengthens the seminal results of Sun et al. on the following fronts: (i) When designing the optimal offline schemes with full knowledge of the delay distributions, a new fixed-point-based method is proposed with quadratic convergence rate, an order-of-magnitude improvement over the state-of-the-art; (ii) When the distributional knowledge is unavailable (which is the norm in practice), two new low-complexity online algorithms are proposed, which provably attain the optimal average AoI penalty; and (iii) the online schemes also admit a modular architecture, which allows the designer to upgrade certain components to handle additional practical challenges. Two such upgrades are proposed for the situations: (iii.1) The AoI penalty function is also unknown and must be estimated on the fly, and (iii.2) the unknown delay distribution is Markovian instead of i.i.d. The performance of our schemes is either provably optimal or within 3% of the omniscient optimal offline solutions in all simulation scenarios. 

One canonical example of Age-Of-Information (AoI) minimization is the update-through-queues models. Existing results fall into two categories: The open-loop setting for which the sender is oblivious of the actual packet departure time, versus the closed-loop setting for which the decision is based on instantaneous Acknowledgement (ACK). Neither setting perfectly reflects modern networked systems, which almost always rely on feedback that experiences some delay. Motivated by this observation, this work subjects the ACK traffic to an independent queue so that the closed-loop decision is made based on delayed feedback. Near-optimal schedulers have been devised, which smoothly transition from the instantaneous-ACK to the open loop schemes depending on how long the feedback delay is. The results thus quantify the benefits of delayed feedback for AoI minimization in the update-through-queues systems. 

The most commonly used setting in the coded caching literature consists of the following four elements: (i) homogeneous file sizes, (ii) homogeneous cache sizes, (iii) user-independent homogeneous file popularity (i.e., all users share the same file preference), and (iv) worst-case rate analysis. While recent results have relaxed some of these assumptions, deeper understanding of the full heterogeneity setting is still much needed since traditional caching schemes place little assumptions on file/cache sizes and almost always allow each user to have his/her own file preference through individualized file request prediction. Taking a microscopic approach, this paper characterizes the exact capacity of the smallest 2-user/2-file (N = K = 2) problem but under the most general setting that simultaneously allows for (i) heterogeneous files sizes, (ii) heterogeneous cache sizes, (iii) user-dependent file popularity, and (iv) average-rate analysis. Solving completely the case of N = K = 2 could shed further insights on the performance and complexity of optimal coded caching with full heterogeneity for arbitrary N and K. 

Streaming codes take a string of source symbols as input and output a string of coded symbols in real time, which effectively eliminate the queueing delay and are regarded as a promising scheme for low latency communications. Aiming at quantifying the fundamental latency performance of random linear streaming codes (RLSCs) over i.i.d. symbol erasure channels, this work derives the exact error probability under, simultaneously, the finite memory length and finite decoding deadline constraints. The result is then used to examine the tradeoff among memory length (complexity), decoding deadline (delay), and error probability (reliability) of RLSCs for the first time in the literature. Two critical observations are made: (i) Too much memory can adversely impact the performance under a finite decoding deadline constraint, a surprising finding not captured by the traditional wisdom that large memory length monotonically improves the performance in the asymptotic regime; (ii) The end-to-end delay of the RLSC is roughly 50% of that of the MDS block code when under identical code rate and error probability requirements. This implies that switching from block codes to RLSCs not only eliminates the queueing delay (thus 50%) but also has little negative impact on the error probability. 

Motivated by the applications for low-delay communication networks, the finite-length analysis, or channel dispersion identification, of the multi-user channel is very important. Recent studies also incorporate the effects of feedback in point-to-point and common-message broadcast channels (BCs). However, with private messages and feedback, finite-length results for BCs are much more scarce. Though it is known that feedback can strictly enlarge the capacity, the ultimate feedback capacity regions remain unknown for even some classical channels including Gaussian BCs. In this work, we study the two-user broadcast packet erasure channel (PEC) with causal feedback, which is one of the cleanest feedback capacity results and the capacity region can be achieved by elegant linear network coding (LNC). We first derive a new finite-length outer bound for any LNCs and then accompanying inner bound by analyzing a three-phase LNC. For the outer-bound, we adopt a linear-space-based framework, which can successfully find the LNC capacity. However, naively applying this method in finite-length regime will result in a loose outer bound. Thus a new bounding technique based on carefully labelling each time slot according to the type of LNC transmitted is proposed. Simulation results show that the sum-rate gap between our inner and outer bounds is within 0.02 bits/channel use. Asymptotic analysis also shows that our bounds bracket the channel dispersion of LNC feedback capacity for broadcast PEC to within a factor of Q-l (E/2)/Q-l (E). 

One main objective of ultra-low-latency communications is to minimize the data staleness at the receivers, recently characterized by a metric called Age-of-Information (AoI). While the question of when to send the next update packet has been the central subject of AoI minimization, each update packet also incurs the cost of transmission that needs to be jointly considered in a practical design. With the exponential growth of interconnected devices and the increasing risk of excessive resource consumption in mind, this work derives an optimal joint cost-and-AoI minimization solution for multiple coexisting source-destination (S-D) pairs. The results admit a new AoI-market-price-based interpretation and are applicable to the setting of (a) general heterogeneous AoI penalty functions and Markov delay distributions for each S-D pair, and (b) a general network cost function of aggregate throughput of all S-D pairs. Extensive simulation is used to demonstrate the superior performance of the proposed scheme. 

The number of devices connected to Internet of Things (IoT) and massive machine-type communication (mMTC) networks is expected to increase exponentially in the next generation of wireless communication systems, resulting in a new type of “massive” random access network. However, most of the work in this emerging field considers the single-hop setting with direct communication between the users and a fully-equipped base station. In contrast, this work explores the massive random access problem in a two-hop relay setting where users access the network through a femto- or pico-cell relay which itself only has a limited amount of bandwidth/power. We present two low-complexity relaying schemes designed to minimize power consumption and discuss their tradeoffs using numerical simulations.