Patent Description:
Distribution of content from the cloud to mobile devices is increasingly more prevalent. For example, over-the-air (OTA) software updates are provided to vehicles, media is provided to user devices in vehicles, and mobile Internet-of Things (IoT) applications consume increasing amounts of content. Distributing such content with low latency to a large number of mobile devices, some of which may have complicated mobility patterns or no pattern to their movement, presents significant challenges.

<CIT> is directed to methods and apparatus for processing requests for content received from customer devices. A decision on how to respond to a request for content is made at an edge node based on a locally maintained popularity list. The local popularity list reflects the local popularity of individual pieces of content at the edge node. A white list of content to be cached and served irrespective of popularity is sometimes used in combination with the local popularity list to make decisions as to how to respond to individual requests for content. The edge node may decidee on one of the following responses to a content request: i) cache and serve the requested content; ii) serve but don't cache the requested content; or iii) redirect the content request to another node, e.g., an alternate serving node, which can respond to the content request.

<CIT> is directed to a method of pre-fetching and preparing content in an information processing system. The method includes the steps of generating at least one content pre-fetching policy and at least one content preparation policy, wherein each of the policies are at least in part a function of context information associated with a user. The content is pre-fetched based on information contained within the at least one content pre-fetching policy. Once the content has been pre-fetched, it is prepared based on information contained within the at least one content preparation policy. The context information associated with the user includes at least one of the user's usage patterns, current location, future plans and preferences.

In accordance with common practice the various features illustrated in the drawings may not be drawn to scale. Accordingly, the dimensions of the various features may be arbitrarily expanded or reduced for clarity. In addition, some of the drawings may not depict all of the components of a given system, method or device. Finally, like reference numerals may be used to denote like features throughout the specification and figures.

Numerous details are described in order to provide a thorough understanding of the example implementations shown in the drawings. However, the drawings merely show some example aspects of the present disclosure and are therefore not to be considered limiting. Those of ordinary skill in the art will appreciate that other effective aspects and/or variants do not include all of the specific details described herein. Moreover, well-known systems, methods, components, devices and circuits have not been described in exhaustive detail so as not to obscure more pertinent aspects of the example implementations described herein.

Various implementations disclosed herein enable a network device in a network edge intelligently to decide whether to cache content for mobile devices, to allow the content to be delivered with low latency while making judicious use of available memory. For example, a networking method is performed by a network device in a network edge. The network device includes one or more processors and memory (e.g., non-transitory memory) storing instructions for execution by the one or more processors. In the method, content directed to a mobile device attached to the network edge is received from an upstream network device and is forwarded toward the mobile device. A decision is made whether to cache the content at the network device based at least in part on a popularity of the content in a region covered by the network device and a prediction error for an estimated probability that the mobile device will transition from the region to another region. The popularity is directly correlated with a first bias toward caching the content. The prediction error is inversely correlated with a second bias toward caching the content. The decision is implemented: the network device either caches the content or foregoes caching the content, in accordance with the decision.

<FIG> is a block diagram illustrating a network architecture <NUM> in accordance with some implementations. The network architecture <NUM> includes a three-tiered network edge. The first tier includes a plurality of access points to which mobile devices attach. In the example of <FIG>, the access points are road-side units (RSUs) <NUM>-<NUM> through <NUM>-<NUM> and the mobile devices are vehicles (or electronic devices in vehicles) <NUM>-<NUM> through <NUM>-<NUM>, although the access points and mobile devices are not so limited. The second tier includes a plurality of gateways (GWs) <NUM> upstream from respective RSUs <NUM>. A first gateway <NUM>-<NUM> is upstream from, and communicates with, RSUs <NUM>-<NUM> through <NUM>-<NUM>. A second gateway <NUM>-<NUM> is upstream from, and communicates with, RSUs <NUM>-<NUM> and <NUM>-<NUM>. The third tier includes a server <NUM> that is upstream from, and communicates with, the gateways <NUM>-<NUM> and <NUM>-<NUM>. In the example of <FIG>, the server <NUM> is a mobile-edge-computing (MEC) server, although the server <NUM> is not so limited.

Each of the RSUs <NUM> provides wireless network access to, and thus serves as an access point for, vehicles <NUM> (or, more generally, respective mobile devices) in respective regions <NUM>. The RSU <NUM>-<NUM> provides wireless access to a vehicle <NUM>-<NUM> in a region <NUM>-<NUM>, the RSU <NUM>-<NUM> provides wireless access to a vehicle <NUM>-<NUM> in a region <NUM>-<NUM>, and so on. A vehicle <NUM> (or, more generally, a mobile device) is said to be attached to the RSU <NUM> that it uses for wireless network access. A vehicle <NUM> may attach to an RSU <NUM> by forming a wireless connection with the RSU <NUM> (e.g., upon entering a corresponding region <NUM>, or after being turned on within a region <NUM>). A vehicle <NUM> may transition from a first region <NUM> to a second region <NUM>; the vehicle <NUM> drops its attachment to a corresponding first RSU <NUM> and attaches to a second RSU <NUM> accordingly. In the example of <FIG>, the vehicle <NUM>-<NUM> is transitioning from the first region <NUM>-<NUM> to the second region <NUM>-<NUM>. The vehicle <NUM>-<NUM> will thus drop its attachment to the RSU <NUM>-<NUM> and will attach to the RSU <NUM>-<NUM>.

All or a portion of the network devices in the network edge include memory for caching content. (The term "caching" as used herein refers to storing content locally at a particular device and does not imply that the content is stored in any particular type of memory. ) In some implementations, the network devices implement information-centric networking (ICN) or hybrid ICN, and content requests from mobile devices are ICN/hICN interests. In the example of <FIG>, the RSUs <NUM> include respective memories <NUM>, the gateways <NUM> include respective memories <NUM>, and the server <NUM> includes memory <NUM>. If a network device receives a request, originating from a vehicle <NUM>, for content that is locally cached, the network device can respond to the request by transmitting the requested content downstream toward the requesting vehicle <NUM>, without passing the request further upstream. For example, the vehicle <NUM>-<NUM> transmits a request for content to the RSU <NUM>-<NUM>. If the RSU <NUM>-<NUM> has the requested content cached in its memory <NUM>, it responds by transmitting the content to the vehicle <NUM>-<NUM>. Otherwise, the RSU <NUM>-<NUM> forwards the request upstream to the gateway <NUM>-<NUM>. If the gateway <NUM>-<NUM> has the requested content cached in its memory <NUM>, it responds by transmitting the content downstream to the RSU <NUM>-<NUM>, and thus toward the vehicle <NUM>-<NUM>. Otherwise, the gateway <NUM>-<NUM> forwards the request upstream to the server <NUM>. If the server <NUM><NUM> has the requested content cached in its memory <NUM>, it responds by transmitting the content downstream to the gateway <NUM>-<NUM>, and thus toward the vehicle <NUM>-<NUM>. Otherwise, the server <NUM> forwards the request through one or more networks <NUM> to a remote device (e.g., server) with the content (e.g., the server <NUM> goes out to the cloud to obtain the content). Caching content in the memories <NUM>, <NUM>, and/or <NUM> results in low latency for responding to content requests and also reduces network traffic by limiting the path taken by content requests. However, because the size of the memories <NUM>, <NUM>, and <NUM> is of course limited, decisions regarding whether to cache particular content items should be made intelligently.

In some implementations, a traffic controller <NUM> monitors the mobile devices and predicts future movement of the mobile devices (e.g., using a Markovian predictor with a fixed history length H). The traffic controller <NUM> estimates the probabilities that a mobile device will transition from a given region <NUM> to other regions <NUM>, and thus from attachment to a given RSU <NUM> to other RSUs <NUM>. The traffic controller <NUM> also calculates prediction errors for respective probabilities. For example, for a particular mobile device (e.g., vehicle <NUM>), the traffic controller generates a set of transition probabilities in an array P with a prediction error E. In some implementations, the prediction error is based at least in part on the presence or absence of a historical pattern of movement for the mobile device. For example, a vehicle <NUM> may have a low prediction error on weekdays, when it follows the same commute, but may have a high prediction error on weekends, when it does not follow a set pattern. The traffic controller <NUM> may estimate these transition probabilities and calculate these errors for all mobile devices (e.g., all vehicles <NUM>) at the network edge.

The traffic controller <NUM> provides the transition probabilities and errors to the server <NUM>, gateways <NUM>, and/or RSUs <NUM> of the network edge. In some implementations, the traffic controller <NUM> is communicatively coupled to the network edge through one or more networks <NUM> (e.g., the Internet, other wide-area networks (WANs), metropolitan-area networks (MAN), etc.), and transmits the transition probabilities and errors to the network devices of the network edge through the one or more networks <NUM>. The traffic controller <NUM> thus may be situated outside of the network edge (e.g., implemented in the cloud). Alternatively, the traffic controller <NUM> may be instantiated in a network device in the network edge (e.g., in the server <NUM>).

<FIG> shows a flowchart illustrating a networking method <NUM> in accordance with some implementations. The method <NUM> is performed (<NUM>) by a network device in the network edge (e.g., an RSU <NUM> or other access point, a gateway <NUM>, or the server <NUM>). In some implementations, respective instances of the method <NUM> are performed repeatedly by all or a portion of the network devices in the network edge.

In the method <NUM>, content directed to a mobile device attached to the network edge is received (<NUM>) from an upstream network device. In some implementations, the mobile device is an electronic device in a vehicle <NUM> (e.g., a mobile device that is part of the vehicle <NUM> or that is in the vehicle <NUM>). The content is forwarded (<NUM>) toward the mobile device. The content may be received (<NUM>) in response to a request for the content that the network device (or another network device) previously received from the mobile device and forwarded to the upstream device (or another upstream device).

In some implementations, an estimated probability that the mobile device will transition between regions and/or a corresponding prediction error are received (<NUM>) from the traffic controller <NUM>, as discussed above.

In some implementations, the popularity of the content in a region covered by the network device is measured (<NUM>). If the network device is an RSU <NUM> or other access point, this region is the corresponding region <NUM>. If the network device is a gateway <NUM> or server <NUM>, this region is the set of regions <NUM> for all downstream access points. To measure the popularity, the network device may count requests for the content received by the network device (e.g., requests originating from mobile devices) and/or instances of the content received by the network device (e.g., instances of the content being transmitted downstream in response to requests from mobile devices). The network device may use counters <NUM> (<FIG>) to keep these counts. The network device may perform sampling to reduce the amount of data to be stored to determine the popularity. For example, the network device samples content-item requests received at the network device and counts sampled content-item requests that are requests for the content. Alternatively, or in addition, the network device samples content items received at the network device and counts sampled content items that are instances of the content.

A decision is made (<NUM>) whether to cache the content at the network device based at least in part on (i) the popularity of the content in the region covered by the network device and (ii) the prediction error for the estimated probability. The popularity is directly correlated with a first bias toward caching the content: the higher the popularity, the more likely the network device is to cache the content. The prediction error is inversely correlated with a second bias toward caching the content: the lower the prediction error, the more likely the network device is to cache the content.

The second bias may be a function of the tier of the network edge in which the network device performing the method <NUM> is situated. For example, if the network device is an access point (e.g., RSU <NUM>) to which the mobile device is attached, then the second bias has a magnitude such that, for a given prediction error, the network device is less likely to decide to cache the content than is a respective gateway <NUM> upstream of the access point. If the network device is a gateway <NUM> upstream of the access point (e.g., RSU <NUM>) to which the mobile device is attached, then the second bias has a magnitude such that, for a given prediction error, the network device is more likely to decide to cache the content than is the downstream access point. Everything else being equal, a gateway <NUM> is thus more likely to cache content for a mobile device with a high prediction error than is an access point, in accordance with some implementations. That is, a gateway <NUM> is more tolerant of prediction error than an access point in deciding to cache content, because a mobile device with high prediction error is more likely to stay within the set of regions <NUM> covered by the gateway <NUM> than within the single region <NUM> covered by the access point. Content cached at the gateway <NUM> is thus more likely to be re-used than content cached at the access point. While the access point offers lower latency than the gateway <NUM>, a high prediction error suggests that caching the content at the access point may be wasteful of memory.

Similarly, if the network device is a gateway <NUM> upstream from an access point (e.g., RSU <NUM>) to which the mobile device is attached, then the second bias has a magnitude such that, for a given prediction error, the network device is less likely to decide to cache the content than is the upstream server <NUM>. If the network device is the server <NUM>, which is upstream of the gateway <NUM> for the access point to which the mobile device is attached, then the second bias has a magnitude such that, for a given prediction error, the network device is more likely to decide to cache the content than is the downstream gateway <NUM>. Everything else being equal, the server <NUM> is thus more likely to cache content for a mobile device with a high prediction error than is a gateway <NUM>, in accordance with some implementations.

In some implementations, the decision is further based (<NUM>) at least in part on a QoS level of the content. The QoS level is directly correlated with a third bias toward caching the content. A higher QoS level indicates a higher desired or guaranteed quality of service. Caching content helps to ensure that the quality of service is met. The bias toward caching for high QoS levels reflects this fact and helps to ensure low latency for providing content with a high QoS. In one example, OTA updates to vehicular software are assigned a high QoS to ensure that the updates are rolled out promptly. The high QoS for these updates may result from safety issues that the updates address or from a premium paid by vehicle owners.

In some implementations, the decision is not based (<NUM>) on whether other network devices in the network edge have cached the content. For example, the network device does not receive communications indicating whether the other network devices in the network edge have cached the content. Various network devices in the network edge thus decide whether to cache content independently of each other. Network traffic is therefore reduced, because network devices do not message each other regarding whether or not they have cached particular content.

In some implementations, to make the decision, a utility function is calculated that accounts for the first bias, the second bias, and any other biases relevant to the decision (e.g., the third bias relating to QoS). A determination is made as to whether the utility function satisfies (e.g., exceeds, or equals or exceeds) a threshold. If the threshold is satisfied, the decision is to cache the content. If the threshold is not satisfied, the decision is to forego caching the content.

One example of a utility function that may be used to make the decision is: <MAT> where n is the total number of biases (i.e., factors) relevant to the decision, i indexes the biases, xi is a suitably weighted (e.g., normalized) value of the bias i, and Ui(xi) is a function that indicates the degree of utility for xi. For example, <MAT> where Λ and α are constants, and α ≥ <NUM>. In another example, <MAT>.

The decision is implemented: the network device either caches (<NUM>) the content or foregoes caching (<NUM>) the content, in accordance with the decision. In some implementations, cached content is stored in the memory <NUM>, <NUM>, or <NUM> of the network device. If the memory space allocated for caching content is full, then content that was previously cached at the network device is evicted to make room for caching the new content. In some implementations, a least-recently-used (LRU) algorithm is used to determine the content to evict. For example, a k-LRU algorithm is used, in which the LRU content is evicted in favor of content that has been counted (or samples of which have been counted) at least k times, where k is an integer. The decision of step <NUM> thus may include a determination as to whether the k-times threshold has been satisfied. In other implementations, other eviction algorithms are used. For example, a least-frequently-used (LFU) algorithm is used, in which the network device maintains counts for how many times respective cached content items are received or requested and evicts the least-frequently-used content.

Steps in the method <NUM> may be combined or broken out and the sequence of the method <NUM> may be modified for steps that are not order-dependent. For example, the order of the steps <NUM>, <NUM>, and/or <NUM> may be varied (e.g., performance of the steps <NUM>, <NUM>, and/or <NUM> may overlap). Also, the decision-making of step <NUM> and/or caching of step <NUM> may be performed before, during, and/or after the forwarding of step <NUM>.

The method <NUM> thus allows network devices in the network edge to make intelligent decisions regarding whether or not to cache content. The network devices are able to balance popularity with the prediction error for mobility estimations, such that low latency for providing content is achieved without wasting memory.

<FIG> is a block diagram of a network device <NUM> according to some implementations. The network device <NUM> is an example of the network device that performs the method <NUM> (<FIG>). For example, the network device may be an RSU <NUM> or other access point, a gateway <NUM>, or the server <NUM>. While certain features are illustrated, those of ordinary skill in the art will appreciate from the present disclosure that various other features have not been illustrated for the sake of brevity, and so as not to obscure more pertinent aspects of the implementations disclosed herein. To that end, in some implementations the network device <NUM> includes one or more processing units (e.g., CPUs, network processors, etc.) <NUM>, a network interface <NUM>, a programming interface <NUM>, memory <NUM>, and one or more communication buses <NUM> for interconnecting these and various other components.

In some implementations, the memory <NUM> or a non-transitory computer-readable storage medium of the memory <NUM> stores the following programs, modules, and data structures, or a subset thereof: an optional operating system <NUM>, content-caching module <NUM>, popularity-determination module <NUM>, packet-routing module <NUM>, and database <NUM>. The operating system <NUM> includes procedures for handling various basic system services and for performing hardware-dependent tasks. The content-caching module <NUM> may include instructions for calculating a utility function <NUM> (e.g., per equations <NUM>, <NUM>, and/or <NUM>). The popularity-determination module <NUM> may include counters <NUM> for measuring the popularity of content items. The content database <NUM>, which caches content items <NUM>, may be an example of memory <NUM>, <NUM>, or <NUM> (<FIG>). The memory <NUM> or a non-transitory computer-readable storage medium of the memory <NUM> thus may include instructions for performing the method <NUM> (<FIG>).

It will also be understood that, although the terms "first," "second," etc. may be used herein to describe various elements, these elements should not be limited by these terms. For example, a first bias could be termed a second bias, and, similarly, a second bias could be termed a first bias, without changing the meaning of the description, so long as all occurrences of the first bias are renamed consistently and all occurrences of the second bias are renamed consistently. The first bias and the second bias are both biases, but they are not the same bias.

The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the claims. As used in the description of the embodiments and the appended claims, the singular forms "a", "an" and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will also be understood that the term "and/or" as used herein refers to and encompasses any and all possible combinations of one or more of the associated listed items.

Claim 1:
A networking method, comprising,
at a network device (<NUM>) in a network edge, the network device (<NUM>) comprising one or more processors and memory storing instructions for execution by the one or more processors:
receiving (<NUM>), from an upstream network device, content directed to a mobile device attached to the network edge;
forwarding (<NUM>) the content toward the mobile device;
making (<NUM>) a decision whether to cache the content at the network device (<NUM>) based at least in part on a popularity of the content in a region covered by the network device (<NUM>) and a prediction error for an estimated probability that the mobile device will transition from the region to another region, wherein the popularity is directly correlated with a first bias toward caching the content and the prediction error is inversely correlated with a second bias toward caching the content; and
implementing the decision, comprising either caching (<NUM>) or foregoing (<NUM>) caching the content at the network device (<NUM>) in accordance with the decision.