Routing

Routing is the process of establishing the routes that data packets must follow to reach their destination. In this process, a routing table is created which contains information regarding routes that data packets follow. Various routing algorithms are used for the purpose of deciding which route an incoming data packet needs to be transmitted on to reach the destination efficiently.

The challenge is transferring data from one node in one network to another node in a different network

Routers

Routers examine the destination IP address of a received packet and make routing decisions accordingly. To determine which interface the packet will be sent to, routers use routing tables. A routing table lists all the networks for which routes are known. Each router’s routing table is unique and stored in the RAM of the device.

Routing Table

A routing table is a set of rules, often viewed in a table format, that is used to determine where data packets traveling over an Internet Protocol (IP) network will be directed.

All IP-enabled devices, including routers and switches, use routing tables.

The routing table contains the information needed to forward a packet along the best path toward its destination. Each packet contains information about its origin and destination. The Routing Table provides the device with instructions for sending the packet to the next hop on its route across the network.

Routing table entries are

Entry	Purpose

Entry	Purpose
Network ID	The next ID/destination on the route
Subnet Mask	The subnet mask that is used to match the destination IP address to the Network ID
Next Hop	The IP address to where the packet is forwarded
Outgoing Interface (ethernet card)	The outgoing ethernet card from which the packet should leave this router
Metric	Typically used to say maximum number of allowed hops

Routing Table Example

Routing Algorithms

Routers use algorithms to determine how routing tables are populated and used. These can be

Fixed
Flooding
Adaptive
Non-adaptive

Fixed Algorithms

For each node in the network, the route is predefined in the routing tables. Changes to the route can only be achieved by changing the topology and the routing tables.

The topology must be known in order to build the routing tables.

Simple
Works well in reliable network with stable load in a reliable network
Lack of flexibility
Doesn’t react to failure or network congestion

Flooding Algorithms

Requires no network information like topology
Every incoming packet to a node is sent out on every outgoing

All possible routes between Source and Destination are tried. A packet will always get through if the path exists
As all routes are tried, there will be at least one route that is the shortest
All nodes directly or indirectly connected are visited
Flooding generates a vast number of duplicate packets
A suitable dampening mechanism must be used to ensure the network is not overwhelmed
A hop counter may be contained in the packet header which is decremented at each hop, the packet is discarded when the counter becomes zero
Are highly robust, emergency or immediate messages can be sent (eg military applications)
Flooding always chooses the shortest path
Broadcast messages to all the nodes

Adaptive Algorithms (dynamic routing)

These algorithms change their routing decisions whenever network topology or traffic load changes. These algorithms make use of dynamic information such as current topology, load, delay, etc. to select routes. Optimization parameters are distance, number of hops, and estimated transit time.

Routing tables algorithms may be

Isolated
Centralized
Distributed

Non-Adaptive Algorithms (status routing)

These algorithms do not change their routing decisions once they have been selected. The route to be taken is computed in advance and downloaded to routers when a router is booted.