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