QoS Differentiated and Fair Packet Scheduling in Broadband Wireless Access Networks

Algorithms of First-Come-First-Served (FCFS) and Round Robin (RR) are first developed for wired networks. Their original versions and improved versions (e.g., Weighted Round Robin and Deficit Round Robin [4]) are underlying schemes for wireless networks. Another well-known algorithm is Generalized Processor Sharing (GPS) [5], which is ideal and unimplementable in packet-based networks. Many other scheduling algorithms try to approximate GPS as far as possible. The merit of these wired scheduling algorithms is their simplicity and ease of implementation. But if directly used in BWA networks, these algorithms cannot achieve high bandwidth utilization and promise fairness guarantee.

The classical two-state Gilbert-Eilliot (GE) model [6, 7] is firstly used to model the wireless link variation. The channel is simply described to be either in "good" or in "bad" state in this model. A survey of this class of scheduling algorithms can be found in [1]. Work in [8] devised Idealized Weight Fair Queuing (IWFQ) algorithm. In [9], Channel-condition Independent Fair Queueing (CIF-Q) algorithm was put forward. Both algorithms of IWFQ and CIF-Q need to simulate a virtual error-free fair queueing system and try to schedule packets in the same order as the ideal reference system does. IWFQ and CIF-Q differ in the way they compensate the lagging flows. Wong et al. [10] presented Token Bank Fair Queueing (TBFQ) algorithm, which uses token pools and token bank to keep track of the service status of each flow and dynamically regulate the priorities of the flows to occupy the channel resource. All these three algorithms achieve good performance tradeoff among the three performance issues aforementioned. But they only work under the GE channel model, which is too coarse to characterize the practical variability of the wireless channel conditions.

Some researchers considered variable-rate transmission in scheduling algorithms [11‐15]. The Modified Largest Weighted Delay First (M-LWDF) algorithm [11] schedules packets according to a simple but effective constructed metric. The scheme was proved analytically to be throughput optimal. But it does not explicitly guarantee any fairness. The algorithm of Jalali et al. [12] was proposed to satisfy the so-called proportional fairness; the algorithm of Liu et al. [13] tried to maximize the long-term average total throughput for a given time fraction; the algorithm of Borst and Whiting [14] was made to be Pareto-optimal. The algorithm of Park et al. [15] selects user for transmission based on the cumulative distribution function (CDF) of the user rates.

Besides the above three classes of scheduling algorithms, researchers also consider standard-compatible schemes recently. In [16], a scheduling algorithm which is practical and compatible to the IEEE 802.16 standard is proposed. It provides QoS support in terms of bandwidth and delay bounds for all types of traffic classes as defined by the standard.

By summarizing the above-mentioned scheduling algorithms, we notice that most of the algorithms are designed based on heuristic methods. Either introducing the virtual/ideal service models as reference systems [8, 9] or defining some key metrics as criteria [11‐14], many existing algorithms are built on the observation, judgement, intuition, and experience of the designers. Although heuristic algorithms have the merit of simplicity, their underlying drawbacks are twofold. Firstly, heuristic algorithms are generally proposed with respect to some given special outside conditions, which means that they are less of adaptivity. When the practical conditions do not match the provided ones, it is hard for heuristic algorithms to maintain their scheduling performance. Secondly, designing a heuristic scheduling algorithm is easy when the problem is relatively simple but could be rather tough when the scheduling environments and objectives become complicated. For packet scheduling problem in BWA networks, the scheduler is required to consider three main objectives simultaneously and, meanwhile, combat highly variable channels and unknown traffic models. Such a complicated scheduling problem is far out of the ability of a heuristic algorithm to handle.

To overcome the disadvantages of heuristic algorithms, we propose in this paper a learning-based algorithm for the packet scheduling problem in BWA networks. The proposed algorithm has in-built capacity of studying from outside environment and adapting system parameters according to the performance requirements. This attractive feature makes the proposed algorithm appropriate for the scheduling problem in BWA networks. More specifically, when this learning-based algorithm is applied in BWA networks, we only need to translate the scheduling objectives to the system reward (or cost) and then connect the scheduling problem with the ingredients of the solution framework. Little attention should be paid on the details of the entire scheduling process such as how to dynamically adapt the scheduler for the optimal performance. Because the scheduler has potential ability of self-training, it could automatically tuning itself towards an optimal system reward (or cost) according to the actual environment. Actually, the works in [13, 14] have realized that fixed and unadaptable scheduling schemes are incapable in complicated scheduling problem. Undetermined constants are integrated into the key metrics at the system initialization phase so that the scheduler could adjust its strategy at some extent. Nonetheless, the learning abilities of these algorithms are very limited, and they should still be looked on as heuristic algorithms.

In a general shared-channel wireless network, the scheduler should make scheduling decisions based on the knowledge of the system state, including the queueing delay of all packets, the channel conditions of all sessions, and the practical service rates of all sessions. Suppose that there are sessions in the system, and each session has a queueing buffer that can store packets at the most. (Without loss of generalization, we assume that all queues can store same number of packets. A more practical assumption may be that the buffer length of the th session is in packets.) At time , the queueing delay of the th packet in the th session is denoted by . For the th session, let denote the maximum available channel rate at time , the practical average service rate at time , and the nominal service rate (negotiated when the session is setup). We now connect the packet scheduling problem with the main ingredients of the Semi-Markov Decision Process (SMDP) as follows.

The definition of cost function directly determines the performance of the scheduling algorithm. In our problem, we restrict the cost function of interest to have the following important properties.

Our discussion of the cost function starts from a draining problem, where given a number of packets in the system, and assuming no more packet arrivals, the scheduler should try to arrange the order of packet transmissions so that the total cost is minimized. Draining problem is indeed a simplified version of the original scheduling problem. By assuming that there is no new packet arrival, draining problem is much more analyzable than the original scheduling problem. Here, we consider a draining problem with the following setup. There are sessions in the system. The initial queue length of session is in packets, . At the beginning, the queueing delay of all the packets is supposed to be zero. We separately define three different forms of cost function below. Each definition actually involves one performance objective.

A common approximation architecture of RL is shown in Figure 3. The architecture consists of two components: the feature extractor and the function approximator. The feature extractor is used to produce a feature vector , which is capable of capturing the most important aspects of state . Features are usually handcraft, based on human intelligence or experience. Our choice of the feature vector will be presented shortly.

The function approximation architectures could be broadly categorized into two classes: the nonlinear and the linear structures. One typical nonlinear architecture is the multilayer perceptron or feedforward neural network with a single hidden layer (see, e.g., [22]). Under this architecture, the output approximating function is the nonlinear combination of input feature vector with internal tunable weight vector . This architecture is powerful because it can approximate arbitrary functions of . The drawback, however, is that the dependence on is nonlinear, and tuning can be time-consuming and unreliable.

Alternatively, a linear feature-based approximation architecture [22] is much simpler and easier to implement, in which the output approximating function is the linear combination of the input feature , given by

where the superscript represents transpose. In this paper, we choose linear approximation architecture in the RL framework.

Since the linear combination of feature vector should approximate the optimal differential average cost, the definition of feature vector explicitly relates to the definition of cost function. As (10) has shown, the cost at each stage is determined by the weighted queueing delay of the packet being assigned to transmit. Thus, the components of the feature vector should be defined with respect to all packets in the system, each component corresponding to one packet. Let denote the packet size of session . At stage , the remaining waiting time for the th packet in session could be estimated by , where is the current actual service rate of session . Thus, the feature component with respect to the th packet of session is defined by

Here, the item could be viewed as the estimation of the queueing delay for the th packet in session . Note that if provides an accurate prediction of the service rate of session , (13) coincides well with (10) and the loss of optimality of the linear architecture could be sufficiently small. Extending (12) yields

where is the number of packet in session ; is the parameter variable associated with feature . The total number of tunable parameters in is equal to .

After establishing the approximating architecture, we employ the technique of Temporal-Difference (TD) learning [2] to perform online parameter tuning. The algorithm starts with an arbitrary initial parameter vector and improves the approximation as more and more state transitions are observed. At each stage, a greedy decision is made based on current and . Specifically, the decision should be made by

where is the estimation of state at the next stage. The computation of is trivial if we simply assume that no packet arrives during the current stage. More concretely, let denote the number of packets in session . At the beginning of a stage, given the state

if no more packet arrives before the current transmission completes, then the state at the end of current stage (i.e., the beginning of next stage) is estimated by

where for , , ; for , , .

In the process of parameter tuning, the update of parameter vector and scalar is carried out stage by stage, according to

where and are small step size parameters, and is called temporal difference. Generally, and should satisfy the following conditions:

In (18), the temporal difference is found as

Note that we use the linear approximation structure as (12), which leads to in (18). We can see the benefit of using the linear feature-based approximation architecture which significantly reduced the complexity of gradient computation in (18). Figure 4 presents the flow chart of the proposed Reinforcement Learning-based Scheduling (RLS) algorithm, which summarizes the main operations of the algorithm.

We consider three classes of traffic for typical BWA networks, including audio, video, and data traffic flows. As listed in Table 1, there are five sessions. All traffic flows are generated based on the models presented in [23]. Note that the traffic models are especially proposed for one of the BWA standards IEEE 802.16. In Table 1, the link conditions of audio, video, and data-1 are supposed to be stably full-rate, while link conditions of data-2 and data-3 are assumed to suffer drastic variation. More specifically, link variability of data-2 and data-3 sessions is characterized by a six-state Markov channel model [18, 19]. Transmission rates of link states are, respectively, 100, 80, 60, 40, 20, 0 percents of the full channel rate (2 Mbps). The steady-state probability vector for error pattern-1 is , while the one for pattern-2 is . The channel state transition probabilities of the data sessions are listed in Table 2.

Generally, audio and video traffic has higher priority than data traffic, due to the requirement of realtime transmission. Thus, we set the priority factors of the audio and video traffic flows as , that is, , and the priority factors of data traffic flows as , that is, . In the aspect of providing fair service, data traffic is usually more sensitive than audio and video traffic. This is because data traffic flows, such as FTP and e-mail, are generally served in the mode of best effort (BE). There is no guarantee how much service the system has to provide for these traffic flows. Without consideration of fair service, multiple data traffic flows in a same system may receive fairly different amounts of service, due to the different wireless channel conditions. Hence, we set larger fairness factors for the data traffic flows. The fairness factors of audio and video traffic are set as , that is, , and the fairness factors of data traffic are set as , that is, .

The first experiment investigates the convergence of RLS in the procedure of parameter tuning. Since the optimal average cost is the most important metric of the system performance, the variation of reflects the convergence of the learning algorithm. We run the simulation and record the value of . The step size of the learning algorithm should be set before the simulation. As mentioned in Section 4, the setting of step size parameters and should satisfy the conditions of (19). One efficient way to determine these parameters is to set the value of step size roughly inversely proportional to the stage number (or running time) [22]. Let represent the step size with respect to feature component at stage . We set

and the step size with the approximate optimal average cost at stage :

After running for 800 seconds, we record the variation of and plot as curve in Figure 5.

It is observed that RLS converges very fast in the procedure of parameter tuning. The approximate optimal average cost has reached a relatively stable value after 100 seconds. Although keeps varying as time goes by, the fluctuation is still in an acceptable range. It is clear that the learning algorithm has converged. For comparison, we also choose another group of step size parameters. We set

where we can see that the step size parameters 's in (23) are of the ones in (21), and parameters 's in (24) are of the ones in (22). The second group of step size parameters is much smaller than the first group. The resulted curve of under the second group of step size parameters is plotted in Figure 6.

We observe in Figure 6 that RLS converges at a smaller speed than in the situation of Figure 5. It takes about 300 seconds for the scheduler to regulate the parameters and reach a stable approximate optimal average cost . But the variation of the value of in Figure 6 is much more moderate than that in Figure 5. These results indicate that the smaller the step size parameters, the slower the convergence speed, but the stabler the system performance. The selection of step size parameters 's and 's depends on the actual network conditions. The scheduler should not only provide a sufficiently stable performance but also be fast reactive to follow the variability of outside environment.

In the second experiment, we examine the performance of RLS in the aspects of bandwidth utilization, QoS guarantee, and fairness. We compare RLS with two existing scheduling algorithms CSDP-WRR [17] and CIF-Q [9]. CSDP-WRR is a combination of CSDP mechanism and Weighted Round Robin (WRR) scheduling algorithm, which has been demonstrated to be simple, robust, and effective [17]. The major feature of CIF-Q lies in the fairness it provides. CIF-Q integrates the well-known CIF-property, which takes into account both long-term and short-term fairness [9]. The simulation lasts for 1200 seconds. During the simulation time, channel errors occur only in the first 400 seconds. The remaining error-free time is to demonstrate the long-term fairness property of RLS. In the simulation, we keep track the delay, throughput, and service amount of the traffic flows. The results are reported in Figures 7, 8, and 9.

We know from Figures 7(a) and 7(b) that both the average and maximum delays of audio and video sessions in RLS are clearly smaller than in either of the other two algorithms. In other words, RLS is able to provide better QoS guarantee for realtime traffic flows. It should be noticed that the satisfying QoS guarantee for audio and video sessions in RLS is not obtained by sacrificing the throughput of the other sessions. This is validated by Figure 8.

Figure 8 consists of three subfigures. Figures 8(a) and 8(b), respectively, report the throughput of data traffic flows in the first 400 seconds and the entire 1200 seconds. Figure 8(c) reports the total throughput of all the three data traffic flows. In Figure 8(a), compared to the other two algorithms, RLS significantly improves the throughput of data-1 and data-2, except that the throughput of data-3 in CIF-Q is a little more than that in RLS. But we know from Figure 8(c) that the total throughput of the three data traffic flows in RLS is much more than that in the other two algorithms. More specifically, in the first 400 seconds, the total throughput of data traffic is 1.62 Mbps, which is higher than that in CSDP-WRR (1.19 Mbps) and higher than that in CIF-Q (1.22 Mbps). In the entire 1200 seconds of simulation, the overall throughput of data traffic in RLS is 1.77 Mbps, which is higher than that in CSDP-WRR (1.57 Mbps) and higher than that in CIF-Q (1.63 Mbps). Results of Figure 8 indicate that RLS has a considerable improvement in bandwidth utilization.

To demonstrate the short-term and long-term fairness properties of RLS, we record the service received by the data sessions over the whole simulation time in Figure 9. It is observed that the curves diverge moderately in the error-prone period and then converge gradually in the error-free period. We give interpretation as follows. To promise short-term fairness, RLS does not force the leading sessions to give up all their leads but just makes them degrade gracefully. So data-1 session receives relatively more service in the first 400 seconds. However, when the system becomes error-free, the lagging sessions will gradually get back their lags, and finally all data sessions obtain same throughput. This observation validates that RLS offers both short-term and long-term fairness guarantee in the sense that it provides short-term fairness for error-free sessions and long-term fairness for error-prone sessions. This exactly coincides with the spirit of CIF properties introduced in [9].

Finally, we plot in Figure 10 the curve of approximate optimal average cost in the second experiment. Note that we use the group of small step size parameters defined by (23) and (24). As we set in the simulation, the network conditions are different in the first 400 seconds and the last 800 seconds (the channel models of data-2 and data-3 change at the th second). It is observed in Figure 10 that RLS, however, could still guarantee the convergence through online learning under the actual network conditions. Benefiting from its in-built learning ability, RLS could work adaptively according to the outside environment.

Suppose that the total bandwidth of the system is . Let denote the proportion of bandwidth allocated by the scheduler to session under the Fluid limit, that is, . The scheduling problem could be formulated as a linear programming:

By introducing a positive Lagrangian multiplier , (A.1) can be rewritten as the following unconstrained optimization problem:

For session with nonzero service proportion , we let and get

By substituting (A.3) into the constraint , we have

The proportion of service for session is finally given by