Internet Routing Internet organized as a two level hierarchy First level autonomous systems AS s EE 122 Intra domain routing AS region of network under a single administrative domain AS s run an intra domain routing protocols Distance Vector e g RIP Link State e g OSPF Ion Stoica September 30 2002 Between AS s runs inter domain routing protocols e g Border Gateway Routing BGP De facto standard today BGP 4 this presentation is based on the on line slides of J Kurose K Rose istoica cs berkele y edu Example 2 Intra domain Routing Protocols Based on unreliable datagram delivery Distance vector Interior router BGP router Routing Information Protocol RIP based on Bellman Ford Each neighbor periodically exchange reachability information to its neighbors Minimal communication overhead but it takes long to converge i e in proportion to the maximum path length AS 1 AS 3 Link state AS 2 Open Shortest Path First Protocol OSPF based on Dijkstra Each network periodically floods immediate reachability information to other routers Fast convergence but high communication and computation overhead istoica cs berkele y edu 3 istoica cs berkele y edu 4 1 Routing A Link State Routing Algorithm Goal determine a good path through the network from source to destination 5 Good means usually the shortest path Network modeled as a graph 2 A Routers nodes 1 Link edges Edge cost delay congestion level B 2 D 3 C 3 1 5 1 E F 2 istoica cs berkele y edu Net topology link costs known to all nodes Accomplished via link state broadcast All nodes have same info Compute least cost paths from one node source to all other nodes Iterative after k iterations know least cost path to k closest destinations 5 to j cost infinite if not direct neighbors D v current value of cost of path from source to destination v p v predecessor node along path from source to v that is next to v S set of nodes whose least cost path definitively known istoica cs berkele y edu Dijsktra s Algorithm 6 Example Dijkstra s Algorithm 1 Initialization 2 S A 3 for all nodes v 4 if v adjacent to A 5 then D v c A v 6 else D v 7 8 Loop 9 find w not in S such that D w is a minimum 10 add w to S 11 update D v for all v adjacent to w and not in S 12 D v min D v D w c w v 13 new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v 15 until all nodes in S istoica cs berkele y edu Notations c i j link cost from node i Dijkstra s algorithm Step 0 1 2 3 4 5 start S A D B p B D C p C D D p D D E p E D F p F 2 A 1 A 5 A 5 2 A B 2 1 D 7 3 C 3 1 5 1 E istoica cs berkele y edu F 2 8 2 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 start S A AD Example Dijkstra s Algorithm D B p B D C p C D D p D D E p E D F p F 1 A 2 A 5 A 4 D 2 D Step 0 1 2 3 4 5 start S A AD ADE D B p B D C p C D D p D D E p E D F p F 1 A 2 A 5 A 4 D 2 D 3 E 4 E 5 2 A B 5 3 2 3 1 D C 1 5 1 E 2 A F 2 D 9 Step 0 1 2 3 4 5 start S A AD ADE ADEB ADEBC 2 2 1 D 1 5 1 E F 2 10 D B p B D C p C D D p D D E p E D F p F 1 A 2 A 5 A 4 D 2 D 3 E 4 E 5 A 3 Example Dijkstra s Algorithm D B p B D C p C D D p D D E p E D F p F 1 A 2 A 5 A 4 D 2 D 3 E 4 E B C istoica cs berkele y edu Example Dijkstra s Algorithm start S A AD ADE ADEB 3 1 2 istoica cs berkele y edu Step 0 1 2 3 4 5 B 5 3 C 3 1 5 1 E istoica cs berkele y edu 2 A F B 2 1 2 D 11 3 C 3 1 5 1 E istoica cs berkele y edu F 2 12 3 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 start S A AD ADE ADEB ADEBC ADEBCF Dijkstra s Algorithm Discussion D B p B D C p C D D p D D E p E D F p F 1 A 2 A 5 A 4 D 2 D 3 E 4 E Algorithm complexity n nodes Each iteration need to check all nodes w not in S n n 1 2 comparisons O n 2 More efficient implementations possible O n log n Oscillation possible E g link cost amount of carried traffic 5 A B 2 1 D 1 3 C 3 1 1 E D 5 0 F 1 e initially recompute routing 13 A 0 2 e D 0 0 B 1 1 e C 2 e A 0 D 1 e 1 B e 0 C recompute recompute istoica cs berkele y edu Distance Vector Routing Algorithm 14 Example Distance Routing Table Iterative continues until no nodes exchange info Asynchronous nodes need not exchange info iterate in lock step Distributed each node communicates only with directlyattached neighbors Routing distance table data structure each router maintains Row for each possible destination Column for each directly attached neighbor to node Entry in row Y and column Z of node X distance from X to Y via Z as next hop 6 A B 1 E cost to destination via D A B D A 1 14 5 B 7 8 5 C 6 9 4 D 4 11 2 2 8 1 E C 2 D E D D C D c E D minw D C w 2 2 4 E D D A D c E D minw D A w loop 2 3 5 E D X Y Z c X Z min w D Z Z w istoica cs berkele y edu C 2 e A 0 D 1 e 1 B 0 0 C 1 e B e 1 2 istoica cs berkele y edu A 0 0 destination 2 B D A B c E B minw D A w loop 8 6 14 15 istoica cs berkele y edu 16 4 Routing Table E cost to destination via Outgoing link to use cost A B D …
View Full Document
Unlocking...