In most of the situations, packets require multiple hops to make journey towards the destination. Routing is one of the most complex and crucial aspect of packet switched network design.
Desirable Properties of Routing Algorithms:-
- Correctness and Simplicity
- Robustness : Ability of the network to deliver packets via some route even in the face of failures.
- Stability : The algorithm should converge to equilibrium fast in the face of changing conditions in the network.
- Fairness and Optimality
- Efficiency : Minimum overhead.
Design Parameters of Routing Algorithms :
- Performance Criteria : Number of hops, Cost(Send packet with high bandwidth path as cost is less) , Delay(Size of Queue) , Throughput time(Number of packets delivered/time).
- Decision Time : When to decide to route a packet? Per-Packet(Datagram) or Per-session(Virtual-Circuit).
- Decision Place : Who will decide about routing? Each Node(distributed), Central Node (centralized),Originated Node (source) .
- Network Information Source: None , Local, Adjacent node, Nodes along route , All nodes.
- Network Information Update Time : Continuous, Periodic, Major Load Change , Topology Change.
Routing Strategies :
- Fixed Routing
- Dynamic Routing
- Random Routing
- Flow-based Routing
Fixed Routing –
- A route is selected for each source and destination pair of node in the network.
- The route are fixed ; changes only if topology of the network changes.
Fixed Routing : Example (1)
- A Central routing matrix is created based on the least-cost path which is stored in the network control center
- The matrix, shows for each source-destination of the route , the identity of the next node on the route.
- Drawback: If the network control center fails, then everything will collapse. Hence it is not reliable.
Fixed Routing : Example (2)
- Routing Table is created for each node. This is called as distributed routing algorithm
- Routing table can be created using least-min path or min-hop reach method. Two famous path algorithms
- Dijkstra Algorithm
- Bellman Ford Algorithm
- Works well in reliable network with stable load in reliable network
- Same for virtual circuit and datagram
- Lack of flexibility
- Doesn’t react to failure or network congestion
- 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.
- For Example in above figure
- A incoming packet to (1) is sent out to (2),(3)
- from (2) is sent to (6),(4) and from (3) it is sent to (4),(5)
- from (4) it is sent to (6),(5),(3) , from (6) it is sent to (2),(4),(5),from (5) it is sent to (4),(3)
- All possible routes between Source and Destination is tried. A packet will always get through if path exists
- As all routes are tried, the will be atleast one route which is the shortes
- All nodes directly or indirectly connected are visited
- Flooding generates vast number of duplicate pakects
- 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 intializes 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.
Selective Flooding : Routers do not send every incoming packet out on every line , only on those lines that go in approximately in the direction of destination.
Advantages of Flooding :
- Highly Robust, emergency or immediate messages can be sent (eg military applications)
- Set up route in virtual circuit
- Flooding always chooses the shortest path
- Broadcast messages to all the nodes
Data and Computer Communications
Read next article – Routing Protocols Set 1 (Distance Vector Routing)