ĐẠI HỌC KHOA HỌC - HUẾ
BỘ MÔN ĐIỆN TỬ VIỄN THÔNG
Nhóm 12:
Nguyễn Ngọc Thanh
Lê Hồng Việt
Nguyễn Đình Hoàng Nam
Phạm Gia Lương
Lê Trần Quốc Đạt
1
BÀI BÁO CÁO
A. GIỚI THIỆU CHUNG
1. Khái niệm:
Định tuyến là quá trình lựa chọn đường đi trên mạng để gửi dữ liệu.
2. Chức Năng Định Tuyến:
Định tuyến giúp chỉ ra hướng và đường đi tốt nhất từ nguồn đến
đích thông qua các node trung gian là các router
3. Phân loại:
Gồm có 2 loại:
1) Định tuyến động : là định tuyến mà có trạng thái đường
đi (link State) thay đổi liên tục, được các router cập nhật
liên tục do đó mang tính linh động cao
2) Định tuyến tĩnh: đường đi là cố định khi có thay đổi
trong mạng thì phải cấu hình lại. Chỉ phù hợp với mạng
nhỏ.
• Định Tuyến:
Hiện tại trong môi trường internet tồn tại Các kiểu định tuyến động
như : RIP, IGRP, EIGRP, OSPF,ISIS, BGP các kiểu định tuyến này
sử dụng các thuật toán tìm đường khác nhau chia thành hai nhóm sau:

• Ở mỗi bước thì router sẽ ở các trạng thái khác nhau, gồm các trạng thái
sau :
- Down: là trạng thái không liên lạc với các router khác.
- Init: trạng thái thiết lập nhưng chỉ theo một chiều từ router gửi.
- 2-way: trạng thái thiết lập theo hai chiều
- Exstart: thiết lập quan hệ Master/slave bằng cách trao đổi
database description(dd) packet. Router có router ID cao nhất sẽ
là master.
3
- Exchange: thông tin định tuyến sẽ đươc trao đổi qua dd và
lsr(link state request)
- Loading : quá trình cập nhật thông tin LSA được bắt đầu khi LSR
được gửi đến Neghibor
- Full : tất cả các LSA đã đươc đồng bộ giữa các Adjacency.
1. BÌNH CHỌN ROUTER ID:
• Đầu tiên, khi một router chạy OSPF, nó phải chỉ ra một giá trị dùng để
định danh duy nhất cho nó trong cộng đồng các router chạy OSPF. Giá
trị này được gọi là Router – id.
• Router – id trên router chạy OSPF có định dạng của một địa chỉ IP.
Mặc định, tiến trình OSPF trên mỗi router sẽ tự động bầu chọn giá trị
router – id là địa chỉ IP cao nhất trong các interface đang active, nhưng
nó ưu tiên cổng loopback.
- Ta cùng làm rõ ý này thông qua ví dụ:
• Chỉ địa chỉ của các interface đang active, tức là ở trạng thái up/up
(status up, line protocol up) mới được tham gia bầu chọn. Ta thấy trên
hình , chỉ có hai cổng F0/0 và F0/1 của R là up/up nên router R sẽ chỉ
xem xét hai địa chỉ trên hai cổng này là 192.168.1.1 và 192.168.2.1
• Để xác định trong hai địa chỉ này, địa chỉ nào là cao hơn, R tiến hành
so sánh hai địa chỉ này theo từng octet từ trái sang phải, địa chỉ nào có
octet đầu tiên lớn hơn được xem là lớn hơn

tin sau bắt buộc phải match với nhau trên hai router để chúng có thể
thiết lập được quan hệ láng giềng với nhau.
• Hello Packet:
- Area – id
- Hello timer và Dead timer
- Hai địa chỉ IP đấu nối phải cùng subnet
- Thỏa mãn các điều kiện xác thực.
- Cùng bật hoặc cùng tắt cờ stub
3. TRAO ĐỔI LSDB ( link state database)
LSDB – Link State Database – Bảng cơ sở dữ liệu trạng thái đường link là
một bảng trên router ghi nhớ mọi trạng thái đường link của mọi router trong
vùng. Ta xem LSDB như là một “tấm bản đồ mạng” mà router sẽ căn cứ vào
đó để tính toán định tuyến
• Đặc điểm :
- LSDB phải hoàn toàn giống nhau giữa các router cùng vùng
6
- LSDB được chia nhỏ ra thành những đơn vị thông tin LSA (link
state advertisment) các đơn vị thông tin này lại chưa trong một
gói tin cụ thể gọi là LSU(link state update)
- Việc trao đổi thông tin diễn ra rất khác nhau tùy theo từng loại
network – type gán cho link giữa hai router, ta sẽ nói qua 2 loại
network sử dụng trong OSPF là: point to point, và
multibroadcast.
• Point to point : Loại link point – to – point điển hình là kết nối serial
điểm – điểm chạy giao thức HDLC hoặc PPP nối giữa hai router. hai
router láng giềng sẽ ngay lập tức gửi toàn bộ bảng LSDB cho nhau qua
kết nối point – to – point và chuyển trạng thái quan hệ từ 2 – WAY
sang một mức độ mới gọi là quan hệ dạng FULL

• Broadcast multiacess: Với môi trường này, mỗi router đều kết nối trực

9
 Xét ví dụ :
• Yêu cầu đặt ra với sơ đồ trên là tính path – cost (metric) cho đường đi
từ R1 đến mạng 192.168.3.0/24 của R3.
• Nguyên tắc cộng cost : Để tính tổng cost từ một router đến một mạng
đích theo một đường (path) nào đó, ta thực hiện lần ngược từ đích lần
về và cộng dồn cost theo quy tắc đi vào thì cộng, đi ra thì không cộng.
áp dụng cho ví dụ trên
Bạn nào có thể tính giúp mình giá trị này ?
• Thuật toán SPF tiến hành tính toán đòi hỏi một khoảng thời gian thời
gian này phụ thuộc vào tính chất của vùng (số router, độ lớn của dữ
liệu………….).
• OSPF sử dụng thuật toán Dijkstra để tìm SPF. Thuật toán như sau :. )
• Giả sử ta có U0 là điểm nguồn ta cân xác định tuần tự khoảng cách của
các điểm khác đến UO từ nhỏ đến lớn . gọi V là tập chứa tất cả các
điểm có liên kết nhau.
- Trước tiên điểm có khoảng cách nhỏ nhất đến U0 là U0 hay chính
nó.
- Trong tập V\{U0} tìm điểm có khoảng cách đến U0 nhỏ nhất( điểm
này phải là điểm kề với U0) giả sử là điểm U1.
- Trong V\{U0,U1} tìm điểm có khoảng cách đến U0 nhỏ
nhất( điểm này phải kề với U0 hoắc U1) giả sử đó là U2
- Tiếp tục như vậy cho đến khi nào tìm được khoảng cách từ U0 đến
mọi đỉnh.
 chú ý : Từ nguồn tới chính nó thì khoảng cách =0
10
Nếu có các nút kề với các nút đã liệt kê trong danh sach thì tính
xem khoảng cách là bao nhiêu rồi sau đó chọn đường ngắn nhất, nếu
không có thì xem như bằng vô cùng
Giả sử các khoảng cách như sau :