Content caching at the network edge is an effective way of mitigating backhaul load and improving user experience. Caching efficiency can be enhanced by content recommendation and by keeping the information fresh. By content recommendation, a requested content that is not in the cache can be alternatively satisfied by a related cached content recommended by the system. Information freshness can be quantified by age of information (AoI). This article has the following contributions. First, we address optimal scheduling of cache updates for a time-slotted system accounting for content recommendation and AoI, and to the best of our knowledge, there is no work that has jointly taken into account these aspects. Next, we rigorously prove the problem's NP-hardness. Then, we derive an integer linear formulation, by which the optimal solution can be obtained for small-scale scenarios. On the algorithmic side, our contributions include the development of an effective algorithm based on Lagrangian decomposition, and efficient algorithms for solving the resulting subproblems. Our algorithm computes a bound that can be used to evaluate the performance of any suboptimal solution. We conduct simulations to show the effectiveness of our algorithm.

The notion of age of information (AoI) has become an important performance metric in network and control systems. Information freshness, represented by AoI, naturally arises in the context of caching. We address optimal scheduling of cache updates for a time-slotted system where the contents vary in size. There is limited capacity for the cache for making updates. Each content is associated with a utility function that depends on the AoI and the time duration of absence from the cache. For this combinatorial optimization problem, we present the following contributions. First, we provide theoretical results of problem tractability. Whereas the problem is NP-hard, we prove solution tractability in polynomial time for a special case where all contents have the same size, by a reformulation using network flows. Second, we derive an integer linear formulation for the problem, of which the optimal solution can be obtained for small-scale scenarios. Next, via a mathematical reformulation, we derive a scalable optimization algorithm using repeated column generation. In addition, the algorithm computes a bound of global optimum, that can be used to assess the performance of any scheduling solution. Performance evaluation of large-scale scenarios demonstrates the strengths of the algorithm in comparison to a greedy schedule. Finally, we extend the applicability of our work to cyclic scheduling.

In this paper, we study the problem of optimal scheduling of content placement along time in a base station with limited cache capacity, taking into account jointly the offloading effect and freshness of information. We model offloading based on popularity in terms of the number of requests and information freshness based on the notion of age of information (AoI). The objective is to reduce the load of backhaul links as well as the AoI of contents in the cache via a joint cost function. For the resulting optimization problem, we prove its hardness via a reduction from the Partition problem. Next, via a mathematical reformulation, we derive a solution approach based on column generation and a tailored rounding mechanism. Finally, we provide performance evaluation results showing that our algorithm provides near-optimal solutions.

Abstract Joint scheduling and routing of data flows with deadline constraints in communication networks has been attracting research interest. This type of problem distinguishes from conventional multicommodity flows due to the presence of the time dimension. In this paper, we address a flow routing and scheduling problem with delivery deadline, where the assignment of link capacity occurs in discrete units. Discrete capacity allocation is motivated by applications in communication systems, where it is common to have a base unit of capacity (e.g., wavelength channel in optical communications). We present and prove complexity results of the problem. Next, we give an optimization formulation based on a time slicing approach, which amounts to a discretization of the time into time slices to enable to formulate the deadline constraints. We then derive an effective reformulation of the problem, via which a column generation algorithm is developed. In addition, we propose a simple and fast max‐flow‐based algorithm. We use a number of networks and traffic scenarios to study various performance aspects of the algorithms.

Task offloading is a key component in mobile edge computing. Offloading a task to a remote server takes communication and networking resources. An alternative is device-to- device (D2D) offloading, where a task of a device is offloaded to some device having computational resource available. The latter requires that the devices are within the range of each other, first for task collection, and later for result gathering. Hence, in mobility scenarios, the performance of D2D offloading will suffer if the contact rates between the devices are low. We enhance the setup to base station (BS) assisted D2D offloading, namely, a BS can act as a relay for task distribution or result collection. However, this would imply additional consumption of wireless resource. The associated cost and the improvement in completion time of task offloading compose a fundamental trade-off. For the resulting optimization problem, we mathematically prove the complexity, and propose an algorithm using Lagrangian duality. The simulation results demonstrate not only that the algorithm has close-to-optimal performance, but also provide structural insights of the optimal trade-off.

Caching popular contents at edge devices is an effective solution to alleviate the burden of the backhaul networks. Earlier investigations commonly neglected the storage cost in caching. More recently, retention-aware caching, where both the downloading cost and storage cost are accounted for, is attracting attention. Motivated by this, we address proactive and retention-aware caching problem with the presence of user mobility, optimizing the sum of the two types of costs. More precisely, a cost-optimal caching problem for vehicle-to-vehicle networks is formulated with joint consideration of the impact of the number of vehicles, cache size, storage cost, and content request probability. This is a combinatorial optimization problem. However, we derive a stream of analytical results and they together lead to an algorithm that guarantees global optimum with polynomial-time complexity. Numerical results show significant improvements in comparison to popular caching and random caching.

Caching popular files at the user equipments (UEs) provides an effective way to alleviate the burden of the backhaul networks. Generally, popularity-based caching is not a system-wide optimal strategy, especially for user mobility scenarios. Motivated by this observation, we consider optimal caching with the presence of mobility. A cost-optimal caching problem (COCP) for device-to-device (D2D) networks is modeled, in which the impact of user mobility, cache size, and total number of encoded segments are all taken into account. The hardness of the problem is proved via a reduction from the satisfiability problem. Next, a lower-bounding function of the objective function is derived. By the function, an approximation of COCP (ACOCP) achieving linearization is obtained, which features two advantages. First, the ACOCP approach can use an off-the-shelf integer linear programming algorithm to obtain the global optimal solution, and it can effectively deliver solutions for small-scale and medium-scale system scenarios. Second, and more importantly, based on the ACOCP approach, one can derive a lower bound of global optimum of COCP, thus enabling performance benchmarking of any sub-optimal algorithm. To tackle large scenarios with low complexity, we first prove that the optimal caching placement of one user, giving other users' caching placements, can be derived in polynomial time. Then, based on this proof, a mobility aware multi-user algorithm is developed. Simulation results verify the effectivenesses of the two approaches by comparing them to the lower bound of global optimum and conventional caching algorithms.

Caching popular files at user equipments (UEs) provides an effective way to alleviate the burden of the backhaul networks. Generally, popularity based caching is not a system-wide optimal strategy, especially for mobility scenarios. Motivated by this observation, an optimal caching problem with respect to user mobility is investigated. To be specific, a cost-optimal caching problem (COCP) for device-to-device (D2D) networks is formulated, in which the impact of user mobility, cache size, and total number of encoded file segments are considered. Compared with the related studies, our investigation guarantees that the collected segments are non-overlapping, takes into account the cost of downloading from the network, and provides a rigorous complexity analysis. For problem solving, we first prove that the optimal caching placement of one user, giving other users' caching placements, can be derived in polynomial time. Then, based on this proof, a fast yet effective caching placement algorithm for all users is developed. Simulation results verify the effectiveness of this algorithm by comparing it to conventional caching algorithms.