LUẬN VĂN: ĐẢM BẢO CÔNG BẰNG TRONG CÁC ỨNG DỤNG CỘNG TÁC NGANG HÀNG

Chia sẻ: Sunflower Sunflower_1 | Ngày: | Loại File: PDF | Số trang:70

Thêm vào BST

Báo xấu

117
lượt xem 26
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.II. 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.III. 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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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) >= 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) 0 và n0 >0 để T(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) = n0 vậy T(n) = n0: T(n) = T1(n) + T2(n)
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) = nk cT>=0 và nT >0 để T(n) = nT Vậy với mọi n >= max(nT,nk) ta có k(n)T(n) Á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ố O(logn) Độ phức tạp logarit O(n) Độ phức tạp tuyến tính O(nlogn) Độ phức tạp nlogn O(nb) Độ phức tạp đa thức 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-