What is a choke packet?

- The networks often experience problems with congestion and flow of the traffic. 

- While implementing flow control a special type of packet is used throughout the network. 

- This packet is known as the choke packet. 

- The congestion in the network is detected by the router when it measures the percentage of the buffers that are actually being used. 

- It also measures the utilization of the lines and average length of the queues. 

- When the congestion is detected, the router transmits choke packets throughout the network. 

- These choke packets are meant for the data sources that are spread across the network and which have an association with the problem of congestion. 

- These data sources in turn respond by cutting down on the amount of the data that they are transmitting. 

- A choke packet has been found to be very useful in the maintenance tasks of the network. 

- It also helps in maintaining the quality to some extent. 

- In both of these tasks, it is used for informing the specific transmitters or the nodes that the traffic they are sending is resulting in congestion in the network. 

- Thus, the transmitters or the nodes are forced to decrease the rate at which they are generating traffic. 

- The main purpose of the choke packets is controlling the congestion and maintaining flow control throughout the network. 

- The router directly addresses the source node, thus causing it to cut down its data transmission rate. 

- This is acknowledged by the source node by making reductions by some percentage in the transmission rates. 

- An example of the choke packet commonly used by the most of the routers is the source quench packet by ICMP (internet control message protocol).  

- The technique of using the choke packets for congestion control and recovery of the network involves the use of the routers. 

- The whole network is continuously monitored over by the routers for any abnormal activity.

- Factors such as the space in the buffers, queue lengths and the line utilization are checked by the routers. 

- In case the congestion occurs in the network, the choke packets are sent by the routers to the corresponding parts of the network instructing them to reduce the throughput. 

- The node that is the source of the congestion has to reduce its throughput rate by a certain percentage that depends on the size of the buffer, bandwidth that is available and the extent of the congestion. 

- Sending the choke packets is the way of routers telling the nodes to slow down so that the traffic can be fairly distributed over the nodes. 

- The advantage of using this technique is that it is dynamic in nature. 

- The source node might send as much data as required while the network might inform that it is sending large amounts of traffic.

- The disadvantage is that it is difficult to know by what factor the node should reduce its throughput.

- The amount of the congestion being caused by this node and the capacity of the region in which congestion has occurred is responsible for deciding this. 

- In practical, this information is not instantly available. 

- Another disadvantage is that after the node has received the choke packet, it should be capable of rejecting the other choke packets for some time. 

- This is so because many additional choke packets might be generated during the transmission of the other packets. 

The question is for how long the node is supposed to ignore these packets? 

- This depends up on some dynamic factors such as the delay time. 

- Not all congestion problems are same, they vary over the network depending up on its topology and number of nodes it has. 

What are general principles of congestion control?

- Problems such as the loss of data packets occur if the buffer of the routers overflows.

- This overflow is caused by the problem of the congestive collapse which is a consequence of the network congestion. 

- If the packets have to be re-transmitted more than once, it is an indication that the network is facing the problem of congestion. 

- Re-transmission of the packets is the treatment of only this indication but not for problem of the network congestion. 

- In the problem of congestive collapse, there are a number of sources that make attempts for sending data and that too at a quite high rate. 

- For preventing this problem of the network congestion, it requires mechanisms that are capable of throttling the sending node if in case the problem of network congestion occurs. 

- Network congestion is a real bad thing as it manifests in the network’s performance that the upper layer applications receive. 

- There are various approaches available for preventing and avoiding the problem of network congestion and thus implementing proper congestion control. 

- When the capacity of the network is exceeded by the demands for the resources and too much queuing occurs in the network causing loss of packets, congestion of packets is said to occur. 

- During this problem of network congestion, the throughput of the network might drop down to zero and there might be a high rise in the path delay. 

- Network can recover from the state of congestive collapse using a congestion control scheme. 

- A network can operate in a region where there is high throughput but low delay with the help of the congestion avoidance scheme.

- These schemes keep the network away from falling in to a state of congestive collapse. 

- There is a big confusion over congestion control and congestion avoidance. Most of us think it is the same thing but it is not. 

- Congestion control provides a recovery mechanism whereas the congestion avoidance provides a prevention mechanism. 

- Today’s technological advances in the field of networking have led to a rise in the network links’ bandwidth. 

- In the year of 1970, ARPAnet came in to existence and built using the leased telephone lines that had a 50 kbits/second bandwidth. 

- LAN (local area network) was first developed in the year of 1980 using token rings and Ethernet and offered a bandwidth of 10 mbits/ second. 

- During the same time many efforts were made for standardizing the LAN using the optical fibers providing a 100 mbits/seconds and higher bandwidth. 

- Attention to the congestion control has been increased because of the increase in the mismatching that occurs between the various links composing the network. 

- Routers, IMPs, gateways, intermediate nodes links etc. are the hot-spots for the congestion problems. 

- It is at these spots that the bandwidth of the receiver falls short for accommodating all the incoming traffic. 

- In the networks using the connection-less protocols, it is even more difficult to cope with the problems of network congestion. 

- It is comparatively easy in the networks using the connection-oriented protocols.

- This happens so because in such networks, the network resources are kept under advance reserve during setting up the connection.

- One way for controlling congestion problems is preventing the setting up of new connections if congestion is detected anywhere in the network but it will also prevent the usage of the reserved resources which is a disadvantage. 

What is the difference between congestion control and flow control?

Flow control and congestion control are similar sounding concepts and often confuse us sometimes. In this article we shall discuss about the differences between these two. 

- Computer networks use the flow control mechanism for keeping control over the data flow between two nodes in such a way that the receiver if it is slower when compared to the sender is not outrun by it. 

- The mechanism of flow control also provides ways to the receiver to maintain control over the speed with which it transmits the information.

- On the other side, the congestion control provides mechanism for the controlling the data flow under the condition of actual congestive collapse. 

- The mechanism keeps a control over the entry of data in to the network so that this traffic can be handled by the network effectively.  

- The mechanism of flow control does not let the receiving node get overwhelmed by the traffic that is being sent by another node. 

There are several reasons why this flow of data gets out of control and affects the network negatively. 

- First reason being that the receiving node might not be capable of processing the incoming data as fast as it is being sent by the sender node. 

- Based on these reasons there are various types of flow control mechanisms available. 

- However, the most common categorization is based on the fact whether the feedback is being sent to the sender or not. 

- There is another flow control mechanism called the open loop flow control mechanism. 

- In this mechanism no feedback is sent to the sender by the receiver and this perhaps the most widely used flow control mechanism. 

- Opposite of open loop flow control mechanism is the closed loop flow control. 

- In this mechanism, the receiver sends back congestion information to the sender. 

- Other commonly used flow control mechanisms are:

Ø  Network congestion

Ø  Windowing flow control

Ø  Data buffer etc.

- Congestion control offers such methods that can be used for regulating the incoming traffic in the network to such an extent where the network itself can manage all that.
- In congestion control, the network is prevented from falling in to a state of congestive collapse. 
- In such a state either little or no communication happens.
- This little communication is of no help. 
- Switching networks usually require congestion control measures than any other type of networks. 
- The congestion control is driven by the goal of keeping the number of data packets at such a level that the performance of the network would be reduced dramatically.
- Congestion control mechanism can be seen even in protocols such as UDP (user datagram protocol), TCP (transport control protocol) and other transport layer protocols. 
- TCP makes use of the exponential back off and slow start algorithms. 
- We classify the congestion control algorithms based up on the feedback that is given by the network, the performance aspect that has to be improved, and modifications that have to be made for the present network, fairness criterion that is being used and so on. 

- Congestion and flow control are two very important mechanisms used for keeping the traffic flow in order. 
- Flow control is a mechanism that stretches from one end to another i.e., between the sender and the receiver where the speed of sender is much higher than that of the receiving node. 
- Congestion control is implemented for preventing packet loss as well as delay that is caused as a side effect of the network congestion. 
- Congestion is meant for controlling the traffic of the entire whereas flow control is limited to transmission between two nodes.

What is meant by multi-destination routing?

- So many routing algorithms have been devised to aid in routing under different conditions.
- Effective routing algorithms have been developed that are capable of routing the messages from one source node to a number of receiving nodes i.e., the multiple destination nodes.
- These algorithms are termed as the multi – destination routing algorithms and the process is therefore called as the multi – destination routing.
- This type of routing has been developed for the minimization of the cost of the network i.e., NC (network cost).
- Network cost can be defined as the sum of all the links’ weights that consist of the routing path.
- There are many heuristic algorithms available for determining the NC min path.
- This problem falls under the category of the NP – complete problems.
- Heuristics are available for the traveling salesman problem and MST (minimum spanning tree) variations.
- Global information is used by both of them.
- Another set of such heuristics is available that uses only shortest paths for reaching the destinations.
- The best worst case performance is exhibited by the MST algorithm.
- However, one study revealed that effectiveness of the simpler heuristics is higher.
- The network cost (NC) is often compared with the destination cost (DC).
- Destination cost is the sum of the cost of all the shortest paths that lead to the destination.
- A scheme of algorithms has been developed for trading off between these two costs i.e., the NC and DC.  
- The sender of the transmitted data cannot be taken as a single node in a network where the cooperative communication is supported.
- This asks for the re-investigation of the traditional link concept.
- Any routing scheme thus depending up on this link concept needs to be reconsidered.
- Also, the potential performance gain resulting because of the cooperative communication needs to be exploited.

- Routing often gets complicated for some networks where the selection of the paths is no longer the job of a single entity.
- Rather, a number of entities are involved in the selection of the paths.
- Multiple entities can even select specific parts of a path.
- If these selected paths are chosen by the entities for their own objectives optimization then it can lead to inefficiency or serious complications in the network since they may or may not conflict with the other entities’ objectives.
- This would become clear from the following example, consider traffic moving in a system of roads.
- Now here each driver selects a path that would minimize only his/her traveling time.
- In this kind of routing, there are longer equilibrium routes (i.e., longer than the optimal.) for almost all other drivers.
- This is often termed as the Braess paradox.
- Another example is of the routing the AGVs (automated guided vehicles) by a model on some terminal.
- For prevention of the simultaneous usage of the infrastructure’s same part reservations are made. - This is called as the context – aware routing.
- The internet is divided in to a number of divisions which are nothing but Ass i.e., the autonomous system like ISPs.
- All these systems have control over the routes that lie in their own network at various different levels.

Following steps are involved in multi – destination routing:
1. The BGP protocol is used for selecting the AS – level paths.
2. A sequence of autonomous systems is produced by the BGP protocol via which the packet flow will take place.
3. The neighboring Ass offer multiple paths for each of the AS from which it can choose. Paths are selected based up on the relationships between the neighboring systems.
4. Each selected path refers to multiple corresponding router level paths.

What is meant by flow based routing?

- The routing algorithm that considers the flow in the network is known as flow based routing. 

- It takes into consideration the amount of traffic flowing in the network before making a decision regarding the outgoing link over which the packet has to be sent. 

- The ability to characterize the traffic flow’s nature with respect to time is the key to the successful implementation of the flow based routing. 

- For any given line, if we know what is its average flow or capacity we can very well compute the mean packet delay of the line using the queuing theory. - This is the basic idea behind the implementation of this algorithm. 

- This idea reduces the size of the problem i.e., only the minimum average delay has to be calculated for the sub net and nothing else. 

- Thus, the flow based routing considers the load and topology of the network while other routing algorithms do not. 

- In few networks, the mean data flow existing between two nodes might be predictable as well as relatively stable. 

- There occur such conditions under which the average traffic between the two points is known. 

- In such conditions the mathematical analyzation of the flow is possible. 

- This calculation can be used in the optimization of the routing protocol. 

- The flow weighted average can be straightforward calculated which in turn can be used for the calculation of the mean packet delay of the entire sub-net. 

The flow based routing algorithm requires the following things in advance:

Ø  Topology of the subnet

Ø  Traffic matrix

Ø  Capacity matrix

Ø  A routing algorithm

- Information flow based routing algorithms are commonly used in the wireless sensor networks. 

- These days, the measure of information is being used a criterion for the analyzation of the performance of the flow based routing algorithms. 

- One research has put forward an argument stating that since the sensor network is driven by the objective of the estimation of a 2D random field, the information flow must be maximized over the entire field and the sensor’s lifetime. 

In response to this algorithm two types of flow based routing algorithm have been designed namely:

1. Maximum information routing (MIR) and
2. Conditional maximum information routing (CMIR)

- Both of these algorithms have proved to be quite significant when compared to the exiting algorithm – maximum residual energy path or MREP.

About MREP Algorithm

 

- This proves to be quite effective in conservation of the energy. 

- The battery energy which is limited is taken as the most important resource. - For the maximization of the lifetime, the energy consumption has to be balanced throughout the nodes. 

- This should be done in proportion to the resource reserves. 

- This is better than routing for the minimization of the absolute consumed power.

About MIR Algorithm

 

- The ideology behind the MIR algorithm is that there is inequality between the nodes. 

- For example, two very close nodes might not provide twice as much information provided by a lonely node. 

- Therefore, the nodes that provide more information are only given preference. 

- An additional penalty according to the node’s contribution is added to the node for achieving the above mentioned preference. 

- Dijkstra’s algorithm is used for the computation of the shortest path. 

- This helps in sending the data to the sensor as per both the information of the origin and the power consumed.

About CMIR Algorithm

- This one is a hybrid algorithm and makes use of MIR to some extent and then uses MREP algorithm for the rest of the cycle. 

- This hybrid version is better than the above two standalone algorithms since it runs better. 

Shortest Path Routing - a type of routing algorithm

- The usage of the re-configurable logic has been increasing day by day both in scope as well as number. 

- Re-configurable computing combines both the hardware speed and the flexibility of the software. 

- This is the result of the combination of the highspeed computing and re-configurability.

- Tough requirements are posed up on the routing in a network by the increased QoS i.e., the quality of service. 

- This increase in the complexity of the computational capabilities bears an exponential relation with the increased QoS. 

- However, additional computational resources are needed for achieving a network performance level that is acceptable. 

- Re-configurable computing offers a promising solution to the issues of the computations in the routing process.

There are 3 major aspects of the shortest path routing as mentioned below:

Ø Path selection: This involves the various algorithms such as the Dijkstra’s and bellman – ford algorithms and shortest path and minimum – hop routing.

Ø Topology change: Changes in the topology are detected using the beacons.

Ø  Routing protocols: This involves routing protocols such as the link state routing protocols and distance vector protocols.

- Forwarding and routing are two different things. 

- In forwarding, the data packet is directed towards an outgoing link and an individual router is used that also maintains a forwarding table.

- Routing computes the paths that have to be followed by the packets. 

- Routers exchange the path information between themselves and the forwarding table is created by each and every router in the chain.

Routing is important for the following three main reasons:

Ø  End-to-end performance: The user performance is affected by the path quality, throughput, packet loss and delay in propagation.

Ø  Use of the network resources: The traffic has to be balanced between the several links and routers. The traffic is directed towards the links that are lightly loaded for avoiding the congestion.

Ø  Transient disruptions during changes: These disruptions include the load balancing problems, maintenance, failures etc. the packet loss as well as the delay has to be limited while the changes take effect.

- Shortest path routing is based up on a path selection model that gives more preference to the destination. 

- This type of routing is insensitive to load as in it involves the static link weights.

- Here, either the sum of the link weights or the minimum hope is considered. 

- In a shortest path problem, the link costs are given for a network topology. 

- For example, C(x,y) denotes the cost of the node x to node y. 

- If the two nodes x and y are not adjacent to each other the cost is taken to be infinity. 

- The least cost paths linking all the nodes are computed from a node taken as the source. 

- Dijkstra’s shortest path algorithm is one of the algorithms used in the shortest path routing. 

- A central role is played by the problems involving finding the shortest paths in the designing and the analyzation of the networks.

- A majority of the routing problems can be taken as the shortest path problems and solved if each link in the network has appropriate cost assigned to it. 

- This cost even reflects the bandwidth as well as the bit error ratio if required. - A number of algorithms are available for computing the shortest path.

- But these algorithms are applicable only if a single non – negative additive metric characterizes every edge in the network.

- Out of these algorithms, the Dijkstra’s algorithm is the most famous one. 

- This algorithm find its use in the OSPF (open shortest path first) routing procedure of the internet. 

- In this algorithm the number of operations carried out are proportional to the number of nodes in the network and the iteration is carried for n-1 times. 

What are applications of flooding algorithm?

- Flooding algorithm and its many other variants are used as material distributing algorithm.

- This algorithm distributes the messages to all the hosts in the entire graph. 

- This algorithm since it acts like a flood and therefore has been named so. 

- In this simple yet useful distribution or routing algorithm, every packet that a node receives is transmitted to every other outgoing link. 

This algorithm is available in many variants but in every variant the following two things are common:

1. Each node acting as receiver and transmitter.

2. Each node responsible for forwarding received message to all its neighboring nodes except the one from which the message came. 

- Thus, the messages are eventually delivered to the hosts spread across the network. 

- Flooding algorithm might have been more useful if it would have been more complex. 

- Also, then it would have been possible to avoid the duplicate messages and infinite loops that occur because of them. 

Applications of Flooding Algorithm

In this article we list some of the application of the flooding algorithm.

1. Used in computer networking

2. Used in graphics

3. These algorithms are quite useful for solving numerous mathematical problems such as the maze problems.

4. Used for solving problems in the graph theory. 

5. Used in systems which make use of bridging. 

6. Used in systems like usenet.

7. Implemented in peer – to – peer file sharing

8. Flooding algorithms are often implemented as a part of some of the routing protocols as in OSPF, DVMRP and so on. 

9. It is also used in the protocols used in the ad hoc wireless networks.

10.There is a variant of flooding algorithm called the selective flooding which is capable on addressing various issues of flooding algorithm partially by allowing the packets to be sent only in the appropriate right direction. The packets are not sent on each and every line. 

11. Another variant of the flooding algorithm called the similarity algorithm is used graph matching algorithm. 

- This variant of the flooding algorithm is quite versatile and has got an application in the schema matching. 

- Matching the contents of the two data schemas has got an important role to play in many biochemical applications, e – business and other data warehousing applications etc. 

- The similarity flooding algorithm is based on a computation that is fixed and can be used across a number of scenarios. 

- Two graphs are passed to the algorithm as the input parameters. 

- These graphs might be of catalogs, schemas or even data structures etc. 

- The algorithm then produces a mapping between the corresponding nodes of the two graphs as output. 

- It depends on the goal of the matching what subset of the mapping has to be chosen using filters. 

- After the algorithm has been executed, a human tester is expected is expected to check and verify the results. 

- The results might be adjusted by the tester if required. 

- In this method, the accuracy of the algorithm is evaluated by number of the adjustments that are necessary.

- In some cases, an accuracy metric might be used for the estimation of the labor savings that could be obtained by the users by means of this similarity flooding algorithm for obtaining a first matching pair.

- Finally, this algorithm can be deployed as an operator of very high level in a test bed that has been implemented for the management of the output mappings and the information models. 

- There are different types of matching problems and thus each type requires following a different approach. 

- For example, the relational schemas can only be matched using SQL data types.

Difference between adaptive and non - adaptive algorithms?

- Routing is the process of sending information from one point of network to another. 

- The originating point is called the source and the last point is called the destination. 

- Through the way a number of intermediate nodes might or might not be encountered. 

- Routing is sometimes compared with bridging. 

- Both of these accomplish the same purpose for the casual observer. But it is not so. 

- The basic difference between the two is that the routing is done at the layer 3 i.e., the network layer of the OSI model and the bridging takes place at the layer 2 i.e., data link layer of the OSI model. 

- Because of this distinction, the input supplied to the two processes is different and thus the task of path selection occurs in different ways. 

- The routing algorithm is included as a part of the network layer software. 

- The primary responsibility of this software is to decide on which line the incoming traffic must be forwarded i.e., what will be the next node. 

- Certain metrics are used by the routing protocols for the evaluation of the path that is most appropriate for the transmission of a packet. 

- These metrics include reliability, path bandwidth, current load, delay and so on. 

- These metrics help in determining the optimal path towards a destination. 

- Routing tables are created and maintained by the routing algorithms in order to aid the path determination process.

- The tables will contain what routing information is entirely based up on the routing algorithm that is being used. 

- The routing tables are filled by a variety of information by the routing algorithms. 

- If the internal subnet used is the datagram subnet, then for every datagram that arrives, a new decision has to be taken since the routes keep changing in this case after every transmission.

- On the other hand in virtual circuit subnet, all the decisions are taken with the setting up of the virtual circuit. 

- Once the connection or the links are established, the same path is followed by all the packets. 

The routing algorithms can be classified in to two major categories namely:

1. Non – adaptive algorithms and
2. Adaptive algorithms

- Another name for non – adaptive algorithms is the static algorithms. 

- Here the computation regarding the various routes is done in advance and the same routes are followed by all the packets. 

- The adaptive algorithms are better known as the dynamic algorithms. 

- In this type of algorithms, the routes are not computed in advance, rather the route is decided up on the arrival of a particular packet depending up on the traffic and the topology of the network. 

We have three different types of algorithms under the category of non – adaptive algorithms as mentioned below:

1. Shortest path routing: This algorithm makes use of the Dijkstra’s algorithm for computing the shortest path where nodes and communication links are represented by vertices and edges of the graph respectively.
2. Flooding: Here, the arriving data packet is transmitted on all the outgoing lines save the one on which it arrived. Its selective flooding variation is commonly used.
3. Flow based routing: This algorithm takes in to consideration the present flow of the network before deciding on which line the packet must be transmitted.

And following are some of the adaptive algorithms:

1. Distance vector routing: It requires knowledge about the whole network and is associated with the count  to infinity problem.
2. Link state routing: It requires knowledge about neighborhood.
3. Hierarchical routing: It is used for very large networks.
4. Optimized link state routing: It is used for mobile hosts. 

What is meant by an optimal route?

- For selecting a path or route, a routing metric has to be applied to a number of routes so as to select the best out of them. 

- This best route is called the optimal route with respect to the routing metric used. 

- This routing metric is computed with the help of the routing algorithms in computer networking.

- It consists of information such as network delay, hop count, network delay, load, MTU, path cost, communication cost, reliability and so on.

- Only the best or the optimal routes are stored in the routing tables that reside in the memory of the routers. 

- The other information is stored in either the topological or the link state databases. 

- There are many types of routing protocol and each of them has a routing metric specific to it. 

- Some external heuristic is required to be used by the multi-protocol routers for selecting between the routes determined using various routing protocols. 

- For example, the administrative distance is the value that is attributed to all the routes in Cisco routers. 

- Here, smaller distances mean that the protocol is a reliable one. 

- Host specific routes to a certain device can be set up by the local network admin. 

- This will offer more control over the usage of the network along with better overall security and permission for testing. 

- This advantage comes handy especially when it is needed to debug the routing tables and the connections. 

In this article we discuss about the optimal routes. 

- With the growing popularity of the IP networks as the mission critical tools for business, the need for methods and techniques using which the network’s routing posture can be monitored is increasing.

- Many routing issues or even incorrect routing can lead to undesirable effects on the network such as downtime, flapping or performance degradation. 

- Route analytic are the techniques and tools that are used for monitoring the routing in a network. 

The performance of the network is measured using the following 2 factors:

1. Throughput or the Quantity of service: This includes the amount of data that is transmitted and time it takes to transfer.
2. Average packet delay or Quality of service: This includes the time taken by a packet to arrive at its destination and the response of the system to the commands entered by the user.

- There is always a constant battle between the fairness and optimality or we can say between quantity of service and quality of service. 

- For optimizing the throughput, the paths existing between the nodes have to be saturated and the response time from source point to destination point must be noticed. 

For finding the optimal routes, we have two types of algorithms namely:

1. Adaptive Algorithms: These algorithms are meant for the networks in which the routes change in a dynamic manner. Here the information regarding the route to be followed is obtained at the run time itself from adjacent as well as the all other routers. The routes change whenever there is a change in the load, change in the topology and every delta T seconds.
2. Non – adaptive algorithms: These algorithms the same routes cannot be followed every time. Therefore the measurements that were made for the previous condition cannot be used for the current condition. The routes thus obtained are called static routes and are computed at the boot time.

Finding optimal routes requires following the principle of optimality according to which the optimal path between an intermediate router and the destination router lies on the same route from the source to the destination route.