Luận văn Đảm bảo công bằng trong các ứng dụng cộng tác ngang hàng

ấn đề tài chính, danh tiếng, lợi ích,… của các đối tượng này. 3.2. Bài toán 3.2.1. Đặt vấn đề Khi một ứng dụng B (có thể là các peer) có nhu cầu truy cập (lấy hoặc chia sẻ tài nguyên hệ thống) tại một nút mạng A nào đó thì sẽ được xem xét để đảm bảo tính tin cậy, hợp pháp đối với nút mạng A. Ngoài ra khi nhiều ứng dụng cùng có nhu cầu lấy tài nguyên tại một nút thì cần phải phân quyền ưu tiên, và nếu ứng dụng nào đã chia sẻ nhiều tài nguyên hơn trong hệ thống cộng tác thì sẽ được quyền ưu tiên cao hơn trong truy cập giành tài nguyên của hệ thống. Để thỏa được điều này, giải pháp đề xuất là nút ứng dụng cấp phát tài nguyên (nút A) sẽ kiểm tra các ứng dụng (các peer-nút B) cần lấy hoặc chia sẻ tài nguyên. Nếu B muốn lấy tài nguyên thì A sẽ kiểm tra B thông qua tổng giá trị các cookie (số điểm như trong cách tính của Website thương mại) có được của mỗi ứng dụng (mỗi peer). Số các cookie này ở mỗi ứng dụng có được khi ứng dụng đó chia sẻ tài nguyên. Trường hợp B muốn chia sẻ tài nguyên thì A và B sẽ thực hiện giao dịch về chia sẻ tài nguyên. Rõ ràng nếu một ứng dụng càng -40- chia sẻ nhiều tài nguyên thì số cookie (và tương ứng tổng giá trị các cookie) mà ứng dụng này có được sẽ càng lớn, và như vậy quyền truy cập, ưu tiên của ứng dụng này sẽ càng cao. Ví dụ về việc một ứng dụng (hoặc người sử dụng) chia sẻ tài nguyên để được tính điểm vào hệ thống có thể được tiến hành như ở một số các Website như sau: nếu muốn tải một tài liệu của Website thì số điểm của người đó phải ở một mức tối thiểu nào đó. Trong trường hợp không đủ điểm để download tài liệu, thì người sử dụng phải thêm số điểm vào tài khoản của mình trên Website bằng cách upload tài liệu của mình lên Website hoặc nạp tiền vào tài khoản của mình trên Website đó. Càng upload nhiều tài liệu (hoặc nạp nhiều tiền vào tài khoản Website) thì sẽ càng có nhiều điểm trong tài khoản của mình trên Website đó. Thường thì khi upload một tài liệu, tài khoản của người upload sẽ được cộng thêm một số điểm, hoặc gửi một tin nhắn theo cú pháp của Website qui định thì được cộng thêm một số điểm (như đã mô tả trong phần 3.2 trên). Ví dụ trên được áp dụng trong mô hình mạng Client/Server. Trong mạng P2P cũng có thể áp dụng vì mỗi máy vừa đóng vai trò Client, vừa đóng vai trò Server. 3.2.2. Bài toán Sau đây là bài toán và giải thuật tương ứng đảm bảo công bằng cho các ứng dụng cộng tác ngang hàng: a) Input: Tập các node (peer) chia sẻ tài nguyên b) Output: - Xác định các node (các peer) cần cộng tác (lấy/chia sẻ) tài nguyên với các node khác. - Kiểm tra độ tin cậy của các peer, tính giá trị tin cậy mỗi peer. c) Giải thuật kiểm tra và tính giá trị tin cậy các peer: i) Kiểm tra trực tiếp tài khoản của peer cần cộng tác (kí hiệu là B) trong cơ sở dữ liệu của máy chia sẻ tài nguyên (kí hiệu là A): i1- Nếu đúng (bao gồm user name và password) thì kiểm tra giá trị tài khoản (là tổng điểm) của B. -41- - Nếu muốn download thì kiểm tra ngưỡng download (so sánh giá trị tài khoản với mức giá trị tối thiểu được phép download). Nếu thỏa ngưỡng download thì xếp hạng thứ tự từ cao xuống thấp về giá trị tài khoản với những peer khác cùng muốn download, thực hiện thủ tục giao dịch dựa trên cookie (phần 3.3.2) và kết thúc. Nếu không thỏa thì thông báo không đủ điều kiện, ra đề nghị (nếu cần) và kết thúc. - Nếu muốn chia sẻ tài nguyên thì thực hiện thủ tục giao dịch dựa trên cookie (phần 3.3.2) và kết thúc. i2- Nếu sai (chưa tồn tại tài khoản trực tiếp) thì sang bước ii. ii) Kiểm tra B qua hàng xóm - Nếu tìm thấy thì thực hiện bước i1. - Nếu không tìm thấy thì thông báo không đủ điều kiện, ra đề nghị (nếu cần) và kết thúc. 3.3.3. Đánh giá thuật toán Chứng minh thuật toán trên hội đủ các tính chất của thuật toán - Đầu vào: Tập các node (peer) chia sẻ tài nguyên - Đầu ra: - Xác định các node (các peer) cần cộng tác (lấy/chia sẻ tài nguyên) với các node khác. Kiểm tra độ tin cậy của các peer, tính giá trị tin cậy mỗi peer. - Tính xác định và khả thi: thuật toán có các bước kiểm tra tài khoản và giá trị tài khoản có sử dụng vòng lặp hữu hạn (vì số nút hữu hạn) và các phép so sánh  các bước đều được xác định chính xác và có thể thi hành. - Tính hữu hạn: thuật toán luôn luôn kết thúc sau khi tất cả các nút được kiểm tra - Tính hiệu quả: thuật toán luôn kết thúc trong 1 khoảng thời gian hữu hạn. - Tính phổ dụng: có thể áp dụng thuật toán này tìm nút bất kỳ trong dãy các nút. 3.3.4. Độ phức tạp của thuật toán -42- Về thời gian: Trong thuật toán này, ta thấy phép toán tích cực là phép tìm kiếm. Tùy thuộc vào cơ sở dữ liệu lưu tại mỗi nút và phương pháp sắp xếp, tìm kiếm mà thời gian thực hiện của chương trình dài hay ngắn. Trường hợp tốt nhất là tìm kiếm trực tiếp tại cơ sở dữ liệu của nút chia sẻ dữ liệu (nút A). Trường hợp xấu nhất là phải tìm trong lân cận hàng xóm, đồng thời phải sử dụng phép toán so sánh khóa và thông qua máy tin cậy AH(C) trong giao dịch tin cậy dựa trên cookie (phần 3.3.2). Nếu cơ sở dữ liệu có n bản ghi (tại nút A và hàng xóm), đồng thời sử dụng giao dịch tin cậy dựa trên cookie ,thì độ phức tạp của thuật toán cỡ n*n*n hay n3. 3.3.5. Các ví dụ mô phỏng thuật toán Ví dụ 1: Giao dịch qua thẻ ATM Một khách hàng (A) sử dụng thẻ ATM của ngân hàng X rút tiền qua case ATM của ngân hàng Y. Tại case giao dịch Y: - A cho thẻ vào ATM - Y kiểm tra tài khoản A (tìm kiếm) qua ngân hàng của Y, sau đó qua hàng xóm X. - Tìm thấy, Y đề nghị A nhập password (thỏa thuận giao dịch). - A nhập mật khẩu. - Y kiểm tra A qua hàng xóm X. Nếu sai thì ra thông báo và đề nghị làm lại (thỏa thuận giao dịch), nếu vẫn sai thì hủy giao dịch, nếu đúng sang bước kế tiếp. - Y yêu cầu A nhập số tiền cần rút - A nhập số tiền - Y kiểm tra số tiền trong tài khoản của A qua người nắm giữ tài khoản của A (là X). Nếu số tiền A nhập để rút vượt quá số tiền trong tài khoản của A có (sau khi trừ phí dịch vụ và số dư tài khoản của A), thì Y ra thông báo đề nghị A nhập lại, trường hợp ngược lại chuyển sang bước tiếp theo. - Y trả tiền cho A (Y cung cấp dịch vụ) và trừ vào tài khoản của A. Y giữ phần trừ này để giao dịch với X. -43- - Quá trình A nhập tiền và Y phục vụ diễn ra cho đến khi A không còn tiền để rút hoặc thỏa thuận với Y ngừng cung cấp dịch vụ thì chấm dứt. Ví dụ 2: Trường hợp gọi điện thoại khác mạng cũng diễn ra tương tự. Trong phần tiếp theo sẽ trình bày giao dịch dựa trên cookie cho các ứng dụng trong giao dịch cộng tác với nhau và kiểm tra tính tin cậy của các cookie của một peer đối với peer chia sẻ tài nguyên. 3.3. Giao dịch dựa trên cookie 3.3.1. Cấu trúc của một cookie [6] 5 trường thông tin đầu tiên: - Issuing date and time (tính theo mili giây) cùng với Serial Number và Owner ID: cung cấp định danh duy nhất của cookie. Đây là yêu cầu nhằm phát hiện cookie trùng lặp. - Account ID: dùng để xác định một cookie minh bạch cho một ứng dụng xác định. Đây là trường lựa chọn. - Signature SK: là chữ kí thông tin được chứa trong 4 trường trên, được kí với khóa riêng của hệ thống, nhằm ngăn sự giả mạo. 3 trường tiếp theo (Transaction Data): Ngày giao dịch, đối tượng tham gia giao dịch và thông tin chất lượng dịch vụ giao dịch. 2 trường cuối: Định danh nhà cung cấp dịch vụ và chữ kí chủ sở hữu nhằm tránh cookie bị đánh cắp. 3.3.2. Giao dịch [6] Trong các giao dịch, hệ thống kiểm soát dựa vào cookie sẽ kiểm soát việc sử dụng tài nguyên, dịch vụ hoặc kết hợp cả hai. Sử dụng dịch vụ được đánh giá cao hơn sử dụng tài nguyên. Một cookie có thể chứa thông tin về các tài nguyên được sử dụng và thông tin giá trị của dịch vụ chính nó. -44- Thông tin được thêm vào cookie trước khi nó được gửi tới nhà cung cấp dịch vụ. Bằng cách này, thông tin chứa trong cookie có thể được sử dụng làm cơ sở cho các cơ cấu thanh toán mở rộng. a) Giao dịch chuẩn (1) Người tiêu thụ dịch vụ C yêu cầu dịch vụ (2) Người cung cấp dịch vụ P thông báo cho C về các điều khoản và điều kiện của dịch vụ, bao gồm số cookie của dịch vụ mà nó chờ nhận lại. Nếu C chấp thuận các điều trên thì phase quá trình cung cấp dịch vụ bắt đầu được tiến hành. + Cookie có thể được vận chuyển trước, sau hoặc trong quá trình cung cấp dịch vụ. + Trước khi 1 cookie được vận chuyển, C điền thông tin kiểm soát yêu cầu. C không khuyến khích làm giả thông tin này vì nó chỉ ảnh hưởng tới cookie trao đổi của P (3) C kí vào cookie với khóa riêng thuộc sở hữu của nó và gửi tới P. (4) P sử dụng khóa chung của C kiểm tra chữ kí của cookie nhận được. Chữ kí có thể là định danh chủ sở hữu hoặc yêu cầu dịch vụ. Vì vậy P có thể sửa đổi được thông tin này. + P có thể ngừng cung cấp dịch vụ nếu phát hiện dữ liệu kiểm soát sai. + Các thành phần cùng tham gia giao dịch có thể cố gắng thu các cookie bằng cách không thanh toán các cookie sau khi nhận một dịch vụ hoặc bằng cách không phân phát dịch vụ sau khi nhận các cookie. => Để tránh các giao dịch đó có thể dùng cách phân chia thành phần -45- (5) C gửi một cookie được kí tới P sau khi P đã phân phát một thành phần của dịch vụ. Ví dụ: C gửi mỗi cookie sau mỗi Mbytes dữ liệu nhận được từ 5 Mbytes vận chuyển file. b) Giao dịch tin cậy Trong khi thực hiện các giao dịch thì giao dịch sau cùng thường có động cơ gian lận đối với các giao dịch khác. Thường thì giao dịch sau cùng vẫn nhận được đầy đủ các lợi ích, nhưng không chịu phân phát các thành phần của nó. Thủ tục sau đây sẽ hạn chế động cơ gian lận đó: (1) C gửi yêu cầu dịch vụ cho P (2) P nhận yêu cầu và gửi lại C các điều kiện và điều khoản của giao dịch, bao gồm số lượng các cookie được yêu cầu. (3) C trả lời với các định danh của cookie được dùng và gửi các cookie tới giao dịch. (4) P liên hệ với máy tin cậy AH(C), là máy chịu trách nhiệm nắm giữ tài khoản của C, để kiểm tra tính hiệu lực của các cookie mà C gửi (5) Máy AH(C) đóng dấu vào danh sách cookie với nhãn “planned to spend”. Những cookie này không có hiệu lực trong các giao dịch khác (6) Nếu tất cả các cookie có hiệu lực, P thông báo C rằng phase giao dịch có thể bắt đầu. -46- (7) C bắt đầu giao dịch bằng việc gửi các cookie chưa đánh dấu tới P. Lúc này C không còn cookie và không kí được nữa, nhưng P cũng không thể thay đổi cookie để sở hữu cho mình vì P không muốn cung cấp thêm dịch vụ. (8) P cung cấp các dịch vụ chấp nhận được. (9) Nếu C quên không gửi các cookie đã kí thì P có thể đề nghị các cookie chưa kí tới AH(C). Thủ tục chứng tỏ khi giao dịch bắt đầu thì các cookie cũng rời khỏi danh sách và C bị mất cookie. Phần thêm trong tiêu thụ kép có thể không bị phát hiện, nhưng bị vô hiệu hóa. Hệ thống danh tiếng đã nói ở trên có thể cung cấp nhiều hơn nữa khả năng chống lại các hành vi hiểm độc. c) Chấm dứt giao dịch Khi hai máy thỏa thuận muốn chấm dứt giao dịch, C không mất các cookie của mình, P thông báo tới AH(C) để xóa nhãn đánh dấu “planned to spend” được đánh dấu trong danh sách cookie. 3.4. Kiểm tra tính tin cậy của các cookie Để có thể đảm bảo được tính tin cậy của cookie trong mỗi giao dịch thì cần đảm bảo các điều kiện sau đây: a) Những người sử dụng hệ thống dựa vào cookie đều có định danh rõ ràng và không đổi. Điều này có thể thực hiện được bằng cách: + Qua sự xác minh cặp khóa riêng/khóa công cộng. Hiện nay có thể sử dụng phần mềm trong việc tạo ra cặp khóa theo chuẩn RSA, một trong những phần mềm nổi tiếng đó là PGP. Ở Việt Nam cho đến thời điểm này Bộ Công thương là chủ quản qui định về vấn đề đăng kí, sử dụng, giải quyết các vấn đề về sử dụng chữ kí số theo chuẩn RSA. + Qua chứng thực được phát ra từ một ủy quyền b) Có một máy danh tiếng trong hệ thống P2P: + Phát hiện được các hành vi gian lận mà các máy kĩ thuật không thể phát hiện được. + Gán một giá trị danh tiếng cho mỗi máy để đại diện tính tin cậy của máy đó như sau: Mỗi máy phát ra các nhãn cá nhân dùng để giao dịch với các -47- máy khác. Nếu máy A yêu cầu một dịch vụ từ máy B, máy A sẽ trả lại cho máy B một số các nhãn của máy B. Trong kiểu giao dịch này không có sự giới hạn việc một máy được phép phát ra bao nhiêu nhãn. Tuy nhiên nếu phát ra quá nhiều nhãn thì trong sự so sánh các dịch vụ được trả giá của nó, các nhãn sẽ không có giá trị, đồng thời các máy sẽ khó khăn trong việc kiếm được các nhãn khác, theo lí các nút sẽ không mong muốn tậu các nhãn của nó (càng nhiều nhãn thì càng phải cung cấp nhiều dịch vụ). + Theo cách này, giao thức các nhãn kết hợp 1 đồng tiền ảo và 1 máy danh tiếng. Có 3 giao thức cơ bản của hệ thống kiểm soát dựa trên cookie: Thu nạp cookie, kiểm tra tiêu thụ kép và thanh toán. 3.4.1. Thu nạp cookie Xử lí thu nạp cookie là thay đổi các cookie ngoài mà một máy tập hợp được thành những cookie mới được phát hành bởi máy đó. Việc này tựa như các ngân hàng ủy quyền thanh toán cho khách hàng của mình thông qua các giao dịch không cùng ngân hàng, khi một khách hàng chuyển/rút tiền tài khoản của mình (tài khoản thuộc ngân hàng A) qua tài khoản khác (thuộc ngân hàng B), chẳng hạn tại các cây ATM. Có 8 bước của thủ tục thu nạp cookie: -48- (1): Máy thay đổi EP xác định một máy tin cậy TP. Các máy tin cậy có đủ tư cách để thay đổi các cookie và xử lí thành phần của khóa riêng của hệ thống. (2): Máy EP gửi tập N các cookie ngoài (Fn1, Fn2, …, FnN) được nó tập hợp tới máy TP. Máy TP kiểm tra các cookie ngoài theo sự hợp lệ của nó. Chỉ những cookie được kí bởi người chủ và tiêu thụ chỉ một lần là có hiệu lực thay đổi. (3): Máy TP sử dụng hàm thu nạp M=A (Fn1, Fn2, …, FnN) tính toán M cookie mới máy EP phải nhận lại đối với các cookie ngoài. Đó là M cookie chưa được kí (Un1, Un2, …, UnM). Hàm thu nạp M là tổng quát và có thể thi hành đối với form bất kì. (4): Máy TP xác định các máy tin cậy ở xa. Lúc này máy EP không được phép chọn các máy đại diện tin cậy nữa, nhằm giảm sự gian lận cộng tác tiềm tàng. Số các máy tin cậy được yêu cầu để kí một cookie được xác định bằng việc sử dụng sơ đồ chia sẻ bí mật. Độ tin cậy của hệ thống tăng tỉ lệ với kích cỡ số các máy tin cậy. (5): Máy TP gửi các cookie mới tới các máy tin cậy này. (6): Mỗi máy tin cậy mới này kí các cookie bằng khóa riêng của hệ thống của nó. (7): Các cookie (Pn1, Pn2, …, PnM) được vận chuyển ngược trở lại máy EP. (8): Kết thúc, máy EP tổ chức các cookie riêng thành các cookie mới (Tn1, Tn2, …, TnM) Tính chất quan trọng của hàm thu nạp làm tăng thêm độ tự do trong hệ thống. Với một hàm thu nạp thích hợp, các hệ thống kinh tế đặc trưng có thể được vận hành. 3.4.2. Kiểm tra tiêu thụ kép - Điều kiện kiểm tra: Cookie phải có định danh rõ ràng - Kiểm tra như sau: -49- + Mỗi máy có một tập các máy nắm giữ tài khoản được tổ chức theo bảng băm phân tán (DHT), ví dụ như bảng băm Pastry. + Các máy nắm giữ tài khoản nắm giữ một danh sách các cookie hiện tại được phát hành tới người sở hữu tài khoản. Danh sách được điền thêm thông tin yêu cầu trong khi thu nạp cookie. + Sau khi một cookie mới được tạo (bước 3-thu nạp cookie), máy TP gửi danh sách các cookie mới này tới các máy nắm giữ tài khoản (EP) (bước 3-kiểm tra cookie). + Trong khi cookie được kiểm tra tính hiệu lực (theo thủ tục thu nạp cookie), máy TP sẽ yêu cầu các máy nắm giữ tài khoản chịu trách nhiệm đối với cookie, nếu cookie có hiệu lực (bước 2-kiểm tra cookie). + Các máy nắm giữ tài khoản sẽ di rời cookie từ danh sách. Nếu cookie không ở trong danh sách, nó là một cookie không có hiệu lực. Máy TP sẽ hủy bỏ cookie và cơ cấu danh tiếng sẽ được thông báo về tình trạng này. - Tránh thông báo lừa lọc + Thông báo gửi đến máy nắm giữ tài khoản phải được kí với khóa riêng của người gửi. - Giữ danh sách nhất quán giữa các máy nắm giữ tài khoản -50- + Tất cả những máy nắm giữ tài khoản đối với một tài khoản xác định thực hiện trao đổi danh sách bất cứ khi nào tập các máy nắm giữ tài khoản thay đổi. + Thay đổi tập nắm giữ này chỉ khi các máy của tập này kết nối hoặc rời khỏi hệ thống. Kiểm tra nhất quán chỉ cần thiết nếu người gửi không nhận được tất cả các thông báo xác nhận. 3.4.3. Đánh giá về an toàn và tin cậy  Mục đích - Làm cho việc sử dụng cơ cấu kiểm soát để cung cấp thông tin được chính xác. - Hệ thống dựa trên cookie được thiết kế để cung cấp độ tin cậy ở mức cao đối với các hệ thống phân tán.  Sự ăn cướp - Các cookie được thiết kế để thích nghi với sự ăn cướp. + Các cookie chứa định danh của chủ sở hữu và không thể thay đổi được khi bị phát hiện bên ngoài nhờ chữ kí hệ thống. + Các cookie tiêu thụ chứa người nhận cookie, được bảo mật nhờ chữ kí của người sở hữu.  Sự giả mạo - Cookie phải chắc chắn chỉ được người chủ hoặc ủy quyền phát hành tạo ra và phải được kí bởi khóa riêng của nó. - Chữ kí hệ thống trong mỗi một cookie là cơ sở đảm bảo dữ liệu của cookie không bị thay đổi và các máy khác không thể tạo được các cookie như vậy. + Chữ kí hệ thống ngăn cản giả mạo và quyết định độ tin cậy của hệ thống. + Cũng cần tránh sự cố ý lừa gạt.  Tiêu thụ kép - Việc xác định tiêu thụ kép dựa vào việc nắm giữ dữ liệu ở những máy nắm giữ tài khoản. -51- - Người sử dụng có thể làm sai lệch danh sách cookie của họ ở máy nắm giữ tài khoản hoặc di chuyển các cookie từ danh sách cookie của những máy khác. Điều này tránh được vì: - Ngăn không cho phép các máy gửi bất kì truy vấn hoặc đòi hỏi nào tới danh sách tài khoản. - Các vi phạm luật được báo cáo tới máy danh tiếng của hệ thống. - Bằng thủ tục thu nạp cookie. - Trường date and time được tạo theo mili giây và là số tuần tự ngẫu nhiên, rất khó đoán được chính xác. - Các hệ thống dựa trên cookie lưu trữ các cookie cục bộ (tự backup, luôn nghĩ tiêu thụ kép bị phát hiện). - Cookie phải được nhận biết rõ ràng: có định danh duy nhất, có thông tin kiểm soát như trong cookie có quy định về tên, loại ứng dụng, dung lượng ứng dụng chia sẻ,… - Có cơ cấu xây dựng trong hệ thống kiểm soát để kiểm tra. 3.5. Áp dụng mô hình tin cậy NICE đảm bảo công bằng trong ứng dụng chia sẻ file BitTorrent 3.5.1. Giới thiệu về BitTorrent 3.5.1.1. Tổng quan về BitTorrent BitTorrent là một mạng chia sẻ file được sáng lập bởi Bram Cohen. BitTorrent là một ứng dụng P2P với mục đích phân phối các file có dung lượng lớn nhanh và hiệu quả qua việc upload băng thông của các máy (peer) khi các máy này download dữ liệu. Nền tảng của vấn đề là phân chia các file thành các block có kích thước như nhau (mỗi block chiếm khoảng 32 đến 256 kbs) để các máy download đồng thời các block từ nhiều máy. Các block ở xa được chia nhỏ hơn để có thể sử dụng đường ống (pipelining) theo các yêu cầu. Giả sử bạn có 1 file dung lượng 1GB và 300 người cần, sẽ cần rất nhiều thời gian để chia sẻ 300GB dữ liệu. Nhưng nếu bạn chia file thành các mảnh nhỏ gửi cho mọi người và họ lại chia sẻ các mảnh đó cho người khác cho đến khi ai ai cũng có file hoàn chỉnh thì sẽ nhanh hơn rất nhiều. Các trang web lớn có thể sử dụng BitTorrent để cập nhật cho các phần mềm của họ, bằng cách này họ sẽ giảm được chi phí trả cho băng thông. Tốc độ của BitTorrent rất đáng kinh ngạc, chỉ mất vài giờ để truyền tải các file cực kỳ lớn. Một vài trang web đã ra đời dựa theo công nghệ này phân phát các nội dung có bản quyền. Ngay lập tức, các tổ -52- chức như MPAA đã đổ lỗi cho công nghệ này, điều đó hoàn toàn sai, thực tế lỗi là ở các cá nhân sử dụng công nghệ cho mục đích trái phép. Dù thế nào đi nữa, BitTorrent không phải sinh ra để phát tán tài nguyên bất hợp pháp, nó là một phát minh của Bram để giúp cho việc truyền tải trở nên nhanh hơn trong thế giới mạng. Nó được sử dụng trên các trang web trên khắp thể giới và Bram tự hào về điều này. 3.5.1.2. Các khái niệm và hoạt động của BitTorrent: Torrent: Mỗi một file lớn có hiệu lực download được gọi là một torrent. Thường thì torrent là một file mang phần mở rộng .torrent nhận từ server. File .torrent này chứa thông tin về dữ liệu muốn down (chứ không phải là bản thân dữ liệu đó). User có thể save file .torrent đó trên máy của mình, sau đó mở nó bằng trình BitTorrent để tiến hành việc download. Hoặc, bạn có thể down ngay bằng cách click thẳng vào link trên trang web - cách này mất thêm chút công sức nếu muốn down lại file đó sau này. BitTorrent không giống các mạng P2P khác như là eD2K hoặc FastTrack, bạn không thể search được file A bằng cách sử dụng các chương trình BitTorrent. Thay vào đó bạn phải vào các trang web có danh sách các file Torrent. Các file Torrent này chứa các thông tin về file A mà bạn muốn download và chứa thông tin về các “tracker” mà bạn phải kết nối để bắt đầu download. Các “tracker” là các máy chủ trung tâm, nó lưu giữ thông tin về từng người đang chia sẻ các file A, và các phần mà họ có. Khi bạn download file Torrent, và open nó, chương trình BitTorrent (như là. Bit Torrent, Bit Tornado, Azureus, ...vvv.) sẽ chạy và kết nối đến các tracker. Tracker sẽ kết nối bạn đến Seeds và Peers – những người đang chia sẻ file A này và quá trình download của bạn sẽ bắt đầu. Đến khi bạn có ít nhất một “mảnh” của file A, bạn đã có thể upload “mảnh” đó cho những người chưa có. Như vậy bạn đã có thể thấy rằng BitTorrent khác với các mạng P2P khác : cần có file Torrent cho các file (hoặc thư mục) mà bạn muốn download hoặc chia sẻ. Tracker: Có một thành phần trung tâm cho biết nơi mà một peer có thể lấy dữ liệu từ các node trong hệ thống, thành phần trung tâm này gọi là tracker. Tracker nhận updates từ các node định kì 30 phút giống như các nút khi kết nối hoặc rời torrent. Các trang web liệt kê các file torrent (như là torrentbox.com) có những tracker của họ để quản lý việc download và chia sẻ giữa mọi người. File torrent phải có thông tin chi tiết về tracker. Do đó bạn muốn kết nối đến tracker nào thì chỉ có thể sử dụng file torrent được tạo cho tracker đó. Có các phần mềm để giúp bạn thiết lập các tracker riêng và tạo file torrent. -53- Một server nằm trên mạng internet, phối hợp hoạt động của các trình BitTorrent. Khi bạn mở một file torrent, máy tính của bạn sẽ liên lạc với tracker để lấy danh sách các peer cần kết nối. Trong quá trình down file torrent, thỉnh thoảng máy tính của bạn sẽ lại liên lạc với tracker, thông báo cho tracker biết bạn đã down và up bao nhiêu, còn bao nhiêu nữa là down xong,... Nếu bạn chuẩn bị down một file mà tracker của nó hiện đang mất kết nối, bạn sẽ không thể tạo kết nối. Nếu đang down mà tracker mất kết nối, bạn vẫn có thể tiếp tục quá trình truyền tải file với các peer hiện có, nhưng sẽ không kết nối thêm được với peer mới nào khác. Thường các lỗi với tracker ít khi xảy ra trong một thời gian dài, do đó bạn chỉ việc chờ đợi và để mở trình BitTorrent. Seed: Một node trong hệ thống mà sau khi hoàn thành việc sao chép đầy đủ các file và có thể phục vụ cho các node khác thì được gọi là một seed. Seeds là những người đã có 100% file hoặc thư mục (file hoặc thư mục hoàn chỉnh) và vẫn đang tiếp tục upload cho những người khác. Một máy tính có bản copy hoàn hảo của file torrent bạn muốn down. Khi quá trình down của bạn kết thúc, bạn sẽ hoạt động như một seed cho đến khi bạn bấm Finish hoặc đóng hoàn toàn trình BitTorrent lại. Thường thì bạn nên seed một file đã down xong cho người khác. Đồng thời, khi một file torrent mới được đưa lên tracker, một ai đó phải seed nó cho người khác down. Hãy nhớ rằng, tracker không biết tí gì về nội dung thực sự của file, vì thế luôn cần phải có ít nhất một máy đóng vai trò seed. Reseed: Với một file torrent mà số seed của nó là con số 0 tròn trĩnh (hoặc không có đủ số peer để tạo thành một bản copy hoàn hảo), thì dù muốn hay không tất cả những gì các peer nhận được cũng sẽ là một file không hoàn chỉnh, vì không ai trong swarm đó có các phần còn thiếu. Khi điều đó xảy ra, một ai đó với file hoàn chỉnh (seed) sẽ phải đứng ra kết nối với swarm để tiến hành việc truyền tải các phần còn thiếu. Nó gọi là reseed. Thường thì khi một yêu cầu reseed được đưa ra và được chấp thuận, người được yêu cầu phải đảm bảo mình sẽ để trình BitTorrent của mình mở trong một thời gian nhất định, tạo điều kiện cho file torrent đó có thể được nhiều người down hơn. Swarm: Một nhóm các máy tính kết nối với nhau thông qua một file torrent. Ví dụ, nếu trình BitTorrent của bạn báo bạn đang nối với 10 peers và 3 seeds, thì điều đó nghĩa là trong swarm đó có 13 người (không kể bạn). Peer: -54- Peer là những người chưa có đủ 100% file (file chưa hoàn chỉnh) đang download các phần mà họ chưa có đồng thời upload các phần họ đã có cho người khác. Peer là một máy tính khác trên mạng internet. Bạn tạo kết nối với peer và truyền tải dữ liệu với nó. Thường thì một peer không có cả 100 % file mà bạn muốn down (nếu có nó sẽ được gọi là seed). Một vài người khi nói đến peer lại nghĩ tới leecher, những kẻ sau khi down xong không chịu để trình BitTorrent chạy tiếp và hoạt động như một seed. Leecher: Một node mà trong khi đang download các file nhưng vẫn phục vụ các block mà node này hiện có cho các node khác thì được gọi là leecher. Thường thì Leechers là những người download file nhưng không upload hoặc giảm mức upload xuống mức thấp nhất. Share rating: Nếu bạn dùng một trình BitTorrent với giao diện GUI, bạn sẽ thấy thông số share rating hiện trên giao diện. Nó đơn giản chỉ là tỉ lệ bạn up trên tỉ lệ down. Nếu thông số share ratio là 1.0, điều đó có nghĩa là lượng bạn down bằng với lượng bạn up. Số này càng cao thì nghĩa là bạn đóng góp càng nhiều. Nếu bạn thấy share ratio là vô cùng, thì nghĩa là bạn đang seed một file - bạn up nhưng không down. Vì lợi ích của người khác, hãy giữ cho share ratio của bạn lớn nhất có thể. Các trang có file torrent Có rất nhiều trang web liệt kê các file torrent. Bạn chọn rồi down load file torrent về. Sau đó open bằng chương trình BitTorrent của bạn. Ngay lập tức, bạn sẽ được kết nối với tracker và bắt đầu download. Một số trang web đó là: mininova.org Torrentbits.org TorrentReactor.com FileList.org – Phải đăng ký ... Tầm quan trọng của việc Upload. Việc upload trên BitTorrent là đương nhiên và cần thiết. Đặt trường hợp bạn đang download file có 3 seeds và 800 peers, và việc chia sẽ đã hoàn tất ở một số peers. Giả sử bạn là 1 peer đã download xong nhưng chỉ upload 10% của file rồi ngừng. Việc làm này sẽ dẫn đến hậu quả rất xấu bởi vì bạn làm vậy thì nhiều người khác cũng có thể làm như vậy, sau đó sẽ có rất ít seeds và có thể sẽ không còn seeds và những người chưa hoàn tất sẽ không có file hoàn chỉnh. Nếu -55- tất cả mọi người đều có thói quen ngừng upload ngay khi download xong thì file đó sẽ không tồn tại lâu. Hãy đảm bảo rằng dung lượng upload của bạn bằng với dung lượng download hoặc hơn. Nếu ai đó download 700MB và upload 700MB thì vẫn chưa tốt. Để file đó có thể tồn tại lâu và những người khác còn được download về với tốc độ cao, mọi người hãy cố upload bằng 150% dung lượng mình download. Khi bạn đã download xong, hãy tiếp tục upload đến khi bạn đạt tỉ lệ này. Các tracker luôn cấm các leechers do đó luôn theo dõi việc download/upload của bạn. Nếu bạn thích BitTorrent, đừng thử hoặc cố đánh lừa nó. Cơ chế hoạt động của BitTorrent Khi một node mới kết nối với một torrent, nó sẽ liên hệ với tracker để nắm được danh sách tập ngẫu nhiên các seed hoặc leecher có trong hệ thống hiện tại. Node mới sau đó sẽ thử thiết lập tới khoảng 40 node tồn tại hiện có trong hệ thống để trở thành hàng xóm với các node này. Nếu số các node hàng xóm của một nút thấp hoặc giảm xuống dưới 20 (do các node đó rời hệ thống - chẳng hạn) thì node mới này sẽ liên hệ lại với tracker để được bổ sung thêm các node mà node này có thể kết nối tới được. Mỗi một node sẽ tìm kiếm thời điểm thích hợp (thời cơ) để download các khối từ các node khác (hàng xóm) và upload các khối tới các node hàng xóm này. Thường thì một nút có thể chọn một vài khối mà nó có thể download. Nó sử dụng chính sách local rarest first (ưu tiên cục bộ-LRF) trong việc chọn các block để download, nghĩa là node thử download các khối được sao chép ít nhất xung quanh các hàng xóm của node đó. Chính sách tit-for-tat (có đi có lại – TFT) được sử dụng để cảnh giác chống lại cái gọi là free-riding, nghĩa là: một node sẽ thích hơn việc upload cho các node hàng xóm đã cung cấp cho node này tỉ lệ download tốt nhất. Mỗi một node giới hạn số các upload đồng thời thành một số nhỏ, số này vào khoảng 5. Các seed không có gì để download, nhưng chúng cho một chính sách như nhau, đó là chúng upload tới 5 nodes mà có tỉ lệ download cao nhất. Cơ cấu được sử dụng để giới hạn số các upload đồng thời gọi là choking (ngăn chặn, điều tiết), đó là khoảng thời gian từ chối của một node để upload tới hàng xóm. Chỉ những kết nối để chọn hàng xóm (vào khoảng 5) là unchoked ở bất kỳ thời điểm nào. Một node tính toán tỉ lệ download nhận được từ hàng xóm của nó từ 10 giây để quyết định hàng xóm này (chưa bị chokes) sẽ bị choke để thay thế bởi một hàng xóm khác. BitTorrent cũng kết hợp một chính sách gọi là optimistic unchoke (unchoke lạc quan) trong một node, trong việc unchoke bình thường đã mô tả ở trên, trong unchoke chọn ngẫu nhiên hàng xóm bất chấp tỉ lệ download đạt được từ hàng xóm đó. Optimistic unchoke thực hiện 30 giây mỗi lần. Cơ cấu này cho -56- phép các node khám phá các node hàng xóm thường có tỉ lệ download cao, giống như cho phép các node mới nhận được block đầu tiên của chúng. Có thể nói BitTorrent là một giao thức được tạo ra phục vụ cho quá trình truyền tải file. Dưới hình thức kết nối peer-to-peer, người sử dụng kết nối trực tiếp với nhau để gửi và nhận các phần của một file. Một server trung tâm, dưới tên gọi tracker, được lập ra để xác định vị trí những người dùng ấy. Tracker mang nhiệm vụ duy nhất là quản lý các kết nối, nó không cần biết gì về nội dung file đang được truyền tải, bởi thế ngay cả khi tracker có băng thông cực nhỏ, một số lượng người dùng cực lớn vẫn có thể tham gia vào việc truyền tải file. Điểm cơ bản trong BitTorrent chính là việc người dùng thực hiện việc up và down cùng một lúc trong khi băng thông được tổ chức sao cho tối ưu nhất. BitTorrent được thiết kế để khi số người dùng càng tăng cao thì càng làm việc hiệu quả - điều này trái ngược hẳn với các giao thức truyền tải file khác. Một ví dụ để dễ hình dung quá trình này này là hình ảnh một nhóm người ngồi quanh một cái bàn. Hiển nhiên ai cũng có thể nói và nghe người khác nói. Giờ hãy tưởng tượng họ đều đang cố lấy một bản copy của một cuốn sách. Người A cho biết anh ta có trang 1-10, 23, 42-50 và trang 75. Người C, D, E đều thiếu một số trang trong số các trang người A có, vì thế họ cần sắp xếp để lấy bản copy của những trang mà mình thiếu. Đến người B, anh cho biết mình có trang 11-22, 31-37, và 63-70. Người A, D và E bảo B rằng họ muốn một vài trang trong số đó, và B cần đưa cho họ bản copy các trang ấy. Quá trình cứ thế tiếp tục, mọi người lần lượt trao đổi cho nhau những phần mình có và người khác cần. Sau một lát, dù tất cả đã có bản copy của hầu hết các trang trong cuốn sách, song không ai trong số họ có đủ cả cuốn. Giờ hãy chú ý đến một người khác cũng ngồi bên bàn mà ta tạm gọi là S. Người này có bản copy của cả cuốn sách, và vì thế không cần nhận bất cứ trang nào. Anh ta có nhiệm vụ phân phát những trang mà không ai trong nhóm có. Còn người nhận sẽ không lấy các trang mà người khác trong nhóm đã có. Như vậy, người S có thể chia sẻ cuốn sách cho người khác mà không cần phải gửi cả bản copy cho từng người. Anh ta chỉ việc đưa bản copy các trang khác nhau cho những người khác nhau, và tự họ sẽ chia sẻ cho nhau. Người S ở đây được gọi là seed trong BitTorrent. Qui trình khi download với chương trình BitTorrent 1. Trước hết, bạn tải về một file có phần mở rộng là .torrent và mở nó với chương trình BitTorrent của mình. File torrent này không chứa file mà bạn muốn down, nó chỉ mang dữ liệu mô tả file mà bạn CHUẨN BỊ down. 2. Chương trình BitTorrent của bạn dùng thông tin ghi nhận được trong file torrent để kết nối với tracker. Tracker là server mang thông tin và danh sách các peer đang kết nối với file bạn muốn down. -57- 3. Trình BitTorrent của bạn gửi request tới các peer đang kết nối với file đó (swarm) và bắt đầu down về các phần nhỏ của file đó từ mỗi peer. 4. Khi đã down xong mỗi phần nhỏ, trình BitTorrent sẽ bắt đầu up phần đó lên cho những ai trong swarm chưa có cơ hội down phần nhỏ ấy. 5. Quá trình tiếp diễn cho và mọi người trong swarm tiến hành down các phần của file mình cần. 6. Sau khi down xong file bạn cần, trình BitTorrent sẽ chuyển máy bạn thành seed cho file đó và cho phép mọi người tiếp tục down cho đến khi bạn thoát khỏi chương trình. Để một file torrent có thể được truyền lại, cần ít nhất một seed. 3.5.2. Áp dụng mô hình tin cậy NICE đảm bảo công bằng trong ứng dụng chia sẻ file BitTorrent Như đã nói ở trên, trong ứng dụng BitTorrent thường xảy ra tình trạng một số peer download dữ liệu nhưng không chịu upload, đó là hiện tượng free- riding. Hiện tượng free-riding trong BitTorrent giống như các node nguy hiểm (malicious) trong NICE, đó là các node xấu trong giao dịch luôn gán cookie với giá trị trong khoảng 0.9 đến 1 cho các node không nguy hiểm khác, hoặc gán giá trị cookie trong khoảng 0 đến 0.2. Áp dụng mô hình NICE sẽ cho khả năng phát hiện và cô lập các nút nguy hiểm, đồng thời tạo ra các nhóm cộng tác thiết thực trong việc chia sẻ tài nguyên (như trong trường hợp download và upload trong BitTorrent), hạn chế các truy vấn, từ đó cải thiện băng thông. Việc phát hiện các nút free-rider được tiến hành trong NICE thông qua các cookie như sau: Trong khi giao dịch, các node sẽ kiểm tra giá trị tin cậy thông qua cookie. Nếu trong cơ sở dữ liệu của nút kiểm tra chưa có cookie của node bị kiểm tra thì tiến hành kiểm tra qua các node lân cận (hàng xóm). Giá trị cookie nếu trong khoảng gần, hoặc bằng 1 là tin cậy (trong đoạn [0.7:1] chẳng hạn). Nếu thấp (chẳng hạn qui định nhỏ hơn hoặc bằng 0.2) là không tin cậy. Tuy vậy, nếu giá trị của cookie là tin cậy, nhưng cookie này không có được một cách tin cậy (không nằm trong cơ sở dữ liệu hoặc thông qua hàng xóm tin cậy) thì cũng bị coi là giả mạo. Tỉ lệ các free-rider sẽ được tính thông qua tỉ số giữa các free-rider phát hiện được chia cho tổng các free-rider tham gia. -58- Trong quá trình giao dịch, mặc dù băng thông giữa hai điểm (node) là cố định, tuy nhiên nếu lượng giao dịch nhiều thì sẽ ảnh hưởng đến tốc độ của các tiến trình (download và upload chẳng hạn) giữa các điểm này. Trong NICE, việc ảnh hưởng đến băng thông chính là phụ thuộc vào số các truy vấn giữa các node. Vì vậy các free-rider tham gia càng nhiều thì càng ảnh hưởng đến băng thông sẽ càng lớn. Để có thể hạn chế các truy vấn, tăng khả năng phát hiện các node nguy hiểm (free-rider) thì NICE đề ra giao thức của mình và tạo ra các nhóm cộng tác thiết thực. Với các node nguy hiểm, chúng sẽ luôn chuyển các truy vấn với giá trị cookie là 1. NICE ngăn chặn các truy vấn này theo phương án tạo ra các nhóm cộng tác thiết thực bằng cách tìm các node tốt. Các truy vấn từ các node xấu sẽ bị các node tốt phát hiện và sẽ không được các node tốt chuyển đi, điều đó làm giảm số các truy vấn giữa các node. Càng nhiều các node tốt thì nhóm cộng tác càng mở rộng, từ đó càng ngăn được nhiều các truy vấn xấu từ các node nguy hiểm, và vì vậy băng thông sẽ càng được cải thiện. Chương trình Demo của NICE sau đây sẽ minh họa các vấn đề trong BitTorrent: - Tỉ lệ các nút tham gia mà không đóng góp (free-rider) - Tỉ lệ phát hiện các free-rider - Băng thông khi có free-rider 3.6. Chương trình Demo và các kết quả thu được 3.6.1. Giới thiệu chương trình, cài đặt và thực hiện mô phỏng Chương trình được cải tiến từ chương trình Demo của NICE. a) Yêu cầu: - Hệ điều hành linux (ở đây dùng ubuntu) - ctags: - nice: b) Cài đặt: Cài đặt ctags: giải nén ctags-5.8.tar.gz và thực hiện các lệnh: cd ctags-5.8 -59- ./configure make sudo make install Cài đặt nice.trustsim.extended: Giải nén nice.trustsim.extended.tgz và thực hiện lệnh: cd nice.trustsim.extended make Kết quả là: gcc -Wall -g -DDEBUG -c context.c gcc -Wall -g -DDEBUG -c event.c gcc -Wall -g -DDEBUG -c history.c gcc -Wall -g -DDEBUG -c link.c gcc -Wall -g -DDEBUG -c main.c gcc -Wall -g -DDEBUG -c node.c gcc -Wall -g -DDEBUG -c pqueue.c gcc -Wall -g -DDEBUG -c query.c gcc -Wall -g -DDEBUG -c toposerver.c gcc -Wall -g -DDEBUG -c truststore.c gcc -Wall -g -DDEBUG -c unittest.c gcc -o hiertrust context.o event.o history.o link.o main.o node.o pqueue.o query.o toposerver.o truststore.o -lm Sau khi make chương trình tạo ra file thực thi hiertrust cùng các file có đuôi .o tương ứng theo các file .c mã nguồn. c) Mô tả các file chương trình: Chức năng chính của các file chương trình File Chức năng main.c Thực hiện các chức năng của chương trình event.h event.c Định nghĩa cấu trúc sự kiện (event) cùng các thủ tục khác: Tạo sự kiện Giải phóng sự kiện node.h, node.c Định nghĩa các khối blocks, cookieQueryInfo, node và các thủ tục khác. Lưu trữ các thông tin của node: lịch sử giao dịch, vị trí các node tin cậy khác, các thông tin cho các node khác có các hàm chính: -60- In trạng thái kết thúc của node Giải phóng tất cả tài nguyên Lưu trữ các blocks của một node Đếm số blocks lưu trữ của một node Loại bỏ các blocks đang lưu trữ của một node Cho một node tham gia query.h, query.c Định nghĩa cấu trúc lấy và kiểm tra truy vấn cùng các hàm và thủ tục khác có liên quan. Lưu trữ các thông tin quảng cáo dùng để phát hiện các node mới có các chức năng chính: Thêm các node vào truy vấn Lấy danh sách các node thông báo Đánh dấu trong truy vấn các node đã được thăm Kiểm tra node đã được thăm chưa pqueue.h, pqueue.c Định nghĩa các cấu trúc về khóa, dữ liệu, độ dài và kích cỡ dữ liệu, hàng đợi cùng các thủ tục khac. Tạo hàng đợi lưu trữ theo cây nhị phân đầy đủ với đỉnh cha luôn nhỏ hơn các đỉnh con, chỉ số bắt đầu từ 1 Thêm dữ liệu vào pqueue Kiểm tra pqueue rỗng context.h, context.c Định nghĩa cấu trúc biến ngữ cảnh Khởi tạo các giá trị ban đầu cho các tham số trong mô phỏng. history.h, history.c Định nghĩa cấu trúc lịch sử giao dịch. Lưu trữ lịch sử giao dịch của các node có các chức năng chính: Giải phóng dữ liệu Cập nhập dữ liệu Thêm dữ liệu Thêm dữ liệu với các node tin cậy Loại các node giao dịch Lấy giao dịch lớn nhất Giải phóng dữ liệu vùng đệm khi in. link.h, link.c Mô phỏng liên kết có các chức năng chính: Tạo độ trễ liên kết Kiểm tra độ trễ Lập lịch biểu độ trễ toposerver. h, toposerver. c Định nghĩa cấu trúc toposerver mạng, Lưu trữ định danh của các node để mô tả topo của mạng có các chức năng chính: Giải phóng các node Thêm node Lấy node trustore.h, Định nghĩa ngưỡng cookie tốt, cấu trúc cookie, cấu trúc lưu trữ tin -61- trustore.c cậy và các hàm khác có liên quan. Lưu trữ giá trị tin cậy của các node có các chức năng chính: Thêm giá trị tin cậy Kiểm tra giá trị tin cậy Đếm các giá trị tin cậy Tìm kiếm giá trị tin cậy Xóa giá trị tin cậy Tạo giá trị tin cậy Lưu trũ vào cookie Kiểm tra độ tin cậy unittest.c Thực hiện thủ tục kiểm tra cấu trúc lưu trữ cookies100 00 Lưu trữ cấu hình của hệ thống dùng với tham số -config Các chức năng chính và mô phỏng trong main.c: parse_args(context * ctx, int argc, char * argv[]): Đọc và kiểm tra các tham số dòng lệnh, nếu hợp lệ thì chạy tiếp chương trình, nếu không hợp lệ thì thông báo cho người dùng. Các tham số : -l : log data[stdout] -L : log NO data[off] -s seed : randomseed[%ld] -config f : sử dụng file config f - read_config(context * ctx) Đọc tham số cấu hình từ dòng lệnh đưa vào biến ngữ cảnh ctx Nếu file config không có thì chạy stubconfig(ctx) <hàm khởi tạo cấu hình hệ thống mặc định> Tiếp theo kiểm tra có ghi log file và ghi ra đâu (stdout mặc định). Đọc file config nhập vào từ dòng lệnh. - stubconfig(context * ctx) Tạo cấu hình mặc định cho hệ thống vào biến ngữ cảnh ctx Cấu hình mặc định cho hệ thống: Bao gồm 10 node, mỗi node có độ tin cậy là 1.0, có 9 block -62- Các sự kiện node_join() được tạo ra nếu node được tạo thành công - init(context * ctx) Khởi tạo hệ thống, seed một số ngẫu nhiên, tạo một topo server gắn với biến ngữ cảnh hệ thống. - printstats(context *ctx) In ra thống kê hiện thời có bao nhiêu lỗi - newround(context * ctx) Tạo vòng mới - heartbeat(context *ctx, event *e, double t) In ra thống kê mỗi nhịp, sau đó tạo lịch mới - cleanup(context * ctx) - Đặt mọi giá trị về vị trí ban đầu (hoàn thành) - Lập sự kiện mới dạng khởi thủy. - main() - Tạo biến ngữ cảnh - Đọc và kiểm tra các tham số dòng lệnh - Đọc file config. - Khởi tạo hệ thống - Chạy mô phỏng. Mặc định chương trình chạy một vòng mô phỏng. - Kết thúc chương trình giải phóng bộ nhớ do các tham số chiếm trong quá trình chạy chương trình. 3.6.2. Chạy chương trình: Sau khi vào cửa sổ lệnh (Terminal) và chuyển đến thư mục chứa các file chương trình và biên dịch chương trình thành công, để chạy chương trình ta sử dụng file cấu hình, gõ lệnh: ./hiertrust –config cookies10000 File cookies10000 có các cấu trúc config như sau: COOKIES 1 -63- NODES 10000 good=1.0 want=10 have=11 state=11 sleep=0 NODES 10000 good=0.1 want=10 have=11 state=11 sleep=0 Kết quả chạy lệnh ./hiertrust -config cookies10000 sẽ hiển thị các kết quả tính toán ra màn hình. Để có được kết quả theo ý thì cần lọc và ghi ra một file cụ thể trên đĩa để tiện cho quá trình phân tích. Khi thay thế file cookies10000 bằng một file khác có cấu hình cụ thể, thì khi chạy lại chương trình sẽ cho kết quả khác. 3.6.3. Các kết quả mô phỏng Trong quá trình mô phỏng, tôi chọn cấu hình cho các file với các thông số như sau: COOKIES 1 HEARTBEAT 0.1 MAXRULE 1 BACKOFF 0.5 NODES 1000 good=1.0 want=100 have=101 state=80 sleep=0 NODES xxxx good=0.2 want=100 have=101 state=80 sleep=0 ở đây xxxx là số các node xấu (lấy giá trị tin cậy của cookie là 0.2). Số các node này thay đổi theo các file được chọn. Mô phỏng được tiến hành trên các file cấu hình được đặt tên là badnode- 0, badnode-1000, badnode-2000, badnode-10000 và badnode-20000 với số node xấu thay đổi tương ứng là 0, 1000, 2000, 10000 và 20000. Các tham số khác giữ nguyên, trừ file badnode-0 giới hạn số các truy vấn tối đa cho mỗi node là 20 để ổn định cho việc so sánh với các trường hợp khác. 3.6.3.1. Tỉ lệ các nút tham gia mà không đóng góp (free-rider) -64- Hình 3.1 cho biết tỉ lệ phát hiện các tương tác (gửi truy vấn theo các cookie) của các node xấu (đường cong có dấu *) so với tổng số các tương tác của các node (bao gồm cả node xấu và node tốt - đường cong có dấu ) tham gia giao dịch. Thời gian phân tích của mô phỏng là 5 phút. Trong kết quả thu được ta thấy khả năng phát hiện các nút xấu tại lân cận phút thứ 2 của mô phỏng là thấp nhất (thể hiện qua hiệu-khoảng cách của 2 đường cong), nhưng sau đó khả năng phát hiện đã ổn định và tỉ lệ đã tương đối cân bằng giữa các node xấu bị phát hiện so với tổng số các node tham gia. Điều này có thể giải thích là lúc đầu khi mà nhóm hợp tác giữa các node tốt chưa hình thành hoặc ít thì khả năng phát hiện node xấu là thấp. Khi nhóm này mở rộng và phát triển thì khả năng phát hiện tăng lên và đạt đến độ ổn định tương đối, đồng thời các truy vấn giảm đáng kể và cũng ổn định (dần về với số các tương tác của các node tốt), thể hiện qua đồ thị là khoảng cách giữa tổng số các tương tác và số tương tác của chỉ mình các node tốt. Hình 3.2 và 3.3 sau đây thể hiện kết quả tương tự. -65- 3.6.3.2. Tỉ lệ phát hiện các free-rider Hình 3.4 minh họa tổng hợp kết quả về khả năng phát hiện các node xấu tương ứng với cấu hình số lượng các node xấu tham gia là 1000, 2000, 10000 và 20000. -66- Hình 3.5 minh họa tỉ lệ phát hiện các node xấu. Tỉ lệ này được lấy bằng tỉ số giữa các tương tác của các node xấu phát hiện được chia cho tổng số các tương tác của các node tham gia. Tại lân cận của phút thứ 2 cho tỉ lệ thấp nhất. Lí do là tổng số các tương tác của các node ở đây lớn nhất (mẫu lớn nhất), trong khi số các tương tác phát hiện được ở thời điểm này là thấp (tử số nhỏ nhất), từ đó kết quả của phép chia là nhỏ nhất. Bắt đầu từ những phút sau phút thứ 2 thì tỉ lệ này là tăng dần, ổn định và gần với nhau. Số các tương tác của các node xấu phát hiện được gần với tổng số các tương tác của node tham gia, và vì vậy tỉ lệ này tiến dần tới 1, đạt kết quả cao nhất vào khoảng trên 90%. Có được kết quả này là do trong mạng tại thời điểm này đã hình thành và mở rộng các nhóm hợp tác thiết thực là các node tốt. Các node tốt sau khi phát hiện ra các node xấu thì ngăn chặn các node xấu chuyển các truy vấn và sau đó “tỉa” các node xấu này ra khỏi hệ thống. Vì vậy trong các đồ thị thì tổng số các tương tác của các node tham gia giao dịch sẽ giảm dần, và giảm về số các tương tác của các node xấu bị phát hiện. Số các tương tác tổng cộng cao hơn (đường cong nằm phía trên) là do có các tương tác của các node tốt cùng tham gia. -67- 3.6.3.3. Băng thông khi có free-rider Theo định nghĩa băng thông (bandwidth) trên mạng thì băng thông là đại lượng đặc trưng cho tốc độ truyền dữ liệu từ điểm này tới điểm khác trong một khoảng thời gian (thường tính bằng đơn vị của bit/giây). Chẳng hạn một modem làm việc ở tốc độ 56 kbs có hai băng thông làm việc ở 28 kbs. Trong một mạng nếu số lượng các truy vấn tham gia nhiều thì các truy vấn này sẽ ảnh hưởng đến tốc độ truyền dữ liệu trên mạng (có sự chia sẻ đường truyền giữa các ứng dụng), điều đó có nghĩa là băng thông bị hạn chế và ảnh hưởng đến hiệu năng của mạng. Trong NICE, các node tốt cùng với các nhóm cộng tác sẽ ngăn chặn việc gửi các truy vấn của các node xấu, từ đó cải thiện được hiệu năng và băng thông của mạng. Hình 3.6 trong thí nghiệm mô phỏng thể hiện tổng số các tương tác của toàn bộ các node tham gia giao dịch trong mạng (bao gồm cả các node tốt và xấu). Mô phỏng làm trên cấu hình trong đó các node nguy hiểm được lấy là 1000, 2000, 10000 và 20000. Mỗi đường cong thể hiện tổng số các tương tác (bao gồm cả các node tốt và node xấu) tương ứng với số các node xấu cho trong cấu hình của tệp mô phỏng. Rõ ràng số các tương tác này giảm nhanh và càng về -68- sau (tính từ phút thứ 3 trở đi) càng ổn định ở mức thấp. Điều này tạo điều kiện rất nhiều cho việc cải thiện băng thông của toàn mạng. Các ứng dụng truy cập dữ liệu, download/upload sẽ được cải thiện nhiều về tốc độ,… -69- Kết luận và hướng nghiên cứu Các ứng dụng của mạng ngang hàng ngày càng phát triển. Việc ngăn chặn các ảnh hưởng làm giảm hiệu năng và băng thông của mạng là cần thiết nhằm cải thiện chất lượng của toàn mạng. Bài viết đã nghiên cứu về các vấn đề tin cậy và đề xuất một khía cạnh là làm thế nào để đảm bảo công bằng trong các ứng dụng cộng tác ngang hàng dựa trên khái niệm tin cậy. Đóng góp chính của bài viết này là một đề xuất giải thuật định giá tin cậy dựa theo cookie, qua đó phát hiện được các trường hợp giả mạo, các truy vấn của các node nguy hiểm, từ đó hạn chế sự chiếm dụng băng thông đường truyền, tạo điều kiện nâng cao tốc độ của đường truyền. Cũng từ sự phát hiện các node nguy hiểm mà có thể ưu tiên cho các node tốt trong vấn đề truy cập và chia sẻ tài nguyên, từ đó đảm bảo công bằng trong các ứng dụng cộng tác. Giải thuật này có thể áp dụng trong môi trường cộng tác của mạng ngang hàng. Giải thuật là thiết thực, hạn chế sự biến đổi của các cuộc tấn công bởi những người sử dụng xấu. Hướng nghiên cứu tiếp theo của đề tài: Củng cố và mở rộng ứng dụng của giải thuật dựa trên khái niệm tin cậy và cookie, đồng thời kiểm định qua ứng dụng cụ thể trong môi trường thực, để có thể áp dụng được tốt hơn trong việc đảm bảo công bằng cho các ứng dụng cộng tác trong mạng ngang hàng. Mặc dù đã rất cố gắng, xong do năng lực còn hạn chế nên bài viết không tránh khỏi những thiếu sót. Rất mong nhận được sự đóng góp quí báu của quý Thầy, Cô và các bạn đồng nghiệp cũng như những ai quan tâm tới bài viết. Tôi xin chân thành cảm ơn. -70- Tài liệu tham khảo Tiếng Anh [1] Alfarez Abdul-Rahman & Stephen Hailes, “A Distributed Trust Model”, pp. 1-9. [2] Dinesh C. Verma (2005), Legitimate Applications of Peer to Peer Networks. Wiley-InterScience, pp. 1-17, 37-54. [3] Jing Zhao, Ping Zhang and Guohong Cao, “On Cooperative Caching inWireless P2P Networks”, pp. 1-3. [4] Karl Aberer, Zoran Despotovic, “Managing Trust in a Peer-2-Peer Information System”, pp.1-3. [5] Lik Mui, Mojdeh Mohtashemi, Ari Halberstadt, “A Computational Model of Trust and Reputation”, pp. 1-5. [6] Nicolas C. Liebau, Vasilios Darlagiannis, Oliver Heckmann, "Accounting in Peer-to-Peer-Systems”, pp. 11-13. [7] Ralf Steinmetz (2003), Peer-to-Peer Systems and Applications, pp.38-43 [8] Rob Sherwood, Seungjoon Lee, Bobby Bhattacharjee, “Cooperative Peer Groups in NICE”, pp. 1-11. [9] The Gnutella Protocol Specification v0.4 Document Revision 1.2. protocols@clip2.com [10] [11] Tiếng Việt [12] Hồ Sĩ Đàm (2007), Cấu trúc dữ liệu và giải thuật, Nhà xuất bản Giáo dục. [13] PGS.TS Hồ Sĩ Đàm: Bài giảng môn Cấu trúc dữ liệu & giải thuật. [14] Đinh Mạnh Tường (2001), Cấu trúc dữ liệu và thuật toán, nhà xuất bản Khoa học và Kỹ thuật Hà Nội, tr. 5-22.