L. Bölöni, D. Turgut, and D. C. Marinescu

Task distribution with a random overlay network


Cite as:

L. Bölöni, D. Turgut, and D. C. Marinescu. Task distribution with a random overlay network. Future Generation Computer Systems (Elsevier), 22(6):676–687, Elsevier, 2006.

Download:

Download 

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 source of profits, to 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.

BibTeX:

@article{Boloni-2006-FGCS,
   author = "L. B{\"o}l{\"o}ni and D. Turgut and D. C. Marinescu",
   title = "Task distribution with a random overlay network",
   journal = "Future Generation Computer Systems (Elsevier)",
   year = "2006",
   volume = "22",
   number = "6",
   pages = "676-687",
   publisher = "Elsevier",
   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 source of profits, to 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.
},
}

Generated by bib2html.pl (written by Patrick Riley, Lotzi Boloni ) on Tue Nov 07, 2017 13:11:27