[PDF] Review: Routing in Packet Networks Shortest Path Algorithms





Previous PDF Next PDF



Shortest Paths (Dijkstras Algorithm) 1. For each of the graphs below

In fact I will maintain two elements in the table



Review: Routing in Packet Networks Shortest Path Algorithms

How are routing tables determined? ? Who determines table entries? When do routing table entries change? ... Dijkstra's algorithm: example.



Programmatic implementation of the Dijkstra algorithm in the

finding paths in a graph using Dijkstra's algorithm set as a sequence of the example of the database tables



Weighted Sum-Dijkstras Algorithm in Best Path Identification based

Dijkstra's Algorithm is a shortest path algorithm that considers a single criterion only. Table 3. Weight allocation of Different Criteria for Example.



Dijsktras Algorithm

Dijkstra's algorithm: example (Step1) hop in shortest path used in forwarding table ... Example: setting forwarding table in router 1d.



Networking: Routing Algorithms

Dijkstra's algorithm: Example. • Source is node u. Resulting forwarding table in u: ... network in order to determine its forwarding table.



Dijkstras Algorithm

Example: For shortest path to C why do we choose edge (B



Priority Queues and Dijkstras Algorithm ? - Mo Chen † Rezaul

12 oct. 2007 Table 1: Amortized I/O bounds for heaps with Decrease-Keys (N = # items in queue B = block size



Dijkstras algorithm: another example

Node u's rouTng table: Shortest path from u to w according to above result. A. 5 through v. B. 4 through x. C. 3 through x. D. 3 through y.



EE 122: Shortest Path Routing

Individual router creating a forwarding table use Dijkstra to compute the shortest path to every other ... Example: Dijkstra's Algorithm.

Page 1

Review:

Routing in Packet Networks

Shortest Path Algorithms:

Dijkstra's & Bellman-Ford

2

Routing:ȱIssues

Whoȱdeterminesȱtableȱentries?

Howȱtoȱcontrolȱtableȱsize?

Page 2

3

Scalability

4

Techniqueȱ1:ȱFlooding

Advantages:

Disadvantages:

ȬWasteȱcapacityȱofȱlinks

Router

Page 3

5

HopȬbyȬHop/SourceȱRouting

HopȬbyȬhopȱrouting

ȬExample:ȱIP

Sourceȱrouting

6

SourceȱRouting

0132
0 13 2 0 13 2 0 13 2 301
301
301

Switch 3

Host B

Switch 2

Host ASwitch 1

Page 4

7

DistributedȱRoutingȱAlgorithms

ȬLinkȱstateȱrouting

ȬDistanceȱvectorȱrouting

8

LinkȱStateȱvsDistanceȱVector

Bothȱassumeȱthat

Bothȱfindȱglobalinformation

Page 5

9

LinkȱStateȱAlgorithm

ȬTopologyȱofȱtheȱnetwork

paths

LinkȬState

10

TopologyȱDissemination

ȬLSPȱcontains

ȬUsingȱcontrolledȱflooding

LinkȬState

Page 6

11

Dijkstra'sȱAlgorithm

Givenȱtheȱnetworkȱtopology

destination?

Someȱnotation

ȬX:ȱsourceȱnode

far •Nȱisȱinitiallyȱempty 12

Algorithmȱ(atȱNodeȱX)

Initialization

ȬNȱ=ȱ{X}

ȬForȱallȱnodesȱV

Loop

ȬAddȱUȱintoȱsetȱN

Page 7

13

LinkȬState

14

Dijkstra'sȱalgorithm:ȱexample

Step 0 1 2 3 4

5start N

A AD ADE ADEB ADEBC

ADEBCFD(B),p(B)

2,A 2,A

2,AD(C),p(C)

5,A 4,D 3,E

3,ED(D),p(D)

1,AD(E),p(E)

infinity

2,DD(F),p(F)

infinity infinity 4,E 4,E 4,E A ED CB F 2 2 13 11 25
35

LinkȬState

Page 8

15 A ED CB F 2 2 13 11 25
35

RoutingȱTableȱComputation

dest next BB CD DD ED FD

LinkȬState

16

DistanceȱVectorȱRouting

ȬComputesȱ"shortestȱpaths"

•D X

Page 9

17

DistanceȱTable:ȱExample

A E D CB 7 8 1 21
2 D () A B C DA 1 7 6 4B 14 8 9 11D 5 5 4 2

Ecost to destination via

destination

DistanceȱVector

18 D () A B C DA 1 7 6 4B 14 8 9 11D 5 5 4 2

Ecost to destination via

destination A B C DA,1 D,5 D,4 D,2

Outgoing link

to use, cost destination

Distance tableRouting table

DistanceȱVector

Page 10

19

Iterative:

continuesȱuntilȱnoȱnodesȱ exchangeȱinfo. selfȬterminating:ȱnoȱ"signal" toȱstop

Asynchronous:

nodesȱneedȱnotexchangeȱ info/iterateȱinȱlockȱstep!

Distributed:

eachȱnodeȱtalksȱonlywithȱ directlyȬattachedȱneighbors

DistanceȱTableȱdataȱstructure

Eachȱnodeȱhasȱitsȱown

neighborȱtoȱnode neighborȱZ:

D (Y,Z)

Xdistance fromX to

Y, viaZ as next hop

c(X,Z) + min {D (Y,w)} Z w

DistanceȱVector

20

Iterative,ȱasynchronous:ȱeachȱ

iterationȱcausedȱby:ȱ

Localȱlinkȱcostȱchangeȱ

Distributed:

anyȱdestinationȱchanges neighborsȱifȱȱnecessary waitfor (change in local link cost or msg from neighbor) recomputedistance table if least cost path to any dest has changed, notify neighbors

Each node:

DistanceȱVector

Page 11

21
XZ 12 7 Y

D (Y,Z)

X c(X,Z) + min {D (Y,w)} w

7+1 = 8

Z

D (Z,Y)

X c(X,Y) + min {D (Z,w)} w

2+1 = 3

Y

DistanceȱVector

22
XZ 12 7 Y

DistanceȱVector

Page 12

23

ConvergenceȱofȱDVȱRouting

Updatesȱdistanceȱtable

neighbors XZ 14 50
Y 1 algorithm terminates "good news travels fast"

DistanceȱVector

24

ProblemsȱwithȱDVȱRouting

Linkȱcostȱchanges:

Goodȱnewsȱtravelsȱfastȱ

Badȱnewsȱtravelsȱslow

Ȭ"CountȱtoȱInfinity"problem!

XZ 14 50
Y 60
algorithm continues on!

DistanceȱVector

Page 13

25

CountȬtoȬInfinityȱProblem

XYZ 11 2

DistanceȱVector

26

Splitȱhorizon

ȬAȱrouterȱnever advertisesȱtheȱcostȱofȱaȱdestinationȱtoȱaȱ neighbor

ȬAcceleratesȱconvergence

DistanceȱVector

Page 14

27
won'tȱrouteȱtoȱXȱviaȱZ) XZ 14 50
Y 60
algorithm terminates

DistanceȱVector

28

LinkȱStateȱvsDistanceȱVector

Tellsȱeveryoneȱaboutȱ

neighbors

Controlledȱfloodingȱtoȱ

exchangeȱlinkȱstate

Dijkstra'sȱalgorithm

Eachȱrouterȱcomputesȱitsȱ

ownȱtable

Mayȱhaveȱoscillations

OpenȱShortestȱPathȱFirstȱ

(OSPF)

Tellsȱneighborsȱaboutȱ

everyone

Exchangesȱdistanceȱ

vectorsȱwithȱneighbors

BellmanȬFordȱalgorithm

byȱothers

Mayȱhaveȱroutingȱloops

RoutingȱInformationȱ

Protocolȱ(RIP)

quotesdbs_dbs21.pdfusesText_27
[PDF] dijkstra algorithm in operation research

[PDF] dijkstra algorithm java explained

[PDF] dijkstra algorithm mit

[PDF] dijkstra algorithm pdf

[PDF] dijkstra algorithm ppt

[PDF] dijkstra algorithm pseudocode

[PDF] dijkstra algorithm python

[PDF] dijkstra algorithm runtime

[PDF] dijkstra algorithm space complexity

[PDF] dijkstra algorithm table

[PDF] dijkstra algorithm time and space complexity

[PDF] dijkstra algorithm time complexity

[PDF] dijkstra algorithm time complexity proof

[PDF] dijkstra algorithm visualization

[PDF] dijkstra pseudocode