A Comparison of Fair Sharing Algorithms for Regulating Search as a Service API

Keywords: Fair Sharing, Deficit Round-Robin, Max-Min Fairness, Token-bucket

Abstract

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.

Author Biographies

Dr Sikha Bagui, University of West Florida

Dr. Sikha Bagui is Professor and Askew Fellow in the Department of Computer Science, at The University West Florida, Pensacola, Florida. Dr. Bagui is active in publishing peer reviewed journal articles in the areas of database design, data mining, BigData and Big Data analytics, and machine learning. Dr. Bagui has worked on funded as well unfunded research projects and has over 70 peer reviewed publications. She has also co-authored several books on database and SQL. Bagui also serves as Associate Editor and is on the editorial board of several journals.

Evorell, University of West Florida

Dr. Evorell Fridge is a web applications engineer and adjunct instructor in The Department of Computer Science at the University of West Florida in Pensacola, Florida. He enjoys introducing students to full-stack software development and researching topics in information retrieval and big data.

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

Published
2021-02-11
How to Cite
Bagui, S., & Fridge, E. (2021). A Comparison of Fair Sharing Algorithms for Regulating Search as a Service API. Transactions on Networks and Communications, 8(6), 16-34. https://doi.org/10.14738/tnc.86.9633