Flexible Buffer Management with Thresholds and Blocking for Congestion Control in Multi - Server Computer Systems

• Autorzy: Oniszczuk W.

Warianty tytułu

PL

Dynamiczna alokacja buforów z progami i blokadami w kontroli przeciążeń systemów komputerowych

• Języki publikacji: EN

Abstrakty

EN

This paper is aimed at designing a congestion control system (decision maker) that scales gracefully with computer system capacity, providing high utilization, and fairness among users. The use of adequate buffer management scheme with thresholds and blocking are well-known techniques for computer systems traffic congestion control. This motivates the study of multi-server computer systems with two distinct priority classes (high and low priority traffics), partial buffer sharing scheme with thresholds and with blocking. The external traffic is modeled using the Poisson processes. The service times have been modeled using the exponential distribution. Adaptive buffer allocation algorithm (scheme) is designed to allow the input traffic to be portioned into different priority classes and based on the input traffic behavior it controls the thresholds dynamically. This algorithm allows input low priority jobs to enter into buffer if its occupancy level is less than the threshold value. Additionally, for low priority jobs a forward threshold and a reverse threshold are defined (hysteresis). Using an open Markovian queuing schema with blocking, and thresholds, a closed form cost-effective analytical solution for this model of computer system is obtained. The model of multi-server system is very accurate. It is derived directly from a state graph and a set of steady-state equations, followed by calculations of main measures of effectiveness. Based on numerical experiments and collected results we conclude that the proposed model with blocking, and thresholds can provide accurate performance estimates of multi-server systems.

PL

Dynamiczna alokacja buforów przez wprowadzenie progów i blokad oraz ich zaimplementowanie w kontrolerze dostępu do zasobów systemów komputerowych jest jednym ze sposobów przeciwdziałania przeciążeniom serwerów. Prowadzi to do lepszego ich wykorzystania, gwarantując przy tym większy komfort pracy użytkownikom. Tak zdefiniowane założenia są podstawą budowy modeli matematycznych systemów komputerowych, w których mamy kilka serwerów ze wspólnym buforem, obsługujących użytkowników podzielonych na dwie klasy, to jest generujących zadania o wyższym i niższym priorytecie. W prezentowanej sieci, zewnętrzne strumienie zadań modelowane są strumieniami Poissona, a zmienna losowa – czas obsługi zadań w serwerach przyjmuje się jako podlegającą rozkładowi wykładniczemu. W zależności od stopnia zapełnienia bufora zadaniami obu klas, progi są dynamicznie zmieniane, a zadania niższego priorytetu przyjmowanie są do węzła obsługi tylko wtedy, gdy zapełnienie bufora jest mniejsze niż wartość progowa m2, bo inaczej następuje blokada przyjęć tych zadań. Wznowienie obsługi zadań niższego priorytetu, nastąpi tylko wtedy, gdy zapełnienie bufora dojdzie do drugiego progum1. Mamy tu zjawisko histerezy. Zadania wyższego priorytetu przyjmowane są zawsze, aż do pełnego zapełnienia bufora i wtedy tez może wystąpić druga blokada przyjmowania zadań, tym razem ze źródła o wyższym priorytecie. W pracy, do modelowania tak zdefiniowanej sieci stanowisk obsługi, użyto teorii markowowskich systemów kolejkowych. Zbudowano pełny graf stanów systemu, ułożono układy równań algebraicznych dla stanów ustalonych, które opisują dynamikę zmian pracy modelu. Obliczono stacjonarne prawdopodobieństwa dla wszystkich rozróżnialnych stanów modelu sieci, a następnie zdefiniowano algorytmy obliczeń podstawowych miar wydajności. W części eksperymentalnej pokazano jak zmieniają się miary wydajności i jakości obsługi w zależności od zmieniających się parametrów wejściowych modelu.

Słowa kluczowe

EN

task and resource allocation; congestion control; decision maker; blocking; threshold-base systems; Markov chains; performance evaluation

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2010
• Tom: Vol. 22, No. 1
• Strony: 49--61
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Oniszczuk W.

• Computer Science Faculty Bialystok University of Technology ul. Wiejska 45A, Bialystok, Poland,

Bibliografia

• 1. I. Awan: Analysis of multiple-threshold queues for congestion control of heterogeneous traffic streams. Simulation Modelling Practice and Theory 14, pp. 712-724, 2006.
• 2. S. Balsamo, V. de Nito Persone, R. Onvural: Analysis of Queueing Networks with Blocking. Kluwer Academic Publishers, Boston, 2001.
• 3. S-T. Cheng, Ch-M. Chen, I-R. Chen: Performance evaluation of an admission control algorithm: dynamic threshold with negotiation. Performance Evaluation 52, pp. 1-13, 2003.
• 4. B.D. Choi, S.H. Choi, B. Kim, D.K. Sung: Analysis of priority queueing systems based on thresholds and its application to signalling system no. 7 with congestion control. Computer Networks 32, pp. 149-170, 2000.
• 5. S. Kausha, R.K. Sharma: Modeling and Analysis of Adaptive Buffer Sharing Scheme for Consecutive Packet Loss Reduction in Broadband Networks. International Journal of Computer Systems Science and Engineering 4(1), pp. 8-15, 2008.
• 6. J.C.S. Lui, L. Golubchik: Stochastic complement analysis of multi-server threshold queues with hysteresis. Performance Evaluation 35, pp. 19-48, 1999.
• 7. W. Oniszczuk: An Intelligent Service Strategy in Linked Networks with Blocking and Feedback. In: N.T. Nguyen, R. Katarzyniak, editors, Studies in Computational Intelligence N. 134 "New Challenges in Applied Intelligence Technologies", Springer-Verlag, Berlin, Heidelberg, pp. 351-361, 2008.
• 8. F. Paganini, Z. Wang, J.C. Doyle, and S.H. Low: Congestion Control for High Performance, Stability, and Fairness in General Networks. IEEE/ACM Transactions on Networking 13(1), pp. 43-56, 2005.
• 9. H.G. Perros: Queuing Networks with Blocking. Exact and Approximate Solution. Oxford University Press, New York, 1994.
• 10. M.L. Puterman: Markov Decision Processes. Discrete Stochastic Dynamic Programming. Wiley-Interscience, Hoboken, New Jersey, 2005.
• 11. F. Sabrina, S.S. Kanhere, S.K. Jha: Design, Analysis, and Implementation of a Novel Multiple Resources Scheduler. IEEE Transactions on Computers 56(6), pp. 1071-1086, 2007.
• 12. E. Xu, A.S. Alfa: A vacation model for the non-saturated Readers and Writers system with a threshold policy. Performance Evaluation 50, pp. 233-244, 2002.
• 13. H. Zhang, Z-P. Jiang, Y. Fan, S. Panwar: Optimization based flow control with improved performance. Communications in Information and Systems 4(1), pp. 235-252, 2004.