Categorizing researches about DLT in Ten groupsAmin Shokripour

Department of Communication Technology and NetworkUniversity Putra Malaysia

43400 UPM Serdang, Selangor D.E., MalaysiaShokripour@gmail.com

Mohamed OthmanDepartment of Communication Technology and Network

University Putra Malaysia43400 UPM Serdang, Selangor D.E., Malaysia

mothman@fsktm.upm.edu.my

Abstract—During the last decade, using parallel and dis-tributed system has been more general. In these systems ahuge size of data or computation is distributed between manysystems for getting better performance. Dividing data is one ofthe challenges in parallel and distributed system. One of proposedmethod for managing data distribution is called Divisible LoadTheory (DLT). Ten reasons for using DLT have been mentioned.Many researches have been done in this field from 1988 to now.One or some of characteristics of DLT have been attended in eachresearch and some of researchers proposed new parameters. Webelieve all the researches can be categorized in ten categoriesbased on ten reasons for using DLT presented by Robertazzi.For a novice researcher in this field, it is necessary to knowimportant parameters and previous researches so in this paperwe presented some of earlier researches in ten categories.

Index Terms—Divisible Load Theory (DLT), Scheduling, Grid,Survey, Ten reasons.

I. INTRODUCTION

Two models for scheduler are presented, resource modeland job model. Different methods have been proposed ineach model. In this paper we will discuss about one of thesemethods called Divisible Load Scheduling (DLS) based onDivisible Load Theory (DLT). In below we will talk about it indetails. Different methods have been proposed in each model.In this paper we will discuss about one of these methods calledDivisible Load Scheduling (DLS) based on Divisible LoadTheory (DLT). Over the past decade or more a new mathe-matical tool has been created to allow tractable performanceanalysis of systems including both communication and com-putation issues, as in parallel and distributed processing. A keyfeature of this divisible load scheduling theory is that it usesa linear mathematical model. Thus, as in other linear models,such as a Markovian queuing theory of electric resistive circuittheory, divisible load scheduling theory is rich in such featuresas easy computation, a schematic language, equivalent networkelement modeling, and numerous applications [48].

In divisible load scheduling theory, it is assumed thatcomputation and communication loads can be partitionedarbitrarily among a number of processors and links, respec-tively. Moreover, the theory of divisible load scheduling isfundamentally deterministic [48].

Many researches have been done in this field from 1988to now [47]. Each research attended to one or some ofcharacteristics of this method and some of them proposedsome new parameters. We believe all the researches can be

categorized in ten categories based on ten reasons for usingDLT presented by Robertazzi [49]. For a novice researcherin this field, it is necessary to know important parametersand previous researches so we collected and categorizedresearches. Although in this article we will investigate recentresearches in DLT, we can not ignore fundamental documents,books and articles [12], [53], [48], [8].

The rest of the paper includes our categories and presentedpaper in each of them. Last section is conclusion.

II. CATEGORIZING DID RESEARCHES

DLT has some characteristics lead to use this method indifferent areas. Ten of these reasons are presented in [49] byRobertazzi. In remain of this paper we will discuss about thesereasons and present some of researches. In each subsection,at the first we will state mentioned reason by Robertazzi andthen present researches in that reason.

A. A tractable model

The optimality principle provides the key to divisible loadscheduling. Setting up a continuous-variable model and as-suming that all processors stop computing at the same instantlets you determine the optimal amount of total load to assignto each processor or link using a set of linear equations or, asin queuing theory and many other cases, recursive equations.

For having better scheduling, one of proposed techniquesis resource reservation. Some of researchers tried to use thismethod in DLT based scheduling [35], [38], [2]. A multi-stagereal-time divisible load scheduling algorithm that supportsadvance reservations was proposed in [35]. The novelty ofthis algorithm is that it reserved blocks on both computingnodes and the communication channel.

Main goal of some researches is to present a closed formulafor finding size of assigned load to each worker [5], [33],[39]. In a real system we should use a formula which supportsHeterogeneity. One of the best formulas for distributing datain a heterogeneous system can be found in [39].

In opposite of [53]’s result, in some cases of using DLT,it is not necessary to complete all jobs at the same time tohave the minimum time. Given that the network bandwidthon a single channel is limited, link aggregation techniques areemployed to provide multiple physical links from a source tothe destination. Its possible use in link striping had not beenexplored before [64]. As required for packet transmission over

2009 IACSIT Spring Conference

978-0-7695-3653-8/09 $25.00 © 2009 IEEE

DOI 10.1109/IACSIT-SC.2009.54

45

2009 International Association of Computer Science and Information Technology - Spring Conference

978-0-7695-3653-8/09 $25.00 © 2009 IEEE

DOI 10.1109/IACSIT-SC.2009.54

45

multiple channels, DLT has to be tuned to consider sequentialordering of the packet transmission times. As suggested bythe DLT literature, it is necessary and sufficient that all theparticipating channels finish transmission at the same timeinstant. Authors of [64] shown all channels complete trans-mission at the same time and thus intend to deliver packets tothe receiver simultaneously. Such a simultaneous completionpattern causes concurrent data delivery at the receiver due tothe competition of the single shared input port. Thus, instead ofletting all the channels complete transmission simultaneously,they proposed a sequential completion pattern to ensure in-order data delivery at the receiver.

In [51], the problem of minimizing the processing timeis investigated when the computation time for each node isnonlinear in the size of the assigned load fraction and linearcommunication model with and without overhead delays.Finally A closed-form solutions for the load fractions assignedto the processors and the processing time are derived from thenonlinear recursive equations.

B. Interconnection topologies

Over the years, researchers have successfully applied di-visible load modeling to a wide variety of interconnectiontopologies, including linear daisy chains [55], [54], [52], [59],trees [42], [66], [23], [3], [39], [51], [15], buses [24], [22],[27], hypercubes, and two-and three-dimensional meshes [65].Star topology as a common topology in small networks wasexplored in [17], [16]. The ability to guarantee performanceclose to that of an infinite-sized network with a small to mod-erate number of processors therefore provides useful designinformation.

Cluster computing has emerged as a new paradigm forsolving large-scale problems. To enhance QoS and provideperformance guarantees in cluster computing environments,various real-time scheduling algorithms and workload modelshave been investigated. [32] investigates DLT based schedulingalgorithms for a cluster environment. Design parameters thataffect the performance of these algorithms and scenarios whenthe choice of these parameters have significant effects arestudied. Some of other researches about applying DLT oncluster are [35], [10], [18].

Studied network topologies are not limited to wired net-work. Some researches in applying DLT on wireless networkswere done. One of these researches is [21]. In this paper, theyproposed architecture of mobile-to-Grid gateway for support-ing two kind of e-Health application and DLT based algorithmfor scheduling data distribution on wireless devices. An otherresearch in this field was presented in [25]. Start of DivisibleLoad Theory was for solving sensor networks communicationproblems. Recently some researches have been done on sensornetworks [30], [29], [28], [40]. The main problem in most ofthese researches is power resource limitation.

Other type of investigated media is optical transporter. Thefamous project for this type of transporter is called Lambdagrid. In [45], the on-line hierarchical scheduling on a lambda

Grid of workload approaching the Grid’s capacity in a two-tier Grid mode of operation is studied. Some other researchesabout applying DLT on optical networks have been done [46].

Addition to network topologies, in some researches otherparameters of network have been studied. For example in[4], authors considered divisible load scheduling under arealistic communication model, where the master node cancommunicate simultaneously to several slaves, provided thatbandwidth constraints are not exceeded. Also they proved thatscheduling divisible load under the bounded multi-port modelis NP-complete.

C. Equivalent networks

Like other linear theories, including Markovian queuingtheory and resistive electric circuit theory, DLT represents acomplex network with an exactly equivalent network element.For some network topologies such as trees, aggregation canbe recursive, one sub tree at a time.

In [66], a universal resource model described by a hybridmulti-level tree for grid computing based on dynamic andheterogeneous networks was presented. Then a method ofreducing the complex multi-level tree to a single level treeusing divisible load theory is presented. Other useful researchin this field is [23].

D. Installments and sequencing

A number of applied optimization problems arise in di-visible load scheduling. Performance under sequential multi-installment load distribution strategies tends to saturate as thenumber of installments increases.

One of the basic algorithm for multi round schedulingcalled Uniform Multi-Round Scheduling (UMR)[62]. UMRuses uniform chunk size in each round. This leads to anear-optimal number of rounds, on both homogeneous andheterogeneous platforms.

Scheduling is a complex task in grid systems. When weuse multi round methods, it is more complex. In multi-roundscheduling, load is sent to each worker as several chunks ratherthan as a single one. Authors of [63], stated and established anoptimality principle in the general case. Also they established anew complexity result by showing that a DLS problem, whosecomplexity has been open for a long time, is in fact NP-hard,even in the one-round case.

In [55] a method used to calculate the optimal numberof installments required in a linear network topology witharbitrarily processor release time was presented and also derivesome important conditions to ensure that the load will be ableto be processed in a finite number of installments.

An extended version of parallel transferable uniform multi-round algorithm [60], which efficiently mitigated impact byallowing chunks to be transmitted in parallel to workers inhomogeneous environments is proposed in [61].

Some other researches in multi round/installment schedulingare [34], [24], [13], [14], [31].

In [39], an optimal sequence of divisible workload onheterogeneous system is discussed. He presented and approved

4646

some theorems about sequence of load distribution in differentconditions. The simplest of them can be seen below.

E. Scalability

DLT studies determined that if load is distributed from onenode to its children sequentially speedup saturates as morenodes are added. Although simply increasing the number ofinstallments also saturates performance, studies indicate thatspeedup is scalable if a node transmits load simultaneously toall its children.

Authors of [36] attended to a different side of Scalability ofDLT. However, only a few authors have explored the simulta-neous scheduling of multiple Divisible Load applications ona distributed computing platform [37].

Theorem: Scheduling of multiple divisible loads is NP-hardeven for two identical processors. You can find an approve forthis theorem in [15].

F. Metacomputing accounting

A devilish metacomputing problem -distributed computingwith payment to computer owners- challenges developers tofactor problem size and system parameters into monetaryaccounting. DLT can incorporate an intuitive linear model forcomputing and communication costs. Simple to moderatelycomplex heuristic rules can be developed to efficiently assignload in terms of both cost and performance.

DLT requires a high degree of cooperation between thevarious processors. If we assume that these processors areowned and operated by independent organizations, these or-ganizations along with the job owners must from a coalitionin order to execute the job and to achieve profits. In the casesin which the players cooperate, we use cooperative insteadof noncooperative game theory. Because of the high degree ofcooperation needed among the players, authors of [7] proposedthat the divisible load scheduling problem is better examinedusing coalitional instead of noncooperative game theory.

G. Time-varying modeling

The actual effort a computer can devote to a divisible jobdepends on the status of other background jobs. Developerscan use integral calculus to apply solution-time optimization todivisible loads if they know the start and end times and effortof such background jobs and messaging. With less than perfectknowledge of background processes, stochastic modeling canbe combined with deterministic DLT.

Authors of [9] tried to minimize average turn around time bydispatching tasks to processors with smallest communicationratio. System throughput could be also enhanced by dispersingprocessor idle time.

The purpose of [34] is to develop an efficient multi roundmodel which helps estimate the available computing powerof a worker under the fluctuation of the number of local andGrid applications. Based on this model, they proposed the CPUpower prediction strategy.

Other research in this field is [56]. In this work, authorsproposed Resource-Aware Dynamic Incremental Scheduling

(RADIS) strategies for situations wherein processing for sev-eral divisible (partitionable) loads need to be completed withintheir respective deadline requirements, while the processingnodes have finite capacity constraints and capacity of memoryis varying with time.

H. Unknown system parametersIt can be difficult to obtain accurate estimates of available

processor effort and link capacity, key inputs to divisible loadscheduling models. Actual implementations must account forthe time-varying nature of available processor effort and linkcapacity as well as processors’ release times. Further, loadmust be distributed on the fastest processors and links.

The problem of minimizing the total processing time of adivisible load on a tree network, without any prior knowledgeof processor speeds and link speeds was considered in [23].They explored two distinct cases of practical interest. Whenthe speeds of the nodes and links do not fluctuate and whenthe speeds of the nodes and links vary with time. This work isthe first attempt of its kind to consider the combined influenceof unknown and time-varying speed parameters.

In real systems, usually resources are not dedicated to gridcomputing so real power of them is unknown. In [27], authorsaddressed the problem of scheduling multiple divisible loadswith unknown network resources and presented some newefficient strategies that provides complete flexibility with lessreality constraints.

An adaptive scheduling method, which can be used forparallel applications whose total workload is unknown a prioriwas presented in [5]. Another article in this field is [6]. In [54],a strategy for scheduling divisible loads on linear networks,when speeds of the computing nodes and the communicationlinks are unknown a priori was proposed.

Traditional DLT does not comprehensively deal with thescheduling of results back to source. In [20], the DLS withResult Collection on HETerogeneous Systems problem is ad-dressed. All papers that had addressed result collection before[20], had advocated simplistic LIFO and FIFO sequences orvariants thereof as solutions. In this paper, a new heuristicalgorithm, ITERLP, was proposed. The ITERLP heuristic al-gorithm finds a solution by iteratively solving linear programs.

I. Extending realismResearchers have attempted to generalize divisible load

scheduling by considering systems with finite buffers, finitejob granularity, scheduling with processor release times, andscheduling multiple divisible loads.

One of the old researches on processor with differentavailable time is [55]. In this research, authors assumed whenthe job is ready to do, minimum required processors for doingit is not available. With attention to this assumption theypresented a method for scheduling job in this type of systems.Some years later, an article, [19], presented and shown, withan example, this method does not always produce a solution.

Other research in this field was presented in [33]. In thisresearch, authors discussed about scheduling job with differ-ent processor available time. Other research on distributing

4747

arbitrarily parallelizable real-time workloads among proces-sors which become available at different instants is [11]. In[10], about scheduling jobs when processors available time isvarying, in clusters, is discussed.

It often happens that load can be generated from multiplesources. Authors of [42] attended to this property of real sys-tem. For solving problems of scheduling data in a system withmultiple source, some methods were presented. One of thesemethods which consider a ”pullbased” strategy, wherein theprocessing nodes request load from the sources, was presentedin [57]. Authors employed the Incremental Balancing Strategy(IBS) algorithm and propose a buffer estimation strategy toderive optimal load distribution. Other papers in this field are[50], [56].

Buffer limitation is another parameter which has directaffect on scheduling. In [13] authors studied multi-installmentdivisible load processing in a heterogeneous distributed systemwith limited memory. The load chunk sizes must be adjusted tothe speeds of communication, computation, and memory sizes,such that the whole processing time is as short as possible.They proposed a new realistic model of memory management.Other paper about limitation in memory is [17].

J. Experimental results

Experiments with actual distributed computer systemsdemonstrate that DLT can be a useful prediction tool.

In most documents DLT was compared with markov chainmodel. In [41], the equivalence between various divisible load-scheduling policies and continuous time Markov chains isdemonstrated. This provides a basic unification of both dataparallel divisible load scheduling and Markov chain modelsfor the first time in 16 years of research.

Authors of [26], compared performance of scheduling byDLT to Genetics Algorithm in data grid systems. After doingexperiments, they show performance of GA is better than DLTbased algorithms. In [44], an adaptive divisible load modelwas proposed. Authors used result of this paper to improveperformance of GA algorithm. [1] exploited AGA approach forscheduling divisible data in data grid. The proposed approachconsequently enhances the performance of AGA in termsof both makespan and execution time. In [43] researchersimproved their first model and presented an improvement ofADLT model. Then they shown performance of this algorithmis better than the GA algorithm. An other research for com-paring performance of DLT to GA was presented in [58].

III. CONCLUSION

Ten reasons for using DLT have been presented by Rober-tazzi. These reasons are the most complete set of this method’scharacteristics. During the last years many researches havebeen done about DLT and applying it in different applications.In this paper we tried to categorize did researches based oneach character of this method attended in each article. Surelythis categorization is not absolute and other researchers maycategorize researches otherwise. Certainly in each researchmany parameters have been studied but in classification, we

categorize base on main investigated parameter. Our collec-tion show that earlier researches have focused on unknownparameter of system, time varying attributes and realism.

REFERENCES

[1] M. Abdullah, M. Othman, H. Ibrahim and S. Subramaniam, ”An In-tegrated Approach for Scheduling Divisible Load on Large Scale DataGrids,” Lecture Notes in Computer Science (4705), 2007, pp. 748-757.

[2] K. Aida and H. Casanova, ”Scheduling mixed-parallel applications withadvance reservations,” 17th international symposium on High perfor-mance distributed computing, 2008, pp. 65-74.

[3] S. Bataineh, ”Divisible Load Distribution in a Network of Processors,”Journal of Interconnection Networks (JOIN), vol. 9, 2008, pp. 31-51.

[4] O. Beaumont, L. Eyraud-Dubois and N. Bonichon., ”Scheduling divisible-workloads on heterogeneous platforms under bounded multi-port model,”IEEE International Symposium on Parallel and Distributed Processing,2008, pp. 1-7.

[5] S.-S. Boutammine, D. Millot and C. Parrot, ”An Adaptive SchedulingMethod for Grid Computing,” Lecture Notes in Computer Science (4128),2006, pp. 188-197.

[6] S.-S. Boutammine, D. Millot and C. Parrot, ”Dynamically SchedulingDivisible Load for Grid Computing,” Lecture Notes in Computer Science(4208), 2006, pp. 763-772.

[7] T. E. Carroll and D. Grosu, ”Divisible Load Scheduling: An ApproachUsing Coalitional Games,” Sixth International Symposium on Parallel andDistributed Computing, 2007, pp. 36-44.

[8] Y. C. Cheng and T. G. Robertazzi, ”Distributed computation with commu-nication delay,” IEEE Transactions on Aerospace and Electronic Systems,vol. 24, 1988, pp. 700-712.

[9] H. Ching-Hsien, C. Tai-Lung and P. Jong-Hyuk, ”On improving resourceutilization and system throughput of master slave job scheduling inheterogeneous systems,” J. Supercomput., vol. 45, 2008, pp. 129-150.

[10] S. Chuprat and S. Baruah, ”Scheduling Divisible Real-Time Loads onClusters with Varying Processor Start Times,” 14th IEEE InternationalConference on Embedded and Real-Time Computing Systems and Ap-plications, 2008, pp. 15-24.

[11] S. Chuprat, S. Salleh and S. K. Baruah, ”Evaluation of a linearprogramming approach towards scheduling divisible real-time loads,”International Symposium on Information Technology, 2008, pp. 1-8.

[12] M. Drozdowski, ”Selected Problems of Scheduling Tasks in Multipro-cessor Computer Systems,” Poznan University of Technology Press, 1997.

[13] M. Drozdowski and M. Lawenda, ”A New Model of Multi-installmentDivisible Loads Processing in Systems with Limited Memory,” LectureNotes in Computer Science (4967), 2008, pp. 1009-1018.

[14] M. Drozdowski and M. Lawenda, ”On Optimum Multi-installment Di-visible Load Processing in Heterogeneous Distributed Systems,” LectureNotes in Computer Science (3648), 2005, pp. 231-240.

[15] M. Drozdowski and M. Lawenda, ”Scheduling multiple divisible loadsin homogeneous star systems,” Concurrency and Computation: Practiceand Experience, vol. 19, 2007, pp. 2237-2253.

[16] M. Drozdowski and M. Lawenda, ”Scheduling multiple divisible loadsin homogeneous star systems,” Concurrency and Computation: Practiceand Experience, vol. 19, 2008, pp. 2237-2253.

[17] M. Drozdowski and P. Wolniewicz, ”Optimum divisible load schedulingon heterogeneous stars with limited memory,” European Journal ofOperational Research, vol. 172, 2006, pp. 545-559.

[18] L. Duc, D. Jitender and G. Steve, ”Feedback scheduling of real-timedivisible loads in clusters,” SIGBED Rev., vol. 5, 2008, pp. 1-4.

[19] M. Gallet, Y. Robert and F. e. e. Vivien, ”Comments on ”Design andperformance evaluation of load distribution strategies for multiple loadson heterogeneous linear daisy chain networks”,” J. Parallel DistributedComputing, vol. 68, 2008, pp. 1021-1031.

[20] A. Ghatpande, H. Nakazato, H. Watanabe and O. Beaumont, ”DivisibleLoad Scheduling with Result Collection on Heterogeneous Systems,”IEEE International Symposium on Parallel and Distributed Processing,2008, pp. 1-8.

[21] Y. Han, C.-H. Youn, T. M. Trung, W.-S. Kim and L. Zhang, ”OptimalLoad Scheduling Mechanism and a Mobile-to-Grid Gateway Model fore-Health Service in Wireless Grid,” Sixth IEEE International Conferenceon Computer and Information Technology, 2006, pp. 54-60.

[22] J. Hu and R. Klefstad, ”Scheduling Divisible Loads on Bus Networkswith Start-Up Costs by Utilizing Multiple Data Transfer Streams: PORI,”International Conference on Parallel Processing, 2007, pp. 23-31.

4848

[23] J. Jia, B. Veeravalli and D. Ghose, ”Adaptive Load Distribution Strate-gies for Divisible Load Processing on Resource Unaware Multilevel TreeNetworks,” IEEE Transactions on Computers, vol. 56, 2007, pp. 999-1005.

[24] H. Jie and R. Klefstad, ”Scheduling Divisible Loads on Bus Networkswith Arbitrary Processor Release Time and Start-Up Costs: XRMI,”Performance, Computing, and Communications Conference, 2007, pp.356-364.

[25] K. Katsaros and G. C. Polyzos, ”Optimizing operation of a hierarchicalcampus-wide mobile grid,” 18th Annual IEEE International Symposiumon Personal, Indoor and Mobile Radio Communications, 2007.

[26] S. Kim and J. B. Weissman, ”A Genetic Algorithm Based Approachfor Scheduling Decomposable Data Grid Applications,” InternationalConference on Parallel Processing, 2004, pp. 406 - 413.

[27] H. Li, G. Sun and Y. Xu, ”Distributed Scheduling Strategies for Process-ing Multiple Divisible Loads with Unknown Network Resources,” IFIPInternational Conference on Network and Parallel Computing Workshops,2007, pp. 824-829.

[28] X. Li, H. Kang and J. Cao, ”Coordinated Workload Scheduling inHierarchical Sensor Networks for Data Fusion Applications,” Journal ofComputer Science and Technology, vol. 23, 2008, pp. 355-364.

[29] X. Li, H. Kang and H.-H. Chen, ”Sensing workload scheduling inhierarchical sensor networks for data fusion applications,” internationalconference on Wireless communications and mobile computing, 2007,pp. 214 - 219.

[30] X. Li, X. Liu and H. Kang, ”Sensing Workload Scheduling in SensorNetworks Using Divisible Load Theory,” The 50th Annual IEEE GlobalTelecommunications Conference, 2007, pp. 785-789.

[31] X. Lin, Y. Lu, J. Deogun and S. Goddard, ”Multi-Round Real-TimeDivisible Load Scheduling for Clusters,” 15th International Conferenceon High Performance Computing, 2008, pp. 196-207.

[32] X. Lin, Y. Lu, J. Deogun and S. Goddard, ”Real-Time Divisible LoadScheduling for Cluster Computing,” 13th IEEE Real Time and EmbeddedTechnology and Applications Symposium, 2007, pp. 303-314.

[33] X. Lin, Y. Lu, J. Deogun and S. Goddard, ”Real-Time Divisible LoadScheduling with Different Processor Available Times,” Proceedings of the2007 International Conference on Parallel Processing, 2007.

[34] N. T. Loc and S. Elnaffar, ”A Dynamic Scheduling Algorithm forDivisible Loads in Grid Environments,” Journal of Communications, vol.2, 2007, pp. 57-64.

[35] A. Mamat, Y. Lu, J. Deogun and S. Goddard, ”Real-Time Divisible LoadScheduling with Advance Reservations,” 20th Euromicro Conference onReal-Time Systems, 2008, pp. 37-46.

[36] L. Marchal, Y. Yang, H. Casanova and Y. Robert, ”A realistic net-work/application model for scheduling divisible loads on large-scaleplatforms,” vol., 2008.

[37] L. Marchal, Y. Yang, H. Casanova and Y. Robert., ”Steady-statescheduling of multiple divisible load applications on wide-area distributedcomputing platforms,” Int. Journal of High Performance ComputingApplications, vol. 20, 2006, pp. 365-381.

[38] M. W. Margo, K. Yoshimoto, P. Kovatch and P. Andrews, ”Impact ofReservations on Production Job Scheduling,” Lecture Notes in ComputerScience (4942), 2007, pp. 116-131.

[39] S. Mingsheng, ”Optimal algorithm for scheduling large divisible work-load on heterogeneous system,” Applied Mathematical Modelling, vol.32, 2008, pp. 1682-1695.

[40] M. Moges and T. G. Robertazzi, ”Wireless Sensor Networks: Schedulingfor Measurement and Data Reporting,” Aerospace and Electronic Sys-tems, vol. 42, 2006, pp. 327- 340.

[41] M. A. Moges and T. G. Robertazzi, ”Divisible Load Scheduling andMarkov Chain Models,” Computers and Mathematics with Applications,vol. 52, 2006, pp. 1529-1542.

[42] M. A. Moges, D. Yu and T. G. Robertazzi, ”Divisible load schedulingwith multiple sources: Closed form solutions,” Conference on InfomationSciences and Systems, 2005.

[43] M. Othman, M. Abdullah, H. Ibrahim and S. Subramaniam, ”A2DLT:Divisible Load Balancing Model for Scheduling Communication-Intensive Grid Applications,” Lecture Notes in Computer Science (5101),2008, pp. 246-253.

[44] M. Othman, M. Abdullah, H. Ibrahim and S. Subramaniam, ”AdaptiveDivisible Load Model for Scheduling Data-Intensive Grid Applications,”Lecture Notes in Computer Science (4487) (4487), 2007, pp. 446-453.

[45] T. Pieter, V. Bruno, L. Marc, T. Filip, D. Bart and D. Piet, ”Dimensioning

and on-line scheduling in Lambda Grids using divisible load concepts,”J. Supercomput., vol. 42, 2007, pp. 59-82.

[46] T. Pieter, L. Marc De, V. Bruno, T. Filip De, D. Bart and D. Piet,”Using Divisible Load Theory to Dimension Optical Transport Networksfor Grid Excess Load Handling,” Proceedings of the Joint InternationalConference on Autonomic and Autonomous Systems and InternationalConference on Networking and Services, 2005.

[47] T. G. Robertazzi, ”Divisible Load Scheduling,Research To Date, October18, 2008,” 2008.

[48] T. G. Robertazzi, ”Networks and Grids Technology and Theory,”Springer, New york, 2007.

[49] T. G. Robertazzi, ”Ten Reasons to Use Divisible Load Theory,” Com-puter, vol. 36, 2003, pp. 63-68.

[50] T. G. Robertazzi and D. Yu, ”Multi-Source Grid Scheduling for Divis-ible Loads,” IEEE 40th annual conference on information sciences andsystems, 2006, pp. 188-191.

[51] S. Suresh, H. J. Kim, B. Y. Lee and T. Robertazzi, ”An analyticalsolution for scheduling nonlinear divisible loads for a single level treenetwork with a collective communication model,” IEEE Transactions onSystems, Man, and Cybernetics, vol. resubmitted after revision, 2008.

[52] S. Suresh, V. Mani, S. N. Omkar, H. J. Kim and N. Sundararajan, ”Anew load distribution strategy for linear network with communicationdelays,” Mathematics and Computers in Simulation, vol. 79, 2009, pp.1488-1501.

[53] B. Veeravalli, D. Ghose, V. Mani and T. G. Robertazzi, ”Scheduling Di-visible Loads in Parallel and Distributed Systems,” Wiley-IEEE ComputerSociety Press, 1996.

[54] B. Veeravalli and J. Jia, ”Design, Analysis, and Performance Evaluationof an Efficient Resource Unaware Scheduling Strategy for ProcessingDivisible Loads on Distributed Linear Daisy Chain Networks,” LectureNotes in Computer Science (5374), 2008, pp. 390-401.

[55] B. Veeravalli and W. H. Min, ”Scheduling Divisible Loads on Hetero-geneous Linear Daisy Chain Networks with Arbitrary Processor ReleaseTimes,” IEEE Transaction on Parallel and Distributed Systems, vol. 15,2004, pp. 273-288.

[56] S. Viswanathan, B. Veeravalli and T. G. Robertazzi, ”Resource-AwareDistributed Scheduling Strategies for Large-Scale Computational Clus-ter/Grid Systems,” IEEE Transactions on Parallel and Distributed Sys-tems, vol. 18, 2007, pp. 1450-1461.

[57] S. Viswanathan, B. Veeravalli, D. Yu and T. G. Robertazzi, ”Design andAnalysis of a Dynamic Scheduling Strategy with Resource Estimation forLarge-Scale Grid Systems,” International Conference on Grid Computing,2004, pp. 163-170.

[58] B. Volckaert, P. Thysebaert, M. D. Leenheer, F. D. Turck, B. Dhoedtand P. Demeester, ”Flexible Grid service management through resourcepartitioning,” The Journal of Supercomputing, vol. 38, 2006, pp. 279 -305.

[59] M. Wong Han, V. Bharadwaj and B. Gerassimos, ”Design and per-formance evaluation of load distribution strategies for multiple divisibleloads on heterogeneous linear daisy chain networks,” J. Parallel Distrib.Comput., vol. 65, 2005, pp. 1558-1577.

[60] H. Yamamoto, M. Tsuru and Y. Oie, ”Parallel Transferable UniformMulti-round Algorithm for Achieving Minimum Application TurnaroundTimes for Divisible Workload,” Lecture Notes in Computer Science(3725), 2005, pp. 817-828.

[61] H. Yamamoto, M. Tsuru and Y. Oie, ”A Parallel Transferable UniformMulti-Round Algorithm in Heterogeneous Distributed Computing Envi-ronment,” Lecture Notes in Computer Science (4208), 2006, pp. 51-60.

[62] Y. Yang and H. Casanova, ”UMR: A Multi-Round Algorithm forScheduling Divisible Workloads,” 17th International Symposium on Par-allel and Distributed Processing, 2003.

[63] Y. Yang, H. Casanova, M. Drozdowski, M. Lawenda and A. Legrand.,”On the complexity of multi-round divisible load scheduling,” 2007.

[64] J. Yao, J. Guo and L. Bhuyan, ”Fair link striping with FIFO delivery onheterogeneous channels,” Computer Communications, vol. 31, 2008, pp.3427-3437.

[65] C. Yeim-Kuan, W. Jia-Hwa, C. Chi-Yeh and C. Chih-Ping, ”ImprovedMethods for Divisible Load Distribution on k-Dimensional Meshes UsingMulti-Installment,” IEEE Trans. Parallel Distrib. Syst., vol. 18, 2007, pp.1618-1629.

[66] T. Zhu, Y. Wu and G. Yang, ”Scheduling divisible loads in the dynamicheterogeneous grid environment,” 1st international conference on Scalableinformation systems, 2006.

4949