Bài giảng Mạng máy tính - Chương 4: Chọn đường - Ngô Hồng Sơn

1Chương 4:
Chọn ñường - Routing
Dự án HEDSPI
Khoa CNTT- ðHBK Hà Nội
Giảng viên: Ngô Hồng Sơn
Bộ môn Truyền thông và Mạng máy tính
Bài giảng có sử dụng nguồn tài liệu cung cấp bởi trường ðại học Keio, Nhật Bản
2Tổng quan

 Tuần trước

 Giao thức IP

 ðịa chỉ IP và cấu trúc gói tin IP

 Giao thức ICMP

 Tuần này: Tiếp tục về tầng mạng

 Thế nào là chọn ñường?

 Chọn ñường tĩnh và chọn ñường ñộng

 Giải thuật và giao thức chọn ñường
3Chọn ñường là gì?
Các nguyên lý chọn ñường
Cơ chế chuyển tiếp gói tin
Quy tắc “Longest matching”
4Cơ bản về chọn ñường (1)

 Khi một máy trạm gửi một gói tin IP tới một máy
khác

 Nếu ñịa chỉ ñích nằm trên cùng một ñường truyền vật lý: 
Chuyển trực tiếp

 Nếu ñịa chỉ ñích nắm trên một mạng khác: Chuyển gián
tiếp qua bộ ñịnh tuyến (chọn ñường)
Router Router
5ðích ñến（Tìm
ñường ñi）
ðích ñến? （Tìm
ñường ñi）
Cơ bản về chọn ñường (2)
6Chọn ñường là gì?

 Cơ chế ñể máy trạm hay bộ ñịnh tuyến
chuyển tiếp gói tin từ nguồn ñến ñích

 Các thành phần của chọn ñường

 Bảng chọn ñường

 Thông tin chọn ñường

 Giải thuật, giao thức chọn ñường
7Bộ ñịnh tuyến?

 Thiết bị chuyển tiếp các gói tin giữa các
mạng

 Là một máy tính, với các phần cứng chuyên dụng

 Kết nối nhiều mạng với nhau

 Chuyển tiếp gói tin dựa trên bảng chọn ñường

 Có nhiều giao diện

 Phù hợp với nhiều dạng lưu lượng và phạm
vi của mạng
8Một số ví dụ
Cisco 2600 
Cisco CRS-1 
BUFFALO
BHR-4RV
Router mạng trục
Router ngoại vi 
Router cỡ trung
Juniper M10
Cisco 3700 
Foundry Networks
NetIron 800
Hitachi
GR2000-1B
YAMAHA
RTX-1500
PLANEX
GW-AP54SAG
9Bảng chọn ñường

 Chỉ ra danh sách các ñường ñi có thể, 
ñược lưu trong bộ nhớ của router

 Các thành phần chính của bảng chọn
ñường

 ðịa chỉ ñích/mặt nạ mạng

 Router kế tiếp
10
Router B
C172.16.0.0/24
A10.0.0.0/24
Next-hopNetwork
Router CRouter A
10.0.0.0/24 192.168.0.0/24 172.16.0.0/24
10.0.0.0/24 172.16.0.0/24
Bảng chọn ñường và cơ chế
chuyển tiếp (1)
Lưu ý quy tắc: No routes, no reachability!
11
Quy tắc “Longest matching”(1)

 Giả sử một ñịa chỉ mạng ñích lại có nhiều hơn
một mục trong bảng chọn ñường

 ðịa chỉ ñích : 11.1.2.5

 Router kế tiếp nào sẽ ñược sử dụng?
C11.1.2.0/24
B11.1.0.0/16
A11.0.0.0/8
Next hopNetwork
12
Quy tắc “Longest matching”(2)
ðịa chỉ ñích:
11.1.2.5 = 00001011.00000001.00000010.00000101
ðường ñi 1:
11.1.2.0/24 = 00001011.00000001.00000010.00000000
ðường ñi 2:
11.1.0.0/16 = 00001011.00000001.00000000.00000000
ðường ñi 3:
11.0.0.0/8 = 00001011.00000000.00000000.00000000
“Longest matching” là gì?
Tại sao phải cần quy tắc này?
13
Router B
C172.16.0.0/24
Direct192.168.0.0/24
A10.0.0.0/24
Next-hopNetwork
Router CRouter A
10.0.0.0/24 192.168.0.0/24 172.16.0.0/24
10.0.0.0/24 172.16.0.0/24
Bảng chọn ñường và cơ chế
chuyển tiếp (2)
Q. Mô tả bảng chọn
ñường trên C
Nếu C nối vào
Internet?
Internet
14
ðường ñi mặc ñịnh

 Nếu ñường ñi không tìm thấy trong bảng chọn
ñường

 ðường ñi mặc ñịnh trỏ ñến một router kết tiếp

 Trong nhiều trường hợp, ñây là ñường ñi duy nhất

 0.0.0.0/0

 Là một trường hợp ñặc biệt, chỉ tất cả các ñường ñi
Internet
Router A
Router kế tiếp luôn là A
15
Kết hợp ñường ñi (Routing 
aggregation)
200.23.1.0/24
200.23.2.0/24
200.23.3.0/24
200.23.4.0/24
200.23.0.0/22
200.23.0.0/23
200.23.2.0/23

 Có bao nhiêu mạng con trên mạng Internet?

 Sẽ có rất nhiều mục trong bảng chọn ñường?

 Các mạng con kế tiếp với cùng ñịa chỉ ñích có thể ñược tổng
hợp lại ñể làm giảm số mục trong bảng chọn ñường.
16
Kết hợp ñường ñi (2)

 Ví dụ về Viettel

 Không gian ñịa chỉ IP: khá lớn

 203.113.128.0-203.113.191.255

 ðể kết nối ñến một mạng con của Vietel (khách
hàng): Chỉ cần chỉ ra ñường ñi ñến mạng Viettel

 ðường ñi mặc ñịnh chính là một dạng của việc
kết hợp ñường

 0.0.0.0/0
17
Ví dụ về bảng chọn ñường –
máy trạm
C:\Documents and Settings\hongson>netstat -rn
Route Table
===========================================================================
Interface List
0x1 ........................... MS TCP Loopback interface
0x2 ...08 00 1f b2 a1 a3 ...... Realtek RTL8139 Family PCI Fast Ethernet NIC -
===========================================================================
Active Routes:
Network Netmask Gateway Interface Metric
0.0.0.0 0.0.0.0 192.168.1.1 192.168.1.34 20
127.0.0.0 255.0.0.0 127.0.0.1 127.0.0.1 1
192.168.1.0 255.255.255.0 192.168.1.34 192.168.1.34 20
192.168.1.34 255.255.255.255 127.0.0.1 127.0.0.1 20
192.168.1.255 255.255.255.255 192.168.1.34 192.168.1.34 20
224.0.0.0 240.0.0.0 192.168.1.34 192.168.1.34 20
255.255.255.255 255.255.255.255 192.168.1.34 192.168.1.34 1
Default Gateway: 192.168.1.1
===========================================================================
18
#show ip route
Prefix Next Hop
203.238.37.0/24 via 203.178.136.14
203.238.37.96/27 via 203.178.136.26
203.238.37.128/27 via 203.178.136.26
203.170.97.0/24 via 203.178.136.14
192.68.132.0/24 via 203.178.136.29
203.254.52.0/24 via 203.178.136.14
202.171.96.0/24 via 203.178.136.14
Ví dụ về bảng chọn ñường –
Router (trích)
19
Chọn ñường tĩnh và chọn
ñường ñộng
Chọn ñường tĩnh
Chọn ñường ñộng
Ưu ñiểm – nhược ñiểm
20
Router B
C172.16.0.0/24
A10.0.0.0/24
Next-
hop
Network
Router CRouter A
10.0.0.0/24 192.168.0.0/24 172.16.0.0/24
B192.168.0.0/24
B10.0.0.0/24
Next-
hop
Network
B172.16.0.0/24
B192.168.0.0/24
Next-
hop
Network
Vấn ñề cập nhật bảng chọn ñường

 Sự thay ñổi cấu trúc mạng: thêm mạng mới, một nút mạng
bị mất ñiện

 Sự cần thiết phải cập nhật bảng chọn ñường

 Cho tất cả các nút mạng (về lý thuyết)

 Thực tế, chỉ một số nút mạng phải cập nhật
172.16.1.0/24
172.16.1.0/24 B 172.16.1.0/24 C
New Network
21
Làm thế nào ñể cập nhật?

 Chọn ñường tĩnh

 Các mục trong bảng chọn ñường ñược sửa ñổi
thủ công bởi người quản trị

 Chọn ñường ñộng

 Tự ñộng cập nhật bảng chọn ñường

 Bằng các giao thức chọn ñường
22
Chọn ñường tĩnh

 Khi có sự cố:

 Không thể nối vào
Internet kể cả khi có tồn
tại ñường ñi dự phòng

 Người quản trị mạng cần
thay ñổi
Internet
Next-hop 10.0.0.3
10.0.0.1
10.0.0.3 10.0.0.2
Next-hop 10.0.0.1
Bảng chọn ñường của 10.0.0.1 (1 phần)
10.0.0.30.0.0.0/0
Next-hopPrefix
Kết nối bị lỗi
23
Chọn ñường ñộng

 Khi có sự cố:

 ðường ñi thay thế ñược cập
nhật một cách tự ñộng
Bảng chọn ñường của 10.0.0.1 (1 phần)
10.0.0.30.0.0.0/0
10.0.0.20.0.0.0/0
Next-hopPrefix
Kết nối bị lỗi
Kết nối dự phòng
Internet
Next-hop 10.0.0.3
10.0.0.1
10.0.0.3 10.0.0.2
Next-hop 10.0.0.1
24
ðặc ñiểm của chọn ñường
tĩnh

 Ưu

 Ổn ñịnh

 An toàn

 Không bị ảnh hưởng bởi các yếu tố tác ñộng

 Nhược

 Cứng nhắc

 Không thể sử dụng tự ñộng kết nối dự phòng

 Khó quản lý
25
Chọn ñường ñộng

 Ưu

 Dễ quản lý

 Tự ñộng sử dụng kết nối dự phòng

 Nhược

 Tính an toàn

 Các giao thức chọn ñường phức tạp và khó hiểu

 Khó quản lý
26
Các giải thuật và giao
thức chọn ñường
Giải thuật Dijkstra và Bellman-Ford
Giao thức dạng link-state và dạng
distance-vector
27
Biểu diễn mạng bởi ñồ thị
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5

 ðồ thị với các nút (bộ ñịnh tuyến) và các cạnh (liên
kết)

 Chi phí cho việc sử dụng mỗi liên kết c(x,y) 

 Băng thông, ñộ trễ, chi phí, mức ñộ tắc nghẽn

 Giả thuật chọn ñường: Xác ñịnh ñường ñi ngắn nhất
giữa hai nút bất kỳ
28
Cây ñường ñi ngắn nhất - SPT

 SPT – Shortest Path Tree

 Các cạnh xuất phát từ nút gốc và tới các lá

 ðường ñi duy nhất từ nút gốc tới nút v, là ñường ñi ngắn nhất
giữa nút gốc và nút v

 Mỗi nút sẽ có một SPT của riêng nút ñó
yx
w
u zu
yx
wv
z
2
2
1
3
1
1
2
5
3
5
v
29
Tập trung hay phân tán

 Tập trung

 Thu thập thông tin vào một nút mạng

 Sử dụng các giải thuật tìm ñường ñi trên ñồ thị

 Phân bổ bảng chọn ñường từ nút trung tâm tới
các nút

 Phân tán

 Mỗi nút tự xây dựng bảng chọn ñường riêng

 Giao thức chọn ñường: Link-state hoặc distance-
vector

 ðược sử dụng phổ biến trong thực tế
30
Tập trung hay phân tán

 Thông tin chọn ñường là cần thiết ñể xây dựng
bảng chọn ñường

 Tập trung hay phân tán?

 Tập trung:

 Mỗi router có thông tin ñầy ñủ về trạng thái của mạng

 Giải thuật dạng “link state”

 Phân tán:

 Các nút chỉ biết ñược trạng thái của liên kết vật lý tới nút kế
bên

 Liên tục lặp lại việc tính toán và trao ñổi thông tin với nút kế
bên

 Giải thuật dạng “distance vector”

 “Bạn của bạn cũng là bạn”
31
Giải thuật dạng link-state
Giải thuật Dijkstra’s

 Mỗi nút ñều có sơ ñồ và chi phí mỗi link

 Quảng bá “Link-state”

 Mỗi nút có cùng thông tin

 Tìm ñường ñi chi phí nhỏ nhất từ một nút (‘nguồn’) 
tới tất cả các nút khác

 dùng ñể xây dựng bảng chọn ñường
32
Ký hiệu

 G = (V,E) : ðồ thị với tập ñỉnh V và tập cạnh E

 c(x,y): chi phí của liên kết x tới y; = ∞ nếu không
phải 2 nút kế nhau

 d(v): chi phí hiện thời của ñường ñi từ nút nguồn tới
nút ñích. v

 p(v): nút ngay trước nút v trên ñường ñi từ nguồn tới
ñích

 T: Tập các nút mà ñường ñi ngắn nhất ñã ñược xác
ñịnh
33
Các thủ tục

 Init():
Với mỗi nút v, d[v] = ∞, p[v] = NIL
d[s] = 0

 Improve(u,v), trong dó (u,v) u, v là một cạnh
nào ñó của G
if d[v] > d[u] + c(u,v) then
d[v] = d[u] + c(u,v)
p[v] = u
34
Dijsktra’s Algorithm
1. Init() ;
2. T = Φ;
3. Repeat
4. u: u ∈ T | d(u) là bé nhất ;
5. T = T ∪ {u};
6. for all v ∈ neighbor(u) và v ∉T
7. update(u,v) ;
8. Until T = V
35
Dijkstra’s algorithm: Ví dụ
Step
0
1
2
3
4
5
T
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
yx
w
u z
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
v
v
x
y
w
z
(u,v)
(u,x)
(u,x)
(u,x)
(u,x)
destination link
Bảng chọn ñường của u:
SPT của u:
36
Giải thuật dạng distance-vector (1)
Phương trình Bellman-Ford (quy hoach ñộng)
ðịnh nghĩa
dx(y) := chi phí của ñường ñi ngắn nhất
từ x tới y
Ta có
dx(y) = min {c(x,v) + dv(y) }
cho tất cả các v là hàng xóm của x 
v
37
Minh họa Bellman-Ford Eq.
u
yx
wv
z
2
2
1
3
1
1
2
5
3
5
Dễ thấy, 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
Nút nào làm giá trị trên nhỏ nhất➜ Lựa chọn là
nút kế tiếp trong bảng chọn ñường
B-F eq. cho ta biết:
38
Giải thuật dạng distance-vector (2)
ý tưởng cơ bản:

 DV: Vector khoảng cách, tạm coi là
ñường ñi ngắn nhất của từ một nút tới
những nút khác

 Mỗi nút ñịnh kỳ gửi DV của nó tới các
nút bên cạnh

 Khi nút x nhận ñược 1 DV, nó sẽ cập
nhật DV của nó qua pt Bellman-ford

 Với một số ñiều kiện, ước lượng Dx(y) 
sẽ hội tụ dần ñến giá trị nhỏ nhất dx(y)
Chờ (Thay ñổi trong DV của
nút bên cạnh)
Tính lại ước lượng DV
Nếu DV thay ñổi, Báo cho
nút bên cạnh
Mỗi nút:
39
x y z
x
y
z
0 2 7
∞ ∞ ∞
∞ ∞ ∞
t
ừ
chi phí tới
t
ừ
t
ừ
x y z
x
y
z
0
t
ừ
chi phí tới
x y z
x
y
z
∞ ∞
∞ ∞ ∞
chi phí tới
x y z
x
y
z
∞ ∞ ∞
7 1 0
chi phí tới
∞
2 0 1
∞ ∞ ∞
2 0 1
7 1 0
thờigian
x z
12
7
y
nút x
nút y
nút 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
32 
40
x y z
x
y
z
0 2 7
∞ ∞ ∞
∞ ∞ ∞
t
ừ
chi phí tới
t
ừ
t
ừ
x y z
x
y
z
0 2 3
t
ừ
chi phí tới
x y z
x
y
z
0 2 3
t
ừ
chi phí tới
x y z
x
y
z
∞ ∞
∞ ∞ ∞
chi phí tới
x y z
x
y
z
0 2 7
t
ừ
chi phí tới
x y z
x
y
z
0 2 3
t
ừ
chi phí tới
x y z
x
y
z
0 2 3
t
ừ
chi phí tới
x y z
x
y
z
0 2 7
t
ừ
chi phí tới
x y z
x
y
z
∞ ∞ ∞
7 1 0
chi 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
thờigian
x z
12
7
y
nút x
nút y
nút 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
41
So sánh các giải thuật LS và DV 
Thông ñiệp trao ñổi

 LS: n nút, E cạnh, O(nE) 
thông ñiệp

 DV: Chỉ trao ñổi giữa các
hàng xóm

 Thời gian hội tụ thay
ñổi
Tốc ñộ hội tụ

 LS: Thuật toán: O(n2) cần
O(nE) thông ñiệp

 DV: Thay ñổi
Sự chắc chắn: Giải sử một
router hoạt ñộng sai
LS:

 nút gửi các chi phí sai

 Mỗi nút tính riêng bảng
chọn ñường -> có vẻ chắc
chắn hơn
DV:

 DV có thể bị gửi sai

 Mỗi nút tính toán dựa trên
các nút khác

 Lỗi bị lan truyền trong
mạng
42
Tóm tắt

 Nguyên lý của bài toán chọn ñường

 Tĩnh vs. ñộng, tập trung vs. phân tán

 Link-state vs. distance-vector
43
Tuần tới: Các giao thức chọn
ñường trên Internet

 Chọn ñường phân cấp

 RIP

 OSPF

 BGP