Bài giảng Mạng máy tính - Chương 5: Cơ sở giao thức định tuyến - Hoàng Thanh Hòa

BÀI GIẢNG 
MÔN: MẠNG MÁY TÍNH 
Giảng viên: Hoàng Thanh Hòa 
CHƢƠNG 5. CƠ SỞ 
GIAO THỨC ĐỊNH TUYẾN 
2 
Các khái niệm cơ bản trong 
định tuyến 
5.1. 
5.2. Các thuật toán định tuyến 
5.3. 
Một số giao thức định tuyến 
thông dụng 
thanhhoa48dhv@gmal.com 
5.1. Các khái niệm cơ bản 
trong định tuyến 
 Định tuyến 
 Bảng định tuyến 
 Metric 
 Giao thức định tuyến 
 Giao thức đƣợc định tuyến 
 Khoảng cách địa lý 
3 thanhhoa48dhv@gmal.com 
Khái niệm định tuyến 
 Là phƣơng pháp xác định đƣờng đi cho việc 
vận chuyển các gói tin từ nguồn đến đích hiệu 
quả nhất. 
 Do các thiết bị thuộc lớp 3 của mô hình OSI, 
thƣờng là Router. 
 Router phải xây dựng cho mình một bảng 
chứa các thông tin cần thiết => đƣờng đi tối 
ƣu nhất đến đích 
4 thanhhoa48dhv@gmal.com 
Bảng định tuyến 
 Là một bảng chứa thông tin về các tuyến 
đƣờng trên mạng, đƣợc lƣu trữ trong RAM 
của Router. 
 Bảng có thể đƣợc lập bởi ngƣời quản trị hoặc 
bằng các giao thức định tuyến. 
5 thanhhoa48dhv@gmal.com 
Bảng định tuyến 
 Gồm có các thông tin: 
- Địa chỉ đích của mạng, mạng con của hệ 
thống. 
- Địa chỉ IP của Router chặng kế tiếp phải đến. 
- Cổng đi đến Router kế tiếp. 
- Mặt nạ mạng của địa chỉ đích. 
- Khoảng cách để đến đích. 
- Thời gian từ khi Router cập nhật lần cuối. 
6 thanhhoa48dhv@gmal.com 
Khái niệm Metric 
 Là một số đo mà giao thức định tuyến sử 
dụng để từ đó chọn ra con đƣờng tối ƣu nhất. 
 Một giao thức định tuyến có thể sử dụng nhiều 
metric khác nhau 
7 thanhhoa48dhv@gmal.com 
Khái niệm Metric 
 Các metric thường được sử dụng là: 
- Path Length (chiều dài tuyến đƣờng): là metric 
cơ bản, đƣợc xác định bằng số Hop giữa nguồn 
và đích. 
- Reliability (độ tin cậy): là khái niệm chỉ độ tin 
cậy của một liên kết. 
- Delay (độ trễ): Chỉ thời gian cần để chuyển một 
packet từ nguồn tới đích. 
- Bandwith (băng thông): Chỉ lƣu lƣợng dữ liệu 
tối đa có thể truyền trên liên kết. 
8 thanhhoa48dhv@gmal.com 
Giao thức định tuyến 
 Là các giao thức để các Router sử dụng để 
trao đổi thông tin định tuyến với các Router 
khác. 
 Đƣợc cài đặt tại các Router, đƣợc sử dụng để 
tạo bảng định tuyến. 
 Có 2 loại giao thức định tuyến: 
- Giao thức định tuyến nội vùng: Rip, OSPF, 
IGRP, EIGRP. 
- Giao thức định tuyến ngoại vùng: BGP. 
9 thanhhoa48dhv@gmal.com 
Giao thức định tuyến 
 Chức năng của giao thức định tuyến: 
- Học thông tin định tuyến về các mạng từ 
Router kế cận. 
- Quảng bá thông tin định tuyến về các mạng 
đến các Router kế cận. 
- Nếu có nhiều hơn một tuyến đƣờng đến một 
mạng, chọn tuyến đƣờng tốt nhất dựa vào 
metric. 
- Chức năng hội tụ định tuyến. 
10 thanhhoa48dhv@gmal.com 
Giao thức đƣợc định tuyến 
 Là giao thức đƣợc sử dụng để định hƣớng 
cho gói dữ liệu của ngƣời dùng. 
 Cung cấp đầy đủ thông tin về địa chỉ lớp mạng 
để gói dữ liệu có thể truyền từ host này tới 
host khác dựa trên cấu trúc địa chỉ đó. 
 Các giao thức đƣợc định tuyến gồm có: 
- Internet Protocol (IP). 
- Internetwork Packet Exchange (EPX). 
11 thanhhoa48dhv@gmal.com 
Khoảng cách địa lý 
 Administrative Distance (AD): là thông số để 
đánh giá độ tin cậy của thông tin định tuyến mà 
Router nhận đƣợc từ Router hàng xóm. 
 AD là một số nguyên có giá trị từ 0 đến 255. 
 Mỗi giao thức định tuyến có một giá trị AD tƣơng 
ứng: 
- Kết nối trực tiếp: 0 
- Tuyến đường tĩnh: 1 
- Rip: 120 
- OSPF: 110 
- IGRP: 100 
12 thanhhoa48dhv@gmal.com 
5.2. Các thuật toán định tuyến 
5.2.1. Thuật toán tìm đƣờng đi ngắn nhất 
5.2.2. Thuật toán định tuyến vector khoảng cách. 
5.2.3. Thuật toán trạng thái đƣờng liên kết 
5.2.4. So sánh các thuật toán 
13 thanhhoa48dhv@gmal.com 
Thuật toán tìm đƣờng đi 
ngắn nhất 
 Thuật toán Bellman- Ford: 
Bài toán: cho đồ thị G với các đỉnh A,B,C,D có độ dài và 
đƣờng đi nhƣ hình dƣới, tìm đƣờng đi ngắn nhất từ B 
đến D. 
14 thanhhoa48dhv@gmal.com 
Thuật toán tìm đƣờng đi 
ngắn nhất 
 Thuật toán Bellman- Ford: 
Bƣớc 0: Ta đánh dấu đỉnh xuất phát B là 0, các đỉnh còn 
lại là vô cực. 
15 thanhhoa48dhv@gmal.com 
Thuật toán tìm đƣờng đi 
ngắn nhất 
 Thuật toán Bellman- Ford: 
Bƣớc 1: Cập nhật lại chi phí các đỉnh A,C 
16 thanhhoa48dhv@gmal.com 
Thuật toán tìm đƣờng đi 
ngắn nhất 
 Thuật toán Bellman- Ford: 
Bƣớc 2: Cập nhật lại chi phí các đỉnh C, D 
17 thanhhoa48dhv@gmal.com 
Thuật toán tìm đƣờng đi 
ngắn nhất 
 Thuật toán Bellman- Ford: 
Bƣớc 3: Cập nhật lại chi phí đỉnh D 
18 thanhhoa48dhv@gmal.com 
Thuật toán tìm đƣờng đi 
ngắn nhất 
 Thuật toán Bellman- Ford: 
Bài toán: Tìm đƣờng đi từ nút u đến các nút còn lại 
Gọi: D(v) là độ dài đƣờng đi ngắn nhất từ một đỉnh nào 
đó tới v 
T(v) là đỉnh nằm phía trƣớc v trên đƣờng đi ngắn 
nhất 
19 thanhhoa48dhv@gmal.com 
Thuật toán tìm đƣờng đi 
ngắn nhất 
 Thuật toán Bellman- Ford: 
Dùng thuật toán Bellman- Ford ta có bảng: 
20 
Lặp D(v), T(v) D(x), T(x) D(w), T(w) D(y), T(y) D(z), T(z) 
Khởi tạo 2,u 1,u 5,u ∞,u ∞,u 
K=1 2,u 1,u 4,x 2,x 10,w 
K=2 2,u 1,u 3,y 2,x 8,w 
K=3 2,u 1,u 3,y 2,x 4,y 
K=4 2,u 1,u 3,y 2,x 4,y 
thanhhoa48dhv@gmal.com 
Thuật toán tìm đƣờng đi 
ngắn nhất 
 Thuật toán Bellman- Ford: 
Nhƣ vậy ta có bảng định tuyến cho nút u: 
21 
Network Next hop Cost 
v v 2 
x x 1 
w x 4 
y x 2 
z x 4 
thanhhoa48dhv@gmal.com 
Thuật toán tìm đƣờng đi 
ngắn nhất 
 Thuật toán Dijkstra: 
Xét bài toán tƣơng tự nhƣ trên, xác định bảng định tuyến 
của nút u: 
22 thanhhoa48dhv@gmal.com 
Thuật toán tìm đƣờng đi 
ngắn nhất 
 Thuật toán Dijkstra: 
Áp dụng Dijsktra ta có bảng phân tích nhƣ sau: 
23 
Lặp T D(v), T(v) D(x), T(x) D(w),T(w) D(y), T(y) D(z), T(z) 
Khởi tạo vxwyz 2,u 1,u 5,u ∞,u ∞,u 
K=1 vwyz 2,u 4,x 2,x 10,w 
K=2 wyz 3,y 2,x 8,w 
K=3 wz 3,y 4,y 
K=4 z 4,y 
K=5 Rỗng 
thanhhoa48dhv@gmal.com 
Thuật toán tìm đƣờng đi 
ngắn nhất 
 Thuật toán Dijkstra: 
Từ bảng phân tích ta có bảng định tuyến của nut u là: 
24 
Network Next hop Cost 
v v 2 
x x 1 
w x 3 
y x 2 
z x 4 
thanhhoa48dhv@gmal.com 
Thuật toán Vector khoảng cách 
 Distance Vector gồm 2 phần: Distance và 
Vector. Trong đó: 
- Distance là khoảng cách (metric) để đến đích 
- Vector là hƣớng để đi đến đích, nó đƣợc xác 
định bởi next-hop của tuyến đƣờng. 
 Mỗi Router chỉ cần biết 2 yếu tố khi chọn 
đƣờng: chọn theo hƣớng nào, khoảng cách tới 
đích là bao nhiêu. 
 25 thanhhoa48dhv@gmal.com 
Thuật toán Vector khoảng cách 
26 
Là thuật toán nhằm chọn ra đƣờng đi tốt nhất 
đến đích dựa trên Bellman- Ford 
thanhhoa48dhv@gmal.com 
Thuật toán Vector khoảng cách 
 Các giao thức sử dụng Distance Vector gửi 
các cập nhật định tuyến theo chu kỳ hoặc khi 
cấu trúc mạng có sự thay đổi. 
 Mỗi Router sẽ gửi toàn bộ bảng định tuyến của 
mình cho các Router kết nối trực tiếp với nó. 
 Khi tất cả các Router cập nhật đầy đủ thông tin 
về các tuyến đƣờng tới các mạng đích => 
mạng đã hội tụ. 
27 thanhhoa48dhv@gmal.com 
Thuật toán Vector khoảng cách 
 Ưu điểm: 
- Giao thức đơn giản, cấu hình dễ dàng, dễ 
duy trì và sử dụng. 
- Thích hợp với các mạng quy mô nhỏ. 
 Nhược điểm: 
- Khi xảy ra sự cố hoặc có thay đổi trong mạng 
thì cần thời gian để hội tụ. 
- Có thể xảy ra lặp do những mâu thuẫn giữa 
các lần định tuyến. 
=> Chậm hội tụ, không thích hợp với mạng 
lớn 
28 thanhhoa48dhv@gmal.com 
Thuật toán trạng thái đƣờng 
liên kết 
 Các Router tự thu tập thông tin về đƣờng đi 
của mạng từ tất cả các Router khác. 
 Mỗi Router sẽ tự tính toán để chọn đƣờng đi 
tốt nhất cho nó đến các mạng đích. 
 Sử dụng các gói tin Hello để mang thông tin về 
các mạng kết nối trực tiếp vào Router. 
 Sử dụng các gói tin LSA mang thông tin cập 
nhật về trạng thái đƣờng liên kết của các 
Router khác trong mạng. 
29 thanhhoa48dhv@gmal.com 
Thuật toán trạng thái đƣờng 
liên kết 
 Cơ chế hoạt động: 
- Sử dụng thông tin từ gói tin Hello và LSA 
nhận đƣợc từ Router hàng xóm để xây dựng 
cơ sở dữ liệu về cấu trúc hệ thống mạng. 
- Sử dụng thuật toán SPF (Dijkstra) để tìm ra 
đƣờng ngắn nhất đến từng mạng. 
- Lƣu kết quả chọn đƣờng trong bảng định 
tuyến 
30 thanhhoa48dhv@gmal.com 
Thuật toán trạng thái đƣờng 
liên kết 
 Ưu điểm: 
- Thời gian hội tụ mạng nhanh hơn. 
- Mỗi router có một sơ đồ đầy đủ và đồng bộ 
về toàn bộ cấu trúc hệ thống mạng. Do đó 
chúng rất khó bị vòng lặp. 
- Router sử dụng thông tin mới nhất để quyết 
định chọn đƣờng đi. 
- Các giao thức định tuyến trạng thái đƣờng 
liên kết có hỗ trợ chia mạng con và phân 
vùng. 
31 thanhhoa48dhv@gmal.com 
Thuật toán trạng thái đƣờng 
liên kết 
 Nhược điểm: 
- Đòi hỏi Router phải có nhiều dung lƣợng bộ 
nhớ và năng lực xử lý cao hơn. 
- Đòi hỏi hệ thống mạng thiết kế theo mô hình 
phân cấp. 
- Tiến trình phát các gói tin LSA có thể chiếm 
dụng nhiều dung lƣợng đƣờng truyền 
32 thanhhoa48dhv@gmal.com 
5.3. Một số giao thức định tuyến 
 Giao thức RIP (Routing Information Protocol) 
 Giao thức IGRP (Interior Gateway Routing 
Protocol) 
 Giao thức OSPF (Open Short Path First) 
33 thanhhoa48dhv@gmal.com 
Giao thức định tuyến RIP 
 RIP là giao thức định tuyến véc tơ khoảng 
cách. 
 RIP gửi toàn bộ bảng định tuyến ra tất cả các 
cổng đang hoạt động đều đặn theo chu kỳ là 
30 giây. 
 RIP sử dụng Metric là hop count để tính ra 
tuyến đƣờng tốt nhất đến đích. 
 Thuật toán mà RIP sử dụng để xây dựng nên 
bảng định tuyến là Bellman-Ford. 
34 thanhhoa48dhv@gmal.com 
Giao thức định tuyến RIP 
 Các giá trị thời gian: 
- Update time: 30 giây 
- Invalid time: 180 giây 
- Holddown time: 180 giây 
- Flush time: 240 giây. 
35 thanhhoa48dhv@gmal.com 
Giao thức định tuyến RIP 
 Cơ chế hoạt động: 
- Tất cả các gói tin của RIP đều đƣợc đóng gói 
vào UDP segment với cả hai trƣờng source 
và destination Port là 520. 
- Request message: đƣợc sử dụng để gửi một 
yêu cầu tới router hàng xóm để gửi update. 
- Reponse message: mang thông tin update 
36 thanhhoa48dhv@gmal.com 
Giao thức định tuyến RIP 
 Cơ chế hoạt động: 
- Router gửi broadcast bản tin Request ra tất 
cả các cổng đang hoạt động => đợi 
- Các router hàng xóm nhận đƣợc các Request 
message rồi gửi Response message chứa 
toàn bộ bảng định tuyến 
- Khi nhận đƣợc thông tin định tuyến: 
→ tuyến đƣờng đang tồn tại sẽ bị thay thế bởi 
tuyến đƣờng mới có hop count nhỏ hơn. 
→ bỏ qua nếu hop count lớn hơn 
37 thanhhoa48dhv@gmal.com 
Giao thức định tuyến RIP 
 Cấu trúc gói tin RIP: 
38 thanhhoa48dhv@gmal.com 
Giao thức định tuyến IGRP 
 IGRP là giao thức định tuyến véc tơ khoảng 
cách, có chu kỳ update là 90 giây. 
 IGRP không sử dụng hopcount trong metric 
của mình, tuy nhiên nó vẫn theo dõi đƣợc 
hopcount. 
 Kích thƣớc của mạng cài đặt IRGP có thể lên 
tới 255 hop. 
39 thanhhoa48dhv@gmal.com 
Giao thức định tuyến IGRP 
 Các giá trị về thời gian: 
- Update time: 90 giây 
- Invalid time: 270 giây 
- Holddown time: 280 giây 
- Flush timer: 630 giây 
40 thanhhoa48dhv@gmal.com 
Giao thức định tuyến IGRP 
 Cơ chế hoạt động: 
- IGRP gửi broadcast Request packet tới tất cả 
các Router kết nối trực tiếp với nó. 
- IGRP sử dụng 3 loại tuyến đƣờng sau trong 
thông tin cập nhật: 
 Đƣờng nội bộ (Interior route): đƣờng nối trực 
tiếp với Router 
 Đƣờng hệ thống (System route): là những 
đƣờng đi giữa các mạng trong cùng một AS. 
 Đƣờng ngoại vi (Exterior route): là những 
đƣờng đi ra ngoài AS. 
41 thanhhoa48dhv@gmal.com 
Giao thức định tuyến IGRP 
 Cấu trúc gói tin IGRP: 
42 thanhhoa48dhv@gmal.com 
Giao thức định tuyến OSPF 
 OSPF là giao thức định tuyến theo trạng thái 
đƣờng liên kết, sử dụng thuật toán Dijkstra. 
 OSPF có ƣu điểm là hội tụ nhanh, hỗ trợ mạng 
có kích thƣớc lớn và không xảy ra vòng lặp 
định tuyến. 
 OSPF có thể chia một AS thành nhiều vùng 
(Area) khác nhau để giảm lƣu lƣợng định 
tuyến, dễ quản trị. 
 Là giao thức hỗ trợ chia mạng con 
43 thanhhoa48dhv@gmal.com 
Giao thức định tuyến OSPF 
 Cơ chế hoạt động: gồm có 3 hoạt động 
- Tìm kiếm và xác lập mối quan hệ với Router 
hàng xóm. 
- Trao đổi cơ sở dữ liệu (LSDB exchange). 
- Sử dụng thuật toán Dijkstra để tính toán con 
đƣờng tốt nhất đặt vào bảng định tuyến. 
44 thanhhoa48dhv@gmal.com 
Bài tập định tuyến 
 Sử dụng thuật toán Bellman –Ford, Dijkstra lập 
bảng định tuyến cho Node A 
45 thanhhoa48dhv@gmal.com 
A 
B 
D 
C 
G 
E 
F 
H 
3 
5 
2 
7 
1 
4 
3 
6 
4 
6 
2 
3 
5 
1 
Đề kiểm tra lại 
Cho địa chỉ IP: 192.168.10.210/27 
1. Cho biết địa chỉ IP trên thuộc mạng có chia 
mạng con không? Tại sao? 
2. Tìm địa chỉ mạng, địa chỉ broadcast và dải 
đia chỉ host của mạng con chứa IP trên. 
3. Hãy chia mạng con vừa tìm đƣợc thành 4 
mạng con mới, liệt kê các địa chỉ mạng, địa 
chỉ Broadcast, dải địa chỉ host của 4 mạng 
con này. 
46 thanhhoa48dhv@gmal.com 
Kiểm tra 
47 
Cho địa chỉ IP của một số Host nhƣ sau: 
 IP1: 134.135.30.10/20 
 IP2: 134.135.40.100/20 
 IP3: 134.135.50.20/20 
 IP4: 134.135.60.70/20 
Hãy cho biết trong các host trên, host nào nằm 
cùng mạng con. 
Hãy cho biết địa chỉ mạng con đó, địa chỉ 
Broadcast của mạng và liệt kê các host hợp lệ, 
tính số lƣợng host trong mạng? 
Bài tập 
Giả sử ta có một địa chỉ Host là: 
172.16.40.32/255.255.240.0 
1. Host trên thuộc mạng có chia mạng con 
không? tại sao? Nếu có thì có bao nhiêu 
mạng con và mỗi mạng con có bao nhiêu 
host. 
2. Tìm địa chỉ mạng, địa chỉ Broadcast của 
mạng chứa host trên 
3. Liệt kê dãy địa chỉ host của mạng con vừa 
tìm đƣợc 
48 thanhhoa48dhv@gmal.com 
Bài tập 
Cho hệ thống mạng gồm 228 host và địa chỉ IP 
đƣợc thiết lập ở lớp 192.168.1.0/24. Hãy chia hệ 
thống này thành 4 mạng con (Net 1: 120 host, 
Net 2: 60 host, Net 3: 30 host, Net 4: 18 host) 
dựa theo kỹ thuật VLSM gồm các thông tin: 
- Địa chỉ mạng con (Network ID) 
- Subnet Mask của mạng con 
- Dải địa chỉ host của mỗi mạng con 
- Địa chỉ Broadcast 
- Diệp hoàng bảo bảo 
49 thanhhoa48dhv@gmal.com