US6070191A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data distribution techniques for load-balanced fault-tolerant web access
Assignee: Nokia of America Corp
•
Filing: 1997-10-17
•
Granted: 2000-05-30
•
Expires: 2017-10-17
Abstract
Abstract A server system for processing client requests received over a communication network includes a cluster of N document servers and at least one redirection server. The redirection server receives a client request from the network and redirects it to one of the document servers, based on a set of pre-computed redirection probabilities. Each of the document servers may be an HTTP server that manages a set of documents locally and can service client requests only for the locally-available documents. A set of documents are distributed across the document servers in accordance with a load distribution algorithm which may utilize the access rates of the documents as a metric for distributing the documents across the servers and determining the redirection probabilities. The load distribution algorithm attempts to equalize the sum of the access rates of all the documents stored at a given document server across all of the document servers. In the event of a server failure, the redirection probabilities may be recomputed such that the load of client requests is approximately balanced among the remaining document servers. The redirection probabilities may also be recomputed periodically in order to take into account changes in document access rates and changes in server capacity. The recomputation may be based on a maximum-flow minimum-cost solution of a network flow problem.
Inventors
- 👤 Balakrishnan Narendran
- 👤 Sampath Rangarajan
- 👤 Shalini Yajnik
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 13:29
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5005; G06F9/5027; G06F9/505; G06F9/5083; H; H04; H04L; H04L67/00; H04L67/01; H04L67/10; H04L67/1001; H04L67/1004; H04L67/1023; H04L67/1095; H04L69/00; H04L69/30; H04L69/32; H04L69/322; H04L69/329; H04L67/1034
Claims Analysis
Total Claims: 64
Claim 1
Independent Claim
92 words
A method of processing client requests received in a server system over a communication network, the method comprising the steps of: determining a distribution of a set of documents over a plurality of servers based at least in part on access rates of at least a subset of the documents; computing a set of redirection probabilities based on the distribution; routing a client request to a redirection server; and redirecting the client request from the redirection server to one of the plurality of document servers based on the set of redirection probabilities.
Claim 2
Independent Claim
92 words
A method of processing client requests received in a server system over a communication network, the method comprising the steps of: determining a distribution of a set of documents over a plurality of servers based at least in part on access rates of at least a subset of the documents; computing a set of redirection probabilities based on the distribution; routing a client request to a redirection server; and redirecting the client request from the redirection server to one of the plurality of document servers based on the set of redirection probabilities.
Claim 3
Dependent Claim
17 words
The method of claim 1 wherein at least one of the document servers is an HTTP server.
Claim 4
Dependent Claim
28 words
The method of claim 1 wherein each of the document servers provides access to only a subset of a given set of documents available in the server system.
Claim 5
Dependent Claim
22 words
The method of claim 3 wherein the subset of documents for a given document server are available locally on that document server.
Claim 6
Dependent Claim
25 words
The method of claim 3 wherein the subset of documents for a given document server are available to that server over a local area network.
Claim 7
Dependent Claim
36 words
The method of claim 3 wherein the redirection server redirects a request for a given document to one of the document servers only if a copy of the given document is available to that document server.
Claim 8
Dependent Claim
30 words
The method of claim 1 wherein the documents are permitted to be replicated, such that more than one document server may be a candidate for servicing a given client request.
Claim 9
Dependent Claim
34 words
The method of claim 1 further including the step of determining the redirection probabilities and an initial distribution of the set of documents across the plurality of document servers using a load distribution algorithm.
Claim 10
Dependent Claim
35 words
The method of claim 8 wherein the load distribution algorithm ensures that at least a specified number k of replicas of each document are present in the system after the initial document distribution is complete.
Claim 11
Dependent Claim
39 words
The method of claim 8 wherein the system includes N document servers and the load distribution algorithm ensures that no more than N-1 redundant replicas of documents are present in the system after the initial document distribution is complete.
Claim 12
Dependent Claim
33 words
The method of claim 8 wherein the load distribution algorithm uses a load balancing metric to distribute the documents across the document servers such that request load is balanced across the document servers.
Claim 13
Dependent Claim
17 words
The method of claim 11 wherein the load balancing metric is the access rates of the documents.
Claim 14
Dependent Claim
35 words
The method of claim 12 wherein the load distribution algorithm attempts to equalize the sum of the access rates of all the documents accessible to a given document server across all of the document servers.
Claim 15
Dependent Claim
44 words
The method of claim 11 wherein the load balancing metric is scaled access rates of the documents, wherein one of the scaled access rates is obtained for a given document by multiplying an access rate for that document by the size of that document.
Claim 16
Dependent Claim
45 words
The method of claim 12 wherein if λ is the rate at which client requests are received in the redirection server, the load distribution algorithm distributes the documents across N document servers such that the rate of requests redirected to each server is approximately λ/N.
Claim 17
Dependent Claim
55 words
The method of claim 8 wherein the load distribution algorithm includes the steps of: randomly selecting a document and one of the document servers; mapping an access rate of the selected document to the selected server; and if the selected server has additional capacity, randomly selecting another document and mapping it to the selected server.
Claim 18
Dependent Claim
72 words
The method of claim 16 wherein the load distribution algorithm includes the steps of: mapping a portion of an access rate of a randomly-selected document to the selected server; and if the selected server has insufficient capacity to accommodate the entire access rate of the randomly-selected document, selecting another document server at random, and mapping a remaining portion of the access rate of the randomly-selected document to the other randomly-selected document server.
Claim 19
Dependent Claim
29 words
The method of claim 17 wherein the selecting and mapping steps are repeated until the entire access rates of all of the documents have been mapped to document servers.
Claim 20
Dependent Claim
58 words
The method of claim 8 wherein the load distribution algorithm is a two-phase algorithm including a first phase and a second phase, and the first phase includes the step of distributing documents to the document servers in accordance with a round robin technique, and further wherein the first phase ends when any server exceeds its access rate capacity.
Claim 21
Dependent Claim
69 words
The method of claim 19 wherein the second phase of the two-phase algorithm distributes document copies to a document server until a cumulative maximum access rate is reached for that server, and then distributes document copies to another document server, and wherein replication of a given document copy takes place when a given document server exceeds its capacity when the given document copy is distributed to the given server.
Claim 22
Dependent Claim
26 words
The method of claim 1 further including the step of recomputing the set of redirection probabilities after a change in conditions associated with the server system.
Claim 23
Dependent Claim
46 words
The method of claim 21 wherein the change in conditions includes at least one of a failure of one or more of the document servers, a change in access rate for one or more documents, or a change in capacity of one of the document servers.
Claim 24
Dependent Claim
21 words
The method of claim 22 wherein the recomputing step is based on a maximum-flow minimum-cost solution of a network flow problem.
Claim 25
Dependent Claim
30 words
The method of claim 1 further including the step of utilizing a binning algorithm to redistribute documents from a failed one of the document servers to the remaining document servers.
Claim 26
Dependent Claim
88 words
A server system for processing client requests received over a communication network, the system comprising: a plurality of document servers, wherein a distribution of a set of documents over the plurality of document servers is determined based at least in part on access rates of at least a subset of the documents; and at least one redirection server for receiving a client request and for redirecting the client request to one of the plurality of document servers based on a set of redirection probabilities computed from the distribution.
Claim 27
Dependent Claim
88 words
A server system for processing client requests received over a communication network, the system comprising: a plurality of document servers, wherein a distribution of a set of documents over the plurality of document servers is determined based at least in part on access rates of at least a subset of the documents; and at least one redirection server for receiving a client request and for redirecting the client request to one of the plurality of document servers based on a set of redirection probabilities computed from the distribution.
Claim 28
Dependent Claim
17 words
The apparatus of claim 25 wherein at least one of the document servers is an HTTP server.
Claim 29
Dependent Claim
28 words
The apparatus of claim 25 wherein each of the document servers provides access to only a subset of a given set of documents available in the server system.
Claim 30
Dependent Claim
22 words
The apparatus of claim 27 wherein the subset of documents for a given document server are available locally on that document server.
Claim 31
Dependent Claim
25 words
The apparatus of claim 27 wherein the subset of documents for a given document server are available to that server over a local area network.
Claim 32
Dependent Claim
36 words
The apparatus of claim 27 wherein the redirection server redirects a request for a given document to one of the document servers only if a copy of the given document is available to that document server.
Claim 33
Dependent Claim
30 words
The apparatus of claim 25 wherein the documents are permitted to be replicated, such that more than one document server may be a candidate for servicing a given client request.
Claim 34
Dependent Claim
31 words
The apparatus of claim 25 wherein the redirection probabilities are determined and the set of documents are distributed across the plurality of document servers in accordance with a load distribution algorithm.
Claim 35
Dependent Claim
35 words
The apparatus of claim 32 wherein the load distribution algorithm ensures that at least a specified number k of replicas of each document are present in the system after an initial document distribution is complete.
Claim 36
Dependent Claim
39 words
The apparatus of claim 32 wherein the system includes N document servers and the load distribution algorithm ensures that no more than N-1 redundant replicas of documents are present in the system after the initial document distribution is complete.
Claim 37
Dependent Claim
33 words
The apparatus of claim 32 wherein the load distribution algorithm uses a load balancing metric to distribute the documents across the document servers such that request load is balanced across the document servers.
Claim 38
Dependent Claim
17 words
The apparatus of claim 35 wherein the load balancing metric is the access rates of the documents.
Claim 39
Dependent Claim
44 words
The apparatus of claim 35 wherein the load balancing metric is scaled access rates of the documents, wherein one of the scaled access rates is obtained for a given document by multiplying an access rate for that document by the size of that document.
Claim 40
Dependent Claim
35 words
The apparatus of claim 36 wherein the load distribution algorithm attempts to equalize the sum of the access rates of all the documents accessible to a given document server across all of the document servers.
Claim 41
Dependent Claim
45 words
The apparatus of claim 32 wherein if λ is the rate at which client requests are received in the redirection server, the load distribution algorithm distributes the documents across N document servers such that the rate of requests redirected to each server is approximately λ/N.
Claim 42
Dependent Claim
54 words
The apparatus of claim 32 wherein the load distribution algorithm is a two-phase algorithm including a first phase and a second phase, and the first phase distributes documents to the document servers in accordance with a round robin technique, and further wherein the first phase ends when any server exceeds its access rate capacity.
Claim 43
Dependent Claim
69 words
The apparatus of claim 40 wherein the second phase of the two-phase algorithm distributes document copies to a document server until a cumulative maximum access rate is reached for that server, and then distributes document copies to another document server, and wherein replication of a given document copy takes place when a given document server exceeds its capacity when the given document copy is distributed to the given server.
Claim 44
Dependent Claim
21 words
The apparatus of claim 25 wherein the redirection probabilities are recomputed after a change in conditions associated with the server system.
Claim 45
Dependent Claim
46 words
The apparatus of claim 42 wherein the change in conditions includes at least one of a failure of one or more of the document servers, a change in access rate for one or more documents, or a change in capacity of one of the document servers.
Claim 46
Independent Claim
97 words
An apparatus for processing client requests received in a server system over a communication network, the apparatus comprising: means for determining a distribution of a set of documents over a plurality of servers based at least in part on access rates of at least a subset of the documents; means for computing a set of redirection probabilities based on the distribution; means for routing a client request to a redirection server; and means for redirecting the client request from the redirection server to one of the plurality of document servers based on the set of redirection probabilities.
Claim 47
Independent Claim
97 words
An apparatus for processing client requests received in a server system over a communication network, the apparatus comprising: means for determining a distribution of a set of documents over a plurality of servers based at least in part on access rates of at least a subset of the documents; means for computing a set of redirection probabilities based on the distribution; means for routing a client request to a redirection server; and means for redirecting the client request from the redirection server to one of the plurality of document servers based on the set of redirection probabilities.
Claim 48
Dependent Claim
28 words
The apparatus of claim 44 wherein each of the document servers provides access to only a subset of a given set of documents available in the server system.
Claim 49
Dependent Claim
31 words
The apparatus of claim 44 wherein the redirection probabilities and an initial distribution of the set of documents across the plurality of document servers are determined using a load distribution algorithm.
Claim 50
Dependent Claim
35 words
The apparatus of claim 46 wherein the load distribution algorithm ensures that at least a specified number k of replicas of each document are present in the system after the initial document distribution is complete.
Claim 51
Dependent Claim
39 words
The apparatus of claim 46 wherein the system includes N document servers and the load distribution algorithm ensures that no more than N-1 redundant replicas of documents are present in the system after the initial document distribution is complete.
Claim 52
Dependent Claim
33 words
The apparatus of claim 46 wherein the load distribution algorithm uses a load balancing metric to distribute the documents across the document servers such that request load is balanced across the document servers.
Claim 53
Dependent Claim
17 words
The apparatus of claim 49 wherein the load balancing metric is the access rates of the documents.
Claim 54
Dependent Claim
44 words
The apparatus of claim 49 wherein the load balancing metric is scaled access rates of the documents, wherein one of the scaled access rates is obtained for a given document by multiplying an access rate for that document by the size of that document.
Claim 55
Dependent Claim
23 words
The apparatus of claim 44 wherein the set of redirection probabilities arc recomputed after a change in conditions associated with the server system.
Claim 56
Dependent Claim
46 words
The apparatus of claim 52 wherein the change in conditions includes at least one of a failure of one or more of the document servers, a change in access rate for one or more documents, or a change in capacity of one of the document servers.
Claim 57
Independent Claim
98 words
An apparatus for processing client requests received in a server system over a communication network, the apparatus comprising: a memory for storing a set of redirection probabilities; and a processor operative to determine a distribution of a set of documents over a plurality of servers based at least in part on access rates of at least a subset of the documents; to compute the set of redirection probabilities based on the distribution; to receive a client request; and to redirect the client request to one of the plurality of document servers based on the set of redirection probabilities.
Claim 58
Independent Claim
98 words
An apparatus for processing client requests received in a server system over a communication network, the apparatus comprising: a memory for storing a set of redirection probabilities; and a processor operative to determine a distribution of a set of documents over a plurality of servers based at least in part on access rates of at least a subset of the documents; to compute the set of redirection probabilities based on the distribution; to receive a client request; and to redirect the client request to one of the plurality of document servers based on the set of redirection probabilities.
Claim 59
Independent Claim
100 words
A method of processing client requests received in a server system over a communication network, the method comprising the steps of: determining a distribution of a set of documents over a plurality of servers of the server system based at least in part on access rates of at least a subset of the documents; computing a set of redirection probabilities based on the distribution; storing the set of redirection probabilities in a memory of the system; receiving a client request; and routing the client request to one of the plurality of document servers based on the set of redirection probabilities.
Claim 60
Independent Claim
100 words
A method of processing client requests received in a server system over a communication network, the method comprising the steps of: determining a distribution of a set of documents over a plurality of servers of the server system based at least in part on access rates of at least a subset of the documents; computing a set of redirection probabilities based on the distribution; storing the set of redirection probabilities in a memory of the system; receiving a client request; and routing the client request to one of the plurality of document servers based on the set of redirection probabilities.
Claim 61
Independent Claim
91 words
A method of processing client requests received in a server system over a communication network, the method comprising the steps of: determining a distribution of a set of documents over a plurality of document servers based at least in part on access rates of at least a subset of the documents; computing a set of redirection probabilities based on the distribution; utilizing the distribution to compute a set of redirection probabilities; and routing a client request to one of the plurality of document servers based on the set of redirection probabilities.
Claim 62
Independent Claim
91 words
A method of processing client requests received in a server system over a communication network, the method comprising the steps of: determining a distribution of a set of documents over a plurality of document servers based at least in part on access rates of at least a subset of the documents; computing a set of redirection probabilities based on the distribution; utilizing the distribution to compute a set of redirection probabilities; and routing a client request to one of the plurality of document servers based on the set of redirection probabilities.
Claim 63
Independent Claim
110 words
A method of processing client requests received in a server system over a communication network, the method comprising the steps of: determining a distribution of a set of documents over a plurality of document servers of the server system based at least in part on access rates of at least a subset of the documents; computing a set of redirection probabilities based on the distribution; routing a client request from a redirection server of the server system to one of the plurality of document servers in the system based on the set of redirection probabilities; and recomputing the redirection probabilities after a change in conditions associated with the server system.
Claim 64
Independent Claim
110 words
A method of processing client requests received in a server system over a communication network, the method comprising the steps of: determining a distribution of a set of documents over a plurality of document servers of the server system based at least in part on access rates of at least a subset of the documents; computing a set of redirection probabilities based on the distribution; routing a client request from a redirection server of the server system to one of the plurality of document servers in the system based on the set of redirection probabilities; and recomputing the redirection probabilities after a change in conditions associated with the server system.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-30 | 2003-11-29 | 2004-05-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-30 | 2007-11-29 | 2008-05-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-30 | 2011-11-29 | 2012-05-30 | $7700.00 | Window Closed / Lapsed |