routing in computer networks for btech.pptx

routing

1. Routing 1

2. Network Layer Design Issues Store-and-Forward Packet Switching Services Provided to the Transport Layer Implementation of Connectionless Service Implementation of Connection-Oriented Service 2

3. Store-and-Forward Packet Switching 3

4. Network Layer Services Connection Oriented :- ATM Connectionless Service :- Internet 4

5. Implementation of Connectionless Service Packets are injected into the subnet individually and routed independently to each other. Packets are called DATAGRAMS. 5

6. 6

7. Implementation of Connection-Oriented Service A path from Source Router to destination router must be established before any data packets can be sent. This connection is called VIRTUAL CIRCUIT . 7

8. 8

9. Routing Algorithms The routing algorithm is that part of the network layer software responsible for deciding which output line an input packet should be transmitted on. In datagram approach decision has to be made for every arriving data packet. In virtual Circuit decision has to be made only when a new virtual circuit is established. 9

10. Properties of Routing Algorithm Correctness Simplicity Robustness :- Should be able to cope with changes in topology and traffic. Fairness and Optimality 10

11. Conflict between fairness and optimality 11

12. Types of Routing Algorithms Non Adaptive (Static Routing) :- Choice of route to use to get from I to J is computed in advance. Adaptive Algorithms :- Change the routing decisions to reflect changes in topology and traffic as well. Three important factors are From where to get information When to change the route What matrix is to be used (Distance, Number of hops etc) 12

13. Optimality Principle It states that if router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same route. Set of optimal routes from all sources to a given destination form a tree routed at destination called sink tree. 13

14. Optimality Principle 14 (a) A subnet. (b) A sink tree for router B.

15. Shortest Path Routing Build a graph of the subnet, with each node representing a router and each arc representing a communication line. The algorithm just finds the shortest path between them on the graph. Metrics used for measuring the length can be No of hops Geographical distance Transmission delay Combination in general 15

16. Shortest Path Routing ( Dijkstra ) Each node is labeled with its distance from the source node. Initially all nodes are labeled with infinity. As the algorithm proceeds and paths are found, the labels may change reflecting better paths. 16

17. 17 The first 5 steps used in computing the shortest path from A to D. The arrows indicate the working node.

18. Flooding Every incoming packet is sent out on every outgoing line except the one it arrived on. Flooding can generate duplicate packets. Use Hope Count Keep Track of packets that have been flooded :- Source router put a sequence number in each packet it receives from its hosts. Each router than needs a list per source router telling which sequence numbers originating at that source have already been seen. 18

19. Flooding Flooding is useful in Distributed database applications. In wireless networks As metric against which other routing algorithms can be compared. 19

20. Distance Vector Routing Each router maintain a table giving the best known distance to each destination and which line to use to get there. These tables are updated by exchanging information with the neighbors. The entry in table contains two parts: Preferred outgoing line Estimate of time or distance to that destination 20

21. Distance Vector Routing The router is assumed to know distance to each of its neighbors. If metric is hope the distance is just one hope. If the metric is delay, the router can measure it directly with special ECHO packet that receiver just timestamps and sends back as fast as it can. 21

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

23. 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. 23

24. Learning about the Neighbors This goal is accomplished by sending a special HELLO packet on each point-to-point line. The router on the other side is expected to send back a reply telling who it is. 24

25. Measuring Line Cost To estimate the delay to each of its neighbors a special ECHO packet is to be sent that the other side is required to send back immediately. 25

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

27. Distributing the Link State Packets As the packets are distributed and installed, the routers getting the first ones will change their routes. Fundamental idea is to use flooding to distribute the link state packets. Sequence number and age of packet is also added in the table. 27

28. 28

29. Computing new Routes Once a router has accumulated a full set of link state packets, it can construct the entire subnet graph. Now Dijkstra algorithm can be run locally to construct the shortest path to all possible destinations. 29

30. Hierarchical Routing As network grow in size, the router routing tables grow proportionally. Not only is router memory consumed by ever increasing tables, but more CPU time is needed to scan them. When hierarchical routing is used, the routers are divided into regions. 30

31. 31

32. Broadcast Routing Sending a packet to all destinations simultaneously is called broadcasting. Flooding can be used for this purpose but problem is that it generates too many packets and consumes too much bandwidth. Another Method is Multidestination Routing. Each packet contains a list of destinations. When a packet arrives at a router, the router checks all the destinations to determine the set of all output lines that will be needed. 32

33. Use of Sink Tree or Spanning Tree A spanning tree is the subset of the subnet that includes all the routers but contains no loops. 33 Reverse path forwarding. (a) A subnet. (b) a Sink tree. (c) The tree built by reverse path forwarding.

34. Reverse path forwarding When a broadcast packet arrives at a router, the router checks to see if the packet arrived on the line that is normally used for sending packets to the source of broadcast. The principle advantage is that it is both reasonably efficient and easy to implement. It does not require routers to know about spanning trees nor does it have the overhead of a destination list or bit map. 34

35. Multicast Routing Sending a message to a group is called multicasting. Routers learn about which of their hosts are in which group. Either hosts must inform their routers about their membership or routers must query their hosts periodically. To do multicasting, each router computes a spanning tree covering all other routers. When a process sends a multicast packet to a group, the first router examines its spanning tree and prunes it, removing all lines that do not lead to hosts that are members of the group. 35

36. 36 (a) A network. (b) A spanning tree for the leftmost router. (c) A multicast tree for group 1. (d) A multicast tree for group 2.