Title

Task Distribution With A Random Overlay Network

Keywords

Commodity computers; Grid computing; Routing

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.

Publication Date

5-1-2006

Publication Title

Future Generation Computer Systems

Volume

22

Issue

6

Number of Pages

676-687

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.future.2005.11.004

Socpus ID

33646160204 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/33646160204

This document is currently not available here.

Share

COinS