15.1.1 Surging Mobile Data Traffic and Declining Operator Profits

The exponential growth in mobile data traffic, especially in the form of video, is severely stressing the cellular backhaul and core networks. On one hand, emerging applications are bandwidth heavy and/or pose stringent requirements for end-user quality of experience (QoE); on the other hand, mobile network operators (MNOs) are unable to charge in proportion to the costs incurred by the higher demands and, hence, are faced with declining profits. MNOs are, therefore, on the lookout for solutions that can help to manage the traffic growth without degradation to end-user QoE and also boost their revenues. Some solutions in this direction that are in active exploration are (i) capacity expansion via infrastructure upgrades, for example, increased number of base stations, deployment of Femto cells, and enabling WiFi offload [2]; (ii) design of sophisticated resource allocation, multimedia content management, and delivery techniques such as caching, including at the cell edge [3–5], transcoding [6], and just-in-time delivery [7]; and (ii) moving away from flat pricing toward pricing schemes that are smarter—adopting variable, dynamic, and adaptive pricing methods to manage growth such as usage-based pricing, tiered wireless data pricing [8], and time-of-the-day pricing and providingeconomic incentives to promote access patterns and behaviors that can alleviate congestion.

While capacity expansion and upgradation can become inevitable at a certain stage, rolling out upgrades is often expensive, and hence, any alternate techniques that delay expansion without impacting user QoE can result in significant cost savings for MNOs.

15.1.2 Traffic Variations and Peak-Time Congestion

One aspect of the traffic demand observed in operational networks that can be leveraged for better traffic management (and, hence, delaying capacity expansion) is the significant variation in utilization levels over time. Such variations are primarily due to cyclic and regular patterns in everyday human activity; for example, networks see more utilization during days than nights [9, 10], cellular base stations in residential areas are more loaded during mornings and late evenings, whereas base stations near commercial areas are busy during office hours [11], etc. In fact, measurements at a commercially deployed base station (reported in Section 15.3.2s) point to large variations in achievable throughput even at short timescales of the order of minutes. This aspect has been reported and corroborated in certain other works [9, 12]. Consequently, while networks are overloaded and congested during certain peak times of a day, they remain sparingly used during certain other times. In other words, while the peak demand is higher than the base station capacity, the average demand is much lower.

Flows in session during peak periods compete for bottleneck resources (such as the spectrum bandwidth), which reduces the bandwidth achieved by each flow and increases the packet delay. Such ineffective use leads to a lower yield of the network resources. The yield of a network deployment is a function of the number of “useful” bytes carried by the network during any interval of time, that is, bytes that do not get dropped, get delivered in time, and do not lead to degradation of end-user QoE, and, hence, are of value.

15.1.3 Yield Management through Smart Pricing

When the average demand is observed to be much lower than the capacity, and congestion occurs only at certain points in time, such peak-time congestion can be eased without expanding network capacity if part of the peak-time traffic is time shifted to periods of lighter use. For this purpose, data traffic can be considered to be of two broad types: (i) delay-inelastic traffic—which users cannot tolerate any delay for any reason—and (ii) delay-elastic traffic—which can be deferred or for which users may be willing to wait, in exchange for incentives. Large multimedia and other file downloads, cloud synchronization,video uploads, and software updates are some examples of traffic that is delay elastic. Note that delay-elastic traffic is in turn of two types: in the first type, the delivery is awaited by users (even if time shifted) for direct consumption, e.g., as in the cae of multimedia files, and in the second one, users are agnostic about transfers and consume content only passively, e.g., software updates.

As video traffic dominates the data carried on mobile networks and content consumption penetrates into larger sections of the society, many of whom react positively to incentives, there is much scope for lowering peaks by including mechanisms to time-shift traffic. In particular, designing incentive and delivery mechanisms for time-shifting traffic can help both delay-elastic and delay-inelastic traffic. For delay-elastic traffic, consumers can also benefit in terms of QoE if their expectations are negotiated and appropriately set in exchange for incentives, such as price discounts, and the altered expectations are adequately met. User-agnostic traffic such as software updates can be shifted by setting the right policies, such as performing updates during nighttime, without affecting the QoE of a user in any way. When some delay-elastic traffic is moved away from peak period, delay-inelastic traffic during that time also benefits because of less contention for bottleneck resources, thereby improving the overall network yield.

Time-shifting traffic, however, introduces a radically different delivery model than what consumers are normally used to and may also require changes to the applications to adhere to the new delivery semantics. As a first step to understand the implications of this changed delivery model and to gauge the sensitivity of consumers to the various aspects of such a delivery model, we conduct a detailed user survey with a representative set of user population. We discuss the setup and results of our study in Section 15.2 and derive interesting insights that are useful for designing traffic time-shifting mechanisms.

Details of our user survey is followed by a description of approaches to time-shifting traffic and their high level comparison in Section 15.3. Section 15.4 describes a pricing scheme for one of the approaches and its integration with the MNO's infrastructure. Section 15.5 evaluates the time-shifting approaches through simulations, while Section 15.6 concludes.

15.2.1 Setup and Goals

The survey page, available at [13], includes several relevant questions to collect inputs from more than 100 users. The set of people taking the survey includes engineers, Internet-savvy nonengineers, people active on social networks such as Facebook, and other tech-savvy users. About 20% respondents are from North America, about 10% from Europe, and the remaining are from India.

The intention of our survey is to find answers to the following questions.

• Current State of User QoE. Do users experience degraded QoE during peak hours?
• Delay Tolerance. What fraction of the users is willing to accept delays to content delivery if offered discounts?
• Delay Elasticity by Traffic Type. What kind of traffic are users willing to delay if offered incentives?
• Price Sensitivity. For a given discount, how long can users wait for the content to be available for consumption?
• Adoption. Given discounts on content delivery, would users increase content consumption (i.e., network usage) further?
• Pricing Interface. Given discounts, how frequently would users like to make choices of pricing?

While a larger user base will make the results even more representative and authoritative, our current observations shed light on several interesting aspects that motivate and guide the design of solutions for time-shifting traffic.

15.2.2 State of User QoE

In our survey, we asked users to report the top three connectivity problems that they typically face when using cellular data network. A few representative responses reported by many users are as follows.I get very low download speed on my wireless broadband connection in the morning during office hours. The 4G (LTE) network connection on my phone often slows down and sometimes breaks when I am commuting, especially, close to the office. Video streaming on my phone over 3G is usually faster during early mornings or late evenings (off peak hours); however, because the data plans are relatively more expensive than wired broadband, I restrict my usage.

While some of the above problems may have several other possible root causes than network congestion, most of the responses suggest the impression the users carry about network connectivity: poor QoE during peak hours. These responses indicate the viability of a pricing/delivery model that can make the users aware of network congestion explicitly and then provide them with the option to delay content delivery for a discount.

15.2.3 Delay Tolerance

Next, to understand the delay-tolerance thresholds of users, we asked the following question: If provided with a delivery promise in terms of an expected delivery time (EDT), how long can you wait for the content to be delivered and available?

Users’ responses are summarized in Figure 15.1. The figure shows that roughly 50 users when choosing delays are sensitive to discounts offered (indicated by f(discount)), while more than 40 are willing to delay the download (by 1–6 h) for an EDT promise for better QoE even without any discount (indicated by f(delay)). This is possibly because of the existing low bandwidth experience in the network and lack of good QoE [14]. About 20% of the users are also sensitive to the specific content type (indicated by f(content)) and time of the day (indicated by f(time-of-day)). Note that a user could select multiple options for this question. For example, delay that is acceptable to a user can depend on both discount and time of the day.

15.2.4 Delay Elasticity by Traffic Type

To get a sense of the content types that are delay elastic, we asked users to select the traffic classes for which they would accept delays to the delivery for discounted rates. Users’ responses are summarized in Figure 15.2. The figure shows that only about 10% of the users are particular about receiving all the content with no extra delay. Others show increased tolerance to different content and transfer types. As expected, people are more willing to tolerate longer delays for larger transfers. Also, more than 50% of the respondents are willing to delay video and photo uploads, possibly because they themselves do not consume the content.

15.2.5 Price Sensitivity

We then asked the users to indicate the discount levels acceptable to them. Response summary in Figure 15.3 shows that most users are willing to wait for up to 2 h if given 50% discount, but not as many users are willing to tolerate higher delays even for 75% discount. However, it shows that many users are price sensitive, and they can trade a delay of 1–2 h, for a sizeable discount.

15.2.6 Adoption

Next, to get a sense of the additional network usage and revenue that the new pricing scheme can lead to, we asked the users as to whether they would be accessing more content, if given a 50% discount on the original price and a promise of delivery within an EDT. Figure 15.4 shows that more than 50% of the respondents would increase usage by 2 if given 50% discount. As this increased adoption is barely sufficient to balance the discount offered, it does not lead to an increase in the operator revenue. However, the same figure also shows that more than 20% of the respondents would increase usage by 3 for the same 50% discount, which has the potential to increase operator revenues. Thus, by providing appropriate discounts and managing expectations on delivery times, the operators can not only manage congestion but also expect their revenues to grow.

15.2.7 Pricing Interface

We finally asked users for their choice of interaction to avail discounts: per-request discounts, day-ahead notification of discounted time periods, or monthly discount plans. Figure 15.5 shows that most respondents are interested in getting discounts: About 45% preferred the maximum flexibility provided by per-object pricing and delivery-time decisions (i.e., choosing the price of an object just before downloading), while about 30% chose to keep it simple with monthly discounts. Only about 10% chose to get day-ahead discounts. The main reason could be that day-ahead discounts require users to keep track of daily price changes, which could get cumbersome, while month-ahead discounts obviates such day-to-day tracking.

15.3.1 Time-Shifting Taxonomy

Request-Shift Versus Delivery-Shift. Consider the typical browsing and content consumption pattern of any user: (i) selection, the user selects an object to view (and clicks on a hyperlink); (ii) request, the user device issues a request to the content server for the object on a transport connection; (iii) delivery, the content server delivers the object on the transport connection; and (iv) consumption, the user uses (e.g., views) the object.

In such a setting, time-shifting traffic can be realized using two possible approaches (see Fig. 15.6):

• Request-Shift. In this approach, if there is congestion at a certain point in time, users are provided an incentive to stop making requests and return back at a later point in time during a low price period and reissue their object requests. With Request-shift, the three steps of request, delivery, and consumption happen close together in time during a lowprice period of user's (or their agent's) choosing. Note that with this approach, delivery is expected to be confined to the chosen low price period, which can be away from the time the user makes a selection (or intends to select) by a large duration.
• Delivery-Shift. In this approach, an object request is collected immediately when the user intends to view the object, but the user is provided an EDT of when the object will be ready to consume. The object's delivery is spread over time, and the request–response transaction is asynchronous to be able to opportunistically transmit during noncongested periods at short time scales.

An instance of the Request-shift approach is the TUBE system [12]. TUBE computes time-dependent prices a priori, typically a day in advance, using past history of network traffic by time and a user-behavior model that predicts user responses to prices offered. TUBE uses a feedback loop between the price-computation and user-behavior models to adapt and optimize price computation based on user's reaction to the prices. To simplify the task of choosing a time for issuing a request so that the overall usage is optimized, TUBE also includes an autopilot mode that can schedule requests on behalf of the users. The prices are computed over time durations of the order of 30 min to 1 h.

An instance of the Delivery-shifting approach is the Async system [18]. Async introduces a “sachet” model in which users (or automated user agents) are allowed to choose the delivery price and expected delivery time (EDT) of different objects at fine granularity. For realizing this model, as shown in Figure 15.7, for each object request, Async presents users with a set of (price, EDT) options to choose from. Thus, the Async system facilitates an MNO to negotiate a delay in content delivery with users in exchange for incentives. The negotiated delay is used by the MNO to actively manage content delivery in such a way that QoE improves for both deferred flows and regular flows (which are not deferred). The price for a request for a given EDT is computed by determining the total traffic levels during the times at which the request is likely to be scheduled. By charging a price that is in proportion to the expected traffic levels, the MNO can offer higher discounts for longer delays. Note that deferred deliveries under Async are not just best-effort attempts but are associated with EDTs. By letting the users to choose the (price, EDT) combination, users get flexibility in choosing the level of service and price they want. At the same time, the MNO also gets to control when and at what price content is delivered.

15.3.2 Comparison of the Time-Shifting Alternatives

The Request-shift approach leads to a simple system implementation, requiring no changes to the network elements, except for setting different charging rules dynamically. The onus is on the user (or a user agent) to issue requests at appropriate times. On the other hand, Request-shift approaches can have the following drawbacks. (i) As the network has no control over the amount of traffic that would arrive in the low price period, time-shifted traffic may again encounter congestion, thereby disappointing the user who chose to defer the traffic. (ii) Transmission opportunities that become available over short time scales in the time intervening between the object selection and final consumption cannot be utilized, lowering the overall network utilization. (iii) Owing to lack of active network control, the system cannot adapt satisfactorily if actual conditions deviate from the predictions. In other words, reasonably accurate estimates of future traffic conditions are required a priori for the system to compute time-of-the-day prices and be effective in practice.

To understand the variations over time in the usage of cellular data links and the capacity that is available, we conducted a set of experiments over a week. In these experiments, we measure and characterize the achievable throughput across different base stations in Bangalore, India. Figure 15.8 shows measurements of throughput with backlogged flows (for a duration of 50 s) using the cellular network of a leading wireless service provider in India from two different locations (in Bangalore). Figure 15.8 shows that there is a lack of any temporal predictability in the achievable throughput (and, hence, load) at cellular base stations; as can be seen, the load can vary significantly across two consecutive half-hour time periods and can be very different at a given time of the day on different days. We observed similar variations at other commercially deployed base stations also. These observations indicate that meeting user expectations with a Delivery-shift approach may be easier than that with a Request-shift approach.

The Async system, which is an instance of Delivery-shifting, strives to overcome the shortcomings of Request-shifting approaches but has to address the following issues. First, it requires active management of content delivery using an in-network element (essentially a content proxy) in order to opportunistically transmit deferred flows during off-peak times. Second, because object delivery can be spread over longer durations, in comparison to Request-shift, and can be intermittent, the number of outstanding requests in the system can be higher. Further, the system has to tolerate disconnections because of mobility and user activity such as device switch off, necessitating that state be managed. Finally, Async requires a reliable sensing method to estimate periods of low utilization to transmit deferred traffic to improve spectrum utilization in comparison to Request-shift. Async successfully addresses these issues by designing an application layer protocol that can manage content delivery, with client-side maintenance of content transfer state [18]. Additionally, such active management allows the system to be more dynamic and adaptive in that delivery times and associated prices can be computed using current traffic conditions in association with coarse estimates of nondeferrable traffic.

15.4.1 Computing (Price, EDT) Options

For every incoming request, Async presents a set of (price,EDT) options to the users. EDTs can be a fixed set of values, such as 1, 2, and 4 h, or chosen based on the context and length of the request. Price for a given EDT is computed based on an estimation of the total traffic level or congestion during the times that the incoming request is likely be scheduled. To estimate congestion, we determine an allocation for the incoming request with respect to the EDT under consideration in the manner of water-filling algorithm, so that the maximum traffic at any point in time is minimized. This gives a reference schedule for the incoming request that can potentially be used by a network-side entity for actively managing its delivery.

Note that computing a reference schedule requires some knowledge of nondeferrable traffic, that is, non-Async traffic, arriving in the future. We assume that historical loads are available for estimating such future traffic. Such historical information can be obtained using the total cell-level load information (available with the network operator) and details of Async traffic available with the Async system (because all Async requests pass through the Async system). To account for deviations in the actual traffic from the estimated one and be adaptive, we recompute reference schedules for outstanding Async requests periodically or when a new request arrives, using their pending transmission sizes. (We, however, do not make changes to negotiated prices or EDTs of outstanding requests.) Such recomputation aids in reducing errors while determining prices for future flows. Further, because prices are computed at runtime, updates to the actual traffic can be made use of while computing prices. Hence, unlike approaches such as TUBE [23], prices in our scheme can evolve based on the load observed at runtime.

In what follows, we describe our pricing methodology in greater detail.

15.4.1.1 Assumptions and Definitions

Time is assumed to be divided into discrete periods. The duration of a period can be set appropriately based on the desired granularity, for example, we set each period to be 30-min long. Let denote the base station capacity in terms of aggregate bytes that can be transmitted in a period. We denote the total aggregate load owing to regular flows (i.e., non-Async flows) in time period as . The total number of Async flows active at time is denoted by and the number of bits allocated to Async flow in period is denoted by . Thus, the total traffic at the base station at time is then given by .

To quantify the degree of congestion, we classify the congestion experienced at a base station into one of a set of distinct levels. To enable such a classification, the base station's transmission capacity is partitioned into discrete subranges, given by , where for . Thus, the congestion level at a base station in period is given by the subrange in which the total traffic it sees in that period, , lies and is said to be if , . For each level , we assign a constant but monotonically increasing congestion weight . We then define a convex congestion-cost function (which is piecewise linear) for time period as follows.

15.1

It is easy to see that this function is nondecreasing with . This cost function allows the MNOs to choose different level thresholds () and appropriate cost () for the levelbased on their experience, for example, based on the probability of facing overload and related operational expenditure.

15.4.1.2 Allocating Async Flows to Minimize Congestion Cost

To compute a price for an EDT, we first formulate and solve the problem of allocating Async flows over time periods so that the aggregate congestion cost over the time periods is minimized. This optimization problem is formulated as follows.

15.2

where is the size (in bits) of Async flow . The constraints in Eq. (15.2) ensure that the base station capacity is not exceeded and the flow is served completely. The capacity of a base station depends on the channel quality seen by the users and, hence, in general, is dynamic for cellular systems. For the above optimization problem, we assume an average capacity given by the average signal quality experienced.

Note that even though the objective cost function is piecewise linear, the problem can be solved optimally because the slope of the objective is bounded and all the constraints are linear. We assume that at least one of the congestion weights and congestion-level widths is strictly increasing and the other is monotonically increasing.

15.4.1.3 Computing Per-Flow Options

When a new flow arrives, we solve the optimization problem PACKING once for each EDT to be presented to the user (with set to that EDT ). In solving the problem, we use the allocations in the future periods to previously accepted Async flows (obtained as solutions to instances of PACKING solved when those flows arrived) and estimates of (traffic because of regular flows). If the problem is infeasible for the largest acceptable EDT, then we declare that the incoming requestcannot be scheduled and send a notification back to the client. We compute a price for EDT , , as follows:

15.3

We assume that if to avoid a large value of (regular traffic) for some (with no Async traffic allocated) affecting the price computation; is the new request under consideration. Also, lies between and and can be used along with a base price. For instance, a fraction of the base price may be charged for the request.

It can be shown that the prices computed in the above manner are monotonically decreasing with increase in EDTs, ensuring higher incentives for waiting for a longer time. This, unlike models in prior work such as in TUBE [23], gives users an easy-to-understand interface: wait more, gain more [17]. Moreover, Async offers higher discounts to the requests arriving in low congestion periods, thus incentivizing users to increase their usage.

15.4.2 Integration with an MNO's Infrastructure

In the 3GPP specification for cellular networks, differential pricing per flow is generally achieved by adding rules to a system referred to as Policy and Charging Rules Function (PCRF) [24]. A rule specifies the price to be paid per byte by a flow identified by the standard 5-tuple:

<src-ip,src-port,dst-ip,dst-port,proto>

In the above, ip addresses and ports can be provided as wildcards. When a flow passes through the Gateway GPRS Support Node (GGSN), where it needs to be billed, a module called Policy and Charging Enforcement Function (PCEF) [24] finds a rule matching the flow and uses it for determining the charges.

To realize our pricing scheme, a small set of ports, each of which maps to a price per byte, can be assigned for the Async flows at a network element, which we shall refer to as the Async proxy. Async flows are made to pass through the proxy so that they can be managed. One rule per port of the form (src-ip=proxy-IP, src-port=, price=$$) can then be added to the PCRF. By assigning ports to flows based on the download price chosen by the user, ports at the proxy can be used for price differentiation. This approach is minimally intrusive to the cellular network deployment and also scalable, because it only adds a small set of rules (as many as the number of discrete pricing levels) to the PCRF. Note that this change to the set of PCRF rules does not affect PCEF (its scalability, in particular), because the charging enforcement functionality of PCEF is independent of how the rule for a flow is specified in PCRF or retrieved from it. Our approach for billing Async flows is illustrated in Figure 15.9.

Recall that for each incoming Async flow, a set of (price, EDT) options is computed as described in Section 15.4.1.3. To facilitate billing as described earlier, only those options with prices close to the prices specified in PCRF rules (based on a difference threshold) are considered. For each option included in the final set using the above rule, the final price is rounded to the highest discrete price in PCRF not exceeding the computed price. On the basis of the price that the user agrees to, the port on which the user can connect to for downloading the content is communicated. Thus, in a simple end-to-end manner, we can enable deadline and price aware transfer of content.

To enable a Request-shift approach such as TUBE, time-dependent rules can be added to PCRF; for instance, a price-per-byte rule can be added for each period of the day. In such a case, every byte of traffic arriving in a particular time period will be billed according to the pricing rule set for that time period. Further, because the number of periods in a day is small, of the order of a few tens, it is sufficient to add and delete a small set of rules per day, thus incurring only a small overhead. Hence, it is quite simple for a mobile network operator to deploy a time-dependent pricing scheme. On the flip side, such time-dependent pricing is flow agnostic. For instance, if a flow starts in a low price period because of the discounted price but does not finish within the period and continues in the next period, whose price is high, it needs to either be torn down, resulting in incomplete downloads or poor streaming, or pay a higher price to continue the service. In contrast, because Async's pricing methodprovides a price agreement for each object request, which maps to a flow, and is independent of the time of transfer, it is immune to such time-based issues.

Note that retransmissions from the proxy may be billed multiple times by the MNO's infrastructure. Peng et al. [25] studied and discussed the problem and provided a few solutions for MNOs to avoid overcharging for the retransmitted content.

15.5.1 Performance Measures

The main idea in both the Request-shift and Delivery-shift approaches is to alleviate congestion by deferring delay-elastic flows. Hence, to compare the two approaches, we define the following two performance measures: (i) aggregate base station load (over time) and (ii) total (end-to-end) delivery time for delayed flows.

To compute the first performance measure, we divide time into multiple periods and compute the aggregate traffic transmitted from the base station during each period. We then plot a cumulative distribution function (or CDF) of the load values. The second performance measure, total delivery time, is defined as the difference between the time a user selects an object and the time at which the corresponding content is completely delivered (i.e., all the bytes of the requested object are delivered at the client). Thus, the total delivery time measures the extent to which a scheme time shifts traffic to ease congestion. Both the schemes use discount as a means to achieve traffic shifts, and the higher the discount, the higher the chances of traffic shifts. To ensure that the traffic shifts are not just due to discounts but also due to effective delivery mechanisms, we also compare the total discount offered by the two schemes.

15.5.2 Simulation Setup

For the evaluation, we first choose an aggregate traffic pattern depicting traffic variations over a day. For this, we observe the traces from a leading service providerin India and consider different base traffic instances. One such instance is shown in Figure 15.10. The pricing schemes that we consider for both Delivery-shift and Request-shift divide a day's time into multiple time periods. We consider 30-min time periods and choose an aggregate traffic load for 48 continuous periods for 24 h. We assume base station capacity to be 270 MB/period. We then generate flow requests period by period to match the aggregate load. We distribute the flow arrival times uniformly randomly within each period. Each generated flow is one of the four content types: web request, short video, long video, and file download. The mean sizes for the four types are chosen from different sets, for example, 50 KB, 5 MB, 25 MB, and 50 MB.

We implement the Async pricing scheme for Delivery-shifting described in Section 15.4 using CVXOPT library [26]. In the Async framework, flows are of two types. (i) Flows that are amenable for deferrals, referred to as Async flows. Upon arrival, such flows are presented with a set of possible (price, EDT) options. (2) Flows that are not amenable for deferrals and do not wish to pass through the Async system, referred to as regular or non-Async flows. The Async pricing program takes the following as input: (i) details of Async flows (time of arrival, object size, type of flow) and (ii) an estimate of the cumulative non-Async traffic (based on historic trends). It should be pointed out that non-Async flows are not presented to the in-network control element, and hence, unlike Async traffic, the total amount of actual non-Async traffic is not available at runtime to the pricing component. The pricing scheme only uses coarse estimates based on historic data (as described in Section 15.4.1). The parameters of the pricing scheme (described in Section 15.4.1) are set as follows: we partition the base station capacity into equal congestion levels. For each level, we set for with .

As output, the pricing program determines the delivery method (NOW or deferred) and, if deferred, the EDT, for each Async flow. Async flows for which deliver NOW option is chosen are delivered without delay, just like a regular flow. We assume a proportional fair scheduling scheme (which is commonly used by cellular base station schedulers) for making allocations to the regular flows while computing (price, EDT) for the deferred flows.

For use with Request-shifting, we also implement the pricing scheme described in Reference 23 to determine per-period discounts based on the aggregate loads specified. We employ the user-response model described therein to determine the aggregate amount of traffic shifts across periods. For fair comparison, we use the same user-behavior model for the Async pricing scheme mentioned earlier to determine the final (price,EDT) options selected by end users. Specifically, for each of the content types described earlier, we choose a patience index (which models the amount of time by which users can shift their requests) as described in Reference 23. For the four content types mentioned earlier, we use 0.5, 1, 1.5, and 2 as the respective patience indices. These patience indices are then used in choosing the end-user's (price, EDT) option from among the set computed for a request. For both the schemes, we compute the discount as a fraction between 0.0 and 1.0, which essentially provides the discount rate per byte served. It should be pointed out that the TUBE pricing approach of Ha et al. [23] computes byte-level shifts, that is, the fraction of bytes that shift from one period to a later period. When extended to flows, a flow that does not complete within a period carries over into the next period. Owing to this, TUBE time periods are constrained to be reasonably granular, for example, at least 15-min long; else, the actual price charged for a flow may not match the price that a user expects to pay when deferring a flow. On the other hand, because the price computed for Delivery-shifting is on a per-object basis, it is not impacted by the times at which theobject is actually delivered, and hence, no constraints are placed on period granularity.

In this chapter, our focus is on the scope of the Delivery-shift and Request-shift approaches in depeaking congestion while improving the network yield. Hence, as mentioned earlier, for Delivery-shift, we assume that an entity in the network (such as a proxy) can schedule the deferred flows such that the reference schedule computed by the pricing module is followed. The Delivery-shift approach is better able to utilize short-term transmission opportunities and improve yield (as described in Section 15.1) because of the following: (i) not restricting a flow to a single or few time periods, as described earlier—hence, traffic spread can be wider—and (ii) active network control, which can sense such opportunities. One scheme that is capable of adapting to and making use of capacity variations is described in Reference 18.

We performed our evaluation for two cases: predictable and unpredictable traffic patterns. As TUBE computes per-period prices in an offline manner assuming a predictable traffic pattern, the first case allows us to compare Async with TUBE in a fair manner. For the second case, we scale the traffic pattern (e.g., increase the aggregate traffic in each period by up to 30%) to introduce unpredictability. The second case evaluates the adaptive nature of Async to runtime deviations to the traffic pattern assumed.

15.5.3 Results

15.5.3.1 Predictable Traffic Conditions

Figure 15.10 shows the input traffic assumed and the aggregate traffic as observed with the two approaches for time-shifting traffic. Given that the base station capacity is 270 MB per time period, periods 0–22 are congested in comparison to the remaining periods. Instead of shifting the flows entirely, the schedule computed by Async pricing can be used to serve the flows over multiple time periods and utilize the transfer opportunities whenever they become available. Further, such a schedule is computed and adapted periodically at runtime by considering the state (i.e., residual content and deadline) of active Async flows. Hence, as can be observed from the figure, the traffic curve for Async is smoother than that for TUBE. Thus, because of runtime determination of congestion and computation of appropriate price and EDT, the Delivery-shift mechanism in Async is more effective in alleviating congestion.

15.5.3.1.1 Flow Deferrals and Discount

To evaluate Async pricing, we generated a total of 750 flows for the duration of 24 h to conform to the aggregate input traffic chosen. (Recall that TUBE pricingoperates at the aggregate traffic level and does not make use of flow-level details.) Table 15.1 shows the mean percentage of bytes deferred over several runs under Async and TUBE. Note that, although the input trace is the same, the number of bytes deferred by the two mechanisms are different because Async computes the deferrals in response to the runtime traffic schedule (considering both the deferred and nondeferred flows), while TUBE precomputes the deferrals. In addition to the deferrals, Table 15.1 also shows the mean values of total discounts. In the case of Async, for every flow deferred, we compute the discount as the product of the rate of discount per byte and the total size in bytes of the flow. For TUBE, we compute the total discount using per-period discounts and aggregate per-period traffic. Note that the discounts offered by Async are comparable to that of TUBE. Further, for a fair comparison with TUBE, we also compute an Async schedule wherein we restrain Async from offering the discounts once the cumulative discount offered becomes equal to the total TUBE discount. Figure 15.10 shows that the traffic shift with above-mentioned discount cap is almost similar to that without any discount cap. This shows that, in comparison to the Request-shift mechanism in TUBE, the Delivery-shift mechanism in Async can better depeak the traffic for a given discount budget. For fair comparison, we let the discount cap remain active in presenting the results for the two performance measures.

Mechanism	Deferrals	Total Discount, Units
TUBE	7.4	313
Async	11.2	389
Async with discount cap	9.8	313

15.5.3.1.2 Aggregate Load

In Figure 15.11, we plot the CDF of aggregate traffic per time period. In our setup, the maximum aggregate load a base station can handle in one period, that is, the base station capacity, is 270 MB. From the figures, we can see that Delivery-shift is more effective in reducing the peaks with a load less than 65% of the capacity in 90% of the periods. We observe a similar behavior when we remove the discount cap. However, with TUBE's Request-shifting, more than 30% of time periods are faced with load exceeding 65% of capacity, reaching up to 80%. This shows that the Delivery-shift mechanism of Async is more effective in alleviating congestion.

15.5.3.1.3 Total Delivery Time

Figure 15.12 shows the CDF of the total delivery times of flows under the two delivery mechanisms. As the Delivery-shift mechanism of Async does not wait for low price time periods, but computes schedules for flows in a feasible manner whenever there is capacity available, the EDTs are much lower than the flow deferrals under the Request-shift mechanisms. The median delivery time of flow deferrals in Async is about 18 periods, which is 50% lower than the median delivery time of flows deferral in TUBE. Thus, for a given discount budget, the Delivery-shift mechanism of Async reduces the delivery time of flows while also depeaking the traffic in an effective manner.

15.5.3.2 Handling Deviations to Estimated Traffic

In another set of experiments, we consider deviations to actual traffic from that estimated by scaling (increasing by 30%) the input traffic pattern in Figure 15.10. Note that, to enable request shifts, TUBE computes prices for different time periods by assuming the original (nonscaled) traffic pattern. In comparison, by design, Async reacts to the changes in traffic at runtime. As a result, as we can see in Figure 15.13, even when there is unpredictable increase in traffic, Delivery-shift outperforms the Request-shift mechanism by better smoothing the traffic and managing the congestion. It can be observed that with the scaled input traffic, there is a peak with TUBE in time period 32, whereas the traffic is smoother with Async. Moreover, even with a 30% increase to the input traffic, the median delivery time in Async is lower than that of TUBE by 45%. Thus, because of the lack of network-side control, the Request-shift approach does not react effectively to the deviation in input traffic patterns. Further, flows shifting to the presumed low traffic periods may suffer from increased contention.

A comparison summary of the salient features of the Request-shift and Delivery-shift approaches discussed in this chapter is presented in Table 15.2

	Request-Shift	Delivery-Shift
Feature	(e.g., TUBE)	(e.g., Async)
Ease of implementation	Simpler. Involves offline computation and dissemination of time-of-day prices	More complex, requiring runtime computation of prices at fine granularity, down to the level of individual requests
Runtime network control	None	Requires active intervention to control when deferred flows get transmitted
Yield management	Cannot make use of short time-scale transmission opportunities	Can put short time-scale transmission opportunities to good use
Depeaking traffic	Less effective	More effective
Robustness	Requires reasonable estimates of future traffic to be effective	Can adapt at runtime to deviations from expected traffic
Ease of integration with PCRF	Easy to provide time-of-day prices but flow-level expectations may be violated	Easy to provide a few discrete prices. Pricing agreements can be made and honored at flow level