EE 122 Intra domain routing Ion Stoica September 30 2002 this presentation is based on the on line slides of J Kurose K Rose Internet Routing Internet organized as a two level hierarchy First level autonomous systems AS s 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 Between AS s runs inter domain routing protocols e g Border Gateway Routing BGP De facto standard today BGP 4 istoica cs berkeley edu 2 Example Interior router BGP router AS 1 AS 3 AS 2 istoica cs berkeley edu 3 Intra domain Routing Protocols Based on unreliable datagram delivery Distance vector 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 Link state 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 berkeley edu 4 Routing Goal determine a good path through the network from source to destination 5 Good means usually the shortest path Network modeled as a graph A Routers nodes 1 Link edges Edge cost delay congestion level istoica cs berkeley edu 2 B 2 D 3 C 3 1 5 F 1 E 2 5 A Link State Routing Algorithm Dijkstra s algorithm 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 Notations c i j link cost from node i 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 berkeley edu 6 Dijsktra 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 berkeley edu 7 Example 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 3 C 3 1 5 F 1 E istoica cs berkeley edu 2 8 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 start S A AD 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 4 D 2 D 5 2 A B 2 1 D 3 C 3 1 5 F 1 E istoica cs berkeley edu 2 9 Example Dijkstra s Algorithm 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 2 1 D 3 C 3 1 5 F 1 E istoica cs berkeley edu 2 10 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 start S A AD ADE ADEB 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 4 D 2 D 3 E 4 E 5 2 A B 2 1 D 3 C 3 1 5 F 1 E istoica cs berkeley edu 2 11 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 start S A AD ADE ADEB ADEBC 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 4 D 2 D 3 E 4 E 5 2 A B 2 1 D 3 C 3 1 5 F 1 E istoica cs berkeley edu 2 12 Example Dijkstra s Algorithm Step 0 1 2 3 4 5 start S A AD ADE ADEB ADEBC ADEBCF 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 2 1 D 3 C 3 1 5 F 1 E istoica cs berkeley edu 2 13 Dijkstra s Algorithm Discussion 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 1 A 1 e D 0 0 B e 0 C 1 1 e initially 2 e A 0 D 1 e 1 B 0 0 C recompute routing A 0 2 e D 0 0 B 1 1 e C recompute istoica cs berkeley edu A 2 e 0 D 1 e 1 B e 0 C recompute 14 Distance Vector Routing Algorithm 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 X Z D Y Z c X Z min w D Z w istoica cs berkeley edu 15 Example Distance Routing Table A E D C D D A D E C 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 B E 2 D destination 6 1 D c E D minw D C w 2 2 4 D c E D minw D A w loop 2 3 5 B D A B c E B minw D A w loop 8 6 14 istoica cs berkeley edu 16 Routing Table Forwarding Table E cost to destination via Outgoing link to use cost B D A 1 14 5 A A 1 B 7 8 5 B D 5 C 6 9 4 …
View Full Document
Unlocking...