Routing Algorithms
We Already Learnt About Routers. In This Topic, We Will Know How The Data Transmission Between Routers Takes Place And How Routing Algorithms Helps In Transmitting Data Packets From One Router To Another Router.
A Router Consists On Two Process Inside It.
One Process Forwards The Incoming Data Packets To Other Routers Through A Route And Second Process Is Filling And Updating The Information Of The Other Routers In A Table, A Table In A Router Consists Of Information About Other Adjacent Routers Or All The Routers In The Network.
For The Second Process, For Filling And For Updating The Information Of The Adjacent Routers Or Others Routers In The Network Routing Algorithms Are Required.
Routing Algorithms - Routing Is A Process Of Establishing The Routes That Data Packets Must Follow To Reach The Destination. In This Routing Process, A Table Is Created In The Router Which Contains Information Regarding Routes Which Data Packets Must Follow. Various Routing Algorithms Are Used For The Purpose Of Deciding Which Route An Incoming Data Packet Need To Be Transmitted On To Reach Destination Efficiently. Routing Algorithms Have Certain Desirable Properties. Correctness - The Data Packets Came To The Router Should Be Sent To The Correct Destination(Other Router). Simplicity - The Routing Algorithm Should Be Simple. Robustness - The Routing Algorithm Should Be Robust(Strong And Healthy). Stability - Routing Algorithm Should Be Stable. Fairness - Routing Algorithm Should Be Fair, In Accordance To The Rules And Standards. Efficiency - The State Or Quality Of Being Efficient.
Adaptive Routing Algorithm And Non- Adaptive Routing Algorithm Are The Two Types Of Routing Algorithms.
Adaptive Routing Algorithm Or Dynamic Routing Algorithm
Is The Algorithm Which Change Their Routing Decisions Whenever Traffic Load Or Network Topology Changes. The Changes In The Routing Decisions Are Reflected In The Traffic As Well As In The Topology Of The Network. Adaptive Routing Algorithm Are Also Know As Dynamic Routing Algorithms Because These Make Use Of Dynamic Information Such As Load, Delay, Current Topology, Etc To Select Routes. These Get Their Routing Information From Adjacent Routers Or From All Other Routers In The Network. Optimisation Parameters Are Distance, Number Of Hops And Estimated Transit Time. This Can Be Furthur Classified As Follows : (i) Centralized In This Type, Some Central Node(Router) Gets Entire Information About (a) Network Topology (b) Traffic (c) Other Nodes (Routers) Then This Transmits This Information To The Respective Routers. Advantage : Only One Node(Router) Is Required To Keep The Information. Disadvantage : If The Central Node(Router) Goes Down, The Entire Network Is Down, I.e Single Point Of Failure. (ii) Isolated In This Method, Node(Router) Decides The Routing Without Seeking Information From Other Nodes. The Sending Node(Router) Does Not Know About The Status Of A Particular Link. Disadvantage : Data Packet May Be Send Through A Congested Route Resulting In A Delay. (iii) Distributed In This, The Node (Router) Receives Information From Its Neighbouring Nodes(Routers) And Then Takes The Decision About Which Way To Send The Packet. Disadvantage: If In Between The Interval It Receives Information And Sends The Packet Something Changes Then The Data Packet May Be Delayed.
Non- Adaptive Routing Algorithm Or Static Routing Algorithm
Is The Algorithm Routing Decisions Will Not Change Whenever The Traffic Load Or Network Topology Changes. Non-Adaptive Routing Algorithm Is Also Known As Static Routing Algorithm. For Example In The Below Picture If A Computer Sends Data Packet to Router 1, The Data Packet Will Be Sent To Other Router 2 And Router 3 As Shown In The Below Picture Even If The Router B Is Deleted From The Network, Which Means In Router 1, The Table Which Consists Of The Information About Routers 2, 3 Is Not Updated After Deletion.
This Can Be Furthur Classified As Follows :
(i) Flooding
It Adapts The Technique In Which Every Incoming Packet Is Sent On Every Outgoing Line Except The One On Which It Arrived. One Problem With This Method Is That, Data Packets May Go In A Loop. As A Result Of This, A Node(Router) May Receive Several Copies Of A Particular Data Packet Which Is Undesirable. Following Techniques Adapted To Overcome These Problems : (a) Sequence Numbers: Every Packet Is Given A Sequence Number. When A Node(Router) Receives The Packet, It Sees Its Source Address And Sequence Number. If Node (Router) Finds That It Has Sent The Same Packet Earlier, Then It Will Not Transmit The Packet And Will Just Discard It. (b) Hop Count: Every Data Packet Has A Hop Count Associated With It. This Is Decremented(Or incremented) By One By Each Node(Router) Which Sees It. When Hop Count Becomes Zero(or a Maximum Possible Value) The Data Packet Is Dropped. (c) Spanning Tree: The Packet Is Sent Only On Those Links That Lead To The Destination By Constructing A Spanning Tree Touted At The Source. This Avoids Loops In Transmission But Is Possible Only When All The Intermediate Nodes(Router) Have Knowledge Of The Network Topology. Flooding Is Not Practical For General Types Of Applications. But In Cases Where High Degree Of Robustness Is Desired Such As In Military Applications, Flooding Is Of Great Help.
(ii) Random Walk
In This Method, A Packet Is Sent By The Node(Router) To One Of Its Neighbours(Router) Randomly. This Algorithm Is Highly Robust. When The Network Is Highly Interconnected, This Non-Adoptive Routing Algorithm Has The Property Of Making Excellent Use Of Alternative Routes. It Is Usually Implemented By Sending The Packet Onto The Least Queued Link. Read the full article