ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN Ngô Văn Chí BẢNG BĂM PHÂN TÁN VÀ ĐỊNH TUYẾN TRÊN MẠNG NGANG HÀNG LUẬN VĂN THẠC SĨ KHOA HỌC Chuyên ngành: Cơ sở toán học cho tin học Mã số ngành: 60 46 01 10 NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Lê Trọng Vĩnh Hà Nội – 2015 Mục lục Danh sách hình vẽ iii Danh sách bảng v Lời mở đầu 1 Tổng quan mạng ngang hàng 1.1 Giới thiệu mạng ngang hàng 1.2 Sự tiến hóa cấu trúc mạng 1.2.1 Kiến trúc khách–chủ 1.2.2 Kiến trúc lưới 1.2.3 Kiến trúc ngang hàng 1.3 Phân loại 1.4 Tìm kiếm mạng ngang hàng 1.5 Ưu nhược điểm mạng ngang hàng 11 1.5.1 Ưu điểm 11 1.5.2 Nhược điểm 12 1.6 Một số vấn đề mạng ngang hàng 13 1.7 Một số phương pháp định tuyến P2P 16 1.7.1 Mạng tập trung cấu hình tĩnh 17 1.7.2 Mạng ngang hàng mạng chồng lấn 18 i Bảng băm phân tán 2.1 2.2 2.3 21 Bảng băm 21 2.1.1 Bảng địa trực tiếp 21 2.1.2 Bảng băm 22 Băm ổn định 28 2.2.1 Ví dụ 28 2.2.2 Định nghĩa 31 2.2.3 Xây dựng 32 2.2.4 Các tính chất 33 Bảng băm phân tán 35 2.3.1 Định nghĩa 36 2.3.2 Ví dụ 37 2.3.3 Tính chất DHT 38 2.3.4 Cấu trúc DHT 40 2.3.5 Các chế DHT 40 2.3.6 Các giao diện DHT 42 2.3.7 Nhận xét 44 Định tuyến mạng ngang hàng 45 3.1 Định tuyến P2P có sử dụng DHT 45 3.2 Thuật toán CAN Chord 46 3.2.1 Thuật toán CAN 46 3.2.2 Thuật toán Chord 3.2.3 So sánh khả định tuyến thuật toán CAN 52 Chord 58 Kết luận 60 Tài liệu tham khảo 65 ii Danh sách hình vẽ 1.1 Kiến trúc khách – chủ 1.2 Mô hình máy chủ trung tâm 17 1.3 Phương pháp làm ngập mạng chồng lấn 19 1.4 Mô hình mạng siêu ngang hàng 19 2.1 Bảng địa trực tiếp 22 2.2 Bảng băm 24 2.3 Một ví dụ phương pháp bảng băm mở 25 2.4 Một ví dụ phương pháp thử tuyến tính 26 2.5 Một ví dụ hệ thống phân phối thông qua máy chủ cache 29 2.6 Hệ thống phân phối thông qua máy chủ cache với nút lỗi 2.7 Khoảng đơn vị 31 2.8 Một DHT đơn giản 37 2.9 Tra cứu khóa 38 3.1 Mạng CAN 2–chiều với nút Mỗi nút gán cho zone 30 nút phân biệt biên zone tương ứng 47 3.2 Định tuyến đến nút có khoá k(x, y) không gian 2–chiều 48 3.3 Nút N7 đến zone N1 N1 tự chia thành hai phần phần gán cho N7 Cập nhật tập hàng xóm N1:{N7, N2, N6, N5} 50 3.4 Không gian khóa Chord 53 iii 3.5 Bảng finger nút mạng 54 3.6 Kết thực nghiệm mô 61 iv Danh sách bảng 3.1 Quan hệ số lượng nút mạng thời gian định tuyến trung bình 60 v Lời mở đầu Mạng máy tính từ lâu trở thành phần thiếu nhiều lĩnh vực đời sống xã hội từ hệ thống mạng cục dùng để chia sẻ tài nguyên công ty, quan, đơn vị, hệ thống mạng toàn cầu mạng Internet Kiến trúc hệ thống mạng ngày cải tiến phát triển Trong đó, kiến trúc mạng ngang hàng với nhiều đặc tính tốt khả mở rộng cao, khả chịu lỗi tốt, hiệu cao, thu hút ý người sử dụng, nhà nghiên cứu đơn vị phát triển ứng dụng Tất ưu điểm tạo lên cách mạng lĩnh vực mạng truyền thông Rất nhiều ứng dụng lớn xây dựng mạng ngang hàng FreeNet, Napster, BitTorent, Bên cạnh ưu điểm trên, mạng ngang hàng gặp phải vài hạn chế vấn đề định tuyến, vấn đề bảo mật, khả cân tải, Trong đó, việc định tuyến mạng ngang hàng toán quan trọng phức tạp Nó nhà khoa học nước sâu vào nghiên cứu Có nhiều phương pháp thiết kế để phục vụ cho việc định tuyến mạng ngang hàng, số phải kể đến phương pháp như: sử dụng máy chủ trung tâm, chế làm ngập (flooding), cấu trúc mạng siêu ngang hàng, định tuyến theo ngữ nghĩa, phương pháp tồn hạn chế định Phương pháp định tuyến mạng ngang hàng áp dụng ý tưởng bảng băm phân tán [19] mang lại kết tốt đồng thời khắc phục nhược điểm mà phương pháp định tuyến nêu gặp phải Vì vậy, luận văn tập trung nghiên cứu bảng băm phân tán ứng dụng việc định tuyến mạng ngang hàng Cấu trúc luận văn gồm có 03 chương Nội dung chương tóm tắt sau: Chương 1: Tổng quan mạng ngang hàng Trong chương này, luận văn trình bày kiến thức tổng quan kiến trúc mạng, mạng ngang hàng, phân loại mạng ngang hàng thách thức đặt với mạng ngang hàng Cuối chương phân tích hạn chế phương pháp định tuyến xây dựng phương pháp thay tốt Chương 2: Bảng băm phân tán Trong chương này, luận văn trình bày phương pháp phân bố tài nguyên cho thao thêm, xóa, sửa tra cứu thực thời gian O(1) Phương pháp nhắc đến bảng băm, bảng băm gồm ba phần tập liệu S , hàm băm h bảng băm T Các phần tử ei ∈ S sử dụng hàm băm h để xác định vị trí T Trong số môi trường, môi trường mạng, bảng băm T lúc ổn định [16] tác giả xây dựng phương pháp gọi băm ổn định Phương pháp khắc phục tình trạng không ổn định bảng băm T Với đặc tính tốt băm ổn định, người ta áp dụng vào việc tra cứu liệu hệ thống phân tán gọi bảng băm phân tán Phương pháp tỏ hiệu mà mang lại nhiều tính tốt Trong nội dung này, luận văn phân tích cấu trúc, tính chất bảng băm phân tán áp dụng vào thủ tục định tuyến mạng ngang hàng gọi thiệu Chương Chương 3: Định tuyến mạng ngang hàng Trong chương cuối này, luận văn trình bày toán định tuyến mạng ngang hàng có áp dụng ý tưởng bảng băm phân tán Sau đó, luận văn phân tích chi tiết hai thuật toán định tuyến tiêu biểu thuật toán CAN thuật toán Chord Cuối phân tích so sánh kết thực nghiệm đạt được, qua rút kết luận định hướng cho nghiên cứu Chương Tổng quan mạng ngang hàng 1.1 Giới thiệu mạng ngang hàng Mạng ngang hàng (Peer–to–Peer network, P2P network ) loại hệ thống phân tán phi tập trung nút mạng (được gọi peer ) đóng vai trò vừa máy chủ vừa máy khách mô hình khách–chủ Nghĩa là, peer yêu cầu tài nguyên từ peer khác trả lời yêu cầu thời điểm Điều trái ngược với mô hình khách–chủ truyền thống, mà có máy khách gửi yêu cầu đến (hoặc vài) máy chủ (các) máy chủ trả lời yêu cầu Với cách tiếp cận theo mô hình khách–chủ, hiệu toàn hệ thống giảm xuống số lượng máy khách (có yêu cầu dịch vụ) tăng lên Trong đó, mạng ngang hàng, hiệu toàn mạng tăng lên số lượng máy (peer ) thêm vào mạng nhiều Các peer tự tổ chức thành nhóm, nhóm chúng giao tiếp, cộng tác chia sẻ băng thông với giúp hoàn thành công việc mong muốn Ví dụ, hệ thống chia sẻ tệp tin ngang hàng, peer tải lên tải xuống tệp tin lúc tiến trình vậy, peer tham gia vào nhóm peer cũ rời lúc Việc tổ chức nhóm peer thực cách tự động suốt với người Hình 3.4: Không gian khóa Chord nhiệm cho tất khoá phía trước gần theo chiều ngược chiều kim đồng hồ Hình 3.4 ví dụ đơn giản không gian khoá Chord Mỗi chuỗi định danh có độ dài 3–bit nên hệ thống có khoá đánh số từ 000 đến 111 Trong ví dụ này, nút 001 successor khoá 001, nút 100 successor khoá 010, 011 100, Định tuyến Cho không gian khóa Chord, tất khoá xếp liên kết khoá nút Vì vậy, cặp khoá/giá trị cấp phát quản lý DHT hình thành tập tất cặp khoá/giá trị tất nút vòng tròn định danh Chord Các khóa để tra cứu cập nhật hoạt động hiệu nên việc định vị nút chịu trách nhiệm cho khóa thực tế thực cách nhanh chóng Chord có thuật toán định tuyến vô đơn giản, số trạng thái nút yêu cầu Mỗi nút cần lưu trữ nút successor không 53 Hình 3.5: Bảng finger nút mạng gian khoá Khi cần tra cứu khoá, nút chuyển tiếp truy vấn tới nút successor không gian khoá Một số nút định khoá nằm successor Do vậy, khoá phải lưu trữ successor Do đó, successor truyền kết trở lại nút truy vấn gốc Rõ ràng, áp dụng cách số lượng thông điệp tuyến tính gửi trường hợp xấu số nút vòng tròn Bởi vậy, Chord thêm vào chế để tăng cường việc tìm kiếm khoá Mỗi nút trì bảng định tuyến, gọi bảng finger (xem Hình 3.5), liên kết đến nút khác không gian khoá Với không gian khoá có độ dài l–bit bảng finger có tối đa l mục Giả sử, nút có khoá n, hàng thứ i bảng định tuyến nút successor cách nút n 2i−1 vị trí (tức nút successor vị trí n + 2i−1 ) Bảng finger lưu trữ hầu hết l mục, kích thước phụ thuộc vào số lượng khoá nút hình thành DHT Mỗi dòng bảng định tuyến bao gồm khoá, địa IP, số cổng có vài thông tin kế toán khác (book–keeping) Thậm chí với số lượng khoá lớn, có lượng 54 tương đối nhỏ liệu nút mà ảnh hưởng tới việc quản lý tìm kiếm Mỗi dòng bảng finger nút cung cấp thông tin nút gần với khoảng cách liên kết nút nút có thông tin bảng finger tăng lên theo lũy thừa số hai Thuật toán định tuyến Chord khai thác thông tin lưu trữ bảng finger nút Một nút chuyển tiếp truy vấn khoá k cho nút tiền nhiệm (predecessor ) k không gian khoá thông qua bảng finger Khi truy vấn tìm nút n mà k nằm nút n successor n không gian khoá, nút n báo cáo successor n câu trả lời truy vấn Như vậy, cho dù khoá k có xa so với nút gốc, truy vấn định tuyến khoảng cách lớn không gian định tuyến bước Cho đoạn lũy thừa hai bảng finger, bước định tuyến bao phủ nửa khoảng cách lại không gian khoá nút nút đích Kết dẫn đến trung bình có O(log(N )) bước định tuyến cho vòng Chord với N nút tham gia Stoica đồng nghiệp chứng minh thời gian tra cứu trung bình 21 log(N ) bước Khả tự tổ chức Hệ thống Chord mô tả cho phép nút tham gia rời bỏ hệ thống cách dễ dàng chống lại nút lỗi cách hiệu • Tham gia Thứ tự để nút tham gia vào Chord sau: nút phải định giá trị khoá n Giao thức gốc Chord không áp đặt hạn chế lựa chọn Với nút n, nút o khác phải biết tồn n hệ thống Bằng việc truy vấn đến o với khoá mà nút n sở hữu, n nhận successor s n thông báo diện dẫn đến việc phải cập nhật predecessor s thành n Sau đó, nút n xây dựng bảng finger việc thực truy vấn tới o để tìm successor 55 vị trí n + 20 , n + 21 , n + 22 , Lúc này, n có bảng finger trỏ liên kết đến successor hợp lệ Tuy nhiên, n mặt bảng finger nút khác Đặc biệt, n predecessor successor từ thuật toán tra cứu không thích hợp cho việc định predecessor nút • Giao thức ổn định Chord giới thiệu giao thức ổn định để xác nhận cập nhật trỏ successor đến nút tham gia rời bỏ hệ thống Tính ổn định đòi hỏi phải bổ sung thêm trỏ predecessor thực cập nhật định kỳ nút Hàm ổn định nút k yêu cầu successor k trả lại predecessor p Nếu p k, k successor chấp nhận predecessor successor tương ứng Thực tế, p nằm k successor p thêm vào vòng Chord successor k Do đó, nút k cập nhật trỏ successor tới p thông báo p trở thành predecessor Với giao thức ổn định, nút n không chủ động xác định predecessor Thay vào đó, predecessor tự phát sửa trỏ successor predecessor không ổn định cách chạy thủ tục (thủ tục stabilize()) Sau nút n học predecessor nó, chép toàn khoá mà chịu trách nhiệm, khoá nằm predecessor n n, predecessor n xóa khoá Lúc này, tất trỏ successor cập nhật truy vấn định tuyến đắn chậm Từ đó, nút n không xuất bảng finger nút khác, chuyển tiếp truy vấn tới predecessor n n phù hợp Sau đó, nút predecessor n cần phải chuyển tiếp truy vấn tới n theo trỏ successor Số lượng nút bảng finger cần cập nhật theo thứ tự O(log(N )) với 56 hệ thống có N nút Dựa vào việc bố trí bảng finger, nút xác định nút với bảng finger hạn predecessor(n + 2i−1 ) với < i ≤ l Tuy nhiên, ảnh hưởng bảng finger hạn nên hiệu tra cứu nhỏ đối mặt với nhiều nút tham gia, việc cập nhật bảng finger tốn Do đó, Chord cập nhật bảng finger Tương tự giao thức ổn định, giao thức sửa bảng finger cho nút n chạy theo chu kỳ Giao thức sửa bảng finger đặt cho hàng i (1 < i ≤ l) bảng finger giá trị ngẫu nhiên thực tìm successor thực cho vị trí n + 2i−1 • Nút lỗi Chord giải nút lỗi với nhiều cấp độ Để phát nút lỗi, tất liên lạc với nút khác cần phải kiểm tra thời gian chờ Khi đó, nút phát nút lỗi bảng finger tra cứu, chọn nút tốt trước nút bảng định tuyến Từ đó, khoảng thời gian chờ ngắn đủ, hiệu tra cứu không bị ảnh hưởng trường hợp Giao thức sửa đảm bảo nút lỗi xóa khỏi bảng finger Độ xác thông tin successor tính xác tra cứu đặc biệt quan trọng cần phải trì Ví dụ, ba nút bảng finger nút n đồng thời bị lỗi bảng finger f sống không thực successor sống s Do đó, nút n giả sử khoá k cấp phát f cấp phát s theo gửi câu trả lời sai cho truy vấn từ k Giao thức ổn định bị lỗi tương tự nhiều nút bị lỗi chí bảng finger sống sử dụng cho việc lưu trữ successor bị lỗi Để trì trỏ successor hợp lệ xuất nhiều nút lỗi đồng thời, nút nắm giữ danh sách successor có độ dài r Thay 57 sử dụng trỏ successor, sử dụng r successor nút Khi đó, nút phát successor bị lỗi nó, trả lại nút successor sống danh sách Trong chạy giao thức ổn định, danh sách successor với nút lỗi sửa chữa cách làm tăng với việc thêm vào successor từ nút sống danh sách Vòng Chord bị ảnh hưởng tất nút danh sách successor đồng thời bị lỗi Một nút bị lỗi nghĩa kết nối với mà liệu quản lý bị Dữ liệu bị từ nút ngăn chặn việc nhân liệu cho nút khác Trong Chord, nút successor nút lỗi chịu trách nhiệm cho khoá liệu nút lỗi Do đó, ứng dụng tiện ích Chord nhân liệu cho nút successor • Rời bỏ Xử lý nút chủ động rời khỏi hệ thống tương tự việc xử lý nút lỗi không ảnh hưởng tới tính ổn định mạng Tuy nhiên, xử lý nút chủ động rời khỏi mạng hiệu nút lỗi cần phải phát sửa chữa lại Do đó, nút rời khỏi mạng chuyển khoá tài nguyên mà quản lý, lưu trữ cho successor thông báo tới tất successor predecessor Điều đảm bảo liệu mà nắm giữ không bị thông tin định tuyến nguyên vẹn 3.2.3 So sánh khả định tuyến thuật toán CAN Chord Hai thuật toán CAN Chord cài đặt giao diện DHT có cách tổ chức nút mạng khác Phần này, thực thực nghiệm để đánh giá hiệu định tuyến hai thuật toán với số lượng 58 nút mạng tham số khác Kịch thực nghiệm Thực nghiệm thực hai bước sau: • Bước 1: Xây dựng mạng ngang hàng mô với số nút cho trước Trong Bảng 3.1, cột thứ chứa thông tin số lượng nút mạng thức nghiệm Số lượng nút mạng 128 nhiều 8192 nút mạng Thực nghiệm sau tăng số nút mạng lên gấp hai lần thực nghiệm trước Trong bước này, chương trình mô tạo nút mạng (được lưu trữ nhớ máy tính) Các nút mạng tự động liên kết với để hình thành lên mạng chồng lấn • Bước 2: Tính thời gian định tuyến trung bình trường hợp tương ứng với số nút mạng Thời gian định tuyến tính thời gian chuyển tiếp thông điệp từ nút nguồn nhận lại kết (nếu không nhận kết trả không tính truy vấn môi trường mô phỏng, xác suất xảy trường hợp thấp) Mỗi lần thực nghiệm thực định tuyến 50 lần, thời gian định tuyến trung bình tính tổng thời gian chia cho số lần định tuyến Ở bước này, nút tự sinh thông điệp cách ngẫu nhiên gửi thông điệp đến nút đích chờ thông điệp phải hồi trở lại Thời gian định tuyến thông điệp tính thời gian từ lúc thông điệp gửi đến lúc nút nguồn nhận lại thông điệp trả lời Kết Bảng 3.1 thể quan hệ số lượng nút mạng thời gian định tuyến trung bình áp dụng thuật toán CAN 2–chiều, 3–chiều thuật toán Chord 59 Số lượng nút mạng CAN 2D CAN 3D Chord 128 0.1500580969 0.2178938356 0.0426247554 256 0.1994710127 0.3032350783 0.0415086840 512 0.2298036937 0.3713765900 0.0952941536 1024 0.3093046722 0.4559075342 0.1259631849 2048 0.4452054795 0.5529904599 0.2960035470 4096 0.5858304795 0.7119771282 0.7147596624 8192 0.8543297456 0.8567606409 1.4540423190 Bảng 3.1: Quan hệ số lượng nút mạng thời gian định tuyến trung bình Nhận xét Hình 3.6 cho ta thấy rằng, số lượng nút mạng tăng lên làm tăng thời gian định tuyến trung bình Tuy nhiên, thực nghiệm cho ta thấy: số lượng nút mạng tăng theo hàm mũ (cơ số 2) thời gian định tuyến trung bình thuật toán CAN có tốc độ tăng tuyến tính Đồng thời, số chiều không gian khóa thuật toán CAN tăng lên thời gian định tuyến trung bình thuật toán giảm Dễ dàng giải thích điều số chiều tăng lên số lượng nút hàng xóm nút tăng theo (số hàng xóm tối đa 2d với d số chiều) Do số lượng hàng xóm nhiều lên việc tìm tới đích thông điệp thực nhanh chóng Trong đó, thuật toán Chord, số lượng nút hàng xóm nút cố định (tối đa độ dài khóa), số nút mạng tăng lên thời gian định tuyến trung bình tăng nhanh so với thuật toán CAN Nhưng bù lại, trường hợp xảy cố thuật toán Chord nhanh chóng phát vị trí xảy lỗi cách kiểm tra định kỳ nút mạng lưu trữ bảng finger sửa chữa lại Còn CAN, khó khăn việc thu hồi lại zone cấp phát nên việc tăng số chiều không gian khóa CAN không tốt trường hợp mạng hay xảy lỗi 60 Hình 3.6: Kết thực nghiệm mô 61 Kết luận Kết thu Mô hình mạng ngang hàng chứng tỏ vai trò quan trọng hoạt động thực tiễn Tuy nhiên, tồn nhiều vấn đề thách thức cần phải nghiên cứu giải Luận văn tập trung giải toán định tuyến mạng ngang hàng nhằm nâng cao độ xác định tuyến giảm độ trễ Những kết mà luận văn đạt sau: • Thứ nhất, luận văn trình bày kiến thức tổng quan mạng ngang hàng ứng dụng mạng ngang hàng triển khai thực tế Qua đó, ta thấy vai trò quan trọng mạng ngang hàng truyền thông xu hướng tương lai Từ phân tích lợi ích phát triển nhanh chóng mạng ngang hàng thấy mô hình mạng ngang hàng thay mô hình mạng truyền thống Tuy nhiên, để đạt điều đó, mô hình mạng ngang hàng cần phải giải nhiều vấn đề thách thức, vấn đề đặt thân mô hình mạng yếu tố khách quan khác hạng tầng mạng, phần cứng, Hiện nay, có nhiều nghiên cứu sâu vào tìm hiểu giải vấn đề thách thức lại mạng ngang hàng • Thứ hai, hướng tiếp cận để giải toán định tuyến mạng ngang hàng áp dụng ý tưởng bảng băm phân tán 62 Trong Chương 2, luận văn trình bày kiến thức bảng băm, bảng băm ổn định bảng băm phân tán Theo thứ tự xếp, bảng băm sau khắc phục nhược điểm cải tiến ưu điểm bảng băm trước Như biết, bảng băm cấu trúc hiệu so với cấu trúc khác toán tra cứu như: tìm kiếm, bảng địa trực tiếp, Chính vậy, áp dụng bảng băm phân tán vào toán định tuyến mạng ngang hàng thu kết tốt so với phương pháp khác Hiện nay, có số ứng dụng thực tế áp dụng bảng băm phân tán vào thủ tục định tuyến cho kết tốt BitTorrent, Kademlia, • Thứ ba, luận văn xem xét thuật toán định tuyến mạng ngang hàng áp dụng ý tưởng bảng băm phân tán thuật toán CAN thuật toán Chord Hai thuật toán hai đại điện tiêu biểu cho hai lớp thuật toán là: i) lớp nút có hàng xóm gần không gian khóa ii) lớp nút có hàng xóm cách theo lũy thừa không gian khóa Cuối cùng, luận văn thực mô hai thuật toán so sánh kết thu từ rút nhận xét thú vị Các vấn đề tồn Luận văn chủ yếu tập trung vào việc áp dụng ý tưởng bảng băm phân tán vào việc định tuyến mạng ngang hàng Tuy nhiên, vấn đề rộng nên trình bày hết khuôn khổ luận văn Luận văn xem xét cài đặt thuật toán môi trường mô mà chưa cài đặt môi trường thực tế nên chưa thể đánh giá cách xác kết thực nghiệm 63 Hướng phát triển Có thể thấy mạng ngang hàng chủ đề quan tâm nghiên cứu mạng nên thời gian tới nên tiếp tục nghiên cứu cải tiến thêm thuật toán định tuyến để tổ chức nút mạng gần với mặt logic địa lý nhằm làm giảm bớt thời gian truyền thông hai nút mạng Trong năm gần đây, thiết bị di động có phát triển vượt bậc, kèm với mạng không dây phát triển theo Tuy nhiên, mạng không dây biết đến không ổn định dẫn đến ứng dụng sử dụng loại mạng không ổn định theo Chính vậy, tương lai nghiên cứu thiết kế mạng ngang hàng đáp ứng với mạng không ổn định mạng không dây 64 Tài liệu tham khảo [1] Nguyễn Đình Hóa, Cấu trúc liệu giải thuật, NXB ĐH Quốc gia Hà Nội [2] Aberer, K., Datta, A., Hauswirth, M.: Efficient, self-contained handling of identity in peer–to–peer systems IEEE Transactions on Knowledge and Data Engineering 16(7), 858–869 (2004).DOI 10.1109/TKDE.2004.1318567 [3] Bryan, D., Jennings, C.: A p2p approach to sip registration and resource location 2005 [4] Chavan G T., Mahajan M A Load Balancing in P2P networks using DHT based systems and Ant based systems: A Comparison Sinhgad College of Engineering, Pune [5] Cormen Thomas H., Leiserson Charles E., Rivest Ronald L., Stein Clifford Introduction to Algorithms MIT Press and McGraw–Hill, 2001 pp 221–252 [6] Emmanuel S., Tim C., Colm R., Rob M Peer to Peer Routing, http://ntrg.cs.tcd.ie/undergrad/4ba2.05/group6/ [7] G Greg Plaxton, Rajmohan Rajaraman, Andréa W Richa A Accessing nearby copies of replicated objects in a distributed environment s.l :Proceeding ACM SPAA (Newport, Rhode Island, 06/1997) [8] Groove networks http://www.groove.net/ (2004) 65 [9] Hari Balakrishnan, M Frans Kaashoek, David Karger, Robert Morris, Ion Stoica Looking up data in P2P systems s.l : MIT Laboratory for Computer Science [10] Horozov, T., Grama, A., Vasudevan, V., Landis, S.: Moby-a mobile peer– to–peer service and data network In: International Conference on Parallel Processing, Proceedings, pp 437–444 (2002) [11] Hu, Y., Das, S., Pucha, H.: Peer–to–peer overlay abstractions in manets In: J Wu (ed.) Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer–to–Peer Networks, pp 845–864 Auerbach Publications (2005) [12] Ion Stoica, Robert Morris, David Liben–Nowell, David R Karger, M Frans Kaashoek, Frank Dabek, Hari Balakrishnan Chord: A Scalable Peer–to– peer Lookup Protocol for Internet Applications s.l : ACM SIGCOMM (San Diego, Aug 2001) [13] Iterbeke, Frédéric, Melis, Stijn and Bart De Vleeschauwe, Tim Wauters, Filip De Turck, Bart Dhoedt, Piet Demeester An open peer-to-peer based platform for scalable multimedia communication s.l : Ghent University – IBBT – IMEC, Department of Information Technology Gaston Crommenlaan bus 201, 9050 Gent, Belgium [14] Jelasity, M., Kermarrec, A.M.: Ordered slicing of very large-scale overlay networks In: Proc Sixth IEEE International Conference on Peer-to-Peer Computing P2P 2006, pp 117–124 (2006) DOI 10.1109/P2P.2006.25 23 Kawulok, L., Zielinski, K., Jaeschke, [15] Knuth, Donald The Art of Computer Programming Addison–Wesley, 1998 pp 513–558 [16] Karger D., Lehman E., Leighton T., Panigrahy R., Levine M., Lewin D Consistent hashing and random trees Proceedings of the twenty-ninth an66 nual ACM symposium on Theory of computing (ACM Press New York, NY, USA): 654–663 doi:10.1145/258533.258660 [17] Karger, D., Web caching with consistent hashing [18] Kirsten Hildrum, John D Kubiatowicz, Satish Rao, Ben Y Zhao Distributed Object Location in a Dynamic Network s.l : Proceeding 14th annual ACM symposium on Parallel algorithms and architectures (08/2012) [19] Klaus Wehrle, Stefan G¨otz, Simon Rieche, Peer–to–peer systems and applications s.l : University of T¨ ubingen [20] Litwin, Witold Linear hashing: A new tool for file and table addressing Proc 6th Conference on Very Large Databases: 212–223, 1980 [21] Mehlhorn, Kurt; Sanders, Pete “Hash Tables and Associative Arrays”, Algorithms and Data Structures The Basic Toolbox, Springer, pp 81–98 [22] Pourebrahimi B., Bertels K., Vassiliadis S A Survey of Peer-to-Peer Networks Computer Engineering Laboratory, ITS, TU Delft, The Netherlands [23] Sarmady, Siamak A survey on Peer–to–Peer and DHT s.l : Grid Lab, School of Computer Science, Universiti Sains Malaysia, Penang, 11800, Malaysia [24] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker A Scalable Content–Addressable Network s.l : ACM SIGCOMM (San Diego, CA, August 2001), pp 161–172 [25] Thomas H Cormen; Charles E Leiserson; Ronald L Rivest; Clifford Stein Rivest “Hash Table”, Introduction to algorithms edition, pp 253–285 [26] Xuemin S., Heather Y., John B., Mursalin A Handbook of Peer–to–Peer Networking, Springer 67 ... pháp định tuyến sử dụng bảng băm phân tán Thuật toán định tuyến có sử dụng bảng băm phân tán hữu dụng hệ thống chia sẻ tệp tin tài nguyên khác mạng ngang hàng Chương thảo luận vấn đề định tuyến mạng. .. nội dung này, luận văn phân tích cấu trúc, tính chất bảng băm phân tán áp dụng vào thủ tục định tuyến mạng ngang hàng gọi thiệu Chương Chương 3: Định tuyến mạng ngang hàng Trong chương cuối này,... (flooding), cấu trúc mạng siêu ngang hàng, định tuyến theo ngữ nghĩa, phương pháp tồn hạn chế định Phương pháp định tuyến mạng ngang hàng áp dụng ý tưởng bảng băm phân tán [19] mang lại kết