Task distribution with a random overlay network

    Authors

    L. Boloni; D. Turgut;D. C. Marinescu

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Futur. Gener. Comp. Syst.

    Keywords

    grid computing; commodity computers; routing; GRIDS; Computer Science, Theory & Methods

    Abstract

    We consider a model where commodity service providers are offering commodity computational services to a set of customers. We provide a solution for the efficient distribution of tasks by forwarding the service requests on an overlay network comprised on random cycles. We introduce algorithms for the creation, maintenance and repair of the overlay network. We discuss two algorithms, random wandering and weighted stochastic forwarding, for the allocation of the tasks to providers. Both approaches are highly scalable because the algorithms use only limited local information. As we are designing our approach for use in a commercial setting, there is a requirement that the tasks, being a source of profits, be allocated fairly to the providers. We investigate the fairness of the algorithms and show that adding a random pre-walk can improve the fairness. Through a simulation study we show that the approach provides efficient task allocation on networks loaded up to 95% of their capacity. Published by Elsevier B.V.

    Journal Title

    Future Generation Computer Systems-the International Journal of Grid Computing Theory Methods and Applications

    Volume

    22

    Issue/Number

    6

    Publication Date

    1-1-2006

    Document Type

    Article

    Language

    English

    First Page

    676

    Last Page

    687

    WOS Identifier

    WOS:000237905500003

    ISSN

    0167-739X

    Share

    COinS