Heuristic algorithms for the optimization of total weighted completion time for asynchronous transmission in a packet data transmission system

• Autorzy: Piórkowski A. , Werewka J. , Bielecka M.
• Języki publikacji: EN

Abstrakty

EN

In this paper, the minimization of total weighted completion time (total cost) for asynchronous transmission in distributed systems is discussed. Special attention has been paid to the problem of message scheduling on the sender side. Messages to be sent form a queue, therefore the order in which they are to be sent has to be set. Scheduling algorithms can be chosen to optimize scheduling criteria such as total completion time or total weighted completion time. The message scheduling problem becomes complicated considerably when the transmitted data stream between the sender and the receiver is formed into packets. TheWSPT (Weighted Shortest Processing Time) scheduling rule, which orders messages according to non-decreasing length and weight ratios has been proven to be non-optimal. It has been demonstrated that the problem of minimizing the total weighted completion time is NP-hard. Here, we propose heuristic algorithms for scheduling messages and experimentally evaluate the performance of these scheduling algorithms.

Słowa kluczowe

EN

total weighted completion time; total cost factor; optimization; heuristic algorithms; packet transmission

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2014
• Tom: Vol. 43, no. 4
• Strony: 507--529
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Piórkowski A.

• Department of Geoinformatics and Applied Computer Science AGH University of Science and Technology al. Mickiewicza 30, 30–059 Cracow, Poland

autor

Werewka J.

• Department of Applied Computer Science AGH University of Science and Technology Al. Mickiewicza 30, 30–059 Cracow, Poland

autor

Bielecka M.

• Department of Geoinformatics and Applied Computer Science AGH University of Science and Technology al. Mickiewicza 30, 30–059 Cracow, Poland

Bibliografia

• 1. Adler, M., Khanna, S., Rajaraman, R., Rosen, A. (1999) Time–constrained scheduling of weighted packets on trees and meshes. In: Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures. ACM, 1–12.
• 2. Adler, M., Sitaraman, R.K., Rosenberg, A.L., Unger, W. (1998) Scheduling time–constrained communication in linear networks. In: Pro- ceedings of the tenth annual ACM symposium on Parallel algorithms and architectures. ACM, 269–278.
• 3. Atencia, I. (2014) A discrete-time system with service control and repairs. International Journal of Applied Mathematics and Computer Science 24(3), 471–484.
• 4. Bansal, N., Harchol-Balter, M. (2001) Analysis of srpt scheduling: Investigating unfairness. SIGMETRICS Perform. Eval. Rev. 29 (1), 279– 290, http://doi.acm.org/10.1145/384268.378792
• 5. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., et al. (2001) Introduction to Algorithms, 2. MIT Press, Cambridge.
• 6. Coulouris, G.F., Dollimore, J., Kindberg, T. (2005) Distributed Systems: Concepts and Design. Pearson Education.
• 7. Dijkstra, E.W. (2002) Cooperating Sequential Processes. Springer
• 8. Dobrin, R., Fohler, G. (2001) Implementing off-line message scheduling on controller area network (can). In: Emerging Technologies and Factory Automation, 2001. Proceedings. 2001 8th IEEE International Conference on. IEEE, 241–245.
• 9. Flieder, K. (2005) Testing and visualizing a message queuing infrastructure. In: N. Callaos, W. Lesso. eds., Proc. of WMSCI ’05, Orlando, Florida, 51–57.
• 10. Gajer, M. (2010) Task scheduling in real-time computer systems with the use of an evolutionary computations technique. Przegl¸ad Elektrotechniczny 86(10), 293–298
• 11. Gawlick, D. (2002) Message queuing for business integration. eAi Journal (October 2002)
• 12. Harchol-Balter, M., Bansal, N., Schroeder, B. (2000) Implementation of srpt scheduling in web servers. Technical Report cmu-cs-00-170. Carnegie Mellon School of Computer Science
• 13. Huang, Y. (2007) Scalable Web Service-based XML Message Brokering Across Organizations. ProQuest
• 14. J´udice, J.J., Faustino, A.M., Ribeiro, I.M. (2002) On the solution of np–hard linear complementarity problems. Top 10(1), 125–145
• 15. Kielmann, T., Hofman, R.F., Bal, H.E., Plaat, A., Bhoedjang, R.A. (1999) MPI’s reduction operations in clustered wide area systems. ACM Sigplan Notices 34 (8), 173–182.
• 16. Nawrocki, J., Complak, W., B la˙zewicz, J., Kopczy´nska, S., Ma´ckowiak, M. (2009) The knapsack lightening problem and its application to scheduling hrt tasks. Bulletin of the Polish Academy of Sciences: Technical Sciences 57(1), 71–77
• 17. Ng, C.T., M´edard, M., Ozdaglar, A. (2009) Completion time minimization and robust power control in wireless packet networks. In: Communications, 2009. ICC09. IEEE International Conference on. IEEE, 1–6.
• 18. Piórkowski, A. (2003) Heurystyczne algorytmy optymalizacji kosztu całkowitego w systemach wiadomości kolejkowanych (Heuristic algorithms to optimize total cost in the systems of queued messages; in Polish). Automatyka. Akademia Górniczo–Hutnicza im. Stanis lawa Staszica w Krakowie 7, 221–227
• 19. Piorkowski, A., Werewka, J. (2010) 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), 391–400
• 20. Ramanathan, P., Rupnick, G.M. (1991) Deadline constrained message scheduling in point–to point interconnection. In: Proc System Design Synthesis Technology Workshop, Silver Spring, MD, Naval Surface Warfare Center, 183–192.
• 21. Ramesh, S., Perros, H.G. (2001) A multi-layer client-server queueing network model with non hierarchical synchronous and asynchronous messages. Performance Evaluation 45(4), 223–256
• 22. Shafer, K., Ahuja, M. (1992) Process-channel agent-process model of asynchronous distributed communication. In: Distributed Computing Systems, 1992., Proceedings of the 12th International Conference on. IEEE, 4–11.
• 23. Smith, W.E. (1956) Various optimizers for single-stage production. Naval Research Logistics Quarterly 3(1-2), 59–66
• 24. Tsai, B.R., Shin, K.G. (1996) Combined routing and scheduling of concurrent communication traffic in hypercube multicomputers. In: Distributed Computing Systems, 1996, Proceedings of the 16th International Conference on. IEEE, 150–157.
• 25. Wozniak, M., Kempa, W.M., Gabryel, M., Nowicki, R.K. (2014) A finite-buffer queue with single vacation policy – analytical study with evolutionary positioning. International Journal of Applied Mathematics and Computer Science 24(4), 887–900
• 26. Yang, B., Liu, D.y., Yang, K. (2002) Communication performance optimization for mobile agent system. In: Machine Learning and Cybernetics, 2002. Proceedings. 2002 International Conference on. IEEE 1, 327–335.
• 27. Yang, J., Ulukus, S. (2010) Transmission completion time minimization in an energy harvesting system. In: Information Sciences and Systems (CISS), 2010 44th Annual Conference on. IEEE, 1–6.
• 28. Zhu, X., Yu, J., Doyle, J.(2001) Heavy tails, generalized coding, and optimal web layout. In: INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. 3, 1617–1626.

Uwagi

PL