CMU CS 15441 - Lecture-Routing (46 pages)

Previewing pages 1, 2, 3, 22, 23, 24, 44, 45, 46 of 46 page document View the full content.
View Full Document

Lecture-Routing



Previewing pages 1, 2, 3, 22, 23, 24, 44, 45, 46 of actual document.

View the full content.
View Full Document
View Full Document

Lecture-Routing

147 views


Pages:
46
School:
Carnegie Mellon University
Course:
Cs 15441 - Computer Networks
Computer Networks Documents
Unformatted text preview:

15 441 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 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 Router This next lecture How to generate the forwarding table 9 28 2006 Lecture 10 Intra Domain Routing 2 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 E 2 A 3 C 1 1 F 6 1 4 3 D B 9 28 2006 Lecture 10 Intra Domain Routing 3 Routes from Node A 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 E 2 3 C 1 1 F 6 A 1 4 3 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 4 Ways to Compute Shortest Paths Centralized Collect graph structure in one place Use standard graph algorithm Disseminate routing tables Distance vector No one has copy of graph Nodes construct their own tables iteratively Each sends information about its table to neighbors Link state Every node collects complete graph structure Each computes shortest paths from it Each generates own routing table 9 28 2006 Lecture 10 Intra Domain Routing 5 Outline Distance Vector Link State Routing Hierarchy 9 28 2006 Lecture 10 Intra Domain Routing 6 Distance Vector Method Initial Table for A Dest Cost Next Hop A 0 A B 4 B C D E 2 E F 6 F E 2 A 3 C 1 1 F 6 1 4 3 D B 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 9 28 2006 Lecture 10 Intra Domain Routing 7 Distance Vector Update z d z y c x z x y 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 z Updated cost next hop else return d x y nexthop x y 9 28 2006 Existing cost next hop Lecture 10 Intra Domain Routing 8 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 9 28 2006 Lecture 10 Intra Domain Routing 9 Start Optimum 1 hop paths Table for A Table for B Dst Cst Hop Dst Cst Hop A 0 A A 4 A B 4 B B 0 B C C D D 3 D E 2 E E F 6 F F 1 F Table for C E 3 1 F 2 6 A 1 3 4 D B Table for D Table for E Table for F Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst Hop A A A 2 A A 6 A B B 3 B B B 1 B C 0 C C 1 C C C 1 C D 1 D D 0 D D D E E E 0 E E 3 E F 1 F F F 3 F F 0 F 9 28 2006 C 1 Lecture 10 Intra Domain Routing 10 Iteration 1 Optimum 2 hop paths Table for A Table for B Dst Cst Hop Dst Cst Hop A 0 A A 4 A B 4 B B 0 B C 7 F C 2 F D 7 B D 3 D E 2 E E 4 F F 5 E F 1 F Table for C E 3 1 F 2 6 A 1 3 4 D B Table for D Table for E Table for F Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst Hop A 7 F A 7 B A 2 A A 5 B B 2 F B 3 B B 4 F B 1 B C 0 C C 1 C C 4 F C 1 C D 1 D D 0 D D D 2 C E 4 F E E 0 E E 3 E F 1 F F 2 C F 3 F F 0 F 9 28 2006 C 1 Lecture 10 Intra Domain Routing 11 Iteration 2 Optimum 3 hop paths Table for A Table for B Dst Cst Hop Dst Cst Hop A 0 A A 4 A B 4 B B 0 B C 6 E C 2 F D 7 B D 3 D E 2 E E 4 F F 5 E F 1 F Table for C E 3 1 F 2 6 A 1 3 4 D B Table for D Table for E Table for F Dst Cst Hop Dst Cst Hop Dst Cst Hop Dst Cst Hop A 6 F A 7 B A 2 A A 5 B B 2 F B 3 B B 4 F B 1 B C 0 C C 1 C C 4 F C 1 C D 1 D D 0 D D 5 F D 2 C E 4 F E 5 C E 0 E E 3 E F 1 F F 2 C F 3 F F 0 F 9 28 2006 C 1 Lecture 10 Intra Domain Routing 12 Distance Vector Link Cost Changes Link cost changes Node detects local link cost change Updates distance table If cost change in least cost path notify neighbors 4 X Y 50 1 Z algorithm terminates good news travels fast 9 28 2006 1 Lecture 10 Intra Domain Routing 13 Distance Vector Link Cost Changes Link cost changes Good news travels fast Bad news travels slow count to infinity problem 60 4 X Y 50 1 Z algorithm continues on 9 28 2006 Lecture 10 Intra Domain Routing 14 Distance Vector Split Horizon If Z routes through Y to get to X Z does not advertise its route to X back to Y 60 4 X Y 1 50 Z algorithm terminates 9 28 2006 Lecture 10 Intra Domain Routing 15 Distance Vector Poison Reverse If Z routes through Y to get to X Z tells Y its Z s distance to X is infinite so Y won t route to X via Z Eliminates some possible timeouts with split horizon Will this completely solve count to infinity problem 60 4 X Y 1 50 Z algorithm terminates 9 28 2006 Lecture 10 Intra Domain Routing 16 Poison Reverse Failures Table for A Table for B …


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Lecture-Routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture-Routing and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?