网络感知负载均衡Network-AwareLoadBalancing

1、Schedule First, Manage LaterWei WangWei WangNetwork-Aware Load BalancingAmir Nahir, Ariel Orda, and Danny RazPresented byLoad balancingLoad balancing in large distributed server system is a complex optimization problem.Critically important in Cloud systems and data centers.Supermarket ModelThe super

2、market model is a queueing network consisting of servers and independent arrival streams to sets of servers. QnQ3Q2Q1At arrival each job is routed to a server from its set where it queues until it is processed and it then departs from the system. The main interest is to study the behavior/efficiency

3、 of the system under various simple routing rules, for example join-the-shortest-queue.ProblemsRegardless of the exact optimization criterion,Common load balancing approaches such as the Supermarket Model, invoke data collection process data collection process upon a jobs arrival. This in turn intro

4、duces a delaydelay in the execution of the job.ChallengeMinimizing the time a job spends till be assigned to a server.Scaling well and being suitable for contemporary data centers.Our schemeDuplicate each job request into several replicas.Send them to randomly chosen servers(FCFS).QnQ3Q2Q1When a rep

5、lica arrives to the head of the queue and begins processing, a signal is sent to the other corresponding servers.Other servers remove corresponding replica.SimulationFirst-come-first-served M/M/N systemsPoisson arrival exponentially distributed service times.Ignore the signaling transmission delay.A

6、ssumptionsAssumptions: :Simulation setup:Simulation setup:A system of 100 servers100,000 jobs(average of 25)Simulation resultsThe proposed scheme offers high value across all loads compared to the basic random assignment policy.d=2 by a factor of 9.4d=3 by a factor of 19.9d=5 by a factor of 47.4The

7、effect of delayIt takes time for the removal message to arrive from one server to the other.It is possible for both replicas of the same job to complete execution at different servers before any removal signal arrives.The effect of delayThe average queuing overhead rises with the signal propagation

8、delay and the number of copies.Addressing delaysReplicas of the same job often reach the heads of the queues in the servers roughly at the same time, causing redundant processing and delaying other jobs.We need to modify the job selection policy of the servers. Location-in-vector selectionA list of

9、servers of the same jobs replicas.When a server completes the processing of some job and is required to select the next job from its queue for processing, the server would select, among the first k jobs, the job that holds the present servers identity in the highest location. Location-in-vector selectionAverage queuing overhead with location in vector selectionWhen the value of k is kept small(i.e.,k=2,3) the queuing overhead drops sharply.As the value of k grows, the effect of changing k levels off,