Giải Pháp Cung Cấp Tài Nguyên Truyền Thông Phân Tán

- Hà Nội, ngày GIẢI PHÁP CUNG CẤP TÀI NGUYÊN TRUYỀN THÔNG PHÂN TÁN Đặng Hùng Vĩ1, Lê Văn Sơn1 1 Trường Đại học Sư phạm – Đại học Đà Nẵng [email protected], [email protected] TÓM TẮT - Hiện nay, hệ phân tán đã và đang được nghiên cứu, triển khai trong các hệ thống ảo hóa.
- Hợp lực trong hệ phân tán chủ yếu sử dụng cơ chế truyền thông điệp (message passing) trong mạng.
- Nhược điểm của vấn đề hợp lực là các thông điệp được tiếp nhận không theo trật tự bởi độ trễ truyền thông gây ảnh hưởng đến xử lý trong hệ.
- Bên cạnh đó, thông điệp truyền trong môi trường truyền thông có thể bị mất, phân mảnh và trùng lặp.
- Do đó, cần phải xây dựng bộ cung cấp tài nguyên truyền thông để đảm bảo trật tự và tối ưu truyền thông điệp.
- Vì vậy, chúng tôi đề xuất cải tiến các thuật toán cung cấp tài nguyên truyền thông phân tán trong nghiên cứu của mình áp dụng cho hệ phân tán.
- Từ khóa - Hệ phân tán, lưu lượng cực đại, cung cấp tài nguyên truyền thông, truyền thông điệp.
- ĐẶT VẤN ĐỀ Hệ phân tán và các ứng dụng của hệ được nghiên cứu và triển khai trên với quy mô lớn, đáp ứng số lượng lớn người dùng truy cập.
- Bốn thực thể của hệ phân tán thể hiện Hình 1, hệ thống này bao gồm các máy chủ kết nối qua hệ thống truyền thông dưới sự điều hành thống nhất của một hệ điều hành gọi là hệ điều hành phân tán [1].
- Bốn thực thể của hệ tin học phân tán Các hoạt động của hệ thống phân tán bao gồm tập các tiến trình cung cấp tài nguyên dùng chung được trao đổi bởi môi trường truyền thông.
- Độ trễ trong mạng truyền thông là hữu hạn nhưng không thể đoán trước và các bộ vi xử lý không chia sẻ một bộ nhớ chung toàn cục.
- giao tiếp duy nhất trong hệ bằng cách truyền thông điệp qua mạng [2].
- Do đó, môi trường truyền thông có thể cung cấp các thông điệp không theo trật tự.
- thông điệp có thể bị mất, bị phân mảnh, hoặc trùng lặp do độ trễ, hết thời gian chờ và yêu cầu phát lại.
- Bên cạnh đó, các tiến trình có thể thất bại và các liên kết truyền thông có thể mất kết nối.
- Hệ phân tán không có đồng hồ vật lý toàn cục để các tiến trình có thể truy cập tức thời, do đó hệ phải sử dụng đồng hồ riêng là đồng hồ lô gic để gắn giá trị và đồng bộ tiến trình trên các máy chủ hay còn gọi là nhãn thời gian lô gic.
- Tuy nhiên, các nhãn đồng hồ này phải được cập nhật và nhất quán trên tất cả các trạm, nếu không việc xử lý thông điệp sẽ bị sai và hoạt động của hệ bị sai trật tự theo lý thuyết trật tự như Hình 2 [1].
- Qua đó cho thấy, thực thể hệ thống truyền thông theo Hình 1 đóng vai trò quan trọng trong quá trình thiết kế các ứng dụng và điều khiển hệ phân tán.
- Các đặc tính của hệ phân tán thể hiện như sau.
- Tính gắn bó là một trong những đặc điểm quan trọng của hệ, một tài nguyên dùng chung chỉ cung cấp duy nhất và trạng thái này phải giống nhau trên tất cả các máy chủ.
- 268 GIẢI PHÁP CUNG CẤP TÀI NGUYÊN TRUYỀN THÔNG PHÂN TÁN - Tính chịu lỗi là khi một hay nhiều máy chủ bị sự cố rời khỏi và vào lại hệ sau khi đã khôi phục thì yêu cầu tính gắn bó phải đảm bảo cho toàn hệ.
- Hệ dừng khi tất cả các máy chủ trong hệ dừng hoạt động.
- Nhãn thời gian thông điệp không theo trật tự Hệ phân tán phụ thuộc vào môi trường truyền thông có độ trễ là một trong những vấn đề quan tâm đó là trật tự thông điệp tiếp nhận và xử lý trên các máy chủ.
- Các trật tự này phải đảm bảo nhất quán giữa các máy chủ sao cho quá trình thực thi thông điệp dẫn đến gắn bó trong toàn hệ.
- Đối với hệ phân tán phức tạp kết nối ngang hàng chia sẻ tài nguyên dùng chung, khi một tài nguyên được cung cấp cho người dùng thì tất cả máy chủ khác đều nhận biết và cung cấp tài nguyên duy nhất.
- Dựa trên nguyên lý này, hệ phân tán có thể cố định số lượng hoặc tăng lên tùy thuộc vào nhu cầu truy cập thực tế từ người dùng.
- Theo nguyên lý thiết kế các chiến lược đồng bộ hóa các tiến trình trong [1] đưa ra các chiến lược cung cấp tài nguyên trong hệ phân tán nhằm đảm bảo tính gắn bó trên cơ sở nhờ dấu.
- Để thực thi giải pháp vừa nêu trong hệ, các máy chủ liên lạc với nhau theo nhóm để thực hiện truyền thông thông điệp, đây chính là phương thức truyền multicast [3-6].
- Tuy nhiên, hai thách thức cơ bản được đưa ra trong nghiên cứu giải pháp cung cấp tài nguyên truyền thông phân tán là trùng lặp thông tin tại tập đích và trùng lặp đường dẫn định tuyến [7, 8].
- Như vậy, cần thiết phải xây dựng bộ cung cấp tài nguyên truyền thông để giải quyết hai hạn chế vừa nêu.
- Bộ cung cấp tài nguyên truyền thông phân tán tập trung vào các xử lý cơ bản là cung cấp giá trị đồng hồ lô gic, điều khiển lưu lượng và định tuyến đường dẫn truyền thông điệp.
- Bộ cung cấp này cho phép các thuật toán được xây dựng và phát triển tham gia vào quá trình điều khiển nhằm tối ưu truyền thông điệp.
- Truyền thông điệp trong hệ phân tán thuộc bài toán NP-khó [8], do đó các giải pháp tối ưu chỉ mang giá trị đúng cho bài toán đang xét.
- Truyền thông trong hệ phân tán có thể được mô hình hóa như một đồ thị có hướng, trong đó đỉnh đại diện cho máy chủ xử lý các tiến trình vào/ra và các cạnh đại diện cho các kênh truyền thông.
- Các hướng nghiên cứu của giải pháp tối ưu truyền thông phân tán tập trung vào bài toán tối ưu lưu lượng mạng từ nguồn đến đích.
- Hướng nghiên cứu của chúng tôi là tìm giải pháp đảm bảo lưu lượng cực đại trong cung cấp tài nguyên truyền thông phân tán.
- bên cạnh đó các thông điệp được gắn dấu nhờ vào bộ cung cấp giá trị đồng hồ lô gic.
- Bộ cung cấp tài nguyên truyền thông phân tán phát triển dựa trên các thuật toán phân tán Lamport, Ford Fulkerson để cung cấp giá trị đồng hồ lô gic, tính toán luồng cực đại khi truyền thông điệp.
- GIẢI PHÁP TỐI ƯU TRUYỀN THÔNG NHÓM TRONG HỆ PHÂN TÁN Một hệ thống truyền thông phân tán được mô tả theo Hình 3 là tập các máy chủ (Host) kết nối qua môi trường truyền thông và định tuyến thông qua các router.
- Mỗi máy chủ là một hệ thống độc lập có bộ nhớ và vi xử lý riêng, sự hợp lực của các máy chủ thông qua truyền thông điệp để thực hiện nhiệm vụ chung.
- Các thông điệp này cũng có thể Đặng Hùng Vĩ, Lê Văn Sơn 269 được xét như là các tiến trình di chuyển trong hệ thống mạng.
- Việc thực thi các tiến trình phụ thuộc vào bộ cung cấp tài nguyên truyền thông để định tuyến từ nguồn đến đích.
- Mạng truyền thông phân tán Hệ thống mạng ở Hình 3 có thể mô tả dưới dạng đồ thị G=(U,V) theo Hình 4, trong đó U là tập các Si và V là tập giữa các Sij trong hệ, Sij là liên kết giữa hai nút Si và Sj liền kề trong hệ thống.
- Ký hiệu P là tập các phiên chuyển thông điệp trong hệ, đối với mỗi phiên p∈P ta có đường dẫn từ S0∈U đến S|U|-1∈U-{S0} tương ứng là nguồn và đích.
- Hệ thống mạng biểu diễn dưới dạng đồ thị Để tối ưu giải pháp truyền thông trong hệ phân tán, truyền thông nhóm được đề xuất để truyền thông điệp từ nguồn đến đích [9-11].
- Truyền thông nhóm là một tập hợp các các tiến trình chia sẻ ngữ cảnh và hợp lực trên một nhiệm vụ chung trong miền ứng dụng phân tán.
- Các thuật toán cụ thể cần phải được thiết kế để cho phép truyền thông và quản lý nhóm hiệu quả, bên cạnh đó các tiến trình có thể tham gia và rời khỏi nhóm tự động.
- Khi nhiều thông điệp phát đồng thời, những bộ nhận trên các máy chủ có thể nhận được các thông điệp trong trật tự khác nhau.
- do đó, có thể phá vỡ hoạt động của chương trình phân tán nếu máy chủ xử lý các thông điệp không theo trật tự này.
- Vì vậy, vai trò bộ cung cấp trật tự cần phải được xây dựng và thực hiện để cung cấp trật tự cho thông điệp đi và đến trong hệ.
- Truyền thông nhóm áp dụng cho việc xây dựng chiến lược cung cấp tài nguyên trong hệ thống phân tán với các đặc điểm sau.
- Yêu cầu máy chủ là truyền thông điệp multicast cho tất cả các thành viên của nhóm, các thông điệp này thực thi cùng một thuật toán.
- Dịch vụ chuyển kết nối: thông điệp multicast có thể được sử dụng bởi các máy chủ và máy khách để xác định vị trí dịch vụ trong đăng ký tài nguyên dùng chung.
- Hiệu năng cao thông qua nhân bản dữ liệu: Dữ liệu được nhân bản để tăng hiệu suất của việc cung cấp tài nguyên.
- 270 GIẢI PHÁP CUNG CẤP TÀI NGUYÊN TRUYỀN THÔNG PHÂN TÁN - Nhân bản các thông báo sự kiện: truyền multicast cho một nhóm có thể được sử dụng để thông báo cho tiến trình khi diễn ra các hoạt động trên máy chủ.
- Điều này quan trọng đối với việc ứng dụng thuật toán Lamport để cung cấp giá trị đồng hồ logic, thiết lập trật tự tổng quát và thực hiện xử lý tuần tự trên các máy chủ.
- Truyền thông nhóm thực hiện truyền thông điệp dựa vào đường dẫn định tuyến đã biết để truyền từ nguồn đến đích.
- Truyền thông nhóm xét hai khía cạnh đó là lưu lượng và các kênh truyền thông.
- Lưu lượng thể hiện giá trị được cấp phát để truyền thông điệp, trong khi đó các kênh truyền thông được xem xét như là tài nguyên của bộ cung cấp tài nguyên truyền thông để thông điệp đi qua.
- Đối với các máy chủ có nhiều kênh truyền thông thì hiệu quả truyền tốt hơn, tuy nhiên nó còn phải phụ thuộc vào lưu lượng được cấp phát.
- Bộ cung cấp tài nguyên truyền thông phân tán trên cơ sở truyền thông nhóm theo Hình 5, tại mỗi máy chủ có hai thành phần đó là hàng đợi và bộ cung cấp tài nguyên truyền thông.
- Hàng đợi trong các máy chủ nhằm cho phép tiếp nhận các thông điệp đến thể hiện như các tiến trình yêu cầu tài nguyên dùng chung.
- Các tiến trình này được xử lý và sắp xếp theo giá trị đồng hồ, do đó nó có thể giải quyết vấn đề tương tranh tài nguyên.
- Bộ cung cấp tài nguyên truyền thông trên mỗi máy chủ trong hệ đảm nhiệm vai trò vừa yêu cầu, vừa đáp ứng yêu cầu từ các server khác trong hệ.
- Mục đích của truyền thông là đảm bảo lưu lượng cực đại khi qua các nút để thông tin đến đích chính xác và nhanh chóng.
- Cung cấp tài nguyên phân tán cho cặp yêu cầu/đáp ứng A.
- Các thuật toán truyền thông nhóm 1.
- Thuật toán Lamport Thuật toán Lamport nhằm cho phép ghi lại các sự kiện của hệ phân tán .
- Trạm e phát thông điệp ghi dấu E của mình dựa trên giá trị hiện hành của He.
- Thuật toán Ford Fulkerson Thuật toán Ford Fulkerson là thuật toán cho phép tính toán luồng cực đại trong một mạng truyền thông [13].
- Kết thúc thuật toán ta đạt được một đường dẫn với lưu lượng có giá trị lớn nhất.
- Thuật toán Ford-Fulkerson có hai bước chính.
- Giải pháp cải tiến thuật toán truyền thông nhóm 1.
- Trật tự toàn phần với đồng hồ lô gic Lamport Dựa vào truyền thông nhóm, thuật toán Lamport được cải tiến lại theo cách giải quyết sau: Mỗi trạm S đều có trang bị công tơ với các giá trị nguyên gọi là Hs, đồng hồ lô gic tăng lên khi có sự kiện skj diễn ra trên một trạm bất kỳ.
- Một trạm i khi phát sinh sự kiện gửi thông điệp yêu cầu được cung cấp giá trị đồng hồ đến tất cả các trạm còn lại theo thủ tục.
- Get _ Lamport Si , H Si , sk j ) tất cả các trạm sau khi nhận được thông điệp trên kiểm tra, so sánh với giá trị hiện tại H Sk của trạm mình ( H Si ≤ H Sk ) và phản hồi thông điệp chấp nhận giá trị với thủ tục.
- Accept _ Lamport Sk , H Sk , sk j , true ) Sau khi tiếp nhận thông điệp phản hồi từ các trạm còn lại, nếu tham số thứ 4 nhận được đều có giá trị true thì.
- tiến hành lấy max H Sk , cập nhật lại giá trị đồng hồ theo max H Sk.
- và tăng giá trị lên 1 để gắn cho sự kiện.
- Sau khi gắn giá trị cho sự kiện và cập nhật lại đồng hồ theo giá trị mới, một thông điệp gửi đồng thời đến các trạm theo thủ tục để xác nhận giá trị đồng hồ đã được gắn cho sự kiện ski.
- Kết quả của thuật toán là tất cả các trạm cùng thực hiện cập nhật giá trị đồng hồ và tuân thủ theo trật tự toàn phần như Hình 6.
- Kết quả này là điều kiện hết sức quan trọng đối với các giải pháp tiếp theo để phát triển ứng dụng phân tán.
- 272 GIẢI PHÁP CUNG CẤP TÀI NGUYÊN TRUYỀN THÔNG PHÂN TÁN Hình 6.
- Trật tự tổng quát các thông điệp theo thuật toán Lamport Sau khi đã gắn nhãn cho thông điệp, bộ cung cấp tài nguyên truyền thông sẽ tính toán luồng cực đại trong hệ thống mạng và tiến hành chuyển thông điệp đến tập đích.
- Thuật toán tìm luồng cực đại Cải tiến thuật toán Ford Fulkerson tập trung vào giải pháp truyền thông nhóm trong thuật toán theo Hình 7, thể hiện xử lý này trong bước 2.
- Trong giải pháp xử lý đồ thị tuyến tính cho các ứng dụng phân tán sử dụng phương thức truyền multicast thì đường dẫn từ nguồn đến đích có thể tồn tại nhiều đường đi khác nhau và phụ thuộc vào k-nút nết nối.
- Tham số đầu vào để tạo tạo tô pô 274 GIẢI PHÁP CUNG CẤP TÀI NGUYÊN TRUYỀN THÔNG PHÂN TÁN Trong Hình 8, N là số nút trong mạng được chọn từ 100 đến 500 nút, băng thông cung cấp từ 10M đến 1024M và được lựa chọn trải đều trên các cạnh.
- Kết quả mô phỏng với 100 nút kết nối và 6 nút lô gich hoạt động bên trong hệ Tập tin brite được thi trên công cụ Distributed System Simulator (DSSim), chương trình khởi tạo đồ thị chứa các nút, tính toán lưu lượng truyền dựa vào số nút lô gic để truyền thông điệp được chọn ngẫu nhiên trong tổng số nút mạng được tạo.
- Các hành động diễn ra trong sự kiện của hệ TT Tên sự kiện Thuyết minh 1 MSG_NODE_SEND Nút gửi thông điệp 2 MSG_NODE_RECV Nút nhận thông điệp 3 MSG_ROUTE_SEND Định tuyến gửi thông điệp 4 MSG_ROUTE_RECV Định tuyến nhận thông điệp 5 ROUTE_BEGIN Định tuyến bắt đầu 6 ROUTE_END Định tuyến kết thúc 7 NODE_BEGIN Nút bắt đầu 8 NODE_END Nút kết thúc 9 MONITORING_LLINK_CREATION Giám sát tạo liên kết 10 MONITORING_LLINK_REMOVAL Giám sát xóa liên kết 11 MONITORING_PROP_CHANGED Giám sát thay đổi Dựa vào các hành động trong Bảng 1, hệ phân tán có thể điều khiển và giám sát toàn bộ hoạt động thông qua thông điệp.
- Cấu trúc một thông điệp được mô tả ở Hình 11.
- Cấu trúc thông điệp Giá trị đồng hồ là 0 thường là trạng thái khởi tạo ban đầu và 1 là bắt đầu các hoạt động trong hệ.
- Giá trị luồng cực đại từ nút nguồn 0 đến các nút đích trong tập lát cắt cực tiểu .
- Thuật toán Ford Fulkerson xử lý song song để tính giá trị luồng cực đại, tuy nhiên định tuyến của thông điệp chưa phải là đường đi ngắn nhất.
- Chương trình thể hiện giá trị tính toán luồng cực đại từ nguồn 0 đến đích 71 qua Hình 13.
- Tính toán luồng cực đại từ nguồn 0 đến đích 71 276 GIẢI PHÁP CUNG CẤP TÀI NGUYÊN TRUYỀN THÔNG PHÂN TÁN III.
- KẾT LUẬN Giải pháp cung cấp tài nguyên phân tán là một trong những giải pháp nhằm tối ưu truyền thông điệp.
- Trong nghiên cứu này, chúng tôi đưa ra hai giải pháp để cải tiến xử lý truyền thông điệp đó là thuật toán Lamport nhằm cho phép ghi nhận các sự kiện diễn ra trong hệ phân tán và thuật toán Ford Fulkerson tìm luồng cực đại truyền thông điệp từ nguồn đến đích.
- Hướng chính của giải pháp là dựa vào truyền thông nhóm để cải tiến hai thuật toán trên đảm bảo đạt được trật tự toàn phần khi truyền thông điệp trong hệ và các thông điệp được chia thành nhiều hướng khác nhau để đến đích một cách nhanh chóng, chính xác dựa vào tính toán lưu lượng cực đại trong quá trình truyền.
- Tuy nhiên, trong giải pháp cung cấp tài nguyên phân tán, trong quá trình truyền các thông điệp có thể bị trùng lặp khi phân chia tại các nút.
- Như vậy, thông điệp nhận tại tập đích có thể bị dư thừa dẫn đến lãng phí tài nguyên truyền thông