Distributed Resource Allocation for Contributory Systems

Author

Vilajosana Guillén, Xavier

Director

Marquès Puig, Joan Manuel

Date of defense

2009-03-13

Legal Deposit

B.29056-2009



Department/Institute

Universitat Oberta de Catalunya. Internet Interdisciplinary Institut (IN3)

Abstract

La tesis presenta una aproximació a un conjunt de tècniques per permetre l'extensió de les capacitats computacionals, sota demanada, en comunitats formades per usuaris d'Internet que volen agregar els seus recursos per aconseguir una finalitat comuna. Aquest tipus de comunitats, emergeixen com a noves formes d'organització gràcies a l'increment de les capacitats computacionals i l'ampla de banda. La computació voluntaria com la que es dona en sistemes com SETI@home, Grids col.laboratius com OurGrid o LaCOLLA, Ad-hoc i Grids d'igual a igual com P-Grid o X-Grid d'Apple, Grids Oberts com els adreçats per SORMA o Grid4All i moltes d'altres formes de computació Grid basades en agrupació de recursos en forma d'Organitzacions Virtuals són l'objectiu d'aquest treball. Aquests sistems es caracteritzen pel propòsit dels seus participants, és a dir, dur a terme un objectiu comú fent ús de l'agregació dels sesus propis recursos. Els sistemes esmentats, contrariament als sistemes Grid d'alt rendiment computacional, són oberts a nous participants fet que els converteix en escenaris inpredictibles, dinàmics i on els recuros poden connectar-se i desconnectar-se de forma espontànea. Mentre que l'aspecte crític dels Grids d'altes prestacions és el rendiment computacional, l'estabilitat i la disponibilitat són els aspectes més importants en els sistemes adrec cats en aquest treball. La tesis homogeinitza els conceptes dels paradigmes anteriors sota el nom de Sistemes Contributius, nom que és usat al llarg de la dissertació per referir-nos a sistemes en els quals els seus usuaris fan contribució dels seus recursos per tal que aquest siguin usats de forma col.lectiva i axií aconseguir un objectiu comú. L'expansió de recursos en els Sistemes Contributius és una funcionalitat requerida per tal de augmentar les limitades capacitats computacionals dels grups col.laboratius formats de forma ad-hoc. Sobretot en moments puntuals quan els recursos necessaris són majors que els disponibles en el grup. Quatre aspectes s'adressen al llarg de la dissertació. Primer, les propietats i principals applicacions dels Sistemes Contributius són identificades, així com es motiva la necessitat d'infraestructures que permetin l'expansió de recursos computacionals sota demanda. Aquestes idees van en la direcció de l'Utility Computing, emergents línies de negoci de les principals companyies de la IT. D'aquesta manera, la tesis proposa la provisió de recursos computacionals sota demanda a aquelles organitzacions que en necessitin, mitjanc cant l'agregació de recursos dels extrems d'Internet, ja siguin usuaris finals de la xarxa, altres organitzacions virtuals o proveidors de recursos. En aquest treball, l'assignació de recursos es gestionada per models de mercat ja que proveixen de mecanismes eficients i simples per gestionar l'assignació de recursos. Aquesta proposta aporta noves oportunitats als usuaris finals d'Internet per tal d'establir el seu negoci a la xarxa mitjanc cant la venda dels seus recursos no usats. A més a més aquest treball dona l'oportunitat a communitats petites a creixer i a portar capacitats de super-computació als usuaris finals d'Internet. En segon lloc, la tesis descriu semànticament els recursos computacionals per tal de constru"ir una base comú de coneixement sobre els recursos d'Internet. La descripció semàntica dels recursos permet un enteniment comú de la naturalesa dels recursos, permetent així l'agrupació i agregació de diferents tipus de tecnologíes mentre es mantenen la mateixa semàntica. Una base semàntica comú permet que aplicacions i sistemes de gestió de recursos siguin independents de la naturalesa real dels recursos. En aquest treball considerem com a aspecte fonamental aillar la gestió dels recursos de la seva naturalesa específica. La descripció semàntica a més permet el desenvolupament de especificacions genèriques que ens permeten definir els requeriments dels usuaris en sistemes d'assignació de recursos basats en mercats computacionals. Tercer, arquitectures que permeten l'expansió de recursos computacionals sota demanda en Sistemes Contributius són presentades. Aquestes arquitectures han estat especialment dissenyades per prove"ir de recursos computacionals mitjanc cant mercats a escenaris caracteritzats pel dinamisme, evolució i heterogene"itat dels seus recursos. L'arquitectura aporta les principals funcionalitats orientades a l'assignació de recursos mitjanc cant subhastes i permet a més a més l'execució d'aquests mercats sota demanda. Finalment, es presenta un mecanisme de mercat adaptat a l'assignació de recursos computacionals. Aquesta contribució es motiva pel fet que no existeix fins avui cap mecanisme que permeti l'assignació efficient de recursos computacionals en que la seva única diferència és la unitat de temps en la que s'ofereixen. La tesis construeix un camí per assolir l'expansió de recursos computacionals de forma flexible i decentralitzada en comunitats on els recursos són compartits pels seus participants. Aquest camí es construeix mitjanc cant l'anàlisis dels escenaris d'aplicació, l'estudi i definició de models semàntics que permeten la descripció dels recursos computacionals, proposant també arquitectures flexibles i configurables que permeten aconseguir l'expansió dels recursos computacionals sota demanda i proposant mecanismes de mercat adaptats a tal escenari.


The thesis presents an approach to on-demand capacity expansion in communities of Internet users that aggregate their resources to achieve a common objective. Such commu- nities are emerging as forms of organisation taking advantage of an increasing broadband access and computational capacity. Volunteer computing such as SETI@home, Collab- orative Grids such as OurGrid and LaCOLLA, Ad-hoc and Peer-to-Peer Grids, such as P-Grid and the XGrid project from Apple, Open Grids such as those addressed by SORMA and Grid4All and many other approaches of Grid Computing based on Virtual Organisa- tions are the focus of our work. These systems are characterised by the purpose of their participants, i.e. to achieve a common objective taking advantage of the aggregation of other resources. The cited systems, in contrast to high performance computing Grids, are open to new participants, which makes their behaviour unpredictable and dynamic, and resources are usually connected and disconnected spontaneously. While the critical aspect of high performance Grids is computational performance, stability and availability are the main issues for the systems addressed in this work. The thesis homogenises the concepts of those paradigms under the term Contributory System, which is used throughout the thesis to refer to the systems where users provide their resources to be used collectively to achieve a common objective. Resource expan- sion in Contributory Systems is required so as to increase the limited capacities of ad-hoc collaborative groups under unexpected load surges, temporary resource requirements or other policies defined by the objectives of the Virtual Organisation that they constitute. Four aspects are addressed by the dissertation. Firstly, it identifies the main properties and applications of Contributory Systems and motivates the need for infrastructures to enable on-demand resource expansion. This goes in the direction of Utility Computing trends which are main business lines for IT companies. Thus the thesis proposes the on-demand provision of idle resources from the extremes of the Internet, other Virtual Or- ganisations or Resource Providers to those organisations that have resource needs. In this work, resource allocation is handled by market models which provide efficient while simple mechanisms to mediate the allocation of resources. This proposal enables new emerging opportunities to Internet users to make their business on the Internet by selling their idle resources. Besides, this brings the opportunity to small communities to grow and to bring super-computing capacities to Internet end-users. Secondly, the thesis describes semantically Computational Resources so as to build a common knowledge about the Internets resources. The semantic description enables a common understanding of the nature of resources, permitting the pooling and aggrega- tion of distinct types of technologies while maintaining the same semantics. This makes applications and resource management frameworks independent of the real nature of the resources which we claim as a fundamental aspect to keep resource management indepen- dent of the dynamics and evolution of technology in computational environments, such as in Contributory Systems. A semantic description permits the development of generic specifications to provide bid and offer descriptions in computational markets. Thirdly, the architecture for on-demand resource expansion in Contributory Systems is presented. It has been designed to provide the main functionalities to on-demand provi- sion of resources through markets to scenarios characterized by dynamism, evolution and heterogeneity. The architecture provides the main market oriented functionalities and en- ables dynamic and on-demand execution of market mechanisms. Finally, a specific Grid-oriented market mechanism is presented. The approach is moti- vated due to the unsuitability of current auctions to efficiently allocate time-differentiated resources (usually provided by many different resource providers) such as most of the re- sources in a Contributory System. The thesis builds a roadmap to achieve flexible and decentralized resource expansion in communities where resources are shared by their participants by analysing the main scenarios where it can be applied, providing the semantics and specification to enable the description of the user's requirements, proposing a flexible and configurable architecture to deal with on-demand resource expansion in Virtual Organisations and proposing an specific mechanism adapted to trade computational resources.

Keywords

Grid Computing; Models economics; Assignació de recursos computacionals

Subjects

004 - Computer science and technology. Computing. Data processing

Knowledge Area

0.75

Documents

Thesis_Xavi_Vilajosana.pdf

5.647Mb

 

Rights

ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.

This item appears in the following Collection(s)