Network Monitors and Contracting Systems: Competition and Innovation Paul Laskowski John Chuang UC Berkeley {paul,chuang}@sims.berkeley.edu ABSTRACT Today"s Internet industry suffers from several well-known pathologies, but none is as destructive in the long term as its resistance to evolution. Rather than introducing new services, ISPs are presently moving towards greater commoditization. It is apparent that the network"s primitive system of contracts does not align incentives properly. In this study, we identify the network"s lack of accountability as a fundamental obstacle to correcting this problem: Employing an economic model, we argue that optimal routes and innovation are impossible unless new monitoring capability is introduced and incorporated with the contracting system. Furthermore, we derive the minimum requirements a monitoring system must meet to support first-best routing and innovation characteristics. Our work does not constitute a new protocol; rather, we provide practical and specific guidance for the design of monitoring systems, as well as a theoretical framework to explore the factors that influence innovation. Categories and Subject Descriptors C.2.4 [Computer-Communication Networks]: Distributed Systems; J.4 [Social And Behavioral Sciences]: Economics General Terms Economics, Theory, Measurement, Design, Legal Aspects. 1. INTRODUCTION Many studies before us have noted the Internet"s resistance to new services and evolution. In recent decades, numerous ideas have been developed in universities, implemented in code, and even written into the routers and end systems of the network, only to languish as network operators fail to turn them on on a large scale. The list includes Multicast, IPv6, IntServ, and DiffServ. Lacking the incentives just to activate services, there seems to be little hope of ISPs devoting adequate resources to developing new ideas. In the long term, this pathology stands out as a critical obstacle to the network"s continued success (Ratnasamy, Shenker, and McCanne provide extensive discussion in [11]). On a smaller time scale, ISPs shun new services in favor of cost cutting measures. Thus, the network has characteristics of a commodity market. Although in theory, ISPs have a plethora of routing policies at their disposal, the prevailing strategy is to route in the cheapest way possible [2]. On one hand, this leads directly to suboptimal routing. More importantly, commoditization in the short term is surely related to the lack of innovation in the long term. When the routing decisions of others ignore quality characteristics, ISPs are motivated only to lower costs. There is simply no reward for introducing new services or investing in quality improvements. In response to these pathologies and others, researchers have put forth various proposals for improving the situation. These can be divided according to three high-level strategies: The first attempts to improve the status quo by empowering end-users. Clark, et al., suggest that giving end-users control over routing would lead to greater service diversity, recognizing that some payment mechanism must also be provided [5]. Ratnasamy, Shenker, and McCanne postulate a link between network evolution and user-directed routing [11]. They propose a system of Anycast to give end-users the ability to tunnel their packets to an ISP that introduces a desirable protocol. The extra traffic to the ISP, the authors suggest, will motivate the initial investment. The second strategy suggests a revision of the contracting system. This is exemplified by MacKie-Mason and Varian, who propose a smart market to control access to network resources [10]. Prices are set to the market-clearing level based on bids that users associate to their traffic. In another direction, Afergan and Wroclawski suggest that prices should be explicitly encoded in the routing protocols [2]. They argue that such a move would improve stability and align incentives. The third high-level strategy calls for greater network accountability. In this vein, Argyraki, et al., propose a system of packet obituaries to provide feedback as to which ISPs drop packets [3]. They argue that such feedback would help reveal which ISPs were adequately meeting their contractual obligations. Unlike the first two strategies, we are not aware of any previous studies that have connected accountability with the pathologies of commoditization or lack of innovation. It is clear that these three strategies are closely linked to each other (for example, [2], [5], and [9] each argue that giving end-users routing control within the current contracting system is problematic). Until today, however, the relationship between them has been poorly understood. There is currently little theoretical foundation to compare the relative merits of each proposal, and a particular lack of evidence linking accountability with innovation and service differentiation. This paper will address both issues. We will begin by introducing an economic network model that relates accountability, contracts, competition, and innovation. Our model is highly stylized and may be considered preliminary: it is based on a single source sending data to a single destination. Nevertheless, the structure is rich enough to expose previously unseen features of network behavior. We will use our model for two main purposes: First, we will use our model to argue that the lack of accountability in today"s network is a fundamental obstacle to overcoming the pathologies of commoditization and lack of innovation. In other words, unless new monitoring capabilities are introduced, and integrated with the system of contracts, the network cannot achieve optimal routing and innovation characteristics. This result provides motivation for the remainder of the paper, in which we explore how accountability can be leveraged to overcome these pathologies and create a sustainable industry. We will approach this problem from a clean-slate perspective, deriving the level of accountability needed to sustain an ideal competitive structure. When we say that today"s Internet has poor accountability, we mean that it reveals little information about the behavior - or misbehavior - of ISPs. This well-known trait is largely rooted in the network"s history. In describing the design philosophy behind the Internet protocols, Clark lists accountability as the least important among seven second level goals. [4] Accordingly, accountability received little attention during the network"s formative years. Clark relates this to the network"s military context, and finds that had the network been designed for commercial development, accountability would have been a top priority. Argyraki, et al., conjecture that applying the principles of layering and transparency may have led to the network"s lack of accountability [3]. According to these principles, end hosts should be informed of network problems only to the extent that they are required to adapt. They notice when packet drops occur so that they can perform congestion control and retransmit packets. Details of where and why drops occur are deliberately concealed. The network"s lack of accountability is highly relevant to a discussion of innovation because it constrains the system of contracts. This is because contracts depend upon external institutions to function - the judge in the language of incomplete contract theory, or simply the legal system. Ultimately, if a judge cannot verify that some condition holds, she cannot enforce a contract based on that condition. Of course, the vast majority of contracts never end up in court. Especially when a judge"s ruling is easily predicted, the parties will typically comply with the contract terms on their own volition. This would not be possible, however, without the judge acting as a last resort. An institution to support contracts is typically complex, but we abstract it as follows: We imagine that a contract is an algorithm that outputs a payment transfer among a set of ISPs (the parties) at every time. This payment is a function of the past and present behaviors of the participants, but only those that are verifiable. Hence, we imagine that a contract only accepts proofs as inputs. We will call any process that generates these proofs a contractible monitor. Such a monitor includes metering or sensing devices on the physical network, but it is a more general concept. Constructing a proof of a particular behavior may require readings from various devices distributed among many ISPs. The contractible monitor includes whatever distributed algorithmic mechanism is used to motivate ISPs to share this private information. Figure 1 demonstrates how our model of contracts fits together. We make the assumption that all payments are mediated by contracts. This means that without contractible monitors that attest to, say, latency, payments cannot be conditioned on latency. Figure 1: Relationship between monitors and contracts With this model, we may conclude that the level of accountability in today"s Internet only permits best effort contracts. Nodes cannot condition payments on either quality or path characteristics. Is there anything wrong with best-effort contracts? The reader might wonder why the Internet needs contracts at all. After all, in non-network industries, traditional firms invest in research and differentiate their products, all in the hopes of keeping their customers and securing new ones. One might believe that such market forces apply to ISPs as well. We may adopt this as our null hypothesis: Null hypothesis: Market forces are sufficient to maintain service diversity and innovation on a network, at least to the same extent as they do in traditional markets. There is a popular intuitive argument that supports this hypothesis, and it may be summarized as follows: Intuitive argument supporting null hypothesis: 1. Access providers try to increase their quality to get more consumers. 2. Access providers are themselves customers for second hop ISPs, and the second hops will therefore try to provide highquality service in order to secure traffic from access providers. Access providers try to select high quality transit because that increases their quality. 3. The process continues through the network, giving every ISP a competitive reason to increase quality. We are careful to model our network in continuous time, in order to capture the essence of this argument. We can, for example, specify equilibria in which nodes switch to a new next hop in the event of a quality drop. Moreover, our model allows us to explore any theoretically possible punishments against cheaters, including those that are costly for end-users to administer. By contrast, customers in the real world rarely respond collectively, and often simply seek the best deal currently offered. These constraints limit their ability to punish cheaters. Even with these liberal assumptions, however, we find that we must reject our null hypothesis. Our model will demonstrate that identifying a cheating ISP is difficult under low accountability, limiting the threat of market driven punishment. We will define an index of commoditization and show that it increases without bound as data paths grow long. Furthermore, we will demonstrate a framework in which an ISP"s maximum research investment decreases hyperbolically with its distance from the end-user. Network Behavior Monitor Contract Proof Payments 184 To summarize, we argue that the Internet"s lack of accountability must be addressed before the pathologies of commoditization and lack of innovation can be resolved. This leads us to our next topic: How can we leverage accountability to overcome these pathologies? We approach this question from a clean-slate perspective. Instead of focusing on incremental improvements, we try to imagine how an ideal industry would behave, then derive the level of accountability needed to meet that objective. According to this approach, we first craft a new equilibrium concept appropriate for network competition. Our concept includes the following requirements: First, we require that punishing ISPs that cheat is done without rerouting the path. Rerouting is likely to prompt end-users to switch providers, punishing access providers who administer punishments correctly. Next, we require that the equilibrium cannot be threatened by a coalition of ISPs that exchanges illicit side payments. Finally, we require that the punishment mechanism that enforces contracts does not punish innocent nodes that are not in the coalition. The last requirement is somewhat unconventional from an economic perspective, but we maintain that it is crucial for any reasonable solution. Although ISPs provide complementary services when they form a data path together, they are likely to be horizontal competitors as well. If innocent nodes may be punished, an ISP may decide to deliberately cheat and draw punishment onto itself and its neighbors. By cheating, the ISP may save resources, thereby ensuring that the punishment is more damaging to the other ISPs, which probably compete with the cheater directly for some customers. In the extreme case, the cheater may force the other ISPs out of business, thereby gaining a monopoly on some routes. Applying this equilibrium concept, we derive the monitors needed to maintain innovation and optimize routes. The solution is surprisingly simple: contractible monitors must report the quality of the rest of the path, from each ISP to the destination. It turns out that this is the correct minimum accountability requirement, as opposed to either end-to-end monitors or hop-by-hop monitors, as one might initially suspect. Rest of path monitors can be implemented in various ways. They may be purely local algorithms that listen for packet echoes. Alternately, they can be distributed in nature. We describe a way to construct a rest of path monitor out of monitors for individual ISP quality and for the data path. This requires a mechanism to motivate ISPs to share their monitor outputs with each other. The rest of path monitor then includes the component monitors and the distributed algorithmic mechanism that ensures that information is shared as required. This example shows that other types of monitors may be useful as building blocks, but must be combined to form rest of path monitors in order to achieve ideal innovation characteristics. Our study has several practical implications for future protocol design. We show that new monitors must be implemented and integrated with the contracting system before the pathologies of commoditization and lack of innovation can be overcome. Moreover, we derive exactly what monitors are needed to optimize routes and support innovation. In addition, our results provide useful input for clean-slate architectural design, and we use several novel techniques that we expect will be applicable to a variety of future research. The rest of this paper is organized as follows: In section 2, we lay out our basic network model. In section 3, we present a lowaccountability network, modeled after today"s Internet. We demonstrate how poor monitoring causes commoditization and a lack of innovation. In section 4, we present verifiable monitors, and show that proofs, even without contracts, can improve the status quo. In section 5, we turn our attention to contractible monitors. We show that rest of path monitors can support competition games with optimal routing and innovation. We further show that rest of path monitors are required to support such competition games. We continue by discussing how such monitors may be constructed using other monitors as building blocks. In section 6, we conclude and present several directions for future research. 2. BASIC NETWORK MODEL A source, S, wants to send data to destination, D. S and D are nodes on a directed, acyclic graph, with a finite set of intermediate nodes, { }NV ,...2,1= , representing ISPs. All paths lead to D, and every node not connected to D has at least two choices for next hop. We will represent quality by a finite dimensional vector space, Q, called the quality space. Each dimension represents a distinct network characteristic that end-users care about. For example, latency, loss probability, jitter, and IP version can each be assigned to a dimension. To each node, i, we associate a vector in the quality space, Qqi ∈ . This corresponds to the quality a user would experience if i were the only ISP on the data path. Let N Q∈q be the vector of all node qualities. Of course, when data passes through multiple nodes, their qualities combine in some way to yield a path quality. We represent this by an associative binary operation, *: QQQ →× . For path ( )nvvv ,...,, 21 , the quality is given by nvvv qqq ∗∗∗ ...21 . The * operation reflects the characteristics of each dimension of quality. For example, * can act as an addition in the case of latency, multiplication in the case of loss probability, or a minimumargument function in the case of security. When data flows along a complete path from S to D, the source and destination, generally regarded as a single player, enjoy utility given by a function of the path quality, →Qu : . Each node along the path, i, experiences some cost of transmission, ci. 2.1 Game Dynamics Ultimately, we are most interested in policies that promote innovation on the network. In this study, we will use innovation in a fairly general sense. Innovation describes any investment by an ISP that alters its quality vector so that at least one potential data path offers higher utility. This includes researching a new routing algorithm that decreases the amount of jitter users experience. It also includes deploying a new protocol that supports quality of service. Even more broadly, buying new equipment to decrease S D 185 latency may also be regarded as innovation. Innovation may be thought of as the micro-level process by which the network evolves. Our analysis is limited in one crucial respect: We focus on inventions that a single ISP can implement to improve the end-user experience. This excludes technologies that require adoption by all ISPs on the network to function. Because such technologies do not create a competitive advantage, rewarding them is difficult and may require intellectual property or some other market distortion. We defer this interesting topic to future work. At first, it may seem unclear how a large-scale distributed process such as innovation can be influenced by mechanical details like networks monitors. Our model must draw this connection in a realistic fashion. The rate of innovation depends on the profits that potential innovators expect in the future. The reward generated by an invention must exceed the total cost to develop it, or the inventor will not rationally invest. This reward, in turn, is governed by the competitive environment in which the firm operates, including the process by which firms select prices, and agree upon contracts with each other. Of course, these decisions depend on how routes are established, and how contracts determine actual monetary exchanges. Any model of network innovation must therefore relate at least three distinct processes: innovation, competition, and routing. We select a game dynamics that makes the relation between these processes as explicit as possible. This is represented schematically in Figure 2. The innovation stage occurs first, at time 2−=t . In this stage, each agent decides whether or not to make research investments. If she chooses not to, her quality remains fixed. If she makes an investment, her quality may change in some way. It is not necessary for us to specify how such changes take place. The agents" choices in this stage determine the vector of qualities, q, common knowledge for the rest of the game. Next, at time 1−=t , agents participate in the competition stage, in which contracts are agreed upon. In today"s industry, these contracts include prices for transit access, and peering agreements. Since access is provided on a best-effort basis, a transit agreement can simply be represented by its price. Other contracting systems we will explore will require more detail. Finally, beginning at 0=t , firms participate in the routing stage. Other research has already employed repeated games to study routing, for example [1], [12]. Repetition reveals interesting effects not visible in a single stage game, such as informal collusion to elevate prices in [12]. We use a game in continuous time in order to study such properties. For example, we will later ask whether a player will maintain higher quality than her contracts require, in the hope of keeping her customer base or attracting future customers. Our dynamics reflect the fact that ISPs make innovation decisions infrequently. Although real firms have multiple opportunities to innovate, each opportunity is followed by a substantial length of time in which qualities are fixed. The decision to invest focuses on how the firm"s new quality will improve the contracts it can enter into. Hence, our model places innovation at the earliest stage, attempting to capture a single investment decision. Contracting decisions are made on an intermediate time scale, thus appearing next in the dynamics. Routing decisions are made very frequently, mainly to maximize immediate profit flows, so they appear in the last stage. Because of this ordering, our model does not allow firms to route strategically to affect future innovation or contracting decisions. In opposition, Afergan and Wroclawski argue that contracts are formed in response to current traffic patterns, in a feedback loop [2]. Although we are sympathetic to their observation, such an addition would make our analysis intractable. Our model is most realistic when contracting decisions are infrequent. Throughout this paper, our solution concept will be a subgame perfect equilibrium (SPE). An SPE is a strategy point that is a Nash equilibrium when restricted to each subgame. Three important subgames have been labeled in Figure 2. The innovation game includes all three stages. The competition game includes only the competition stage and the routing stage. The routing game includes only the routing stage. An SPE guarantees that players are forward-looking. This means, for example, that in the competition stage, firms must act rationally, maximizing their expected profits in the routing stage. They cannot carry out threats they made in the innovation stage if it lowers their expected payoff. Our schematic already suggests that the routing game is crucial for promoting innovation. To support innovation, the competition game must somehow reward ISPs with high quality. But that means that the routing game must tend to route to nodes with high quality. If the routing game always selects the lowest-cost routes, for example, innovation will not be supported. We will support this observation with analysis later. 2.2 The Routing Game The routing game proceeds in continuous time, with all players discounting by a common factor, r. The outputs from previous stages, q and the set of contracts, are treated as exogenous parameters for this game. For each time 0≥t , each node must select a next hop to route data to. Data flows across the resultant path, causing utility flow to S and D, and a flow cost to the nodes on the path, as described above. Payment flows are also created, based on the contracts in place. Relating our game to the familiar repeated prisoners" dilemma, imagine that we are trying to impose a high quality, but costly path. As we argued loosely above, such paths must be sustainable in order to support innovation. Each ISP on the path tries to maximize her own payment, net of costs, so she may not want to cooperate with our plan. Rather, if she can find a way to save on costs, at the expense of the high quality we desire, she will be tempted to do so. Innovation Game Competition Game Routing Game Innovation stage Competition stage Routing stageQualities (q) Contracts (prices) Profits t = -2 t = -1 t ∈ [ 0 , ) Figure 2: Game Dynamics 186 Analogously to the prisoners" dilemma, we will call such a decision cheating. A little more formally, Cheating refers to any action that an ISP can take, contrary to some target strategy point that we are trying to impose, that enhances her immediate payoff, but compromises the quality of the data path. One type of cheating relates to the data path. Each node on the path has to pay the next node to deliver its traffic. If the next node offers high quality transit, we may expect that a lower quality node will offer a lower price. Each node on the path will be tempted to route to a cheaper next hop, increasing her immediate profits, but lowering the path quality. We will call this type of action cheating in route. Another possibility we can model, is that a node finds a way to save on its internal forwarding costs, at the expense of its own quality. We will call this cheating internally to distinguish it from cheating in route. For example, a node might drop packets beyond the rate required for congestion control, in order to throttle back TCP flows and thus save on forwarding costs [3]. Alternately, a node employing quality of service could give high priority packets a lower class of service, thus saving on resources and perhaps allowing itself to sell more high priority service. If either cheating in route or cheating internally is profitable, the specified path will not be an equilibrium. We assume that cheating can never be caught instantaneously. Rather, a cheater can always enjoy the payoff from cheating for some positive time, which we label 0t . This includes the time for other players to detect and react to the cheating. If the cheater has a contract which includes a customer lock-in period, 0t also includes the time until customers are allowed to switch to a new ISP. As we will see later, it is socially beneficial to decrease 0t , so such lock-in is detrimental to welfare. 3. PATHOLOGIES OF A LOWACCOUNTABILITY NETWORK In order to motivate an exploration of monitoring systems, we begin in this section by considering a network with a poor degree of accountability, modeled after today"s Internet. We will show how the lack of monitoring necessarily leads to poor routing and diminishes the rate of innovation. Thus, the network"s lack of accountability is a fundamental obstacle to resolving these pathologies. 3.1 Accountability in the Current Internet First, we reflect on what accountability characteristics the present Internet has. Argyraki, et al., point out that end hosts are given minimal information about packet drops [3]. Users know when drops occur, but not where they occur, nor why. Dropped packets may represent the innocent signaling of congestion, or, as we mentioned above, they may be a form of cheating internally. The problem is similar for other dimensions of quality, or in fact more acute. Finding an ISP that gives high priority packets a lower class of service, for example, is further complicated by the lack of even basic diagnostic tools. In fact, it is similarly difficult to identify an ISP that cheats in route. Huston notes that Internet traffic flows do not always correspond to routing information [8]. An ISP may hand a packet off to a neighbor regardless of what routes that neighbor has advertised. Furthermore, blocks of addresses are summarized together for distant hosts, so a destination may not even be resolvable until packets are forwarded closer. One might argue that diagnostic tools like ping and traceroute can identify cheaters. Unfortunately, Argyraki, et al., explain that these tools only reveal whether probe packets are echoed, not the fate of past packets [3]. Thus, for example, they are ineffective in detecting low-frequency packet drops. Even more fundamentally, a sophisticated cheater can always spot diagnostic packets and give them special treatment. As a further complication, a cheater may assume different aliases for diagnostic packets arriving over different routes. As we will see below, this gives the cheater a significant advantage in escaping punishment for bad behavior, even if the data path is otherwise observable. 3.2 Modeling Low-Accountability As the above evidence suggests, the current industry allows for very little insight into the behavior of the network. In this section, we attempt to capture this lack of accountability in our model. We begin by defining a monitor, our model of the way that players receive external information about network behavior, A monitor is any distributed algorithmic mechanism that runs on the network graph, and outputs, to specific nodes, informational statements about current or past network behavior. We assume that all external information about network behavior is mediated in this way. The accountability properties of the Internet can be represented by the following monitors: E2E (End to End): A monitor that informs S/D about what the total path quality is at any time (this is the quality they experience). ROP (Rest of Path): A monitor that informs each node along the data path what the quality is for the rest of the path to the destination. PRc (Packets Received): A monitor that tells nodes how much data they accept from each other, so that they can charge by volume. It is important to note, however, that this information is aggregated over many source-destination pairs. Hence, for the sake of realism, it cannot be used to monitor what the data path is. Players cannot measure the qualities of other, single nodes, just the rest of the path. Nodes cannot see the path past the next hop. This last assumption is stricter than needed for our results. The critical ingredient is that nodes cannot verify that the path avoids a specific hop. This holds, for example, if the path is generally visible, except nodes can use different aliases for different parents. Similar results also hold if alternate paths always converge after some integer number, m, of hops. It is important to stress that E2E and ROP are not the contractible monitors we described in the introduction - they do not generate proofs. Thus, even though a player observes certain information, she generally cannot credibly share it with another player. For example, if a node after the first hop starts cheating, the first hop will detect the sudden drop in quality for the rest of the path, but the first hop cannot make the source believe this observation - the 187 source will suspect that the first hop was the cheater, and fabricated the claim against the rest of the path. Typically, E2E and ROP are envisioned as algorithms that run on a single node, and listen for packet echoes. This is not the only way that they could be implemented, however; an alternate strategy is to aggregate quality measurements from multiple points in the network. These measurements can originate in other monitors, located at various ISPs. The monitor then includes the component monitors as well as whatever mechanisms are in place to motivate nodes to share information honestly as needed. For example, if the source has monitors that reveal the qualities of individual nodes, they could be combined with path information to create an ROP monitor. Since we know that contracts only accept proofs as input, we can infer that payments in this environment can only depend on the number of packets exchanged between players. In other words, contracts are best-effort. For the remainder of this section, we will assume that contracts are also linear - there is a constant payment flow so long as a node accepts data, and all conditions of the contract are met. Other, more complicated tariffs are also possible, and are typically used to generate lock-in. We believe that our parameter t0 is sufficient to describe lock-in effects, and we believe that the insights in this section apply equally to any tariffs that are bounded so that the routing game remains continuous at infinity. Restricting attention to linear contracts allows us to represent some node i"s contract by its price, pi. Because we further know that nodes cannot observe the path after the next hop, we can infer that contracts exist only between neighboring nodes on the graph. We will call this arrangement of contracts bilateral. When a competition game exclusively uses bilateral contracts, we will call it a bilateral contract competition game. We first focus on the routing game and ask whether a high quality route can be maintained, even when a low quality route is cheaper. Recall that this is a requirement in order for nodes to have any incentive to innovate. If nodes tend to route to low price next hops, regardless of quality, we say that the network is commoditized. To measure this tendency, we define an index of commoditization as follows: For a node on the data path, i, define its quality premium, minppd ji −= , where pj is the flow payment to the next hop in equilibrium, and pmin is the price of the lowest cost next hop. Definition: The index of commoditization, CI , is the average, over each node on the data path, i, of i"s flow profit as a fraction of i"s quality premium, ( ) ijii dpcp /−− . CI ranges from 0, when each node spends all of its potential profit on its quality premium, to infinite, when a node absorbs positive profit, but uses the lowest price next hop. A high value for CI implies that nodes are spending little of their money inflow on purchasing high quality for the rest of the path. As the next claim shows, this is exactly what happens as the path grows long: Claim 1. If the only monitors are E2E, ROP, and PRc, ∞→CI as ∞→n , where n is the number of nodes on the data path. To show that this is true, we first need the following lemma, which will establish the difficulty of punishing nodes in the network. First a bit of notation: Recall that a cheater can benefit from its actions for 00 >t before other players can react. When a node cheats, it can expect a higher profit flow, at least until it is caught and other players react, perhaps by diverting traffic. Let node i"s normal profit flow be iπ , and her profit flow during cheating be some greater value, yi. We will call the ratio, iiy π/ , the temptation to cheat. Lemma 1. If the only monitors are E2E, ROP, and PRc, the discounted time, −nt rt e 0 , needed to punish a cheater increases at least as fast as the product of the temptations to cheat along the data path, ∏ −− ≥ 0 0 pathdataon 0 t rt i i i t rt e y e n π (1) Corollary. If nodes share a minimum temptation to cheat, π/y , the discounted time needed to punish cheating increases at least exponentially in the length of the data path, n, −− ≥ 0 00 t rt nt rt e y e n π (2) Since it is the discounted time that increases exponentially, the actual time increases faster than exponentially. If n is so large that tn is undefined, the given path cannot be maintained in equilibrium. Proof. The proof proceeds by induction on the number of nodes on the equilibrium data path, n. For 1=n , there is a single node, say i. By cheating, the node earns extra profit ( ) − − 0 0 t rt ii ey π . If node i is then punished until time 1t , the extra profit must be cancelled out by the lost profit between time 0t and 1t , −1 0 t t rt i eπ . A little manipulation gives −− = 01 00 t rt i i t rt e y e π , as required. For 1>n , assume for induction that the claim holds for 1−n . The source does not know whether the cheater is the first hop, or after the first hop. Because the source does not know the data path after the first hop, it is unable to punish nodes beyond it. If it chooses a new first hop, it might not affect the rest of the data path. Because of this, the source must rely on the first hop to punish cheating nodes farther along the path. The first hop needs discounted time, ∏ −0 0 hopfirstafter t rt i i i e y π , to accomplish this by assumption. So the source must give the first hop this much discounted time in order to punish defectors further down the line (and the source will expect poor quality during this period). Next, the source must be protected against a first hop that cheats, and pretends that the problem is later in the path. The first hop can 188 do this for the full discounted time, ∏ −0 0 hopfirstafter t rt i i i e y π , so the source must punish the first hop long enough to remove the extra profit it can make. Following the same argument as for 1=n , we can show that the full discounted time is ∏ −0 0 pathdataon t rt i i i e y π , which completes the proof. The above lemma and its corollary show that punishing cheaters becomes more and more difficult as the data path grows long, until doing so is impossible. To capture some intuition behind this result, imagine that you are an end user, and you notice a sudden drop in service quality. If your data only travels through your access provider, you know it is that provider"s fault. You can therefore take your business elsewhere, at least for some time. This threat should motivate your provider to maintain high quality. Suppose, on the other hand, that your data traverses two providers. When you complain to your ISP, he responds, yes, we know your quality went down, but it"s not our fault, it"s the next ISP. Give us some time to punish them and then normal quality will resume. If your access provider is telling the truth, you will want to listen, since switching access providers may not even route around the actual offender. Thus, you will have to accept lower quality service for some longer time. On the other hand, you may want to punish your access provider as well, in case he is lying. This means you have to wait longer to resume normal service. As more ISPs are added to the path, the time increases in a recursive fashion. With this lemma in hand, we can return to prove Claim 1. Proof of Claim 1. Fix an equilibrium data path of length n. Label the path nodes 1,2,…,n. For each node i, let i"s quality premium be '11 ++ −= iii ppd . Then we have, [ ] = − = − + + = − + ++ = + −=− −− −− = −− − = −− = n i i n i iii iii n i iii ii n i i iii C g npcp pcp n pcp pp nd pcp n I 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 '1 '11 , (3) where gi is node i"s temptation to cheat by routing to the lowest price next hop. Lemma 1 tells us that Tg n i i <∏ =1 , where ( )01 rt eT − −= . It requires a bit of calculus to show that IC is minimized by setting each gi equal to n T /1 . However, as ∞→n , we have 1/1 →n T , which shows that ∞→CI . According to the claim, as the data path grows long, it increasingly resembles a lowest-price path. Since lowest-price routing does not support innovation, we may speculate that innovation degrades with the length of the data path. Though we suspect stronger claims are possible, we can demonstrate one such result by including an extra assumption: Available Bargain Path: A competitive market exists for lowcost transit, such that every node can route to the destination for no more than flow payment, lp . Claim 2. Under the available bargain path assumption, if node i , a distance n from S, can invest to alter its quality, and the source will spend no more than sP for a route including node i"s new quality, then the payment to node i, p, decreases hyperbolically with n, ( ) ( ) s n l P n T pp 1 1/1 − +≤ − , (4) where ( )01 rt eT − −= is the bound on the product of temptations from the previous claim. Thus, i will spend no more than ( ) ( )− + − s n l P n T p r 1 1 1/1 on this quality improvement, which approaches the bargain path"s payment, r pl , as ∞→n . The proof is given in the appendix. As a node gets farther from the source, its maximum payment approaches the bargain price, pl. Hence, the reward for innovation is bounded by the same amount. Large innovations, meaning substantially more expensive than rpl / , will not be pursued deep into the network. Claim 2 can alternately be viewed as a lower bound on how much it costs to elicit innovation in a network. If the source S wants node i to innovate, it needs to get a motivating payment, p, to i during the routing stage. However, it must also pay the nodes on the way to i a premium in order to motivate them to route properly. The claim shows that this premium increases with the distance to i, until it dwarfs the original payment, p. Our claims stand in sharp contrast to our null hypothesis from the introduction. Comparing the intuitive argument that supported our hypothesis with these claims, we can see that we implicitly used an oversimplified model of market pressure (as either present or not). As is now clear, market pressure relies on the decisions of customers, but these are limited by the lack of information. Hence, competitive forces degrade as the network deepens. 4. VERIFIABLE MONITORS In this section, we begin to introduce more accountability into the network. Recall that in the previous section, we assumed that players couldn"t convince each other of their private information. What would happen if they could? If a monitor"s informational signal can be credibly conveyed to others, we will call it a verifiable monitor. The monitor"s output in this case can be thought of as a statement accompanied by a proof, a string that can be processed by any player to determine that the statement is true. A verifiable monitor is a distributed algorithmic mechanism that runs on the network graph, and outputs, to specific nodes, proofs about current or past network behavior. Along these lines, we can imagine verifiable counterparts to E2E and ROP. We will label these E2Ev and ROPv. With these monitors, each node observes the quality of the rest of the path and can also convince other players of these observations by giving them a proof. 189 By adding verifiability to our monitors, identifying a single cheater is straightforward. The cheater is the node that cannot produce proof that the rest of path quality decreased. This means that the negative results of the previous section no longer hold. For example, the following lemma stands in contrast to Lemma 1. Lemma 2. With monitors E2Ev, ROPv, and PRc, and provided that the node before each potential cheater has an alternate next hop that isn"t more expensive, it is possible to enforce any data path in SPE so long as the maximum temptation is less than what can be deterred in finite time, − ≤ 0 0 max 1 t rt er y π (5) Proof. This lemma follows because nodes can share proofs to identify who the cheater is. Only that node must be punished in equilibrium, and the preceding node does not lose any payoff in administering the punishment. With this lemma in mind, it is easy to construct counterexamples to Claim 1 and Claim 2 in this new environment. Unfortunately, there are at least four reasons not to be satisfied with this improved monitoring system. The first, and weakest reason is that the maximum temptation remains finite, causing some distortion in routes or payments. Each node along a route must extract some positive profit unless the next hop is also the cheapest. Of course, if t0 is small, this effect is minimal. The second, and more serious reason is that we have always given our source the ability to commit to any punishment. Real world users are less likely to act collectively, and may simply search for the best service currently offered. Since punishment phases are generally characterized by a drop in quality, real world end-users may take this opportunity to shop for a new access provider. This will make nodes less motivated to administer punishments. The third reason is that Lemma 2 does not apply to cheating by coalitions. A coalition node may pretend to punish its successor, but instead enjoy a secret payment from the cheating node. Alternately, a node may bribe its successor to cheat, if the punishment phase is profitable, and so forth. The required discounted time for punishment may increase exponentially in the number of coalition members, just as in the previous section! The final reason not to accept this monitoring system is that when a cheater is punished, the path will often be routed around not just the offender, but around other nodes as well. Effectively, innocent nodes will be punished along with the guilty. In our abstract model, this doesn"t cause trouble since the punishment falls off the equilibrium path. The effects are not so benign in the real world. When ISPs lie in sequence along a data path, they contribute complementary services, and their relationship is vertical. From the perspective of other source-destination pairs, however, these same firms are likely to be horizontal competitors. Because of this, a node might deliberately cheat, in order to trigger punishment for itself and its neighbors. By cheating, the node will save money to some extent, so the cheater is likely to emerge from the punishment phase better off than the innocent nodes. This may give the cheater a strategic advantage against its competitors. In the extreme, the cheater may use such a strategy to drive neighbors out of business, and thereby gain a monopoly on some routes. 5. CONTRACTIBLE MONITORS At the end of the last section, we identified several drawbacks that persist in an environment with E2Ev, ROPv, and PRc. In this section, we will show how all of these drawbacks can be overcome. To do this, we will require our third and final category of monitor: A contractible monitor is simply a verifiable monitor that generates proofs that can serve as input to a contract. Thus, contractible is jointly a property of the monitor and the institutions that must verify its proofs. Contractibility requires that a court, 1. Can verify the monitor"s proofs. 2. Can understand what the proofs and contracts represent to the extent required to police illegal activity. 3. Can enforce payments among contracting parties. Understanding the agreements between companies has traditionally been a matter of reading contracts on paper. This may prove to be a harder task in a future network setting. Contracts may plausibly be negotiated by machine, be numerous, even per-flow, and be further complicated by the many dimensions of quality. When a monitor (together with institutional infrastructure) meets these criteria, we will label it with a subscript c, for contractible. The reader may recall that this is how we labeled the packets received monitor, PRc, which allows ISPs to form contracts with per-packet payments. Similarly, E2Ec and ROPc are contractible versions of the monitors we are now familiar with. At the end of the previous section, we argued for some desirable properties that we"d like our solution to have. Briefly, we would like to enforce optimal data paths with an equilibrium concept that doesn"t rely on re-routing for punishment, is coalition proof, and doesn"t punish innocent nodes when a coalition cheats. We will call such an equilibrium a fixed-route coalition-proof protect-theinnocent equilibrium. As the next claim shows, ROPc allows us to create a system of linear (price, quality) contracts under just such an equilibrium. Claim 3. With ROPc, for any feasible and consistent assignment of rest of path qualities to nodes, and any corresponding payment schedule that yields non-negative payoffs, these qualities can be maintained with bilateral contracts in a fixed-route coalition-proof protect-the-innocent equilibrium. Proof: Fix any data path consistent with the given rest of path qualities. Select some monetary punishment, P, large enough to prevent any cheating for time t0 (the discounted total payment from the source will work). Let each node on the path enter into a contract with its parent, which fixes an arbitrary payment schedule so long as the rest of path quality is as prescribed. When the parent node, which has ROPc, submits a proof that the rest of path quality is less than expected, the contract awards her an instantaneous transfer, P, from the downstream node. Such proofs can be submitted every 0t for the previous interval. Suppose now that a coalition, C, decides to cheat. The source measures a decrease in quality, and according to her contract, is awarded P from the first hop. This means that there is a net outflow of P from the ISPs as a whole. Suppose that node i is not in C. In order for the parent node to claim P from i, it must submit proof that the quality of the path starting at i is not as prescribed. This means 190 that there is a cheater after i. Hence, i would also have detected a change in quality, so i can claim P from the next node on the path. Thus, innocent nodes are not punished. The sequence of payments must end by the destination, so the net outflow of P must come from the nodes in C. This establishes all necessary conditions of the equilibrium. Essentially, ROPc allows for an implementation of (price, quality) contracts. Building upon this result, we can construct competition games in which nodes offer various qualities to each other at specified prices, and can credibly commit to meet these performance targets, even allowing for coalitions and a desire to damage other ISPs. Example 1. Define a Stackelberg price-quality competition game as follows: Extend the partial order of nodes induced by the graph to any complete ordering, such that downstream nodes appear before their parents. In this order, each node selects a contract to offer to its parents, consisting of a rest of path quality, and a linear price. In the routing game, each node selects a next hop at every time, consistent with its advertised rest of path quality. The Stackelberg price-quality competition game can be implemented in our model with ROPc monitors, by using the strategy in the proof, above. It has the following useful property: Claim 4. The Stackelberg price-quality competition game yields optimal routes in SPE. The proof is given in the appendix. This property is favorable from an innovation perspective, since firms that invest in high quality will tend to fall on the optimal path, gaining positive payoff. In general, however, investments may be over or under rewarded. Extra conditions may be given under which innovation decisions approach perfect efficiency for large innovations. We omit the full analysis here. Example 2. Alternately, we can imagine that players report their private information to a central authority, which then assigns all contracts. For example, contracts could be computed to implement the cost-minimizing VCG mechanism proposed by Feigenbaum, et al. in [7]. With ROPc monitors, we can adapt this mechanism to maximize welfare. For node, i, on the optimal path, L, the net payment must equal, essentially, its contribution to the welfare of S, D, and the other nodes. If L" is an optimal path in the graph with i removed, the profit flow to i is, ( ) ( ) ∈≠∈ +−− ', ' Lj j ijLj jLL ccququ , (6) where Lq and 'Lq are the qualities of the two paths. Here, (price, quality) contracts ensure that nodes report their qualities honestly. The incentive structure of the VCG mechanism is what motivates nodes to report their costs accurately. A nice feature of this game is that individual innovation decisions are efficient, meaning that a node will invest in an innovation whenever the investment cost is less than the increased welfare of the optimal data path. Unfortunately, the source may end up paying more than the utility of the path. Notice that with just E2Ec, a weaker version of Claim 3 holds. Bilateral (price, quality) contracts can be maintained in an equilibrium that is fixed-route and coalition-proof, but not protectthe-innocent. This is done by writing contracts to punish everyone on the path when the end to end quality drops. If the path length is n, the first hop pays nP to the source, the second hop pays ( )Pn 1− to the first, and so forth. This ensures that every node is punished sufficiently to make cheating unprofitable. For the reasons we gave previously, we believe that this solution concept is less than ideal, since it allows for malicious nodes to deliberately trigger punishments for potential competitors. Up to this point, we have adopted fixed-route coalition-proof protect-the-innocent equilibrium as our desired solution concept, and shown that ROPc monitors are sufficient to create some competition games that are desirable in terms of service diversity and innovation. As the next claim will show, rest of path monitoring is also necessary to construct such games under our solution concept. Before we proceed, what does it mean for a game to be desirable from the perspective of service diversity and innovation? We will use a very weak assumption, essentially, that the game is not fully commoditized for any node. The claim will hold for this entire class of games. Definition: A competition game is nowhere-commoditized if for each node, i, not adjacent to D, there is some assignment of qualities and marginal costs to nodes, such that the optimal data path includes i, and i has a positive temptation to cheat. In the case of linear contracts, it is sufficient to require that ∞<CI , and that every node make positive profit under some assignment of qualities and marginal costs. Strictly speaking, ROPc monitors are not the only way to construct these desirable games. To prove the next claim, we must broaden our notion of rest of path monitoring to include the similar ROPc" monitor, which attests to the quality starting at its own node, through the end of the path. Compare the two monitors below: ROPc: gives a node proof that the path quality from the next node to the destination is not correct. ROPc": gives a node proof that the path quality from that node to the destination is correct. We present a simplified version of this claim, by including an assumption that only one node on the path can cheat at a time (though conspirators can still exchange side payments). We will discuss the full version after the proof. Claim 5. Assume a set of monitors, and a nowhere-commoditized bilateral contract competition game that always maintains the optimal quality in fixed-route coalition-proof protect-the-innocent equilibrium, with only one node allowed to cheat at a time. Then for each node, i, not adjacent to D, either i has an ROPc monitor, or i"s children each have an ROPc" monitor. Proof: First, because of the fixed-route assumption, punishments must be purely monetary. Next, when cheating occurs, if the payment does not go to the source or destination, it may go to another coalition member, rendering it ineffective. Thus, the source must accept some monetary compensation, net of its normal flow payment, when cheating occurs. Since the source only contracts with the first hop, it must accept this money from the first hop. The source"s contract must therefore distinguish when the path quality is normal from when it is lowered by cheating. To do so, it can either accept proofs 191 from the source, that the quality is lower than required, or it can accept proofs from the first hop, that the quality is correct. These nodes will not rationally offer the opposing type of proof. By definition, any monitor that gives the source proof that the path quality is wrong is an ROPc monitor. Any monitor that gives the first hop proof that the quality is correct is a ROPc" monitor. Thus, at least one of these monitors must exist. By the protect-the-innocent assumption, if cheating occurs, but the first hop is not a cheater, she must be able to claim the same size reward from the next ISP on the path, and thus pass on the punishment. The first hop"s contract with the second must then distinguish when cheating occurs after the first hop. By argument similar to that for the source, either the first hop has a ROPc monitor, or the second has a ROPc" monitor. This argument can be iterated along the entire path to the penultimate node before D. Since the marginal costs and qualities can be arranged to make any path the optimal path, these statements must hold for all nodes and their children, which completes the proof. The two possibilities for monitor correspond to which node has the burden of proof. In one case, the prior node must prove the suboptimal quality to claim its reward. In the other, the subsequent node must prove that the quality was correct to avoid penalty. Because the two monitors are similar, it seems likely that they require comparable costs to implement. If submitting the proofs is costly, it seems natural that nodes would prefer to use the ROPc monitor, placing the burden of proof on the upstream node. Finally, we note that it is straightforward to derive the full version of the claim, which allows for multiple cheaters. The only complication is that cheaters can exchange side payments, which makes any money transfers between them redundant. Because of this, we have to further generalize our rest of path monitors, so they are less constrained in the case that there are cheaters on either side. 5.1 Implementing Monitors Claim 5 should not be interpreted as a statement that each node must compute the rest of path quality locally, without input from other nodes. Other monitors, besides ROPc and ROPc" can still be used, loosely speaking, as building blocks. For instance, network tomography is concerned with measuring properties of the network interior with tools located at the edge. Using such techniques, our source might learn both individual node qualities and the data path. This is represented by the following two monitors: SHOPc i : (source-based hop quality) A monitor that gives the source proof of what the quality of node i is. SPATHc: (source-based path) A monitor that gives the source proof of what the data path is at any time, at least as far as it matches the equilibrium path. With these monitors, a punishment mechanism can be designed to fulfill the conditions of Claim 5. It involves the source sharing the proofs it generates with nodes further down the path, which use them to determine bilateral payments. Ultimately however, the proof of Claim 5 shows us that each node i"s bilateral contracts require proof of the rest of path quality. This means that node i (or possibly its children) will have to combine the proofs that they receive to generate a proof of the rest of path quality. Thus, the combined process is itself a rest of path monitor. What we have done, all in all, is constructed a rest of path monitor using SPATHc and SHOPc i as building blocks. Our new monitor includes both the component monitors and whatever distributed algorithmic mechanism exists to make sure nodes share their proofs correctly. This mechanism can potentially involve external institutions. For a concrete example, suppose that when node i suspects it is getting poor rest of path quality from its successor, it takes the downstream node to court. During the discovery process, the court subpoenas proofs of the path and of node qualities from the source (ultimately, there must be some threat to ensure the source complies). Finally, for the court to issue a judgment, one party or the other must compile a proof of what the rest of path quality was. Hence, the entire discovery process acts as a rest of path monitor, albeit a rather costly monitor in this case. Of course, mechanisms can be designed to combine these monitors at much lower cost. Typically, such mechanisms would call for automatic sharing of proofs, with court intervention only as a last resort. We defer these interesting mechanisms to future work. As an aside, intuition might dictate that SHOPc i generates more information than ROPc; after all, inferring individual node qualities seems a much harder problem. Yet, without path information, SHOPc i is not sufficient for our first-best innovation result. The proof of this demonstrates a useful technique: Claim 6. With monitors E2E, ROP, SHOPc i and PRc, and a nowhere-commoditized bilateral contract competition game, the optimal quality cannot be maintained for all assignments of quality and marginal cost, in fixed-route coalition-proof protect-theinnocent equilibrium. Proof: Because nodes cannot verify the data path, they cannot form a proof of what the rest of path quality is. Hence, ROPc monitors do not exist, and therefore the requirements of Claim 5 cannot hold. 6. CONCLUSIONS AND FUTURE WORK It is our hope that this study will have a positive impact in at least three different ways. The first is practical: we believe our analysis has implications for the design of future monitoring protocols and for public policy. For protocol designers, we first provide fresh motivation to create monitoring systems. We have argued that the poor accountability of the Internet is a fundamental obstacle to alleviating the pathologies of commoditization and lack of innovation. Unless accountability improves, these pathologies are guaranteed to remain. Secondly, we suggest directions for future advances in monitoring. We have shown that adding verifiability to monitors allows for some improvements in the characteristics of competition. At the same time, this does not present a fully satisfying solution. This paper has suggested a novel standard for monitors to aspire to - one of supporting optimal routes in innovative competition games under fixed-route coalition-proof protect-the-innocent equilibrium. We have shown that under bilateral contracts, this specifically requires contractible rest of path monitors. This is not to say that other types of monitors are unimportant. We included an example in which individual hop quality monitors and a path monitor can also meet our standard for sustaining competition. However, in order for this to happen, a mechanism must be included 192 to combine proofs from these monitors to form a proof of rest of path quality. In other words, the monitors must ultimately be combined to form contractible rest of path monitors. To support service differentiation and innovation, it may be easier to design rest of path monitors directly, thereby avoiding the task of designing mechanisms for combining component monitors. As far as policy implications, our analysis points to the need for legal institutions to enforce contracts based on quality. These institutions must be equipped to verify proofs of quality, and police illegal contracting behavior. As quality-based contracts become numerous and complicated, and possibly negotiated by machine, this may become a challenging task, and new standards and regulations may have to emerge in response. This remains an interesting and unexplored area for research. The second area we hope our study will benefit is that of clean-slate architectural design. Traditionally, clean-slate design tends to focus on creating effective and elegant networks for a static set of requirements. Thus, the approach is often one of engineering, which tends to neglect competitive effects. We agree with Ratnasamy, Shenker, and McCanne, that designing for evolution should be a top priority [11]. We have demonstrated that the network"s monitoring ability is critical to supporting innovation, as are the institutions that support contracting. These elements should feature prominently in new designs. Our analysis specifically suggests that architectures based on bilateral contracts should include contractible rest of path monitoring. From a clean-slate perspective, these monitors can be transparently and fully integrated with the routing and contracting systems. Finally, the last contribution our study makes is methodological. We believe that the mathematical formalization we present is applicable to a variety of future research questions. While a significant literature addresses innovation in the presence of network effects, to the best of our knowledge, ours is the first model of innovation in a network industry that successfully incorporates the actual topological structure as input. This allows the discovery of new properties, such as the weakening of market forces with the number of ISPs on a data path that we observe with lowaccountability. Our method also stands in contrast to the typical approach of distributed algorithmic mechanism design. Because this field is based on a principle-agent framework, contracts are usually proposed by the source, who is allowed to make a take it or leave it offer to network nodes. Our technique allows contracts to emerge from a competitive framework, so the source is limited to selecting the most desirable contract. We believe this is a closer reflection of the industry. Based on the insights in this study, the possible directions for future research are numerous and exciting. To some degree, contracting based on quality opens a Pandora"s Box of pressing questions: Do quality-based contracts stand counter to the principle of network neutrality? Should ISPs be allowed to offer a choice of contracts at different quality levels? What anti-competitive behaviors are enabled by quality-based contracts? Can a contracting system support optimal multicast trees? In this study, we have focused on bilateral contracts. This system has seemed natural, especially since it is the prevalent system on the current network. Perhaps its most important benefit is that each contract is local in nature, so both parties share a common, familiar legal jurisdiction. There is no need to worry about who will enforce a punishment against another ISP on the opposite side of the planet, nor is there a dispute over whose legal rules to apply in interpreting a contract. Although this benefit is compelling, it is worth considering other systems. The clearest alternative is to form a contract between the source and every node on the path. We may call these source contracts. Source contracting may present surprising advantages. For instance, since ISPs do not exchange money with each other, an ISP cannot save money by selecting a cheaper next hop. Additionally, if the source only has contracts with nodes on the intended path, other nodes won"t even be willing to accept packets from this source since they won"t receive compensation for carrying them. This combination seems to eliminate all temptation for a single cheater to cheat in route. Because of this and other encouraging features, we believe source contracts are a fertile topic for further study. Another important research task is to relax our assumption that quality can be measured fully and precisely. One possibility is to assume that monitoring is only probabilistic or suffers from noise. Even more relevant is the possibility that quality monitors are fundamentally incomplete. A quality monitor can never anticipate every dimension of quality that future applications will care about, nor can it anticipate a new and valuable protocol that an ISP introduces. We may define a monitor space as a subspace of the quality space that a monitor can measure, QM ⊂ , and a corresponding monitoring function that simply projects the full range of qualities onto the monitor space, MQm →: . Clearly, innovations that leave quality invariant under m are not easy to support - they are invisible to the monitoring system. In this environment, we expect that path monitoring becomes more important, since it is the only way to ensure data reaches certain innovator ISPs. Further research is needed to understand this process. 7. ACKNOWLEDGEMENTS We would like to thank the anonymous reviewers, Jens Grossklags, Moshe Babaioff, Scott Shenker, Sylvia Ratnasamy, and Hal Varian for their comments. This work is supported in part by the National Science Foundation under ITR award ANI-0331659. 8. REFERENCES [1] Afergan, M. Using Repeated Games to Design IncentiveBased Routing Systems. In Proceedings of IEEE INFOCOM (April 2006). [2] Afergan, M. and Wroclawski, J. On the Benefits and Feasibility of Incentive Based Routing Infrastructure. In ACM SIGCOMM'04 Workshop on Practice and Theory of Incentives in Networked Systems (PINS) (August 2004). [3] Argyraki, K., Maniatis, P., Cheriton, D., and Shenker, S. Providing Packet Obituaries. In Third Workshop on Hot Topics in Networks (HotNets) (November 2004). [4] Clark, D. D. The Design Philosophy of the DARPA Internet Protocols. In Proceedings of ACM SIGCOMM (1988). 193 [5] Clark, D. D., Wroclawski, J., Sollins, K. R., and Braden, R. Tussle in cyberspace: Defining tomorrow's internet. In Proceedings of ACM SIGCOMM (August 2002). [6] Dang-Nguyen, G. and Pénard, T. Interconnection Agreements: Strategic Behaviour and Property Rights. In Brousseau, E. and Glachant, J.M. Eds. The Economics of Contracts: Theories and Applications, Cambridge University Press, 2002. [7] Feigenbaum, J., Papadimitriou, C., Sami, R., and Shenker, S. A BGP-based Mechanism for Lowest-Cost Routing. Distributed Computing 18 (2005), pp. 61-72. [8] Huston, G. Interconnection, Peering, and Settlements. Telstra, Australia. [9] Liu, Y., Zhang, H., Gong, W., and Towsley, D. On the Interaction Between Overlay Routing and Traffic Engineering. In Proceedings of IEEE INFOCOM (2005). [10] MacKie-Mason, J. and Varian, H. Pricing the Internet. In Kahin, B. and Keller, J. Eds. Public access to the Internet. Englewood Cliffs, NJ; Prentice-Hall, 1995. [11] Ratnasamy, S., Shenker, S., and McCanne, S. Towards an Evolvable Internet Architecture. In Proceeding of ACM SIGCOMM (2005). [12] Shakkottai, S., and Srikant, R. Economics of Network Pricing with Multiple ISPs. In Proceedings of IEEE INFOCOM (2005). 9. APPENDIX Proof of Claim 2. Node i must fall on the equilibrium data path to receive any payment. Let the prices along the data path be ppppP nS == ,..., 21 , with marginal costs, ncc ,...,1 . We may assume the prices on the path are greater than lp or the claim follows trivially. Each node along the data path can cheat in route by giving data to the bargain path at price no more than lp . So node j"s temptation to cheat is at least 11 ++ − − ≥ −− −− jj l jjj ljj pp pp pcp pcp . Then Lemma 1 gives, 1 13221 1... − − − −> − − ⋅⋅ − − − − ≥ n S l n lll P pp n pp pp pp pp pp pp T (7) This can be rearranged to give ( ) ( ) s n l P n T pp 1 1/1 − +≤ − , as required. The rest of the claim simply recognizes that rp / is the greatest reward node i can receive for its investment, so it will not invest sums greater than this. Proof of Claim 4. Label the nodes 1,2,.. N in the order in which they select contracts. Let subgame n be the game that begins with n choosing its contract. Let Ln be the set of possible paths restricted to nodes n,…,N. That is, Ln is the set of possible routes from S to reach some node that has already moved. For subgame n, define the local welfare over paths nLl ∈ , and their possible next hops, nj < as follows, ( ) ( ) j li ipathjl pcqqujlV −−= ∈ *, , (8) where ql is the quality of path l in the set {n,…,N}, and pathjq and pj are the quality and price of the contract j has offered. For induction, assume that subgame n + 1 maximizes local welfare. We show that subgame n does as well. If node n selects next hop k, we can write the following relation, ( ) ( )( ) ( )( ) nknn knlVpcpknlVnlV π−=++−= ,,,,, , (9) where n is node n"s profit if the path to n is chosen. This path is chosen whenever ( )nlV , is maximal over Ln+1 and possible next hops. If ( )( )knlV ,, is maximal over Ln, it is also maximal over the paths in Ln+1 that don"t lead to n. This means that node n can choose some n small enough so that ( )nlV , is maximal over Ln+1, so the route will lead to k. Conversely, if ( )( )knlV ,, is not maximal over Ln, either V is greater for another of n"s next hops, in which case n will select that one in order to increase n, or V is greater for some path in Ln+1 that don"t lead to n, in which case ( )nlV , cannot be maximal for any nonnegative n. Thus, we conclude that subgame n maximizes local welfare. For the initial case, observe that this assumption holds for the source. Finally, we deduce that subgame 1, which is the entire game, maximizes local welfare, which is equivalent to actual welfare. Hence, the Stackelberg price-quality game yields an optimal route. 194
smart market verifiable monitor contractible monitor contracting system commoditization innovation monitor contract incentive
network monitor routing stagequality routing policy clean-slate architectural design