FI118167B - Procedure for assigning data - Google Patents

Description

ί 118167: - <5, 1 ί

METHOD OF ALLOCATION OF TASKS

SUMMARY

5 Performance optimization is needed to effectively manage many modern information and communication technology-based systems.

Such systems include, for example, telecommunications networks, data processing centers or workflow systems. An important part of optimization is the dynamic allocation of tasks between servers.

10 This discussion discusses the division of tasks into a server cluster, where each server has a different processing capacity. We are introducing a new dynamic IPN (Idle Period Notification) method where each server - only needs to announce its release to the task distributor. By simulation, we show that this method works just as well as the Minimum Response Time policy 15, which requires immediate knowledge of the status of each server at the time each task arrives at that server. The advantage of the IPN method is that it does not affect server execution time.

. sl SEARCH TERMS: decentralized system, task sharing • · · 20

: '. 0 INTRODUCTION

The task routing method is an important component that affects the performance of the system, as it coordinates the processing capacity of the servers ··· • · · ··· 1. High-speed Web clusters [1] and Internet routers [2] employ a variety of task routing methods. Job Routing Methods • 1 · ': ¾:' also applies to optimizing business transactions and workflow management. | * ·; · 1 An important part of defining a routing method for tasks is the information it needs to * 1 · • 'm · operate. In general, dynamic methods use time-dependent information and; • · 1 1 ϊ.,. Ϊ 30 static methods for time-independent system information [3].

* · »·« · • · · # # • • 118167 I, '| 2

We look at the problem of distribution of tasks in a server cluster, where servers have different service processing times. Tasks arrive at the Task Distributor, who is responsible for distributing them to the FIFO servers, following a task distribution method that takes into account resource availability on the servers. We are interested in 5 methods that minimize the average service time for all tasks.

An important part of the task distribution method is the information it needs to function.

Static methods use time-independent information about the system, such as task arrival intensity and probability distribution of task service times. i

Typically, it is assumed that the task arrival process is Poisson-distributed. Buzen '£ 10 and Chen [4] led to optimal yield intensities A, · for servers in a server cluster with common service time distributions. Ni and Hvang [5] developed a closed form solution in the case of service times that are exponentially distributed.

Tantawi and Towsley [6] study an arbitrarily distributed distributed system.

In it, tasks can arrive on any server and can be served either locally or forwarded to another server. They derived an iterative algorithm that defines the optimal static assignment method, which was later developed by Kim and Kameda [7]. - 'i *

Dynamic task distribution methods utilize the current 5 global system status information to distribute the load between servers. In a typical case, when a new task arrives at time t, the associated cost function c, (0. The server with the lowest value of ♦ · • · is selected to perform the task. For example, in the Minimum Response Time Policy (MRT), the cost function is the expected value of the new task ί · 2 ··; 3 · the service time estimated by the formula = + O // 7;, where i ', (0 «·· 25 is the number of tasks on server z including current / incoming task and / 1 /

: ·· is the processing intensity of the server [8]. However, it is unrealistic to assume that I

· T j? the actual task distributor would be able to obtain the current global status information. | j · 2 · 1: In reference [9], Mitzenmacher has investigated various types of obsolete state information f • 2.

: 3: models applied to a cluster of identical servers assuming exponential service processing times for '30 tasks. In the periodic update model, the global status information λ • φ • 1 · 2 • ··. /.1 3 ♦ · Z? i 118167: 3 '- Refreshed every T seconds. In this case, the MRT method will work poorly unless T is very small due to the herd phenomenon: all tasks arriving between two measurement moments are routed to the same server. Methods that use only a small amount of state information can work better. A method of selecting the 5 shortest service times from two randomly selected servers has been found to work very well. In the continuous update model, the global state information is constantly updated, but is X seconds behind the actual state at all times of arrival, where X is a random variable independent of all tasks. If X is a fixed constant T, then the system applying the continuous update model works in the same way as if it were using the periodic update model 10. Instead, if X is exponentially or: i, 4 evenly distributed random variables, the results are much better. f

.-V

There is still an open question about how much data and what refresh rate is sufficient to ensure good performance. In this description, we propose a new dynamic IPN (Idle Period Notification) method in which each server 15 need only notify its release to the task distributor (Figure 1). We show that this method works just as well as the MRT method, which needs instant information on the status of each server at each moment that tasks arrive on the servers.

IPN METHOD • • f:: 20 * * *; * · *; In the proposed IPN (Idle Period Notification) method, each server

• · 'S

· * · * · Informs the Task Distributor of its release by sending its server identifier • · ·; ··· (ID). Task Distributor can use these notifications to calculate ··· duration of busy periods, number of tasks assigned to servers as busy periods, and 25 service processing speeds, unless otherwise known.

• · j In general, it is quite difficult to calculate the exact response time expectancy using * * i as a starting point for realized server busy periods and the number of tasks assigned to them. Suppose a new task arrives at the server at time t.

• · * 30 Consider the current busy period of the server, and for the sake of simplicity - * · · assume that it starts at time 0 and that a total of N tasks have arrived before • · · · 118167 -4 ^ 4 j ·: | | moments. It is known that the wait time wr of the FlFO server task r implements Lindley's equation wr + i = (wr + br -ar) +, where br is the service time of the task, ar is the time interval between the arrival of tasks r and r + 1, and x + = x , if x> 0, and otherwise jc + = 0 [10]. Since all tasks that arrive at intervals (CU) have a wait time other than zero, their service times and arrival intervals follow the following inequalities; Σ *, ·> Σ «/. For 1- = 1,2 ... ^,: / = 1 / = 1 f- and the exit time for N + \ from the service is given by 1 N + 1:

δΝ + \ = Yubi · I

i 1. .

^ It follows that the exact conditional expectation value f of the task arriving at time t, provided its sequence number is iV + 1 for that busy time,; can be calculated from equation j

N r r N

dN + \ (t) = J ~ + E (YJbi \ Xbi> Zai'r = l'2-N'Xai = th μ <= i / = i / = ii = i; t4 # where // is the processing received by the task -intensity.

* · • ·. *** 15 Instead of waiting time for response time, we propose a much simpler * · * cost function. In the proposed IPN method, the Task Distributor attempts to make the workloads of ♦ * '\ all servers equal within the current busy period of each server. Define 7 / (/) by the formula 7 / (0 = sup {r </ 1 s / (r) = 0} f where • * · ·: s, (r) is the number of jobs on the server / at time f. (/) is the beginning of the current busy period of server i 20, if busy at t, otherwise 7 / (/) = /.

•] * Let Nj (t) be the number of tasks assigned to the server i in the interval [7) (/), t). If a new • · • ♦ task arrives at /, then the task distributor redirects it to /, which | ! . * value of cost function V C {(0 = MUl • 'Mi ··· «· * ♦ *, ·,; 25 is the smallest.

• »· •« i 118167 Λ 1): '5 SIMULATION1MARKS

We simulated three different systems using the Poisson arrival process as in Reference [11], and compared the MRT and IPN methods.

5 The first system, called System 1, has 10 nodes. The processing intensities of the nodes are μ \ = 6, μ2 = ... = μιο = 1. In another system,

In System 2, there are also 10 nodes. The processing intensities of the nodes follow the '• Ä' /, 0 arithmetic sequence according to the formula Mi-3 tt, / = 1,2 ... 10. Each sv ι / y / ·% of these systems has a total processing intensity of 15. The third system, System 3, has 8 nodes and their processing intensities follow 10 geometric sequences μ; · = 210 - <, / = 1.2. .10. i

Figures 2 to 3 show the average response times of the processed tasks. S

MRT (solid lines) and IPN (dotted) tasks.? 15 as a function of arrival intensity λ. Assuming exponentially distributed service times in systems, we can also calculate the average response times (dashed lines) of the optimal static method. As expected, both dynamic task assignment methods provide better performance than the optimal i ***** static method. Surprisingly, the proposed IPN method works just as well as the MRT method even under heavy load, with very long charge times,

CONCLUSIONS

* · · ··· 1 ........... ....... ... ..... .......

• · · \ .. 1 In this description, we introduce a dynamic task allocation method that appears to use 25 least resources. In the proposed IPN (Idle Period Notification) - »· •“ method, each server sends only one status update • · * ♦ ·· 1 to the task distributor per busy period - when the IPN notification is released - and: ·· · '%! • it contains the server information (ID) as the only information. However,> »» · The IPN method operates over a very wide system parameter range, •. ·? ····· '<· * · 1' · * 1 · '···' • 1 6 118167

Another advantage of this method is that IPN notifications are sent when servers become available. Therefore, the iPN method does not load servers with their ·.

while processing tasks.

5 REFERENCES

[1] V. Cardellini and E. Casalicchio. State of the Art in Locally Distributed Web-Server Systems, ACM Computing Surveys, Vol. 34, No. 2, June 2002, p. 263- 311. 1 K3 [2] O. Younis and S. Fahmy. Constraint-Based Routing in the Internet: Basic

Principles and Recent Research, IEEE Communications Surveys, Vol. 1, 2003, p. 2-13.

[3] T.L. Casavant and J.G. Kuhl. The Taxonomy of Scheduling in General-Purpose:

Distributed Computing Systems, IEEE Transactions on Software Engineering, Vol.

15 14, No. 2, February 1988, p. 141-154. '-' ··; [4] J.P. Buzen and P.P.-S, Chen, Optimal Load Balancing in Memory Hierarchies, in

Information Processing 74, J.L. Rosenfeld, Ed., New York: North-Holland, p. 271- | 275.1974.

[5] L.M. Ni and K. Hwang, Optimal load balancing in a multiple processor system it · ·.

* ··· * 20 with many job classes ”, IEEE Transactions on Software Engineering, vol. 11, no. 5, · :; • ·: -V 1985, pp. 491-496.

♦ · · f '· | [6] A.N. Tantawi and D. Towsley, "Optimal Static Load Balancing in Distributed Computer Systems," Journal of A CM, vol 32, no. 2, p. 445-465, Apr. 1985.

«* · [7] C. Kim and H. Kameda," An Algorithm for Optimum Static Load Balancing in * · * · '25 Distributed Computer Systems, "IEEE Transactions on Computers, vol. 41, no. 3, p.

381-384, March 1992.

[8] Y.C. Chow and W.H. Kohler, "Models of Dynamic Load Balancing in a • · • · Heterogeneous Multiple Processor System." IEEE Transactions on Computers, vol. C- ♦ · ·: V 28, no. 5, p. 354-361, May 1979.

* * 'Yl * ·· «* M [9] M. Mitzenmacher," How useful is old information? ". IEEE Transactions on *: **: Parallel and Distributed Systems, vol 11, no. 1, p. 6-20 Jan. 2000. - • · • * · · · 1181816 [10] D.V., Lindley, "On the Theory of Queues with a Single Server," Proc.

Cambridge Philosophical Society, vol 48, p. 277-289, 1952.

[11] S.A. Banawan and N.M. Zeidat, "Comparative Study of Load Sharing in ± Heterogeneous Multicomputer Systems", Proc, 25th Annual Simulation Symposium, 5 Orlando, Florida, USA, pp. 22-31, Apr. 6-9, 1992.

> *; '; 1 ··· • · * »• ♦ · · 1 • 1 ··.

• · · • ·

• · »A

♦ · · • 1 • 1 «· t ·« * • · · • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • «t ί

·· I

• · ♦ 1 • · · ♦ ** ** ** ** «« ** **,,,,, 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Claims (4)

1. A method of selecting the service point in a system containing at least one task distributor and multiple service points, in which a new incoming task is referred to one of these service points specified by the task distributor, and in which the choice of service points provided by the task distributor, depends on the IPN (Idle Period Notification) the information that the service points send to the task distributor each time the service points become vacant, and which IPN information contains at least the identification of the service points, characterized by the fact that the workload associated with the service points during its present reservation period is all information that has been * referred to the service points during the current reservation period. ϋ,; t! A 2. A method according to claim 1, characterized in that the task distributor 15 refers the new task to the service location, which has the least referenced?, The workload during its current reservation period. - | 3. A method according to claims 1-2, characterized in that if ... the data distributor does not know the workload of data, it can approximate | • e · · "; j, 20 workload associated with a service location by multiplying the amount of |. ♦ 4. # tili service points referred data with the average service time at ί • *.. * * · Service locations. ···· • · • · · • 'T. ···. 4. A method according to claims 1-3, characterized in that the average service time at the service points can be approximated by the data distributor by calculating the average of sub-phases, which are phased by dividing the length. of • · ♦ * .1 ·. the reservation period with the amount of information at the service points during • · ·. ·. reservation period. !; • · ♦ • · * ··· #. · ·· ♦ 30 ··· • · * · • · · ·. · • * · • *