Scheduler Algorithm for Multi-Class Switch with Priority Threshold ()
1. Introduction
In the current communication network, the desire of having multiple applications on a single traffic stream has become essentials. The multi-class traffic [1-9] is used to classify these applications based on its QoS requirements. The use of priority provides the means to give different classes of service a different type of traffic [4]. This needs an efficient scheduling algorithm to handle the flows of multi-class traffic packets.
Scheduling algorithm plays an important role in obtaining a high performance in multi-class switch. Priority scheduling technique is commonly used in multi-class switch. This technique is used to classify the priority level for each class. Unfortunately, most of the existing scheduling algorithm [1,2,4-6] only strives to maximize the QoS level in delay sensitive class for each arrival cell without considering the performance in lost sensitive class, which may result in poor QoS for this class, especially when the system is in heavy load. Scheduling algorithm for a single priority class may not perform well when it is applied to a multi-class scheduling [6]. The introduction of Weighted Fair Queue (WFQ) has improved the performance of the multi-class switch.
In Weighted Fair Queue (WFQ), traffic classes are served based on the fixed weight assigned to the related queue [7,8]. The weight is determined according to the QoS parameters, such as service rate or delay. This technique is not suitable under high-traffic load because of the fixed weight that is assigned to the queue and introduces starvation problems to loss sensitive class. The introduction of adaptive technique in threshold levels selection [9] has improved the performance. The priority given in these switch will determine the cells from which class should be served first with consideration of QoS requirements.
Despite improving the performance of loss sensitive class, designing a high speed packet multi-class switching with the threshold will introduce problems such as the drop of QoS performance for delay sensitive class whenever the threshold is active. This research is expected to improve the mean delay in delay sensitive class when the threshold for loss sensitive class is active.
In order to achieve the stated objective, the new scheduling algorithm is introduced to improve the delay sensitive class performance. Non-blocking switch such as the crossbar switch is used as a switching fabric. The scheduler wills evaluate all possible connections between all input port and output port for every class in the switch in order to make the best decision.
In this paper, we proposed an efficient scheduling technique to control the flow of the cells for both loss sensitive class and delay sensitive class in the multi-class switch with the threshold. This scheduler is able to detect and match the idle output port for delay sensitive class even in the present of the active threshold in loss sensitive class within the same input port.
2. Proposed Model
The proposed multi-class switch architecture with N ports serving 2 classes of traffics is shown in Figure 1. Priority switch is used to forward delay sensitive packet (Class 1) faster than loss sensitive packet (Class 0).
The delay requirement for class j cells is defined by Dj where j = 0, 1 and D0 > D1. In other words, the delay requirement for Class 1 is more stringent than Class 0 for system shown in Figure 1. Thus, cells that queue in Class 0 have the lowest priority and cells that queue in Class 1 have the highest priority. These delay requirements are set based on the QoS requirement for different type of applications.
Time slot is used to represent the time of one cell arrival at the input port or cell departure at the output port. The period of time slot Ts, where s = 0, 1, 2, ··· is set to be equal to the time to process a single cell when the server is idle.
The class j cells arrive at the input port in every time slot according to Bernoulli distributions with mean lj. The cell is classified based on its delay requirement. In this architecture, the class of the cell is stored in the header. Arrival cells for Class j (lj) is queued in the FirstIn-First-Out (FIFO) buffer while waiting to be served.
The threshold setting is introduced in order to give some privileges to cells in lower priority class. In the case when there are cells from different classes are waiting at HoL; the scheduler will select the cell with high priority to be served. However, when the threshold is active, the scheduler will select the cell in the low-priority class. The losing cells in the contention must wait in the queue. In case when the threshold is active, and the
Figure 1. Multi-class switch architecture.
cells from both classes are destined to the different output port that is idle, both cells will be selected if there is no contention.
3. Thresholds in Multi-Class Input Buffer
In multi-class switch, priority is given to delay sensitive packets compare to loss sensitive packets. This means, the cells from real time packets or delay sensitive packets in Class 1 are served first while cells from non-real time packets in Class 0 are queued in the buffer while waiting to be served. This will create a large amount of delay and starvation problem in non-real time class. To overcome this problem, scheduling has to give some priority to cells in Class 0.
To achieve this goal, each individual class will have their own buffer to accommodate different traffic classes. This can eliminate the head-of-line (HoL) for different classes blocking effects.
In normal cases, the scheduling algorithm for multiclass traffic only considers one parameter; priority cell setting or probability of serving low priority classes. In this research, two parameters have been selected to set the threshold level; the number of Class 0 cells in the queue (Nb) and the probability on serving the Class 0 cells (PSC0) over the Class 1 cells. The threshold values are set based on the minimum requirement for high-priority class, arrival rate and buffer size of the switch. Therefore, the threshold settings can be adjusted to optimizing the total cell delay for both classes.
The number of Class 0 cells in the queue (Nb) parameter is chosen because of the limited buffer size available in FPGA. The need to adjust the Nb parameter is necessary to reduce the packet loss due to buffer full. This parameter is adjusted based on size of buffer used to stored cell in Class 0.
Figure 2 illustrates the threshold active signal for setting at Class 0 buffer to two (Nb = 2). The threshold signal is active when the buffer occupancy.
The probability on serving the Class 0 cells (PSC0) parameter is chosen in order to control the variation of delay between real time cell and non-real-time cell based on the real time QoS requirements. This is necessary in order to achieve better performance for Class 0 cells.
All arrivals for Class 0 cells and Class 1 cells are stored
Figure 2. Threshold active signal with setting of Nb = 2.
in the First-In-First-Out (FIFO) buffer while waiting for their turns to be served. Selection from FIFO HoL between Class 0 and class1 is determined by the threshold setting in the scheduler. The scheduler will give priority for Class 0 when there is no cell in class1 or when both thresholds are triggered.
4. Protocol
The scheduler process consists of three phase, i.e. request, grant, departure. Figure 3 shows the protocol of each Head-of-Line (HoL) cell in the input buffer until departure.
All the HoL cells in input buffer will request grant to depart from the input port buffer (i) to output port (j). The granting process will depend on the situation of status either idle output port; availability of priority cells or threshold for low priority class is active. The award of grant to depart will be given by the scheduler. Once the cells received the grant signal, it can be departed from that input port and then update port for new HoL cell.
5. Scheduling Algorithm
The scheduling algorithm is developed to control the cells flows through the switch. Figure 4 shows the bipartite graph for the proposed scheduling algorithm. The high-priority class and low priority class will be control by a centralize scheduler.
A = Matrix of HoL for High priority class (H-HOL);
B = Matrix of HoL for Low priority class (L-HOL);
Figure 3. Protocol for scheduler process.
Figure 4. Bipartite graph for the scheduling algorithm.
T = Matrix of threshold of input port of Low priority class;
OT = Vector of output port that have L-HOL cell with threshold;
OA = Vector of output port that have H-HOL cell;
OB = Vector of output port that have L-HOL cell;
γ = Vector of output port of H-HOL that not overlap with L-HOL with threshold;
φ = Vector of output port of L-HOL with and without threshold which not overlap with H-HOL;
H = Matrix of selected H-HOL cell;
L = Matrix of selected L-HOL cell;
1 = [1 1 1 1];
t = [t1 t2 t3 t4].
where ti = {1, 0}
. (1)
Vector t is given by the diagonal elements of the matrix T.
. (2)
Vectors oA and oB represent the existing HOL cell for the destined output ports associated with High and Low priority class traffic, respectively. On the other hands, vector oT denotes the location of the output ports that have the active threshold signal. The three vectors are generated using the following expressions:
. (3)
. (4)
. (5)
Note that all vectors’ elements can only assume 1 or 0 value.
The above vectors (oA, oB, and oT) are used to construct diagonal matrices OA, OB, and OT, where the vectors become their respective diagonal elements. These diagonal matrices will be used in our selection section algorithm.
5.1. High Class Traffic Input Selection
Let us define a temporary vector γ to represent the legitimate output arrangement associated with the highclass traffic considering the low-class traffic input with active threshold.
(6)
Note that, in the event contention, the high class traffic will be blocked. Then we can generate the selected input for the High class traffic, which is represented by a matrix H given by:
(7)
However, if more than 1 inputs are possible for the same output, a round robin technique will be used to select the one of these input ports.
5.2. Low Class Traffic Input Selection
Let us define a temporary vector φ given by the following expression:
(8)
Recall that f(a) is given by Equation (8). Hence, f(OB – OA) will eliminate an output port option for the low class traffic if that port has been allocated for the high class traffic. After that, the final φ will also contain legitimate output port information about the low class traffic with active threshold.
Finally, we can define the input selection for the low class traffic by using the following equations:
(9)
The L matrix contains input selection weight for the low-class traffic. Similar to the previous case, whenever exists more than 1 input port with the same maximum weight, a round-robin technique will be used to select the one of these input ports.
The maximum weight in the row index of each column will determine the input ports for each output port. The output port is only able to select one input port either from H or L, the γ matrix has eliminated the overlap input selection for high-priority class traffic and j matrix has eliminated the overlap input selection for low priority class traffic.
6. Hardware Design
The hardware design of the scheduler is developed to evaluate the performance of the multi-class switch. The design of 16 × 16 multi-class switch scheduler can be divided into two parts: HoL scheduler and full-scheduler. The HoL scheduler is used to cater the Head-of-Line (HoL) cells from different priority class. The full-schedule is used to perform the selection of cells for departure.
Figure 5 shows the architecture of multi-class scheduler. All the cells in input port HoL will be granted for departure based on scheduler protocol. The mux selector (Sel_L, Sel_H and Sel_out) will be determining by using the scheduling algorithm.
HoL Scheduler is used to select HoL cell from delay sensitive class (FIFOH) and/or loss sensitive class (FIFOL). Figure 6 shows the HoL scheduler design for twoclass switch. Mux1 will transfer cell from FIFOH if dual threshold setting (Nb0 and PTSC0) does not meet its limit and there are cells in FIFOH. Cell from FIFOL will be transfered by Mux1 if there is no cell in FIFOH or when both thresholds setting to reach its limit. Mux2 will
Figure 5. Multi-class scheduler architecture.
transfer cell from FIFOL when the destination address for high class (AddrH) is different from destination address for low class (AddrL). Mux2 will eliminate the HoL blocking effect for loss sensitive class and will increase the switch performance.
Figure 7 illustrates an example of the scheduler process. Output port 1 will be accepting cell either from input