Khóa luận Tối ưu hóa topology cho mạng ngang hàng có cấu trúc chord

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Đặng Ngọc Bền TỐI ƯU HÓA TOPOLOGY CHO MẠNG NGANG HÀNG CÓ CẤU TRÚC CHORD KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ Thông tin Cán bộ hướng dẫn: TS. Nguyễn Hoài Sơn HÀ NỘI - 2009 LỜI CẢM ƠN Em xin chân thành cảm ơn các thầy cô giáo trong trường Đại học Công nghệ - Đại học Quốc gia Hà Nội đã tận tình giúp đỡ và truyền đạt kiến thức cho em trong suốt 4 năm học qua để em có đủ kiến thức hoàn thành khóa luận này. Đặc biệt, em xin gửi lời cảm ơn sâu sắc tới thầy Nguyễn Hoài Sơn – người đã nhiệt tình động viên, định hướng em trong quá trình định hình, nghiên cứu và hoàn thành khóa luận. Em xin cảm ơn sự nhiệt tình chia sẻ kinh nghiệm, đóng góp ý kiến của nhóm nghiên cứu do thầy Nguyễn Hoài Sơn hướng dẫn, của các anh chị cao học. Em xin gửi lời cảm ơn chân thành tới thầy Nguyễn Đại Thọ, người đã giảng dạy cho em những kiến thức cơ bản liên quan trực tiếp đến đề tài của khóa luận. Mặc dù đã rất cố gắng hoàn thành khóa luận này, xong khóa luận sẽ khó tránh khỏi những thiếu sót, kính mong quý thầy cô tận tình chỉ bảo giúp em. Một lần nữa em xin cảm ơn tất cả mọi người. Hà Nội, tháng 5 năm 2009 Sinh viên Đặng Ngọc Bền Tóm tắt Ngày nay, Internet đã thực sự phát triển và đi sâu vào đời sống của mỗi con người. Khả năng chia sẻ những tài nguyên lớn một cách nhanh chóng và hiệu quả luôn nhận được quan tâm từ những người nghiên cứu cũng như sử dụng Internet. Với những đặc điểm phù hợp, mạng ngang hàng, đặc biệt là mạng ngang hàng có cấu trúc ngày càng được sử dụng phổ biến cho các ứng dụng nêu trên. Tuy nhiên, bên cạnh những ưu điểm, mạng ngang hàng có cấu trúc cũng bộc lộ những hạn chế nhất định, làm tiêu tốn băng thông và khả năng của mạng cũng như ứng dụng. Vì thế, vấn đề tối ưu mạng ngang hàng có cấu trúc, khắc phục những nhược điểm còn tồn tại trở lên cần thiết. Khóa luận sẽ trình bày một giải pháp tối ưu mạng ngang hàng cấu trúc Chord - một giao thức của mạng ngang hàng có cấu trúc - dựa trên thời gian trễ. Giải pháp tập trung giải quyết vấn đề khác biệt về topo (topology mismatch) qua hai quá trình: lựa chọn vị trí tham gia mạng của nút và tối ưu bảng định tuyến. Tiêu chí dùng để tối ưu chính là thời gian trễ giữa các nút tham gia. Giải pháp này đã được thử nghiệm trên chương trình mô phỏng với môi trường mạng ảo có thời gian trễ gần giống với Internet. Kết quả cho thấy, giải pháp tối ưu đã đem lại hiệu quả với việc làm giảm thời gian trễ và chi phí truyền thông trong các truy vấn tìm kiếm. Theo đó, hiệu năng của mạng và ứng dụng cũng được nâng lên. Mục lục Danh mục hình ảnh Hình 1. Mô hình mạng ngang hàng 3 Hình 2. Mô hình mạng khách chủ 4 Hình 3. Mạng ngang hàng lai thế hệ thứ nhất (Napster) 7 Hình 4. Mạng ngang hàng thuần túy (Gnutella 0.4, FreeNet) 8 Hình 5. Kiến trúc siêu ngang hàng(Gnutella 0.6, JXTA) 9 Hình 6. Cơ chế của bảng băm phân tán (DHT) 11 Hình 7. Mạng ngang hàng có cấu trúc Chord dạng vòng tròn. 12 Hình 8. Một mạng Chord với 3 nút 13 Hình 9. Lưu giữ key trong mạng Chord 14 Hình 10. Bản đồ miền trong không gian hai chiều 18 Hình 11. Tính toán với các điểm mốc 21 Hình 12. Tính toán với nút thông thường 21 Hình 13. Biểu đồ không gian Cantor với C=8 22 Hình 14: Bảng định tuyến giả định của N51 trong Quasi-Chord 23 Hình 15: Lựa chọn vị trí tham gia mạng 26 Hình 16: Mô hình mạng thực tế 29 Hình 17: Mô hình mạng mô phỏng 31 Hình 18: Biểu đồ thời gian trễ trung bình của Chord truyền thống và cải tiến 38 Hình 19: Biểu đồ thời gian trễ trung bình biến đổi theo CHOICE 38 Hình 20: Biểu đồ thời gian trễ trung bình theo EXPANSION 39 Hình 21: Biểu đồ thời gian trễ trung bình thay đổi theo lượng miền 40 Hình 22: Biểu đồ thời gian trễ trung bình thay đổi theo lượng nút tối đa 41 Mở đầu Trong những năm gần đây, công nghệ ngang hàng (peer-to-peer - P2P) hay mạng ngang hàng đã trở nên phổ biến trong các nghiên cứu về lĩnh vực Internet. So với các mô hình mạng khác, mạng ngang hàng có nhiều ưu điểm như khả năng mở rộng, không tồn tại điểm chết, khả năng của hệ thống tỉ lệ với số lượng máy tham gia,.. Tất cả những đặc điểm trên đã tạo lên công nghệ P2P và các ứng dụng ngang hàng liên quan. Nhiều ứng dụng lớn đã và đang được xây dựng trên mạng ngang hàng như FreeNet, Napster, Gnutella, BitTorrent, eMule.... Mạng ngang hàng có cấu trúc sử dụng giải thuật DHT (Distributed Hash Table – bảng băm phân tán) tạo nên một mạng phủ (overlay) trên mạng liên kết vật lý. Giải thuật này định nghĩa liên kết giữa các nút mạng trong mạng phủ theo một cấu trúc cụ thể, đồng thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với một phần dữ liệu chia sẻ trong mạng. Mỗi nút đều được kết nối với một tập các nút khác gọi là tập nút láng giềng. Chord là một giao thức của mạng ngang hàng có cấu trúc với không gian địa chỉ một chiều dạng vòng. Mạng ngang hàng cấu trúc Chord ngày càng thể hiện nhiều ưu điểm như khả năng mở rộng, cân bằng tải, định tuyến,... Giống như những giao thức trên mạng có cấu trúc khác, mỗi nút trong Chord xây dựng một bảng định tuyến giúp cho việc tìm kiếm thông tin giảm từ O(N) với N là số lượng tối đa nút trong mạng, xuống còn O(log2N). Trong mạng ngang hàng có cấu trúc nói chung và Chord nói riêng, quan hệ hàng xóm của các nút được thiết lập mà không xem xét đến topo (topology) tầng dưới. Đó chính là nguyên nhân gây ra sự sai khác giữa topo của mạng DHT và topo mạng liên kết vật lý (topology mismatch). Điều này làm cho độ trễ truyền thông báo giữa các nút và chi phí truyền thông trong mạng P2P. Yêu cầu đặt ra là làm sao để tối ưu mạng phủ, khắc phục sự khác biệt đó. Ngoài ra, khi xây dựng bảng định tuyến trong cấu trúc Chord, liên kết tại hàng thứ i được chọn cố định là nút quản lý định danh k+2i. Như vậy, quá trình xây dựng liên kết trong bảng định tuyến cũng không xem xét đến quan hệ giữa các nút ở tầng dưới. Nếu như liên kết này có thời gian trễ lớn thì tất cả những truy vấn đi qua nó đều bị ảnh hưởng bởi độ trễ này. Quá trình chuyển tiếp truy vấn là đưa truy vấn đến vị trí mà khóa cần tìm kiếm thuộc lân cận của vị trí đó. Vì thế, phương pháp hiện có để xây dựng các liên kết trong bảng định tuyến là chưa tốt. Khóa luận này sẽ đề xuất một phương pháp mới để giải quyết hai vấn đề nêu trên xảy ra với mạng ngang hàng có cấu trúc nói chung và cấu trúc Chord nói riêng. Vẫn dựa trên cấu trúc và định tuyến của Chord truyền thống, trong đề xuất mà khóa luận đưa ra, thứ nhất, các nút tham gia vào mạng sẽ lựa chọn vị trí theo tiêu chí mà tại đó, nút được chọn có thời gian trễ tới các nút liền trước và liền sau là nhỏ nhất; thứ hai, bảng định tuyến của nút sẽ được thay đổi bằng cách lựa chọn lại các nút đích của các liên kết từ một tập nút nào đó cũng theo tiêu chí thời gian trễ nhỏ nhất, nhằm tiết kiệm chi phí đường đi của các thông báo. Hai đề xuất sẽ giải quyết lần lượt vấn đề khác biệt về topo và xây dựng liên kết trong bảng định tuyến dựa vào thời gian trễ. Để đánh giá hiệu quả của giải pháp đề xuất, khóa luận xây dựng một chương trình mô phỏng giả lập mạng Internet và đo thời gian trễ truyền thông báo giữa các nút trong mạng Chord. Các kết quả thử nghiệm chứng minh cho khả năng của giải pháp đề xuất trong việc giảm thời gian truyển thông báo trên mạng, kéo theo giảm chi phí truyền thông. Khóa luận được chia thành năm chương: Chương 1: Giới thiệu tổng quan về ngạng ngang hàng, ưu nhược điểm và sự phân loại mạng ngang hàng; những kiến thức cơ bản về DHT và đặc biệt là cấu trúc Chord. Chương 2: Đề cập đến sự tối ưu hóa trong mạng Chord, các vấn đề và các nghiên cứu cho những vấn đề đó. Chương 3: Đề xuất giải pháp tối ưu cấu trúc Chord dựa trên độ trễ, những ưu nhược điểm của giải pháp đó. Chương 4: Xây dựng chương trình mô phỏng, các bước thực thi chương trình và những đánh giá từ kết quả đạt được. Chương 5: Kết luận, những vấn đề nảy sinh và hướng đi tiếp theo. Chương 1. Tổng quan Mạng ngang hàng (mạng đồng đẳng, peer-to-peer, P2P) hay công nghệ ngang hàng đã trở thành thuật ngữ phổ biến trong công nghệ thông tin nói chung và trong lĩnh vực Internet nói riêng. Các ứng dụng trên mạng ngang hàng xuất hiện ngày càng nhiều, thu hút đông đảo người dùng máy tính. Rất nhiều công ty, ứng dụng với công nghệ ngang hàng đã trở lên nổi tiếng, được đông đảo cư dân mạng sử dụng như: Usenet, Freenet, Napster, Gnutella, BitTorrent… Trong điều kiện Internet ngày càng phát triển, lượng thông tin truyền tải và chia sẻ ngàng càng lớn, mô hình client server bộc lộ nhiều hạn chế về băng thông và sức mạnh, mạng ngang hàng với nhiều ưu điểm nổi bật có thêm nhiều cơ hội mới để phát triển. Chương này, khóa luận sẽ giới thiệu về mạng ngang hàng, những ưu nhược điểm của mạng ngang hàng để biết tại sao chúng lại được sử dụng rộng rãi như vậy. Phân biệt được các loại mạng ngang hàng, đặc điểm, cách hoạt động của từng loại. Và hơn hết, chúng ta sẽ làm quen với cấu trúc Chord, một trong những giao thức phổ biến nhất trong mạng ngang hàng có cấu trúc. Mạng ngang hàng Định nghĩa Mạng ngang hàng, là một mạng máy tính trong đó hoạt động của mạng chủ yếu dựa vào khả năng tính toán và băng thông của các máy tham gia chứ không tập trung vào một số nhỏ các máy chủ trung tâm như các mạng thông thường. Mạng ngang hàng thường được sử dụng để kết nối các máy thông qua một lượng kết nối dạng ad hoc. Mạng ngang hàng có nhiều ứng dụng. Ứng dụng thường xuyên gặp nhất là chia sẻ tệp tin, tất cả các dạng như âm thanh, hình ảnh, dữ liệu,... hoặc để truyền dữ liệu thời gian thực như điện thoại VoIP. Hình 1. Mô hình mạng ngang hàng Một mạng ngang hàng đúng nghĩa không có khái niệm máy chủ và máy khách, nói cách khác, tất cả các máy tham gia đều bình đẳng và được gọi là peer, là một nút mạng đóng vai trò đồng thời là máy khách và máy chủ đối với các máy khác trong mạng. Một ví dụ điển hình là dịch vụ truyền dữ liệu. Các nút trong mạng ngang hàng sẽ liên lạc với nhau, lấy dữ liệu từ nút khác về, đồng thời chia sẻ dữ liệu đó cho những nút có nhu cầu. Với mô hình khách chủ, máy khách gửi yêu cầu, thực hiện việc nhận dữ liệu một chiều từ phía máy chủ. Đây chính là điểm khác biệt cơ bản nhất của mô hình ngang hàng so với các mô hình truyền thống. Hình 2. Mô hình mạng khách chủ Một số mạng hay kênh như Napster, IRC (thuộc thế hệ thứ nhất) sử dụng mô hình máy chủ-máy khách cho một số tác vụ và mô hình ngang hàng cho những tác vụ khác. Ngược lại, các mạng như Gnutella hay Freenet (thế hệ thứ 2) sử dụng mô hình ngang hàng cho tất cả các tác vụ, nên các mạng này thường được xem như là mạng ngang hàng đúng nghĩa (thực ra Gnutella vẫn sử dụng một số máy chủ để giúp các máy trong mạng tìm kiếm địa chỉ IP của nhau). Cấu trúc mạng ngang hàng là biểu hiện của một trong những khái niệm quan trọng nhất của Internet, mô tả trong "RFC 1, Host Software" xuất bản ngày 7 tháng 4 năm 1969. Gần hơn, khái niệm này đã được sự công nhận rộng rãi trong các cấu trúc chia sẻ nội dung mà không có máy chủ trung tâm. Khái niệm ngang hàng ngày nay được tiến hóa vào nhiều mục đích sử dụng khác nhau, không chỉ để trao đổi tệp mà còn khái quát hóa thành trao đổi thông tin giữa người với người, đặc biệt trong những tình huống hợp tác giữa một nhóm người trong cộng đồng. Ưu điểm Ưu điểm của mạng ngang hàng thể hiện ở việc áp dụng vào từng ứng dụng cụ thể mà cấu trúc mạng khách chủ không có được. Nói cách khác, ưu điểm của mạng ngang hàng chính là khắc phục những nhược điểm của mô hình mạng cũ. Mục đích quan trọng của mạng đồng đằng là trong mạng tất cả các máy tham gia đều đóng góp tài nguyên, bao gồm băng thông, lưu trữ, và khả năng tính toán. Do đó khi càng có nhiều máy tham gia mạng thì khả năng tổng thể của hệ thống mạng càng lớn. Ngược lại, trong cấu trúc máy chủ-máy khách, nếu số lượng máy chủ là cố định, thì khi số lượng máy khách tăng lên khả năng chuyển dữ liệu cho mỗi máy khách sẽ giảm xuống. Tính chất phân tán của mạng ngang hàng cũng giúp cho mạng hoạt động tốt khi một số máy gặp sự cố. Đối với cấu trúc tập trung, chỉ cần máy chủ gặp sự cố thì cả hệ thống sẽ ngưng trệ. Ngoài ra, do mô hình mạng ngang hàng đơn giản nên dễ cài đặt, tổ chức và quản trị, chi phí thiết bị thấp. Mô hình khách chủ đòi hỏi một server đủ mạnh với giá thành cao, thường thì server này ít sự cố, nhưng nếu có sẽ gây thiệt hại lớn về thông tin và cả chi phí để tái thiết lập lại hệ thống. Hiện nay, máy tính cá nhân đủ mạnh để có thể làm nhiều hơn công việc của một client, vì thế tham gia vào mạng ngang hàng với nhiều tiềm năng là khả thi. Đối với mạng Napster, thuật ngữ ngang hàng nói lên tính chất quan trọng của giao thức giao tiếp ngang hàng, còn thực ra thành công của Napster phải nhờ vào sự liên kết chặt chẽ giữa các máy tham gia với máy chủ trung tâm lưu trữ danh sách nội dung tệp trên các máy tham gia. Nhờ vậy việc tìm kiếm trở nên nhanh và hiệu quả hơn, tuy nhiên, đây cũng chính là điểm yếu dẫn đến các rắc rối pháp lý mà kết cục là sự sụp đổ của Napster. Nhược điểm Mặc dù có rất nhiều ưu điểm, nhưng mạng ngang hàng cũng bộc lộ khá nhiều nhược điểm. Các nút tham gia với tính phân tán, trách nhiệm và vai trò là như nhau trong mạng, ít tuân theo quy luật hay giàng buộc nào. Đáng kể như: Kết quả truy vấn trả về có thể là rất nhiều do kết nối đến nhiều nút khác nhau, sự đồng bộ giữa các nút là khá khó khăn. Hoặc có thể chẳng nhận được trả lời nào hay dữ liệu cần tìm không tồn tại, do không biết trước nút đích có còn nằm trong mạng hay không. Các nút đột ngột rời khỏi mạng sẽ làm sai bảng định tuyến trong một thời gian nhất định, làm cho việc truy vấn thiếu chính xác. Dữ liệu mà nút đó phụ trách cũng có thể bị mất theo. Sự bảo mật dữ liệu là kém do dữ liệu phân tán. Các nhược điểm trên đang dần được san lấp bằng nhiều phương pháp. Đáng chú ý là đặt ra các luật lệ, nội quy ràng buộc các bên tham gia với quyền lợi và trách nhiệm nhất định sẽ giúp cho mạng ổn định và an toàn hơn. Số lượng thành viên tham gia mạng ngang hàng ngày càng nhiều giúp cho tài nguyên mạng trở lên phong phú, hiệu suất mạng cũng tăng tỉ lệ với số lượng nút tham gia. Ngoài ra, các cơ chế nhân bản giúp cho xác suất mất dữ liệu khi các nút rời đi trở lên vô cùng nhỏ. Phân loại mạng ngang hàng Hai tiêu chí cơ bản để phân loại mạng ngang hàng: Theo mục đích sử dụng Chia sẻ file (file sharing) Điện thoại VoIP (telephony) Đa phương tiện media streaming (audio, video) Diễn đàn thảo luận (Discussion forums) Tiêu chí này thường được các nhà phát triển ứng dụng quan tâm. Theo đó các ứng dụng với đặc điểm riêng sẽ được phân loại và áp dụng theo những mô hình sẵn có, chuyên biệt. Theo topo của mạng ở tầng vật lý và mạng phủ. Đây là tiêu chí được phát triển qua từng thời kỳ và được xem xét nghiên cứu để tìm ra những giải pháp tốt nhất, xây dựng nền tảng vững chắc cho các ứng dụng sau này. Hệ thống ngang hàng lai (Hybrid Peer-to-peer System) Đây là mạng ngang hàng thế hệ thứ nhất, đặc điểm là vẫn còn dựa trên một máy chủ tìm kiếm trung tâm - đặc điểm của mô hình khách chủ, chính vì vậy nó còn được gọi là mạng ngang hàng lai hay mạng tập trung (centralized Peer-to-Peer networks). Cấu trúc Overlay của mạng ngang hàng lai có thể được mô tả như một mạng hình sao. Nguyên tắc hoạt động: Mỗi client lưu trữ files định chia sẻ với các nút khác trong mạng. Một bảng lưu trữ thông tin kết nối của người dùng đăng kí (IP address, connection bandwidth…). Một bảng liệt kê danh sách các files mà mỗi người dùng định chia sẻ (tên file, dung lượng, thời gian tạo file…). Mọi máy tính tham gia mạng được kết nối với máy chủ tìm kiếm trung tâm, các yêu cầu tìm kiếm được gửi tới máy chủ trung tâm phân tích, nếu yêu cầu được giải quyết máy chủ sẽ gửi trả lại địa chỉ IP của máy chứa tài nguyên trong mạng và quá trình truyền file được thực hiện theo đúng cơ chế của mạng ngang hàng, giữa các host với nhau mà không cần quan máy chủ trung tâm. Hình 3. Mạng ngang hàng lai thế hệ thứ nhất (Napster) Ưu điểm: Dễ xây dựng. Tìm kiếm file nhanh và hiệu quả. Nhược điểm: Vấn đề luật pháp, bản quyền. Dễ bị tấn công. Cần quản trị (central server). Napster là mạng ngang hàng đặc trưng cho hệ thống mạng ngang hàng của thế hệ thứ nhất, chúng được dùng cho việc chia sẻ các file giữa các người dùng Internet, được sử dụng rộng rãi, tuy nhiên nhanh chóng bị mất thị trường bởi yếu tố về luật pháp. Khái niệm và kiến trúc của Napster vẫn còn được sử dụng trong các ứng dụng khác như: Audiogalaxy, WinMX. Với Napster, việc tìm kiếm file bị thất bại khi bảng tìm kiếm trên máy chủ vì lý do nào đó không thực hiện được. Chỉ có các file truy vấn và việc lưu trữ được phân tán, vì vậy máy chủ đóng vai trò là một nút cổ chai. Khả năng tính toán và lưu trữ của máy chủ tìm kiếm phải tương xứng với số nút mạng trong hệ thống, do đó khả năng mở rộng mạng bị hạn chế rất nhiều. Mạng ngang hàng thuần túy (Pure Peer-to-peer System) Mạng ngang hàng thuần túy là một dạng khác của thế hệ thứ nhất trong hệ thống các mạng ngang hàng. Không còn máy chủ tìm kiếm tập trung như trong mạng Napster, nó khắc phục được vấn đề nút cổ chai trong mô hình tập trung. Tuy nhiên vấn đề tìm kiếm trong mạng ngang hàng thuần túy lại sử dụng cơ chế Flooding, yêu cầu tìm kiếm được gửi cho tất cả các nút mạng là láng giềng với nó, điều này làm tăng đáng kể lưu lượng trong mạng. Đây là một yếu điểm của các mạng ngang hàng thuần túy. Các phần mềm tiêu biểu cho mạng ngang hàng dạng này là Gnutella 0.4, FreeNet. Hình 4. Mạng ngang hàng thuần túy (Gnutella 0.4, FreeNet) Ưu điểm: Dễ xây dựng. Đảm bảo tính phân tán hoàn toàn cho các nút tham gia mạng, các nút tham gia và rời khỏi mạng một cách tùy ý mà không ảnh hưởng đến cấu trúc của mạng. Nhược điểm: Tốn băng thông. Phức tạp trong tìm kiếm. Các nút có khả năng khác nhau (CPU power, bandwidth, storage) đều có thể phải chịu tải (load) như nhau. Kiến trúc siêu ngang hàng (Super-peer Architecture) Để khắc phục nhược điểm của mạng ngang hàng thuần túy, một mô hình mang ngang hàng mới được phát triển với tên gọi là mạng siêu ngang hàng. Đây được gọi là mạng ngang hàng thế hệ 2. Phần mềm tiêu biểu cho mạng ngang hàng kiểu này là Gnutella 0.6 và JXTA (Juxtapose). JXTA được bắt đầu phát triển bởi SUN từ 2001 (Đây là giao thức P2P mã nguồn mở). JXTA được sử dụng cho PCs, mainframes, cell phones, PDAs - để giao tiếp theo cách không tập trung. Skype cũng được xây dựng dựa trên cấu trúc này. Hình 5. Kiến trúc siêu ngang hàng(Gnutella 0.6, JXTA) Nguyên tắc hoạt động: Trong mô hình mạng siêu ngang hàng tồn tại một trật tự phân cấp bằng việc định nghĩa các Super-peers. Các Super-peer tạo thành một mạng không cấu trúc, có sự khác nhau giữa Super-peers và Client-peers trong mạng, mỗi Super-peer có nhiều kết nối đến các Client-peers. Mỗi Supper-peer chứa một danh sách các file được cung cấp bởi các Client-peer và địa chỉ IP của chúng vì vậy nó có thể trả lời ngay lập tức các yêu cầu truy vấn từ các Client-peer gửi tới. Ưu điểm: Hạn chế việc Flooding các query, làm giảm lưu lượng trong mạng, nhưng vẫn tránh được hiện tượng nút cổ chai (do có nhiều Super-peers). Khắc phục được nhược điểm về sự khác nhau về CPU power, bandwidth… ở mạng ngang hàng thuần túy, các Super-peer sẽ chịu tải chính, các nút khác chịu tải nhẹ. Nhược điểm: Mỗi điểm Super-peer trở thành điểm gây lỗi cho nhóm siêu ngang hàng tương ứng trong trường hợp số lượng Client trong nhóm là rất lớn (tuy nhiên, nhược điểm này đã được giải quyết bằng việc cải tiến mạng siêu ngang hàng thông thường, đưa ra khái niệm siêu ngang hàng dư cấp k). Mạng ngang hàng có cấu trúc (Structured) Hệ thống mạng ngang hàng không cấu trúc thể hiện nhược điểm: không có gì đảm bảo tìm kiếm sẽ thành công. Đối với tìm kiếm các dữ liệu phổ biến được chia sẻ trên nhiều máy, tỉ lệ thành công là khá cao, ngược lại, nếu dữ liệu chỉ được chia sẻ trên một vài máy thì xác suất tìm thấy là khá nhỏ. Tính chất này là hiển nhiên vì trong mạng ngang hàng không cấu trúc, không có bất kì mối tương quan nào giữa một máy và dữ liệu nó quản lý trong mạng, do đó yêu cầu tìm kiếm được chuyển một cách ngẫu nhiên đến một số máy trong mạng. Số lượng máy trong mạng càng lớn thì khả năng tìm thấy thông tin càng nhỏ. Một nhược điểm khác của hệ thống này là do không có định hướng, một yêu cầu tìm kiếm thường được chuyển cho một số lượng lớn máy trong mạng làm tiêu tốn một lượng lớn băng thông của mạng, dẫn đến hiệu quả tìm kiếm chung của mạng thấp. Mạng ngang hàng có cấu trúc khắc phục nhược điểm của mạng không cấu trúc bằng cách sử dụng hệ thống DHT (Distributed Hash Table - Bảng Băm Phân Tán). Hệ thống này định nghĩa liên kết giữa các nút mạng trong mạng phủ theo một thuật toán cụ thể, đồng thời xác định chặt chẽ mỗi nút mạng sẽ chịu trách nhiệm đối với một phần dữ liệu chia sẻ trong mạng. Với cấu trúc này, khi một máy cần tìm một dữ liệu, nó chỉ cần áp dụng một giao thức chung để xác định nút mạng nào chịu trách nhiệm cho dữ liệu đó và sau đó liên lạc trực tiếp đến nút mạng đó để lấy kết quả. Nguyên tắc hoạt động: Topo mạng được kiểm soát chặt chẽ. Files (hoặc con trỏ trỏ tới files) được đặt ở một vị trí xác định. Điều quan trọng đối với những hệ thống có cấu trúc là cung cấp sự liên kết (mapping) giữa nội dung (ví dụ: id của file) và vị trí nút (ví dụ: địa chỉ nút). Việc này thường dựa trên một cấu trúc dữ liệu bảng băm phân tán (Distributed Hash Table). Hình 6. Cơ chế của bảng băm phân tán (DHT) Dựa trên cấu trúc bảng băm phân tán đã có nhiều nghiên cứu và đề xuất ra các mô hình mạng ngang hàng có cấu trúc, điển hình là cấu trúc dạng vòng (như trong hình vẽ mô tả): Chord, Pastry…, và cấu trúc không gian đa chiều: CAN, Viceroy. Ưu điểm: Khả năng mở rộng được nâng cao rõ rệt do không có điểm tập trung gây ra hiện tượng thắt nút cổ chai tại những điểm này. Các truy vấn tìm kiếm được phát đi theo một thuật toán cụ thể, hạn chế tối đa lượng truy vấn hay kỹ thuật flooding, tiết kiệm băng thông mạng. Nhược điểm: Việc quản lí cấu trúc của topo mạng gặp khó khăn, đặc biệt trong trong trường hợp tỷ lệ vào/ra mạng của các nút cao. Vấn đề cân bằng tải trong mạng. Sự khác biệt về topology trên mạng overlay và mạng liên kết vật lý dẫn đến thời gian trễ truy vấn trung bình cao. Cấu trúc Chord Chord là một trong những mạng DHT phổ biến nhất, với những đặc điểm riêng mang tính ưu thế của mình. Hai trong số những đặc điểm của Chord không thể không kể tới đó là khả năng tìm kiếm dữ liệu nhanh và cân bằng tải giữa các nút. Hình 7. Mạng ngang hàng có cấu trúc Chord dạng vòng tròn. Một đặc điểm của mạng DHT dễ nhận thấy ở Chord là sự phân phát khóa tương đối đồng đều vào các nút trong mạng. Đây chính là hệ quả của việc sử dụng kỹ thuật consistent hashing để cấp khóa cho các nút. Phương thức hình thành khóa phổ biến nhất thường được dùng là băm giá trị của dữ liệu để tạo thành khóa. Giá trị của dữ liệu ở đây có thể là địa chỉ, tên tài liệu, những từ xuất hiện nhiều trong một văn bản, nội dung văn bản đó,… Mỗi loại giá trị dữ liệu có những đặc điểm khác nhau, tùy từng trường hợp mà giá trị nào được sử dụng sao cho phù hợp với ứng dụng nhất. Sự phân bổ khóa trong giao thức Chord thường đi kèm với dữ liệu, thường là một cặp (khóa, dữ liệu). Khóa được coi như phương thức chỉ đường để có thể tìm thấy dữ liệu mong muốn một cách nhanh nhất. Có thể nói Chord là đại diện tiêu biểu nhất của hệ thống mạng ngang hàng có cấu trúc DHT, không những vậy Chord còn là nền tảng cho những nghiên cứu phát triển ứng dụng sau này. Một số nghiên cứu đã chỉ ra rằng: Chord không chỉ là một mạng DHT đơn thuần mà còn mang nhiều ưu điểm khác mà một số mạng DHT không có. Nói tới Chord ta có thể nhắc tới những đặc điểm sau đây: Cân bằng tải (Load Balance): Quá trình hình thành và phân bổ khóa của Chord dựa trên thuật toán Consistent Hashing. Chính những đặc điểm của thuật toán này đã tạo cho Chord một khả năng cân bằng tải một cách tự nhiên ngay khi mạng được khởi tạo. Sự phân quyền: Trong giao thức Chord, không nút nào quan trọng hơn nút nào, quyền hạn này được thực hiện rất hiệu quả trong giao thức Chord. Một số mạng P2P ban đầu cũng có những đặc điểm tương tự nhưng vẫn tồn tại những yếu điểm mà Chord đã khắc phục được. Khả năng mở rộng: Quá trình hình thành mạng, tìm kiếm dữ liệu trong Chord phụ thuộc nhiều vào sự biến thiên của hàm số logarit. Chính điều này tạo cho Chord khả năng mở rộng với số lượng rất lớn các nút, cải thiện hiệu suất tìm kiếm một các tối đa. Tính sẵn sàng: Mỗi nút trong Chord tự động điều chỉnh bảng thông tin định tuyến ( Finger Table) của chính nó khi có một nút tham gia hoặc dời mạng. Nói cách khác trong mạng Chord quá trình duy trì sự tồn tại của mạng diễn ra hoàn toàn tự động, chính điều này đã giảm thiểu khả năng đổ vỡ xuống mức tối thiểu khi quá trình tham gia và dời bỏ mạng của các nút diễn ra. Mô hình mạng Chord Chord được mô tả dưới dạng một vòng tròn và có không gian định danh cỡ N, với N là số bit định danh của không gian. Mạng Chord sẽ có thế chứa tối đa 2 mũ N Chord nút. Một Chord nút (hay một nút - một máy tính trong mạng Chord) có một định danh id, và các id trong mạng Chord sắp xếp thành vòng tròn và tăng theo chiều kim đồng hồ. Chord sử dụng một hàm băm để sinh định danh cho nút và tài liệu, đầu ra của hàm băm là một giá trị N bit. Để đảm bảo xác suất định danh trùng nhau là thấp, N phải đủ lớn. Với Chord, N thường là 160 bit. Một nút trỏ tới nút tiếp theo là nút có id lớn hơn, được gọi là Successor(id), và một nút nữa có id nhỏ hơn, được gọi là Predecessor(id). Các nút liên kết với nhau dựa vào Succcessor và Predecessor của nó. Hình 8. Một mạng Chord với 3 nút Mỗi nút sẽ lưu một bảng định tuyến gọi là Finger Table. Thay vì phải tìm kiếm tuyến tính, bảng định tuyến cho phép một nút định tuyến tới các nút ở xa. Mỗi dòng trong bảng Finger Table sẽ lưu thông tin về 1 nút ở xa, gọi là 1 entry. Entry thứ i sẽ lưu nút là successor của khóa có định danh cách định danh nút đang xét 2i theo chiều tiến của vòng Chord. Vì vậy, không gian định danh có bao nhiêu bit thì Finger Table có bấy nhiêu entry. Ánh xạ khóa vào một nút trong Chord Chord ánh xạ các khóa vào các nút, thường sẽ là một cặp key và value. Một value có thể là 1 address, 1 văn bản, hoặc 1 mục dữ liệu. Chord có thể thực hiện chức năng này bằng cách lưu các cặp key/value ở các nút mà key được ánh xạ. Một nút sẽ chịu trách nhiệm lưu giữ một khóa k nếu nút đó là nút có định danh id nhỏ nhất và lớn hơn k. Một nút khi lưu giữ khóa k cũng sẽ được gọi là Successor(k). Hình 9. Lưu giữ key trong mạng Chord Tìm kiếm trong mạng Chord Khi một nút cần tìm kiếm một khóa có định danh id, nút đó sẽ tìm nút chịu trách nhiệm lưu giữ id đó. Nếu nút ở xa so với vị trí của nút lưu giữ id, nút có thể nhờ vào thông tin trong bảng Finger Table để định tuyến đến các nút xa hơn, từ đó dần dần biết được nút chịu trách lưu giữ id. Một ví dụ được chỉ trong hình 6, giả sử nút 3 muốn tìm successor của ID (hoặc còn có thể coi là khóa) 1. ID 1 thuộc khoảng [7, 3), tức là 3.finger[3].interval. nút 3 kiểm tra entry thứ 3 trong bảng định tuyến của nó, là 0. Bởi vì 0 trước 1, nút 3 sẽ hỏi nút 0 để tìm successor của 1. Quay trờ lại, nút 0 sẽ suy ra từ bảng định tuyển rằng successor của 1 chính là nút 1, và trả về nút 1 cho nút 3. Tham gia và ổn định mạng Trong 1 mạng động , thường xuyên có sự thay đổi với các nút tham gia và rời khỏi bất kì lúc nào. Để có thể xác định được vị trí của các khóa ở trong mạng, Chord cần thỏa mãn 2 điểm sau : Mỗi successor của 1 nút phải đc duy trì đúng Với mỗi khóa k, nút successor(k) có trách nhiệm quản lý k Khi tham gia vào một mạng Chord, một nút n cần chọn cho nó một định danh id và báo cho các nút bên cạnh biết sự tham gia của nó. Các nút Successor và Predecessor sẽ cần phải cập nhật thông tin về nút mới tham gia vào mạng. Nút n cũng cần khởi tạo bảng định tuyến Finger Table bằng cách tìm các nút mà Successor các id trong từng entry của Finger Table. Để mạng vẫn định tuyến đúng sau khi có sự tham gia của nút n, các nút cần thường xuyên chạy thuật toán ổn định mạng để cập nhật thông tin về nút bên cạnh ( hay nút hàng xóm). Một số nút sẽ có n trong bảng Finger Table, nên cần cập nhật một số entry của Finger Table. Cuối cùng là nút Successor của n sẽ chuyển một phần khóa mà bây giờ n là Successor(khóa), cho n lưu giữ. Việc chuyển khóa sẽ do tầng trên của ứng dụng thực hiện. Khi một nút chuẩn bị rời khỏi mạng, nó cần thông báo cho các nút bên cạnh biết để ổn định lại mạng. Nút đó cũng sẽ chuyển các khóa nó lưu giữ cho nút Successor của nó. Chương 2. Các nghiên cứu về tối ưu Chord Trong chương một, chúng ta đã được làm quen với Chord, cách xây dựng, cơ chế vận hành của Chord nói riêng và mạng ngang hàng có cấu trúc DHT nói chung. Đồng thời cũng thấy được tính ưu việt của Chord so với các cấu trúc khác. Tuy nhiên, vẫn tồn tại rất nhiều vấn đề của Chord và cả DHT – những vấn đề trở thành nhược điểm làm cho chi phí truyền thông cao, hiệu suất mạng giảm. Tiếp theo, khóa luận sẽ nói kỹ hơn về một số vấn đề mà mạng Chord gặp phải, phương hướng giải quyết cũng như tối ưu những vấn đề trên. Sau đó là một số nghiên cứu tiêu biểu cho vấn đề này. Tối ưu hóa trên Chord Cấu trúc Chord ngày càng được áp dụng cho nhiều ứng dụng ngang hàng. Vì vậy, việc tối ưu, khắc phục những nhược điểm của cấu trúc này là cần thiết. Có nhiều vấn đề đã được đề cập đến trong rất nhiều các bài nghiên cứu, báo cáo. Nhưng tập trung vào hai vấn đề chính: sự khác biệt về topo và tối ưu bảng định tuyến. Sự khác biệt về topo (Topology mismatch) Vấn đề khác biệt về topo nảy sinh ngày từ khi mạng ngang hàng có cấu trúc với bẳng băm phân tán được đưa ra. DHT xây dựng một mạng phủ bên trên mạng kết nối vật lý giữa các nút và sử dụng topo này trong việc xác định quan hệ, liên lạc, truyền dữ liệu. Mạng phủ định vị lại các nút trong một topology mới với địa chỉ là các giá trị băm. Sự phân tán của giá trị băm giúp cho mạng phủ được cân bằng ngẫu nhiên về không gian địa chỉ - tránh sự tập trung của nút và tài liệu trên toàn dải địa chỉ, đồng thời hỗ trợ việc bảo mật thông tin địa chỉ giữa các tầng cũng như các nút tham gia mạng, nhưng lại gây ra sự không đồng bộ về topo như trên. Theo đó, hai nút ở rất gần nhau về đường truyền vật lý có thể sẽ trở lên xa nhau trên dải địa chỉ của Chord và ngược lại. Trong các ứng dụng ngang hàng Chord, các truy vấn ngắn thường có tần suất lớn hơn các truy vấn dài do quá trình tìm kiếm ưu tiên các nút hàng xóm trước. Như vậy, hậu quả rõ rệt là với một truy vấn bất kỳ, thời gian đáp ứng cho truy vấn đó có thể rất lớn, hiệu suất của ứng dụng giảm. Một cách tiếp cận để giải quyết vấn đề Topology mismatch là dựa vào các đặc điểm vật lý. Đặc điểm vật lý chúng ta nói ở đây là vị trí của nút, địa chỉ của nút. Với các thông tin này, chúng ta có thể làm mới cấu trúc của mạng phủ sao cho phù hợp với mạng vật lý nhất. Nhưng giá phải trả cho phương pháp này là không nhỏ. Trước hết, cấu trúc gần với mạng vật lý trong nhiều trường hợp lại tỏ ra kém hiệu quả, đặc biệt là sự khó kiểm soát giao thông trên mạng tại từng vùng, từng điều kiện và thời điểm. Thứ hai, rất quan trọng, là làm mất đi tính trong suốt giữa các tầng. Tầng ứng dụng phải nắm được rất nhiều thông tin về tầng dưới không chỉ của máy local, các máy khác cũng phải cung cấp thông tin. Điều này ảnh hưởng đến an toàn giao thông mạng, các hình thức tấn công và hơn hết là sự riêng tư của những người tham gia mạng ngang hàng. Tối ưu bảng định tuyến (Finger Table) Một điểm cải tiến rất lớn lớn trong cấu trúc Chord (DHT nói chung) so với các thế hệ mạng ngang hàng trước chính là việc bổ xung thêm bảng định tuyến. Thay vì phát tràn các truy vấn hay thực hiện phát truy vấn theo một thuật toán ưu tiên nào đó như trong mạng ngang hàng không có cấu trúc, hoặc truy vấn tuyến tính trên dải địa chỉ băm của mạng có cấu trúc, bảng định tuyến giúp cho việc gửi các yêu cầu truy vấn diễn ra nhanh chóng, hiệu quả. Số lượng truy vấn phát ra từ nút tìm kiếm là duy nhất, và sau tối đa log2n bước chuyển tiếp, truy vấn sẽ tới đích. Cơ chế này dựa trên thuật toán tìm kiếm nhị phân, điều này lý giải tại sao entry thứ i trong bảng định tuyến sẽ lưu nút là successor của khóa có định danh cách định danh nút đang xét 2i định danh. Nhận thấy rằng, nút được chọn khi xây dựng từng entry của một bảng định tuyến là cố định, chỉ phụ thuộc vào topo hiện tại của mạng Chord. Sự thiếu mềm dẻo khi xây dựng bảng định tuyến cũng sẽ làm gia tăng thời trễ truy vấn, giảm chất lượng ứng dụng. Từ những nhận xét trên, đã có nhiều nghiên cứu nhằm cải tiến và tối ưu hiệu năng của Chord. Sau đây là một số nghiên cứu tiêu biểu – những nghiên cứu cũng được áp dụng trên nền Chord. Lựa chọn láng giềng gần (Proximity Neighbor Selection[5]) Nghiên cứu này tập trung cải thiện thuộc tính gần gũi trong mạng ngang hàng có cấu trúc nói chung. Căn cứ vào mạng liên kết tọa độ hai chiều ảo, những nút được xem là gần nhau được tập hợp lại vào một miền, các miền này kề sát nhau và phủ kín mặt phẳng tọa độ. Sau đó là quá trình ánh xạ (mapping) từ không gian mạng quan hệ sang không gian địa chỉ của DHT. Thông qua quá trình tìm kiếm các định danh miền tương ứng sử dụng thủ tục RPC trong Chord, các nút có thể nhận được danh sách hàng xóm của chúng một cách nhanh chóng theo cách thức phân tán hoàn toàn. Kết quả thu được thông qua chương trình mô phỏng mô hình với topo mở rộng đủ lớn chỉ ra rằng, cải tiến có một độ trễ lân cận trung bình thấp hơn phương pháp lấy ngẫu nhiên rất nhiều. Phương pháp này có hai điểm chính tập trung vào việc tối ưu hóa mạng Chord. Đầu tiên là sự chọn lọc láng giềng gần (Proximity Neighbor Selection - PNS), ở đó những láng giềng trong bảng định tuyến được lựa chọn dựa vào mức độ gần gũi của chúng với nút đang xét. Thứ hai là lựa chon tuyến đường gần, diễn ra khi lựa chọn điểm đích tiếp theo trong quá trình định tuyến tới một điểm đích riêng biệt, và cũng dựa trên mức độ gần gũi đã nêu. Phương pháp này giải quyết cả hai nhược điểm được nêu ở phần trước của Chord. Phân chia không gian liên kết hai chiều Trước tiên chúng ta sẽ xem xét cách xây dựng không gian liên kết hai chiều của các nút. Từ đó có thể đánh giá được mức độ gần gũi của các nút. Vì vậy, đây là một phần trọng trong khâu chuẩn bị, quyết định khá nhiều đến sự thành công của thuật toán. Hình 10. Bản đồ miền trong không gian hai chiều Thông qua thuật toán Vivaldi, mỗi nút sẽ lấy được tập các quan hệ trong mạng ảo hai chiều. Thuật toán Vivaldi sẽ ánh xạ một nút vào một tọa độ hai chiều (x, y) dựa vào công thức với nhiều tham số, trong đó có thời gian quay vòng (round-trip delay time - RTT) là thời gian đo đc tương tự như quá trình ping hay DNS và tọa độ của các nút trước đó. Kết quả của thuật toán là một mặt phằng tọa độ với các nút được ánh xạ vào một điểm trên đó. Tiếp theo là ánh xạ chia miền để xét quan hệ gần gũi. Với mỗi nút s được chọn là nút trung tâm, xét r cố định, các đường tròn có bán kính r, 2r, 3r… được định nghĩa như hình vẽ. Miền được định nghĩa như sau: hình vành khăn tạo bới phần cắt giữa đường tròn bán kính ir với đường tròn có bán kính (i-1)r chia thành 2i-1 miền diện tích bằng nhau và bằng PI*r2. Điều này chứng minh khá đơn giản. Các miền được đặt định danh bằng một cặp (i, j), trong đó i là số hiệu đường tròn nhỏ nhất chứa miền đó, j là thứ tự miền trong hình vành khăn đang xét. Thứ tự miền được đánh số theo chiều dương và từ góc 0o. Như vậy, mỗi nút sẽ có một bản đồ miền như mô tả. Từ vị trí của bản thân nút và vị trí tương đối của các nút xung quanh, thực hiện ánh xạ các nút hàng xóm vào các miền, các nút trong cùng một miền được xem là có quan hệ như nhau với nút trung tâm. Độ ưu tiên miền dựa vào tên định danh của miền, theo đó, giá trị i càng nhỏ, miền càng gần nút trung tâm. Việc chia miền giúp những cụm nút có khoảng cách và thuộc tính gần như nhau hợp lại, trợ giúp cho quá trình tìm kiếm và định tuyến phía sau. Tối ưu quá trình định tuyến Việc tìm kiếm các láng giềng gần diễn ra khá đơn giản. Mỗi nút đều lưu định danh miền mà nó thuộc về. Khi có yêu cầu tìm kiếm những nút láng giềng, nút được yêu cầu sẽ dựa vào định danh miền, xác định các nút nằm trong cùng miền đó. Như vậy dễ dàng tìm ra các nút láng giềng gần. Nếu nút đó 1 mình 1 miền, quá trình tìm kiếm bắt đầu với 6 miền lân cận. Quá trình tìm kiếm diễn ra cho đến khi tìm được ít nhất một nút. Những nút tìm được sẽ được add vào tập láng giềng gần. Thay đổi các đường dẫn trong bảng định tuyến là mục đích chính của nghiên cứu này. Trong Chord truyền thống, entry thứ i của là định danh của nút là successor của khóa k+2i với k là định danh nút hiện tại. Để có thể tận dụng được thời gian trễ và topo xây dựng bên trên, đồng thời tạo tính mềm dẻo cho việc lựa chọn, cải tiến đã chọn lại nút này bằng nút hàng xóm có định dạnh nằm trong khoảng [k+2i-1, k+2i) và gần nút đang xét nhất. Quá trình tìm kiếm nút hàng xóm gần đã được mô tả ở trên. Ưu điểm Cải thiện hiệu năng mạng, giảm độ trễ. Giữ nguyên cơ chế chạy của Chord truyền thống, đặc biệt là phần truy vấn. Nhược điểm Xây dựng không gian liên kết hai chiều theo thuật toán Vivaldi khá phức tạp. Tạo ra ánh xạ càng đầy đủ, càng gần thì chi phí xây dựng càng lớn. Quasi-Chord [7] Vấn đề sai khác topo mạng (topology mismatch) như đã được giới thiệu là một trong những vấn đề đáng kể nhất trong tối ưu mạng ngang hàng có cấu trúc. Nghiên cứu này đưa ra một mô hình mạng Chord mới với tên Quasi-Chord. Mô hình sử dụng hệ thống mạng định vị toàn cầu (global network position - GNP) để liên kết các nút trên tầng vật lý và sử dụng không gian Cantor, ánh xạ từ không gian hình học hai chiều sang một chiều theo đường gấp khúc. Sau đó xây dựng mô hình Quasi-Chord dựa trên các giá trị Cantor đó. Thực nghiệm mô phỏng cho thấy phương pháp thực sự đã làm giảm độ trễ và lưu lượng mạng với cùng một bộ truy vấn. Điểm đặc trưng nhất trong phương pháp là giải pháp thu thập điểm mốc (landmark clustering). Điểm mốc là một vài nút cố định trong hệ thống. Và mỗi nút khác đo thời gian quay vòng tới các điểm mốc, sắp xếp các điểm mốc đó theo thời gian đo được vào một chuỗi. Chuỗi điểm mốc này được dùng để mô tả vị trí của nút trong hệ thống, các nút có những chuỗi tương tự nhau sẽ là hàng xóm của nhau. Bản thu thập các điểm mốc là một bản phỏng đoán vị trí của các nút. Nó có thể không giúp đỡ đc gì trong tình trạng các nút ở rất gần nhau. Quasi-Chord xây dựng topo logic trên cơ sở là các thông tin về topo của tầng dưới. Vì thế, các nút gần nhau về ở tầng dưới thì cũng kề nhau ở tầng trên, điều mà có thể hạn chế mạnh mẽ giao thông mạng. Để xây dựng mô hình Quasi-Chord, cần ba bước. Đầu tiên, sử dụng mạng định vị toàn cầu để lấy các liên kết của nút trong không gian hình học P2P. Tiếp theo, sử dụng không gian Cantor, men theo đường gấp khúc để chuyển từ không gian hai chiều sang một chiều. Bước cuối cùng là xây dựng vòng Quasi-Chord thông qua các giá trị Cantor của các nút. Tính toán tọa độ của mỗi nút tham gia với GNP Quá trình ánh xạ và tính toán được chia thành hai giai đoạn: Tính toán với các điểm mốc: Trước tiên, chọn N điểm mốc từ L1 đến Ln. Phép đo đơn giản giữa các điêm mốc là thời gian quay vòng sử dụng gói tin ping ICMP và lấy giá trị nhỏ nhất trong một vài phép đo cho mỗi tuyến đường ở nửa dưới ma trân khoảng cách N*N đối xứng qua đường chéo của ma trận. Sử dụng những khoảng cách vừa đo được, các điểm mốc sẽ tính toán vị trí và liên kết trong không gian hình học S. Mục đích của phần này là tìm được tập hợp các vị trí, các liên kết cho N điểm mốc sao cho sự sai khác giữa khoảng cách đo được (thời gian quay vòng của gói tin ping) và khoảng cách tính toán trong không gian hình học S là nhỏ nhất. Hình 11. Tính toán với các điểm mốc Tính toán với nút thông thường Tương tự như trên nhưng áp dụng với một nút thông thường. Các giá trị thời gian quay vòng từ nút đến các điểm mốc được đo và lấy những giá trị nhỏ nhất. Từ những giá trị này, tính toán tìm vị trí của nút trên không gian S cũng với điều kiện sự sai khác giữa khoảng cách đo được và khoảng cách tính toán là nhỏ nhất. Hình 12. Tính toán với nút thông thường Ánh xạ không gian hai chiều sang một chiều sử dụng Cantor Đến đây, các nút đều đã được ánh xạ vào không gian hình học hai chiều. Do không gian địa chỉ của Chord là một chiều, việc ánh xạ từ không gian hai chiều sang một chiều là cần thiết. Để làm được điều đó, chúng ta sẽ đi theo đường rích rắc trên không gian hai chiều. Hình 13. Biểu đồ không gian Cantor với C=8 Giả sử không gian hình học hai chiều tựa ma trận vuông hai chiều như hình vẽ. Kích thước của ma trận phụ thuộc và tọa độ cực của các nút được ánh xạ trong phần trên. Xét đường đi rích rắc theo đường chéo xuất phát từ điểm trái dưới của ma trận như hình vẽ. Chúng ta sẽ được một thứ tự cho các nút có tọa độ giống chỉ số các ô trong ma trận. Đây chính là topo một chiều sẽ được ánh xạ lên vòng không gian địa chỉ trong phần sau. Xây dựng mô hình Quasi-Chord Vì các nút có giá trị Cantor tương tự nhau sẽ gần nhau trên tầng vật lý, chúng ta sẽ xây dựng vòng không gian địa chỉ Quasi-Chord dựa trên các giá trị Cantor này. Theo đường đi một chiều được chỉ ra ở phần trên, các nút theo thứ tự có tọa độ gần nhau sẽ trở thành hàng xóm trên vòng địa chỉ. Thay vì sử dụng hàm băm để lấy địa chỉ trong không gian DHT, Quasi-Chord sử dụng địa chỉ từ các giá trị Cantor. Giả sử có tối đa n nút tham gia vào mạng và kích thước ma trận vuông giới hạn bởi các tọa độ cực trị là C*C, địa chỉ nút trong mô hình này có m bit, thỏa mãn log2n≤ ≤ log2(C*C). Mỗi nút trong mô hình Quasi-Chord có hai bảng định tuyến. Một bảng theo chiều kim đồng hồ tương tự như Chord truyền thống, một bảng theo chiều ngược lại. Theo cách sắp xếp topo như trên, nút đầu và cuối trên vòng địa chỉ là rất xa nhau. Với Chord, hai nút này là gần nhau. Nhưng với Quasi-Chord, nếu xem xét hai nút là hàng xóm thì sẽ gây khó khăn khi truy cập cho những bước định tuyến phải vượt qua vị trí nối này. Vì thế Quasi-Chord quan niệm hai nút này không gần nhau. Nói cách khác successor của nút cuối không phải là nút đầu tiên và ngược lại. Hình 14: Bảng định tuyến giả định của N51 trong Quasi-Chord Bảng định tuyến thứ nhất xây dựng giống như trong Chord truyền thống. Điểm đáng chú ý là các định danh successor của các key mục tiêu trong mỗi entry đều không được nhỏ hơn định danh của nút đang xét. Ngược lại, với bảng thứ hai ngược chiều kim đồng hồ, định danh của successor không được lớn hơn định danh nút đang xét. Và tính key mục tiêu theo công thức (k – 2i-1) mod 2m thay vì (k + 2i-1) mod 2m. Khi nhận được một yêu cầu truy vấn, nút sẽ so sánh key của tài liệu lớn hay nhỏ hơn định danh nút, từ đó sử dụng bảng định tuyến xuôi hay ngược chiều kim đồng hồ tương ứng. Ưu điểm của Quasi-Chord thể hiện rất rõ ràng qua bước phân tích bên trên và kết quả thực nghiệm như biểu đồ. Tuy vậy vẫn tồn tại một vài nhược điểm: Mô hình thích hợp với số lượng nút và các nút trong mạng cố định. Cường độ vào ra cao của các nút trong mạng cao gây khó khăn việc ánh xạ địa chỉ. Xung đột có thể xảy ra khi ánh xạ nút vào không gian Cantor. Vẫn còn vấn đề tại điểm giao nhau giữa nút đầu tiên và cuối cùng trên vòng địa chỉ. Chương 3. Tối ưu Chord dựa trên lựa chọn độ trễ Chương hai cho chúng ta thấy được tổng quan những vấn đề, nhược điểm còn tồn tại trong mô hình mạng ngang hàng Chord và xem xét một số nghiên cứu nhằm tối ưu mạng Chord. Tư tưởng chủ đạo của những nghiên cứu này là ánh xạ mỗi nút tham gia vào một không gian ảo hai chiều, sử dụng thời gian trễ làm tham số; đánh giá mối quan hệ giữa các nút bằng quan hệ trên không gian hai chiều đó. Ưu điểm của phương pháp này là đánh giá mối quan hệ gần gũi tương đối sát so với trên mạng liên kết vật lý. Trong lựa chọn láng giềng gần, nhược điểm là khối lượng công việc khi nút tham gia mạng lớn, việc tạo mới và duy trì bản đồ quan hệ tại mỗi nút đòi hỏi nhiều tài nguyên. Vấn đề của Quasi-Chord là nguy cơ xung đột trên không gian ảo hai chiều và điểm nối giữa định danh lớn nhất và nhỏ nhất trên vòng địa chỉ. Trong chương ba, một giải pháp đơn giản sẽ được đề xuất cũng với mục đích tối ưu topo mạng phủ cấu trúc Chord. Giải pháp này cũng dựa trên thời gian quay vòng của gói tin ICMP, lựa chọn láng giềng và thay đổi bảng định tuyến. Đề xuất Để giải quyết vấn đề khác biệt giữa topo vật lý và topo logic thì các nút gần nhau tại tầng vật lý cần trở thành hàng xóm của nhau trên mạng phủ. Thêm nữa việc có được thông tin tầng dưới (địa chỉ ip, cổng) để xây dựng mạng phủ là không thể. Do đó, khoảng cách dựa vào thời gian trễ giữa các nút được xem là thước đo khả thi nhất đánh giá sự gần gũi giữa chúng. Trong Chord, vị trí của một nút khi tham gia vào mạng được sinh hết sức ngẫu nhiên và không có sự chọn lựa. Vì vậy, nếu cung cấp khả năng lựa chọn trong những quá trình này, sẽ tạo được kết quả chắc chắn có lợi hơn nhiều để cải thiện thời gian truy vấn. Từ những nhận xét trên, giải pháp được đưa ra chính là tập trung vào việc lựa chọn theo tiêu chí độ trễ. Giải pháp sẽ được chia thành hai giai đoạn. Đầu tiền, thực hiện lựa chọn vị trí gia nhập mạng cho nút mới từ một tập các định danh, tiêu chí lựa chọn là độ trễ thấp nhất đến các nút hàng xóm. Thứ hai, khi cập nhật lại bảng định tuyến cho nút sau quá trình vào ra của một số nút, tiếp tục lựa chọn điểm đến tiếp theo khi truy vấn trong tập chứa successor của khóa mục tiêu tại entry i và các lân cận của successor đó. Thời gian trễ từ nút đang xét tới các nút trong tập lựa chọn nhỏ nhất là tiêu chí lựa chọn. Chi tiết hai giai đoạn tối ưu như sau: Lựa chọn vị trí tham gia mạng Khi nút muốn tham gia vào mạng, thay vì cung cấp một định danh duy nhất, chúng ta sẽ cho phép một nút chọn một trong một tập định danh. Tập định danh này được sinh từ hàm băm với đầu vào là thông tin nút và tham số ngẫu nhiên do ứng dụng sinh ra. Tại mỗi vị trí với các định danh tương ứng, lựa chọn khoảng cách thời gian quay vòng nhỏ nhất với cả successor và predeccesor. Vị trí được chọn sẽ là vị trí có độ trễ đến một trong hai nút liền kề là nhỏ nhất. Thay đổi bảng định tuyến Bảng định tuyến sẽ được xây dựng ngay sau đó. Mỗi entry trong bảng định tuyến sẽ không được lấp đầy luôn bằng nút là successor của key mục tiêu tại entry i. Từ nút successor này, tìm kiếm về hai phía trên không gian một chiều Chord. Đo khoảng cách từ nút hiện tại tới các nút nằm trong tập các nút hàng xóm vừa tìm được, chọn nút có độ trễ ping nhỏ nhất. Dùng nút này đề lấp đầy entry đang xét. Việc lựa chọn vị trí sẽ làm cho các nút gần nhau theo thời gian trễ đo được đứng cạnh nhau trên vòng Chord. Quá trình thay đổi bảng định tuyến cũng sẽ làm giảm độ trễ trong việc chuyển tiếp một truy vấn. Như vậy, hai quá trình này hứa hẹn sẽ khắc phục được phần nào những vấn đề với mạng Chord đã được đề cập ở trên. Nội dung Chúng ta sẽ đi một cách chi tiết hơn vào các cải tiến, để từ một ứng dụng Chord truyền thống, có thể thực thi những cải tiến này một cách nhanh nhất. Trước tiên, cần có một vài thay đổi trong một số đối tượng so với Chord truyền thống: Hàm băm có thêm nhiều hơn một tham số. Trong Chord truyền thống, hàm băm nhận thông tin về nút, thường là địa chỉ ip và số hiệu cổng của tiến trình chạy. Như vậy, chúng ta sẽ có một giá trị băm duy nhất cho một nút. Theo yêu cầu của bài toán, chúng ta cần nhiều hơn một giá trị định danh từ một nút. Vì vậy, hàm băm cần nhận thêm một tham số là chỉ số nữa chẳng hạn. Đối tượng đo thời gian trễ giữa hai nút. Có thêm một đối tượng có thể gửi nhận các gói tin ICMP để đo khoảng thời gian quay vòng của các gói tin, từ đó tính khoảng cách một cách tương đối giữa các nút. Những sự thay đổi trong quá trình hoạt động của Chord để thực thi hai biện pháp tối ưu: Nút tham gia mạng Khi một nút muốn tham gia vào mạng, Chord truyền thống sẽ thực hiện băm để nhận một giá trị băm duy nhất. Sau đó thực hiện việc tham gia mạng cho nút tại vị trí đó. Với cải tiến, thay vì một giá trị băm được tính toán, một tập các giá trị băm được tính toán vào chuyển cho nút. Đây là tập giá trị có được từ việc băm thông tin nút và chỉ số phụ. Với mỗi giá trị địa chỉ, tìm successor và predeccessor cho địa chỉ đó. Thực hiện đo độ trễ từ nút đang xét đến hai nút này, lấy giá trị thời gian nhỏ nhất đại diện cho địa chỉ đó. Định danh được chọn sẽ có khoảng thời gian này là nhỏ nhất. Quá trình đo độ trễ, tính toán phải trong suốt. Có rất nhiều lựa chọn về điều kiện để chọn định danh, nhưng khoảng thời gian trễ nhỏ nhất là điều kiện đơn giản, đem lại hiệu quả khá tốt. Hình 15: Lựa chọn vị trí tham gia mạng Cho phép nút tham gia vào mạng với định danh đã được chỉ định như trong Chord truyền thống. Rõ ràng, cải tiến này sẽ làm tiêu tốn thời gian của nút khi tham gia vào mạng. Nói cách khác là khoảng thời gian trễ sẽ lâu hơn từ khi gửi yêu cầu tham gia và được tham gia thực sự. Xây dựng bảng định tuyến Sau khi để nút tham gia vào mạng, việc tiếp theo là xây dựng bảng định tuyến. Trước tiên, với entry thứ i trong bảng định tuyến, tính giá trị key mục tiêu (k + 2i-1) mod 2m, đồng thời tìm s là successor của key này. Giá trị ex được gọi là độ mở rộng trong xây dựng bảng định tuyến. Theo đó, xét ex nút liền trước, liền sau và bản thân s, ta được một tập 2*ex +1 nút. Điều kiện để lọc bớt các nút trong tập này là định danh nút phải nằm trong khoảng (k+2i-2, k+2i). Giới hạn này tránh sự xung đột và trùng lặp trong quá trình xây dựng định tuyến giữa các entry. Thực hiện đo thời gian trễ từ nút đang xét tới tập các nút vừa nêu, một danh sách độ trễ được trả về. Chọn nút có khoảng cách quay vòng là nhỏ nhất là successor của entry i. Những thay đổi trên mang tính cục bộ, chỉ là tác động vào quá trình tham gia mạng của nút mới và cập nhật bảng định tuyến trên Chord truyền thống. Vì thế, khả năng thực thi thêm giải pháp tối ưu vào ứng dụng Chord truyền thống là có thể làm được. Việc thay đổi bảng định tuyến sẽ không làm ảnh hướng đến thuật toán định tuyến của Chord truyền thống. Với cải tiến trên, có thể có những truy vấn mà số bước tìm kiếm cũng như thời gian đáp ứng tăng. Nhưng nhìn vào tổng thể, cải tiến đem lại tiềm năng rất lớn trong việc tiết kiệm băng thông và giảm thời gian đáp ứng khi truy vấn. Ưu nhược điểm Tiêu chí lựa chọn là có thời gian trễ gần nhất với hai nút hàng xóm mang tính cục bộ. Vì thế, xét một cách tổng thể khi so sánh với hai phương pháp trên, tất cả nút được ánh xạ vào không gian hai chiều trước, giải pháp tỏ ra kém hiệu quả hơn. Các quan hệ gần nhau trên vòng định danh mang tính cục bộ, các nút có thể bị chia thành các cụm nhỏ trên đó. Quasi-Chord với việc xếp đặt các nút lên vòng định danh khi lấy theo đường rích rắc trong không gian ảo hai chiều làm cho khoảng cách giữa các hàng xóm đều và trơn hơn. Giải pháp mang những đặc điểm của các nghiên cứu đã trình bày, đều hướng tới giải quyết vấn đề khác biệt trong topo mạng Chord và thay đổi bảng định tuyến dựa trên khoảng thời gian trễ giữa các điểm nút. Xong, mỗi phương pháp đều có những cách thực hiện riêng, khác nhau. Tất cả đều mang lại hiệu quả nhất định trong việc cải thiện hiệu năng, nhưng cũng tồn tại nhiều nhược điểm. Ưu điểm Đơn giản, dễ dàng nắm bắt và thực thi. Khá mềm dẻo, tùy biến các tham số tối ưu để phù hợp với điều kiện mạng cơ sở cũng như mục đích ứng dụng. Số lượng lựa chọn trong hai quá trình tối ưu đều có thể thay đổi dễ dàng. Nhược điểm Số lượng lựa chọn lớn sẽ gây trễ quá trình tham gia vào mạng của nút. Trong một số ít trường hợp, sự tối ưu không đem lại hiệu quả mong muốn. Trong quá trình truy vấn, bảng định tuyến thay đổi, thời gian trễ giữa hai nút chuyển tiếp có thể nhỏ, nhưng số lượng lần chuyển tiếp truy vấn lại tăng. Như vậy, tính tổng thời gian trễ có thể sẽ lớn hơn. Chương 4. Mô phỏng và đánh giá Để thấy được hiệu quả của giải pháp mới và xem xét giải pháp đó tốt đến mức nào, chúng ta cần có những con số thống kê, thể hiện sự hoạt động thực sự của mạng. Về cơ bản, những thử nghiệm và kết quả trên một mạng thực sự luôn là những đánh giá tốt nhất, chính xác nhất. Vì điều kiện để có một mô hình mạng thực sự dành cho việc kiểm tra là rất khó nên mô phỏng là cách lựa chọn đúng đắn. Chương 4 sẽ trình bày về chương trình mô phỏng, các bước để thực hiện chương trình mô phỏng, chạy thử, thống kê kết quả và đánh giá. Vì mô phỏng khác rất xa so với thực tế nên mục đích của chương này là đưa ra được những đánh giá sơ bộ, tổng quát nhất. Chương trình mô phỏng Chương trình mô phỏng gồm gồm hai phần chính là dữ liệu và thực thi. Phần dữ liệu bao gồm các loại dữ liệu và phần mã nguồn chương trình tạo ra chúng. Thực thi chính là phần mô tả hoạt động của mạng ngang hàng Chord. Ngoài ra còn phải kể đến kiến trúc mạng mô phỏng cho tầng dưới – tầng liên kết vật lý. Kiến trúc mạng mô phỏng Để có thể thực hiện được quá trình mô phỏng, trước tiên chúng ta cần có một mô hình mạng tầng liên kết vật lý với thời gian trễ giữa các nút trên mạng. Topo của mạng mô phỏng rất quan trọng vì nó quyết định việc thử nghiệm, kết quả và đánh giá hiệu năng của những cải tiến. Hình 16: Mô hình mạng thực tế Việc xây dựng được một mạng mô phỏng có mô hình giống như mạng thực tế là điều không thể. Trước hết, vì topo mạng thực tế rất phức tạp (thường là mạng lưới ở mức nhà cung cấp và hình cây với rất nhiều tầng ở mức thấp hơn). Thêm vào đó, thời gian trễ đo tại mỗi thời điểm mang tính tức thời, không phải là thời gian trễ hiệu dụng của cả quá trình. Trên thực tế, thời gian trễ này phụ thuộc vào rất nhiều yếu tố như thời điểm đo, giao thông mạng, đường truyền,… Chương trình sẽ xây dựng một topo mạng đơn giản theo các điều kiện giả định. Vì là mạng giả lập với yêu cầu đơn giản, nên các điều kiện ở đây mang tính quy ước, các tham số dựa vào mạng thực tế và kinh nghiệm của nhóm làm khóa luận. Để có được một topo có sức thuyết phục, cần có sự nghiên cứu và thử nghiệm lâu dài hơn. Các điều kiện của mạng mô phỏng: Mạng được chia thành nhiều miền (area), các miền này đôi một không giao nhau. Mỗi miền bao gồm nhiều nút và một điểm trung tâm, được gọi là switch. Các nút trong một miền sẽ kết nối trực tiếp với switch theo topo hình sao. Hai miền bất kì được nối với nhau bằng đường trực tiếp giữa hai switch. Khoảng thời gian trễ trên các đường nối này được gọi là độ trễ liên miền và lấy ngẫu nhiên trong khoảng giá trị cho trước. Trong mỗi vùng thời gian trễ cũng chỉ tính trên các đường nối trực tiếp từ switch trung tâm đến các nút. Độ trễ này – được gọi là độ trễ nội miền - nhỏ hơn nhiều so với độ trễ liên miền. Độ trễ giữa hai nút bất kỳ được tính bằng tổng độ trễ nội miền của hai nút và độ trễ liên miền giữa hai miền chứa hai nút đó. Độ trễ giữa hai nút cùng miền là một trường hợp đặc biệt, trong đó giá trị liên miền bằng 0. Hình 19 mô tả một mạng mô phỏng đơn giản. Mô hình này không thể hiện được đầy đủ nhưng vẫn nói lên được phần nào những đặc điểm của mạng Internet thực tế. Dữ liệu mô tả cho mô hình mạng mô phỏng nằm trong hai tệp sẽ được đề cập đến trong phần sau. Trong đó, thời gian trễ liên miền được đặt cố định trong toàn bộ quá trình thực thi của chương trình, thời gian trễ nội miền sẽ được thay đổi sau mỗi lần nút tham gia mạng và giữ nguyên trong thời gian tồn tại của nút trong mạng. Điều này cũng chỉ đóng góp phần nào cho quá trình bất ổn định thời gian trễ tức thời giữa các nút. Hình 17: Mô hình mạng mô phỏng Dữ liệu Chương trình mô phỏng sử dụng khá nhiều loại dữ liệu. Có dữ liệu chỉ được sử dụng trong quá trình khởi tạo, có dữ liệu được đọc lần lượt và sử dùng từ khi bắt đầu chương trình đến khi kết thúc. Phần này chỉ nói đến ý nghĩa của các tệp dữ liệu, cấu trúc tệp được chi hóa tại phụ lục A, việc tạo ra các tệp dữ liệu này sẽ được trình bày chi tiết hơn trong phần thực thi. Thông tin miền Thông tin về miền bao gồm số lượng miền, thời gian trễ liên miền. Giá trị thời gian trễ liên miền sẽ nằm trong khoảng cố định nào đó được đưa ra khi sinh dữ liệu. Cần định khoảng để khi lấy ngẫu nhiên, kết quả thu được phải tương đối phù hợp. Thông tin nút Dữ liệu này chỉ cung cấp xem có tối đa bao nhiêu nút tham gia mạng, các nút thuộc miền nào. Đây là các giá trị cố định trong toàn bộ một chương trình mô phỏng. Thông tin sự vào ra (churn) Đây là dữ liệu để mô phỏng được sự vào ra, không ổn định của các nút. Tại mỗi mốc thời gian mô phỏng, dữ liệu cung cấp thông tin về các nút tham gia hay rời đi cũng như thời gian trễ nội vùng của nó. Thông tin các truy vấn (query) Đây cũng là dữ liệu gắn với quá trình mô phỏng theo mốc thời gian. Tại các mốc thời gian, các truy vấn được phát đi từ nút nguồn để tìm một tài liệu có khóa được chỉ ra. Các đối tượng Chương trình mô phỏng là sự tương tác giữa các đối tượng. Để hình dung được quá trình mô phỏng làm những gì, chúng ta sẽ xem xét các đối tượng và chức năng của chúng. Trong chương trình này, các đối tượng chủ yếu dùng để lưu trữ dữ liệu là chính. Areas Đối tượng lưu trữ thông tin về miền, tệp chứa miền, các thao tác với dữ liệu miền. Quan trọng nhất là phương thức lấy thời gian trễ liên miền. NodeLocation Lưu thông tin về vị trí nút, chính xác là một nút bất kỳ thuộc miền nào. Cùng với Areas là hai đối tượng lưu thông tin để tạo lên topo mạng mô phỏng. FingerEntry Thể hiện một entry trong bảng định tuyến. Thuộc tính idSuccessor với ý nghĩa là định danh successor của khóa mục tiêu tại entry đang xét. Khi định tuyến chúng ta quan tâm đến thuộc tính này. Do cơ chế định tuyến chỉ dựa vào giá trị của định danh, khi thay đổi định danh theo cải tiến, thuật toán định tuyến không cần thay đổi. Đây chính là một lợi thế lớn. Node Mô tả thông tin một nút trong mạng với tên, miền mà nút thuộc về, thời gian trễ nội miền, định danh trên vòng không gian địa chỉ Chord, định danh successor và predeccessor, cuối cùng là bảng định tuyến có kiểu là FingerEntry. Các thao tác với các thuộc tính của nút. Phương thức đáng chủ ý là nextNode(). Trong quá trình truy vấn, một nút có thể sẽ được giao cho một yêu cầu chứa khóa của tài liệu cần tìm kiếm. Nhiệm vụ của nút là phải thông báo trở lại nếu nó là nút quản lý khóa cần tìm (nắm giữ tài liệu nếu có) hoặc chuyển tiếp yêu cầu sang nút khác, những nút gần với câu trả lời hơn. Quá trình chuyển tiếp dựa chủ yếu vào bảng định tuyến, hàm nextNode() sẽ trả lại định danh của nút chuyển tiếp đó. Network Đây có thể coi là đối tượng chính, cơ bản nhất trong chương trình mô phỏng. Đối tượng lưu trữ thông tin tạo lên một topo mạng mô phỏng, tạo ra cấu trúc Chord từ mạng mô phỏng đó cùng quá trình churn của các nút, đồng thời mô ta lại hoạt động cũng như truy vấn dữ liệu trong Chord. Có hai lựa chọn khi khởi tạo một đối tượng Network, đối tượng với thuộc tính type là normal sẽ mô tả cấu trúc Chord truyền thống. Ngược lại nếu type là advance, cấu trúc Chord được mô tả đã có những cải tiến. Một số phương thức cơ bản birth(), death(): Thực hiên khi có một nút tham gia hay rời khỏi mạng. fixFingerTables(): Cập nhật bảng định tuyến của tất cả các nút trong mạng. Hàm thực hiện sau khi có một loạt quá trình vào ra của các nút làm cho bảng định tuyến trở lên lỗi thời. findSuccessor(): Tìm successor của một nút. queryMsg(): Thực hiện truy vấn, dữ liệu đầu vào gồm có khóa cần tìm kiếm và tên nút nguồn. Phương thức trả lại tổng thời gian trễ của truy vấn tính từ nút nguồn cho đến khi nút đích nhận được truy vấn đó. Đây chính là giá trị dùng để đánh giá hiệu quả của cải tiến. Hai quá trình tối ưu nằm lần lượt trong các phương thức birth() khi một nút tham gia mạng và fixFingerTables() khi xây dựng lại bảng định tuyến cho các nút. Tùy vào kiểu của mạng mà hai phần cải tiến nằm trong hai hàm sẽ được kích hoạt hay không. InputGenerator Đối tượng chứa các phương thức để tạo ra các tệp dữ liệu như đã mô tả phần trên. Dữ liệu để cho chương trình có thể vận hành gồm bốn tệp, tương đương có bốn phương thức tạo tệp riêng. Các dữ liệu miền, dữ liệu nút và truy vấn được sinh theo phân bố đều một cách ngẫu nhiên với các giá trị giới hạn là các tham số mô tả trong lời gọi phương thức. Riêng dữ liệu về độ bất ổn (churn) được sinh theo luật phân bố Pareto. Đây là luật phân bố khá phổ biển và đúng đắn trong nhiều lĩnh vực. Distribution Đây là đối tượng cho phép sinh các giá trị theo luật phân bố Pareto như đã nêu. Sau khi khởi tạo bằng các hằng số đặc trưng cho loại phân bố này, đối tượng cho phép sinh một giá trị theo luật bằng phương thức next(). Thư viện hash Một thư viện nhỏ chứa hàm băm sha-1. Thư viện là mã nguồn mở với hai hàm băm tiêu biểu là sha và md5. Riêng sha, thư viện cung cấp nhiều hơn một hàm, do yêu cầu số lượng bit của kết quả (160, 256, 512,…). Do nhu cầu sử dụng là nhỏ nên chương trinhg mô phỏng chỉ thêm hàm băm sha với số lượng bit của kết quả là 160. Thư viện sử dụng khá dễ dàng với API là các phương thức mô tả đơn giản. Các hàm toán học Khá nhiều hàm liên quan đến toán học và những con số. Những hàm này rất cần thiết, phục vụ hầu hết các quá trình tính toán trong chương trình. Đáng kể là hàm băm hash(). Đầu vào của hàm là tên của một nút, đầu ra là một định danh 32 bit. Chương trình mô phỏng chỉ sử dụng không gian địn danh 32 bit vì nhu cầu chỉ cần như vậy. 32 bit này được trích từ những bit đầu tiên của giá trị băm có được từ thư viện hashlib++[40] với 160 bit độ dài. Thực thi Quá trình thực thi cũng được chia thành hai phần riêng biệt: sinh dữ liệu và mô phỏng hoạt động của Chord. Sinh dữ liệu đơn giản chỉ là tạo ra các tệp với dữ liệu bên trong một cách ngẫu nhiên hoặc tuân theo những điều kiện hoặc luật phân bố riêng. Mô phỏng hoạt động của Chord được thực hiện theo các mốc thời gian. Theo đó, tại mỗi mốc thời gian, một số nút tham gia vào mạng và một số rời đi (churn), chương trình sẽ thực hiện vào ra cho các nút, ổn định mạng, thực hiện truy vấn và ghi nhận kết quả truy vấn đó. Sinh dữ liệu Về nguyên tắc, trong một lần thực thi chương trình, có thể vừa sinh dữ liệu, rồi mô phỏng hoạt động của Chord ngay sau đó từ chính những dữ liệu vừa sinh. Xong nên nhớ rằng, chúng ta cần so sánh hiệu năng của mạng cấu trúc Chord truyền thống với mạng sau khi đã cải tiến, nói cách khác chúng ta phải chạy chương trình hai lần với thuộc tính type thay đổi để lấy kết quả. Vì thế, dữ liệu đầu vào giống nhau là cách đánh giá khách quan nhất. Việc sinh mới dữ liệu sau mỗi lần thực thi sẽ làm mất đi tính chất đó. Cho nên, dữ liệu sẽ được tạo riêng, mô phỏng hoạt động của mạng thực thi riêng. Quá trình sinh dữ liệu cần đảm bảo một số yêu cầu. Những yêu cầu này giúp cho dữ liệu được sinh là đúng đắn và tiệm cận với những giá trị của mạng thực tế. Thông tin miền Số lượng miền được định trước, đủ lớn để tạo tính phân tán, nhưng cũng không quá lớn sẽ làm cho mạng mô phỏng trở lên vụn, khó khăn cho việc lưu trữ. Theo các thử nghiệm, số lượng vùng nên nhỏ hơn 128. Sinh ngẫu nhiên các giá trị thời gian trễ liên miền giữa các cặp miền trong khoảng 50-250. Thời gian trễ trên mạng thực tế thường hay nằm trong khoảng này trong điều kiện mạng bình thường. Đơn vị tính độ trễ quy định là ms (mili second). Thông tin nút Số lượng nút tối đa được định trước. Sinh ngẫu nhiên một định danh vùng cho mỗi nút. Quá trình ngẫu nhiên sẽ phân bố đều các nút vào các miền. Quá trình churn Sử dụng luật phân bố Pareto để sinh tên của những nút có sự kiện, thời điểm xảy ra sự kiện đó. Luật phân bố này được sử dụng rất rộng dãi trong các lĩnh vự kinh tế, công nghệ. Độ trễ nội miền được sinh ngẫu nhiên theo phân bố đều (ngẫu nhiên) với các giá trị nhỏ. Trong chương trình, giới hạn của độ trễ này trong đoạn [1, 30]. Truy vấn Sinh ngẫu nhiên số lượng các truy vấn với từng mốc thời gian nằm trong khoảng định trước. Sinh tên của tài liệu cần tìm kiếm. Thực hiện cơ chế băm giống như với quá trình sinh định danh của nút. Kết quả là một số nguyên 32 bit. Tên của nút nguồn đươc sinh ngẫu nhiên, vì thế, có thể khi thực hiện truy vấn, nút này không tồn tại trong mạng. Các giá trị hằng số của quá trình sinh dữ liệu được định nghĩa ngay trong tệp header generator.h. Các giá trị này được lấy theo kinh nghiệm cá nhân nên chắc chắn không thế đúng như mong muốn. Quá trình chạy thử sẽ tạo kinh nghiệm để có thể thay đổi những hằng số này đúng đắn hơn. Thực thi mô phỏng Mục tiêu cuối cùng của phần mô phỏng là các giá trị thời gian trễ. Để có được những giá trị này, cần thực hiện các bước sau: Khởi tạo đối tượng Network theo những tham số đưa ra bao gồm kiểu mạng (cải tiến hay truyền thống) và tên của các tệp input cũng như output. Khởi tạo hai đối tượng để lưu thông tin về miền và nút, đọc những thông tin đó từ các tệp input và đưa vào hệ thống. Thực hiện quá trình lặp theo các mốc thời gian, đọc những thông tin về độ bất ổn, cập nhật thay đổi trạng thái nút trên cấu trúc mạng. Cập nhật lại bảng định tuyến (fingerTable) cho tất cả các nút. Sau bước cập nhật độ bất ổn, đọc các truy vấn trong cùng mốc thời gian, thực hiện truy vấn và ghi nhận thời gian truy vấn theo định dạng cụ thể sao cho thuận tiện cho việc thông kê sau này. Quá trình cải tiến được chia thành hai giai đoạn và lần lượt nằm trong các hàm birth() và fixFingerTables(). birth() Phương thức cho phép một nút tham gia vào mạng ngang hàng. CHOICE là hằng số được sử dụng trong quá trình tối ưu được thực thi ở phương thức này. Hàm băm với dữ liệu đầu vào là chỉ số nút và tham số đầu tiên cho chúng ta một định danh. Định danh này sẽ được sử dụng luôn là định danh của nút nếu mạng mô phỏng có kiểu truyền thống. Nếu là mạng cải tiến, thực hiện lặp CHOICE-1 lần và hàm băm cũng với chỉ số nút và các tham số khác, nhận được CHOICE giá trị băm khác nhau. Với mỗi định danh, tìm successor và predeccessor của định danh đó, đo thời gian trễ đến hai nút hàng xóm này lấy giá trị t nhỏ nhất. Định danh nào có t nhỏ nhất sẽ được chọn là định danh của nút. Thêm nút vào cấu trúc mạng với định danh đã chọn. Chuẩn hóa hai giá trị định danh của successor và predeccessor. Việc cập nhật bảng định tuyến sẽ được thực thi sau khi tất cả sự vào ra của nút trong mốc thời gian đó được thực hiện xong. fixFingerTables() Cập nhật bảng định tuyến của tất cả các nút. Sử dụng hằng số EXPANSION để gia tăng lựa chọn khi xây dựng các entry trong bảng định tuyến. Thực hiện lặp trên bảng định tuyến của nút định danh k, với entry thứ i (0≤ i <ADDR_SPACE), tính giá trị khóa k+2i và tìm successor succ của khóa này. Ghi nhận vào entry i định danh của successor vừa tìm được nếu mạng cấu trúc Chord thường. Ngược lại, tìm xuôi và ngược chiều kim đồng hồ trên không gian định danh Chord từ vị trí của succ, mỗi hướng lấy EXPANSION nút gần nhất, chỉ xét những nút nằm trong khoảng (k+2i-1, k+2i+1], riêng với i=0 thì (k, k+2]. Thực hiện đo thời gian trễ từ nút đang xét tới mỗi nút trong tập tối đa 2*EXPANSION+1 phần tử, nút nào cho giá trị thời gian trễ nhỏ nhất sẽ được chọn và ghi nhận vào entry i. Thực hiện cập nhật trên tất cả các bảng định tuyến. Việc thay đổi bảng định tuyến này không hệ làm cho quá trình định tuyến trở lên sai. Nó có thể làm cho truy vấn đi thêm hoặc bớt một vài bước trước khi đến đích, nhưng sẽ đóng góp vào việc giảm độ trễ tổng của nhiều truy vấn. Kết quả và đánh giá Phần này sẽ trình bày kết quả mô phỏng đạt được. Trước tiên, cần đánh giá hiệu quả của quá trình tối ưu đối với Chord truyền thống trong trường hợp tổng quát nhất. Tiếp theo là xem xét với sự thay đổi của các lựa chọn, quá trình tối ưu sẽ có chiều hướng như thế nào. Hiệu quả so với Chord truyền thống Để thấy được hiệu quả của giải pháp đề xuất, phần này sẽ thực hiện so sánh thời gian truy vấn trung bình của Chord truyền thống và sau khi đã thực thi quá trình tối ưu. Các giá trị thời gian trễ trung bình được đo trong mỗi bước mô phỏng với khoảng 1000 truy vấn trong mỗi bước. Cấu hình mạng mô phỏng: Bộ dữ liệu gồm miền, nút, độ vào ra của nút (churn) và truy vấn (query) được dùng chung trong cả hai trường hợp. 32 miền và 4096 nút tối đa. Quá trình tối ưu sử dụng hai hằng số CHOICE = 8, EXPANSION = 3, tức là lựa chọn trong 8 vị trí để nút tham gia mạng và mở rộng thay đổi bảng định tuyến là 3. Số bước thời gian thử nghiệm là 360 bước (chỉ vẽ 100 bước). So sánh thời gian trễ trung bình trong mỗi bước mô phỏng giữa trường hợp thể hiện ở hình 20. Trục X của đồ thị là bước thời gian thử nghiệm, trục Y là độ trễ tính theo ms(milisecond). Dải điểm tròn đỏ thể hiện thời gian truy vấn trung bình của mạng Chord truyền thống, còn lại là của Chord cải tiến với tham số. Kết quả cho thấy, thời gian trễ trung bình trong mỗi bước của quá trình tối ưu đã giảm đi đáng kể so với Chord truyền thống và ổn định theo các bước mô phỏng. Thời gian trễ trung bình của tất cả các truy vấn sau 360 bước mô phỏng là 759ms với Chord cải tiến, bằng 67% so với 1123ms của Chord. Như vậy, những cải tiến đã cho thấy hiệu quả thực sự. Hình 18: Biểu đồ thời gian trễ trung bình của Chord truyền thống và cải tiến Hiệu quả khi thay đổi tham số Lựa chọn vị trí gia nhập mạng Giá trị lựa chọn vị trí gia nhập mạng được biểu bằng hằng số CHOICE. Các thử nghiệm dùng chung một bộ dữ liệu với 32 miền, 4096 nút, độ mở rộng trong tối ưu bảng định tuyến (hằng số EXPANSION) bằng 3. Thử nghiệm lấy thời gian trễ trung bình qua 3600 bước. Hình 19: Biểu đồ thời gian trễ trung bình biến đổi theo CHOICE Hình 21 có trục X là sự biên thiên hằng số CHOICE, trục Y là giá trị thời gian trễ. Các giá trị CHOICE lần lượt được chọn là 1, 2, 4, 8, 12, 16, 20, 24, 28, 32. CHOICE = 1 là trường hợp đặc biệt, khi đó, cải tiến này không được thực thi, chỉ còn cải tiến thứ hai – tối ưu bảng định tuyến. Như vậy chỉ cẩn áp dụng giải pháp tối ưu bảng định tuyến, thời gian trễ trung bình cũng đã giảm đi đáng kể (814ms). Một điều đễ nhận thấy rằng nếu lượng lựa chọn càng lớn, vị trí nút tham gia (join) vào mạng sẽ càng tối ưu hơn trong quá trình so sánh, giá trị độ trễ ngày càng giảm. Vì thế hiệu năng của cải tiến đem lại cũng tăng theo. Tuy nhiên, hướng của đồ thị ngày càng thẳng, độ dốc giảm dần khi CHOICE lớn dần. Như vậy, giá trị độ trễ trung bình sẽ dần tiệm cận đến một mức nào đó mà thôi. Thêm nữa, nếu lượng lựa chọn là nhiều, sẽ gây trễ lớn khi một nút tham gia vào mạng. Độ mở rộng tối ưu bảng định tuyến thay đổi Độ mở rộng được biểu diễn bằng hằng số EXPANSION. Thử nghiệm dùng chung một bộ dữ liệu với 32 miền, 4096 nút, lượng lựa chọn vị trí tham gia mạng là 16. Thử nghiệm mô phỏng qua 3600 bước, rồi lấy giá trị thời gian truy vấn trung bình. Biểu dồ hình 22 có trục X biểu diễn độ mở rộng, trục Y để biểu diễn độ trễ trung bình. Giá trị EXPANSION lần lượt từ 0 đến 10. Hình 20: Biểu đồ thời gian trễ trung bình theo EXPANSION Khi giá trị của EXPANSION tăng, vì có thêm nhiều lựa chọn đồng nghĩa với việc các entry trong bảng định tuyến tối ưu nên thời gian truy vấn trung bình giảm, hiệu quả của cải tiến được nâng lên. Nhưng cũng giống như với CHOICE, độ dốc của đồ thị giảm, thời gian trễ trung bình sẽ tiến gần đến một giá trị nào đó. EXPANSION = 0, bảng định tuyến không có sự tối ưu vì chỉ có duy nhất một định danh gán cho entry bất kỳ. Lúc này, chỉ còn giải pháp lựa chọn vị trí gia nhập hoạt động, giá trị thời gian trễ trung bình vào khoảng 970, không tốt như khi chỉ có tối ưu bảng định tuyến. Số lượng miền và nút thay đổi Cả hai biểu đồ dưới, mạng Chord cải tiến dùng các giá trị hằng CHOICE = 16, EXPANSION = 3. Hình vẽ 23, lượng nút cố định là 4096, số lượng miền nhận các giá trị 8, 16, 32, 64, 128. Hình vẽ 24, lượng miền cố định 32, lượng nút lần lượt nhận giá trị 512, 1024, 2048, 4096, 8192. Tất cả đều lấy thời gian trễ trung bình sau 3600 bước mô phỏng. Hình 21: Biểu đồ thời gian trễ trung bình thay đổi theo lượng miền Sự thay đổi về số lượng miền quyết định mức độ tập trung của nút như thế nào. Khi số lượng nút không đổi, giá trị miền tăng sẽ làm cho mức độ tập trung của các nút kém, khoảng cách trung bình giữa các nút tăng lên, kéo theo thời gian trễ trung bình tăng. Hình 23, trục X biểu diễn sự biến thiên của lượng miền. Hình 24, trục X biểu diễn sự biến thiên của nút. Khi lượng nút tăng, mỗi nút quản lý một vùng định danh nhỏ hơn, quá trình truy vấn diễn ra lâu hơn do phải chuyển tiếp nhiều lần hơn, theo đó, thời gian truy cập trung bình cũng tăng lên. Hình 22: Biểu đồ thời gian trễ trung bình thay đổi theo lượng nút tối đa Trong cả hai trường hợp trên, đồ thị của Chord cải tiến luôn thấp hơn của Chord truyền thống, dáng của hai đồ thị tương tự nhau. Điều này chứng tỏ, giải pháp tối ưu vẫn đúng đắn và góp phần tăng chất lượng của mạng ngang hàng khi mà các điều kiện mạng thay đổi. Chương 5. Kết luận Kết luận Khóa luận đã đưa ra một cái nhìn tổng quan về mạng ngang hàng, mạng ngang hàng có cấu trúc, đặc biệt tập trung vào cấu trúc Chord và tiềm năng phát triển các ứng dụng dựa trên cấu trúc mạng này. Sau đó, khóa luận đề cập đến một số vấn đề đối với cấu trúc Chord. Đó là sự sai khác về topo giữa mạng logic và mạng vật lý (topology mismatch), xây dựng bảng định tuyến kém hiệu quả; đồng thời nhấn mạnh sự cần thiết phải tìm cách cải tiến, tối ưu những nhược điểm đó. Khóa luận cũng trích lược một số nghiên cứu giải quyết hai vấn đề trên và ưu nhược điểm của những nghiên cứu đó. Dựa vào những yêu cầu đưa ra, khóa luận đã đề xuất một giải pháp mới, nhằm khắc phục hai vấn đề trên. Quá trình tối ưu cũng chia thành hai giai đoạn lần lượt giải quyết hai vấn đề mà cấu trúc Chord gặp phải. Thứ nhất, thực hiện lựa chọn vị trí cho nút tham gia vào mạng theo tiêu chí thời gian trễ thấp đến hai nút liền trước và liền sau, vấn đề sai khác về topo phần nào được giải quyết khi các nút gần nhau trên mạng vật lý có thể cũng gần nhau trên mạng phủ. Thứ hai, thực hiện chọn lựa liên kết khi xây dựng bảng định tuyến, sao cho các liên kết là những đường nối có thời gian trễ thấp, thay đổi này sẽ giúp cho tổng thời gian đáp ứng của một thông báo được phát trên mạng sẽ nhỏ hơn nhờ đi qua những liên kết ngắn. Ưu điểm của phương pháp này so với những nghiên cứu trước là rất dễ thực thi trên nền ứng dụng Chord sẵn có, khả năng tùy biến các lựa chọn khá linh hoạt, giúp cho quá trình tối ưu có thể hoạt động được trên từng điều kiện mạng và những ứng dụng sử dụng cấu trúc Chord cụ thể. Để đánh giá hiệu năng của giải pháp mới, khóa luận đã xây dựng một chương trình, mô phỏng lại một mạng liên kết vật lý, xây dựng mạng ngang hàng có cấu trúc Chord trên mạng vật lý ảo đó, thực hiện việc truy vấn đề lấy thời gian trễ trung bình trên cả cấu trúc Chord truyền thống và Chord sau khi thực thi các giải pháp tối ưu. Kết quả của các phép thử cho thấy, phương pháp tối ưu đem lại hiệu quả thực sự trong việc làm giảm độ trễ của quá trình truyền tin trên mạng ngang hàng. Hướng phát triển tiếp theo của đề tài Kết quả mô phỏng cho thấy tiềm năng của giải pháp tối ưu là rất lớn. Tuy nhiên, đó chỉ là mạng mô phỏng. Để đánh giá hiệu năng của giải pháp một cách đúng đắn nhất, cần thử nghiệm trên một mạng thực sự. Vì thế, trong thời gian sắp tới, hướng đi tiếp của đề tài khóa luận là thực thi giải pháp tối ưu trên mạng Internet. Khi thực nghiệm trên mạng thực tế, có rất nhiều vấn đề nảy sinh: Sự phân tán hoàn toàn giữa các nút làm cho quá trình cập nhật, thử nghiệm, đồng bộ và lấy kết quả khó khăn. Có sự mất gói tin trên mạng thực sự, việc thiết kế giao thức giao tiếp phải được làm thật tốt. Các giá trị hằng số lựa chọn lớn sẽ làm cho quá trình tham gia vào mạng và cập nhật bảng định tuyến mất nhiều thời gian, các gói tin ICMP gửi đi để đo khoảng thời gian trễ có thể gây tràn đường truyền, cản trở giao thông mạng. Như vậy, những vấn đề còn tồn tại không phải là nhỏ. Và để có được những kết quả chính xác, giải pháp tối ưu có ý nghĩa thực sự, làm cơ sở xây dựng những ứng dụng, cần thời gian và sự cố gắng rất nhiều của cả nhóm làm khóa luận. Tài liệu tham khảo Tiếng Việt [1] Mạng_đồng_đẳng [2] Hoàng Ngọc Khánh. Xây dựng mạng ngang hàng có cấu trúc. June 2008. [3] Phan Anh, Nguyễn Đình Nghĩa. Các vấn đề hiện đại trong Công nghệ Thông tin. Lecture 3. English [4] [5] Hancong Duan, Xianliang Lu, Hui Tang; Xu Zhou, Zhijun Zhao. Proximity Neighbor Selection in Structured P2P Network. Computer and Information Technology, 2006. [6] Jonathan Ledlie and Margo Seltzer. Distributed, Secure Load Balancing with Skew, Heterogeneity, and Churn, In Proceedings of IEEE INFOCOM 2005, March 2005. [7] Mingsong Sun, Zhongqiu Zhang. Quasi-Chord: physical topology aware structured P2P network. [8] Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols For Computer Communications (San Diego, California, United States). SIGCOMM ‘01. ACM, New York, NY, 149-160. Phụ lục A A.1. Định dạng dữ liệu Thông tin miền Dòng đầu tiên chứa một số nguyên n là số lượng miền. n*(n+1)/2 dòng tiếp theo, mỗi dòng có cú pháp là a b l. Trong đó, a và b là định danh miền, l là thời gian trễ liên miền giữa hai miền a và b. 32 0 1 171 0 2 161 Thông tin nút Dòng đầu số nguyên N là số lượng nút tối đa. N dòng sau, mỗi dòng có cấu trúc a s. Trong đó, a là chỉ số nút, s là định danh miền mà nút đó thuộc về. 4096 0 18 1 30 Thông tin sự vào ra (churn) Gồm nhiều dòng, mỗi dòng có cấu trúc t c a l. Trong đó, t là nhãn thời gian, thời điểm xảy ra sự kiện; c là loại sự kiện, ‘b’ là nút tham gia, ‘d’ là nút rời đi khỏi mạng, giá trị ‘q’ khi quá trình churn kết thúc; a là chỉ số của nút; l là thời gian trễ nội vùng của nút đó. 00000 b 996 7 00000 b 998 25 00001 b 1003 1 Thông tin các truy vấn (query) Gổm nhiều dòng, mỗi dòng có cú pháp t d n. Trong đó, t là nhãn thời gian; d là định danh tài liệu cần tìm, n là chỉ số của nút nguồn. 0 2609 2642739199 1 3467 2206708070 1 1678 3427259639