5.2. Hướng phát triển tiếp theo của đề tài 42
Tài liệu tham khảo 44
Phụ lục A 45
Danh mục hình ảnh
Hình 1. Mô hình mạng ngang hàng 3
Hình 2. Mô hình mạng khách chủ 4
Hình 3. Mạng ngang hàng lai thế hệ thứ nhất (Napster) 7
Hình 4. Mạng ngang hàng thuần túy (Gnutella 0.4, FreeNet) 8
Hình 5. Kiến trúc siêu ngang hàng(Gnutella 0.6, JXTA) 9
Hình 6. Cơ chế của bảng băm phân tán (DHT) 11
Hình 7. Mạng ngang hàng có cấu trúc Chord dạng vòng tròn 11
Hình 8. Một mạng Chord với 3 nút 13
Hình 9. Lưu giữ key trong mạng Chord 14
Hình 10. Bản đồ miền trong không gian hai chiều 18
Hình 11. Tính toán với các điểm mốc 21
Hình 12. Tính toán với nút thông thường 21
Hình 13. Biểu đồ không gian Cantor với C=8 22
Hình 14: Bảng định tuyến giả định của N51 trong Quasi-Chord 23
Hình 15: Lựa chọn vị trí tham gia mạng 26
Hình 16: Mô hình mạng thực tế 28
Hình 17: Mô hình mạng mô phỏng 30
Hình 18: Biểu đồ thời gian trễ trung bình của Chord truyền thống và cải tiến 37
Hình 19: Biểu đồ thời gian trễ trung bình biến đổi theo CHOICE 38
Hình 20: Biểu đồ thời gian trễ trung bình theo EXPANSION 39
Hình 21: Biểu đồ thời gian trễ trung bình thay đổi theo lượng miền 40
Hình 22: Biểu đồ thời gian trễ trung bình thay đổi theo lượng nút tối đa 40
Mở đầu
Trong những năm gần đây, công nghệ ngang hàng (peer-to-peer - P2P) hay mạng
ngang hàng đã trở nên phổ biến trong các nghiên cứu về lĩnh vực Internet. So với các
mô hình mạng khác, mạng ngang hàng có nhiều ưu điểm như khả năng mở rộng, không
tồn tại điểm chết, khả năng của hệ thống tỉ lệ với số lượng máy tham gia, Tất cả những
đặc điểm trên đã tạo lên công nghệ P2P và các ứng dụng ngang hàng liên quan. Nhiều
ứng dụng lớn đã và đang được xây dựng trên mạng ngang hàng như FreeNet, Napster,
Gnutella, BitTorrent, eMule
Mạng ngang hàng có cấu trúc sử dụng giải thuật DHT (Distributed Hash Table –
bảng băm phân tán) tạo nên một mạng phủ (overlay) trên mạng liên kết vật lý. Giải
thuật này định nghĩa liên kết giữa các nút mạng trong mạng phủ theo một cấu trúc 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. Mỗi nút đều được kết nối với một tập các nút khác gọi là tập
nút láng giềng. Chord là một giao thức của mạng ngang hàng có cấu trúc với không gian
địa chỉ một chiều dạng vòng. Mạng ngang hàng cấu trúc Chord ngày càng thể hiện
nhiều ưu điểm như khả năng mở rộng, cân bằng tải, định tuyến, Giống như những
giao thức trên mạng có cấu trúc khác, mỗi nút trong Chord xây dựng một bảng định
tuyến giúp cho việc tìm kiếm thông tin giảm từ O(N) với N là số lượng tối đa nút trong
mạng, xuống còn O(log
2
N).
Trong mạng ngang hàng có cấu trúc nói chung và Chord nói riêng, quan hệ hàng
xóm của các nút được thiết lập mà không xem xét đến topo (topology) tầng dưới. Đó
chính là nguyên nhân gây ra sự sai khác giữa topo của mạng DHT và topo mạng liên kết
vật lý (topology mismatch). Điều này làm cho độ trễ truyền thông báo giữa các nút và
chi phí truyền thông trong mạng P2P. Yêu cầu đặt ra là làm sao để tối ưu mạng phủ,
khắc phục sự khác biệt đó.
Ngoài ra, khi xây dựng bảng định tuyến trong cấu trúc Chord, liên kết tại hàng thứ
i được chọn cố định là nút quản lý định danh k+2
i
. Như vậy, quá trình xây dựng liên kết
trong bảng định tuyến cũng không xem xét đến quan hệ giữa các nút ở tầng dưới. Nếu
như liên kết này có thời gian trễ lớn thì tất cả những truy vấn đi qua nó đều bị ảnh
hưởng bởi độ trễ này. Quá trình chuyển tiếp truy vấn là đưa truy vấn đến vị trí mà khóa
cần tìm kiếm thuộc lân cận của vị trí đó. Vì thế, phương pháp hiện có để xây dựng các
liên kết trong bảng định tuyến là chưa tốt.
1
Khóa luận này sẽ đề xuất một phương pháp mới để giải quyết hai vấn đề nêu trên
xảy ra với mạng ngang hàng có cấu trúc nói chung và cấu trúc Chord nói riêng. Vẫn dựa
trên cấu trúc và định tuyến của Chord truyền thống, trong đề xuất mà khóa luận đưa ra,
thứ nhất, các nút tham gia vào mạng sẽ lựa chọn vị trí theo tiêu chí mà tại đó, nút được
chọn có thời gian trễ tới các nút liền trước và liền sau là nhỏ nhất; thứ hai, bảng định
tuyến của nút sẽ được thay đổi bằng cách lựa chọn lại các nút đích của các liên kết từ
một tập nút nào đó cũng theo tiêu chí thời gian trễ nhỏ nhất, nhằm tiết kiệm chi phí
đường đi của các thông báo. Hai đề xuất sẽ giải quyết lần lượt vấn đề khác biệt về topo
và xây dựng liên kết trong bảng định tuyến dựa vào thời gian trễ.
Để đánh giá hiệu quả của giải pháp đề xuất, khóa luận xây dựng một chương trình
mô phỏng giả lập mạng Internet và đo thời gian trễ truyền thông báo giữa các nút trong
mạng Chord. Các kết quả thử nghiệm chứng minh cho khả năng của giải pháp đề xuất
trong việc giảm thời gian truyển thông báo trên mạng, kéo theo giảm chi phí truyền
thông.
Khóa luận được chia thành năm chương:
Chương 1: Giới thiệu tổng quan về ngạng ngang hàng, ưu nhược điểm và sự phân
loại mạng ngang hàng; những kiến thức cơ bản về DHT và đặc biệt là cấu trúc Chord.
Chương 2: Đề cập đến sự tối ưu hóa trong mạng Chord, các vấn đề và các nghiên
cứu cho những vấn đề đó.
Chương 3: Đề xuất giải pháp tối ưu cấu trúc Chord dựa trên độ trễ, những ưu
nhược điểm của giải pháp đó.
Chương 4: Xây dựng chương trình mô phỏng, các bước thực thi chương trình và
những đánh giá từ kết quả đạt được.
Chương 5: Kết luận, những vấn đề nảy sinh và hướng đi tiếp theo.
2
Chương 1. Tổng quan
Mạng ngang hàng (mạng đồng đẳng, peer-to-peer, P2P) hay công nghệ ngang hàng
đã trở thành thuật ngữ phổ biến trong công nghệ thông tin nói chung và trong lĩnh vực
Internet nói riêng. Các ứng dụng trên mạng ngang hàng xuất hiện ngày càng nhiều, thu
hút đông đảo người dùng máy tính. Rất nhiều công ty, ứng dụng với công nghệ ngang
hàng đã trở lên nổi tiếng, được đông đảo cư dân mạng sử dụng như: Usenet, Freenet,
Napster, Gnutella, BitTorrent… Trong điều kiện Internet ngày càng phát triển, lượng
thông tin truyền tải và chia sẻ ngàng càng lớn, mô hình client server bộc lộ nhiều hạn
chế về băng thông và sức mạnh, mạng ngang hàng với nhiều ưu điểm nổi bật có thêm
nhiều cơ hội mới để phát triển.
Chương này, khóa luận sẽ giới thiệu về mạng ngang hàng, những ưu nhược điểm
của mạng ngang hàng để biết tại sao chúng lại được sử dụng rộng rãi như vậy. Phân biệt
được các loại mạng ngang hàng, đặc điểm, cách hoạt động của từng loại. Và hơn hết,
chúng ta sẽ làm quen với cấu trúc Chord, một trong những giao thức phổ biến nhất trong
mạng ngang hàng có cấu trúc.
1.1. Mạng ngang hàng
Định nghĩa
Mạng ngang hàng, là một mạng máy tính trong đó hoạt động của mạng chủ yếu
dựa vào khả năng tính toán và băng thông của các máy tham gia chứ không tập trung
vào một số nhỏ các máy chủ trung tâm như các mạng thông thường. Mạng ngang hàng
thường được sử dụng để kết nối các máy thông qua một lượng kết nối dạng ad hoc.
Mạng ngang hàng có 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 như âm thanh, hình ảnh, dữ liệu, hoặc
để truyền dữ liệu thời gian thực như điện thoại
VoIP.
Một mạng ngang hàng đúng nghĩa không có
khái niệm máy chủ và máy khách, 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, là một nút mạng đóng vai trò đồng
thời là máy khách và máy chủ đối với các máy
khác trong mạng. Một ví dụ điển hình là dịch vụ
3
Hình 1. Mô hình mạng ngang hàng
truyền dữ liệu. Các nút trong mạng ngang hàng sẽ
liên lạc với nhau, lấy dữ liệu từ nút khác về, đồng
thời chia sẻ dữ liệu đó cho những nút có nhu cầu.
Với mô hình khách chủ, máy khách gửi yêu cầu,
thực hiện việc nhận dữ liệu một chiều từ phía
máy chủ. Đây chính là điểm khác biệt cơ bản nhất
của mô hình ngang hàng so với các mô hình
truyền thống.
Một số mạng hay kênh như Napster, IRC
(thuộc thế hệ thứ nhất) sử dụng mô hình máy chủ-
máy khách cho một số tác vụ và mô hình ngang
hàng cho những tác vụ khác. Ngược lại, các mạng
như Gnutella hay Freenet (thế hệ thứ 2) sử dụng mô hình ngang hàng cho tất cả các tác
vụ, nên các mạng này thường được xem như là mạng ngang hàng đúng nghĩa (thực ra
Gnutella vẫn sử dụng một số máy chủ để giúp các máy trong mạng tìm kiếm địa chỉ IP
của nhau).
Cấu trúc mạng ngang hàng là biểu hiện của một trong những khái niệm quan trọng
nhất của Internet, mô tả trong "RFC 1, Host Software" xuất bản ngày 7 tháng 4 năm
1969. Gần hơn, khái niệm này đã được sự công nhận rộng rãi trong các cấu trúc chia sẻ
nội dung mà không có máy chủ trung tâm.
Khái niệm ngang hàng ngày nay được tiến hóa vào nhiều mục đích sử dụng khác
nhau, không chỉ để trao đổi tệp mà còn khái quát hóa thành trao đổi thông tin giữa người
với người, đặc biệt trong những tình huống hợp tác giữa một nhóm người trong cộng
đồng.
Ưu điểm
Ưu điểm của mạng ngang hàng thể hiện ở việc áp dụng vào từng ứng dụng cụ thể
mà cấu trúc mạng khách chủ không có được. Nói cách khác, ưu điểm của mạng ngang
hàng chính là khắc phục những nhược điểm của mô hình mạng cũ.
Mục đích quan trọng của mạng đồng đằng là trong mạng tất cả các máy tham gia
đều đóng góp tài nguyên, bao gồm băng thông, lưu trữ, và khả năng tính toán. Do đó khi
càng có nhiều máy tham gia mạng thì khả năng tổng thể của hệ thống mạng càng lớn.
Ngược lại, trong cấu trúc máy chủ-máy khách, nếu số lượng máy chủ là cố định, thì khi
số lượng máy khách tăng lên khả năng chuyển dữ liệu cho mỗi máy khách sẽ giảm
xuống.
4
Hình 2. Mô hình mạng khách chủ
Tính chất phân tán của mạng ngang hàng cũng giúp cho mạng hoạt động tốt khi
một số máy gặp sự cố. Đối với cấu trúc tập trung, chỉ cần máy chủ gặp sự cố thì cả hệ
thống sẽ ngưng trệ.
Ngoài ra, do mô hình mạng ngang hàng đơn giản nên dễ cài đặt, tổ chức và quản
trị, chi phí thiết bị thấp. Mô hình khách chủ đòi hỏi một server đủ mạnh với giá thành
cao, thường thì server này ít sự cố, nhưng nếu có sẽ gây thiệt hại lớn về thông tin và cả
chi phí để tái thiết lập lại hệ thống. Hiện nay, máy tính cá nhân đủ mạnh để có thể làm
nhiều hơn công việc của một client, vì thế tham gia vào mạng ngang hàng với nhiều
tiềm năng là khả thi.
Đối với mạng Napster, thuật ngữ ngang hàng nói lên tính chất quan trọng của giao
thức giao tiếp ngang hàng, còn thực ra thành công của Napster phải nhờ vào sự liên kết
chặt chẽ giữa các máy tham gia với máy chủ trung tâm lưu trữ danh sách nội dung tệp
trên các máy tham gia. Nhờ vậy việc tìm kiếm trở nên nhanh và hiệu quả hơn, tuy nhiên,
đây cũng chính là điểm yếu dẫn đến các rắc rối pháp lý mà kết cục là sự sụp đổ của
Napster.
Nhược điểm
Mặc dù có rất nhiều ưu điểm, nhưng mạng ngang hàng cũng bộc lộ khá nhiều
nhược điểm. Các nút tham gia với tính phân tán, trách nhiệm và vai trò là như nhau
trong mạng, ít tuân theo quy luật hay giàng buộc nào. Đáng kể như:
− Kết quả truy vấn trả về có thể là rất nhiều do kết nối đến nhiều nút khác nhau,
sự đồng bộ giữa các nút là khá khó khăn. Hoặc có thể chẳng nhận được trả lời
nào hay dữ liệu cần tìm không tồn tại, do không biết trước nút đích có còn nằm
trong mạng hay không.
− Các nút đột ngột rời khỏi mạng sẽ làm sai bảng định tuyến trong một thời gian
nhất định, làm cho việc truy vấn thiếu chính xác. Dữ liệu mà nút đó phụ trách
cũng có thể bị mất theo.
− Sự bảo mật dữ liệu là kém do dữ liệu phân tán.
Các nhược điểm trên đang dần được san lấp bằng nhiều phương pháp. Đáng chú ý
là đặt ra các luật lệ, nội quy ràng buộc các bên tham gia với quyền lợi và trách nhiệm
nhất định sẽ giúp cho mạng ổn định và an toàn hơn. Số lượng thành viên tham gia mạng
ngang hàng ngày càng nhiều giúp cho tài nguyên mạng trở lên phong phú, hiệu suất
mạng cũng tăng tỉ lệ với số lượng nút tham gia. Ngoài ra, các cơ chế nhân bản giúp cho
xác suất mất dữ liệu khi các nút rời đi trở lên vô cùng nhỏ.
5
1.2. Phân loại mạng ngang hàng
Hai tiêu chí cơ bản để phân loại mạng ngang hàng:
− Theo mục đích sử dụng
Chia sẻ file (file sharing)
Điện thoại VoIP (telephony)
Đa phương tiện media streaming (audio, video)
Diễn đàn thảo luận (Discussion forums)
Tiêu chí này thường được các nhà phát triển ứng dụng quan tâm. Theo đó
các ứng dụng với đặc điểm riêng sẽ được phân loại và áp dụng theo những mô
hình sẵn có, chuyên biệt.
− Theo topo của mạng ở tầng vật lý và mạng phủ.
Đây là tiêu chí được phát triển qua từng thời kỳ và được xem xét nghiên cứu
để tìm ra những giải pháp tốt nhất, xây dựng nền tảng vững chắc cho các ứng dụng
sau này.
1.2.1. Hệ thống ngang hàng lai (Hybrid Peer-to-peer System)
Đây là mạng ngang hàng thế hệ thứ nhất, đặc điểm là vẫn còn dựa trên một
máy chủ tìm kiếm trung tâm - đặc điểm của mô hình khách chủ, chính vì vậy nó
còn được gọi là mạng ngang hàng lai hay mạng tập trung (centralized Peer-to-Peer
networks). Cấu trúc Overlay của mạng ngang hàng lai có thể được mô tả như một
mạng hình sao.
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.
6
Không có nhận xét nào:
Đăng nhận xét