Non-preemptive priority scheduler with multiple thresholds for network routers
The vast variety of applications available and being developed forcomputer networks have different quality of service requirements. Oneof the most significant ways to satisfy the needs of the applications is thepacket scheduling algorithms employed by the network routers. Byallocating router resources to the applications, packet schedulers try toimprove the quality of service needs of the applications. Thus, the delayscan be reduced or the reliability of the applications can be increased byreducing packet losses. Priority schedulers are able reduce the delay andlosses for high priority applications. On the other hand, for low priorityapplications they introduce the starvation problem. Low priorityapplication packets can face excessive delays and losses. In this paper, anon-preemptive priority scheduler with multiple thresholds (PRMT) isproposed. The PRMT scheduler needs only a single queue withpredefined threshold levels for different priority applications. The PRMTscheduler eliminates the starvation problem of low priority applicationswithout a significant impact on the high priority applications.
Ağ yönlendiricileri için çoklu eşik kullanan geçişsiz öncelikli zamanlayıcı
Bilgisayar ağları için mevcut ve geliştirilmekte olan çok çeşitli uygulamaların farklı hizmet kalitesi gereksinimleri vardır. Uygulamaların ihtiyaçlarını karşılamanın en önemli yollarından birisi ağ yönlendiricileri tarafından kullanlan paket zamanlama algoritmalarıdır. Uygulamalara yönlendirici kaynaklarını ayırarak, paket zamanlayıcıları uygulamaların hizmet kalitesi ihtiyaçlarını artırmaya çalışır. Bu nedenle, gecikmeler azaltılabilir ya da uygulamaların güvenilirliği paket kayıplarını azaltmak suretiyle arttırılabilir. Öncelikli zamanlayıcılar, yüksek öncelikli uygulamaların gecikme ve kayıplarını azaltabilirler. Öte yandan, düşük öncelikli uygulamalar için açlık problemi getirirler. Düşük öncelikli uygulama paketleri aşırı gecikmeler ve kayıplarla karşılaşabilirler. Bu makalede çoklu eşik kullanan geçişsiz öncelikli zamanlayıcı (PRMT) önerilmektedir. PRMT zamanlayıcı farklı öncelikli uygulamalar için önceden tanımlanmış eşik seviyeleri kullanan tek bir kuyruk ihtiyacı duyar. PRMT zamanlayıcı yüksek öncelikli uygulamaların üzerinde önemli bir etkiye yol açmadan, düşük öncelikli uygulamalardaki açlık sorunu ortadan kaldırır.
___
- Zorzi M, Gluhak A, Lange S, Bassi A. “From today's intranet
of things to a future internet of things: a wireless-and
mobility-related view”. IEEE Wireless Communications,
17(6), 44-51, 2010
- Gubbi J, Buyya R, Marusic S, Palaniswami M. “Internet of
Things (IoT): A vision, architectural elements, and future
directions”. Future Generation Computer Systems, 29(7),
1645-1660, 2013.
- Gartner Inc. “Gartner Says 6.4 Billion Connected Things
Will be in Use in 2016, up 30 Percent From 2015”.
http://www.gartner.com/newsroom/id/3165317
(19.10.2016).
- Tanenbaum AS, Wetherall DJ. Computer Networks. 5 th ed.
Boston, USA, Pearson, 2011.
- Kurose JF, Ross KW. Computer Networking a Top-Down
Approach. 6 th ed. Essex, England, Pearson, 2013.
- Zhang H. “Service disciplines for guaranteed performance
service in packet-switching networks”. Proceedings of the
IEEE, 83(10), 1374-1396, 1995.
- Necker MC. “A comparison of scheduling mechanisms for
service class differentiation in HSDPA networks”.
AEU-International
Journal
of
Electronics
and
Communications, 60(2), 136-141, 2006.
- Bhatti SN, Crowcroft J. “QoS-sensitive flows: Issues in IP
packet handling”. IEEE Internet Computing, 4(4), 48-57,
2000.
- Kleinrock L. Queuing Systems, Volume 2: Computer
Applications. New York, USA, Wiley Interscience, 1975.
- Zhao W, Stankovic JA. “Performance analysis of FCFS and
improved FCFS scheduling algorithms for dynamic
real-time computer systems”. Real Time Systems
Symposium, Santa Monica, CA, USA, 5-7 December 1989.
- Saleh M, Dong L. “Comparing FCFS & EDF scheduling
algorithms for real-time packet switching networks”. 2010
International Conference on Networking, Sensing and
Control (ICNSC), Chicago, IL, USA, 10-12 April 2010.
- Jain V, Agarwal S, Goswami K. “Dynamic multilevel priority
packet scheduling design for WSN”. 2014 International
Conference on Signal Propagation and Computer
Technology (ICSPCT), Rajasthan, India, 12-13 July 2014.
- Justus JJ, Sekar AC. “Energy efficient priority packet
scheduling with delay and loss constraints for wireless
sensor networks”. International Conference on Inventive
Computation
Technologies,
Tamilnadu,
India,
26-27 August 2016.
- Dag T, Uzungenc S. “Dynamic multi threshold priority
packet scheduling algorithms”. 2016 International
Conference on Measurement Instrumentation and
Electronics (ICMIE), MATEC Web of Conferences, Munich,
Germany, 6-8 June 2016.
- Yantong W, Sheng Z. “An enhanced dynamic priority
packet scheduling algorithm in wireless sensor networks”.
18 th International Conference on Computer Modelling and
Simulation (UKSim), Cambridge, UK, 6-8 April 2016.
- Bansode S, Sambare S. “Performance evaluation of
dynamic multilevel priority (DMP) packet scheduling for
wireless sensor networks”. 2015 International Conference
on Pervasive Computing, Pune, India, 8-10 January 2015.
- Karim L, Nasse N, Taleb T, Alqallaf A. “An efficient priority
packet scheduling algorithm for wireless sensor network”.
2012 IEEE International Conference on Communications
(ICC), Ottawa, ON, Canada, 10-15 June 2012.
- Kargahi M, Movaghar A. “Non-preemptive earliest-
deadline-first scheduling policy: a performance study”.
13 th IEEE International Symposium on Modeling, Analysis,
and Simulation of Computer and Telecommunication
Systems, Atlanta, GA, USA, 26-29 September 2005.
- Liu D, Lee YH. “An efficient scheduling discipline for packet
switching networks using earliest deadline first round
robin”. 12 th International Conference on Computer
Communications and Networks (ICCCN), Dallas, TX, USA,
20-22 October 2003.
- Hamed M, Shukry S, El-Mahallawy MS, El-Ramly S.
“Modified earliest deadline first scheduling with channel
quality indicator for downlink real-time traffic in LTE
networks”. 3 rd International Conference on e-Techologies
and Networks for Development (ICeND), Beirut, Lebanon,
29 April-1 May 2014.
- Demers A, Keshav S, Shenker S. “Analysis and Simulation
of a Fair Queueing Algorithm”. ACM SIGCOMM Symposium,
Austin, TX, USA, 19-22 September 1989.
- Parekh AK, Gallager RG. “A generalized processor sharing
approach to flow control in ıntegrated services networks:
the single-node Case”. IEEE/ACM Transactions on
Networking, 1(3), 344-357, 1993.
- Banks J, Carson II JS, Nelson B, Nicol DM. Discrete-Event
System Simulation. 5 th ed. New Jersey, USA, Pearson, 2010.