Luận văn Phân bổ nội dung ngang hàng dựa trên cấu trúc mesh trong các mạng tự hợp di động

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Trung Duy PHÂN BỔ NỘI DUNG NGANG HÀNG DỰA TRÊN CẤU TRÚC MESH TRONG CÁC MẠNG TỰ HỢP DI ĐỘNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Mạng và Truyền thông máy tính HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Trung Duy PHÂN BỔ NỘI DUNG NGANG HÀNG DỰA TRÊN CẤU TRÚC MESH TRONG CÁC MẠNG TỰ HỢP DI ĐỘNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Mạng và Truyền thông máy tính Cán bộ hướng dẫn: TS. Nguyễn Đại Thọ HÀ NỘI - 2010 TÓM TẮT Đa số các mạng ngang hàng được xây dựng cho mạng Internet với số lượng hàng triệu nút mạng, trong khi đó mạng tự động di hợp chỉ là tập hợp từ mười đến vài trăm nút. Các giao thức mạng ngang hàng thường hoạt động trên tầng ứng dụng , sử dụng đơn phát để phân bổ dữ liệu, và không quan tâm đến tính di động của các nút. Bên cạnh đó, các mạng tự hợp di động sử dụng các phiên truyền đa phát không tin cậy thông qua kênh truyền dùng chung, trong đó các nút di chuyển một cách tự do. Trong khóa luận này , chúng tôi đề xuất ý tưởng cải tiến giao thức P2MAN [1] nhằm giải quyết vấn đề phân bổ nội dung ngang hàng trong các mạng tự hợp di động.Kết quả ban đầu cho thấy giao thức phân bổ nội dung sau khi được cải tiến hoạt động hiệu quả và ổn định hơn trong môi trường di động khi số lượng các nút có dữ liệu trong mạng tăng lên. LỜI CÁM ƠN Trước tiên, tôi xin gửi lời cám ơn sâu sắc tới người hướng dẫn, thầy giáo, TS. Nguyễn Đại Thọ, Bộ môn Mạng và Truyền thông máy tính – người đã trực tiếp hướng dẫn tôi trong suốt quá trình thực hiện khóa luận. Tiếp theo tôi xin chân thành cám ơn trường Đại Học Công Nghệ - Đại Học Quốc Gia Hà Nội đã cho tôi một môi trường thật tốt để học tập và rèn luyện bản thân trong suốt bốn năm học tập tại trường. Cuối cùng, xin gửi lời cảm ơn tới gia đình và bạn bè tôi, những người đã luôn ủng hộ và khuyến khích tôi rất nhiều trong quá trình học tập. Họ là nguồn động viên vô tận của tôi trong cuộc sống. Hà Nội, tháng 5 năm 2010 Nguyễn Trung Duy MỤC LỤC Chương 1 Mở đầu........................................................................................... 1 1.1 Lý do kết hợp công nghệ mạng ngang hàng và mạng tự hợp di động ................1 1.2 Mục đích của đề tài ..........................................................................................1 1.3 Nguồn gốc ý tưởng...........................................................................................2 1.4 Bố cục khóa luận..............................................................................................2 Chương 2 Công nghệ mạng ngang hàng........................................................... 4 2.1 Giới thiệu chung...............................................................................................4 2.2 Nguyên tắc tổ chức...........................................................................................5 2.2.1 Lớp xếp chồng cơ bản................................................................................5 2.2.2 Lớp phần mềm trung gian ..........................................................................6 2.2.3 Lớp ứng dụng ............................................................................................6 2.3 So sánh mô hình mạng ngang hàng và mô hình máy khách – máy chủ..............6 2.4 Các ứng dụng mạng ngang hàng......................................................................7 2.4.1 Thông tin ...................................................................................................7 2.4.2 File ............................................................................................................8 2.4.3 Băng thông ..............................................................................................10 2.4.4 Không gian lưu giữ ..................................................................................10 2.4.5 Chu trình xử lý ............................................................................................11 Chương 3 Các mạng tự hợp di động............................................................... 12 3.1 Giới thiệu chung.............................................................................................12 3.2 Khái niệm mạng tự hợp di động .....................................................................12 3.3 Đặc điểm của mạng tự hợp di động ................................................................13 3.4 Định tuyến trong mạng tự hợp di động ...........................................................14 3.4.1 Phát tràn .................................................................................................14 3.4.2 Kỹ thuật phát tràn hiệu quả ......................................................................15 3.4.3 Định tuyến đơn phát ................................................................................15 3.4.4 Định tuyến đa phát...................................................................................18 Chương 4:Giao thức phân bổ nội dung ngang hàng trong các mạng tự hợp di động P2MAN………………………………………………………………………..23 4.1 Giới thiệu chung.............................................................................................23 4.2 Giao thức đa phát PUMA ...............................................................................24 4.3 Cơ chế hoạt động của P2MAN .......................................................................24 4.3.1 Tìm kiếm dữ liệu .....................................................................................25 4.3.2 Phân bổ dữ liệu........................................................................................26 4.3.3 Cơ chế sửa lỗi ..........................................................................................27 Chương 5 Đề xuất ý tưởng và kết quả thu được ............................................. 29 5.1 Đặt vấn đề ......................................................................................................29 5.2 Giải thuật cải tiến ...........................................................................................29 5.2.1 Tìm kiếm .................................................................................................30 5.2.2 Phân bổ dữ liệu........................................................................................30 5.2.3 Cơ chế sửa lỗi ..........................................................................................31 5.2.4 Ví dụ minh họa .......................................................................................31 5 .3 Kết quả thu được...........................................................................................36 CÁC HÌNH ẢNH SỬ DỤNG TRONG KHOÁ LUẬN Hình 2.1 Mô hình mạng ngang hàng với các nút mạng là các loại thiết bị khác nhau ………………………………………………………………………………………… 5 Hình 2.2 Kiến trúc Gnutella ………………………………………………………….. 9 Hình 3.1 Ví dụ về mạng tự hợp di động gồm các thiết bị như PDA, điện thoại di động, máy tính xách tay ……………………………………………………………………. 13 Hình 3.2 Một số giao thức định tuyến đơn phát trong mạng tự hợp di động ……… 15 Hình 3.3 Giao thức AODV. Quá trình dò tìm đường đi từ nút nguồn đến nút đích ....…………………………………………………………………………………….. 17 Hình 3.4 Giao thúc MAODV ……………………………………………………….. 19 Hình 3.5 Giao thức ODMRP ……………………………………………………....... 21 Hình 4.1 Mô phỏng P2MAN với các loại nút ……………………………………..... 25 Hình 4.2 Tìm kiếm nội dung ……………………………………………………...... .26 Hình 4.3 Nhận gói dữ liệu ………………………………………………………....... 27 Hình 4.4 Cơ chế sửa lỗi …………………………………………………………....... 28 Hình 5.1 Mô tả các thành viên trong nhóm đa phát PC …………………………..… 31 Hình 5.2 Quá trình tìm kiếm ……………………………………………………..…. 32 Hình 5.3 Trạng thái các nút tại thời điểm đầu tiên nhận được gói phản hồi……...…. 33 Hình 5.4 - a N nhận gói phản hồi từ G……………………………………………..... 33 Hình 5.4 - b N nhận gói phản hồi từ C …………………………………………….....34 Hình 5.4 - c N nhận gói phản hồi từ E ……………………………………………….34 Hình 5.5 Các tham số mô phỏng ………………………………………………….....35 Hình 5.6 Thời gian nhận X Số lượng nút gửi ……………………..……….…………36 Hình 5.7 Thời gian tải X Số lượng nút truy vấn ……………………..……………….37 Hình 5.8 Thời gian tải X Tốc độ di chuyển của nút mạng …………………….…….38 BẢNG CÁC TỪ VIẾT TẮT AODV Ad-hoc On-demand Distance Vector DMS Customarily Document Management Systems DSDV Destination-Sequenced Distance-Vector MANET Mobile Ad Hoc Network NS-2 Network Simulator Version 2 P2MAN Peer to Peer Mobile Ad Hoc Network PC Public Chanel TCP Transmission Control Protocol UDP User Datagram Protocol 1 Chương 1 Mở đầu Chương này giới thiệu về công nghệ mạng ngang hàng trong môi trường di động, lý do triển khai mạng ngang hàng trong môi trường di động và mô tả khái quát về cải tiến trong khóa luận. 1.1 Lý do kết hợp công nghệ mạng ngang hàng và mạng tự hợp di động Đặc điểm nổi bật của các hệ thống ngang hàng là khả năng tự tổ chức, khả năng tìm kiếm và phân bổ tài nguyên. Cùng với sự gia tăng của các kết nối di động – bao gồm truy cập Internet trong các mạng di động đã khiến các ứng dụng ngang hàng ngày càng trở nên phổ biến với người dùng di động. Thông thường chúng ta có thể chia các mạng di động làm hai loại : các mạng tế bào và các mạng tự hợp di động. Trong mạng tế bào mỗi nút ngang hàng di động kết nối đến mạng Internet cố định thông qua một liên kết không dây đơn. Do đó chúng ta luôn biết rằng kể cả khi nút di chuyển thì quãng đường vật lý tới nút vẫn không thay đổi. Các nút ngang hàng kết nối vào mạng Internet thông qua liên kết tế bào không dây sẽ giảm hiệu suất do giới hạn băng thông. Trong hệ thống tế bào không dây, thay đổi trong giao thức ngang hàng để đáp ứng được tính di chuyển của các nút mạng sẽ không cần thiết . Tuy nhiên trong các mạng tự hợp di động , nếu chỉ triển khai đơn thuần công nghệ mạng ngang hàng trên một mạng tự hợp di động chúng ta sẽ không thể giải quyết được vấn đề di động của các nút mạng. Do đó yêu cầu đặt ra là cần tìm ra các giải pháp để thực thi công nghệ ngang hàng trong mạng tự hợp di động một cách hiệu quả. 1.2 Mục đích của đề tài Khóa luận xây dựng một giao thức phân bổ nội dung ngang hàng trong mạng tự động di hợp. Cũng như hầu hết các giao thức ngang hàng khác, giao thức phân bổ nội dung này hoạt động trên tầng ứng dụng. Nó sử dụng giao thức đa phát PUMA [1] làm giao thức đa phát ở tầng mạng. Do hoạt động trong môi trường mạng tự hợp di động nên việc nút di chuyển và phá vỡ các liên kết luôn xảy ra. Nhằm đảm bảo tính tin cậy cho quá trình phân bổ nội dung , giao thức phân bổ nội dung thực thi cơ chế sửa lỗi ở 2 tầng ứng dụng. Quá trình sửa lỗi sẽ được khởi động mỗi khi nút phát hiện quá trình tải dữ liệu gặp lỗi. Đồng thời giao thức cho phép nút truy vấn có khả năng cùng lúc nhận các gói dữ liệu từ nhiều nút gửi khác nhau. Điều này sẽ nâng cao hiệu quả quá trình tải dữ liệu. Sử dụng giao thức đa phát PUMA, là giao thức đa phát đơn giản và có hiệu quả. Giao thức phân bổ nội dung này đã kết hợp được những ưu điểm của công nghệ ngang hàng vào mạng tự hợp di động. Giao thức phân bổ nội dung ngang hàng và giao thức đa phát PUMA xây dựng và hoạt động trong môi trường mô phỏng NS-2 [2]. 1.3 Nguồn gốc ý tưởng Chương trình được phát triển dựa trên giao thức P2MAN đã được đề xuất trong bài báo “A Multicast Approach for Peer-to- peer Content Distribution in Mobile Ad Hoc NetWork” [3] của hai tác giả Sidney Santos Doria và Marco Aurélio Sphon. Tuy nhiên giao thức trong bài báo [1] có những điểm hạn chế sau : o Trong một phiên truyền dữ liệu , nút nhận chỉ nhận dữ liệu từ một nút gửi duy nhất . o Trong khi nếu nhận từ đồng thời nhiều nút sẽ hiệu quả hơn . Từ những nhận xét đó chúng tôi đã đề xuất ý tưởng cho phép một nút có thể đồng thời nhận dữ liệu từ một tập các nút có dữ liệu. Qua quá trình triển khai ý tưởng và các kết quả thu được chúng tôi thấy chương trình mô phỏng hoạt động hiệu quả với các tiêu chí đánh giá thời gian tải dữ liệu trong bài báo [2] qua các trường hợp : số lượng nút truy vấn tăng dần , tốc độ di chuyển của nút tăng dần. Mục đích trước mắt của chúng tôi khi thực hiện đề tài là xây dựng được một chương trình mô phỏng cho “giao thức phân bổ nội dung ngang hàng trong các mạng tự hợp di động”. Xa hơn nữa, chúng tôi muốn xây dựng một ứng dụng hoạt động hiệu quả trong môi trường thực. 1.4 Bố cục khóa luận Ngoài phần mở đầu và kết luận, khóa luận còn có các phần như sau : o Chương 2 : Công nghệ mạng ngang hàng. Chương này giới thiệu về mạng ngang hàng, đồng thời nếu ra một vài so sánh giữa mô hình mạng ngang hàng và mô hình máy khách – máy chủ truyền thống. 3 o Chương 3 : Các mạng tự hợp di động. Chương này giới thiệu về mạng tự hợp di động cũng như các đặc điểm của chúng. o Chương 4 : Giao thức phân bổ nội dung ngang hàng trong các mạng tự hợp di động P2MAN. Chương này trình bày về giao thức phân bổ nội dung ngang hàng được đề xuất trong bài báo “A Multicast Approach for Peer-to- peer Content Distribution in Mobile Ad Hoc NetWork” [3]. o Chương 5 : Đề xuất ý tưởng và kết quả mô phỏng Chương này đề xuất ý tưởng cải tiến giao thức phân bổ nội dung ngang hàng trong các mạng tự hợp di động P2MAN và trình bày các kết quả đạt được. 4 Chương 2 Công nghệ mạng ngang hàng Chương này giới thiệu về công nghệ mạng ngang hàng cũng như những ưu điểm của mô hình mạng ngang hàng so với mô hình truyền thống như máy khách – máy chủ. 2.1 Giới thiệu chung Hiện nay, hầu hết mọi dịch vụ mà Internet cung cấp đều dựa trên mô hình máy khách – máy chủ. Theo mô hình này trong mạng sẽ có một số máy thông qua một giao thức nhất định, chẳng hạn FTP, Telnet, …. Ở đây máy chủ đóng vai trò là trọng tài, khi cần thông tin, mỗi máy khách sẽ gửi yêu cầu lên máy chủ, máy chủ sẽ xử lý và trả lời. Tuy nhiên khi mà mạng Internet phát triển với tốc độ chóng mặt như ngày nay thì mô hình máy khách – máy chủ đã bộc lộ những nhược điểm quan trọng, ví dụ khi số lượng máy khách tăng đến ngưỡng nào đó thì nhu cầu về tải và băng thông tăng đến mức máy chủ không còn đủ khả năng đáp ứng nữa. Để giải quyết vấn đề trên nhiều mô hình mạng máy tính khác đã được nêu ra. Trong số đó mạng ngang hàng là mô hình được chú ý nhiều nhất và có tầm ứng dụng thực tiễn cao nhất. Theo thống kê của nhiều nhà cung cấp dịch vụ mạng thì hiện nay các ứng dụng mạng ngang hàng chiếm khoảng 50% (thậm chí là 75%) băng thông mạng Internet [4]. Có rất nhiều định nghĩa được đưa ra cho mạng ngang hàng nhưng chưa có một định nghĩa nào được công nhận rộng rãi. Tuy nhiên để nhận biết một mạng ngang hàng, chúng ta có thể dựa vào một số đặc điểm chung trong hầu hết các mạng ngang hàng : o Một máy tính trong mạng ngang hàng được gọi là một nút mạng. Nút mạng có thể đóng vai trò của cả client và server. Các nút mạng có khả năng trao đổi tài nguyên một cách nhanh chóng, các tài nguyên bao gồm file, dung lượng ổ cứng, khả năng xử lý và các tri thức. o Trong các hệ thống mạng ngang hàng có thể có hoặc không những máy chủ chuyên dụng. các máy chủ trong mạng hệ thống mạng ngang hàng chỉ có nhiệm vụ hỗ trợ các nút mạng phát hiện ra nhau. Các mạng ngang hàng không có máy chủ chuyên dụng được gọi là mạng ngang hàng thuần túy. o Các nút mạng có thể tùy ý tham gia và rời khỏi mạng. 5 o Một điểm đáng chú ý là các nút trong mạng ngang hàng không nhất thiết phả là một máy tính, nó có thể là các thiết bị di động như điện thoai di dộng, PDA, … Hình 2.1 – Mô hình mạng ngang hàng với các nút mạng là các loại thiết bị khác nhau 2.2 Nguyên tắc tổ chức Các hệ thống ngang hàng dựa trên sự phi tập trung và khả năng tự tổ chức của các hệ thống phân tá. Kiến trúc ngang hàng là cách thức tổ chức một ứng dụng phân tán thành tập các module phần mêm riêng, mỗi module sẽ chạy trên một máy tính khác nhau. Các module phần mềm khác nhau sẽ giao tiếp với module khác để xử lý yêu cầu hoản chỉnh của chương trình phân tán.Một ứng dụng ngang hàng gồm ba thành phần chính : lớp xếp chồng cơ bản, lớp phần mềm trung gian và lớp ứng dụng. 2.2.1 Lớp xếp chồng cơ bản Lớp xếp chồng cơ bản đảm bảo tất cả các nút tham gia hệ thống ngang hàng biết đến nhau và cung cấp cơ chế cho tất cả các nút giao tiếp với nhau. Đây là lớp cần thiết đối với tất cả các hệ thống ngang hàng. Lớp xếp chồng cơ bản có các chức năng sau : o Chức năng phát hiện : trước khi giao tiếp với nhau mỗi nút mạng cần phát hiện ra một tập tối thiểu các nút khác. o Tạo lớp xếp chồng : cung cấp cơ chế cho các nút kết nối vào mạng chung sử dụng bởi mỗi nút khi muốn giao tiếp với nút khác. 6 o Đa phát mức ứng dụng : cơ chế cho phép một nút gửi thông báo đến tất cả các nút khác thuộc một nhóm nào đó. 2.2.2 Lớp phần mềm trung gian Lớp phần mềm trung gian bao gồm các thành phần phần mềm có thể được sử dụng lại bởi nhiều ứng dụng khác nhau. Lớp này chủ yếu được gọi thực hiện bởi các thành phần phần mềm khác và được sử dụng như cơ sở hạ tầng hỗ trợ xây dựng các ứng dụng khác.Bên cạnh đó, lớp còn có nhiệm vụ tạo chỉ mục phân tán cho thông tin trong hệ thống, cung cấp phương tiện gửi phát – đăng nhận, và các dịch vụ an ninh. Trong ứng dụng, lớp xếp chồng trung gian là không cần thiết cho tất cả các ứng dụng nhưng được phát triển để sử dụng lại bởi nhiều hơn một ứng dụng. 2.2.3 Lớp ứng dụng Lớp ứng dụng bao gồm các thành phần phần mềm được thiế kế để sử dụng chủ yếu bới con người. Lớp này được phát triển sao cho khai thác được bản chất phân tán của cơ sở hạ tầng. 2.3 So sánh mô hình mạng ngang hàng và mô hình máy khách – máy chủ Hiện nay, mô hình mạng ngang hàng và mô hình truyền thống client – server đang cùng tồn tại song song , mỗi mô hình đều có những ưu điểm và hạn chế riêng. Dưới đây chung tôi xin nêu ra một vài so sánh giữa hai mô hình trên. Thứ nhất, một mạng ngang hàng cho phép hai hay nhiều nút mạng chia sẻ các tài nguyên với nhau. Các tài nguyên đó có thể là ổ đĩa, đĩa CD-ROM, và kể cả máy in, và chúng nằm phân tán ở các nút mạng. Tất cả các tài nguyên này đều có thể được truy cập từ mọi nút trong mạng. Bên cạnh đó trong một mạng máy khách – máy chủ tất cả thông tin được lưu trữ tập trung ở một máy chủ trung tâm có tốc độ và năng lực xử lý vượt trội. Dữ liệu trên máy chủ này có thể được cung cấp cho hàng trăm , hàng ngàn … máy khách tùy theo năng lực xử lý của máy chủ trong mạng. Khi một máy khách muốn yêu cầu thông tin nào đó, máy sẽ gửi yêu cầu tới máy chủ và chờ được xử lý. Cả hai mô hình mạng ngang hàng và mô hình máy khách – máy chủ đều có những ưu điểm và điểm hạn chế riêng. 7 Điểm mạnh của mô hình mạng ngang hàng ở chỗ chi phí xây dựng mạng khá rẻ do tận dựng được tài nguyên trên của các nút mạng. Tuy nhiên các mô hình mạng ngang hàng cũng ẩn chứa trong chúng nhiều hạn chế. o Các nút mạng dễ bị tấn công o Số lượng nút thành viên trong một mạng ngang hàng là rất lớn do đó rất khó để có một chuẩn chung bắt buộc cho mọi thành viên trong mạng ngang hàng. o Các nút có thể tự do rời khỏi mạng, do đó mạng ngang hàng không thể luôn đảm bảo lúc nào tài nguyên cũng sẵn sàng. o Do không có sự điều phối chung nên trong một số nhiệm vụ sẽ xuất hiện sự mất cân bằng tải trong mạng. Điểm mạnh của mô hình máy khách – máy chủ ở chỗ nó cho phép mở rộng mô tùy theo sự phát triển của tổ chức, thông qua một máy chủ tập trung chúng ta có thể dễ dàng quản lý hàng trăm máy khách. Hơn nữa, trong mô hình máy khách – máy chủ vấn đề an ninh được nghiên cứu kỹ lưỡng và phát triển. Do vậy, mô hình này bảo đảm an ninh hơn mô hình phân tán trong mạng ngang hàng. Tuy vậy, mô hình khách – chủ cũng có những điểm hạn chế như sau: o Dữ liệu trong mạng khách – chủ đều nằm tập trung ở một máy chủ duy nhất, do vậy nguy cơ sụp đổ toàn trong toàn mạng là rấ