Method for multiclass task allocation

Embodiments of the invention include a method of selection of server in a system including at least one dispatcher and several servers, in which system when a new task of a given class arrives, then the dispatcher assigns the task to one of these servers, characterized that the selection of the servers by the dispatcher is based on the MIPN (Multiclass Idle Period Notification) information, which is sent by the servers to the dispatcher.

BACKGROUND

Various distributed server systems consist of service nodes and dispatchers, which assign arriving tasks to one of the service nodes. Many task assignment policies have been already proposed, which differ in system state estimation, decision making and policy objectives.

DETAILED DESCRIPTION

In this description we consider the task assignment problem in a distributed server system, consisting of multiclass tasks, multiserver nodes and dispatchers, which assign arriving tasks to service nodes. We propose new dynamic Multiclass Idle Period Notification policy, in which each service node only needs for each class to notify dispatchers on the start of every idle period. We demonstrate by simulation that this policy performs as well as Shortest Expected Delay policy, which requires immediate knowledge of the state of each node at the time of every arrival.

In various embodiments, a distributed server system includes service nodes and dispatchers, which assign arriving tasks to one of service nodes. Many task assignment policies have been already proposed, which differ in system state estimation, decision-making and policy objectives. An important element of a task assignment policy is the information it requires to operate. Dynamic task assignment policies use the knowledge of the current global state information to distribute the workload among servers. Typically if a new task arrives at time t, a load index ri(t) is evaluated for each server i. The server that yields minimum load index is selected to execute the task. For example, in the Shortest Expected Delay (SED) policy, the load index is the expected response time to complete new task. It is estimated using formula ri(t)=mi(si(t)+1), where si(t) is the number of tasks at server i including the one in service at time t of arrival, and miis the mean service time.

For many distributed systems it is unrealistic to have immediate knowledge of the system state information and dispatchers distribute tasks using stale information. Several authors examine the task assignment with stale information. It was found that task assignment policies can have extremely bad behavior when state information is out of date. New task assignment policies which outperform SED when use old information were proposed. In Idle Period Notification (IPN) policy, servers send special control messages to notify dispatcher of start of every idle period. Dispatchers use idle period notifications to balance the amount of work assigned to each server during its current busy period. IPN policy uses small amount of state information but performs as well as SED policy.

In this description we generalize IPN policy to distributed systems with multiple dispatchers, multiserver nodes and multiclass tasks. We propose new Multiclass Idle Period Notification (MIPN) policy, in which selection of the nodes by the dispatcher is based on the MIPN information sent by the nodes to the dispatcher. MIPN information is sent by a node each time it becomes free from the tasks of a particular class, and contains at least the identification of that node and the identification of that class. The dispatcher keeps record of the times it has received the last MIPN for each class and node. Dispatcher defines the start time of the current busy period of a node for a class as the moment when the first task of that class is sent by the dispatcher to the node after it has received from that node the last MIPN information related to that class. Dispatcher defines the end time of the current busy period of a node for a class as the moment when dispatcher receives from the node new MIPN information related to that class. The length of a busy period of a node for a class is calculated as the difference of the end time and the start time of that busy period.

Dispatcher calculates the amount of work assigned to the node during the current busy period of a node for a class as the sum of the amount of work associated with each task of that class assigned to the node during the current busy period of the node for that class. Arriving task is assigned by dispatcher to the node with the smallest amount of work assigned to the node by that dispatcher during the current busy period of the node for the class to which arrived task belongs.

We demonstrate by simulation that this policy performs as well as Shortest Expected Delay policy, which requires immediate knowledge of the state of each node at the time of every arrival.

Multiclass Idle Period Notification Policy

Consider a distributed system100, consisting of N service nodes and M dispatchers, which assign tasks to service nodes (seeFIG. 1). Each service node can be either single server queue or multiserver queue or may have more complex internal structure. Tasks are divided into K classes, where one or more classes of tasks may have priority over other classes. Tasks within a given class are executed in FIFO order. We denote Dc,nthe set of all dispatchers, which may send class c tasks to node n. Tasks of a class c arriving to a dispatcher d requires a service at one node nεSc,d, where Sc,dis the set of all service nodes available to class c tasks from dispatcher d.

In proposed MIPN policy when class c task departs the node n and there is no other class c tasks in the node n it sends the idle period notification IPN(c, n) to all dispatchers dεDc,nWe define a busy period of type (c, d, n) as follows. Busy period of type (c, d, n) begins when dispatcher d directs first, after receiving IPN(c,n), class c task to node n. It ends when dispatcher d receives next IPN(c,n) (seeFIG. 2, diagram200).

Each class c task forwarded to a node nεSc,dis characterized by a nonnegative weight wc,d,n, which may depend of the time t of task arrival. For each class c and node n dispatcher dεDc,ntries to balance the aggregate weight of class c tasks assigned to node n during current busy period of type (c, d, n). It maintains load index Wc,d,n, which is set to wc,d,n, at time t=0 and also each time, when dispatcher d receives idle period notification IPN(c,n). In MIPN policy if a new task of class c arrives to a dispatcher d, then the node nεSc,dthat yields minimum load index Wc,d,n, is selected to execute the task. After forwarding class c task to node n, dispatcher d increments load index Wc,d,nby wc,d,n.

Behavior of MIPN policy is determined by the weights wc,d,n, which can be specified either statically or dynamically. Dispatcher can accommodate task assignment policy to changes in traffic conditions by dynamically changing weights. Dispatchers use idle period notifications for. calculation of the length of busy periods. of different types and the number of tasks assigned to each node during busy periods.

τ⁢(j)c,d,n
be the length of j-th busy period of type (c,d,n) and

v⁢(j)c,d,n
be the number of tasks sent by dispatcher d to node n during this busy period. After completion of j-th busy period of type (c,d,n) the weight wc,d,nis updated using exponentially weighted average given by

wc,d,n(j)=(1-α)⁢wc,d,n(j-1)+α⁢τc,d,n(j)vc,d,n(j),0<α<1.(1)
Updated value wc,d,n(j)of the weight wc,d,nis used for assignment of tasks arriving during (j+1)-th busy period of type (c,d,n).

EXAMPLES WITH SIMULATION

We simulate two different systems, which differ in the variability of the processing rates of the servers. The first system, System1, consists of 10 single server nodes. The processing rates of the servers of System1form an arithmetic series, that is
rn=3n/11, n=1,2 . . . 10.
System 1 has an aggregate processing rate of 15. The second system, System2, has 8 single server nodes, and the processing rates of the servers form the geometric series
rn=2n−i, n=1, 2 . . . 8.
Its aggregate processing rate is equal to 255.

Tasks are divided into C priority classes, where the class1tasks have the highest priority, class2tasks the second highest priority and so on. Tasks of class c arrive to the system from a Poisson source with rate λc=λ/C, where λ is the total task arrival rate. Each server is available to tasks of any priority class. The tasks within a given priority class are executed in FIFO order before servicing those of lower priority classes. Once started, each task is executed to completion without interruption; i.e., there is no preemption. We compare MIPN policy with Shortest Expected Delay (SED) policy. In SED policy if a new class c task arrives at time τ for each server n the expected response time to complete new task is estimated as

rc,n⁡(t)={mc,n+∑i=1c⁢si,n⁡(t)⁢mi,n,∑i=1c⁢si,n⁡(t)>0,mc,n+mpn⁡(t),n,∑i=1c⁢si,n⁡(t)=0,∑i=c+1C⁢si,n⁡(t)>0,mc,n,∑i=1C⁢si,n⁡(t)=0.(2)
Here mi,nis the mean service time of class i tasks at node n, Si,n(t) is the number of class i tasks at node n including the one in service at time τ of arrival and

pn⁡(t)=mini⁢(si,n⁡(t)>0)
is the priority of a task at service at node n. The server that yields minimum expected response time is selected to execute the task.

We consider cases with constant and exponentially distributed service times.FIG. 3including diagrams300andFIG. 4including diagrams400show for each priority class the average response times under SED and MIPN policies versus server utilization ρ. Performance of proposed MIPN policy is slightly worse at low utilizations, but in high load conditions MIPN outperforms SED.

TECHNICAL EXAMPLES

Let us consider a communication network where datagrams are routed and the routing decisions are made by edge routers. The class of a datagram can be the application type to which the datagram is related. To optimize the routing in the network the routing decisions by the edge routers can be based on MIPN.

Let us consider a health center patient workflow. The arriving patients are sent to examining doctors, and before the examination the patients may be prepared by nurses or visit the laboratory. The patient class can be the type of special problem she or he has. The routing of arriving patients to examining doctors can be based on MIPN.

In a microprocessor system tasks to be processed are sent to the processors by preprocessors. The MIPN policy can be applied so that the preprocessors are considered as dispatchers and the processors as nodes.