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

g 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ất cao. o Hơn nữa máy chủ phải đồng thời xử lý yêu cầu từ nhiều máy khách trong mạng nên trong một số trường hợp máy chủ sẽ không thể đáp ứng được các yêu cầu từ máy khách. 2.4 Các ứng dụng mạng ngang hàng Mô hình mạng ngang hàng cung cấp một cách thức mới cho việc quản lý các tài nguyên trên nhiều lĩnh vực ứng dụng khác nhau. Trong mục này chúng tôi điểm qua những cơ chế quản lý tài nguyên thuộc các loại khác nhau, ví dụ : thông tin, file, băng thông, thiết bị lưu trữ … 2.4.1 Thông tin Trong đời sống hàng ngày nói chung và trong các mạng máy tính nói riêng thì nhu cầu chia sẻ và trao đổi thông tin luôn chiếm vị trí vô cùng quan trong. Mạng ngang hàng cung cấp các cơ chế đáp ứng các nhu cầu này của người sử dụng. 8 2.4.1.1 Biểu diễn thông tin Biểu diễn thông tin hay presence information chiếm vai trò rất quan trọng đối với các ứng dụng ngang hàng. Quá trình biểu diễn thông tin là yếu tố quyết định trong các mạng tự tổ chức nhưng mạng ngang hàng khi mà nút phải cung cấp thông tin về các nút mạng và các tài nguyên hiện có trong mạng. Biểu diễn thông tin cho phép nút mạng khởi tạo kết nối tới các nút mạng khác và truy vấn các tài nguyên. Một ví dụ điển hình về ứng dụng biểu diễn thông tin là các hệ thống tin nhắn tức thời. 2.4.1.2 Quản lý tài liệu DMS hay Customarity Document Management Systems là hệ được tổ chức tập trung, giới hạn dung lượng chia sẻ, quyền quản lý và sử dụng dữ liệu. Tuy nhiên, chỉ có thể truy cập tới dữ liệu được đặt trong thư mục chia sẻ của DMS. Điều này dẫn tới yêu cầu cần phải có một chỉ mục tập trung cho các tài liệu liên quan. Tuy nhiên thực tế cho thấy trong các công ty dữ liệu được tạo và lưu giữ mà không có bất kỳ thông tin nào khác. Trong trường hợp này mạng ngang hàng là một lựa chọn cần thiết. 2.4.2 File Chia sẻ file là một trong các ứng dụng ngang hàng quan trọng nhất. Theo nghiên cứu thì 75% tải trọng mạng Internet được sử dụng để trao đổi file, đặc biệt là các file nhạc [4]. Đặc trưng chia sẻ file trong các mạng ngang hàng ở chỗ một nút mạng đóng vai trò của máy khách khi nó nhận dữ liệu từ nút mạng khác, đồng thời nút lại đóng vai trò là máy chủ khi nó có dữ liệu chia sẻ cùng các nút mạng khác. Vấn đề trọng tâm trong các mạng ngang hàng nói chung, đối với ứng dụng chia sè file nói riêng chính là định địa chỉ các tài nguyên. Trong khuôn khổ các hệ thống chia sẻ file, có ba mẫu đã được phát triển : mẫu truy vấn phát tràn, mẫu thư mục tập trung và mẫu tài liệu định tuyến. Những ví dự điển hình cho các mẫu trên là : Gnutella, Napster, Freenet. 2.4.2.1 Gnutella Trong mạng Gnutella, mỗi nút mạng đóng vai trò là một nút mạng đơn thuần, một ruoter hoặc có thể là nút trung gian, sử dụng giao thức TCP để chuyển các gói tin giao vận và giao thức HTTP để gửi file. Các truy vấn tìm kiếm truyền đi trong mạng dựa theo mẫu truy vấn phát tràn, nghĩa là một nút sẽ gửi gói truy vấn tới tất cả hàng xóm của nó và cứ thế thông điệp được truyền đi trong toàn mạng. Khi nhận được truy vấn nếu nút mạng không có khả 9 năng đáp ứng nó sẽ chuyển tiếp thông điệp cho các hàng xóm cho đến khi giá trị TTL = 0 hoặc thông điệp đến được file cần truy vấn. Hình 2.2 – Kiến trúc Gnutella 2.4.2.2 Napster Napster là mạng ngang hàng lai ghép, bao gồm một máy chủ trung tâm đảm nhiệm chức năng tìm kiếm, tất cả sử dụng giao thức TCP làm giao thức tầng ứng dụng. Máy chủ tìm kiếm trong hệ thống Napster lưu giữ danh sách bao gồm các điểm nút đang them gia vào mạng và danh sách các file đang được chia sẻ. Một nút hiện thời đang nhập vào mạng Napster, các file được chia sẻ bởi file sẽ được đăng ký với máy chủ Napster. Khi một truy vấn tìm kiếm được phát tán, máy chủ Napster gửi danh sách các nút mạng có file đang được truy vấn. 2.4.2.3 Freenet Mạng Freenet sử dụng mẫu tài liệu định tuyến để tìm kiếm và lưu trữ file. Trong mạng Freenet các file dữ liệu không được lưu ở ổ cứng của các nút mạng cung cấp chúng mà được lưu ở vị trí khác trong mạng. Nguyên nhân là Freenet được phát triển với mục đích xây dựng một mạng lưu trữ và truy cập thông tin ẩn danh. Để thực hiên điều này file và các nút trong mạng Freenet được gán một định danh duy nhất. Khi môt file được tạo , nó được gửi tới nút có định danh gần với định danh của file nhất và file sẽ được lưu trữ ở đấy. Các nút tham gia truyền file sẽ lưu lại định danh của file và thông báo tới các nút hàng xóm và thông tin này sẽ được lưu giữ trong bảng định tuyến của nút hàng xóm. 10 2.4.3 Băng thông Do yêu cầu về khả năng truyền dẫn của mạng Internet ngày càng cao, đặc biệt là nhu cầu với các dữ liệu đa phương tiện tăng ngày càng nhanh thì yêu cầu sử dụng băng thông hiệu quả càng trở nên quan trọng. Với hướng tiếp cận mạng ngang hàng vấn đề cân bằng tải sẽ được giải quyết một cách tối ưu nhất. 2.4.3.1 Tăng cường cân bằng tải Khác với kiến trúc máy khách – máy chủ các mạng ngang hàng lai ghép đạt được cân bằng tải tốt hơn. Với mô hình máy khách – máy chủ thì các thông tin truy vấn và truyền tải dữ liệu đều được thực hiện giữa máy chủ và máy khách, điều này dẫn tới tình trạng mất cân bằng tải khi có nhiều truy vấn được gửi tới máy chủ. Trong mô hình mạng ngang hàng lai ghép, chỉ có yêu cầu truy vấn được thực hiện giữa máy tính tham gia với máy chủ, còn quá trình truyền file được thực hiện giữa hai nút mạng với nhau. 2.4.3.2 Chia sẻ băng thông Sử dụng mô hình mạng ngang hàng làm tăng khả năng tải và truyền các file nhờ vào cơ chế tận dụng đường truyền tới các nút mạng. Một file dữ liệu lớn sẽ được chia thành các mảnh độc lập, các mảnh sau đó được gửi đồng thời tới các nút mạng khác nhau cho đến khi nút yêu cầu nhận được chúng. Tại nút đích, các mảnh dữ liệu sẽ được ghép lại thành file dữ liệu ban đầu. 2.4.4 Không gian lưu giữ Ngày nay các giải pháp như DAS , NAS hay SAN đang được các công ty và tổ chức lựa chọn để lưu trữ dữ liệu. Các giải pháp này đang tồn tại một số nhược điểm như : o Kém hiệu quả trong việc sử dụng hệ thống lưu trữ sẵn có. o Tăng tải trong mạng trong tổ chức. o Phải tăng cường việc sao lưu dữ liệu. Tuy nhiên, băng thông ngày càng được cải thiện , tính kết nối liên thông ngày một dễ dàng đã cho phép thay đổi cách thức quản lý vấn đề lưu trữ dữ liệu. 11 2.4.5 Chu trình xử lý Có thể nhận thấy rằng trong các ứng dụng đòi hỏi đến sức mạnh tính toán chúng ta thường tìm cách xây dựng các máy tính có cấu hình mạnh chứ chưa tập trung vào việc tận dụng khả năng tính toán của các máy tính được nối mạng. Ngày nay do các yêu cầu tính toán phức tạp với lượng dữ liệu lớn tăng cao dẫn tới nhiều nghiên cứu đã cố gắng tận dụng sức mạnh của mạng ngang hàng để xử lý. Bằng cách ứng dụng công nghệ mạng ngang hàng để kết hợp sức mạnh tính toán của nhiều nút trong mạng một cách đồng thời chúng ta có thể giải quyết các bài toán mà trước kia cần đến các siêu máy tính. 12 Chương 3 Các mạng tự hợp di động Chương này giới thiệu về mạng di động, cũng như các thách thức gặp phải khi triển khai công nghệ ngang hàng trong môi trường di động. Đồng thời, trong chương này chúng tôi cũng xin giới thiệu một vài giải pháp cơ bản cho việc triển khai công nghệ ngang hàng trong các mạng tự hợp di động. 3.1 Giới thiệu chung Khi nhắc tới cụm từ “kết nối di động” nghĩa là chúng ta nói đến những hệ thống có chứa ít nhất một nút thành viên kết nối vào hệ thống thông qua đường truyền không dây. Thông thường các mạng di động được chia làm hai nhóm nhỏ : Mạng tế bào không dây và mạng tự hợp di động. Trong các mạng tế bào không dây, nút mạng kết nối tới mạng Internet thông qua một liên kết đơn không dây. Như vậy, dù cho các nút di chuyển thì liên kết vật lý tới nút vẫn không thay đổi. Do giới hạn băng thông của liên kết không dây nên nút di động sẽ có hiệu suất thấp. Mạng tự hợp di động là hệ thống không dây đa chặng, có khả năng tự tổ chức và không dựa trên một kiến trúc cố định nào. Mỗi nút trong mạng tự hợp di động đồng thời đóng vai trò là nguồn dữ liệu, vừa đóng vai trò là một router trong tầng mạng. 3.2 Khái niệm mạng tự hợp di động Theo định nghĩa của Tổ chức Internet Engineering Task Force [5] mạng tự hợp di động – MANETs là một vùng tự trị của các router và cũng chính là các nút mạng, được kết nối với nhau bằng liên kết không dây. Trong mạng tự hợp di động các nút mạng có thể di chuyển một cách tự do dẫn đến hình trạng của mạng thay đổi liên tục mà không thể dự đoán trước . 13 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 3.3 Đặc điểm của mạng tự hợp di động Một là, các nút mạng di chuyển tự do trong không gian, kéo theo mô hình mạng luôn luôn thay đổi . Hai là, mạng tự hợp di động là mạng đa chặng , điều đó có nghĩa là đường đi từ nút nguồn đến nút đích sẽ đi qua nhiều nút mạng trung gian. Các nút mạng vừa đóng vai trò là router , vừa đóng vai trò là nguồn chia sẻ dữ liệu. Trong hình vẽ 3.1 ở trên đường cong màu xanh thể hiện đường đi từ PDA A đến Laptop B phải đi qua các chặng trung gian C , D , E. Ba là, các nút trong mạng tự hợp di động có khả năng tự tổ chức mà không cần thiết phải dựa trên một kiến trúc hạ tầng nào cả. Hơn nữa các kết nối trong mạng tự 14 hợp di động đều là kết nối không dây. Một mạng tự hợp di động có thể hoạt động một mình hoặc cũng có thể kết nối vào mạng Internet. Bốn là, cũng như các mạng di động khác mạng tự hợp di động bị giới hạn bởi năng lực xử lý, dung lượng bộ nhớ và nguồn năng lượng của các nút mạng. 3.4 Định tuyến trong mạng tự hợp di động Do các đặc điểm nêu trên khiến vấn để định tuyến trong các mạng tự hợp di động phải đối mặt với rất nhiều khó khăn. Vấn đề thứ nhất, các nút mạng luôn di động, mô hình mạng thay đổi liên tục do vậy các giao thức định tuyến trong mạng tự hợp di động cần có khả năng thích nghi động với mỗi sự thay đổi mạng. Vấn để thứ hai, các nút mạng có bộ nhớ và năng lực xử lý hạn chế, hơn nữa lại phải chia sẻ cùng nhau kênh truyền không dây nên băng thông dành cho mỗi nút mạng khá thấp. Do vậy nên các giao thức định tuyến trong mạng tự hợp di động cần phải tiết kiệm băng thông cho các phiên truyền dữ liệu bằng cách giảm thiểu các gói tin phục vụ cho quá trình định tuyến. Vấn đề thứ ba gặp phải là các nút mạng hoạt động nhờ vào năng lượng pin. Do vậy các nút mạng có thể tồn tại và tham gia liên kết trong thời gian dài thì các giao thức định tuyến phải có khả năng tiết kiệm tối đa năng lượng. Sau đây là một số giao thức định tuyến đã được ứng dụng trong các mạng tự hợp di động. 3.4.1 Phát tràn Phát tràn là cách thức đơn giản nhất để chuyển dữ liệu từ nút gửi đến nút nhận. Với cơ chế phát tràn, nút gửi sẽ gửi broadcast gói dữ liệu tới tất cả các hàng xóm. Trong lần đầu tiên nhận được gói tin broadcast nút sẽ tiếp tục broadcast gói tin tới tất cả hàng xóm của mình. Cơ chế “mỗi nút chỉ gửi một lần” được áp dụng để tránh vòng lặp của các gói tin, cũng là để kết thúc quá trình broadcast. Đối với cơ chế phát tràn, nút không cần biết đến các thông tin về hình trạng mạng. Đối với những mạng mà các nút mạng luôn di chuyển thì phát tràn có thể là phương án duy nhất để gửi các gói dữ liệu. Tuy nhiên trong các trường hợp khác phát tràn tỏ ra không hiệu quả. Mặc dù vậy, phát tràn vẫn đảm nhận những chức năng quan trọng trong các giao thức định tuyến , chẳng hạn như : khám phá các đường đi và xác định hình trạng mạng. 15 3.4.2 Kỹ thuật phát tràn hiệu quả Phát tràn hiệu quả cố gắng loại bỏ những yếu tố không hiệu quả của broadcast, nhưng vẫn đảm bảo tất cả các nút mạng đều nhận được gói tin. Cách thức đơn giản nhất là tất cả các nút sẽ broadcast tiếp gói dữ liệu nhận được với xác suất p. Việc xác định giá trị p quyết định đến sự hiệu quả của phiên phát tràn. Một cách khác có thể thực hiện được là nút sau khi nhận được gói tin đa phát, nút sẽ đợi trong khoảng thời gian nào đó. Nếu trong khoảng thời gian này, k lần nút nhận được gói tin trên thì nó hiểu rằng tất cả các hàng xóm của nó đều đã nhận được gói tin này. Rõ ràng việc lựa chọn giá trị k là yếu tố quyết định chất lượng phát tràn. Bên cạnh đó chúng ta có thể xác định một tập con các nút mạng có khả năng gửi gói dữ liệu tới tất cả các nút trong mạng, nhóm này được gọi là “nhóm chuyển” hay “forward set” nhiều thuật toán đã được dùng tối ưu hóa việc xây dựng nhóm chuyển. 3.4.3 Định tuyến đơn phát Phần này sẽ trình bày khái quát về một vài giao thức định tuyến đơn phát được sử dụng trong mạng tự hợp di động. Hình 3.2 – Một số giao thức định tuyến đơn phát trong mạng tự hợp di động Giao thức định tuyến đơn phát trong MANETs Định tuyến chủ động Định tuyến lai Định tuyến theo yêu cầu Định tuyến đám mây Distan ce Vector Link State 16 3.4.3.1 Định tuyến chủ động Các giao thức định tuyến theo chiến lược chủ động duy trì thông tin định tuyến đến các nút mạng đang tồn tại trong mạng ở mỗi nút mạng. Định kỳ hoặc khi có sự thay đổi trong mạng, các nút mạng sẽ trao đổi thông tin định tuyến cho nhau bằng cách quảng bá thông tin định tuyến đến các nút láng giềng. o Ưu điểm: tính sẵn sàng cao và độ trễ thấp. o Khuyết diểm: tải mạng cao, sử dụng băng thông không hiệu quả, không thích hợp trong trường hợp kích thước mạng lớn cũng như đồ hình mạng thay đổi thường xuyên. Một trong những giao thức kinh điển sử dụng chiến lược chủ động để xây dựng thông tin định tuyến là giao thức Destination-Sequenced Distance-Vector (DSDV) [6] Giao thức DSDV dựa trên thuật toán Bellman-Ford, đặc biệt là giao thức định tuyến RIP trong mạng có dây. Theo đó mỗi nút mạng duy trì một bảng định tuyến lưu thông tin đường đi ngắn nhất tới tất cả các nút mạng khác trong mạng. Với mỗi dòng dữ liệu trong bảng định tuyến, giao thức DSDV sử dụng thêm tham số sequence number nhằm tránh tình trạng lặp khi trao đổi thông tin định tuyến mà giao thức RIP mắc phải. Thông tin định tuyến của một nút mạng được quảng bá hoặc gửi đến một số nút hàng xóm của nó theo định kỳ và tăng tần suất quảng bá khi phát hiện đồ hình mạng thay đổi. Các giao thức định tuyến chủ động lưu giữ tất cả đường đi đơn phát giữ tất cả các cặp nút. Do đó khi có như cầu nút nguồn sẽ không bị bất kỳ độ trễ nào cho quá trình phát hiện đường đi nữa. Các giao thức định tuyến chủ động có thể tìm thấy đường đi tối ưu. Tuy nhiên giao thức này lại không thực sự phù hợp với mạng tự hợp di động. Do đó nhiều cải tiến đã được đề xuất để có thể sử dụng trong môi trường mạng tự hợp di động. 3.4.3.2 Giao thức định tuyến theo yêu cầu Ngược với giải pháp chủ động, các giao thức định tuyến theo nhu cầu chỉ thiết lập thông tin định tuyến khi nút nguồn có nhu cầu gởi dữ liệu đến một nút khác trong mạng. Khi đó nút nguồn bắt đầu quá trình thiết lập thông tin định tuyến đến nút đích. 17 o Ưu điểm: giảm tải mạng và dễ dàng tương thích khi có nút mạng mới gia nhập mạng. o Khuyết điểm: độ trễ cao, không thích hợp với môi trường mạng có lưu lượng cao. Giao thức Ad-hoc On-demand Distance Vector (AODV) [7] là một giao thức được xây dựng theo giải pháp này. Giao thức AODV chỉ thiết lập đường đi đến đích khi nơi gởi có nhu cầu và thông tin này được duy trì trong bộ đệm (cache) suốt phiên truyền thông giữa hai nút mạng. Khi một nút có nhu cầu gởi dữ liệu đến một nút khác, nếu như thông tin định tuyến không được tìm thấy trong bộ đệm, nút nguồn sẽ gởi một thông điệp dò tìm đường đi đến đích route request – RREQ cho toàn mạng. Những nút trong mạng khi nhận được thông điệp RREQ sẽ cập nhật thông tin định tuyến của chính mình. Song song đó, một nút gọi là x hồi đáp cho nút gởi một thông điệp route reply - RREP nếu như nút x chính là nút đích hoặc có thông tin định tuyến đến nút đích. Ngược lại, nút x tiếp tục quảng bá thông điệp RREQ đến các nút láng giềng để tìm đường đi đến đích. Quá trình dò tìm đường đi và phản hồi kết quả cho nút nguồn được minh họa trong hình 3.3. Tất cả các nút mạng lưu vết thông tin về địa chỉ và broadcast ID của các thông điệp RREQ để kiểm tra thông điệp đã xử lý hay chưa. Tuy nhiên khi các nút di chuyển, thông định định tuyến lưu trong bộ đệm bị sai dẫn đến giao thức thực thi không hiệu quả. 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 18 3.4.4 Định tuyến đa phát Trong định tuyến đa phát, gói tin từ một nút gửi thường phải được gửi đến nhiều nút nhận và tạo nên một nhóm đa phát. Tất cả các nút có thể đồng thời gửi dữ liệu, và bất kỳ nút nào cũng có thể tham gia và rời khởi nhóm một cách tùy ý. Trong các mạng tự hợp di động với các nhược điểm đã nêu ở phần trên, định tuyến đa phát trở thành vấn đề rất phức tạp. Những năm gần đây, nhiều giao thức định tuyến đa phát cho các mạng tự hợp di động đã được phát triển, một số thì dựa trên cơ chế thụ động , các đường đi được khám phá khi có nhu cầu; một số khác lại dựa trên cơ chế chủ động như định kỳ gửi phát tràn hoặc định kỳ cập nhất bảng định tuyến. 3.4.4.1 Multicast Ad hoc On-demand Distance Vector - MAODV Giao thức MAODV [8] được phát triển từ giao thức AODV. Nó lưu trữ một cây dùng chung chứa các nút nhận và các nút chuyển trung gian cho mỗi nhóm đa phát. Giao thức phát hiện một tuyến đường đa phát khi có yêu cầu thông qua cơ chế gửi gói tin quảng bá. Thành viên đầu tiên của nhóm đa phát trở thành “ nút leader” của nhóm. Nút leader lưu giữ và quảng bá một số thứ tự cho nhóm đa phát thông qua gói tin HELLO. Các nút sử dụng thông tin trong gói HELLO đề cập nhật bảng yêu cầu của chúng. Khi một nút muốn tham gia vào nhóm đa phát, nút sẽ gửi gói tin truy vấn tìm đường đi (RREQ) tới nút leader thông qua đơn phát hoặc gửi quảng bá. Chỉ có nút leader hoặc các nút thành viên của nhóm có số thứ tự cao hơn nút truy vấn mới được phép gửi phản hồi cho nó. Khi các nút như thế nhận được gói tin RREQ, nút sẽ chon số thứ tự lớn nhất và số chặng nhỏ nhất để gửi đơn phát gói tin phản hồi RREP cho nút truy vấn. Gói RREP chứa khoảng cách từ nút gửi phản hồi tới nút leader và số thứ tự hiện thời của nhóm. Khi nút truy vấn nhận được nhiều gói RREP nó sẽ chọn gói có số thứ tự lớn nhất và gần nút leader nhất, sau đó nút gửi gói MACT tới chặng tiếp theo để khởi tạo tuyến đường. Các nút không phải lá khi muốn rời khỏi nhóm sẽ gửi thông điệp với cờ prune được thiết lập tới chặng kế tiếp của nút. MAODV sử dụng tìm kiếm vòng mở rộng 19 (ERS) để duy trì cây đa phát. Khi link lỗi giữa hai nút được phát hiện, nút bị tách rời sẽ gửi gói tin RREQ sử dụng ERS. Các nút gần leader hơn sẽ gửi phản hồi. Nếu nút không nhận được phản hồi, nó tự mình xây dựng cây đa phát mới. o Nhận xét :  Trở ngại lớn nhất của MAODV là độ trễ cao và overhead lớn. Hơn nữa tỉ lệ nhận gói tin thấp trong các mô phỏng có nút mạng di chuyển nhiều, số lượng nút thành viên lớn, và độ tải cao. Trường hợp tồi tệ nhất xảy ra khi nút leader bị lỗi. Hình 3.4 – Giao thúc MAODV (a) Nút R3 tham gia nhóm. (b) Nhóm sau khi nút R3 tham gia 20 3.4.4.2 On-Demand Multicast Routing Protocol On-demand Multicast Routing Protocol hay ODMRP [8] là giao thức đa phát dựa trên nút nguồn. Ở đây chúng ta quan tâm đến thuật ngữ “nhóm chuyển” – là tập các nút chuyển gói dữ liệu đa phát. Khi nguồn đa phát có dữ liệu để gửi nhưng không có bất ký thông tin định tuyến nào, nút sẽ phát tràn gói tin JOIN DATA. Khi một nút nhận được một gói tin JOIN DATA gốc, nó lưu lại ID nút gửi và tiếp túc gửi quảng bá gói tin đó. Khi gói JOIN DATA đến được nút nhận, nút nhận sinh gói tin JOIN TABLE và gửi quảng bá cho các hàng xóm của nó. Khi một nút nhận đượcgói JOIN TABLE, nếu ID của nút bằng với giá trị trường next ID của một trong các entry thuộc JOIN TABLE thì nút sẽ quyết định mình nằm trên đường đi tới nguồn, điều này đồng nghĩa với việc nút này thuộc về “nhóm chuyển”. Sau đó nó bắt đầu gửi quảng bá gói JOIN TABLE của chính nó. Gói JOIN TABLE được gửi qua từng thành viên trong nhóm chuyển cho đến khi tới được nguồn đa phát. Các nút gửi cập nhật thông tin về các nút thành viên bằng cách gửi định kỳ các gói JOIN DATA. Các nút tự do rời khởi nhóm và không cần gửi bất kỳ gói tin nào vào mạng. o Nhận xét :  Hạn chế chính của quá tải do các gói tin điều khiển gây nên trong quá trình duy trì nhóm chuyển và phát tràn gói tin toàn mạng.  Hạn chế thứ hai chính là hiện tượng nhân bản các gói tin trong mạng  Cuối cùng, các nút nguồn phải là thành viên của mạng lưới đa phát cho dù chúng không muốn nhận các gói đa phát. 21 Hình 3.5 – Giao thức ODMRP 3.5 Những thách thức khi triển khai công nghệ ngang hàng trong các mạng tự hợp di động Kiến trúc các mạng ngang hàng và tự hợp di động có rât nhiều triển vọng để kết hợp với nhau. Mặc dù chúng xây dựng và hoạt động trên các lớp khác nhau, nhưng ý tưởng kết hợp hai kiến trúc có tính khả quan rất cao. Tuy nhiên , để thu được một hệ thống hoạt động hiệu quả khi kết hợp hai kiến trúc thì điều cần thiết là phải xây dựng một tầng kết nối trung gian giữa chúng. Các ứng dụng ngang hàng có các thuật toán tối ưu để tìm kiếm thông tin trong tầng mạng xếp chồng của chúng, nhưng để gửi dữ liệu chúng dựa trên TCP và các kết nối bền vững. Bất cứ lúc nào kết nối bị lỗi, các nút ngang hàng cho rằng nút đối tác của mình rời khỏi mạng và nút sẽ chuyển sang nút đối tác khác, một nút được chọn ngẫu nhiên. 22 Trong mạng tự hợp di động, các liên kết thường xuyên bị phá vỡ bởi các nút luôn di chuyển. Bất cứ khi nào hai nút kế nhau di chuyển ra ngoài tầm phủ sóng nhau thì liên kết giữa chúng bị phá vỡ. Một giao thức trong mạng tự hợp di động không biết về các ứng dụng ngang hàng, có gắng khởi tạo lại một đường đi mới tới nút đích cũ. Trong khi đó việc tạo một đường đi mới tới đích cũ sau khi mô hình mạng bị thay đổi, các nguồn khác có thể hiệu quả hơn. Do vậy các nút mạng tự hợp di động phải thông báo những đường đi bị lỗi với nút mạng ngang hàng ở tầng trên. Bởi vì đa số mạng ngang hàng được triển khai trên cơ sở hạ tầng những mạng cố định, nút trong mạng ngang hàng không phân biệt giữa nút đối tác ở gần hay ở xa. Các mạng ngang hàng chỉ sử những kết nối đa chặng cho quá trình truy vấn tìm kiếm. Và sử dụng kết nối TCP để truyền dữ liệu giữa nút nguồn và nút đích. Khoảng cách giữa các nút không ảnh hưởng đến hoạt động của kết nối. Do vậy, các nút ngang hàng có thể lấy được những dữ liệu ở xa hoàn toàn tương tự ở gần. Khoảng cách giữa hai đầu kết nối trong mạng tự hợp di động được đo bằng số chặng trung gian giữa chúng. Đây là tham số quan trọng trong định tuyến. Đường di quá dài sẽ làm tăng quá tải định tuyến, cũng như tăng độ trễ phiên truyền gói tin, kéo theo giảm hiệu năng toàn mạng. Do vậy, các ứng dụng máy khách phải sắp xếp các truy vấn đến tùy theo khoảng cách từ chúng tới nút dích. Như vậy, một cơ chế kết hợp giữa mạng ngang hàng và tự hợp di động phải phải phù hợp với kiến trúc tầng bên dưới và cả lớp xếp chồng trên tầng ứng dụng. Các nút mạng có tài nguyên giới hạn, chẳng hạn năng lượng pin, dung lượng bộ nhớ, tốc độ xử lý, băng thông ….. khiên vấn đề trở nên phức tạp hơn nhiều lần. Hệ quả khiến các hệ thống ngang hàng di động sử dụng những tài nguyên này sao cho hiệu quả nhất. 23 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 giới thiệu về giao thức phân bổ nội dung P2MAN. 4.1 Giới thiệu chung P2MAN dựa trên giao thức đa phát PUMA nhằm đạt được phân bổ nội dung tin cậy trên tầng ứng dụng . Trong giao thức PUMA , các nút nhận sẽ khởi tạo một mesh dùng chung để nhận dữ liệu. Peer-to-MANETs (P2MAN) là một giao thức phân bổ nội dung cho các mạng tự hợp di động. P2MAN sử dụng các nhóm đa phát để phân bổ nội dung, và một nhóm đa phát đặc biệt gọi là “nhóm đa phát dùng chung” - PC để truyền các gói tin điều khiển. Khi một nút P2MAN khởi động nó tham gia vào nhóm đa phát PC để trao đổi các gói tin điều khiển. Tất cả các nút muốn chia sẻ dữ liệu là thành viên của nhóm PC. Vị trí của dữ liệu không được lưu tại bất kỳ nút mạng nào. Để tìm kiếm một đối tượng dữ liệu nào đó, nút nhận sẽ gửi thông điệp truy vấn đến nhóm đa phát dùng chung mà không cần phát tràn gói tin đó trong toàn mạng. Các nút mang dữ liệu được truy vấn, thông qua nhóm PC sẽ được phát hiện. Và thông qua nhóm PC nút sẽ gửi thông điệp trả lời đến nút yêu cầu đối tượng dữ liệu. Thông điệp trả lời có chứa các chỉ dẫn để nút yêu cầu có thể nhận được dữ liệu mong muốn. Giống như trong hầu hết các mạng ngang hàng, P2MAN sẽ chia nhỏ dữ liệu để phân bổ. Nút có dữ liệu sẽ quyết định cách thức chia nhỏ dữ liệu thành các mảnh, đồng thời cũng quyết định nhóm đa phát nào sẽ được sử dụng để gửi dữ liệu. Thông điệp phản hồi chứa các thông tin chỉ dẫn như : tên đối tượng dữ liệu, địa chỉ nhóm đa phát sẽ được sử dụng để truyền dữ liệu, số lượng và kích thước các mảnh…. Nút nhận sẽ tham gia vào nhóm đa phát được chỉ định trong gói tin phản hồi , gửi một gói tin xác nhận vào nhóm PC và bắt đầu quá trình nhận dữ liệu. Sau khi nhận được gói tin phản hồi đầu tiên, nút nhận sẽ lờ đi tất cả các gói phản hồi đến sau đó. Như vậy, nút quyết định sẽ chỉ nhận dữ liệu từ một nút gửi duy nhất. Do đặc tính di động của các nút trong mạng tự động di hợp, chúng ta sẽ không nhận được bất kỳ sự tin cậy nào từ tầng giao vận trong quá trình truyền dữ liệu như ở 24 thức TCP. Trong P2MAN, phiên truyền tin cậy sẽ được thực thi ở tầng ứng dụng nhờ cơ chế sửa lỗi. Khi một nút khởi động cơ chế sửa lỗi , nó sẽ khởi động lại quá trình truy vấn dữ liệu. Tuy nhiên, trong thông điệp truy vấn lần này sẽ chứa các thông tin hướng dẫn, theo đó nút gửi sẽ chỉ gửi lại các mảnh lỗi. Kết quả đánh giá cho thấy giao thức phân bổ nội dung P2MAN hoạt động hiệu quả trong trong các trường hợp gia tăng nút truy vấn, gia tăng kích thước đối tượng dữ liệu và các nút mạng di chuyển. 4.2 Giao thức đa phát PUMA PUMA là giao thức đa phát trong đó các nút nhận sẽ chủ động khởi tạo một mesh để phục vụ cho quá trình nhận dữ liệu. Mặc định, nút nhận đầu tiên tham gia nhóm đa phát sẽ đóng vai trò là lõi của nhóm, trong trường hợp có nhiều nút nhận đồng thời tham gia vào nhóm thì nút có địa chỉ IP lớn nhất sẽ được chọn làm lõi.PUMA là giao thức đơn giản, nó chỉ sử dụng một gói tin điều khiển duy nhất Multicast Announcement. PUMA không cần đến bất cứ kênh truyền đơn phát nào , tất cả các phiên truyền nhận dữ liệu đều là broadcast. Thành viên của mesh sẽ chỉ bao gồm thành viên nhóm đa phát và các nốt kết nối giữa chúng. Khi một thông điệp Multicast annoucement truyền đi trong mesh , các nút sẽ biết được đường đi ngắn nhất tới lõi. Theo cách này, các gói dữ liệu sẽ được định tuyến tới đích một cách nhanh nhất. Trên đường hướng về lõi, gói dữ liệu sẽ gặp phải hai trường hợp : (a) gói đi dọc theo tất cả các đường đi có thể cho đến khi gặp lõi , hoặc (b) gói sẽ đến một thành viên của mesh trước khi đến được lõi. Trong trường hợp (b) , gói sẽ được truyền giới hạn trong các thành viên của mesh. Khi lõi của nhóm gặp lỗi , quá trình chọn lõi sẽ được kích hoạt để chọn ra một lõi mới. 4.3 Cơ chế hoạt động của P2MAN Để thuận tiên cho việc trình bày, chúng tôi gọi nút có bản copy đầy đủ của một đối tượng được chia sẻ gọi là nút gửi, nút có như cầu tải một đối tượng dữ liệu được chia sẻ nào gọi là nút truy vấn. Ở đây , cả nút gửi và nút truy vấn đều thuộc vào nhóm PC. Địa chỉ nhóm PC được xác định trước và được tất cả các nút đều biết đến nhóm. 25 Hình 4.1 – Mô phỏng P2MAN với các loại nút 4.3.1 Tìm kiếm dữ liệu Để tìm kiếm dữ liệu , nút truy vấn gửi “thông điệp truy vấn” tới nhóm PC. Thông điệp truy vấn có chứa định danh của đối tượng, chẳng hạn tên đối tượng … Do được gửi tới nhóm PC nên tất cả nút thành viên của nhóm đều sẽ nhận được thông điệp truy vấn đó. Các nút có dữ liệu chia sẻ sẽ trả lời bằng cách gửi “thông điệp phản hồi” trở lại nhóm PC. Trong trường hợp nút truy vấn không nhận được thông điệp phản hồi nào , thì định kỳ cứ sau một khoảng thời gian nút lại lặp lại quá trình truy vấn. Quá trình trên sẽ dừng lại khi nút nhận được thông điệp phản hồi hoặc sau một số lần lặp lại nào đó. Thông điệp phản hồi sẽ chứa các thông tin về đối tượng được truy vấn, chẳng hạn như :  Tên đối tượng  Địa chỉ nhóm đa phát được sử dụng để gửi các mảnh dữ liệu  Số lượng các mảnh 26 Hình 4.2 – Tìm kiếm nội dung 4.3.2 Phân bổ dữ liệu Sau khi gửi đi thông điệp truy vấn, nút sẽ khởi động Timer để chờ các thông điệp phản hồi từ các nút có dữ liệu. Khi nhận được thông điệp phản hồi đầu tiên từ một nút gửi nào đó trong mạng, nút truy vấn sẽ kiểm tra các thông tin trong thông điệp, tham gia vào nhóm đa phát đã được nút gửi chọn cho việc phân bổ dữ liệu , đồng thời gửi thông điệp đăng ký tới nút gửi thông qua nhóm đa phát PC. Một điểm cần chú ý ở giao thức P2MAN là sau khi gửi đi thông điệp đăng ký, nút truy vấn khởi động Timer để nhận gói dữ liệu đầu tiên, trong quá trình này nút sẽ bỏ qua những thông điệp phản hồi từ các nút có dữ liệu khác. Như vậy, nút sẽ chỉ tham gia nhận dữ liệu từ một nút gừi thông qua một nhóm đa phát duy nhất do nút gửi chỉ định. Nút lựa chọn thông điệp đầu tiên bởi vì thông điệp đến đầu tiên sẽ đi trên đoạn đường tốt nhất giữa nút truy vấn và nút có dữ liệu. Thông điệp đăng ký có chứa định danh của nút gửi đã được chọn làm nguồn phát dữ liệu. Khi nút gửi được chọn nhận được thông điệp đăng ký thì nó bắt đầu gửi dữ liệu vào nhóm đa phát, và sau khi gửi xong dữ liệu nút sẽ không làm gì nữa. Các nút gửi không phải nút được chọn sẽ bỏ qua thông điệp được chọn. Sau khi gửi thông điệp đăng ký nút gửi sẽ khởi động Timer để bắt đầu nhận dữ liệu, mỗi khi nhận được gói dữ liệu nút sẽ khởi động lại Timer cho gói dữ liệu tiếp 27 theo. Trong trường hợp xảy ra hiện tượng timeout, nút sẽ khởi động “cơ chế sửa lỗi” – được trình bày ở mục 4.3.3. Hình 4.3 – Nhận gói dữ liệu 4.3.3 Cơ chế sửa lỗi Do không có bất kỳ cơ chế nào đảm bảo truyền tin tin cậy ở các tầng bên dưới nên trong giao thức này chúng tôi thực thi cơ chế sửa lỗi ở tầng ứng dụng với mục đích đảm bảo một tính tin cậy cho quá trình phân bổ nội dung. Cơ bản , khi một nút chuyển sang chế độ sửa lỗi nó sẽ khởi động lại quá trình tìm kiếm nội dung. Tuy nhiên trong thông điệp truy vấn được gửi đi sẽ cung cấp thêm thông tin về các mảnh lỗi. Do đó nút gửi sẽ chỉ gửi lại những mảnh lỗi. 28 Hình 4.4 – Cơ chế sửa lỗi 29 Chương 5 Đề xuất ý tưởng và kết quả thu được Phần này của khóa luận đề xuất một ý tưởng cải tiến giao thức phân bổ nội dung ngang hàng P2MAN. 5.1 Đặt vấn đề Như đã trình bày ở chương 4, giao thức P2MAN chỉ cho phép nút truy vấn nhận dữ liệu từ một nút gửi duy nhất thông qua một nhóm đa phát được nút gửi chỉ định. Tuy nhiên trong môi trường mạng di động thì các liên kết luôn bị phã vỡ, mô hình mạng luôn thay đổi nên việc tải dữ liệu từ một nguồn hiệu quả sẽ không cao. Trong khi đó nút hoàn toàn có thể nhận dữ liệu từ nhiều nút gửi khác nhau thông qua các nhóm đa phát. Từ nhận định trên chúng tôi đề xuất ý tưởng cải tiến giao thức P2MAN nhằm cho phép nút truy vấn có thể đồng thời nhận dữ liệu từ nhiều nút gửi khác nhau. 5.2 Giải thuật cải tiến Trong giao thức phân bổ nội dung cải tiến nút truy vấn sẽ yêu cầu nút có dữ liệu gửi cho nó một số mảnh còn thiếu nào đó và chưa được phân công cho nút gửi nào khác. Để đơn giản chúng tôi giả thiết tất cả nút gửi đều có dữ liệu giống nhau, các nút có cách chia nhỏ dữ liệu giống nhau. Ta quy ước : Tập A = { P0, P1, ……………, Pn} là tập biểu diễn tất cả các mảnh được chia nhỏ của đối tượng dữ liệu. Tập A có n phần từ. Tập M = {Mi | i = 0,1,……. , n} là tập biểu diễn các mảnh mà nút gửi chưa nhận được và chưa được phân công cho bất kỳ nút gửi nào. Tập W = {Wi | i = 0, 1, …. ,n} là tập biểu diễn các mảnh dữ liệu mà nút đang đợi để nhận từ các nút gửi. Các tập A, M và W ở đây không phải chứa các mảnh dữ liệu thật sự mà chỉ là các tập biểu diễn các mảnh. Mỗi phần tử chứa thông tin tương ứng về một mảnh của đối tượng, chẳng hạn như ID của mảnh dữ liệu. Để thuận tiện cho việc trình bày, chúng tôi gán cho phần tử Pi giá trị i tương ứng với ví trí của nó trong tập A. 30 Số nguyên N với điều kiện 0 gọi là “bước nhảy” là số lượng tối đa các mảnh dữ liệu mà nút truy vấn mong muốn nhận được từ nút gửi trong một phiên giao tiếp. 5.2.1 Tìm kiếm Khi một nút có nhu cầu tìm kiếm một đối tượng dữ liệu nào đó, nút sẽ gửi một thông điệp truy vấn tới nhóm đa phát PC. Thông điệp truy vấn sẽ chứa thông tin về đối tượng dữ liệu được truy vấn chẳng hạn ID, và thông địa chỉ của nút truy vấn. Thông điệp này sau đó sẽ được phát tràn trong nhóm PC. Sau khi gửi đi thông điệp truy vấn nút sẽ khởi động Timer để đợi các thông điệp phản hồi. Sau khoảng thời gian timeout nếu không nhận được thông điệp phản hồi nào từ nhóm PC nút truy vấn sẽ khởi động lại quá trình tìm kiếm. Quá trình này sẽ lặp lại cho đến khi nút nhận được thông điệp truy vấn hoặc sau một số lần lặp nào đó. Trong thời điểm nút bắt đầu quá trình tìm kiếm A = M = W = . 5.2.2 Phân bổ dữ liệu Do thông điệp truy vấn được phát tràn nên tất cả thành viên nhóm PC sẽ nhận được thông điệp này. Khi một nút có dữ liệu nhận được thông điệp truy vấn nó sẽ trả lời bằng cách gửi thông điệp phản hồi tới nhóm PC. Trong thông điệp phản hồi có chứa các thông tin như : o ID có dữ liệu hay còn gọi là nút gửi o ID nhóm đa phát được nút gửi chọn để gửi dữ liệu o Số lượng các mảnh dữ liệu Thông điệp này được phát tràn trong nhóm PC và đến được nút truy vấn. Khi nút truy vấn nhận được gói phản hồi đầu tiên từ một nút gửi nào đó, dựa vào thông tin trong thông điệp phản hồi nút truy vấn sẽ biết được các thông tin về đối tượng dữ liệu mà nó muốn tải về, chẳng hạn như : đối tượng được chia thành bao nhiêu mảnh, kích thước mỗi mảnh là bao nhiêu … Tại thời điểm này tập M = A = { P0, P1, …… , Pn } và tập W = . Mỗi khi nhận được thông điệp phản hồi, nếu nút truy vấn thấy đây là thông điệp phản hồi đầu tiên mà nó nhận được từ nút gửi này kể từ lần gửi gói tin truy vấn gần nhất , nó sẽ lấy trong tập M phần tử có giá trị i nhỏ nhất và tối đa N-1kế tiếp trong M để phân công cho nút gửi này, đồng thời loại các phần từ này khỏi tập M và thêm 31 chúng vào tập W. Thông tin về các mảnh dữ liệu dữ liệu này sẽ nút thêm vào thông điệp đăng ký và gửi đi. Khi nút nhận tương ứng nhận được thông điệp đăng ký, dựa vào thông tin trong thông điệp nút sẽ chỉ gửi các mảnh được yêu cầu tới nhóm đa phát đã được lựa chọn. Sau khi gửi gói đăng ký đi, nút truy vấn sẽ khởi động Timer cho gói dữ liệu đầu tiên. Khi nhận được một mảnh dữ liệu Pi nút sẽ loại khỏi tập W và M phần tử Mi và Wi, đồng thời khởi động Timer cho gói dữ liệu tiếp theo. Nếu xảy ra timeout, nút sẽ khởi động cơ chế sửa lỗi được trình bày ở mục sau. 5.2.3 Cơ chế sửa lỗi Cơ chế sửa lỗi được khởi động mỗi khi xảy ra mất mát các mảnh dữ liệu trong quá trình gửi và nhận. Như đã trình bày ở trên sau khi gửi đi thông điệp đăng ký nút truy vấn sẽ khởi động Timer để bắt đầu nhận các mảnh dữ liệu, và mỗi khi nhận được mảnh dữ liệu nút sẽ khởi động lại Timer để đợi gói dữ liệu tiếp theo. Nếu sau khoảng thời gian timeout, nút không nhận thêm được mảnh dữ liệu nào tương ứng với nút gửi đó thì quá trình sửa lỗi được khởi động. Khi quá trình sửa lỗi được khởi động, nút truy vấn sẽ lấy các phần tử tương ứng với các mảnh dữ liệu mà nút đang chờ ra khỏi tập W và thêm chúng vào tập M, đồng thời gửi gói tin truy vấn vào mạng để khởi động lại quá trình nhận dữ liệu. 5.2.4 Ví dụ minh họa Sau đây là một ví dụ minh họa cho hoạt động của giao thức 32 Hình 5.1 – Mô tả các thành viên trong nhóm đa phát PC Hình 5.1 mô tả một mạng tự hợp di động gồm 15 nút mạng, trong đó các nút C, E, G là các nút gửi, còn nút N là nút truy vấn. Các nút C, E và G cùng chứa một đối tượng mà nút N muốn tải về và chúng cùng chia nhỏ đối tượng dữ liệu này thành 6 mảnh nhỏ mỗi khi nhận được yêu cầu gửi đối tượng. Giá trị bước nhảy N = 2 Trong hình 6.2 mô tả các tập hợp A, W, M tại các nút C, E, G lúc các nút khởi động. 33 Hình 5.2 – Quá trình tìm kiếm Để tìm kiếm dữ liệu nút N gửi gói tin truy vấn vào mạng, và lần lượt nhận được gói phản hồi từ các nút G, C và E. Tại thời điểm nút nhận được gói tin phẩn hồi đầu tiên từ G, nút dựa vào thông tin về đối tượng dữ liệu trong thông điệp phản hồi để xây dựng các tập A, W, M. Ban đầu tập các mảnh dữ liệu còn thiếu sẽ là tất cả các mảnh của đối tượng. Và tập các mảnh dữ liệu đã được phân công W sẽ bằng rỗng như trong hình 6.3 dưới đây 34 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 Sau khi nhận được gói phản hồi từ G, nút N kiểm tra trong M và thấy gói dữ liệu có vị trí nhỏ nhất mà nó chưa nhận được là gói P0, và gói kế tiếp là P1. Do vậy, N chọn G làm nút gửi cho hai gói dữ liệu P0, P1. Nút N loại P0, P1 ra khỏi M và thêm hai mảnh đó vào tập W. N tham gia vào nhóm đa phát đã được G chọn và gửi thông điệp đăng ký để bắt đầu việc nhận các mảnh P0, P1. Tiếp sau đó N nhận được thông điệp phản hồi từ nút C, N kiểm tra tập M và thấy hai phần từ có vị trí bé nhất mà nó chưa nhận được là P2 và P3 nên nó chọn C là nút gửi cho các mảnh P2, P3. Tương tự N chọn E là nút gửi các mảnh P4, P5. Quá trình này thể hiện ở các hình 6.4 a – b – c . Hình 5.4 a – N nhận gói phản hồi từ G 35 Hình 5.4 b – N nhận gói phản hồi từ C Hình 5.4 c – N nhận gói phản hồi từ E Sau khi gửi gói tin đăng ký tới nhóm PC, N sẽ khởi động Timer cho các gói tin P0, P1. Giả sử N nhận được mảnh P0 trước khi xảy ra timeout, N sẽ loại P0 ra khỏi tập W. và thiết lập Timer để tiếp tục đợi gói tin P0. Trong lúc đợi gói tin P0, nếu các mảnh P2, P3, P4, P5 đến trước thì nút N sẽ nhận các mảnh đó và loại các phần từ P2, P3, P4, P5 ra khỏi tập W. Sau thời gian timeout nếu nút N vẫn chưa nhận được mảnh P0, N sẽ loại P0 khỏi tập W và thêm P0 vào tập M. Đồng thời gửi gói tin truy vấn vào mạng để thực hiện quá trình sửa lỗi. 36 5 .3 Kết quả thu được Bảng 5.5 mô tả các tham số của chương trình mô phỏng NS-2. Trong khóa luận này để tính thời gian tải của mạng trong các mô phỏng khác nhau, chúng tôi thực hiện chạy mô phỏng 6 lần rồi lấy giá trị trung bình của chúng. Đối với mỗi lần chạy mô phỏng, thời gian tải được tính bằng trung bình các thời gian để tất cả nút truy vấn được chọn hoàn thành việc tải dữ liệu. Tham số Miêu tả Phần mềm mô phỏng NS-2 phiên bản all-in-one 2.3.4 Số lần thực hiện mẫu 6 Phạm vi thực hiện 1000m X 1000m Di chuyển Nút di chuyển ngẫu nhiên Thời gian tạm dừng 0s Tầm phủ sóng của nút 250m Băng thông 2Mbps Giao thức tầng MAC 802.11 DCF Kích thước mỗi mảnh dữ liệu 512 byte Hình 5.5 – Các tham số mô phỏng 37 Hình 5.6 là kết quả chạy chương trình với bộ mô phỏng gồm 100 nút mạng, các nút di chuyển ngẫu nhiên với tốc độ 1m/s trên diện tích 2200mX600m. Qua đồ thị ta thấy thởi gian tải trong mạng tỉ lệ nghịch với số lượng nút gửi trong mạng. Thời gian tải trung bình đã giảm đi đáng kể khi số lượng nút gửi tăng từ : 1 nút , 5 nút, 10 nút , 15 nút và 20 nút…. Điều này đã đúng với nhận định ban đầu khi đề xuất ý tưởng của chúng tôi là “số nút gửi càng lớn thì thời gian download dữ liệu càng giảm.” Hình 5.6 – Thời gian nhận X Số lượng nút gửi 38 Hình 5.7 là kết quả chạy chương trình với số lượng nút truy vấn tăng dần theo các giá trị 5 nút, 10 nút, 15 nút, 20 nút. Cả hai đồ thị đều cho ta thấy khi số lượng nút truy vấn tăng lên thì thời gian tải dữ liệu cũng tăng lên. Đồ thị màu xanh biểu diễn phụ thuộc giữa thời gian tải với số lượng nút truy vấn của giao thức phân bổ cải tiến . Đồ thị màu đỏ biểu diễn phụ thuộc giữa thời gian tải với số nút truy vấn của giao thức cũ. Qua đồ thị chúng ta thấy rõ với số lượng nút có dữ liệu là 15 nút thì thời gian tải của giao thức phân bổ cải tiến thấp hơn khá nhiều so với giao thức cũ, hơn nữa tốc độ gia tăng của thời gian tải cũng thấp hơn rất nhiều so với giao thức cũ. Hình 5.7 – Thời gian tải X Số lượng nút truy vấn 39 Hình 5.8 là kết quả chạy mô phỏng với tốc độ di chuyển của nút mạng với các giá trị tăng dần : 0m/s , 2m/s , 5m/s , 10m/s , 20m/s , 30m/s. Mạng có 50 nút, trong đó có 5 nút gửi và 5 nút truy vấn, di chuyển liên tục trong khu vực có diện tích 1000m X 1000m. Tuy chúng ta thấy hai đồ thị không tuyến tính nhưng với giao thức mới thì chất lượng tải dữ liệu ổn định hơn. Điều đó chúng tỏ giao thức phân bổ nội dung sau khi cải tiến đã đạt dộ ổn định cao hơn trong môi trường di động. Hình 5.8 – Thời gian tải X Tốc độ di chuyển của nút mạng 40 KẾT LUẬN Khóa luận đã trình bày những khái niệm cơ bản về công nghệ mạng ngang hàng, cũng như các đặc điểm cơ bản của các mạng không dây di động, đặc biệt là các mạng tự hợp di động. Khóa luận đã đạt được những thành công nhất định trong việc cải tiến giao thức đa phát ngang hàng P2MAN cho phép một nút đồng thời nhận dữ liệu từ nhiều nguồn từ đó đã giảm thấp thời gian download trong mạng và tốc độ download ổn định hơn. Tuy nhiên mặt hạn chế của phương pháp này chính là quản lý overhead xuất phát từ việc gửi các gói tin điều khiển. Trong thời gian tới chúng tôi sẽ tiếp tục nghiên cứu để đề xuất phương án tối ưu hơn. Trong quá trình xây dựng và trình bày khóa luận này, chúng tôi không tránh khỏi nhiều thiếu sót. Rất mong nhận được sự góp ý của thầy cô và các bạn. Chúng tôi xin chân thành cảm ơn ! 41 PHƯƠNG HƯỚNG TIẾP THEO Trong chương trình ,giá trị bước nhảy N ảnh hưởng rất lơn đến hiệu quả của chương trình. Tuy nhiên chúng tôi chọn bước nhảy N một cách tùy ý nên chắc hẳn còn nhiều hạn chế cho hoạt động của giao thức. Hơn nữa các khoảng thời gian timeout cũng chưa được đánh giá một cách khoa học, đặc biệt là thời gian timeout giành cho quá trình sửa lỗi. Chính vì vậy , trong thời gian tới chúng tôi đẩu tư thời gian nghiên cứu để có thế áp dụng giao thức để xây dựng một chương trình phân bổ nội dung ngang hàng có hiệu quả. 42 TÀI LIỆU THAM KHẢO [1] R. Vaishampayan and J. J. Garcia-Luna-Aceves, “Efficient and robust multicast routing in mobile ad hoc networks,” IEEE International Conference on Mobile Ad-hoc and Sensor Systems, pp. 304–313, 2004. [2] “The network simulator,” [3] S. Doria and M. A. Spohn “A Multicast Approach for Peer-to- peer Content Distribution in Mobile Ad Hoc NetWork” Proceedings of the 2009 IEEE conference on Wireless Communications & Networking Conference Budapest, Hungary Pages: 2920-2925 Year of Publication: 2009 [4] Peer to Peer Systems and Applications, tr 9 [5] [6] ACM SIGCOMM Computer Communication Review Volume 24 , Issue 4 (October 1994) [7] C. Perkins and E. Royer, “Ad hoc on demand distance vector (aodv) routing,” in Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, February 1999. [8] E. Royer and C. Perkins, “Multicast operation of the ad hoc on-demand distance vector routing protocol,” in Proceedings of Mobicom, August 1999. 43