Đề tài Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc

Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 1 ĐH Công nghệ - ĐH Quốc Gia HN TRƯỜNG …………………. KHOA………………………. -----[\ [\----- Báo cáo tốt nghiệp Đề tài: SỬ DỤNG TÁC TỬ DI ĐỘNG PHÁT HIỆN DỊCH VỤ TRONG CÁC MẠNG NGANG HÀNG KHÔNG CÓ CẤU TRÚC Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 2 ĐH Công nghệ - ĐH Quốc Gia HN LỜI CẢM ƠN Tôi xin gửi lời cảm ơn tới các thầy cô trong khoa Công nghệ Thông tin trường Đại học Công nghệ, Đại học Quốc Gia Hà Nội, đặc biệt là các thầy cô trong bộ môn Mạng và truyền thông máy tính. Các thầy cô đã dạy bảo và giúp đỡ tôi rất nhiều trong quá trình học tập, giúp tôi trưởng thành hơn trong suy nghĩ và nhận thức. Đặc biệt xin chân thành cảm ơn thầy Nguyễn Đại Thọ, người đã trực tiếp hướng dẫn tôi hoàn thành khóa luận này. Sự nhiệt tình hướng dẫn của thầy là nguồn động lực lớn lao cho tôi. Tôi cũng xin chân thành cảm ơn những người bạn thân thiết đã chia sẻ những kinh nghiệm và kiến thức bổ ích cho tôi, xin cảm ơn những người thân trong gia đình đã động viên và tạo điều kiện cho tôi trong quá trình hoàn thành khóa luận. Hà Nội, tháng 5 năm 2009 Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 3 ĐH Công nghệ - ĐH Quốc Gia HN TÓM TẮT NỘI DUNG Khóa luận này là kết quả nghiên cứu của tác giả về vấn đề tìm kiếm trong mạng ngang hàng.Trong khuôn khổ của khóa luận, tác giả đã trình bày tổng quan nhất về mạng ngang hàng và vấn đề tìm kiếm trong mạng ngang hàng không có cấu trúc. Phương pháp tìm kiếm đề xuất trong khóa luận được tác giả nghiên cứu dựa trên nhiều nguồn tư liệu trong đó tư liệu chính là bài báo [4] Khóa luận cũng giới thiệu về một công nghệ đang còn rất nhiều tiềm năng đó là công nghệ tác tử di động. Công nghệ hữu ích này đã giải quyết bài toán tìm kiếm hóc búa như thế nào và dựa trên những cơ sở lý thuyết nào, đó là vấn đề mà khóa luận tập trung phân tích. Để làm rõ hơn những phân tích và nghiên cứu, trong khóa luận tác giả đã trình bày phần thí nghiệm mô phỏng với dự án MATES của Evan Sultanik. Dựa trên kết quả thực nghiệm thu được, so sánh với các công thức lý thuyết tác giả đã đánh giá và đưa ra kết luận cho những nghiên cứu của mình. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 4 ĐH Công nghệ - ĐH Quốc Gia HN MỤC LỤC LỜI CẢM ƠN .................................................................................................................................... 2 TÓM TẮT NỘI DUNG ..................................................................................................................... 3 BẢNG CÁC THUẬT NGỮ VIẾT TẮT ............................................................................................ 6 DANH MỤC CÁC HÌNH VẼ BẢNG BIỂU ..................................................................................... 7 MỞ ĐẦU............................................................................................................................................ 8 Chương 1. TỔNG QUAN ................................................................................................................ 10 1.1. Tổng quan mạng ngang hàng ................................................................................................ 10 1.1.1. Định nghĩa...................................................................................................................... 10 1.1.2. Phân loại......................................................................................................................... 11 1.1.3. Ưu điểm và nhược điểm của mạng ngang hàng ............................................................. 11 1.1.4. Các ứng dụng của mạng ngang hàng.............................................................................. 12 1.2. Vấn đề tìm kiếm trong mạng ngang hàng không cấu trúc..................................................... 13 1.2.1. Một số kĩ thuật tìm kiếm phổ biến ................................................................................. 13 1.2.2. Xu hướng phát triển ....................................................................................................... 15 Chương 2. CÔNG NGHỆ TÁC TỬ DI ĐỘNG ............................................................................... 16 2.1. Tổng quan về tác tử di động.................................................................................................. 16 2.1.1. Lịch sử hình thành.......................................................................................................... 16 2.1.2. Định nghĩa...................................................................................................................... 16 2.1.3. Các đặc tính chính .......................................................................................................... 17 2.2. Nguyên lý hoạt động ............................................................................................................. 17 2.3. Ứng dụng............................................................................................................................... 18 2.3.1. Những lợi điểm của tác tử di động................................................................................. 18 2.3.2. Các ứng dụng chính........................................................................................................ 19 Chương 3. MÔ HÌNH SỬ DỤNG TÁC TỬ DI ĐỘNG PHÁT HIỆN DỊCH VỤ TRONG CÁC MẠNG NGANG HÀNG KHÔNG CẤU TRÚC ............................................................................. 21 3.1. Cơ sở lý thuyết ...................................................................................................................... 21 3.1.1. Chuỗi Markov và đường đi ngẫu nhiên.......................................................................... 22 3.1.2. Thuật toán PageRank ..................................................................................................... 24 3.2. Các tham số đánh giá hiệu năng............................................................................................ 26 Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 5 ĐH Công nghệ - ĐH Quốc Gia HN 3.2.1. Xác suất tác tử tới thăm một host cho trước................................................................... 26 3.2.2. Xác suất tác tử phát hiện dịch vụ ................................................................................... 26 3.2.3. Hàm dự đoán tác tử nhìn thấy dịch vụ và thăm host ...................................................... 27 3.2.4. Thời gian kì vọng tác tử di chuyển ngẫu nhiên trở về nguồn......................................... 28 3.3. Mô hình triển khai ................................................................................................................. 29 3.4. Đánh giá mô hình .................................................................................................................. 30 Chương 4. CÁC THÍ NGHIỆM MÔ PHỎNG VÀ ĐÁNH GIÁ...................................................... 31 4.1. Chương trình mô phỏng MATES.......................................................................................... 31 4.1.1. Kiến trúc chương trình ................................................................................................... 31 4.1.2. Triển khai chương trình.................................................................................................. 34 4.1.3. Ưu điểm, nhược điểm của chương trình......................................................................... 36 4.2. Thí nghiệm đo tần suất tác tử tới thăm host .......................................................................... 37 4.3. Thí nghiệm 2 ......................................................................................................................... 39 4.4. Thí nghiệm 3 ......................................................................................................................... 43 Chương 5. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN..................................................................... 45 LỜI KẾT .......................................................................................................................................... 47 TÀI LIỆU THAM KHẢO................................................................................................................ 48 Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 6 ĐH Công nghệ - ĐH Quốc Gia HN BẢNG CÁC THUẬT NGỮ VIẾT TẮT P2P Peer-to-Peer WWW World Wide Web URL Uniform Resource Locator CAN Content Addressable Networks DHT Distributed Hash Table TTL Time-to-Live MATES Macro Agent Transport Event-based Simulator MANET Mobile Ad-hoc Network AI Artificial Intelligence Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 7 ĐH Công nghệ - ĐH Quốc Gia HN DANH MỤC CÁC HÌNH VẼ BẢNG BIỂU Hình 1-Mô hình mạng ngang hàng .......................................................................... 10 Hình 2-Một agent di chuyển ngẫu nhiên trong mạng ngang hàng .......................... 22 Hình 3-Một vòng mô phỏng...................................................................................... 31 Hình 4-Mối tương quan giữa xấp xỉ v và tần suất tác tử tới thăm host trong 100000 lần lặp ....................................................................................................................... 39 Hình 5-Hàm dự đoán F(N) và xác suất tới thăm host của tác tử có thông tin về dịch vụ .............................................................................................................................. 42 Hình 6-Thời gian kì vọng tác tử về nguồn................................................................ 44 Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 8 ĐH Công nghệ - ĐH Quốc Gia HN MỞ ĐẦU Ngày này cư dân mạng đã không còn lạ lẫm với thuật ngữ mạng ngang hàng (P2P). Mạng ngang hàng là bước phát triển từ mô hình mạng client/server truyền thống tới một mô hình mạng trong đó mỗi phần tử của mạng hoạt động với vai trò của cả client và server. Mạng ngang hàng đã tỏ rõ ưu thế và ích lợi của mình trong vấn đề lưu trữ và băng thông. Công nghệ mạng ngang hàng đã trở nên gần gũi và phổ dụng với người dùng. Nó giảm những chi phí đắt đỏ bởi những người dùng có thể sử dụng chung và chia sẻ cho nhau những phần cứng, những tài nguyên mạng. Một số hệ thống mạng ngang hàng đã trở nên quen thuộc với người dùng Internet như Napster, SETI@Home, ICQ. P2P hiện đang được ứng dụng trong rất nhiều lĩnh vực, bao gồm cả thương mại điện tử. Thu hút hàng nghìn kết nối từ người dùng mà không phải lo lắng tới vấn đề điều khiển tập trung và mở rộng, P2P vẫn phải đối mặt với vấn đề định vị tài nguyên do sự phân tán của mạng đặc biệt khi cấu trúc mạng không cố định mà thường xuyên thay đổi. Các giao thức phát hiện tài nguyên phổ biến nhất trong mạng ngang hàng vẫn là truy vấn phát tràn và bảng băm phân tán. Tuy nhiên phương thức phát tràn đặt ra bài toán tắc nghẽn trong mạng trong khi bảng băm phân tán lại yêu cầu tăng chi phí cho những cập nhật phân tán. Giao thức tìm kiếm truyền thống trong mạng ngang hàng có thể được cải tiến nếu một nút bắt đầu truy vấn có một chút thông tin về nơi tìm kiếm tài nguyên mà không phải duy trì việc băm phân tán. Một số thông tin như topo mạng, băng thông do các nút khác hỗ trợ có thể được sử dụng để cung cấp hướng tìm kiếm cho những truy vấn sau này. Sự phát triển của khoa học máy tính, trí tuệ nhân tạo và công nghệ phần mềm cho ra đời một đối tượng khá hữu dụng giải quyết vấn đề trên đó là tác tử. Một tác tử là một đoạn mã có thể tiếp tục thi hành những hành động đã được lập trình mà không cần phải chịu sự giám sát của bộ quản lý trung tâm. Các tác tử thông minh cũng có khả năng học hỏi thông tin từ môi trường để cải tiến hành động của chúng và di chuyển từ một nút này tới nút khác để thực thi những tác vụ phân tán. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 9 ĐH Công nghệ - ĐH Quốc Gia HN Tác tử phần mềm (software agent) là một hướng lập trình mới phù hợp để thực thi cơ chế tìm kiếm thông tin trong mạng ngang hàng không có cấu trúc. Trong bối cảnh đó đề tài “Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc” đi sâu vào nghiên cứu giải pháp ứng dụng tác tử di động phát hiện dịch vụ trong mạng ngang hàng không có cấu trúc dựa trên thuật toán đường đi ngẫu nhiên và những cơ sở lý thuyết toán học. Ý tưởng sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc không phải là mới. Vấn đề này đã được các nhà khoa học nghiên cứu và có những đánh giá nhất định. Trong khuôn khổ của khóa luận này, tác giả chỉ nghiên cứu và xem xét các khía cạnh liên quan tới nguyên lý, cơ chế, những lý thuyết về thuật toán của giải pháp và đánh giá những lý thuyết đã đưa ra bằng những thí nghiệm mô phỏng cụ thể. Nội dung của khóa luận sẽ bao gồm những phần sau: • Chương 1: Tìm hiểu chung về mạng ngang hàng, những phương pháp tìm kiếm truyền thống trong mạng ngang hàng. • Chương 2: Giới thiệu công nghệ tác tử di động, từ khái niệm, phân loại, các tính chất, nguyên lý hoạt động, các lợi điểm cho tới những ứng dụng của công nghệ này trong thực tiễn. • Chương 3: Nghiên cứu giải pháp sử dụng tác tử di động tìm kiếm thông tin trong các mạng ngang hàng không có cấu trúc, cơ sở lý thuyết, các tham số liên quan và những đánh giá sơ bộ về giải pháp. • Chương 4: Giới thiệu chương trình mô phỏng và cài đặt những thí nghiệm cụ thể để đánh giá giải pháp • Chương 5: Kết luận và hướng phát triển Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 10 ĐH Công nghệ - ĐH Quốc Gia HN Chương 1. TỔNG QUAN 1.1. Tổng quan mạng ngang hàng 1.1.1. Định nghĩa Mạng ngang hàng (peer to peer) là một mạng máy tính trong đó hoạt động của mạng chủ yếu dựa vào khả năng tính toán và băng thông của các máy tham gia chứ không tập chung vào một số nhỏ các máy chủ tập chung như các mạng thông thường. Hay nói một cách đơn giản hơn đó là mạng ngang hàng là một mạng mà được tạo ra bởi hai hay nhiều máy tính được kết nối với nhau và chia sẻ tài nguyên mà không phải thông qua một máy chủ rành riêng. Dưới đây là một ví dụ về mạng ngang hàng. Hình 1-Mô hình mạng ngang hàng Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 11 ĐH Công nghệ - ĐH Quốc Gia HN 1.1.2. Phân loại Có thể phân loại các mạng đồng đẳng hiện nay theo tiêu chí về mức độ tập trung của chúng như sau: - Mạng ngang hàng “thuần túy”: • Các máy trạm có vai trò vừa là máy chủ vừa là máy khách • Không có máy chủ trung tâm quản lý mạng • Không có bộ định tuyến trung tâm, các máy trạm có khả năng tự định tuyến - Mạng ngang hàng “lai”: • Có một máy chủ trung tâm dùng để lưu trữ thông tin của các máy trạm và trả lời các truy vấn thông tin này. • Các máy trạm có vai trò lưu trữ thông tin, tài nguyên được chia sẻ, cung cấp các thông tin về chia sẻ tài nguyên của nó cho máy chủ. • Sử dụng các trạm định tuyến để xác định địa chỉ IP của các máy trạm. Các mạng ngang hàng "thuần túy" có thể kể là Gnutella và Freenet. Các mạng ngang hàng lai có nhiều loại: mạng P2P tập trung như Napste, mạng P2P phân tán như KazaA, mạng P2P có cấu trúc như CAN, mạng P2P không cấu trúc như Gnutella. 1.1.3. Ưu điểm và nhược điểm của mạng ngang hàng 1.1.3.1. Ưu điểm Mạng ngang hàng thể hiện rõ ưu thế so với mạng theo mô hình Client/Server.Nó tận dụng được tiềm năng từ "cạnh" của Internet còn ít được khai thác. Ví dụ chỉ cần từ 10 triệu máy tính 100 MHz nối vào mạng cùng một lúc, mỗi máy có dung lượng lưu trữ 100 MB, băng thông 1000 bps, 10% khả năng xử lý chưa được sử dụng đến. Nó không dựa trên server tập trung và thường hoạt động ngoài hệ thống tên miền mà sử dụng kiến trúc phẳng, tính kết nối cao để các máy tự tìm ra nhau, xác định nơi cung cấp dịch vụ và chủ động yêu cầu dịch vụ theo ý muốn. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 12 ĐH Công nghệ - ĐH Quốc Gia HN Kiến trúc mạng ngang hàng cho phép phân tán trách nhiệm cung cấp dịch vụ đến tất cả các điểm nút trên mạng. Chính vì thế đã loại bỏ vấn đề ngừng trệ dịch vụ do nơi duy nhất cung cấp bị sự cố. Đó chính là giải pháp khả biến hơn trong việc cung cấp dịch vụ. Mạng ngang hàng tận dụng băng thông trên toàn bộ mạng bởi vì các máy tính giao tiếp qua nhiều đường truyền khác nhau nên đã giảm đáng kể hiện tượng nghẽn tắc mạng. Mạng ngang hàng phục vụ tài nguyên với độ sẵn sàng cao, chi phí thấp đồng thời nâng cao hiệu suất khai thác trong khi đó thì mạng theo mô hình Client-Server thì phải cần thêm băng thông, thiết bị, phương tiện. 1.1.3.2. Nhược điểm Do tính các máy tính trong mạng có vai trò ngang nhau nên yêu cầu dịch vụ cũng được đáp ứng một cách tùy biến. Ví dụ, các client yêu cầu cùng một dịch vụ có thể nối tới các máy khác nhau, qua các đường truyền khác nhau, với kết quả nhận được khác nhau. Một nhược điểm nữa của mạng ngang hàng là các yêu cầu từ các máy có thể không nhận được kết quả ngay và có thể không được đáp ứng do các tài nguyên có thể biến mất do máy cung cấp ngắt kết nối trong khi đó với Client/Server thì hầu như tài nguyên liên tục hiện diện. 1.1.4. Các ứng dụng của mạng ngang hàng Ứng dụng lớn nhất có thể kể đến của mạng ngang hàng là ứng dụng chia sẻ file. Có hai công nghệ mạng ngang hàng trong lĩnh vực chia sẻ file điển hình là Napster và Gnutenlla. Trong khi Napster cho phép người dùng trao đổi các file MP3 với nhau và có thêm chức năng gửi tin nhắn tức thời thì Gnutenlla có thể cho phép chia sẻ mọi kiểu file. Napster sử dụng kiến trúc mạng ngang hàng lai ghép trong đó server lưu danh sách các file MP3 mỗi người dùng chia sẻ, cho phép người dùng tìm kiếm một file cụ thể và các file được trao đổi trực tiếp giữa các điểm nút. Gnutella thì không sử dụng server. Ngoài ứng dụng chia sẻ file, mạng ngang hàng còn có ứng dụng tính toán phân tán. SETI@Home và Distributed.net là hai ứng dụng điển hình của tính toán phân tán. Sử dụng tác tử di động phát hiện dịch vụ trong các mạng ngang hàng không có cấu trúc! Nguyễn Thị Kim Oanh – K50MTT Trang 13 ĐH Công nghệ - ĐH Quốc Gia HN 1.2. Vấn đề tìm kiếm trong mạng ngang hàng không cấu trúc 1.2.1. Một số kĩ thuật tìm kiếm phổ biến 1.2.1.1. Phát tràn Phát tràn là chiến lược tìm kiếm đơn giản nhất và thông dụng nhất trong mạng ngang hàng. Bởi thế mà mạng Gnutella đã sử dụng phương pháp tìm kiếm này. Việc tìm kiếm được tiến hành như sau: đầu tiền nút cần tìm gửi đi một thông điệp do thám tới tất cả các hàng xóm của nó. Các hàng xóm này sẽ chuyển những bản sao của thông điệp kia tới những nút hàng xóm kế tiếp trừ nút hàng xóm mà đã chuyển thông điệp tới nó. Cứ như thế, công cuộc tìm kiếm được tiếp diễn. Trong quá trình thực thi phương pháp này cho thấy một số hạn chế và nhược điểm. Hạn chế lớn nhất đó là vấn đề truyền tải. Những thành phần tham dự vào mạng như những máy tính cá nhân tại gia hay ở cơ quan là những thành phần chịu ảnh hưởng nhiều nhất. Nếu một máy tính phải xử lý rất nhiều gián đoạ