A Comparison of Fair Sharing Algorithms for Regulating Search as a Service API
DOI:
https://doi.org/10.14738/tnc.101.9633Keywords:
Fair Sharing, Deficit Round-Robin, Max-Min Fairness, Token-bucketAbstract
Providers of a Search as a Service (SaaS) environment must ensure that their users will not monopolize the service or use more than their fair share of resources. Fair sharing algorithms have long been used in computer networking to balance access to a router or switch, and some of these algorithms have also been applied to the control of queries submitted to search engine APIs. If a search query’s execution cost can be reliably estimated, fair sharing algorithms can be applied to the input of a SaaS API to ensure everyone has equitable access to the search engine.
The novelty of this paper lies in presenting a Single-Server Max-Min Fair Deficit Round Robin algorithm, a modified version of the Multi-Server Max-Min Fair Deficit Round Robin algorithm. The Single-Server Max-Min Fair Deficit Round Robin algorithm is compared to three other fair sharing algorithms, token-bucket, Deficit Round Robin (DRR), and Peng and Plale’s [1] Modified Deficit Round Robin (MDRR) in terms of three different usage scenarios, balanced usage, unbalanced usage as well as an idle client usage, to determine which is the most suitable fair sharing algorithm for use in regulating traffic to a SaaS API. This research demonstrated that the Single-Server Max-Min Fair DRR algorithm provided the highest throughput of traffic to the search engine while also maintaining a fair balance of resources among clients by re-allocating unused throughput to clients with saturated queues so a max-min allocation was achieved.
References
(1) A. Peng and B. Plale, “A Mulit-tenant Fair Share Approach to Full-text Search Engine”, in 2016 Seventh International Workshop on Data-Intensive Computing in the Clouds (DataCloud), pp. 40-50, doi: 10.1109/datacloud.2016.010.
(2) Amazon. “Amazon API Gateway Developer Guide: Throttle API requests for better throughput.” https://docs.aws.amazon.com/apigateway/latest/developerguide/api-gateway-request-throttling.html (accessed Nov. 17, 2020).
(3) M. Shreedhar, G. Varghese, “Efficient fair queuing using deficit round-robin,” IEEE/ACM Transactions on Networking, 4(3), pp. 375–385, doi: 10.1109/90.502236.
(4) J. Khamse-Ashari, G. Kesidis, I. Lambadaris, B. Urgaonkar, and Y. Zhao. “Max-Min Fair Scheduling of Variable-Length-Packet-Flows to Multiple Servers by Deficit Round-Robin,” in 2016 Annual Conference on Information Science and Systems (CISS), pp. 390-395, doi: 10.1109/CISS.2016.7460534.
(5) P. Dordal, An Introduction to Computer Networks. Chicago, Illinois: Loyola University Chicago, 2020. [E-book] Available: http://intronetworks.cs.luc.edu/
(6) I. Marsic, Computer Networks: Performance and Quality of Service. New Brunswick, New Jersey: Rutgers, 2013. [E-book] Available: https://www.ece.rutgers.edu/~marsic/books/CN/
(7) R. Jain, D. Chiu, and W. Hawe. “A Quantitative Measure Of Fairness And Discrimination For Resource Allocation In Shared Computer Systems,” ArXiv, Sept. 1998, doi: cs.NI/9809099.
(8) J. Nagle. “On Packet Switches with Infinite Storage,” IEEE Transactions on Communications, 35(4), pp. 435–438, doi: 10.1109/tcom.1987.1096782.
(9) A. Demers, S. Keshav, and S. Shenker. “Analysis and simulation of a fair queueing algorithm,” ACM SIGCOMM Computer Communication Review, 19(4), pp. 1–12, doi: 10.1145/75247.75248.
(10) P.E. McKenney, “Stochastic Fairness Queuing,” Internetworking: Research and Experience, 2(January), pp. 113–131.
(11) G. Varghese, Network Algorithmics: An Interdisciplinary Approach to Designing Fast Networked Devices. Amsterdam: Morgan Kaufmann, 2005, doi: 10.1016/B978-012088477-3/50017-5.
(12) W. Tong, J. Zhao, “Quantum Varying Deficit Round Robin Scheduling Over Priority Queues,” 2007 International Conference on Computational Intelligence and Security (CIS 2007), Computational Intelligence and Security, 2007 International Conference On, pp. 252–256. doi: 10.1109/CIS.2007.182.
(13) J. Heinanen and R. Guerin. “A Two Rate Three Color Marker”, IETF. https://tools.ietf.org/html/rfc2698 (accessed Jan. 11, 2021).
(14) C. Macdonald, N. Tonellotto, and I. Ounis. “Learning to predict response times for online query scheduling,” in Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’12), doi: 10.1145/2348283.2348367.
(15) E.L. Fridge and S. Bagui. “Estimating Query Timings in Elasticsearch,” submitted for publication.
(16) Datasets, Hathitrust. [Online]. Available: https://www.hathitrust.org/datasets
(17) “Apache JMeter.” Apache Software Foundation. https://https://jmeter.apache.org/ (accessed Sept. 15, 2020).
(18) AOL Search Data Collection, Archive.org. [Online]. Available: https://archive.org/details/AOL_search_data_leak_2006
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Sikha Bagui, Evorell Fridge
This work is licensed under a Creative Commons Attribution 4.0 International License.
