Network Layer – Need of Routing and IP Fragmentation (Bellman Ford and Dijkstra Algorithm)

Spoiler : this post is long yet interesting !!

In the previous post we have seen the basic overview of the network layer and some of its basic functions. Now we must dig deep inside the two most important work which is indeed required for the correct delivery of packet data (delivery of data packet to correct destination is basic work done by this layer).

Routing is a process of giving/assigning required route to an incoming data packet. Let us understand the complete complex process step by step.

What is Forwarding of data packet ?

Forwarding basically means to place a packet in its route to its destination. This requires a host or a router to have a routing table. Forwarding is defined as the process of placing the packet in its route towards its destination. Forwarding is possible only if the host or a router has a routing table of their own. 

A sender host or a router will refer to this routing table when it receives a packet and from the table, they will find the root to the final destination. This process is complex as today in the internetwork environment, a large number of entries required to be made in a routing table.

Types of the forwarding process

Next hop method versus Route method

This Route method is the most basic method in which the information about the complete route is stored in the routing tables of hosts and routers. The routing table holds only the address of the next-hop instead of the information about the complete route .

This makes the routing tables extremely large and difficult to manage. In order to reduce the size of routing tables, the next hop method is used in which the routing table contains only the address of the next hop (upto the next router) instead of information about the complete route.

Network specific method versus Host specific method

Another technique to reduce the routing table and simplify the searching process is called the network-specific method. In the host-specific method, the routing table of a host or router will specify each destination host connected to the same physical network.

This increases the number of entries in a routing table and makes it large. But in the network-specific method, we have only one entry corresponding to the destination network .

Default method

Another method to simplify routing is called the default method. In the routing table instead of listing all networks in the entire Internet, a host will have only one entry called the default entry (normally defined as network address 0.0.0.0). This is one more method of simplifying the routing tables.

To decrease the size of the routing table further, we need to extend the routing to include geographical routing. We must divide the entire address space into a few large blocks.

Routing Element

Let us first understand the basic element used in this layer.  Every one of us (mostly) might have used a router at our home or workplace. 

Routers are simply devices that connect two or more networks and consist of both hardware and software.Various types of networks can be interconnected through routers. The software in any router is the operating system and the routing protocol. 

Routers use logical and physical addressing to connect two or more logically separate networks. The large network is organized into small network segments called as subnets and these subnets are interconnected via routers. Each of the subnets is given a logical address.

This allows any network to be separate but still access each other and exchange data. Data are grouped in the form of packets, or blocks of data. Each packet has a physical device address as well as a logical network address.

Routing Tables

The routing table for a host or a router consists of an entry for each destination, or a combination of destinations to route the IP packets. Routing tables can be of two types:

• Static routing tables
• Dynamic routing tables

1. Static routing tables

Static routing table can be used in a small internet that doesn’t change very often, or in an experimental internet i.e.  for troubleshooting. The information in the static routing tables is entered manually. The route of a packet to each destination is entered into the table by the administrator . 

This routing table can not update itself automatically. It has to be changed manually as and when required. Static routing table is useful only for small networks.

2. Dynamic routing tables

The routers in the big internet such as the Internet need to be updated dynamically for efficient delivery of the IP packets.The dynamic routing tables can get automatically updated by using a dynamic routing protocol such as RIP, OSPF etc (all explained in later posts).

Unicast Routing 

In unicast routing, there is a one to one relation between the source and the destination. That means only one source sends packets to only one destination. The type of source and destination addresses included in the IP datagram are unicast addresses assigned to the hosts. 

In unicast routing when a router receives a packet, it forwards that packet through only one of its ports which corresponds to the optimum path. The router can discard the packet if it can not find the destination address.

A routing protocol is indeed a combination of rules and procedures that lets routers in the internet inform each other of changes. It basically allows the routers to share whatever they know about the internet or their neighborhood.

Broadcast Routing

In a broadcast communication, the relationship between the source and the destination is one-to-all. In this, the host has to send the packets to many or all other hosts. If the sender sends a packet to all destinations simultaneously then it is called as broadcasting. There are mainly three types in this :

       1. Simple Broadcasting 

In this method the source will simply send a distinct (a separate) packet to each destination. A lot of bandwidth will be lost and the source has to have a complete list of all destinations.

        2. Flooding

Flooding is another method used for broadcasting. The problem with flooding is that it has a point to point routing algorithm. So it consumes a lot of bandwidth and generates too many packets.

         3. Multidestination routing

In this algorithm each packet will contain a list of destinations or a bit map that indicates the desired destination. When such a packet arrives at a router, the router first checks all the destinations.

Then it decides the set of output lines that will be required based on the destination addresses. This will save bandwidth to a great extent. Also generation of too many packets right from the sending end will also be avoided.

Multicast Routing

In multicasting , a message from a sender is to be sent to a group of destinations but not all the destinations in a network. The relationship is one-to-many. A process has to send a message to all other processes in the group. For a small group, it is possible to send a point to point message. 

But this is expensive if the group is large. So we have to send messages to a well-defined groups which are small compared to the network size. Sending a message to such a group is called multicasting and the routing algorithm used for multicasting is multicast routing .

Types of Routing Algorithms

Routing algorithms can be divided into two groups :

• Non·adaptive (static) algorithms : For this type of algorithms, the routing decision is not based on the measurement or estimation of current traffic and topology
• Adaptive (dynamic) algorithms : For these algorithms the routing decision can be changed dynamically if there are any changes in topology or traffic etc.

Shortest Path Routing:

This algorithm is based on the simplest and most widely used principle. Here a graph of subnet is prepared in which each node represents either a host or a router and each arc represents a communication link. So as to choose a path between any two routers, this algorithm simply finds the shortest path between them. 

How to decide the shortest path ?

One way of measuring the path length is the number of hops. Another way (metric) is the geographical distance in kilometers. Some other metrics can also be used for this purpose like queuing and transmission delay and obtain the shortest path as the fastest path.

There are many algorithms for computing the shortest path between two nodes. One of them is Dijkstra algorithm. The other one is Bellman Ford algorithm.

Dijkstra’s Algorithm:

Dijkstra’ s algorithm is used for computing the shortest path from the root node to every other node in the network. The Dijkstra algorithm simply creates a shortest path tree from a graph. This algorithm divides the nodes into two sets i.e. tentative and permanent.

It first finds the neighbors of a current node, makes them tentative, examines them, and if they pass the criteria, then makes them permanent.

The root node is defined as the node corresponding to the router where the algorithm is being run.The total number of nodes are divided into two groups namely the P (permanent) group and T(temporary) group. In the P group we have those nodes for which the shortest path has already been found. In T group the remaining nodes are placed.

The path to every node in the T group should be computed from a node which is already present in group P. We should find out every possible way to reach an outside node by a one hop path from a node which is already present in P and choose the shortest of these paths as the path to the desired node . 

Distance Vector Routing Algorithm (Distributed Bellman-Ford routing algorithm)

The table at each node guides the packets to the desired node by showing the next stop in the route (next-hop routing). We can simply think of nodes as the cities in an area and the lines as the roads connecting them. A table can show a tourist the minimum distance between cities.

In this algorithm, each router maintains a table called vector, such a table gives the best-known distance to each destination and the information about which line to be used to reach there. In distance vector routing method, each router maintains a routing table. It contains one entry for each router in the subnet. This entry has two parts :

• The first part shows the preferred outgoing line to be used to reach the specific destination and
• Second part gives an estimate of the time or distance to that destination.

In distance vector routing, we assume that each router knows the identity of every other router in the network, but the shortest part to each router is not known.

A router periodically sends a copy of its distance vector to all its neighbours.  When a router receives a distance vector from its neighbour. it tries to find out whether its cost to reach any destination would decrease if it routed packets to that destination through that particular neighbouring router.

Concept of Internetworking

A network of computer networks is known as Internetwork or simply an Internet . The best example of an internetwork is Internet.The difference between Networking and Internetworking may be stated as follows : In networking all the devices (hosts) involved are compatible with each other.

But in internetworking this may not be true. The networks that are being connected to each other through internetworking may or may not be compatible with each other, in many respects. 

Despite all the problems present with the internetworking computer scientists and engineers have found a mechanism in order to connect computer networks together. 

The two important incompatibility issues which need to be sorted out are as follows: 

• Hardware issues and
• Software issues

We have to add some hardware for physically connecting computer networks which are for away to each other. A router has its own CPU and memory.

It has multiple input/output interfaces that allow connections to many computer networks. The routers on the software level must agree with the manner in which information from the source computer be transmitted to the destination computer. 

All routers must confirm to a pre-specified standard for the same , hence a standard packet format is decided. The sender breaks down its original message into this standard packet format . Therefore we need some protocols for standardizing the communication between incompatible networks. 

What is IP Fragmentation in Network Layer

The network designers are not free to choose any size of the packet data. The maximum packet size varies network to network and the factors which decide the maximum packet size are as follows:

• Width of the TDM transmission slot.
• Protocols used
• Type of operating system.
• International standards.
• Efforts to reduce re transmission. 
• Desire to prevent one packet from occupying the current channel too long

All these factors put a limit on the maximum packet size. The maximum payload size ranges from 48 bytes for an ATM cell to 65,515 bytes for an IP packet. When a large packet wants to travel over a network whose maximum packet size is very small, we face a problem. 

The solution to this problem is to avoid this situation in the first place by using a routing algorithm that will avoid sending packets through the networks that cannot handle them. But this solution cannot be exercised every time. The real solution to this problem is Fragmentation . 

In this technique, the gateways break up large packets into smaller ones called as fragments. Then each fragment is sent as a separate internet packet. 

Method 1 of Fragmentation (transparent strategy)

In this strategy. the fragmentation caused by a “small packet” network is made transparent to any subsequent network through which the packets will pass. When a large packet arrives at a gateway,it breaks the packet into fragments. 

Each fragment is then addressed to the same exit gateway. The exit gateway (G2) recombines all these fragments. In this way, the small packet network has been made transparent i.e. the rest of the network cant see what happened. 

The subsequent networks are not even aware that fragmentation has taken place. The problem with transparent fragmentation is that the exit gateway has to know that it has received all the pieces. For this, a count field or an end of packet bit has to be included in each packet. 

Method 2 of Fragmentation (non transparent strategy)

In this strategy, the fragmented packets are not reassembled at any intermediate stage. That means the exit gateways will not reassemble the fragments. Instead, each fragment is treated as a separate original packet.

All these packets are passed through the exit gateway or gateways and their recombination is carried out at the destination host. Every host must be capable of reassembling the fragments. The total overhead increases due to fragmentation since each fragment has to have a header. 

The advantage of a non-transparent strategy is that now we can use multiple exit gateways and improve network performance.

Stay tuned for all the routing protocols in the subsequent posts.