Research Articles Open Access

Performance and Fairness of Web API Rate-Limiting Algorithms under Bursty and Heterogeneous Traffic: A Controlled Event-Driven Study

Sadia Aslam * , Muhammad Umar Hameed
* Corresponding author: Sadia Aslam ( sadia.aslam@ucp.edu.pk )
Available online January 1, 2026
PDF

Abstract

An API quota such as 100 requests per second does not, by itself, specify how a limiter behaves around a burst or how admitted capacity is divided among competing clients. We examine that ambiguity with five implementations: fixed-window counting, an approximate sliding-window counter, an exact sliding-window log, a global token bucket, and an equal-share per-client token bucket. The same event traces are replayed through every limiter. The workloads include Poisson arrivals, boundary-aligned and synchronized bursts, heterogeneous clients, and a flash crowd. The global policies use a nominal rate of 100 requests per second. In the boundary experiment, two 100-request bursts were placed 20 ms apart on opposite sides of a fixed-window boundary. Fixed window admitted 200 requests within one rolling second. The exact sliding log and per-client token bucket admitted 100, whereas the approximate counter admitted 101 and the global token bucket 102. A second experiment used 16 clients at 6 requests/s and four clients at 25 requests/s. Jain's index remained between 0.6234 and 0.6258 for the global limiters, while the equal-share policy reached 0.9995 with 97.20 requests/s of admitted throughput. The same static allocation was inefficient when the 16 lower-rate clients had only 2 requests/s, with admitted throughput dropping to 52.20 requests/s as their unused shares were not reallocated. The measurements thus consider rolling-window compliance, client allocation and utilization as separate features of an API rate-limit policy.

Keywords

API rate limiting token bucket sliding window fairness burst traffic

Introduction

An API provider might impose a limit, for example, “100 requests per second,” but that statement leaves some part of the policy unspecified. A client can exceed a limit, as defined by RFC 6585 and the server can then return status code 429. The RFC does not specify how the client is identified, nor how requests are counted. Two implementations can therefore advertize the same numerical quota, but still pass different amounts of traffic to the protected service.

This difference is more evident for burst traffic. Fixed window counting is tied to a clock boundary, so a request arriving just before and one just after a reset will be charged to different counters even if they are temporally close. Sliding-window schemes avoid that particular reset effect, but an exact log keeps more state, as recent timestamps must be kept. Token buckets have yet another rule: stored tokens are allowed to absorb a short burst while the refill rate controls sustained admission. The basic ideas stem from prior work on leaky-bucket regulation, generalized processor sharing and fair resource allocation . However , in an API , the regulated unit is usually a request , not a packet or a virtual circuit .

Capacity sharing causes another problem. A global limiter can keep aggregate admission near a target, while allowing a few high-rate clients to consume a large fraction of that capacity. Such concentration is important in service chains, where overload and long tail behavior can propagate across dependent requests . Per-client limits can isolate callers. But a fixed partition also has a cost: capacity assigned to an idle client cannot be used elsewhere unless the policy includes redistribution. Related problems are studied with more general system feedback in (Distributed enforcement), (fairness-throughput scheduling), (adaptive Web admission), and (microservice overload control). A traditional API limiter is typically less complex than these mechanisms, but the allocation choice still exists.

In a few studies the setting of the API is approximated. El Malki et al. model the impact of rate limits on microservice reliability, while Serbout et al. discuss design choices for rate-limit method, scope and granularity. Noah uses reinforcement learning to adjust the limits as the microservice behavior changes. Other works statistically estimate the throttling limits or adapt clients such that repeated HTTP 429 responses are reduced . The studies are concerned with the selection, adaptation or response to a boundary. We are more concerned with a more basic question: what traffic is counted under the underlying counting rule and scope before adaptation is applied?

We evaluate five configurations on the same timestamped traces: fixed window, approximate sliding counter, exact sliding log, global token bucket, and equal-share per-client token bucket. Each limiter has the same nominal rate, only the admission semantics or policy scope varies. The experiments differ in the offered load and traffic shape. We record acceptance ratio, maximum count admitted in a rolling one second interval, Jain’s allocation index and admitted throughput. The analysis also follows the share taken by four high-rate clients, recovery on a digital flash-crowd trace, and processing cost of the provided Python implementation. The per-client token bucket is intentionally simple and is used to reveal the impact of static isolation, not as a comprehensive fairness scheduler.

The experiments are designed to address three questions. Does the limiter roll one second ceiling during a burst? How does a global quota divide when client demand varies and how much capacity is stranded by fixed equal shares? The event-driven design is motivated by the fact that these questions concern admission semantics. Network transfer, HTTP parsing, backend execution and gateway latency are outside the model, and no end-to-end latency claim is made.

Organization of the paper is given below: Section 2 reviews related work. Section 3 describes the limiter model and measures. The workload protocol is described in Section 4 and the measurements in Section 5. Limitations of the study and design implications are discussed in Sections 6 and 7.

Complete Article

The complete article, including all figures, tables, equations and algorithms, is available in the official publication PDF.

Conclusion

Five rate-limit configurations were evaluated with the same event traces and a nominal capacity of 100 requests/s. Their behavior was not interchangeable. In the boundary test, fixed window admitted 200 requests inside one rolling second. The exact sliding log and equal-share per-client token bucket admitted 100, the approximate sliding counter 101, and the global token bucket 102. The difference comes from the policy semantics applied to the same 20 ms-separated bursts rather than from a change in offered traffic.

Client demand changed the allocation result as well. With all 20 clients above their equal share, Jain’s index stays near 0.62 for the global policies, and the four high-rate clients receive about 51% of admitted traffic. The static per-client token bucket changes those values to 0.9995 and 20.71% respectively, while admitting 97.20 requests/s. The same policy allows 52.20 requests/s only when most clients are below their allocated share, because unused quota remains with the low-demand clients.

There is no configuration that is preferred by every metric in this benchmark. Which is right depends on what the API policy is meant to control: a strict rolling-window count, a permitted burst budget, aggregate backend admission, or separation among clients. The provided traces and code make those differences reproducible at the admission rule level. The next logical step is to replay these workloads through production gateways, then add work-conserving redistribution, weighted tenant shares, and replicated rate-limit state so we can measure the costs of consistency directly.

References

  1. M. Nottingham and R. T. Fielding, “Additional http status codes, ” Internet Engineering Task Force, Tech. Rep. RFC 6585, Apr. 2012.
  2. J. S. Turner, “New directions in communications (or which way to the information age?), ” IEEE Communications Magazine, vol. 24, no. 10, pp. 8–15, Oct. 1986.
  3. M. Sidi, W.-Z. Liu, I. Cidon, and I. Gopal, “Congestion control through input rate regulation, ” IEEE Transactions on Communications, vol. 41, no. 3, pp. 471–477, Mar. 1993.
  4. A. K. Parekh and R. G. Gallager, “A generalized processor sharing approach to flow control in integrated services networks: The single-node case, ” IEEE/ACM Transactions on Networking, vol. 1, no. 3, pp. 344–357, Jun. 1993.
  5. A. J. Demers, S. Keshav, and S. Shenker, “Analysis and simulation of a fair queueing algorithm, ” in Proceedings of ACM SIGCOMM, 1989, pp. 1–12.
  6. J. Dean and L. A. Barroso, “The tail at scale, ” Communications of the ACM, vol. 56, no. 2, pp. 74–80, Feb. 2013.
  7. B. Raghavan, K. Vishwanath, S. Ramabhadran, K. Yocum, and A. C. Snoeren, “Cloud control with distributed rate limiting, ” in Proceedings of ACM SIGCOMM, 2007, pp. 337–348.
  8. D. Abendroth, M. E. Eckel, and U. Killat, “Solving the trade-off between fairness and throughput: Token bucket and leaky bucket-based weighted fair queueing schedulers, ” AEU - International Journal of Electronics and Communications, vol. 60, no. 5, pp. 404–407, 2006.
  9. M. Welsh and D. Culler, “Adaptive overload control for busy internet servers, ” in 4th USENIX Symposium on Internet Technologies and Systems (USITS 03). 1em plus 0.5em minus 0.4em USENIX Association, Mar. 2003, pp. 43–57.
  10. N. Bartolini, G. Bongiovanni, and S. Silvestri, “Self-* through self-learning: Overload control for distributed web systems, ” Computer Networks, vol. 53, no. 5, pp. 727–743, Apr. 2009.
  11. H. Zhou, M. Chen, Q. Lin, Y. Wang, X. She, S. Liu, R. Gu, B. C. Ooi, and J. Yang, “Overload control for scaling wechat microservices, ” in Proceedings of the 9th ACM Symposium on Cloud Computing, 2018, pp. 149–161.
  12. I. Cho, A. Saeed, J. Fried, S. J. Park, M. Alizadeh, and A. Belay, “Overload control for microsecond-scale rpcs with breakwater, ” in 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). 1em plus 0.5em minus 0.4em USENIX Association, 2020, pp. 299–314.
  13. J. Park, J. Park, Y. Jung, H. Lim, H. Yeo, and D. Han, “Topfull: An adaptive top-down overload control for slo-oriented microservices, ” in Proceedings of the ACM SIGCOMM 2024 Conference, 2024, pp. 876–890.
  14. J. Xing, A. Giannoukos, P. Loh, S. Wang, J. Qiu, H. M. Demoulin, K. Kallas, and B. C. Lee, “Rajomon: Decentralized and coordinated overload control for latency-sensitive microservices, ” in 22nd USENIX Symposium on Networked Systems Design and Implementation (NSDI 25). 1em plus 0.5em minus 0.4em USENIX Association, Apr. 2025, pp. 21–36.
  15. A. E. Malki, U. Zdun, and C. Pautasso, “Impact of api rate limit on reliability of microservices-based architectures, ” in 2022 IEEE 16th International Conference on Service-Oriented System Engineering (SOSE), 2022, pp. 19–28.
  16. S. Serbout, A. E. Malki, C. Pautasso, and U. Zdun, “Api rate limit adoption: A pattern collection, ” in Proceedings of the 28th European Conference on Pattern Languages of Programs, 2023, pp. 1–20.
  17. Z. Li, H. Sun, Z. Xiong, Q. Huang, Z. Hu, D. Li, S. Ruan, H. Hong, J. Gui, J. He, Z. Xu, and Y. Fang, “Noah: Reinforcement-learning-based rate limiter for microservices in large-scale e-commerce services, ” IEEE Transactions on Neural Networks and Learning Systems, vol. 34, no. 9, pp. 5403–5417, Sep. 2023.
  18. A. Arman, M. Monticelli, D. Firmani, F. Leotta, and M. Mecella, “An adaptive toolbox for computing throttling rate limits in web apis, ” IEEE Transactions on Services Computing, vol. 19, no. 1, pp. 141–152, 2026.
  19. B. Farkiani, F. Liu, and P. Crowley, “Rethinking http api rate limiting: A client-side approach, ” in 2026 IEEE 23rd Consumer Communications and Networking Conference (CCNC), Jan. 2026, pp. 1–7.
  20. R. Jain, D.-M. Chiu, and W. Hawe, “A quantitative measure of fairness and discrimination for resource allocation in shared computer systems, ” Digital Equipment Corporation, Tech. Rep. DEC-TR-301, Sep. 1984.
  21. H. S. Kim, E.-C. Park, and S. W. Heo, “A token-bucket based rate control algorithm with maximum and minimum rate constraints, ” IEICE Transactions on Communications, vol. E91-B, no. 5, pp. 1623–1626, May 2008.
  22. A. Saeed, N. Dukkipati, V. Valancius, V. T. Lam, C. Contavalli, and A. Vahdat, “Carousel: Scalable traffic shaping at end hosts, ” in Proceedings of ACM SIGCOMM, 2017, pp. 404–417.
  23. M. Welsh, D. Culler, and E. Brewer, “Seda: An architecture for well-conditioned, scalable internet services, ” ACM SIGOPS Operating Systems Review, vol. 35, no. 5, pp. 230–243, Oct. 2001.
  24. D. Cotroneo, R. Natella, and S. Rosiello, “Draco: Distributed resource-aware admission control for large-scale, multi-tier systems, ” Journal of Parallel and Distributed Computing, vol. 192, p. 104935, Oct. 2024.
  25. R. T. Fielding, M. Nottingham, and J. Reschke, “Http semantics, ” Internet Engineering Task Force, Tech. Rep. RFC 9110, Jun. 2022.
58 31

Similar Articles

You may also start an advanced similarity search for this article.