12/01/1995 09:00 AM
Computer Engineering
Although Weighted Fair Queueing is regarded as an ideal scheduling algorithm in terms of its delay and fairness properties, its computation complexity is asymptotically linear in the number of connections serviced by the scheduler, thus making its implementation prohibitively expensive in high-speed networks. An algorithm that combines the delay and fairness bounds of Weighted Fair Queueing with 0(1) timestamp computations had remained elusive so far. In this paper, we present two novel scheduling algorithms that have 0(1) complexity for timestamp computations, and provide the same bounds on end-to-end delay and buffer requirements as those of Weighted Fair Queueing. The first algorithm, Frame-based Fair Queueing, uses a framing mechanism to periodically re-calibrate a global variable tracking the progress of work in the system, limiting any short-term unfairness to within a frame-period. The second algorithm, Starting Potential-based Fair Queueing (SPFQ), performs the re-calibration at packet boundaries, resulting in a fairness bound that is equal to that of Weighted Fair Queueing, still maintaining the 0 (1) timestamp computations. This improved fairness bound is achieved at the expense of a slightly higher implementation cost. Thus, SPFQ is attractive over FFQ in those applications where its improved fairness properties justify the additional implementation cost. The algorithms may be used in both general packet networks with variable packet sized and in Asynchronous Transfer Mode (ATM) networks. Both algorithms are based on the general framework of rate-proportional servers (RPS) introduced in [11]. Details of hardware implementation of both algorithms are presented for use in an ATM network.
