Luận văn: Gestion de groupe et détection de partition en mobile - Nguyễn Tuấn Dũng

Luận văn thạc sĩ nghiên cứu vnu gestion de groupe et détection de partition en environnement mobile, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh

• Tác giả: Nguyen Tuan Dung
• Người hướng dẫn: Denis Conan
• Trường học: Institut National des Télécommunications
• Chuyên ngành: Informatique
• Đề tài: Gestion de groupe et détection de partition en environnement mobile
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2005
• Địa điểm: Évry

Mục lục chi tiết

• Lời cảm ơn
• Tóm tắt
• Tóm tắt tiếng Anh
• Danh mục hình vẽ
• Danh mục bảng biểu
• Danh mục thuật toán
• 1. Chương 1: Giới thiệu
• 1.1. Đặt vấn đề
• 1.2. Động lực và mục tiêu thực tập
• 1.3. Môi trường làm việc
• 1.4. Đóng góp
• 1.5. Bố cục tài liệu
• 2. Chương 2: Các bộ phát hiện trong môi trường di động
• 2.1. Mô hình tổng quát
• 2.2. Bộ phát hiện lỗi không tin cậy
• 2.3. Bộ phát hiện kết nối
• 2.4. Bộ phát hiện mất kết nối
• 2.5. Bộ phát hiện phân vùng
• 3. Chương 3: Hệ thống truyền thông nhóm
• 3.4. Nghiên cứu hai triển khai hiện có
• 3.5. Lựa chọn triển khai
• 4. Chương 4: Đặc tả dịch vụ quản lý nhóm mới
• 4.1. Mô hình hệ thống phân tán
• 4.3. Sơ đồ lỗi
• 4.4. Sơ đồ mất kết nối
• 4.5. Sơ đồ phân vùng
• 4.6. Các thuộc tính của dịch vụ quản lý nhóm
• 5. Chương 5: Kiến trúc, thuật toán và nguyên mẫu
• 5.1. Kiến trúc
• 5.4. Tiến độ phát triển
• 6. Chương 6: Kết luận và hướng phát triển
• Tài liệu tham khảo
• Phụ lục A: Chứng minh

Tóm tắt

I. Giải mã luận văn thạc sĩ VNU Quản lý nhóm di động

Luận văn thạc sĩ với chủ đề Gestion de groupe et détection de partition en environnement mobile là một công trình nghiên cứu chuyên sâu, thuộc chương trình đào tạo thạc sĩ Công nghệ thông tin của Đại học Quốc gia Hà Nội (VNU), hợp tác với Viện Tin học Pháp ngữ (IFI). Đề tài này tập trung giải quyết các bài toán cốt lõi trong lĩnh vực hệ thống phân tán di động, một lĩnh vực ngày càng trở nên quan trọng với sự bùng nổ của các thiết bị không dây và mạng ad-hoc. Mục tiêu chính của luận văn là xây dựng một dịch vụ quản lý nhóm trong môi trường di động có khả năng chịu lỗi cao và xử lý hiệu quả các tình huống phức tạp như ngắt kết nối và phân vùng mạng. Khác với các hệ thống phân tán truyền thống, môi trường di động đặc trưng bởi sự thay đổi liên tục của topo mạng, kết nối không ổn định và tài nguyên hạn chế. Điều này đòi hỏi các cơ chế và thuật toán phải linh hoạt và thích ứng. Nghiên cứu đề xuất một dịch vụ quản lý nhóm mới, không chỉ đồng thuận về tập hợp các tiến trình đang hoạt động và kết nối, mà còn đồng thuận về các tiến trình bị lỗi, ngắt kết nối hoặc bị cô lập trong các phân vùng mạng. Để đạt được mục tiêu này, luận văn kế thừa và phát triển các công trình trước đó về các bộ phát hiện (detectors) trong môi trường di động, bao gồm bộ phát hiện lỗi, bộ phát hiện kết nối, bộ phát hiện ngắt kết nối và đặc biệt là bộ phát hiện phân vùng. Cách tiếp cận này giúp các ứng dụng phân tán có được cái nhìn toàn diện và chính xác hơn về trạng thái của hệ thống, từ đó đưa ra các quyết định xử lý phù hợp, đảm bảo tính sẵn sàng của hệ thống và độ tin cậy. Luận văn này là một tài liệu tham khảo giá trị cho các nhà nghiên cứu và sinh viên quan tâm đến đề tài thạc sĩ về mạng máy tính và hệ thống phân tán.

1.1. Bối cảnh và tầm quan trọng của đề tài nghiên cứu

Sự phát triển của mạng không dây và các thiết bị di động đã tạo ra một mô hình tính toán mới, được gọi là "tính toán di động". Mô hình này cho phép người dùng truy cập dữ liệu và dịch vụ ở bất kỳ đâu, bất kể vị trí địa lý. Tuy nhiên, trong môi trường di động, các thiết bị thường xuyên bị ngắt kết nối. Đặc điểm này đòi hỏi các cơ chế chuyên biệt để quản lý ngắt kết nối và fault tolerance in mobile systems. Dịch vụ quản lý nhóm (group membership) là một thành phần nền tảng của các hệ thống giao tiếp nhóm (group communication protocols), vốn là viên gạch quan trọng để xây dựng các ứng dụng phân tán phức tạp. Nghiên cứu này ra đời nhằm giải quyết những thách thức đó, bằng cách đề xuất một dịch vụ quản lý nhóm nâng cao, có khả năng phân biệt rõ ràng giữa các trạng thái lỗi, ngắt kết nối và phân vùng mạng, điều mà nhiều hệ thống trước đây còn hạn chế.

1.2. Mục tiêu chính của luận văn Đại học Quốc gia Hà Nội

Luận văn đặt ra hai mục tiêu chính. Thứ nhất, xây dựng một dịch vụ quản lý nhóm cho các tiến trình có khả năng bị phân vùng, đồng thời chịu được tính di động và kết nối không ổn định của các thiết bị đầu cuối. Dịch vụ này phải đảm bảo tính nhất quán về trạng thái thành viên nhóm trên toàn hệ thống. Thứ hai, khai thác các bộ phát hiện (detectors) đã có để định nghĩa các thuộc tính và dịch vụ phân tán mới. Cụ thể, luận văn hướng đến việc đạt được sự đồng thuận không chỉ về tập hợp các tiến trình đang hoạt động (correct and connected), mà còn về tập hợp các tiến trình bị lỗi (failed), ngắt kết nối (disconnected) và bị phân vùng (partitioned). Việc đạt được sự đồng thuận đa trạng thái này là một đóng góp mới, giúp tăng cường sự tin cậy và khả năng phục hồi cho các ứng dụng phân tán di động. Luận văn được thực hiện tại phòng thí nghiệm SAMOVAR, thuộc Viện Viễn thông Quốc gia Pháp (INT).

II. Thách thức chính Phát hiện phân vùng mạng di động

Môi trường di động mang đến những thách thức đặc thù mà các hệ thống phân tán có dây truyền thống không phải đối mặt. Một trong những vấn đề nan giải nhất là tình trạng network partitioning, tức là mạng bị chia cắt thành nhiều phân vùng độc lập, khiến các tiến trình trong các phân vùng khác nhau không thể giao tiếp với nhau. Tình trạng này có thể xảy ra do lỗi liên kết vật lý, một tiến trình quan trọng bị lỗi, hoặc do một thiết bị tự nguyện ngắt kết nối để tiết kiệm năng lượng. Thách thức lớn nhất là phân biệt được nguyên nhân gây ra sự mất liên lạc. Một tiến trình không phản hồi có thể do nó đã bị lỗi (crash), do người dùng chủ động ngắt kết nối, hay chỉ đơn giản là nó đang nằm trong một phân vùng mạng khác. Các hệ thống truyền thống thường xem tất cả các trường hợp này là lỗi, dẫn đến các hành động xử lý không chính xác và lãng phí tài nguyên. Luận văn chỉ ra rằng việc phân biệt rõ ràng ba trạng thái này là cực kỳ quan trọng. Theo trích dẫn từ nghiên cứu [7], "Avec l'apparition du détecteur de partition, nous pouvons faire la distinction entre les défaillances, les déconnexions et les partitions." (Với sự ra đời của bộ phát hiện phân vùng, chúng ta có thể phân biệt giữa lỗi, ngắt kết nối và phân vùng). Việc giải quyết được sự mơ hồ này là tiền đề để xây dựng các thuật toán quản lý nhóm hiệu quả và các hệ thống có tính sẵn sàng của hệ thống cao hơn. Các Mobile Ad-hoc Networks (MANETs) là môi trường điển hình nơi các vấn đề này biểu hiện rõ rệt nhất, đòi hỏi một giải pháp toàn diện và tinh vi.

2.1. Vấn đề về Fault Tolerance và tính sẵn sàng của hệ thống

Khả năng chịu lỗi (fault tolerance in mobile systems) là một yêu cầu cơ bản đối với mọi hệ thống phân tán. Hệ thống phải đảm bảo hai thuộc tính quan trọng: an toàn (sûreté - safety) và sống động (viva ité - liveness). An toàn đảm bảo rằng các hành vi xấu không bao giờ xảy ra, trong khi sống động đảm bảo các hành vi tốt cuối cùng sẽ xảy ra. Tuy nhiên, trong môi trường không đồng bộ (asynchronous), nơi không có giới hạn về tốc độ xử lý hay thời gian truyền tin, việc đạt được đồng thuận là bất khả thi nếu có dù chỉ một tiến trình bị lỗi [14]. Đây là một rào cản lớn cho việc xây dựng các hệ thống giao tiếp nhóm tin cậy. Luận văn giải quyết vấn đề này bằng cách hoạt động trong mô hình bán đồng bộ (partially synchronous), sử dụng khái niệm bộ phát hiện lỗi không tin cậy (unreliable failure detectors) [10] làm nền tảng.

2.2. Đặc thù của Mobile Ad hoc Networks MANETs và kết nối

Môi trường tính toán di động, đặc biệt là Mobile Ad-hoc Networks (MANETs), có bốn đặc điểm chính gây ra nhiều thách thức [24]: (1) các thiết bị di động có tài nguyên rất hạn chế; (2) tính di động và kết nối tiềm ẩn nhiều rủi ro (mất, cắp); (3) kết nối không dây có hiệu suất và độ tin cậy biến đổi cao; (4) nguồn năng lượng của thiết bị bị giới hạn. Các thiết bị có thể chủ động ngắt kết nối (voluntary disconnection) để tiết kiệm chi phí, năng lượng, hoặc bị ngắt kết nối đột ngột (involuntary disconnection) khi đi vào vùng không có sóng. Những yếu tố này làm cho việc duy trì trạng thái nhóm ổn định trở nên cực kỳ khó khăn và đòi hỏi các giải pháp thích ứng linh hoạt.

2.3. Sự mơ hồ giữa lỗi ngắt kết nối và phân vùng mạng

Đây là vấn đề cốt lõi mà luận văn tập trung giải quyết. Tình trạng phát hiện phân vùng mạng (network partitioning) có thể xảy ra do nhiều nguyên nhân: một liên kết bị lỗi, một tiến trình trung tâm bị lỗi, hoặc một tiến trình ngắt kết nối. Khi một tiến trình p không thể liên lạc với tiến trình q, p không thể biết chắc chắn rằng q đã bị lỗi, tự ngắt kết nối, hay đang nằm ở một phân vùng khác. Sự mơ hồ này dẫn đến tình trạng không nhất quán (incoherence) giữa các bộ phát hiện của các tiến trình khác nhau. Ví dụ, p có thể nghi ngờ q bị phân vùng, nhưng một tiến trình r khác lại nghi ngờ q bị lỗi. Luận văn đề xuất xây dựng một dịch vụ quản lý nhóm nằm trên các bộ phát hiện này để giải quyết sự không nhất quán, tạo ra một cái nhìn đồng thuận trên toàn hệ thống.

III. Phương pháp tiếp cận dựa trên hệ thống các bộ phát hiện

Để giải quyết các thách thức trong môi trường di động, luận văn không phát minh lại từ đầu mà dựa trên một nền tảng vững chắc là hệ thống các bộ phát hiện (detectors). Cách tiếp cận này cho phép tách biệt logic phát hiện trạng thái khỏi logic xử lý của ứng dụng, tạo ra một kiến trúc module và linh hoạt. Luận văn tích hợp và mở rộng bốn loại bộ phát hiện chuyên biệt, mỗi loại chịu trách nhiệm giám sát một khía cạnh khác nhau của hệ thống phân tán di động. Bộ phát hiện lỗi không tin cậy (Failure Detector - FD) kế thừa từ công trình của Chandra và Toueg [10] giúp giải quyết bài toán đồng thuận trong môi trường bán đồng bộ. Bộ phát hiện kết nối (Connectivity Detector - CD) giám sát tài nguyên cục bộ (như pin, cường độ sóng) để dự đoán các ngắt kết nối sắp xảy ra. Bộ phát hiện ngắt kết nối (Disconnection Detector - DD) có nhiệm vụ lan truyền thông tin về trạng thái ngắt kết nối giữa các tiến trình. Cuối cùng và quan trọng nhất là Bộ phát hiện phân vùng (Partition Detector - PD) [7], có khả năng tổng hợp thông tin từ các bộ phát hiện khác và topo mạng để xác định các tình huống network partitioning. Bằng cách kết hợp thông tin từ cả bốn bộ phát hiện này, hệ thống có thể xây dựng một bức tranh toàn cảnh và chi tiết về trạng thái của từng tiến trình, giúp phân biệt giữa lỗi, ngắt kết nối và phân vùng. Đây là cơ sở để xây dựng một dịch vụ quản lý nhóm thông minh và đáng tin cậy hơn.

3.1. Bộ phát hiện lỗi không tin cậy Failure Detector FD

Bộ phát hiện lỗi (FD) là một module cục bộ trong mỗi tiến trình, có nhiệm vụ cung cấp một danh sách các tiến trình bị nghi ngờ là đã lỗi (crash). Luận văn sử dụng loại bộ phát hiện "nhịp tim" (heartbeat) cho mạng có khả năng phân vùng, ký hiệu là HBP [1]. Thay vì chỉ đưa ra danh sách nghi ngờ, bộ phát hiện này cung cấp một mảng các bộ đếm nhịp tim từ các tiến trình lân cận. Bộ đếm của một tiến trình q tại p sẽ liên tục tăng miễn là q vẫn nằm trong cùng phân vùng với p. Ứng dụng sẽ dựa vào sự thay đổi của các bộ đếm này để tự quyết định tiến trình nào bị nghi ngờ lỗi. Cách tiếp cận này linh hoạt hơn so với việc sử dụng timeout cố định, đặc biệt phù hợp với môi trường có độ trễ biến đổi cao.

3.2. Bộ phát hiện kết nối CD và ngắt kết nối DD

Bộ phát hiện kết nối (Connectivity Detector - CD) [26] hoạt động ở tầng cục bộ, giám sát tài nguyên của thiết bị (pin, băng thông) để dự đoán các ngắt kết nối. Luận văn đề cập đến một thuật toán dựa trên cơ chế hysteresis (sử dụng hai ngưỡng kép) để tránh hiệu ứng "ping-pong" khi trạng thái kết nối dao động quanh một giá trị ngưỡng. Trong khi đó, bộ phát hiện ngắt kết nối (Disconnection Detector - DD) [26] làm nhiệm vụ trao đổi thông tin cục bộ từ CD giữa các tiến trình. Khi một tiến trình p nhận được thông báo ngắt kết nối từ q, nó sẽ thêm q vào danh sách các tiến trình bị ngắt kết nối. Hai bộ phát hiện này cung cấp dữ liệu đầu vào quan trọng cho việc phân biệt giữa ngắt kết nối chủ động và lỗi hệ thống.

3.3. Bộ phát hiện phân vùng mạng Partition Detector PDG

Đây là thành phần cốt lõi của giải pháp. Bộ phát hiện phân vùng (PD) [7] được thiết kế để phân biệt rõ ràng các tình huống phát hiện phân vùng mạng. Luận văn tập trung vào thuật toán PDG, một thuật toán yêu cầu kiến thức về topo toàn cục của hệ thống. PDG xây dựng và duy trì một đồ thị biểu diễn tất cả các tiến trình và liên kết. Dựa trên đồ thị này, nó có thể phát hiện khi nào hệ thống bị chia thành các thành phần liên thông riêng biệt. Tuy nhiên, đầu ra của PDG tại các tiến trình khác nhau có thể không nhất quán tạm thời. Luận văn nhấn mạnh rằng "sự không nhất quán của các bộ phát hiện phân vùng" (incohérence des détecteurs de partitions) là một vấn đề cần được giải quyết, và đề xuất sử dụng dịch vụ quản lý nhóm như một lớp đồng thuận nằm phía trên PDG.

IV. Mô hình dịch vụ quản lý nhóm mới và các thuộc tính

Dựa trên nền tảng của các bộ phát hiện, luận văn đề xuất một dịch vụ quản lý nhóm trong môi trường di động với những thuộc tính mới và mạnh mẽ hơn. Đóng góp cốt lõi là khái niệm "khung nhìn mở rộng" (vue augmentée). Thay vì một khung nhìn (view) chỉ chứa danh sách các thành viên đang hoạt động như trong các hệ thống truyền thống, khung nhìn mở rộng bao gồm bốn thành phần riêng biệt: (1) tập hợp các tiến trình đang hoạt động và có thể truy cập (view.comp), (2) tập hợp các tiến trình bị lỗi (view.fail), (3) tập hợp các tiến trình bị ngắt kết nối (view.disc), và (4) tập hợp các tiến trình bị phân vùng (view.part). Việc định nghĩa một cấu trúc dữ liệu toàn diện như vậy cho phép các ứng dụng có cái nhìn chi tiết về trạng thái hệ thống. Để đảm bảo tính nhất quán của khung nhìn mở rộng này trên tất cả các thành viên, luận văn giới thiệu một khái niệm thuật toán mới gọi là "đồng thuận phân vùng" (accord de partitions). Quá trình này không chỉ tìm kiếm sự đồng thuận về các thành viên sống, mà còn về các thành viên đã lỗi, ngắt kết nối hay bị cô lập. Các thuộc tính của dịch vụ được định nghĩa hình thức một cách chặt chẽ, dựa trên đặc tả của JGroups [5] nhưng được mở rộng để bao gồm các thành phần mới của khung nhìn. Các thuộc tính này đảm bảo tính chính xác, đầy đủ, nhất quán, có thứ tự và toàn vẹn của các khung nhìn được cài đặt trên toàn hệ thống.

4.1. Khái niệm Khung nhìn mở rộng Vue Augmentée

Khung nhìn (view) trong các hệ thống giao tiếp nhóm (group communication protocols) là một cấu trúc dữ liệu biểu diễn thành phần của nhóm tại một thời điểm nhất định. Luận văn này mở rộng khái niệm này thành "khung nhìn mở rộng", bao gồm: VC (vue du groupe) - tập hợp các tiến trình đúng và kết nối; VF (vue des défaillances) - tập hợp các tiến trình bị lỗi; VD (vue des déconnexions) - tập hợp các tiến trình được xem là đã ngắt kết nối; và VP (vue des partitions) - tập hợp các tiến trình được xem là bị phân vùng. Bốn tập hợp này phải rời nhau, đảm bảo tính toàn vẹn (AGM5: VC ∩ VF ∩ VD ∩ VP = ∅). Cấu trúc này cung cấp thông tin ngữ nghĩa phong phú hơn cho các ứng dụng phân tán.

4.2. Thuật toán Đồng thuận phân vùng Accord de Partitions

Để đạt được sự nhất quán về "khung nhìn mở rộng", các thành viên nhóm phải thực hiện một thuật toán đồng thuận. Luận văn đề xuất thuật toán quản lý nhóm mới gọi là "đồng thuận phân vùng". Mục tiêu là để tất cả các tiến trình trong cùng một phân vùng không chỉ đồng ý về danh sách thành viên đang hoạt động, mà còn đồng ý về trạng thái (lỗi, ngắt kết nối, hay phân vùng) của các tiến trình không thể truy cập. Quá trình này giải quyết vấn đề không nhất quán của các bộ phát hiện ở tầng dưới. Ví dụ, nếu tiến trình p thấy q bị phân vùng và tiến trình r thấy q bị lỗi, thuật toán đồng thuận sẽ giúp p và r đi đến một quyết định chung, ví dụ như cùng coi q bị phân vùng, dựa trên các quy tắc hội tụ được định nghĩa trước.

4.3. Các thuộc tính hình thức của dịch vụ quản lý nhóm

Dịch vụ mới được đặc tả bởi năm nhóm thuộc tính hình thức (AGM1-AGM5), mở rộng từ đặc tả của JGroups [5]. Các thuộc tính chính bao gồm: Tính chính xác của khung nhìn (AGM1 - View Accuracy), đảm bảo các tiến trình có thể truy cập cuối cùng sẽ được đưa vào nhóm. Tính đầy đủ của khung nhìn (AGM2 - View Completeness), đảm bảo các tiến trình không thể truy cập cuối cùng sẽ bị loại khỏi nhóm và được đưa vào một trong ba tập hợp còn lại. Các thuộc tính khác như Tính nhất quán (AGM3), Thứ tự (AGM4) và Toàn vẹn (AGM5) đảm bảo các khung nhìn được cài đặt một cách hợp lý và đồng bộ trên toàn hệ thống.

V. Hướng dẫn triển khai kiến trúc và thuật toán trên JGroups

Để kiểm chứng tính khả thi của mô hình đề xuất, luận văn đã xây dựng một prototype dựa trên hệ thống mã nguồn mở JGroups [17]. Việc lựa chọn JGroups là hợp lý vì đây là một hệ thống giao tiếp nhóm có khả năng xử lý phân vùng (partitionable), kiến trúc module, và được phát triển bằng Java, giúp dễ dàng sửa đổi và tích hợp. Kiến trúc của prototype được điều chỉnh từ kiến trúc gốc của JGroups. Một lớp trung gian mới, thực hiện chức năng của các bộ phát hiện (CD, DD, PDG), được chèn vào giữa hai lớp hiện có là MSL (Multi Send Layer) và VML (View Membership Layer). Lớp trung gian này chặn các thông điệp nghi ngờ (msuspect) từ lớp dưới, xử lý chúng thông qua logic của các bộ phát hiện mới, và sau đó gửi đi một thông điệp nghi ngờ mở rộng (msuspect*) lên lớp VML. Do các bộ phát hiện (trừ FD) vẫn còn ở mức lý thuyết, luận văn sử dụng một phương pháp mô phỏng mạng NS-3 (mặc dù ở đây là mô phỏng kịch bản client-server) để giả lập đầu ra của chúng. Người dùng có thể định nghĩa trước các kịch bản ngắt kết nối và phân vùng để kiểm thử thuật toán. Thuật toán quản lý nhóm trong lớp VML được sửa đổi để xử lý "khung nhìn mở rộng". Các quy tắc hội tụ (convergence rules) được thêm vào để giải quyết sự không nhất quán giữa các trạng thái và đảm bảo tất cả các thành viên đi đến một sự đồng thuận duy nhất về trạng thái của toàn bộ hệ thống.

5.1. Kiến trúc hệ thống và lựa chọn nền tảng JGroups

Luận văn đã thực hiện một so sánh giữa JGroups và Javagroup, hai hệ thống GCS (Group Communication System) mã nguồn mở phổ biến. JGroups được chọn vì có tài liệu chi tiết hơn và kiến trúc dễ sửa đổi hơn. Kiến trúc đề xuất chèn một lớp mới (tạm gọi là lớp PDG) vào giữa MSL và VML của JGroups. Lớp PDG này nhận thông điệp msuspect từ lớp MSL (vốn dựa trên bộ phát hiện lỗi HBDP), kết hợp nó với thông tin từ bộ mô phỏng ngắt kết nối và phân vùng, sau đó tạo ra một thông điệp msuspect* mới chứa ba tập hợp (lỗi, ngắt kết nối, phân vùng) để gửi lên lớp VML. Kiến trúc này giữ nguyên tính module của JGroups và cho phép thay thế bộ mô phỏng bằng một cài đặt thực tế trong tương lai.

5.2. Sửa đổi thuật toán quản lý nhóm trong lớp VML

Thuật toán quản lý nhóm cốt lõi của JGroups trong lớp VML, vốn dựa trên một điều phối viên (coordinator), đã được sửa đổi. Các cấu trúc dữ liệu như view, estimate được mở rộng để chứa bốn thành phần của "khung nhìn mở rộng". Phần quan trọng nhất của sự sửa đổi nằm trong pha trao đổi ước tính (EstimateExchangePhase). Khi các tiến trình trao đổi ước tính của mình về khung nhìn mới, các quy tắc hội tụ được áp dụng. Ví dụ, quy tắc R3 nêu rằng: "Nếu một tiến trình p thấy tiến trình q vừa nằm trong tập hợp lỗi, vừa nằm trong tập hợp ngắt kết nối, p sẽ loại q khỏi tập hợp lỗi". Các quy tắc này đảm bảo rằng các trạng thái loại trừ lẫn nhau (lỗi, ngắt kết nối, phân vùng) sẽ được giải quyết một cách nhất quán trước khi cài đặt khung nhìn mới.

5.3. Tình trạng phát triển prototype và kiểm thử

Tại thời điểm hoàn thành luận văn, prototype đã hoàn thành việc xây dựng kiến trúc và chèn lớp trung gian PDG. Lớp này đã có thể chặn và biến đổi các thông điệp msuspect thành công. Việc sửa đổi thuật toán trong lớp VML đang trong quá trình hoàn thiện. Việc kiểm thử được thực hiện bằng cách chạy nhiều tiến trình helloserver trong JGroups. Khi một kịch bản được kích hoạt thông qua bộ mô phỏng (ví dụ: một tiến trình bị ngắt kết nối), các tiến trình còn lại sẽ nhận được thông tin và cài đặt một khung nhìn mới, phản ánh đúng sự thay đổi đó. Kết quả ban đầu cho thấy cách tiếp cận này là khả thi và có tiềm năng lớn.

VI. Đánh giá đóng góp và tương lai của luận văn thạc sĩ

Luận văn Gestion de groupe et détection de partition en environnement mobile đã có những đóng góp quan trọng và thiết thực cho lĩnh vực hệ thống phân tán di động. Đóng góp chính và nổi bật nhất là việc hiện thực hóa một dịch vụ quản lý nhóm mới với các thuộc tính nâng cao, dựa trên việc tích hợp các bộ phát hiện chuyên biệt. Khái niệm "khung nhìn mở rộng" và thuật toán "đồng thuận phân vùng" là những ý tưởng mới, giải quyết hiệu quả sự mơ hồ giữa các trạng thái lỗi, ngắt kết nối và phân vùng vốn là một bài toán khó trong môi trường di động. Việc xây dựng một prototype trên nền tảng JGroups đã chứng minh tính khả thi của phương pháp đề xuất. Đây là một tài liệu có giá trị, có thể tìm thấy trong thư viện số VNU, và là nguồn tham khảo hữu ích cho các đề tài thạc sĩ về mạng máy tính. Tuy nhiên, nghiên cứu vẫn còn một số hạn chế. Luận văn giả định topo mạng không thay đổi ngầm, và các tiến trình khi kết nối lại sẽ kết nối với các lân cận cũ. Đây là một giới hạn cần được gỡ bỏ trong các công trình tương lai để hỗ trợ đầy đủ tính di động và kết nối linh hoạt hơn. Hướng phát triển trong tương lai bao gồm việc hoàn thiện prototype, thực hiện các cài đặt thực tế cho các bộ phát hiện thay vì mô phỏng, và tiến hành các đo đạc hiệu năng chi tiết để đánh giá giải pháp trong các kịch bản phức tạp hơn. Hơn nữa, việc mở rộng mô hình để xử lý các kịch bản nút di động hoàn toàn (full mobility) sẽ là một hướng nghiên cứu đầy hứa hẹn.

6.1. Tổng kết những đóng góp chính của công trình nghiên cứu

Đóng góp quan trọng nhất của luận văn thạc sĩ công nghệ thông tin này là việc đề xuất và đặc tả hình thức một dịch vụ quản lý nhóm mới, có khả năng phân biệt và đồng thuận trên nhiều trạng thái hệ thống (hoạt động, lỗi, ngắt kết nối, phân vùng). Việc giới thiệu khái niệm "khung nhìn mở rộng" và các quy tắc hội tụ trong thuật toán đồng thuận đã giải quyết được vấn đề không nhất quán của các bộ phát hiện ở tầng dưới. Việc hiện thực hóa ý tưởng này trên một nền tảng thực tế như JGroups cho thấy tính ứng dụng cao của nghiên cứu, vượt ra ngoài phạm vi lý thuyết thuần túy.

6.2. Hạn chế của luận văn và các giả định được sử dụng

Nghiên cứu vẫn tồn tại một số hạn chế. Giả định rằng các tiến trình và liên kết bị lỗi sẽ không khôi phục (fail-stop model) và topo mạng không thay đổi một cách ngầm định (tức là một tiến trình khi kết nối lại sẽ giữ nguyên các lân cận) đã đơn giản hóa bài toán. Trong thực tế của Mobile Ad-hoc Networks (MANETs), các nút di chuyển liên tục, làm thay đổi topo mạng một cách khó lường. Ngoài ra, việc sử dụng mô phỏng cho các bộ phát hiện thay vì cài đặt thực tế cũng là một điểm cần cải thiện. Đây là những giới hạn cần được giải quyết trong các nghiên cứu tiếp theo để giải pháp có thể áp dụng rộng rãi hơn.

6.3. Hướng phát triển và các nghiên cứu tiềm năng trong tương lai

Tương lai của đề tài này rất rộng mở. Trước hết, cần hoàn thiện việc cài đặt và kiểm thử prototype trên JGroups một cách toàn diện. Bước tiếp theo là xây dựng các phiên bản cài đặt thực tế của bộ phát hiện kết nối (CD), ngắt kết nối (DD) và phân vùng (PDG) để thay thế cho bộ mô phỏng. Việc đo lường hiệu năng (performance evaluation) của hệ thống trong các kịch bản thực tế sẽ cung cấp những đánh giá khách quan về độ trễ, chi phí giao tiếp và khả năng mở rộng. Một hướng nghiên cứu dài hạn và thách thức hơn là gỡ bỏ giả định về topo mạng tĩnh, phát triển một giải pháp quản lý nhóm có thể xử lý được sự di chuyển hoàn toàn tự do của các nút trong mạng.

Trích đoạn nội dung tài liệu

Institut de la Fran ophonie pour l'Informatique Institut National des Télé ommuni ations MÉMOIRE DE FIN D'ÉTUDES MASTER D'INFORMATIQUE Gestion de groupe et déte tion de partition en environnement mobile NGUYEN Tuan Dung Responsable de stage : Denis CONAN Ce stage a été réalisé au sein du laboratoire SAMOVAR, équipe MARGE du département Informatique de l'Institut National des Télé ommuni ations GET/INT CNRS UMR SAMOVAR Évry, 15 août 2005 LUAN VAN CHAT LUONG download : add [e-mail] Remer iements Je voudrais tout d'abord remer ier le Professeur Guy Bernard pour m'avoir a ueilli dans son équipe de re her he de l'Institut National des Télé ommuni ations (INT). Je tiens à remer ier tout parti ulièrement Denis Conan pour avoir proposé e sujet de stage et m'avoir en adré pendant es inq mois. Je le remer ie de son onta t haleureux, ses onseils et en ouragements, son soutien permanent et la liberté de re her he qu'il a bien voulu me laisser. Qu'il trouve i i l'expression de ma profonde re onnaissan e.

Mes plus sin ères remer iements vont également à tous les professeurs et les personnels de l'Institut de la Fran ophonie pour l'Informatique (IFI) pour m'avoir donné des ours de très bonne qualité et pour leur soutien tout au long de mes études à l'IFI. Un grand mer i aux thésards et aux autres stagiaires dans l'équipe à l'INT pour une am- bian e de travail parti ulièrement favorable. Je remer ie haleureusement mes amarades de la promotion IX pour leur amitié sans faille et je leur souhaite bonne han e pour la soutenan e. Mer i enn à mes parents, mon frère et mes amis pour leur soutien et leur en ouragement à tout l'instant.

i LUAN VAN CHAT LUONG download : add [e-mail] Résumé L'évolution des réseaux sans l et des équipements a abouti à un nouveau paradigme onnu sous le nom  informatique mobile . Il ore aux utilisateurs la apa ité de pouvoir se dépla- er tout en restant onne té aux appli ations répartis et d'être indépendant de la lo alisation géographique. Dans un environnement mobile, les terminaux mobiles sont sujets à des dé on- nexions. Ce i requiert des mé anismes spé iques de gestion de dé onnexions et de toléran e aux fautes.

La gestion de groupe est un servi e prin ipal des systèmes de ommuni ation de groupe, une brique importante pour onstruire des appli ations réparties. Les travaux dans la littérature ont montré omment et dans quelle mesure des intergi iels existant peuvent être enri his par quatre déte teurs : défaillan e, onne tivité, dé onnexions, plus un quatrième, partitions. En se basant sur es déte teurs, nous proposons un nouveau servi e de gestion de groupe ayant de nouvelles propriétés intéressantes. Ave e servi e, les pro essus se mettent d'a ord non seulement sur l'ensemble des pro essus orre ts onne tés du groupe mais aussi sur les ensembles des pro essus défaillants, dé onne tés ou partitionnés.

Un prototype est onstruit pour tester notre appro he. Mots- lefs : mobilité, toléran e aux fautes, algorithmique répartie, gestion de groupe et intergi iels. ii LUAN VAN CHAT LUONG download : add [e-mail] Abstra t The advan es in wireless networking and portable applian es have engendered a new pa- radigm of omputing, alled  mobile omputing , in whi h users have a ess to data and information servi es regardless of their physi al lo ation or movement behavior. In mobile en- vironment, the mobile terminals ould frequently be dis onne ted.

This hara teristi requires the spe i and adapted me hanisms of dis onne tion management and fault toleran e. Group membership is a fundamental servi e of group ommuni ation systems, whi h are often used like the important bri ks to build distributed appli ations. Re ent resear h works have showed that the existed middleware an be augmented with four dete tors : failure, onne tivity, dis onne tion and partition. Based on these dete tors, we propose a new group membership servi e with new interesting properties.

With this servi e, the pro esses rea h an agreement not only about the set of orre t onne ted pro esses but also about the set of failure, dis onne ted and partitioned pro esses. A prototype is developped to test our approa h. Keywords : mobility, fault toleran e, distributed algorithm, group membership, middle- ware. iii LUAN VAN CHAT LUONG download : add [e-mail] Table des matières Résumé ii Abstra t iii 1 Introdu tion 1 1.2 Motivation et obje tifs du stage .3 Environnement de travail .5 Plan du do ument.

5 2 Déte teurs en environnement mobile 6 2.2 Déte teur de défaillan es non able .3 Déte teur de onne tivité .4 Déte teur de dé onnexions .5 Déte teur de partitions. 12 3 Système de ommuni ation de groupe 13 3.4 Études de deux implantations existantes. 16 iv LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3 Choix de l'implantation. 18 4 Spé i ation d'un nouveau servi e de gestion de groupe 19 4.1 Modèle de système réparti .3 S héma de défaillan e .4 S héma de dé onnexion .5 S héma de partitionnement .6 Propriétés du servi e de gestion de groupe.

26 5 Ar hite ture, algorithmes et prototype 27 5.1 Ar hite ture .4 État d'avan ement du développement. 40 6 Con lusions et perspe tives 42 Bibliographie 46 A Preuves 47 v LUAN VAN CHAT LUONG download : add [e-mail] Table des gures 1.1 Partitionnement dans le réseau .2 Stratégies de l'adaptation .1 Hystérésis du gestionnaire de onne tivité .2 Situations de partitionnement .3 Déte tion de partitions pour la gestion de groupe .1 Ar hite ture d'un système de ommuni ation de groupe .2 Ar hite ture de Javagroup .3 Ar hite ture de Jgroup .1 Ar hite ture du système proposé .2 Algorithme de gestion de groupe .3 Diagramme des lasses de la ou he PDG. 40 vi LUAN VAN CHAT LUONG download : add [e-mail] Liste des tableaux 1.1 Quatre formes de toléran e aux fautes .1 Déte teurs de défaillan es .2 In ohéren e des déte teurs de partitions .1 Comparaison entre système de ommuni ation de groupe et autres proto oles. 13 vii LUAN VAN CHAT LUONG download : add [e-mail] Liste des algorithmes 1 Algorithme prin ipal d'un pro essus p.

33 2 AgreementP hase et SynchronizationP hase. 37 4 Pro édures et fon tions supplémentaires. 39 viii LUAN VAN CHAT LUONG download : add [e-mail] Chapitre 1 Introdu tion 1.1 Problématique L'apparition des ordinateurs portables, des assistants personnels numériques (PDA) puis- sants et des réseaux lo aux sans l (WLAN) dans les années 90s posent de nouveaux problèmes de onstru tion des systèmes répartis ave les lients mobiles [25℄. Ce i a engendré un nou- veau paradigme appelé  informatique mobile  qui sus ite des re her hes non seulement pour résoudre les problèmes existants dans les systèmes répartis (p.

la toléran e aux fautes) mais aussi pour traiter les problèmes spé iques en environnement mobile (p. la gestion de dé onnexions). La toléran e aux fautes est un sujet de re her he important pour les systèmes répartis. Ces systèmes disposent de deux propriétés importantes : la sûreté et la viva ité.

La première assure que les omportements mauvais n'apparaissent jamais dans le système et la se onde assure que les bons omportements doivent nalement apparaître lors de l'exé ution du système. Dans les systèmes réels, la prioritaire entre es deux propriétés dépend du type de l'appli ation. Les ombinaisons de es deux propriétés nous donnent les quatre formes de toléran e aux fautes présentées dans le tableau 1. viva e non viva e sûre masquant fail safe non sûre non masquant rien Tab.1  Quatre formes de toléran e aux fautes La redondan e est indispensable pour la toléran e aux fautes.

Chaque système réparti doit don être redondant dans l'espa e (p. ex serveurs primaires vs. se ondaires) ou dans le temps 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 Problématique 2 d'exé ution (p. ex le al ul d'une variable plusieurs fois).

Pour assurer la sûreté, il faut déte ter les défaillan es dans le système grâ e aux mé anismes de déte tion. Par ontre, la viva ité est plus di ile à garantir ar nous devons orriger les erreurs déte tés (la orre tion) [15℄. Dans les systèmes purement asyn hrones, 'est-à-dire dans lesquels il n'existe au une borne sur la vitesse de al ul de haque pro essus ou sur le temps de transmission des messages, [14℄ a montré qu'il est impossible de résoudre le problème du onsensus entre pro essus répartis dès qu'un seul d'entre eux est défaillant (p. par un arrêt fran ).

La raison est que nous ne pouvons pas dire si un pro essus est défaillant ou simplement très lent. Les systèmes de ommuni ation de groupe (GCSs pour Group Communi ation Systems en anglais) sont onsidérés omme des briques fondamentales pour onstruire les appli ations réparties. Ils fournissent aux appli ations la apa ité de ommuni ation de type multi ast able. Mais le prin ipe d'un GCS s'appuie sur un mé anisme de onsensus et don subit aussi un résultat d'impossibilité dans les systèmes asyn hrones [9℄.

Pourtant, le problème du onsensus peut être résolu dans un modèle partiellement syn hrone où nous ne onnaissons pas les délais de al ul ou de transmission mais dans lequel il existe un instant et une borne tels que, après et instant, les délais sont inférieurs à ette borne. Un exemple du onsensus dans e modèle est onstruit en utilisant le on ept de déte teur de défaillan es non able [10℄. D'autres appro hes utilisent les algorithmes probabilistes. Grâ e à e modèle, nous pouvons ensuite dénombrer plusieurs résultats de re her he sur les GCSs.

Mais, il est montré dans [3℄ que la plupart d'entre eux possèdent des faiblesses dans leur spé i ation : es systèmes peuvent autoriser des exé utions indésirables ou leur spé i ation peuvent être fa ilement satisfaites par des solutions triviales sans utilité (p. par les vues apri ieuses1 ). La grande di ulté est alors de trouver une spé i ation à la fois assez forte pour éviter tous es problèmes et assez faible pour qu'il soit faisable de trouver une solution. Nous présentons maintenant les ara téristiques de l'environnement mobile et la problé- matique de notre re her he.

Tout d'abord, l'informatique mobile est souvent ara térisée par quatre ontraintes [24℄ :  les entités mobiles ont des ressour es très limitées par rapport aux entités xes ;  la mobilité ontient elle-même plus de risques (p. perte ou vol) ; 1 La vue du pro essus p est le singleton {p}. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 Problématique 3  la onne tivité en environnement mobile est hautement variable en performan e et en abilité ;  les entités mobiles disposent d'une sour e limitée d'énergie. Dans les environnements mobiles, les terminaux mobiles sont sujets à des dé onnexions vo- lontaires ou involontaires.

Les premières, dé idées par l'utilisateur depuis son terminal mobile, sont justiées par les béné es attendus sur le oût nan ier des ommuni ations, l'énergie, la disponibilité du servi e appli atif, et la minimisation des désagréments induits par des dé- onnexions inopinées. Les se ondes sont le résultat de oupures intempestives des onnexions physiques du réseau, par exemple, lors du passage de l'utilisateur dans une zone d'ombre radio. Cette ara téristique donne naissan e à de nouveaux types de déte teurs omme les déte teurs de onne tivité et de dé onnexions [26℄.