11.2.1 The Pricing of a Monopoly CDN

We first introduce the pricing models used in the CDN industry. The most common model is to charge based on traffic volume delivered by a CDN over a period of time, for example, a month. This pricing model usually offers a volume discount, the larger the volume, the more the deduction [16]. The disadvantage of this volume-based model is that it fails to consider the bursty traffic [17], which can demand a costly investment from CDNs. The second pricing model enables CDNs to charge based on the bursty traffic. With the second charging model, a CDN periodically monitors the bandwidth usage and charges customers according to the 95-percentile usage. In this case, customers commit to a maximum bandwidth usage in advance. If the actual usage goes over the commitment by more than 5%, a penalty may be charged. The last pricing model is based on request. A customer is charged by the number of requests served by a CDN. This model is not widely used. A CDN may provide all types of pricing models, and customers can select the one that is best for their business.

Previous works on CDN pricing mainly focus on the best pricing scheme of a monopoly CDN when facing multiple heterogeneous content producers [18–20]. Content producers are given the option of either self-provisioning or subscribing to a CDN. Content producers’ decisions are a function of the CDN's pricing scheme. The studies [19, 20] show that the optimal pricing scheme is determined by the patterns of the traffic. When traffic is Possion, CDNs should provide volume discounts to content providers. While facing bursty traffic and the burst varies across content providers, volume discounts can be suboptimal. In this case, a percentile-based pricing is more profitable than volume-based pricing.

Because of the rapid development of the CDN market, the monopoly CDN model may not be suitable for the current situation any more. As we have mentioned in Section 11.1, a content producer can subscribe to multiple CDNs at the same time. Under this situation, a CDN's price is mainly driven by the heated competition among CDNs rather than traffic patterns. In this chapter, we study the pricing schemes under competition.

11.2.2 CDNs in Content Delivery Supply Chain

Before CDNs and big content providers became big players, the supply chain of the Internet was clear and simple. Essentially, small networks (including content producers, CDNs and access networks) purchased transit from backbone networks, that is, they establish transit relationships, and both backbone networks and small networks peered among themselves to exchange traffic for free. However, as CDNs and content producers emerge as the biggest traffic contributors in the Internet [11], it becomes unclear which side gains more benefit from the connections, the content or the transit. Thus, it is hard to judge who should get paid in the supply chain. Transit networks argue that delivering the high volume content involves huge cost, and thus content producers or CDNsshould pay for the service. On the other hand, content producers and CDNs insist that their content and service are valuable and help transit networks attract end users. There are many papers addressing the network neutrality debate [21, 22], and in this chapter, we focus on the debate that involves CDNs.

The debate is highlighted by a recent event between Level 3 (a backbone network and a CDN) and Comcast (an access network) [23, 24]. Originally, the relationship between Level 3 and Comcast is peering. In late 2010, Level 3 started to carry the traffic from Netflix, which significantly increased the traffic sent from Level 3 to Comcast. Level 3 then informed Comcast that they needed to add additional interconnect capacity. Comcast rejected the request, citing that their relationship was no longer peering because the traffic exchanged was unbalanced and requested Level 3 to pay for the connection. Level 3 eventually paid Comcast for the extra traffic. The result is supported by a study of Clark and Bauer [5]. Their paper points out that it is economically efficient for a CDN to pay access networks.

A number of studies formulate models to describe the position of CDNs in the Internet supply chain. One popular model involves two-sided markets [25]. It combines the access networks and the CDNs together as one platform and analyzes the best policy for the platform facing end users on one side and content producers on the other. In another related paper, Chuang [4] argues that the network structure is better measured under bilateral oligopoly relationship as shown in Figure 11.1. Compared with the two-sided market model, bilateral oligopoly preserves the market power for both CDNs and access networks, and it is capable of analyzing the competition within both CDN and access networks. According to the author, the competition is an indispensable factor to maintain economical sustainability in the Internet. Although the bilateral oligopoly relationship is of great interest, as far as we know, it has not been used by any analytical model. We try to take the first step toward the goal by focusing on the competition in the locus of CDN market (marked by the dashed line in Fig. 11.1). Because the relationship between CDNs and content producers has several unique properties that are ubiquitous among entities in the Internet, for example, customers can subscribe to several CDNs at the same time, and CDNs have both overlapped and unique service ranges, analyzing the competition between CDNs and content producers can provide useful insight for other competition in the Internet as well.

11.2.3 Compare CDN and Other Multiple-Choice Markets

There are many markets where customers face multiple choices. For example, a firm or a company may purchase multiple units of computers from multiple brands to meet their needs; a household may have multiple vehicles for different usages; and on one trip to a grocery store, customers regularly purchase multiple products on carbonated soft drinks, ready-to-eat cereals, canned soups, and so on. The previous research in this area focuses on modeling customers’ multiple-choice behavior as firms’ policies, customers’ preference and demographics, and other related parameters change. Dube [26] proposed a model to analyze customers’ multiple choices on carbonated soft drinks, and used the model to predict customers’ future purchase. Hendel [27] developed a model to characterize firms’ computer purchase behavior. Chandra Bhat and Sen [28] designed a model not only to estimate vehicle holdings in a family but also to predict the miles of travel for each vehicle. All these previous models focus on one-time multiple-choice purchase rather than a series of purchases that happen over time. There are two reasons that these models do not need (and never intend) to consider the market and customer behavior change over time. First, the markets addressed in these models are relatively stable. The number of competitors and their efficiency tend to stay consistent, and prices are also steady. Second, goods sold in these markets are durable and usually last a while after purchase. However, the CDN market is a different type of multiple-choice market. First, the CDN market sells service and charges content producers based on usage. It is easy for customers to switch among CDNs. Second, the CDN market exhibits high dynamics. New CDNs enter the market constantly, and incumbent CDNs keep expending their coverages, and the pricing of the CDN market changes dramatically. In the dynamic CDN market, we are not only interested in how customers make multiple-CDN selection as the market state changes, but more importantly, we also want to understand how CDNs survive and compete with customers’ multiple-choice behavior and whether the competition is efficient and sustainable over the long term.

11.3.1 Static Analysis

In economics, competition is the rivalry among firms or providers that aim to achieve higher utilities, market share, and so on by adjusting the price, investment,innovation, or other marketing strategies [29]. Competition in economics has a long history stretching back to the nineteenth century. The original work was introduced in Reference 14 by Cournot. Cournot's model assumes that the demand in the market is a decreasing function of price and the competing firms choose quantities of a good to produce in order to maximize their own utility. The conclusion is that every firm eventually chooses the same quantity to produce and earns positive utility. As the number of firms increases, the price approaches marginal cost. Following the work of Cournot, Bertrand [13] took a different analysis approach. In Bertrand's model, the quantity is determined solely by the demand in the market and firms control prices rather than quantity. As a result, customers only purchase the good from the firm with the minimum price. The final outcome is an equilibrium where any firm in the market has zero utility. Since the two original papers, there have been a variety of models that discuss the competition among firms. Some of them produce more realistic results with the assumption that the firms are willing to supply only up to a quantity that maximizes their utility [30, 31]. Others focus on differentiated goods. For example, the Hotelling model [32] assumes that the goods associate with a cost depending on the location of the firms.

The previous models we introduced assume that an action has no long-term effect, for example, when a firm needs to make a decision, it ignores what other firms would do to react to its action in the future. The models also assume the state of the market, for example, the number of firms or the efficiency of each firm, is static. We refer to the analysis on games with only immediate impact and static market state as the static analysis. In the following subsections, we relax the constraints and introduce more realistic models to analyze the competition.

11.3.2 Predictive Analysis

One of the important factors that the static analysis rules out is the impact of competitors’ current actions on the future. If actions are made with respect to the future, the same competitors may behave very differently. Repeated games capture the idea that a player takes into account the impact of his/her current action on the future. In a repeated game, a base game (or called a stage game) is played in finite or infinite repetitions with prediction. We name the analysis used in repeated games the predictive analysis.

We take the prisoners’ dilemma as an example. In the classical version of the game, two prisoners are arrested and under investigation. If neither of them confesses, both of them will be sentenced to year. If one of them confesses and the other keeps silence, then the one who confesses will be set free, and the other one will be sentenced to years. If both of them confess, then both of them will get years. Table 11.1 shows the utility of the prisoners with different actions. Note that,the longer the sentence, the lower the utility.

Suppose the game is played iteratively with the same pair of prisoners. We first assume no prisoner is concerned about the future impact. Then any rational prisoner would confess, because if they only consider the gain of the current iteration, confession always rewards more than silence. Thus, the only possible outcome in every iteration is that both prisoners confess. The interesting part of this result is that pursuing individual reward logically leads the prisoners to confess, but they would get a better reward if they both keep silence. The utility gained by each prisoner over time will be

11.1

where is a discount factor. The discount factor indicates the value reduction for the future utility because the future utility cannot be obtained immediately.

Next, we assume that every prisoner makes decisions knowing that, in the next iteration, the other prisoner will act based on his/her current action. In this case, the outcome will be changed. The strategy of prisoners is (i) always keep silence in the first iteration and (ii) if the other prisoner also keeps silence, then play silence in the next iteration; otherwise, always confess in all the future iterations. We will show in the following text that prisoners always have incentive to keep silence if the discount factor is small. If a prisoner keeps silence in the current iteration, the utility he/she gets is

11.2

In this case, both prisoners will play silence in every iteration and earn a utility of 2. If a prisoner confesses, then the utility he/she gets is

11.3

Although the confessed prisoner earns a high utility in the first iteration, he/she will get 0 for all the future iterations. Note that, as long as the discount factor is larger than , silence is always a better strategy than confession.

We can see that the future impact may dramatically change players’ strategy. This is because the promise of future reward or the threat of future punishment provides incentive for both players to cooperate in the current iteration.

Although predictive analysis models the impact of the current actions on the future, it fails to model the state change of the game. For example, in the prisoners’ dilemma game, we assume the utility gained under the same condition is constant. However, the utility may change over time in reality. If silence no long gives a utility of 2 but 0, then the prisoners’ strategy should be changed accordingly. In general, the state change can be driven by both internal or external forces. An internal force can be a firm's investment or improvement in its technology, and an external force can be the outside market shock that may change the demand in the market we are interested in. The next model we introduce helps us to handle the case where the game state can change.

11.3.3 Dynamic Analysis

Both static and predictive analysis assume that the state of the game, for example, the efficiency of the firms or the number of competitors, stays the same over time. However, this assumption is not always true in reality. For example, players or firms can actively impact their efficiency by reducing their cost or adopting a new technology, and they can also change the total number of players by entering or exiting the game. The state of the game can also be changed by external causes. For example, the demand of customers can decrease ifan outside alternative emerges. Introducing the state change can make the analysis more complicated, but it can provide useful insight for more realistic scenarios.

11.3.3.1 One-Player Dynamic Analysis

We start with the simplest case, where there is only one player. We assume the base game is played iteratively. The utility that the player gains at time t is

11.4

where is the state of the game and is the action taken by the player at time t. The utility over time is thus

11.5

The state of the game can change over time. The state at time is determined by the previous state, the action taken, and the outside market change. That is, , where represents the change from the outside. The goal of the game is to determine the best action to maximize the player's utility over time. Maximizing utility over time is equivalent to solving the following maximization problem.

11.6

Define a new function and assume the initial state is , then Eq. (11.6 ) will be expanded as follows.

11.7

Drop the time subscripts, we get

11.8

We refer to Eq. (11.8 ) as the value equation of the one-player dynamic game. Similar to solving the Bellman equations [33], we can solve Eq. (11.8 ). The solution is a reaction function , which gives the best reaction x under state . We name the reaction function the optimal action or strategy. We will briefly talk about a numerical method to solve Eq. (11.8 ). Please refer to References 33–35 for other methods to solve the equation.

Rewrite Eq. (11.8 ) in the iterative form

11.9

where represents the result derived from the k-th iteration. Start with . Let be any bounded function that maps to a real number. Solve the maximization function on the right side of the equation by letting the derivative of x equal to 0. Replace x with the solution of the maximization function, and then we get the function of . Next, let , and solve the right side with and get . Repeat the process until , where is the desired degree of accuracy.

11.3.3.2 Multiple-Player Dynamic Analysis

In the previous subsection, we focus on the case where there is only one player in the game. Now, we discuss the case where n players are involved. Player i, where , solves the following maximization function to maximize his/her utility over time:

11.10

where and are player i's utility and action. Note that, for a n-player game, the state of the game depends on all players’ actions. That is, . Define a new function to be “,” and then player i's value equation can be written as

11.11

The solution of the n-player game is n reaction functions , where , and we name them the optimal action or strategy. Pakes and McGuire [34] and Ericson and Pakes [35] propose a method to solve Eq. (11.11 ). We will briefly introduce this method.

The iterative forms of the n players’ value equations are as follows:

11.12

11.13

11.14

where is the function derived from the k-th iteration. To derive , we let the derivative of the function on the right side equal to 0. That is,

11.15

11.16

11.17

By solving the system of nonlinear equations, we can get as a function of , denoted by . Note that, the system of equations may not be easy to solve, because they include n variables. We can use the methods in References 34 and 35 to simplify the process. In the i-th equation of the system, replace by the function derived from the previous iteration, where and . Then, the equations become

11.18

11.19

11.20

As a result, we reduce the n-variable system of nonlinear equations to n one-variable equations. This significantly reduces the computational cost.

Compared to static analysis and predictive analysis, dynamic analysis allows the state of games to change, and thus it can provide a solution suitable for more realistic scenarios. However, we can also see that deriving the optimal strategy using dynamic analysis can be hard and, in most cases, we can only use numerical methods to solve the problem. Dynamic analysis is explicitly summarized in the original works [34, 35]: “we give up on analytic elegance in favor of an ability to numerically analyze themore complex situations that might better approximate what is observed in real data or situations.”

11.3.4 Summary

In this section, we introduce three analytical models to characterize competition in economics. Static analysis ignores the impact of a current action on the future and the market state change. Predictive analysis considers the impact but it ignores the market state change. Dynamic analysis can model the market state change but the computation cost can be high. In the following sections, we use these methods to characterize the competition among CDNs.

11.4.1 Precise-Coverage Model

The precise-coverage model describes the universe of S's end users in a Venn diagram as shown in Figure 11.2. Each circle represents the perceived coverage of a CDN. The circles divide the universe into subsets. We use to represent the subset that is exclusively covered by a group of CDNs whose indexes are in the set, I. For example, represents the subset of end users who are covered by only and represents the end users who are covered by both and . Note that, and are subsets that do not overlap. Figure 11.2 shows the universe of end users who are divided into eight subsets by three CDNs. The traffic volume that S sends to is represented by .

If a subset is served by a CDN that covers the region, then each unit of traffic gets benefit . If a subset is served by a CDN that does not cover it, the benefit is . Apparently, . Suppose is the price charged by . Then, S chooses for if and only if S prefers it over all the alternatives. That is,

11.21

where and . If covers , . Otherwise, . The CDN selection problem is equivalent to the following maximization problem. Select the best CDNs so that

11.22

If several CDNs provide the same utility, then S divides traffic evenly among them.

We use an matrix named E to represent S's CDN selection. The rows of E represent CDNs, and the columns represent end users’ subsets divided by CDNs’ perceived coverages. Therefore, . is the percentage of subset j's traffic that is delivered by . As a result, the utility of S can be written as

11.23

11.4.2 Approximate-Coverage Model

The precise-coverage model is able to provide fine-grained details about coverage. But the model does not scale well. The next model we will introduce is more suitable for a large number of CDNs.

We use parameter to represent content producer S's perceived coverage of CDN , where . The parameter reflects how well can serve S's need. Thus, the parameter changes as 's coverage or S's need changes. The larger 's coverage, the larger , and the higher S's traffic volume, the smaller .

To enable S to make multiple-CDN selection, we assume S's benefit from is equal to , where is the traffic volume served by , and and are constants whose values stay the same across different CDNs. This benefit function is increasing and concave. The increasing property means that the more traffic volume S sends to , the more benefit. The concave property indicates that the increase in the benefit generated by a one-unit volume increase becomes smaller as the total volume increases. The “diminishing return” as volume scales enables S to split traffic to multiple CDNs rather than use one CDN for all the traffic. This model has been widely used by multiple discrete choice analysis (refer to Reference 41 for details). S's utility gained from is the benefit minus price: . The total utility of S then can be written as . Suppose the total traffic of S is , then S's CDN selection problem is equivalent to the following optimization problem. Choose the optimal so that

11.24

11.25

Note that can be smaller than , because S's traffic can be delivered by ISPs directly.

In order to make the CDN selection problem scale, the approximate-coverage model simplifies the way to describe the service quality that S receives from CDNs. The model uses a single parameter to represent S's perceived coverage size for and implicitly assumes that the perceived coverage size is the only parameter to determine 's service. An important factor that the approximate-coverage model ignores is the overlap among CDNs. If a CDN's coverage is already covered by other CDNs, no matter how big its coverage is, using the CDN may provide littleimprovement for S's end users’ experience. The precise-coverage model is able to describe the coverage overlaps and adjust service quality accordingly, but it does not scale well. While deciding which model to use for the CDN selection problem, we have to make the trade-off between the scalability and the precision.

11.5.1 Two-CDN Pricing Games

A two-CDN pricing game is defined as a repeated game where price decisions are made iteratively by two CDNs, and . selects a price at the beginning of a period, and that price is stable for the rest of the period. cannot change its price during the period when is about to move and vice versa. After a CDN decides its price, S makes CDN selection.

We use and to represent the volume of S's traffic that is exclusively covered by and , respectively, and is the volume that is covered by both CDNs, and is the rest of the traffic, for example, the traffic that is covered by neither of the CDNs.

Assume the utility of during period t is , where is the price, is the traffic served by , and c is the cost. According to the precise-coverage model in Section 11.4.1, content producer S can make four possible CDN selections: case 1: if , S uses for all the traffic, and , ; case 2: if , S uses for and for the rest, and , ; case 3: if , S uses for and for the rest, and , ; case 4: if , S uses for all the traffic, and , .

If both CDNs ignore the impact of the current action on the future and maximize their current utility, then the competition can lead to price wars. Fortunately, we also show that if both CDNs plan ahead and maximize utility overtime, then a price war can be avoided. We name the former strategy the nonpredictive strategy (Section 11.5.1.1) and the latter the predictive strategy (Section 11.5.1.2).

11.5.1.1 Nonpredictive Strategy

A price war is commercial competition characterized by repeated cutting of prices below those of competitors, and it may eventually force firms to close because of profit reduction. In this chapter, we say a price war occurs if a series of price reduction leads to a state where at least one CDN cannot avoid zero or negative utility by changing its price.

Any CDN that applies the nonpredictive strategy aims to maximize its current utility. Assume is about to move and the current price of is . It is straightforward that will select a price that makes S choose one of the first three CDN selection cases. Within each case, can reach the highest possible utility if it charges the highest price in corresponding range. Note that, only in case 3, selects a price that is higher than , and in case 1 and case 2, will choose an action that is prone to price war (charge a price lower than ). Only if case 3 yields more utility than case 1 and case 2, then will charge a higher price than . It is easy to verify that the condition is

11.26

where and is the smallest price unit. We define the right side of the inequality as the turning price of , denoted by . Similarly, we can derive the same condition for to charge a higher price than the current price of , which is

11.27

We define the right side of the inequality as the turning price of , denoted by . We use to represent the larger one between and . Note that, the price will keep decreasing till it hits and bounce back to a high price, where a new round of decreasing starts. The price oscillates in a cycle as shown in Figure 11.3. This figure shows a unique property of the multiple-choice market, where one of the CDNs will voluntarily increase its price in order to get a higher utility. The price increase can happen because the multiple-choice market allows a CDN to take a full advantage of its unique coverage. Whenever it is not profitable to compete for the overlap coverage, a CDN can focus on attracting end users in its exclusive coverage and charge a high price for the service. This will never happen to a single-choice market, where providers have to always compete for the same service, and increasing price will only make a provider less competitive. Thus, the multiple-choice market is less prone to price wars compared to the single-choice market.

However, price wars can still happen in multiple-choice markets. As the price decreases, the utility decreases as well. As the lowest price can be reached is , the lowest income gained by a CDN is . We name the value the bottom value. If the bottom value is smaller than c, then one CDN will find itself having negative utility before reaching , and the CDN cannot make positive utility by changing its price. The result is a price war. When a price war happens, the best nonpredictive strategy is to exit the game. We have the following theorem.

The overlapped coverage is linked to the likelihood of price wars. If two CDNs are fully overlapped (), then and the bottom price is 0. Then a price war must occur. The game becomes less prone to price wars as the overlapped coverage decreases. Let us consider a game where two CDNs have partially overlapped coverage and assume the game leads to a price war with the nonpredictive strategy. Without the loss of generality, suppose . Let keep its coverage stable, and the other CDN reduce its coverage by decreasing the overlapped coverage. Thus, increases and decreases. According to the definitions, both and the bottom value will increase. If the increase makes the bottom value larger than c, then will be reached before the utility goes below zero, and the price bounces back before a price war can happen. That is, if the total covered region stays the same, the less the overlap, the less prone a game to a price war.

11.5.1.2 Predictive Strategies

In this subsection, we assume any CDN that is about to move knows that its rival CDN will select a price based on its current move in the next period. The price strategy can be denoted by a pair of reaction functions and as follows:

11.28

where is 's price at t. Because the reaction functions consider the consequences of the current action on the future, we name them the predictive strategy.

's utility over time is . Substitute 's price using its reaction function, and then the utility over time can be written as . Note that at period , the game will repeat the same decision process as it has at period t. We define a new function . Then, to maximize 's utility over time is equivalent to solving the following maximization function:

11.29

The solution of Eq. (11.29 ) is the optimal reaction function . Similarly, we can derive the maximization function of :

11.30

The solution of Eq. (11.30 ) is the optimal reaction function . We can solve the pair of equations using the Markov perfect equilibrium theorem [42, 43]. In the following content, we introduce the results for two different two-CDN pricing games, one with the same-size coverage () and the other with the subsumed coverage ().

For the CDN pricing game with the same-size coverage, the optimal predictive strategy is given by

11.31

where and and satisfy two functions (details can be found in Reference 44): and , and . Note that, at the equilibrium state, both CDNs will charge a price equal to . According to the strategy, if the rival CDN charges a price that is greater than or equal to , or smaller than , then a CDN needs to charge . If the rival CDN's price is between and , then a CDN needs to charge . The optimal predictive strategy of the same-size coverage game is motivated by incentives, and it strategically forces the two CDNs to stay at instead of competing to price wars. When any CDN deviates from , the strategy makes sure that the other CDN will choose a price so that the deviating CDN can get the maximal utility only if its price goes back to .

For the subsumed coverage CDN pricing game, the optimal predictive strategy is given by

11.32

where , , and satisfy , , , and . Note that, at the equilibrium state, and will charge and , respectively. The strategy adopts a similar method as the same-size case to force the two CDNs to stay at and . It is interesting to see that, under the optimal strategy, the larger CDN always charges a higher price.

Not all the CDN pricing games have an optimal strategy. The sufficient condition for its existence in the same-size game is that and . The first condition requires the overlapped coverage of and to be large enough, and the second condition requires to be larger than . Note that a game that satisfies the first condition can be prone to a price war, and the optimal predictive strategy ensures that the price war can be avoided. More details about the sufficient conditions can be found in References 44 and 45.

We define the social optimal utility as the utility obtained by CDNs if they maximize their total utility instead of individual utilities. The social optimal utility is thus the highest utility that can be reached if all CDNs act selflessly. The closer the actual utility to the social optimal utility, the more efficient the strategy. Because the predictive strategy strategically forces CDNs to stay at a high price rather than compete to price wars, it is efficient in terms of price of anarchy. We have the following theorem.

Please refer to Reference 44 for proof. The predictive strategy is apparently beneficial for CDNs, because the total utility is close to the social optimal utility (defined as the highest utility the CDN market can get). But the benefit for CDN market does not necessarily mean the loss for content producers, because content producers will never pay more than what CDN service can provide. That is because content producers have two options to deliver traffic to end users: going through an ISP or a CDN. If CDNs charge more than what their service worths, content producers can always switch to ISPs. The predictive strategy is designed to help CDNs to compete more efficiently rather than squeeze the revenue from content producers.

11.5.2 The n-CDN Pricing Games

In Section 11.5.1, we focus on two-CDN pricing games. Now, we extend the game to n CDNs. In a n-CDN pricing game, CDN decides prices to maximize its own utility , knowing that content producer S makes CDN selection to maximize Eqs. (11.24 ) and (11.25 ). We say the game is under the equilibrium state if (i) content producer S cannot increase its utility by changing traffic distribution and (ii) CDNs cannot increase their utility by adjusting prices.

We will only demonstrate how to solve this problem with S as a big content producer. We omit the CDN pricing game that competes for small content producers because, unlike the big content producers who normally select multiple CDNs, small content producers usually select one CDN only, and any single-choice model [46] can solve the problem.¹

Big content producers are the most important customers of the CDN market, because they possess huge traffic volume and pay great amount of money for traffic delivery [10]. To simplify the discussion but still preserve meaningful insights, we assume that a big content producer will only select among big CDNs (This assumption is consistent with the decision made by big content producers in reality [10]). Further, from a big content producer's perspective, the big CDNs have either a high coverage or a lower coverage . We call them type 1 and type 2 big CDN, respectively. A type 1 CDN is intended to model Akamai, and a type 2 CDN resembles Level 3 or Limelight. We further assume CDNs with the same coverage have the same price. and represent the prices of the two types of big CDNs, and and represent their numbers.

Unfortunately, the solution of the CDN selection problem in Eqs. (11.24 ) and (11.25 ) has no closed form, so we apply a numerical method to solve it. Because of the way we solve the CDN selection problem, the CDN pricing game has to be solved numerically as well. We enumerate all possible prices that CDNs can charge (with a step equal to 0.1) and solve the CDN selection problem. Then let CDNs choose the best price that can maximize their own utility.

We play eight CDN pricing games where the number of type 1 CDNs are either one or two and the number of type 2 CDNs ranges from one to four. We set . We choose these values so that when there are one type 1 CDN and two type 2 CDNs in the market, their traffic shares are consistent with the percentages in the real market (introduced in Section 11.1). Note that, an arbitrary unit can be attached to , for example, MB,GB,TB, and PB. For all the runs, there is always an equilibrium state. The result is shown in Table 11.2. We compare different games’ price, traffic volume, and utility at the equilibrium state. We can see that type 1 CDNs always charge a higher price than type 2 CDNs do. But as the number of type 2 CDN increases, type 1 CDNs’ price will decrease slightly. Moreover, type 1 CDNs always attract more traffic, and thus they always obtain a higher utility. An interesting observation is as the number of type 2 CDNs increases, the total utility gained by all CDNs can reduce. The reduction can be caused by the heated competition among CDNs. If there is one type 1 CDN, then having two type 2 CDNs can result in the highest utility. If there are two type 2 CDNs, then having one type 2 CDN can result in the highestutility.

Note that, if we play the n-CDN pricing game repeatedly as we did in the two-CDN pricing game, the outcome of the game will not change. That is because, with a stable market state, the base game will produce the same result in each iteration.

11.6.1 Assumptions

Suppose there are M content producers, represented by , …, , …, . The end users are evenly distributed over the network and request the same amount of traffic from the same content producer. Depending on the traffic volume generated, we divide content producers into K levels from low to high. There are content producers at the kth level, and their volume is , where . We assume both and follow power law distribution over k, because the majority of the Internet traffic is generated by a small number of content producers [11]. More precisely, , where , and , where . In the following subsections, we suppose content producers are categorized into three levels, corresponding to small, medium, and big content producers, and , and . Content producers in different levels have different perceived coverage as shown in Table 11.3.

11.6.2 Market State Change Through CDN Federation

CDN federation is a collection of CDNs that are operated autonomously by different entities but are interconnected through open interfaces, so that they can work collectively as a logical content delivery infrastructure [47]. CDN federation is an efficient and economic way for small CDNs to expand their coverage and compete more directly against large CDNs, such as Akamai. It has been under fast development recently. In June 2011, a group of small CDNs make one step forward to federation by founding an Operator Carrier Exchange (OCX) to interconnect their networks [12]. Edgecast networks built a platform where small CDNs can buy and sell capacity with an easy-to-use online control panel. In this section, we will not discuss the technical problems and feasibility of CDN federation [48]. Instead, we will focus on the economic incentives of CDN federation. We will answer the questions of whether it is profitable for small CDNs to join a federation, and to what extent.

Federation impacts the market state by changing the number of CDNs and their coverage. If k small CDNs form a federation, the number of small CDNs decreases by k, and the number of big CDNs increases by 1, the new big CDNs’ coverage is the combination of the small CDNs’ coverage. To determine whether a federation is profitable, we compute the utility with and without a federation.

On the basis of the current status of the CDN market, we assume the numbers of type 1, type 2, and small CDNs are , , and , respectively, and small CDNs can federate to become a type 2 big CDN. CDNs conduct the n-CDN pricing game for every content producer independently (introduced in Section 11.5.2). We compare the utility gained by CDNs with and without a federation. Note that, a CDN's utility is equal to the summation of the utility gained from every content producer. The result is shown in Figure 11.4. We demonstrate four cases in the figure: no federation, three CDNs forming a federation, four CDNs forming a federation, and five CDNs forming a federation. For each case, we plot the utility of a type 1 CDN, a type 2 CDN, a small CDN, and a member of the CDN federation. We can see that a federation with three or four CDNs can be beneficial, because the members of the federation can gain more utility than individual small CDNs. Not surprisingly, as the number of members grows, the utility of each member decreases. If more than four CDNs are needed in order to form a federation, small CDNs may not have the motivation to join in, because acting as independent small CDNs can gain more utility than the small CDNs in the federation. The reason is twofold. First, the more members in the federation, the smaller share of the utility each of them will get. Second, as more small CDNs join the federation to compete with big CDNs, the competition among small CDNs becomes moderate and small CDNs’ utility increases.

For the current CDN market, a beneficial CDN federation has four or less member CDNs. If the CDN market has more big CDNs, the threshold will become smaller. But if two small CDNs can form a type 2 CDN, then forming a federation is always a better choice for these small CDNs, no matter how many big CDNs are in the market. That is because the federation can attract traffic from big content producers which contribute more traffic than small content producers.

11.6.3 The Dynamic CDN Game

In this subsection, we discuss the dynamic CDN game where the market state can be changed through the voluntary investment, entry and exit, as well as the involuntary market shocks. We model the dynamic CDN game as an infinitely repeated game where, at the beginning of each period, every CDN chooses an action (invest, enter, or exit) to maximize its utility over time. If a CDN decides to exit, it will get a scrap value in the current period. If it chooses to enter or invest, the market state change will take effect at the beginning of the next period. Within each period, the market state is stable and CDNs conduct the n-CDN pricing game introduced in Section 11.5.2. As CDNs’ utility is totally determined by the market state, in the dynamic CDN game, each CDN aims to choose an action that can result in a market state that can benefit itself most. We use a vector to represent themarket state, where is the type of incumbent CDN . We start with the case where the market state is changed by voluntary actions. Then we consider the case with market shocks.

11.6.3.1 Voluntary Dynamic CDN Game

We first introduce a game where the market state can be changed by voluntary actions only (no market shocks). The game is referred to as the voluntary dynamic CDN game. We apply the Markov perfect equilibrium theory [34, 43] to derive the optimal reaction scheme in the game.

Any CDN, represented by , aims to select proper actions to maximize its utility over time. is allowed to invest, enter or exit the market. For simple explanation, we first consider the case where is allowed to invest only. Later, we will add the other actions. We use to represent 's investment at time t, then 's utility over time is equal to

11.33

where is the market state at t and represents 's utility from the n-CDN pricing game under .

According to the dynamic analysis in Section 11.3.3, a CDN should solve the following value equation.

11.34

Note that at time , faces the same maximization problem as the one it faces at , but the market state changes to .

Assume investment either enhances by one level in the type rank or fails to do so. We use to represent the result of investment . is a random variable whose value depends on .

11.35

Note that the probability to have a level increment is a monotonically increasing concave function of . If , the probability is 0. We define a vector to represent the market change after the investment . The market state at time , , depends on the market state at time t and the investments of all n incumbent CDNs. That is, . Thus, the expected value of is

Then, 's value equation can be written as

Next, we expand the value equation to include exit strategy. We assume obtains a scrap value when it exits the market. Thus, if the expected utility over time is less than , will quit. always prefers an action that can result in a higher value between exit and staying. After including exit, 's value equation becomes

Dropping the time subscripts, we get 's value equation with investment and exit.

Next, we introduce entry to the value equation. We assume a new CDN enters the market as a small CDN and it pays a sunk cost . If the expected utility over time is higher than , then a CDN will enter. Otherwise, it stays inactive. A new CDN's expected utility over time is

11.36

where e represents market state change after the entry. Note that, if a CDN enters, the size of and will increase by one in order to match the total number of CDNs in the new market state.

The incumbent CDNs need to take entries into account while estimating their utility over time. Assume a new CDN's sunk cost is a random variable that is uniformly distributed on . We use to represent the probability that , hat is, an entry occurs, and to represent the probability that there is no entry. After including entries, 's value equation becomes

We refer to the equation as 's value equation of the voluntary dynamic CDN game.

In the following subsections, we make the same assumptions as we did in Section 11.6.1. In order to resemble the reality, for example, a new CDN is willing to enter when one type 1 and two type 2 CDNs are in the market, and there are less than five big CDNs at the equilibrium state, we assume that the scrap value is and and are 1 and 2, respectively. The discount factor is set to be , a value commonly used in dynamic analysis [34, 35]. Note that, we do not intend to precisely predict what will happen in the real CDN market. We aim to show how CDNs’ strategy may change as the market state changes, and whether the dynamics can produce anefficient market.

		Best investment
Current state		Small CDNs				Type 2 CDNs
Type 1 #	Type 2 #	1	2	3	4	5
0	0	2.3	4.3	6.1	7.6	9.0	1.1
0	1	3.6	5.1	6.3	7.8	8.3	0.85
0	2	4.0	4.9	5.6	6.3	6.9	0.73
0	3	3.1	3.7	4.1	4.4	5.0	0.58
0		0	0	0	0	0	0.35
1	0	3.0	4.1	5.0	5.8	6.5	0
1	1	2.8	3.4	4.0	4.5	5.3	0
1	2	2.1	2.5	2.8	3.0	3.3	0
1		0	0	0	0	0	0
2	0	4.2	4.9	5.6	6.1	6.5	0
2	1	2.5	2.8	3.1	3.2	3.3	0
2		0	0	0	0	0	0
3	0	7.3	7.9	8.4	9.0	9.2	0
3		0	0	0	0	0	0

The best investment strategy is shown in Table 11.4. In this table, the first two columns show the number of type 1 and type 2 CDNs at the current market state and the rest of the columns show type 2 and small CDNs’ best investment under corresponding market states (The best strategy of type 1 big CDNs is to avoid investment in any of the states). In general, if there are four or more big CDNs in the market, then small CDNs do not invest. Otherwise, they always invest. The investment increases as more small CDNs are competing in the market (the number of small CDNs is specified in the third row). Type 2 CDNs’ best strategy is to invest only if there is no type 1 CDN in the market. The best entry strategy is as follows. If there are more than seven CDNs in the market, then no CDN should enter. Otherwise, CDNs can enter.

If all CDNs apply the best strategy, the voluntary dynamic CDN game will converge to an equilibrium state. Because the level increment and the sunk cost are random variables, different games may have different equilibria. We simulate 10,000 games with an initial state where there are one type 1 CDN and two type 2 CDNs. At the equilibriums state, there are 1.0 type 1 CDN, 3.0 type 2 CDNs, and 2.9 small CDNs on an average (Fig. 11.5a), and the type 1 CDN attracts 38.2% of all the traffic, and each type 2 and small CDN attract 17.6% and 2.7%, respectively. The utilities gained by the three types of CDNs are 1.16, 0.55, and 0.08 per period.

To understand how efficient the equilibrium is, we compare the utility at the equilibrium state with the social optimal utility. We define a perfect cartel game to compute the social optimal utility. Assume that a perfect cartel can control the investment of all the CDNs and it aims to maximize the social utility of the CDN market. The value equation of the perfect cartel game is as follows.

Assume the conditions stay the same as the voluntary dynamic CDN game. The best strategy of the perfect cartel game is to promote a type 2 CDN to be a type 1 CDN if there are less than three type 1 CDNs in the market. The equilibrium state of the perfect cartel game has three type 1 CDNs, one type 2 CDNs, and no small CDN (Fig. 11.5b). The utilities of each type 1 CDN and type 2 CDN are 0.92 and 0.80, respectively, and thus the social optimal utility is 3.56. As a result, the total utility of the voluntary dynamic CDN game is 85.4% of the social optimal utility.

11.6.3.2 Dynamic CDN Game with Market Shocks

In the dynamic CDN game, we allow both voluntary market state change and market shocks. We say a market shock happens when content producers downgrade the perceived type of the incumbents CDNs. The downgrade can be caused by several reasons, including the increase of content producers’ traffic or the improvement of outside competitors such as ISPs. We assume that when a downgrade happens, it happens to all the incumbent CDNs and the probability of its occurrence is . With market shocks, 's value equation becomes

The best investment strategy under different is shown in Table 11.5. The first two columns show the numbers of type 1 and type 2 CDNs in the current market state, and the rest of the columns show the best investment strategy of small and type 2 CDNs (The best strategy of type 1 big CDNs is to avoid investment in any of the states). If the probability of market shocks is high, it is hard for small CDNs to survive. Thus, small CDNs only invest when there is no big CDN in the market. The best strategy of a type 2 CDN is to invest if there is no type 1 CDN. If there is already one type 1 CDN, then invest if two or three type 2 CDNs are in the market and the probability of market shock is high. The best entry strategy is as follows. When , a CDN should never enter if there are four or more CDNs in the market. The threshold is five and seven CDNs for and , respectively.

		Best Investment Strategy
Current State
T-1	T-2	Small	T-2	Small	T-2	Small	T-2
0	0	0.5–0.7		0.7–1.0		0.9–1.3
0	1	0	1.1	0.5–0.7	1.1	0.7–1.0	1.2
0	2	0	0.7	0.1–0.2	0.9	0.5–0.7	0.9
0	3	0	0.6	0	0.6	0.2–0.2	0.8
0	4	0	0.6	0	0.4	0	0.6
0	5	0	0.5	0	0.5	0	0.4
1	0	0		0.3–0.5		0.5–0.8
1	1	0	0	0	0	0.3–0.4	0
1	2	0	0.1	0	0.2	0.1–0.1	0
1		0	0	0	0.1	0	0
1		0	0	0	0	0	0
2	0	0		0.1–0.2		0.5–0.8
2	1	0	0	0	0	0.1–0.1	0
2		0	0	0	0	0	0
3	0	0		0		0.5–0.7
3		0	0	0	0	0	0

	Dynamic CDN Game			Perfect Cartel Game
p	Type 1	Type 2	Small	Type 1	Type 2	Small
0.1	0.5	0.4	2.0	0	1.7	1.8
0.05	0.8	1.0	2.6	0	2.7	2.7
0.01	1.1	2.6	2.9	0	3.4	2.0

To demonstrate the features at the equilibrium state, we simulate 10,000 periods with all CDNs applying their best strategy. The result is shown in Table 11.6. The first column represents the probability of market shocks. The next three columns show the average numbers of different types of CDNs at the equilibrium state. We can see that there are always more small CDNs than type 1 and type 2 big CDNs. As the probability of market shock decreases, the number of CDNs at the equilibrium state increases. We also show the equilibrium state of the perfect cartel game with market shocks in the last three columns. There is no type 1 CDN, but there are more type 2 CDNs compared to the dynamic CDN game.

We compare the total utility of the dynamic CDN game with the social optimal utility (the perfect cartel game). The result is shown in Figure 11.6. The first observation is that as the probability of market shocks decreases, the utility of both games increases. Further, as the probability decreases, the utility of the dynamic game gets closer to the social optimal utility. With the probability ranges from 0.1 to 0.01, the dynamic game can achieve 63–90% of the social optimal utility. That is, the dynamic CDN game becomes more efficient as the probability of market shocks decreases.