Đề tài 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