Bài giảng Mạng máy tính - Nguyễn Cao Đạt - Chương 4: Tầng mạng (Bài giảng 2)

ường liên kết 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
18 
Chương 4: Tầng Mạng 
 4.1 Giới thiệu 
 4.2 Bên trong bộ định 
tuyến là gì? 
 4.3 IP: Internet Protocol 
 Định dạng gói tin 
 Đánh địa chỉ IPv4 
 ICMP 
 IPv6 
 4.4 Các giải thuật định 
tuyến 
 Trạng thái liên kết 
 Véc-tơ Khoảng cách 
 Định tuyến phân cấp 
 4.5 Định tuyến trong 
Internet 
 RIP 
 OSPF 
 BGP 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
19 
Một g/thuật trạng thái-liên kết 
giải thuật Dijkstra 
 tất cả nốt đều biết đồ hình 
mạng, chi phí liên kết 
 thực hiện bởi “phát tán trạng 
thái liên kết” 
 mọi nốt có cùng th/tin 
 tính tuyến đường rẻ nhất từ 1 
nốt tới tất cả nốt khác 
 tạo bảng chuyển tiếp cho nốt 
đó 
 lặp: sau k lần lặp, biết được 
tuyến đường rẻ nhất tới k đích 
Kí hiệu: 
 c(x,y): chi phí từ nốt x tới y; 
= ∞ nếu không phải hàng xóm 
trực tiếp 
 D(v): giá trị hiện tại của chi phí 
của tuyến đường từ nguồn tới 
đích v 
 p(v): nốt liền trước trên đường 
đi từ nguồn tới v 
 N': tập các nốt mà đã biết 
được đường đi xác định rẻ nhất 
tới chúng 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
20 
Giải thuật Dijsktra 
1 Khởi tạo: 
2 N' = {u} 
3 với mọi nốt v 
4 nếu v kề với u 
5 thì D(v) = c(u,v) 
6 ngoài ra D(v) = ∞ 
7 
8 Lặp 
9 tìm w không thuộc N' sao cho D(w) là min 
10 thêm w vào N' 
11 cập nhật D(v) cho tất cả v kề với w và ko thuộc N' : 
12 D(v) = min( D(v), D(w) + c(w,v) ) 
13 /* chi phí mới tới v hoặc là chi phí cũ tới v hoặc là chi phí 
14 tuyến ngắn nhất tới w cộng với chi phí từ w tới v */ 
15 tới khi tất cả các nốt đều thuộc N' 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
21 
Giải thuật Dijkstra: Ví dụ 
Bước 
0 
1 
2 
3 
4 
5 
N' 
u 
ux 
uxy 
uxyv 
uxyvw 
uxyvwz 
D(v),p(v) 
2,u 
2,u 
2,u 
D(w),p(w) 
5,u 
4,x 
3,y 
3,y 
D(x),p(x) 
1,u 
D(y),p(y) 
∞ 
2,x 
D(z),p(z) 
∞ 
∞ 
4,y 
4,y 
4,y 
u 
y x 
w v 
z 
2 
2 
1 
3 
1 
1 
2 
5 
3 
5 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
22 
Giải thuật Dijkstra: ví dụ (2) 
u 
y x 
w v 
z 
Kết quả cây đường đi ngắn nhất từ u: 
v 
x 
y 
w 
z 
(u,v) 
(u,x) 
(u,x) 
(u,x) 
(u,x) 
đích liên kết 
Kết quả bảng chuyển tiếp tại u: 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
23 
Giải thuật Dijkstra, thảo luận 
Độ phức tạp giải thuật: n nốt 
 mỗi lần lặp: phải kiểm tra tất cả n nốt, w, ko thuộc N 
 thực hiện n(n+1)/2 lần so sánh: O(n2) 
 có khả năng hiện thực tốt hơn: O(nlogn) 
Dạng khác: 
 vd, chi phí liên kết = lượng lưu lượng sử dụng 
A 
D 
C 
B 
1 1+e 
e 0 
e 
1 1 
0 0 
A 
D 
C 
B 
2+e 0 
0 0 
1+e 1 
A 
D 
C 
B 
0 2+e 
1+e 1 
0 0 
A 
D 
C 
B 
2+e 0 
e 0 
1+e 1 
khởi đầu 
… tính lại 
định tuyến 
… tính lại … tính lại 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
24 
Chương 4: Tầng Mạng 
 4.1 Giới thiệu 
 4.2 Bên trong bộ định 
tuyến là gì? 
 4.3 IP: Internet Protocol 
 Định dạng gói tin 
 Đánh địa chỉ IPv4 
 ICMP 
 IPv6 
 4.4 Các giải thuật định 
tuyến 
 Trạng thái liên kết 
 Véc-tơ Khoảng cách 
 Định tuyến phân cấp 
 4.5 Định tuyến trong 
Internet 
 RIP 
 OSPF 
 BGP 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
25 
Giải thuật Véc tơ-Khoảng cách 
Phương trình Bellman-Ford (lập trình động) 
Xác định 
dx(y) := chí phí của tuyến đường rẻ nhất từ x tới y 
Khi đó 
dx(y) = min {c(x,v) + dv(y) } 
với min được lấy trên tất cả hàng xóm v của x 
v 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
26 
Ví dụ Bellman-Ford 
u 
y x 
w v 
z 
2 
2 
1 
3 
1 
1 
2 
5 
3 
5 
Rõ ràng, dv(z) = 5, dx(z) = 3, dw(z) = 3 
du(z) = min { c(u,v) + dv(z), 
 c(u,x) + dx(z), 
 c(u,w) + dw(z) } 
 = min {2 + 5, 
 1 + 3, 
 5 + 3} = 4 
node mà đạt được giá trị min sẽ là node tiếp theo trong 
tuyến đường ngắn nhất ➜ bảng chuyển tiếp 
phương trình B-F: 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
27 
Giải thuật Véc tơ-Khoảng cách 
 Dx(y) = chi phí thấp nhất từ x tới y 
 node x biết chi phí tới mỗi hàng xóm v: c(x,v) 
 node x duy trì véc tơ khoảng cách 
Dx = [Dx(y): y є N ] 
 node x cũng duy trì các véc tơ khoảng cách của hàng xóm 
 Cho mỗi hàng xóm v, x duy trì 
Dv = [Dv(y): y є N ] 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
28 
Giải thuật Véc tơ-Khoảng cách 
Ý tưởng căn bản: 
 Qua thời gian, mỗi node gửi đo đạc VTKC của nó tới các 
hàng xóm 
 Không đồng bộ 
 Khi một node x nhận được DV mới từ hàng xóm, nó cập 
nhật DV của nó sử dụng p/trình B-F: 
 Với vài điều kiện nhỏ, giá trị của Dx(y) sẽ hội tụ tới giá trị 
chi phí nhỏ nhất thực tế dx(y) 
Dx(y) ← minv{c(x,v) + Dv(y)} với mọi node y ∊ N 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
29 
Giải thuật Véc tơ-Khoảng cách (5) 
Lặp, không đồng bộ: mỗi 
vòng lặp cục bộ gây ra bởi: 
 thay đổi chi phí liên kết cục 
bộ 
 thông điệp cập nhật DV từ 
hàng xóm 
Phân tán: 
 mỗi node thông báo cho 
hàng xóm chỉ khi DV của nó 
thay đổi 
 hàng xóm khi đó sẽ lại 
thông báo cho hàng xóm 
của chúng, nếu cần 
chờ cho (thay đổi trong chi 
phí của liên kết cục bộ hoặc 
t/điệp từ hàng xóm) 
tính lại các đo đạc 
nếu DV tới bất kì đích nào 
thay đổi, thông báo cho hàng 
xóm 
Mỗi node: 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
30 
x y z 
x 
y 
z 
0 2 7 
∞ ∞ ∞ 
∞ ∞ ∞ 
từ
c.phí tới 
từ
từ
x y z 
x 
y 
z 
0 
từ
c.phí tới 
x y z 
x 
y 
z 
∞ ∞ 
∞ ∞ ∞ 
c.phí tới 
x y z 
x 
y 
z 
∞ ∞ ∞ 
7 1 0 
c.phí tới 
∞ 
2 0 1 
∞ ∞ 
∞ 
2 0 1 
7 1 0 
t 
x z 
1 2 
7 
y 
bảng node x 
bảng node y 
bảng node z 
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} 
 = min{2+0 , 7+1} = 2 
Dx(z) = min{c(x,y) + 
 Dy(z), c(x,z) + Dz(z)} 
= min{2+1 , 7+0} = 3 
3 2 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
31 
x y z 
x 
y 
z 
0 2 7 
∞ ∞ ∞ 
∞ ∞ ∞ 
từ
c.phí tới 
từ
từ
x y z 
x 
y 
z 
0 2 3 
từ
c.phí tới 
x y z 
x 
y 
z 
0 2 3 
từ
c.phí tới 
x y z 
x 
y 
z 
∞ ∞ 
∞ ∞ ∞ 
c.phí tới 
x y z 
x 
y 
z 
0 2 7 
từ
c.phí tới 
x y z 
x 
y 
z 
0 2 3 
từ
c.phí tới 
x y z 
x 
y 
z 
0 2 3 
từ
c.phí tới 
x y z 
x 
y 
z 
0 2 7 
từ
c.phí tới 
x y z 
x 
y 
z 
∞ ∞ ∞ 
7 1 0 
c.phí tới 
∞ 
2 0 1 
∞ ∞ ∞ 
2 0 1 
7 1 0 
2 0 1 
7 1 0 
2 0 1 
3 1 0 
2 0 1 
3 1 0 
2 0 1 
3 1 0 
2 0 1 
3 1 0 
t 
x z 
1 2 
7 
y 
bảng node x 
bảng node y 
bảng node z 
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} 
 = min{2+0 , 7+1} = 2 
Dx(z) = min{c(x,y) + 
 Dy(z), c(x,z) + Dz(z)} 
= min{2+1 , 7+0} = 3 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
32 
VTKC: chi phí liên kết thay đổi 
Chi phí liên kết thay đổi: 
 node nhận ra sự thay đổi chi phí trong liên 
kết cục bộ 
 cập nhật t/tin định tuyến, tính lại véc tơ KC 
 nếu DV thay đổi, thông báo hàng xóm 
 “tin 
tốt 
truyền 
nhanh” 
x z 
1 4 
50 
y 
1 
tại t0, y phát hiện thay đổi chi phí lk, cập nhật DV của nó, 
và thông báo hàng xóm. 
tại t1, z nhận được cập nhật của y và cập nhật bảng của nó. Nó tính 
chi phí thấp nhất tới x và gửi cho hàng xóm DV của nó. 
tại t2, y nhận được cập nhật của z và cập nhật DV của nó. 
tuyến đường chi phí thấp nhất của y không đổi vì vậy nó không 
gửi thông điệp nào cho z. 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
33 
Véc tơ KC: chi phí liên kết thay đổi 
Chi phí liên kết thay đổi: 
 tin tốt truyền nhanh 
 tin xấu truyền chậm – vấn đề “đếm 
tới vô cùng”! 
 44 vòng lặp trước khi giải thuật ổn 
định 
Sự nhiễm độc ngược: 
 Nếu Z đi qua Y để tới X: 
 Z nói Y khoảng cách của nó tới X là vô tận (vậy Y 
sẽ không đi qua Z để tới X) 
 liệu cách này có giải quyết hoàn toàn 
vấn đề đếm tới vô cùng không? 
x z 
1 4 
50 
y 
60 
Trường Đại Học Bách Khoa Tp.HCM 
Khoa Khoa Học và Kỹ Thuật Máy Tính 
© 2011 
MẠNG MÁY TÍNH CĂN BẢN 
Bài giảng 3 - Chương 4: Tầng Mạng 
34 
So sánh các giải thuật LS và DV 
Sự phức tạp của th/điệp 
 LS: với n node, E liên kết, O(nE) 
th/đ được gửi 
 DV: chỉ trao đổi giữa hàng xóm với 
nhau 
 t/gian hội tụ thay đổi 
Tốc độ hội tụ 
 LS: O(n2) giải thuật cần O(nE) 
thông điệp 
 có thể có dao động 
 DV: thời gian hội tụ thay đổi 
 có thể có vòng lặp định tuyến 
 vấn đề đếm-tới-vô-cùng 
Sức chịu đựng: nếu bđt trục 
trặc? 
LS: 
 node có thể quảng bá chi 
phí liên kết sai 
 mỗi node chỉ tính toán 
bảng của riêng nó 
DV: 
 node DV có thể quảng bá 
chi phí tuyến đường sai 
 mỗi bảng của node được 
dùng bởi các node khác 
 lỗi lan truyền trong mạng