Broadcast Disks

Broadcast Disks By Anubhav Trivedi

Introduction to Broadcasting 1. Broadcasting is distribution of audio and/or video signals which transmit

programs to an audience. The audience may be the general public or a relatively large sub-audience, such as children or young adults. 2. The sequencing of content in a broadcast is called a schedule. 3. Television and radio programs are distributed through radio

broadcasting or cable, often both simultaneously. By coding signals and having decoding equipment in homes, the latter also enables subscription-based channels and pay-per-view services. 4. Broadcasting forms a very large segment of the mass media.

Broadcasting to a very narrow range of audience is called narrowcasting. 5. The first regular television broadcasts began in 1937.

Asymmetric Communication Environments In many existing and emerging application domains the downstream communication capacity from servers to clients is much greater than the upstream communication capacity from clients back to servers. We refer to these environments as Asymmetric Communications Environments. Communications asymmetry can arise in two ways:

The first is from the bandwidth limitations of the physical communications medium. Stationary servers have powerful broadcast transmitters while mobile clients have little or no transmission capability. Because asymmetry can arise due to either physical devices or workload characteristics, the class of asymmetric communications environments spans a wide range of important systems and applications, encompassing both wired and wireless networks. Examples include: w Wireless networks with stationary base stations and mobile clients. W Information dispersal systems for volatile, time-sensitive information such as stock prices, weather information, traffic updates, factory floor information, etc. i Cable or satellite broadcast television networks with settop boxes that allow viewers to communicate with the broadcasting home office, and videoon-demand servers. o Information retrieval systems with large client populations, such as mailorder catalog services, mutual fund information services, software help desks, etc. Broadcast Disks 1. The Broadcast Disks project is focused on the use of data broadcast to

provide improved performance, scalability, and availability in an increasingly important class of networked environments, namely, those with asymmetric communication. Examples include wireless networks with mobile clients, cable and direct satellite broadcast networks, information dissemination and information retrieval applications. 2. Broadcast Disks exploits communication asymmetry by treating a broadcast stream of data that are repeatedly and cyclicly transmitted as a storage device. Two Main Components of Broadcast Disks 1. First, multiple broadcast programs (or ``disks'') with different latencies are superimposed on a single broadcast channel, in order to provide

improved performance for non-uniform data access patterns and increased availability for critical data. 2. Second, the technique integrates the use of client storage resources for caching and prefetching data that is delivered over the broadcast.

Broadcast Disk Approaches 1. Flat Approach: Data is broadcasted as a union of all that is requested in a

cyclic manner. 2. Skewed Approach or Random Approach: Requests are broadcasted randomly

as they arrive. The goal is that the interarrival time between two instances of the same item matches the clients needs.

Assumptions 1. Wireless data broadcasting can be as storage on the air. 2. Broadcast is periodic in nature. 3. Bucket is the logical unit of broadcast. 4. Each bucket has an address or sequence no. within the broadacast. 5. Data changes often. 6. Each successive broadcast may differ in size and contents. 7. No updates during a particular broadcast. 8. Client has no prior knowledge of the structure of the broadcast. 9. Clients are interested in fetching a particular record identified by a key.

10. Access Time: Avg. time elapsed between beginning of search of an item to

the downloading of it from broadcast channel. 11. Tuning Time: The time for which client is listening or tuning the

channel.

Broadcast Scheduling Algorithms 1. FCFS 2. Round Robin 3. Priority Scheduling 4. Request Wait Algorithm We will study Request wait algorithm Its Assumptions: 1. Broadcast has fixed data items. 2. Time Required to transmit 1 item is called “ Broadcast Tick ”. 3. Clients keep listening after making requests. 4. Delay time errors are ignored 5. No other errors

R X W Algorithm 1. For each page with pending requests , maintain: o PID – Page identifier o REQcnt – No. of outstanding requests o

1st arv – Time stamp of earliest unsatisfied request.

2. On request arrival

o Look up the page o If found o Increment REQcnt o Else o

Add new entry ; REQcnt = 1; 1st arv = current time

3. At each broadcast o Broadcast the page with maximum value of R X W where o R = REQcnt o

W = clock – 1st arv , where clock is current time

Data Management in broadcast disks The algorithm has the following steps (for simplicity, assume that data items are “pages”, that is, they are of a uniform, fixed length): 1. Order the pages from hottest (most popular) to coldest. 2. Partition the list of pages into multiple ranges,where each range contains pages with similar access probabilities. These ranges are referred to as disks. 3. Choose the relative frequency of broadcast for each of the disks. The only restriction on the relative frequencies is that they must be integers. For example given two disks, disk 1 could be broadcast three times for every two times that disk 2 is broadcast, thus, rel freq(1) = 3, and rel freq(2) = 2. 4. Split each disk into a number of smaller units. These units are called chunks (( ___ refers to the _____ chunk in disk ). First, calculate max chunks as the Least Common Multiple (LCM) of the relative frequencies. Then, split each disk into num chunks(i) = max chunks / rel freq(i) chunks. In the previous example, num chunks(1) would be 2, while num chunks(2) would be 3. 5. Create the broadcast program by interleaving the chunks of each disks