Computer Networking ecture 10: Intra-Domain Routing RIP(Routing Information Protocol)& OSPF(Open Shortest Path First)
Computer Networking Lecture 10: Intra-Domain Routing RIP (Routing Information Protocol) & OSPF (Open Shortest Path First)
IP Forwarding The story So far iP addresses are structure to reflect Internet structure Router iP packet headers carry these addresses When Packet arrives at router Examine header to determine intended destination Look up in table to determine next hop in path Send packet out appropriate port This/next lecture How to generate the forwarding table 9/28/2006 Lecture 10: Intra-Domain routing 2
9/28/2006 Lecture 10: Intra-Domain Routing 2 IP Forwarding • The Story So Far… • IP addresses are structure to reflect Internet structure • IP packet headers carry these addresses • When Packet Arrives at Router • Examine header to determine intended destination • Look up in table to determine next hop in path • Send packet out appropriate port • This/next lecture • How to generate the forwarding table Router
Graph Model Represent each router as node Direct link between routers represented by edge Symmetric links= undirected graph Edge"cost c(x,y) denotes measure of difficulty of using link delay, s cost, or congestion level ·Task Determine least cost path from every node to every other node Path cost d(x, y)=sum of link costs 3 D 9/28/2006 Lecture 10: Intra-Domain routing 3
9/28/2006 Lecture 10: Intra-Domain Routing 3 Graph Model • Represent each router as node • Direct link between routers represented by edge • Symmetric links undirected graph • Edge “cost” c(x,y) denotes measure of difficulty of using link • delay, $ cost, or congestion level • Task • Determine least cost path from every node to every other node • Path cost d(x,y) = sum of link costs A E F C D B 2 3 6 4 1 1 1 3
Routes from node a Forwarding Table for A 3 Dest Cost Next Hop 2 ABCDEF 046725 ABEBEE D B Properties Some set of shortest paths forms tree Shortest path spanning tree Solution not unique E.g., A-E-F-C-D also has cost 7 9/28/2006 Lecture 10: Intra-Domain routing
9/28/2006 Lecture 10: Intra-Domain Routing 4 Routes from Node A • Properties • Some set of shortest paths forms tree • Shortest path spanning tree • Solution not unique • E.g., A-E-F-C-D also has cost 7 A E F C D B 2 3 6 4 1 1 1 3 Forwarding Table for A Dest Cost Next Hop A 0 A B 4 B C 6 E D 7 B E 2 E F 5 E
Ways to Compute Shortest Paths Centralized Collect graph structure in one place Use standard graph algorithm Disseminate routing tables ·Link- state Every node collects complete graph structure Each computes shortest paths from it Each generates own routing table Distance-vector No one has copy of graph Nodes construct their own tables iteratively Each sends information about its table to neighbors 9/28/2006 Lecture 10: Intra-Domain routing 5
9/28/2006 Lecture 10: Intra-Domain Routing 5 Ways to Compute Shortest Paths • Centralized • Collect graph structure in one place • Use standard graph algorithm • Disseminate routing tables • Link-state • Every node collects complete graph structure • Each computes shortest paths from it • Each generates own routing table • Distance-vector • No one has copy of graph • Nodes construct their own tables iteratively • Each sends information about its table to neighbors
Outline Distance∨ ector Link State Routing Hierarchy 9/28/2006 Lecture 10: Intra-Domain routing 6
9/28/2006 Lecture 10: Intra-Domain Routing 6 Outline • Distance Vector • Link State • Routing Hierarchy
Distance-Vector method Initial Table for a Dest Cost Next p A 0 A F CDEF D o A 4 E B 6 F dea At any time, have cost/next hop of best known path to destination Use cost oo when no path known Initially Only have entries for directly connected nodes 9/28/2006 Lecture 10: Intra-Domain routing 7
9/28/2006 Lecture 10: Intra-Domain Routing 7 Distance-Vector Method • Idea • At any time, have cost/next hop of best known path to destination • Use cost when no path known • Initially • Only have entries for directly connected nodes A E F C D B 2 3 6 4 1 1 1 3 Initial Table for A Dest Cost Next Hop A 0 A B 4 B C – D – E 2 E F 6 F
Distance-Vector Update (z,y) c(x, z) d(x,y) Update(x, y, z) d <c(x, Z)+d(z, y cost of path from x to y with first hop z if d< d(x,y) Found better path return d Updated cost/next hop else return d(x, y), nexthop(x,y)#Existing cost/next hop 9/28/2006 Lecture 10: Intra-Domain routing 8
9/28/2006 Lecture 10: Intra-Domain Routing 8 Distance-Vector Update • Update(x,y,z) d c(x,z) + d(z,y) # Cost of path from x to y with first hop z if d < d(x,y) # Found better path return d,z # Updated cost / next hop else return d(x,y), nexthop(x,y) # Existing cost / next hop x z y c(x,z) d(z,y) d(x,y)
Algorithm Bellman-Ford algorithm Repeat For every node X For every neighbor Z For every destination y d(xy)← Update(Xy,z) Until converge 9/28/2006 Lecture 10: Intra-Domain routing 9
9/28/2006 Lecture 10: Intra-Domain Routing 9 Algorithm • Bellman-Ford algorithm • Repeat For every node x For every neighbor z For every destination y d(x,y) Update(x,y,z) • Until converge
Start Optimum 1-hop paths Table for a Table for B Dst Cst Hop Dst Cst Hop 3 A 0 A A 4 B 0B 6 C D 3 D 4 E 2 E E B F F F Table for c Table for d Table for e Table for f Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst A A 2 6 A B b3 B B B C 0 C C C D D 0 D D D E E E E E 3 F F F F F F 0 9/28/2006 Lecture 10: Intra-Domain routing 10
9/28/2006 Lecture 10: Intra-Domain Routing 10 Start A E F C D B 2 3 6 4 1 1 1 3 Table for A Dst Cst Hop A 0 A B 4 B C – D – E 2 E F 6 F Table for B Dst Cst Hop A 4 A B 0 B C – D 3 D E – F 1 F Table for C Dst Cst Hop A – B – C 0 C D 1 D E – F 1 F Table for D Dst Cst Hop A – B 3 B C 1 C D 0 D E – F – Table for E Dst Cst Hop A 2 A B – C – D – E 0 E F 3 F Table for F Dst Cst Hop A 6 A B 1 B C 1 C D – E 3 E F 0 F Optimum 1-hop paths
