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

- Đề tài nghiên cứu của khóa luận tập trung vào vấn đề “nghiên cứu ảnh hưởng của hiện tượng “tham gia mà không đóng góp”(tiếng Anh: free-riding) đối với hệ thống chia sẻ file ngang hàng BitTorrent”.
- Trước hết, khóa luận sẽ cung cấp một cái nhìn tổng quan về hệ thống mạng ngang hàng hiện nay.
- Tiếp đó, chúng ta sẽ đi sâu vào nghiên cứu hệ thống chia sẻ file ngang hàng BitTorrent (khái niệm, cơ chế và hoạt động).
- Optimistic Unchoking và Free-Rider.
- So sánh BitTorrent và một số hệ thống chia sẻ file ngang hàng khác.
- 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.
- Nghiên cứu hệ thống ở trạng thái ổn định (steady-state).
- 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.
- 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..
- 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ạ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).
- Như vậy có thể thấy hệ thống BitTorrent mà chúng là nghiên cứu thuộc loại mạng ngang hàng lai ghép.
- Các vấn đề cần xem xét trong mạng ngang hàng Các hệ thống mạng ngang hàng đều được xây dựng nên dựa trên sự tự nguyện tham gia của các nút thành viên.
- Đả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.
- Để triển khai về mặt ứng dụng, hệ thống BitTorrent chỉ cần một máy chủ có cài ứng dụng Tracker và các nút tham gia sử dụng một chương trình BitTorrent client nào đó.
- Thuật toán Choking BitTorrent là một hệ thống chia sẻ file ngang hàng, do đó sự tham gia của các nút vào quá trình up và download ảnh hưởng rất lớn đến sự sống còn của mạng.
- 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.
- Trong đó xn là số lượng các nút bình thường (non free-rider) và xf là số lượng của free-rider trong mạng.
- Gọi ρ là tỉ lệ của tổng tốc độ download của free-rider so với tổng băng thông upload của các nút bình thường.
- Từ (2) cho thấy free-rider vẫn có được một phần tốc độ download của cả hệ thống.
- Nói cách khác, cơ chế của BitTorent không thể loại trừ hoàn toàn hiện tượng free-riding, và free-rider có thể nhận được tài nguyên từ các nút bình thường thông qua optimistic unchoking.
- Ví dụ chương trình eMule có hệ thống điểm (credits system) để thưởng các máy tải lên nhiều.
- Các thử nghiệm trong [4] đã chỉ ra rằng cơ chế của BitTorrent không thể đảm báo được tính công bằng trong hệ thống.
- Mô hình chia các downloader trong mạng thành 2 loại chính free-rider và non free-rider và xem xét ảnh hưởng của free-rider trong hệ thống BitTorrent một cách khá toàn diện..
- Mô hình và các tham số Dựa trên các kết luận trình bày trong phần 4.1.1, chúng ta sẽ xây dựng một mô hình mạng trong đó các nút trong mạng được chia làm 3 loại chính: seed, free-rider và non free-rider.
- Các nút non free-rider được xem là đóng góp cho mạng ngang nhau trong khi các nút free-rider hoàn toàn không có đóng góp gì cho hệ thống.
- Seed không phân biệt free-rider hay non free-rider trong quá trình upload.
- Hệ thống được mô tả bởi các tham số (mô hình “Fluid model”) sau:.
- số lượng của non free-rider trong hệ thống tại thời điểm t · xf(t): số lượng của free-rider trong hệ thống tại thời điểm t · y(t): số lượng seed trong hệ thống tại thời điểm t · λn: Tốc độ tham gia vào mạng của non free-rider · λf: Tốc độ tham gia vào mạng của free-rider · µ: Băng thông upload của một nút · c: Băng thông download của một nút · θ: Tốc độ rời mạng của nút bình thường · γ: Tốc độ rời mạng của seed · η: Hiệu năng của quá trình chia sẻ file [3].
- ρ(t): Tỉ lệ của tổng tốc độ download của free-rider so với tổng tốc độ upload của non free-rider tại thời điểm t.
- κ(t): Tỉ lệ của số lượng free-rider trên tổng số lượng của free-rider và non free-rider tại thời điểm t.
- Ta giả sử free-rider rời mạng ngay sau khi download hoàn thành(bởi vì free-rider khi đó có ở lại mạng cũng không có ý nghĩa gì).
- Như vậy, trong hệ thống tồn tại 3 trạng thái: Seed, free-rider và non free-rider.
- Hình 2: Mô hình chung biểu diễn 3 trạng thái trong hệ thống chia sẻ file BitTorrent.
- Trong mô hình này, tốc độ gia nhập mạng của free-rider và non free rider tương ứng là λf và λn.
- Hiệu năng chia sẻ file của free-rider bằng 0.
- Tại thời điểm t, tốc độ upload của toàn bộ hệ thống là µ(ηxn(t.
- Tất cả các nút trong mạng cùng chia sẻ tốc độ upload được cung cấp bởi non free-rider và seed.
- ρ(t) cho biết tỉ lệ băng thống upload của non free-rider bị chiếm vởi free-rider.
- Do đó, tổng tốc độ download của non free-rider là : µ[(1-ρ(t))ηxn(t.
- θxn(t) và θxf(t) tương ứng là tốc độ của non free-rider và free-rider rởi khỏi các trạng thái tương ứng khi đang download dở.
- Non free-rider chuyển sang trạng thái seed với tốc độ Dn(t) sau khi download xong.
- Nghiên cứu hệ thống ở trạng thái ổn định (steady-state) Để nghiên cứu hệ thống ở trạng thái ổn định, chúng ta giả sử limt→∞xn(t), limt→∞xf(t), limt→∞y(t) tồn tại và : Trong đó xn, xf , và y là các giá trị cân bằng tương ứng của xn(t), xf(t) và y.
- Định lý 1 : Gọi Tn và Tf là thời gian download trung bình tương ứng của non free-rider và free-rider trong hệ thống.
- Trong một hệ thống không có seed, chúng ta có kết quả sau.
- Tương tự, trong mô hình của chúng ta, thời gian download trung bình tương ứng của non free-rider và free-rider được tính bởi.
- Khi có một nút hoàn thành download, khả năng nó là free-rider là ρ , và khả năng nó là non free-rider là 1 – ρ.
- Do đó thời gian download trung bình của toàn bộ hệ thống là: Thay tương ứng các giá trị trong các biểu thức ta được kết quả của định lý.
- Nhận xét: Thông qua việc mô hình hóa hệ thống BitTorrent, chúng ta đã thấy được hiệu năng của hệ thống ở trạng thái ổn định và ảnh hưởng của hiện tượng free-riding lên hệ thống BitTorrent.
- Từ kết quả của định lý 1, xét trong điều kiện số lượng liên kết upload của một nút u=5, và với giá trị hiệu năng chia sẻ file η được xem xét trong [12] là gần như bằng 1, chúng ta thu được đồ thị biểu diễn sự phụ thuộc thời gian download trung bình của non free-rider, free-rider và hệ thống thông qua sự biến thiên của α: Hình 3: Thời gian download trung bình của non free-rider, free-rider và hệ thống theo sự biến thiên của α.
- Từ đồ thị trên cho thấy thời gian download trung bình Tf của free-rider luôn luôn lớn hơn thời gian download trung bình Tn của non free-rider.
- Hơn nữa, khi α đạt giá trị 0.2 (=1/u) thì Tf không tồn tại (có nghĩa là một số free-rider không có đủ tài nguyên để kết thúc quá trình download).Ngược lại, non free-rider luôn luôn có thể hoàn thành quá trình download.
- Từ đó, có thể kết luận là cơ chế của BitTorrent có khả năng chống lại hiện tượng free-riding trong hệ thống không có seed, và thông qua Optimistic Unchoking, free-rider cũng không gây ảnh hưởng lớn đối với hiệu năng của toàn hệ thống..
- có nghĩa là nút non free-rider sẽ rời mạng ngay sau khi quá trình download hoàn thành.
- Tuy nhiên, trong thực tế, sau khi hoàn thành download vẫn có một số lượng các nút vẫn ở lại hệ thống và đóng vai trò như seed.
- Do đó, free-rider vẫn có cơ hội nhận được thêm tài nguyên từ seed và có thể hoàn thành dược quá trình download.
- Bây giờ, chúng ta sẽ xem xét ảnh hưởng của hiện tượng free-riding lên hiệu năng của hệ thống khi giá trị γ thay đổi.
- Định lý 2: Gọi Tn và Tf là thời gian download trung bình tương ứng của non free-rider và free-rider trong hệ thống có seed, chúng ta có kết quả sau.
- Từ kết luận của định lý 2, ta có đồ thị sau: Hình 4: Tỉ số giữa thời gian download trung bình của non free-rider trên thời gian download trung bình của free-rider biến thiên theo γ..
- thì thời gian download trung bình của non free-rider và free-rider lúc đó là ngang nhau (thời gian này được xác định bởi băng thông download c).
- Khi γ tăng lên, thời gian download của free-rider dần dần tăng lên do đó, tỉ số giữa Tn và Tf giảm xuống..
- Từ nhận xét trên, chúng ta có thể kết luận rằng cơ chế của BitTorrent không có hiệu quả trong việc hạn chế free-riding khi hệ thống có nhiều seed.
- Khi số lượng seed trong hệ thống tăng lên đến một giá trị nhất định, thời gian download của free-rider và non free-rider là ngang nhau..
- private SortedList nodes : Chứa danh sách toàn bộ các nút tham gia trong hệ thống.
- Phương thức được sử dụng khi một nút hoàn thành download và ở lại thành seed trong hệ thống.
- public static long joinTime : Thời gian để các nút tham gia vào hệ thống.
- public static float joinRate : Tốc độ các nút tham gia vào hệ thống.
- Đẳng thức (3) cho thấy rằng free-rider có thể nhận được một phần tài nguyên cung cấp bởi non free-rider thông qua Optimistic Unchoking.
- Tuy nhiên, kết quả thu được từ định lý 1 đã cho thấy rằng, phần tài nguyên hệ thống mà free-rider có thể thu được thông qua Optimistic Unchoking là không đáng kể, khi số lượng free-rider trong mạng tăng lên (tương ứng với sự tăng lên của α), thì thời gian download trung bình của free-rider cũng tăng lên đáng kể trong khi thời gian download trung bình của non free-rider không thay đổi nhiều.
- Mặt khác, từ kết quả thu được của định lý 2, chúng ta thấy rằng, khi số lượng seed trong hệ thống tăng lên thì thời gian download trung bình của free rider lại giảm đi, và khi số lượng seed trong hệ thống đạt đến một giá trị nhất định thì thời gian download trung bình của free-rider và non free-rider trở nên tương đương với nhau.
- Như vậy, ta có thể thấy rằng, trong hệ thống chia sẻ file BitTorrent, free-rider chủ yếu nhận được nguồn tài nguyên từ seed.
- Đề xuất phương án cải thiện Ở trên chúng ta đã thấy được rằng, free-rider chủ yếu nhận được nguồn tài nguyên trong hệ thống nhờ có seed.
- Điều đó gây nên sự mất công bằng đối với các nút non free-rider.
- Quy tắc thứ 2, không mở kết nối upload cho nút có tốc độ download bằng 0 nhằm loại bỏ cơ hội download từ seed của free-rider.
- Tuy nhiên, chúng ta lại thấy rằng, free-rider vẫn có thể nhận được một phần tài nguyên trong hệ thống do seed cũng vẫn áp dụng Optimistic Unchoking.
- Đó là thêm một thuộc tính đánh dấu node có phải là free-rider hay không (vì free-rider có hành động hoàn toàn khác với nút bình thường, nó không mở kết nối upload cho bất cứ nút hàng xóm nào).
- Trong các thí nghiệm, tôi sử dụng chức năng được thiết kế cho “post flash crown” trong bài báo [4] để đưa các free-rider vào hệ thống song song cùng với các nút bình thường.
- Chúng ta sẽ xem xét ảnh hưởng của free-riding lên hệ thống khi thay đổi tốc độ tham gia vào mạng của free-rider từ 1 đến 12, và cố định tốc độ tham gia vào mạng của non free-rider là 100.
- Non free-rider join rate: 100/s.
- Free rider join rate: thay đổi lần lượt từ 1 đến 12 - Join time : 10s - Băng thông của non free-rider: Download: 1500, Upload 400.
- Băng thông của free-rider: Download: 1500, Upload 0 C.
- Hình 5: Sự thay đổi thời gian download trung bình của free-rider và non free-rider theo sự biến thiên tốc độ tham gia mạng của free-rider..
- Từ kết quả thử nghiệm chúng ta thấy được rằng thời gian download trung bình của free-rider tăng lên một cách nhanh chóng (đường khá dốc) khi tăng tốc độ free-rider tham gia trong mạng (Tôi đã thử nghiệm khi λf bằng 20 thì 1 số free-rider không thể hoàn thành download – kết quả đó không được thể hiện trong biểu đồ này).
- Trong khi đó, thời gian download trung bình của các nút non free-rider lại thay đổi không đáng kể.
- Điều này chứng tỏ rằng cơ chế hiện tại của BitTorrent có khả năng hạn chế hiện tượng free-riding khá hiệu quả khi trong hệ thống không có seed..
- Mô tả thử nghiệm Trong thử nghiệm này, chúng ta sẽ xác nhận lại ảnh hưởng của seed đối với free-rider.
- Chúng ta sẽ cố định tốc độ tham gia vào mạng của cả free-rider và non free-rider tương ứng là 100 và 12.
- Hình 6: So sánh thời gian download trung bình của free-rider và non free-rider khi số lượng seed trong hệ thống thay đổi Từ kết quả thí nghiệm, chúng ta thấy rằng, khi số lượng seed trong hệ thống tăng lên thì thời gian download hoàn thành trung bình của free-rider giảm đi, và giảm đến 1 giá trị gần như cố định khi tỉ lệ rời mạng là 0.8 (lúc này, số nút non free-rider ở lại mạng và trở thành seed tương đương với số lượng free-rider có trong mạng, do đó, free-rider có thể dễ dàng có được đủ lượng tài nguyên hệ thống cần thiết để hoàn thành download sớm).
- Điều này cũng khẳng định, cơ chế của BitTorrent không hiệu quả trong việc hạn chế hiện tượng free-riding khi hệ thống có nhiều seed..
- Hình 7: Thời gian download trung bình của free-rider trong cơ chế cũ và mới Trong khi thử nghiệm với tỉ lệ rời mạng của non free-rider bằng 1 và cơ chế mới, trong hệ thống chỉ có 32 free-rider có thể hoàn thành download ( trên tổng số 120 free-rider có trong hệ thống), thời gian download trung bình trên biểu đồ là tính cho các nút hoàn thành download còn lại.
- Từ tỉ lệ 0.9 trở xuống, free-rider mới có đủ tài nguyên để hoàn thành quá trình download..
- Từ biểu đồ cho thấy rằng, sau khi thay đổi cơ chế của BitTorrent, thời gian download trung bình của free-rider bị tăng lên, và cơ chế mới tỏ ra đặc biệt hiệu quả khi hệ thống có số lượng seed ít.
- Khi số lượng seed trong hệ thống tăng lên.
- cỡ bằng số lượng free-rider thì free-rider vẫn có cơ hội nhận đủ tài nguyên thông qua Optimistic Unchoking).
- Nghiên cứu tập trung vào vấn đề Free-riding đối với hệ thống BitTorrent.
- Bằng việc mô hình hóa hệ thống BitTorrent với các tham số, chúng ta đã thấy được rằng, các free-rider vẫn có khả năng chiếm được một phần nguồn tài nguyên hệ thống thông qua Optimistic Unchoking.
- Đề tài nghiên cứu về ảnh hưởng của hiện tượng free-riding lên hệ thống chia sẻ file ngang hàng BitTorrent đã đạt được những kết quả nhất định.
- 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