Optimality Principle in Computer Networks

In this tutorial, you will learn the basics of optimality theory, shortest path, and flooding. After reading this tutorial, you will learn how a router determines the optimal and shortest path in the network to send packets.

Contents:

1. Optimality, Shortest Path, and Flooding
2. The Optimality Principle
3. Sink Tree in Optimality
4. Shortest Path Algorithm
5. Dijkstra Algorithm
6. Flooding Technique
7. Prevent Flooding on a Network
8. Flooding Advantages

Optimality, Shortest Path, and Flooding

Before learning about routing algorithms, it is necessary to understand the techniques which give an optimal and shortest path for sending packets.

• If the optimal and shortest path technique is chosen for sending the packets, the delay will be reduced, increasing the quality of services on the network.
• Using shortest path techniques, the router can forward packets to the destination with minimal cost.
• On a network, routers must communicate so that they can learn neighbors and build routing tables.
• When a packet arrives at a router, instead of finding a destination router among several routers, the sending router broadcasts the packet to all outgoing links. This technique is called flooding, and it reduces the time taken to find the destination.
• Optimality, Shortest Path, and Flooding are techniques used by routers before using routing protocols.

The Optimality Principle

It is necessary to find the optimal path to send packets regardless of network topology or traffic. The router creates a routing table, lists the optimal routes, and selects the best optimal path to send the packets.

The below diagram explains the Optimality Principle.

• As shown in the figure, if the path from Router-A to Router-C is optimal and Router-B falls in the middle of this path, the path from Router-B to Router-C will also be optimal.
• Suppose the route from Router-A to Router-B is r1 and from Router-B to Router-C is r2.
• If a router better than r2 existed from Router-B to Router-C, it can be combined with r1 to improve the route from Router-A to Router-B. This sentence contradicts our statement that r1 r2 is optimal.
• The tree is formed when there exists a set of optimal routes from multiple sources to a given destination. This tree is known as the sink tree, in which the distance metric is the number of hops.

Sink Tree in Optimality

Routers use routing algorithms to find and use sink trees.

The below diagram explains the sink tree of a router in a network.

• As shown in the figure, there are 10 routers on a network. The topology graph of the router on the left is cyclic, while the sink tree for Router-2 is shown on the right.
• The structure of the sink tree is a directed acyclic graph (DAG), in which the DAG has no loops.
• In the sink tree, no loop exists, so packets sent by the sender will be distributed within a limited number of routers.
• The sink tree is not necessarily unique. It may be possible that there exist other trees with similar path lengths.

Shortest Path Algorithm

In a network, not all routers know all the details of the network. Therefore, routers build a graph in a network to find the shortest path for communication.

• To find the shortest path, first, a graph of the network is constructed. The shortest path with minimum cost is measured in terms of the number of hops on the network. It can also be measured in terms of geographical distance in kilometers.
• The shortest path is the path that has the minimum number of edges. Labels on the edges can be calculated as a function of distance, bandwidth, traffic, cost, delay, etc.
• Dijkstra is one of the most popular algorithms for finding the shortest path.
• In Dijkstra, no path is known at the beginning, so all nodes have an infinite value. As the algorithm works, paths are found, the value of the link changes, indicating better paths.

Dijkstra Algorithm

Dijkstra’s algorithm is used to find the shortest path for communication. Let us understand the working of the Dijkstra algorithm with an example.

The diagram below explains the Dijkstra algorithm.

• As shown in the figure, eight routers are connected. The above graph is weighted and undirected, as weight is assigned to each edge.
• Now, we want to find the shortest path from Router-A to Router-D. So, first, we’ll mark Router-A as permanent.
• Router-A checks for adjacent routers. Router-B and Router-G are adjacent routers to A, so both are re-labeled with A’s distance.
• Router-B checks all nodes adjacent to it. Router-C and Router-E re-labeled their distance with Router-B.
• Similarly, all routers will be re-labeled with the distance to other routers, and the path cost from one router to another will be minimal.

Flooding Technique

Routers have local knowledge of the network, which means they only have information about their neighboring routers and not the entire network. So they take the routing decision based on local knowledge. Routers decide to send incoming packets on each outgoing line, a process known as flooding.

• When the flooding technique is used, a large number of duplicate packets are generated on the network, due to which the network becomes congested.
• In flooding, the hop counter is present in the header field of the packet, which is decremented at each router. When the packet hop counter reaches zero, the packet is discarded by the network and is not forwarded.
• The hop counter is set in such a way that it should be the length of the path from sender to receiver.
• The hop counter is set to the full diameter of the network if the sender does not know the length of the path to reach the receiver.

Prevent Flooding on a Network

When the router floods the network using the flooding method, it generates a large number of packets on the network. Therefore, the number of hop count on a network increases continuously and other routers may find packet as duplicate because they may have received that packet earlier.

• Routers can prevent flooding on the network by keeping track of packets already sent to the network. With this method, the router will not send the same packet over the network again.
• The router obtains quality on the network by adding a sequence number to each packet. When the router receives a packet from another router, it looks up the sequence number of the packet and checks whether it was received before. This method prevents flooding.
• Each router has a list of routers per source that describes which packets it receives. If the router finds an incoming packet in the list, it discards it and does not flood.

Flooding Advantages

In practice, flooding is not good for sending most packets. But still, it has some advantages over the network. The uses of flooding are given below.

• When a router uses flooding technology, flooding ensures that the packet sent by the router reaches every node of the network. In simple words, flooding is effective if the router wants to broadcast information.
• In wireless networks, messages are sent in the form of waves and transmitted by a single station. The message sent by a station is received to all other stations if they are in the same radio range. Flooding and some other algorithms make use of this feature.
• If a network has a large number of routers that are communicating, the flooding can still find a way to send packets to the destination.
• Flooding technology is easy to set up because the router only needs to know its neighbors. Flooding can be used as a building block for efficient algorithms that are more complex to set up.
• The main advantage of flooding is that it chooses the shortest path on a network because it chooses all possible paths simultaneously.
• Lastly, no algorithm exists on computer networks that can generate low latency if we ignore the overhead generated by the flooding process.