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 -
.PDF 
63 
93 
61 
