Electrical computers and digital processing systems: multicomput – Computer network managing – Computer network monitoring
Reexamination Certificate
1998-05-21
2002-08-20
Meky, Moustafa M. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer network managing
Computer network monitoring
C709S203000
Reexamination Certificate
active
06438593
ABSTRACT:
FIELD OF THE INVENTION
The present invention is related to data broadcasting. More particularly, the present invention relates to an improved method for information retrieval from broadcast disk systems.
BACKGROUND OF THE INVENTION
In traditional client-server architectures, such as the World Wide Web, data transfers are initiated by the clients. Such an architecture is referred to as a “pull” system because clients, by their requests, “pull” data from the server. An emerging alternative to pull systems are “push” systems. In push systems, the server repeatedly broadcasts or “pushes” data towards clients even though there is no request on the part of the clients for such data.
One type of push technology is referred to as a “broadcast disk system.” In broadcast disk systems, data is divided into a number of equal-sized pages. Such pages are broadcast in a round-robin manner by a server. The name “broadcast disk” derives from the broadcast schedule, which is a circular repetition of the pages. Broadcast disk systems have been in use since the early 1980s by many national television companies in Western Europe. Moreover, broadcast disks have also been used in high-throughput multiprocessor database systems over high-bandwidth networks and wireless telecommunications systems. Typical of push systems, broadcast disk systems are particularly useful for disseminating massive amounts of information to a large number of clients.
FIG. 1
depicts, figuratively, a broadcast disk system that is implemented using wireless telecommunications technology. It should be understood that a broadcast disk system may alternatively be implemented as a wireline system. The broadcast disk system comprises server
102
including appropriate radios and processors (not shown) for broadcasting information or data items on pages P
l
-P
n
in a broadcast cycle
104
. The pages of data items are broadcast by antenna
106
to aplurality of clients, four of which clients, C
1
-C
4
, are shown in FIG.
1
. The clients receive each particular page at substantially the same time.
Since the pages are broadcast according to a set schedule unrelated to a particular client's need for a specific item of information, a client may disadvantageously have to wait a long time for desired information to be broadcast. Such a scenario is illustrated with reference to
FIG. 1
, which depicts server
102
broadcasting page P
j
at time T
1
. For the purpose of the present example, it is assumed that client C
1
requires, at time T
1
, a data item that is located on page P
i
. It is evident from the illustration that client C
1
will have to wait the better part of a broadcast cycle until page P
i
is again broadcast.
To improve the performance (i.e., decrease the waiting time) of broadcast disk systems, client storage resources are advantageously integrated with the broadcast disk system. In particular, such storage resources allow a client to store at least some of the broadcasted pages in a local fast memory. If a page desired by the client turns out to be stored in such fast memory, such a page request can be satisfied immediately. For example, if client C
1
possessed such storage capabilities, and has page P
i
stored in its fast memory at time T
1
, the page request for page P
i
will be immediately satisfied.
It will be appreciated that the storage capacity of a client's fast memory is typically insufficient for storing all information broadcast by the broadcast disk system. As such, pages must be selectively stored. The contents of a client's fast memory typically changes on a substantially regular basis as a client adds pages to the fast memory and evicts others to make room for the added pages. Returning to the example, if client C
1
chooses not to store page P
i
in its fast memory, or, if page P
i
is stored but the client decides to evict it before time T
1
, then the client will have to wait for page P
i
to be broadcast again by the server, thereby incurring a “cost.”
The aforementioned technique wherein client storage resources are used for storing broadcasted pages is referred to as “paging.” A broadcast disk system incorporating paging is referred to as broadcast disk paging (BDP) system. A client's objective is to reduce, to a practical minimum, the time (i.e., cost) needed to satisfy a sequence of page requests.
The prior art has utilized a paging method referred to as “least recently used” (“LRU”) to improve broadcast disk system performance. In the LRU method, as a page is requested it is time-stamped. The time stamp is continually updated to reflect the most recent request for each particular page. When a page fault occurs (i.e., a requested page is not in fast memory), the least recently requested page is evicted from fast memory and the requested page, once broadcast, is added thereto.
The cost, A, for a paging method can be evaluated relative to the cost, C, of an optimal paging method. In an optimal paging method, the schedule of page requests is known Thus, pages can be stored and evicted in fast memory in an “optimum” manner. The LRU method achieves a relatively poor competitive ratio, A/C, of O (n·k), where n is the number of pages being broadcast, k is the size of the fast memory and the notation “O,” referred to as “big O,” or “on the order of,” is a conventional notation defined for use herein as follows: a function ƒ (x) is said to be “O (g (x))” is there exists a constant, c, such that for every x, ƒ(x)≦c·g (x).
In view of the poor competitive ratio achieved by the aforementioned prior art paging method, the art would benefit from a new paging method having improved competitive performance.
SUMMARY OF THE INVENTION
A paging method for information retrieval from broadcast disk systems is described. In some embodiments, the present method advantageously achieves a competitive ratio of O (n log k), which is significantly better than that of the prior art LRU methods. The method proceeds in response to a page request (e.g., a request for an item of data, which request originates from a program operating on a processor). To satisfy the request in an efficient manner, a three- “color” labelling scheme is advantageously used, wherein:
(1) Fast memory is checked for the requested page.
(2) If the requested page is present in the fast memory, the request is considered to be immediately fulfilled.
If the requested page is not present in the fast memory, and
(A) if the requested page is not presently being broadcasted, and
(i) if the page being broadcasted is “grey,” indicating that it has “somewhat recently” been requested, then the grey page is stored in fast memory;
(ii) if the page being broadcasted is “white,” indicating that is has not been requested in some time, then the page is not added to fast memory.
(B) if the requested page is presently being broadcasted, it is re-labelled as “black” and added to fast memory.
As a black- or grey-labelled page is added to fast memory, the grey-labelled page that is “least expensive” to reload into fast memory is evicted therefrom to make room for the added page, as required.
(3) When fast memory is filled with black-labelled pages, all grey-labelled pages (none of which will be in fast memory) are re-labelled as “white” to indicate that they have not been requested in quite some time, and all black-labelled pages are relabelled as “grey” indicating that they have recently been requested. The method then repeats, adding and evicting pages as appropriate.
The operation wherein “grey” (i. e., non-requested) pages are added to fast memory while waiting for the requested page to be broadcasted is referred to herein as “prefetching.” Prefetching in accordance with the present teachings advantageously adds a “highest-cost” page to fast memory. By way of explanation, each non-requested page, at the completion of its broadcast, is a “highest-cost” page because it will take a complete broadcast cycle until that page is rebroadcasted. In accordance with the present teachings, if such a “highest-cost” page is a grey-labelled page indic
Khanna Sanjeev
Liberatore Vincenzo
Breyer Wayne S.
DeMont Jason Paul
DeMont & Breyer, LL
Lucent Technologies - Inc.
Meky Moustafa M.
LandOfFree
Method for information retrieval in broadcast disk systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for information retrieval in broadcast disk systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for information retrieval in broadcast disk systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2878526