Sử dụng mô hình thế giới nhỏ trong truyền hình mạng ngang hàng

  • Số trang: 63 |
  • Loại file: PDF |
  • Lượt xem: 17 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 26946 tài liệu

Mô tả:

MỤC LỤC MỞ ĐẦU ................................................................................................................1 Chƣơng 1. TỔNG QUAN .......................................................................................4 1.1. Khái niệm mạng ngang hàng ...........................................................................4 1.2. Phân loại mạng ngang hàng .............................................................................5 1.2.1. Hệ thống ngang hàng lai ghép ...............................................................5 1.2.2. Mạng ngang hàng thuần túy (Pure Peer-to-peer System) ......................7 1.2.2.1. Khái niệm về lớp mạng phủ ............................................................................. 8 1.2.2.2. Mạng ngang hàng thuần túy không có cấu trúc................................................ 8 1.2.2.3. Mạng ngang hàng có cấu trúc........................................................................... 9 1.3. Phƣơng pháp truyền thông mạng ngang hàng ...............................................10 1.3.1. Đẩy (Push)............................................................................................11 1.3.2. Kéo (Pull) .............................................................................................11 1.3.3. Kéo đẩy xen kẽ .....................................................................................11 1.3.4. Phƣơng pháp truyền thông lan tỏa (gossip protocol) ...........................13 1.4. Giới thiệu về trình giả lập iGridMedia ..........................................................14 1.4.1. Giới thiệu chung iGridMedia ...............................................................14 1.4.2. Mô hình hoạt động ...............................................................................15 1.4.3. Kiến trúc chung của trình mô phỏng....................................................16 1.4.3.1. Cách thức hoạt động ....................................................................................... 16 1.4.3.2. Kiến trúc lớp mạng phủ .................................................................................. 17 Chƣơng 2. TRUYỀN HÌNH NGANG HÀNG TRÊN MẠNG THẾ GIỚI NHỎ .19 2.1. Ứng dụng chia sẻ video, truyền hình trên mạng ngang hàng ........................19 2.2. Các loại mô hình lớp mạng phủ - Overlay Network......................................22 2.2.1. Khái niệm lớp mạng phủ ......................................................................22 2.2.2. Mạng ngẫu nhiên - Random graphs .....................................................23 2.2.2.1. Định Nghĩa ..................................................................................................... 23 2.2.2.2. Tính chất ......................................................................................................... 24 2.2.3. Mạng bao đóng – Scale free .................................................................25 2.2.3.1. Định nghĩa: ..................................................................................................... 25 2.2.3.2. Tính chất ......................................................................................................... 27 2.2.3.3. Xây dựng đồ thị bao đóng .............................................................................. 27 2.2.4. Mạng thế giới nhỏ ................................................................................29 2.2.4.1. Mô tả mạng thế giới nhỏ. ............................................................................... 29 2.2.4.2. Tính chất của mạng thế giới nhỏ .................................................................... 31 2.3. Ứng dụng mạng thế giới nhỏ .........................................................................33 2.3.1. Đánh giá về các lớp mạng phủ .............................................................33 2.3.2. Truyền dữ liệu trong mạng thế giới nhỏ ..............................................34 Chƣơng 3. GIẢI PHÁP XÂY DỰNG MẠNG THẾ GIỚI NHỎ .........................37 3.1. Xây dựng mô hình lý thuyết ..........................................................................37 3.2. Giải thuật xây dựng mô hình thế giới nhỏ dựa vào xây dựng nhóm .............38 3.3. Giải thuật xây dựng mạng thế giới nhỏ dựa trên độ trễ liên kết của các nút mạng. 43 3.4. Đề xuất giải thuật cải tiến. .............................................................................47 3.4.1. Giải thuật GoCast: ................................................................................47 3.4.2. Đề xuất .................................................................................................49 Chƣơng 4. MÔ PHỎNG VÀ ĐÁNH GIÁ HIỆU NĂNG .....................................51 4.1. Phƣơng thức mô phỏng ..................................................................................51 4.2. Kết quả ...........................................................................................................54 4.2.1. Đánh giá về số lƣợng gói tin điều khiển mạng ....................................54 4.2.2. Đánh giá về tốc độ truyền nhận thông tin ............................................55 4.2.3. Đánh giá về thời gian trễ giữa nguồn và các nút trong mạng ..............56 4.2.4. Đánh giá khoảng cách trung bình trong mạng .....................................56 Chƣơng 5. KẾT LUẬN & PHƢƠNG HƢỚNG MỞ RỘNG ...............................58 TÀI LIỆU THAM KHẢO ....................................................................................59 DANH MỤC HÌNH ẢNH Hình 1. Mạng ngang hàng lai ghép .........................................................................5 Hình 2. Mạng ngang hàng thuần túy.......................................................................8 Hình 3. Cơ chế bảng băm phân tán (DHT) ...........................................................10 Hình 4. Ứng dụng truyền dữ liệu đa phƣơng tiện trên iGridMedia ......................15 Hình 5. Cách thức hoạt động của trình mô phỏng iGridMedia ............................16 Hình 6. Xây dựng lớp mạng phủ trong iGridMedia .............................................17 Hình 7. Phân loại ứng dụng chia sẻ video trên mạng ngang hàng........................19 Hình 8. Mô hình lớp mạng phủ .............................................................................22 Hình 9. Vị trí của lớp mạng phủ ...........................................................................23 Hình 10. Đồ thị ngẫu nhiên ...................................................................................24 Hình 11. Đồ thị bao đóng......................................................................................26 Hình 12. Phân biệt đồ thị bao đóng và đồ thị ngẫu nhiên .....................................26 Hình 13. Xây dựng đồ thị bao đóng......................................................................28 Hình 14. Mạng thông thƣờng, mạng thế giới nhỏ, mạng ngẫu nhiên ...................30 Hình 15. Xây dựng đồ thị thế giới nhỏ theo Kleinberg trong lƣới hai chiều........31 Hình 16. Tính phân cụm của đồ thị thế giới nhỏ ..................................................31 Hình 17. Mô hình truyền tin nội bộ của các nút trong một nhóm ........................35 Hình 18. Truyền tin giữa các nhóm ......................................................................36 Hình 19. Tƣơng quan liên kết gần, liên kết xa......................................................44 Hình 20. Ví dụ về độ trễ truyền tin .......................................................................46 Hình 21. Chƣơng trình mô phỏng .........................................................................53 Hình 22. Đánh giá về số lƣợng gói tin điều khiển mạng/giây ..............................54 Hình 23. Đánh giá tốc độ truyền nhận thông tin...................................................55 Hình 24. Độ trễ trung bình truyền dữ liệu trên các nút so với nguồn ...................56 Hình 25. Đánh giá khoảng cách trung bình giữa các nút mạng ............................57 MỞ ĐẦU Ngày nay, máy tính và mạng Internet đã trở thành một phần không thể thiếu của cuộc sống. Cùng với sự phát triển của Internet băng thông rộng và các thiết bị đa phƣơng tiện cá nhân, nhu cầu chia sẻ thông tin của ngƣời dùng cuối không chỉ dừng lại ở việc gửi và nhận những dòng văn bản, những file dữ liệu có sẵn với kích thƣớc nhỏ thì mô hình mạng truyền thống máy phục vụ/máy khách (Client/Server) ngày càng bộc lộ những điểm yếu của mình. Chi phí duy trì hoạt động của các máy phục vụ ngày càng tốn kém theo độ phức tạp và sự mở rộng của mạng. Không chỉ có vậy, hoạt động của mạng còn bị phụ thuộc chặt chẽ vào trạng thái của máy phục vụ: nếu máy phục vụ gặp sự cố thì toàn bộ hệ thống sẽ bị ảnh hƣởng. Chính bởi vậy mà mô hình mạng ngang hàng (Peer to Peer hay P2P) ngày càng thu hút sự quan tâm của đông đảo ngƣời dùng, các nhà nghiên cứu mạng và ngay cả của các công ty thƣơng mại lớn. Với ba đặc điểm nổi bật là tận dụng đƣợc tài nguyên của các máy tham gia, giải quyết đƣợc vấn đề điểm chết trung tâm của mô hình máy phục vụ/máy khách, và chi phí xây dựng vận hành thấp; mạng ngang hàng đã mở đƣờng cho rất nhiều nghiên cứu và ứng dụng trong mọi lĩnh vực. Mƣời năm qua đã đánh dấu những bƣớc phát triển lớn của dịch vụ mạng ngang hàng. Từ những hệ thống chia sẻ file đơn giản trong mạng cục bộ Napster (1999) hiện nay BittorenteDonkey, Bittorent… thƣờng cung cấp các file dữ liệu có kích thƣớc hàng trăm MB tới hàng ngàn ngƣời dùng; tới các hệ thống tìm kiếm nội dung, hội thảo qua mạng (video conference, VoIP), và đặc biệt là việc phân bổ các dữ liệu truyền thông đa phƣơng tiện từ một máy tính nguồn tới một lƣợng lớn ngƣời dùng. Một trong những vấn đề quan trọng nhất để nâng cao chất lƣợng dịch vụ của mạng ngang hàng là tốc độ và hiệu suất truyền tin trong mạng. Có nhiều nghiên cứu về vấn đề này, tuy nhiên trong phạm vi luận văn chúng tôi tập trung vào tầng mạng phủ (overlay network). Để đảm bảo tốc độ truyền tin, cũng nhƣ chất lƣợng dịch vụ thì tầng mạng phủ cần đáp ứng các yêu cầu sau: a. Có cấu trúc: đây là tiền đề cho việc phát triển, xây dựng các thuật toán tìm kiếm tài nguyên trong mạng. 1 b. Đáng tin tƣởng: Đảm bảo mạng vẫn hoạt động khi có nút tham gia hoặc rời khỏi mạng. c. Có khả năng mở rộng: Cho phép nhiều nút mạng tham gia mạng đồng thời. Có nhiều đề xuất để giải quyết các yêu cầu trên, trong đó mạng phủ theo mô hình thế giới nhỏ [2],[3],[4],[5] là một trong những giải pháp đƣợc nhiều ngƣời quan tâm. Các nghiên cứu về mạng thế giới nhỏ đƣa ra các tiêu chí về đánh giá hàng xóm gần hàng xóm xa. Theo các đánh giá [2],[3], hàng xóm gần là những hàng xóm có độ trễ truyền tin thấp. Cách đánh giá này mạng thế giới nhỏ đƣợc xây dựng sẽ có các nhóm nút mạng có tốc độ truyền tin cao liên kết trực tiếp với nhau, giúp tăng hiệu suất truyền tin chung của các nút trong mạng. Tuy nhiên vấn đề đặt ra với phƣơng pháp này là lƣợng thông tin cần thiết để xây dựng và duy trì mạng là lớn, điều đó ảnh hƣởng đến tính hiệu quả và khả năng mở rộng của mạng. Trong [6] có đề xuất các giải thuật xây dựng mạng ngang hàng, một trong những giải thuật đó là Gocast. Gocast có nhiều điểm tƣơng đồng với cách xây dựng mạng trong [2],[3] hơn nữa giải thuật Gocast còn khắc phục đƣợc một số điểm yếu cho việc xây dựng mạng thế giới nhỏ, nhƣ làm giảm lƣợng thông tin duy trì mạng, khống chế tốt hơn cân bằng bậc của tất các đỉnh trong đồ thị. Ngoài ra Gocast cũng là giải thuật đã đƣợc cài đặt sử dụng trong thực tế. Để khắc phục vấn đề về thông lƣợng yêu cầu duy trì mạng thế giới nhỏ, luận văn nghiên cứu giải thuật kết hợp giữa Gocast và thế giới nhỏ, để tận dụng tính cân bằng bậc ở các nút mạng của Gocast và các điểm mạnh của mô hình thế giới nhỏ. Giải pháp đã đƣợc thử nhiệm trên môi trƣờng mô phỏng iGridMedia với các tham số thời gian trễ gần giống Internet. Kết quả cho thấy, giải pháp đã đem lại hiệu quả với việc làm giảm thời gian trễ và chi phí truyền thông cho các gói tin điều khiển mạng. Theo đó, hiệu năng và độ trễ trung bình của mạng cũng đƣợc cải thiện. Quá trình nghiên cứu thực hiện và kết quả nghiên cứu đã đƣợc trình bày đầy đủ trong 5 chƣơng của luận văn với nội dung cụ thể sau: Chƣơng 1: Giới thiệu tổng quan về mạng ngang hàng, với các khái niệm cơ bản nhất, cách thức phân loại và các ứng dụng trên mạng ngang hàng, các phƣơng pháp truyền tin trên mạng ngang hàng. Chƣơng 1 cũng đồng thời giới thiệu về iGridMedia trình giả lập đƣợc chọn để đánh giá chất lƣợng của mạng thế giới nhỏ. 2 Chƣơng 2: Giới thiệu tổng quan về dịch vụ truyền hình ngang hàng, các yêu cầu với truyền hình ngang hàng. Giới thiệu chi tiết về các lớp mạng phủ đi sâu vào mạng thế giới nhỏ. Chƣơng 3: Các giải thuật xây dựng mạng thế giới nhỏ. Trình bầy giải thuật cải tiến, kết hợp mạng thế giới nhỏ với giải thuật Gocast nhằm khắc phục điểm yếu về yêu cầu lƣợng thông tin lớn để duy trì mạng thế giới nhỏ theo phƣơng thức truyền thống. Chƣơng 4: Trình bày cách thức thực hiện mô phỏng và sử dụng các kết quả mô phỏng thu đƣợc để so sánh đánh giá tính hiệu quả của giải thuật kết hợp so với giải thuật gốc. Chƣơng 5: Kết luận và các phƣơng hƣớng nghiên cứu trong tƣơng lai. 3 Chƣơng 1. TỔNG QUAN 1.1. Khái niệm mạng ngang hàng Trong quá trình phát triển của mạng máy tính chúng ta đã đƣợc chứng kiến sự phát triển vƣợt bậc của các mô hình mạng, ban đầu chỉ là 2 máy tính kết nối với nhau một cách thuần túy, sau đó là mạng LAN với kết nối vài chục máy tính trong một phạm vi nhỏ. Không chỉ dừng lại ở đó, mô hình mạng ngày càng đƣợc mở rộng cả về tính chất và quy mô thành mạng WAN với hàng nghìn máy tính kết nối với nhau trong một phạm vi lớn hơn. Và cuối cùng là sự ra đời của mạng Internet - vốn đƣợc xem nhƣ là một sự phát triển vĩ đại của ngành công nghệ thông tin nói riêng và của toàn thế giới nói chung. Internet là kho tài nguyên khổng lồ của loài ngƣời với rất nhiều ứng dụng chia sẻ thông tin, mang con ngƣời trên toàn thế giới xích lại gần nhau hơn. Hiện nay hầu hết các ứng dụng trên mạng Internet đều đƣợc xây dựng theo mô hình Client/Server với các tính năng ƣu việt của nó nhƣ: các máy Client không cần cấu hình mạnh, tiết kiệm đƣợc địa chỉ IP do có thể cấp phát đƣợc địa chỉ IP động, việc bảo trì các phần mềm phục vụ trên Server là tập trung nên rất dễ dàng. Tuy nhiên đổi lại trong các mô hình mạng Client/Server, chi phí đầu tƣ cho các server đó rất lớn. Hệ thống ngày càng lớn thì việc mở rộng đòi hỏi chi phí ngày càng cao cho việc nâng cấp server hoặc thậm chí là phải bổ sung thêm server mới. Mặt khác, nếu các máy server gặp sự cố thì toàn bộ hệ thống sẽ bị ảnh hƣởng thậm chí ngừng hoạt động ngay lập tức. Ngoài ra mô hình Client/Server cũng không tận dụng đƣợc sức mạnh của các máy client. Chính bởi vậy, để khắc phục các nhƣợc điểm của mô hình Client/Server, cấu trúc mạng ngang hàng (Peer-To-Peer) ra đời, đang ngày càng đƣợc quan tâm và phát triển rộng rãi hơn trong thời gian gần đây. Mạng ngang hàng (Peer-To-Peer network), còn gọi là mạng đồng đẳng, là cấu trúc 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 trung vào một số nhỏ các server trung tâm nhƣ các mạng thông thƣờng. Mạng ngang hàng hiện có rất nhiều ứng dụng. Ứng dụng thƣờng xuyên gặp nhất là chia sẻ tệp tin, tất cả các dạng dữ liệu nhƣ văn bản, âm thanh, hình ảnh... hoặc để truyền dữ liệu thời gian thực nhƣ điện thoại VoIP, chia sẻ video thời gian trực, truyền hình trực tuyến… 4 Một mạng ngang hàng đúng nghĩa không có khái niệm server và client, nói cách khác, tất cả các máy tham gia đều bình đẳng và đƣợc gọi là peer, có nghĩa là mỗi nút mạng vừa đóng vai trò là client , vừa đóng vai trò là server đối với các máy khác trong mạng. 1.2. Phân loại mạng ngang hàng Theo mức độ tập trung của mạng ngang hàng, chúng ta có thể phân loại các mạng ngang hàng nhƣ sau. 1.2.1. Hệ thống ngang hàng lai ghép Hình 1. Mạng ngang hàng lai ghép Đây là mạng ngang hàng thế hệ thứ nhất. Các mạng kiểu này đƣợc gọi là mạng ngang hàng lai ghép vì trong mạng vẫn có một hay một số máy chủ trung tâm dùng để lƣu trữ thông tin của các máy trạm thành viên và trả lời các truy vấn. Tuy nhiên, tài nguyên phân phối của mạng không nằm trên máy chủ đó mà nằm trên chính các máy trạm thành viên. Máy chủ trung tâm chỉ có vai trò lƣu trữ thông tin về các máy trạm thành viên và các thông tin tài nguyên đƣợc chia sẻ để có thể sẵn sàng cung cấp các thông tin liên quan mỗi khi có một máy trạm gửi yêu cầu tìm kiếm tới. Các mạng ngang hàng lai ghép này có thể sử dụng các trạm định tuyến để xác định địa chỉ IP của các máy trạm. 5 Nguyên tắc hoạt động:  Mỗi client lƣu trữ files định chia sẻ với các nút khác trong mạng.  Một bảng lƣu trữ thông tin kết nối của ngƣời dùng đăng kí (IP address, connection bandwidth…).  Một bảng liệt kê danh sách các files mà mỗi ngƣời dùng định chia sẻ (tên file, dung lƣợng, thời gian tạo file…).  Mọi máy tính tham gia mạng đƣợc kết nối với máy chủ tìm kiếm trung tâm, các yêu cầu tìm kiếm đƣợc gửi tới máy chủ trung tâm phân tích, nếu yêu cầu đƣợc giải quyết, máy chủ sẽ gửi trả lại địa chỉ IP của máy chứa tài nguyên trong mạng và quá trình truyền file đƣợc thực hiện theo đúng cơ chế của mạng ngang hàng, giữa các host với nhau mà không cần quan máy chủ trung tâm. Ƣu điểm:  Dễ xây dựng.  Tìm kiếm file nhanh và hiệu quả. Nhƣợc điểm:  Dễ bị tấn công.  Cần quản trị (central server). Các đại diện cho mạng ngang hàng lai ghép đƣợc biết đến nhiều nhất là Napster và BitTorrent. Napster là mạng ngang hàng đặc trƣng cho hệ thống mạng ngang hàng lai ghép, chúng đƣợc dùng cho việc chia sẻ các file giữa các ngƣời dùng Internet. Mạng này đã đƣợc sử dụng rộng rãi. Tuy nhiên, Do các yếu tố về luật pháp, Napster đã nhanh chóng bị mất thị trƣờng. Napster có một server trung tâm hoạt động nhƣ một index server lƣu trữ các thông tin về các file nhạc có sẵn trên các máy trạm tham gia mạng. Khi một ngƣời dùng tiến hành tìm kiếm một file nhạc, hệ thống yêu cầu server trung tâm tìm kiếm và trả về một danh sách các máy trạm có các tài nguyên tƣơng ứng. Sau khi nhận đƣợc danh sách này, ngƣời dùng tạo một kết nối trực tiếp với các máy trạm đó và tải 6 về những file mình muốn. Các khái niệm và kiến trúc của Napster vẫn còn đƣợc sử dụng trong các ứng dụng khác nhƣ: Audiogalaxy, WinMX. Với Napster, việc tìm kiếm file bị thất bại khi bảng tìm kiếm trên máy chủ vì lý do nào đó không thực hiện đƣợc. Chỉ có các file truy vấn và việc lƣu trữ đƣợc phân tán, vì vậy máy chủ đóng vai trò là một nút cổ chai. Khả năng tính toán và lƣu trữ của máy chủ tìm kiếm phải tƣơng xứng với số nút mạng trong hệ thống, do đó khả năng mở rộng mạng bị hạn chế rất nhiều. BitTorrent cũng là một mạng ngang hàng lai ghép nổi tiếng khác trong việc chia sẻ nội dung. BitTorrent cho phép một lƣợng lớn ngƣời dùng download nhanh các file có dung lƣợng lớn. Giao thức BitTorrent gồm có một số thực thể nhƣ: tracker, peers, và seeds (hạt giống). Mỗi một thực thể có vai trò khác nhau trong việc phục vụ mục tiêu chia sẻ tài nguyên của mạng. Tracker hoạt động nhƣ một server trung tâm và các máy trạm kết nối vào tracker này để download file. Tracker theo dõi các máy trạm và hƣớng dẫn các máy trạm này kết nối vào các máy trạm khác. Các máy trạm là thành viên tham gia vào mạng với mục đích download và upload các phần của file. Seeds cũng là thành viên tham gia vào mạng và là những nút đã download thành công nội dung mình cần và hiện chỉ tham gia với vai trò upload. Đối với các file lớn, việc yêu cầu các seed vẫn còn online cho đến khi tất cả các máy trạm khác hoàn tất việc download tất cả file là một yêu cầu rất quan trọng. Giao thức này có ý định giải quyết các vấn đề về mở rộng – là vấn đề thách thức nhất cho các mạng chia sẻ nội dung. Giao thức đảm bảo sự công bằng trong mạng ngang hàng khi chia cắt các file có dung lƣợng lớn thành từng mảnh nhỏ có dung lƣợng bằng nhau. Ƣu điểm của BitTorrent là cung cấp một kỹ thuật chia sẻ file có dung lớn một cách hiệu quả và linh động. Một nhƣợc điểm của giao thức BitTorrent là nếu một máy trạm đang download một file lớn mà không còn seed nào đang online thì những mảnh nhỏ đã đƣợc download về không bao giờ còn cơ hội đƣợc sử dụng nữa. 1.2.2. Mạng ngang hàng thuần túy (Pure Peer-to-peer System) Khác với mạng ngang hàng lai ghép, mạng ngang hàng thuần túy là một mạng ngang hàng đúng nghĩa, 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 tham gia mạng có vai trò vừa là máy chủ vừa là máy khách và có khả năng định tuyến độc lập. 7 Hình 2. Mạng ngang hàng thuần túy 1.2.2.1. Khái niệm về lớp mạng phủ Lớp mạng phủ (Overlay network) là mạng đƣợc xây dựng bên trên một hoặc nhiều mạng vật lý đang tồn tại, bao gồm tất cả các nút mạng đại diện cho các máy tham gia và các liên kết giữa các nút mạng này. Một liên kết tồn tại giữa hai nút mạng khi một nút mạng này biết vị trí của nút mạng kia. Dựa vào cấu trúc liên kết giữa các nút mạng trong mạng ta có thể phân loại mạng ngang hàng thuần túy thành 2 loại: có cấu trúc hay không cấu trúc. 1.2.2.2. Mạng ngang hàng thuần túy không có cấu trúc Mạng ngang hàng đƣợc xem là thuần túy không có cấu trúc khi các liên kết giữa các nút mạng trong mạng đƣợc thiết lập một cách ngẫu nhiên, không theo qui luật nào. Mạng ngang hàng thuần túy không có cấu trúc dễ dàng đƣợc xây dựng: một máy mới khi muốn tham gia mạng có thể lấy luôn các liên kết có sẵn của một máy khác đang ở trong mạng và sau đó dần dần bổ sung thêm các liên kết mới của riêng mình mà không cần bất cứ một thủ tục nào khác. Khi một máy muốn tìm một dữ liệu trong mạng ngang hàng không cấu trúc, yêu cầu tìm kiếm sẽ đƣợc truyền trên cả mạng để tìm ra càng nhiều máy chia sẻ càng tốt. Nhƣợc điểm có thể thấy ngay của hệ thống này là không có gì đảm bảo việc tìm kiếm sẽ thành công. Đối với việc tìm kiếm các dữ liệu 8 phổ biến đƣợc chia sẻ trên nhiều máy, tỉ lệ thành công là khá cao, ngƣợc lại, nếu dữ liệu chỉ đƣợc chia sẻ trên một vài máy thì xác suất tìm thấy là khá nhỏ. Tính chất này là hiển nhiên vì trong mạng ngang hàng không cấu trúc, không có bất kì mối tƣơng quan nào giữa các máy tính và dữ liệu mà mỗi máy tính quản lý trong mạng. Do đó, yêu cầu tìm kiếm cần đƣợc chuyển một cách ngẫu nhiên đến một số máy trong mạng. Một nhƣợc điểm khác của hệ thống này là do không có định hƣớng, một yêu cầu tìm kiếm thƣờng đƣợc chuyển cho một số lƣợng lớn máy trong mạng làm tiêu tốn một lƣợng lớn băng thông của mạng, dẫn đến hiệu quả tìm kiếm chung của mạng thấp. Các mạng ngang hàng không có cấu trúc nổi tiếng nhƣ là Gnutella, KazaA, Morpheus, DirrectConnect,… 1.2.2.3. Mạng ngang hàng có cấu trúc Để khắc phục nhƣợc điểm của mạng không cấu trúc, mạng ngang hàng có cấu trúc đƣợc xây dựng bằng cách sử dụng hệ thống DHT (Distributed Hash Table - Bảng Băm Phân Tán). Hệ thống này định nghĩa liên kết giữa các nút mạng trong mạng phủ theo một thuật toán cụ thể, đồng thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với một phần dữ liệu chia sẻ trong mạng. Với cấu trúc này, khi một máy cần tìm một dữ liệu, nó chỉ cần áp dụng một giao thức chung để xác định nút mạng nào chịu trách nhiệm cho dữ liệu đó và sau đó liên lạc trực tiếp đến nút mạng đó để lấy kết quả. Nguyên tắc hoạt động:  Topo mạng đƣợc kiểm soát chặt chẽ.  Files (hoặc con trỏ trỏ tới files) đƣợc đặt ở một vị trí xác định.  Điều quan trọng đối với những hệ thống có cấu trúc là cung cấp sự liên kết (mapping) giữa nội dung (ví dụ: id của file) và vị trí nút (ví dụ: địa chỉ nút). Việc này thƣờng dựa trên một cấu trúc dữ liệu bảng băm phân tán (Distributed Hash Table). 9 Hình 3. Cơ chế bảng băm phân tán (DHT) Dựa trên cấu trúc bảng băm phân tán đã có nhiều nghiên cứu và đề xuất ra các mô hình mạng ngang hàng có cấu trúc, điển hình là cấu trúc dạng vòng (nhƣ trong hình vẽ mô tả): Chord, Pastry…, và cấu trúc không gian đa chiều: CAN, Viceroy. Ƣu điểm:  Khả năng mở rộng đƣợc nâng cao rõ rệt do không có điểm tập trung gây ra hiện tƣợng thắt nút cổ chai tại những điểm này.  Các truy vấn tìm kiếm đƣợc phát đi theo một thuật toán cụ thể, hạn chế tối đa lƣợng truy vấn hay kỹ thuật flooding, tiết kiệm băng thông mạng. Nhƣợc điểm:  Việc quản lí cấu trúc của topo mạng gặp khó khăn, đặc biệt trong trong trƣờng hợp tỷ lệ vào/ra mạng của các nút cao.  Vấn đề cân bằng tải trong mạng.  Sự khác biệt về topology trên mạng overlay và mạng liên kết vật lý dẫn đến thời gian trễ truy vấn trung bình cao. 1.3. Phƣơng pháp truyền thông mạng ngang hàng Trong mô hình ngang hàng, sự truyền phát thông tin có thể đƣợc chia làm ba dạng thức chính: 10 1.3.1. Đẩy (Push) Các mảnh dữ liệu đƣợc chuyển xuống từ một máy trạm (máy cha) xuống máy trạm khác (máy con) mà không cần thông báo trƣớc với máy con về gói dữ liệu sẽ đƣợc chuyển tới. Chính vì vậy, trong các mạng không có cấu trúc hoặc có nhiều máy cha, nhiều mảnh dữ liệu có thể đƣợc chuyển tới một máy trạm tại cùng một thời điểm trong khi có những mảnh dữ liệu không bao giờ đƣợc chuyển tới máy con do thất lạc trên đƣờng truyền. Phƣơng thức đẩy thƣờng đƣợc kết hợp trong các mạng có cấu trúc hình cây. Trong trƣờng hợp các máy tính trong mạng có mối quan hệ hàng xóm chặt chẽ và lâu dài thì phƣơng thức này đƣợc sử dụng rất hiệu quả. 1.3.2. Kéo (Pull) Ngƣợc lại với phƣơng thức đẩy, trong phƣơng thức kéo, các máy con đóng vai trò chủ động yêu cầu dữ liệu từ máy cha mà không cần biết máy cha có chứa dữ liệu hay không. Việc trùng lặp dữ liệu ở đây không phải là vấn đề lớn, mà vấn đề chủ yếu là khả năng khan hiếm dữ liệu khi một máy con không thể nào tìm thấy bất kỳ máy cha nào có chứa dữ liệu. Phƣơng thức này thƣờng đƣợc sử dụng trong các hệ thống swarming không có cấu trúc, nơi mà một máy tính có thể có nhiều máy cha. Tuy nhiên trong thực tế, các hệ thống đều cho phép các máy tính trao đổi các thông tin với nhau về các khối dữ liệu nó có. Do đó, một mạng kéo thuần túy thƣờng đƣợc sử dụng nhƣ một mô hình tham chiếu. 1.3.3. Kéo đẩy xen kẽ Giao thức kéo đẩy xen kẽ cũng là một trong số các giao thức đƣợc đề xuất nhằm cải tiến phƣơng pháp kéo đẩy thuần túy ban đầu. Tuy nhiên khác với các phƣơng pháp đƣợc đề cập tới trong các bài báo [1] phƣơng pháp kéo đẩy xen kẽ- nhƣ tên gọi của nó - kết hợp hai phƣơng thức kéo và đẩy xen kẽ với nhau một cách thông minh, thông qua một chính sách lựa chọn các máy trạm khéo léo mà không cần phải duy trì việc trao đổi thông tin về trạng thái download các mảnh dữ liệu giữa các máy tính với nhau. Để đơn giản, chúng ta sẽ xem xét một hệ thống chỉ có một nguồn phát dữ liệu, trong đó nội dung đƣợc phân tách thành các mảnh nhỏ gọi là chunk (hay piece) và đƣợc trao đổi giữa các máy tính trong mạng một cách độc lập. Các mảnh dữ liệu đƣợc tạo ra với một tốc độ không đổi rstr , tốc độ này có thể là chính tốc độ truyền phát dữ 11 liệu hoặc đơn giản hơn là tốc độ dịch vụ cho việc truyền file. Mỗi mảnh dữ liệu đều có một số tuần tự kèm theo, phản ánh vị trí của mảnh dữ liệu đó trong dữ liệu gốc. Mỗi máy tính trong mạng sẽ thực hiện luân phiên phƣơng thức kéo đẩy và có một tập hữu hạn các máy hàng xóm đƣợc chỉ ra trong danh sách hàng xóm lƣu trữ tại chính máy tính đó. Danh sách đó đƣợc gọi là contact list. Giả thiết kích thƣớc của danh sách đó là k; khi đó máy trạm P trong mạng chỉ có thể liên lạc với k máy trong danh sách hàng xóm của nó. Tuy nhiên P hoàn toàn có thể đƣợc gọi tới từ một máy trạm khác không nằm trong danh sách hàng xóm của P. Trong chế độ đẩy, máy trạm P sẽ lựa chọn hàng xóm một cách ngẫu nhiên và đẩy một mảnh dữ liệu tới hàng xóm đó. Nếu máy hàng xóm chƣa có mảnh dữ liệu đó và còn trống băng thông cho việc download, P sẽ đẩy mảnh dữ liệu đó sang bên máy hàng xóm. Nếu máy hàng xóm đã chứa mảnh dữ liệu đó hoặc không còn băng thông trống để download dữ liệu thì việc đẩy sẽ bị hủy bỏ. Trong chế độ kéo, máy trạm P cũng sẽ lựa chọn ngẫu nhiên một máy hàng xóm và gửi yêu cầu dữ liệu cần lấy tới máy đó. Nếu máy hàng xóm đang có chứa mảnh dữ liệu đƣợc yêu cầu đó và hiện tại nó đang không upload dữ liệu nào tới các máy tính khác, nó sẽ chấp nhận yêu cầu kéo dữ liệu từ P, ngƣợc lại, nó sẽ từ chối yêu cầu. Cơ chế lựa chọn mảnh dữ liệu để đẩy đi hoặc kéo về, nhƣ đã nói ở trên, luôn là một yêu cầu quan trọng nhất của thiết kế, đặc biệt trong các hệ thống truyền thông đa phƣơng tiện, khi mà các gói dữ liệu bị giới hạn bởi độ trễ tối đa. Một thuật toán lựa chọn có thể làm việc tốt với hệ thống chia sẻ file nhƣng chƣa chắc đã đúng đối với một hệ thống truyền thông đa phƣơng tiện thời gian thực. Do đó, một thủ tục lựa chọn thông minh: chẳng hạn nhƣ “hiếm nhất trƣớc” (tƣơng tự Bittorrent) có thể đƣợc sử dụng, thay vì phải lƣu trữ việc thay đổi trạng thái giữa các máy tính trong mạng:  Trong chế độ đẩy, máy trạm P sẽ đẩy đi mảnh dữ liệu có số tuần tự cao nhất giữa các mảnh dữ liệu mà P nhận đƣợc trong số các dữ liệu đƣợc đẩy tới từ các hàng xóm của P.  Trong chế độ kéo, ngƣợc lại, P sẽ yêu cầu mảnh dữ liệu có số tuần tự thấp nhất mà máy hàng xóm đang giữ. Mục đích ở đây là có thể lấp đầy các chỗ trống của các mảnh dữ liệu theo số tuần tự. 12 1.3.4. Phƣơng pháp truyền thông lan tỏa (gossip protocol) Phƣơng pháp truyền thông lan tỏa hay còn gọi là phƣơng pháp truyền thông dựa theo tin đồn là một loại giao thức truyền thông đƣợc sử dụng chủ yếu trong các hệ thống quy mô lớn. Nguyên tắc của giao thức này dựa trên nguyên tắc lan truyền các tin đồn phổ biến trong xã hội. Giao thức truyền thông lan tỏa đang ngày càng trở nên phổ biến trong các ứng dụng trên các mạng ngang hàng do khả năng mở rộng, đơn giản, độ tin cậy cao và khả năng thay đổi giữa các môi trƣờng. Giao thức truyền thông lan tỏa liên quan đến việc trao đổi thông tin định kỳ giữa các cặp nút, và cuối cùng kết quả trong thông tin đƣợc lan truyền khắp hệ thống, tƣơng tự nhƣ cách thức truyền các tin đồn trong một cộng đồng. Nó đôi khi đƣợc gọi nhƣ các giao thức lây truyền dịch bệnh vì sự lan truyền thông tin tƣơng tự nhƣ sự lây lan của virus. Nguyên tắc hoạt động cụ thể của một giao thức truyền thông lan tỏa nhƣ sau:  Mỗi nút có một số dữ liệu của bản thân nó và định kỳ, thông báo những tin đồn rằng nó có dữ liệu đó với một nút khác  Một nút A chọn ngẫu nhiên một nút B từ một danh sách các nút hàng xóm.  A gửi một thông điệp tới B để B nhận các dữ liệu từ A  B gửi lại một phản hồi về việc đồng ý tiếp nhận dữ liệu đó  A và B cập nhật bộ dữ liệu của mình bằng cách kết hợp nó với các dữ liệu nhận đƣợc. Nếu chúng ta bắt đầu với một nút duy nhất có một mục dữ liệu cụ thể, nó sẽ thông báo tin đồn với một nút khác. Sau đó, theo định kỳ, dữ liệu ở mỗi nút sẽ đƣợc tăng gấp đôi và dữ liệu đƣợc phân phối trên toàn hệ thống khá nhanh chóng. Ƣu điểm:  Giao thức đơn giản, thực hiện dễ dàng.  Khả năng mở rộng là một ƣu điểm rất lớn của giao thức truyền thông lan tỏa. Khi mỗi nút chỉ biết về một số giới hạn các nút khác và tại một thời điểm, mỗi nút giao tiếp chỉ với một nút lựa chọn ngẫu nhiên với một số cố định của tin 13 nhắn, giao thức này có hiệu suất ổn định ngay cả khi hệ thống vẫn tiếp tục phát triển về kích thƣớc.  Giao thức truyền thông lan tỏa cũng xử lý rất tốt với việc thay đổi các nút trong mạng. Khi các nút tham gia và rời khỏi mạng mà không thông báo trƣớc, mạng vẫn đảm bảo hoạt động liên tục do giao thức truyền thông lan tỏa thực hiện trao đổi thông tin ngẫu nhiên và định kỳ. Vấn đề mất các thông điệp cũng không phải là vấn đề lớn do cùng một dữ liệu sẽ đƣợc nhận đƣợc từ nhiều nút. Trong giao thức truyền thông lan tỏa, các nút không đƣợc giao vai trò cụ thể. Vì vậy, một nút gặp sự cố sẽ không ngăn chặn các nút khác tiếp tục gửi tin nhắn và do đó sẽ không gặp vấn đề về sự cố phụ thuộc vào một điểm duy nhất và không có nhu cầu để thực thi các hành động phát hiện phục hồi sự cố. Nhƣợc điểm:  Một nhƣợc điểm của giao thức truyền thông lan tỏa là sự dƣ thừa dữ liệu, do dữ liệu bị lặp lại giữa các nút lân cận.  Một vấn đề khác là độ trễ cao trong việc truyền tin. Trao đổi thông tin đƣợc thực hiện định kỳ. Ngoài ra, các nút có thể chọn các nút khác mà nó có thể đã giao tiếp và nó sẽ mất một thời gian dài cho thông tin để đạt đến đích mong muốn vì nó phải đi vòng qua các nút khác. Vì vậy, dữ liệu đƣợc truyền tƣơng đối chậm và không thích hợp cho các hệ thống thời gian thực, vốn đòi hỏi tốc độ là mục tiêu hàng đầu. 1.4. Giới thiệu về trình giả lập iGridMedia 1.4.1. Giới thiệu chung iGridMedia Dự án GridMedia đã đƣợc lập ra từ 03/2004 nhằm cung cấp nội dung truyền hình chất lƣợng cao tới hàng triệu ngƣời dùng trên toàn cầu qua mạng Internet. GridMedia đã đƣợc CCTV (đài truyền hình lớn nhất ở Trung Quốc) sử dụng để phát sóng tới 500.000 ngƣời ngƣời dùng cuối. Số ngƣời sử dụng đồng thời lên đến 224.000, tƣơng đƣơng với máy chủ có băng thông 200Mbps. GridMedia đang đƣợc sử dụng bởi các ứng dụng chia sẻ video ngang hàng nổi tiếng thế giới cung cấp bởi: PPLive, QQLive, Zattoo… 14 Phần lõi của hệ thống đƣợc phát triển bởi tiến sĩ Meng Zhang, Đại học Tsinghua, Bắc Kinh, Trung Quốc. iGridMedia là dự án mở rộng của GridMedia nhằm hỗ trợ cho các ứng dụng tƣơng tác đạt hiệu suất tốt hơn trong nhóm có quy mô lớn, và nhóm có quy mô nhỏ. iGridMedia cũng có khả năng mở rộng và phù hợp với số lƣợng rất lớn ngƣời sử dụng quy mô trong một kênh. Bên cạnh đó, iGridMedia cân bằng giữa độ trễ, chất lƣợng và chi phí băng thông máy cung cấp kênh truyền hình. Dự án bao gồm module cho phép mô phỏng ứng dụng truyền đa phƣơng tiện trên diện rộng. Bằng cách mô phỏng, chúng ta có thể dựng các cấu hình thử nghiệm và đánh giá và phân tích các tiêu chí của mạng theo các phƣơng pháp khác nhau. 1.4.2. Mô hình hoạt động Trong trƣờng hợp ứng dụng truyền hình quảng bá trực tiếp qua Internet nhƣ trong hình, khi ngƣời chia sẻ muốn chia sẻ video, họ thƣờng sử dụng DSL để truy cập Internet, do đó băng thông upload thấp. Để tận dụng đầy đủ băng thông upload, ngƣời chia sẻ cần sẽ tải lên luồng video của họ lên máy chủ chuyên dụng và nội dung trực tiếp sẽ đƣợc truyền tải từ máy chủ chuyên dụng đó tới ngƣời xem đầu cuối. Nhƣ trong hình dƣới ngƣời xem đầu cuối sẽ duy trì một kết nối “cứu hộ” tới máy phục vụ chuyên dụng. Khi gói tin chia sẻ không đến đƣợc đúng hạn, ứng dụng phát audio/video sẽ tải nó qua đƣờng “cứu hộ”. Hình 4. Ứng dụng truyền dữ liệu đa phương tiện trên iGridMedia 15 Khi hệ thống hoạt động, máy phục vụ sẽ cung cấp các gói dữ liệu trực tuyến tới một số nút trong mạng. Sau đó, những nút mạng này sẽ tiếp tục chia sẻ dữ liệu đến những nút khác trong mạng. Quá trình chia sẻ đƣợc lặp lại cho đến khi dữ liệu đƣợc truyền tải đến tất cả các nút. Giao thức chia sẻ dữ liệu trong hệ thống iGridMedia là kéo đẩy xen kẽ trên một mạng lƣới chồng phủ theo cấu trúc ngẫu nhiên. Việc xây dựng lớp mạng phủ đƣợc hỗ trợ bởi một điểm đƣợc gọi là điểm hẹn (RP), thực chất là một máy chủ duy trì kết nối tới các máy đang “online” trên các kênh khác nhau của mạng ngang hàng. Một địa chỉ liên lạc nút tham gia đầu tiên RP để có đƣợc một danh sách các nút hiện đang tham gia vào lớp xếp chồng. Sau khi nhận đƣợc danh sách các nút bên trong hệ thống, các nút tham gia sẽ ngẫu nhiên chọn ngƣời hàng xóm mới của mình, nó sẽ gửi tin nhắn đến những ngƣời hàng xóm để thông báo cho họ kết nối mới. Nếu kết nối với một nút đƣợc kết thúc hoặc thất bại, hàng xóm mới sẽ đƣợc lấy từ bảng thành viên cung cấp bởi server. Vì vậy, một mạng lƣới lớp xếp chồng phi cấu trúc đƣợc xây dựng. 1.4.3. Kiến trúc chung của trình mô phỏng 1.4.3.1. Cách thức hoạt động Hình 5. Cách thức hoạt động của trình mô phỏng iGridMedia 16 Trình mô phỏng bao gồm ba thành phần chính, thành phần tạo topo mạng, thành phần tạo kế hoạch mô phỏng và engine thực hiện các event mô phỏng. Khi bắt đầu quá trình mô phỏng, chƣơng trình mô phỏng sẽ xây dựng mạng theo topo đƣợc định nghĩa trong các file input đầu vào. Tiếp đó, trình mô phỏng xây dựng danh sách các sự kiện cho các nút mạng và cuối cùng thì engine sự kiện sẽ thực hiện các hành động diễn ra theo kịch bản mô phỏng. Đồng thời, trình mô phỏng cũng ghi nhận các tham số mạng đo đƣợc. 1.4.3.2. Kiến trúc lớp mạng phủ Sau khi các nút tham gia vào mạng, các nút mạng sẽ tự động tìm kiếm các hàng xóm một cách ngẫu nhiên cho đến khi có đủ số lƣợng hàng xóm theo định nghĩa số hàng xóm trong file cấu hình. Quá trình tìm hàng xóm đƣợc lặp lại định kỳ giúp các nút mạng liên tục cập nhật danh sách hàng xóm của mình. Việc loại bỏ cạnh cũ, và tạo cạnh mới cũng đƣợc thực hiện theo cơ chế hoàn toàn ngẫu nhiên. Hình 6. Xây dựng lớp mạng phủ trong iGridMedia Với cách xây dựng hàng xóm trên, lớp mạng phủ trên iGridMedia là lớp mạng phủ ngẫu nhiên. 17
- Xem thêm -