1
Định tuyến động, các thuật toán định
tuyến, giao thức RIP và OSPF
Thành viên: Hoàng TuấnMinh
Trần ĐứcHiếu
TrầnMạnh Hà
Điệntử 5 – K48
MụcLục
•1. Định tuyến và các khái niệmcơ bản
•2. Định tuyến động
•3. Cácthuật toán định tuyến
• 4. Giao thứcRIP
• 5. Giao thức OSPF
•6. Lờicảm ơn
2
1. Định tuyến và các khái niệmcơ bản
Mô hình mạng Internet :
-Các mạng đơn (sử dụng gửi gói trực tiếp)
-Kết nối liên mạng tạo thành đám mây mạng (sử dụng
gửi gói gián tiếp)
1. Định tuyến và các khái niệmcơ bản
• Định nghĩa định tuyến: làhoạt động mạng nhằmxác
định 1 tuyến đường tốtnhất để truyềndữ liệulênđó.
•Thiếtbị thựchiệnhoạt động đó là các router (bộđịnh
tuyến)
3
1.Định tuyến và các khái niệmcơ bản
1.Định tuyến và các khái niệmcơ bản
Định tuyếnsử dụng bảng định tuyến:
•Lưu thông tin về các đích đếncóthể và làm thế nào để
đến đó.

6
2. Định tuyến động
2. Định tuyến động
Định tuyến động (Dynamic routing):
• Trong định tuyến động, bảng định tuyến không được
định nghĩasẵntấtcả các đích đếnnhưđịnh tuyếntĩnh.
• Các nút mạng phảitự xác định được đường đitối ưubất
kì mà không cầnphải đặtcấuhìnhtừ bên ngoài.
•Khimộtkếtnốibị trụctrặc các nút tự tìm ra đường tối ưu
mới không cầncósự can thiệptừ bên ngoài.
•Như vậy trong định tuyến động các nút mạng cầnphải
có cơ chếđểtrao đổi thông tin định tuyến giữa các nút
mạng để đánh giá đượctuyến đường đitốtnhất
7
2. Định tuyến động
3. Các thuậttoánđịnh tuyến
•Mục đích cuối cùng củahoạt động định tuyếnlàđể tìm
ra đường đigiữa 2 nút bấtkìvới chi phí nhỏ nhất.
8
3. Các thuậttoánđịnh tuyến
Mô hình toán họccủamạng
• Các nút
•Cáccạnh
• Metric
A
C
B
E
D
F

SPT (Shortest Path Tree)
•Tấtcả các thuậttoántìmđường đingắnnhất đềudựavàocácnhận
xét đượcminhhọa trong hình dưới đây. Đólàviệclồng nhau giữa
các đường đingắnnhất. Một nút k thuộc đường đingắnnhấttừ i tới
j sẽ bằng đường đingắnnhấttừ i tớik cộng với đường đingắnnhất
từ k tớij. Do vậycóthể
tìm được đường đingắnnhấtgiữa2 nút
theo công thức đệ qui sau
Djj= mink(dik + djk)
•Dxylàđộ dài của đường đingắnnhấttừ x tớiy. Khókhăncủacách
tiếpcận này là phảicómộtcáchkhởi động đệ qui nào đó vì chúng
ta không thể khởi động vớicácgiátrị bấtkìở vế phảicủaphương
trình. Có nhiềucácđể thựchiệnviệcnày, mỗicáchlàcơ sở cho
mộtthuậ
t toán khác nhau.
10
3. Các thuậttoánđịnh tuyến
Lưu đồ thuật toán của
Dijkstra
3. Các thuậttoánđịnh tuyến
VD: tìm đường đi ngắn nhất từ A
đến E
1. Nút gốc A được chọn làm nút
đầu tiên được quét (trên hình
vẽ là hình tròn tô đen)
2. Tại bước này, giá trị trạng thái
các nút B,C bị thay đôi. B có giá
trị nhỏ hơn được chọn làm nút
quét tiếp theo
11

2
5
Link state and distance vector
Distance-Vector Protocols (RIP, IGRP):
• – Thu nhận thông tin về mạng thông qua các router lân
cận.
• –Thêm 1 vào vector khoảng cách giữa các router với
nhau.
•–Cập nhật định kỳ.
• – Trao đổi các bản sao của bảng định tuyến với các
router lân cận.
13
Link state and distance vector
• Distance vector routing
Link state and distance vector
• Ưu điểm:
–Ít tốn tài nguyên hệ thống
•Nhược điểm:
– Router thu thập thông tin về khoảng cách đến các
mạng khác, từ đónóxây dựng và bảo trì một cơ sở
dữ liệu về thông tin định tuyến trong mạng. Tuy nhiên
hoạt động theo thuật toán vector khoảng cách như
vậy thì sẽ không biết chính xác cấu trúc của toàn bộ
hệ thống mạng, mà chỉ biết được các router láng
giềng kết nối trực tiếp với nó.
–Tốc độ đồng bộ chậm
14
Link state and distance vector
Link State Protocols (OSPF, IS -IS):
• – Thu nhận thông tin chung về trạng thái của toàn bộ

•a. Định nghĩa
•b. Phiênbản
•c. Hoạt động
• d. Cách khắcphụchiệntượng LOOP
16
4. RIP (Routing Information Protocol )
•a. Định nghĩa:
– RIP là 1 giao thức định tuyến Distance vector sử
dụng số hop làm metric để xác định hướng và
khoảng cách cho bấtkỳ một liên kết nào trong liên
mạng, được mô tả trong tiêu chuẩn RFC 1058 vào
năm 1988
•b. Phiênbản:
– RIP v1:yêu cầutấtcả các thiếtbị trên 1 mạng sủ
dụng cùng 1 subnet mask,vì nó không chứa thông tin
subnet mask trong các cậpnhật định tuyến->Classful
Routing
– RIP v2:mang thông tin subnet mask trong bảntin định
tuyến
4. RIP (Routing Information Protocol )
17
4.RIP (Routing Information Protocol )
•c. Hoạt động:
– Message Rip có trường command
=1: RIP Request
=2: RIP Reply
– Ban đầugửi Request packet cho mỗigiaodiện để
yêu cầu các giao diện đógửi cho nó đầy đủ bảng
định tuyếncủa các Router khác
– Khi RIP Request đượcnhận, bảng định tuyến được

• Không cho phép 1
Router cậpnhậtlại
những thông tin mà
nó đãgửi cho 1
Router khác quay
trở lại Router đấy
4.RIP (Routing Information Protocol)
– Poision Reverse:
• Routing Protocol
cho phép Loop
xảyrachođến
khi metric vượt
quá 16
20
4.RIP (Routing Information Protocol)
– Thời gian Holddown:
• Thời gian Holddown mặc định của RIP là 180s.
• Giúp router tránh bị vòng lặp đếm đến vô hạn
nhưng lại làm tăng thời gian hội tụ giữa các router
4.RIP (Routing Information Protocol)
• Cập nhật tức thời (Trigered updates):
21
5. Giao thức OSPF
• a. Định nghĩa
• b. Đặc điểm
• c. Đặc điểm so với RIP
• d. Các bước trong hoạt động của OSPF
• e. Các loại mạng trong OSPF
5. Giao thức OSPF
• a. Định nghĩa:

23
5. Giao thức OSPF
•d. Các bước trong hoạt động của OSPF
–Thiết lập quan hệ liền kề giữa các router
(Establishing a router Adjacency)
5. Giao thức OSPF
–Lựa chọn DR và BDR (Electing a DR and
BDR)
24
5. Giao thức OSPF
–Chọn đường đi ngắn nhất (Selecting the best
route)
5. Giao thức OSPF
–Lưu trữ thông tin định tuyến (Maintaining
route information)
25
5. Giao thức OSPF
5. Giao thức OSPF
•e. Các loại mạng trong OSPF
– Broadcast multiaccess
– Point to point
– Nonbroadcast multiaccess
– Point to multipoint