Work Planning: Market-based and Corresponding Sharing

1610 days ago, 606 views
PowerPoint PPT Presentation
Creates heuristics for booking and confirmation control in business sector based lattice undertaking administration ... monotonically on solicitation dispatch occasions, however may not progress on each dispatch ...

Presentation Transcript

Slide 1

Work Scheduling: Market-based and Proportional Sharing Richard Dutton CSci 780 – P2P and Grid Systems November 22, 2004

Slide 2

Importance Computing and capacity assets are being shared among numerous clients Grids, utility figuring, "group utilities" Sharing can enhance asset effectiveness and adaptability and bring additionally registering influence Difficulty comes in controlling asset use

Slide 3

Outline Market-based structure Motivation/Problem Characteristics of approach Interposed Proportional Sharing Goals Methodology Experimentation/Results Conclusions Discussion

Slide 4

Market-based approach

Slide 5

Motivation Grids empower sharing of assets Users have entry to more assets Resource use must be parleyed for contending requests Both sides (asset supplier and buyer) must profit Provider – successful worldwide utilization of assets Consumer – decency, unsurprising conduct, control over relative need of occupations

Slide 6

Motivation(2) Why advertise based approach? Expansive size of assets and members in Grid Varying free market activity Market-based approach is great in light of the fact that Provides decentralized asset administration Selfish purchasers prompt to worldwide objective User completes occupations rapidly, suppliers proficiently assign assets Laissez faire

Slide 7

Ideas from clump frameworks Batch frameworks fuse: User need Weighted corresponding sharing SLAs for setting limits on accessible assets Additionally, advertise based approach will utilize relative earnestness and cost of employments

Slide 8

Value-based framework Value-based (here and there called client driven) planning permits clients to characterize an esteem (yield or utility) to every occupation System is attempting to augment add up to estimation of employments finished as opposed to just meeting due dates or achieving a specific throughput Users offer for assets and pay with the esteem (v alue  cash) System offers to most noteworthy "bidder" to expand benefits

Slide 9

Risk versus Compensate Focus here is planning in matrix benefit locales Since cost is gotten from finishing time, scheduler must think about length of an assignment with its esteem and opportunity cost What this implies: scheduler must adjust the danger of conceding an undertaking with the reward of booking the errand

Slide 10

Example: Market-Based Task Service Tasks are bunch calculation occupations Self-contained units of work Execute anyplace Consume known assets Tasks give some esteem upon consummation Tasks connected with esteem work – gives esteem as capacity of culmination time

Slide 11

Example: Market-Based Task Service Characteristics of a market-based errand benefit Negotiation amongst clients and suppliers Value ��  cost and nature of administration ��  fulfillment time Form contracts for assignment execution Not meeting terms of the agreement suggests a punishment Consumers search for the best arrangement and every site endeavors to amplify its benefits

Slide 12

Market Framework Bid (esteem, benefit request) Accept (fruition time, value) Accept (contract) Customer Bid (esteem, benefit request) Reject Bid (esteem, benefit request) Accept (culmination time, value) Reject Task Service Sites

Slide 13

Goals Develop approach decisions for the assignment benefit destinations to augment benefits Acceptance – affirmation control Scheduling Use esteem metric to adjust hazard and reward in offering and planning Not worried with coin supply, evaluating frameworks, motivation components, installment…

Slide 14

Value capacities Negotiation amongst site and bidder builds up concurrence on cost and QoS Value work maps benefit quality (culmination time) to esteem Want the definition to be "straightforward, rich, and tractable" Generalization of direct rot esteem capacities from Millenium Expresses how estimation of errand corrupts with time – rot i

Slide 15

Maximum Value Runtime Value Penalty Time Value work

Slide 16

Decisions Which errands to concede? At the point when to run a conceded errand? Wish to augment benefit How much ought to an errand be charged? In view of significant worth capacities Must discover most noteworthy estimated undertakings and reject those which don't meet some base levels

Slide 17

Experimental Methodology Simulator to permit offering and calendar as indicated by an errand benefit economy with straight esteem capacities Use manufactured follows that are illustrative of genuine bunch workloads Compare against FirstPrice from Millenium Concerned with relative execution and affectability examination of utilizing quality and rot

Slide 18

Risk/Reward Heuristics Discounting Future Gains Leans toward shorter assignments – more averse to be appropriated Realizes acquires rapidly with short assignments – chance loath scheduler Opportunity Cost – considers the slant of rot Leans toward more dire undertakings If all undertakings must be finished, it is best to finish most critical assignments first

Slide 19

Discounting Future Gains Based on Present Value from fund PV i = yield i/(1 + (discount_rate * RPT i )) PV i can be considered as speculation esteem Interest is earned at discount_rate for Remaining Processing Time ( RPT ) High discount_rate causes the framework to be more hazard disinclined Heuristic called PV chooses occupations all together of marked down pick up PV i/RPT i

Slide 20

Improvement for PV

Slide 21

Opportunity Cost Extended heuristic to represent misfortunes from circumstance cost Loss in income from picking some errand i before errand j Opportunity cost to begin i is given by total loss of all other contending errands Bounded punishments require O(n 2 ) time Unbounded punishments registered in O(log n)

Slide 22

Balancing Gains and Opportunity Cost It is hazardous to concede picks up from high-esteem errand construct exclusively in light of chance cost Solution: FirstReward compensate i = (( α )*PV i – (1-α )*cost i )/RPT i The α parameter controls how much framework considers expected increases α =1 and discount_rate =0 decreases FirstReward to PV

Slide 23

Bounded Penalties Shows it is more imperative to consider costs than additions ��  low alpha Most viable around α =.3

Slide 24

Unbounded Penalties Shows it is ONLY essential to consider costs, not picks up Magnitude of enhancements much more noteworthy

Slide 25

Negotiation Client submits assignment offers Site acknowledges/rejects offer If site acknowledges, it consults to set a cost and fruition time

Slide 26

Admission Control Steps for proposed assignments Integrate assignment into competitor plan as indicated by FirstReward Determine yield for the errand if acknowledged Apply acknowledgment heuristic to decide adequacy If tolerating, issue an offer to the customer If customer acknowledges the agreement, put undertaking into timetable to execute Acceptance heuristic in light of measure of extra defer the undertaking can permit before its esteem falls underneath some yield edge

Slide 27

Summary of Market-based Services Develops heuristics for booking and affirmation control in market-based lattice errand benefit Value-based planning permits client to indicate the esteem and criticalness of the employment Maximizing client esteem thusly amplifies yield all inclusive Approach in light of computational economy

Slide 28

Interposed Proportional Sharing

Slide 29

Overview This paper manages share-based planning calculations for separated administration in system administrations, specifically capacity benefit utilities Allows a server to be imparted among numerous demand streams to some probabilistic certification of getting some base share of assets

Slide 30

Situation Sharing of assets must be reasonable SLA's regularly characterize legally binding commitments amongst customer and administration

Slide 31

Goals of This Research Performance confinement A surge from one stream ought not debase the execution of another stream Differentiated application benefit quality Performance ought to be unsurprising and configurable Non-meddling asset control Designed to work without changes to existing administrations, similar to business stockpiling servers Views server as a discovery Control server assets remotely

Slide 32

Idea in Words As the name recommends, the thought is to mediate a demand scheduler between the customer and server The scheduler will capture solicitations to the server Depending on the demand and condition of past solicitations, it will postponement, reorder, or basically dispatch the demand

Slide 33

Idea in Pictures

Slide 34

Interposed Request Scheduling Scheduler catches demands Dispatches as per a few arrangements trying to decently share assets among all streams Parameter D limits greatest number of extraordinary demands Each stream has isolate line Scheduler dispatches from every line on FIFO premise

Slide 35

Related Approaches Façade proposes an intervened ask for scheduler that utilizations Earliest Deadline First(EDF) Drawback: out of line – can't give execution disengagement Uses need booking to accomplish detachment SLEDS – per-customer organize connector Uses defective basin channel to shape and throttle I/O streams Not work-rationing

Slide 36

Proportional Sharing Proposes 3 corresponding sharing calculations SFQ( D ) – Start-time Fair Queuing FSFQ( D ) – Four-label Start-time Fair Queuing RW(D) – Request Windows which are general and configurable arrangements that give Performance seclusion Fairness Work-conservation

Slide 37

Fair Queuing Each stream is alloted a weight Φ f Resources designated among dynamic streams in extent to weight A stream is dynamic in the event that it has no less than 1 remarkable demand Fair: Proven property jumping distinction in work accomplished for any match of dynamic streams (slack) Work-monitoring: surplus assets devoured by dynamic streams without punishment

Slide 38

Start-time Fair Queuing Start-time Fair Queuing(SFQ) is the reason for the booking calculations because of reasonableness SFQ relegates a tag to every demand upon entry and dispatches the solicitations in rising request of labels Fairness comes from strategy for figuring and appointing labels

Slide 39

SFQ Assigns a begin tag and complete tag for every demand Start label: Finish label: Defines a framework thought