M.Sc Thesis

M.Sc StudentSimionovici Aviv
SubjectAllocation of Computational Resources in a Network Using
Economic Metaphors
DepartmentDepartment of Industrial Engineering and Management
Supervisor PROF. Roy Friedman


In this work we cope with the problem of locating servers among Internet hosts. We have to install I servers on J hosts. Every two hosts are interconnected by a link with a specific delay and data transfer cost. A server can be installed on any number of hosts. Each host has a finite amount of Computational Power Units which it partitions to its installed servers. An installed server makes use of its computational power portion to serve its jobs. A job enters the system through a host, and picks a server from the installed ones. It has a computation length attribute defining how much time it will take it to compute on a server with 1 unit of computational power and a communication length attribute defining how much time it will take to pass a link. A particular server allocation to hosts is measured with the mean job service ratio criteria. We present a new dynamic distributed mechanism, that allocates both jobs to servers and servers to hosts, to solve the problem. Our mechanism is based on economic paradigms. We form 3 markets: (1) Service Time market with jobs as consumers and servers as producers; (2) Communication Bandwidth market with jobs as consumers and hosts as producers; (3) Computational Power market with servers as consumers and hosts as producers. We define the markets rules, the auctions that we use and the regulations we impose. We show how theses definitions lead to the problem solutions.