Định tuyến trong mạng ngang hàng p2p

KHOA VIỄN THÔNG 1 BỘ MÔN CHUYỂN MẠCH Tên chuyên đề: ĐỊNH TUYẾN TRONG MẠNG NGANG HÀNG P2P Danh sách nhóm 12 STT Họ và tên Lớp Số điện thoại E-mail Nhiệm vụ Ghi chú 1 Nguyễn văn Phúc H10vt1 0983117321 vanphucnguyen4586@gmail.com Viết chương 1 Nhóm trưởng 2 Phạm Văn Đồng H10vt1 01674552698 phamdongh10vt1@gmail.com Viết chương 1 3 Nguyễn Văn Tuyên H10vt1 01886204999 oleola1986@gmail.com Viết chương 2 4 Nguyễn Văn Thái H10vt1 0912278777 vanthai66@gmail.com Viết chương 2 5 Đàm Trọng Tú H10vt1 01686940762 huukhanh_cn@yahoo.com Viết chương 2 ĐỀ CƯƠNG CHI TIẾT Lời nói đầu Các thuật ngữ viết tắt Danh mục các hình vẽ Danh mục các bảng biểu Chương 1: Tổng quan về mạng ngang hàng P2P và định tuyến Tổng quan về mạng ngang hàng Phân loại mạng ngang hàng Hệ thống ngang hàng lai (Hybrid Peer to Peer System) Mạng ngang hàng thuần túy (Pure Peer to Peer System) Kiến trúc siêu ngang hàng (Super-peer Architecture) Mạng ngang hàng có cấu trúc (Structured) Khái quát về định tuyến Bảng định tuyến Định tuyến động và định tuyến tĩnh Định tuyến tĩnh Định tuyến động Kết luận chương 1 Chương 2: Định tuyến trong mạng ngang hàng P2P 2.1. Các thuật toán định tuyến trong mạng ngang hàng P2P 2.2. Định tuyến dựa vào tiền tố (Prefix routing) 2.3. Thuật toán Plaxon et al 2.4. Thuật toán Tapetry 2.5. Thuật toán Pastry 2.6. Thuật toán Chord 2.7. Thuật toán CAN 2.8. Kết luận chương 2 KẾT LUẬN TÀI LIỆU THAM KHẢO GIÁO VIÊN HƯỚNG DẪN TS. LÊ NHẬT THĂNG Lời 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...Trong các loại mạng ngang hàng , mạng ngang hang có cấu trúc hiện nay được sử dụng một cách phổ biến bởi những ưu điểm của nó. Ngày nay nhu cầu về thông tin ngày càng tăng cả về số lượng, chất lượng và các loại hình dịch vụ,…vv điều này đã thúc đẩy thế giới phải tìm ra giải pháp mới. Các kỹ thuật định tuyến đã phần nào giải quyết được một số vấn đề lưu lượng trong mạng. Nội dung được trình bày trong chuyên đề sẽ làm rõ về các vấn đề trên. Do thời gian nghiên cứu chuyên đề cũng như sự  hiểu biết có hạn  nên không tránh khỏi những thiếu sót. Nhóm thực hiện rất mong nhận được sự góp ý từ phía các thầy cô và bạn đọc để nhóm chúng em hoàn thiện hơn nội dung chuyên đề. Chúng em xin chân thành cảm ơn sự giúp đỡ tận tình của Thầy Lê Nhật Thăng cùng các bạn đã cung cấp thêm tài liệu giúp nhóm  em hoàn thành chuyên đề này.                                                Nhóm sinh viên thực hiện Các Thuật Ngữ Viết Tắt Từ viết tắt Nghĩa tiếng Anh Nghĩa tiếng Việt P2P PEER-TO-PEER Mạng Ngang Hàng IP Internet Protocol Giao Thức Mạng Internet DNS Distributed Network System Hệ Thống Mạng Phân Tán DHT Distributed Hash Table Bảng Băm phân Tán ICQ I Seek You Mạng xã hội ICQ SPRR Simple prefix routing Định tuyến đựa và tiền tố đơn giản PC Personal computer Máy tính cá nhân PDA Personal Digital Assistant Thiết Bị kỹ thuật số hỗ trợ cá nhân CPU Central processing unit Bộ sử lý trung tâm ID Identifier Định Dạng IDS integrated data store sự lưu giữ dữ liệu tích hợp DANH MỤC CÁC HÌNH VẼ Danh mục Hình 1.1: Mô hình mạng ngang hàng……………………………………………………..8 Hình 1.2: Mạng ngang hàng lai thế hệ thứ nhất (Napster)……………………………….10 Hình1. 3: Mạng ngang hàng thuần túy (Gnutella 0.4, FreeNet)…………………………11 Hình 1.4: Kiến trúc siêu ngang hàng(Gnutella 0.6, JXTA)………………………….......12 Hình 1. 5: Cơ chế của bảng băm phân tán (DHT)……………………………………….14 Hình 2.1 : Độ dài thông điệp gốc của khối 512 bít………………………………………22 Hình 2.1: Bảng Định Tuyến Chứa các Node có ID……………………………………...24 Hình 2.3: Bảng Finger table và cấp key cho từng node 0,1,3 và keys 1,2,6……………..26 Hình 2.4: Lưu giữ key trong mạng Chord……………………………………………….27 Hình 2.5: Tương tác với chorp qua 2 đường……..………………………………………28 Hình 2.6: Mạng CAN với không gian khóa 2 chiều………………………….………….29 CHƯƠNG I: TỔNG QUAN VỀ MẠNG NGANG HÀNG P2P VÀ ĐỊNH TUYẾN 1.1 Tổng quan về mạng ngang hàng P2P Hiện nay, tên gọi “ mạng ngang hàng ” hay “ mạng đồng đẳng ” và các ứng dụng của kiểu mạng này như là: Napster, Skype, BitTorrent, FlashGet, Sopcast, ICQ...vv..không còn xa lạ gì với người dùng Internet. Mạng ngang hàng (Peer-to-Peer – P2P) bắt đầu xuất hiện từ 1999 và đã thu hút sự quan tâm trong những năm gần đây. Đặc biệt việc áp dụng các mô hình P2P trong việc xây dựng những ứng dụng chia sẻ tệp (file), video, điện thoại trên nền Internet (Internet-based telephony) đã đạt được nhiều thành công. Hiện nay các ứng dụng P2P chiếm khoảng 50% (thậm chí 75%) băng thông trên Internet. Các mạng ngang hàng Peer-to-Peer (P2P) cung cấp một nền tảng tốt để chia sẻ dữ liệu, phân phối nội dung cùng với các ứng dụng truyền thông đa hướng mức ứng dụng ở phạm vi rộng. Các mạng P2P có khả năng cung cấp một kiến trúc định tuyến hiệu quả có tính chất tự tổ chức trên diện rộng, kết hợp với khả năng chịu đựng lỗi, cân bằng tải và quan điểm về vị trí rõ ràng. Như vậy, sự phổ biến của mạng ngang hàng là rất rộng nhưng hiểu biết về mạng ngang hàng, cũng như mạng ngang hàng bao gồm những thành phần gì? Thế nào được gọi là mạng ngang hàng? Cấu trúc ra sao? Hoạt động ra sao? Có bao nhiêu loại mô hình mạng được gọi là mạng ngang hàng?..vv..thì đa phần người dùng chưa có cái nhìn tổng quan và chi tiết về chúng. Trong chương này, chúng em sẽ trình bày về những vấn đề đó. Đầu tiên, chúng em sẽ trình bày về các thành phần trong mạng ngang hàng và khái niệm mạng ngang hàng. Sau đó, chúng em sẽ giới thiệu qua về các loại mô hình mạng ngang hàng. 1.1.1 Định nghĩa mạng ngang hàng Trong tài liệu tham khảo [8], Oram đã định nghĩa về mạng ngang hàng như sau: “Mạng ngang hàng là 1 lớp ứng dụng tận dụng ưu điểm của lưu trữ các tài nguyên, các chu trình, nội dung, giá trị hiện diện của con người ở phía rìa của mạng Internet. Bởi vì việc truy cập tới các tài nguyên phi tập trung này giống như đang hoạt động trong một môi trường kết nối không ổn định và các địa chỉ IP không thể đoán trước được, các nút mạng ngang hàng phải hoạt động bên ngoài hệ thống DNS và có quyền tự trị đáng kể hoặc hoàn toàn độc lập với các máy chủ trung tâm”. Theo định nghĩa này, mạng ngang hàng là một hệ thống phân tán đặc biệt trong tầng ứng dụng, ở đó mỗi cặp điểm nút có thể giao tiếp với nhau thông qua giao thức định tuyến trọng các tầng mạng ngang hàng. Mỗi điểm nút giữ 1 đối tượng dữ liệu nào đó có thể là nhạc, ảnh, tài liệu,..vv... Mỗi điểm nút có thể truy vấn tới đối tượng nó cần từ các điểm nút khác thông qua kết nối logic trong tầng mạng ngang hàng. Và sau đây là mô hình kết nối trong mạng ngang hàng peer to peer Hình 1.1. Mô hình mạng ngang hàng 1.2 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. 1.2.1 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 1.2. 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. 1.2.2 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ình1. 3. 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. 1.2.3 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 1.4. 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). 1.2.4 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 1. 5. 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. 1.3 Khái quát về định tuyến 1.3.1. Khái niêm: - Định tuyến là 1 quá trình chọn lựa các đường đi trên một mạng máy tính để gửi dữ liệu qua đó. - Định tuyến chỉ ra hướng và đường đi tốt nhất từ nguồn đến đích của các gói tin (packer) thông qua các node trung gian là router. 1.3.2. Nguyên tắc định tuyến: - Trong hoạt động định tuyến , người ta chia làm hai loại là định tuyến trực tiếp và định tuyến gián tiếp. Định tuyến trực tiếp là định tuyến giữa hai máy tính nối với nhau vào một mạng vật lý. Định tuyến gián tiếp là định tuyến giữa hai máy tính ở xa các mạng vật lý khác nhau nên chúng phải thực hiện thông qua cac Gateway. - Để kiểm tra xem máy đích có năm trên cùng một mạng vật lý với máy nguồn hay không thì người gửi phải tách lấy địa chỉ mạng của máy đích trong phần tiêu đề của gói dữ liệu và so sánh với phần địa chỉ mạng trong phần địa chỉ IP của nó. Nêu trùng thì gói tin sẽ được truyền trực tiếp nếu không cần phải xác định Gateway để truyền các gói này thông qua nó để ra mạng ngoài thích hợp. 1.4. Bảng định tuyến: - Bảng định tuyến hay còn gọi là bảng chọn đường( Routing table). Các host và các router trên mạng internet đều chứa 1 bảng định tuyến để tính toán các chặng tiếp theo cho gói tin . Bảng định tuyến này gán tương ứng mỗi địa chỉ đích với một địa chỉ Router cần đến ở chặng tiếp theo . Địa chỉ đích trong bảng định tuyến có thể bao gồm cả địa chỉ mang , mạng con và hệ thống độc lâp .Trong bảng định tuyến có thể bao gồm một tuyến mặc định được biểu diễn bằng địa chỉ 0.0.0.0. -Bảng định tuyến có thể tạo ra bởi người quản trị mạng hoặc từ sự thay đổi thông tin định tuyến giữa các router bằng các giao thức định tuyến động. Bảng định tuyến có rất nhiều dạng nhưng đơn giản và phổ biến nhất có thể diễn đạt được bằng mô hình mạng bao gồm các thông tin sau. + Địa chỉ đích của mạng, mạng con và hệ thống độc lập. + Địa chỉ IP của giao diện router kế tiếp phải đến + Giao tiếp vật lý trên router phải sử dụng để đến chặng kế tiếp + Mặt nạ mạng của địa chỉ đích + Khoảng cách quản trị + Thời gian(tính theo giây) từ khi router cập nhật. 1.5.. Định tuyến tĩnh và định tuyến động - Định tuyến là quá trình mà router thực hiện để chuyển gói dữ liệu tới mạng đích. Tất cả các router dọc theo đường đi đều dựa vào địa chỉ IP đích của gói dữ liệu để chuyển gói theo đúng hướng đến đích cuối cùng .Để thực hiện được điều này, router phải học thông tin về đường đi tới các mạng khác .Nếu router chạy định tuyến động thì router tự động học những thông tin này từ các router khác .Còn nếu router chạy định tuyến tĩnh thì người quản trị mạng phải cấu hình các thông tin đến các mạng khác cho router . - Đối với định tuyến tĩnh ,các thông tin về đường đi phải do người quản trị mạng nhập cho router . Khi cấu trúc mạng có bất kỳ thay đổi nào thì chính người quản trị mạng phải xoá hoặc thêm các thông tin về đường đi cho router . Những loại đường đi như vậy gọi là đường đi cố địn. Đối với hệ thống mạng lớn thì công việc bảo trì mạng định tuyến cho router như trên tốn rất nhiều thời gian .Còn đối với hệ thống mạng nhỏ ,ít có thay đổi thì công việc này đỡ mất công hơn . Chính vì định tuyến tĩnh đòi hỏi người quản trị mạng phải cấu hình mọi thông tin về đường đi cho router nên nó không có được tính linh hoạt như định tuyến động .Trong những hệ thống mạng lớn , định tuyến tĩnh thường được sử dụng kết hợp với giao thức định tuyến động cho một mục đích đặc biệt. 1.5.1.Định tuyến tĩnh: 1.5.1.1. Hoạt động định tuyến tĩnh: Hoạt động của định tuyến tĩnh có thể chia ra làm 3 bước như sau: - Đầu tiên ,người quản trị mạng cấu hình các đường cố định cho router. - Router cài đặt các đường đi này vào bảng định tuyến . - Gói dữ liệu được định tuyến theo các đường cố định này . Người quản trị mạng cấu hình đường cố định cho router bằng lệnh iprouter. 1.5.1.2. Cấu hình đường cố định: Sau đây là các bước để cấu hình đường cố định : - Xác định tất cả các mạng đích cần cấu hình ,subnet mask tương ứng và gateway tương ứng .Gateway có thể là cổng giao tiếp trên router hoặc là địa chỉ của trạm kế tiếp để đến được mạng đích . - Bạn vào chế độ cấu hình toàn cục của router . - Nhập lệnh ip router với địa chỉ mạng đích, subnet mask tương ứng và gateway tương ứng mà bạn đã xác định ở bước 1. Nếu cần thì bạn thêm thông số về chỉ số tin cậy . - Lặp lại bước 3 cho những mạng đích khác - Thoát khỏi chế độ cấu hình toàn cục - Lưu tập tin cấu hình đang hoạt động thành tập tin cấu hình khởi động bằng lệnh copy running -config statup-config . 1.5.1.3 Kiểm tra cấu hình đường cố định: Sau khi cấu hình đường cố định ,chúng ta phải kiểm tra xem bảng định tuyến đã có đường ,cố định mà chúng ta đã cấu hình hay chưa ,hoạt động định tuyến có đúng hay không .Bạn dùng lệnh show running -config để kiểm tra nội dung tập tin cấu hình đang chạy trên RAM xem câu lệnh cấu hình đường cố định đã được nhập vào đúng chưa .Sau đó bạn dùng lệnh show ip route để xem có đường cố định trong bảng định tuyến hay không . Sau đây là các bước kiểm tra cấu hình đường cố định : - Ở chế độ đặc quyền ,bạn nhập lệnh show running-config để xem tập tin cấu hình đang hoạt động . - Kiểm tra xem câu lệnh cấu hình đường cố định có đúng không .Nếu không đúng thì bạn phải vào lại chế độ cấu hình toàn cục ,xoá câu lệnh sai đi và nhập lại câu lệnh mới . - Nhập lệnh show ip router. - Kiểm tra xem đường cố định mà bạn đã cấu hình có trong bảng định tuyến hay không. 1.5.2. Định tuyến động: Giao thức định tuyến khác với giao thức được định tuyến cả về chức năng và nhiệm vụ. Giao thức định tuyến được sử dụng để giao tiếp giữa các router với nhau.Giao thức định tuyến cho phép router này chia sẻ các thông tin định tuyến mà nó biết cho các router khác. Từ đó ,các router có thể xây dựng và bảo trì bảng định tuyến của nó. 1.6. Kết luận chương 1 Từ những khái quát cơ bản và tổng quan về mạng ngang hàng P2P là cơ sở cho ta sự lựa chọn phù hợp với từng ứng dụng của các mạng ngang hàng khác nhau. Đồng thời cũng là cơ sở xây dựng những kiến trúc định tuyến khác nhau trong từng mạng ngang hàng. Từ đó đưa ra các thuật toán xây dựng cho các mạng ngang hàng. Và các thuật toán đó được thể hiện rõ nhất ở chương II. CHƯƠNG II: ĐỊNH TUYẾN TRONG MẠNG NGANG HÀNG P2P 2.1. Các thuật toán định tuyến trong mạng ngang hàng P2P Các hệ thống chia sẻ dữ liệu peer-to-peer (P2P) hiện là một trong những ứng dụng Internet phổ biến nhất và đang trở thành nguồn lưu lượng Internet chính. Do vậy, việc mở rộng quy mô cho các hệ thống này là cực kỳ quan trọng. Tuy nhiên, các thiết kế ban đầu cho các hệ thống P2P không phù hợp với các mạng có quy mô lớn, ví dụ như Napster và Gnutella. Nhằm đáp ứng các vấn đề mở rộng quy mô, thế hệ mới các hệ thống P2P hỗ trợ tính năng bảng hàm băm phân tán (DHT), trong số đó là Tapestry, Pastry, Chord và CAN (Content-Addressable Networks). Trong các hệ thống này (còn gọi là các hệ thống DHT), các file được ràng buộc với các khoá (key). Tính năng DHT này được chứng minh là một cơ sở hữu ích cho các hệ thống phân phối lớn; một số các dịch vụ ứng dụng DHT như: các hệ thống file phân tán, truyền thông đa hướng (multicast) mức ứng dụng, các dịch vụ khai báo sự kiện, và các dịch vụ trò chuyện (chat). Với rất nhiều các ứng dụng đang được phát triển trong thời gian qua, chúng ta mong đợi tính năng DHT sẽ trở thành một phần tích hợp trong P2P tương lai. Mạng ngang hàng bao gồm tất cả các nút mạng đại diện cho các máy tham gia và các liên kết giữa các nút mạng này. Một liên kết tồn tại giưã hai nút mạng khi một nút mạng biết vị trí nút mạng kia. Dựa vào cấu trúc liên kết giữa các nút mạng trong mạng ngang hàng ta có thể phân loại thành 2 loại: Mạng ngang hàng không cấu trúc Mạng đồng đẳng có cấu trúc Mạng ngang hàng không cấu trúc Mạng ngang hàng không cấu trúc: khi các liên kết giữa các nút mạng trong mạng ngang hàng đươc thiết lập ngẫu nhiên(tức là không theo quy luật nào ). Những mạng như thế này dễ dàng được xây dựng vì một máy mới khi muốn tham gia mạng có thể lấy các liên kết có sẵn của một máy khác đang ở trong mạng và sau đó dần dần tự bản than nó sẽ thêm vào các liên kết mới của riêng mình.Khi một máy muốn tìm môt dữ liệu trong mang ngang hàng không cấu trúc, yêu cầu tìm kiếm sẽ đươc truyền trên cả mạng để tìm ra càng nhiều máy chia sẻ càng tốt. Các thuật toán định tuyến không cấu trúc: Napster Gnutella Fasttrack eDonkey2000 Mạng đồng đẳng có cấu trúc Mạng đồng đẳ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 bảng băm phân tán DHT(Distributed Hash Table). Bảng băm phân tán này định nghĩa liên kết giữa các liên kết trong mạng ngang hang 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 tử 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ả.Các thuật toán định tuyến trong mạng có cấu trúc: Prefix routing Paxon et on Chord Can Pastry Tapestry 2.2. Định tuyến dựa vào tiền tố (Prefix routing) Định tuyến dựa vào tiền tố (Prefix routing) - PRR: đây là thuật toán đầu tiên cho việc tìm kiếm và định tuyến của mạng ngang hàng. Bằng cách ánh xạ nhận dạng đối tượng thành không gian địa chỉ của các peers, PRR định tuyến dựa trên key và có thể trợ giúp các thao tác: đọc, chèn và xóa đối tượng lưu trữ trong mạng chồng phủ. Nguyên lý của thuật toán này là nền tảng cho các thiết kế DHT sau này. PRR là định tuyến dựa trên hậu tố, là trường hợp đối xứng của định tuyến tiền tố. Định tuyến hậu tố và tiền tố đều dựa trên sự giống nhau để tăng vị trí của địa chỉ đích tại mỗi hop dọc theo đường cho đến khi đích đạt tới. Thiết kế PPR dựa trên tập các node tĩnh; không quan tâm tới thành viên là các node động, không có kỹ thuật cập nhật bảng định tuyến khi node ra nhập hoặc rời mạng. Phiên bản đơn giản của PRR được gọi là SPRR được đưa ra bởi Li and Paxton. Một số các thuật toán Tapestry, Pastry, P-Grid, Cycloid, and Z-Grid. Plaxton, Rajaraman đều dựa trên PRR. 2.3. Thuật toán Plaxon et al Plaxon et al: Plaxon et al là một phiên bản của PRR, đây là thuật toán đầu tiên được sử dụng trên quy mô lớn bởi các DHT, nhưng không cung cấp việc định tuyến tìm kiếm hiệu quả. Thuật toán của Plaxton ban đầu được tạo ra để định tuyến các truy vấn Web tới các cache lân cận, và nó ảnh hưởng đến thiết kế của Pastry, Tapestry và Chord. Phương pháp Plaxton có độ phức tạp tham gia/rời bỏ theo hàm loga. Plaxton đảm bảo các truy vấn không bao giờ đi xa hơn trong khoảng cách mạng so với peer mà lưu giữ key. Tuy nhiên, Plaxton cũng có một số nhược điểm: yêu cầu hiểu biết toàn bộ để xây dựng mạng chồng; peer gốc của đối tượng là điểm lỗi đơn; không có sự chèn thêm hoặc xoá bỏ peer; không có sự tránh các điểm tắc nghẽn nóng. Đối với một hệ thống n node, mỗi node có O(log n) lân cận, độ dài đường định tuyến O(log n) bước nhảy 2.4. Thuật toán Tapetry Tapestry sử dụng một biến thể của thuật toán Palaxon et al và thêm vào tính năng động cho các pees trong mạng chồng. Sử dụng định tuyến dựa vào tiền tố, Tapestry sử dụng thuật toán SHA-1 để băm các địa chỉ node thành các ID biểu diễn theo hệ số 2. Để hiểu rõ hơn về vấn đề ta sẽ tìm hiểu về thuật toán SHA-1 : Khởi gán các biến: H0:=0x67452301 H1:=0xEFCDAB89 H2:=0x98BADCFE H3:=0x10325476 H4:=0xC3D2E1F0 Tiền xử lý: Thêm 1 bít vào thông điệp. Thêm vào k bit 0 sao cho độ dài thông diệp đồng du 448 (mod 512). Thêm 64 bít biểu diễn độ dài của thông điệp gốc ( giá trị lưu dạng big –endian) Hình 2.1. Độ dài thông điệp gốc của khối 512 bít Từ hình vẽ 2.1 ta chia thông điệp ( pha đinh) thành các khối 512 bít. Mỗi khối 512 bít: Chia thành 16 word (32 bít, big-endian) w[0..15] w[i]=(w[i-3]Å w[i-8] Å w[i-14] Å w[i-16]) <<< 1 với 16 £ i < 80 A= h0, B= h1, C= h2, D= h3, E= h4 80 chu kỳ xử lý h0+=A, h1+=B, h2+=C, h3+=D, h4+=E Kết quả:= h0 | h1 | h2 | h3 | h4 Å:phép Xor Chu kỳ xử lý: t là số thứ tự của chu kỳ A, B, C, D, E là 5 word (32 bit) của trạng thái F là hàm phi tuyến (thay đổi tùy theo chu kỳ) <<< n là phép quay trái n vị trí ⊞ phép cộng modulo 232. Kt là hằng số . XY phép toán AND trên bít giữa X và Y XY phép toán OR trên bít giữa X và Y XY phép toán XOR trên bít giữa X và Y X phép toán NOT trên bít X Hình 2.2. Bảng Định Tuyến Chứa các Node có ID Mỗi node lưu giữ một bảng định tuyến gồm log 2(N) hàng và 2cột. Hàng thứ nhất trong bảng định tuyến chứa các node có ID khác với ID của node đó ở chỉ số thứ nhất. Hàng thứ hai trong bảng định tuyến chứa các node có ID giống với ID của node đó ở chữ số thứ nhất nhưng khác ở chữ số thứ hai. Các hàng còn lại của bảng định tuyến cũng được tổ chức tương tự. Quá trình tìm kiếm được thực hiện bằng cách so sánh lần lượt các chữ số tiền tố của ID. Ví dụ 4*** 42**422*4227, quá trình này gọi là “ánh xạ lân cận”. Bảng định tuyến của một node X được chia thành nhiều mức (log2(N)), mỗi mức i bao gồm các liên kết (2-1) đến các node có tiền tố giống đến chữ số thứ i-1 với ID của X. khi một node định tuyến đến node đích nó sẽ đi theo đường đến node có ID gần giống với ID đích nhất (dựa theo bảng định tuyến). Sau mỗi chặng node tiếp theo sẽ có mức cao hơn ít nhất là 1, vì vậy sau nhiều nhất là log 2(N) chặng quá trình tìm kiếm kết thúc. 2.5. Thuật toán Pastry Trong Pastry việc định tuyến bao gồm việc chuyển truy vấn tới node lân cận có tiền tố được chia sẻ dài nhất với key (và, trong trường hợp chặt chẽ, thì tới node có bộ nhận dạng gần nhất về số đối với key). Pastry có O(log n) lân cận và định tuyến trong vòng O (log n) bước nhảy . 2.6. Thuật toán Chord Hệ thống và các ứng dụng peer-to-peer là các hệ thông phân tán không cần bộ xử lý trung tâm, các phần mềm được chạy trên các node và thực hiện các chức năng của nó. Các đặc điểm của ứng dụng peer-2-peer như : lưu trữ bản dự phòng, lâu dài, lựa chọn điểm gần, tìm kiếm, xác thực, phân cấp tên.Thực tế với nhiều đặc điểm tốt, lõi (core)của hầu hết các hệ thống peer-2-peer đều dựa trên xác định vị trí dữ liệu. 2.6.1. Giao thức Chord Giao thức Chord được thiết kế giống như giao thức định tuyến DHT nhằm mục đích phát triển một cách phân tán dữ liệu tốt nhất, các node được phân phối IDs và Keys với nhiều đặc trưng như Scalability(đánh giá), Complete Decentralization(phân quyền), Efficient Load Blancing(cân bằng tải), và Simplicity( đơn giản). Chord coi các khóa Key là các điểm trên một đường tròn. Không gian khóa đường tròn được chia thành các cung liên tiếp mà điểm cuối của cung này là các định danh ID của các node. Mỗi node lưu trữ thông tin định tuyến tới các node khác trong một bảng định tuyến được gọi là Finger Table. Hình 2.3. Bảng Finger table và cấp key cho từng node 0,1,3 và keys 1,2,6 Giao thức Chord hỗ trợ duy nhất một hoạt động : đưa ra 1 key, nó sẽ ánh xạ key đó vào 1 node.Tùy thuộc vào ứng dụng sử dụng Chord ( văn bản, hình ảnh, media..), node đó sẽ lưu trữ một giá trị kết hợp với key. Chord sử dụng kí thuật consistent hashing để cấp key cho các node.Consistent hashing dùng để cần bằng tải, mỗi node sẽ nhận được số lượng key gần ngang nhau, vào làm cả việc chuyển số lượng key khi có node tham gia hay rời khỏi hệ thống. Kĩ thuật consistent hashing đầu tiên sẽ nhận biết các node trong hệ thống, tạo ra sự cân chỉnh về số lượng các node. Mỗi node trong Chord cần được "routing" để biết thông tin về một vài node khác. Vì bảng định tuyến là phân tán, 1 node sẽ sử dụng hàm băm để giao tiếp với các node khác. Khi mạng được thiết lập, 1 hệ thống gồm N-node, trong đó mỗi node chứa thống tin về O(log N) node xung quanh nó, và tìm kiếm các node khác thông qua O(log N) thông điệp tới các node đó. Chord duy trì thông tin định tuyến khi các node tham gia/rời khỏi hệ thống. Với một hệ thống có tần suất cao, một node cũng chỉ cần gửi không quá O(log2 N) thông điệp để định tuyến. 2.6.2. Á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 2.4. Lưu giữ key trong mạng Chord 2.6.3. Đặc Điểm Hệ Thống Chord Chord được thiết kế dựa trên các vấn đề sau :- Load Balance ( phân tải) : Chord sử dụng bảng băm phân tán, phân tải trên các node, một node sẽ không chứa quá nhiều kay.- Decẻntralization (phân quyền): Chord là phân tán hoàn toàn, không node nào quan trọng hơn node nào, việc này cải thiện được sự vững chắc của hệ thống.- Scalability ( đánh giá) : giá của việc tìm kiếm tăng lên theo Log của số node : Log(n)- Availability (tiện dụng) : Chord tự điều chỉnh các bảng định tuyến khi có node tham gia và rời khỏi mạng Flexible naming ( định nghĩa tên linh hoạt) : Chord không ràng buộc về cấu trúc của key mà nó tìm kiếm, không gian key là phẳng bằng việc gán cho key một cái tên và tìm kiếm. ( ví dụ phẳng tức là đưa tất cả các loại key về thành 1 kiểu như id , khi tìm thì chỉ cần tìm id của key) Phần mềm Chord tạo ra một liên kết giữa client và server của ứng dụng. Ứng dụng tương tác với Chord qua 2 đường :- Chord cung cấp các thuật toán lookup(key) Hình 2.5.Tương tác với chord qua 2 đường Chord nhận biết sự thay đổi của key khi node phản ứng ( ví dụ khi có 1 node tham gia vào mạng, nó sẽ được node bên cạnh chuyển cho một số lượng key lưu giữ) 2.7. Thuật toán CAN Định tuyến trong CAN hoạt động bằng cách đi theo một hướng thẳng thông qua không gian Cartesian từ nguồn đến tọa độ điểm đến. Một node có thể duy trì một bảng định tuyến toạ độ chứa địa chỉ IP và vùng toạ độ ảo của mỗi của nó các nút lân cận trực tiếp trong không gian tọa độ. Trong một phối hợp d-chiều không gian, hai nút là láng giềng nếu kéo dài toạ độ của họ chồng lên nhau cùng kích thước và tiếp nối dọc theo một chiều. Sử dụng toạ độ nút lân cận của nó để thiết lập, một nút định tuyến thông điệp theo hướng đích của nó bằng cách chuyển tiếp tham lam (greedy) đơn giản tới nut lân cận có tọa độ gần với các tọa độ đích. 2.7.1. Mô hình mạng CAN Mạng CAN là một không gian n chiều. Không gian khóa được chia thành các vùng nhỏ cho các node trong mạng quản lý, mỗi node sẽ chịu trách nhiệm toàn bộ các khóa trong vùng quản lý nắm giữ. Mỗi khóa là một cặp (khóa, giá trị) , cặp (khóa,giá trị) này được ánh xạ vào node tương ứng. Các node trong mạng CAN sẽ duy trì thông tin định tuyến với các node hàng xóm của nó, là các node có vùng quản lý tiếp giáp với nhau. Các node hàng xóm này sẽ liên lạc với nhau để định tuyến tìm tới các node lưu giữ khóa ở xa. Hình 2.6.Mạng CAN với không gian khóa 2 chiều 2.7.2. Cấu trúc CAN Như mô tả ở trên, toàn bộ không gian CAN được chia giữa các nút hiện tại trong hệ thống. Để cho phép CAN phát triển từng bước, một nút mới gia nhập hệ thống phải được phân bổ riêng phần của không gian toạ độ. Điều này được thực hiện bởi một tách nút hiện tại, khu vực của nút được phân bổ một nửa, giữ lại một nửa và bàn giao nửa còn lại đến nút mới. Quá trình này có ba bước: Đầu tiên là nút mới phải tìm thấy một nút đã có trong CAN. CAN sử dụng cơ chế định tuyến, nó phải tìm một nút khu vực mà sẽ được chia. Những nút lân cận của vùng tách phải được thông báo định tuyến có thể bao gồm các nút mới. 2.7.3. Tìm kiếm trong mạng CAN Một node sẽ chịu trách nhiệm quản lý một vùng trong mạng gọi là “zone”, các khóa nằm trong vùng này sẽ được ánh xạ vào node đó. Một node khác cần tìm kiếm khóa k sẽ tìm tới node chịu trách nhiệm quản lý vùng có khóa k. Các node sẽ tìm kiếm khóa dựa vào các hàng xóm của nó. Hai node được gọi là hàng xóm của nhau nếu có chung một chiều quản lý trong vùng của mỗi node hay hai node có một chiều tiếp giáp nhau. Để duy trì tập các hàng xóm này thì mỗi node trong mạng CAN tạo ra một bảng định tuyến, bảng định tuyến sẽ lưu các node hàng xóm để khi cần sẽ định tuyến tới. Thông tin định tuyến sẽ được truyền đi liên tiếp các node lân cận của nhau cho tới khi tới được node có vùng quản lý khóa cần tìm kiếm. 2.8. Kết luận chương 2 Mạng có cấu trúc, thường gọi là các mạng P2P thế hệ mới, thường sử dụng mô hình định tuyến dựa trên bảng băm phân tán DHT để làm giảm chi phí định tuyến và cung cấp một giới hạn cho số bước nhảy được yêu cầu trong việc tìm kiếm một mục dữ liệu. Các hệ thống như vậy có các ưu điểm như: tính phân tán, khả năng mở rộng, tính sẵn sàng, khoảng cách định tuyến ngắn, sức chịu đựng lỗi. Định tuyến DHT dựa trên khái niệm định tuyến trên cơ sở tiền tố, ban đầu được giới thiệu bởi Plaxton để hỗ trợ sự tham gia/ rời bỏ động của các peer và để cung cấp các cơ chế khôi phục khi gặp lỗi. Nói cách khác, các mạng P2P có cấu trúc có nghĩa là tô pô mạng P2P được điều khiển chặt chẽ và các các đối tượng dữ liệu được đặt tại các vị trí cụ thể sao cho đạt được hiệu năng truy vấn tốt hơn. Khoảng mười năm trở lại đây, thế giới đã chứng kiến sự bùng nổ của Internet băng thông rộng, cùng với nó là sự phát triển mạnh mẽ của các ứng dụng peer-to-peer. Với nhiều ưu điểm hứa hẹn như tính hiệu quả, linh hoạt và khả năng mở rộng cao, các mạng peer-to-peer đã và đang thu hút được nhiều sự quan tâm từ cộng đồng nghiên cứu. Mạng peer-to-peer đã phát triển qua nhiều thế hệ, thế hệ hiện nay là mạng có cấu trúc dựa trên khả năng lưu trữ và tìm kiếm dữ liệu hiệu quả theo cơ chế Bảng băm phân tán (DHT). Vấn đề cốt lõi của P2P là các thuật toán định tuyến, nó đóng vai trò quyết định hiệu quả hoạt động khi thiết lập các dịch vụ hệ thống nền tảng của mạng ngang hàng nói riêng và mạng ảo trên Internet nói chung. Tài liệu tham khảo [1] Hoàng Trọng Minh, Nguyễn Thị Thanh Trà “Kỹ thuật chuyển mạch 1” Học viện công nghệ BCVT _ 5/2007. [2] Vũ Thị Thuý Hà, Lê Nhật Thăng “Kỹ thuật chuyển mạch 2” Học viện công nghệ BCVT _ 2007. [3] Lê Nhật Thăng, Vũ Thị Thuý Hà “Hệ thống định tuyến tốc độ cao” Học viện công nghệ BCVT. [4] Hồ Bảo Quốc “Triển khai NGN của VNPT” Báo cáo thực tập tốt nghiệp 8/2008. [5] Juniper Network’s doccuments “System Basics Configuration Guide” www.juniper.net. [6] Juniper Network’s doccuments “ERX Command Reference Guide” www.juniper.net. [7] Juniper Network’s doccuments “M320 – Hwguide ” www.juniper.net. [8] Andy Oram. “Peer to Peer: Harnessing the Power of Disruptive Technologies”. OReilly Publishing, first edition March 2001. Page 9,page 19. Chapter 8. [9] TS. Lê Nhật Thăng, ThS.Vũ Thị Thúy Hà, Định tuyến trong mạng ngang hàng thế hệ mới