Scheduler

Resources / Queues
Block Name: Scheduler

Code File Location: VisualSim/actor/lib/Scheduler

Block Overview

  o  Used to define a queue that has a arbitration scheme to pop the next data structure out.

  o  Create multiple concurrent queues of type FIFO or LIFO.

  o  Buffer to store requests or transactions from different sources or for different destinations in separate queues.

  o  Create rudimentary cache with equal sized data access (Read or Write).

  o  Priority queue reordered based on the priority of the incoming task.

  o  Used to define a resource as a set of Queues/FIFO.

  o  Queue Management Algorithms are used to reject the packet in case queues overflow, are as follows

• Tail Drop / Incoming Token Rejected
• Random Drop on Full
• Drop Front on Full
• Random Early Detection
•  Lowest Priority Token Rejected     

  o   Scheduling Algorithms  are used to send the packet out of the queue such as -:

• FCFS
• FIFO
•  LIFO
• Round Robin
• Weighted Round Robin
• Weighted Fair Queueing
• Strict Priority
• Deficit Round Robin
• Round Robin Priority
  

 

Description

The following is a block diagram that illustrates the operation of the Smart Resource block.

The Queues is a Queueing or static resource. This block defines multiple independent queues. Each queue orders the incoming data structures from highest to the lowest priority. The parameter- Queue_Number_Field selects the queue to place and the parameter-Priority_Field contains the priority for each transaction to reorder/reject in the Queue. The Queue_Number_Field and the Priority_Field can be a Expression, containing a fixed value, parameter, variable, incoming data structure field or RegEx. This block queues the incoming data structure or token in a FIFO or LIFO order based on the Queue_Type parameter. To remove from the queue, the user can send an integer value for the queue number to remove the head of the Queue or a two index array where index-0 is the queue number and index-1 is the position in the array.  All queue can have the same depth (integer value for the Max_Queue_Length) or each queue can have a different value (integer array for the Max_Queue_Length).

The first token or Data Structure arriving at the Queue can either be sent out immediately or queued until a pop_input is received, based on the Initial_Queue_State parameter setting. If the queue is full, the incoming Data Structure or the lowest priority token is placed on the reject_output port, depending on the Queue_Reject_Mechanism parameter setting.  If there are multiple tokens with the same priority, the last arriving transaction of the same priority is rejected.

The Script or Smart_Controller block is used in conjunction with this block and is normally connected to the pop_input port.  The Smart_Controller is used to define the arbitartion and other management policies.  This block can be used to trigger (pop) the next transaction from a Queue.

  QUEUE MANAGEMENT ALGORITHMS:

•          Tail Drop / Incoming Token Rejected
  

 It is a Passive Queue Management algorithm.  Each queue has a maximum queue length and when the queue length exceeds beyond the maximum, the new incoming packets will be dropped. The incoming packets drops continuously whenever the buffer  capacity exceeds and this dropping continues until the queue gets enough space for accommodating new incoming packets.

In the VisualSim, a parameter called Max_Queue_Length is used to define the maximum packets that can be accommodated in a given queue. The user can also define the queue number for each data.When a new packet arrives, the length of the  corresponding queue is checked and if it is equal to the Max_Queue_Length, that packet will be dropped.

•          Random Drop On Full

When the new packet arrives, the corresponding queue length is checked. If it is equal to the Max_Queue_Length parameter, then random data from the queue is selected and dropped regardless of the  priority or any other criteria, and the new incoming  packet is accommodated in the queue.

•          Drop Front On Full

When the new packet comes in, the corresponding queue length is checked. If it is equal to the Max_Queue_Length parameter, then a packet at the head of the queue is dropped and the new incoming  packet is accommodated in that queue.

 

•          Random Early Detection

RED monitors the average queue size and drops packets based on statistical probabilities. If the buffer is almost empty, then all incoming packets are accepted. As the queue grows, the probability for dropping an incoming packet grows too. When the buffer is full, the probability has reached 1 and all incoming packets are dropped.
The RED algorithm calculates the average queue size. The probability of drop increases as the average queue size increases. The average queue size is then compared with two thresholds parameter such  as a minimum threshold and a maximum threshold. 

  SCHEDULING ALGORITHMS

•          First Come First Serve

The packet which arrives first in the queue is first sent out. It is a non-pre-emptive scheduling algorithm. That is, the process is executed in the order they received, irrespective of the priority.

•          Strictly Priority

In strictly Priority algorithm, the packets that are queued in a high priority queue are served before the packets in other queues.  Queues with lower priority are served only when there are no packets in all  the higher priority queues. The advantages of Priority queuing is the relatively low computational load on the system and setting priorities so that real-time traffic gets priority over applications that do not operate in real-time.

A disadvantage of priority queuing is that it might lead to starvation of some low-priority flows, if the higher priority traffic becomes excessive.

•          Round Robin

This algorithm lets every active data flow that has data packets in the queue to take turns to transfer packets on a shared channel in a repeated order. The scheduling is work conserving, that is if one flow  is out of packets, the next data flow will take its place.  It handles all the flows in a circular First-In-First-Out( FIFO) order and avoids priority so that all the flows are processed.

•          Weighted Fair Queueing

In WFQ, a scheduler handling N flows is configured with one weight(a parameter Weight_Array in VisualSim) w i {\displaystyle w_{i}} for each flow. Then, the flow of number i {\displaystyle i} will achieve an average data rate. w i ( w 1 + w 2 + . . . + w N ) R {\displaystyle {\frac {w_{i}}{(w_{1}+w_{2}+...+w_{N})}}R}A WFQ scheduler where all weights are equal is a FQ scheduler. Like all fair-queuing schedulers, each flow is protected from the others, and it can be proved that if a data flow is leaky bucket constrained, an end-to-end  delay bound can be guaranteed. For each packet, a virtual theoretical departure date will be computed, defined as the departure date if the scheduler was a perfect GPS scheduler. Then, each time the output link is idle, the packet with the smallest date is selected for emission.

•          Weighted Round Robin

The weighted round-robin scheduling is designed to better handle queues with different processing capacities. Each queue (a parameter Queue_Weight in VisualSim) can be assigned a weight, an integer  value that indicates the processing capacity. Queues with higher weights receive new connections first than those with less weight, and queues with equal weights get equal connections. For example, the  real queues, A, B and C, have the weights, 4, 3, 2 respectively, a scheduling sequence will be AABABCABC in a scheduling period.

•          Deficit Round Robin

It uses a deficit counter. In VisualSim maximum packet size parameter (Quantum) number is subtracted from the packet length, and packets that exceed that number are held back until the next visit of the scheduler. 

•       ROUND ROBIN+PRIORITY   
  

In Round Robin+Priority Scheduling algorithm, each queue is a given a priority. In VisualSim a parameter Queue_Priority is defined. The packets are first served from the queue with the highest priority to the lowest priority. There it forms a sequence according to the priority. Then the packets are served in that repeated order.

  Statistics

The statistics for the Queues are generated using the getBlockStatus RegEx function with type "length", Resource_Statistics block or Queue_Name + "_" + Length.  The array lookup is significantly faster than the other two methods. The function and array lookup can be called in the Script, Smart_Controller and ExpressionList blocks.  

Result_B = Queue_Length(2) where the array index starts at 1 for Queue number 1.  Array Index of 0 is not used.

Statistics_A = getBlockStatus(Queue_Name,"Any Value","stats",Queue_Number,1)  -> To get the statistics.  

Reset_Stats_A = getBlockStatus(Smart_Resource_Name,"Any Value","stats",-(Queue_Number), 1)   -> To reset the statistics.  

If reset or statistics is required for all Queue, then make the Queue_Number = Number of Queues + 1.

There is a pre-created "Generator" block and is used in the Resource_Statistics Example in the BDE.

Copy_A = getBlockStatus(Smart_Resource_Name,"Any Value","copy",Queue_Number, position)  -> To get copy of the Data Structure at a position in the Queue.

Length_A = getBlockStatus(Smart_Resource_Name,"Any Value","length",Queue_Number,1)  -> To get the length of the selected Queue.

Remove_A = getBlockStatus(Smart_Resource_Name,"Any Value","take",Queue_Number, position)  -> To remove a transaction in any position of the selected Queue.  Make sure 1 is not used, else the head will be removed.

isAvailable =  getBlockStatus(Smart_Resource_Name,"Any Value","array",Any Integer, Any Integer)- Returns an array of which Queue is free (true) or busy (false)

To learn about the use of the getBlockstatus, check the library example for getBlockStatus.  There are a number of additional getBlockStatus settings to the list above. Also, view the getBlockStatus setting in the RegEx documentation and in the Basic Technology document.

Refer Single Scheduler Queue , Scheduler Modeland Multiple Queues with Scheduler for Pop and Arbitration demo model.

Statistics Output:

Where n is the number of samples and X is occupancy or delay.

---