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
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
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
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:

11Shortest-Path Routing:Link-State & Distance-VectorEE 122: Intro to Communication NetworksFall 2007 (WF 4-5:30 in Cory 277)Vern PaxsonTAs: Lisa Fowler, Daniel Killebrew & Jorge Ortizhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford2Dijkstra’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 learned23Dijsktra’s Algorithm1 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 Loop9 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 S4Dijkstra’s Algorithm Example322114145332211414533221141453322114145335Dijkstra’s Algorithm Example32211414533221141453322114145332211414536Shortest-Path Tree• Shortest-path tree from u • Forwarding table at u3221141453uvwxyzstv (u,v)w (u,w)x (u,w)y (u,v)z(u,v)links (u,w)t(u,w)47Distance 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 Dvto 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 Dxconverges8Distance Vector Example: Step 1AEFCDB23641113Table for ADst Cst HopA 0 AB 4 BC ∞ –D ∞ –E 2 EF 6 FTable for BDst Cst HopA 4 AB 0 BC ∞ –D 3 DE ∞ –F 1 FTable for CDst Cst HopA ∞ –B ∞ –C 0 CD 1 DE ∞ –F 1 FTable for DDst Cst HopA ∞ –B 3 BC 1 CD 0 DE ∞ –F ∞ –Table for EDst Cst HopA 2 AB ∞ –C ∞ –D ∞ –E 0 EF 3 FTable for FDst Cst HopA 6 AB 1 BC 1 CD ∞ –E 3 EF 0 FOptimum 1-hop paths59Distance Vector Example: Step 2Table for ADst Cst HopA 0 AB 4 BC 7 FD 7 BE 2 EF 5 ETable for BDst Cst HopA 4 AB 0 BC 2 FD 3 DE 4 FF 1 FTable for CDst Cst HopA 7 FB 2 FC 0 CD 1 DE 4 FF 1 FTable for DDst Cst HopA 7 BB 3 BC 1 CD 0 DE ∞ –F 2 CTable for EDst Cst HopA 2 AB 4 FC 4 FD ∞ –E 0 EF 3 FTable for FDst Cst HopA 5 BB 1 BC 1 CD 2 CE 3 EF 0 FOptimum 2-hop pathsAEFCDB2364111310Distance Vector Example: Step 3Table for ADst Cst HopA 0 AB 4 BC 6 ED 7 BE 2 EF 5 ETable for BDst Cst HopA 4 AB 0 BC 2 FD 3 DE 4 FF 1 FTable for CDst Cst HopA 6 FB 2 FC 0 CD 1 DE 4 FF 1 FTable for DDst Cst HopA 7 BB 3 BC 1 CD 0 DE 5 CF 2 CTable for EDst Cst HopA 2 AB 4 FC 4 FD 5 FE 0 EF 3 FTable for FDst Cst HopA 5 BB 1 BC 1 CD 2 CE 3 EF 0 FOptimum 3-hop


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 2 2 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?