16-07-2013, 02:32 PM
Broadcast data dissemination
Broadcast data .ppt (Size: 116 KB / Downloads: 11)
Assumptions for Broadcast Disks
Wireless data broadcasting can be viewed as "storage on the air".
Periodic broadcast - broadcast cycles or bcycles
Bucket: logical unit of broadcast
Each bucket has an address or sequence number within the broadcast.
Data changes often
Each successive broadcast may differ in size and content
No updates during a particular broadcast.
Client has no prior knowledge of the structure or content of the broadcast.
Clients are interested in fetching a particular record identified by a key.
Access time: average time elapsed between the beginning of the search for an item to the reading of it from the broadcast channel
Listening/Tuning time: the amount of time spent listening to the broadcast channel
Broadcast Disks
Multi-Disks Organization [Acharya et. al, SIGMOD95]
The frequency of broadcasting each item depends on its access probability.
Data broadcast with the same frequency are viewed as belonging to the same disk.
Multiple disks of different sizes and speeds are superimposed on the broadcast medium.
No variant in the inter-arrival time of each item.
Indexing
(1,M) Indexing:
We broadcast the index M times during one version of the data.
All buckets have the offset to the beginning of the next index segment.
Distributed Indexing
Cuts down on the replication of index material
Divides the index into:
replicated top L levels, non-replicated bottom 4-L levels
Flexible Indexing
Broadcast divided into p data segments with sorted data.
A binary control index is used to determine the data segment
A local index to locate the specific item within the segment
Access protocol
Index buckets hold the directory, data buckets hold data.
User tunes in to find out when a needed index bucket is broadcasted.
Synchronize by accessing a pointer that tells the user when to tune in for the data.
After you synchronize you must access the data in the same broadcast.
Tune in to the data at the right time.
Caching in Broadcasting
Data are cache to improve access time
Lessen the dependency on the server's choice of broadcast priority
Traditionally, clients cache their "hottest" data to improve hit ratio
Cache data based on PIX:
Probability of access (P)/Broadcast frequency (X).
Cost-based data replacement is not practical:
requires perfect knowledge of access probabilities
comparison of PIX values with all resident pages
Alternative: LIX, LRU with broadcast frequency
pages are placed on lists based on their frequency (X)
lists are ordered based on L, the running avg. of interaccess times
page with lowest LIX = L/X is replaced