1
Định Tuyến Động, Thuật Toán
Định Tuyến ,OSPF và RIP
Sinh viên thực hiện: Nguyễn Văn Chung
Hoàng Thế Doanh
Phan Thị Thu
Nội Dung Chính
 Định tuyến động.
 Thuật toán định tuyến.
 OSPF và RIP.
2
Định Tuyến Động
1. Khái niệm định tuyến thông tin.
2. Sự khác nhau giữa định tuyến tĩnh và định
tuyến động.
3. Các hoạt động định tuyến động.
4. Khái niệm bảng định tuyến.
5. Các giao thức định tuyến.
6. Hệ thống tự quản Autonomous system.
1. Khái niệm định tuyến thông tin
 Định tuyến là quá trình xác định một tuyến
đường tốt nhất giữa hai nút bất kì.
3
 Định tuyến tĩnh: Là dùng một tuyến đã được lập
trình do người quản trị mạng nhập vào router.
 Định tuyến động: Là một tuyến mà giao thức định
tuyến mạng điều chỉnh một cách tự động phù hợp
topo hay các thay đổi của lưu lượng.
Î Định tuyến động linh hoạt hơn định tuyến tĩnh .
2. Sự khác nhau giữa định tuyến động
và định tuyến tĩnh:

¾ Bảng định tuyến IP
¾ Distance-vector.
¾ Link - state.
¾ Balance hybrid.
5. Các loại giao thức định tuyến:
7
¾ Một hệ thống tự trị bao gồm các router chịu sự
quản lý chung.
6. Hệ thống tự trị autonomous system:
¾ Các giao thức định tuyến exterior được dùng để
truyền thông tin giữa các hệ thống tự trị.
¾ Các giao thức interior được dùng bên trong hệ thống
tự trị.
¾ Các giao thức định tuyến IP bên trong bao gồm:
9 RIP (Routing Information Protocol)
9 IGRP (Interior GateWay Routing Protocol)]
9 OSPF (Open Shortest Path First )
9 EIGRP (Enhanced Interior Gateway
Protocol)
8
Thuật Toán Định Tuyến
1. Thuật toán distance-vector.
2. Thuật toán link-state.
3. Thuật toán Dijkstra.
¾ Định tuyến distance-vector xác định hướng và
khoảng cách đối với bất kì liên kết nào trong
mạng.
¾ Chúng định kỳ chuyển các bản copy của bảng
định tuyến từ router này đến router khác và
tích lũy các vector khoảng cách.

-Khắc phục:
• Định nghĩa giới hạn tối đa.
• Dùng các bộ định thời khống chế.
11
o Lặp:
Tiếp tục thực hiện thuật toán cho tới khi không
còn thông tin trao đổi trên mạng
o Đồng bộ :
Các node trao đổi thông tin không đồng bộ.
o Sự phân tán:
Mỗi một node chỉ liên kết với các node lân cận trực
tiếp với nó.Do đó quá trình định tuyến phân tán trên
mạng.
Có 3 đặc điểm quan trọng định tuyến
distance-vector:
 Đặc điểm:
¾ Thuật toán định tuyến theo trạng thái đường
liên kết xây dựng và duy trì một cơ sở dữ liệu
phức tạp về cấu trúc hệ thống mạng bằng cách
trao đổi các gói LSAs với tất cả các router khác
trong mạng.
¾ Chúng là một tập hợp các giao thức SPF.
¾ Chúng dựa trên thuật toán Dijkstra.
2. Thuật toán định tuyến link-state:
12
1C192.168.33.0D
1B192.168.66.0D
2C10.0.0.0D
2B10.0.0.0D
1D192.168.157.0C

14
¾ Nhược điểm:
 Cần dung lượng bộ nhớ lớn và năng lực xử lý cao.
 Chúng đòi hỏi hệ thống mạng phải được thiết kế theo
mô hình phân cấp, hệ thống mạng được chia ra nhiều
vùng nhỏ để làm giảm bớt độ lớn và độ phức tạp của
cơ sở dữ liệu về cấu trúc hệ thống mạng.
 Chúng đòi hỏi nhà quản lý phải nắm vững giao thức.
 Trong quá trình khởi động ,các router thu thập thông
tin về cấu trúc hệ thống mạng để xây dựng cơ sở dữ
liệu, chúng phát các gói LSA trên toàn mạng làm cho
dung lượng đường truyền dành cho dữ liệu khác giảm.
¾ Coi hệ thống mạng là một tập hợp các node được
kết nối với nhau bằng kết nối điểm-đến-điểm.
¾ Mỗi kết nối có một chi phí.
¾ Mỗi node chứa đầy đủ thông tin về cấu trúc vật lý
của hệ thống mạng.
3. Thuật toán Dijkstra:
15
 Mô tả thuật toán:
 Thiết lập:
- dii = 0;
- Dij = ∞ nếu I và j không liên kết với nhau.
- Để tìm đường đi ngắn nhất ta dựa vao công
thức.
Dx(y,z) =C(x,z) + min{Dz(y,w)}
Trong đó Dx(y,z) là khoảng cách từ x đến y
thông qua node z.
C(x,z) chi phí liên kết từ node x tới z.
16

18
3.3 Giải quyết vấn đề đếm đến vô hạn
Giải quyết đếm đến vô hạn bằng cách:
1. Sử dụng kỹ thuật có tên là split horizon
update.
2. Theo phơng diện luồng thông tin.
3. Sử dụng biến hold down.
4. Poison reverse.
3.4 Định dạng thông điệp RIP1
Có hai loại thông điệp RIP: các thông điệp RIP về
thông tin định tuyến và các thông điệp đợc sử
dụng để yêu cầu về thông tin. Cả hai đều sử dụng
một định dạng bao gồm một phần đầu cố định, tiếp
theo sau là một danh sách tuỳ chọn về mạng và
khoảng cách.
Hình vẽ sau trình bày định dạng thông điệp đợc
sử dụng trong RIP1
19
3.4 Định dạng thông điệp RIP1

DISTANCE TO NET 2
MUST BE ZERO
MUST BE ZERO
IP ADDRESS OF NET 2
MUST BE ZERO FAMILY OF NET 2
DISTANCE TO NET 1
MUST BE ZERO
MUST BE ZERO
IP ADDRESS OF NET 1
MUST BE ZEROFAMILY OF NET 1

định tuyến và vấn đề đếm đến vô hạn
RIP2 hoàn thiện đợc việc tránh lỗi
21
3.8 Định dạng thông điệp RIP2
Distance to net 1
Next hop for net 1
Subnet mask for net 1
Ip address of net 1
Route tag for net1Family of net 1
Must be zeroVersion
(1)
Command (1-
5)

Distance to net 2
Next hop for net 2
Subnet mask for net 2
Ip address of net 2
Route tag for net 2Family of net 2
3.9 Việc truyền các thông điệp RIP
Các thông điệp RIP không chứa vùng độ dài
tờng minh và cũng không chứa tờng minh
biến đếm các mục
Khi đợc sử dụng với TCP/IP, các thông
điệp RIP dựa vào UDP để thông báo cho nơi
nhận độ dài của thông điệp RIP hoạt động
trên cổng số 520 của UDP