So sánh thuật toán spf (ospf), dual (eigrp) và thuật toán chọn đường của bgp

[admin]

SO SÁNH THUẬT TOÁN SPF (OSPF), DUAL (EIGRP) VÀ THUẬT TOÁN CHỌN ĐƯỜNG CỦA BGP

Chào mọi người trong diễn đàn! Hôm nay mình muốn chia sẻ một chủ đề thú vị: so sánh các thuật toán định tuyến cốt lõi của ba giao thức phổ biến: SPF trong OSPF, DUAL trong EIGRP, và thuật toán chọn đường của BGP. Mỗi giao thức có cách tiếp cận riêng để tìm đường đi tối ưu trong mạng, và việc hiểu rõ sự khác biệt sẽ giúp chúng ta áp dụng hiệu quả trong các kịch bản thực tế. Hãy cùng phân tích chi tiết nhé!

---

1. SPF (Shortest Path First) của OSPF
Tổng Quan
OSPF (Open Shortest Path First) là một giao thức định tuyến trạng thái liên kết (link-state), sử dụng thuật toán SPF (hay còn gọi là thuật toán Dijkstra) để tính toán đường đi ngắn nhất từ router hiện tại đến tất cả các đích trong mạng.
Cách Hoạt Động

1. Thu Thập Thông Tin:
   • Mỗi router trong OSPF xây dựng một Link-State Database (LSDB) bằng cách trao đổi các Link-State Advertisement (LSA) với các router khác.
   • LSDB chứa thông tin về trạng thái liên kết (link-state) của toàn mạng, bao gồm tất cả router, liên kết, và chi phí (cost) của các liên kết.
2. Tính Toán Đường Đi:
   • SPF sử dụng LSDB để xây dựng một cây đường đi ngắn nhất (SPF Tree) với router hiện tại là gốc.
   • Chi phí (cost) của mỗi liên kết được tính dựa trên băng thông:

Cost = Reference Bandwidth / Interface Bandwidth
(Mặc định: Reference Bandwidth = 10^8 bps = 100 Mbps. Ví dụ: Giao diện 1 Gbps → Cost = 100,000,000 / 1,000,000,000 = 0.1, nhưng OSPF làm tròn lên thành 1).

1. • Thuật toán Dijkstra đảm bảo tìm đường đi có tổng cost nhỏ nhất đến đích.
2. Cập Nhật Bảng Định Tuyến:
   • Sau khi xây dựng SPF Tree, router chọn đường đi ngắn nhất đến từng đích và cập nhật vào bảng định tuyến (Routing Table).

Đặc Điểm Chính

• Hội Tụ: Hội tụ nhanh trong mạng nhỏ đến trung bình (thường vài giây), nhưng chậm hơn trong mạng lớn do tính toán SPF phức tạp.
• Không Vòng Lặp: LSDB đồng bộ trên toàn mạng đảm bảo không vòng lặp.
• Tài Nguyên: Yêu cầu CPU và bộ nhớ cao để duy trì LSDB và tính toán SPF, đặc biệt khi mạng lớn.
• Metric: Dựa trên cost (băng thông), không hỗ trợ các yếu tố khác như độ trễ, tải, hoặc độ tin cậy.
• Cân Bằng Tải: Hỗ trợ cân bằng tải chi phí bằng nhau (ECMP), nhưng không hỗ trợ chi phí không bằng nhau.
• Phạm Vi Áp Dụng: Thích hợp cho mạng nội bộ (IGP), hỗ trợ phân vùng (area) để mở rộng.

Ưu Điểm

• Hỗ trợ tốt cho mạng lớn nhờ cơ chế phân vùng (area).
• Định tuyến chính xác dựa trên trạng thái liên kết toàn mạng.
• Chuẩn mở (open standard), tương thích đa nhà cung cấp.

Nhược Điểm

• Tính toán SPF tiêu tốn tài nguyên CPU, đặc biệt khi mạng có nhiều thay đổi.
• Yêu cầu cấu hình cẩn thận để tránh bất đồng bộ LSDB.
• Không hỗ trợ cân bằng tải chi phí không bằng nhau.

---

2. DUAL (Diffusing Update Algorithm) của EIGRP
Tổng Quan
EIGRP (Enhanced Interior Gateway Routing Protocol) là một giao thức định tuyến lai (hybrid), sử dụng thuật toán DUAL để tìm đường đi tối ưu và đảm bảo không vòng lặp. DUAL kết hợp ưu điểm của giao thức vectơ khoảng cách và trạng thái liên kết.
Cách Hoạt Động

1. Thu Thập Thông Tin:
   • EIGRP xây dựng Neighbor Table (danh sách láng giềng) qua gói Hello.
   • Láng giềng trao đổi thông tin định tuyến qua gói Update, lưu vào Topology Table, chứa tất cả đường đi đến đích.
2. Tính Toán Đường Đi:
   • DUAL chọn Successor (đường đi tốt nhất, có Feasible Distance - FD nhỏ nhất) để đưa vào bảng định tuyến.
   • Feasible Successor (FS) là đường dự phòng, thỏa mãn Feasibility Condition (FC): AD (Advertised Distance) của FS < FD hiện tại.
   • Metric được tính dựa trên băng thông và độ trễ (có thể thêm tải, độ tin cậy):

Metric = 256 * [(10^7 / min_bandwidth) + (total_delay / 10)]
(Mặc định: K1 = K3 = 1, các K khác = 0).

1. • EIGRP hỗ trợ wide metrics cho giao diện tốc độ cao, đo độ trễ bằng picosecond và nhân với 65,535.
2. Xử Lý Mất Tuyến:
   • Nếu mất Successor:
     • Có FS: Chuyển ngay sang FS (Local Computation), hội tụ rất nhanh (dưới 1 giây).
     • Không Có FS: Chuyển tuyến sang trạng thái Active, gửi Query lan tỏa để hỏi đường thay thế, nhận Reply để cập nhật.

Đặc Điểm Chính

• Hội Tụ: Cực nhanh nhờ FS, thường dưới 1 giây nếu có đường dự phòng.
• Không Vòng Lặp: FC và cơ chế Query/Reply đảm bảo không vòng lặp.
• Tài Nguyên: Tiết kiệm CPU hơn OSPF, chỉ gửi partial update và Query khi cần.
• Metric: Linh hoạt, dùng băng thông, độ trễ, và có thể tùy chỉnh thêm tải, độ tin cậy.
• Cân Bằng Tải: Hỗ trợ cả chi phí bằng nhau (ECMP) và không bằng nhau (dùng variance).
• Phạm Vi Áp Dụng: IGP, phù hợp cho mạng doanh nghiệp, nhưng không hỗ trợ phân vùng phức tạp như OSPF.

Ưu Điểm

• Hội tụ nhanh nhờ FS và Local Computation.
• Hỗ trợ cân bằng tải chi phí không bằng nhau, tối ưu lưu lượng.
• Tiết kiệm tài nguyên với partial update và Query scoping.

Nhược Điểm

• Là giao thức độc quyền của Cisco (tuy nhiên, từ 2013 Cisco đã mở một phần).
• Không hỗ trợ phân vùng phức tạp như OSPF, có thể gặp khó khăn trong mạng rất lớn.
• Nguy cơ Stuck-in-Active (SIA) nếu Query không được trả lời kịp thời.

---

3. Thuật Toán Chọn Đường của BGP
Tổng Quan
BGP (Border Gateway Protocol) là một giao thức định tuyến vectơ đường đi (path-vector), sử dụng thuật toán chọn đường dựa trên chính sách (policy-based) thay vì số liệu đơn thuần như OSPF hay EIGRP. BGP được thiết kế cho định tuyến liên miền (EGP), thường dùng giữa các hệ thống tự trị (AS).
Cách Hoạt Động

1. Thu Thập Thông Tin:
   • BGP trao đổi thông tin định tuyến qua Update messages, chứa các tiền tố (prefix) và thuộc tính đường đi (path attributes) như AS Path, Next-Hop, Local Preference, v.v.
   • Mỗi router lưu các tuyến vào BGP Table (RIB - Routing Information Base).
2. Thuật Toán Chọn Đường (Path Selection):
   • BGP không dùng metric kiểu băng thông hay độ trễ, mà chọn đường đi dựa trên một loạt thuộc tính (attributes) theo thứ tự ưu tiên:
     1. Highest Weight (Cisco-specific, ưu tiên cao nhất, mặc định 0).
     2. Highest Local Preference: Giá trị cao hơn được ưu tiên (mặc định 100), dùng trong cùng AS.
     3. Locally Originated: Ưu tiên tuyến do router này khởi tạo.
     4. Shortest AS Path: Chọn đường có ít AS đi qua nhất.
     5. Lowest Origin Type: Ưu tiên IGP > EGP > Incomplete.
     6. Lowest MED (Multi-Exit Discriminator): So sánh khi nhận tuyến từ cùng AS.
     7. eBGP over iBGP: Ưu tiên tuyến từ eBGP hơn iBGP.
     8. Lowest IGP Metric to Next-Hop: Nếu vẫn hòa, chọn đường có IGP metric thấp nhất đến Next-Hop.
     9. Oldest Route: Chọn tuyến lâu đời hơn (ổn định hơn).
     10. Lowest Router ID: Chọn router có Router ID nhỏ nhất.
     11. Lowest Neighbor IP: Nếu vẫn hòa, chọn router có địa chỉ IP láng giềng nhỏ nhất.
   • Sau khi chọn đường tốt nhất (best path), tuyến được cài vào bảng định tuyến.
3. Cập Nhật và Hội Tụ:
   • BGP không hội tụ nhanh như OSPF hay EIGRP, vì phải xử lý nhiều thuộc tính và chính sách.
   • Khi mạng thay đổi, BGP gửi Update để cập nhật, nhưng không tính toán lại toàn bộ như SPF.

Đặc Điểm Chính

• Hội Tụ: Chậm, có thể mất vài phút, đặc biệt trong mạng lớn như Internet.
• Không Vòng Lặp: Đảm bảo không vòng lặp nhờ thuộc tính AS Path (không chấp nhận tuyến có AS của mình trong AS Path).
• Tài Nguyên: Tiêu tốn bộ nhớ lớn để lưu BGP Table (hàng triệu tuyến trên Internet), nhưng ít tốn CPU hơn SPF.
• Metric: Dựa trên thuộc tính và chính sách, không dùng số liệu băng thông/độ trễ.
• Cân Bằng Tải: Chỉ hỗ trợ ECMP (chi phí bằng nhau) theo mặc định, nhưng có thể tùy chỉnh qua chính sách.
• Phạm Vi Áp Dụng: EGP, dùng cho định tuyến liên miền, đặc biệt trên Internet.

Ưu Điểm

• Linh hoạt cao, dễ áp dụng chính sách định tuyến (dựa trên Local Preference, MED, AS Path Prepending, v.v.).
• Mở rộng tốt, xử lý hàng triệu tuyến trên Internet.
• Hỗ trợ định tuyến liên miền phức tạp.

Nhược Điểm

• Hội tụ chậm, không phù hợp cho mạng nội bộ cần phản hồi nhanh.
• Phức tạp trong cấu hình và quản lý chính sách.
• Dễ bị ảnh hưởng bởi chính sách sai, dẫn đến định tuyến không tối ưu.

---

4. So Sánh Tổng Quan

Tiêu Chí	SPF (OSPF)	DUAL (EIGRP)	BGP Path Selection
Loại Giao Thức	Link-State	Hybrid (Distance Vector + Link-State)	Path-Vector
Hội Tụ	Nhanh (vài giây)	Rất nhanh (dưới 1 giây nếu có FS)	Chậm (vài phút)
Không Vòng Lặp	Đảm bảo (LSDB đồng bộ)	Đảm bảo (FC, Query/Reply)	Đảm bảo (AS Path)
Metric	Cost (dựa trên băng thông)	Linh hoạt (băng thông, độ trễ, tải, độ tin cậy)	Thuộc tính (Local Preference, AS Path, MED, v.v.)
Tài Nguyên	Tốn CPU, bộ nhớ (LSDB, SPF)	Tiết kiệm CPU, bộ nhớ vừa phải	Tốn bộ nhớ (BGP Table lớn), ít CPU
Cân Bằng Tải	ECMP (chi phí bằng nhau)	ECMP + Unequal-Cost (dùng variance)	ECMP, tùy chỉnh qua chính sách
Phạm Vi Áp Dụng	IGP (mạng nội bộ)	IGP (mạng nội bộ)	EGP (mạng liên miền, Internet)
Mở Rộng	Tốt (phân vùng area)	Hạn chế (không hỗ trợ phân vùng phức tạp)	Rất tốt (xử lý hàng triệu tuyến)
Chính Sách	Ít linh hoạt	Hạn chế (dùng metric điều chỉnh)	Rất linh hoạt (dựa trên thuộc tính)

---

5. Ứng Dụng Thực Tế

• OSPF (SPF): Thích hợp cho mạng nội bộ (doanh nghiệp, ISP nội bộ) cần hội tụ nhanh và định tuyến chính xác. Ví dụ: Mạng doanh nghiệp với nhiều chi nhánh, cần phân vùng để mở rộng.
• EIGRP (DUAL): Phù hợp cho mạng doanh nghiệp vừa và nhỏ, cần hội tụ nhanh và cân bằng tải linh hoạt. Ví dụ: Mạng nội bộ của công ty sử dụng thiết bị Cisco.
• BGP: Dùng cho định tuyến liên miền, đặc biệt trên Internet hoặc giữa các ISP. Ví dụ: Kết nối giữa các AS, định tuyến chính sách giữa nhà cung cấp dịch vụ.

---

6. Kết Luận
Việc lựa chọn giao thức định tuyến không chỉ phụ thuộc vào khả năng hội tụ hay tài nguyên tiêu thụ, mà còn liên quan đến phạm vi ứng dụng, yêu cầu chính sách định tuyến, và đặc điểm của hệ thống mạng.

• OSPF (SPF) nổi bật với tính chuẩn mở, phù hợp cho môi trường mạng doanh nghiệp quy mô lớn nhờ khả năng phân chia area và định tuyến chính xác dựa trên trạng thái liên kết.
• EIGRP (DUAL) là lựa chọn tối ưu cho các mạng nội bộ dùng thiết bị Cisco, nhờ khả năng hội tụ cực nhanh, hỗ trợ cân bằng tải không bằng nhau, và tiết kiệm tài nguyên.
• BGP là xương sống của Internet – mặc dù hội tụ chậm nhưng lại cực kỳ linh hoạt và mạnh mẽ cho các hệ thống lớn với nhiều chính sách định tuyến phức tạp.

👉 Mỗi giao thức đều có điểm mạnh – điểm yếu riêng. Khi thiết kế hệ thống mạng, bạn cần cân nhắc mục tiêu triển khai, mức độ phức tạp, và yêu cầu thực tế để chọn giải pháp phù hợp nhất.