Minimization of the total completion time for asynchronous transmission in a packet data-transmission system

Adam Piórkowski ; Jan Werewka

International Journal of Applied Mathematics and Computer Science, Tome 20 (2010), p. 391-400 / Harvested from The Polish Digital Mathematics Library

Résumé

The minimization of the total completion time for asynchronous transmission in distributed systems is discussed. Attention is focused on the problem of message scheduling on part of the sender. Messages to be sent form a queue, and the order in which they are to be sent has to be first established. The methods of scheduling messages, which minimize the factor of the total completion time, are presented herein. The message-scheduling problem becomes considerably complicated when the stream of data transmitted between the sender and the receiver is organized into packets. A scheduling rule, according to which the shortest messages (SPT-Shortest Processing Time) are selected as the first to be sent, has been proven to be appropriate for the proposed model. A heuristic algorithm for scheduling messages with real-time constraints is proposed. The performance of the scheduling algorithm is experimentally evaluated. The results of the study show the possibility of improving the total completion time from a few to ten percent, depending on the characteristics of the sender. Thus, the practicability of the method has been proved.

Détail

Publié le : 2010-01-01

Zbl 1231.68101

EUDML-ID : urn:eudml:doc:207995

Bibliographie

[000] Adler, M., Khanna S., Rajaraman, R., and Rosen, A., (1999). Time-constrained scheduling of weighted packets on trees and meshes, Proceedings of the 1999 ACM Symposium on Parallel Algorithms and Architecture, New York, NY, USA, pp. 1-12. | Zbl 1053.68013

[001] Adler, M., Rosenberg, A.L., Sitaraman, R., and Unger, W., (1998). Scheduling time-constrained communication in linear networks, 10-th ACM Symposiumon Parallel Algorithms and Architectures, New York, NY, USA, pp. 269-278.

[002] Bansal, N. and Harchol-Balter, M. (2000). Analysis of SRPT scheduling: Investigating unfairness, Technical Report CMU-CS-00-149, Carnegie Mellon University, Pittsburgh, PA.

[003] Coulouris, C., Dollimore, J. and Kindberg, T. (2001). Distributed Systems-Concepts and Design, Addison-Wesley, Harlow. | Zbl 0848.68021

[004] Dobrin, R. and Fohler, G. (2001). Implementing off-line message scheduling on Controller Area Network (CAN), 8-th IEEE International Conference on Emerging Technologies & Factory Automation, Nice, France.

[005] Gouaux, F. and Simon-Chautemps, L. (2002). Ambient intelligence and pervasive systems for the monitoring of citizens at cardiac risk: New solutions from the EPI-MEDICS project, IEEE Computers in Cardiology 29: 289-292.

[006] Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Operations Research 5(5): 287-326. | Zbl 0411.90044

[007] Hamalainen, P., Hannikainen, M., Hamalainen, T.D. and Soininen, R. (2003). Offline architecture for real-time betting, ICME'03. Proceedings of the 2003 International Conference on Multimedia and Expo, Baltimore, MD, USA, Vol. I, pp. 709-712.

[008] Harchol-Balter, M., Bansal, N. and Schroeder, B. (2000). Implementation of SRPT scheduling in web servers, Technical Report CMU-CS-00-170, Carnegie Mellon School of Computer Science, Pittsburgh, PA. | Zbl 1056.68610

[009] Janiak, A. and Krysiak, T. (2007). Single processor scheduling with job values depending on their completion times, Journal of Scheduling 10(2): 129-138. | Zbl 1154.90462

[010] Khoor, S., Nieberl, J., Fugedi, K. and Kail, E. (2003). Internetbased, GPRS, long-term ECG monitoring and non-linear heart-rate analysis for cardiovascular telemedicine management, Computers in Cardiology 30: 209-212.

[011] Kielmann, T., Hofman, R.F.H., Bal, H.E., Plaat, A. and Bhoedjang, R.A.F. (1999). MPI's reduction operations in clustered wide area systems, Proceedings of MPIDC '99, Message Passing Interface Developer's and User's Conference, Atlanta, GA, USA, pp. 43-52.

[012] Liu, C.L., and Layland, J.W. (1973). Scheduling algorithms for multiprogramming in a hard real-time environment, Journal of the ACM 20(1): 46-61. | Zbl 0265.68013

[013] Lui, K.S. and Zaks, S.(1997). Scheduling in synchronous networks and the greedy algorithm, Proceedings of the 11-th International Workshop on Distributed Algorithms (WDAG), Saarbrucken, Germany, Vol. 2, pp. 556-561.

[014] Osman, M.Y.B., Kin, P.F.W., Leong, L.L.E., Wong, Ch.V., Wong, K.N., Khoon, J.T.L., Goh, S.B., Zainol, M.N.B. and Prakash, E.C. (2000). Simple pools online betting software system-A UML use case analysis, Proceedings of TENCON2000, Kuala Lumpur, Malaysia, Vol. 2, pp. 556-561.

[015] Ramanathan, P. and Rupnick, G.M. (1991). Deadline constrained message scheduling in point-to-point interconnection, Proceedings of the System Design Synthesis Technology Workshop, Silver Spring, MD, USA, pp. 183-192.

[016] Smith, W.E. (1956). Various optimizers for single-stage production, Naval Research Logistics (2): 59-66.

[017] Tsai, B.R. and Shin, K.G. (1996). Combined routing and scheduling of concurrent communication traffic in hypercube multicomputers, Proceedings of the International Conference on Distributed Computing Systems, Hong Kong, pp. 150-157.

[018] Yang, B., Dayou L. and Kun Y. (2002). Communication performance optimization for mobile agent system, Proceedings of the IEEE First International Conference on Machine Learning and Cybernetics (ICMLC2002), Beijing, China, pp. 327-335.

[019] Xu, X. (2008). The videotex hot line lottery-ticket-buying solution based on mobile GPRS system, International Conference on Management of e-Commerce and e-Government, ICMECG'08, Washington, DC, USA, pp. 30-35.

[020] Zhu, X., Yu J. and Doyle J.(2001). Heavy tails, generalized coding and optimal web layout, Proceedings of IEEE INFOCOM, Piscataway, ND, USA, Vol. 3, pp. 1617-1626.