What are different policies to prevent congestion at different layers?

- Many times it happens that the demand for the resource is more than what network can offer i.e., its capacity. 

- Too much queuing occurs in the networks leading to a great loss of packets. 

- When the network is in the state of congestive collapse, its throughput drops down to zero whereas the path delay increases by a great margin. 

- The network can recover from this state by following a congestion control scheme.

- A congestion avoidance scheme enables the network to operate in an environment where the throughput is high and the delay is low. 

- In other words, these schemes prevent a computer network from falling prey to the vicious clutches of the network congestion problem. 

- Recovery mechanism is implemented through congestion and the prevention mechanism is implemented through congestion avoidance. 

- The network and the user policies are modeled for the purpose of congestion avoidance. 

- These act like a feedback control system. 

The following are defined as the key components of a general congestion avoidance scheme:

Ø  Congestion detection

Ø  Congestion feedback

Ø  Feedback selector

Ø  Signal filter

Ø  Decision function

Ø  Increase and decrease algorithms

- The problem of congestion control gets more complex when the network is using a connection-less protocol. 

- Avoiding congestion rather than simply controlling it is the main focus. 

- A congestion avoidance scheme is designed after comparing it with a number of other alternative schemes. 

- During the comparison, the algorithm with the right parameter values is selected. 

For doing so few goals have been set with which there is an associated test for verifying whether it is being met by the scheme or not:

Ø  Efficient: If the network is operating at the “knee” point, then it is said to be working efficiently.

Ø  Responsiveness: There is a continuous variation in the configuration and the traffic of the network. Therefore the point for optimal operation also varies continuously.

Ø Minimum oscillation: Only those schemes are preferred that have smaller oscillation amplitude.

Ø Convergence: The scheme should be such that it should bring the network to a point of stable operation for keeping the workload as well as the network configuration stable. The schemes that are able to satisfy this goal are called convergent schemes and the divergent schemes are rejected.

Ø Fairness: This goal aims at providing a fair share of resources to each independent user.

Ø  Robustness: This goal defines the capability of the scheme to work in any random environment. Therefore the schemes that are capable of working only for the deterministic service times are rejected.

Ø  Simplicity: Schemes are accepted in their most simple version.

Ø Low parameter sensitivity: Sensitivity of a scheme is measured with respect to its various parameter values. The scheme which is found to be too much sensitive to a particular parameter, it is rejected.

Ø Information entropy: This goal is about how the feedback information is used. The goal is to get maximum info with the minimum possible feedback.

Ø Dimensionless parameters: A parameter having the dimensions such as the mass, time and the length is taken as a network configuration or speed function. A parameter that has no dimensions has got more applicability.

Ø Configuration independence: The scheme is accepted only if it has been tested for various different configurations.

Congestion avoidance scheme has two main components:

Ø  Network policies: It consists of the following algorithms: feedback filter, feedback selector and congestion detection.

Ø  User policies: It consists of the following algorithms: increase/ decrease algorithm, decision function and signal filter.

These algorithms decide whether the network feedback has to be implemented via packet header field or as source quench messages.

When is a situation called as congestion?

- Network congestion is quite a common problem in the queuing theory and data networking. 

- Sometimes, the data carried by a node or a link is so much that its QoS (quality of service) starts deteriorating. 

- This situation or problem is known as the network congestion or simply congestion. 

This problem has the following two typical effects:

Ø  Queuing delay

Ø  Packet loss and

Ø  Blocking of the new connections

- The last two effects lead to two other problems. 

- As the offered load increases by the increments, either the throughput of the network is actually reduced or the throughput increases by very small amounts. 

- Aggressive re-transmissions are used by the network protocols for compensating for the packet loss. 

- The network protocols thus tend to maintain a state of network congestion for the system even if the actual initial load is too less that it cannot cause the problem of network congestion. 

- Thus, two stable states are exhibited by the networks that use these protocols under similar load levels. 

- The stable state in which the throughput is low is called the congestive collapse. 

- Congestive collapse is also called congestion collapse.

- In this condition, the switched computer network that can be reached by a packet when because of congestion there is no or little communication happening.

- In such a situation even if a little communication happens it is of no use. 

- There are certain points in the network called the choke points where the congestion usually occurs.

- At these points, the outgoing bandwidth is lesser than the incoming traffic. 

- Choke points are usually the points which connect the wide area network and a local area network. 

- When a network falls in such a condition, it is said to be in a stable state. 

- In this state, the demand for the traffic is high but the useful throughput is quite less.

- Also, the levels of packet delay are quite high. 

- The quality of service gets extremely bad and the routers cause the packet loss since their output queues are full and they discard the packets. 

- The problem of the network congestion was identified in the year of 1984. 

- The problem first came in to the scenario when the backbone of the NSF net phase dropped 3 times of its actual capacity. 

- This problem continued to occur until the Van Jacobson’s congestion control method was implemented at the end nodes.

Let us now see what is the cause of this problem? 

- When the number of packets being set to a router exceeds its packet handling capacity, many packets are discarded by the routers that are intermediate. 

- These routers expect the re-transmission of the discarded information. 

- Earlier, the re-transmission behavior of the TCP implementations was very bad. 

- Whenever a packet was lost, the extra packets were sent in by the end points, thus repeating the lost information. 

- But this doubled the data rate. 

- This is just the opposite of what routine should be carried out during the congestion problem. 

- The entire network is thus pushed in a state of the congestive collapse resulting in a huge loss of packets and reducing the throughput of the network. 

- Congestion control as well as congestion avoidance techniques are used by the networks of modern era for avoiding the congestive collapse problem. 

- Various congestion control algorithms are available that can be implemented for avoiding the problem of network congestion. 

- There are various criteria based up on which these congestion control algorithms are classified such as amount of feedback, deploy-ability and so on. 

Differentiate between persistent and non-persistent CSMA?

- CSMA or Carrier Sense Multiple Access makes use of LBT or listen before technique before making any transmission. 

- It senses the channel for its status and if found free or idle, the data frames are transmitted otherwise the transmission is deferred till the channel becomes idle again. 

- In simple words, we can say that CSMA is an analogy to human behavior of not interrupting others when busy. 

- There are number of protocols out which the persistent and the non – persistent are the major ones. 

- CSMA is based on the idea that if the state of the channel can be listened or sensed prior to transmitting a packet, better throughput can be achieved.

- Also, using this methodology a number of collisions can be avoided. 

- However, it is necessary to make the following assumptions in CSMA technology:

1. The length of the packets is constant.
2. The errors can only be caused by collisions except which there are no errors.
3. Capture effect is absent.
4. The transmissions made by all the other hosts can be sensed by each of the hosts.
5. The transmission time is always greater than the propagation delay.

About Persistent CSMA

- This protocol first senses the transmission channel and acts accordingly. 

- If the channel is found to be occupied by some other transmission, it keeps listening or sensing the channel and as soon as the channel becomes free or idle, starts its transmission. 

- On the other hand, if the channel is found empty, then it does not wait and starts transmitting immediately. 

- There are possibilities of collisions. 

- If one occurs, the transmitter must wait for random time duration and start again with the transmission. 

- It has a type called 1 – persistent protocol which makes transmission of probability 1 whenever the channel is idle. 

- In persistent CSMA there are possibilities of occurrence of collisions even if the propagation delay is 0. 

- However, collisions can only be avoided if the stations do not act so greedy. 

- We can say that this CSMA protocol is aggressive and selfish. 

- There is another type of this protocol called the P – persistent CSMA. 

- This is the most optimal strategy. 

- Here the channels are assumed to be slotted where one slot equals the period of contention i.e., 1 RTT delay. 

- The protocol has been named so because it transmits the packet with probability p if the channel is idle otherwise it waits for one slot and then transmits.

About Non–Persistent CSMA

- It is deferential and less aggressive when compared to its persistent counterpart. 

- It senses the channel and if it is busy it just waits and then again after sometime senses the channel unlike persistent CSMA which keeps on sensing the channel continuously. 

- As and when the channel is found free, the data packet is transmitted immediately. 

- If there occurs a collision it waits and starts again.

- In this protocol, even if the two stations become greedy in midst of transmission of some other station they do not collide probably whereas, in persistent CSMA they collide.

- Also, if only one of the stations become greedy in midst of some other transmission in progress, it has no choice but to wait. 

- In persistent CSMA this greedy stations takes over the channel up on completion of the current transmission.

- Using non – persistent CSMA can reduce the number of collisions whereas persistent CSMA only increases the risk. 

- But the non – persistent CSMA is less efficient when compared to the persistent CSMA.

- Efficiency lies in the ability of the protocols of detecting the collisions before starting the transmission. 

What is CPU Scheduling Criteria?

Scheduling is an essential concept that serves in the multitasking, multiprocessor and distributed systems. There are several schedulers available for this purpose. But these schedulers also require a criterion up on which they can decide how to schedule the processes. In this article we discuss about these scheduling criteria. Today a number of scheduling algorithms are available and all these have different properties. This is why these may work up on different scheduling criteria. Also the chosen algorithm may favor one class of processes more than the other.

What Criteria is used by algorithms for Scheduling?

Below mentioned are some of the criteria used by these algorithms for scheduling:
1. CPU utilization:
- It is a property of a good system to keep the CPU as busy as possible all the time.
- Thus, this utilization ranges from 0 percent to 100 percent.
- However, in the systems that are loaded lightly, the range is around 40 percent and for the systems heavily loaded it ranges around 90 percent.

2. Throughput:
- The work is said to be done if the CPU is busy with the execution of the processes.
- Throughput is one measure of CPU performance and can be defined as the number of processes being executed completely in a certain unit of time.
- For example, in short transactions throughput might range around like 10 processes per second.
- In longer transactions this may range around only one process being executed in one hour.

3. Turnaround time:
- This is an important criterion from the point of view of a process.
- This tells how much time the processor has taken for execution of  a processor.
- The turnaround time can be defined as the time duration elapsed from the submission of the process till its completion.

4. Waiting time:
- The amount of time taken for the process for its completion is not affected by the CPU scheduling algorithms.
- Rather, these algorithms only affects the time when the process is in waiting state.
- The time for which the process waits is called the waiting time.

5. Response time:
- The turnaround is not a good criterion in all the situations.
- The response time is favorable in the case of the interactive systems.
- It happens many a times that a process is able to produce the output in a fairly short time compared to the expected time.
- This process then can continue with the next instructions.
- The time taken for a process from its submission till production of the first response is calculated as the response time and is another criterion for the CPU scheduling algorithms.

All these are the primary performance criteria out of which one or more can be selected by a typical CPU scheduler. These criteria might be ranked by the scheduler depending up on their importance. One common problem in the selection of performance criteria is the possibility of conflict ion between them.
For example, increasing the number of active processes will increase the CPU utilization but at the same time will decrease the response time. This is often desirable to produce reduction in waiting time and turnaround time also. In a number of cases the average measure is optimized. But there are certain cases also where it is more beneficial to optimize the maximum or the minimum values.
It is not necessary that a scheduling algorithm that maximizes the throughput will decrease the turnaround time. Out of a mix of short and long jobs, if a scheduler runs only the short jobs, it will produce the best throughput. But at the same time the turnaround time for the long jobs will be so high which is not desirable.

What is a CPU Scheduler?

Scheduling is a very important concept when it comes to the multi-tasking operating systems. 

- It is the method via which the data flows, threads and processes are provided access to the shared resources of the computer system. 

- These resources include communications bandwidth, processor time, and memory and so on. 

- Scheduling is important as it helps in striking a balance the system processor and its resources effectively. 

- It helps in achieving the target QoS or quality of service. 

But what gave rise to scheduling? 

- Almost all the modern systems require to carry out multiple tasks i.e., multi-tasking and multiplexing as well which require a scheduling algorithm. 

- Multiplexing means transmission of the multiple data flows at the same time. - There are some other things also with which the scheduler is concerned. They are:

1. Throughput: It is the ratio of total number of processes executed to a given amount of time.
2. Latency: This factor can be sub – divided in to two namely response time and the turnaround time. Response time is the time taken from the submission of the process till its output is produced by the processor. The latter i.e., the turnaround time is the time period elapsed between the process submission and its completion.
3. Waiting/ fairness time: This is the equal CPU time given to each process or we can say that the time is allocated as per the priority of the processes. The time for which the processes wait in the ready queue is also counted in this.

- But in practical, conflicts may arise between these goals such as in case of latency versus throughput. 

- If such a case occurs, a suitable compromise has to be implemented by the scheduler. 

- The needs and the objectives of the user are used for deciding to who (of the above concerns) the preference is to be given. 

- In robotics or embedded systems i.e., in the real time environments, it becomes a duty of the scheduler for ensuring that all the processes meet their deadlines. 

- This is important for maintaining the stability of the system. 

- The mobile devices are given the scheduled tasks which are then managed by an administrative back end.

Types of CPU Schedulers

There are many types of CPU schedulers as discussed below:

1. Long-term Schedulers: 

- These schedulers facilitate the long term scheduling and are also known as the high level schedulers and the admission schedulers. 

- It is up to them to determine which processes and jobs are to be sent to the ready queue. 

- When the CPU makes an attempt for executing a program, the long term scheduler has the right to decide whether this program will be admitted to the currently executing set of processes. 

- Thus, it is dictated by this scheduler what processes are to be run and the extent of the concurrency has to be there.

- It also decides what amounts of processes have to be concurrently executed. 

- It also decides the handling of the split between the CPU intensive and I/O processes.  

2. Medium-term Schedulers: 

- The processes are temporarily removed from the main memory and placed up on the secondary memory by this scheduler. 

- This process is called “swapping in” and “swapping out”. 

- Usually this scheduler swaps out the following processes:

a)   processes that have been inactive since some time

b)   the processes that has raised a frequent page faulting

c)   processes having a low priority

d) processes that take up large memory chunks for releasing the main memory to other processes

- The scheduler later swaps in these processes whenever sufficient memory is available and if the processes are unblocked and not in waiting state.

3. Short-term Schedulers: 

It takes decision regarding the processes to be executed after clock interrupt. 

What is Throughput, Turnaround time, waiting time and Response time?

In this article we discuss about four important terms that we often come across while dealing with processes. These 4 factors are:

1.  Throughput

2.  Turnaround Time

3. Waiting Time

4.  Response time

What is Throughput?

- In communications networks like packet radio, Ethernet etc., throughput refers to the rate of the successful delivery of data over the channel. 

- The data might be delivered via either logical link or physical link depending on the type of communication that is being used. 

- This throughput is measured in the terms of bps or bits per second or data packets per slot. 

- Another term common in networks performance is the aggregate throughput or the system throughput. 

- This equals to the sum of all the data rates at which the data is delivered to each and every terminal in a network. 

- In computer systems, throughput means the rate of successful completion of the tasks by the CPU in a specific period of time. 

- Queuing theory is used for the mathematical analyzation of the throughout. 

- There is always a synonymy between the digital bandwidth consumption and the throughput. 

- Another related term is the maximum throughput.This bears synonymy with the digital bandwidth capacity.

What is Turnaround Time?

- In computer systems, the total time taken by the CPU from submission of a task or thread for execution to its completion is referred to as the turnaround time. 

- The turnaround time varies depending on the programming language used and the developer of the software.

- It deals with the whole amount of time taken for delivering the desired output to the end user following the start of the task completion process. 

- This is counted among the metrics that are used for the evaluation of the scheduling algorithms used by the operating systems. 

- When it comes to the batch systems, the turnaround time is more because of the time taken in the formation of the batches, executing and returning the output.

What is Waiting Time?

 

- This is the time duration between the requesting of an action and when it occurs. 

- Waiting time depends up on the speed and make of the CPU and the architecture that it uses. 

- If the processor supports pipeline architecture, then the process is said to be waiting in the pipe. 

- When the current task in processor is completed, the waiting task is passed on to the CPU for execution. 

- When the CPU starts executing this task, the waiting period is said to be over. 

- The status of the task that is waiting is set to ‘waiting’. From waiting status, it changes to active and then halts.

What is Response Time?

 

- The time taken by the computer system or the functional unit for reacting or responding to the input supplied is called the response time. 

- In data processing, there are various situations for which the user would perceive the response time:

Ø  Time between operator entering a request at a terminal  and

Ø  The instant at which appears the first character of the response.

- Coming to the data systems, the response time can be defined as the time taken from the receipt of EOT (end of transmission) of a message inquiry and start of the transmission in response to that inquiry. 

- Response is an important concept in the real time systems and it is the time that elapses between the dispatch of the request until its completion. 

- However, one should not confuse response time with the WCET.

- It is the maximum time taken by the execution of the task without any interference. 

- Response time also differs from the deadline. 

- Deadline is the time for which the output is valid. 

What are Real-time operating systems?

- The RTOS or a real time operating system was developed with the intention of serving the application requests that occur in real time. 

- This type of operating system is capable of processing the data as and when it comes in to the system. 

- This it does without making any buffering delays. 

- The time requirements are processed in 10ths of seconds or even on much smaller scale. 

- A key characteristic feature of the real operating system is that the amount of time they take for accepting and processing a given task remains consistent. 

- The variability is so less that it can be ignored totally.

Real time operating systems also there are two types as stated below:

1. The soft real –time operating system: It produces more jitter.
2. The hard real – time operating system: It produces less jitter when compared to the previous one.

- The real time operating systems are driven by the goal of giving guaranteed hard or soft performance rather than just producing a high throughput. 

- Another distinction between these two operating systems is that the soft real time operating system can generally meet deadline whereas the hard real time operating system meets a deadline deterministic ally.

- For the scheduling purpose, some advance algorithms are used by these operating systems. 

- Flexibility in scheduling has many advantages to offer such as the cso (computer system orchestration) of the process priorities becomes wider.

- But a typical real time OS dedicates itself to a small number of applications at a time. 

- There are 2 key factors in any real –time OS namely:

1. Minimal interrupt latency and
2. Minimal thread switching latency.

- Two types of design philosophies are followed in designing the real  time Oss:

1. Time sharing design: As per this design, the tasks are switched based up on a clocked interrupt and events at regular intervals. This is also termed as the round robin scheduling.
2. Event – driven design: As per this design, the switching occurs only when some other event demands higher priority. This is why it is also termed as priority scheduling or preemptive priority.

- In the former designs, the tasks are switched more frequently than what is strictly required but it proves to be good at providing a smooth multi – tasking experience. 

- This gives the user an illusion that he/ she is solely using the machine. 

- The earlier designs of CPU forced us to have several cycles for switching a task and while switching it could not perform any other task. 

- This was the reason why the early operating systems avoided unnecessary switching in order to save the CPU time. 

- Typically, in any design there are 3 states of a task:

1. Running or executing on CPU
2. Ready to be executed
3. Waiting or blocked for some event

- Many of the tasks are kept in the second and third states because at a time the CPU can perform only one task. 

- The number of tasks waiting to be executed in the ready queue may vary depending on the running applications and the scheduler type being used by the CPU. 

- On multi – tasking systems that are non – preemptive, one task might have to give up its CPU time to let the other tasks to be executed. 

- This leads to a situation called the resource starvation i.e., the number of tasks to be executed is more and the resources are less.

What are the metrics that can be used during performance testing?

One of the most important parts that together make up the complete and effective software testing is the performance testing. Perhaps no software system or application can do without performance testing and testing of any software system or application is incomplete without this one. 

"The determination of the performance of a software system or application in terms of how and when and responsiveness and stability under different particular work loads is nothing but performance testing".

Apart from this there are several other attributes that can be taken care of by the performance testing like for example:

1. Scalability
2. Reliability
3. Resource usage and so on.

The concept of performance testing falls under the concept of performance engineering. The practice of performance testing is aimed at building the performance in to the architecture as well as design of the software system or applications before the actual coding of the software system or application begins. 

We have so many other types of testing that together make up the complete performance testing and have been mentioned below:

1. Load testing
2. Stress testing
3. Soak testing or Endurance testing
4. Spike testing
5. Isolation testing and
6. Configuration testing

Metrics used during Performance Testing

The performance testing cannot be carried out all alone by itself! Rather it is supported by some specific metrics called performance metrics. In this article we shall discuss about the metrics that are to be used during the performance testing.  We shall discuss them one by one:

 1. Average response time: 

This is the time that takes in to consideration all the response cycle ups or round trip requests until a particular point is reached and is the mean of all the response times. Response times can be measured in any of the following way:

      a) Time to last byte or 

      b) Time to first byte

   

      2. Peak response time: 

    This is similar to the previously mentioned metric and represents the longest cycle at a particular point in a particular test. Peak response time is an indication of some potential problem in our software system or application.

   

     3. Error rate: 

   The occurrence of errors under load during the processing of the requests is perhaps the most expected thing during the testing. it has been noted that the most of the errors are reported when the load on the application reaches a peak point and further from there the software system or application is not able to process any requests. Thus error rate provides a percentage of the HTTP status code responses as errors on the servers.

    

     4. Throughput: 

   This performance metric gives you a percentage of the flow of data back and forth from the servers and is measured in units of KB per second.

   

    5. Requests per second (RPS): 

    It gives a measure of the requests that are sent to the target server including requests for CSS style sheets, HTML pages, JavaScript libraries, flash files, XML documents and so on.

    6. Concurrent users: 

    This performance metric is perhaps that best way for expressing the load that is being levied on the software system or application during the performance testing. This metric is not to be equated to the RPS since there are possibilities of one user only generating a high number of requests and on the other hand a user not constantly generating requests.

     7. Cross result graphs: 

     It shows difference between post tuning and pre-tuning tests. 

What are different characteristics of Scalability Testing?

Scalability can be essentially defined as the ability of a software application, network, process or program to effective and gracefully handle the increasing workload and effectively and easily carry out the specified tasks assigned properly. Throughput is the best example for this ability of a software application.

- Scalability as such is very difficult to define without practical examples.
- Therefore, scalability is defined based on some dimensions.
- Scalability is very much needed in communication areas like in a network, in software applications, in handling huge databases and it is also a very important aspect in routers and networking.
- Software applications and systems having the property of scalability are called scalable software systems or applications.
- They improve throughput to surprising extent after addition of new hardware devices. Such systems are commonly known as scalable systems.
- Similarly if a design, network, systems protocol, program or algorithm is suitable and efficient enough and works well when applied to greater conditions and problems in which the input data is in large amount or the problem or situation has got several nodes, they are said to be efficiently scalable.

If, during the process of increasing the quantity of input data the program fails, the program is not said to scale. Scalability is so much needed in the field of information technology. Scalability can be measured in several dimensions. Scalability testing deals with testing of these dimensions only.

The kinds of scalability testing have been discussed in detail below:

- Functional scalability testing:
In this testing new functionalities which are added to the software application or the program to enhance and improve its overall working are tested.

- Geographic scalability testing:
This testing tests the ability of the software system or the application to maintain its performance and throughput, and usefulness irrespective of distributing of working nodes in some geographical pattern.

- Administrative scalability testing:
This testing deals with the increment of working nodes in software, so that a single difficult task is divided among smaller units making it much easier to accomplish.

- Load scalability testing:
This testing can be defined as the testing of the ability of a divided program to divide further and unite again to take light and heavy workload accordingly.

There are several examples available for scalability today. Few have been listed below:

- Routing table of the routing protocol which increases in extent with respect to the increase in the extent of network.
- DBMS (data base management system) is scalable in the sense that more and more data can be uploaded to it by adding new required devices.
- Online transaction processing system can also be stated as scalable as one can upgrade it and more transactions can be done easily at one time.
- Domain name system is a distributed system and works effectively even when the hosting is on the level of World Wide Web. It is scalable.

Scaling is done basically in two ways. These two ways have been discussed below:

- Scaling out or scaling horizontally: This method of involves addition of several nodes or work stations to an already divided or distributed software application. This method has led to the development of technologies namely batch processing management and remote maintenance which were not available before the discovery of this technology.

Scaling up or scaling vertically:
Scaling up or scaling vertically can be defined as the addition of hardware or software resources to any single node of the system. These resources can either be CPUs or memory devices. This method of scaling has led to a tremendous improvement in virtualization technology.