Routing

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

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, load condition, cost of diff. paths

• Every incoming packet to a node is sent out on every outgoing like except the one it arrived on.

• 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 which is the shortest

• All nodes directly or indirectly connected are visited

• Flooding generates a vast number of duplicate packets

• Suitable damping mechanism must be used

• A hop counter may be contained in the packet header which is decremented at each hop. 
  with the packet being discarded when the counter becomes zero

• The sender initializes the hop counter. If no estimate is known, it is set to the full diameter of the subnet.

• Keep track of the packets which are responsible for flooding using a sequence number. Avoid sending them out a second time.

• Highly Robust, emergency or immediate messages can be sent (eg military applications)

• Set up the route in virtual circuit

• Flooding always chooses the shortest path

• Broadcast messages to all the nodes

Adaptive Algorithms

These are the algorithms that change their routing decisions whenever network topology or traffic load changes. The changes in routing decisions are reflected in the topology as well as the traffic of the network. Also known as dynamic routing, these 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

These are the algorithms that do not change their routing decisions once they have been selected. This is also known as static routing as a route to be taken is computed in advance and downloaded to routers when a router is booted. 

Routing tables algorithms may be

• Flooded

• Random Walk