Queues-Scheduling-Network

This is an Omnet++ project written in C++ describing different scheduling algorithms for a network of queues(FIFOs). This project was realised with omnetpp-5.5.1 Windows version. (Linux distributions may prove problematic) Code inspiration was provided by existing samples in the omnetpp folder and user manual.

Describing the system

Each algorithm supposes we have 3 Users, each of which having a queue(FIFO) with package self-generation every 1ms. Every User wants to empty its queue or reduce the number of error packages, corresponding to the task at hand. All packages go to the Sink, which is where they are 'processed'. A User cannot send packages to the Sink without having a 'greenlight' from the Scheduler. There are 3 types of users, based on their priority:

1. premium user can send 3 packages to the Sink
2. standard user can send 2 packages to the Sink and the
3. economy user can send only 1 package to the Sink (the above rule is not applicable in the Priority Scheduler Method).

The Scheduler sends packages to the Users and allows them to get rid of their packages. The order/priority of Users is decided by the Scheduling Method we chose. The Scheduler sends the packages at a constant period of time, and it recalculates its priority (and number of packgages a user can send) according to the algorithm, being either real-time aware or periodically aware of the users'state. The generation period and packet transfer period is described in omnetpp.ini. However, due to omnet++ limitations, the scheduling algorithm is chosen in the LTE_sched.net file in the scheduleMethod variable.

Scheduling Methods

Fuzzy Logic Scheduler

To choose this algorithm, modify accordingly:

scheduleMethod = 4;

This method uses the same rules as the Error Adaptive Scheduler, but uses different intervals, and each interval has a linear decrease for the last 10 units of it. This algorithm uses Fuzzy Logic. For calculating the package allocation for each user, a weight system is used. That means each time the algorithm needs to decide how many packages a user can send, a combination of 1 or 2 complementary weights are multiplied with the old package allocation number and the interval delta, depending in which intervals the error is. The interval delta is a number of aditional packages, varying from each interval. This is the graph of the fuzzy logic:

This is an example of the calculations for the number of packages to send by a user. The first example, point A, shows a case where it's both correct and laggy. This means that for calculating the required number, a weighted sum of the products between interval deltas and previously sent packages. For point B, the case is only very laggy, so the weights and deltas for the correct and laggy intervals are 0.

The system options can be uncommented in the .ini file.

Error Adaptive Scheduler

To choose this algorithm, modify accordingly:

scheduleMethod = 3;

This method is applied to a system with the following rules:

• Users have a 20% chance of sending an ERROR package
• Scheduling period is 20ms
• During one Scheduling period, a max of 18 packages can be sent by all Users combined
• Each User sends at least 1 package per Scheduling period. This means that a single User cand send a max of 16 packages, so that the others can send
• Each User start sending at the same time, for the sake of easy observation
• All error rates (or LAGs) reset at each Scheduling period

These said, this method has 3 intervals of acction, depending on the error rate during an interval. The intervals are: [0,20) - correct; [20,80) - laggy; [80,100] - very laggy. The action graph is:

The user with the highest LAG (error rate), will be modified by a delta factor, depending on the interval it falls into. The final allocation is limited by the system's rule (e.g. if a User is very laggy and tries to get more resources than possible - 16 - then hard limit it). The same is done for the rest of the Users, except the last one - which gets allocated what's left. Over an interval, the number of additional packages is varying, so there are no pre-programmed numbers. The only exception is the first case, where if all users are correct - then we apply the classic Weighted Round Robin algorithm.

Error-Weighted Round Robin Scheduler

To choose this algorithm, modify accordingly:

scheduleMethod = 2;

This algorithm has an additional factor added to the system: Packages sent by the users to the Sink have a probability % of sending error packages to the Sink. This method tries to imitate the behaviour of a Weight-Varying Round Robin Scheduler, and reduce the factor of (error packages sent / total packages send), by shifting the priority to the 'worst performing' user, at a predetermined scheduling period. This algorithm has at its base the Weighted Round Robin algorithm, to the extent that an updated priority status is given to every user at each scheduling period. When none of the users presents an error factor that passes a predetermined arbitrary threshold, the network keeps its current state of priority and works normally until the error-weighted meethod is needed again.

Priority Scheduler

To choose this algorithm modify accordingly:

scheduleMethod = 1;

This algorithm gives sending priority to the User without an empty Queue, until it empties it. To better understand this, we need different generation periods for the sources of the Users, which should be less frequent than the scheduling period at which the Scheduler takes action.

Weighted Round Robin Scheduler

To choose this algorithm, modify accordingly:

scheduleMethod = 0;

This works as a normal RR scheduler, with the users having a permanent priority. This algorithm is adaptable, as it takes into consideration if a prioritized user has an empty queue (thus it does not need to use the scheduler's time while other Users can be attended to), and shifts its priority to the next prioritized user until there is someone with a higher priority back online.

Alpha Version Round Robin Scheduler

To choose this algorithm, modify accordingly:

scheduleMethod = 10;

This works as the Weighted Round Robin Scheduler described above, but it is not adaptable in the event of unnecessary priority occupation.

Running the project

Make sure you have the correct version of omnet++ mentioned above. Choose a scheduling method through the scheduleMethod variable, comment and uncomment the necessary lines in omnetpp.ini, and while you have that file window opened and selected, press the Run simulations button.

Understanding the simulations

The above gif represents a rundown of the Error-Weighted Round Robin Scheduler. Here is some explanation:

TO BE MENTIONED: The above method is not a Fuzzy Logic Controller. It has fuzzy-names because the code used for this method was meant to be a FLC, but later repurposed into the Error-Weighted Round Robin Scheduler. This will be patched in a future version.

The other scheduling algorithms are more straight forward and make use of the emptyQueue, which transmits the queue status.

P.S.: This is a slightly messy project, as there are redundant variables that are passed around and are irrelevant to some algorithm methods, but removing them would not allow the code to be multi-purpose, as omnet++ does not provide a very flexible environment. Also, because of developing new Scheduling methods, some nomenclature is confusing between methods. This will be corrected on the way.

©Debucean Caius-Ioan @ github.com/caiusdebucean