routing alg.pptx

Network Layer Routing Algorithm

1. Network Layer

2. Shortest Path Algorithm Distance Vector Routing - Count to Infinite Problem Link State Routing Hierarchical Routing

3. Shortest Path Algorithm The first 5 steps used in computing the shortest path from A to D. The arrows indicate the working node.

4. Shortest path is the fastest path rather than the path with fewest edges or kilometers Initially no path is known so all nodes are labeled with infinity Labels on the edges could be computed as a function of the distance ,bandwidth, average traffic ,communication cost ,measured delay and other factors

5. Initially, no path is known – All nodes are labeled with infinity. 2. As the algorithm progresses labels are changed reflecting the better path. The label is called as  tentative label . 3. As it is found that the label represents the shortest path then it is made  permanent  and never changed thereafter.

6. Distance Vector Routing (a) A subnet. (b) Input from A, I, H, K, and the new routing table for J.

7. Distance Vector routing is called Routing information Protocol(RIP) A Route with the less number of hops is considered as the best route Every Router advertises its best route to the other routers Convergence : setting of routers to the best paths across the network It reacts rapidly to good news & converge slowly to bad news .

8. Possible route from J to B JA+AB=8+12 =20 JI+IB=10+36 = 46 JH+HB=12+31=43 JK+KB = 6+28 =34 Min =20 when taken ‘A’ Route , So 20 is updated in J new table

9. Find the route from J to C JA+AC =8+25=33 JI+IC=10+18=28 JH+HC=12+19=31 JK+KC=6+36=42 Shortes t distance is 28 when C Route taken

10. Find the Route from J to D JA+AD =8+40=48 JI+ID=10+27=37 JH+HD=12+8=20 JK+KD=6+24=30 Shortest distance is 20 through H route

11. Find the Route from J to E JA+AE =8+14=22 JI+IE=10+7=17 JH+HE=12+30=42 JK+KE=6+22=28 17 is the shortest distance from the I route

12. Find the Route from J to F JA+AF=8+23=31 JI+IF=10+20=30 JK+KF=6+40 JH+HF=12+19=13 30 is the shortest distance through I Route

13. Find the Route from J to G JA+AG=8+18=26 JH+HG=12+6=18 JK+KG=6+31=37 JI+IG=10+31=41 18 is the shortest distance through H Route

14. Find the Route from J to I JA+AI=8+21=29 JH+HI=12+14=26 JK+KI=6+22=28 JI+IJ=10+0=10 10 is the shortest distance from I Route

15. Find the Route from J TO K JA+AK=8+24=32 JH+HK=12+22=34 JK+KK=6+0=6 JI+IK=10+22=34 6 is the shortest distance from the K Route

16. Find the route from J To L JA+AL=8+29=37 JH+HL=12+9=21 JK+KL=6+9=15 JI+IL=10+33=43 15 is the shortest distance from K Route

17. 3 Distance Vector Routing (2) The count-to-infinity problem.

18. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D Initialization

19. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 10 1 10 2 2 2 2 2 2 1 Direct Neighbours

20. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 10 1 10 2 2 2 2 2 2 1 3 3 11 3 3 11 Neighbours of neighbours

21. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 10 1 10 2 2 2 2 2 2 1 3 3 11 3 3 11 13 13 13 13 Neighbours of neighbours of neighbours

22. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 10 1 10 2 2 2 2 2 2 1 3 3 11 3 3 11 13 13 13 13 Stable convergence

23. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 10 1 10 2 2 2 2 2 2 1 3 3 11 3 3 11 13 13 13 13 1 Good news: A new link!

24. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 10 1 10 2 2 2 2 2 2 1 3 3 11 3 3 11 1 13 1 13 1 Direct endpoints know

25. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 10 1 4 2 2 2 2 2 2 1 3 3 3 3 3 3 1 3 1 3 1 Neighbours know

26. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 4 1 4 2 2 2 2 2 2 1 3 3 3 3 3 3 1 3 1 3 1 Neighbours of neighbours know

27. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 4 1 4 2 2 2 2 2 2 1 3 3 3 3 3 3 1 3 1 3 1 A happy and stable network

28. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 4 1 4 2 2 2 2 2 2 1 3 3 3 3 3 3 1 3 1 3 Bad news: Link crash!!

29. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 4 1 2 2 2 2 2 2 1 3 3 3 3 3 3 Direct endpoints know

30. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 4 1 2 2 2 2 2 2 1 3 3 3 3 3 3 10

31. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 4 1 2 2 2 2 2 2 1 3 3 3 3 3 3 10 5 13 11 13 Get help from neighbours

32. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 4 1 2 2 2 2 2 2 1 3 3 3 3 7 7 10 5 13 11 13 Routing loop (due to inconsistent state info)

33. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 8 1 2 2 2 2 2 2 1 3 3 3 3 7 7 10 9 13 11 13

34. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 8 1 2 2 2 2 2 2 1 3 3 3 3 11 11 10 9 13 11 13 Counting to infinity…

35. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 10 1 2 2 2 2 2 2 1 3 3 3 3 11 11 10 13 13 11 13

36. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 10 1 2 2 2 2 2 2 1 3 3 3 3 11 13 10 13 13 11 13

37. 1 10 2 2 2 A B C E D A C E B D A C E B D A C E B D A C E B D A C E B D 10 1 2 2 2 2 2 2 1 3 3 3 3 11 13 10 13 13 11 13 Stability again

38. Link State Routing Each router must do the following: Discover its neighbors, learn their network address. Measure the delay or cost to each of its neighbors. Construct a packet telling all it has just learned. Send this packet to all other routers. Compute the shortest path to every other router.

39. Link State Routing : Learning about the Neighbors Nine routers and a LAN. A graph model of (a).

40. States of lines of all the routers in a network is considered to build a common graph of the entire network . New artificial node ‘N’ to which A,C & F are connected. Possibility of visiting A to C on the LAN is represented by ANC

41. Link State Routing (3): Measuring Line Cost A subnet in which the East and West parts are connected by two lines.

42. Setting a Link Cost

43. Delay = Round trip time of ECHO Packet / 2 Sending router get a reasonable estimate of the delay by measuring round trip time & dividing it by two

44. Link State Routing : Building Link State Packets (a) A subnet. (b) The link state packets for this subnet.

45. Link State Routing : Distributing the Link State Packets

46. The Packet buffer for router B Packet from A arrives directly . So it must be sent to C & F and Acknowledgement to A , as indicated by the Flag bits E is different ,It arrives twice one via EAB and Vis EFB . IT must be sent only to C and it must be acknowledged to both A & F

47. Duplicate arrives scenario If a copy of C’s state arrives from F before the fourth entry in the table has been forwarded. The sixth bit will be changed to 100011 to indicate packet must be Acknowledged to F but not sent there

48. Hierarchical Routing Hierarchical routing.

49. The routers are divided into regions . Each router has complete details about how to route packets to destination with in its own region. But it does not have any idea about the internal structure of other regions