Luận văn Đảm bảo công bằng trong các ứng dụng cộng tác ngang hàng
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGH
NGUYỄN XUÂN LÔ
ĐẢM BẢO CÔNG BẰNG TRONG CÁC ỨNG DỤNG
CỘNG TÁC NGANG HÀNG
Ngành: Công nghệ thông tin
Chuyên ngành: Truyền dữ liệu và Mạng máy tính
Mã số: 60 48 15
LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS HỒ SĨ ĐÀM
Hà Nội – 2011
-1-
LỜI CAM ĐOAN
Tôi xin cam đoan toàn bộ nội dung của bản luận văn với tên “Đảm bảo công
bằng trong các ứng dụng cộng tác ngang hàng” là do tôi tự nghiên cứu, tham khảo và
phát triển các ý, các giải thuật theo yêu cầu của đề tài luận văn.
Nội dung bản luận văn chưa từng được công bố, phát hành hoặc sao chép dưới
bất kì hình thức nào.
Nếu sai, tôi xin chịu hoàn toàn mọi trách nhiệm !
Hà Nội, ngày 13/6/2011
Người cam đoan
Nguyễn Xuân Lô
-2-
LỜI CẢM ƠN
Em xin chân thành cảm ơn các Thầy, Cô giáo khoa Công nghệ Thông tin
trường Đại học Công nghệ - Đại học Quốc gia Hà Nội; các Thầy, Cô giáo trong và
ngoài trường Đại học Công nghệ đã giảng dạy, giúp đỡ, tạo điều kiện cho em học tập,
nghiên cứu để có tri thức bậc Sau đại học.
Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc tới Thầy giáo - Phó Giáo sư Tiến sĩ
Hồ Sĩ Đàm đã tận tình hướng dẫn, chỉ bảo để em hoàn thành luận văn.
Tôi cũng xin chân thành cảm ơn tới tất cả các bạn học viên cao học K14 ngành
Công nghệ thông tin trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã giúp đỡ
tôi trong thời gian học tập và làm luận văn.
Mặc dù đã có nhiều cố gắng, song do trình độ năng lực còn hạn chế, nên luận
văn không tránh khỏi thiếu sót. Rất mong nhận được sự góp ý, quan tâm của các Thầy,
Cô cùng toàn thể các bạn và những ai quan tâm tới luận văn.
Một lần nữa, tôi xin chân thành cảm ơn.
Hà Nội, tháng 6 năm 2011
Người làm luận văn
Nguyễn Xuân Lô
-3-
MỤC LỤC
Trang
Chương Mở đầu .................................................................................................................................5
Lý do chọn đề tài............................................................................................................................ 5
Mục đích nghiên cứu...................................................................................................................... 5
Nội dung nghiên cứu...................................................................................................................... 5
Bố cục luận văn.............................................................................................................................. 6
Chương 1: Những vấn đề chung..........................................................................................................7
1.1. Ứng dụng phân tán.................................................................................................................. 7
1.2. Ứng dụng cộng tác ngang hàng................................................................................................ 9
1.3. Mạng ngang hàng Peer – to - Peer (P2P).................................................................................10
1.4. Một số mạng chia sẻ file.........................................................................................................10
1.5. Thuật toán và độ phức tạp thuật toán ....................................................................................13
Chương 2: Suy luận tin cậy trong mạng ngang hàng ..........................................................................19
2.1. Khái niệm tin cậy và quản lí tin cậy .........................................................................................19
2.2. Mô hình tin cậy ......................................................................................................................19
2.3. Xác định người cộng tác .........................................................................................................22
2.4. Mô hình suy luận....................................................................................................................23
2.5. Mô hình hệ thống tin cậy NICE: ..............................................................................................24
2.6. Tính toán tin cậy phân tán trong NICE.....................................................................................28
2.7. Các hệ thống tin cậy khác .......................................................................................................36
Chương 3: Đảm bảo công bằng với các ứng dụng cộng tác trong mạng ngang hàng .........................38
3.1. Giới thiệu ...............................................................................................................................38
3.2. Bài toán..................................................................................................................................39
3.3. Giao dịch dựa trên cookie.......................................................................................................43
3.4. Kiểm tra tính tin cậy của các cookie ........................................................................................46
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 ......51
3.6. Chương trình Demo và các kết quả thu được..........................................................................58
Kết luận và hướng nghiên cứu ..........................................................................................................69
Tài liệu tham khảo ............................................................................................................................70
-4-
Chương Mở đầu
Lý do chọn đề tài
Hiện nay mạng ngang hàng Peer - to - Peer (P2P) cùng với các ứng dụng của
nó đang nổi lên và ngày càng chiếm nhiều thị phần trong đời sống. Các mô hình
ứng dụng chia sẻ file dữ liệu đã được triển khai nhiều ở các công ty, xí nghiệp,
trường học và đã và đang đem lại nhiều lợi ích. Để có thể sử dụng mạng P2P
hiệu quả thì người sử dụng phải cộng tác với nhau. Chia sẻ file và cộng tác trong
các ứng dụng P2P là đặc trưng tiêu biểu của mạng ngang hàng. Tuy nhiên trong
quá trình cộng tác với nhau nảy sinh nhiều vấn đề, ví dụ như cách chia sẻ file,
quyền truy cập lấy tài liệu, thứ tự ưu tiên lấy tài liệu, kiểm tra tính tín cậy trong
cộng tác, ảnh hưởng trong giao dịch đến băng thông và hiệu năng của mạng,
vấn đề bảo mật,... đặc biệt là trong môi trường cộng tác nhưng có tính phí. Để có
thể cải thiện được một môi trường cộng tác hiệu quả hơn trong các ứng dụng
P2P, làm cho nó ngày càng phát triển, thì đã có rất nhiều các công trình nghiên
cứu trong và ngoài nước và cũng đạt được nhiều thành tựu. Với những lý do trên
mà tôi chọn đề tài nghiên cứu “Đảm bảo công bằng trong các ứng dụng cộng
tác ngang hàng”, với mong muốn nghiên cứu về một lĩnh vực nhỏ trong ứng
dụng P2P, và góp một phần vào việc nâng cao hiệu quả trong ứng dụng cộng tác
ngang hàng.
Mục đích nghiên cứu
Mục đích nghiên cứu của đề tài là:
- Phân biệt ứng dụng (người) cộng tác và không cộng tác.
- Tìm được giải thuật định giá và kiểm tra tính tin cậy của ứng dụng cộng
tác.
- Áp dụng kết quả nghiên cứu vào các ứng dụng cộng tác trong mạng P2P.
Nội dung nghiên cứu
- Ứng dụng cộng tác trong mạng P2P
- Suy luận tin cậy trong mạng P2P, mô hình độ tin cậy ngang hàng của
NICE.
- Đảm bảo công bằng cho các ứng dụng cộng tác trong mạng P2P.
-5-
+ Vấn đề công bằng trong mạng.
+ Á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.
+ Mô phỏng và đánh gía hiệu năng.
Bố cục luận văn
Luận văn gồm 4 chương:
Chương mở đầu: trình bày về lí do chọn đề tài nghiên cứu, mục đích
nghiên cứu, nội dung nghiên cứu.
Chương 1: Những vấn đề chung: Trình bày các khái niệm cơ bản về ứng
dụng phân tán và ứng dụng cộng tác, các khái niệm trong mạng ngang hàng, giải
thuật và độ phức tạp của giải thuật.
Chương 2: Suy luận tin cậy trong mạng ngang hàng: Trình bày về các
khái niệm tin cậy, định giá tin cậy, mô hình tin cậy NICE làm nền tảng cho áp
dụng vào ứng dụng của chương 3.
Chương 3: Đảm bảo công bằng với các ứng dụng cộng tác ngang hàng:
Chương này trình bày về những khái niệm công bằng, đảm bảo công bằng trong
các ứng dụng chủ/khách và ngang hàng, giao dịch dựa trên cookie và kiểm tra
tính tin cậy của cookie. Chương này cũng tập trung trình bày việc áp dụng mô
hình NICE vào một ứng dụng nhỏ trong mạng BitTorrent và chương trình demo
cùng kết quả.
-6-
Chương 1: Những vấn đề chung
1.1. Ứng dụng phân tán
Theo tác giả Dinesh C. Verma [2]. Phần này trình bày những khái niệm
cơ bản về ứng dụng phân tán, lĩnh vực liên quan đến cộng tác ngang hàng.
a) Khái niệm ứng dụng phân tán: Bao gồm hai hoặc nhiều module phần
mềm chạy trên các máy tính khác nhau, tương tác với nhau thông qua mạng
truyền thông kết nối giữa các máy tính.
Các vấn đề chủ yếu cần quyết định khi xây dựng ứng dụng phân tán
– Ứng dụng cần bao nhiêu module phần mềm
– Triển khai các module phần mềm trên các máy tính khác nhau như
thế nào
– Bằng cách nào mỗi module phần mềm phát hiện ra các module
khác nó cần giao tiếp
b) Kiến trúc client/server
Kiến trúc client/server là cách tổ chức một ứng dụng phân tán bao gồm
hai modules phần mềm khác nhau:
– Module server với chỉ một thể hiện trong hệ thống.
– Module client với nhiều thể hiện trong hệ thống.
Về mặt giao tiếp trong hệ thống: Chỉ diễn ra giữa module server và các
module client. Đặc trưng của kiến trúc client/server là có một module server làm
điểm trung tâm trong giao tiếp. Các client không giao tiếp trực tiếp với nhau mà
chỉ giao tiếp với module server.
Trong kiến trúc client/server, server thường chứa nhiều phần mềm phức
tạp, trong khi clients thì đơn giản. Với lợi ích của trình duyệt web trong hầu hết
các máy tính, thì đây là kiến trúc hầu như dành để phát triển các ứng dụng phân
tán vì rằng chúng có thể sử dụng một trình duyệt web chuẩn làm client.
Vấn đề phát hiện để giao tiếp: Mỗi client cần phát hiện địa chỉ mạng của
server:
Server chạy trên cổng và địa chỉ IP biết trước với các client
Client kết nối với server theo địa chỉ mạng đã biết
-7-
Server không cần biết trước bất kỳ thông tin nào về các client
Trên Internet, client chỉ cần biết địa chỉ IP của server vì số hiệu cổng của
client đã được chuẩn hóa.
• Ưu điểm
– Đơn giản hóa công việc bảo trì và nâng cấp
• Module server thường phức tạp hơn module client lại được
đặt ở chỉ một máy tính
• Hiện nay thường trình duyệt Web được sử dụng làm client,
người phát triển ứng dụng không cần phát triển và bảo trì
• Nhược điểm
Không sử dụng hiệu quả sức mạnh tính toán của các máy client như máy
server
c) Kiến trúc ngang hàng
Kiến trúc P2P là cách tổ chức nhiều module phần mềm giống nhau, mỗi
module chạy trên một máy tính khác nhau giao tiếp với nhau. Theo cách này thì
có thể coi mỗi máy tính vừa chạy module client yêu cầu truy nhập dịch vụ vừa
chạy module server cung cấp dịch vụ cho các máy tính khác.
+ Vấn đề phát hiện
Mỗi máy tính cần biết địa chỉ mạng của các máy tính khác nó muốn giao
tiếp
+ Ưu và nhược điểm
Tận dụng sức mạnh kết hợp và khả năng mở rộng, tuy nhiên vấn đề bảo
trì và nâng cấp phần mềm khó khăn hơn.
d) Vấn đề khám phá
Để có thể giao tiếp với nhau mỗi module cần biết nơi gửi thông báo cho
các module khác (Tức địa chỉ mạng gồm địa chỉ IP và số cổng).
- Các giải pháp phát hiện địa chỉ:
+ Cố định số cổng, cho tất cả các module biết địa chỉ IP và số cổng của
các module khác. Điều này làm được bằng cách: Có thể mã cứng vào chương
-8-
trình, tuy nhiên cũng giống như phương pháp cấu hình địa chỉ IP tĩnh trên mạng
-> cần phối hợp tổng thể tránh đụng độ số cổng.
+ Địa chỉ IP và số cổng của các module khác được cung cấp như các tham
số cấu hình. Phương pháp này có nhược điểm đối với các ứng dụng quy mô lớn
đòi hỏi nhiều công sức cấu hình.
1.2. Ứng dụng cộng tác ngang hàng
Một ứng dụng cộng tác là một ứng dụng chia sẻ các thành phần tài
nguyên của chúng để cho các thành viên khác trong nhóm cộng tác sử dụng. Nói
một cách khác, một ứng dụng cộng tác là một ứng dụng phân bổ một tập con tài
nguyên của nó cho việc sử dụng của các máy khác trong ứng dụng.
Tài nguyên phân bổ ở đây là bộ xử lí, băng thông, dữ liệu lưu trữ,…, của
ứng dụng cộng tác.
Khi các ứng dụng cộng tác với nhau, chúng tạo thành các nhóm cộng tác.
Các nhóm cộng tác, trong thực tế, hiện nay có thể kể đến một lớp rộng lớn
các ứng dụng, bao gồm các ứng dụng dòng đa phương tiện trực tuyến, các ứng
dụng hội nghị đa thành phần và các ứng dụng P2P…, và có thể là một hạ tầng cơ
sở cộng tác.
Tuy vậy các hệ thống cộng tác chỉ thi hành tốt nhất nếu tất cả mọi người
sử dụng làm việc, cộng tác và cung cấp chia sẻ tài nguyên của họ tới hệ thống.
Quan điểm của hệ thống cộng tác là không duy nhất trong liên mạng.
Trong thực tế các gói tin vận chuyển trong Internet là sự cộng tác mạo hiểm khi
dùng các tài nguyên chia sẻ ở các bộ định tuyến (router).
Mục đích hướng tới đối với những ứng dụng cộng tác là các ứng dụng đầu
cuối, nơi cung cấp một platform trong việc thực hiện các ứng dụng phân tán
rộng lớn theo kiểu cộng tác. Rõ ràng, một số các tài nguyên phân tán rộng lớn có
thể có được qua Internet trong sự cộng tác. Đây cũng chính là xu hướng của các
ứng dụng cộng tác ngang hàng Peer-to-Peer (P2P), và những thế hệ tiếp theo của
các ứng dụng P2P dựa trên các khái niệm của sự chia sẻ tài nguyên phân tán
cộng tác.
-9-
1.3. Mạng ngang hàng Peer – to - Peer (P2P)
Định nghĩa: Theo tài liệu của Ralf Steinmetz [7] trang 21 thì Oram et al
đưa ra định nghĩa cơ bản về hệ thống Peer – to – Peer như sau: [a Peer-to-Peer
system is] a self-organizing system of equal, autonomous entities (peers)
[which] aims for the shared usage of distributed resources in a networked
environment avoiding central services.
Mạng P2P không có khái niệm máy trạm (client) hay máy chủ (server),
mà chỉ có khái niệm các nốt (peers) đóng vai trò cả client và server.
Theo Karl Aberer, Zoran Despotovic [4] thì các nốt khi tham gia trao đổi
trong cộng đồng mạng sẽ cung cấp truy cập tới các tài nguyên tính toán của
chính nó.
Một mạng P2P có thể được đặc trưng bởi các tính chất sau:
- Không có sự sắp đặt trung tâm (Các máy không chịu sự sắp đặt của
một máy khác).
- Không có cơ sở dữ liệu trung tâm (Cơ sở dữ liệu là phân tán).
- Không có máy nào bao trùm hệ thống (Các máy là ngang hàng).
- Các máy tự trị
- Các máy và các kết nối là không tin cậy.
1.4. Một số mạng chia sẻ file
1.4.1. Mạng chia sẻ file P2P:
- Là mạng P2P phổ biến và nổi tiếng nhất trên Internet hiện nay.
+ Chức năng chủ yếu của mạng là cho phép tìm kiếm và truyền dữ liệu
dựa trên giao thức IP (Internet Protocol).
+ Để truy cập vào mạng P2P này, người dùng chỉ cần download và cài đặt
phần mềm ứng dụng phù hợp cho máy tính của mình.
+ Có nhiều mạng P2P và phần mềm ứng dụng P2P tồn tại hiện nay. Một
số phần mềm chỉ sử dụng được cho 1 mạng P2P nhất định, một số hoạt động
được với nhiều mạng P2P khác nhau.
+ Một số mạng P2P nổi tiếng trên Internet như: BitTorent, Gnutella,...
-10-
1.4.2. Chia sẻ file trong mạng ngang hàng
- Có thể nói ứng dụng được sử dụng nhiều nhất của mạng ngang hàng đó
là chia sẻ file.
- Theo ước tính khoảng 50% (có thời điểm đến 75% ) lưu lượng mạng
trên Internet được cho là để trao đổi các file đặc biệt là các file âm nhạc (hơn 1
tỷ các file âm nhạc được download mỗi tuần).
- Đặc điểm của vấn đề chia sẻ file là các máy (Peer) có các file được
download với vai trò là một Client làm cho chúng luôn sẵn sàng với các Peer
khác trong vai trò của một Server.
- Vấn đề chủ yếu cho mạng ngang hàng nói chung và cho vấn đề chia sẻ
file nó riêng là vấn đề tìm kiếm. Trong ngữ cảnh của hệ thống chia sẻ file, có ba
mô hình khác nhau được phát triển: mô hình flooded request, mô hình thư mục
trung tâm và mô hình hướng tài liệu. Các mô hình này được minh hoạ qua các
ứng dụng thực của mạng ngang hàng sau: Gnutella, Naspter và FreeNet.
Gnutella : Trong hệ thống Gnutella, không có sự tập trung hoá, các file
được lưu trữ trên các Peer của hệ thống, khi có yêu cầu tìm kiếm một file máy
tính sẽ gửi yêu cầu này tới tất cả các peer là láng giềng của nó và quá trình này
được lặp lại cho tới khi tìm thấy máy chứa file cần tìm. Tiếp theo là quá trình
trao đổi file trực tiếp giữa hai máy tính trong mạng. Hiện nay phần mềm nổi
tiếng sử dụng phương pháp tìm kiếm và chia sẻ file dạng này là Bittorent.
Naspter : Trong hệ thống Naspter, có sự tập trung hoá. Khi một máy
tham gia vào mạng, danh mục các file sẽ được đăng ký và lưu trữ trên Server
trung tâm, khi có yêu cầu tìm kiếm, máy tính sẽ hỏi Server trung tâm về vị trí
của file. Sau đó việc trao đổi file được thực hiện giữa hai máy tính với nhau.
FreeNet: Trong hệ thống Freenet, file không được lưu trữ trên đĩa cứng
của các peer cung cấp chúng mà được lưu trữ ở các vị trí khác trong mạng. Mục
đích của việc phát triển mạng Freenet là làm cho thông tin được lưu trữ và truy
cập mà không cần biết định danh. Với các tổ chức như vậy, chủ sở hữu của một
node mạng cũng không biết được tài liệu gì được lưu trữ trên đĩa cứng của máy
anh ta. Vì lý do này mà các Peer và các file được cung cấp các số định danh
khác nhau. Khi một file được tạo, nó được truyền qua các peer láng giềng tới các
peer có số định danh gần với số định danh của file nhất và được lưu trữ ở đó.
1.4.3. Một số giao thức sử dụng trong các mạng chia sẻ file
-11-
a) Hệ thống Gnutella
Giao thức trong Gnutella là giao thức tìm kiếm phân tán. Giao thức
Gnutella được định nghĩa là lối vào để các servent truyền thông qua mạng. Nó
bao gồm một tập các đặc tả được sử dụng cho truyền thông dữ liệu giữa các
servent và một tập các qui tắc chủ yếu trao đổi bên trong các servent của các
đặc tả.
Mặc dù giao thức Gnutella hỗ trợ tìm kiếm theo dạng chủ-khách truyền
thống, nhưng nét đặc biệt của Gnutella là mô hình không tập trung, dạng peer-
to-peer chính nó. Trong mô hình này, mỗi máy khách cũng đồng thời là máy
chủ. Chính vì vậy, Gnutella còn được gọi là servents thực hiện công việc của cả
máy chủ lẫn máy khách. Chúng cung cấp các giao diện phía máy khách để cho
người sử dụng phát ra các truy vấn và xem các kết quả tìm kiếm được, trong khi
ở cùng thời điểm chúng cũng truy cập các truy vấn ở các servent khác, kiểm tra
tính tương phản của tập dữ liệu cục bộ, và trả lời đối với các kết quả tương
xứng.
Do tính phân tán tự nhiên của chính nó, mà một mạng servents áp dụng
giao thức Glutella sẽ có khả năng kháng lỗi rất cao, việc xử lí của mạng sẽ
không bị ngắt nếu như có một tập các servent xảy ra tình trạng offline.
Việc tìm kiếm trong mạng ngang hàng theo cơ chế lan truyền giữa các
máy gây ra sự chiếm dụng băng thông đường truyền lớn. Trong Gnutella, các
máy vận chuyển truy vấn của các máy khác làm ngập lụt hệ thống. Mỗi thông
báo vận chuyển tiêu thụ băng thông và bộ xử lí ở mỗi nút nó viếng thăm. Cải
thiện vấn đề này chính là khả năng cân bằng tải của mạng.
b) Hệ thống dựa trên giải thuật Chord
Trong Chord, tài liệu được ánh xạ tới nút đặc biệt sử dụng hàm băm. Tuy
vậy mỗi máy phục vụ một tài liệu, tài liệu này trong thực tế được sở hữu bởi một
vài nút khác trong hệ thống. Như vậy các máy trong hệ thống tiêu thụ tài nguyên
của chúng để phục vụ các tài liệu đối với các nút khác trong hệ thống. Tình
trạng này là không duy nhất đối với Chord; tất cả các hệ thống xác định dựa trên
việc băm, bao gồm CAN, Bayeux, Pastry, đều có tính chất này. Điều đó có thể
làm được nhằm xây dựng một hệ thống trong đó các nút chỉ phục vụ một điểm
tới tài liệu và cũng để thực hiện các hệ thống cân bằng tải khác nhau. Như vậy,
-12-
ngay cả trong hệ thống được cân bằng tải tốt nhất, có thể nhất thời xảy ra quá tải
khi một lượng lớn các tài nguyên cục bộ được tiêu thụ do các dịch vụ mở rộng.
c) Một số các giao thức dòng phương tiện dựa trên chuyển mạch
Trong các giao thức này, các nút dành hết tài nguyên (giống như băng
thông) để phục vụ cho các nút con của nó.
Trong mỗi ví dụ trên, bất kì một người sử dụng riêng lẻ có thể chọn không
để dành tài nguyên cục bộ cho các yêu cầu mở rộng, nhưng vẫn nhận được đầy
đủ lợi ích của hệ thống. Trong các trường hợp khác, được tích hợp và chính xác
các hàm của hệ thống tiêu thụ trong mỗi người sử dụng đang thực hiện toàn bộ
giao thức phân tán không ích kỉ và đúng đắn. Như vậy, bằng kinh nghiệm triển
khai các hệ thống, như Gnutella và Napster trước đó, diễn tả rằng chỉ một tập
nhỏ các máy đưa ra như vậy ích kỉ dịch vụ đối với cộng đồng chung, trong khi
phần lớn những người sử dụng sử dụng các dịch vụ được đưa ra bởi một ít hào
phóng này. Mục đích của công việc này là xác định hiệu quả số ít hào phóng và
dạng tất cả những người sử dụng mà đưa ra các dịch vụ cục bộ đối với cộng
đồng chung.
1.5. Thuật toán và độ phức tạp thuật toán
1.5.1. Thuật toán [14]
Thuật toán (algorithm) là một trong những khái niệm quan trọng nhất
trong tin học, là một trong hai thành tố cấu tạo nên chương trình máy tính (cấu
trúc dữ liệu + giải thuật = chương trình).
Theo PGS.TS Hồ Sĩ Đàm [13] định nghĩa thì thuật toán là một dãy hữu
hạn các thao tác, sắp xếp theo một trật tự xác định, sau khi thực hiện, từ Input ta
nhận được Output cần tìm.
1.5.2. Các đặc trưng chính của thuật toán [14]:
a) Input: Mỗi thuật toán cần có một số (có thể bằng không) dữ liệu vào
(input). Đó là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc. Các dữ liệu
này cần được lấy từ các tập hợp cụ thể nào đó.
b) Output: Mỗi thuật toán cần có một hoặc nhiều dữ liệu ra (output). Đó là
các giá trị có quan hệ hoàn toàn xác định với các dữ liệu vào và là kết quả của sự
thực hiện thuật toán.
-13-
c)Tính xác định : Mỗi bước của thuật toán cần phải được mô tả một cách
chính xác, chỉ có một cách hiểu duy nhất.
d) Tính khả thi: Tất cả các phép toán có mặt trong các bước của thuật toán
phải đủ đơn giản, nghĩa là các phép toán phải sao cho, ít nhất về nguyên tắc có
thể thực hiện được bởi con người chỉ bằng giấy trắng và bút chì trong một
khoảng thời gian hữu hạn.
e) Tính kết thúc (tính đóng): Với mọi bộ dữ liệu vào thỏa mãn các điều
kiện của dữ liệu vào (tức là được lấy ra từ các tập giá trị của các dữ liệu vào),
thuật toán phải kết thúc (dừng) sau một số hữu hạn các bước thực hiện.
f) Tính chi tiết [13]: Phụ thuộc vào đối tượng thực hiện
g) Tính phổ dụng [13]: Thuật toán có thể áp dụng với một lớp các bài toán
khi thay đổi đầu vào (input).
h) Tính hiệu quả [13]: Được đặc trưng bởi 2 yếu tố: Thời gian (Tốc độ xử
lý) và không gian (Dung lượng lưu trữ).
• Ví dụ minh họa: Bài toán: tìm phần tử lớn nhất trong 1 dãy hữu hạn các số
nguyên a1, a2,..,an.
• Thuật toán:
– Bước 1:Đặt giá trị cực đại tạm thời max = a1
– Bước 2: So sánh số nguyên tiếp sau với max
• Nếu số nguyên tiếp sau lớn hơn đặt max = số nguyên tiếp
sau
– Bước 3: Lặp lại bước trên nếu còn số nguyên trong dãy
– Bước 4: Dừng khi không còn số nguyên nào.
Số nguyên = max chính là phần tử lớn nhất
• 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: dãy các số nguyên a1,…. an
– Đầu ra: số lớn nhất trong dãy đó
– Tính xác định và khả thi: thuật toán gồm 1 phép gán, 1 vòng lặp
hữu hạn và phép so sánh các bước đều được xác định chính xác
và có thể thi hành.
-14-
– 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 số
nguyên đượ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 số cực đại cho
bất kỳ dãy số nguyên nào
1.5.3. Độ phức tạp của thuật toán
Hiệu quả của thuật toán được phân tích như thế nào?
Khi giải một bài toán, chúng ta cần chọn trong số các thuật toán, một
thuật toán mà chúng ta cho là “tốt” nhất.
Các thước đo tính hiệu quả của 1 thuật toán:
– Thời gian mà máy tính sử dụng để giải bài toán theo thuật toán
đang xét khi các giá trị đầu vào có kích thước xác định
Độ phức tạp thời gian
– Dung lượng bộ nhớ để thực hiện thuật toán khi các giá trị đầu vào
có kích thước xác định
Độ phức tạp không gian
a) Lựa chọn thuật toán:
Dễ hiểu, dễ cài đặt và dễ ghi chép.
Sử dụng các tài nguyên hiệu quả.
b) Ký pháp
Giả sử T(n) là thời gian thực hiện TT và f(n), g(n), h(n) là các hàm xác
định dương.
- Hàm Theta lớn: T(n) là hàm Theta lớn của g(n): T(n) =Θ(g(n))
nếu các hằng số dương c1, c2, n0 sao cho với mọi n>= n0 :
c1 g(n) <= T(n) <= c2 g(n)
- Hàm Omega lớn:
T(n) là hàm Omega lớn của g(n): T(n)=Ω(g(n)) nếu c và n0 sao cho với
mọi n>= n0 thì
-15-
T(n) >= c.g(n)
- Hàm O lớn: T(n) là hàm Omega lớn của g(n), T(n) =O (g(n))
nếu c và n0 sao cho với mọi n>= n0 :
T(n) <=c g(n)
g(n) còn gọi là giới hạn trên của T(n).
c) Các tính chất
(i) Tính bắc cầu: nếu f(n)= O(g(n)) và g(n)= O(h(n)) thì f(n)= O(h(n))
(ii) Tính phản xạ: f(n)=O(f(n))
d) Xác định độ phức tạp
- Quy tắc hằng số:
Nếu P có T(n)= O(c1f(n)) thì gọi P là có độ phức tạp O(f(n)).
CM: T(n)= O(c1f(n)) nên tồn tại c0>0 và n0 >0 để T(n) <= c0.c1 f(n) với mọi
n>= n0. Đặt c=c0.c1 ta có điều cần CM.
- Quy tắc lấy Max
Nếu P có T(n)= O( f(n)+g(n)) thì P có độ phức tạp là O(max( f(n), g(n))).
CM: T(n) = O(f(n)+g(n)) nên tồn tại n0>0 và c>0 để T(n) <= cf(n) + cg(n),
với mọi n>= n0 vậy T(n) <= cf(n) +cg(n) <= 2c max (f(n),g(n)) với mọi n>=n0.
Từ đó suy điều cần CM.
- Quy tắc cộng
Nếu P1 có T1(n) = O(f(n) và P2 có T2(n)= O(g(n)), khi đó: T1(n) +T2(n) =
O(f(n) +g(n)).
CM: Vì T1(n)= O(f(n)) nên các hàng số c1 và n1 sao cho T(n) <= c1.f(n)
n: n>= n1.
Vì T2(n) =O(g(n)) nên các hàng số c2 và n2 sao cho T(n) <= c1.g(n) n:
n>= n2
Chọn c= max (c1,c2) và n0 = max(n1, n2) ta có n: n n>= n0:
T(n) = T1(n) + T2(n) <= c1f(n) + c2g(n)<= cf(n) +cg(n) = c(f(n)+g(n)).
- Quy tắc nhân
-16-
Nếu P có T(n)= O(f(n)). Khi đó nếu thực hiện k(n) lần P với
k(n)=O(g(n)) thì độ phức tạp là O(f(n) g(n)).
CM: Thời gian thực hiện k(n) lần đoạn chương trình P sẽ là k(n) T(n), theo
định nghĩa:
ck>=0 và nk >0 để k(n) <= ck(g(n)) với mọi n>= nk
cT>=0 và nT >0 để T(n) <= cTf(n) với mọi n>= nT
Vậy với mọi n >= max(nT,nk) ta có k(n)T(n) <= ckcT(f(n)g(n)).
e) Áp dụng đánh giá chương trình
- Câu lệnh đơn thực hiện một thao tác => Áp dụng qui tắc hằng số
- Câu lệnh hợp thành là dãy các câu lệnh => Áp dụng qui tắc tổng
- Câu lệnh rẽ nhánh dạng If ..Then..Else. => Áp dụng qui tắc Max
- Các câu lệnh lặp => Áp dụng qui tắc Nhân
Các thuật ngữ dùng cho độ phức tạp của thuật toán
Độ phức tạp
Thuật ngữ
O(1)
Độ phức tạp hằng số
Độ phức tạp logarit
Độ phức tạp tuyến tính
Độ phức tạp nlogn
Độ phức tạp đa thức
O(logn)
O(n)
O(nlogn)
O(nb)
O(bn) b>1 Độ phức tạp hàm mũ
O(n!) Độ phức tạp giai thừa
g) Độ phức tạp tính toán và dữ liệu vào:
- Trường hợp tốt nhất: T(n) là thời gian ít nhất.
- Trường hợp xấu nhất: T(n) là thời gian lớn nhất.
- Trường hợp trung bình: dữ liệu vào tuân theo một phân bố xác suất nào
đó.
h) Phép toán tích cực:
-17-
Là các phép toán thực hiện nhiều nhất trong chương trình.
Trong một chương trình, nếu các phép toán tích cực chiếm thời gian chủ
yếu, còn các phép toán khác chiếm thời gian không đáng kể, thì độ phức tạp thời
gian của chương trình được tính theo các phép toán tích cực.
-18-
Chương 2: Suy luận tin cậy trong mạng ngang hàng
2.1. Khái niệm tin cậy và quản lí tin cậy
a) Khái niệm tin cậy [1]: Tin cậy là mức đặc thù của sự khẳng định chủ
quan theo nghĩa một agent sẽ thực hiện một hành động đặc thù trước khi bị giám
sát và trước khi gây ảnh hưởng trong phạm vi của hành động.
Có ba vấn đề trong định nghĩa tin cậy trên, đó là:
Tin cậy là chủ quan
Tin cậy là ảnh hưởng của những hành động mà không thể giám sát
Mức độ tin cậy phụ thuộc vào các hành động chính nó gây ảnh
hưởng như thế nào.
b) Quản lí tin cậy [4]: Là cơ cấu cho phép thiết lập tin cậy lẫn nhau. Nổi
tiếng là phép đo giúp nhận biết được (bằng trực tiếp hay gián tiếp) các tương tác
sớm của các agent và được sử dụng để định giá mức độ tin cậy của một agent so
với một agent khác.
Tồn tại nhiều phương pháp quản lí tin cậy, tập trung vào các đặc trưng về
mặt ngữ nghĩa của mô hình tin cậy. Các phương pháp này chưa tương xứng với
độ tin cậy của chúng trong cơ sở dữ liệu tập trung hoặc đòi hỏi tới sự duy trì
trong nhận biết tổng thể một agent để cung cấp dữ liệu trong các tương tác sớm.
Cũng có những phương pháp quản lí tin cậy dựa trên cả hai phương diện: quản lí
dữ liệu và mức ngữ nghĩa.
2.2. Mô hình tin cậy
Trong phần này sẽ trình bày tin cậy được định nghĩa như thế nào trong mô
hình tin cậy do Alfarez Abdul-Rahman & Stephen Hailes [1] đề xuất thông qua
mô tả các phần tử của nó.
2.2.1. Agents
Các agent là những thực thể có khả năng thực thi giao thức đề cử
(Recommendation Protocol). Đây là điểm khác biệt giữa các agent với các thực
thể tĩnh (như máy in hay ổ đĩa chẳng hạn). Mọi thực thể đều có thể được đề cử,
nhưng chỉ có các agent là có thể gửi và nhận các đề cử.
2.2.2. Các quan hệ tin cậy
-19-
Một quan hệ tin cậy tồn tại giữa Alice và Bob khi Alice nắm giữ niềm tin
về những điều tin cậy của Bob. Tuy vậy, niềm tin theo hướng ngược lại không
cần thiết ở cùng thời điểm. Trong trường hợp khác, quan hệ tin cậy của Alice chỉ
là một hướng.
Các đặc tính của quan hệ tin cậy là:
- Nó luôn xảy ra giữa hai thực thể
- Nó không đối xứng (chỉ là một hướng)
- Nó là điều kiện chuyển tiếp (bắc cầu)
Có hai kiểu quan hệ khác nhau đáng lưu ý là:
+ Nếu Alice tin cậy Bob thì đây là kiểu quan hệ tin cậy trực tiếp.
+ Nếu Alice tin cậy Bob để đưa ra đề cử về sự tin cậy của các thực thể
khác, thì đây là quan hệ tin cậy đề cử giữa Alice và Bob.
Các quan hệ tin cậy chỉ tồn tại bên trong cơ sở dữ liệu của chính mỗi
agent.
2.2.3. Loại tin cậy
Các agent sử dụng loại tin cậy để biểu thị tin cậy đối với các agent khác
theo các cách khác nhau phụ thuộc vào các đặc trưng riêng hoặc theo khía cạnh
mà thực thể xem xét ở thời điểm hiện tại.
Ví dụ: Chúng ta tin cậy CA chứng thực cặp khóa công cộng (loại Kí-
khóa), nhưng không làm chứng cho các trạng thái tin tưởng của sự nắm giữ khóa
(loại Tin tưởng).
2.2.4. Giá trị tin cậy
Các giá trị tin cậy được sử dụng để giới thiệu các mức độ tin cậy khác
nhau mà một agent có thể có với các agent khác.
-20-
Theo nghĩa tự nhiên thì không có một hệ thống giá trị vũ trụ vì nó sử dụng
ứng dụng riêng biệt. Tuy vậy việc chuẩn hóa là quan trọng để một hệ thống
được đề xuất.
Các giá trị tin cậy trong mô hình này là tương phản với mỗi loại và độc
lập với các giá trị tin cậy của loại khác.
Có hai kiểu giá trị tin cậy được sử dụng:
a) Giá trị tin cậy trực tiếp: thích hợp với quan hệ tin cậy trực tiếp.
b) Giá trị tin cậy đề cử : thích hợp với các quan hệ tin cậy đề cử.
Sau đây là mô tả cho từng trường hợp cụ thể:
Giá trị
Ý nghĩa
-1
0
Không tin cậy
Bỏ qua, không thể tạo được quan hệ tin cậy về agent
Giá trị tin cậy cực tiểu (thấp nhất)
1
2
Giá trị tin cậy trung bình. Hầu hết các thực thể có giá trị tin cậy này
Giá trị tin cậy tốt
3
4
Hoàn toàn tin cậy thực thể này
Ngữ nghĩa giá trị tin cậy trực tiếp
Giá trị
Ý nghĩa
Không tin cậy
-1
0
Bỏ qua, không thể tạo được quan hệ tin cậy về agent
1
Tính chính xác của quyết định của đề cử cho sở hữu tính chất tin
cậy
2
3
4
Ngữ nghĩa giá trị tin cậy đề cử
-21-
2.2.5. Danh tiếng và đề cử
Danh tiếng của một agent là chuỗi ba thành phần: định danh (hoặc tên)
của agent, loại tin cậy và giá trị tin cậy của agent.
Reputation = {Name, Trust-Category, Trust-Value}
Một đề cử là một thông tin tin cậy được truyền đạt, trong đó có chứa
thông tin danh tiếng.
Mỗi agent lưu các bản ghi danh tiếng trong cơ sở dữ liệu riêng của chính
nó và sử dụng thông tin này để tạo các đề cử tới các agent khác.
2.3. Xác định người cộng tác
Phần này giới thiệu kĩ thuật trong việc xác định những người cộng tác và
không cộng tác. Những người sử dụng riêng lẻ có thể suy ra và gán các giá trị
“tin cậy” cho những người sử dụng khác. Những giá trị tin cậy được suy ra
giống như một người sử dụng xem xét những người sử dụng khác để cùng cộng
tác, và được sử dụng để định giá trị tài nguyên trong hệ thống.
Phân tích vấn đề suy luận tin cậy theo các giải pháp phân tán trong 2
phần:
+ Một là thành phần suy luận tin cậy cục bộ mà yêu cầu thông tin tin cậy
giữa những thành phần đứng đầu trong hệ thống như đầu vào (input)
+ Hai là thành phần tìm kiếm phân tán mà có khả năng tập hợp thông tin
tin cậy riêng lẻ này để sử dụng như đầu vào đối với các giải thuật suy luận cục
bộ.
Các hệ thống tồn tại như vậy, ví dụ e-bay, có hệ thống định giá người sử
dụng tập trung. Các hệ thống trao đổi tài nguyên khác, như MojoNation cũng
thực hiện các giải pháp suy luận tin cậy tập trung. Mục đích đặt ra của các hệ
thống là cho phép các ứng dụng mở nơi người sử dụng không đăng kí với một
ủy quyền trở thành một thành phần của hệ thống. Các giải pháp tập trung không
phân chia trong các hệ thống mở, từ đó những người sử dụng nguy hiểm có thể
vượt qua dịch vụ “tin cậy” ở trung tâm với các giao dịch giả mạo. Sử dụng
nhiều nhất hệ thống suy luận tin cậy được phân quyền có lẽ là trang Web PGP.
Trong hệ thống suy luận tin cậy được phân quyền có thể sử dụng để dự đoán
qua các mức tin cậy tùy ý. Không có thành phần thứ 3 tin cậy hoặc nơi tập trung
thông tin tin cậy trong hệ thống. Những người sử dụng trong hệ thống chỉ dự
-22-
trữ thông tin rõ ràng có thể sử dụng đối với lợi ích sở hữu của họ. Một giải thuật
phân chia công bằng với lượng dự trữ được giới hạn ở mỗi nút, và có thể sử
dụng để thực hiện hiệu quả các ứng dụng phân tán rộng lớn. Hơn nữa các giải
pháp trong hệ thống tin cậy cho phép những người sử dụng đơn lẻ tính toán các
giá trị tin tưởng cục bộ đối với những người sử dụng khác sử dụng giải thuật suy
luận lựa chọn của chính họ, và vì vậy có thể sử dụng để thực hiện một loạt chính
sách khác.
2.4. Mô hình suy luận
Trong bài viết này, giả sử rằng các hệ thống P2P có thể được phân tích
bên trong tập các giao dịch 2 thành phần: Một giao dịch đơn có thể có quan hệ
hoạt động nhẹ giống như vận chuyển một truy vấn Gnutella hoặc tiềm tàng một
họat động tài nguyên nặng hơn giống như thuê máy chủ tài liệu Chord. Đồng
thời cũng giả sử rằng hệ thống gồm có một tập các nút “tốt” mà luôn luôn thực
hiện dưới các giao thức chính xác và trọn vẹn, nghĩa là những người tốt luôn thi
hành cuối của một giao dịch của họ. Mục đích công việc ở đây là phát triển các
giải thuật cho phép những người sử dụng “tốt” định danh được những người
“tốt” khác, và như vậy tạo được các nhóm cộng tác thiết thực (robust). Đây là
các nhóm máy, với xác suất cao, mỗi thành phần tham gia hoàn thành đầy đủ
cuối mỗi giao dịch của họ. Một đề cử về họ các giải thuật phân tán có thể được
sử dụng bởi người sử dụng để tính toán giá trị tin cậy đối với mỗi người sử
dụng. Giá trị tin cậy đối với nút B ở nút A là độ đo giống như nút A tin tưởng
giao dịch với nút B sẽ thành công. Trong hệ thống, mỗi người sử dụng lưu trữ
một số giới hạn các thông tin về bao nhiêu người sử dụng khác tin cậy họ, và
giải thuật chọn những thông tin gì để lưu trữ và làm thế nào để tìm lại được
những thông tin này. Một trong những thông tin thích hợp được tập hợp, những
người sử dụng đơn lẻ có thể sử dụng các giải thuật suy luận cục bộ khác để tính
toán các giá trị tin cậy.
Điều quan trọng cần lưu ý là thừa nhận các nút tốt có khả năng xác định
được khi một giao dịch thành công. Rõ ràng trong nhiều trường hợp không rõ
được có hay chăng một giao dịch thất bại (ví dụ khi một nút thỉnh thoảng không
phục vụ các tài liệu Chord mà nó tự thuê). Thường khó khăn hơn khi xác định
phần nào một giao dịch thất bại do bởi hệ thống thất bại hoặc do bởi người sử
dụng không cộng tác.
-23-
Ví dụ: Xem xét trường hợp khi tất cả những người sử dụng cộng tác
nhưng tài liệu không được phục vụ, từ đó mạng thất bại.
Đây là vấn đề vốn có ở bất kì một hệ thống suy luận tin cậy nào dựa trên
các giao dịch chất lượng (quality).
Một hệ thống suy luận tin cậy lí tưởng, trong quá khứ, sẽ có khả năng
phân loại tất cả những người sử dụng thành các lớp cộng tác hoặc không cộng
tác mà không có lỗi. Tuy vậy, điều này không có khả năng trong thực tế vì
những người không cộng tác có thể khởi động bên ngoài những người cộng tác.
Một số hệ thống, chẳng hạn NICE [8], đã đưa ra được các giải thuật với
các mục đích sau:
Cho phép các nút “tốt” tìm các nút khác nhanh hiệu
quả: Các nút tốt sẽ có khả năng xác định các nút tốt khác ngoài sự
mất mát một lượng lớn các tài nguyên tác động qua lại với các nút
nguy hiểm. Điều này cho phép NICE nhanh chóng hình thành các
nhóm cộng tác thiết thực.
Các nút nguy hiểm và tương tự sẽ không có khả năng
bẻ gãy các nhóm cộng tác bằng cách đưa các thông tin thiếu tới các
nút tốt. Đặc biệt, NICE phát triển các giao thức trong đó các nút
nguy hiểm nhanh chóng bị tỉa bớt ra ngoài các nhóm cộng tác. Xa
hơn, NICE giả thiết các nút nguy hiểm có thể khuếch tán tùy ý
thông tin tin cậy, và tập các nút tốt cùng dạng sẽ nhanh chóng
chống lại các cuộc tấn công dạng này.
2.5. Mô hình hệ thống tin cậy NICE:
NICE là viết tắt của “NICE is the Internet Cooperative Environment”
(NICE là môi trường cộng tác trên Internet).
Mục đích của NICE là cung cấp phạm vi các giải thuật tính toán tin cậy
phân tán. NICE là một platform đối với việc thực hiện các ứng dụng phân tán
cộng tác. Các ứng dụng trong NICE mở rộng truy cập tới các tài nguyên ở xa
bằng việc trao đổi các tài nguyên cục bộ. Các giao dịch trong NICE bao gồm các
trao đổi an toàn các chứng thực tài nguyên. Các chứng thực này có thể được giữ
lại với các tài nguyên được đặt tên (ở xa). Những người không cộng tác có thể
mở rộng truy cập “tự do” tới các tài nguyên ở xa bằng cách phát hành các chứng
thực mà các chứng thực này rốt cuộc không được giữ lại.
-24-
NICE cung cấp một dịch vụ API tới các ứng dụng đầu cuối và được phân
tầng giữa các giao thức tầng ứng dụng và tầng vận chuyển. Kiến trúc thành phần
của NICE được giới thiệu ở hình trên. Các ứng dụng tương tác qua lại với NICE
sử dụng NICE API, và phát ra lời gọi để tìm các tài nguyên thích ứng. Tất cả các
giao thức đổi chác, mua bán, bồi thường được thực hiện bên trong NICE và
không bộc lộ tới ứng dụng. Các giao thức con này chia sẻ thông tin bên trong
chính nó và được điều khiển bởi người sử dụng sử dụng các chính sách theo nút
(per-node). Các máy NICE được sắp xếp bên trong giao thức báo hiệu
(signaling) sử dụng giao thức đa phát tầng ứng dụng. Tất cả các thông báo đặc
trưng giao thức NICE khi gửi sử dụng đơn phát trực tiếp hoặc đa phát qua giao
thức báo hiệu này.
Định danh người sử dụng NICE: sau đây sử dụng thuật ngữ nhóm người
sử dụng (user) và nút (node) theo dạng tổng quát. Trong NICE, mỗi người sử
bản mã chuỗi nhận dạng và một khóa công cộng. Khóa kết hợp với định danh
NICE được sử dụng trong việc kí các chứng thực tài nguyên, trong trao đổi tài
nguyên và trong việc gán các giá trị tin cậy.
Điều đó là quan trọng để lưu ý rằng không khóa với cả không định danh
NICE cần thiết để được đăng kí ở một trung tâm ủy quyền bất kì; tuy vậy, cho
dù NICE sử dụng các khóa chung, nhưng không đòi hỏi bất kì dạng PKI toàn
cục. Tuy thế, NICE có thể được sử dụng để thực hiện các ứng dụng P2P mở bên
ngoài bất kì trung tâm ủy quyền nào. Vì lẽ không có trung tâm đăng kí ủy quyền
trong NICE, một người sử dụng có thể tạo ra một số tùy ý các khóa và giả mạo.
Tuy vậy, trong NICE, sự định giá được ghép với định danh và nó có lợi để bảo
vệ khóa đơn của người sử dụng và không thay đổi các khóa thường xuyên. Tính
-25-
chất này làm cho các ứng dụng của NICE chống được một số các tấn công DoS,
điều mà xảy ra được với các hệ thống P2P khác.
Trong NICE, các hành động ứng dụng ở xa được chuyển thành các yêu
cầu tài nguyên cục bộ, và nếu tiện lợi, các tài nguyên cục bộ này được đổi chác
với các tài nguyên khác ở các nút ở xa (Nó cũng được tham gia để mua bán các
tài nguyên thành phần thứ 3 mà lẽ ra chỉ là đổi chác các tài nguyên cục bộ). Hy
vọng không phải mọi yêu cầu ở xa chuyển qua NICE; thay vào đó, những người
sử dụng trao đổi và mua bán các đơn vị tài nguyên (giống như 100Mb lưu trữ
trong 10 ngày, vv). Các tài nguyên đã được xác định sử dụng một phiên bản đơn
giản của W3 RDF. NICE cung cấp các dịch vụ sau đây:
Xác định và quảng cáo tài nguyên
Bảo đảm việc trao đổi và mua bán tài nguyên
Định giá “tin cậy” phân tán.
Các máy trong NICE đổi chác tài nguyên bằng việc trao đổi các thông báo
“giao dịch”. Một thông báo giao dịch định danh tập các tài nguyên chủ yếu tự
nguyện để trao đổi. Sự tích hợp của thông báo giao dịch để đảm bảo sử dụng
chữ kí băm đồng hành theo thông báo.
Trong NICE sử dụng sơ đồ dựa trên Beaconing để mở rộng việc thông
báo và xác định các tài nguyên có hiệu lực. NICE sử dụng một giải thuật trao
đổi mới dựa trên các giao thức vận chuyển để trao đổi các chứng thực tài
nguyên. Giao thức này đảm bảo rằng không bộ phận nào có thể thu được một
chứng thực có thể dùng được ngoài những chứng thực có hiệu lực được phát
hành. Các chứng thực tài nguyên này cuối cùng được giữ ở các nút phát hành.
Các nút tốt luôn luôn giữ bất kì chứng thực mà chúng phát ra, trong khi các nút
nguy hiểm có thể chọn không làm như vậy. Trong phạm vi của NICE, mục đích
đặc biệt của bài viết này là phát triển các giải thuật để định danh các nút mà
phát ra (hoặc giữ) các chứng thực tốt. NICE mô tả thành phần suy luận tin cậy,
các kết quả của hệ thống này được sử dụng để định giá các tài nguyên trong
NICE như thế nào.
Chính sách định giá và mua bán :
Mục đích của các chính sách mặc định trong NICE là giới hạn các tài
nguyên mà có thể bị tiêu thụ bởi các nhóm người nguy hiểm. Các chính sách
-26-
này được kết hợp với sự tính toán tin cậy được sử dụng để định danh các nút
không hoạt động (misbehaving). Trong thực tiễn, những người sử dụng NICE có
thể sử dụng bất kì chính sách riêng biệt, và có thể cố gắng để được số tài nguyên
lớn nhất qua mua bán số tài nguyên được họ sở hữu. Mục đích chính của các
chính sách mặc định là cho phép những người sử dụng tốt hình thành các nhóm
cộng tác và không bị mất một lượng lớn tài nguyên cho những người nguy hiểm.
Các chính sách định giá và mua bán được sử dụng để đề phòng chống lại những
người sử dụng mà phát hành các chính sách tài nguyên giả mạo sử dụng nhiều
đặc tính giống NICE. Trong NICE sử dụng 2 cơ cấu để bảo vệ sự tích hợp nhóm
như sau:
- Định giá dựa trên tin cậy
Trong định giá dựa trên tin cậy, các tài nguyên được định giá tỉ lệ tương
hỗ độ tin cậy nhận biết được. Giả sử khoảng giá trị tin cậy giữa 0 và 1, và xem
xét giao dịch đầu tiên giữa Alice và Bob nơi suy ra được giá trị tin cậy từ Alice
tới Bob là TAlice(Bob) =0.5 và TBob(Alice) =1.0. Theo định giá dựa trên tin cậy,
Alice sẽ chỉ đổi chác với Bob nếu Bob tỏ ra có nhiều tài nguyên hơn cái anh ta
nhận trở về. Lưu ý rằng Bob điều khiển nhiều giao dịch thành công hơn với
Alice, giá chênh lệch sẽ giảm. Chính sách này là động cơ thúc đẩy bởi sự quan
sát rằng Alice mua bán với độ tin cậy thấp cô ta gặp nguy cơ lớn không nhận
được dịch vụ trở lại, mà được phản ánh trong sự định giá.
- Các giới hạn mua bán dựa trên tin cậy
Trong các chính sách này, thay vì thay đổi giá của tài nguyên, chính sách
thay đổi tổng số tài nguyên mà Alice mua bán. Ví dụ, trong cốt chuyện giữa
Alice và Bob, Alice có thể cho phép Bob lưu trữ 1 Mb dữ liệu ở máy của cô ấy
trong 1 ngày, và từ từ tăng lưu trữ và thời gian khi cô ấy hoàn thành việc lưu trữ
các chứng thực tài nguyên của Bob. Chính sách này đảm bảo rằng khi mua bán
chủ yếu bằng quan hệ tin cậy thấp, Alice kề cận với số tài nguyên cô ta có thể
mất.
Phân loại đối tượng người sử dụng trong NICE
Có 3 đối tượng người sử dụng:
Người sử dụng tốt: Những người sử dụng tốt luôn thực hiện giao thức
đúng đắn. Nếu người sử dụng tốt quan hệ với người sử dụng tốt khác thì giá trị
cookie được kí luôn là 1.
-27-
Những người sử dụng bình thường: Những người sử dụng bình thường
luôn thực hiện giao thức đúng đắn. Tuy vậy khi một người sử dụng bình thường
quan hệ qua lại với một người khác, kết quả các giao dịch trong định giá cookie
trong khoảng giữa 0.0 và 1.0, trung bình là 0.7.
Những người sử dụng nguy hiểm: mỗi người sử dụng nguy hiểm luôn báo
độ tin cậy tuyệt đối (giá trị cookie là 1.0) với mỗi người sử dụng nguy hiểm
khác. Những người sử dụng nguy hiểm quan hệ qua lại với người sử dụng không
nguy hiểm khác thì người sử dụng nguy hiểm tạo ra giá trị cookie tin cậy cao
(giữa 0.9 và 1.0) hoặc rất thấp (khoảng giữa 0.0 và 0.1). Xác xuất giao dịch thất
bại là giống nhau và ngẫu nhiên.
2.6. Tính toán tin cậy phân tán trong NICE
Giả sử rằng với mỗi giao dịch trong hệ thống, mỗi người sử dụng liên
quan tạo một bản tuyên bố được ký (và gọi là cookie) về chất lượng của giao
dịch. Ví dụ: xem xét giao dịch đầy đủ t giữa những người sử dụng Alice và Bob
trong đó Alice tiêu thụ một tập tài nguyên của Bob. Sau khi giao dịch hoàn
thành, Alice kí một cookie với tình trạng c mà cô ấy đã hoàn thành đầy đủ giao
dịch t với Bob. Bob có thể chọn lưu trữ cookie c này được kí bởi Alice cho việc
sử dụng sau này để chứng tỏ độ tin cậy của Bob với những người sử dụng khác,
bao gồm cả Alice. Như tiến trình hệ thống, mỗi giao dịch tạo một cookie mới và
được lưu trữ bởi những người sử dụng khác. (Rõ ràng các cookie sẽ hết hạn
hoặc trong trường hợp khác sẽ bị hủy).
Sau đây là mô tả giải thuật suy luận tin cậy trong phạm vi của đồ thị có
hướng T và gọi là đồ thị tin cậy. Các đỉnh trong T thể hiện chính xác những
người sử dụng trong hệ thống. Có một cạnh nối trực tiếp từ Alice tới Bob nếu
và chỉ nếu Bob lưu giữ một cookie của Alice. Giá trị của cạnh Alice → Bob
biểu thị Alice tin cậy Bob bao nhiêu, và phụ thuộc vào tập các cookie Bob nắm
giữ của Alice. Chú ý rằng mỗi giao dịch trong hệ thống có thể thêm một cạnh có
hướng mới khác trong đồ thị tin cậy, hoặc dán lại nhãn giá trị của cạnh đã có với
giá trị tin cậy mới của nó.
Giả sử rằng phiên bản hiện tại của đồ thị tin cậy T là có hiệu lực với
Alice và thừa nhận Alice mong muốn tính toán một giá trị tin cậy đối với Bob.
Nếu Alice và Bob có các giao dịch trước, sau đó Alice có thể tìm kiếm giá trị
của cạnh Alice → Bob trong T. Tuy vậy, giả sử Alice và Bob không bao giờ có
-28-
một giao dịch trước. Alice có thể suy ra giá trị tin cậy đối với Bob bằng các
đường có hướng tiếp theo (kết thúc ở Bob) trong đồ thị tin cậy.
2.6.1. Suy luận tin cậy trong đồ thị tin cậy
Xem xét đường dẫn có hướng A0 → A1 →…→ Ak trong T. Mỗi cặp kế
tiếp là những người sử dụng có các giao dịch trực tiếp với người khác, và các
giá trị cạnh là độ đo nói lên Ai tin cậy bao nhiêu Ai+1. Cho một đường dẫn như
vậy, A0 có thể suy ra số các giá trị tin cậy hợp lý đối với Ak, bao gồm giá trị nhỏ
nhất của một cạnh bất kì trong đường dẫn hoặc tích của các giá trị tin cậy dọc
theo đường dẫn. Gọi các giá trị tin cậy suy ra được này là sự khỏe mạnh
(strength) của đường dẫn A0 → Ak. Bài toán suy luận là những gì khó hơn tính
toán độ khỏe mạnh của các đường dẫn tin cậy vì rằng có thể có nhiều đường dẫn
giữa 2 nút, và những đường dẫn này có thể chia sẻ các cạnh hoặc các đỉnh. Suy
luận tin cậy tập trung không tập trung ở bài viết này, nhưng nó quan trọng cho
việc sử dụng giải thuật suy luận thiết thực. Trong mô tả sau đây, giả sử A
(Alice) truy cập tới đồ thị tin cậy, và muốn suy ra giá trị tin cậy đối với B (Bob):
Hình 2: Đồ thị tin cậy
Đường dẫn khỏe nhất: Lấy một tập các đường dẫn giữa Alice và Bob,
Alice chọn đường dẫn khỏe nhất và sử dụng giá trị tin cậy nhỏ nhất trong đường
dẫn làm giá trị tin cậy đối với Bob. Độ khỏe của một đường dẫn có thể được tính
bằng cách làm cực tiểu giá trị cạnh dọc theo đường dẫn hoặc tính tích của tất cả
các cạnh dọc theo đường dẫn. Cho đồ thị tin cậy, việc đo độ tin cậy này có thể
tính được bằng cách sử dụng tìm kiếm theo chiều sâu (depth-first search). Trong
ví dụ mô tả trong hình 2, có sử dụng hàm cực tiểu để tính độ khỏe của đường
dẫn. Trong ví dụ này, đường dẫn khỏe nhất là AEFB, và Alice suy ra mức tin
cậy là 0.8 đối với Bob.
-29-
Phương pháp tính trung bình trọng số theo các đường dẫn rời rạc khỏe
nhất: Thay cho sự lựa chọn chỉ đường dẫn khỏe nhất, Alice có thể chọn cách
góp từ tất cả các đường dẫn rời rạc. Tập các đường dẫn rời rạc này không duy
nhất, nhưng tập các đường dẫn rời rạc khỏe nhất là và có thể tính được bằng
cách sử dụng các luồng mạng với sự thu hẹp luồng trong các đỉnh. Cho một tập
các đường dẫn rời rạc, Alice có thể tính giá trị tin cậy đối với Bob bằng việc
tính trung bình trọng số của độ khỏe của tất cả các đường rời rạc khỏe nhất.
Trọng số được gán cho đường Alice→X→... →Bob là giá trị của cạnh Alice →
X (được giải thích là Alice trực tiếp tin cậy X bao nhiêu). Trong ví dụ trong hình
2, ACDB là đường rời rạc khác (với độ khỏe mạnh 0.6), và suy ra giá trị tin cậy
từ Alice tới Bob là 0.72. Cách tính như sau: Trước tiên tìm đường dẫn khỏe nhất
(AEFB, hoặc 0.9 -> 0.8 ->0.9 với trọng sô cực tiểu 0.8), loại bỏ các cạnh đó, tìm
đường khỏe nhất tiếp theo (ACDB, 0.6 -> 0.7 -> 0.9 với trọng số cực tiểu là
0.6). Như vậy, lấy 2 đường, Alice tính được trung bình cực tiểu của mỗi đường,
trọng số tính được bằng giá trị của chặng (hop) sau cùng. Theo đó, đường AEFB
có trọng số cực tiểu 0.8 với liên kết AE có giá trị 0.9, cũng tương tự đường
ACDB có trọng số cực tiểu 0.6 với liên kết chặng sau cùng (AC) có trọng số 0.6.
Vậy trung bình trọng số tính được là (0.6*0.6 + 0.8*0.9)/ (0.6 + 0.9) và bằng
0.72.
Cả hai giải thuật này đều thiết thực trong ý nghĩa rằng không có giá trị
cạnh nào được sử dụng nhiều hơn một lần, và các giá trị tin cậy được tính luôn
luôn bị chặn trên bởi giá trị tin cậy cực tiểu của một đường. Trước khi bất kì một
giải thuật cục bộ như vậy được sử dụng, đồ thị tin cậy thu được có thể thay đổi,
và các giá trị (cạnh) được gán cho các cookie. Chú ý rằng để suy ra độ tin cậy
đối với Bob, Alice không cần toàn bộ đồ thị tin cậy, mà chỉ cần tập các đường từ
cô ấy tới Bob.
2.6.2. Gán các giá trị cho các cookie
Về ý tưởng, sau mỗi giao dịch, có thể thực hiện được việc gán một số
thực trong khoảng giá trị thực [0, 1] cho chất lượng của giao dịch và số được
gán này là giá trị của cookie. Trong một số trường hợp, các giao dịch có thể
được tổ chức như vậy là có thể thực hiện được: như trường hợp giả sử rằng
Alice chuyển mã và cung cấp 400 Kbps dòng video cho Bob ở 128 Kbps, và
theo sự chấp thuận trước, Bob kí một cookie với giá trị 0.75 cho Alice. Trường
hợp giao dịch tương tự có thể cho kết quả một cookie với giá trị 0.9 nếu Alice
-30-
Tải về để xem bản đầy đủ
70 trang
08/04/2025
130
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Đảm bảo công bằng trong các ứng dụng cộng tác ngang hàng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_dam_bao_cong_bang_trong_cac_ung_dung_cong_tac_ngang.pdf
