- ii DANH MỤC THUẬT NGỮ TIẾNG ANH SANG TIẾNG VIỆT TT Tiếng anh Dịch nghĩa 1 Unicast route Định tuyến đơn đích 2 Multicast route Định tuyến đa đích 3 Multicast networks Mạng đa đích 4 Multicast session Một phiên đa đích 5 Multicast group Nhóm đa đích 6 Multicast tree Cây đa đích 7 Delay Minimization Cực tiểu hóa độ trễ 8 Cost minimization Chi phí cực tiểu 9 Congestion minimization Cực tiểu hóa tình trạng tắc nghẽn 10 Cache placement Vị trí bộ nhớ cache 11 Steiner tree-based Cây cơ sở Steiner 12 Center – based tree Cây cơ sở trung tâm 13 Source – based routing Định tuyến cơ sở nguồn 14 Topological center Tâm tô pô 15 Steiner tree – based Cây Steiner cơ sở 16 Core Based Trees Cây dựa vào lõi 17 Shared trees Cây chia sẻ 18 NP – hard NP – khó iii DANH MỤC TỪ TIẾT TẮT TT Từ viết tắt Tiếng anh Tiếng việt 1 OSPF Open Shortest Path First Giao thức định tuyến đường liên kết đầu tiên theo chuẩn mở 2 PIM Protocol Independent Multicast Định tuyến đa đích không phụ thuộc giao thức 3 DVMRP Distance Vector Multicast Routing Protocol Giao thức định tuyến đa đích với vecto khoảng cách 4 MOSPF Multicast OSPF Giao thức định tuyến đa đích đường liên kết đầu tiên theo chuẩn mở 5 CBT Core Based Trees Cây dựa vào lõi 6 PIM - DM PIM Dense Mode Định tuyến đa đích không phụ thuộc giao thức chế độ dày 7 PIM – SM PIM Sparse Mode Định tuyến đa đích không phụ thuộc giao thức chế độ thưa 8 RIP Routing Information Protocol Giao thức định tuyến thông tin 9 RP Rendezvous Point Điểm hẹn 10 RPT Rendezvous Point Tree Cây điểm hẹn 11 RPF Reverse Path Forwarding Chuyển tiếp theo đường dẫn ngược 12 DR Tái cấu hình động 13 LSA Link-State Advertisement Trạng thái liên kết quảng cáo 14 ASBR Autonomous System Border Routers Bộ định tuyến biên hệ thống độc lập 15 MASBR Multicast AS Border Router Bộ định tuyến biên đa đích hệ thống độc lập iv 16 IETF Internet Engineering Task Force Lực lượng quản lý kỹ thuật Internet 17 CLM 18 QoS Quality of Service Chất lượng dịch vụ 19 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 20 MST Minimum Spanning Tree Cây bao trùm tối thiểu 21 BDB Bounded Delay Broadcast Quảng bá độ trễ bị chặn 22 B2B business-to-business Mô hình thương mại điện tử giữa các công ty 23 CBT core-based tree Cây cơ sở lõi 24 BDB Bounded Delay Broadcast v MỤC LỤC LỜI CẢM ƠN. - Lý thuyết đồ thị. - Một số thuật toán cơ bản trên đồ thị. - Thuật toán Prim. - Thuật toán Dijkstra cơ bản. - Các giao thức. - Các giao thức Multicast chính. - Giao thức định tuyến multicast với vecto khoảng cách. - Giao thức PIM (Protocol Independent Multicast. - 17 Chƣơng 1: BÀI TOÁN ĐỊNH TUYẾN ĐA ĐÍCH. - Giới thiệu bài toán định tuyến đa đích. - Các bài toán tối ƣu hóa. - Bài toán cực tiểu hóa độ trễ (Delay Minimization. - Ứng dụng định tuyến đa đích. - 27 Chƣơng 2: CÁC THUẬT TOÁN GIẢI BÀI TOÁN ĐỊNH TUYẾN ĐA ĐÍCH. - Phân loại các thuật toán (Algorithm Classification. - Các thuật toán cơ bản. - Thuật toán lan tràn (Flooding Algorithm. - Bài toán đường đi ngắn nhất với hạn chế độ trễ (Shortest Path Problems with Delay Constraints. - Các thuật toán phân tán. - Thuật toán phân tán cho định tuyến đa đích ((Định nghĩa thuật toán phân tán)-(Distributed Algorithm Concepts. - Thuật toán phân tán cho audio và video trên đa đích (Distributed Algorithm for Audio and Video on Multicast. - Thuật toán cho các nhóm Sparse (Algorithms for Sparse Groups. - 46 vii Chƣơng 3: GIẢI THUẬT DIJKSTRA CẢI BIÊN GIẢI BÀI TOÁN ĐỊNH TUYẾN ĐA ĐÍCH. - Phát biểu bài toán tối ƣu trong mạng định tuyến đa đích. - Áp dụng giải thuật dijkstra cải biên để giải quyết bài toán định tuyến đa đích. - 63 DANH MỤC TÀI LIỆU THAM KHẢO viii DANH MỤC HÌNH ẢNH, BẢNG Hình 0.1.1: Một đồ thị đơn giản. - 3 Hình 0.3.1.1: Khái niệm tổ chức của một nhóm đa đích. - 9 Hình 0.3.2.1: Tìm hàng xóm trong DVMRP. - 11 Hình 0.3.2.2: Cắt nhánh trong DVMRP. - 11 Hình 0.3.3.3: Ghép nhánh trong DVMRP. - 12 Hình 1.2.1: Ví dụ đơn giản của vấn đề định tuyến đa đích (multicast routing. - 20 Hình 3.1.1: Đồ thị G = (V, E) với nút nguồn s. - 51 Hình 3.1.2: Đồ thị G = (V, E) với đường màu đỏ thể hiện đường truyền tin từ nút nguồn s đến các nút đích 1, 2, 3. - Đồ thị G = (V, E) với đường màu đỏ thể hiện đường truyền tin từ nút nguồn s đến các nút đích 1, 2, 3. - 52 Hình: 3.3.1: Đồ thị G = (V, E) và nút nguồn s. - 55 Hình 3.3.2: Bước 1. - 56 Hình 3.3.3: Bước 2. - 56 Hình 3.3.4: Bước 3. - 57 Hình 3.3.5: Bước 4. - 57 Hình 3.3.6: Bước 5. - 58 Hình 3.3.7: Bước 6. - 58 Hình 3.3.8: Đáp số của bài toán. - 59 Bảng 1: So sánh các thuật toán cho bài toán định tuyến đa đích với hạn chế độ trễ LỜI MỞ ĐẦU Ngày nay với sự bùng nổ của nghành công nghệ thông tin, mạng internet có những bước nhảy vọt trong việc cung cấp dịch vụ cho khách hàng. - Điều này chứng tỏ internet đã và đang làm thay đổi cuộc sống của con người, làm cải thiện công việc kinh doanh, giải trí, giáo dục cũng như các phương thức liên lạc … Một trong những hoạt động của mạng nói chung là việc truyền dữ liệu từ nguồn tới đích. - Định tuyến là một chức năng không thể tách rời của mạng truyền thông khi kết nối từ điểm xuất phát tới điểm đích và có ý nghĩa đặc biệt quan trọng trong việc thiết kế và tối ưu hóa mạng. - Cấu trúc mạng, giải pháp công nghệ, phương pháp định tuyến và các phương pháp giải quyết bài toán thiết kế mạng là các vấn đề liên quan mật thiết với nhau và quyết định chất lượng hoạt động của mạng. - Chính vì vậy, bài toán thiết kế mạng với đường truyền ngắn nhất cần được quan tâm nghiên cứu để nhằm tối ưu hóa sử dụng tài nguyên mạng. - Trên thế giới đã có nhiều nghiên cứu về các phương pháp định tuyến với mục đích là tìm ra những phương pháp định tuyến thích hợp để áp dụng vào thực tế mạng lưới. - Trong thời gian gần đây, xu hướng định tuyến tối ưu cho mạng đã trở thành một chủ đề nghiên cứu quan trọng. - Mục đích của đề tài: Tìm hiểu thuật toán phân tán giải bài toán định tuyến đa đích. - Tìm hiểu về các thuật toán giải quyết bài toán. - Triển khai cài đặt các thuật toán và tiến hành thực nghiệm để đánh giá hiệu quả của các thuật toán đã tìm hiểu. - “Các thuật toán phân tán giải bài toán định tuyến đa đích” là một trong các cách tiếp cận để giải quyết vấn đề đặt ra. - Phƣơng pháp nghiên cứu: Kết hợp nghiên cứu lý thuyết, tìm hiểu về bài toán định tuyến đa đích và phương pháp giải quyết, đánh giá… Nội dung luận văn được chia làm 5 chương: Chương 0: Các khái niện cần thiết Chương 1: Bài toán định tuyến đa đích Chương 2: Các thuật toán giải bài toán định tuyến đa đích Chương 3: Giải thuật Dijkstra cải biên giải bài toán định tuyến đa đích Chương 4: Xây dựng chƣơng trình và cài đặt thực nghiệm 3 Chƣơng 0: CÁC KHÁI NIỆM CẦN THIẾT Chương này trình bày một số khái niệm cần thiết cho việc trình bày các nội dung tiếp theo của luận văn. - Lý thuyết đồ thị Một đồ thị G, được định nghĩa bởi tập các đỉnh V và tập các cạnh E. - Các đỉnh thường được gọi là các nút (node) và chúng biểu diễn vị trí cho các thành phần trong mạng (ví dụ một điểm chứa lưu lượng hoặc một khu vực chứa thiết bị truyền thông, nguồn hoặc các điếm đến). - Các cạnh được gọi là các liên kết và chúng biểu diễn phương tiện truyền thông. - Đồ thị có thể được biểu diễn như sau: G = (V, E) Đồ thị vô hướng: là đồ thị mà tất cả các cạnh trong đồ thị đều là cạnh vô hướng. - Đồ thị có hướng: là đồ thị mà tất cả các cạnh trong đồ thị là cạnh có hướng (còn gọi là cung). - Hình 0.1.1: Một đồ thị đơn giản Mặc dù theo lý thuyết, V có thể là tập hợp rỗng hoặc không có xác định nhưng thông thường V là tập hợp xác định khác rỗng, nghĩa là có thể biểu diễn V = {vi | i = 1, 2, …,N} 4 Trong đó N là số lượng nút. - Có thể biểu diễn liên kết ej giữa nút i và k bởi: ej = (vi,vk) hoặc ej = (i,k). - Một liên kết gọi là đường đi tới một nút nếu đó là một trong hai điểm cuối của liên kết. - Nút i và k gọi là kề nhau nếu tồn tại một liên kết (i,k) giữa chúng. - Những nút như vậy được xem là các nút “hàng xóm”. - Bậc của nút là số lượng liên kết đi tới nút hay là số lượng nút hàng xóm. - Tuy nhiên với các graph có nhiều hơn một liên kết giữa cùng một cặp nút, thì hai khái niệm trên là không tương đương. - Trong trường hợp đó, bậc của một nút được định nghĩa là số lượng liên kết đi tới nút đó. - Một liên kết có thể có hai hướng. - Khi đó thứ tự của các nút là không có ý nghĩa. - Ngược lại thứ tự các nút có ý nghĩa. - Trong trường hợp thứ tự các nút có ý nghĩa, một liên kết có thể được xem như là một cung và được định nghĩa: aj = [vj,vk] hoặc aj = [i,k]. - k được gọi là cận kề hướng ra đối với i nếu một cung [i,k] tồn tại và bậc hướng ra của i là số lượng các cung như vậy. - Một graph gọi là một mạng nếu các liên kết và các nút có mặt trong liên kết có các thuộc tính (chẳng hạn như độ dài, dung lượng, loại. - Các mạng được sử dụng để mô hình các vấn đề cần quan tâm trong truyền thông, các thuộc tính riêng biệt của các nút và liên kết thì liên quan đến các vấn đề cụ thể trong truyền thông. - Một đồ thị có các liên kết gọi là đồ thị vô hướng, tuy nhiên một graph có các cung gọi là đồ thị hữu hướng. - Một graph hữu hướng có thể có cả các liên kết vô hướng. - 5 Có thể có khả năng xảy ra hiện tượng xuất hiện nhiều hơn một liên kết giữa cùng một cặp nút(điều này tương ứng với việc có nhiều kênh thông tin giữa hai chuyển mạch). - Những liên kết như vậy gọi là các liên kết song song. - Một đồ thị có có cạnh lặp gọi là một đa đồ thị. - Cũng có khả năng xuất hiện các liên kết giữa một nút nào đó và chính nó. - Những liên kết đó được gọi là các khuyên. - Một đồ thị không có cạnh lặp hoặc các khuyên gọi là một đơn đồ thị. - Với mỗi cạnh (i, j) E, chúng tôi có thể kết hợp các hàm đại diện cho đặc điểm của các liên kết mạng. - Đối với mỗi cạnh (i, j) E, thông lượng c(i, j) cho biết số lượng dữ liệu tối đa có thể được gửi giữa các nút i và j. - Trong các ứng dụng multicast, các thông lượng là các số nguyên , vì vậy có thể nói c(i, j) Z+, với mọi (i, j) E. - Hàm chi phí: hàm w(i, j): Z x Z R được sử dụng để mô tả bấy kỳ chi phí phát sinh cho việc sử dụng các liên kết giữa các nút i và j. - Độ trễ d(i, j) đại diện cho thời gian cần thiết để truyền tải thông tin giữa các nút i và j. - Như một ví dụ điển hình, các ứng dụng video có thể yêu cầu cụ thể về thời gian truyền. - Mỗi gói tin i có thể được đánh dấu độ trễ tối đa di có thể cho phép cho quá trình truyền dẫn. - Trong trường hợp này, các bộ định tuyến phải xem xét duy nhất một đường với tổng độ trễ là di. - Một số thuật toán cơ bản trên đồ thị 0.2.1. - Thuật toán Prim Ý tưởng. - {Q là tập các đỉnh chưa ở trong cây khung} 3. - Thuật toán Dijkstra cơ bản Lịch sử của giải thuật Dijkstra: Thuật toán Dijkstra mang tên của nhà khoa học máy tính người Hà Lan Edsger Dijkstra vào năm 1956 và ấn bản năm 1959, là một thuật toán giải quyết bài toán đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh trong đồ thị (không có cạnh mang trọng số âm). - Giải thuật là một trong những bài toán tối ưu trên đồ thị và được ứng dụng rộng rãi trong thực tế cũng như các ứng dụng thú vị trong nghành toán học rời rạc(ví dụ như ứng dụng trong mạng định tuyến hay trong công nghệ Hệ thống định vị toàn cầu (GPS. - Đặc trưng của thuật toán dijkstra: Giải quyết bài toán tìm đường đi ngắn nhất giữa 1 cặp đỉnh và bài toán tìm đường đi ngắn nhất từ một nguồn tới mọi đích. - Đồ thị G(V,E) trong đó V là tập đỉnh, E là tập cạnh có trọng số không âm - Đỉnh nguồn s: s V 8 Dữ liệu ra: Đường đi ngắn nhất từ đỉnh nguồn S đến tất cả các đỉnh còn lại Phương pháp: Sử dụng hai mảng trung gian D và P gồm n phần tử. - Với n là số đỉnh trong đồ thị. - D[i] chứa khoảng cách từ đỉnh s đến đỉnh i, P[i] chứa đỉnh ngay trước i trong đường đi ngắn nhất từ s đến i tại một thời điểm
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt