LOAD BALANCING

Posted: August 26th, 2021

LOAD BALANCING

Student’s Name

Course
Professor’s Name
Institutional Affiliation
City (State)
Date

Table of Contents
Load Balancing 3
Introduction 3
Background Information 3
Problem Statement 4
Related Research Works 5
Changeable Time Quantum (CTQ) 5
Burst Round-Robin Algorithm (BRR) 5
Enhanced Round-Robin Algorithm 5
Proposed Algorithm 6
Weighted Round-Robin Algorithm (WRR) Definitions 6
Table 1: Terminologies used in the work 6
Figure 1: Flow Chart for the proposed Scheduler 8
Illustrative Case 8
Table 2: Number of processes having different CPU burst time 8
Under Round-Robin algorithm 8
Figure 2: Gant Chart for RR algorithm 9
Table 3: Scheduling Criteria for RR Algorithm 9
TAT {i} 9
Under Weighted Round-Robin algorithm 9
Table 4: Process and respective time slices for WRR 9
Figure 3: Gant Chart for WRR algorithm 10
Table 5: Processes, respective weights and burst time for WRR second round 10
Table 6: Scheduling Criteria for WRR 10
Experiment Results 10
Results for Scenario 1 11
Figure 4: Average waiting time in scenario 1 11
Figure 5: Turnaround time average for scenario 1 12
Figure 6: Number of Context Switches for Scenario 1 12
Results for Scenario 2 13
Figure 7: Comparison of Turnaround Average time for Scenario 2 13
Figure 9: Comparison of the average waiting time for scenario 2 14
Implementing the Weighted Round-Robin 14
Round-Robin Algorithm 14
Weighted Round-Robin Algorithm 15
Architecture of WRR 17
Figure 10: Operation Architecture of WRR 17
Simulation 18
Conclusion 19

Load Balancing
Introduction
The increasing strain on organization operations or website applications implies that it is not possible for a single server to adequately support such workload. Hence, many organizations are trying to spread the excessive workload to a multiple server system. This activity is referred to as ‘load balancing (Brázio 2006). It tries to minimize the risk of overworking a single server that might eventually reduce its efficiency, thus slowing down, dropping the requests,or crashing. Through load balancing, network traffic is uniformly distributed, which eventually reduces the possible failure of the system because of overloading a given source.
Further, in the case of a user, the load balancer is an invisible facilitator between the group of servers and the client responsible for ensuring that there is no loss in the connection requests (Kumar, Abdelhadi & Clancy 2018). Most applications, online services, databases, and websites are likely to fail without load balancing (Brázio 2006). For example, a single website with high traffic can receive thousands of requests from users at a particular time. Therefore, a multiple server system is required to enhance accuracy in populating and directing the requests to particular webpages with the requested information, video, audio streaming, and photos, among other activities.
Background Information
System behavior is affected by factors such as the aggregate process time and waiting time spent in ready queue, the turnaround period, and the time when the process was started up to the time when it was completed, among other factors (Brázio 2006). It is essential to optimize system behavior. Properties of scheduling algorithms vary from one central processing (CPU) to the other. Equally, a set of processes is affected by the choice of an algorithm (Kumar, Abdelhadi & Clancy 2018). Hence, the characteristics used in the comparison between the CPU scheduling algorithms determine the type of scheduling algorithm employed to execute the process. Notably, the purpose of the CPU scheduler is to allocate resources; in this case, the CPU time to all the processes (Brázio 2006). Here, therefore, the problem is to determine when a specific type of a process should be moved, its target destination, and the running duration.
Problem Statement
The critical aspect ofthe round-robin policy is selecting a time slice. The performance of a system is primarily affected by the size of the time slice it is assigned (Kumar, Abdelhadi & Clancy 2018). For example, a very long time slice will ultimately cause a convoy effect. Convoy effect is a situation where processes are halted as they wait for a significant process to be completed and out of the CPU (Brázio 2006). Conversely, a very short time slice contributes to increasing context switches, implying that the system will become inefficient during switching. In such a case, the system is downgraded. Similarly, when short processes are allowed to utilize much of the CPU resources, there is decreasing context switch overheads (Brázio 2006). Therefore, a balanced selection of the time slice is critical.
Related Research Works
There are different research works on scheduling algorithms that are related to the research, which are discussed in the following parts of this section.
Burst Round-Robin Algorithm (BRR)
This is a type of weighting algorithm that is based on the process burst time. In this case, the time slice increases with the increase in the weight of a process (Kumar, Abdelhadi & Clancy 2018). Usually, short processes leave the CPU earlier since they are given more time.
Enhanced Round-Robin Algorithm
It is a type of modified round-robin algorithm where in every round, a new time slice is assigned by the algorithm equals the mean burst time of all the processes running (Kumar, Abdelhadi & Clancy 2018).
Proposed Algorithm
Weighted Round-Robin Algorithm (WRR) Definitions
WRR is a proportional CPU scheduler, which assigns time slice for each process proportional to the burst time. It is well designed to handle servers whose processing capacities vary. Each server is assigned a weight or time slice, indicating its processing capacity. The speed of connection increases with the amount of time slice assigned for each server. The following are terminologies used in this work.
Table 1: Terminologies used in the work
n Number of processes
PID Identity of a process
BT {i} The original burst time of a process i
RR_TQ Time quantum that is assigned by the RR policy
BT {i}{r} The burst time of a process i in a round r
W {i}{r} Weight of a process i in a round r
TSH A predefined threshold
NTQ {i}{r} The new time quantum for a process i in a round r
WT {i} The waiting time for a process i
TAT {i} The turnaround time for a process i
AVGTAT The average turnaround time
CS {i} Context switches
AVGWT Average waiting time
The following part discusses the design issues for the WRR functions;
It is a first-in and first-out (FIFO) type of queue
The process weight equals the burst time of a process divided by the sum of all burst time in a queue. That is;
W{i}{r}=BT{i}{r}/(total sum of BT{i} ),BT {i}{1}=BT {i}…eq.1
The time slice of a process
NTQ {i}{r}=(1-W {i}{r} )*RR_TQ…eq.2
Burst time
BT {i}{r}=BT {r}{r-1}-NTQ {i}{r-1}…eq.3
Burst time for a selected process under execution is compared with the time slice that is assigned by RR policy according to the predefined threshold. That is, the threshold value depends on the choice of implementation.
Given that conditions outlined in part (v) are real, the short process completes the implementation until it is terminated.
However, when conditions in part (v) are false, the process under implementation will be interrupted once the time slice expires according to part (iii) and repositions at the tail of the ready queue.
The following is a flow chart for the proposed scheduler for the work.

Figure 1: Flow Chart for the proposed Scheduler
Illustrative Case
The proposed consideration is illustrated in the following case. Four processes arrive within the same time interval, and their burst time is given in milliseconds.
Table 2: Number of processes having different CPU burst time
BT {i} PID
22 P1
21 P2
7 P3
15 P4
Under Round-Robin algorithm
The results of the illustration case under the round-robin algorithm are as shown in the Gant Chart, figure 3 below RR (RR_TQ = 10 milliseconds).

Figure 2: Gant Chart for RR algorithm
Subsequently, the scheduling criteria for the RR algorithm is given under table 3 below.
Table 3: Scheduling Criteria for RR Algorithm
PID BT {i} WT {i} TAT {i} CS {i}
P1 22 41 60 2
P2 21 39 57 2
P3 7 21 27 0
P4 10 48 59 2
AVGWT = 37.25 MS AVGTAT = 50.75 MS NO. CS = 6
Under Weighted Round-Robin algorithm
In the case of the WRR algorithm, the threshold for this work is TSH=0.3*RR_TQ. The weights of the process and several time slices are shown in Table 4.
Table 4: Process and respective time slices for WRR
PID BT {i} BT {i}{1} W {i}{1} NTQ {i}{1}
P1 22 22 0.36 6.5
P2 21 21 0.3333 6.667
P3 7 7 0.2 7
P4 10 10 0.4166 11
Sum 60
Since process P3 fulfills the conditions provided under part (v), it will continue to completion until it is terminated. The schedule results are shown in the Gant chart below.
Figure 3: Gant Chart for WRR algorithm
The second schedule burst time and respective time slices that are assigned for the processes are shown under Table 5.
Table 5: Processes, respective weights and burst time for WRR second round
PID BT {i} BT {i}{2} W {i}{2} NTQ {i}{2}
P1 22 15.5 0.246 7.75
P2 21 13.422 0.322 13.666
P3 7 Terminated
P4 10 Terminated
Sum 60
From the results above, once process P2 achieves conditions defined under part (v), it continues to completion until terminated. The scheduling criteria for WRR is presented in the table below;
Table 6: Scheduling Criteria for WRR
PID BT {i} WT {i} TAT {i} CS {i}
P1 22 41 60 2
P2 21 36.667 53.166 1
P3 7 33.18 20.223 0
P4 15 13.266 32.337 0
AVGWT = 31.02825 MS AVGTAT = 41.4315 MS No. of CS = 3
Experiment Results
In an attempt to demonstrate WRR, quantitative experimental data was used to compare the performance of WRR against the RR algorithms over different sets of combinations using two scenarios. The first scenario involved having the process scheduled to arrive at the same interval (named US_WRR), while the second scenario involved having the processes arrive at a different time interval (name S_WRR). The process was repeated, and results recorded. Besides, each scenario has two cases. The first case is where the processes are left to run according to the order they arrive. However, the process order is sorted and arranged in ascending order. These processes were generated using the predictable generator, which assigns each process its arrival time, the burst time, and process identity. The arrival of the process was scheduled based on Poisson’s randomization. When comparing the results, it was revealed that there is a critical difference in minimizing the scheduling criteria, which had significantly improved in terms of waiting time, contextual switches and the turnaround time average. The summary for scenario 1 is shown in figures 3, 4 and 5 while scenario 2 in figures 6, 7, and 8, displaying changes in the average waiting time, the turnaround average, and the contextual switches respectively.
Results for Scenario 1

Figure 4: Average waiting time in scenario 1
Figure 4 is the average waiting time for scenario 1, showing a combination of processes undertaken in the two algorithms, RR and WRR.

Figure 5: Turnaround time average for scenario 1
Figure 5 is the turnaround average time for scenario 1, showing a combination of processes undertaken in the two algorithms, RR and WRR.

Figure 6: Number of Context Switches for Scenario 1
Figure 6 is the number of context switches for scenario 1, showing a combination of processes undertaken in the two algorithms, RR and WRR.
Implementing the Weighted Round-Robin
Round-Robin Algorithm
The benefit of the round-robin scheduling algorithm is that it does not experience starvation. It exists to ensure that every process on the queue in the job queue share a time slice existing on the processor. As defined earlier, time slicing refers to the time intervals allocated to the competing programs for use in the CPU (Stoica, 2004). In every interaction of the RR algorithm, this represents the period taken by each job. All the jobs are executed in a first-come-first-served (FCFS) system (Stoica, 2004). However, they are pre-empted once time scale elapses. Therefore, if the job is completed within the allocated time slice, it is returned to the process queue tail for reprocessing.
Priority scheduling is either non-preemptive or preemptive. However, it is worth noting that priority scheduling is affected by starvation. Besides, there are ways a processor may lose CPU control. These include when the task is completed, the higher priority task is ready or the task is under a waiting condition. Whenever a higher priority task becomes ready, it could cause disregarding of the lower priority tasks. Similarly, since higher priority jobs usually take longer to complete, they will be affected. In this case, the process is weighted, and aging implemented with the RR algorithm to avert the issue.
Weighted Round-Robin Algorithm
The weighted round-robin CPU scheduling algorithm relies on the RR advantages of eliminating the issues arising from starvation. Accordingly, the WRR structure is almost similar to the RR as it utilizes an FCFS job listing structure (Stoica, 2004). A complete cycle of the job queue occurs once all the jobs have shared the processor time. FCFS is implemented when all jobs are at the same weight. All processes are given a time slice to eliminate the issue of starvation. Hence, the WRR algorithm ensures that the CPU is never held for a longer time than the required period. At the same time, short jobs that are re-queued are not prolonged while waiting for the completion of high priority ones as all jobs in the queue are granted sufficient time (Yamanaka, 2004). In this case, the value of each time slice becomes essential, especially before changes in the job weight. In fact, in the WRR structure, the time slice is varied continuously for every specific job based on their respective weight allocated by the CPU. Notably, the increase in the job weight leads to a relative increase in time slice, such that it remains proportional to the change in job weight.
Subsequently, aging is implemented in the WRR algorithm. The purpose of aging is to boost the weight of a job in the queue. According to WRR structure, the job’s weight is increased three times the weight of three jobs under processing. The general sequence for a WRR algorithm is as shown below;
All the new jobs enter the job queue
Aging implementation: in case of an increase in weight is needed, an evaluation is done before aging.
The new processes (jobs) are allocated new value of time slice based on their respective weight.
Reordering of the job queue is done putting those jobs with higher weight at the front
All jobs have their assigned time on the processor
Returns to 1
Architecture of WRR
As discussed earlier, the WRR scheduling algorithm uses the packet-switched network with static weights that are assigned to the job queues. The algorithm works by cycling through these queues to transmit the packet amounts from the queues according to their respective weight, as shown in figure 10 below. In this way, each connection is guaranteed a fraction of the output link to the bandwidth. At the same time, it ensures that there is no starving of lower priority job queues. The feasibility of the structure to the high-speed interfaces both at the edge and at the core of the network is enhanced by the ability to process at O (1).
Figure 10: Operation Architecture of WRR
Figure 10 shows the operation architecture of the WRR scheduler. The WRR scheduling works by assigning weights Øi to each of the process queues in such a way that the total weight of all job queues equals to 1.
sum of Øi=1,i=1…n …eq. 1
Given that weight is assigned as a fraction and the aim is to obtain the number of integer packets that are served on each queue, a constant integer, M is multiplied by fraction weight. The result is then rounded off to the nearest integer value to integer weight Wi. The value specifies the packets that are supposed to be processed from the job queue. As such, the sum of these values represents the round-robin. Hence, for the ith queue, the integer weight is as follows;
wi=[Øi*M]…eq.2
The round-robin length W defines the total of N existing connections, which is represented in the equation below;
W=sum of wi=m,where i=1…N …eq.3
Assuming that outgoing link has a rate of r, then the ith connection rate is given by;
ri=wi/W r …eq.4
According to the four equations, it is possible to ascertain how the rate is affected following an increase in the number of connections. As connections, N increase, according to equation (1), the connection’s weight, Øi decreases, which effectively reduces wi. Given that W is unchanged and that weight is constant, according to equation (4), there will be a decrease in the rate of connection.
Conclusion
The report suggested a weighted round-robin scheduler that benefits from the low overhead schedules of the round-robin scheduling algorithm. The WRR is based on the RR scheduler since the latter is mainly designed for systems that share time resources. WRR assigns new resources in the form of time slices to every weight following the burst time. As such, short processes have a chance of getting more time allocated by the CPU. Accordingly, adopting the scheduler exhibits critical improvement in minimizing the scheduling criteria. The percentage is provided when all the packets in the queues are of similar size or the mean of the packet size is known.

References
Brázio, J. (2006). Analysis and design of advanced multiservice networks supporting mobility, multimedia, and internetworking: COST action 279 final reports. Dordrecht: Springer.
Kumar, A., Abdelhadi, A. & Clancy, T. (2018). Design and implementation of practical schedulers for M2M uplink networks: using MATLAB. Cham, Switzerland: Springer.
Noubir, G. & Raynal, M. (2014). Networked systems: second International Conference, NETYS 2014, Marrakech, Morocco, May 15-17, 2014. Revised selected papers. Cham: Springer.
Stoica, I. (2004). Stateless core: a scalable approach for quality of service on the Internet: winning thesis of the 2001 ACM Doctoral Dissertation Competition. Berlin-New York: Springer.
Yamanaka, N. (2004). High-performance backbone network technology. Tokyo New York: Institute of Electronics, Information, and Communication Engineers Marcel Dekker.