The simulation of a distributed control model for resource allocation and the implied pricing

ABSTRACT

The allocation of computing resources and the scheduling of tasks in a multitasking environment are simulated using a distributed control model. The tasks compete for computing resources in a decentralized manner through sealed bid auctions to improve their schedules, rather than having resources centrally administered by a host controller. Funds used for bidding are endowed to the tasks upon arrival at the computing system. The effects on completion times of three endowment strategies and two machine sizes are analyzed using a range of system capacities. Within each capacity class, an apparent cost, derived from the run parameters, is contrasted with an implied price generated by the auction process. Performance is examined in terms of congestion at various capacities. At optimal (lowest cost per successful completion) rates of occurrence of these capacity classes, an implied price arises that exceeds the “free access” price. This internally generated price appears to ration resources and time, thus discouraging congestion. Implementing such a distributed control algorithm suggests that determining a price schedule for allocating computing resources can be moved “to the left” in the system life cycle.

REFERENCES

• 1: Peter J. Denning , Jeffrey P. Buzen, The Operational Analysis of Queueing Network Models, ACM Computing Surveys (CSUR), v.10 n.3, p.225-261, Sept. 1978 [doi>10.1145/356733.356735]
• 2: Martin D. Fraser , Ross A. Gagliano, Mathematical modeling and Ada simulation of some synchronization processes, Proceedings of the 20th annual symposium on Simulation, p.163-184, June 1987, Tampa, Florida, United States
• 3: Gagliano~ R. A., M. D. Fraser and M. E. Schaefer. 1987. "A Market Model for Distributed Control: The Role of Algorithms for the Initial Endowment of Wealth," Presented at (and to appear in the Proceedings of) the International Symposium on Systems Research, Informatics and Cybernetics, Baden-Baden, West Germany (Aug.).
• 4: Ross A. Gagliano , Martin D. Fraser , Mark E. Schaefer, Simulation of a market model for distributed control, Proceedings of the 21st annual symposium on Simulation, p.171-187, January 1988, Tampa, Florida, United States
• 5: R. W. Hockney , C. R. Jesshope, Parallel Computers Two: Architecture, Programming and Algorithms, IOP Publishing Ltd., Bristol, UK, 1988
• 6: Haim Mendelson, Pricing computer services: queueing effects, Communications of the ACM, v.28 n.3, p.312-321, March 1985 [doi>10.1145/3166.3171]
• 7: M R Railey, Dynamic control structures for cooperating processes, University of Illinois, Department of Computer Science, Urbana, IL, 1986
• 8: Randall Jay Raynor, Minimization of supervisor conflict for multiprocessor computer systems., 1974
• 9: Zimmerman, W.F. (Jet Propulsion Laboratory). 1988. Personal communication, 21st Annual Simulation Symposium, Tampa, FL, (March).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed

General Terms:
Design, Measurement, Performance, Theory