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 (2010)

  • Volume: 20, Issue: 2, page 391-400
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Adam Piórkowski, and Jan Werewka. "Minimization of the total completion time for asynchronous transmission in a packet data-transmission system." International Journal of Applied Mathematics and Computer Science 20.2 (2010): 391-400. <http://eudml.org/doc/207995>.

@article{AdamPiórkowski2010,
abstract = {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.},
author = {Adam Piórkowski, Jan Werewka},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {message scheduling; message queuing; distributed systems; real-time systems},
language = {eng},
number = {2},
pages = {391-400},
title = {Minimization of the total completion time for asynchronous transmission in a packet data-transmission system},
url = {http://eudml.org/doc/207995},
volume = {20},
year = {2010},
}

TY - JOUR
AU - Adam Piórkowski
AU - Jan Werewka
TI - Minimization of the total completion time for asynchronous transmission in a packet data-transmission system
JO - International Journal of Applied Mathematics and Computer Science
PY - 2010
VL - 20
IS - 2
SP - 391
EP - 400
AB - 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.
LA - eng
KW - message scheduling; message queuing; distributed systems; real-time systems
UR - http://eudml.org/doc/207995
ER -

References

top
  1. 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. Zbl1053.68013
  2. 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. 
  3. Bansal, N. and Harchol-Balter, M. (2000). Analysis of SRPT scheduling: Investigating unfairness, Technical Report CMU-CS-00-149, Carnegie Mellon University, Pittsburgh, PA. 
  4. Coulouris, C., Dollimore, J. and Kindberg, T. (2001). Distributed Systems-Concepts and Design, Addison-Wesley, Harlow. Zbl0848.68021
  5. 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. 
  6. 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. 
  7. 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. Zbl0411.90044
  8. 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. 
  9. 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. Zbl1056.68610
  10. Janiak, A. and Krysiak, T. (2007). Single processor scheduling with job values depending on their completion times, Journal of Scheduling 10(2): 129-138. Zbl1154.90462
  11. 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. 
  12. 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. 
  13. 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. Zbl0265.68013
  14. 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. 
  15. 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. 
  16. 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. 
  17. Smith, W.E. (1956). Various optimizers for single-stage production, Naval Research Logistics (2): 59-66. 
  18. 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. 
  19. 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. 
  20. 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. 
  21. 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. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.