DOC PREVIEW
Berkeley ELENG 122 - Shortest-Path Routing: Link-State & Distance-Vector

This preview shows page 1-2 out of 5 pages.

Save
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Shortest Path Routing Link State Distance Vector EE 122 Intro to Communication Networks Fall 2007 WF 4 5 30 in Cory 277 Vern Paxson TAs Lisa Fowler Daniel Killebrew Jorge Ortiz http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford 1 Dijkstra s Shortest Path Algorithm Iterative algorithm After k iterations know least cost path to k nodes S nodes whose least cost path definitively known Initially S u where u is the source node Add one node to S in each iteration D v current cost of path from source to node v Initially D v c u v for all nodes v adjacent to u and D v for all other nodes v Continually update D v as shorter paths are learned 2 1 Dijsktra s Algorithm 1 Initialization 2 S u 3 for all nodes v 4 if v adjacent to u 5 D v c u v 6 else D v 7 8 Loop 9 find w not in S with the smallest D w 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 until all nodes in S 3 Dijkstra s Algorithm Example 2 3 2 1 1 3 1 1 4 2 4 2 1 1 5 4 5 4 3 3 2 3 2 1 1 3 1 1 4 2 4 2 1 1 5 4 5 3 4 3 4 2 Dijkstra s Algorithm Example 2 3 2 1 1 3 1 1 4 2 4 2 1 1 5 5 4 4 3 3 2 3 2 1 1 3 1 1 4 2 4 2 1 1 5 5 4 4 3 3 5 Shortest Path Tree Shortest path tree from u v u y 2 3 4 x z 1 5 w link 1 1 2 Forwarding table at u 4 t 3 s v w x y z s t u v u w u w u v u v u w u w 6 3 Distance Vector Algorithm c x v cost for direct link from x to v Node x maintains costs of direct links c x v Dx y estimate of least cost from x to y Node x maintains distance vector Dx Dx y y N Node x maintains its neighbors distance vectors For each neighbor v x maintains Dv Dv y y N Each node v periodically sends Dv to its neighbors And neighbors update their own distance vectors Dx y minv c x v Dv y for each node y N Over time the distance vector Dx converges 7 Distance Vector Example Step 1 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 C 1 1 F 2 6 1 A 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 8 4 Distance Vector Example Step 2 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 C 1 1 F 2 6 1 A D 3 4 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 Distance Vector Example Step 3 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 C 1 1 F 2 6 1 A 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 10 5


View Full Document

Berkeley ELENG 122 - Shortest-Path Routing: Link-State & Distance-Vector

Documents in this Course
Lecture 6

Lecture 6

22 pages

Wireless

Wireless

16 pages

Links

Links

21 pages

Ethernet

Ethernet

10 pages

routing

routing

11 pages

Links

Links

7 pages

Switches

Switches

30 pages

Multicast

Multicast

36 pages

Switches

Switches

18 pages

Security

Security

16 pages

Switches

Switches

18 pages

Lecture 1

Lecture 1

56 pages

OPNET

OPNET

5 pages

Lecture 4

Lecture 4

16 pages

Ethernet

Ethernet

65 pages

Models

Models

30 pages

TCP

TCP

16 pages

Wireless

Wireless

48 pages

Load more
Download Shortest-Path Routing: Link-State & Distance-Vector
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Shortest-Path Routing: Link-State & Distance-Vector 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 Shortest-Path Routing: Link-State & Distance-Vector 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?