Advanced Computer Networks: Lecture 21 - Dr. Amir Qayyum
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (342.53 KB, 13 trang )
CS716
Advanced Computer Networks
By Dr. Amir Qayyum
1
Lecture No. 21
Distance Vector Routing Example
Information in routing table of each node:
Iteration 1
At Distance to reach node
node A B C D E F G
A 0 1 1 x 1 1 x
B 1 0 1 x x x x
C 1 1 0 1 x x x
D x x 1 0 x x 1
E 1 x x x 0 x x
F 1 x x x x 0 1
G x x x 1 x 1 0
B
C
A
D
E
F
G
Distance Vector Routing Example
Information in routing table of each node:
Iteration 2
At Distance to reach node
node A B C D E F G
A 0 1 1 2 1 1 2
B 1 0 1 2 2 2 x
C 1 1 0 1 2 2 2
D 2 2 1 0 x 2 1
E 1 2 2 x 0 2 x
F 1 2 2 2 2 0 1
G 2 x 2 1 x 1 0
B
C
A
D
E
F
G
Distance Vector Routing Example
Information in routing table of each node:
Iteration 3
At Distance to reach node
node A B C D E F G
A 0 1 1 2 1 1 2
B 1 0 1 2 2 2 3
C 1 1 0 1 2 2 2
D 2 2 1 0 3 2 1
E 1 2 2 3 0 2 3
F 1 2 2 2 2 0 1
G 2 3 2 1 3 1 0
B
C
A
D
E
F
G
Distance Vector Routing Table
B
C
A
D
E
F
G
Destination
Cost
NextHop
A
1
A
C
1
C
D
2
C
E
2
A
F
2
A
G
3
A
Distance Vector Routing: Link Failure
• F detects that link to G has failed
• F sets distance to G to infinity and
sends update to A
• A sets distance to G to infinity since
it uses F to reach G
• A receives periodic update from C
with 2hop path to G
• A sets distance to G to 3 and sends
update to F
• F decides it can reach G in 4 hops
via A
B
C
A
D
E
F
G
Count to Infinity Problem
• Link from A to E fails
• A advertises distance of infinity to E, but
B and C advertise a distance of 2 to E !
• B decides it can reach E in 3 hops;
advertises this to all
• A decides it can read E in 4 hops;
advertises this to all
A
• C decides that it can reach E in 5 hops…
• We are counting to infinity …
F
B
C
D
E
G
Split Horizon
C : 2 : B
AA
C : 2 : B
DD
Loop of > 2 nodes fails split horizon !!!
BB
C : 1 : C
C : ∞ :
CC
Reliable Flooding
X
A
C
B
D
X
A
C
B
(a)
X
A
C
B
(c)
D
(b)
D
X
A
C
B
D
(d)
10
•
Route Calculation: Dijkstra’s Shortest
Path Algorithm
Let
–
–
–
–
–
N denotes set of nodes in the graph
l (i, j) denotes nonnegative cost (weight) for edge (i, j)
s denotes this node
M denotes the set of nodes incorporated so far
C(n) denotes cost of the path from s to node n
M = {s}
for each n in N - {s}
C(n) = l(s, n)
// calculate cost to each node
while (M != N)
M = M union {w} such that C(w) is the minimum for
all w in (N - M)
for each n in (N - M)
C(n) = MIN(C(n), C (w) + l(w, n ))
11
Link State Algorithm
1.
2.
3.
Initialize confirmed with entry for self (cost = 0)
For newly added node (next), select its LSP
For each neighbor of next, calculate cost to reach
neighbor as the sum of cost from self to next and from
next to neighbor
1.
2.
4.
If neighbor is currently in neither confirmed nor tentative, add
<neighbor, cost, nexthop> to tentative, where nexthop is the
direction to reach next
If neighbor is currently in tentative and cost is less than current
cost for neighbor , then replace current entry with
If tentative is empty, stop. Otherwise pick entry from
tentative with the lowest cost, move it to confirmed and
return to step 2.
12
Route Calculation
At node D
Confirmed list
Tentative list
1. (D,0,)
2. (D,0,)
(C,2,C), (B,11,B)
3. (D,0,), (C,2,C)
(B,11,B)
4. (D,0,), (C,2,C)
(B,5,C), (A,12,C)
5
5. (D,0,), (C,2,C), (B,5,C)
(A,12,C)
6. (D,0,), (C,2,C), (B,5,C)
(A,10,C)
A
7. (D,0,), (C,2,C), (B,5,C), (A,10,C)
B
3
10
11
D
C
2
