ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Lê Quang Tuấn
NGHIÊN CỨU ẢNH HƯỞNG CỦA HIỆN TƯỢNG
“THAM GIA MÀ KHÔNG ĐÓNG GÓP” LÊN HỆ
THỐNG CHIA SẺ FILE NGANG HÀNG
BITTORRENT
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2009
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Lê Quang Tuấn
NGHIÊN CỨU ẢNH HƯỞNG CỦA HIỆN
TƯỢNG “THAM GIA MÀ KHÔNG ĐÓNG GÓP”
LÊN HỆ THỐNG CHIA SẺ FILE NGANG HÀNG
BITTORRENT
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: Tiến sỹ Nguyễn Đại Thọ
HÀ NỘI - 2009
Lời cảm ơn
Mở đầu cho khóa luận, em xin gửi lời cám ơn chân thành nhất tới
các thầy cô giáo trong khoa Công nghệ thông tin, Trường đại học
Công Nghệ, Đại học Quốc gia Hà nội đã tận tình dạy dỗ em trong 4
năm học vừa qua. Đặc biệt, em xin chân thành cám ơn tiến sỹ
Nguyễn Đại Thọ, người đã hướng dẫn, chỉ bảo em trong quá trình
thực hiện khóa luận này.
Mình cũng muốn gửi lời cám ơn tới những người bạn học K50CB và
K50MMT, những người đã cùng với em chia sẽ những ngày tháng trên
ghế giảng đường đại học, cùng chia sẻ niềm vui cũng như giúp đỡ lẫn
1.1. Khái niệm về mạng ngang hàng ......................................................................................................................... 8
1.2. Phân loại mạng ngang hàng ............................................................................................................................... 8
1.2.1. Mạng ngang hàng thuần túy và mạng ngang hàng lai ghép ....................................................... 8
1.2.2. Mạng ngang hàng không có cấu trúc và mạng ngang hàng có cấu trúc ..................................... 9
1.3. Ưu thế và các vấn đề cần xem xét trong mạng ngang hàng ............................................................................ 10
1.3.1. Các ưu thế của mạng ngang hàng ............................................................................................ 10
1.3.2. Các vấn đề cần xem xét trong mạng ngang hàng .................................................................... 10
1.3.3. Tiềm năng phát triển của mạng ngang hàng ........................................................................... 11
Chương 2. Mạng chia sẻ file ngang hàng BitTorrent ...................................................................................... 12
2.1. BitTorrent là gì? .............................................................................................................................................. 12
2.2. Cơ chế và hoạt động của BitTorrent ................................................................................................................ 13
2.2.1. Quá trình chia sẻ file ................................................................................................................ 13
2.2.2. Sự lựa chọn các phần đơn vị (Piece Selection) ........................................................................ 14
2.2.3. Thuật toán Choking ................................................................................................................. 14
2.3. Optimistic Unchoking và Free-Rider .................................................................................................................. 15
2.4. So sánh BitTorrent và một số hệ thống chia sẻ file ngang hàng khác .............................................................. 16
Chương 3. Mô hình hóa và xem xét ảnh hưởng của free-riding lên hệ thống chia sẻ file BitTorrent .............. 17
3.1. Một số nghiên cứu liên quan ............................................................................................................................ 17
3.2. Mô hình và các tham số ................................................................................................................................... 18
3.3. Nghiên cứu hệ thống ở trạng thái ổn định (steady-state) ............................................................................... 21
Chương 4. Chương trình mô phỏng OctoSim ................................................................................................ 27
4.1. Cài đặt và sử dụng chương trình ..................................................................................................................... 27
4.1.1. Giới thiệu, cách thức cài đặt và thiết lập môi trường để chạy chương trình OctoSim ............ 27
4.1.2. Đầu vào và đầu ra của chương trình mô phỏng ...................................................................... 28
4.2. Cấu trúc và chức năng của chương trình mô phỏng ......................................................................................... 29
4.2.1. File Main.cs: ............................................................................................................................ 30
4.2.2. File WorkloadProcessor.cs: ..................................................................................................... 30
4.2.3. File Sim.cs: .............................................................................................................................. 31
4.2.4. File ProtocolMain.cs: .............................................................................................................. 32
4.2.5. File Node.cs: ............................................................................................................................ 33
BitTorrent chiếm tới 35% lưu lượng trung chuyển trên mạng Internet, đó là 1 con số lớn,
hơn tất cả các hệ thống chia sẻ file khác gộp lại.
Sự phát triển mạnh mẽ của BitTorrent trong thời gian vừa qua cho thấy sự hiệu
quả và ổn định trong cơ chế và giao thức của nó. Tuy nhiên, cũng như hầu hết các hệ
thống hoạt động trên mô hình mạng ngang hàng, hoạt động của BitTorrent cũng dựa
trên sự tự nguyện đóng góp của các thành phần tham gia trong mạng. Do đó, BitTorrent
cũng phải đối mặt với vấn đề free-riding (có những người dùng tham gia vào mạng chỉ
để lấy tài nguyên về mà không chịu đóng góp cho hệ thống).
Trong khuôn khổ của khóa luận, chúng ta sẽ từng bước tìm hiểu qua 6 chương:
Chương 1: Tổng quan về mạng ngang hàng, Trình bày các kiến thức cơ bản về
mạng ngang hàng (P2P Network),ưu nhược điểm của mạng ngang hàng và các vấn đề
cần chú ý khi nghiên cứu mạng ngang hàng.
Chương 2: Hệ thống chia sẻ file ngang hàng BitTorrent, giới thiệu về
BitTorrent, cơ bản về giao thức, cách thức chia sẻ file, cơ chế thúc đẩy các nút tham gia
đóng góp cho hệ thống. So sánh BitTorrent với một vài hệ thống chia sẻ file ngang hàng
khác. Trong chương này cũng trình bày nguyên nhân dẫn đến khả năng tồn tại của các
nút free-rider.
Chương 3: Mô hình hóa và xem xét ảnh hưởng của hiện tượng free-riding
lên hệ thống chia sẻ file BitTorrent, trong chương này tôi nghiên cứu mô hình
BitTorrent được đề xuất trong bài báo “Free-Riding on BitTorrent-like File Sharing
System: Modeling, Analysis and Improvement” của các tác giả Jiadia Yu, Minglu Li, Jie
Wu. Qua đó thấy được mức độ ảnh hưởng của hiện tượng free-riding lên hệ thống cũng
như khả năng tự bảo vệ của hệ thống BitTorrent. Từ đó, đề xuất cơ chế khắc hạn chế
hiện tượng free-riding.
Chương 4: Chương trình mô phỏng OctoSim, chương này giới thiệu và mô tả
cấu trúc chức năng của chương trình mô phỏng OctoSim ( một chương trình mô phỏng
hệ thống BitTorrent của Microsoft Research được viết bằng ngôn ngữ C#)
Chương 5: Các thí nghiệm mô phỏng và đánh giá, trong chương này tôi rút ra
một số kết luận từ quá trình nghiên cứu và đề xuất phương án nhằm hạn chế hiện tượng
free-riding, sau đó sử dụng chương trình mô phỏng OctoSim để thực hiện các thí
1.2.2. Mạng ngang hàng không có cấu trúc và mạng ngang hàng có cấu
trúc
Mạng phủ (Overlay) ngang hàng 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 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 phủ ta có thể phân loại hệ thống mạng ngang hàng phân tán thành
2 loại: có cấu trúc hay không cấu trúc.
Một mạng ngang hàng không cấu trúc khi các liên kết giữa các nút mạng trong
mạng phủ được thiết lập ngẫu nhiên (tức là không theo qui luật nào). Những mạng như
thế này dễ dàng được xây dựng vì một máy mới khi muốn tham gia mạng có thể lấy 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 tự bản thân nó
sẽ thêm vào các liên kết mới của riêng mình. Khi một máy muốn tìm một dữ liệu trong
mạng đồng đẳ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. Hệ thống này thể hiện rõ nhược điểm: không có gì
đảm bảo tìm kiếm sẽ thành công. Đối với tìm kiếm các dữ liệu 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 một máy và dữ
liệu nó quản lý trong mạng, do đó yêu cầu tìm kiếm được chuyển một cách ngẫu nhiên
đến một số máy trong mạng. Số lượng máy trong mạng càng lớn thì khả năng tìm thấy
thông tin càng nhỏ.
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.
Hầu hết các mạng ngang hàng phổ biến là không cấu trúc như Napster, Gnutella,
Fasttrack và eDonkey2000.
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
bằng cách sử dụng hệ thống DHT (Bảng Băm Phân Tán, tiếng anh: Distributed Hash
Table). 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
của một hệ thống mạng ngang hàng phụ thuộc vào việc hệ thống đó tận dụng
được các tài nguyên đóng góp của các nút tham gia mạng. Đặc biệt chú ý đến
vấn đề tận dụng băng thông của các nút tham gia mạng.
- Đảm bảo được tính công bằng trên mạng: Vai trò của các nút trong một hệ
thống mạng ngang hàng là ngang nhau, do đó mức độ đóng góp và dịch vụ
được hưởng cũng phải ngang nhau. Trong vấn đề về tính công bằng trên
mạng cần đặc biệt chú ý đến hiện tượng free-riding, đây cũng là yếu tố được
nghiên cứu trong khóa luận này.
- Duy trì tính sẵn có(avaibility) của tài nguyên: Mục đích của việc lưu trữ và
chia sẻ file, ai cũng muốn file được lưu trữ lâu dài và có thể lấy về bất cứ lúc
nào. Tuy nhiên trong mạng ngang hàng thì không có ràng buộc gì để đảm bảo
được điều đó do trong mạng ngang hàng, sự đóng góp là hoàn toàn tự nguyện.
- Còn một vấn đề khác cần được lưu ý ngoài các vấn đề về mặt kĩ thuật trên.
Đó chính là vấn đề về bản quyền của các thông tin được chia sẻ trên mạng.
Hiện tại, P2P là nơi lý tưởng để trao đổi các file nhạc, film không có bản
quyền (cũng là một phần lý do thúc đẩy mạng P2P phát triển như hiện nay).
1.3.3. Tiềm năng phát triển của mạng ngang hàng
Hiện nay, khái niệm mạng ngang hàng hoàn toàn không lạ lẫm. Số người biết đến
và sử dụng những ứng dụng trên nền tảng công nghệ mạng ngang hàng đang tăng lên
từng ngày. Mặc dù vẫn còn những vấn đề về bảo mật hay vấn đề về bản quyền của
những nội dung được trao đổi trong mạng ngang hàng, nhưng với những ưu thế và lợi
ích mà mạng ngang hàng đem lại, chúng ta vẫn có thể thấy được sự phát triển mạnh mẽ
của nó.
Trên thực tế, cũng đang có rất nhiều nghiên cứu phát triển các ứng dụng trên nền
công nghệ mạng ngang hàng, từ những lĩnh vực bình thường của đời sống như giải trí
hay truyền hình( các ứng dụng về truyền video thông qua mạng ngang hàng) đến công
việc kinh doanh hay nghiên cứu khoa học. Đặc biệt, quân đội Mỹ cũng đã có những dự
án nghiên cứu phát triển những ứng dụng quân sự trên nền công nghệ mạng ngang hàng.
Chúng ta hoàn toàn có thể tin tưởng rằng, trong tương lai gần, mạng ngang hàng sẽ
tiếp tục phát triển và cung cấp thêm nhiều lợi ích cho cuộc sống.
(thường là có kích thước 256KB) và một nút khi tham gia vào mạng thì có thể download
cùng lúc các phần khác nhau từ các nút khác nhau.
Để bắt đầu chia sẻ 1 file, người nắm giữ file này sẽ tạo ra một file tĩnh có phần mở
rộng là .torrent. File .torrent này có chứa các thông tin về file muốn chia sẻ như, dung
lượng file, tên file, số lượng các phần và giá trị băm của nội dung file cũng như nội
dung từng phần nhỏ đó, đồng thời trong file đó cũng có chứa địa chỉ url của Tracker
(server có nhiệm vụ liên kết các nút với nhau). Cụ thể, Tracker sẽ nắm giữ các thông tin
như có những nút nào đang download file nào và các nút đó đang lắng nghe ở cổng
nào…, các thông tin này được cập nhật mỗi 30 phút. Và để đảm bảo là người dùng khác
có thể download, người muốn chia sẻ ban đầu phải giữ kết nối vào mạng trong thời gian
nhất định. Nút mạng này được gọi là seed. Ngoài ra, seed còn để chỉ các nút nắm giữ
toàn bộ các phần của file và tự nguyện tham gia quá trình upload các phần đó cho các
nút khác. Các nút còn lại trong mạng được gọi là downloader hay leecher.
Khi ai đó muốn download 1 file qua BitTorrent, bằng cách nào đó có được file
.torrent của file đó (ví dụ như tải về từ 1 trang web nào đó .v.v..), từ thông tin có trong
file .torrent, nút đó sẽ kết nối đến tracker và nhận về 1 danh sách(khoảng 40 nút) ngẫu
nhiên các nút đang tham gia vào quá trình download file đó. Sau đó, nó sẽ tiến hành kết
nối đến các nút đó và bắt đầu trao đổi các phần đơn vị của file. Tập hợp các nút cùng
đang chia sẻ 1 file gọi là 1 swarm hay torrent, tập hợp các nút đang liên kết với 1 nút
nào đó gọi là neiborghs hay peers của nút đó. Để quá trình trao đổi được thuận lợi, mỗi
nút sẽ thông báo cho tất cả các nút kết nối với nó rằng nó đang nắm giữ những phần đơn
vị nào của file đang chia sẻ.
2.2.2. Sự lựa chọn các phần đơn vị (Piece Selection)
Như đã nói ở trên, quá trình chia sẻ file trong BitTorrent chính là quá trình trao đổi
các phần đơn vị (pieces) của file đó giữa các nút mạng. Vì thế giải thuật lựa chọn các
phần này sao cho hợp lý rất quan trọng. Trong BitTorrent, giải thuật lựa chọn được áp
dụng ở các nút tuân theo các nguyên tắc sau.
Ưu tiên nghiêm ngặt( Strict Priority): Khi một piece được chọn, nó phải được
download xong trước khi chọn piece khác. Quy tắc này để đảm bảo nút có được đầy đủ
pieces một cách nhanh nhất có thể.
độ download cũng như upload.
Trong Khóa luận này, chúng ta sẽ nghiên cứu kĩ hơn tác dụng của cơ chế thúc đẩy
của BitTorrent trong việc hạn chế hiện tượng free-riding trong BitTorrent.
2.3. Optimistic Unchoking và Free-Rider
Free-rider là nút không upload đến các nút khác, do đó theo chiến lược TFT, nó
cũng không nhận được dữ liệu từ các nút khác. Tuy nhiên do có Optimistic Unchoke
như đã nói ở trên, free-rider vẫn có được cơ hội nhận được dữ liệu từ hệ thống. Chúng
ta sẽ xem xét cụ thể hơn vấn đề này.
Gọi G{p
0
,p
1
, …, p
xn-1
, q
0
,q
1
, …, q
xf-1
} là tập hợp các nút trong mạng
BitTorrent. Trong đó x
n
là số lượng các nút bình thường (non free-rider) và x
f
là số
lượng của free-rider trong mạng. Giả sử tất cả các nút trong mạng có cùng một băng
thông upload , và không có seed trong G. Gọi µ là băng thông upload của mỗi nút, như
vậy tổng băng thông upload của hệ thống là µx
n
chuyển vị trí các máy này lên đầu của hàng đợi làm cho thời gian chờ ít hơn. Hệ thống
này tỏ ra khá hiệu quả vì hàng đợi trong mỗi máy khách sử dụng eMule thường lên đến
hàng trăm, thậm chí hàng ngàn.
KaZaA là một giao thức gần giống với giao thức BitTorrent nhưng nó có một điểm
khác đó là nó phân biệt các máy trạm theo cấp cống hiến (Participation Level). Cấp
cống hiến tăng khi bạn tải lên và giảm khi bạn tải về. Khi bạn tải lên một tài nguyên thì
người có cấp cống hiến cao nhất nhận đầu tiên sau đó người có cấp cống hiến cao nhất
này tải lên cho người có cấp cống hiến thấp hơn và cứ tiếp tục như vậy. Mô hình này
tương tự như mô hình kim tự tháp, với người tải lên nhiều nhất ở vị trí đỉnh của kim tự
tháp, và người ít tải lên ở các vị trí đáy của kim tự tháp. Mô hình KaZaA chỉ thích hợp
phân phối tài nguyên cho một số lượng lớn người dùng, nó đã được chứng minh là
người ở đáy kim tự tháp tải tệp về nhanh hơn trường hợp tải tệp về bằng phương pháp
HTTP (trong trường hợp tệp rất lớn). Nhưng mô hình KaZaA có một nhược điểm nhỏ
đó là nó tin tưởng vào báo cáo của các máy trạm về cấp cống hiến vì vậy các máy trạm
có thể gian lận cấp cống hiến với rất nhiều các máy trạm không chính thức.
Chương 3. Mô hình hóa và xem xét ảnh hưởng của free-
riding lên hệ thống chia sẻ file BitTorrent
3.1. Một số nghiên cứu liên quan
BitTorrent là hệ thống chia sẻ file ngang hàng phổ biến nhất hiện nay, vì thế nó
cũng dành được sự quan tâm nghiên cứu của rất nhiều nhà khoa học. Có nhiều nghiên
cứu nhằm cải tiến nâng cao hiệu năng của hệ thống BitTorrent với nhiều đề xuất khác
nhau. Tuy nhiên đa số những khảo sát, cả về mô phỏng lẫn theo dõi thực thế [4][6][7]
Copyright: Tài liệu đại học ©