Assessing the Feasibility of Web-Request
Prediction Models on Mobile Platforms

Prefetching has yielded a large body of work since the birth of the Internet [16, 1, 17, 2, 3, 4, 5, 6, 7, 8, 9, 10, 18, 19, 11, 20], and has been shown promising on mobile platforms recently [13]. Related work includes identifying performance bottlenecks [42, 43, 44], balancing trade-offs between prefetching benefits and waste [45, 46], and content-based techniques  [7, 6, 14, 5] as discussed earlier.

History-based prefetching has remained largely unexplored on mobile platforms. Prior work has mainly focused on mobile browsers [47, 48, 49, 50, 51, 32], while missing mobile apps where users spend over 80% of their time [52]. The few techniques targeting mobile apps are restricted to specific domains, such as social media [53], video streaming [54, 55], and ads [31]. We believe this restriction is caused by the already mentioned challenge of accessing user data, limiting history-based prefetching to specific applications and/or domains with public data (e.g., Twitter [53]). To mitigate this challenge, our work explores a novel strategy of assessing history-based prefetching across different domains, by relying on small amounts of user data. The closest work to ours is the already discussed evaluation of one history-based prediction algorithm (MP [40]) using data collected during one year from 25 iPhone users [8]. By contrast, our conclusions are based on four algorithms, including MP, and a much larger user base but over a much shorter time period.

History-based prefetching consists of three phases: training the prediction model based on the historical data; predicting future requests based on the trained model; and prefetching requests based on the prediction results and runtime conditions.

In the training phase, a prediction model is trained with past requests to capture their relationship based on a prediction algorithm (e.g., the probability of making a given request next). One prediction algorithm can be used to produce multiple prediction models by taking as input different training data, such as different numbers of past requests. In the predicting phase, the trained model is used to predict future requests based on the current context (e.g., the current request) and the prediction algorithm. Finally, in the prefetching phase, certain predicted requests are prefetched based on runtime conditions, such as battery life and cellular-data usage [45].

Our study’s goal is to assess the applicability of existing prediction algorithms that are most likely candidates for effective use on mobile platforms. The algorithm selection is guided by our focus on small models. We thus exclude algorithms that rely on large amounts of training data, such as those using neural networks (e.g., LSTM [56]). We specifically include the MP algorithm [40] since it is used in the closest related study [8]. Finally, we select two additional algorithms—DG [10] and PPM [9]—that are widely used to predict web requests [57, 58, 59, 60, 61, 62, 63]. Note that there are multiple variations of the three selected algorithms [57, 58, 64, 59, 60, 61, 65, 66, 11]; a detailed summary can be found in a survey [12]. The variations in question target specific characteristics of traditional browsers, such as web-page structure [64], and do not carry over to mobile platforms. We thus rely on the originally defined algorithms.

Most-Popular (MP) [40] maintains a list of the most-popular subsequent requests for each request in the training set. In the training phase, MP adds next requests within a specified window to the current request’s list and stores their occurrences. In the predicting phase, MP predicts the most-popular requests.

Dependency Graph (DG) [10] trains a directed graph indicating the dependencies among the requests, where nodes represent requests and arcs indicate that a target node is visited after the original node within a window. Each arc has a weight that represents the probability that the target node will be visited next. In the predicting phase, DG predicts future requests based on their probabilities stored in the dependency graph.

Prediction-by-Partial-Match (PPM) [9] uses a high-order Markov model that is context-sensitive since it considers the order of requests. In the training phase, it builds a trie structure [67] that indicates the immediate-followed-by relationship of the past requests. In the predicting phase, it predicts future requests whose parents match the previous $N$ requests.

We focus on the accuracy of prediction models built in the first two phases of the workflow, i.e., training and predicting. The third, prefetching phase involves trading off runtime conditions, studied by a complementary body of research [45, 46]. We exclude such runtime factors since they would taint the results of the models’ accuracy (e.g., failing to prefetch requests due to a third-party server’s errors). Moreover, the expiration of the prefetched requests may vary depending on when the experiments are conducted, which would introduce additional bias into our results. Currently, determining whether a request has expired remains an open challenge as the HTTP headers [68] (e.g., Cache-Control, Expires) are not trustworthy [13]. Thus, to eliminate runtime variations and fairly assess the models’ accuracy, we assume ideal runtime conditions: each predicted request will be prefetched and will not expire.

As mentioned earlier, our prediction models are tailored to individual users based on their past behaviors. This is motivated by today’s stringent regulations limiting personal data access. This has shifted recent research to “on-device” prediction, to avoid exporting sensitive user data to servers [69, 70, 71]. At the same time, this trend of client-side prediction highlights the need for small prediction models since mobile devices are resource-constrained. We thus also assess the resource consumption of different prediction models trained on-device.

Figure 1 depicts HipHarness’s workflow, comprising six customizable components that can be reused, extended, or replaced as needed. For instance, one can explore how much training data to use with a given prediction algorithm by varying Training Selection and reusing the remaining components.

HipHarness takes Historical Requests as input. Each component (shaded boxes) are either reused from existing components, or provided anew if unavailable. Historical Requests are past requests used to generate the intermediate outputs of Training Requests, Trigger Requests, and Test Requests based on the logic defined in Training Selection, Trigger Selection, and Test Selection, respectively. Training Requests are used to build the Prediction Model. Trigger Requests triggers the prediction of subsequent requests, such as the current request. Finally, Test Requests are the future requests used to evaluate the Prediction Model; they represent the “ground truth”.

The three intermediate outputs make the prediction and produce the final Test Results to evaluate the Prediction Model. The Training Engine implements the algorithm used to train a specific Prediction Model, such as the dependency graph in DG [10], based on the selected Training Requests. Optionally, the trained Prediction Model can be updated dynamically (dashed arrow) while being evaluated: Test Requests become historical requests after being tested, and can be used to train the Prediction Model. Prediction Engine implements the algorithm that predicts subsequent requests based on Trigger Requests and the trained Prediction Model. Finally, when evaluating the Prediction Model, Test Engine iteratively invokes Prediction Engine with a series of Test Requests. Prediction Engine selects $N$ requests that immediately precede each Test Request to obtain a set of Predicted Requests. Test Engine then compares the Predicted Requests with the corresponding Test Requests (i.e., “ground truth”) and outputs the Test Results that contain the information needed to calculate the evaluation metrics of interest (see Section IV-C).

HipHarness supports “plug and play” by tuning and/or replacing each of the components to explore different research questions. The Training Selection, Trigger Selection, and Test Selection components can be customized based on different selection strategies. For example, different parts of Historical Requests can be chosen based on desired ratios or time periods, to produce the corresponding Training Requests, Trigger Requests, and Test Requests. Likewise, Training Engine and Prediction Engine can be tailored with specific algorithms to train the models based on the selected Training Requests. Finally, Test Engine can be customized to evaluate different prediction models with various testing strategies. For instance, as discussed earlier, Test Engine may enable updating the prediction model dynamically; by plugging-in Test Engines that implement different dynamic-update strategies, HipHarness can isolate the impact of those strategies by producing their side-by-side Test Results.

We have instantiated HipHarness by implementing several variations of its six components. Instances of Training Selection and Test Selection are implemented to select requests based on different ratios, such as using the first 80% of the Historical Requests as Training Requests and the remaining 20% as Test Requests. Trigger Selection is implemented to select one current request to trigger the prediction of subsequent requests. Four pairs of Training Engine and Prediction Engine are implemented based on the three algorithms introduced in Section II—DG [10], PPM [9], and MP [40]—and a fourth baseline algorithm we will describe in Section V. Finally, Test Engine’s implementation is detailed in Algorithm 1.

Test Engine’s objective is to output information needed for evaluating Prediction Engine’s (PE) results. For each request $current\_req$ in Test Requests $test\_reqs$, PE predicts the potential current requests based on $current\_req$’s previous request $current\_req.pre$ (Line 4) and prefetches the predicted requests that are not already in the cache (Lines 5-9).

As discussed in Section II-D, we assume that all predicted requests should be prefetched and will not expire. We thus place the predicted requests in the cache without sending them to the server to avoid tainted results caused by spurious runtime variations. The cache size is unbounded in our study: since we focus on small amounts of historical data guided by our hypothesis (recall Section I), the required cache size is negligible compared to the available storage on mobile devices.

Test Engine then compares ${current\_req}$ with the cached requests to determine whether it can be reused, and updates the corresponding information (Lines 10-15). Finally, $PE$ dynamically updates the Prediction Model by adding ${current\_req}$ to train the model (Line 16) since ${current\_req}$ becomes a past request as Test Engine moves to the next request in ${test\_reqs}$.

In the end, Test Engine outputs the size of the cache ($cache.$Size); unique prefetched requests that were subsequently used (${hit\_set}$); unique requests in Test Requests that were not in the cache when requested (${miss\_set}$); total number of prefetched requests (${\#prefetch}$); and numbers of times a request was in the cache (${\#hit}$) vs. not in the cache (${\#miss}$) when requested. We use this information to define metrics that evaluate the accuracy of prediction models in Section IV.

An overarching hypothesis frames our study: History-based prefetching may work effectively with small prediction models trained on mobile-user requests collected during short time periods. To evaluate it, we focus on three research questions.

• •

  RQ₁ – To what extent are mobile users’ requests repetitive during short time periods?

• •

  RQ₂ – How effective are the existing prediction algorithms when applied on mobile platforms using small prediction models?

• •

  RQ₃ – Can the training-data size be reduced without significantly sacrificing the prediction models’ accuracy?

Data Collection Process. The network traces were collected at the gateway between Beijing University of Posts and Telecommunications’s campus network and the Internet. The measurement servers were placed at the campus gateway router, connected via optical splitters to the Gigabit access links. The HTTP headers were captured by the servers along with the timestamps. The authentication information (User ID) identifies the traffic from the same user.

Ethical Considerations. Our study was approved by the university, and was guided by the agreement the authors signed. The study strictly followed the Research Data Management Policy of the university, including data storage, sharing, and disposal. All collected raw data was processed by the university’s network center. All recorded IP addresses and authentication information were anonymized. The authors did not have access to any of the raw data at any time. Unlike prior work that selected 25 users [8, 29], our data includes all users who accessed the campus network without any selection.

Dataset Overview. Our study aims to assess small models trained on mobile-user requests collected during much shorter time periods compared to the conventional weekly or monthly models [8, 17, 2, 77, 1, 16]. To that end, we were given access to the network traffic collected by the university, spanning the 24 hours of May 28, 2018 (a randomly selected date). This included the traffic from nearly 11,500 accounts, representing all users who accessed the campus network via a mobile device¹¹1PCs and mobile devices use different clients for authentication. We only collected the mobile-network traffic based on the authentication information. during that time: students, faculty, staff, contract employees, residents, outside vendors, and visitors. These users exhibit various behavior patterns and form a diverse group for our study. We further filtered the mobile-network traffic to include only the requests involving the HTTP GET method [78]: GET requests are considered “safe” for prefetching in that they do not have any side-effects on the server [72, 79, 13]. Ultimately, we collected 15,143,757 GET requests from 11,476 users. Each request is identified by its URL, including GET parameters if any.

As discussed in Section II-D, we focus on the accuracy of the prediction models. We thus leverage two widely adopted accuracy metrics in the prefetching literature, and introduce a new accuracy metric. The metrics are computed based on the information output by our Test Engine (recall Algorithm 1).

Static Precision measures the percentage of correctly predicted unique requests, i.e., the ratio of prefetched requests that are subsequently used to the number of all prefetched requests [57]. This metric is often referred to as precision or hit ratio in the literature [40, 18, 80, 8, 9, 81, 57].

Static Recall is a new metric we introduce as the counterpart to Static Precision. Static Recall measures the ratio of unique requests that were previously prefetched (and have been cached) to the total number of unique requests made by a user.

Dynamic Recall measures the ratio of previously-prefetched requests to all requests a user issues [57]. This metric is often referred to as recall or usefulness in the prefetching literature [40, 18, 80, 8, 9, 81, 57].

We do not use a dynamic counterpart to Static Precision because it is not meaningful. To measure the ratio of correctly predicted requests dynamically, this metric needs to reward the predicted requests (hits) each time they are accessed, and penalize “useless” requests that were prefetched but never used. However, the reward for hits would be potentially unbounded. Moreover, the metric would allow cases in which a model with a low Static Precision has an artificially high Dynamic Precision: repeated hits of the same request would progressively diminish the penalty for arbitrarily many useless requests.

• •

  RQ₁ – To what extent are mobile users’ requests repetitive during short time periods?

To answer RQ₁, we calculate both the number and percentage of repeated requests in each user’s data, as they indicate different aspects of predictability. The percentage provides insights about the potential cost: low percentage indicates high proportion of non-predictable requests, increasing the cost of building the model. The number sets the upper-bound on requests that can be prefetched.

Table II shows this data across the 9,900 subject users. The minimums indicate that certain users did not access the same URL more than once. 222 (2%) of our users fall in this category. Further investigation uncovered that these users do not access the network frequently enough to show repetitive behaviors: the average number of the network requests sent by these users is 32, i.e., $\approx$1 request every 80 minutes during the 24 hours.

On average, 28% of the requests are repeated. An average user sends 293 repeated requests, which can be prefetched and reused from a cache. The maximum percentage (98%) and number (3,225) show that history-based prefetching can especially benefit certain users. We also find a large variation across different users (see standard deviation in Table II). This indicates that individual users exhibit markedly different behaviors, which reinforces our choice of building personalized prediction models for each user on the client side (recall Section II-D).

To provide further insights for future techniques, we study the characteristics of frequently repeated requests by computing how many times each repeated request occurs per user. Due to space constraints, we highlight two findings. The average numbers of certain users’ repeated requests are unusually high, with the maximum of 779. Further investigation showed that these users tended to send large numbers of requests to obtain the same WiFi configuration files from a specific domain. Since the data available to us was sanitized, we can only hypothesize that this was due to server-side flaws. The maximum occurrence of a repeated request across all users was 2,634. This and other high values corresponded to continually obtaining information from certain servers based on the given users’ unchanging location coordinates, as indicated in GET requests’ parameters. Such domains may also have flaws that require resending the user location even when it remains the same. Both instances clearly point to opportunities for caching.

• •

  RQ₂ – How effective are the existing prediction algorithms when applied on mobile platforms using small prediction models?

RQ₁’s results indicate that our 24-hour dataset is amenable to prefetching, motivating us to apply the existing prediction algorithms on it. The rationale behind our algorithm selection was discussed in Section II-C. We further develop an additional algorithm (Naïve) to serve as the evaluation baseline. Naïve assumes that each request appeared in the past will appear again, and caches each such request. Naïve thus guarantees the upper-bound on the number of predictable requests, and provides a baseline for measuring any other prediction algorithm’s recall.

To answer RQ₂, we use HipHarness to obtain the Test Results (recall Figure 1) of the prediction models built for each user. As discussed in Section III-B, we implemented four pairs of Training Engine and Prediction Engine in HipHarness, based on the three existing algorithms discussed in Section II-C and Naïve. In the end, Test Engine outputs the Test Results needed for evaluating the models’ accuracy (recall Algorithm 1), using the three accuracy metrics discussed in Section IV-C.

For all four algorithms, we follow the common approach of selecting the first 80% of Historical Requests as Training Requests, and the remaining 20% as Test Requests [83]. The thresholds of each prediction algorithm are set to the same values used in the original techniques. Recall that our goal is to show the feasibility of small models on mobile platforms. In turn, this will enable fine-grained customization of the models to improve accuracy, e.g., tuning the thresholds, pre-processing the training data, and considering additional context.

Due to the complexity induced by PPM’s context-sensitivity (recall Section II), it was unable to output results when using our entire dataset. To enable a fair comparison among the algorithms, we thus excluded certain domains that displayed low percentages of repeated requests to reduce the dataset. We explored multiple cut-off points as the repeated percentage at which a domain is excluded and found that 10% was sufficient to enable PPM. This eliminated certain users since all of their requests were excluded, resulting in 9,751 users and 39,004 corresponding models built with the four algorithms. Interestingly, this process uncovered a potential correlation between the cut-off point’s size and the increase in the models’ accuracy. This suggests a smaller, better-tailored training set can yield even more accurate models, directly motivating RQ₃.

• •

  RQ₃ – Can the training-data size be reduced without significantly sacrificing the prediction models’ accuracy?

To answer RQ₃, we first investigate the three data-pruning strategies introduced in Section IV-A: Most Occurring Requests (MOR), Most Accessed Domains (MAD), and Most Suitable Domains (MSD). We then explore whether there is a lower-bound on the training-data size that yields the smallest prediction models without sacrificing accuracy.