Thạc Sĩ Các cơ chế định tuyến QoS và thuật toán mở đường ngắn nhất đầu tiên (OSPF) mở rộng

MỤC LỤC
MỞ ĐẦU . 1
CHƯƠNG 1 - TỔNG QUAN VỀ ĐỊNH TUYẾN QoS 3
1.1. Giới thiệu định tuyến dựa trên QoS 3
1.1.1. Định tuyến 3
1.1.2. Định tuyến dựa trên QoS 5
1.1.3. Mục đích của định tuyến dựa trên QoS . 7
1.2. Các vấn đề cơ bản của định tuyến dựa trên QoS . 8
1.2.1. Metric và sự tính toán đường đi 8
1.2.2. Lan truyền và duy trì thông tin . 9
1.2.3. Mô hình thông tin trạng thái không chính xác 10
1.2.4. Điều khiển của quản trị mạng . 11
1.2.5. Vấn đề thuật toán trong định tuyến dựa trên QoS. 11
1.2.6. Vấn đề động trong định tuyến dựa trên QoS . 15
1.3. Kỹ thuật OSPF và vấn đề mở rộng OSPF cho định tuyến QoS . 17
1.3.1. Kỹ thuật OSPF . 17
1.3.2. Độ tin cậy trong định tuyến dựa trên QoS . 21
1.3.3. Đặt vấn đề nghiên cứu thuật toán OSPF mở rộng . 22
CHƯƠNG 2 – CƠ BẢN VỀ CÁC CƠ CHẾ ĐỊNH TUYẾN QoS [2] 25
2.1. Định tuyến QoS nội miền . 25
2.1.1. Vấn đề thuật toán lựa chọn đường đi 26
2.1.2. Định tuyến đa đích . 31
2.1.3. Định tuyến liên kết riêng biệt . 33
2.1.4. Phương pháp định tuyến dựa trên dự đoán 34
2.2. Định tuyến QoS liên miền[14] 36 iii
2.2.1. Các mở rộng QoS và kỹ thuật lưu lượng sử dụng BGP . 37
2.2.2. Các phương pháp che phủ 37
2.2.3. Multihoming . 39
2.3. Bảng định tuyến . 42
2.3.1. Cơ chế trao đổi thông tin để xây dựng bảng định tuyến 44
2.3.2. Các chính sách cập nhật 44
2.3.3. Cơ chế chuyển tiếp . 46
2.3.4. Chuyển tiếp hai mức giới hạn . 49
CHƯƠNG 3 - OSPF MỞ RỘNG CHO ĐỊNH TUYẾN QoS . 51
3.1. Mở rộng đảm bảo chất lượng dịch vụ cho OSPF [7]- [12] 51
3.1.1. Các khả năng tùy chọn QoS 51
3.1.2. Mã hóa tài nguyên khi TOS mở rộng 52
3.1.3. Mã hóa băng thông . 53
3.1.4. Mã hóa trễ 55
3.2. Các cơ chế thực hiện mở rộng QoS cho OSPF 55
3.2.1. Các thuật toán và thông tin lựa chọn đường dẫn . 55
3.2.2. Thông báo thông tin trạng thái liên kết . 63
3.3. Khảo sát cơ chế chuyển tiếp trong định tuyến OSPF mở rộng cho QoS 66
3.3.1. Hiệu suất của các phiên bản không giới hạn . 68
3.3.2. Hiệu suất của các phiên bản giới hạn 72
KẾT LUẬN 75
TÀI LIỆU THAM KHẢO 76
iv

THUẬT NGỮ VIẾT TẮT

ARPANET Advanced Research Projects
Agency Network
Mạng lưới cơ quan với các đề
án nghiên cứu tiên tiến
AS Autonomous System Hệ thống tự trị
ASid Autonomous System
Identifier
Số nhận dạng hệ thống tự trị
BGP Border Gateway Protocol Giao thức cổng biên
BRP Bandwidth Restricted Path Tuyến bị giới hạn băng thông
CLM Connectionless Multicast Đa điểm không kết nối
COS Class of Service Lớp dịch vụ
DIMCRA Link-Disjoint Multiple
Constraints Routing
Algorithm
Thuật toán định tuyến đa
rằng buộc liên kết rời rạc
DVMRP Distance Vector Multicast
Routing Protocol
Giao thức định tuyến đa điểm
theo véc-tơ khoảng cách
FTP File Transfer Protocol Giao thức truyền tệp
IETE Internet Engineering Task
Force
Nhóm đặc trách kỹ thuật
internet
IP Internet Protocol Giao thức Internet
ISP Internet Service Provider Nhà cung cấp dịch vụ
Internet
ITU International
Telecommunication Union
Hiệp hội viễn thông quốc tế
LSA Link State Advertisement Thông báo trạng thái liên kết v
MAMCRA Multicast Adaptive Multiple
Constraints Routing
Algorithm
Thuật toán định tuyến đa
ràng buộc thích ứng đa điểm
MCOP Multi-Constrained Optimal
Path
Tuyến tối ưu đa ràng buộc
MCP Multi-Constrained Path Tuyến đa ràng buộc
MOSPF Multicast Open Shortest Path
First
Mở đường ngắn nhất đầu tiên
đa điểm
MP-BGP Multi-Protocol BGP BGP đa giao thức
MPLS Multiprotocol Label
Switching
Chuyển mạch nhẵn đa giao
thức
NP Non-Polynomial Không đa thức
OSPF Open Shortest Path First Mở đường ngắn nhất đầu tiên
PBR Prediction-based routing
approach
Phương pháp định tuyến dựa
trên dự đoán
PIM Protocol Independent
Multicast
Chế độ đa điểm không phụ
thuộc giao thức
PNNI Private Network – Network
Interface
Giao diện mạng - mạng cá
nhân
QoS Quality of Service Chất lượng dịch vụ
QoSR QoS-based Routing Định tuyến dựa trên Chất
lượng dịch vụ
RIS Routing Information Service Dịch vụ thông tin định tuyến
RSVP Reservation Protocol Giao thức giữ chỗ
SAMCRA Self-Adaptive Multiple
Constraints Routing
Algorithm
Thuật toán định tuyến đa
ràng buộc tự thích ứng vi
SLA Service Level Agreement Thỏa thuận mức độ dịch vụ
TOS Types of Service Kiểu dịch vụ
UMTS Universal Mobile
Telecommunications Systems
Hệ thống viễn thông di động
toàn cầu
VPN Virtual Private Network Mạng riêng ảo
WIFI Wireless Fidelity Thông tin không dây trung
thực

vii
DANH MỤC HÌNH VẼ
Hình 1.1. Định tuyến 3
Hình 1.2. Ví dụ về phương pháp định tuyến dựa trên QoS . 6
Hình 1.3. Mối quan hệ giữa ba kiểu định tuyến 6
Hình 1.4. Cấu trúc định tuyến phân cấp 13
Hình 1.5. Ví dụ về bảng định tuyến phân cấp (của A1) . 13
Hình 1.6. Đường dẫn ngắn nhất trong một sơ đồ có hướng . 15
Hình 1.7. Ví dụ mạng . 18
Hình 1.8. Bắt đầu từ router A và các LSA của nó . 18
Hình 1.9. Lựa chọn router B, và thêm các LSA của nó . 18
Hình 1.10. Lựa chọn router E, tuyến đường không tốt hơn tới router C 19
Hình 1.11. Lựa chọn router C, và thêm các LSA của nó . 19
Hình 1.12. Lựa chọn router F, và thêm các LSA của nó . 19
Hình 1.13. Lựa chọn router G, và thêm các LSA của nó . 20
Tuyến đường tốt hơn tới router D được tìm thấy 20
Hình 1.14. Lựa chọn router D . 20
Hình 1.15. Định tuyến nội miền so với định tuyến liên miền 23
Hình 2.1. Ví dụ về việc dự đoán với 2 lộ trình 35
Hình 2.2. Cơ chế chuyển tiếp gói tin tại một nút . 47
Hình 3.1. Một ví dụ mạng 67
Hình 3.2. MESH-I 68
Hình 3.3. ISP 68
Hình 3.4. Flooding không giới hạn: Quá tải trên MESH-I 69
Hình 3.5. Flooding không giới hạn: băng thông nhận vào trong MESH-I . 70
Hình 3.6. Flooding không giới hạn: Quá tải trên ISP 71 viii
Hình 3.7. Flooding không giới hạn: băng thông nhận vào trên ISP . 71
Hình 3.8. Giới hạn (L): Quá tải trên MESH-I . 72
Hình 3.9. Giới hạn (L): Băng thông nhận vào trên MESH-I . 73
Hình 3.10. Giới hạn (L): Quá tải trên ISP . 74
Hình 3.11. Giới hạn (L): Băng thông nhận vào trên ISP . 74 1
MỞ ĐẦU
Ngày nay, khi công nghệ viễn thông đang phát triển mạnh mẽ trên toàn
thế giới thì vấn đề QoS là mối quan tâm lớn nhất không chỉ của các nhà cung
cấp dịch vụ viễn thông mà của cả những khách hàng sử dụng dịch vụ. Nhằm
mục đích nâng cao chất lượng và hiệu quả của mạng thì một trong những giải
pháp được quan tâm là định tuyến đảm bảo chất lượng dịch vụ (định tuyến QoS-
QoSR). QoSR không những có vai trò làm tăng chất lượng dịch vụ mà còn có ý
nghĩa quan trọng trong việc giảm chi phí vận hành mạng, đem lại hiệu quả kinh
doanh và ý nghĩa kinh tế to lớn trên đà phát triển của mạng viễn thông.
Vấn đề định tuyến trên mạng Internet hiện nay tập trung chủ yếu vào việc
cung cấp kết nối và thường chỉ hỗ trợ dịch vụ dữ liệu “cố gắng tối đa”, với các
giao thức định tuyến dùng phương pháp định tuyến tìm đường ngắn nhất OSPF,
việc định tuyến được tối ưu dựa trên các số đo tĩnh như là số lượng các chặng và
các trọng số mang tính quản trị. Dịch vụ được cung cấp bởi những giao thức này
chỉ thích hợp cho các ứng dụng dữ liệu truyền thống mà không thích hợp cho
nhiều ứng dụng yêu cầu sự đảm bảo chặt chẽ về độ trễ và băng thông. Hơn nữa,
với sự phát triển bùng nổ của lưu lượng Internet, việc duy trì định tuyến tìm
đường ngắn nhất của Internet hiện thời dẫn đến sự phân bố mất cân đối của lưu
lượng.
Các giao thức định tuyến hiện nay được sử dụng trong các mạng IP,
không có bất kỳ nhận thức nào về nguồn tài nguyên sẵn có và yêu cầu. Điều này
có nghĩa là luồng lưu lượng thường được định tuyến qua các tuyến đường không
có khả năng hỗ trợ các yêu cầu của chúng, trong khi các tuyến đường kế tiếp
nhau với đủ các nguồn tài nguyên có sẵn. Điều này có thể dẫn đến suy giảm
đáng kể về hiệu suất. Mục tiêu của định tuyến đảm bảo QoS là cung cấp các
thuật toán định tuyến có khả năng nhận biết đường dẫn để đáp ứng số lượng tối
đa có thể có của các luồng lưu lượng với các yêu cầu QoS. Theo đó, định tuyến
đảm bảo QoS trong bối cảnh của Internet ngày nay đã nhận được sự quan tâm
ngày càng lớn.
Xuất phát từ thực tế trên, đề tài nghiên cứu: “Các cơ chế định tuyến QoS
và thuật toán mở đường ngắn nhất đầu tiên (OSPF) mở rộng” được lựa
chọn. Thay vì tìm hiểu các vấn đề chung khá rộng lớn của định tuyến QoS, ở
đây chỉ tập trung vào một vấn đề cụ thể, dựa trên một giao thức định tuyến hiện
có. Cụ thể là, mô tả một tập hợp các đề xuất bổ sung cho giao thức định tuyến
OSPF để hỗ trợ cho việc định tuyến đảm bảo chất lượng của dịch vụ (QoS) 2
trong IP. Tập trung vào các luồng lưu lượng đơn điểm, chú trọng tới các metric
cần thiết để hỗ trợ QoS, các cơ chế thông báo liên kết kết hợp, thuật toán lựa
chọn đường dẫn, cũng như các khía cạnh của việc thiết lập tuyến đường đảm bảo
QoS. Mục tiêu là định rõ một cách tiếp cận, trong khi đạt được các mục tiêu cải
thiện hiệu suất cho các luồng lưu lượng QoS, làm như vậy với các tác động ít
nhất có thể trên giao thức OSPF hiện có.
Nội dung chính của luận văn gồm ba chương:
Chương 1: Tổng quan về định tuyến đảm bảo QoS
Nội dung chính của chương này là giới thiệu các khái niệm, các vấn đề
liên quan cần nghiên cứu về định tuyến đảm bảo QoS và đặt vấn đề cho các mở
rộng sang OSPF.
Chương 2: Các cơ chế định tuyến QoS
Nội dung chính là trình bày về định tuyến QoS trong mạng phân cấp và
các cơ chế định tuyến đảm bảo QoS.
Chương 3: OSPF mở rộng cho định tuyến đảm bảo chất lượng
Nội dung tập trung vào các mở rộng của OSPF cho định tuyến QoS.