LUẬN VĂN: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

Chia sẻ: Lan Lan | Ngày: | Loại File: PDF | Số trang:85

Thêm vào BST

Báo xấu

223
lượt xem 79
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ượngNội dung tập trung vào các...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: LUẬN VĂN: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

i ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ NGÂN 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ỘN LUẬN VĂN THẠC SĨ Hà Nội – 2011
ii 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 Mạng lưới cơ quan với các đề Agency Network án nghiên cứu tiên tiến AS Autonomous System Hệ thống tự trị ASid Autonomous System Số nhận dạng hệ thống tự trị Identiﬁer 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 Thuật toán định tuyến đa Constraints Routing rằng buộc liên kết rời rạc Algorithm DVMRP Distance Vector Multicast Giao thức định tuyến đa điểm Routing Protocol theo véc-tơ khoảng cách FTP File Transfer Protocol Giao thức truyền tệp IETE Internet Engineering Task Nhóm đặc trách kỹ thuật Force internet IP Internet Protocol Giao thức Internet ISP Internet Service Provider Nhà cung cấp dịch vụ Internet ITU International Hiệp hội viễn thông quốc tế Telecommunication Union LSA Link State Advertisement Thông báo trạng thái liên kết
v MAMCRA Multicast Adaptive Multiple Thuật toán định tuyến đa Constraints Routing ràng buộc thích ứng đa điểm Algorithm MCOP Multi-Constrained Optimal Tuyến tối ưu đa ràng buộc Path MCP Multi-Constrained Path Tuyến đa ràng buộc MOSPF Multicast Open Shortest Path Mở đường ngắn nhất đầu tiên First đa điểm MP-BGP Multi-Protocol BGP BGP đa giao thức MPLS Multiprotocol Label Chuyển mạch nhẵn đa giao Switching 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 Phương pháp định tuyến dựa approach trên dự đoán PIM Protocol Independent Chế độ đa điể m không phụ Multicast thuộc giao thức PNNI Private Network – Network Giao diện mạng - mạng cá Interface 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 Thuật toán định tuyến đa Constraints Routing ràng buộc tự thích ứng Algorithm
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 Hệ thống viễn thông di động Telecommunications Systems 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.
3 CHƯƠNG 1 - TỔNG QUAN VỀ ĐỊNH TUYẾN QoS 1.1. Giới thiệu định tuyến dựa trên QoS 1.1.1. Định tuyến Định tuyến là sự lựa chọn đường đi để truyền một đơn vị dữ liệu từ trạ m nguồn đến trạm đích trong một liên mạng theo tiêu chí nhất định. Chức năng định tuyến được thực hiện ở tầng mạng, cho phép router đánh giá các đường đi sẵn có tới đích và chọn đường đi thích hợp (Hình 1.1). Để đánh giá đường đi, định tuyến sử dụng các thông tin topo mạng, các thông tin này có thể do người quản trị thiết lập hoặc được thu lượm thông qua các giao thức định tuyến. Chọn đường? Hình 1.1. Định tuyến Tầng mạng hỗ trợ chuyển gói từ đầu cuối tới đầu cuối cố gắng tối đa (best-effort) qua các mạng được kết nối với nhau, sử dụng bảng định tuyến để gửi các gói từ mạng nguồn đến mạng đích. Sau khi đã quyết định sử dụng đường đi nào, router tiến hành việc chuyển gói. Nó lấy một gói nhận được ở giao diệ n vào và chuyển tiếp gói này tới giao diện ra tương ứng (giao diện thể hiện đường đi tốt nhất tới đích cho gói). Mục tiêu cơ bản của các phương pháp định tuyến là nhằ m sử dụng tối đa tài nguyên mạng, và tối thiểu hoá giá thành mạng. Để đạt được điều này kỹ thuật định tuyến phải tối ưu được các tham số mạng và người sử dụng như: xác suất tắc nghẽn, băng thông, độ trễ, độ tin cậy, giá thành,v.v... Vì vậy, một kỹ thuật định tuyến phải thực hiện tốt hai chức năng chính sau đây:  Quyết định chọn đường theo những tiêu chuẩn tối ưu nào đó.  Cập nhật thông tin định tuyến Tuỳ thuộc vào kiến trúc, hạ tầng cơ sở mạng mà các kỹ thuật định tuyến
4 khác nhau được áp dụng. Các tiêu chuẩn tối ưu khi chọn đường dẫn từ trạ m nguồn tới trạ m đích có thể phụ thuộc vào yêu cầu người sử dụng dịch vụ mạng. Giữa mạng và người sử dụng có thể có các thoả thuận ràng buộc về chất lượng dịch vụ cung cấp hay một số yêu cầu khác, điều đó có thể dẫn tới khả năng chọ n đường của mạng chỉ là cận tối ưu đối với một loại hình dịch vụ cụ thể, hoặc vớ i một số nhóm người sử dụng dịch vụ cụ thể. Chức năng cập nhật thông tin định tuyến là chức năng quan trọng nhất mà các giao thức định tuyến phải thừa hành, các giải pháp cập nhật thông tin định tuyến đưa ra hiện nay tập trung vào giả i quyết bài toán cân đối lưu lượng báo hiệu và định tuyến trên mạng với tính đầy đủ và sự nhanh chóng của thông tin định tuyến. Có nhiều cách để phân loại giao thức định tuyến, trong đó cách phân loại phổ biến nhất là phân định tuyến thành định tuyến theo véc-tơ khoảng cách và định tuyến theo trạng thái kết nối.  Định tuyến theo trạng thái kết nối: các nút mạng quảng bá thông tin định tuyến tới tất cả các nút trong liên mạng. Tuy nhiên, mỗi router chỉ gửi một phần bảng định tuyến (phần mô tả trạng thái kết nối của router) và xây dựng một bức tranh về toàn bộ mạng trong bảng topo. Mỗi khi topo trạng thái kết nối thay đổi, các router đầu tiên biết được sự thay đổi này sẽ gửi một thông báo trạng thái kết nối LSA (Link State Advertisement) mới tớ i các router khác hoặc tới một router chỉ định (nơi các router khác có thể sử dụng để cập nhật). LSA này sẽ được tràn ngập (flooding) tới tất cả các router trên liên mạng.  Định tuyến theo véc-tơ khoảng cách: là một thuật toán thích nghi nhằ m tính toán con đường ngắn nhất giữa các cặp nút trong mạng, dựa trên phương pháp tập trung được biết đến như là thuật toán Bellman-Ford. Các nút mạng thực hiện quá trình trao đổi thông tin trên cơ sở của địa chỉ đích, nút kế tiếp và con đường ngắn nhất tới đích. Khi tính toán đường đi ngắ n nhất sử d ụng định tuyến t heo trạ ng thái kết nố i và đ ịnh tuyến theo véc-tơ khoả ng cách, thông tin trạng thái c ủa mạ ng thể hiệ n qua các số đo (Metric) thông qua giá (cost), các bộ định tuyế n phả i được cập nhật giá trên tuyế n kết nố i. Khi có s ự thay đổ i topo mạ ng hoặc lưu lượ ng, các nút mạ ng phả i khở i tạo và tính toán lạ i tuyến đườ ng đi ngắ n nhất, tuỳ theo giao thức được sử dụng trong mạ ng. Các bảng định tuyến chứa thông tin được sử dụng bởi phần mề m chuyển mạch để chọn tuyến tốt nhất. Các thuật toán phức tạp có thể chọn tuyến dựa trên
5 nhiều metric bằng cách kết hợp chúng thành một metric phức hợp. Các metric được sử dụng phổ biến gồm: chiều dài đường đi, độ tin cậy, độ trễ, băng thông, tải và giá truyền thông. Chúng ta có thể so sánh định tuyến véc-tơ khoảng cách với định tuyến trạng thái kết nối theo một số tiêu chí như trong Bảng 1.1: Bảng 1.1. So sánh định tuyến trạng thái kết nối và véc-tơ khoảng cách. Véc-tơ khoảng cách Trạng thái kết nối Nhận thức về topo mạng từ các Có được cái nhìn toàn cảnh về liên router kế cận. mạng. Cộng vào véc-tơ khoảng cách từ Tính toán đường đi ngắn nhất tới tất cả router này tới router khác. các router. Cập nhật định kỳ, hội tụ chậ m. Cập nhật ngay khi thay đổi, hội tụ nhanh. Chuyển bản sao của bảng định Chuyển cập nhật định tuyến trạng thái tuyến tới các router kế cận. kết nối tới tất cả các router. Định tuyế n véc-tơ khoả ng cách lấy dữ liệu topo từ t hông tin bả ng đ ịnh tuyế n c ủa các router kế cận. Đ ịnh tuyế n trạng thái kết nố i có được một cái nhìn toàn cả nh về topo của liên mạ ng bằ ng cách tích luỹ tất cả các LSA cần thiết. Định tuyến véc-tơ khoảng cách xác định đường đi tốt nhất bằng cách cộng thêm vào giá trị metric mà nó nhận được khi thông tin định tuyến được gửi từ router này tới router khác. Đối với định tuyến trạng thái kết nối, mỗi router làm việc độc lập trong việc tính toán đường đi ngắn nhất tới các mạng đích. Trong hầu hết các giao thức định tuyến véc-tơ khoảng cách, cập nhật định tuyến về thay đổi topo mạng được gửi định kỳ. Các cập nhật được gửi từ router này tới router khác, dẫn đến mạng hội tụ chậm. Với các giao thức định tuyến trạng thái kết nối, cập nhật được gửi ngay khi topo mạng thay đổi. Các gói thông báo trạng thái kết nối LSA có kích thước tương đối nhỏ được chuyển tới tất cả các router, do đó thời gian hội tụ sẽ nhanh hơn khi topo mạng thay đổi. 1.1.2. Định tuyến dựa trên QoS Định tuyến dựa trên QoS là cơ chế định tuyến theo đó đường đi cho các luồng được xác định dựa trên một số hiểu biết về sự sẵn sàng của tài nguyên
6 trong mạng cũng như nhu cầu QoS của luồng [3]. Hay nói cách khác, đó là “ một giao thức định tuyến động có mở rộng tiêu chí chọn đường của nó bao gồm các tham số QoS như băng thông sẵn có, hiệu quả sử dụng đường đầu cuối và kết nối, mức tiêu thụ tài nguyên nút, trễ và trượt, biến động trễ”. Nói một cách ngắn gọn là định tuyến động có tính đến QoS. Hình 1.2 là ví dụ đơn giản về định tuyến dựa trên QoS. Giả sử có luồng lưu lượng từ nút A tới nút C yêu cầu băng thông 4Mbps, mặc dù đường A-B-C ngắn hơn, nhưng nó sẽ không được chọn vì không có đủ băng thông. Thay vào đó đường A-D-E-C được chọn. Hình 1.2. Ví dụ về phương pháp định tuyến dựa trên QoS Bên c ạnh đó, còn có hai khái niệm liên quan là đ ịnh tuyến dựa trên c hính sách và đ ịnh tuyến ràng buộc. Mối quan hệ giữa ba kiểu định tuyến được thể hiện trong hình 1.3. Định tuyến ràng buộc Định tuyến theo Định tuyến theo QoS chính sách Hình 1.3. Mối quan hệ giữa ba kiểu định tuyến
7 Định tuyến dựa tr ên chính sách là quyết định định tuyến không dựa trên hiểu biết về topo mạng và các số đo mà d ựa theo các chính sách quản trị. Định tuyến theo chính sách th ường đ ược cấu hình t ĩnh. Định tuyến ràng buộc là một quan niệm phát triển từ định tuyến dựa trên QoS nhưng có ý nghĩa rộng hơn. Nó tính đường đi để thoả mãn một số ràng buộc, bao gồm cả các ràng buộc về QoS (yêu cầu QoS và sự sẵn sàng của tài nguyên) và các ràng buộc theo chính sách. 1.1.3. Mục đích của định tuyến dựa trên QoS Các giao thức định tuyến Internet hiện nay được gọi là giao thức định tuyến “cố gắng tối đa”. Các giao thức này chỉ sử dụng “đường ngắn nhất” tới đích, chúng thường dùng các thuật toán tối ưu với mục tiêu đơn, theo đó chỉ xem xét một số đo (băng thông, số chặng, giá). Như vậy, toàn bộ lưu lượng được định tuyến vào “đường ngắn nhất”, ngay cả khi tồn tại đường cạnh tranh khác, chúng không được sử dụng chừng nào chúng chưa trở thành đường ngắn nhất. Điều này có thể dẫn tới tắc nghẽn của một vài kết nối, trong khi các kết nối khác không được dùng hết. Định tuyến “cố gắng tối đa” sẽ chuyển lưu lượng từ một đường tới đường “tốt hơn” mỗi khi nó tìm được. Việc này xảy ra ngay cả khi đường đang dùng đáp ứng được các yêu cầu dịch vụ của lưu lượng. Kiểu chuyển đổi này là không mong muốn vì nó dẫn tới sự dao động định tuyến, lưu lượng sẽ bị định tuyế n qua lại giữa các đường cạnh tranh. Thậm chí còn tồi tệ hơn vì kiểu dao động này có thể làm tăng biến động trễ và trượt. Định tuyến dựa trên QoS được cho là giải quyết hoặc tránh các vấn đề đã nêu trên. Các mục tiêu chính của định tuyến dựa trên QoS là:  Thứ nhất, là để đáp ứng các yêu cầu QoS của người sử dụng. Định tuyế n dựa trên QoS được giả thiết là để tìm một đường từ nguồn đến đích để thoả mãn các yêu cầu của người sử dụng về băng thông, trễ đầu cuối, … Ngoài ra, việc này phải được thực hiện trong chế độ động chứ không phả i là cấu hình tĩnh. Trong trường hợp có một vài tuyến khả thi sẵn có, tuyến được lựa chọn có thể là cơ sở cho một vài chính sách ràng buộc. Ví dụ: chúng ta có thể chọn tuyến ít chi phí nhất hoặc theo nhà cung cấp dịch vụ chỉ định.
8  Thứ hai, là để tối ưu hoá mức độ sử dụng tài nguyên mạng. Đây là mục đích theo quan điểm của nhà cung cấp dịch vụ. Tất cả các nhà cung cấp muốn khai thác tối đa khả năng mạng hiện thời của họ, nhờ thế đạt lợi nhuận cao nhất. Bên cạnh đó, đây cũng là yêu cầu xuất phát từ góc độ kỹ thuật xây dựng mạng. Định tuyến dựa trên QoS được trông đợi để quản lý lưu lượng mạng một cách hiệu quả sao cho thông lượng qua mạng là lớn nhất. Một lược đồ thông thường là luôn lựa chọn đường ngắn nhất trong số các đường khả thi, vì đường dài hơn có nghĩa là sử dụng tài nguyên mạng nhiều hơn.  Thứ ba, khi mà mạng ở tình trạng tải lớn, khả năng thực thi của mạng giảm, giống như xảy ra tắc nghẽn, định tuyến dựa trên QoS được mong đợi là sẽ cho chất lượng tốt hơn (ví dụ: thông lượng tốt hơn) so với định tuyến cố gắng tối đa, (định tuyến cố gắng tối đa có thể làm giảm thực thi mạng một cách đột ngột). 1.2. Các vấn đề cơ bản của định tuyến dựa trên QoS Định tuyến dựa trên QoS thì khó thiết kế và thực thi hơn nhiều so với định tuyến cố gắng tối đa. Trong hầu hết các trường hợp mục đích không phải là tìm giải pháp tốt nhất, mà là tìm giải pháp với chi phí có thể chấp nhận được. 1.2.1. Metric và sự tính toán đường đi Có hai vấn đề cơ bản của phương pháp định tuyến dựa trên QoS: Thứ nhất, đo và thu thập thông tin trạng thái mạng như thế nào; Thứ hai, tính toán các lộ trình dựa trên thông tin đã thu được như thế nào. Sự lựa chọn metric là rất quan trọng theo nghĩa rằng: “các metric phải thể hiện các đặc tính mạng cơ bản mà ta quan tâm”. Do đó các metric như băng thông sẵn có, trễ, biến động trễ, … được sử dụng phổ biến; cũng như là các metric xác định kiểu bảo đảm QoS mà mạng cung cấp. Không có phương pháp hỗ trợ yêu cầu QoS nào mà không thể biểu diễn bởi tổ hợp nào đó của các metric hiện hữu. Bên cạnh đó cần xem xét sự phức tạp trong tính toán, nghĩa là việc tính toán đường đi dựa trên một metric hoặc tổ hợp các metric phải không quá phức tạp. Tiếc rằng, định tuyến dựa trên QoS thường được thực hiện với nhiều ràng buộc và việc tính toán đường dựa trên tổ hợp nhất định nào đó của các metric đã được chứng minh là bài toán NP (No Polynomial) hoàn thiện. Rất nhiều thuật toán được đề xuất để giải quyết vấn đề này. Một phương pháp chung nhất được
9 gọi là “lọc tuần tự”, nghĩa là “một tổ hợp của các metric được sắp xếp thứ tự theo một dạng nào đó phản ánh tầm quan trọng của các metric khác nhau”. Các đường đi dựa trên metric đầu tiên được tính toán trước tiên và tập con của chúng được loại bỏ dựa trên metric thứ hai và cứ như thế cho đến khi một đường đơn được tìm thấy. Đây là sự cân bằng giữa sự tối ưu hoá phẩm chất và sự đơn giản trong tính toán. Việc tính toán đường đi cũng liên quan chặt chẽ tới việc dành trước tài nguyên, nghĩa là một khi đường thích hợp đã được chọn thì tài nguyên tương ứng (băng thông, không gian đệm trong các bộ định tuyến, …) phải được dành cho dòng lưu lượng, vì vậy không thể dành cho các dòng khác. Hậu quả là, lượng tài nguyên sẵn có (như băng thông) sau khi dành trước phải được tính toán lại và thông tin đó phải được phát tán tới các bộ định tuyến khác. Bằng cách này tất cả các bộ định tuyến có thể tạo quyết định đúng đắn cho các luồng khác nhau. 1.2.2. Lan truyền và duy trì thông tin Một vấn đề quan trọng là thông tin đ ịnh tuyến thường được trao đổi giữa các bộ định tuyến như thế nào. Đ ịnh tuyến dựa trên QoS cần trao đổi nhiều thông tin hơn đ ịnh tuyến cố gắng tối đa. Thứ nhất, ngo ài thông tin đ ịnh tuyến cần có giống như đ ịnh tuyến cố gắng tối đa, cần trao đổi cả những thông tin QoS, ví dụ như băng thông s ẵn có. Thứ hai, các metric được sử dụng trong đ ịnh tuyến dựa trên QoS có thể thay đổi rất nhanh (một lần nữa, băng thông sẵn có là một ví dụ điển hình). Nếu như thông tin đ ịnh tuyến được trao đổi mỗi khi có sự thay đổi giá trị metric, nó sẽ gây ra một tải trọng lớn cho các kết nối mạng và các bộ định tuyến, tiêu thụ băng thông của mạng và các nhịp CPU của các bộ định tuyến. Một cách chung nhất là thiết lập một ngưỡng để phân biệt các thay đổi đáng kể từ các thay đổi nhỏ. Thông tin chỉ đ ược trao đổi khi xảy ra một thay đổi đáng kể. Là m như thế, có thể đem lại sự ổn định của các tuyến QoS. Thêm nữa, đây là sự trả giá giữa hiệu quả và sự chính xác của thông tin định tuyến. Một phương pháp khác là chỉ xem xét các tài nguyên sẵn có sau khi dành trước thay cho các tài nguyên có thực. Lấy băng thông là ví d ụ. Giả sử một đ ường kết nối trong mạng có băng thông 4 Mbps, trong đó băng thông 3Mbps đã được dành trước bởi một số đường nào đó. Vì vậy băng thông sẵn có còn lại là 1Mbps. Trong điều kiện là không có một luồng mới nào dành lấy
10 băng thông sẵn có này và không có luồ ng nào trả lại băng thông hiện đang giữ, thì băng thông sẵn có được coi là 1 Mbps. Nói cách khác, ta không xem xét lượng băng thông được dành trước nhưng không được sử dụng, mặc dù băng thông được dùng trong thực tế có thể thay đổi t heo thời gian (có thể là 1,5Mbps tại thời điểm này và 2,5Mbps tại thời điểm khác). Hai cách này có thể được sử dụng cùng với nhau. Một vấn đề liên quan là duy trì thông tin thu đ ược như thế nào. Nếu ta giữ thông tin cho từng luồng trong các bộ định tuyến, t hì kích thước của bảng định tuyến sẽ tăng lên rất nhanh. Có một gợi ý là chỉ giữ bảng định tuyến cho lưu lượng cố gắng tối đa và tính toán các đường đi cho các luồng QoS theo nhu cầu. Đây là sự hy sinh thời gian tính toán thay c ho không gian bộ nhớ. Một phương pháp khác có thể là nhóm luồng. Thay cho việc ghi nhớ thông tin về các luồng riêng rẽ ta có thể nhóm các luồng và chỉ duy tr ì thông tin về các nhóm luồng, với số lượng rõ ràng ít hơn. 1.2.3. Mô hình thông tin trạng thái không chính xác Một xu hướng trong thiết kế thuật toán định tuyến dựa trên QoS là ngày càng có nhiều người tin rằng định tuyến QoS về bản chất là không chính xác. “Không chính xác” có nghĩa rằng thông tin trạng thái dùng trong định tuyến là không chính xác. Các nguồn gốc của sự không chính xác là:  Tính động của mạng: một vài tham số hay metric (cụ thể là băng thông sẵn có và độ trễ) gắn với nút và kết nối của mạng thay đổi theo thời gian. Sẽ rất khó (thậm chí là không thể) để gửi cho thông tin thật chính xác.  Nhóm thông tin định tuyến: như đã đề cập ở phần trước, nhóm định tuyến là được khuyến khích để giảm sự định tuyến cập nhật tải và sự định tuyến chứa tải, đặc biệt cho các mạng lớn. Tổng tin của nhóm thường mang tính đại diện hoặc tính trung b ình.  Thông tin ẩn: đối với việc bảo mật hoặc một vài nguyên nhân khác, một vài thông tin đ ịnh tuyến được ẩn đi và do đó không thể nhận ra.  Các tính toán gần đúng: không có giá tr ị nào của tham số hay metric của mạng thực sự là chính xác. Đó chỉ là các giá trị gần đúng của các giá trị thực, theo thời gian thực
11 1.2.4. Điều khiển của quản trị mạng Có một số vấn đề điều khiển liên quan tới QoS.  Thứ nhất là vấn đề ưu tiên và chiếm đoạt: các luồng khác nhau trong mạng có các yêu cầu QoS khác nhau, vì thế có mức ưu tiên khác nhau. Các luồng quan trọng có thể được gán mức ưu tiên cao hơn các luồng khác. Khi tài nguyên (ví d ụ như băng thông) không có đ ủ, các luồng này có thể chiếm tài nguyên từ các luồng có mức ưu tiên thấp hơn. Ví dụ luồng thoại hoặc video (với yêu cầu nghiêm ngặt về trễ và băng thông) có thể được gán mức ưu tiên cao hơn và được phép chiếm băng thông hoặc bộ đệm của các luồng FTP ( File Transfer Protocol - Giao thức truyền tệp).  Thứ hai là vấn đề kiểm soát tài nguyên: Trong khung cảnh mạng có nhiều lớp dịch vụ lưu lượng, tài nguyên phải được phân phối công bằng giữa các dịch vụ. Như vậy sự thiếu hụt t ài nguyên c ủa các lớp dịch vụ ưu tiên thấp có thể tránh được. Việc bố trí tài nguyên này có thể đ ược thực hiện ở dạng động. Định tuyến dựa tr ên QoS cần bao hàm các sơ đồ điều khiển như trên. 1.2.5. Vấn đề thuật toán trong định tuyến dựa trên QoS. Về cơ bản có thể chia các thuật toán định tuyến dựa trên QoS thành ba loại: định tuyến chặng tới chặng (còn gọi là định tuyến phân tán), định tuyến nguồn và định tuyến phân cấp. Chúng được chia theo cách duy trì thông tin trạng thái và tìm đường thích hợp để truyền như thế nào.  Định tuyến nguồn: Mỗi bộ định tuyến đều chứa thông tin trạng thái mạng toàn cục và đường được chọn một cách cục bộ dựa trên thông tin trạng thái này. Sau khi đường được xác định, bộ định tuyến nguồn thông báo cách đưa các lưu lượng tải như thế nào cho các bộ định tuyến khác theo đường đó. Sau đó luồng sẽ được định tuyến đến đích phù hợp. Định tuyến nguồn là đơn giản theo nghĩa rằng chỉ bị quyết định bởi nguồn. Các bộ định tuyến khác theo đường truyền chỉ cần theo đường xác định trước đó và nó sẽ không gây ra sự định tuyến lòng vòng. Tuy nhiên, nó cũng có những nhược điể m. o Thứ nhất, yêu cầu mỗi bộ định tuyến chứa thông tin trạng thái mạng hoàn chỉnh, mà điều này là khó duy trì, đặc biệt đối với mạng
12 lớn, gây ra nhiều cập nhật thông tin trạng thái, do đó đưa nhiều lưu lượng tải tới mạng. o Thứ hai, nếu tổng hợp những cập nhật thông tin trạng thái để làm giả m sự quá tải lưu lượng, thì độ chính xác của thông tin có thể bị giả m đi. Do vậy, có thể không tìm được một đường thích hợp hiện tại. o Thứ ba, mặc dù các bộ định tuyến khác có thể dễ dàng định hướng lưu lượng, nhưng việc tính toán tải tại các bộ định tuyến nguồn là rất lớn. Tóm lại, thuật toán định tuyến nguồn có vấn đề co giãn, do vậy không tốt cho các mạng lớn.  Định tuyến phân tán: Trong định tuyến phân tán, mỗi bộ định tuyến chỉ biết các chặng kế tiếp tới nguồn đích. Do đó khi một gói truyền tới, bộ định tuyến chỉ chuyển nó tới bộ định tuyến chặng tiếp theo. Theo từng bước như vậy, gói được đưa đến đích. Phần lớn các giao thức mạng Internet (như RIP) đều dùng thuật toán này. Định tuyến phân tán được sử dụng cho hầ u hết các giao thức định tuyến “cố gắng tối đa”. Do vậy, dễ dàng để thiết kế và phù hợp hơn với các giao thức định tuyến hiện thời. Việc tính toán tải định tuyến được góp bởi tất cả các bộ định tuyến trên đường, từ nút nguồn tới nút đích. Tuy nhiên, tồn tại vấn đề định tuyến lòng vòng khi thông tin trạng thái định tuyến trong các bộ định tuyến khác nhau là không phù hợp. Bên cạnh đó cũng có vấn đề co giãn.  Định tuyến phân cấp: Định tuyến phân cấp là phù hợp nhất cho mạng lớn. Cấu trúc của định tuyến bao gồm nhiều cấp. Cấp trung tâm bao gồ m các bộ định tuyến hiện thời. Những bộ định tuyến này được tổ chức thành các nhóm cục bộ, mà hình thành nên cấp tiếp theo. Mỗi nhóm là các nút cục bộ trong cấp kế tiếp. Các nhóm có thể được tổ chức lớn hơn trong các nhóm cấp cao hơn. Quá trình xử lý này có thể đệ quy (recursively), do đó mỗi cấp không có quá nhiều nút (các bộ định tuyến). Thông tin định tuyến được tích hợp tại các nút tiếp giáp với mỗi nhóm. Mỗi nút bao gồm thông tin chi tiết về nhóm của nó và thông tin được tích hợp về các nhóm khác. PNNI và QOSPF là ví dụ tiêu biểu cho định tuyến phân cấp. Như thấy trong hình 1.4: A1, A2, A3 tạo thành một nhóm cục bộ, được tương ứng bằng nút cục bộ A. Tượng tự: B1, B2, B3 tạo thành một nhóm; C1 và C2 tạo thành một nhóm khác, tương ứng với các