Proactive Content Delivery for Vehicles over Cellular Networks: the Fundamental Bene fits of Computing and Caching

Jiping Jiao, Xuemin Hong,2, Jianghong Shi,2,＊

1 Department of Communications Engineering, School of Information Science and Technology, Xiamen University, Xiamen 361005, China

2 Key Laboratory of Underwater Acoustic Communication and Marine Information Technology, Ministry of Education of China,Xiamen University, Xiamen 361005, China

Abstract: The emergence of self-driving technologies implies that a future vehicle will likely become an entertainment center that demands personalized multimedia contents with very high quality. The surge of vehicular content demand brings significant challenges for the fifth generation (5G) cellular communication network. To cope with the challenge of massive content delivery, previous studies suggested that the 5G mobile edge network should be designed to integrate communication, computing, and cache (3C) resources to enable advanced functionalities such as proactive content delivery and in-network caching.However, the fundamental bene fits achievable by computing and caching in mobile communications networks are not yet properly understood. This paper proposes a novel theoretical framework to characterize the tradeoff among computing, cache, and communication resources required by the mobile edge network to fulfill the task of content delivery.Analytical and numerical results are obtained to characterize the 3C resource tradeoff curve.These results reveal key insights into the fundamental bene fits of computing and caching in vehicular mobile content delivery networks.

Keywords: content delivery; mobile edge network; vehicular network

I. INTRODUCTION

Self-driving vehicles are becoming a commercial reality, setting free the attentions of onboard passengers from the driving tasks. This gives an unprecedented opportunity for future vehicles to become moving entertainment centers [1]-[3]. The emerging vehicular media has different characteristics compared with the other conventional media types [4] [5].It differs from TV and PC media by its high mobility. Moreover, it differs from the mobile phone by a much better media interface with larger screen size. This means that the vehicular media prefers high quality contents such as high-resolution video, which generates a large volume of data. Consequently, the vehicular media is expected to bring a new surge of mobile data demand, which would impose signi ficant challenges for future cellular communication networks.

Unfortunately, the traditional connection-centric cellular network paradigm, which is designed for symmetric unicast communications, is found to be inefficcient in supporting massive content delivery services characterized by asymmetric multicast communications[6]. Recently, a novel content-centric design philosophy has been suggested to improve the efficciency of content delivery in mobile edge networks [7]-[12]. The underlying rationale of this new philosophy is to exploit content delivery’s distinctive features. For example: 1)content data can be jointly coded and cached in distributed facilities [7]-[9]; 2) content demand (i.e., user preference for contents) can be predicted with good accuracy using big data and recommender technologies [10] [11];3) user demand is highly concentrated to a small subset of popular contents [12].

Compared with the mobile phone media,vehicular media offers a better environment to exploit all the three features of content delivery [13] [16]. First, vehicles can be equipped with a large-volume on-board cache [17]. Second, the beginning and end time of a vehicular content consumption event, which is the same as the traveling duration of a particular trip,can be accurately predicted using transportation big data technologies [14] [18]. Third,compared with the mobile phone media, vehicular media is perceived as a less-personal media by users [13] [15]. This means that the vehicular media can have a higher concentration on popular contents. By exploiting the three features of content delivery, novel schemes such as proactive caching and in-network caching have been proposed to improve the effectiveness of content delivery over mobile communication networks [19] [20]. More generally, it is widely believed that the mobile network should take a holistic approach to jointly utilize the communication, computing,and cache (3C) resources for content delivery,leading to the so-called "3C" design [7] [21].

From the theoretical perspective, it is important to understand how investments in computing and cache resources are related to the communication performance gain. This is called the 3C tradeoff problem, as the 3C resources are intuitively exchangeable. It is a non-trivial research challenge to choose proper measures for 3C and integrate these measures into a coherent and tractable theoretical framework. In the literature, the 3C tradeoff problem has been addressed by two independent research efforts in different context. The first effort focused on a joint caching and wireless multicasting scheme, where the computing resource is measured by the signal processing power and the cache resource by storage space [3]. The communication performance is measured by a new definition of"effective capacity". The second effort considered the 3C tradeoff problem in the context of coded caching, where the computing resource is measured by degrees of freedom in signal processing and the cache resource by storage space [22] [23]. Unlike these two efforts, this paper considers a different type of caching schemes with different measures of the 3C resources.

In this paper, we study the 3C tradeoff problem for an important type of caching scheme called proactive content caching [24]-[26]. To our best knowledge, our paper is the first attempt to study the 3C tradeoff problem for proactive caching in mobile networks.To this end, we propose a novel theoretical framework, in which the computing resource is measured by the scale and accuracy of user demand prediction, the cache resource is measured by the number of cache-enabled network nodes, and the communication performance is measured by communication hops in the mobile edge network. Our framework is shown to be useful in revealing important insights into the fundamental benefits of computing and caching in proactive mobile content delivery networks.

The remainder of the paper is organized as follows. Section II describes the system model. Sections III and IV derive the performance gains achievable by computing and caching,respectively. Section V further characterizes the 3C tradeoff, followed by numerical results in Section VI. Finally, conclusions are drawn in Section VII.

II. SYSTEM MODEL

2.1 General settings and assumptions

Fig. 1. Typical mobile edge network and its logically tree-like topology.

Fig. 2. Content delivery network with a complete 5-tree topology.

As shown in figure 1, a typical mobile edge network consists of multiple fiber rings to aggregate trafficc. Such a network can be logically treated as a tree network. Therefore,the content delivery network we considered includes an original content server (outside the mobile edge network), a mobile edge network with a tree topology, and multiple vehicular users connected to the leaves of the tree.The leaves of the tree represent base stations(BSs). In the rest of this paper, the term “user”refers to a vehicular user (i.e., on-board vehicular media center) instead of a conventional mobile user. Moreover, the users with a high demand/interest on the content considered are calledcontent-interested users, otherwise they are calledcontent-uninterested users. The proactive content delivery scheme we considered includes the following four steps:

1) User demand prediction: predict the user demand (i.e., interest) for a given piece of popular content;

2) Proactive multicasting: multicast the content to the users predicted as ones with a high demand for on-device caching;

3) Proactive network caching: store copies of the content in caching facilities of the mobile edge network;

4) On-demand service: serve users’ requests by the nearest cache (either device or network cache).

Due to page limits, our discussion in this paper is constrained to the following simplifying assumptions. First, we assume universal caching facility, which means all nodes in the mobile edge network can cache content. Second, we assume homogeneous user demand distribution, which means the users who are interested on a particular content are uniformly distributed among all leaves (BSs). Third,the network topology is assumed to be a completeM-tree with a content server connected to the root of the tree, as shown in figure 2.The above assumptions allow us to reveal closed-form insights into the following question: consider the task of delivering a piece of content to a subset of content-interested users in the network, how many computing, cache,and communication resources are required to ful fill this task?

2.2 Measures of 3C resources

Novel measures are introduced in our paper for quantitative evaluation of the 3C resources.The cache resource, denoted byγ, is measured by the number of content copies stored in the network (excluding user devices). LetT*=(V,E) denote a completeM-tree, whereVis the set of vertices andEis the set of edges. For every vertexvi∈V, we uselito denote the level ofvi, i.e., the number of hops betweenviand the content server. The height of a treeT*is denoted asL. The treeT*with heightLhas(ML-1)/(M-1) vertexes andML-1leaves. It is easy to see that the cache resourceγis an integer ranging from 0 toML-1. In the extreme case of full caching, all leaves of the tree cache a copy of the content.

The computing resource is measured by the scale and accuracy of user demand prediction. LetUdenote the set of all users in the network. Computations are performed on a subsetusers to predict their interests on a particular content. The scale of predication is measured by the integerψ. We assume that the computation over a user yields a binary output: whether the user becomes a recommendation user or not. We useURto denote the set of recommendation users, for which the content will be proactively push to the user devices via a single multicast. LetUIdenote the set of users actually interested on the content. The accuracy of the prediction is modeled by a probabilistic binary model as illustrated in figure 3, wherepAandpMare probabilities of correct and missed recommendations, respectively. The computing resource is jointly characterized byψtogether withpA(orpM).

The communication performance is measured by the total number of transmission hops within the mobile edge network. We note that in this paper, our main focus is on the wired backhaul links of the mobile communication network rather than the radio interface. The number of communication hops is directly related to the traffic volume in the backhaul,thus it is a widely used metric for measuring the benefits of mobile edge caching systems,e.g. [27]-[29]. To better indicate the advantage of proactive content delivery, we consider a baseline scheme of pure on-demand content delivery. In this scheme, content-interested users independently pull contents from the original server, so that each request requiresLtransmission hops. The reduced number of hops due to predictive multicasting and network caching are called computing gain and caching gain, respectively, and denoted bygΨ(ψ) andgΓ(γ), respectively. The total gaingΨ,Γ(ψ,γ), called computing-caching gain or communication gain, is regarded as a function ofψandγin this paper. Our goal is to establish the expressions forgΨ(ψ),gΓ(γ), andgΨ,Γ(ψ,γ).

Fig. 3. Definition of the computing accuracy.

III. COMPUTING GAIN

This section aims to establish the computing gaingΨ(ψ) as a function of the computing resourceψ. LetXRI(ψ) be the number of correct recommendations for a given value ofψ, it is a discrete random variable that takes integer values ranging from 0 to min(ψ,|UI|). The probability mass function (PMF) ofXRI(ψ) is given by

whereYis the number of predicted users who are contained inUI. It is easy to see thatYfollows a hyper-geometric distribution with a PMF given by

Proposition 1.Given the network topology and computing accuracypM(orpA), the computing gain is a function ofψgiven by

For a given scenario, parameterskαandkβbecome constants. In this case, Proposition 1 shows that the computing gain is a linear function of the computing scaleψ, while the computing accuracypAmainly affects the slope of the linear function.

IV. CACHING GAIN

4.1 The problem of optimal cache placement

Derivation of the optimal caching gain is less straightforward because it involves an integer optimization problem described in this subsection. Forvi∈V, de fine a binary parameterxito indicate the caching state ofvi, wherexi=1 means thatvicaches content and otherwisexi=0. The vertex withxi=1 is also called a cache vertex. The cache placement policy forT*is a vector comprised of the caching states of all

We are interested in the maximum caching gain, which is the output of the following optimization problem known as the cache placement problem (P1)

For an arbitrary network, the cache placement problem is proved to be NP-hard. However, if the network topology is a completeM-tree and the user demand distribution is uniform across all BSs, we propose an optimal algorithm in algorithm 1.

Proposition 2.If the network topology is a completeM-tree and the user demand follows uniform distribution, Algorithm 1 will yield the optimal cache placement results.

A brief proof of this proposition is given in Appendix I.

4.2 Caching gain and its approximations

Because Algorithm 1 is an optimal algorithm,it yields the following proposition.

Proposition 3.Given a completeM-treeT*,suppose that each leaf ofT*is connected to only one content-interested user. The optimal caching gain is given by

We note that Propositions 2 and 3 are only valid for a completeM-tree with a uniform demand pro file. For an arbitrary topology and demand pro file, the cache placement problem is NP-hard and is usually solved by heuristic algorithms [23]. In (16), the impact of cache resource on the caching gain is not straightforward. To obtain better insight, we further present two approximations of (16). Removing the ceiling function in yields the first approximation (Approx I) given by

whereζis determined by (14) as before. Then a further removal of the flooring function from leads to an even simpler approximation (Approx II) given by

As we will see later in Section VI, both approximations are fairly accurate. Eqn. (18)reveals a key insight that the caching gain is approximately a logarithm function of the cache resource.

V. 3C TRADEOFF

Based on the results in Sections III and IV,this section further derives the overall 3C tradeoff. We suppose that each leaf is connected tonAusers among whomnIcontent-interested users are contained. ThenT*has a total ofusers andcontent-interested users. By definition, the parameterskαandkβin (7) can be calculated as, respectively.

LetkΓ(ψ) be the number of the remaining content-interested users of a leaf after multicasting, we have

Eqns. (7) and (20) leads to the following proposition.

Proposition 4.For a network that jointly applies proactive multicasting and proactive caching, the overall computing-caching gain is given by

Proposition 4 implies that given a targeted communication performance, the computing and cache resources are exchangeable to a certain extent. We call this exchange relationship the computing-caching tradeoff, which can be characterized by the following equation

where the computing resourceψis expressed as a function of the cache resourceγ.

VI. NUMERICAL RESULTS AND DISCUSSIONS

6.1 Numerical results

This section presents numerical results to illustrate the theoretical findings derived previously. We consider a scenario with a complete 5-tree with height 4. Each leaf is connected to a constant number of users that consist of 20 content-interested users and 30 content-uninterested users. The total number of users is capped to be 6250.

Fig. 4. Computing gain as a function of the computing resourceψ with varying pA.

Fig. 5. Exact optimal caching gain and its two approximations as functions of the cache resourceγ under the assumption that each leaf is connected to only one content-interested user.

Figure 4 shows the computing gain as a function of the computing scaleψwith varying values of computing accuracypA. The gain is shown to be a linear function ofψ. In addition,it can be observed that a higher prediction accuracy (i.e., greater values ofpA) leads to a steeper slope of the liner curve.

Figure 5 shows the caching gainγas a function of cache resourceγaccording to (16).Without loss of generality, the average demand of each BS is normalized to 1. Whenγ=125,all BS will have a copy of the target content andgΓ*(γ) will reach its maximum value at 500. The caching gain is shown to be a discontinuous curve divided into four segments.The boundaries of the segments occur atγ=5i-1,i=1,2,3. The interval of thei-th segment is 5i-5i-1, which increases exponentially withi. We note that each segment contributes to the same amount of increased gains. This implies that the slope of each segment decreases logarithmically. In figure 5,gΓ*(γ) is compared with its two approximations given by (17) and (18).We can see that both approximations are fairly accurate. The normalized mean square root error of the two approximations are 0.013%and 0.29%, respectively.

Figure 6 shows the 3C tradeoff in 3-dimension based on (21). It can be observed that increasing the computing and cache resources can lead to greater gains. Clearly, computing and cache resources are exchangeable for a targeted communication performance. Finally,according to (21), figure 7 shows the computing-caching trade-off curves with varying values of communication gaingΓ*(γ) and computing accuracypM. The trade-off curves are shown to be discontinuous with multiple segments. The segment intervals are identical to the intervals shown in figure 7. While each segment is a slightly concave curve, the overall tendency appears to be a convex one. This implies that investment in the cache resource is initially effective, but increasing computing resource is more effective when the gains are already high.

6.2 Discussions and future work

We note that in this paper, the proposed “3C tradeoff” theoretical framework is only applied to a primitive scenario. In the future work,many extensions can be sought by applying the framework to more general scenarios. A few promising directions are brie fly discussed below.

1) Arbitrary network topology:The problem of optimal cache placement in an arbitrary network topology has been proven to be NP-hard. Similarly, evaluation of the computing gain in an arbitrary network requires solving the Steiner tree problem (i.e., constructing a shortest path multicast tree), with is also NP-hard in general. Nevertheless, effective algorithms exist to find sub-optimal solutions of the cache placement problem and multicast tree construction problem. Therefore, the suboptimal caching gain and computing gain,which can be interpreted as lower bounds, can be evaluated by numerical methods. Furthermore, once we retreat to special types of network topologies such as tree or grid, optimal algorithms with polynomial complexity may exist to find the optimal caching and computing gains effectively.

2) User mobility:Generally speaking, high user mobility will have an averaging effect on the caching gain because a single user demand will be spread over multiple BSs. In this case,one can expect a general tendency to place the cache closer to the root, especially when the number of cache is small. New algorithms can be sought to find the optimal caching policy considering user mobility. The computing gain, on the other hand, will not be much affected by the user mobility as long as the multicast step can be completed within a short time, during which the user-BS association remains unchanged.

3) Multiple contents and arbitrary user demand:In practice, each content file may have a different (arbitrary) user demand profile. Because content files can be multicasted separately, the (averaged) computing gain can be evaluated as a statistical average over all possible demand profiles. When the overall computing resource is limited, certain scheduling and prioritization mechanisms are required to compute a subset of content files(e.g., the most popular files) that are likely to yield higher computing gains. Similarly, once the cache resource (e.g., cache space and location) is limited, maximizing the caching gain requires certain prioritization over different contents. Joint prioritization of contents for different purposes (i.e., maximizing computing gain and caching gain) is an interesting topic to be investigated.

Fig. 6. Communication gain as a function of the computing resourceψ and cache resourceγ with pA=0.75.

Fig. 7. Computing-caching tradeoff with varying computing accuracy for fixed communication gains gΨ,Γ at 8000, 9000, and 10000.

Fig. 8. Example on feasible cache placement types used in the proof of Proposition 2.

VII. CONCLUSIONS

In this paper, we consider the problem of proactive content delivery over cellular communications networks for vehicular media applications. A theoretical framework has been proposed to measure the communications,computing, and cache resources by transmission hops, scale and accuracy of user demand prediction, and number of cached copies, respectively. Under the assumptions of complete tree topology and homogeneous user demand distribution, closed-from results have been derived to characterize the 3C resource tradeoff.It has been found that to ful fill a content delivery task, investments into the computing and cache resources will lead to linear and logarithmical reductions on the required communication resource, respectively.

Appendix I. Brief Proof of Proposition 2

Here we only provide a brief outline of the proof. Letζbe the integer that satisfiesMζ-1≤γ

Let the numbers of instances of types I and II benaandnb, respectively. Maximizing the caching gain means solving the following integer programming problem

Consequently, the expressions in can be determined from the solution of problem and the proof is completed.

ACKNOWLEDGEMENT

The authors acknowledge the support from the Natural Science Foundation of China (Grant No. 61571378).