Quản lý và phổ biến dữ liệu trong tính toán di động

 Tổng quan  Quảng bá và phổ biến dữ liệu  Phân phối băng thông cho kênh quảng bá  Lập lịch cho kênh quảng bá  Mobile Caching  Caching cho các hệ thống Push-Based  Quảng bá các thông báo vô hiệu hóa cache  Cơ chế không đồng bộ có trạng thái  Cơ chế cửa sổ trượt

pdf51 trang | Chia sẻ: Huongnt365 | Lượt xem: 495 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Quản lý và phổ biến dữ liệu trong tính toán di động, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Quản lý và phổ biến dữ liệu trong tính toán di động Tính toán di động 2011 Nội dung 1. Giới thiệu chung 2. Phổ biến dữ liệu 3. Caching Tính toán di động @Hà Quốc Trung 2011 2 1. Giới thiệu chung I. Môi trường di động II. Thiết bị di động III. Liên kết di động IV. Dữ liệu di động V. Tổng quan Tính toán di động @Hà Quốc Trung 2011 3 I. Tổng quan  Ứng dụng cung cấp thông tin  Email, Messaging, News  Giao thông công cộng, tình hình giao thông, thông tin về chuyến bay  Thông tin nghiệp vụ, tài chính, chứng khoản, mua-bán  Thông tin về sự kiện, chỗ đậu xe, điểm thăm quan du lịch, nhà hàng, thời tiết, hiệu thuốc, dịch vụ, danh bạ, ....  Nhiều loại thông tin có thể được cung cấp qua MC Tính toán di động @Hà Quốc Trung 2011 4 Nhiệm vụ/chức năng  Yêu cầu: chính xác, nhanh chóng  Nhiệm vụ  Tích hợp các dữ liệu/thông tin di động  Hệ thông tin di động toàn cầu  Bảo mật và an toàn dữ liệu di động  Trung tâm dữ liệu di động  Mô hình dữ liệu thống nhất  PM trung gian để truy cập dữ liệu di động Tính toán di động @Hà Quốc Trung 2011 5 Thực hiện  Mô hình vật lý  Có thể có các mô hình phần cứng khác nhau  Server-mạng có dây-AP-mạng không dây-MS  Mô hình trao đổi thông tin  On demand: (i) gửi yêu cầu, (ii) nhận trả lời  Publish-Subscribe: (i) đăng ký, (ii)công bố  Tăng hiệu năng=>Bộ nhớ đệm Tính toán di động @Hà Quốc Trung 2011 6 Mô hình Publisher-Subscriber  Thuận lợi  Bản chất của mạng không dây: quảng bá  Khả năng co giãn cao (số lượng client thay đổi không ảnh hưởng nhiều đến hiệu năng của server)  Tỷ lệ các yêu cầu uplink (client=> server) nhỏ=> tiết kiệm năng lượng cho client  Vấn đề  Cấu trúc của thông tin quảng bá  Tần suất quảng bá (phối hợp giữa các đơn vị dữ liệu khác nhau)  Phân phối băng thông cho các đơn vị dữ liệu  Tiết kiệm năng lượng (vd hot items, doze mode) Tính toán di động @Hà Quốc Trung 2011 7 Caching  On demand: chi phí truy cập cao  Dự trữ  Phù hợp: nhiều=> lãng phí, ít=> chi phí cao  Bản chất của đối tượng dự trữ: mau hỏng, bền vững  => có khả năng giảm chi phí khi có chính sách phù hợp  Vấn đề cần giải quyết  Dự trữ thông tin=> có nhiều bản sao  Sai lệch thông tin: cần đảm bảo các thao tác đọc cho kết quả thống nhất  Xung đột thông tin: cần đảm bảo các thao tác ghi cho kết quả thống nhất Tính toán di động @Hà Quốc Trung 2011 8 II. Ảnh hưởng của tính toán di động  Hệ thống di động có thể là có kiến trúc/không có kiến trúc  Kết nối yếu/không ổn định  Thường xuyên ngắt kết nối  Ngắt chủ động  Ngắt bị động  Nhu cầu  Kết nối trong suốt  Đảm bảo dữ liệu sẵn sàng cho các ứng dụng khi kết nối bị/không bị ngắt Tính toán di động @Hà Quốc Trung 2011 9 Thiết bị di động  Tài nguyên hạn chế  CPU, bộ nhớ, nguồn  Tối thiểu hóa lượng tài nguyên sử dụng  Đảm bảo tính thống nhất dữ liệu một cách hợp lý  Liên kết di động  Bất đối xứng  Khác nhau giữa kênh lên và kênh xuống  MS cạnh tranh để có kênh lên=>tốn kém tài nguyên cho kênh lên  Tối ưu hóa việc sử dụng tài nguyên thông qua việc phân phối hợp lý kênh lên/kênh xuống Tính toán di động @Hà Quốc Trung 2011 10 Dữ liệu di động  Rất nhiều dữ liệu về vị trí  Rất nhiều dữ liệu phụ thuộc vị trí  Caching phụ thuộc vị trí  Mở rộng các cơ chế caching phù hợp với các dữ liệu vị trí Tính toán di động @Hà Quốc Trung 2011 11 MANET Mobile Adhoc Network  Kết nối chủ yếu là adhoc  Các nút định tuyến không tin cậy  Bản chất trao đổi thông tin P2P  Có các tính chất của MNET  => Giải quyết vấn đề caching cho adhoc Tính toán di động @Hà Quốc Trung 2011 12 2. Phổ biến dữ liệu I. Giới thiệu II. Phân phối băng thông cho các kênh logic III. Lập lịch cho kênh quảng bá Tính toán di động @Hà Quốc Trung 2011 13 I. Giới thiệu Tính toán di động @Hà Quốc Trung 2011 14  On demand  Gửi yêu cầu, nhận trả lời  2 thao tác, 1 lên, 1 xuống cho một đơn vị dữ liêu  Số lượng MS tăng=> Server bị quá tải  Số lượng đơn vị dữ liệu tăng=> tiêu tốn năng lượng của MS  Mô hình Push  MS đăng ký, server quảng bá  N phần tử dữ liệu=> 01 lên, N xuống  Số lượng MS tăng: không ảnh hưởng đến server  N tăng:  Chỉ có 1 thông báo lên  Độ trễ trung bình nhận một phần tử dữ liệu tăng Các kênh truyền logics Tính toán di động @Hà Quốc Trung 2011 15  Sử dụng hỗn hợp cả 2 mô hình  Kênh ondemand: đòi hỏi băng thông Uplink và Downlink  Kênh lên  Kênh xuống riêng  Kênh quảng bá: chủ yếu là băng thông Downlink  Bài toán:  phân phối băng thông cho các kênh logic  lập lịch quảng bá các đơn vị dữ liệu II. Phân phối băng thông cho kênh logic Tính toán di động @Hà Quốc Trung 2011 16  Giả định  Số lượng nút là M  tổng băng thông là B  băng thông quảng bá là 𝐵𝑏  băng thông on demand là 𝐵𝑜  Có n phần tử dữ liệu 𝐷1. . , 𝐷𝑛, kích thước S  Các thông báo yêu cầu thông tin kích thước R  Các phần tử xuất hiện với xác suất 𝑝1, 𝑝2 𝑝𝑛 theo thứ tự giảm dần  Các nút yêu cầu dữ liệu giống nhau với tốc độ là r yêu cầu /s  Tính thời gian truy cập một đơn vị dữ liệu  𝑇 = 𝑇𝑏 + 𝑇𝑜, trong đó  𝑇𝑜, thời gian trung bình để truy cập một đơn vị dữ liệu theo kiểu ondemand  𝑇𝑏, thời gian trung bình để truy cập dữ liệu từ kênh quảng bá Nếu kênh truyền là on demand Tính toán di động @Hà Quốc Trung 2011 17  Thời gian để truy cập một đơn vị dữ liệu theo ondemand S/Bb + R/Bo  Số lượng các yêu cầu trung bình trong cả hệ thống 𝑀 × 𝑟  Khả năng cung cấp dịch vụ 𝐵𝑜/(𝑆 + 𝑅)  Điểm tới hạn 𝑀 × 𝑟 gần với 𝐵𝑜 𝑆+𝑅 => rất khó có thể bổ sung thêm nút vào hệ thống  Không đảm bảo tính co giãn Nếu kênh truyền là broadcast Tính toán di động @Hà Quốc Trung 2011 18  Thời gian chờ trung bình của mỗi nút 𝑛/2 đơn vị (𝑛/2) ∗ ( 𝑆 𝐵𝑏 )  Không phụ thuộc vào số nút M  Chỉ phụ thuộc vào số lượng đơn vị dữ liệu n  => có thể điều chỉnh bằng cách thay đổi tần suất quảng bá của các đơn vị dữ liệu Ví dụ Tính toán di động @Hà Quốc Trung 2011 19  Quảng bá với 2 đơn vị dữ liệu 𝐷1𝑣à 𝐷2, với xác suất 𝑝1 ≫ 𝑝2  Thời gian truy cập vào 𝐷1 𝑣à 𝐷2 bằng 1/2 thời gian truy cập on demand  Hệ thống luôn luôn quảng bá 𝐷1 => thời gian truy cập vào 𝐷2 là vô cùng lớn.  Bài toán: xác định tần số quảng bá để thời gian truy cập trung bình nhỏ nhất  Kết quả: 𝑓1 = 𝑝1 𝑝1 + 𝑝2 ; 𝑓2 = 𝑝2 𝑝1 + 𝑝2  vd: 𝑝1 = 0,9, 𝑝2 = 0,1, 𝑝1 = 9𝑝2, khi đó 𝑓1 = 3 𝑓2  Có thể tổng quát kết quả cho n đơn vị dữ liệu bằng nhau. Giải thuật Tính toán di động @Hà Quốc Trung 2011 20  Xác định số đơn vị dữ liệu gán cho kênh ondemande, đảm bảo độ trễ < một giá trị ngưỡng L nào đó  Đưa càng nhiều “hot items” vào kênh quảng bá càng tốt.  Giải thuật For i = N down to 1 do: Begin 1. Assign D1, , Di to the broadcast channel 2. Assign Di+1, , DN to the on-demand channel 3. Determine the optimal value of Bb and Bo, to minimize the access time T, as follows a. Compute To by modeling on-demand channel as M/M/1 (or M/D/1) queue b. Compute Tb by using the optimal broadcast frequencies F1, , Fi c. Compute optimal value of Bb which minimizes the function T = To + Tb. 4. if T <= L then break End III. Lập lịch cho quảng bá Tính toán di động @Hà Quốc Trung 2011 21  Nhiệm vụ  Xác định quảng bá phần tử dữ liệu nào  Xác định quảng bá một phần tử dữ liệu khi nào  Trừu tượng hóa kênh logic với chương trình  Sử dụng kênh quảng bá như các ổ đĩa ảo, với tốc độ quay khác nhau  Kiến trúc  Nhiều đĩa ảo với các tốc độ quay khác nhau  Đĩa cập nhật nhanh nhất: phần tử dữ liệu được truy cập nhiều nhất  Tốc độ quay-tần suất truy cập Giải thuật AAFZ Tính toán di động @Hà Quốc Trung 2011 22  Lập lịch cho các đĩa để đạt được tốc độ quay tương đối  Đầu vào  N đĩa: vd1, vd2..vdN  Ánh xạ các phần tử dữ liệu có tần suất xấp xỉ nhau fi vào đĩa i  Tốc độ quay tương đối của các đĩa khi đó là fi  Đầu ra: Lịch quảng bá các phần tử dữ liệu  Giải thuật  max_chunk=BCLN(fi)  Chia đĩa ảo i thành 𝑛𝑢𝑚_𝑐ℎ𝑢𝑛𝑘(𝑖) = max _𝑐ℎ𝑢𝑛𝑘 𝑓(𝑖) chunk  Mỗi vòng lặp sẽ truyền các chunk với tần suất của đơn vị dữ liệu tương ứng. Giải thuật AFFZ Tính toán di động @Hà Quốc Trung 2011 23 For i = 0 to max_chunk do: For j=1 to n-1 i. k=i mod num_chunk(j) ii. Quảng bá chunk(j,k) End For End For Ví dụ Tính toán di động @Hà Quốc Trung 2011 24 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 6 1 4 5 7 1 2 3 8 1 4 5 9 Data Items in decreasing Order of popularity Relative frequency 4 2 1 1 2 4 LCM = 4 = Max_Chunks Num Chunks = Max_Chunks/Rel_freq(i) Broadcast schedule Disk 1 Disk 2 Disk 3 3. Caching Tính toán di động @Hà Quốc Trung 2011 25 I. Caching trong hệ thống phân tán cố định II. Caching trong các hệ thống di động III. Mobile web caching I. Caching trong các hệ thống cố định Tính toán di động @Hà Quốc Trung 2011 26  Bài toán  Dữ liệu được sao lưu  Tại client, proxy, server  Dữ liệu được cập nhật bởi server (1 chiều), bởi client và server (2 chiều)  Cần thống nhất dữ liệu giữa client và server  Lý thuyết:  Khi nào cần thống nhất, cơ chế thống nhất  Thực tế  Thống nhất như thế nào Thống nhất mạnh/thống nhất yếu Tính toán di động @Hà Quốc Trung 2011 27  Thống nhất mạnh  Cập nhật dữ liệu được phổ biến ngay cho các bản sao  Chi phí  Thống nhất yếu  Không bắt buộc phổ biến ngay Các kỹ thuật caching (hệ thống cố định) Tính toán di động @Hà Quốc Trung 2011 28  Polling every time  TTL based  Server Invalidation  Leased Based Invalidation Đảm bảo tính thống nhất Tính toán di động @Hà Quốc Trung 2011 29  Tính thống nhất mạnh  Khi một phần tử dữ liệu được truy cập, tính thống nhất dữ liệu của phần tử luôn luôn được đảm bảo  Tính thống nhất yếu  Hi sinh tính thống nhất mạnh, chấp nhận có những thời điểm ứng dụng client và server truy cập vào các phần tử dữ liệu có giá trị khác nhau  Cơ chế  Validity check (kiểm tra tính hợp lệ của dữ liệu)  Callback (invalidation message): thông báo vô hiệu hóa dữ liệu  Chưa giải quyết được các vấn đề trong hệ thống di động  Vd nếu callback bị mất=> dữ liệu bị sai Mất thông báo vô hiệu hóa Tính toán di động @Hà Quốc Trung 2011 30 Các yếu tố cần quan tâm Tính toán di động @Hà Quốc Trung 2011 31  Cách thức/qui luật truy cập dữ liệu  Tần suất cập nhật dữ liệu  Chi phí truyền thông/truy cập  Cách thức/qui luật di chuyển  Đặc điểm của kết nối  Nhu cầu về tính cập nhật của dữ liệu  Thông tin phụ thuộc bối cảnh Các vấn đề cần giải quyết Tính toán di động @Hà Quốc Trung 2011 32  Giảm độ trễ (client)  Đảm bảo tính thống nhất của dữ liệu  Đảm bảo tính sẵn sàng cao của dữ liệu  Đảm bảo hiệu quả cao về nguồn/băng thông  Xác định chi phí của cache miss và sử dụng trong cơ chế cache  Quản lý dữ liệu vị trí trong cache  Đồng bộ các bộ nhớ đệm của nhiều bên Các lựa chọn có thể Tính toán di động @Hà Quốc Trung 2011 33  Cache ở đâu  Cache bao nhiêu lớp  Cache cái gì  Làm thế nào để hủy một phần tử cache  Mức độ cập nhật của thông tin trong cache  Hiệu quả đáp ứng yêu cầu Các mô hình caching trong MC Tính toán di động @Hà Quốc Trung 2011 34  3 mô hình cơ bản  Polling: client chủ động  TTL : client chủ động  Invalidation: server chủ động  Stateless: không trạng thái  Không đồng bộ, có đồng bộ  Statefull: có trạng thái  Không đồng bộ, có đồng bộ  2 loại thống nhất  Yếu,mạnh Caching cho các hệ thống mô hình Push Tính toán di động @Hà Quốc Trung 2011 35  Hệ thống cố định:  cache đơn vị dữ liệu được sử dụng nhiều nhất  Chủ yếu để tăng hiệu năng  Chi phí tải đơn vị dữ liệu không đáng kể  Hệ thống di động  Cần tính thêm chi phí tải đơn vị dữ liệu về client  Client C, 2 phần tử dữ liệu x và y,  tần suất xuất hiện là 1% và 0,5%  thời gian truyền là 1% và 0,1%  Thời gian chờ đợi giữa 2 đơn vị dữ liệu của y gấp 10 lần x=>vấn đề về độ trễ  Cần một cơ chế cache mới có tính đến chi phí tải, thời gian chờ khi truy cập các dữ liệu Nguyên tắc Tính toán di động @Hà Quốc Trung 2011 36  Gán cho các phần tử dữ liệu các thông số liên quan đến chi phí tải  Đưa vào trong hit ratio : thông số đánh giá chất lượng của hệ thống cache  Tỷ lệ các yêu cầu đọc từ cache trên tổng số các yêu cầu đọc  Ví dụ: Phần tử dữ liệu được coi là hot nếu tích giữa xác xuất xuất hiện và tần xuất quảng bá lớn hơn  => cải tiến các hệ thống caching đã có sẵn, đưa vào các thông số liên quan đến chi phí tải dữ liệu Quảng bá các thông báo vô hiệu hóa dữ liệu Tính toán di động @Hà Quốc Trung 2011 37  BT: quảng bá thời gian  Server quảng bá các thông báo vô hiệu hóa dữ liệu cho tất cả các dữ liệu trong khoảng thời gian [𝑡 − 𝑤, 𝑡]  Thông báo có dạng 𝑖𝑑, 𝑡𝑠  Id: số thứ tự của đơn vị dữ liệu  Ts: thời gian thay đổi cuối cùng của dữ liệu  Nhận được thông báo, MS m thực hiện  Với mỗi phần tử id, kiểm tra nếu ts cục bộ của id nhỏ hơn trong thông báo => xóa dữ liệu khỏi bộ đệm  w là thời gian mà một trạm MS có thể bị ngắt kết nối (bình thường). Quá thời gian đó, tất cả các dữ liệu trong bộ nhớ đệm cần được xóa đi Tính toán di động @Hà Quốc Trung 2011 38 Mobile Host (MH) Wireless Access Point Data Server w = kL L Time Queries Data item ID and its updation timestamp pair(ID,t) for all updated data items in last w time units Invalidation Report Queries are batched and answered after cache validation following the next invalidation report Cache validation is performed Một vài cải tiến Tính toán di động @Hà Quốc Trung 2011 39  Broadcasting Timestamp (BT)  A Variant of Broadcasting Invalidation Report (Jing and Colleagues, 1997) – Điều chỉnh kích thước của thông báo vô hiệu hóa để tối ưu băng thông  Two-Level Caching Scheme based on mobility agents (Liu and Maguire, 1996): Đưa tính chất di động của thiết bị vào mô hình cache  Sử dụng mô hình cập nhật và truy vấn và ngắt kết nối, kết nối (Hue and Lee 1998)  Đặc điểm chung  Không trạng thái  Không hướng tới các ứng dụng di động  Chưa giải quyết vấn đề nếu MS ngắt kết nối quá w=>tải lại dữ liệu Quản lý kết nối bị ngắt Tính toán di động @Hà Quốc Trung 2011 40  Nguyên tắc  Ngắt kết nối: không đảm bảo tính thống nhất  Tính sẵn sàng: có dữ liệu cho ứng dụng  Tính thống nhấttính sẵn sàng  Có nhiều trường hợp có thông tin (không) chính xác tốt hơn không có thông tin.  Nguyên lý: “dự trữ thông tin”  Cho phép client thao tác trên bộ nhớ đệm khi kết nối bị ngắt  Khi kết nối được thiết lập, xác nhận lại các thao tác đã được thực hiện  => cần có dấu thời gian cho các thay đổi dữ liệu  Tổng quát: làm lại tất cả các thao tác=> hiệu năng Dự trữ thông tin Tính toán di động @Hà Quốc Trung 2011 41  Dự trữ các phần tử thông tin nào?  Dự trữ thế nào (tần suất thay đổi của các thông tin  Xử lý khi có cache miss  Đồng bộ dữ liệu client-server Cơ chế không đồng bộ có trạng thái (Kahol- 2001) Tính toán di động @Hà Quốc Trung 2011 42  Nguyên lý  Sử dụng các thông báo không định kỳ để vô hiệu hóa các phần tử dữ liệu trong cache  Kết hợp giữa kết nối có dây và kết nối không dây Thành phần hệ thống Tính toán di động @Hà Quốc Trung 2011 43  Server: chứa dữ liệu  HA: chứa các HLC, mỗi MS có một HLC là một danh sách (x,T,invFlag)  MS: chứa cache với các đơn vị dữ liệu, có time stamp  Ứng dụng: gửi các yêu cầu dữ liệu đến MS  Kết nối: MS chứa ứng dụng. Server kết nối với HA bằng mạng có dây Điều kiện ràng buộc Tính toán di động @Hà Quốc Trung 2011 44  Khi đơn vị dữ liệu được cập nhật, thông báo vô hiệu hóa nội dung cache được gửi tới tất cả các HA bằng mạng có dây  HA chuyển tiếp thông báo đến cho MS  Không có thông báo bị mất khi chuyển trong mạng có dây  MS có thể phát hiện được tình trạng kết nối. Khi ở trạng thái không kết nối, không đáp ứng các yêu cầu từ ứng dụng  MS thông báo cho HA trước khi cập nhật bất cứ một phần tử dữ liệu nào trong bộ nhớ đệm Cơ chế thực hiện Tính toán di động @Hà Quốc Trung 2011 45  HA theo dõi các dữ liệu được lưu ở bộ nhớ đệm của các MS bằng  HLC=danh sách các cặp (x,T, invFlag), trong đó:  x là định danh của phần tử dữ liệu  T là thời gian vô hiệu hóa lần cuối của dữ liệu  invFlag=True nếu HA đã gửi yêu cầu vô hiệu hóa đến MS mà chưa nhận được trả lời  MS có thể gửi các thông báo chứa yêu cầu với dấu thời gian có thể coi là báo nhận thông báo vô hiệu hóa.  MS lưu trữ các phần tử dữ liệu được truy cập thường xuyên. Cập nhật dữ liệu Tính toán di động @Hà Quốc Trung 2011 46  Khi HA nhận được yêu cầu vô hiệu hóa cache từ phía server, HA xác định các MS đang sử dụng dữ liệu bằng cách tìm kiếm trong các HLC.  HA gửi các thông báo vô hiệu hóa tới các MS  Khi các MS nhận được thông báo, loại bỏ phần tử dữ liệu  Khi nhận được yêu cầu từ phía application, MS đọc trong cache.  Nếu có, MS trả lời application.  Nếu không có, gửi yêu cầu cập nhật phần tử đến HA.  HA yêu cầu server cung cấp dữ liệu,  gửi đến cho client,  cập nhật HLC Vấn đề: Tính toán di động @Hà Quốc Trung 2011 47  nếu MS ở trong trạng thái ngủ một thời gian=>  tất cả các yêu cầu vô hiệu hóa đều phải truyền lại?  Yêu cầu nào phải truyền lại?  Cơ chế  Sau khi thiết lập lại kết nối với HA, MS gửi một thông báo probe (nếu có nhu cầu gửi thông báo khác thì không cần gửi thông báo probe) đến cho HA, chứa dấu thời gian của MS  HA căn cứ vào dấu thời gian của MS để xác định những phần tử dữ liệu nào trong cache của MS không còn giá trị và gửi yêu cầu vô hiệu hóa đến cho MS  MS có thể xác định được là dữ liệu nào đã bị thay đổi trong quá trình ngắt kết nối Ví dụ Tính toán di động @Hà Quốc Trung 2011 48 Mobile Host (MH) Wireless Access Point Data Server Time Query (y,t1) Invalidation (x,t1) Ignored Data Server . . . Internet . . . x changed X Z * * F F X Z t0 * Y F Z * F t0 t1 t2 (y,t2) Data Query + Probe (*,t2) t3 t4 t5 MH awake Sleeping (y,z,t5) Y Z * T T t3 X Z * T T t3 y changed z changed 1) Fetch y from server 2) Add (y,t2) to HLC 3) Forward y to MH First query after wakeup x z t0 z t1 y z t2 * t5 Cache Data Timestamp Home Location Cache (HLC) Maintaining in HA D a ta ID T im e s t a m p In v a lid fla g Chính sách sử dụng cache Tính toán di động @Hà Quốc Trung 2011 49  Dữ liệu không thay đổi: luôn luôn dùng phiên bản cục bộ  Dữ liệu có thay đổi=> lựa chọn cache  Không bao giờ (SA-Never)  Luôn luôn (SA-Always)  Trung gian  Hiệu quả?  Biết trước lịch thay đổi=> tối ưu hóa cache  Không biết trước=> thuật toán trực tuyến Huang 1998: cơ chế cửa sổ trượt Tính toán di động @Hà Quốc Trung 2011 50  Các thao tác trên đơn vị dữ liệu  wm, ws, rm, rs. Chi phí tương ứng là 0,1,1,0  Lịch cập nhật dữ liệu s=> cost C(s)  Ví dụ: c=ws, rm, rm, ws  Nếu dùng chính sách Always, cost=?  Nếu dùng chính sách Never, cost=?  Theo dõi một cửa sổ kích thước k  Nếu ws cache  Nếu ws >=k/2=> không cache  Cần quan tâm tới các yếu tố khác  Nhiều đơn vị dữ liệu, Ngắt kết nối Tóm tắt Tính toán di động @Hà Quốc Trung 2011 51  Tổng quan  Quảng bá và phổ biến dữ liệu  Phân phối băng thông cho kênh quảng bá  Lập lịch cho kênh quảng bá  Mobile Caching  Caching cho các hệ thống Push-Based  Quảng bá các thông báo vô hiệu hóa cache  Cơ chế không đồng bộ có trạng thái  Cơ chế cửa sổ trượt

Các file đính kèm theo tài liệu này:

  • pdf05_datadissemination_0407_1789966.pdf
Tài liệu liên quan