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 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. 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. 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 Chọn đường? 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 theo 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 router kế cận. Có được cái nhìn toàn cảnh về liên mạng. Cộng vào véc-tơ khoảng cách từ router này tới router khác. Tính toán đường đi ngắn nhất tới tất 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 tuyến tới các router kế cận. Chuyển cập nhật định tuyến trạng thái 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ừ thô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 chí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. Hình 1.3. Mối quan hệ giữa ba kiểu định tuyến Định tuyến ràng buộc Định tuyến theo QoS Định tuyến theo chính sách 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 4Mbps, 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à 1Mbps. 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 theo 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, thì 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 cho 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 13 nút cục bộ B và C. Các nút cục bộ A, B và C tạo thành một nhóm ở một cấp khác. Hình 1.4. Cấu trúc định tuyến phân cấp Hình 1.5 cho thấy bảng định tuyến của A1 trong cấu trúc hình 1.4, nó chứa thông tin chi tiết về nhóm của nó (nhóm A), trong khi thông tin về nhóm B và nhóm C được tích hợp. Hình 1.5. Ví dụ về bảng định tuyến phân cấp (của A1) Có thể nói, ưu điểm lớn nhất của định tuyến phân cấp là sự co giãn. Do vậy phù hợp với các mạng lớn. Thông tin trạng thái định tuyến có thể được tổng hợp để giảm tải trong bộ nhớ và cập nhật định tuyến. Tuy nhiên, việc tổng hợp cũng giảm độ chính xác của thông tin trạng thái định tuyến, do vậy ảnh hưởng đến chất lượng của định tuyến dựa trên QoS. Rõ ràng, định tuyến phân cấp cho thấy rất nhiều ưu điểm nổi trội, phù hợp cho việc định tuyến QoS trong các mạng hiện nay. Chúng ta sẽ nghiên Nút logic B Nút logic C Nhóm logic mức 2 Nhóm logic A Nhóm logic B Nhóm logic C Nút logic A Nút logic B Nút logic C 14 cứu sâu hơn về cơ chế và thuật toán trong định tuyến QoS nội miền và liên miền trong chương 2 Như đã nêu, vấn đề thuật toán trong định tuyến dựa trên QoS, được gọi là vấn đề chọn đường tối ưu hóa đa ràng buộc MC(O)P (Multi-Constrained (Optimal) Path).. Một vài phương pháp đã đề xuất ra chỉ tiêu đặc biệt cho vấn đề MC(O)P. Ví dụ, khi băng thông là một trong những ràng buộc phải được thỏa mãn bởi thuật toán tính toán đường đi, vấn đề MCP được định nghĩa như là vấn đề đường dẫn có giới hạn băng thông BRP. Một phương pháp đơn giản để giải quyết vấn đề MCP nói chung là thông qua việc kết hợp các tham số. Bằng việc kết hợp một tập hợp các phép đo QoS trong một phép đo đơn, nó có thể sử dụng thuật toán tính toán đa thức thời gian hiện tại như Bellman–Ford hoặc Dijkstra. Thuật toán Dijkstra cần có thông tin về toàn bộ đồ thị để có thể tìm ra con đường ngắn nhất từ một đỉnh tới các đỉnh còn lại. Thuật toán Bellman-Ford thì thích hợp cho việc tính toán phân tán chỉ cần thông tin về các cung từ một đỉnh tới các đỉnh lân cận. Việc sử dụng các thuật toán này, mỗi nút trong mạng sẽ lưu giữ một bảng chọn đường, chỉ ra nút tiếp theo trên con đường ngắn nhất tới đích, và số đo của con đường đó. Khi mạng có sự thay đổi, các thông tin cập nhật được chuyển qua các nút lân cận hoặc được quảng bá trên toàn mạng. Từ đó, các nút sẽ tính lại bảng chọn đường của mình. Dựa vào các bảng chọn đường trong mỗi nút, chúng ta có thể tạo được cây đường ngắn nhất tới mỗi nút. Hình dưới đây mô tả đường dẫn ngắn nhất trong một sơ đồ hướng theo Dijkstra. Sơ đồ này có 6 nút và 11 cạnh. Đường dẫn ngắn nhất từ nút 1 đến nút 6 là đường đi từ nút 1 đến nút 5 đến nút 4 rồi đến nút 6. 15 Hình 1.6. Đường dẫn ngắn nhất trong một sơ đồ có hướng 1.2.6. Vấn đề động trong định tuyến dựa trên QoS Vấn đề khó khăn nhất hiện nay cản trở việc thực hiện QoS trên Internet liên quan tới giao thức định tuyến dựa trên QoS. Để cho phép định tuyến dựa trên QoS, cần phải triển khai các giao thức mạng nhận biết được QoS và phụ thuộc vào trạng thái. Một ví dụ về giao thức PNNI (Private Network – Network Interface) sử dụng định tuyến trạng thái liên kết, trong đó mỗi nút sẽ cố gắng để có được bản đồ topo mạng cơ bản và các tài nguyên có thể dùng được thông qua “flooding” (gửi tin kiểu tràn ngập). Các tài nguyên sẵn có trong một kết nối được thể hiện bằng các giá trị, được gọi là trọng số kết nối. Mặc dù đơn giản, đáng tin cậy, nhưng “flooding” kéo theo việc truyền thông không cần thiết và gây ra việc sử dụng không hiệu quả nguồn tài nguyên. Đặc biệt, định tuyến dựa trên QoS yêu cầu sự phân bố thường xuyên của các số liệu động và phức tạp. Giám sát bất kì sự thay đổi nào của internet là việc không đơn giản và thậm chí là không mong muốn bởi vì không phải tất cả sự thay đổi đều quan trọng. Hai thay đổi hợp lý được xem xét là:  Thay đổi thường xuyên do việc tham gia hoặc rời khỏi mạng của các nút. Trong internet hiện nay, chỉ loại thay đổi topo mới được xét đến. Tính động của nó tương đối được hiểu rõ 16  Các thay đổi thường xuyên liên quan đặc thù tới sự tiêu hao các nguồn tài nguyên hoặc tới sự truyền tải lưu lượng qua mạng. Việc kết hợp trọng số kết nối với thông tin trạng thái làm phức tạp thêm “flooding” bởi vì, trái với những thay đổi thường xuyên, thời gian hội tụ “flooding” có thể lâu hơn tốc độ thay đổi của một vài tham số (như băng thông khả dụng). Sự nhận dạng các đặc tính QoS và sự mô tả đặc điểm của chúng là yếu tố quyết định đến khái niệm giao thức định tuyến nhận biết được QoS. Các đặc tính QoS sử dụng để hỗ trợ các quyết định định tuyến thường bao gồm băng thông, tỷ lệ mất mát, trễ và jitter. Việc lựa chọn các thông số để mà căn cứ vào đó đưa ra quyết định định tuyến là một trong những vấn đề chính phải được giải quyết trong chiến lược định tuyến bởi vì nó quyết định đồng thời các đặc tính để cung cấp cho lưu lượng và sự phức tạp của thuật toán tính toán đường dẫn. Việc lựa chọn các tham số phải được thực hiện để tăng nhận thức dịch vụ mạng và tự nhận thức mạng. Định nghĩa của các vấn đề liên quan đến các thông số góp phần nâng cao tự nhận thức và nhận thức dịch vụ thông qua định nghĩa của các quyết định liên quan đến lựa chọn thông số và các cơ chế cho việc thao tác số liệu. Việc tính toán các đường dẫn nhận thức QoS yêu cầu các bộ định tuyến có được thông tin về trạng thái của mạng dưới dạng các số liệu đã được lựa chọn. Trạng thái của mạng gồm có trạng thái cục bộ của mỗi nút và trạng thái bao trùm đang gắn liền với đường dẫn hiện tại. Trạng thái bao trùm duy trì bởi mỗi nút có thể nhận được bởi sự phân bố của các trạng thái cục bộ của các nút. Một chiến lược cập nhật tối ưu cho những thay đổi không thường xuyên là mong muốn trong tương lai, các mạng đa phương tiện được đặc trưng bởi sự biến đổi lớn trong chế độ lưu lượng và yêu cầu QoS. Mặc dù một số nghiên cứu đã đề cập đến vấn đề này nhưng không có chiến lược cập nhật chi tiết nào cho các thay đổi không thường xuyên. Hơn nữa, không phải tất cả các chi tiết của toàn bộ mạng internet toàn cầu là cần thiết để xác định đường đi từ A tới B. Một mạng con bao gồm A và B có vẻ như đủ. Về mặt này, các thuộc tính của một topo mạng là rất quan trọng. Internet cho thấy có một sự phân cấp nhất định, trong khi các mạng Ad-Hoc có thể thay đổi từ các cấu trúc lưới thành các đồ hình ngẫu nhiên. Từ đó các đường dẫn phụ thuộc mạnh mẽ vào cấu trúc trọng số kết nối và các thuộc tính của đồ hình, tính động của mạng sẽ phụ thuộc vào các yếu tố này, thậm chí đến mức mà 17 một số chiến lược điều khiển thành công trong một lớp nào đó của đồ hình có thể không làm việc đúng trong đồ hình khác. 1.3. Kỹ thuật OSPF và vấn đề mở rộng OSPF cho định tuyến QoS 1.3.1. Kỹ thuật OSPF OSPF [6] là một giao thức với một phạm vi rộng các metric có thể cấu hình. Đây là loại giao thức định tuyến yêu cầu mỗi router duy trì ít nhất một bản đồ một phần của mạng. Khi một router mới gia nhập vào một mạng, nó tìm hiểu để nhận dạng danh tính của tất cả các router láng giềng của nó. Khi điều này được thực hiện, mỗi router sẽ xây dựng một thông điệp có chứa các định danh và các giá của các liên kết gắn với router cụ thể. Các thông điệp này được gọi là các thông báo trạng thái liên kết (LSA). Bất cứ khi nào trạng thái của một liên kết thay đổi, thì một LSA được flooding trên toàn mạng. Tất cả các bộ định tuyến sẽ thông báo sự thay đổi này, và tính toán lại các tuyến đường phù hợp. Mỗi router sẽ lưu LSA mới nhất từ mọi router trong mạng, bây giờ mỗi bộ định tuyến biết topo mạng hiện tại và có thể tính toán các tuyến đường ngắn nhất. Các tuyến đường ngắn nhất tới tất cả các nút khác trong mạng được tính toán với các thuật toán Dijkstra. Hoạt động cơ bản của thuật toán được minh họa trong hình sau đây. Bảng 1.2 là bảng chuyển tiếp kết quả cho router A. Bảng 1.2. Bảng chuyển tiếp cho router A Đích đến Liên kết Metric A Local 0 B 1 10 C 1 20 D 1 60 E 2 20 F 1 40 G 1 50 18 Hình 1.7. Ví dụ mạng Hình 1.8. Bắt đầu từ router A và các LSA của nó Hình 1.9. Lựa chọn router B, và thêm các LSA của nó 19 Hình 1.10. Lựa chọn router E, tuyến đường không tốt hơn tới router C Hình 1.11. Lựa chọn router C, và thêm các LSA của nó Hình 1.12. Lựa chọn router F, và thêm các LSA của nó 20 Hình 1.13. Lựa chọn router G, và thêm các LSA của nó. Tuyến đường tốt hơn tới router D được tìm thấy Hình 1.14. Lựa chọn router D 21 1.3.2. Độ tin cậy trong định tuyến dựa trên QoS Căn nguyên của độ tin cậy có thể được truy trở lại những ngày đầu của máy tính và truyền thông. Trong bối cảnh của những năm đầu và công trình tiên phong của Babbages, Larnder vào năm 1834 [16] đã đề xuất để loại bỏ sai sót trong tính toán bằng cách sử dụng các máy tính độc lập và riêng biệt và thậm chí mang tính quyết định hơn với các phương pháp tính toán khác nhau. Sau đó, máy tính điện tử đầu tiên và hệ thống truyền thông sử dụng các khối có độ tin cậy không cao. Như một kết quả nghiên cứu tập trung vào việc nâng cao độ tin cậy và độ tin cậy của hoạt động là bước đầu tiên hướng tới QoS. Lý thuyết cơ bản của sự dự phòng để nâng cao độ tin cậy của cấu trúc theo logic và nâng cao chất lượng của truyền thông đã được phát triển từ Von Neumann, Moore, Shannon [17]-[18] và những người kế thừa của họ và vẫn là cơ sở cho công việc nghiên cứu của chúng ta. Ngày nay, khái niệm cơ bản của độ tin cậy trong hệ thống máy tính hay hệ thống truyền thông được thảo luận từ một quan điểm kỹ thuật trong các nhóm nghiên cứu khác nhau Bây giờ chúng ta tập trung vào các khía cạnh của độ tin cậy liên quan chặt chẽ tới mạng lưới truyền thông và đặc biệt là internet. Sự hoạt động tin cậy của hệ thống định tuyến là một phần của chương trình nghị sự định tuyến dựa trên QoS kể từ những ngày đầu của internet. Ví dụ, tiền thân của internet, ARPANET, bị thất bại bởi vì giao thức định tuyến của nó chỉ có thể được chỉnh sửa với sự can thiệp thủ công. Dựa trên kinh nghiệm này, cộng đồng Internet quyết định cần có giao thức định tuyến để thực hiện một vài tiêu chuẩn tin cậy cơ bản, như khả năng của giao thức để ổn định (phục hồi) sau khi tình trạng hoạt động không mong đợi được loại bỏ (tự ổn định). Bị ảnh hưởng bởi sự thất bại của ARPANET, các giao thức định tuyến cho Internet đã được giữ ở mức rất đơn giản. Thậm chí ngày nay và mặc dù thực tế của yêu cầu ứng dụng dựa trên QoS cao, Internet hoạt động mà không có QoS và không có các cơ chế định tuyến QoS. Chúng ta kết luận rằng chính yêu cầu về độ tin cậy và khả năng sống còn của chức năng vận chuyển ngay cả trong điều kiện khắc nghiệt đã tạo nên một điểm quan trọng trong chương trình nghị sự về định tuyến dựa trên QoS. Chúng ta định nghĩa “Độ tin cậy định tuyến là tính tin cậy của một hệ thống định tuyến, được đặt trên sự nhất quán của cách hoạt động và hiệu suất của dịch vụ định tuyến nó thực hiện” [9]. Để có thể thiết kế các hệ thống định tuyến dựa trên QoS tin cậy, cần thiết phải hiểu rõ hơn các số đo độ tin cậy của định tuyến. Các số đo này không cố 22 định, tuy nhiên, chúng bị ảnh hưởng bởi các đặc tính của mạng đang xem xét. Ví dụ, về truyền thông không dây, chúng ta tìm ra một vài các đặc tính quan trọng để chi phối độ tin cậy định tuyến có thể là:  Sự di động hệ thống đầu cuối và người sử dụng;  Bản chất vô tuyến của kênh truyền;  Các giao thức định tuyến và thuật toán định tuyến…. Sự thích ứng với tình trạng thay đổi của mạng cũng như chi phí phụ phát sinh;  Các cấu trúc hạ tầng cơ sở hoặc các hệ thống định tuyến lai ghép;  Những hạn chế về các tài nguyên năng lượng;  Khả năng không cân bằng của các nút trong các mạng phức tạp;  Sự hợp tác và không hợp tác của các nút mạng trong mạng ad hoc;  Các tác động bên ngoài, như là điều kiện môi trường… 1.3.3. Đặt vấn đề nghiên cứu thuật toán OSPF mở rộng Để đạt được độ tin cậy cao, đã có nhiều sơ đồ định tuyến dựa trên QoS khác nhau được đề xuất (cho cả đơn đích và đa đích). Tuy nhiên, phần lớn các sơ đồ này tập trung vào một vấn đề cụ thể với các thuật toán dựa trên những giả thiết khác nhau về trạng thái mạng và vì vậy không thể làm việc cùng nhau. Từ đó ta thấy rõ ràng rằng cần có một khuôn khổ làm việc chung nhất với hai mức định tuyến dựa trên QoS nội miền [4] và định tuyến dựa trên QoS liên miền [14]. Mô hình phân cấp này tương thích với các cấp thang định tuyến của Internet ngày nay (vốn có quan niệm Hệ thống tự trị). Hình 1.15 cho thấy cấu trúc định tuyến hai mức như thế nào. Định tuyến giữa các nút A, B và C thuộc về định tuyến nội miền, trong khi giữa nút B với E hoặc F thuộc về định tuyến liên miền. Định tuyến nội miền sử dụng định tuyến trong một mạng đơn hoặc một miền quản trị. Mỗi miền quản trị tự do lựa chọn giao thức định tuyến nội miền sử dụng trong mạng của mình. Hai loại giao thức định tuyến nội miền có thể dùng được hiện nay là giao thức định tuyến theo trạng thái liên kết và giao thức định tuyến theo vecto khoảng cách. Giao thức trạng thái liên kết phân phối topo toàn mạng tới tất cả các router trong miền, và quyết định cách thức lựa chọn đường dẫn tốt nhất để đạt đến bất kỳ đích đến nào bên trong miền này, dựa trên thuật toán đường dẫn ngắn nhất của Dijkstra. Ngoài ra, trong giao thức định 23 tuyến theo vector khoảng cách, các router thiếu topo toàn mạng và lựa chọn đường dẫn tốt nhất là dựa trên thuật toán định tuyến Bellman-Ford. Hiện nay, hầu hết các triển khai mở rộng của giao thức định tuyến nội miền là một giao thức trạng thái liên kết OSPF. Hình 1.15. Định tuyến nội miền so với định tuyến liên miền Vượt qua ranh giới miền quản trị một giao thức định tuyến liên miền [14] được sử dụng để trao đổi thông tin, và để lựa chọn đường dẫn tốt nhất để đạt đến bất kỳ đích nào theo những nguyên tắc cụ thể và nhu cầu của mỗi miền. Ngược lại với trường hợp nội miền, với định tuyến liên miền có một giao thức định tuyến chuẩn thực tế, giao thức cổng đường biên BGP. Phiên bản hiện tại của BGP là một giao thức định tuyến theo vector, nó chỉ nhận biết về các mối liên kết giữa các miền quản trị khác nhau. Nói cách khác, BGP không quản lý hoặc trao đổi bất kỳ loại thông tin nội miền nào, do đó, tình trạng nội mạng trong bất kỳ miền quản trị nào cũng không bị tiết lộ bởi BGP. Tóm lại, trong khi định tuyến nội miền quản lý việc lựa chọn đường đi tốt nhất trong một miền quản trị duy nhất, thì định tuyến liên miền lại giữ cho Internet như một đơn vị duy nhất. Định tuyến nội miền Định tuyến liên miền Miền 1 Miền 2 Miền 3 Miền N 24 BGP hiện tại cung cấp một phản ứng lại chậm và giao thức định tuyến có giới hạn, mà không đủ để xử lý hầu hết các nhu cầu xuất hiện cho các chức năng liên miền. Trong số những yêu cầu liên miền này không có các cơ chế hiệu quả về giá và hiệu quả cao để cung cấp các mức độ khác nhau của QoS end-to-end, trong đó giao thức định tuyến liên miền thì lại có tầm quan trọng tuyệt đối. Nói cách khác, phiên bản hiện tại của BGP thiếu năng lực định tuyến dựa trên QoS, cái mà đã được công nhận như một nhu cầu mạnh mẽ của nhóm đặc trách kỹ thuật internet (IETF) từ giữa năm 1998. Do đó, nhiều nỗ lực đang được thực hiện để giải quyết vấn đề định tuyến dựa trên QoS ở mức độ liên miền trong các mạng IP. Như vậy, cả ở mức độ nội miền và ở mức độ liên miền đều cần giải quyết các vấn đề định tuyến dựa trên QoS. Luận văn chọn phương án sử dụng một giao thức định tuyến cơ bản là OSPF, từ đó mở rộng các thuật toán và các cơ chế định tuyến liên quan để đảm bảo QoS. Một vấn đề cần quan tâm nhất là vấn để tăng tải do truyền thông tin định tuyến, nhất là khi chọn đường đảm bảo các ràng buộc về QoS. Luận văn chọn đi sâu phân tích một vài cơ chế liên quan đến lan tràn thông tin định tuyến bằng “flooding”. Điều này sẽ được trình bày ở chương 2 Tóm lại: Chương 1 đã giúp chúng ta có cái nhìn tổng quát về định tuyến dựa trên QoS, chỉ ra các vấn đề cơ bản của định tuyến đảm bảo QoS như metric, thuật toán…Chương 2 sẽ trình bày về định tuyến dựa trên QoS trong mạng có phân cấp định tuyến-mạng phổ biến hiện nay (định tuyến QoS nội miền và liên miền) và phân tích cơ chế trao đổi thông tin định tuyến. 25 CHƯƠNG 2 – CƠ BẢN VỀ CÁC CƠ CHẾ ĐỊNH TUYẾN QoS [2] Định tuyến Internet có thể được chia thành 2 phần riêng biệt, mỗi phần có một đặc điểm và mục đích rất khác nhau, cụ thể là định tuyến nội miền và định tuyến liên miền. Chương 2 trình bày về định tuyến QoS nội miền và liên miền, sau đó tổng kết về các cơ chế cơ bản nhất trong định tuyến QoS. Nội dung của chương này phục vụ cho các trình bày về mở rộng thuật toán định tuyến OSPF cho QoS ở Chương 3. 2.1. Định tuyến QoS nội miền Đối với định tuyến dựa trên QoS nội miền, người ta chủ động bố trí nhiều sơ đồ với các thuật toán khác nhau trong cùng một miền. Người quản lý có quyền lựa chọn loại định tuyến dựa trên QoS bất kỳ trong miền này, độc lập với định tuyến dựa trên QoS trong các miền khác. Ở mức này người ta khuyến khích sự đa dạng các dịch vụ định tuyến dựa trên QoS trải suốt từ việc tính toán đường động dựa trên thông tin trạng thái hiện thời cho tới các đường dự trữ tính hỗ trợ một số ít các lớp dịch vụ. Tuy nhiên, định tuyến dựa trên QoS nội miền yêu cầu một vài đặc điểm chung, như được liệt kê dưới đây:  Sơ đồ định tuyến phải tìm đường đáp ứng yêu cầu QoS của luồng lưu lượng, nếu tồn tại một luồng lưu lượng như thế. Ngược lại nó phải chỉ ra rằng luồng lưu lượng đó không được phép.  Để tối ưu hoá việc sử dụng tài nguyên, sơ đồ định tuyến phải có thông báo đường bị ngắt mỗi khi đường bị ảnh hưởng bởi những thay đổi topo trong mạng.  Sơ đồ định tuyến phải hỗ trợ các luồng cố gắng tối đa, những luồng này không có các yêu cầu dành trước tài nguyên. Nói cách khác, các giao thức và ứng dụng cố gắng tối đa hiện thời không cần phải thay đổi trong miền định tuyến dựa trên QoS.  Sơ đồ định tuyến được mong đợi là phải hỗ trợ định tuyến dựa trên QoS đa đích.  Sơ đồ định tuyến phải có quyền kiểm soát cho phép ở mức cao hơn, để hạn chế sự sử dụng tài nguyên tổng thể của các luồng riêng. 26 Trong phần này ta tập trung vào định tuyến dựa trên QoS nội miền, còn định tuyến dựa trên QoS liên miền sẽ được đề cập trong phần kế tiếp. Các vấn đề chính khi lựa chọn một đường dẫn, chẳng hạn như sự phức tạp, độ chính xác của thông tin định tuyến và sự ổn định định tuyến được phân tích dưới đây. Sau đó, định tuyến đa đích, định tuyến liên kết rời và định tuyến dựa trên dự báo cũng được trình bày ở phần cuối. 2.1.1. Vấn đề thuật toán lựa chọn đường đi Các phương pháp được sử dụng bởi các thuật toán định tuyến dựa trên QoS tính toán đường dẫn đa ràng buộc thì thường theo một thỏa hiệp giữa sự tối ưu của đường dẫn và độ phức tạp của thuật toán. Các nghiên cứu của các thuật toán tính toán đường dẫn mới nhằm cải thiện độ phức tạp và chất lượng của đường dẫn vẫn còn là một vấn đề mở trong lĩnh vực định tuyến dựa trên QoS. 2.1.1.1. Quá tải trong thuật toán định tuyến dựa trên QoS động Mục tiêu của giao thức định tuyến dựa trên QoS có thể bị thỏa hiệp bởi việc áp đặt thêm tải trong mạng. Tải trọng được giới thiệu bởi các phương pháp định tuyến dựa trên QoS bao gồm:  Quá tải xử lý do việc tính toán thường xuyên hơn và phức tạp hơn.  Việc lưu trữ bổ sung cần thiết để hỗ trợ các giao thức định tuyến dựa trên QoS.  Các quá tải truyền thông gây ra bởi sự gia tăng lượng thông tin định tuyến được trao đổi trong mạng. Cần lưu ý rằng tất cả những yếu tố này tác động chặt chẽ tới khả năng mở rộng mạng, tức là khả năng mở rộng trở thành một vấn đề phải được giải quyết bởi bất kỳ đề xuất định tuyến dựa trên QoS nào. Các quá tải xử lý gây ra bởi định tuyến dựa trên QoS là do 2 yếu tố chính, cụ thể là, sự phức tạp của thuật toán tính toán đường dẫn và tần suất tính toán đường dẫn. Vì số các ràng buộc cần được thỏa mãn bởi các thuật toán định tuyến ngày càng tăng lên. Độ phức tạp của thuật toán tính toán đường dẫn trở lên cao hơn, đòi hỏi khắt khe hơn trong việc xử lý các nguồn tài nguyên. Sau đó, trong trường hợp của phương pháp tính toán trước đường dẫn, các đường dẫn đảm bảo QoS đã cài đặt bảng định tuyến phải được cập nhật tình trạng mạng, và trong trường hợp tính toán đường dẫn theo yêu cầu, các đường dẫn phải được tính toán lúc tiếp nhận yêu cầu kết nối. Trong bất kỳ cách định tuyến nào, thuật 27 toán tính toán đường dẫn được sử dụng thường xuyên hơn trong các giao thức định tuyến truyền thống, do đó đòi hỏi xử lý các nguồn tài nguyên nhiều hơn. Mặc dù hầu hết các đề xuất định tuyến dựa trên QoS sử dụng tính toán đường dẫn theo yêu cầu, cách định tuyến này có hai nhược điểm. Thứ nhất, nó gây ra trễ trước khi bắt đầu chuyển tiếp lưu lượng. Thứ hai, nó đòi hỏi phải áp dụng các thuật toán tính toán đường đi cho mỗi yêu cầu kết nối, do đó đưa thêm quá tải xử lý trên các bộ định tuyến, đặc biệt là khi tỷ lệ đến của các yêu cầu kết nối không cao. Tính toán trước đường dẫn là cách tiếp cận khác để xử lý các vấn đề của quá tải xử lý kết hợp với tính toán đường dẫn theo yêu cầu do tác dụng phụ của sự thiếu chính xác cuối cùng của quyết định định tuyến [7]-[8]. Định tuyến dựa trên QoS làm tăng nhu cầu lưu trữ trong bộ định tuyến do sự tăng lượng thông tin trạng thái mạng và do kích thước của các bảng định tuyến dựa trên QoS. Thông tin được lưu giữ trong các bộ định tuyến bao gồm các metric mô tả trạng thái của các liên kết trong mạng như trễ, tỷ lệ mất mát và sử dụng, và dữ liệu thống kê về lưu lượng kết hợp được chuyển tiếp thông qua bộ định tuyến. Kích thước của các bảng định tuyến dựa trên QoS được xác định bởi loại lưu lượng sử dụng, và có thể thay đổi từ chỉ một đường vào cho mỗi đích đến trong mạng. Mặc dù định tuyến dựa trên QoS cần nhiều tài nguyên hơn, nhưng dung lượng bộ nhớ của các bộ định tuyến hiện tại hoàn toàn đủ khả năng đáp ứng, do đó nó không phải là một hạn chế nghiêm trọng cho việc triển khai các giải pháp định tuyến dựa trên QoS trong mạng. Trong trường hợp các giao thức trạng thái liên kết, quá tải truyền thông là do tải của quá trình “flooding” sử dụng trong việc trao đổi thông tin trạng thái liên kết giữa các bộ định tuyến trong mạng. Do các bộ định tuyến cần phải cập nhật trạng thái mạng để hỗ trợ các quyết định định tuyến chính xác, thông tin trạng thái cần phải được phân phối thường xuyên và vì thế có thể làm tăng quá tải truyền thông. Tác động của vấn đề này phụ thuộc vào các yếu tố như số lượng các tham số QoS, thang thời gian của quyết định định tuyến, mô hình định tuyến và sự tức thời của việc tính toán đường dẫn. Giao thức định tuyến dựa trên QoS dựa trên sự thăm dò có thể cũng đưa ra quá tải truyền thông trong mạng. Trong trường hợp này, quá tải là do các bản tin thăm dò được sử dụng để thu thập trạng thái của liên kết trong mạng hoặc để kiểm tra đường dẫn thay thế cần thiết cho các yêu cầu kết nối cụ thể. Số chi phí truyền thông do bản tin thăm dò tùy thuộc vào số lượng các bản tin tham dò ban hành, kích thước và tần suất phát ra của chúng. Các bản tin báo hiệu phát ra bởi các giao thức định tuyến dựa trên QoS, giao thức mà thực thi tính toán đường dẫn theo yêu cầu và thiết lập 28 đường dẫn là các yếu tố khác góp phần vào chi phí truyền thông. Các bản tin báo hiệu được sử dụng để yêu cầu tính toán các đường dẫn cụ thể cho việc tính đường dẫn theo yêu cầu và để cài đặt đường dẫn đảm bảo QoS tương ứng trên các nút dọc theo các đường dẫn đảm bảo QoS. Cách tiếp cận này gây gia tăng cả về truyền thông và quá tải xử lý. Việc giảm quá tải truyền thông có thể được thực hiện theo 2 cách bổ sung. Đầu tiên là giới hạn số lượng các bản tin định tuyến bằng cách giới hạn tần suất phát ra của bản tin cập nhật và bằng cách giới hạn số lượng các bộ định tuyến mà có đủ điều kiện để nhận bản tin cập nhật. Sự phân bố các bản tin cập nhật có thể được thực hiện ngay khi một sự thay đổi trạng thái xảy ra trong mạng. Tuy nhiên, cách tiếp cận này có thể dẫn đến quá tải truyền thông trên mạng và cũng có thể tạo ra sự bất ổn định. Thay vì phân phối các bản tin cập nhật ngay lập tức khi có một sự thay đổi, quá trình phân phối được điều khiển chung bởi chính sách kích hoạt. Quá trình “flooding” sử dụng bởi giao thức trạng thái liên kết gây ra lượng tải mà có thể tiêu thụ lượng tài nguyên quá mức trong mạng, đặc biệt là khi sử dụng trong các định tuyến có hoạch định dựa trên QoS. Việc lựa chọn các giải pháp “flooding” phù hợp có thể giảm chi phí gây ra bởi sự phát ra của các bản tin cập nhật trạng thái liên kết trên toàn mạng. Thứ hai là giảm kích thước của bản tin định tuyến. Sự quảng bá các số liệu định lượng, thay vì quảng bá các giá trị tức thời, là một phương pháp phổ biến để tránh các quá tải truyền thông quá mức của các giao thức định tuyến động. Cách tổ chức phân cấp của mạng cho phép kết hợp thông tin định tuyến giữa các cấp độ khác nhau và làm giảm lượng thông tin phải được phân phối và lưu trữ, trong khi giảm số lượng các thiết bị định tuyến liên quan đến việc trao đổi thông tin định tuyến. Các tư tưởng chiến lược cho việc kết hợp thông tin định tuyến phải có trong việc xem xét mức độ của sự kết hợp và hiệu quả hoạt động định tuyến. Khi kích thước của mạng phát triển, tải gây ra bởi các giải pháp định tuyến dựa trên QoS có thể trở nên quá mức, ảnh hưởng đến hiệu năng mạng. Vấn đề mở rộng quy mô liên quan đến lượng thông tin chảy trên mạng, tới sự phức tạp của thuật toán tính toán đường dẫn, và tới lượng thông tin lưu trữ và xử lý tại các bộ định tuyến. Các cơ chế có thể được sử dụng để điều khiển quá tải định tuyến và góp phần vào việc mở rộng quy mô bao gồm các số liệu định lượng và chính sách kích hoạt, lựa chọn flooding, tổng hợp thông tin và tính toán trước đường dẫn. 29 Các quá tải kết hợp với định tuyến dựa trên QoS là một hạn chế quan trọng để triển khai nó. Cụ thể, quá trình flooding sử dụng để phân phối thông tin trạng thái của mạng là một yếu tố quan trọng trong quá tải định tuyến dựa trên QoS. Quan điểm của các phương án định tuyến dựa trên QoS mới mà không dựa vào “flooding” hoặc khắc phục những khiếm khuyết của nó là một vấn đề cần được xem xét thêm. 2.2.1.2. Định tuyến dựa trên QoS theo thông tin không chính xác Việc sử dụng các thông tin định tuyến không chính xác bởi thuật toán tính toán đường dẫn có thể gây ảnh hưởng tới việc thực thi của các giao thức định tuyến dựa trên QoS. Vì vậy, người ta mong muốn rằng tình trạng của mạng lưu giữ ở tất cả các router luôn được cập nhật và phản ánh tình trạng của mạng một cách chi tiết và đầy đủ. Tuy nhiên, có một số yếu tố ngăn không cho thực hiện mục tiêu này, như mô tả dưới đây. Sự phân phối không thường xuyên của bản cập nhật trạng thái liên kết định tuyến là một trong những nguồn không chính xác của thông tin định tuyến. Trong trường hợp việc phân phối thông tin định tuyến được thực hiện định kỳ, những thay đổi trong trạng thái mạng xảy ra giữa hai lần cập nhật sẽ không được lan rộng, và do đó các đường dẫn đang sử dụng vẫn như cũ, dẫn đến phân phối lưu lượng không chính xác trong mạng. Một tình trạng tương tự xảy ra khi sự điều khiển việc phân phối các thông điệp định tuyến được thực hiện bởi các chính sách cập nhật, chẳng hạn như dựa trên ngưỡng hoặc dựa trên lớp. Nếu các thông số điều khiển chính sách cập nhật được cấu hình với độ nhạy thấp để hạn chế lượng truyền thông quá tải, thông tin trạng thái liên kết trong các bộ định tuyến sẽ trở thành cũ và các thuật toán tính toán đường dẫn có thể đưa ra quyết định định tuyến sai. Các đề xuất vận dụng thông tin trạng thái không chính xác phải đối phó với một thỏa hiệp giữa quá tải giao thức cần thiết để giữ thông tin trạng thái cập nhật và sự thiếu chính xác phát sinh do giới hạn của sự phát ra của bản cập nhật. Vì vậy, đề xuất khắc phục sự thiếu chính xác gây ra bởi thông tin trạng thái liên kết hết hiệu lực có hai mục tiêu chính, cụ thể là, để cải thiện hiệu suất của giao thức khi có thông tin thiếu chính xác trong định tuyến và giảm quá tải liên quan đến giao thức kết hợp với phân phối thường xuyên các bản cập nhật. Sự tổng hợp thông tin trong các mạng phân cấp cũng là một yếu tố quan trọng của thông tin định tuyến không chính xác trong các mạng lớn. Ngay cả trong các giao thức định tuyến nội miền, chẳng hạn như OSPF, các bộ định 30 tuyến được nhóm lại tại các khu vực để cho phép khả năng mở rộng và thời gian hội tụ nhanh hơn. Trong các mạng phân cấp, các số liệu định tuyến của liên kết vật lý được tổng hợp lại để hình thành tải lưu lượng của các liên kết logic, do đó cho rằng các router đều có trạng thái mạng là một xấp xỉ của các giá trị thực sự đại diện cho trạng thái của mỗi liên kết riêng biệt. Các nguồn khác của sự không chính xác là trễ truyền của các bản tin định tuyến trong các mạng lớn, việc sử dụng các ước tính về trạng thái hiện tại của mạng, và tác động của cơ chế đo đạc các metric được sử dụng. Do nhiều yếu tố, tình trạng chung được lưu giữ bởi mỗi router là một xấp xỉ của trạng thái thật sự thực tế. Khi các thuật toán tính toán đường dẫn sử dụng thông tin không chính xác này coi như nó là chính xác, thì hiệu suất của chúng có thể bị thiệt hại, và vì vậy phải tìm ra giải pháp được để giải quyết vấn đề này. Cách tiếp cận theo xác suất để giải quyết sự thiếu chính xác trong định tuyến nhằm mục đích tìm kiếm một đường dẫn thích hợp nhất phù hợp với yêu cầu mới, có tính đến thông tin có sẵn về trạng thái của mạng là không chính xác và biểu diễn bởi một hàm xác suất. Việc thăm dò dựa vào bản tin là một kỹ thuật nữa được sử dụng để đối phó với các thông tin trạng thái không chính xác. Việc sử dụng thăm dò tránh được sự mất hiệu lực của thông tin trạng thái liên kết bởi vì các thăm dò thu thập các thông tin trạng thái gần đúng nhất. Vấn đề của sự không chính xác về thông tin định tuyến liên quan chặt chẽ với phương thức sử dụng cho việc phân phối và tập hợp thông tin định tuyến, và như vậy kế hoạch định tuyến dựa trên QoS mới với vấn đề này cần được phát triển trong một cách tích hợp của cả hai cấp thuật toán và giao thức. 2.2.1.3. Tính ổn định của định tuyến dựa trên QoS Sự ổn định của các giao thức định tuyến dựa trên QoS là một yếu tố quyết định cho hoạt động của chúng. Sự bất ổn có thể xảy ra bất cứ khi nào đáp ứng của giao thức này trở nên quá mức, do đó không cần thiết tái định tuyến lưu lượng. Cụ thể, trong các giao thức trạng thái liên kết, “flooding” không phù hợp các bản cập nhật có thể sẽ làm suy giảm hiệu suất truyền lưu lượng. Điều này đặc biệt có vấn đề khi mạng bị ách tắc, kể từ khi các bản tin định tuyến bổ sung tiêu thụ các nguồn tài nguyên băng thông đã khan hiếm, và các ứng dụng tiếp theo của thuật toán tính toán đường dẫn áp đặt tải nhiều hơn cho bộ xử lý định tuyến. Các vấn đề về sự bất ổn định trong định tuyến bị ảnh hưởng bởi nhiều yếu tố, cụ thể là, các loại metric được sử dụng để tính toán đường dẫn tốt nhất, các 31 chính sách kiểm soát các thông báo metric và thuật toán tính toán đường dẫn. Topo mạng và các mô hình lưu lượng cũng ảnh hưởng đến sự ổn định và động thái của định tuyến. Cụ thể, việc định tuyến theo đường dẫn ngắn nhất dựa trên một sự tắc nghẽn căn cứ vào các metric liên kết thì rất dễ bị mất ổn định dưới tải trọng nặng và lưu lượng truyền loạt. Các cơ chế để kiểm soát các vấn đề bất ổn được giới thiệu ở trên có thể được phân loại, cụ thể là, liên quan đến cơ chế phân phối các metric, các thuật toán lựa chọn đường dẫn và cách xử lý lưu lượng khác nhau với các yêu cầu QoS khác nhau. Việc quảng bá các metric được lượng tử hóa là phương pháp đầu tiên để tránh việc định tuyến bất ổn định. Việc lượng tử hóa các metric có thể thực hiện bằng cách sử dụng một số trung bình đơn giản của các số liệu đo hoặc sử dụng các cơ chế trễ và các ngưỡng. Các kỹ thuật cân bằng tải cung cấp các cách sử dụng nhiều đường dẫn giữa một nguồn và một đích, để tránh các dao động định tuyến. Route-pinning và class-pinning cũng được sử dụng để hạn chế sự dao động định tuyến là những trường hợp mà các đường dẫn đảm bảo QoS có thể cung cấp một mức độ đầy đủ QoS. Sự ổn định và hiệu suất định tuyến tổng thể có thể được tăng lên bằng cách sử dụng các giao thức định tuyến xử lý các luồng lưu lượng theo khoảng thời gian của chúng, và giao thức thực hiện các tính toán tuyến đường theo lưu lượng hỗn hợp có xét đến các nhu cầu riêng của phương pháp truyền nỗ lực tối đa và lưu lượng nhạy cảm QoS. Khả năng thích ứng mong muốn của định tuyến dựa trên QoS không thể dẫn đến bất ổn định. Tuy nhiên, hai mục đích có thể là mâu thuẫn và các giải pháp cho mục đích này có thể phủ nhận việc thỏa mãn mục đích kia. Các thuật toán định tuyến dựa trên QoS mới cần được thiết kế để tránh các dao động định tuyến, trong khi cung cấp các đường dẫn thích hợp cho các loại hình lưu lượng trong mạng. 2.1.2. Định tuyến đa đích Vấn đề đa đích là vấn đề định tuyến từ một nút nguồn đơn đến một tập gồm p nút đích, hay còn được gọi là định tuyến từ một điểm tới đa điểm. Các tiến bộ trong công nghệ và các ứng dụng đa phương tiện nổi lên nhanh chóng đã cung cấp động lực lớn cho các ứng dụng đa đích (thời gian thực) mới. Nhiều ứng dụng đa đích (ví dụ, chơi game, hội nghị truyền hình) sẽ không hoạt động đúng nếu như QoS không được đảm bảo. Do đó, các thuật toán đa đích phải có khả năng đáp ứng một tập các ràng buộc về QoS. 32 Một đặc tính cơ bản của định tuyến đa đích là sử dụng hiệu quả các nguồn tài nguyên. Bởi vì mỗi một nút trong số p đích sẽ nhận thông tin như nhau, việc gửi thông tin p lần trên mỗi đường dẫn ngắn nhất tới mỗi nút đơn lẻ (đơn đích) là không hiệu quả, vì rất có thể sẽ có một vài sự chồng chéo giữa tập các đường dẫn ngắn nhất. Multicasting chỉ sao chép các gói tin nếu thấy cần thiết và điều này rõ ràng là hiệu quả hơn. Đối với trường hợp của một metric đơn, định tuyến nguồn đa đích có thể được thực hiện bởi việc chuyển tiếp gói tin của một luồng lưu lượng hoặc cây các đường dẫn ngắn nhất. Tuy nhiên, một cây đa đích có thể không phải luôn luôn đảm bảo các điều kiện ràng buộc về QoS đã được yêu cầu, trong khi nhiều phiên QoS đơn điểm phức tạp lại có thể. Tính chất này làm tăng sự phức tạp của định tuyến đa đích ràng buộc, vì chúng ta phải duy trì một tập hợp các đường dẫn hoặc các cây và chúng ta cần phải kiểm tra nếu không ràng buộc cực đại hoặc cực tiểu nào bị vi phạm (việc lọc topo đơn thuần có thể là thiếu). Một sự cân bằng giữa hiệu quả sử dụng tài nguyên và QoS đã được thực hiện. Thuật toán định tuyến đa ràng buộc thích ứng đa đích (MAMCRA) đã công nhận sự cân bằng này và tìm ra tập các đường dẫn ngắn nhất cho tất cả các đích đến và sau đó làm giảm việc tiêu thụ các nguồn tài nguyên mà không vi phạm các ràng buộc QoS. Cuối cùng, lấy ý tưởng từ đa đích không kết nối (CLM), chúng ta có các cơ chế Diffserv đa đích và các phiên bản của nó. Trong CLM, tiêu đề gói tin mang địa chỉ IP của tất cả các thành viên đa đích. Mỗi router xác định các chặng tiếp theo cho mỗi đích đến và xây dựng một tiêu đề mới cho mỗi chặng riêng biệt. Tiêu đề mới chỉ chứa các điểm đến mà chặng tiếp theo là trên đường dẫn ngắn nhất. Tương thích với Diffserv đơn điểm, chúng ta có thể mở rộng CLM, như vậy là mỗi gói tin thuộc về một lớp của dịch vụ nào đó (CoS) và mỗi router có một bảng định tuyến cho từng CoS. Định tuyến đảm bảo QoS dựa trên đích đến có thể chỉ được đảm bảo trong một mạng đang hoạt động. Nếu chúng ta lưu trữ lịch sử của một gói tin đang hoạt động trong phần mào đầu của nó, sau đó cho mỗi gói tin khi đến một bộ định tuyến, thì MAMCRA có thể được sử dụng để tính toán chiến lược chuyển tiếp hoặc sao chép tốt nhất. Chiến lược CLM được sử dụng tốt nhất trong các môi trường mang tính động cao (ví dụ không dây), vì chúng ta không cần (để tính toán lại) bảng định tuyến. Tuy nhiên, chúng ta cần phải có mô tả chính xác về mạng. 33 2.1.3. Định tuyến liên kết riêng biệt Vấn đề của việc tìm kiếm các đường dẫn rời rạc trong một mạng đã được quan tâm nhiều trong các tài liệu do lý thuyết của nó cũng như ý nghĩa thiết thực của nó cho nhiều ứng dụng, chẳng hạn như định tuyến tin cậy hoặc định tuyến có thể phục hồi. Các đường dẫn giữa một cặp nút nguồn và nút đích trong một mạng được gọi là liên kết riêng biệt nếu chúng không có liên kết chung (tức là chồng chéo), và nút riêng biệt, nếu, ngoài các nút nguồn và đích, chúng không có các nút chung. Với sự phát triển của các mạng quang và triển khai của các mạng MPLS hoặc GMPLS, vấn đề của việc tìm kiếm các đường dẫn rời nhau đang nhận được sự quan tâm mới nhờ phục hồi nhanh chóng sau một lỗi mạng. Trong các mạng truyền thông mạnh, kết nối thông thường bao gồm hai đường dẫn kết nối hoặc đường dẫn nút riêng biệt: một đường dẫn hoạt động và một đường dẫn sao lưu dự phòng. Một luồng lưu lượng dịch vụ sẽ được chuyển đến đường dẫn sao lưu dự phòng nếu đường dẫn hoạt động bị lỗi. Cân bằng tải, một khía cạnh quan trọng khác cho các mạng truyền thông là để tránh tắc nghẽn mạng và tối ưu hóa thông lượng mạng, cũng đòi hỏi các đường dẫn tách biệt để phân phối các luồng lưu lượng. Sự mạnh mẽ và cân bằng tải là hai khía cạnh của định tuyến dựa trên QoS. Nhìn chung một thuật toán các đường dẫn liên kết riêng biệt có thể được mở rộng cho một thuật toán nút riêng biệt với các khái niệm về sự chia tách nút, tức là thay thế một nút bằng hai nút được liên kết với nhau thông qua liên kết với các trọng số giá trị 0, và do đó chúng ta tập trung vào tìm hiểu định tuyến dựa trên QoS liên kết riêng biệt. Một phương pháp trực quan để xác định hai đường dẫn liên kết riêng biệt ngắn nhất giữa một cặp nút nguồn và đích gồm hai bước: bước đầu tiên là khôi phục lại đường dẫn ngắn nhất giữa một cặp nút trong sơ đồ hướng. Bước thứ hai là lược bớt tất cả các liên kết của đường dẫn từ sơ đồ hướng và tìm đường dẫn ngắn nhất trong sơ đồ hướng đã rút gọn. Phương pháp này có ít nhất hai nhược điểm: (1) cứ cho rằng tồn tại hai đường dẫn liên kết riêng biệt, không có đảm bảo rằng chúng sẽ được tìm thấy. (2) đường dẫn kết nối riêng biệt thứ hai có thể có chiều dài lớn hơn đáng kể so với đường dẫn ngắn nhất đầu tiên. Để vượt qua những bất lợi, các phương pháp khác đã được đưa ra để tìm kiếm một cặp đường dẫn kết nối riêng biệt với tổng chiều dài là nhỏ nhất. Trên thực tế, các kỹ thuật này không dễ dàng mở rộng cho định tuyến dựa trên QoS liên kết riêng biệt, thứ cần phải tuân theo các ràng buộc và có tổng chiều dài là tối thiểu. Kuipers và 34 Vawn Mieghem có đề xuất thuật toán định tuyến đa rằng buộc liên kết riêng biệt (DIMCRA), thuật toán thể hiện tốt hơn so với các phương pháp đơn giản loại bỏ một đường dẫn và tìm được đường dẫn riêng biệt thứ hai. 2.1.4. Phương pháp định tuyến dựa trên dự đoán Phương pháp định tuyến dựa trên dự đoán (PBR) đã được đề xuất như là một đề án tính toán trước trong các mạng truyền tải quang. Đã có nhiều nỗ lực được thực hiện để áp dụng PBR cho các mạng IP truyền thống. Có nhiều đề xuất xử lý liên quan tới các vấn đề về tính toán trước hoặc dự đoán, như ba đề xuất sau: (i) định tuyến hot-potato "dự đoán" đường dẫn tốt nhất đến đích dựa trên thông tin về độ trễ của các yêu cầu đến từ đích đó, (ii) đề xuất dự đoán tải thông tin tương lai trong một liên kết dựa trên các mẫu đo được trước đó của tải thông tin trong liên kết đó, và (iii) một biến thể của định tuyến hot-potato. Trái ngược với những đề xuất này, các liên kết dự đoán PBR với sự khả dụng của các đường dẫn thay vì dự đoán tải thông tin truy cập đến. PBR dựa trên những ý tưởng của sự dự báo nhánh trong kiến trúc máy tính. Bằng cách mở rộng khái niệm về dự đoán nhánh tới kiến trúc máy tính, nó sẽ là cần thiết để đăng ký lịch sử của trạng thái mạng từ quan điểm của nút nguồn, nghĩa là các nút nguồn chứa một đăng ký cho mọi tuyến từ nút đó, nút mà được cập nhật thông tin trạng thái mạng. Cần lưu ý rằng các đăng ký đó không được cập nhật bởi các bản tin cập nhật truyền thống (bao gồm cả thông tin trạng thái mạng), nhưng tại các chu kỳ thời gian nhất định. Thông tin thu được từ các đăng ký lịch sử được sử dụng để truy cập các bảng dự đoán. Trên thực tế, trong mọi nút nguồn có một bảng dự báo cho mỗi đường dẫn khả thi từ nút nguồn đó. Các bảng dự báo có các mục khác nhau, mỗi mục lưu giữ thông tin về một mô hình khác nhau bằng một bộ đếm hai bit. Dự báo thực hiện đọc giá trị của một bộ đếm hai bit. Một đường dẫn được lựa chọn chỉ với giá trị là 0 hoặc 1. Thuật toán được sử dụng để lựa chọn các đường dẫn được giải thích bằng một ví dụ. Chúng ta giả sử rằng giữa các cặp nguồn - đích có hai tuyến được tính toán, nhưng thuật toán có thể được thực hiện trong nhiều hơn hai đường dẫn. Việc đăng ký lịch sử thì chỉ ra băng thông trong chu kỳ cuối cùng với 2 bit. Hình dưới đây trình bày cho ví dụ sau: khi một yêu cầu mới đòi hỏi 40% băng thông của nút nguồn, lộ trình đầu tiên được kiểm tra. Thông tin mới nhất về băng thông chiếm dụng cho thấy là 40% băng thông đã được sử dụng trong 35 đường đầu tiên. Cả hai giá trị băng thông được cộng vào 40%+40%, và nếu nó nhỏ hơn 100% thì bảng dự đoán của tuyến đầu tiên được kiểm tra, nếu không thì các bảng dự đoán tiếp theo sẽ được kiểm tra. Trong trường hợp này, tổng băng thông là 80% (>75%) và chỉ số để truy cập vào bảng dự đoán đầu tiên là 0 (00 trong mã hóa 2 bit). Với chỉ số này trong bảng dự đoán của tuyến đường đầu tiên được truy cập và bộ đếm được đọc. Giả sử bộ đếm là 2, thì sau đó dự đoán không sử dụng tuyến đường đầu tiên này và có thể tuyến đường thứ hai sẽ được kiểm tra. Trong tuyến đường thứ hai băng thông bị chiếm dụng trong chu kỳ cuối là 25%. Băng thông mới này sẽ là 40%+25%=65%, tương ứng với một chỉ mục của 1 (01 với mã hóa 2 bit). Với chỉ số này trong bảng dự đoán của tuyến đường thứ hai được truy cập và giá trị bộ đếm là 1. Giá trị bộ đếm này có nghĩa là dự báo là sử dụng tuyến đường thứ hai này do đó thuật toán sẽ chọn tuyến đường thứ hai này. Hình 2.1. Ví dụ về việc dự đoán với 2 lộ trình Như đã nêu ở trên, các đăng ký lịch sử được cập nhật mỗi chu kỳ với thông tin về băng thông bị chiếm cho nút nguồn ở mỗi đường dẫn. Trong ví dụ cuối cùng, khi thuật toán lựa chọn đường dẫn thứ hai, băng thông mới bị chiếm dụng bởi nút này trong đường dẫn thứ hai này sẽ là 65%. Điều quan trọng cần lưu ý rằng băng thông chiếm dụng này chỉ là băng thông mà nút biết, nhưng nó có thể không phải là sự chiếm dụng thực sự. Tình huống này xảy ra do việc loại bỏ các bản tin cập nhật, khi các nút nguồn khác có thể sử dụng nhiều băng thông 40% 25% Đăng ký tuyến 2 Lưu lượng vào đòi hỏi 40% băng thông 1) (40+40)% băng thông 2) (25+40)% băng thông PT1 chỉ số=00 PT2 chỉ số=01 00 01 10 11 00 01 10 11 2 1 Bảng dự đoán Kiểm tra tuyến 2 Chọn tuyến 2 36 hơn trong các liên kết của cùng một đường dẫn và nút nguồn, thông tin chiếm dụng sẽ không được cập nhật. Chỉ có bảng dự đoán của các đường dẫn được lựa chọn là được cập nhật. Nếu kết nối được thiết lập thì bộ đếm tương ứng của bảng dự báo bị giảm, nhưng nếu kết nối bị chặn thì bộ đếm được tăng lên. Trong ví dụ trên, nếu kết nối được thiết lập bộ đếm của mục nhập 01 của bảng dự đoán của các đường dẫn 2 sẽ là 0, nhưng nếu kết nối bị chặn bộ đếm sẽ là 2. 2.2. Định tuyến QoS liên miền[14] Định tuyến liên miền được mong đợi là càng đơn giản càng tốt. Tính ổn định và tính co dãn là các đặc trưng quan trọng nhất ở mức này. Như vậy việc định tuyến không thể dựa chủ yếu trên thông tin trạng thái mạng động. Thay vào đó, sự trao đổi thông tin QoS giữa các miền định tuyến phải là khá tĩnh. Định tuyến liên miền phải có các chức năng cơ bản sau:  Xác định rõ đích thực hiện.  Tránh định tuyến lòng vòng.  Hỗ trợ việc gộp địa chỉ.  Xác định xem có đường nào tới đích hỗ trợ được các yêu cầu QoS hay không.  Xác định đa đường tới đích, dựa trên các lớp dịch vụ (đây là tuỳ chọn). Trong suốt những năm qua số lượng các hệ thống tự trị (AS) kết nối với Internet đã gia tăng lớn, mà theo đó làm tăng nhu cầu trên phạm vi mạng. Bất chấp gánh nặng này, giao thức cổng biên BGP đã chứng tỏ là một giao thức định tuyến linh hoạt. Những điểm mạnh đã làm BGP trở nên phổ biến là: thứ nhất giao thức này được thiết kế để giải quyết các vấn đề về khả năng mở rộng các nhu cầu kết nối với một quy mô rất lớn. Thứ hai, nó đã chứng minh được khả năng cung cấp ổn định cho các mạng lớn nhất từng được triển khai, và thứ ba, nó được ưu đãi với chính sách dựa trên các tính năng định tuyến cho phép từng miền quản trị ở các cạnh của một kết nối BGP để quản lý sự truyền tải luồng lưu lượng vào và ra của nó theo ưu tiên cụ thể và nhu cầu của nó. Cuối cùng, đáng chú ý là BGP có các cơ chế rất linh hoạt cho phép dễ dàng phát triển và mở rộng cho giao thức. Mặc dù BGP có nhiều điểm mạnh nhưng nó cũng còn một vài điểm yếu. Ví dụ, trong nhiều trường hợp BGP yêu cầu hàng chục phút để phục hồi từ một tuyến đường hoặc một liên kết thất bại. Hơn nữa, mặc dù BGP cho phép một hệ 37 thống tự trị để quản lý linh hoạt truyền tải luồng ra của nó, nó cho thấy một mức độ khan hiếm của điều khiển để quản lý và cân bằng lưu lượng đi vào một hệ thống tự trị như thế nào qua nhiều đường dẫn có thể. Thêm vào đó, mỗi router BGP chỉ thông báo tuyến đường tốt nhất mà nó biết đến bất kỳ đích nào được cho thêm vào đầu. Điều này có nghĩa là, các đường dẫn thay thế có thể được sử dụng bởi bất kỳ nguồn lưu lượng nào sẽ không được nhận ra bởi vì động thái lược bớt cố hữu của BGP. Các biện minh cho hành vi này là BGP về bản chất được thiết kế để giải quyết khả năng mở rộng và ổn định tổng thể thay vì liên quan đến các vấn đề như phục hồi nhanh chóng từ một thất bại liên kết cụ thể, hoặc độ trễ biên hoặc tỉ lệ mất gói qua internet cho một khối thêm vào phần đầu. 2.2.1. Các mở rộng QoS và kỹ thuật lưu lượng sử dụng BGP Nhiều nhà nghiên cứu và các nhà sản xuất đang cố gắng để tăng cường BGP với các khả năng mới như kỹ thuật lưu lượng, và các mở rộng QoS, chủ yếu là vì tính phổ biến và thành công của BGP tại thời điểm hiện tại. Điều quan trọng là mặc dù phiên bản chưa mở rộng của BGP thể hiện chức năng hữu hạn nhưng nó thực sự là một giao thức định tuyến phức tạp, nơi mà các lỗi và sự thiết lập cấu hình lỗi không phải là hiếm khi xảy ra. Hơn nữa, một vài nhóm nghiên cứu đã mở rộng BGP với sự khám phá và các khả năng báo hiệu mạng riêng ảo VPN ở lớp 2 và lớp 3. Kết quả là, những đề xuất để tăng cường BGP không chỉ có xu hướng biến nó thành giao thức phức tạp hơn, mà còn cho thấy nếu như sự bổ sung của tất cả các cải tiến này trong một môi trường thực không thể chôn vùi giao thức này. 2.2.2. Các phương pháp che phủ Thay vì tăng cường BGP, một sự lựa chọn cho định tuyến QoS liên miền là phương pháp che phủ, một phương pháp đã trở thành một ứng cử viên thích hợp để giải quyết vấn đề. Ý tưởng chính đằng sau các khái niệm che phủ là để tách riêng phần điều khiển chiến lược của quá trình định tuyến từ các thiết bị BGP. Trong ý nghĩa này, hai cách tiếp cận khác nhau cho vấn đề các chính sách được điều khiển và báo hiệu như thế nào. Các cải tiến BGP có xu hướng cung cấp việc truyền tín hiệu trong dải, trong khi phương pháp che phủ cung cấp sự truyền tín hiệu ngoài dải. Trong trường hợp này, điều quan trọng cần lưu ý là hiện nay cách duy nhất cho kỹ thuật lưu lượng liên miền trong các mạng IP là bằng phương pháp cấu hình thông minh BGP. Do đó, cuối cùng cả hai cơ chế dựa vào sự điều chỉnh thích hợp BGP để thực hiện theo các chính sách lưu 38 lượng tương ứng của chúng. Điều đáng chú ý là, trong khi các phương pháp tiếp cận trước đây cung cấp những cải tiến đáng kể cho internet định tuyến thấp, sau này thì hiệu quả hơn khi các thay đổi định tuyến xảy ra thường xuyên hơn. Trong khi các sự mở rộng quan trọng và các cải tiến đáng kể BGP chắc chắn sẽ được nhìn thấy, thì cấu trúc lớp che phủ đặt ra là một ứng cử viên mạnh mẽ để cung cấp định tuyến QoS liên miền ngoài dải giá trị gia tăng và linh hoạt. Đặc biệt, điều này trở lên hoàn toàn phù hợp khi mô hình lưu lượng liên miền cần phải thích nghi linh hoạt và phản ứng nhanh chóng với các điều kiện thay đổi của mạng trung bình và cao, nơi mà các giải pháp trước đây dường như không thể thực hiện tại thời điểm hiện tại. Kiến trúc lớp phủ thích hợp khi các miền truyền thông được multihomed, và do đó có thể cần một số loại cơ chế để nhanh chóng thay đổi hoạt động lưu lượng của chúng tùy thuộc vào các điều kiện mạng. Multihoming là xu hướng mà phần lớn các hệ thống tự trị sơ khai thực hiện trong internet ngày nay, mà chủ yếu là cố gắng để đạt được cân bằng tải và khả năng chịu lỗi trong kết nối mạng. Thực tế là, gần 80% của hơn 17000 hệ thống tự trị cấu thành internet là hệ thống tự trị sơ khai, nơi mà đa số các bộ phận được multihomed. Thêm vào đó, hiện nay các đặc tính lưu lượng liên miền tiết lộ rằng một hệ thống tự trị sẽ trao đổi lưu lượng với phần lớn internet, chỉ một số ít hệ thống tự trị chịu trách nhiệm về lưu lượng lớn nhất hiện tại. Hơn nữa, lưu lượng này chủ yếu là trao đổi giữa các hệ thống tự trị không được kết nối trực tiếp; thay vào đó chúng thông thường là 2, 3, 4 chặng cách xa. Như vậy, có thể hình thành một kiến trúc lớp phủ phân bố hoàn toàn và lớp định tuyến được thiết kế cụ thể để cung cấp định tuyến đảm bảo QoS liên miền giữa các hệ thống tự trị được multihomed không ngang hàng được lựa chọn theo chiến lược. Động lực quan trọng nhất cho lưu lượng ảnh hưởng theo cách này là với chỉ một số rất nhỏ thực thể lớp che phủ, nhưng nằm ở vị trí chiến lược được lựa chọn từ xa các hệ thống tự trị multihomed đủ để kiểm soát một phần quan trọng của lưu lượng cho loại hệ thống tự trị triển khai rộng rãi nhất trong Internet hiện nay. Một lợi thế lớn của chương trình này là không thực thể che phủ nào là cần thiết trong bất kỳ hệ thống truyền tải nào đang kết nối các hệ thống tự trị từ xa trong mô hình che phủ. Như vậy, sự phức tạp của sự cung cấp QoS động được đẩy tới mép của mạng bằng một cấu trúc lớp che phủ được phân phối. Trong đề xuất này một cặp thực thể che phủ trong hai hệ thống tự trị multihomed từ xa có thể trao đổi các thỏa thuận mức độ dịch vụ (SLA) liên quan đến lưu lượng trong số chúng, kiểm tra việc tuân thủ những thỏa thuận mức độ dịch vụ, và cấu hình 39 chính xác lớp BGP cơ bản đang chạy để bỏ qua các vấn đề của mạng như các liên kết hỏng, hoặc sự xuống cấp của các dịch vụ cho bất kỳ lớp của dịch vụ (CoS) nào. Bản chất của phương pháp này là sự nhận thức QoS giữa một cặp hệ thống tự trị từ xa về cơ bản là một trong những các thực thể che phủ lẫn nhau. Sự phức tạp của định tuyến QoS liên miền tăng lên đáng kể khi so sánh với các vấn đề của định tuyến QoS nội miền chủ yếu là do nhu cầu QoS đầu cuối (end-to-end) cho các khả năng dự phòng tài nguyên liên miền. Ngoài ra, có thể hình thành QoS liên miền end-to-end động mà không cần bất kỳ sự dự phòng tài nguyên nào, và để thực hiện theo các mô hình phi kết nối IP, miễn là QoS end-to-end linh hoạt là được đảm bảo. Một lần nữa, cách tiếp cận lớp phủ xuất hiện như là ứng cử viên hoàn hảo để cung cấp các loại giải pháp. Một thách thức lớn trong phương pháp che phủ là làm thế nào để cung cấp một sự kết hợp có hiệu quả cao giữa lớp định tuyến BGP cơ sở và lớp định tuyến che phủ. Hơn nữa, một cách tiếp cận hấp dẫn cho định tuyến QoS liên miền là để cung cấp một giải pháp bổ sung cho các vấn đề trong đó một kiến trúc lớp che phủ được phân bố hoàn toàn và một lớp định tuyến được sử dụng cho sự cung cấp QoS động, trong khi các mở rộng QoS và / hoặc các khả năng TE của lớp BGP cơ bản được sử dụng để cung cấp QoS tĩnh. Trong ý nghĩa này, cấu trúc lớp che phủ dẫn vào và tái sử dụng các nỗ lực tốt nhất trong lĩnh vực định tuyến QoS liên miền trong dải cho sự cung cấp QoS và/ hoặc TE động thấp. Như vậy, trong điều kiện của cấu trúc định tuyến liên miền cơ sở hai loại router BGP có thể hoạt động, cụ thể là, các router BGP không nhận thức QoS và các router BGP có nhận thức QoS (QBGP), nơi để phát triển khả năng mở rộng cao và các đề án định tuyến ổn định. Nó có tính bắt buộc rằng các router QBGP chỉ phân phối thông tin QoS động. Điều này chủ yếu là do các thay đổi mạng thường xuyên sẽ chuyển thành cập nhật BGP thường xuyên, điều mà có thể dẫn đến sự không ổn định định tuyến. Bản chất tác động trở lại của lớp định tuyến che phủ hoạt động sau đó như là một lớp bổ sung được hình thành để nâng cao hiệu quả hoạt động của lớp BGP cơ sở có chứa cả các router nhận thức và không nhân thức QoS. Các phương pháp tiếp cận lớp che phủ phân phối cho định tuyến QoS liên miền đưa ra một vài thách thức nghiên cứu. 2.2.3. Multihoming Các nghiên cứu gần đây cho thấy sự gia tăng của các bảng định tuyến Internet, bất chấp sự bùng nổ của công nghệ và sự hợp nhất trong các thị trường 40 cung cấp dịch vụ Internet. Các hiệp hội có bộ định danh hệ thống tự trị (ASid) riêng của họ và một phạm vi địa chỉ từ không gian địa chỉ. Chúng kết nối tới hai hay nhiều nhà cung cấp hơn để đạt được khả năng phục hồi trong việc truy cập Internet của chúng. Một tác dụng phụ tích cực của chiến lược này là tránh được việc lệ thuộc vào nhà cung cấp dịch vụ truy cập internet. Một trong những mục tiêu chính của IPv6 là để cung cấp sự kết hợp chặt chẽ không gian địa chỉ của lõi định tuyến, để tối ưu hóa quá trình định tuyến trong lõi và giữ cho kích thước của bảng định tuyến có thể quản lý được. Hơn nữa, đáng chú ý là triển khai thực tế của các mạng IPv6 thể hiện một mức độ cao về tái sử dụng các công nghệ, kỹ thuật và thực thi tốt nhất (ví dụ, các giao thức cổng ngoài trong Internet IPv6 là BGP4C, mà là một phần mở rộng của BGP phiên bản 4, giao thức cổng bên ngoài của Internet IPv4). Nhưng nếu multihoming (vấn đề trung tâm cho sự thành công của một mạng Internet dựa trên IPv6), như được biết trong Internet IPv4 và cũng được áp dụng trong IPv6, hiệu quả về kích thước bảng định tuyến IPv6 là dự đoán được. Với một không gian địa chỉ lớn hơn rất nhiều, kích thước của các bảng định tuyến trong lõi của một bộ định tuyến IPv6 với multihoming không kiểm soát được có khả năng bùng nổ vượt ra ngoài khả năng có thể điều khiển, hoặc ít nhất là vượt quá mức mà các thiết bị chuyển mạch lõi mang lại hiệu quả về giá có thể được sản xuất. Nỗ lực hơn nữa phải được dành cho việc đề xuất một phương pháp tiếp cận mới cho multihoming IPv6. Sự đồng thuận giữa các nhà cung cấp và khách hàng được xây dựng xung quanh một giải pháp mà là cả hai công nghệ âm thanh và khả năng thương mại là rất quan trọng. Điều này phản ánh trong một chu kỳ phát triển phức tạp cho một giải pháp hoàn chỉnh. Sự ổn định và khả năng tồn tại của Internet IPv6 tương lai - các tình trạng hiện tại của tiêu chuẩn hóa cho multihoming IPv6 không phải là rất đáng khích lệ. Multihoming trong IPv6 đã được xem như là một vấn đề của host cuối cùng, nhưng thực tế là các tiêu chuẩn IPv6 cho phép nhiều địa chỉ IPv6 được gán cho thiết bị đầu cuối kết thúc. Multihoming ở cấp độ nhà cung cấp đã không gây được nhiều sự chú ý, hoặc, và một số kiến nghị cho cấu trúc kết nối của các ISP đã không tạo ra lợi ích đủ và do đó, chưa bao giờ được phát huy từ bản dự thảo Internet cho RFC. Multihoming tại mức ISP là một thực tế phổ biến trên mạng Internet ngày nay. Hai điều quan trọng chính của BGP-4 là hỗ trợ multihoming đang được sử dụng. Các công ty nhỏ kết nối Internet của họ mua từ một nhà cung cấp có thể được 41 kết nối qua hai hay nhiều liên kết độc lập, để nâng cao độ tin cậy. Trong trường hợp này, khách hàng sử dụng một định danh hệ thống tự trị trong cái ngang hàng của nó với nhà cung cấp. Trong trường hợp phạm vi địa chỉ được chỉ định cho khách hàng không phải là được kết hợp lại thành một trong những phạm vi địa chỉ của nhà cung cấp, định danh này được loại bỏ tại các điểm ngang hàng của nhà cung cấp và phạm vi địa chỉ của khách hàng xuất hiện như là một trong các phạm vi địa chỉ của nhà cung cấp. Khi multihoming cho nhiều nhà cung cấp, khách hàng multihoming cần một định danh hệ thống tự trị công cộng, cái mà sự tiến bộ qua tất cả sự ngang hang BGP-4 tới các bảng định tuyến của Internet. Dịch vụ thông tin định tuyến (RIS) của RIPE có trên 300 đồng nghiệp IPv4 và IPv6 tại 12 điểm thu thập dữ liệu trên toàn thế giới, trong đó thu thập và lưu trữ thông tin định tuyến (BGP) và làm cho nó công khai có thể dùng được cho cộng đồng Internet. Các cơ sở dữ liệu RIS quản lý một số lượng lớn các dữ liệu định tuyến và các đặc tính của IPv4/IPv6 đã được trộn lẫn của các kho chứa hiện tại tạo ra một chi phí rất lớn trong quá trình xử lý. Điều này có thể được khắc phục bằng cách thiết lập mới, các kho chứa tuyến đường cụ thể IPv6 trong cơ sở hạ tầng thuần túy IPv6. Ứng cử viên cho các môi trường triển khai cho các kho chứa định tuyến mới là các dự án IST khác nhau trong Chương trình framework lần thứ 6, trong đó đã thực hiện bản IPv6 trong cơ sở hạ tầng mạng cũng như mạng lưới nghiên cứu quốc gia, trong đó đã triển khai hoặc đang triển khai hạ tầng mạng thuần túy IPv6. Trong phạm vi nghiên cứu multihoming IPv6, các công cụ RIS cần phải được tăng cường với các công cụ chuyên ngành, trong đó nghiên cứu tác động của việc thực hiện multihoming trong các mạng IPv6 mới xuất hiện. Việc nghiên cứu các thực thi multihoming hiện tại và tác động của chúng trên Internet hiện nay chỉ nên được coi là một điểm khởi đầu. Giao thức định tuyến BGP-4 có một lỗ hổng trong thiết kế của nó. Trong khi các giao thức định tuyến khác có một mục tiêu rõ ràng, tức là tìm các tuyến đường giữa hai điểm sao cho là tối ưu theo tập tiêu chí đã định rõ, mục tiêu chính của BGP-4 là cung cấp liên tục tuyến giữa các miền định tuyến tự trị. Sự độc lập trong chính sách giữa các hệ thống tự trị và tính mở của các chính sách định tuyến bên ngoài hệ thống tự trị dẫn đến bất ổn. Nghiên cứu về những mâu thuẫn của BGP-4 đã dẫn đến việc phát hiện ra các tình huống, nơi mà các hành động phối hợp của các quản trị viên của hơn hai miền định tuyến là cần thiết để khôi phục lại sự ổn định trong một tiểu khu nhất định của Internet. Một lớp che phủ quản lý định tuyến, mà có thể có khả năng phát hiện và tránh những loại 42 tình huống sẽ cải thiện lớn chất lượng của Internet IPv6. Như một lớp phủ sẽ có những sự cái mà sẽ cho rằng quyền tự chủ của các hệ thống tự trị được đặt trong nguy hiểm bởi cách tiếp cận như vậy. Một chuyển đổi mô hình là cần thiết và một số thực thi hiện tại đã được sửa đổi. Cạnh tranh, nhưng sự hợp tác giữa các nhà cung cấp dịch vụ Internet sẽ có thể đạt được các mức độ dịch vụ tốt hơn so với các nhà cung cấp Internet bị cô lập. 2.3. Bảng định tuyến Dù là nội miền hay liên miền, chức năng chính của một Router là chuyển gói tin đến mạng đích của nó, để làm được điều này Router cần phải tìm được thông tin định tuyến được lưu trữ trên bảng định tuyến của nó. Một bảng định tuyến là một file dữ liệu trong RAM được dùng để lưu trữ thông tin đường đi các đường mạng được kết nối trực tiếp hoặc từ xa. Bảng định tuyến của mỗi giao thức định tuyến là khác nhau, nhưng có thể bao gồm những thông tin sau :  Địa chỉ đích của mạng, mạng con hoặc hệ thống.  Địa chỉ IP của router chặng kế tiếp phải đến  Giao tiếp vật lý phải sử dụng để đi đến router kế tiếp  Mặt nạ mạng của địa chỉ đích  Khoảng cách đến đích, ví dụ như số lượng chặng để đến đích  Thời gian (tính theo giây) từ khi router cập nhật lần cuối Định tuyến có hai loại: định tuyến tĩnh và định tuyến động  Định tuyến tĩnh: Định tuyến tĩnh do người quản trị phải cấu hình cố định các thông tin đến các mạng khác cho router. Quyết định định tuyến tĩnh không dựa trên sự đánh giá lưu lượng và topo mạng hiện thời. Trong môi trường IP các router không thể phát hiện ra các router mới, chúng chỉ có thể chuyển gói tin tới các router được chỉ định của nhà quản lý mạng. Khi cấu trúc mạng có bất kì thay đổi nào thì người quản trị mạng phải xóa hoặc thêm các thông tin về đường đi cho router. Các đường đi này là cố định nên trong hệ thống mạng lớn việc bảo trì bảng định tuyến cho router tốn rất nhiều thời gian. Định tuyến tĩnh là cách định tuyến không linh hoạt nên thường phù hợp với hệ thống mạng nhỏ hoặc tuyến đơn ít có biến đổi 43 về thông tin định tuyến. Hoạt động của định tuyến tĩnh gồm 3 bước chính sau: o Người quản trị cấu hình các đường đi cố định cho router o Router cài đặt các thông tin này vào bảng định tuyến o Gói tin được định tuyến theo các đường cố định đã được cài đặt.  Định tuyến động: Định tuyến động lựa chọn tuyến dựa trên thông tin trạng thái hiện thời của mạng. Thông tin trạng thái có thể đo hoặc dự đoán và tuyến đường có thể thay đổi khi topo mạng hoặc lưu lượng mạng thay đổi. Thông tin định tuyến được cập nhật tự động vào trong các bảng định tuyến của các nút mạng trực tuyến, và đáp ứng tính thời gian thực nhằm tránh tắc nghẽn cũng như tối ưu hiệu năng mạng. Định tuyến động phù hợp đối với mạng lớn, thường biến đổi trong quá trình hoạt động. Giao thức định tuyến được sử dụng để giao tiếp giữa các router với nhau. Giao thức định tuyến cho phép router chia sẻ các thông tin định tuyến mà nó biết cho các router khác. Từ đó router có thể xây dựng và bảo trì bảng định tuyến của nó. Một số giao thức định tuyến động thường được sử dụng như: RIP, IGRP, EIGRP, OSPF, BRP. Các giao thức này thực thi nhiều hoạt động như là: khám phá mạng và cập nhật, duy trì các bảng định tuyến. Các giao thức định tuyến động này không chỉ tạo ra một đường đi xác định tốt nhất đến các mạng khác mà còn xác định một đường dẫn mới tốt nhất khi đường đi khởi đầu không còn hữu dụng hoặc có sự thay đổi topology. Với những lý do đó, định tuyến động có lợi thế hơn so với định tuyến tĩnh. Các Router mà sử dụng các giao thức định tuyến động chia sẻ bảng định tuyến một cách tự động với các Router khác và bổ sung cho bất cứ sự thay đổi topology mà không liên quan đến quản trị viên mạng. Chúng ta thừa nhận rằng: (1) Tất cả các nút lưu giữ các số liệu nội bộ của chúng và (2) tất cả các nút nhận biết được khi gửi cập nhật tới các nút hàng xóm của nó. Giả định (1) hợp lý khi một nút luôn biết tài nguyên khả dụng trong các liên kết outgoing của nó. Giả định (2) sẽ trở lên hợp lý, nếu một chính sách cập nhật được thực thi. Trong phần này, chúng ta có thể sử dụng một chính sách cập nhật dựa trên ngưỡng. Mỗi nút duy trì một bảng link-to-node. Bảng này đưa ra liên kết sử dụng để dẫn tới một nút hàng xóm và nguồn khả dụng dọc theo liên kết. Một nút có thể dễ dàng xây dựng bảng định tuyến bằng cách trao đổi các gói tin Hello với hàng xóm của nó. Mỗi nút xây dựng một bảng link-to-node. 44 2.3.1. Cơ chế trao đổi thông tin để xây dựng bảng định tuyến Mỗi router duy trì một bảng định tuyến. Trong việc tiếp nhận một thăm dò nhu cầu kết nối, một router sử dụng bảng định tuyến để quyết định liên kết đầu ra. Chúng ta xem xét một nút:  )(1 vN biểu thị các nút gần kề với nút v trong mạng  )(1 vE biểu thị các liên kết kết nối nút v tới các nút trong )(1 vN  )(2 vN biểu thị các nút gần kề với các nút trong )(1 vN  )(2 vE biểu thị các liên kết kết nối các nút trong )(1 vN tới các nút trong )(2 vN Bảng định tuyến của nút v chứa thông tin về các số liệu của tất cả các liên kết trong )(1 vE và )(2 vE . Các mục vào (entry) tương ứng với )(1 vE được gọi là các mục vào mức một 1vR của v; các mục vào tương ứng với )(2 vE được gọi là các mục vào mức hai 2vR của v. Các mục vào mức hai được biểu diễn như một bộ của 21, ji ll trong đó )( 11 vEli  và )(22 vEl j  . Nếu một nút u là một thành viên của cả )(1 vN và )(2 vN , thì nó được biểu diễn chỉ như là một mục vào mức một. Để xây dựng và duy trì bảng định tuyến, nút v phải nhận bản cập nhật về các tham số QoS trong tất cả các mục vào mức hai của nó từ các nút trong )(1 vN . Việc này được thực hiện bởi việc trao đổi các bản tin đặc biệt gọi là các gói tin Hello2 với một tần suất xác định được điều khiển bởi chính sách cập nhật. Các gói tin Hello2 được xây dựng bằng cách sao chép danh sách hàng xóm và các thông số QoS có được từ bảng định tuyến của các router. Tại nút v, các mục vào mức một trong bảng định tuyến được tạo ra bằng cách sao chép bảng định tuyến của nút v. Các mục vào mức hai trong bảng định tuyến được tạo ra bằng cách kiểm soát việc nhận các gói tin Hello2. Tất cả các mục vào mức hai tồn tại trong bảng định tuyến được cập nhật bởi gói tin Hello2. Ngoài ra, một vài mục vào mới được thêm vào các mục vào mức hai hiện tại. 2.3.2. Các chính sách cập nhật Ý tưởng chính của việc gửi các gói tin Hello2 là để truyền tải những sự thay đổi trong tài nguyên sẵn có của một router tới các router khác. Nếu một router gửi các gói tin Hello2 mỗi khi có một sự thay đổi xuất hiện, thì mạng có thể bị quá tải. Để giảm quá tải này, một chính sách cập nhật được thi hành. 45 Chính sách cập nhật này sẽ được lựa chọn khi các gói tin Hello2 được gửi. Một chính sách cập nhật đơn giản có thể dựa trên các bộ định thời và nó có thể giống như là một bản cập nhật được gửi đi cứ mỗi T giây. Các giao thức như OSPF và RIP gửi các bản cập nhật ở những khoảng thời gian đều nhau. Tr