Remote proceduce call

và các ứng dụng chạy trên các máy riêng biệt. Trong trường hợp đó, ứng dụng được cung cấp giao diện tương tự như khi người quản lý hàng đợi đc đặt trên cùng một máy. Tuy nhiên, giao diện được thực hiện như là một proxy , liên lạc với người quản lý hàng đợi bằng cách sử dụng RPC truyền thống dựa trên giao tiếp, đồng bộ. Bằng cách này,MQ về cơ bản vẫn giữ được những mô hình hàng đợi địa phương để chỉ một ứng dụng có thể được truy cập. Kênh Một thành phần quan trọng của MQ được hình thành bởi các kênh messages. Mỗi kênh message c ó chính xác một liên kết hàng đợi gửi mà từ đó nó fetches những thông điệp cần chuyển đến đầu kia. Chuyển dọc theo kênh chỉ có thể xảy ra nếu cả hai bên gửi và nhận MCA đang hoạt động và chạy. Ngoài việc bắt đầu từ cả hai MCAs bằng tay, có một số cách khác để bắt đầu một kênh, một số trong đó chúng tôi có thảo luận kế tiếp. Một trong những thay thế là để có một ứng dụng trực tiếp bắt đầu kết thúc của một kênh bằng cách kích hoạt phía gửi hoặc nhận MCA. Tuy nhiên, từ yêu cầu về tính trong suốt, đây không phải là một lựa chọn rất hấp dẫn. Một cách tiếp cận tốt hơn để bắt đầu một gửi Mea là cấu hình của kênh gửi hàng đợi để đặt ra một kích hoạt khi một message là lần đầu tiên đưa vào hàng đợi. Kích hoạt đó là liên kết với một xử lý để bắt đầu gửi MCA để nó có thể loại bỏ thư từ hàng đợi gửi. Một lựa chọn khác là để bắt đầu một MCA qua mạng. Cụ thể, nếu một bên của một kênh đã được kích hoạt, nó có thể gửi một thông điệp điều khiển yêu cầu MCA khác bắt đầu. Như một thông điệp điều khiển được gửi đến một daemon nghe đến một địa chỉ nổi tiếng trên cùng một máy như là nơi MCA khác bắt đầu. Kênh được ngừng lại tự động sau một thời gian quy định đã hết hạn nh ưng không có message nào bị bỏ vào hàng đợi gửi. Mỗi MCA có một tập các thuộc tính liên quan xác định các hành vi tổng thể của một kênh. Một số các thuộc tính được liệt kê trong Hình. 4-23. Thuộc tính giá trị của việc gửi và nhận MCA cần được tương thích và có lẽ ph ải đc đàm phán đầu tiên trước khi một kênh có thể được thiết lập. Ví dụ, cả hai MCAs rõ ràng nên hỗ trợ giao thức transport như nhau. Một ví dụ của một thuộc tính nonnegotiable là messages sẽ được chuyển giao k theo thứ tự như chúng được đưa vào gửi hàng đợi. Nếu một trong MCA muốn chuyển ph át FIFO, phía kia c ũng phải tuân theo. Một ví dụ về một thỏa thuận giá trị thuộc tính là chiều dài tối đa của messages, mà chỉ đơn giản sẽ được chọn làm giá trị tối thiểu xác định bởi MCA. Truyền Message Để chuyển một messages từ một người quản lý hàng đợi đến một người quản lý hàng đợi khác (có thể điều khiển từ xa) , đó là cần thiết rằng mỗi message mang địa chỉ đích của nó, được sử dụng trong quá trình truyền dẫn. Một địa chỉ trong MQ gồm hai phần. Phần thứ nhất bao gồm tên của người quản lý hàng đợi mà message sẽ được chuyển giao. Phần thứ hai là tên của hàng đợi đích resorting theo đó người quản lý mà messages này được gắn vào(the name of the destination queue resorting under that manager to which the message is to be appended.). Bên cạnh các địa chỉ đích, nó cũng cần xác định các tuyến đường mà một messages nên đc chuyển theo. Đặc điểm kỹ thuật của tuyến đ ừơngđược thực hiện bằng cách cung cấp tên của hàng đợi gửi địa phương mà message được gắn vào. Vì vậy, nó không phải là cần thiết để cung cấp đầy đủ các tuyến đường trong messages. Nhớ lại rằng mỗi kênh message có đúng một hàng đợi gửi. Trong hầu hết trường hợp, các tuyến đường được rõ ràng lưu giữ trong một nhà quản lý hàng đợi trong một bảng định tuyến. Một mục nhập trong một bảng định tuyến là một cặp (destQM, sendQ), nơi destQM là tên của người quản lý hàng đợi đích, và sendQ là tên của các hàng đợi gửi địa phương mà message cho người quản lý hàng đợi nên được nối. (Một mục nhập bảng định tuyến được gọi là một bí danh trong MQ.) Có thể là một message cần phải được chuyển qua nhiều nhà quản lý hàng đợi trước khi đến đích của nó. Bất cứ khi nào một người quản lý hàng đợi trung gian nhận được messages, nó đơn giản chỉ trích tên của người quản lý hàng đợi đích đến từ các tiêu đề messages, và định tuyến-table look-up để tìm hàng đợi địa phương để gửi messages, đ ịa ch ỉ đó sẽ được gắn v ào. Điều quan trọng là nhận thức rằng mỗi người quản lý hàng đợi có một tên duy nhất systemwide đc sử dụng hiệu quả như một định danh cho người quản lý hàng đợi đ ó. Vấn đề với việc sử dụng các tên này là thay thế một người quản lý hàng đợi, hoặc thay đổi tên của nó, sẽ ảnh hưởng đến tất cả các ứng dụng gửi messages đến nó. Vấn đề có thể khắc ph ục bằng cách sử dụng một bí danh cho tên địa phương quản lý hàng đợi. Một bí danh được định nghĩa với người quản lý hàng đợi Ml là một tên gọi cho một người quản lý hàng đợi M2, nhưng đó chỉ có sẵn để ứng dụng giao tiếp v ới Ml. Một bí danh cho phép sử dụng như nhau (logic) cho một hàng đợi, thậm chí nếu người quản lý hàng thay đổi . Thay đổi tên của một người quản lý hàng đợi yêu cầu chúng tôi thay đổi bí danh của ch úng trong tất cả các nhà quản lý hàng đợi. Tuy nhiên, các ứng dụng k thể tr ánh không bị ảnh hưởng. Các nguyên tắc sử dụng bảng định tuyến và bí danh là thể hiện trong hình. 4-24. Ví dụ, một ứng dụng được liên kết đến quản lý hàng đợi QMA có thể tham khảo một người quản lý hàng đợi từ xa sử dụng bí danh địa phương LAJ. Người quản lý hàng đợi đầu tiên sẽ tìm đích đến thực tế trong bảng bí danh để tìm người quản lý hàng đợi QMC. Các tuyến đường đến QMC được tìm thấy trong bảng định tuyến, messages cho QMC nên được nối vào hàng đợi gửi đi SQL, được dùng để chuyển các messages đến người quản lý hàng đợi QMB. Loại thứ hai sẽ sử dụng bảng định tuyến của nó để chuyển tiếp messages tới QMC. Sau này phương pháp tiếp cận định tuyến và bí danh dẫn đến một giao diện lập trình đó, về cơ bản, là tương đối đơn giản, được gọi là Message Queue Interface (MQI). Các phương thức nguyên thủy quan trọng nhất của MQI được tóm tắt trong Hình. 4-25. Để đưa vào hàng đợi một messages, ứng dụng gọi phương thức nguyên thủy MQopen, chỉ định một điểm đến hàng đợi ở một người quản lý hàng đợi cụ thể. Người quản lý hàng đợi có thể được đặt tên bằng cách sử dụng bí danh địa phương có sẵn. Cho dù hàng đợi đích thực sự là từ xa hay không là hoàn toàn trong suốt với ứng dụng. MQopen cũng nên được gọi nếu ứng dụng muốn nhận được messages từ hàng đợi địa phương. Chỉ hàng đợi địa phương địa phương có thể được mở để đọc các messages đến. Khi một ứng dụng kết thúc với truy cập vào một hàng đợi, cần đóng nó bằng cách gọi MQclose.Thông điệp có thể được ghi vào, hoặc đọc từ, một hàng đợi bằng cách sử dụng MQput và MQget, tương ứng. Về nguyên tắc, thông điệp được gỡ bỏ khỏi một hàng đợi trên cơ sở ưu tiên. Thông điệp với ưu tiên giống nhau được xóa trên FIFO cơ sở, đó là, thông điệp đang chờ lâu nhất là bỏ đi đầu tiên. Cũng có thể để yêu cầu cho các messages cụ thể. Cuối cùng, MQ cung cấp cơ sở để báo hiệu ứng dụng khi message đã đến, như vậy tránh cho một ứng dụng liên tục sẽ có một cuộc thăm dò hàng đợi message cho các messages đến. Lớp phủ quản lý mạng lưới Từ các mô tả cho đến nay, cần rõ ràng một phần quan trọng của quản lý MQ hệ thống là kết nối các nhà quản lý hàng đợi khác nhau thành một mạng lưới che phủ vững chắc Ngoài ra, mạng lưới này cần phải được duy trì theo thời gian. Đối với các mạng nhỏ, điều này sẽ không cần bảo trì nhiều hơn công việc hành chính trung bình, nhưng vấn đề trở nên phức tạp khi hàng đợi message được sử dụng để tích hợp và phân rã hệ thống lớn hiện có. Một vấn đề lớn với MQ là mạng che phủ cần phải được quản trị. Người quản trị không chỉ liên quan đến việc tạo ra các kênh giữa các nhà quản lý hàng đợi, nhưng cũng điền vào các bảng định tuyến. Rõ ràng, điều này có thể phát triển thành một cơn ác mộng. Thật không may, quản lý, hỗ trợ cho các hệ thống tiên tiến MQ là chỉ theo ý nghĩa là một quản trị viên có thể thiết lập hầu như tất cả các thuộc tính có thể, và tinh chỉnh bất kỳ cấu hình có thể nghi tới. Tuy nhiên, trung tâm là kênh và các bảng định tuyến cần phải được duy trì bằng tay. Trọng tâm của quản lý lớp phủ là kiểm soát kênh chức năng thành phần, vị trí logic giữa các tác t ử kênh messages. Thành phần này cho phép một nhà điều hành để theo dõi chính xác những gì đang xảy ra tại hai điểm kết thúc của một kênh. Ngoài ra, nó được sử dụng để tạo ra các kênh và các bảng định tuyến, mà còn để quản lý các nhà quản lý hàng đợi mà lưu trữ các tác tử kênh message . Trong một cách n ào đ ó, phương pháp này để quản lý lớp phủ mạnh giống với việc quản lý các cụm máy chủ, nơi một máy chủ quản trị duy nhất được sử dụng. Trong trường hợp thứ hai, máy chủ cung cấp thực chất chỉ là một vỏ máy tính từ xa để mỗi trong cluster, cùng với một vài hoạt động tập thể để xử lý các nhóm máy móc. Các tin tốt về phân phối các hệ thống phân tán là nó cung cấp rất nhiều cơ hội nếu bạn đang tìm kiếm một khu vực để khám phá các giải pháp mới cho những vấn đề nghiêm trọng. 4.4 Truyền thông hướng luồng Medium (số nhiều là media) : chỉ các phương tiện dùng để truyền thông tin như các thiết bị lưu trữ, đường truyền, các phương tiện hiển thị… Continuous media: quan hệ thời gian giữa các mục là yếu tố cơ bản để thông dịch đúng ngữ nghĩa thực sự của dữ liệu. Discrete media: quan hệ thời gian không còn là yếu tố cơ bản để thông dịch đúng dữ liệu. Data stream: là một chuỗi các đơn vị dữ liệu. Với data stream thì thời gian là yếu tố quyết định. Để kiểm soát thời gian người ta đưa ra ba phương thức truyền sau: Truyền dị bộ (asynchronous transmission mode): các mục dữ liệu truyền tuần tự và không có ràng buộc thời gian đối với việc truyền. Truyến đồng bộ (synchronous transmission mode): quy định trước độ trễ tối đa cho mỗi đơn vị dữ liệu trong data stream. Truyền đẳng thời (isochronous transmission mode): quy định độ trễ lớn nhất và nhỏ nhất cho mỗi đơn vị dữ liệu trong data stream. Cách truyền này đóng một vai trò quan trọng trong việc trình diễn audio và video. Dòng đơn (simple stream) là dòng chỉ gồm một chuỗi đơn vị dữ liệu. Dòng phức (complex stream): bao gồm nhiều chuỗi đơn vị dữ liệu khác nhau. Mỗi chuỗi này được gọi là một dòng con (sub stream). Truyền thông như đã nói ở trên tập trung vào có sự thay đổi giữa sự độc lập ít - nhiều và những đơn vị hoàn chỉnh của thông tin, ví dụ như với 1 yêu cầu lời gọi hàm, kết quả trả lại một yêu cầu như vậy, và thông điệp được trao đổi giữa như 1 hệ thống xếp hàng thông điệp các ứng dụng. Tính năng đặc tính của loại truyền thông này là không quan trọng điều gì đặc biệt đã diễn ra vào thời điểm truyền. Mặc dù rằng 1 hệ thống có thể hoạt động hoặc quá chậm chạp hoặc quá nhanh thì việc định thời gian không có ảnh hưởng tới việc sửa lỗi Cũng có 1những kiểu truyền thông mà trong đó việc định thời gian đóng 1 vai trò quan trọng. Hãy xem xét ví dụ: Một dòng dữ liệu âm thanh được dựng như 1 dãy các mẫu 16 bit, mỗi mẫu được mã hóa thông qua PCM. Dòng dữ liệu âm thanh tương đương chất lượng của đĩa CD, nghĩa là âm thanh gốc được lấy mẫu ở tần số 44.100Hz. Để tái tạo lại nguồn âm thanh gốc, thì những mẫu trong dòng dữ liệu âm thanh được chơi theo thứ tự xắp xếp trong luồng ở 1/44100 phần giây là rất cần thiết. Chơi ở thần số khác sẽ tạo ra 1 phiên bản không đúng gốc Câu hỏi mà chúng ta chỉ ra ở trong phần này là bằng phương tiện nào để 1 hệ phân tán đưa ra sự chuyển đổi sự dữ liệu phụ thuộc thời gian như luồng dữ liệu âm thanh, hình ảnh. Nhiều giao thức mạng liên quan đến truyền thông hướng luồng đã được thảo luận như Halsall (2001), Steinmetz and Nahrstedt (2004) cung cấp một giới thiệu về những giải pháp cho đa phương tiện, 1 phần trong những giải pháp đó định hình cho truyền thông hướng luồng. 4.4.1 Hỗ trợ các phương tiện liền kề (Continuous media) Hỗ trợ cho việc chuyển những thông tin phụ thuộc thời gian thường được hiểu như là hỗ trợ cho những phương tiện liền kề bao gồm phương tiện lưu trữ và truyền, phương tiện trình diễn như màn hình và những phương tiện giống như vậy. Thông tin được truyền qua Medium. Một dạng quan trọng của Medium là cách mà thông tin được miêu tả. Nói cách khác, bằng cách nào thông tin được mã hóa trong hệ thống máy tính??? Những cách diễn đạt khác nhau đã được sử dụng cho những dạng khác nhau của tông tin. Ví dụ: ký tự thường được mã hóa bằng mã ASCII hoặc Unicode.. Trong Phương tiện liền kề (Continuous media) , mối quan hệ tạm thời giữa các mục dữ liệu khác nhau chủ yếu là để dịch nghĩa của dữ liệu. Chúgn ta vừa đưa ra 1 ví dụ về việc tái tạo sóng âm thanh bằng cách chơi một luồng dữ liệu âm thanh. Một ví dụ khác là chuyển động. Chuyển động có thể được thể hiện như 1 chuỗi các hình ảnh hiển thị đều đặn trong khoảng thời gian T, thông thường là 30-40 ms mỗi ảnh. Việc tái tạo lại đúng đòi hỏi không chỉ thể hiện thứ tự đúng mà còn cả về mã của đối tượng hoặc file thực thi Luồng dữ liệu Để có được sự chuyển đổi của thông tin phụ thuộc thời gian, thông thường hệ phân tán cung cấp sự hỗ trợ cho dòng dữ liệu. Luồng dữ liệu có thể được đưa vào để rời rạc giống như Continuous media. Những pipes trong Unix hoặc kết nối TCP/IP là những ví dụ tiêu biểu cho rời rạc hóa dòng dữ liệu. Chơi 1 file âm thanh đòi hỏi 1 cách tiêu biểu việc thiết lập 1 dòng dữ liệu liên tục giữa file và thiết bị âm thanh Việc định thời gian là cần thiết cho dòng dữ liệu liên tục. Một sự khác biệt được tạo tra giữa các chế độ truyền để có được những khoảng thời gian. Trong chế độ truyền dị bộ, dữ liệu trong dòng là dữ liệu được truyền sau những thông tin khác, nhưng không có thêm sự ràng buộc về mặt thời gian nào lên thời điểm truyền. Đó là trường hợp tiêu biểu cho việc rời rac hóa dòng dữ liệu. Trong chế độ truyền đồng bộ, một khoảng trễ lớn nhất định nghĩa mỗi đơn vị trong 1 dòng dữ liệu. Việc một đơn vị có được truyền nhanh hơn nhiều so với việc trễ lỗi lớn nhất hay không là không quan trọng. Cuối cùng , trong chế độ truyền đẳng thời (đồng bộ về mặt thời gian), điều quan trọng là truyền những đơn vị dữ liệu đúng thời gian. Chế độ này thường thích hợp cho hệ thống phân tán đa phương tiện và đóng 1 vai trò quan trọng trong việc biểu diễn âm thanh và video. Những dòng có thể là đơn giản hoặc phức tạp. Một dòng đơn bao gồm chỉ một dòng dữ liệu, nhưng ngược lại, một dòng phức bao gồm nhiều dòng đơn (được gọi là những dòng con) liên quan đến nhau. Sự liên quan giữa những dòng con trong một dòng phức tạp thường là sự phụ thuộc vào thời gian. Ví dụ như dữ liệu âm thanh stereo có thể được truyền bởi một dòng phức gồm 2 dòng con, mỗi dòng con là 1 kênh âm thanh đơn. Sự đồng bộ giữa các dòng con quan trọng, nếu như đồng bộ thất bại, việc tái tạo dữ liệu cũng thất bại Nhìn từ góc độ của một hệ phân tán, chúng ta có thể phân biệt nhiều thành tố cần cho việc hỗ trợ dòng. Đơn giản là chúng ta tập trung vào việc tạo dòng những dữ liệu đã được lưu trữ cũng giống như tạo dòng những dữ liệu thực. Trong trường hợp dữ liệu được thu trong thời gian thực và được gửi qua mạng đến người nhận, điểm khác nhau lớn nhất giữa 2 loại dữ liệu trên là dòng dữ liệu thực có ít cơ hội điều chỉnh 1 dòng hơn. Theo Wu et al (2001), chúng ta sau đó có thể phác thảo ra 1 kiếm trúc client-server để hỗ trợ dòng đa phương tiện liên tục như hình 4-26 Kiến trúc thông thường này tiết lộ một con số của những giải pháp quan trọng cần được quan tâm đến. Đầu tiên là dữ liệu đa phương tiện, đoạn video đặc biệt và một đoạn âm thanh ít mở rộng hơn cần được nén mạnh theo thứ tự để giảm yêu cầu về dung lượng lưu trữ và đặc biệt là khả năng của mạng. Quan trọng hơn là kiểm soát chất lượng của giải phát truyền và đồng bộ. 4.2 Dòng và Chất lượng Dịch vụ Chất lượng dịch vụ QoS liên quan đến các vấn đề sau: Băng thông yêu cầu, tốc độ truyền, trễ… Loss sensitivity: kết hợp cùng với loss interval cho phép ta xác định được tốc độ mất mát thông tin có thể chấp nhận được. Burst loss sensitivity: cho phép xác định bao nhiêu đơn vị dữ liệu liên tiếp có thể bị mất. Minimum delay noticed: xác định giới hạn thời gian trễ trên đường truyền cho phép để bên nhận không nhận biết được là có trễ. Maximum delay variation: xác định độ trễ (jitter) rung lớn nhất cho phép. Quality of guarantee: chỉ số lượng các dịch vụ yêu cầu cần phải có. Những yêu cầu định thời thông thường được diễn tả như yêu cầu về Chất lượng dịch vụ(QoS) . Những yêu cầu này mô tả những điều cần thiết từ hạ tầng của hệ phân tán và mạng . Ví dụ, mối liên hệ tam thời trong 1 dòng có hẻ được đảm bảo. QoS cho dòng dữ liệu liên tục chủ yếu là liên quan đếm sự timeliness,volume và sự tin cậy. Trong phần này chúng ta sẽ tiếp cận gần hơn với QoS và quan hệ của nó đến việc thiết lập một dòng Chúng ta đã nói nhiều về việc chỉ ra những QoS được yêu cầu. Từ 1 quan điểm của ứng dụng, trong nhiều trường hợp có thể tổng quát đựoc 1 số thuộc tính quan trọng sau: Số bit yêu cầu cho dữ liệu để truyền Độ trễ lớn nhất cho đến khi 1 phiên làm việc được thiết lập (ví dụ như khi 1 ứng dụng có thẻ bắt đầu gửi dữ liệu) Độ trễ end-to-end lớn nhất (vd: mất bao lâu để truyền 1 đơn vị dữ liệu từ đầu này đến đầu kia) Biến trễ lớn nhất hoặc nhiễu (jitter) Trễ vòng lớn nhất Chú ý rằng nhiều cải tiến đã được đưa ra trong những mô tả, như những điều đã được giải thích, những ví dụ. Tuy nhiên khi tiếp cận với truyền thông hướng dòng dựa trên Stack của giao thức Internet, chúng ta phải thực tế là cơ sở của truyền thông được định hình bởi một dịch vụ dữ liệu siêu đơn giản, hiệu quả tốt nhất: IP . Tính năng của IP cho phép thực thi giao thức loại bỏ gói dữ liệu nếu stack đầy. Nếu không phải là tất cả các hệ phân tán đều hỗ trợ truyền thông hướng dòng, thí nhiều gói sẽ được xây dựng trên đỉnh của Stack của giao thức Internet. Quá nhiều cho chức năng QoS (Thực tế, IP cung cấp một số hỗ trợ cho QoS) Tạo hiệu lực cho QoS Hệ thống dưới cung cấp chỉ 1 dịch vụ vận chuyển có hiệu năng tốt nhất, một HPT có thể thử che giấu nhiều nhất có thể những thiếu sót về chất lượng của dịch vụ. Thật không may là có nhiều máy móc đã được triển khai như vậy Đầu tiên, vấn đề này không quá tệ như đã trình bày. Ví dụ: Internet cung cấp 1 phương tiện cho các lớp khác biệt của dữ liệu bới phương thức của các dịch vụ khác biệt của nó . Một host gửi có thể nhất thiết đánh dáu các gói gửi đi khi đang thuộc về một trong vài lớp , bao gồm một lớp chuyển tiếp đã được xác đinh Thêm vào đó, cõng có 1 vài lớp chuyển tiếp giả lập mà đường truyền được chia thành 4 lớp con. Có 3 cách bỏ những gói tin nếu bị nghẽn mạng. Sự giả lập chuyển tiếp bởi vậy định nghĩa 1 cách hiệu quả 1 số những thứ tự ưu tiên có thể gán vào các gói tin và điều đó cho phép những ứng dụng phân biệt những góp nhạy cảm với thời gian từ những gói khác. Bê cạnh những giải pháp ở lớp mạng này, HPT cũng có thể giúp đỡ việc lấy dữ liệu từ bên nhận. Mặc dù rằng không có nhiều công cụ hợp lệ để sử dụng nhưng một công hữu hiệu thôgn thường là sử dụng bộ đệm để giảm nhiễm (Jittter). Nguyên lý này đơn giản và được chỉ ra ở hình 4-27. Giả thiết rằng gói tin bị trễ với 1 biến xác định nào đó khi được truyền trên mạng, bên nhận chỉ đơn giản là lưu nó lại trong bô đệm với 1 khoảng thừoi gian lớn nhất. Điều này cho phép bên nhận đưa những gói tin qua ứng dụng theo cách thông thường và biết rằng các có đủ các gói tin để dùng hết chúng trong bộ đệm Figure 4-27. Dùng bộ đệm để giảm nhiễu . Đương nhiên là có thể có 1 vài sai sót , như điều đã được chỉ ra với gói 8 trong hình 4-27. Kích thước scủa bộ đệm bên nhận phù hop với những gói có thời gian truyền ít hơn hoặc bằng 9 giây để đưa qua ứng dụng. Không may là gói 8 mất 11 giây để đến bên nhận, ở thời điểm này, bộ đệm sẽ hoàn toàn trống. Kết quả là có 1 chỗ trống dữ liệu trong lúc ứng dụng chạy. Giải pháp duy nhất là tăng kích thước bộ đệm lên . Những kỹ thuật khác cũgn có thể dùng tốt. Ví dụ như kỹ thuật sửa lỗi. Việc êu cầu bên gửi truyền lại gói tin bị mất để đưa vào quá trình sửa lỗi chuyển tiếp. Một kỹ thuật được biết đến là mã hóa gói tin ra bằng 1 dạng mà chỉ cần k/n thông tin trong gói là có thể tái cấu trúc của gói k Một vấn đề có thể xảy ra là gói đơn mang dữ liệu âm thanh và cả hình ảnh. Hậu quả là khi 1 gói tin bị mất, bên nhận có thể nhận ra một khoảng trống khi chơi hết khung các đọan. Tác động này có thể được loại bỏ bằng cách chèn vào những khung như hình 4-28. Bằng cách này, khi một gói bị mất, khoảng trống trong khung dữ liệu hoàn chỉnh sẽ được phân tán về thời gian. Chú ý rằng dù vậy cách tiếp cận này đòi hỏi một số lượng bộ đệm lớn bên nhận trong việc tương thích với giải pháp không chèn khung, và cách đó buộc một độ trễ đầu lớn hơn cho việc ứng dụng nhận gói tin. 4.4.3. Đồng bộ dòng Một giải pháp quan trọng trong hệ thống đa phưong tiện là những dòng khác nhau, có thể xảy ra trong các dạng của dòng phức, là sự đồng bộ qua lại lẫn nhau. Đồng bộ dòng liên can đến việc duy trì các mối quan hệ tạm thời giữa các dòng. Có 2 loại đồng bộ. Loại đơn giản nhất của đòng bộ là giữa các dòng dữ liệu rời rạc và dòng dữ liệu liên tục. Ví dụ: 1 slide show trên web được tối ưu với âm thanh, mỗi slide được truyền từ máy chủ đến máy khách theo quy dạng của dòng dữ liệu rời rạc. Một dạng đòi hỏi hơn của đồng bộ là giữa những dòng dữ liệu liên tục. Một ví dụ thường ngày là chạy các đoạn movie đã được đồng bộ với âm thanh. Đồng bộ diễn ra ở cấp của đơn vị dữ liệu mà một dòng được tạo ra. Nói cách khác, chúng ta có thể đồng bộ 2 dòng chỉ giữa các đơn vị dữ liệu. Sự lựa chọn một cách chính xác 1 đơn vị dữ liệu nào phụ thuộc rất nhiều vào lớp trừu tượng ởa dòng dữ liệu được thể hiện. Máy đồng bộ Hai giải pháp của sự đồng bộ cần được phân biệt: (1) máy cơ sở cho đồng bộ 2 dòng và (2) sự phân bố những máy này trong môi trường mạng Máy đồng bộ có thể được thấy ở nhiều mức sự trừu tượng. Ở mức thấp nhất, sự đồng bộ được thực hiện một cách rõ ràng bởi việc điều hành các đơn vị dữ liệu của dòng đơn. Nguyên lý được chỉ ra trong hình 4-19, trong đó có 1 xử lý thực thi đơn giản là đọc và ghi các quá trình họat động trong nhiều dòng đơn, để chắc chắn rằng những hoạt động này bám sát với việc định thời và đồng bộ ràng buộc Figure 4-29. The principle of explicit synchronization on the level data units. Ví dụ: Giả định rằng đoạn video gồm 2 dòng đơn. Dòng video bao gồm các ảnh không nén chất lương thấp, mỗi ảnh được mã hóa bởi các byte đơn và theo đó thì mỗi ảnh cần 76.800 byte.Giả thiết rằng những bức ảnh được xuất hiện với tần số 30Hz hoặc mỗi ảnh xuất hiện 33ms Dòng audio bao gồm các mẫu âm thanh được nhóm vào trong mỗi đơn vị 11760 byte, mỗi đơn vị lại phù hợp với 33ms âm thanh theo như đã giải thích ở trên. Nếu mỗi xử lý đầu vào có thể xử lý 2,5Mb mỗi giây thì chúng ta có thể đạt được sự đồng bộ bằng cách đơn giản là xử lý lần lượt một khối gồm âm thanh và hình ảnh mỗi 33ms Trở ngại của cách tiếp cận này là ứng dụng được tạo ra hoàng toàn chịu trách nhiệm về việc thực thi đồng bộ trong khi nso chỉ có những chức năng ở mức thấp. Một cách tiếp cận tốt hơn là cho ứng dụng một giao diện mà cho phép nó có thể điểu khiển dòng và thiết bị dễ dàng hơn. Quay lại ví dụ trên, giả định rằng sự hiển thị video đa có 1 giao diện điều khiển cho phép nó có thể xác định rõ đâu là ảnh cần phải hiện. Với giao diện này thì người phát triển ứng dụng chỉ cần viềt một đoạn chương trình thể hiện bao gồm 2 bộ điều khiển, mỗi cái cho 1 dòng để kiểm tra nhóm dữ liệu video và audio được đồng bộ hay chưa và chỉnh nó nếu cần thiết. Ví dụ cuối cùng được đưa tra trong hình 4-30, và nó cần thiết cho nhiều hệ thống trung chuyển đa phương tiện. VỀ hiệu quả, hệ thống trung chuyển cho phép 1 tập hợp những giao diện điều khiển các dòng audio và video bao gồm các giao diện cho các thiết bị điều khiển như màn hình, microphone, v,v.. Mỗi thiết bị và các dùng có giao diện mức cao của nó, bao gồm những giao diện cho việc thông báo cho một ứng dụng khi nào sự kiện nào đó xảy ra. Ví dụ về loại giao diên như vậy được đưa ra bởi Blair và Stefani (1998) Figure 4-30. The principle of synchronization as supported by high-level interfaces. Sự phân tán những máy đồng bộ trong các giải pháp khác đổi hỏi phải được xem xét. Đầu tiên phía nhận của dòng phức bao gồm những dòng con mà yêu cầu sự đồng bộ, cần phải biết chính xác phải làm cái gì. Nói cách khác là phỉa hoàn thiện việc xác định sự đồng bộ cục bộ. Một hành động thông thường là cấp những thông tin này một cách hoàn toàn bằng việc dồn kênh nhữg dòng khác nhau thành một dòng bao gồm tất cả các đơn vị dữ liệu bao gồm cr những dữ liệu cho việc đồng bộ Các tiếp cận sau này để đồng bộ được dùng cho các dòng MPEG. Chuẩn MPEG định dạng cho một tập hợp những thuật tóan cho việc nén dữ liệu audio và video. Nhiều chuẩn MPEG đã tồn tại, MPEG2 là 1 ví dụ, và nguyên gôc của nó là để nén dữ liệu video vào khoảng 4-6Mbps. Trong MPEG2, một con số không giới hạn về các dòng liên tục và rời rạc có thể được nối lại vào 1 dòng đơn. Mỗi dòng vào được đưa vào 1 dòng các gói dữ liệu và được truyền đi dựa trên xung 90khz của hệ thống. Giải pháp quan trong khác là có hay không đồng bộ ơ rbên nhận hay bên guiử. Nếu bên gửi đồng bộ , có thể là nó sẽ nối nhữgn dòng vào một dòng đơn với những kiểu khác nhau về đơn vị dữ liệu. Lại giả định là dòng âm thanh stereo là truyền mỗi dòng độc lập tới bên nhận và sau đó là đồng bộ mẫu cùng 1 lúc. Hiển nhiên là mỗi dòng con có thể phân về các độ trễ khác nhau, sự đồng bộ lúc đó thực sự là khó khăn. Một cách tiếp cận tốt hơn là nối 2 dòng con ở bên gửi. Dòng kết quả bao gồm các đơn vị dữ liệu gồm 1 cặp mẫu cho từng kênh. Bên nhận chỉ cần đọc một đơn vị dữ liệu và tách chúng sang mẫu trái và phải. Độ trễ cho cả 2 kênh giờ đã giống nhau. 4.5 MULTICAST COMMUNICATION Một chủ đề quan trọng trong giao tiếp trong các hệ thống phân tán là hỗ trợ cho việc gửi dữ liệu đến đa người nhận, đã biết là truyền thông multicast.Trong nhiều năm qua, đề tài này đã thuộc về tên miền của giao thức mạng, nơi đề xuất nhiều cho giải pháp network-level và transport-level đã được triển khai và đánh giá (Janie, 2005; và Obraczka, 1998). Một vấn đề lớn trong tất cả các giải pháp đã được thiết lập đường dẫn truyền thông để phổ biến thông tin. Trong thực tế, điều này liên quan đến một nỗ lực quản lý rất lớn, trong nhiều trường hợp yêu cầu con người can thiệp. Ngoài ra, miễn là không có sự hội tụ của các đề xuất, ISPs đã chỉ ra được miễn cưỡng để hỗ trợ multicasting (Diot et ai, 2000.). Với sự ra đời của công nghệ peer-to-peer, và đáng chú ý là cấu trúc lớp phủ quản lý, nó trở nên dễ dàng hơn để thiết lập các đường truyền. Như giải pháp peer-to-peer thường được triển khai tại lớp ứng dụng, ở cấp ứng dụng kỹ thuật multicasting khác nhau đã được giới thiệu. Trong phần này, chúng tôi sẽ mất một lược xem xét các kỹ thuật này. Truyền thông Multicast cũng có thể được thực hiện theo những cách khác hơn là thiết lập đường dẫn truyền thông rõ ràng. Như chúng ta cũng khám phá trong phần này.Thông tin phổ biến gossip-based, cung cấp thông tin một cách đơn giản (nhưng thường ít hiệu quả) cho multicasting. 4.5.1 Application-Level Multicasting Ý tưởng cơ bản trong tầng ứng dụng multicasting là các nút tổ chức thành một Overlay-Network, mà sau đó sẽ được sử dụng để phổ biến thông tin cho các thành viên của nó. Một quan sát quan trọng là định tuyến mạng không được tham gia vào nhóm thành viên. Kết quả là, các kết nối giữa các nút trong các Overlay-Network có thể chéo một số các liên kết vật lý, và như vậy, các thông điệp định tuyến kèm theo lớp phủ có thể không được tối ưu so với những gì có thể đã đạt được bằng network-level-routing. Một vấn đề thiết kế rất quan trọng là xây dựng các mạng che phủ. Về bản chất, có hai phương pháp tiếp cận (El-Sayed, 2003). Trước tiên, các nút có thể tổ chức mình trực tiếp vào một cây, có nghĩa rằng có một con đường duy nhất (che phủ) giữa mọi cặp nút. Một cách tiếp cận khác cho rằng các nút tổ chức thành một mạng lưới trong đó mỗi nút sẽ có nhiều hàng xóm và, nói chung, có nhiều đường dẫn tồn tại giữa mỗi cặp nút. Sự khác biệt chính giữa hai cách ở trên là mà sau này muốn cung cấp cho độ bền cao hơn: nếu một kết nối bị hư (ví dụ, bởi vì một node không thành công), ở đó vẫn sẽ là một cơ hội để phổ biến thông tin ngay lập tức mà không cần phải tổ chức lại mạng che phủ toàn bộ. Để làm cho những vấn đề cụ thể, chúng ta hãy xem xét một đề án tương đối đơn giản để xây dựng một cây multicast tại Chord, mà chúng tôi mô tả trong Chap. 2. Sơ đồ này ban đầu được đề xuất cho scribe (Castro et al, 2002.) mà là một đề án tầng ứng dụng multicasting được xây dựng trên Pastry (Rowstron và Druschel, 2001). Điều thứ hai cũng là một hệ thống DHT-based peer-to-peer. Giả sử một nút muốn bắt đầu một phiên multicast. Để kết thúc việc này, nó chỉ đơn giản là tạo ra một nhận dạng multicast,mid chỉ được gọi là một lựa chọn ngẫu nhiên khóa 160-bit. Sau đó nó sẽ tìm đến Succ (mid), là nút chịu trách nhiệm tại khóa đó, và khuyến khích nó trở thành root của cây multicast đó mà sẽ được sử dụng để gửi dữ liệu đến các nút đã quan tâm. Để tham gia các cây, một nút P chỉ đơn giản thực hiện các hoạt động LOOKUP(mid) có hiệu lực cho một tin nhắn tra cứu với các yêu cầu tham gia vào mid của nhóm multicast sẽ được định tuyển từ P đến succ(mid). Như chúng tôi đã đề cập trước đó, các thuật toán định tuyến chính nó sẽ được giải thích chi tiết trong Chap. 5. Trên đường về root, các yêu cầu tham gia sẽ vượt qua một số nút. Giả định nó lần đầu tiên đạt đến nút Q. Nếu Q chưa bao giờ nhìn thấy một yêu cầu tham gia vào mid trước, nó sẽ trở thành một ngành giao nhận cho nhóm đó. Vào thời điểm đó, P sẽ trở thành một người con của Q trong khi sau này sẽ tiếp tục yêu cầu chuyển tiếp tham gia vào root. Nếu tiếp theo nút trên root, nói R cũng chưa là một ngành giao nhận, nó sẽ trở thành 1 thằng con và ghi Q, như con của mình và tiếp tục gửi các yêu cầu tham gia. Mặt khác, nếu Q (hay R) đã là một ngành giao nhận cho mid, nó sẽ ghi nhớ người gửi trước như 1 thằng con của nó (tức là, P hoặc Q, tương ứng), nhưng sẽ không cần gửi yêu cầu tham gia vào root nữa, như là Q (hoặc R) sẽ là một thành viên của cây multicast đó. Các nút như P có một cách rõ ràng yêu cầu để gia nhập cây multicast , Theo định nghĩa, cũng forwarders. Kết quả của chương trình này là chúng tôi xây dựng một cây multicast trên mạng che phủ với hai loại nút: forwarders tinh khiết đóng vai trò như người trợ giúp, và các nút mà cũng vân chuyển, nhưng có một cách rõ ràng yêu cầu để gia nhập cây. Multicasting bây giờ là đơn giản: một nút chỉ gửi một thông điệp multicast về phía root của cây bằng một lần nữa thực hiện các tra cứu hoạt động LOOKUP(mid), sau đó thông báo rằng có thể được gửi cùng cây. Chúng ta lưu ý rằng điều mô tả cấp cao của multicasting trong scribe không làm công lý để thiết kế ban đầu của chúng. Người đọc quan tâm là do đó khuyến khích xem xét các chi tiết, có thể được tìm thấy trong Castro et al.(2002). Overlay Construction Từ các mô tả cấp độ cao nhất định ở trên, cần rõ ràng rằng, mặc dù tự nó xây dựng một cây không phải là khó khăn khi chúng tôi đã tổ chức các nút vào một lớp phủ, xây dựng một cây hiệu quả có thể là một câu chuyện khác. Lưu ý rằng trong Mô tả của chúng tôi cho đến nay, việc lựa chọn tham gia vào các nút mà cây không mất vào tài khoản của bất cứ số liệu thực hiện: đó là hoàn toàn dựa trên (logical) định tuyến của tin nhắn thông qua các lớp phủ. Để hiểu được vấn đề trong tay, hãy xem hình. 4-31 trong đó cho thấy một lặp đặt nhỏ trong bốn nút được tổ chức tại một mạng lưới che phủ đơn giản, với nút A tạo được một root của cây multicast. Các chi phí để vượt qua một liên kết vật lý được cũng được hiển thị. Bây giờ, bất cứ khi nào A multicasts thư đến các nút khác, nó được nhìn thấy rằng thông báo này sẽ đi qua mỗi liên kết ,« Rc, Rd », và và . Chất lượng của một tầng ứng dụng cây multicast thường được đo bằng ba số liệu khác nhau: liên kết căng thẳng(link stress), căng ra(stretch), và chi phí cây(tree cost). Liên kết Căng thẳng được định nghĩa mỗi liên kết và tính được một gói đi qua cùng một liên kết (Chu et ai, 2002.). Một căng thẳng liên kết lớn hơn 1 đến từ thực tế là mặc dù mức độ một lúc hợp lý một gói dữ liệu có thể được chuyển tiếp dọc theo hai kết nối khác nhau, một phần của những kết nối thực sự có thể tương ứng với các liên kết vật lý tương tự, như chúng tôi đã cho thấy trong hình. 4-31. Các căng hoặc Relative Delay Penalty (RDP) đo tỷ lệ chậm trễ giữa hai nút trong lớp phủ, và trì hoãn việc mà những hai nút sẽ rút kinh nghiệm trong mạng nằm bên dưới. Ví dụ, trong mạng che phủ, thư từ B đến C theo các tuyến đường B ~ Rb ~ Ra ~ Rc ~ C, có tổng chi phí của 59 đơn vị. Tuy nhiên, tin nhắn sẽ được định tuyến trong mạng lớp dưới dọc theo con đường B ~ Rb ~ Rd ~ Rc ~ C, với tổng chi phí - 7 đơn vị, dẫn đến một căng của 1,255. Rõ ràng, khi xây dựng một mạng lưới che phủ, mục tiêu là để giảm thiểu căng tổng hợp, hoặc tương tự như vậy, RDP trung bình đo được trên tất cả các cặp nút. Cuối cùng, chi phí cây là một thước đo toàn cầu, nói chung liên quan tới việc giảm thiểu các chi phí liên kết tổng hợp. Ví dụ, nếu chi phí của một liên kết lấy được những chậm trễ giữa hai nút cuối cùng của nó, sau đó tối ưu hóa chi phí cây nắm để tìm một cây spanning tối thiểu trong đó tổng thời gian để phổ biến thông tin cho tất cả các nút là tối thiểu. Để đơn giản hóa những vấn đề một chút, giả định rằng một nhóm multicast có liên quan và nổi tiếng nút đó theo dõi các nút đó đã tham gia vào cây. Khi một nút mới các vấn đề ajoin yêu cầu, nó liên lạc hẹn nút này để có được một danh sách (có khả năng một phần) của các thành viên. Mục đích là để chọn các thành viên tốt nhất mà có thể hoạt động như là cha mẹ các nút mới trong cây. Ai cần chọn? Có nhiều lựa chọn thay thế và đề xuất khác nhau thường được thực hiện theo các giải pháp rất khác nhau.              Xem xét, ví dụ, một nhóm multicast với chỉ một nguồn duy nhất. Trong trường hợp, việc lựa chọn nút tốt nhất là hiển nhiên: cần nguồn (bởi vì trong trường hợp đó, chúng tôi có thể yên tâm rằng căng sẽ bằng 1). Tuy nhiên, trong thực hiện vì vậy, chúng tôi sẽ giới thiệu một topo sao với nguồn gốc ở giữa. Mặc dù đơn giản, nó không phải là khó tưởng tượng nguồn dễ dàng có thể trở nên quá tải. Trong Nói cách khác, lựa chọn của một node nói chung sẽ được hạn chế như vậy mà chỉ những nút có thể chọn những người có k hàng xóm hoặc ít hơn, với k là một thiết kế tham số. Hạn chế này nghiêm phức tạp cây-thuật toán thành lập, như là một giải pháp tốt có thể yêu cầu một phần của cây hiện tại là cấu hình lại.               Tân et al. (2003) cung cấp một tổng quan rộng rãi và đánh giá khác nhau giải pháp cho vấn đề này. Như minh hoạ một, chúng ta hãy xem xét kỹ hơn ở một gia đình cụ thể, được gọi là chuyển đổi cây (Helder và Jamin, 2002). Ý tưởng cơ bản là đơn giản. Giả sử chúng ta đã có một cây multicast với một nguồn duy nhất là gốc. Trong cây này, một nút P cha mẹ có thể chuyển đổi bằng cách thả vào liên kết để cha mẹ hiện tại của mình trong ưu tiên của một liên kết đến một nút khác. Các khó khăn chỉ áp đặt trên các liên kết chuyển mạch là rằng cha mẹ mới không bao giờ có thể là một thành viên của subtree bắt nguồn từ lúc P (như này sẽ phân vùng cây và tạo một vòng lặp), và rằng cha mẹ mới sẽ không có quá nhiều ngay lập tức trẻ em. Điều thứ hai là cần thiết để hạn chế tải trọng chuyển tiếp tin nhắn của bất kỳ nút duy nhất.               Có những tiêu chí khác nhau cho việc quyết định chuyển sang phụ huynh. Một một trong những đơn giản là để tối ưu hóa các tuyến đường đến nguồn, có hiệu quả giảm thiểu sự chậm trễ khi một tin nhắn là được multicast. Để kết thúc này, mỗi node thường xuyên nhận được thông tin về khác các nút (chúng tôi sẽ giải thích một cách cụ thể để làm điều này dưới đây). Tại thời điểm đó, các node có thể đánh giá xem nút khác cũng có thể là cha mẹ tốt hơn về sự chậm trễ dọc theo tuyến đường đến mã nguồn, và nếu như vậy, khởi một chuyển đổi.                Một tiêu chuẩn có thể được xem là sự chậm trễ để phụ huynh khác có tiềm năng là thấp hơn so với các phụ huynh hiện nay. Nếu mỗi nút mất này như một tiêu chuẩn một, sau đó trì hoãn tổng hợp kết quả của cây lý tưởng cần được tối thiểu. Nói cách khác, đây là một ví dụ về việc tối ưu hóa chi phí của cây như chúng tôi đã giải thích ở trên. Tuy nhiên, nhiều thông tin hơn sẽ là cần thiết để xây dựng một cây như vậy, nhưng khi nó quay ra, sơ đồ này đơn giản là một heuristic hợp lý dẫn đến một xấp xỉ tốt của một cây spanning tối thiểu.           Ví dụ, hãy xem xét trường hợp một nút P nhận được thông tin về hàng xóm của mẹ. Lưu ý rằng những người hàng xóm bao gồm ông bà P's, cùng với các anh chị em khác của cha mẹ P's. Nút P sau đó có thể đánh giá sự chậm trễ cho mỗi của các nút và sau đó chọn một với sự chậm trễ thấp nhất, nói Q, như của cha mẹ mới. Cuối cùng, nó sẽ gửi một yêu cầu chuyển đổi sang Q. Để ngăn chặn các vòng từ đang được hình thành do đồng thời yêu cầu chuyển đổi. một node có một nổi bật chuyển đổi sẽ từ chối yêu cầu đơn giản chỉ để xử lý bất cứ yêu cầu gửi đến. Trong thực tế, điều này dẫn đến tình hình một nơi mà chỉ chuyển mạch hoàn toàn độc lập có thể được thực ra đồng thời. Hơn nữa, P sẽ cung cấp cho Q với đủ thông tin để cho phép thứ hai để kết luận rằng cả hai nút có cùng cha mẹ, hoặc Q là ông bà.            Một vấn đề quan trọng là chúng tôi chưa có địa chỉ là nút thất bại. Trong trường hợp chuyển đổi cây, một giải pháp đơn giản là đề xuất: mỗi khi một nút thông báo rằng cha của nó đã không thành công, nó chỉ đơn giản là gắn chính nó vào gốc. Vào thời điểm đó, các giao thức tối ưu hóa có thể tiến hành nhưbình thường và cuối cùng sẽ diễn ra tại một nút tốt điểm trong cây multicast. Thí nghiệm được mô tả trong Helder và Jamin (2002) cho thấy, cây kết quả thực sự là một trong gần một spanning tối thiểu. 4.5.2 Gossip-Based Data Dissemination Một kỹ thuật ngày càng quan trọng cho việc phổ biến thông tin là dựa về hành vi của bệnh dịch. Quan sát các bệnh lây lan như thế nào giữa các dân, các nhà nghiên cứu đã từ lâu điều tra xem các kỹ thuật đơn giản có thể được phát triển cho lan truyền thông tin trong các hệ thống rất quy mô lớn được phân phối. Mục đích chính của những giao thức này là nhanh chóng dịch tuyên truyền thông tin giữa các lớn bộ sưu tập của các nút chỉ bằng cách sử dụng thông tin địa phương. Nói cách khác, không có trung tâm thành phần mà phổ biến thông tin là điều hợp.           Để giải thích những nguyên tắc chung của các thuật toán, chúng tôi giả định rằng tất cả các bản cập nhật • cho một mục dữ liệu cụ thể được bắt đầu tại một nút duy nhất. Bằng cách này, chúng tôi chỉ đơn giản là tránh viết-ghi xung đột. Trình bày sau đây là dựa trên cổ điển giấy bởi Demers et al. (1987) về các thuật toán dịch. Một tổng quan gần đây phổ biến thông tin dịch bệnh có thể được tìm thấy trong Eugster lúc el. (2004). Information Dissemination Models Như tên cho thấy, dịch thuật toán dựa trên lý thuyết của dịch bệnh, trong đó nghiên cứu các lây lan các bệnh truyền nhiễm. Trong trường hợp quy mô lớn hệ thống phân phối, thay vì bệnh lây lan, họ information.Research về dịch bệnh lây lan cho các hệ thống phân phối cũng nhằm mục tiêu hoàn toàn differentgoal: trong khi đó sức khỏe các tổ chức sẽ làm hết sức tốt nhất của họ để ngăn ngừa các bệnh truyền nhiễm lây lan trong các nhóm lớn của người dân, nhà thiết kế của các thuật toán dịch cho các hệ thống phân phối sẽ cố gắng "lây nhiễm" tất cả các nút với các thông tin mới nhanh aspossible.          Sử dụng các thuật ngữ từ dịch bệnh, một nút là một phần của một hệ thống phân phối được gọi là mắc bệnh nếu nó giữ dữ liệu mà nó sẵn sàng để lây lan sang các nút khác. Một nút mà vẫn chưa thấy dữ liệu này được gọi là nhạy cảm. Cuối cùng, một nút, cập nhật mà không sẵn sàng hoặc có thể lan truyền dữ liệu của nó được nói là được loại bỏ. Lưu ý rằng chúng ta giả sử chúng ta có thể phân biệt tuổi từ dữ liệu mới, ví dụ, vì nó đã được timestamped hoặc versioned. Trong ánh sáng này, các nút cũng cho biết bản cập nhật để lây lan.          Một mô hình tuyên truyền phổ biến là chống dữ liệu ngẫu nhiên. Trong mô hình này, một nút P Q picks một nút ngẫu nhiên, và sau đó trao đổi thông tin cập nhật với Q. Có ba phương pháp tiếp cận để trao đổi thông tin cập nhật:           1. P chỉ đẩy bản cập nhật của chính mình để Q           2. P chỉ kéo innew cập nhật từ Q           3. P và Q sendupdates với nhau (ví dụ, apush-pull cách tiếp cận)            Khi nói đến lây lan nhanh chóng cập nhật, chỉ đẩy các cập nhật hóa ra là một sự lựa chọn xấu. Trực giác, điều này có thể được hiểu như sau. Trước tiên, lưu ý rằng trong một đẩy thuần dựa trên phương pháp tiếp cận, cập nhật có thể được nhân giống chỉ bằng các nút bị nhiễm bệnh. Tuy nhiên, nếu các nút nhiều bị nhiễm, xác suất của mỗi một trong những lựa chọn một nút nhạy cảm là tương đối nhỏ. Do đó, rất có thể là có một nút cụ thể vẫn còn nhạy cảm trong một thời gian dài chỉ đơn giản bởi vì nó không được chọn bởi một nút bị nhiễm bệnh.            Ngược lại, kéo theo phương pháp làm việc tốt hơn khi các nút nhiều bệnh. Trong trường hợp đó, thông tin cập nhật lan rộng về bản chất là kích hoạt bởi các nút nhạy cảm. Là cơ hội lớn như vậy một nút sẽ liên hệ với một trong nhiễm để sau đó kéo vào các thông tin cập nhật và bị nhiễm bệnh là tốt.            Cũng có thể thấy rằng nếu chỉ có một nút duy nhất là mắc bệnh, bản cập nhật sẽ nhanh chóng lan truyền trên tất cả các nút sử dụng một trong hai hình thức chống dữ liệu ngẫu nhiên, mặc dù push-pull vẫn là chiến lược tốt nhất (Jelasity et al, 2005a.). Xác định một vòng như một spanning khoảng thời gian mà trong đó mỗi nút sẽ có ít nhất một lần đưa các sáng kiến để trao đổi cập nhật với một nút khác được chọn ngẫu nhiên. Sau đó có thể thấy rằng số lượng của viên đạn để truyền bá một cập nhật duy nhất cho tất cả các nút mất O (log (N)) vòng, nơi N là số nút trong hệ thống. Điều này chỉ ra rằng thực sự tuyên truyền cập nhật là nhanh chóng, nhưng trên tất cả khả năng mở rộng.            Một cụ thể biến thể của phương pháp này được gọi là tin đồn lan rộng, hoặc đơn giản là gossiping. Nó hoạt động như sau. Nếu P nút vừa được cập nhật dữ liệu hàng x, nó địa chỉ liên hệ một khác tùy ý nút Q và cố gắng để đẩy những cập nhật cho H. Tuy nhiên, nó là Có thể là Q đã được cập nhật bằng một nút khác. Trong trường hợp đó, P có thể bị mất quan tâm trong việc truyền bá các cập nhật bất cứ tiếp tục, nói với 11k xác suất. Trong khác từ, sau đó nó sẽ trở thành loại bỏ. Gossiping là hoàn toàn tương tự với cuộc sống thực. Khi Bob có một số tin tức nóng để lây lan xung quanh, ông có thể điện thoại Alice bạn mình nói cho tất cả các cô về nó. Alice, giống như Bob, sẽ được thực sự vui mừng lây gossip đến bạn bè của cô là tốt. Tuy nhiên, cô ấy sẽ trở thành thất vọng khi gọi số một người bạn, nói Chuck, chỉ khi được biết những tin tức đã đạt đến ông. Cơ hội được rằng cô sẽ ngừng gọi số khác bạn bè, cho những gì tốt là nó nếu họ đã biết?            Gossiping biến ra được một cách tuyệt vời của tin tức nhanh chóng lan rộng. Tuy nhiên, nó không thể đảm bảo rằng tất cả các nút trên thực tế sẽ được cập nhật (Demers et ai., 1987). Có thể thấy rằng khi có một số lượng lớn các nút đó tham gia vào dịch bệnh, phần nhỏ trong s các nút đó sẽ vẫn dốt nát của một cập nhật, nghĩa là, vẫn còn nhạy cảm, đáp ứng các phương trình:                          s = e-(k + \) (1-.1 ')           Fig.4-32 hiện tại (s) như là một chức năng của k. Ví dụ, nếu k = 4, Trong (51) =- 4,97, do đó s nhỏ hơn 0,007, có nghĩa là ít hơn 0,7% của các nút vẫn còn nhạy cảm. Tuy nhiên, các biện pháp đặc biệt là cần thiết để bảo đảm rằng những nút cũng sẽ được cập nhật. Kết hợp chống entropy với gossiping sẽ làm các trick.          Một trong những ưu điểm chính của thuật toán dịch là khả năng mở rộng của họ, do thực tế là số lượng synchronizations giữa các quá trình là tương đối nhỏ so với phương pháp tuyên truyền khác. Đối với hệ thống khu vực rộng, Lin và Marzullo (1999) cho thấy rằng nó làm cho tinh thần để đi theo topo mạng thực tế vào tài khoản để đạt được kết quả tốt hơn. Trong phương pháp tiếp cận của họ, các nút được kết nối với chỉ một vài các nút khác được liên lạc với một xác suất tương đối cao. Các lớp dưới giả định là các nút đó hình thành một cầu nối để các bộ phận khác của mạng từ xa; Do đó, họ nên được liên lạc càng sớm càng tốt. Cách tiếp cận này được gọi là là gossiping và định hướng đến trong các biến thể khác nhau.          Chạm đến vấn đề này khi một giả định rằng các giải pháp quan trọng nhất làm cho bệnh dịch, cụ thể là có một nút ngẫu nhiên có thể chọn bất kỳ nút khác để gossip với. Điều này ngụ ý rằng, về nguyên tắc, các thiết lập hoàn toàn của các nút cần biết là mỗi thành viên. Trong hệ thống alarge, giả định này không bao giờ có thể giữ.           May mắn thay, không có cần phải có một danh sách như vậy. Như chúng tôi đã giải thích tại Chap. 2, duy trì một lần xem một phần đó là nhiều hay ít liên tục cập nhật sẽ tổ chức bộ sưu tập của các nút vào một đồ thị ngẫu nhiên. Bởi thường xuyên cập nhật phần xem của mỗi node, lựa chọn ngẫu nhiên không còn là vấn đề. Removing Data Thuật toán dịch rất tốt để truyền bá thông tin cập nhật. Tuy nhiên, họ có một mặt khá lạ, có hiệu lực: lan rộng việc xoá một mục dữ liệu là cứng. Bản chất của vấn đề nằm ở một thực tế là xóa dữ liệu của một mục tiêu hủy tất cả các thông tin về sản phẩm đó. Do đó, khi một mục dữ liệu chỉ đơn giản là loại bỏ khỏi một nút, là nút cuối cùng sẽ nhận được bản sao cũ của mục dữ liệu và giải thích những người như cập nhật vào cái gì nó đã không có trước đó.           Bí quyết là để ghi nhận việc xoá một mục dữ liệu như cập nhật các chỉ khác, và giữ một hồ sơ về xóa đó. Bằng cách này, bản cũ sẽ không được hiểu là cái gì mới, nhưng chỉ được coi như là phiên bản đã được cập nhật bởi một xóa hoạt động. Các ghi âm của xóa một được thực hiện bằng cách trải giấy chứng nhận cái chết. Tất nhiên, một vấn đề với giấy chứng nhận cái chết là họ nên cuối cùng được làm sạch lên, hoặc mỗi nút dần dần sẽ xây dựng một cơ sở dữ liệu khổng lồ của địa phương thông tin lịch sử trên dữ liệu đã xóa bài đó là nếu không được sử dụng. Demers et al. (1987) đề xuất để sử dụng những gì họ gọi giấy chứng nhận cái chết không hoạt động. Mỗi cái chết Giấy chứng nhận là timestamped khi nó được tạo ra. Nếu nó có thể được giả định rằng bản cập nhật tuyên truyền cho tất cả các nút trong vòng một thời gian hữu hạn được biết đến, sau đó cóthể được chứng nhận cái chết gỡ bỏ sau khi tuyên truyền tối đa thời gian này đã trôi qua.            Tuy nhiên, để cung cấp bảo lãnh khó mà xóa thật sự đang lan rộng đến tất cả các nút, chỉ có một nút rất ít duy trì giấy chứng nhận cái chết không hoạt động mà không bao giờ vứt bỏ. Giả sử nút P có các giấy chứng nhận cho dữ liệu hàng x. Nếu do bất kỳ cơ hội cập nhật lỗi cho x đạt đến P, P sẽ phản ứng bằng cách đơn giản lây lan của Giấy chứng nhận cái chết cho x một lần nữa. Applications Để hoàn thành bản trình bày này, chúng ta hãy xem xét một số ứng dụng thú vị các giao thức dịch. Chúng tôi đã đề cập đến thông tin cập nhật lan rộng, trong đó có lẽ là rộng rãi nhất triển khai ứng dụng. Ngoài ra, trong Chap. 2 chúng tôi đã thảo luận làm thế nào cung cấp thông tin định vị về các nút có thể trợ giúp trong việc xây dựng topo cụ thể. Trong ánh sáng cùng, gossiping có thể được sử dụng để phát hiện ra rằng có một nút gửi đi vài liên kết khu vực rộng, để rồi sau đó áp dụng hướng gossiping như chúng tôi đã đề cập ở trên.             Một khu vực ứng dụng thú vị là chỉ cần thu thập, hoặc thực sự tập hợp thông tin (Jelasity et al, 2005b.). Hãy xem xét việc trao đổi thông tin sau đây. Mỗi i ban đầu nút chọn một số tùy ý, nói Xi-Khi nút i chỉ liên lạc nút j, họ mỗi lần cập nhật giá trị của họ như:  Xi,Xjß (Xi+Xj)/2  Rõ ràng. sau khi trao đổi này, cả hai i và j sẽ có giá trị như nhau. Trong thực tế. nó là không khó để thấy rằng cuối cùng tất cả các nút sẽ có cùng giá trị, cụ thể là, các trung bình của tất cả các giá trị ban đầu. Tuyên truyền tốc độ một lần nữa mũ.             Những gì không sử dụng máy tính trung bình có? Xem xét tình hình là tất cả i đã thiết lập các nút Xi về không, ngoại trừ x tôi, mà đã thiết lập nó cho tôi:     Nếu có các nút B, sau đó dần dần từng nút sẽ tính trung bình, mà là Lin. Kết quả là, mỗi khi tôi nút có thể ước tính kích thước của hệ thống như là Thông tin này Ilxi 'một mình có thể được sử dụng để tự động điều chỉnh các thông số hệ thống khác nhau. Ví dụ, kích thước của phần xem (nghĩa là, số lượng hàng xóm mà các nút từng theo dõi) nên phụ thuộc vào tổng số tham gia các nút. Hiểu biết con số này sẽ cho phép một nút để tự động điều chỉnh kích thước của xem một phần của nó. Thật vậy, điều này có thể được xem như là một tài sản của tự quản lý.                            Máy tính trung bình có thể chứng minh được khó khăn khi các nút thường xuyên tham gia và để lại hệ thống. Một trong những giải pháp thiết thực cho vấn đề này là giới thiệu kỷ nguyên. Giả sử nút I là ổn định, nó chỉ đơn giản là bắt đầu một kỷ nguyên mới ngay bây giờ và sau đó. Khi tôi nhìn thấy nút một kỷ nguyên mới cho lần đầu tiên, nó resets biến riêng của mình để Xi số không và bắt đầu tính toán mức trung bình một lần nữa.              Tất nhiên, kết quả khác cũng có thể được tính. Ví dụ, thay vì có một nút cố định (x 1) bắt đầu tính trung bình, chúng tôi có thể dễ dàng chọn một nút ngẫu nhiên như sau. Mỗi i nút ban đầu đặt ra Xi cho một số ngẫu nhiên từ cùng một khoảng thời gian, nói [0, I], và cũng có thể lưu trữ nó vĩnh viễn như m. Sau khi trao đổi giữa các nút i và j, mỗi lần thay đổi giá trị của họ về:                     Xi,Xjß max(Xi,Xj)                               Mỗi nút i mà mi <Xi sẽ mất tính cạnh tranh cho là xướng trong bắt đầu tính trung bình. Cuối cùng, sẽ có một người chiến thắng duy nhất. Tất nhiên, mặc dù nó rất dễ dàng để kết luận rằng một node đã bị mất, nó là nhiều hơn nữa khó khăn để quyết định rằng nó đã giành được, vì nó vẫn không chắc chắn liệu tất cả các kết quả đã đến.The đến giải pháp cho vấn đề này là để được lạc quan: một node luôn luôn giả định nó là người chiến thắng cho đến khi được chứng minh bằng cách khác. Vào thời điểm đó, nó chỉ đơn giản resets biến nó được sử dụng cho máy tính trung bình không. Lưu ý rằng bây giờ, một số khác nhau tính toán (trong ví dụ của chúng tôi tính toán tối đa và tính trung bình) có thể được thực hiện đồng thời.