Routing algorithms

Routing Algorithms. Distance Vector routing Algorithm. link state routing algorithm. path vector routing algorithm

1. Routing Algorithms N.G.S.Parameswaran . Assistant Professor, Department of Computer Applications, V.H.N.S.N. College (Autonomous) Virudhunagar .

2. Routing The process of moving a packet of data from source to destination. Routing is usually performed by a dedicated device called a  Router. It is the key feature of Internet because it enables messages to pass from one computer to another and eventually reach the target machine

3. Classification of Routing Algorithms Adaptive Algorithms These are the algorithms which change their routing decisions whenever network topology or traffic load changes. The changes in routing decisions are reflected in the topology as well as 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.

4. Classification of Adaptive Algorithms (a) Isolated –  In this method each, node makes its routing decisions using the information it has without seeking information from other nodes. The sending nodes doesn’t have information about status of particular link. Disadvantage is that packet may be sent through a congested network which may result in delay. Examples: Hot potato routing, backward learning. (b) Centralized –  In this method, a centralized node has entire information about the network and makes all the routing decisions. Advantage of this is only one node is required to keep the information of entire network and disadvantage is that if central node goes down the entire network is done. (c) Distributed –  In this method, the node receives information from its neighbors and then takes the decision about routing the packets. Disadvantage is that the packet may be delayed if there is change in between interval in which it receives information and sends packet.

5. Non-Adaptive Algorithms These are the algorithms which do not change their routing decisions once they have been selected. This is also known as static routing as route to be taken is computed in advance and downloaded to routers when router is booted. (a) Flooding –  This adapts the technique in which every incoming packet is sent on every outgoing line except from which it arrived. One problem with this is that packets may go in loop and as a result of which a node may receive duplicate packets. These problems can be overcome with the help of sequence numbers, hop count and spanning tree. (b) Random walk –  In this method, packets are sent host by host or node by node to one of its neighbors randomly. This is highly robust method which is usually implemented by sending packets onto the link which is least queued.

6. Types of Routing Algorithms Distance Vector Link State Path Vector

7. Distance Vector Routing Algorithm Historically known as the old ARPANET routing algorithm (or known as Bellman-Ford algorithm). Each router maintains a Distance Vector table containing the distance between itself and ALL possible destination nodes. Distances based on a chosen metric, are computed using information from the neighbors’ distance vectors.

8. A router transmits its distance vector to each of its neighbors in a routing packet. Each router receives and saves the most recently received distance vector from each of its neighbors. A router recalculates its distance vector when: It receives a distance vector from a neighbor containing different information than before. It discovers that a link to a neighbor has gone down. Algorithm

9. The DV calculation is based on minimizing the cost to each destination. Dx (y) = Estimate of least cost from x to y C( x,v ) = Node x knows cost to each neighbor v Dx = [ Dx (y): y ∈ N ] = Node x maintains distance vector Node x also maintains its neighbors' distance vectors – For each neighbor v, x maintains Dv = [ Dv (y): y ∈ N ] From time-to-time, each node sends its own distance vector estimate to neighbors. When a node x receives new DV estimate from any neighbor v, it saves v’s distance vector and it updates its own DV using B-F equation: Dx (y) = min { C( x,v ) + Dv (y)} for each node y ∈ N

10. Advantages It is simpler to configure and maintain than link state routing. Disadvantages It is slower to converge than link state. It is at risk from the count-to-infinity problem. It creates more traffic than link state since a hop count change must be propagated to all routers and processed on each router. Hop count updates take place on a periodic basis, even if there are no changes in the network topology, so bandwidth-wasting broadcasts still occur. For larger networks, distance vector routing results in larger routing tables than link state since each router must know about all other routers. This can also lead to congestion on WAN links.

11. Link State Routing Algorithm Also known as Shortest path Routing algorithm. Information about the state of (Router interfaces) links is known as link-states This information includes: • The interface's IP address and subnet mask. • The type of network, such as Ethernet (broadcast) or Serial point-to-point link. • The cost of that link. • Any neighbor routers on that link.

12. It is a dynamic routing algorithm in which each router shares knowledge of its neighbors with every other router in the network. A router sends its information about its neighbors only to all the routers through flooding. Information sharing takes place only whenever there is a change. It makes use of  Dijkastra’s Algorithm  for making routing tables. Link State Routing Algorithm

13. Two Phases Reliable flooding » Tell all routers what you know about your local topology Path calculation ( Dijkstraʼs algorithm) » Each router computes best path over complete network

14. Path Vector Routing Path Vector Routing is a routing algorithm in unicast routing protocol of network layer, and it is useful for interdomain routing. The principle of path vector routing is similar to that of distance vector routing. It assumes that there is one node in each autonomous system that acts on behalf of the entire autonomous system is called Speaker node. The speaker node in an AS creates a routing cable and advertises to the speaker node in the neighbouring ASs. A speaker node advertises the path, not the metrics of the nodes, in its autonomous system or other autonomous systems.

15. It is the initial table for each speaker node in a system made four ASs. Here Node A1 is the speaker node for AS1, B1 for AS2, C1 for AS3 and D1 for AS4, Node A1 creates an initial table that shows A1 to A5 and these are located in AS1, it can be reached through it A speaker in an autonomous system shares its table with immediate neighbours. Here Node A1 share its table with nodes B1 and C1 , Node C1 share its table with nodes A1,B1 and D1 , Node B1 share its table with nodes A1 and C1 , Node D1 share its table with node C1

16. If router A1 receives a packet for nodes A3 , it knows that the path is in AS1. If it receives a packet for D1,it knows that the packet should go from AS1,to AS2 and then to AS3 ,then the routing table shows that path completely. If the node D1 in AS4 receives a packet for node A2,it knows it should go through AS4,AS3,and AS1. Working Principle

17. Functions of Path vector Routing PREVENTION OF LOOP POLICY ROUTING OPTIMUM PATH

18. Any Probes?

19. Thank You