Chương 8<br />
<br />
GI I THU T<br />
NH TUY N<br />
(ROUTING ALGORITHM)<br />
<br />
Gi i thu t<br />
<br />
nh tuy n<br />
<br />
4-1<br />
<br />
N I DUNG<br />
T ng quan<br />
Link state<br />
Distance Vector<br />
Hierarchical routing<br />
<br />
Gi i thu t<br />
<br />
nh tuy n<br />
<br />
4-2<br />
<br />
T ng quan: Ph i h p gi a routing và<br />
forwarding<br />
routing algorithm<br />
<br />
local forwarding table<br />
header value output link<br />
0100<br />
0101<br />
0111<br />
1001<br />
<br />
Tham s trong<br />
header c a gói<br />
<br />
3<br />
2<br />
2<br />
1<br />
<br />
n<br />
0111<br />
<br />
1<br />
3 2<br />
<br />
Gi i thu t<br />
<br />
nh tuy n<br />
<br />
4-3<br />
<br />
T ng quan:<br />
<br />
th m ng<br />
5<br />
2<br />
<br />
u<br />
<br />
2<br />
1<br />
<br />
Graph: G = (N,E)<br />
<br />
v<br />
<br />
x<br />
<br />
3<br />
<br />
w<br />
3<br />
<br />
1<br />
<br />
5<br />
<br />
z<br />
<br />
1<br />
<br />
y<br />
<br />
2<br />
<br />
N = t p các router = { u, v, w, x, y, z }<br />
E = t p các liên k t={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }<br />
th m ng cũng h u d ng trong các ng c nh m ng khác<br />
Ví d : P2P, v i N là tâp các peer và E là t p các k t n i TCP<br />
Gi i thu t<br />
<br />
nh tuy n<br />
<br />
4-4<br />
<br />
T ng quan: Chi phí liên k t (cost)<br />
5<br />
2<br />
<br />
u<br />
<br />
v<br />
2<br />
<br />
1<br />
<br />
x<br />
<br />
• c(x,x’) = chi phí c a liên k t (x,x’)<br />
3<br />
<br />
w<br />
3<br />
<br />
1<br />
<br />
5<br />
<br />
z<br />
<br />
1<br />
<br />
y<br />
<br />
- ví d c(w,z) = 5<br />
<br />
2<br />
<br />
• chi phí ư c xác nh tùy theo<br />
các y u t như băng thông, m c<br />
ngh n...<br />
<br />
Chi phí c a ư ng i (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)<br />
Câu h i:<br />
<br />
Gi i thu t<br />
<br />
âu là ư ng i có chi phí nh nh t gi a u và z ?<br />
<br />
nh tuy n s xác<br />
<br />
nh ư ng i có chi phí nh nh t<br />
Gi i thu t<br />
<br />
nh tuy n<br />
<br />
4-5<br />
<br />