Fair queueing is a service scheduling discipline to pursue the fairness among users in packet communication networks. Many fair queueing algorithms, however, have problems of computational overhead since the central scheduler has to maintain a certain performance counter for each flow of user packets based on the global virtual time. Moreover, they are not suitable for wireless networks with high probability of input channel errors due to the lack or complexity in the compensation mechanism for the recovery from the error state. In this paper, we propose a new, computationally efficient, distributed fair queueing scheme, which we call Channel-Aware Throughput Fair Queueing (CATFQ), that is applicable to both wired and wireless packet networks. In our CATFQ scheme, each flow is equipped with a counter that measures the weighted throughput achievement while it has a backlog of packets. At the end of every service to a packet, the scheduler simply selects a flow with the minimum counter value as the one from which a packet is served next. We show that the difference between any two throughput counters is bounded. Our scheme significantly reduces the scheduler's computational overhead and guarantees fair throughput for all flows. For wireless networks with error-prone channels, the service chance lost in bad channel condition is compensated quickly as the channel recovers. Our scheme suppresses the service for leading flows, brings short-term fairness for flows without channel errors, and achieves long-term fairness for all flows. These merits are verified by simulation.

This letter proposes a new weighted fair queueing algorithm, which adjusts dynamically each flow's service probability according to its weight and average packet length and then uses the service probability parameters to implement fair queueing. This solves the main drawback of traditional weighted fair queueing algorithms--the packet-based tracing of weight parameters. In addition, this letter proposes a novel service probability calculation method which solves the unfairness problem induced by the variable packet length.

Self-Clocked Fair Queueing (SCFQ) and Credit-Based Fair Queueing (CBFQ) are well-known fair scheduling schemes for packet-switched network. In this paper, it is shown that SCFQ and CBFQ are equivalent in selecting packets to transmit. For this, we modified the per-packet service tag based SCFQ algorithm to an equivalent per-session service tag based algorithm, SCFQ+, and showed that the service tags for SCFQ+ and CBFQ evolve identically.

Supporting Quality of Service (QoS) over the Internet is a very important issue and many mechanism have been already devised or are under way towards achieving this goal. One of the most important approaches is the class-based architecture, which provides a scalable mechanism for QoS support in a TCP/IP network. Class-based service differentiation can be realized without resource reservation, admission control and traffic policing. However, the resulting services are only relative. While it is, in principle, not feasible to provision for absolute guarantees without admission control and/or traffic policing, such a service can be reasonably well emulated using adaptive rate allocation at the link scheduler of routers. In this paper, we propose mechanism for link scheduler of router that achieve emulated absolute and other relative guarantees using dynamic weighted fair queueing (DWFQ) combining with class packet dropping. The weights of DWFQ are frequently adjusted to current load conditions and based on prediction of realistic class traffic. These mechanisms can realize many approaches to QoS guarantees and class-based differentiation.

The recent Internet needs a network structure and traffic engineering that can support various applications requiring differentiated traffic processing and a high quality of service. The extension of the Internet from wired to wireless systems that generate location-dependent and burst errors has made the support of good services more difficult with existing packet scheduling algorithms. Accordingly, this paper proposes a wireless differentiated service packet scheduling (WDSPS) algorithm that can provide reliable and fair services in differentiated wireless internet service networks. As such, the proposed scheduling algorithm solves the HOL blocking problem within a class packet queue that occurs in a wireless network, supports differentiated services for each class defined in a differentiated service network, and facilitates gradual and efficient service compensation not only among classes but also among flows within a class, thereby preventing a monopoly by one class or one flow. Simulations confirmed that the proposed WDSPS scheduling algorithm could provide the required QoS differentiation between classes and enhanced the service throughput under various wireless network conditions.

Fair scheduling algorithms have been proposed to tackle the problem of bursty and location-dependent errors in wireless packet networks. Most of those algorithms ensure the fairness property and guarantee the QoS of all sessions in a large-scale cellular network such as GSM or GPRS. In this paper, we propose the Weighted-Sacrificing Fair Queueing (WSFQ) scheduling algorithm for small-area and device-limited wireless networks. WSFQ slows down the growth of queue length in limited-buffer devices, still maintains the properties of fairness, and guarantees the throughputs of the system. Moreover, WSFQ can easily adapt itself to various kinds of traffic load. We also implement a packet-based scheduling algorithm, the Packetized Weighted Sacrificing Fair Queueing (PWSFQ), to approach the WSFQ. WSFQ and PWSFQ are evaluated by comparing with other algorithms by mathematical analysis and simulations.

This paper proposes a novel method of identifying the design parameters for a practical implementation of the fair queueing discipline, which is capable of class-level delay control. The notion of class weight is introduced at first, and then the session weights are determined. This two-phase approach is favorable in terms of the scalability;that is, the overall complexity is dependent upon the number of classes only. We propose a packet scheduler referred to as the DPS (Delay-centric Processor Sharing) scheme which employs those design parameters to deliver class-wise delay bound services. The associated admission policy for delay guarantee is also derived. System analysis and derivation of the parameters have their origins in the understanding of the so-called system equation, which describes the dynamics of the class-level service share. The proposed design parameters are QoS-aware in that they are consistently refined depending on the system status. Several numerical and simulation results show that the DPS scheme is advantageous over other ones in terms of both resource efficiency and the robustness. Concerning the scalability, we show that an alternative tagging process of the DPS scheme is implementable with O(1) complexity with no significant degradation in delay performance.

This paper proposes an efficient fair queuing algorithm, called Medium Starting Potential Fair Queuing (MSPFQ), which has O(1) complexity for the virtual time computation while it has delay and fairness properties similar to Starting-Potential Fair Queueing (SPFQ). The key idea of MSPFQ algorithm is that it recalibrates the system virtual time to the medium value of the minimum possible virtual start times of HOL packets in each backlogged session. We show that MSPFQ belongs to the class of Rate-Proportional Server (RPS). In addition, we analytically prove that our algorithm has good delay and fairness properties.

In this paper, we propose a packet-scheduling algorithm, called the Class-level Service Lagging (CSL) algorithm, that guarantees multiple delay bounds for multi-class traffic in packet networks. We derive the associated schedulability test conditions, which are used to determine call admission. We first introduce a novel implementation of priority control, which has a conventional and simple form. We show how the efforts to confirm the logical validity of that implementation are managed to reach the definition of the CSL algorithm. The priority control is realized by imposing class-level unfairness in service provisioning, while the underlying service mechanism is carried out using the notion of fair queueing. The adoption of fair queueing allows the capability to maintain the service quality of the well-behaving traffic even in the presence of misbehaving traffic. We call this the firewall property. Simulation results demonstrate the superiority of the CSL algorithm in both priority control and firewall functionality. We also describe how the CSL algorithm is implementable with a computational complexity of O(1). Those features as well as the enhanced scalability, which results from the class-level approach, confirm the adequacy of the CSL algorithm for the fast packet networks.

In this paper, we propose a new fair queueing algorithm to improve cell delay variation (CDV) for real-time service categories and to make efficient use of system resources for multimedia traffic in high speed ATM networks. The proposed algorithm is called the delay variation-based fair queueing (DVFQ) algorithm, which is based on per-VC queueing to improve CDV and fairness for each VC of real-time services such as CBR and rt-VBR. In DVFQ algorithm, we define two fairness indexes, which indicate the degree of the fairness of CDV at the rate of each VC, and the degree of impartially sharing the bandwidth between the scheduled cells for each VC. The simulation results for both heavily and lightly loaded conditions show that DVFQ algorithm provides better performances in terms of the CDV, the CDV fairness, and the service fairness than those of FCFS for real-time service.

WFQ (Weighted Fair Queueing) is an ideal scheduling algorithm in terms of delay and fairness. However, timestamp computation complexity makes the implementation difficult. In this paper we propose an efficient and simple fair queueing algorithm, called Emulated Weighted Fair Queueing (EWFQ), which has O(1) complexity for the virtual time computation while it almost perfectly emulates the delay and fairness properties of WFQ. The key idea of EWFQ is that it calibrates the system virtual time only at the end of each packet transmission, while it calculates the system virtual time for a newly arrived packet by employing a linear approximation. By doing so, EWFQ has a rate-proportional property. EWFQ can be implemented in a router for supporting the differential and integrated services.

In the past, a number of scheduling algorithms that approximate GPS, such as WFQ, have been proposed and have received much attention. This class of algorithms provides per-flow QoS guarantees in terms of the bounded delay and minimum bandwidth guarantee. However, with O(log N) computational cost for each new arrival scheduling, where N is the number of backlogged flows, these algorithms are expensive to implement (e.g., in terms of scalability). Moreover, none of them addresses the issues of delay distribution and jitter. In this paper, we propose a new traffic scheduling discipline called Jitter Control Frame-based Queueing (JCFQ) that provides an upper bound for delay jitter in the case of rate-controlled connections, such as packet video streams and IP telephony, while guaranteeing bounded delay and worst-case fair weighted fairness, such as in the WF2Q algorithm, but with O(1) complexity in selecting the next packet to serve, assuming that the number of flows is fixed. Three different algorithms for slot or service order assignment between flows are proposed: Earliest Jitter Deadline First (EJDF), Rate Monotonic (RM) and Maximum Jitter First (MJF). In these algorithms, delay jitter is formulated into the virtual finish time calculation. We compare the fairness, delay and jitter performance of the JCFQ with that of the MJF algorithm with WF2Q via simulation. The results show that with proper choice of the slot size, JCFQ can achieve better flow isolation in delay distribution than can WF2Q.

This paper proposes a new scheduling algorithm named TWFQ (Two-phased Weighted Fair Queueing) not only to maintain the fair utilization of available bandwidth but also to improve the performance of CDV and cell loss probability. The TWFQ algorithm makes use of the cell inter-arrival time of each connection for determining the cell service order among connections, which contributes to get a small CDV. To achieve low cell loss probability, the TWFQ allows connections, which suffer from the more bursty input traffic, to send the cell with more opportunities by using two scheduling phases. Through simulations, we show that the proposed algorithm achieves good performance in terms of CDV and cell loss probability, while other performance criteria are preserved in an acceptable level.

To implement the PGPS packet scheduling algorithm in high speed networks is more difficult since it is based on real time simulation of an equivalent fluid-model system leading to a higher implementation time complexity. A modified approach to PGPS is the SCFQ scheme. This scheme is easy to implement, but has an increasing end-to-end delay bound. The VC packet scheduling algorithm provides the same end-to-end delay bound as PGPS does, but has the disadvantage of unfairness. As SCFQ, SFQ is much easier to implement than PGPS and achieves the same fairness, but has a higher end-to-end delay bound than PGPS. We propose a new packet scheduling algorithm, called Minimum Starting-tag Fair Queueing (MSFQ), which assigns the virtual time to be the minimum starting tag over all backlogged connections. MSFQ is much easier to implement than PGPS and provides the same end-to-end delay bound for each connection and fairness as PGPS. In this paper, we will show the end-to-end delay bound and fairness of MSFQ and compare 5 rate-based packet scheduling algorithms including PGPS, VC, SCFQ, SFQ, and MSFQ focusing on end-to-end delay bound, fairness, and implementation time complexity.

This paper discusses two approaches to statistical multiplexing: rate envelope multiplexing, allowing resource sharing with small delays for low peak rate connections, and rate sharing, based on the use of large multiplexer buffers to ensure high link utilization for high speed data traffic. We argue that the weighted fair queueing scheduling algorithm provides an efficient means for combining both kinds of multiplexing in the B-ISDN. A feasible implementation known as Virtual Spacing is outlined. We illustrate the flexibility of the proposed scheme by showing how different service categories could be provided.