On EDF scheduler with the exponential deadlines

• Autorzy: Janowski R. , Janowski A.
• Języki publikacji: EN

Abstrakty

EN

This work deals with the performance evaluation of EDF (Earliest Deadline First) packet scheduler with two classes. The primary metric of interest is the mean sojourn time for each class. The system is composed of two classes (two queues) with Poisson input to each of them, deterministic service times and exponentially distributed deadline values. The model is analysed as an embedded Markov chain at the instants of packet departures from the service. The solution i.e. the joint probability distribution of the number of packets in each queue is obtained using the matrix approach. The metrics such as the mean sojourn time or the mean number of packets in the system for each class are directly obtained from this joint probability distribution.

Słowa kluczowe

EN

Earliest Deadline First; scheduling; performance evaluation; Markov chains

• Wydawca: Warszawska Wyższa Szkoła Informatyki
• Czasopismo: Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki
• Rocznik: 2016
• Tom: nr 15
• Strony: 7--17
• Opis fizyczny: Bibliogr. 13 poz., rys., wykr.

Twórcy

autor

Janowski R.

• Warsaw School of Computer Science

autor

Janowski A.

• Independent scholar

Bibliografia

• [1] Jaiswal N.K., Priority queues, Academic Press, New York, 1968
• [2] Parekh A.K., Gallager R.G., A generalized processor sharing approach to flow control in integrated services networks, “IEEE/ACM Transaction on Networking” Vol. 1, No. 3, June 1993
• [3] Stankovic J.A., Spuri M., Ramamritham K., Buttazzo G.C., EDF scheduling for Real Time systems, Springer International Series in Engineering and Computer Science, 1998
• [4] ITU-T Recommendation Y.1541, Network performance objectives for IP- based services, ITU, May 2002
• [5] ITU-T Recommendation Y.1540, Internet Protocol data communication service - IP packet transfer and availability performance parameters, ITU, January 2002
• [6] Bui D., Revision of a Non-Preemptive EDF Packet Scheduling Algorithm, Technical Report No. UCB / EECS-2009-50, http://www.eecs.berkeley.edu/ Pubs/TechRpts/2009/EECS-2009-50.html, April 24, 2009
• [7] Kargahi M., Movaghar A., A Method for Performance Analysis of Earliest- Deadline-First Scheduling Policy, “The Journal of Supercomputing” 37, 2006
• [8] Ciucu F., Poloczek F., Schmitt J., Sharp Bounds in Stochastic Network Calculus, “SIGMETRICS '13” June 2013
• [9] Biton E., Orda A., QoS Provision with EDF Scheduling, Stochastic Burstiness and Stochastic Guarantees, proceedings of 18th International Teletraffic Congress, ITC18, September 2003
• [10] Scriba S.M., Takawira F., Packet violation probability analysis of the Earliest Deadline First scheduler, Proceedings of Southern African, 2004
• [11] Gross D, Harris C., Fundamentals of queueing theory, 3rd edition, Wiley, Hoboken, 2002
• [12] Kleinrock L., Queueing Systems, Vol. 1 & 2, Wiley, Hoboken, 1975
• [13] SageMath, https://www.sagemath.org/