12-07-2013, 04:16 PM
Broadcast data dissemination
[attachment=56582]
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 Data Dissemination
business data, e.g., Vitria, Tibco
election coverage data
stock related data
traffic information
sportscasts, e.g., Praja
Datatacycle [Herman]
Broadcast disks
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.
Selective Tuning
Basic broadcast access is sequential
Want to minimize client's access time and tuning time.
active mode power is 250mW, in doze mode 50μW
What about using database access methods?
Hashing: broadcast hashing parameters h(K)
Indexing: index needs to be broadcast too
"self-addressable cache on the air"
(+) "listening/tuning time" decreases
(-) "access time" increases
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
[attachment=56582]
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 Data Dissemination
business data, e.g., Vitria, Tibco
election coverage data
stock related data
traffic information
sportscasts, e.g., Praja
Datatacycle [Herman]
Broadcast disks
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.
Selective Tuning
Basic broadcast access is sequential
Want to minimize client's access time and tuning time.
active mode power is 250mW, in doze mode 50μW
What about using database access methods?
Hashing: broadcast hashing parameters h(K)
Indexing: index needs to be broadcast too
"self-addressable cache on the air"
(+) "listening/tuning time" decreases
(-) "access time" increases
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