Intra-domain RoutingOverviewRouting Protocol IssuesDistance Vector (Bellman-Ford,RIP)ExampleRouting LoopsLoop-Breaking HeuristicsLink State (Dijkstra’s algorithm,OSPF)Link State (cont)CS 640 1Intra-domain RoutingOutlineIntroduction to RoutingDistance Vector AlgorithmCS 640 2Overview•Forwarding vs Routing–forwarding: to select an output port based on destination address and routing table–routing: process by which routing table is built•Network as a Graph–Assume single admin. authority–Assume nodes are routers–Assume links have cost•Problem: Find lowest cost path (sum of links) between two nodes43621911DAFEBCCS 640 3Routing Protocol Issues•It may be simple to calculate least cost path if graph is static but…•Links and routers go down•Links and routers are added•Traffic can cause links to overload•How are costs calculated?•Algorithm must be distributed in order to scale•Rich area for research due to distributed, dynamic nature of the problem•Different routers can have different routes at same timeCS 640 4Distance Vector (Bellman-Ford,RIP)•Find SP for node such that paths contain at most 1 hop, then 2…•Each node maintains a set of triples –(Destination, Cost, NextHop)–Assume each node knows cost of directly connected neighbors•Exchange updates directly connected neighbors–periodically ( on the order of several seconds) – even if there are no changes–whenever its table changes (called triggered update)•Each update is a list of pairs:–(Destination, Cost)•Update local table if receive a “better” route–smaller cost–came from next-hop•Refresh existing routes; delete if they time outCS 640 5ExampleDestination Cost NextHop B 1 B C 3 D D 1 D E 2 D F 4 D G 1 GDGABCEF5111213521CS 640 6Routing Loops•Example 1–E detects that link to C has failed–E sets distance to C to infinity and sends update to D–D sets distance to C to infinity since it uses D to reach E–D receives periodic update from B with 2-hop path to C–D sets distance to C to 5 and sends update to E–E decides it can reach C in 3 hops via B•Example 2–link from A to G fails–A advertises distance of infinity to G–B and D advertise a distance of 2 to G–B decides it can reach G in 3 hops; advertises this to A–A decides it can read G in 4 hops; advertises this to D–D decides that it can reach G in 5 hops…CS 640 7Loop-Breaking Heuristics•Set infinity to 16–Assume this is maximum number of hops in network•Split horizon–Don’t send routes learned from a neighbor back to a neighbor•Split horizon with poison reverse–Send route back to neighbor with negative information ie. Infinite•What are the problems?CS 640 8Link State (Dijkstra’s algorithm,OSPF)•Find SP from a given node by sending path data to all nodes and developing paths in order of increasing length•Strategy–send to all nodes (not just neighbors) information about directly connected links (not entire routing table)•Link State Packet (LSP)–id of the node that created the LSP–cost of the link to each directly connected neighbor–sequence number (SEQNO)–time-to-live (TTL) for this packetCS 640 9Link State (cont)•Reliable flooding–store most recent LSP from each node–forward LSP to all nodes but one that sent it–generate new LSP periodically•increment SEQNO–start SEQNO at 0 when reboot–decrement TTL of each stored LSP•discard when TTL=0–This is not
View Full Document
Unlocking...