Method for information retrieval in broadcast disk systems

• US 6,438,593 B1
• Filed: 05/21/1998
• Issued: 08/20/2002
• Est. Priority Date: 05/21/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Liberatore, Vincenzo, Khanna, Sanjeev
• Primary Examiner(s): Meky, Moustafa M.
• Application Number:
  US09/082,786
• Time in Patent Office: 1,552 Days
• Field of Search: 709/212, 709/213, 709/214, 709/216, 709/200, 709/201, 709/223, 709/224, 709/203, 709/217, 709/218, 709/219, 709/229, 711/137, 711/136, 725/94, 725/115, 725/145, 348/461, 348/468
• US Class Current: 709/224
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0676 Magnetic disk device
• CPC Class Codes: H04H 20/16 Arrangements for broadcast or for distribution of identical information repeatedly
• CPC Class Codes: H04H 20/40 Arrangements for broadcast specially adapted for accumulation-type receivers
• CPC Class Codes: H04H 60/27 Arrangements for recording or accumulating broadcast information or broadcast-related information
• CPC Class Codes: H04N 21/23106 involving caching operations prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568

Abstract

A paging method for information retrieval from broadcast disk systems is described. In response to a page request (e.g., a request for an item of data), the method selectively stores and evicts, in and from a fast memory, pages of data broadcasted by the broadcast disk system. The methods proceeds using a three-“color” labelling scheme, wherein the label assigned to a broadcasted page is based on how recently a given page was last requested. If a requested page is stored in fast memory, then the request is immediately served. If the requested page is not stored in fast memory, the request cannot be served until the requested page is broadcasted. While waiting for the requested page to be broadcasted, certain “somewhat-recently” requested pages are “prefetched,” wherein they are stored in fast memory even though there is no pending request for such pages. Since the size of the fast memory is very small compared to the amount of information being broadcasted, only a small amount of the available information can be stored and there will be significant turnover in the particular stored pages as a function of the page requests. Pages are selected for eviction based upon the “cost” (to the competitive performance of the method) to replace the evicted page, wherein the least costly page to replace is evicted. The present method achieves a bounded competitive ratio of O (n log k), where n is the number of pages being broadcasted and k is the size of the fast memory.

Claims

1. A method for information retrieval, wherein the information is broadcast in the form of pages, comprising the steps of:

receiving a request for a first page;

labelling pages with first, second or third labels, wherein the first label designates pages more recently requested than the second label, and the second label designates pages more recently requested than the third label;

storing a broadcasted page in a fast memory when said broadcasted page is the requested first page, and labelling the broadcasted page with the first label, but only if the broadcasted page is not already stored in the fast memory; and

prefetching the broadcasted page when said broadcasted page is not the requested first page, said prefetching comprising storing said broadcasted page in the fast memory, but only if;

(i) the broadcasted page is not already stored in the fast memory; and

(ii) the broadcasted page is labelled with the second label.

2. The method of claim 1, and further comprising the step of serving the request if the requested first page is stored in the fast memory.

3. The method of claim 2, and further comprising the step of:

selecting a page for eviction from the fast memory and evicting the selected page if the fast memory is full, wherein, only a page labelled with the second label is eligible for eviction.

4. The method of claim 3, wherein the selecting step comprises selecting that eligible page which would be least expensive to reload into the fast memory.

5. The method of claim 4, and further comprising the steps of:

relabelling all pages when the fast memory is full of pages labelled with the first label, wherein,

(i) all pages having the second label are given, instead, the third label; and

(ii) all pages having the first label are given, instead, the second label.

6. The method of claim 2, wherein the step of serving the request further comprises the step of re-labelling the first page stored in fast memory with the first label if the stored first page has the second label.

7. The method of claim 1, wherein the step of receiving a request further comprises receiving a request for the first page from an applications software program.

8. A broadcast disk paging system, comprising:

a server operable to broadcast information organized into a plurality of equal-sized pages, and

a client operable to receive the broadcasted pages of information, the client comprising;

means for receiving the broadcasted pages;

a fast memory;

selecting means for selecting pages to store in the fast memory in response to a request for a first page, said selecting means operable to;

(i) label pages with at least first or second labels, the first label designating pages more recently requested than the second label; and

(ii) prefetch a page labelled with the second label when said page is being broadcast, but only if said page is not the first requested page and said page is not stored in the fast memory.

9. The broadcast disk paging system of claim 8, wherein the server comprises a base station operable to broadcast the pages of information via an antenna, and means for receiving the broadcasted pages comprises an antenna and a receiver.

10. The broadcast disk paging system of claim 8, wherein the client further comprises an applications program that originates the page request.

11. The broadcast disk paging system of claim 8, wherein the client comprises:

an appropriately-programmed general purpose processor;

a memory for storing the selecting means embodied as software; and

the fast memory, in which broadcasted pages are stored, wherein the processor is operable to run the selecting means and store pages in the fast memory.

12. The broadcast disk paging system of claim 11, wherein the client further comprises:

an applications software program stored in the memory.

13. A computer-readable storage medium comprising encoded computer-readable program instructions for use in conjunction with a programmable computer, which instructions cause the computer to selectively store information, in response to a request for a first page of information, wherein the information is stored in a fast memory that is in communication with the programmable computer, the instructions further operable to cause the computer to:

(i) label pages with at least first or second labels, the first label designating pages more recently requested than the second label; and

(ii) prefetch a page labelled with the second label when said page is being broadcast, but only if said page is not the first requested page and said page is not