Achieving Good End-to-End Service Using Bill-PayCristian Estan Aditya Akella Suman BanerjeeUniversity of Wisconsin-Madison1 IntroductionOver the past couple of decades, the Internet has rapidlyevolved from a collaborative social experiment to an ag-glomerate of competing commercial providers. This shifthas helped maintain growth and has turned the Internetinto a vast economic force, but it has also introducedsome serious problems. A particularly bad problem isthe inability of end-users to obtain the desired levels ofperformance for their transfers.Today, an organization can set up a contract with itsISP to ensure that the ISP offers good service to its traf-fic. But typical transfers in the Internet traverse multipleISPs and it is clearly infeasible for the organization tohave contracts with all of them. It is possible for neigh-boring ISPs to enter into contracts that require them tooffer good performance to each other’s “premium” traf-fic. However, such contracts are extremely rare and, evenwhen used, cannot guarantee good end-to-end service touser transfers.Our thesis in this paper is that we can support goodend-to-end service to user transfers by extending the cur-rent model of binding bi-lateral contracts between neigh-boring entities (e.g. customers and providers or peeringpartners) with simple mechanisms that produce tacit in-centives for remote ISPs. Our use of the phrase “goodend-to-end service” is intentional: our goal is not to offer“end-to-end QoS” with strict performance guarantees,but rather to provide end users the flexibility to improvethe performance experienced by their transfers, as andwhen desired.Our proposal builds on two main end-user basedmechanisms that generate the tacit incentives.• The carrot: We propose that the end-user include in-band payments with their data. Each ISP then retains aportion of the payment, commensurate with the transitperformance it offers.• The stick: We propose that end-users be able to in-fluence what path their traffic uses and thus bypass re-mote ISPs with unjustifiably bad service and/or thoserequiring unjustifiably high payments.Our proposal, Bill-Pay (Bilateral local nanoPayments),enables end-users to apply these mechanisms in a fine-grained manner by adding, to every individual packet:(1) a small payment which we call “nanopayment”, and(2) information indicating the user’s preferred path andservice levels. In its basic form, Bill-Pay users pay ac-cording to their network usage, but Bill-Pay can support“flat fee” pricing for end users as well. We argue thatBill-Pay enables good service to end-user transfers andallows more effective protection against DDoS floodsand spam.1.1 Overview of Bill-PayWe illustrate the functioning of Bill-Pay using the exam-ple in Figure 1. End-host A wishes to transfer data toend-host B. ISP Y along the path experiences congestionthat reduces the throughput of the transfer below that de-sired by A.ISP XISP XISP YISP YISP ZISP Z20199876ABFigure 1: A uses Bill-Pay nanopayments to achieve priority servicethrough congested ISP Y.All networks and users in this example have local bi-lateral Bill-Pay agreements with their neighbors (A hasan agreement with ISP X, X and Y have an agreement,etc.). To improve throughput in the face of congestion inISP Y, A adds a nanopayment of 20 nanodollars to thedata packet it sends to B. Since ISP X is not congestedit leaves most of the nanopayment in the packet as it for-wards it to ISPY. ISP Y retains 10 nanodollars and givesthe packet preferential treatment. B returns most of theremaining nanopayment in the acknowledgment packetit sends through ISP Z.We note that A owes ISP X 14 nanodollars for this par-ticular pair of packets: while A sent out 20 nanodollars, itreceived6 nanodollars in the acknowledgment. In return,A’s packet received good service despite the congestionin ISP Y. These nanopayment balances are convertedto actual payments at the end of the billing cycle. Wenote that the profit made by an intermediate ISP is re-lated to the number of packets it carries, and the level ofservice it offers. For example, X makes 2 nanodollars fortwo packets and Z makes 1 nanodollar for the one packet(both X and Z offer “regular” service) while Y makes10 nanodollars for offering premium service to a singlepacket.HotNets V Session 7: Money 115The viability of such an architecture depends on fourimportant questions.• How can we ensure that ISPs provide improvedservice at fair prices? In Section 2.1 we discuss theincentives ISPs have to limit the amount of nanopay-ment they retain and to provide a commensurate ser-vice quality. We also discuss various mechanismswhich ISPs can use to determine how much paymentto retain.• How can Bill-Pay end-users avoid expensive andcongested paths? In Section 2.2 we describe a mech-anism that allows the senders to influence the trajec-tory of packets through the network at a granularityslightly finer than AS-level paths, with ISPs retainingcontrol over the level of detail exposed to end-users.• How can the end-user ascertain how large a pay-ment a transfer is worth? In Section 2.3 we dis-cuss the feasibility of a digital secretary that learns theuser’s preferences.• How can the payments be secured from malicioushackers who takecontrolof an end-host? In Section2.4 we discuss mechanisms that ensure that even if theend-host is hijacked, no significant payments can beleaked without the consent of the user.After discussing each of these issues in turn, we ex-amine how our architecture facilitates solutions to vari-ous important problems (Section 3), how it compares toprior related proposals (Section 4), and finally concludewith a discussion of future work (Section 5). The techni-cal report version of this paper [1] also contains a discus-sion of how Bill-Pay can interoperate with existing tech-nologies such as diffserv and how it can be incrementallydeployed.2 Detailed discussion of Bill-PayThe basic Bill-Pay contract is very simple and very easyto enforce: the upstream organization has to pay thedownstream an amount of money equal to the total ofthe nanopayments in the packets it sent, and the down-stream organization has no contractual obligation. Sincethe downstream organization has an economic incentiveto provide good service to the packet, contractual obliga-tions are not needed. More complex contracts linkingpayment to performance metrics such as loss rate andjitter clearly provide a stronger