I. Introduction
For a long time, round-robin schedulers have been found appealing for their simplicity and corresponding efficient implementation as well as their inherent fairness [2] (see [3] for an early reference). Weighted round robin (WRR) is a frequently used scheduling algorithm in packet-switched networks as well as in real-time processing systems to provide a different resource allocation among flows (or tasks). In its basic version, sometimes called plain WRR, we (conceptually) have a queue for each flow at a server and service is provided in rounds; in each round, a flow receives the opportunity to send packets consecutively. The term weighted round robin was coined in [4] in the context of ATM (i.e., a network with constant packet sizes), where also some modifications, such as interleaving, were suggested. WRR has been considered intensively in the literature on communication networks: e.g., investigating variants such as multi-class or multi-server WRR [5], [6]; or, in applications such as in the IEEE Standard 802.1Q [7], load balancing of cloud infrastructures [8], [9], or networks on chip (NoC) [10], [11]; and found usage in real-world equipment, e.g., in Ethernet switches [12]. In contrast to another popular round-robin scheduler, deficit round robin (DRR) [13], WRR does not assume that the size of the head-of-the-line packet is known at each queue. Therefore, it is also used in distributed queueing scenarios, for instance, as the uplink scheduler in an IEEE Standard 802.16 network [14].
State-of-the-art service curves for wrr and our service curve under constrained cross-traffic.