路由协议.ppt

路由协议8499374767Routing
Graph abstraction for routing algorithms:
graph nodes are routers
graph edges are physical links
link cost: delay, $ cost, or congestion level
single cost
Goal: determine “good” path
(sequence of routers) thru
network from source to dest.
Routing protocol
A
E
D
C
B
F
2
2
1
3
1
1
2
5
3
5
“good” path:
typically means minimum cost path
other def’s possible
1
Network Layer
A Link-State Routing Algorithm
Dijkstra’s topology, link costs known to all nodes
plished via “link state broadcast”
all nodes have same putes least cost paths from one node (“source”) to all other nodes
gives routing table for that node
iterative: after k iterations, know least cost path to k dest.’s
Notation:
c(i,j): link cost from node i to j. cost infinite if not direct neighbors
D(v): current value of cost of path from source to dest. V
p(v): predecessor node along path from source to v, that is next v
N: set of nodes whose least cost path definitively known
2
Network Layer
Dijsktra’s Algorithm
1 Initialization:
2 N = {A}
3 for all nodes v
4 if v adjacent to A
5 then D(v) = c(A,v)
6 else D(v) = infty
7
8 Loop
9 find w not in N such that D(w) is a minimum
10 add w to N
11 update D(v) for all v adjacent to w and not in N:
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v