Đề tài 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