Managing incentives in community network clouds

Managing Incentives in Community Network Clouds Amin M. Khan a dissertation presented to the faculty of Universitat Politècnica de Catalunya in candidacy for the degree of Doctor of Philosophy recommended for acceptance by the Department of Computer Architecture Advisors: Dr. Felix Freitag & Dr. Luís Rodrigues April 2016 ©2016 – Amin M. Khan all rights reserved. To my family. To my teachers, my mentors. Acknowledgments I am hugely indebted to my advisors, Felix Freitag and Luís Rodrigues, without whose guidance and support, this journey would never have been possible. I would also like to thank my co-authors Ümit C. Büyükşahin (UPC), Roger P. Centelles (Guifi), Emmanouil Dimogerontakis (UPC), Jacek Dominiak (CA Labs), Smrati Gupta (CA Labs), Mennan Selimi (UPC), Leila Sharifi (IST), and Xavier Vilaça (INESC-ID), who were a great pleasure to work with. I am also thankful to my colleagues at Distributed Systems Groups, DSG at UPC and GSD at INESC-ID, who provided a great work environment, and the backdrop from many an insightful discussions. During the course of my research, I got a chance to interact with many great minds, and I appreciate their feedback and insights, notably Jörn Altmann (Seoul), Roger Baig (Guifi), Gianfranco Giulioni (Chieti-Pescara), Leonardo Maccari (Trento), Victor Muntes (CA Labs), Leandro Navarro (UPC), Navaneeth Rameshan (UPC), Omer F. Rana (Cardiff), Davide Veiga (UPC), and Luis Veiga (INESC-ID, IST). I would like to especially thank Ricardo Pereira (INESC-ID, IST) who reviewed an earlier draft of this manuscript and provided valuable suggestions. On this life long journey of learning, I am lucky to be guided and mentored by many great teachers on its many twists and turns, and I owe to them my contributions and achievements. Lastly, I am thankful to my family for their tremendous support. *** This work was funded by European Commission (EACEA) through the Erasmus Mundus doctoral fellowship, via Erasmus Mundus Joint Doctorate in Distributed Computing (EMJDDC) programme. This work was also supported by European Community Framework Programme 7 FIRE Initiative projects Community Networks Testbed for the Future Internet (CONFINE), FP7-288535, and CLOMMUNITY, FP7-317879. Support was also provided by the Universitat Politècnica de Catalunya BarcelonaTECH and the Spanish Government under contract TIN2013-47245-C2-1-R. iii Abstract Internet and communication technologies have lowered the costs for communities to collaborate, leading to new services like user-generated content and social computing, and through collaboration, collectively built infrastructures like community networks have also emerged. While community networks focus solely on sharing of network bandwidth, community network clouds extend this sharing to provide for applications of local interest deployed within community networks through collaborative efforts to provision cloud infrastructures. Community network clouds complement the traditional large-scale public cloud providers similar to the model of decentralised edge clouds by bringing both content and computation closer to the users at the edges of the network. Community network clouds are based on the principle of reciprocal sharing and most of their users are moved by altruistic principles. However, as any other human organisation, these networks are not immune to overuse, free-riding, or under-provisioning, specially in scenarios where users may have motivations to compete for scarce resources. We focus in this thesis on the incentives based resource regulations mechanisms to derive practical ways of implementing arbitration when such contention for limited resources occurs. We first design these regulation mechanisms for the local level where stronger social relationships between the community members imply trust, and ensure adherence to the system policies. We next extend the mechanisms for larger communities of untrusted users, where rational users may be motivated to deviate for their personal gains, and develop a distributed framework for guaranteeing trust in the resource regulation. Such mechanisms assist in encouraging contribution by the community members, and will help towards adoption, sustainability, and growth of the community cloud model. Keywords community cloud; community networks; cloud computing; economic mechanisms v Resumen El Internet y las tecnologías de la comunicación han bajado los costos de colaborar en comunidad, dando lugar a nuevos servicios, como los contenidos generados por usuarios y la informática social y, por medio de la colaboración, han surgido infraestructuras construídas colectivamente, como las redes comunitarias. Mientras las redes comunitarias se centran exclusivamente en el intercambio de ancho de banda de la red, las nubes comunitarias extienden este intercambio para proporcionar aplicaciones de interés local, desplegadas en las redes comunitarias a través de actividades de colaboración para proveer infraestructuras en la nube. Las nubes comunitarias complementan a los proveedores tradicionales de la nube a gran escala, en un modo similar al modelo de las nubes descentralizadas, trayendo tanto el contenido como la computación más cerca hacia los usuarios en los extremos de la red. Las nubes comunitarias se basan en el principio de compartir recíprocamente y la mayoría de sus usuarios son movidos por principios altruistas. Sin embargo, como cualquier otra organización humana, estas redes no son inmunes al uso excesivo, al parasitismo, o al bajo-aprovisionamiento, especialmente en escenarios donde los usuarios pueden estar motivados a competir por recursos escasos. Nos centramos en esta tesis en los mecanismos de regulación de recursos basados en incentivos para derivar formas de aplicación práctica del arbitraje cuando se produce tal contención por recursos limitados. Primero diseñamos estos mecanismos de regulación a nivel local, donde las fuertes relaciones sociales entre los miembros de la comunidad generan confianza y aseguran la adhesión a las políticas del sistema. A continuación, extendemos los mecanismos para comunidades más grandes de usuarios no confiables, donde usuarios racionales pueden ser motivados a desviarse por sus ganancias personales, y desarrollamos un marco distribuido para garantizar confianza en la regulación de recursos. Tales mecanismos ayudan a fomentar la contribución de los miembros de la comunidad, y ayudan a la adopción, la sostenibilidad y el crecimiento del modelo de nube comunitaria. Palabras Clave nube comunitaria; redes comunitarias; computación en la nube; mecanismos económicos vii Abstracts, Demos & Posters [Bai+15] Roger Baig, Felix Freitag, Amin M Khan, Agusti Moll, Leandro Navarro, Roger Pueyo Centelles, and Vladimir Vlassov. “Community Clouds at the Edge deployed in Guifi.net”. In: 4th International Conference on Cloud Networking (CloudNet 2015). Niagara Falls, Canada: IEEE, Oct. 2015. [Sel+14] Mennan Selimi, Jorge L Florit, Davide Vega, Roc Meseguer, Ester Lopez, Amin M Khan, Axel Neumann, Felix Freitag, Leandro Navarro, Roger Baig, Pau Escrich, Agusti Moll, Roger Pueyo Centelles, Ivan Vilata, Marc Aymerich, and Santiago Lamora. “Cloud-Based Extension for Community-Lab”. In: 22nd International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS 2014). (CORE Rank A). Paris, France: IEEE, Sept. 2014, pp. 502–505. [Jim+13] Javi Jiménez, Roger Baig, Pau Escrich, Amin M Khan, Felix Freitag, Leandro Navarro, Ermanno Pietrosemoli, Marco Zennaro, Amir H Payberah, and Vladimir Vlassov. “Supporting cloud deployment in the Guifi.net community network”. In: 5th Global Information Infrastructure and Networking Symposium (GIIS 2013). (CORE Rank C). Trento, Italy: IEEE, Oct. 2013. Technical Reports [KBF13] Amin M Khan, Umit Cavus Buyuksahin, and Felix Freitag. Distributed Architecture for Cloud System tailored for Wireless Community Networks. Tech. rep. UPC-DAC-RR-XCSD-2013-4. Barcelona, Spain: Universitat Politècnica de Catalunya, May 2013. xiv Contents Acknowledgments ii Abstract iv List of Publications xiv List of Figures xix List of Tables xxi List of Algorithms xxiii 1 Introduction 1 1.1 ProblemStatement ............................... 2 1.2 ResearchMethodology ............................. 2 1.3 Results...................................... 3 1.4 Summary of Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5 OutlineoftheThesis .............................. 4 2 State-of-the-Art 5 2.1 Definitions.................................... 5 2.2 Incentives .................................... 7 2.3 Economic Based Resource Allocation . . . . . . . . . . . . . . . . . . . . . 8 2.3.1 Community Networks . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.2 CloudSystems............................. 10 2.3.3 CloudFederations........................... 13 2.4 Trust in Resource Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.1 Allocation with Rational Users . . . . . . . . . . . . . . . . . . . . 16 xv 3 Middleware for Resource Regulation in Community Clouds 19 3.1 Community Network Clouds . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.1.1 Commercial Community Clouds . . . . . . . . . . . . . . . . . . . 20 3.1.2 Citizen Community Clouds . . . . . . . . . . . . . . . . . . . . . . 21 3.1.3 Community Clouds in Community Networks . . . . . . . . . . . . 21 3.2 Architecture for Community Network Cloud . . . . . . . . . . . . . . . . . 22 3.3 Incentives Based Resource Regulation . . . . . . . . . . . . . . . . . . . . . 24 3.4 Summary .................................... 26 4 Managing Incentives with Trusted Users 29 4.1 Motivations ................................... 30 4.2 SystemModel.................................. 31 4.2.1 Nodes in Community Network . . . . . . . . . . . . . . . . . . . . 31 4.2.2 Community Cloud Scenarios . . . . . . . . . . . . . . . . . . . . . 31 4.2.3 Resource Provisioning and Coordination . . . . . . . . . . . . . . 33 4.3 Effort-Based Incentive Mechanism . . . . . . . . . . . . . . . . . . . . . . . 33 4.3.1 Formulations.............................. 33 4.3.2 Algorithm for Requests Processing . . . . . . . . . . . . . . . . . . 35 4.4 PerformanceEvaluation............................. 36 4.4.1 Evaluation with Simulation Experiments . . . . . . . . . . . . . . . 37 4.4.2 Evaluation with Prototype . . . . . . . . . . . . . . . . . . . . . . . 40 4.4.3 Discussion............................... 46 4.5 Summary .................................... 47 5 Managing Incentives with Untrusted Users 51 5.1 Motivations ................................... 54 5.1.1 SystemModel ............................. 54 5.1.2 Pricing Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.1.3 Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.1.4 Evaluation ............................... 58 5.1.5 Discussion............................... 62 5.2 SystemModel.................................. 63 5.2.1 Resource Allocation Auctions . . . . . . . . . . . . . . . . . . . . . 63 5.2.2 Distributed Auctioneer Simulation . . . . . . . . . . . . . . . . . . 65 5.2.3 Game Theoretical Model . . . . . . . . . . . . . . . . . . . . . . . 66 xvi 5.3 The Distributed Auctioneer . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.3.1 GeneralFramework.......................... 67 5.3.2 Parallel Allocator Framework . . . . . . . . . . . . . . . . . . . . . 71 5.3.3 Resource Allocation Instances . . . . . . . . . . . . . . . . . . . . 76 5.4 PerformanceEvaluation............................. 78 5.4.1 Hardware/Software Setup . . . . . . . . . . . . . . . . . . . . . . . 78 5.4.2 Double Auction Deployment . . . . . . . . . . . . . . . . . . . . . 79 5.4.3 Standard Auction Deployment . . . . . . . . . . . . . . . . . . . . 80 5.5 Summary .................................... 81 6 Conclusion 83 6.1 Ramifications and Collaborations . . . . . . . . . . . . . . . . . . . . . . . 84 6.1.1 CommunityClouds.......................... 84 6.1.2 Social and Economic Mechanisms . . . . . . . . . . . . . . . . . . 84 6.1.3 Scalability of Community Cloud Architectures . . . . . . . . . . . 85 6.1.4 Supporting Service Selection . . . . . . . . . . . . . . . . . . . . . 85 6.1.5 Cloud Services in Guifi.net . . . . . . . . . . . . . . . . . . . . . . 85 6.2 FutureWork................................... 86 Bibliography 89 xvii List of Figures 1.1 Overview of the proposed framework . . . . . . . . . . . . . . . . . . . . . 4 3.1 Framework for community cloud management system . . . . . . . . . . . . 23 4.1 Nodes in federated community cloud . . . . . . . . . . . . . . . . . . . . . 32 4.2 Details of the VM request operation by ON . . . . . . . . . . . . . . . . . . 36 4.3 Breakdown of outcome of requests . . . . . . . . . . . . . . . . . . . . . . . 40 4.4 Resourceutilisation............................... 41 4.5 Components of cloud coordinator . . . . . . . . . . . . . . . . . . . . . . . 42 4.6 Overall resource utilisation of the four ONs . . . . . . . . . . . . . . . . . . 44 4.7 Distribution of credit among the four ONs . . . . . . . . . . . . . . . . . . . 45 4.8 Ratio of fulfilled and rejected requests . . . . . . . . . . . . . . . . . . . . . 46 4.9 Resources assigned from different SN zones . . . . . . . . . . . . . . . . . . 48 5.1 Users connected to the service provider’s gateway . . . . . . . . . . . . . . . 52 5.2 Value function 𝑣𝑖(ℎ,𝑡)for user 𝑖....................... 59 5.3 Percentage difference in social welfare as more users lie . . . . . . . . . . . . 60 5.4 Percentage difference in utility for low priority class ℎ0............ 61 5.5 Percentage difference in utility for high priority class ℎ1........... 62 5.6 Maximum gain in utility for a user from low priority class ℎ0........ 63 5.7 Maximum gain in utility for a user from high priority class ℎ1........ 64 5.8 Framework: Bid Agreement (BA) and Allocator (A) . . . . . . . . . . . . . 68 5.9 Decomposition of the Allocator into Tasks . . . . . . . . . . . . . . . . . . . 72 5.10 ParallelAllocator ................................ 73 5.11 Running time for double auction . . . . . . . . . . . . . . . . . . . . . . . . 79 5.12 Running time for standard auction . . . . . . . . . . . . . . . . . . . . . . . 81 xix List of Tables 4.1 Configuration for each node in a zone with shared and total instances . . . . 38 4.2 Success ratio for nodes with different configurations . . . . . . . . . . . . . 39 4.3 Two cases with different resource distribution between zones . . . . . . . . 47 xxi List of Algorithms 4.1 Handling requests from ONs . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.1 Scheduling algorithm for 𝜙, allocating  𝑡slots to 𝑁users ........... 58 5.2 Standard auction allocator . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 xxiii Efficiency Efficiency refers to an increased aggregate valuation for all the users. An optimal solution maximises the social welfare in the system. Ex Post Budget Balance Budget balance is the property that after the resources have been allocated the total value paid by users covers the total payments made to the providers. Ex Post Nash Equilibrium Ex post Nash equilibrium means that the system reaches a Nash equilibrium no matter what a scheduling adversary does. Fairness A fair resource allocation assigns each user a share of system resources which is close to its share of total system funding. In other words, fairness refers to minimising envy between the users resulting from allocation of resources. Free Riding Free riding refers to the situation where users consume public goods or resources without any or minimal contributions from their side, which results in underprovision of these goods or resources. Incentive Compatibility Incentive compatibility means that there is no incentive for any player to lie about her private information. Individual Rationality Individual-rationality means that every player truthfully participating in the allocation is expected to gain no less utility than by not participating. Nash Equilibrium A joint strategy involving all players in a game is a Nash equilibrium if no player can achieve better utility by unilaterally deviating, provided all the other players continue to play their role as suggested by the joint strategy. Social Welfare Social welfare is an aggregate over the utility of all the players in an allocation. Solution Preference Solution preference means that no player has the incentive to fail the algorithm. Even though players have different preference over the outcomes of an algorithm, no player can gain if the algorithm fails and there is no solution. 6 Strategy Proofness Strategy proofness means that the dominant strategy for all the players is to report their true valuations to the allocator, and therefore no player has any incentive to cheat. Utility Utility function in game theory measures preference over the allocation of resources, and represents satisfaction experienced by the players. Vickrey-Clarke-Groves (VCG) Mechanism VCG is a generic truthful mechanism for achieving a socially-optimal solution [NR99]. It is a generalisation of a Vickrey–Clarke–Groves auction, where each individual is charged a “social cost” equivalent to the harm they cause to other bidders. Virtual Machines Virtual machine (VM) is an emulation of a computer system, where hardware resources, like computing, memory, and storage, are packaged as virtual instances. 2.2 Incentives Many volunteer and distributed platforms appeal to users’ altruistic instincts. Projects like SETI@Home [And+02], BOINC [And04], and Folding@home [Beb+09] propose to solve challenging scientific problems, which encourage users to contribute the idle resources of their machines. Other projects like PlanetLab [Chu+03] and various Grid systems [FK03] require some mutually-agreed upon level of contribution as a pre-condition for participating in the system. Other earlier popular peer-to-peer (P2P) file sharing programs like Kazaa, Gnnutella, Napsters, and eMule among others [RD10], allowed users to upload and download files for free, and often suffered from the issues like free riding, under-provisioning, etc. This has led to designing incentive mechanisms in P2P systems to ensure that users actively contribute. For example, BitTorrent, using reciprocity principle, only allows users to download content if they also upload part of it to other BitTorrent users. Similar incentive mechanisms have been extensively studied for other P2P systems [BCF07; She+10; ZAM10]. Community networks are also based on the principle of reciprocal sharing, and offer various tangible and intangible benefits to their users. Bina and Giaglis [BG06] have explored various psychological and social motivations of the users of AWMN community network. Reciprocal resource sharing is, in fact, part of the membership rules or peering agreements [Pic05] 7 of many community networks. The Wireless Commons License (WCL) [Wir10] of many community networks states that the network participants that extend the network, e.g. contribute new nodes, will extend the network in the same WCL terms and conditions, allowing traffic of other members to transit on their own network segments. Therefore, resource sharing in community networks from the equipment perspective refers in practice to the sharing of the nodes’ bandwidth. This sharing, done in a reciprocal manner, enables the traffic from other nodes to be routed over the nodes of different node owners, and allows community networks to successfully operate as IP networks. Most of these incentive mechanisms are based on the idea of reciprocating individual’s contribution, anybody who contributes more value to the system is allowed to reap more benefits from it. However, this does not take into account that in many cases not all users are as rich in resources as others. Participatory Economics (Parecon) model envisions rewarding the users based on their effort, which is defined as contribution as a fraction of their capacity, instead of rewarding purely on the basis of their absolute contribution [Alb04]. Effort-based incentives [Rah+10; Veg+13; Veg15] have been proposed based on Parecon principle to achieve fairness and improve social welfare, while better addressing the resource heterogeneity in the system. For instance, Rahman et al. [Rah+10] apply effort-based incentives for file sharing in BitTorrent where some users with slow Internet connections cannot upload as much content as others. When deciding how much a user can download, they propose factoring in user’s connection speed in addition to the data the user has uploaded. Their results show that the effort-based mechanism remains incentive-compatible and improves efficiency and fairness as compared to purely contribution-based approach. We also turn to effort-based incentives in Chapter 5 when devising mechanisms for resource sharing between the users of community network clouds. 2.3 Economic Based Resource Allocation Most distributed systems have limited resources that need to be shared by many nodes. For instance, in a network there is limited bandwidth that needs to be allocated to multiple nodes. In cloud applications, virtual machines (VMs) need to be allocated to different cloud users. Resource allocation is, therefore, a key problem in distributed systems, and there is a vast literature on resource allocation of shared resources, whether they be network bandwidth, or other general computing resources. Distributed resource allocation is particularly challenging when nodes operate under dif- 8 ferent spheres of control and may not be willing to cooperate. Namely, a resource allocation strategy that assumes that all nodes execute a given algorithm may break if nodes may extract benefits by deviating from the expected behaviour. Many examples of this problem can be found in the literature. The works of [Lee+07] and [Xia+13] illustrate how a network user may attempt to monopolise the bandwidth utilisation if it has the opportunity. There is evidence that programmers can instrument their code to get an unfair advantage of several Unix schedulers [GC05]. In shared infrastructures, like Grid systems, participating users try to maximise their own usage to the detriment of the others [Lai+04]. Dynamic wireless spectrum allocation suffers from unfair manipulation [Zho+08]. Social cloud computing [Cat+14] and cooperative computing systems like BitTorrent [Liu+10] suffer when users act selfishly in consuming resources. An approach that has emerged as a viable alternative for the problem above is to use economic models to address resource allocation, in particular by resorting to auction systems [Hur73; RS81]. As a result, an extensive literature exists on the use of several types of auctions to perform resource allocation in distributed systems [NR99; Niy13; Wal+92]. In particular, the advent of the cloud computing model, where many clients may compete for the resources managed by one or more providers, has spurred the usage of different auction mechanisms for the cloud [WRM12]. In these approaches, users are modelled as non-cooperative rational players who are willing to pay for using resources or get paid for providing those resources. Specifically, users declare to an auctioneer the preference for different allocations of resources, and the auctioneer executes some auction mechanism to derive an allocation between users and resources that maximises social welfare (preferences of users for the allocation), and the payments to be performed or received by each user. The aim is to obtain an allocation with a social welfare as close as possible to the optimal while ensuring truthfulness from the users, such that they do not have incentives to lie about their bids. In addition to maximal social welfare and truthfulness, other guarantees may be provided, including computational efficiency and budget balance (the payments made by the users outweigh the payments received). In the following, we look at the state-of-the-art in economic-based resource regulation, first for community networks (§ 2.3.1), and then for cloud systems (§ 2.3.2) both in the context of virtual machines and network bandwidth. Next, we study managing resource sharing between federations of cloud providers (§ 2.3.3) . 9 2.3.1 Community Networks Various pricing schemes, game theoretic mechanisms and auction-based approaches for arbitrating network resources have been proposed and used in practice. Maillé and Tuffin [MT14] provide a comprehensive survey of the historical approaches and the current state-of-the-art from the viewpoint of telecommunication services. Community networks comprise of wireless mesh and multi-hop networks, and require cooperation among its users for proper functioning. Game theory, both non-cooperative and cooperative, has been applied in literature for studying the incentives of its user and devising network allocation mechanisms. Xiao et al. [Xia+13] propose a general framework for studying the user cooperation in a network, and formalise the relationship between incentive, fairness and efficiency for cooperative networks. Zhou et al. [ZLL14b] develop a Vickrey- Clarke-Groves (VCG) based mechanism for non-cooperative users. Since VCG mechanism cannot be directly applied because of the high computational complexity, they modify it by using relaxation-based greedy algorithm in such a way that it still guarantees strategy-proofness and efficiency. Lee et al. [Lee+07] focus on the problem of backbone construction with selfish users in a community network, who want others to relay their packets but want to avoid relaying packets for others. They propose an incentive-compatible protocol based on Volunteer’s Timing Dilemma from non-cooperative game theory. Their findings show that using their protocol the backbone forms quickly, with characteristics comparable to protocols designed only for altruistic users. Community networks like Guifi.net, in practice, also put emphasis on social sharing agreements [Pic05; Wir10], and when conflicts occur enforce these agreements through social mechanisms [Bai+15b]. For our context of community network clouds, we accept the guarantees implied by the community networks, and assume that the network is owned by the whole community so the traffic within the network between any two nodes is ensured to transit over intermediary nodes. Therefore, when we address the issue of bandwidth reservation in Chapter 5, we focus solely on the gateways present in the community network that provide access to the Internet. 2.3.2 Cloud Systems With respect to the general computing resources, there has been a lot of existing work in the context of Grid systems [FK03; BAV05; CW12] and shared infrastructures like Planet- Lab [Leo13]. For instance, one of the system implemented for PlanetLab is Tycoon [Lai+04], 10 which is a distributed marked-based resource allocation system, implementing proportional fairness using decentralised isolated auctions. Tycoon allows users to differentiate their jobs based on their importance by specifying different bid amounts. Auctioneers manage only local resources, and users submit separate bids to these auctioneers. The bids remain valid until a user’s credit gets low, so the mechanism reduces manual bidding overhead by the users. Resources are assigned in proportion to the bid amounts using a best-effort approach. This allows Tycoon to achieve efficient usage of resources, while maintaining little allocation overhead. Economic-based resource allocation mechanisms have been extensively explored for cloud computing [NFL12; Pop+12; Shi+14; WRM12; Zha+13; Zha+15b; Zhe+14; Zhe+15]. Amazon, one of the leading providers of public cloud services, was among the first to offer cloud resources using market-driven prices [Agm+13]. Besides investigating how a provider can use economic-based mechanisms to maximise the utilisation of its resources and increase its revenue [WRM12], the recent research has also looked into devising the best strategies for the users to bid for the cloud resources in such a market [Zhe+15]. Many works, for instance [ZLW14; Zha+15b], employ the celebrated Vickrey-Clarke-Groves (VCG) mechanism [NR99] for achieving truthfulness and a trade-off between maximal social welfare and computational efficiency. The challenge in applying VCG mechanisms in clouds is that in most of these problems, finding an optimal allocation is NP-hard, and so traditional VCG mechanism cannot be applied. One key line of work has been to use randomised algorithms [ZLW14; Zha+15b], or linear programming decomposition techniques [NL13; Zha+15a], to achieve strategy-proofness with a computationally feasible solution, albeit achieving less than optimal social welfare. The overall aim is to look for solutions with lower computational complexity, and higher social welfare, while ensuring strategy-proofness. Virtual Machines Allocation Cloud computing employs virtualization to package computing resources like CPU time, memory, and storage as virtual machines (VMs). Therefore, resource allocation in cloud, for the most part, deals with composing VMs from the hardware resources, and allocating them to the users in the most efficient manner. Cloud providers offer a variety of VM instances of different types, where type refers to the composition of different resources packaged in the VM instance. For example, a VM consisting of 2 virtual CPU units, 8 GB RAM and 100 GB storage is one type of VM. Zhang et al. [Zha+15b] extend this to allow users to request customised dynamically assembled VM types, bundling VMs from different geo-distributed 11 data centres of the provider. They use smoothed analysis and randomised reduction to design a randomised, highly efficient auction mechanism. Their mechanism is general and expressive enough to encompass various cloud scenarios, and achieves truthfulness (in expectation), polynomial running time (in expectation), and (1−𝜖)-optimal social welfare (in expectation) for resource allocation in a geo-distributed cloud, where 𝜖∈(0,1). Zhang et al. [ZLW14] approach combinatorial auctions of heterogeneous VMs by modelling social welfare maximization as a mixed linear integer program. They design an efficient 𝛼-approximation algorithm, with 𝛼∼2.72in typical scenarios. They use this algorithm as a building block for designing a randomised combinatorial auction that is computationally efficient, truthful in expectation, and guarantees the same social welfare approximation factor 𝛼. They utilise a pair of tailored primal and dual linear programs (LPs) to decompose fractional solution of social welfare maximization problem into a convex combination of integral solutions. Bandwidth Reservation The focus remains mostly on efficiently allocating VMs in the cloud, even though the bandwidth, both upstream and downstream, to connect to VMs in the cloud is metered. Bandwidth allocation and reservation gains significance, in particular when the applications are network-intensive or have real-time constraints. Some prime examples are video-streaming, video-on-demand and cloud-based gaming. Recent work has explored various economic based bandwidth allocation schemes for public clouds [Gui+14; Guo+13; NFL12; Pop+12; SL14; Zhe+14]. The emphasis in the cloud has been on having bandwidth reserved with service level guarantees for the cloud applications. Gui et al. [Gui+14] propose VCG-auction based mechanisms for reserving bandwidth at the multiple geo-distributed data centres of the cloud provider. The users submit bandwidth reservation requests separately for each of the data centres. In case the users can accept partially fulfilled requests, i.e. bandwidth reserved up to the maximum requested, a solution can be calculated using linear programming in polynomial time, which achieves both optimal social welfare and strategy-proofness. However, if partial reservations are not permissible, the allocation problem is NP-hard, so the above polynomial time algorithm cannot be used to calculate optimal allocation. The authors propose a heuristics-based greedy algorithm that guarantees strategy-proofness, though provides less than optimal social welfare. Zheng et al. [Zhe+14] focus on a multi-cloud scenario where users need to reserve bandwidth from different cloud providers, because they have strict requirements on the amount of bandwidth 12 for guaranteeing their quality of services. They model this open market of cloud providers as a double-sided auction, where providers also submit bids to the auctioneer besides the users, and propose strategy-proof mechanisms based on McAfee double auction [MS83]. Shen and Li [SL14] propose a bandwidth pricing model, a network bandwidth sharing policy and flow arrangement policies, and use non-cooperative game theory analysis. Their policies encourage cooperation among the tenants of the cloud infrastructure, who are incentivised to prefer uncongested links and constrain congestion. Guo et al. [Guo+13] focus on the bandwidth available within the data centre infrastructure, on the links connecting the multiple VMs owned by the tenants. They apply cooperative game-theoretic framework to design a distributed algorithm to achieve efficient and fair bandwidth allocation corresponding to the Nash bargaining solution. 2.3.3 Cloud Federations Aside from public clouds, another emerging model in cloud computing involves cloud providers trading of VM resources among themselves, referred to as federating their individual clouds. There are various terms for this scenario in literature such as federated clouds, Intercloud, community clouds, cloud brokerage, etc. In this case, cloud providers agree to provision VMs for each other, for instance one provider can solicit additional resources from others to satisfy peaks in demands. Such a federated or community cloud presents the challenge of a free market, where participants have the incentive only to accept those resource exchanges that are profitable for them. Zhao at al. [ZLL14a] develop a distributed marketoriented model for the resource negotiation and trading problem in such a community cloud. They use this model to propose a multi-agent based approach that provides an efficient and fair resource allocation for a group of autonomous cloud providers. They also consider resource trading under budget constraints, and based on a directed hypergraph model, present effective heuristic-based distributed protocols to achieve resource allocation within budget limits. Social cloud computing [Cat+14; Pun+13] similarly focuses on trading resources between cloud providers, who in this case are individual users of online social networks, like Facebook, Twitter, etc. Punceva et al. [Pun+13] propose a decentralised resource sharing model, and use virtual currency to incentivise cooperation without requiring a central reputation management system. They differentiate between intra-community and inter-community sharing, where a community consists of a group of “friends” on social networks, because the trust inherent within a tightly knit community aids in designing a more flexible virtual currency rep- 13 resentation. Caton et al. [Cat+14] focus more on improving how the providers are matched to the users in a social cloud. They propose heuristics based matching algorithms for bidirectional preference-based socially-aware resource allocation, with the aim to optimise social welfare and allocation fairness. Li et al. [Li+13] study how individual cloud providers can maximise their profits through better resource trading and scheduling. They apply a double auction-based mechanism, which is strategy proof, individual rational, and ex-post budget balanced. Based on this auction mechanism, they propose an efficient and dynamic resource trading and scheduling algorithm, which carefully computes the true valuations of VMs in the auction, and aims to optimally schedule stochastic job requests onto the VMs. Palmieri et al. [Pal+13] focus on scheduling resources within federated clouds, and present a fully distributed agent-based game-theoretic scheme for scheduling computing resources between providers in federated clouds. Their scheme is based on independent, competing, and self-interested task execution agents, with the goal to achieve an optimum social welfare criteria towards a Nash equilibrium solution, using a slotted time model to provide advance reservation of resources in a fully distributed manner. For the scenario of community network clouds, we consider members of community networks as cloud providers, and present efficient incentives based mechanisms for allocating cloud resources in Chapter 4. 2.4 Trust in Resource Allocation The issue of trust in auctions is well-known and well-studied in economic theory, for various type of auctions [San00]. In particular Vickrey auction, which forms basis of the celebrated VCG mechanism [NR99], is very susceptible to a lying auctioneer [San00]. VCG mechanism is often used in distributed systems and cloud computing to ensure strategy-proofness in resource allocation, but it suffers from significant issues because of the trust required in the auctioneer [San00]. There are numerous distributed auction schemes proposed in literature [Guo+13; Zho+08; Lai+04], but the fact that they are decentralised in itself does not imply trust. Without careful design, one or more agents participating in the distributed auction can affect the results to their advantage. The issue of an auctioneer cheating in second-price sealed-bid auctions, similar to VCG auctions, has been so severe that fraud was commonplace in the stamps auctions of late 19th and 20th century [Luc00b], which provide the first recorded example of using Vickrey auc- 14 tions in practice. More recently, such second-price auctions have been used by eBay [Luc00a] to sell goods, and by Yahoo, Google, and other Internet search companies to sell keywordsbased online advertising [EOS07]. It has been suggested that such auctions are viable for these Internet companies, in the absence of any trust, because these companies have low commissions, and conduct so many trades that it is not in their interest to cheat [Luc00b]. But the issue of mistrust in the auctioneer has been prevalent, so much so that when Amazon introduced its “spot instances” service using market-based pricing, there were doubts that Amazon was not using supply and demand to set the prices, but instead employed a mathematical regression function to set the rates [Agm+13]. This lack of trust can create various problems for resource allocation in decentralised systems, and we go through a few examples here. InterCloud allows for multiple cloud providers to federate their resources to form a cloud market [GB14]. The current approaches mostly rely on bilateral agreements, and price negotiation. However, as the number of providers increases this arrangement will no longer be tenable. The providers cannot put absolute trust in anyone among them or in a third party to execute the auction fairly. Social clouds [Cat+14] allow exchanging resources between users of online social networks. Here, as well, the users have to trust the allocation and resource matching algorithm, which even if it runs distributed on multiple machines, cannot be trusted, since some of the users can tweak the allocator to their advantage. Secondary wireless spectrum markets [Zho+08; LLZ15] also apply auctions to ensure strategy-proofness, but again fail if a trusted auctioneer is not available. BitTorrent, like other similar popular P2P file sharing systems, regulates access to available resources depending on the users’ contribution. However, users can easily use their BitTorrent clients to falsely report their contribution to be high. To counter this, BitTorrent private communities have a central mediator that dictates rules for uploading and downloading content, and tracks contribution and consumption by the users [Liu+10]. However, the administrators and privileged users can affect the central mediator to get unfair advantage. Resource allocation in shared infrastructures like Grid systems also require incentive-compatible solutions [Lai+04; KA06; Buy+02], and many of the proposed approaches in the literature apply only when a trusted entity is available for executing the auction mechanisms. A cheating auctioneer can pose a number of problems. The major among them, that we focus on, is that the winning bids may not be selected fairly, and the payment each winning bidder has to make is not calculated properly. In open-bid auctions, like English and Dutch auctions [Kri09], the above two issues are not a major problem as the bidding process is open to all the participants. In sealed-bid first price auction, each winning bidder pays the amount she quoted, so even though the auctioneer can cheat on selecting the winning bidders, at least 15 cloud applications tailored to local needs, built on infrastructure provided by the community members. Community network clouds build on the success of community networks and aim to provide services and applications of local interest for the communities by applying the model of cloud computing. Community network clouds fit nicely with the recent shift in exploring alternative approaches to large-scale data centres based public cloud computing, which include Inter-Cloud and federated clouds (where multiple public cloud providers work together), hybrid clouds (where enterprises combine their own cloud infrastructure with the public clouds), and edge clouds using nano data centres [Sat+09] (where smaller clusters are deployed at the edges of the network to avoid latency and improve content-delivery). These initiatives provide an excellent backdrop to explore the role of the community network clouds in enhancing the value proposition of the community networks, since an infrastructure of nano data centres [Sat+09] to be deployed in a community network has to fit well with specific socio-economic and technical context of the community networks [KF14b]. For example, Guifi.net community network has deployed community edge cloud using their Debian-based Cloudy distribution [Bai+15a]. 3.2 Architecture for Community Network Cloud We foresee realising the community cloud by deploying a community cloud platform tailored to the specific infrastructure and context of community networks. A standard cloud system is usually a centralised platform designed to perform resource management. There are quite a few well known cloud platforms for managing public and private clouds, like Open- Stack [Ope16b] and OpenNebula [Ope16a] among others. For community network cloud, we focus on providing a framework that would allow users to share resources and access collaboratively-built services in a distributed manner. We propose a framework that can serve as the core of a community cloud system. Our community cloud framework is a distributed bottom-up resource sharing and collaborative services platform. This is achieved by adopting a layered architecture, as shown in Figure 3.1. 1. The Hardware layer provides the physical infrastructure needed to run the cloud services and applications. The hardware in the community network customarily consists of management nodes, client nodes, routers and the communication infrastructure, along with any computation, storage and other resources attached to the nodes. 22 CLI GUI API Front End Layer Core Layer Hardware Layer Middleware Layer Services Layer Storage Video Network Cloud Services Cloud Coordinator Resource Regulation Trusted Auctioneer Support Services VM Controller VM Monitor VM Scheduler Management Services VMs VMs VMs Figure 3.1: Framework for community cloud management system 2. The Core layer is responsible for managing the hardware as virtualised resources. It consists of components, such as a manager for the hosts and the network as well as a controller, scheduler, monitor, and data storage for virtual machines (VMs). 3. The Middleware layer amalgamates the resources from multiple local community clouds, providing an integrated and consistent view of the cloud system to the cloud services. This can comprise of a variety of support services: •Cloud coordinator and services broker components for assisting in combining resources from multiple cloud providers. 23 • Incentives-based resource regulation and allocation components are important as a driver for users’ participation for the sustainability and growth of the community cloud model. Our proposed incentive mechanisms in Chapter 4 can provide the building blocks for these components. •Trusted auctioneer module for auction-based resource allocation schemes. Resource allocation component needs to be trusted by the users, and in turn the users need to follow the prescribed polices for the system to function properly. We return to this issue in Chapter 5, and devise a virtual distributed trusted auctioneer to integrate into the community cloud framework. • Other support services may include, among many other: –Network coordination component to identify and manage different local clouds. –Service discovery component to keep track of the services provided by the various clouds. –Authentications and auditing components to support resource regulation. 4. The Services layer integrates useful services and applications providing utilities for the community network members to encourage their participation. Common services include storage, video streaming, video on demand, IP telephony, and network applications. 5. The Front-end layer provides the interface to interact with the infrastructure of the community cloud, including command line interfaces (CLI), graphical user interfaces (GUI), application programming interfaces (API), and any other tools for assisting in the development of cloud services and applications. 3.3 Incentives Based Resource Regulation Community network clouds, like other volunteer computing platforms, not only need to solve the technical challenges to be feasible but also address the social and economic context to engage their participants. The existing social relationships among the users provide the foundation for building community cloud services. Just as in social computing [Cat+14], relationships from online social networks provide the backdrop to provision cloud services, in the case of community network clouds, we believe the existing relationships among users of the community networks will make it possible for the model to be adopted. 24 The community networks provide the context and motivating scenarios for developing the proposed solutions that are discussed in Chapters 4 and 5; however, our proposals and findings are general enough for being applicable to other related fields. In order to realise clouds in community networks, we can take the existing software and technology, and adapt and extend it to better fit with the characteristics and constraints of the community networks. For example, an initiative in this regard has been the Cloudy distribution [Clo16], which is based on Linux operating system and incorporates useful free and open-source services of interest to the members of Guifi.net [Sel+15]. Of course, this does not imply that the community cloud model is restricted only to the members of the community networks. In fact, with Cloudy distribution there has been an effort to engage and involve others who are not part of a community network, and let them connect using network tunnelling protocols [Com16a]. The emphasis is on building cloud services and applications of local interest using the resources contributed by the members of the community networks, but also on engaging the wider Internet community at the same time, which can also generate interest in the community networks themselves. The resources available in the community network clouds can be divided into various categories. Network resources, like upstream and downstream bandwidth at different links of the community network, available bandwidth at the Internet gateways, or bandwidth at the links connecting to the popular content servers, are limited and already of value to the members of the community networks. Any community cloud solution has to work within the constraints of the available network capacity, and avoid negatively impacting the operations of the community network. Community clouds at the basic level provide Infrastructure-as-a-service (IaaS), where resources like computation, memory and storage, are packaged as virtual machine (VM) instances. In the collaborative model of community network clouds, users will be trading these resources as VMs among themselves. Other resources can include multimedia content, data storage, and other services, that are of interest to the users. The underlying principles for regulating resources, in general, apply equally to all these different kinds of resources. In practice, the proposed solutions are often customised to better fit a particular problem scenario. In our work, we have focused on two scenarios, which provide broad coverage of resource regulation problem in the community network clouds, and our prototypes addressing the two scenarios bring completeness to the solution for managing incentives in community network clouds. In Chapter 4, we focus on managing computing resources as VMs among the users. We propose efficient regulation mechanisms in the context of a small community of users, perhaps part of a single zone of the community network, which already has trust and strong social 25 relationships among its members. Our mechanisms regulate usage of the shared resource of available VMs, and succeed in incentivising contribution from the users. This is important in the community cloud model, since without active and continued contribution by the users, the model cannot be sustainable and scalable. In Chapter 5, we broaden our scope to the overall community network where users participating in the community cloud may be from different zones, and have no prior relationships or established trust among them. We focus specifically on the bandwidth available at the Internet gateways in the community network for two main reasons. Firstly, the available bandwidth to Internet is limited and already in high demand by the users of the community networks, and secondly, the community cloud services will also require access to Internet often with service-level guarantees for the bandwidth resource. We propose a framework for distributed auctioneer that arbitrates users’ access to the bandwidth available from the different getaway providers in a fair manner, even in the absence of trust among the users. Even though in Chapter 5 we develop and evaluate the distributed auctioneer for bandwidth allocation, the proposed framework can be generalised and also directly applied to allocating VMs at a cloud service provider. We can also extend this framework for the scenario of trading VMs from Chapter 4, which we leave for the future work. 3.4 Summary The idea of community network clouds follows on from volunteer computing paradigm. We looked at the general ideas of community clouds, both in commercial and non-commercial context, and focused on the realisation of citizen community clouds within the community networks. Community network clouds are as much a social construct as a technical one, and so require careful design of resource regulation and allocation mechanisms, in order to encourage participation by the members of the community networks. Notes The background studies presented in this chapter (§ 3.1) were accomplished in cooperation with my advisors Felix Freitag and Luís Rodrigues. We are also thankful for the cooperation of Roger Baig and Roger Pueyo Centelles from Guifi.net, and Leandro Navarro from Universitat Politècnica de Catalunya (UPC), who provided valuable insights into the operation of Guifi.net community network. The studies were published as a book chapter “Community Clouds” [KFN16], in Encyclopedia of Cloud Computing (2016), published by Wiley & IEEE 26 (ISBN: 978-1-118-82197-8), and as a short paper “Current Trends and Future Directions in Community Edge Clouds” [KFR15], in 4th International Conference on Cloud Networking (CloudNet 2015), Niagara Falls, Canada, October 2015. The work on the proposal for distributed architecture presented in this chapter (§ 3.2) was accomplished in cooperation with my advisor Felix Freitag. We also collaborated with Mennan Selimi and Emmanouil Dimogerontakis, other PhD students at UPC and IST, who did provide relevant contributions for the evaluation of cloud services in community networks. The proposal was published as a full paper “Towards Distributed Architecture for Collaborative Cloud Services in Community Networks” [KSF14], in 6th International Conference on Intelligent Networking and Collaborative Systems (INCoS 2014), Salerno, Italy, September 2014. It was later integrated into an extended journal article “Cloud services in the Guifi.net community network” [Sel+15], in Computer Networks 93.P2 (Dec. 2015). 27 4 Managing Incentives with Trusted Users Community networks are an ecosystem which is able to regulate and maintain itself, some of the community networks are there for even more than a decade. We argue that community cloud, a cloud infrastructure formed by community-owned computing and communication resources, has many technical and social challenges so that the main drivers of today’s contribution to community networks, volunteer and altruistic behaviour, are not enough to successfully overcome these barriers. Our hypothesis is that for community cloud to happen, the members’ technical and human contribution needed for such a cloud, needs to be steered by incentive mechanisms that pay back the users’ contribution with a better quality of experience for them. In this chapter, we study an incentive mechanism for clouds in community networks, keeping in view the key characteristics of community networks and the scenarios we foresee for communityclouds. Thisincentive mechanism isinspired byPareconeconomic model [Alb04; Rah+10; Veg+13], and is based on the idea of effort of each participant, which we defineas her contribution relative to her capacity. Our approach is to do the evaluation with simulation experiments and a prototype, which allows us to derive additional conclusions regarding its feasibility for implementation and deployment on a wider scale. 29 4.1 Motivations Community networks are based on the principle of reciprocal sharing, which is formalised by the agreements users accept when they join the network. The Wireless Commons License [Wir10] or Pico Peering Agreement [Pic05] is adopted by many community networks to regulate network sharing. The underlying principle is that users allow all the traffic to transit over the links that they own, and this is in return for the access they enjoy to the community network. The agreements are enforced, in most cases, through the social context. For example, members of Guifi.net have mailing lists and many regularly hold meetings where any complaints and issues are also addressed [Bai+15b]. In the worst situation, users may be excluded from using the services, if their behaviour continues to be damaging to the operation of the community network. Community networks in most cases tend to avoid having sophisticated mechanisms in place like auditing, billing, or other advanced pricing or auction-based mechanism, since they find it not in line with the sharing and open spirit of the community networks. Moreover, such mechanisms introduce additional overheads to the operation of the network, and in many cases may be difficult for users to understand and may discourage participation. When problems do occur, these are often addressed in ad-hoc manner and at the local level, for example, the network administrator may shut down some of the links. For persistent problems, the community often chooses to increase the capacity by buying more equipment and adding new links. For instance, in Guifi.net, some nodes have been successfully crowd-funded [Bai+15b] if such a node was needed by several people. Crowd-funding of a node happened when for a group of people an infrastructure improvement was necessary. For example, an isolated zone of Guifi.net established a super node to connect to other zones. We think that such a situation may not be sufficient for sustaining a community cloud ecosystem. This is because the contribution required from the users of community cloud, both in terms of the equipment, capital investment, and maintenance costs, and their effort, knowledge, and time, is orders of magnitude larger than what is needed to keep the community networks running. In the absence of any resource regulation mechanism, users will lack incentives to contribute resources. When all the computing and storage are made available at no cost to the community, it would be difficult to find many users willing to contribute solely for altruistic reasons, and even when the resources are made available, they will get consumed quickly by the free-riding users. Therefore, we propose that incentives based resource regulation has to play a key part in the sustainability of a community cloud ecosystem. 30 4.2 System Model 4.2.1 Nodes in Community Network We consider a community network, which is managed and owned by the community, and the nodes are managed independently by their owners. The nodes in a community network vary widely in their capacity, function and capability, so we generally divide the nodes into two categories: super nodes (SNs), and client or ordinary nodes (ONs). SNs have multiple wireless links and connect with other SNs to form the backbone of the community network, and are usually intended to be stable with permanent connectivity. Most SNs are installed in the community network participant’s premises. A few SNs, however are placed strategically in a third party location, e.g. telecommunication installations of municipalities, to improve the community network’s backbone. ONs, on the other hand, are only connected to the access point of a SN. Topological analysis of approximately 17,000 nodes of the Guifi.net community network indicates that around 7% are SNs while the others are ONs [Veg+12]. Principally the hardware for computation and storage is already available in community networks, consisting of some servers attached to the networking nodes. No cloud services, however, are yet deployed in community networks to use this hardware as a cloud, leaving the community network services significantly behind the current standard of the Internet. Our vision is that some community wireless routers will have cloud resources attached, building the infrastructure for a community cloud formed by several cloud resources attached to the nodes. We note that ONs could principally also contribute cloud resources. On the management side, community networks like Guifi.net, are organised into zones. A zone can be a village, a small city, a region, or a district of a larger city. The organisation of the group within a zone is of many types. Mostly the interests, available time and education of the people drive what happens in the zone. We note that while the allocation of IP addresses and layer 3 networking is agreed among all Guifi.net zones, as it is needed to make the IP network work, the detailed technical support is rather given within the local community of the zone. Therefore, we identify a zone to have the highest social strength within the community network. 4.2.2 Community Cloud Scenarios These observed characteristics of the community networks lead to two cloud scenarios in our model, local and federated community clouds. The SNs and ONs provide the networking 31 Table 4.1: Configuration for each node in a zone with shared and total instances Node Behaviour Shared Small capacity Medium capacity Large capacity Selfish 33% ON1 (1/3) ON2 (2/6) ON3 (3/9) Normal 66% ON4 (2/3) ON5 (4/6) ON6 (6/9) Altruistic 100% ON7 (3/3) ON8 (6/6) ON9 (9/9) ulation can host a number of VM instances that allows users’ applications to run in isolation. Nodes in the zone have two main attributes, one is capacity which is the number of available VM instances, and other is sharing behaviour which is how many instances are shared with other nodes. Table 4.1 shows the different configurations for each of the nine ONs in each zone. Nodes with low, medium and high capacity host 3, 6 and 9 VM instances respectively and they exhibit selfish, normal or altruistic behaviour sharing one-third, two-thirds or all of their VM instances. For example, node ON2 has medium capacity with 6 instances and exhibits selfish behaviour reserving 4 instances for itself and contributing only 2 to the system. When the experiment runs, the nodes are given initial credit in proportion to their capacity. Nodes make requests for resources proportional to their capacity asking for two-thirds of their capacity. For instance nodes with capacity of 3, 6 and 9 VM instances request 2, 4 and 6 instances respectively. Nodes request instances for fixed duration and after transaction is complete wait briefly before making further requests. We have implemented the simulator in Python. Ratio of Successful Requests Table 4.2 shows the success ratio for requests made by different nodes analysed both with the effort-based and contribution-based incentive mechanisms. We first notice that the success ratio values decrease as the capacity of the nodes increases. This is explained by the fact that nodes with greater capacity request more instances, and so have a higher chance of getting rejected either because there are not many resources available in the system or because the requesting nodes do not have sufficient credit. However, when comparing the success ratio for nodes as their capacity increases, we observe that there is not a great variation. For instance, for the normal sharing behaviour the values range from 66% to 97% for contribution-based incentives, but from 86% to 90% for effort-based incentives. This is explained by the fact that contribution-based approach does not take heterogeneity of nodes into account, and penalises 38 Table 4.2: Success ratio for nodes with different configurations (effort vs contribution) Node Behaviour Incentives Small capacity Medium capacity Large capacity Selfish effort-based 54% 53% 50% contribution-based 66% 59% 39% Normal effort-based 90% 91% 86% contribution-based 97% 77% 66% Altruistic effort-based 97% 94% 86% contribution-based 97% 85% 65% nodes with low capacity as they cannot contribute as much to the system as others. These results indicate that effort-based incentives ensure fairness in the system, since the nodes with the same sharing behaviour are treated equally irrespective of their capacity. Breakdown of Request Responses Figure 4.3 shows the overall breakdown of successful and rejected requests across all the zones, where there are many more successful requests than rejected ones. The success ratio is slightly better for effort-based incentives. Moreover, contribution-based mechanism has greater share of requests rejected because of lack of credit, while very few requests are rejected because of a lack of resources. This indicates that the effort-based incentive mechanism improves efficiency as more resources are utilised. In addition to this observation, the majority of the requests are fulfilled using resources from the local zone with very few requests forwarded to other zones. Resource Utilisation Figure 4.4 shows the proportion of resources utilised in the system along the execution of a 24 minutes experiment for effort and contribution based approaches. In the beginning, all nodes have enough credit and the resource utilisation is high. Then it drops to below 60% at around the 12th minute, and keeps fluctuating for a while. Afterwards, since most of the nodes have completed their transactions and consumed their credits, the utilisation decreases significantly. The effort-based approach though achieves a higher resource utilisation during that time. 39 Figure 4.3: Breakdown of outcome of requests with effort and contribution based mechanisms The results also point to a possible load imbalance issue since as the experiment progresses the large capacity nodes may accumulate the credit, lowering the percentage of used resources over time. Many nodes are left with insufficient credit to consume resources. One approach to overcome this issue is to supply all the nodes with a limited fixed amount of credit at regular intervals, which will keep the resource utilisation high. 4.4.2 Evaluation with Prototype Prototype Implementation We have implemented a prototype of the incentive-based regulation mechanism [KBF14] in Python using CouchDB [ALS10] database at the back-end, and deployed it in Community- Lab testbed [Com16b]. We chose Python because the current host operating system installed on ONs in the testbed is OpenWRT [Ope16c], which supports Python, but does not support many other languages such as Java. We selected CouchDB because among its advantages, it is lock-free, schema-less and provides a REST interface, and is also part of the other components of the SN’s cloud management software being developed. In the SNs, Debian operating system is installed. Figure 4.5 shows the implemented components of the cloud coordinator from the architecture in § 3.2. The components from the prototype are described below. 40 Figure 4.4: Resource utilisation ON Management ONs can register with SN to request and to contribute resources. Regulation Mechanism When pooling resources from multiple zones, the cloud coordinator applies a regulation mechanism that takes into account resource utilisation and contribution by different nodes to perform resource allocation. SN Interconnectivity The design of a community cloud manager follows a decentralised approach, so cloud coordinator relies on gossip-based discovery mechanisms to manage overlay network of the SNs in community cloud. The updated list of adjacent SNs is saved in SN-List database. SN Resource Sharing When requests from ONs cannot be met from resources in the local zone, SN can request resources from other SNs in the system. ONs use the remote procedure call (RPC) mechanism to connect to the SN. First of all, an ON assigns itself to a parent SN with a register message which includes metadata of that ON such as IP address, total capacity and number of VMs shared. In the current prototype, the IP address of SN is fixed and is manually provided when setting up ONs. However in future, service discovery tools like Serf [Ser16] can be used to get address of SN. This registration 41 Figure 4.5: Components of cloud coordinator information is stored in the ON-List database of the parent SN by creating an entry for the corresponding ON. After that, the ON is ready to send requests to its parent SN, which are processed using Algorithm 4.1 as shown in Figure 4.2. When an ON requests its parent SN for any VMs, it specifies the duration for how long it needs to use the VMs. This request is evaluated by performing incentive and decision mechanisms as explained in section 4.3. If a request cannot be met locally, the corresponding parent SN checks its SN-List database to find another zone with available resources. The interactions between SNs are also made through RPC mechanism. In the SN controller software, there is a separate process which regularly checks the database for any updates. If the duration of a consumer ON’s resource request has expired, it frees the VMs and makes them available for the provider ON, and updates the metadata entries of the corresponding ONs in the ON-List database. The current implementation keeps track of the number of VMs contributed and consumed by each ON. The system copes with ONs connecting and disconnecting from the SN at any time since ONs periodically send heartbeat messages to the SN. The design allows us to include values of metrics like CPU, memory, and bandwidth usage in the future for fine-grained decisions about resources assignment. Experiment Setup We deploy the prototype of the regulation component of the cloud coordinator from community cloud management system in the Community-Lab testbed, which is developed by the 42 CONFINE European project [Bra+13]. The cloud coordinator components are installed on nodes of the Community-Lab testbed, which consist of Jetway JBC372F36W devices, and are equipped with an Intel Atom N2600 CPU, 4GB of RAM and 120GB SSD. Depending on the experiment, one or two nodes operate as SNs, while each ON hosts between one and four VM instances. Note, however, that since OpenWRT has limited supported for either containersbased or full virtualization, in these experiments the nodes submit and process the requests but VMs are not actually created on the ONs. The objectives of the experiments are twofold: 1. Experiment 1: Assess the prototype operation regarding the incentive-based resource assignment algorithm in a local community cloud scenario. 2. Experiment 2: Study the coordination between SNs from different zones in the federated community cloud scenario with heterogeneous resource distribution. Resource Assignment in Local Community Cloud Scenario In order to study the performance of the prototype in a real deployment of a local community cloud, we install our software components in four ONs and one SN in Community-Lab testbed, which are connected to the Guifi.net community network. Each node behaves as an ON but with different configuration, in order to have a heterogeneous set of cloud resources. The four nodes include f101 sharing 1 out of total 2 VMs, f102 sharing 3 out of total 3 VMs, f103 sharing 1 out of total 3 VMs, and f104 sharing 1 out of total 1 VM. Each ON sends request for VM instances to the SN at regular intervals. VMs are requested for 20 seconds interval at a time. Each ON requests as many VMs as its total capacity, for example node f101 always requests 2 VMs. If the request is accepted by the SN, the ON obtains the VMs for the next 20 seconds. If the request is rejected, the ON waits for 5 seconds before making any further requests. The experiment is run with this setup for around 5 minutes. We analyse the different aspects of the system behaviour in the following. Resource Utilisation Figure 4.6 shows the level of resource utilisation in the system in terms of the number of reserved VMs versus the total number of VMs. It can be seen that resource utilisation varies widely and 100% utilisation, meaning all the VMs being occupied, occurs only for short intervals. This is because as nodes obtain VMs they spend their credit, and if they are not able to earn credit by contributing VMs, their credit gets below a certain threshold, and they can no 43 Figure 4.6: Overall resource utilisation of the four ONs longer request more VMs. At approximately 80th second, the utilisation gets very low. Nodes then need to earn credit by providing VMs to others before they can request VMs again. So even though VMs are available, they cannot be utilised due to the lack of credit in the system. Credit Distribution Figure 4.7 shows the credit distribution among the four ONs during the 5 minutes of the experiment. A node’s credit is affected by how many VMs it shares and how much credit it spends to obtain VMs. When a node shares most of its capacity, like ON f102 providing all its 3 VMs, it earns more credit and so maintains a high credit level during the experiment. On the other hand, when a node continuously consumes VMs like ON f101 and f104, it keeps on spending any credit that it earns, so its credit does not increase beyond a certain level. Of particular interest is the behaviour of ON f103, which earns credit in the start and gets a spike in credit level halfway through the experiment, but then quickly spends it as it requests VMs from others. Note that an ON’s credit can be negative or higher than 100% of the total credit because in the current implementation SN can allow requests from ONs with zero or or less than zero credit up to some extent. The ONs with zero or negative credit can, of course, continue to provide VMs and earn credit, they can only not request VMs if their credit is negative and below a certain threshold. This allows the nodes without any credit an opportunity to 44 Figure 4.7: Distribution of credit among the four ONs continue participating in the system and increase their credit by contributing resources. Success Ratio Figure 4.8 shows the ratio of the fulfilled requests for each node, which is affected by the level of credit of the node and the amount of resources available in the system. ON f104 has the most success since it requests only one VM at a time while ON f103 has the least success since it requests 3 VMs, which is half of the total shared VMs in the system. ON f101, on the other hand, gets its requests rejected because of the lack of credit. Therefore, this node has to wait to gain the needed credit. Resource Assignment in Federated Community Cloud Scenario In this experiment, we set up two local clouds, each with one SN and four ONs to study the federated community cloud scenario, as illustrated in Figure 4.1. Table 4.3 shows the two cases with different number of VMs available in the two zones. In the case of scarce capacity (case 1), the nodes in the SN1 zone share very few VMs compared to nodes in SN2 zone. In the case of equal capacity (case 2), the nodes in both the zones share the same number of VMs. 45 Figure 4.8: Ratio of fulfilled and rejected requests Figure 4.9 shows the proportion of the requests fulfilled by VMs provided by the other zone. With scarce capacity in SN1 zone, around 50% of the requests are fulfilled by VMs provided by SN2 zone. SN2 with sufficient capacity is able to meet most of the requests from VMs within the same zone, forwarding less than 15% requests to the other zone. In the second case, when both zones have the same available capacity, most of the requests get processed within the same zone for both the SNs. This shows that a federated community cloud scenario extends the resources assigned to zones with limited capacity. 4.4.3 Discussion From the simulation experiments (§ 4.4.1) we find that the effort-based resource regulation succeed in not only ensuring high system utilisation, but they also ensure fairness when rewarding users for their contributions. Following on from the insights through the simulation experiments, we implemented a prototype and from the results through its deployment in Guifi.net community network (§ 4.4.2), we observe that: 1. The prototype of the regulation service deployed in real community network nodes performed the required operations. Its components worked correctly both in the ON’s host operating system (OpenWRT) and the SN’s operating system (Debian). We could not observe the limitations of our implementation within scales that are realistic for 46 Table 4.3: Two cases with different resource distribution between zones Case 1: Scarce Capacity Case 2: Equal Capacity SNs ONs Total VMs Shared VMs Total VMs Shared VMs SN1 ON1 3 1 3 2 ON2 3 1 3 3 ON3 3 1 3 2 ON4 1 1 1 1 SN2 ON1 3 2 3 2 ON2 3 3 3 3 ON3 3 2 3 2 ON4 1 1 1 1 community networks. We note however that as a continuation of this work, a more extensive deployment of several federated community clouds with real users and real usage should ultimately be undertaken. 2. The algorithm used for the regulated resource allocation controlled the VM assignments, taking into account the user’s contribution and usage. More complex situations, however, should be created in further studies to provide additional insight into how the system behaves. 3. Our experiments were carried out on limited number of nodes and for limited time. If our prototype was deployed on additional nodes that are geographically widely spread and run for extended periods, the VM assignment decisions might need to take into account information from network awareness to select the appropriate cloud resource providers. 4.5 Summary We focused in this chapter on the need for an incentive-driven regulation mechanism, and identified it as a key component to encourage contribution towards and foster adoption of community clouds. We investigated incentive mechanisms for community clouds based on reciprocal resource sharing, and the results highlight their impact on the efficiency of the system and on regulating the resource assignments. The regulation component is implemented in a simulator in order to be able to perform assessments for large scale scenarios. With 47 • We implement instances of the framework and report the results from its deployment on the actual Guifi.net nodes. The rest of the chapter is organised as follows. First, we discuss the motivation for a truthful and trusted resource allocation mechanism in § 5.1. Next, we provide the system model in § 5.2. We present the framework for simulating the auctioneer in § 5.3, and we illustrate its applicability to the execution of two different auction mechanisms, with different computational properties, in § 5.3.3. We discuss results from the experiments using a prototype for distributed auctioneer in § 5.4. 5.1 Motivations We have seen in Chapter 4 how incentives based resource regulation is important to encourage contribution and thus ensure a sustainable community cloud ecosystem. However, the mechanisms in Chapter 4 assume the users will always follow the prescribed polices, and just like in community networks, the social context and the ties between the community would be sufficient to correct any erroneous behaviour. But these assumptions do not always hold true, especially when the community cloud would grow to a large user base. With weakening of any direct social interaction, the system may be open to abuse by the selfish or malicious users. This can negatively impact the viability of community cloud model. In order to understand better the implications of untruthful behaviour, we study the effects of untruthfulness on the utility obtained by the users and the social welfare of the overall system [Kha+15b]. We first present a model that differentiates between cloud applications with different priority classes. Next, we use this model to evaluate the impact of untruthfulness on the social welfare through simulation experiments, for the different pricing mechanisms proposed in the literature [MT14]. 5.1.1 System Model We consider a bandwidth provider 𝒫in the community network and a set of N users {1,2,…𝑁}. The provider operates a gateway to the Internet, which allows access to resources outside the community network for the users. The users are connected to the provider’s gateway through the wireless and fibre links in the community network [Bai+15b], and the applications in community network cloud access their external servers and Internet through this gateway. Figure 5.1 shows the users in the community network connected to 54 the provider through multiple such paths, where only few of these users are the clients of the provider for reserving bandwidth. The provider processes the requests in a queue at the gateway, where time in the queue is divided into an infinite sequence of slots starting from 1, where all the available bandwidth is allocated to exactly one user in each slot. The provider allocates the slots in batch after receiving all the requests from 𝑁users and assigns the next 𝑁slots, one to each user. We choose this model for simplicity, and we divide users into different priority classes based on their slots in the queue, as discussed below. Our findings are applicable to other models, for instance where all the available bandwidth is shared between the users at the same time. In this case, we can have priority classes based on the quality of different links, for example. Considering the provider has two links to the Internet, high priority requests are assigned to the better link with low latency, less packet loss, etc., while the low priority requests are assigned the other link. The discussion and findings presented below can equally apply to this alternate model as well. We divide theusers into twopriority classes, ℎ∈{0,1}, somehavelower priorityrequests, ℎ0, and some have higher priority requests, ℎ1. Here in this model, the main consideration for higher priority requests is that they are more sensitive to the waiting time, and prefer to reserve earlier slots in the queue. Provider 𝒫aims for an optimal schedule when allocating the slots to the users, so as to maximise its revenue and the overall utility for all the users. We provide formal details below. Schedule A schedule 𝜙maps each time slot 𝑡to a user 𝑖. Value For any schedule 𝜙and user 𝑖, let 𝑡be the slot assigned to user 𝑖, then 𝑣𝑖(ℎ,𝑡)is the valuation given by 𝑖for being allocated time slot 𝑡, where ℎ ∈ {0,1}is the priority class of the user. 𝑣𝑖is communicated by each 𝑖to 𝒫beforehand. Utility For any schedule 𝜙which assigns user 𝑖a slot 𝑡, the utility 𝑢𝑖(𝜙,𝑡) for user 𝑖is difference between the value 𝑣𝑖and the payment 𝑝𝑖(𝜙,𝑡)made by user 𝑖to 𝒫. 𝑢𝑖(𝜙,𝑡)=𝑣𝑖(ℎ,𝑡)−𝑝𝑖(ℎ,𝑡) (5.1) Restriction Any slot 𝑡can be assigned to at most one user. 55 Optimization Find 𝜙that maximises the social welfare, which is the sum of utilities 𝑢𝑖of all users, while fulfilling the restrictions. maximise welfare (𝜙)= ∑ 𝑖∈𝑁𝑢𝑖(𝜙,𝑡) (5.2) Scheduler Function 𝑆that maps 𝑢=(𝑢𝑖)𝑖∈𝑁 to optimal 𝜙. Goal A user 𝑖when submitting the request to 𝒫, declares the priority class ℎ𝑖and value 𝑣𝑖, and also the bid amount 𝑏𝑖where applicable. When the user behaves truthfully the reported value 𝑣∗ 𝑖is the same as her inherent value 𝑣𝑖. We want to ensure that it is in the interest of every 𝑖to declare her true value of 𝑣𝑖, regardless of the declared values 𝑣𝑗for any 𝑗 ≠ 𝑖. Such a mechanism is said to be truthful in dominant strategy, where users have no incentive to misreport their values [NR99]. 5.1.2 Pricing Mechanisms Given the above model, the prices are calculated for the bandwidth usage according to different mechanisms [MT14]. Fixed Pricing In the case of fixed usage-based pricing, all the users pay the identical price 𝑐0for each unit of bandwidth consumed, which is constant irrespective of the priority class. Priority Pricing In the case of priority pricing, users pay according to the priority class ℎ. Since in our model, there are only two priority classes ℎ0and ℎ1, provider 𝒫charges two different prices 𝑐ℎ0and 𝑐ℎ1per unit of bandwidth, respectively. First-Price Auction In the case of sealed first-price auction, users make different bids 𝑏𝑖 depending on their priority class ℎ, with high priority requests quoting higher bid amounts in general. Each winning user pays their bid amount. 𝑝𝑖(𝜙,𝑡)=𝑏𝑖(5.3) 56 Generalised Second Price (GSP) Auction In a generalised second price (GSP) auction, users make different bids 𝑏𝑖but in this case the winning user pays the amount corresponding to the next highest bidder [Jan+11]. So the user with the highest bid pays the amount of the second highest bidder, and the second highest bidder pays the amount of the third highest bidder, and so on. Vickrey-Clarke-Groves (VCG) Auction VCG is a second-price sealed-bid auction based mechanism, which ensures truthfulness and maximum social welfare [NR99], if the provider 𝒫can calculate optimal schedule 𝜙in polynomial time. Each user 𝑖provides a bid 𝑏𝑖to 𝒫, and given a schedule 𝜙, each user 𝑖pays the price 𝑝𝑖(𝜙,𝑡)according to: 𝑝𝑖(𝜙,𝑡)= ∑ 𝑗!=𝑖 𝑗∈𝑁 (𝑣𝑗(ℎ,𝜙′)−𝑏𝑗)− ∑ 𝑗!=𝑖 𝑗∈𝑁 (𝑣𝑗(ℎ,𝜙)−𝑏𝑗)(5.4) where 𝜙and 𝜙′are the schedules that maximise ∑ 𝑖∈𝑁𝑢𝑖while including and excluding the bid 𝑏𝑖by user 𝑖from the allocation respectively. 5.1.3 Scheduling Algorithm We consider a simple scheduling algorithm which applies a greedy approach for mapping users’ requests to the available slots. Algorithm 5.1 shows the scheduling algorithm, where 𝒫 assignsthe slots tothe usersin non-increasingorderof their reported bids (andcorresponding ℎ𝑖and 𝑣𝑖) for the bandwidth resource. The prices calculated are dependent on the pricing mechanism, the priority class ℎof the requests, and the assigned slot 𝑡in the schedule 𝜙. The runtime of the algorithm is 𝑂(𝑁𝑙𝑜𝑔𝑁)for 𝑁users for the different pricing mechanisms. VCG mechanism, however, requires computing 𝑁schedules for calculating payments for the 𝑁winning bids, so the running time in the case of VCG is 𝑂(𝑁2𝑙𝑜𝑔𝑁). The greedy approach, in general, does not always provide an optimal allocation, which is a pre-requisite for VCG mechanism. However, in the case of the model given above and considering the step function we are going to use for 𝑣𝑖(ℎ,𝑡)from Figure 5.2, the greedy approach from Algorithm 5.1 always returns an optimal allocation. This can be proven through induction, and can be explained intuitively as follows. Selecting the requests with higher bids first (corresponding to higher ℎ𝑖and 𝑣𝑖) will always give the maximum social welfare, since the value function in Figure 5.2 is non-increasing with time and choosing a bid with lower amount causes a loss in social welfare which cannot be recovered as the time progresses. 57 Algorithm 5.1 Scheduling algorithm for 𝜙, allocating  𝑡slots to 𝑁users Input: List of users 𝑛, bids  𝑏, for total 𝑁users Output: List of assigned slots  𝑡, and payments 𝑝 1: Sort 𝑛users in non-increasing order on their bids  𝑏 2: for 𝑖 =1,…𝑁 do 3:  𝑡[𝑖]← 𝑛[𝑖] ▷Assign slots 4: end for 5: for 𝑖 =1,…𝑁 do 6: 𝑝[𝑖]←payment ( 𝑏[𝑖],  𝑡[𝑖]) ▷Calculate payments 7: end for 5.1.4 Evaluation We conduct the simulation experiments using the multi-agent programmable modelling environment NetLogo [Wil99]. In all the experiments, we consider a single provider and 500 users. We run the experiments for 1000 rounds, and plot the average values in the graphs. For different pricing mechanisms (as explained in § 5.1.2), we use the following values. For fixed pricing, we set 𝑐0=0.5. For priority pricing, we set 𝑐ℎ0=0.25and 𝑐ℎ1=0.75. For auctions based pricing, the bids for lower priority requests ℎ0are uniformly distributed in the range [0.25,0.5], while the bids for higher priority requests ℎ1are uniformly distributed in therange(0.5,0.75]. For differentiatingbetween the two priorityclasses, wechoose different time-utilityfunctions(TUF),whichin thiscasewehavechosen asstepfunctionsforsimplicity. According to this step function, the value 𝑣𝑖(ℎ,𝑡), based on priority class ℎand slot 𝑡in schedule 𝜙, decreases for both higher and lower priority classes after a threshold 𝑡0=𝑁 2, as shown in Figure 5.2. Specifically, for lower priority class ℎ0: 𝑣𝑖(ℎ0,𝑡)=⎧ { ⎨ { ⎩ 1.5 if 𝑡≤ 𝑁 2 1if 𝑁 2<𝑡≤𝑁 (5.5) And for high priority class ℎ1: 𝑣𝑖(ℎ1,𝑡)=⎧ { ⎨ { ⎩ 3if 𝑡≤ 𝑁 2 2if 𝑁 2<𝑡≤𝑁 (5.6) Each user 𝑖submits exactly one request to 𝒫, declaring her priority class ℎ𝑖, value 𝑣𝑖, and 58 t/ 4 t/ 2 3 t/ 4 t t 0.0 0.5 1.0 1.5 2.0 2.5 3.0 v ( h, t ) h = h 1 (Higher priority) h = h 0 (Lower priority) Figure 5.2: Value function 𝑣𝑖(ℎ,𝑡)for user 𝑖based on priority class ℎand slot 𝑡in schedule bid amount 𝑏𝑖where applicable. Both the priority classes, ℎ0and ℎ1occur with the same probability, so almost half of the requests are of higher priority, and the rest are of lower priority. We model lying behaviour of the users, by randomly flipping their reported priority class ℎto 𝒫, according to a uniform distribution. When the users lie, we observe the normalised difference from the case where all the users are truthful. Here, 𝑢∗ 𝑖(𝜙,𝑡) indicates the case where the users lie to 𝒫, and 𝑢𝑖(𝜙,𝑡)where all the users are truthful. 𝛥welfare =∑ 𝑖∈𝑁𝑢∗ 𝑖(𝜙,𝑡)− ∑ 𝑖∈𝑁𝑢𝑖(𝜙,𝑡) ∑ 𝑖∈𝑁𝑢𝑖(𝜙,𝑡) (5.7) Social Welfare Figure 5.3 shows how social welfare is affected when the probability 𝑝(𝑙𝑦𝑖𝑛𝑔)of a user misreporting her value to 𝒫increases up to the point where 90% of the users may be lying. As expected, social welfare decreases as the probability of lying increases, since 𝒫fails to allocate better slots for higher priority requests. All the pricing schemes behave similarly as the proportion of lying users increases, except VCG which performs marginally better in that social welfare is slightly higher for VCG as compared to the other schemes. This shows the importance of encouraging truthful behaviour in the users for maximising social welfare. 59 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 p ( lying ) 16 14 12 10 8 6 4 2 0 ∆ welfare % First Price Fixed GSP Priority VCG Figure 5.3: Percentage difference in social welfare as more users lie Individual Gain in Utility for Different Classes To understand how the pricing mechanisms incentivise truthfulness for different priority classes, in the next experiment we look at the normalised difference in utility for an individual user (on average), separately for ℎ0and ℎ1. Here again, 𝑢∗ 𝑖(𝜙,𝑡) is the individual utility when some of the users lie, and 𝑢𝑖(𝜙,𝑡)is when all the users are truthful. 𝛥utility =𝑢∗ 𝑖(𝜙,𝑡)−𝑢𝑖(𝜙,𝑡) 𝑢𝑖(𝜙,𝑡) (5.8) Figure 5.4 shows the percentage difference in the average utility for all the users with low priority requests. Note that this average is over all the users in ℎ0, and not only those who lie. Users from ℎ0may lie in order to get higher value (through reserving an earlier slot), hoping to still pay as little as possible. Figure 5.4 shows that for fixed usage-based price, they do gain in utility since they are paying the same amount for a better service. For priority pricing, they gain nothing as any gains in utility are offset by the higher price. For first price and GSP auctions, the results are similar and there are gains due to lying, though less than those in the case of the fixed price. The first price and GSP auctions behave similarly since expected payments are the same in the first and second price auctions, when the bids are independent and identically distributed [MT14], as is the case in this experiment. VCG performs better since the utility decreases as more users lie. Figure 5.5 shows the percentage difference in the average utility for all the users with high priority requests. Note that this average is over all the users in ℎ1, and not only those who lie. 60 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 p ( lying ) 40 20 0 20 40 60 80 100 ∆ utility % First Price Fixed GSP Priority VCG Figure 5.4: Percentage difference in utility for low priority class ℎ0 Users from ℎ1may lie in order to save on their payments, with the hope that they can still get the same value (through keeping their earlier slot). Figure 5.4 shows that users from ℎ1, in general, lose by lying since there is little chance that 𝒫will assign earlier slots to the users declaring low priority to 𝒫. So even though they save on the payments, the decrease in value because of getting assigned later slots results in net loss for users from ℎ1. Maximum Gains In the next experiment, we look specifically at the utility for the users that report untruthful values to 𝒫, to see the maximum gain they can get in the utility under different pricing mechanisms. Figure 5.6 shows the maximum gain in utility a user from ℎ0can get as the number of lying users increases. Note that in this case we pick only the maximum utility for a user from ℎ0that is lying, averaged across all the experiment runs. The results are similar to what we observed earlier in Figure 5.4. Similarly, Figure 5.7 shows the maximum gain in utility a user from ℎ1can obtain through lying. We noticed in Figure 5.5 that on average the users from ℎ1do not gain through lying, but here we see that for all the pricing mechanisms except VCG, the utility for a lying user with high priority request increases with increase in the number of lying users, though the net gain is not significant. For VCG, the number of lying users does not have much impact, and the loss in utility for the lying user remains almost the same. Moreover, first price and GSP auctions perform better than priority pricing here. The user can have a net gain in utility by misreporting her priority class as ℎ0when more than half of the users are lying in the case of 61 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 p ( lying ) 35 30 25 20 15 10 5 0 5 ∆ utility % First Price Fixed GSP Priority VCG Figure 5.5: Percentage difference in utility for high priority class ℎ1 priority pricing. 5.1.5 Discussion We find that static pricing schemes like fixed usage-based pricing and priority pricing are not very useful for arbitration between requests from different priority classes, since it is hard to avoid everyone reporting their requests as higher priority [MT14]. Dynamic pricing, for example, based on first-price auction can help here but with this simple auction scheme users report bid amounts lower than their true valuation of the bandwidth resource [MT14]. VCG mechanism, when either using optimal allocation algorithms [NR99] or approximate allocation algorithms [Zha+15b], can ensure truthfulness but is often computationally intensive to implement in practice. Generalised second price (GSP) auction mechanism, an extension of VCG, is not as computationally intensive as VCG and even though it doesn’t guarantee truthfulness, it shares many desirable properties of VCG [MT14]. These results show that auction-based mechanisms are good candidates for using in allocation algorithms for bandwidth reservation in community network clouds. However, these mechanisms assume that a centralised auctioneer exists that can be trusted to to execute the allocation algorithm as designed. In the absence of a trusted auctioneer, the truthfulness guarantees of mechanisms like GSP and VCG no longer hold. To address the shortcoming that a centralised trusted auctioneer is not feasible in community network clouds, we present our proposal for a virtual distributed auctioneer in § 5.3. 62 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 p ( lying ) 40 20 0 20 40 60 80 100 ∆ utility % First Price Fixed GSP Priority VCG Figure 5.6: Maximum gain in utility for a user from low priority class ℎ0 5.2 System Model We define the family of resource allocation auctions, the requirements of a distributed simulation of the auctioneer, and the Game Theoretical model used to analyse simulations. These provide basis for our proposed framework for distributed auctioneer (§ 5.3). 5.2.1 Resource Allocation Auctions Consider a family of auctions with 𝑚providers,𝑛users, and an auctioneer. Providers sell multiple resources with a limited capacity, in exchange for payments in some currency. Users are willing to pay to the providers in exchange for the allocation of a minimum amount of each resource in the provider. The auctioneer defines an allocation between users and providers that is feasible (i.e., that does not exceed the capacity of each resource in any provider) and defines the payments to be made/received by the users/providers, respectively. Both users and providers attribute a utility to each allocation, which is a function of the value given to the allocation and the payments made/received. More precisely, each user 𝑖has a valuation 𝑣𝑖specifying how much 𝑖is willing to pay for the allocation of a unit of each resource in each provider; 𝑖’s utility is the difference between the total value attributed by 𝑖to the allocation and the payments made by 𝑖. On the other hand, the valuation 𝑣𝑗of a provider 𝑗specifies how much 𝑗wants to be paid for allocating a unit of each resource; 𝑗’s utility is the difference between the payments received by 𝑗and the total value attributed by 𝑗to the allocation. Note that in the context of our model, providers are the owners of the gateways, and have 63 Allocator The input at every provider is a vector  𝑏of bids, and the output is either a pair (𝑥, 𝑝) or ⊥. We want the allocator to satisfy four conditions. First, we want the allocator to correctly simulate 𝒜, i.e., given that all providers input the same vector  𝑏and follow the protocol, every provider must eventually output pair (𝑥, 𝑝)with probability 𝒜(𝑥, 𝑝 ∣  𝑏). Second, we want resilience to collusive influences, defined as, for all coalitions 𝐾of at most 𝑘elements, if all providers not in 𝐾input  𝑏and follow the protocol, then no 𝑗∉𝐾outputs a pair (𝑥, 𝑝) with probability higher than 𝒜(𝑥, 𝑝∣  𝑏), regardless of the protocol followed by providers in 𝐾. Intuitively, no coalition 𝐾can influence the output of providers not in 𝐾, except that they may output ⊥with higher probability. Third, we want input validation to ensure that providers have preference for solutions at the bid agreement. More precisely, if two providers input different vectors and follow the protocol, then they both output ⊥, regardless of the protocol followed by other providers. Finally, we want 𝑘-resilience for solution preference given that all providers have the same input. Property 5.2. A protocol 𝑃implements the allocator if and only if it satisfies four conditions: (1) correct simulation of 𝒜; (2) resilience to collusive influence; (3) input validation; and (4) 𝑘-resiliency for solution preference if all providers have the same input. We discuss implementations of the allocator in § 5.3.2. Analysis We show in Theorem 5.1 that a protocol that implements our framework correctly simulates the auctioneer and is 𝑘-resilient. Theorem 5.1. For every protocol 𝑃that implements the framework, 𝑃correctly simulates the auctioneer, and there exists a function 𝑓such that, if 𝑚 > 𝑓(𝑘), then 𝑃is a 𝑘-resilient equilibrium. Proof. First, we show that 𝑃correctly simulates the auctioneer. Every provider 𝑗inputs  𝑏𝑗 to the bid agreement. By (1) of Property 5.1, regardless of the inputs, all providers output the same vector  𝑏that satisfies validity. By (1) of Property 5.2, the outcome of the simulation is pair (𝑥, 𝑝)with probability 𝒜(𝑥, 𝑝∣  𝑏). This concludes the first step of the proof. Now, we show that 𝑃is a 𝑘-resilient equilibrium for 𝑚>𝑓(𝑘)for some 𝑓. Fix a coalition 𝐾. We take 𝑓to be larger for all 𝑘than the minimum value of 𝑚required by Properties 5.1 70 and 5.2. These properties imply that, if providers have preference for a solution at the bid agreement, then the implementations of bid agreement is 𝑘-resilient, so providers in 𝐾prefer to follow 𝑃for bid agreement. Since this guarantees that all providers have the same input at the allocator, the implementation of the allocator is also 𝑘-resilient, implying that 𝑃is 𝑘-resilient. Now, we show that solution preference holds for both blocks. Recall that the outcome is not ⊥only if providers not in 𝐾output the same pair, and, if the outcome is ⊥, then the utility is 0. Hence, providers in 𝐾prefer (obtain an expected utility at least as high) that providers not in 𝐾output the same pair (𝑥, 𝑝); in this case, they clearly prefer to output (𝑥, 𝑝)as well, thus they have preference for a solution at the allocator. Now, consider the bid agreement. The utility of an outcome of this block is the expected utility given that providers not in 𝐾 follow 𝑃and providers in 𝐾follow an arbitrary protocol. Clearly, providers in 𝐾prefer that no provider in 𝐾outputs ⊥. By (3) of Property 5.2, providers in 𝐾prefer that all providers not in 𝐾output the same vector. By (2) of Property 5.2, providers in 𝐾cannot increase the probability of any outcome of the framework other than ⊥by deviating, thus, they cannot increase their expected utility by outputting a vector  𝑏′≠ 𝑏at the bid agreement. This shows that providers have preference for a solution at the bid agreement, concluding the proof. 5.3.2 Parallel Allocator Framework We describe a framework for implementations of the allocator that satisfy Property 5.2. We explore the possibility of parallelising the execution of 𝒜in multiple providers. Although this approach introduces the overhead of communication between providers, since 𝒜is often computationally intensive, its parallelisation compensates for this overhead. The framework consists in an initial invocation of a building block for input validation followed by the simulation of 𝒜, which invokes two additional building blocks: data transfer and common coin. The input is a vector of bids and the output is either ⊥or a pair (𝑥, 𝑝). At the invocation of each block, providers either output a valid value or ⊥; in the latter case, they output ⊥at the allocator. To describe the simulation of 𝒜, it is useful to characterise the execution of 𝒜in terms of a graph of tasks, where nodes correspond to tasks to be executed in sequence and edges represent data dependencies. This graph establishes a partial order of tasks; every two tasks that are not ordered can be executed in parallel by different providers. Figure 5.9 gives an example of a graph of 4tasks, where tasks T2.1 and T2.2 can be executed in parallel. To cope with collusion, each task 𝑇is assigned to a set 𝑆of at least 𝑘+1providers. If a task 𝑇′is to be executed by a set 𝑂≠𝑆of providers and 𝑇′depends on the result of 𝑇, 71 T3T1 T2.1 T2.2 Figure 5.9: Decomposition of the Allocator into Tasks then the providers of 𝑆transfer data to the providers of 𝑂using the data transfer building block. In a correct simulation of 𝒜, there must be one final task that depends on all other tasks, where all providers gather all the required data to produce the final output. Whenever providers need a random number distributed according to a probability distribution 𝛱, they invoke the common coin with input 𝛱. Figure 5.10 illustrates the framework for the task decomposition of Figure 5.9. As in the previous section, we describe properties that must be satisfied by the implementations of each block and then show that every implementation of this framework satisfies Property 5.2. Input Validation The input is a vector  𝑏and the output is either ⊥or  𝑏. We want an implementation to satisfy 𝑘-resiliency for solution preference and that all providers eventually output  𝑏given that they all input  𝑏, and we need to satisfy (3) from Property 5.2. Property 5.3. An implementation 𝑃of the input validation must satisfy three conditions: (1) if two providers follow 𝑃and have different inputs, then they eventually output ⊥; (2) if all providers follow 𝑃with the same input  𝑏, then they eventually output  𝑏; and (3) 𝑘-resiliency for solution preference if all providers have the same input. A simple implementation is to have providers broadcasting their vectors of bids and outputting ⊥when two different vectors are detected. This clearly satisfies (1) and (2), whereas (3) is immediately true if providers have preference for a solution and 𝑚>𝑘. 72 1 2 4 Providers Allocator b b b(x,p) (x,p) (x,p) T1 3 1 2 4 3 (x,p) T1 T2.1 T2.1 T2.2 bT2.2 D T T3 T3 T3 T3 CC I V T1 T1 Providers Figure 5.10: Parallel Allocator: Input Validation (IV), Data Transfer (DT), and Common Coin (CC) Common Coin The input is a probability distribution 𝛱and the output is either ⊥or a number distributed according to 𝛱. Given that all providers have the same input, we want the common coin to satisfy 𝑘-resilience for solution preference and to output the same random number. Property 5.4. Given that all providers have input 𝛱, an implementation 𝑃of the common coin must satisfy two conditions: (1) if all providers follow 𝑃, then they eventually output the same value distributed according to 𝛱; and (2) 𝑘-resiliency for solution preference. A possible implementation of the shared coin is the protocol from [ADH13]. The idea is that every provider 𝑗commits to a random number 𝑟𝑗∈ [0,1], before learning the random numbers of every other provider not in its coalition. Then, providers reveal all random numbers and compute the output by summing all numbers modulo 1. If some provider 𝑗sees a number not in [0,1]or some provider does not send a random value compatible with its commitment, then it outputs ⊥. Otherwise, 𝑗applies a transformation on the computed value, which is uniformly distributed in [0,1], to produce an output that is distributed according to 𝛱. It is clear that all providers output the same random number distributed according to the common input 𝛱if they follow the protocol. Assuming that 𝑚>𝑘, no provider 𝑗can manipulate the probability distribution of the output by not committing to 𝑟𝑗selected at ran- 73 dom without some provider outputting ⊥, even if 𝑗is in a coalition of at most 𝑘providers. Therefore, the protocol satisfies 𝑘-resiliency for solution preference. Data Transfer A set 𝑆of providers inputs a value from a domain 𝐷. Providers from a set 𝑂either output a value from 𝐷or ⊥. When all providers in 𝑆have the same input, we want them to output the same value in 𝐷when they follow the protocol. We only require an implementation to be 𝑘-resilient if |𝑆|,|𝑂|>𝑘, since otherwise coalitions can always manipulate the output of this block. Property 5.5. Given that |𝑆|,|𝑂|>𝑘and all providers have the same input 𝑣, an implementation 𝑃of the data transfer must satisfy two conditions: (1) if all providers follow 𝑃, then they eventually output 𝑣; and (2) 𝑘-resiliency for solution preference. We propose a simple 𝑘-resilient implementation of this block, where providers in 𝑆broadcast their input to all providers in 𝑂. In the end, if some provider 𝑗∈𝑂detects two different values, then 𝑗outputs ⊥. Given that all providers have input 𝑣and that |𝑆|,|𝑂| > 𝑘, they eventually output 𝑣, and no coalition 𝐾of up to 𝑘providers can cause all providers to output 𝑣′∉{𝑣,⊥}. By solution preference, no provider in 𝐾gains if someone lies about the input 𝑣or omits a message. Analysis Theorem 5.2 shows that every implementation of the above framework satisfies the four conditions of Property 5.2. Theorem 5.2. Every protocol 𝑃that implements the parallel allocator satisfies Property 5.2. Proof. We show that 𝑃ensures (1) correct simulation of 𝒜; (2) resilience to collusive influence; (3) input validation; and (4) 𝑘-resiliency for solution preference if all providers have the same input. First, we show (1). Suppose that all providers input the same vector  𝑏and follow 𝑃. We show that every provider outputs the same pair (𝑥, 𝑝)with probability 𝒜(𝑥, 𝑝 ∣  𝑏). We show using induction that, if the decomposition of 𝒜into tasks is done correctly and we fix all random numbers, then at every task 𝑇every provider 𝑗that executes 𝑇has the same output that she would have if 𝑗executed 𝒜locally with the same random numbers. This is true for the first task by (2) of Property 5.3. In the inductive step, the input at each task 74 depends only on the output of a set of tasks. For each of those tasks 𝑇, by the induction hypothesis, a set 𝑆of at least 𝑘+1providers computes the same result and inputs it to the data transfer; by (1) of Property 5.5, all providers that execute 𝑇receive that value and perform the same computation as they would if they were executing 𝒜. This implies that all providers output the same pair at the end. By (1) of Property 5.4, at every invocation of the common coin, all providers input the same distribution 𝛱and output the same random number distributed according to 𝛱, where 𝛱is specified by 𝒜. This proves (1). Now, we show (2). Fix a coalition 𝐾and suppose that all providers not in 𝐾follow 𝑃with input  𝑏and providers in 𝐾follow an arbitrary 𝑃′≠ 𝑃. The only way that providers in 𝐾 could cause providers not in 𝐾to return pair (𝑥, 𝑝)with probability higher than 𝒜(𝑥, 𝑝∣  𝑏) is if the result of some task used in the input of another task or as the final output is not distributed as specified by 𝒜and  𝑏. Since each task is executed by more than 𝑘providers, using an identical reasoning to the proof of (1), we can show using induction that providers in 𝐾cannot manipulate the probability distribution over the results of each task, except only by increasing the probability of some provider not in 𝐾outputting ⊥. Here, we use the fact that, by (3) of Property 5.3 and (2) of Properties 5.4, 5.5, providers in 𝐾cannot manipulate the probability distribution over outputs of the building blocks in a way that increases the expected utility of some provider in 𝐾. This proves (2). Condition (3) follows by (2) of Property 5.3. To show (4), we first need to prove that providers have preference for a solution at all invocations of building blocks, assuming that they have preference for a solution of the allocator. Fix a coalition 𝐾. It is clear that providers in 𝐾prefer that providers not in 𝐾do not output ⊥at all invocations. Now, we use backward induction to show that they prefer that providers not in 𝐾never return different values. In the last invocation, this is clearly true by preference for a solution of the allocator. Continuing backwards, if two providers not in 𝐾output different values at the same invocation of some block, then either they output different pairs at the end or input different values at the following invocation of the data transfer, which by the hypothesis is never preferable to outputting the same value at the considered invocation. By the proof of (2), providers in 𝐾cannot manipulate the final outcome by not outputting the same values at all invocations, so they also prefer to output the same values as providers not in 𝐾, showing solution preference at all invocations. This also shows that providers prefer to have the same input at all invocations. Thus, given that all providers have the same input, no provider in 𝐾can increase its expected utility if some provider 𝑗∈𝐾does not compute each task correctly. By (3) of Property 5.3 and (2) of Properties 5.4 and 5.5, 𝑃is a 𝑘-resilient equilibrium. 75 5.3.3 Resource Allocation Instances We now show how our framework can be applied to two different bandwidth allocation problems in the context of community networks. For that purpose, we resort to two different algorithms that have been proposed in the literature to solve bandwidth allocation for users in providers. These algorithms rely on standard and double auctions respectively, and have different computational properties: the double auction algorithm provides an example of a graph with only one task that is not computationally intensive, such that decomposing its execution into parallel tasks does not provide a performance gain; the standard auction algorithm provides a graph with multiple computationally intensive tasks that can be parallelised. Later in the chapter (§ 5.4), we will use these examples to evaluate the performance of implementations of the framework. We use the double auctions example to measure a worstcase overhead of executing all building blocks of the framework compared to an execution with a centralised trusted auctioneer, and we use the standard auctions example to show that the improvements of parallelisation can outweigh the added overhead when the execution time is dominated by computation. Double Auction Consider an auction where each provider has a limited bandwidth to be allocated to multiple users, and each user has a demand of bandwidth that may be satisfied by multiple providers. Both the users and the providers declare in their bids the value given to a unit of allocated bandwidth. An allocation gives the amount of bandwidth for each user allocated in each provider. We want to ensure truthfulness in expectation and budget balance. For this purpose, we use the algorithm 𝒜of [Zhe+14], which provides the above properties at the expense of social welfare. The idea is to order the providers by increasing value and to order the users by decreasing value. Then, users are allocated by their order to the providers using the water-filling method: the maximum amount of bandwidth of each user is allocated to the first available provider without exceeding its capacity, and any unsatisfied demand of that user is allocated to the following providers using the same method. Since the most computationally intensive task of this algorithm is sorting, in most practical settings there is no performance gain in parallelising the execution of 𝒜. Instead, every provider executes 𝒜locally and outputs the result. Hence, we never need to invoke the data transfer building block. 76 Algorithm 5.2 Standard auction allocator 1: Task 1: Calculate the allocation solution 𝑥 2: for Each subset 𝑆of bidders in parallel do 3: Task 2.𝑆: calculate payment 𝑝𝑗of every 𝑗∈ 𝑆 4: end for 5: Task 3: Collect the outputs of each task with the data transfer and output (𝑥, 𝑝) Standard Auction Consider a variation of the double auction where providers do not send bids and each bidder can only have its bandwidth demand allocated in a single provider. Here, we aim for truthfulness in expectation, maximal social welfare, and computational efficiency. It is well known that a VCG mechanism can be used to provide the first two guarantees. The difficulty is that determining the maximal social welfare is in general an NP Hard problem, which conflicts with the goal of computational efficiency. To address this issue, we use the algorithm of [Zha+15b] which adapts the VCG mechanism to achieve a tradeoff between the two conflicting requirements. Specifically, [Zha+15b] offers a (1 − 𝜖) approximation of maximal social welfare for an arbitrarily small 𝜖, while terminating in polynomial time according to smoothed analysis. Interestingly, the randomised algorithm proposed in [Zha+15b] has the potential for parallelisation. In a course manner, the algorithm can be divided into three steps, depicted in Algorithm 5.2. The first step derives an approximately optimal allocation of users to providers. This step is hard to parallelise effectively in a distributed system, so we run it in a single sequential task. The second step calculates the payments for each user based on the result of the first step. This step is computationally intensive and the payments for each user can be computed independently and, therefore, can be easily parallelised. The final step gathers all intermediate results to produce the output. In our implementation, the first and third steps are executed by all providers. In the second step, we group the providers into 𝑐groups, each containing at least 𝑘+1providers. Each group is assigned the computation of the payments of a subset of 𝑛/𝑐 users. Then, all providers of a group execute the data transfer block to transfer the resulting payments to all providers. 77 5.4 Performance Evaluation We have evaluated the implementations of the allocator for double and standard auctions proposed in § 5.3.3. The implementations of all the remaining blocks are as suggested in § 5.3.2: we use the rational consensus algorithm proposed in [Afe+14] in the implementation of the bid agreement, while the input validation and data transfer blocks are implemented as simple broadcasts, and the common coin is implemented using the scheme from [ADH13]. For these implementations to be 𝑘-resilient equilibria, we need 𝑚 > 2𝑘. This is a requirement of the rational consensus algorithm. Our goal is to assess the overhead of the distributed protocol, when compared to a purely centralised solution, in the case the allocation algorithm is not parallelisable, and to assess the potential benefits from parallelisation when computationally expensive allocation algorithms are used. For that purpose, we measure performance gains for different levels 𝑝of parallelism, where 𝑝=⌊𝑚/(𝑘+1)⌋is the maximum level of parallelism for each possible 𝑘and 𝑝=1 represents the sequential execution by a trusted auctioneer. We consider a fixed number of 𝑚=8providers in the auctions, but we vary the number of providers that execute each protocol. 5.4.1 Hardware/Software Setup In order to obtain a meaningful evaluation of our approach, we have resorted to a prototype implementation on realistic hardware and software environment and deployed it in an experimental testbed for community networks, namely on nodes of the Guifi.net, one of the largest community networks in the world [Com16a]. We were given access to 4 different nodes of the experimental testbed, 2 machines in Barcelona, Spain (in different locations) and 2 machines in Trieste, Italy (in the same location) connected to Guifi.net through an Ethernet over IP tunnel. When doing tests executed by more than 4 providers we have instantiated multiple VMs in each nodes, ensuring that each VM is allocated a different CPU. The machines are Intel Core i7-3770 3.40GHz CPU with 16 GB RAM and 1 TB hard disk, running Proxmox virtualisation engine. Our experiment runs in OpenVZ containers with Debian 7 x86 1 CPU, 2 GB RAM, and 10 GB storage. We have implemented the framework in Python, using PyPy for speed reasons, and used ØMQ [Zmq16] as the messaging library for the communication. Since the communication overhead only depends on the number of providers involved in the computation (which depends on 𝑘and not on the complexity of the allocation algorithm), we have measured the communication overhead and the computation times separately and 78        n           m =8  m =8  k =1  m =8  k =2  m =8  k =3  Figure 5.11: Running time for double auction summed the corresponding values to derive multiple combinations of allocation problems and number of providers involved in the computation. All the values presented in the plots were obtained in this manner. These values, capture the time from when the inputs are available at the experiment instances, till the time the results are available at all of them. We run the experiments for 100 rounds, and plot the average values in the graphs. 5.4.2 Double Auction Deployment We have used an experimental set up similar to [Zhe+14] with some slight modifications suitable to our use case. In both the experiments, the double and standard auction, the bids by the users are uniformly distributed in the range [0.75,1.25], and the requested bandwidth resource is uniformly distributed in the range (0,1]. Before the experiment starts, the input data is generated and distributed to all the experiment instances. The input data in this case is a list of floating-point numbers denoting the values of the bids, requests, payments, capacities, and uses 𝑂(𝑛+𝑚)space for 𝑛users and 𝑚providers. We vary the capacity of the providers depending upon the overall bandwidth required, and scale it using a random factor in [0.5,1.5]so as to consider both the cases where providers lack the capacity to satisfy all the requests, and where the providers have excess capacity. The providers have a unit cost of bandwidth uniformly distributed in the range (0,1]. Figure 5.11 shows the running time for the double auction algorithm (§ 5.3.3) as a function 79 6.2 Future Work Carrying onwards from the experience and results with the prototype implementations, a working service needs to be developed further, that provides the feedback loop between the users’ contribution and experience, and will be inevitable for adoption, sustainability, maintenance and growth of cloud infrastructures in community networks. Larger scale deployments are required with extended implementation of the different components of the community cloud framework. This should be complemented by additional services and applications deployed in the cloud infrastructure, which will provide enhanced value and utility to the members of community networks for their contribution towards the community cloud. With respect to bandwidth allocation mechanism, there are others challenges, for instance, multiple users may be connected to the provider using the same path in the community network, and reserving bandwidth for such users in the same time interval may cause congestion across some of the links, which an intelligent allocation algorithm should try to avoid. Moreover, any bandwidth reservation scheme should not negatively impact the normal operation of the communitynetwork, so allocation mechanism needs tobe adaptiveto thenetwork congestion and bandwidth usage in the community network. For distributed auctioneer, we have considered only rational users, and we plan to extend our framework to the Byzantine users. In the current model, we assumed all providers to be fully inter-connected. But in the case of federated community clouds, it is possible that providers in different local clouds may not have very good connections between them, and so the current approach may result in slow down. In such cases, we plan to explore how to adapt our distributed auctioneer to different network topologies. The area of community cloud builds on a vast body of research in peer-to-peer and edge computing research, and the various lessons learnt from the successes and the failures of many P2P applications. We see a huge opportunity in extending this work for building the core community cloud services that drive innovation in many related areas, and not just the edge computing. The determinant of this success will not be just the technical sophistication with which the research challenges and open problems are solved, but also by how well the enthusiasts of the community cloud succeed in capturing the imagination and meeting the expectations of the end users. 86 Notes The research discussed in this chapter (§ 6.1) was included in the following publications. [Bai+15] Roger Baig, Felix Freitag, Amin M Khan, Agusti Moll, Leandro Navarro, Roger Pueyo Centelles, and Vladimir Vlassov. “Community Clouds at the Edge deployed in Guifi.net”. In: 4th International Conference on Cloud Networking (CloudNet 2015). Niagara Falls, Canada: IEEE, Oct. 2015. [Fre+14] Felix Freitag, Leila Sharifi, Amin M Khan, Leandro Navarro, Roger Baig, Pau Escrich, and Luis Veiga. “A Look at Energy Efficient System Opportunities with Community Network Clouds”. In: Workshop on Energy-Efficient System (EES), within 2nd International Conference on ICT for Sustainability (IST4S 2014). Stockholm, Sweden, Aug. 2014. [Jim+13] Javi Jiménez, Roger Baig, Pau Escrich, Amin M Khan, Felix Freitag, Leandro Navarro, Ermanno Pietrosemoli, Marco Zennaro, Amir H Payberah, and Vladimir Vlassov. “Supporting cloud deployment in the Guifi.net community network”. In: 5th Global Information Infrastructure and Networking Symposium (GIIS 2013). Trento, Italy: IEEE, Oct. 2013. [KF14a] Amin M Khan and Felix Freitag. “Exploring the Role of Macroeconomic Mechanisms in Voluntary Resource Provisioning in Community Network Clouds”. In: 11th International Symposium on Distributed Computing and Artificial Intelligence (DCAI 2014). Vol. 290. Advances in Intelligent Systems and Computing. Salamanca, Spain: Springer International Publishing, June 2014, pp. 269–278. [KF14b] Amin M Khan and Felix Freitag. “Sparks in the Fog: Social and Economic Mechanisms as Enablers for Community Network Clouds”. In: ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal 3.8 (2014). [Kha+15] Amin M Khan, Felix Freitag, Smrati Gupta, Victor Muntés-Mulero, Jacek Dominiak, and Peter Matthews. “On Supporting Service Selection for Collaborative Multi-Cloud Ecosystems in Community Networks”. In: 29th IEEE International Conference on Advanced Information Networking and Applications (AINA 2015). Gwangju, Korea, Mar. 2015. [KFN16] Amin M Khan, Felix Freitag, and Leandro Navarro. “Community Clouds”. In: Encyclopedia of Cloud Computing. Ed. by San Murugesan and Irena Bojanova. Wiley-IEEE, June 2016. 87 [Kha+16] Amin M Khan, Felix Freitag, Leandro Navarro, and Roger Baig. “Enabling Clouds in Community Networks”. In: European Project Space on Research and Applications of Information and Communication Systems. Ed. by Carlos Cerqueira and James Uhomoibhi. Lisbon, Portugal: SCITEPRESS, 2016. [KFR15] Amin M Khan, Felix Freitag, and Luis Rodrigues. “Current Trends and Future Directions in Community Edge Clouds”. In: 4th International Conference on Cloud Networking (CloudNet 2015). Niagara Falls, Canada: IEEE, Oct. 2015. [Kha+13] Amin M Khan, Leila Sharifi, LeandroNavarro, and Luis Veiga. “Clouds of Small Things: Provisioning Infrastructure-as-a-Service from within Community Networks”. In: 2nd International Workshop on Community Networks and Bottom-up- Broadband (CNBuB 2013), within IEEE WiMob. Lyon, France: IEEE, Oct. 2013, pp. 16–21. [Sel+15] Mennan Selimi, Amin M Khan, Emmanouil Dimogerontakis, Felix Freitag, and Roger Pueyo Centelles. “Cloud services in the Guifi.net community network”. In: Computer Networks 93.P2 (Dec. 2015). Q2, pp. 373–388. 88 Bibliography [Abr+06] I Abraham, D Dolev, R Gonen, and J Halpern. “Distributed Computing Meets Game Theory: Robust Mechanisms for Rational Secret Sharing and Multiparty Computation”. In: PODC. 2006, pp. 53–62 (cit. on p. 16). [ADH13] Ittai Abraham, Danny Dolev, and Joseph Y. Halpern. “Distributed Protocols for Leader Election: A Game-Theoretic Perspective”. In: DISC. Vol. 8205. LNCS. Jerusalem, Israel, Oct. 2013, pp. 61–75 (cit. on pp. 16, 17, 53, 66, 73, 78). [Afe+14] Yehuda Afek, Yehonatan Ginzberg, Shir Landau Feibish, and Moshe Sulamy. “Distributed computing building blocks for rational agents”. In: PODC. New York, NY, USA: ACM Press, July 2014, pp. 406–415 (cit. on pp. 16, 17, 69, 78). [Agm+13] Orna Agmon Ben-Yehuda, Muli Ben-Yehuda, Assaf Schuster, and Dan Tsafrir. “Deconstructing Amazon EC2 Spot Instance Pricing”. In: ACM Transactions on Economics and Computation 1.3 (Sept. 2013), pp. 1–20 (cit. on pp. 11, 15). [Aiy+05] Amitanand S. Aiyer, Lorenzo Alvisi, Allen Clement, Mike Dahlin, Jean-Philippe Martin, and Carl Porth. “BAR fault tolerance for cooperative services”. In: ACM SIGOPS Operating Systems Review 39.5 (Oct. 2005), p. 45 (cit. on p. 16). [Alb04] Michael Albert. Parecon: Life After Capitalism. Verso Books, 2004 (cit. on pp. 8, 29, 33). [And04] David P Anderson. “BOINC : A System for Public-Resource Computing and Storage”. In: 5th IEEE/ACM International Workshop on Grid Computing. Pittsburgh, USA, Nov. 2004, pp. 4–10 (cit. on pp. 7, 21). [And+02] David P. Anderson, Jeff Cobb, Eric Korpela, Matt Lebofsky, and Dan Werthimer. “SETI@home: an experiment in public-resource computing”. In: Communications of the ACM 45.11 (Nov. 2002), pp. 56–61 (cit. on pp. 7, 21). [ALS10] J Chris Anderson, Jan Lehnardt, and Noah Slater. CouchDB: The Definitive Guide. 1st. O’Reilly Media, Inc., 2010 (cit. on p. 40). [Ath16] Athens Wireless Metropolitan Network (AWMN). 2016. url: http://www.awmn. net/ (cit. on p. 1). 89 [BCF07] Moshe Babaioff, John Chuang, and Michal Feldman. “Incentives in peer-to-peer systems”. In: Algorithmic Game Theory. Ed. by Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani. Cambridge University Press, 2007, pp. 593–612 (cit. on p. 7). [BMT12] Ozalp Babaoglu, Moreno Marzolla, and Michele Tamburini. “Design and implementation of a P2P Cloud system”. In: 27th Annual ACM Symposium on Applied Computing (SAC ’12). New York, NY, USA: ACM Press, Mar. 2012, pp. 412–417 (cit. on p. 21). [Bai+15a] Roger Baig, Felix Freitag, Amin M Khan, Agusti Moll, Leandro Navarro, Roger Pueyo Centelles, and Vladimir Vlassov. “Community Clouds at the Edge deployed in Guifi.net”. In: 4th International Conference on Cloud Networking (CloudNet 2015). Niagara Falls, Canada: IEEE, Oct. 2015 (cit. on pp. 22, 85). [Bai+15b] Roger Baig, Ramon Roca, Felix Freitag, and Leandro Navarro. “guifi.net, a crowdsourced network infrastructure held in common”. In: Computer Networks 90 (Oct. 2015), pp. 150–165 (cit. on pp. 1, 10, 30, 52, 54). [Beb+09] Adam L. Beberg, Daniel L. Ensign, Guha Jayachandran, Siraj Khaliq, and Vijay S. Pande. “Folding@home: Lessons From Eight Years of Volunteer Distributed Computing”. In: 8th IEEE International Workshop on High Performance Computational Biology (HiCOMB ’09), within IPDPS. Rome, Italy: IEEE, May 2009, pp. 1–8 (cit. on pp. 7, 21). [BG06] Maria Bina and GM Giaglis. “Unwired Collective Action: Motivations of Wireless Community Participants”. In: International Conference on Mobile Business (ICMB’06). Copenhagen, Denmark: IEEE, June 2006, pp. 31–31 (cit. on p. 7). [Bra+13] Bart Braem, Roger Baig Viñas, Aaron L. Kaplan, Axel Neumann, Ivan Vilata i Balaguer, Blaine Tatum, Malcolm Matson, Chris Blondia, Christoph Barz, Henning Rogge, Felix Freitag, Leandro Navarro, Joseph Bonicioli, Stavros Papathanasiou, and Pau Escrich. “A case for research with and on community networks”. In: ACM SIGCOMM Computer Communication Review 43.3 (July 2013), pp. 68–73 (cit. on pp. 1, 21, 43). [Buy13] Umit Cavus Buyuksahin. “On Incentive Mechanisms for Resource Sharing in Community Clouds”. Master’s thesis. Universitat Politècnica de Catalunya, 2013 (cit. on p. 48). 90 [Buy+02] Rajkumar Buyya, David Abramson, Jonathan Giddy, and Heinz Stockinger. “Economic models for resource management and scheduling in Grid computing”. In: Concurrency and Computation: Practice and Experience 14.13-15 (Nov. 2002), pp. 1507–1542 (cit. on p. 15). [BAV05] Rajkumar Buyya, David Abramson, and Srikumar Venugopal. “The Grid Economy”. In: Proceedings of the IEEE 93.3 (Mar. 2005), pp. 698–714 (cit. on p. 10). [Cap+09] Justin Cappos, Ivan Beschastnikh, Arvind Krishnamurthy, and Tom Anderson. “Seattle: a platform for educational cloud computing”. In: 40th ACM Technical Symposium on Computer Science Education (SIGCSE 2009). Chattanooga, USA: ACM, Mar. 2009, pp. 111–115 (cit. on p. 21). [Cat+14] Simon Caton, Christian Haas, Kyle Chard, Kris Bubendorfer, and Omer F. Rana. “A Social Compute Cloud: Allocating and Sharing Infrastructure Resources via Social Networks”. In: IEEE Transactions on Services Computing 7.3 (July 2014), pp. 359–372 (cit. on pp. 9, 13–15, 21, 24). [Cha+12] Kyle Chard, Kris Bubendorfer, Simon Caton, and Omer F. Rana. “Social Cloud Computing: A Vision for Socially Motivated Resource Sharing”. In: IEEE Transactions on Services Computing 5.4 (Jan. 2012), pp. 551–563 (cit. on p. 21). [Chu+03] Brent Chun, David Culler, Timothy Roscoe, Andy Bavier, Larry Peterson, Mike Wawrzoniak, and Mic Bowman. “PlanetLab: An Overlay Testbed for Broad- Coverage Services”. In: ACM SIGCOMM Computer Communication Review 33.3 (July 2003), pp. 3–12 (cit. on pp. 7, 21). [Clo16] Cloudy GNU/Linux Distribution. 2016. url: http://cloudy.community (cit. on pp. 25, 85). [Com16a] Community Cloud Testbed. 2016. url: http://wiki.clommunityproject.eu/ testbed:start (cit. on pp. 25, 78). [Com16b] Community-Lab: Community Networks Testbed by the CONFINE Project. 2016. url: http://community-lab.net/ (cit. on p. 40). [CW12] Costas Courcoubetis and Richard Weber. “Economic Issues in Shared Infrastructures”. In: IEEE/ACM Transactions on Networking 20.2 (Apr. 2012), pp. 594–608 (cit. on p. 10). [DP12] Salvatore Distefano and Antonio Puliafito. “Cloud@Home: Toward a Volunteer Cloud”. In: IT Professional 14.1 (Jan. 2012), pp. 27–31 (cit. on p. 21). 91 [EOS07] Benjamin Edelman, Michael Ostrovsky, and Michael Schwarz. “Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords”. In: American Economic Review 97.1 (2007), pp. 242–259 (cit. on p. 15). [FK03] Ian Foster and Carl Kesselman. The Grid 2: Blueprint for a new computing infrastructure. Elsevier, 2003 (cit. on pp. 7, 10). [Frei16] Freifunk. 2016. url: http://freifunk.net (cit. on p. 1). [Fre+14] Felix Freitag, Leila Sharifi, Amin M Khan, Leandro Navarro, Roger Baig, Pau Escrich, and Luis Veiga. “A Look at Energy Efficient System Opportunities with Community Network Clouds”. In: Workshop on Energy-Efficient System (EES), within 2nd International Conference on ICT for Sustainability (IST4S 2014). Stockholm, Sweden, Aug. 2014 (cit. on p. 85). [Fun16] FunkFeuer. 2016. url: http://funkfeuer.at/ (cit. on p. 1). [GC05] Daniel Grosu and Anthony T. Chronopoulos. “Noncooperative load balancing in distributed systems”. In: Journal of Parallel and Distributed Computing 65.9 (Sept. 2005), pp. 1022–1034 (cit. on p. 9). [GB14] Nikolay Grozev and Rajkumar Buyya. “Inter-Cloud architectures and application brokering: Taxonomy and survey”. In: Software: Practice and Experience 44.3 (Mar. 2014), pp. 369–390 (cit. on p. 15). [Gui+14] Yang Gui, Zhenzhe Zheng, Fan Wu, Xiaofeng Gao, and Guihai Chen. “SOAR: Strategy-proof auction mechanisms for distributed cloud bandwidth reservation”. In: IEEE International Conference on Communication Systems (ICCS 2014). Macau: IEEE, Nov. 2014, pp. 162–166 (cit. on p. 12). [Gui16] Guifi.net: Open, Free and Neutral Network Internet for everybody. 2016. url: http://guifi.net (cit. on p. 1). [Guo+13] Jian Guo, Fangming Liu, Dan Zeng, John C S Lui, and Hai Jin. “A cooperative game based allocation for sharing data center networks”. In: 32nd IEEE International Conference on Computer Communications (INFOCOM’13). Turin, Italy: IEEE, Apr. 2013, pp. 2139–2147 (cit. on pp. 12–14). [HT04] J Halpern and V Teague. “Rational Secret Sharing and Multiparty Computation: Extended Abstract”. In: STOC. 2004, pp. 623–632 (cit. on p. 16). 92 [Hur73] Leonid Hurwicz. “The Design of Mechanisms for Resource Allocation”. In: The American Economic Review 63.2 (1973), pp. 1–30 (cit. on p. 9). [Jan+11] R. Jana, Karthik N. Kannan, Yih-Farn Chen, R. Jana, and Karthik N. Kannan. “Using Generalized Second Price Auction for Congestion Pricing”. In: IEEE Global Telecommunications Conference (GLOBECOM 2011). Dec. 2011 (cit. on p. 57). [Jan+14] Minsung Jang, Karsten Schwan, Ketan Bhardwaj, Ada Gavrilovska, and Adhyas Avasthi. “Personal clouds: Sharing and integrating networked resources to enhance end user experiences”. In: 33rd Annual IEEE International Conference on Computer Communications (INFOCOM’14). Toronto, Canada: IEEE, Apr. 2014, pp. 2220–2228 (cit. on p. 21). [Jim+13] Javi Jiménez, Roger Baig, Pau Escrich, Amin M Khan, Felix Freitag, Leandro Navarro, Ermanno Pietrosemoli, Marco Zennaro, Amir H Payberah, and Vladimir Vlassov. “Supporting cloud deployment in the Guifi.net community network”. In: 5th Global Information Infrastructure and Networking Symposium (GIIS 2013). Trento, Italy: IEEE, Oct. 2013 (cit. on p. 85). [KBF15] Amin M Khan, Umit Cavus Buyuksahin, and Felix Freitag. “Incentive-based resource assignment and regulation for collaborative cloud services in community networks”. In: Journal of Computer and System Sciences 81.8 (Dec. 2015), pp. 1479–1495 (cit. on pp. 33, 49). [KBF14] Amin M Khan, Umit Cavus Buyuksahin, and Felix Freitag. “Prototyping Incentive-Based Resource Assignment for Clouds in Community Networks”. In: 28th IEEE International Conference on Advanced Information Networking and Applications (AINA 2014). Victoria, Canada: IEEE, May 2014, pp. 719–726 (cit. on pp. 40, 48). [KBF13] Amin M Khan, Umit Cavus Buyuksahin, and Felix Freitag. “Towards Incentivebased Resource Assignment and Regulation in Clouds for Community Networks”. In: Economics of Grids, Clouds, Systems, and Services. Ed. by Jörn Altmann Altmann, Kurt Vanmechelen, and Omer F. Rana. Vol. 8193. Lecture Notes in Computer Science. Zaragoza, Spain: Springer International Publishing, Sept. 2013, pp. 197–211 (cit. on pp. 36, 48). 93 [KF14a] Amin M Khan and Felix Freitag. “Exploring the Role of Macroeconomic Mechanisms in Voluntary Resource Provisioning in Community Network Clouds”. In: 11th International Symposium on Distributed Computing and Artificial Intelligence (DCAI 2014). Vol. 290. Advances in Intelligent Systems and Computing. Salamanca, Spain: Springer International Publishing, June 2014, pp. 269–278 (cit. on p. 84). [KF14b] Amin M Khan and Felix Freitag. “Sparks in the Fog: Social and Economic Mechanisms as Enablers for Community Network Clouds”. In: ADCAIJ: Advances in Distributed Computing and Artificial Intelligence Journal 3.8 (2014) (cit. on pp. 22, 84). [Kha+15a] Amin M Khan, Felix Freitag, Smrati Gupta, Victor Muntés-Mulero, Jacek Dominiak, and Peter Matthews. “On Supporting Service Selection for Collaborative Multi-Cloud Ecosystems in Community Networks”. In: 29th IEEE International Conference on Advanced Information Networking and Applications (AINA 2015). Gwangju, Korea, Mar. 2015 (cit. on p. 85). [KFN16] Amin M Khan, Felix Freitag, and Leandro Navarro. “Community Clouds”. In: Encyclopedia of Cloud Computing. Ed. by San Murugesan and Irena Bojanova. Wiley-IEEE, June 2016 (cit. on pp. 20, 26, 84). [Kha+16a] Amin M Khan, Felix Freitag, Leandro Navarro, and Roger Baig. “Enabling Clouds in Community Networks”. In: European Project Space on Research and Applications of Information and Communication Systems. Ed. by Carlos Cerqueira and James Uhomoibhi. Lisbon, Portugal: SCITEPRESS, 2016 (cit. on p. 85). [KFR15] Amin M Khan, Felix Freitag, and Luis Rodrigues. “Current Trends and Future Directions in Community Edge Clouds”. In: 4th International Conference on Cloud Networking (CloudNet 2015). Niagara Falls, Canada: IEEE, Oct. 2015 (cit. on pp. 21, 27, 84). [KSF14] Amin M Khan, Mennan Selimi, and Felix Freitag. “Towards Distributed Architecture for Collaborative Cloud Services in Community Networks”. In: 6th International Conference on Intelligent Networking and Collaborative Systems (INCoS 2014). Salerno, Italy: IEEE, Sept. 2014 (cit. on p. 27). 94 [Kha+13] Amin M Khan, Leila Sharifi, LeandroNavarro, and Luis Veiga. “Clouds of Small Things: Provisioning Infrastructure-as-a-Service from within Community Networks”. In: 2nd International Workshop on Community Networks and Bottom-up- Broadband (CNBuB 2013), within IEEE WiMob. Lyon, France: IEEE, Oct. 2013, pp. 16–21 (cit. on p. 85). [Kha+16b] Amin M Khan, Xavier Vilaça, Luis Rodrigues, and Felix Freitag. “A Distributed Auctioneer for Resource Allocation in Decentralized Systems”. In: 36th IEEE International Conference on Distributed Computing Systems (ICDCS 2016). Nara, Japan, June 2016 (cit. on p. 82). [Kha+15b] Amin M Khan, Xavier Vilaça, Luis Rodrigues, and Felix Freitag. “Towards Incentive-Compatible Pricing for Bandwidth Reservation in Community Network Clouds”. In: 12th International Conference on Economics of Grids, Clouds, Systems, and Services (GECON 2015). Cluj-Napoca, Romania: Springer International Publishing, Sept. 2015 (cit. on pp. 54, 82). [KA06] Samee Ullah Khan and Ishfaq Ahmad. “Non-cooperative, semi-cooperative, and cooperative games-based grid resource allocation”. In: 20th International Parallel and Distributed Processing Symposium (IPDPS 2006). IEEE, 2006 (cit. on p. 15). [Kri09] Vijay Krishna. Auction Theory. Academic Press, 2009, p. 336 (cit. on p. 15). [Lai+04] Kevin Lai, Lars Rasmusson, Eytan Adar, Stephen Sorkin, Li Zhang, and Bernardo A. Huberman. “Tycoon: an Implementation of a Distributed, Marketbased Resource Allocation System”. In: Multiagent and Grid Systems 1.3 (Dec. 2004), pp. 169–182 (cit. on pp. 9, 10, 14, 15, 53). [Lee+07] Seungjoon Lee, Dave Levin, Vijay Gopalakrishnan, and Bobby Bhattacharjee. “Backbone construction in selfish wireless networks”. In: ACM SIGMETRICS Performance Evaluation Review 35.1 (2007), p. 121 (cit. on pp. 9, 10). [Leo13] Xavier Leon. “Economic regulation for multi tenant infrastructures”. PhD Thesis. Universitat Politècnica de Catalunya, 2013 (cit. on p. 10). [Li+13] Hongxing Li, Chuan Wu, Zongpeng Li, and Francis C. M. Lau. “Profitmaximizing virtual machine trading in a federation of selfish clouds”. In: 32nd IEEE International Conference on Computer Communications (INFOCOM’13). Turin, Italy: IEEE, Apr. 2013, pp. 25–29 (cit. on p. 14). 95 This thesis was typeset using L A T EX, originally developed by Leslie Lamport and based on Donald Knuth’s T EX. The body text is set in 11 point Minion Pro, designed by Robert Slimbach in 1990 inspired by late Renaissance-era type and issued by Adobe in 2000. The headlines and captions are set in variations of Myriad Pro, a humanist sans-serif typeface designed by Robert Slimbach and Carol Twombly in 1990 and issued by Adobe in 2000. The above illustration was created by Ben Schlitter and released under cc by-nc-nd 4.0. A template that can be used to format a PhD dissertation with this look &feel has been released under the permissive agpl license, and can be found online at github.com/aminmkhan/Dissertate or from its lead author, Jordan Suchow, at sucho[email protected]vard.edu.