Khóa luậ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

ĐẠ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 nhau trong quá trình học tập tại trường. Cuối cùng, với tất cả lòng biết ơn, con muốn nói lời cám ơn cha mẹ, những người đã luôn tin tưởng và động viên em, cho em chỗ dựa vững chắc để vững tin hơn trong cuộc sống. Tháng 5 năm 2009 Lê Quang Tuấn Tóm tắt Đề 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). và để làm rõ nội dung của đề tài nghiên cứu, Hệ thống BitTorrent sẽ được mô hình hóa bởi các tham số, các nút tham gia trong mạng được chia làm 3 loại đó là seed (nút chỉ upload mà không download), free-rider (nút tham gia vào hệ thống chỉ download mà không đóng góp) và non free-rider (các nút bình thường, vừa tham gia download vừa tham gia upload), từ đó xem xét khả năng tự bảo vệ chống lại free- riding trong cơ chế của BitTorrent, và đề xuất phương án cải thiện. Trong phần sau của khóa luận, tôi đã sử dụng 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) để thực hiện các thử nghiệm chứng minh tính đúng đắn của những nghiên cứu. Mục lục Giới thiệu chung .................................................................................................................................................... 1 Chương 1. Tổng quan về mạng ngang hàng........................................................................................................ 3 1.1. Khái niệm về mạng ngang hàng ....................................................................................................................... 3 1.2. Phân loại mạng ngang hàng............................................................................................................................. 3 1.2.1. Mạng ngang hàng thuần túy và mạng ngang hàng lai ghép ............................................................... 3 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 ............................................. 4 1.3. Ưu thế và các vấn đề cần xem xét trong mạng ngang hàng ............................................................................. 5 1.3.1. Các ưu thế của mạng ngang hàng....................................................................................................... 5 1.3.2. Các vấn đề cần xem xét trong mạng ngang hàng ............................................................................... 5 1.3.3. Tiềm năng phát triển của mạng ngang hàng....................................................................................... 6 Chương 2. Mạng chia sẻ file ngang hàng BitTorrent ......................................................................................... 7 2.1. BitTorrent là gì?............................................................................................................................................. 7 2.2. Cơ chế và hoạt động của BitTorrent ............................................................................................................... 8 2.2.1. Quá trình chia sẻ file .......................................................................................................................... 8 2.2.2. Sự lựa chọn các phần đơn vị (Piece Selection) .................................................................................. 9 2.2.3. Thuật toán Choking.......................................................................................................................... 10 2.3. Optimistic Unchoking và Free-Rider.............................................................................................................. 10 2.4. So sánh BitTorrent và một số hệ thống chia sẻ file ngang hàng khác ........................................................... 11 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.......... 13 3.1. Một số nghiên cứu liên quan .......................................................................................................................... 13 3.2. Mô hình và các tham số................................................................................................................................. 13 3.3. Nghiên cứu hệ thống ở trạng thái ổn định (steady-state) .............................................................................. 16 Chương 4. Chương trình mô phỏng OctoSim................................................................................................... 23 4.1. Cài đặt và sử dụng chương trình ................................................................................................................... 23 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...................... 23 4.1.2. Đầu vào và đầu ra của chương trình mô phỏng................................................................................ 24 4.2. Cấu trúc và chức năng của chương trình mô phỏng ...................................................................................... 25 4.2.1. File Main.cs:..................................................................................................................................... 25 4.2.2. File WorkloadProcessor.cs:.............................................................................................................. 26 4.2.3. File Sim.cs:....................................................................................................................................... 27 4.2.4. File ProtocolMain.cs: ....................................................................................................................... 28 4.2.5. File Node.cs: .................................................................................................................................... 29 4.2.6. File SimParameters.cs ...................................................................................................................... 30 4.2.7. Các file khác..................................................................................................................................... 30 Chương 5. Các thí nghiệm mô phỏng và đánh giá............................................................................................ 31 5.1. Kết luận sau khi xem xét mô hình và đề xuất phương án cải thiện................................................................ 31 5.1.1. Kết luận thu được từ quá trình phân tích và tính toán ...................................................................... 31 5.1.2. Đề xuất phương án cải thiện............................................................................................................. 31 5.2. Tiến hành các thử nghiệm .............................................................................................................................. 32 5.2.1. Thử nghiệm thứ nhất ........................................................................................................................ 32 5.2.2. Thử nghiệm thứ hai .......................................................................................................................... 34 5.2.3. Thử nghiệm thứ ba ........................................................................................................................... 36 Chương 6. Kết luận và phương hướng tiếp theo............................................................................................... 37 Tài liệu tham khảo............................................................................................................................................... 39  1 Giới thiệu chung Hiện nay, máy tính đã trở thành công cụ không thể thiếu trong cuộc sống của mỗi con người. Máy tính đã hỗ trợ rất đắc lực cho chúng ta trong công việc, học tập cũng như giải trí hầu như mọi nơi, mọi lúc. Và một trong những lý do lớn khiến cho máy tính có thể len lỏi vào từng ngõ ngách của cuộc sống như vậy chính là do có sự xuất hiện của mạng Internet. Internet giúp chúng ta thu hẹp mọi khoảng cách, mở cánh cửa bước vào kho tài nguyên tri thức vô tận của nhân loại. Trong quá trình phát triển của Internet, bên cạnh những ứng dụng theo mô hình Client / Server truyền thống như WWW, email, FTP,… trong thời gian gần đây, đã xuất hiện các ứng dụng theo mô hình ngang hàng (Peer to Peer – P2P). Với các ưu điểm như tốn ít chi phí xây dựng cơ sở hạ tầng, tận dụng được tài nguyên của các máy tham gia vào mạng, giải quyết được vấn đề điểm chết trung tâm của mô hình Client / Server truyền thống, các ứng dụng trên mạng ngang hàng ngày càng được quan tâm phát triển nhiều hơn. Từ sự xuất hiện của Napster vào năm 1999, có nhiều ứng dụng chia sẻ file ngang hàng được phát triển, ví dụng như Gnutella, KaZaA và BitTorren. Nhưng trong đó BitTorrent có số lượng người dùng lớn nhất và đã trở thành giải pháp chính cho việc chia sẻ file ngang hàng. Trong một nghiên cứu đã cho thấy rằng, các tài khoản sử dụng 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 2 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í nghiệm nhằm kiểm chứng các kết quả nghiên cứu và hiệu quả của đề xuất, và có những nhận xét cũng như giải thích về những kết quả đã đạt được. Chương 6: Kết quả thu được trong quá trình làm khóa luận và phương hướng nghiên cứu trong tương lai. 3 Chương 1. Tổng quan về mạng ngang hàng 1.1. Khái niệm về mạng ngang hàng Mạng ngang hàng (Peer-to-Peer hay P2P) [1] 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. Các loại ứng dụng thường xuyên gặp nhất là các ứng dụng chia sẻ tập tin, tất cả các dạng như âm thanh, hình ảnh, dữ liệu,... hoặc ứng dụng 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, mỗi máy là một nút mạng (còn gọi là peer) đó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. 1.2. Phân loại mạng ngang hàng 1.2.1. Mạng ngang hàng thuần túy và mạng ngang hàng lai ghép Mạng ngang hàng thuần túy: - Các máy trạm có vai trò vừa là máy chủ vừa là máy khách. - Không có máy chủ trung tâm quản lý mạng. - Không có máy định tuyến (bộ định tuyến) trung tâm. Các máy trạm có khả năng tự định tuyến. Mạng ngang hàng lai ghép: - Có một máy chủ trung tâm dùng để lưu trữ thông tin của các máy trạm và trả lời các truy vấn thông tin này - Các máy trạm có vai trò lưu trữ thông tin, tài nguyên được chia sẻ để cung cấp các thông tin về chia sẻ tài nguyên của nó cho máy chủ. - Sử dụng các trạm định tuyến để xác định đia chỉ IP của các máy trạm 4 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 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ả. 5 Một số mạng ngang hàng có cấu trúc nổi tiếng bao gồm Chord, CAN, Kademlia, Pastry và Tapestry. 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 ☺ 1.3. Ưu thế và các vấn đề cần xem xét trong mạng ngang hàng 1.3.1. Các ưu thế của mạng ngang hàng Các ưu thế của mạng ngang hàng cũng chính là các mục đích ban đầu khi tạo ra mạng ngang hàng người ta nghĩ đến. Mạng ngang hàng là tập hợp liên kết của các máy tính đơn lẻ với nhau và đóng góp tài nguyên (bao gồm dung lượng ổ cứng, băng thông và khả năng tính toán). Do đó, sức mạnh của mạng ngang hàng tăng lên khi số nút tham gia mạng tăng lên(trái với mô hình client/server truyền thống, sức mạnh và hiệu năng của mạng giảm khi số lượng client tham gia vào mạng tăng lên). Một ưu thế khác của mạng ngang hàng so với mô hình client/server truyền thống đó chính là tính chất phân tán. Điều này đảm bảo được tính bền vững của mạng khi có một(hoặc một vài nút) gặp phải sự cố. Mặt khác, do tính chất bền vững của mạng là lớn nên nếu có cơ chế phân phối thông tin hợp lý thì sẽ luôn đảm bảo được tính sẵn sàng cao trong mạng. Một ưu thế đáng được nói đến nữa của mô hình P2P đó chính là chi phí xây dựng hệ thống thấp, do đó việc triển khai một hệ thống mạng cũng khá dễ dàng. 1.3.2. 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. Do đó khi thiết kế và nghiên cứu cần chú ý đến các vấn đề sau: - Tính ổn định và dễ mở rộng của mạng: Làm thế nào để cho các nút có thể tham gia vào mạng một cách dễ dàng nhất có thể, đồng thời cũng phải giữ được tính ổn định của mạng, có nghĩa là mạng vẫn có thể hoạt động bình thường khi có một số nút rời mạng (tự nguyệt hay đột ngột bị lỗi). - Tận dụng tối đa tài nguyên đóng góp của các nút tham gia mạng: Sức mạnh 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. 6 - Đả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. 7 Chương 2. Mạng chia sẻ file ngang hàng BitTorrent 2.1. BitTorrent là gì? BitTorrent là tên một giao thức chia sẻ file được lập trình viên Bram Cohen thiết kế vào tháng 4 năm 2007, và chỉ 3 tháng sau đó, tháng 7 năm 2001, giao thức này đã được đưa vào triển khai trong thực tế và tạo ra một hệ thống chia sẻ file theo mô hình mạng ngang hàng mới, cũng được mang tên là BitTorrent. Ngoài chương trình BitTorrent Client đầu tiên được viết bởi Bram Cohen là BitTorrent (hay Mainline) cũng đã có rất nhiều chương trình BitTorrent Client khác được phát triển và có thể chạy được trên nhiều nền tảng khác nhau (Windows, Mac, Linux,...). Hình 1: Giao diện một chương trình BitTorrent Client Trong hình trên là giao diện của µTorrent, một chương trình BitTorrent Client khá phổ biến. Về cơ bản thì nó cũng khá giống một chương trình hỗ trợ download bình thường. Để 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 đó. Quá trình hoạt động cụ thể của việc chia sẻ file sẽ được nói chi tiết trong phần sau. 8 Một số khái niệm (thuật ngữ) hay được dùng trong BitTorrent: Seed: Nút nắm giữ toàn bộ file, chỉ tham gia quá trình upload file. Peer(or downloader/leecher): Nút tham gia vào cả quá trình download và upload file. Neiborghs (Swarm): Các nút giữ liên kết với một nút nào đó trong quá trình download 1 file nhất định. Tracker: Máy chủ có nhiệm vụ theo dõi và nắm thông tin về các nút nào đang tham gia download file nào. *.torrent: File lưu trữ các thông tin về file chia sẻ, địa chỉ của tracker.. (sẽ nói chi tiết hơn trong phần sau). Piece/chunk/share/block…: Một đơn vị sau khi chia nhỏ file trong BitTorrent. Sự chia sẻ file trong BT được thực hiển bởi sự trao đổi các đơn vị này. 2.2. Cơ chế và hoạt động của BitTorrent 2.2.1. Quá trình chia sẻ file Ý tưởng cơ bản của BitTorrent là chia file thành các phần đơn vị (piece) bằng nhau (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 9 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ể. Ít nhất trước(Local Rarest First): Để quyết định xem piece nào sẽ được chọn, nút sẽ so sánh số lượng của mỗi piece trong tập tất cả các nút đang liên kết với nó(bao gồm cả chính bản thân nút đó) và lựa chọn tải về piece có số lượng ít nhất. Chiến lược này để đảm bảo sự cân bằng của số lượng mỗi piece trong mạng. Một vấn đề nữa là đối với nút đầu tiên tham gia upload file lên mạng (original seed) là làm sao có thể phát tán tất cả các piece của file vào mạng 1 cách nhanh nhất có thể. Khi đó, chiến lược LRF được áp dụng cho seed là, trong các yêu cầu pieces từ các nút kết nối đến nó, nó sẽ ưu tiên phục vụ piece nào có số lượng được phục vụ ít nhất. Đơn vị đầu tiên ngẫu nhiên(Random First Piece): Khi một nút mới gia nhập mạng, nó sẽ chọn ngẫu nhiên 1 piece để tải về. Quy tắc này để khiến cho nút có được mẩu đầu tiên một cách nhanh nhất để bắt đầu upload. Chế độ kết thúc(Endgame Mode): Để giúp nút có thể kết thúc nhanh quá trình download, nút có thể yêu cầu piece cuối từ tất cả các nút liên kết với nó. 10 2.2.3. 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. Nút trong mạng sẽ không đáp ứng tất cả các yêu cầu download các piece từ các nút liên kết với nó, mỗi yêu cầu đó chỉ được đáp ứng khi nút có yêu cầu đảm bảo được những điều kiện nhất định. Quy tắc được đặt ra để nhằm khuyến khích các nút tham gia upload vào mạng nhiều hơn, được gọi là cơ chế thúc đẩy (Incentive Mechanism) của BitTorrent. Thông thường, một nút chỉ đáp ứng yêu cầu của 4 nút hàng xóm cung cấp cho nó tốc độ download cao nhất, và quá trình xác định tốc độ download của các nút liên kết với nó được thực hiện 10 giây một lần. Khi chiến lược này được áp dụng, nút nào có tốc độ upload vào mạng càng cao thì càng có được tốc độ download cao. Chiến lược này gọi là chiến lược ăn miếng trả miếng (Tit-for-tat Strategy). Optimistic Unchoking: Nếu chỉ áp dụng quy tắc như trên sẽ bó hẹp sự trao đổi dữ liệu giữa các nút liên kết với nhau. Để tạo cơ hội tìm kiếm các nút có cung cấp tốc độ download cao hơn cũng như để cho nút mới tham gia vào mạng có thể có được đáp ứng về piece đầu tiên, BitTorrent sử dụng “optimictic unchoke” 30 giây 1 lần. Optimistic unchoke sẽ mở đáp ứng cho một kết nối ngẫu nhiên mà không tính đến tốc độ 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{p0,p1, …, pxn-1, q0,q1, …, qxf-1 } là tập hợp các nút trong mạng BitTorrent. 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. 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à µxn. Gọi u là số lượng kết nối upload của 11 nút trong mạng, trong đó có 1 kết nối là optimistic unchoking. Tốc độ của mỗi kết nối bị giới hạn bởi µ/u. Theo quy tắc Optimistic Unchoking, mỗi nút bình thường sẽ chọn ngẫu nhiên một nút khác để gửi dữ liệu, từ đó tổng số kì vọng tốc độ download của free-rider trong G là: (1) Trong trường hợp xn+xf >> u Từ (1) cho thấy rằng mặc dù không đóng góp cho hệ thống như free-rider vẫn nhận được tốc độ download được tính bởi (1). 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. ta có: (2) Với 0 ≤ ρ ≤ 1. 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. Để rút ra kết luận trên và các đẳng thức (1) và (2), tôi đã tham khảo trong [13]. 2.4. So sánh BitTorrent và một số hệ thống chia sẻ file ngang hàng khác Phương pháp dùng để phân phối tệp giữa mạng eDonkey2000 và BitTorrent là giống nhau, như các máy trong mạng eDonkey thường chia sẻ và tải về rất nhiều tệp, làm cho băng thông cho mỗi vận chuyển trở nên ít hơn. Ngược lại, vận chuyển BitTorrent nhanh hơn nhiều do các máy tập trung vào một tệp hay một nhóm tệp cụ thể. Giao thức eDonkey2000 nguyên thủy cung cấp rất ít khả năng chống free-riding, các phiên bản client mới của eDonkey2000 có cài đặt hệ thống khuyến khích tải lên 12 nhiều hơn. 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. Một máy sẽ ưu tiên các máy vận chuyển cho mình trước đây bằng cách 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. 13 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][10][11] đều cho thấy rằng hệ thống BitTorrent tỏ ra rất hiệu quả trong việc tận dụng tài nguyên hệ thống và hỗ trợ số lượng lớn người sử dụng. Và vấn đề tối ưu hóa hệ thống BitTorrent thường tập trung hơn vào vấn đề đảm bảo tính công bằng trên mạng. Một vài nghiên cứu về “cơ chế thúc đẩy” của BitTorrent được trình bày trong [4][8][9][12]. 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. Jun và Ahamad [8] xem xét hệ thống BitTorrent dưới lý thuyết trò chơi (vấn đề song đề tù nhân lặp lại – Iterated Prisoner’s Dilemma) và cho thấy rằng free-rider không bị trừng phạt thích đáng và những nút đóng góp cho hệ thống cũng không được đền đáp tương ứng. Qiu và Skirant [12] đã mô tả sơ lược ảnh hưởng của optimistic unchoking đối với hiện tượng free-riding, và cho thấy optimistic unchoking có thể dẫn đến hiện tượng free-ring trong hệ thống. Locher và các tác giả khác [9] cũng đã cho thấy trong BitTorrent một nút có thể tải file về thành công mà không có sự đóng góp gì cho mạng. Trong nội dung của khóa luận này, tôi sử dụng mô hình của các tác giả Jiadia Yu, Minglu Li, Jie Wu được giới thiệu trong [13]. 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. 3.2. 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: 14 • xn(t) : 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. Mô hình trên được mở rộng từ mô hình trong [3] và được trình bày trong [4]. 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. Quan hệ giữa các trạng thái được trình bày như hình sau: 15 Hình 2: Mô hình chung biểu diễn 3 trạng thái trong hệ thống chia sẻ file BitTorrent Hình vẽ trên cho ta thấy quan hệ giữa 3 trạng thái, tốc độ các nút tham gia và rời khỏi các trạng thái và thành phần phân phối băng thông của 3 trạng thái trong hệ thống 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. Tham số η biểu thị hiệu quả của việc chia sẻ file và được tính toán là rất gần với 1 trong [8]. 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) + y(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. Áp dụng đẳng thức (2) ta có (3) Với 0 ≤ ρ(t) ≤ 1. Với seed khi upload không phân biệt free-rider hay non free-rider, do đó, tỉ lệ băng thông upload của seed bị chiếm bởi free-rider là: (4) Với 0 ≤ κ(t) ≤ 1. Do đó, tổng tốc độ download của non free-rider là : µ[(1-ρ(t))ηxn(t) + (1-κ(t))y(t)] Và tổng tốc độ download của free-rider là : µ[ρ(t)ηxn(t) + κ(t)y(t)] Tuy nhiên, tốc độ download của free-rider và non free-rider bị giới hạn bởi cxn(t) và cxf(t). Ta có : (5) 16 Trong đó Dn(t) và Df(t) biểu thị tương ứng là tổng tốc độ download của non free- rider và free-rider tại thời điểm t(tốc độ non free-rider và free-rider rời khỏi các trạng thái tương ứng sau khi download xong). θ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. Seed rời bỏ trạng thái với tốc độ γ. Từ đó, tốc độ thay đổi của 3 trạng thái được xác định tương ứng bằng phương trình sau : (6) 3.3. 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. Ở trạng thái ổn định t→∞ ta có : (7) Để đơn giản, chúng ta giả sử nút không bao giờ rời mạng khí chưa download xong (θ =0) và sẽ rời mạng ngay sau khi download hoàn thành (γ→∞). Với giả sử trên, từ (6) và (7) phương trình biểu thị trạng thái ổn định được viết lại thành : (8) Với 17 (9) là giá trị cân bằng của ρ(t) và 0 ≤ ρ ≤ 1 Dễ thấy, với điều kiện thực tế c > µ thì và . Kết hợp với (8) ta thu được : (10) Với và Đị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 : (11) Chứng minh : Trong [12], áp dụng Little Law[3]. Ta có thời gian download trung bình cho một nút ở trạng thái ổn định được xác định bởi: ( )x x x Tλ θ λ θλ − = − Với T là thời gian download trung bình. 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à: 18 Thay tương ứng các giá trị trong các biểu thức (9), (10), 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. Đồng thời, giá trị của Tf cũng tăng rất nhanh khi α tăng lên, ngược lại Tn hầu như không tăng khi giá trị α nhỏ. T hờ i g ia n do w nl oa d tr un g bì nh 19 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. Từ đẳng thức (11) ta cũng thấy một điều rằng có thể tăng thời gian Tf bằng cách tăng số liên kết upload của mỗi nút u, tuy nhiên, điều này khó có thể thực hiện trong thực tế do nếu tăng số lượng kết nối TCP sẽ tăng thời gian trễ và ảnh hưởng đến hiệu năng của mạng. Ở trên, chúng ta đã giả sử γ→∞, 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. Khi có tính đến γ, phương trình biểu diễn trạng thái ổn định của hệ thống được viết lại thành: (12) Trong đó Với ρ và κ là giá trị cân bằng tương ứng của ρ(t) và κ(t), 0 ≤ ρ, κ ≤ 1. Sau khi giải phương trình (12) ta thu được: 20 (13) Khi Ngược lại, nếu tốc độ rời mạng γ của seed nhỏ hơn thì băng thông download c sẽ quyết định hiệu năng của mạng nếu giá trị của c là rất lớn []. Từ đó, ta có: (14) Khi Đị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 : (15) Khi Và (16) 21 Khi Chứng minh: Dễ dàng chứng minh được định lý 2 tương tự như chứng minh định lý 1. Nhận xét: Khi tốc độ rời mạng của seed giảm, đồng nghĩa với việc số lượng seed có trong hệ thống tăng lên, số lượng tài nguyên dành cho các nút download cũng nhiều hơn. 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 γ. Biểu đồ trong hình 4 biểu thị sự thay đổi về tỉ lệ giữa Tn và Tf khi thay đổi giá trị của γ. Ta thấy rằng, tỉ số này tăng lên khi tốc độ rời mạng của seed giảm đi. Và khi γ giảm đến 1 giá trị xác định ( ) 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 T ỉ s ố gi ữa th ời g ia n do w nl oa d tr un g bì nh T n/ T f 22 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ừ đồ thị trên ta cũng thấy được một điều nữa là khi giá trị của α tăng lên, tỉ số giữa Tn và Tf cũng giảm xuống do thời gian download Tf tăng lên tương tự như trong hệ thống không có seed đã xét ở phần trước. 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. 23 Chương 4. Chương trình mô phỏng OctoSim 4.1. Cài đặt và sử dụng chương trình 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 OctoSim : A BitTorrent Simulator là một ứng dụng viết bằng ngôn ngữ C# bởi các tác giả Ashwin Bharambe, Cormac Herley và Venkat Padmanabhan. Mã chương trình được các tác giả viết ra để thực hiện các thử nghiệm trong [4]. Có thể tìm và download chương trình tại địa chỉ trang web của Microsoft Research ( và tìm với từ khóa BitTorrent Simulator). Chương trình mô phỏng lại hệ thống BitTorrent theo các chi tiết sau: File được chia nhỏ thành các pieces, và không thể chia nhỏ hơn nữa, đồng thời, thuật toán Choking của BitTorrent cũng được triển khai một cách chính xác. Tuy nhiên, chế độ kết thúc (EndGame Mode) không được tính đến, tuy nhiên điều này cũng không ảnh hưởng nhiều đến các kết quả thử nghiệm. Để cài đặt và chạy chương trình, trên Linux, cần có mono và mcs (để biên dịch ngôn ngữ C#), trên Windows, sử dụng bộ công cụ lập trình Visual Studio. Để thực hiện các thử nghiệm trong khóa luận này, tôi đã sử dụng Visual Studio 2005 trên hệ điều hành Windows XP để build và chạy chương trình mô phỏng. Cấu hình cần thiết để chạy được chương trình mô phỏng này là máy tính có thể cài và chạy được Visual Studio, tuy nhiên, chương trình sử dụng các hàm tính toán và xử lý khá nhiều sự kiện nên một máy tính có CPU với tốc độ xử lý cao có thể giúp rút ngắn thời gian tiến hành các thử nghiệm. Đối với môi trường Windows, sau khi tải về mã nguồn chương trình từ Microsoft Research (sẽ được 1 file có đuôi là .msi), sau khi bung nén, chúng ta sẽ được một thư mục chứa mọi file liên quan đến chương trình (địa chỉ mặc định khi bung nén của thư mục thường là “C:\Program Files\Microsoft Research\MSR Simulator for the BitTorrent Protocol”, trong đó chúng ta cần chú ý đến 2 thư mục con là OctoSim chứa mã nguồn C# của chương trình và workloads chứa các file mẫu đầu vào của chương trình mô phỏng. 24 4.1.2. Đầu vào và đầu ra của chương trình mô phỏng Về mặt thực thi, OctoSim là một ứng dụng dòng lệnh (Console Application) cho phép nhập các giá trị đầu vào thông qua các tham số dòng lệnh hoặc file text. Các kết quả thử nghiệm được hiện một phần ngay trong cửa sổ Console và kết xuất trong các file text. Bây giờ chúng ta sẽ mô tả ngắn gọn về các file text đầu vào và đầu ra của chương trình. - File đầu vào: Một vài mẫu của file đầu vào có thể tìm thấy trong thư mục workloads. Các file có phần mở rộng là .wl. Trong file này các lệnh được bố trí theo dòng, các dòng bắt đầu bằng # chỉ đó là những dòng chú thích, và chương trình sẽ bỏ qua khi đọc đến những dòng này. Cấu trúc của một dòng bình thường được xử lý bởi chương trình mô phỏng như sau: [end] Có thể hiểu một cách khái quát nội dung của 1 dòng sẽ xác định một sự kiện (một lệnh) được thực hiện vào thời điểm nào trong quá trình mô phỏng. Chi tiết cụ thể sẽ được mô tả kĩ hơn trong phần sau, khi chúng ta nói về nội dung file mã nguồn WorkloadProcessor.cs - File đầu ra: Khi chạy chương trình mô phỏng OctoSim sẽ kết xuất ra 4 file text đầu ra có phần mở rộng lần lượt là .out.prm, .out.nds, .out.bw, .out.gph. Trong đó: File .out.prm lưu thông tin về giá trị của các tham số sử dụng trong chương trình như thời gian tiến hành thử nghiệm, thời gian và tốc độ tham gia vào mạng của các nút, kích cỡ file chia sẻ … File .out.nds có chứa các thông tin chung về các sự kiện xảy ra với các nút. Cấu trúc chung của một dòng trong file này là: [time] [node] [event] Có thể hiểu nội dung của dòng này là thời gian diễn ra sự kiện đối với nút, nút diễn ra sự kiện là nút nào, sự kiện đó là sự kiện gì và các thông tin chi tiết tương ứng với mỗi loại sự kiện. Thông tin chi tiết về từng loại sự kiện đối với 1 nút chúng ta có thể xem thêm trong file Logger.cs File .out.bw, file này chính xác đóng vai trò là file log của hệ thống. Cấu trúc của file chia thành các khối, mỗi khối bắt đầu bằng một dòng có nội dung là “time ”. Các dòng tiếp theo trong khối mô tả một cách vắn tắt về 25 tình trạng của toàn bộ các nút trong mạng tại thời điểm xét, mỗi nút trên 1 dòng, cụ thể, thông tin trên mỗi dòng sẽ là: #d <tổng tốc độ download của các kết nối> #u <tổng tốc độ upload của các kết nối> p s <bit đánh dấu xem nút đang có vai trò là seed hay không> #p <số lượng các nút hàng xóm> <số lượng các kết nối không bị choke> <số lượng các kết nối upload interested> <số lượng các kết nối upload useful> D Muốn biết chi tiết và hiểu hơn các khái niệm, có thể xem trong phương thức Dump của class Node trong file Node.cs. 4.2. Cấu trúc và chức năng của chương trình mô phỏng Tại thư mục được tạo ra sau khi bung nén chương trình, có chứa các thư mục con như sau: + cmu_scripts + exp_scripts + OctoSim + plotscripts + scripts + workloads. Tuy nhiên, khi xem xét và thực thi chương trình ta chỉ cần chú ý và tác động vào các file trong 2 thư mục OctoSim và workloads. Thư mục OctoSim chứa toàn bộ mã nguồn C# của chương trình. Sau đây, chúng ta sẽ mô tả một vài file mã nguồn quan trọng của chương trình 4.2.1. File Main.cs: Chức năng chính của file này là xử lý các tham số dòng lệnh và lưu vào một mảng tĩnh để xử lý sau. Về mặt cấu trúc trong file chứa class MainWrapper là class chứa hàm public static int Main(String[] args) sẽ được gọi đến đầu tiên khi chạy chương trình. Ngoài ra, trong lớp này còn khai báo một mảng tĩnh public static ArrayList cmdline_arguments dùng để lưu giá trị các tham số dòng lệnh. 26 Nhiệm vụ chính trong hàm Main là đọc vào các tham số dòng lệnh, lưu nó vào mảng tĩnh đã được khai báo ở trên (chi tiết các tham số và ý nghĩa của các tham số có thể xem cụ thể trong file mã nguồn), sau đó tạo ra một thực thể new WorkloadProcessor(workload_file) để xử lý file nằm trong thư mục workloads đã nói ở trên. Nội dung chi tiết về WorkloadProcessor sẽ được nêu ngay sau đây. 4.2.2. File WorkloadProcessor.cs: Chức năng của file này là đọc nội dung file workload (*.wl), dịch nội dung các dòng tương ứng thành các chức năng hoặc gán tham số cho chương trình, tạo ra một thực thể Simulator và khởi động vòng lặp để xử lý các sự kiện của chương trình mô phỏng Về mặt cấu trúc, trong nội dung của file mã nguồn chỉ có 3 phương thức: ƒ void ProcessWorkload(string workloadfile): Đọc vào nội dung của file workload theo từng dòng, bỏ qua những dòng nào bắt đầu bằng kí tự ‘#’ (kí tự # để chỉ những dòng đó chỉ là những dòng chú thích), gọi phương thức GetTimeOfJob để lấy ra thời gian lệnh đó được thực hiện và kiểm tra kiểm tra xem thời gian thực hiện lệnh trong nội dung của dòng đó có còn hiệu lực hay không, nếu còn thì gọi đến hàm ProcessJob để thực hiện. ƒ public void ProcessJob(string jobstring):Xử lý nội dung trong từng dòng và thực hiện các chức năng tương ứng với từ khóa. Khi xem nội dung của phương thức này, chúng ta có thể hiểu thêm ý nghĩa của các từ khóa chứa trong file workload, đồng thời cũng biết được cách thức viết một dòng trong file workload sao cho chính xác và phù hợp với ý định của mình. Hai từ không thể thiếu khi viết file workload đó là "process_cmdline_args" dùng để chỉ cho chương trình biết cần xử lý các tham số dòng lệnh (đã được xử lý và lưu bởi hàm Main()), và "initialize" dùng để bắt đầu “chạy” chương trình mô phỏng. Thiếu đi 2 từ khóa này thì chương trình mô phỏng không hoạt động được như ý. Như thế, 2 dòng luôn luôn phải có trong file workload “now process_cmdline_args end” là và “now initialize end” . Ngoài ra còn có từ khóa "setparam" dùng để gán giá trị các tham số của chương trình. Chi tiết hơn có thể xem trong file mã nguồn. Thông tin và ý 27 nghĩa của các tham số trong chương trình sẽ được nêu trong phần mô tả file SimParameter.cs. ƒ private long GetTimeOfJob(string job): Phương thức đọc lấy thời gian thực hiện của mỗi dòng lệnh trong file workload (lấy giá trị đầu tiên từ trái sang phải – chính là giá trị time được mô tả trong cấu trúc file workload đầu vào đã nói ở phần trước). 4.2.3. File Sim.cs: Chứa lớp đại diện cho sự mô phỏng của chương trình, với hàng đợi các sự kiện và xử lý sự theo băng thông. Về mặt cấu trúc, trong file có chứa 2 lớp và một giao diện: public interface TimerEvent: Khai báo mẫu cho một sự kiện được xử lý trong chương trình, để được lưu vào hàng đợi và xử lý, các sự kiện cần tuân theo mẫu này. public class WorkloadGenerator : Tạo ra các thông số môi trường cho các thử nghiệm ( ví dụ như sự phân phối băng thông của các nút, thời gian tham gia và rời khỏi mạng của các nút … tùy thuộc các tham số đầu vào). public class Sim: Đây chính là lớp đại diện cho toàn bộ một chương trình mô phỏng. Trong lớp này cần chú ý đến: ƒ private EventQueue triggers : Cây lưu giữ các sự kiện sẽ được xử lý của chương trình mô phỏng. Khi chương trình chạy sẽ duyệt cây từ gốc và xử lý các sự kiện. ƒ private SortedList nodes : Chứa danh sách toàn bộ các nút tham gia trong hệ thống. ƒ public void RaiseSimulationEvent(long ms, TimerEvent obj): Phương thức thêm một sự kiện vào trong hàng đợi, với đầu vào là nội dung của sự kiện và thời gian diễn ra sự kiện, phương thức này rất quan trọng và được dùng để xây dựng nên hàng đợi của chương trình mô phỏng. ƒ public void AssignBandwidth(Node node): Gán băng thông cho một nút. ƒ public Node CreateNode(): Thêm một nút vào danh sách các nút và gán băng thông cho nút đó (chuẩn bị cho một nút tham gia vào mạng). ƒ public void KillNode(Node node): Xóa đi một nút trong danh sách các nút đã lưu (sử dụng trong trường hợp nút rời khỏi mạng). 28 ƒ public bool ProcessTill: Đây chính là phương thức tạo ra vòng lặp xử lý cho chương trình mô phỏng. Nó sẽ duyệt lần lượt các sự kiện trong hàng đợi và xử lý cho đến khi hết sự kiện hoặc hết thời gian quy định. Trong phương thức còn có chức năng xuất ra màn hình console một số thông tin về tiến trình thực hiện các thử nghiệm ở các thời điểm nhất định. 4.2.4. File ProtocolMain.cs: Chứa các sự kiện và chức năng điều khiển chương trình mô phỏng bằng cách đưa vào những sự kiện thích hợp tại những thời điểm hợp lý Về mặt cấu trúc, trong nội dung file bao gồm các lớp: public class CreateNodeEvent : TimerEvent: Khai báo và xử lý sự kiện tạo ra một nút mới. Sự kiện được gọi đến và xử lý khi có một nút tham gia mạng. public class KillNodeEvent : TimerEvent: Khai báo và xử lý sử kiện hủy bỏ một nút. Được sử dụng khi muốn một nút rời mạng. public class ScheduleSomeJoinsEvent : TimerEvent: Khai báo và xử lý sự kiện lập lịch cho một số nút tham gia vào mạng. public class ProtocolSim: Lớp chính trong file này, định nghĩa các cách thức xảy ra của các sự kiện trong chương trình. Một số phương thức cần chú ý trong lớp này là: ƒ public static void CreateNode(): Tạo ra một nút. ƒ public static void KillNode(Node n): Hủy một nút. ƒ private static void CreateSeeds(int n_seeds): Tạo ra các seed trong thời điểm bắt đầu (initial seeds). ƒ public static void Initialize(): Bắt đầu chương trình mô phỏng. ƒ public static void ScheduleSomeJoins(): Lập lịch cho toàn bộ các nút trong quá trình tham gia vào mạng. Các giá trị được sử dụng trong hàm này được thiết lập thông qua các tham số của chương trình. ƒ public static void SchedulePFCJoins(): lập lịch cho các nút khác tham gia vào mạng. Có thể đọc chi tiết hơn trong phần VIII.A của [4] (phần nói về Post-Flash Crowd), trong khóa luận này, tôi sẽ tận dụng chức năng này để thực hiện các thử nghiệm. 29 4.2.5. File Node.cs: Nội dung của file này được xem là “lõi” của toàn bộ hệ thống, trong file có lớp biểu diễn toàn bộ đời sống của 1 nút từ khi được tạo ra và tham gia vào mạng đến khi rời khỏi hệ thống. Về mặt cấu trúc, trong file có nhiều lớp, nhưng quan trọng nhất vẫn là lớp Node, đó là sự mô phỏng cho mỗi nút tham gia vào hệ thống. và trong lớp này cần chú ý đến: ƒ private LinkCap m_LinkCap : Chứa thông tin về băng thông download và upload của nút. ƒ private Hashtable m_Connections: Chứa toàn bộ kết nối của nút hiện tại đến các nút hàng xóm. ƒ private ArrayList m_Uploads : Chứa danh sách các liên kết đang upload. ƒ private ArrayList m_Downloads : Chứa danh sách các liên kết dang download. ƒ private PieceInfo[] m_PieceInfoArray : Chứa thông tin về toàn bộ các pieces chứa trong nút hiện tại. ƒ private bool m_AmSeed : Cờ để xác định xem nút có phải là seed hay không. ƒ public Node(Sim s, Oracle ora, int n_pieces) : Phương thức khởi tạo, trong này cho ta một cái nhìn tổng quan về một nút, và giá trị các thuộc tính của nút khi được khởi tạo. ƒ public void JoinNetwork() : Phương thức biểu diễn các hành động của một nút khi nó gia nhập vào hệ thống. Và lập lịch cho các hoạt động của nút. ƒ public void BecomeSeed() : 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. ƒ private int FindPieceToDownload(Connection conn): Trong phương thức này có cài đặt quy tắc chọn piece theo Local Rarest First đã nói trong phần cơ chế của BitTorrent. ƒ public float GetTotalDownloadRate(),public float GetTotaluploadRate(): Trả về tốc độ download và upload của nút. ƒ public void Dump(StreamWriter stream): Phương thức xuất ra thông tin về một nút, được sử dụng để ghi vào file output *.out.bw. 30 Ngoài ra còn rất nhiều thuộc tính và phương thức khác, có thể xem trực tiếp trong nội dung file mã nguồn. 4.2.6. File SimParameters.cs Đây là file liệt kê hầu hết các tham số được sử dụng bởi chương trình mô phỏng. Khi tiến hành các thử nghiệm, cần lưu ý nhiều đến file này. Về mặt cấu trúc, trong file có chứa lớp chính là public class SimParameters, trong lớp này có các thuộc tính được dùng làm tham số cho chương trình mô phỏng. Các tham số đã được mô tả khá kĩ trong file mã nguồn, ở đây, ta sẽ liệt kê ra một vài tham số quan trọng: ƒ public static long simulationTime: Tổng thời gian tiến hành một thử nghiệm ƒ 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. ƒ public static int fileSize : Dung lượng của file sử dụng, tính theo kilobit. ƒ public static int blockSize : Độ lớn của mỗi piece, tính theo kilobit. ƒ public static double seedLeavingProbability : Tỉ lệ nút rời mạng sau khi hoàn thành download ( giá trị này luôn nằm trong khoảng từ 0 đến 1). ƒ public static int maxUploads: Số lượng kết nối upload đồng thời của 1 nút. ƒ public static int nInitialSeeds : Số lượng seed trong thời điểm bắt đầu mọi sự kiện, các seed này chính là nguồn cung cấp nội dung file cho toàn bộ hệ thống. 4.2.7. Các file khác Ngoài các file chính ở trên đã nêu, còn có một số file khác trong thư mục mã nguồn như Logger.cs, file này có chức năng chính là tạo ra các file text đầu ra của chương trình hay Choker.cs là file mô phỏng lại chiến lược TFT của BitTorrent … 31 Chương 5. Các thí nghiệm mô phỏng và đánh giá 5.1. Kết luận sau khi xem xét mô hình và đề xuất phương án cải thiện 5.1.1. Kết luận thu được từ quá trình phân tích và tính toán Thông qua nghiên cứu mô hình xây dựng trong chương 3, chúng ta thấy rằng Optimistic Unchoking có khả năng dẫn đến sự mất công bằng trong mạng và hiện tượng free-riding. Đẳ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. 5.1.2. Đề 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. Nguyên nhân của hiện tượng này là do trong cơ chế hiện tại của BitTorrent, seed là nút tự nguyện upload dữ liệu vào mạng, và nó sẽ upload dữ liệu cho một số lượng giới hạn các nút liên kết với nó có tốc độ download về từ nó nhanh nhất mà không phân biệt nút đó là free-rider hay non free-rider. Điều đó gây nên sự mất công bằng đối với các nút non free-rider. Trong khóa luận này, tôi xin đề xuất một thay đổi nhỏ trong cơ chế hiện tại của BitTorrent đối với seed. Đó là, khi chọn lựa nút hàng xóm để upload dữ liệu, seed sẽ xem xét đến sự đóng góp của nút đó trong mạng, với một quy tắc đơn giản là thay vì upload đến một số lượng giới hạn nút có tốc độ download từ nó là nhanh nhất thì nó sẽ 32 upload dữ liệu cho một số lượng giới hạn các nút có tổng tốc độ upload vào hệ thống nhanh nhất, và từ chối upload cho nút có tổng tốc độ upload vào mạng bằng 0. Từ thay đổi nhỏ trên, chúng ta sẽ thấy rằng, trong hệ thống mới, seed sẽ ưu tiên hơn đối với các nút có đóng góp nhiều trong mạng, nút nào có tốc độ upload càng cao thì sẽ có cơ hội được phục vụ trước, như vậy sẽ cải thiện hơn tính công bằng trong mạng. 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. Do hạn chế về thời gian và trình độ, tôi chưa có điều kiện kiểm chứng và đánh giá hiệu quả của phương án thay đổi đã đề xuất ở trên thông qua mô hình các tham số, tuy nhiên, chúng ta sẽ thấy được hiệu quả sau khi thay đổi cơ chế đối với seed trong hệ thống BitTorrent ở chương sau, khi tiến hành thử nghiệm trên mô phỏng. 5.2. Tiến hành các thử nghiệm Trong phần này, chúng ta sẽ tiến hành các thử nghiệm để xác nhận kết quả của định lý 1 và 2 cũng như đề xuất cải thiện nêu ở trên. Để chuẩn bị cho thử nghiệm, chúng ta mở file .sln bằng Visual Studio, và trong các thí nghiệm, sẽ sử dụng file đầu vào là Homog.wl trong thư mục workloads. Để có thể tiến hành được các thí nghiệm đã nêu, tôi đã chỉnh sửa lại chương trình mô phỏng một chút. Đó 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. Và để thực hiện thử nghiệm 3, tôi cũng đã chỉnh sửa lại cơ chế choke đối với seed theo như mô tả trong phần đề xuất phương án cải thiện. 5.2.1. Thử nghiệm thứ nhất A. Mô tả thử nghiệm: Trong thử nghiệm này, chúng ta sẽ kiểm tra để xác nhận lại kết quả của định lý 1. 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. 33 B. Thiết lập các tham số - File size: 50MB - Block(piece) size: 256KB - #initial seed: 1 - Seed leaving probability: 1 - 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. Kết quả thu đượ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- 34 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ể. Kết quả của thí nghiệm trong hình 5 thấy có sự tương ứng với biểu đồ lý thuyết thu được trong hình 3. Đ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. 5.2.2. Thử nghiệm thứ hai A. 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. Và thay đổi tham số seed leaving probability (giá trị của tham số này là từ 0 đến 1, tương ứng với tỉ lệ số non free-rider rời khỏi hệ thống sau khi hoàn thành quá trình download, giá trị này bằng 1 có nghĩa là tất cả non free-rider đều rời hệ thống sau khi download hoàn thành, giá trị này bằng 0 có nghĩa là tất cả non free-rider sẽ ở lại hệ thống và trở thành seed sau khi hoàn thành quá trình download). B. Thiết lập các tham số - File size: 50MB - Block(piece) size: 256KB - #initial seed: 1 - Seed leaving probability: Nhận các giá trị 1, 0.975, 0.95, 0.8, 0.5, 0.2, 0 - Non free-rider join rate: 100/s - Free rider join rate: 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. Kết quả thu được 35 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. 36 5.2.3. Thử nghiệm thứ ba A. Mô tả thử nghiệm Trong thử nghiệm thứ 3 này, chúng ta sẽ tiến hành xem xét hiệu của của đề xuất cải tiến của tôi đã nêu trong chương 4. Các tham số được thiết lập tương tự như trong thử nghiệm 2. Tuy nhiên, có sự thay đổi trong cơ chế của seed B. Thiết lập các tham số - File size: 50MB - Block(piece) size: 256KB - #initial seed: 1 - Seed leaving probability: Nhận các giá trị 1, 0.975, 0.95, 0.8, 0.5, 0.2, 0 - Non free-rider join rate: 100/s - Free rider join rate: 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. Kết quả thu được Hình 7: Thời gian download trung bình của free-rider trong cơ chế cũ và mới 37 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. Với tỉ lệ rời mạng của non free-rider là 0.975 thì chỉ có 41 nút hoàn thành được quá trình download, và với tỉ lệ là 0.95 thì có 57 nút hoàn thành download. 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). Điều đó chứng tỏ đề xuất cải thiện được nêu trong chương 4 cũng đạt được những hiệu quả nhất định. 38 Chương 6. Kết luận và phương hướng tiếp theo Trong nội dung của khóa luận, tôi đã giới thiệu tổng quan về mô hình mạng ngang hàng và tập trung vào tìm hiểu cơ chế và cách thức hoạt động của hệ thống chia sẻ file ngang hàng BitTorrent, hệ thống chia sẻ file lớn và phổ biến nhất hiện nay. 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. Tuy nhiên, các tính toán cũng đã chỉ ra được cơ chế thúc đẩy của BitTorrent có khả năng hạn chế hiệu quả hiện tượng free-riding trong môi trường không có seed, tuy nhiên, cơ chế đó lại không thành công khi hệ thống có nhiều seed. Dựa trên kết luận trên, tôi đã đề xuất một cải tiến nhỏ giúp cho hệ thống BitTorrent hoạt động hiệu quả hơn trong việc hạn chế hiện tượng free-riding. Các thử nghiệm trên chương trình mô phỏng đã chứng minh tính đúng đắn của những kết luận thu được từ quá trình tính toán lý thuyết. Kết quả của thử nghiệm 3 cho thấy đề xuất cải tiến đã có những hiệu quả nhất định, tuy nhiên, kết quả đó vẫn chưa đạt yêu cầu như mong muốn. Đề 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. Tuy nhiên, những kết quả nghiên cứu mới chỉ dừng lại ở góc độ lý thuyết và mô phỏng, và với hạn chế về thời gian và trình độ, rất có thể nghiên cứu của tôi gặp phải những sai sót. Vấn đề đảm bảo tính công bằng trên mạng chia sẻ file ngang hàng, đặc biệt là làm sao hạn chế hiệu quả hiện tượng free-riding luông là vấn đề quan trọng vì nó thúc đẩy người dùng tham gia đóng góp cho hệ thống, nâng cao tính bền vững và hiệu quả của hệ thống. Trong tương lai, nếu có điều kiện tôi sẽ tiếp tục nghiên cứu để có được những kiến thức sâu hơn về hệ thống chia sẻ file ngang hàng BitTorrent, từ đó có thể đề xuất được những cải tiến giá trị và hiệu quả hơn. Xa hơn nữa, có thể tìm hiểu và viết ứng dụng BitTorrent Client thực sự để những cải tiến có thể được đưa vào ứng dụng trong thực tế. 39 Tài liệu tham khảo [1] [2] [3] D.Bertsekas and R. Gallager, “Data Networks”, Prentice Hall, Englewood Cliffs NJ 1987. [4] A.R. Bharambe, C. Herley, and V.N. Padmanabhan, “Analyzing and Improving a BitTorrent’s Performance Mechanism”, Infocom 2006. [5] Bram Cohen, “ Incentives Build Robustness in BitTorrent”, 2003. [6] L. Guo, S. Chen, Z. Xiao, E. Tan, X. Ding, and X. Zhang, “Measurements, Analysis, and Modeling of BitTorrent-like Systems,” Proc. Internet Measurement Conference (IMC) , Berkeley, CA,October 2005. [7] M. Izal, G. Urvoy-Keller, E. Biersack, P. Felber, A. Hamra, and L. Garces-Erice, “Dissecting BitTorrent: five months in a torrents lifetime,” Proc. Passive and Active Measurements, Antibes Juan-les-Pins, France, April 2004. [8] S. Jun, andM. Ahamad, “Incentives in BitTorrent Induce Free Riding,” Proc. the ACMSIGCOMM Workshop on Economics of Peer-to-Peer Systems (P2PECON), ACM Press, Aug. 2005. [9] T. Locher, Patrick Moor, S. Schmid, R. Wattenhofer, “Free-riding in BitTorrent is cheap”, 2006. [10] J. A. Pouwelse, P.Garbacki, D. H. J. Epema, and H. J. Sips, “A Measurement Study of the BitTorrent Peer-to-Peer File-Sharing System,” Technical Report PDS- 2004-003, Delft University of Technology, The Netherlands, April 2004. [11] J. A. Pouwelse, P. Garbacki, D. H. J. Epema, and H. J. Sips, “The BitTorrent P2P File-Sharing System: Measurements and Analysis,” Proc. Fourth International Workshop on Peer-to-Peer Systems (IPTPS), February 2005. [12] D. Qiu and R. Srikant, “Modeling and Performance Analysis of BitTorrent-like Peer-to-Peer Networks,” SIGCOMM, Sep. 2004. [13] Jiadia Yu, Minglu Li, Jie Wu, “Free-Riding on BitTorrent-like File Sharing System: Modeling, Analysis and Improvement” IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 19, pages 954-966. [14] Nguyễn Ngọc Hà. Nghiên cứu mô phỏng các tham số ảnh hưởng tới hiệu năng của mạng BitTorrent. Khóa luận Tốt nghiệp Đại học, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội, 2008.